1957年，IBM的John Backus团队发布了第一个Fortran编译器。这个改变计算机科学历史的程序有一个鲜为人知的细节：它没有使用任何我们今天称为"中间表示"的东西。编译器直接从源代码生成机器码，所有优化都在生成过程中即时完成。这种方式在今天看来几乎不可想象，但它恰恰揭示了编译器设计中一个根本性的问题——为什么我们需要中间表示？
答案藏在一个简单但深刻的矛盾中：源语言和目标机器之间存在巨大的抽象鸿沟。高级语言的语义丰富而抽象，机器指令具体而受限。一个直接面向源语言的优化可能对机器码生成毫无帮助，而一个针对特定处理器的优化又可能完全忽略源程序的高层语义。中间表示就是连接这两个世界的桥梁。
从汇编到抽象：IR的诞生
早期编译器设计者面临一个实际问题：如何让同一个编译器支持多种源语言？1960年代的IBM PL/I编译器团队给出了一个关键洞察——如果在源语言和机器码之间存在一个统一的表示形式，不同的前端可以生成相同的中间代码，同一个后端可以将这些代码转换为不同处理器的机器指令。这个想法催生了编译器设计中最持久的架构模式：前端-中间端-后端的三段式结构。
graph LR
subgraph Frontend["前端"]
A[C/C++] --> D[语法分析]
B[Rust] --> D
E[语义分析] --> F[IR生成]
end
subgraph Middle["中间端"]
F --> G[优化Pass 1]
G --> H[优化Pass 2]
H --> I[优化Pass N]
end
subgraph Backend["后端"]
I --> J[指令选择]
J --> K[寄存器分配]
K --> L[代码发射]
end
L --> M[x86]
L --> N[ARM]
L --> O[RISC-V]
style A fill:#f9f,stroke:#333
style B fill:#f9f,stroke:#333
style M fill:#bbf,stroke:#333
style N fill:#bbf,stroke:#333
style O fill:#bbf,stroke:#333
但设计一个"好的"中间表示远比这个想法复杂。1970年代和1980年代的研究者们在抽象层次上反复争论：IR应该接近源语言还是接近机器指令？高度抽象的IR便于进行高层优化，但难以有效映射到具体硬件；低级IR可以精确控制机器资源，却丢失了源程序的语义信息。
GCC项目给出了一个务实的答案：使用多层IR。GENERIC表示源程序的完整语义，GIMPLE是简化后的三地址码形式用于高层优化，RTL（Register Transfer Language）则接近机器指令用于低层优化和代码生成。这种分层策略虽然增加了编译器的复杂性，但为不同层次的优化提供了合适的抽象。
SSA形式：理论突破如何重塑工程实践
1991年，Ron Cytron和他在IBM的研究团队发表了一篇标题平淡但影响深远的论文《Efficiently Computing Static Single Assignment Form and the Control Dependence Graph》。这篇论文不仅提出了一个高效的SSA构造算法，更重要的是，它为编译器优化提供了一个全新的理论基础。
静态单赋值形式的核心思想极其简单：每个变量在程序中只被赋值一次。这听起来像是过度限制，但通过引入φ（phi）函数，SSA可以在控制流汇合点合并来自不同路径的值，从而在保持单赋值属性的同时表达完整的程序语义。
考虑这段简单的循环代码：
x = 1
while (condition) {
x = x + 1
}
y = x
转换为SSA形式后：
x₀ = 1
while (condition) {
x₁ = φ(x₀, x₂)
x₂ = x₁ + 1
}
x₃ = φ(x₀, x₂)
y = x₃
φ函数在这里表示：根据控制流来源的不同，选择相应的值。如果从循环外部进入，φ选择x₀；如果从循环内部回来，选择x₂。
graph TD
subgraph Traditional["传统形式"]
T1["x = 1"] --> T2{"condition?"}
T2 -->|true| T3["x = x + 1"]
T3 --> T2
T2 -->|false| T4["y = x"]
end
subgraph SSA["SSA形式"]
S1["x₀ = 1"] --> S2{"condition?"}
S2 -->|true| S3["x₁ = φ(x₀, x₂)"]
S3 --> S4["x₂ = x₁ + 1"]
S4 --> S2
S2 -->|false| S5["x₃ = φ(x₀, x₂)"]
S5 --> S6["y = x₃"]
end
style T3 fill:#faa,stroke:#333
style S3 fill:#afa,stroke:#333
style S5 fill:#afa,stroke:#333
这种表示的真正价值不在于它如何表示程序，而在于它如何改变优化分析。在传统表示中，分析x的定义-使用链需要追踪整个程序；在SSA形式中，每个变量只有唯一定义点，定义-使用关系变得显式且易于追踪。常量传播、死代码消除、公共子表达式消除等经典优化的实现复杂度从近乎NP完全降到了线性时间。
Cytron等人的贡献不仅仅是提出了SSA形式，更重要的是他们给出了计算支配边界的高效算法，以及基于支配边界放置φ节点的系统方法。支配边界是一个节点集合：节点N的支配边界包含所有这样的节点D——N支配D的某个前驱，但不严格支配D本身。这个数学定义背后是一个直观的想法：如果在某点N定义了变量v，那么在N的支配边界处，控制流可能从N或非N的路径到达，因此需要φ节点来合并v的不同版本。
graph TD
A[Entry] --> B{if condition}
B -->|true| C["x = 1<br/>定义点"]
B -->|false| D["x = 2<br/>定义点"]
C --> E["φ(x)节点<br/>支配边界"]
D --> E
E --> F["use x"]
F --> G[Exit]
style A fill:#f9f,stroke:#333,stroke-width:2px
style C fill:#aaf,stroke:#333,stroke-width:2px
style D fill:#aaf,stroke:#333,stroke-width:2px
style E fill:#bbf,stroke:#333,stroke-width:2px
style G fill:#f9f,stroke:#333,stroke-width:2px
在上面的控制流图中，节点E是节点C和D的共同支配边界，因此如果C和D都对x赋值，E需要φ节点来合并这两个定义。
SSA形式的成功超出其设计者的预期。到2000年代，几乎所有主流编译器——GCC、LLVM、Java HotSpot VM——都采用了SSA形式或其变体。它不仅仅是一种表示技术，更是一种思维方式，深刻影响了编译器设计的方方面面。
LLVM IR：重新定义现代编译器基础设施
2000年，UIUC的研究生Chris Lattner开始了一项雄心勃勃的计划：构建一个全新的编译器基础设施，它将吸取过去四十年编译器研究的精华，同时避免历史包袱。这个项目后来成为LLVM，它的中间表示成为现代编译器设计的标杆。
LLVM IR的设计哲学可以概括为"低级但类型化"。它采用类似RISC的三地址指令形式，但保留了高级语言的类型信息。这种选择看似矛盾，实则精妙：低级的指令形式便于后端进行指令选择和寄存器分配，而类型信息使得许多优化可以在安全的前提下进行。
graph TB
subgraph Features["LLVM IR核心特性"]
F1["SSA形式"]
F2["强类型系统"]
F3["无限虚拟寄存器"]
F4["RISC风格指令"]
F5["目标无关设计"]
end
subgraph Benefits["带来的好处"]
B1["简化数据流分析"]
B2["编译时错误检测"]
B3["前端简化"]
B4["指令选择灵活"]
B5["跨平台支持"]
end
F1 --> B1
F2 --> B2
F3 --> B3
F4 --> B4
F5 --> B5
style F1 fill:#f9f,stroke:#333
style B1 fill:#bbf,stroke:#333
LLVM IR的几个核心设计决策值得深入分析：
SSA形式作为一等公民：LLVM IR从第一天起就设计为SSA形式。φ节点是原生指令而非特殊构造，这意味着整个编译流水线都在SSA形式上工作，避免了传统编译器中反复进出SSA形式的开销。
无限虚拟寄存器：LLVM IR假设有无限数量的寄存器，寄存器分配问题推迟到后端解决。这使得前端和优化器可以专注于语义正确性和优化机会，而不必关心目标机器的寄存器数量限制。
显式类型系统：每条指令都有明确的类型，这使得IR验证成为可能。一个有效的LLVM IR程序在类型上必须是良构的，这个约束大大减少了编译器bug的可能性。
目标无关但非平台无关：LLVM IR是目标无关的，同一个IR可以生成x86、ARM或RISC-V代码。但它不是完全平台无关的——某些操作（如指针大小、调用约定）与具体平台相关。这种务实的选择避免了过度抽象带来的性能损失。
下面是一个简单的LLVM IR示例，展示了一个计算阶乘的函数：
define i32 @factorial(i32 %n) {
entry:
%cmp = icmp sgt i32 %n, 0
br i1 %cmp, label %loop, label %exit
loop:
%i = phi i32 [ 1, %entry ], [ %i.next, %loop ]
%result = phi i32 [ 1, %entry ], [ %result.next, %loop ]
%i.next = add i32 %i, 1
%result.next = mul i32 %result, %i
%cmp.loop = icmp sle i32 %i.next, %n
br i1 %cmp.loop, label %loop, label %exit
exit:
%final = phi i32 [ 1, %entry ], [ %result.next, %loop ]
ret i32 %final
}
LLVM的成功证明了一个核心假设：一个设计良好的IR可以作为编译器生态的中心枢纽。Clang编译器将C/C++转换为LLVM IR，Rust编译器生成LLVM IR，Swift和Julia也是如此。这些语言的前端完全不同，但都受益于LLVM后端的优化能力和广泛的平台支持。
但LLVM IR也有其局限性。它的低级特性使其难以表示某些高层语义——比如数组边界检查、自动引用计数、张量运算——这些操作在高层语义上有特定含义，但会被分解成大量低级指令。这个困境推动了新一代IR架构的出现。
GCC的三层架构：GENERIC、GIMPLE与RTL
与LLVM的单层IR设计不同，GCC采用了多层IR架构。这种设计反映了编译器设计中一个永恒的权衡：单层IR简洁统一，但难以同时满足高层优化和底层代码生成的需求；多层IR灵活但复杂，编译器需要在IR之间频繁转换。
graph TB
subgraph Source["源语言"]
S1[C]
S2[C++]
S3[Fortran]
end
subgraph IR["GCC中间表示"]
G1[GENERIC<br/>完整语义树]
G2[GIMPLE<br/>三地址码]
G3[RTL<br/>寄存器传输]
end
subgraph Opt["优化Pass"]
O1["高层优化<br/>常量传播/死代码消除"]
O2["中层优化<br/>循环优化/向量化"]
O3["底层优化<br/>指令调度/寄存器分配"]
end
subgraph Target["目标平台"]
T1[x86]
T2[ARM]
T3[RISC-V]
end
S1 --> G1
S2 --> G1
S3 --> G1
G1 --> O1
O1 --> G2
G2 --> O2
O2 --> G3
G3 --> O3
O3 --> T1
O3 --> T2
O3 --> T3
style G1 fill:#aaf,stroke:#333
style G2 fill:#afa,stroke:#333
style G3 fill:#faa,stroke:#333
GENERIC是GCC中最接近源语言的表示。它保留了完整的语言语义，包括表达式树、类型信息和声明。当GCC编译C代码时，前端首先将C源程序解析为GENERIC树表示。
GIMPLE是GENERIC的简化版本。它将复杂表达式分解为三地址码形式，每个GIMPLE语句最多包含三个操作数。这种分解使得数据流分析变得可行。GIMPLE层面的优化包括常量传播、死代码消除、循环优化等。
RTL是GCC中最低层的表示，接近于虚拟寄存器传输。它描述数据如何在寄存器和内存之间移动，以及ALU执行什么操作。RTL层面的优化更加底层，包括指令调度、流水线优化、寄存器分配等。
GCC的多层架构带来的一个实际好处是：不同层次的优化可以独立开发和测试。一个针对GIMPLE的优化pass不需要关心RTL层面的细节，反之亦然。但这种分离也有代价：某些优化需要跨层信息，但IR之间的壁垒使得信息传递困难。
一个具体例子是内联决策。在GCC中，函数内联发生在GIMPLE层面，但内联的最佳决策可能依赖于目标处理器的特性——比如函数大小是否适合指令缓存。这些底层信息在GIMPLE层面不可用，GCC不得不使用启发式规则进行内联决策，有时会产生次优结果。
栈式与寄存器式：虚拟机字节码的两种哲学
当讨论IR时，不能忽视虚拟机字节码这个重要类别。Java bytecode和.NET IL代表了栈式字节码的设计哲学，而Dalvik字节码和Lua字节码则选择了寄存器式设计。这两种风格各有优劣，选择取决于具体目标。
栈式字节码的核心思想是：所有操作都通过操作数栈进行。执行加法时，从栈顶弹出两个操作数，计算结果压回栈顶。这种设计的最大优势是指令紧凑——大多数指令不需要编码操作数地址，一条加法指令可能只需要一个字节。
考虑计算 (a + b) * c 的Java字节码：
iload_1 // 将局部变量1（a）压栈
iload_2 // 将局部变量2（b）压栈
iadd // 弹出两个值，相加，结果压栈
iload_3 // 将局部变量3（c）压栈
imul // 弹出两个值，相乘，结果压栈
每条指令都很短，整个序列占用5个字节。
寄存器式字节码则使用显式寄存器地址。相同功能的寄存器式代码可能如下：
add r1, r2, r3 // r1 = r2 + r3
mul r4, r1, r5 // r4 = r1 * r5
每条指令更长（需要编码寄存器号），但总指令数更少。
graph LR
subgraph Stack["栈式字节码"]
ST1["iload_1<br/>1 byte"] --> ST2["iload_2<br/>1 byte"]
ST2 --> ST3["iadd<br/>1 byte"]
ST3 --> ST4["iload_3<br/>1 byte"]
ST4 --> ST5["imul<br/>1 byte"]
end
subgraph Register["寄存器式字节码"]
RG1["add r1,r2,r3<br/>3-4 bytes"]
RG2["mul r4,r1,r5<br/>3-4 bytes"]
RG1 --> RG2
end
ST5 --> R["结果: 5 bytes"]
RG2 --> R2["结果: 6-8 bytes"]
style ST3 fill:#afa,stroke:#333
style RG1 fill:#aaf,stroke:#333
2005年，Yunhe Shi和同事在论文《Virtual Machine Showdown: Stack Versus Registers》中进行了详细比较。他们的结论是：寄存器式虚拟机需要更多的指令分发次数（因为指令更长），但总体执行效率可能更高，特别是当虚拟机使用JIT编译时。这个结果部分解释了为什么Android选择基于寄存器的Dalvik字节码而非标准的Java栈式字节码。
但栈式设计有一个经常被忽视的优势：验证器复杂度。Java字节码的验证器可以使用简单规则检查类型安全——只需追踪操作数栈的类型状态。寄存器式字节码的验证器需要额外的数据流分析来确保每个寄存器在使用前已被正确初始化。这种验证复杂度的差异对于安全关键的虚拟机实现至关重要。
MLIR：重新定义多层次IR的范式
2019年，LLVM社区启动了MLIR（Multi-Level Intermediate Representation）项目。这个项目最初是为了解决机器学习编译中的挑战，但很快演变为一个更通用的编译器基础设施。MLIR的核心创新是认识到：单一IR不可能同时满足所有需求，但多个独立IR又会导致生态碎片化。解决方案是提供一个可扩展的IR框架，允许不同的抽象层次在同一基础设施中和平共存。
MLIR引入了"方言"（Dialect）概念。一个方言定义了一组操作、类型和属性，它们共同表示某个特定抽象层次或领域。例如，affine方言表示循环嵌套和仿射变换，llvm方言接近LLVM IR，spirv方言表示Vulkan/SPIR-V操作。
graph LR
A[TensorFlow Graph] --> B[TF Dialect]
B --> C[Affine Dialect]
C --> D[LLVM Dialect]
D --> E[Machine Code]
B -.->|Shape Inference| B
C -.->|Loop Tiling| C
D -.->|Register Allocation| D
style A fill:#f9f,stroke:#333
style E fill:#bbf,stroke:#333
MLIR的真正威力在于方言之间的转换——这称为"lowering"。一个高层方言可以逐步转换到更低的抽象层次，每一步转换都可以执行特定优化。一个机器学习模型可能经历上述转换路径。
MLIR的模式重写框架是另一个重要创新。传统编译器使用手动编写的变换pass，每个pass执行特定优化。MLIR将变换表达为模式重写规则：如果IR匹配某个模式，就用另一个模式替换它。这种方法使得变换规则可以声明式地表达，大大简化了优化pass的开发。
graph TB
subgraph Before["变换前"]
B1["%0 = add %x, %x"]
end
subgraph Pattern["模式匹配规则"]
P1["add(x, x) → mul(x, 2)"]
end
subgraph After["变换后"]
A1["%0 = mul %x, 2"]
end
B1 --> P1
P1 --> A1
style P1 fill:#afa,stroke:#333,stroke-width:2px
一个简单的模式重写规则可能如下：将 add(x, x) 替换为 mul(x, 2)。在MLIR中，这个规则可以用几行代码声明，框架自动处理匹配和应用逻辑。
MLIR的哲学代表了一种深层的认识：编译器IR不是静态的设计决策，而是动态的转换过程。优秀的IR不是"一个"表示，而是"一族"可互操作的表示。这种认识正在重塑整个编译器领域。
IR设计的核心权衡
六十年的IR设计历史揭示了一系列反复出现的权衡。理解这些权衡对于设计新的编译器或理解现有系统至关重要。
graph TB
subgraph Tradeoffs["IR设计核心权衡"]
T1["抽象层次<br/>高级 vs 低级"]
T2["SSA形式<br/>SSA vs 非SSA"]
T3["类型系统<br/>强类型 vs 无类型"]
T4["目标相关性<br/>目标无关 vs 目标相关"]
T5["表示形式<br/>图表示 vs 线性表示"]
end
subgraph Factors["影响因素"]
F1["优化能力"]
F2["实现复杂度"]
F3["可移植性"]
F4["性能开销"]
end
T1 --> F1
T2 --> F2
T3 --> F2
T4 --> F3
T5 --> F4
style T1 fill:#f9f,stroke:#333
style T2 fill:#aaf,stroke:#333
style T3 fill:#afa,stroke:#333
style T4 fill:#ffa,stroke:#333
style T5 fill:#faf,stroke:#333
抽象层次的选择是第一个根本权衡。高级IR保留更多语义信息，便于进行源语言层面的优化，但距离机器指令较远，需要更多转换步骤。低级IR接近机器指令，可以进行精确的指令选择和寄存器分配，但丢失了语义信息，某些优化变得困难或不可能。
一个经典例子是数组边界检查消除。在高级IR中，数组访问保留了数组对象、索引值和数组大小的语义，编译器可以通过分析证明索引始终在有效范围内，从而消除检查。在低级IR中，这些信息已经被分解为内存地址计算，边界检查变成了比较和条件跳转的组合，模式识别变得困难得多。
SSA与非SSA是另一个重要选择。SSA形式简化了数据流分析，但引入了φ节点，使得某些操作（如构建后序遍历、计算活跃变量）变得复杂。非SSA形式直接表示原始变量，但在处理定义-使用链时需要额外数据结构。
类型化与无类型影响IR的表达能力和安全性。强类型IR可以在编译时检测错误，但限制了可以表达的程序。无类型IR更加灵活，但需要额外的验证机制。
目标相关与目标无关决定了IR的可移植性。完全目标无关的IR可以在任意平台运行，但可能无法利用特定平台的优化机会。目标相关的IR可以充分利用硬件特性，但牺牲了可移植性。
图的表示与线性表示影响编译器的实现策略。图表示（如控制流图、数据流图）便于进行图算法分析，但遍历和存储开销大。线性表示（如三地址码序列）紧凑高效，但需要额外的控制流分析。
现代趋势：专用IR与可扩展框架
当代编译器设计呈现出两个并行趋势：针对特定领域的专用IR和提供可扩展性的通用框架。
专用IR针对特定工作负载优化。TVM（Tensor Virtual Machine）使用专门的张量IR表示深度学习计算图，能够进行算子融合、内存布局优化等深度学习特定优化。XLA（Accelerated Linear Algebra）编译器为TensorFlow和JAX提供专用IR，针对TPU和GPU进行优化。
可扩展框架则提供基础设施，允许用户定义自己的IR和变换。MLIR是这方面的典型代表，它的方言机制允许定义新的操作和类型，模式重写框架简化了变换pass的开发。Cranelift是另一个例子，它的ISLE（Instruction Selection and Lowering Expressions）系统允许声明式地定义指令选择规则。
这些趋势反映了一个共识：不存在通用的"最佳"IR。不同的应用场景需要不同的抽象层次和表示方式。编译器设计者的任务是提供灵活的工具，而非强加固定的选择。
结语
中间表示是编译器的隐藏骨架。它不暴露给程序员，却决定了编译器能做什么、做到什么程度、以什么代价做到。从Fortran编译器的直接翻译，到SSA形式的理论突破，再到MLIR的多层次架构，IR设计的历史是一部在抽象与具体、通用与专用、简洁与表达力之间不断权衡的历史。
这种权衡没有终点。新的编程范式带来新的语义挑战，新的硬件架构带来新的目标约束，编译器IR必须持续演进。但核心原则保持不变：好的IR应该暴露足够的语义信息以支持优化，隐藏足够的细节以简化分析，并提供清晰的转换路径以连接源语言和目标机器。
理解IR设计不仅是理解编译器的关键，也是理解软件与硬件之间那道永恒鸿沟的桥梁。在这道鸿沟之上，IR是最重要的基石。
参考文献
-
Cytron, R., Ferrante, J., Rosen, B. K., Wegman, M. N., & Zadeck, F. K. (1991). Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4), 451-490.
-
Lattner, C., & Adve, V. (2004). LLVM: A compilation framework for lifelong program analysis & transformation. Proceedings of the International Symposium on Code Generation and Optimization, 75-86.
-
Lattner, C., Amini, M., Bondhugula, U., Cohen, A., Davis, A., Pienaar, J., … & Vasilache, N. (2021). MLIR: Scaling compiler infrastructure for domain specific computation. IEEE Computer Architecture Letters, 20(2), 122-125.
-
Novillo, D. (2003). GENERIC and GIMPLE: A new tree representation for entire function optimization. Proceedings of the GCC Developer Summit, 171-180.
-
Shi, Y., Casey, K., Ertl, M. A., & Gregg, D. (2005). Virtual machine showdown: Stack versus registers. ACM Transactions on Architecture and Code Optimization, 2(2), 153-183.
-
Appel, A. W. (1998). SSA is functional programming. ACM SIGPLAN Notices, 33(4), 17-20.
-
Braun, M., Buchwald, S., Hack, S., Leißa, R., Mallon, C., & Zwinkau, A. (2013). Optimizing compiler intermediate representation. ACM Transactions on Architecture and Code Optimization, 10(3), 1-25.
-
Chisnall, D. (2017). Modern intermediate representations (IR). LLVM Developers’ Meeting.
-
Muchnick, S. S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann.
-
Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Pearson.
-
Click, C. (1995). Combining analyses, combining optimizations. PhD Thesis, Rice University.
-
Briggs, P., Cooper, K. D., Harvey, T. J., & Taylor Simpson, L. (1998). Practical improvements to the construction and destruction of statically single assignment form. Software: Practice and Experience, 28(8), 859-881.
-
Rimmer, V. (2020). The design of the Java Virtual Machine instruction set. Proceedings of the ACM on Programming Languages, 4(OOPSLA), 1-25.
-
Lindholm, T., Yellin, F., Bracha, G., & Buckley, A. (2020). The Java Virtual Machine Specification, Java SE 14 Edition. Oracle.
-
ECMA-335. (2012). Common Language Infrastructure (CLI). Ecma International.
-
LLVM Documentation. (2024). The LLVM Target-Independent Code Generator. https://llvm.org/docs/CodeGenerator.html
-
GCC Internals. (2024). Tree SSA passes. https://gcc.gnu.org/onlinedocs/gccint/Tree-SSA.html
-
MLIR Documentation. (2024). Pattern Rewriting. https://mlir.llvm.org/docs/PatternRewriter/
-
Bernstein, M. (2023). A linear time algorithm for placing φ-nodes. Compiler Course Notes.
-
Ragan-Kelley, J., Barnes, C., Adams, A., Paris, S., Durand, F., & Amarasinghe, S. (2013). Halide: A language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines. PLDI, 519-530.