5 Intermediate Code Generation

为什么需要 IR

没有 IR:M 种语言 × N 种目标机 = M×N 个编译器。 有 IR:M 个前端 + N 个后端 = M+N 个模块。

除此之外 IR 还有两个不可替代的作用:

  1. 优化需要一个稳定的平台。在 AST 上做数据流分析很别扭(树形结构不便于表达"这个值从哪来、到哪去"),线性/图状 IR 才方便。
  2. 便于做多遍分析。前端建完 IR 之后,可以反复跑 Pass 直到收敛。

IR 的几种形态

按"离机器远近"排:

形态特点典型用途
AST树形,最贴近源码语义分析,某些解释器的执行对象
DAGAST 消除公共子表达式后的压缩形式表达式优化的可视化
三地址码 TAC线性,x = y op z教学、GCC 的 GENERIC/GIMPLE
SSATAC + 每个变量只赋值一次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 + 1

SSA 为什么好?

  • 定义-使用关系显式: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:

addr(A[i])=base+(i−low)×w\text{addr}(A[i]) = \text{base} + (i - \text{low}) \times w

二维行优先 A[i][j],每行 n2 个:

addr=base+((i−l1)×n2+(j−l2))×w\text{addr} = \text{base} + \big((i - l_1) \times n_2 + (j - l_2)\big) \times w

生成的 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,O(1)O(1))
分支少线性比较链
值稀疏二分比较树
// 密集 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):一个最大化的指令序列,满足

  • 只有第一条指令能作为入口(没有从中间跳进来的)
  • 只有最后一条指令能作为出口(没有中间跳出去的)

划分算法:

  1. 找出所有 leader(首指令、跳转目标、跳转指令的下一条)
  2. 每个 leader 到下一个 leader 之前(或下一个跳转/返回之前)就是一个基本块

控制流图(CFG):块是顶点,跳转关系是有向边。

     ┌──────┐
     │  B1  │  if (a<b)
     └──┬───┘
   T ↙   ↘ F
┌────┐  ┌────┐
│ B2 │  │ B3 │
└──┬─┘  └──┬─┘
    ↘    ↙
    ┌────┐
    │ B4 │
    └────┘

CFG 是几乎所有机器无关优化的基础设施:

  • 到达定值(Reaching Definitions)
  • 活跃变量(Live Variables)
  • 可用表达式(Available Expressions)

这三个经典数据流分析都是在 CFG 上解方程求不动点。

SSA 构造

支配关系

节点dd 支配nn(d dom nd\ \text{dom}\ n),若从入口到nn 的每条路径都经过dd。

  • 直接支配者(idom):最近的严格支配者。构成支配树,父节点是 idom。
  • 支配边界(Dominance Frontier):DF(d)={n∣dDF(d) = \{n \mid d 支配nn 的某个前驱,但不严格支配n}n\}

插 φ 的规则

迭代支配边界(Iterated Dominance Frontier):在变量vv 的所有定义点dd 的DF+(d)DF^+(d) 处插入 φ 函数。

DF+(S)=迭代求 DF 直到不动点DF^+(S) = \text{迭代求 } DF \text{ 直到不动点}

算法(Cytron et al.)分两步:

  1. 计算支配树和支配边界
  2. 对每个变量,从定义点集合出发,沿迭代支配边界扩张,在扩张到的块开头插 φ

之后做完变量重命名(每个赋值给新版本号,使用处沿支配树查找最近的支配定义),就得到了 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)