Building the Interference Graph from Live Sets

Graph coloring allocation rests on a single reduction: build a graph whose vertices are virtual registers and whose edges mean “these two cannot share a physical register”, then color the graph with as many colors as there are registers. The reduction is exact for the constraint it models and approximate for the machine, and the gap between the two is entirely decided at graph construction time. Edges that are added but not required cost colors; edges that are required but missing produce wrong code.

The definition of an edge

Two virtual registers interfere when they are simultaneously live at some program point and are not the same register. Simultaneity is the operative word. If a is live from instruction 1 to instruction 5 and b from instruction 5 to instruction 9, they touch at instruction 5 and can be assigned the same register only if the value of a is never read after that point. The standard formulation avoids the ambiguity by testing at definitions rather than at arbitrary points:

Add an edge between the defined register d and every register in the live-out set of the defining instruction, except d itself.

If b is defined at instruction 5 and a is live out of instruction 5, then some path from the next instruction reads a before defining it, so a is still needed while b occupies a register. If a is not live out, every read of a happens at or before instruction 5, and sharing the register is safe. The instruction’s own operand ordering — whether an operand is read before the destination is written — is a separate constraint that the graph does not model.

The exception for d itself matters when an instruction both reads and writes a register, as in add r1, r1, r2, or in a load with a writeback addressing mode on an architecture such as AArch64, where ldr x1, [x2], #8 both reads and writes the pointer register. The live-out set of such an instruction contains r1, and adding a self-edge would make the graph uncolorable with any number of registers. Self-edges must be dropped at insertion, not filtered later.

Parallel copies at the end of a block are the other case where the naive rule over-constrains. A parallel move a, b = b, a has b live out of the definition of a, so the rule adds an edge between two registers that must be swapped. The edge is real for a sequential implementation of the swap but not for the parallel semantics, and an architecture that can exchange two registers without a temporary does not need it. The usual treatment is to keep the edge and let coalescing decide, or to detect the cycle and break it with one temporary. Dropping the edge silently is only safe if the backend expands parallel moves into a correct sequential sequence first.

Moves and the pre-built graph

A move instruction d <- s is special in a way no other instruction is. It creates no interference between d and s even when the live-out set of the move contains s: if the two are assigned the same register, the move becomes a no-op and both values are correct. Every other instruction that reads s and defines d forces the two apart, because the operation has to see the old value of d and the new value of s separately.

This asymmetry is why interference graphs are built with move instructions contributing no edges to their own operands, while all other definitions contribute the full live-out set. It also creates the graph’s most useful structure: a move that survives allocation is pure cost, one instruction with no semantic effect, and the allocator’s job is to make as many of them disappear as possible. Coalescing is the mechanism that removes them, and the graph must not pre-emptively forbid the assignment coalescing wants.

An alternative construction builds two graphs at once. The interference graph carries the constraints that cannot be violated; a separate move graph (or a set of move-related pairs stored on the nodes) records which pairs are candidates for merging. Chaitin’s original formulation folded the move information into the interference graph by adding edges between the source and destination of every move, then removing them when coalescing; that variant makes the graph simpler to reason about but makes coalescing decisions coarser, because a removed edge cannot be restored if the merge fails.

Precolored nodes and the machine’s own registers

Physical registers are vertices too. Each one is precolored: its color is fixed to itself, and it has an edge to every virtual register that interferes with it. Without these nodes the allocator would happily assign a value to rsp and watch the stack pointer be overwritten. With them, the constraint “do not use the stack pointer for a value that is live across a call” is just an edge, and the coloring algorithm needs no special case for it.

The edges from a virtual register to a physical register come from the same live-out rule, but the machine’s registers are not named in the instruction stream the way virtual ones are. They appear as implicit uses and defs: the stack pointer is read and written by every push, the flags register is defined by every comparison, the link register is written by every call. The instruction selector is responsible for recording those operands, and a backend that leaves them implicit produces a graph missing edges to precolored nodes, which is a well-known source of bugs where the allocator clobbers a register the frame or call sequence depends on. The full set of constraints derived from the ABI is the subject of calling conventions as precolored nodes.

Precolored nodes also break the symmetry of the coloring problem. A graph with K precolored vertices and N uncolored ones is not a K-colorability question in the usual sense: the precolored vertices are already assigned, and the question is whether the uncolored ones can be extended. Greedy coloring handles this naturally: precolored nodes are never placed on the simplify stack, and an uncolored node is blocked from a color if any precolored neighbor holds it.

Representation and its cost

The number of edges is what determines the cost of the coloring loop. Each node’s neighbor list is scanned repeatedly: during simplification to compute degrees, during selection to test colors, during coalescing to test Briggs’ condition. A function with N virtual registers produces O(N * K) edges, where K is the number of simultaneously live values, because each definition adds an edge to each value in its live-out set. In practice K is bounded by the register pressure of the code, which is why the graph is usually sparse relative to N^2.

Three representations are used. An adjacency list (a vector of neighbor ids per node) costs 4 bytes per edge on a 32-bit id, is cache-unfriendly during neighbor scans, and is what most production allocators use because the scans are short. An adjacency matrix is O(N^2) bits and is only viable for small functions; a thousand registers is 125 KB and a hundred thousand is about 1.25 GB, so the matrix is a small-function optimization at best. Bitset adjacency, one bit per neighbour with the bits packed into machine words, gives constant-time edge tests and fast set unions, at N/8 bytes per node: 125 bytes for a thousand registers, 12.5 KB for a hundred thousand, which makes the “is there an edge” query free.

The choice interacts with the algorithm. Chaitin-style simplification only needs degrees and neighbor lists, so adjacency lists suffice. Coalescing needs edge tests between arbitrary pairs, which favors bitsets. Spilling needs the degree of a node after every removal, which favors an incrementally maintained counter over recomputation.

A construction that stays correct at block boundaries

The following builds edges from a per-instruction liveness map. live_out holds one set of virtual register names per instruction, indexed the same way as instrs, and instructions are tuples of the form (defined, used, is_move).

def build_graph(instrs, live_out, physical):
    adj = {v: set() for v in physical}
    for i, (d, uses, is_move) in enumerate(instrs):
        adj.setdefault(d, set())
        for u in uses:
            adj.setdefault(u, set())
        for v in live_out[i]:
            if v == d:
                continue                       # a self-edge is never a conflict
            if is_move and v in uses:
                continue                       # move source may share the target
            adj[d].add(v)
            adj[v].add(d)
    for p in physical:                         # precolored nodes keep their color
        adj[p] = adj[p] - {p}
    return adj

Two details in that loop are easy to get wrong. The first is the is_move test: it must exempt only the move’s own source, not every register live across the move. A move that is live across c still forces d to differ from c, because c is read later and d occupies the destination. The second is the treatment of the physical registers: their adjacency sets are seeded so that an uncolored node’s neighbor scan always finds them, but self-edges are removed because a precolored node trivially “interferes” with itself under the definition rule.

Sizes that matter

A few orders of magnitude keep the design honest. A large function after inlining can have tens of thousands of virtual registers; the graph then has hundreds of thousands of edges and the simplification loop runs in time proportional to that, which is why allocators are among the slower backend passes and why function splitting exists. Live sets stored as bit vectors cost one bit per virtual register per block: a function with 20,000 values and 5,000 blocks is 12.5 MB of bit vectors if every block stores a full set, which is why block-level sets are usually computed per block on demand during a single backward sweep rather than materialized for the whole function at once.

The graph is also the point where the allocator’s precision is decided for the rest of the backend. An edge added for a value that is live across a region but never actually read there is pure loss: it consumes a color, may force a spill, and the spill adds loads and stores. Interval-based approximations do exactly this, and the false edges they add sit on top of the edges precise construction would also have added, which is where the extra density comes from. Precise construction from per-instruction liveness costs more analysis time and produces a smaller graph; the trade is between front-end time and the quality of the code that follows, and the crossover is somewhere around the point where the function is large enough that the analysis itself dominates.