本章完成后的能力与验收

第九章不增加表面语法。它的完成标准是：第八章正常程序的结果语义和已经规定的受控错误继续成立，同时编译结果不再依赖“对象永远不移动、永远不释放”这个假设。

下面的清单既是章节边界，也是修改代码时可以重复执行的验收标准。

累积语言能力不能回退

这一快照继续支持：

• 正整数、零和负整数；
• + 与 sub1；
• let、词法作用域和遮蔽；
• eq? 与 if；
• 一元 lambda、一元调用和 letrec；
• 零字段或任意字段数的 record；
• record?、size 和带边界检查的 get；
• set! 与恰好两个表达式的 begin；
• closure 共享 cell，以及可修改的递归 self cell。

普通 identifier 仍然只能是一个或多个英文字母。sub1、eq?、record? 和 set! 只是 parser 在列表头识别的固定特殊拼写。

对正常程序以及后端已经承诺检查的动态错误，解释器和编译器必须保持同一套可观察语义：

• 只有整数 0 为假；
• record 按对象身份比较；
• closure 不能参加 eq?；
• call 先求 callee、检查 callee，再求 argument；
• set! 先解析已有 Location，再求 RHS，并返回写入的值；
• 未选择的 if 分支不执行；
• letrec 的函数体、外层 body 和逃逸 closure 共享同一个 self cell。

第四章末尾用于 ABI 联调的 (cin) 与 (cout expr) 不属于本章快照。本章没有通用输入输出或 FFI。

解释器边界

mini run 继续使用 C++ 解释器：

1

name -> integer Location -> Store 中的 Value

解释器不调用 mini_alloc，也不执行 gc_runtime.o 中的 collector。它的职责是给出语言语义基准；GC 是编译后程序的运行时机制。

因此同一个压力程序的两条路径验证的是不同事情：

1

./mini run examples/gc_live_record.lang

检查解释器语义，输出：

1

42

而生成、链接后的程序检查 root 与搬移协议，最终用进程状态返回 42。

编译链要求

编译路径必须保持：

1

AST -> structured IrProgram -> assembly emitter

IrProgram 继续由 OperandKind、OpKind、Op 和 IrFunction 表示。汇编器不能绕过它直接消费 AST，也不能把 IR 退回需要重新解析的字符串列表。

必须保持以下既有顺序：

• check-closure 位于 argument operations 之前；
• branch 的 false edge 跳到 else，true edge fall through 到 then；
• begin 的第一项操作先于第二项；
• record 字段从左到右求值；
• set! 的 RHS 成功以后才执行 store。

compile 只输出 x86-64 System V ABI 的 AT&T 汇编，不调用 c++，也不负责链接可执行文件。第九章的生成汇编可以引用 mini_gc_init、mini_gc_root_end、mini_alloc 和 mini_gc_abort；这些 C ABI 符号由同章构建出的 gc_runtime.o 在链接时提供。

堆对象协议

record、closure 和 cell 必须共用 heap-object pointer tag 4，再由 header kind 区分：

header 公式保持：

1

header = (payload_count << 8) | kind

所有对象 8 字节对齐。closure offset 8 的 raw code pointer 计入大小但不参与扫描；record 字段、closure captures 和 cell offset 8 的当前 Value 都是对象图中的边。

空 record 只有一个 8 字节 header。forwarding 方案必须只占旧 header word，不能假设对象至少有一个 payload。

root 与 safepoint 要求

generated code 使用 1 MiB shadow root stack，%r15 保存当前 top。每个 IR 名字拥有固定 root home，函数进入时建立自己的 root frame，退出时恢复调用者的 top。

root 管理必须满足：

• 新槽先初始化为 tagged 0；
• 参数、self cell 和 captures 在函数第一次分配前进入 roots；
• 分配前仍然活跃的字段、初值和 captures 位于 roots；
• mini_alloc 返回后，从可能已更新的 root home 重新读取指针；
• allocation 和可能继续分配的源语言 call 都按 safepoint 处理；
• 未扫描的 scratch register 不能成为堆指针跨 safepoint 的唯一保存位置。

清根不能只依赖 IR 文本中的“最后一次出现”。后端需要在控制流图上反向计算 root liveness：

1
2

live_out(op) = 所有后继 live_in 的并集
live_in(op)  = uses(op) ∪ (live_out(op) - defs(op))

具体要求是：

• branch 同时考虑 then 和 else 两个后继；
• jump 使用目标 label 作为后继；
• allocation 类操作在调用 mini_alloc 前清除不属于该操作 live_in 的 roots；
• call 先把 callee、argument 和 raw code address 装入约定寄存器，再在真正的间接调用前清除不属于 live_out 的 caller roots；
• 没有 safepoint 的普通操作和 label 不需要为了 GC 立即清根。

call 的规则不会让 callee 或 argument 丢失：从清 caller roots 到进入被调函数之间没有 safepoint；被调函数又会在第一次分配前把参数与 captures 放进自己的 root frame。完全未使用的参数、self metadata 或 captures 最迟会在下一个 safepoint 因不属于 live_in/live_out 而被清除。

本章仍给每个 IR 名字分配固定 home，不复用 slot，不构建冲突图，也不做寄存器分配。CFG liveness 在这里仅用于在 safepoint 准确收紧 GC roots。

collector 要求

src/runtime/gc.cpp 必须用 C++ 实现分配器和 collector，并通过 gc.h 中的 extern "C" 声明只暴露生成代码所需的窄接口。运行时必须：

• 分配两个各 4096 字节的 semispace；
• 使用 bump pointer 完成正常分配；
• 空间不足时从 shadow roots 发起 collection；
• 转发并原地更新每个 root slot；
• 按 header 扫描 record、closure 和 cell；
• 跳过 closure 的 raw code pointer；
• 用 forwarding 保持共享对象身份；
• 正确结束 closure 与 cell 构成的环；
• 完成 Cheney 扫描后交换两个半区；
• collection 后重试一次分配；
• 仍然放不下时调用 abort。

运行时还要检查 malloc 失败、root top 越界、请求未对齐、对象越过已分配区间、未知 kind 和 to-space 溢出。

collect 与 forward 应保留为 runtime 内部函数，不成为 IR op 或生成汇编必须调用的入口。make 必须同时生成宿主工具 mini 和目标 runtime object gc_runtime.o，并确保后者与生成汇编使用同一目标架构。

九个 GC 验收示例

本章在完整继承第八章 77 个示例的基础上增加 9 个 GC 示例，总计 86 个 .lang 文件：

先验证解释器：

1
2
3
4
5
6
7
8
9

./mini run examples/gc_stress.lang
./mini run examples/gc_live_record.lang
./mini run examples/gc_empty_record.lang
./mini run examples/gc_record_identity.lang
./mini run examples/gc_closure_cell.lang
./mini run examples/gc_record_closure.lang
./mini run examples/gc_caller_live.lang
./mini run examples/gc_branch_liveness.lang
./mini run examples/gc_call_liveness.lang

前七个结果如表所示：identity 示例输出 1，其余六个输出 42。最后两个解释器结果是 300；编译结果通过进程状态观察时按 8 位截断，因此是 300 mod 256 = 44。

再任选结果为 42 的程序验证编译路径：

1
2
3
4

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

状态应为：

1

42

Apple Silicon Mac 的链接命令使用：

1

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

累积示例回归

GC 不能用“压力示例能运行”掩盖旧能力回退。至少还应运行：

1
2
3
4
5
6

./mini run examples/add.lang
./mini run examples/empty_record_size.lang
./mini run examples/record_get_third.lang
./mini run examples/counter.lang
./mini run examples/recursive_binding_set.lang
./mini run examples/self_param_shadow.lang

输出依次应为：

1
2
3
4
5
6

42
0
30
42
42
42

这些例子分别覆盖基础算术、空 record、变长 record、安全字段读取、共享状态和可变递归 self。

错误路径验收

解释器错误由 CLI 捕获，打印 error: 并返回状态 1：

1
2
3

./mini run examples/function_eq_error.lang
./mini run examples/record_get_bounds_error.lang
./mini run examples/set_undefined_error.lang

前两个属于可以生成运行时检查的动态错误。把它们或错误调用编译并链接后，程序应进入 exit(70)：

1
2
3
4

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

结果应为 70。

set_undefined_error.lang 不同：lowering 时就找不到赋值目标，因此 mini compile 本身返回状态 1，不会生成一份等待运行的错误程序。

GC 的 abort 不属于语言错误码 70。固定半区或固定 root stack 无法继续时，进程通常因信号终止；不同系统不保证相同 shell 状态。

本章明确不做什么

本章不实现：

• mark-sweep、分代、增量或并发 GC；
• 可扩展半区或可扩展 shadow root stack；
• finalizer、弱引用或手动释放；
• register root map；
• root slot 复用、冲突图、图染色或寄存器分配；
• 尾调用优化；
• 静态类型系统、异常或通用 FFI；
• record 字段修改或多表达式 begin。

本章也不借 GC 改造旧算术操作的全部动态类型检查。验收重点是：既有语言语义不回退，可达对象在搬家后仍然可用，不可达对象不再被无意义的 roots 长期保留。