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

活跃集、冲突边和 home 都是编译器内部事实。若只能盯着几百行最终汇编猜测，读者很难判断错误究竟发生在哪一步。因此第十章增加一个只用于观察的命令：

1

./mini alloc <file>

它会完成 parser、IR lowering、表示分析、活跃性和 home 分配，然后打印结果。它不会执行程序，不会生成 .s 文件，也不会调用工具链或链接器。

先构建本章代码：

1
2

cd code/10_registers
make

从一个跨 allocation 的整数开始

examples/register_alloc_live.lang 是：

1
2

(+ (+ 19 21)
  (size (record 0 0)))

左边先得到整数 40。求右边时要分配 record，因此左边结果必须跨越一次 mini_alloc；record 引用则必须留在 GC 可以更新的位置。

先看 lowering 怎样把算术检查放进 IR：

1

./mini ir examples/register_alloc_live.lang

1
2
3
4
5
6
7

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
return t.3

最里面的 (+ 19 21) 两项都是整数字面量，tag 在编译期已经知道，所以不需要生成检查。外层加法则先得到左操作数 t.0，立即执行 check-integer t.0，然后才开始 lowering 右操作数中的 record 和 size。这让运行时的左侧类型错误能够阻止右侧求值。右侧得到 t.2 后也先检查，最后才执行真正的加法。

运行：

1

./mini alloc examples/register_alloc_live.lang

当前输出为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

main:
  values:
    t.0 : integer -> register %rbx
    t.1 : root -> root -8(%r15)
    t.2 : integer -> register %r12
    t.3 : integer -> register %rbx
  flow:
    0 add [t.0 = 19 + 21] use={} in={} out={t.0}
    1 integer_check [check-integer t.0] use={t.0} in={t.0} out={t.0}
    2 record [t.1 = record 0 0] use={} in={t.0} out={t.0, t.1}
    3 record_size [t.2 = size t.1] use={t.1} in={t.0, t.1} out={t.0, t.2}
    4 integer_check [check-integer t.2] use={t.2} in={t.0, t.2} out={t.0, t.2}
    5 add [t.3 = t.0 + t.2] use={t.0, t.2} in={t.0, t.2} out={t.3}
  interference:
    t.0 : {t.2}
    t.2 : {t.0}
    t.3 : {}
  root-bytes=8 spill-count=0

不要急着一次读完。输出分成四段，每段回答一个问题。

values：它是什么，住在哪里

每行都包含 Value 名字、保守表示分类和最终 home：

1
2

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

t.0 是 (+ 19 21) 的结果，后端能证明它是整数，所以参加染色。t.1 是 record，必须进入 root slot。size 成功返回时一定是整数，因此 t.2 又能回到寄存器。

root 的意思是“必须按可能的堆引用保守处理”，并不承诺运行时一定是对象。例如 load、get 和函数调用的结果都可能在某次执行中恰好是整数，但当前分析不追踪 cell 内容、record 字段类型或函数返回类型，所以仍把它们放进 root slot。

flow：逐条检查 use、in 和 out

一条 flow 行形如：

1

3 record_size [t.2 = size t.1] use={t.1} in={t.0, t.1} out={t.0, t.2}

它表达的是：

• 方括号中是完整的 IR 操作，这一条定义 t.2；
• 执行它需要 t.1；
• 执行前 t.0 和 t.1 都活跃；
• 执行后 record t.1 已经用完，t.0 与新结果 t.2 仍活跃。

紧接着的一行是：

1

4 integer_check [check-integer t.2] use={t.2} in={t.0, t.2} out={t.0, t.2}

integer_check 使用已有的 t.2，但不定义新 Value，所以没有 dst，也不会获得新 home。它只把运行时检查固定在正确的求值位置；检查前后仍活跃的名字没有变化。

这也是检查 CFG 算法最直接的窗口。遇到 branch，它的 out 必须合并 then 与 else 两个后继；遇到 jump，后继是目标 label，而不是文本下一行。

interference：哪些整数不能共用寄存器

输出只为 integer Value 建图：

1
2
3

t.0 : {t.2}
t.2 : {t.0}
t.3 : {}

t.0 和 t.2 在最后一次加法前同时活跃，不能使用同一个寄存器。最终结果 t.3 定义时，两项输入都被消费了，所以它可以复用 %rbx。

root Value 不参加这张颜色图。它们由 root allocator 分配固定的 shadow-stack slot；缺席不是遗漏，而是另一类 home 的规则。

最后一行：一眼看出两块帧有多大

1

root-bytes=8 spill-count=0

这表示当前函数需要 8 字节 root frame，没有普通 spill。每个函数体单独分析和分配，所以带函数的程序会继续打印 lambda0:、lambda1: 等段落，各自有自己的统计。

例如：

1

./mini alloc examples/gc_stress.lang

会同时打印 main 和递归函数 lambda0。这里没有“切换到另一套后端”：完整语言的所有函数体都经过同一个分配器。

三个适合对照的命令

看寄存器复用

1

./mini alloc examples/registers.lang

这个程序的结果是 10。当前分配中多个不同时活跃的整数复用 %rbx，而由 let 产生的 cell 和保守的 load 结果位于 %r15 root slots。

看真正的 spill

1

./mini alloc examples/register_spill.lang

输出末尾应为：

1

root-bytes=0 spill-count=11

并能看到从 spill -48(%rbp) 开始的普通栈槽。

看分支合流的保守分类

1

./mini alloc examples/register_mixed_join.lang

程序中的 if 一边返回整数，另一边返回空 record。合流 Value 会显示为 root；随后的 record? 和加法结果则显示为 integer。

从 alloc 走到汇编

alloc 打印的是将要交给 emitter 的决定。用同一程序生成汇编：

1

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

在 out.s 中可以找到三类位置：

1
2
3
4
5
6
7
8

# 分配得到的整数 home
movq %rax, %rbx

# record 的 root home
movq %rax, -8(%r15)

# allocation safepoint
call mini_alloc

这里的具体指令会随 emitter 调整，但两条不变量不会变：可能的堆引用不能跨 safepoint 脱离 root slot；确定整数若在寄存器中跨 call，所在寄存器必须遵守 ABI 保存约定。

run 与编译结果观察的是同一语义

解释器直接打印 Value：

1

./mini run examples/register_alloc_live.lang

1

42

在 Linux、WSL 或 Intel Mac 上，生成并链接：

1
2
3
4

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

退出状态也应是 42。Apple Silicon Mac 要显式链接 x86-64 程序：

1
2
3

c++ -arch x86_64 out.s gc_runtime.o -o out
./out
echo $?

与前章一样，compile 只写出 x86-64 System V ABI 的 AT&T 汇编，不调用 c++，也不替读者运行结果。链接时必须带上本章 make 生成的 gc_runtime.o。若最终 Value 是整数，main 解码后把它作为进程退出状态；若最终是 record 或 closure，main 返回 0。

--target 不会改变分配

可以从同一份 IR 生成两种平台符号拼写：

1
2

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

Linux 生成汇编使用 main、mini_gc_init、mini_gc_root_end、mini_alloc、mini_gc_abort 和 exit；macOS 为这些外部符号增加前导下划线。malloc 与 abort 已封装在 gc_runtime.o 中，不再由 emitter 直接引用。表示分析、活跃集、冲突图、home 和函数调用协议完全相同；--target 不会产生第二套寄存器后端，也不会自动安装交叉链接工具链。