IR lowering：把 AST 变成分支和汇合

本节阅读量:

上一节已经确定目标 IR 的形状。这一节进入实现，看看 lowerer 怎样生成谓词、label、跳转和共享结果名。

代码在：

1
2


code/03_conditionals/src/compile/ir.h
code/03_conditionals/src/compile/ir.cpp

lower_expr 的约定没有改变

先回顾 lowerer 的核心约定：

1

Operand lower_expr(const Expr& expr, std::vector<Op>& ops, Env& env)

它做两件事：

1
2


1. 把计算 expr 所需的操作追加到当前 ops。
2. 返回一个 Operand，告诉调用者 expr 的结果在哪里。

例如：

1
2
3


Int(42)       不追加操作，直接返回整数操作数 42
Add(...)      追加一条 add，返回保存结果的临时名字
If(...)       追加分支和两条路径，返回汇合后的共享结果名

因此，lowering if 并不是立刻求出 then 或 else 的值。lowerer 在编译期间会遍历两个分支，把两边的操作都生成出来；将来程序运行时，branch 才会决定执行哪一边。

要特别区分这两个时刻：

1
2


编译时：lower 两个分支，生成两份代码。
运行时：根据 condition，只执行一个分支。

lowerer 会先后遍历 then 和 else，但两边都从进入这个 if 时的同一个 lowerer 环境出发。某个分支内部如果出现 let，它会在该分支 lowering 期间 push 绑定，并在离开作用域前 pop；then 中的局部绑定不会因为先生成，就泄漏到 else。

IR 在代码里怎样保存

操作种类定义在 ir.h：

1
2
3
4
5
6
7
8


enum class OpKind {
    copy,
    add,
    equal,
    branch,
    jump,
    label,
};

equal 负责产生普通整数结果，branch、jump 和 label 负责控制下一步去哪里。

每条操作都保存在同一个 Op 结构里：

1
2
3
4
5
6
7
8


struct Op {
    OpKind kind;
    std::string dst;
    Operand lhs;
    Operand rhs;
    std::string target;
    std::string else_target;
};

不同 OpKind 使用不同字段：

1
2
3
4
5
6


copy       dst、lhs
add        dst、lhs、rhs
equal      dst、lhs、rhs
branch     lhs、target、else_target
jump       target
label      target

例如，一条 branch：

1

if t.0 goto then0 else else0

在结构里保存的是：

1
2
3
4


kind          = branch
lhs           = temp("t.0")
target        = "then0"
else_target   = "else0"

没有使用到的字段会放占位值。真正决定一条 Op 应该怎样解释的是 kind；IR 打印和下一节的汇编生成器都会用 switch 分派。

把重复动作抽成两个辅助函数

第二章直接在各个分支里生成临时名字、追加 copy。第三章需要这些动作的地方变多了，所以把重复代码抽成两个辅助函数：

1
2
3
4
5
6
7


std::string new_temp() {
    return "t." + std::to_string(next_temp_++);
}

void emit_copy(std::vector<Op>& ops, const std::string& dst, Operand value) {
    ops.push_back({OpKind::copy, dst, std::move(value), Operand::integer(0), "", ""});
}

new_temp() 统一生成 t.0、t.1 这样的临时名字，供加法、eq? 和 if 的共享结果使用。emit_copy() 统一追加 dst = value，既用于原有的 let，也用于把 then 和 else 的结果保存到同一个名字。

它们没有引入新的 IR 概念，只是把多处相同的实现集中起来。

eq? 怎样 lowering

eq? 是前面说过的谓词表达式：它提出一个判断，并把结果表示成整数 0 或 1。

谓词本身不会改变控制流。它和加法一样，读取操作数、生成一个临时名字，再把结果写进去。后面的 if 可以读取这个 0 或 1，再决定走哪个分支。

eq? 读取两个操作数：

1
2
3
4
5
6
7
8


case ExprKind::equal: {
    const auto& eq_expr = static_cast<const EqExpr&>(expr);
    Operand lhs = lower_expr(*eq_expr.lhs, ops, env);
    Operand rhs = lower_expr(*eq_expr.rhs, ops, env);
    std::string dst = new_temp();
    ops.push_back({OpKind::equal, dst, std::move(lhs), std::move(rhs), "", ""});
    return Operand::temp(dst);
}

这里也保持从左到右的 lowering 顺序：先生成 lhs 所需的操作，再生成 rhs，最后追加 equal。

例如 (eq? (+ 20 22) 42) 得到：

1
2
3


t.0 = 20 + 22
t.1 = eq? t.0 42
return t.1

判断某个表达式是否为零也用同一条路径，例如 (eq? x 0)。equal 的结果一定是 0 或 1，但在 IR 中仍然只是普通整数操作数，可以继续交给 if、加法或其他表达式使用。

if 怎样 lowering

先不看 C++ 细节，把 lowering 骨架写成步骤：

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


condition = lower condition
创建 then、else、end label 和共享 result

追加 branch condition then else
追加 then label
lower then，把值 copy 到 result
追加 jump end

追加 else label
lower else，把值 copy 到 result
追加 end label

返回 result

这份骨架先解决控制流，再把两个分支的值汇合到同一个内部名字。对照它阅读完整代码：

 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


case ExprKind::conditional: {
    const auto& if_expr = static_cast<const IfExpr&>(expr);
    Operand condition = lower_expr(*if_expr.condition, ops, env);
    int label_id = next_label_++;
    std::string then_label = "then" + std::to_string(label_id);
    std::string else_label = "else" + std::to_string(label_id);
    std::string end_label = "end" + std::to_string(label_id);
    std::string result = new_temp();

    ops.push_back({OpKind::branch,
                   "",
                   std::move(condition),
                   Operand::integer(0),
                   then_label,
                   else_label});
    ops.push_back(
        {OpKind::label, "", Operand::integer(0), Operand::integer(0), then_label, ""});
    Operand then_value = lower_expr(*if_expr.then_branch, ops, env);
    emit_copy(ops, result, std::move(then_value));
    ops.push_back(
        {OpKind::jump, "", Operand::integer(0), Operand::integer(0), end_label, ""});
    ops.push_back(
        {OpKind::label, "", Operand::integer(0), Operand::integer(0), else_label, ""});
    Operand else_value = lower_expr(*if_expr.else_branch, ops, env);
    emit_copy(ops, result, std::move(else_value));
    ops.push_back(
        {OpKind::label, "", Operand::integer(0), Operand::integer(0), end_label, ""});
    return Operand::temp(result);
}

第一步递归 lower condition。condition 自己可能包含加法、变量甚至另一个 if：

1

Operand condition = lower_expr(*if_expr.condition, ops, env);

接着为这次 if 创建三个互不冲突的 label，以及一个共享结果名：

1
2
3
4
5


int label_id = next_label_++;
std::string then_label = "then" + std::to_string(label_id);
std::string else_label = "else" + std::to_string(label_id);
std::string end_label = "end" + std::to_string(label_id);
std::string result = new_temp();

然后按线性布局追加两条路径：

1
2
3
4
5
6
7
8
9


branch condition then_label else_label
then_label:
lower then_branch
result = then_value
jump end_label
else_label:
lower else_branch
result = else_value
end_label:

then 和 else 都通过 emit_copy() 写入 result，但运行时只会执行其中一个 copy。当前布局把 then label 紧跟在 branch 后面，让非零条件可以顺序落入 then；零条件则跳到 else。then 结束后必须 jump end_label，避免继续落入 else。

最后返回共享结果名：

1

return Operand::temp(result);

调用者不需要知道这个结果来自哪个分支。它只知道：执行到 end_label 后，result 中就是整个 if 的值。

next_label_ 为每个 if 分配独立编号，所以嵌套条件会得到 then0、then1 等不同名字，不会跳进别的 if。

到这里，AST 已经 lowering 成带控制流的 IR。下一节把这些 IR 操作翻译成 x86-64 汇编。

3.5 IR：把一条直线变成几条可选择的路

3.7 汇编：让 CPU 真的选择道路

本节目录