编译原理第9章.ppt

第9章 代码优化,目录,9.1 优化技术简介9.2 局部优化9.3 控制流分析和循环优化,9.1 优化技术简介,一、代码优化的目的 提高目标代码的运行效率。注：效率是指目标代码运行时间较短，占有空间较少。二、代码优化的实质 代码优化实际上是对代码进行等价变换，由一组代码变成运行结果相同的另一组代码。,与机器无关的优化-对中间代码进行；依赖于机器的优化-对目标代码进行,三、优化阶段,四、优化分类,根据优化所涉及的程序范围分成:(1)局部优化:(基本块)(2)循环优化:对循环中的代码进行优化(3)全局优化:在整个程序范围内的优化,五、常用优化技术简介,1.删除多余运算2.循环不变代码外提3.强度削弱4.变换循环控制条件5.合并已知量与复写传播6.删除无用赋值,目的：提高目标代码速度。例如：P:=0for I:=1 to 20 do P:=P+AI*BI,1.删除多余运算（删除公共子表达式）：,(1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=4*I(7)T5:=addr(B)-4(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if I=20 goto(3),减少循环中代码总数的重要办法。方法：把循环不变运算，即其结果独立于循环执行次数的表达式提到循环的前面，使之只在循环外计算一次。例如：P:=0for I:=1 to 20 do P:=P+AI*BI,2、代码外提,(1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=T1(7)T5:=addr(B)-4(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if I=20 goto(3),(1)P:=0(2)I:=1(3)T1:=4*I(5)T3:=T2T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if I=20 goto(3),(4)T2:=addr(A)-4(7)T5:=addr(B)-4,(6)T4:=T1,基本思想：把强度大的运算换算成强度小的。例如：a)i*2=2*i=i+i=i1b)i/2=(int)(i*0.5)c)0-1=-1d)f*2=2.0*f=f+fe)f/2.0=f*0.5,3.强度削弱,(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if I=20 goto(3),(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if I=20 goto(5),(3)T1:=4*I,(3)T1:=T1+4,4、变换循环控制条件,如果在循环体内存在一个变量T 与循环控制变量I保持线性关系，同时在循环后面不引用I，而除去I又不影响程序结果，则可以由T 取代的控制循环次数的作用。从循环中删除这这种方法称为变换循环控制条件，或称为删除归纳变量。,(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3)T1:=T1+4(12)if I=20 goto(5),(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(3)T1:=T1+4,(12)if T1=80 goto(5),5、合并已知量与复写传播,已知量就是指常数或在编译时就能确定其值的变量。若参加运算的两个对象在编译时都是已知量，则可以在编译时候直接计算出它们的运算结果，不必等到程序运行时再计算，这种变换称为合并已知量或常数合并。复写传播是指尽量不引用那些在程序中仅仅只传递信息而不改变其值，也不影响程序运行结果的变量。通过复制后没有再改变的值可以互相替换，不会改变程序的结果。,(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(3)T1:=T1+4(12)if T1=80 goto(5),(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)(5)T3:=T2T1(6)T4:=T1(9)T7:=T3*T6(10)P:=P+T7(3)T1:=T1+4(12)if T1=80 goto(5),(3)T1:=4,(8)T6:=T5T1,(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T1(9)T7:=T3*T6(10)P:=P+T7(3)T1:=T1+4(12)if T1=80 goto(5),(1)P:=0(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2T1(8)T6:=T5T1(9)T7:=T3*T6(10)P:=P+T7(3)T1:=T1+4(12)if T1=80 goto(5),6.删除无用赋值,局部优化：基本块内的优化,9.2局部优化,一、基本块1、定义 程序中一个只有一个入口和一个出口的一段顺序执行的语句序列，称为程序的一个基本块。注：1)一个给定的程序，可以划分为一系列的基本块。优化在各基本块中分别进行。2)局部优化就是局限于基本块范围内的优化。3)在运行基本块时，只能从其入口进入，从出口退出。,a)求出各基本块的入口语句 对四元式程序，各个基本块的入口语句是：1)程序的第一个语句；或 2)能由条件转移语句和无条件转移语句转移到达的语句；或 3)紧跟在条件转移语句后面的语句。注：若条件语句由真转移和假转移两条语句组成，则跟在转移语句后面的语句是指假转移语句后面的一条语句。,2、划分基本块算法,b)根据入口语句，构造其所属的基本块 一入口语句所属的基本块是由该入口语句到:下一入口语句(不包括该入口语句);或到一转移语句(包括转移语句);或到一停(halt)语句(包括该语句)之间的语句序列组成。C)删除不会被执行的语句 凡是没有纳入到任何一个基本块中的语句，都是程序控制流程所无法到达的语句，即不会被执行到的语句，可将其删除。,例：求最大公因子算法 begin read X;read Y;while(X mod Y0)do begin T:=X mod Y;X:=Y;Y:=T end;write Y end,(1)Read X(2)Read Y(3)T1:=X mod Y(4)If T10 goto(6)(5)goto(10)(6)T:=X mod Y(7)X:=Y(8)Y:=T(9)goto(3)(10)write Y(11)halt,四元式序列：,基本块的划分：,主要是进行已知量合并、删除公共子表达式、删除无用赋值。注：仅在一个基本块中，是否是无用赋值很难判断。这是因为，无用赋值有以下情形：(a)对某变量A赋值后，在程序中没有引用；(b)对某变量A赋值后，在引用前又重新赋值；(c)对某变量A进行自增赋值，且它仅仅被用在自增运算中。对上面第一和第三种情况，应进行全局分析。,3、块内优化,1、DAG(有向无环图)定义a)父子结点 若在一有向图中，结点ni有弧指向nj，则称ni是nj的父结点，nj是ni的子结点。B)路径与环路 若在一有向图中，结点n1 n2 nk间存在有向弧n1n2 nk,则称n1 到nk之间存在一条通路，若n1 nk则该路径称为环路；c)有向无环图 若有向图中任一路径都不是环路，则称该图为无环路有向图。,二、基本块的DAG表示,a)叶结点 以一标识符(变量名)或常数作为标记。即，该结点代表该变量或常数的值。注：1)若叶结点代表变量a的地址，则标记为addr(a)。2)通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。b)内部结点 以一运算符作为标记。即，该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。c)附标：图中各个结点上可能附加一个或多个标识符，表示这些标识符具有该结点所代表的值，这简称附标。,2、DAG结点标记或附标,例如：A:=B op C 即四元式(op,B,C,A)的DAG图为：注：1)图中的有向弧都省去箭头。2)结点ni是构造DAG过程中给予各结点的编号;3)各结点下面的符号（运算符、变量、常数）是各结点的标记;4)各结点右边的标识符是结点的附标。,根据其对应结点的子结点个数，可分为0型、1型、2型和3型四种类型。A)0型A:=B,GOTO(S)即四元式(:=,B,_,A),其DAG结点为0型：,3、四元式的DAG结点类型,B)1型A:=op B，即四元式(op,B,_,A)，其DAG结点为1型：,C)2型 A:=B op C，即四元式(op,B,C,A)，其DAG结点为2型；A:=BC，即四元式(=,BC,_,A)，其DAG结点为2型；if B rop C goto(s)即四元式(jrop,B,C,(s)其DAG结点为2型,D)3型 DC:=B即四元式(=,B,_,DC)，其DAG结点为3型：,说明：大写字母（A、B）表示四元式中变量名；Node(A):表示A在DAG中的相应结点，其值可以为n或无定义。N表示DAG中的一个结点值。由基本块构造DAG的算法如下：将元表和结点表置空。对基本块内每个四元式(op,B,C,A)进行如下操作：1)查元表中有无结点B，有则返回其序号，无则建立该结点并返回序号；2)若四元式类型为0型，则不做任何操作；,4、基本块的DAG构造算法,3)若四元式类型为1型(即：A:=OP B)，则 IF node(B).标记常量 THEN/*叶*/执行OP B 得值P/*合并已知量*/,若node(B)是当前四元式建立的，就删去。查有无node(P)结点，有就返回结点序号，没有就建立并返回其序号 ELSE 查结点表是否有一结点，其后继为node(B)，标 记为OP，有就返回结点序号，没有就建立并返回其序号,4)若四元式类型为2型(即：A:=B OP C)，则，查元表中有无结点node(C),有就返回结点序号，没有就建立并返回其序号;IF(node(B).标记常量)AND(node(C).标记常量)执行B OP C 得值P/*合并已知量*/若node(B),node(C)是当前四元式建立的，就删去;查有无结点node(P),有就返回结点序号，没有就建立并返回其序号;ELSE 查结点表是否有一结点，其左后继为node(B)且右后继为node(C)，标记为OP，有就返回结点序号，没有就建立并返回其序号。;,5)如果NODE（A）无定义，则把A附加在结点n上并令NODE（A）n；否则先把A从NODE（A）结点上的附加标识符集中删除（注意，如果NODE（A）是叶结点，则其标记A不删除），把A附加到新结点n上并令NODE（A）n。转处理下一四元式。,例如：下面程序用来求圆环内外圆周之和及圆环正反两面面积之和。对其优化：Pi:=3.14 A:2*Pi*(R+r);B:=A;B:=2*Pi*(R+r)*(R-r)由语法制导翻译生成右边的四元式序列,(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:=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,(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,(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,(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,(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,(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,(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,(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,(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,(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,1、可做到三种优化 a)合并已知量 对任何一个四元式，若其中参与运算的对象均是编译时的已知量，则合并已知量，并用合并后算出的常量生成一个叶结点。若参与运算的已知量的叶结点是当前四元式建立的结果，则可删除。b)删除对变量的前一个赋值，即删除该变量的前一个附标。c)检查公共子表达式 对具有公共子表达式的所有四元式，只产生一个计算该表达式值的内部结点，而将那些被赋值的变量附加到该结点。,三、DAG在基本块优化中的作用,2、利用DAG图还原四元式序列 a)若为叶结点，无附标，则不生成任何四元式；b)若为叶结点，标记为B，附标为A，则生成A:=B四元式；若有多个附标，则生成值为B的相应赋值语句四元式 c)若为中间结点，有附标，则根据其标记op，生成相应四元式(如A:=B op C,A:=op B,A:=BC或if B rop C goto(s)；若有多个附标，则除了第一个附标用于生成相应四元式，其它生成值为第一个附标的赋值语句四元式 d)若中间结点无附标，则添加一个临时附标SA，然后转c),(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,3、获得其它优化信息 a)在基本块外定值并在基本块内被引用的所有标识符，就是作为叶结点标记的那些标识符。b)在基本块内被定值，且该值能在基本块后面被引用的所有标识符，就是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,S1:=R+rA:=6.28*s1S2:=R-rB:=A*S2,一、控制流分析作用1、是数据流程分析的基础2、找出程序中的循环注：1)循环包括循环语句构成的循环及条件转移和无条件转移构成的循环。2)为了找出程序中的循环，也需要进行程序数据流程分析。,9.3 控制流分析和循环优化,1、程序流图定义 以基本块作为结点，控制程序流向作为有向弧，画出的图，称为程序流图。注；1)程序流图的特点是具有唯一首结点的有向图。所谓首结点，是包含程序第一个语句的基本块。2)从首结点沿着流图可到达任何结点。,二、程序流图与必经结点集,程序流图三元式定义,有向边集的构成：满足下列条件之一时，结点 I到结点j有有向边：基本块j在程序的位置紧跟在i后,且i的出口语句不是无条件转移goto(S)或停语句i的出口是goto(S)或if goto(S),而(S)是j的入口语句,(1)Read X(2)Read Y,(3)T1:=X mod Y(4)If T1=0 goto(8),(5)X:=Y(6)Y:=T1(7)goto(3),(8)write Y(9)halt,B1,B2,B3,B4,程序流图,分析程序流图中结点间的关系（1）m DOM n 定义 在程序流图中,对任意两个结点m和n,如果从流图的首结点出发,到达n的任意通路都要经过m,则称m是n的必经结点,记为m DOM n(a,a DOM a)（2）必经结点集 定义 结点n的所有必经结点的集合,称为结点n的必经结点集,记为D(n).,2、必经结点集定义,各结点的必经结点集为：D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,6D(7)=1,2,4,7,（3）必经结点DOM的性质,自反性：a,a DOM a传递性：对流图中的任意结点a,b和c，若a DOM b,b DOM c,则有a DOM c。反对称性：若a DOM b且 b DOM a，则有a=b.,DOM关系是一个偏序关系。,1、基本思想 根据一个结点的所有父结点的必经结点集，求出该结点的必经结点集。若设结点n的父结点是P1,P2,Pk，则D(n)=(D(P1)D(P2)D(Pk)n2、具体实现方式 使用迭代方法：比较相邻两次迭代结果，若相同，则结束。,三、求必经结点集算法,3、算法设全部结点集合为N，首结点为n0，D(n0)=n0;for nN-N0 do D(n):=N;/*置初值*/change=TRUE;while change/*完成若干迭代*/change=FALSE;for n N-N0 do/*完成一次迭代*/newd=(D(P1)D(P2)D(Pk)n;if D(n)newd change=TRUE;D(n):=NEWD,注：此算法中没有规定计算结点的顺序，若顺序选的不好，效率可能很低。所以使用算法之前先将流图中各结点排序，此序为深度为主排序。,1、基本思想 利用必经结点集求出流图中的回边，利用回边找出流图中的循环。2、回边定义 设ab是流图中一条有向边，若b dom a，则ab是流图中一条回边。注：1)可应用必经结点集求出流图中的回边。2)设nd是回边，则该回边构成的循环包括如下结点：n、d以及不经过d能到达n的所有结点。,四、查找循环算法,例：求出下图的所有回边,D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,6D(7)=1,2,4,7,有6 dom 6,4 dom 7,2 dom 4故：66，74，42都是流图的回边。,解：首先，求出必经结点集：,3、查找循环的算法1)找出回边nd；2)则n,d必定属于nd回边组成的循环L中，即,L:=n,d;3)若 nd且n的父结点n不在L中，则将它添至L中，即L:=Ln;4)对3)求出的父结点n重复执行3)，直至不再有新结点加入L为止。,回边对应的循环结点：667 442,循环结点：6,循环结点：7,4,5,6,循环结点：4,2,3,7,5,6,4、定理 对于循环必定满足强连通，而且只有唯一入口点。注：1)强连通是指循环中任意两个结点都有通路，单结点循环也有一弧指向自身。它保证了循环内各结点的代码都可反复执行。2)唯一入口点是指要到达循环内任意结点必须经过此入口点。它保证了循环优化时，可将代码外提到唯一入口点前的前置结点中。,五、可归约流图,当且仅当流图中除去回边外，其余的边构成一个无环路回路，就称流图为可归约流图。左图为可归约流图。,5,4,7,6,2,1,3,循环优化：三种重要技术代码外提：产生的结果独立于循环执行次数的表达式，放到循环前面。强度削弱：把程序中执行时间较长的运算替换为时间较短的运算。删除归纳变量：对形如I:=I+C的赋值 C为循环不变量，称I为基本归纳变量。对形如J:=C1*I+C2,的赋值称J为归纳变量,六、循环优化,（一）、代码外提1、循环不变量定义 形如(s)A:=B op C四元式，若(1)B、C为常量；(2)到达(s)点的B、C定值点均在循环外；(3)到达(s)点的B、C定值点虽在循环内，但只有一个定值点且已被标为循环不变运算。则(s)为循环不变运算，A、B、C为循环不变量。注：循环不变量不论循环执行多少次均始终保持不变，有可能外提到循环外，以提高运行速度。,2、循环不变量外提条件a)该不变运算所在结点(基本块)必须是循环出口结点的必经结点或者该不变运算所定值的变量在循环出口之后是不活跃的；b)循环内不变运算所定值的变量只有唯一的一个定值点；c)外提循环不变运算(s)A:=B op C时循环内所有A的引用点必须且仅是(s)所能到达的。,假定程序两次执行途径分别为：B1,B2,B4,B5,出口后B=5;B1,B2,B3,B4,B5,出口后B3；若A:=3外提，则上述两条途径执行结果均为B=3。注意：其原因就是B3不是B4的必经结点，而且A在出口是活跃的。,前提a示例,2、循环不变量外提条件a)该不变运算所在结点(基本块)必须是循环出口结点的必经结点或者该不变运算所定值的变量在循环出口之后是不活跃的；b)循环内不变运算所定值的变量只有唯一的一个定值点；c)外提循环不变运算(s)A:=B op C时循环内所有A的引用点必须且仅是(s)所能到达的。,前提b示例,假定程序外提前执行途径为：B1,B2,B3,B4,B2,B4,出口后B=5;A:=5外提后执行相同的执行途径出口后B3；注意：A有两个定值点。,2、循环不变量外提条件a)该不变运算所在结点(基本块)必须是循环出口结点的必经结点或者该不变运算所定值的变量在循环出口之后是不活跃的；b)循环内不变运算所定值的变量只有唯一的一个定值点；c)外提循环不变运算(s)A:=B op C时循环内所有A的引用点必须且仅是(s)所能到达的。,前提c示例,假定程序外提前执行途径为：B1,B2,B3,出口后B=6;A:=2外提后执行相同的执行途径出口后B3；注意：原因是B3当中引用的A值不仅B4中A的定值可到达，B1中A的定值也能到达。,3、外提算法基本思想 寻找符合循环不变量外提条件的不变运算，进行外提。并外提到前置结点。4、前置结点 实行代码外提时，在循环入口结点前面建立一个新结点(基本块)，即前置结点。注：1)前置结点是唯一的，循环中外提的代码将全部放到前置结点中。2)前置结点以循环入口结点为其唯一后继。,作业,P267：4、5、7,