跳到主要内容

中间代码生成

中间代码生成​

在词法、语法、语义分析之后,编译器并不会直接生成目标机器代码,而是先把源程序翻译成一种"不高不低"的中间表示(Intermediate Representation,IR)。IR 比源语言简单,比机器指令抽象,是前端和后端之间的一座桥。

通俗理解:把 IR 想成"世界语"。中文、英文、法文都先翻成世界语,再从世界语翻到日语、韩语、俄语。如果 M 种源语言直接对 N 种目标机器,需要 M × N 个翻译器;引入世界语后只需要 M + N 个,成本从乘法降到加法。

除了解耦,IR 还有第二个好处:机器无关优化(常量折叠、公共子表达式消除、死代码删除)几乎都是在 IR 层做的,因为此时既保留了程序的语义结构,又摆脱了源语言的语法细节。

常见的 IR 形式​

不同编译器阶段常用不同粒度的 IR:

  1. AST(抽象语法树):最高层的 IR,几乎是源程序结构的直接映射。适合做类型检查、语义分析,但不方便描述控制流跳转。

  2. 三地址码(Three-Address Code):每条指令最多有三个地址,一次只做一个操作,形如 x = y op z。它是 IR 的主力形式,介于 AST 和汇编之间,非常适合优化。

  3. DAG(有向无环图):把一个基本块内的表达式画成图,公共子表达式自然合并成同一个节点,非常适合局部优化。

  4. SSA(静态单赋值):每个变量只被赋值一次,配合 φ 函数处理分支合并,是现代编译器(LLVM、GCC、V8)优化的核心表示。这一块内容量大,我们放到下一章展开。

三地址码在实现层面又有几种存储方式:

  • 四元式(Quadruple):(op, arg1, arg2, result),四个字段全展开,最直观,也最占空间。
  • 三元式(Triple):(op, arg1, arg2),用指令自身的位置当结果的引用,节省一个字段,但一旦重排指令,所有引用都要跟着改。
  • 间接三元式(Indirect Triple):三元式外面再套一层指针数组,重排时只需要改数组,三元式本体不动,兼顾了紧凑和灵活。

一个例子:三地址码与 DAG​

用一句常见的赋值语句来看具体形态:a = b * -c + b * -c。翻成三地址码是:

t1 = - c
t2 = b * t1
t3 = - c
t4 = b * t3
t5 = t2 + t4
a = t5

对应的四元式表如下:

序号  op     arg1  arg2  result
0 uminus c _ t1
1 * b t1 t2
2 uminus c _ t3
3 * b t3 t4
4 + t2 t4 t5
5 = t5 _ a

肉眼可见 t1 和 t3、t2 和 t4 完全重复。如果画成 DAG,节点会自动合并:

        =
|
+
/ \
* * <-- 同一个节点
/ \
b uminus
|
c

DAG 里 b * -c 只出现一次,从中可以直接生成消除了公共子表达式的三地址码:

t1 = - c
t2 = b * t1
t3 = t2 + t2
a = t3

同一句表达式,代码量减少了一半。这就是"IR + 图结构"能带来的直接收益。

类型检查与转换​

在生成 IR 的同时,编译器还会做类型系统相关的事:

  • 静态类型检查:确认每个运算的操作数类型是允许的,例如禁止把结构体和整数相加。
  • 类型推导:像 auto、let 这类没有显式类型的声明,需要从初始化表达式反推。
  • 类型转换:int + double 要先把 int 提升到 double,这一步会在 IR 里插入一条显式的转换指令,例如 t2 = (double) t1。
  • 类型兼容规则:数组和指针在 C 里是可退化的,但在 Rust 里就不行;结构体(记录类型)要按字段名和字段类型逐一对比。

好的做法是在 IR 里把所有隐式转换都变显式,让后端不必再猜测。

控制流语句的翻译​

高级语言的 if、while、for 到了三地址码里都要拆成"条件跳转 + 标号"的形式。以 while (a < b) { a = a + 1; } 为例:

L1: if a >= b goto L2   ; 条件不满足就跳出
a = a + 1
goto L1
L2:

&& 和 || 的翻译要利用短路求值。表达式 a < b && c < d 只有 a < b 为真时才会评估右半边:

    if a >= b goto Lfalse
if c >= d goto Lfalse
; true 分支代码
goto Lend
Lfalse:
; false 分支代码
Lend:

break 和 continue 的处理靠"记住当前循环的出口/回跳标号"。翻译进入循环时把 break 的目标压栈,遇到 break 时生成一条 goto 到栈顶的标号即可,continue 同理。

回填技术​

上面的翻译有一个尴尬:写 if a < b 时还没生成 true 分支的代码,我们根本不知道跳转的目标标号在哪。传统做法是先留个空槽,等目标位置确定后再回来填,这就是回填(backpatching)。

具体做法是给每个布尔表达式维护两个链表:

  • truelist:所有还没确定"真时该跳到哪"的跳转指令编号。
  • falselist:所有还没确定"假时该跳到哪"的跳转指令编号。

翻译 a < b 生成两条指令:

100: if a < b goto _   ; truelist = {100}
101: goto _ ; falselist = {101}

当外层语法结构确定了 true 出口在 200,就把 truelist 里的每条指令的目标改成 200,falselist 同理。这种链表拼接的写法可以在单遍翻译里完成,不用回头改 AST。

现代 IR:LLVM 一瞥​

现代编译器基本都用 SSA 形式的 IR,最有代表性的是 LLVM IR。它的语法非常"像汇编又像 C":

define i32 @add(i32 %a, i32 %b) {
entry:
%1 = add i32 %a, %b
%2 = mul i32 %1, 2
ret i32 %2
}
  • i32 表示 32 位整数,是显式类型。
  • %a、%b、%1、%2 都是 SSA 值,每个名字只被赋值一次。
  • 每条指令基本对应一次三地址运算,和我们前面讲的三地址码几乎是一回事,区别在于类型是显式的,且天生就是 SSA。

GCC 的 GIMPLE、V8 的 Sea-of-Nodes、Java 的字节码本质上都是"某种带类型的三地址码 + 控制流图"。学会读三地址码,再看这些工业级 IR 就只是换了套皮。中间代码生成的核心思想始终一致:给程序找一种既方便优化又不依赖具体机器的表达形式。