IR：把函数体和函数值分开

本节阅读量:

解释器可以把函数体 AST 留在内存里，等调用发生时再回来求值。编译器面对的问题不同：它最后要得到一段按地址排列的机器代码，不能把一棵 AST 当作运行时的函数值。

这一节继续使用贯穿本章的例子：

1

(let inc (lambda x (+ x 1)) (inc 41))

先看 AST：

1
2


cd code/04_functions
./mini ast examples/function_value.lang

输出是：

1

Let(inc, Lambda(x, Add(Var(x), Int(1))), Call(Var(inc), Int(41)))

AST 把 lambda 的 body 直接放在 Lambda 节点里面。可是运行程序时，遇到 lambda 不能顺势执行这个 body；它只应该产生一个以后可以调用的值。因此 lowering 必须把一棵 AST 拆成两个层次：

1
2


主程序中的 lambda 表达式     产生一个指向函数入口的值
独立的函数体                 保存真正要在调用时执行的操作

代码在：

1
2


code/04_functions/src/compile/ir.h
code/04_functions/src/compile/ir.cpp

先记住本节最核心的两次变换：

1
2
3
4
5


lambda -> 当前 ops 中的一条 function_ref
       + program.functions 中的一个独立 IrFunction

call   -> 先生成 callee 和 argument 所需的操作
       + 当前 ops 中的一条 call

IR 现在有两个代码层次

前三章的 IrProgram 只有一串主程序操作和一个结果。第四章新增 IrFunction，并让 IrProgram 保存一组函数：

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


struct IrFunction {
    std::string label;
    std::string param;
    std::vector<Op> ops;
    Operand result;
};

struct IrProgram {
    std::vector<Op> ops;
    Operand result;
    std::vector<IrFunction> functions;

    std::string dump() const;
};

这几个字段可以这样读：

1
2
3
4
5
6
7
8


IrProgram::ops          主程序运行的操作
IrProgram::result       主程序最终返回的值
IrProgram::functions    整段程序包含的独立函数体

IrFunction::label       函数入口的名字，例如 lambda0
IrFunction::param       参数的源语言名字，例如 x
IrFunction::ops         调用后才执行的函数体操作
IrFunction::result      函数体最终得到的 IR Operand

一个函数体也是“若干操作加一个结果”，但它还需要入口 label 和参数。因此没有把主程序与函数体硬塞进同一个操作列表，而是明确地用两种结构保存它们。

打印结果里的 return 来自 IrProgram::result 或 IrFunction::result，并不是一条 OpKind::return。真正进入汇编阶段时，生成器才会把这个结果搬到 %rax 并执行 retq。

新增的两种操作

第四章给 OpKind 增加了 function_ref 和 call：

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


enum class OpKind {
    copy,
    add,
    equal,
    branch,
    jump,
    label,
    function_ref,
    call,
    input,
    output,
};

函数主线真正新增的是 function_ref 和 call。完整代码末尾的 input、output 属于章末可选的 C++ runtime 实验；第一次阅读本节时先忽略，等完成函数地址和间接调用后再回来看。

它们仍然复用同一个 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;
};

不同操作使用的字段如下：

操作	含义	使用的字段
`function_ref`	取得某个函数入口的地址	`dst`、`target`
`call`	通过一个运行时值调用函数	`dst`、`lhs`、`rhs`

例如：

1
2


f.0 = function lambda0
t.1 = call inc0 41

第一行表示把 lambda0 的入口地址写入 f.0，对应：

1
2
3


kind    = function_ref
dst     = "f.0"
target  = "lambda0"

第二行表示调用 inc0 中的函数，传入 41，把返回值写入 t.1：

1
2
3
4


kind  = call
dst   = "t.1"
lhs   = temp("inc0")
rhs   = integer(41)

aggregate initializer 里偶尔出现的 Operand::integer(0) 只是没有被这种 op 使用的字段占位值。例如 function_ref 只读取 dst 和 target，不会把那两个零生成到 IR 或汇编中。

注意 OperandKind 并没有增加 function：

1
2
3
4


enum class OperandKind {
    integer,
    temp,
};

f.0 只是一个临时名字。到了汇编层，它的栈槽里会放一个 64 位代码地址；IR 本身没有给这个地址附加类型标签。这一点会在汇编页再讨论。

f.0、t.1、inc0 和 lambda0 都是编译器生成的内部名字，不是用户源码中的 identifier，因此不受源语言 letter+ 规则限制。点号和数字只帮助调试输出保持唯一、容易辨认。

lower_expr 的约定仍然成立

lowerer 的核心函数仍然是：

1

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

它的约定没有改变：

1
2


把计算 expr 所需的操作追加到当前 ops；
返回一个 Operand，说明 expr 的结果在哪里。

变化在于：现在 lowering 一个表达式时，必须同时分清三种上下文。

1
2
3


program_    整段程序；新发现的函数都登记到 program_.functions
ops         当前正在生成的操作列表；可能属于主程序，也可能属于某个函数
env         当前名字环境；把源语言变量映射到 IR Operand

主入口先建立空环境，并明确把主表达式的操作写进 program_.ops：

1
2
3
4
5


IrProgram lower(const Expr& expr) {
    Env env;
    program_.result = lower_expr(expr, program_.ops, env);
    return std::move(program_);
}

把 ops 作为参数传递很重要。如果当前在 lowering 主程序，操作进入 program_.ops；如果当前在 lowering 一个函数体，操作进入这个函数自己的 function.ops。program_ 则是整次 lowering 共用的总容器，所以即使在函数体里遇到嵌套 lambda，也能把新函数登记到整段程序中。

env 负责的是名字，不是代码归属。例如主程序的环境可能包含 inc -> inc0，但进入 lambda 后会建立一份新的函数环境。

lambda 怎样 lowering

ExprKind::lambda 的完整分支是：

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


case ExprKind::lambda: {
    const auto& lambda_expr = static_cast<const LambdaExpr&>(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,
                   ""});

    Env function_env;
    function_env.push_back({lambda_expr.param, Operand::temp(lambda_expr.param)});

    IrFunction function;
    function.label = label;
    function.param = lambda_expr.param;
    function.result = lower_expr(*lambda_expr.body, function.ops, function_env);
    program_.functions.push_back(std::move(function));

    return Operand::temp(function_value);
}

可以分五步读。

第一步，为函数入口和函数值各取一个名字：

1
2


label           lambda0    将来汇编中的代码位置
function_value  f.0        当前表达式产生的运行时值

这两个名字不能混为一谈。lambda0 是一段代码的入口；f.0 是当前操作序列里的临时值，可以继续被 let 保存或作为参数传递。

第二步，向当前 ops 追加 function_ref：

1

f.0 = function lambda0

如果 lambda 出现在主程序，这条操作进入 program_.ops；如果它嵌套在另一个函数体中，这条操作就进入外层函数的 function.ops。无论出现在哪里，求值 lambda 都只取得地址，不执行 body。

第三步，为函数体建立一份新环境：

1
2


Env function_env;
function_env.push_back({lambda_expr.param, Operand::temp(lambda_expr.param)});

此时参数 x 仍是一个符号化的 IR 名字。下一节分配栈槽时，它才会得到 -8(%rbp) 这样的机器位置。

新环境里只有参数，没有沿用调用处或创建处的 env。这是本章“不捕获外层变量”的实现边界。

第四步，把 body lowering 到 function.ops，而不是当前 ops：

1

function.result = lower_expr(*lambda_expr.body, function.ops, function_env);

第五步，把完整的函数登记到 program_.functions，再把 f.0 作为整个 lambda 表达式的结果返回。

于是一次 lambda lowering 同时产生两样东西：

1
2


当前代码中的一条 function_ref
整段程序函数列表中的一个 IrFunction

call 怎样 lowering

ExprKind::call 的完整分支短一些：

1
2
3
4
5
6
7
8


case ExprKind::call: {
    const auto& call_expr = static_cast<const CallExpr&>(expr);
    Operand callee = lower_expr(*call_expr.callee, ops, env);
    Operand argument = lower_expr(*call_expr.argument, ops, env);
    std::string dst = new_temp();
    ops.push_back({OpKind::call, dst, std::move(callee), std::move(argument), "", ""});
    return Operand::temp(dst);
}

这里固定先 lowering callee，再 lowering argument，与解释器的求值顺序一致。两边都可能是复杂表达式，它们产生的操作也都会先追加到当前 ops。等两个 Operand 都准备好后，lowerer 才追加 call。

callee 没有被写死成 lambda0。它可能来自 let 变量，也可能来自另一次调用的返回值。因此 IR 保留的是：

1

通过 lhs 中的运行时函数值发起调用

到了汇编层，这会变成间接调用 call *%rcx。

完整走一遍

重新看源码：

1

(let inc (lambda x (+ x 1)) (inc 41))

lowering 按下面的过程发生：

1
2
3
4
5
6
7


1. lower let 的 value，也就是 lambda。
2. 在主程序追加 f.0 = function lambda0。
3. 用新环境 x -> temp("x") lower 函数体，得到 t.0 = x + 1。
4. 回到主程序，把 f.0 复制到 let 局部名字 inc0。
5. 在环境中加入 inc -> temp("inc0")。
6. lower (inc 41)，得到 t.1 = call inc0 41。
7. let 结束，移除 inc 的环境绑定，返回 t.1。

运行命令：

1

./mini ir examples/function_value.lang

得到：

1
2
3
4
5
6
7
8


f.0 = function lambda0
inc0 = f.0
t.1 = call inc0 41
return t.1
lambda0(x):
  t.0 = x + 1
  return t.0
end lambda0

这里有一个容易让人停顿的小细节：t.1 在打印结果中出现在 t.0 前面。lowerer 处理 lambda 时，先进入函数体并分配了全局临时编号 t.0，回到主程序后才为调用分配 t.1；IrProgram::dump() 又固定先打印主程序，再打印函数列表。

打印位置和临时编号都不决定控制流。运行时先在主程序执行 call inc0 41，调用进入 lambda0 计算 t.0，返回后才把结果保存为 t.1。lambda0(x): 也不会在 return t.1 后面自动顺序执行，只有 call 才会进入它。

嵌套 lambda 怎样进入函数列表

这一部分用于解释“函数返回函数”，第一遍只要知道每个 lambda 都会得到一个独立函数体；函数在列表中的登记顺序可以第二遍再跟。

program_ 是整个 lowerer 共用的成员，因此函数体中遇到的 lambda 也能登记到同一个 IrProgram::functions。例如：

1

(lambda ignored (lambda x (+ x 1)))

它的 IR 是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


f.0 = function lambda0
return f.0
lambda1(x):
  t.0 = x + 1
  return t.0
end lambda1
lambda0(ignored):
  f.1 = function lambda1
  return f.1
end lambda0

外层函数体里的 f.1 = function lambda1 被写进 lambda0 自己的 ops；真正的 lambda1 函数体仍登记在整段程序的函数列表中。

这里内层 lambda1 比外层 lambda0 先打印，是因为 lowerer 必须先完成外层 body，才能把完整的 lambda0 放进函数列表；lowering body 时，内层 lambda1 已经先登记好了。汇编通过 label 引用代码位置，函数在列表里的先后顺序不影响调用。

这个例子中的内层函数不使用 ignored，所以不需要捕获。如果写成：

1

(let x 40 (lambda y (+ x y)))

lowerer 进入 lambda 后只把参数 y 放进 function_env，查找 x 时会报告 undefined variable: x。解释器只运行这段源码时会先得到 <function>，因为它尚未求值 body；真正调用这个函数时也会在查找 x 处失败。

也就是说，两条路径都不支持捕获，但错误出现的时机可能不同。闭包章节会为函数值增加环境，届时才能跨过这条边界。

到这里，编译路径变成了：

1
2
3
4


AST
-> 主程序操作 + 独立函数列表
-> function_ref / call IR
-> 代码地址和间接调用

下一步要解决的是机器层面的交接：调用者把参数放在哪里，被调用函数怎样拥有自己的局部空间，又怎样回到调用位置。

4.4 解释器：函数值和一次新的求值环境

4.6 栈帧和调用约定：让两个函数完成交接

本节目录