Colin James - Sequentialising Parallel Moves
Sequentialising Parallel Moves
This article aims to describe the topic of lowering parallel moves in<br>a compiler. Many compiler textbooks do not cover this topic at all,<br>rendering their treatment of things such as emitting register<br>arguments (for calls) incorrect in general.
Introduction
A set of parallel moves (or assignments), $(l_1, l_2, \ldots, l_n) := (l’_1, l’_2, \ldots, l’_n)$<br>, is a set of moves between locations (typically, registers or stack<br>slots) that, semantically, must be done at the same time. The naive<br>lowering of such a construct, by means of emitting a sequence of<br>individual moves, is not correct in general. A correct lowering must<br>take care to honour dependencies between moves (in the case that the<br>destination and source locations intersect) and to deal with cycles<br>appropriately (often by introducing a temporary location to break the<br>cycle).
Example
Parallel moves appear in a few places in compilers. Most notably, in the destruction of<br>ϕ-nodes when going out of SSA and when populating register arguments<br>for calls. This article will focus on the latter for demonstration.
Consider the following C snippet:
int bar(int y, int x);
int foo(int x, int y) {<br>return bar(y, x);<br>If we assume a calling convention where arguments are passed in registers r0, r1, ..., rN,<br>then we expect that this function will enter with x within r0 and y within r1. These variables<br>are then passed to bar in reverse order. In order to do this shuffling of registers correctly, some care must be taken.
For example, consider the naive (incorrect) lowering of this function:
foo:<br>mov r0, r1<br>mov r1, r0<br>b bar<br>This is clearly incorrect as it will logically result in a call similar to bar(y, y). In other words, we have overwritten one of our source registers because it also appears as a destination register within our parallel move. This example is a canonical example of the "swap" problem (as it is known in SSA literature).
In order to do this lowering correctly, the compiler must identify that there is a cycle between these assignment locations and either break the cycle with a temporary register (to preserve the overwritten value) or with a dedicated swap instruction (such as xchg in x86_64).
For example, the following is a correct lowering:
foo:<br>mov r2, r0<br>mov r0, r1<br>mov r1, r2<br>b bar<br>As we will see later, it turns out you can always sequentialise<br>parallel moves with a single temporary location (per register class).<br>The following sections describe how we can tackle this problem in a<br>principled way by identifying the two major categories of dependencies<br>between locations.
Location Transfer Graph
In order to visualise dependencies between locations involved in a<br>parallel move, it is convenient to create a graph representation.
For each $(l_i, l’_i)$ pair involved in the parallel move $(l_1, l_2,<br>\ldots, l_n) := (l’_1, l’_2, \ldots, l’_n)$, we add an edge $l’_i \to<br>l_i$ to the graph. This edge can be read “$l’_i$ populates $l_i$” or<br>“$l_i$ gets its value from $l’_i$”.
Consider the graph created for the parallel moves $(B, D, C) := (A, A, B)$:
To aid the presentation, each edge is labelled with its index as it<br>appears in the parallel move notation.
If we were to naively introduce copies in order of appearance, we’d<br>get:
B := A<br>D := A<br>C := B<br>This is wrong, as $B$’s value is overwritten whilst another move’s<br>destination depends on it as a source. In the above case, a correct<br>sequentialisation of copies does not require a temporary, as no swap<br>occurs between locations (there is no cycle in the graph).
Consider a correct lowering:
C := B<br>B := A<br>D := A<br>This is correct because $B$’s value is used by its dependent move<br>before it itself is overwritten (as part of the move it’s involved in<br>with $A$). Similarly, the following is also a correct lowering:
C := B<br>D := A<br>B := A<br>Each correct lowering corresponds to traversing the transfer location<br>graph in post-order. This makes sense when you consider that<br>post-order traversals of graphs result in a node visitation order that<br>corresponds to a valid topological sort of the transpose (reverse)<br>graph. This knowledge motivates an algorithm that, before emitting a<br>move $t_i := t’_i$ considers all moves whose source depends on $t_i$<br>(in other words, processes its successors before itself - exactly a<br>post-order traversal).
Dealing with Cycles
However, what if cycles exist in the location transfer graph? In the<br>case of cycles, we can always use a single temporary to break the<br>cycle. The basic idea is that if we begin processing edge $X_1 \to<br>X_2$ in post-order, by considering edges $X_2 \to \ldots$ first, if we<br>ever get to the point of considering an edge $X_j \to X_1$, we have<br>found a cycle. The strategy for resolving cycles uses a temporary<br>location to preserve $X_1$’s in the meantime so that all post-order<br>dependent moves can be emitted as normal. Then, when we get around to<br>emitting the move for $X_1 \to X_2$ (after all...