LINEAR SCAN REGISTER ALLOCATION one sweep over live intervals; spill the farthest end
Graph-colouring register allocation is powerful but slow. Linear scan approximates a variable’s life by a single interval [first-use, last-use] and sweeps left to right: at each interval start, free the registers of intervals that have ended; assign a free register; if all are busy, spill the active interval that ends farthest away. One pass, near-linear — which is why JITs use it.
THE TECHNIQUE expire, assign, or spill-farthest
Four overlapping live intervals, k registers. The maximum overlap is the registers needed for zero spills; drop k below it and the scan spills the interval reaching farthest. Slide k: live demo
HISTORY & CREDIT Poletto & Sarkar, TOPLAS 1999
“Linear scan beats graph colouring.” — not on quality. Graph colouring (Chaitin, 1981) generally produces better allocations; linear scan trades some quality for speed and simplicity, which is the right call in a JIT that compiles at run time, not an AOT compiler with time to spare. cited
1981–82 · Gregory Chaitin et al. — register allocation as graph colouring (the quality baseline linear scan is measured against). 1999 · Massimiliano Poletto & Vivek Sarkar — “Linear Scan Register Allocation” (TOPLAS 21(5)): live intervals, one sweep, spill the farthest-ending active interval. 2002 / 2010 · Traub / Wimmer & Franz — second-chance and SSA-based linear scan, the variants in HotSpot and LLVM-era JITs.
The approximation is the interval: a variable dead in the middle of its span still holds its register (a “lifetime hole”), which second-chance / SSA variants recover. Speed for a little waste. Poletto & Sarkar, 1999
RECOMMEND FOR I-13 max overlap = registers needed
The zero-spill register count — the maximum number of intervals live at once — runs on the canonical compiler:
$ i13 run scan.i13 # sweep time, count intervals live at each point, take the max
minregs = 3 -- max overlap of the four intervals = 3 registers for no spill
-- give the scan k<3 and it must spill the farthest-ending interval
Recommend: linear scan is LIT at its heart — the canonical compiler computes the maximum overlap = 3 (the registers needed for a spill-free allocation) by a sweep over interval arrays (native I-13). It is the register allocator to write first for an I-13 back-end: live intervals are two integer arrays, the scan is one bounded loop, and the spill choice (farthest end) is a max. Graph colouring is the quality upgrade when compile time is free; on a bounded VM linear scan is the pragmatic fit. Consumes the ordering from Sethi-Ullman (159) and scheduling (160).