中间代码生成
中间代码生成
在词法、语法、语义分析之 后,编译器并不会直接生成目标机器代码,而是先把源程序翻译成一种"不高不低"的中间表示(Intermediate Representation,IR)。IR 比源语言简单,比机器指令抽象,是前端和后端之间的一座桥。
通俗理解:把 IR 想成"世界语"。中文、英文、法文都先翻成世界语,再从世界语翻到日语、韩语、俄语。如果 M 种源语言直接对 N 种目标机器,需要 M × N 个翻译器;引入世界语后只需要 M + N 个,成本从乘法降到加法。
除了解耦,IR 还有第二个好处:机器无关优化(常量折叠、公共子表达式消除、死代码删除)几乎都是在 IR 层做的,因为此时既保留了程序的语义结构,又摆脱了源语言的语法细节。
常见的 IR 形式
不同编译器阶段常用不同粒度的 IR:
-
AST(抽象语法树):最高层的 IR,几乎是源程序结构的直接映射。适合做类型检查、语义分析,但不方便描述控制流跳转。
-
三地址码(Three-Address Code):每条指令最多有三个地址,一次只做一个操作,形如
x = y op z。它是 IR 的主力形式,介于 AST 和汇编之间,非常适合优化。 -
DAG(有向无环图):把一个基本块内的表达式画成图,公共子表达式自然合并成同一个节点,非常适合局部优化。
-
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 就只是换了套皮。中间代码生成的核心思想始终一致:给程序找一种既方便优化又不依赖具体机器的表达形式。