Lesson 22.2 — Local allocation: Belady's MIN and LLVM's fast allocator¶

Techniques: Belady's MIN (furthest next use); local allocation in LLVM (RegAllocFast) · Lab: labs/ch22-regalloc E0 (beladyMisses) and E1 (allocateLocal) · Prerequisites: Lesson 22.1 · Time: 3–4 hours

A local allocator looks at one basic block at a time. Inside a block there is no control flow, so the question "which value should leave the registers when a new one arrives?" becomes a question about a sequence of references, the same question an operating system asks about memory pages. Belady answered it in 1966: evict the value whose next use is furthest away [Bel66]. For a block of loads and uses this is optimal. Local allocation is what a compiler does when it must be fast (LLVM at -O0), what global allocators fall back to inside a block, and the basis of the spilling heuristics of SSA-based allocators (Lesson 22.6).

1. Problem and motivation¶

Belady's MIN¶

Input: a straight-line sequence of instructions (one block), the values each one reads and writes, and \(K\) registers. Output: at each instruction, which values are in registers, and which values are loaded (reloaded) and evicted. Goal: as few loads as possible. When the only cost is loading a value that is not in a register, this is the paging problem with a cache of \(K\) pages, and the offline optimum is Belady's MIN rule: on a miss with a full cache, evict the value whose next reference is furthest in the future [Bel66]. Belady described MIN as the theoretical optimum of his replacement study; the first published optimality proofs came later [MGST70], and a textbook exchange argument is in Kleinberg and Tardos [KT06, §4.3].

The history of the rule in compilers is older than the paging paper: Horwitz, Karp, Miller and Winograd studied optimal "index register allocation" for straight-line code in 1966 [HKMW66], and every modern textbook allocates a block bottom-up with the furthest-next-use rule [EaC3, Ch. 13]. The subtlety is that registers are not pages: evicting a value that was computed in the block (a dirty value) costs a store as well as a later load, and with that asymmetry MIN is no longer optimal. The problem even becomes NP-hard [FCL00].

Local allocation in LLVM (RegAllocFast)¶

At -O0, LLVM runs RegAllocFast (llvm/lib/CodeGen/RegAllocFast.cpp) [LLVM-RAFast]. It allocates one block at a time, walking it backwards, keeps every value that lives across a block boundary in its stack slot, and when it needs a register it picks the one that is cheapest to vacate (a free one, then one holding a value already in memory, then one holding a value it must store). It never builds live intervals, which makes it linear in the size of the function: the right trade-off for debug builds, where compile time matters and every variable should be in memory anyway so a debugger can find it.

2. Definitions and algorithms¶

Belady's MIN¶

Definition 22.2.1 (Reference string, schedule, misses)

A reference string is a sequence \(\sigma = \sigma_1 \sigma_2 \cdots \sigma_m\) of values. With \(K\) registers, a schedule is a sequence of sets \(C_0 = \emptyset, C_1, \dots, C_m\) with \(\lvert C_t \rvert \le K\) and \(\sigma_t \in C_t\) (\(C_t\) is what the registers hold after serving reference \(t\)). Reference \(t\) is a miss if \(\sigma_t \notin C_{t-1}\). The schedule is demand (lazy) if \(C_t \setminus C_{t-1} \subseteq \{\sigma_t\}\): it only loads the value that is needed now. Its cost is its number of loads, \(\sum_t \lvert C_t \setminus C_{t-1} \rvert\). For a position \(t\) and a value \(v\), \(\mathrm{next}_t(v) = \min\{\, t' > t \mid \sigma_{t'} = v \,\}\), or \(\infty\) if \(v\) is never referenced again.

Algorithm 22.2.2 (Belady's MIN / furthest next use)

Input: \(\sigma_1 \cdots \sigma_m\) and \(K \ge 1\).
Output: a demand schedule and its number of misses; the value evicted at each miss.
Precondition: none (values are arbitrary tokens).
Postcondition: the schedule has the minimum number of loads among all schedules (Theorem 22.2.6).
Invariant: after step \(t\), \(C_t\) is the register contents, \(\lvert C_t \rvert \le K\), and \(\sigma_t \in C_t\).

function MIN(σ, K):
    C ← ∅; misses ← 0
    for t ← 1 to m:
        if σ_t ∈ C: continue                              # hit
        misses ← misses + 1
        if |C| = K:
            victim ← argmax over v ∈ C of next_t(v)        # ties: smallest name
            C ← C \ {victim}
        C ← C ∪ {σ_t}
    return misses

next is precomputed right to left in \(O(m)\): nextpos[t] is the next position with the same value.

Definition 22.2.3 (Clean and dirty values)

In a block, a value is clean if a copy of it is already in memory (it was loaded, or it was defined in an earlier block and stored there) and dirty if it was computed in the block and not yet stored. Evicting a dirty value that will be used again costs a store; the cost of a schedule is (loads) \(+\) (stores).

Algorithm 22.2.4 (Local allocation by furthest next use)

Input: one block \(B\) (instructions reading operands, writing at most one result), \(\mathrm{live\text{-}out}(B)\), \(K\) registers.
Output: a register for every operand and result; the reloads, spills and end-of-block stores.
Precondition: at entry every value live into \(B\) is in memory (its stack slot).
Postcondition: every instruction finds its operands in registers; at exit every dirty value in \(\mathrm{live\text{-}out}(B)\) has been stored.
Invariant: at most \(K\) values occupy registers; each occupied register's value is either clean or recorded as dirty.

function LocalAlloc(B, K):
    regs ← {}                                   # register → (value, dirty?)
    for each instruction I = (d ← op u1, …, uk) of B, in order:
        for each operand u of I not in regs:
            r ← Pick(I, exclude = operands of I)
            emit "r ← load slot(u)"; regs[r] ← (u, clean)
        for each operand u whose next use in B is ∞ and u ∉ live-out(B):
            free u's register                     # the result may reuse it
        if I defines d:
            r ← Pick(I, exclude = operands of I still live); regs[r] ← (d, dirty)
    for each (r, (v, dirty)) in regs with dirty and v ∈ live-out(B):
        emit "store r → slot(v)"

function Pick(I, exclude):
    if some register is free: return it
    v ← the value in regs \ exclude with the furthest next use (∞ if not used again in B)
    if v is dirty and (next use of v < ∞ or v ∈ live-out(B)): emit "store reg(v) → slot(v)"
    free reg(v); return it

The lab's E1 is the whole-value variant (Location = register or slot for the entire live range): values live across a block boundary stay in memory, and a block-local value that loses the furthest-next-use contest is spilled for its whole life (SPEC R5).

Local allocation in LLVM (RegAllocFast)¶

Algorithm 22.2.5 (RegAllocFast, simplified from RegAllocFastImpl::allocateBasicBlock)

Input: a machine function with virtual registers, not in SSA (PHIs eliminated), and the physical registers reserved by calls, live-outs and constraints.
Output: every virtual register operand replaced by a physical register, with spills and reloads.
Precondition: every virtual register live across a block boundary has a stack slot (mayLiveOut/mayLiveIn decide conservatively).
Postcondition: at every block boundary each such value is in its slot.
Invariant: walking the block backwards, LiveVirtRegs maps each virtual register that is live below the current instruction to its physical register; each register unit is free, preassigned or holds one virtual register.

function AllocateBlock(MBB):
    mark MBB's physical live-outs preassigned
    for MI in MBB, from last to first:                  # allocateInstruction
        for each def of a virtual register v in MI:
            if v has a register r: free r
                if v may live out or has a slot: emit "spill r → slot(v)" after MI
            else if v is dead: give it any free register
        for each use of a virtual register v in MI:
            if v has no register: r ← AllocVirtReg(v); record v ↦ r
    for each v still in LiveVirtRegs: emit "reload slot(v) → reg(v)" at MBB's start

function AllocVirtReg(v):
    if a hint register (copy source/destination) is free: return it
    best ← the register in allocation order with the least calcSpillCost:
        0 if free; spillClean = 50 if its value already has a slot or lives out;
        spillDirty = 100 otherwise; ∞ if preassigned
    displace best's current value (it will be reloaded below) and return best

Walking backwards means a use is seen before its definition: when the allocator reaches the definition it already knows where the value must be, and the displaced value's "reload" is placed after the instruction in program order.

3. Worked example¶

Belady's MIN¶

\(K = 3\), block reference string a b c a d b a c d (positions 1–9). The table shows every step; "next use" lists \(\mathrm{next}_t\) of each register value at a miss with full registers (1-based positions, \(\infty\) = never).

step	ref	hit/miss	next use of each register value	evict	registers after
1	a	miss	—	—	{a}
2	b	miss	—	—	{a, b}
3	c	miss	—	—	{a, b, c}
4	a	hit	—	—	{a, b, c}
5	d	miss	a→7, b→6, c→8	c	{a, b, d}
6	b	hit	—	—	{a, b, d}
7	a	hit	—	—	{a, b, d}
8	c	miss	a→∞, b→∞, d→9	a	{b, c, d}
9	d	hit	—	—	{b, c, d}

Step 5: c is needed again only at position 8, later than a (7) and b (6): evict c.
Step 8: neither a nor b is used again; the tie goes to the smallest name, a.
5 loads, the minimum: an exhaustive search over all eviction choices (regalloc.min_misses_brute) also finds 5. Least-recently-used eviction needs 7 on the same string: at step 5 it evicts b (least recently used), which is needed at step 6.

Why dirtiness breaks optimality. Take \(K = 2\), registers holding c (clean) and d (dirty, computed earlier in the block), and references e c d. MIN evicts d at e (next use 3 > 2): store d, load e, then at d evict e and reload d: 1 store + 2 loads = 3. Evicting the clean c instead costs load e, then at c evict e (never used again) and reload c: 2 loads = 2. Proposition 22.2.7 below states this in general.

Local allocation in LLVM (RegAllocFast)¶

On the running example with \(K = 3\) the whole-value local allocator of the lab (E1) finds that a, i, s, s2, i2 cross block boundaries, so they live in memory; only the block-local c, t, u, r get registers, and one register suffices because each dies at the next instruction:

value	crosses a block boundary?	location	why
a	yes (live-out of B0)	slot	global
i, s	yes (live-out of B1)	slot	global
s2, i2	yes (live-out of B2, phi operands)	slot	global
c	no (used by B1's `br`)	r0	free register
t	no	r0	`s` is in memory, r0 free again after `c`
u	no	r0	`t` dies at `u = add t a`: reuse
r	no	r0	free

Spill cost (lab metric, loads and stores weighted by \(10^{\text{loop depth}}\)): 126, against 13 for the global allocators of the next lessons with the same \(K\) (ch22-regalloc --method=local --gpr=3 --metrics). That factor of ten is the price of never keeping a value in a register across a branch.

Try it

./course drill belady --seed 4 --difficulty hard --solution replays a random block with MIN and asks for the LRU count as well.

4. Invariants and correctness¶

Belady's MIN¶

Theorem 22.2.6 (MIN is optimal)

For every reference string \(\sigma\) and every \(K \ge 1\), the number of misses of Algorithm 22.2.2 is the minimum number of loads over all schedules (Definition 22.2.1).

Proof (exchange argument; see also [KT06, §4.3])

Call a schedule reduced if it loads only \(\sigma_t\) at a miss and evicts only at a miss with full registers. MIN is reduced.

Claim 1: every schedule can be turned into a reduced one with no more loads, without changing its first \(j\) steps if those are already reduced. Postpone each load of a value \(v\) to the next reference to \(v\) (drop it if \(v\) is evicted or never referenced before then), and postpone each eviction to the next moment the registers are full at a miss. Holding a value longer can only turn misses into hits, every reference is still served, and each postponed load is charged at most once, so the number of loads does not grow.

Claim 2: if a reduced schedule \(S\) agrees with MIN on the first \(j\) steps, there is a reduced schedule \(S'\) that agrees with MIN on the first \(j + 1\) steps and has no more loads. If step \(j + 1\) is a hit, or a miss with free registers, \(S\) already does what MIN does. Otherwise MIN evicts \(f\) (furthest next use) and \(S\) evicts some \(e \ne f\). Let \(S'\) evict \(f\) at step \(j + 1\); now \(S'\) holds \(e\) where \(S\) holds \(f\), and otherwise the same values. After step \(j + 1\), \(S'\) copies \(S\) until the first step \(t\) at which one of these happens: (a) \(\sigma_t = e\). It comes before any reference to \(f\), because \(\mathrm{next}_{j+1}(f) \ge \mathrm{next}_{j+1}(e)\) and \(S\) has not re-loaded \(e\) (it is reduced). \(S\) misses and loads \(e\), evicting some \(x\). If \(x = f\), the two register sets are now equal and \(S'\), which hit, has one load fewer. If \(x \ne f\), let \(S'\) evict \(x\) and load \(f\) at this step: both schedules made one load and their register sets are equal. (b) \(S\) evicts \(f\) to serve a miss on some \(y \notin \{e, f\}\): let \(S'\) evict \(e\) instead; both loaded \(y\) and the register sets are equal. (c) The string ends. A reference to \(f\) cannot come first: that would need \(\mathrm{next}(f) < \mathrm{next}(e)\), or both infinite, in which case nothing is referenced. From step \(t\) on, \(S'\) copies \(S\). So \(S'\) has at most the loads of \(S\). The only step of \(S'\) that may not be reduced is the extra load of \(f\) in case (a), after step \(j + 1\); Claim 1 removes it without adding loads or changing the first \(j + 1\) steps.

Start from an optimal schedule, make it reduced (Claim 1), and apply Claim 2 for \(j = 0, 1, \dots, m - 1\): the result is MIN's schedule, with at most the optimal number of loads. Ties (several values with the same furthest next use) do not matter in the argument, so any tie-breaking rule is optimal.

Proposition 22.2.7 (MIN is not optimal with store costs)

When evicting a dirty value that will be used again costs a store (Definition 22.2.3), furthest-next-use eviction is not optimal.

Proof

The instance of §3: \(K = 2\), registers \(\{c \text{ (clean)}, d \text{ (dirty)}\}\), references e c d. MIN pays one store and two loads (3); evicting \(c\) pays two loads (2). The general problem with stores is NP-hard [FCL00, Theorem 1], so no simple eviction rule is optimal unless P = NP.

The invariant of Algorithm 22.2.4 (at most \(K\) occupied registers, operands present at their instruction) is maintained by construction: Pick never returns a register holding an operand of the current instruction, which is possible as long as \(K\) is at least the number of operands plus one. Its end-of-block stores make the precondition of the next block true, which is what makes a sequence of local allocations a correct global allocation.

Local allocation in LLVM (RegAllocFast)¶

Proposition 22.2.8 (RegAllocFast's block boundary invariant)

If every virtual register that may be live across a block boundary is stored to its slot after each definition and reloaded at the start of each block that uses it before defining it, then allocating each block independently yields a correct program.

Proof

Within a block the allocator maintains, walking backwards, that each virtual register with a use below the current point is in the register recorded in LiveVirtRegs from its last (in program order: first) reload or definition to that use, and that no other value is written to that register in between (a register is re-assigned only after being displaced, and displacement inserts a reload of the displaced value). At the block's start every remaining live virtual register is reloaded from its slot, and by the hypothesis its slot holds the value stored at its definition in a previous block. Blocks do not share register contents, so the correctness of each block implies the correctness of the function. The hypothesis is what mayLiveOut, mayLiveIn and the spills after definitions guarantee [LLVM-RAFast].

5. Complexity¶

\(m\) = references (or instructions) in a block, \(K\) registers, \(N\) instructions in the function.

Algorithm	Time (worst)	Time (typical)	Space	Justification
MIN (Algorithm 22.2.2)	\(O(m \log K)\) with a heap keyed by next use; \(O(mK)\) with a scan	\(O(mK)\), \(K \le 32\)	\(O(m)\) for `nextpos`	one heap update per reference
Optimal with stores	NP-hard [FCL00]; \(O(m \cdot \binom{n}{K})\) by dynamic programming over cache states	—	exponential	DP over \(\le \binom{n}{K} 2^K\) states per step
Local allocation (Algorithm 22.2.4)	\(O(N K)\)	linear	\(O(K)\) + next-use table	constant work per operand, scan of \(K\) registers per eviction
RegAllocFast	\(O(N \cdot U)\), \(U\) = register units per register	linear in practice	\(O(\text{units})\)	one pass per block, no liveness analysis

Pathological family. Consider the loop for (i…) { x0 += …; x1 += …; …; x_{K} += …; } with \(K + 1\) accumulators. Every accumulator is live across the back edge, so a local allocator keeps all of them in memory: \(2(K+1)\) memory operations per iteration, and the loop runs \(10\times\) more often than the surrounding code in the weighting of Lesson 22.9. A global allocator keeps \(K\) of them in registers and spills one. On the lab corpus with \(K = 8\), local allocation's weighted spill cost is about ten times that of the global allocators (Lesson 22.8 §8 has the table).

Belady's MIN¶

Online policies (LRU, FIFO, clock). They do not know the future; LRU is \(K\)-competitive, the best possible ratio for deterministic online paging [ST85]. Trade-off: usable at run time (caches), strictly worse than MIN offline (7 vs 5 loads in §3). A compiler knows the future of a block, so it has no reason to use them.
Optimal with stores. Horwitz et al. give an exact exponential algorithm [HKMW66]; Farach-Colton and Liberatore prove NP-hardness and give a 2-approximation [FCL00]. Trade-off: optimality at exponential cost versus a factor-2 guarantee.
Belady across blocks. Braun and Hack extend furthest-next-use to whole SSA programs, deciding at block entries which values to keep, with next-use distances measured along the CFG and loops counted as far away [BH09]; this is the spiller of libFirm and of Lesson 22.6. Trade-off: near-optimal spilling in linear time, but it needs SSA and a separate colouring phase.

Local allocation in LLVM (RegAllocFast)¶

Top-down (frequency-count) local allocation. Give the \(K\) most-used values of the block a register for the whole block [EaC3, Ch. 13]. Trade-off: trivial, but a value used heavily at the start and never at the end keeps its register.
Bottom-up versus top-down walking. RegAllocFast walks backwards so that it sees uses before definitions and can place reloads right before the uses it knows about; EaC's bottom-up allocator walks forwards with next-use distances. Trade-off: the backward walk needs no next-use table.

7. In real compilers¶

Belady's MIN¶

Go's SSA back end allocates each function in one linear pass and, when it must free a register, evicts the value whose next use is farthest away (regAllocState.allocReg in src/cmd/compile/internal/ssa/regalloc.go, go1.24.7) [Go-regalloc]. Next-use distances come from regAllocState.computeLive. libFirm's spiller is Belady-based (ir/be/bespillbelady.c, libfirm-1.22.0, see Lesson 22.6) [Firm-Belady]. LLVM does not use MIN: its local decisions come from spill weights.

Go's allocator spills the value used farthest in the future

Reproduce (go 1.24.7, linux/amd64; curl reads the pinned source):

curl -s https://raw.githubusercontent.com/golang/go/go1.24.7/src/cmd/compile/internal/ssa/regalloc.go \
  | sed -n '446,461p'
cat > main.go <<'EOF'
package main

//go:noinline
func press(a []int) int {
    s0, s1, s2, s3, s4, s5, s6, s7 := 0, 1, 2, 3, 4, 5, 6, 7
    s8, s9, s10, s11, s12, s13, s14, s15 := 8, 9, 10, 11, 12, 13, 14, 15
    for _, x := range a {
        s0 += x; s1 ^= x; s2 += x * 3; s3 -= x; s4 += x >> 1; s5 |= x; s6 += x << 2; s7 &= x
        s8 += x * 5; s9 ^= x << 1; s10 += x >> 3; s11 -= x * 7; s12 ^= x + 1; s13 += x - 2
        s14 ^= x * 9; s15 += x >> 2
    }
    return s0 + s1 + s2 + s3 + s4 + s5 + s6 + s7 + s8 + s9 + s10 + s11 + s12 + s13 + s14 + s15
}

func main() { println(press([]int{1, 2, 3})) }
EOF
go tool compile -d=ssa/regalloc/dump=press -o /dev/null main.go
echo "StoreReg: $(grep -c StoreReg press_01__regalloc.dump)  LoadReg: $(grep -c LoadReg press_01__regalloc.dump)"

Output (complete):

    // Find a register to spill. We spill the register containing the value
    // whose next use is as far in the future as possible.
    // https://en.wikipedia.org/wiki/Page_replacement_algorithm#The_theoretically_optimal_page_replacement_algorithm
    var r register
    maxuse := int32(-1)
    for t := register(0); t < s.numRegs; t++ {
        if mask>>t&1 == 0 {
            continue
        }
        v := s.regs[t].v
        if n := s.values[v.ID].uses.dist; n > maxuse {
            // v's next use is farther in the future than any value
            // we've seen so far. A new best spill candidate.
            r = t
            maxuse = n
        }
StoreReg: 25  LoadReg: 29

What to notice: the loop in allocReg is Algorithm 22.2.2's argmax next, with uses.dist = number of instructions to the next use. Sixteen accumulators plus the loop variables exceed amd64's allocatable registers, so the dump contains 25 spill stores (StoreReg) and 29 reloads (LoadReg). Go applies the rule globally, in a single pass over the blocks in layout order, and repairs mismatches on merge edges with shuffle, which is why Go's allocator is often called "linear scan" in its source.

Local allocation in LLVM (RegAllocFast)¶

llc -O0 (and -regalloc=fast at any level) runs RegAllocFast [LLVM-RAFast]; its register choice is RegAllocFastImpl::allocVirtReg with calcSpillCost returning spillClean = 50 or spillDirty = 100. GCC's IRA switches to fast_allocation at -O0 (gcc/ira-color.cc, gcc-15.1.0: "a simple register allocator without usage of allocno conflicts … close to Chow's priority coloring"), selected in ira.cc by ira_conflicts_p = optimize > 0 [GCC-IRA].

The running example under LLVM's fast and greedy allocators

Reproduce (llc 23.1.2; run.ll is the file from Lesson 22.1 §7):

for o in "-O0" "-O2 -regalloc=fast" "-O2"; do
  for t in x86_64-linux-gnu aarch64-linux-gnu; do
    llc $o -mtriple=$t run.ll -o r.s
    printf '%-20s %-18s spills %d reloads %d\n' "$o" $t $(grep -c 'Spill$' r.s) $(grep -c 'Reload$' r.s)
  done
done
llc -O2 -regalloc=fast -mtriple=x86_64-linux-gnu run.ll -o - | sed -n '/^run:/,/^\.Lfunc_end0/p' | grep -v '\.cfi\|\.p2align'

Output (complete):

-O0                  x86_64-linux-gnu   spills 7 reloads 7
-O0                  aarch64-linux-gnu  spills 7 reloads 7
-O2 -regalloc=fast   x86_64-linux-gnu   spills 5 reloads 6
-O2 -regalloc=fast   aarch64-linux-gnu  spills 3 reloads 4
-O2                  x86_64-linux-gnu   spills 0 reloads 0
-O2                  aarch64-linux-gnu  spills 0 reloads 0
run:                                    # @run
# %bb.0:                                # %entry
    movq    %rdi, %rax
    movq    %rax, -8(%rsp)                  # 8-byte Spill
    xorl    %ecx, %ecx
    movq    %rcx, -24(%rsp)                 # 8-byte Spill
    movq    %rax, -16(%rsp)                 # 8-byte Spill
    movq    -8(%rsp), %rdx                  # 8-byte Reload
.LBB0_1:                                # %loop
                                        # =>This Inner Loop Header: Depth=1
    movq    -24(%rsp), %rax                 # 8-byte Reload
    cmpq    $9, %rax
    jg  .LBB0_3
# %bb.2:                                # %body
                                        #   in Loop: Header=BB0_1 Depth=1
    movq    -24(%rsp), %rax                 # 8-byte Reload
    movq    -16(%rsp), %rcx                 # 8-byte Reload
    imulq   %rax, %rcx
    addq    %rdx, %rcx
    xorq    %rax, %rcx
    movq    %rcx, -16(%rsp)                 # 8-byte Spill
    incq    %rax
    movq    %rax, -24(%rsp)                 # 8-byte Spill
    jmp .LBB0_1
.LBB0_3:                                # %exit
    movq    -16(%rsp), %rax                 # 8-byte Reload
    movq    -8(%rsp), %rcx                  # 8-byte Reload
    addq    %rcx, %rax
    retq
.Lfunc_end0:

What to notice: with the fast allocator every value that crosses a block boundary (i in slot −24, s in −16, a in −8) is stored after its definition and reloaded in every block that uses it (Proposition 22.2.8): the loop body reloads i although the header just loaded it. The greedy allocator (-O2) keeps all of them in registers. The reload of a into %rdx sits before the loop, not in it: after allocation, MachineLICM hoisted the loop-invariant reload. -O0 also changes instruction selection (FastISel), so its counts are not only the allocator's doing; -O2 -regalloc=fast isolates the allocator.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Belady's MIN	optimal loads for a clean reference string (Theorem 22.2.6); not optimal with stores (Proposition 22.2.7)	\(O(m \log K)\) · negligible	minimal reloads within a block; blind to control flow	tiny	spill choice in Go, libFirm, SSA spillers; lab E0
Local allocation (RegAllocFast, lab E1)	no value in a register across blocks	\(O(N)\) · the fastest LLVM allocator	many spills: 7/7 on the running example at `-O0`, weighted spill cost ≈ 10× the global allocators in the lab	small	`-O0`, JIT baseline tiers

Choose MIN when you must decide what to evict inside a straight-line region with known future uses: it is optimal there and trivial to implement. Choose a local allocator when compile time matters more than code quality (debug builds, baseline JITs) or when values must live in memory anyway (debugging).

9. Assessment¶

Quiz (./course quiz 22): belady-trace, belady-loads, fast-backward, fast-spill-cost (tags belady, regallocfast).
Drill: ./course drill belady (loads, evictions, LRU comparison).
Flashcards: tags belady, regallocfast.
Lab: E0 beladyMisses (tested against exhaustive search), E1 allocateLocal (SPEC R5, R11).

References¶

See the chapter references.

Lesson 22.2 — Local allocation: Belady's MIN and LLVM's fast allocator¶

1. Problem and motivation¶

Belady's MIN¶

Local allocation in LLVM (RegAllocFast)¶

2. Definitions and algorithms¶

Belady's MIN¶

Local allocation in LLVM (RegAllocFast)¶

3. Worked example¶

Belady's MIN¶

Local allocation in LLVM (RegAllocFast)¶

4. Invariants and correctness¶

Belady's MIN¶

Local allocation in LLVM (RegAllocFast)¶

5. Complexity¶

6. Variants and refinements¶

Belady's MIN¶

Local allocation in LLVM (RegAllocFast)¶

7. In real compilers¶

Belady's MIN¶

Local allocation in LLVM (RegAllocFast)¶

8. Comparison¶

9. Assessment¶

References¶