冲突图与染色：谁不能共用寄存器

本节阅读量:

活跃性分析给了我们每条 IR 操作前后的集合，但还没有直接回答“t.0 应该放哪个寄存器”。冲突图把这些集合压缩成一个更适合分配的问题：

1
2


节点：一个确定为整数、需要 home 的 IR 名字
边：两个名字不能使用同一个机器寄存器

只要两个整数的生命周期重叠，它们之间就需要一条边。之后给图染色，就相当于给每个节点选择一个寄存器。

从一条定义产生冲突边

仍看本章主例子中间几行：

1
2
3
4


2  t.1 = record 0 0
3  t.2 = size t.1
4  check-integer t.2
5  t.3 = t.0 + t.2

第 3 条的 live_out 是：

1

{t.0, t.2}

这一条刚刚定义 t.2，而旧值 t.0 在它定义以后仍然活着。因此 t.2 不能覆盖 t.0 的寄存器：

1

t.0 -------- t.2

第 4 条 integer_check 只使用 t.2，不定义新节点，所以它不会单独产生冲突边。它的 use 仍会进入 liveness，因而可能间接影响更早 definition 的边。第 5 条定义 t.3 时，live_out 只有最终结果 t.3 自己，没有别的整数与它冲突。因此 t.3 可以复用 t.0 或 t.2 的寄存器。

一般规则是：

1
2


如果操作定义整数 d，
那么 d 与 live_out 中每个不同的整数 v 冲突。

为什么看 live_out 而不是 live_in？因为 d 是本条操作执行后才产生的。只有执行后仍需保留的旧值，才会和新定义的 d 同时存在。

图中只放确定为整数的值

实现先为每个 integer 值创建节点：

1
2
3
4
5


for (const auto& name : allocation.value_order) {
    if (allocation.value_classes.at(name) == ValueClass::integer) {
        allocation.interference[name];
    }
}

随后遍历 IR definitions 和 live_out：

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


for (std::size_t index = 0; index < body.ops->size(); ++index) {
    const auto& op = body.ops->at(index);
    if (op.dst.empty()) {
        continue;
    }
    auto dst_class = allocation.value_classes.find(op.dst);
    if (dst_class == allocation.value_classes.end() ||
        dst_class->second != ValueClass::integer) {
        continue;
    }

    for (const auto& live : allocation.live_out[index]) {
        auto live_class = allocation.value_classes.find(live);
        if (live == op.dst ||
            live_class == allocation.value_classes.end() ||
            live_class->second != ValueClass::integer) {
            continue;
        }
        allocation.interference[op.dst].insert(live);
        allocation.interference[live].insert(op.dst);
    }
}

边要双向插入，因为“t.0 不能和 t.2 共用”与“t.2 不能和 t.0 共用”是同一件事。

root 值不进入这张图。它们已经按固定顺序得到各自的 shadow root slot，本章不做 root slot 复用。这样既保持第九章 GC 规则，又让冲突图只回答一个清晰问题：确定整数怎样分享有限的普通机器位置。

用 `alloc` 观察冲突边

运行：

1

./mini alloc examples/register_alloc_live.lang

图染色就是选择寄存器编号

假设有四个颜色：

1
2
3
4


color 0 -> %rbx
color 1 -> %r12
color 2 -> %r13
color 3 -> %r14

一条边两端不能同色。不相邻的节点可以同色，也就可以共享同一个寄存器。

寻找最少颜色的一般图染色是困难问题，但编译器不需要为每个程序找到数学上的最优解。当前实现使用一个容易理解、结果稳定的贪心策略：

先处理邻居更多的节点；
度数相同时保持 IR 名字的原始顺序；
查看已经着色的邻居占用了哪些颜色；
选择第一个仍可用的颜色；
四种颜色都不可用时，把当前整数 spill 到机器栈。

排序代码是：

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


std::stable_sort(
    color_order.begin(), color_order.end(),
    [&](const std::string& lhs, const std::string& rhs) {
        std::size_t lhs_degree =
            allocation.interference[lhs].size();
        std::size_t rhs_degree =
            allocation.interference[rhs].size();
        if (lhs_degree != rhs_degree) {
            return lhs_degree > rhs_degree;
        }
        return original_order.at(lhs) < original_order.at(rhs);
    });

“度数高的先处理”是一种朴素启发式：约束更多的节点更难放，先为它们选择颜色，往往比完全按生成顺序更少 spill。它不是最优性保证，但足够建立一条完整、正确且可观察的教学路径。

四个候选寄存器

真实候选表只有四项：

1
2


const std::vector<std::string> registers{
    "%rbx", "%r12", "%r13", "%r14"};

它们都是 System V x86-64 ABI 的 callee-saved register。调用者可以假定被调函数返回后这些寄存器仍保持原值；相应地，每个生成函数必须在入口保存、出口恢复它们。

emitter 的函数序言包含：

1
2
3
4
5
6
7


out_ += "    pushq %rbp\n";
out_ += "    movq %rsp, %rbp\n";
out_ += "    pushq %rbx\n";
out_ += "    pushq %r12\n";
out_ += "    pushq %r13\n";
out_ += "    pushq %r14\n";
out_ += "    pushq %r15\n";

退出时按相反顺序恢复。当前实现无论某个 body 实际用了几个候选寄存器，都统一保存这四个寄存器；这不是最省指令的策略，却让调用约定简单而明确。

为什么不把更多寄存器加入颜色表？因为它们已经承担其他职责：

%r15 保存 shadow root stack top；
%rbp 和 %rsp 管理机器栈 frame；
%rdi、%rsi 传递 closure、argument 和分配器参数；
%rax 承接结果，并作为大多数指令的 scratch；
%rcx、%rdx 和 %r11 用于 tag 检查、对象地址和间接 call。

尤其是 %rax、%rcx、%rdx、%rdi、%rsi、%r11 都属于 caller-saved 一侧，普通 call 可以改写它们。若把活整数长期分配到这些寄存器，就必须额外为每个 call 建立物理寄存器冲突或保存恢复逻辑。

本章选择 callee-saved 候选，使活整数天然能跨过源语言 call 和 GC allocator call。代价是候选只有四个，因而更容易出现 spill；这也正好让读者完整看到寄存器不足时的处理路径。

着色与 spill 的真实循环

分配器依次查看每个节点已经着色的邻居：

 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


std::map<std::string, int> colors;
std::size_t next_spill = 0;
for (const auto& name : color_order) {
    std::set<int> unavailable;
    for (const auto& neighbor : allocation.interference[name]) {
        auto color = colors.find(neighbor);
        if (color != colors.end() && color->second >= 0) {
            unavailable.insert(color->second);
        }
    }

    int color = 0;
    while (color < static_cast<int>(registers.size()) &&
           unavailable.find(color) != unavailable.end()) {
        ++color;
    }

    if (color < static_cast<int>(registers.size())) {
        colors[name] = color;
        allocation.homes[name] =
            {HomeKind::machine_register, registers[color], 0};
    } else {
        colors[name] = -1;
        int offset =
            -48 - static_cast<int>(next_spill * kWordSize);
        allocation.homes[name] =
            {HomeKind::spill_slot, "", offset};
        ++next_spill;
    }
}

每个 spilled integer 都得到独立 slot。第一个从 -48(%rbp) 开始，是因为 -8 到 -40 对应序言保存的 %rbx、%r12、%r13、%r14 和 %r15。后面的 spill 依次使用 -56(%rbp)、-64(%rbp) 等位置。

spill 仍然是 tagged integer，算术语义没有改变。区别只是 emitter 需要从内存 home 取值，再通过 scratch register 生成合法的 x86-64 指令。

一个确定会 spill 的例子

examples/register_spill.lang 先产生十个都要留到后面的和，再逐层相加：

1
2


./mini run examples/register_spill.lang
./mini alloc examples/register_spill.lang

解释器输出：

1

210

values 开头会显示：

1
2
3
4
5
6


t.0 : integer -> register %rbx
t.1 : integer -> register %r12
t.2 : integer -> register %r13
t.3 : integer -> register %r14
t.4 : integer -> spill -48(%rbp)
t.5 : integer -> spill -56(%rbp)

汇总是：

1

root-bytes=0 spill-count=11

这不表示程序只有四个整数能运行。它只表示任一时刻最多有四个互相冲突的整数使用候选寄存器，其余值拥有普通机器栈 home。稍后一些旧值死亡后，新的结果又会重新使用 %r14、%r13、%r12 和 %rbx。

活整数可以跨过会触发 GC 的调用

examples/register_call_live.lang 专门保留六个整数，再调用一个会反复分配 record 的递归函数，最后继续使用这些整数：

1
2


./mini run examples/register_call_live.lang
./mini alloc examples/register_call_live.lang

解释器结果是 42。main 的分配开头包含：

1
2
3
4
5
6


t.16 : integer -> register %rbx
t.17 : integer -> register %r12
t.18 : integer -> register %r13
t.19 : integer -> register %r14
t.20 : integer -> spill -48(%rbp)
t.21 : integer -> spill -56(%rbp)

这些值在 call 的 live_out 中继续存活。四个寄存器属于 callee-saved，两个 spill slots 属于 caller 自己的 frame，所以被调函数和其中的多轮 GC 都不会破坏它们。

与此同时，callee、cell 和 call 返回值仍按 root 规则放在 shadow root slots。这个例子把统一后端最重要的分工放在了一起：

1
2
3


确定整数跨 call       callee-saved register 或普通 spill
可能的堆引用跨 GC     shadow root slot
对象操作的短暂地址     scratch register

染色正确性比少 spill 更重要

当前贪心算法可能不是最优的；换一种节点顺序，也许能少用几个 spill slot。但无论是否最优，必须始终满足：

1

冲突边两端的值不能分到同一个机器寄存器。

不相邻的值分到同一寄存器是有意复用，不是错误；寄存器不够而 spill 也不是失败。只要 homes 覆盖所有名字、冲突约束成立、root 值仍由 GC 扫描，生成程序的语义就应与解释器一致。

下一节会继续沿着 homes 走到最终汇编，具体解释普通 spill slot、root slot、scratch register、frame 对齐和内存操作限制怎样一起落地。

10.3 活跃性：这个值以后还会不会用

10.5 三种 home：寄存器、普通 spill 与 GC root

本节目录