一、什么是中间表示(IR)
中间表示(Intermediate Representation,简称 IR)是编译器在处理源代码过程中使用的一种内部程序表示形式。
源代码通常具有较强的语言特征,例如:
int result = a + b * c;
如果编译器直接从 C 语言源代码生成 x86 机器指令,就需要在代码生成过程中同时处理:
- C 语言的语法结构。
- C 语言的类型系统。
- 表达式的运算规则。
- 变量和作用域。
- x86 指令集。
- 寄存器分配。
- 内存布局。
- 目标平台的调用约定。
这种方式会让编译器前端与后端高度耦合。
IR 的核心思想是:先将源代码转换为一种更适合编译器处理的中间形式,再基于这种形式执行优化和目标代码生成。
例如:
int result = a + b * c;
可以转换为类似三地址码的 IR:
t1 = b * c
t2 = a + t1
result = t2
这时,IR 已经不再依赖 C 语言的具体语法形式,而是将计算过程表示为明确的操作。
IR 的核心价值在于解耦编程语言与目标机器,使编译器能够复用分析、优化和代码生成能力。
二、为什么编译器需要 IR
2.1 解决前端与后端的耦合问题
假设一个编译器需要支持:
- C
- C++
- Rust
- Swift
同时需要生成:
- x86-64
- ARM64
- WebAssembly
如果每种语言都直接针对每种目标架构开发代码生成器,就需要维护大量组合关系。
例如:
| 源语言 | x86-64 | ARM64 | WebAssembly |
|---|---|---|---|
| C | 独立后端 | 独立后端 | 独立后端 |
| C++ | 独立后端 | 独立后端 | 独立后端 |
| Rust | 独立后端 | 独立后端 | 独立后端 |
| Swift | 独立后端 | 独立后端 | 独立后端 |
如果有 M 种源语言和 N 种目标架构,直接组合的实现规模可能接近:
引入统一 IR 后,可以让不同语言的前端生成 IR,再由不同目标架构的后端处理 IR。
flowchart TB
subgraph Frontend["编译器前端"]
A["C 前端"]
B["C++ 前端"]
C["Rust 前端"]
D["Swift 前端"]
end
E["统一中间表示 IR"]
subgraph Backend["编译器后端"]
F["x86-64 后端"]
G["ARM64 后端"]
H["WebAssembly 后端"]
end
A --> E
B --> E
C --> E
D --> E
E --> F
E --> G
E --> H
style A fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style D fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style E fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style F fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style G fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style H fill:#F3EDFC,stroke:#C4B2E3,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
这样,前端只需要负责将语言转换为 IR,后端只需要负责将 IR 转换为目标平台代码。
如果有 M 种前端和 N 种后端,核心适配关系可以从大量两两组合,转变为分别维护前端和后端接口,整体规模更接近:
实际工程中,不同语言的语义差异和目标平台特性仍然需要专门处理,但 IR 显著降低了系统集成成本。
2.2 提供统一的优化基础
不同编程语言可能具有不同的语法,但很多底层计算操作是相似的。
例如:
int result = a * 2 + 10;
let result = a * 2 + 10;
int result = a * 2 + 10;
这些代码在语言层面存在差异,但可以转换为相近的中间计算结构。
编译器可以在 IR 层统一执行:
- 常量折叠。
- 常量传播。
- 死代码消除。
- 公共子表达式消除。
- 循环优化。
- 指令调度。
- 数据流分析。
这样就不必为每一种编程语言重复实现全部底层优化算法。
2.3 支持多阶段编译与优化
IR 通常不是只有一种形式。
一个编译器可以在不同阶段使用不同抽象层次的 IR:
- 高层 IR:保留高级语言的结构和语义。
- 中层 IR:突出控制流、数据流和计算操作。
- 低层 IR:更加接近机器指令和硬件资源。
每一层 IR 关注不同的优化问题。
flowchart TB
A["源代码"]
B["高层 IR"]
C["中层 IR"]
D["低层 IR"]
E["目标机器代码"]
A --> B
B --> C
C --> D
D --> E
style A fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style C fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style E fill:#FFF5DE,stroke:#E8D29A,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
并不是所有编译器都必须使用三层 IR,也不是所有 IR 都按照严格的高、中、低层次组织。这是一种常见的设计思路。
三、IR 的基本组成
IR 的具体结构取决于编译器设计,但通常需要表达程序中的计算、数据、控制流和类型信息。
3.1 指令(Instruction)
指令表示程序中的一个具体操作。
例如:
t1 = a + b
t2 = t1 * c
可以拆分为:
| 指令 | 操作 | 操作数 | 结果 |
|---|---|---|---|
t1 = a + b |
ADD | a、b | t1 |
t2 = t1 * c |
MUL | t1、c | t2 |
不同 IR 的指令设计不同。
有些 IR 使用明确的操作码,例如 add、mul、load、store;有些 IR 使用更高层次的操作,例如函数调用、对象创建和异常处理。
3.2 操作数(Operand)
操作数是指令执行所需要的数据。
常见操作数包括:
| 类型 | 示例 | 说明 |
|---|---|---|
| 常量 | 10 |
固定值 |
| 变量 | count |
程序变量 |
| 临时值 | %1、t1 |
中间计算结果 |
| 函数参数 | arg0 |
函数输入 |
| 内存地址 | ptr |
内存访问位置 |
| 全局符号 | global_var |
全局变量或符号 |
例如:
%3 = add i32 %1, %2
其中:
%3:结果值。add:加法操作。i32:操作数类型。%1、%2:输入操作数。
这是 LLVM IR 风格的指令表示。
3.3 基本块(Basic Block)
基本块是控制流图中的重要结构。
它是一段具有单一入口、单一出口的连续指令序列。
通常情况下:
- 控制流只能从基本块的入口进入。
- 基本块内部指令按顺序执行。
- 控制流通过基本块末尾的终结指令离开。
例如:
entry:
t1 = a + b
t2 = t1 * c
return t2
这段指令可以构成一个基本块。
如果程序包含条件判断,则通常会被划分为多个基本块。
3.4 控制流图(Control Flow Graph,CFG)
控制流图使用图结构描述程序执行路径。
节点通常代表基本块,边表示基本块之间可能存在的控制转移。
例如:
if (x > 0) {
y = x + 1;
} else {
y = x - 1;
}
return y;
可以划分为:
- 条件判断块。
- 条件成立分支。
- 条件不成立分支。
- 汇合后的返回块。
flowchart TB
A["Entry"]
B["判断 x > 0"]
C["y = x + 1"]
D["y = x - 1"]
E["return y"]
F["Exit"]
A --> B
B -->|"True"| C
B -->|"False"| D
C --> E
D --> E
E --> F
style A fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style B fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style E fill:#FFF5DE,stroke:#E8D29A,color:#334155
style F fill:#E8EDF2,stroke:#B8C3CE,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
控制流图是编译器进行程序分析和优化的重要基础。
例如:
- 判断某个基本块是否可达。
- 分析循环结构。
- 计算支配关系。
- 分析数据流。
- 执行死代码消除。
3.5 类型信息(Type Information)
IR 通常需要明确表示数据类型。
例如:
%1 = add i32 %a, %b
%2 = add float %x, %y
两条指令都表示加法,但操作数类型不同。
类型信息可以帮助编译器判断:
- 指令是否合法。
- 运算结果的类型。
- 数据宽度。
- 是否需要类型转换。
- 如何选择目标机器指令。
不同 IR 的类型系统差异很大。
例如,LLVM IR 使用明确的类型系统,而某些低层 IR 可能更多依赖机器级数据宽度和操作约束。
四、IR 的主要分类
IR 可以从不同维度分类。
最常见的划分方式,是按照其数据结构和抽象层次进行区分。
4.1 树形 IR(Tree-based IR)
树形 IR 使用树结构表示程序计算关系。
例如:
a + b * c
可以表示为:
+
/ \
a *
/ \
b c
树形结构适合表达:
- 表达式嵌套。
- 运算符优先级。
- 计算依赖。
- 高层程序结构。
AST 就是一种典型的树形表示,但 AST 与所有树形 IR 并不完全等价。
某些树形 IR 会在 AST 的基础上进一步规范化,使表达式更适合优化或代码生成。
4.2 三地址码(Three-Address Code,TAC)
三地址码是一种常见的线性 IR。
它通常将复杂表达式拆分为多条简单指令,每条指令最多包含三个地址相关部分:
- 一个结果地址。
- 两个源操作数地址。
例如:
result = a + b * c;
可以转换为:
t1 = b * c
t2 = a + t1
result = t2
这里的 t1 和 t2 是编译器生成的临时变量。
三地址码的主要优点:
- 指令结构简单。
- 计算顺序明确。
- 容易进行局部优化。
- 便于转换为机器指令。
- 便于分析数据依赖。
需要注意,三地址码是一种抽象形式,并不要求所有指令都必须严格包含三个地址。赋值、跳转、函数调用等指令通常具有不同的操作数形式。
4.3 栈式 IR(Stack-based IR)
栈式 IR 使用操作数栈保存中间计算结果。
例如:
a + b * c
可以表示为:
PUSH a
PUSH b
PUSH c
MUL
ADD
执行过程:
- 将
a压入栈。 - 将
b压入栈。 - 将
c压入栈。 - 执行乘法,弹出
b和c,将结果压入栈。 - 执行加法,弹出
a和乘法结果,将最终结果压入栈。
栈式 IR 的特点:
- 指令通常不需要显式指定所有操作数。
- 操作数通过栈顶位置隐式传递。
- 指令编码可以比较紧凑。
- 执行时需要维护操作数栈状态。
Java 字节码和 WebAssembly 都具有明显的栈式操作特征,但它们并不是完全相同的 IR,也有各自的类型、控制流和验证规则。
4.4 SSA 形式(Static Single Assignment)
SSA(静态单赋值形式)是一种非常重要的 IR 表示形式。
它要求每个变量在静态程序表示中只被赋值一次。
例如,普通形式:
x = 10
x = x + 1
x = x * 2
转换为 SSA 形式:
x1 = 10
x2 = x1 + 1
x3 = x2 * 2
每次赋值都产生一个新的变量版本。
这样可以明确表达数据依赖关系。
SSA 形式是现代编译器优化的重要基础。
五、三地址码的工作原理
三地址码是理解 IR 最直观的方式之一。
5.1 将复杂表达式拆分为简单指令
考虑:
int result = (a + b) * (c - d);
原始表达式包含:
- 加法。
- 减法。
- 乘法。
- 最终赋值。
转换为三地址码:
t1 = a + b
t2 = c - d
t3 = t1 * t2
result = t3
复杂表达式被拆分成了多个简单计算步骤。
5.2 临时变量的作用
临时变量用于保存中间计算结果。
例如:
t1 = a + b
t2 = t1 * c
t3 = t2 - d
临时变量可以帮助编译器:
- 明确计算依赖。
- 分析数据流。
- 判断变量生命周期。
- 进行寄存器分配。
- 执行公共子表达式消除。
临时变量不一定对应最终机器代码中的真实内存变量。
在后续优化中,编译器可能将它们直接映射到寄存器,甚至完全消除。
5.3 三地址码的指令类型
常见指令包括:
| 指令类别 | 示例 | 作用 |
|---|---|---|
| 算术运算 | t1 = a + b |
加减乘除 |
| 逻辑运算 | t1 = a && b |
逻辑操作 |
| 比较运算 | t1 = a > b |
条件判断 |
| 赋值操作 | x = t1 |
数据赋值 |
| 条件跳转 | if t1 goto L1 |
条件分支 |
| 无条件跳转 | goto L2 |
控制转移 |
| 函数调用 | call foo |
调用函数 |
| 返回操作 | return t1 |
函数返回 |
| 内存访问 | t1 = load p |
读取内存 |
| 内存写入 | store t1, p |
写入内存 |
不同编译器的 IR 指令集合并不完全相同。
六、SSA:静态单赋值形式
SSA 是现代编译器中极其重要的 IR 形式。
理解 SSA,需要掌握两个核心概念:
- 每个变量只定义一次。
- 使用特殊的合并节点处理不同控制流路径产生的值。
6.1 为什么需要 SSA
考虑:
int x = 10;
if (condition) {
x = 20;
} else {
x = 30;
}
return x;
在普通变量表示中,x 在不同路径中被多次赋值。
编译器需要分析:
- 当前路径中
x的值是什么? - 哪次赋值会影响最终返回结果?
- 不同路径中的赋值如何合并?
SSA 将每次赋值转换为独立版本:
x1 = 10
if condition:
x2 = 20
else:
x3 = 30
x4 = phi(x2, x3)
return x4
其中,x4 由 Phi 函数产生。
6.2 Phi 函数(φ Function)
Phi 函数用于在控制流汇合时,根据实际执行路径选择对应的变量值。
例如:
x4 = phi(x2, x3)
表示:
- 如果从第一个分支进入,则选择
x2。 - 如果从第二个分支进入,则选择
x3。
Phi 函数并不是普通的数学函数调用。
它表示控制流汇合点上的数据选择关系。
可以用下面的结构理解:
flowchart TB
A["Entry"]
B["判断 condition"]
C["x2 = 20"]
D["x3 = 30"]
E["x4 = phi(x2, x3)"]
F["return x4"]
A --> B
B -->|"True"| C
B -->|"False"| D
C --> E
D --> E
E --> F
style A fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style B fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style E fill:#FFF5DE,stroke:#E8D29A,color:#334155
style F fill:#E8EDF2,stroke:#B8C3CE,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
Phi 函数的参数与控制流前驱基本块相关联,而不是根据运行时的普通条件表达式直接执行一次函数调用。
在具体 SSA 实现中,Phi 节点的操作数通常按照对应前驱基本块组织。
6.3 SSA 的核心优势
SSA 使变量定义与使用关系更加明确。
例如:
x1 = a + b
x2 = x1 * c
x3 = x2 + d
可以直接得到:
x1依赖a和b。x2依赖x1和c。x3依赖x2和d。
这种明确的数据依赖关系有利于:
- 常量传播。
- 死代码消除。
- 公共子表达式消除。
- 全局值编号。
- 数据流分析。
- 寄存器分配前的变量活跃性分析。
SSA 并不意味着程序运行时每个变量只能修改一次。它约束的是编译器静态表示中的定义形式,而不是源语言变量在运行时的行为。
七、IR 优化技术
IR 的重要价值之一,就是为编译器优化提供统一基础。
常见优化包括:
7.1 常量折叠(Constant Folding)
如果表达式中的操作数都是编译期已知的常量,编译器可以提前计算结果。
优化前:
t1 = 10 * 20
t2 = t1 + 5
优化后:
t2 = 205
常量折叠减少了运行时计算。
7.2 常量传播(Constant Propagation)
如果编译器能够确定某个变量的值,就可以将该值传播到后续使用位置。
优化前:
x = 10
y = x + 5
z = y * 2
优化后:
x = 10
y = 15
z = 30
常量传播和常量折叠经常配合使用。
7.3 公共子表达式消除(Common Subexpression Elimination)
如果相同表达式被重复计算,而且相关操作数在两次计算之间没有发生影响结果的变化,就可以复用之前的计算结果。
优化前:
t1 = a * b
t2 = a * b
result = t1 + t2
优化后:
t1 = a * b
result = t1 + t1
这种优化可以减少重复计算。
但不能仅凭表达式文本相同就认定可以复用。内存读写、副作用、浮点运算规则以及异常行为等因素都可能影响优化是否合法。
7.4 死代码消除(Dead Code Elimination)
如果某条指令的计算结果永远不会被使用,并且该指令没有必须保留的副作用,就可以删除。
优化前:
t1 = a + b
t2 = c * d
return t1
如果 t2 不会被其他地方使用,且计算没有副作用:
t1 = a + b
return t1
需要注意,函数调用、内存写入、异常触发和同步操作等可能具有副作用,不能简单地因为返回值未使用就删除。
7.5 强度削弱(Strength Reduction)
将成本较高的操作替换为成本较低的等价操作。
例如,在满足整数语义和溢出规则等前提下:
x = i * 8
可能被转换为:
x = i << 3
在现代处理器上,乘法指令不一定比移位指令慢,因此编译器是否执行这种转换需要结合目标架构和成本模型判断。
7.6 循环优化
循环通常是程序执行时间的重要组成部分。
编译器可以针对循环执行:
- 循环不变量外提。
- 循环展开。
- 循环融合。
- 循环向量化。
- 归纳变量优化。
例如:
for (int i = 0; i < n; i++) {
int factor = a * b;
result[i] = factor + i;
}
如果 a 和 b 在循环执行期间不会改变,编译器可以将乘法计算移动到循环外部。
优化后:
int factor = a * b;
for (int i = 0; i < n; i++) {
result[i] = factor + i;
}
这类优化称为循环不变量外提(Loop-Invariant Code Motion)。
八、IR 优化的整体过程
编译器通常不会只执行一次优化,而是运行多个优化 Pass。
每个 Pass 负责某一类分析或转换。
例如: