编译原理-第十章-第二部分

1、1编译原理编译原理第十章第十章 优化（第二部分）优化（第二部分）王金伟计算机与信息工程学院天津师范大学2五、五、基本块的基本块的DAGDAG表示及其应用表示及其应用1.DAG的基本概念的基本概念有向边有向边: ninj前驱：前驱：ni是是nj的前驱的前驱后继：后继： nj是是ni的后继的后继通路通路: n1n2 , n2n3 ,. ,nk-1nk环路：环路： n1=nk DAG：无环路有向图：无环路有向图(Directed Acyclic Graph)若有向图中，任何一条通路都不是环路，若有向图中，任何一条通路都不是环路，则称该有向图为无环有向图，简称则称该有向图为无环有向图，简称DAGn1n

2、2n3n4n1n2n3n410.2 10.2 局部优化局部优化32.一个基本块的一个基本块的DAG是一种带有下述标记或附加信息的是一种带有下述标记或附加信息的DAG:n13.14n3n4Rrn5+T2, T4n图的图的叶结点叶结点以一以一标识符标识符或或常数常数作为标记，表示该结点代作为标记，表示该结点代表该变量或常数的值表该变量或常数的值;n图的图的内部结点内部结点以一以一运算符运算符作为标记，作为标记，表示该结点代表应用该运算符对其表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结后继结点所代表的值进行运算的结果果;n图中各个结点上可能图中各个结点上可能附加附加一个或多个标识符一

3、个或多个标识符(称附称附加标识符加标识符)表示这些变量表示这些变量具有该结点所代表的值。具有该结点所代表的值。4n一个基本块，可用一个一个基本块，可用一个DAG来表示与各四来表示与各四元式相对应的元式相对应的DAG结点形式结点形式: 四元式四元式 DAG 图图(0) 0型型: A:=B (:=，B，-，A) n1AB3.基本块四元式与基本块四元式与DAG结点表示结点表示5四元式四元式 DAG 图图(1) 1型型: A:=op B (op，B，-，A)n1ABn2op(2) 2型型: A:=B op C (op，B，C，A)n2ABn1opn3C6四元式四元式 DAG 图图(3) 2型型: A:

4、=BC (=，BC，-，A) n2ABn1=n3C(4) 2型型: if B rop C goto (s) (jrop，B，C，(s)n2(s)Bn1ropn3C7四元式四元式 DAG 图图(5) 3型型: DC:=B (=，B，-，DC)(6) 0型型: goto (s) (j，-，-，(s)(s)n1n2Bn1=n4Cn3D8n假设假设DAG各结点信息将用某种适当的数据结构存放各结点信息将用某种适当的数据结构存放(如如链表链表)。另设置一个标识符与结点的对应函数。另设置一个标识符与结点的对应函数:否则识符是其上的标记或附加标，如果存在一个结点 nullAnn)A(Node9n0 0，1 1

5、，2 2型四元式的基本块的型四元式的基本块的DAGDAG构造算法构造算法0型型: A:=B1型型: A:=op B2型型: A:=B op C 对基本块中每一四元式，依次执行以下步骤对基本块中每一四元式，依次执行以下步骤: :1. 1. 准备操作数的结点准备操作数的结点 2. 2. 合并已知量合并已知量3. 3. 删除公共子表达式删除公共子表达式4. 4. 删除无用赋值删除无用赋值101.1.准备操作数的结点准备操作数的结点0型型: A:=B1型型: A:=op B2型型: A:=B op C n如果如果NODE(B)NODE(B)无定义，则构造一标记为无定义，则构造一标记为B B的叶结点并定

6、义的叶结点并定义NODE(B)NODE(B)为这个结点为这个结点; ;如果当前四元式是如果当前四元式是0 0型，则记型，则记NODE(B)NODE(B)的值为的值为n n，转，转4 4。如果当前四元式是如果当前四元式是1 1型，则转型，则转2(1)2(1)如果当前四元式是如果当前四元式是2 2型，则型，则(i)(i)如果如果NODE(C)NODE(C)无定义，则无定义，则构造一标记为构造一标记为C C的叶结点并定义的叶结点并定义NODE(C)NODE(C)为这个结点；为这个结点；(ii)(ii)转转2(2)2(2)。112.2.合并已知量合并已知量(1) (1) 如果如果NODE(B)NODE

7、(B)是标记为常数的叶结点，则转是标记为常数的叶结点，则转2(3)2(3)；否则，；否则，转转3(1)3(1)。(2) (2) 如果如果NODE(B)NODE(B)和和NODE(C)NODE(C)都是标记为常数的叶结点，则转都是标记为常数的叶结点，则转2(4)2(4)；否则，转；否则，转3(2)3(2)。(3) (3) 执行执行op B (op B (即合并已知量即合并已知量) )。令得到的新常数为。令得到的新常数为P P。如果。如果NODE(B)NODE(B)是处理当前四元式时新构造出来的结点，则删除是处理当前四元式时新构造出来的结点，则删除它。如果它。如果NODE(P)NODE(P)无定义

8、，则构造一用无定义，则构造一用P P作标记的叶结点作标记的叶结点n n。置置NODE(P)=nNODE(P)=n，转，转4 4。(4)(4)执行执行B op C (B op C (即合并已知量即合并已知量) )。令得到的新常数为。令得到的新常数为P P。如果。如果NODE(B)NODE(B)或或NODE(C)NODE(C)是处理当前四元式时新构造出来的结是处理当前四元式时新构造出来的结点，则删除它。如果点，则删除它。如果NODE(P)NODE(P)无定义，则构造一用无定义，则构造一用P P作标作标记的叶结点记的叶结点n n。置。置NODE(P)=nNODE(P)=n，转，转4 4。123. 3

9、. 寻找公共子表达式寻找公共子表达式(1) (1) 检查检查DAGDAG中是否已有一结点，其唯一后继为中是否已有一结点，其唯一后继为NODE(B)NODE(B)且标记为且标记为op(op(即公共子表达式即公共子表达式) )。如果没有，则构造。如果没有，则构造该结点该结点n n，否则，把已有的结点作为它的结点并设该，否则，把已有的结点作为它的结点并设该结点为结点为n n。转。转4 4。(2) (2) 检查检查DAGDAG中是否已有一结点，其左后继为中是否已有一结点，其左后继为NODE(B)NODE(B)，右后继为右后继为NODE(C)NODE(C)，且标记为，且标记为op(op(即公共子表达式即

10、公共子表达式) )。如果没有，则构造该结点如果没有，则构造该结点n n，否则，把已有的结点作，否则，把已有的结点作为它的结点并设该结点为为它的结点并设该结点为n n。转。转4 4。134.4. 删除无用赋值删除无用赋值 如果如果NODE(A)NODE(A)无定义，则把无定义，则把A A附加在结点附加在结点n n上并令上并令NODE(A)=n;NODE(A)=n;否则，先把否则，先把A A从从NODE(A)NODE(A)结点上的附加标识结点上的附加标识符集中删除符集中删除( (注意，如果注意，如果NODE(A)NODE(A)是叶结点，则其是叶结点，则其A A标标记不删除记不删除) )。把。把A

11、A附加到新结点附加到新结点n n上并置上并置NODE(A)=nNODE(A)=n。转。转处理下一四元式。处理下一四元式。14:试构造以下基本块试构造以下基本块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*T615(1) T0:=3.14n13.14T0n26.28T1n3n4Rrn5+T2n6*A, B, T3, T4, T5n7T6-n8*B(2) T1:=2*T0(3) T2:=R+r(4) A:=T

12、1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+r(8) T5:=T3*T4(9) T6:=R-r(10) B:=T5*T6T616q优化后的四元式优化后的四元式(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*BT617q优化后的四元式优化后的四元式若只有若只有A和和B是出基是出基本块之后活跃的本块之后活跃的(1)

13、 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*BT618利用利用DAG可以实现局部优化可以实现局部优化(1)合并已知量合并已知量G中中T1和和T3都变成都变成6.28(2)删除多余运算删除多余运算G中中T4=R+rGT4=T2(3)删除无用赋值删除无用赋值G中中B=A在在G中不再出现中不再出现G(1) T0:=3.14(2) T1:=6.28(3) T3

14、:=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练习n设有基本块如下：nT1:=3nT2:=A*BnT3:=9+T1nM:=A*BnT4:=C-DnL:=T3*T4nT2:=C+DnN:=T2设L，M，N在基本块出口之后是活跃变量，用DAG方法给出优化后的三地址代码序列。

15、1920n从从DAGDAG中还能得到其他的优化信息：中还能得到其他的优化信息：在基本块外被定值并在基本块内被引用的所有标识在基本块外被定值并在基本块内被引用的所有标识符，就是作为叶子结点上标记的那些标识符。符，就是作为叶子结点上标记的那些标识符。在基本块内被定值并且该值在基本块后面可以被引在基本块内被定值并且该值在基本块后面可以被引用的所有标识符，就是用的所有标识符，就是DAGDAG各结点上的那些附加标各结点上的那些附加标识符。识符。2110.3 10.3 循环优化循环优化n对循环中的代码，可以实行：对循环中的代码，可以实行：代码外提代码外提强度消弱强度消弱删除归纳变量删除归纳变量( (变换循

16、环控制条件变换循环控制条件) )循环展开循环展开循环合并循环合并 22一、一、代码外提代码外提n循环不变运算循环不变运算: : 对四元式对四元式A:=B op C,A:=B op C,若若B B和和C C是常数，或者是常数，或者到达它们的到达它们的B B和和C C的定值点都在循环外。的定值点都在循环外。n所谓变量所谓变量A A在某点在某点d d的的定值到达定值到达另一点另一点u u（或称变量（或称变量A A的定值的定值点点d d到达另一点到达另一点u u），是指流图中从），是指流图中从d d有一通路到达有一通路到达u u且该通且该通路上没有路上没有A A的其它定值。的其它定值。d d : A:

17、=B op Cu u : D:=A op En把循环不变运算提到循环体外。把循环不变运算提到循环体外。23入口结点入口结点循环循环L入口结点入口结点循环循环L前置结点前置结点实行代码外提，在循环入口结点前面建立一个新结点实行代码外提，在循环入口结点前面建立一个新结点(基本基本块块)，称为循环的，称为循环的前置结点前置结点，前置结点以循环入口结点为其，前置结点以循环入口结点为其唯一后继，原来流图中从循环外引到循环入口结点的有向边，唯一后继，原来流图中从循环外引到循环入口结点的有向边，改成引到循环前置结点。改成引到循环前置结点。24n代码外提条件代码外提条件for I:=1 to 10 doAI,

18、 2*J := AI, 2*J + 125(1)I:=1(2) if I10 goto (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= T8T7(12) T4T3= T9+1(13) I:=I+1(14) goto B2B3B2B1(15)(1)I:=1(2) if I10 goto (15)(4) T2=10*I(5) T3= T2+T1(8) T6=10*I(9) T7= T6+ T5(11) T9= T

19、8T7(12) T4T3= T9+1(13) I:=I+1(14) goto B2B3B2B1(15)(3) T1=2*J(6) T4=addr(A)-11(7) T5=2*J(10) T8=addr(A)-11B226(1)I:=1(2) if XY goto B3B1B2(3) I:=2(4) X:=X+1(5) Y:=Y-1(6) if Y=20 goto B5(7) J:=IB3B4B5循环循环L：B2，B3，B4入口结点：入口结点：B2出口结点：出口结点：B4（从该结点有一有向边引到循环外的某结点）（从该结点有一有向边引到循环外的某结点）27(1)I:=1(2) if XY goto

20、 B3B1B2(3) I:=2(4) X:=X+1(5) Y:=Y-1(6) if Y=20 goto B5(7) J:=IB3B4B5X=30, Y=25B1 B2 B4 B2 B4 B2 B4 B5J=1, I=128(3)I:=2(2) if XY goto B3B1B2(4) X:=X+1(5) Y:=Y-1(6) if Y=20 goto B5(7) J:=IB3B4B5(1)I:=1B2X=30, Y=25B1 B2 B2 B4 B2 B4 B2 B4 B5J=2, I=229不能外提的原因：不能外提的原因：B3B3不是循环出口结点不是循环出口结点B4B4的必经结点。的必经结点。代

21、码外提条件代码外提条件: :不变运算所在的结点是循环不变运算所在的结点是循环L L所有出口结点所有出口结点的必经结点的必经结点. .(1)I:=1(2) if XY goto B3B1B2(3) I:=2(4) X:=X+1(5) Y:=Y-1(6) if Y=20 goto B5(7) J:=IB3B4B530(1)I:=1(2) I:=3(2) if XY goto B3B1B2(3) I:=2(4) X:=X+1(5) Y:=Y-1(6) if Y=20 goto B5(7) J:=IB3B4B5考虑考虑: B2 B3 B4 B2 B4 B5I=3, J=331(2)I:=3(2) if

22、 XY goto B3B1B2(3)I:=2(4) X:=X+1(5) Y:=Y-1(6) if Y=20 goto B5(7) J:=IB3B4B5(1)I:=1B2考虑考虑: B2 B3 B4 B2 B4 B5I=2, J=232代码外提条件代码外提条件: 对于循环不变运算对于循环不变运算A:=B op C，只有，只有A在循在循环中其他地方未再定值环中其他地方未再定值,才能把才能把A:=B op C外提外提; (1)I:=1(2) I:=3(2) if XY goto B3B1B2(3) I:=2(4) X:=X+1(5) Y:=Y-1(6) if Y=20 goto B5(7) J:=I

23、B3B4B533考虑考虑: X=0, Y=2 B2 B3 B4 B2 B4 B5A=2, J=2(1)I:=1(2) if XY goto B3B1B2(3) A:=I+1(4) X:=X+1(5) I:=2(6) Y:=Y-1(7) if Y=0 goto B5(8) J:=AB3B4B534(5)I:=2(2) if XY goto B3B1B2(3) A:=I+1(4) X:=X+1(6) Y:=Y-1(7) if Y=20 goto B5(8) J:=AB3B4B5(1)I:=1B2考虑考虑: X=0, Y=2 B2 B3 B4 B2 B4 B5A=3, J=335S(A:=B OP

24、C)外提条件外提条件:循环中所有循环中所有A的引用点只有的引用点只有S中的中的A的定值才能到达。的定值才能到达。(1)I:=1(2) if XY goto B3B1B2(3) A:=I+1(4) X:=X+1(5) I:=2(6) Y:=Y-1(7) if Y10 goto (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= T8T7(12) T4T3= T9+1(13) I:=I+1(14) goto B2B3

25、B2B1(15)(1)I:=1(2) if I10 goto (15)(4) T2=10*I(5) T3= T2+T1(8) T6=10*I(9) T7= T6+ T5(11) T9= T8T7(12) T4T3= T9+1(13) I:=I+1(14) goto B2B3B2B1(15)(3) T1=2*J(6) T4=addr(A)-11(7) T5=2*J(10) T8=addr(A)-11B242(1)I:=1(2) if I10 goto (15)(4) T2=10*I(5) T3= T2+ T1(8) T6=10*I(9) T7= T6+ T5(11) T9= T8T7(12) T

26、4T3= T9+1(13) I:=I+1(14) goto B2B3B2B1(15)(3) T1=2*J(6) T4=addr(A)-11(7) T5=2*J(10) T8=addr(A)-11B2(1)I:=1(2) if I10 goto (15)(5) T3= T2+ T1(9) T7= T6+ T5(11) T9= T8T7(12) T4T3= T9+1(13) I:=I+1 (4) T2= T2 +10(8) T6= T6 +10(14) goto B2B3B2B1(15)(3) T1=2*J(6) T4=addr(A)-11(7) T5=2*J(10) T8=addr(A)-11(

27、4) T2=10*I(8) T6=10*IB243(1)I:=1(2) if I10 goto (15)(5) T3= T2+ T1(9) T7= T6+ T5(11) T9= T8T7(12) T4T3= T9+1(13) I:=I+1 (4) T2= T2 +10(8) T6= T6 +10(14) goto B2B3B2B1(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) if I10 goto (15)(11) T9= T8T7(12) T4T3=

28、T9+1(13) I:=I+1 (4) T2= T2 +10(8) T6= T6 +10(5) T3= T3+ 10(9) T7= T7+ 10(14) goto B2B3B2B1(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+ T5B244n强度消弱强度消弱强度消弱主要是对与强度消弱主要是对与归纳变量归纳变量有有线性关系线性关系的变量赋的变量赋值进行；值进行；经过强度消弱后，循环中可能出现一些新的无用赋经过强度消弱后，循环中可能出

29、现一些新的无用赋值；值；对于消弱下标变量地址计算的强度非常有效。对于消弱下标变量地址计算的强度非常有效。45三、三、删除归纳变量删除归纳变量n如果循环中对变量如果循环中对变量I只有唯一的形如只有唯一的形如I:=I C的赋值，且其的赋值，且其中中C为循环不变量，则称为循环不变量，则称I为循环中的为循环中的基本归纳变量基本归纳变量。n如果如果I是循环中一基本归纳变量，是循环中一基本归纳变量，J在循环中的定值总是在循环中的定值总是可化归为可化归为I的同一线性函数，也即的同一线性函数，也即J=C1*I C2，其中，其中C1和和C2都是循环不变量，则称都是循环不变量，则称J是是归纳变量归纳变量，并称它与

30、，并称它与I同同族。一个基本归纳变量也是一归纳变量。族。一个基本归纳变量也是一归纳变量。46(1)I:=1(2) if I10 goto (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= T8T7(12) T4T3= T9+1(13) I:=I+1(14) goto B2B3B2B1(15)(1)I:=1(2) if I10 goto (15)(4) T2=10*I(5) T3= T2+T1(8) T6=10*

31、I(9) T7= T6+ T5(11) T9= T8T7(12) T4T3= T9+1(13) I:=I+1(14) goto B2B3B2B1(15)(3) T1=2*J(6) T4=addr(A)-11(7) T5=2*J(10) T8=addr(A)-11B247(1)I:=1(2) if I10 goto (15)(11) T9= T8T7(12) T4T3= T9+1(13) I:=I+1 (4) T2= T2 +10(8) T6= T6 +10(5) T3= T3+ 10(9) T7= T7+ 10(14) goto B2B3B2B1(15)(3) T1=2*J(6) T4=add

32、r(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，所以所以I10和和T3100+T1等价。等价。把把if I10 goto (15)变为：变为：R=100+T1if T3R goto (15)48(1)I:=1(2) if I10 goto (15)(11) T9= T8T7(12) T4T3= T9+1(13) I:=I+1 (4) T2= T2 +10(8) T6= T6 +10(5) T3= T3+ 10(9) T7= T7+ 10(14) goto B2B3B2B1(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) T