第11章代码优化.ppt

第11章代码优化,教学目的：正确理解代码优化的定义和各种可能的优化概念；掌握用DAG表示进行局部优化的方法、循环优化技术。,教学重点与难点：局部优化；DAG的构造与应用、循环优化。,学时分配：4学时,本章知识点：,局部优化,控制流分析和循环优化,数据流的分析与全局优化,优化技术简介,优化,编译前端,代码优化器,代码产生,控制流分析,数据流分析,代码变换,代码优化器的地位和结构,首页,结束,1、优化的概念：优化的定义:对程序进行各种等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大，或占用存储空间减少，或两者都有。我们通常称这种变换为优化。,11.1优化技术简介,首页,结束,优化的目的是为了产生更高效的代码。由优化编译程序提供的对代码的各种变换必须遵循下面的原则：1)等价原则主要指优化后的目标代码运行时间较短,以及占用的存储空间较小。2)有效原则使优化后所产生的目标代码运行时间确实较短，占用的空间确实较小3）合算原则应尽可能以较低的代价取得较好的优化效果,2、优化的原则,首页,结束,3、代码优化的基本方法按照与机器相关的程度，代码优化分为：与机器相关的优化：在生成目标程序时进行的，它在很大程度上与具体的计算机有关。与机器无关的优化：在语法、语义分析生成中间代码之后，在中间代码上进行，这一类优化不依赖于具体的计算机，而取决于语言的结构。,首页,结束,根据优化所涉及的程序范围分成:局部优化：基本块范围内的优化：合并已知量消除公共子表达式，削减计算强度和删除无用代码循环优化：主要是基于循环的优化，包括循环不变式外提，归纳变量删除，计算强度削减。全局优化：主要是在整个程序范围内进行的优化。因为程序段是非线性的，因此需要分析程序的控制流和数据流，处理比较复杂。,4、优化技术,合并常量计算,消除公共子表达式,削减计算强度,删除无用代码,循环不变表达式外提,归纳变量删除,首页,结束,演示,局限于基本块范围内的优化称为基本块内的优化或局部优化。1、基本块的定义所谓基本块是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。,11.2局部优化,首页,结束,划分四元式程序为基本块的算法如下：（1）求出四元式程序中各个基本块的入口语句，它们可以是下述语句之一：程序的第一个语句；,2基本块的划分算法,紧跟在条件转移语句后面的语句。,能由条件转移语句或无条件转移语句转移到的目标语句；,首页,结束,（2）对以上求出的每一入口语句构造其所属的基本块。它是由该入口语句到另一入口语句(不包括该入口语句)，或到一转移语句(包括该转移语句)，或到一停语句（包括该停语句)之间的语句序列组成的。,（3)凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，将其删除。,2基本块的划分算法,首页,结束,【例如】有下列三地址代码程序：1）readX2）readY3）R：=XmodY4）ifR=0goto(8)5)X:=Y6)Y:=R7)goto(3)8）writeY9)halt,划分为4个基本块:B11）、2）B23)、4）B35）、6）、7）B48）、9）,首页,结束,【例如】划分基本块(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)halt,划分为4个基本块:B1（1）、（2）、（3）B2（4）、（5）B3（6）、（7）B4（8）、（9）,首页,结束,3、基本块的变换基本块内可进行的优化：,合并已知常量和复写传播,临时变量改名,交换语句的位置,删除公共子表达式,删除无用代码,首页,结束,删除公共子表达式如果一个表达式E的值已计算过，并且在此之后E中变量的值没有改变，则称E为公共子表达式，为避免重复计算而删除，称为删除公共子表达式【例如】x:=(a+b)*c-(a+b)2t1=a+b;t2=t1*c;t3=a+b;t4=t32X:=t2-t4;,首页,结束,x+y*t-a*(x+y*t)/(y*t)(1)(*，y，t，t1)(2)(+，x，t1，t2)(3)(*，y，t，t3)(4)(+，x，t3，t4)(5)(*，a，t4，t5)(6)(*，y，t，t6)(7)(/，t5，t1，t7)(8)(-，t2，t7，t8),消除公共子表达式之后：(1)(*，y，t，t1)(2)(+，x，t1，t2)(3)(*，a，t2，t5)(4)(/，t5，t1，t7)(5)(-，t2，t7，t8),【例如】,返回,首页,结束,删除无用代码,若某些变量的值在整个程序中不再使用，那么这些变量的赋值对程序运行结果没有任何作用，那么就可以删除对这些变量赋值的代码，称为删除无用代码或删除无用赋值。,【例如】若T7、T8、T6在以后的程序中不再使用T6:=T2X:=T3T7:=T2T8:=T4aT2:=T5aT4:=T3,aT2:=T5aT4:=T3,返回,首页,结束,合并已知量a=10*5+6-b;t0=10;t1=5;t2=t0*t1;t3=6;t4=t2+t3；t5=t4b;a=t5;,首页,结束,【例】d=2*3.14*r(1)(*，2，3.14，t1)(2)(*，t1，r，t2)(3)(=，t2，d)2*3.14的值在编译时刻就可以确定。(1)(*，6.28，r，t2)(2)(=，t2，d),首页,结束,返回,复写传播,形成为f:=g的赋值叫做复写语句。优化过程中会大量引入复写。复写传播变换的做法是在复写语句f:=g后，尽可能用g代表f。复写传播变换本身并不是优化，但它给其它优化如常量合并和死代码删除带来机会。,t2=t1;t3=t2*t1;t4=t3;t5=t3*t2;c=t5+t4;,【例】,返回,重新命名临时变量例如:t:=b+cu:=b+c,返回,交换语句次序目的：减少临时变量【例如】相邻两个语句t1:=b+ct2:=x+yt2:=x+yt1:=b+c,基本块优化的实现从四元式序列构造DAG，然后再从DAG重写四元式。,4、基本块的有向图DAG表示,基本块内部优化实现的主要工具为：DAG(DirectedAcyclicGraph的缩写)DAG:如果有向图中任一通路都不是环路,则称该有向图为无环路有向图，也称有向非循环图,简称DAG。用DAG图表示各个值的计算/依赖关系。,演示,返回,DAG图中结点的特点1.叶结点标记:标识符名(变量名)或常数,写在结点下面。代表:该结点代表该变量或常数的值。地址的表示：Addr(A)通常将其标识符加上下标0,表示该变量的初值。,2.内部结点标记:一个运算符号，写在结点下面。代表:利用后续结点运算出来的值。,3图中各个结点可能附加一个或多个标识符,表示这些标识符具有该结点所代表的值，同一个结点的标识符表示相同的值，写在结点右面。,四元式相应的DAG,（1）A：=opB1型,该算法只对如下三种四元式构造DAG：0型A:=Bl型A:=opB2型A:=BopCop是双目运算符还可以是=或=。,基本块的DAG构造算法,输入：一个基本块输出：相应DAG图算法说明：通过逐个扫描四元式来逐渐建立DAG图。函数node(A)的值或者是一个结点的编号n或者无定义。如果是前一种情况，代表存在一个结点n，A是其上的标记或附加标识符。,基本块的DAG构造算法,首先DAG为空。对基本块的每一四元式，依次执行：1如果NODE（B）无定义，则构造一标记为B的叶结点并定义NODE（B）为这个结点；如果当前四元式是0型，则记NODE(B)的值为n，转4。如果当前四元式是1型，则转2.(1)。如果当前四元式是2型，则：(I)如果NODE(C)无定义，则构造一标记为C的叶结点并定义NODE(C)为这个结点；(II)转2.(2),2（合并已知量）（1）如果NODE(B)是标记为常数的叶结点，则转2(3)，否则转3.（1）。（2）如果NODE(B)和NODE(C)都是标记为常数的叶结点，则转2.（4），否则转3.（2）。（3）执行opB（即合并已知量），令得到的新常数为P。如果NODE(B)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4。（4）执行BopC（即合并已知量），令得到的新常数为P。如果NODE(B)或NODE(C)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4。,基本块的DAG构造算法,基本块的DAG构造算法,3（找公共子表达式）（1）检查DAG中是否已有一结点，其唯一后继为NODE(B)，且标记为op（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4。（2）检查中DAG中是否已有一结点，其左后继为NODE(B)，其右后继为NODE(C)，且标记为op（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4。,4.（删除无用赋值语句）如果NODE(A)无定义，则把A附加在结点n上并令NODE(A)=n；否则先把A从NODE(A)结点上附加标识符集中删除（注意，如果NODE(A)是叶结点，则其标记A不删除），把A附加到新结点n上并令NODE(A)=n。转处理下一四元式。,仅含0,1,2型四元式的基本块的DAG构造算法:首先：假定DAG为空，即没有任何结点。对基本块中的每一四元式依次执行：,【例】构造下列四元式序列的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,演示,根据DAG图重写四元式后得到如下优化的四元式序列：,(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(删除无用代码),【例】试对以下基本块B1应用DAG进行优化。B1:A:=B*CD:=B/CE:=A+DF:=E*2G:=B*CH:=G*GF:=H*GL:=FM:=L并就以下两种情况分别写出优化后的四元式序列：,若某个变量在基本块后不被引用,可删除。,（1）假设G、L、M在基本块后面被引用；（2）假设只有L在基本块后被引用。解：对于B1其DAG图：,(1)若只有G、L、M在基本块后被引用，则优化为：G:=B*CH:=G*GL:=H*GM:=L,(2)若只有L在基本块后被引用，则优化为：G:=B*CH:=G*GL:=H*G,11.3控制流分析和循环的优化,定义：以基本块为结点，将控制流信息增加到基本块的集合上来表示一个程序而得到的有向图，称为程序流图。如果一个结点的基本块入口语句是程序的第一条语句，则此结点为首结点。如果在某个执行顺序中基本块B2紧接在基本块B1之后执行，则从B1到B2有一条有向边。,一、程序流图,【例如】有下列三地址代码程序，给出程序流程图。1）readX2）readY3）R：=XmodY4）ifR=0goto(8)5)X:=Y6)Y:=R7)goto(3)8）writeY9)halt,演示,【例】有下列三地址代码程序，给出程序流程图。,(1）I:=1(2)ifI10goto(15)(3)T1:=2*J(4)T2:=10*I(5)T3:=T2+T1(6)T4:=add(A)11(7)T5:=2*J(8)T6:=10*I(9)T7:=T5+T6(10)T8:=add(A)-11(11)T9:=T8T7(12）T4T3:=T9+1(13)I:=I+1(14)goto(2)(15),演示,循环是程序流图中具有唯一入口结点的强连通子图。说明：1.强连通的(任意两结点间,必有一条通路,且该通路上各结点都属于该结点序列)2.它们中间有且只有一个是入口结点。,二、循环的查找,必经结点：在程序流图中，对任意两个结点m和n，若从流图的首结点出发，到达n的任一通路都要经过m，则称m是n的必经结点，记为mDOMn,流图中结点n的所有必经结点的集合，称为结点n的必经结点集，记为D(n).回边：设n-m是流图中的一条有向边，且mDOMn,则称n-m是流图中的一条回边。,【例】对下面语句划分基本块，画出程序流程图a:=1;ifa=bthenb:=1elsec:=1endif;d:=a+b,1、翻译的四元式是：1）a:=12)IFa=bgoto4)3)goto6)4)b:=15)goto7)6)c:=17)d:=a+b;,步骤：,1、翻译为四元式2、划分基本块，画程序流程图,2、划分基本块，画程序流程图,1）a:=12)IFa=bgoto4),3)goto6),4)b:=15)goto7),6)c:=1,7)d:=a+b;,(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)halt,【例】对下面语句划分基本块，画出程序流程图。,【例如】,6,7,3,4,1,2,3,5,7,6,1,2,1,2,1,2,1,必经结点必经结点集,3,下图给出求回边n-d组成的循环的算法：procedureinsen(m)；ifm不属于loopthenbeginloop:loopUm；把m下推进栈stack；end；*主程序*Stack：空；loop:d；insert(n)；whilestack非空dObegin把stack的栈顶元素m上托出去forpP(m)dOinsert(p)end,其中P(m)表示结点m的前驱结点集，stack为工作栈，loop为所求循环。insert为一过程。,算法的基本思想是：由于要求回边n-d组成的循环，这个循环将以d为其唯入口，n是它的一个出口。若n不等于d，则n的所有前驱结点应属于循环。当求出n的所有前驱后，只要它们不是循环入口d，就应再求出它们的前驱，新求出的所有前驱也应属于循环。然后再对新求出的所有前驱，重复以上步骤，直到所求出的前驱是d为止。此时算法结束。,回边66循环6744,5,6,7422,3,4,5,6,7,【例】,6,7,3,4,1,2,3,5,7,6,1,2,1,2,1,2,3,1,四元式序列如下：1）J：=0;2)L1:I=0;3)IFI8gotoL34)L2:A:=B+C5)B:=D*C6)L3:IFB=0gotoL4;7)writeB;8)gotoL5;9)L4:I:=I+1;10)IFI10goto(15),(3)T1:=2*J(4)T2:=10*I(5)T3:=T2+T1(6)T4:=add(A)11(7)T5:=2*J(8)T6:=10*I(9)T7:=T5+T6(10)T8:=add(A)-11(11)T9:=T8T7(12）T4T3:=T9+1(13)I:=I+1(14)goto(2),(15),B1,B2,B3,B4,代码外提后：,（1）I:=1,(3)T1:=2*J(6)T4:=add(A)11(7)T5:=2*J(8)T8:=add(A)-11,(,(2)ifI10goto(15),(4)T2:=10*I(5)T3:=T2+T1(8)T6:=10*I(9)T7:=T6+T5(11)T9:=T8T7(12)T4T3:=T9+1(13)I:=I+1(14)goto（2）,(15),B1,B2,B2,B3,B4,（1）I：=1,(3)T1:=2*J(6)T4:=add(A)11(7)T5:=2*J(10)T8:=add(A)-11(4)T2:=10*I(8)T6:=10*I,(2)IfI10goto(15),(5)T3:=T2+T1(9)T7:=T6+T5(11）T9:=T8T7(12)T4T3:=T9+1(13)I:=I+1(4)T2:=T2+10(8)T6:=T6+10(14)gotoB2,(15),B1,B2,B2,B3,B4,2、强度消弱：指把程序中执行时间较长的运算替换为执行时间较短的运算3、删除归纳变量,再次强度消弱如果，T2,T6出循环后不是活动变量，则可在循环后删除。,(1)I:=1,(3)T1:=2*J(6)T4:=add(A)-11(7)T5:=2*J(10)T8:=add(A)-11(4)T2:=10*I(8)T6:=10*I(5)T3:=T2+T1(9)T7:=T6+T5,(2)ifI10goto(15),(11)T9:=T8T7(12)T4T3:=T9+1(13)I:=I+1(4)T2:=T2+10(8)T6:=T6+10(5)T3:=T3+10(9)T7:=T7+10(14)gotoB2,(15),B1,B2,B2,B3,(15),解：三地址代码：,(1)I:=1(2)j:=1,B1,例3试写出以下程序段forI:=1toMdoforj:=1toNdoAI,j:=BI,j的三地址代码，然后求出其中的循环，并进行循环优化。,(3)IfIMgoto(30),(4)IfjNgoto(13),(5)T1:=I*N(6)T2:=T1+j(7)T3:=N+1(8)T4:=add(A)-T3(9)T5:=add(B)-T3(10)T4T2:=T5T2(11)j:=j+1(12)goto(4),(13)I:=I+1(14)j:=1(15)goto(3),(30),B2,B3,B4,B5,B6,代码外提：,（1）I:=1(2)j:=1,(7)T3:=N+1(8)T4:=add(A)-T3(9)T5:=add(B)-T3,(3)IfIMgoto(30),(5)T1:=I*N,(4)IfjNgoto(13),(6)T2:=T1+j(10)T4T2:=T5T2(11)j:=j+1(12)goto(4),(13)I:=I+1(14)j:=1(15)goto(3),(30),B1,B2,B2,B3,B3,B4,B5,B6,强度消弱：,I:=1j:=1,(7)T3:=N+1(8)T4:=add(A)-T3(9)T5:=add(B)-T3(5)T1:=I*N,(3)ifIMgoto(30),(4)IfjNgoto(13),(6)T2:=T1+j(10)T4T2:=T5T2(11)j:=j+1(12)goto(4),(13)I:=I+1(5)T1:=T1+N(14)j:=1(15)goto(3),(30),B1,B2,B2,B3,B4,B5,B6,强度消弱(1):,（1）I:=1(2)j:=1,(7)T3:=N+1(8)T4:=add(A)-T3(9)T5:=add(B)-T3(5)T1:=I*N,(3)IfIMgoto(30),(5)T2:=T1+j,(4)IfjNgoto(13),(10)T4T2:=T5T2(11)j:=j+1(6)T2:=T2+1(12)goto(4),(13)I:=I+1(5)T1:=I+N(14)j:=1(15)goto(3),(30),B1,B2,B2,B3,B3,B4,B5