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

一、导读

1.1 本章学习目标

理解中间表示（IR）在编译器架构中的核心定位：前后端解耦的桥梁

掌握三地址码（Three-Address Code）的结构、特点及其作为线性 IR 的优势与局限

深入理解静态单赋值形式（SSA）的定义、构造算法（Phi 函数）及其对优化的革命性影响

掌握控制流图（CFG）的构建方法，理解基本块（Basic Block）的性质与识别算法

了解图式 IR（AST、CFG）与线性 IR（三地址码、字节码）的适用场景对比

理解多层 IR 设计（如 LLVM 的 HIR/MIR/LIR）的工程动机与实现策略

掌握从 AST 到 IR 的翻译策略，包括表达式、控制流语句和函数调用的 IR 生成

了解现代 IR 设计的前沿方向：可分析性、可变换性与目标无关性的平衡

1.2 为什么本章如此重要

中间表示是编译器设计中最具创造性的环节之一。它既不是源语言的高级抽象，也不是目标机器的低级指令，而是介于两者之间的一种"中间态"程序表示。IR 的设计质量直接决定了编译器优化的便利性和后端代码生成的效率，是编译器架构中最关键的接口层。

从架构设计的角度来看，IR 的最大贡献在于实现了源语言和目标机器的解耦。没有 IR 的编译器，每增加一种源语言就需要为每种目标机器编写一个完整的代码生成器——N 种语言和 M 种机器需要 N*M 个组件。引入 IR 后，每种语言只需要一个前端（语言到 IR 的翻译器），每种机器只需要一个后端（IR 到机器码的翻译器），总共只需要 N+M 个组件。这种解耦不仅大幅降低了编译器开发的工作量，还使得前端和后端可以独立演进——优化器的改进对所有前端和后端同时生效。

从优化技术的角度来看，IR 的设计直接影响优化算法的表达和实施效率。SSA 形式的引入是编译器优化领域最重要的突破之一——通过约束每个变量只被赋值一次，SSA 极大地简化了数据流分析，使得常量传播、死代码消除、值编号等优化算法能够以更低的计算复杂度达到更强的优化效果。现代编译器中几乎所有的关键优化都依赖于 SSA 形式。

1.3 核心问题引导

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

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

SSA 形式中的 Phi 函数是什么？它解决了什么问题？如何在控制流合并点构造 Phi 函数？

如何将高级语言的控制流结构（if-else、while、for、switch）翻译为控制流图？

为什么现代编译器（如 LLVM）采用多层 IR 设计？每层 IR 的职责是什么？

图式 IR 和线性 IR 各有什么优缺点？在编译器的不同阶段应如何选择？

IR 如何表示高级语言的特性，如异常处理、闭包、泛型？

二、核心概念详解

2.1 三地址码的结构与特点

三地址码（Three-Address Code, TAC）是最经典的线性中间表示形式。每条三地址码指令最多包含三个操作数，形式通常为 x = y op z，其中 x 是结果变量，y 和 z 是源操作数，op 是运算符。这种形式类似于汇编语言，但使用了无限数量的临时变量，且不涉及具体的机器寄存器或内存地址。

三地址码的指令集通常包括以下几类：算术和逻辑运算（如 t1 = a + b、t2 = c * d）；一元运算（如 t3 = -a、t4 = !b）；条件跳转（如 if t1 > 0 goto L1）；无条件跳转（如 goto L2）；赋值（如 x = y）；参数传递和函数调用（如 param x、call f, n）；内存操作（如 x = y[i]、x = &y、*p = x）。

三地址码的优势在于其简洁性和规整性。每条指令的操作简单明确，便于进行各种优化变换。同时，三地址码将复杂的表达式分解为一系列简单指令，使得每条指令与目标机器指令之间的映射关系更加清晰。例如，表达式 a + b * c 被分解为 t1 = b * c 和 t2 = a + t1 两条指令，每条指令都可以独立地进行优化和代码生成。

然而，三地址码也有其局限性。首先，它引入了大量的临时变量，增加了后续分析的负担。其次，变量的多次赋值使得数据流分析变得复杂——当一个变量在不同位置被赋予不同的值时，分析器需要追踪每次赋值的影响范围。这正是 SSA 形式要解决的核心问题。

2.2 静态单赋值形式（SSA）

静态单赋值形式（Static Single Assignment, SSA）是一种特殊的中间表示约束：每个变量在程序中只被赋值一次，即每个变量只有一个定值（Definition）。这意味着当一个变量在程序的不同路径上被赋予不同的值时，需要使用新的变量名来区分这些不同的赋值。

SSA 的核心挑战在于控制流合并点——当多个控制流路径汇聚到同一个程序点时，来自不同路径的变量可能具有不同的值。SSA 使用 Phi（φ）函数来解决这个问题。Phi 函数不是真正的运行时操作，而是一种记号，表示"根据控制流来源选择不同的值"。例如，在 if-else 结构的合并点，变量 x 可能来自 then 分支的 x1 或 else 分支的 x2，SSA 表示为 x3 = phi(x1, x2)，含义是：如果控制流来自 then 分支则取 x1，如果来自 else 分支则取 x2。

SSA 形式为编译器优化带来了革命性的改进。首先，变量的定义-使用链（Def-Use Chain）变得显式且唯一——每个使用点可以直接追溯到唯一的定义点，无需复杂的数据流分析。其次，常量传播变得极其简单——如果一个变量只有一个定值且该定值是常量，则该变量的所有使用点都可以直接替换为该常量。第三，死代码消除变得精确——如果一个变量的定义没有被任何使用点引用（且没有副作用），则该定义可以安全删除。

从 SSA 形式转换回普通形式（SSA 解构）需要在每个 Phi 函数处插入复制指令（Copy），并在控制流的前驱块中安排这些复制的位置。这个过程需要小心处理，以避免复制指令之间的干扰（Copy Interference）。

2.3 控制流图（CFG）

控制流图（Control Flow Graph, CFG）是程序控制流结构的图式表示。CFG 是一个有向图，节点是基本块（Basic Block），边是控制转移关系。基本块是一段线性执行的指令序列，具有单一入口（第一条指令）和单一出口（最后一条指令），块内的指令总是按顺序执行，不会中途跳转或被打断。

基本块的识别算法如下：首先确定入口指令（程序的第一个指令、所有跳转目标指令和跳转指令的后续指令），然后从每个入口指令开始，将连续的指令（直到下一个入口指令或程序结束）收集为一个基本块。最后，根据跳转指令和顺序执行关系建立基本块之间的有向边。

CFG 是进行程序分析和优化的基础数据结构。在 CFG 上可以定义多种重要的概念：路径（Path）是从入口块到某个块的节点序列；可达性（Reachability）是指从入口块是否存在路径到达某个块；支配关系（Dominance）是指如果从入口块到块 B 的所有路径都必须经过块 A，则 A 支配 B；循环（Loop）在 CFG 中表现为回边（Back Edge）——从某个块指向其支配者的有向边。

CFG 的结构直接影响优化策略的选择。例如，循环优化需要在 CFG 中识别自然循环（Natural Loop）——具有回边的 strongly connected component。循环不变量外提、归纳变量消除等优化都依赖于对循环结构的精确识别。

2.4 从 AST 到 IR 的翻译

从 AST 到 IR 的翻译是编译器前端的核心任务之一。翻译过程遍历 AST 的每个节点，为每个节点生成对应的 IR 指令序列。

表达式的翻译需要处理运算符优先级和操作数求值顺序。对于二元运算 a + b * c，翻译器先递归翻译右子树 b * c，将结果存入临时变量 t1，然后翻译左子树 a，生成指令 t2 = a + t1。对于短路求值的布尔表达式（如 a && b），翻译器需要生成条件跳转指令：先计算 a，如果 a 为假则跳转到结果位置（短路），否则继续计算 b。

控制流语句的翻译将高级结构转换为基本块和跳转指令。if-else 语句翻译为：计算条件表达式，如果为假则跳转到 else 块，then 块执行后跳转到合并点，else 块执行后也到达合并点。while 循环翻译为：循环头部是条件测试块，条件为真进入循环体，条件为假跳出循环，循环体末尾跳回条件测试。switch 语句可以翻译为一系列条件跳转（线性搜索），或在 case 数量较多时翻译为跳转表（Jump Table）以实现 O(1) 的分支选择。

函数调用的翻译涉及参数传递和返回值处理。参数按照调用约定（Calling Convention）依次放入参数寄存器或压入栈中，生成 call 指令调用目标函数，返回值从约定的寄存器或栈位置取出。

2.5 多层 IR 设计

现代编译器通常采用多层 IR 设计，在不同的编译阶段使用不同抽象层次的中间表示。这种设计的动机是：高层次的 IR 保留更多源语言的语义信息，适合进行与机器无关的高层优化；低层次的 IR 更接近目标机器的指令模型，适合进行与机器相关的低层优化和代码生成。

以 LLVM 为例，它使用三层 IR 设计。第一层是 LLVM IR（也称为 HIR/MIR），一种高级的、类型丰富的 SSA 形式 IR，保留了结构体类型、数组类型、函数类型等高级类型信息，适合进行函数内联、常量合并、循环优化等与机器无关的优化。第二层是 Machine IR（MIR），在 LLVM IR 的基础上增加了目标机器的信息，如虚拟寄存器、目标机器指令、调用约定和寄存器类，但尚未进行寄存器分配。第三层是 Selection DAG（有向无环图），一种低层次的图式 IR，用于指令选择和调度，最终生成机器码。

多层 IR 设计的优势在于：每层 IR 只关注特定层次的优化任务，避免了单一 IR 需要兼顾所有需求的复杂性；高层优化的结果可以自然地传递到低层，低层优化不会影响高层的语义信息；每层 IR 可以独立演进，添加新的优化 Pass 而不影响其他层次。

三、深入分析与讨论

3.1 SSA 构造算法与 Phi 函数放置

SSA 构造的核心问题是如何在控制流合并点正确放置 Phi 函数。一个天真的方法是在每个有多个前驱的基本块的每个变量上都放置 Phi 函数，但这会产生大量不必要的 Phi 函数。更精确的方法是基于支配 frontier（Dominance Frontier）的概念。

支配 frontier DF(X) 定义为：所有满足"X 支配其某个前驱但不严格支配它"的块的集合。直觉上，支配 frontier 是 X 的"影响力边界"——在 DF(X) 中的块，来自 X 的值和来自其他路径的值可能发生冲突。Phi 函数的放置算法是：对于变量 v 的每个定值点 d，将 Phi 函数放置在 DF(d) 中的所有块上；然后，由于新放置的 Phi 函数本身也是 v 的定值点，需要递归地将 Phi 函数放置在它们的支配 frontier 上，直到不再需要新的 Phi 函数。

这个算法的时间复杂度为 O(|E| * |V|)，其中 |E| 是 CFG 的边数，|V| 是变量数。在实际实现中，通常使用迭代支配 frontier 算法来高效地计算 Phi 函数的放置位置。构造完 SSA 形式后，还需要进行 Phi 函数的优化——删除冗余的 Phi 函数（如所有操作数相同的 Phi 函数可以直接替换为该操作数）。

3.2 IR 的设计哲学：表达力与可分析性的平衡

IR 设计面临的核心矛盾是表达力与可分析性之间的权衡。一个表达力强的 IR 能够精确地表示源语言的各种特性，但可能难以进行分析和优化；一个易于分析的 IR 可能无法表达某些高级语言特性，导致信息丢失。

以异常处理为例。C++ 的异常处理涉及 try-catch 块、栈展开（Stack Unwinding）、析构函数调用等复杂语义。如何在 IR 中表示这些语义是一个挑战。一种方法是在 IR 中引入显式的异常处理指令（如 invoke 和 landingpad），将异常控制流编码为 CFG 的额外边。这种方法保留了异常处理的完整语义，但增加了 IR 的复杂性和优化 Pass 的负担。另一种方法是在高层 IR 中保留异常处理结构，在低层 IR 中将其展开为显式的控制流。这种方法在不同层次保持了 IR 的简洁性，但需要额外的展开 Pass。

类似的设计选择也出现在闭包（Closure）、协程（Coroutine）、泛型（Generics）等高级语言特性的 IR 表示中。每种选择都有其利弊，IR 设计者需要根据编译器的整体架构和目标来做出决策。

四、实践案例

4.1 将 while 循环翻译为控制流图

以 while (i < n) { sum = sum + i; i = i + 1; } 为例，展示从高级语言到 CFG 的翻译过程。

翻译结果包含四个基本块。入口块（Entry）包含初始化指令和条件测试 t1 = i < n，如果 t1 为假则跳转到退出块（Exit）。循环体块（Body）包含 t2 = sum + i、sum = t2、t3 = i + 1、i = t3，执行完毕后跳转到循环头块（Header）。循环头块重新测试条件 t4 = i < n，为真跳转到循环体块，为假跳转到退出块。退出块包含循环后的后续代码。

这个 CFG 清晰地展示了循环的结构：Header 块是循环头，Body -> Header 的回边标识了循环的存在。基于这个 CFG，优化器可以进行循环不变量外提（如果 n 在循环中不变，可以将 i < n 的比较优化）、归纳变量识别（i 是线性递增的归纳变量）等循环优化。

4.2 LLVM IR 的实际示例

以 C 函数 int add(int a, int b) { return a + b; } 为例，展示 LLVM IR 的实际形式。

LLVM IR 使用 SSA 形式，每个变量以 % 开头（如 %a、%b、%result）。函数定义包含参数类型和返回类型（define i32 @add(i32 %a, i32 %b)）。函数体由基本块组成，每个块以标签开头（如 entry:）。指令使用三地址码形式（%result = add i32 %a, %b）。返回指令指定返回值和类型（ret i32 %result）。

LLVM IR 的类型系统比大多数 IR 更丰富——它区分 i32（32 位整数）、i64（64 位整数）、float、double、指针类型（ptr）和聚合类型（结构体、数组）。这种类型信息使得优化器能够进行更精确的分析和优化，如基于类型的别名分析（Type-Based Alias Analysis）。

五、常见误区与注意事项

5.1 误区一：IR 只是编译器的内部细节，不需要精心设计

IR 的设计是编译器架构中最关键的决策之一。一个设计不良的 IR 会使优化算法的实现变得极其困难，增加编译器的维护成本，限制编译器的可扩展性。IR 的设计需要深思熟虑，权衡表达力、可分析性、可变换性和实现复杂度。

5.2 误区二：SSA 形式一定比普通形式更好

虽然 SSA 形式在大多数优化场景下具有显著优势，但它并非万能。SSA 增加了 Phi 函数的开销，某些优化（如某些循环变换）在 SSA 形式下反而更难实现。此外，SSA 的构造和解构都需要额外的编译时间。在实际编译器中，通常在优化阶段使用 SSA 形式，在代码生成阶段转换回普通形式。

5.3 误区三：IR 应该尽可能保留源语言的高级信息

虽然保留高级信息有利于某些优化（如基于类型的优化），但过多的源语言信息会增加 IR 的复杂性，使得与目标机器相关的优化变得困难。IR 的设计需要在信息保留和信息抽象之间找到平衡点，通常通过多层 IR 来解决不同层次的需求。

5.4 注意事项：IR 的版本兼容性

对于像 LLVM IR 这样被广泛使用的中间表示，版本兼容性是一个重要的工程问题。LLVM IR 的格式在版本之间可能会有变化（如不透明指针类型的引入），依赖特定 IR 格式的外部工具（如验证器、分析器）需要随之更新。在设计 IR 时，应当考虑前向兼容性和向后兼容性的策略。

六、本章小结

本章系统介绍了编译器中间表示的设计与实现。三地址码以其简洁的三操作数形式成为经典的线性 IR，将复杂表达式分解为易于优化的简单指令。SSA 形式通过约束每个变量只被赋值一次，极大地简化了数据流分析和优化算法的实现，是现代编译器优化的基石。控制流图以基本块为节点、控制转移为边，清晰地展示了程序的控制流结构，是循环分析和数据流分析的基础。从 AST 到 IR 的翻译将高级语言结构转换为低层次的指令序列，同时保留程序的完整语义。多层 IR 设计在不同抽象层次上支持不同类型的优化，实现了编译器的模块化架构。IR 的设计是编译器工程中最具创造性和挑战性的任务之一。

七、思考题与练习

将以下 C 代码翻译为三地址码：for (int i = 0; i < 10; i++) { if (i % 2 == 0) sum += i; else product *= i; }

将第 1 题的三地址码转换为 SSA 形式，标注所有 Phi 函数及其放置位置。

手动构造以下代码的控制流图，识别其中的基本块、回边和自然循环：包含嵌套 if-else 和 while 循环的代码段。

比较 LLVM IR 和 GCC GIMPLE 的设计差异，分析它们各自的优缺点。

实现从简单表达式 AST 到三地址码的翻译器，支持算术运算、逻辑运算（含短路求值）和函数调用。

调研 SSA 构造算法，实现基于支配 frontier 的 Phi 函数放置算法，并在测试用例上验证其正确性。

分析为什么 SSA 形式使得常量传播算法的实现更加简单，并给出时间复杂度分析。

设计一种 IR 来表示以下高级语言特性：(a) 异常处理（try-catch-finally），(b) 闭包（Lambda 表达式捕获外部变量），(c) 异步操作（async/await）。讨论你的设计选择及其对优化的影响。