编译器变化：让活值拥有可更新的 root home

本节阅读量:

第九章没有增加源语言语法，也没有另造一套 GC 专用 IR。第八章结束时的 AST、解释器语义和结构化 IR 都原样保留：变量仍然通过 cell 读写，closure 仍然捕获 cell，record 仍然允许零个或任意多个字段。

真正改变的是 IR 之后的机器表示：

1
2
3
4
5


第八章
IrProgram -> malloc -> 永不移动的对象

第九章
IrProgram -> mini_alloc -> 可能被 collector 搬动的对象

对象一旦会移动，编译器就必须回答一个新问题：GC 发生时，怎样找到仍然有用的堆指针，并把它们改成搬家后的地址？

本章的答案是为 IR 临时量安排一块独立的 shadow root stack。每个临时量都有一个可扫描、可原地更新的 root home。后端仍然朴素，但从这一刻开始，值放在哪里已经不再只是汇编细节，而是内存安全协议的一部分。

编译路径仍然只有一条

CLI 的编译路径是：

1
2
3
4
5
6
7
8


source
  -> lexer
  -> parser
  -> AST
  -> lower_to_ir
  -> IrProgram
  -> compile_to_assembly
  -> x86-64 AT&T assembly

compile 先调用 lower_to_ir，再把同一个 IrProgram 交给汇编 emitter。它没有从 AST 直接生成另一份汇编。因此：

./mini ir 展示的 cell、load、store 确实是后端的输入；
callee 检查、条件分支和副作用顺序不会在另一条旁路中悄悄改变；
GC 只需要改变对象分配和 root 管理，不需要重新定义语言语义。

为了让这条协议始终一致，即使程序只有整数、根本不会创建堆对象，当前后端也会初始化 GC，并引用同一份 C ABI runtime。本章没有增加“这个程序是否需要托管堆”的分析，也没有为纯整数程序保留另一套后端；这点固定开销换来的是一条更容易理解和验证的编译路径。区别只在构建产物：emitter 写出 out.s，src/runtime/gc.cpp 单独编成 gc_runtime.o，最后由链接器把二者接起来。

例如：

1
2
3


cd code/09_gc
make
./mini ir examples/record.lang

实际输出仍然是结构化 IR 的文本展示：

1
2


t.0 = record 40 2
return t.0

record 是一个带 OpKind::record 的操作，不是一行供汇编器重新解析的字符串。

从 `malloc` 换成托管分配器

生成 Linux 符号拼写的汇编：

1

./mini compile examples/record.lang -o out.s --target linux

创建二字段 record 的真实片段是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


movq $24, %rdi
movq %r15, %rsi
call mini_alloc
movq $513, 0(%rax)
movq $321, %rcx
movq %rcx, 8(%rax)
movq $17, %rcx
movq %rcx, 16(%rax)
orq $4, %rax
movq %rax, -8(%r15)

和第八章相比，变化集中在调用分配器的三行：

寄存器	调用 `mini_alloc` 时的含义
`%rdi`	需要分配的字节数，这里是 `24`
`%rsi`	当前 shadow root stack 的顶部
`%rax`	返回的、尚未加 tag 的对象地址

后面的布局协议没有改变：header 513 来自 (2 << 8) | 1，字段 40 和 2 的 tagged 表示分别是 321 和 17，最终用共同的 heap-object tag 4 标记指针。

cell、closure 和 record 都走 mini_alloc：

1
2
3


cell bytes       = 16
closure bytes    = 8 * (2 + capture_count)
record bytes     = 8 * (1 + field_count)

这里的 closure 包含一个 header、一个 raw code pointer 和若干 capture。

为什么需要独立的 root stack

collector 会复制对象。假设一个 record 从地址 A 搬到地址 B，程序里仍然保存 A | 4 的位置都必须改成 B | 4。只知道“某个寄存器里好像有指针”是不够的；GC 需要一组明确、可写回的位置。

本章把两种栈分开：

1
2
3
4
5
6


机器栈 %rsp/%rbp
  保存返回地址、旧 frame pointer、旧 %r15

shadow root stack
  只保存 tagged Value
  由 %r15 指向当前顶部

%r15 是 System V ABI 中的 callee-saved register，普通函数调用必须保持它的值。这很适合保存跨调用存在的 root-stack top。

进入 main 时先初始化 GC，再为当前 IR body 申请 root frame：

1
2
3
4
5
6
7


call mini_gc_init
movq %rax, %r15
leaq 8(%r15), %rax
cmpq mini_gc_root_end(%rip), %rax
ja .Lmini_gc_abort
movq %rax, %r15
movq $1, -8(%r15)

mini_gc_init 在 %rax 中返回 shadow root stack 的起点。mini_gc_root_end 是 runtime 通过 C ABI 导出的边界变量；.Lmini_gc_abort 则只是生成文件内部的跳转目标，最终调用外部 mini_gc_abort()。这个 record.lang 只有一个 IR 临时量，所以 root frame 是 8 字节。-8(%r15) 就是 t.0 的 home。

新 root slot 先写入 1。这不是随便选的哨兵值，而是源语言整数 0 的 tagged 表示：

1

tagged(0) = 0 * 8 + 1 = 1

因此 collector 即使在临时量真正赋值前扫描这个槽，也只会看到一个合法的非指针 Value。

所有 IR 临时量先拥有 root home

汇编器会先遍历一段 ops，为以下内容分配 root slot：

函数的原始参数；
递归函数的 self cell；
closure 的普通 captures；
每个会产生 dst 的 IR 操作。

这是一条有意保守的规则。即使某个临时量只能装整数，它本章仍然先拥有 root home。collector 通过低位 tag 判断它是不是堆引用，因此整数放在 root stack 上不会被错误搬动。

第十章才会在表示分析之后，把确定为整数的值送进普通寄存器分配。第九章先保证一条更容易验证的规则：任何可能的堆指针跨过 safepoint 时，都能在 shadow root stack 中找到。

分配之后必须重新读取字段

考虑压力示例中的八字段 record：

1

(record n n n n n n n n)

它需要 72 字节。真实汇编先调用分配器，再从 root homes 读取字段：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


movq $72, %rdi
movq %r15, %rsi
call mini_alloc
movq $2049, 0(%rax)
movq -56(%r15), %rcx
movq %rcx, 8(%rax)
movq -64(%r15), %rcx
movq %rcx, 16(%rax)
# 其余六个字段同样从 -72(%r15) 到 -112(%r15) 读取
orq $4, %rax
movq %rax, -120(%r15)

这个先后顺序很重要。这里的八个字段恰好都是整数；但在一般的 record、cell 或 closure 分配中，mini_alloc 可能触发 collection，并更新字段或 capture 对应槽里的堆指针。若 emitter 在调用前把这类值放进一个未扫描的 scratch register，调用后继续使用旧地址，就会把悬空指针写进新对象。

可靠的顺序是：

1
2
3
4


1. 字段值先落到 root home
2. 调用可能触发 GC 的分配器
3. 从已经被 GC 更新过的 root home 重新读取字段
4. 初始化新对象

cell 的初值和 closure 的 captures 也遵守同一条规则。

只在 safepoint 前收紧 roots

“所有临时量都有 root home”保证了安全，却会带来另一个问题：已经没有用的对象若一直留在槽里，collector 仍会把它当成活对象。

gc_stress.lang 每轮创建一个随后丢弃的八字段 record。若对应 root slot 永远保留旧指针，这些临时 record 就都无法回收，固定 4 KiB 半区很快会被假活跃集塞满。

仅按 IR 文本中的“最后一次出现”清根也不可靠。控制流可能跳过那条清理：一个值只在 else 中使用，程序走 then 时就不会执行 else 路径里的最后一次使用。call 还有另一种假保活风险：callee 和 argument 若等到调用返回后才清除，会跨过被调函数中的所有 allocations。

后端因此先在 CFG 上反向计算 root liveness：

1
2


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

branch 有 then、else 两个后继，jump 的后继是目标 label，普通操作的后继是下一条操作。这样得到的是“从当前程序点继续执行，哪些 IR 名字仍可能被使用”，而不是简单的文本位置。

把公式落进 `assembly.cpp`

公式里的集合在代码中就是 NameSet，每条操作各有一份 live_in 和 live_out：

1
2
3
4
5
6


using NameSet = std::unordered_set<std::string>;

struct Liveness {
    std::vector<NameSet> live_in;
    std::vector<NameSet> live_out;
};

第一步是求一条操作读取了哪些名字。这里继续遵守全书的 kind + switch 约定，没有从 IR 打印文本中猜操作类型：

 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
31
32
33


NameSet used_names(const Op& op) {
    NameSet uses;
    switch (op.kind) {
    case OpKind::copy:
    case OpKind::cell:
    case OpKind::load:
    case OpKind::sub1:
    case OpKind::branch:
    case OpKind::closure_check:
    case OpKind::record_predicate:
    case OpKind::record_size:
    case OpKind::field:
        note_use(uses, op.lhs);
        break;
    case OpKind::store:
    case OpKind::add:
    case OpKind::equal:
    case OpKind::call:
        note_use(uses, op.lhs);
        note_use(uses, op.rhs);
        break;
    case OpKind::closure:
    case OpKind::record:
        for (const auto& field : op.fields) {
            note_use(uses, field);
        }
        break;
    case OpKind::jump:
    case OpKind::label:
        break;
    }
    return uses;
}

note_use 只把临时量 operand 加进集合，整数字面量没有名字，因此不会成为 root。操作写入的 op.dst 就是它的 defs；store、branch、jump 等没有结果的操作，其 dst 为空。

第二步是把线性的 ops 接成控制流图。代码先建立 label 到操作下标的映射，再按操作种类记录后继：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


switch (op.kind) {
case OpKind::branch:
    successors[index].push_back(label_index(op.target));
    successors[index].push_back(label_index(op.else_target));
    break;
case OpKind::jump:
    successors[index].push_back(label_index(op.target));
    break;
default:
    successors[index].push_back(index + 1);
    break;
}

最后一条普通操作的后继是虚拟的 exit_index。程序最终返回的 operand 在出口处仍然活着，否则分析可能在返回前的 allocation 把结果清掉：

1
2


NameSet exit_live;
note_use(exit_live, result);

最后从后向前反复应用方程，直到没有集合变化。new_out 合并所有后继，name != ops[index].dst 完成 live_out - defs：

 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


bool changed = true;
while (changed) {
    changed = false;
    for (std::size_t reverse = ops.size(); reverse > 0; --reverse) {
        const std::size_t index = reverse - 1;
        NameSet new_out;
        for (std::size_t successor : successors[index]) {
            const NameSet& successor_live =
                successor == exit_index
                    ? exit_live
                    : liveness.live_in.at(successor);
            new_out.insert(successor_live.begin(), successor_live.end());
        }

        NameSet new_in = used_names(ops[index]);
        for (const auto& name : new_out) {
            if (name != ops[index].dst) {
                new_in.insert(name);
            }
        }

        if (new_in != liveness.live_in[index] ||
            new_out != liveness.live_out[index]) {
            liveness.live_in[index] = std::move(new_in);
            liveness.live_out[index] = std::move(new_out);
            changed = true;
        }
    }
}

CFG 中即使有回边，这个过程也不会无限增长：集合中的名字来自有限个 IR 临时量，每轮只会把必要的名字传播到更多程序点，最终一定会稳定。递归调用在当前 body 中只是一条 call，callee 的 body 会单独分析，不需要做跨函数活跃性分析。

只在 safepoint 消费分析结果

清根不必发生在每条普通指令之后。没有 safepoint 时 collector 根本不会运行，root home 中暂时留着死值不会影响语义。本章只在真正可能触发或进入 GC 的位置收紧 roots。分配器调用使用当前操作的 live_in：

1
2
3
4
5
6
7


void emit_allocator_call(std::size_t bytes, std::size_t index) {
    clear_roots_not_in(liveness_.live_in.at(index));
    out_ += "    movq $" + std::to_string(bytes) + ", %rdi\n";
    out_ += "    movq %r15, %rsi\n";
    out_ += "    call " + runtime_label(target_, "mini_alloc") +
            "\n";
}

runtime_label 只处理目标文件的 C 符号拼写：Linux 得到 mini_alloc，macOS 得到 _mini_alloc。它不再生成或追加 allocator 的函数体。

源语言 call 则先把三个调用必需的值装进寄存器，再使用 live_out 收紧调用者的 roots：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


void emit_call(const Op& op, std::size_t index) {
    out_ += "    movq " + operand_text(op.lhs) + ", %rdi\n";
    out_ += "    movq %rdi, %rcx\n";
    out_ += "    andq $-8, %rcx\n";
    out_ += "    movq " + std::to_string(closure_code_offset()) +
            "(%rcx), %r11\n";
    out_ += "    movq " + operand_text(op.rhs) + ", %rsi\n";
    clear_roots_not_in(liveness_.live_out.at(index));
    out_ += "    call *%r11\n";
    store_result(op.dst);
}

clear_roots_not_in 先把 slots 按 offset 排序，让每次生成的汇编顺序稳定；真正决定清哪个槽的是下面这个循环：

1
2
3
4
5
6
7


for (const auto& [offset, name] : ordered_slots) {
    if (live.find(name) == live.end()) {
        out_ += "    movq $" +
                std::to_string(tagged_integer(0)) + ", " +
                std::to_string(offset) + "(%r15)\n";
    }
}

两处调用对应的规则可以缩写为：

1
2
3
4
5
6
7


allocation
  在调用 mini_alloc 前，只保留该操作 live_in 中的 roots

source call
  先把 closure、argument、raw code address 装入寄存器
  再只保留 call live_out 中的 caller roots
  最后执行间接 call

清除仍然是向 root home 写入 tagged 0：

1

movq $1, -offset(%r15)

allocation 的 operands 属于该操作的 live_in，所以字段、cell 初值和 closure captures 会保留到 allocator 返回，并能被原地更新。call operands 已经装入约定寄存器；从清 caller roots 到进入被调函数之间没有 safepoint，被调函数又会在第一次分配前把 argument 与 captures 放入自己的 root frame。

gc_caller_live.lang 专门检查 live_out 的另一面：调用者的 keep 在 churn 返回后还要读取，所以它的 root home 必须保留。churn 自己不捕获 keep，却会触发多轮 collection；若 call 前把所有 caller roots 都清掉，keep 的 home 会被写成 tagged 0，不再保存能由 collector 更新的 cell pointer，返回后的 load 就会解引用无效值。

本章仍然没有做 root slot 复用或寄存器分配：

每个 IR 名字始终有固定 root home；
CFG liveness 只决定 safepoint 时哪些 homes 应算作 roots；
dead value 在两个 safepoints 之间暂时留在 home 中是安全的；
真正危险的是在 safepoint 前清掉仍属于 live_in/live_out 的值。

函数入口先把参数和 captures 变成 roots

closure 调用约定仍然是：

寄存器	内容
`%rdi`	完整的 tagged closure Value
`%rsi`	完整的 tagged argument Value
`%rax`	完整的 tagged result Value

函数刚进入时，参数和 captures 还在寄存器或 closure 对象里。它必须在第一次分配前把这些值放进自己的 root frame。

counter.lang 内层函数开头的真实片段是：

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


movq %rsi, -8(%r15)
movq %rdi, %rax
andq $-8, %rax
movq 16(%rax), %rcx
movq %rcx, -16(%r15)
movq $1, -24(%r15)
movq $1, -32(%r15)
movq $1, -40(%r15)
movq $1, -48(%r15)
movq $1, -56(%r15)
movq $16, %rdi
movq %r15, %rsi
call mini_alloc
movq $259, 0(%rax)
movq -8(%r15), %rcx
movq %rcx, 8(%rax)

保存 argument 和读取 capture 的几行没有调用其他函数，所以不会触发 GC。它们先保存原始 argument，再从 closure offset 16 取出捕获的 start cell。紧接着的五行把不属于这次 allocation live_in 的其他 homes 初始化或重置为 tagged 0；argument 与 capture 两个 roots 保留下来。参数装箱所需的 mini_alloc 此时才能安全发生。

递归函数也遵守同一协议，只是 closure offset 16 对应 self cell，普通 captures 从 offset 24 开始。函数建立环境时仍让参数最后遮蔽同名 self；GC 没有改变词法作用域规则。

函数退出时恢复调用者进入前的 %r15，整个被调函数 root frame 随即离开扫描范围：

1
2
3


movq -8(%rbp), %r15
leave
retq

这和普通机器栈帧返回时失效的直觉相似，只是 root frame 位于另一块内存中。

普通源语言调用也是 safepoint

IR 仍然保持第七、八章规定的顺序：

1
2
3
4


callee operations
check-closure
argument operations
call

例如 gc_live_record.lang 的主程序结尾是：

1
2
3
4


t.22 = load loop1.cell
check-closure t.22
t.23 = call t.22 100
return t.23

check-closure 在 argument 之前出现。若 callee 不是函数，argument 中可能存在的分配或副作用都不会先发生。

间接调用的核心汇编仍是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


movq -40(%r15), %rdi
movq %rdi, %rcx
andq $-8, %rcx
movq 8(%rcx), %r11
movq $801, %rsi
movq $1, -8(%r15)
movq $1, -16(%r15)
movq $1, -24(%r15)
movq $1, -32(%r15)
movq $1, -40(%r15)
call *%r11

源语言 call 本身不直接调用 collector，但被调函数可能立刻分配，因此它也必须按 safepoint 对待。后端在真正 call 前按 CFG live_out 清掉不再需要的 caller roots；调用后仍会使用的值继续留在调用者 root frame 中。被调函数增加 %r15 后，collector 会扫描从 root stack 起点到新顶部的全部活动 frames，并原地更新其中的指针。

调用返回后，调用者不能相信调用前留在 scratch register 中的堆地址。后续操作继续从 root home 读取。

branch 仍然采用 then fallthrough

GC 没有引入基本块重排，也没有改变条件分支约定。结构化 IR 仍然让 branch 后紧跟 then block：

1
2
3
4
5
6
7


if t.2 goto then0 else else0
then0:
  # then operations
goto end0
else0:
  # else operations
end0:

汇编只显式跳向 false 分支：

1
2
3


cmpq $1, %rax
je .Lelse0
.Lthen0:

条件为真时继续向下执行 then；条件为假时跳到 else。后端没有增加基本块布局 pass，也不需要先生成双跳转再做窥孔优化。CFG liveness 只用于在后续 safepoint 判断 root，不改变这个物理布局约定。

动态错误协议不因 GC 扩大

汇编 emitter 继续实现已经规定的动态检查：

call 的 callee 必须是 closure；
closure 不能参加 eq?；
size 和 get 的输入必须是 record；
get 的字面量 index 必须小于 record 字段数。

这些错误进入共同的 .Lruntime_error，再调用 exit(70)。GC 内部不变量被破坏或固定内存耗尽则走另一条 abort 路径，下一节会区分它们。

本章没有借加入 GC 的机会扩大旧算术操作的动态检查范围。这里的目标只有一个：让第八章已有的语言和 IR 在对象会移动以后仍然正确运行。

到这里可以把编译器变化概括成一句话：IR 继续描述值怎样计算，汇编器额外保证每个跨 safepoint 的堆引用都有一个 collector 能找到并更新的 home。

9.4 forwarding 与 Cheney：搬一次，更新每一条边

9.6 C++ runtime：让汇编只负责交接

本节目录