Register Allocation

IR can assign a new name to each intermediate value, but the target machine has only a limited number of registers with different capabilities. Register allocation determines which register or stack slot holds a value during various execution phases and inserts necessary data movements.

It is not a one-time selection of a permanent location for all variables. A value may reside in a register, be spilled to the stack across a call, and then reloaded into another register. The actual quality often depends on how these intervals are split.

Liveness Intervals and Interference

A value is live at the current position if a future path will use it before overwriting it. If different values must be retained simultaneously and cannot share a representation, they compete for the same physical register. The interference graph expresses such constraints with edges.

Liveness intervals in the CFG may have branches and holes, and do not necessarily correspond to a continuous segment on source line numbers. SSA φ inputs are used on their corresponding predecessor edges; one cannot assume that inputs from different predecessors are simultaneously used at the merge block entry, nor unconditionally connect all φ sources and results into a single liveness interval.

Graph Coloring: Understanding with a Simplified Model

In a model with K interchangeable registers and considering only pairwise interference, registers are colors, and adjacent nodes must have different colors. General K-coloring decision is a hard problem, and optimizing spill cost is an additional challenge; the entire real-world allocation process cannot be simply equated to an NP-complete decision problem.

The simplified algorithm repeatedly removes nodes with degree less than K and pushes them onto a stack. During restoration, its already-colored neighbors number at most K−1, leaving at least one color available. This reasoning relies on assumptions like interchangeable colors; fixed registers and class constraints require extended handling.

Optimistic Coloring: High Degree Does Not Necessarily Mean Allocation Failure

When the remaining graph has no low-degree nodes, a potential spill candidate can be selected for removal, but spill generation is deferred. During restoration coloring, if a color is still available, normal allocation proceeds; spilling occurs only if no color is left.

This is the key to optimism: defer judgment on candidates with degree greater than or equal to K, rather than doubting the colorability of nodes with degree less than K. High-degree nodes' neighbors may share colors, so a high number of neighbors does not mean all colors are already occupied.

Actual candidate costs usually combine usage frequency, loop weights, reload costs, and liveness intervals. Spilling values used repeatedly in hot loops is often more expensive than spilling values on cold paths.

Quadrilateral Counterexample: All Nodes Have Degree K, Yet K Colors Suffice

Take K=2, with edges A—B, B—C, C—D, D—A. Each node has degree 2; according to the "degree strictly less than K" rule, there are no nodes that can be immediately simplified; but assigning A/C to one register and B/D to another is sufficient.

Optimistic allocation can first treat A as a potential spill candidate and remove it. The remaining path B—C—D has endpoints with degree 1, allowing further simplification; during restoration, B and D can share a color, leaving another color available for A. The candidate marking means it is temporarily impossible to guarantee success via low-degree proof, not that a memory access has been proven necessary.

Below is a small graph enumeration used as a result verification tool, not to simulate industrial allocator performance. A quadrilateral is 2-colorable, a triangle is not; both "high-degree nodes don't necessarily fail" and "resources may indeed be insufficient" hold true within the same model.

from itertools import product


def coloring(nodes, edges, k):
    for colors in product(range(k), repeat=len(nodes)):
        assigned = dict(zip(nodes, colors))
        if all(assigned[a] != assigned[b] for a, b in edges):
            return assigned
    return None


square = [("A", "B"), ("B", "C"), ("C", "D"), ("D", "A")]
assert coloring("ABCD", square, 2) is not None
triangle = [("A", "B"), ("B", "C"), ("C", "A")]
assert coloring("ABC", triangle, 2) is None
assert coloring("ABC", triangle, 3) is not None

This quadrilateral is an example of a general interference graph model, not an example for the "chordal graph property of strict SSA" later in the text. A quadrilateral has no chords; it cannot be used to explain optimistic simplification for general graphs while simultaneously claiming it satisfies all premises of the strict SSA model.

If Every Node Has High Degree, Is Spilling Inevitable?

The degree condition provides a sufficient guarantee, not a verdict of unallocatability. A quadrilateral has no low-degree nodes when K=2, but placing two non-adjacent nodes in the same register allows a valid allocation. Below, we allow manual color trial and use small graph enumeration to provide independent feasibility conclusions; manual allocation conflicts and the fact that the entire graph cannot be K-colored should be read separately.

Spilling, Splitting, and Rematerialization

Spilling saves a value to the stack when needed and reloads it before subsequent use. The locations for saving and loading can be optimized; it is not necessary to always "write immediately after definition and read immediately before each use." Inserted new instructions create new short-lived values and constraints, which may require further allocation.

Liveness interval splitting allows hot segments to remain in registers while cold segments are temporarily stored. Rematerialization recomputes cheap, safely reconstructible values, such as certain constants or addresses, avoiding memory reads and writes. Rematerialization must also adhere to exception handling, side effects, and target costs.

Stack slots can also be reused when lifetimes do not overlap, but alignment, size, GC reference mapping, and debug information must be correctly updated.

Linear Scan: Processing Intervals by Program Layout

Basic linear scan approximates liveness intervals as intervals and sorts them by start point, maintaining an active set of currently occupied registers. When a new interval begins, ended intervals are released; if resources are insufficient, the new interval or a part of an existing interval is spilled.

Basic approximations may count holes in the true lifetime as live, increasing unnecessary pressure. Improved versions can handle holes, fixed intervals, splitting, and placement constraints. It is often used in scenarios where compilation latency is critical, but one cannot assert that any linear scan is worse or faster than any graph allocator.

Complexity depends on sorting, interval data structures, and splitting strategies. Comparisons should be based on specific implementations, compilation time, and final spills, rather than attaching unconditional complexity labels to both algorithms.

Coalescing: Eliminating Copies, But Potentially Increasing Pressure

If v2=v1 can use the same register on both sides, the copy can disappear. However, merging two nodes merges their adjacency constraints, potentially making a graph that was easy to color more difficult.

The classic Briggs conservative criterion focuses on whether the number of high-risk neighbors with degree at least K is less than K, rather than simply requiring the total degree after merging to be less than K. George-style criteria check conditions such as whether a node's neighbors are low-degree or already adjacent to another node, often combined with pre-coloring.

These criteria are sufficient conditions within specific graph coloring models, not universal formulas applicable under all machine constraints. Implementations can also perform copy elimination after allocation or reduce pressure caused by over-merging through splitting.

Merging Two Nodes Without Direct Interference Can Also Increase Color Count

Consider the path A—B—C—D, which can alternate between two colors. A and D have no edge between them. If a candidate copy merge intends to permanently share a location for both, merging them into M results in edges M—B, B—C, C—M, forming a triangle that requires three colors.

from itertools import product


def can_color(nodes, edges, k):
    for values in product(range(k), repeat=len(nodes)):
        colors = dict(zip(nodes, values))
        if all(colors[a] != colors[b] for a, b in edges):
            return True
    return False


path = [("A", "B"), ("B", "C"), ("C", "D")]
assert can_color("ABCD", path, 2)
rename = {"A": "M", "B": "B", "C": "C", "D": "M"}
merged = [(rename[a], rename[b]) for a, b in path]
assert not can_color("MBC", merged, 2)
assert can_color("MBC", merged, 3)

Here, copy candidates and interference edges are viewed separately: candidates represent moves desired to be eliminated, while edges represent constraints prohibiting shared locations. The absence of an A—D edge only indicates they do not directly conflict; it does not prove that merging their other constraints can still be handled with the same number of registers. Conservative merge criteria are precisely designed to avoid this indirect pressure increase; rejecting a merge does not mean the copy must be permanently retained, as subsequent splitting or local elimination may still handle it.

Why Does Merging Without Direct Conflict Result in Insufficient Registers?

When merging nodes, all their adjacency constraints must be carried over. Below, the two names A and D are folded into a single M, and the constraints originally at opposite ends close into a triangle. This counterexample shows that "no direct interference" is insufficient to approve permanent merging; whether to reject a specific coalescing operation should still be decided by the criteria used and target constraints, and cannot be interpreted as meaning all copies should be retained.

Why SSA Helps, Yet Does Not Eliminate All Difficulties

Under strict SSA, interference graphs constructed with correct φ-edge semantics possess exploitable chordal graph properties. In an ideal register model, the minimum number of colors can be efficiently obtained through a suitable order; this refers to the interference graph, not the def-use graph itself. SSA Register Allocation Paper

In reality, there are spill selection, copy merging, register classes, pre-coloring, sub-register overlaps, and instruction constraints. Parallel copies in SSA destruction also require correct scheduling; optimal ideal coloring does not mean the entire target allocation is already solved.

ABI and Instruction Constraints

Values surviving across calls cannot be placed in caller-saved registers without protection. Options include using callee-saved registers, saving and reloading, or splitting; using callee-saved registers may introduce save/restore costs within the current function.

Parameter and return value rules depend on types and ABI classifications; one cannot treat all x86-64 values as "first six integer registers, return in RAX". Two-address instructions, implicit registers, and vector register groups introduce additional bindings. See Target Code and ABI.

Observing Allocation Quality

Ultimately, machine code and target load should be checked. Changing inlining, scheduling, or loop unrolling alters liveness intervals, so register allocation is part of the entire backend pipeline.

References

• Register Allocation for Programs in SSA-Form.
• LLVM Code Generator.
• Data Flow Analysis.

Keywords: register allocation, interference graph, coloring, optimistic coloring, linear scan, spill, splitting, rematerialization, coalescing