本章实现要求

本节阅读量:

第十章不增加源语言语法。它重做的是从第九章结构化 IR 到最终汇编的后半段：完整语言只经过一套表示分析、活跃性分析、home 分配和 assembly emitter。

这一章完成后，下面四条命令必须都走通：

1
2
3
4


./mini run examples/registers.lang
./mini ir examples/registers.lang
./mini alloc examples/registers.lang
./mini compile examples/registers.lang -o out.s

alloc 对 record、closure、函数调用、可变 cell 和 GC 压力程序同样有效。完整语言共同经过这一条分配路径。

继承要求

第九章已经支持的能力不能因为后端变化而丢失：

整数、负整数、加法和 sub1；
词法作用域、遮蔽、let、条件与 eq?；
一元函数、递归、函数值和闭包；
空及变长 record、record?、size 与带边界检查的 get；
set!、begin、共享可变 cell 和可修改的递归 self；
统一 heap-object tag、Cheney copying collector 和 shadow root stack；
callee 先检查、再求 argument 的调用顺序；
算术先求并检查 lhs、再求并检查 rhs 的从左到右错误顺序；
then 紧跟条件跳转、false 跳向 else 的既有块布局；
动态错误、GC abort 和正常结果之间已有的协议。

前端和解释器继续保持第九章接口；结构化 IrProgram 保留所有既有操作，只新增用于固定算术错误顺序的 integer_check，不能退回字符串 IR。汇编生成入口仍然消费 IR：

1
2


std::string compile_to_assembly(const IrProgram& program,
                                Target target);

不能从 AST 另建一条“方便分配寄存器”的编译路径。

表示分析要求

源语言仍是动态类型语言。这里的 integer 是编译器对某个 IR 结果作出的保守证明，不是给用户增加静态类型。

最低要求如下：

定义来源	分类
`add`、`sub1`、`equal`	`integer`
`record_predicate`、`record_size`	`integer`
`cell`、`record`、`closure`	`root`
`load`、`field`、`call`	`root`
`copy`	继承输入分类
多个分支给同一名字赋值	对所有到达定义求保守合并

若所有定义都确定为整数，合流结果可以继续分类为 integer；只要有一路可能产生堆引用，就必须分类为 root。分析无法证明的 unknown 最终也必须降为 root，不能凭运行示例的偶然结果猜成整数。

integer_check 不定义结果，因此不属于上表的定义来源，也不产生新的表示分类或 home。它使用被检查的 operand，把动态错误发生的位置显式保存在 IR 中。

CFG 活跃性要求

每个主程序和函数体都要独立计算 live_in 与 live_out：

1
2


live_out[n] = 后继 live_in 的并集
live_in[n]  = use[n] ∪ (live_out[n] - def[n])

后继关系必须来自 CFG：

普通 op 的后继是下一条；
jump 的后继只有目标 label；
branch 的后继是 then 和 else 两个 label；
函数结果作为虚拟 exit 的一次 use。

integer_check 的 lhs 必须进入 use 集合，dst 为空，所以没有 def。check 前仍活跃的其他值要原样保留，不能因为检查没有结果就把它当作可删除的空操作。

算法应迭代到集合不再变化，不能只按文本顺序反向扫描一次。活跃性既服务于整数冲突图，也继续服务于 allocation 和 call safepoint 的 root 清理。

冲突图与染色要求

冲突图只包含分类为 integer 的 Value。定义 dst 后仍在 live_out 中的另一个整数 Value 与 dst 冲突；边必须双向记录。

当前实现：

按冲突度从高到低稳定排序；
依次尝试 %rbx、%r12、%r13、%r14；
没有颜色可用时分配 ordinary spill slot；
不同时活跃的值可以复用同一机器寄存器。

每个有名字的 Value 最终必须恰好拥有一个 home。label、jump、store、integer_check 和其他 guard 等没有 dst 的操作不凭空获得 home。

三类 home 与 ABI 要求

分配结果必须明确区分：

1
2
3


integer -> register %rbx
integer -> spill -48(%rbp)
root    -> root -8(%r15)

寄存器和普通 spill 只保存确定整数；
普通 spill 由 %rbp 定位，不属于 GC roots；
可能为堆引用的 Value 始终拥有 %r15 root slot；
%r15 保留为 shadow root top，不能交给图染色；
%rbx、%r12、%r13、%r14 在每个生成函数中保存并恢复；
%rax、%rcx、%rdx、%r11 等 scratch register 不作为长期 home；
每次 call 前 %rsp 满足 x86-64 System V ABI 的 16 字节对齐要求。

若一个 tagged heap Value 为了读 header 或字段短暂进入 scratch register，这是允许的；但未被扫描的堆引用不能跨越 mini_alloc 或源语言 call。

GC safepoint 要求

第九章的两类 safepoint 继续保留：

cell、record、closure 分配调用 C++ runtime 的 mini_alloc；
源语言函数调用可能在 callee 中继续分配。

allocation 前按当前 op 的 live_in 清除死 root。源语言 call 必须先把 tagged callee、tagged argument 和 raw code address 装入约定位置，再按 live_out 清理 caller roots，最后发出间接 call。

整数若位于 %rbx、%r12、%r13 或 %r14，可以跨 safepoint 存活，因为这些寄存器按 ABI 由 callee 保存。spill 中的整数也位于 caller 的机器栈帧，callee 不会覆盖。堆引用则必须由 collector 扫描并在搬移后更新 root slot。

每个 root frame 在第一次 safepoint 前初始化为 tagged 0，函数退出时恢复进入前的 %r15。固定 root area 溢出和固定半区耗尽仍走 abort()，不能伪装成语言错误状态 70。

`alloc` 命令要求

1

./mini alloc <file>

至少要输出：

主程序及每个函数体的 Value 顺序；
integer 或 root 表示分类；
register、spill 或 root home；
每条 op 的 kind、完整 IR 操作、use、live_in 和 live_out；
整数冲突集合；
root-bytes 与 spill-count。

以下命令必须全部打印完整分析：

1
2
3
4


./mini alloc examples/registers.lang
./mini alloc examples/register_spill.lang
./mini alloc examples/gc_stress.lang
./mini alloc examples/counter.lang

六个本章专项示例

本目录完整继承第九章的 86 个示例，再增加 6 个寄存器分配示例，总计 92 个 .lang 文件：

示例	主要检查	`run` 结果	编译结果状态
`registers.lang`	表示分类、分支和寄存器复用	`10`	`10`
`register_spill.lang`	四个颜色不够时进入普通 spill	`210`	`210`
`register_alloc_live.lang`	整数跨 allocation safepoint	`42`	`42`
`register_call_live.lang`	寄存器及 spill 中的整数跨 call 和多轮 GC	`42`	`42`
`register_mixed_join.lang`	int/record 分支合流保守进入 root	`42`	`42`
`add_record_error.lang`	lhs 错误在 RHS 的 OOM 压力前退出	`error:`，CLI 状态 `1`	`70`

先检查示例数量：

1

find examples -name '*.lang' | wc -l

应看到 92。

再解释执行五个正常示例：

1
2
3
4
5


./mini run examples/registers.lang
./mini run examples/register_spill.lang
./mini run examples/register_alloc_live.lang
./mini run examples/register_call_live.lang
./mini run examples/register_mixed_join.lang

结果依次为：

分配输出还应满足：

register_spill.lang 为 root-bytes=0 spill-count=11；
register_alloc_live.lang 的 record 是 root，40 与 size 结果使用不同寄存器；
register_alloc_live.lang 的 IR 在 t.0 后立即检查 lhs，再 lower 右侧 record；t.2 后也先检查再加法；
register_call_live.lang 的 main 同时出现 register、spill 和 root 三类 home；
register_mixed_join.lang 的 branch 合流 Value 是 root。
add_record_error.lang 的 lhs check 排在递归构造 RHS record 链之前。

编译结果验收

在 Linux、WSL 或 Intel Mac 上，以一个正常程序为例：

1
2
3
4


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

状态应为 42。Apple Silicon Mac 使用：

1
2
3
4


./mini compile examples/register_call_live.lang -o out.s --target macos
c++ -arch x86_64 out.s gc_runtime.o -o out
./out
echo $?

register_spill.lang 的编译结果状态应为 210。这个数没有超过 shell 的 8 位退出状态范围，不需要取模换算。

动态错误验收

解释器会捕获求值错误、打印 error: 并让 mini run 返回状态 1：

1
2
3


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

第一条应包含：

1

error: addition left operand expected a number

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)))

lhs 是 record，必须立刻报告加法类型错误。若编译器先求完整 rhs 再统一检查两个操作数，(build 171) 会先构造一条仍然可达的 record 链，程序将错误地进入 GC abort。正确结果是直接进入语言错误状态 70，根本不执行 rhs。

lowering 用显式 integer_check 固定算术检查顺序。add 的顺序必须是：

1
2
3
4
5


lower lhs
check-integer lhs
lower rhs
check-integer rhs
add lhs rhs

sub1 在唯一操作数之后立即 check。若 operand 是整数字面量，lowering 可以省略已知必定成功的检查。emitter 只在 integer_check op 处生成 tag guard；检查失败时进入共同的 .Lruntime_error，再调用 exit(70)。

用本章主例子直接验收顺序：

1

./mini ir examples/register_alloc_live.lang

关键顺序应为：

1
2
3
4
5
6


t.0 = 19 + 21
check-integer t.0
t.1 = record 0 0
t.2 = size t.1
check-integer t.2
t.3 = t.0 + t.2

左侧 t.0 的检查排在整个右操作数之前，所以 lhs 类型错误会阻止 rhs 的运行时求值。受控错误的编译验收仍是：

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。这个程序把“lhs check 位于 rhs 之前”变成了可观察的永久回归：顺序正确就得到受控语言错误，顺序错误就会先耗尽堆。错误 call、函数 eq?、非法 size 和非法 get 也继续返回 70。

set_undefined_error.lang 不同：lowering 时就找不到目标绑定，因此 mini compile 自身返回 1，不会生成等待运行的错误程序。GC 初始化失败、root stack 溢出和堆耗尽则继续调用 abort()；这两类失败不能混为一谈。

第九章 GC 回归

至少重新验证九个 GC 专项示例：

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。编译结果通过进程状态观察时，300 mod 256 = 44。

还要保留第九章 OOM 边界：可达 record 链的深度 170 成功，171 进入 abort。寄存器分配减少整数 root，不得改变真正活跃的堆对象集合。

Linux 与 macOS 目标

同一份程序必须可以生成两种目标文本：

1
2


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

Linux 目标的生成汇编应引用：

1

main mini_gc_init mini_gc_root_end mini_alloc mini_gc_abort exit

macOS 目标应引用：

1

_main _mini_gc_init _mini_gc_root_end _mini_alloc _mini_gc_abort _exit

在对应的 x86-64 平台上，两份汇编都应能与同目标的 gc_runtime.o 链接和运行。malloc、abort 和 collector 内部状态属于 C++ runtime，不再直接出现在生成汇编中。--target 只改变符号拼写，不改变 IR、分配结果、GC 布局或 ABI，也不承诺宿主已经安装另一平台的交叉链接器。

非目标

本章不实现：

静态类型系统或用户类型标注；
caller-saved register 的 precolor/clobber 建模；
move coalescing；
基于执行频率的 spill cost；
复杂 spill rewrite；
root slot 着色或复用；
精确寄存器 root map；
逃逸分析或栈上分配 heap object。

这些优化都可以建立在当前分层上继续做，但不应破坏本章已经形成的一套统一后端和三类 home 的安全边界。

10.6 用 `alloc` 看见整个分配过程

10.8 常见错误与练习

本节目录