第一部分：经典的“数据流”优化
1 引言
回顾一下简单的非优化编译器的结构（例如来自CST第一部分b）。
字符
流
词法分析
标记
流
语法分析
解析
树
转换
中间代码
生成
目标
代码
在这样的编译器中，“中间代码”通常是一个面向堆栈的抽象机器代码（例如BCPL编译器中
的OCODE或Java中的JVM）。请注意，阶段“词法分析”、“语法分析”和“转换”原则上是源
语言相关的，但不是目标架构相关的，而阶段“生成”是目标相关的，但不是语言相关的。
为了简化优化（实际上是‘改善’！），我们需要一个中间代码，使得指令之间的依赖关系
明确，以便于移动计算。 通常我们使用3地址代码（有时称为‘四元组’）。 这也接近现代RIS
C架构，因此有助于目标相关阶段的‘生成’。 这个中间代码存储在一个流图 G中，它的节点
上标有3地址指令（或者后来的‘基本块’）。我们写作
pred(n) = {n
′
| (n
′
, n) ∈ edges(G)}
succ(n) = {n
′
| (n, n
′
) ∈ edges(G)}
表示给定节点的前驱和后继节点集合；我们假设常见的图论概念，如路径和循环。
三地址指令的形式（a， b， c是操作数， f是过程名， lab是一个标签）：
• ENTRY f：没有前驱；
• EXIT：没有后继；
• ALUa, b, c：一个后继（ADD， MUL，等等）；
• CMPconda, b, lab：两个后继（CMPNE， CMPEQ，等等）—在直线代码中，这些指令带
有一个标签参数（如果分支不发生，则继续执行下一条指令），而在流图中，它们有
两个后继边。
多路分支（例如case语句）可以被视为一系列CMP指令。 过程调用（CALL f）和间接调用
（CALLI a）被视为类似于ALUa, b, c的原子指令。 类似地，我们区分MOVa, b指令（忽略
一个操作数的ALU的特殊情况）和间接内存引用指令（LDIa, b和STIa, b）用于表示指针解
引用，包括访问数组元素。 间接分支（用于本地 goto exp）终止一个基本块（稍后会介绍
）；它们的后继必须包括所有可能的分支目标（参见Fortran ASSIGNED GOTO的描述）。
4
