编译原理,清华大学,第2版_第11章 代码优化

•11.1优化技术简介•11.2局部优化•11.3控制流分析和循环优化第十一章代码优化11.1优化技术简介一、优化的原则1、等价原则优化后不改变原程序运行的功能。2、有效原则优化后产生的目标代码运行时间较短，占用空间较小。•与机器无关的优化---中间代码优化。•依赖于机器的优化---目标代码优化。二、优化阶段源代码中间代码目标代码中间代码优化目标代码优化三、优化分类(1)局部优化:对基本块内的代码进行优化(2)循环优化:对循环中的代码进行优化(3)全局优化:在整个程序范围内的优化四、常用优化技术简介1.删除多余运算2.循环不变代码外提3.强度削弱4.变换循环控制条件5.合并已知量与复写传播6.删除无用赋值例如：（假设数组元素占用空间为4个字节）P:=0forI:=1to20doP:=P+A[I]*B[I]1.删除多余运算（删除公共子表达式）：目的：提高目标代码速度。(6)T4:=4*I(7)T5:=addr(B)(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI=20goto(3)(1)P:=0(2)I:=0(3)T1:=4*I(4)T2:=addr(A)(5)T3:=T2[T1](7)T5:=addr(B)(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI=20goto(3)(6)T4:=T1变址取数(1)P:=0(2)I:=0(3)T1:=4*I(4)T2:=addr(A)(5)T3:=T2[T1]目的：减少循环中代码总数。方法：把循环不变运算，即其结果独立于循环执行次数的表达式提到循环的前面，使之只在循环外计算一次。2、代码外提(1)P:=0(2)I:=0(3)T1:=4*I(4)T2:=addr(A)(5)T3:=T2[T1](6)T4:=T1(7)T5:=addr(B)(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI=20goto(3)(1)P:=0(2)I:=0(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)T2:=addr(A)(7)T5:=addr(B)•基本思想：把强度大的运算换算成强度小的。例如：a)i*2=2*i=i+ib)0-1=-1c)f/2.0=f*0.53.强度削弱(1)P:=0(2)I:=0(4)T2:=addr(A)(7)T5:=addr(B)(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)(1)P:=0(2)I:=0(4)T2:=addr(A)(7)T5:=addr(B)(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(5)(3)T1:=4*I(3‘)T1:=T1+44、变换循环控制条件•经过变换后，有些变量不被引用，可以从循环中删除。(1)P:=0(2)I:=0(4)T2:=addr(A)(7)T5:=addr(B)(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)(1)P:=0(2)I:=1(4)T2:=addr(A)(7)T5:=addr(B)(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)ifgoto(5)T1=805、合并已知量与复写传播•编码时的已知量—常数，可在编译时计算出它的值，这种变换称为合并已知量或常数合并。•通过复制后没有再改变的值可以互相替换，不会改变程序的结果，这种变换称为复写传播。2020/1/2015复写传播tmp2=tmp1;tmp3=tmp2*tmp1;tmp4=tmp3;tmp5=tmp3*tmp2;c=tmp5+tmp4;tmp3=tmp1*tmp1;tmp5=tmp3*tmp1;c=tmp5+tmp3;(1)P:=0(2)I:=0(4)T2:=addr(A)(7)T5:=addr(B)(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:=0(4)T2:=addr(A)(7)T5:=addr(B)(5)T3:=T2[T1](6)T4:=T1(9)T7:=T3*T6(10)P:=P+T7(3’)T1:=T1+4(12)ifT1=80goto(5)(3)T1:=0(8)T6:=T5[T1](1)P:=0(2)I:=0(4)T2:=addr(A)(7)T5:=addr(B)(3)T1:=0(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)(1)P:=0(4)T2:=addr(A)(7)T5:=addr(B)(3)T1:=0(5)T3:=T2[T1](8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(3’)T1:=T1+4(12)ifT1=80goto(5)6.删除无用赋值11.2局部优化一、基本块1、定义程序中一个只有一个入口和一个出口的一段顺序执行的语句序列，称为程序的一个基本块。注：1)一个给定的程序，可以划分为一系列的基本块。优化在各基本块中分别进行(局部优化)。2)在运行基本块时，只能从其入口进入，从出口退出。(1)求出各基本块的入口语句1)程序的第一个语句；2)能由条件转移语句和无条件转移语句转移到达的语句；3)紧跟在条件转移语句后面的语句。2、划分基本块算法2020/1/2020(2)对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)之间的语句序列组成的。入口语句n……入口语句m2020/1/2021(2)对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)之间的语句序列组成的。入口语句n……入口语句m入口语句n……转移语句m2020/1/2022(2)对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)、或一停语句(包括该停语句)之间的语句序列组成的。入口语句n……入口语句m入口语句n……转移语句m入口语句n……停语句m(3)删除不会被执行的语句凡是没有纳入到任何一个基本块中的语句，都是程序控制流程所无法到达的语句，即不会被执行到的语句，可将其删除。2020/1/2024•例：划分基本块(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。2020/1/2025•例：划分基本块(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。2020/1/2026•例：划分基本块(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。2020/1/2027•例：划分基本块(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。2020/1/2028•例：划分基本块(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。2020/1/2029•例：划分基本块(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt2.对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)、或一停语句(包括该停语句)之间的语句序列组成的。2020/1/2030(1)read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt2020/1/2031划分为四个基本块（8）（9）（1）（2）（3）（4）（5）（6）（7）主要是进行已知量合并、删除公共子表达式、删除无用赋值。注：无用赋值有以下情形：(a)对某变量A赋值后，在程序中没有引用；(b)对某变量A赋值后，在引用前又重新赋值；(c)对某变量A进行自增赋值，且它仅仅被用在自增运算中。对上面第一和第三种情况，应进行全局分析。3、块内优化1、DAG(有向无环图)定义a)父子结点若在一有向图中，结点ni有弧指向nj，则称ni是nj的父结点，nj是ni的子结点。b)路径与环路若在一有向图中，结点n1n2……nk间存在有向弧n1n2……nk,则称n1到nk之间存在一条通路，若n1＝nk则该路径称为环路；c)有向无环图若有向图中任一路径都不是环路，则称该图为无环路有向图。二、基本块的DAG表示a)叶结点没有子结点的结点称为叶结点，以一标识符(变量名)或常数作为标记。即该结点代表该变量或常数的值。注：1)若叶结点代表变量a的地址，则标记为addr(a)2)通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。b)内部结点以一运算符作为标记。即该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。c)各结点上可能附加一个或多个标识符，表示这些标识符具有该结点所代表的值，简称附标。2、DAG结点标记或附加信息注：1)图中的有向弧都省去箭头。2)结点ni是构造DAG过程中给予各结点的编号;3)各结点下面的符号（运算符、变量、常数）是各结点的标记;4)各结点右边的标识符是结点的附标。n1n2n3BCAop例如：A:=BopC即四元式(op,B,C,A)的DAG图为：根据其对应结点的子结点个数，可分为0型、1型、2型和3型四种类型。A)0型A:=B,即四元式(:=,B,_,A),