基本块的优化
DAG图的构造
针对基本块的优化可以有很好的效果（局部优化）。许多局部优化技术需要先将基本块内的指令转化为有向无环图（Directed Acyclic Graph，DAG）。DAG可反映变量及其值对其他变量的依赖关系。
每个变量都有一个对应的DAG节点表示其初始值。每个语句都有一个相关的节点N，代表此计算得到的值。N的子节点对应于（得到其运算分量当前值的）其他语句，N的标号是s中的运算符，同时还有一组变量被关联到N，表示s是最新对这些变量进行定值的语句。
DAG图描述了基本块运行时各变量的值 (和初始值) 之间的关系。以DAG为基础，对代码进行转换。
局部公共子表达式
局部公共子表达式的发现：建立某个结点 M 之前，检查是否存在一个结点 N，它和 M 具有相同的运算符和子结点 (顺序也相同)。如果存在，则不需要生成新的结点，用N代表M。
消除死代码
在DAG图上消除没有附加活跃变量的根节点，即消除死代码。
基于代数恒等式的优化
实现这些优化，只需在DAG图上寻找特定的模式。
数组引用
a[j]可能改变a[i]的值，因此不能像普通运算符一样构造节点。
从数组取值的运算
x=a[i]对应于=[]的节点，这个节点的左右子节点是数组初始值a0和下标i，变量x是这个节点的标号之一。对数组赋值的运算
a[i]=j对应于[]=的节点，这个节点的三个子节点分别表示a0、j和y。杀死所有依赖于a0的节点。
指针赋值/过程调用
通过指针进行取值/赋值：x=*p *q=y
x使用了任意变量，因此无法消除死代码
*q=y对任意变量赋值，因此杀死了全部其他节点
可以通过（全局/局部）指针分析部分地解决这个问题。
过程调用也类似，必须安全地假设它使用了可访问范围内的所有变量，修改了可访问范围内的所有变量。
从DAG到基本块
重构的方法：
每个结点构造一个三地址语句，计算对应的值
结果应该尽量赋给一个活跃的变量
如果结点有多个关联的变量，则需要用赋值语句进行赋值
窥孔优化（peephole optimization）
使用一个滑动窗口（窥孔）来检查目标指令，在窥孔内实现优化。比如冗余指令消除、控制流优化、代数化简/强度消减、机器特有指令的使用。滑动窗口 (窥孔) 并无准确定义，可理解为只需关注少量相关指令即可完成的优化
冗余指令消除
控制流优化
代数化简/强度消减和机器特有指令
Last updated