第9章代码优化目录9.1优化技术简介与机器无关的优化---对中间代码进行；依赖于机器的优化--对目标代码进行四、优化分类五、常用优化技术简介目的：提高目标代码速度。例如：P:=0forI:=1to20doP:=P+A[I]*B[I](1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2[T1](6)T4:=4*I(7)T5:=addr(B)-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(3)减少循环中代码总数的重要办法。方法：把循环不变运算，即其结果独立于循环执行次数的表达式提到循环的前面，使之只在循环外计算一次。例如：P:=0forI:=1to20doP:=P+A[I]*B[I](1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2[T1](6)T4:=T1(7)T5:=addr(B)-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(3)基本思想：把强度大的运算换算成强度小的。例如：a)i*2=2*i=i+i=i<<1b)i/2=(int)(i*0.5)c)0-1=-1d)f*2=2.0*f=f+fe)f/2.0=f*0.5(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(3)4、变换循环控制条件(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)ifI<=20goto(5)5、合并已知量与复写传播(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(3’)T1:=T1+4(12)ifT1<=80goto(5)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(3’)T1:=T1+4(12)ifT1<=80goto(5)局部优化：基本块内的优化a)求出各基本块的入口语句对四元式程序，各个基本块的入口语句是：1)程序的第一个语句；或2)能由条件转移语句和无条件转移语句转移到达的语句；或3)紧跟在条件转移语句后面的语句。注：若条件语句由真转移和假转移两条语句组成，则跟在转移语句后面的语句是指假转移语句后面的一条语句。b)根据入口语句，构造其所属的基本块一入口语句所属的基本块是由该入口语句到:下一入口语句(不包括该入口语句);或到一转移语句(包括转移语句);或到一停(halt)语句(包括该语句)之间的语句序列组成。C)删除不会被执行的语句凡是没有纳入到任何一个基本块中的语句，都是程序控制流程所无法到达的语句，即不会被执行到的语句，可将其删除。例：求最大公因子算法beginreadX;readY;while(XmodY<>0)dobeginT:=XmodY;X:=Y;Y:=Tend;writeYend(1)ReadX(2)ReadY主要是进行已知量合并、删除公共子表达式、删除无用赋值。注：仅在一个基本块中，是否是无用赋值很难判断。这是因为，无用赋值有以下情形：(a)对某变量A赋值后，在程序中没有引用；(b)对某变量A赋值后，在引用前又重新赋值；(c)对某变量A进行自增赋值，且它仅仅被用在自增运算中。对上面第一和第三种情况，应进行全局分析。1、DAG(有向无环图)定义a)父子结点若在一有向图中，结点ni有弧指向nj，则称ni是nj的父结点，nj是ni的子结点。B)路径与环路若在一有向图中，结点n1n2……nk间存在有向弧n1n2……nk,则称n1到n