Compilers · Cluster
Register Allocation
Graph coloring, spilling, and calling conventions.
- 01 Live Ranges as the Input to Register Allocation How backward liveness analysis turns a control-flow graph into the per-value program points that every allocator reasons over, and where that abstraction stops being exact.
- 02 Building the Interference Graph from Live Sets The exact rules that turn per-instruction liveness into graph edges, why move instructions are treated differently, and how the graph representation affects the cost of coloring.
- 03 The Simplify and Select Loop of Chaitin-Style Coloring Why coloring a register interference graph is done by repeatedly removing low-degree nodes and pushing them back on a stack, what the degree test really guarantees, and when the greedy result is optimal.
- 04 Spill Cost Heuristics and the Choice of Victim How allocators price a virtual register in loads and stores, why the cost-to-degree ratio is the wrong objective in loops, and what the reload placement problem looks like after spilling.
- 05 Conservative Coalescing and the Conditions That Make It Safe Why merging the source and destination of a move can make a colorable graph uncolorable, and how the Briggs and George tests decide when the merge is guaranteed not to hurt.
- 06 Linear Scan Allocation over Sorted Live Intervals How a single pass over intervals ordered by start point assigns registers, why active-list eviction beats spilling the current interval, and what the interval approximation gives up.
- 07 Calling Conventions as Precolored Constraints on the Graph How the ABI fixes which registers hold arguments, returns, and preserved values, and how those obligations enter the interference graph as edges to nodes that already have a color.
- 08 Live-Range Splitting at Region Boundaries Why a value that is live in two distant regions is better allocated as two values, how splitting interacts with spilling, and what the extra moves cost at the join.
- 09 Chordal Interference Graphs and Optimal Coloring in SSA Form Why the interference graph of an SSA program has no induced cycles longer than three, how a perfect elimination ordering yields a minimum coloring in linear time, and what destroying SSA costs.
- 10 Partitioned Boolean Quadratic Programming for Register Allocation How encoding allocation as per-node costs plus per-edge cost matrices lets a solver trade spills against copies with a single objective, and why reduction rules beat coloring heuristics on hard graphs.