中间代码优化
局部优化
- 基本块内
全局优化
- 函数 / 过程内
跨函数优化
- 程序范围内
基本块：具有唯一入口和出口的块
流图：将IR划分成多个基本块，基本块与基本块之间顺序连接
划分方式：任何可被跳转的指令标记为起点，跳转指令被标记为终点
块内优化
- 代数性质
- 编译时完成常量的计算
- 运算强度削减
- 把高开销运算换成低开销的运算（除法变乘法，位运算代替）
- 被除数为常量时，有特定的优化方法
- 常数合并和传播
DAG
消除公共子表达式用
DAG生成
以DAG为导向的启发式优化算法
死代码删除
构建一个活性集合：从最后一句逆向向上构建
优化方法：反复遍历代码和状态集，若一个语句下方的状态不含有这个语句的左值，则标记为死代码，删除。反复构建活性集合和删除死代码直至无死代码存在
数据流分析
out(B) = gen(B) ∪ (in(B) - kill(B))
gen(B): B里的赋值 / 声明语句语句集合
kill(B): 在其他任意Block中声明 / 赋值了gen(B)中语句所声明/定义的变量的语句集合
到达定义分析
- 输入gen和kil得到out和in
- in(B) = ∪out(B的所有前驱块)，然后计算out(B). 从头到尾生成
- 重复上面这步直到每个B的in不变
in(B) = use(B) ∪ ( out(B) - def(B) )
use(B): 在B中，使用先于定义/赋值的变量（x = x + y这种x也算use）
def(B): 在B中，定义/赋值先于使用的变量
活跃变量分析
- 输入out和def得到out和in
- out(B) = ∪in(B的所有后继块)，然后算in(B)，从尾往头生成
- 重复上面这步直到每个B的out不变
- 此时的in(B)为B中的活跃变量
冲突图
一个无向图，边a-x表示a在x的定义点是活跃的
冲突判定：
找出跨块活跃的变量。只要出现在任何一个in或者out集合中就是跨块活跃的
找出基本块间冲突的变量。出现在同一个in或out集合的变量之间是冲突的
找出块内冲突的变量。在同一基本块中，找出「仅出现在in或out之一的变量」，用下面的定义判断仅出现在in里的变量与仅出现在out里的变量之间有没有冲突。
使用-定义链
对于变量的每个赋值语句di，找到可能会使用这一次赋值的所有语句dj们
di的def-use chain: {di, dj们}
对于同一变量的du链，若两个du链之间有交集则合并为一个du网络
这样每个变量可能有多个du网，每个du网可以单独作为一个变量，利于SSA优化
不同变量之间的du网若有交集，则可以产生冲突图中的一条边
机器架构相关优化
微处理器体系结构特点
栈式
直接操作栈上的数据
累加器式
直接操作内存
寄存器-内存式
可以直接内存寻址
寄存器-寄存器式
寄存器分配
全局寄存器是相对于基本块而言的
局部变量参与全局寄存器分配
静态变量和全局变量不参与全局寄存器分配（线程不安全，因为寄存器是线程专属的）
全局寄存器分配
- 引用计数（难以准确统计）
- 线性扫描
- 图着色算法
- 输入基本块的冲突图和寄存器个数K，规定冲突变量不能着一种颜色（分配同一个寄存器）
- 一种启发式图着色算法：Chaitin-Briggs算法
- 对所有节点，找到度数小于K的结点，压入栈S中，从冲突图中移除
- 重复上面这一步直到不存在满足条件的结点
- 从中移除一个合适的点，记为不分配全局寄存器的节点，压入栈S中
- 重复第一步
- 所有节点全部加入S后，一个个弹出来，还原到原冲突图中，依次按照“冲突变量不能着一种颜色”的规则进行着色
需要参与全局寄存器分配的变量：局部变量 && 跨块活跃变量（多个块的def-use都出现了）
冲突：a定义的时候b活跃