第十章：寄存器分配

本节阅读量:

第九章已经有了一台完整的小语言机器：整数、函数、闭包、record、可变状态和 copying GC 都能沿着同一条编译路径运行。不过，为了让 GC 总能找到活对象，那一章给每个 IR 临时值都准备了一个 shadow root slot。这样做很安全，也很容易解释，却没有利用 CPU 最擅长访问的存储位置——寄存器。

第十章不增加任何源语言语法。我们只改变编译器后半段回答问题的方式：

1

一个 IR 临时值在机器上应该住在哪里？

完整路径现在是：

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


source
  |
  v
AST -----------------------------> interpreter -> Value
  |
  v
structured IrProgram
  |
  v
representation classification
  |
  v
CFG liveness -> interference graph -> home allocation
                                      |
                                      v
                         x86-64 AT&T assembly --+
                                                 +-> executable
                         C++ GC runtime object --+

这里没有“纯整数走一个后端，堆对象走另一个后端”的分叉。无论程序里有没有 closure、record、cell、函数调用或 GC，compile 都先生成同一个 IrProgram，再经过同一套表示分类、活跃性分析和 home 分配。

先看一个同时用到寄存器和堆的程序

本章的主例子是 examples/register_alloc_live.lang：

1
2


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

左边算出 40，右边创建一个二字段 record，再用 size 得到 2，所以整个程序的结果是 42。

先走解释器路径：

1
2
3


cd code/10_registers
make
./mini run examples/register_alloc_live.lang

这里的 make 同时构建 mini 和稍后链接原生程序所需的 gc_runtime.o。

输出：

1

42

语言语义没有变化。解释器并不知道 %rbx、spill 或 root slot；它仍然按照前几章建立的规则递归求值，最后得到动态 Value。

`IrProgram` 也没有换掉

运行：

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

这仍是第九章延续下来的结构化 IR。每个 t.* 都只是一个尚未决定机器位置的名字：它可能进入寄存器，也可能进入普通 spill slot 或 GC root slot。

两条 check-integer 是显式的动态检查操作。lowering 先求左操作数，立刻检查它，再开始求右操作数；右操作数求完也立即检查，最后才执行 add。这样，如果左边不是整数，右边可能包含的函数调用、分配或 set! 都不会抢先执行，编译器与解释器的左到右求值顺序保持一致。19、21 这类整数字面量在编译期已经确定合法，所以内层加法不需要额外 check。

第十章新增的 alloc 命令专门把这一步决定打印出来：

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

现在先抓住三个现象：

t.0、t.2 和 t.3 都能确定是整数，因此可以参加寄存器分配。
t.1 是 record 引用，必须拥有一个 GC 可以扫描和更新的 root slot。
t.0 与 t.2 同时活跃，所以它们分别住进 %rbx 和 %r12；t.3 产生时 t.0 已经死去，因此又能使用 %rbx。

这正是本章要建立的直觉：home 属于一段值的生命周期，而不是永远绑定给某个源码变量。

三种 home

本章统一后端会产生三种 home：

home	保存什么	当前实现中的样子
machine register	编译器已经确定为整数的值	`%rbx`、`%r12`、`%r13`、`%r14`
spill slot	确定为整数、但寄存器放不下的值	`-48(%rbp)` 等机器栈位置
root slot	堆引用或无法排除堆引用的动态值	`-8(%r15)` 等 shadow root 位置

root slot 不是另一种 spill。普通 spill 只保存确定的整数，collector 不需要扫描它；root slot 则属于第九章的 shadow root stack，copying collector 会在搬移对象后原地更新其中的指针。

同样，对象“分配在堆上”不等于对象引用一刻也不能进入寄存器。生成字段访问代码时，后端可以暂时把 tagged pointer 装进 %rax 或 %rcx。真正的约束是：可能的堆指针不能只待在未扫描的 scratch register 里跨过 GC safepoint。

编译并观察机器代码

生成汇编：

1

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

compile 仍然只输出 x86-64 System V ABI 的 AT&T 汇编，不会替你调用 c++。第九章引入的 C++ GC runtime 继续单独构建为 gc_runtime.o；在输出中可以找到这样的片段：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


# t.0 写入 %rbx 后立即执行第一条 check-integer
movq %rax, %rbx
movq %rbx, %rax
movq %rax, %rcx
andq $7, %rcx
cmpq $1, %rcx
jne .Lruntime_error

# 通过检查以后，才开始创建右操作数中的 record
# t.1 的 record 引用拥有 root home
movq %rax, -8(%r15)

# t.0 在 %rbx，t.2 与它冲突，所以使用另一个寄存器
movq %rax, %r12

# t.2 产生后立即执行第二条 check-integer
movq %r12, %rax
movq %rax, %rcx
andq $7, %rcx
cmpq $1, %rcx
jne .Lruntime_error

# 两个操作数都已检查，add 本体只负责 tagged arithmetic
# 两个 tagged integer 相加会多出一个 tag 1，减去 1 才得到正确编码
movq %rbx, %rax
addq %r12, %rax
subq $1, %rax

# t.3 可以重新使用已经死亡的 t.0 所在的 %rbx
movq %rax, %rbx

这里没有把 tagged word 当作普通整数直接相加。对 a_tagged + b_tagged 来说，两个低位 tag 会相加成 2，所以 subq $1, %rax 把结果恢复成低位 tag 1。动态 guards 由前面的两条 integer_check 生成；它们既保留运行时错误行为，也把检查放在正确的求值时刻。

链接并运行：

1
2
3


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

如果你在 Apple Silicon Mac 上运行，需要显式要求 c++ 生成 x86-64 可执行文件：

1
2
3


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

程序本身不打印内容，最后一行应看到进程结束码：

1

42

这和解释器输出的 42 是同一个语言结果，只是观察方式不同。

完整语言仍然走这条路径

再试一个第九章的 GC 示例：

1
2
3


./mini run examples/gc_live_record.lang
./mini alloc examples/gc_live_record.lang
./mini compile examples/gc_live_record.lang -o gc.s

第一条命令输出 42。第二条命令不会显示“回退到另一个后端”，而是同时打印 main 和 lambda0 的分类、活跃集合与 homes；第三条命令仍由同一个汇编 emitter 处理 closure、record、cell 和 safepoint。

因此，第十章优化的是值的机器位置，而不是缩小语言范围。前九章已经实现的行为都必须继续成立。

这一章要回答什么

接下来会依次解决这些问题：

动态语言里，“确定为整数”究竟是什么意思？
为什么保守分类成 root 不等于断言它一定是堆指针？
为什么整数动态检查要成为独立 IR op，而不能等 rhs 也求完后再做？
结构化 IR 怎样同时服务 CFG 分析、GC 和寄存器分配？
live_in 与 live_out 怎样告诉我们两个值是否同时存在？
冲突图怎样把“不能共用”变成一条边？
为什么当前实现选择 %rbx、%r12、%r13 和 %r14？
四个寄存器不够时，整数怎样 spill 到机器栈？
root slot、普通 spill slot 和 scratch register 的职责怎样分开？

学完这一章，你看到的将不再是“每个临时量固定占一个栈槽”，而是一条能在完整动态语言、函数调用和 GC 之间保持正确性的统一后端。

9.8 常见错误与练习

10.1 本章边界：不改语言，只改变值的家

本节目录