Lesson 16.7 — Leaving SSA well: Boissinot et al., parallel-copy sequentialization, coalescing¶

Techniques: Boissinot et al.'s out-of-SSA translation (phi isolation with parallel copies, value-based interference, interference checks in dominance order, fast liveness checking), parallel-copy sequentialization with the minimum number of moves, copy coalescing (aggressive, on SSA names and congruence classes); preview of SSA-based register allocation (Ch 22) · Pebble implements: lab L2's split method (optimal sequentialization) and coalesce method (value-based coalescing) · Prerequisites: Lesson 16.6, Lesson 14.3 (liveness) · Time: 5–6 hours

Lesson 16.6 ended with a choice: split edges and order copies (correct, many copies) or isolate every phi with Method I (correct, even more copies) and hope a coalescer removes them. Boissinot, Darte, Rastello, Dupont de Dinechin and Guillon showed that the second path, done carefully, is both the simplest and the best: treat the copies an edge needs as one parallel copy, coalesce names aggressively using a notion of interference that knows when two names hold the same value, check interference cheaply using dominance, and finally turn each remaining parallel copy into sequential moves with the fewest moves possible [BDR+09]. Lab L2's coalesce method is a compact version of this pipeline.

1. Problem and motivation¶

The problem. Produce a phi-free program equivalent to the SSA input with as few copies as possible, quickly (the translation runs on every function a JIT compiles), and without splitting edges when that can be avoided. Two sub-problems stand out and have exact solutions: deciding whether two names may share a variable (interference), and implementing one edge's parallel copy with sequential moves (sequentialization).

Boissinot et al.¶

Sreedhar's Method III avoids copies up front with a subtle case analysis (Lesson 16.6). Boissinot et al. invert the order: insert all Method I copies as parallel copies (virtually, without creating the names), then coalesce. What makes this work is a better interference test: two names whose live ranges overlap do not interfere if they provably hold the same value (a copy and its source), an observation from Chaitin's register allocator made systematic with SSA value numbers [BDR+09, AWZ88]. Checking interference between two congruence classes costs linear time when members are sorted by dominance, and liveness can be queried without liveness sets [BHG+08]. LLVM's register coalescer compares value numbers in the same spirit [LLVM-RegCoalescer].

Parallel-copy sequentialization¶

After coalescing, each edge still has a parallel copy $(d_1, \dots, d_k) \gets (s_1, \dots, s_k)$ over registers or variables. Executing it with ordinary moves requires an order and, for cycles, a spare location. The minimum number of moves is known exactly (Theorem 16.7.6), and a simple worklist algorithm achieves it [BDR+09; SSAB, Ch. 21]; C. May analyzed the problem in 1989 [May89], and CompCert uses a formally verified version [RSL08]. Go's register allocator solves the same problem on every edge ("shuffle") [Go-Regalloc].

Coalescing¶

Coalescing merges two copy-related names into one variable when they do not interfere, deleting the copy. In SSA destruction it is aggressive (merge whenever there is no interference, ignoring register pressure); in register allocation it is conservative (merge only if the graph stays colorable, Briggs's and George's tests, Ch 22). GCC coalesces SSA names into partitions before expanding to RTL [GCC-Coalesce]; LLVM coalesces virtual registers after phi elimination [LLVM-RegCoalescer].

2. Definitions and algorithms¶

Boissinot et al.¶

Lemma 16.7.1 (Interference in strict SSA)

Points are the program points between instructions; $\mathrm{def}(x)$ is the point just after $x$'s definition (block entry for a phi or block parameter). The live range $\mathrm{LR}(x)$ is $\{\mathrm{def}(x)\}$ together with every point where $x$ is live. In a strict SSA program, if $\mathrm{LR}(a) \cap \mathrm{LR}(b) \neq \emptyset$, then one definition, say $\mathrm{def}(a)$, dominates the other and $\mathrm{def}(b) \in \mathrm{LR}(a)$. Hence live ranges intersect iff one name is defined inside the live range of the other [BCH+02].

Proof

(i) Every point of $\mathrm{LR}(x)$ is dominated by $\mathrm{def}(x)$. Trivial for $\mathrm{def}(x)$ itself. If $x$ is live at $p$, some path $p \leadsto u$ to a use $u$ of $x$ avoids $\mathrm{def}(x)$. If $\mathrm{def}(x)$ did not dominate $p$, some path $r \leadsto p$ would avoid it too, and the concatenation would reach $u$ without passing $\mathrm{def}(x)$, contradicting strictness.

(ii) Order. Let $p \in \mathrm{LR}(a) \cap \mathrm{LR}(b)$. By (i), both definitions dominate $p$, and the dominators of one point form a chain (Theorem 15.1.6), so one of them, call it $\mathrm{def}(a)$, dominates the other.

(iii) $\mathrm{def}(b) \in \mathrm{LR}(a)$. If $\mathrm{def}(b) = \mathrm{def}(a)$ (two parameters of one block) this is immediate. If $p = \mathrm{def}(a)$, then $\mathrm{def}(b)$ dominates $\mathrm{def}(a)$ and vice versa, so they are equal. Otherwise $a$ is live at $p$ and $\mathrm{def}(a) \neq \mathrm{def}(b)$. Take a simple path $r \leadsto p$. It passes $\mathrm{def}(b)$ (which dominates $p$) exactly once, and its prefix up to $\mathrm{def}(b)$ passes $\mathrm{def}(a)$ (which dominates $\mathrm{def}(b)$). So $\mathrm{def}(a)$ occurs once, before $\mathrm{def}(b)$, and the segment $\mathrm{def}(b) \leadsto p$ avoids it. Append the $\mathrm{def}(a)$-free path from $p$ to a use of $a$: $a$ is live at $\mathrm{def}(b)$.

The converse is immediate: $\mathrm{def}(b)$ lies in both live ranges.

Definition 16.7.2 (Value; value-based interference)

The value $V(x)$ of an SSA name is $V(y)$ if $x$ is defined by a copy $x \gets y$, and $x$ itself otherwise (a phi or a computation defines a new value). Names $a \neq b$ interfere if their live ranges intersect (Lemma 16.7.1) and $V(a) \neq V(b)$ [BDR+09]. With $V(x) = x$ for all $x$ this is ordinary live-range interference. Two parameters of one block (two results of one parallel copy) always interfere. A congruence class is a set of names that will share one variable; classes interfere if some member of one interferes with some member of the other.

Algorithm 16.7.3 (Out of SSA by isolation and value-based coalescing)

Input: strict SSA in block-argument form.
Output: an equivalent program with parallel copies on edges, then sequential moves.
Precondition: strict SSA; liveness of SSA names (or a fast liveness checker).
Postcondition: equivalent (Theorem 16.7.8); every coalesced copy is gone; the remaining copies of each edge are sequentialized optimally (Theorem 16.7.6).
Invariant: no class ever contains two interfering names.

function OutOfSSA(F):
    for each name x: class[x] ← {x}
    for each edge P → B(a_1..a_k) in block order, for ℓ in 1..k:     # the copy p_ℓ ← a_ℓ
        if a_ℓ is a name and class[p_ℓ] ≠ class[a_ℓ]
           and not ClassesInterfere(class[p_ℓ], class[a_ℓ]):
            merge the two classes
    rename every name to its class representative (copies x = x vanish)
    for each edge e with remaining non-trivial copies:
        place them as in Algorithm 16.6.3 (end of P, start of B, or a split block)
        emit Sequentialize(the renamed copies of e, temp)             # Algorithm 16.7.5

Lab L2's Method::Coalesce is this algorithm with the pairwise test interfere(x, y) for every $x \in$ one class, $y \in$ the other. Boissinot et al. keep the Method I copies at both ends of the edge (a parallel copy at the end of $P$ and one at the start of $B$) and coalesce those too; merging a parameter directly with an argument, as here, is the same result when the placement of Algorithm 16.6.3 is used.

Algorithm 16.7.4 (Class interference in dominance order)

Input: two classes $A$, $B$, each without internal interference, each sorted by the preorder of its members' definitions in the dominator tree.
Output: whether some $a \in A$ and $b \in B$ interfere.
Precondition: strict SSA; a dominance test and a liveness query (isLiveAfter(x, def(y))).
Postcondition: returns true iff $A \cup B$ contains an interfering pair (Theorem 16.7.7).
Invariant: the stack holds the chain of members whose definitions dominate the current definition, innermost on top.

function ClassesInterfere(A, B):
    stack ← []
    for x in Merge(A, B) by preorder of def(x):
        while stack not empty and def(top(stack)) does not dominate def(x):
            pop stack
        if stack not empty:
            y ← top(stack)                          # the nearest dominating member
            if y and x come from different classes and V(x) ≠ V(y)
               and isLiveAfter(y, def(x)):
                return true
        push x
    return false

With value-based interference the nearest dominating member of the other class is not always enough; Boissinot et al. add an "equal intersecting ancestor" pointer per member to skip over members with the same value [BDR+09]. Without values (all $V(x) = x$) the test is Budimlić et al.'s [BCH+02].

Parallel-copy sequentialization¶

Algorithm 16.7.5 (Parallel-copy sequentialization)

Input: copies $(d_1 \gets s_1), \dots, (d_k \gets s_k)$ with distinct destinations; sources are locations or constants; one spare location $t$.
Output: a sequence of moves with the effect of the parallel copy on every location except $t$.
Precondition: the $d_i$ are distinct.
Postcondition: correct (Theorem 16.7.6) with exactly $\lvert\{i : d_i \neq s_i\}\rvert + c$ moves, where $c$ is the number of pure cycles.
Invariant: loc[s] is a location that currently holds the original value of $s$; a destination is ready when no pending copy's source value lives only there.

function Sequentialize(copies, t):
    pending ← { d_i | d_i ≠ s_i };  pred[d_i] ← s_i;  loc[s_i] ← s_i for all i
    ready ← [ d ∈ pending | no pending copy has loc[pred[·]] = d ]
    moves ← []
    while pending not empty:
        while ready not empty:
            d ← remove the first element of ready
            if d ∉ pending: continue
            x ← loc[pred[d]]
            append "d ← x" to moves;  remove d from pending
            if pred[d] is not a constant: loc[pred[d]] ← d      # later readers read d
            if x ∈ pending and no pending copy reads location x:
                append x to ready                              # x's old value is saved
        if pending not empty:                                  # only pure cycles remain
            d ← the first pending destination
            append "t ← d" to moves
            for every s with loc[s] = d: loc[s] ← t
            append d to ready
    return moves

The line loc[pred[d]] ← d is what makes the algorithm optimal: after c ← a, the old value of a also lives in c, so a copy b ← a can read c, and a becomes free. This is the oracle's sequentialize and lab L2's reference solution; [SSAB, Ch. 21] gives the same algorithm with loc and pred arrays.

Theorem 16.7.6 (Optimal number of moves)

Let the non-trivial copies $d \gets s$ form the copy graph with an edge $s \to d$ for each (every node has in-degree at most one). A pure cycle is a cycle of this graph none of whose nodes has an edge leaving the cycle. With one spare location, the minimum number of moves implementing the parallel copy is $n + c$, where $n$ is the number of non-trivial copies and $c$ the number of pure cycles; Algorithm 16.7.5 attains it.

Proof

Lower bound. Each destination $d$ must be written at least once, and the last write to $d$ must write the original value of $s = \mathrm{pred}(d)$: $n$ distinct moves ("final writes"). Take a pure cycle $C$ and consider the first move of the whole sequence that writes a node of $C$, say $x$. Just before it, $x$ still holds its original value, which some other node of $C$ (the successor of $x$ on the cycle) needs later; after the move, the original value of $x$ must still exist somewhere, so an earlier move $y \gets x$ copied it to a location $y$. No node of $C$ has been written yet, so $y \notin C$. Is this move a final write? A final write to $y$ writes $\mathrm{pred}(y)$'s value; $\mathrm{pred}(y) = x$ would be an edge $x \to y$ leaving the pure cycle $C$, which does not exist. So $y \gets x$ is an extra move, and it copies $x$'s value, a value of $C$; extra moves for different pure cycles copy values of different cycles, so they are distinct: at least $n + c$ moves. Upper bound: Algorithm 16.7.5 emits $n + c$ moves and is correct. Every emitted d ← x is a final write: $x$ holds $\mathrm{pred}(d)$'s original value by the invariant on loc, and $d$ is never written again ($d$ leaves pending). The invariant holds initially, is kept by loc[pred[d]] ← d (after the move $d$ holds that value too) and by the cycle break (t ← d saves $d$'s value and redirects loc); a location becomes ready only when no pending copy still needs a value that lives only there, so no value is destroyed before its last read. The inner loop ends when no pending destination is ready: every pending destination is then the only holder of some value a pending copy needs. Each pending node has one incoming copy and at least one pending reader, and there are as many readers (one per pending copy) as pending nodes, so each has exactly one reader, and the pending copies form disjoint cycles; none of them has an edge leaving to an already-written node (such a reader would have made it saved). They are pure cycles of the original graph: a node with an edge leaving its cycle would have been written by the tree hanging off it, which runs first because leaves are ready. The break costs one move per such cycle, after which the whole cycle drains through ready. Total: $n$ final writes $+ c$ breaks.

The oracle test ParallelCopies.test_sequentialize_is_correct_and_optimal checks every parallel copy over 4 locations (340 of them) by simulation, checks the count against the formula for all of them and against a breadth-first search for the true minimum on every seventh one.

Coalescing¶

Theorem 16.7.7 (Correctness of Algorithm 16.7.4 without values)

With $V(x) = x$ for all $x$, Algorithm 16.7.4 returns true iff some $a \in A$, $b \in B$ interfere.

Proof (after [BCH+02]; the value-based extension is [BDR+09])

By the invariant, when $x$ is processed the top of the stack is $x$'s parent: the member of $A \cup B$, processed earlier, whose definition is the nearest one dominating $\mathrm{def}(x)$. (Preorder lists every dominating definition before $x$. A member popped because its definition does not dominate $\mathrm{def}(x)$ cannot dominate any later definition either, since preorder leaves a subtree for good.)

Only real interference is reported. A report means $\mathrm{def}(x) \in \mathrm{LR}(y)$, so the live ranges intersect.

Every interference is found. Let $a, b \in A \cup B$ interfere. By Lemma 16.7.1, $\mathrm{def}(a)$ dominates $\mathrm{def}(b)$ and $\mathrm{def}(b) \in \mathrm{LR}(a)$. Label ties so that $a$ comes first. Following parents from $b$ gives a chain $b = y_0, y_1, \dots, y_k = a$ with $k \ge 1$ and definitions nested by dominance.

We show $\mathrm{def}(y_{k-1}) \in \mathrm{LR}(a)$. This is trivial if $\mathrm{def}(y_{k-1})$ equals $\mathrm{def}(a)$ or $\mathrm{def}(b)$. Otherwise $a$ is live at $\mathrm{def}(b)$. A simple path $r \leadsto \mathrm{def}(b)$ passes $\mathrm{def}(a)$ and then $\mathrm{def}(y_{k-1})$, once each, so the segment from $\mathrm{def}(y_{k-1})$ to $\mathrm{def}(b)$ avoids $\mathrm{def}(a)$. Extended by the $\mathrm{def}(a)$-free path from $\mathrm{def}(b)$ to a use of $a$, it shows that $a$ is live at $\mathrm{def}(y_{k-1})$.

So $y_{k-1}$ and its parent $a$ interfere. Each class is interference-free, so the two lie in different classes. The algorithm therefore tests exactly this pair when it processes $y_{k-1}$, and returns true then, if it has not already done so.

Theorem 16.7.8 (Coalescing non-interfering names preserves behavior)

Renaming every name of a congruence class to one variable, where no two members interfere in the value-based sense (Definition 16.7.2), and then implementing each edge's remaining parallel copy, gives a program equivalent to the SSA input.

Proof

Fix an execution and a class $K$ renamed to $v$. We show that whenever a member $x \in K$ is live at a point $p$ reached by the execution, $v$ holds the value $x$ has in the SSA run. Uses of $x$ then read the right value.

Setup. Let $q_0$ be the most recent execution of $\mathrm{def}(x)$ before $p$. At $q_0$, $v$ receives $x$'s value: the defining instruction now writes $v$, and for a parameter the sequentialized edge copy does (Theorem 16.7.6). On the executed segment from $q_0$ to $p$, $x$ is live at every point, because the segment followed by $p \leadsto \mathrm{use}(x)$ avoids $\mathrm{def}(x)$.

Other writes to $v$. Any write to $v$ on that segment is the definition of another member $y \in K$, and $\mathrm{def}(y) \in \mathrm{LR}(x)$ there. The live ranges intersect, and $x$, $y$ do not interfere, so $V(x) = V(y) = w$. Then $x$ and $y$ are both copies, through chains of copies, of the same name $w$.

Why the write is harmless. We claim no definition on those chains, including $\mathrm{def}(w)$, executes between $q_0$ and $p$. Take such a definition $\mathrm{def}(z)$ on $x$'s chain. It strictly dominates $\mathrm{def}(x)$ (strictness), so $\mathrm{def}(x)$ does not dominate it, and some path $r \leadsto \mathrm{def}(z)$ avoids $\mathrm{def}(x)$. If $\mathrm{def}(z)$ executed while $x$ was live, that path followed by the rest of the execution to a use of $x$ would avoid $\mathrm{def}(x)$, contradicting strictness. The same argument applied to each link $z$ of $y$'s chain (the name $z$ copies is live from its definition to $\mathrm{def}(z)$) shows that no earlier link of that chain, and in particular not $\mathrm{def}(w)$, re-executes between the copies along the chain. So $y$ copies the latest instance of $w$ before $\mathrm{def}(y)$, $x$ copies the latest one before $q_0$, and these coincide because $\mathrm{def}(w)$ does not execute between $q_0$ and $p$: the write stores the value $v$ already holds.

Remaining copies. Parameters of one block always interfere, so they never share a variable, and no parallel copy gets two equal destinations after renaming. Copies whose two sides were merged become $v \gets v$ and are dropped. The rest are implemented by Algorithm 16.7.5 (Theorem 16.7.6) and placed by Algorithm 16.6.3 (Theorem 16.6.7).

Placement at the end of $P$ is used only when $P$ has a single successor $B$. Then the only names live at that point but not at $B$'s entry are the arguments the parallel copy itself reads, and it reads them before it writes.

3. Worked example¶

Boissinot et al. on the running example¶

Braun's output for the running example (Lesson 16.3 §3) is transformed SSA: copies were folded, so arguments are constants and values from other variables' names. Its edge copies:

edge	copies (param ← arg)	critical?
A → B	x.2 ← 1, i.1 ← 0	no
B → E	y.3 ← y.0, x.3 ← x.2	yes
C → H	x.4 ← x.0	yes
D → E	y.3 ← y.1, x.3 ← x.0	no
E → H	x.4 ← x.3	yes
G → E	y.3 ← y.2, x.3 ← x.1	yes
G → H	x.4 ← x.1	yes
H → B	x.2 ← x.4, i.1 ← i.0	yes

Without coalescing (lab split): 13 copies, 6 split blocks. Algorithm 16.7.3 visits the copies in the order of the table (the oracle's trace, coalesce_classes(..., trace)):

step	edge	copy	classes interfere?	effect
1	B→E	y.3 ← y.0	no	{y.0, y.3}
2	B→E	x.3 ← x.2	no	{x.2, x.3}
3	C→H	x.4 ← x.0	no	{x.0, x.4}
4	D→E	y.3 ← y.1	no	{y.0, y.1, y.3}
5	D→E	x.3 ← x.0	no	{x.0, x.2, x.3, x.4}
6	G→E	y.3 ← y.2	no	{y.0, y.1, y.2, y.3}
7	G→E	x.3 ← x.1	no	{x.0, x.1, x.2, x.3, x.4}
8	H→B	i.1 ← i.0	no	{i.0, i.1}

(A → B carries only constants; E → H, G → H and H → B's x.2 ← x.4 are already inside one class when visited.) Every copy between names disappears; the result (lab coalesce) has 2 copies, x.2 = 1 and i.1 = 0, and no split block, because every edge's copy became trivial:

A:  x.2 = 1 ; i.1 = 0 ; goto B
B:  y.0 = add x.2, i.1 ; if i.1 goto C ; goto E
C:  x.2 = add y.0, 2 ; t.0 = lt x.2, 20 ; if t.0 goto D ; goto H
D:  y.0 = mul y.0, 2 ; goto E
E:  t.1 = gt y.0, 0 ; if t.1 goto F ; goto H
F:  x.2 = add x.2, y.0 ; y.0 = sub y.0, 7 ; goto G
G:  t.2 = rem x.2, 3 ; if t.2 goto E ; goto H
H:  i.1 = add i.1, 1 ; t.3 = lt i.1, 4 ; if t.3 goto B ; goto I
I:  return x.2

This is the original TAC program with renamed variables: coalescing undid SSA exactly. On the lost-copy program, by contrast, the single candidate $x_2 \gets x_3$ is rejected: $x_2$ is live after $x_3$'s definition (it is returned) and $V(x_2) = x_2 \neq x_3 = V(x_3)$. Two copies remain, and the edge is split.

Parallel-copy sequentialization¶

The oracle's trace for three parallel copies (sequentialize); loc shows only moved values ("a in d": the original a is now in d):

(1) $(a, b, c, d) \gets (b, c, a, a)$: a 3-cycle $a \to c \to b \to a$ with $d$ hanging off $a$ (not pure).

step	move	pending after	moved values
1	d ← a	a, b, c	a in d
2	a ← b	b, c	a in d, b in a
3	b ← c	c	a in d, b in a, c in b
4	c ← d	—	a in c, …

4 moves $= 4$ copies $+ 0$ pure cycles: the fan-out copy d ← a saved $a$, so no temporary is needed.

(2) $(a, b, c) \gets (b, c, a)$: a pure 3-cycle.

step	move	pending after	moved values
1	t ← a (break the cycle)	a, b, c	a in t
2	a ← b	b, c	a in t, b in a
3	b ← c	c	…, c in b
4	c ← t	—	a in c

4 moves $= 3 + 1$.

(3) $(a, b, c, d) \gets (b, a, d, 5)$: a pure 2-cycle, a chain $d \to c$ and a constant.

step	move	pending after
1	c ← d	a, b, d
2	d ← 5	a, b
3	t ← a (break)	a, b
4	a ← b	b
5	b ← t	—

5 moves $= 4 + 1$. The chain is done first because c was ready (no one reads it); after c ← d, d is free.

Try it

./course drill parallel-copy --seed 5 --difficulty hard --solution generates a parallel copy with several cycles, fan-out and constants, and grades your sequence by simulation and by move count.

4. Invariants and correctness¶

Boissinot et al.¶

Theorem 16.7.8 is the correctness of Algorithm 16.7.3; its invariant ("no class contains two interfering names") holds initially (singletons) and is maintained because two classes are merged only after ClassesInterfere returns false. Two points need care:

Why values matter. A copy b = a whose source stays live makes $a$ and $b$ overlap, although they always hold the same value. In tests/ch16/Inputs/value-copy.ssa, a and b = a are both read in block R, and the edges L → J and R → J pass a and b to J's parameter. Ordinary interference merges J's parameter with a and then refuses b (3 copies remain, as with split); value-based interference merges all three and leaves 0 copies. This is Chaitin's copy exception generalized [BDR+09]. The Braun output of the running example does not need values: there ordinary interference also leaves only the 2 constant copies.
Why parameters of one block always interfere. They are written by one parallel copy; merging two of them would make the copy write one variable twice. The lab's Interference class hard-codes this.

Parallel-copy sequentialization¶

Theorem 16.7.6 above. When it breaks: if two copies had the same destination (not a parallel copy at all), or if the spare location $t$ is itself a source or destination; the oracle picks tmp, or tmp.N when that name is taken.

Coalescing¶

Theorem 16.7.8 covers correctness. Optimality does not hold: finding the coalescing that removes the most copies is NP-complete in general (aggressive coalescing on SSA included) [BDR+09]; the visiting order is a heuristic. Lab L2 visits copies in block order; GCC sorts them by estimated execution cost; LLVM's coalescer visits copies in loop-depth order.

5. Complexity¶

$N$ = SSA names, $C$ = copy candidates, $\lvert K \rvert$ = class sizes, $k$ = copies of one edge, $n$, $m$ = blocks and edges.

Technique	Time	Space	Notes
Boissinot et al. (Algorithm 16.7.3 with 16.7.4)	$O(C \cdot (\lvert K_1 \rvert + \lvert K_2 \rvert) \cdot q)$, where $q$ is the cost of a liveness query ($O(1)$ with liveness sets as bit vectors, near-constant with fast liveness checking)	$O(N)$ plus liveness	no interference graph
Lab L2 `coalesce` (pairwise)	$O(C \cdot \lvert K_1 \rvert \lvert K_2 \rvert)$	$O(N + \text{live sets})$	simple, fine for the lab's functions
Sequentialization	$O(k)$ with the `needs` counts kept incrementally; $O(k^2)$ as written in the oracle (it recounts readers)	$O(k)$	moves $= n + c$
Graph-based coalescing (GCC, classical)	$O(N^2)$ bits for the conflict graph, $O(N^2)$ to build it in the worst case	$O(N^2)$	what Boissinot et al. avoid

Justification. Algorithm 16.7.4 visits each member of the two classes once and pushes and pops each once; each visited pair costs one dominance test ($O(1)$ with DFS numbers of the dominator tree, Corollary 15.1.7) and at most one liveness query. Sequentialization: each copy is emitted once, each cycle broken once.

Proposition 16.7.9 (Interference graphs are quadratic, SSA interference tests are not)

A function with $N$ names that are all live at one point has an interference graph with $N(N-1)/2$ edges, while Algorithm 16.7.4 checks any two classes in time linear in their size.

Proof

All pairs of names live at a common point interfere (Definition 16.7.2 with distinct values), hence the clique. Algorithm 16.7.4 does $O(\lvert A \rvert + \lvert B \rvert)$ work per call, independent of how many other names are live.

At scale. Boissinot et al.'s motivation is compile time and memory: their paper evaluates the approach against Sreedhar's Method III with an interference graph [BDR+09]. (We did not re-check its measurements from the course container, so we don't quote numbers here.) On lab L2's corpus, split leaves 7 176 copies on the conventional inputs and coalesce 2 615; on the Braun (transformed) inputs 4 595 and 2 195 (every remaining copy there is a constant or an original copy that could not be merged).

Boissinot et al.¶

Virtualized isolation: do not create Method I's names at all; record which copies are "virtual" and materialize only those coalescing did not remove [BDR+09] — trade-off: less memory, more bookkeeping.
Fast liveness checking [BHG+08]: answer "is $x$ live-in at $B$?" with the dominator tree and a precomputed reduced reachability, no liveness sets — trade-off: fast queries and no invalidation after the program changes, at the cost of a per-CFG precomputation.
Linear-scan coalescing (the "dominance forest" of [BCH+02]) — trade-off: simpler than full value-based checks, somewhat more copies.

Parallel-copy sequentialization¶

Swap instructions (xchg on x86): a $c$-cycle costs $c - 1$ swaps and no temporary — trade-off: swaps are slower than moves on many cores; LLVM's register allocator uses moves.
No spare register: then a cycle needs a swap or a stack slot — trade-off: the register allocator must reserve a scratch register or accept a spill; Cranelift's regalloc2 finds a free register or uses a stack slot when none is available.
Register-allocated parallel copies are the same problem on physical registers: in SSA-based register allocation [Hack07], leaving SSA after allocation turns every phi into a permutation of registers, sequentialized exactly like this (Ch 22).

Coalescing¶

Conservative coalescing (Briggs's and George's tests: merge only if the merged node has fewer than $K$ significant neighbors) — trade-off: preserves colorability for register allocation; leaves copies that aggressive coalescing would remove (Ch 22).
Cost-ordered coalescing (GCC's sorted coalesce list, by execution frequency) — trade-off: removes the hottest copies first; same worst case.
Coalescing on the chordal SSA interference graph (Hack's thesis): SSA interference graphs are chordal, which makes optimal coloring polynomial but optimal coalescing still NP-complete [Hack07].

7. In real compilers¶

Boissinot et al.¶

The ideas are in production at LLVM's machine level: phi elimination isolates every phi (Method I, Lesson 16.6's box), and the register coalescer compares value numbers of live intervals, so a copy of a value never interferes with its source.

LLVM's coalescer: two copies of one value do not interfere

Reproduce (curl 8.x on any OS; LLVM source at tag llvmorg-23.1.2, printed unmodified):

curl -sS https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/llvm/lib/CodeGen/RegisterCoalescer.cpp \
  | sed -n '/Handle the case where VNI and OtherVNI can be proven to be identical/,/return CR_Erase/p'

Output (complete):

  // Handle the case where VNI and OtherVNI can be proven to be identical:
  //
  //   %other = COPY %ext
  //   %this  = COPY %ext <-- Erase this copy
  //
  if (DefMI->isFullCopy() && !CP.isPartial() &&
      valuesIdentical(VNI, V.OtherVNI, Other)) {
    V.Identical = true;
    return CR_Erase;

What to notice: when two live ranges overlap, JoinVals::analyzeValue does not give up: it follows copy chains (followCopyChain) and, if both values come from the same original definition, erases the copy and merges the value numbers. That is Definition 16.7.2's $V(a) = V(b)$ test, applied to machine virtual registers [LLVM-RegCoalescer]. The other resolutions (CR_Keep, CR_Replace, CR_Impossible) cover non-overlapping values, dead lanes and genuine interference.

Parallel-copy sequentialization¶

Go's register allocator: a 3-cycle becomes four moves

Reproduce (Go 1.24.7, linux/amd64):

mkdir rot && cd rot
cat > go.mod <<'EOF'
module swap
go 1.24
EOF
cat > rot.go <<'EOF'
package swap

func Rot(n, x, y, z int) int {
    for i := 0; i < n; i++ {
        x, y, z = y, z, x
    }
    return x - 2*y + 3*z
}
EOF
GOSSAFUNC='Rot+' go build . 2>&1 | sed -n '/pass regalloc end/,/pass loop rotate begin/p' | sed -n '/b2:/,/b5:/p'

Output (complete):

  b2: <- b1 b4
    (-4) v14 = Phi <int> v9 v22 : AX (i[int])
    (-7) v37 = Phi <int> v10 v25 : BX (x[int], z[int])
    (-7) v36 = Phi <int> v11 v23 : CX (x[int], y[int])
    (-7) v35 = Phi <int> v12 v16 : DI (y[int], z[int])
    (+4) v29 = TESTQ <flags> v14 v14
    GT v29 -> b4 b5 (likely)
  b4: <- b2
    (+4) v22 = ADDQconst <int> [-1] v14 : AX (i[int])
    (-7) v20 = Copy <int> v37 : DX
    (-7) v25 = Copy <int> v36 : BX
    (-7) v23 = Copy <int> v35 : CX
    (-7) v16 = Copy <int> v20 : DI
    Plain -> b2
  b5: <- b2

What to notice: after allocation the three phis live in BX, CX, DI and the back edge must perform the parallel copy $(\mathrm{BX}, \mathrm{CX}, \mathrm{DI}) \gets (\mathrm{CX}, \mathrm{DI}, \mathrm{BX})$, a pure 3-cycle. Go's edgeState.shuffle [Go-Regalloc] emits DX ← BX (break the cycle through a free register), BX ← CX, CX ← DI, DI ← DX: 4 moves $= 3 + 1$, the minimum of Theorem 16.7.6, in the same order as Algorithm 16.7.5's trace (2).

Coalescing¶

LLVM's register coalescer removes 10 of 14 copies in the swap loop

Reproduce (clang 23.1.2, opt 23.1.2, llc 23.1.2, target x86_64 Linux):

cat > swap.c <<'EOF'
int fib(int n) {
  int a = 0, b = 1;
  for (int i = 0; i < n; i++) {
    int t = a;
    a = b;
    b = t + b;
  }
  return a;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm swap.c -o swap.ll
opt -passes=mem2reg swap.ll -S -o swap.m2r.ll
llc -mtriple=x86_64-unknown-linux-gnu -O2 swap.m2r.ll -print-before=register-coalescer -print-after=register-coalescer -o /dev/null 2>&1 | grep -v '^$'

Output (complete):

# *** IR Dump Before Register Coalescer (register-coalescer) ***:
# Machine code for function fib: NoPHIs, TracksLiveness, TiedOpsRewritten
Function Live Ins: $edi in %5
0B  bb.0.entry:
      successors: %bb.1(0x80000000); %bb.1(100.00%)
      liveins: $edi
16B   %5:gr32 = COPY $edi
32B   %7:gr32 = MOV32r0 implicit-def dead $eflags
48B   %6:gr32 = MOV32ri 1
64B   %10:gr32 = COPY %6:gr32
80B   %11:gr32 = COPY %7:gr32
96B   %12:gr32 = COPY %7:gr32
112B    bb.1.for.cond:
    ; predecessors: %bb.0, %bb.2
      successors: %bb.2(0x7c000000), %bb.3(0x04000000); %bb.2(96.88%), %bb.3(3.12%)
128B      %2:gr32 = COPY %12:gr32
144B      %1:gr32 = COPY %11:gr32
160B      %0:gr32 = COPY %10:gr32
176B      CMP32rr %2:gr32, %5:gr32, implicit-def $eflags
192B      JCC_1 %bb.3, 13, implicit killed $eflags
208B      JMP_1 %bb.2
224B    bb.2.for.body:
    ; predecessors: %bb.1
      successors: %bb.1(0x80000000); %bb.1(100.00%)
240B      %3:gr32 = COPY %1:gr32
256B      %3:gr32 = nsw ADD32rr %3:gr32(tied-def 0), %0:gr32, implicit-def dead $eflags
272B      %9:gr32 = COPY %2:gr32
288B      %9:gr32 = nsw INC32r %9:gr32(tied-def 0), implicit-def dead $eflags
304B      %10:gr32 = COPY %3:gr32
320B      %11:gr32 = COPY %0:gr32
336B      %12:gr32 = COPY %9:gr32
352B      JMP_1 %bb.1
368B    bb.3.for.end:
    ; predecessors: %bb.1
384B      $eax = COPY %1:gr32
400B      RET 0, killed $eax
# End machine code for function fib.
# *** IR Dump After Register Coalescer (register-coalescer) ***:
# Machine code for function fib: NoPHIs, TracksLiveness, TiedOpsRewritten
Function Live Ins: $edi in %5
0B  bb.0.entry:
      successors: %bb.1(0x80000000); %bb.1(100.00%)
      liveins: $edi
16B   %5:gr32 = COPY $edi
32B   %11:gr32 = MOV32r0 implicit-def dead $eflags
48B   %10:gr32 = MOV32ri 1
96B   %12:gr32 = MOV32r0 implicit-def dead $eflags
112B    bb.1.for.cond:
    ; predecessors: %bb.0, %bb.2
      successors: %bb.2(0x7c000000), %bb.3(0x04000000); %bb.2(96.88%), %bb.3(3.12%)
160B      %0:gr32 = COPY %10:gr32
176B      CMP32rr %12:gr32, %5:gr32, implicit-def $eflags
192B      JCC_1 %bb.3, 13, implicit killed $eflags
208B      JMP_1 %bb.2
224B    bb.2.for.body:
    ; predecessors: %bb.1
      successors: %bb.1(0x80000000); %bb.1(100.00%)
256B      %11:gr32 = nsw ADD32rr %11:gr32(tied-def 0), %0:gr32, implicit-def dead $eflags
288B      %12:gr32 = nsw INC32r %12:gr32(tied-def 0), implicit-def dead $eflags
304B      %10:gr32 = COPY %11:gr32
320B      %11:gr32 = COPY %0:gr32
352B      JMP_1 %bb.1
368B    bb.3.for.end:
    ; predecessors: %bb.1
384B      $eax = COPY %11:gr32
400B      RET 0, killed $eax
# End machine code for function fib.

What to notice: before coalescing there are 14 COPYs: the Method I copies of three phis (six at the ends of the predecessors, three at the header), the two-address copies (%3 = COPY %1 before the tied ADD32rr), and the ABI copies. Afterwards 4 remain: the ABI's $edi/$eax copies and exactly the swap's 2-cycle through %0, %10, %11 ($a$ and $b$ exchange roles every iteration, and $b$'s old value is also needed for the addition). The two copies of the constant 0 (%11 = COPY %7, %12 = COPY %7) were turned into rematerialized MOV32r0s instead of being merged into one register: they are the same value, but both registers are later redefined differently.

GCC: coalescing SSA names into partitions, with conflicts

Reproduce (gcc-14 = GCC 14.2.0, Ubuntu build 14.2.0-4ubuntu2~24.04.1; swap.c from the previous box):

gcc-14 -O2 -fdump-rtl-expand-details=fib.expand -c swap.c -o /dev/null
sed -n '/^Sorted Coalesce list:/,/^;; Generating RTL for gimple basic block 2/p' fib.expand | grep -v '^$'

Output (complete):

Sorted Coalesce list:
(15842, 0) i_7 <-> i_14
(15842, 3) a_3 <-> a_11
(15842, 3) b_6 <-> b_13
(8900, 2) b_2 <-> b_13
(8900, 2) b_2 <-> a_3
(1958, 0) b_2 <-> a_12
(1100, 0) _1(D) <-> a_12
Partition map 
Partition 0 (_1(D) - 1 )
Partition 1 (b_2 - 2 )
Partition 2 (a_3 - 3 )
Partition 3 (n_4(D) - 4 )
Partition 4 (b_6 - 6 )
Partition 5 (i_7 - 7 )
Partition 6 (a_11 - 11 )
Partition 7 (a_12 - 12 )
Partition 8 (b_13 - 13 )
Partition 9 (i_14 - 14 )
Coalesce list: (7)i_7 & (14)i_14 [map: 5, 9] : Success -> 5
Coalesce list: (3)a_3 & (11)a_11 [map: 2, 6] : Success -> 2
Coalesce list: (6)b_6 & (13)b_13 [map: 4, 8] : Success -> 4
Coalesce list: (2)b_2 & (13)b_6 [map: 1, 4] : Fail due to conflict
Coalesce list: (2)b_2 & (3)a_3 [map: 1, 2] : Fail due to conflict
Coalesce list: (2)b_2 & (12)a_12 [map: 1, 7] : Success -> 1
Coalesce list: (1)_1(D) & (12)b_2 [map: 0, 1] : Success -> 1
After Coalescing:
Partition map 
Partition 0 (b_2 - 1 2 12 )
Partition 1 (a_3 - 3 11 )
Partition 2 (n_4(D) - 4 )
Partition 3 (b_6 - 6 13 )
Partition 4 (i_7 - 7 14 )
Inserting a value copy on edge BB2->BB3 : PART.4 = 0
Inserting a value copy on edge BB2->BB3 : PART.3 = 1
Inserting a value copy on edge BB2->BB3 : PART.1 = 0
Inserting a value copy on edge BB2->BB4 : PART.0 = 0
;; Generating RTL for gimple basic block 2

What to notice: GCC's candidates are phi arguments and copies (b_2 = b_13 is the copy through t), sorted by cost (the first number: execution frequency). Each "Success" merges two partitions whose names do not conflict [GCC-Coalesce]; the two failures are the swap: b_2 (the old $b$, destined to become $a$) is live together with both b_6 and a_3. The final partitions are the phi congruence classes that survive (Sreedhar's classes after coalescing); insert_partition_copy_on_edge then places copies only where partitions differ, here only the constants on the entry edges [GCC-OutOfSSA].

Find where LLVM does it. Open llvm/lib/CodeGen/RegisterCoalescer.cpp (LLVM 23.1.2). Question: which member function of JoinVals decides, for one value number, between CR_Keep, CR_Erase, CR_Replace and CR_Impossible? (Quiz llvm-where-joinvals.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Boissinot et al.	always correct; handles TSSA and critical edges; value-aware	linear-time class checks, no interference graph · fastest known	fewest copies among the lesson's methods: lab 2 195 vs 4 595 (split) on Braun outputs	~200 lines with liveness	out-of-SSA passes that avoid interference graphs; LLVM's coalescer uses its value idea
Parallel-copy sequentialization	exact: $n + c$ moves, proven optimal	$O(k)$ per edge	minimal moves; one spare location	~40 lines	every out-of-SSA pass and register allocator (Go, GCC, Cranelift, CompCert)
Coalescing	removes copies between non-interfering names; not optimal (NP-complete)	graph: $O(N^2)$; SSA dominance tests: linear	depends on visiting order and interference notion	~60 lines (union-find + tests)	GCC partitions, LLVM register coalescer, Ch 22 allocators

Choose Boissinot et al.'s translation when you build an out-of-SSA pass today: isolate with parallel copies, coalesce with value-based interference, sequentialize optimally. Choose the sequentialization algorithm whenever you implement parallel copies anywhere, including register permutations at block boundaries. Choose aggressive coalescing during destruction and conservative coalescing during register allocation (Ch 22).

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch16.yaml`)	Drill	Flashcard tag	Exercises
Boissinot et al.	`boissinot-value-interference`, `coalesce-lost-copy`	`./course drill lost-copy-swap --solution` (the correct translation)	`boissinot`	lab L2 R4
Parallel-copy sequentialization	`pcopy-moves`, `pcopy-sequence`, `pcopy-fanout`	`./course drill parallel-copy`	`parallel-copy`	lab L2 R3
Coalescing	`coalesce-lost-copy`, `llvm-where-joinvals`, `ssa-regalloc-preview`	`./course drill parallel-copy --difficulty hard` (after coalescing, the leftover copies)	`coalescing`	lab L2 R4

Saving every cycle in the temporary

A cycle with a copy hanging off it, like $(a, b, c) \gets (b, a, a)$, needs no temporary: do c ← a first, then a ← b, then b ← c. An algorithm that detects "cycle" by looking only at the cycle, and not at loc, emits 4 moves instead of 3; the parallel-copy drill counts it as wrong.

References¶

See the chapter references.

Technique	Time	Space	Notes
Boissinot et al. (Algorithm 16.7.3 with 16.7.4)	\(O(C \cdot (\lvert K_1 \rvert + \lvert K_2 \rvert) \cdot q)\), where \(q\) is the cost of a liveness query (\(O(1)\) with liveness sets as bit vectors, near-constant with fast liveness checking)	\(O(N)\) plus liveness	no interference graph
Lab L2 `coalesce` (pairwise)	\(O(C \cdot \lvert K_1 \rvert \lvert K_2 \rvert)\)	\(O(N + \text{live sets})\)	simple, fine for the lab's functions
Sequentialization	\(O(k)\) with the `needs` counts kept incrementally; \(O(k^2)\) as written in the oracle (it recounts readers)	\(O(k)\)	moves \(= n + c\)
Graph-based coalescing (GCC, classical)	\(O(N^2)\) bits for the conflict graph, \(O(N^2)\) to build it in the worst case	\(O(N^2)\)	what Boissinot et al. avoid

Lesson 16.7 — Leaving SSA well: Boissinot et al., parallel-copy sequentialization, coalescing¶

1. Problem and motivation¶

Boissinot et al.¶

Parallel-copy sequentialization¶

Coalescing¶

2. Definitions and algorithms¶

Boissinot et al.¶

Parallel-copy sequentialization¶

Coalescing¶

3. Worked example¶

Boissinot et al. on the running example¶

Parallel-copy sequentialization¶

4. Invariants and correctness¶

Boissinot et al.¶

Parallel-copy sequentialization¶

Coalescing¶

5. Complexity¶

6. Variants and refinements¶

Boissinot et al.¶

Parallel-copy sequentialization¶

Coalescing¶

7. In real compilers¶

Boissinot et al.¶

Parallel-copy sequentialization¶

Coalescing¶

8. Comparison¶

9. Assessment¶

References¶