第10章 优化.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,10.1 优化概述,1,10.1 优化概述,本节内容,一,.,代码优化概念、目的与原则,二,.,代码优化器的地位和结构,三,.,代码优化分类,四,.,代码优化涉及的各个环节,五,.,四元式的改写,六,.,引例：优化主要方法简介,2,一.代码优化概念、目的与原则,优化的,目的,是为了产生,更高效的代码,。,对程序进行各种,等价变换,，使得从变换后的程序出发，能生成,更有效的目标代码,，我们通常称这种变换为,优化,。,优化的原则：,(1),等价原则,(3),合算原则,(2),有效原则,经过优化后,不应改变,程序运行的结果。,使优化后所产生的目标代码,运行时间较短,，占用的,存储空间较小,。,应尽可能以,较低的代价,取得较好的优化效果。,3,二.代码优化器的地位和结构,编译前端,代码生成,代码优化器,控制流分析,代码变换,数据流分析,4,三.代码优化分类,另一类重要的优化是在生成,目标代码,时进行的这类优化,很大程序上依赖于,具体的计算机。,优化可在编译的各个阶段进行,最主要一类优化是在目标代码生成以前，对语法分析后的,中间代码,进行的。这类优化,不依赖于,具体的计算机。,1.,按所处阶段分类,5,三.代码优化分类,单个基本块内,局部优化,2.,按所涉及范围,循环优化,涉及所有代码,全局优化,可能涉及多个基本块,6,四.代码优化涉及的各个环节,选择适当的,算法,源代码,安排适当的,实现语句,源代码的优化很重要,设计语义动作时,考虑产生,更加高效的中间代码,为后面的优化阶段做一些,可能的预备工作,中间代码,安排,专门,的优化阶段，进行各种等价变换,本章讨论的重点,目标代码,有效地利用寄存器,选择指令,窥孔优化,7,五.四元式的改写,(:=,B,A),改写成,A:=B,(op,B,A),改写成,A:=op B,(op,B,C,A),改写成,A:=B op C,(=,B,C,A),改写成,A:=BC,(=,B,DC),改写成,DC:=B,(,jrop,B,C,L),改写成,if B,rop,C,goto,L,(j ,L),改写成,goto,L,8,六.引例：优化主要方法简介,1.,快速排序子程序：,C,语言,-,原始中间代码,B6,B1,B2,B3,B4,B5,i=m-1;,j=n;,v=,an,;,i:=m-1,j:=n,T,1,:=4*n,v:=aT1,do i=i+1;,while(,ai,v);,i:=i+1,T,2,:=4*i,T,3,:=aT,2,if T,3,v);,j:=j-1,T,4,:=4*j,T,5,:=aT,4,if T,5,v,goto,B3,if(i=j),break;,if i=j,goto,B6,x=,ai,;,ai,=,aj,;,aj,=x;,T,6,:=4*i,x:=aT,6,T,7,:=4*i,T,8,:=4*j,T,9,:=aT,8,aT,7,:=T,9,T,10,:=4*j,aT,10,:=x,goto,B2,x=,ai,;,ai,=,an,;,an,=x;,T,11,:=4*j,x:=aT,11,T,12,:=4*i,T,13,:=4*n,T,14,:=aT,13,aT,12,:=T,14,T,15,:=4*n,aT,15,:=x,9,如果一个表达式,E,在前面已计算过，并且,在这之后,E,中变量的值没有改变,，则称,E,为,公共子表达式,。,2.,删除公共子表示式,(,删除多余运算,),六.引例：优化主要方法简介,对于公共子表达式，我们可以,避免对它的重复计算,，称为,删除公共子表达式,(,有时称,删除多余运算,),。,公共子表达式可以在,基本块内,，也可以在,全局范围内,消除。,10,3.,删除公共子表示式示例,六.引例：优化主要方法简介,T,6,:=4*i,T,7,:=4*i,T,7,:=T,6,T,8,:=4*j,T,10,:=4*j,T,10,:=T,8,T,2,:=4*i,T,6,:=4*i,T,6,:=T,2,T,4,:=4*j,T,8,:=4*j,T,8,:=T,4,11,T,6,：,=T,2,(,复写语句,),把,T,2,赋给,T,6,，,x,：,=aT,6,中,引用,了,T,6,的值，而,这中间没有改变,T,6,的值,。因此，可以把,x,：,=aT,6,变换为,x,：,=aT,2,这种变换称为,复写传播,。,4.,复写传播,(,重复传送,),六.引例：优化主要方法简介,“复写”强调了,重复性,，传播是由复写引起的,复写传播的,目的,是使对某些变量的,赋值变为无用,换言之，将来可以,删除,这些无用赋值语句,12,5.,复写传播示例,六.引例：优化主要方法简介,T,6,:=T,2,x:=aT,6,x:=aT,2,T,6,:=T,2,T,7,:=T,6,T,7,:=T,2,T,6,:=T,2,aT,7,:=T,9,aT,2,:=T,9,T,7,:=T,6,T,8,:=T,4,T,9,:=aT,8,T,9,:=aT,4,T,8,:=T,4,T,10,:=T,8,T,10,:=T,4,T,8,:=T,4,aT,10,:=x,aT,4,:=x,T,10,:=T,8,在,B2,中有,T,3,:=aT,2,x:=aT,2,x:=T,3,在,B2,中有,T,3,:=aT,2,aT,4,:=x,aT,4,:=T,3,x:=aT,2,在,B3,中有,T,5,:=aT,4,T,9,:=aT,4,T,9,:=T,5,在,B3,中有,T,5,:=aT,4,aT,2,:=T,9,aT,2,:=T,5,T,9,:=aT,4,13,由于某些变量的,值在整个程序中不再被使用,，因,此，这些变量的,赋值对程序运算结果没有任何作,用,。我们可以删除对这些变量赋值的代码。我们,称之为,删除无用赋值,或,删除无用代码,。,6.,删除无用代码,(,删除无用赋值,),六.引例：优化主要方法简介,14,7.,删除无用代码示例,六.引例：优化主要方法简介,aT,2,:=T,5,aT,4,:=T,3,goto,B2,无用代码,15,对于循环中的有些代码，如果它,产生的结果在循环中是不变的,，就可以把它,提到循环外来,，以避免每循环一次都要对这条代码进行运算。这种变换称为,代码外提,。,8.,代码外提,(,频度削弱,),六.引例：优化主要方法简介,while(i=,limit-2,);,t:=,limit-2,;,while(i=j,变换成,if T,2,=T,4,同时删除,i:=i+1,j:=j-1,两条自赋值语句,19,10.2 局部优化,本节内容,一,.,基本块,二,.,基本块内的优化方法,三,.,流图,四,.,基本块的,DAG,表示及其应用,五,.,应用,DAG,时的相关问题,20,一.基本块及流图,对一个基本块来说，执行时只能,从其人口进人，从其出口退出,人口,就是其中的第一个语句,出口,就是其中的最后一个语句,局限于基本块范围内的优化称为,基本块内的优化,，或称为,局部优化,。,所谓,基本块,，是指程序中,一顺序执行,的语句序列，其中只有,一个人口和一个出口,。,1.,基本块,21,一.基本块及流图,在一个基本块中的一个名字，所谓在程序中的某个给定点是,活跃的,，是指如果在程序中（包括在本基本块或在其他基本块中）它的值在该点以后被引用,如果一条三地址语句为,x,：,=y+z,，,则称对,x,定值,并,引用,y,和,z,此时,T,2,被定值,引用了,a,和,b,2.,定值与引用,此点,T,2,是活跃的,因为后面两处引用了,T,2,T,2,T,2,T,2,22,一.基本块及流图,1.,确定四元式程序中各个基本块的人口语句,3.,划分四元式程序为基本块的算法,(1),程序的第一个语句,(2),能由条件转移语句或无条件转移语句转移到的语句,(3),紧跟在条件转移语句后面的语句,2.,对以上求出的每一人口语句，构造其所属的基本块,它是由该人口语句（开始）到,另一人口语句,(,不包括该人口语句,),，或到,一停语句,(,包括该停语句,),一转移语句,(,包括该转移语句,),，或到,之间的语句序列组成的,3.,删除无用代码,凡未被纳入某一基本块中的语句，都是程序中控制流程无法到达的语句，从而也是不会被执行到的语句，我们可把它们从程序中删除,23,一.基本块及流图,入,口,语,句,4.,划分基本块示例,read X,read Y,R:=X mod Y,if R=0 goto(8),X:=Y,Y:=R,goto(3),write Y,halt,程序的第一条语句,条件转移语句转到的语句,在条件转移语句后的语句,无条件转移语句转到的语句,基 本 块,24,二.基本块内的优化方法,如：对于,T,1,:=2,.,T,2,:=4*T,1,此时可把,T,2,:=,4*T,1,变换为,T,2,:=,8,若两个运算对象都是,编译时的已知量,。可以,在编译时计算出它的值,，而不必等到程序运行时再计算。我们称这种变换为,合并已知量,。,1.,合并已知量,25,二.基本块内的优化方法,如：假定在一个基本块里有语句：,T,:=b+c,其中，,T,是一个临时变量名。如果把这个语句改成：,S,:=b+c,其中，,S,是一个新的临时变量名，并且把本基本块中出现的所有,T,都改成,S,，则不改变基本块的值。,总可以把一个基本块变换成等价的另一个基本块，使其中定义临时变量的语句改成定义新的临时变量。我们称这种变换为,临时变量改名,。,2.,临时变量改名,26,二.基本块内的优化方法,如：假定在一个基本块里有下列两个相邻的语句：,T,1,:=,b+c,T,2,:=,x+y,如果,x,，,y,均不为,T,，,b,，,c,均不为,T,2,，则交换这两个语句的位置不影响基本块的值。,如果交换两个语句的位置而,不影响基本块的值,，则可以进行这种交换。我们称这种变换为,交换语句的位置,。,3.,交换语句的位置,27,二.基本块内的优化方法,如：语句,x:=,y*2,中的乘方运算，通常需要调用一个函数来实现。可以用代数上等价的形式，用简单的运算,x:=,y*y,替换。,对基本块中求值的表达式，用代数上等价的形式替换，以期使复杂运算变成简单运算。我们称这种变换为,代数变换,。,4.,代数变换,28,三.流图,每个流图以基本块为,结点,。,如果一个结点的基本块的人口语句是程序的第一条语句，则称此结点为,首结点,。,通过构造一个有向图，称之为,流图,，我们可以,将控制流的信息增加到基本块的集合上,来表示一个程序。,1.,概念,29,三.流图,2.,构造流图示例,(1)read X,(2)read Y,B1,(3)R:=X mod Y,(4)if R=0 goto(8),B2,(5)X:=Y,(6)Y:=R,(7)goto(3),B3,(8)write Y,(9)halt,B4,30,四.基本块的DAG表示及其应用,DAG(Directed Acyclic Graph),无环路有向图,一个基本块的,DAG,是一种其结点带有下述标记或附加信息的,DAG,1.,概念,1.,叶结点,值,3.,多标记共享,2.,其他结点,运算,图的叶结点以一,标识符,(,变量名,),或,常数,作为标记，表示该结点代表该变量或常数的,值,。,如果叶结点用来代表某,变量,A,的地址,，则用,addr(A),作为该结点的标记,内部结点,以一,运算符,作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行,运算的结果,图中各个结点上可能附加,一个或多个,标识符，表示,这些变量,具有该结点所代表的值,31,四.基本块的DAG表示及其应用,2.,构造基本块的,DAG,的算法,1,.,叶结点生成 代码类型判断,3,.,查找、处理公共子表达式,单目运算（,3,（,1,）双目运算（,3,（,2,）,2,.,常数参数与非常数参数的判断,（,2,（,1,）单目、,2,（,2,）双目）,合并已知量,（,2,（,3,）单目、,2,（,4,）双目）,4.,赋值号处理,32,四.基本块的DAG表示及其应用,3.,构造基本块的,DAG,的算法流程,初,始,化,生,成,B,0,1,生成,C,B,是常数,2,B,不是常数,寻找公共,子表达式,B,、,C,都是常数,B,或者,C,不是常数,合并已知量,生成新常数,P,处理赋值号,处理,A,合并已知量,生成新常数,P,寻找公共,子表达式,33,n1,3.14,T,0,T,0,:=3.14,T,1,:=2*T,0,T,2,:=R+r,A:=T,1,*T,2,B:=A,T,3,:=2*T,0,T,4,:=R+r,T,5,:=T,3,*T,4,T,6,:=R,r,B:=T,5,*T,6,文法,G,NODE(3.14),无定义，构造一个标记为,3.14,的结点,当前代码为,0,型，记,NODE(3.14),的值为,n1,转,4,T,0,:=3.14,NODE(T,0,),无定义，将,T,0,附加在结点,n1,上,令,NODE(T,0,)=n1,，转处理下一条代码,T,1,:=2*T,0,NODE(2),无定义，构造一个标记为,2,的结点,当前代码为,2,型，,NODE(T,0,),已定义，转,2,（,2,）,NODE(2),和,NODE(T,0,),均,已定义，转,2,（,4,）,执行,2*T,0,，新得到常数,6.28,NODE(2),是处理当前代码时新构造出来的，删除之，,NODE(6.28),无定义，,构造一个标记为,6.28,的结点,n2,，置,NODE(6.28)=n2,，转,4,NODE(T,1,),无定义，将,T,1,附加在结点,n2,上,令,NODE(T,1,)=n2,，转处理下一条代码,n2,2,T,1,n2,6.28,T,2,:=R+r,NODE(R),无定义，构造一个标记为,R,的结点,n3,，,令,NODE(R)=n3,当前代码为,2,型，,NODE(r),无定义，,构造一个标记为,r,的结点,n4,，,令,NODE(r)=n4,，转,2,（,2,）,n3,R,n4,r,NODE(R),不是标记为常数的结点，转,3,（,2,）,DAG,中无结点其左后继为,NODE(R),，故构造一个结点,n5,，,其左后继为,NODE(R),，右后继为,NODE(r),，转,4,n5,+,NODE(T,2,),无定义，将,T,2,附加在结点,n5,上，,令,NODE(T2)=n5,，转处理下一条代码,T,2,A:=T,1,*T,2,NODE(T,1,),已定义，当前代码为,2,型，,NODE(T,2,),已定义，转,2,（,2,）,NODE(T,1,),不是标记为常数的结点，,转,3,（,2,）,DAG,中无结点其左后继为,NODE(T,1,),，故构造结点,n6,，,其左后继为,NODE(T,1,),，,右后继为,NODE(T,2,),，转,4,n6,*,NODE(A),无定义，将,A,附加到结点,n6,上，,令,NODE(A)=n6,，转处理下一条代码,A,B:=A,NODE(A),已定义，当前代码为,0,型，转,4,NODE(B),无定义，将,B,附加到结点,n6,上，,令,NODE(B)=n6,，转处理下一条代码,T,3,:=2*T,0,NODE(2),无定义，构造一个标记为,2,的结点,n7,，,令,NODE(2)=n7,n7,2,当前代码为,2,型，,NODE(T,0,),已定义，转,2,（,2,）,NODE(2),和,NODE(T,0,),都为标记为常数的结点，转,2,（,4,）,执行,2*T,0,，得到,6.28,，,NODE(2),是处理当前代码时构造出来的，删除之；,NODE(6.28),已有定义,n2,，转,4,NODE(T,3,),无定义，将,T3,附加到,NODE(6.28),上，,即附加到,n2,上，转处理下一条代码,T,1,T,3,A,B,T,4,:=R+r,NODE(R),已定义，当前代码为,2,型，,NODE(r,),已定义，转,2,（,2,）,NODE(R),不是标记为常数的叶结点，转,3,（,2,）,DAG,中结点,n5,其左后继为,NODE(R),，右后继为,NODE(r,),且其标记为,+,，故将,n5,作为当前结点，转,4,NODE(T,4,),无定义，将,T,4,附加到结点,n5,上，,令,NODE(T,4,)=n5,，转处理下一条代码,T,2,T,4,T,5,:=T,3,*T,4,NODE(T,3,),已定义，当前代码为,2,型，,NODE(T,4,),已定义，转,2,（,2,）,NODE(T,4,),不是标记为常数的叶结点，转,3,（,2,）,DAG,中结点,n6,其左后继为,NODE(T,3,),，右后继为,NODE(T,4,),，,且标记为*，故将,n6,作为当前结点，转,4,NODE(T,5,),无定义，故将,T,5,附加到结点,n6,上，,转处理下一条代码,A,B,T,5,T,6,:=R,r,NODE(R),已定义，当前代码为,2,型，,NODE(r,),已定义，转,2,（,2,）,NODE(R),不是标记为常数的叶结点，转,3,（,2,）,DAG,中无结点其左后继为,NODE(R),，右后继为,NODE(r,),，,且标记为,-,；故构造结点,n7,，使,其左后继为,NODE(R),，,右后继为,NODE(r,),，且标记为,-,，转,4,n7,-,NODE(T,6,),无定义，将,T,6,附加到结点,n7,上，,转处理下一条代码,T,6,B:=T,5,*T,6,NODE(T,5,),已定义，当前代码为,2,型，,NODE(T,6,),已定义，,转,2,（,2,）,NODE(T,5,),不是标记为常数的叶结点，,转,3,（,2,）,DAG,中无结点其左后继为,NODE(T,5,),，,故构造结点,n8,，使其左后继为,NODE(T,5,),，,右后继为,NODE(T,6,),，且标记为*,，转,4,n8,*,NODE(B),已定义，故将,B,从,NODE(B),结点（当前为,n6,）,中的附加标识符集中删除,A,T,5,B,将,B,附加到,n8,上，令,NODE(B)=n8,，转处理下一条代码,所有代码处理完毕，构造过程结束,文法,G,的最终,DAG,如上图所示,四.基本块的DAG表示及其应用,4.,构造,DAG,示例,34,四.基本块的DAG表示及其应用,5.,由,DAG,重写代码顺序,重写中间代码的顺序应遵循,(2),转移语句,(,如果有的话,),仍然是基本,块的最后一个语句,(,保证基本块的正确性,),(1),其中任一内部结点在其后继结点之,后被重写,(,保证计算的正确性,),目的：,生成有效目标代码,35,n1,3.14,T,0,B:=A*T,6,n2,6.28,n3,R,n4,r,n5,+,n6,*,T,1,T,3,T,2,T,4,n7,-,T,6,n8,*,A,T,5,B,T,0,:=3.14,T,1,:=6.28,T,3,:=6.28,T,2,:=R+r,T,4,:=T,2,A:=6.28*T,2,T,5,:=A,T,6,:=R,r,T,0,T,1,T,3,T,2,T,4,A,T,5,T,6,B,文法,G,n1,结点标记为常数，,故产生,T,0,:=3.14,n2,结点标记为常数，,故产生,T,1,:=6,.28,四.基本块的DAG表示及其应用,6.,由,DAG,重写,代码示例,n2,结点标记为常数，,故产生,T,3,:=6.28,T,4,与,T,2,同标记在一个结点，,故产生,T,4,:=T,2,T,5,与,A,同标记在一个结点，,故产生,T,5,:=A,n2,结点标记为常数，,故产生,A:=6.28*T,2,重写过程结束,，,文法,G,如上所示,36,B:=A*T,6,T,0,:=3.14,T,1,:=6.28,T,3,:=6.28,T,2,:=R+r,T,4,:=T,2,A:=6.28*T,2,T,5,:=A,T,6,:=R,r,T,0,:=3.14,T,1,:=2*T,0,B:=T,5,*T,6,T,2,:=R+r,A:=T,1,*T,2,B:=A,T,3,:=2*T,0,T,4,:=R+r,T,5,:=T,3,*T,4,T,6,:=R,r,T,0,为常数，故此时作合并已知量优化,T,0,为常数，故此时作合并已知量优化,R+r,为公共子表达式，并且,T,2,已计算，,故此时不必重复计算,T,1,是常量，此处可用常量代替,文法,G,中,B:=A,是无用赋值，故文法,G,中将此代码删除,T,3,:=6.28,，,T,4,:=T,2,，故此时,T,3,*T,4,=6.28*T,2,，,而,6.28*T,2,为公共子表达式，且,A,已计算过，,故此时不必重复计算,此时可用,A,代替,T,5,文法,G,文法,G,文法,G,中为何缺一句代码？,四.基本块的DAG表示及其应用,7.,文法优化效果比较,37,五.应用DAG时的相关问题,1.,数组元素引用问题,原因：,当对一个数组元素赋值时，可能改变表达式,ai,的,右值,，即使,a,和,i,都没有改变。,优化前,x:=ai,aj:=y,z:=ai,此时,Z=y,优化后,x:=ai,z:=x,aj:=y,此时,Z=ai,引例：在,i=j,并且,y!=ai,时，,38,五.应用DAG时的相关问题,2.,数组元素引用问题解决方法,当我们对数组,a,的一个元素赋值时我们“,注销,”所有,标记为,左边的变元是,a,加上或减去一个常数,(,也可能是,0),的结点。,即，我们认为对这样的结点再添加附加标识符是非法的，从而,取消了它作为公共子表达式的资格,。,39,五.应用DAG时的相关问题,3.,指针赋值问题,优化前,x:=*p,*q:=y,z:=*p,此时,Z=y,优化后,x:=*p,z:=x,*q:=y,此时,Z=*p,对指针赋值，会产生与数组元素引用同样的问题。引例：在,p=q,并且,y!=*p,时,40,五.应用DAG时的相关问题,4.,指针赋值问题解决方法,如果我们不知道,p,可能指向哪一个变量，那么，就要认为它,可能改变基本块中任一变量的值,。,当构造这种赋值句的结点时，要把,DAG,各结点上,所有标识符,(,包括作为叶结点上标记的标识符,),都予以注销,。,把,DAG,中所有结点上的标识符都注销，也同时意味着,DAG,中所有结点也都被注销。,41,五.应用DAG时的相关问题,5.,过程调用问题及其解决方法,与上面两个问题类似，因为对被调用过程的情况缺乏了解，我们,必须假定,：,任何变量都可能因产生副作用而发生变化,。,解决方法：,与上面类似，在一个基本块中的一个过程调用将,注销所有的结点,42,五.应用DAG时的相关问题,6.,对基本块重写时的总原则,1.,任何数组,a,的引用,不可以互相调换次序,2.,任何语句,不得跨越,一个过程调用语句或通过指针的间接赋值,43,五.应用DAG时的相关问题,7.,重写中间代码时的顺序,1.,对数组,a,任何元素的引用或赋值，都必须跟在原来位于其前面的对数组,a,任何元素的赋值之后。,2.,对数组,a,任何元素的赋值，都必须跟在原来位于其前面的对数组,a,任何元素的引用之后。,3.,对任何标识符的引用或赋值，必须跟在原来位于其前面任何过程调用或通过指针的间接赋值之后。,4.,任何过程调用或通过指针的间接赋值，必须跟在原来位于其前面的任何标识符的引用或赋值之后。,44,10.3 循环优化,本节内容,一,.,循环优化概述,二,.,代码外提,三,.,强度削弱,四,.,删除归纳变量,45,一.循环优化概述,循环中存储,空间变化一般不大,因为循环中代码可能要反复执行，所以，进行代码优化时应,着重考虑循环的代码优化,，这对提高目标代码的效率将起更大的作用。（尤其要,注意优化内层循环,）,循环,就是程序中那些可能,反复执行的代码序列,。,1.,概念,46,一.循环优化概述,2.,定值、引用、活跃、定值到达,如果一条三地址语句为,x:=y+z,，则称对,x,定值,并,引用,y,和,z,示例：分析变量,R,定值,引用,所谓在程序中的,某个给定点,是,活跃,的，是指如果在程序中,(,包括在本基本块或在其它基本块中,),它的值在该点以后被引用,。,活跃,所谓变量,A,在某点,d,的,定值到达,另一点,u(,或称变量,A,的,定值点,d,到达另一点,u,),，是指流图中,从,d,有一通路到达,u,（,可以到达,）,该通路上没有,A,的其它定值（,定值到达,）,d,u,R,R,R,R,R,R,47,二.代码外提,外提到哪里？,循环中的某些代码，其运算的结果往往是不变的。对于这种不变运算，我们可以把它外提到循环外。这样，,程序的运行结果仍保持不变,，但,程序的运行速度却提高了,。我们称这种优化为,代码外提,。,1.,概念,循环前置结点,48,二.代码外提,2.,循环的前置结点,前置结点的构造：,1,新结点,在,循环人口结点前面,建立一个新结点,(,基 本块,),，称为,循环的前置结点,入口结点,循环,L,前置结点,2,输出,循环前置结点以循环人口结点为其,唯一后继,3,输入,原来流图中从循环外引到循环人口结点的,有向边,，,改,成,引,到循环前置结点,49,二.代码外提,3.,引例 一,左图,B3,中,I:=2,是循环不变运算，能否将其外提（如右图所示）呢？,？,当,X=30 Y=25,时,I=1,I=2,代码外提后程序结果发生改变，故此时不能外提,所谓,出口结点,，是指循环中从该结点有一有向边引到循环外的某结点。此处即为,B4,错误原因分析：,B3,不是此循环的必经结点（左图），而将,I:=2,外提后，将其从非必经结点放入了必经结点（右图），故程序结果有所不同,解决方法：当把一不变运算外提到循环前置结点时，要求该不变运算,所在的结点是循环所有出口结点的必经结点,。,50,二.代码外提,4.,引例 二,右图,B4,中,I:=2,能否外提？,I:=1,B1,if XY,goto,B3,B2,A:=I+1,X:=X+1,B3,I:=2,Y:=Y-1,if Y=0,goto,B5,B4,J:=A,B5,I:=2,当,X=0 Y=2,时，执行顺序为,B2B3B4B2B4B5,原始结果,J=2,外提后结果,J=3,I:=1,B1,if XY,goto,B3,B2,A:=I+1,X:=X+1,B3,Y:=Y-1,if Y10,goto,(15),B2,(15).,B3,(3)T,1,:=2*J,(4)T,2,:=10*I,(5)T,3,:=T,2,+T,1,(6)T,4,:=addr(A)-11,(7)T,5,:=2*J,(8)T,6,:=10*I,(9)T,7,:=T,6,+T,5,(10)T,8,:=ddr(A)-11,(11)T,9,:=T,8,T,7,(12)T,4,T,3,:=T,9,+1,(13)I:=I+1,(14)goto B2,(3)T,1,:=2*J,(6)T,4,:=addr(A)-11,(7)T,5,:=2*J,(10)T,8,:=ddr(A)-11,查找不变运算,J,的定值点在循环外边,addr(A,),的定值点在循环外边,代码外提,B2,(2)if I10,goto,(15),B2,(15).,B3,(4)T,2,:=10*I,(5)T,3,:=T,2,+T,1,(8)T,6,:=10*I,(9)T,7,:=T,6,+T,5,(11)T,9,:=T,8,T,7,(12)T,4,T,3,:=T,9,+1,(13)I:=I+1,(14)goto B2,(3)T,1,:=2*J,(6)T,4,:=addr(A)-11,(7)T,5,:=2*J,(10)T,8,:=ddr(A)-11,B2,54,三.强度削弱,强度削弱可以,强度削弱,是指把程序中执行时间较长的运算替换为执行时间较短的运算。,（,即将复杂（高阶）运算用,“,递归,+,低阶运算,”,代替,）,1.,概念,对乘法运算,使用变址器,对加法运算,55,三.强度削弱,2.,强度削弱示例,-,对乘法运算,(2)if I10,goto,(15),B2,(15).,(3)T,1,:=2*J,(6)T,4,:=addr(A)-11,(7)T,5,:=2*J,(10)T,8,:=ddr(A)-11,B2,B3,中,I,是递归赋值变量，每循环一次其值增加,1,B3,中,T,2,是,I,的线性函数，每循环一次其值增加,10,故可将,(4),提到,B2,中，并在,(13),后增加代码给,T,2,加常量,10,，如此程序运行结果保持不变,(3)T,1,:=2*J,(6)T,4,:=addr(A)-11,(7)T,5,:=2*J,(10)T,8,:=ddr(A)-11,B2,(4)T,2,:=10*I,B3,(5)T,3,:=T,2,+T,1,(8)T,6,:=10*I,(9)T,7,:=T,6,+T,5,(11)T,9,:=T,8,T,7,(12)T,4,T,3,:=T,9,+1,(13)I:=I+1,(14)goto B2,B3,(4)T,2,:=10*I,(5)T,3,:=T,2,+T,1,(8)T,6,:=10*I,(9)T,7,:=T,6,+T,5,(11)T,9,:=T,8,T,7,(12)T,4,T,3,:=T,9,+1,(13)I:=I+1,(14)goto B2,B3,(4)T,2,:=T,2,+10,(5)T,3,:=T,2,+T,1,(8)T,6,:=10*I,(9)T,7,:=T,6,+T,5,(11)T,9,:=T,8,T,7,(12)T,4,T,3,:=T,9,+1,(13)I:=I+1,(14)goto B2,同理，可将,(8),提到,B2,中，并在,(4,),后增加代码给,T,6,加常量,10,，如此程序运行结果保持不变,(5)T,3,:=T,2,+T,1,B3,(4)T,2,:=T,2,+10,(9)T,7,:=T,6,+T,5,(11)T,9,:=T,8,T,7,(12)T,4,T,3,:=T,9,+1,(13)I:=I+1,(14)goto B2,(3)T,1,:=2*J,(6)T,4,:=addr(A)-11,(7)T,5,:=2*J,(10)T,8,:=ddr(A)-11,B2,(4)T,2,:=10*I,(8)T,6,:=10*I,B3,(4)T,2,:=T,2,+10,(9)T,7,:=T,6,+T,5,(11)T,9,:=T,8,T,7,(12)T,4,T,3,:=T,9,+1,(13)I:=I+1,(14)goto B2,(5)T,3,:=T,2,+T,1,(8)T,6,:=T,6,+10,(4)T,2,:=10*I,(4)T,2,:=T,2,+10,(8)T,6,:=10*I,(8)T,6,:=10*I,如此即对原,程序,中的乘法运算,(4),、,(8),进行了强度削弱,(8)T,6,:=T,6,+10,(13)I:=I+1,(4)T,2,:=10*I,(4)T,2,:=10*I,56,三.强度削弱,(2)if I10,goto,(15),B2,(15).,(3)T,1,:=2*J,(6)T,4,:=addr(A)-11,(7)T,5,:=2*J,(10)T,8,:=ddr(A)-11,B2,(4)T,2,:=10*I,(8)T,6,:=10*I,B3,(4)T,2,:=T,2,+10,(9)T,7,:=T,6,+T,5,(11)T,9,:=T,8,T,7,(12)T,4,T,3,:=T,9,+1,(13)I:=I+1,(14)goto B2,(5)T,3,:=T,2,+T,1,(8)T,6,:=T,6,+10,3.,强度削弱示例,-,对加法运算,由,B3,中,(4),可以看出，,T,2,是递归赋值变量，每循环一次其值增加,10,B3,中,T,1,是循环不变量，故,T,3,是,T,2,的线性函数，每循环一次其值增加,10,故可将,(5),提到,B2,中，并在,(8,),后增加代码给,T,3,加常量,10,，如此程序运行结果保持不变,B3,(4)T,2,:=T,2,+10,(9)T,7,:=T,6,+T,5,(11)T,9,:=T,8,T,7,(12)T,4,T,3,:=T,9,+1,(13)I:=I+1,(14)goto B2,(8)T,6,:=T,6,+10,(3)T,1,:=2*J,(6)T,4,:=addr(A)-11,(7)T,5,:=2*J,(10)T,8,:=ddr(A)-11,B2,(4)T,2,:=10*I,(8)T,6,:=10*I,(5)T,3,:=T,2,+T,1,B3,(4)T,2,:=T,2,+10,(9)T,7,:=T,6,+T,5,(11)T,9,:=T,8,T,7,(12)T,4,T,3,:=T,9,+1,(13)I:=I+1,(14)goto B2,(5)T,3,:=T,3,+10,(8)T,6,:=T,6,+10,同理，可将,(9),提到,B2,中，并在,(5,),后增加代码给,T,7,加常量,10,，如此程序运行结果保持不变,B3,(4)T,2,:=T,2,+10,(11)T,9,:=T,8,T,7,(12)T,4,T,3,:=T,9,+1,(13)I:=I+1,(14)goto B2,(5)T,3,:=T,3,+10,(8)T,6,:=T,6,+10,(9)T,7,:=T,6,+T,5,(3)T,1,:=2*J,(6)T,4,:=addr(A)-11,(7)T,5,:=2*J,(10)T,8,:=ddr(A)-11,B2,(4)T,2,:=10*I,(8)T,6,:=10*I,(5)T,3,:=T,2,+T,1,B3,(4)T,2,:=T,2,+10,(11)T,9,:=T,8,T,7,(12)T,4,T,3,:=T,9,+1,(13)I:=I+1,(14)goto B2,(5)T,3,:=T,3,+10,(8)T,6,:=T,6,+10,(9)T,7,:=T,7,+10,如此即对原,程序,中的加法运算,(5),、,(9),进行了强度削弱,(5)T,3,:=T,2,+T,1,(5)T,3,:=T,2,+T,1,(4)T,2,:=T,2,+10,(3)T,1,:=2*J,(5)T,3,:=T,2,+T,1,(5)T,3,:=T,3,+10,(9)T,7,:=T,6,+T,5,(9)T,7,:=T,6,+T,5,(7)T,5,:=2*J,(9)T,7,:=T,6,+T,5,(9)T,7,:=T,7,+10,57,三.强度削弱,4.,强度削弱示例,-,使用变址器,我们还可以,可利用变址器提高运算速度,，从而使运算的强度得到削。（,是否会优化依赖于具体硬件,）,mov ax,7,loopstart:,add ax,3,cmp ax,22,jne loopstart,mov bp,7,loopstart:,lea bp,bp+3,cmp bp,22,jne loopstart,优化前,优化后,58,四.删除归纳变量,基本归纳变量的作用：,如果循环中对变量,I,只有唯一的,形如,I,：,=I,C,的赋值，且其中,C,为循环不变量,，则称,I,为循环中的,基本归纳变量,。,1.,基本归纳变量,用于其,自身,的递归定值,在循环中用来计算,其它,归纳变量,用来,控制,循环的进行,59,四.删除归纳变量,归纳变量的确定,找与基本归纳变量存在的线性关系,如果,I,是循环中一基本归纳变量，,J,在循环中的定值,总是,可化归为,I,的,同一线性函数,，也即,J=C,1,*I,C,2,，其中,C,1,和,C,2,都是循环不变量，则称,J,是,归纳变量,，,并称它与,I,同族,。,2.,归纳变量,60,(15).,(2)if I10,goto,(15),B2,(9)T,7,:=T,6,+T,5,(3)T,1,:=2*J,(6)T,4,:=addr(A)-11,(7)T,5,:=2*J,(10)T,8,:=ddr(A)-11,B2,(4)T,2,:=10*I,(8)T,6