结构化 IR：把值和位置分开

本节阅读量:

第七章的 lowering 环境把源码名字解析成一个表示“值”的 Operand。第八章加入 set! 以后，同一个名字在不同时刻可能读出不同的值，因此环境不能再把名字直接解析成某次读取的结果。

本章采用一条统一规则：

1
2
3
4
5
6


lowering 环境：源码名字 -> cell Operand

let       创建 cell
变量读取  从 cell load
set!      向同一个 cell store
closure   捕获 cell Operand

这里的 cell 是编译器内部可见的可变位置。源程序不能直接取得 cell，也不能把某个普通表达式当作赋值目标。

从最小程序观察三个新操作

先看 examples/set.lang：

1
2
3
4


(let x 1
  (begin
    (set! x 41)
    (+ x 1)))

构建后输出 IR：

1
2
3


cd code/08_state
make
./mini ir examples/set.lang

实际输出是：

1
2
3
4
5


x0.cell = cell 1
store x0.cell 41
t.0 = load x0.cell
t.1 = t.0 + 1
return t.1

逐行阅读：

cell 1 创建一个初值为 1 的位置，x0.cell 表示这个位置。
store x0.cell 41 把位置里的内容改成 41。
后面的变量 x 不再直接变成某个旧值，而是生成 load x0.cell。
加法使用刚刚读出的 41，最终得到 42。

.cell 只是 IR 名字中的可读提示，不是源语言语法，也不是一套静态类型标注。

IR 仍然是结构化数据

本章没有退回“把每行 IR 拼成字符串”的做法。OpKind 在第七章的操作上增加 cell、load 和 store：

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


enum class OpKind {
    copy,
    cell,
    load,
    store,
    add,
    sub1,
    equal,
    branch,
    jump,
    label,
    closure,
    closure_check,
    call,
    record,
    record_predicate,
    record_size,
    field,
};

它们继续复用同一个 Op：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


struct Op {
    OpKind kind;
    std::string dst;
    Operand lhs;
    Operand rhs;
    std::string target;
    std::string else_target;
    std::size_t field_index = 0;
    std::vector<Operand> fields;
};

三个新操作使用这些字段的方式如下：

操作	`dst`	`lhs`	`rhs`
`cell`	新 cell 的 IR 名字	初始 Value	不使用
`load`	读取结果	cell Operand	不使用
`store`	不使用	cell Operand	要写入的 Value

store 没有结果槽，是因为写入本身只产生副作用。但源语言中的 set! 有结果：它返回刚刚写入的 Value。lowering 会直接把 RHS 的 Operand 作为整个 set! 的结果，不需要再 load 一次。

运行：

1

./mini ir examples/set_result.lang

会看到：

1
2
3
4


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

源码是 (+ (set! x 40) 2)，所以加法可以直接使用 set! 返回的 40。

lowering 环境保存 cell Operand

lowerer 里的环境类型仍然很小：

1

using Env = std::vector<std::pair<std::string, Operand>>;

变化在于其中的 Operand 现在表示 cell，而不是变量本次读取出的 Value。

变量节点先找到 cell，再生成 load：

1
2
3
4


case ExprKind::variable: {
    const auto& var_expr = static_cast<const VarExpr&>(expr);
    return emit_load(ops, lookup(env, var_expr.name));
}

let 则先求 initializer，成功以后创建 cell，再把源码名字和 cell 对应起来：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


case ExprKind::let: {
    const auto& let_expr = static_cast<const LetExpr&>(expr);
    Operand value = lower_expr(*let_expr.value, ops, env);
    std::string cell = new_cell_local(let_expr.name);
    emit_cell(ops, cell, std::move(value));
    env.push_back({let_expr.name, Operand::temp(cell)});
    Operand result = lower_expr(*let_expr.body, ops, env);
    env.pop_back();
    return result;
}

本章对所有 let 绑定和函数参数都采用这套表示，即使某个变量最后没有被 set! 修改，也仍然创建 cell。这样变量读取、闭包捕获和赋值只有一条路径。只给真正会修改的变量装箱需要额外的分析，留到进阶练习再讨论。

`set!` 与 `begin` 怎样 lowering

set! 必须修改已经存在的绑定。lowering 先解析目标 cell，再处理 RHS：

1
2
3
4
5
6
7


case ExprKind::set: {
    const auto& set_expr = static_cast<const SetExpr&>(expr);
    Operand cell = lookup(env, set_expr.name);
    Operand value = lower_expr(*set_expr.value, ops, env);
    emit_store(ops, std::move(cell), value);
    return value;
}

这个顺序带来两个结果：

未绑定的目标会得到 undefined variable，不会悄悄创建新 cell；
RHS 的所有操作都排在最终 store 前，只有 RHS 成功以后才修改原值。

begin 不需要自己的 IR 操作。它只规定 lowering 和运行顺序：

1
2
3
4
5


case ExprKind::begin: {
    const auto& begin_expr = static_cast<const BeginExpr&>(expr);
    (void)lower_expr(*begin_expr.first, ops, env);
    return lower_expr(*begin_expr.second, ops, env);
}

第一项产生的操作会先进入 ops，它的结果 Operand 被丢弃；第二项随后 lowering，并成为整个 begin 的结果。

可以用 begin_order.lang 核对：

1

./mini ir examples/begin_order.lang

1
2
3
4
5
6
7


x0.cell = cell 0
store x0.cell 40
t.0 = load x0.cell
t.1 = t.0 + 2
store x0.cell t.1
t.2 = load x0.cell
return t.2

两个 store 的先后顺序就是源码中的执行顺序，最终 load 得到 42。

闭包捕获位置，而不是一次读取结果

考虑 write_only_capture.lang：

1
2
3


(let x 0
  (let put (lambda value (set! x value))
    (begin (put 42) x)))

函数体没有普通的 Var(x) 读取，只有 (set! x value)。自由变量分析仍必须把赋值目标 x 算作自由变量，否则 closure 将不知道应该写哪个位置。

运行：

1

./mini ir examples/write_only_capture.lang

完整输出是：

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


x0.cell = cell 0
f.0 = closure lambda0 [x0.cell]
put4.cell = cell f.0
t.1 = load put4.cell
check-closure t.1
t.2 = call t.1 42
t.3 = load x0.cell
return t.3
lambda0(value2, self-cell: -, captures: [x1.cell]):
  value3.cell = cell value2
  t.0 = load value3.cell
  store x1.cell t.0
  return t.0
end lambda0

围绕同一个运行时 cell，可以看到四处对应表示：

1
2
3
4


源码自由变量 x
创建位置的 x0.cell
closure payload 中的 capture 0
函数入口对应的 x1.cell

这四处不是四个运行时位置。x0.cell 和 x1.cell 是不同作用域里的 IR 名字，closure field 则保存带 tag 的 cell 指针；三者最终指向同一个 cell 对象。函数里的 store x1.cell t.0 因而能被外层最后的 load x0.cell 看见。

函数参数也会在每次调用时得到新位置。签名中的 value2 是本次调用传入的普通 Value，函数第一条操作：

1

value3.cell = cell value2

把它装进本次调用独有的参数 cell。以后对参数执行 set!，不会修改调用者的变量绑定。

两个 closure 可以保存同一个 cell

two_closures_share.lang 同时创建一个写函数和一个读函数：

1
2


./mini run examples/two_closures_share.lang
./mini ir examples/two_closures_share.lang

解释器结果是 42。IR 开头可以看到两个 closure 都捕获 x0.cell：

1
2
3
4
5


x0.cell = cell 40
f.0 = closure lambda0 [x0.cell]
put4.cell = cell f.0
f.1 = closure lambda1 [x0.cell]
read8.cell = cell f.1

这正是共享状态在进入汇编前的形态。若创建 closure 时先 load x0.cell 再捕获 40，写函数和读函数就只会各自保存一个旧值，程序不可能得到正确结果。

`letrec` 为什么把 self 也变成 cell

第七章的递归名字不可修改，可以直接把隐藏的 callee closure 当作 self。第八章允许对 letrec 名字执行 set!，函数体、外层 body 和已经保存的旧函数别名必须观察同一个递归绑定，因此 self 也必须是共享 cell。

lowering 顺序是：

1
2
3
4


1. 创建初值为 0 的 self cell
2. 创建 closure，并把 self cell 放在 capture 0
3. 把 closure store 回 self cell
4. 用同一个 self cell lowering 函数体和 letrec body

self_param_shadow.lang 还故意让递归名和参数都叫 f：

1

(letrec f f f (f 42))

查看 IR：

1

./mini ir examples/self_param_shadow.lang

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


f0.cell = cell 0
f.0 = closure lambda0 [f0.cell]
store f0.cell f.0
t.1 = load f0.cell
check-closure t.1
t.2 = call t.1 42
return t.2
lambda0(f2, self-cell: f1.cell, captures: []):
  f3.cell = cell f2
  t.0 = load f3.cell
  return t.0
end lambda0

IrFunction::self_cell 对应 closure 的 capture 0；普通 captures 从后面的槽开始。建立函数环境时，顺序是 self、普通 captures、参数 cell。查找从后往前进行，所以同名参数 f3.cell 正确遮蔽 self f1.cell，结果是 42。

这个 self cell 与 closure 会形成一个运行时对象环。它不是实现失误，而是可变递归绑定的自然对象图；第九章的 tracing GC 正是为了处理这类结构。

callee 检查必须排在 argument 之前

第七章已经规定：先求 callee，确认它是 closure，再求 argument。第八章有了副作用以后，这个顺序更加重要。

假设把下面程序保存为 order.lang：

1
2


(let x 0
  ((record) (set! x 1)))

它的 IR 是：

1
2
3
4
5
6


x0.cell = cell 0
t.0 = record
check-closure t.0
store x0.cell 1
t.1 = call t.0 1
return t.1

check-closure 位于 argument 的 store 之前。运行时发现空 record 不是函数后立即失败，不会先把 x 改成 1。因此 call lowering 必须保持：

1
2
3
4


callee ops
closure_check
argument ops
call

branch 后仍然紧跟 then

状态操作不会改变既定的条件分支布局。运行：

1

./mini ir examples/short_branch.lang

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


if 1 goto then0 else else0
then0:
t.0 = 42
goto end0
else0:
t.1 = record 0
check-closure t.1
t.2 = call t.1 1
t.0 = t.2
end0:
return t.0

branch 后物理上立即是 then0:。条件为真时顺序进入 then，条件为假时跳到 else。未选择分支里的 store、call 或其他操作都不会执行。

`compile` 消费同一份 IR

本章继续保持一条编译路径：

1

AST -> IrProgram -> x86-64 assembly

生成汇编：

1

./mini compile examples/counter.lang -o out.s

CLI 先调用 lower_to_ir，再把得到的 IrProgram 交给 compile_to_assembly。因此 ./mini ir 展示的 cell、load、store、capture 和检查顺序，就是汇编生成器真正消费的数据，而不是旁路的调试文本。

读完这一节，应该能用一句话概括本章 IR：环境保存位置，表达式计算值，load 和 store 在两者之间建立明确边界。

8.3 解释器：Environment 找位置，Store 保存值

8.5 汇编：把位置落成 cell 对象

本节目录