IR：编译器的草稿步骤

本节阅读量:

解释器会直接算出答案：

1

(+ 40 2) -> 42

编译器不直接返回 42。它要生成一段以后可以执行的代码。

汇编的语法很朴素，更像一行一行的机器步骤：

1
2
3


把一个数放进寄存器。
把另一个数加上去。
把结果放到某个地方。

AST 保留的是源码结构，比如“这是一个加法，左边还是一个表达式，右边也是一个表达式”。这种树形结构适合解释器递归求值，但很难一步变成汇编。

所以编译器会先把 AST 拆成一份更接近汇编、但仍然容易读的草稿。这份草稿叫 IR。

IR 是 intermediate representation，中间表示。第一次读可以先理解成：

1

编译器内部使用的一步一步计算计划。

从 AST 到步骤清单

源码：

1

(+ 40 2)

可以先变成这样的 IR：

1
2


t.0 = 40 + 2
return t.0

这里的 t.0 不是用户写的变量。它只是编译器给中间结果起的临时名字。点号表示这是编译器内部名字，后面的数字让每个临时结果都有不同的名字。

嵌套加法更能看出临时名字的作用：

1

(+ (+ 1 2) (+ 3 4))

IR 会把它拆成几步：

1
2
3
4


t.0 = 1 + 2
t.1 = 3 + 4
t.2 = t.0 + t.1
return t.2

每一步都只做一件简单的事。后面生成汇编时，也会按这些简单步骤往下翻译。

在代码里表示 IR

IR 代码在：

1
2


code/01_numbers/src/compile/ir.h
code/01_numbers/src/compile/ir.cpp

第一章只有一种 IR 操作：加法。即使这样，代码也没有把每一行都写死成 dst = lhs + rhs。每条操作都会保存自己的 OpKind，操作数也会保存自己的 OperandKind。

对应到代码，就是这些结构：

 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


enum class OperandKind {
    integer,
    temp,
};

struct Operand {
    OperandKind kind;
    long integer_value;
    std::string temp_name;
};

enum class OpKind {
    add,
};

struct Op {
    OpKind kind;
    std::string dst;
    Operand lhs;
    Operand rhs;
};

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

Operand 表示一个输入值来自哪里：

1
2


integer  直接写出来的整数，例如 40
temp     前面某一步算出来的临时变量，例如 t.0

Op 表示一步计算：

1
2
3
4


kind  这一步要做什么
dst   结果放到哪个临时变量
lhs   左输入
rhs   右输入

第一章里 kind 只有 OpKind::add。后面加入减法、比较、跳转时，可以继续增加新的 kind，再用 switch 明确处理每一种操作。

IrProgram 表示一整段 IR：

1
2


ops     前面生成的计算步骤
result  整个表达式最后的结果在哪里

result 不是已经算出来的整数结果。它也是一个 Operand，意思是“整个表达式最后要返回哪个操作数”。

无论源码是整数还是加法，都需要 result。ops 只记录中间计算步骤，result 记录这些步骤做完以后，最终答案在哪里。

对于单个整数：

1

42

它不需要任何加法步骤，所以 ops 是空的。但它仍然有 result：

1

result: 42

对于 (+ 40 2)，情况是：

1
2
3
4


ops:
  t.0 = 40 + 2
result:
  t.0

把 AST 拆成 IR

把 AST 拆成 IR 的过程常叫 lowering。第一章可以先把它理解成：

1

把树形结构拆成一步一步的计算计划。

IR 代码的对外入口是：

1

IrProgram lower_to_ir(const Expr& expr);

IrLowerer 会创建一个 IrProgram，再让 lower_expr 处理整棵 AST：

1
2
3
4
5


IrProgram lower(const Expr& expr) {
    IrProgram program;
    program.result = lower_expr(expr, program);
    return program;
}

这行很重要：

1

program.result = lower_expr(expr, program);

lower_expr 返回的不是整数，而是一个 Operand，也就是“这个表达式的结果在哪里”。这个返回值最后会成为整个程序的 result。

IrLowerer 还保存一个计数器，用来生成临时变量名：

1

next_temp_ = 0

每生成一个新的中间结果，就取一个新名字：

1
2
3


t.0
t.1
t.2

核心函数是 lower_expr：

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


Operand lower_expr(const Expr& expr, IrProgram& program) {
    switch (expr.kind) {
    case ExprKind::integer: {
        const auto& int_expr = static_cast<const IntExpr&>(expr);
        return Operand::integer(int_expr.value);
    }
    case ExprKind::add: {
        const auto& add_expr = static_cast<const AddExpr&>(expr);
        Operand lhs = lower_expr(*add_expr.lhs, program);
        Operand rhs = lower_expr(*add_expr.rhs, program);
        std::string name = "t." + std::to_string(next_temp_++);
        program.ops.push_back({OpKind::add, name, std::move(lhs), std::move(rhs)});
        return Operand::temp(name);
    }
    }

    throw std::runtime_error("unknown expression kind");
}

如果看到 Int(40)，它不需要生成新步骤，直接返回整数操作数 40。

如果看到 Add(lhs, rhs)，它会先处理左右两个子表达式。左右两边处理完以后，才生成一条 add IR，把结果放进新的临时变量，例如 t.0。最后返回临时变量操作数 t.0。

第二个参数 program 是正在积累的 IR。处理左右子表达式时，可能会继续往同一个 program.ops 里追加步骤。

std::move(lhs) 和 std::move(rhs) 可以继续按 parser 那里的理解来读：

1

把已经处理好的左右操作数，交给这条 IR 操作保存。

放进 program.ops 之后，当前这两个局部变量就不再使用。

IR 和 AST 的区别

可以先这样记：

1
2


AST 保留源码结构，像一棵树。
IR 记录计算步骤，像一张清单。

解释器看到 Add，会马上递归求值，最后得到一个整数。

编译器看到 Add，不会马上给用户答案，而是生成后续要执行的步骤。

运行 IR 命令

运行：

1
2
3


cd code/01_numbers
make
./mini ir examples/add.lang

输出：

1
2


t.0 = 40 + 2
return t.0

再运行：

1

./mini ir examples/nested_add.lang

输出：

1
2
3
4


t.0 = 1 + 2
t.1 = 3 + 4
t.2 = t.0 + t.1
return t.2

第一章先用 IR 当中间草稿。下一节会把这份草稿里的步骤翻译成真正的 x86-64 汇编。

1.5 解释器：沿着 AST 直接算结果

1.7 汇编基础：寄存器、栈槽和返回值

本节目录