Live-Range Splitting at Region Boundaries

The interference graph treats a virtual register as one indivisible node, and that indivisibility is an artifact of the representation rather than a property of the program. A value defined once and used in two places a thousand instructions apart does not need one register for the whole span; it needs a register at each use and a way to get the value from the definition to each use. Splitting rewrites the program so that each piece of the live range becomes a separate virtual register, connected by moves or by loads and stores, and the pieces can then be colored independently. The rewrite is legal whenever the program is still correct, and it is profitable whenever the sum of the pieces’ pressure is less than the original’s.

The shape of a split

Splitting after a point p inside a live range of value v creates two values v1 and v2, with v1 live from the definition to p and v2 live from just after p to the uses after p. At p a move v2 <- v1 is inserted, or a store and load pair if the split is a spill. The original uses after p are rewritten to read v2.

The choice of p is the whole problem. A split at a point where the pressure is low does nothing useful: both pieces are still live in the high-pressure region, and the move is pure cost. A split at a point where the pressure is high, such as a call, a loop boundary, or a branch join, separates the value from the region that could not accommodate it, and the piece on the far side may be colored with a register the region freed.

The classical formulation is in terms of regions: identify the loops and the calls, and split values at the boundaries of the regions where they interfere with the most other values. The formulation that production allocators use is more opportunistic: when a value cannot be colored, split it at the boundary of the block where the coloring failed, rather than spilling the whole value. The value then keeps a register in the region where it is cheap to keep and goes to memory only across the region where it is expensive.

Splitting versus spilling

A spill is a split where one of the pieces is stored in memory and all of its uses are reloads. The distinction is one of degree, and the intermediate forms are where the quality comes from.

A value spilled for its whole live range pays a store at the definition and a load at every use, regardless of whether a register was available at any of those points. A value split at a region boundary pays a store at the split, a load at the join, and keeps a register on both sides. If the two sides are both high-pressure, splitting is no better than spilling. If one side is low-pressure, splitting is strictly better, and the difference is the number of uses on the low-pressure side that would otherwise have been reloads.

The decision of where to split is therefore a decision about which regions are worth keeping in registers, and it is the same trade-off as the spill cost model but at a finer granularity. The cost model that evaluates splits should compare, for each candidate boundary, the cost of the moves introduced against the cost of the reloads avoided, weighted by the block frequencies.

A split is not free even when it saves reloads, because the move at the split point costs an instruction and occupies a register at that point. The move is also a candidate for coalescing, and if the allocator coalesces v1 and v2 back together, the split has accomplished nothing. Implementations prevent that by marking the inserted moves as non-coalescible, or by running coalescing before splitting so that the split’s moves are never seen by the coalescer.

Rematerialization as the limiting case

A split where the second piece is recomputed from scratch rather than copied is rematerialization. A constant defined by mov r1, 42 and used a thousand instructions later does not need to be live for the whole span: the second use can be preceded by another mov r1, 42. The live range becomes two short ranges with no connection at all, and the graph loses the long node entirely.

Three conditions must hold for rematerialization to be legal. The defining instruction must be free of side effects and must not depend on values that change between the definition and the recomputation point. It must be cheap: a constant load, an address computation from an invariant, or a load from a location that has not been written. And the recomputation must not be inside a region where the value’s definition is invalid, which for an address computation means the base pointer must still hold the same value.

The gain is largest for values that are live across long regions and used rarely. A constant used once per loop iteration but defined outside the loop is a candidate: rematerializing it inside the loop costs one instruction per iteration, spilling it costs one load per iteration plus a store once, and keeping it in a register costs one register for the whole loop. The comparison depends on the register pressure inside the loop, which is exactly the quantity the allocator is trying to reduce.

Rematerialization interacts with the calling convention in a way that is easy to miss: a value that is rematerializable does not need a callee-saved register, because it can be recomputed after the call. This removes the value’s edges to the caller-saved registers at the call site, which can turn a spill into a colorable assignment. The interaction is the reason some allocators run a rematerialization pass before building the graph, marking the candidates so that the graph construction can omit the long-range edges.

The SSA connection

Splitting is natural in SSA form, where every value has exactly one definition and the live ranges are already the maximal spans of a single definition. The graph built from SSA has a property that makes it tractable: the interference graph of an SSA program in which each variable’s live range is the set of blocks dominated by its definition is chordal, and chordal graphs can be colored optimally in linear time by a perfect elimination ordering. The chordality is the subject of why SSA graphs are easy to color, and it is the reason SSA-based allocators can avoid the heuristic simplification loop entirely.

Leaving SSA destroys the property. The destruction is usually done by inserting copies at the join points where phi functions were, and each copy is a split: the value on one side of the join becomes a separate node from the value on the other. The copies are exactly the moves that coalescing tries to eliminate, and the tension between eliminating them and keeping the ranges short is the central design problem of SSA-based allocation. Allocators that destroy SSA aggressively get small graphs and many moves; allocators that keep the phi structure get large graphs and few moves. The middle ground is to coalesce only where the merge passes the conservative test, and to leave the other copies as splits.

A subtlety: coalescing two SSA values that are connected by a phi can merge live ranges that are not simultaneously live at any point, which is legal, and the merged range can then interfere with values that neither original interfered with. The interference introduced by coalescing is the same phenomenon as the split in reverse, and the conservative tests are what keep it from destroying colorability.

Where the splits go in practice

Three placements dominate. Splitting at loop boundaries separates a value’s life inside a loop from its life outside, which is valuable when the loop is the high-pressure region: the value can live in memory across the loop and in a register elsewhere, or vice versa. Splitting at calls separates the parts of a live range on either side of a call, which gives the allocator two shorter ranges to colour instead of one long one. A value that is live across the call still needs a callee-saved register or a spill slot on both sides; what the split buys is that the pieces before and after the call are independent nodes, so a piece that dies in the call’s neighbourhood does not constrain the rest of the range. Splitting at branch joins separates the values flowing in from different predecessors, which lets each arm of the branch use its own registers and lets the join do the merge.

The third placement is the one that most directly changes the graph’s density. A value that is defined in both arms of an if-then-else and read after the join is live in both arms under the unsplit representation, so it interferes with everything live in both arms. Split at the join, each arm’s value is live only in its own arm, and the code in the other arm is free of it.

A split in code

The following splits a live range at a given instruction index and rewrites the uses. It assumes an instruction list and a per-instruction use map, and it inserts the connecting move.

def split_at(instrs, uses, v, point, fresh):
    # instrs: list of (dst, srcs); uses: position -> list of vregs read
    # fresh: supplies a new virtual register name
    v2 = fresh()
    instrs.insert(point, (v2, [v]))          # v2 <- v at the split point
    for i in range(point + 1, len(instrs)):
        dst, srcs = instrs[i]
        if v in srcs:
            srcs[srcs.index(v)] = v2
    return v2

The inserted move is a real instruction and must be counted in the cost. The rewrite of later uses is what makes the split legal: every read after the split point now reads v2, and the definition still writes v, so the value flows through the move exactly once. Splitting at a point that is not on every path from the definition to the rewritten uses is illegal, because a use reached without passing through the split point would read an undefined v2. Checking that condition is a dominance test: the split point must dominate every use it rewrites, so that every path reaching such a use passes through the move. For uses not dominated by the split point, a different split point or a different mechanism such as a phi-like merge is needed.

That dominance requirement is why splitting is usually performed at block boundaries rather than at arbitrary instructions. A block boundary that post-dominates the definition and dominates the uses is easy to find, and the move can be placed at the top of the block.

The cost of getting it wrong

Three failure modes are worth naming. Splitting a value that is used once creates a move and a new short live range for no benefit; the value was already cheap to keep. Splitting a value at a point where both pieces are live in the same high-pressure region creates two nodes where there was one, and if both need registers in the same region the graph is now harder to color, not easier. The second failure is why splitting is usually driven by the coloring failure rather than applied speculatively: the allocator only splits a value it has already failed to color, and only at a boundary where the pressure is known to drop.

The third is the move itself, which the coalescer may then try to eliminate. A split followed by a coalesce is a no-op that costs compile time and, if the coalescer fails, an instruction. Ordering the passes so that coalescing precedes splitting avoids the first part and leaves the second as a real instruction that the split was worth paying for.