Registerssimplified

The Interference Graph

A node per value, an edge whenever two values are live at the same point. Once the program is in this form, register allocation is graph colouring — which is how an NP-complete problem ended up in the middle of every compiler.

The question

How does a compiler represent "these two values cannot share a register"?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

An undirected graph: one node per virtual register, one edge per pair of values that are simultaneously live at some program point. It exists to discard everything about the program except the conflicts — the graph knows nothing about what the values are, what they compute, or where in the function they live. That deliberate forgetting is what turns a compiler problem into a graph problem with a literature.

What this phase may assume or do

The graph must be a *conservative over-approximation* of the true conflicts: every genuine simultaneous liveness must produce an edge, and extra edges are permitted. A missing edge means the allocator may give two live values the same register, which silently destroys one of them; a spurious edge only costs a register. The construction must also add edges for constraints that are not liveness at all — a value live across a call interferes with every caller-saved register, and an instruction with a fixed operand pins its value regardless of what else is live.

Key points

  • One node per value, one edge per pair of values live at the same point; nothing else about the program survives into the graph.
  • Register allocation on this graph is exactly graph k-colouring, which is NP-complete — but the allocator may always spill, so it never has to fail.
  • The graph must over-approximate: a missing edge is a miscompilation, a spurious edge only wastes a register.
  • Real allocators add edges that are not liveness at all — call-clobbered registers, fixed instruction operands, sub-register aliasing — usually via precoloured nodes.
  • Interference graphs from strict SSA are chordal and therefore optimally colourable in polynomial time, which is the basis of SSA-based allocation.
  • Building the graph is quadratic in simultaneous liveness, which is why it is the phase that blows up on machine-generated code.

From bars to edges

The live-range chart already contains the answer; the graph just changes the question you can ask cheaply. Walk every program point, look at which ranges cover it, and add an edge between every pair. That is exactly what buildInterference does in our engine, and it computes the peak pressure in the same sweep because the number of ranges covering a point *is* the pressure there.

The table below is our engine's output for the function from [[live-ranges]]. Read it as an adjacency list — the same structure as [[adjacency-list]] in the data-structures domain, and for the same reason: the graph is sparse and the operation that matters is "iterate my neighbours".

The interference graph our engine builds for (a*b - (a+b)) * 2 + a*bsimplified
ValueLive rangeInterferes withDegree
%0points 0–3%1, %2, %33
%1points 1–3%0, %2, %33
%2points 2–6%0, %1, %3, %4, %5, %66
%3points 3–4%0, %1, %2, %44
%4points 4–5%2, %3, %53
%5points 5–6%2, %4, %63
%6points 6–7%2, %52
The same graph drawn out. Peak pressure is 4, at point 3.
        %0 ────── %1
         │ ╲      ╱ │
         │  ╲    ╱  │
         │   ╲  ╱   │
        %3 ─── %2 ────────┐
         │      │ ╲       │
         │      │  ╲      │
        %4 ─────┤   %6 ───┘
         │      │  ╱
         └──── %5 ┘

  %2 touches everything: it is defined at point 2 and read at point 6,
  so it is live across the entire middle of the function. Degree 6 out
  of a possible 6 — it conflicts with every other value in the program.

Why this makes the problem NP-complete, and why that is fine

simplifiedBecause our live ranges have no holes, the graphs we build are always interval graphs, and interval graphs are perfectly colourable by a greedy sweep. That means our graph colouring and our linear scan always need the same number of registers, and differ only in *which* register each value gets and in which value is chosen to spill. The genuine quality gap between the two algorithms appears once ranges have holes and the graph stops being an interval graph — which is exactly what [[live-ranges]] says our model gives up.

Assigning k registers such that no edge joins two nodes of the same colour is exactly graph k-colouring, which is NP-complete for k ≥ 3. Chaitin observed in 1981 that the reduction runs both ways — any graph is the interference graph of some program — so register allocation in full generality is as hard as colouring, and there is no clever program-specific structure to exploit in the worst case.

In practice this is far less alarming than it sounds, for two reasons. First, real interference graphs are sparse and highly structured: most values are short-lived and interfere with a handful of neighbours. Second, the allocator is allowed to give up — spilling is always available, so the algorithm never has to *fail*, only to produce a worse answer. Heuristics with an escape hatch are a much easier engineering proposition than heuristics that must succeed.

There is one genuinely important structural result. Interference graphs derived from programs in strict SSA form are *chordal*, and chordal graphs can be optimally coloured in polynomial time. That is the basis of SSA-based register allocation, which splits the problem into "decide what to spill" and "assign colours", the second of which is then no longer the hard part. Our engine works on ranges over a linearised order rather than on SSA, and hole-free intervals happen to give an interval graph, which is also chordal — which is why both our algorithms always achieve the peak-pressure bound. Real allocators, working on real ranges with holes, do not get that for free.

Edges that are not liveness

targetWhich registers a call destroys, and which instructions pin operands, are ABI and ISA facts. On x86-64 System V, rax rcx rdx rsi rdi r8–r11 are caller-saved and idiv pins rdx:rax; on Windows x64 the caller-saved set is smaller; on AArch64 AAPCS x0–x18 are caller-saved and no integer instruction pins a register. The graph construction is identical; the edges it produces are not.

A graph built purely from simultaneous liveness is incomplete, and the missing edges are all target constraints. Building them in is what turns a textbook algorithm into a working allocator.

A value live across a call cannot live in a caller-saved register, so it is given an edge to every one of them — precoloured nodes representing the physical registers themselves. An instruction with fixed operands does the same: on x86-64, idiv reads rdx:rax and clobbers both, so every value live across a division interferes with those two. Sub-register aliasing adds edges too, since on x86-64 writing eax modifies rax.

The usual implementation trick is to seed the graph with one precoloured node per physical register, all mutually adjacent, and then add edges from values to the registers they may not occupy. Colouring then handles ABI constraints and liveness with one mechanism instead of two, which is a considerable simplification given how many such constraints a real target has.

  • Live across a call → edges to every caller-saved register, or spill around the call.
  • Operand of a fixed-register instruction → an edge to every register except the one it must occupy.
  • Sub-register aliasing → an edge whenever writing one register modifies another.
  • Two values connected by a copy → deliberately *no* edge if they do not otherwise interfere, so they can be coalesced into one register — see [[coalescing-and-rematerialization]].
  • Precoloured nodes for the physical registers make all of this one mechanism rather than several.

The cost of building it

The graph has a node per value and, in the worst case, an edge per pair — quadratic in the number of simultaneously live values. For a normal function that is nothing. For a machine-generated function with a basic block of ten thousand instructions and thousands of long-lived values, it is millions of edges, and building the graph dominates compile time.

This is the practical reason JIT compilers do not build interference graphs at all, and the reason production allocators use a hybrid representation — a bit matrix for fast adjacency queries plus adjacency lists for iteration, with the matrix dropped above some size threshold. It is also why compile-time blow-ups on generated code are almost always reported against the register allocator rather than against any other phase.

How it works

The steps, in the order the compiler takes them.

  • Compute live ranges from the liveness solution.
  • Sweep the program points; at each one, take the set of values live there and add an edge between every pair.
  • Record the maximum size of that set as the peak pressure, which is the lower bound on registers needed.
  • Seed precoloured nodes for the physical registers, mutually adjacent, and connect values to the registers they may not use.
  • Add edges for call-clobbered registers across every call site, for fixed-operand instructions, and for sub-register aliasing.
  • Deliberately omit an edge between the two ends of a copy instruction when they do not otherwise interfere, so a later coalescing step can merge them.
  • Store adjacency both as a bit matrix (fast membership) and as lists (fast iteration), dropping the matrix when the graph is too large.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • An edge is missed because liveness was under-computed, two live values share a register, and a value is silently corrupted with no crash and no diagnostic.
  • Call-clobber edges are omitted, a value survives in a caller-saved register across a call, and it comes back holding whatever the callee left. The symptom depends on the callee, so it moves when unrelated code changes.
  • The graph is built for a generated function with an enormous basic block, and compile time and memory blow up on one translation unit while everything else compiles instantly.
  • Sub-register aliasing is not modelled, a 32-bit write to eax clobbers a 64-bit value held in rax, and the upper half is silently zeroed.
  • Copy-related nodes are given an interference edge unconditionally, coalescing becomes impossible, and the output is full of register-to-register moves that no peephole can remove.

When it helps

  • Any allocator that wants to reason globally about conflicts rather than sweeping in one direction — the graph is what makes non-local decisions possible.
  • Coalescing, which is a graph operation: merge two non-adjacent nodes and check the resulting degree.
  • Explaining an allocation to a human. The degree of a node is a direct, checkable statement about why a value could not get a register.

When it hurts

  • JIT compilation, where the quadratic construction cost is paid while the user waits and a linear sweep is worth more than a better allocation.
  • Enormous basic blocks from code generators, where the graph is the compile-time bottleneck.
  • When it is treated as the whole problem. Colouring the graph is only half the job; deciding what to spill when it will not colour is the half that determines code quality.

What it costs

Every one of these is paid by something.

  • Building the graph buys global reasoning and coalescing, and costs time and memory quadratic in simultaneous liveness — real enough to be the reported cause of compile-time blow-ups on generated code.
  • Over-approximating edges buys guaranteed correctness and costs registers: every spurious edge is a value that could have shared storage and did not.
  • Representing physical registers as precoloured nodes buys one uniform mechanism for liveness and ABI constraints, and costs a graph that is denser from the outset — every value now has edges to registers as well as to values.

What else you could do

What a different compiler or language does instead, and when that is better.

  • Do not build a graph: sweep the intervals in order and allocate greedily, which is [[linear-scan-allocation]]. Linear time, no global view, no coalescing.
  • Exploit SSA: the interference graph of a strict-SSA program is chordal, so colouring is polynomial and the hard decision moves entirely to spilling. Several research and production allocators are built this way.
  • Puzzle-based or PBQP formulations, which encode register constraints as a different optimisation problem and solve it with a general solver. Better results, considerably slower.
  • For a small language on a machine with plenty of registers, allocate greedily per basic block and reload everything at block boundaries. Crude, fast, and adequate until it is not.

See it for yourself

The flag, dump or tool that shows you this directly.

  • LLVM prints interference information in its register-allocator debug output: llc -debug-only=regalloc file.ll on a debug build shows live intervals and the conflicts considered.
  • GCC: -fdump-rtl-ira includes the conflict information the integrated allocator computed.
  • Ours: buildInterference in src/compilers/sim/regalloc.ts returns the adjacency map, the peak pressure and the point at which the peak occurred; /compilers/registers renders all three.
  • To see the effect rather than the graph: compile a function with increasing numbers of simultaneously live values and watch the point at which spill code appears in clang -O2 -S output.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "An edge means the two values are related." An edge means they are alive at the same time. Two values that never interact at all interfere if their ranges overlap.
  • "A high-degree node must be spilled." High degree makes a node hard to colour, not impossible — its neighbours may share colours among themselves. That is precisely the observation Briggs added to Chaitin's algorithm.
  • "The graph tells you what the program does." It tells you nothing about what the program does. Every fact except conflict has been discarded, which is what makes it tractable.
  • "Colouring the graph is register allocation." Colouring is the easy half once you have decided what to spill. Spill selection is where the code quality is decided.

Misconceptions

The claim, and what is actually true.

The interference graph is built from the control-flow graph.
It is built from the liveness solution, which is computed *over* the CFG. The interference graph has no notion of control flow at all — two values in unrelated branches interfere if the linearisation says their ranges overlap.
Fewer edges is always better.
Fewer edges is better only if they were spurious. Removing a genuine edge produces a miscompilation, which is why every uncertainty in the analysis is resolved by adding an edge.
Because colouring is NP-complete, compilers cannot do it well.
They do it well most of the time because real graphs are sparse and structured, and because spilling means the algorithm always has a legal answer available. NP-completeness bounds the worst case, not the typical one.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

Draw a dot for each value the function computes, and a line between any two dots whose values are alive at the same moment. Now give each dot a register such that no line joins two dots with the same register. That is register allocation, and it is the same puzzle as colouring a map so that no two neighbouring countries share a colour.

practical

The useful thing the graph gives you is an explanation rather than an outcome. When a value spills, its degree tells you whether it was unlucky or doomed: a node with fewer neighbours than there are registers can always be coloured, so if it spilled, something in the ordering went wrong. A node adjacent to everything, like %2 in this lesson, was going to lose the moment the register budget dropped below the peak.

advanced

The most consequential result in this area is that strict-SSA interference graphs are chordal, published around 2005 and quietly reshaping the field. Chordality means optimal colouring in polynomial time, which decomposes allocation into two independent problems: how much to spill (still hard, still where the quality is) and how to assign colours (now easy). It also explains something that had puzzled implementers for years — that Chaitin-style allocators seemed to spill more than the graph structure suggested they needed to, because they ran after leaving SSA and destroyed the chordality in the process. The practical lesson generalises well beyond allocation: the representation you run an algorithm on can change its complexity class, and leaving a good representation early can cost more than the algorithm ever gains.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

simplifiedOur graphs come from hole-free intervals and are therefore always interval graphs, which are chordal and greedily colourable. That makes our two allocators agree on the number of registers needed, which real allocators on real ranges do not. The adjacency table in this lesson is our engine's genuine output for the function shown, and it is a graph with more structure than a production allocator ever gets.
targetEvery edge that is not pure liveness — call-clobber, fixed operands, sub-register aliasing — is a target and ABI fact. The x86-64 System V examples here have no AArch64 counterpart for the fixed-operand case, and the caller-saved set differs on Windows x64.
typicalThe bit-matrix-plus-adjacency-list representation and the size threshold above which the matrix is abandoned describe mainstream allocators such as GCC's IRA and LLVM's earlier PBQP and linear-scan implementations. LLVM's current default greedy allocator works on live intervals with a union-of-intervals interference test rather than building an explicit graph at all.

If you were asked this in an interview

  • How would you build an interference graph, and what is its worst-case size?
  • Why is it safe for the graph to have edges that do not correspond to real conflicts, but not safe to be missing one?
  • What edges does a call add, and what alternative does the allocator have to obeying them?

Connections

DSAundirected-graphadjacency-listdfs
Computer Architectureregisters