Live Ranges as the Input to Register Allocation

A register allocator never sees variables. By the time it runs, the program has been lowered to instructions over an unbounded set of virtual registers, and the only question left is which of those virtual registers may share one physical register. The answer comes from a single predicate: a virtual register is live at a program point when some path forward from that point reads it before overwriting it. Two values live at the same point cannot share a register, because a write to one would destroy the other. Everything else in register allocation, from the interference graph and the coloring loop to the spill decisions and the coalescing rules, is machinery erected on top of that predicate. If the predicate is wrong in one direction the program miscompiles; if it is wrong in the other the allocator spills values it did not need to spill.

The predicate the allocator needs

Liveness is defined over a control-flow graph whose nodes are basic blocks and whose edges are possible transfers of control. Each block has a def set (virtual registers written before being read in that block) and a use set (virtual registers read before being written). A register in use is live on entry to the block no matter what the block does later. A register in def stops being live at the point of the definition unless a later read revives it.

The equations are backward:

live_out(B) = union of live_in(S) for every successor S of B
live_in(B)  = use(B) union (live_out(B) minus def(B))

A block with two successors contributes the union of both entry states, which is what makes the analysis conservative at joins: a value needed on either path is live before the branch. A loop back edge makes the equations recursive, so they are solved by iteration from an empty initial state until a fixed point is reached. Each pass can only add registers to the sets, so the iteration terminates; the number of passes is bounded by the loop nesting depth in practice and by the number of blocks in the worst case.

The usual representation is a bit vector per block, one bit per virtual register. For a function with a thousand virtual registers a block’s live set occupies 125 bytes, and the union operations are word-at-a-time. Dense bit vectors beat hash sets once the union operation dominates, because the union of two successor sets is the inner loop of the whole analysis: a hash set pays a hash and a probe per element, while a bit vector pays one word operation per 64 values.

Per-instruction liveness is recovered by walking a block backward from its live_out set. Before each instruction, the live set is the set after it, minus the registers the instruction defines, plus the registers it uses. This backward walk is where the allocator gets the point-level facts it actually consumes; block-level sets are only the intermediate.

Intervals, holes, and the shape of a live range

The set of points at which a value is live is its live range. Once the instructions are linearized into some order, a live range becomes a set of positions, and that set is frequently not contiguous. A value defined in both arms of an if-then-else and read after the join is live in both arms but not in the code between them if that code is laid out elsewhere. A value used inside a loop and again after the loop is live across the loop’s exit block but may not be live in blocks that lie between the two in layout order.

Two representations are in common use, and the choice determines the quality of the result. The precise representation stores the actual set of live points, or equivalently the set of blocks in which the value is live, and derives interference exactly. The approximate representation stores one interval from first definition to last use, ignoring holes. The approximate form is what makes linear scan allocation fast; its cost is false interference. A value that is dead across a long stretch of code still occupies a register for that stretch, and it blocks every other value that needs a register there. The precise form is what graph coloring uses, and it is why interference graph construction can produce a graph with far fewer edges than a naive interval model would suggest.

Neither representation is free. Storing precise live sets for every value at every point is quadratic in the size of the function in the worst case: a thousand values and ten thousand instructions is ten million bits, about 1.2 MB, before any graph is built. Compilers routinely accept that cost for the precision, and routinely reject it for large functions by falling back to intervals or by splitting the function into regions.

Where the equations quietly give the wrong answer

The four-line definition above is correct only if the control-flow graph and the instruction semantics are complete. Several ordinary situations make them incomplete, and each produces a specific kind of miscompile.

Calls are a common source. A call instruction does not mention most of the registers it destroys. The calling convention says which registers the callee may overwrite without restoring, and from the allocator’s point of view the call defines all of them. A value that is live across a call therefore interferes with every caller-saved register, whether or not the callee actually touches it. Omitting that implicit definition lets the allocator park a live value in a register the callee will destroy, and the value is silently corrupted. The full treatment of this belongs to calling conventions as constraints on the graph; the point here is that liveness itself is where the clobber set has to be recorded.

Exception handling adds edges that the syntax does not show. In a region with a handler, every instruction that can raise has an implicit successor: the handler’s entry block. A value that is dead on the normal path but read by the handler is live at the raising instruction. Analyses that build the graph from explicit branches alone compute a live set that is too small, and the handler reads a register that has been reused.

Indirect jumps create successors the compiler cannot enumerate. A jump table with a default case has edges to every case plus the default; a computed goto with no default has edges to every label whose address was taken. A successor set that is missing an edge is the same bug in a different costume: some value that is live on the omitted path is declared dead.

Function entry is a fourth case. Values that arrive in registers, including a function’s parameters before they are stored, are live on entry to the entry block. The initial state of the iteration is therefore not always empty: live_in(entry) includes the registers the entry block uses before defining them, plus any ABI-mandated incoming value read before it is written.

A loop that defines a value in its body and reads it at the top of the next iteration makes the value live across the back edge. A single pass over the instruction list in layout order misses this, because the read appears textually before the definition even though control reaches it after. Only fixed-point iteration over the graph catches it, which is why liveness is formulated as a dataflow problem rather than as a scan.

A worked miniature

The following computes block-level liveness for a small graph and then recovers point-level sets by walking backward. Bit vectors are Python integers used as bitsets, one bit per value, which keeps the union operations cheap.

VALUES = ["a", "b", "c", "d"]
BIT = {v: 1 << i for i, v in enumerate(VALUES)}

# blocks: name -> (defs, uses, successors)
blocks = {
    "entry": ({"a"}, set(), ["head"]),
    "head":  (set(), {"a"}, ["body", "exit"]),
    "body":  ({"b"}, {"a"}, ["head"]),
    "exit":  (set(), {"a", "b"}, []),
}

def mask(names):
    m = 0
    for n in names:
        m |= BIT[n]
    return m

live_in = {b: 0 for b in blocks}
live_out = {b: 0 for b in blocks}
changed = True
while changed:                      # iterate to a fixed point
    changed = False
    for b, (defs, uses, succs) in blocks.items():
        out = 0
        for s in succs:
            out |= live_in[s]
        new_in = mask(uses) | (out & ~mask(defs))
        if new_in != live_in[b] or out != live_out[b]:
            live_in[b], live_out[b], changed = new_in, out, True

# point-level liveness inside one block, walking backward
def walk(defs_uses, out_mask):
    live = out_mask
    for op, names in reversed(defs_uses):
        if op == "use":
            live |= mask(names)
        else:
            live &= ~mask(names)
    return live

After the fixed point, live_in["head"] holds a because the block itself uses a before defining anything. live_out["body"] also holds a: body defines only b, head reads a, and the back edge from body to head makes that read happen after the definition of b. Remove the back edge and live_out["body"] becomes empty, which is exactly the failure a linear scan of the instruction list would produce.

What the allocator does with the result

Two values interfere when one is live at a definition of the other. That asymmetric-sounding rule is equivalent to simultaneous liveness once definitions are handled consistently, and it is the form used when the graph is built, because it is cheap to test: at each definition, every value in the live-out set gets an edge to the defined value. The resulting graph is the input to every algorithm in this cluster, from the simplify and select loop to spill cost models. A liveness analysis that is too precise is not a problem; one that is too coarse is a miscompile, and one that is merely imprecise, in the form of interval approximation, shows up as extra spills and extra moves rather than as wrong code. The distinction matters when choosing where to spend effort: exactness at joins and across calls is mandatory, exactness in the middle of a straight-line block usually is not.