用线性扫描分配寄存器，再标记与清除

目标

在使用虚拟寄存器的中间代码里，求出值的活跃区间，用线性扫描把它们分配到 k 个真实寄存器上，并做到有循环的 CFG 的活跃性分析。接着做一个 mark-sweep 回收器，在堆的图中只保留能从根到达的对象，并统计引用计数方式漏掉了什么。

为什么重要

-O0 与 -O2 最大的差别，是值是否放在寄存器里，而这个决定取决于“两个值是否同时活跃”。垃圾回收则在另一头——运行中创建的对象什么时候可以丢弃——用同样的工具（沿着图找出能到达的东西）来解决。两者都容易在一个字符（< 与 <=，递归与循环）上出错。

规则

중간 코드   명령 {"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"}

步骤

补全 /root/mini/regalloc.py 的 liveness(code)。
补全 intervals(code) 和 max_pressure(code)。
补全 linear_scan(ivs, k)——评分器会分别用 1、2、3、4、6 个寄存器对照。
补全 conflicts(ivs, alloc)——对正确的分配不能出现误报。
补全 block_liveness(blocks, succ)——/opt/fixtures/mini/regalloc/loop.json 里有循环的例子。
补全 /root/mini/heap.py 的 mark(heap, roots)。
补全 sweep(heap, marked) 和 refcount_leaks(heap, roots)。
补全 simulate(trace, capacity)——/opt/fixtures/mini/regalloc/trace.json 是可以手工跟着走一遍的例子。

参考

材料：/opt/fixtures/mini/regalloc/ 里的 straight.json（可以手算的直线代码）、pressure.json（寄存器不够用的代码）、loop.json 和 trace.json。
常见错误：返回 live-in 而不是 live-out，释放终点与新起点相同的区间，溢出时总是溢出新区间，CFG 只扫描一遍，把标记写成递归，在环里重复访问已经看过的对象。
会话从 60 分钟开始，可以用＋时间延长，结束后 /root/mini 会消失。

从后往前——活跃性分析

把 live 集合清空，从最后一条指令开始倒着走。对每条指令，先把当前的 live 记为这条指令的 live-out，然后减去 def，加上 use（这就是前一条指令的 live-out）。

活跃区间与同时活跃的数量

遇到 def 就以 [i, i] 开始，每遇到一次 use，就把终点扩大为 max(终点, i)。最大同时活跃数，是每条指令的 use、def 和 live-out 合并成的集合的大小中最大的那个值。

线性扫描

按起点顺序扫描，并带着一个活跃列表。对每个新区间，先只释放终点 < 新起点的那些，取回寄存器（相等的话还在使用）。空闲寄存器从编号小的开始用。没有的话，就把 (终点, 名字) 最大的那个溢出，如果它不是新区间，就把它的寄存器交给新区间。

验证分配

把不是 spill 的值按名字顺序排好，检查所有的两两组合。如果寄存器相同、区间又重叠（一方的起点 ≤ 另一方的终点，反过来也成立），就是冲突。终点与起点正好相接也算重叠——因为那条指令两者都要用。

有循环的活跃性分析

先求出每个块的 use（在块内定义之前就被使用的）和 def。然后对所有块应用 live_out = 后继块们的 live_in 的并集、live_in = use ∪ (live_out − def)，如此反复，直到一整圈都没有任何变化。

给从根能到达的对象做标记

不用递归，用列表当栈。从在堆中的根开始，取出的对象如果已经看过就跳过，否则标记它，并把它所指向的对象压入栈。必须跳过已经看过的，在有环的情况下才能结束。

清除，以及引用计数漏掉的东西

sweep 只把被标记的对象移到新字典。refcount_leaks 统计所有对象被引用的次数（包括根），把为 0 的清理掉，并减少它所指向的对象的计数，如此反复。最后还剩下、却无法通过 mark 到达的，就是泄漏的那一部分。

按分配记录运转的回收器

遇到 alloc 时，如果已经有 capacity 个了，就先 mark → sweep，再累加回收次数和清理的个数。如果仍有 capacity 个，就记下 error 并停止。peak 是 alloc 之后的对象数中的最大值。手工跟着 trace.json 走一遍，就能看出规则。