Skip to content

References — Chapter 21 · Instruction Selection & the LLVM Code Generator

Every source this chapter cites, grouped by kind. Lessons cite entries inline as [KEY]; each entry says why and when to read it. Core reading marks the entries the chapter assumes you will open.

Foundational and research papers

  • [AGT89] Alfred V. Aho, Mahadevan Ganapathi, and Steven W. K. Tjiang. Code Generation Using Tree Matching and Dynamic Programming. ACM TOPLAS 11(4), pp. 491–516, 1989. doi:10.1145/69558.75700
    Why and when: Core reading. twig: tree patterns with costs and actions, top-down matching and the tiling DP of Algorithm 21.2.3. The paper that made DP tiling a generator (Lesson 21.2 §1 and §7).
    Cited in: overview, 02-optimal-tree-tiling

  • [AJ76] Alfred V. Aho and Stephen C. Johnson. Optimal Code Generation for Expression Trees. Journal of the ACM 23(3), pp. 488–501, 1976. doi:10.1145/321958.321970
    Why and when: Core reading. The origin of dynamic-programming tree tiling: contiguous evaluation, the cost vector per register count, and the optimality proof behind Algorithm 21.2.5 and Theorem 21.2.8. Read §3–4 after Lesson 21.2 §2.
    Cited in: overview, 02-optimal-tree-tiling

  • [AJU77] Alfred V. Aho, Stephen C. Johnson, and Jeffrey D. Ullman. Code Generation for Expressions with Common Subexpressions. Journal of the ACM 24(1), pp. 146–160, 1977. doi:10.1145/321992.322001
    Why and when: Generating optimal code from a DAG is NP-complete with more registers too, which is why DAG covering uses decomposition and heuristics (Lesson 21.4 §1).
    Cited in: 04-dag-covering

  • [BA06] Sorav Bansal and Alex Aiken. Automatic Generation of Peephole Superoptimizers. ASPLOS XII, pp. 394–403, 2006. doi:10.1145/1168857.1168906
    Why and when: Learn peephole combinations offline by enumeration and equivalence checking: the automated end of Lesson 21.1 §6's variants (and Ch 13).
    Cited in: 01-macro-expansion-and-maximal-munch

  • [BDB90] A. Balachandran, D. M. Dhamdhere, and S. Biswas. Efficient Retargetable Code Generation Using Bottom-up Tree Pattern Matching. Computer Languages 15(3), pp. 127–140, 1990. doi:10.1016/0096-0551(90)90006-B
    Why and when: A simpler BURS table construction for regular tree grammars with Graham–Glanville style costs; compare with Algorithm 21.3.5 after Lesson 21.3 §6.
    Cited in: 03-burs-automata

  • [BS76] John Bruno and Ravi Sethi. Code Generation for a One-Register Machine. Journal of the ACM 23(3), pp. 502–510, 1976. doi:10.1145/321958.321971
    Why and when: Optimal code for expression DAGs is NP-complete even with one register: the first of the hardness results behind Lesson 21.4 §1. Read the introduction and the reduction outline.
    Cited in: 04-dag-covering

  • [Cat80] Roderic G. G. Cattell. Automatic Derivation of Code Generators from Machine Descriptions. ACM TOPLAS 2(2), pp. 173–190, 1980. doi:10.1145/357094.357097
    Why and when: Top-down, largest-pattern-first matching of trees against a machine description: the origin of maximal munch as a technique (Lesson 21.1 §1, Algorithm 21.1.8).
    Cited in: 01-macro-expansion-and-maximal-munch, 08-target-description

  • [Cha87] David R. Chase. An Improvement to Bottom-up Tree Pattern Matching. POPL 1987, 1987. doi:10.1145/41625.41640
    Why and when: Per-child index maps that shrink bottom-up matching tables, the compression every BURS table generator uses (Lesson 21.3, Definition 21.3.9 and Algorithm 21.3.10).
    Cited in: 03-burs-automata

  • [Cho88] Fred C. Chow. Minimizing Register Usage Penalty at Procedure Calls. PLDI 1988, 1988. doi:10.1145/53990.53999
    Why and when: The origin of shrink-wrapping: place callee-saved register saves and restores around the region that uses them. Read §4 with Lesson 21.9 (Algorithm 21.9.10).
    Cited in: 09-calling-conventions-and-frames

  • [DF80] Jack W. Davidson and Christopher W. Fraser. The Design and Application of a Retargetable Peephole Optimizer. ACM TOPLAS 2(2), pp. 191–202, 1980. doi:10.1145/357094.357098
    Why and when: Register transfers and a combiner that merges adjacent instructions whose joint effect is one machine instruction: the ancestor of GCC's combine (Lesson 21.1 §2, Algorithm 21.1.11).
    Cited in: 01-macro-expansion-and-maximal-munch, 08-target-description

  • [DF84] Jack W. Davidson and Christopher W. Fraser. Code Selection through Object Code Optimization. ACM TOPLAS 6(4), pp. 505–526, 1984. doi:10.1145/1780.1783
    Why and when: "Expand naively, then combine" as a complete selection strategy (the PO/YC compilers). Read after Lesson 21.1 §3 to see the combiner reach the running example's cost 5.
    Cited in: 01-macro-expansion-and-maximal-munch

  • [EBSKWK08] Dietmar Ebner, Florian Brandner, Bernhard Scholz, Andreas Krall, Peter Wiedermann, and Albrecht Kadlec. Generalized Instruction Selection Using SSA-Graphs. LCTES 2008, pp. 31–40, 2008. doi:10.1145/1375657.1375663 · pdf
    Why and when: PBQP selection with multi-output (DAG) patterns in an LLVM prototype. Read §3 and the evaluation after Lesson 21.4 §2 and the PBQP box of §7.
    Cited in: 04-dag-covering

  • [EKS03] Erik Eckstein, Oliver König, and Bernhard Scholz. Code Instruction Selection Based on SSA-Graphs. SCOPES 2003, LNCS 2826, pp. 49–65, 2003. doi:10.1007/978-3-540-39920-9_5
    Why and when: Whole-function selection on the SSA graph as a PBQP (Definition 21.4.11). Read §3–4 after Lesson 21.4 §2.
    Cited in: 04-dag-covering

  • [Ert99] M. Anton Ertl. Optimal Code Selection in DAGs. POPL 1999, 1999. doi:10.1145/292540.292562
    Why and when: For grammars with a checkable property, running the tree DP on a DAG is already optimal. Read after Lesson 21.4 §6 to see when the NP-hardness does not bite.
    Cited in: 04-dag-covering

  • [FHP92a] Christopher W. Fraser, Robert R. Henry, and Todd A. Proebsting. BURG: Fast Optimal Instruction Selection and Tree Parsing. ACM SIGPLAN Notices 27(4), pp. 68–76, 1992. doi:10.1145/131080.131089
    Why and when: The BURG tool: a grammar in, a hard-coded BURS labeler out. The input format is the one of the lab's rules files (labs/ch21-isel, E4). Read with Lesson 21.3 §7.
    Cited in: 03-burs-automata

  • [FHP92b] Christopher W. Fraser, David R. Hanson, and Todd A. Proebsting. Engineering a Simple, Efficient Code-Generator Generator. ACM LOPLAS 1(3), pp. 213–226, 1992. doi:10.1145/151640.151642
    Why and when: Core reading. iburg: the DP labeler of Algorithm 21.2.11 generated as C, with dynamic costs. Twelve pages and the clearest description of a tree-grammar generator; read after Lesson 21.2 §2.
    Cited in: overview, 02-optimal-tree-tiling, 03-burs-automata

  • [GG78] R. Steven Glanville and Susan L. Graham. A New Method for Compiler Code Generation. POPL 1978, 1978. doi:10.1145/512760.512785
    Why and when: Instruction selection as LR parsing of a linearized tree, with conflicts resolved toward the longest match (maximal munch). The variant discussed in Lesson 21.1 §6.
    Cited in: 01-macro-expansion-and-maximal-munch, 08-target-description

  • [HO82] Christoph M. Hoffmann and Michael J. O'Donnell. Pattern Matching in Trees. Journal of the ACM 29(1), pp. 68–95, 1982. doi:10.1145/322290.322295
    Why and when: Top-down and bottom-up tree pattern matching automata. The bottom-up construction is the matching half of BURS (Lesson 21.3 §1); twig uses the top-down one (Lesson 21.2 §6).
    Cited in: 02-optimal-tree-tiling, 03-burs-automata

  • [JNR02] Rajeev Joshi, Greg Nelson, and Keith Randall. Denali: A Goal-directed Superoptimizer. PLDI 2002, 2002. doi:10.1145/512529.512566
    Why and when: The first e-graph-based instruction selector: saturate with axioms, then ask a SAT solver for the shortest program. Read §2–3 before Lesson 21.7's e-graph section.
    Cited in: 04-dag-covering, 07-rewrite-based-selection

  • [KG08] David Ryan Koes and Seth Copen Goldstein. Near-Optimal Instruction Selection on DAGs. CGO 2008, pp. 45–54, 2008. doi:10.1145/1356058.1356065 · pdf
    Why and when: Core reading. NOLTIS (Algorithm 21.4.9): tile the DAG as if it were a tree, then fix shared nodes whose duplication costs more than sharing. Implemented in LLVM and compared with an ILP optimum. Read §3–5 with Lesson 21.4.
    Cited in: overview, 04-dag-covering

  • [McK65] William M. McKeeman. Peephole Optimization. Communications of the ACM 8(7), pp. 443–444, 1965. doi:10.1145/364995.365000
    Why and when: Names the peephole idea that Davidson and Fraser later turned into instruction selection by combining (Lesson 21.1 §1). Two pages; read them before Algorithm 21.1.11.
    Cited in: 01-macro-expansion-and-maximal-munch

  • [PG88] Eduardo Pelegrí-Llopart and Susan L. Graham. Optimal Code Generation for Expression Trees: An Application of BURS Theory. POPL 1988, pp. 294–308, 1988. doi:10.1145/73560.73586
    Why and when: Core reading. The origin of BURS: relative costs folded into automaton states, so optimal selection needs no cost arithmetic at compile time. Read §3–4 with Lesson 21.3 §2.
    Cited in: overview, 03-burs-automata

  • [Pro92] Todd A. Proebsting. Simple and Efficient BURS Table Generation. PLDI 1992, 1992. doi:10.1145/143095.143145
    Why and when: The worklist state construction with cost normalization and chain closure that Algorithm 21.3.5 and the lab's ch21-burg follow. Read §3 with Lesson 21.3 §2.
    Cited in: 03-burs-automata

  • [Pro95] Todd A. Proebsting. BURS Automata Generation. ACM TOPLAS 17(3), pp. 461–486, 1995. doi:10.1145/203095.203098
    Why and when: The journal version: state trimming, representer states and the table sizes of real grammars (Proposition 21.3.11). Read §4–6 after Lesson 21.3 §5.
    Cited in: 03-burs-automata

  • [Pro98] Todd A. Proebsting. Least-Cost Instruction Selection in DAGs is NP-Complete. Unpublished note, Microsoft Research, 1998.
    Why and when: The short SAT reduction behind Theorem 21.4.4. Read it (or [KG08, §2]) after Lesson 21.4 §2 and compare with the lesson's 3-SAT gadgets.
    Note: Published only as a web page (research.microsoft.com/~toddpro/papers/proof.htm, now offline; archived copies exist). Koes and Goldstein [KG08] restate the reduction.
    Cited in: 04-dag-covering

  • [SU70] Ravi Sethi and Jeffrey D. Ullman. The Generation of Optimal Code for Arithmetic Expressions. Journal of the ACM 17(4), pp. 715–728, 1970. doi:10.1145/321607.321620
    Why and when: Optimal register-bounded evaluation of expression trees on a simple machine, the result Aho and Johnson generalized (Lesson 21.2 §1). Read §2–3 for the labeling idea.
    Cited in: 02-optimal-tree-tiling

  • [Szy78] Thomas G. Szymanski. Assembling Code for Machines with Span-Dependent Instructions. Communications of the ACM 21(4), pp. 300–308, 1978. doi:10.1145/359460.359474
    Why and when: Span-dependent instructions: an efficient optimal algorithm for label operands and an NP-completeness proof for general expressions (Theorem 21.10.7, Proposition 21.10.8). Read it after Lesson 21.10 §2.
    Cited in: overview, 10-mc-layer-and-object-files

  • [TSTL09] Ross Tate, Michael Stepp, Zachary Tatlock, and Sorin Lerner. Equality Saturation: A New Approach to Optimization. POPL 2009, pp. 264–276, 2009. doi:10.1145/1480881.1480915
    Why and when: Equality saturation as an optimizer architecture, the idea behind Algorithm 21.7.5. Read §1–3 with Lesson 21.7 §2.
    Cited in: 07-rewrite-based-selection

  • [VNLBS21] Alexa VanHattum, Rachit Nigam, Vincent T. Lee, James Bornholt, and Adrian Sampson. Vectorization for Digital Signal Processors via Equality Saturation. ASPLOS 2021, 2021. doi:10.1145/3445814.3446707
    Why and when: Diospyros: selecting DSP vector instructions by equality saturation and extraction, a concrete e-graph selector (Lesson 21.7 §6).
    Cited in: 07-rewrite-based-selection

  • [VPFSB24] Alexa VanHattum, Monica Pardeshi, Chris Fallin, Adrian Sampson, and Fraser Brown. Lightweight, Modular Verification for WebAssembly-to-Native Instruction Selection. ASPLOS 2024, 2024. doi:10.1145/3617232.3624862
    Why and when: Crocus: SMT verification of Cranelift's ISLE lowering rules, which found real bugs. Read §2–4 after Lesson 21.7 §4 to see why a rule DSL makes selectors verifiable.
    Cited in: 07-rewrite-based-selection

  • [WNW+21] Max Willsey, Chandrakana Nandi, Yisu Remy Wang, Oliver Flatt, Zachary Tatlock, and Pavel Panchekha. egg: Fast and Extensible Equality Saturation. Proc. ACM on Programming Languages 5 (POPL), Article 23, 2021. doi:10.1145/3434304
    Why and when: Rebuilding and e-class analyses: the library behind most e-graph selection prototypes. Read §2–3 after Lesson 21.7 §2 (and see Ch 8, Lesson 8.5).
    Cited in: 07-rewrite-based-selection

Textbooks and monographs

  • [Appel] Andrew W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998. Read: §9.1 (Algorithms for instruction selection: maximal munch, dynamic programming, tree grammars), Ch. 6 (Activation records).
    Why and when: The source of the names "maximal munch", "optimal" and "optimum" used in Definition 21.1.9. §9.1 is ten pages and has code; the C and Java editions share the numbering.
    Cited in: 01-macro-expansion-and-maximal-munch

  • [Bli16] Gabriel Hjort Blindell. Instruction Selection: Principles, Methods, and Applications. Springer, 2016. Read: Ch. 2 (Macro expansion), Ch. 3 (Tree covering), Ch. 4 (DAG covering), Ch. 5 (Graph covering); an earlier version is the survey arXiv:1306.4898.
    Why and when: Core reading. The survey of the whole field this chapter compresses: every technique of Lessons 21.1–21.4 and 21.7 with its history. Read the chapter matching each lesson afterwards.
    Cited in: overview, 01-macro-expansion-and-maximal-munch, 03-burs-automata, 04-dag-covering

  • [Col25] Quentin Colombet. LLVM Code Generation: A deep dive into compiler backend development. Packt, 2025. Read: Ch. 6 (TableGen), Ch. 11 (the backend), Ch. 12 (the machine code layer), Ch. 14–17 (instruction selection: SelectionDAG and GlobalISel), Ch. 20 (stack layout), Ch. 21 (the assembler); code: github.com/PacktPublishing/LLVM-Code-Generation.
    Why and when: By the architect of GlobalISel: the whole LLVM back end of Lessons 21.5–21.10 from a target writer's point of view. Read Ch. 14–17 after Lesson 21.6.
    Cited in: 06-globalisel-and-fastisel, 08-target-description

  • [Dragon2] Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools, 2nd ed.. Addison-Wesley, 2006. Read: §8.5 (DAGs of basic blocks), §8.9 (instruction selection by tree rewriting), §8.10 (optimal code for expressions), §8.11 (dynamic-programming code generation).
    Why and when: The textbook versions of tree rewriting and the Aho–Johnson DP (Lesson 21.2) and of code generation from block DAGs (Lesson 21.4). Gentler than the papers.
    Cited in: 02-optimal-tree-tiling, 04-dag-covering

  • [EaC3] Keith D. Cooper and Linda Torczon. Engineering a Compiler, 3rd ed.. Morgan Kaufmann, 2022. Read: Ch. 11 (Instruction Selection: tree-pattern matching, peephole-based selection), Ch. 6 (Implementing Procedures: activation records, linkage conventions).
    Why and when: A compact survey of selection by tree patterns and by peephole combining (Lessons 21.1–21.2) and of calling sequences and frames (Lesson 21.9). Read Ch. 11 as a second explanation.
    Cited in: 01-macro-expansion-and-maximal-munch

  • [FH95] Christopher W. Fraser and David R. Hanson. A Retargetable C Compiler: Design and Implementation. Addison-Wesley, 1995. Read: Ch. 14 (selecting and emitting instructions with lburg), Ch. 16–18 (the MIPS, SPARC and x86 code generators).
    Why and when: lcc's code generators and lburg explained with the full source (Lesson 21.2 §7 and Lesson 21.8 §2). Read Ch. 14 with the lcc box of Lesson 21.8.
    Cited in: 02-optimal-tree-tiling, 08-target-description

  • [Lev00] John R. Levine. Linkers and Loaders. Morgan Kaufmann, 2000. Read: Ch. 3 (Object files: ELF, COFF/PE and others), Ch. 7 (Relocation).
    Why and when: What the linker does with Lesson 21.10's relocations. Read Ch. 7 after Theorem 21.10.11.
    Cited in: overview

  • [Muchnick] Steven S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997. Read: Ch. 6 (Producing Code Generators Automatically: §6.2 the syntax-directed Graham–Glanville technique, §6.4 tree pattern matching and dynamic programming).
    Why and when: The detailed treatment of LR-parsing code generators and their pitfalls (Lesson 21.1 §6).
    Cited in: 01-macro-expansion-and-maximal-munch

Source code (pinned versions)

  • [CL-Egraph] Cranelift's aegraph mid-end — cranelift/codegen/src/egraph.rs in bytecodealliance/wasmtime at v37.0.2.
    Why and when: The e-graph build, rewrite and elaboration of Lesson 21.7; extraction costs are in egraph/cost.rs and the rules in opts/.isle.
    Cited in:* 07-rewrite-based-selection

  • [CL-ISLE-Src] The ISLE compiler's overlap checker (and the aarch64 lowering rules) — cranelift/isle/isle/src/overlap.rs in bytecodealliance/wasmtime at v37.0.2.
    Why and when: Proposition 21.7.7's check in code; the rules themselves are in cranelift/codegen/src/isa/aarch64/lower.isle.
    Cited in: 07-rewrite-based-selection

  • [CL-MachBuffer] Cranelift's MachBuffer (single-pass emission with islands and veneers) — cranelift/codegen/src/machinst/buffer.rs in bytecodealliance/wasmtime at v37.0.2. Symbols: MachBuffer::island_needed, MachBuffer::emit_island.
    Why and when: The alternative to fixpoint relaxation in Lesson 21.10 §6; the module comment explains deadlines, islands and veneers in two pages.
    Cited in: 10-mc-layer-and-object-files

  • [GCC-Combine] GCC's instruction combiner — gcc/combine.cc in gcc-mirror/gcc at releases/gcc-15. Symbols: try_combine, combine_instructions.
    Why and when: The descendant of Davidson–Fraser combining (Algorithm 21.1.11): merges two to four linked instructions and keeps the result if recog accepts it. Read the header comment.
    Cited in: 01-macro-expansion-and-maximal-munch

  • [GO-Rules] Go's lowering rules for amd64 — src/cmd/compile/internal/ssa/_gen/AMD64.rules in golang/go at go1.23.0.
    Why and when: A rewrite-rule DSL applied greedily to a fixed point, without priorities: compare with ISLE after Lesson 21.7 §6.
    Cited in: 07-rewrite-based-selection

  • [HS-ADLC] HotSpot's ADLC generator of C2's DFA labeler — src/hotspot/share/adlc/dfa.cpp in openjdk/jdk at jdk-21-ga. Symbols: cost_check.
    Why and when: Generates the DP labeler from the .ad files (for x86-64, src/hotspot/cpu/x86/x86_64.ad), pruning cost tests with bounds (Lesson 21.2 §6, Lesson 21.8).
    Cited in: 02-optimal-tree-tiling, 08-target-description

  • [HS-Matcher] HotSpot C2's matcher — src/hotspot/share/opto/matcher.cpp in openjdk/jdk at jdk-21-ga. Symbols: Matcher::Label_Root, Matcher::ReduceInst.
    Why and when: Labeling and reduction exactly as Algorithms 21.2.3–21.2.4 on C2's sea of nodes.
    Cited in: 02-optimal-tree-tiling

  • [IBURG-Src] iburg, the code-generator generator — iburg.c in drh/iburg at ef9d6452000e3b371b446c198d2028dfa38b11c4.
    Why and when: About 750 lines of C that emit the labeler of Algorithm 21.2.11; run it on sample.brg as in Lesson 21.2's box.
    Cited in: 02-optimal-tree-tiling

  • [LCC-Src] lcc's lburg and its machine descriptions (src/x86linux.md) — lburg/lburg.c in drh/lcc at 2b5cf358d9aa6759923dd7461f2df7f7f2a28471.
    Why and when: lburg plus the .md grammars of Lessons 21.2 and 21.8; undag in src/dag.c cuts DAGs into trees (Lesson 21.4).
    Cited in: 02-optimal-tree-tiling, 04-dag-covering, 08-target-description

  • [LLVM-CC] x86 calling conventions in TableGen — llvm/lib/Target/X86/X86CallingConv.td in llvm/llvm-project at llvmorg-23.1.2. Symbols: CC_X86_64_C, RetCC_X86_64_C.
    Why and when: Algorithm 21.9.2 as CCIfType/CCAssignToReg rules; the driver is CCState in llvm/lib/CodeGen/CallingConvLower.cpp.
    Cited in: 09-calling-conventions-and-frames

  • [LLVM-DAGISelEmitter] TableGen's generator of the SelectionDAG matcher table — llvm/utils/TableGen/DAGISelEmitter.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: DAGISelEmitter::run.
    Why and when: Sorts patterns by complexity (PatternToMatch::getPatternComplexity in Common/CodeGenDAGPatterns.cpp) and emits the table that Algorithm 21.5.10 interprets. Read after Lesson 21.5 §7.
    Cited in: 01-macro-expansion-and-maximal-munch, 05-selectiondag, 08-target-description

  • [LLVM-ELFWriter] The ELF object writer — llvm/lib/MC/ELFObjectWriter.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: ELFObjectWriter::recordRelocation, ELFObjectWriter::useSectionSymbol, ELFWriter::writeObject.
    Why and when: How fixups become RELA records and when a local symbol is replaced by its section (Algorithm 21.10.10).
    Cited in: 10-mc-layer-and-object-files

  • [LLVM-FastISel] FastISel — llvm/lib/CodeGen/SelectionDAG/FastISel.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: FastISel::selectInstruction, FastISel::tryToFoldLoad.
    Why and when: Algorithm 21.6.3: bottom-up per-instruction selection with target hooks and fallback.
    Cited in: 06-globalisel-and-fastisel

  • [LLVM-GISel-Combine] GlobalISel's generic combine rules — llvm/include/llvm/Target/GlobalISel/Combine.td in llvm/llvm-project at llvmorg-23.1.2. Symbols: mul_to_shl, trivial_combines.
    Why and when: GICombineRule definitions (match, apply) with C++ halves in CombinerHelper.cpp; the mul_to_shl rule of Lesson 21.6's box.
    Cited in: 06-globalisel-and-fastisel

  • [LLVM-GlobalISelSrc] The GlobalISel passes — llvm/lib/CodeGen/GlobalISel in llvm/llvm-project at llvmorg-23.1.2. Symbols: IRTranslator::translate, Legalizer::legalizeMachineFunction, RegBankSelect::assignInstr, InstructionSelect::selectInstr.
    Why and when: One file per stage of Lesson 21.6's pipeline; AArch64's target parts are in llvm/lib/Target/AArch64/GISel/.
    Cited in: 06-globalisel-and-fastisel

  • [LLVM-LegalizeTypes] SelectionDAG type legalization — llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: DAGTypeLegalizer::run.
    Why and when: Algorithm 21.5.7: the worklist that promotes, expands, softens and splits illegal types (the operation legalizer is LegalizeDAG.cpp next to it).
    Cited in: 05-selectiondag

  • [LLVM-MachineCombiner] Latency-driven reassociation and combining of machine instructions — llvm/lib/CodeGen/MachineCombiner.cpp in llvm/llvm-project at llvmorg-23.1.2.
    Why and when: A combiner that accepts a rewrite only if the critical path does not grow (Lesson 21.1 §6).
    Cited in: 01-macro-expansion-and-maximal-munch

  • [LLVM-MachO] AArch64 Mach-O relocation writer — llvm/lib/Target/AArch64/MCTargetDesc/AArch64MachObjectWriter.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: AArch64MachObjectWriter::recordRelocation.
    Why and when: The mapping from AArch64 fixup kinds to ARM64_RELOC_* types seen in Lesson 21.10's object box.
    Cited in: 10-mc-layer-and-object-files

  • [LLVM-MCAssembler] The MC assembler (layout, relaxation, fixups) — llvm/lib/MC/MCAssembler.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: MCAssembler::layout, MCAssembler::relaxOnce, MCAssembler::evaluateFixup.
    Why and when: Algorithm 21.10.6 as a fused forward sweep and Algorithm 21.10.10's fixup evaluation. Read relaxOnce after Theorem 21.10.7.
    Cited in: 10-mc-layer-and-object-files

  • [LLVM-PBQP] LLVM's PBQP reduction rules (used by the PBQP register allocator) — llvm/include/llvm/CodeGen/PBQP/ReductionRules.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: applyR1, applyR2, backpropagate.
    Why and when: The R1/R2 reductions of Algorithm 21.4.12 in about 220 lines. Read with Lesson 21.4's PBQP box.
    Cited in: 04-dag-covering

  • [LLVM-PEI] Prologue/epilogue insertion and frame layout — llvm/lib/CodeGen/PrologEpilogInserter.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: PEIImpl::calculateFrameObjectOffsets, PEIImpl::insertPrologEpilogCode, PEIImpl::replaceFrameIndices.
    Why and when: Algorithms 21.9.6 and 21.9.8; shrink-wrapping (Algorithm 21.9.10) is ShrinkWrap.cpp in the same directory.
    Cited in: 09-calling-conventions-and-frames

  • [LLVM-SDCombiner] The SelectionDAG combiner — llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: DAGCombiner::combine, DAGCombiner::visitADD, DAGCombiner::visitMUL.
    Why and when: Algorithm 21.5.4 in production: a worklist of visit* rewrites run at four legality levels. Read visitMUL after Lesson 21.5 §3.
    Cited in: 05-selectiondag

  • [LLVM-SDISel] The SelectionDAG driver and the matcher-table interpreter — llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SelectionDAGISel::CodeGenAndEmitDAG, SelectionDAGISel::SelectCodeCommon, SelectionDAGISel::SelectAllBasicBlocks.
    Why and when: The phase order of Lesson 21.5 (CodeGenAndEmitDAG), Algorithm 21.5.10 (SelectCodeCommon) and FastISel's fallback loop (SelectAllBasicBlocks, Lesson 21.6).
    Cited in: 03-burs-automata, 04-dag-covering, 05-selectiondag

  • [LLVM-TargetLowering] The legalization actions a target declares — llvm/include/llvm/CodeGen/TargetLowering.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: TargetLoweringBase::LegalizeAction, TargetLoweringBase::LegalizeTypeAction, TargetLoweringBase::setOperationAction.
    Why and when: The action enums of Definition 21.5.6 and the setters targets call in their constructors.
    Cited in: 05-selectiondag

  • [LLVM-X86AsmBackend] x86 relaxation and fixup application — llvm/lib/Target/X86/MCTargetDesc/X86AsmBackend.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: X86AsmBackend::fixupNeedsRelaxationAdvanced, X86AsmBackend::relaxInstruction, X86AsmBackend::applyFixup.
    Why and when: The rel8 test (isInt<8>) and JMP_1 to JMP_4 rewrite of Lesson 21.10's relaxation box.
    Cited in: 10-mc-layer-and-object-files

  • [LLVM-X86ISelDAG] x86 SelectionDAG selection hooks (address-mode matching) — llvm/lib/Target/X86/X86ISelDAGToDAG.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: X86DAGToDAGISel::matchAddress, X86DAGToDAGISel::selectAddr.
    Why and when: Handwritten address-mode folding that duplicates shared address arithmetic (Lesson 21.4 §7).
    Cited in: 04-dag-covering

  • [LLVM-X86ISelLowering] x86 legality declarations and custom lowering — llvm/lib/Target/X86/X86ISelLowering.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: X86TargetLowering::X86TargetLowering.
    Why and when: The setOperationAction calls behind Lesson 21.5's legalization tables and the legalization drill's oracle.
    Cited in: 05-selectiondag

  • [LLVM-X86MCEmitter] The x86 instruction encoder — llvm/lib/Target/X86/MCTargetDesc/X86MCCodeEmitter.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: X86MCCodeEmitter::encodeInstruction, X86MCCodeEmitter::emitMemModRMByte, X86MCCodeEmitter::emitREXPrefix.
    Why and when: Algorithm 21.10.2 with all the special cases; read emitMemModRMByte with Proposition 21.10.3.
    Cited in: 10-mc-layer-and-object-files

  • [V8-Baseline] V8's Sparkplug baseline compiler (and Liftoff in src/wasm/baseline/) — src/baseline/baseline-compiler.cc in v8/v8 at 13.6.99.
    Why and when: Template-style code generation straight from bytecode, the macro-expansion design point of Lesson 21.1 §7.
    Cited in: 01-macro-expansion-and-maximal-munch

  • [WT-Winch] Winch, Wasmtime's baseline compiler (one visit method per Wasm operator) — winch/codegen/src/visitor.rs in bytecodealliance/wasmtime at v37.0.2.
    Why and when: Macro expansion in production (Lesson 21.1 §7): compare its output with Cranelift's in the lesson's box.
    Cited in: 01-macro-expansion-and-maximal-munch

Official documentation and specifications

  • [AAPCS64] Procedure Call Standard for the Arm 64-bit Architecture (AArch64). abi-aa 2025Q4. link
    Why and when: The parameter-passing rules (stage C, rules C.1–C.17) that Algorithm 21.9.3 follows. Read them with Lesson 21.9 §2 and compare with the drill's traces.
    Cited in: 09-calling-conventions-and-frames

  • [ELF] Tool Interface Standard (TIS) Executable and Linking Format (ELF) Specification, Version 1.2. link
    Why and when: Sections, symbol tables and REL/RELA relocation records (Definition 21.10.9). Read the "Relocation" section with Lesson 21.10 §3.
    Cited in: 10-mc-layer-and-object-files

  • [GCC-MD] GCC Internals: Machine Descriptions (md.texi). GCC 15. link
    Why and when: define_insn, define_expand, define_split, constraints and predicates: the GCC side of Lesson 21.8. Read "Patterns" and "Constraints" with the lesson's i386.md box.
    Cited in: 08-target-description

  • [Intel-SDM] Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 2 (Instruction Set Reference). link
    Why and when: Ch. 2 (Instruction Format): prefixes, REX, ModRM and SIB with Table 2-2, the basis of Algorithm 21.10.2 and Proposition 21.10.3.
    Cited in: 10-mc-layer-and-object-files

  • [ISLE] ISLE language reference (Cranelift's instruction-selection and rewrite DSL). Wasmtime v37.0.2. link
    Why and when: Terms, extractors, constructors, priorities and the overlap rules of Definitions 21.7.1–21.7.2. Read it with Lesson 21.7 §2.
    Cited in: 07-rewrite-based-selection

  • [LLVM-CodeGenDoc] The LLVM Target-Independent Code Generator. LLVM 23.1.2. link
    Why and when: Core reading. The official overview of the back end: SelectionDAG phases, legalization, scheduling, the MC layer. Read "Instruction Selection" with Lesson 21.5 and "The MC Layer" with Lesson 21.10.
    Cited in: overview, 05-selectiondag, 10-mc-layer-and-object-files

  • [LLVM-GISel] Global Instruction Selection (GlobalISel). LLVM 23.1.2. link
    Why and when: Core reading. GlobalISel's goals (performance, granularity, modularity) and a page per pass. Read the index and the pipeline pages with Lesson 21.6.
    Cited in: overview, 05-selectiondag, 06-globalisel-and-fastisel

  • [LLVM-TableGenRef] TableGen Programmer's Reference. LLVM 23.1.2. link
    Why and when: The exact semantics of classes, defs, let and multiclasses behind Algorithm 21.8.3. Read the "let" and "multiclass" sections with Lesson 21.8 §2.
    Cited in: 08-target-description

  • [MIR-LangRef] Machine IR (MIR) Format Reference Manual. LLVM 23.1.2. link
    Why and when: The textual MIR that every -stop-after box and the labs/ch21-mir tasks print. Keep it open during exercise E5.
    Cited in: 05-selectiondag

  • [PE-COFF] PE Format (Microsoft Portable Executable and Common Object File Format). link
    Why and when: COFF sections, symbols and the x64 relocation types (IMAGE_REL_AMD64_REL32, ADDR32NB) seen in Lesson 21.10's object box. Read "COFF Relocations" after §3.
    Cited in: 10-mc-layer-and-object-files

  • [SysV-ABI] System V Application Binary Interface, AMD64 Architecture Processor Supplement. link
    Why and when: Parameter passing (§3.2.3), the red zone (§3.2.2) and the relocation types (Algorithm 21.9.2, Lesson 21.10 Definition 21.10.9). Read §3.2 with Lesson 21.9.
    Cited in: overview, 09-calling-conventions-and-frames, 10-mc-layer-and-object-files

Talks and videos

  • [Fal23b] Chris Fallin. ægraphs: Acyclic E-graphs for Efficient Optimization in a Production Compiler. EGRAPHS 2023 (PLDI 2023 workshop), invited talk, 2023. link
    Why and when: How Cranelift's mid-end became an acyclic e-graph with elaboration back to a CFG, the design behind Lesson 21.7's aegraph box. Slides; a recorded video is linked from the PLDI 2023 program and on Vimeo.
    Cited in: 07-rewrite-based-selection

Blog posts and articles

  • [Fal23] Chris Fallin. Cranelift's Instruction Selector DSL, ISLE: Term-Rewriting Made Practical. 2023. link
    Why and when: Why Cranelift replaced handwritten lowering with ISLE, and how rules, priorities and the trie compiler work. Read before Lesson 21.7 §2.
    Cited in: 07-rewrite-based-selection

  • [MR25] Fangrui Song. LLVM integrated assembler: Engineering better fragments. 2025. link
    Why and when: A tour of the recent rework of MC fragments (fixed contents plus a variable tail) and relaxation by the engineer who did much of it. Read after Lesson 21.10 §7.
    Cited in: 10-mc-layer-and-object-files