第5章 中间代码（独立于机器的表示） Intermediate Representations

一、导读

1.1 本章学习目标

理解中间表示（IR）在编译器架构中的桥梁作用及其设计目标

掌握三地址码（Three-Address Code）的语法、语义及其与源语言的对应关系

深入理解静态单赋值形式（SSA）的定义、优势及 phi 函数的作用

掌握控制流图（CFG）的构建方法，理解基本块的划分规则

了解过程（函数）的 IR 表示，包括调用约定、参数传递和活动记录

学会从 AST 生成中间代码的翻译方案（语法制导翻译）

理解不同 IR 层次（高层 IR、中层 IR、低层 IR）的设计权衡

1.2 为什么本章如此重要

中间表示是编译器设计中最具创造性和影响力的部分。它既是前端分析成果的凝练，又是后端优化的操作对象。IR 的设计质量直接决定了优化算法的实现难度、编译器的可扩展性以及最终生成代码的质量。可以说，一个编译器的核心竞争力往往体现在其 IR 的设计上。

从历史角度看，IR 的演进反映了编译器技术的进步。早期的编译器直接从 AST 生成目标代码，没有独立的中间表示，这使得优化极其困难。1970 年代，三地址码的引入使得优化可以在独立于机器的层面上进行。1990 年代，SSA 形式的普及革命性地简化了数据流分析，使得许多之前难以实现的优化变得简单高效。2000 年代，LLVM 的 IR 设计进一步推动了模块化和可组合的编译器架构，成为现代编译器工程的标杆。

从实践角度看，理解 IR 不仅对编译器开发者重要，对程序开发者同样有价值。许多性能问题的根源可以通过分析 IR 来发现；调试信息、覆盖率分析、性能 Profile 等工具都依赖 IR 层面的信息。掌握 IR 的知识，有助于你更深入地理解程序的行为和编译器的决策。

1.3 核心问题引导

为什么编译器不直接从 AST 生成目标代码，而需要中间表示？

三地址码为什么选择"最多三个操作数"的形式？更多或更少操作数会有什么影响？

SSA 形式中 phi 函数的语义是什么？为什么需要它？如何避免 phi 函数过多导致的问题？

控制流图中，为什么基本块的定义要求"只有一个入口和一个出口"？

如何从高级语言的控制结构（if/while/for/break/continue）生成控制流图？

函数的中间代码表示如何处理递归调用和嵌套作用域？

为什么 LLVM 选择基于 SSA 的 IR，而不是传统的三地址码？

二、核心概念详解

2.1 三地址码（约 700 字）

三地址码（Three-Address Code, TAC）是最经典的中间表示形式之一。每条三地址码指令的形式为 x = y op z，其中 x、y、z 是临时变量或源程序变量，op 是运算符（算术运算、逻辑运算、地址运算等）。"三地址"指的是每条指令最多涉及三个操作数（两个源操作数和一个目标操作数）。

三地址码的指令集通常包括以下几类。算术运算：t1 = t2 + t3、t1 = t2 * t3、t1 = -t2 等。逻辑运算：t1 = t2 < t3、t1 = t2 && t3 等。条件跳转：if t1 > t2 goto L、goto L 等。无条件赋值：x = y、x = *y（指针解引用）、*x = y（指针赋值）等。函数调用：x = call f, n（调用函数 f，参数个数为 n）和 param x（传递参数 x）等。地址运算：x = &y（取地址）等。

以 C 语言代码 a = b + c * d; 为例，对应的三地址码为：

t1 = c * d
t2 = b + t1
a = t2

三地址码的优势在于其简洁性和规整性：每条指令只做一件简单的事情，便于分析和变换。临时变量（t1、t2 等）的引入消除了表达式中的嵌套结构，使得每条指令的语义清晰明确。这种规整性使得数据流分析、依赖分析等优化算法可以逐条指令处理，大大简化了实现。

三地址码的不足在于它仍然是线性表示，对于控制流的表达需要借助标签（Label）和跳转指令。此外，三地址码中的变量可以被多次赋值，这使得分析变量的定义-使用关系变得复杂——这正是 SSA 形式要解决的问题。

2.2 静态单赋值形式（SSA）（约 800 字）

静态单赋值形式（Static Single Assignment, SSA）是一种特殊的中间表示约束：每个变量在程序中只被赋值一次，即每个变量只有一个定义点。如果源程序中某个变量被多次赋值，SSA 形式会为每次赋值创建一个新版本（如 x1、x2、x3），并在控制流汇合处使用 phi 函数 选择正确的版本。

例如，源程序中的循环：

x = 1;
while (cond) {
  x = x + 1;
}
use(x);

转换为 SSA 形式后：

x1 = 1;
x2 = phi(x1, x3);    // 循环入口：如果从循环前来，取 x1；如果从循环体来，取 x3
x3 = x2 + 1;
use(x2);              // 注意：循环后使用的是 x2 还是 x3 取决于控制流

phi 函数 x = phi(a, b) 的语义是：根据控制流的前驱基本块选择值。如果控制流从第一个前驱块到达，x 取 a 的值；如果从第二个前驱块到达，x 取 b 的值。phi 函数不是真正的运行时操作，它只在 SSA 的语义层面起作用，在转换回普通形式时被消除。

SSA 形式的核心优势在于简化数据流分析。在传统形式中，分析变量 x 在某点的可能值需要追踪所有对 x 的赋值；在 SSA 形式中，每个版本的变量只有一个定义，到达-定义（Reaching Definition）分析变得平凡。这使得许多优化算法（如常量传播、死代码消除、公共子表达式消除）在 SSA 上实现更加简单高效。

SSA 的构建算法基于控制流图的支配边界（Dominance Frontier）概念。变量 x 的每个定义 d 的支配边界是那些"被 d 支配但又不严格被 d 支配"的基本块集合。在这些基本块的开头需要插入 phi 函数。算法首先计算支配树和支配边界，然后为每个变量的每个定义在相应的支配边界插入 phi 函数，最后对变量进行重命名（Renaming），确保每个版本只被赋值一次。

现代编译器广泛采用 SSA 形式。GCC 从 4.x 版本开始使用 SSA 作为内部 IR 的基础，LLVM 的 IR 从一开始就基于 SSA 设计。SSA 已成为现代编译器优化的标准基础。

2.3 控制流图（CFG）（约 600 字）

控制流图（Control Flow Graph, CFG）是程序控制结构的图表示。它以基本块（Basic Block）为节点，以控制转移（Control Flow Edge）为有向边，展示程序执行时可能经过的所有路径。

基本块是最长的线性指令序列，满足两个条件：只有一个入口（第一条指令只能从块的第一条指令进入）和一个出口（控制流只能从块的最后一条指令转出）。基本块的划分算法如下：首先确定入口指令（Leader）：程序的第一条指令、条件跳转或无条件跳转的目标指令、条件跳转或无条件跳转的下一条指令。然后，每个入口指令到下一个入口指令之前（或程序结束）的指令序列构成一个基本块。

控制流图的边表示基本块之间的控制转移关系。如果基本块 B1 的最后一条指令可能将控制流转移到基本块 B2 的第一条指令，则存在从 B1 到 B2 的边。条件跳转产生两条出边（真分支和假分支），无条件跳转产生一条出边，顺序执行产生一条到下一个基本块的边（如果没有跳转）。

控制流图是进行全局优化的基础数据结构。许多优化算法（如死代码消除、常量传播、循环优化）都需要在 CFG 上进行分析。CFG 的结构特征（如循环、分支、汇合）直接影响优化的效果和难度。

支配关系（Dominance）是 CFG 上的重要概念。节点 d 支配节点 n（记为 d dom n），如果从入口到 n 的所有路径都必须经过 d。支配关系是构建 SSA 形式、识别自然循环等高级分析的基础。支配树的最近公共祖先（LCA）还用于 phi 函数的放置。

2.4 从 AST 到中间代码的翻译（约 500 字）

从 AST 生成中间代码的过程称为中间代码生成或语法制导翻译。它遍历 AST 的每个节点，根据节点类型生成对应的中间代码指令。

对于表达式节点，翻译策略是递归地生成子表达式的代码，将结果存入临时变量，然后生成运算指令。例如，二元运算节点 a + b * c 的翻译过程：先翻译 b * c，生成 t1 = b * c；再翻译 a + t1，生成 t2 = a + t1。

对于控制流语句，翻译策略是使用标签和跳转指令实现控制转移。if-else 语句翻译为：计算条件表达式，若为假则跳转到 else 分支的标签；执行 then 分支后跳转到结束标签；else 分支的代码跟在后面。while 循环翻译为：循环头部设置一个标签，计算条件表达式，若为假则跳转到循环后；执行循环体后跳转回循环头部标签。

对于函数调用，翻译需要处理参数传递和返回值。常见的策略是：先依次生成参数的值并存入临时变量，然后生成 param 指令传递每个参数，最后生成 call 指令调用函数并将返回值存入目标变量。

中间代码生成还需要处理一些细节：短路线路的条件表达式（a && b 中如果 a 为假则不计算 b）、数组元素的地址计算（a[i] 的地址为 base + i * element_size）、结构体成员的偏移访问等。

三、深入分析与讨论

3.1 SSA 的构建算法详解（约 500 字）

将普通中间代码转换为 SSA 形式需要两个步骤：phi 函数插入和变量重命名。

步骤一：phi 函数插入。对于每个变量 v，首先收集 v 的所有定义点（基本块）集合 Defs(v)。然后，计算 Defs(v) 的迭代支配边界 J(Defs(v))——即 Defs(v) 中所有基本块的支配边界的并集。在 J(Defs(v)) 中的每个基本块开头插入 v = phi(v, v, ...)（参数个数等于该基本块的前驱个数）。

步骤二：变量重命名。遍历支配树（前序遍历），维护一个栈记录每个变量当前的版本。进入基本块 B 时，对于 B 中的每条指令：如果是 phi 函数 v = phi(...)，为 v 创建新版本 vi，并记录在栈中；如果是赋值 v = ...，为 v 创建新版本 vi，替换右部中所有变量引用为栈顶版本。然后递归处理 B 在支配树中的子节点。离开 B 时，恢复栈状态。

这个算法的时间复杂度与 CFG 的大小和变量数量成线性关系，非常高效。构建完成后，每个变量版本只有一个定义点，数据流分析变得极其简单：要查询变量 vi 在某点的值，只需沿支配树向上找到 vi 的定义即可。

3.2 不同 IR 层次的设计权衡（约 500 字）

现代编译器通常使用多层 IR，每层侧重不同的优化目标。

高层 IR（High-Level IR）保留更多源语言信息，如类型信息、对象模型、异常处理结构等。它便于进行语言级优化，如虚函数调用去虚拟化（Devirtualization）、内联候选选择、泛型特化等。Clang 的 AST 可以看作一种高层 IR。

中层 IR（Mid-Level IR）是独立于源语言和目标机器的通用表示。它通常基于 SSA 形式，具有显式的控制流图和类型系统。LLVM IR 就是典型的中层 IR，它既支持来自 C/C++ 的前端，也支持多种目标架构的后端。中层 IR 上进行全局优化，如循环优化、内联、常量传播等。

低层 IR（Low-Level IR）更接近目标机器，包含寄存器约束、指令选择信息、调用约定等机器相关细节。它便于进行机器级优化，如寄存器分配、指令调度、栈帧布局等。GCC 的 RTL（Register Transfer Language）就是一种低层 IR。

分层 IR 的好处是每层优化各司其职，高层优化利用语言信息，低层优化利用机器信息，中层优化处理通用问题。缺点是层间转换可能丢失信息，需要精心设计 IR 的表达能力来最小化信息损失。

3.3 过程间分析与调用图（约 400 字）

上述讨论主要关注单个过程（函数）内的中间表示。对于跨过程的分析（过程间分析，Interprocedural Analysis），需要构建调用图（Call Graph），表示程序中所有函数之间的调用关系。

调用图的节点是函数，边是调用关系。调用图对于内联优化（决定哪些函数调用应该被内联）、死函数消除（删除从未被调用的函数）、全局常量传播等跨过程优化至关重要。

构建精确的调用图在面向对象语言中尤其困难，因为虚函数调用的目标在编译期可能不确定（需要运行时类型信息）。解决方案包括保守近似（假设所有可能的重写方法都可能被调用）和基于类层次分析（CHA, Class Hierarchy Analysis）的精确分析。

四、实践案例

4.1 案例一：将 if-while 结构翻译为三地址码（约 400 字）

考虑以下 C 语言代码：

int sum = 0;
int i = 1;
while (i <= n) {
  if (i % 2 == 0) {
    sum = sum + i;
  }
  i = i + 1;
}

翻译为三地址码的过程：首先初始化 sum 和 i，然后设置循环头部标签 L1，计算条件 i <= n，若为假跳转到循环后标签 L2。循环体内计算 i % 2，判断是否为 0，若不为 0 跳转到 L3（跳过 sum 更新）。执行 sum = sum + i 后到达 L3，执行 i = i + 1，跳转回 L1。

完整的三地址码为：

sum = 0
i = 1
L1: t1 = i <= n
    if not t1 goto L2
    t2 = i % 2
    t3 = t2 == 0
    if not t3 goto L3
    t4 = sum + i
    sum = t4
L3: t5 = i + 1
    i = t5
    goto L1
L2:

4.2 案例二：将循环转换为 SSA 形式（约 400 字）

将上述循环的三地址码转换为 SSA 形式。首先识别变量的定义点：sum 在基本块 B0（初始化）和 B3（循环体更新）中定义；i 在 B0 和 B4（循环递增）中定义。

计算支配边界后，在循环头部基本块 B1 插入 phi 函数：sum1 = phi(0, sum2) 和 i1 = phi(1, i2)。然后重命名变量：B0 中 sum0=0, i0=1；B1 中使用 phi 函数的结果 sum1, i1；B3 中计算 sum2 = sum1 + i1；B4 中计算 i2 = i1 + 1。

SSA 形式清晰地展示了变量的版本关系：sum1 是循环入口处的值（可能是初始值 0 或上一次循环的结果），sum2 是循环体更新后的值。这种显式的版本追踪使得后续的优化（如循环不变量检测、归纳变量识别）变得简单直接。

五、常见误区与注意事项

5.1 误区一：SSA 形式会增加运行时开销

SSA 中的 phi 函数只是语义层面的概念，不是真正的运行时操作。在 SSA 转换回普通形式（Out-of-SSA）时，phi 函数被转换为普通的赋值指令。精心实现的 Out-of-SSA 转换可以保证不引入额外的复制开销（通过协调寄存器分配）。因此，SSA 不会增加最终代码的运行时开销。

5.2 误区二：中间代码越接近机器码越好

中间代码的设计需要在"目标无关性"和"机器相关性"之间权衡。过于接近机器码的 IR 会丧失可移植性，难以复用优化 Pass；过于抽象的 IR 则难以表达机器特定的优化机会。分层 IR 是解决这一矛盾的有效方案。

5.3 误区三：基本块越大越好

基本块的划分应该遵循"最大线性序列"原则。过小的基本块会增加 CFG 的节点数和边的数量，使分析更复杂；但基本块也不能包含条件跳转或跳转目标，否则违反了单入口单出口的约束。正确的划分是在跳转指令处自然断开。

5.4 注意事项：中间代码的可读性

中间代码虽然是给编译器使用的，但可读性仍然重要。调试编译器、分析优化效果、定位代码生成错误都需要阅读中间代码。好的 IR 设计应该有清晰的语法、一致的命名规则和合理的抽象层次。LLVM IR 的文本格式（.ll 文件）就是一个可读性优秀的范例。

六、本章小结

本章系统讲解了编译器中间表示的核心技术。三地址码以简洁的三操作数指令形式提供了独立于机器的程序表示，是中间代码的经典形式。SSA 形式通过约束每个变量只赋值一次并引入 phi 函数，极大地简化了数据流分析和优化算法的实现。控制流图以基本块为节点、控制转移为边，直观地展示了程序的控制结构，是全局优化的基础数据结构。从 AST 到中间代码的翻译需要处理表达式求值、控制流转移、函数调用等多种语言结构。现代编译器通常采用分层 IR 设计，在不同层次进行不同性质的优化。掌握中间表示技术，是理解和实现编译器优化能力的关键。

七、思考题与练习

将以下 C 语言代码翻译为三地址码：for (int i = 0; i < n; i++) { a[i] = b[i] + c[i]; }

为上述三地址码构建控制流图，标识所有基本块和控制流边。

将上述控制流图转换为 SSA 形式，插入 phi 函数并重命名变量。

证明：在 SSA 形式中，每个变量的使用点（Use）的定义点（Definition）是唯一确定的（沿支配树路径）。

实现一个从 AST 到三地址码的翻译器，处理表达式、赋值语句、if-else 和 while 循环。

调研 LLVM IR 的文本格式，阅读一段简单的 .ll 文件，说明其 SSA 结构、类型系统和指令集的特点。

比较三地址码和栈式中间表示（如 Java 字节码）的优缺点，说明各自适用的场景。

分析：为什么 phi 函数的数量与变量的定义点数量和 CFG 的结构有关？如何最小化 phi 函数的数量？