Lesson 16.6 — Leaving SSA: naive copies, the lost-copy and swap problems, conventional SSA¶

Techniques: Cytron et al.'s naive copy insertion, Briggs et al.'s analysis of the lost-copy and swap problems with critical-edge splitting and ordered copies, Sreedhar et al.'s conventional SSA and translation Methods I, II and III · Pebble implements: lab L2 methods naive (exactly Cytron's, including its failures) and split (critical-edge splitting with parallel copies) · Prerequisites: Lesson 16.1 (Definition 16.1.2, CSSA/TSSA), Lesson 8.2 (critical edges) · Time: 4–5 hours

Machines have no phi instruction. Before register allocation (or, in LLVM, as its first step), every phi must become ordinary copies. Cytron et al. proposed the obvious translation: for \(x \gets \phi(a_1, \dots, a_k)\), put the copy \(x := a_j\) at the end of predecessor \(P_j\) [CFRWZ91, §7]. It is correct for SSA as freshly built. It is wrong for SSA that optimizations have touched: Briggs et al. found two ways it breaks, the lost-copy and the swap problem [BCHS98]. Sreedhar et al. then explained when dropping the phis is safe (the program must be in conventional SSA) and gave three methods to get there [SJGS99]. This lesson covers these three; Lesson 16.7 covers the modern refinement (Boissinot et al.), optimal copy sequencing and coalescing.

1. Problem and motivation¶

The problem. Given a strict SSA program in phi or block-argument form, produce an equivalent program without phis, using as few copies as possible. The input may be transformed SSA (Definition 16.1.8): copy propagation, value numbering and code motion all create it. Lab L2 takes Chapter 8's block-argument ssa text and produces a tac listing.

Naive copies¶

Cytron et al. replace each phi by copies in its predecessors [CFRWZ91, §7]: correct right after construction, because construction produces conventional SSA (Theorem 16.1.15), and the paper then relies on coalescing in the register allocator to remove the copies. LLVM's machine-level phi elimination still inserts copies at the ends of predecessors, with one crucial change (a fresh register per phi) that §7 shows.

Critical-edge splitting (Briggs et al.)¶

Briggs, Cooper, Harvey and Simpson showed two failures of the naive translation on optimized SSA [BCHS98]. Lost copy: after copy propagation, a phi's result can be live beyond the loop that redefines it; the copy at the end of the latch, which is also the loop's exit block, overwrites it on the exit path as well. Swap: after copy propagation, one phi of a block can use another phi of the same block (Definition 16.1.2's parallel semantics); sequential copies clobber a value another copy still needs. Their fixes: split critical edges so that each edge has its own place for copies (or, where splitting is impossible, keep a temporary), and order the copies of an edge, breaking cycles with a temporary.

Sreedhar's CSSA¶

Sreedhar, Ju, Gillies and Santhanam asked a better question: when can the phis simply be deleted, after giving every name of a phi congruence class one variable? Exactly when no two names of a class interfere, which they call conventional SSA. Their Methods I, II and III insert copies to turn transformed SSA into CSSA, from "copy every operand and result" (Method I, always correct, many copies) to "copy only operands whose live ranges really conflict" (Method III) [SJGS99].

2. Definitions and algorithms¶

Throughout, edges are counted with multiplicity; an edge \(P \to B\) is critical if \(P\) has at least two outgoing edges and \(B\) at least two incoming ones (Definition 8.2.5). In block-argument form the edge \(P \to B(a_1, \dots, a_k)\) with \(B(p_1, \dots, p_k)\) carries the edge copy \((p_1, \dots, p_k) \gets (a_1, \dots, a_k)\).

Naive copies¶

Algorithm 16.6.1 (Naive destruction, Cytron et al.)

Input: strict SSA in block-argument form.
Output: the same program with copies and no parameters.
Precondition: none (this is what makes it dangerous).
Postcondition: correct when neither a lost copy nor a swap exists (Theorem 16.6.6).
Invariant: the copies of edge \(P \to B\) are emitted at the end of \(P\), before its terminator, one per parameter in order, skipping \(p = a\).

function NaiveDestruction(F):
    for each block P, for each outgoing edge P → B(a_1, ..., a_k), in terminator order:
        for ℓ in 1..k:
            if p_ℓ ≠ a_ℓ: append "p_ℓ = a_ℓ" to the end of P (before the terminator)
    drop all parameters and arguments; branches keep their targets

This is lab L2's Method::Naive (R2): for a conditional branch the first target's copies come first. The copies run on both successor paths, because they precede the branch.

Critical-edge splitting (Briggs et al.)¶

Definition 16.6.2 (Lost copy; swap)

Let the edge \(e = P \to B\) carry the non-trivial copy \(p_\ell \gets a_\ell\). (a) \(e\) has a lost copy if \(P\) ends in a two-way branch and either its other edge goes to \(C \neq B\) and \(p_\ell\) is live on that path (\(p_\ell \in \mathrm{LiveIn}(C)\), or \(p_\ell\) is an argument of the other edge, or \(p_\ell\) is the branch condition), or its other edge also goes to \(B\) with a different argument list (the second edge's copies would overwrite the first's). (b) \(e\) has a swap if some copy \(p_{\ell'} \gets a_{\ell'}\) with \(\ell' > \ell\) reads \(a_{\ell'} = p_\ell\): the sequential order overwrites \(p_\ell\) before a later copy of the same edge reads its old value.

Algorithm 16.6.3 (Destruction with edge splitting and ordered copies)

Input: strict SSA in block-argument form.
Output: an equivalent program without parameters.
Precondition: every edge can be split (true in the lab's IR; not for LLVM's indirectbr or exception edges).
Postcondition: equivalent to the input (Theorem 16.6.7); lab L2's Method::Split additionally uses the fewest moves per edge (Lesson 16.7).
Invariant: each edge's copies are placed where they execute only on that edge; within an edge, a copy is emitted only when no pending copy still reads its destination.

function SplitDestruction(F):
    for each edge e = P → B(a_1..a_k) with a non-trivial copy:
        if P has one outgoing edge:        place ← end of P, before its terminator
        else if B has one incoming edge:   place ← start of B
        else:                              place ← a new block N on e (P → N → B); end of N
        emit OrderedCopies([(p_ℓ, a_ℓ)]) at place
    drop all parameters and arguments

function OrderedCopies(C):                            # Briggs et al.'s ordering
    pending ← the non-trivial copies of C
    while pending not empty:
        if some (d, s) ∈ pending has d not read by another pending copy:
            emit "d = s"; remove (d, s) from pending
        else:                                           # only cycles remain
            pick (d, s) ∈ pending; emit "t = d" for a fresh t
            replace d by t as the source of the pending copy that reads d

Placing copies at the start of \(B\) is safe when \(B\) has one predecessor because then the edge is the only way in. Lesson 16.7's Algorithm 16.7.5 improves OrderedCopies to the optimal number of moves.

Sreedhar's CSSA¶

Algorithm 16.6.4 (Sreedhar et al., Method I: isolate every phi)

Input: SSA in phi form.
Output: CSSA (Definition 16.1.8), then a phi-free program.
Precondition: strict SSA.
Postcondition: every phi congruence class is \(\{x_0', x_1', \dots, x_k'\}\) for one phi, and its members do not interfere (Theorem 16.6.8(b)).
Invariant: each new name \(x_j'\) is live only between its copy at the end of \(P_j\) and the end of \(P_j\) (for operands) or between the block start and the copy \(x_0 := x_0'\) (for the result).

function MethodI(F):
    for each phi x_0 = φ(x_1, ..., x_k) at block B with predecessors P_1..P_k:
        for j in 1..k:
            x_j' ← fresh; insert "x_j' = x_j" at the end of P_j (in the edge's parallel copy)
        x_0' ← fresh; insert "x_0 = x_0'" right after the phis of B (a parallel copy)
        rewrite the phi as x_0' = φ(x_1', ..., x_k')
    # now CSSA: give each congruence class one name and delete the phis
    for each class K: rename every member of K to one variable v_K
    delete all phis

Algorithm 16.6.5 (Sreedhar et al., Method III: copy only where live ranges conflict)

Input: SSA in phi form with liveness (\(\mathrm{LiveIn}\), \(\mathrm{LiveOut}\)) and phi congruence classes initialized to singletons.
Output: CSSA with fewer copies than Method I.
Precondition: strict SSA; critical edges need not be split.
Postcondition: no two members of a congruence class interfere [SJGS99].
Invariant: after processing a phi, its resources that were not copied are in one class, and that class is interference-free.

function MethodIII(F):
    for each phi x_0 = φ(x_1, ..., x_k) at block B:
        L_0 ← B; L_j ← P_j for j ≥ 1              # where each resource must be available
        candidates ← {}; unresolved ← {}
        for each pair i < j of resources with interfering classes:
            ii ← (class(x_i) intersects LiveOut(L_j))   # x_i's class is live where x_j is needed
            jj ← (class(x_j) intersects LiveOut(L_i))
            if ii and not jj:   candidates ← candidates ∪ {x_i}      # case 1
            if jj and not ii:   candidates ← candidates ∪ {x_j}      # case 2
            if ii and jj:       candidates ← candidates ∪ {x_i, x_j} # case 3
            if not ii and not jj: unresolved ← unresolved ∪ {(x_i, x_j)}  # case 4
        for each (x_i, x_j) ∈ unresolved with neither in candidates:
            add the one with more unresolved neighbors to candidates  # greedy
        for x ∈ candidates: insert a Method I copy for x only (at the end of its L, or after the phis for x_0)
        merge the classes of the phi's (possibly new) resources
    rename each class to one variable; delete the phis

For the result \(x_0\), "\(\mathrm{LiveOut}(L_0)\)" means \(\mathrm{LiveIn}(B)\) (live on entry to the phi's block, excluding the phi results themselves). Method II is between the two: it uses the interference graph instead of liveness at the phi's blocks, and copies a resource when its class interferes with another resource's class.

3. Worked example¶

Naive copies on the lost-copy and swap programs¶

The oracle's two programs (LOST_COPY_SSA and SWAP_SSA in tools/course/lib/ssa.py, labs/ch16-out-of-ssa/inputs/*.ssa), with the naive translation next to each:

ssa                                     tac    (naive)
entry:                                  entry:
  br H(1)                                 x2 = 1
H(x2):                                    goto H
  x3 = add x2, 1                        H:
  t = lt x3, 5                            x3 = add x2, 1
  cbr t, H(x3), X()                       t = lt x3, 5
X:                                        x2 = x3          <- runs on the exit path too
  ret x2                                  if t goto H
                                          goto X
                                        X:
                                          return x2

Trace of the SSA program: \(x_2 = 1, 2, 3, 4\) with \(x_3 = 2, 3, 4, 5\); at \(x_3 = 5\) the branch exits and ret x2 returns 4. The naive listing returns 5: the copy x2 = x3 executed before the branch. \(H \to H\) is critical (\(H\) has two successors, two predecessors) and \(x_2 \in \mathrm{LiveIn}(X)\): a lost copy (Definition 16.6.2(a)).

ssa                                     tac    (naive)
entry:                                  L:
  br H(1, 2, 0)                           a = b
H(a, b, i):                               b = a            <- reads the new a
  i1 = add i, 1                           i = i1
  t = lt i1, 3                            goto H
  cbr t, L(), X()
L:
  br H(b, a, i1)
X:
  r = sub a, b
  ret r

The SSA program swaps \(a\) and \(b\) twice and returns \(1 - 2 = -1\); the naive listing makes \(a = b = 2\) on the first back edge and returns 0. \(L \to H\) is not critical (\(L\) has one successor), so splitting does not help; the copy b = a reads \(a\) after a = b overwrote it: a swap (Definition 16.6.2(b)).

Critical-edge splitting on the same programs¶

Algorithm 16.6.3 splits \(H \to H\) of the first program into split.0 and leaves the second program's edge in place but orders its copies with a temporary (lab L2's split output, from the oracle):

tac (lost copy, split)                   tac (swap, split: the L block)
H:                                       L:
  x3 = add x2, 1                           i = i1
  t = lt x3, 5                             tmp = a
  if t goto split.0                        a = b
  goto X                                   b = tmp
X:                                         goto H
  return x2
split.0:
  x2 = x3
  goto H

Both return the SSA values, 4 and \(-1\). The copy counts (lab L2's measure: all copy instructions in the output) are 2 and 7: x2 = 1 plus the split copy; and three entry copies plus i = i1 plus the three moves of the cycle.

program	naive copies	naive value	split copies	split value	Method I copies
lost copy	2	5 (wrong)	2	4	3
swap	6	0 (wrong)	7	−1	9

Sreedhar's CSSA on the lost-copy program¶

Method I introduces \(x_2'\) for the result and \(x_2^{(1)}, x_2^{(2)}\) for the operands (block-argument view: every edge copies into the fresh names, and the block begins with \(x_2 := x_2'\)):

entry:  x2' = 1                 ; goto H
H:      x2 = x2'                ; x3 = add x2, 1 ; t = lt x3, 5
        x2' = x3                ; if t goto H ; goto X
X:      return x2

(The class \(\{x_2', x_2^{(1)}, x_2^{(2)}\}\) has been given the single name x2'.) The copy x2' = x3 still runs on the exit path, but it now writes \(x_2'\), which is dead there: correct without splitting, at the price of one more copy (3 instead of 2).

Method III on the same phi \(x_2 = \phi(1, x_3)\): the resources are \(x_2\) (the result, \(L_0 = H\)) and \(x_3\) (the operand from \(H\), \(L_2 = H\)); the constant operand always needs its copy. The classes of \(x_2\) and \(x_3\) interfere: \(x_2\) is live at \(x_3\)'s definition (it is returned later, in X). Is \(x_2\)'s class live out of \(L_2 = H\)? Yes, into X. Is \(x_3\)'s class live on entry to \(L_0 = H\)? No, \(x_3\) is defined in H. Case 1: copy the result \(x_2\) only. The phi becomes \(x_2' = \phi(1, x_3)\) with the copy \(x_2 := x_2'\) at H's start, and the class \(\{x_2', x_3\}\) is renamed to one variable v:

entry:  v = 1                   ; goto H
H:      x2 = v                  ; v = add x2, 1 ; t = lt v, 5 ; if t goto H ; goto X
X:      return x2

Two copies instead of Method I's three: \(x_3\) lives directly in the phi's variable, so the back edge needs no copy at all, and the exit still reads x2, which the loop does not overwrite after the test. It returns 4.

Try it

./course drill lost-copy-swap --seed 3 --difficulty medium --solution generates a loop, runs it before and after naive destruction, and names the lost-copy and swap edges; --difficulty hard adds exit arguments.

4. Invariants and correctness¶

Naive copies¶

Theorem 16.6.6 (When naive destruction is correct)

If no edge has a lost copy or a swap (Definition 16.6.2), Algorithm 16.6.1 produces an equivalent program. In particular it is correct on conventional SSA whose phi operands are all names (not constants).

Proof

Consider an execution that leaves \(P\) along \(e = P \to B\). At the end of \(P\) the naive program executes the copies of every outgoing edge of \(P\) (for a conditional branch, both edges' copies), then branches. (i) The copies of \(e\) itself compute the parallel copy. No swap means no copy of \(e\) reads a name an earlier copy of \(e\) wrote, so every copy reads the value its source had at the end of \(P\) (Proposition 16.1.3). (ii) The copies of the other edge are harmless. A copy \(q \gets c\) of the other edge \(P \to C\) writes \(q\), a parameter of \(C \neq B\). No lost copy on the other edge means \(q\) is not live on the path through \(e\): not in \(\mathrm{LiveIn}(B)\), not an argument of \(e\), not the condition. So its new value is never read before \(q\) is redefined (by \(C\)'s entry, the only definition of \(q\)). If both edges go to the same block \(B\) with different arguments, the second edge's copies overwrite the first's: that is a lost copy by definition (the parameters are live on the first edge as its own arguments' targets), excluded. (iii) The copies do not disturb the condition: the condition is not overwritten (no lost copy). Hence after the branch every parameter of \(B\) holds the value of Definition 16.1.2 and every other live name is unchanged. CSSA: assume the program is conventional and every phi operand is a name (a constant operand is first copied into a fresh name at the end of its predecessor, as Sreedhar et al. assume; otherwise a constant copied into a phi result live on the other path is a lost copy that CSSA does not prevent). In strict SSA, two names that are live at the same point interfere (Lemma 16.7.1). No lost copy: \(a_\ell\) is live at the end of \(P\) (the edge uses it), and \(p_\ell\) live on the other path or as the condition is live at the end of \(P\) too; they are in one class: contradiction. The multi-edge case is the same with the other edge's arguments. No harmful swap: \(a_{\ell'} = p_\ell\) makes \(p_\ell\) and \(p_{\ell'}\) members of one class, both defined at \(B\)'s entry. \(p_\ell\) is used at the end of \(P\) and its definition dominates that use, so it is live from \(B\)'s entry to the end of \(P\); if \(p_{\ell'}\) has any use, it is live just after the same entry, and the two interfere: contradiction. If \(p_{\ell'}\) has no use, the wrong value the sequential copy gives it is never observed.

The oracle test Destruction.test_random checks the first sentence's contrapositive on 480 SSA functions: whenever the naive translation returns a different value, a lost-copy or swap edge exists.

Critical-edge splitting (Briggs et al.)¶

Theorem 16.6.7 (Correctness of Algorithm 16.6.3)

Algorithm 16.6.3 produces an equivalent program for every strict SSA input.

Proof

Placement: the copies of \(e = P \to B\) execute exactly when \(e\) is taken. If \(P\) has one outgoing edge, the end of \(P\) is followed only by \(e\). If \(B\) has one incoming edge, the start of \(B\) is reached only through \(e\). Otherwise the new block \(N\) lies only on \(e\). So copies of different edges never execute together, and no copy runs on a path where its destination is live (the lost-copy argument of Theorem 16.6.6(ii) is void). A copy placed at the start of \(B\) runs after \(P\)'s terminator has read its condition, so the condition is safe too. Ordering: OrderedCopies emits \(d := s\) only when no pending copy reads \(d\), so every pending copy still finds its source's value (in the source or, after a cycle break, in \(t\)); when every pending destination is read by another pending copy, each destination has in-degree one in the copy graph and every node is read, so the pending copies form disjoint cycles, and saving one node of a cycle in \(t\) frees it. By induction on the number of pending copies, the emitted sequence implements the parallel copy.

Sreedhar's CSSA¶

Theorem 16.6.8 (CSSA can be left by renaming; Method I produces CSSA)

(a) If the program is in CSSA, renaming every member of each phi congruence class to one variable and deleting the phis gives an equivalent program. (b) After Method I's copies, the program is in CSSA.

Proof sketch (full proof: [SJGS99]; [SSAB, Ch. 21])

(a) Take a class \(K\) renamed to \(v_K\). On the edge \(P_j \to B\) the phi \(x_0 = \phi(\dots, x_j, \dots)\) wants \(x_0 := x_j\); both are \(v_K\) now, so the deleted phi's effect is "keep \(v_K\)", which is right provided \(v_K\) holds \(x_j\)'s value at the end of \(P_j\): \(x_j\) is live there (it is used by the phi), and no other member of \(K\) is live at the same time (no interference), so no other member's definition has overwritten \(v_K\) since \(x_j\)'s definition. The same argument shows that every use of a member reads that member's value. Parallel semantics is not an issue: two phis of \(B\) belong to different classes (else two members, both defined at \(B\)'s entry and used, would interfere). (b) After Method I, \(x_j'\) is live only from its copy at the end of \(P_j\) to the end of \(P_j\), \(x_0'\) only from \(B\)'s entry to the copy \(x_0 := x_0'\); the class \(\{x_0', x_1', \dots, x_k'\}\) has members whose live ranges are in different blocks or disjoint parts of one block, so none interfere. The copies into \(x_j'\) at the end of \(P_j\) must form a parallel copy per edge, and \(P_j\)'s other successor never reads \(x_j'\) [BDR+09]. Two phis of \(B\) never share a class after Method I (each has its own fresh names).

Theorem 16.6.9 (Method III produces CSSA)

Algorithm 16.6.5 produces a program in CSSA with a subset of Method I's copies.

Proof sketch (full proof: [SJGS99])

The copies are a subset by construction (a Method I copy for each candidate only). Two resources of a phi whose classes interfere cannot both stay uncopied: in cases 1–3 at least one of them is copied, and case 4 pairs are resolved greedily until each has a copied member. A copied resource \(x'\) is live only in its own block's end (or start), which Sreedhar et al. show cannot intersect the merged class, because the liveness tests of cases 1–3 detect every way two live ranges can overlap at the phi's blocks. Merging the uncopied resources' classes therefore creates no interference.

When they break. Algorithm 16.6.3 needs edges that can be split; LLVM cannot split the edge into an exception landing pad or out of indirectbr or callbr, and must fall back to Method I-style isolation there. Method I needs the copies at the end of \(P_j\) to form a parallel copy, and to be placed after the definitions of all operands used there; for a terminator that defines a value (LLVM invoke), the copy cannot go after it and needs a split.

5. Complexity¶

\(n\) = blocks, \(E\) = edges, \(\Phi\) = phis, \(A\) = phi operands (sum of arities), \(c_e\) = copies of edge \(e\).

Technique	Copies inserted	Time	Notes
Naive copies	\(A\) minus trivial ones	\(O(A)\)	wrong on TSSA
Critical-edge splitting	\(\sum_e (c_e + \text{cycles}_e)\), plus split blocks	\(O(A + E)\) plus the ordering: \(O(c_e^2)\) per edge for the simple scan, \(O(c_e)\) with Algorithm 16.7.5	new blocks cost branches at run time
Sreedhar Method I	\(A + \Phi\)	\(O(A)\)	all correct; coalescing must remove most
Sreedhar Method III	at most Method I's	\(O(\Phi \cdot r^2)\) for \(r\) resources per phi, plus liveness and interference tests	closest to optimal of the three

Justification. Naive and Method I touch each phi operand once; Method I adds one copy per phi result. Splitting adds at most one block per critical edge. Method III examines all pairs of the \(r = k + 1\) resources of each phi.

Proposition 16.6.10 (Method I can be much worse than necessary)

A function with a loop header of \(\Phi\) phis and \(k\) predecessors, in CSSA (no copies needed at all), receives \(\Phi (k + 1)\) copies from Method I.

Proof

Freshly constructed SSA is CSSA (Theorem 16.1.15), so renaming classes needs no copy (Theorem 16.6.8(a)); Method I inserts \(k\) operand copies and one result copy per phi regardless. On lab L2's corpus, Method I would insert 9 110 copies on the pruned (CSSA) inputs where coalescing leaves 2 615, all of them for constants and original copy instructions (tests/ch16 goldens).

At scale. Sreedhar et al. compare the three methods experimentally and recommend Method III followed by coalescing [SJGS99]; Boissinot et al. later showed that Method I followed by aggressive, value-aware coalescing does as well with a simpler, faster implementation (Lesson 16.7) [BDR+09]. On lab L2's corpus the naive translation is wrong on 158 of 564 functions, all transformed SSA: 155 of the 256 parallel-copy stress cases, one Braun output and the two Briggs programs; it is right on all 153 conventional (pruned Cytron) inputs.

Naive copies¶

Fresh register per phi (LLVM PHIElimination) — trade-off: turns naive placement into Method I at the machine level; correct, but leaves twice the copies for the coalescer.
Copies on edges committed later (GCC's insert_partition_copy_on_edge + commit_edge_insertions) — trade-off: the edge-insertion machinery splits edges only when copies remain after coalescing.

Critical-edge splitting (Briggs et al.)¶

Split all critical edges before any SSA pass (common in older compilers; LLVM's -phi-elim-split-all-critical-edges flag) — trade-off: simple, but extra jumps in the final code.
Liveness-based placement without splitting: Briggs et al. also give a version that checks whether the destination is live out of the predecessor and uses a temporary instead of splitting [BCHS98] — trade-off: no new blocks, more copies and a liveness query per copy.
Split only when it helps (LLVM SplitPHIEdges: only if the incoming value is live past the phi on another path, and never for a loop's own back edge) — trade-off: fewer blocks; §7 shows it.

Sreedhar's CSSA¶

Method II (interference-graph based) — trade-off: simpler than Method III, more copies.
Virtualized Method I (Boissinot et al.): do not insert the copies, but reason about them as if present, inserting only those coalescing cannot remove — trade-off: fewer temporary variables, the basis of Lesson 16.7 [BDR+09].
Phi isolation in upsilon/phi form is Method I by construction (Theorem 16.5.8).

7. In real compilers¶

Naive copies¶

LLVM places the phi copy at the end of the latch, into a fresh register

Reproduce (llc 23.1.2, target x86_64; any host):

cat > lost.ll <<'EOF'
define i32 @lost(i32 %n) {
entry:
  br label %loop

loop:
  %x2 = phi i32 [ 1, %entry ], [ %x3, %loop ]
  %x3 = add i32 %x2, 1
  %c = icmp slt i32 %x3, %n
  br i1 %c, label %loop, label %exit

exit:
  ret i32 %x2
}
EOF
llc -mtriple=x86_64-unknown-linux-gnu -O0 lost.ll -print-after=phi-node-elimination -o /dev/null 2>&1 | grep -v '^$'

Output (complete):

# *** IR Dump After Eliminate PHI nodes for register allocation (phi-node-elimination) ***:
# Machine code for function lost: NoPHIs, TracksLiveness
Function Live Ins: $edi in %2
bb.0.entry:
  successors: %bb.1
  liveins: $edi
  %2:gr32 = COPY $edi
  %3:gr32 = COPY killed %2:gr32
  %4:gr32 = MOV32ri 1
  %6:gr32 = COPY %4:gr32
  JMP_1 %bb.1
bb.1.loop:
; predecessors: %bb.0, %bb.1
  successors: %bb.1, %bb.2
  %0:gr32 = COPY %6:gr32
  %5:gr32 = ADD32ri %0:gr32(tied-def 0), 1, implicit-def $eflags
  CMP32rr %5:gr32, %3:gr32, implicit-def $eflags
  %6:gr32 = COPY %5:gr32
  JCC_1 %bb.1, 12, implicit $eflags
bb.2.exit:
; predecessors: %bb.1
  $eax = COPY %0:gr32
  RET64 implicit $eax
# End machine code for function lost.

What to notice: this is the lost-copy program. The phi %x2 became %0, and its copy for the back edge, %6 = COPY %5, sits at the end of the latch bb.1, before the conditional jump, exactly where Algorithm 16.6.1 puts it; it runs on the exit path too. It is harmless only because it writes %6, a fresh register, and the loop header reads %0 = COPY %6 at its start: the exit reads %0, which the late copy did not touch. That is Method I's isolation (\(x_0'\) = %6), not the naive translation %0 = COPY %5, which would return the wrong value ([LLVM-PHIElim], PHIEliminationImpl::LowerPHINode).

Critical-edge splitting (Briggs et al.)¶

LLVM splits a critical edge when the incoming value is live on the other path

Reproduce (llc 23.1.2, target x86_64):

cat > crit.ll <<'EOF'
define i32 @crit(i32 %x, i1 %c, i1 %d) {
entry:
  %y = add i32 %x, 1
  br i1 %c, label %join, label %other

other:
  %z = mul i32 %x, 3
  br i1 %d, label %join, label %exit

join:
  %p = phi i32 [ %y, %entry ], [ %x, %other ]
  %r = add i32 %p, 5
  ret i32 %r

exit:
  %q = add i32 %x, %z
  ret i32 %q
}
EOF
llc -mtriple=x86_64-unknown-linux-gnu -O2 crit.ll -print-after=phi-node-elimination -o /dev/null 2>&1 | grep -v '^$'

Output (complete):

# *** IR Dump After Eliminate PHI nodes for register allocation (phi-node-elimination) ***:
# Machine code for function crit: NoPHIs, TracksLiveness
Function Live Ins: $edi in %3, $esi in %4, $edx in %5
bb.0.entry:
  successors: %bb.1(0x40000000), %bb.2(0x40000000); %bb.1(50.00%), %bb.2(50.00%)
  liveins: $edi, $esi, $edx
  %5:gr32 = COPY killed $edx
  %4:gr32 = COPY killed $esi
  %3:gr32 = COPY killed $edi
  %7:gr8 = COPY killed %4.sub_8bit:gr32
  TEST8ri killed %7:gr8, 1, implicit-def $eflags
  JCC_1 %bb.2, 4, implicit killed $eflags
bb.1:
; predecessors: %bb.0
  successors: %bb.3(0x80000000); %bb.3(100.00%)
  %0:gr32 = INC32r killed %3:gr32(tied-def 0), implicit-def dead $eflags
  %12:gr32 = COPY killed %0:gr32
  JMP_1 %bb.3
bb.2.other:
; predecessors: %bb.0
  successors: %bb.5(0x40000000), %bb.4(0x40000000); %bb.5(50.00%), %bb.4(50.00%)
  %6:gr8 = COPY killed %5.sub_8bit:gr32
  TEST8ri killed %6:gr8, 1, implicit-def $eflags
  JCC_1 %bb.4, 4, implicit killed $eflags
bb.5:
; predecessors: %bb.2
  successors: %bb.3(0x80000000); %bb.3(100.00%)
  %12:gr32 = COPY killed %3:gr32
bb.3.join:
; predecessors: %bb.1, %bb.5
  %2:gr32 = COPY killed %12:gr32
  %11:gr32 = ADD32ri killed %2:gr32(tied-def 0), 5, implicit-def dead $eflags
  $eax = COPY killed %11:gr32
  RET 0, killed $eax
bb.4.exit:
; predecessors: %bb.2
  %8:gr64_nosp = INSERT_SUBREG undef %9:gr64(tied-def 0), %3:gr32, %subreg.sub_32bit
  %1:gr32 = LEA64_32r killed %8:gr64_nosp, 2, %8:gr64_nosp, 0, $noreg
  %10:gr32 = ADD32rr killed %3:gr32(tied-def 0), killed %1:gr32, implicit-def dead $eflags
  $eax = COPY killed %10:gr32
  RET 0, killed $eax
# End machine code for function crit.

What to notice: other → join is critical (other also branches to exit), and the incoming value %x (%3) is live on the exit path. SplitPHIEdges created bb.5 on the edge and put the copy %12 = COPY killed %3 there, where it runs only on that edge (Algorithm 16.6.3's third case); with the copy in other instead, %3 could not be killed there and coalescing would be harder. The entry → join edge was already split into bb.1 by the earlier block placement of the conditional branch.

Sreedhar's CSSA¶

LLVM's PHIElimination is Method I: the swap loop gets six copies

Reproduce (llc 23.1.2, target x86_64):

cat > swapfn.ll <<'EOF'
define i32 @swap(i32 %n) {
entry:
  br label %loop

loop:
  %a = phi i32 [ 1, %entry ], [ %b, %loop ]
  %b = phi i32 [ 2, %entry ], [ %a, %loop ]
  %i = phi i32 [ 0, %entry ], [ %i1, %loop ]
  %i1 = add i32 %i, 1
  %c = icmp slt i32 %i1, %n
  br i1 %c, label %loop, label %exit

exit:
  %r = sub i32 %a, %b
  ret i32 %r
}
EOF
llc -mtriple=x86_64-unknown-linux-gnu -O0 swapfn.ll -print-after=phi-node-elimination -o /dev/null 2>&1 | grep -v '^$'

Output (complete):

# *** IR Dump After Eliminate PHI nodes for register allocation (phi-node-elimination) ***:
# Machine code for function swap: NoPHIs, TracksLiveness
Function Live Ins: $edi in %4
bb.0.entry:
  successors: %bb.1
  liveins: $edi
  %4:gr32 = COPY $edi
  %5:gr32 = COPY killed %4:gr32
  %6:gr32 = MOV32ri 1
  %7:gr32 = MOV32ri 2
  %8:gr32 = MOV32r0 implicit-def $eflags
  %12:gr32 = COPY %6:gr32
  %13:gr32 = COPY %7:gr32
  %14:gr32 = COPY %8:gr32
  JMP_1 %bb.1
bb.1.loop:
; predecessors: %bb.0, %bb.1
  successors: %bb.1, %bb.2
  %2:gr32 = COPY %14:gr32
  %1:gr32 = COPY %13:gr32
  %0:gr32 = COPY %12:gr32
  %9:gr32 = ADD32ri %2:gr32(tied-def 0), 1, implicit-def $eflags
  CMP32rr %9:gr32, %5:gr32, implicit-def $eflags
  %12:gr32 = COPY %1:gr32
  %13:gr32 = COPY %0:gr32
  %14:gr32 = COPY %9:gr32
  JCC_1 %bb.1, 12, implicit $eflags
bb.2.exit:
; predecessors: %bb.1
  %11:gr32 = SUB32rr %0:gr32(tied-def 0), %1:gr32, implicit-def $eflags
  $eax = COPY %11:gr32
  RET64 implicit $eax
# End machine code for function swap.

What to notice: each phi \(x_0 = \phi(\dots)\) got a fresh register \(x_0'\) (%12, %13, %14 for %a, %b, %i), copies into it at the end of both predecessors, and one copy out of it at the start of the loop (%0 = COPY %12 and so on): Algorithm 16.6.4 exactly, \(\Phi (k + 1) = 3 \times 3 = 9\) copies. The back-edge copies %12 = COPY %1 and %13 = COPY %0 swap \(a\) and \(b\) correctly although they are sequential, because they write the isolated registers, not %0 and %1. The register coalescer (Lesson 16.7) removes most of them.

Find where LLVM does it. Open llvm/lib/CodeGen/PHIElimination.cpp (LLVM 23.1.2). Question: what is the name of the command-line option that forces splitting of every critical edge during phi elimination? (Quiz llvm-where-split-all.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Naive copies	correct only without lost copies and swaps (CSSA with named operands)	\(O(A)\) · trivial	wrong answers on TSSA: 158 of the 564 lab L2 inputs (0 of the 153 conventional ones)	~10 lines	Cytron's paper; never alone in production
Critical-edge splitting (Briggs et al.)	always correct	\(O(A + E)\) · adds blocks and jumps	copies = operands + cycles; extra blocks	~60 lines + an edge splitter	GCC edge insertion, LLVM `SplitPHIEdges`, lab `split`
Sreedhar's CSSA (Methods I–III)	always correct; Method III close to minimal	I: \(O(A)\); III: pairwise tests per phi	I: \(A + \Phi\) copies before coalescing; III: far fewer	I: ~20 lines; III: ~150 with liveness	LLVM PHIElimination (Method I at machine level), research compilers

Choose naive copies when you know the SSA is conventional (straight out of construction) and want the simplest code. Choose edge splitting when you want correctness on transformed SSA with a small, local algorithm and can afford extra blocks. Choose a Sreedhar method when you want correctness without new blocks and plan to coalesce; Method I is what LLVM and upsilon/phi form do implicitly.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch16.yaml`)	Drill	Flashcard tag	Exercises
Naive copies	`naive-lost-copy-value`, `naive-cssa-correct`	`./course drill lost-copy-swap`	`naive-copies`	lab L2 R2
Critical-edge splitting (Briggs et al.)	`briggs-which-problem`, `llvm-where-split-all`	`./course drill lost-copy-swap --difficulty hard`	`briggs`	lab L2 R3
Sreedhar's CSSA	`sreedhar-method1-count`, `sreedhar-method3-case`	no dedicated drill: Method III's case analysis is practiced by the quiz question `sreedhar-method3-case` and lab L2's `coalesce` method (which starts from the same isolation idea)	`sreedhar-cssa`	lab L2 R4

Splitting critical edges does not fix the swap problem

The swap program's back edge \(L \to H\) is not critical (\(L\) has one successor), yet the naive copies are wrong. Splitting fixes lost copies; only ordering the copies of one edge (with a temporary for cycles) fixes swaps. You need both.

References¶

See the chapter references.

Lesson 16.6 — Leaving SSA: naive copies, the lost-copy and swap problems, conventional SSA¶

1. Problem and motivation¶

Naive copies¶

Critical-edge splitting (Briggs et al.)¶

Sreedhar's CSSA¶

2. Definitions and algorithms¶

Naive copies¶

Critical-edge splitting (Briggs et al.)¶

Sreedhar's CSSA¶

3. Worked example¶

Naive copies on the lost-copy and swap programs¶

Critical-edge splitting on the same programs¶

Sreedhar's CSSA on the lost-copy program¶

4. Invariants and correctness¶

Naive copies¶

Critical-edge splitting (Briggs et al.)¶

Sreedhar's CSSA¶

5. Complexity¶

6. Variants and refinements¶

Naive copies¶

Critical-edge splitting (Briggs et al.)¶

Sreedhar's CSSA¶

7. In real compilers¶

Naive copies¶

Critical-edge splitting (Briggs et al.)¶

Sreedhar's CSSA¶

8. Comparison¶

9. Assessment¶

References¶