How Compiler Register Allocation Uses Interference and Spilling
Register allocation is the compiler pass that assigns a program’s temporary values to a small set of physical CPU registers. When too many values are needed at once, it decides which ones to move to memory temporarily; this is called spilling.
The problem: more values than registers
CPUs have far fewer fast registers than a program may need intermediate values. A function might calculate several expressions, keep loop state, hold pointers, and preserve values across branches. The compiler’s internal instruction form represents these intermediates as virtual registers—names for values that are not yet tied to hardware registers.
Without register allocation, the compiler would have to give every intermediate its own memory location, loading values before operations and storing them afterward. That would work, but register operations are normally much cheaper than memory operations. Allocation tries to keep frequently used values in registers while respecting the hardware limit.
A value does not need a register for the entire function. It is live at a point if the program may still use its current value there. Its live range is the part of the program from where that value is produced to its final use. Once a value will never be read again, its register can be reused.
For example, in this simplified sequence:
let a = load_a();
let b = load_b();
let c = a + b;
let d = c * b;
a and b are both live before the addition. After the addition, a is dead, while b and c are live. The same physical register can therefore hold a first and c later.
Interference describes conflicts
The allocator first performs liveness analysis, which determines which values are live at each instruction. It then builds an interference graph. Each node represents a virtual value, and an edge connects two nodes when their live ranges overlap in a way that prevents them from sharing a register.
The edge means: these two values must have different physical registers. It does not mean the values are mathematically related; it is a storage conflict.
Register assignment can then be viewed as a graph-coloring problem. Each available physical register is a color, and connected nodes must receive different colors. If a CPU provides four usable registers, the allocator tries to color the graph with four colors.
Consider a point where a, b, and c are all still needed:
a = load_a()
b = load_b()
c = load_c()
d = a + b
e = d + c
Just before d is computed, all three values are live: a and b are needed by the addition, and c is needed later. They interfere with one another. If only two registers are available, three different colors cannot be assigned. At least one value must stop occupying a register for part of its live range.
The graph is not the only constraint. Some instructions require particular registers, and a function call may overwrite (“clobber”) certain registers. Values that must survive such a call need a safe register or a memory location. Different kinds of values may also require different register classes, such as integer versus floating-point registers. Allocators represent these requirements as additional conflicts or fixed assignments.
Spilling makes an impossible graph workable
When the graph cannot be colored with the available registers, the allocator chooses a value to spill. Spilling means assigning part or all of that value’s live range to a stack slot in memory rather than keeping it in a register.
The compiler inserts a store after producing the value and a reload before a later use. In conceptual form:
r1 = load_c()
store r1, [stack slot for c]
r1 = load_a()
r2 = load_b()
r2 = r1 + r2
r1 = load [stack slot for c]
r1 = r2 + r1
The exact registers and instructions depend on the target CPU. The important change is that c no longer occupies a register while a and b are being combined. Its value survives in a stack slot and returns to a register only when needed.
A spill is not automatically a bug, and the stack slot is not usually a heap allocation. It is compiler-managed function memory, often called a spill slot. But loads and stores add instructions and can introduce cache and memory-pressure costs, so the allocator tries to spill values whose use is cheap or infrequent.
Typical decisions consider how often a value is used, how long its live range is, and how many other values it conflicts with. A value used inside a hot loop is expensive to spill. A value used once on a cold error path is a more attractive candidate. The allocator may also split a live range: keep a value in a register in one region, spill it across another, and reload it later rather than spilling everywhere.
The allocation process
A practical allocator usually follows this broad sequence:
- It examines the compiler’s intermediate instructions and calculates live ranges.
- It creates interference constraints, including fixed-register and call-related constraints.
- It assigns physical registers to as many virtual values as possible.
- When no legal register remains, it selects values to spill or splits their live ranges.
- It inserts the required stores and reloads, then repeats allocation for the changed instructions.
- It rewrites the final instructions using real registers and stack locations.
Classic allocators explicitly simplify and color an interference graph. Other widely used allocators, such as linear-scan allocators, process live ranges in program order and use intervals to make faster, approximate decisions. Both rely on the same central facts: values need registers only while live, overlapping live ranges cannot share one register, and excess live values must be moved elsewhere.
This is why compiler diagnostics and performance reports sometimes mention register pressure, spills, or reloads. They describe the point where too many values are simultaneously live. Reducing unnecessary live values— for example, by shortening a temporary’s lifetime—can give the allocator more freedom and remove memory traffic from the generated machine code.