# 机器无关代码优化

## 常见的优化方式

1. 代码优化
   - 在不改变程序运行效果前提下，做等价变化，生成更加高效目标代码
   - 优化目标：运行时间更短，占用空间更小
   - 代码优化是编写程序过程中不可或缺的关键环节

2. 为什么代码优化
   - 程序员编写的代码存在低效计算
   - 代码翻译过程中产生冗余代码

3. 优化源头
   - 程序存在很多程序员无法避免的冗余运算
     - 数组或结构体访问会展开成多步低级算术运算
     - 而对同一个数据结构多次访问导致许多公共低级运算

4. 公共子表达式删除
   - 如果一个表达式已被计算过，且到目前为止，表达式的两个运算对象均未变化，则该表达式的本次出现是公共子表达式
   - 本次计算可被删除，直接使用上次计算结果替代
   - 局部公共子表达式&全局公共子表达式

5. 死代码删除
   - 死代码是指计算的结果永远不被引用的语句
   - 优化变换可能引起死代码
   - 复制传播、常量合并本身没有优化，但可以引起死代码删除

6. 循环系列优化
   - 强度削弱：降低每次迭代计算的复杂度，将执行时间较长的运算替换为时间较短的运算
     - 可以用增量运算替换乘法运算，如循环中的 `x=c*i+d`，中 c 和 d 为常量，i 为归纳变量，则可将其改为 `x=x+c`，每次迭代增加 c，将初始化提到循环之外
   - 删除归纳变量：如果循环中一组归纳变量的值变化保持步调一致，可只保留一个

7. 代码移动
   - 循环不变计算是指不管循环执行多少次，得到相同结果的表达式，则可以移到循环外，在进入循坏前就对循环不变计算进行求值
   - 多层循环嵌套，要由里向外分析

## 数据流与到达定值分析

1. 代码优化的实现方式
   - 全局视角：跨基本块的优化，数据流分析
   - 局部视角：基本块的优化，DAG 表示

2. 数据流分析 dataflow analysis：一组用来获取程序执行路径上的数据流信息的技术
   - 数据流分析应用：到达-定值分析 (检测未定义的变量)、活跃变量分析 (用于寄存器分配)、可用表达式分析 (检测全局公共子表达式)
   - 每一种数据流分析应用中，都会把每个程序点和一个数据流值关联起来

3. 程序点 (流图上的点)
   - 基本块中，两个相邻的语句之间的一个点
   - 基本块的开始点和结束点

4. 流图上的路径：点序列 $p_1,p_2,\ldots,p_n$，对 $i=1,2,\ldots,n-1$，$p_i$ 是先于一个语句的点，$p_{i+1}$ 是同一块中位于该语句后的点，或者 $p_i$ 是某块的结束点，$p_{i+1}$ 是后继块的开始点

5. 数据流分析介绍
   - 分析程序行为时，必须考虑在流图上的所有执行路径
   - 通常，从流图得到的程序执行路径数无限，每个程序点的不同状态数也可能无限

6. 数据流值：代表在任意程序点能观测到的所有可能程序状态集合的一个抽象
   - 对一个语句 $s$，$IN[s]$ 是 $s$ 的所有可能的到达状态集合，$OUT[s]$ 是 $s$ 的所有可能的离开状态集合

7. 传递函数 $f$：语句前后两点的数据流值受该语句的语义约束
   - 若沿执行路径正向传播，$OUT[s]=f_s(IN[s])$
   - 若沿执行路径反向传播，$IN[s]=f_s(OUT[s])$

8. 对基本块
   - 基本块中有 $IN[s_{i+1}]=OUT[s_i],i=1,2,\ldots,n-1$
   - 基本块 $IN[B]=IN[s_1]$，$OUT[B]=OUT[s_n]$
   - 基本块的传递函数
     - 正向数据流 $OUT[B]=f_B(IN[B])$，$f_B=f_n\circ\cdots f_2\circ f_1$
     - 逆向数据流 $IN[B]=f_B(OUT[B])$，$f_B=f_1\circ\cdots f_{n-1}\circ f_n$
   - 控制流约束 (此处的 $\bigcup$ 为汇合操作)
     - 正向传播 $IN[B]=\bigcup_{P\in pred(B)}OUT[P]$
     - 逆向传播 $OUT[B]=\bigcup_{S\in succ(B)}IN[S]$
   - 约束方程组的解通常不是唯一的，求解目标是找到满足约束的最精确解

9. 到达-定值分析 reaching-definitions analysis，循环不变计算的检测、常量合并、错误检测
   - 到达一个程序点的所有定值 (gen)
   - 定值注销 (kill)：在一条执行路径上，对一个变量的赋值注销先前对其的所有赋值
   - *以下不考虑变量的别名*
   - 定值点 d：对一个变量定值的语句
   - 引用点 u：对一个变量引用的语句
   - 引用-定值链 ud 链：从定值点 d 到引用点 u 的一条路径，该路径上的所有语句都不对该变量定值
   - 算法：
     - 用 gen 和 kill 分别表示一个基本块生成和注销的定值
     - 对一个语句 $f_d(x)=gen_d\bigcup (x-kill_d)$，对一个基本块 $f_B(x)=gen_n\bigcup (gen_{n-1}-kill_n)\bigcup\cdots\bigcup(gen_1-kill_2-kill_3-\cdots-kill_n)$
     - 给定初始条件 $OUT[ENTRY]\varnothing$
     - 迭代求解，到达不动点
   - 分析：
     - 是正向的方程
     - 是求并集
     - 是求最小解

## 数据流与可用表达式分析

1. 可用表达式：一个表达式中的变量在到达程序点前没有变化，则原本的表达式称为可用表达式
   - 可用表达式可以用于消除全局公共子表达式

2. 基本块生成的表达式
   - 一个语句 x=y+z 的前点处可用表达式集合为 S，则经过语句后的可用表达式集合为 $S=S\bigcup\{y+z\}$，$S=S-\{S 中所有涉及变量 x 的表达式\}$ 顺序不能颠倒，因为 x 可能就是 y 或 z
   - 对基本块中所有语句如上处理，得到基本块生成的可用表达式集合

3. 基本块杀死的表达式：所有类似 y+z 的表达式，基本块中对 y 或 z 定值，但没有生成 y+z.

4. 可用表达式分析
   - 若到点 $p$ 的每条执行路径都计算 x op y，并且计算后没有对 x 或 y 赋值，则称 x op y 在点 $p$ 可用
   - $e\_gen_B$, $e\_kill_B$, $IN[B]$, $OUT[B]$
   - $OUT[B]=e\_gen_B\bigcup(IN[B]-e\_kill_B)$
   - $IN[B]=\bigcap_{P\in pred(B)}OUT[P]$
   - $OUT[ENTRY]=\varnothing$
   - 初始化每一块的可用表达式集合为全集

5. 和之前区别
   - 使用 $\bigcap$ 作为汇合算符
   - 只有一个表达式在所有前驱结尾可用才能在开头可用
   - 求最大解

## 数据流与活跃变量分析

1. 活跃变量：对一个变量 x 和程序点 $p$，如果 x 的值在 $p$ 点开始的某条执行路径上被引用，则说 x 在 $p$ 点活跃，否则称 x 在 $p$ 点已经死亡

2. 用于为基本块分配寄存器
   - 如果所有寄存器都被占用，且还需要申请一个寄存器，则应该考虑使用已经存放死亡值的寄存器
   - 如果一个值在基本块结尾是死的，就不必在结尾处保存这个值了

3. 相关定义：$IN[B]$, $OUT[B]$, $use_B$ (块中有引用，引用前在块中没有被定值), $def_B$ (块中有定值，定值前在块中没有被引用)

4. 逆向数据流等式
   - $IN[EXIT]=\varnothing$，程序出口没有活跃变量
   - $OUT[B]=\bigcup_{S\in succ(B)}IN[S]$
   - $IN[B]=use_B\bigcup (OUT[B]-def_B)$

5. 与之前联系与区别
   - 以 $\bigcup$ 作为汇合算符
   - 信息流动方向相反
   - 求最小集

## 基本块内的优化

1. 基本块的 DAG 表示
   - 每个变量有一个对应的 DAG 节点表示初值
   - 每条语句对应一个内部节点，标号是运算符，一组变量被关联，在这个语句之前最后一次被定值的语句对应节点为该节点的子节点
   - 某些节点是输出节点，在出口处活跃
   - 如果某条语句的表达式已经被值编码，则可以直接在已存在的节点关联变量中增加该语句结果

2. 删除局部公共子表达式
   - 假如两个语句有公共表达式，而其中一个结果在基本块出口处不活跃，则可以直接留下另一个语句，删去不活跃的
   - 而如果一个节点有多个关联的活跃变量，必须引入复制语句，为每个变量赋正确的值

3. 删除死代码
   - 删除所有没有关联活跃变量的根节点，直到没有节点可以被删除

4. 代数恒等式的使用
   - 可以消除的计算：$x + 0$, $x - 0$, $x * 1$, $x / 1$
   - 局部强度消减：$x^2=x*x$, $2*x=x+x$,$x/2=x*0.5$
   - 常量合并：计算常量表达式的值，可能是宏展开
   - 交换律
   - 结合律

5. 数组引用的表示
   - 数组取值的三地址指令创建一个运算符为 `=[]` 的节点，节点子节点为数组名和下标
   - 数组赋值的三地址指令创建一个运算符为 `[]=` 的节点，节点子节点为数组名、下标和赋的值

6. 从 DAG 到基本块的重组
   - 遍历图，恢复节点