优化讲义.ppt

例：构造以下基本块的DAG (1) T0:=3.14 (2) T1:=2*T0 (3) T2:=R+r (4) A:=T1*T2 (5) B:=A (6) T3:=2*T0 (7) T4:=R+r (8) T5:=T3*T4 (9) T6:=R－r (10) B:=T5*T6 T6 ,T5 ,T3 T0 ,T4 6.28 n2 R n3 r n4 3.14 n1 B * n6 * n8 － n7 + n5 2 T1 T2 A ,B 2 * 7.2.3 DAG的应用 在一个基本块被构造成相应的DAG的过程中，进行了如下基本的优化工作： 合并已知量 在DAG构造算法中，如果运算量都是已知量，则不生成计算该结点值的内部结点，而执行该运算，将计算结果生成一个叶结点，实现了合并已知量优化 * 删除多余运算 对具有公共子表达式的所有四元式，只生成一个计算该表达式的内部结点，所有被赋值的变量都作为该结点的附加标识符，实现了删除多余运算的优化 删除无用赋值 如果变量被赋值后，在它被引用前又被重新赋值，则变量被从具有前一个值的结点上删除 * － + r T6 A, T5 * T1,T3 T0 R 6.28 3.14 T2,T4 n5 n7 n2 n3 n4 n1 B * n6 n8 (1) T0 :=3.14 (2) T1 :=6.28 (3) T3 :=6.28 (4) T2 :=R+r (5) T4 :=T2 (6) A :=6.28*T2 (7) T5 :=A (8) T6 :=R－r (9) B :=A*T6 由DAG重新生成原基本块的一个优化的代码序列： * 原基本块的四元式序列G (1) T0:=3.14 (2) T1:=2*T0 (3) T2:=R+r (4) A:=T1*T2 (5) B:=A (6) T3:=2*T0 (7) T4:=R+r (8) T5:=T3*T4 (9) T6:=R－r (10) B:=T5*T6 按DAG重新写成的四元式序列G’ (1) T0 :=3.14 (2) T1 :=6.28 (3) T3 :=6.28 (4) T2 :=R+r (5) T4 :=T2 (6) A :=6.28*T2 (7) T5 :=A (8) T6 :=R－r (9) B :=A*T6 G中(2)(6)的已知量已合并 G中(5)的无用赋值已删除 G中(3)(7)的公共子表达式R+r 只计算一次，删除了多余运算 * 利用DAG进行优化 删除在基本块后不被引用变量的赋值 r R 6.28 3.14 － + T6 A, T5 * T1,T3 T0 T2,T4 n5 n7 n2 n3 n4 n1 B * n6 n8 假如T0，T1，…，T6在基本块后都不被引用，则这些符号可在DAG附加标识符中删去，重写四元式得到进一步的优化： （1） S1:=R+r （2） A:=6.28*S1 （3） S2:=R－r （4） B:=A*S2 其中S1和S2是临时变量。 T0，T1，…，T6被赋值的代码被优化掉 * 7.3 循环优化简介 循环就是程序中那些可能反复执行的代码序列。 因为循环中的代码要反复执行，所以循环的代码优化对提高目标代码的效率将起更大的作用。 * 7.3.1 程序流图 把控制流的信息加到基本块集合上构成的有向图称为表示程序的流图，简称流图。 流图的构造方法： 点集：以基本块为结点，含程序第一条语句的结点为首结点。 边集：从基本块Bi向基本块Bj引有向边，仅当 Bj在程序中的位置紧跟在Bi之后, 且Bi的出口语句不是无条件转移语句或停止语句。或者 Bi的出口是转移语句 (goto (s)或if…goto (s))，并且转移目标(s)是Bj的入口语句。 * 例：构造以下程序的流图 (1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:=Y (6) Y:=R (7) goto (3) (8) write Y (9) halt (1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:=Y (6) Y:=R (7) goto (3) (8) write Y (9) halt * 7.3.2 循环优化 1. 代码外提 把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面，使之只在循环外计算一次，这种优化称为代码外提。 循环不变运算：运算量为常量或在循环外定值，每次循环时其值不变的运算