References — Chapter 22 · Register Allocation

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

• [AG01] Andrew W. Appel and Lal George. Optimal Spilling for CISC Machines with Few Registers. PLDI 2001, pp. 243–253, 2001. doi:10.1145/381694.378854
  Why and when: Split the problem: decide optimally by ILP where each value is in a register, then assign registers by coalescing (Algorithm 22.7.7). Read §2–3.
  Cited in: 06-ssa-based-allocation, 07-pbqp-and-ilp, 09-spilling-and-rematerialization

• [BCH+02] Zoran Budimlić, Keith D. Cooper, Timothy J. Harvey, Ken Kennedy, Timothy S. Oberg, and Steven W. Reeves. Fast Copy Coalescing and Live-Range Identification. Proc. ACM SIGPLAN PLDI 2002, 2002. doi:10.1145/512529.512534
  Why and when: In strict SSA, two values interfere iff one is live at the definition of the other (Lemma 22.1.11); the dominance-based interference test behind Lesson 22.6.
  Cited in: 01-the-problem

• [BCT92] Preston Briggs, Keith D. Cooper, and Linda Torczon. Rematerialization. PLDI 1992, 1992. doi:10.1145/143095.143143
  Why and when: Core reading. The origin of rematerialization in a Chaitin–Briggs allocator: tag values with the instruction that computes them by a sparse SSA propagation, split live ranges where the tag changes, and recompute instead of reloading. Read §3–4 with Lesson 22.9.
  Cited in: overview, 09-spilling-and-rematerialization

• [BCT94] Preston Briggs, Keith D. Cooper, and Linda Torczon. Improvements to Graph Coloring Register Allocation. ACM TOPLAS 16(3), pp. 428–455, 1994. doi:10.1145/177492.177575
  Why and when: Core reading. Optimistic colouring (spill only when select fails), the Briggs coalescing test, and the measurements behind "never worse than Chaitin". Read §2–4 with Lessons 22.3 and 22.4.
  Cited in: overview, 03-graph-coloring, 04-coalescing

• [BDGR06] Florent Bouchez, Alain Darte, Christophe Guillon, and Fabrice Rastello. Register Allocation: What Does the NP-Completeness Proof of Chaitin et al. Really Prove?. LCPC 2006 (LNCS, published 2007), 2006. doi:10.1007/978-3-540-72521-3_21
  Why and when: Chaitin's reduction relies on critical edges and copies; without them (SSA, no spilling) the colouring problem is easy. Read after Theorem 22.3.6 and Lesson 22.6.
  Cited in: 03-graph-coloring, 06-ssa-based-allocation

• [BDMS05] Philip Brisk, Foad Dabiri, Jamie Macbeth, and Majid Sarrafzadeh. Polynomial-Time Graph Coloring Register Allocation. International Workshop on Logic and Synthesis (IWLS 2005), pp. 447–454, 2005.
  Why and when: An independent proof that SSA interference graphs are chordal, from high-level synthesis; cited with Theorem 22.6.5.
  Note: Workshop paper (Lake Arrowhead, CA, June 2005); indexed by ResearchGate and the ACM Digital Library.
  Cited in: 06-ssa-based-allocation

• [BDR+09] Benoit Boissinot, Alain Darte, Fabrice Rastello, Benoît Dupont de Dinechin, and Christophe Guillon. Revisiting Out-of-SSA Translation for Correctness, Code Quality, and Efficiency. Proc. 7^th IEEE/ACM International Symposium on Code Generation and Optimization (CGO 2009), 2009. doi:10.1109/CGO.2009.19
  Why and when: Out-of-SSA translation with parallel copies and value-based interference; the step that SSA allocation before destruction replaces by register permutations (Lesson 22.6).
  Cited in: 01-the-problem, 04-coalescing

• [BDR07] Florent Bouchez, Alain Darte, and Fabrice Rastello. On the Complexity of Register Coalescing. CGO 2007, pp. 102–114, 2007. doi:10.1109/CGO.2007.26
  Why and when: Aggressive, conservative, incremental and optimistic coalescing classified by complexity (Theorem 22.4.11); incremental conservative coalescing on chordal graphs is polynomial. Read the summary table first.
  Cited in: 04-coalescing, 06-ssa-based-allocation

• [BDR07b] Florent Bouchez, Alain Darte, and Fabrice Rastello. On the Complexity of Spill Everywhere under SSA Form. LCTES 2007, 2007. doi:10.1145/1273444.1254782 · pdf
  Why and when: Spilling stays NP-complete on SSA and on interval graphs, with the polynomial special cases (Theorems 22.6.11 and 22.9.11). Read the introduction and the summary of results.
  Cited in: 06-ssa-based-allocation, 09-spilling-and-rematerialization

• [BDR08] Florent Bouchez, Alain Darte, and Fabrice Rastello. Advanced Conservative and Optimistic Register Coalescing. CASES 2008, 2008. doi:10.1145/1450095.1450119
  Why and when: Stronger conservative tests and better de-coalescing; read after Lesson 22.4 §6 if you want to go beyond Briggs and George.
  Cited in: 03-graph-coloring, 04-coalescing

• [Bel66] Laszlo A. Belady. A Study of Replacement Algorithms for a Virtual-Storage Computer. IBM Systems Journal 5(2), pp. 78–101, 1966. doi:10.1147/sj.52.0078
  Why and when: Core reading. The furthest-next-use rule (MIN) as the optimum of page replacement; Lesson 22.2 applies it to the registers of one block. Read the description of MIN; the simulations are of historical interest only.
  Cited in: 02-local-allocation

• [BGG+89] David Bernstein, Martin C. Golumbic, Yishay Mansour, Ron Y. Pinter, Dina Q. Goldin, Hugo Krawczyk, and Itai Nahshon. Spill Code Minimization Techniques for Optimizing Compilers. PLDI 1989 (SIGPLAN Notices 24(7)), pp. 258–263, 1989. doi:10.1145/73141.74841
  Why and when: Best-of-three spill heuristics (cost/degree, cost/degree², area-based) and cleaning of spill code; the refinements of Chaitin's metric in Lessons 22.3 §6 and 22.9 §6.
  Cited in: 03-graph-coloring, 09-spilling-and-rematerialization

• [BH09] Matthias Braun and Sebastian Hack. Register Spilling and Live-Range Splitting for SSA-Form Programs. CC 2009 (LNCS), 2009. doi:10.1007/978-3-642-00722-4_13
  Why and when: Belady's rule made global: next-use distances over the CFG, loops counted as far away, and coupling at block borders; the spiller of libFirm and of Lesson 22.6's decoupled spilling.
  Cited in: overview, 02-local-allocation, 06-ssa-based-allocation

• [BHG+08] Benoit Boissinot, Sebastian Hack, Daniel Grund, Benoît Dupont de Dinechin, and Fabrice Rastello. Fast Liveness Checking for SSA-Form Programs. CGO 2008, pp. 35-44, 2008. doi:10.1145/1356058.1356064
  Why and when: Liveness queries without liveness sets; used by SSA-based allocators to test interference on demand (Lesson 22.6 §6).
  Cited in: 01-the-problem, 05-linear-scan, 06-ssa-based-allocation

• [BZB11] Sebastian Buchwald, Andreas Zwinkau, and Thomas Bersch. SSA-Based Register Allocation with PBQP. CC 2011 (LNCS), 2011. doi:10.1007/978-3-642-19861-8_4
  Why and when: PBQP on chordal SSA graphs, reducing along a perfect elimination order; a variant in Lesson 22.7 §6 that joins Lessons 22.6 and 22.7.
  Cited in: 07-pbqp-and-ilp

• [CACCHM81] Gregory J. Chaitin, Marc A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. Markstein. Register Allocation via Coloring. Computer Languages 6(1), pp. 47–57, 1981. link
  Why and when: Core reading. The origin of register allocation as graph colouring and of the definition of interference used in Lesson 22.1 ("a value interferes with everything live where it is defined"). Short; read it after Lesson 22.1 §2, then the NP-completeness argument that Lesson 22.3 revisits.
  Cited in: overview, 01-the-problem, 03-graph-coloring, 04-coalescing

• [CCBS19] Roberto Castañeda Lozano, Mats Carlsson, Gabriel Hjort Blindell, and Christian Schulte. Combinatorial Register Allocation and Instruction Scheduling. ACM TOPLAS 41(3), 2019. link
  Why and when: Unison: allocation and scheduling together as a constraint problem, solved to optimality for most functions of MediaBench and SPEC; the state of the art of the exact approaches in Lesson 22.7 §6.
  Cited in: 07-pbqp-and-ilp

• [CH90] Fred C. Chow and John L. Hennessy. The Priority-Based Coloring Approach to Register Allocation. ACM TOPLAS 12(4), pp. 501–536, 1990. doi:10.1145/88616.88621
  Why and when: Colour live ranges by priority (savings per unit of size) and split instead of spilling; the ancestor of LLVM greedy's priority queue and splitting (Lessons 22.3 §6 and 22.8).
  Cited in: 03-graph-coloring, 08-llvm-greedy

• [Cha82] Gregory J. Chaitin. Register Allocation & Spilling via Graph Coloring. Proc. SIGPLAN '82 Symposium on Compiler Construction (SIGPLAN Notices 17(6)), pp. 98–105, 1982. doi:10.1145/872726.806984 · pdf
  Why and when: Core reading. The allocator of Lesson 22.3: build, coalesce, simplify, spill with cost/degree, select, and iterate after inserting spill code. Eight pages; the spill-cost definition is Definition 22.3.2 and the loop-depth weight \(10^d\) used by the lab comes from here.
  Cited in: overview, 03-graph-coloring, 09-spilling-and-rematerialization

• [Cho88] Fred C. Chow. Minimizing Register Usage Penalty at Procedure Calls. PLDI 1988, 1988. doi:10.1145/53990.53999
  Why and when: Shrink-wrapping: place callee-saved saves and restores only around the region that uses the register, a spill-placement problem for callee-saved registers (Lessons 22.1 §6 and 22.9 §6).
  Cited in: 01-the-problem, 09-spilling-and-rematerialization

• [CK91] David Callahan and Brian Koblenz. Register Allocation via Hierarchical Graph Coloring. PLDI 1991 (SIGPLAN Notices 26(6)), pp. 192–203, 1991. link
  Why and when: Colour a tree of tiles (loops, conditionals) bottom-up and place spill code at tile boundaries in cold code; the regional variant mentioned in Lessons 22.3 §6 and 22.9 §6.
  Cited in: 03-graph-coloring, 09-spilling-and-rematerialization

• [CL95] Martin C. Carlisle and Errol L. Lloyd. On the k-Coloring of Intervals. Discrete Applied Mathematics 59, pp. 225–235, 1995. link · pdf
  Why and when: Maximum k-colourable subsets of interval graphs; why "spill the interval that ends last" is optimal for unit weights and why weights break it (Lesson 22.5 §6).
  Cited in: 05-linear-scan

• [EGS+16] Josef Eisl, Matthias Grimmer, Doug Simon, Thomas Würthinger, and Hanspeter Mössenböck. Trace-based Register Allocation in a JIT Compiler. PPPJ 2016, 2016. doi:10.1145/2972206.2972211
  Why and when: Allocate hot traces with linear scan and cold ones with cheaper strategies (Graal); a variant in Lesson 22.5 §6.
  Cited in: 05-linear-scan

• [FCL00] Martin Farach-Colton and Vincenzo Liberatore. On Local Register Allocation. Journal of Algorithms 37(1), pp. 37–65, 2000. doi:10.1006/jagm.2000.1095
  Why and when: Local allocation with store (write-back) costs is NP-hard, and a 2-approximation exists (Proposition 22.2.7, Theorem 22.9.11). Read the introduction and Theorem 1's statement; the reduction is optional.
  Cited in: 02-local-allocation, 09-spilling-and-rematerialization

• [FG65] Delbert R. Fulkerson and Oliver A. Gross. Incidence Matrices and Interval Graphs. Pacific Journal of Mathematics 15(3), pp. 835–855, 1965. doi:10.2140/pjm.1965.15.835
  Why and when: Chordal graphs are exactly the graphs with a perfect elimination order (Definition 22.6.1, Theorem 22.6.2). Read the characterization; the interval-graph recognition is optional.
  Cited in: 06-ssa-based-allocation

• [GA96] Lal George and Andrew W. Appel. Iterated Register Coalescing. ACM TOPLAS 18(3), pp. 300–324, 1996. doi:10.1145/229542.229546
  Why and when: Core reading. The George test and the worklist algorithm of Lesson 22.4 (Algorithm 22.4.6), with the argument that interleaving coalescing and simplification removes most copies without new spills. Implement E2 from its pseudo-code.
  Cited in: overview, 01-the-problem, 04-coalescing

• [Gav72] Fănică Gavril. Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph. SIAM Journal on Computing 1(2), pp. 180–187, 1972. doi:10.1137/0201013
  Why and when: Optimal colouring of chordal graphs along a perfect elimination order (Theorem 22.6.2). Two pages of the paper are enough.
  Cited in: 06-ssa-based-allocation

• [GW96] David W. Goodwin and Kent D. Wilken. Optimal and Near-optimal Global Register Allocation Using 0-1 Integer Programming. Software: Practice and Experience 26(8), pp. 929–965, 1996.
  Why and when: The first ILP formulation of global allocation with spill placement, copies and rematerialization, solved to optimality on real functions (Lesson 22.7).
  Note: Wiley; Software—Practice and Experience, vol. 26, no. 8 (August 1996).
  Cited in: 07-pbqp-and-ilp

• [HGG06] Sebastian Hack, Daniel Grund, and Gerhard Goos. Register Allocation for Programs in SSA-Form. CC 2006 (LNCS), 2006. doi:10.1007/11688839_20
  Why and when: Core reading. SSA interference graphs are chordal; colour in dominance order with MaxLive colours and spill beforehand (Theorems 22.6.5 and 22.6.7). The shortest route to Lesson 22.6.
  Cited in: overview, 06-ssa-based-allocation

• [HKMW66] L. P. Horwitz, Richard M. Karp, Raymond E. Miller, and Shmuel Winograd. Index Register Allocation. Journal of the ACM 13(1), pp. 43–61, 1966.
  Why and when: Optimal register allocation for straight-line code with store costs, by an exact exponential search; the compiler-side ancestor of Lesson 22.2's MIN and of Proposition 22.2.7's dirty values. Skim the problem statement and the pruning rules.
  Note: In the ACM Digital Library under Journal of the ACM, vol. 13, no. 1 (January 1966).
  Cited in: 02-local-allocation

• [HS06] Lang Hames and Bernhard Scholz. Nearly Optimal Register Allocation with PBQP. JMLC 2006 (LNCS), 2006. doi:10.1007/11860990_21
  Why and when: A better RN heuristic and an evaluation against a branch-and-bound optimum; the design of LLVM's RegAllocPBQP (Lesson 22.7 §7).
  Cited in: overview, 07-pbqp-and-ilp

• [LGA00] Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Fusion-Based Register Allocation. ACM TOPLAS 22(3), pp. 431–470, 2000. doi:10.1145/353926.353929
  Why and when: Allocate regions separately and fuse them along the hottest edges, so that shuffle and spill code lands on cold edges; a placement-aware alternative to global colouring (Lesson 22.9 §6).
  Cited in: 09-spilling-and-rematerialization

• [MGST70] Richard L. Mattson, Jan Gecsei, Donald R. Slutz, and Irving L. Traiger. Evaluation Techniques for Storage Hierarchies. IBM Systems Journal 9(2), pp. 78–117, 1970. pdf
  Why and when: Stack algorithms and a proof that Belady's MIN is optimal; background for Theorem 22.2.6 if you want the original argument rather than the exchange proof in the lesson.
  Cited in: 02-local-allocation

• [PM04] Jinpyo Park and Soo-Mook Moon. Optimistic Register Coalescing. ACM TOPLAS 26(4), 2004. doi:10.1145/1011508.1011512
  Why and when: Coalesce aggressively and undo it for nodes that become actual spills; the alternative to conservative tests in Lesson 22.4 §6.
  Cited in: 03-graph-coloring, 04-coalescing

• [PP05] Fernando Magno Quintão Pereira and Jens Palsberg. Register Allocation via Coloring of Chordal Graphs. APLAS 2005 (LNCS), 2005. doi:10.1007/11575467_21
  Why and when: Most interference graphs of Java methods are chordal even before SSA; a chordal-colouring allocator for JoeQ. Background for Lesson 22.6 §1.
  Cited in: 06-ssa-based-allocation

• [PS99] Massimiliano Poletto and Vivek Sarkar. Linear Scan Register Allocation. ACM TOPLAS 21(5), 1999. doi:10.1145/330249.330250
  Why and when: Core reading. Algorithm 22.5.3 and its spill-furthest-end heuristic, with measurements against colouring. Short; implement E3 from §2.
  Cited in: overview, 01-the-problem, 05-linear-scan

• [SE02] Bernhard Scholz and Erik Eckstein. Register Allocation for Irregular Architectures. LCTES/SCOPES 2002, pp. 139–148, 2002. doi:10.1145/513829.513854
  Why and when: Core reading. PBQP as a model of register allocation and the R0/RI/RII/RN reduction solver (Algorithm 22.7.3). Read §3–4 with the drill pbqp.
  Cited in: overview, 07-pbqp-and-ilp

• [SRH04] Michael D. Smith, Norman Ramsey, and Glenn Holloway. A Generalized Algorithm for Graph-Coloring Register Allocation. PLDI 2004, pp. 277–288, 2004. doi:10.1145/996841.996875 · pdf
  Why and when: Colouring for irregular register files with aliasing and pairs: generalizes the degree test by counting how many registers each neighbour can block (Lesson 22.1 §6, Lesson 22.3 §6).
  Cited in: 01-the-problem

• [ST85] Daniel D. Sleator and Robert E. Tarjan. Amortized Efficiency of List Update and Paging Rules. Communications of the ACM 28(2), pp. 202–208, 1985. doi:10.1145/2786.2793
  Why and when: Competitive analysis of paging: LRU is K-competitive and no deterministic online rule does better. Read the paging section after Lesson 22.2 §6 to see why local allocators that cannot look ahead lose to MIN.
  Cited in: 02-local-allocation

• [THS98] Omri Traub, Glenn Holloway, and Michael D. Smith. Quality and Speed in Linear-scan Register Allocation. PLDI 1998, 1998. doi:10.1145/277650.277714
  Why and when: Second-chance binpacking: pack into lifetime holes, give spilled values a register again at the next use, and resolve locations on edges (Algorithm 22.5.7). Read §3–4.
  Cited in: overview, 05-linear-scan

• [WF10] Christian Wimmer and Michael Franz. Linear Scan Register Allocation on SSA Form. CGO 2010, 2010. doi:10.1145/1772954.1772979
  Why and when: Build lifetime intervals in one backward pass over SSA with contiguous loops, and destroy SSA during resolution (Algorithm 22.5.10, Theorem 22.5.11).
  Cited in: 05-linear-scan

• [WM05] Christian Wimmer and Hanspeter Mössenböck. Optimized Interval Splitting in a Linear Scan Register Allocator. VEE 2005, 2005. doi:10.1145/1064979.1064998
  Why and when: Core reading. The linear scan of HotSpot C1 and Graal: free-until and next-use positions, split at optimal positions, spill-slot resolution (Algorithm 22.5.8). The pseudo-code maps line by line onto c1_LinearScan.cpp.
  Cited in: overview, 05-linear-scan

Textbooks and monographs

• [Appel] Andrew W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998. Read: Ch. 11 (Register Allocation), §11.4 (graph-colouring implementation: the worklists of IRC).
  Why and when: IRC with complete data structures (Algorithm 22.4.6); the C and Java editions share the numbering. Keep §11.4 open while implementing lab E2.
  Cited in: overview, 04-coalescing

• [EaC3] Keith D. Cooper and Linda Torczon. Engineering a Compiler, 3^rd ed.. Morgan Kaufmann, 2022. Read: Ch. 13 (Register Allocation: local allocation, live ranges, global colouring, coalescing, spilling).
  Why and when: The gentlest complete treatment of the chapter's first half; read Ch. 13 alongside Lessons 22.1–22.4 if the proofs feel compressed.
  Cited in: overview, 01-the-problem, 02-local-allocation

• [GJ79] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Read: Appendix A1.1, problem GT4 (graph K-colourability).
  Why and when: The NP-completeness of K-colourability that Theorem 22.3.6 builds on. Use as a lookup: GT4 and its comments on fixed K ≥ 3.
  Cited in: 03-graph-coloring

• [KT06] Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2006. Read: §4.3 (Optimal Caching: A More Complex Exchange Argument).
  Why and when: The textbook exchange-argument proof that furthest-in-future is optimal; compare it with the proof of Theorem 22.2.6.
  Cited in: 02-local-allocation

• [Muchnick] Steven S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997. Read: Ch. 16 (Register Allocation), §16.3 (graph colouring: webs, interference, spill costs).
  Why and when: Webs instead of SSA values and a detailed Chaitin-style allocator; read §16.3 for the non-SSA view of Lesson 22.1.
  Cited in: 01-the-problem

Theses and technical reports

• [Hack07] Sebastian Hack. Register Allocation for Programs in SSA Form. PhD thesis, Universität Karlsruhe (TH), 2007.
  Why and when: The complete SSA-based allocator: chordality, dominance-order colouring, decoupled spilling, recolouring for copies, and register permutations for phis (Lesson 22.6). Chapters 4–5 are the core.
  Note: Published by Universitätsverlag Karlsruhe; the KIT library repository hosts the PDF.
  Cited in: overview, 01-the-problem, 04-coalescing, 06-ssa-based-allocation

Source code (pinned versions)

• [Firm-Belady] libFirm's Belady-based spiller for SSA — ir/be/bespillbelady.c in libfirm/libfirm at libfirm-1.22.0. Symbols: be_spill_belady.
  Why and when: The global next-use spiller of [BH09] that makes pressure fit before colouring (Lesson 22.6).
  Cited in: 02-local-allocation, 06-ssa-based-allocation

• [Firm-Chordal] libFirm's chordal (dominance-order) colouring — ir/be/bechordal.c in libfirm/libfirm at libfirm-1.22.0. Symbols: assign, create_borders.
  Why and when: Algorithm 22.6.6 in production: pressure borders per block, colours assigned walking the dominator tree.
  Cited in: 06-ssa-based-allocation

• [GCC-IRA] GCC's integrated register allocator (regional Chaitin–Briggs colouring) — gcc/ira-color.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: color_allocnos, push_allocnos_to_stack, pop_allocnos_from_stack.
  Why and when: Optimistic colouring over a loop tree; the header comment of gcc/ira.cc (same tag) is the best overview of IRA's regions and cost model.
  Cited in: 01-the-problem, 02-local-allocation, 03-graph-coloring, 04-coalescing, 08-llvm-greedy

• [GCC-LRA] GCC's local register allocator (constraints, reloads, final substitution) — gcc/lra.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: lra.
  Why and when: GCC's rewriter and constraint solver after IRA; lra-constraints.cc (same tag) splits pseudos and inserts reloads (Lessons 22.5 §7 and 22.8 §7).
  Cited in: 05-linear-scan, 08-llvm-greedy

• [GCC-LRARemat] GCC LRA's rematerialization sub-pass — gcc/lra-remat.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: lra_remat.
  Why and when: Rematerialization as an availability dataflow problem; the header comment quoted in Lesson 22.9 §7 states the conditions of Definition 22.9.4.
  Cited in: 09-spilling-and-rematerialization

• [Go-regalloc] Go's SSA register allocator — src/cmd/compile/internal/ssa/regalloc.go in golang/go at go1.24.7. Symbols: regAllocState.allocValToReg, regAllocState.placeSpills, Value.rematerializeable.
  Why and when: Furthest-next-use eviction over blocks, rematerialization of cheap values, and spill sinking on the dominator tree (Lessons 22.2 and 22.9); the header comment explains the design.
  Cited in: 01-the-problem, 02-local-allocation, 05-linear-scan, 09-spilling-and-rematerialization

• [Graal-LSRA] Graal's linear scan register allocator — compiler/src/jdk.graal.compiler/src/jdk/graal/compiler/lir/alloc/lsra/LinearScan.java in oracle/graal at vm-24.1.0. Symbols: LinearScan, LinearScan.allocate.
  Why and when: The Java successor of C1's allocator, with an SSA variant (Lesson 22.5 §7).
  Cited in: 05-linear-scan

• [HS-C1LinearScan] HotSpot C1's linear scan with interval splitting — src/hotspot/share/c1/c1_LinearScan.cpp in openjdk/jdk at jdk-21+35. Symbols: LinearScanWalker::alloc_free_reg, LinearScanWalker::alloc_locked_reg.
  Why and when: Wimmer–Mössenböck in production (Algorithm 22.5.8): free-until and next-use positions, splitting, resolution.
  Cited in: 05-linear-scan

• [HS-Chaitin] HotSpot C2's Chaitin–Briggs allocator — src/hotspot/share/opto/chaitin.cpp in openjdk/jdk at jdk-21+35. Symbols: PhaseChaitin::Register_Allocate, PhaseChaitin::Simplify, PhaseChaitin::Select, LRG::score.
  Why and when: A production Chaitin–Briggs loop with splitting instead of spill-everywhere (Lesson 22.3 §7).
  Cited in: 03-graph-coloring

• [HS-Coalesce] HotSpot C2's aggressive and conservative coalescing — src/hotspot/share/opto/coalesce.cpp in openjdk/jdk at jdk-21+35. Symbols: PhaseAggressiveCoalesce, PhaseConservativeCoalesce.
  Why and when: The two coalescing phases of Lesson 22.4 §7, one after the other.
  Cited in: 04-coalescing

• [LLVM-Basic] LLVM's basic allocator (priority queue, spill interference) — llvm/lib/CodeGen/RegAllocBasic.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: RABasic::selectOrSplit.
  Why and when: The simplest client of RegAllocBase: Algorithm 22.8.2 in under 350 lines; read it before RegAllocGreedy.cpp.
  Cited in: 08-llvm-greedy

• [LLVM-Greedy] LLVM's greedy register allocator — llvm/lib/CodeGen/RegAllocGreedy.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: RAGreedy::selectOrSplitImpl, RAGreedy::tryEvict, RAGreedy::tryRegionSplit, RAGreedy::evictInterference.
  Why and when: Algorithm 22.8.3: stages, eviction with cascades, and the splitting strategies. Follow selectOrSplitImpl top-down after Lesson 22.8 §2.
  Cited in: overview, 08-llvm-greedy

• [LLVM-InlineSpiller] LLVM's inline spiller (rematerialization, folding, spill hoisting) — llvm/lib/CodeGen/InlineSpiller.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: InlineSpiller::reMaterializeFor, InlineSpiller::spillAroundUses, HoistSpillHelper::runHoistSpills.
  Why and when: Algorithms 22.9.7 and 22.9.9: rematerialize before uses, fold stack accesses, and hoist spills of the same value bottom-up on the dominator tree.
  Cited in: overview, 09-spilling-and-rematerialization

• [LLVM-LiveIntervals] LLVM's live interval analysis (segments over slot indexes) — llvm/lib/CodeGen/LiveIntervals.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: LiveIntervals::computeVirtRegInterval, LiveIntervals::getSpillWeight.
  Why and when: How LLVM builds the live intervals of Definition 22.1.8, with holes and value numbers, and the per-instruction spill weight used by Definition 22.9.1.
  Cited in: 01-the-problem

• [LLVM-MCP] LLVM's post-RA machine copy propagation — llvm/lib/CodeGen/MachineCopyPropagation.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: MachineCopyPropagation::forwardUses, MachineCopyPropagation::forwardCopyPropagateBlock.
  Why and when: Forwards and removes the copies that allocation leaves behind; the file header states the legality conditions quoted in Lesson 22.8 §4.
  Cited in: 08-llvm-greedy

• [LLVM-PBQPRA] LLVM's PBQP register allocation graph and solver — llvm/include/llvm/CodeGen/RegAllocPBQP.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: PBQP::RegAlloc::RegAllocSolverImpl::reduce, PBQP::RegAlloc::solve.
  Why and when: The reduction order of Lesson 22.7 §7 (optimal R0–R2 first, then conservatively allocatable nodes, then lowest spill cost per degree); the graph is built in RegAllocPBQP.cpp.
  Cited in: 07-pbqp-and-ilp

• [LLVM-RAFast] LLVM's fast (local) register allocator used at -O0 — llvm/lib/CodeGen/RegAllocFast.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: RegAllocFastImpl::allocateBasicBlock, RegAllocFastImpl::allocateInstruction.
  Why and when: Algorithm 22.2.5: allocate one block bottom-up, spill everything live across block boundaries. Read allocateBasicBlock after Lesson 22.2 §7.
  Cited in: 02-local-allocation

• [LLVM-RegCoalescer] LLVM's register coalescer (value-numbered live intervals) — llvm/lib/CodeGen/RegisterCoalescer.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: JoinVals::analyzeValue, JoinVals::valuesIdentical, RegisterCoalescer::joinCopy.
  Why and when: LLVM's aggressive coalescing before allocation (Lesson 22.4 §7): copies of one value do not interfere, and greedy's splitting undoes merges that hurt.
  Cited in: 04-coalescing

• [LLVM-SpillPlacement] LLVM's spill placement analysis (Hopfield network over edge bundles) — llvm/lib/CodeGen/SpillPlacement.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SpillPlacement::iterate, SpillPlacement::update.
  Why and when: The energy function in the file header is the objective quoted in Lesson 22.8 §4; used by region splitting to decide where a value lives in a register.
  Cited in: 08-llvm-greedy

• [LLVM-SpillWeights] LLVM's spill weight computation — llvm/lib/CodeGen/CalcSpillWeights.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: VirtRegAuxInfo::weightCalcHelper, VirtRegAuxInfo::isRematerializable, VirtRegAuxInfo::allUsesAvailableAt.
  Why and when: Definition 22.9.1 and Algorithm 22.9.3 in code, including the remat halving, the hint boost and the loop-exit factor; normalizeSpillWeight is in CalcSpillWeights.h.
  Cited in: overview, 09-spilling-and-rematerialization

• [LLVM-SplitKit] LLVM's live-range splitting machinery — llvm/lib/CodeGen/SplitKit.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SplitAnalysis, SplitEditor::finish.
  Why and when: How greedy's split decisions become new intervals and lr-split copies (Proposition 22.8.7).
  Cited in: overview, 08-llvm-greedy

• [LLVM-VirtRegMap] LLVM's virtual register map and rewriter — llvm/lib/CodeGen/VirtRegMap.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: VirtRegRewriter::rewrite, VirtRegRewriter::handleIdentityCopy.
  Why and when: Algorithm 22.8.8: replace virtual registers by physical ones and delete identity copies.
  Cited in: 08-llvm-greedy

• [LLVM29-LinScan] LLVM 2.9's linear scan allocator (removed in LLVM 3.0) — llvm/lib/CodeGen/RegAllocLinearScan.cpp in llvm/llvm-project at llvmorg-2.9.0. Symbols: RALinScan::linearScan.
  Why and when: The historical LLVM default before greedy; read it after Lesson 22.5 to see linear scan with live intervals in production code.
  Cited in: 05-linear-scan

• [MLRISC-RA] SML/NJ MLRISC's iterated register coalescing core — MLRISC/ra/ra-core.sml in smlnj/legacy at v110.99.9.
  Why and when: IRC as written by George and Appel's colleagues, with Briggs and George counters (Lesson 22.4 §7).
  Cited in: 04-coalescing

• [RA2-Design] regalloc2's design notes (Cranelift's register allocator) — doc/GENERAL.md in bytecodealliance/regalloc2 at v0.15.2.
  Why and when: SSA input with block parameters, bundles, eviction and splitting; the README at the same tag describes regalloc2 as a port of IonMonkey's backtracking allocator (Lessons 22.6 and 22.8).
  Cited in: 06-ssa-based-allocation, 08-llvm-greedy

• [V8-RegAlloc] V8 TurboFan's linear scan register allocator — src/compiler/backend/register-allocator.cc in v8/v8 at 12.4.254.21. Symbols: LinearScanAllocator::AllocateRegisters, TopLevelLiveRange.
  Why and when: Linear scan with splitting, deferred-block spilling and gap moves (Lessons 22.5 and 22.9).
  Cited in: 05-linear-scan

Official documentation and specifications

• [LLVM-CodeGenDoc] The LLVM Target-Independent Code Generator. LLVM 23.1.2. link
  Why and when: The "Register Allocation" section: virtual and physical registers, register classes and units, live intervals, and the available allocators; read it with Lesson 22.1.
  Cited in: 01-the-problem

Blog posts and articles

• [Ole11] Jakob Stoklund Olesen. Greedy Register Allocation in LLVM 3.0. 2011. link
  Why and when: Core reading. The design rationale of greedy by its author: why not linear scan, the priority queue, eviction, live-range splitting and its measurements. Read before Lesson 22.8; the slides of his 2011 LLVM Developers' Meeting talk (llvm.org/devmtg/2011-11) add pictures of splitting.
  Cited in: overview, 08-llvm-greedy