编译原理第11章 代码优化

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,编译原理,之,代码优化,华东交通大学软件学院,万仲保,第,11,章 代码优化,优化技术简介,局部优化,控制流分析和循环优化,数据流的分析与全局优化,优化技术简介,优化概念,优化分类,优化技术,优化概念,优化实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。,优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也有所不同，在同一范围内，可进行多种优化。,一般，优化工作阶段可在中间代码生成之后和,(,或,),目标代码生成之后进行。,优化分类,按,阶段分类,与机器无关的优化,依赖于机器的优化,根据优化所涉及的程序范围分类,局部优化：是在只有一个入口、一个出口的基本程序块上进行的优化。,循环优化：是对循环中的代码进行的优化。,全局优化：是在整个程序范围内进行的优化。,优化技术,删除多余运算,(,删除公共子表达式）,代码外提,强度削弱,变换循环控制条件,合并已知量与复写传播,删除无用赋值,删除多余运算,目的：在于使目标代码执行速度较快。,示例：,程序代码,中间代码段,删除多余运算的,程序代码,P:=0,for I:=1 to 20 do,P:=P+AI*BI,删除多余运算优化的,中间代码,(3)T,1,:=4*I,(4)T,2,:=addr(A)-4,(5)T,3,:=T,2,T,1,(6)T,4,:=4*I,(7)T,5,:=addr(B)-4,(8)T,6,:=T,5,T,4,(9)T,7,:=T,3,*T,6,(10)P:=P+T,7,(11)I:=I+1,(12)if I=20 goto(3),(1)P:=0,(2)I:=1,B1,B2,(3)T,1,:=4*I,(4)T,2,:=addr(A)-4,(5)T,3,:=T,2,T,1,(6)T,4,:= T,1,(7)T,5,:=addr(B)-4,(8)T,6,:=T,5,T4,(9)T,7,:=T,3,*T,6,(10)P:=P+T,7,(11)I:=I+1,(12)if I=20 goto(3),(1)P:=0,(2)I:=1,B1,B2,代码外提,把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面。使之只在循环外计算一次。,示例,代码外提,示例,(3)T,1,:=4*I,(4)T,2,:=addr(A)-4,(5)T,3,:=T,2,T,1,(6)T,4,:=T,1,(7)T,5,:=addr(B)-4,(8)T,6,:=T,5,T,4,(9)T,7,:=T,3,*T,6,(10)P:=P+T,7,(11)I:=I+1,(12)if I=20 goto(3),(1)P:=0,(2)I:=1,B1,B2,(3)T,1,:=4*I,(5)T,3,:=T,2,T,1,(6)T,4,:= T,1,(8)T,6,:=T,5,T,4,(9)T,7,:=T,3,*T,6,(10)P:=P+T,7,(11)I:=I+1,(12)if I=20 goto(3),(1)P:=0,(2)I:=1,(4)T,2,:=addr(A)-4,(7)T,5,:=addr(B)-4,B1,B2,强度削弱,强度削弱的思想是把强度大的运算换算成强度小的运算。,示例,强度削弱,示例,(5)T,3,:=T,2,T,1,(6)T,4,:= T,1,(8)T,6,:=T,5,T,4,(9)T,7,:=T,3,*T,6,(10)P:=P+T,7,(11)I:=I+1,(3)T,1,:= T,1,+4,(12)if I=20 goto(3),(1)P:=0,(2)I:=1,(4)T,2,:=addr(A)-4,(7)T,5,:=addr(B)-4,(3)T,1,:=4*I,B1,B2,(3)T,1,:=4*I,(5)T,3,:=T,2,T,1,(6)T,4,:= T,1,(8)T,6,:=T,5,T,4,(9)T,7,:=T,3,*T,6,(10)P:=P+T,7,(11)I:=I+1,(12)if I=20 goto(3),(1)P:=0,(2)I:=1,(4)T,2,:=addr(A)-4,(7)T,5,:=addr(B)-4,B1,B2,变换循环控制条件,变换循环控制条件，确保整个程序的运行结果不变。,示例,变换循环控制条件,示例,(5)T,3,:=T,2,T,1,(6)T,4,:= T,1,(8)T,6,:=T,5,T,4,(9)T,7,:=T,3,*T,6,(10)P:=P+T,7,(11)I:=I+1,(3)T,1,:= T,1,+4,(12)if,T,1,=80,goto(3),(1)P:=0,(2)I:=1,(4)T,2,:=addr(A)-4,(7)T,5,:=addr(B)-4,(3)T,1,:=4*I,B1,B2,(5)T,3,:=T,2,T,1,(6)T,4,:= T,1,(8)T,6,:=T,5,T,4,(9)T,7,:=T,3,*T,6,(10)P:=P+T,7,(11)I:=I+1,(3)T,1,:= T,1,+4,(12)if,I=20,goto(3),(1)P:=0,(2)I:=1,(4)T,2,:=addr(A)-4,(7)T,5,:=addr(B)-4,(3)T,1,:=4*I,B1,B2,合并已知量与复写传播,运算对象都是编码时的已知量，可在编译时计算出它的值。,复写传播变换的做法是：在复写语句,f:=g,后尽可能用,g,代表,f,。,示例,合并已知量与复写传播,示例,(5)T,3,:=T,2,T,1,(6)T,4,:= T,1,(8)T,6,:=T,5,T,1,(9)T,7,:=T,3,*T,6,(10)P:=P+T,7,(11)I:=I+1,(3)T,1,:= T,1,+4,(12)if T,1,=80 goto(3),(1)P:=0,(2)I:=1,(4)T,2,:=addr(A)-4,(7)T,5,:=addr(B)-4,(3)T1:=4,B1,B2,(5)T,3,:=T,2,T,1,(6)T,4,:= T,1,(8)T,6,:=T,5,T,4,(9)T,7,:=T,3,*T,6,(10)P:=P+T,7,(11)I:=I+1,(3)T,1,:= T,1,+4,(12)if T,1,=80 goto(3),(1)P:=0,(2)I:=1,(4)T,2,:=addr(A)-4,(7)T,5,:=addr(B)-4,(3)T,1,:=4*I,B1,B2,删除无用赋值,只要程序中其它地方不需要引用的赋值语句，删除后对程序的运行结果无任何作用。,示例,删除无用赋值,示例,(5)T3:=T2T1,(6)T4:= T1,(8)T6:=T5T4,(9)T,7,:=T,3,*T,6,(10)P:=P+T,7,(3)T1:= T1+4,(12)if T1 =80 goto(3),(1)P:=0,(2)I:=1,(4)T2:=addr(A)-4,(7)T5:=addr(B)-4,(3)T1:=4,B1,B2,(5)T3:=T2T1,(6)T4:= T1,(8)T6:=T5T4,(9)T,7,:=T,3,*T,6,(10)P:=P+T,7,(11)I:=I+1,(3)T1:= T1+4,(12)if T1 =80 goto(3),(1)P:=0,(2)I:=1,(4)T2:=addr(A)-4,(7)T5:=addr(B)-4,(3)T1:=4,B1,B2,局部优化,基本块的概念,基本块的划分,基本块的变换,基本块的,DAG,表示,DAG,构造算法,DAG,的应用,基本块的概念,基本块，是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。执行时只能从其入口语句进入，从其出口语句退出。,入口语句，严格地说来就是：,1,程序的第一个语句；,2,条件转移语句或无条件转移语句的转移目标语句；,3,紧跟在条件转移语句后面的语句。,基本块的划分,划分中间代码,(,四元式程序,),为基本块的算法，其步骤如下：,1,求出四元式程序中各个基本块的入口语句。,2,对每一入口语句，构造其所属的基本块。它是由该入口语句到下一入口语句,(,不包括下一入口语句,),，或到一转移语句,(,包括该转移语句,),，或到一停语句,(,包括该停语句,),之间的语句序列组成的。,3,凡末被纳入某一基本块的语句、都是程序中控制流程无法到达的语句,，,因而也是不会被执行到的语句，我们可以把它们删除。,示例,基本块划分的示例,(1)P:=0,(2)I:=1,(3)T,1,:=4*I,(4)T,2,:=addr(A)-4,(5)T,3,:=T,2,T,1,(6)T,4,:=4*I,(7)T,5,:=addr(B)-4,(8)T,6,:=T,5,T,4,(9)T,7,:=T,3,*T,6,(10)P:=P+T,7,(11)I:=I+1,(12)if I=20 goto(3),入口语句,入口语句,(3)T,1,:=4*I,(4)T,2,:=addr(A)-4,(5)T,3,:=T,2,T,1,(6)T,4,:=4*I,(7)T,5,:=addr(B)-4,(8)T,6,:=T,5,T,4,(9)T,7,:=T,3,*T,6,(10)P:=P+T,7,(11)I:=I+1,(12)if I=20 goto(3),(1)P:=0,(2)I:=1,B1,B2,基本块的变换,基本块的主要保结构变换是：,1,删除公共子表达式,2,删除无用代码,3,重新命名临时变量,4,交换语句次序,示例,基本块变换的示例,重新命名,:,语句,t := b+c,，,其中,t,是临时变量。如果把这个语句改为,u := b+c,，,其中,u,是新的临时变量，并且把这个,t,的所有引用改成,u,，,那么基本块的运算结果不变,交换语句次序,:,t1:=b+c t2:=x+y,如果基本块有两个相邻的语句，当且仅当,x,和,y,都不是,tl,，,b,和,c,都不是,t2,时，可以交换这两个语句的次序,。,代数变换：可以把基本块计算的表达式集合变换成代数等价的集合。,简化表达式或用较快运算代替较设运算的变换。,例如：,x := X+0,或,x := x*1,这样的语句可以从基本块中删除而不改变它计算的表达式集合，又如,x := y *2,的指数算符通常要用函数调用来实现，使用代数变换，这个语句可由快速、等价的语句,x := y*y,来代替。,基本块的,DAG,表示,概念,DAG,的要素,DAG,的表示,DAG,的概念,在一个有向图中，称任一有向边,m,n(,或表示为有序对,(m,，,n),中的结点,m,为结点,n,的前驱,(,分结,),，结点,n,为结点,m,的后继,(,子结,),。,环路：,任一有向边序列,n,1,n,2,，,n,2,n,3,，,，,n,k-1,n,k,为从结点,n,1,到结点,n,k,的一条通路。如果其中,n,1,=,n,k,，,则称该通路为环路。该结点序列记为,(n,1,，,n,2,，,，,n,k,),。,如果有向图中任一通路都不是环路，则称该有向图为无环路有向图，简称,DAG,。,DAG,的要素,图的叶结点：,即无后继的结点，以一标识符,(,变量名,),或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来代表某变量,A,的地址，则用,addr(A,),作为该结点的标记。通常把叶结点上作为标记的标识符加上下标,0,，,以表示它是该变量的初值。,图的内部结点：,即有后继的结点以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。,图中各个结点上可能附加一个或多个标识符：,表示这些变虽具有该结点所代表的值。,DAG,的表示,一个基本块，可用一个,DAG,来表示。,表示方法,:,n,i,为结点编号，,结点下面的符号,(,运算符、标识符或常数,),是各结点的标记，,各结点右边的标识符是结点的附加标识符。,四元式的,DAG,表示,四元式的,DAG,表示,（,6,）,goto,(s),(j,-,-,(s),（0）A:=B,(:=,B,-,A),（1）A:=op B,(op,B,-,A),（2）A:=B op C,(op,B,C,A),（3）A:=BC,(=,BC,-,A),（,4,）,if B,rop,C,goto,(s),(,jrop,B,C,(s,),（5）DC:= B,(=,B,-,DC),DAG,构造算法（一,）,首先，,DAG,为空。,对基本块的每一四元式，依次执行：,1,、如果,NODE(D),无定义，则构造一标记为,B,的叶结点并定义,NODE(B),为这个结点；,如果当前四元式是,0,型，则记,NODE(B),的值为,n,，,转,4,。,如果当前四元式是,1,型，则转,2 (1),。,如果当前四元式是,2,型，则：,(I),如果,NODE(C),无定义，则构造一标记为,C,的叶结点并定义,NODE(1),为这个结点，,(II),转,2(2),。,DAG,构造算法（二,）,2,、,(1),如果,NODE(B),是标记为常数的叶结点，则转,2(3),，否则转,3(1),。,(2),如果,NODE(B),和,NODE(C),都是标记为常数的叶结点，则转,2(4),，否则转,3(2),。,(3),执行,op B(,即合并已知量,),，令得到的新常数为,P,。,如果,NODE(B),是处理当前四元式时新构造出来的结点，则删除它。如果,NODE(P),无定义，则构造一用,P,做标记的叶结点,n,。置,NODE(P),n,，,转,4,。,(4),执行,B op C(,即合并已知量,),，令得到的新常数为,P,。,如果,NODE(B),或,NODE(C),是处理当前四元式时新构造出来的结点，则删除它。如果,NODE(P),无定义，则构造一用,P,做标记的叶结点,n,。置,NODE(P),n,，,转,4,。,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,。,转处理下一四元式。,DAG,的应用,示例,基本块,G,相应的,DAG,利用,DAG,进行优化,从基本块得到的优化信息,基本块,G,T0:=3.14,T1:=2*T0,T2:=R+r,A:=T1*T2,B:=A,T3:=2*T0,T4:=R+r,T5:=T3*T4,T6:=R-r,B:=T5*T6,相应的,DAG,利用,DAG,进行优化,T0:=3.14,T1:=6.28,T3:=6.28,T2:=R+r,T4:=T2,A:=6.28*T2,T5:=A,T6:=R-r,B:=A*T6,从基本块得到的优化信息,1,在基本块外被定值并在基本块内被引用的所有标识符，就是作为叶子结点上标记的那些标识符。,2,在基本块内被定值且该值能在基本块后被引用约所有标识符，就是,DAG,各结点上的那些附加标识符。,控制流分析和循环优化,概述,程序流图,循环,概述,在一个程序流程中，循环是必不可少的一种控制结构。所谓循环，就是程序中那些可能反复执行的代码序列。因为循环中的代码要反复执行，因而为了提高目标代码的效率必须着重考虑循环的代码优化。,要进行循环优化。首先必须找出程序中的循环，为找出程序中的循环，就需要对程序的控制进程进行分析。,程序流图,相关概念,有向边集的构成,示例,程序,流图,相关概念,一个控制流程图,(,简称为流图,),就是具有唯一首结点的有向图。,首结点就是从它开始到控制流程图中任何结点都有一条通路的结点。,一个控制流程图表示成一个三元组,C,(N,，,E,，,no),，,其中,:,N,代表图中所有结点集，,E,代表图中所有有向边集，取代表首结点。,一个程序可用一个流图来表示。,流图中的有限结点集,N,就是程序的基本块集，,流图中的结点就是程序中的基本块。,流图的首结点就是包含程序第一个语句的基本块。,有向边集的构成,假设流图中结点,i,和结点,j,分别对应于程序的基本块,i,和基本块,j,，,则当下述条件,1,或,2,有一个成立时，从结点,i,有一有向边引向结点,j,1,、,基本块,j,在程序中的位置紧跟在基本块,i,之后，并且基本块的出口语句不是无条件转移语句,goto(s,),或停语句。,2,、基本块,i,的出口语句是,goto(s,),或,if,goto(s,),，,并且,(s),是基本块,j,的入口语句。,程序,例 构造以下程序的流图,(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,它们是强连通的。也即，其中任意两个结点之间，必有一条通路，而且该通路上各结点部居于该结点序列。如果序列只包含一个结点则必有一有向边从该结点引到其自身。,2,它们中间有且只有一个是入口结点。,示例,循环示例,是循环的结点序列,6,4,，,5,，,6,，,7,2,，,3,，,4,，,5,，,6,，,7,不是循环的结点序列,2,，,42,，,4,为入口,2,，,3,，,42,，,4,为入口,4,，,6,，,7 4,，,7,为入口,4,，,5,，,7 4,，,7,为入口,2,6,1,5,7,3,4,程序流图,返回算法的,D(N),返回,D(N),示例,返回回边求循环,返回求扩展树,返回可归约流图,循环,查找,必经结点：,在程序流图中，对任意两个结点,m,和,n,，,如果从流图的首结点出发，到达,n,的任一通路都要经过,m,，,则称,m,是,n,的必经结点，记为,m DOM n,。,必经结点集：,流图中结点,n,的所有必经结点的集合，称为结点,n,的必经结点集，记为,D(n),。,示例,回边：,假设,a,b,是流图中的一条有向边，如果,b DOM a,，,则称,n,b,是流图中的一条回边。,必经结点的性质,查找算法,必经结点的性质,1,自反性：,对流图中任意结点,a,，有,a DOM a,。,2,传递性：,对流图中任意结点,a,、,b,和,c,。若,a DOM b,，,b DOM c,，则有,a DOM c,。,3,反对称性：,若,a DOM b,且,b DOM a,，,则必有,a,b,。,因此，关系,DOM,是一个偏序关系。任何结点,n,的必经结点集是一个有序集。,循环,查找算法,求流图所有结点必经结点集的算法,计算必经结点集结点次序的方法,由回边求循环的结论,由回边求循环算法的基本思想,求流图中由回边组成循环的算法,示例,:,运用算法求,D,（,N,）,的示例,求回边,由回边求循环,求流图所有结点必经结点集的算法,深度为主查找法,简介,相关概念：,前向边,后向边,横向边,深度,深度为主扩展树,深度为主扩展树算法,示例,深度为主查找法简介,如果对于给定的流图，在沿着从首结点开始的通路访问图中各个结点的过程中，始终沿着某通路前进，直到访问不到新结点时，才回退到其前驱。然后由前驱结点沿另一通路前进，直到访问不到新结点时，再回退其前驱。按此步骤，直至退到首结点并且再也访问不到新结点为止，这种查找方法被称为,深度为主查找法,。,如果按深度为主查找中所经过结点序列的逆序，依次给各结点排上一个次序，则称该次序为,深度为主次序,。,前向边,假设,m,n,是流图的一条有向边，如果在流图的,DFST,中,m,是,n,的祖先，则称,m,n,为流图的前向边。,后向边,假设,m,n,是流图的一条有向边，如果在流因的,DFST,中，,n,是,m,的祖先或,n,m,，,则称,m,n,为流图的后向边。,横向边,假设,m,n,是流图的一条有向边，如果在流图的,DFST,中,m,与,n,没有祖先与后代的关系，则称,m,n,为流图的横向边。,深度,对于一个流图和它的某一扩展树，流图中任何无环路通路含有的后向边边数的最大值称为该流图的深度。,深度为主扩展树,把在按深度为主查找中依次访问到的各个新结点用有向边联结成一个图，就成为一棵树，称该树为深度为主扩展树，简称,DFST(Depth First Spanning Tree),。,深度,为主扩展树算法,procedure search(n);,begin,(1),把,n,标记为,“,已访问,”,；,(2) for s,S(n) do / S(n),为,n,的后继集,(3) if s,标记为,“,未访问,”,then,begin,(4),把有向边,n,s,加到,T,中,(5) search(s),end;,(6) DFNn:= i;,i:=i-1,end;,begin,(8) T:=,空；,(9) for n,N do,标记,n,为,“,未访问,”,；,(10),i: =|N|;,(11) search(n,0,),end;,深度为主扩展树示例,对于,流图,，把各结点按深度为主次序进行访问，先沿最左通路访问各结点，所经过的结点序列是：,1 2 4 6,7,6,4,5,4,2,3,2,1,结点下面的底线指出该结点在序列中最后一次出现的位置。按以上序列的逆序，各结点的排出次序为：,1,，,2,，,3,，,4,，,5,，,6,，,7,这个次序就是各结点的深度为主次序，由此可得其深度为主扩展树见右图。,由回边求循环的结论,如果已知有向边,n,d,是回边那么就可以求出由它组成的循环。该循环就是由结点,d,、,结点,n,以及有通路到达,n,而该通路不经过,d,的所有结点组成，并且,d,是该循环的唯一入口结点。,这是因为：,1,令上述结点集为,L,，则,L,必定是强连通的，这一点可由图论知识予以证明。,2,对所有的,n,i,L,，,都有,d DOM,n,i,，,d,必为,L,的一个入口结点，同时也是,n,i,的唯一入口结点。,由回边求循环算法的基本思想,由于要求回边,n,d,组成的循环，这个循环将以,d,为其唯一入口，,n,是它的一个出口。,若,n,不同时是,d,，则,n,的所有前驱结点应属于循环。,当求出,n,的所有前驱后，只要它们不是循环入口,d,，,就应再求出它们的前驱，新求出的所有前驱也应属于循环。,然后再对新求出的所有前驱，重复以上步骤，直到所求出的前驱是,d,为止。此时算法结束。,求流图中由回边组成循环的算法,/*,主程序*,/,stack:=,空；,loop:=d;,insert(n);,while stack,非空,do,begin,把,Stack,的栈顶元素,m,上托出去,for p,P(m) do,insert(p),end,procedure insert(m);,if m,不属于,loop then,begin,loop:=loopm;,把,m,下推进栈,stack;,end,求,D,（,N,）,的示例,结点 必经结点集,D(1)=1,D(2)=1,2,D(3)=1,2,3,D(4)=1,2,4,D(5)=1,2,4,5,D(6)=1,2,4,6,D(7)=1,2,4,7,程序流图,返回算法求,D(N),的示例,运用算法求,D,（,N,）,的示例,(,一,),首先置初值：,D(1),1,D(2),D(3)=,=D(7),1,2,3,4,5,6,7,置,CHANGE,为,FALSE,，,对结点,2,到结点,7,依次执行,(7)(10),对结点,2,：,NEWD,2,D(1),D(4),2,1,1,2,3,4,5,6,7=1,2,因,D(2),NEWD,，,故置,CHANGE,TRUE,，令,D(2),NEWD,1,2,对结点,3:,NEWD,3,D(2),1,2,3,，,因,D(3),NEWD,，令,D(3),NEWD,1,2,3,对结点,4:,NEWD,4,D(2),D(3),D(7),1,2,4,D(4),，令,D(3),1,2,4,程序流图,运用算法求,D,（,N,）,的示例,(,二,),同理得,D(5),5,D(4),1,2,4,5,D(6),6,D(4),1,2,4,6,D(7),7,D(5),D(6),1,2,4,7,至此，一次迭代完毕，由于,CHANGE,TRUE,，,进行下一次迭代。,运用算法求,D,（,N,）,的示例,(,三,),置,CHANGE,为,FALSE,，,对结点,2,到结点,7,依次执行,(7)(10),对结点,2,：,NEWD,2,D(1),D(4),2,1,1,2, 4=1,2,4,此时,D(2),=,NEWD,，故,D(2),不变,对结点,3:,NEWD,3,D(2),1,2,3= D(3),同理可求得所有结点均有,NEWD,D(n) ,故第二次送代结束后,CHANGE,为,FALSE,，,迭代结束，每个结点的,D(n),值就是所求的,结果,。,求,回边的示例,程序流图,因为在所有的有向边中，存在：,6 DOM 6,，,4 DOM 7,，,2 DOM 4,，,所以有向边,6,6,、,7,4,、,4,2,是回边。,由回边求循环示例,求,流图,中回边,7,4,组成的循环,开始，置,loop,4,，,stack,为空。由,insert,把,结点,7,放到栈中，此时,loop,4,7,。,然后,7,退栈，,7,的前驱结点集,P(7),5,6,，,把,5,和,6,先后故入,loop,和,stack,中，这时,loop,4,7,5,6,。,然后,6,退栈，,P(6),6,4,已在,loop,中，故,6,仅退出,stack,而已。,此时栈顶为,P(5),6,4,也在,loop,中，之后,stack,已空，算法结束，所求循环,loop,4,5,6,7,可归约流图,可归约流图：,当且仅当流图中除去回边外，其余的边构成的一个无环路流图。（,示例,）,可归约流图的性质：,1,图中任何直观意义下的环路，都属于循环；,2,只要找出图中所有回边，对回边应用前述循环查找算法，就可找出流图中所有的循环；,3,图中任意两个循环要么嵌套，要么不相交,(,除了可能有公共的入门结点,),。,循环,优化,相关定义,优化方法,代码外提,强度削弱,删除归纳变量,相关定义,“,点,”指某一四元式的位置。,对变量的“,定值,”指对变量赋值或输入值。,定值点,指变量在该点被赋值或输入值。,引用点,则指在该点使用了该变量。,到达一定值点,是指变量在某点定值后到达的一点，通路上没有其它该变量的定值。,如果循环中对变量,I,只有唯一的形如,I:=I,C,的赋值。且其中,C,为循环不变量，则称,I,为循环中的,基本归纳变量,。,如果,J,是循环中一基本归纳变量，,J,在循环中的定值总是可以化归为,I,的同一线性函数，也即,J,C,1,* I,C,2,，,其中,C,1,和,C,2,都是循环不变量，则称,J,为,归纳变量,，并称它与,I,同族。,代码外提,代码外提的流图,不变运算的查找算法,代码外提的要求,代码外提的算法,示例,代码外提的流图,实行代码外提时，在循环的入口结点前面建立一个新结点,(,基本块,),，称之为循环的前置结点。,循环的前置结点以循环的入口结点为其唯一后继，原来流图中从循环外引到循环入口结点的有向边，改成引到循环前置结点。,不变运算的查找算法,(1),依次查看循环,L,中各基本块的每个四元式，如果它的每个运算对象或为常数，或者定值点在,L,外，则将此四元式标记为“不变运算”；,(2),依次查看尚未被标记为“不变运算”的四元式，如果它的每个运算对象或为常数，或者定值点在,L,之外，或只有一个到达,定值点且该点上的四元式已被标记为“不变运算”。则被查看的四元式标记为“不变运算”；,(3),重复第,(2),步直至没有新的四元式被标记为“不变运算”为止。,代码外提的要求,(1),当把循环中的不变运算,A:=B op C,外提时，要求循环中其它地方不再有,A,的定值点。,(2),当把循环中的不变运算,A:=B op C,外提时，要求循环中,A,的所有引用点都是而且仅仅是这个定值所能达到的。,代码外提的算法,1),求出循环,L,的所有不变运算。,2),对步骤,1),所求得的每一不变运算,s,：,A:=B op C,或,A :=op B,检查它是否满足以下条件,(a),或,(b),：,(a)(,)s,所在的结点是,L,的所有出口结点的必经结点。,(,)A,在,L,中其它地方未再定值。,(,)L,中所有,A,的引用点只有,s,中,A,的定值才能到达。,(b)A,在离开,L,之后不再是活跃的，并且条件,(a),的,(I),和,(,),成立。所谓,A,在离开,L,后不再是活跃的是指，,A,在,L,的任何出口结点的后继结点的入口处不是活跃的,(,从此点后不被引用,),。,(3),按步骤,(1),所找出的不变运算的顺序，依次把符合,(2),的条件,(a),或,(b),的不变运算,s,外提到,C,的前置结点中。如果,s,的运算对象,(B,或,C),是在,L,中定值的，则只有当这些定值四元式都已外提到前置结点中时，才可把,s,也外提到前置结点。,代码外提的示例,( 1 ) i : = 1,( 2 ) if x y,goto,B,3,(5)y:=y-1,(6)if y=20,goto,B,5,(3)i:=2,(4)x:=x+1,( 7 ) j : = i,B,1,B,2,B,3,B,4,B,5,(3)i:=2,( 1 ) i : = 1,( 2 ) if x y,goto,B,3,(5)y:=y-1,(6)if y=20,goto,B,5,(4)x:=x+1,( 7 ) j : = i,B,1,B,2,B,3,B,4,B,5,B,2,在,入口处,(B,2,),，,如果,x,的值,大于或等于,y,，,则将,i:=2,外提则是错误的。,强度削弱,(,算法,),(1),找出循环中的所有基本归纳变量。,(2),找出所有其它归纳变量,A,，,并找出,A,与已知基本归纳变量,x,的同族线性函数关系,F,A,(x),。,具体地说：,(a),在循环,L,中找出形如,A:=B*C,，,A := C*B,，,A := B/C,，,A := B,C,，,A := C,B,的四元式，其中,B,是归纳变量，,C,是循环不变量。,(b),假设找出的四元式为,s,：,A := C*B,，,这时,:,(I),如果,B,就是基本归纳变量，则,X,就是,B,，,A,与基本归纳变量,B,是同族的归纳变量，且,A,与,B,的函数关系就是,F,A,(B),C*B,。,(II),如果,B,不是基本归纳变量，假设,B,与基本归纳变量,D,同族且它们的函数关系为,F,B,(D),，,那么，如果,L,外,B,的定值点不能到达,s,且,L,中,B,的定值点与,s,之间未曾对,D,定值，则,x,就是,D,，,A,与基本归纳变量,D,是同族的归纳变量，,A,与,D,的函数关系是：,F,A,(D),C*B,C* F,B,(D),。,强度削弱,(,算法,),(3),对,(2),中找出的每一归纳变量,A,，,假设,A,与基本归纳变量,B,同族，而且,A,与,B,的函数关系为,F,A,(B),C,1,*B+C,2,，,其中,C,1,和,C,2,均为循环不变量，执行以下步骤,:,(a),建立一个新的临时变量,S,FA(B),。,如果两个归纳变量同族且这两个归纳变量与其同族基本归纳变量的函数关系相同，即，若,A,和,A,都与,B,同族且,F,A,(B),F,A,(B),，,则为这两个归纳变量只建一个临时变量,S,FA,(B),。,(b),在循环前置结点原有的四元式后，增加：,S,FA(B),:= C,1,*B,S,FA(B),:=S,FA(B),+C,2,如果,C,2,0,，,则没有后一四元式。,(c),把循环中原来对,A,赋值的四元式改为,A:= S,FA(B),。,(d),在循环中基本归纳变量,B,的唯一赋值,B:,B,E(E,为循环不变量,),后增加：,S,FA(B),:= S,FA(B),C,1,* E,如果,C,1,1,且,E,是变量名，则上式是以下两个四元式：,T:= C,1,* E,S,FA(B),:= S,FA(B), T,其中,T,为,临时变量。,强度削弱,(,算法,),(4),依次考察,(3),中每一归纳变量,A,，,如果在,A := S,FA(B),与循环中任何引用,A,的四元式之间没有对,S,FA(B),的赋值且,A,在循环出口之后不活跃，则删除,A := S,FA(B),，,并把所有引用,A,的地方改为引用,S,FA(B),。,删除归纳变量,(1),找出循环中的所有基本归纳变量,B,。,(2),如果基本归纳变量,B,在循环出口之后不是活跃的，并且在循环中，除在其自身的递归赋值中被引用外，只在形如,if B,rop,Y,goto,Z,中被引用，则：,(a),选取一个与,B,同族的归纳变量,M,，,并设,F,M,(B),C,l,*B+ C,2,。,(b),建立一个临时变量,R,，,并用,R:=C,1,*Y,R:=R+C,2,if F,M,(B),rop,Y,goto,Z,来替换,if B,rop,Y,goto,Z,(c),删除循环中对,B,递归赋值的四元式。,数据流的分析与全局优化,主要的概念,到达,-,定值,引用,-,定值链,活跃变量,定值,-,引用链,可用表达式,数据流方程,复写传播,到达,-,定值,定值点,:,变量,A,的定值是一个语句,(,四元式,),，它赋值或可能赋值给,A,，,最普通的定值是对,A,的赋值或读值到,A,的语句，该语句的位置称作,A,的定置点。,到达,-,定值,:,变量,A,的定值点,d,到达某点,p,，,是指如果有路径从紧跟,d,的点到达,p,、,并且在这条路径上,d,没有被“注销”,(,指该变量重新被定值,),。即在流图中从,d,有一条路径到达,p,且该通路上没有,A,的其它定值。,引用,-,定值链,假设在程序中某点,u,引用了变量,A,的值，则把能到达,u,的,A,的所有定值点的全体，称为,A,在引用点,u,的,引用,-,定值链,。,通常，把到达,-,定值信息存储作为引用,-,定值链是比较方便的，它是所有能够到达变量的某个引用的定值表。也称之为,ud,链。,在进行循环优化时为了求出循环中的所有不变运算，我们需要知道各变量引用点的,ud,链,信息。,活跃变量,对程序中的某变量,A,和某点,p,而言，如果存在一条从,p,开始的通路，其中引用了,A,在点,P,的值，则称,A,在点,p,是活跃的。否则称,A,在点,p,是死亡的。,无论是基本块优化或是循环优化，都可能引起某些变量的定值在该基本块或循环内不会被引用；只要这些变量在基本块或循环的出口之后也不是活跃的，那么，这些变量在该基本块或循环内的定值就是无用赋值，从而可以予以删除。因此，活跃变量的分析对于删除无用赋值是很有意义的。,定值,-,引用链,对一个变量,A,在某点,p,的定值，该定值能到达的对,A,的所有引用点。这些引用点的集合称为该定值点的定值,引用链，简称,du,链。,可用表达式,如果从首结点到,p,的每条路径上,(,不必是无环,),都计算,X op Y,，,并且在每条通路上最后一个这样的计算和,p,之间没有对,X,和,Y,的定值，则称表达式,X op Y,在点,p,可用。,对可用表达式，如果一个基本块对,X,或,Y,赋值,(,或可能赋值,),，并且随后没有重新计算,X op Y,，,则称为,基本块注销表达式,。,如果它计算,X op Y,，,并且随后又没有重新定义,X,或,Y,，,则称为,基本块产生表达式,。,可用表达式的应用,可用表达式的应用,可用表达式的基本应用是寻找公共子表达式。,首先要计算基本块产生的可用表达式集合。,在块的开始点，假定无可用表达式，从头到尾扫描块中所有语句。如果在,p,点可用表达式集合是,A,，,q,是,p,的下一点，,p,和,q,之间的语句是,X :,Y op Z,。,那么,q,点的可用表达式集合由下列两步计算,:,1,把表达式,Y op Z,加入,A,。,2,删掉,A,中任何含,X,的表达式。,注意，这两步必须以此次序完成，因为,x,可能就是,Y,和,Z,。,到达块的结束点之后，,A,是由此块产生的表达式集合。,注销表达式集合是所有的表达式,Y op Z,，,其中,Y,或,Z,在本块中定值，并且该块没有产生,Y op Z,。,示例,可用表达式的应用示例,语句,(1) a:=b+c,(2) b:=a-d,(3) c:=b+c,(4) d:=a-d,可用表达式,none,only b+c,only a-d,only a-d,none,左图的四个语句中：,第一个语句后，,b+c,可用。,第二个语句后，,a-d,可用，,b+c,不再可用，因为,b,已重新定值。,第三个语句不能使,b+c,再次可用，因为,c,的值立即改变。,经最后一个语句，,a-d,也不再可用，因为,d,已改变。,这样，没有可用表达式生成，包含,a,，,b,，,c,或,d,的表达式都被注销。,数据流方程,基本形式,建立和解散的依据,具体的数据流方程,到达,-,定值数据流方程,可用表达式数据流方程,活跃变量数据流方程,数据流方程的,基本形式,当控制流通过一个语句时，在语句末尾的信息是进入这个语句中的信息扣除语句中产生和注销的信息并上产生的信息。这样的方程称之为数据流方程。,一般形式：,outs=,ins-kills,gens,建立和解散的依据,1,、产生和注销的概念依赖于所需要的信息，即根据数据流方程所要解决的问题来决定。对某些问题，有可能不是沿着控制流前进和由,ins,来定义,outs,，,而是反向前进和由,outs,来定义,ins,。,2,、,因为数据沿控制路径流动，所以数据流分析受程序控制结构影响。事实上，当写,outs,时，隐合地认为控制流从语句的唯一出口点离开这个语句。通常方程是在基本块一级建立而不是在语句级建立。因为基本块有唯一的出口点。,3,、在过程调用，通过指针赋值以及对数组变量的赋值语句中，常常会伴随一些问题，对于这些问题需进行相应的处理。,到达,-,定值数据流方程,约定,求定值点的规则,到达,-,定值数据流方程,outB=mB-killB,genB,inB=,outp p,PB,求解算法,示例,约定,inB:,到达基本块,B,入口之前的各个变量的所有定值点集,。,outB:,到达,B,的出口之后,(,紧接着,B,出口之后的位置,),的各个变量的所有定值点,。,genB:B,中定值的并到达,B,出口之后的所有定值点集。也即,B,所“生成”的定值点集。,killB:,基本块,B,外满足下述条件的定值点集：,这些定值点所定值的变量在,B,中巳被重新定值。也即,B,所“注销”的定位点集。,genB,和,killB,均可直接从给定的流图求出，利用,genB,和,killB,可以列出关于,inB,和,outB,的数据流方程而求出,InB,和,outB,。,求定值点的规则,1,、,如果,B,中,p,的前面有,A,的定值，则到达,p,的,A,的定值点是唯一的，它就是与,p,最靠近的那个,A,的定值点。,2,、如果,B,中,p,的前面没有,A,的定值，则到达,p,的,A,的所有定值点就是,inB,中,A,的那些定值点。,求解算法,begin,for i:= 1 to n do,begin,in Bi :=,;,outBi :=,genBi,;,end;,change := true;,while change do,begin,change := false;,for i := 1 to n do,begin,newin,:=,outp; /p,PBi,if,newin,inBi then,begin,change :=,ture,;,inBi :=,newin,;,out Bi : = (inBi kill Bi),genBi,end,end,end,end,到达,-,定值数据流方程示例,B1,B2,B3,B4,B5,i:=2,j:=i+1,i:=1,j:=j+1,j:=j-4,B2,B1,B3,B4,B5,d1,d2,d3,d4,d5,d6,d7,流图,深度为主扩展树,gen,和,kill,的值,置迭代初值,迭代过程,a:=i,b:=j,gen,和,kill,的值,基本块,B,genB,位向量,killB,位向量,B1,d1,d2,1100000,d3,d4,d5,0011100,B2,d3,0010000,d1,1000000,B3,d4,0001000,d2,d5,0100100,B4,d5,0000100,d2,d4,0101000,B5,0000000,0000000,迭代过程,基本块,B,第一次,第二次,第三次,第四次,inB,outB,inB,outB,inB,outB,inB,outB,B1,0010000,1100000,0110000,1100000,0111100,1100000,0111100,1100000,B2,1100000,0110000,1111100,0111100,1111100,0111100,1111100,0111100,B3,0110000,0011000,0111100,0011000,0111100,0011000,0111100,0011000,B4,0011000,0010100,0011000,0010100,0011000,0010100,0011000,0010100,B5,0011100,0011100,0011100,0011100,0011100,0011100,0011100,0011100,置迭代初值,开始，置迭代初值,(,第,0,次迭代,),inB1,inB2,inB3,inB4,inB5,0000000,outB1,1100000,outB2,0010000,outB3,0001000,outB4,0000100,outB5,0000000,执行算法第,(4),行，置,change,为,true,。,第一次迭代,迭代初值,(,第,1,次迭代开始，置,change,为,false),，,在算法第,(7),行按深度为主次序依次对,B1,，,B 2,，,B3,，,B4,，,B5,执行算法第,(8),行至第,(12),行。,对于,B1:,newin,=outB2=0010000,inB1,所以，,change,为,true,，,inB1 =0010000,outB1 = inB1 killB1,gen,B1,=0010000-0011100,1100000=1100000,对于,B2:,newin,=outB1,outB5 = 1100000,0000000,inB2,所以，,change,为,true,，,inB2 =1100000,outB2 = inB2 killB2,gen B2,=1100000-1000000,0010000= 0110000,对于,B3:,newin,=outB2=0110000,inB3,所以，,change,为,true,，,inB3 =0110000,outB3 = inB3 killB3,gen,B3,=01