Chapter 21 · Instruction Selection & the LLVM Code Generator¶

Part 5 · Back End · about 3 weeks · Previous: Ch 20 · Next: Ch 22

The problem¶

You are given optimized IR: for each function, a control-flow graph of basic blocks whose instructions compute values from typed operands (LLVM IR for pebblec, Ch 9). You want an object file: for each function, bytes of machine code for a concrete target (x86-64 and AArch64 in this chapter), with every value in a register or stack slot the target allows, every call following the platform's calling convention, and relocations for every address the linker must fill in. The heart of the problem is instruction selection: cover each block's expression trees or DAGs with the target's instructions ("tiles") at minimum cost, where one IR operation may take several instructions and one instruction may implement several IR operations (ldr x0, [x1, x2, lsl #3] is a shift, an add and a load). Around it sit the rest of LLVM's code generator: legalization (rewrite types and operations the target lacks), scheduling the selected DAG into a list, the target description that all of it is generated from, calling conventions and frame lowering, and the MC layer that encodes, relaxes and relocates. The outputs of this chapter's pipeline are the MachineInstrs that register allocation (Ch 22) and scheduling (Ch 23) consume, and the final .o. In pebblec all of this is LLVM's back end, driven by llc or the TargetMachine API; this chapter teaches you to read it, and the labs build the classic selectors yourself on a toy ISA.

What you will be able to do¶

Tile an expression tree by macro expansion, maximal munch and dynamic programming by hand, and prove that DP is optimum while munch is only optimal (Theorems 21.1.13, 21.1.15 and 21.2.7).
Build the BURS automaton of a small grammar by hand, decide whether a grammar is BURS-finite, and explain what BURG precomputes that iburg recomputes.
Prove that optimal DAG covering is NP-complete and explain how LLVM, NOLTIS and PBQP cope with sharing.
Follow an IR function through SelectionDAG (build, combine, legalize, select, schedule), GlobalISel (IRTranslator, Legalizer, RegBankSelect, InstructionSelect) and FastISel with llc -stop-after, and predict each legalization step.
Read TableGen patterns, GCC define_insns, lburg grammars and ISLE rules, and say which selection algorithm each description feeds.
Assign SysV and AAPCS64 argument locations, lay out a frame, and explain prologue/epilogue insertion and shrink-wrapping.
Explain how an MCInst becomes bytes, why branch relaxation is a fixpoint and when it is optimal, and what each relocation in an ELF, Mach-O or COFF object asks the linker to do.
Implement macro, munch and DP selectors for a toy ISA (★ and a BURG table generator), check them against a simulator and brute force, and measure how they differ.

Prerequisites: Ch 8 (trees, DAGs and e-graphs as IRs), Ch 9 (LLVM IR, types, llc), Ch 13 (peephole optimization and value numbering), Ch 15 (dominators and post-dominators, for shrink-wrapping). Ch 0 Lesson 0.6 introduces object files and linking from the user's side.

Notation¶

Shared notation follows the house notation: §1 (sets, functions, logic) and §3 (graphs). Costs are non-negative integers with \(\infty\) for "impossible". In this chapter:

Symbol	Meaning
\(\Sigma\), \(\mathrm{ar}(o)\)	ranked alphabet of IR operators and the arity of \(o\) (Definition 21.1.1)
\(t\), \(t_v\), \(V(t)\), \(n\)	an expression tree, its subtree at node \(v\), its nodes, \(n = \lvert V(t) \rvert\)
\(G = (N, \Sigma, R, S, c)\)	tile grammar: nonterminals, operators, rules, start nonterminal, rule cost (Definition 21.1.2)
\(r = A \to \pi\), \(\lvert \pi \rvert\)	a rule with pattern \(\pi\); the pattern's number of operator nodes
\(\mathrm{ops}(\pi, v)\), \(\mathrm{cov}(\pi, v)\)	operand nodes and covered nodes of a match (Definition 21.1.3)
\(\mathrm{OPT}(t)\)	the cost of an optimum tiling (Definition 21.1.4), also \(\mathrm{OPT}(D)\) for a DAG
\(C(v, A)\), \(\mathrm{rule}(v, A)\)	label: least cost of deriving \(t_v\) from \(A\), and a rule achieving it (Definition 21.2.1)
\(C_0(v, \cdot)\)	labels before chain closure (Definition 21.2.2)
\(c_r(v)\)	dynamic cost of rule \(r\) at node \(v\) (Definition 21.2.10)
\(\sigma_v\), \(Q(G)\), \(\delta\)	δ-state of node \(v\), the set of all states, the transition function (Definitions 21.3.2–21.3.3)
\(N_{o,i}\), \(\pi_{o,i}\), \(\mu_{o,i}\)	nonterminals at child \(i\) of operator \(o\), projection to representer states, index map (Definition 21.3.9)
\(D = (V, E)\), \(\mathrm{Roots}\)	expression DAG and its required roots (Definition 21.4.1)
\(\omega(n)\)	NOLTIS overlap cost of a shared node (Definition 21.4.8)
\(x_v\), \(\vec{c}_v\), \(M_{vu}\)	PBQP variable, cost vector and edge cost matrix (Definition 21.4.11)
\(y_{v,r}\)	ILP 0/1 variable: rule \(r\) is used at node \(v\) (Definition 21.4.14)
\(\rho = (p_\rho, \ell_\rho, e_\rho)\), \(A(t)\)	ISLE rule with priority, left- and right-hand side; the rules applicable to term \(t\) (Definitions 21.7.1–21.7.2)
\(g\), \(f\), \(\mathit{sp}\)	SysV counters: GPRs and XMM registers used, next stack offset (Algorithm 21.9.2)
NGRN, NSRN, NSAA	AAPCS64's next general-purpose register, next SIMD/FP register, next stacked argument address (Algorithm 21.9.3)
\(U\), \(S\), \(R\)	in Lesson 21.9: blocks using callee-saved registers, save point, restore point (Definition 21.9.9)
\(L\), \(s_j\), \(l_j\), \(\sigma_j(L)\)	in Lesson 21.10: set of long span-dependent instructions, short and long sizes, span of \(j\) (Definition 21.10.5)
\((P, \mathit{type}, S, A)\)	in Lesson 21.10: relocation offset, type, symbol, addend (Definition 21.10.9)

\(S\) and \(\sigma\) are overloaded across lessons as listed; each lesson uses only one meaning. Numbered statements are 21.k.m (chapter, lesson, counter), as in NOTATION.md §9.

Technique map¶

Family	Techniques (origin)	Lesson
Selection approaches	Macro expansion (early compilers; surveyed by Blindell 2016), maximal munch (Cattell 1980; named by Appel 1998), peephole combining (McKeeman 1965; Davidson & Fraser 1980, 1984)	21.1
Optimal tree tiling	Aho–Johnson dynamic programming (Sethi & Ullman 1970; Aho & Johnson 1976), tree-grammar generators: twig (Aho, Ganapathi & Tjiang 1989), iburg (Fraser, Hanson & Proebsting 1992), lburg (Fraser & Hanson 1995)	21.2
Bottom-up rewrite systems	BURS theory (Pelegrí-Llopart & Graham 1988, on Hoffmann & O'Donnell 1982), BURG table generation and compression (Chase 1987; Balachandran, Dhamdhere & Biswas 1990; Fraser, Henry & Proebsting 1992; Proebsting 1992, 1995)	21.3
DAG covering	NP-completeness (Bruno & Sethi 1976; Aho, Johnson & Ullman 1977; Proebsting 1998), tree decomposition and greedy DAG matching (lcc, LLVM), NOLTIS (Koes & Goldstein 2008), PBQP (Eckstein, König & Scholz 2003; Ebner et al. 2008) and ILP formulations	21.4
LLVM's selectors	SelectionDAG: DAG building and combining, type and operation legalization, matcher-table selection, list scheduling (LLVM, from 2005)	21.5
	FastISel (LLVM, 2008), the GlobalISel pipeline and its combiners (LLVM, from 2015; Colombet 2025)	21.6
Other frameworks	ISLE term rewriting (Cranelift, Fallin 2021–2023; verified by Crocus, VanHattum et al. 2024), e-graph-based selection (Denali, Joshi, Nelson & Randall 2002; equality saturation, Tate et al. 2009; egg, Willsey et al. 2021; Cranelift's aegraph, Fallin 2023)	21.7
Target description	LLVM TableGen, GCC machine descriptions (`define_insn`, `recog`), tree-grammar and architecture-description files (lburg, iburg, HotSpot ADL)	21.8
Lowering details	Argument assignment by calling convention (System V psABI, AAPCS64), frame layout and frame lowering, prologue/epilogue insertion and shrink-wrapping (Chow 1988)	21.9
The MC layer	Instruction encoding (`MCInst`, `MCCodeEmitter`), assembly with fragments, fixups and relaxation (Szymanski 1978), relocations and object formats (ELF, Mach-O, COFF)	21.10

flowchart LR
  ME[Macro expansion] -->|look at several nodes| MM[Maximal munch<br/>Cattell 1980]
  ME -->|expand, then combine| PC[Peephole combining<br/>Davidson-Fraser 1980]
  SU[Sethi-Ullman 1970] -->|any tiles, costs| AJ[Aho-Johnson DP 1976]
  MM -->|optimal instead of greedy| AJ
  AJ -->|generated from a grammar| TW[twig 1989]
  TW -->|DP in C, dynamic costs| IB[iburg / lburg 1992-95]
  AJ -->|precompute relative costs| BURS[BURS<br/>Pelegri-Graham 1988]
  HO[Hoffmann-O'Donnell 1982] --> BURS
  BURS -->|table generation| BURG[BURG, Proebsting 1992-95]
  AJ -->|trees to DAGs: NP-complete| DAG[DAG covering]
  DAG -->|cut at shared nodes| TD[tree decomposition]
  DAG -->|fix overlaps| NOL[NOLTIS 2008]
  DAG -->|whole function| PBQP[PBQP / ILP 2003-08]
  MM -->|greedy DAG matching, tables| SD[SelectionDAG]
  TD --> SD
  SD -->|whole function, MIR| GI[GlobalISel]
  ME --> FI[FastISel]
  PC --> ISLE[ISLE rules]
  JNR[Denali 2002, equality saturation 2009] --> EG[e-graph selection / aegraph]
  TG[TableGen] --> SD
  TG --> GI
  SD --> MC[MC layer: encode, relax, relocate]
  GI --> MC
  FI --> MC

The pipeline these techniques sit in, as LLVM runs it:

flowchart LR
  IR[LLVM IR] --> SEL{selector}
  SEL -->|-O1 and up| SD[SelectionDAG<br/>build · combine · legalize · select · schedule]
  SEL -->|-global-isel| GI[GlobalISel<br/>IRTranslator · Legalizer · RegBankSelect · InstructionSelect]
  SEL -->|-O0| FI[FastISel<br/>falls back to SelectionDAG]
  SD --> MIR[SSA MIR]
  GI --> MIR
  FI --> MIR
  MIR --> OPT[machine SSA opts] --> RA[register allocation<br/>Ch 22] --> PEI[prologue/epilogue insertion<br/>shrink-wrapping]
  PEI --> POST[post-RA scheduling<br/>Ch 23] --> AP[AsmPrinter: MCInst]
  AP --> MC[MC: encode · relax · fixups] --> OBJ[ELF / Mach-O / COFF]

Who uses what¶

System	Technique	Notes
LLVM 23	SelectionDAG (greedy DAG matching by pattern complexity, TableGen matcher table) at `-O1` and up on most targets; GlobalISel by default for AArch64 at `-O0`; FastISel at `-O0` on x86; TableGen descriptions; MC integrated assembler	Lessons 21.5, 21.6, 21.8, 21.10
GCC 15	Macro expansion to RTL (`define_expand`), then combining (`combine.cc`) checked by the generated recognizer `recog` from `define_insn` patterns	Lessons 21.1 §7, 21.8
Cranelift (Wasmtime v37)	ISLE rules with priorities, applied per instruction in reverse order with load sinking; aegraph mid-end; `MachBuffer` with islands and veneers	Lessons 21.7, 21.10 §6
Winch (Wasmtime v37), V8 Sparkplug and Liftoff	Macro expansion: one code template per bytecode operator	Lesson 21.1 §7
HotSpot C2 (JDK 21)	DP tiling with a generated labeler (ADLC's `DFA` from `.ad` descriptions)	Lessons 21.2 §7, 21.8
lcc	lburg-generated DP labelers from `.md` tree grammars; DAGs cut into trees (`undag`)	Lessons 21.2, 21.4
Go 1.23 (`cmd/compile`)	Rewrite rules (`_gen/*.rules`) applied greedily to a fixed point for lowering	Lesson 21.7 §6

Comparison¶

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

Lesson 21.1 — Tree tiling I: macro expansion, maximal munch and peephole combining

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Macro expansion	one instruction sequence per node; cannot use multi-node instructions or addressing modes	\(\Theta(n)\) · lab: 14 µs per program; cost 70866 on the lab corpus (32 % above optimum)	poorest code; very predictable	lowest: a table of templates	baseline and debug compilers: Winch, Liftoff, Sparkplug; first stage of expand-then-combine
Maximal munch	largest tile at each node; locally optimal (Theorem 21.1.13), not optimum (Proposition 21.1.14)	\(O(nRp)\) · lab: 36 µs per program; cost 53935 (0.6 % above optimum)	good; loses when a big tile near the root blocks a better one below	low: pattern matcher plus an ordering	LLVM SelectionDAG and GlobalISel (by complexity), Cranelift ISLE (by priority), Appel's Tiger compiler
Peephole combining	whatever single-use links and the recognizer allow; order-dependent local fixed point (Theorem 21.1.16)	\(O(m^2 w)\) worst · a linear pass or two in practice	good with a strong recognizer; misses combinations across multiple uses	moderate: RTL substitution, recognizer, liveness	GCC `combine`, LLVM `PeepholeOptimizer` and `MachineCombiner`, the Davidson–Fraser PO and vpo

Lesson 21.2 — Optimal tree tiling: dynamic programming, twig, iburg and lburg

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Aho–Johnson dynamic programming	optimum tiling of trees (Theorem 21.2.7); with registers, optimal for the machine class of [AJ76]	\(O(n R p)\), linear in \(n\) · lab: 59 µs per program (1.6× munch), cost 53632 = optimum	best possible for a tree; register-bounded version also minimizes spills	moderate: labels, chain closure, reduce	the lab's DP selector; HotSpot C2's matcher; textbook compilers
Tree-grammar generators (twig, iburg, lburg)	same optimum, from a grammar; dynamic costs add predicates (Proposition 21.2.12)	generated DP, linear · lcc compiles itself with it	same as DP; grammar errors surface as "no cover"	low per target once the generator exists	lcc (lburg), Jikes RVM's and HotSpot's generated matchers, many teaching compilers

Lesson 21.3 — Bottom-up rewrite systems: BURS theory, BURG and table compression

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
BURS theory (Pelegrí-Llopart–Graham)	optimum tiling (Theorem 21.3.7) when the grammar is BURS-finite; no dynamic costs	labeling \(\Theta(n)\) with \(O(1)\) per node; generation up to exponential in the grammar	same code as DP; a non-finite grammar is rejected at build time	high: normal form, closure, state interning	the theory behind BURG; offline tables for fixed grammars
BURG table generation (Proebsting)	same, with representers and trimming	one lookup per node, no cost arithmetic; tables of \(\sum_o \prod_i \rho_{o,i}\) entries	same code as DP	high generator, trivial runtime	historical production back ends, embedded and JIT generators; the lab's part B

Lesson 21.4 — Beyond trees: DAG covering, NP-completeness and near-optimal selection

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Tree decomposition and greedy DAG matching	optimum only among covers that never duplicate (Proposition 21.4.7); greedy folds follow fixed rules	linear · the default in production	D1: 6, D2: 7 (optimum 5 and 7)	low: reuse the tree selector; fold legality checks	LLVM SelectionDAG (single-use fold + address-mode duplication), lcc (`undag`), the Dragon book
NOLTIS	near-optimal: optimum on 99.7 % of cases [KG08]; D1: 5, D2: 7	linear, two DP passes	usually optimal; local decisions can mislead it	moderate: DP twice plus overlap/CSE costs	research prototype in LLVM; the idea is in address-mode duplication
PBQP and ILP formulations	PBQP optimum when R0–R2 suffice (Theorem 21.4.13); ILP always optimum	PBQP near linear with RN; ILP exponential	best available; PBQP degrades gracefully	high: formulation, solver, DAG-pattern constraints	DSP compilers, research (Ebner et al. in LLVM), universal selection with CP

Lesson 21.5 — LLVM's SelectionDAG: build, combine, legalize, select, schedule

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
DAG building and combining	exposes all dependences of a block; canonicalizes and simplifies (Proposition 21.5.5)	linear build; combine linear per run in practice, 4 runs	good code depends on it (the `-combiner-disabled` box); combine bugs are silent miscompiles	high: thousands of rules in `DAGCombiner.cpp`	every SelectionDAG target
Type and operation legalization	makes any IR type and operation executable (Theorem 21.5.9)	linear in practice	predictable per target; custom lowerings can be very good (NEON `CNT`)	high per target: action tables plus `LowerOperation`	every SelectionDAG target; the `legalization` drill
Matcher-table selection	greedy munch by complexity on DAGs (Proposition 21.5.11)	\(O(n \cdot d)\); x86 table 627 KB	near-optimal on common code; "Cannot select" when uncovered	patterns are declarative (TableGen); `Select` for the rest	every SelectionDAG target
SelectionDAG scheduling	any topological order; heuristics for pressure or ILP	\(O(n \log n)\)	modest effect since MachineScheduler runs later	low (choose a scheduler)	linearization before register allocation

Lesson 21.6 — GlobalISel and FastISel

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
FastISel	one IR instruction at a time plus local folds; falls back for the rest (Proposition 21.6.4)	linear, smallest constant	`-O0` quality; debuggable 1:1 mapping	moderate per target (hooks)	`-O0` on x86-64 and other SelectionDAG targets
GlobalISel pipeline	whole-function generic MIR; legal → banked → selected (Theorem 21.6.6)	linear passes, no per-block DAG	on AArch64 comparable to SelectionDAG; on x86-64 still incomplete (4 instructions vs 2 on the store box; fallbacks)	high: four target components, but reusable and testable in MIR	AArch64 (`-O0` default), AMDGPU, RISC-V, Apple GPU; experimental x86
GlobalISel combiners	canonicalization and simplification on MIR, across blocks	linear per iteration, capped	quality depends on the rule set	rules in TableGen plus C++ helpers	pre-/post-legalizer passes of every GlobalISel target

Lesson 21.7 — Rewriting-based selection: Cranelift ISLE and e-graphs

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
ISLE term rewriting	greedy per instruction with explicit priorities; deterministic (Proposition 21.7.7); patterns see operand trees through extractors	linear; compiled to a Rust trie	comparable to LLVM's selectors on common code; rules verifiable (Crocus)	moderate: rules are concise, extractors are Rust	Cranelift (Wasmtime, rustc_codegen_cranelift); Go's rulegen is a cousin
E-graph-based selection	all rewrites at once; optimal tree extraction (Theorem 21.7.6), DAG extraction NP-hard	exponential worst case; limits or acyclic variants make it practical	best when rules are rich; limited by the rule set (the `isub` example)	high: e-graph, rebuild, extraction, elaboration	Denali (research), Diospyros/egg (DSP vectorization), Cranelift's mid-end (aegraph)

Lesson 21.8 — Describing targets: TableGen, GCC machine descriptions and tree grammars

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
LLVM TableGen	general records; many generated artifacts (selectors, encoders, registers, CC, scheduling); typed patterns (Proposition 21.8.4)	x86 matcher generated in about 10 s; elaboration linear	type contradictions reported with the offending pattern; semantics unchecked	high learning curve; very high reuse	every LLVM back end
GCC machine descriptions	RTL templates with constraints and alternatives; conditions in C	`recog` decision tree generated at build time	first match in file order (Proposition 21.8.7); order-dependent surprises	moderate per pattern; large files (i386.md: 30,221 lines)	every GCC back end
Tree-grammar and ADL descriptions	exactly the tile grammars of Lesson 21.1, with dynamic costs (lburg) or operand classes and encodings (ADL)	labelers generated in linear time	"no cover" at compile time for missing rules	low for lburg (one line per rule); moderate for ADL (encodings included)	lcc, iburg users, HotSpot C2

Lesson 21.9 — Calling conventions, frame lowering and prologue/epilogue insertion

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Argument assignment (calling conventions)	exact by construction (Theorem 21.9.4); aggregates need front-end help	\(\Theta(n)\) · negligible	ABI mismatches are silent until run time	declarative in TableGen; custom C++ for odd cases (`i128`)	every call and function entry; drill `calling-convention`
Frame layout and frame lowering	aligned, disjoint slots (Proposition 21.9.7); red zone for leaves	\(O(k \log k)\) · negligible	smaller frames with slot coloring; alignment bugs crash late	moderate per target (`TargetFrameLowering`)	every function; `-frame-pointer`, `noredzone`
Prologue/epilogue insertion and shrink-wrapping	correct under dominance conditions (Theorem 21.9.11)	linear plus dominator trees	faster early-exit paths (4 → 3 instructions in the box)	high: CFI, unwinding, funclets, stack probing	PEI in every function; shrink-wrapping at `-O1` and above on most targets

Lesson 21.10 — The MC layer: encoding, relaxation, relocations and object files

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Instruction encoding (MCInst and MCCodeEmitter)	exact bytes for every instruction form; symbolic operands deferred as fixups	\(O(1)\) per instruction · negligible	wrong bytes are silent until run; round-trip tests catch them	generated from TableGen on regular ISAs; handwritten special cases on x86	every object file; `llvm-mc -show-encoding` for inspection
Assembly with fragments, fixups and relaxation	minimal size for label operands (Theorem 21.10.7); NP-complete in general [Szy78]	\(\le n + 1\) layout rounds · usually 1–2	smallest consistent branches; relax-all trades size for simplicity	moderate: fragments, fixpoint, per-target relaxation tables	integrated assemblers (LLVM MC, GNU as); islands and veneers in JITs
Relocations and object formats (ELF, Mach-O, COFF)	any cross-section or cross-module reference the ABI defines	\(O(r)\) · negligible	link-time errors for out-of-range relocations; wrong types are silent	high: three formats, dozens of relocation types per processor	every separately compiled program

Comparison-lab results (reproduce with build/<preset>/bin/ch21-compare; this machine): on 2005 programs with 71 197 IR nodes, macro expansion emits 55 436 instructions of total cost 70 866, maximal munch 37 554 instructions of cost 53 935, and DP 38 202 instructions of cost 53 632; DP beats munch on 286 programs (14.3 %) and never loses. Timings on this shared 4-core container vary with load: the lessons quote a quiet run (14, 36 and 59 µs per program); over four later runs under load, macro expansion took 17–33 µs per program, munch 38–57 µs and DP 81–104 µs, so DP costs about 3–6× macro expansion and 1.6–2.7× munch. See labs/ch21-isel/SPEC.md for how to measure.

Route through this chapter¶

Step	What	Techniques	How it is exercised
1	Lesson 21.1	macro expansion, maximal munch, peephole combining	drill `munch-tiling`; lab E1–E2
2	Lesson 21.2	Aho–Johnson DP; twig, iburg, lburg	drill `dp-tiling`; lab E3
3	Lesson 21.3	BURS theory, BURG table generation	★ lab E4 (`ch21-burg`)
4	Lesson 21.4	tree decomposition, NOLTIS, PBQP/ILP	quiz; theory only
5	Lesson 21.5	SelectionDAG phases	drill `legalization`; E5 tasks 1, 5, 6
6	Lesson 21.6	FastISel, GlobalISel, GlobalISel combiners	E5 tasks 3, 4, 8
7	Lesson 21.7	ISLE, e-graph selection	quiz; real-world boxes with Wasmtime
8	Lesson 21.8	TableGen, GCC machine descriptions, tree grammars and ADL	quiz; `llvm-tblgen` boxes
9	Lesson 21.9	calling conventions, frame lowering, PEI and shrink-wrapping	drill `calling-convention`; E5 task 7
10	Lesson 21.10	encoding, relaxation, relocations and object formats	E5 task 9
11	Exercises E1–E4: the comparison lab `labs/ch21-isel/SPEC.md`	macro vs munch vs DP on the Tessera ISA (★ BURG tables)	`ch21.isel.*` unit tests, lit tests with the simulator, `ch21-compare`
12	Exercises E5: guided MIR exploration `labs/ch21-mir/SPEC.md`	Pebble uses LLVM's back end: SelectionDAG at `-O1`+, FastISel/GlobalISel at `-O0`	`ch21.lit` (`mir-answers.test`, graded answers)
13	Theory test	all	`./course quiz 21` (≥ 80 % to finish)

Practice and check¶

./course drill munch-tiling --difficulty easy        # warm up; --solution shows every step
./course drill dp-tiling --seed 3 --solution          # the label table of Algorithm 21.2.3
./course drill legalization --difficulty hard         # x86-64 and AArch64 legalization steps
./course drill calling-convention --seed 5            # SysV vs AAPCS64 locations
./course flash 21                                     # daily, a few minutes
./course quiz 21                                      # after the lessons
./course test 21                                      # after the exercises
./course status                                       # done = quiz ≥ 80 % and tests pass

References¶

The chapter's annotated bibliography (papers, textbook sections, pinned source files for LLVM 23.1.2, GCC 15, Cranelift/Wasmtime v37, HotSpot, lcc/iburg, Go and V8, specifications, a talk and blog posts) is in references.md. Start with: [AJ76] and [AGT89] (DP tiling and its generator), [PG88] and [FHP92b] (BURS and iburg), [KG08] (DAGs in practice), [Bli16] (the survey of the whole field), and for LLVM [LLVM-CodeGenDoc] and [LLVM-GISel]. For the object-file end, keep [SysV-ABI] and [Lev00, Ch. 7] at hand.