5 Intermediate Code Generation
为什么需要 IR
没有 IR:M 种语言 × N 种目标机 = M×N 个编译器。 有 IR:M 个前端 + N 个后端 = M+N 个模块。
除此之外 IR 还有两个不可替代的作用:
- 优化需要一个稳定的平台。在 AST 上做数据流分析很别扭(树形结构不便于表达"这个值从哪来、到哪去"),线性/图状 IR 才方便。
- 便于做多遍分析。前端建完 IR 之后,可以反复跑 Pass 直到收敛。
IR 的几种形态
按"离机器远近"排:
| 形态 | 特点 | 典型用途 |
|---|---|---|
| AST | 树形,最贴近源码 | 语义分析,某些解释器的执行对象 |
| DAG | AST 消除公共子表达式后的压缩形式 | 表达式优化的可视化 |
| 三地址码 TAC | 线性,x = y op z | 教学、GCC 的 GENERIC/GIMPLE |
| SSA | TAC + 每个变量只赋值一次 | LLVM IR、现代编译器标配 |
| 字节码 | 栈式或寄存器式的紧凑指令 | Java/C#/Lua/Python 虚拟机 |
| Sea of Nodes | 控制流与数据流统一成一张图 | HotSpot C2、Graal |
三地址码(Three-Address Code)
每个指令最多三个操作数,最多一个运算符:
x = y op z // 二元运算
x = op y // 一元运算
x = y // 赋值
goto L // 无条件跳
if x relop y goto L // 条件跳
param x / call p, n / return y // 过程调用
x = y[i] / y[i] = x // 数组
x = &y / x = *y / *x = y // 取址/解引用"三地址"指两个源 + 一个目的。为什么这样设计?因为绝大多数目标机指令就是这个形状(add r1, r2, r3),从三地址码到机器码的映射最直接。
表达式 a = b * c + b * d 的 TAC:
t1 = b * c
t2 = b * d
t3 = t1 + t2
a = t3临时变量 t1, t2, ... 是编译器造的,对应后面要分配的虚拟寄存器。
四元式 / 三元式 / 间接三元式
同一件事的三种记账方式:
四元式: (op, arg1, arg2, result) ( *, b, c, t1 )
三元式: (op, arg1, arg2) + 隐式序号 (0) (*, b, c)
间接三元式: 用指针数组引用三元式,便于重排四元式最常用——结果字段显式,优化时改写方便。三元式省空间但优化时要重排就得改引用。
SSA(Static Single Assignment)
核心约束:每个变量只被赋值一次,且每个使用都只有一个定义到达。
// 非 SSA // SSA
x = 1 x1 = 1
x = x + 1 x2 = x1 + 1
y = x * 2 y1 = x2 * 2控制流汇合处,多个版本"合并",需要 φ(phi)函数:
if (c) { x1 = 1; } else { x2 = 2; }
x3 = φ(x1, x2); // 取决于从哪个分支进来
y = x3 + 1SSA 为什么好?
- 定义-使用关系显式:
x3只有一处定义,不用做 reaching-definitions 数据流分析 - 优化算法大幅简化:常量传播、DCE、GVN 在 SSA 上都有近乎线性的算法
- 寄存器分配的干扰图更精确:变量的 live range 天然被版本切碎了
代价是要构造 SSA(插 φ 函数)和析构 SSA(寄存器分配时把 φ 变成拷贝)。构造算法见后文。
栈式 vs 寄存器式字节码
// a = b + c
// 栈式(JVM) // 寄存器式(Lua 5.x, Dalvik)
iload_1 // 压 b LOAD R1, b
iload_2 // 压 c LOAD R2, c
iadd // 弹两个压和 ADD R3, R1, R2
istore_0 // 弹到 a STORE a, R3- 栈式:指令紧凑(不用编码寄存器号),便于在栈机上解释;但每条指令有隐式操作数,数据流分析不便
- 寄存器式:指令条数少(同样的计算少 30%~40% 指令),更适合 JIT;但指令更宽
Lua 5.0 → 5.1 从栈式改成寄存器式,解释器提速约 20%,就是省掉了大量 push/pop。
声明语句的翻译
核心是类型 + 存储布局。
int a, b; → 符号表: a@(type=int, offset=0), b@(type=int, offset=4)
float f[10]; → f@(type=array(10,float), base=8, size=40)
struct S { int x; double y; }; → 计算字段偏移(考虑对齐!)类型表达式要能被递归地表示:
array(n, T), record(field→T), pointer(T), function(params→T)宽度与对齐:struct S { char c; int i; } 不是 5 字节,通常 8 字节(i 要 4 字节对齐)。布局计算错一点,和 ABI 对不上,链接出来的程序直接崩。
表达式的翻译
简单表达式
E → E₁ + E₂ { E.place = newtemp(); emit(E.place = E₁.place + E₂.place); }
E → id { E.place = lookup(id).place; }
E → num { E.place = newtemp(); emit(E.place = num.val); }newtemp() 每调用一次给一个新名字(t1, t2, ...),emit() 追加一条指令。
数组元素
一维数组 A[i],元素宽 w,基址 base:
二维行优先 A[i][j],每行 n2 个:
生成的 TAC:
t1 = i * 4 // 元素宽 4
t2 = base + t1
t3 = *t2 // 取值注意 row-major(C)vs column-major(Fortran) 的差别,以及循环顺序对缓存命中率的影响——for i: for j: A[i][j] 和 for j: for i: A[i][j] 在 C 里性能可以差好几倍。
类型强制
int + float 要先插入转换:
t1 = (float) i
t2 = t1 + f转换节点是后续"强度削弱/常量折叠"的处理对象,也可能在后端被优化掉。
控制流的翻译
布尔表达式短路
a < b && c < d 不该把两边都算出来再 and。正确做法是用跳转表达短路:
if a < b goto L1
goto Lfalse
L1: if c < d goto Ltrue
Lfalse:|| 同理。关键在于 true/false 两个出口标签,由上下文决定。
回填(Backpatching)
问题:生成跳转时,目标标签的地址还不知道。
if (a < b) { ... } else { ... }
// 翻译 if 时,还不知道 else 分支在哪、整个 if 之后在哪解法:先留空,后填。
makelist(i):创建只含指令 i 的列表merge(p, q):合并两个列表backpatch(p, L):把 p 中所有指令的目标填成 L
E → E₁ && E₂
{ backpatch(E₁.truelist, nextquad());
E.truelist = E₂.truelist;
E.falselist = merge(E₁.falselist, E₂.falselist); }nextquad() 返回下一条指令的地址——正好是 E₂ 的开始。这样一遍扫描就能生成完整跳转,不用回头改。
if / while / for
if-then-else:
if E goto Ltrue
goto Lfalse
Ltrue: S1
goto Lnext
Lfalse: S2
Lnext:while:
Ltest: if E goto Lbody
goto Lnext
Lbody: S
goto Ltest
Lnext:for (init; cond; step) body 脱糖为 while 后:
init
Ltest: if cond goto Lbody
goto Lnext
Lbody: body
step
goto Ltest
Lnext:注意 step 在 body 之后——continue 应该跳到 step 而不是 Ltest,这就是脱糖时要小心的地方。
switch 的下界优化
不是简单的一串 if-else。三种策略:
| 情况 | 策略 |
|---|---|
| 分支多且值密集 | 跳转表(jumptable,) |
| 分支少 | 线性比较链 |
| 值稀疏 | 二分比较树 |
// 密集 case 的跳转表
static void* table[] = {&&L0, &&L1, &&L2, &&Ldefault};
if (v < 0 || v > 2) goto Ldefault;
goto *table[v];编译器会根据 case 数量和值的分布自动选,这也是为什么写稀疏的 case(如 1, 10000, 500000)编译出来比 if-else 快不了多少。
过程调用
活动记录(Activation Record / 栈帧)
┌─────────────────┐ 高地址
│ 实参 n..1 │ 调用者压入
│ 返回地址 │
│ 控制链(旧 FP) │◄─ FP
│ 局部变量 │
│ 临时变量 │
│ 寄存器保存区 │◄─ SP
└─────────────────┘ 低地址调用序列(calling sequence):
调用者: 被调者:
保存 caller-save 寄存器 保存旧 FP;FP = SP
逐个 param arg SP -= frameSize
call f 保存 callee-save 寄存器
清理实参 ... 函数体 ...
恢复 caller-save 恢复 callee-save
SP = FP;恢复 FP
return**调用约定(ABI)**必须前后端一致:谁保存哪些寄存器、参数怎么传(寄存器还是栈)、栈往哪长、谁清理参数。x86-64 SysV 和 Windows x64 就不一样(整数参数寄存器分别是 rdi,rsi,rdx,rcx,r8,r9 和 rcx,rdx,r8,r9)。
嵌套作用域的访问链
Pascal 这类允许嵌套函数定义的语言,内层函数要能访问外层变量。解法是访问链(access link),或者更彻底的 lambda lifting / closure conversion(把自由变量打包进闭包对象)。
基本块与 CFG
基本块(Basic Block):一个最大化的指令序列,满足
- 只有第一条指令能作为入口(没有从中间跳进来的)
- 只有最后一条指令能作为出口(没有中间跳出去的)
划分算法:
- 找出所有 leader(首指令、跳转目标、跳转指令的下一条)
- 每个 leader 到下一个 leader 之前(或下一个跳转/返回之前)就是一个基本块
控制流图(CFG):块是顶点,跳转关系是有向边。
┌──────┐
│ B1 │ if (a<b)
└──┬───┘
T ↙ ↘ F
┌────┐ ┌────┐
│ B2 │ │ B3 │
└──┬─┘ └──┬─┘
↘ ↙
┌────┐
│ B4 │
└────┘CFG 是几乎所有机器无关优化的基础设施:
- 到达定值(Reaching Definitions)
- 活跃变量(Live Variables)
- 可用表达式(Available Expressions)
这三个经典数据流分析都是在 CFG 上解方程求不动点。
SSA 构造
支配关系
节点 支配(),若从入口到 的每条路径都经过。
- 直接支配者(idom):最近的严格支配者。构成支配树,父节点是 idom。
- 支配边界(Dominance Frontier): 支配 的某个前驱,但不严格支配
插 φ 的规则
迭代支配边界(Iterated Dominance Frontier):在变量 的所有定义点 的 处插入 φ 函数。
算法(Cytron et al.)分两步:
- 计算支配树和支配边界
- 对每个变量,从定义点集合出发,沿迭代支配边界扩张,在扩张到的块开头插 φ
之后做完变量重命名(每个赋值给新版本号,使用处沿支配树查找最近的支配定义),就得到了 SSA。
为什么是支配边界? 因为 φ 要放在"多个不同定义可能汇合"的点,也就是刚好在支配关系"失守"的边界上。这个位置由支配精确地刻画出来了。
一个完整的例子
int sum(int n) {
int s = 0;
for (int i = 1; i <= n; i++)
s += i * 2;
return s;
}TAC:
sum:
s = 0
i = 1
L_test:
if i <= n goto L_body
goto L_end
L_body:
t1 = i * 2
s = s + t1
i = i + 1
goto L_test
L_end:
return s转 SSA(循环体会合点 L_body 需要 φ):
sum:
s1 = 0
i1 = 1
goto L_test
L_test:
s2 = φ(s1, s4)
i2 = φ(i1, i4)
if i2 <= n goto L_body
goto L_end
L_body:
i3 = i2 * 2
s3 = s2 + i3
i4 = i2 + 1
goto L_test
L_end:
return s2优化后(强度削弱 i*2 → i+i,归纳变量识别,常量传播……最终可能整个被 GCC 识别成闭式 n*(n+1)):
sum:
t = n * (n + 1)
return t——这个"整段循环被一个乘法替换"的结果,正是中间代码 + 多遍优化才能做到的事。直接在 AST 上生成目标码是做不到的。
设计 IR 的经验
- IR 要能被打印成人类可读的文本。LLVM IR、GIMPLE 都能 dump 出来读,这是调试优化器的唯一现实手段。
- 给每条 IR 指令一个价值号(value numbering),便于做 GVN/CSE。
- SSA 值得做。前期投入大,但后面每个优化 Pass 都变简单。
- 保留调试信息(location)。IR 会被反复变换,丢了位置就报不了准确的错、也调不了优。
- IR 指令集要小。指令种类越少,每个 Pass 要考虑的情况越少。LLVM 核心 IR 只有几十种指令。
常见坑
- 临时变量无限增长:
newtemp()不加限制会让寄存器分配压力爆表。真实编译器会限制虚拟寄存器数量并做合并(coalescing)。 - 短路求值写成非短路:
a && f()里f()不能有副作用地被调用——语义就错了。 - 回填列表忘了 merge,导致某个分支的跳转目标没被填上,生成的是
goto 0。 - 数组下标忘了减下界:
low != 0时(Fortran 默认从 1 开始)直接base + i*w就错位了。 - 调用约定前后端不一致:编译器认为参数在寄存器,库函数以为在栈上,跑起来随机崩。
- SSA 析构时丢失并行拷贝语义:φ 的多个源同时赋值,析构时直接生成一串
mov可能互相覆盖(如swap)。要用并行拷贝序列化(拆成临时变量或找环)。
参考
- 龙书 第 6 章(Intermediate-Code Generation)、第 9 章(Machine-Independent Optimizations)
- LLVM Language Reference
- Cytron et al., Efficiently Computing Static Single Assignment Form and the Control Dependence Graph(1991)
- 《SSA Book》(Static Single Assignment Book, 2022)