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

本节阅读量:

上一节里，解释器可以直接借助 C++ 的 if 选择分支：

1
2
3
4


if (eval_expr(*if_expr.condition, env) != 0) {
    return eval_expr(*if_expr.then_branch, env);
}
return eval_expr(*if_expr.else_branch, env);

编译器不能在编译时替程序做这个选择。condition 的结果通常要等程序运行后才能知道，因此编译器必须把两条路都生成出来，再让运行中的程序选择其中一条。

这一节先不看具体 C++ 实现，只解决两个问题：

1
2


1. IR 怎样表示“下一步不一定是列表里的下一条操作”？
2. then 和 else 只会执行一个，整个 if 的结果放在哪里？

原来的直线 IR 为什么不够用

第二章的 IR 是一条直线：

1
2
3


x0 = 40
t.0 = x0 + 2
return t.0

它有一个没有明说的规则：执行完当前操作，就继续执行列表里的下一条操作。

这个规则适合整数、加法和 let，却不能直接表示 if。例如：

1

(if (eq? 0 0) (+ 40 2) (+ 3 4))

如果仍然只把计算步骤依次排下去，可能得到这样的错误 IR：

1
2
3
4


t.0 = eq? 0 0
t.1 = 40 + 2
t.2 = 3 + 4
return ???

这里有两个明显的问题：

t.0 算出来以后，没有任何操作根据它选择道路。
then 和 else 的计算都排在直线上，运行时会把两个分支都执行一遍。

所以，第三章的 IR 不能只回答“算什么”，还必须回答“算完以后去哪里”。

给操作之间加上道路

if 的执行形状不是一条直线，而是先分开、再汇合：

1
2
3
4
5
6
7


                    condition
                   /         \
              非 0 /           \ 0
                 then          else
                   \           /
                    \         /
                       end

第三章加入三种控制流操作来表达这张图：

1
2
3
4
5
6
7
8


branch condition then_label else_label
    根据 condition 选择一个目标

jump target
    无条件前往 target

label name
    给某个位置命名，让 branch 和 jump 可以指向它

虽然 IR 仍然把操作保存在一个线性列表里，但运行顺序不再完全等于存放顺序。遇到 branch 或 jump 时，下一步要到目标 label，而不是机械地执行列表中的下一条。

核心变化可以概括成：

1
2


操作仍然线性存放；
branch、jump 和 label 在操作之间建立控制流。

看一遍完整 IR

运行：

1
2
3


cd code/03_conditionals
make
./mini ir examples/if.lang

源码是：

1

(if (eq? 0 0) 42 7)

输出是：

1
2
3
4
5
6
7
8
9


t.0 = eq? 0 0
if t.0 goto then0 else else0
then0:
t.1 = 42
goto end0
else0:
t.1 = 7
end0:
return t.1

两条路线都出现在编译结果里，但一次运行只会走其中一条。这与解释器“只调用一个分支”的语义完全一致。

then 末尾必须有 goto end0。如果没有这次跳转，执行完 then 后就会继续落入紧随其后的 else0，两个分支仍然都会执行。

两条路怎样产生一个结果

控制流解决了“走哪条路”，接下来还要解决“结果在哪里”。

在这门语言里，if 不是一条没有结果的语句，而是表达式：

1

(+ 1 (if 1 20 30))

后面的加法需要取得 if 的结果。第三章为一次 if 创建一个共享结果名，例如 t.1：

1
2
3
4
5
6
7


then0:
t.1 = 42
goto end0
else0:
t.1 = 7
end0:
return t.1

运行时只有一个分支会执行，因此 t.1 只会被其中一条路写入。到达 end0 时，无论来自 then 还是 else，t.1 都已经保存了整个 if 的结果。

这份小型 IR 允许两个分支写同一个内部名字。后面分配栈槽时，两个 t.1 也必须对应同一个位置，汇合后才能从同一处读取结果。

label 也划出了基本块

现在可以给这些连续操作一个名字：基本块。

一个基本块只能从开头进入，进入以后会顺序执行其中的操作，直到末尾跳转、分支或返回。上面的 IR 可以看成四块：

1
2
3
4


入口块   计算 condition，最后执行 branch
then0    计算 then，最后 jump end0
else0    计算 else，随后到达 end0
end0     使用汇合后的结果

它们之间的道路是：

1
2


入口 -> then0 -> end0
    \-> else0 -> end0

这就是一个很小的控制流图。第三章暂时不创建单独的 CFG 类；线性操作列表保存各块的内容，label 标出块的入口，branch 和 jump 记录块之间的边。

到这里，IR 已经同时表达了两件事：

1
2


数据流：每一步读取什么，结果写到哪里。
控制流：执行完这一步，下一步可能去哪里。

下一节进入代码，看看 AST 怎样 lowering 成这些操作和道路。

3.4 解释器：先判断，再选择

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

本节目录