IR：两个函数值临时指向同一个入口
本节阅读量:
解释器通过调用环境建立 sum -> callee。编译器没有运行时的名字环境，它必须把同一件事提前变成明确的 IR 操作。
这里不需要增加“递归调用”这种特殊机器动作。普通函数调用已经能通过函数值完成递归；lowering 只需要确保函数体内部也能取得自己的入口地址。
先观察完整结果
运行：
1
2
3
|
cd code/05_recursion
make
./mini ir examples/recursive_sum.lang
|
当前实现输出：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
f.0 = function lambda0
t.5 = call f.0 5
return t.5
lambda0(n):
sum0 = function lambda0
t.0 = eq? n 0
if t.0 goto then0 else else0
then0:
t.1 = 0
goto end0
else0:
t.2 = sub1 n
t.3 = call sum0 t.2
t.4 = n + t.3
t.1 = t.4
end0:
return t.1
end lambda0
|
先抓住其中最重要的三行：
1
2
3
|
f.0 = function lambda0 主程序取得函数入口地址
sum0 = function lambda0 函数体再次取得同一个入口地址
t.3 = call sum0 t.2 通过函数体自己的临时值递归调用
|
f.0 和 sum0 是两个不同的 IR 临时值，却都表示同一个标签 lambda0 的地址。它们分别属于主程序和函数体，之后也会进入不同的机器栈帧。
IR 只新增 sub1 操作
第五章的 OpKind 在第四章基础上增加 sub1：
1
2
3
4
5
6
7
8
9
10
11
|
enum class OpKind {
copy,
add,
sub1,
equal,
branch,
jump,
label,
function_ref,
call,
};
|
这里没有 letrec 操作，也没有 recursive_call 操作：
letrec 在 lowering 时展开成独立 IrFunction、两个 function_ref 和已有的名字绑定；- 自调用仍然使用第四章已经存在的
call；
sub1 才是本章唯一需要直接交给汇编生成器的新操作。
这也说明 AST 和 IR 不需要一一对应。AST 保留源语言的作用域结构，IR 则只保留后端继续工作所需的动作。
sub1 的 lowering 与 add 很接近：先降低子表达式，再产生一个新临时值。
1
2
3
4
5
6
7
8
|
case ExprKind::sub1: {
const auto& sub1_expr = static_cast<const Sub1Expr&>(expr);
Operand value = lower_expr(*sub1_expr.expr, ops, env);
std::string dst = new_temp();
ops.push_back(
{OpKind::sub1, dst, std::move(value), Operand::integer(0), "", ""});
return Operand::temp(dst);
}
|
例如 (sub1 n) 变成：
lowering 的三个上下文没有改变
第五章继续沿用前几章建立的接口：
1
2
3
4
5
6
7
8
9
10
|
using Env = std::vector<std::pair<std::string, Operand>>;
class IrLowerer {
// ...
Operand lower_expr(const Expr& expr,
std::vector<Op>& ops,
Env& env);
IrProgram program_;
};
|
三个上下文各有清楚的职责：
| 上下文 |
作用 |
program_ |
保存整段程序，包括主程序与所有独立函数 |
ops |
当前正在追加操作的列表，可能属于主程序，也可能属于某个函数 |
env |
当前词法位置的源语言名字到 IR operand 的映射 |
IrProgram 是整个 lowering pass 的状态，不需要在每一层递归调用之间来回传递。ops 和 env 却必须显式传入，因为降低函数体时，这两者都要切换到函数自己的上下文。
入口保持很简单：
1
2
3
4
5
|
IrProgram lower(const Expr& expr) {
Env env;
program_.result = lower_expr(expr, program_.ops, env);
return std::move(program_);
}
|
主程序从空环境开始，操作追加到 program_.ops。遇到函数后，再创建独立的 function.ops 和 function_env。
第一步：主程序取得函数地址
letrec lowering 先为函数选择标签和主程序中的函数值临时：
1
2
3
4
5
6
7
8
9
|
std::string label = "lambda" + std::to_string(next_function_++);
std::string function_value =
"f." + std::to_string(next_function_value_++);
ops.push_back({OpKind::function_ref,
function_value,
Operand::integer(0),
Operand::integer(0),
label,
""});
|
对贯穿示例，这一步产生：
它的意思不是执行 lambda0，而是把 lambda0 的入口地址保存为值。随后 lowering 会在 letrec 的 body 环境里建立：
于是最外层 (sum 5) 能变成：
第二步：函数体建立自己的自引用
主程序里的 f.0 不能直接供递归函数体使用。f.0 将来属于 main 的栈帧，而每次执行 lambda0 时都有另一份独立栈帧。
因此 lowering 在函数体自己的操作列表中，再放入一个指向相同标签的 function_ref：
1
2
3
4
5
6
7
8
9
10
|
std::string self = letrec_expr.name + std::to_string(next_local_++);
IrFunction function;
function.label = label;
function.param = letrec_expr.param;
function.ops.push_back({OpKind::function_ref,
self,
Operand::integer(0),
Operand::integer(0),
label,
""});
|
贯穿示例中的 self 是 sum0，所以函数体开头得到：
1
|
sum0 = function lambda0
|
接着只为函数体建立一份新的名字环境：
1
2
3
4
5
|
Env function_env;
function_env.push_back(
{letrec_expr.name, Operand::temp(self)});
function_env.push_back(
{letrec_expr.param, Operand::temp(letrec_expr.param)});
|
它包含：
第一条映射让函数体中的 Var(sum) 得到 sum0，第二条映射让 Var(n) 得到当前函数参数。这里没有复制外层 env，因此 lowering 与解释器遵守相同边界：递归函数能看到自己和参数，不能直接读取其他外层变量。
最后把函数体 lowering 到独立操作列表，并登记到整段程序：
1
2
3
|
function.result =
lower_expr(*letrec_expr.function_body, function.ops, function_env);
program_.functions.push_back(std::move(function));
|
第三步：降低 letrec 的 body
独立函数登记完成后，原来的外层 env 一直没有被替换。lowering 只在其中临时加入递归名字：
1
2
3
4
|
env.push_back({letrec_expr.name, Operand::temp(function_value)});
Operand result = lower_expr(*letrec_expr.body, ops, env);
env.pop_back();
return result;
|
这对应源语言的作用域规则：
1
2
|
function_body 使用新的 function_env：self + parameter
letrec body 使用原来的 env：outer bindings + function_value
|
两份环境不能混为一谈。若把外层 env 直接交给 function_body，就会在尚未实现闭包表示时错误地允许函数读取外层局部值。
完整的 letrec lowering
把三个阶段合在一起，当前代码是：
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
35
36
37
|
case ExprKind::letrec: {
const auto& letrec_expr = static_cast<const LetRecExpr&>(expr);
std::string label = "lambda" + std::to_string(next_function_++);
std::string function_value =
"f." + std::to_string(next_function_value_++);
ops.push_back({OpKind::function_ref,
function_value,
Operand::integer(0),
Operand::integer(0),
label,
""});
std::string self = letrec_expr.name + std::to_string(next_local_++);
IrFunction function;
function.label = label;
function.param = letrec_expr.param;
function.ops.push_back({OpKind::function_ref,
self,
Operand::integer(0),
Operand::integer(0),
label,
""});
Env function_env;
function_env.push_back(
{letrec_expr.name, Operand::temp(self)});
function_env.push_back(
{letrec_expr.param, Operand::temp(letrec_expr.param)});
function.result =
lower_expr(*letrec_expr.function_body, function.ops, function_env);
program_.functions.push_back(std::move(function));
env.push_back({letrec_expr.name, Operand::temp(function_value)});
Operand result = lower_expr(*letrec_expr.body, ops, env);
env.pop_back();
return result;
}
|
它没有修改普通 lambda 的 lowering。普通函数的 function_env 仍然只包含参数；只有专用 letrec 会额外加入 self 映射。
按求值顺序阅读完整 IR
函数体的 IR 可以分成四段。
第一段取得 self 并检查停止条件：
1
2
3
|
sum0 = function lambda0
t.0 = eq? n 0
if t.0 goto then0 else else0
|
条件为真时，CFG 沿 branch 的 then 边进入 then0，把结果设为 0：
1
2
3
|
then0:
t.1 = 0
goto end0
|
当前 lowering 按固定约定把 then0 放在 branch 后面，但在 IR/CFG 层它仍然是显式的 branch 目标。到了汇编层，这个固定的物理布局才会让 then 路径直接顺序执行，并只用条件跳转前往 else；本章不做基本块重排或额外窥孔优化。
条件为假时，先把参数减一，再通过 sum0 调用同一个函数入口：
1
2
3
|
else0:
t.2 = sub1 n
t.3 = call sum0 t.2
|
递归调用返回后，当前这一层才能把自己的 n 加到结果上：
1
2
3
4
|
t.4 = n + t.3
t.1 = t.4
end0:
return t.1
|
t.3 是更深一层递归的结果，n 则是当前函数调用的参数。两者在 call 之后仍然要参与加法，所以 recursive_sum.lang 中的递归调用不在尾位置。
你还会看到函数体使用了 t.0 到 t.4，主程序的调用结果却编号为 t.5。原因是 lowering 在遇到 letrec 时先完整降低并登记函数体，之后才继续降低 letrec 的 body。编号反映的是 lowering 的处理顺序，不是最终打印行的先后顺序。
函数值被转存后仍然指向同一入口
运行：
1
|
./mini ir examples/recursive_function_value.lang
|
主程序开头会变成：
1
2
3
|
f.0 = function lambda0
f1 = f.0
t.5 = call f1 5
|
源程序让 letrec 返回函数值，再用普通 let 把它保存为 f。IR 名字虽然从 f.0 复制成了 f1，其中的机器值仍是 lambda0 的地址；函数体内部也仍会用 sum0 取得这个标签。递归能力不依赖外层变量最终叫什么名字。
不支持的捕获会在哪里被发现
对下面的边界示例：
1
|
./mini ir examples/recursive_capture_error.lang
|
lowering 会报告：
1
|
error: undefined variable: base
|
这是因为 function_env 只有 adddown 和 n。编译器在 lowering 函数体时就遇到了 base，所以它通常比解释器更早发现这个作用域错误；支持范围内的程序结果保持一致，并不要求两条路径在同一时刻报告所有错误。
到这里，递归在 IR 中可以压缩成一句话：主程序和递归函数体各自取得同一个函数标签的地址，再完全复用普通的间接 call。
5.4 解释器：每次调用都把函数自己带进去
上一节
