8. 中间代码优化

1. Motivation (动机：为什么要做优化？)

代码优化是编译器的“增效剂”，位于中间代码生成之后（机器无关优化）或目标代码生成之后（机器相关优化）。

核心原则：等价变换 (Equivalent Transformation)。

即：优化不能改变程序的语义（运行结果），不能引入新的错误。

两大目标：

1. 时间优化：减少指令条数、降低计算强度 跑得更快（首要目标）。

2. 空间优化：减少代码体积、减少内存/寄存器占用 更省空间。

---

2. Concept (核心概念)

2.1 优化的分类矩阵

理解不同层级的优化是解题的基础。

维度	分类	特点	典型例子
按范围	局部优化 (Local)	仅在基本块内部，不跨越跳转。	常量合并、删除死代码。
	循环优化 (Loop)	针对循环体。收益最高（90/10法则）。	代码外提、强度削弱。
	全局优化 (Global)	跨越基本块，基于整个程序流图。	全局公共子表达式消除。
按机器	机器无关	基于中间代码 (IR)，不考虑 CPU 细节。	本章重点 (DAG, 循环优化)。
	机器相关	依赖 CPU 架构、寄存器数量。	寄存器分配、窥孔优化。

2.2 基本块 (Basic Block)

定义：单入口、单出口的线性语句序列。中间没有跳转（进或出）。

划分算法 (Partition Algorithm) - 找入口 (Leaders)：

要切分基本块，首先要找到“切分点”（首结点/入口语句）：

1. 程序的第一条语句。

2. 跳转指令（goto, if）的目标语句。

3. 紧跟在跳转指令后面的那条语句。

2.3 程序流图 (Control Flow Graph, CFG)

• 结点：基本块。

• 边：控制流向 ()。

  • 结尾跳到 。

  • 顺序执行下来紧接 （且 结尾不是无条件跳转）。

---

3. Method (核心优化方法)

3.1 局部优化：基于 DAG (有向无环图)

在基本块内构造 DAG，可以自动实现以下优化：

1. 合并已知量 (Constant Folding)：

   • 编译时计算 。

2. 删除公共子表达式 (CSE)：

   • 若 DAG 中已有结点 代表 ，再次计算 时直接指向 。

3. 删除死代码 (Dead Code Elimination)：

   • DAG 中没有父结点（没人用它）且不是活跃变量（后续程序不再读取）的根结点，可以删除。

4. 代数恒等变换：

   • , , 。

3.2 循环优化 (Loop Optimization)

这是提升程序性能的关键，通常包括三个步骤：

1. 代码外提 (Code Motion)：

   • 寻找循环不变量（在循环中值不变的量），搬到循环外面去算一次。

2. 削弱计算强度 (Strength Reduction)：

   • 用“便宜”的指令代替“昂贵”的指令。

   • 典型：乘法 加法 (如 )。

3. 删除归纳变量 (Induction Variable Elimination)：

   • 归纳变量：随循环呈线性变化的变量（如循环计数器 ）。

   • 如果 仅用于计算另一个归纳变量 和控制循环，可以用 直接控制循环，从而删掉 。

3.3 窥孔优化 (Peephole Optimization)

• 机制：在目标代码上开一个滑动的“小窗口”（如 2-3 条指令），检查并替换低效模式。

• 例子：

  • Store R, x 紧接 Load x, R 删除第二条（R 里已经是 x 了）。

  • goto L1 … L1: goto L2 改为直接 goto L2。

---

4. Example (经典例题深度解析)

例题 1：基本块划分 (Basic Block Partition)

输入代码：

Plaintext

(1) i := 1  
(2) j := 1  
(3) t1 := 10 * i      <-- L1 (Jump Target)  
(4) t2 := t1 + j  
(5) t3 := 8 * t2  
(6) t4 := t3 - 88  
(7) if t4 < 0 goto (3)  
(8) i := i + 1        <-- L2 (Follows Jump)  

解析：

1. 找入口 (Leaders)：

   • (1): 程序首句。

   • (3): goto (3) 的目标。

   • (8): 紧跟在条件跳转 (7) 之后。

2. 切分结果：

   • B1: (1) - (2)

   • B2: (3) - (7) (循环体)

   • B3: (8) … (如有后续)

例题 2：DAG 优化与代数变换

输入：

(1) a := b + c  
(2) b := b - d  
(3) c := c + d  
(4) e := b + c  <-- 重点  

DAG 构造推导：

1. 初始状态：。

2. 更新 b：。

3. 更新 c：。

4. 计算 e：。

   • 利用代数律重排：。

   • 编译器发现 这个结构在第 (1) 步已经算过了（就是 ）。

   • 优化结果：e := a。

例题 3：循环优化综合 (必考大题)

原始代码：

i := 1  
L1: t1 := i * 4      // 代价高  
    t2 := A[t1]  
    if t2 < 10 goto L2  
    i := i + 1       // 归纳变量 1  
    goto L1  
L2: ...  

第一步：强度削弱 (乘法变加法)

引入新变量 对应 的值序列 ()。

i := 1  
T1 := 4              // 1. 初始化 (i*4)  
L1: t2 := A[T1]      // 2. 替换 t1  
    if t2 < 10 goto L2  
    i := i + 1  
    T1 := T1 + 4     // 3. 用加法更新 (4*1)  
    goto L1  

第二步：删除归纳变量 (i)

观察发现 除了算 和自身自增外，没有被其他地方引用（假设循环控制不依赖 或者可以转换）。

若循环控制是 if i <= 10，可转换为 if T1 <= 40。

Plaintext

T1 := 4  
L1: t2 := A[T1]  
    if t2 < 10 goto L2  
    T1 := T1 + 4     // i 被删除了  
    goto L1