常见错误与练习

这一章的难点不在某一条 x86-64 指令，而在几套约束必须同时成立：数据流决定哪些值冲突，表示分析决定哪些值允许染色，ABI 决定寄存器怎样跨 call，GC 又决定哪些位置必须可扫描。

下面先整理最容易犯的错误，再用可以实际运行的程序逐层检查。

开始前进入本章目录并构建：

1
2

cd code/10_registers
make

常见错误

把 %rbp spill 当成 GC root

-48(%rbp) 和 -8(%r15) 都是内存，但 collector 只扫描后者。若把 record 引用 spill 到 %rbp，对象搬移后机器栈里仍是旧地址；下一次 get 或 call 就会访问 from-space 中已经失效的对象。

正确规则是：ordinary spill 只接收已经证明为整数的 Value；不能排除堆引用的值始终使用 root slot。

看见运行时是整数，就把 load 或 call 结果染色

某个示例中的函数可能每次都返回 42，但源语言没有函数返回类型。仅凭这个示例，编译器不能证明所有 call 结果都是整数。

当前保守规则把 load、get 和 call 结果分类为 root。它们随后若参加成功的 add、sub1、record? 或 size，新操作的结果才可能重新成为确定整数。

让不同语言子集经过不同 emitter

彼此独立的 emitter 很快会产生不同的求值顺序、错误检查、record 布局和调用约定。第十章的目标不是只改善一个小子集，而是让完整语言共同经过同一套分配流程。

./mini alloc examples/gc_stress.lang 应打印 main 和函数体的完整分析。

只看文本下一行计算活跃性

branch 有 then 和 else 两个后继，jump 的后继是目标 label。若把后继永远写成下一行，分支合流处的 live set 会漏值，冲突图也会缺边。

等到 add emitter 才一起检查两个操作数

源语言规定从左到右求值并及时报告错误。若先把 lhs 和 rhs 都求完，最后才由 add emitter 检查，错误的 lhs 仍可能让 rhs 中的 allocation、call、set! 或另一项错误先发生。

lowering 必须显式生成 integer_check：先 lower lhs 并立即 check，再 lower/check rhs，最后才生成 add。integer_check 是一次 use，没有 def，也没有独立 home。sub1 则在唯一操作数后立即 check。

把 caller-saved register 直接加入颜色列表

%rax、%rcx、%rdx、%rdi、%rsi、%r8～%r11 都可能被 call 改写。若没有 precolor/clobber 建模，把跨 call 活跃的整数放进去会静默算错。

本章只分配 %rbx、%r12、%r13、%r14，并在每个生成函数的 prologue/epilogue 中保存恢复。

在源语言 call 前清掉全部 caller roots

call operands 用完不等于 caller 的所有对象都死了。调用返回后还会使用的 record 必须跨越 callee 中的 collection；另一方面，已经消费且以后不用的巨大 argument 又应该及时清掉。

因此 call 先暂存 callee、argument 和 code pointer，再按 live_out 清 root。既不能无条件全清，也不能一项都不清。

把 abort() 和状态 70 混为一谈

受控语言错误进入 exit(70)；固定半区、root stack 或 runtime 内部协议无法继续时进入 abort()。解释器中的错误则由 mini 捕获，打印 error: 并返回 1。三种结果承担不同职责。

练习 1：读懂三种 home

运行：

1

./mini alloc examples/register_alloc_live.lang

先只看 values：

1
2
3
4

t.0 : integer -> register %rbx
t.1 : root -> root -8(%r15)
t.2 : integer -> register %r12
t.3 : integer -> register %rbx

依次回答：

1. t.0 对应源码中的哪一次计算？
2. 为什么 t.1 不能进入普通 spill？
3. t.0 与 t.2 为什么使用不同寄存器？
4. 最终的 t.3 为什么又能复用 %rbx？

再看 flow 和 interference。检查点是：check-integer t.0 使用 t.0、没有定义新名字；t.0 在检查和 record allocation 前后都活跃；t.0 与 t.2 互相冲突；定义 t.3 后，两项输入已经不再需要。

最后确认语义：

1

./mini run examples/register_alloc_live.lang

应输出 42。

练习 2：手推一个分支的活跃集

查看 registers.lang 的 IR 与分配结果：

1
2

./mini ir examples/registers.lang
./mini alloc examples/registers.lang

从最后的 return 开始，按下面两条方程向前推：

1
2

out = 所有后继 in 的并集
in  = use ∪ (out - def)

遇到 branch 时先分别推 then 与 else，再把两个入口集合并起来。然后与 alloc 的 in={...}、out={...} 对照。

思考：为什么 branch 的 out 需要考虑两条路径，而进入 then 以后，下一个 safepoint 的 in 又可以排除只在 else 使用的 Value？

程序的解释器结果应为：

1

10

练习 3：验证寄存器不够时真的 spill

运行：

1

./mini alloc examples/register_spill.lang

当前快照的末行应为：

1

root-bytes=0 spill-count=11

从 flow 中找出活跃整数最多的一点，再数一数当时集合中有多少项。前四种颜色分给 %rbx、%r12、%r13、%r14，其余冲突值为什么不能复用它们？

接着运行：

1

./mini run examples/register_spill.lang

应输出 210。在 Linux、WSL 或 Intel Mac 上再验证生成程序：

1
2
3
4

./mini compile examples/register_spill.lang -o out.s
c++ out.s gc_runtime.o -o out
./out
echo $?

进程状态也应为 210。如果 alloc 看到了 spill，而运行结果改变了，问题通常在 spill offset、机器栈大小、内存操作数改写或 epilogue 恢复中。

练习 4：为什么 int/record 合流必须保守

源码是：

1

(+ (record? (if 0 42 (record))) 41)

先运行：

1
2
3

./mini ir examples/register_mixed_join.lang
./mini alloc examples/register_mixed_join.lang
./mini run examples/register_mixed_join.lang

结果应为 42。在 alloc 输出中找到 if 两条分支共同定义的名字，它应分类为 root。

分三步解释：

1. then 定义来自整数，else 定义来自 record；
2. 编译器不能因为本次 condition 为 0 就删除另一条定义；
3. record? 无论收到哪一种 Value 都返回整数，因此它的结果可以参加染色。

把条件从 0 改成 1 再运行。结果会变成 41，但合流 Value 的静态分类不应改变。

练习 5：让整数跨越 allocation safepoint

再次使用：

1

./mini compile examples/register_alloc_live.lang -o out.s

先确认 IR 中 check-integer t.0 位于 record 之前，再在汇编中找到这个 check、mini_alloc 以及前后对 %rbx 的使用。回答：

1. 为什么 collector 不需要扫描 %rbx？
2. 为什么 C++ runtime 的 mini_alloc 不能破坏 %rbx 中的 40？
3. record 搬移时，哪个位置会被 collector 更新？

答案的关键分别是：%rbx 中已证明为 tagged integer；%rbx 是 callee-saved；record 位于 %r15 shadow root slot。

生成程序的状态仍应为 42。Apple Silicon Mac 链接时使用：

1

c++ -arch x86_64 out.s gc_runtime.o -o out

练习 6：整数跨 call 与多轮 GC

register_call_live.lang 同时制造三种 home。main 先计算多项整数，再调用递归函数；callee 每轮分配八字段 record，累计分配超过一个半区。

运行：

1
2

./mini alloc examples/register_call_live.lang
./mini run examples/register_call_live.lang

当前 main 的摘要是：

1

root-bytes=32 spill-count=4

解释器输出应为 42。在 values 中分别找出一个 register、一个 spill 和一个 root，再回答：

• caller 中的寄存器整数由谁保证跨 call 不变？
• caller 的 ordinary spill 为什么不会被 callee 覆盖？
• callee 触发 collection 时，为什么不能扫描 ordinary spill？
• call 返回值为什么先保守进入 root，而后续 add 的结果可以成为 integer？

最后编译、链接，确认进程状态也是 42。这项测试同时覆盖寄存器保存、spill 帧、call clobber、caller root 生命周期和 Cheney collection。

练习 7：正反验证 call 的 root 生命周期

依次运行：

1
2
3

./mini run examples/gc_caller_live.lang
./mini run examples/gc_branch_liveness.lang
./mini run examples/gc_call_liveness.lang

结果应为：

1
2
3

42
300
300

三个程序分别防住三种错误：

• gc_caller_live：不能漏掉返回后仍会读取的 caller root；
• gc_branch_liveness：不能让未执行路径上的死对象假活跃；
• gc_call_liveness：不能让已经消费的巨大 argument 跨整个 callee 假活跃。

编译结果的状态依次是 42、44、44，因为 shell 只保留退出状态低 8 位，300 mod 256 = 44。

思考：寄存器分配只给整数建冲突图，为什么这三个第九章的 root liveness 回归在第十章仍不可缺少？

练习 8：表示分类与显式 check 并不矛盾

运行错误程序：

1
2

./mini run examples/add_record_error.lang
echo $?

应看到类似：

1
2

error: addition left operand expected a number
1

再看分配：

1

./mini alloc examples/add_record_error.lang

这个程序把危险的递归分配放在右操作数：

1
2
3
4
5

(letrec build n
  (if (eq? n 0)
      (record)
      (record n (build (sub1 n))))
  (+ (record) (build 171)))

main 的关键 IR 是：

1
2
3
4
5
6
7
8

t.10 = record
check-integer t.10
t.11 = load build0.cell
check-closure t.11
t.12 = call t.11 171
check-integer t.12
t.13 = t.10 + t.12
return t.13

lhs record t.10 是 root，加法的 dst t.13 却是 integer。这不是自相矛盾：t.13 只在两次 integer_check 都成功后才会产生；第一条 check 失败时控制流直接进入错误出口，后面的 rhs call 根本不会执行。

(build 171) 会返回一条仍然可达的 record 链。若错误地先执行 rhs，它会超过 4096 字节半区并触发 abort。这个设计让求值顺序不再只是阅读 IR 的约定，而是可以通过进程结果区分：正确实现进入语言错误 70，错误实现会先 OOM。

验证编译结果：

1
2
3
4

./mini compile examples/add_record_error.lang -o out.s
c++ out.s gc_runtime.o -o out
./out
echo $?

状态应为 70，不能是 abort。在 out.s 中找到由第一条 integer_check 生成的 tag 比较和 .Lruntime_error，画出“检查成功才继续 rhs、检查失败立即退出”的两条控制流。

最后回到 register_alloc_live.lang：

1

./mini ir examples/register_alloc_live.lang

说明为什么 check-integer t.0 必须出现在右操作数的 record 之前，而 check-integer t.2 必须出现在最终 add 之前。若 lhs 错误，这个顺序会阻止 rhs 中的运行时操作；若 lhs 正确而 rhs 错误，则在 rhs 求完后立即报告。

练习 9：比较两个目标的符号拼写

生成两份汇编：

1
2

./mini compile examples/registers.lang -o linux.s --target linux
./mini compile examples/registers.lang -o macos.s --target macos

查看开头和 C ABI runtime 外部调用，确认：

1
2

Linux   : main  mini_gc_init  mini_gc_root_end  mini_alloc  mini_gc_abort  exit
macOS   : _main _mini_gc_init _mini_gc_root_end _mini_alloc _mini_gc_abort _exit

malloc 和 abort 由 gc_runtime.o 内部的 C++ 实现使用，不应再出现在生成汇编的直接调用列表中。

再运行：

1

./mini alloc examples/registers.lang

为什么 alloc 不接受 --target？因为目标平台只影响最后的外部符号拼写；结构化 IR、表示分类、活跃集、冲突图和 home 在两种目标上完全相同。

只在与目标匹配的平台链接。--target linux 不会在 macOS 上凭空提供 ELF 链接器，--target macos 也不会在 Linux 上提供 Mach-O 工具链。

练习 10：减少颜色，但不改变语义

在 src/compile/register_alloc.cpp 中找到：

1
2

const std::vector<std::string> registers{
    "%rbx", "%r12", "%r13", "%r14"};

临时只保留前两个寄存器，重新构建并运行：

1
2
3

make
./mini alloc examples/register_spill.lang
./mini run examples/register_spill.lang

预测后再观察：

• spill-count 应增加还是减少？
• root-bytes 会不会改变？
• 解释器结果会不会改变？
• 编译结果是否仍应为 210？

正确方向是：可用颜色减少会制造更多 ordinary spill，但表示分类和 root frame 不受影响，语言结果也不能改变。练习结束后恢复四个寄存器并重新 make。

练习 11：递归不是本地 CFG 回边

查看递归程序的 IR：

1

./mini ir examples/register_call_live.lang

递归发生在 call，不是一条跳回函数开头的 jump。因此这个例子验证了重复调用、ABI 和跨 call 活跃值，却不能单独证明本函数 CFG 中的 backward edge 分析正确。

思考：为什么活跃性实现仍采用“迭代到不再变化”，而不是依赖当前 lowering 恰好只生成向前分支？因为数据流算法应该服从 CFG，而不是把今天的 surface syntax 当作永久假设。将来若某个 lowering 产生回边，这套方程不需要改写。

练习 12：重新确认 OOM 不会变成 70

沿用第九章的可达 record 链：

1
2
3
4
5

(letrec build n
  (if (eq? n 0)
      (record)
      (record n (build (sub1 n))))
  (build 171))

把它保存为 oom.lang，生成并运行。深度 170 时所需 live bytes 为：

1

8 + 24 * 170 = 4088

能够放入 4096 字节半区；改成 171 后应进入 abort()。寄存器分配减少的是整数 roots，不会让仍然可达的 record 链凭空消失，也不能把固定堆耗尽改成语言错误状态 70。