第5章代码优化.

第5章代码优化第5章代码优化5.1局部优化5.2循环优化5.3代码优化示例第5章代码优化5.1局部优化局部优化是指对代码的每一个线性部分所进行的优化，使得在这个线性部分只存在一个入口和一个出口，而这个线性部分我们称之为基本块。第5章代码优化5.1.1基本块的划分方法所谓基本块，是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是该序列的第一个语句，出口就是该序列的最后一个语句。对一个基本块来说，执行时只能从其入口进入，从其出口退出。对一个给定的程序，我们可以把它划分为一系列基本块，在各个基本块范围内进行的优化称为局部优化。第5章代码优化划分基本块的关键问题是准确定义入口和出口语句。下面我们给出划分四元式程序为基本块的算法：(1)从四元式序列确定满足以下条件的入口语句：①四元式序列的第一个语句；②能由条件转移语句或无条件转移语句转移到的语句；③紧跟在条件转移语句后面的语句。第5章代码优化(2)确定满足以下条件的出口语句：①下一个入口语句的前导语句；②转移语句(包括转移语句自身)；③停语句(包括停语句自身)。第5章代码优化例如，考察下面求最大公因子的三地址代码程序：(1) readX(2) readY(3) R=X%Y(4) ifR=0goto(8)(5) X=Y(6) Y=R(7) goto(3)(8) writeY(9) halt第5章代码优化(1) readX----------入口（1）B1={(1)(2)}(2) readY(3) R=X%Y----------入口（2）B2={(3)(4)}(4) ifR=0goto(8)(5) X=Y----------入口（3）B3={(5)(6)(7)}(6) Y=R(7) goto(3)(8) writeY-----------入口（2）(3）B4={(8)(9)}(9) halt第5章代码优化5.1.2基本块的优化项目基本块主要完成三项优化：（1）合并常数和已知量：指在编译阶段可以计算出来的量直接完成其运算。（2）消除多余运算：指一个运算多次出现，而运算量没有发生改变，就只运算一次。（3）消除无用赋值：指对一个变量多次赋值而只引用该变量的当前值，则可以将无用赋值删除。第5章代码优化例如，考察下面基本快的三地址代码程序：(1)T1=A*B(2) T2=3/2(3) T3=T1-T2(4) X=T3(5) C=2(6) T4=A*B(7) C=5(8) T5=18+C(9) T6=T4*T5第5章代码优化完成三项优化后的基本快的三地址代码程序：(1)T1=A*B(2) T2=1.5(3) T3=T1-T2(4) X=T3(5) T4=T1(6) C=5(7) T5=23(8) T6=T4*T5第5章代码优化5.1.3基本块的DAG表示和构造DAG(DirectedAcyclicGraph)是一种有向图，常常用来对基本块进行优化。一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG：(1)图的叶结点(无后继的结点)以一标识符(变量名)或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来表示一变量A的地址，则用addr(A)作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。第5章代码优化(2)图的内部结点(有后继的结点)以一运算符作为标记，表示该结点代表应用该运算符对其直接后继结点所代表的值进行运算的结果。(3)图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。第5章代码优化一个基本块由一个四元式序列组成，且每一个四元式都可以用相应的DAG结点表示。图5–1给出了不同四元式和与其对应的DAG结点形式。图中，各结点圆圈中的ni是构造DAG过程中各结点的编号，而各结点下面的符号(运算符、标识符或常数)是各结点的标记，各结点右边的标识符是结点上的附加标识符。第5章代码优化n1BA(1)A＝Bn2n1ABop(2)A＝opBn1Bn2Cn3opA(3)A＝BopCn1Bn2Cn3＝[](4)A＝B[C]n1Bn2Cn3rop(S)(5)ifBropCgoto(S)n1Dn3n4(6)D[C]＝Bn2＝[]CBn1(S)(7)goto(S)图5–1四元式与DAG结点第5章代码优化利用DAG进行基本块优化的基本思想是：首先按基本块内的四元式序列顺序将所有的四元式构造成一个DAG，然后按构造结点的次序将DAG还原成四元式序列。由于在构造DAG的同时已作了局部优化，所以最后所得到的是优化过的四元式序列。为了DAG构造算法的需要，我们将图5–1中的四元式按照其对应结点的后继结点个数分为四类：第5章代码优化(1)0型四元式：后继结点个数为0，如图5–1(1)所示；(2)1型四元式：有一个后继结点，如图5–1(2)所示；(3)2型四元式：有两个后继结点，如图5–1(3)、(4)、(5)所示；(4) 3型四元式：有三个后继结点，如图5–1(6)所示。第5章代码优化我们规定：用大写字母(如A、B等)表示四元式中的变量名(或常数)；用函数Node(A)表示A在DAG中的相应结点，其值可为n或者无定义，并用n表示DAG中的一个结点值。这样，每个基本块仅含0、1、2型四元式的DAG构造算法如下(对基本块的每一个四元式依次执行该算法)：第5章代码优化(1)若Node(B)无定义，则构造一标记为B的叶结点并定义Node(B)为这个结点，然后根据下列情况做不同处理：①若当前四元式是0型，则记Node(B)的值为n，转(4)。②若当前四元式是1型，则转(2)①。③若当前四元式是2型，则：i.如果Node(C)无定义，则构造一标记为C的叶结点，并定义Node(C)为这个结点；ii.转(2)②。第5章代码优化(2)①若Node(B)是以常数标记的叶结点，则转(2)③，否则转(3)①。②若Node(B)和Node(C)都是以常数标记的叶结点，则转(2)④，否则转(3)②。③执行opB(即合并已知量)，令得到的新常数为P。若Node(B)是处理当前四元式时新建立的结点，则删除它；若Node(P)无定义，则构造一用P做标记的叶结点n并置Node(P)=n；转(4)。第5章代码优化④执行BopC(即合并已知量)，令得到的新常数为P。若Node(B)或Node(C)是处理当前四元式时新建立的结点，则删除它；若Node(P)无定义，则构造一用P做标记的叶结点n并置Node(P)=n；转(4)。(3)①检查DAG中是否有标记为op且以Node(B)为惟一后继的结点(即查找公共子表达式)。若有，则把已有的结点作为它的结点并设该结点为n；若没有，则构造一个新结点；转(4)。第5章代码优化②检查DAG中是否有标记为op且其左后继为Node(B)、右后继为Node(C)的结点(即查找公共子表达式)。若有，则把已有的结点作为它的结点并设该结点为n；若没有，则构造一个新结点；转(4)。(4)若Node(A)无定义，则把A附加在结点n上并令Node(A)=n；否则，先从Node(A)的附加标识符集中将A删去(注意，若Node(A)是叶结点，则不能将A删去)，然后再把A附加到新结点n上，并令Node(A)=n。第5章代码优化5.1.4利用DAG进行基本块的优化处理利用DAG进行基本块优化处理的基本思想是：首先按基本块内的四元式序列顺序将所有的四元式构造成一个DAG，在构造DAG的同时完成局部优化，然后按构造结点的次序将DAG还原成四元式序列得到优化过的四元式序列。例如：我们给出如下基本块，利用DAG完成对该基本块的各项优化。[解答]按照算法顺序处理每一四元式后构造出的DAG如图5–2所示，其中每一子图(1)、(2)、…、(10)分别对应四元式(1)～(10)的DAG构造。第5章代码优化(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第5章代码优化n6n1n2T0T1,T3n3n4n5n7n8B*A,T5T6T2,T4*＋－3.146.28Rr(10)B＝T5*T6(9)T6＝R－rn6n1n2T0T1,T3n3n4n5A,B,T5T2,T4*＋3.146.28Rr(8)T5＝T3*T4n6n1n2T0T1,T3n3n4n5n7A,B,T5T6T2,T4*＋－3.146.28Rrn6n1n2T0T1,T3n3n4n5A,BT2,T4*＋3.146.28Rr(7)T4＝R＋r(6)T3＝2*T0n6n1n2T0T1n3n4n5A,BT2*＋3.146.28Rr(5)B＝An6n1n2T0T1,T3n3n4n5A,BT2*＋3.146.28Rrn6n1n2T0T1n3n4n5AT2*＋3.146.28Rr(4)T4＝T1*T2(3)T3＝R＋rn1T0n1n2n3T1*3.143.142(2)T1＝2*T0n1n2T0T1n3n4n5T2＋3.146.28Rr6.28(1)T0＝3.14图5–2DAG第5章代码优化(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第5章代码优化将G'和原基本块G相比，我们看到：(1) G中四元式(2)和(6)都是已知量和已知量的运算，G'已合并；(2) G中四元式(5)是一种无用赋值，G'已将它删除；(3) G中四元式(3)和(7)的R+r是公共子表达式, G'只对它们计算了一次，即删除了多余的R+r运算。因此，G'是对G实现上述三种优化的结果。第5章代码优化通过观察图5–2(10)中的所有叶结点和内部结点以及其上的附加标识符，还可以得出以下结论：(1)在基本块外被定值并在基本块内被引用的所有标识符就是DAG中相应叶结点上标记的标识符；(2)在基本块内被定值且该值能在基本块后面被引用的标识符就是DAG各结点上的附加标识符。第5章代码优化这些结论可以引导优化工作的进一步深入，尤其是无用赋值的优化，也即：(1)如果DAG中某结点上的标识符在该基本块之后不会被引用，就可以不生成对该标识符赋值的四元式。(2)如果某结点ni上没有任何附加标识符，或者ni上的附加标识符在该基本块之后不会被引用，而且ni也没有前驱结点，这表明在基本块内和基本块之后都不会引用ni的值，那么就不生成计算ni结点值的四元式。第5章代码优化(3)如果有两个相邻的四元式A=CopD和B=A，其中第一条代码计算出来的A值仅在第二个四元式中被引用，则将DAG中相应结点重写成四元式时，原来的两个四元式可以优化为B=CopD。假设例5.1中T0、T1、T2、T3、T4、T5和T6在基本块后都不会被引用，则图5-2(10)中的DAG就可重写为如下的四元式序列：第5章代码优化(1) T1=R+r/*T1、T2为存放中间结果的临时变量*/(2) A=6.28*T1(3) T2=R−r(4) B=A*T2第5章代码优化以上把DAG重写成四元式序列时，是按照原来构造DAG结点的顺序(即n5、n6、n7、n8)依次进行的。实际上，我们还可以采用其它顺序(如自下而上)重写，只要其中的任何一个内部结点是在其后继结点之后被重写并且转移语句(如果有的话)仍然是基本块的最后一个语句即可。第5章代码优化5.2循环优化5.2.1程序流图与循环为了进行循环优化，必须先找出程序中的循环。由程序语言的循环语句形成的循环是不难找出的，但由条件转移语句和无条件转移语句同样可以形成程序中的循环，并且其结构可能更加复杂。因此，为了找出程序中的循环，就需要对程序中的控制流程进行分析。我们应用程序的控制流程图来给出循环的定义并找出程序中的循环。第5章代码优化一个控制流程图(简称流图)就是具有惟一首结点的有向图。所谓首结点，就是从它开始到控制流程图中任何一个结点都有一条通路的结点