Skip to content

References — Chapter 24 · The Complete Pebble Compiler — and Beyond

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

  • [BGS00] Rastislav Bodík, Rajiv Gupta, and Vivek Sarkar. ABCD: Eliminating Array Bounds Checks on Demand. PLDI 2000, pp. 321–333, 2000. doi:10.1145/349299.349342
    Why and when: Demand-driven check elimination on e-SSA with a constraint graph; the on-demand shape of LLVM's isKnownPredicateAt queries. Read after Chapter 18's BCE and before Lesson 24.2 §4.
    Cited in: 02-compile-time-vs-run-time

  • [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: SSA as the canonical form every scalar pass assumes (Definition 24.1.3's first example). You built it in Chapter 16; here it is the reason mem2reg is a gate, re-run after inlining.
    Cited in: 01-pipeline-design

  • [Col60] George E. Collins. A Method for Overlapping and Erasure of Lists. Communications of the ACM 3(12), pp. 655–657, 1960. doi:10.1145/367487.367501
    Why and when: Core reading. The origin of reference counting, three pages; read it to see that the cycle problem was visible from the start (Lesson 24.5 §1).
    Cited in: 05-memory-management

  • [CPN98] David G. Clarke, John M. Potter, and James Noble. Ownership Types for Flexible Alias Protection. OOPSLA 1998, pp. 48–64, 1998. doi:10.1145/286936.286947
    Why and when: Core reading. Ownership as a type discipline that restricts aliasing; the ancestor of Rust's model (Lesson 24.5 §1). Read §2–3 for the ownership contexts, then RustBelt for the modern form.
    Cited in: 05-memory-management

  • [CSS99] Keith D. Cooper, Philip J. Schielke, and Devika Subramanian. Optimizing for Reduced Code Space using Genetic Algorithms. LCTES 1999, pp. 1–9, 1999. doi:10.1145/314403.314414
    Why and when: Search over pass orders with a genetic algorithm, per program: the first demonstration that the fixed order is a compromise. The offline variant of Lesson 24.1 §6; read §3–4.
    Cited in: 01-pipeline-design

  • [DB76] L. Peter Deutsch and Daniel G. Bobrow. An Efficient, Incremental, Automatic Garbage Collector. Communications of the ACM 19(9), pp. 522–526, 1976. doi:10.1145/360336.360345
    Why and when: Deferred reference counting: do not count stack references, reconcile periodically; the variant of Lesson 24.5 §6 that every fast counting runtime uses in some form.
    Cited in: 05-memory-management

  • [DMH92] Amer Diwan, Eliot Moss, and Richard Hudson. Compiler Support for Garbage Collection in a Statically Typed Language. PLDI 1992, pp. 273–282, 1992. doi:10.1145/143095.143140
    Why and when: Core reading. Stack maps at safepoints and derived pointers in an optimizing compiler: the origin of Algorithm 24.5.6 and of the (base, derived) pairs. Read §3–4 after Lesson 24.5 §2.
    Cited in: 05-memory-management

  • [DS84] L. Peter Deutsch and Allan M. Schiffman. Efficient Implementation of the Smalltalk-80 System. POPL 1984, pp. 297–302, 1984. doi:10.1145/800017.800542
    Why and when: Core reading. Compile on first use: the origin of lazy compilation (Lesson 24.3 §1). Short; read the section on dynamic translation and compare with the lazy reexport stub.
    Cited in: 03-jit-designs

  • [Gup90] Rajiv Gupta. A Fresh Look at Optimizing Array Bound Checking. PLDI 1990, pp. 272–282, 1990. doi:10.1145/93542.93581
    Why and when: Core reading. Bounds checks as redundancy: a check is removable when a dominating check or a loop invariant implies it. The origin of static check elimination (Algorithm 24.2.3); read §3–4.
    Cited in: 02-compile-time-vs-run-time

  • [HCU92] Urs Hölzle, Craig Chambers, and David Ungar. Debugging Optimized Code with Dynamic Deoptimization. PLDI 1992, pp. 32–43, 1992. doi:10.1145/143095.143114
    Why and when: Core reading. Deoptimization: rebuilding unoptimized frames from optimized ones at safe points, the mechanism behind Algorithm 24.2.7 and Theorem 24.2.10. Read §3–4 after Lesson 24.2 §2.
    Cited in: overview, 02-compile-time-vs-run-time

  • [HU94] Urs Hölzle and David Ungar. Optimizing Dynamically-Dispatched Calls with Run-Time Type Feedback. PLDI 1994, pp. 326–336, 1994. doi:10.1145/178243.178478
    Why and when: Adaptive recompilation of hot methods with feedback from the running program: the tiering pattern that ReOptimizeLayer provides the mechanism for. Read §2–3 after Lesson 24.3 §2.
    Cited in: 03-jit-designs

  • [JJKD17] Ralf Jung, Jacques-Henri Jourdan, Robbert Krebbers, and Derek Dreyer. RustBelt: Securing the Foundations of the Rust Programming Language. Proceedings of the ACM on Programming Languages 2 (POPL 2018), article 66, 2017. doi:10.1145/3158154
    Why and when: The machine-checked proof that Rust's ownership and borrowing guarantee memory safety for a core calculus, and how unsafe code fits. The full proof behind Theorem 24.5.13's sketch.
    Cited in: 05-memory-management

  • [JMG+02] Trevor Jim, Greg Morrisett, Dan Grossman, Michael Hicks, James Cheney, and Yanling Wang. Cyclone: A Safe Dialect of C. USENIX Annual Technical Conference 2002, pp. 275–288, 2002. link
    Why and when: Unique pointers and region types in a C dialect: the bridge between Tofte–Talpin regions, ownership types and Rust. Read §3 (regions) and §5 after Lesson 24.5 §6.
    Cited in: 05-memory-management

  • [KWTD06] Prasad A. Kulkarni, David B. Whalley, Gary S. Tyson, and Jack W. Davidson. Exhaustive Optimization Phase Order Space Exploration. CGO 2006, pp. 306–318, 2006. doi:10.1109/CGO.2006.15
    Why and when: Enumerates every distinct function instance reachable by pass orders (most orders coincide), which is what makes the space searchable; read after Theorem 24.1.12 for how large "pathological" really is in practice.
    Cited in: 01-pipeline-design

  • [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, operations with regions, and progressive lowering as the design; read §2–3 after Lesson 24.7 §1, and §4's case studies to see what "one IR for all levels" bought.
    Cited in: 07-whats-next

  • [Ler09] Xavier Leroy. Formal Verification of a Realistic Compiler. Communications of the ACM 52(7), pp. 107–115, 2009. doi:10.1145/1538788.1538814
    Why and when: Core reading. CompCert in nine pages: semantic preservation as simulation, the pass list, the trusted base. Read it whole after Lesson 24.7 §2, before opening Compiler.v.
    Cited in: overview, 07-whats-next

  • [LLH+21] Nuno P. Lopes, Juneyoung Lee, Chung-Kil Hur, Zhengyang Liu, and John Regehr. Alive2: Bounded Translation Validation for LLVM. PLDI 2021, pp. 65–79, 2021. doi:10.1145/3453483.3454030
    Why and when: Core reading. Refinement for LLVM functions with undef, poison, memory and bounded loops, and the bugs it found. Read §2–4 after Lesson 12.8, then §6 (limitations) with Proposition 24.7.6.
    Cited in: overview, 07-whats-next

  • [McC60] John McCarthy. Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Communications of the ACM 3(4), pp. 184–195, 1960. doi:10.1145/367177.367199
    Why and when: Core reading. The origin of tracing garbage collection (mark from the roots, sweep the rest) in LISP's implementation section; read §4 after Definition 24.5.1.
    Cited in: 05-memory-management

  • [TQB+21] Mircea Trofin, Yundi Qian, Eugene Brevdo, Zinan Lin, Krzysztof Choromanski, and David Li. MLGO: a Machine Learning Guided Compiler Optimizations Framework. arXiv preprint 2101.04808, 2021. link
    Why and when: Learned heuristics inside a fixed pipeline (the inliner's decision, register eviction) as opposed to learned pass orders; the variant of Lesson 24.1 §6. Read §3 to see what stays fixed.
    Cited in: 01-pipeline-design

  • [TT94] Mads Tofte and Jean-Pierre Talpin. Implementation of the Typed Call-by-Value λ-calculus using a Stack of Regions. POPL 1994, pp. 188–201, 1994. doi:10.1145/174675.177855
    Why and when: Core reading. Region inference: allocate every value in a lexically scoped region and free regions as a whole. The origin of Definition 24.5.9; read §2–3, and the later ML Kit papers for the space-leak fix.
    Cited in: 05-memory-management

  • [WS97] Deborah L. Whitfield and Mary Lou Soffa. An Approach for Exploring Code Improving Transformations. ACM TOPLAS 19(6), pp. 1053–1084, 1997. doi:10.1145/267959.267961
    Why and when: Core reading. Pre- and postconditions of transformations, the enabling and disabling relations between them, and a framework (Genesis) for exploring orders. The source of Definition 24.1.2; read §2–3 after Lesson 24.1 §2, and the interaction tables in §4 with the enabling graph of the drill.
    Cited in: overview, 01-pipeline-design

  • [YCER11] Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. Finding and Understanding Bugs in C Compilers. PLDI 2011, pp. 283–294, 2011. doi:10.1145/1993498.1993532
    Why and when: Csmith: random C programs free of undefined behavior, run differentially; the generator of Lab L1 is Csmith's idea for a language where "free of UB" is automatic. §3 has the "no bugs in CompCert's verified passes" result that Lesson 24.7 §1 cites.
    Cited in: 07-whats-next

Textbooks and monographs

  • [JHM11] Richard Jones, Antony Hosking, and Eliot Moss. The Garbage Collection Handbook: The Art of Automatic Memory Management. Chapman & Hall/CRC, 2011. Read: Ch. 5 (reference counting: deferred and coalesced), Ch. 11 (run-time interface: stack maps, safepoints, derived pointers), Ch. 4 (mark–sweep basics).
    Why and when: The reference for everything Lesson 24.5 compresses: read Ch. 11 when the stack-map and base/derived discussion feels thin, Ch. 5 for the counting variants of §6.

Source code (pinned versions)

  • [Alive2] The alive-tv driver and the LLVM-to-Alive translation — tools/alive-tv.cpp in AliveToolkit/alive2 at 01a5ec45c8152995755f7331827407a9de19f262. Symbols: Verifier::compareFunctions.
    Why and when: The commit built in the course container (Chapter 12). alive-tv.cpp pairs functions by name (or --func) and calls Verifier::compareFunctions; llvm_util/llvm2alive.cpp (same commit) is where unreachable becomes assume false in the box's dump, and ir/memory.cpp is the block memory model.
    Cited in: 07-whats-next

  • [CompCert-Compiler] CompCert's pipeline and its correctness theorem — driver/Compiler.v in AbsInt/CompCert at v3.15. Symbols: transf_rtl_program, transf_c_program, transf_c_program_correct, c_semantic_preservation.
    Why and when: Core reading. Lesson 24.1 §7 reads transf_rtl_program as a staged design with Renumber gates; Lesson 24.7 §3–4 reads transf_c_program_correct and the composition of simulations. Read the pass list first, then the theorem statement, then the proof script's structure.
    Cited in: 01-pipeline-design, 07-whats-next

  • [CompCert-Smallstep] CompCert's simulation diagrams — common/Smallstep.v in AbsInt/CompCert at v3.15. Symbols: fsim_properties, forward_simulation, forward_simulation_star, compose_forward_simulations, forward_to_backward_simulation, determinate.
    Why and when: Core reading. Definition 24.7.4 verbatim (fsim_properties), the special cases each pass proof picks, and the forward-to-backward theorem that needs determinism. backend/Inliningproof.v shows a proof that uses forward_simulation_star.
    Cited in: 07-whats-next

  • [GCC-Dwarf2out] GCC's DWARF emitter — gcc/dwarf2out.cc in gcc-mirror/gcc at releases/gcc-15. Symbols: add_location_or_const_value_attribute, loc_list_from_tree, dw_loc_list.
    Why and when: The same location-list construction from GCC's var_loc_list (produced by var-tracking.cc). Skim after Lesson 24.4 §7 for the comparison; the file is enormous, grep the symbols.
    Cited in: 04-debug-info

  • [GCC-IPAPureConst] GCC's nothrow propagation over the call graph — gcc/ipa-pure-const.cc in gcc-mirror/gcc at releases/gcc-15. Symbols: propagate_nothrow, stmt_can_throw_external.
    Why and when: The GCC form of Algorithm 24.6.7: a can_throw summary per function, propagated over ipa_reduced_postorder. Read propagate_nothrow after Lesson 24.6 §7.

  • [GCC-LoopManip] GCC's loop-closed SSA — gcc/tree-ssa-loop-manip.cc in gcc-mirror/gcc at releases/gcc-15. Symbols: rewrite_into_loop_closed_ssa, verify_loop_closed_ssa.
    Why and when: GCC's LCSSA, with a verifier that checks the form after every loop pass: the canonical-form discipline of Lesson 24.1 §7 in GCC.
    Cited in: 01-pipeline-design

  • [GCC-MultipleTarget] GCC's function multiversioning (target_clones) — gcc/multiple_target.cc in gcc-mirror/gcc at releases/gcc-15. Symbols: expand_target_clones, create_dispatcher_calls.
    Why and when: The origin of target_clones: one body per target, a dispatcher resolved through IFUNC. Read expand_target_clones after Lesson 24.2 §7's Clang box.
    Cited in: 02-compile-time-vs-run-time

  • [GCC-PassesDef] GCC's pass tree as a static list — gcc/passes.def in gcc-mirror/gcc at releases/gcc-15. Symbols: NEXT_PASS, PUSH_INSERT_PASSES_WITHIN.
    Why and when: The same staging as LLVM's builder, written as data; count the repeated pass_ccp, pass_fre and pass_dce entries to see the gates and rounds of Lesson 24.1 in another compiler.
    Cited in: 01-pipeline-design

  • [GCC-TreeEH] GCC's GIMPLE exception-handling lowering and cleanup — gcc/tree-eh.cc in gcc-mirror/gcc at releases/gcc-15. Symbols: lower_resx, remove_unreachable_handlers, cleanup_empty_eh, pass_refactor_eh.
    Why and when: What GCC does to EH regions between the front end and RTL: lowering RESX, deleting unreachable and empty handlers. The comparison point for SimplifyCFG's pad removal.

  • [LLVM-Allocator] LLVM's bump-pointer (arena) allocator — llvm/include/llvm/Support/Allocator.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: BumpPtrAllocatorImpl::Allocate, BumpPtrAllocatorImpl::Reset.
    Why and when: A region in practice: slabs, a bump pointer, no per-object free, Reset as the region's end. Every LLVMContext and AST context you used is one; read after Lesson 24.5 §7.
    Cited in: 05-memory-management

  • [LLVM-CGSCC] The CGSCC pass manager and the devirt repeat wrapper — llvm/lib/Analysis/CGSCCPassManager.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: DevirtSCCRepeatedPass::run, ModuleToPostOrderCGSCCPassAdaptor::run.
    Why and when: DevirtSCCRepeatedPass::run is a fixpoint stage with a witness of change (a devirtualized call) and a round limit; read it after Algorithm 24.1.7 to compare with the hash-based rounds.
    Cited in: 01-pipeline-design

  • [LLVM-DIBuilder] The DIBuilder API that E3 uses — llvm/lib/IR/DIBuilder.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: DIBuilder::createCompileUnit, DIBuilder::createFunction, DIBuilder::createAutoVariable, DIBuilder::insertDeclare, DIBuilder::insertDbgValueIntrinsic, DIBuilder::finalize.
    Why and when: Every call pebble-debugify makes, and finalize's handling of retainedNodes. Read createFunction and finalizeSubprogram before writing the pass.
    Cited in: 04-debug-info

  • [LLVM-DwarfDebug] Emitting DWARF from machine code and debug records — llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: DwarfDebug::buildLocationList, DwarfDebug::collectEntityInfo, DwarfDebug::beginInstruction.
    Why and when: Where location lists and the line table are produced from DBG_VALUEs and !dbg locations; read buildLocationList after Algorithm 24.4.7 and Theorem 24.4.10.
    Cited in: 04-debug-info

  • [LLVM-FunctionAttrs] Bottom-up inference of nounwind and friends — llvm/lib/Transforms/IPO/FunctionAttrs.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: InstrBreaksNonThrowing, inferAttrsFromFunctionBodies, PostOrderFunctionAttrsPass::run.
    Why and when: Algorithm 24.6.7 and the check of Proposition 24.6.6; the same file infers nofree, norecurse, memory(...), which Chapter 20's pebble-funcattrs imitates.

  • [LLVM-InlineFunction] Inlining through an invoke — llvm/lib/Transforms/Utils/InlineFunction.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: HandleInlinedLandingPad, HandleInlinedEHPad, HandleCallsInBlockInlinedThroughInvoke.
    Why and when: Algorithm 24.6.8: calls of the copied body become invokes to the caller's pad, resumes become branches, clauses are merged; the funclet variant rewrites parent tokens.

  • [LLVM-InstCombine] InstCombine's worklist and its iteration limit — llvm/lib/Transforms/InstCombine/InstructionCombining.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: InstCombinerImpl::run, combineInstructionsOverFunction.
    Why and when: A fixpoint pass inside a fixpoint pipeline: combineInstructionsOverFunction iterates its worklist with a bounded number of rounds; read after Theorem 24.1.12 for the pathological-case discussion.
    Cited in: 01-pipeline-design

  • [LLVM-IRCE] Inductive range-check elimination by loop splitting — llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: InductiveRangeCheck::extractRangeChecksFromBranch, InductiveRangeCheckElimination::run.
    Why and when: Versioning applied to range checks: split the iteration space into a checked prefix, an unchecked middle and a checked suffix. Read after Lesson 24.2 §6 with Chapter 18's Lesson 18.9.
    Cited in: 02-compile-time-vs-run-time

  • [LLVM-LazyReexports] Lazy reexports: stubs, trampolines and the call-through manager — llvm/lib/ExecutionEngine/Orc/LazyReexports.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: LazyCallThroughManager::resolveTrampolineLandingAddress, LazyCallThroughManager::notifyResolved, LazyReexportsMaterializationUnit.
    Why and when: Definition 24.3.4 and Algorithm 24.3.5 in code: what happens on the first call through a stub, and where a failed lookup lands (ErrorHandlerAddr).
    Cited in: 03-jit-designs

  • [LLVM-LiveDebugValues] LiveDebugValues (the VarLoc-based implementation) — llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: VarLocBasedLDV::transferRegisterDef, VarLocBasedLDV::transferSpillOrRestoreInst, VarLocBasedLDV::join.
    Why and when: Algorithm 24.4.7 in production: the dataflow that propagates variable locations across blocks, with the clobber-at-call and spill/restore transfers of the drill's model.
    Cited in: 04-debug-info

  • [LLVM-LLJIT] LLJIT and LLLazyJIT — llvm/lib/ExecutionEngine/Orc/LLJIT.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: LLJIT::addIRModule, LLJIT::lookup, LLLazyJIT::addLazyIRModule, LLJITBuilderState::prepareForConstruction.
    Why and when: The two configurations behind pebblejit::Session: addIRModule (one unit per module) and addLazyIRModule (one per function through the CompileOnDemand layer). Read prepareForConstruction for the default layer stack.
    Cited in: 03-jit-designs

  • [LLVM-LoopSimplify] The loop-simplify canonicalization — llvm/lib/Transforms/Utils/LoopSimplify.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: simplifyOneLoop, InsertPreheaderForLoop.
    Why and when: The canonical form (Definition 24.1.9's example) that every loop pass of Chapter 18 assumes; FunctionToLoopPassAdaptor re-establishes it before each loop pipeline, the gate of Algorithm 24.1.5.
    Cited in: 01-pipeline-design

  • [LLVM-LoopVersioning] LLVM's loop versioning utility — llvm/lib/Transforms/Utils/LoopVersioning.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: LoopVersioning::versionLoop, LoopVersioning::addPHINodes, LoopVersioning::annotateLoopWithNoAlias.
    Why and when: Algorithm 24.2.5 in production: cloning with cloneLoopWithPreheader, the exit phis, and the noalias scopes that tell later passes the runtime checks passed.
    Cited in: 02-compile-time-vs-run-time

  • [LLVM-PB] PassBuilder's pipeline parser and extension points — llvm/include/llvm/Passes/PassBuilder.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: PassBuilder::parsePassPipeline, PassBuilder::registerPipelineParsingCallback.
    Why and when: What pebble-o1 calls to turn each stage's text into a pass manager; the adaptor syntax (function(...), loop(...), cgscc(...)) is documented in the header comment.
    Cited in: 01-pipeline-design

  • [LLVM-PBP] How LLVM's -O1/-O2/-O3 pipelines are staged — llvm/lib/Passes/PassBuilderPipelines.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: PassBuilder::buildPerModuleDefaultPipeline, PassBuilder::buildModuleSimplificationPipeline, PassBuilder::buildInlinerPipeline, PassBuilder::buildO1FunctionSimplificationPipeline, PassBuilder::buildModuleOptimizationPipeline.
    Why and when: Core reading. The production version of Lesson 24.1's design: read buildPerModuleDefaultPipeline top to bottom with the stage vocabulary (canonicalize, early scalar, inline + devirt<4>, function simplification, loops, late cleanup) and compare with your designCoursePipeline.
    Cited in: overview, 01-pipeline-design

  • [LLVM-RemoveDIs] The debug-record classes — llvm/lib/IR/DebugProgramInstruction.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: DbgVariableRecord, DbgMarker, DbgRecord::insertBefore.
    Why and when: What a #dbg_value is in memory (a DbgVariableRecord hanging off a DbgMarker), which is why instruction counts do not see it. Read alongside [LLVM-DbgRecords].
    Cited in: 04-debug-info

  • [LLVM-ReOpt] ORC's re-optimization layer (tiering by symbol redirection) — llvm/include/llvm/ExecutionEngine/Orc/ReOptimizeLayer.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: ReOptimizeLayer, ReOptimizeLayer::reoptimizeIfCallFrequent, ReOptimizeLayer::CallCountThreshold.
    Why and when: Algorithm 24.3.6: call-count instrumentation, the threshold of 10, and redirection through a RedirectableSymbolManager. The .cpp next to it has the instrumentation IR.
    Cited in: 03-jit-designs

  • [LLVM-RS4GC] Rewriting calls into statepoints with base/derived pairs — llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: findBasePointers, findLiveSetAtInst, RewriteStatepointsForGC::runOnFunction.
    Why and when: Algorithm 24.5.6 in production: liveness at each call, the base pointer of every live value (phis get base phis), and the relocation of derived pointers after the call.
    Cited in: 05-memory-management

  • [LLVM-SimplifyCFG] Where invoke becomes call — llvm/lib/Transforms/Utils/SimplifyCFG.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: removeUnwindEdge, SimplifyCFGOpt::simplifyUnreachable, SimplifyCFGOpt::simplifyCommonResume, SimplifyCFGOpt::simplifySingleResume.
    Why and when: Proposition 24.6.9 in code: removeUnwindEdge rewrites the terminator and the pad loses its predecessor; the resume simplifications remove pads that only re-raise.

  • [LLVM-StackMaps] The stack-map records the back end emits — llvm/lib/CodeGen/StackMaps.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: StackMaps::recordStatepoint, StackMaps::parseOperand, StackMaps::emitCallsiteEntries.
    Why and when: The location kinds (Register, Direct, Indirect, Constant, ConstantIndex) and record layout that llvm-readobj --stackmap prints in Lesson 24.2's box. Read parseOperand to see how a spilled value becomes Indirect.
    Cited in: 02-compile-time-vs-run-time, 05-memory-management

  • [LLVM-StatepointLowering] Lowering a statepoint to a call plus a stack-map record — llvm/lib/CodeGen/SelectionDAG/StatepointLowering.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SelectionDAGBuilder::LowerStatepoint, lowerStatepointMetaArgs.
    Why and when: How the deopt and GC operands of a statepoint become locations: after Lesson 24.2 §7, for the question "where does the Constant 0/0/2 header come from".
    Cited in: 02-compile-time-vs-run-time

  • [LLVM-WasmEHPrepare] Preparing funclet IR for WebAssembly's engine-driven unwinding — llvm/lib/CodeGen/WasmEHPrepare.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: WasmEHPrepareImpl::prepareThrows, WasmEHPrepareImpl::prepareEHPads, WasmEHPrepareImpl::prepareEHPad.
    Why and when: The header comment is the best short description of Wasm EH from the compiler's side (Definition 24.6.4's __wasm_lpad_context); prepareEHPad is Algorithm 24.6.5.

  • [LLVM-WinEHPrepare] Funclet coloring, cloning and state numbering — llvm/lib/CodeGen/WinEHPrepare.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: WinEHPrepareImpl::colorFunclets, WinEHPrepareImpl::cloneCommonBlocks, WinEHPrepareImpl::removeImplausibleInstructions, calculateStateNumbersForInvokes, WinEHPrepareImpl::demotePHIsOnFunclets.
    Why and when: Algorithms 24.6.2 and 24.6.3 in production. Read colorFunclets first (a worklist over blocks with the pad-exit rules), then cloneCommonBlocks.

  • [MLIR-ArithToLLVM] A complete dialect conversion (arith to llvm) — mlir/lib/Conversion/ArithToLLVM/ArithToLLVM.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: ArithToLLVMConversionPass, populateArithToLLVMConversionPatterns, ConstantOpLowering.
    Why and when: The smallest real conversion pass: a target, a type converter, patterns, applyPartialConversion. mlir/test/Conversion/ArithToLLVM/arith-to-llvm.mlir is the worked example of Lesson 24.7 §3.

  • [MLIR-DialectConversion] MLIR's dialect-conversion driver — mlir/lib/Transforms/Utils/DialectConversion.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: OperationLegalizer::legalize, OperationLegalizer::legalizeWithFold, OperationLegalizer::legalizeWithPattern, OperationLegalizer::computeLegalizationGraphBenefit, mlir::applyPartialConversion, mlir::applyFullConversion.
    Why and when: Core reading. Algorithm 24.7.2 in code; mlir/docs/DialectConversion.md (same tag) is the prose ("Modes of Conversion", "Conversion Target") quoted in Definition 24.7.1. Read the doc first, then legalize.
    Cited in: 07-whats-next

  • [Rust-Borrowck] rustc's borrow checker entry point — compiler/rustc_borrowck/src/lib.rs in rust-lang/rust at 1.94.1. Symbols: do_mir_borrowck, MirBorrowckCtxt.
    Why and when: Where the borrow checker runs on MIR: the dataflow analyses it sets up (borrows, moves, initialization) and the error reporting. Read do_mir_borrowck after Algorithm 24.5.8; elaborate_drops.rs next door is Algorithm 24.5.8's ElaborateDrops.
    Cited in: 05-memory-management

  • [Rust-Debuginfo] rustc's MIR locals to debug variables — compiler/rustc_codegen_ssa/src/mir/debuginfo.rs in rust-lang/rust at 1.94.1. Symbols: debug_introduce_local, compute_per_local_var_debug_info.
    Why and when: How a front end with its own IR decides which MIR locals become DILocalVariables and where their #dbg_declare/#dbg_value go; compare with E3's naming rule.
    Cited in: 04-debug-info

  • [Swift-ARCSeqOpts] Swift's ARC pair elimination — lib/SILOptimizer/ARC/ARCSequenceOpts.cpp in swiftlang/swift at swift-6.1-RELEASE. Symbols: ARCSequenceOpts, processFunctionWithoutLoopSupport, processFunctionWithLoopSupport.
    Why and when: The dataflow that pairs a retain with a matching release and deletes both, run twice; the variant of Lesson 24.5 §6. No swiftc in the course container: read the source.
    Cited in: 05-memory-management

  • [V8-Deopt] V8's deoptimizer rebuilding interpreter frames — src/deoptimizer/deoptimizer.cc in v8/v8 at 13.6.233. Symbols: Deoptimizer::DoComputeOutputFrames, Deoptimizer::DoComputeUnoptimizedFrame.
    Why and when: The production form of Algorithm 24.2.7's transfer: translation records to interpreter frames. Read DoComputeOutputFrames after Lesson 24.2 §7 to see how many registers of state a real deopt restores.
    Cited in: 02-compile-time-vs-run-time

Official documentation and specifications

  • [DWARF5] DWARF Debugging Information Format, Version 5. 5 (February 2017). link
    Why and when: Core reading. The standard: §2.5 (location expressions, Definition 24.4.3), §2.6 (location lists), §6.2 (the line-number program). Read §2.5 with the drill dwarf-location open; skip the type-unit and split-DWARF chapters.
    Cited in: overview, 04-debug-info

  • [LLVM-DbgRecords] Debug info migration: from intrinsics to records (RemoveDIsDebugInfo). LLVM 23.1.2. link
    Why and when: Why #dbg_value replaced llvm.dbg.value (Proposition 9.6.11) and how to write a pass against the record API. Read before E3's #dbg_declare insertion.
    Cited in: 04-debug-info

  • [LLVM-EH] Exception Handling in LLVM. LLVM 23.1.2. link
    Why and when: Core reading. The Itanium model (Lesson 11.7) and, in "Exception Handling using the Windows Runtime", the funclet instructions, parent tokens and transition rules quoted in Lesson 24.6 §2. Read that section before Algorithm 24.6.2.
    Cited in: 06-exception-handling-survey

  • [LLVM-GC] Garbage Collection with LLVM. LLVM 23.1.2. link
    Why and when: The two strategies LLVM offers a collector: llvm.gcroot shadow stacks and statepoint stack maps, with the gc "name" attribute and GCStrategy. Read "Built In GC Strategies" after Lesson 24.5 §6.
    Cited in: 05-memory-management

  • [LLVM-ORC] ORC Design and Implementation (ORCv2). LLVM 23.1.2. link
    Why and when: Core reading. JITDylibs, materialization units, lookup, layers, lazy reexports and the design rationale. Read "Design Overview" and "Laziness" before Lab J1, and "Removable code" for the REPL's stretch goal.
    Cited in: overview, 03-jit-designs

  • [LLVM-SourceLevelDebugging] Source Level Debugging with LLVM. LLVM 23.1.2. link
    Why and when: Core reading. The metadata (DICompileUnit, DISubprogram, DILocalVariable, DILocation), the debug records and the rules a pass must obey to keep them truthful. Read "Debug information format" before E3 and "Debug info in optimized code" after Algorithm 24.4.7.
    Cited in: 04-debug-info

  • [LLVM-Statepoints] Garbage Collection Safepoints in LLVM (statepoints). LLVM 23.1.2. link
    Why and when: Core reading. gc.statepoint, gc.relocate, the deopt operand bundle and RewriteStatepointsForGC: the substrate for both deoptimization (Lesson 24.2) and precise GC (Lesson 24.5). Read the "Overview" and "Deoptimization" sections first.
    Cited in: overview, 02-compile-time-vs-run-time, 05-memory-management

  • [Swift-ARCOpt] ARC Optimization in Swift (docs/ARCOptimization.md). Swift 6.1. link
    Why and when: Core reading. Swift's own account of retain/release semantics, owned vs guaranteed conventions, and the optimizer's pairing and code-motion rules. Read "Reference Counting" and "ARC Sequence Optimization" after Algorithm 24.5.3.
    Cited in: 05-memory-management

  • [Swift-Ownership] Swift Ownership Manifesto (docs/OwnershipManifesto.md). Swift 6.1. link
    Why and when: Why a reference-counted language adds ownership (moves, borrows, non-copyable types) on top of ARC: the design space between Lesson 24.5's first and third technique.
    Cited in: 05-memory-management

  • [Wasm-EH] WebAssembly Exception Handling proposal — Exceptions.md. proposal repository, main branch (2023 legacy and 2024 exnref forms). link
    Why and when: Core reading. The instructions (try, catch, catch_all, delegate, rethrow, throw) and their semantics; the "Changes to the text format" section shows the nesting the assembly in Lesson 24.6 §7 uses.
    Cited in: 06-exception-handling-survey