Split Registers with Linear Scan, Then Mark and Sweep

Goal

From intermediate code that uses virtual registers, you find the intervals in which values are alive, divide them among k real registers with linear scan, and even do liveness analysis of a CFG with loops. Next, you build a mark-sweep collector that keeps only the objects reachable from the roots in a heap graph, and count what reference counting misses.

Why it matters

The biggest difference between -O0 and -O2 is whether values are kept in registers, and that decision depends on "are the two values alive at the same time?" Garbage collection solves the opposite side — when may an object created at run time be thrown away — with the same tool (finding what is reachable by following a graph). In both, it is easy to go wrong over a single character of the rules (< versus <=) or over recursion versus iteration.

The rules

중간 코드   명령 {"op", "def"(없을 수 있음), "use": [..]} 의 목록. 가상 레지스터마다 def 는 한 번(param 도 def)
liveness    명령마다 그 명령 **바로 뒤** 에 살아 있는 값(이름순 목록). 마지막 명령 뒤는 빈 목록
intervals   {값: [정의한 명령, 마지막으로 쓰는 명령]} (쓰지 않으면 [정의, 정의])
max_pressure 한 명령에서 쓰는 값 ∪ 정의하는 값 ∪ 그 뒤에 살아 있는 값 의 크기 가운데 최댓값
linear_scan(구간, k)  → {값: "r0".."r{k-1}" 또는 "spill"}
            시작 순(같으면 이름순)으로 훑는다. 새 구간 앞에서 끝 < 새 시작 인 활성 구간만 풀어 준다.
            빈 레지스터가 있으면 번호가 가장 작은 것. 없으면 활성 구간과 새 구간 가운데 끝이 가장 먼 것
            (끝이 같으면 이름이 큰 쪽)을 넘기고, 넘긴 것이 활성 구간이면 그 레지스터를 새 구간이 물려받는다
conflicts   같은 레지스터를 받은 두 구간이 겹치면(s1 ≤ e2 이고 s2 ≤ e1) [a, b](이름순), 목록도 정렬
block_liveness(blocks, succ)  → (live_in, live_out) 블록마다 이름순 목록. 고정점까지 되풀이
mark(heap, roots)   heap = {번호: [가리키는 번호…]}. 뿌리에서 닿는 번호(오름차순). 힙에 없는 뿌리는 무시.
                    재귀하지 않는다(10만 개짜리 연결 리스트도 받는다)
sweep(heap, marked) → (살아남은 힙, 치운 번호 오름차순)
refcount_leaks(heap, roots)  뿌리도 참조 하나로 센다. 0 인 것을 치우며 가리키던 것의 수를 줄이고 되풀이.
                    그래도 남았는데 뿌리에서 닿지 않는 번호(오름차순)
simulate(trace, capacity)  기록: ["alloc", n] · ["link", a, b] · ["unlink", a, b] · ["root", n] · ["unroot", n]
                    alloc 하려는데 힙이 capacity 개면 먼저 mark-sweep. 그래도 꽉 차면 "out of memory" 로 멈춘다.
                    → {"collections", "freed", "peak", "live"(끝의 번호 오름차순), "error"}

Steps

1. Fill in liveness(code) in /root/mini/regalloc.py.
2. Fill in intervals(code) and max_pressure(code).
3. Fill in linear_scan(ivs, k) — the grader compares with 1, 2, 3, 4, and 6 registers.
4. Fill in conflicts(ivs, alloc) — there must be no false alarms on correct allocations.
5. Fill in block_liveness(blocks, succ) — /opt/fixtures/mini/regalloc/loop.json has a loop example.
6. Fill in mark(heap, roots) in /root/mini/heap.py.
7. Fill in sweep(heap, marked) and refcount_leaks(heap, roots).
8. Fill in simulate(trace, capacity) — /opt/fixtures/mini/regalloc/trace.json is an example you can follow by hand.

Notes

• Materials: in /opt/fixtures/mini/regalloc/, straight.json (straight-line code to work out by hand), pressure.json (code with too few registers), loop.json, and trace.json.
• Common mistakes: returning live-in instead of live-out, freeing an interval whose end is equal to the new start, always spilling the new interval, sweeping the CFG only once, writing marking recursively, and revisiting an object already seen in a cycle.
• The session starts at 60 minutes and you can extend it with the +time button, and when it ends /root/mini disappears.

From back to front — liveness analysis

Start with an empty live set and walk backward from the last instruction. For each instruction, first write the current live as that instruction's live-out, then subtract def and add use (that becomes the live-out of the previous instruction).

Live intervals and the number alive at once

When you meet a def, start with [i, i], and each time you meet a use, extend the end to max(end, i). The maximum number alive at once is the largest size, over instructions, of the set combining use, def, and live-out.

Linear scan

Sweep in order of start, carrying a list of active intervals. For each new interval, first free, and take back the registers of, only those with end < new start (if equal, it is still in use). Take a free register starting from the smallest number. If there is none, spill the one with the largest (end, name), and if that is not the new interval, give that register to the new interval.

Verify the allocation

Put the values that are not spilled in name order and look at every pair. If they have the same register and their intervals overlap (one's start ≤ the other's end, and vice versa), it is a conflict. Intervals where an end and a start touch also overlap — because that instruction uses both.

Liveness analysis with loops

For each block, first find use (used before being defined inside the block) and def. Then apply live_out = the union of the live_in of the next blocks and live_in = use ∪ (live_out − def) to all blocks, repeating until nothing changes during a full pass.

Mark what is reachable from the roots

Use a list as a stack instead of recursion. Starting from the roots that are in the heap, if a popped object has already been seen, skip it; otherwise mark it and then push the objects it points to. You must skip what has already been seen for it to finish even on a cycle.

Sweep, and what reference counting misses

sweep moves only the marked ones into a new dictionary. refcount_leaks counts the incoming reference count of every object (including roots), and repeats clearing those at 0 and reducing the counts of what they pointed to. What remains to the end yet is not reached by mark is the leaking share.

A collector that runs along an allocation trace

When you meet an alloc and there are already capacity objects, do mark → sweep and then add the collection count and the number freed. If it is still capacity, write error and stop. peak is the maximum of the object count right after an alloc. If you follow trace.json by hand, you can see the rules.