Chapter 22 · Register Allocation

Part 5 · Back End · about 3 weeks · Previous: Ch 21 · Next: Ch 23

The problem

After instruction selection (Ch 21) every value lives in a virtual register, and there are as many of them as the program needs. The machine has a small, fixed set of physical registers, split into classes (general-purpose, floating-point, vector) whose members may overlap (eax is part of rax), some of them fixed by the calling convention (arguments, return values, registers clobbered by calls). Register allocation takes a function over virtual registers, with its liveness, the machine's register classes and the constraints of its instructions and calls, and produces an assignment of a physical register to every value at every point where it is live, plus spill code (stores to and loads from stack slots) for values that do not fit, and copies where a value must move between registers. The assignment must be valid (no two simultaneously live values share a register; constraints hold), and it should minimize the executed spill code and copies. In LLVM it runs after PHI elimination, two-address lowering and coalescing, as RAGreedy (-O1 and up) or RegAllocFast (-O0), followed by VirtRegRewriter; in pebblec it is LLVM's, reached through llc. The chapter's lab allocates SSA LLVM IR itself, treating IR values as virtual registers, so that four allocators can be compared under one checker.

What you will be able to do

• Build the interference graph and the live intervals of a function by hand, compute MaxLive, and explain why interference is checked only at definition points (Theorem 22.1.12).
• Trace Belady's MIN, Chaitin's simplify/select, Briggs's optimistic colouring, the Briggs and George coalescing tests, iterated register coalescing, Poletto–Sarkar linear scan, dominance-order colouring of SSA programs and PBQP reductions on small instances, and get the answers of the course's oracles.
• Prove that MIN is optimal, that the Briggs and George tests never turn a colourable graph uncolourable, that SSA interference graphs are chordal and are coloured with MaxLive registers in dominance order, and that rematerialization and spill hoisting preserve values.
• Implement local, Chaitin–Briggs with IRC, linear scan and SSA-based allocators behind one contract, validate them with an independent checker and lli, and measure spills and copies on a corpus (labs/ch22-regalloc).
• Read LLVM's greedy allocator (RegAllocGreedy.cpp, SplitKit.cpp, InlineSpiller.cpp, CalcSpillWeights.cpp) and explain its stages, cascades, splitting, spill weights and rematerialization with llc -stop-after=greedy,1 and -pass-remarks-missed=regalloc.
• Choose an allocator for a JIT tier, an optimizing compiler or an irregular DSP target, and justify the choice with the comparison table.

Prerequisites: Ch 14 (liveness, Definition 14.3.9; the lab calls pebble::dataflow::computeLiveness), Ch 15 (dominator trees, loops and block order), Ch 16 (strict SSA, phis as parallel copies, out-of-SSA translation), Ch 21 (MIR, llc -stop-after, calling conventions and frames). Graph colouring and NP-completeness at the level of an algorithms course.

Notation

Shared notation follows the house notation: §1 (sets, functions, logic), §3 (graphs and CFGs) and §4 (dominance and loops). In this chapter:

Symbol	Meaning
\(\mathcal{R}\), \(\mathcal{R}_c\), \(K_c\)	physical registers; those of class \(c\); their number (Definition 22.1.1). \(K\) when there is one class
\(k\)	number of colours in a graph-colouring statement (the same number as \(K\) when the graph is an interference graph)
\(r \asymp r'\)	registers \(r\) and \(r'\) alias (share storage)
\(\mathcal{R}^{\mathrm{cs}}\)	callee-saved registers; the others are caller-saved (clobbered by calls)
\(V\), \(\mathrm{cls}(v)\)	the values (virtual registers) of a function; the register class of \(v\) (Definition 22.1.2)
\(\mathcal{P}\), \(\mathrm{defs}(p)\), \(\mathrm{live}(p)\)	definition points; values defined at \(p\); values live just after \(p\) (Definition 22.1.4)
\(\mathrm{live\text{-}in}(B)\), \(\mathrm{live\text{-}out}(B)\)	values live at the start and end of block \(B\) (Definition 22.1.3)
\(u \mathbin{\text{—}} v\), \(G_I = (V, E_I)\)	\(u\) and \(v\) interfere; the interference graph (Definition 22.1.5)
\(\rho : V \to \mathcal{R} \cup \{\bot\}\)	an assignment; \(\rho(v) = \bot\) means \(v\) is spilled (Definition 22.1.6)
\(P_c(p)\), \(\mathrm{MaxLive}\)	register pressure at \(p\); its maximum (Definition 22.1.7)
\([s, e]\), slot \(2j\) / \(2j+1\)	a live segment; instruction \(j\) reads at slot \(2j\) and writes at \(2j+1\) (Definition 22.1.8)
\(\deg(v)\), \(\chi(G)\), \(\omega(G)\)	degree; chromatic number; clique number (Definitions 22.3.1, 22.6.1)
\(\mathrm{cost}(v)\), \(d(B)\)	Chaitin's spill cost; loop depth of \(B\), weight \(10^{d(B)}\) (Definition 22.3.2)
\(G / uv\)	the graph with \(u\) and \(v\) merged (coalesced) into one node (Definition 22.4.1)
\(\vec{c}_v\), \(C_{uv}\)	PBQP cost vector of \(v\) and cost matrix of edge \(uv\) (Definition 22.7.1)
\(f(B)\), \(\mathrm{UD}(v)\), \(w(v)\)	relative block frequency; use/def frequency; LLVM spill weight (Definition 22.9.1)
\(\kappa(v)\)	greedy's cascade number of \(v\) (Definition 22.8.1)

Unless stated otherwise, programs are in strict SSA form and a phi operand from predecessor \(P\) is used at the end of \(P\).

Technique map

Family	Techniques (origin)	Lesson
The problem	live ranges and interference graphs (Chaitin et al. 1981); live intervals with holes (Traub, Holloway, Smith 1998; LLVM LiveIntervals); register classes, sub-registers and register units (LLVM); pre-coloured registers and calling conventions	22.1
Local allocation	Belady's MIN / furthest next use (Belady 1966; Horwitz et al. 1966); LLVM's fast allocator (RegAllocFast)	22.2
Graph colouring	Chaitin's allocator (Chaitin et al. 1981; Chaitin 1982); Briggs's optimistic colouring (Briggs, Cooper, Torczon 1994)	22.3
Coalescing	aggressive coalescing (Chaitin 1982); conservative tests (Briggs 1994; George and Appel 1996); iterated register coalescing (George and Appel 1996)	22.4
Linear scan	Poletto–Sarkar (1999); second-chance binpacking (Traub, Holloway, Smith 1998); interval splitting with lifetime holes (Wimmer, Mössenböck 2005); SSA-based linear scan (Wimmer, Franz 2010)	22.5
SSA-based allocation	chordal colouring in dominance order (Hack, Grund, Goos 2006; Brisk et al. 2005; Bouchez et al. 2006); decoupled MaxLive-driven spilling (Hack 2007; Braun, Hack 2009); allocation before SSA destruction (Hack 2007)	22.6
Formulations	PBQP (Scholz, Eckstein 2002; Hames, Scholz 2006); ILP (Goodwin, Wilken 1996; Appel, George 2001)	22.7
LLVM's greedy allocator	priority queue, eviction and cascades (Olesen 2011, LLVM 3.0); live-range splitting (region, block, local, instruction); virtual register rewriting and post-RA copy propagation	22.8
Spilling	spill weights and block frequency (Chaitin 1982; LLVM CalcSpillWeights); rematerialization (Briggs, Cooper, Torczon 1992); spill-code placement (LLVM HoistSpillHelper, Go placeSpills; Chow 1988 for callee-saved registers)	22.9

flowchart LR
  B66[Belady MIN 1966] -->|furthest next use, per block| FAST[RegAllocFast]
  B66 -->|global next-use spilling| DEC[Decoupled spilling<br/>Hack 2007, Braun-Hack 2009]
  C81[Chaitin 1981/82<br/>simplify, select, spill] -->|spill only on actual failure| BR[Briggs optimistic 1994]
  C81 -->|merge copies| AGG[Aggressive coalescing]
  AGG -->|never harm colourability| CONS[Briggs / George tests]
  BR --> IRC[Iterated register coalescing<br/>George-Appel 1996]
  CONS --> IRC
  C81 -->|drop the graph, use intervals| PS[Poletto-Sarkar linear scan 1999]
  PS -->|holes, second chance| SC[Traub et al. 1998]
  PS -->|split at use positions| WM[Wimmer-Moessenboeck 2005]
  WM -->|SSA: one-pass intervals| WF[Wimmer-Franz 2010]
  C81 -->|SSA graphs are chordal| HACK[Hack et al. 2006<br/>colour in dominance order]
  DEC --> HACK
  C81 -->|costs per choice| PBQP[PBQP 2002]
  C81 -->|exact model| ILP[ILP 1996 / 2001]
  C81 -->|priority + splitting| CH[Chow-Hennessy 1990]
  CH --> GREEDY[LLVM greedy 2011<br/>eviction, cascades, splitting]
  SC --> GREEDY
  GREEDY --> RA2[IonMonkey, regalloc2]
  C81 -->|which value, what instead, where| SPILL[Spill weights, remat 1992, placement]
  SPILL --> GREEDY

Who uses what

System	Technique	Notes
LLVM 23	greedy (priority queue, eviction with cascades, region/block/local splitting, frequency-based spill weights, rematerialization, spill hoisting) at -O1 and up; RegAllocFast at -O0; basic and PBQP selectable with -regalloc=; aggressive coalescing before allocation (RegisterCoalescer)	Lessons 22.2, 22.4, 22.7, 22.8, 22.9
GCC 15	IRA: regional Chaitin–Briggs colouring with optimistic spilling over a loop tree; LRA for constraints, reloads and rematerialization (lra-remat.cc)	Lessons 22.3 §7, 22.9 §6
HotSpot C2 (jdk-21+35)	Chaitin–Briggs with aggressive then conservative coalescing and splitting (chaitin.cpp, coalesce.cpp)	Lessons 22.3, 22.4
HotSpot C1, Graal (vm-24.1.0)	linear scan with interval splitting (Wimmer–Mössenböck); Graal also SSA linear scan (Wimmer–Franz)	Lesson 22.5
V8 TurboFan (12.4)	linear scan with splitting, second-chance style spilling and deferred-block spill placement (register-allocator.cc)	Lesson 22.5
Cranelift (regalloc2 0.15.2)	backtracking allocation with bundles, eviction and splitting, derived from IonMonkey; allocation on SSA before destruction	Lessons 22.6, 22.8
Go 1.24 (cmd/compile)	local-style linear allocation over blocks with furthest-next-use eviction, rematerialization of constants and addresses, spill sinking on the dominator tree (regalloc.go)	Lessons 22.2, 22.9
libFirm 1.22	SSA-based allocation: Belady-based spilling, chordal colouring, recolouring for copies (bechordal.c, bespillbelady.c)	Lesson 22.6
SML/NJ (MLRISC, v110.99.9)	iterated register coalescing	Lesson 22.4

The same high-pressure loop (press.c, Lesson 22.3) through LLVM's four allocators, as measured in Lesson 22.7 §7 with llc 23.1.2 (llc -O2 -regalloc=fast|basic|greedy|pbqp; spills / reloads / folded memory operands / instructions):

target	fast	basic	greedy	pbqp
x86-64	39 / 35 / 0 / 156	32 / 20 / 22 / 113	12 / 11 / 3 / 106	21 / 14 / 19 / 101
AArch64	29 / 22 / 33 / 116	17 / 15 / 21 / 97	11 / 9 / 16 / 85	18 / 15 / 20 / 101

Comparison

The rows below are the lessons' §8 tables, gathered in one place (same text as in each lesson). \(N\) = instructions, \(n\) = values, \(e\) = interference edges, \(L\) = values live at a point, \(K\) = registers, \(R\) = spill rounds, \(m\) = registers per PBQP vector.

Lesson 22.1 — The problem: live ranges, interference and constraints

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Interference graph (Chaitin)	exact pairwise conflicts (Theorem 22.1.12); loses where they happen	\(\Theta(N \cdot L)\) build, \(\Theta(n^2)\) worst-case edges · the dominant cost of graph colouring	enables colouring, coalescing tests	moderate (bit matrix + lists)	Chaitin–Briggs, IRC, GCC IRA, HotSpot C2
Live intervals (segments, slot indexes)	exact with holes; hulls over-approximate	linear build · fast queries by segment search	enables linear scan, splitting	moderate	LLVM greedy, V8, HotSpot C1, Graal
Register classes and units	models overlap exactly	set intersection per unit	needed for any real ISA	TableGen-generated in LLVM	every production allocator
Pre-colouring and register masks	exact constraints	one query per call / constraint	may force spills (Go) or CSR saves (LLVM)	small, but pervasive	every production allocator

Lesson 22.2 — Local allocation: Belady's MIN and LLVM's fast allocator

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Belady's MIN	optimal loads for a clean reference string (Theorem 22.2.6); not optimal with stores (Proposition 22.2.7)	\(O(m \log K)\) · negligible	minimal reloads within a block; blind to control flow	tiny	spill choice in Go, libFirm, SSA spillers; lab E0
Local allocation (RegAllocFast, lab E1)	no value in a register across blocks	\(O(N)\) · the fastest LLVM allocator	many spills: 7/7 on the running example at -O0, weighted spill cost ≈ 10× the global allocators in the lab	small	-O0, JIT baseline tiers

Lesson 22.3 — Graph colouring: Chaitin's allocator and Briggs's optimistic colouring

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Chaitin's allocator	colours whenever simplification succeeds; spills whole values; heuristic (NP-complete problem)	\(O(R(NL + n + e))\) · slow on large functions (graph build)	good; spills more than needed on graphs like the square	moderate: build, simplify, select, spill code, iterate	textbooks; historical PL.8; basis of all colouring allocators
Briggs's optimistic colouring	never more spills than Chaitin (Theorem 22.3.9); colours many graphs Chaitin gives up on	same as Chaitin	fewer spills than Chaitin [BCT94]	Chaitin + a few lines	GCC IRA, HotSpot C2, the lab's E2

Lesson 22.4 — Coalescing: aggressive, conservative (Briggs, George) and iterated

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Aggressive coalescing	removes every removable copy; can create spills (Proposition 22.4.7 (ii))	near-linear (union–find) · fast	fewest copies, possibly more spills	small	LLVM RegisterCoalescer + splitting, HotSpot C2 phase 1
Conservative coalescing (Briggs, George)	never breaks simplifiability (Theorems 22.4.8, 22.4.9); refuses many harmless merges when applied once	\(O(\deg)\) per test	no new spills; more copies than aggressive	small	HotSpot C2 phase 2, MLRISC, IRC's tests
Iterated register coalescing	conservative, but retries after simplification: accepts far more merges	close to Chaitin–Briggs; \(O(m \cdot e)\) worst case	few copies and no coalescing-induced spills	large (five worklists, five move states)	Appel's compilers, MLRISC, the lab's E2

Lesson 22.5 — Linear scan: Poletto–Sarkar, second-chance binpacking, interval splitting, SSA

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Poletto–Sarkar linear scan	whole-interval spills; hulls add false conflicts	\(O(n \log n)\) · fastest global allocator	spills by end, not cost; no coalescing	small	early JITs, teaching, the lab's E3
Second-chance binpacking	uses holes; spilled values get registers back	near-linear	close to graph colouring [THS98]	moderate (resolution)	V8 TurboFan (splitting, deferred spills)
Interval splitting (Wimmer–Mössenböck)	split at optimal positions; Belady-style eviction	near-linear	good; spill code outside loops	large	HotSpot C1, Graal, V8
SSA-based linear scan (Wimmer–Franz)	same, plus exact intervals in one pass	linear lifetime analysis	as above, fewer phi moves	large	Graal SSALinearScan

Lesson 22.6 — SSA-based allocation: chordal graphs, MaxLive, decoupled spilling

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Chordal colouring in dominance order	optimal: MaxLive colours (Theorem 22.6.7); needs strict SSA	\(O(N)\) · as fast as linear scan	no spills beyond what spilling decided; copies depend on biased choice/recolouring	small (after liveness and a dominator tree)	libFirm; the lab's E4
Decoupled spilling (MaxLive-driven)	heuristic for an NP-complete problem; exact target (pressure \(\le K\))	linear to quadratic	good with Belady-style global rules [BH09]; spill-everywhere is coarse	moderate	libFirm, Hack's allocator, the lab's E4
Allocation before SSA destruction	phis become register permutations; no out-of-SSA pass before RA	linear	copies only where colours differ	moderate (parallel copies, Lesson 16.7)	regalloc2 (Cranelift), libFirm, Graal SSA LSRA

Lesson 22.7 — Formulations: PBQP and integer linear programming

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
PBQP (Scholz–Eckstein)	models irregular files, preferences, coalescing in one cost function; optimal when R0–RII suffice	\(O(n m^3)\) · slower than greedy in LLVM	near-optimal on irregular architectures [HS06]; on x86 more spills than greedy in the box above	moderate (reductions + back-propagation)	LLVM -regalloc=pbqp (DSP-like targets), research
ILP (Goodwin–Wilken; Appel–George)	provably optimal for its model	exponential · seconds to minutes per function	the best possible within the model	small model, large solver	research baselines, offline code generation

Lesson 22.8 — LLVM's greedy allocator: priority, eviction, splitting, rewriting

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Priority queue, eviction and cascades (basic, greedy)	revisits decisions by eviction; weights decide	near-linear · LLVM's default at -O1+	basic: 32 spills on press; greedy: 12	large (advisors, stages, cascades)	LLVM (all targets), IonMonkey, regalloc2
Live-range splitting (region/block/local/instruction)	spill code only where needed	dominant part of greedy's time	the main reason greedy beats basic and PBQP on x86	very large (SplitKit, SpillPlacement)	LLVM greedy, GCC IRA regions, V8
Rewriting and post-RA copy propagation	exact translation; removes identity/redundant copies	linear	clean output; fewer copies	moderate	every allocator in LLVM; GCC cprop_hardreg

Lesson 22.9 — Spill weights, rematerialization and spill-code placement

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Spill weights and block frequency	ranks candidates by expected spill cost per unit of pressure	linear · negligible	only as good as the frequency estimate	small (formula) plus block frequency analysis	LLVM (CalcSpillWeights), GCC IRA costs, every allocator's spill choice
Rematerialization	removes stores and reloads of recomputable values	per use, constant · negligible	a spilled constant costs one ALU instruction per use	moderate (availability checks)	LLVM InlineSpiller, GCC lra-remat, Go, HotSpot C2
Spill-code placement	stores where they execute least often; optimal per value on the tree	linear per value · small	fewer executed stores on cold paths and outside loops	moderate	LLVM HoistSpillHelper, Go placeSpills, V8 deferred spills

Comparison-lab results (reproduce with build/<preset>/bin/ch22-compare, reference solution; it reads labs/ch22-regalloc/inputs/corpus.ll and 200 random programs, 414 functions in all, and prints \(K = 3, 4, 6, 8\); the rows below are \(K = 4\) per class with two callee-saved registers per class; spill cost and move cost weighted by \(10^{\text{loop depth}}\)):

allocator	spilled values	spill cost	phi moves left	move cost
local (E1)	7007	281309	0	0
Chaitin–Briggs with IRC (E2)	2269	68935	22	112
Poletto–Sarkar linear scan (E3)	2499	105719	1411	21787
★ linear scan with holes (E3★)	1914	77647	1881	26460
SSA colouring in dominance order (E4)	2528	68351	758	6365

Global allocation cuts the spill cost of local allocation by a factor of four; IRC and SSA colouring spill about the same weighted cost, IRC with far fewer copies; plain linear scan pays 50 % more spill cost for its speed, and packing into lifetime holes recovers three quarters of the difference at the price of more copies (local allocation has no register-to-register phi copies because every value that reaches a phi is in memory). At \(K = 8\) the spill costs are 280796 (local), 19691 (IRC), 53701 (linear scan), 26897 (holes) and 24155 (SSA).

Route through this chapter

Step	What	Techniques	How it is exercised
1	Lesson 22.1	interference graphs, live intervals, register classes, pre-colouring	drill interference-graph; the lab's checker and rewriter (provided)
2	Lesson 22.2	Belady's MIN, RegAllocFast	drill belady; lab E0, E1
3	Lesson 22.3	Chaitin, Briggs	drill chaitin-briggs; lab E2
4	Lesson 22.4	aggressive and conservative coalescing, IRC	drill coalescing-test; lab E2
5	Lesson 22.5	Poletto–Sarkar, second chance, Wimmer–Mössenböck, Wimmer–Franz	drill linear-scan; lab E3 (★ E3★ holes)
6	Lesson 22.6	chordal colouring, decoupled spilling, allocation before SSA destruction	drill ssa-coloring; lab E4
7	Lesson 22.7	PBQP, ILP	drill pbqp; theory and solver experiments
8	Lesson 22.8	greedy: eviction, splitting, rewriting	quiz; llc experiments (theory + real tools only)
9	Lesson 22.9	spill weights, rematerialization, spill placement	quiz; llc and Go experiments; exercise E5
10	Exercises: the comparison lab labs/ch22-regalloc/SPEC.md	local vs Chaitin–Briggs/IRC vs linear scan (★ with holes) vs SSA-based colouring, one checker, one rewriter, lli equivalence. Pebble uses LLVM's greedy allocator through llc; the lab's allocators are for comparison	./course test 22, ch22-compare
11	Theory test	all	./course quiz 22 (≥ 80 % to finish)

Practice and check

./course drill interference-graph --difficulty easy   # warm up; --solution shows every step
./course drill belady --seed 4 --solution              # furthest next use, step by step
./course drill chaitin-briggs --difficulty hard        # stack order, actual spills, colours
./course drill coalescing-test                         # Briggs and George verdicts
./course drill linear-scan --difficulty hard           # intervals from a program, then scan
./course drill ssa-coloring --difficulty hard          # dominator-tree order and MaxLive colours
./course drill pbqp                                    # R0/RI/RII reductions
./course flash 22                                      # daily, a few minutes
./course quiz 22                                       # after the lessons
./course test 22                                       # after the exercises
./course status                                        # done = quiz ≥ 80 % and tests pass

References

The chapter's annotated bibliography (papers, textbook sections, pinned source files for LLVM 23.1.2, GCC 15.1, HotSpot, Graal, V8, regalloc2, Go, libFirm and SML/NJ, docs and talks) is in references.md. Start with: [CACCHM81] and [Cha82] (graph colouring), [BCT94] (optimistic colouring), [GA96] (iterated register coalescing), [PS99] and [WM05] (linear scan), [HGG06] and [Hack07] (SSA-based allocation), [SE02] (PBQP), [Ole11] (LLVM's greedy allocator) and [BCT92] (rematerialization); for a textbook route [Appel, Ch. 11] and [EaC3, Ch. 13]. The LLVM files to keep open are [LLVM-Greedy], [LLVM-SplitKit], [LLVM-SpillWeights] and [LLVM-InlineSpiller].