register allocation
Inside the IR the compiler pretends it has an unlimited supply of named slots for values — virtual registers, as many as it likes. But a real processor has only a small, fixed set of fast registers (something like 16 general-purpose ones on x86-64). Register allocation is the back-end job of mapping those unlimited virtual registers onto the few real ones, deciding which values get to live in a register at any moment.
The core difficulty is that two values can share one real register only if they are not needed at the same time. The compiler computes each value's live range (the span of code from its definition to its last use) and asks: which values are live simultaneously? Values that overlap conflict and must get different registers. This is naturally modeled as graph coloring: make each value a node, draw an edge between values whose live ranges overlap, and color the graph with as many colors as there are registers so no two connected nodes share a color. Coloring is hard in general, so compilers use heuristics. A faster alternative used in just-in-time compilers is linear scan, which sweeps the live ranges in order and assigns registers greedily, trading some quality for speed. When there are simply not enough registers for all the simultaneously-live values, some must be spilled — kept in memory on the stack and loaded back when needed.
It matters because keeping a value in a register versus memory is the difference between an instruction that runs in well under a nanosecond and one that may wait on a cache or memory access; good allocation is a large part of why -O2 code is fast. A caveat: register allocation is invisible in your source but very visible in the generated assembly — and it is why a function with many simultaneously-live variables generates stack loads and stores you never asked for (spills). It also interacts with everything around it: aggressive inlining or CSE that lengthens live ranges can increase register pressure and force more spilling, so an optimization that looks like a pure win upstream can cost you here.
// virtual: %a,%b,%c,%d,%e all live at once, but only ~16 real registers exist. // build an interference graph (edges = overlapping live ranges), color it with // register names. If too many overlap, spill one to the stack: // mov [rsp-8], rax ; spill // ... ; reuse rax for another value // mov rax, [rsp-8] ; reload before its next use
Values whose live ranges overlap need different registers; when the chip runs out, the allocator spills to the stack.
Optimal register allocation is computationally hard (graph coloring), so compilers use heuristics; and upstream passes that lengthen live ranges (aggressive inlining, CSE) raise register pressure, meaning a 'pure win' earlier can force extra spills here.