Skip to content

References — Chapter 8 · The Design Space of Intermediate Representations

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

  • [All70] Frances E. Allen. Control Flow Analysis. SIGPLAN Notices 5(7), Proc. Symposium on Compiler Optimization, pp. 1–19, 1970. doi:10.1145/390013.808479
    Why and when: Basic blocks, flow graphs and intervals: the paper that made the CFG the foundation of optimization. Read §2 with Lesson 8.2.
    Cited in: 02-cfgs-and-orders

  • [App98] Andrew W. Appel. SSA is Functional Programming. ACM SIGPLAN Notices 33(4), pp. 17–20, 1998. doi:10.1145/278283.278285
    Why and when: Core reading. A four-page explanation of why "definitions dominate uses" is lexical scoping when blocks become nested functions. Read it before Lesson 8.6 §4.
    Cited in: overview, 06-functional-irs

  • [AWZ88] Bowen Alpern, Mark N. Wegman, and F. Kenneth Zadeck. Detecting Equality of Variables in Programs. POPL 1988, pp. 1–11, 1988. doi:10.1145/73560.73561
    Why and when: One of the two 1988 papers that introduced SSA form, used here for global value numbering by partitioning. Read §1–2 for the motivation of Lesson 8.4.
    Cited in: 03-trees-and-dags, 04-ssa-and-block-arguments

  • [BBH+13] Matthias Braun, Sebastian Buchwald, Sebastian Hack, Roland Leißa, Christoph Mallon, and Andreas Zwinkau. Simple and Efficient Construction of Static Single Assignment Form. CC 2013, LNCS 7791, pp. 102–122, 2013. doi:10.1007/978-3-642-37051-9_6
    Why and when: SSA construction directly from the AST with trivial-phi removal, used by Cranelift's SSABuilder; the trivial-parameter pruning of Lesson 8.4 is its removal rule on block arguments. Implemented in Ch 16.
    Cited in: 04-ssa-and-block-arguments, 07-multi-level-and-pipelines

  • [CCF91] Jong-Deok Choi, Ron Cytron, and Jeanne Ferrante. Automatic Construction of Sparse Data Flow Evaluation Graphs. POPL 1991, pp. 55–66, 1991. doi:10.1145/99583.99594
    Why and when: The origin of pruned SSA (phis only for live variables), the dead-parameter pruning step of Lesson 8.4 §3. Read the introduction.
    Cited in: 04-ssa-and-block-arguments

  • [CFRWZ91] Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph. ACM TOPLAS 13(4), pp. 451–490, 1991. doi:10.1145/115372.115320
    Why and when: Core reading. The SSA paper: definitions, phi placement at iterated dominance frontiers and renaming, plus control dependence. Lesson 8.4 uses its definitions and Lesson 8.5 its control dependence; the construction is taught in Ch 16.
    Cited in: overview, 04-ssa-and-block-arguments, 07-multi-level-and-pipelines

  • [Cli95] Cliff Click. Global Code Motion / Global Value Numbering. PLDI 1995, pp. 246–257, 1995. doi:10.1145/207110.207154
    Why and when: GCM (schedule early, schedule late, choose the least loop depth) and hash-based GVN on the sea of nodes: Algorithm 8.5.3 and its proof. Read §2–3 after Lesson 8.5 §2.
    Cited in: 03-trees-and-dags, 05-graph-irs

  • [CP95] Cliff Click and Michael Paleczny. A Simple Graph-Based Intermediate Representation. ACM SIGPLAN Workshop on Intermediate Representations (IR '95), SIGPLAN Notices 30(3), pp. 35–49, 1995.
    Why and when: Core reading. The sea-of-nodes IR: control and data in one graph, pinned and floating nodes. The origin of Lesson 8.5's first technique; read all of it (it is short).
    Note: Published in the IR '95 workshop issue of SIGPLAN Notices (ACM Digital Library).
    Cited in: overview, 05-graph-irs

  • [DF92] Olivier Danvy and Andrzej Filinski. Representing Control: A Study of the CPS Transformation. Mathematical Structures in Computer Science 2(4), pp. 361–391, 1992. doi:10.1017/S0960129500001535
    Why and when: The one-pass CPS transform that produces no administrative redexes by using meta-level continuations: Algorithm 8.6.3. Read the part on the one-pass transform.
    Cited in: 06-functional-irs

  • [Ers58] A. P. Ershov. On Programming of Arithmetic Operations. Communications of the ACM 1(8), pp. 3–6, 1958. doi:10.1145/368892.368907
    Why and when: An early description of detecting repeated operations with a table of already-computed expressions, the idea behind value numbering (Lesson 8.3). Historical; skim it after Algorithm 8.3.5.
    Cited in: 03-trees-and-dags

  • [FOW87] Jeanne Ferrante, Karl J. Ottenstein, and Joe D. Warren. The Program Dependence Graph and Its Use in Optimization. ACM TOPLAS 9(3), pp. 319–349, 1987. doi:10.1145/24039.24041
    Why and when: Core reading. The PDG: control dependence from post-dominance plus data dependence, and the post-dominator-tree walk of Algorithm 8.5.6. Read §2–3 with Lesson 8.5.
    Cited in: 05-graph-irs

  • [FSDF93] Cormac Flanagan, Amr Sabry, Bruce F. Duba, and Matthias Felleisen. The Essence of Compiling with Continuations. PLDI 1993, pp. 237–247, 1993. doi:10.1145/155090.155113
    Why and when: Core reading. A-normal form: CPS followed by administrative reduction and un-CPS equals direct A-normalization (Theorem 8.6.10). The origin of Lesson 8.6's ANF; read all of it.
    Cited in: overview, 06-functional-irs

  • [HPR88] Susan Horwitz, Jan Prins, and Thomas Reps. On the Adequacy of Program Dependence Graphs for Representing Programs. POPL 1988, pp. 146–157, 1988. doi:10.1145/73560.73573
    Why and when: Proves that programs with isomorphic PDGs are equivalent, under restrictions: the full proof behind Theorem 8.5.11.
    Cited in: 05-graph-irs

  • [HRS+17] Andreas Haas, Andreas Rossberg, Derek L. Schuff, Ben L. Titzer, Michael Holman, Dan Gohman, Luke Wagner, Alon Zakai, and JF Bastien. Bringing the Web up to Speed with WebAssembly. PLDI 2017, pp. 185–200, 2017. doi:10.1145/3062341.3062363
    Why and when: The design of WebAssembly as a validated stack machine with structured control flow; the origin of the structured-stack-code variant in Lesson 8.1 and of its one-pass validation.
    Cited in: 01-linear-irs

  • [IdFC05] Roberto Ierusalimschy, Luiz Henrique de Figueiredo, and Waldemar Celes. The Implementation of Lua 5.0. Journal of Universal Computer Science 11(7), pp. 1159–1176, 2005. pdf
    Why and when: Why Lua moved from a stack VM to a register VM, and how registers are allocated in stack order (§7). Read it with Lesson 8.1's register-bytecode sections and the luac box.
    Cited in: 01-linear-irs

  • [JM03] Neil Johnson and Alan Mycroft. Combined Code Motion and Register Allocation Using the Value State Dependence Graph. CC 2003, LNCS 2622, pp. 1–16, 2003. doi:10.1007/3-540-36579-6_1
    Why and when: The VSDG: value and state edges, γ and θ nodes. The origin of Definition 8.5.5's non-hierarchical version.
    Cited in: 05-graph-irs

  • [Kel95] Richard A. Kelsey. A Correspondence between Continuation Passing Style and Static Single Assignment Form. ACM SIGPLAN Workshop on Intermediate Representations (IR '95), SIGPLAN Notices 30(3), pp. 13–22, 1995.
    Why and when: Core reading. Translations in both directions between SSA and CPS with non-escaping continuations, nesting blocks by the dominator tree: Algorithm 8.6.7 and Theorem 8.6.12.
    Note: Published in the IR '95 workshop issue of SIGPLAN Notices (ACM Digital Library).
    Cited in: 06-functional-irs

  • [Ken07] Andrew Kennedy. Compiling with Continuations, Continued. ICFP 2007, pp. 177–190, 2007. doi:10.1145/1291151.1291179
    Why and when: Argues for CPS with second-class continuations (letcont) over ANF, which duplicates code at joins; the source of Lesson 8.6's pathological family and join-point discussion.
    Cited in: 06-functional-irs

  • [LA04] Chris Lattner and Vikram Adve. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. CGO 2004, pp. 75–86, 2004. doi:10.1109/CGO.2004.1281665
    Why and when: LLVM IR as a typed, SSA-based three-address code. Read §2 with Lesson 8.4 to see which choices of phi-based SSA were made in 2004.
    Cited in: 04-ssa-and-block-arguments

  • [LAB+21] Chris Lattner, Mehdi Amini, Uday Bondhugula, Albert Cohen, Andy Davis, Jacques Pienaar, River Riddle, Tatiana Shpeisman, Nicolas Vasilache, and Oleksandr Zinenko. MLIR: Scaling Compiler Infrastructure for Domain Specific Computation. CGO 2021, pp. 2–14, 2021. doi:10.1109/CGO51591.2021.9370308
    Why and when: Core reading. Dialects, regions, block arguments and progressive lowering: the design of Lesson 8.7's first technique and of the block arguments in Lesson 8.4.
    Cited in: overview, 04-ssa-and-block-arguments, 07-multi-level-and-pipelines

  • [Ler03] Xavier Leroy. Java Bytecode Verification: Algorithms and Formalizations. Journal of Automated Reasoning 30(3–4), pp. 235–269, 2003. doi:10.1023/A:1025055424017
    Why and when: The JVM verifier as dataflow over stack and local types, the trouble with subroutines, and the move to checking stack maps. Read it after Algorithm 8.1.6 to see the typed version of height consistency.
    Cited in: 01-linear-irs

  • [MDAJ17] Luke Maurer, Paul Downen, Zena M. Ariola, and Simon Peyton Jones. Compiling without Continuations. PLDI 2017, pp. 482–494, 2017. doi:10.1145/3062341.3062380
    Why and when: Join points in GHC's direct-style Core: ANF plus second-class local functions, which is the lab's join/loop/jump. Read §2–3 with Lesson 8.6 and the GHC boxes.
    Cited in: 06-functional-irs

  • [NO80] Greg Nelson and Derek C. Oppen. Fast Decision Procedures Based on Congruence Closure. Journal of the ACM 27(2), pp. 356–364, 1980. doi:10.1145/322186.322198
    Why and when: Congruence closure with union-find, the data structure an e-graph is (Definition 8.5.7 and its congruence invariant). Read after Lesson 8.5 §2.
    Cited in: 05-graph-irs

  • [Plo75] Gordon D. Plotkin. Call-by-Name, Call-by-Value and the λ-Calculus. Theoretical Computer Science 1(2), pp. 125–159, 1975. doi:10.1016/0304-3975(75)90017-1
    Why and when: The CPS transform and its correctness (simulation) theorems; the naive transform of Definition 8.6.2. Read the sections on the call-by-value CPS translation.
    Cited in: 06-functional-irs

  • [RMBS20] Nico Reissmann, Jan Christian Meyer, Helge Bahmann, and Magnus Själander. RVSDG: An Intermediate Representation for Optimizing Compilers. ACM Transactions on Embedded Computing Systems 19(6), Article 49, 2020. doi:10.1145/3391902
    Why and when: Core reading. The regionalized VSDG: γ/θ/λ/δ/φ nodes with acyclic regions, construction from a CFG with restructuring, and simple optimizations on it. Read the definitions with Lesson 8.5 §2 and the construction section for the restructuring cost.
    Cited in: 05-graph-irs

  • [RWZ88] Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Global Value Numbers and Redundant Computations. POPL 1988, pp. 12–27, 1988. doi:10.1145/73560.73562
    Why and when: The companion paper to [AWZ88]: SSA names and phi functions as the basis of global redundancy elimination. Historical background for Lesson 8.4.
    Cited in: 04-ssa-and-block-arguments

  • [SGBE05] Yunhe Shi, David Gregg, Andrew Beatty, and M. Anton Ertl. Virtual Machine Showdown: Stack Versus Registers. VEE 2005, pp. 153–163, 2005. doi:10.1145/1064979.1065001 · pdf
    Why and when: Translates JVM stack code to register code; the abstract reports that more than 47% of executed VM instructions are eliminated while code grows by roughly 25%. The empirical side of Proposition 8.1.16 (Lesson 8.1); read the abstract and the dynamic instruction counts.
    Cited in: overview, 01-linear-irs

  • [Tar72] Robert Tarjan. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing 1(2), pp. 146–160, 1972. doi:10.1137/0201010
    Why and when: DFS numbering and the tree/back/forward/cross classification used in Definition 8.2.7 and Lemma 8.2.13; read §2.
    Cited in: 02-cfgs-and-orders

  • [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: The origin of equality saturation as an optimizer: apply rules non-destructively, then extract. Read §1–3 with Lesson 8.5; Ch 17 implements it.
    Cited in: 05-graph-irs

  • [WCES94] Daniel Weise, Roger F. Crew, Michael Ernst, and Bjarne Steensgaard. Value Dependence Graphs: Representation Without Taxation. POPL 1994, pp. 297–310, 1994. doi:10.1145/174675.177907
    Why and when: The VDG, a demand-driven dependence representation without a CFG; the step from the PDG to the VSDG in Lesson 8.5.
    Cited in: 05-graph-irs

  • [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: Core reading. Rebuilding (deferred congruence repair, §3) and e-class analyses (§4): Algorithm 8.5.8 and the egg library of the real-world box. Read §2–4.
    Cited in: 05-graph-irs

Textbooks and monographs

  • [App92] Andrew W. Appel. Compiling with Continuations. Cambridge University Press, 1992. Read: Ch. 1–2 (overview, continuation-passing style), Ch. 5 (conversion into CPS).
    Why and when: How SML/NJ compiled through CPS: the CPS datatype that Lesson 8.6's real-world pointer shows (cexp) and the conversion algorithm. Read Ch. 2 before Lesson 8.6 §2 if CPS is new.
    Cited in: 06-functional-irs

  • [Dragon2] Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools, 2nd ed.. Addison-Wesley, 2006. Read: §6.1 (syntax trees and DAGs, the value-number method), §6.2 (three-address code: quadruples, triples, indirect triples), §8.4 (basic blocks and flow graphs; §8.4.1 leaders), §8.5 (optimization of basic blocks; §8.5.1 the DAG of a block), §9.6 (depth-first ordering).
    Why and when: Core reading. The textbook treatment of Lessons 8.1–8.3: read §6.2 next to Lesson 8.1's quadruple and triple tables, §8.4.1 with the leaders algorithm, and §8.5.1 with local value numbering; its four-statement DAG example is a golden test of the chapter's oracle.
    Cited in: overview, 01-linear-irs, 02-cfgs-and-orders, 03-trees-and-dags

  • [EaC3] Keith D. Cooper and Linda Torczon. Engineering a Compiler, 3rd ed.. Morgan Kaufmann, 2022. Read: Ch. 4 (intermediate representations: graphical and linear IRs, SSA, naming), Ch. 8 (introduction to optimization: local, superlocal and dominator-based value numbering).
    Why and when: The gentlest survey of the whole design space of this chapter (Ch. 4) and the best explanation of value numbering beyond one block (Ch. 8). Read Ch. 4 before Lesson 8.1 if the idea of an IR is new, and Ch. 8 after Lesson 8.3.
    Cited in: 01-linear-irs, 02-cfgs-and-orders, 03-trees-and-dags

  • [SSAbook] Fabrice Rastello and Florent Bouchez Tichadou. SSA-based Compiler Design. Springer, 2022. Read: Part I, Ch. 1–3 (introduction, properties and flavours, construction and destruction); Ch. 6 (functional representations of SSA). doi:10.1007/978-3-030-80515-9
    Why and when: The reference on SSA. Chapters 1–3 back Lesson 8.4 (minimal, pruned and strict SSA); the chapter on functional representations states the SSA/CPS/ANF correspondence of Lesson 8.6 with the dominator-tree nesting in full.
    Cited in: 04-ssa-and-block-arguments

Theses and technical reports

  • [Cli95t] Clifford Noel Click Jr.. Combining Analyses, Combining Optimizations. PhD thesis, Rice University, 1995.
    Why and when: The long form of the sea-of-nodes design and of combining optimizations; background for Lesson 8.5 when [CP95] and [Cli95] are too terse.
    Note: Rice University Ph.D. thesis (also a Rice CS technical report); available from Rice's repository.
    Cited in: 05-graph-irs

  • [CS70] John Cocke and Jacob T. Schwartz. Programming Languages and Their Compilers: Preliminary Notes. Courant Institute of Mathematical Sciences, New York University (2nd revised version), 1970.
    Why and when: The early source usually credited with local value numbering over basic blocks. Cited in Lesson 8.3 for history; the algorithm is taught from [Dragon2] and [EaC3].
    Note: Technical notes; scanned copies circulate in university libraries and archives.
    Cited in: 03-trees-and-dags

  • [Ste78] Guy L. Steele Jr.. Rabbit: A Compiler for Scheme. MIT Artificial Intelligence Laboratory, Technical Report AI-TR-474 (Master's thesis), 1978.
    Why and when: The first compiler to use CPS as its intermediate representation. Historical background for Lesson 8.6 §1.
    Note: MIT AI Lab technical report AI-TR-474; scanned in MIT's DSpace repository.
    Cited in: 06-functional-irs

Source code (pinned versions)

  • [CIR-Src] ClangIR code generation from the Clang AST — clang/lib/CIR/CodeGen/CIRGenStmt.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: CIRGenFunction::emitForStmt.
    Why and when: ClangIR, the MLIR dialect between Clang's AST and LLVM IR (Lesson 8.7); compare with clang/lib/CodeGen/CGStmt.cpp, which emits LLVM IR directly.
    Cited in: 07-multi-level-and-pipelines

  • [CL-Egraph] Cranelift's aegraph mid-end — cranelift/codegen/src/egraph.rs in bytecodealliance/wasmtime at v37.0.2. Symbols: EgraphPass.
    Why and when: A production acyclic e-graph with elaboration back into a CFG (Lesson 8.5 §6); its rewrite rules are ISLE files under cranelift/codegen/src/opts/.
    Cited in: 05-graph-irs

  • [CL-IR-Docs] Cranelift IR reference — cranelift/docs/ir.md in bytecodealliance/wasmtime at v37.0.2. Symbols: Static single assignment form.
    Why and when: "Cranelift does not have phi instructions but uses BB parameters instead": the definition behind Lesson 8.4's Cranelift box.
    Cited in: 04-ssa-and-block-arguments

  • [CL-SSA] Cranelift's SSA construction (Braun et al.) for its front-end helper — cranelift/frontend/src/ssa.rs in bytecodealliance/wasmtime at v37.0.2. Symbols: SSABuilder.
    Why and when: How a producer of block-argument SSA builds it on the fly from variables; compare with Algorithm 8.4.7 and with Ch 16.
    Cited in: 04-ssa-and-block-arguments

  • [Clang-AST] Clang's statement AST classes — clang/include/clang/AST/Stmt.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: ForStmt, IfStmt.
    Why and when: The typed tree dumped in Lesson 8.3's box; Clang keeps for and += as distinct nodes.
    Cited in: 03-trees-and-dags

  • [CPY-Compile] CPython's bytecode compiler (AST to stack bytecode) — Python/compile.c in python/cpython at v3.11.15.
    Why and when: The postorder code generator for CPython's stack bytecode shown by dis in Lesson 8.1; Python/ceval.c is the interpreter.
    Cited in: 01-linear-irs

  • [EGG-Src] The egg e-graph implementation — src/egraph.rs in egraphs-good/egg at v0.11.0. Symbols: EGraph::add, EGraph::union, EGraph::rebuild.
    Why and when: Algorithm 8.5.8's Add, Merge and Rebuild; the Runner of the real-world box is in src/run.rs.
    Cited in: 05-graph-irs

  • [GCC-CFGAnal] GCC's DFS orders over the CFG — gcc/cfganal.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: post_order_compute, pre_and_rev_post_order_compute.
    Why and when: Postorder and RPO as GCC computes them (Lesson 8.2 §7).
    Cited in: 02-cfgs-and-orders

  • [GCC-Expand] GCC's expansion from GIMPLE to RTL — gcc/cfgexpand.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: pass_expand, expand_gimple_basic_block.
    Why and when: The GIMPLE → RTL step of GCC's pipeline (Lesson 8.7).
    Cited in: 07-multi-level-and-pipelines

  • [GCC-GimpleH] GIMPLE statement classes — gcc/gimple.h in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: gassign.
    Why and when: gassign holds one operator and its operands: GCC's quadruple (Definition 8.1.2).
    Cited in: 01-linear-irs

  • [GCC-Gimplify] GCC's gimplifier (GENERIC to GIMPLE three-address code) — gcc/gimplify.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: gimplify_function_tree, gimplify_expr.
    Why and when: Where GCC produces the TAC of Lesson 8.1's GIMPLE box.
    Cited in: 01-linear-irs

  • [GCC-IntoSSA] GCC's SSA construction — gcc/tree-into-ssa.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: pass_build_ssa, insert_phi_nodes.
    Why and when: Where the PHI <…> nodes of Lesson 8.4's GIMPLE SSA box come from.
    Cited in: 04-ssa-and-block-arguments

  • [GCC-SCCVN] GCC's value numbering over SSA, in RPO — gcc/tree-ssa-sccvn.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: do_rpo_vn, run_rpo_vn.
    Why and when: Global value numbering in GCC, named for the traversal order of Lesson 8.2; the global big sibling of Lesson 8.3's local value numbering.
    Cited in: 03-trees-and-dags

  • [GCC-TreeCFG] GCC's GIMPLE CFG construction and critical-edge splitting — gcc/tree-cfg.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: build_gimple_cfg, make_blocks, make_edges, split_critical_edges.
    Why and when: GCC's leaders algorithm (make_blocks) and edges (make_edges); compare with Algorithm 8.2.3 and the -fdump-tree-cfg box of Lesson 8.2.
    Cited in: 02-cfgs-and-orders

  • [GHC-Prep] GHC's CorePrep pass (conversion to A-normal form) — compiler/GHC/CoreToStg/Prep.hs in ghc/ghc at ghc-9.4.7-release. Symbols: corePrepPgm.
    Why and when: "Convert to A-normal form; that is, function arguments are always variables": the pass behind Lesson 8.6's CorePrep box.
    Cited in: 06-functional-irs

  • [GRAAL-SG] Graal's graph IR — compiler/src/jdk.internal.vm.compiler/src/org/graalvm/compiler/nodes/StructuredGraph.java in oracle/graal at vm-23.1.0. Symbols: StructuredGraph.
    Why and when: Graal's sea-of-nodes variant with fixed and floating nodes (Lesson 8.5 §6).
    Cited in: 05-graph-irs

  • [HS-GCM] HotSpot C2's global code motion over the sea of nodes — src/hotspot/share/opto/gcm.cpp in openjdk/jdk at jdk-21-ga. Symbols: PhaseCFG::schedule_early, PhaseCFG::schedule_late, PhaseCFG::global_code_motion.
    Why and when: Algorithm 8.5.3 in production; C2's Node class is in src/hotspot/share/opto/node.hpp.
    Cited in: 05-graph-irs

  • [JLM-RVSDG] jlm's RVSDG implementation (γ nodes; θ nodes in jlm/rvsdg/theta.hpp) — jlm/rvsdg/gamma.hpp in phate/jlm at 4da82da042a7e4bb6f2c1c12a119547bfc659c5b. Symbols: GammaNode.
    Why and when: A working RVSDG compiler by the RVSDG paper's authors; read GammaNode and ThetaNode after Definition 8.5.5.
    Cited in: 05-graph-irs

  • [LLVM-BCE] LLVM's critical-edge splitting — llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SplitCriticalEdge, SplitAllCriticalEdges, BreakCriticalEdgesPass::run.
    Why and when: The break-crit-edges pass of Lesson 8.2's box and the on-demand SplitCriticalEdge; isCriticalEdge is in llvm/lib/Analysis/CFG.cpp.
    Cited in: 02-cfgs-and-orders

  • [LLVM-DDG] LLVM's loop data dependence graph — llvm/include/llvm/Analysis/DDG.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: DataDependenceGraph, PiBlockDDGNode.
    Why and when: The dependence graph printed by print<ddg> in Lesson 8.5; llvm/lib/Analysis/DDG.cpp builds it.
    Cited in: 05-graph-irs

  • [LLVM-EarlyCSE] LLVM's EarlyCSE (dominator-scoped value numbering) — llvm/lib/Transforms/Scalar/EarlyCSE.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SimpleValue, DenseMapInfo<SimpleValue>::getHashValue, EarlyCSEPass::run.
    Why and when: Hash-based value numbering with commutative operands swapped before hashing: the key of Definition 8.3.4 in production (Lesson 8.3's box).
    Cited in: 03-trees-and-dags

  • [LLVM-Mem2Reg] LLVM's mem2reg (phi placement by iterated dominance frontiers) — llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: PromoteMemToReg.
    Why and when: Where the phis of Lesson 8.4's LLVM box and Lesson 8.7's PIR box are placed.
    Cited in: 04-ssa-and-block-arguments

  • [LLVM-RPOT] LLVM's generic postorder and RPO iterators — llvm/include/llvm/ADT/PostOrderIterator.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: post_order, ReversePostOrderTraversal.
    Why and when: An explicit-stack DFS over any GraphTraits graph: Algorithm 8.2.8 in production, used by the RPO box of Lesson 8.2.
    Cited in: 02-cfgs-and-orders

  • [LLVM-SDAG] LLVM's SelectionDAG (a hash-consed DAG per basic block) — llvm/include/llvm/CodeGen/SelectionDAG.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: SelectionDAG, CSEMap.
    Why and when: The expression-DAG IR of LLVM's instruction selector (Ch 21); nodes are CSE'd through FoldingSet<SDNode> CSEMap as they are created.
    Cited in: 03-trees-and-dags

  • [LUA-Opcodes] Lua 5.4 opcode definitions — lopcodes.h in lua/lua at v5.4.6. Symbols: OP_ADD, OP_MODK.
    Why and when: The register instruction formats (R[A] := R[B] % K[C]) of Lesson 8.1's luac box; lcode.c allocates the registers.
    Cited in: 01-linear-irs

  • [MLIR-DialectConv] MLIR's dialect conversion framework — mlir/lib/Transforms/Utils/DialectConversion.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: applyPartialConversion, applyFullConversion, OperationLegalizer.
    Why and when: The legalization driver behind Algorithm 8.7.3; its header mlir/include/mlir/Transforms/DialectConversion.h documents targets and patterns.
    Cited in: 07-multi-level-and-pipelines

  • [MLIR-SCF] Lowering structured control flow (scf) to blocks with arguments (cf) — mlir/lib/Conversion/SCFToControlFlow/SCFToControlFlow.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: ForLowering, IfLowering.
    Why and when: How scf.for's iter_args become block arguments of a loop header (Lessons 8.4 and 8.7).
    Cited in: 07-multi-level-and-pipelines

  • [MLIR-Translate] MLIR to LLVM IR translation (block arguments to phis) — mlir/lib/Target/LLVMIR/ModuleTranslation.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: connectPHINodes.
    Why and when: connectPHINodes turns block arguments into phi entries: Algorithm 8.4.6 (ArgsToPhi) in production, seen in Lesson 8.4's MLIR box.
    Cited in: 04-ssa-and-block-arguments

  • [MLTON-SSA] MLton's SSA IR (blocks with arguments) — mlton/ssa/ssa-tree.sig in MLton/mlton at on-20210117-release. Symbols: Block, Goto.
    Why and when: A functional-language compiler whose SSA uses block arguments and Goto {dst, args}: the SSA side of Theorem 8.6.12 in a production ML compiler.
    Cited in: 06-functional-irs

  • [RUSTC-HIR] rustc's AST-to-HIR lowering of while loops — compiler/rustc_ast_lowering/src/expr.rs in rust-lang/rust at 1.94.1. Symbols: lower_expr_while_in_loop_scope.
    Why and when: Algorithm 8.3.3 in production: while becomes loop { if c {…} else { break } } with LoopSource::While (Lesson 8.3).
    Cited in: 03-trees-and-dags

  • [RUSTC-MIR] rustc's MIR construction — compiler/rustc_mir_build/src/builder/mod.rs in rust-lang/rust at 1.94.1. Symbols: build_mir_inner_impl, construct_fn.
    Why and when: Where MIR bodies are built; the data structures (Body, BasicBlockData, TerminatorKind) are in compiler/rustc_middle/src/mir/. Read with Lesson 8.7's MIR box.
    Cited in: 07-multi-level-and-pipelines

  • [RUSTC-THIR] rustc's THIR (typed high-level tree IR) — compiler/rustc_middle/src/thir.rs in rust-lang/rust at 1.94.1. Symbols: Thir, ExprKind.
    Why and when: The typed tree from which MIR is built (Lessons 8.3 and 8.7).
    Cited in: 03-trees-and-dags

  • [SIL-Docs] Swift Intermediate Language (SIL) reference — docs/SIL.rst in swiftlang/swift at swift-6.1-RELEASE. Symbols: Basic Blocks, Mandatory optimization passes (critical edge splitting).
    Why and when: Core reading. SIL's definition: block arguments as the alternative to phi nodes (quoted in Lesson 8.7) and mandatory critical-edge splitting for non-cond_branch terminators (Lesson 8.2).
    Cited in: 02-cfgs-and-orders, 04-ssa-and-block-arguments, 07-multi-level-and-pipelines

  • [SMLNJ-CPS] SML/NJ's CPS intermediate language — compiler/CPS/cps/cps.sig in smlnj/smlnj at v2025.1. Symbols: cexp, APP, FIX.
    Why and when: The CPS datatype of [App92] as it exists today: APP calls, FIX binds mutually recursive local functions (Lesson 8.6).
    Cited in: 06-functional-irs

  • [SWIFT-CFGOpt] SIL critical-edge splitting — lib/SILOptimizer/Utils/CFGOptUtils.cpp in swiftlang/swift at swift-6.1-RELEASE. Symbols: swift::splitCriticalEdge, swift::splitCriticalEdgesFrom.
    Why and when: Swift's implementation of Definition 8.2.5 for SIL (Lesson 8.2).
    Cited in: 02-cfgs-and-orders

  • [SWIFT-SILArg] SIL block arguments ("phi arguments") — include/swift/SIL/SILArgument.h in swiftlang/swift at swift-6.1-RELEASE. Symbols: SILArgument, SILPhiArgument.
    Why and when: SIL's name for a block parameter that merges values is SILPhiArgument: Theorem 8.4.10 in a class name.
    Cited in: 04-ssa-and-block-arguments

  • [SWIFT-SILGen] SIL generation from the type-checked Swift AST — lib/SILGen/SILGen.cpp in swiftlang/swift at swift-6.1-RELEASE.
    Why and when: The AST → SIL step of swiftc's pipeline (Lesson 8.7); lib/IRGen/IRGenSIL.cpp lowers SIL to LLVM IR.
    Cited in: 07-multi-level-and-pipelines

  • [V8-Ignition] V8 Ignition bytecode definitions (register machine with an accumulator) — src/interpreter/bytecodes.h in v8/v8 at 12.4.254.21.
    Why and when: The list of Ignition bytecodes (Ldar, Star, ModSmi, …) printed by node --print-bytecode in Lesson 8.1.
    Cited in: 01-linear-irs

  • [V8-Scheduler] TurboFan's scheduler (sea of nodes to blocks) — src/compiler/scheduler.cc in v8/v8 at 12.4.254.21. Symbols: Scheduler::ScheduleEarly, Scheduler::ScheduleLate.
    Why and when: The schedule phase of Lesson 8.5's V8 box; Turboshaft's CFG IR is in src/compiler/turboshaft/graph.h.
    Cited in: 05-graph-irs

Official documentation and specifications

  • [Dalvik] Android Open Source Project — Dalvik bytecode and instruction formats. link
    Why and when: Dalvik's register-based bytecode: 16-bit code units and 4-, 8- or 16-bit register fields. The register-VM example of Lesson 8.1 that has no tool in the course container.
    Cited in: 01-linear-irs

  • [GCC-Int] GNU Compiler Collection Internals — GENERIC, GIMPLE, Tree SSA and RTL chapters. GCC 15. link
    Why and when: GCC's own description of its IR pipeline: read the GIMPLE chapter with Lesson 8.1, Tree SSA with Lesson 8.4 and RTL with Lesson 8.7.
    Cited in: 01-linear-irs, 04-ssa-and-block-arguments, 07-multi-level-and-pipelines

  • [JVMS] The Java Virtual Machine Specification, Java SE 21 Edition — Chapter 4 (class files), §4.10 (verification). Java SE 21. link
    Why and when: §4.10.1 (verification by type checking with StackMapTable frames) and §4.10.2 (by type inference) are the production versions of Algorithm 8.1.6; read them after Lesson 8.1.
    Cited in: 01-linear-irs

  • [LLVM-LangRef] LLVM Language Reference Manual. LLVM 23.1.2. link
    Why and when: Read "Well-Formedness", the phi instruction and terminator instructions with Lessons 8.2 and 8.4: LLVM's rules for basic blocks and phi-SSA.
    Cited in: 01-linear-irs, 02-cfgs-and-orders, 04-ssa-and-block-arguments

  • [MLIR-LangRef] MLIR Language Reference (operations, regions, blocks and block arguments, dominance). LLVM 23.1.2. link
    Why and when: The authoritative definition of MLIR blocks with arguments and of region dominance; read "High Level Structure", "Blocks" and "Regions" with Lessons 8.4 and 8.7.
    Cited in: 04-ssa-and-block-arguments, 07-multi-level-and-pipelines

  • [Rustc-Guide] Rust Compiler Development Guide — the MIR, THIR and HIR chapters. link
    Why and when: rustc's IR pipeline explained by its developers: HIR (desugaring), THIR (typed tree) and MIR (CFG of locals and places). Read the MIR overview after Lesson 8.7's MIR box.
    Cited in: 03-trees-and-dags, 07-multi-level-and-pipelines

  • [WasmSpec] WebAssembly Core Specification — Validation (instructions) and the validation algorithm appendix. Release 2.0. link
    Why and when: The typing rules of every instruction and the appendix's one-pass validation algorithm with an operand stack and a control stack: typed height consistency (Lesson 8.1).
    Cited in: 01-linear-irs

Blog posts and articles

  • [Mer25] Darius Mercadier. Land ahoy: leaving the Sea of Nodes. V8 blog, 2025. link
    Why and when: Why V8 replaced TurboFan's sea of nodes with the CFG-based Turboshaft: effect chains that mirror control, hard scheduling, poor cache behavior; compile time divided by 2 and up to 190× faster load elimination. The source of Lesson 8.5's "why V8 left" discussion (not the origin of any technique).
    Cited in: overview, 05-graph-irs