编译原理第十第二部分

*编译原理——第十章优化（第二部分）王金伟计算机与信息工程学院天津师范大学*五、基本块的DAG表示及其应用1.DAG的基本概念有向边:ninj前驱：ni是nj的前驱后继：nj是ni的后继通路:n1n2,n2n3,...,nk-1nk环路：n1=nkDAG：无环路有向图(DirectedAcyclicGraph)若有向图中，任何一条通路都不是环路，则称该有向图为无环有向图，简称DAGn1n2n3n4n1n2n3n410.2局部优化*2.一个基本块的DAG是一种带有下述标记或附加信息的DAG:n13.14n3n4Rrn5+T2,T4图的叶结点以一标识符或常数作为标记，表示该结点代表该变量或常数的值;图的内部结点以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果;图中各个结点上可能附加一个或多个标识符(称附加标识符)表示这些变量具有该结点所代表的值。*一个基本块，可用一个DAG来表示与各四元式相对应的DAG结点形式:四元式DAG图(0)0型:A:=B(:=，B，-，A)n1AB3.基本块四元式与DAG结点表示*四元式DAG图(1)1型:A:=opB(op，B，-，A)n1ABn2op(2)2型:A:=BopC(op，B，C，A)n2ABn1opn3C*四元式DAG图(3)2型:A:=B[C](=[]，B[C]，-，A)n2ABn1=[]n3C(4)2型:ifBropCgoto(s)(jrop，B，C，(s))n2(s)Bn1ropn3C*四元式DAG图(5)3型:D[C]:=B([]=，B，-，D[C])(6)0型:goto(s)(j，-，-，(s))(s)n1n2Bn1[]=n4Cn3D*假设DAG各结点信息将用某种适当的数据结构存放(如链表)。另设置一个标识符与结点的对应函数:*0，1，2型四元式的基本块的DAG构造算法0型:A:=B1型:A:=opB2型:A:=BopC对基本块中每一四元式，依次执行以下步骤:1.准备操作数的结点2.合并已知量3.删除公共子表达式4.删除无用赋值*1.准备操作数的结点0型:A:=B1型:A:=opB2型:A:=BopC如果NODE(B)无定义，则构造一标记为B的叶结点并定义NODE(B)为这个结点;如果当前四元式是0型，则记NODE(B)的值为n，转4。如果当前四元式是1型，则转2(1)如果当前四元式是2型，则(i)如果NODE(C)无定义，则构造一标记为C的叶结点并定义NODE(C)为这个结点；(ii)转2(2)。*2.合并已知量(1)如果NODE(B)是标记为常数的叶结点，则转2(3)；否则，转3(1)。(2)如果NODE(B)和NODE(C)都是标记为常数的叶结点，则转2(4)；否则，转3(2)。(3)执行opB(即合并已知量)。令得到的新常数为P。如果NODE(B)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P作标记的叶结点n。置NODE(P)=n，转4。(4)执行BopC(即合并已知量)。令得到的新常数为P。如果NODE(B)或NODE(C)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P作标记的叶结点n。置NODE(P)=n，转4。*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。转处理下一四元式。*例:试构造以下基本块G的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.14n13.14T0n26.28T1n3n4Rrn5+T2n6*A,B,T3,T4,T5n7T6-n8*B(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*T6T6*优化后的四元式(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*T6n13.14T0n26.28T1n3n4Rrn5+T2n6*A,B,T3,T4,T5n7T6-n8*BT6*优化后的四元式——若只有A和B是出基本块之后活跃的(1)T2:=R+r(2)A:=6.28*T2(3)T6:=R-r(4)B:=A*T6(1)S1:=R+r(2)A:=6.28*S1(3)S2:=R-r(4)B:=A*S2n13.14T0n26.28T1n3n4Rrn5+T2n6*A,B,T3,T4,T5n7T6-n8*BT6*利用DAG可以实现局部优化(1)合并已知量G’中T1和T3都变成6.28(2)删除多余运算G中T4=R+rG’T4=T2(3)删除无用赋值G中B=A在G’中不再出现G’(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*T6G(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练习设有基本块如下：T1:=3T2:=A*BT3:=9+T1M:=A*BT4:=C-DL:=T3*T4T2:=C+DN:=T2设L，M，N在基本块出口之后是活跃变量，用DAG方法给出优化后的三地址代码序列。**从DAG中还能得到其他的优化信息：在基本块外被定值并在基本块内被引用的所有标识符，就是作为叶子结点上标记的那些标识符。在基本块内被定值并且该值在基本块后面可以被引用的所有标识符，就是DAG各结点上的那些附加标识符。*10.3循环优化对循环中的代码，可以实行：代码外提强度消弱删除归纳变量(变换循环控制条件)循环展开循环合并*一、代码外提循环不变运算:对四元式A:=BopC,若B和C是常数，或者到达它们的B和C的定值点都在循环外。所谓变量A在某点d的定值到达另一点u（或称变量A的定值点d到达另一点u），是指流图中从d有一通路到达u且该通路上没有A的其它定值。d:A:=BopC…u:D:=AopE把循环不变运算提到循环体外。*入口结点循环L入口结点循环L前置结点实行代码外提，在循环入口结点前面建立一个新结点(基本块)，称为循环的前置结点，前置结点以循环入口结点为其唯一后继，原来流图中从循环外引到循环入口结点的有向边，改成引到循环前置结点。*代码外提条件forI:=1to10doA[I,2*J]:=A[I,2*J]+1*(1)I:=1(2)ifI>10goto(15)(3)T1=2*J(4)T2=10*I(5)T3=T2+T1(6)T4=addr(A)-11(7)T5=2*J(8)T6=10*I(9)T7=T6+T5(10)T8=addr(A)-11(11)T9=T8[T7](12)T4[T3]=T9+1(13)I:=I+1(14)gotoB2B3B2B1(15)(1)I:=1(2)ifI>10goto(15)(4)T2=10*I(5)T3=T2+T1(8)T6=10*I(9)T7=T6+T5(11)T9=T8[T7](12)T4[T3]=T9+1(13)I:=I+1(14)gotoB2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11B2’*(1)I:=1(2)ifX10goto(15)(3)T1=2*J(4)T2=10*I(5)T3=T2+T1(6)T4=addr(A)-11(7)T5=2*J(8)T6=10*I(9)T7=T6+T5(10)T8=addr(A)-11(11)T9=T8[T7](12)T4[T3]=T9+1(13)I:=I+1(14)gotoB2B3B2B1(15)(1)I:=1(2)ifI>10goto(15)(4)T2=10*I(5)T3=T2+T1(8)T6=10*I(9)T7=T6+T5(11)T9=T8[T7](12)T4[T3]=T9+1(13)I:=I+1(14)gotoB2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11B2’*(1)I:=1(2)ifI>10goto(15)(4)T2=10*I(5)T3=T2+T1(8)T6=10*I(9)T7=T6+T5(11)T9=T8[T7](12)T4[T3]=T9+1(13)I:=I+1(14)gotoB2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11B2’(1)I:=1(2)ifI>10goto(15)(5)T3=T2+T1(9)T7=T6+T5(11)T9=T8[T7](12)T4[T3]=T9+1(13)I:=I+1(4‘)T2=T2+10(8’)T6=T6+10(14)gotoB2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11(4)T2=10*I(8)T6=10*IB2’*(1)I:=1(2)ifI>10goto(15)(5)T3=T2+T1(9)T7=T6+T5(11)T9=T8[T7](12)T4[T3]=T9+1(13)I:=I+1(4‘)T2=T2+10(8’)T6=T6+10(14)gotoB2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11(4)T2=10*I(8)T6=10*IB2’(1)I:=1(2)ifI>10goto(15)(11)T9=T8[T7](12)T4[T3]=T9+1(13)I:=I+1(4‘)T2=T2+10(8’)T6=T6+10(5‘)T3=T3+10(9‘)T7=T7+10(14)gotoB2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11(4)T2=10*I(8)T6=10*I(5)T3=T2+T1(9)T7=T6+T5B2’*强度消弱强度消弱主要是对与归纳变量有线性关系的变量赋值进行；经过强度消弱后，循环中可能出现一些新的无用赋值；对于消弱下标变量地址计算的强度非常有效。*三、删除归纳变量如果循环中对变量I只有唯一的形如I:=IC的赋值，且其中C为循环不变量，则称I为循环中的基本归纳变量。如果I是循环中一基本归纳变量，J在循环中的定值总是可化归为I的同一线性函数，也即J=C1*IC2，其中C1和C2都是循环不变量，则称J是归纳变量，并称它与I同族。一个基本归纳变量也是一归纳变量。*(1)I:=1(2)ifI>10goto(15)(3)T1=2*J(4)T2=10*I(5)T3=T2+T1(6)T4=addr(A)-11(7)T5=2*J(8)T6=10*I(9)T7=T6+T5(10)T8=addr(A)-11(11)T9=T8[T7](12)T4[T3]=T9+1(13)I:=I+1(14)gotoB2B3B2B1(15)(1)I:=1(2)ifI>10goto(15)(4)T2=10*I(5)T3=T2+T1(8)T6=10*I(9)T7=T6+T5(11)T9=T8[T7](12)T4[T3]=T9+1(13)I:=I+1(14)gotoB2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11B2’*(1)I:=1(2)ifI>10goto(15)(11)T9=T8[T7](12)T4[T3]=T9+1(13)I:=I+1(4‘)T2=T2+10(8’)T6=T6+10(5‘)T3=T3+10(9‘)T7=T7+10(14)gotoB2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11(4)T2=10*I(8)T6=10*I(5)T3=T2+T1(9)T7=T6+T5B2’一个基本归纳变量除用于自身的递归定值外，往往只在循环中用来计算其他归纳变量以及用来控制循环进行例如：I可用于I同族的某一归纳变量来替换循环控制条件中的I，从而把I删除例如：T3是与I同族的归纳变量。且T3=10*I+T1，所以I>10和T3>100+T1等价。把ifI>10goto(15)变为：R=100+T1ifT3>Rgoto(15)*(1)I:=1(2)ifI>10goto(15)(11)T9=T8[T7](12)T4[T3]=T9+1(13)I:=I+1(4‘)T2=T2+10(8’)T6=T6+10(5‘)T3=T3+10(9‘)T7=T7+10(14)gotoB2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11(4)T2=10*I(8)T6=10*I(5)T3=T2+T1(9)T7=T6+T5B2’(1)I:=1(2)ifT3>Rgoto(15)(11)T9=T8[T7](12)T4[T3]=T9+1(5‘)T3=T3+10(9‘)T7=T7+10(14)gotoB2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11(4)T2=10*I(8)T6=10*I(5)T3=T2+T1(9)T7=T6+T5(21)R=100+T1B2’*删除归纳变量是在强度削弱以后进行的。强度削弱和删除归纳变量的统一算法框架，其步骤如下：1.利用循环不变运算信息，找出循环中所有基本归纳变量。2.找出所有其它归纳变量A，并找出A与已知基本归纳变量X的同族线性函数关系FA(X)。3.对2中找出的每一归纳变量A，进行强度削弱。4.删除对归纳变量的无用赋值。5.删除基本归纳变量如果基本归纳变量B在循环出口之后不是活跃的，并且在循环中，除在其自身的递归赋值中被引用外，只在形如ifBropYgotoL中被引用，则可选取一与B同族的归纳变量M来替换B进行条件控制。最后删除循环中对B的递归赋值的代码。*作业P306-3，4，5*第四次上机作业1.目的掌握并应用DAG方法对基本块进行优化2.内容对基本块P进行DAG优化2. 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 应用DAG优化思想，编写一个程序实现基本块优化，要求输入基本块P(文件)，输出优化后的四元式序列(直接打印在屏幕上或文件)*例如：优化前S0=2S1=3/S0S2=T-CS3=T+CK=S0/S3H=KS4=3/S1S5=T+CS6=S4/S5H=S6*S2优化后S0=2S4=2S1=1.5S2=T-CS3=T+CK=2/S3S5=S3S6=KH=S6*S2