章节目录

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

本节阅读量:

寄存器之所以能够复用，是因为一个程序虽然会产生许多临时值，却不会让它们永远同时存在。某个值最后一次被使用以后，它的 home 就可以交给另一个值。

第九章已经为了收紧 GC roots 做过 CFG liveness。第十章没有另外发明一套分析：同一份 live_in 和 live_out 既告诉 emitter 哪些 root 在 safepoint 前必须保留，也告诉寄存器分配器哪些整数不能共用 home。

1
2
3
4

同一份控制流事实，服务两个消费者：

root value     -> safepoint 前保留还是清零
integer value  -> 冲突图中是否需要连边

先手推六条指令

继续使用：

1
2

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

IR 是：

1
2
3
4
5
6
7

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

对一条操作，我们先问两件事：

1
2

use  这条操作执行前必须已经存在的临时值
def  这条操作新定义的临时值

于是：

序号 操作 use def
0 t.0 = 19 + 21 {} t.0
1 check-integer t.0 {t.0} 无
2 t.1 = record 0 0 {} t.1
3 t.2 = size t.1 {t.1} t.2
4 check-integer t.2 {t.2} 无
5 t.3 = t.0 + t.2 {t.0, t.2} t.3

立即数不需要 home，所以 19、21 和 record 的两个 0 不进入 use 集合。

从后往前看：

  • return t.3 需要 t.3，所以第 5 条执行后 t.3 仍然活着。
  • 第 5 条使用 t.0 和 t.2，所以它执行前两者都活着；它同时定义了新的 t.3。
  • 第 4 条检查 t.2，因此 t.2 在进入该操作时必须活着；它也还要供第 5 条使用。
  • 第 3 条定义 t.2，但执行后还需要早先的 t.0 和新值 t.2。
  • 第 2 条创建 t.1，随后 size 会使用它；更早产生的 t.0 也必须跨过 record 分配继续存活。
  • 第 1 条使用 t.0 做左操作数检查；检查通过后，t.0 还要跨过右操作数的整段求值。

最终得到：

序号 live_in live_out
0 {} {t.0}
1 {t.0} {t.0}
2 {t.0} {t.0, t.1}
3 {t.0, t.1} {t.0, t.2}
4 {t.0, t.2} {t.0, t.2}
5 {t.0, t.2} {t.3}

这张表已经告诉我们：t.0 和 t.2 在第 3 条之后同时活着，不能放进同一个寄存器；t.3 出现时它们都被消费了，可以复用其中一个 home。

两条 check 不定义新值，却不是可以从 CFG 中抹掉的装饰。它们作为真实 IR 节点，既记录当前值的一次 use，也把“lhs 检查完才求 rhs”的解释器顺序固定下来。

两条活跃性方程

对第 i 条操作，定义：

1
2
3

use[i]   该操作读取的名字
def[i]   该操作写入的名字；没有 dst 时为空
succ[i]  控制流可能前往的后继

活跃性方程是：

1
2
3
4

live_out[i] = union(live_in[s])             for s in succ[i]

live_in[i]  = use[i] union
              (live_out[i] - def[i])

第一条说：只要某个值在任意后继入口仍有用，它就在当前操作出口活着。

第二条说：一条操作执行前，既要准备它自己会读取的值，也要保留执行后仍然需要、且没有被本条重新定义的值。

def 为什么要从 live_out 中减掉？看：

1

t.3 = t.0 + t.2

执行前需要的是旧的 t.0 与 t.2，不需要一个尚未产生的 t.3。执行以后才由本条定义 t.3。

用 kind + switch 收集 uses

register_alloc.cpp 中的 used_names 覆盖全部 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
34

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::integer_check:
    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 只记录临时名，忽略整数立即数：

1
2
3
4
5

void note_use(NameSet& uses, const Operand& operand) {
    if (operand.kind == OperandKind::temp) {
        uses.insert(operand.temp_name);
    }
}

定义则直接来自非空的 op.dst。像 store、integer_check、branch、jump、label 和 closure_check 这样的操作没有结果名，自然没有 def。integer_check 仍通过 lhs 产生一次 use，所以被检查的值不会在 check 之前提前死去。

这份 uses 规则也精确描述了求值阶段必须保留的值。例如 record 的所有字段都是 uses；如果分配触发 GC，字段对应的活对象必须还在 roots 中，等对象地址更新后才能写入新 record。

后继不能只看下一行

顺序操作通常前往 index + 1，但控制流操作不同：

1
2

jump       只有目标 label 一个后继
branch     then label 和 else label 两个后继

实现先建立 label 到指令序号的映射，再构造后继表：

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

std::vector<std::vector<std::size_t>> successors(ops.size());
for (std::size_t index = 0; index < ops.size(); ++index) {
    const auto& op = ops[index];
    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;
    }
}

这里分析的是 CFG 边，而不是猜测最终汇编哪一行排在下一行。汇编层继续采用既定的 then fallthrough 布局；活跃性仍然同时合并 then 和 else 两条可能路径。

integer_check 在正常情况下顺序进入下一条 op，所以由 default 处理。检查失败时，汇编会转入不返回、也不再使用任何 IR Value 的全局错误出口。如果在 liveness 中把这条失败边也画出来，它的入口集合为空，与只保留正常 fallthrough 后继的分析结果完全相同。

如果某条普通操作是 body 的最后一条，index + 1 会等于 ops.size()。实现把这个位置视作一个虚拟 exit 节点。

body result 是出口处的一次使用

IrProgram 和 IrFunction 都把最终结果单独保存在 result 字段中。分析先为 exit 节点建立活跃集合：

1
2

NameSet exit_live;
note_use(exit_live, result);

因此，即使最后一个 IR 操作定义了一个此后没有普通 op 使用的临时值，它也不会被误判为死值。上一例中的 t.3 正是通过 exit_live 出现在最后一行的 live_out 中。

如果 result 是整数字面量，exit_live 为空，因为立即数可以在函数返回时直接生成，不需要事先占据 home。

反向迭代直到不再变化

有了 uses、defs 和 successors，真实定点迭代几乎就是方程的逐行翻译：

 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

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;
        }
    }
}

集合最初都为空。每轮从后向前更新；只要有一条边传播了新名字，changed 就会保持为真，再跑一轮。名字总数有限，而且集合只会增加到正确的定点，所以分析最终会停止。

即使当前 IR 的控制流很小，采用标准定点算法也比依赖文本恰好怎样排列更可靠。以后 pass 调整块内细节时，只要 CFG 后继不变，活跃性含义就不变。

用 alloc 对照计算结果

运行：

1

./mini alloc examples/register_alloc_live.lang

flow 部分会打印完整 IR 操作和四组信息：

1
2
3
4
5
6
7

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}

阅读一行时，可以按这个顺序：

  1. 方括号内先确认这是哪条真实 IR；
  2. use 确认当前操作会读取谁；
  3. in 确认进入操作前必须保留谁；
  4. out 确认操作结束后谁仍有后续用途。

values 里的 integer/root 分类不参与活跃性方程本身。分析先对所有临时值统一计算生命周期，下一步建立冲突图时才只挑出 integer 节点。

同一份 liveness 怎样继续服务 GC

第九章的两个 safepoint 规则被保留下来。

分配对象前，操作本身的输入还没有被消费，所以按 live_in 清 root：

1
2
3
4
5
6
7

void emit_allocator_call(std::size_t bytes, std::size_t index) {
    clear_roots_not_in(body_allocation_->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";
}

普通源语言 call 则先把 callee、argument 和 raw code address 装进 ABI 规定的位置，再按 live_out 清理 caller root slots：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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(body_allocation_->live_out.at(index));
out_ += "    call *%r11\n";
store_result(op.dst);

这两处只会清 HomeKind::root_slot。确定为整数的 register 或 spill home 不需要 collector 扫描；而 %rbx、%r12、%r13、%r14 又是 callee-saved，所以活整数可以安全跨过调用。

三个容易犯的错误

只按文本下一行传播

这样会漏掉 jump 目标或 branch 的另一条后继，使分支汇合后的 live set 不完整。错误结果可能让两个实际同时活跃的值共用寄存器。

忘记把 body result 放进 exit

最后一个临时结果会看起来“后面没人用”，分配器可能错误复用它的 home，或者 safepoint 过早清理它。

把 liveness 和表示分类混成一件事

root 值也会生、会死；integer 值也可能活很久。分类回答 collector 是否必须扫描，liveness 回答控制流上以后是否还要使用。只有把两个维度分开，才能既安全又复用寄存器。

有了完整 live sets，下一节就可以把“两个确定整数同时活着”转换成冲突图中的一条边。

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

上一节

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

下一节
本节目录