Register Allocation
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.
How does a compiler fit an unlimited number of IR values into sixteen registers?
Machine instructions over *virtual* registers: real target opcodes, but operands that are still IR value names with no physical home. This representation exists precisely so that instruction selection could be decided without deciding storage — and it is the last representation in which a value still has an identity, because after allocation rax may hold four unrelated values at four different points in the function.
Two values may share a physical register only if they are never both live at the same program point — where "live" means the value has been defined and will still be read. Sharing a register between two simultaneously live values silently destroys one of them. The allocator must additionally honour every constraint the target imposes: an instruction with fixed operands (x86 division reads rdx:rax) pins those registers, a call clobbers every caller-saved register, and a value in a callee-saved register obliges the function to save and restore it.
Key points
- The IR names as many values as it likes; the machine has a fixed, small set of registers, and the allocator decides who gets one.
- Two values may share a register exactly when their live ranges do not overlap.
- The lower bound is the peak number of simultaneously live values. Below that, spilling is the program's fault, not the allocator's.
- A spill turns a register operand into a load and a store, which adds instructions, lengthens dependence chains and consumes memory ports.
- The register *count* is rarely the binding constraint. Call-clobbered sets, instructions with fixed operands and ABI-pinned arguments shape the answer more.
- Register pressure is created upstream by inlining, unrolling and scheduling. The allocator receives it and cannot decline.
Seven values, three registers
Here is a whole function's worth of the problem. The IR below computes (a*b - (a+b)) * 2 + a*b and names seven values. Every one of them needs to be somewhere when it is read. If there were seven registers this would be uninteresting; the interesting version is what happens when there are three.
The chart is the allocation our engine produces for exactly this function with three registers available. Read the bars first and the register names second. A bar spans from the point where the value is defined to the point where it is last read — that is its *live range* — and two bars that overlap vertically cannot be given the same register. Where four bars overlap, three registers are not enough, and something has to go to memory.
The value that went to memory is %2, and the reason is worth stating exactly rather than approximately: %2 is live across five instructions and is read only twice, so keeping it in a register reserves scarce storage for a long time in exchange for very little. That ratio — uses per unit of live range — is the spill heuristic, and [[spilling]] is where it is argued properly.
(a*b - (a+b)) * 2 + a*b with three registers availableRead it asThe peak is at point 3, where %0, %1, %2 and %3 are all live — four values, three registers. No allocator can do better than four registers on this function, so the spill is not a failure of the algorithm; the program genuinely demands more storage than it was given. Our engine reports that peak separately (minimumRegisters) so the reader can tell "the allocator did badly" from "the program is this demanding".
Why this is the expensive decision
A register access is part of the instruction. A stack-slot access is a load or a store — an instruction of its own, hitting the L1 cache in the good case and much worse memory in the bad one. Turning a register into a spill slot therefore does not cost a little; it adds instructions to every use, extends the dependence chains through them, and consumes the load and store issue ports that other work wanted.
This is why register allocation is usually described as the most important backend phase, and it is also why it is genuinely hard. The decision problem is graph colouring, which is NP-complete in general, so every real allocator is a heuristic. And unlike most compiler heuristics, the failure mode is not "slightly worse code" — a hot loop that spills a value it uses every iteration can be several times slower than the same loop that does not.
The other half of the difficulty is that the allocator does not control its own inputs. Register pressure is created upstream, by inlining that brought two functions' worth of live values into one body, by unrolling that quadrupled them, and by a scheduler that hoisted loads to hide latency. The allocator is handed the bill and cannot refuse it — see [[phase-ordering]].
- A value in a register: the operand is a register field in the instruction. Zero extra instructions.
- A value in a stack slot: one load before each use, one store after each definition, plus the addressing.
- A value in a callee-saved register: free at each use, and one push in the prologue and one pop in the epilogue.
- A value recomputed instead of stored: the cost of the computation, paid at each use — see
[[coalescing-and-rematerialization]].
What the target dictates
The number of registers is the visible constraint and rarely the binding one. What actually shapes an allocation is the set of *rules* attached to those registers, and every one of them comes from the target and the ABI rather than from the algorithm.
Some registers are destroyed by any call, so a value live across a call must either live in a callee-saved register — which the function must then save and restore — or be spilled around the call. Some instructions demand specific registers: x86 integer division reads rdx:rax and clobbers both, and a variable shift reads its count from cl. Registers alias: writing eax zeroes the upper half of rax, so the allocator cannot treat the two as independent. And arguments arrive in registers the ABI names, which pins several values at the function boundary before the allocator has made a single choice.
| x86-64 System V | AArch64 AAPCS | |
|---|---|---|
| General-purpose registerstarget | 16 named rax…r15 | 31 named x0…x30, plus a zero register |
| Practically allocatabletarget | ~13 — rsp is the stack pointer, rbp usually the frame pointer | ~29 — x29 is the frame pointer, x30 the link register |
| Destroyed by a calltarget | rax rcx rdx rsi rdi r8–r11 | x0–x18 |
| Preserved across a calltarget | rbx rbp r12–r15 | x19–x28 |
| Pinned by instructionstarget | idiv uses rdx:rax; variable shifts use cl | None for integer arithmetic |
| Sub-register aliasingtarget | eax is the low half of rax, and writing it zeroes the top | w0 is the low half of x0, and writing it zeroes the top |
| Practical consequencetarget | Spills are common in numerically dense code; the flags register is a separate contended resource | Pressure is rarely the limit; constant materialisation is a bigger cost |
How it works
The steps, in the order the compiler takes them.
- Liveness analysis runs backwards over the CFG to a fixed point, producing the set of values live at every program point.
- Live ranges are derived from that: each value spans from its definition to its last use, along the linearised instruction order.
- An interference graph is built — a node per value, an edge between any two values live at the same point.
- An allocation algorithm assigns colours (registers) to nodes such that no edge joins two nodes of the same colour, under target constraints.
- Values that cannot be coloured are spilled: they get a stack slot, and a load is inserted before each use and a store after each definition.
- Spilling changes the live ranges — the new loads and stores create tiny new ranges — so a real allocator repeats the whole process until it converges.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- Two simultaneously live values are given the same register, and one is silently destroyed. The wrong answer appears in a caller several frames away with no crash and no diagnostic.
- A value live across a call is left in a caller-saved register, and it comes back holding whatever the callee left there. The corruption is intermittent because it depends on what the callee did.
- A hot loop spills a value used every iteration, and the function is several times slower than the same code compiled with one more available register — or with slightly less inlining upstream.
- The allocator is handed a basic block with ten thousand instructions from a code generator, and compilation time explodes because the interference graph has millions of edges.
- A variable reads as "optimized out" in the debugger for exactly the region the engineer wants to inspect, because its register was reused there and no location entry survives.
When it helps
- Any code at all: this is not an optional optimization. Without allocation there is no way to emit instructions, since instructions take register operands.
- Hot loops in particular, where keeping the working set in registers is frequently the difference between memory-bound and compute-bound.
- Diagnosing performance cliffs: stack traffic inside a loop body in a disassembly is the unambiguous signature of a spill.
When it hurts
- Debug builds, where keeping every variable in its stack slot is worth more than speed, because the debugger can then always find it. That is a large part of what
-O0actually means. - When the pressure came from an upstream decision. Tuning the allocator will not fix spills caused by inlining a large function into a loop body; reducing the inlining will.
What it costs
Every one of these is paid by something.
- Keeping more values in registers buys instruction count and dependence-chain length, and costs the risk that the values chosen were the wrong ones — an allocator that keeps a rarely-used value and spills a hot one is worse than one that spills evenly.
- A better allocator (graph colouring with coalescing and live-range splitting) buys measurably faster code and costs compile time that grows superlinearly with function size, which is why JITs use something worse on purpose.
- Using callee-saved registers buys values that survive calls for free at each use, and costs a push and a pop in every invocation of the function — a bad trade for a function called in a loop and a good one for a function containing a loop.
What else you could do
What a different compiler or language does instead, and when that is better.
- Linear scan: sweep the intervals in start order and never build a graph. Much faster to run, worse code, and the standard choice for a JIT — see
[[linear-scan-allocation]]. - Do not allocate at all: keep every value in a stack slot and load and store around every operation. This is roughly what
-O0produces, and its virtue is that every variable is always inspectable. - A stack machine with no registers: bytecode VMs and WebAssembly sidestep the problem entirely by having no registers to allocate, and push it to whoever compiles that form to real machine code — see
[[stack-based-vm]]. - Optimal allocation by integer programming or PBQP. It exists, it produces better code, and it is far too slow for a general-purpose compiler except in research and in small embedded kernels.
See it for yourself
The flag, dump or tool that shows you this directly.
- Before and after, in LLVM:
llc -print-after=virtregrewriter file.llshows the machine IR once virtual registers have been replaced by physical ones. - What was spilled:
llc -stats file.ll 2>&1 | grep -i spillreports the number of spills and reloads inserted. - In the assembly: look for loads and stores of
[rbp-N]or[rsp+N]inside a loop body. Those are almost always spill code rather than program variables. - GCC:
-fdump-rtl-iraand-fdump-rtl-lradump the integrated and local register allocators' decisions. - Ours:
/compilers/registersrunsallocateByColoringandallocateByLinearScanfromsrc/compilers/sim/regalloc.tson the same function so the two can be diffed directly.
Plausible wrong readings
Stated the way a confident engineer states them.
- "More registers would remove the problem." More registers raises the pressure at which spilling starts and costs more state to save on a call and a context switch. AArch64 has nearly twice as many as x86-64 and still spills.
- "The allocator decides which variables are in registers." It decides which *values* are, and after the middle-end has run, the values often no longer correspond to source variables at all.
- "Spilling means the allocator failed." Below the peak-liveness bound, no allocation exists. The program was asking for more storage than the machine has.
- "Register allocation is a solved problem." Colouring is NP-complete, every production allocator is a heuristic, and the choice of heuristic is still a live engineering decision in every major compiler.
Misconceptions
The claim, and what is actually true.
register keyword in C controls this.Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
The compiler's intermediate form invents a new name for every value it computes, as many as it needs. The processor has sixteen places to put things. Register allocation decides which values get one of those places and which get pushed out to memory, and since a memory access costs an extra instruction while a register access costs nothing, it matters a great deal which ones lose.
practical
The observable signature of an allocation problem is loads and stores of stack offsets inside a loop body. When you see that in a hot function, the fix is usually upstream rather than in the allocator: fewer simultaneously live values, which means less aggressive inlining or unrolling into that loop, or restructuring so that the working set of the inner loop is smaller. Compiling the same function for AArch64 and comparing is a quick way to confirm the problem is pressure rather than something else.
advanced
The framing that repays study is that allocation is where a program stops having variables. Up to this point every value has an identity and a name; afterwards there are sixteen boxes whose contents change meaning every few instructions. Everything downstream that wants to talk about a variable — a debugger, an unwinder, a garbage collector's stack map, a sampling profiler — needs the allocator to have recorded, per program point, where each source-level entity currently lives. That side-table is often larger than the code it describes, and its accuracy under optimization is exactly why [[debugging-optimized-code]] is hard. Register allocation is not just an optimization; it is the phase that makes the program stop resembling itself.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
rbx r12-r15 preserved is x86-64 System V; Windows x64 has the same registers and a larger preserved set including rsi and rdi; AArch64 AAPCS has 31 registers with x19-x28 preserved. The algorithm is identical in all three and the results are not comparable.[[live-ranges]] states what that costs.-O0) is a different, much simpler allocator, is true of LLVM at the time of writing. GCC uses IRA plus LRA. Neither is textbook Chaitin-Briggs, though both descend from it.If you were asked this in an interview
- Why can two values share a register, and what exactly must be true for it to be safe?
- What is the lower bound on the number of registers a function needs, and how would you compute it?
- A hot loop got slower after you enabled more aggressive inlining. Give the most likely mechanism.