The promise the back end has to break
Through the whole middle end, the IR has been living a comfortable lie. In SSA form it minted a fresh name for every value — x1, x2, t37, as many as it pleased — and the optimizer reasoned as if storage were free and infinite. That fiction is exactly what made the optimizations of the previous guides so clean. But a real CPU does not have infinitely many named slots. An x86-64 core has roughly sixteen general-purpose registers (rax, rbx, rcx, rdx, rsi, rdi, rsp, rbp, and r8 through r15), and rsp is spoken for as the stack pointer. The back end is where the comfortable lie meets the hardware, and one of its jobs is to squeeze that unbounded crowd of virtual values into the chip's tiny, fixed register file.
Why fight so hard to keep values in registers at all? Because the gap is enormous. A value that lives in a register is available to the arithmetic unit in well under a nanosecond; a value that has to be fetched from memory may cost a handful of cycles if it is in cache, or well over a hundred if it is not. The earlier rungs taught you the memory hierarchy — registers at the top, then cache, then main memory, each level dramatically slower than the one above. Register allocation is the compiler deciding, moment by moment, which of your live values get to sit at the very top of that hierarchy. Do it well and a hot loop runs near the chip's peak; do it badly and the same loop drowns in needless memory traffic.
Register allocation as coloring a graph
The heart of register allocation is one clean observation: two values can safely share a single physical register if and only if they are never needed at the same moment. To make that precise, the compiler computes each value's live range — the span of code from where the value is defined to its very last use. Two values interfere when their live ranges overlap, because at some instruction both must be readable at once, so they cannot occupy the same register. The whole problem reduces to: assign a register to every value such that no two interfering values get the same one. Values whose live ranges never touch can freely reuse a register, which is precisely how sixteen registers can hold the dozens of named values a function juggles over its lifetime.
Phrased that way, the problem is a famous one in disguise: graph coloring. Make every value a node; draw an edge between any two values that interfere; then color the nodes with as many colors as you have registers, so that no edge joins two nodes of the same color. A valid coloring is a valid register assignment. Graph coloring is computationally hard in general, so real compilers do not solve it exactly — they use clever heuristics (a classic one repeatedly removes any node with fewer neighbors than there are registers, since such a node can always be colored last, and pushes it on a stack to color on the way back). Just-in-time compilers, which must compile fast, often skip coloring entirely for linear scan: sweep the live ranges in order of where they start and hand out registers greedily, trading a little code quality for a lot of compile speed.
live ranges (| marks where each value is live): a: |====| b: |=======| c: |====| a interferes with b (ranges overlap) b interferes with c (ranges overlap) a does NOT touch c -> a and c may share one register interference graph: a --- b --- c 2-coloring: a=R1 b=R2 c=R1 (only 2 registers needed)
When you run out: spilling
Sometimes the graph simply cannot be colored with the registers you have — at some instruction, more values are live at once than the chip has registers to hold. The function has high register pressure, and the allocator has no choice but to spill. Picture a workbench with room for only a few tools: when a job needs more than fit, you set some down on a shelf behind you and fetch them back when needed. The registers are the workbench, the stack is the shelf. To spill a value, the allocator stores it to a slot on the stack, frees its register for something else, and inserts a load to bring it back just before its next use. Every spilled value therefore costs two extra memory operations — a store and a later reload — that it would never have needed had it stayed in a register.
The allocator is not careless about what it spills: it prefers to spill values that are used least often or whose live ranges are longest, so the added memory traffic lands where it hurts least. Reading disassembly, spills have a telltale signature — unexpected mov instructions shuffling values to and from stack offsets like [rsp-8] or [rsp-0x10], wrapped around your real computation, that you never wrote. Be honest with yourself about what this means: spilling is not a bug and is frequently unavoidable; the compiler is doing the right thing given a fixed number of registers. There is no setting that grants you more physical registers — the ISA fixes their count.
Selecting and scheduling the instructions
Register allocation is one of three back-end jobs, and the other two bracket it. Before allocation comes instruction selection: the IR speaks abstract operations — add, multiply, load, compare — that belong to no chip in particular, and the selector pattern-matches chunks of IR against the target's actual instruction menu, picking the cheapest real instructions that produce the same effect. Often it fuses several abstract operations into one: on x86-64 the address pattern base + index * 4 + offset collapses into a single load using a complex addressing mode, and a multiply-then-add can become one fused multiply-add. This is a big part of why the same C compiles to genuinely different assembly on x86 versus ARM — the back end is target-specific precisely because the instruction menu is.
After allocation comes instruction scheduling: a modern CPU overlaps instructions on a pipeline and can issue several at once, but only if the next instruction is not waiting on a result that has not arrived yet. The classic stall is a load — a value from memory may take many cycles to show up, and an instruction that uses it immediately would freeze the pipeline waiting. The scheduler builds a dependency graph and reorders independent instructions to fill that wait with useful work, never moving an instruction before one whose result it needs. Two honest caveats. First, big out-of-order cores reorder in hardware at run time anyway, so static scheduling matters most on simpler in-order chips and as good raw material for the hardware; do not overstate its effect on a large desktop core. Second, the scheduler reorders only because doing so preserves single-thread observable behavior — that same freedom is exactly why memory writes seen by other threads can appear reordered, which is the realm of the memory model, not something single-thread scheduling promises to preserve.
The license — and the trap: UB-driven codegen
Every transformation in this rung — folding, inlining, deleting, reordering, reusing a register — rests on one legal foundation you met in the first guide: the as-if rule. The standard describes your program as running on an abstract machine, and the only thing the compiler must preserve is its observable behavior: the contents and ordering of I/O, reads and writes to volatile objects, and program termination. Everything else is fair game. That is why a loop can vanish, a variable can have no memory location, and statements can be reordered — none of it is observable, so the as-if rule permits it. But there is a clause in that contract with sharp teeth, and being honest about it matters more than any single optimization.
Here it is, stated carefully. The as-if rule preserves behavior only for programs that are well-defined. If your program executes undefined behavior, the abstract machine has NO defined behavior to preserve — so the as-if rule constrains nothing, and the optimizer may do literally anything. The optimizer turns this around into an assumption: it assumes your program never has undefined behavior, and it uses that assumption to justify rewrites it otherwise could not. This is UB-driven optimization, and it is the single most consequential idea in the field. First keep three things apart, because they are constantly confused: unspecified behavior means the standard allows several outcomes and the compiler picks one (argument evaluation order); implementation-defined behavior means it must pick a documented one (how many bits an int has); only undefined behavior licenses the optimizer to assume it never happens.
Watch how it bites, because the examples are the whole point. Because signed integer overflow is undefined, the compiler may assume x + 1 > x is always true for a signed int x, and delete an overflow check you wrote that relied on the wrap. Because dereferencing a null pointer is undefined, if your code does p->field and only LATER tests if (p != NULL), the compiler may reason that p must have been non-null all along (else the dereference was UB) and delete your null check as redundant — your safety net silently removed. And the strict-aliasing rule lets the compiler assume an int * and a float * never point at the same bytes, so type-punning by casting one pointer to the other and dereferencing is UB whose results can look impossible. This is why a buggy program can "work" at -O0 and corrupt at -O2: the extra passes lean on an assumption your code violates. The compiler is not malicious — it reasons soundly from a premise you broke.