返回专栏
· 16 分钟阅读

中间表示(Intermediate Representation,IR)


一、什么是中间表示(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 种目标架构,直接组合的实现规模可能接近:

M \times 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 种后端,核心适配关系可以从大量两两组合,转变为分别维护前端和后端接口,整体规模更接近:

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

执行过程:

  1. 将 a 压入栈。
  2. 将 b 压入栈。
  3. 将 c 压入栈。
  4. 执行乘法,弹出 b 和 c,将结果压入栈。
  5. 执行加法,弹出 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 负责某一类分析或转换。

例如: