Lesson 22.8 — LLVM's greedy allocator: priority, eviction, splitting, rewriting¶

Techniques: priority queue, eviction and cascades (RegAllocBasic and RegAllocGreedy); live-range splitting (region, block, local, instruction); virtual register rewriting and post-RA copy propagation · Lab: none (the lab's allocators are simpler relatives); real llc experiments · Prerequisites: Lessons 22.1–22.5, Ch 21 (MIR, llc -stop-after) · Time: 4–5 hours

LLVM's default optimizing allocator since LLVM 3.0 is greedy (RAGreedy, llvm/lib/CodeGen/RegAllocGreedy.cpp) [Ole11, LLVM-Greedy]. It is neither graph colouring nor linear scan. It keeps, for every physical register, the set of live intervals already assigned to it (LiveRegMatrix), and assigns virtual registers one at a time from a priority queue, largest first. When no register is free it may evict an already assigned interval with a lower spill weight; when that fails it splits the live range into pieces that fit, and only as a last resort spills. Evicted and split ranges go back into the queue, so earlier decisions are revisited: a backtracking allocator. Mozilla's IonMonkey copied the design, and Cranelift's regalloc2 descends from IonMonkey's version [RA2-Design]. This lesson follows a virtual register through the machinery, from the queue to the rewritten machine code.

1. Problem and motivation¶

Input: MIR after PHI elimination, two-address lowering and coalescing (Lesson 22.4); a LiveInterval for every virtual register; the target's register classes, allocation orders and pre-coloured constraints. Output: a physical register for every virtual register (possibly a split product), spill code, and finally MIR without virtual registers.

Priority queue, eviction and cascades¶

Linear scan allocates in a fixed order and spills whatever does not fit. LLVM's linear scan (until 2.9) needed backtracking to recover from bad early choices. Olesen's basic allocator (RegAllocBasic) replaced the order by a priority queue ordered by spill weight and, when a register is blocked, spills the interfering ranges if they are all cheaper; greedy refined the priority (large ranges first, so small ones fill the gaps), replaced "spill the interference" by "evict the interference back into the queue", and added cascade numbers so that evictions cannot loop [Ole11].

Live-range splitting¶

A value that is used heavily in a loop and once after it should be in a register in the loop and in memory, or in another register, outside it. Chaitin's allocators spill it everywhere; Chow–Hennessy split live ranges at colouring time [CH90]. Greedy splits in stages: around a region of blocks where a register is free (using SpillPlacement's Hopfield network to choose the region), then per block, then inside a block (local splitting around a gap, and instruction splitting per use) [Ole11, LLVM-SplitKit].

Virtual register rewriting and post-RA copy propagation¶

The allocator only records decisions in VirtRegMap (virtual → physical register, or stack slot). VirtRegRewriter then replaces every virtual register operand by its physical register, deletes copies that became identities, and adds live-in lists. Machine copy propagation (MachineCopyPropagation) then forwards copies and removes redundant ones that allocation left behind [LLVM-VirtRegMap, LLVM-MCP].

2. Definitions and algorithms¶

Priority queue, eviction and cascades¶

Definition 22.8.1 (Spill weight, stage, cascade)

The spill weight $w(v)$ of a live interval is its use/def frequency normalized by its size (Lesson 22.9, Definition 22.9.1); an unspillable interval has weight $\infty$. Each interval has a stage in $\mathrm{RS\_New} < \mathrm{RS\_Assign} < \mathrm{RS\_Split} < \mathrm{RS\_Split2} < \mathrm{RS\_Spill} < \mathrm{RS\_Done}$ (LiveRangeStage in RegAllocEvictionAdvisor.h) that only increases, and a cascade number $\kappa(v) \in \mathbb{N}$, 0 for "never involved in an eviction". Interval $A$ may evict $B$ from register $r$ only if $\kappa(B) < \kappa(A)$ (or $B$ has no cascade), $B$ is not a spill product ($\mathrm{RS\_Done}$), and $w(A) > w(B)$ (or $A$ wants $r$ as its hint and $B$ can still be split).

Algorithm 22.8.2 (The allocation loop: RegAllocBase::allocatePhysRegs with RABasic::selectOrSplit)

Input: live intervals; LiveRegMatrix (per register unit, the assigned intervals).
Output: an assignment of every non-spilled interval (in VirtRegMap).
Precondition: intervals are computed; each has a spill weight.
Postcondition: no two intervals assigned to overlapping registers overlap.
Invariant: every interval in the matrix is assigned and does not overlap another interval of any of its register's units.

function AllocatePhysRegs():
    enqueue every virtual register interval
    while the queue is not empty:
        v ← dequeue the highest-priority interval       # basic: largest spill weight
        newRegs ← []
        r ← SelectOrSplit(v, newRegs)                   # may evict/split/spill, filling newRegs
        if r ≠ none: assign v to r in the matrix
        enqueue every interval of newRegs

function SelectOrSplit_Basic(v, newRegs):
    candidates ← []
    for r in v's allocation order:
        case Matrix.checkInterference(v, r) of
            free:          return r
            virtual regs:  candidates.append(r)          # only virtual intervals in the way
            otherwise:     continue                       # regmask or physical interference
    for r in candidates:
        if every interval interfering with v on r has weight < w(v):
            spill all of them (their spill products go to newRegs); return r
    spill v (products to newRegs); return none

Algorithm 22.8.3 (Greedy's selectOrSplitImpl, LLVM 23.1.2)

Input: interval $v$ dequeued from the priority queue.
Output: a register, or none (then $v$ was split, spilled, or requeued).
Precondition: $v$ unassigned; the priority is DefaultPriorityAdvisor::getPriority: local ranges (in one block) by instruction order, global and split ranges by size, with bits for "has a hint" and "global"; ranges in stage RS_Split come after all others.
Postcondition: the matrix invariant of Algorithm 22.8.2; stages only increase.
Invariant: every evicted interval carries the cascade of its evictor (evictInterference), which is at least its own previous cascade.

function SelectOrSplit_Greedy(v, newRegs):
    if r ← TryAssign(v): return r                      # a free register, preferring hints
    if stage(v) ≠ RS_Split:
        if r ← TryEvict(v):                            # cheapest register whose interference
            return r                                   # may be evicted (Definition 22.8.1)
    if stage(v) < RS_Split:                            # first failure: wait for the others
        stage(v) ← RS_Split; newRegs.append(v); return none
    if stage(v) < RS_Spill and v is not empty:
        if TrySplit(v, newRegs) made progress: return that register or none
    if stage(v) ≥ RS_Done or v is unspillable:
        return TryLastChanceRecoloring(v)              # recolour interference recursively
    spill v (inline spiller); mark products RS_Done; return none

function TryEvict(v):
    best ← none; bestCost ← (∞ broken hints, ∞ weight)
    for r in v's allocation order:
        cost ← (number of broken hints, max weight) of the intervals interfering on r
        if every interfering interval may be evicted by v (Definition 22.8.1, and fewer than
           EvictInterferenceCutoff = 10 of them) and cost < bestCost:
            best ← r; bestCost ← cost
    if best: EvictInterference(v, best)                 # unassign them, set their cascade to
    return best                                        # κ(v) (a new one if v had none), requeue

function TrySplit(v, newRegs):
    if v lives in one block: return TryLocalSplit(v) or TryInstructionSplit(v)
    if stage(v) < RS_Split2 and (r ← TryRegionSplit(v)) made progress: return r
    return TryBlockSplit(v)

Theorem 22.8.4 (Greedy terminates)

The loop of Algorithm 22.8.2 with Algorithm 22.8.3 terminates.

Proof sketch (full argument: the comments of LiveRangeStage and evictInterference, [LLVM-Greedy]; [Ole11])

Stages only increase, and there are six. An interval is requeued without progress only once per stage transition (RS_Assign → RS_Split). Splitting creates new intervals, but each split product is strictly smaller than its parent or enters a later stage (RS_Split2, RS_Spill), and the splitters refuse to split when no product would shrink ("guaranteed to make progress" for RS_Split2), so only finitely many intervals are ever created. Spill products are RS_Done and never evicted or split. The remaining source of non-termination is eviction cycles: $A$ evicts $B$, $B$ evicts $A$, … An eviction sets the evictee's cascade to the evictor's cascade $c$, and an interval may evict only intervals with a strictly smaller cascade (Definition 22.8.1). New cascade numbers are drawn from a counter that only increases, and an interval's cascade never decreases (the assertion in evictInterference), so along any chain of evictions of the same intervals the cascade numbers must strictly increase, which bounds the chain by the number of cascades ever assigned, itself bounded by the number of dequeues of intervals without a cascade. Urgent evictions that break cascades are allowed only for intervals that cannot be spilled, a finite exception.

Live-range splitting¶

Definition 22.8.5 (Split, edge bundle, split kinds)

Splitting interval $v$ replaces it by intervals $v_1, \dots, v_m$ (new virtual registers) whose segments partition $v$'s segments, with a COPY (marked lr-split in MIR) at every point where the value passes from one to another. An edge bundle groups the CFG edges that must agree on where a value lives (all edges leaving a block, all edges entering a block, transitively merged: EdgeBundles). The kinds are: region split (a set of blocks in one register, the rest elsewhere); block split (isolate each block's uses); local split (inside one block, around the largest gap between uses); instruction split (a tiny interval per use, the last resort before spilling).

Algorithm 22.8.6 (Region splitting, after RAGreedy::tryRegionSplit and SpillPlacement)

Input: a global interval $v$ that could not be assigned or evict; per physical register $r$ its interference with $v$ per block (InterferenceCache).
Output: a candidate register $r$ and a set of edge bundles where $v$ lives in $r$; the split of $v$ accordingly.
Precondition: block frequencies (MachineBlockFrequencyInfo).
Postcondition: the chosen region's estimated cost (spill code at region borders plus extra copies) is lower than splitting per block and lower than spilling.
Invariant: SpillPlacement's energy function (§4) never increases during its updates.

function TryRegionSplit(v):
    best ← cost of spilling v around every use (calcBlockSplitCost)
    for r in v's allocation order:
        constraints ← for each block with a use of v: prefer "in a register" at its entry/exit
                      bundles if r is free there, "in memory" if r is taken, with a bias
                      equal to the block frequency
        SpillPlacement.prepare(); add constraints; grow the region over blocks where v is
            live-through and r is free (growRegion)
        SpillPlacement.finish()                      # Hopfield network settles: each bundle
                                                     # decides register (1) or memory (0)
        cost ← static cost of the borders + calcGlobalSplitCost (copies/spills at borders)
        if cost < best: best ← cost; bestCand ← (r, live bundles)
    if bestCand: split v: one new interval for the blocks of the region (hinted to r),
                 new intervals for the rest (they will be split further or spilled)

Proposition 22.8.7 (Splitting preserves the program)

Replacing $v$ by $v_1, \dots, v_m$ with copies at the transition points, and resolving the locations on edges where adjacent pieces differ, yields a program whose uses read the same values as before.

Proof

This is Theorem 22.5.9 with LLVM's pieces: every use of $v$ is renamed to the piece covering it, every transition inside a block is a COPY from the old piece to the new one at the split point, and SplitKit inserts copies on edges (in the predecessor or successor, or on a split critical edge) where the pieces live-out and live-in differ. Each piece is a new virtual register with one value per definition, so the renaming is the SSA-updater construction of Lesson 16.4 applied to the copies.

Virtual register rewriting and post-RA copy propagation¶

Algorithm 22.8.8 (VirtRegRewriter::rewrite and handleIdentityCopy)

Input: MIR with virtual registers; VirtRegMap (virtual → physical, or stack slot handled earlier by the spiller).
Output: MIR without virtual registers.
Precondition: every remaining virtual register has a physical register.
Postcondition: operands name physical registers (sub-registers composed); identity copies are gone or turned into KILLs; block live-in lists are set.
Invariant: instructions already visited mention no virtual register.

function Rewrite(MF):
    add live-ins to each block from the intervals (addMBBLiveIns)
    for each instruction MI:
        for each virtual register operand MO:
            p ← VirtRegMap.phys(MO.reg); if MO has a sub-register index s: p ← subreg(p, s)
            replace MO by p; keep kill/dead/undef flags
        if MI is a COPY with equal source and destination (HandleIdentityCopy):
            if it carries extra liveness (undef source, implicit operands): make it a KILL
            else: erase MI

Proposition 22.8.9 (Identity copies are no-ops)

Deleting a COPY whose source and destination are the same physical register does not change the program's behaviour, except for liveness facts, which KILL preserves where needed.

Proof

A copy $r \gets r$ writes to $r$ the value $r$ already holds, and has no other effect on machine state. The only information lost is the implicit statement that the (super-)register is defined here, which matters to later passes' liveness when the copy was partial (an undefined source or a sub-register copy with implicit super-register operands); the rewriter keeps exactly those as KILL pseudo-instructions, which produce no code.

3. Worked example¶

Priority queue, eviction and cascades¶

A three-interval example with one register ($K = 1$) shows the mechanics (weights in parentheses; all three overlap):

step	dequeued	action	register	queue after	cascades
1	A (5), size largest	r free: assign	r: A	B, C	—
2	B (8)	r taken by A; A may be evicted ($\kappa(A) = 0 <$ new cascade 1, $w(A) = 5 < 8$): evict A	r: B	C, A	κ(B) = 1, κ(A) = 1
3	C (6)	r taken by B, $w(B) = 8 > 6$: no eviction; first failure: stage → RS_Split, requeue	r: B	A, C	—
4	A (5)	r taken by B; $\kappa(B) = \kappa(A) = 1$: may not evict (same cascade); stage → RS_Split, requeue	r: B	C, A	—
5	C (6, RS_Split)	cannot split usefully (one register, full overlap): spill C	r: B	A	—
6	A (5, RS_Split)	spill A	r: B	—	—

Without cascades step 4 could evict B (it could, if weights allowed), B could evict A again, and so on. With them, A — once evicted by B — cannot push B out. The same run on the running example is not traceable in release builds of LLVM (-debug-only=regalloc needs an assertions build); §7 shows the aggregate effect of the eviction limit instead.

Live-range splitting¶

In the high-pressure loop of Lesson 22.3 (press.c, fourteen accumulators and a call s0 = g(s0) executed when x == 42), every accumulator is live across the call, and on x86-64 there are only six callee-saved registers. Spilling the accumulators everywhere would put loads and stores in the whole loop. Region splitting instead keeps them in registers in the loop's blocks and gives each a new interval inside the call block, whose piece is then spilled: stores before the call and reloads after it, only on the rare path (§7 shows the MIR).

Virtual register rewriting and post-RA copy propagation¶

In f(a, b) = (g(a) + b) * a (Lesson 22.1 §7), greedy assigned %7 to $rax because of the hints from COPY killed $rax and $rax = COPY %7. The rewriter turned both copies into $rax = COPY $rax and deleted them (Proposition 22.8.9): the rewritten MIR in Lesson 22.1 has no copy at 112B and 240B.

Try it

There is no drill for greedy's heuristics (they depend on LLVM's tuned weights and thresholds); run llc -O2 -stop-after=greedy,1 -o - on your own code and find the lr-split copies, or change -regalloc-eviction-max-interference-cutoff and count spills.

4. Invariants and correctness¶

Priority queue, eviction and cascades¶

The matrix invariant (no two intervals assigned to overlapping registers overlap) holds because assign is only called after checkInterference returns "free" or after the interference was evicted; evicted intervals are unassigned before the new one is assigned. Termination is Theorem 22.8.4.

Priority is not spill weight

Greedy dequeues by size (and locality), not by spill weight: a long, rarely used range is allocated early and may then be evicted by a heavier one. Weight decides evictions, size decides order. Reading enqueue without DefaultPriorityAdvisor::getPriority gives the wrong picture.

Live-range splitting¶

Correctness is Proposition 22.8.7. For the quality of the split, SpillPlacement minimizes (locally) the energy

\[ E = -\sum_{n} V_n \Bigl( B_n + \sum_{\{n, m\} \text{ linked by block } b} V_m \, F_b \Bigr), \qquad V_n \in \{-1, +1\}, \]

where $V_n = +1$ means "in a register" at bundle $n$, $B_n$ is the frequency-weighted bias from the constraints of blocks at that bundle, and $F_b$ the frequency of a transparent block linking two bundles (the comment at the top of SpillPlacement.cpp) [LLVM-SpillPlacement]. Each node update sets $V_n$ to the sign of its local field, which never increases $E$ (a Hopfield network is a Lyapunov system), so the iteration converges to a local minimum; greedy uses it as a heuristic for where splitting is cheap, not as an exact optimum.

Virtual register rewriting and post-RA copy propagation¶

The rewriter's only deletion is justified by Proposition 22.8.9. Machine copy propagation's forwarding is correct when the copy's source is not clobbered between the copy and the use, the copy is the only definition reaching the use, and register-class constraints allow the replacement (its file header) [LLVM-MCP].

5. Complexity¶

$n$ intervals, $s$ = total segments, $K$ = registers in a class, $R$ = requeues per interval (small in practice), $B$ = edge bundles.

Algorithm	Time (worst)	Time (typical)	Space	Justification
Interference query (`LiveIntervalUnion`)	$O(\log s + k)$ per query and unit, $k$ = overlaps reported	fast	$O(s)$ per unit	segment interval trees
Basic / greedy main loop	$O(n R K (\log s + \mathrm{cutoff}))$ plus splitting	near-linear	$O(n + s)$	each dequeue scans the allocation order; eviction checks at most `EvictInterferenceCutoff` = 10 interferences per unit
Region split	$O(K \cdot (B + \text{blocks}) \cdot \text{iterations})$ per candidate interval	dominant compile-time cost of greedy	$O(B)$	one `SpillPlacement` run per candidate register
Last-chance recoloring	exponential in `lcr-max-depth`	rare	recursion depth	bounded by `-lcr-max-depth` and `-lcr-max-interf`
Rewriter, MCP	$O(N)$	linear	$O(\text{registers})$	one pass each

Pathological family. Huge functions with long live ranges spanning thousands of blocks make region splitting dominate compile time; greedy therefore has thresholds (-huge-size-for-split, the GlobalPriority fallback for giant ranges in getPriority) that switch to cheaper decisions. Olesen reports greedy's code as 1–2% smaller and up to 10% faster than LLVM's linear scan at comparable compile time [Ole11].

Priority queue, eviction and cascades¶

ML-guided eviction and priority (-regalloc-enable-advisor=release|development, RegAllocEvictionAdvisor, RegAllocPriorityAdvisor): a learned model replaces shouldEvict and the priority function (MLGO). Trade-off: better code on trained workloads, models to maintain.
Callee-saved register cost. The first use of an unused CSR costs its save/restore (-regalloc-csr-first-time-cost, tryAssignCSRFirstTime). Trade-off: fewer prologue saves versus more splitting.
Last-chance recoloring for unspillable intervals (tryLastChanceRecoloring). Trade-off: exponential search, bounded by depth.

Live-range splitting¶

Split spill modes (-split-spill-mode=default|size|speed, SplitEditor::ComplementSpillMode) decide where the complement of a split is spilled. Trade-off: code size versus speed.
Splitting around hints (trySplitAroundHintReg) creates copies to satisfy a register hint in hot code. Trade-off: extra copies in cold code.

Virtual register rewriting and post-RA copy propagation¶

Stack slot colouring (StackSlotColoring) shares spill slots between non-overlapping spilled intervals. Trade-off: smaller frames; one more pass.
Post-RA machine LICM and sinking move reloads out of loops (seen in Lesson 22.2's fast-allocator listing) and sink copies. Trade-off: must respect physical register liveness.

7. In real compilers¶

The LLVM register-allocation pipeline for x86-64 at -O2, as llc 23.1.2 runs it: PHI elimination and the two-address pass create copies; LiveIntervals computes intervals; the coalescer merges; the machine scheduler reorders; then greedy allocates, twice on x86 (once for AMX tile registers, once for the rest), the rewriter rewrites, and stack slot colouring and copy propagation clean up. PEI inserts callee-saved saves (Lesson 21.9).

Priority queue, eviction and cascades¶

RegAllocBase::allocatePhysRegs (llvm/lib/CodeGen/RegAllocBase.cpp) is Algorithm 22.8.2's loop; RABasic::selectOrSplit (RegAllocBasic.cpp) and RAGreedy::selectOrSplitImpl (RegAllocGreedy.cpp) are the two policies; DefaultEvictionAdvisor::canEvictInterferenceBasedOnCost and shouldEvict (RegAllocEvictionAdvisor.cpp) implement Definition 22.8.1 [LLVM-Greedy, LLVM-Basic]. IonMonkey's backtracking allocator and regalloc2 use the same "evict by weight, requeue" loop [RA2-Design].

The pipeline, and what eviction buys on a high-pressure loop

Reproduce (llc 23.1.2; press-x86_64-linux-gnu.ll from Lesson 22.7 §7):

llc -O2 -debug-pass=Structure press-x86_64-linux-gnu.ll -o /dev/null 2>&1 | grep -E \
  '^\s+(Live Variable Analysis|Eliminate PHI nodes|Two-Address|Live Interval Analysis|Register Coalescer|Machine Instruction Scheduler|Live Stack Slot|Virtual Register Map|Live Register Matrix|Spill Code Placement|Greedy Register Allocator|Tile Register Configure|Virtual Register Rewriter|Stack Slot Coloring|Machine Copy Propagation Pass|Prologue/Epilogue Insertion)'
for o in "" "-regalloc-eviction-max-interference-cutoff=1" "-regalloc=basic"; do
  llc -O2 $o press-x86_64-linux-gnu.ll -o t.s
  printf '%-48s spills %2d reloads %2d\n' "[${o:-greedy, default}]" $(grep -c ' Spill$' t.s) $(grep -c ' Reload$' t.s)
done

Output (complete):

      Live Variable Analysis
      Eliminate PHI nodes for register allocation
      Two-Address instruction pass
      Live Interval Analysis
      Register Coalescer
      Machine Instruction Scheduler
      Live Stack Slot Analysis
      Virtual Register Map
      Live Register Matrix
      Spill Code Placement Analysis
      Greedy Register Allocator
      Tile Register Configure
      Greedy Register Allocator
      Virtual Register Rewriter
      Stack Slot Coloring
      Machine Copy Propagation Pass
      Prologue/Epilogue Insertion & Frame Finalization
      Machine Copy Propagation Pass
[greedy, default]                                spills 12 reloads 11
[-regalloc-eviction-max-interference-cutoff=1]   spills 14 reloads 13
[-regalloc=basic]                                spills 32 reloads 20

What to notice: the pipeline is §7's description, with "Greedy Register Allocator" twice (the first instance allocates only AMX tile registers, so -stop-after=greedy stops too early on x86; use greedy,1 for the second). Allowing eviction only when a single interval is in the way (cutoff 1 instead of 10) costs two more spills and two more reloads; RegAllocBasic, which spills interference instead of evicting and never splits, needs almost three times as many spills (Algorithm 22.8.2 versus 22.8.3).

Live-range splitting¶

SplitAnalysis and SplitEditor (llvm/lib/CodeGen/SplitKit.cpp) perform the splits; SpillPlacement (llvm/lib/CodeGen/SpillPlacement.cpp) runs the Hopfield network over EdgeBundles; RAGreedy::tryRegionSplit, tryBlockSplit, tryLocalSplit and tryInstructionSplit choose among them [LLVM-SplitKit, LLVM-SpillPlacement]. GCC's IRA obtains a similar effect by allocating regions (loops) separately and moving values at region borders (Lesson 22.3 §7) [GCC-IRA].

Greedy splits live ranges around a rarely executed call

Reproduce (llc 23.1.2; the same press-x86_64-linux-gnu.ll):

llc -O2 -stop-before=greedy,1 press-x86_64-linux-gnu.ll -o - | sed -n '/^  bb.6/,/^  bb.7/p'
llc -O2 -stop-after=greedy,1 press-x86_64-linux-gnu.ll -o - | sed -n '/^  bb.6/,/^  bb.7/p'

Output (complete):

  bb.6 (%ir-block.62):
    successors: %bb.7(0x80000000)

    ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
    $rdi = COPY %106
    CALL64pcrel32 target-flags(x86-plt) @g, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, implicit-def $rsp, implicit-def $ssp, implicit-def $rax
    ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
    %106:gr64_with_sub_8bit = COPY killed $rax

  bb.7 (%ir-block.64):
  bb.6 (%ir-block.62):
    successors: %bb.7(0x80000000)

    ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
    MOV64mr %stack.1, 1, $noreg, 0, $noreg, %110 :: (store (s64) into %stack.1)
    $rdi = COPY %106
    MOV64mr %stack.0, 1, $noreg, 0, $noreg, %108 :: (store (s64) into %stack.0)
    MOV64mr %stack.2, 1, $noreg, 0, $noreg, %112 :: (store (s64) into %stack.2)
    MOV64mr %stack.3, 1, $noreg, 0, $noreg, %114 :: (store (s64) into %stack.3)
    MOV64mr %stack.5, 1, $noreg, 0, $noreg, %120 :: (store (s64) into %stack.5)
    %115:gr64 = lr-split COPY %116
    MOV64mr %stack.4, 1, $noreg, 0, $noreg, %118 :: (store (s64) into %stack.4)
    CALL64pcrel32 target-flags(x86-plt) @g, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, implicit-def $rsp, implicit-def $ssp, implicit-def $rax
    %118:gr64 = MOV64rm %stack.4, 1, $noreg, 0, $noreg :: (load (s64) from %stack.4)
    %116:gr64 = lr-split COPY %115
    %120:gr64 = MOV64rm %stack.5, 1, $noreg, 0, $noreg :: (load (s64) from %stack.5)
    %114:gr64 = MOV64rm %stack.3, 1, $noreg, 0, $noreg :: (load (s64) from %stack.3)
    %112:gr64 = MOV64rm %stack.2, 1, $noreg, 0, $noreg :: (load (s64) from %stack.2)
    %110:gr64 = MOV64rm %stack.1, 1, $noreg, 0, $noreg :: (load (s64) from %stack.1)
    %108:gr64 = MOV64rm %stack.0, 1, $noreg, 0, $noreg :: (load (s64) from %stack.0)
    ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
    %106:gr64_with_sub_8bit = COPY $rax

  bb.7 (%ir-block.64):

What to notice: bb.6 is the call s0 = g(s0) inside the loop (the call mask csr_64 preserves only rbx, rbp, r12–r15). Before allocation the accumulators simply pass through. After greedy, six of them (%108 … %120) have been split so that their piece in bb.6 is spilled: stored before the call and reloaded after it, while their pieces in the other loop blocks stay in caller-saved registers. %115 = lr-split COPY %116 and back is a split that moves one value into a different register across the call instead of spilling it. The rest of the loop has no memory traffic for these values. (bb.6 is not the loop's common path: the call runs only when x == 42.)

Virtual register rewriting and post-RA copy propagation¶

VirtRegRewriter is in llvm/lib/CodeGen/VirtRegMap.cpp (VirtRegRewriter::rewrite, handleIdentityCopy) and MachineCopyPropagation in llvm/lib/CodeGen/MachineCopyPropagation.cpp [LLVM-VirtRegMap, LLVM-MCP]. GCC's equivalent of the rewriter is LRA's final substitution (gcc/lra.cc) followed by cprop_hardreg (gcc/regcprop.cc) [GCC-LRA]. Lesson 22.1's MIR box shows the rewriter deleting identity copies; the box below shows copy propagation.

Machine copy propagation after allocation

Reproduce (clang 23.1.2, llc 23.1.2):

cat > gcd.c <<'EOF'
long gcd(long a, long b) {
  while (b != 0) { long t = a % b; a = b; b = t; }
  return a;
}
EOF
clang-23 --target=x86_64-linux-gnu -O1 -S -emit-llvm gcd.c -o gcd.ll
for s in before after; do llc -O2 -stop-$s=machine-cp gcd.ll -o - | sed -n '/^body:/,/^\.\.\./p' > gcd-$s.mir; done
diff gcd-before.mir gcd-after.mir
sed -n '2,9p' gcd-after.mir

Output (complete):

8c8
<     TEST64rr renamable $rdx, renamable $rdx, implicit-def $eflags
---
>     TEST64rr $rsi, $rsi, implicit-def $eflags
  bb.0 (%ir-block.2):
    successors: %bb.7(0x30000000), %bb.1(0x50000000)
    liveins: $rdi, $rsi

    renamable $rdx = COPY $rsi
    renamable $rax = COPY $rdi
    TEST64rr $rsi, $rsi, implicit-def $eflags
    JCC_1 %bb.1, 5, implicit $eflags

What to notice: after allocation, b lives in $rdx (it is later needed there by the division sequence) and was copied from the argument register $rsi. The test b != 0 read $rdx; copy propagation forwards the copy's source, so the test reads $rsi directly, which removes a dependence on the copy (on out-of-order cores, a shorter critical path). This is the first transformation of the pass's header comment: "forwards the source of COPYs to the users of their destinations when doing so is legal".

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Priority queue, eviction and cascades (basic, greedy)	revisits decisions by eviction; weights decide	near-linear · LLVM's default at `-O1`+	basic: 32 spills on `press`; greedy: 12	large (advisors, stages, cascades)	LLVM (all targets), IonMonkey, regalloc2
Live-range splitting (region/block/local/instruction)	spill code only where needed	dominant part of greedy's time	the main reason greedy beats basic and PBQP on x86	very large (`SplitKit`, `SpillPlacement`)	LLVM greedy, GCC IRA regions, V8
Rewriting and post-RA copy propagation	exact translation; removes identity/redundant copies	linear	clean output; fewer copies	moderate	every allocator in LLVM; GCC `cprop_hardreg`

Measured with llc 23.1.2 on press.c (Lesson 22.3), x86-64: fast 39 spills / 35 reloads, basic 32 / 20, greedy 12 / 11, PBQP 21 / 14 (the full table for x86-64 and AArch64 is in the README).

Choose greedy (LLVM's default) for optimized code: its splitting puts spill code where it is cheap. Choose basic only as a reference point or when debugging greedy. Keep the rewriter and copy propagation regardless of the allocator: every allocator in LLVM ends with them.

9. Assessment¶

Quiz (./course quiz 22): greedy-stage-order, greedy-cascade, find-evict-advisor, split-kinds, find-spill-placement, rewriter-identity, mcp-forward (tags greedy-eviction, splitting, rewriter).
Drill: none; greedy's decisions depend on LLVM's weights, thresholds and target costs, so a hand-traceable drill would teach a different allocator. The quiz's source-reading questions and the llc experiments above replace it.
Flashcards: tags greedy-eviction, splitting, rewriter.

References¶

See the chapter references.

Algorithm	Time (worst)	Time (typical)	Space	Justification
Interference query (`LiveIntervalUnion`)	\(O(\log s + k)\) per query and unit, \(k\) = overlaps reported	fast	\(O(s)\) per unit	segment interval trees
Basic / greedy main loop	\(O(n R K (\log s + \mathrm{cutoff}))\) plus splitting	near-linear	\(O(n + s)\)	each dequeue scans the allocation order; eviction checks at most `EvictInterferenceCutoff` = 10 interferences per unit
Region split	\(O(K \cdot (B + \text{blocks}) \cdot \text{iterations})\) per candidate interval	dominant compile-time cost of greedy	\(O(B)\)	one `SpillPlacement` run per candidate register
Last-chance recoloring	exponential in `lcr-max-depth`	rare	recursion depth	bounded by `-lcr-max-depth` and `-lcr-max-interf`
Rewriter, MCP	\(O(N)\)	linear	\(O(\text{registers})\)	one pass each

Lesson 22.8 — LLVM's greedy allocator: priority, eviction, splitting, rewriting¶

1. Problem and motivation¶

Priority queue, eviction and cascades¶

Live-range splitting¶

Virtual register rewriting and post-RA copy propagation¶

2. Definitions and algorithms¶

Priority queue, eviction and cascades¶

Live-range splitting¶

Virtual register rewriting and post-RA copy propagation¶

3. Worked example¶

Priority queue, eviction and cascades¶

Live-range splitting¶

Virtual register rewriting and post-RA copy propagation¶

4. Invariants and correctness¶

Priority queue, eviction and cascades¶

Live-range splitting¶

Virtual register rewriting and post-RA copy propagation¶

5. Complexity¶

6. Variants and refinements¶

Priority queue, eviction and cascades¶

Live-range splitting¶

Virtual register rewriting and post-RA copy propagation¶

7. In real compilers¶

Priority queue, eviction and cascades¶

Live-range splitting¶

Virtual register rewriting and post-RA copy propagation¶

8. Comparison¶

9. Assessment¶

References¶