寄存器少、值很多 — 按生命周期分配并回收
一句话总结
编译器可以为每个值无限地创建名字（虚拟寄存器），而 CPU 的寄存器只有十六个。活跃性分析会求出每个值从何时到何时一直活着，线性扫描让互不重叠的值共用同一个寄存器，不够用时就把一部分溢出（spill）到内存。至于程序在运行中创建的对象，则正好相反：当没有任何东西再指向它们时，垃圾回收器只保留从根可达的对象，把其余的清理掉。
为什么需要它
第 8 个模块的代码生成器把所有局部变量都放在栈槽位里，每次使用都要从内存读写。这不会出错，但寄存器一个周期就能读到，而内存即使在缓存里也要好几个周期。gcc -O0 与 -O2 输出之间最大的差别就在这里——值是否放在寄存器里。
可是值多，寄存器少。两个值如果不同时活跃，就可以用同一个寄存器。“活跃”的意思是“以后还会再读这个值”，仅凭代码来计算它，就是活跃性分析。
在内存的另一头也有同样的问题。第 5 个模块的闭包，把已经调用结束的环境抓住，让它继续存活。那么，什么时候可以丢弃？就是再也没有任何东西能到达它的时候。垃圾回收器替人来计算这件事。
工作原理
活跃性分析从后往前。如果知道紧跟在指令 i 之后活跃的值（live-out），那么它之前的（live-in）就是 use ∪ (live_out − def)——这条指令使用的值，在它之前也必须是活跃的，而这条指令定义的值，在它之前还不存在。从最后一条指令开始倒着走，一遍就结束。在有循环的 CFG 里，因为有向后的边，一遍是不够的——按块来说，要反复计算 live_out = 다음 블록들의 live_in 합집합（韩文意为“后继块的 live_in 的并集”），直到不再变化为止（与第 7 个模块的支配节点一样，都是不动点计算）。
线性扫描。为每个值建立 [定义它的指令, 最后使用它的指令] 区间，按起点顺序扫描，分配寄存器。
구간(명령 번호) 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 는 아직 쓰는 중(같으면 풀지 않는다) → 넘긴다
之所以要把终点最远的那个溢出，是因为那个值会占用寄存器最久。被溢出的值，每次使用都要从内存读写（第 8 个模块的槽位就是那个位置）。在新区间之前，只释放终点小于新起点的区间——因为在同一条指令上结束的值，那条指令还在读它。就是这一个字符（< 与 <=）的差别，是最常见的失误。
mark-sweep。把堆看作“对象 → 它所指向的对象们”的图，那么只有从根（栈和全局中的值）出发能顺着走到的对象才是活的。标记（mark）阶段从根出发遍历图，给走到的对象做上标记；清除（sweep）阶段把没有标记的全部清理掉。即使有环（A ↔ B），已经标记过的也不再看，所以能够结束，而脱离了根的环，则会被整个清理掉。如果把标记写成递归，在 10 万个节点的链表上会超过递归上限，所以要用显式的栈来遍历。
引用计数漏掉的东西。给每个对象数“有几处指向我”，数到 0 就立刻清理，这种方式（引用计数）没有标记阶段，立即清理，没有停顿。但如果 A 和 B 互相指向，即使脱离了根，计数也降不到 1 以下，所以会永远留下来。CPython 以引用计数为基础，却另设一个寻找环的回收器（gc 模块），原因就在这里。
在现场相遇的样子
- JIT 喜欢线性扫描。图着色（graph coloring）方式能把寄存器用得更好，但是更慢。需要在运行中编译的 JIT（HotSpot 的 C1、V8 的早期阶段）使用速度快的线性扫描一类，因为编译时间就是用户等待的时间。
- GC 停顿。mark-sweep 在标记期间必须暂停程序（期间如果指针发生变化，标记就会出错）。堆一大，这个停顿就会达到几百毫秒。真实的 JVM 如何把这种停顿记入日志，又用什么来缩短它，会在 堆还有空间，服务却停了 课程的 GC 日志模块里讲。
- 不靠 GC 来清理。Rust 不用回收器，而是在编译时确定“这个值的主人在哪里消失”，在那个位置放入释放代码。可以说，这是把第 4 个模块的作用域分析扩展到了值的生命周期，Rust — 编译器拦下的那些 课程会通过错误信息来阅读这些规则。
下一项实验要做什么
在 regalloc.py 中做出直线代码的活跃性分析、活跃区间与最大同时活跃数、线性扫描、分配验证器，以及有循环的 CFG 的逐块活跃性分析；在 heap.py 中做出标记与清除、引用计数漏掉的垃圾的计算，以及按分配记录运转的回收器。评分器会用几百个随机代码、图、堆和记录与参考对照。