Linear Scan Allocation over Sorted Live Intervals

Graph coloring produces good code and costs a liveness analysis, a graph construction, and an iterative simplification over the whole function. For a just-in-time compiler that has milliseconds to produce machine code, that budget does not exist, and the alternative that fits is linear scan: sort the live intervals by starting point, walk them once, and maintain the set of intervals currently occupying registers. The whole allocation is O(n log n) dominated by the sort, with a linear sweep and a small active set. It gives up precision for that speed: collisions between values that are not simultaneously live inflate the intervals and force assignments a precise liveness analysis would have avoided, which shows up as extra spills and extra moves around loops and calls.

The interval model

Linear scan represents each virtual register’s live range as a single interval [start, end], where the positions are indices in a linearized instruction order. The linearization is the crucial assumption: the algorithm treats control flow as if it were a straight line, so a value that is live in two disjoint regions of the layout gets one interval spanning both, including everything between them. The approximation is conservative in the right direction, since an interval that spans a region where the value is dead still blocks registers there, which causes extra spills but never wrong code. It is the source of most of the quality gap.

Positions are usually instruction indices, with a value’s interval starting at its definition and ending at its last use. The convention for whether the end is inclusive matters at boundaries: if a value is defined at position 3 and another is used at position 3, they must not be assigned the same register unless the instruction can read and write it in one step. The standard convention is to make intervals half-open, so that a value dying at position p frees its register for a value born at p when the boundary instruction reads before it writes, and to extend the live range across the boundary when it does not.

Values that are live across a call need their interval to be split at the call, or the allocator must know that the call clobbers caller-saved registers. The simple treatment is to split the interval at each call and treat the pieces as separate intervals, which allows the part before the call to use caller-saved registers and the part after to use callee-saved ones. Without the split, a value live across a call must be assigned a callee-saved register or spilled, and the allocator cannot express the choice.

The sweep

The algorithm maintains an active list of intervals that currently hold registers, sorted by end point. Intervals are processed in order of start point. For each new interval, two steps happen before it is assigned.

First, every interval in active whose end is before the new interval’s start is expired and its register is returned to the free pool. Because active is sorted by end point, the expired ones are a prefix, and the scan stops at the first interval that has not expired.

Second, if no register is free, an interval must be chosen to spill. The naive choice is to spill the new interval and continue. The better choice, and the one that makes linear scan competitive, is to compare the new interval’s end point against the furthest end point in active: if the new interval ends later, spill the active interval with the furthest end, take its register, and insert the new interval. The reasoning is that the interval ending latest is the one that will block the most future allocations, so removing it frees a register for the longest time.

That eviction rule is what separates a usable allocator from a bad one. Spilling the new interval whenever the pool is empty produces a spill for every value that arrives during a high-pressure region; evicting the longest-lived active interval keeps the pressure bounded and pushes the spills onto values that are live across the whole region, which are usually the cheapest to reload.

The spilled interval is not simply discarded. It is marked, and its uses are rewritten to load from a stack slot; the loads need registers too, and the standard approach is to allocate a small number of reserved registers for spill reloads or to re-run the allocation with the spilled value’s interval split into short intervals around each use. The second approach is what makes the result acceptable: a spilled value whose uses are each preceded by a short live interval can have those short intervals allocated to whatever register is free at that point, rather than reserving one for the whole range.

What the sweep gets wrong on real code

Linear scan’s weakness is precisely its strength: the linear model. Four situations produce code that a graph allocator handles better.

A value live in both arms of an if-then-else, read after the join, has an interval spanning the entire construct, including the code between the arms if the layout places it there. In the graph model, the value’s live set is confined to the two arms and the join, and the code between them is free for other values. Linear scan sees one long interval and either spills it or blocks a register across the whole region.

A loop body that uses a value defined before the loop and again after it produces an interval that spans the loop. Every other value live inside the loop interferes with it, which raises the loop’s pressure by one for the whole loop. Coloring allocators that split live ranges at loop boundaries, the subject of live-range splitting, avoid this by keeping the value in memory across the loop and reloading it inside.

Calls in the middle of a long interval force either a split or a callee-saved assignment, as noted above. Without splitting, a function with many calls in a hot region pushes values into the small callee-saved set or into memory, and the code degrades in a way that is not visible from the interval statistics.

The order of intervals is fixed by the sort, and the sort key is the start point, which is a property of where the value is defined rather than of how valuable its allocation is. The simplification order used by coloring can be tuned to the program’s structure; linear scan’s order is the program’s layout, and layout is chosen for other reasons such as branch prediction, code size, and icache behaviour, not for allocation quality.

The variant that closes most of the gap

Second-chance binpacking, from Traub, Holloway and Smith, is the best-known member of the family that assigns each interval a set of holes instead of a single span. The representation changes from a single [start, end] to a start, an end, and a sorted list of [hole_start, hole_end] ranges during which the value is dead. The sweep then tests occupancy at the current position rather than over the whole range, so a value that is dead between two of its uses no longer blocks a register there.

The cost is in the data structure. Testing whether a register is free at a position requires knowing, for each active interval, whether the position falls in a hole, which takes a binary search per active interval or an interval tree. With a small active set the binary searches are cheap, and the quality improvement over plain linear scan is what motivates the extra bookkeeping, on code with branches as well as in straight-line regions whose intervals have holes.

A middle ground keeps the single interval but splits it at points where the pressure would otherwise be forced: before a call, at a loop boundary, at a branch join. Each split creates two intervals that can be allocated independently, and the join point gets a move or a spill/reload pair. The number of splits is bounded by a budget, and the choice of where to split is a heuristic, the same problem that live-range splitting addresses in the graph-coloring setting.

The sweep as code

def linear_scan(intervals, K):
    # intervals: list of (vreg, start, end), sorted by start
    free = list(range(K))
    active = []                 # (end, vreg, reg), kept sorted by end
    assigned, spilled = {}, []

    for vreg, start, end in sorted(intervals, key=lambda t: t[1]):
        # expire everything that ended before this interval begins
        while active and active[0][0] < start:
            _, _, reg = active.pop(0)
            free.append(reg)

        if free:
            reg = free.pop()
            assigned[vreg] = reg
            active.append((end, vreg, reg))
            active.sort()       # small list; insertion is cheaper in practice
        else:
            latest_end, victim, reg = active[-1]
            if latest_end > end:
                # the new interval ends sooner: evict the longer one
                active.pop()
                spilled.append(victim)
                assigned[vreg] = reg
                active.append((end, vreg, reg))
                active.sort()
            else:
                spilled.append(vreg)

    return assigned, spilled

Two details make the difference between this and a correct implementation. The expiration test uses < rather than <=, which treats an interval that ends exactly where the next begins as expired: the two do not overlap, and the register can be reused. Implementations that extend live ranges across read-write instructions avoid the boundary case by making the extended range overlap, and then the test never fires on a genuine interference. The active.sort() calls are placeholders for an insertion into the right position, which keeps the list sorted by end point and makes the expiration prefix scan valid; calling list.sort() on every insertion costs O(n log n) per interval instead of O(n) for a shift, which matters on functions with high pressure.

The spill list is not the end of the story. Each spilled vreg needs its uses rewritten, and the rewritten code needs new short intervals allocated in a second pass, which is why the loop in a real implementation is: scan, rewrite, scan again on the expanded interval set, until the spill set stops changing.

Cost, quality, and where it is used

The asymptotic difference is the reason the algorithm exists. Graph coloring’s iterative simplification and re-coloring after spills can take time superlinear in the function size with large constants; linear scan is one sort plus one sweep, and its constants are small enough that a JIT can run it on every compilation. The quality difference on straight-line code is small, because straight-line code has few holes and low pressure; the difference on branch-heavy code is larger, and the difference on code with many calls and loops is where the two approaches diverge most.

The choice in practice tracks the compilation budget. Ahead-of-time compilers with a large budget use coloring or a hybrid that starts with a fast allocator and upgrades expensive functions to a more precise one; JITs with a small budget use linear scan, often with the lifetime-hole extension; and the boundary between the two is set by how much time the compiler is willing to spend per function rather than by any property of the program.