Lesson 11.1 — SSA generation strategies: syntax-directed translation, allocas + mem2reg, on-the-fly SSA

Techniques: tree-walking syntax-directed translation (Irons 1961), which turns every expression node into a fresh temporary; allocas + mem2reg (Clang; the Kaleidoscope tutorial), which puts every variable in memory and lets LLVM place the phis by iterated dominance frontiers (Cytron et al. 1991); direct SSA construction during code generation (Braun et al. 2013; Cranelift, Go, libFirm), which builds phis on demand without dominance information · Pebble implements: syntax-directed translation to PIR (E1–E4), allocas in the code generator (E5), ★ on-the-fly SSA in the code generator (E6; Chapter 16 implements it in full) · Prerequisites: SSA form and phis (Ch 8, Ch 9); dominance frontiers (Ch 15) · Time: 5–7 hours

A code generator produces values for expressions and locations for variables. Expressions are easy: every AST node computes one value once, so each gets a fresh name. Variables are the problem. s = s + i inside a loop assigns s many times, while LLVM IR demands that every register be assigned exactly once (static single assignment, SSA). This lesson covers the three ways production compilers bridge that gap, on one running example that every section reuses:

fn count(n: int) -> int {
    var s = 0;
    var i = 0;
    while i < n {
        if i & 1 == 0 { s = s &+ i; }
        i = i &+ 1;
    }
    return s;
}

(The wrapping operators &+ keep the example free of overflow checks; checks are Lesson 11.6.)

1. Problem and motivation

Syntax-directed translation

Irons' ALGOL 60 compiler attached a translation to each grammar rule and produced code in one walk over the parse [Iro61]; Aho, Lam, Sethi and Ullman call such a scheme a syntax-directed translation [ALSU07 §6.4]. Walking an expression tree bottom-up and giving every node a fresh temporary produces three-address code whose temporaries are already in SSA form: each one is written exactly once. What the walk cannot do is give a variable one definition, because the source assigns it several times. The walk therefore leaves variables as mutable locations. PIR is exactly this output: lowerToPIR (E1–E4) is a syntax-directed translation whose temporaries (_3, _4, _5 below) are written once, while the locals of var bindings (_1, _2) are assigned many times.

Allocas and mem2reg

Clang does not construct SSA at all. It gives every local variable a stack slot (alloca) in the entry block, reads it with load and writes it with store, and leaves the rest to LLVM's mem2reg pass, which promotes each slot to SSA registers and inserts phis where control flow merges [KAL7]. The phis are placed at iterated dominance frontiers and the uses renamed by a walk of the dominator tree: Cytron et al.'s algorithm [CFRWZ91], restricted to blocks where the variable is live (pruned SSA). The front end stays simple and uniform, and a variable whose address escapes stays in memory automatically. Pebble's reference code generator (E5) does exactly what Clang does [LLVM-Mem2Reg].

Direct SSA construction (on the fly)

Braun et al. showed that SSA can be built while the code is generated, with no dominance tree and no liveness: a read of a variable looks backwards through the predecessors of the current block and creates a phi only where two different definitions meet; phis that turn out to merge a single value (trivial phis) are removed at once [BBH+13]. Cranelift's front-end helper implements it (SSABuilder) [CL-SSA], Go's compiler builds SSA directly with forward-reference placeholders [GO-Phi], and libFirm uses it. It avoids generating (and then deleting) a load and store for every variable access. ★ E6 adds it to Pebble's code generator (pebblec --ssa=braun); Chapter 16 implements it on a stand-alone IR and proves it in full.

2. Definitions and algorithms

Definition 11.1.1 (SSA form, variable, temporary)

A function is in static single assignment (SSA) form if every value has exactly one static definition and every use of a value is dominated by its definition (a phi's operand is used at the end of the corresponding predecessor). In the output of a translation, a temporary is a name the translator invents for one expression node; a variable is a name the source program assigns, possibly many times.

Definition 11.1.2 (Syntax-directed lowering of expressions)

A syntax-directed lowering is a function \(\mathcal{T}[\![e]\!]\) defined by one equation per kind of expression node \(e\) that returns an operand (a constant, a variable or a temporary) and appends instructions to the current block. For a binary node, \(\mathcal{T}[\![e_1 \oplus e_2]\!] = t\) where \(o_1 = \mathcal{T}[\![e_1]\!]\), \(o_2 = \mathcal{T}[\![e_2]\!]\), and the instruction \(t \gets o_1 \oplus o_2\) is appended with \(t\) fresh.

Algorithm 11.1.3 (Tree-walking translation of an expression)

• Input: a typed expression tree \(e\); the current block \(B\).
• Output: an operand whose value, at the end of the appended instructions, is the value of \(e\).
• Precondition: \(e\) passed the type checker; every variable it names is in scope.
• Postcondition: every temporary the call creates is assigned exactly once, before its first use.
• Invariant: the temporaries created so far are pairwise distinct and each is defined by exactly one appended instruction (Lemma 11.1.4).

function Lower(e):
    if e is a constant c:            return c
    if e is a variable x:            return x              # a mutable location
    if e is op(e1, ..., ek):
        for j in 1..k: oj ← Lower(ej)                     # left to right (spec §8.2)
        t ← FreshTemp(type(e))
        Append(B, t ← op(o1, ..., ok))
        return t

Lemma 11.1.4 (Temporaries are in SSA form)

After Algorithm 11.1.3 returns, every temporary it created has exactly one definition, and that definition precedes every use of the temporary in the same block.

Proof

By induction on the height of \(e\). A constant or a variable creates no temporary. For \(e = \mathrm{op}(e_1, \dots, e_k)\), the recursive calls create disjoint sets of temporaries (each set contains only names that are fresh when created), each satisfying the claim by the induction hypothesis; their defining instructions are appended before the call returns. The new \(t\) is fresh, so it is distinct from all of them, and it is defined by the one instruction appended last, after the instructions that define \(o_1, \dots, o_k\). Its only use is by the caller, after it is returned, hence after its definition. All instructions are appended to the one block \(B\), so "precedes" is program order within \(B\).

Definition 11.1.5 (Promotable slot)

An alloca of a first-class scalar type is promotable if every use of its address is the pointer operand of a load or a store of that type (never a value stored, passed to a call, or offset by a GEP). For such a slot \(v\), \(\mathrm{defs}(v)\) is the set of blocks that store to it and \(\mathrm{live\text{-}in}(v)\) the set of blocks where a load of \(v\) can be reached before a store.

Algorithm 11.1.6 (Allocas then mem2reg)

• Input: a function whose locals were given one alloca each in the entry block (the code generator's half), with loads and stores for every access.
• Output: the same function with every promotable slot replaced by SSA values and phis.
• Precondition: every block is reachable (unreachable blocks are deleted first); slots satisfy Definition 11.1.5.
• Postcondition: each former load is replaced by the value of the reaching store (or poison if there is none); phis are exactly at \(\mathrm{DF}^{+}(\mathrm{defs}(v)) \cap \mathrm{live\text{-}in}(v)\) (pruned SSA).
• Invariant: during renaming, the top of \(\mathit{stack}[v]\) is the value of \(v\) reaching the current program point along the dominator-tree path from the entry.

function Mem2Reg(F):
    for each promotable slot v:
        D ← defs(v);  L ← LiveInBlocks(v)                 # backward walk from each load
        for each block b in IDF(D) ∩ L:                    # iterated dominance frontier
            insert  phi_v(b) : "v ← φ(...)"  at the top of b
    stack[v] ← [poison] for every v
    Rename(entry)

function Rename(b):                                       # preorder walk of the dominator tree
    pushed ← []
    for each phi_v in b: push(stack[v], phi_v); pushed.add(v)
    for each instruction I in b:
        if I = load v:   replace uses of I by top(stack[v]); delete I
        if I = store x → v: push(stack[v], x); pushed.add(v); delete I
    for each successor s of b, for each phi_v in s:
        add incoming (top(stack[v]), b) to phi_v
    for each child c of b in the dominator tree: Rename(c)
    for each v in pushed (one pop per push): pop(stack[v])
    # finally, delete the allocas

function LiveInBlocks(v):
    W ← blocks with a load of v that is not preceded by a store to v in the same block
    L ← {}
    while W not empty:
        b ← pop(W); if b ∈ L: continue; L ← L ∪ {b}
        for p in preds(b): if p does not store to v: W ← W ∪ {p}
    return L

Theorem 11.1.7 (mem2reg preserves meaning and produces pruned SSA)

Under the preconditions of Algorithm 11.1.6, the promoted function computes the same results as the original, every load is replaced by the value stored by the (unique) reaching store, and a phi for \(v\) exists at block \(b\) iff \(b \in \mathrm{DF}^{+}(\mathrm{defs}(v))\) and \(v\) is live on entry to \(b\).

Proof sketch (full proof: [CFRWZ91])

Cytron et al. prove that the join points where two different definitions of \(v\) meet are exactly \(\mathrm{DF}^{+}(\mathrm{defs}(v) \cup \{r\})\), and that renaming by a preorder walk of the dominator tree, with one stack of current names per variable (the invariant of Algorithm 11.1.6), gives each use the reaching definition. Intersecting with the live-in set removes only phis whose value is never used, which does not change any other value (pruned SSA; the liveness is exact because a promotable slot has no other readers). The slot is promotable, so no instruction other than the replaced loads could observe its contents: deleting the stores and the alloca changes nothing observable.

Definition 11.1.8 (Sealed block, incomplete phi, trivial phi)

During on-the-fly construction a block is sealed once all of its predecessors are known (no edge into it will be added). A phi created in an unsealed block has no operands yet: it is incomplete. A phi is trivial if its operands, ignoring references to the phi itself, are all one value \(w\) (or there are none); it can then be replaced by \(w\) (by poison if there are none).

Algorithm 11.1.9 (On-the-fly SSA construction, after Braun et al.)

• Input: the statements of a function, visited block by block; for every block, when it becomes sealed.
• Output: SSA values for every read of a variable, with phis.
• Precondition: the variable's address is never taken (Definition 11.1.5); every edge into a block is created before the block is sealed.
• Postcondition: each read returns the value of the reaching write, and no trivial phi remains (Theorem 11.1.10).
• Invariant: \(\mathit{def}[v][b]\), when present, is the value of \(v\) at the current end of block \(b\); every incomplete phi of an unsealed block is recorded in \(\mathit{incomplete}[b]\).

function WriteVariable(v, b, value):  def[v][b] ← value

function ReadVariable(v, b):
    if (v, b) ∈ def: return def[v][b]                     # local value numbering
    return ReadVariableRecursive(v, b)

function ReadVariableRecursive(v, b):
    if b is not sealed:
        val ← new phi in b with no operands;  incomplete[b].add((v, val))
    else if b has one predecessor p:
        val ← ReadVariable(v, p)                          # no phi needed
    else if b has no predecessor:
        val ← poison                                      # read before any write
    else:
        val ← new phi in b with no operands
        WriteVariable(v, b, val)                          # breaks cycles through loops
        val ← AddPhiOperands(v, val)
    WriteVariable(v, b, val)
    return val

function AddPhiOperands(v, phi):
    for each predecessor edge (p → block(phi)):
        add operand ReadVariable(v, p) for p
    return TryRemoveTrivialPhi(phi)

function TryRemoveTrivialPhi(phi):
    same ← none
    for each operand op of phi:
        if op = same or op = phi: continue
        if same ≠ none: return phi                        # merges two values: keep it
        same ← op
    if same = none: same ← poison
    users ← the phis among phi's users, other than phi
    replace every use of phi by same (also in def[·][·]); delete phi
    for each u in users: TryRemoveTrivialPhi(u)          # they may have become trivial
    return same

function SealBlock(b):
    for each (v, phi) in incomplete[b]: AddPhiOperands(v, phi)
    mark b sealed

Pebble's sealing policy (E6). The first LLVM block of each PIR block is sealed as soon as the terminators of all its PIR predecessors have been emitted; the blocks the code generator creates inside one PIR block (assert.ok, trap.*, the loop of a repeat) are sealed as soon as their one or two predecessors exist. Promoted locals are the scalar locals whose address no &/&mut rvalue takes.

Theorem 11.1.10 (On-the-fly construction is correct)

When every block has been sealed, every read \(\mathrm{ReadVariable}(v, b)\) made at a program point \(q\) of \(b\) has been resolved to a value that equals, on every execution reaching \(q\), the value of the last write to \(v\) executed before \(q\) (or poison if there is none).

Proof

Call a value correct for \((v, b)\) if it equals, on every path from the entry to the end of \(b\) (or to the read point inside \(b\)), the last write to \(v\) on that path. We show that every value stored in \(\mathit{def}[v][b]\) is correct for \((v, b)\) once all blocks are sealed, by induction on the order in which entries are written.

Local writes. WriteVariable at an assignment records the assigned value, which is the last write in \(b\) so far: correct by definition.

Recursive reads. (i) Single predecessor \(p\): every path to \(b\) passes through the end of \(p\) with no write in between, so the value correct for \((v, p)\) (induction hypothesis) is correct for \((v, b)\). (ii) No predecessor: the entry (where no write precedes, and poison is the specified result) or an unreachable block (E6 seals those before emission; their values are never observed). (iii) Several predecessors, or unsealed: the phi receives one operand per incoming edge \(p \to b\) (at creation if \(b\) is sealed, otherwise at SealBlock, which happens before the end by the precondition that every edge is created before sealing), and each operand is correct for \((v, p)\) by the induction hypothesis — the recursion terminates because the phi is recorded in \(\mathit{def}[v][b]\) before the predecessors are asked, so a loop leads back to the phi instead of recursing forever. A phi evaluates to the operand of the edge taken, hence it is correct for \((v, b)\).

Trivial-phi removal. If all operands other than the phi itself are one value \(w\), then on every path the phi yields either \(w\) or its own earlier value, which by induction on the number of loop iterations is \(w\); replacing it by \(w\) keeps every use correct. Replacing uses includes the entries of \(\mathit{def}\) (tracking handles in E6), so later reads see \(w\). Removing a phi can make a phi that used it trivial, which the recursive call handles; each call deletes one phi or returns, so the recursion terminates.

Theorem 11.1.11 (Minimality on reducible control flow)

If the CFG is reducible, Algorithm 11.1.9 with trivial-phi removal produces minimal SSA form: no phi could be removed without changing the value of some use. On irreducible CFGs, sets of phis that only reference each other and one outside value (redundant SCCs) can remain.

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

Braun et al. show that a non-trivial phi left by the algorithm on a reducible CFG merges two different definitions at the first block where their paths meet, which is the definition of a phi in minimal SSA; the argument uses the fact that in a reducible CFG every cycle of phis passes through a loop header whose entry edge brings a value from outside the loop, so a redundant cycle collapses to a trivial phi. For an irreducible loop with two entries, each header's phi references the other's: neither is trivial, yet together they carry one value. Their paper adds a pass that removes such strongly connected components; Chapter 16's lab implements it (Lesson 16.3). Pebble's lowering only produces reducible CFGs (Proposition 11.1.12), so E6 needs only the trivial-phi rule.

Proposition 11.1.12 (Pebble's lowering yields reducible CFGs)

Every CFG produced by the reference lowering of spec §15 (and by the code generator's splitting of PIR blocks) is reducible.

Proof

The lowering creates edges only from if (to the then/else/join blocks), while/for (to the header, body, exit and latch), break/continue/return, jumping code (Lesson 11.2) and asserts (to a trap block and a continuation). The only edges to a block created earlier in the walk are the jumps to a loop header (the back edge after the body and continue), and the header of a loop is created before, and control can enter the body only through it, so it dominates every block of its body. Hence every retreating edge targets a block that dominates its source, which is the characterization of reducible CFGs (Lesson 15.5). The code generator only splits blocks and adds edges to fresh trap and continuation blocks, which creates no new cycles.

3. Worked example

Syntax-directed translation

pebblec --emit=pir walks count with Algorithm 11.1.3 for expressions and the statement rules of spec §15. The three comparisons and the and get fresh temporaries (_3, _4, _5), each assigned once (Lemma 11.1.4); s and i stay variables (_1, _2) assigned twice each:

fn @count(_0: i64 "n") -> i64 {
  let _1: i64 "s"
  let _2: i64 "i"
  let _3: bool
  let _4: i64
  let _5: bool
bb0:
  _1 = 0 @2:5
  _2 = 0 @3:5
  goto bb1 @4:5
bb1:
  _3 = slt _2, _0 @4:11
  br _3, bb2, bb3 @4:5
bb2:
  _4 = and _2, 1 @5:12
  _5 = eq _4, 0 @5:12
  br _5, bb4, bb5 @5:9
bb3:
  return _1 @8:5
bb4:
  _1 = add _1, _2 @5:25
  goto bb5 @5:9
bb5:
  _2 = add _2, 1 @6:9
  goto bb1 @4:5
}

flowchart TD
  E([entry]) --> B0[bb0]
  B0 --> B1[bb1]
  B1 --> B2[bb2]
  B1 --> B3[bb3]
  B2 --> B4[bb4]
  B2 --> B5[bb5]
  B4 --> B5
  B5 --> B1
  classDef hl fill:#fde68a,stroke:#b45309;
  class B1,B5 hl;

Allocas and mem2reg

The code generator (E5) gives each of the six locals an alloca (%n.addr, %s.addr, %i.addr, %_3, %_4, %_5; the bools are i8 slots) and turns every read into a load. For mem2reg, the CFG is the one drawn above with the entry block entry in front of bb0. Its dominator tree is entry → bb0 → bb1 → {bb2, bb3}, bb2 → {bb4, bb5}, and the dominance frontiers are \(\mathrm{DF}(\mathit{bb4}) = \{\mathit{bb5}\}\), \(\mathrm{DF}(\mathit{bb5}) = \mathrm{DF}(\mathit{bb2}) = \mathrm{DF}(\mathit{bb1}) = \{\mathit{bb1}\}\), empty for the others. Algorithm 11.1.6 per slot:

slot	defs	\(\mathrm{DF}^{+}(\mathrm{defs})\)	live-in	phis
%n.addr	{entry}	{}	{bb0, bb1, bb2, bb4, bb5}	none
%s.addr	{bb0, bb4}	{bb1, bb5}	{bb1, bb2, bb3, bb4, bb5}	bb1, bb5
%i.addr	{bb0, bb5}	{bb1}	{bb1, bb2, bb4, bb5}	bb1
%_3	{bb1}	{bb1}	{}	none (pruned)
%_4	{bb2}	{bb1}	{}	none (pruned)
%_5	{bb2}	{bb1}	{}	none (pruned)

• %s.addr: the store in bb4 puts bb5 in the frontier; bb5's frontier adds bb1; bb1's frontier is bb1 again, no change. The minimal-SSA phi for the temporaries at bb1 is dropped because they are dead on entry to bb1 (pruning).
• The renaming walk visits entry, bb0, bb1, bb2, bb4, bb5, bb3 (a dominator-tree preorder); at bb4 the stack of s holds [poison, 0, φ(bb1)] and the store pushes %7; at the end of bb4 it fills φ(bb5)'s bb4 operand with %7.

The result has 3 phis; the real-world box in §7 shows it.

On-the-fly SSA construction

pebblec --ssa=braun runs Algorithm 11.1.9 while it emits the same PIR blocks in the order entry, bb0, …, bb5. Pending predecessor counts start at bb1: 2 (bb0, bb5), bb5: 2 (bb2, bb4), all others 1. Every event, in order (φ_v(b) is the phi for \(v\) in block \(b\)):

step	block	event	def / phis after the step
1	entry	write n := %n; entry sealed; br bb0 → bb0 sealed	def[n][entry] = %n
2	bb0	write s := 0, i := 0; goto bb1 → bb1 pending 1	def[s][bb0] = 0, def[i][bb0] = 0
3	bb1	read i: bb1 not sealed → incomplete φ_i(bb1)	incomplete[bb1] =
4	bb1	read n: not sealed → incomplete φ_n(bb1); br → bb2, bb3 sealed	incomplete[bb1] =
5	bb2	read i: one predecessor → ReadVariable(i, bb1) = φ_i(bb1); br → bb4 sealed, bb5 pending 1	def[i][bb2] = φ_i(bb1)
6	bb3	read s: one predecessor bb1, not sealed → incomplete φ_s(bb1); ret	incomplete[bb1] =
7	bb4	read s → φ_s(bb1), read i → φ_i(bb1); write s := %3; br → bb5 sealed	def[s][bb4] = %3
8	bb5	read i: sealed, 2 preds → φ_i(bb5) = [φ_i(bb1) from bb4, φ_i(bb1) from bb2]: trivial → φ_i(bb1)	φ_i(bb5) removed
9	bb5	write i := %4; br bb1 → bb1 pending 0 → SealBlock(bb1)
10	seal bb1	φ_i(bb1) ← [%4 from bb5, 0 from bb0]: two values, kept	φ_i(bb1) = %i
11	seal bb1	φ_n(bb1) ← [ReadVariable(n, bb5), %n from bb0]; the read in bb5 creates φ_n(bb5) = [φ_n(bb1), φ_n(bb1)] → trivial → φ_n(bb1); so φ_n(bb1) = [φ_n(bb1), %n] → trivial → %n	φ_n removed; uses of φ_n now %n
12	seal bb1	φ_s(bb1) ← [ReadVariable(s, bb5), 0 from bb0]; the read creates φ_s(bb5) = [φ_s(bb1) from bb2, %3 from bb4]: two values, kept	φ_s(bb1) = %s, φ_s(bb5) = %s4

After the last step: three phis (%s, %i in bb1, %s4 in bb5), the same number and places as mem2reg; no alloca, no load, no store, and no zext/trunc pairs for the bool temporaries. Chapter 16's oracle braun_ssa (Lesson 16.3) produces the same three phis for this function written in its TAC format.

Try it

./course drill phi-placement --seed 11 --difficulty medium --solution places phis by iterated dominance frontiers (Algorithm 11.1.6); ./course drill ssa-renaming --seed 4 --solution traces the renaming walk.

4. Invariants and correctness

Syntax-directed translation

Lemma 11.1.4 is the invariant: temporaries are single-assignment by construction, which is why PIR needs no phis — and why PIR must not reuse a temporary across two expressions: the lowering's isStable rule (spec §15) relies on temporaries never being written after their definition. The precondition that breaks it is sharing: a translator that caches the operand of a common subexpression and reuses it after the variable it read has been reassigned would read a stale value. lowerToPIR never caches.

Using a variable's place as an operand after a call

Returning the place x as the operand of x + f(&mut x) is only correct if x is read before the call. The reference lowering copies x into a temporary when a later operand may write it (mayWrite, spec §8.2); the e2e test order-binary-call.pbl fails otherwise.

Allocas and mem2reg

Theorem 11.1.7 needs promotability: a slot whose address is passed to a call may be read or written by the callee, so its loads are not determined by the stores in the function. mem2reg leaves such slots alone. It also needs every block to be reachable for the dominator tree; LLVM's pass skips unreachable blocks when renaming and fills their phi operands with poison.

On-the-fly SSA construction

Theorem 11.1.10 needs the sealing precondition: sealing a block before all edges into it exist would build a phi with too few operands. In E6 this is the pending-predecessor count; the ★ test ch11.SSAOnTheFly.ExecutablesBehaveLikeTheInterpreter compares every corpus program with pir-run. Theorem 11.1.11 needs reducibility, guaranteed by Proposition 11.1.12.

5. Complexity

\(n\) = blocks, \(e\) = CFG edges, \(V\) = variables (slots), \(U\) = uses of variables, \(|\mathrm{DF}|\) = total size of the dominance frontiers.

Technique	Time (worst)	Time (typical)	Space	Justification
Syntax-directed translation	\(O(\lvert\mathrm{AST}\rvert)\)	linear	one temporary per node	each node is visited once and appends \(O(1)\) instructions (Algorithm 11.1.3)
Allocas + mem2reg	\(O(V \cdot (n + e) + \lvert\mathrm{DF}\rvert)\) with frontier sets; LLVM's IDF calculator: \(O(V \cdot (n + e))\)	near linear	the allocas, then one phi per (variable, join)	liveness is one backward walk per slot; IDF per slot is linear with the Sreedhar–Gao priority-queue method [SG95] that IDFCalculator uses; renaming is one dominator-tree walk
On-the-fly SSA	\(O(V \cdot (n + e) + U)\)	linear	\(\mathit{def}\) maps: one entry per (variable, visited block)	ReadVariableRecursive runs at most once per (variable, block) because the result is memoized in \(\mathit{def}\); each creates at most one phi with one operand per incoming edge; each phi is removed at most once, and a removal costs its uses

Pathological family. For frontier-based placement, Cytron et al.'s nest of \(k\) repeat … until loops gives \(\lvert\mathrm{DF}\rvert = \Theta(k^2)\): the innermost block's frontier contains every enclosing header [CFRWZ91], so an algorithm that materializes frontier sets does quadratic work although only \(k\) phis are needed; the linear IDF method avoids materializing them. For on-the-fly construction, a loop header with \(V\) live variables that is read before its back edge exists gets \(V\) incomplete phis, and a chain of \(k\) nested loops whose innermost body reads all \(V\) variables creates \(k \cdot V\) phis before sealing — every one of which may be trivial and removed again: \(\Theta(kV)\) work for no phi in the result.

At scale. On this chapter's 77-program corpus (the conformance PIR samples and the e2e programs), ch11.SSAOnTheFly.ShapeAndMinimality counts 92 phis for both strategies (E6's solution vs E5 + LLVM's mem2reg).

6. Variants and refinements

Syntax-directed translation

• Backpatching [ALSU07 §6.7]: jumps whose targets are not yet known are emitted with holes and patched later, which allows translation in one pass without building the whole CFG first; trade-off: lists of holes instead of block objects.
• Value numbering during translation (a hash table from (op, operands) to temporaries, Lesson 13.3): removes redundant temporaries as they are created, as LLVM's IRBuilder constant folder does for constants; trade-off: the translator must know which operations are pure.
• Destination-driven translation (the reference lowering's lowerCall(…, MakeDest)): pass the destination place down so that the last instruction writes the variable directly (_1 = add _1, _2) instead of a temporary plus a copy.

Allocas and mem2reg

• SROA first splits aggregates into promotable scalar slots, then promotes them [LLVM-SROA]; it is what makes Clang's structs and Pebble's aggregate locals SSA values in LLVM's -O1/-O2 pipelines (pebblec -O2, or --passes=sroa).
• Linear-time IDF (Sreedhar and Gao [SG95]): a priority queue by dominator-tree depth instead of explicit frontier sets; LLVM's IDFCalculator uses it.
• The rustc hybrid: non_ssa_locals decides before code generation which MIR locals can be SSA values (assigned once, never borrowed) and gives allocas only to the others [RUSTC-NonSSA] — the syntax-directed temporaries never touch memory (box in §7).

On-the-fly SSA construction

• Redundant-SCC removal for irreducible CFGs [BBH+13] (Theorem 11.1.11); Chapter 16's lab implements it.
• Forward-reference placeholders (Go): reads that are not defined in the current block become FwdRef values; after the function is built, a pass resolves them — for large functions by a dominance-based phi placement, for small ones by a recursive lookup like Algorithm 11.1.9 — and leaves trivial phis to later passes [GO-Phi] (box in §7).
• Block parameters instead of phis (Cranelift): the same algorithm adds block parameters and branch arguments (Lesson 8.4, [CL-SSA]).

7. In real compilers

Syntax-directed translation

GCC's gimplifier lowers GENERIC trees to GIMPLE three-address code by one recursive walk, gimplify_expr in gcc/gimplify.cc [GCC-Gimplify]; rustc's MIR builder does the same for Rust (compiler/rustc_mir_build/src/builder/expr/) [RUSTC-LogicalOp]. Pebble's is lowerToPIR (solutions/pebble/lib/Lower/LowerExpr.cpp, FunctionLowering::lowerRvalue).

GCC's GIMPLE and rustc's MIR: fresh temporaries for expressions, mutable variables

Reproduce (gcc 14.2.0, rustc 1.94.1):

cat > expr.c <<'EOF'
int f(int a, int b, int c) {
  return (a + b) * (a - c) + b / c;
}
EOF
gcc-14 -O0 -fdump-tree-gimple -c expr.c && cat expr.c.*.gimple
cat > count.rs <<'EOF'
pub fn count(n: i64) -> i64 {
    let mut s: i64 = 0;
    let mut i: i64 = 0;
    while i < n {
        if i & 1 == 0 { s = s.wrapping_add(i); }
        i = i.wrapping_add(1);
    }
    s
}
EOF
rustc --crate-type=lib -C opt-level=0 --emit=mir count.rs -o count.mir
sed -n '/bb1: {/,/bb3: {/p' count.mir

Output (the MIR abridged to bb1–bb2):

int f (int a, int b, int c)
{
  int D.2774;

  _1 = a + b;
  _2 = a - c;
  _3 = _1 * _2;
  _4 = b / c;
  D.2774 = _3 + _4;
  return D.2774;
}


    bb1: {
        _5 = copy _3;
        _4 = Lt(move _5, copy _1);
        switchInt(move _4) -> [0: bb7, otherwise: bb2];
    }

    bb2: {
        _8 = copy _3;
        _7 = BitAnd(move _8, const 1_i64);
        _6 = Eq(move _7, const 0_i64);
        switchInt(move _6) -> [0: bb5, otherwise: bb3];
    }

    bb3: {

What to notice: each operator node became one assignment to a fresh temporary (_1–_4 in GIMPLE, _4–_8 in MIR), assigned once (Lemma 11.1.4). The variables s and i are MIR locals _2 and _3, assigned in several blocks: exactly PIR's split between temporaries and variables.

Allocas and mem2reg

Clang emits one alloca per local from CodeGenFunction::CreateTempAlloca in clang/lib/CodeGen/CGExpr.cpp [CLANG-CGExpr]; LLVM promotes them in PromoteMem2Reg::run (llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp) [LLVM-Mem2Reg], called by PromotePass (Mem2Reg.cpp) [LLVM-Mem2RegPass] and by SROA. rustc decides which MIR locals need a slot in non_ssa_locals (compiler/rustc_codegen_ssa/src/mir/analyze.rs) [RUSTC-NonSSA].

Clang's allocas and LLVM's mem2reg on the running example

Reproduce (clang 23.1.2, opt 23.1.2):

cat > count.c <<'EOF'
int count(int n) {
  int s = 0;
  for (int i = 0; i < n; i++)
    if (i % 3 == 0)
      s += i;
  return s;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm count.c -o count.ll
sed -n '/^define/,/^for.cond:/p' count.ll
opt -passes=mem2reg -S count.ll | sed -n '/^define/,/^}/p'

Output (the first command's output is the entry block only):

define dso_local i32 @count(i32 noundef %n) #0 {
entry:
  %n.addr = alloca i32, align 4
  %s = alloca i32, align 4
  %i = alloca i32, align 4
  store i32 %n, ptr %n.addr, align 4
  store i32 0, ptr %s, align 4
  store i32 0, ptr %i, align 4
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
define dso_local i32 @count(i32 noundef %n) #0 {
entry:
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %s.0 = phi i32 [ 0, %entry ], [ %s.1, %for.inc ]
  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
  %cmp = icmp slt i32 %i.0, %n
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %rem = srem i32 %i.0, 3
  %cmp1 = icmp eq i32 %rem, 0
  br i1 %cmp1, label %if.then, label %if.end

if.then:                                          ; preds = %for.body
  %add = add nsw i32 %s.0, %i.0
  br label %if.end

if.end:                                           ; preds = %if.then, %for.body
  %s.1 = phi i32 [ %add, %if.then ], [ %s.0, %for.body ]
  br label %for.inc

for.inc:                                          ; preds = %if.end
  %inc = add nsw i32 %i.0, 1
  br label %for.cond, !llvm.loop !5

for.end:                                          ; preds = %for.cond
  ret i32 %s.0
}

What to notice: Clang never computes a phi; every access to s, i and n is a load or store of its slot. mem2reg puts s's phis at the loop header and the join after the if — \(\mathrm{DF}^{+}\) of its two stores, as in the table of §3 — and i's at the header only; n, stored once, needs none (Theorem 11.1.7).

rustc: temporaries in registers, only the reassigned variables in allocas

Reproduce (rustc 1.94.1):

cat > count.rs <<'EOF'
pub fn count(n: i64) -> i64 {
    let mut s: i64 = 0;
    let mut i: i64 = 0;
    while i < n {
        if i & 1 == 0 { s = s.wrapping_add(i); }
        i = i.wrapping_add(1);
    }
    s
}
EOF
rustc --crate-type=lib -C opt-level=0 --emit=llvm-ir count.rs -o count.ll
sed -n '/^define/,/^bb7:/p' count.ll

Output:

define i64 @_ZN5count5count17h67b6f11c668df552E(i64 %n) unnamed_addr #0 {
start:
  %i = alloca [8 x i8], align 8
  %s = alloca [8 x i8], align 8
  store i64 0, ptr %s, align 8
  store i64 0, ptr %i, align 8
  br label %bb1

bb1:                                              ; preds = %bb5, %start
  %_5 = load i64, ptr %i, align 8
  %_4 = icmp slt i64 %_5, %n
  br i1 %_4, label %bb2, label %bb7

bb7:                                              ; preds = %bb1

What to notice: the MIR temporaries _4, _5 became SSA values directly and n is used as the argument register, while s and i — assigned in several blocks — got allocas (non_ssa_locals). This is the hybrid of §6: syntax-directed temporaries (Lemma 11.1.4) never touch memory.

On-the-fly SSA construction

Cranelift's SSABuilder in cranelift/frontend/src/ssa.rs (use_var, seal_one_block) cites Braun et al. in its header [CL-SSA]; Go's (*state).insertPhis in src/cmd/compile/internal/ssagen/phi.go resolves forward references, with simplePhiState for small functions [GO-Phi]; Pebble's ★ is FunctionLowering::readVariable in solutions/pebble/lib/CodeGen/PIRToLLVM.cpp.

pebblec --ssa=braun: SSA with no allocas, straight from PIR

Reproduce (pebblec built from this repository with -DPEBBLE_USE_SOLUTION=all, LLVM 23.1.2; on your PATH as build/<preset>/bin; count.pbl is the Pebble function at the top of this lesson plus fn main() -> int { return count(10); }):

pebblec --ssa=braun --emit=llvm count.pbl -o - | sed -n '/define internal i64 @count/,/^}/p'

Output:

define internal i64 @count(i64 %n) {
entry:
  br label %bb0

bb0:                                              ; preds = %entry
  br label %bb1

bb1:                                              ; preds = %bb5, %bb0
  %s = phi i64 [ %s4, %bb5 ], [ 0, %bb0 ]
  %i = phi i64 [ %4, %bb5 ], [ 0, %bb0 ]
  %0 = icmp slt i64 %i, %n
  br i1 %0, label %bb2, label %bb3

bb2:                                              ; preds = %bb1
  %1 = and i64 %i, 1
  %2 = icmp eq i64 %1, 0
  br i1 %2, label %bb4, label %bb5

bb3:                                              ; preds = %bb1
  ret i64 %s

bb4:                                              ; preds = %bb2
  %3 = add i64 %s, %i
  br label %bb5

bb5:                                              ; preds = %bb4, %bb2
  %s4 = phi i64 [ %3, %bb4 ], [ %s, %bb2 ]
  %4 = add i64 %i, 1
  br label %bb1
}

What to notice: the three phis of the §3 trace (steps 10–12), no memory traffic, and the bool temporaries are plain i1 values — pebblec --emit=llvm count.pbl | opt -passes=mem2reg gives the same phis but keeps a zext/trunc pair per bool temporary, because those went through i8 slots. The operands of %s are in predecessor order (bb5, bb0), as Algorithm 11.1.9 reads them.

Go: SSA built directly, trivial phis left for later passes

Reproduce (go 1.24.7):

mkdir gossa && cd gossa
printf 'module count\ngo 1.24\n' > go.mod
cat > count.go <<'EOF'
package count

func Count(n int) int {
    s := 0
    for i := 0; i < n; i++ {
        if i&1 == 0 {
            s += i
        }
    }
    return s
}
EOF
GOSSAFUNC='Count+' go build -a 2>&1 | awk '/^Count func/{n++} n==1' | sed -n '12,17p;33,37p'

Output (the header block b2 and the join b6 of the first dump, start):

  b2: <- b1 b4
    (-5) v8 = Phi <int> v7 v19 (i[int])
    (-5) v9 = Phi <int> v6 v28 (n[int])
    (-7) v23 = Phi <int> v7 v24 (s[int])
    (-10) v25 = Phi <mem> v1 v26
    (5) v10 = Less64 <bool> v8 v9
  b6: <- b3 b7
    (-7) v24 = Phi <int> v23 v17 (s[int])
    (-5) v27 = Phi <int> v11 v16 (i[int])
    (-10) v26 = Copy <mem> v25
    (-5) v28 = Copy <int> v9 (n[int])

What to notice: Go builds SSA while walking the syntax tree, like Algorithm 11.1.9, but does not remove trivial phis during construction: v9 = Phi v6 v28 for the parameter n is trivial (v28 is a copy of v9), exactly the phi that step 11 of §3 deletes, and v27 is trivial too (v16 copies v11). Go's later copyelim and phielim passes remove them.

Find where LLVM does it. Open llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp. Which function computes the set of blocks where an alloca is live on entry, so that PromoteMem2Reg::run can prune the phis? (Quiz llvm-where-mem2reg-livein.)

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Syntax-directed translation	SSA for expression temporaries only; variables stay mutable	\(O(\lvert\mathrm{AST}\rvert)\) · one walk	Output mirrors the source; easy to map back to locations	Low	Every front end's first step: GIMPLE, MIR, PIR, Clang's IR emission
Allocas + mem2reg	Pruned SSA for every promotable slot; escaping slots stay in memory automatically	\(O(V(n + e))\) · a separate pass, plus the load/store IR it deletes	The front end's IR is verbose (a load per read) but trivially correct	Lowest for the front end (no phis); mem2reg is shared	Clang, rustc (for non-SSA locals), Swift (SILMem2Reg), Pebble E5
On-the-fly SSA	Minimal SSA on reducible CFGs (+ SCC removal: all CFGs); needs to know which variables are address-taken	\(O(V(n + e) + U)\) · no intermediate memory IR	Compact IR from the start; phi names follow variables	Medium (sealing discipline, trivial-phi removal)	Cranelift frontends, Go (variant), libFirm, Pebble ★ E6

Choose syntax-directed translation when you are writing the first lowering out of an AST: it is always part of the answer. Choose allocas + mem2reg when the target has a good promotion pass (LLVM) and front-end simplicity matters more than compile time — the default for LLVM front ends. Choose on-the-fly construction when you generate IR for a backend without a promotion pass (Cranelift, a JIT) or when compile time matters, and you can tell which variables are address-taken before you start.

9. Assessment

• Quiz (./course quiz 11): sdt-temporaries (tag sdt); mem2reg-phi-blocks (tags sdt, allocas-mem2reg), llvm-where-mem2reg-livein (tag allocas-mem2reg); braun-trivial-phi, braun-phi-count (tag braun).
• Drills: ./course drill phi-placement (IDF, Algorithm 11.1.6) and ./course drill ssa-renaming (the renaming walk), both from Chapter 16. Syntax-directed translation has no separate drill: its output is fully determined (Lemma 11.1.4), and the jumping-code drill of Lesson 11.2 exercises the same recursive translation on conditions.
• Flashcards: tags sdt, allocas-mem2reg, braun.
• Exercises: E1–E4 (syntax-directed lowering to PIR), E5 (allocas), ★ E6 (on-the-fly SSA).

References

See the chapter references.