C++ 编译器第四步：中间代码优化器设计

1. 优化器的作用

优化器（Optimizer）的任务，是在不改变程序语义的前提下，对已经生成的中间代码进行等价变换，使其更加简洁、高效，并为后续目标代码生成打下基础。

在本项目的编译流程中，前几个阶段已经完成了：

词法分析：把源代码切分为 Token 序列
语法分析：根据 LL(1) 文法构造语法分析树
语义分析：检查作用域、类型和声明使用关系
中间代码生成：生成三地址码风格的四元式

优化器位于中间代码生成之后，通常位于目标代码生成之前。

也就是说，优化器不直接处理源代码，也不直接处理语法树，而是处理已经生成好的中间表示。例如：

(+, 2, 3, t1)
(=, t1, -, a)

如果发现 2 + 3 可以在编译阶段直接算出，那么可以优化为：

(=, 5, -, t1)
(=, t1, -, a)

本项目是教学导向的 C++ 子集编译器，因此优化器的目标不是实现工业级优化，而是建立一个清晰、可演示、便于扩展的中间代码优化框架。

2. 中间代码优化的基本原理

中间代码优化的核心思想是：在保持程序运行结果不变的前提下，消除冗余计算和无效控制流。

常见优化可以分为三类：

2.1 局部优化

局部优化只关注一个较小范围内的指令，通常是一个基本块。

基本块是指一段顺序执行的中间代码：

只有第一条指令可以从外部跳入
只有最后一条指令可以跳出
中间没有其他分支入口或出口

局部优化实现简单，适合本项目的教学型编译器。

2.2 全局优化

全局优化会跨越多个基本块，分析更大范围内的数据流和控制流。

例如：

跨分支的常量传播
循环不变量外提
全局公共子表达式消除
全局活跃变量分析

这类优化效果更强，但实现复杂度也更高。本项目可以先保留为后续扩展方向。

2.3 控制流优化

控制流优化关注跳转、标签和分支结构，例如：

删除跳转到下一条指令的无意义 goto
合并连续标签
将跳转到跳转的结构简化为直接跳转
删除不可达代码

由于当前 IR 中已经使用 label、goto、jz 表示控制流，因此控制流优化也可以作为优化器的一部分逐步实现。

3. 本项目的优化对象

本项目当前的中间代码采用四元式形式：

(op, arg1, arg2, result)

对应 Java 结构为：

public record Quadruple(String op, String arg1, String arg2, String result) {
}

其中：

op 表示操作码，例如 +、-、*、=、jz、goto、label、return
arg1 表示第一个操作数
arg2 表示第二个操作数
result 表示结果位置、跳转目标或标签名

语义分析阶段通过 IRGenerator 生成四元式列表：

irGenerator.emit("+", "a", "b", "t1");
irGenerator.emit("=", "t1", null, "x");

因此，优化器可以设计为：

public List<Quadruple> optimize(List<Quadruple> input) {
    // 返回优化后的四元式序列
}

优化器的输入和输出都应是四元式列表。这样做有几个好处：

不需要重新修改 Lexer、Parser 或 SemanticAnalyzer
可以保持编译流水线清晰分层
方便对比优化前后的 IR
后续目标代码生成只需要读取优化后的四元式

4. 基础优化策略设计

本项目可以先支持几类最常见、最容易演示的中间代码优化。

4.1 常量折叠

常量折叠（Constant Folding）是指在编译阶段直接计算常量表达式。

例如：

(+, 2, 3, t1)
(*, t1, 4, t2)

第一条指令中，2 和 3 都是常量，可以直接计算为：

(=, 5, -, t1)
(*, t1, 4, t2)

如果再结合常量传播，第二条还可以继续变为：

(=, 5, -, t1)
(=, 20, -, t2)

适合折叠的操作包括：

算术运算：+、-、*、/、%
关系运算：<、<=、>、>=、==、!=
逻辑运算：&&、||
一元运算：uminus、!

需要注意的是，除法和取模应避免在编译阶段执行除以零的计算。

4.2 常量传播

常量传播（Constant Propagation）是指如果某个变量或临时变量已经确定为常量，则后续使用它的地方可以直接替换为常量。

例如：

(=, 10, -, a)
(+, a, 1, t1)

如果在这两条指令之间 a 没有被重新赋值，那么可以优化为：

(=, 10, -, a)
(+, 10, 1, t1)

再结合常量折叠，可以继续得到：

(=, 10, -, a)
(=, 11, -, t1)

常量传播通常需要维护一张表：

变量名 -> 已知常量值

当变量被重新赋值为非常量时，需要从表中移除该变量。

4.3 复制传播

复制传播（Copy Propagation）是指当某个变量只是另一个变量的副本时，后续可以直接使用原变量。

例如：

(=, a, -, t1)
(+, t1, b, t2)

可以优化为：

(=, a, -, t1)
(+, a, b, t2)

如果 t1 后续不再被需要，再结合死代码删除，可以删除第一条复制指令。

复制传播适合处理语义分析阶段生成的大量临时变量，使 IR 更简洁。

4.4 公共子表达式消除

公共子表达式消除（Common Subexpression Elimination）用于避免重复计算相同表达式。

例如：

(+, a, b, t1)
(+, a, b, t2)
(*, t2, c, t3)

如果在两次 a + b 之间，a 和 b 都没有被重新赋值，则第二次计算是冗余的，可以优化为：

(+, a, b, t1)
(=, t1, -, t2)
(*, t2, c, t3)

进一步结合复制传播后，可以得到：

(+, a, b, t1)
(*, t1, c, t3)

对于 +、*、==、!= 这类满足交换律或对称性的操作，还可以把 (+, a, b) 和 (+, b, a) 视作同一个表达式。

4.5 死代码删除

死代码删除（Dead Code Elimination）用于删除结果不再被使用的指令。

例如：

(+, a, b, t1)
(*, c, d, t2)
(=, t2, -, x)

如果 t1 后续没有被使用，那么第一条指令没有实际意义，可以删除：

(*, c, d, t2)
(=, t2, -, x)

但不是所有看似“结果未使用”的指令都能删除。例如：

return 不能删除
goto、jz 不能随意删除
label 是否能删除取决于是否仍有跳转引用
未来如果加入函数调用，可能存在副作用，不能简单删除

因此，本项目可以先只删除纯计算指令产生的无用临时变量。

4.6 跳转优化

控制流相关的四元式中常见冗余包括：

(goto, -, -, L1)
(label, -, -, L1)

如果 goto 的目标正好是下一条指令的标签，那么这条 goto 没有意义，可以删除。

另一个例子：

(goto, -, -, L1)
(label, -, -, L1)
(goto, -, -, L2)

可以把跳转目标从 L1 改为 L2，减少一次间接跳转。

跳转优化的目标是让控制流更直接，减少不必要的分支指令。

5. 数据流分析基础

为了判断某条指令是否可以优化，优化器需要知道变量在某个范围内的使用和定义情况。

5.1 def 与 use

对于一条四元式：

(+, a, b, t1)

可以认为：

a、b 是 use：它们被读取
t1 是 def：它被定义

对于赋值指令：

(=, t1, -, x)

可以认为：

t1 是 use
x 是 def

对于跳转和标签：

(jz, t1, -, L1)
(label, -, -, L1)

可以认为：

jz 使用条件变量 t1
label 定义的是控制流目标，不是普通变量定义

5.2 活跃变量

如果某个变量的值在后续仍可能被读取，那么它就是活跃的。

例如：

(+, a, b, t1)
(=, t1, -, x)

在第一条指令之后，t1 是活跃的，因为第二条指令会读取它。

而在下面的代码中：

(+, a, b, t1)
(=, 0, -, x)

如果 t1 后续没有被使用，那么第一条指令可以视为死代码。

5.3 基本块内分析

完整的数据流分析可能需要跨越多个分支和循环。为了保持实现简单，本项目可以先采用基本块内分析：

先把四元式序列划分为多个基本块
在每个基本块内部维护常量表、复制表和表达式表
在基本块边界处清空这些局部信息

这种方式虽然优化能力有限，但实现清晰、风险较小，适合作为第一版优化器。

6. 基本块划分设计

基本块划分是很多中间代码优化的基础。

6.1 leader 规则

可以先找出所有基本块入口，通常称为 leader：

第一条四元式是 leader
所有 label 指令是 leader
所有跳转指令后面的第一条指令是 leader
所有跳转目标对应的标签是 leader

跳转指令包括：

goto
jz
jnz（如果后续加入）

6.2 划分过程

假设有如下四元式：

0: (=, 10, -, a)
1: (>=, a, 10, t1)
2: (jz, t1, -, L1)
3: (+, a, 1, t2)
4: (return, t2, -, -)
5: (label, -, -, L1)
6: (return, 0, -, -)

可以划分为：

Block 1:
0: (=, 10, -, a)
1: (>=, a, 10, t1)
2: (jz, t1, -, L1)

Block 2:
3: (+, a, 1, t2)
4: (return, t2, -, -)

Block 3:
5: (label, -, -, L1)
6: (return, 0, -, -)

这样，优化器就可以先在每个基本块内部做局部优化，再对块之间的标签和跳转做简单整理。

7. 优化器执行流程

优化器可以按照流水线方式组织多个优化步骤。

7.1 总体流程

输入原始四元式列表
        |
        v
划分基本块
        |
        v
基本块内常量折叠
        |
        v
基本块内常量传播与复制传播
        |
        v
公共子表达式消除
        |
        v
死代码删除
        |
        v
跳转与标签清理
        |
        v
输出优化后的四元式列表

7.2 迭代优化

有些优化会触发新的优化机会。例如：

常量传播后，表达式可能变成常量表达式
常量折叠后，某些临时变量可能不再需要
复制传播后，复制指令可能变成死代码

因此，优化器可以采用有限轮次迭代：

repeat
    执行一轮优化
until 本轮没有变化，或达到最大轮次

为了避免实现复杂化，第一版可以只执行固定顺序的一轮优化。等基础功能稳定后，再增加迭代机制。

7.3 语义保持原则

优化器必须遵守一个基本原则：

优化前后的程序可观察行为必须一致。

因此，以下指令应谨慎处理：

控制流指令：goto、jz、label
返回指令：return
未来可能引入的函数调用、输入输出或内存访问指令

第一版优化器应优先处理无副作用的普通表达式计算。

8. Java 模块实现思路

可以为优化器新增独立包：

src/main/java/org/yyds/optimizer

建议先设计以下几个核心类。

8.1 Optimizer

Optimizer 是优化器入口，负责组织各个优化步骤。

public class Optimizer {
    public List<Quadruple> optimize(List<Quadruple> input) {
        List<BasicBlock> blocks = splitBasicBlocks(input);
        List<BasicBlock> optimizedBlocks = optimizeBlocks(blocks);
        return cleanupJumps(flatten(optimizedBlocks));
    }
}

它的职责包括：

接收原始四元式列表
调用基本块划分逻辑
执行各类优化 pass
返回新的四元式列表

8.2 BasicBlock

BasicBlock 表示一个基本块。

public class BasicBlock {
    private final String name;
    private final List<Quadruple> quadruples;
}

它可以保存：

基本块名称或编号
块内四元式序列
前驱块集合
后继块集合

第一版可以只保存块内四元式，等需要控制流图时再扩展前驱和后继信息。

8.3 OptimizationPass

为了方便扩展，可以把每类优化抽象为一个 pass：

public interface OptimizationPass {
    List<Quadruple> apply(List<Quadruple> input);
}

例如：

ConstantFoldingPass
ConstantPropagationPass
CopyPropagationPass
DeadCodeEliminationPass
JumpCleanupPass

如果希望保持实现简单，也可以先在 Optimizer 中用私有方法实现这些逻辑，等优化策略增多后再拆分为独立类。

8.4 与 Quadruple 的关系

当前 Quadruple 是不可变 record，因此优化时不应原地修改字段，而应创建新的四元式：

Quadruple optimized = new Quadruple("=", "5", null, "t1");

这种方式可以避免修改原始 IR，方便打印和对比优化前后的结果。

9. 优化示例

下面给出一个较完整的优化示例。

9.1 优化前

(=, 2, -, a)
(=, 3, -, b)
(+, a, b, t1)
(+, a, b, t2)
(*, t2, 4, t3)
(+, 1, 2, t4)
(=, t3, -, x)
(goto, -, -, L1)
(label, -, -, L1)
(return, x, -, -)

9.2 优化过程

首先，常量传播可将 a、b 的值传播到表达式中：

(+, 2, 3, t1)
(+, 2, 3, t2)

然后，常量折叠得到：

(=, 5, -, t1)
(=, 5, -, t2)

(+, 1, 2, t4) 可以折叠为 t4 = 3，但如果 t4 后续没有被使用，则可以删除。

goto L1 的下一条指令正好是 label L1，因此该跳转可以删除。

9.3 优化后

一种可能的优化结果为：

(=, 2, -, a)
(=, 3, -, b)
(=, 5, -, t2)
(*, t2, 4, t3)
(=, t3, -, x)
(label, -, -, L1)
(return, x, -, -)

如果进一步传播 t2 = 5，还可以优化为：

(=, 2, -, a)
(=, 3, -, b)
(=, 20, -, t3)
(=, t3, -, x)
(label, -, -, L1)
(return, x, -, -)

这个例子体现了多种优化之间的联动关系。

10. 与现有编译流程的衔接

当前 Main 中的演示流程大致为：

Lexer -> Parser -> SemanticAnalyzer -> 打印 IR

加入优化器后，可以调整为：

Lexer -> Parser -> SemanticAnalyzer -> Optimizer -> 打印优化后 IR

示意代码如下：

SemanticAnalyzer semanticAnalyzer = new SemanticAnalyzer();
semanticAnalyzer.analyze(parseTree);

Optimizer optimizer = new Optimizer();
List<Quadruple> optimized = optimizer.optimize(
    semanticAnalyzer.getIrGenerator().getQuadruples()
);

for (Quadruple quadruple : optimized) {
    System.out.println(quadruple);
}

这样可以保留原有语义分析和 IR 生成逻辑，只在后面增加一个独立优化阶段。

为了便于教学展示，也可以同时打印优化前和优化后的四元式：

中间代码四元式：
...

优化后四元式：
...

这样可以直观看出优化器的作用。

11. 设计小结

本阶段优化器的核心目标，是在已有四元式 IR 的基础上，建立一个简单、清晰、可扩展的中间代码优化框架。

第一版优化器可以重点支持：

常量折叠
常量传播
复制传播
公共子表达式消除
死代码删除
简单跳转优化
基本块划分

它应满足以下设计原则：

输入和输出都使用 List<Quadruple>
不直接修改语法树和语义符号表
优先优化无副作用的表达式计算
保持优化前后程序语义一致
便于在 Main 中展示优化前后的 IR 对比

后续可以继续扩展：

构建完整控制流图
实现跨基本块的数据流分析
支持循环不变量外提
引入 SSA 中间表示
根据目标机器特性做目标代码优化

对于当前教学型编译器来说，先完成基于四元式的局部优化，就可以很好地展示“中间代码不仅可以被生成，还可以被分析和改写”的核心思想。

FilesExpand file tree

optimizer-design.md

Latest commit

History

optimizer-design.md

File metadata and controls

C++ 编译器第四步：中间代码优化器设计

1. 优化器的作用

2. 中间代码优化的基本原理

2.1 局部优化

2.2 全局优化

2.3 控制流优化

3. 本项目的优化对象

4. 基础优化策略设计

4.1 常量折叠

4.2 常量传播

4.3 复制传播

4.4 公共子表达式消除

4.5 死代码删除

4.6 跳转优化

5. 数据流分析基础

5.1 def 与 use

5.2 活跃变量

5.3 基本块内分析

6. 基本块划分设计

6.1 leader 规则

6.2 划分过程

7. 优化器执行流程

7.1 总体流程

7.2 迭代优化

7.3 语义保持原则

8. Java 模块实现思路

8.1 Optimizer

8.2 BasicBlock

8.3 OptimizationPass

8.4 与 Quadruple 的关系

9. 优化示例

9.1 优化前

9.2 优化过程

9.3 优化后

10. 与现有编译流程的衔接

11. 设计小结