13.2 Register Allocation: Graph Coloring and Linear Scan

Instruction selection usually produces many virtual registers, but a machine has a small set of physical registers. Register allocation maps virtual values to physical locations while respecting overlaps, fixed-register constraints, calls, and the calling convention. Values that cannot remain in registers are spilled to stack slots.

The allocator consumes liveness information from Chapter 12. If two virtual values are live at the same program point, they interfere and cannot occupy the same physical register.

Interference graphs and coloring

An interference graph has one node per virtual register and an edge between simultaneously live values. Assigning K physical registers becomes a graph-coloring problem with K colors. Adjacent nodes must receive different colors.

Exact coloring is expensive, so compilers use heuristics:

1. repeatedly remove a node with degree less than K and push it on a stack;

2. if none exists, choose a potential spill using cost and degree;

3. pop nodes and assign a color not used by colored neighbors;

4. if no color is available, spill and rewrite the function.

Precolored nodes represent fixed machine registers. A call instruction interferes with values live across it through caller-saved registers that the callee may overwrite. Different register classes—integer, vector, predicate—normally use separate or partially overlapping coloring problems.

Coalescing and spilling

Copies such as %b = copy %a are desirable coalescing candidates: if %a and %b do not interfere, assigning the same register removes the copy. Aggressive coalescing can make the remaining graph harder to color, so algorithms use conservative tests before merging nodes.

Spill choice is not simply “highest degree.” A value used frequently inside a deep loop is expensive to reload. A value cheap to recompute may be rematerialized instead of loaded from a stack slot. Spill cost commonly weighs use frequency, loop depth, live-range length, and available addressing modes.

After inserting spill loads and stores, liveness and interference change, so allocation runs again. The rewrite must avoid creating an endless cycle in which newly introduced temporaries also spill.

Linear scan allocation

Linear scan represents each virtual value as a live interval [start, end] in instruction order. It processes intervals by start position and maintains an active set sorted by end:

• expire active intervals that end before the new interval begins;

• assign a free register when available;

• otherwise spill the new interval or an active interval with a less favorable end/use profile.

Linear scan is fast and well suited to JIT compilation. Graph coloring can produce better allocations when compile time permits. Production allocators often split live ranges, creating separate intervals around calls or pressure peaks, and use different physical registers in different regions connected by copies.

Verifying an allocation

After allocation, every virtual register must be replaced, every instruction's register-class and fixed-register constraints must hold, and no two interfering values may share a physical register. Spill slots must have valid size and alignment. Values live across calls must survive according to caller/callee-save rules.

A useful checker symbolically walks machine instructions, tracking which value each physical register and spill slot should contain. Tests should include high-pressure loops, calls, tied operands, two-address instructions, precolored arguments, exception edges, and intervals with holes.