Registerssimplified

Linear Scan Allocation

Sort the intervals by start point, sweep once, hand a register back whenever an interval ends, and when nothing is free spill whichever active interval ends last. Much faster than colouring, worse code — which is exactly the trade a JIT wants.

The question

What does an allocator look like when compile time is the thing the user is waiting for?

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

Live intervals sorted by start point, plus two small mutable sets: the free registers and the currently active intervals ordered by end point. There is no graph. The representation deliberately forgets the pairwise conflict structure and keeps only "what is live right now", which is the sole reason the algorithm is linear.

What this phase may assume or do

Identical to colouring — no two simultaneously live values may share a register — but established differently. The sweep guarantees it structurally: a register is only returned to the free set when the interval holding it has ended before the current position, so anything in the free set is provably dead. The correctness argument is an invariant maintained by the sweep rather than a property checked against a graph, which is why the algorithm needs no verification step and why an off-by-one in the expiry test is a silent miscompilation.

Key points

  • Sort intervals by start, sweep once, expire finished intervals back into the free set, allocate from it.
  • When nothing is free, spill whichever of the newcomer and the latest-ending active interval ends last.
  • No graph is built, so the cost is the sort plus a linear pass — an order of magnitude faster than colouring in the original measurements.
  • The spill decision is positional rather than value-based, which is precisely the information the algorithm gave up by not building a graph.
  • JITs use it because allocation time is paid on every compilation while a user waits, and ten percent worse code beats ten times slower compilation at the lower tiers.
  • Modern versions add interval splitting and lifetime holes, which recovers most of the quality gap and costs the strict linearity.

One sweep, two sets

Sort intervals by start point. Walk them in order. At each interval, first expire: any active interval that ended before this one starts is finished, so return its register to the free set. Then allocate: if a register is free, take it and add this interval to the active set. If none is free, something must spill.

The spill rule is the interesting part and the one that gives the algorithm its character. Compare this interval with the active interval that ends *last*. Whichever of the two ends later gets spilled, because it is the one that would block a register for longer. If the incumbent loses, it hands its register to the newcomer and goes to memory; if the newcomer loses, it goes to memory immediately.

That is the entire algorithm. No graph, no simplification stack, no iteration. The cost is dominated by the sort — O(n log n) — and the sweep is linear in the number of intervals with a small constant. Poletto and Sarkar's 1999 paper reported it running an order of magnitude faster than colouring while producing code within about ten percent, and that ratio is why every JIT baseline and many optimizing tiers use it.

The sweep, as implemented in src/compilers/sim/regalloc.ts
1for interval in sort_by_start(intervals):
2    # 1. expire: anything that ended before we start is done
3    for a in active:
4        if a.to < interval.from:
5            free.push(register_of(a))
6            active.remove(a)
7 
8    # 2. allocate
9    if free is not empty:
10        assign(interval, free.pop())
11        active.add(interval)          # kept sorted by end point
12    else:
13        # 3. spill whichever ends last
14        longest = active.last()       # the latest-ending active interval
15        if longest.to > interval.to:
16            assign(interval, register_of(longest))
17            spill(longest)
18            active.replace(longest, interval)
19        else:
20            spill(interval)

The active list is kept sorted by end point so that active.last() is the latest-ending interval in constant time. That ordering is the only data structure in the algorithm, and it is why the whole thing fits on a slide.

The same function, two algorithms

simplifiedThat the two algorithms spill the same *number* of values here is an artefact of our model: hole-free intervals produce an interval graph, and interval graphs are optimally coloured by any left-to-right greedy sweep, so both algorithms hit the peak-pressure bound. On real live ranges with holes the counts genuinely diverge, and that divergence — not the choice of which value — is the usual reported quality gap.

Here is the comparison the module exists to make. The function below has a call in it, six values, and only two registers available. Both algorithms spill exactly two values — but not the same two, and for entirely different stated reasons.

Graph colouring spills %0 and %2: both are long-lived with few uses, which is what its cost heuristic — uses per unit of live range — selects for. It spilled the values that were cheapest to keep in memory. Linear scan spills %2 and %3: at the moment each of them arrives, nothing is free and every active interval ends later, so they lose by position rather than by value. It spilled whatever happened to arrive when the registers were full.

That difference is the whole character of the two algorithms. Colouring asks "which value is least worth a register?" and can answer globally because it has the whole graph. Linear scan asks "what is live right now?" and answers locally because that is all it has kept. Neither is wrong; one has more information and pays for it.

Linear scan, two registers, on a function containing a call
program points →home
%0rax
%1rcx
%2⤓ spilled
%3⤓ spilled
%4rcx
%5rax
2 registers: rax, rcxin a registerspilled to the stack

Read it asCompare with the colouring result on the same function and the same two registers: it spills %0 and %2 instead. Two spills either way — our hole-free interval model guarantees the counts match — but colouring chose the two cheapest values to keep in memory, while linear scan chose whoever showed up when the registers were full. The difference in *which* values, on a function where one of them is in a loop, is the ten percent.

Why JITs choose it, and what they add back

For an ahead-of-time compiler, allocation time is paid once by a developer. For a JIT it is paid on every invocation of the compiler, while a user is waiting and while the interpreter continues running the slow version. A tenfold difference in allocator speed for a ten percent difference in code quality is an easy trade at the bottom tiers, and an obviously wrong one at the top — which is why tiered systems use different allocators at different tiers.

Nobody ships plain 1999 linear scan, though. The important extension is *interval splitting*: allow a value to occupy a register for part of its life and memory for the rest, rather than making the decision once for the whole interval. That is exactly the pessimism our hole-free model exhibits, and it is what the second-generation linear scan of Traub, Holloway and Smith and the widely-copied HotSpot C1 variant address. Once splitting and lifetime holes are added, linear scan closes most of the gap to colouring and stops being linear in the strict sense, but keeps a much better constant factor.

The other reason to know this algorithm is that it makes an excellent fallback. LLVM's -O0 path uses a fast allocator rather than its greedy one, because at -O0 nobody is asking for good code and everyone is asking for a fast build.

The two allocators, side by sidetypical
Graph colouring (Chaitin-Briggs)Linear scan
Data structureInterference graph, quadratic in simultaneous livenessA sorted interval list and two small sets
TimeSuperlinear; plus rebuilds after spillingDominated by the sort; one sweep
Spill choiceGlobal: lowest cost by uses per unit of rangeLocal: whichever active interval ends last
CoalescingNatural — merge non-adjacent nodesAwkward; needs a separate pass or a hint mechanism
Code qualityBetter; the baseline everyone compares againstRoughly within ten percent in the original paper, and closer with splitting
Used byimplementationGCC (IRA, descended from it); optimizing AOT compilers generallyHotSpot C1, many JIT baseline tiers, LLVM's fast -O0 path
Fails badly whenThe function is enormous or machine-generatedA long-lived value is used constantly and gets spilled for ending late

How it works

The steps, in the order the compiler takes them.

  • Compute live intervals and sort them by start point.
  • Maintain a free-register set and an active list sorted by end point.
  • For each interval in order: expire every active interval whose end precedes this interval's start, returning its register to the free set.
  • If a register is free, assign it and insert this interval into the active list in end-point order.
  • Otherwise compare against the latest-ending active interval: whichever of the two ends later is spilled, and the other keeps or takes the register.
  • Record why: our engine reports either "ends later than the newcomer, so it blocks a register for longer" or "nothing was free and every active value ends earlier".

How it breaks

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

  • The expiry test uses <= where it should use < (or the reverse), a register is returned to the free set one point too early, two live values share it, and a value is silently corrupted.
  • A value that is used every iteration of a hot loop is spilled because its interval ends late, and the loop is several times slower than the colouring allocator's version of the same code.
  • The active list is not kept sorted by end point, the "latest-ending" lookup returns the wrong interval, and the algorithm spills a value that had almost expired.
  • Values pinned to specific registers by the ABI are not modelled, so the sweep assigns them elsewhere and arguments arrive in the wrong registers.
  • Copies from out-of-SSA are not coalesced — linear scan has no natural way to do it — and the output is full of register-to-register moves that only a peephole pass removes.

When it helps

  • JIT baseline and warm tiers, where compilation happens during execution and the compile time is user-visible latency.
  • Debug and -O0 builds, where compilation speed is the whole product and code quality is explicitly not.
  • Very large machine-generated functions, where building an interference graph is the compile-time bottleneck.
  • Any allocator you have to write yourself in a weekend. It fits on one page and it works.

When it hurts

  • Hot loops with a long-lived, frequently-used value: the "ends last" rule will pick exactly the wrong victim, because ending late and being used often are not the same property.
  • Code with many copies, since coalescing does not fall out of the algorithm the way it does from a graph.
  • Optimizing ahead-of-time builds, where the compile-time saving buys nothing anyone can perceive.

What it costs

Every one of these is paid by something.

  • Dropping the interference graph buys an order of magnitude of compile time and costs the global view — the spill decision becomes positional, so the algorithm cannot tell a hot value from a cold one.
  • Spilling the latest-ending interval buys a decision rule that is computable in constant time from the active list, and costs correctness of *judgement*: interval length is a poor proxy for how much a value is worth.
  • Adding interval splitting and holes buys most of the quality back and costs the simplicity and the strict linearity that were the reason to choose the algorithm.

What else you could do

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

  • Graph colouring, when compile time is not the binding constraint — see [[graph-coloring-allocation]].
  • Second-chance binpacking and the extended linear scans (Traub et al., HotSpot C1), which add splitting and holes and sit between the two in both cost and quality.
  • Register allocation by trace: allocate well along the hot path and accept whatever happens off it, which suits profile-guided JITs.
  • No allocation at all: keep everything in stack slots, which is what a template JIT and an -O0 build effectively do, and let the hardware's store-to-load forwarding absorb some of the cost.

See it for yourself

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

  • LLVM's comparable fast path: llc -regalloc=fast file.ll beside -regalloc=greedy, and diff both the assembly and the compile time.
  • Spill counts for each: llc -regalloc=fast -stats file.ll 2>&1 | grep -i spill, then again with greedy.
  • HotSpot's C1 allocator in action: run with -XX:TieredStopAtLevel=1 and compare the generated code with full tiering via -XX:+PrintCompilation.
  • Ours: allocateByLinearScan in src/compilers/sim/regalloc.ts, and /compilers/registers runs it beside allocateByColoring on the same function so the two assignments can be diffed directly.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Linear scan is a worse algorithm." It is a different point on a curve. At the tier where it is used, the alternative is not better code — it is the interpreter continuing to run while a slower compiler finishes.
  • "It spills the least important value." It spills whichever of two candidates ends later. That correlates with unimportance only loosely, which is the algorithm's main weakness.
  • "It is linear time." The sort is not, and modern versions with splitting are not linear either. The name describes the sweep, not the complexity.
  • "JITs use it because they are simple." They use it because compilation happens while the user waits. The top tiers of the same JITs use much more elaborate allocators.

Misconceptions

The claim, and what is actually true.

Linear scan and graph colouring differ only in speed.
They differ in what information they keep. Colouring keeps pairwise conflicts and can therefore reason about which value deserves a register; linear scan keeps only the current live set and decides by position.
A faster allocator produces faster code because the compiler gets further.
These are separate budgets. A faster allocator produces the code sooner; whether the code is faster depends entirely on the allocation quality, which is worse.
Once a linear-scan interval is spilled, it is in memory for its whole life.
In the original algorithm, yes — and that is its main weakness. Every serious implementation since adds splitting so that a value can be in a register where it matters and in memory where it does not.

Go deeper

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

overview

Line up every value by when it first appears. Walk the line handing out registers, and take a register back the moment its value is no longer needed. If someone arrives and nothing is free, look at who is holding a register the longest and evict whichever of the two will be around longer. It is much less clever than the graph approach and it runs in a fraction of the time.

practical

You meet this algorithm as the reason JIT-compiled code is not as fast as ahead-of-time-compiled code even after warm-up at the lower tiers, and as the reason -O0 builds are quick. If you are benchmarking a JIT, make sure you are measuring the tier you think you are: comparing a baseline-tier linear-scan allocation against an optimizing AOT build is comparing two deliberately different points on the compile-time curve.

advanced

The lasting interest in linear scan is what it reveals about the shape of the allocation problem. Poletto and Sarkar's result was that discarding the entire pairwise conflict structure — the thing that makes the problem NP-complete — costs only around ten percent of code quality. That says the difficulty is concentrated in a small number of decisions rather than spread through the graph, which is also why splitting recovers most of the remaining gap: it targets exactly the cases where a single all-or-nothing decision was too coarse. The general lesson transfers: before investing in an exact solver for a hard combinatorial problem, find out how much the exactness is actually worth on real inputs. Here the answer was "about ten percent, for ten times the time", and that number determined the architecture of every JIT built since.

How much this depends on

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

simplifiedOur implementation is the original 1999 algorithm with no interval splitting and no lifetime holes, so a value dead in the middle of its interval still occupies a register throughout. Production linear scans add both, which closes most of the quality gap to colouring. Our version is the one that fits on a page, not the one that ships.
simplifiedThat both of our allocators spill the same number of values on the example is a consequence of hole-free intervals producing an interval graph, which any left-to-right greedy sweep colours optimally. Real allocators do not have that guarantee, and the divergence in spill counts is the usual measured quality difference.
implementationHotSpot's C1 uses a linear-scan variant with splitting; V8's TurboFan and JavaScriptCore's optimizing tiers use more elaborate allocators; LLVM's fast allocator at -O0 is simpler still and is not linear scan proper. "JITs use linear scan" is true of a specific set of tiers at a specific time, not a general law.

If you were asked this in an interview

  • Describe linear scan in five sentences, including the spill rule.
  • Why does linear scan spill the interval that ends last, and when is that clearly the wrong choice?
  • Why would a compiler ship two register allocators?

Connections

DSAinterval-schedulingundirected-graph
Computer Architectureregisters
Performancejit-and-warmup