Register Allocation
Many live values, few registers. Live ranges, interference, graph colouring, linear scan, and the spill that turns a register access into a memory access.
The IR assumed an unlimited supply of names. x86-64 has sixteen general-purpose registers and AArch64 has thirty-one. Deciding which values get one, and which go to memory, is the last decision that meaningfully changes how fast the code runs.
A value is live from its definition to its last use, and two values can share a register exactly when their ranges do not overlap. Our engine models ranges without holes — a real simplification, and this lesson says what it costs.
A node per value, an edge whenever two values are live at the same point. Once the program is in this form, register allocation is graph colouring — which is how an NP-complete problem ended up in the middle of every compiler.
Chaitin-Briggs: repeatedly remove any node with fewer than k neighbours and push it on a stack, because such a node is always colourable later. When everything has k or more, push the cheapest optimistically. Then pop and assign.
Sort the intervals by start point, sweep once, hand a register back whenever an interval ends, and when nothing is free spill whichever active interval ends last. Much faster than colouring, worse code — which is exactly the trade a JIT wants.
When there is no register left, a value goes to a stack slot and every use becomes a memory access. The interesting question is never whether to spill but which value — and our engine reports the reason rather than just the outcome.
Two ways to avoid paying. Coalescing merges a copy's source and destination into one register when they do not interfere, deleting the copy. Rematerialization recomputes a cheap value at each use instead of spilling and reloading it.