CP-8.md

# 8 中间代码优化
## 8.1 优化方法概述
- 在不改变语义的情况下，对中间代码进行加工变换
- 提高效率、缩短运行时间、减少运行空间
- 优化目标：提过程序的质量，尤其是运行速度
- 优化要求
- 保证正确性
- 使运行速度有数量级上的提高
- 适度
- 优化对象：主要针对循环内下标变量地址的计算
- 分类
- 源程序阶段的优化
- 编译阶段的优化
- 前端中间代码级
- 局部优化：基本块内的优化
- 常量表达式优化：合并常数项
- 公共表达式优化：消除重复操作
- 非局部优化：涉及范围比基本块大
- 循环优化：循环不变表达式外提
- 全局优化：超越循环之后需要完成
- 后端目标代码级
- 有效合理使用机器资源
- 减少指令个数提高执行效率
- 典型优化方法
- 常量表达式优化：合并常数项
- 公共表达式优化：消除重复操作
- 循环不变表达式外提
## 8.2 基本块划分
- 程序的一组顺序执行的语句序列
- 入口：第一条语句
- 出口：最后一条语句
- 基本块只有一个入口和出口
- 执行时只能从入口进入、出口退出
- 基本块内部的语句要么全执行，要么全不执行
- 不能从中间转入或转出
- 可基于源代码、中间代码、目标代码
- 标号性中间代码
- 定位性四元式
- 如 $\mathrm{LABEL,ENTRY,WHILE,ENDIF}$ 等
- 转移性中间代码
- 产生跳转指令的四元式
- 如 $\mathrm{JMP,ENDPROC,ENDFUNC,THEN,ELSE,DO,ENDWHILE}$ 等
- 基于四元式中间代码基本块划分原则
- 初始四元式为第一个基本块的入口
- 遇到转移性中间代码时
- 结束当前基本块
- 把转移性中间代码作为出口
- 把下一条中间代码作为新基本块的入口
- 遇到标号性中间代码时
- 结束当前基本块
- 把标号性中间代码作为新基本块的入口
- 遇到 $(\mathrm{ASSIG},A,\_,X)$ 时
- 若 $X$ 为引用型形参
- 结束当前基本块
- $\mathrm{ASSIG}$ 作为出口
- 程序流图：以基本块为结点的有向图
## 8.3 常量表达式优化
- 常量定值表 $\mathrm{ConstDef}$，元素为 $(\mathrm{Var,Val})$
- 基本块常量表达式优化算法
- 基本块入口置 $\mathrm{ConstDef}$ 为空
- 读当前四元式
- 利用 $\mathrm{ConstDef}$ 替换得新四元式
- 若新四元式形如 $(\omega,A,B,t)$ 且 $A,B$ 为常量
- 将 $(t,A\ \omega \ B)$ 填入 $\mathrm{ConstDef}$
- 删除当前四元式
- 若新四元式形如 $(\mathrm{ASSIG},A,\_,B)$
- $A$ 是常数，将 $(B,A)$ 填入 $\mathrm{ConstDef}$
- 否则从 $\mathrm{ConstDef}$ 删除 $B$ 的登记项
- 重复直至基本块结束
## 8.4 公共表达式优化
- 四元式等价：两个非赋值的运算类四元式，对应运算和分量相同
- 公共表达式（可节省的公共代码 ECC）
- 基本块中除第一个以外其他等价的四元式
- 实现
- 值编码优化方法
- 逻辑尺优化方法
- DAG 优化方法
- 值编码优化方法
- $\mu(x)$ 表示任意运算分量 $x$ 的值编码
- $\mathrm{NewVN}$ 为新值编码产生器，从 $1$ 开始递增
- $(\mu(A),\mu(B),\mu(t))$ 为四元式 $(\_,A,B,t)$ 的映像码
- $(\omega,\mu(A),\mu(B),\mu(t))$ 为 $(\omega,A,B,t)$ 的编码四元式
- 三张表
- 值编码表 $\mathrm{ValiNum}$
- 存放变量或常数及其值编码
- 可用表达式代码表 $\mathrm{UsableExpr}$
- 存放基本块中可用于匹配的表达式编码四元式
- 临时变量等价表 $\mathrm{PAIR}$
- 存放等价的临时变量偶对
## 8.5 基于值编码的公共表达式优化算法
- 从基本块第一条四元式开始
- $\mathrm{PAIR}$ 替换结果，值编码替换分量
- 对四元式的新运算分量进行值编码，生成编码四元式
- 遇到运算型四元式，在 $\mathrm{UsableExpr}$ 中查
- 算符和分量都相同说明当前四元式为 ECC，删去，并把结果临时变量填入 $\mathrm{PAIR}$
- 遇到赋值四元式，左侧编码和右侧编码相同
## 8.6 循环不变式外提优化
- 循环不变式：表达式 $E$ 在循环内不变
- 流程
- 循环识别
- 基于程序或程序流图
- 安全性
- 除法不能外提（除零溢出）
- 赋值不能外提（循环不一定执行）
- 外提策略
- 凡是循环不变式都外提
- 只外提一定被执行的循环不变式
## 8.7 循环不变式外提算法
- 第一次扫描，把循环体内定义的变量填到变量信息表 $\mathrm{LoopDef}$
- 第二次扫描
- 遇到运算型四元式，若运算分量都不在 $\mathrm{LoopDef}$ 中
- 外提
- 在 $\mathrm{LoopDef}$ 中删去对应变量，移到外层