基本块的优化

• 基本块的DAG表示

很多重要的局部优化技术首先把一个基本块转换成为一个有向无环图DAG。

基本块的DAG构造方式：

1. 基本块中出现的每一个变量有一个对应的DAG结点表示其初始值。
2. 基本块中每个语句s都有一个相关的节点N，N的子节点是基本块中其他语句的对应节点。这些语句是在s之前、最后一个对s的某个运算分量定值的语句。
3. 结点N的标号是s中的运算符；同时还有一组变量被关联到N，表示s是在此基本块中最晚对这些变量定值的语句。
4. 某些结点被指明为输出节点(output node)。这些结点的变量在基本块的出口处活跃。也就是说这些变量的值可能以后会在流图的另一个基本块被使用。

基本块的DAG表示可以使我们可以对基本块所代表的代码进行一些转换。

1. 消除局部公共子表达式。（即重复计算一个已经计算得到的值得指令）
2. 消除死代码。（即计算得到的值不会被使用的指令）
3. 可以对相对独立得语句进行重新排序，这样的重新排序可以降低一个临时值需要保持在寄存器中的时间。
4. 可以使用代数规则来重新排列三地址指令的运算分量的顺序。

• 寻找局部公共子表达式

检测公共子表达式的方法是这样的。当一个新结点M将被加入DAG中时，我们检查是否存在一个结点N，它和M具有同样的运算符和子节点，且子节点顺序相同。

如果存在这样的结点，N计算的值和M计算的值是一样的，因此可以用N替代M。

• 消除死代码

我们从一个DAG上删除所有没有附加活跃变量的根节点（即没有父结点的结点）。重复应用这样的处理就可以从DAG中消除所有对应死代码的结点。

• 代数恒等式的使用

1. 使用恒等式消除计算步骤。(示例x + 0 => x、x / 1 => x)
2. 把代价高的运算替换为代价低的。（示例：x^2 => x * x、x * 2 => x + x）
3. 常量合并。（例如3.14 * 2 => 6.28）

• 数组引用的表示

数组访问不能被当成一个变量来优化，而是需要当成一个运算。

• 指针赋值和过程调用

（《编译原理》p346）

• 从DAG到基本块的重组

（《编译原理》p347）

(END)