统一 pseudo 指令：分配器真正看到什么

本节阅读量:

前几章已经把 AST lowering 成结构化 IrProgram。第十章没有再造一套只支持整数表达式的指令选择器，而是直接把这份 IR 当作统一的 pseudo 指令流：

1
2


pseudo 的意思不是“字符串形式的假汇编”，
而是“操作已经明确，机器位置还没有决定”。

例如：

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

这里已经明确了运算、动态检查和分配的先后顺序，却没有说 t.0 应该放 %rbx 还是 -48(%rbp)。这种“名字无限、物理位置有限”的中间状态，正适合交给活跃性分析和寄存器分配。

IR 不是字符串列表

src/compile/ir.h 用显式 kind + switch 表达操作。操作数先区分整数立即数和 IR 临时名：

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


enum class OperandKind {
    integer,
    temp,
};

struct Operand {
    OperandKind kind = OperandKind::integer;
    long integer_value = 0;
    std::string temp_name;

    static Operand integer(long value);
    static Operand temp(std::string name);

    std::string dump() const;
};

Operand::integer(19) 是源语言整数 19，emitter 最终会把它编码成 tagged integer；Operand::temp("t.0") 则引用另一个 IR 操作定义的结果。

IR 操作也有明确的 kind：

 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


enum class OpKind {
    copy,
    cell,
    load,
    store,
    integer_check,
    add,
    sub1,
    equal,
    branch,
    jump,
    label,
    closure,
    closure_check,
    call,
    record,
    record_predicate,
    record_size,
    field,
};

struct Op {
    OpKind kind;
    std::string dst;
    Operand lhs;
    Operand rhs;
    std::string target;
    std::string else_target;
    std::size_t field_index = 0;
    std::vector<Operand> fields;
};

这些字段会根据 kind 承担不同职责。例如：

操作	定义	使用	额外信息
`integer_check`	无	`lhs`	立即检查一个已求值的动态 `Value`
`add`	`dst`	`lhs`、`rhs`	操作数已由前面的 check 验证
`cell`	`dst`	`lhs`	分配一个 cell
`store`	无	`lhs`、`rhs`	`lhs` 是 cell，`rhs` 是新值
`branch`	无	`lhs`	`target` 是 then，`else_target` 是 else
`closure`	`dst`	`fields`	`target` 是函数 label
`call`	`dst`	`lhs`、`rhs`	callee 和 argument
`record`	`dst`	`fields`	字段数可以为零或任意多个
`field`	`dst`	`lhs`	`field_index` 是字段下标

不用字符串解析操作名，后续每个 pass 都可以用 switch (op.kind) 完整覆盖所有情况。编译器新增一种 IR 操作时，编译器也会迫使我们检查表示分析、uses、汇编生成等消费者是否都已处理它。

main 与函数体使用同一种表示

主程序和 closure 函数体都由同样的 Op 列表组成：

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


struct IrFunction {
    std::string label;
    std::string param;
    std::string self_cell;
    std::vector<std::string> captures;
    std::vector<Op> ops;
    Operand result;
};

struct IrProgram {
    std::vector<Op> ops;
    Operand result;
    std::vector<IrFunction> functions;

    std::string dump() const;
};

result 单独保存在 body 末尾，而不是伪装成一条普通 OpKind::return。活跃性分析会把它当作 CFG 出口处的一次使用，保证最终结果不会在最后一个操作后被当成死值。

函数体比 main 多出三类入口值：

param：调用者传来的动态参数；
self_cell：letrec 递归绑定使用的 self cell；
captures：closure 从外层捕获的 cells。

它们都可能关联堆对象，因此表示分析从 root 开始。每个函数体分别计算自己的 CFG、冲突图、spill 数和 root frame 大小，但所有 body 都使用同一套分析代码。

从源程序看到统一 IR

再次运行本章主例子：

1

./mini ir examples/register_alloc_live.lang

源程序：

1
2


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

对应：

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

逐行看：

t.0 是两个整数字面量相加的结果。
第一条 check-integer 在开始求外层加法的右操作数之前检查 t.0。
t.1 是二字段 record 的 tagged pointer。
t.2 先检查 t.1 确实是 record，再取 header 中的字段数。
第二条 check-integer 立即检查刚产生的 t.2。
t.3 把两个已通过检查的 tagged integer 相加。
body 的 result 引用 t.3。

整数 19、21、0 和 0 是立即数，不需要各自分配 home；只有被名字引用的 t.0 到 t.3 进入 home 分配。integer_check 没有 dst，因此也不会凭空增加一个 home。

为什么整数检查必须进入 IR

如果只在最后生成 add 汇编时才连续检查两个操作数，lowering 就会先把 lhs 和 rhs 都求完。这会改变解释器的精确顺序：解释器在 lhs 求值后立即调用 expect_number，只有左边通过才会求 rhs。

因此 lowering 有一个小 helper：

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


void emit_integer_check(std::vector<Op>& ops,
                        const Operand& value) {
    if (value.kind == OperandKind::integer) {
        return;
    }
    ops.push_back({OpKind::integer_check,
                   "",
                   value,
                   Operand::integer(0),
                   "",
                   ""});
}

整数字面量一定使用 integer tag，可以直接省略检查。临时名则代表一个运行时 Value，需要生成显式 op。

add lowering 按语义顺序交错求值与检查：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Operand lhs = lower_expr(*add_expr.lhs, ops, env);
emit_integer_check(ops, lhs);
Operand rhs = lower_expr(*add_expr.rhs, ops, env);
emit_integer_check(ops, rhs);
std::string dst = new_temp();
ops.push_back({OpKind::add,
               dst,
               std::move(lhs),
               std::move(rhs),
               "",
               ""});

sub1 只有一个操作数，也是先 lower_expr，紧接着 emit_integer_check，最后才生成 OpKind::sub1。

汇编 emitter 也严格按这个分工处理：

1
2
3
4
5
6
7
8
9


case OpKind::integer_check:
    emit_integer_guard(op.lhs);
    return;
case OpKind::add:
    out_ += "    movq " + operand_text(op.lhs) + ", %rax\n";
    out_ += "    addq " + operand_text(op.rhs) + ", %rax\n";
    out_ += "    subq $" + std::to_string(kIntTag) + ", %rax\n";
    store_result(op.dst);
    return;

add 本体不再重复 guard；检查在 IR 中出现在哪里，它就在汇编中出现在哪里。这是“把语义顺序写进 IR”的一个具体例子：emitter 不必重新猜测一个 add 最初是怎样求值的。

主例子中的 t.0 和 t.2 之后都会被表示分析证明为 integer，但它们仍有显式 check。这是因为 lowering 发生在表示分析之前，它只看到一个 OperandKind::temp。当前章节不再加一个“删除已证明冗余检查”的优化 pass；多一次不会失败的 guard 影响效率，却不改变语义。

examples/add_record_error.lang 把顺序差异放大成一个回归测试。它最后计算：

1

(+ (record) (build 171))

左操作数显然不是整数，所以正确程序应立即进入语言错误路径，不应调用右边会构造长 record 链的 build。它的 main IR 中相关顺序是：

1
2
3
4
5
6
7


t.10 = record
check-integer t.10
t.11 = load build0.cell
check-closure t.11
t.12 = call t.11 171
check-integer t.12
t.13 = t.10 + t.12

正确实现在第二行就以状态 70 结束。如果错误地先求 rhs，build 171 会先把固定半区的活集撑满并进入 GC abort。这说明 integer_check 的 IR 位置是语义正确性，不只是汇编风格。

分配器先把不同 body 变成同一种视图

register_alloc.cpp 内部用一个只读 BodyView 统一 main 和函数体：

1
2
3
4
5
6
7
8


struct BodyView {
    std::string label;
    const std::vector<Op>* ops;
    const Operand* result;
    const std::string* param;
    const std::string* self_cell;
    const std::vector<std::string>* captures;
};

main 没有参数、self cell 和 captures，所以对应指针是 nullptr；IrFunction 则把这些入口值一并交给分析。后面的 ordered_names 先收集入口值，再按 IR 顺序收集每个 dst 和 use，最后补上 body result。

保持顺序有两个教学上的好处：

alloc 输出和 IR 的阅读顺序相近；
冲突度数相同时，图染色可以用原始顺序稳定地打破平局。

表示分类怎样落到 `switch`

上一节给出了分类规则。真实实现把它们集中在 definition_class：

 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


AnalysisClass definition_class(
    const Op& op,
    const std::map<std::string, AnalysisClass>& classes) {
    switch (op.kind) {
    case OpKind::copy:
        return operand_class(op.lhs, classes);
    case OpKind::add:
    case OpKind::sub1:
    case OpKind::equal:
    case OpKind::record_predicate:
    case OpKind::record_size:
        return AnalysisClass::integer;
    case OpKind::cell:
    case OpKind::load:
    case OpKind::closure:
    case OpKind::call:
    case OpKind::record:
    case OpKind::field:
        return AnalysisClass::root;
    case OpKind::store:
    case OpKind::integer_check:
    case OpKind::branch:
    case OpKind::jump:
    case OpKind::label:
    case OpKind::closure_check:
        return AnalysisClass::unknown;
    }
    throw std::runtime_error(
        "unknown IR operation kind in representation analysis");
}

没有 dst 的操作不会定义新值，所以返回的 unknown 不会成为某个 home 的最终分类。

copy 需要读取源操作数的当前分类。条件表达式会让同一个结果名在两个分支分别被 copy 定义，因此分析用 join_class 合并新旧信息：

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


AnalysisClass join_class(AnalysisClass current,
                         AnalysisClass incoming) {
    if (incoming == AnalysisClass::unknown) {
        return current;
    }
    if (current == AnalysisClass::unknown) {
        return incoming;
    }
    if (current == incoming) {
        return current;
    }
    return AnalysisClass::root;
}

只要一个来源是 root，汇合结果就不能继续声称“确定为整数”。

为什么表示分析要迭代

copy 的源值可能也是另一个尚未确定的临时名。一次从头到尾扫描未必能立即得到最终分类，所以实现反复传播，直到没有变化：

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


auto propagate = [&]() {
    bool changed = false;
    for (const auto& body : bodies) {
        for (const auto& op : *body.ops) {
            if (op.dst.empty()) {
                continue;
            }
            AnalysisClass incoming = definition_class(op, classes);
            AnalysisClass combined =
                join_class(classes[op.dst], incoming);
            if (combined != classes[op.dst]) {
                classes[op.dst] = combined;
                changed = true;
            }
        }
    }
    return changed;
};

while (propagate()) {
}

第一轮收敛后，仍然未知的值全部保守改成 root，再传播一次，让依赖这些值的 copy 也跟着变成 root。最终才转换成公开的 ValueClass。

这不是为了推断源语言类型，而是在有限的两类 home 资格之间做单调、保守的选择：信息只会从 unknown 走向 integer 或 root，冲突时走向更安全的 root。

分类结果与控制流分析放在一起

公开的分配结果保留了本章后续各步需要观察的信息：

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


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

struct BodyAllocation {
    std::vector<std::string> value_order;
    std::map<std::string, ValueClass> value_classes;
    std::map<std::string, Home> homes;
    std::vector<NameSet> live_in;
    std::vector<NameSet> live_out;
    std::map<std::string, NameSet> interference;
    std::size_t root_frame_size = 0;
    std::size_t spill_count = 0;

    const Home& home(const std::string& name) const;
};

struct ProgramAllocation {
    BodyAllocation main_body;
    std::vector<BodyAllocation> function_bodies;
};

入口接口只有一份：

1

ProgramAllocation allocate_registers(const IrProgram& program);

因此，表示分类不是一个会产生另一门语言的独立前端。它为同一个 IrProgram 添加 ValueClass 信息；紧接着，活跃性分析和冲突图继续为这些名字选择 home。

`alloc` 是每一步的观察窗口

运行：

1

./mini alloc examples/register_alloc_live.lang

输出分成四部分：

1
2
3
4


values         每个 IR 名字的 ValueClass 与 home
flow           方括号中的完整 IR 操作，以及 use、live_in、live_out
interference   确定为整数的值与谁冲突
summary        root frame 字节数与 spill 个数

如果程序包含函数，后面还会继续出现 lambda0:、lambda1: 等 body。不会出现“fallback”提示，因为 closure、record、cell 和整数从一开始就在同一个 IR 与分配器里。

可以用下面的命令观察一个带递归函数调用的完整例子：

1

./mini alloc examples/register_call_live.lang

输出较长，但结构没有变化：main 和 lambda0 各有自己的 values、flow、interference 和 frame 汇总。

pseudo 指令与最终 x86-64 仍有距离

IR 中的 add lhs rhs 可以让两个操作数都引用任意 home，但 x86-64 并不允许每一种内存到内存组合。IR 已经显式保存 integer_check 这类有语义顺序的检查，但仍没有写死函数序言、保存 callee-saved register、栈对齐、具体 tag 检查指令序列或 root frame 扩展。

这些细节留给最终 emitter：

分配器先决定每个名字的 home；
emitter 再用 %rax、%rcx 等 scratch register 把 IR 操作改写成合法指令；
分配和 call 之前，emitter 仍依据 liveness 收紧 root slots；
branch 保持条件为假跳 else、条件为真顺序进入 then 的固定布局。

所以，结构化 IR 足够接近机器，能进行 CFG 和 home 分析；又没有过早写死机器位置，仍给寄存器分配留下空间。这正是 pseudo 层存在的价值。

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

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

本节目录