结构化 IR：把代码标签和捕获值配成一对
本节阅读量:
解释器可以让 Closure 直接保存 AST body。编译器不能在运行时解释 AST，因此要把一个 lambda 拆成两部分：
1
2
|
独立的 IrFunction 描述以后执行的函数体
closure op 在当前时刻把代码标签和捕获 Value 组成函数值
|
这一步通常叫 closure conversion。本章把它落实在结构化 IR 中，而不是先拼接字符串。
compile 必须经过 IrProgram
CLI 的编译路径明确写成：
1
|
mini::compile_to_assembly(mini::lower_to_ir(*expr), target)
|
完整路径是：
1
2
3
4
5
6
7
|
source
↓ parse
Expr AST
↓ lower_to_ir
IrProgram
↓ compile_to_assembly
x86-64 assembly
|
汇编生成器只接收 const IrProgram&。这样自由变量、求值顺序、函数体边界和捕获列表先在 IR 中固定下来，机器层只负责布局和指令选择。
closure 是一种明确的 OpKind
第七章在已有 op 种类中加入：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
enum class OpKind {
copy,
add,
sub1,
equal,
branch,
jump,
label,
closure,
closure_check,
call,
record,
record_predicate,
record_size,
field,
};
|
OpKind::closure 复用 Op 的两个通用字段：
1
2
|
target 函数代码标签
fields 按稳定顺序排列的捕获 operands
|
这里把捕获列表放在 fields，只是复用 C++ IR 容器，并不表示 closure 是 record op。op.kind 仍明确区分 closure 和 record，后端也会写入不同 header kind。
IrFunction 描述函数入口需要什么
每个被提取出的函数体使用：
1
2
3
4
5
6
7
8
|
struct IrFunction {
std::string label;
std::string param;
std::string self;
std::vector<std::string> captures;
std::vector<Op> ops;
Operand result;
};
|
字段含义是：
| 字段 |
用途 |
label |
生成汇编时的代码入口 |
param |
用户参数对应的唯一 IR 局部名 |
self |
letrec 的递归局部名；普通 lambda 为空 |
captures |
与 closure payload 槽一一对应的函数体局部名 |
ops |
函数体结构化操作 |
result |
函数返回的 operand |
self 与 captures 分开是有意的：self 由调用时的实际 callee 提供，不占用捕获槽。
从一个普通 lambda 开始
源码：
1
2
|
(let x 40
((lambda y (+ x y)) 2))
|
AST 仍然是：
1
|
Let(x, Int(40), Call(Lambda(y, Add(Var(x), Var(y))), Int(2)))
|
自由变量分析得到 [x]。lowering 在当前环境中把源码名 x 解析为 x0，然后产生 closure op：
1
2
3
4
5
6
7
8
9
|
x0 = 40
f.0 = closure lambda0 [x0]
check-closure f.0
t.1 = call f.0 2
return t.1
lambda0(y2, self: -, captures: [x1]):
t.0 = x1 + y2
return t.0
end lambda0
|
这里有三组名字，不要混淆：
1
2
3
|
x 源码中的变量名
x0 创建 closure 时可用的外层 IR local
x1 函数入口从 capture 0 装入的 IR local
|
它们不是三个源语言变量。x0 的 Value 被写进槽 0，调用函数时再从槽 0 读成 x1。
lowering 怎样解析捕获值
自由变量分析返回源码名字，resolve_captures 通过当前 lowering 环境找到对应 operand：
1
2
3
4
5
6
7
8
9
10
|
std::vector<Operand> resolve_captures(
const std::vector<std::string>& capture_names,
const Env& env) const {
std::vector<Operand> captures;
captures.reserve(capture_names.size());
for (const auto& name : capture_names) {
captures.push_back(lookup(env, name));
}
return captures;
}
|
普通 lambda 的主体步骤是：
1
2
3
4
5
6
|
capture_names = free_vars(lambda)
capture_values = resolve_captures(capture_names, current_env)
生成唯一函数 label
emit closure(label, capture_values)
为函数体创建新的 param local 和 capture locals
在新的函数环境中 lower body
|
函数环境不继承整个主程序环境。只把 capture_names 映射到新建的 capture locals，再加入参数。
捕获顺序同时约束两边
multiple_captures.lang 的 IR 是：
1
2
3
4
5
6
7
8
9
10
11
|
x0 = 10
y1 = 20
f.0 = closure lambda0 [x0, y1]
check-closure f.0
t.2 = call f.0 12
return t.2
lambda0(z4, self: -, captures: [x2, y3]):
t.0 = y3 + z4
t.1 = x2 + t.0
return t.1
end lambda0
|
这两份列表必须等长并保持同一顺序：
1
2
|
creation fields [x0, y1]
function locals [x2, y3]
|
IR 不需要保存一张运行时名字表。位置 i 就是两边的对应关系。
closure_check 把类型检查放在 argument 之前
调用涉及两种 op：
1
2
|
check-closure f.0
t.1 = call f.0 2
|
lowering 的顺序是：
1
2
3
4
|
lower callee
emit closure_check
lower argument
emit call
|
把检查单独放进结构化 IR，是为了保留源语言“先求 callee，确认它是函数，再求 argument”的顺序。若等到 call emitter 才检查，argument 的 ops 已经排在检查之前。
closure_check 的 lhs 是 callee，不产生 dst。call 的字段则是：
1
2
3
|
lhs callee Value
rhs argument Value
dst result local
|
IR 不在这里拆出 code pointer，也不决定 %rdi、%rsi。closure_check 只要求机器层验证 callee；heap tag、header kind、代码偏移和失败出口仍由汇编 emitter 决定。最终 call op 可以假定前面的检查已经成功。
嵌套 lambda 产生多个 IrFunction
运行：
1
2
|
cd code/07_closures
./mini ir examples/nested_closure.lang
|
完整输出是：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
x0 = 40
f.0 = closure lambda0 [x0]
check-closure f.0
t.2 = call f.0 1
check-closure t.2
t.3 = call t.2 1
return t.3
lambda1(z5, self: -, captures: [x3, y4]):
t.0 = y4 + z5
t.1 = x3 + t.0
return t.1
end lambda1
lambda0(y2, self: -, captures: [x1]):
f.1 = closure lambda1 [x1, y2]
return f.1
end lambda0
|
外层函数的 body 中创建内层 closure。对那条 op 而言，x1 和 y2 都是当时函数环境中可用的普通 operands。IR 无需增加“嵌套函数专用”的 closure 种类。
IrProgram::functions 中内层函数可能先于外层函数打印。这不影响标签引用：汇编标签可以在定义前被取地址。
letrec 使用 self 字段，不制造 self capture
recursive_closure.lang 的 IR 是：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
base0 = 10
f.0 = closure lambda0 [base0]
check-closure f.0
t.5 = call f.0 5
return t.5
lambda0(n3, self: adddown1, captures: [base2]):
t.0 = eq? n3 0
if t.0 goto then0 else else0
then0:
t.1 = base2
goto end0
else0:
check-closure adddown1
t.2 = sub1 n3
t.3 = call adddown1 t.2
t.4 = 1 + t.3
t.1 = t.4
end0:
return t.1
end lambda0
|
创建位置只有 [base0]，没有 f.0：
1
2
|
closure payload captures [base0]
IrFunction self adddown1
|
汇编函数入口会把隐藏的 %rdi 保存到 adddown1 的栈槽。递归 call 使用这个 tagged Value。因此 self 是调用约定带来的局部值，不是闭包提前捕获的外层值。
alpha-renaming 处理 self 与参数同名
对：
1
2
3
|
(letrec f f
f
(f 42))
|
IR 是：
1
2
3
4
5
6
7
|
f.0 = closure lambda0 []
check-closure f.0
t.0 = call f.0 42
return t.0
lambda0(f1, self: f0, captures: []):
return f1
end lambda0
|
self 是 f0，参数是 f1。函数体里的源码名 f 解析到更内层的参数 f1，所以返回 42。若只保存字符串 f 而不做词法环境解析，这个例子就无法正确实现。
closure 能捕获任何 Value
IR operand 不带静态源语言类型。捕获整数、record 或另一个 closure 都使用同一 Operand：
1
2
|
(let box (record 40 2)
((lambda x (+ (get box 0) x)) 2))
|
对应 IR：
1
2
3
4
5
6
7
8
9
10
11
|
t.0 = record 40 2
box0 = t.0
f.0 = closure lambda0 [box0]
check-closure f.0
t.3 = call f.0 2
return t.3
lambda0(x2, self: -, captures: [box1]):
t.1 = get box1 0
t.2 = t.1 + x2
return t.2
end lambda0
|
box0 是完整 tagged Value。closure op 不查看或复制 record payload。
IR 仍不决定机器布局
这一层表达的是：
1
2
|
创建 closure，代码标签是 lambda0，捕获 operands 是 [...]
调用某个 callee Value，并传一个 argument Value
|
它还没有决定：
- heap-object tag 是多少；
- closure header kind 是多少；
- code pointer 和 capture 的字节偏移；
- 哪个寄存器传隐藏 closure；
- 类型检查失败怎样退出。
这些决定集中在下一节的 runtime/value.h 与汇编 emitter 中。结构化边界让 AST、IR 和机器表示各自只回答自己那一层的问题。
7.5 汇编：在通用堆对象里放入代码和环境
下一节
