The intermediate representation lied to you, generously. When three-address code minted temporaries t_1, t_2, t_3, \dots without limit, it pretended the machine had infinitely many registers. Real hardware does not: an x86-64 core has 16 general-purpose registers, ARM64 has 31, and a function routinely juggles hundreds of live values. Register allocation is the phase that faces the lie head-on — it maps that unbounded set of virtual registers onto the tiny fixed pool of physical ones, and decides which unlucky values must be evicted to memory when the registers run out.

It matters enormously. Registers are the fastest storage a CPU has — a value in a register is free to use; the same value in memory costs a load and a store every time. A good allocator can make the difference between code that keeps its hot variables in registers across a whole loop and code that dutifully shuttles them to the stack on every iteration. This is where the compiler earns much of its keep.

The problem: many virtuals, few physicals

State it plainly. The IR names values with virtual registers v_1, v_2, \dots — as many as the code needed. The target offers k physical registers (k = 16, 31, \dots). The allocator must assign each virtual to a physical such that two values that are needed at the same time never share one register. When more values are simultaneously needed than there are registers, some must spill to memory — with loads before uses and stores after definitions — and spilling is exactly what we want to minimise.

The keystone is knowing when two values are "needed at the same time." That is liveness: a value is live at a program point if it holds a value that may be read later before being overwritten. Two values whose live ranges overlap cannot occupy the same register — they interfere.

The interference graph

Overlapping live ranges cry out for a graph. Build the interference graph: one node per value, and an edge between any two values whose live ranges overlap (that interfere). Now the whole problem is reframed as pure combinatorics — assign each node a register so that adjacent nodes get different registers. If registers are "colours", this is precisely graph colouring: colour the interference graph with k colours, or spill if you cannot.

In the figure, the values a, b, c are all live together — a triangle — so they need three distinct registers. Value d interferes only with a and c, never with b, so it can reuse b's register. Four values fit in three registers with no spill — the allocator has found the reuse the schedule made possible.

Graph-colouring allocation (Chaitin)

The classic global allocator, due to Chaitin (1981) and refined by Briggs, colours the interference graph with a beautifully simple heuristic resting on one observation about node degree:

This simplify / select pair colours almost every real interference graph. The full machinery — Briggs' optimistic pushing of high-degree nodes, and coalescing to delete move instructions — is the subject of the dedicated graph-colouring page. Here we care about the whole pipeline, and about the moment the colours run out.

When colours run out: spilling

If some node cannot be coloured — its neighbours have used all k colours — that value must spill. Spilling keeps the value in a stack slot and inserts a load before each use and a store after each definition. This does three things: it frees a register at every point the value is not being touched, it adds new (very short) live ranges for the loaded/stored copies, and it therefore changes the code — so the interference graph must be rebuilt and the whole colouring re-run. Allocation is a loop that terminates when nothing spills.

Which value to spill? The allocator picks the one that hurts least — a common heuristic is to minimise \dfrac{\text{spill cost}}{\text{degree}}, spilling a high-degree node (frees lots of conflicts) whose uses are cheap and outside loops (a value used inside a tight loop is the last thing you want in memory). The art of allocation is really the art of choosing good spills.

The fast alternative: linear scan

Graph colouring is powerful but not cheap: building the interference graph and iterating can dominate compile time, which is fatal for a JIT compiling at run time. Linear-scan allocation (Poletto & Sarkar, 1999) trades a little code quality for a lot of speed. It never builds a graph at all. Instead it approximates each value's live range as a single interval on a linearised ordering of the code, sorts the intervals by start point, and sweeps once left to right, keeping a pool of free registers: give each interval a free register as it begins, return the register when the interval ends, and if none is free, spill the interval that ends latest.

With just two registers, the single sweep hands a and b the two registers, reuses b's once it expires, and spills whatever cannot fit — all in O(n \log n), dominated by the sort. No graph, no iteration to a fixpoint. This is why HotSpot's client compiler, early V8, and many JITs allocate by linear scan: a hair worse than Chaitin's code, produced an order of magnitude faster.