Lesson 9.3 — Control flow: terminators, phi and select, and the verifier's invariants¶
Techniques: terminators (
ret,br,switch,indirectbr,invoke/callbr/resume,unreachable);phiandselect; the verifier's invariants (well-formedness and the SSA dominance property) · Pebble uses:br,switch,ret,unreachable,phi,select· Lab: E1, E4, E7, E8, F1–F7 · Prerequisites: Lesson 9.1, Ch 15 (dominance; you only need Definition 9.3.2 below) · Time: 4 hours
The running example's if (a[i] > 0) s += a[i]; became two blocks and a phi (Lesson 9.1):
if.then:
%add = add nsw i64 %s.0, %1
br label %if.end
if.end: ; preds = %if.then, %for.body
%s.1 = phi i64 [ %add, %if.then ], [ %s.0, %for.body ]
Replace %s.1's use of %add by a direct use in %if.end (%s.1 = add i64 %add, 0) and the verifier refuses the function: "Instruction does not dominate all uses!". On the path for.body → if.end, %add was never computed. This lesson makes that rule and its companions precise: which instructions may end a block, what a phi means, why select exists next to it, and which invariants every function must satisfy. They are the rules you break in the lab's F-tasks.
1. Problem and motivation¶
A CFG-based IR has to say how a block hands control to the next (terminators), how values merge where paths join (phi), and which programs are meaningful at all (well-formedness). LLVM's choices follow the SSA literature: phi nodes at join points [CFRWZ91], one terminator per block, and a verifier that checks the SSA dominance property after every pass in debug builds [LA04, §2.1; LLVM-LangRef, §Well-Formedness].
Terminators¶
Every basic block ends with exactly one instruction that transfers control: return, branch, multiway branch, computed jump, a call that can unwind, or "this point is never reached". Making these explicit instructions, rather than implicit fall-through, is what lets block order be arbitrary: LLVM can move blocks around without changing semantics. Exception handling was the hard case: a call that may throw has two successors, so it must be a terminator (invoke), which is why LLVM has both call and invoke [LLVM-EH].
Phi and select¶
At a join, SSA needs to name "the value of s that arrived along whichever edge was taken". Cytron et al. introduced the \(\phi\)-function for this [CFRWZ91]; LLVM's phi instruction lists one incoming value per predecessor edge. select is the data-flow counterpart: the same choice without control flow, which lets the optimizer turn small diamonds into straight-line code (and the back end into cmov/csel).
The verifier's invariants¶
An IR that is transformed by hundreds of passes needs a precise notion of "valid", checked mechanically, or bugs surface far from their cause. LLVM's Verifier pass checks well-formedness; the parser runs it on every .ll file, and opt runs it before writing output. The central invariant is the SSA dominance property: every use is dominated by its definition, so that every value a use reads has actually been computed [CFRWZ91; ZNMZ12; SSAB, Ch. 2].
2. Definitions and algorithms¶
Definition 9.3.1 (Terminators and successors)
The terminators of LLVM 23 and their successor lists \(\mathrm{succs}(t)\) are:
| terminator | successors | meaning |
|---|---|---|
ret [τ v] |
none | return (the value, if any) to the caller |
br label %d |
\(\langle d \rangle\) | jump |
br i1 %c, label %t, label %f |
\(\langle t, f \rangle\) | to \(t\) if \(c = 1\), to \(f\) if \(c = 0\) |
switch iN %v, label %d [ iN c1, label %b1 … ] |
\(\langle d, b_1, \dots, b_k \rangle\) | to \(b_j\) if \(v = c_j\) (the \(c_j\) distinct constants), else to \(d\) |
indirectbr ptr %a, [label %b1, …] |
\(\langle b_1, \dots, b_k \rangle\) | to the block whose address (blockaddress) \(a\) is; UB if it is not listed |
invoke … to label %n unwind label %u |
\(\langle n, u \rangle\) | call; to \(n\) on return, to \(u\) if the callee unwinds |
callbr … to label %d [label %i1, …] |
\(\langle d, i_1, \dots \rangle\) | inline asm goto: fall through or jump to an indirect target |
resume {ptr, i32} %e |
none | continue unwinding with exception \(e\) |
catchswitch, catchret, cleanupret |
listed labels | funclet-based exception handling (Windows) |
unreachable |
none | executing it is undefined behavior |
Successors are counted with multiplicity: switch i32 %x, label %d [i32 1, label %j i32 2, label %j] gives \(j\) twice. The CFG of Definition 9.1.5 uses these edges.
Definition 9.3.2 (Dominance)
In the CFG \(G_f = (B, E, b_0)\), block \(d\) dominates block \(b\), written \(d \mathrel{\mathrm{dom}} b\), if every path from \(b_0\) to \(b\) contains \(d\); \(d \mathrel{\mathrm{sdom}} b\) if moreover \(d \ne b\) (as in Ch 15). A block not reachable from \(b_0\) is dominated by every block (the convention LLVM uses).
Definition 9.3.3 (A definition dominates a use)
Let value \(v\) be defined by instruction \(i_v\) in block \(b_v\) (a parameter counts as defined before the first instruction of \(b_0\)). A use of \(v\) as operand of instruction \(i\) in block \(b\) is dominated by its definition if
- \(i\) is not a
phi, and either \(b_v = b\) and \(i_v\) comes before \(i\) in \(b\), or \(b_v \mathrel{\mathrm{sdom}} b\); or - \(i\) is a
phiand \(v\) is its incoming value for the edge \(p \to b\), and \(b_v \mathrel{\mathrm{dom}} p\) (the definition is available at the end of the predecessor, where the value is read); or - \(b\) is unreachable from \(b_0\).
If \(i_v\) is an invoke, its result exists only after a normal return, so "\(b_v \mathrel{\mathrm{sdom}} b\)" (for a phi, "\(b_v \mathrel{\mathrm{dom}} p\)") is strengthened to: every path from \(b_0\) to \(b\) (for a phi: every path to \(p\) followed by the edge \(p \to b\)) passes through the edge from \(b_v\) to the invoke's normal destination. This is the edge-dominance test DominatorTree::dominates(const BasicBlockEdge &, const Use &) that the verifier applies.
Definition 9.3.4 (Well-formed function)
A function is well formed if:
- (W1) every block ends in exactly one terminator and contains no other (Definition 9.1.5);
- (W2) the entry block \(b_0\) has no predecessors (and therefore no phis);
- (W3) in every block, all
phiinstructions come before any other instruction (and alandingpador other EH pad, if present, is the first non-phi); - (W4) every phi in block \(b\) has exactly one entry per incoming edge of \(b\), counted with multiplicity, entries for the same predecessor carry the same value, and no entry names a non-predecessor;
- (W5) operand and result types agree with the instruction (for example, a
brcondition isi1,retreturns the function's type); - (W6) every use is dominated by its definition (Definition 9.3.3); in particular no non-phi instruction uses its own result;
- (W7) exception handling is consistent: the unwind destination of an
invokestarts (after phis) with alandingpad, and a function containing one has apersonality.
The parser enforces W1 (it starts a new block after each terminator) and W5; the Verifier enforces W2–W7.
Theorem 9.3.5 (SSA dominance property)
Let \(f\) be well formed and consider any execution of \(f\) that reaches a use of \(v\) in a reachable block. Then \(v\)'s definition was executed on that execution, and the value read is the one produced by the most recent execution of that definition before the use (for a phi use: before leaving the predecessor).
Proof
An execution follows a path \(\pi = b_0 \to b_1 \to \dots \to b_m = b\) of the CFG. Non-phi use, \(b_v \ne b\): by (W6) \(b_v \mathrel{\mathrm{sdom}} b\), so by Definition 9.3.2 the path \(\pi\) contains \(b_v\), and since the path ends at \(b \ne b_v\), it passes through all of \(b_v\), executing \(i_v\) (blocks execute to their terminator, W1). If \(i_v\) is an invoke, the strengthened condition of Definition 9.3.3 says that \(\pi\) uses the invoke's normal edge, so the call returned normally and defined \(v\). Non-phi use, \(b_v = b\): \(i_v\) precedes \(i\) in \(b\), so it executed earlier during this visit of \(b\). Phi use on edge \(p \to b\): the execution reached \(b\) from \(p = b_{m-1}\), so the prefix \(b_0 \to \dots \to p\) is a path to \(p\), which contains \(b_v\) because \(b_v \mathrel{\mathrm{dom}} p\); the definition executed before leaving \(p\). Most recent: each execution of \(i_v\) produces a new value for the single name \(v\) (SSA, Definition 9.1.6), and the use reads the name's current value, i.e. the last one produced. Parameters are defined on entry, before everything.
Algorithm 9.3.6 (Writing a counted loop in SSA form by hand)
- Input: a loop
for (x1 = e1, …, xk = ek; cond(x); ) bodywhose body updates the loop-carried variables \(x_1, \dots, x_k\), and whose result is some \(x_r\) after the loop. - Output: a well-formed CFG with blocks
entry,header,body,exitand no memory for the \(x_j\). - Precondition: \(e_1, \dots, e_k\) and every value used by
condandbodyother than the \(x_j\) are defined in or beforeentry. - Postcondition: W1–W6 hold; at the start of each iteration, phi \(x_j\) holds the variable's current value.
- Invariant: every value used in
headerorbodyis either a header phi, a value defined earlier in the same block, or defined inentry(which dominates both).
function WriteLoop(vars x1..xk, inits e1..ek, cond, body, result xr):
emit entry: compute e1..ek; "br label %header"
emit header: for j in 1..k: "%xj = phi τj [ ej, %entry ], [ %xj.next, %body ]"
"%c = <cond on %x1..%xk>"
"br i1 %c, label %body, label %exit"
emit body: compute %x1.next..%xk.next from %x1..%xk # new names: no updates in place
"br label %header"
emit exit: "ret τr %xr" # header dominates exit: %xr is available
A guarded variant tests the condition once in entry and jumps straight to exit, so that the loop runs at least once when entered; exit then needs a phi with one entry per incoming edge (lab E1, @collatz_steps).
Algorithm 9.3.7 (Checking well-formedness in LLVM's order)
- Input: the text of one function.
- Output: "valid", or the first violated rule of Definition 9.3.4.
- Precondition: the text uses only the constructs of Definition 9.3.1 and ordinary instructions.
- Postcondition: the reported rule is the one
llvm-as/opt -passes=verifyreports first. - Invariant: when step \(k\) runs, the rules of steps \(1, \dots, k - 1\) hold, so each step may rely on them (for example, dominance is only computed on a CFG whose blocks all have terminators).
function CheckFunction(text):
# parser (llvm-as)
1: for each block: if code follows a terminator, or a label follows a non-terminator → W1
2: for each name: if defined twice → "multiple definition"; if used but never defined → "undefined value"
3: for each use: if its type ≠ the type of its definition → W5 ("defined with type …")
4: for each ret: if the returned type ≠ the function's → W5
# verifier (Verifier::visitFunction, visitBasicBlock, visitPHINode, visitInstruction)
5: if preds(b0) ≠ ∅ → W2
6: for each block: if a phi follows a non-phi → W3
7: for each block b, phi φ: if multiset of φ's blocks ≠ multiset of preds(b) → W4
8: for each non-phi i: if i uses itself → W6 ("Only PHI nodes may reference their own value!")
9: compute the dominator tree; for each use: if not dominated (Definition 9.3.3) → W6
return valid
The drill ir-validity uses exactly this order (tools/course/lib/llvmir.py, check_function).
Phi and select semantics.
Definition 9.3.8 (Phi and select)
Let block \(b\) start with phis \(\phi_1, \dots, \phi_k\). When control transfers along edge \(p \to b\), the phis are assigned simultaneously: each \(\phi_j\) takes the value its entry for \(p\) had at the end of \(p\). A select i1 %c, τ %x, τ %y evaluates to \(x\) if \(c = 1\) and \(y\) if \(c = 0\); it is poison if \(c\) is poison, and otherwise poison only if the chosen operand is (Lesson 9.7).
3. Worked example¶
Checking the running example (Algorithm 9.3.7). The blocks of @sum_pos in RPO are entry, for.cond, for.body, if.then, if.end, for.inc, for.end. Its dominator tree (Ch 15, computable with opt -passes='print<domtree>'):
flowchart TD
entry([entry]) --> for.cond[for.cond]
for.cond --> for.body[for.body]
for.cond --> for.end[for.end]
for.body --> if.then[if.then]
for.body --> if.end[if.end]
if.end --> for.inc[for.inc](if.end is dominated by for.body, not by if.then, because of the edge for.body → if.end.) The trace of the checks:
| step | rule | what is checked on @sum_pos |
result |
|---|---|---|---|
| 1 | W1 | 7 blocks, each ends in br/ret |
ok |
| 2 | names | 13 local definitions, each once; every used name is defined | ok |
| 3 | W5 | e.g. %cmp is i1 in br i1 %cmp; %s.0 is i64 in add nsw i64 |
ok |
| 4 | W5 | ret i64 %s.0 in an i64 function |
ok |
| 5 | W2 | preds(entry) = ∅ |
ok |
| 6 | W3 | phis only at the tops of for.cond and if.end |
ok |
| 7 | W4 | for.cond: phi blocks {entry, for.inc} = preds; if.end: {if.then, for.body} = preds |
ok |
| 8 | W6 | no instruction uses itself | ok |
| 9 | W6 | see the dominance table below | ok |
Dominance of every non-trivial use (step 9):
| use | in block | definition in | rule of Definition 9.3.3 | holds? |
|---|---|---|---|---|
%s.0 in %add |
if.then | for.cond | for.cond sdom if.then | yes |
%s.0 in ret |
for.end | for.cond | for.cond sdom for.end | yes |
%s.0 entry of %s.1 for edge for.body → if.end |
if.end (phi) | for.cond | for.cond dom for.body | yes |
%add entry of %s.1 for edge if.then → if.end |
if.end (phi) | if.then | if.then dom if.then | yes |
%s.1 entry of %s.0 for edge for.inc → for.cond |
for.cond (phi) | if.end | if.end dom for.inc | yes |
%inc entry of %i.0 for edge for.inc → for.cond |
for.cond (phi) | for.inc | for.inc dom for.inc | yes |
%i.0 in %arrayidx2 |
if.then | for.cond | for.cond sdom if.then | yes |
hypothetical %add in ret |
for.end | if.then | if.then sdom for.end? no (path via for.body → if.end) | W6 fails |
The last row is the mistake from the introduction; it is lab task F1 in another function.
A phi swap. The simultaneity in Definition 9.3.8 matters when phis read each other. The loop header of the Fibonacci function of lab task F3
loop:
%a = phi i64 [ 0, %entry ], [ %b, %loop ]
%b = phi i64 [ 1, %entry ], [ %sum, %loop ]
%sum = add i64 %a, %b
executes, on the back edge, \(a' = b\) and \(b' = \mathit{sum}\) at once:
| iteration | %a |
%b |
%sum |
|---|---|---|---|
| 1 (from entry) | 0 | 1 | 1 |
| 2 (back edge) | 1 | 1 | 2 |
| 3 | 1 | 2 | 3 |
| 4 | 2 | 3 | 5 |
If the phis were executed one after the other in the order %b, then %a, the back edge after iteration 2 would first set %b ← %sum = 2 and then %a ← the new %b = 2, giving (2, 2) instead of (1, 2). Textual order (%a first) happens to give the right answer here, but only because %a reads %b before %b is overwritten; the semantics must not depend on the order in which phis are listed, so the reading %a ← %b always sees the old %b. Out-of-SSA translation must implement these parallel copies with care (Ch 16, the "swap problem").
Select from a diamond. simplifycfg turns the running example's if into a select (real-world box in the "Phi and select" section): it speculates %add = add nsw i64 %s.0, %0 into for.body, which now runs even when a[i] ≤ 0, and picks with %spec.select = select i1 %cmp1, i64 %add, i64 %s.0. If the speculated add nsw overflows on a path where the source would not have executed it, it is poison, but the select does not choose it. That is why select's poison rule is "only the chosen operand" (Lesson 9.7, Proposition 9.7.12).
Try it
./course drill ir-validity --seed 11 --difficulty medium --solution shows the step table of Algorithm 9.3.7 on a random function, one rule broken or none.
4. Invariants and correctness¶
Terminators¶
Proposition 9.3.9 (Block order does not matter)
Permuting the blocks of a well-formed function other than the entry block yields a well-formed function with the same executions.
Proof
No terminator falls through: every successor is named explicitly (Definition 9.3.1), so the CFG \(G_f\) does not depend on block order. Rules W1–W5 and W7 are local to blocks or instructions. Dominance (Definition 9.3.2) is a property of \(G_f\) and of the positions of instructions within blocks, both unchanged, so W6 is preserved. Executions follow CFG edges from the entry block, which is fixed, so they are unchanged.
unreachable deserves a separate remark: it has no successors, so a block ending in it has no way out, and reaching it is undefined behavior. Optimizers may therefore delete any code that must reach it, and may treat the branch that leads to it as never taken, which is how __builtin_unreachable() in a default: case turns a switch into a table lookup (real-world box below).
Phi and select¶
Proposition 9.3.10 (Branch to select is a refinement)
Let \(b\) end in br i1 %c, label %t, label %e where \(t\) and \(e\) each contain only speculatable instructions, compute \(x\) and \(y\) respectively, and branch to \(j\), whose phi is %r = phi [ %x, %t ], [ %y, %e ]. Replacing the diamond by the instructions of \(t\) and \(e\) in \(b\) followed by %r = select i1 %c, %x, %y produces a program whose every behavior is a behavior of the original.
Proof
Case \(c \in \{0, 1\}\): the original executes one arm and \(r\) is that arm's value; the new program executes both arms, which is allowed because their instructions are speculatable (no side effects, no immediate UB: e.g. add nsw may yield poison but never traps), and the select returns the same arm's value. If the other arm's value is poison, select ignores it (Definition 9.3.8). Case \(c\) poison: branching on poison is undefined behavior in the original (Lesson 9.7), so any behavior of the new program, which gets \(r\) = poison, is allowed. The converse fails: turning a select on a possibly-poison condition into a branch introduces UB, unless the condition is first freezed.
The verifier's invariants¶
Proposition 9.3.11 (Why the entry block may not have predecessors)
If (W2) held without its restriction, a phi in the entry block would have no well-defined value on function entry.
Proof
On entry, control arrives at \(b_0\) without traversing any CFG edge, so no phi entry applies (Definition 9.3.8 assigns phis only along edges). A phi in \(b_0\) would therefore be undefined on the first iteration. Forbidding predecessors of \(b_0\) also forbids phis there, since a phi with zero entries in a block with zero predecessors is useless and rejected. The lab's F4 is exactly this: a loop whose header is the entry block must get a new entry block.
The SSA dominance property (Theorem 9.3.5) is the invariant most passes silently rely on: GVN replaces a value by an equivalent one only if the replacement dominates the use; LICM hoists an instruction only to a block that dominates all its uses; SROA and mem2reg place phis precisely so that every new use is dominated. A pass that violates it produces IR that the verifier catches, and that without the verifier would read garbage.
When it breaks. Theorem 9.3.5 needs (W1): a block that could be left before its terminator would break "the path passes through all of \(b_v\)". Unwinding is the exception that proves the rule: an ordinary call that throws leaves the block in the middle, so a definition after the call is not executed. That is why a call that may unwind to a handler in the same function must be the terminator invoke, and why values defined by an invoke are available only in its normal successor: the verifier checks that the invoke's result is used only in blocks dominated by the normal edge.
5. Complexity¶
| Technique | Time (worst) | Time (typical) | Space | Variables |
|---|---|---|---|---|
| Parsing blocks and terminators (W1) | \(\Theta(i)\) | linear | \(O(i)\) | \(i\) = instructions |
| Phi-entry check (W4) | \(O(\sum_b \mathrm{phis}(b) \cdot \mathrm{preds}(b))\) | linear | \(O(\mathrm{preds})\) | — |
| Dominance check (W6), per use | \(O(1)\) with DFS intervals, after building the tree | — | \(O(n)\) | \(n\) = blocks |
| Whole verifier | \(O(i + u + T_{\mathrm{dom}}(n, e))\) (Proposition 9.3.12) | near-linear | \(O(n + u)\) | \(u\) = uses, \(e\) = edges |
Proposition 9.3.12 (Cost of Algorithm 9.3.7)
Algorithm 9.3.7 runs in \(O(i + u + T_{\mathrm{dom}}(n, e))\) time, where \(T_{\mathrm{dom}}\) is the time to build the dominator tree (Ch 15: near-linear for Lengauer–Tarjan, \(O(n^2)\) worst case for Semi-NCA as used by LLVM).
Proof
Steps 1–8 visit each instruction and each use a constant number of times, with hash lookups for names, \(O(i + u)\). Step 7 compares, per phi, a multiset of incoming blocks with the predecessor multiset; summed over all phis this is \(O(\sum_b \mathrm{phis}(b) \cdot \mathrm{preds}(b))\), bounded by the number of phi operands, i.e. by \(u\). Step 9 builds the dominator tree once, \(T_{\mathrm{dom}}(n, e)\), and then answers each use in \(O(1)\): same-block uses compare instruction positions (LLVM caches an order number per instruction), cross-block uses compare DFS entry/exit numbers of the tree.
Pathological input. A block with \(p\) predecessors and \(k\) phis has \(k \cdot p\) phi operands: a switch with \(10^4\) cases jumping to one join with 100 phis creates \(10^6\) operands, all checked. A same-block dominance query without cached instruction order would cost \(O(\text{block length})\), making a long block with many uses quadratic; LLVM renumbers instructions lazily (Instruction::comesBefore) to keep it \(O(1)\) amortized.
6. Variants and refinements¶
Terminators¶
- Funclet-based EH (
catchswitch,catchpad,cleanuppad,catchret,cleanupret) [LLVM-EH]: models Windows SEH/C++ EH, where handlers are separate "funclets", with tokens tying pads to their exits (Lesson 9.2); trade-off: more terminators and rules, but required by the Windows ABI. callbr(asm goto): a call with multiple successors, needed by the Linux kernel's static keys; trade-off: critical edges that cannot be split normally.- Switch lowering in the back end (jump tables, bit tests, binary search): the IR keeps one
switch; the choice is made late (Ch 11).
Phi and select¶
- Block arguments (MLIR, SIL, Cranelift) instead of phis: branches pass values explicitly; no "one entry per predecessor" bookkeeping, and multiple edges from one block to another can carry different values (Lesson 9.8).
selectwith vector conditions chooses per lane;llvm.smax/smin/umax/umin/absare canonical forms of common selects (the running example's select becomessmaxunderinstcombine).
The verifier's invariants¶
- Machine verifier (
-verify-machineinstrs): the same idea for Machine IR after instruction selection (Ch 21). - Formal verification of the IR's well-formedness and of SSA-preserving transformations: Vellvm formalizes LLVM IR in Coq and proves the dominance property is preserved by
mem2reg-like passes [ZNMZ12]; Alive2 validates transformations semantically [LLM+21].
7. In real compilers¶
Terminators¶
LLVM
llvm/include/llvm/IR/Instructions.h — classes ReturnInst, BranchInst (split in LLVM 23 into the subclasses UncondBrInst and CondBrInst), SwitchInst, IndirectBrInst, InvokeInst, CallBrInst, ResumeInst, UnreachableInst; llvm/lib/Transforms/Utils/SimplifyCFG.cpp — simplifySwitchLookup turns a switch that selects constants into a table named switch.table.<function> (LLVM 23.1.2).
- GCC 15: GIMPLE has
GIMPLE_COND,GIMPLE_SWITCH,GIMPLE_GOTO,GIMPLE_RETURN(gcc/gimple.def); exceptional edges are CFG edges flaggedEDGE_EH, and a throwing call ends its block, the same constraint LLVM expresses withinvoke. - rustc MIR: terminators are an enum (
TerminatorKind::{Goto, SwitchInt, Return, Unreachable, Call { unwind, .. }, Assert, Drop, …},compiler/rustc_middle/src/mir/syntax.rs); every call has an explicit unwind action.
Find where LLVM does it. In llvm/lib/Transforms/Utils/SimplifyCFG.cpp, find simplifySwitchLookup, which converts a switch into a lookup table. Question: what does the table hold for case values that are not listed when the default is unreachable?
switch, unreachable, and the lookup table they become
Reproduce (clang 23.1.2, opt 23.1.2):
cat > sw.c <<'EOF'
int classify(int op) {
switch (op) {
case 0: return 10;
case 1: return 20;
case 7: return 30;
default: __builtin_unreachable();
}
}
EOF
clang-23 --target=x86_64-unknown-linux-gnu -O0 -Xclang -disable-O0-optnone -S -emit-llvm sw.c -o - \
| opt -passes=mem2reg -S | sed -n '/^define/,/^}/p'
echo ----
clang-23 --target=x86_64-unknown-linux-gnu -O1 -S -emit-llvm sw.c -o - | grep -E "^@|^define|^ [%r]"
Output (complete):
define dso_local i32 @classify(i32 noundef %0) #0 {
switch i32 %0, label %5 [
i32 0, label %2
i32 1, label %3
i32 7, label %4
]
2: ; preds = %1
br label %6
3: ; preds = %1
br label %6
4: ; preds = %1
br label %6
5: ; preds = %1
unreachable
6: ; preds = %4, %3, %2
%.0 = phi i32 [ 10, %2 ], [ 20, %3 ], [ 30, %4 ]
ret i32 %.0
}
----
@switch.table.classify = private unnamed_addr constant [8 x i8] [i8 10, i8 20, i8 poison, i8 poison, i8 poison, i8 poison, i8 poison, i8 30], align 4
define dso_local range(i32 10, 31) i32 @classify(i32 noundef %0) local_unnamed_addr #0 {
%2 = zext nneg i32 %0 to i64
%3 = getelementptr inbounds nuw i8, ptr @switch.table.classify, i64 %2
%4 = load i8, ptr %3, align 1
%5 = zext i8 %4 to i32
ret i32 %5
What to notice: the switch has four successors (Definition 9.3.1) and the join's phi one entry per incoming edge (W4). Because reaching unreachable is UB, -O1 may assume op ∈ {0, 1, 7}: it drops the range check, fills the holes of the table with poison, and even marks the index zext nneg and the result range(i32 10, 31).
invoke, landingpad, resume: a call with two successors
Reproduce (clang++ 23.1.2):
cat > eh.cpp <<'EOF'
struct Guard { ~Guard(); };
int risky(int);
int caller(int x) {
Guard g; // needs a cleanup when risky() throws
try { return risky(x); }
catch (int e) { return -e; }
}
EOF
clang++-23 --target=x86_64-unknown-linux-gnu -O1 -fno-discard-value-names -S -emit-llvm eh.cpp -o - \
| sed -n '/^define/,/^}/p'
Output (complete):
define dso_local noundef i32 @_Z6calleri(i32 noundef %x) local_unnamed_addr #0 personality ptr @__gxx_personality_v0 {
entry:
%g = alloca %struct.Guard, align 1
call void @llvm.lifetime.start.p0(ptr nonnull %g) #5
%call = invoke noundef i32 @_Z5riskyi(i32 noundef %x)
to label %cleanup unwind label %lpad
lpad: ; preds = %entry
%0 = landingpad { ptr, i32 }
cleanup
catch ptr @_ZTIi
%1 = extractvalue { ptr, i32 } %0, 1
%2 = tail call i32 @llvm.eh.typeid.for.p0(ptr nonnull @_ZTIi) #5
%matches = icmp eq i32 %1, %2
br i1 %matches, label %catch, label %ehcleanup
catch: ; preds = %lpad
%3 = extractvalue { ptr, i32 } %0, 0
%4 = tail call ptr @__cxa_begin_catch(ptr %3) #5
%5 = load i32, ptr %4, align 4, !tbaa !9
%sub = sub nsw i32 0, %5
tail call void @__cxa_end_catch() #5
br label %cleanup
cleanup: ; preds = %entry, %catch
%retval.0 = phi i32 [ %sub, %catch ], [ %call, %entry ]
call void @_ZN5GuardD1Ev(ptr noundef nonnull align 1 dereferenceable(1) %g) #5
call void @llvm.lifetime.end.p0(ptr nonnull %g) #5
ret i32 %retval.0
ehcleanup: ; preds = %lpad
call void @_ZN5GuardD1Ev(ptr noundef nonnull align 1 dereferenceable(1) %g) #5
call void @llvm.lifetime.end.p0(ptr nonnull %g) #5
resume { ptr, i32 } %0
}
What to notice: %call is used in the phi only on the edge from %entry, the invoke's normal edge: on the unwind edge it was never computed (the "When it breaks" remark of Section 4). The landing pad says what it handles (cleanup, catch ptr @_ZTIi), dispatches on the selector, and either catches or runs the destructor and resumes unwinding. The function carries a personality (W7). Lab task E8 writes a smaller version by hand.
indirectbr and callbr from computed goto and asm goto
Reproduce (clang 23.1.2):
cat > jumps.c <<'EOF'
int interp(const unsigned char *pc) {
static void *table[] = { &&op_inc, &&op_halt };
int acc = 0;
goto *table[*pc];
op_inc:
acc++; pc++; goto *table[*pc];
op_halt:
return acc;
}
int flag(int x) {
asm goto("testl %0, %0; jz %l[zero]" :: "r"(x) :: zero);
return 1;
zero:
return 0;
}
EOF
clang-23 --target=x86_64-unknown-linux-gnu -O1 -S -emit-llvm jumps.c -o - | grep -E "indirectbr|callbr|blockaddress"
Output (complete):
@interp.table = internal unnamed_addr constant [2 x ptr] [ptr blockaddress(@interp, %2), ptr blockaddress(@interp, %5)], align 16
indirectbr ptr %12, [label %2, label %5]
callbr void asm sideeffect "testl $0, $0; jz ${1:l}", "r,!i,~{dirflag},~{fpsr},~{flags}"(i32 %0) #2
What to notice: indirectbr lists every block it may reach, so the CFG stays exact even for a computed jump; the targets' addresses are blockaddress constants. callbr makes inline assembly a terminator with an extra (!i) successor.
Phi and select¶
LLVM
llvm/include/llvm/IR/Instructions.h — PHINode (incoming values and blocks stored in parallel arrays, getIncomingValueForBlock) and SelectInst; llvm/lib/Transforms/Utils/SimplifyCFG.cpp — foldTwoEntryPHINode and SimplifyCFGOpt::speculativelyExecuteBB turn small diamonds and triangles into select (Proposition 9.3.10) (LLVM 23.1.2).
- GCC 15:
GIMPLE_PHInodes (# s_5 = PHI <s_15(4), s_11(5)>in Lesson 9.8's dump) andCOND_EXPRfor selects; the if-conversion pass istree-ssa-phiopt.cc. - Cranelift 37: no phis;
selectexists as an instruction, and block parameters carry merges (cranelift/codegen/src/ir/dfg.rs).
Find where LLVM does it. In llvm/lib/Transforms/Utils/SimplifyCFG.cpp, find SimplifyCFGOpt::speculativelyExecuteBB. Question: which name does it give the select instructions it creates (visible in the box below)?
simplifycfg speculates an add nsw and merges with select
Reproduce (clang 23.1.2, opt 23.1.2):
cat > sum_pos.c <<'EOF'
long long sum_pos(const long long *a, long long n) {
long long s = 0;
for (long long i = 0; i < n; i++)
if (a[i] > 0)
s += a[i];
return s;
}
EOF
clang-23 --target=x86_64-unknown-linux-gnu -O0 -Xclang -disable-O0-optnone -fno-discard-value-names \
-S -emit-llvm sum_pos.c -o sum_pos.ll
opt -passes='mem2reg,early-cse,simplifycfg' -S sum_pos.ll | sed -n '/^for.body/,/^for.end/p'
opt -passes='mem2reg,early-cse,simplifycfg,instcombine' -S sum_pos.ll | grep -E "call i64 @llvm.smax|spec.select ="
Output (complete):
for.body: ; preds = %for.cond
%arrayidx = getelementptr inbounds i64, ptr %a, i64 %i.0
%0 = load i64, ptr %arrayidx, align 8
%cmp1 = icmp sgt i64 %0, 0
%add = add nsw i64 %s.0, %0
%spec.select = select i1 %cmp1, i64 %add, i64 %s.0
%inc = add nsw i64 %i.0, 1
br label %for.cond, !llvm.loop !5
for.end: ; preds = %for.cond
%add = call i64 @llvm.smax.i64(i64 %0, i64 0)
%spec.select = add nuw nsw i64 %s.0, %add
What to notice: early-cse removed the second load of a[i], which made if.then speculatable; simplifycfg then hoisted %add = add nsw … (executed now even when a[i] ≤ 0, where it may be poison) and replaced the phi by a select that never chooses the poison (Proposition 9.3.10). instcombine rewrote s + (a[i] > 0 ? a[i] : 0) as s + smax(a[i], 0), the form in clang's -O2 output.
The verifier's invariants¶
LLVM
llvm/lib/IR/Verifier.cpp — Verifier::visitFunction (W2: "Entry block to function must not have predecessors!"), Verifier::visitBasicBlock (W4: "PHINode should have one entry for each predecessor…", "PHI node entries do not match predecessors!"), Verifier::visitPHINode (W3), Verifier::visitInstruction (self-reference), Verifier::verifyDominatesUse (W6: "Instruction does not dominate all uses!") (LLVM 23.1.2) [LLVM-Verifier].
- GCC 15:
verify_ssa(gcc/tree-ssa.cc) checks that every SSA name's definition dominates its uses and that PHI arguments match the incoming edges;verify_gimple_in_cfg(gcc/tree-cfg.cc) checks statement types, run with-fchecking. - Swift SIL:
SILVerifier(lib/SIL/Verifier/SILVerifier.cpp) checks the same dominance rule for block arguments plus ownership rules.
Find where LLVM does it. In llvm/lib/IR/Verifier.cpp, find the message "PHI node has multiple entries for the same basic block with different incoming values!". Question: which W-rule of Definition 9.3.4 does it enforce?
Phi entries are per edge, not per block
Reproduce (opt 23.1.2):
cat > dup.ll <<'EOF'
define i32 @f(i32 %x) {
entry:
switch i32 %x, label %other [ i32 1, label %join
i32 2, label %join ]
other:
br label %join
join:
%r = phi i32 [ 10, %entry ], [ 20, %other ]
ret i32 %r
}
EOF
opt -passes=verify -disable-output dup.ll
sed 's/\[ 10, %entry \], \[ 20, %other \]/[ 10, %entry ], [ 11, %entry ], [ 20, %other ]/' dup.ll > dup2.ll
opt -passes=verify -disable-output dup2.ll
sed 's/\[ 10, %entry \], \[ 20, %other \]/[ 10, %entry ], [ 10, %entry ], [ 20, %other ]/' dup.ll > dup3.ll
opt -passes=verify -disable-output dup3.ll && echo "dup3.ll verifies"
Output (complete):
PHINode should have one entry for each predecessor of its parent basic block!
%r = phi i32 [ 10, %entry ], [ 20, %other ]
opt: dup.ll: error: input module is broken!
PHI node has multiple entries for the same basic block with different incoming values!
%r = phi i32 [ 10, %entry ], [ 11, %entry ], [ 20, %other ]
label %entry
i32 11
i32 10
opt: dup2.ll: error: input module is broken!
dup3.ll verifies
What to notice: the switch reaches %join along two edges, so the phi needs two entries for %entry (W4 counts with multiplicity), and they must agree because one block cannot pass two different values to the same phi. Block arguments (Lesson 9.8) lift exactly this restriction.
8. Comparison¶
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Terminators | exact CFG, including computed jumps (indirectbr), unwinding (invoke) and asm goto (callbr) |
successor lists \(O(1)\) per block | explicit edges; unreachable enables deletion |
moderate; EH adds several instructions | every function; invoke for C++/Rust unwinding |
| Phi and select | phi: merges at joins, one entry per edge; select: branch-free choice that ignores unchosen poison | phi check \(O(\text{operands})\); select is one instruction | phi entries must match predecessors exactly | phi bookkeeping on every CFG edit | phis at joins; selects after if-conversion, cmov |
| The verifier's invariants | W1–W7, with the SSA dominance property | \(O(i + u + T_{\mathrm{dom}})\) | the offending instruction printed with a message | ~8 000 lines (Verifier.cpp) |
parser, opt, every pass in debug builds |
Choose invoke for any call that may unwind to a handler in the same function; a plain call in a function with no handler just unwinds through. Choose select when both values are cheap and speculatable; keep the branch when one arm is expensive or has side effects. Run the verifier after every transformation you write (Chapter 12's test harness does it for you): its messages point at the rule (W1–W7) you broke.
9. Assessment¶
| Technique | Quiz ids (solutions/quizzes/ch09.yaml) |
Drill | Flashcard tag | Exercises |
|---|---|---|---|---|
| Terminators | switch-successors, invoke-normal-edge, find-switch-table |
./course drill ir-validity (missing terminators) |
terminators |
E4, E7, E8 |
| Phi and select | phi-parallel, select-poison, branch-to-select |
./course drill poison-propagation (select) |
phi-select |
E1, E2, F2, F3 |
| The verifier's invariants | verifier-rule-of-error, dominance-use, find-phi-dup-check |
./course drill ir-validity --difficulty hard |
verifier |
F1–F7 |
A phi reads its operand at the end of the predecessor, not at the phi
In %x = phi i64 [ %v, %p ], %v need not dominate the phi's block, only the end of %p. A value defined in the loop body can feed the header's phi on the back edge; the same value cannot be used by a non-phi instruction in the header.
References¶
See the chapter references.