Register Allocation by Graph Colouring

A variable is live from where it is defined to its last use. Two variables whose live ranges overlap hold different values at the same instant, so they cannot share a register — draw an edge between them. The result is the interference graph.

Assigning k registers is then exactly k-colouring that graph: give every node a colour such that no edge joins two nodes of the same one. Variables with no edge between them are free to share.

What matters is not how many variables a function has, but how many are live simultaneously — usually far fewer.

Deciding whether a graph is k-colourable is NP-complete, so no compiler solves it exactly. The standard heuristic is simple and works remarkably well:

1. 1Find any node with fewer than k neighbours. Whatever else happens, a colour will be free for it later.
2. 2Remove it from the graph and push it on a stack. Removing it may drop other nodes below k neighbours.
3. 3Repeat. If only nodes with k or more neighbours remain, choose a spill candidate, remove it, and carry on.
4. 4Pop the stack, assigning each node a colour no neighbour has taken.

When no register is free, the variable is spilled to memory: a store after its definition, a load before each use. The program stays correct and gets slower.

Which variable to spill matters enormously. One used once outside any loop is nearly free to spill; one used every iteration of an inner loop is catastrophic. Allocators weight candidates by estimated use frequency, which is why loop depth, discovered from the flow graph, feeds directly into this decision.

A register access takes about one cycle; a memory access takes tens or hundreds even when it hits cache. Keeping the right values in registers is often the difference between fast and slow code, which is why allocation is usually the most valuable thing the back end does.

Linear scan is the common alternative: sort live intervals by start point and assign greedily. It produces worse allocations and runs far faster, so JIT compilers use it — there, compile time is part of run time.