(精品)第10章 优化

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,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,:= 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,四. 删除归纳变量,3.,示例,由,B3,中,(13),可以看出，,I,是循环的基本归纳变量,由,B2,中,(4),和,B3,中,(4),可以看出，,T,2,:= 10*I,， 故,T,2,是与,I,同族的归纳变量,由,B2,中,(8),和,B3,中,(8),可以看出，,T,6,:= 10*I,， 故,T,6,是与,I,同族的归纳变量,由,B2,中,(5),和,B3,中,(5),可以看出，,T,3,:= 10*I+T,1,， 故,T,3,是与,I,同族的归纳变量,由,B2,中,(9),和,B3,中,(9),可以看出，,T,7,:= 10*I+T,5,， 故,T,7,是与,I,同族的归纳变量,若基本归纳变量,I,仅用于自身递归定值,(13),和控制循环进行,(2),，则可对其进行优化,方法是用与,I,同族的任一归纳变量,(T,2,、,T,3,、,T,6,或,T,7,),来替换循环控制条件中的,I,如用,T,3,代替,I,，则由于,T,3,:= 10*I+T,1,，故,(2),中,I10,与,T,3,100+T,1,等价,故原代码中的,(2),可变为,(2,1,),、,(2,2,),两条代码，并将不便运算,(2,1,),外提至,B2,中,(2,1,) R := 100+T,1,(2,2,) if T,3,R,goto,(15),B2,(2,2,) if T,3,R,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,:= 10*I,(5)T,3,:= T,2,+T,1,(2,1,) R := 100+T,1,若循环后不再引用变量,I,，则可将无效赋值,(13),删去,若循环后不再引用变量,T,2,，则可将无效赋值,(4),删去,(,变量,T,6,与,(8),同理,),B3,(4)T,2,:= T,2,+10,(11)T,9,:= T,8,T,7,(12)T,4,T,3, := T,9,+1,(14)goto B2,(5)T,3,:= T,3,+10,(8)T,6,:= T,6,+10,(9)T,7,:= T,7,+10,B3,(11)T,9,:= T,8,T,7,(12)T,4,T,3, := T,9,+1,(14)goto B2,(5)T,3,:= T,3,+10,(8)T,6,:= T,6,+10,(9)T,7,:= T,7,+10,B3,(11)T,9,:= T,8,T,7,(12)T,4,T,3, := T,9,+1,(14)goto B2,(5)T,3,:= T,3,+10,(9)T,7,:= T,7,+10,至此归纳变量删除完毕,(T,3,、,T,7,不能删除，因循环中用此二变量进行数组的偏移量定值,),(13)I := I+1,(4)T,2,:= T,2,+10,(8)T,6,:= T,6,+10,(5)T,3,:= T,3,+10,(9)T,7,:= T,7,+10,(13)I := I+1,(4)T,2,:= 10*I,(8)T,6,:= 10*I,(5)T,3,:= T,2,+T,1,(9)T,7,:= T,6,+T,5,(2) if I10,goto,(15),I10,T,3,100+T,1,(13)I := I+1,(4)T,2,:= T,2,+10,(8)T,6,:= T,6,+10,(12)T,4,T,3, := T,9,+1,(11)T,9,:= T,8,T,7,(2) if I10,goto,(15),(22) if T,3,R,goto,(15),(2,1,) R := 100+T,1,(2,1,) R := 100+T,1,61,10.4 数据流分析,本节内容,一,.,任意路径数据流分析,二,.,全路径数据流分析,三,.,数据流问题的分类,四,.,其他主要的数据流问题,五,.,利用数据流信息进行全局优化,62,数据流分析概述,分析数据的值在基本块之间是如何被修改的，,这种工作就是,全局数据流分析,。,在优化中往往要在,全局范围内,考虑数据值的变化情,况以及变量的定义、使用情况等。,63,数据流分析概述,全局数据流分析有两种分类方法：,根据信息流与控制流的相对方向可分为：,向前流问题,（方向一致）,向后流问题,（方向相反）,根据分析时对于路径的不同要求可分为：,任意路径数据流分析,（性质在某条路径为真）,全路径数据流分析,（性质在所有可能路径为真）,64,数据流分析概述,数据流分析往往使用,方程,作为工具,数据流方程往往,成对出现,：,一个方程描述,基本块之间的关系,一个方程描述,基本块内部的关系,不同数据流分析,所使用的方程不同，但,方程结构十分类似,65,一.任意路径数据流分析,我们执行数据流分析时,假定,流图中,所有路径都是有可能执行的,。,涉及多个基本块范围的优化通常,依赖于,对程序的可能执行路径的分析。,1.,概述,66,一.任意路径数据流