Between the AST and machine code sits the IR — the data structure the optimiser actually works on. We tour the spectrum from tree-like HIR to machine-near LIR, the linear and graph forms (three-address code, bytecode, the control-flow graph), and the idea that powers every modern compiler: Static Single Assignment, dominance and the φ-function.
An IR is the compiler's working representation — produced from the AST, optimised, then lowered to a target. This deck covers what makes a good IR and the major families in use today.
You could walk the AST and emit machine code directly — some toy compilers do. But the AST is shaped by the source language, and machine code by the target. An intermediate representation is a deliberately neutral middle form: a data structure designed for analysis and transformation, not for humans and not for a CPU.
These pull against each other. A high-level IR is easy to produce but hard to optimise for machines; a low-level IR is easy to lower but has lost source structure. Real compilers resolve this by using several IRs at different levels — lowering progressively.
Above all, an IR is the representation the middle end rewrites. Every optimisation in Part 07 — constant folding, CSE, dead-code elimination, loop-invariant code motion — is a transformation on the IR. Its design dictates which analyses are cheap and which are awkward.
The decisive reason for a stable, shared IR is reuse. With N source languages and M targets, route everything through one IR and you need N + M halves, not N × M whole compilers. The IR is the narrow waist — and crucially, the optimiser written once serves all N×M combinations.
Beyond reuse, a shared IR is a contract: front-end and back-end teams can evolve independently as long as both honour the IR's semantics. This is why LLVM IR, JVM bytecode and Wasm are ecosystems, not single programs.
IRs vary in level — how close they sit to the source vs the machine. Modern compilers use several, lowering step by step: each level discards source abstraction and exposes more machine detail, enabling different optimisations.
| Compiler | High-level IR | Mid-level IR | Low-level IR |
|---|---|---|---|
| Rust (rustc) | HIR (desugared AST) | MIR (CFG, borrow-check) | LLVM IR → codegen |
| Swift | AST | SIL (Swift IL, SSA) | LLVM IR |
| V8 (JS) | AST / bytecode (Ignition) | Turbofan sea-of-nodes | machine code |
Three-address code (TAC) is the canonical mid-level linear IR. Each instruction has at most one operator and (up to) three operands — a result and two sources: t = a op b. Complex expressions are broken into a sequence using compiler-generated temporaries (t1, t2…), which makes every sub-computation explicit and addressable.
source: x = (a + b) * (a + b) - c;
three-address code:
t1 = a + b
t2 = a + b
t3 = t1 * t2
t4 = t3 - c
x = t4
after common-subexpression elimination:
t1 = a + b
t3 = t1 * t1
x = t3 - cAt most three names per instruction. Control flow is explicit too — goto L, if x < y goto L, param/call. It maps cleanly onto a CFG.
Each holds one intermediate value. They are virtual — unbounded in number; the register allocator (Part 08) later maps them onto finite physical registers.
Tree-walking obscures sharing and ordering. Flattening to a list of simple instructions makes data dependencies and evaluation order plain — exactly what analyses need.
How is each TAC instruction stored? Three classic encodings trade memory against ease of reordering. For t1 = b * 2; t2 = a + t1:
(op, arg1, arg2, result) — the result is a named field.
op a1 a2 res
0 * b 2 t1
1 + a t1 t2Explicit result names → instructions move freely. Most common in practice.
(op, arg1, arg2) — no result field; the result is the row index, referenced as (i).
op a1 a2
(0) * b 2
(1) + a (0)Compact — no temporaries stored. But moving a row renumbers every reference.
A list of pointers into a triple table. Reorder by shuffling the pointer list; the triples stay put.
order: (0)(1)
(0) * b 2
(1) + a (0)Best of both: compact and reorderable — the classic optimising-compiler choice.
The lesson generalises: a result that is a stable name (quad) is easier to move than one that is a position (triple). SSA, later, takes naming to its logical extreme — every value gets a unique name forever.
Many IRs target a virtual machine rather than analysis. Stack bytecode has no named operands at all: instructions push and pop an operand stack. 2 + 3 becomes push 2, push 3, add. It is trivially easy to generate from an AST (a post-order walk) and extremely compact.
JVM bytecode for a + b * 2 (ints in locals 1, 2):
iload_1 ; push a
iload_2 ; push b
iconst_2 ; push 2
imul ; pop 2,b push b*2
iadd ; pop b*2,a push a+(b*2)CPython bytecode (dis of a + b * 2):
LOAD_FAST a
LOAD_FAST b
LOAD_CONST 2
BINARY_OP * (5)
BINARY_OP + (0)JVM, CPython (.pyc), WebAssembly, the CLR. Compact, portable, easy to verify — ideal as a distribution format.
Stack VMs are easy to generate but execute many tiny instructions. Register bytecode uses a flat array of virtual registers instead of a stack, so one instruction can name its operands directly — fewer instructions, fewer dispatches, faster interpretation. Lua 5 and Android's Dalvik pioneered this for production VMs.
Stack (Wasm-style) for x = a + b * 2:
local.get a
local.get b
i32.const 2
i32.mul
i32.add
local.set x ; 6 instructionsRegister (Lua-style) — R are registers:
MUL R3 Rb K2 ; R3 = b * 2
ADD Rx Ra R3 ; Rx = a + R3
; 2 instructions| Axis | Stack VM | Register VM |
|---|---|---|
| Operands | implicit (the stack) | explicit (register #) |
| Instr. count | more (push/pop) | fewer |
| Instr. size | small | larger (operand fields) |
| Codegen | trivial (post-order) | needs register assignment |
| Dispatch cost | higher (more ops) | lower |
| Examples | JVM, CPython, Wasm, CLR | Lua 5, Dalvik, BEAM-ish |
Stack code is smaller and simpler to produce; register code is faster to interpret (fewer dispatches dominate). Distribution formats (Wasm, JVM) favour stack; embedded interpreters (Lua) favour registers.
Optimisation needs structure linear code hides. The control-flow graph (CFG) is a directed graph whose nodes are basic blocks — maximal straight-line instruction sequences — and whose edges are possible transfers of control. Control enters a block only at its top and leaves only at its bottom.
A maximal run of instructions with one entry (the first) and one exit (the last). No branch lands in the middle; no branch leaves before the end.
An edge B→C means control can pass from B to C. A conditional branch gives two successors; a fall-through or jump gives one.
An edge to a block that dominates its source (B2→B1) is a back edge — the signature of a loop. Loops are found from the CFG, not the source syntax.
Given a linear instruction list, the CFG is built by identifying leaders — the first instruction of each block. A block runs from a leader up to (but not including) the next leader.
Each leader begins a basic block containing it and all following instructions up to the next leader or the end. Add a CFG edge for each fall-through and each branch target.
i = 0 ; L1: leader (first)
L2: t = i < n ; leader (branch target)
if !t goto L4 ;
s = s + a[i] ; L3: leader (after branch)
i = i + 1
goto L2 ;
L4: return s ; leader (branch target)
leaders: {1, 2, 4, 7}
blocks:
B0 = [i=0] → B1
B1 = [t=i<n, if !t goto L4] → B2, B3
B2 = [s=s+a[i], i=i+1, goto L2] → B1
B3 = [return s]This three-rule algorithm is linear in the instruction count and is the foundation under every later analysis — liveness, reaching definitions, dominance and SSA all operate on the CFG it produces.
A node d dominates node n (written d dom n) if every path from the entry to n passes through d. Dominance is reflexive (n dom n) and transitive. It is the backbone of loop detection and SSA construction.
idom(n)The unique closest strict dominator of n — the last dominator before n on every path. Every node except entry has exactly one idom, so the idom relation forms a tree rooted at entry.
D is reached via A→B→D and A→C→D. Neither B nor C is on every path, so neither dominates D. Only A does — so idom(D)=A.
Iterative dataflow (Cooper–Harvey–Kennedy, 2001) is simple and fast in practice; Lengauer–Tarjan (1979) is near-linear. Both yield the dominator tree.
The dominance frontier of node n, DF(n), is the set of nodes that n almost dominates: nodes where n's dominance "runs out". Formally, DF(n) is the set of nodes y such that n dominates a predecessor of y but does not strictly dominate y itself. It is precisely where merging happens — and exactly where SSA must insert φ-functions.
Start at n and walk forward. As long as you stay in n's dominated region, no merge is needed. The frontier is the first set of join points reachable from n where control could also have arrived without going through n — so a value defined in n may or may not be live.
If a variable is assigned in block n, then any use that could see either n's value or another definition needs a φ to reconcile them. Those merge points are exactly DF(n). This is the key insight of Cytron et al. (1991) for placing φ-functions optimally.
Block D is a join of the B and C paths. DF(B) = {D} and DF(C) = {D}: B dominates itself (a predecessor of D) but does not dominate D (you can reach D via C). So a variable assigned in B and in C forces a φ at D — which is precisely what the next slides build.
SSA form imposes one rule: every variable is assigned exactly once, statically. Reassignments become fresh, subscripted names — x → x₁, x₂, …. The payoff is that every name has a single, unambiguous definition, so def–use chains are explicit and free: to find a value's definition you just read its name.
original: SSA:
x = 1 x₁ = 1
x = x + 1 x₂ = x₁ + 1
y = x * 2 y₁ = x₂ * 2What name does a variable have after two branches that each assigned it? Straight-line renaming can't answer — control could arrive from either side. SSA's answer is the φ-function.
x₃ = φ(x₁, x₂) at a join block selects the value corresponding to the predecessor through which control arrived. It is a notional, parallel, edge-indexed copy — not a real instruction the CPU runs.
Introduced by Cytron, Ferrante, Rosen, Wegman & Zadeck at IBM (1991). Now the standard mid-level form: LLVM, GCC, V8, HotSpot, Swift SIL.
A diamond: x is assigned on both arms of an if, then used after the merge. Renaming alone produces two names; the join block needs a φ to pick the right one per incoming edge.
The φ reads x₁ if control came via the left edge, x₂ via the right — a value parameterised by the incoming CFG edge. The merge block here is the dominance frontier of both arms.
The classic algorithm builds minimal SSA — the fewest φ-functions that satisfy the single-assignment property — in two phases, driven by the dominator tree and dominance frontiers.
DF(n) for every blockA φ for v is needed exactly where two definitions of v converge — the join points just outside a definition's dominated region. That set is the dominance frontier. Iterating it accounts for φs creating new definitions.
Minimal SSA may place φs for variables that are dead at the join. Pruned SSA adds a liveness check so a φ is inserted only if v is live there — fewer φs, more analysis.
Braun et al. (2013) construct SSA directly during IR generation, on the fly, without a separate dominance-frontier pass — used by libFirm and others.
Hardware has no φ. Before code generation the compiler must leave SSA, replacing each φ with ordinary copies on the incoming edges. Done naively this is buggy — two classic hazards lurk.
Naively inserting a copy x = x₁ at the end of a predecessor can be clobbered if that block has other successors or the value of x₁ is overwritten before the copy along a critical edge. The copy's value is "lost".
A critical edge goes from a block with multiple successors to one with multiple predecessors. Insert a new empty block on it to host the copy safely.
Parallel φs like a₂=φ(a₁,b₁), b₂=φ(b₁,a₁) swap two values. Sequentialised carelessly — a=b; b=a — the first copy destroys the value the second needs.
All φs in a block execute simultaneously. Lower them as a parallel copy, then sequentialise with a temporary to break cycles (t=a; a=b; b=t). Sreedhar et al. (1999) and Boissinot et al. (2009) give correct, efficient methods.
Both hazards share a root cause: a φ is a parallel, edge-placed operation, and turning it into sequential, block-placed copies must preserve those two properties. Get either wrong and the program miscompiles silently.
LLVM IR (Lattner, 2003) is the most widely used production IR. It is typed, in SSA form, and organised as a strict containment hierarchy. Virtual registers (%name) are SSA values — assigned once, infinite in number.
Module → Function → Basic Block → Instruction. Every block ends in exactly one terminator (br, ret, switch…).
Every value carries a type (i32, i8*, double, {i32,i8}). %x are virtual registers (SSA); @g are globals. Verifier enforces both.
getelementptr — type-safe address arithmetic, never dereferencesphi — the SSA φ-functionbr — conditional / unconditional branchcall + intrinsics (@llvm.memcpy…).ll SnippetIterative factorial, lowered to LLVM IR. Note the SSA virtual registers, the explicit basic blocks, the loop phi nodes selecting per predecessor, and the typed conditional branch.
define i32 @fact(i32 %n) {
entry:
br label %loop
loop:
%i = phi i32 [ 1, %entry ], [ %i.next, %loop ]
%acc = phi i32 [ 1, %entry ], [ %acc.next, %loop ]
%acc.next = mul i32 %acc, %i
%i.next = add i32 %i, 1
%cond = icmp sle i32 %i.next, %n
br i1 %cond, label %loop, label %done
done:
ret i32 %acc.next
}%i / %acc are loop-carried — each phi picks the entry value first, the updated value on later iterationsicmp sle → an i1 (signed ≤)br i1 %cond, A, B — typed two-way terminatorAll three encode the same IR; llvm-as / llvm-dis convert losslessly between text and bitcode.
A functional IR where every call passes an explicit continuation — "what to do next" as a function. Control flow becomes function application; there is no implicit return.
; direct: z = f(x) + 1
; CPS:
f(x, k) where
k(r) = { z = r + 1; ... }SSA ≡ CPS: Appel and Kelsey showed they are essentially the same idea — a φ corresponds to a continuation's parameter, dominance to lexical scope. Used by SML/NJ, MLton, and the Scheme/ML world.
Cliff Click's IR (1995) where control and data are one graph. Nodes are operations; edges are data and control dependencies. Instructions are not pinned to blocks — only ordering constraints exist, so the scheduler places them late, freely floating to better positions.
Cost: harder to read, debug and serialise than a block-structured IR — V8 has since moved parts toward a more conventional CFG IR (Maglev/Turboshaft).
"Multi-Level IR" — not one IR but a framework for defining IRs. Its core abstraction is the dialect: a namespaced set of operations and types. One module can mix dialects (linalg, affine, gpu, llvm) and lower progressively between them.
Why it exists: every domain (tensors, hardware, polyhedral) was reinventing IR plumbing. MLIR makes the levels first-class and composable.
GCC's mid-level IR: a three-address, tree-based form in SSA. The front ends lower to GENERIC, then to GIMPLE, on which most machine-independent optimisation runs.
Register Transfer Language — GCC's low-level IR, close to the machine: virtual then physical registers, addressing modes, machine patterns. Instruction selection, scheduling and register allocation happen here.
GENERIC → GIMPLE (SSA, target-neutral) → RTL (target-near). The same progressive-lowering pattern as rustc's HIR/MIR/LLVM and Swift's AST/SIL/LLVM.
A final side-by-side for x = a + b * 2: the same computation as stack bytecode (implicit operands, more instructions) and as three-address code (explicit temporaries, named results). Different IRs answer different questions.
Stack form is built for generation & transport; three-address form is built for analysis & optimisation. SSA refines the latter further by making every name unique.
There is no universally best IR. Three axes dominate the design space, and real compilers pick a different point on each — often using several IRs to get the best of each.
Match the IR to the work: tree/HIR for source-level checks; SSA + CFG (MIR) for machine-independent optimisation; low-level IR for register allocation and scheduling. Make each transformation's job local and the right facts cheap to read — that is the whole art of IR design.
t = a op b; quads / triples / indirect triples encode itOptimization — the transformations the IR was built for: constant folding, CSE, dead-code elimination, loop-invariant code motion, GVN, and how SSA & dataflow make them tractable.