Chapter 8 · The Design Space of Intermediate Representations¶

Part 2 · Intermediate Representations & LLVM · about 2–3 weeks · Previous: Ch 7 · Next: Ch 9

The problem¶

Between the syntax tree and machine code, a compiler represents the program in one or more intermediate representations (IRs): a set of programs, a well-formedness predicate every pass may assume, and a semantics (Definition 8.1.1). This chapter maps the design space. Given a program, how should its operations name their operands (implicit stack slots, registers, named temporaries, SSA values, graph edges, let-bound variables)? How should control flow be represented (jumps in a list, a CFG of basic blocks, control nodes in a graph, regions, continuations)? How should values be merged at joins (mutable variables, phi functions, block arguments, join-point parameters)? Every choice makes some transformations easy and others hard, and real compilers use several IRs in a row. The chapter's single running example, the sum of the multiples of 3 or 5 up to 10, appears in every one of them, in the lab's four forms and in Clang, GCC, rustc, the JVM, Wasm, CPython, Lua, V8, MLIR, Cranelift, GHC and Chicken Scheme. The Pebble compiler you build uses the tree AST, then PIR (a MIR/SIL-style CFG over typed locals), then LLVM IR (phi-SSA).

What you will be able to do¶

Translate a program by hand and by code into stack bytecode, three-address code (quadruples, triples, indirect triples), A-normal form and block-argument SSA, and predict their sizes (Lessons 8.1, 8.4, 8.6; lab L1).
Verify stack code by height consistency and translate it to register code (Theorems 8.1.12, 8.1.15).
Compute leaders, basic blocks, the CFG, critical edges, DFS preorder, postorder and RPO of a listing, split critical edges, and prove that RPO orders every non-back edge forward (Theorem 8.2.14; lab L2; drills leaders, traversal-orders).
Build an expression DAG by local value numbering and explain the kill rule (drill value-numbering).
Convert between phi functions and block arguments, and state exactly when they differ (Theorem 8.4.10, Lemma 8.4.11; drill phi-to-block-args).
Explain sea of nodes and global code motion, PDG/VSDG/RVSDG and e-graphs, and why V8 moved from a sea of nodes back to a CFG.
CPS-convert and A-normalize an expression, and prove that strict SSA and well-scoped ANF are the same thing (Theorem 8.6.12; drill tac-to-anf).
Read the IR dumps of Clang, rustc, GCC, MLIR and Cranelift, and write PIR by hand (exercise P1).

Prerequisites: Ch 0 (Tiny, stack machines, pipeline shapes). Lessons 8.4–8.6 use dominance from Ch 15, Lesson 15.1 (only the definition and the dominator tree) and Lesson 8.5 uses post-dominance (Lesson 15.4). If you follow the chapters in order, read those two definitions when you reach them.

Notation¶

Shared notation follows the house notation (§1 sets and logic, §3 graphs, §4 dominance, §6 semantics, §7 SSA and IR, §8 complexity). In this chapter:

Symbol	Meaning
\((\mathcal{L}, \mathrm{WF}, [\![\cdot]\!])\)	an IR: programs, well-formedness predicate, semantics (Definition 8.1.1)
\(c_0 \dots c_{n-1}\)	a listing of \(n\) instructions (TAC or stack code); positions from 0 (Definition 8.1.2)
\(a, b\)	atoms: a variable or a 64-bit integer constant (Definition 8.1.2)
\((\mathit{op}, \mathit{arg}_1, \mathit{arg}_2, \mathit{result})\); \((k)\); \(\pi\)	a quadruple; a triple reference to position \(k\); the execution order of indirect triples (Definition 8.1.3)
\(\delta(c)\), \(\rho(c)\), \(h\)	stack effect and requirement of an instruction; a height assignment (Definition 8.1.5)
\(T(i)\)	the jump targets of instruction \(i\) (Definition 8.2.1)
\(\ell_k\), \(B_k = [\ell_k, e_k]\)	the \(k\)-th leader and basic block (Algorithm 8.2.3)
\(G = (N, E, r)\), \(\mathrm{succs}\), \(\mathrm{preds}\)	the CFG with entry \(r\) and ordered successor lists (Definition 8.2.4; NOTATION §3)
\(\mathrm{pre}(v)\), \(\mathrm{post}(v)\), \(\mathrm{rpo}(v)\), \(T\), \(u \preceq_T v\)	DFS numbers, DFS tree and ancestor relation (Definition 8.2.7)
\(\mathrm{VN}(i)\), \(\kappa\)	value number of instruction \(i\); a value-numbering key \((\mathit{op}, n_1, n_2)\) (Definition 8.3.4)
\(x = \phi([a_1, P_1], \dots)\)	a phi function with one entry per predecessor (Definition 8.4.2)
\(B(p_1, \dots, p_k)\), `br B(a_1, …)`	a block with parameters; a branch with arguments (Definition 8.4.4)
S0–S4	the lab's SSA validity rules (Definition 8.4.4)
\(\mathcal{D}\), \(\mathrm{idom}\), \(\mathrm{dom}\)	dominator tree, immediate dominator, dominance (NOTATION §4; Ch 15)
\(\mathrm{early}(x)\), \(\mathrm{late}(x)\), \(\mathrm{blk}(x)\)	GCM's earliest, latest and chosen block of a floating node (Algorithm 8.5.3)
\(\gamma\), \(\theta\)	RVSDG conditional and loop nodes (Definition 8.5.5)
\(\mathrm{find}(c)\)	the canonical e-class id in an e-graph (Definition 8.5.7)
\(\mathcal{C}[\![e]\!]\,\kappa\), \(K\)	CPS transform of \(e\) with continuation \(\kappa\); a meta-level continuation (Definition 8.6.2, Algorithm 8.6.3)
\(K(B)\)	the Kelsey term of block \(B\) (Definition 8.6.6)

Technique map¶

Family	Techniques (origin)	Lesson
Linear IRs	three-address code: quadruples, triples, indirect triples (FORTRAN-era compilers; [Dragon2, §6.2]); stack bytecode (P-code; JVM 1995; CPython; WebAssembly, Haas et al. 2017); register bytecode (Lua 5.0, Ierusalimschy et al. 2005; Dalvik; V8 Ignition; Shi et al. 2005)	8.1
Mechanics	basic blocks and the leaders algorithm (Allen 1970); control-flow graphs and critical edges and their splitting; depth-first orders: preorder, postorder, reverse postorder (Tarjan 1972)	8.2
Trees and DAGs	abstract syntax trees and HIR (rustc HIR/THIR, Clang AST); expression DAGs by value numbering (Ershov 1958; Cocke–Schwartz 1970)	8.3
CFG + SSA	phi-SSA (Alpern–Wegman–Zadeck, Rosen–Wegman–Zadeck 1988; Cytron et al. 1991; LLVM, GCC GIMPLE); block arguments (Swift SIL, MLIR, Cranelift) and their exact correspondence to phi	8.4
Graph IRs	sea of nodes (Click–Paleczny 1995; HotSpot C2, Graal, V8 TurboFan) and why V8 moved to Turboshaft (2025); PDG (Ferrante–Ottenstein–Warren 1987), VSDG (Johnson–Mycroft 2003), RVSDG (Reissmann et al. 2020); e-graphs as an IR (Nelson–Oppen 1980; Tate et al. 2009; egg, Willsey et al. 2021; Cranelift aegraph)	8.5
Functional IRs	CPS (Plotkin 1975; Steele 1978; Appel 1992; Danvy–Filinski 1992); ANF (Flanagan–Sabry–Duba–Felleisen 1993; join points: Kennedy 2007, Maurer et al. 2017); SSA as functional programming (Kelsey 1995; Appel 1998)	8.6
Multi-level IRs and case studies	MLIR dialects and progressive lowering (Lattner et al. 2021); production pipelines: Clang (AST → ClangIR → LLVM IR), rustc (HIR → THIR → MIR), swiftc (AST → SIL → LLVM IR), GCC (GENERIC → GIMPLE → RTL); PIR, the course's MIR/SIL-style IR	8.7

flowchart LR
  subgraph Linear[Linear]
    TAC[TAC / quadruples<br/>Dragon §6.2] --> TRI[triples, indirect triples]
    STK[stack bytecode<br/>JVM, Wasm, CPython] -->|Alg. 8.1.9| REG[register bytecode<br/>Lua 5, Dalvik, Ignition]
  end
  subgraph Graph[Graphs]
    AST[AST / HIR] -->|value numbering| DAG[expression DAG]
    TAC -->|leaders| CFG[CFG of basic blocks]
    CFG -->|rename| SSA[phi-SSA<br/>Cytron 1991]
    SSA <-->|Thm 8.4.10| BA[block arguments<br/>SIL, MLIR, Cranelift]
    SSA -->|drop block order| SON[sea of nodes<br/>Click 1995]
    SSA -->|drop control flow| PDG[PDG / VSDG / RVSDG]
    DAG -->|many terms per class| EG[e-graphs<br/>egg 2021]
  end
  subgraph Fun[Functional]
    CPS[CPS<br/>Plotkin 1975] -->|admin. reduction| ANF[ANF + join points<br/>Flanagan 1993]
  end
  BA <-->|Thm 8.6.12, Kelsey 1995| ANF
  BA --> MLIR[MLIR dialects<br/>2021]
  SON -->|V8 2025| CFG

Read the diagram left to right as "less order, more structure": linear code fixes the order of everything, a CFG fixes order only inside blocks, SSA names every value, the sea of nodes and dependence graphs keep only the dependences, and e-graphs keep many equivalent programs at once. The functional column is the same point as block-argument SSA, seen through lexical scope.

Who uses what¶

System	IRs (in pipeline order)	Where in this chapter
LLVM 23 / Clang	Clang AST → (ClangIR, optional) → LLVM IR (TAC + phi-SSA) → SelectionDAG (DAG per block) → MIR	Lessons 8.2 (`break-crit-edges`, RPO), 8.3 (AST, EarlyCSE), 8.4 (phis), 8.7
GCC 14/15	GENERIC → GIMPLE (TAC) → GIMPLE SSA → RTL	Lessons 8.1, 8.2 (`make_blocks`), 8.4, 8.7
rustc 1.94	AST → HIR → THIR → MIR (CFG of locals, explicit checks) → LLVM IR	Lessons 8.3 (HIR), 8.7 (MIR)
swiftc 6.1	AST → SIL (block arguments, ownership) → LLVM IR	Lessons 8.2, 8.4, 8.7 (SIL docs)
HotSpot / JVM 21	stack bytecode (verified) → C1, C2 (sea of nodes)	Lessons 8.1 (`javap`), 8.5 (C2 GCM)
V8 12.4 (Node 22)	Ignition register bytecode → TurboFan (sea of nodes) → Turboshaft (CFG)	Lessons 8.1, 8.5
WebAssembly / Wasmtime 37	structured stack code → Cranelift IR (block parameters, aegraph)	Lessons 8.1, 8.4, 8.5
CPython 3.11, Lua 5.4	stack bytecode; register bytecode	Lesson 8.1
MLIR 23	any dialects, lowered progressively (`scf` → `cf` → `llvm`)	Lessons 8.4, 8.7
GHC 9.4, Chicken 5.3, SML/NJ, MLton	Core with join points → CorePrep (ANF); CPS; CPS; SSA with block arguments	Lesson 8.6
pebblec (this course)	Pebble AST → PIR (typed locals, CFG, explicit checks) → LLVM IR	Lesson 8.7, pir-spec

Comparison¶

The rows below are the lessons' §8 tables, gathered in one place (same text as in each lesson).

Lesson 8.1 — Linear IRs: three-address code, stack bytecode and register bytecode

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Three-address code	every value named; any analysis or transformation; order free with quadruples	\(O(\lvert e \rvert)\) generation · 19 instructions / 127 executed steps on the running example	readable dumps (GIMPLE, PIR); names map to source variables	low (Algorithm 8.1.4)	optimizer IRs: GIMPLE, LLVM IR (SSA), PIR, Cranelift
Stack bytecode	implicit operands; needs verification (heights, types) before trust	\(O(\lvert e \rvert)\) generation, \(O(n)\) verification · 37 instructions / 249 steps (about 2× TAC)	compact (1-byte opcodes); verifier errors name the join point	lowest to generate; verifier moderate	distribution and interpretation: JVM, Wasm, CPython, CIL
Register bytecode	explicit operands in a bounded frame	\(O(n)\) from stack code · Lua: 19 instructions, about 47 % fewer executed instructions than stack code [SGBE05]	larger instructions (3 operands); register numbers less readable	moderate (register allocation of temporaries)	interpreters that care about dispatch count: Lua, Dalvik, V8 Ignition

Lesson 8.2 — Basic blocks, control-flow graphs and traversal orders

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Basic blocks and the leaders algorithm	exact: the unique maximal partition (Theorem 8.2.9)	\(O(n)\) · one pass; 19 instructions → 10 blocks on the running example	blocks named by their leaders; unreferenced labels vanish	very low	every compiler that starts from a linear IR (GCC's `make_blocks`, JVM and Wasm JITs)
Control-flow graphs and critical edges	exact successor relation; splitting adds one block per critical edge	\(O(n + e)\) · 3 critical edges, 10 → 13 blocks on the running example	a new block per split edge (`…_crit_edge` in LLVM)	low	every optimizer; splitting before out-of-SSA, PRE, code placement
Depth-first orders	RPO is a topological order modulo back edges (Theorem 8.2.14)	\(\Theta(m + e)\) · linear, explicit stack	three sequences plus an edge classification	low (iterative DFS needs care)	dataflow iteration order, dominators, SSA construction, scheduling

Lesson 8.3 — Trees and DAGs: ASTs, HIR and expression DAGs

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Abstract syntax trees and HIR	full source structure; types and names attached in HIR/THIR	\(O(\lvert t \rvert)\) per pass · tree traversals chase pointers	best diagnostics: source ranges on every node	low (tree) to high (typed HIR with desugaring)	front ends: Clang AST, rustc HIR/THIR, GCC GENERIC, Pebble AST
Expression DAGs and value numbering	shares syntactically equal computations inside a block (Theorem 8.3.8)	\(O(k)\) expected · 15 instructions → 12 nodes, 3 redundant (§3)	a DAG per block; holders say where values live	low (hash table + kill rule)	local CSE (EarlyCSE), SelectionDAG, basic-block code generation

Lesson 8.4 — SSA form: phi functions and block arguments

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

Lesson 8.5 — Graph IRs beyond the CFG: sea of nodes, dependence graphs, e-graphs

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Sea of nodes	code motion and value numbering for free; order only from real dependences	GCM \(O(N d + E)\) · V8 found SoN compile time about 2× that of its CFG replacement [Mer25]	hard to read and debug ("manually/visually inspecting … is hard" [Mer25]); needs a scheduler	high: effect chains, scheduling, deopt state	HotSpot C2, Graal; V8 TurboFan (being replaced by Turboshaft)
Dependence graphs: PDG, VSDG, RVSDG	only true dependences; RVSDG makes DCE, CSE and invariant motion graph operations	PDG \(O(m^2)\) control edges worst · RVSDG linear after restructuring	no CFG to print; needs a CFG reconstruction for code generation	high (restructuring, γ/θ regions)	slicing tools, LLVM's loop DDG, research compilers (jlm)
E-graphs	all rewrites at once, no phase ordering; cheapest-term extraction	exponential worst case; limited by node and iteration limits · the egg example saturates in 4 iterations	explanations (egg can explain why two terms are equal)	moderate with a library (egg), high for a production aegraph	superoptimizers, Herbie, Cranelift's mid-end (aegraph), Ch 17

Lesson 8.6 — Functional IRs: CPS, ANF, and SSA as functional programming

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Continuation-passing style	control fully explicit, including exceptions and call/cc; every call a tail call	\(O(\lvert e \rvert)\) one-pass · administrative redexes if naive	verbose: 68 lines for euler1 in Chicken	moderate (one-pass transform; closure representation for escaping continuations)	Scheme and ML compilers (Chicken, SML/NJ), compiling first-class control
A-normal form	same optimizations as CPS for direct-style programs; with join points, same as a CFG	\(O(\lvert p \rvert(1 + V))\) · lab: 18 nodes, 130 steps on the running example	readable direct style; scoping errors are static ("not in scope")	low (Algorithm 8.6.5)	GHC CorePrep, many functional-language compilers, the lab's `anf`
SSA as functional programming	a bijection: strict SSA ≡ well-scoped ANF (Theorem 8.6.12)	translation \(O(n + m \log m)\) given dominators	lets you use lexical-scope reasoning (and type systems) on SSA	low given a dominator tree	MLton's SSA from CPS, GHC's join points, MLIR/SIL block arguments

Lesson 8.7 — Multi-level IRs and real pipelines: MLIR, Clang, rustc, swiftc, GCC, and PIR

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
MLIR dialects and progressive lowering	any abstraction as a dialect; mixed-level modules	\(O(N)\) per conversion with indexed patterns · two passes for euler1	per-dialect verifiers; partial conversions leave mixed modules	high framework cost, low per dialect	ML and HPC compilers (IREE, Triton), Flang, CIRCT, ClangIR
Pipelines of IRs in production compilers	each analysis at its level (Proposition 8.7.11)	sum of stages · rustc builds MIR per body, lazily	dumps per stage (`-ast-dump`, `--emit=mir`, `-fdump-tree-*`)	high: several IRs, each with a verifier	Clang, rustc, swiftc, GCC
PIR: a MIR-style mid-level IR	typed locals, places, explicit checks; SSA left to the back end	alloca scheme \(O(n)\) + `mem2reg` · gcd: 5 locals → 3 phis	text format with line/column verifier messages (`V15: …`)	low for front ends (print text); the shared back end does SSA	the Pebble compiler; any language front end targeting the course back end

Comparison-lab results (reproduce with build/<preset>/bin/ch08-compare on a build with -DPEBBLE_USE_SOLUTION=ir-forms; the reference solution on the samples and 200 random Tiny programs): relative to stack bytecode, static size is 0.55 (TAC), 0.52 (ANF) and 0.49 (SSA), and executed steps 0.52, 0.51 and 0.50. On the running example: 37/19/18/17 instructions and 249/127/130/127 steps (stack/TAC/ANF/SSA).

Route through this chapter¶

Step	What	Techniques	How it is exercised
1	Lesson 8.1	TAC, stack bytecode, register bytecode	drill `stack-code` (Ch 0); quiz; flashcards
2	Lesson 8.2	leaders, CFGs and critical edges, DFS orders	drills `leaders`, `traversal-orders`; lab L2
3	Lesson 8.3	AST/HIR, expression DAGs	drill `value-numbering`; exercise X1 ★
4	Lesson 8.4	phi-SSA, block arguments	drill `phi-to-block-args`; lab L1 (`ssa`)
5	Lesson 8.5	sea of nodes, PDG/VSDG/RVSDG, e-graphs	quiz; flashcards (Ch 17 implements e-graphs)
6	Lesson 8.6	CPS, ANF, SSA ≡ ANF	drill `tac-to-anf`; lab L1 (`anf`)
7	Lesson 8.7	MLIR, production pipelines, PIR	exercise P1 (PIR by hand)
8	Comparison lab `labs/ch08-forms`	stack vs TAC vs ANF vs block-argument SSA	`./course test 8` + `ch08-compare`
9	Lab `labs/ch08-cfg`	leaders, CFG, orders, critical-edge splitting	`./course test 8`
10	Theory test	all	`./course quiz 8` (≥ 80 % to finish)

Pebble implements none of these IRs in its compiler in this chapter: PIR and its tools are provided (Ch 11 writes the lowering into and out of it). Four IR forms are implemented in the comparison lab, the CFG mechanics in the second lab, and sea of nodes, dependence graphs, e-graphs and CPS are theory + quiz here (e-graphs are implemented in Ch 17).

Practice and check¶

./course drill leaders --difficulty medium            # basic blocks (Lesson 8.2)
./course drill traversal-orders --difficulty easy     # DFS orders (Lesson 8.2)
./course drill value-numbering --difficulty medium    # DAGs (Lesson 8.3)
./course drill phi-to-block-args --difficulty medium  # SSA forms (Lesson 8.4)
./course drill tac-to-anf --difficulty medium         # ANF (Lesson 8.6)
./course drill stack-code --difficulty medium         # stack vs register code (Ch 0, Lesson 8.1)
./course flash 8
./course quiz 8
./course test 8

References¶

The chapter's annotated bibliography, with papers, textbook sections, pinned source files and docs, is in references.md. Start with: [Dragon2, §6.2, §8.4] (TAC and basic blocks), [CFRWZ91] (SSA), [CP95] (sea of nodes), [FSDF93] and [App98] (ANF, and SSA as functional programming), [LAB+21] (MLIR), and [Mer25] for a production team's experience report on IR design.