第十章代码优化.ppt

* * e_kill[B]的计算 设流图的表达式全集为E; 初始设置：EK = 空； 顺序扫描基本块的每个四元式： 对于四元式op x y z，把表达式x op y从EK中消除； 把E中所有和z相关的四元式加入到EK中。 扫描完所有的四元式之后，EK就是所求的e_kill[B]。 * * 数据流方程 out[B]=e_gen[B]∪(in[B]-e_kill[B]) in[B]= ∩out[p] B!=B1, p是B的前驱。 in[B1]=空集 说明： 在程序开始的时候，无可用表达式。(3) 一个表达式在某个基本块的入口点可用，必须要求它在所有前驱的出口点也可用。（2） 一个表达式在某个基本块的出口点可用，或者该表达式是由它的产生的；或者该表达式在入口点可用，且没有被注销掉。（1） B p2 p1 p3 IN OUT GEN -KILL * * 方程求解算法 迭代算法 初始化：in[B1]=空; out[B1]=e_gen[B1];out[Bi]=U-e_kill[Bi](i=2) 重复执行下列算法直到out稳定: for（i=2; i=n ;i++) { in[Bi]= ∩out[p], p是Bi的前驱； out[Bi]=e_gen[Bi] ∪(in[Bi]-e_kill[Bi]); } * * 算法说明 初始化值和前面的两个算法不同。out[Bi]的初值大于实际的值。 在迭代的过程种，out[Bi]的值逐渐缩小直到稳定。 U表示四元式的全集，就是四元式序列中所有表达式x op y的集合。 * * 10.4 局部优化 基本块的功能实际上就是计算一组表达式，这些表达式是在基本块出口活跃的变量的值。如果两个基本块计算一组同样的表达式，则称它们是等价的。 可以对基本块应用很多变换而不改变它所计算的表达式集合，许多这样的变换对改进最终由某基本块生成的代码的质量很有用。 利用基本块的dag表示可以实现一些常用的对基本块的变换。 * * 10.4.1 基本块的dag表示 dag的构造方法 ⑴ 基本块中出现的每个变量都有一个dag节点表示其初始值。 ⑵ 基本块中的每个语句s都有一个dag节点n与之相关联。n的子节点是那些在s之前、最后一次对s中用到的运算对象进行定义的语句所对应的节点。 ⑶ 节点n由s中用到的运算符来标记，节点n还附加了一组变量，这些变量在基本块中都是由s最后定义的。 ⑷ 如果有的话，还要记下那些其值在块的出口是活跃的节点，它们是输出节点。流图的另一个基本块以后可能会用到这些变量的值。 * * 利用dag进行的基本块变换 ⑴ 局部公共子表达式删除。 ⑵ 无用代码删除。 ⑶ 交换两个独立的相邻语句的次序，以便减少某个临时值需要保存在寄存器中的时间。 ⑷ 使用代数规则重新排列三地址码的运算对象的顺序，以便简化计算过程。 * * 10.4.2 局部公共子表达式删除 例10.12 a := b+c b := a-d c := b+c d := a-d (10.8) 如果b在出口处不是活跃的： a := b+c d := a-d c := d+c 图10.13 基本块(10.8)的dag * * 10.4.3 无用代码删除 在dag上删除无用代码的方法很简单：只要从dag上删除所有没有附加活跃变量的根节点(即没有父节点的节点)即可。重复进行这样的处理即可从dag中删除所有与无用代码相对应的节点。 a := b+c b := b-d c := c+d e := b+c 图10.14中的a和b是活跃变量， 而c和e不是，我们可以立即删除 标记为e的根节点。随后，标记 为c的节点变成了根节点， 下一步也可以被删除。 图10.14基本块(10.9)的dag * * 10.4.4代数恒等式的使用 代数恒等式代表基本块上另一类重要的优化方法，下面是一些常见的代数恒等式： x+0 = 0+x = x x–0 = x x*1 = 1*x = x x/1 = x 另外一类代数优化是局部强度削弱，即用较快的运算符取代较慢的运算符，例如： x**2 = x*x 2.0*x = x+x x/2 = x*0.5 * * 10.4.4代数恒等式的使用 第三类相关的优化技术是常量合并。即在编译时对常量表达式进行计算，并利用它们的值取代常量表达式。例如，表达式2*3.14可以替换为6.28。 dag构造过程可以帮助我们应用上述和更多其它的通用代数变换，比如交换律和结合律。 * * 10.4.5 数组引用的dag表示 在dag中表示数组访问的正确方法为： 将数组元素赋给其他变量的运算(如x = a[i])用一个新创建的运算符为=[]的节点表示。该节点