Lesson 16.3 — Construction without frontiers: Braun et al. and Aycock–Horspool

Techniques: Braun et al.'s on-the-fly construction (local and global value numbering, sealed blocks, trivial-phi removal, SCC-based removal of redundant phi sets), Aycock–Horspool's "build everything, then minimize" · Pebble implements: both in lab L1 (Braun required, Aycock–Horspool optional ★), compared with Cytron's three flavors by phi count and time · Prerequisites: Lesson 16.1, Lesson 16.2, Tarjan's SCC algorithm (Lesson 15.5) · Time: 5–6 hours

Cytron's construction needs the whole CFG, its dominator tree and its frontiers before the first phi exists. A front end that emits SSA while parsing has none of these: when it compiles the body of a while loop, it does not yet know the loop's back edge. Braun, Buchwald, Hack, Leißa, Mallon and Zwinkau showed that SSA can be built during IR construction with nothing but a map from (block, variable) to value and a flag per block that says "all predecessors are known" [BBH+13]. Cranelift, Go (for small functions) and the libFirm compiler use it. Aycock and Horspool had earlier shown the other extreme: put a phi for every variable in every block, then delete the useless ones by rewrite rules until none applies [AH00].

1. Problem and motivation

The problem. Build SSA (with phis or block arguments) for a function whose CFG is revealed incrementally, block by block, as a front end or a translator (Wasm to Cranelift, AST to IR) emits it, without dominance frontiers and ideally without a separate liveness pass; produce few phis. Pebble's lab L1 applies both algorithms to a TAC listing processed in listing order, which simulates a front end emitting blocks one by one.

Braun et al.

The key idea is lazy lookup: when an instruction reads variable \(v\) in block \(B\), ask \(B\) for \(v\)'s current value. If \(B\) defined \(v\), answer locally; otherwise ask the predecessors, and if there are several, create a phi and fill its operands by asking each predecessor. Two refinements make this work: a block whose predecessors are not all known yet (a loop header before its latch is emitted) gets an incomplete phi that is completed when the block is sealed; and a phi whose operands turn out to be all the same value (or itself) is trivial and is removed immediately, rewiring its users [BBH+13]. Copies are folded: x = y just records that \(x\)'s current value is \(y\)'s value.

Aycock–Horspool

Aycock and Horspool target the same users (front ends of functional-language and scripting compilers) with an even simpler idea: place a phi for every variable at every join ("maximal" or "crude" SSA), rename, and then apply two rules until nothing changes: a phi \(x \gets \phi(x, \dots, x)\) is deleted, and a phi \(x \gets \phi(x_1, \dots, x_k)\) whose operands are all \(x\) or one other value \(y\) is replaced by \(y\) [AH00]. For reducible CFGs the result is minimal in Cytron's sense. LLVM's InstSimplify applies exactly these rules to phis [LLVM-InstSimplify].

2. Definitions and algorithms

Blocks are filled when all their instructions have been processed, and sealed when all their predecessors are known (in the lab: when all predecessors have been filled, or, for the entry, at once). Values are instruction results, integer constants (two constants are the same value iff they are equal) and phis. \(\mathrm{cur}[B][v]\) is the value of \(v\) at the end of the part of \(B\) processed so far.

Braun et al.

Definition 16.3.1 (Trivial phi; redundant phi set)

A phi \(p = \phi(o_1, \dots, o_k)\) is trivial if the set \(\{o_1, \dots, o_k\} \setminus \{p\}\) has at most one element (after following replacements): it merges only itself and one value \(w\), and can be replaced by \(w\) (by an undefined value if the set is empty, which happens only in unreachable code). A set \(P\) of phis is redundant if every operand of every phi of \(P\) is in \(P\) or equals one value \(w \notin P\) [BBH+13].

Algorithm 16.3.2 (Braun et al.: on-the-fly construction)

• Input: blocks emitted in some order (in the lab: listing order), each with its instructions; predecessor lists that grow as edges are emitted.
• Output: SSA values for every read, and phis with complete operand lists.
• Precondition: every block is eventually sealed; an operand list is filled only after the block is sealed (so its predecessor list is final).
• Postcondition: every read is replaced by a value whose definition reaches it on all paths (Theorem 16.3.6).
• Invariant: for every sealed block \(B\) and every \(v\), incomplete[B] is empty; for every unsealed \(B\), each read of \(v\) that reached \(B\) got the incomplete phi incomplete[B][v], which is also cur[B][v].

function writeVariable(v, B, value):
    cur[B][v] ← value

function readVariable(v, B):
    if v ∈ cur[B]: return cur[B][v]                  # local value numbering
    return readVariableRecursive(v, B)               # global value numbering

function readVariableRecursive(v, B):
    if B is not sealed:
        val ← new empty phi in B;  incomplete[B][v] ← val
    else if preds(B) is empty:
        val ← the initial value of v (0 in Tiny/TAC)
    else if preds(B) = [P]:
        val ← readVariable(v, P)                     # no phi needed
    else:
        val ← new empty phi in B
        writeVariable(v, B, val)                     # breaks cycles through loops
        val ← addPhiOperands(v, val)
    writeVariable(v, B, val)
    return val

function addPhiOperands(v, phi):
    for P in preds(block(phi)):
        append readVariable(v, P) to operands(phi)
    return tryRemoveTrivialPhi(phi)

function sealBlock(B):
    for (v, phi) in incomplete[B]: addPhiOperands(v, phi)
    mark B sealed

function processBlock(B):                          # the lab's driver, blocks in order
    if B is not sealed and every predecessor of B is filled: sealBlock(B)
    for instruction "x = a" (copy): writeVariable(x, B, value(a))     # copy folding
    for instruction "x = op a, b": writeVariable(x, B, new value op(value(a), value(b)))
    mark B filled
    for every unsealed block S whose predecessors are all filled: sealBlock(S)

value(a) is a itself for a constant and readVariable(a, B) for a variable.

Algorithm 16.3.3 (tryRemoveTrivialPhi)

• Input: a phi \(p\) with its operands filled.
• Output: \(p\), or the value that replaces it.
• Precondition: \(p\)'s block is sealed.
• Postcondition: if \(p\) was trivial (Definition 16.3.1), every use of \(p\) now uses its replacement \(w\), and every phi user of \(p\) that became trivial was removed too.
• Invariant: replacements form chains that end in a non-removed value; reading a value always follows the chain (resolve).

function tryRemoveTrivialPhi(p):
    same ← none
    for o in operands(p):
        o ← resolve(o)
        if o = same or o = p: continue               # unique value or self reference
        if same ≠ none: return p                     # merges two values: not trivial
        same ← o
    if same = none: same ← undefined                 # unreachable or only self references
    users ← the phis that use p, except p
    replace every use of p by same                   # in the lab: record repl(p) ← same
    for q in users: tryRemoveTrivialPhi(q)           # they may have become trivial
    return same

Algorithm 16.3.4 (Removing redundant phi SCCs)

• Input: the phis left after construction.
• Output: the same program without redundant phi sets.
• Precondition: all blocks sealed; Algorithm 16.3.3 applied.
• Postcondition: no redundant set (Definition 16.3.1) remains (Theorem 16.3.8).
• Invariant: SCCs are processed operands-first (Tarjan's order), so every phi outside the current SCC that it uses is already final.

function removeRedundantPhis(phis):
    for C in SCCs of the graph phi → phi-operand restricted to phis, operands first:
        if |C| = 1 and C's phi is trivial: replace it (as in Algorithm 16.3.3); continue
        outer ← { resolve(o) | p ∈ C, o ∈ operands(p), resolve(o) ∉ C }
        inner ← { p ∈ C | every operand of p is in C }
        if |outer| = 1:
            replace every phi of C by the single element of outer
        else if |outer| > 1:
            removeRedundantPhis(inner)               # a redundant subset can hide inside

[BBH+13] gives the same recursion. It is needed only for irreducible CFGs (Theorem 16.3.7).

Aycock–Horspool

Algorithm 16.3.5 (Aycock–Horspool: maximal SSA, then minimize)

• Input: a variable program.
• Output: an SSA program.
• Precondition: none beyond a CFG with an entry.
• Postcondition: no phi of the result satisfies rule R1 or R2; on reducible CFGs its phis are a subset of minimal SSA's (Theorem 16.3.9).
• Invariant: every deletion replaces a phi by a value that equals it in every execution, so the program's meaning never changes.

function AycockHorspool(G):
    for every join block B (at least two predecessors), for every v in V:
        insert a phi for v at the top of B
    Rename(G, D)                                     # Algorithm 16.2.3, with copy folding
    repeat
        changed ← false
        for every phi p:
            others ← { resolve(o) | o ∈ operands(p) } \\ {p}
            if |others| = 0:  replace p by undefined; changed ← true     # R1: p = φ(p, ..., p)
            if |others| = 1:  replace p by the element; changed ← true   # R2: p = φ(p|w, ..., p|w)
    until not changed

3. Worked example

Braun et al. on the running example

Blocks are processed in listing order A, B, C, D, E, F, G, H, I. A block is sealed when all its predecessors are filled. The oracle trace (braun_ssa(..., trace=...) in tools/course/lib/ssa.py), one row per event:

step	event	block	var	phi	detail
1	seal	A	—	—	entry: no predecessors
2	incomplete phi	B	x	φ0	B not sealed (pred H not filled); read by y = add x, i
3	incomplete phi	B	i	φ1	same instruction, second operand
4	seal	C	—	—	pred B filled
5	seal	D	—	—	pred C filled
6	incomplete phi	E	y	φ2	E's preds B, D, G: G not filled yet
7	seal	F	—	—	pred E filled
8	incomplete phi	E	x	φ3	F reads x: F → E, E unsealed
9	seal	G	—	—	pred F filled
10	operands	E	y	φ2	E sealed after G: φ2 = φ(y from B, y from D, y from G) = φ(y.0, y.1, y.2)
11	operands	E	x	φ3	φ3 = φ(x from B = φ0, x from D = x.0, x from G = x.1)
12	seal	E	—	—
13	seal	H	—	—	preds C, E, G filled
14	phi	H	i	φ4	H reads i, H sealed, 3 preds
15	phi	E	i	φ5	reading i from H's pred E: E sealed, 3 preds
16	operands	E	i	φ5	φ5 = φ(φ1, φ1, φ5): from B, D (via C, B) and G (via F, E = φ5 itself)
17	remove trivial	E	i	φ5	only φ1 besides itself: φ5 → φ1
18	operands	H	i	φ4	φ4 = φ(φ1, φ1, φ1)
19	remove trivial	H	i	φ4	φ4 → φ1
20	phi	H	x	φ6	return x in I reads H
21	operands	H	x	φ6	φ6 = φ(x.0, φ3, x.1)
22	operands	B	x	φ0	B sealed after H: φ0 = φ(1, φ6) (the copy x = 1 was folded)
23	operands	B	i	φ1	φ1 = φ(0, i.0)
24	seal	B	—	—
25	seal	I	—	—

Seven phis were created, two were trivial: 5 phis, the same count as pruned SSA and at the same blocks (φ1 and φ0 at B, φ2 and φ3 at E, φ6 at H). Three differences from Cytron's pruned output are worth studying:

• The copies i = 0 and x = 1 produced no instruction: the phi at B receives the constants directly (step 22-23), so this output is transformed SSA in miniature.
• No phi was ever created for t: it is never read in a block that does not define it first (on-demand construction is automatically at least semi-pruned).
• The phis for i at E and H existed briefly: they were created because i is read in H and the lookup had to cross joins, then removed as trivial. Cytron's pruned placement never creates them because \(\mathrm{defs}(i) = \{A, H\}\) has no frontier at E or H.

The printed result (ch16-ssa --algo=braun running.tac):

ssa
A:
  br B(1, 0)
B(x.2, i.1):
  y.0 = add x.2, i.1
  cbr i.1, C(), E(y.0, x.2)
C:
  x.0 = add y.0, 2
  t.0 = lt x.0, 20
  cbr t.0, D(), H(x.0)
D:
  y.1 = mul y.0, 2
  br E(y.1, x.0)
E(y.3, x.3):
  t.1 = gt y.3, 0
  cbr t.1, F(), H(x.3)
F:
  x.1 = add x.3, y.3
  y.2 = sub y.3, 7
  br G()
G:
  t.2 = rem x.1, 3
  cbr t.2, E(y.2, x.1), H(x.1)
H(x.4):
  i.0 = add i.1, 1
  t.3 = lt i.0, 4
  cbr t.3, B(x.4, i.0), I()
I:
  ret x.4

Redundant SCCs on an irreducible CFG

The corpus listing irreducible-two-entry (in tests/ch16/Inputs/construct-corpus.txt) enters the loop {L, R} at both L and R. x is assigned only in the entry block; c is never assigned, so it is 0:

tac
  x = 5
  if c goto R
L:
  y = add y, 1
  t = lt y, 3
  ifz t goto X
R:
  goto L
X:
  return x

Reading x in X asks L (X's only predecessor); L and R are joins. Braun creates \(\varphi_2 = \phi(5, \varphi_3)\) at L and \(\varphi_3 = \phi(5, \varphi_2)\) at R. Neither is trivial on its own: each sees two different operands, 5 and the other phi. But \(\{\varphi_2, \varphi_3\}\) is a redundant set whose only outside operand is 5. Without Algorithm 16.3.4 the output keeps 4 phis (two for y, two for x); with it, the SCC \(\{\varphi_2, \varphi_3\}\) is replaced by 5, leaving 2 and ret 5. Minimal SSA places \(\mathrm{DF}^{+}(\mathrm{defs}(x)) = \emptyset\) for x: the two phis are outside it, which cannot happen on reducible CFGs (Theorem 16.3.7).

Aycock–Horspool on the running example

The joins are B, E, H, and there are 4 variables: 12 phis. After renaming with copy folding, rule R2 deletes \(i\)'s phis at E (\(\phi(i_B, i_B, i_E)\)) and H (\(\phi(i_B, i_B, i_B)\)); nothing else is redundant: 10 phis, including the three dead phis for t and the dead phis for y at B and H. Aycock–Horspool reaches minimal SSA's count here, not pruned SSA's: it never looks at uses.

Try it

build/<preset>/bin/ch16-ssa --algo=braun --stats labs/ch16-ssa-construct/inputs/running.tac prints the output above and phis: 5 once your lab L1 works; --algo=aycock-horspool prints phis: 10.

4. Invariants and correctness

Braun et al.

Theorem 16.3.6 (Correctness of Braun et al.'s construction)

After every block is filled and sealed, Algorithms 16.3.2 and 16.3.3 produce a strict SSA program in which every read of \(v\) at point \(p\) receives a value that, on every execution, equals the value of \(v\) at \(p\) in the original program.

Proof sketch (full proof: [BBH+13])

Value correctness by induction on the recursion of readVariable: a local hit returns the last write to \(v\) in the block, which is what the original program holds there; a single predecessor returns that predecessor's end value; a join returns a phi whose \(j\)-th operand is the end value of \(v\) in the \(j\)-th predecessor, which is exactly Definition 16.1.2's selection. Incomplete phis get the same operands later, when the predecessor list is final (sealing). A trivial phi \(p = \phi(w, p, \dots)\) equals \(w\) on every execution: on entry to its block along any edge it receives \(w\) or its own previous value, which by induction on the number of executions of the block is \(w\). Strictness: a read in block \(U\) that returns a phi of block \(B\) reached \(B\) by walking backwards from \(U\) through blocks with a single predecessor and no definition of \(v\); each such step goes to the block's unique predecessor, which dominates it, so \(B\) dominates \(U\). A phi operand read for the edge \(P \to B'\) is a read at the end of \(P\), and the same argument shows its definition dominates \(P\). Replacing a trivial phi by \(w\) keeps this: \(w\) is an operand of the phi, so its definition dominates the end of a predecessor of the phi's block along every path that does not go through the phi itself, hence it dominates the phi's block [BBH+13]. Termination: each (block, variable) pair creates at most one phi, because writeVariable(v, B, phi) precedes the recursive operand lookups.

Theorem 16.3.7 (Reducible CFGs: trivial-phi removal suffices)

If the CFG is reducible, every phi that survives Algorithms 16.3.2–16.3.3 lies at a block of \(\Phi_{\mathrm{pruned}}(v)\) (Definition 16.1.7). On irreducible CFGs, phis outside \(\mathrm{DF}^{+}(\mathrm{defs}(v))\) can survive, as the two-entry loop above shows.

Proof sketch (full proof: [BBH+13])

A phi is created at \(B\) for \(v\) only when a read of \(v\) reaches \(B\)'s start without a definition, so \(v\) is live-in at \(B\). It survives only if two of its operands resolve to different values; Braun et al. show that in a reducible CFG this implies two paths from different definitions of \(v\) (counting copies and the initial value) that meet first at \(B\), i.e. \(B \in J^{+}(\mathrm{defs}(v)) = \mathrm{DF}^{+}(\mathrm{defs}(v))\). The reducibility argument: a redundant SCC that contains no trivial phi must be entered at two different blocks from outside, which requires a loop with two entries. The oracle test Construction.test_random_programs checks the inclusion on 360 random programs and finds irreducible counterexamples.

Theorem 16.3.8 (After SCC removal no redundant set remains)

For a phi \(p\) let \(R(p)\) be the set of non-phi values that reach \(p\) through chains of phi operands (the least solution of \(R(p) = \bigcup_{o \in \mathrm{operands}(p)} (R(o)\) if \(o\) is a phi, else \(\{o\})\)). After Algorithms 16.3.2–16.3.4: (a) no set of surviving phis is redundant (Definition 16.3.1); (b) every survivor has \(\lvert R(p) \rvert \geq 2\), but the converse fails; (c) every survivor for \(v\) lies at a block of \(\Phi_{\mathrm{pruned}}(v)\).

Proof sketch (the algorithm and its minimality claim: [BBH+13, §3.2])

(a) Suppose a set \(P\) of survivors is redundant with outside value \(w\), and let \(K\) be a sink SCC of the operand graph restricted to \(P\): every operand of a member of \(K\) is in \(K\) or is \(w\), and \(K\) is strongly connected. Replacements only redirect operand edges along paths that existed before, so \(K\) lies inside one SCC \(C\) of the phi graph that Algorithm 16.3.4 processed. If \(w \notin C\), every phi of \(C\) is reachable from \(K\) inside \(C\), but operand edges leaving \(K\) go only to \(w\); so \(C = K\), \(\mathit{outer}(C) = \{w\}\) and \(C\) was replaced: contradiction. If \(w \in C\), every member of \(K\) has all its operands in \(C\), so \(K \subseteq \mathit{inner}\), and the same argument applies to the recursive call on \(\mathit{inner}\), whose sets are strictly smaller; the recursion ends with \(K\) replaced. (b) If \(R(p) = \{w\}\), the phis reachable from \(p\) through operand chains form a redundant set with outside value \(w\), which (a) excludes. The converse fails: in the example after this proof, a phi with \(\lvert R(p) \rvert = 2\) is removed. (c) A phi is created at \(B\) for \(v\) only when a lookup of \(v\) reaches \(B\)'s start through blocks without a definition of \(v\), on behalf of a real use or of a phi operand that is itself live, so \(v \in \mathrm{LiveIn}(B)\). Suppose \(B \notin \mathrm{DF}^{+}(\mathrm{defs}(v))\). Then by Theorem 16.2.6 one definition \(d\) of \(v\) (a statement or a phi of minimal SSA at a block \(D\)) is the last definition on every path from \(r\) to \(B\), and every lookup that starts at \(B\) walks backwards only through blocks on definition-free paths from \(d\) to \(B\). So all chains of phi operands from \(B\)'s phi end at the value \(d\) produces (if \(d\) is a statement) or at the Braun value of \(v\) at \(D\) (if \(d\) is a phi): the phis on those chains form a redundant set, which (a) excludes.

The converse of (b) fails when a redundant set sits behind a phi that really merges two values. In this listing x is 1 or 2 after the join J, and the irreducible loop {L, R} does not assign it:

tac
  if c goto A2
  x = 1
  goto J
A2:
  x = 2
J:
  if d goto R
L:
  y = add y, 1
  t = lt y, 3
  ifz t goto X
R:
  goto L
X:
  return x

Braun creates \(\varphi_J = \phi(1, 2)\), \(\varphi_L = \phi(\varphi_J, \varphi_R)\) and \(\varphi_R = \phi(\varphi_J, \varphi_L)\). \(R(\varphi_L) = R(\varphi_R) = \{1, 2\}\), yet \(\{\varphi_L, \varphi_R\}\) is redundant with outside value \(\varphi_J\), and Algorithm 16.3.4 replaces both by \(\varphi_J\) (the oracle trace prints remove SCC {phi4(L.x), phi6(R.x)} -> phi5(J.x)). So "at least two reaching values" is necessary for survival but not sufficient.

The lab's goldens rely on this result through minimized_phi_count in the oracle, which reaches the same count by a different route (phis at every live-in join, Cytron renaming with copy folding, then trivial-phi and SCC removal to a fixed point); the unit tests check that it equals the Braun count on all 360 random programs. A brute-force search for redundant sets among Braun's survivors, on 3 000 random goto programs (423 of them irreducible), found none, and no survivor outside \(\Phi_{\mathrm{pruned}}\).

Aycock–Horspool

Theorem 16.3.9 (Aycock–Horspool is minimal on reducible CFGs)

Algorithm 16.3.5 preserves the program's meaning. If the CFG is reducible, every phi it keeps lies at a block of \(\Phi_{\min}(v) = \mathrm{DF}^{+}(\mathrm{defs}(v))\).

Proof sketch (full proof: [AH00])

Meaning: R1 and R2 replace a phi by the only value it can ever hold (the argument of Theorem 16.3.6 for trivial phis). Termination: each application deletes a phi. Minimality: Aycock and Horspool show that on a reducible CFG, a phi at a block \(B\) outside \(\mathrm{DF}^{+}(\mathrm{defs}(v))\) receives, on every edge, either one fixed definition or a phi of the same kind, and that the reducibility (every loop has a single entry, its header) orders these phis so that one of them is always removable by R1 or R2, until none is left. On the irreducible two-entry loop the pair of phis for x at L and R is not removable by R1 or R2, as for Braun et al. The oracle test Construction.test_aycock_horspool_inside_minimal checks it on 800 random programs: on the 746 reducible ones the kept phis are always inside \(\Phi_{\min}\); 22 of the 54 irreducible ones keep phis outside it.

When the arguments break. Braun's algorithm needs every block to be sealed eventually; a front end that forgets to seal a block leaves incomplete phis with no operands. Both algorithms assume the entry has no predecessors (the lab adds a synthetic entry, as BlockCFG does). Copy folding makes the output transformed SSA, so leaving it needs the careful destruction of Lessons 16.6–16.7.

5. Complexity

\(S\) = instructions, \(n\) = blocks, \(\lvert V \rvert\) = variables, \(A\) = phis created, \(u\) = uses.

Technique	Time (worst)	Time (typical)	Space
Braun et al.	\(O(S + A \cdot \bar{k} + T)\), where \(\bar{k}\) is the average predecessor count and \(T\) the cost of trivial-phi removal: \(O(A \cdot u_\phi)\) if every removal rescans the phi's users (the lab's simple version), linear with use lists	about linear; slower than Cytron in the lab's Python-like C++ (226 ms vs 130 ms on 306 listings) because of the per-read recursion	\(O(n \cdot \lvert V \rvert)\) for the cur maps in the worst case, usually much less
+ SCC removal	\(O(A + E_\phi)\) for Tarjan on the phi graph, recursion depth bounded by the nesting of irreducible regions	negligible: few phis remain	\(O(A)\)
Aycock–Horspool	placement \(O(n_{\mathrm{join}} \cdot \lvert V \rvert)\) phis; each rule sweep \(O(A \cdot \bar{k})\), at most \(A\) sweeps: \(O(A^2 \bar{k})\)	a handful of sweeps	\(O(n_{\mathrm{join}} \cdot \lvert V \rvert)\) phis before minimization

Justification. Each (block, variable) pair is looked up at most once through the recursion before cur caches it, and each phi operand is one lookup, hence \(O(S + A \bar{k})\) lookups. Aycock–Horspool places a phi per join per variable; each sweep either deletes a phi or stops, so there are at most \(A + 1\) sweeps.

Proposition 16.3.10 (Aycock–Horspool's quadratic start)

A function with \(n_{\mathrm{join}}\) join blocks and \(\lvert V \rvert\) variables, of which each is used in a single block, starts with \(n_{\mathrm{join}} \cdot \lvert V \rvert\) phis although pruned SSA has none.

Proof

Placement is unconditional. Take a chain of \(n_{\mathrm{join}}\) diamonds and \(\lvert V \rvert\) temporaries each assigned and read inside one arm of one diamond: no temporary is live at any join, so pruned SSA has no phi, and Aycock–Horspool starts with one per (join, variable).

At scale. Braun et al. evaluate their construction against LLVM's mem2reg-based pipeline, in both compile time and phi counts [BBH+13]; read their evaluation for the numbers, which we did not re-check from the course container. On the lab corpus Braun places 4 352 phis against pruned SSA's 4 477 (copy folding removes the rest) and Aycock–Horspool 18 990, close to minimal SSA's 19 106 (tests/ch16/Inputs/construct-goldens.txt).

6. Variants and refinements

Braun et al.

• Marker algorithm for irreducible control flow instead of the SCC pass: Braun et al. also describe detecting redundant sets during construction by marking phis on a cycle [BBH+13] — trade-off: no separate pass, more bookkeeping per lookup.
• Block arguments instead of phis (Cranelift's SSABuilder) — trade-off: removing a trivial parameter must also delete the argument from every predecessor's branch [CL-SSA].
• No copy folding (keep x = y as an instruction) — trade-off: conventional SSA comes out (easier destruction, Lesson 16.6), more instructions.
• SSA repair after transformations (LLVM's SSAUpdater, Lesson 16.4) is the same lazy lookup applied to one variable at a time.

Aycock–Horspool

• Place phis only at joins where the variable is live — trade-off: needs liveness; then the result is pruned, and the algorithm becomes a "pruned SSA by simplification" method.
• Fixpoint by worklist (re-examine only the phi users of a deleted phi, like Algorithm 16.3.3) instead of full sweeps — trade-off: linear total work, more code.
• InstSimplify-style folding (LLVM simplifyPHINode) adds dominance-based undef handling: phi(x, undef) becomes x only if x dominates the phi — trade-off: more folding, a dominance query per phi.

7. In real compilers

Braun et al.

Cranelift: the Wasm local $t disappears, the others become block parameters

Reproduce (Wasmtime 37.0.2, wasmtime-v37.0.2-x86_64-linux release archive; any OS that Wasmtime supports):

cat > fib.wat <<'EOF'
(module
  (func (export "fib") (param $n i32) (result i32)
    (local $a i32) (local $b i32) (local $t i32)
    (local.set $b (i32.const 1))
    (block $done
      (loop $top
        (br_if $done (i32.eqz (local.get $n)))
        (local.set $t (local.get $a))
        (local.set $a (local.get $b))
        (local.set $b (i32.add (local.get $t) (local.get $b)))
        (local.set $n (i32.sub (local.get $n) (i32.const 1)))
        (br $top)))
    (local.get $a)))
EOF
mkdir -p clif && wasmtime compile --emit-clif clif fib.wat -o fib.cwasm
cat 'clif/wasm[0]--function[0].clif'

Output (complete):

;; Intermediate Representation of function <wasm[0]::function[0]>:
function u0:0(i64 vmctx, i64, i32) -> i32 tail {
    gv0 = vmctx
    gv1 = load.i64 notrap aligned readonly gv0+8
    gv2 = load.i64 notrap aligned gv1+16
    stack_limit = gv2

                                block0(v0: i64, v1: i64, v2: i32):
@0022                               v4 = iconst.i32 0
@0024                               v5 = iconst.i32 1
@002a                               jump block3(v2, v4, v5)  ; v4 = 0, v5 = 1

                                block3(v6: i32, v9: i32, v10: i32):
                                    v15 = iconst.i32 0
                                    v16 = icmp eq v6, v15  ; v15 = 0
@002e                               v8 = uextend.i32 v16
@002f                               brif v8, block2, block5

                                block5:
                                    v17 = iconst.i32 1
                                    v18 = isub.i32 v6, v17  ; v17 = 1
@003d                               v11 = iadd.i32 v9, v10
@0047                               jump block3(v18, v10, v11)

                                block2:
@004d                               jump block1(v9)

                                block1(v3: i32):
@004d                               return v3
}

What to notice: the translator declares one Variable per Wasm local and calls use_var/def_var, which is Algorithm 16.3.2 in cranelift/frontend/src/ssa.rs [CL-SSA]. The loop header block3 gets parameters for $n, $a, $b only: $t is written before it is read, so no lookup ever crosses a join for it. local.set $t is a folded copy (no instruction), and the back edge passes v10 (the old $b) as the new $a: the swap problem of Lesson 16.6 is already present in the construction's output. block1(v3) is the return block's parameter for the function result.

Go: Braun's construction for small functions keeps copies as values

Reproduce (Go 1.24.7, linux/amd64):

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

func Fib(n int) int {
    a, b := 0, 1
    for i := 0; i < n; i++ {
        a, b = b, a+b
    }
    return a
}
EOF
GOSSAFUNC='Fib+' go build . 2>&1 | sed -n '/^compiling Fib/,/^name i/p'

Output (complete):

compiling Fib
Fib func(int) int
  b1:
    (?) v1 = InitMem <mem>
    (?) v2 = SP <uintptr> DEAD
    (?) v3 = SB <uintptr> DEAD
    (?) v4 = LocalAddr <*int> {n} v2 v1 DEAD
    (?) v5 = LocalAddr <*int> {~r0} v2 v1 DEAD
    (-3) v6 = Arg <int> {n} (n[int])
    (?) v7 = Const64 <int> [0] (a[int], i[int])
    (?) v8 = Const64 <int> [1] (b[int])
    Plain -> b2
  b2: <- b1 b4
    (-5) v9 = Phi <int> v7 v16 (i[int])
    (-8) v21 = Phi <int> v7 v13 (a[int])
    (-6) v22 = Phi <int> v8 v14 (b[int])
    (-5) v10 = Copy <int> v6 (n[int])
    (5) v11 = Less64 <bool> v9 v10
    (-8) v20 = Copy <mem> v1
    If v11 -> b3 b5 (likely)
  b3: <- b2
    (-6) v12 = Copy <int> v21 (a[int])
    (-6) v13 = Copy <int> v22 (a[int], b[int])
    (6) v14 = Add64 <int> v12 v13 (b[int])
    Plain -> b4
  b4: <- b3
    (-5) v15 = Copy <int> v9 (i[int])
    (5) v16 = Add64 <int> v15 v8 (i[int])
    Plain -> b2
  b5: <- b2
    (-8) v17 = Copy <int> v21 (a[int])
    (-8) v18 = Copy <mem> v20
    (8) v19 = MakeResult <int,mem> v17 v18
    Ret v19
name n[int]: [v6 v10]
name a[int]: [v7 v12 v13 v17 v21]
name b[int]: [v8 v13 v14 v22]
name i[int]: [v7 v9 v15 v16]

What to notice: Go's simplePhiState (functions up to smallBlocks = 500 blocks, src/cmd/compile/internal/ssagen/phi.go [Go-SSAGen]) resolves each variable read (FwdRef) by looking backwards through predecessors, creating a phi only at the join b2, as Algorithm 16.3.2 does. Unlike the lab, Go keeps the lookups as Copy values and removes them, with trivial phis, in the next pass (early phielim and copyelim). n needs no phi: it is never reassigned, so every lookup ends at the same definition v6.

Aycock–Horspool

No production compiler builds maximal SSA on purpose, but the two reduction rules are LLVM's phi simplification, and the mem2reg and SSAUpdater clients call it on the phis they create.

LLVM InstSimplify applies rules R2 and R1 to phis

Reproduce (opt 23.1.2):

cat > ah.ll <<'EOF'
define i32 @ah(i32 %x, i32 %n) {
entry:
  br label %head

head:
  %p = phi i32 [ %x, %entry ], [ %q, %latch ]
  %i = phi i32 [ 0, %entry ], [ %i1, %latch ]
  %c = icmp slt i32 %i, %n
  br i1 %c, label %body, label %exit

body:
  %i1 = add i32 %i, 1
  br i1 %c, label %left, label %right

left:
  br label %latch

right:
  br label %latch

latch:
  %q = phi i32 [ %p, %left ], [ %p, %right ]
  br label %head

exit:
  ret i32 %p
}
EOF
opt -passes=instsimplify -S ah.ll | sed -n '/^define/,/^}/p'

Output (complete):

define i32 @ah(i32 %x, i32 %n) {
entry:
  br label %head

head:                                             ; preds = %latch, %entry
  %i = phi i32 [ 0, %entry ], [ %i1, %latch ]
  %c = icmp slt i32 %i, %n
  br i1 %c, label %body, label %exit

body:                                             ; preds = %head
  %i1 = add i32 %i, 1
  br i1 %c, label %left, label %right

left:                                             ; preds = %body
  br label %latch

right:                                            ; preds = %body
  br label %latch

latch:                                            ; preds = %right, %left
  br label %head

exit:                                             ; preds = %head
  ret i32 %x
}

What to notice: this is the maximal-SSA shape Aycock–Horspool start from for a variable \(p\) that the loop never changes: a phi at every join. %q = phi [%p], [%p] has one distinct operand (rule R2) and becomes %p; then %p = phi [%x], [%p] has only itself and %x (rule R2 again) and becomes %x. simplifyPHINode in llvm/lib/Analysis/InstructionSimplify.cpp [LLVM-InstSimplify] implements both rules (plus undef handling); the pass iterates until no instruction simplifies, like Algorithm 16.3.5's repeat. %i merges two different values and stays.

Find where LLVM does it. Open llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp (LLVM 23.1.2), PromoteMem2Reg::run, the loop after renaming. Question: which LLVM function does mem2reg call on each new phi to perform the Aycock–Horspool-style cleanup? (Quiz llvm-where-phi-simplify.)

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Braun et al.	pruned and copy-folded; minimal for reducible CFGs; needs the SCC pass for irreducible ones	about linear, no dominance information · lab: 227 ms on 306 listings (vs 130 ms for Cytron)	TSSA (copies folded); 4 352 phis on the lab corpus	~150 lines + ~60 for SCCs	Cranelift, Go (≤ 500 blocks), libFirm, LLVM's SSAUpdater
Aycock–Horspool	minimal (Cytron) on reducible CFGs; dead phis stay; redundant SCCs stay on irreducible CFGs	\(O(n_{\mathrm{join}} \lvert V \rvert)\) phis first, then sweeps · lab: 216 ms	18 990 phis on the lab corpus	~80 lines	teaching, quick prototypes; its rules are LLVM's phi simplification

Choose Braun et al. when SSA must be built while the CFG is being emitted (front ends, bytecode translators, JITs) or when you want pruned SSA without a liveness pass. Choose Aycock–Horspool when simplicity matters more than speed and the program is small, or as a cleanup step after a transformation that produced redundant phis. For batch construction of an already built CFG, Cytron with a pruned filter remains the standard.

9. Assessment

Technique	Quiz ids (solutions/quizzes/ch16.yaml)	Drill	Flashcard tag	Exercises
Braun et al.	braun-trivial, braun-scc, braun-seal	no dedicated drill: the lookup recursion is practiced in lab L1 (exact phi counts on 303 listings); ./course drill phi-placement (pruned column) drills the blocks it reaches on reducible CFGs	braun	lab L1 R6
Aycock–Horspool	ah-count, llvm-where-phi-simplify	./course drill phi-placement --difficulty hard (minimal column)	aycock-horspool	lab L1 R7 ★

Forgetting to re-check the users of a removed phi

Removing a trivial phi can make its phi users trivial (steps 17–19 above only work because tryRemoveTrivialPhi recurses into users). A version without the recursion leaves phis such as \(\phi(\varphi_1, \varphi_1, \varphi_1)\) behind. Without Algorithm 16.3.4 the phi count then goes up; with it, the SCC pass removes the leftover singletons at the end, so the lab's final counts hide the bug, and only a trace (or a construction without the SCC pass) shows it.

References

See the chapter references.