Lesson 22.5 — Linear scan: Poletto–Sarkar, second-chance binpacking, interval splitting, SSA¶

Techniques: Poletto–Sarkar linear scan; second-chance binpacking (Traub–Holloway–Smith); interval splitting with lifetime holes (Wimmer–Mössenböck); SSA-based linear scan (Wimmer–Franz) · Lab: labs/ch22-regalloc E3 (allocateLinearScan), E3★ (allocateLinearScanHoles) · Prerequisites: Lesson 22.1 (live intervals, Definition 22.1.8) · Time: 4–5 hours

Graph colouring spends most of its time building a graph that can have \(\Theta(n^2)\) edges. For a just-in-time compiler that is too slow. Linear scan replaces the graph by the live intervals of Definition 22.1.8, sorted by start point, and allocates in one sweep over them, keeping the set of intervals that currently hold a register [PS99]. The first version gave each value one convex interval and spilled whole intervals. Its successors put back what that simplification lost: lifetime holes and a second chance for spilled values [THS98], optimal split positions [WM05], and finally SSA form, which makes the intervals cheap to compute and the resolution of phis natural [WF10]. HotSpot's client compiler and Graal implement Wimmer's allocators directly; V8's TurboFan uses its own linear scan with live-range splitting.

1. Problem and motivation¶

Input: a function whose instructions are numbered in some linear order of the blocks, the live interval (or ranges) of each value, and \(K\) registers. Output: for each value, or for each piece of a value's interval if splitting is allowed, a register or a stack slot; plus the moves needed where the location changes. Goal: allocation in (near) linear time, with spill code comparable to graph colouring.

Poletto–Sarkar linear scan¶

Poletto and Sarkar designed linear scan for dynamic code generation: it was implemented in icode, the run-time back end of the tcc compiler for 'C (a C extension for generating code at run time), where allocation time is part of the program's run time, and compared with graph colouring in Machine SUIF [PS99]. The algorithm keeps an active list of intervals that overlap the current point, sorted by end. At each new interval it expires the finished ones; if no register is free it spills whichever of the current interval and the active ones ends last, because that one blocks a register for the longest time. They report code of a quality near that of a well-tuned graph-colouring allocator, produced several times faster on medium-sized to large programs [PS99].

Second-chance binpacking¶

Traub, Holloway and Smith treat registers as bins into which interval pieces are packed, allow packing into the lifetime holes of values already in a bin, and give a spilled value a second chance: when it is used again it is reloaded into a register, possibly evicting another value, instead of staying in memory for the rest of its life [THS98]. The price is a resolution pass that inserts moves on CFG edges where a value's location at the end of the predecessor differs from its location at the start of the successor.

Interval splitting with lifetime holes (Wimmer–Mössenböck)¶

Wimmer and Mössenböck made splitting systematic for the HotSpot client compiler (C1): intervals are lists of ranges with use positions; a register is free for an interval "until position \(p\)", and an interval that fits only partly is split at the best position before \(p\), preferably at a block boundary outside loops [WM05]. When no register is free, the register whose next use is furthest away is taken, as in Belady's rule (Lesson 22.2), and the intervals holding it are split and spilled until their next use.

SSA-based linear scan (Wimmer–Franz)¶

On SSA form every value has one definition, which is the start of its interval. Wimmer and Franz show that the intervals can then be built in one backward pass over the blocks, without iterative liveness, provided the blocks of each loop are contiguous in the linear order, and that phis can be resolved together with the moves of splitting [WF10]. No separate out-of-SSA pass is needed before allocation.

2. Definitions and algorithms¶

Poletto–Sarkar linear scan¶

Definition 22.5.1 (Interval notions)

With the slots of Definition 22.1.8, the interval of \(v\) is \(I(v) = [s(v), e(v)]\), the convex hull of its live range. Two intervals overlap if they share a slot. At a position \(p\), an interval is active if it covers \(p\), inactive if \(s(v) \le p \le e(v)\) but \(p\) is in one of its lifetime holes, handled if \(e(v) < p\), and unhandled if \(s(v) > p\). The interval graph of a set of intervals has an edge between every two that overlap; its depth is the largest number of intervals covering one slot.

Definition 22.5.2 (Resolution)

If a value may change location (register, another register, stack slot) along its life, then on every CFG edge \(P \to B\) where its location at the end of \(P\) differs from its location at the start of \(B\) a resolution move is inserted; the moves of one edge form a parallel copy (sequentialized as in Lesson 16.7).

Algorithm 22.5.3 (Poletto–Sarkar linear scan)

Input: intervals \(I(v)\) for all values; \(K\) registers.
Output: for every value a register or "spilled".
Precondition: \(I(v)\) contains every slot at which \(v\) is live or defined.
Postcondition: two values that receive the same register have disjoint intervals (Theorem 22.5.4).
Invariant: before processing interval \(i\), active holds exactly the allocated intervals with \(e \ge s(i)\) after ExpireOldIntervals, sorted by increasing end; \(\lvert \texttt{active} \rvert \le K\); every register not used by an interval in active is in free.

function LinearScan(intervals, K):
    active ← []; free ← {r0, …, r(K−1)}
    for each interval i in order of increasing start (ties: name):
        ExpireOldIntervals(i)
        if |active| = K:
            SpillAtInterval(i)
        else:
            reg[i] ← the lowest register in free; free ← free \ {reg[i]}
            insert i into active (sorted by end)

function ExpireOldIntervals(i):
    for each j in active, in order of increasing end:
        if e(j) ≥ s(i): return
        remove j from active; free ← free ∪ {reg[j]}

function SpillAtInterval(i):
    spill ← the last interval in active (largest end; ties: the later name)
    if e(spill) > e(i):
        reg[i] ← reg[spill]; mark spill spilled
        remove spill from active; insert i into active (sorted by end)
    else:
        mark i spilled

With the slots of Definition 22.1.8 an interval that ends at a use slot \(2j\) and one that starts at the def slot \(2j + 1\) of the same instruction do not overlap, so they may share a register (the result reuses a dying operand's register). The lab's and the drill's convention is e(j) < s(i) for expiry, as in the paper.

Theorem 22.5.4 (Poletto–Sarkar produces valid assignments)

If every interval contains its value's live range, then two values assigned the same register by Algorithm 22.5.3 do not interfere (Definition 22.1.5). If the depth of the interval graph is at most \(K\), nothing is spilled.

Proof

Validity. A register is handed out only when it is in free. By the invariant, a register is in free only if no interval in active holds it; an interval leaves active either by expiring (\(e(j) < s(i)\), so it ends before every later interval starts) or by being spilled (it loses the register, which is passed to \(i\)). Hence when \(i\) receives register \(r\), every earlier holder of \(r\) that is not spilled ends before \(s(i)\), and later holders start after \(i\) has expired. So the intervals of the non-spilled holders of \(r\) are pairwise disjoint. If \(u\) and \(v\) interfere, some point has both defined or live (Theorem 22.1.12), so their live ranges, and thus their intervals, share a slot: they cannot hold the same register. No spill at depth \(\le K\). SpillAtInterval runs only when \(K\) intervals in active cover \(s(i)\) (they started no later and have not expired), and \(i\) covers it too: \(K + 1\) intervals at one slot, more than the depth.

Proposition 22.5.5 (Interval graphs are perfect)

For a set of intervals, the chromatic number of the interval graph equals its depth (its largest clique). Colouring greedily in order of increasing start with the lowest free colour achieves it.

Proof

Every slot's covering intervals form a clique, so \(\chi \ge\) depth. Conversely, when the greedy colouring handles interval \(i\), the intervals already coloured that overlap it all contain \(s(i)\) (they started no later and end at or after \(s(i)\)), so there are at most depth \(- 1\) of them and a colour among the first depth is free. This is Algorithm 22.5.3 with \(K\) = depth, which by Theorem 22.5.4 never spills.

Second-chance binpacking¶

Definition 22.5.6 (Bins, holes, second chance)

In binpacking each register is a bin holding a set of interval pieces with pairwise disjoint ranges; a new piece fits in a bin if it overlaps none of them, possibly because it falls into their lifetime holes. A second chance is the reallocation of a spilled value at its next use: it is reloaded into a register there instead of being read from memory for the rest of its life.

Algorithm 22.5.7 (Second-chance binpacking, after [THS98])

Input: ranges and use positions of every value; a linear order of the blocks; \(K\) bins.
Output: a location for each value at each position; spill stores, reloads and resolution moves.
Precondition: ranges are exact (holes included).
Postcondition: at every position no two values that are live there share a bin, and every use finds its value in a register.
Invariant: walking positions in increasing order, each bin holds at most one value whose range covers the current position; a value's current location is recorded in loc[v] and is a bin or its stack slot.

function SecondChance(values, K):
    for each position p in order:
        for each value v used at p:
            if loc[v] is its stack slot:                       # second chance
                b ← a bin that is free over v's next range piece, or
                    the bin whose occupant's next use is furthest (evict it: store if dirty)
                emit "reload v into b" before p; loc[v] ← b
        for each value d defined at p:
            b ← a bin free over d's range (lifetime holes of occupants count as free), or
                evict as above; loc[d] ← b
        for each value whose range ended at p: free its bin
    Resolve()                               # moves on edges where loc differs (Definition 22.5.2)

The stack copy must be up to date whenever a second chance reloads it; Traub et al. discuss where to place the spill stores so that this holds on every path [THS98].

Interval splitting with lifetime holes (Wimmer–Mössenböck)¶

Algorithm 22.5.8 (Linear scan with interval splitting, after [WM05])

Input: intervals as sorted range lists with use positions (definitions and uses that need a register); fixed intervals for pre-coloured registers; \(K\) registers.
Output: a register or stack slot for every piece of every interval; split positions.
Precondition: positions are the slot numbers of Definition 22.1.8; each use position lies inside a range of its interval.
Postcondition: no two pieces with the same register overlap; every use position lies in a piece with a register. After Resolve, the program is correct (Theorem 22.5.9).
Invariant: at position \(p\) = start of current, active holds the allocated pieces covering \(p\) and inactive those whose hull contains \(p\) but which are in a hole.

function Walk(unhandled, K):
    while unhandled ≠ ∅:
        current ← the piece with the lowest start p
        move active pieces that ended to handled, those in a hole to inactive,
             and inactive pieces covering p back to active
        if not TryAllocateFreeReg(current): AllocateBlockedReg(current)

function TryAllocateFreeReg(current):
    freeUntil[r] ← ∞ for every r
    for each piece in active:   freeUntil[reg(piece)] ← 0
    for each piece in inactive overlapping current:
        freeUntil[reg(piece)] ← min(freeUntil[reg(piece)], next intersection with current)
    r ← the register with the largest freeUntil
    if freeUntil[r] ≤ p + 1: return false                  # no register free right now
    if freeUntil[r] > end(current): reg(current) ← r        # free for the whole piece
    else: reg(current) ← r; split current before freeUntil[r]; put the rest in unhandled
    return true

function AllocateBlockedReg(current):
    nextUse[r] ← ∞ for every r
    for each piece in active and inactive (overlapping current) with register r:
        nextUse[r] ← min(nextUse[r], next use position of that piece after p)
    r ← the register with the largest nextUse
    if nextUse[r] < first use of current:
        spill current from p until just before its first use; put the rest in unhandled
    else:
        reg(current) ← r
        for each piece holding r that overlaps current:
            split it at p; spill the part from p until its next use;
            put the part from its next use in unhandled          # its second chance

Wimmer and Mössenböck choose split positions carefully: as late as possible, but moved to a block boundary of an outer loop when that lowers the executed spill code [WM05]. The course's oracle regalloc.linear_scan_split splits exactly at the positions above.

Theorem 22.5.9 (Splitting with resolution is correct)

If after Walk no two pieces with the same register overlap and every use lies in a piece with a register, then inserting (i) a store at each split point where a piece in a register is followed by a spilled piece, (ii) a load where a spilled piece is followed by a piece in a register, (iii) a move where two consecutive pieces have different registers, and (iv) resolution moves on CFG edges (Definition 22.5.2), yields a program that reads, at every use, the value the original program reads.

Proof

Consider one value \(v\) and the linear order. Within a block, consecutive pieces of \(v\) are connected by the moves (i)–(iii) placed at the split point, which lies between two instructions of the block; so along every path inside the block, \(v\)'s current location holds its value, by induction over the positions. Across an edge \(P \to B\), the location at the end of \(P\) and at the start of \(B\) are the locations of the pieces covering those two slots; they need not be neighbours in the linear order, which is why (iv) inserts a move on the edge itself (on a split edge if \(P\) has several successors). The moves of one edge for all values form a parallel copy: reading all sources before writing any destination is correct because the pieces at the start of \(B\) with the same register do not overlap (so destinations are distinct) and each source is the location of a different live value at the end of \(P\). No other value's location is overwritten by these moves: a destination register \(r\) at the start of \(B\) is held by \(v\)'s piece, and no other piece holding \(r\) covers that slot. A store (i) followed later by a load (ii) of the same slot is correct because \(v\)'s stack slot is written only by stores of \(v\). Hence every use of \(v\) reads \(v\)'s value.

SSA-based linear scan (Wimmer–Franz)¶

Algorithm 22.5.10 (Building intervals in one pass on SSA, after [WF10])

Input: a strict SSA function; a linear order of its reachable blocks in which every block comes after its dominator and the blocks of each loop are contiguous; for each loop header its last block in the order.
Output: ranges for every value; liveIn(b) for every block.
Precondition: the order conditions above.
Postcondition: each value's ranges cover exactly the slots where it is live (Theorem 22.5.11).
Invariant: when block \(b\) is processed (blocks in reverse order), liveIn is final for every block after \(b\) except loop headers of loops containing \(b\), whose missing values are added by the loop-end extension.

function BuildIntervals(blocks):
    for each block b in reverse order:
        live ← ∪ over successors s of b of liveIn(s)
        for each phi φ of each successor s: live ← live ∪ {operand of φ from b}
        for each v in live: addRange(v, from(b), to(b))
        for each instruction op of b, in reverse order (phis excluded):
            if op defines d: setFrom(d, pos(op)); live ← live \ {d}   # shorten to the def
            for each operand u of op: addRange(u, from(b), pos(op)); live ← live ∪ {u}
        for each phi φ of b: live ← live \ {φ}     # φ's range starts at from(b)
        if b is a loop header:
            for each v in live: addRange(v, from(b), to(loopEnd(b)))   # live around the loop
        liveIn(b) ← live

Theorem 22.5.11 (One pass suffices on SSA with contiguous loops)

Under the preconditions of Algorithm 22.5.10, the computed ranges equal the live ranges of Definition 22.1.8.

Proof sketch (full proof: [WF10])

Without back edges, processing blocks in reverse order is the standard backward liveness walk: every successor has been processed, so live at the end of \(b\) is exact. A back edge \(t \to h\) is the only way a successor (\(h\)) can be processed before its final liveIn is needed. The values missing from \(h\)'s liveIn when \(t\) is processed are values live at \(h\)'s start that are used somewhere in the loop. In strict SSA such a value \(v\) is defined outside the loop or is a phi of \(h\) (its definition dominates \(h\), since it dominates a use reached from \(h\) without passing it); a phi of \(h\) is removed from live, so \(v\) is defined before \(h\). Such a value is live in every block of the loop, because every block of the loop reaches \(h\) through the back edge. Extending its range over the contiguous span \([\mathrm{from}(h), \mathrm{to}(\mathrm{loopEnd}(h))]\) adds exactly those slots. Nested loops are handled from the inside out, because an inner header is processed before its outer one.

3. Worked example¶

Poletto–Sarkar linear scan¶

The running example's intervals (Lesson 22.1 §3): a [1, 20], i [5, 16], s [5, 20], c [7, 8], t [11, 12], u [13, 14], s2 [15, 19], i2 [17, 19], r [21, 22]. With \(K = 3\) (regalloc.linear_scan; "active" lists name[start,end]:reg, sorted by end):

current	expired	action	active after	free after
a [1, 20]	—	a → r0	a[1,20]:r0	r1 r2
i [5, 16]	—	i → r1	i[5,16]:r1; a[1,20]:r0	r2
s [5, 20]	—	s → r2	i[5,16]:r1; a[1,20]:r0; s[5,20]:r2	—
c [7, 8]	—	full: furthest end is `s` (20, tie with `a` broken by name: the later name) > 8: spill `s`, c takes r2	c[7,8]:r2; i[5,16]:r1; a[1,20]:r0	—
t [11, 12]	c	t → r2	t[11,12]:r2; i; a	—
u [13, 14]	t	u → r2	u[13,14]:r2; i; a	—
s2 [15, 19]	u	s2 → r2	i[5,16]:r1; s2[15,19]:r2; a	—
i2 [17, 19]	i	i2 → r1	i2[17,19]:r1; s2; a	—
r [21, 22]	i2, s2, a	r → r0	r[21,22]:r0	r1 r2

Linear scan spills s (spill cost 21), where graph colouring spilled a (13) in Lesson 22.3: the furthest-end rule looks at interval ends, not at costs or uses. It also leaves the copies s ← s2 (r2 vs spilled s: a store on the back edge) and i ← i2 (r1 and r1: none). With \(K = 4\) nothing is spilled (depth 4, Proposition 22.5.5), but the moves s2 → s remain (r3 vs r2): linear scan does not coalesce.

Try it

./course drill linear-scan --seed 1 --difficulty hard --solution computes intervals from a random program with this slot numbering and scans them.

Second-chance binpacking¶

The precise ranges of the running example have one hole: s is live on [5, 10] and [20, 20] (dead in the loop body after t = mul s i, live again in the exit block). Binpacking may therefore place a in s's bin during the hole. The next worked example (splitting) shows the effect, together with the second chance of a.

Interval splitting with lifetime holes (Wimmer–Mössenböck)¶

Algorithm 22.5.8 with \(K = 3\) on the running example (regalloc.linear_scan_split); use positions: a at 1, 3, 12, 20; i at 5, 6, 10, 14, 16; s at 5, 10, 20; c at 7, 8:

position	current	decision
1	a [1, 20]	r0 free for ever: a → r0
5	i [5, 16]	r1 free: i → r1
5	s [5, 10] ∪ [20, 20]	r2 free: s → r2
7	c [7, 8]	no register free. Next uses: r0 (`a`) at 12, r1 (`i`) at 10, r2 (`s`) at 10. r0 is used furthest away and 12 > 7 (c's first use): split `a` at 7; `a`[7, 11] is spilled, `a`[12, 20] goes back to unhandled; c → r0
11	t [11, 12]	r0 free again: t → r0
12	a [12, 20]	second chance for `a`: r2 is in `s`'s hole until 20: a[12, 19] → r2, split at 20
13	u [13, 14]	u → r0
15	s2 [15, 19]	s2 → r0
17	i2 [17, 19]	i2 → r1
20	a [20, 20]	r0 free: a → r0
21	r [21, 22]	r → r0

Nothing is spilled for good: a lives in r0, then in memory while c needs a register, then in r2 inside the lifetime hole of s, then in r0 again. The resolution moves are: a store of a at 7, a reload at 12 (both in the loop, weight 10), r0 ← r2 on the back edge \(B2 \to B1\) (a ends the body in r2 but is expected in r0 at the header), and a reload of a into r0 on the exit edge \(B1 \to B3\) (a is in memory at the end of B1). Four moves, three of them in the loop, against Poletto–Sarkar's spill of s with a store and a reload per iteration; which is cheaper depends on the machine. The point is the mechanism: holes and splitting let one value use three different homes.

SSA-based linear scan (Wimmer–Franz)¶

Algorithm 22.5.10 on the running example with the order B0, B1, B2, B3 (B1 is a loop header, its loop is {B1, B2}, loop end B2, slots of B1–B2 = [4, 19]):

block (reverse order)	live at end	after walking the block	loop extension	liveIn
B3 [20, 23]	{}	`r` [21, 22]; `s` and `a` get [20, 20] (used by `r = add s a` at slot 20)	—	{a, s}
B2 [10, 19]	liveIn(B1) = {} so far, plus phi operands `i2`, `s2`	`i2` [17, 19], `s2` [15, 19], `u`, `t`; `i` [10, 16], `a` [10, 12], `s` [10, 10]	—	{a, i, s}
B1 [4, 9]	liveIn(B2) ∪ liveIn(B3) =	`c` [7, 8]; `i`, `s` [5, 9] (the phis are defined at slot 5 and leave `live`); `a` [4, 9]	B1 is a header: `a` is still live → add [4, 19]	{a}
B0 [0, 3]	{a} (and the phi operand `a` for `s`)	`a` [1, 3]	—	{}

The loop extension is what an iterative analysis would have discovered with a second pass: a is live in the whole loop because the back edge reaches the header while a is still needed. The result equals the ranges of §3 above, with a = [1, 20] and s = [5, 10] ∪ [20, 20].

4. Invariants and correctness¶

Poletto–Sarkar linear scan¶

Theorem 22.5.4 (validity; no spills at depth \(\le K\)) and Proposition 22.5.5 (optimal colouring of an interval graph) are in §2. The invariant of Algorithm 22.5.3 is maintained because ExpireOldIntervals removes exactly the intervals ending before \(s(i)\) (the list is sorted by end, so it stops at the first one that does not), and SpillAtInterval either swaps \(i\) for the spilled interval in active or leaves active unchanged.

Hulls cost spills

Poletto–Sarkar's interval of s is [5, 20] although s is dead between 11 and 19. The interval graph therefore has edges s–t, s–u, s–s2, s–i2 that the interference graph of Lesson 22.1 does not have. With \(K = 3\) the furthest-end rule then spills s. Theorem 22.5.4 is still true (the hull contains the live range), but the allocation pays for conflicts that do not exist. Lifetime holes (second chance, Wimmer–Mössenböck) remove this loss.

Second-chance binpacking¶

The invariant of Algorithm 22.5.7 (one covering value per bin at each position) gives validity inside blocks; resolution gives validity across edges by Theorem 22.5.9's argument. Traub et al. note that the second chance makes the allocation of a value depend on the linear order: a value can be in a register at the end of one predecessor and in memory at the end of another, which is exactly what resolution repairs [THS98].

Interval splitting with lifetime holes (Wimmer–Mössenböck)¶

Theorem 22.5.9. The walk terminates because every split produces a piece that starts strictly later than the current position (a split at \(p\) puts the part from the next use \(> p\) into unhandled, and a piece that is spilled until its first use restarts at that use), and pieces never grow: the multiset of piece starts increases.

SSA-based linear scan (Wimmer–Franz)¶

Theorem 22.5.11. The precondition matters: if the blocks of a loop are not contiguous, the loop-end extension \([\mathrm{from}(h), \mathrm{to}(\mathrm{loopEnd}(h))]\) covers blocks outside the loop and makes ranges too long (still sound, less precise); if a block precedes its dominator, a use may be processed after the value's definition was already passed, and the range would be cut wrongly.

5. Complexity¶

\(n\) = values (intervals), \(N\) = instructions, \(K\) registers, \(R\) = total number of ranges, \(S\) = number of splits.

Algorithm	Time (worst)	Time (typical)	Space	Justification
Interval construction (iterative liveness)	\(O(b \cdot n)\) per pass × passes	2–3 passes	\(O(b \cdot n)\) bits	Ch 14
Interval construction on SSA (Algorithm 22.5.10)	\(O(N + b \cdot L)\)	linear	\(O(n + R)\)	one pass over blocks; each block adds a range per live value
Poletto–Sarkar	\(O(n \log n + n \log K)\)	sort + \(O(n K)\) scan	\(O(n)\)	sort by start; `active` holds \(\le K\) intervals, kept sorted
Second-chance / Wimmer–Mössenböck	\(O((n + S) \cdot K \cdot R_{\max})\)	near-linear	\(O(n + R)\)	each piece scans \(K\) registers and intersects range lists
Resolution	\(O(e \cdot L)\)	small	\(O(L)\) per edge	one parallel copy per edge

Pathological family. For Poletto–Sarkar: \(m\) values, each live on two short ranges far apart, \([2j, 2j+1] \cup [2m + 2j, 2m + 2j + 1]\). Their true live ranges never overlap (depth 1 without holes), but their hulls \([2j, 2m + 2j + 1]\) all overlap at slot \(2m\): the interval graph is complete, and with \(K\) registers Poletto–Sarkar spills \(m - K\) values that a hole-aware allocator puts in a single register. For Wimmer–Mössenböck without careful split placement: a value used once before and once after a loop of many blocks, with every register busy in the loop, is split at the loop entry and exit; placing a split inside the loop instead would add a load per iteration, which is why split positions are moved to block boundaries of outer loops [WM05].

Poletto–Sarkar linear scan¶

Spill by weight, not end. Spill the active interval with the lowest spill weight per length. Trade-off: better code on loops; loses the "blocks the register longest" rationale that makes the rule optimal for unit weights on interval graphs [CL95].
Binpacking into holes (LLVM 2.x RALinScan kept an inactive_ list for this) — see second chance.

Second-chance binpacking¶

Early versus late spill stores. Store at the definition once (if the value is ever evicted) or at each eviction [THS98]. Trade-off: fewer stores in loops versus stores on paths that never reload.
Move coalescing by hints. Prefer the register of a copy's source; used by all production linear scans. Trade-off: cheap, not guaranteed.

Interval splitting with lifetime holes (Wimmer–Mössenböck)¶

Optimal split positions outside loops, and spill store elimination when a value is already in its slot [WM05]. Trade-off: more analysis per split, much less spill code in loops.
Trace-based allocation (Eisl et al.): allocate each trace (a hot path) with a linear scan and different strategies for cold traces [EGS+16]. Trade-off: compile time spent where it matters.

SSA-based linear scan (Wimmer–Franz)¶

Phi resolution in the data-flow resolution pass instead of an out-of-SSA pass [WF10]. Trade-off: fewer moves; the allocator must understand phis.
Lifetime analysis on SSA without contiguous loops via the fast liveness sets of Boissinot et al. [BHG+08]. Trade-off: no ordering constraint, one more analysis.

7. In real compilers¶

Poletto–Sarkar linear scan¶

LLVM used linear scan from version 1.x until 2.9 (llvm/lib/CodeGen/RegAllocLinearScan.cpp at llvmorg-2.9.0, class RALinScan), with an inactive_ list for lifetime holes and backtracking on spills; LLVM 3.0 replaced it with the basic and greedy allocators (Lesson 22.8) [LLVM29-LinScan]. Go's allocator calls itself "a version of a linear scan register allocator" but allocates greedily in one pass over the blocks with Belady's eviction (Lesson 22.2) [Go-regalloc]. The lab's E3 is Poletto–Sarkar.

LLVM 2.9's linear scan: unhandled heap by start, active and inactive lists

Reproduce (LLVM tag llvmorg-2.9.0; curl reads the pinned source):

curl -s https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-2.9.0/llvm/lib/CodeGen/RegAllocLinearScan.cpp \
  | sed -n '152,165p;596,615p'

Output (complete):

    IntervalPtrs fixed_;

    /// active_ - Intervals that are currently being processed, and which have a
    /// live range active for the current point.
    IntervalPtrs active_;

    /// inactive_ - Intervals that are currently being processed, but which have
    /// a hold at the current point.
    IntervalPtrs inactive_;

    typedef std::priority_queue<LiveInterval*,
                                SmallVector<LiveInterval*, 64>,
                                greater_ptr<LiveInterval> > IntervalHeap;
    IntervalHeap unhandled_;

  while (!unhandled_.empty()) {
    // pick the interval with the earliest start point
    LiveInterval* cur = unhandled_.top();
    unhandled_.pop();
    ++NumIters;
    DEBUG(dbgs() << "\n*** CURRENT ***: " << *cur << '\n');

    assert(!cur->empty() && "Empty interval in unhandled set.");

    processActiveIntervals(cur->beginIndex());
    processInactiveIntervals(cur->beginIndex());

    assert(TargetRegisterInfo::isVirtualRegister(cur->reg) &&
           "Can only allocate virtual registers!");

    // Allocating a virtual register. try to find a free
    // physical register or spill an interval (possibly this one) in order to
    // assign it one.
    assignRegOrStackSlotAtInterval(cur);

What to notice: the loop is Algorithm 22.5.3: pick the interval with the earliest start (unhandled_ is a min-heap by start), expire (processActiveIntervals), then assign or spill. inactive_ ("a hole at the current point": the comment's "hold" is a typo) is the extension to lifetime holes of Definition 22.5.1, which Poletto and Sarkar's convex intervals do not need. The current LLVM 23 has no linear scan; this historical source is quoted because it is the best-known production use of the algorithm.

Second-chance binpacking¶

V8's TurboFan allocator (src/compiler/backend/register-allocator.cc, LinearScanAllocator::AllocateRegisters, V8 12.4) splits live ranges, spills the pieces in deferred (cold) code, and gives them a register again at their next use: the second chance, with spill and reload moves placed as "gap moves" between instructions [V8-RegAlloc]. GCC's LRA can split pseudos and reload them into different registers at different uses (gcc/lra-constraints.cc) [GCC-LRA].

V8 TurboFan: registers in the loop, spills and reloads only in the deferred block

Reproduce (node v22.22.2, V8 12.4.254.21; x86-64 Linux):

cat > ls.js <<'EOF'
function f(a, n) {
  let s = 0, t = 1;
  for (let i = 0; i < n; i++) { s = (s + a[i] * t) | 0; t = (t * 3 + i) | 0; }
  return (s ^ t) | 0;
}
const a = new Int32Array(64).map((_, i) => i);
%PrepareFunctionForOptimization(f); f(a, 64); f(a, 64); %OptimizeFunctionOnNextCall(f);
console.log(f(a, 64));
EOF
node --allow-natives-syntax --trace-turbo-graph --trace-turbo-filter=f ls.js 2>&1 \
  | awk '/Instruction sequence after register allocation/,0' | sed -n '/^B9:/,/^B14:/p' \
  | grep -E '^B[0-9]+:|stack:[0-9]|ArchCallCodeObject'

Output (complete):

B9: AO#8 (no frame) loop blocks: [9, 14)  instructions: [35, 37)
B10: AO#9 (no frame)  instructions: [37, 53)
          X64Cmp && deoptimize if unsigned greater than or equal [rax|R|w32] [rdi|R|w64] #2 [immediate:3] [stack:-1|t] [rcx|R|t] [rdx|R|t] [stack:5|t] [r11|R|w32] [r12|R|w32] [rax|R|w32] [rdx|R|t]
          [r14|R|w64] = X64Add32 && deoptimize if overflow [r14|R|w64] #1 #1 [immediate:2] [stack:-1|t] [rcx|R|t] [rdx|R|t] [stack:5|t] [r11|R|w32] [r12|R|w32] [rax|R|w32] [rdx|R|t]
B11: AO#10 (no frame)  instructions: [53, 54)
B12: AO#14 (deferred)  instructions: [54, 56)
      54: gap ([stack:11|w32] = [r11|R|w32]; [stack:6|w32] = [r12|R|w32]; [stack:7|w64] = [r14|R|w64]; [stack:8|w64] = [r9|R|w64]; [stack:9|t] = [r8|R|t]; [stack:10|w64] = [rdi|R|w64]; [rbx|R|w64] = [constant:v14]; [rax|R|w64] = [constant:v15]; [rsi|R|t] = [constant:v16]) ()
          [rax|R|t] = ArchCallCodeObject [immediate:0] #0 [immediate:1] [stack:-1|t] [stack:-2|t] [stack:-3|t] [stack:5|t] [stack:11|w32] [stack:6|w32] [stack:7|w64] [rbx|R|w64] [rax|R|w64] [rsi|R|t] #0
      55: gap ([rcx|R|t] = [stack:-2|t]; [rdx|R|t] = [stack:-3|t]; [r11|R|w32] = [stack:11|w32]; [r12|R|w32] = [stack:6|w32]; [r14|R|w64] = [stack:7|w64]; [r9|R|w64] = [stack:8|w64]; [r8|R|t] = [stack:9|t]; [rdi|R|w64] = [stack:10|w64]) ()
B13: AO#7 (no frame)  instructions: [56, 57)
B14: AO#11 (no frame)  instructions: [57, 61)

What to notice: B9–B13 are the loop. In the hot blocks B9–B11 every value is in a register ([r14|R|w64], [r11|R|w32] …); only the frame arguments [stack:-1], [stack:5] live on the stack. B12 is the loop's stack/interrupt check, marked deferred (cold): its call clobbers all registers, so the gap move before it stores the six live values to spill slots ([stack:11|w32] = [r11|R|w32], …) and the gap after it reloads them. Their live ranges were split around the deferred block, spilled there, and given registers again at the next use: second-chance allocation, with the spill code only where it rarely runs.

Interval splitting with lifetime holes (Wimmer–Mössenböck)¶

HotSpot's client compiler C1 is Wimmer and Mössenböck's allocator: LinearScanWalker::alloc_free_reg computes, for each register, the position until which it is free (_use_pos), and LinearScanWalker::alloc_locked_reg / split_and_spill_interval implement the blocked case (src/hotspot/share/c1/c1_LinearScan.cpp, jdk-21+35) [HS-C1LinearScan]. Graal's LinearScan (jdk.graal.compiler.lir.alloc.lsra, vm-24.1.0) cites the same paper [Graal-LSRA].

HotSpot C1: free-until positions and splitting

Reproduce (OpenJDK tag jdk-21+35; curl reads the pinned source):

curl -s 'https://raw.githubusercontent.com/openjdk/jdk/jdk-21%2B35/src/hotspot/share/c1/c1_LinearScan.cpp' \
  | sed -n '5466,5468p;5508,5510p;5525,5530p'

Output (complete):

  // _use_pos contains the start of the next interval that has this register assigned
  // (either as a fixed register or a normal allocated register in the past)
  // the register must be free at least until this position
  int reg_needed_until = cur->from() + 1;
  int interval_to = cur->to();
  } else {
    reg = find_free_reg(reg_needed_until, interval_to, hint_reg, any_reg, &need_split);
    if (reg == any_reg) {
      return false;
    }
    split_pos = _use_pos[reg];

What to notice: _use_pos[reg] is freeUntil[r] of Algorithm 22.5.8 (it also counts inactive intervals, i.e. lifetime holes, and fixed intervals for pre-coloured registers). find_free_reg needs the register free "at least until" cur->from() + 1, and if it is not free until cur->to(), need_split is set and the interval is split at split_pos: the TryAllocateFreeReg case. java -XX:+PrintLIRWithAssembly or -XX:+TraceLinearScanLevel would show the decisions, but only in debug builds of the JVM, so the pinned source is quoted.

SSA-based linear scan (Wimmer–Franz)¶

Graal ships an SSA variant of its linear scan: SSALinearScan keeps the LIR in SSA form through allocation, uses an SSA-aware lifetime analysis and resolves phis in the data-flow resolution pass with an SSAMoveResolver (jdk.graal.compiler.lir.alloc.lsra.ssa, vm-24.1.0), the design of Wimmer and Franz [WF10, Graal-LSRA]. Cranelift's regalloc2 also takes SSA input with block parameters (Lesson 22.6).

Graal's SSA linear scan

Reproduce (Graal tag vm-24.1.0; curl reads the pinned source):

U=https://raw.githubusercontent.com/oracle/graal/vm-24.1.0/compiler/src/jdk.graal.compiler/src/jdk/graal/compiler/lir/alloc/lsra
curl -s $U/LinearScan.java | sed -n '72,74p'
curl -s $U/ssa/SSALinearScan.java | sed -n '41,63p'

Output (complete):

 * An implementation of the linear scan register allocator algorithm described in
 * <a href="http://doi.acm.org/10.1145/1064979.1064998" > "Optimized Interval Splitting in a Linear
 * Scan Register Allocator"</a> by Christian Wimmer and Hanspeter Moessenboeck.
public final class SSALinearScan extends LinearScan {

    public SSALinearScan(TargetDescription target, LIRGenerationResult res, MoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, int[] sortedBlocks,
                    boolean neverSpillConstants) {
        super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks, neverSpillConstants);
    }

    @Override
    protected MoveResolver createMoveResolver() {
        SSAMoveResolver moveResolver = new SSAMoveResolver(this);
        assert moveResolver.checkEmpty();
        return moveResolver;
    }

    @Override
    protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() {
        return new SSALinearScanLifetimeAnalysisPhase(this);
    }

    @Override
    protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() {
        return new SSALinearScanResolveDataFlowPhase(this);
    }

What to notice: the SSA allocator is the Wimmer–Mössenböck allocator with three phases replaced: lifetime analysis (Algorithm 22.5.10 needs no iteration on SSA), the move resolver, and data-flow resolution, which is where the phis' parallel copies are inserted together with the splitting moves (Definition 22.5.2). There is no separate out-of-SSA pass before allocation.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Poletto–Sarkar linear scan	whole-interval spills; hulls add false conflicts	\(O(n \log n)\) · fastest global allocator	spills by end, not cost; no coalescing	small	early JITs, teaching, the lab's E3
Second-chance binpacking	uses holes; spilled values get registers back	near-linear	close to graph colouring [THS98]	moderate (resolution)	V8 TurboFan (splitting, deferred spills)
Interval splitting (Wimmer–Mössenböck)	split at optimal positions; Belady-style eviction	near-linear	good; spill code outside loops	large	HotSpot C1, Graal, V8
SSA-based linear scan (Wimmer–Franz)	same, plus exact intervals in one pass	linear lifetime analysis	as above, fewer phi moves	large	Graal `SSALinearScan`

Measured in the lab (ch22-compare, \(K = 4\)): Poletto–Sarkar spills 2499 values (weighted spill cost 105719) and leaves 1411 moves; the hole-aware variant E3★ spills 1914 (77647); IRC 2269 (68935); SSA colouring 2528 (68351). Linear scan was also 3–4× faster than IRC (25 ms against 100 ms for the 414 functions).

Choose Poletto–Sarkar when allocation time dominates (a baseline JIT) and spill quality is secondary. Choose second-chance binpacking or Wimmer–Mössenböck splitting when you want linear-scan speed with near-colouring quality. Choose the SSA variant when your IR is SSA up to allocation (it saves the liveness iteration and the out-of-SSA pass).

9. Assessment¶

Quiz (./course quiz 22): ls-spill-running, ls-no-spill-depth, ls-hull-false-conflict, second-chance-meaning, wm-free-until, wm-blocked-choice, wf-loop-extension, wf-order (tags linear-scan, second-chance, lifetime-holes, ssa-linear-scan).
Drill: ./course drill linear-scan (spilled set, registers; hard: intervals from a program). The splitting variant has no drill: its decisions depend on use positions and split heuristics that differ between implementations; the quiz asks about the rules (free-until, next-use choice), and the worked example above can be regenerated with regalloc.linear_scan_split.
Flashcards: tags linear-scan, second-chance, lifetime-holes, ssa-linear-scan.
Lab: E3 allocateLinearScan (SPEC R7), E3★ allocateLinearScanHoles (R8).

References¶

See the chapter references.

Lesson 22.5 — Linear scan: Poletto–Sarkar, second-chance binpacking, interval splitting, SSA¶

1. Problem and motivation¶

Poletto–Sarkar linear scan¶

Second-chance binpacking¶

Interval splitting with lifetime holes (Wimmer–Mössenböck)¶

SSA-based linear scan (Wimmer–Franz)¶

2. Definitions and algorithms¶

Poletto–Sarkar linear scan¶

Second-chance binpacking¶

Interval splitting with lifetime holes (Wimmer–Mössenböck)¶

SSA-based linear scan (Wimmer–Franz)¶

3. Worked example¶

Poletto–Sarkar linear scan¶

Second-chance binpacking¶

Interval splitting with lifetime holes (Wimmer–Mössenböck)¶

SSA-based linear scan (Wimmer–Franz)¶

4. Invariants and correctness¶

Poletto–Sarkar linear scan¶

Second-chance binpacking¶

Interval splitting with lifetime holes (Wimmer–Mössenböck)¶

SSA-based linear scan (Wimmer–Franz)¶

5. Complexity¶

6. Variants and refinements¶

Poletto–Sarkar linear scan¶

Second-chance binpacking¶

Interval splitting with lifetime holes (Wimmer–Mössenböck)¶

SSA-based linear scan (Wimmer–Franz)¶

7. In real compilers¶

Poletto–Sarkar linear scan¶

Second-chance binpacking¶

Interval splitting with lifetime holes (Wimmer–Mössenböck)¶

SSA-based linear scan (Wimmer–Franz)¶

8. Comparison¶

9. Assessment¶

References¶