Lesson 8.4 — SSA form: phi functions and block arguments¶
Techniques: CFG + SSA with phi functions (LLVM IR, GCC GIMPLE SSA), SSA with block arguments (MLIR, Swift SIL, Cranelift) and the exact correspondence between the two · Pebble uses: LLVM IR (phi) after PIR is lowered; Ch 16 builds SSA over PIR · Lab: the
ssaform of labs/ch08-forms is block-argument SSA checked by a validator · Prerequisites: Lesson 8.2, dominance (Ch 15, Lesson 15.1) · Time: 4–6 hours
In TAC, s = add s, i overwrites s. Any analysis that asks "which value of s is this?" must solve a dataflow problem (reaching definitions, Ch 14). Static single assignment (SSA) form renames every assignment so that each name has exactly one definition. Then "which definition?" is answered by the name itself. At a join point, the values arriving from different predecessors must be merged. Classical SSA uses phi functions for this. MLIR, Swift SIL and Cranelift use block arguments: a block has parameters, and every branch passes arguments. This lesson shows that the two are the same thing, precisely (Theorem 8.4.10), and where they differ.
1. Problem and motivation¶
The problem. Give every value in a function exactly one static definition, so that use-def chains are explicit and every use is dominated by its definition, while keeping the program's behavior. Choose how to represent the merge of values at control-flow joins.
CFG with phi-SSA¶
SSA was developed at IBM in the late 1980s for global value numbering and code motion (Alpern, Wegman and Zadeck [AWZ88]; Rosen, Wegman and Zadeck [RWZ88]) and made practical by Cytron et al.'s dominance-frontier construction [CFRWZ91]. A phi function x3 = phi [x1, B1], [x2, B2] at the top of a block selects the value from the predecessor control came from. LLVM IR has been SSA from the start [LA04]. GCC's tree optimizers run on GIMPLE in SSA form (PHI <s_4(4), s_11(5)>) [GCC-Int]. The SSA book covers the theory in depth [SSAbook].
Block arguments¶
A phi is not really an instruction: it executes "on the edge", all phis of a block execute "at once", and it must list every predecessor. Block arguments make that explicit: a block is declared with parameters ^bb1(%s: i64, %i: i64), and each branch supplies arguments cf.br ^bb1(%s2, %i2 : i64, i64). The origin is continuation-passing style (Lesson 8.6): a block is a local function and a branch is a tail call. Swift's SIL [SIL-Docs] and MLIR [LAB+21; MLIR-LangRef] adopted block arguments, and so did Cranelift's IR [CL-IR-Docs]. The lab's ssa form is block-argument SSA with a validator (rules S0–S4).
2. Definitions and algorithms¶
Definition 8.4.1 (SSA; strict SSA)
A function over a CFG \(G = (N, E, r)\) (Definition 8.2.4) is in static single assignment form if every name has at most one definition site. It is strict if, in addition, for every use of a name \(x\) at a point \(p\) reachable from \(r\), the definition of \(x\) dominates \(p\) (Ch 15, Definition 15.1.2: every path from \(r\) to \(p\) passes through it). For a use in an instruction, \(p\) is that instruction. For a use as an argument on an edge \(u \to v\) (Definition 8.4.3 or 8.4.4), \(p\) is the end of \(u\).
CFG with phi-SSA¶
Definition 8.4.2 (Phi function and its semantics)
A phi function in block \(B\) with predecessors \(P_1, \dots, P_k\) is \(x = \phi([a_1, P_1], \dots, [a_k, P_k])\) with atoms \(a_j\). All phis of \(B\) sit at the top of \(B\). Semantics: when control moves along the edge \(P_j \to B\), first the values \(v_\ell = [\![a_{\ell j}]\!]\) of all phis \(\ell\) of \(B\) are read, and then all the results are written, \(x_\ell := v_\ell\). This is a parallel copy on the edge.
Definition 8.4.3 (Phi-form SSA program)
A phi-form function is a CFG whose blocks hold phis, then ordinary three-address
instructions (Definition 8.1.2, without goto/if), then one terminator: br B,
cbr a, B_t, B_f, or ret a. It is well formed if it is strict SSA
(Definition 8.4.1), each phi of \(B\) has exactly one entry per predecessor of \(B\), and the
phi operands \(a_j\) count as uses at the end of \(P_j\). LLVM's phi has this shape
[LLVM-LangRef].
Block arguments¶
Definition 8.4.4 (Block-argument SSA; rules S0–S4)
A block-argument function is a list of blocks \(B(p_1, \dots, p_k): \mathit{body};\ \mathit{term}\),
with parameters \(p_i\), three-address instructions, and a terminator br B(a_1, …),
cbr a, B_t(a_1, …), B_f(b_1, …) or ret a. The first block is the entry. It is valid
(the lab's validator) when:
S0 it parses;
S1 every name is defined once (as a parameter or an instruction result);
S2 every use is dominated by its definition: a parameter of \(B\) dominates all of \(B\),
an instruction dominates later instructions of its block and the terminator, and a
definition in block \(D\) dominates uses in \(B\) iff \(D\) dominates \(B\) (branch arguments
are uses at the terminator; uses in unreachable blocks are exempt);
S3 every branch to \(B\) passes exactly as many arguments as \(B\) has parameters;
S4 block names are unique, every target exists, and the entry has no parameters and is
not a branch target.
Semantics: a branch to \(B(a_1, \dots, a_k)\) reads all \(a_i\), then assigns
\(p_i := [\![a_i]\!]\) (a parallel copy), then runs \(B\).
Algorithm 8.4.5 (SSA validation, rules S1–S4)
- Input: a parsed block-argument function.
- Output: the list of violated rules (empty = valid).
- Precondition: S0 (it parsed).
- Postcondition: the list is empty iff the function satisfies S1–S4 (Definition 8.4.4).
- Invariant: \(\mathit{defsite}[x]\) is the unique (block, position) of \(x\), with position \(-1\) for parameters, once S1 has passed.
function ValidateSSA(F):
errors ← []
S4: check unique block names, existing targets, entry without parameters and predecessors
S1: for each parameter and instruction result x:
if x ∈ defsite: errors.add("S1: x defined twice") else defsite[x] ← (block, position)
S3: for each branch B'(args) in a terminator: if |args| ≠ |params(B')|: errors.add("S3 …")
if errors ≠ []: return errors # dominance needs a sane graph
Dom ← dominators of the reachable blocks (Ch 15, e.g. iterative in RPO)
for each use of name x at (block B, position q) with B reachable: # q = |body| for terminators
if x ∉ defsite: errors.add("S2: x never defined"); continue
(D, j) ← defsite[x]
if D = B and j ≥ q: errors.add("S2: x used before its definition")
if D ≠ B and D ∉ Dom(B): errors.add("S2: definition of x does not dominate its use")
return errors
Algorithm 8.4.6 (Phi form ↔ block arguments)
- Input: a phi-form function (Definition 8.4.3), or a block-argument function (Definition 8.4.4) with no multi-edge carrying different argument lists.
- Output: the other form.
- Precondition: for block arguments → phi, if both targets of a
cbrare the same block, both argument lists are equal (else split one edge first, Lemma 8.4.11). - Postcondition: the output has the same CFG, the same instructions and the same behavior (Theorem 8.4.10).
- Invariant: the \(i\)-th phi of \(B\) corresponds to the \(i\)-th parameter of \(B\); the entry of the \(i\)-th phi for predecessor \(P\) is the \(i\)-th argument of the branch \(P \to B\).
function PhiToArgs(F):
for each block B: params(B) ← [ x for x = φ(...) at the top of B, in order ]; remove the phis
for each terminator of block P and each target B in it:
args(P→B) ← [ a_P of the i-th phi of B, for i = 1 .. |params(B)| ]
function ArgsToPhi(F):
for each block B with params p_1..p_k:
for i in 1..k: insert at the top of B: p_i = φ([ args(P→B)[i], P ] for each pred P of B)
remove the parameter list
drop the argument lists from every terminator
Algorithm 8.4.7 (Naive block-argument SSA from a tree: the lab's algorithm)
- Input: a Tiny program with source variables \(V\).
- Output: a valid block-argument function (Definition 8.4.4) with the program's value.
- Precondition: fresh names
x.k(source names contain no.). - Postcondition: valid (S0–S4), same value (Theorem 8.4.9).
- Invariant: \(\mathit{env}[x]\) is an atom whose definition dominates the current emission point and which holds \(x\)'s current value.
function Stmts(ss, env): # emits into the current block; returns the new env
for s in ss:
case s of
x = e: env[x] ← Expr(e, env)
while c {b}:
Emit(br H(env[v] for v ∈ V)); H(ps) ← NewBlock with fresh params ps for V
envH ← (V ↦ ps); a ← Expr(c, envH); Emit(cbr a, Body(), Exit())
NewBlock Body; envB ← Stmts(b, envH); Emit(br H(envB[v] for v ∈ V))
NewBlock Exit # one predecessor (H): no parameters needed
env ← envH
if c {b1} else {b0}:
a ← Expr(c, env); Emit(cbr a, T(), E())
NewBlock T; e1 ← Stmts(b1, env); Emit(br J(e1[v] for v ∈ V))
NewBlock E; e0 ← Stmts(b0, env); Emit(br J(e0[v] for v ∈ V))
J(ps) ← NewBlock with fresh params ps; env ← (V ↦ ps)
return env
function Expr(e, env): # returns an atom
k: return k; x: return env[x]
op1 e1: a ← Expr(e1, env); t ← Fresh(); Emit(t = op a); return t
e1 ⊕ e2: a ← Expr(e1, env); b ← Expr(e2, env); t ← Fresh(); Emit(t = op a, b); return t
e1 && e2: a ← Expr(e1, env); Emit(cbr a, R(), J(0))
NewBlock R; b ← Expr(e2, env); t ← Fresh(); Emit(t = ne b, 0); Emit(br J(t))
J(r) ← NewBlock with fresh param r; return r # || is dual: J(1) on true
function Translate(ss return e): NewBlock entry; env ← (V ↦ 0); env ← Stmts(ss, env)
Emit(ret Expr(e, env))
3. Worked example¶
CFG with phi-SSA on the running example¶
Start from the TAC of Lesson 8.1 and its CFG B0…B9 (Lesson 8.2). The oracle tac_to_ssa builds block-argument SSA with every variable as a parameter of every non-entry block. That is 81 parameters for 9 variables (n s i t.0 t.1 t.2 t.3 t.4 t.5) and 9 blocks. Two pruning steps:
| step | rule | parameters left |
|---|---|---|
| maximal | every variable a parameter of every non-entry block | 81 |
| dead parameters (Choi et al. [CCF91]) | drop a parameter unless used by an instruction, cbr, ret, or passed to a live parameter |
26 |
| trivial parameters (Braun et al. [BBH+13]) | drop a parameter whose incoming arguments are all one value \(v\) (ignoring itself); replace it by \(v\); repeat | 4 |
The four survivors, written as phis (Algorithm 8.4.6, ssa_to_phi):
B1:
s.1 = phi [s.0, B0], [s.9, B8]
i.1 = phi [i.0, B0], [i.9, B8]
t.0_1 = le i.1, n.0
cbr t.0_1, B2, B9
…
B6:
t.1_7 = phi [t.1_4, B4], [t.1_6, B5]
cbr t.1_7, B7, B8
B7:
s.8 = add s.1, i.1
br B8
B8:
s.9 = phi [s.1, B6], [s.8, B7]
i.9 = add i.1, 1
br B1
s and i merge at the loop header, s again after the if, and t.1 (the value of ||) after its two assignments. LLVM's mem2reg/sroa puts its phis in the same places for the C version: %s.0, %i.0 in for.cond and %s.1 in if.end (§7). Clang's CFG has no block for the materialized || value, because it lowers || as jumping code.
Block arguments on the running example¶
The same four phis as block arguments (Algorithm 8.4.6, PhiToArgs):
| block | parameters | incoming edge | arguments |
|---|---|---|---|
| B1 | (s.1, i.1) | B0→B1 | (s.0, i.0) |
| B8→B1 | (s.9, i.9) | ||
| B6 | (t.1_7) | B4→B6 | (t.1_4) |
| B5→B6 | (t.1_6) | ||
| B8 | (s.9) | B6→B8 | (s.1) |
| B7→B8 | (s.8) |
The edge B6→B8 is critical (Lesson 8.2). In phi form, the copy s.9 ← s.1 has nowhere to go without splitting (Lemma 8.2.11). In block-argument form it is written in B6's terminator, cbr t.1_7, B7(), B8(s.1), and belongs to that edge only.
The lab's Algorithm 8.4.7 works from the syntax tree and passes every source variable at every join. For the running example it emits 17 instructions and terminators (ch08-lower --form=ssa labs/ch08-forms/inputs/euler1.tiny, reference solution):
ssa
entry:
br b.0(10, 0, 1)
b.0(n.0, s.0, i.0):
t.0 = le i.0, n.0
cbr t.0, b.1(), b.2()
b.1:
t.2 = rem i.0, 3
t.3 = eq t.2, 0
cbr t.3, b.7(1), b.6()
b.6:
t.4 = rem i.0, 5
t.5 = eq t.4, 0
t.6 = ne t.5, 0
br b.7(t.6)
b.7(t.1):
cbr t.1, b.3(), b.4()
b.3:
t.7 = add s.0, i.0
br b.5(n.0, t.7, i.0)
b.4:
br b.5(n.0, s.0, i.0)
b.5(n.1, s.1, i.1):
t.8 = add i.1, 1
br b.0(n.1, s.1, t.8)
b.2:
ret s.0
Two things are visible. First, copies disappear: n = 10 produces no instruction, env[n] is just the atom 10. Second, n.0, n.1, i.1 are trivial parameters (every argument is the same value or the parameter itself), which Braun et al.'s rule would remove, leaving exactly the phis of the table above. The validator (Algorithm 8.4.5) accepts both versions: minimality is an optimization, not a validity rule.
The swap problem: why phis are parallel
Euclid's loop t = a % b; a = b; b = t in the lab's SSA (gcd.tiny) ends its loop body
with br b.0(b.3, t.2, t.2) into b.0(a.0, b.3, t.0): the new a is the old b. As phis,
a.0 = phi [1071, entry], [b.3, b.1] and b.3 = phi [462, entry], [t.2, b.1]: the first
phi reads b.3, which the second phi defines in the same block. With sequential semantics
(first assign a.0, then b.3) this would still work, but a pair of phis swapping two
values (a = phi […, b], b = phi […, a]) would not. Definition 8.4.2 therefore reads
all operands before writing any result. LLVM's code for PIR's gcd (Lesson 8.7) contains
%a.addr.0 = phi i64 [ %a, %bb0 ], [ %b.addr.0, %bb5 ], which reads another phi of the same block.
Try it
./course drill phi-to-block-args --seed 4 --difficulty medium --solution (phi → block arguments) and
--difficulty hard (block arguments → phi, plus the critical edges that carry arguments).
4. Invariants and correctness¶
CFG with phi-SSA¶
Theorem 8.4.8 (Validation is sound and complete)
Algorithm 8.4.5 returns an empty list iff the function satisfies S1–S4 of Definition 8.4.4.
Proof
S1, S3 and S4 are checked literally, one definition, branch or block at a time. If one of them fails, the algorithm reports it and stops before S2, so a non-empty list is returned exactly when S1, S3 or S4 fails (or S2 fails, below). With S1 and S4 holding, \(\mathit{defsite}\) is a function and the graph is well formed, so the dominator sets of the reachable blocks are defined and computed exactly by the iterative algorithm (Theorem 15.1.22 in Ch 15). S2 is a conjunction over uses, and each use is checked against the two cases of Definition 8.4.4 (same block: the position order; different block: \(D \in \mathrm{Dom}(B)\)). A parameter has position \(-1\), so it precedes every use in its block. Uses in unreachable blocks are skipped, as S2 exempts them. A use of an undefined name violates S2 and is reported.
Theorem 8.4.9 (Algorithm 8.4.7 produces valid SSA with the program's value)
For every Tiny program \(p\), the output of Algorithm 8.4.7 satisfies S0–S4, and running it returns the value of \(p\) (Definition 0.2.2).
Proof
S1: every definition is a fresh name (a temporary, or a parameter created by NewBlock).
S3: a br H(…) or br J(…) passes one atom per variable of \(V\), and \(H\), \(J\) have one
parameter per variable. The && join has one parameter, and both branches to it pass one
atom. S4: blocks are fresh, the entry is created first with no parameters, and no branch
targets it. S2, by the invariant: \(\mathit{env}[x]\) is always a constant, a parameter of
the current block, or a definition in a block that dominates it. This holds initially
(constants 0). After x = e, the new atom is defined in the current block. At a loop
header \(H\) and an if-join \(J\), the environment becomes \(H\)'s or \(J\)'s own parameters,
which dominate everything emitted after them in the same construct. The body and branch
blocks each have a single predecessor (the block that ends in cbr), so they are
dominated by it and inherit its valid environment. The exit block's only predecessor is
\(H\), so \(H\)'s parameters dominate it. The && join \(J\) is dominated by the block where
\(e_1\) was evaluated, so atoms from \(\mathit{env}\) remain valid there. Value: by induction
on the big-step derivation, as in Theorem 8.1.10. Each branch passes the current values of
all variables, and the parallel copy on entry makes the parameters hold exactly the values
the source variables have at that point. The loop header receives the values of each
iteration, so the while rules are simulated one iteration at a time.
Block arguments¶
Theorem 8.4.10 (Phi functions and block arguments are equivalent)
Let \(F\) be a well-formed phi-form function and \(F' = \mathrm{PhiToArgs}(F)\). Then (a) \(F'\) is valid block-argument SSA (S1–S4) if \(F\)'s entry has no predecessors, (b) \(F\) and \(F'\) have the same behavior (the same sequence of blocks, instructions and values in every execution), and (c) \(\mathrm{ArgsToPhi}(F') = F\). Conversely, for a valid block-argument function \(F'\) in which no terminator branches twice to the same block with different arguments, \(\mathrm{ArgsToPhi}(F')\) is well-formed phi form with the same behavior, and \(\mathrm{PhiToArgs}\) maps it back to \(F'\).
Proof
Fix a block \(B\) with phis \(x_1, \dots, x_k\) (equivalently, parameters \(p_i = x_i\)) and a predecessor \(P\). By the invariant of Algorithm 8.4.6, the \(i\)-th argument of the branch \(P \to B\) is the \(P\)-entry of the \(i\)-th phi. (b) Semantics: on the edge \(P \to B\), Definition 8.4.2 reads all \(P\)-entries and then assigns the \(x_i\); Definition 8.4.4 reads all arguments of the branch and then assigns the \(p_i\). These are the same parallel copy, and the rest of \(B\) is unchanged. So by induction on the number of executed edges, both functions visit the same blocks with the same values. (a) S1: the names are unchanged, and each phi result becomes the parameter of the same name. S3: \(B\) has \(k\) phis and \(P\) passes \(k\) arguments. S2: a phi entry is a use at the end of \(P\) (Definition 8.4.3), and so is a branch argument (Definition 8.4.4), so the same dominance obligations appear in both. A phi result, used anywhere in \(B\) or below, is dominated by \(B\)'s top in both. S4 requires the entry to have no predecessors, which is the hypothesis. (c) and the converse: \(\mathrm{ArgsToPhi}\) rebuilds, for each parameter \(p_i\), the phi whose \(P\)-entry is the \(i\)-th argument of \(P \to B\). This is well defined iff each predecessor contributes one argument list, which is the no-conflicting-multi-edge hypothesis. It inverts \(\mathrm{PhiToArgs}\) entry by entry.
Lemma 8.4.11 (Multi-edges separate the two forms)
Block arguments can express cbr c, B(1), B(2), which has no phi form: a phi has one
entry per predecessor block, and here both edges come from the same block. Splitting one
of the two edges (Definition 8.2.5) restores the correspondence.
Proof
The function B0: cbr c, B1(1), B1(2); B1(x): ret x returns 1 or 2 depending on \(c\). A
phi \(x = \phi([a, B0])\) can name only one value for the predecessor B0, so no phi form over
the same CFG returns different values on the two edges. After splitting the false edge
through a new block \(X\) (B0: cbr c, B1(1), X(); X: br B1(2)), B1's predecessors are B0 and
\(X\), and \(x = \phi([1, B0], [2, X])\) is the phi form of Theorem 8.4.10. (LLVM allows a
br i1 %c, label %b, label %b multi-edge only if the phi lists the same value for both
entries. Its verifier rejects different ones.) The oracle checks this example
(tools/course/tests/test_ch08.py).
Proposition 8.4.12 (Pruning preserves validity and behavior)
In a valid function (S1–S4), removing a parameter \(p\) of \(B\) whose incoming arguments are all the same atom \(v\) or \(p\) itself, and replacing \(p\) by \(v\) everywhere, preserves validity and behavior when \(v\)'s definition strictly dominates \(B\) (so it dominates \(B\)'s uses of \(p\)). Removing a dead parameter (Algorithm of §3: not used except as an argument to dead parameters), together with the matching argument on every edge, preserves behavior.
Proof
Trivial parameter: we show that \(p = v\) whenever \(B\) runs, by induction on the entries into \(B\). An entry along an edge that passes \(v\) sets \(p\) to \(v\)'s current value. An entry along an edge \(L \to B\) that passes \(p\) itself keeps \(p\)'s value. That edge's argument is a use of \(p\) at the end of \(L\), so \(B\) dominates \(L\) (S2), and between the last execution of \(B\) and this entry control stayed in blocks other than \(B\). If \(v\)'s definition, in a block \(D \ne B\) that strictly dominates \(B\), ran in that stretch, then a path from the entry to \(D\) that avoids \(B\) (one exists, since \(D\) strictly dominates \(B\)), followed by the stretch from \(D\) to \(L\), would reach \(L\) without passing \(B\), contradicting \(B \mathrel{\mathrm{dom}} L\). So \(v\) was not redefined, and \(p = v\) still holds by the induction hypothesis. (A constant \(v\) is never redefined.) Substitution then preserves every computed value, and the dominance side condition keeps S2. It holds when \(v\) is a constant or a parameter or instruction of a block dominating all predecessors of \(B\) (the case in [BBH+13]). Dead parameter: its value never reaches an instruction, a condition or a return, so removing it and its arguments changes no observable value. The liveness closure ensures no live parameter loses an argument source.
5. Complexity¶
Variables: \(n\) = instructions, \(m\) = blocks, \(e\) = edges, \(V\) = source variables, \(P\) = phi functions (block parameters) in the result.
| Technique | Time (worst) | Time (typical) | Space | Justification |
|---|---|---|---|---|
| Phi ↔ block arguments (Alg. 8.4.6) | \(O(n + e \cdot k_{\max})\) | linear | same as input | one argument per (edge, parameter): \(\sum_B \lvert \mathrm{preds}(B) \rvert \cdot \lvert \mathrm{params}(B) \rvert\) |
| Naive construction (Alg. 8.4.7) | \(O(\lvert p \rvert + m \cdot V)\) | same | \(P = O(m \cdot V)\) parameters | every join passes all \(V\) variables |
| Validation (Alg. 8.4.5) | \(O(m^2 + n)\) with iterative bit-set dominators; \(O(e\,\alpha + n)\) with Lengauer–Tarjan | \(O(n)\) | \(O(m^2)\) bits or \(O(m)\) | Ch 15; each use checked in \(O(1)\) with a dominance query |
| Minimal SSA (Cytron) | \(O(e + m^2 V)\) worst, since \(P\) can be \(\Theta(m^2)\) in total argument count | near-linear | [CFRWZ91], Ch 16 |
Pathological family. A chain of \(m\) if-diamonds in which every diamond assigns all \(V\) variables forces \(V\) phis at every join even in minimal SSA, \(\Theta(mV)\). With block arguments, each join has two incoming edges with \(V\) arguments each, \(2mV\) arguments. For the naive Algorithm 8.4.7, \(P = mV\) even when no variable is assigned inside the diamonds. The running example shows the gap: 81 parameters naive, 4 after pruning.
At scale. Minimal SSA is linear in practice: Cytron et al. measured that the number of phis grows roughly linearly with program size on their benchmarks [CFRWZ91], and Braun et al. report that their construction, implemented in LLVM, is about as fast as LLVM's own dominance-frontier-based construction [BBH+13].
6. Variants and refinements¶
CFG with phi-SSA¶
- Minimal, pruned and semi-pruned SSA: phis only at the iterated dominance frontier, and only for live variables (pruned) or for names live across blocks (semi-pruned). The trade-off is the cost of liveness versus the number of useless phis (Ch 16, [SSAbook, Ch. 2–3]).
- Memory SSA (LLVM's
MemorySSA, GCC's virtual operands) gives memory states SSA names and phis (Ch 19). - Gated SSA / thinned gated SSA attach the branch condition to the phi (γ-functions), which leads toward the dependence graphs of Lesson 8.5.
Block arguments¶
- Edge arguments only on some terminators (SIL):
brandcond_brpass arguments, but other terminators (such asswitch_enum) cannot pass arbitrary ones, so their critical edges must be split. Swift's mandatory critical-edge splitting does this for "all non cond_branch terminators" [SIL-Docs]. - Successor operands in regions (MLIR):
scf.for'siter_argsandscf.yieldare structured block arguments, lowered tocf.brarguments bySCFToControlFlow(Lesson 8.7). - Cranelift's
brifwith arguments on both targets allows the parallel copies of both edges to be decided at the branch, so SSA destruction (in Cranelift's register allocator) never splits edges.
7. In real compilers¶
CFG with phi-SSA¶
LLVM: PHINode in llvm/include/llvm/IR/Instructions.h. PromoteMem2Reg in llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp places phis by iterated dominance frontiers (LLVM 23.1.2) [LLVM-Mem2Reg]. GCC: pass_build_ssa and insert_phi_nodes in gcc/tree-into-ssa.cc (gcc 15.1) [GCC-IntoSSA].
LLVM's phis for the running example
Reproduce (clang 23.1.2, opt 23.1.2; euler1.c from Lesson 8.1):
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm euler1.c -o euler1.O0.ll
opt -passes=sroa -S euler1.O0.ll | sed -n '/define/,/^}/p'
Output (complete function):
define dso_local i64 @euler1(i64 noundef %n) #0 {
entry:
br label %for.cond
for.cond: ; preds = %for.inc, %entry
%s.0 = phi i64 [ 0, %entry ], [ %s.1, %for.inc ]
%i.0 = phi i64 [ 1, %entry ], [ %inc, %for.inc ]
%cmp = icmp sle i64 %i.0, %n
br i1 %cmp, label %for.body, label %for.end
for.body: ; preds = %for.cond
%rem = srem i64 %i.0, 3
%cmp1 = icmp eq i64 %rem, 0
br i1 %cmp1, label %if.then, label %lor.lhs.false
lor.lhs.false: ; preds = %for.body
%rem2 = srem i64 %i.0, 5
%cmp3 = icmp eq i64 %rem2, 0
br i1 %cmp3, label %if.then, label %if.end
if.then: ; preds = %lor.lhs.false, %for.body
%add = add nsw i64 %s.0, %i.0
br label %if.end
if.end: ; preds = %if.then, %lor.lhs.false
%s.1 = phi i64 [ %add, %if.then ], [ %s.0, %lor.lhs.false ]
br label %for.inc
for.inc: ; preds = %if.end
%inc = add nsw i64 %i.0, 1
br label %for.cond, !llvm.loop !5
for.end: ; preds = %for.cond
ret i64 %s.0
}
What to notice: three phis, exactly the pruned ones of §3 for s and i (%s.0,
%i.0 at the loop header, %s.1 at the join after the if). The constants 0 and 1
appear directly as phi entries for %entry, like the argument list of br B1(0, 1).
Every phi entry names a predecessor block (Definition 8.4.3). The allocas of the -O0
code are gone: sroa rebuilt SSA from memory, which is Clang's strategy (Ch 11).
GCC's GIMPLE SSA: PHI nodes with predecessor numbers
Reproduce (gcc 14.2.0):
Output (complete function):
long int euler1 (long int n)
{
long int i;
long int s;
long int _1;
long int _2;
long int _9;
<bb 2> :
s_6 = 0;
i_7 = 1;
goto <bb 7>; [INV]
<bb 3> :
_1 = i_5 % 3;
if (_1 == 0)
goto <bb 5>; [INV]
else
goto <bb 4>; [INV]
<bb 4> :
_2 = i_5 % 5;
if (_2 == 0)
goto <bb 5>; [INV]
else
goto <bb 6>; [INV]
<bb 5> :
s_11 = s_4 + i_5;
<bb 6> :
# s_3 = PHI <s_4(4), s_11(5)>
i_12 = i_5 + 1;
<bb 7> :
# s_4 = PHI <s_6(2), s_3(6)>
# i_5 = PHI <i_7(2), i_12(6)>
if (i_5 <= n_8(D))
goto <bb 3>; [INV]
else
goto <bb 8>; [INV]
<bb 8> :
_9 = s_4;
return _9;
}
What to notice: GCC names SSA versions s_4, s_11 after the variable, and writes
phis as PHI <value(pred-bb), …>. n_8(D) is the default definition, the parameter's
value on entry, which plays the role of our entry block's parameters. Because GCC tests
the loop at the bottom (Lesson 8.1), the loop phis sit in bb 7.
Block arguments¶
MLIR: Block::getArguments in mlir/include/mlir/IR/Block.h. The verifier's dominance check (OperationVerifier::verifyDominanceOfContainedRegions, "operand #… does not dominate this use") is in mlir/lib/IR/Verifier.cpp. The translation to LLVM IR turns block arguments into phis in connectPHINodes (mlir/lib/Target/LLVMIR/ModuleTranslation.cpp, LLVM 23.1.2) [MLIR-Translate]. Cranelift: DataFlowGraph::append_block_param in cranelift/codegen/src/ir/dfg.rs (wasmtime v37.0.2), and the Braun-style SSABuilder in cranelift/frontend/src/ssa.rs [CL-SSA]. Swift: SILPhiArgument in include/swift/SIL/SILArgument.h (swift-6.1-RELEASE) [SWIFT-SILArg].
MLIR: block arguments, then phis — Theorem 8.4.10 as a tool
Reproduce (mlir-opt and mlir-translate 23.1.2, conda-forge package mlir 23.1.2):
cat > euler1.mlir <<'EOF'
func.func @euler1(%n: i64) -> i64 {
%c0 = arith.constant 0 : i64
%c1 = arith.constant 1 : i64
%c3 = arith.constant 3 : i64
%c5 = arith.constant 5 : i64
%np1 = arith.addi %n, %c1 : i64
%s = scf.for %i = %c1 to %np1 step %c1 iter_args(%acc = %c0) -> (i64) : i64 {
%r3 = arith.remsi %i, %c3 : i64
%r5 = arith.remsi %i, %c5 : i64
%z3 = arith.cmpi eq, %r3, %c0 : i64
%z5 = arith.cmpi eq, %r5, %c0 : i64
%c = arith.ori %z3, %z5 : i1
%next = scf.if %c -> (i64) {
%a = arith.addi %acc, %i : i64
scf.yield %a : i64
} else {
scf.yield %acc : i64
}
scf.yield %next : i64
}
return %s : i64
}
EOF
mlir-opt euler1.mlir --convert-scf-to-cf
mlir-opt euler1.mlir --convert-scf-to-cf --convert-to-llvm | mlir-translate --mlir-to-llvmir | sed -n '/define/,/^}/p'
Output (complete; first the cf dialect, then LLVM IR):
module {
func.func @euler1(%arg0: i64) -> i64 {
%c0_i64 = arith.constant 0 : i64
%c1_i64 = arith.constant 1 : i64
%c3_i64 = arith.constant 3 : i64
%c5_i64 = arith.constant 5 : i64
%0 = arith.addi %arg0, %c1_i64 : i64
cf.br ^bb1(%c1_i64, %c0_i64 : i64, i64)
^bb1(%1: i64, %2: i64): // 2 preds: ^bb0, ^bb6
%3 = arith.cmpi slt, %1, %0 : i64
cf.cond_br %3, ^bb2, ^bb7
^bb2: // pred: ^bb1
%4 = arith.remsi %1, %c3_i64 : i64
%5 = arith.remsi %1, %c5_i64 : i64
%6 = arith.cmpi eq, %4, %c0_i64 : i64
%7 = arith.cmpi eq, %5, %c0_i64 : i64
%8 = arith.ori %6, %7 : i1
cf.cond_br %8, ^bb3, ^bb4
^bb3: // pred: ^bb2
%9 = arith.addi %2, %1 : i64
cf.br ^bb5(%9 : i64)
^bb4: // pred: ^bb2
cf.br ^bb5(%2 : i64)
^bb5(%10: i64): // 2 preds: ^bb3, ^bb4
cf.br ^bb6
^bb6: // pred: ^bb5
%11 = arith.addi %1, %c1_i64 : i64
cf.br ^bb1(%11, %10 : i64, i64)
^bb7: // pred: ^bb1
return %2 : i64
}
}
define i64 @euler1(i64 %0) {
%2 = add i64 %0, 1
br label %3
3: ; preds = %18, %1
%4 = phi i64 [ %19, %18 ], [ 1, %1 ]
%5 = phi i64 [ %17, %18 ], [ 0, %1 ]
%6 = icmp slt i64 %4, %2
br i1 %6, label %7, label %20
7: ; preds = %3
%8 = srem i64 %4, 3
%9 = srem i64 %4, 5
%10 = icmp eq i64 %8, 0
%11 = icmp eq i64 %9, 0
%12 = or i1 %10, %11
br i1 %12, label %13, label %15
13: ; preds = %7
%14 = add i64 %5, %4
br label %16
15: ; preds = %7
br label %16
16: ; preds = %13, %15
%17 = phi i64 [ %5, %15 ], [ %14, %13 ]
br label %18
18: ; preds = %16
%19 = add i64 %4, 1
br label %3
20: ; preds = %3
ret i64 %5
}
What to notice: ^bb1(%1: i64, %2: i64) is the loop header with parameters \((i, s)\),
and cf.br ^bb1(%11, %10 : …) passes the next values, as in §3's table. mlir-translate
then runs PhiToArgs in reverse (connectPHINodes): each block argument becomes a phi
(%4, %5, %17), with one entry per incoming branch. The block ^bb4: cf.br ^bb5(%2) is
the "else" edge's parallel copy. It was never critical, because scf.if lowering gives
each arm its own block.
Cranelift IR: block parameters on a branch with two targets
Reproduce (Wasmtime 37.0.2; euler1.wasm from Lesson 8.1's Wasm box):
mkdir -p clif && wasmtime compile --emit-clif clif euler1.wasm -o euler1.cwasm
cat 'clif/wasm[0]--function[0].clif'
Output (complete file for the function):
;; Intermediate Representation of function <wasm[0]::function[0]>:
function u0:0(i64 vmctx, i64, i64) -> i64 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: i64):
@0027 v5 = iconst.i64 1
@0025 v4 = iconst.i64 0
v28 = iconst.i64 0x5555_5555_5555_5556
v31 = iconst.i64 63
@0038 v10 = iconst.i64 3
v36 = iconst.i64 0x6666_6666_6666_6667
@003e v14 = iconst.i64 5
@002d jump block3(v5, v4) ; v5 = 1, v4 = 0
block3(v6: i64, v19: i64):
@0033 v8 = icmp sgt v6, v2
@0033 v9 = uextend.i32 v8
@0034 brif v9, block2, block5
block5:
v46 = iconst.i64 0x5555_5555_5555_5556
v47 = smulhi.i64 v6, v46 ; v46 = 0x5555_5555_5555_5556
v48 = iconst.i64 63
v49 = ushr v47, v48 ; v48 = 63
v33 = iadd v47, v49
v50 = iconst.i64 3
v51 = imul v33, v50 ; v50 = 3
v35 = isub.i64 v6, v51
v11 -> v35
v52 = iconst.i64 0
v53 = icmp eq v35, v52 ; v52 = 0
v54 = iconst.i64 0x6666_6666_6666_6667
v55 = smulhi.i64 v6, v54 ; v54 = 0x6666_6666_6666_6667
v56 = iconst.i64 1
v57 = sshr v55, v56 ; v56 = 1
v58 = ushr v57, v48 ; v48 = 63
v40 = iadd v57, v58
v59 = iconst.i64 5
v60 = imul v40, v59 ; v59 = 5
v42 = isub.i64 v6, v60
v15 -> v42
v61 = icmp eq v42, v52 ; v52 = 0
v43 = bor v53, v61
v44 = uextend.i32 v43
@0043 brif v44, block6, block7(v19)
block6:
@0049 v20 = iadd.i64 v19, v6
@004c jump block7(v20)
block7(v25: i64):
v62 = iconst.i64 1
v63 = iadd.i64 v6, v62 ; v62 = 1
@0054 jump block3(v63, v25)
block2:
@005a jump block1(v19)
block1(v3: i64):
@005a return v3
}
What to notice: Wasm locals became block parameters: block3(v6, v19) is the loop header
with \((i, s)\). brif v44, block6, block7(v19) passes an argument on the false edge only.
That edge from block5 (two successors) into block7 (two predecessors) is critical, yet
its copy v25 ← v19 is written in the branch itself, and no block was split. This is the
advantage of §6. (The smulhi sequences are Cranelift's mid-end replacing srem by a
constant with multiplication, Lesson 8.5. The v11 -> v35 lines are value aliases left by
that rewrite.)
8. Comparison¶
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| CFG with phi-SSA | strict SSA: explicit use-def chains, dominance of definitions | phis \(\Theta(mV)\) worst; linear in practice · running example: 3 phis in LLVM | verifier checks "phi node entries do not match predecessors" and dominance | moderate (phi placement: Ch 16); multi-edges and critical edges need care | LLVM IR, GCC GIMPLE SSA, Go's SSA, HotSpot C2 (phis in the sea of nodes) |
| Block arguments | the same power (Theorem 8.4.10) plus per-edge copies on multi-edges (Lemma 8.4.11) | same asymptotics · lab: 17 instructions, 127 steps on the running example | parameters listed once per block; arguments at the branch | slightly lower: no "phi at the top" invariants, no predecessor lists | MLIR, Swift SIL, Cranelift, the lab's ssa form, many recent JITs |
Choose phis when you work inside LLVM or GCC, or when your passes iterate "for each phi of B, for each predecessor". Choose block arguments for a new IR: an edge's copies live with the edge, CFG edits need not rewrite phi predecessor lists, and the form maps directly onto functional IRs (Lesson 8.6). The one extra case (multi-edges with different arguments) is easy to split when lowering to LLVM.
9. Assessment¶
| Technique | Quiz ids (solutions/quizzes/ch08.yaml) |
Drill | Flashcard tag | Exercises |
|---|---|---|---|---|
| CFG with phi-SSA | phi-parallel-swap, pruned-phi-count |
./course drill phi-to-block-args --difficulty hard |
phi-ssa |
L1 (validator) |
| Block arguments | phi-to-args-mapping, multi-edge-args, mlir-where-phi |
./course drill phi-to-block-args |
block-args |
L1 (ssa form) |
A phi is not an instruction in the block it appears in
Its operands are used at the end of the predecessor. In
%s.1 = phi i64 [ %add, %if.then ], [ %s.0, %lor.lhs.false ], %add need not dominate
if.end: it only needs to dominate the end of if.then. Checking phi operands against
the phi's own block is the most common SSA-verifier bug, and the lab's rule S2 is written
to avoid it.
References¶
See the chapter references.