Few Registers, Many Values — Splitting by Lifetime and Cleaning Up

In one line

A compiler makes up and uses endless names (virtual registers) for values, but the CPU has only sixteen registers. Liveness analysis finds from when to when a value is alive, linear scan lets values that do not overlap share the same register, and when there are not enough, some are spilled to memory. Conversely, for the objects a program creates while running, once nobody points to them anymore, a garbage collector keeps only what is reachable from the roots and clears the rest.

Why this was needed

Module 8's code generator puts all local variables in stack slots and reads and writes memory each time it uses them. It is not wrong, but a register is read in one cycle, while memory takes several cycles even when it is in the cache. The biggest share of the difference between gcc -O0 and -O2 output is this — whether you keep values in registers.

But values are many and registers are few. If two values are not alive at the same time, they may use the same register. "Alive" means "there is a chance this value will be read again later," and computing that from the code alone is liveness analysis.

The same question exists on the other side, in memory. Module 5's closures held on to and kept alive an environment whose call had ended. Then when may it be thrown away? When nobody can reach it anymore. A garbage collector computes that in place of a person.

How it works

Liveness analysis runs from back to front. If you know the values alive right after instruction i (live-out), then those before it (live-in) are use ∪ (live_out − def) — a value this instruction uses must be alive before it too, and a value this instruction defines did not exist yet before it. If you walk backward from the last instruction, it finishes in one pass. In a CFG with loops, back edges mean one pass is not enough — per block, you repeat live_out = 다음 블록들의 live_in 합집합 (the live_out is the union of the live_in of the next blocks) until nothing changes (the same fixed point computation as module 7's dominators).

Linear scan. For each value, you make an interval [the instruction that defines it, the last instruction that uses it], sweep in order of start, and hand out registers.

구간(명령 번호)          k = 2 개의 레지스터로
t1 [0 ──────── 4]        t1 → r0
t2   [1 ───────────── 6] t2 → r1
t3     [2 ──── 4]        t3: 빈 레지스터가 없다. 활성인 t1(끝 4)·t2(끝 6)와 t3(끝 4) 가운데
                             끝이 가장 먼 t2 를 넘기고, t3 가 t2 의 r1 을 물려받는다
t4        [3 ── 5]       t4: 여전히 꽉 참. t1·t3(끝 4)·t4(끝 5) 가운데 끝이 가장 먼 것은 t4 자신 → t4 를 넘긴다
t5          [4 ─ 5]      t5: 시작 4 — 끝이 4 인 t1·t3 는 아직 쓰는 중(같으면 풀지 않는다) → 넘긴다

The reason you spill the one whose end is farthest is that that value will hold a register the longest. A spilled value is read and written from memory each time it is used (module 8's slots are exactly that place). Before a new interval, you free only the intervals whose end is smaller than the new start — because a value that ends at the same instruction is still being read by that instruction. This single character (< versus <=) is the most common mistake.

mark-sweep. If you view the heap as a graph of "object → the objects it points to," only the objects reachable from the roots (the values on the stack and in globals) are alive. The mark phase sweeps the graph from the roots and marks what it reaches, and the sweep phase clears everything without a mark. Even with a cycle (A ↔ B), it does not revisit what is already marked, so it finishes, and a cycle cut off from the roots is cleared as a whole. If you write marking recursively, a 100,000-element linked list exceeds the recursion limit, so you traverse with an explicit stack.

What reference counting misses. The approach of counting "how many places point to me" for each object and clearing it right away when it reaches 0 (reference counting) clears immediately with no mark phase, so there are no pauses. But if A and B point to each other, then even when they are cut off from the roots, the count does not drop from 1 and they remain forever. This is why CPython, while using reference counting by default, also keeps a separate collector that finds cycles (the gc module).

What it looks like in the field

• JITs like linear scan. The graph coloring approach uses registers better but is slow. A JIT that has to compile while running (HotSpot's C1, V8's early tiers) uses the fast linear scan family — because compile time is exactly the time the user waits.
• GC pauses. mark-sweep has to stop the program while marking (if pointers change in the meantime, the marks are wrong). With a large heap, this pause can reach hundreds of milliseconds. How a real JVM logs this pause and what reduces it is covered by the GC log module of the course The heap had room, but the service stopped.
• Clearing without GC. Rust decides at compile time "where the owner of this value disappears" and inserts the release code there, without a collector. It can be seen as extending module 4's scope analysis to the lifetime of values, and the course Rust — What the Compiler Refuses reads those rules through error messages.

What you will do in the next lab

In regalloc.py, you build liveness analysis on straight-line code, live intervals and the maximum number alive at once, linear scan, an allocation verifier, and per-block liveness analysis on a CFG with loops; in heap.py, you build mark and sweep, the computation of garbage that reference counting misses, and a collector that runs along an allocation trace. The grader compares against the reference with hundreds of random codes, graphs, heaps, and traces.