Building the Interference Graph from SSA Live Ranges

Register allocation is the problem of assigning each value that must exist simultaneously to a distinct machine register. The abstraction that makes it tractable is the interference graph: a node per value, an edge between two values that cannot share a register because both are live at the same program point. Colouring that graph with as many colours as there are registers solves the problem, and spilling a node removes it from the graph at the cost of memory traffic.

The graph’s size is the first problem. A naive construction adds an edge for every pair of values simultaneously live, which is quadratic in the number of live values per point and can be enormous for a block with hundreds of live temporaries. SSA form changes the structure of the graph in a way that makes it both smaller and better behaved, and understanding exactly how is necessary to see why allocation on SSA is not merely an optimisation of the classical algorithm but a different algorithm.

Live Ranges and the Definition of Interference

A live range is the set of program points between a definition and its last use, following the control-flow graph. Two ranges interfere if there is a point where both are live, because at that point both must be held in registers and they must be different registers.

The conventional formulation adds edges between all pairs of ranges that overlap at any point, which is correct and is also what liveness-based construction produces: two values that are live at a common program point genuinely need distinct registers, because both must be readable from that point onward. The over-approximation is elsewhere. A range is often modelled as a single interval from its first definition to its last use, together with the whole of any loop it appears in, and such a range counts as live at points where no path carries the value from the definition to that point. Building the graph from liveness sets instead of from interval containment removes that imprecision, and the difference is largest around loop exits and along branches that do not define the value.

The over-approximation matters because colouring a denser graph needs more colours and spills more. A graph that is a clique of size k needs k colours regardless of whether the corresponding ranges could have been split. Splitting a range at a point where its value is copied into a new name can reduce the clique, which is why live-range splitting is a standard pre-allocation transformation and why the choice of where to split is a cost-model question.

What SSA Changes

In SSA form, each name is defined once and dominates all its uses, so its live range is a connected region: the definition, all the points on paths to the uses, and the uses. Two SSA names can only interfere at a point where both are live, and because each is defined at exactly one place, the interference pattern has a special structure.

The key result is that the interference graph of an SSA program, built with no coalescing pre-applied and with phi functions handled by treating all phi inputs and the phi destination as simultaneously live at the block entry, is chordal: a graph in which every cycle of length four or more has a chord. Chordal graphs are perfect, so their chromatic number equals the size of their largest clique. The clique number here is the largest number of values simultaneously live, which means a greedy colouring in a perfect elimination order reaches that number and no colouring can need fewer register names beyond those that precolouring and instruction constraints force.

The structural reason is that phi operands are what creates the chords. Without phis, the interference graph of an SSA program can contain chordless cycles of arbitrary length; the chords come from the multiple simultaneously live values at a block with several predecessors. The practical consequence is that allocation on SSA, done before any coalescing, can be optimal in the number of registers, and the optimality is lost the moment copies are merged or a value is pinned to a fixed register.

def build_ssa_interference(func):
    g = {name: set() for name in func.names}
    for block in func.blocks:
        live = set(block.live_out)
        for ins in reversed(block.instructions):
            if ins.is_phi:
                # all phi inputs and the destination are live together
                group = set(ins.inputs) | {ins.dst}
                for a in group:
                    g[a] |= group - {a}
                live |= group
                continue
            live.discard(ins.dst)
            for a in live:
                g[a].add(ins.dst)
                g[ins.dst].add(a)
            live |= set(ins.uses)
    return g

Walking backward is what makes this correct: at each instruction, the values live after it are known, and the destination is added to their interference set before the uses are added to the live set. The phi case is special because a phi’s inputs are not read at the phi’s position in the block; they are read on the incoming edges, so they must be treated as live at the block entry along with the destination.

Where the Chordality Breaks

Coalescing is the first thing that breaks it. Merging two nodes to remove a copy can create a graph that is no longer chordal, and the merged node may have a clique of neighbours larger than the register count. Precoloured nodes — values constrained to specific registers by the calling convention or by an instruction’s fixed operands — break it in a different way, because their colours are fixed and the greedy order must respect them.

The standard response is to keep the SSA graph for the initial colouring and to handle coalescing as a separate decision with its own cost model. The Briggs test merges two nodes only when the combined node has fewer than k neighbours of significant degree, defined as degree at least k, which is cheap to check and rarely produces an uncolourable graph. The George test is more permissive in one direction: it merges when every neighbour of one node either already interferes with the other node or has degree below k. Chaitin’s original test, which merges only when the combined node has fewer than k neighbours of any degree, is the strictest of the three and is rarely used alone because it blocks most coalescing.

Phi coalescing deserves separate treatment. Eliminating a phi requires the input values and the destination to be in the same register, which is a coalescing constraint rather than a normal interference edge. If the constraint cannot be satisfied, the phi becomes moves, and the moves are what Phi Functions: Parallel Semantics and the Out-of-SSA Problem describes. Treating phi-related nodes as precoloured to a single colour is one way to force the merge; treating them as normal nodes with a coalescing preference is the other, and the second is more flexible but requires the allocator to reason about move costs.

Spilling and the Cost of a Bad Choice

When the graph cannot be coloured with k colours, some node must be spilled: its value lives in memory, each use becomes a load, and each definition becomes a store. The choice of which node to spill determines the cost, and the classical heuristic is the ratio of spill cost to degree, where spill cost is the sum of the execution frequencies of the definition and uses, weighted by loop nesting depth.

The heuristic is heuristic because the true cost depends on what happens after the spill: the loads and stores are new instructions, they have their own register needs, and they may themselves interfere with the remaining values. Spilling a node with a huge degree removes many edges at once, which can make the rest of the graph colourable, while the same decision applied to a low-degree node in a hot loop buys one colour at the price of a load or store on every entry to that loop, so the ratio is comparing a static degree against a dynamic cost without a common unit. Neither effect is captured by the ratio, which is why spilling is usually followed by a re-run of the allocation and sometimes by a re-run of scheduling.

The SSA-specific version of the problem is that a spill can often be avoided by splitting the live range at a point where the value is not needed, which is cheaper than a memory spill because it requires no memory traffic at all. Splitting requires a copy into a new name, and the copy itself is an instruction; if the copy can be coalesced away, the split is free, and if not, the split costs a move. The decision is a small instance of the same trade-off that governs coalescing: moves versus registers.

Linear Scan as the Alternative

Graph colouring produces good code and costs time that is superlinear in the number of values, which is why large functions with thousands of live ranges pay for it. A linear formulation such as chordal colouring is cheaper in practice than iterated simplify-and-select, but either uses more compile time than the linear-scan family. Linear scan allocates in one pass over a linear ordering of the live intervals, maintaining an active list sorted by end point and spilling the interval that ends furthest in the future when a new interval needs a register.

The algorithm is simpler, faster, and less precise. It assumes each live range is a single interval in the chosen ordering, which holds for straight-line code and for a variable used only inside one loop, but not for a value defined before a loop and used after it: that range has a hole where the variable is not live, and treating it as one interval counts registers as busy at points where nothing is held. Picking an ordering does not remove the problem, because no ordering of the blocks makes every non-convex range convex. Linear scan also cannot exploit the chordal structure, because it never builds the graph, so it cannot guarantee the chromatic number and may spill where colouring would not.

The practical trade is compile time versus code quality, and the crossover is a function of function size and of how much of the compile time budget is available. A just-in-time compiler that must produce code while the program waits will use linear scan and accept the extra spills; an ahead-of-time compiler with a large budget will use colouring and accept the graph construction cost. Hybrids that use linear scan as a fast path and fall back to colouring for hot functions are also common.

What the Allocator Needs From the IR

The allocator needs liveness at block boundaries, which the CFG supplies; a def-use relation, which SSA supplies; and a list of constraints imposed by the instruction set, which only the machine description knows. The third is the one that most often surprises: an instruction that writes a fixed register, a call that clobbers a set of registers, and a two-address instruction whose destination must equal one of its sources all become edges or precolouring in the graph.

Those constraints can be modelled as precoloured nodes or as edges to a special “machine register” node, and the choice affects how much freedom the allocator has. Modelling a call’s clobbers as interference with every value live across the call is correct and expensive; modelling them as constraints only on values that are actually used after the call is cheaper and needs liveness at the call site.

After allocation, the values are held in physical registers, many of which are reused for different values at different points, so the names the optimiser reasoned about no longer correspond one-to-one with locations. The transformations that follow — resource-aware scheduling, peephole optimisation, and emission — operate on a form where the register assignments are part of the code. That is the point at which the intermediate representation has served its purpose and the machine representation takes over.