Register Allocation (Linear Scan)

Stack-machine codegen is correct but slow: every operation hits memory. Register allocation assigns IR temporaries to a fixed pool of K physical registers; values that can't fit get spilled (kept in stack slots, loaded only when used).

Two classic algorithms

1. Graph coloring (Chaitin, 1981) — build an interference graph (nodes = temps, edges = "both live at the same time"), K-color it. Optimal in theory; O(n²) typical. Used in production GCC.
2. Linear scan (Poletto & Sarkar, 1999) — walk live intervals in order of start point, maintain a list of active intervals. Linear in the number of temps. Used in JIT compilers (HotSpot C1, LLVM fast-isel).

Linear scan trades a tiny bit of code quality for a lot of compile-time speed. We implement it.

Live intervals

For each temp, compute the range [start, end] of IR instructions during which it's live. Two temps interfere iff their intervals overlap.

1: a = ...
2: b = ...
3: c = a + b     ; a, b are live here
4: d = c * 2     ; c is live; a, b dead
5: print d

Intervals: a:[1,3], b:[2,3], c:[3,4], d:[4,5].

The algorithm

sort intervals by start
active = []                  ; sorted by end-point
for I in intervals:
  expire_old(I.start)        ; remove from active any J with J.end < I.start; free its reg
  if |active| == K:
    spill_at(I)              ; pick spill candidate, possibly displace
  else:
    allocate I to any free reg
    add I to active

Spill heuristic (the cheap one): the active interval with the latest end-point is the spill candidate. If its end is later than the current interval's end, displace it and give its register to the current; mark the displaced one as spilled. Otherwise spill the current one.

What "spilled" really means

A spilled temp lives in a stack slot. Every use becomes mov reg, [rbp - offset] followed by the op, every def becomes mov [rbp - offset], reg. The stack slot allocator runs separately.

What our exercise builds

A linear-scan allocator that consumes K + a list of intervals and prints the allocation: each temp gets either a register r0..r(K-1) or SPILLED.

References: Poletto & Sarkar, "Linear Scan Register Allocation" (ACM TOPLAS 1999); LLVM RegAllocFast and RegAllocGreedy; Muchnick, "Advanced Compiler Design" Ch. 16.