第7章代码优化

1、编编 译译 原原 理理2022年3月17日S.PO.P语义分析、生成中间代码语义分析、生成中间代码目标代码生成目标代码生成代码优化代码优化语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理编编 译译 原原 理理2022年3月17日第第7 7章代码优化章代码优化要求明确代码优化的目的和分类要求明确代码优化的目的和分类掌握基本块的划分方法，基本块内的三种优化掌握基本块的划分方法，基本块内的三种优化方法方法掌握程序流图的构造方法，循环优化的三种优掌握程序流图的构造方法，循环优化的三种优化方法化方法教学目标教学目标编编 译译 原原 理理2022年3月17日 7.1 局

2、部优化局部优化 7.2 循环优化循环优化教学内容教学内容编编 译译 原原 理理2022年3月17日7.17.1代码优化代码优化原则：原则： 不能改变原有不能改变原有程序语义程序语义 时间效率（减少运行时间）时间效率（减少运行时间）空间效率（减少内存容量）空间效率（减少内存容量）目的：目的：提高目标代码提高目标代码运行效率运行效率 优化实质上是对代码进行优化实质上是对代码进行等价变换等价变换，变，变换后换后代码结构不同但运行结果相同代码结构不同但运行结果相同。 编编 译译 原原 理理2022年3月17日代码优化分类代码优化分类 从优化的层次，从优化的层次，与机器是否有关与机器是否有关q与机器无关

3、：与机器无关：与目标机无关，在中间代码上优化与目标机无关，在中间代码上优化q与机器有关：与机器有关：充分利用系统资源，（指令系统，寄存器）充分利用系统资源，（指令系统，寄存器） 从优化从优化涉及的范围涉及的范围局部优化：局部优化：在在基本块基本块内进行优化。内进行优化。循环优化：循环优化：对对循环语句循环语句所生成的中间代码进行优化。所生成的中间代码进行优化。全局优化：全局优化：跨越多个基本块的跨越多个基本块的全局范围内全局范围内的优化，复杂。的优化，复杂。编编 译译 原原 理理2022年3月17日7.27.2局部优化局部优化基本块：基本块：程序中一个程序中一个顺序执行顺序执行的语句序列，的语

4、句序列，即一个程序段，它只有即一个程序段，它只有一个入口一个入口和和一个出一个出口口，入口是第一条语句，出口是最后一条，入口是第一条语句，出口是最后一条语句。语句。 在一个在一个基本块上基本块上进行的优化进行的优化 编编 译译 原原 理理2022年3月17日基本块划分方法基本块划分方法 （1 1）确定各个基本块的的入口语句（基本块的第）确定各个基本块的的入口语句（基本块的第一个语句）一个语句） 语句序列的语句序列的第一个语句第一个语句是入口语句；是入口语句； 能由能由条件转移语句或无条件转移语句条件转移语句或无条件转移语句转到的语句转到的语句是入口语句；是入口语句； 紧跟在紧跟在条件转移语句或

5、无条件转移语句后面的语条件转移语句或无条件转移语句后面的语句是入口语句。句是入口语句。编编 译译 原原 理理2022年3月17日基本块划分方法基本块划分方法（2 2）对于每个入口语句，构造其所属的基本块。它）对于每个入口语句，构造其所属的基本块。它是以下三种情况之一：是以下三种情况之一： 该入口语句到该入口语句到下一条入口下一条入口语句（不包括该入口语语句（不包括该入口语句）之间的语句序列；句）之间的语句序列； 该入口语句到该入口语句到一条转移语句一条转移语句（包括该转移语句）（包括该转移语句）之间的语句序列；之间的语句序列； 该入口语句到该入口语句到一条停语句一条停语句（包括该停语句（包括该

6、停语句）之间之间的语句序列；的语句序列；（3 3）凡）凡未被纳入未被纳入某一基本块的语句，都是程序中控某一基本块的语句，都是程序中控制流程无法到达的语句，从而也是不会被执行到制流程无法到达的语句，从而也是不会被执行到的语句，将其的语句，将其删除删除。 编编 译译 原原 理理2022年3月17日【例例8.18.1】（1 1）read Xread X（2 2）read Yread Y（3 3）R=X mod YR=X mod Y（4 4）if R= =0 gotoif R= =0 goto（8 8）（5 5）X=YX=Y（6 6）Y=RY=R（7 7）gotogoto（3 3）（8 8）write

7、 Ywrite Y（9 9）halthalt编编 译译 原原 理理2022年3月17日1345620101121 FACTOR=2EXP 1=IF ( )GOTO 10 BASE=2.0FACTOR=FACTOR*2GOTO 2010. BASE=11. FACTOR20. Q=21. RETURN基本块基本块基本块基本块基本块基本块基本块基本块练习：练习：编编 译译 原原 理理2022年3月17日基本块内的优化方法基本块内的优化方法1.1.合并常量：合并常量：编译时就计算表达式中的编译时就计算表达式中的常量运算常量运算x=1x=1a=2a=2* *x+1x+1b=x+10b=x+10c=a+

8、bc=a+b（1 1）x=1x=1（2 2）a= 3a= 3（3 3）b=11b=11（4 4）c=14c=14合并常量合并常量（1 1）x=1x=1（2 2）T T1 1=2=2* *x x（3 3）a= Ta= T1 1+1+1（4 4）b=x+10b=x+10（5 5）c=a+bc=a+b四元式四元式编编 译译 原原 理理2022年3月17日基本块内的优化方法基本块内的优化方法2 2删除公共子表达式删除公共子表达式 x=ax=a* *b+cb+cy=ay=a* *b+xb+xz=az=a* *b+yb+y（1 1）T T1 1= a= a* *b b（2 2）x= Tx= T1 1+c+

9、c（3 3）y= Ty= T1 1+x+x（4 4）z=Tz=T1 1+y+y删除公共删除公共子表达式子表达式（1 1）T T1 1= a= a* *b b（2 2）x=Tx=T1 1+c+c（3 3）T T2 2= a= a* *b b（4 4）y=Ty=T2 2+x+x（5 5）T T3 3= a= a* *b b（6 6）z=Tz=T3 3+y+y四元式四元式编编 译译 原原 理理2022年3月17日基本块内的优化方法基本块内的优化方法3 3删除无用赋值删除无用赋值 （1 1）x=10+ax=10+a（2 2）y=x+by=x+b（1 1）x=1x=1（2 2）x=10+ax=10+a（

10、3 3）y=x+by=x+b编编 译译 原原 理理2022年3月17日 7.3 7.3 基本块的基本块的DAGDAG表示表示 DAG(Directed Acyclic Graph)DAG(Directed Acyclic Graph)是一种有向图，常是一种有向图，常常用来对基本块进行优化。一个基本块的常用来对基本块进行优化。一个基本块的DAGDAG是一种其是一种其结点带有下述标记或附加信息的结点带有下述标记或附加信息的DAGDAG： (1) (1) 图的叶结点图的叶结点( (无后继的结点无后继的结点) )以一标识符以一标识符( (变量名变量名) )或常数作为标记，表示该结点代表该变量或常数的值

11、。或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来表示一变量如果叶结点用来表示一变量A A的地址，则用的地址，则用addr(A)addr(A)作为作为该结点的标记。通常把叶结点上作为标记的标识符加上该结点的标记。通常把叶结点上作为标记的标识符加上下标下标0 0，以表示它是该变量的初值。，以表示它是该变量的初值。 (2) (2) 图的内部结点图的内部结点( (有后继的结点有后继的结点) )以一运算符作为以一运算符作为标记，表示该结点代表应用该运算符对其直接后继结点标记，表示该结点代表应用该运算符对其直接后继结点所代表的值进行运算的结果。所代表的值进行运算的结果。 (3) (3) 图

12、中各个结点上可能附加一个或多个标识符，图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。表示这些变量具有该结点所代表的值。编编 译译 原原 理理2022年3月17日 一个基本块由一个四元式序列组成，且一个基本块由一个四元式序列组成，且每一个四元式都可以用相应的每一个四元式都可以用相应的DAGDAG结点表示。图结点表示。图7 71 1给出了不同四元式和与其对应的给出了不同四元式和与其对应的DAGDAG结点形结点形式。图中，各结点圆圈中的式。图中，各结点圆圈中的nini是构造是构造DAGDAG过程中过程中各结点的编号，而各结点下面的符号各结点的编号，而各结点下面的符号( (

13、运算符、运算符、标识符或常数标识符或常数) )是各结点的标记，各结点右边的是各结点的标记，各结点右边的标识符是结点上的附加标识符。除了对应转移标识符是结点上的附加标识符。除了对应转移语句的结点右边可附加一语句位置来指示转移语句的结点右边可附加一语句位置来指示转移目标外，其余各类结点的右边只允许附加标识目标外，其余各类结点的右边只允许附加标识符。除对应于数组元素赋值的结点符。除对应于数组元素赋值的结点( (标记为标记为 =) =)有三个后继外，其余结点最多只有两个后继。有三个后继外，其余结点最多只有两个后继。编编 译译 原原 理理2022年3月17日n1BA(1) ABn2n1ABop(2) A

14、op Bn1Bn2Cn3opA(3) AB op Cn1Bn2Cn3 (4) AB Cn1Bn2Cn3rop(S)(5) if B rop C goto (S)n1Dn3n4(6) DCBn2 CBn1(S)(7) goto (S)图71 四元式与DAG结点编编 译译 原原 理理2022年3月17日 利用利用DAGDAG进行基本块优化的基本思想是进行基本块优化的基本思想是：首：首先按基本块内的四元式序列顺序将所有的四元先按基本块内的四元式序列顺序将所有的四元式构造成一个式构造成一个DAGDAG，然后按构造结点的次序将，然后按构造结点的次序将DAGDAG还原成四元式序列。由于在构造还原成四元式序

15、列。由于在构造DAGDAG的同时的同时已作了局部优化，所以最后所得到的是优化过已作了局部优化，所以最后所得到的是优化过的四元式序列。的四元式序列。 为了为了DAGDAG构造算法的需要，我们将图构造算法的需要，我们将图7 71 1中中的四元式按照其对应结点的后继结点个数分为的四元式按照其对应结点的后继结点个数分为四类：四类：编编 译译 原原 理理2022年3月17日 (1) 0(1) 0型四元式：后继结点个数为型四元式：后继结点个数为0 0，如图，如图7 71(1)1(1)所示；所示； (2) 1(2) 1型四元式：有一个后继结点，如图型四元式：有一个后继结点，如图7 71(2)1(2)所示；所

16、示； (3) 2(3) 2型四元式：有两个后继结点，如图型四元式：有两个后继结点，如图7 71(3)1(3)、(4)(4)、(5)(5)所示；所示； (4) (4) 3 3型四元式：有三个后继结点，如图型四元式：有三个后继结点，如图7 71(6)1(6)所示。所示。 我们规定：用大写字母我们规定：用大写字母( (如如A A、B B等等) )表示四元式中表示四元式中的变量名的变量名( (或常数或常数) )；用函数；用函数Node(A)Node(A)表示表示A A在在DAGDAG中的中的相应结点，其值可为相应结点，其值可为n n或者无定义，并用或者无定义，并用n n表示表示DAGDAG中中的一个结

17、点值。这样，每个基本块仅含的一个结点值。这样，每个基本块仅含0 0、1 1、2 2型四型四元式的元式的DAGDAG构造算法如下构造算法如下( (对基本块的每一个四元式依对基本块的每一个四元式依次执行该算法次执行该算法) )：编编 译译 原原 理理2022年3月17日 (1) (1) 若若Node(B)Node(B)无定义，则构造一标记为无定义，则构造一标记为B B的的叶结点并定义叶结点并定义Node(B)Node(B)为这个结点，然后根据下为这个结点，然后根据下列情况做不同处理：列情况做不同处理： 若当前四元式是若当前四元式是0 0型，则记型，则记Node(B)Node(B)的值为的值为n n

18、，转，转(4)(4)。 若当前四元式是若当前四元式是1 1型，则转型，则转(2)(2)。 若当前四元式是若当前四元式是2 2型，则：型，则： i. i. 如果如果Node(C)Node(C)无定义，则构造一标记为无定义，则构造一标记为C C的的叶结点，并定义叶结点，并定义Node(C)Node(C)为这个结点；为这个结点；ii. ii. 转转(2)(2)。编编 译译 原原 理理2022年3月17日 (2) (2) 若若Node(B)Node(B)是以常数标记的叶结点，是以常数标记的叶结点，则转则转(2)(2)，否则转，否则转(3)(3)。 若若Node(B)Node(B)和和Node(C)No

19、de(C)都是以常数标记的叶结点，则转都是以常数标记的叶结点，则转(2)(2)，否则转否则转(3)(3)。 执行执行op B(op B(即合并已知量即合并已知量) )，令得到的新常数为令得到的新常数为P P。若。若Node(B)Node(B)是处理当前四是处理当前四元式时新建立的结点，则删除它；若元式时新建立的结点，则删除它；若Node(P)Node(P)无无定义，则构造一用定义，则构造一用P P做标记的叶结点做标记的叶结点n n并置并置Node(P)= nNode(P)= n；转；转(4)(4)。 执行执行B op C(B op C(即合并即合并已知量已知量) )，令得到的新常数为，令得到的

20、新常数为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)。编编 译译 原原 理理2022年3月17日 (3) (3) 检查检查DAGDAG中是否有标记为中是否有标记为opop且以且以Node(B)Node(B)为惟一后继的结点为惟一后继的结点( (即查找公共子表达式即查找公共子表达式) )。若。若有，则把已有的结

21、点作为它的结点并设该结点有，则把已有的结点作为它的结点并设该结点为为n n；若没有，则构造一个新结点；转；若没有，则构造一个新结点；转(4)(4)。 检查检查DAGDAG中是否有标记为中是否有标记为opop且其左后继且其左后继为为Node(B)Node(B)、右后继为、右后继为Node(C)Node(C)的结点的结点( (即查找公即查找公共子表达式共子表达式) )。若有，则把已有的结点作为它的。若有，则把已有的结点作为它的结点并设该结点为结点并设该结点为n n；若没有，则构造一个新结；若没有，则构造一个新结点；转点；转(4)(4)。编编 译译 原原 理理2022年3月17日 (4) (4) 若

22、若Node(A)Node(A)无定义，则把无定义，则把A A附加在结点附加在结点n n上上并令并令Node(A)= nNode(A)= n；否则，先从；否则，先从Node(A)Node(A)的附加标的附加标识符集中将识符集中将A A删去删去( (注意，若注意，若Node(A)Node(A)是叶结点，是叶结点，则不能将则不能将A A删去删去) )，然后再把，然后再把A A附加到新结点附加到新结点n n上，上，并令并令Node(A)=nNode(A)=n。 解答解答 按照算法顺序处理每一四元式后构按照算法顺序处理每一四元式后构造出的造出的DAGDAG如图如图7 72 2所示，其中每一子图所示，其中

23、每一子图(1)(1)、(2)(2)、(10)(10)分别对应四元式分别对应四元式(1)(1)(10)(10)的的DAGDAG构造。构造。编编 译译 原原 理理2022年3月17日n6n1n2T0T1, T3n3n4n5n7n8B*A, T5T6T2, T4*3.146.28Rr( 10 ) BT5*T6(9) T6Rrn6n1n2T0T1, T3n3n4n5A, B, T5T2, T4*3.146.28Rr(8) T5T3*T4n6n1n2T0T1, T3n3n4n5n7A, B, T5T6T2, T4*3.146.28Rrn6n1n2T0T1, T3n3n4n5A, BT2, T4*3.14

24、6.28Rr(7) T4Rr(6) T32*T0n6n1n2T0T1n3n4n5A, BT2*3.146.28Rr(5) B An6n1n2T0T1, T3n3n4n5A, BT2*3.146.28Rrn6n1n2T0T1n3n4n5AT2*3.146.28Rr(4) T4T1*T2(3) T3Rrn1T0n1n2n3T1*3.143.142(2) T12*T0n1n2T0T1n3n4n5T23.146.28Rr6.28(1) T03.14图52 DAG编编 译译 原原 理理2022年3月17日 构造过程说明如下：构造过程说明如下： (1) (1) 对应图对应图7 72(2)2(2)，四元式，

25、四元式T1=2T1=2* *T0T0首先执首先执行算法中的步骤行算法中的步骤(1)(1)，因，因Node(B)Node(B)无定义，所以无定义，所以构造一个标记为构造一个标记为2 2的叶结点并定义的叶结点并定义Node(2)Node(2)为这为这个结点；因当前四元式是个结点；因当前四元式是2 2型且型且Node(C)Node(C)已有定已有定义义( (此时为此时为Node(T0)Node(T0)，转算法步骤，转算法步骤(2)(2)；因；因Node(B)=Node(2)Node(B)=Node(2)和和Node(C)=Node(T0)Node(C)=Node(T0)都是标记都是标记为常数的叶结点

26、，则执行为常数的叶结点，则执行B op CB op C并令新结点为并令新结点为P(=6.28)P(=6.28)；由于；由于Node(P)Node(P)无定义，故构造无定义，故构造Node(P)=Node(6.28)Node(P)=Node(6.28)； 编编 译译 原原 理理2022年3月17日 此外，因此外，因Node(B)=Node(2)Node(B)=Node(2)是处理当前四元是处理当前四元式时新构造出来的结点，故删除式时新构造出来的结点，故删除n2n2；接下来执；接下来执行算法步骤行算法步骤(4)(4)，因，因Node(A)Node(A)无定义而将无定义而将T1T1附加附加在结点在结

27、点n3n3上，并令上，并令Node(T1)=6.28Node(T1)=6.28；最后；最后DAGDAG生生成了成了2 2个结点个结点n1n1和和n3n3，因结点，因结点n2n2被删除而将被删除而将n3n3改改名为名为n2n2。图。图5 52(2)2(2)的形成过程实际上也是合并的形成过程实际上也是合并已知量的优化过程。已知量的优化过程。 (2) (2) 图图5 52(4)2(4)中中T1T1、T2T2已有定义，则仅生成已有定义，则仅生成一个新结点一个新结点n6n6并将并将A A附加在附加在n6n6上。图上。图5-2(5)5-2(5)中结中结点点B B已有定义，故直接附加在已有定义，故直接附加在

28、n6n6上。上。编编 译译 原原 理理2022年3月17日 (3) (3) 图图5 52(6)2(6)的处理过程与图的处理过程与图5 52(2)2(2)略同，略同，但在生成但在生成P P时因其已在时因其已在DAGDAG中中( (即即 Node(6.28)Node(6.28)，故不生成新结点而直接将故不生成新结点而直接将T3T3附加在结点附加在结点6.286.28上。上。 (4) (4) 图图5 52(7)2(7)的生成过程实质上是删除多余的生成过程实质上是删除多余运算运算( (删除公共子表达式删除公共子表达式) )的优化。因为的优化。因为DAGDAG中已中已有叶结点有叶结点R R与叶结点与叶结

29、点r r，并且执行，并且执行opop操作后得到操作后得到的新结点的新结点T2T2也已经在也已经在DAGDAG中，故执行算法步骤中，故执行算法步骤(4)(4)时因时因T4T4无定义而将无定义而将T4T4附加在结点附加在结点n5n5上。上。编编 译译 原原 理理2022年3月17日 (5) (5) 图图5 52(9)2(9)中，变量中，变量R R和和r r已在已在DAGDAG中有相中有相应的结点，执行应的结点，执行“”操作后，产生的新结点操作后，产生的新结点P P无定义，故仅生成一个新结点无定义，故仅生成一个新结点n7n7并将并将T6T6标记于标记于其上。其上。 (6) (6) 图图5 52(10

30、)2(10)中，对当前四元式中，对当前四元式B=T5B=T5* *T6T6，DAGDAG中已有结点中已有结点T5T5和和T6T6；执行算法步骤；执行算法步骤(4)(4)时因时因结点结点B B已有定义且不是叶结点，故先将原已有定义且不是叶结点，故先将原B B从从DAGDAG中删除，然后生成一个新结点中删除，然后生成一个新结点n8n8，将，将B B附加其上附加其上并令并令Node(B)=n8Node(B)=n8。这一处理过程实质上是删除。这一处理过程实质上是删除了无用赋值了无用赋值B=AB=A。编编 译译 原原 理理2022年3月17日 7.2.2 7.2.2 利用利用DAGDAG进行基本块的优化

31、处理进行基本块的优化处理 利用利用DAGDAG进行基本块优化处理的基本思想是：进行基本块优化处理的基本思想是：按照构造按照构造DAGDAG结点的顺序，对每一个结点写出其结点的顺序，对每一个结点写出其相应的四元式表示。相应的四元式表示。 我们根据例我们根据例5.1DAG5.1DAG结点的构造顺序，按照结点的构造顺序，按照图图7 72(10)2(10)写出四元式序列写出四元式序列GG如下：如下：编编 译译 原原 理理2022年3月17日(1) (1) T0=3.14T0=3.14(2) (2) T1=6.28T1=6.28(3) (3) T3=6.28T3=6.28(4) (4) T2=R+rT2

32、=R+r(5) (5) T4=T2T4=T2(6) (6) A=6.28A=6.28* *T2T2(7) (7) T5=AT5=A(8) (8) T6= RT6= Rr r (9) (9) B=AB=A* *T6T6编编 译译 原原 理理2022年3月17日将将GG和原基本块和原基本块G G相比，我们看到：相比，我们看到：(1) (1) G G中四元式中四元式(2)(2)和和(6)(6)都是已知量和已知量的都是已知量和已知量的运算，运算，GG已合并；已合并；(2) (2) G G中四元式中四元式(5)(5)是一种无用赋值，是一种无用赋值，GG已将它删已将它删除；除；(3) (3) G G中四元

33、式中四元式(3)(3)和和(7)(7)的的R+rR+r是公共子表达是公共子表达式式, ,GG只对它们计算了一次，即删除了多余的只对它们计算了一次，即删除了多余的R+rR+r运算。运算。因此，因此，GG是对是对G G实现上述三种优化的结果。实现上述三种优化的结果。编编 译译 原原 理理2022年3月17日 通过观察图通过观察图7 72(10)2(10)中的所有叶结点和内部中的所有叶结点和内部结点以及其上的附加标识符，还可以得出以下结点以及其上的附加标识符，还可以得出以下结论：结论： (1) (1) 在基本块外被定值并在基本块内被引用在基本块外被定值并在基本块内被引用的所有标识符就是的所有标识符就

34、是DAGDAG中相应叶结点上标记的标中相应叶结点上标记的标识符；识符； (2) (2) 在基本块内被定值且该值能在基本块后在基本块内被定值且该值能在基本块后面被引用的标识符就是面被引用的标识符就是DAGDAG各结点上的附加标识各结点上的附加标识符。符。编编 译译 原原 理理2022年3月17日 这些结论可以引导优化工作的进一步深入，这些结论可以引导优化工作的进一步深入，尤其是无用赋值的优化，也即：尤其是无用赋值的优化，也即： (1) (1) 如果如果DAGDAG中某结点上的标识符在该基本中某结点上的标识符在该基本块之后不会被引用，就可以不生成对该标识符块之后不会被引用，就可以不生成对该标识符赋

35、值的四元式。赋值的四元式。 (2) (2) 如果某结点如果某结点nini上没有任何附加标识符，上没有任何附加标识符，或者或者nini上的附加标识符在该基本块之后不会被上的附加标识符在该基本块之后不会被引用，而且引用，而且nini也没有前驱结点，这表明在基本也没有前驱结点，这表明在基本块内和基本块之后都不会引用块内和基本块之后都不会引用nini的值，那么就的值，那么就不生成计算不生成计算nini结点值的四元式。结点值的四元式。编编 译译 原原 理理2022年3月17日 (3) (3) 如果有两个相邻的四元式如果有两个相邻的四元式A=C op DA=C op D和和B=AB=A，其中第一条代码计算

36、出来的，其中第一条代码计算出来的A A值仅在第二值仅在第二个四元式中被引用，则将个四元式中被引用，则将DAGDAG中相应结点重写成中相应结点重写成四元式时，原来的两个四元式可以优化为四元式时，原来的两个四元式可以优化为B=C B=C op Dop D。 假设例假设例7.17.1中中T0T0、T1T1、T2T2、T3T3、T4T4、T5T5和和T6T6在在基本块后都不会被引用，则图基本块后都不会被引用，则图7-2(10)7-2(10)中的中的DAGDAG就可重写为如下的四元式序列：就可重写为如下的四元式序列：编编 译译 原原 理理2022年3月17日(1) (1) S1=R+r /S1=R+r

37、/* *S1S1、S2S2为存放中间结果的临时变量为存放中间结果的临时变量* */ /(2) (2) A=6.28A=6.28* *S1S1(3) (3) S2=RS2=Rr r(4) (4) B=AB=A* *S2S2编编 译译 原原 理理2022年3月17日 以上把以上把DAGDAG重写成四元式序列时，是按照原重写成四元式序列时，是按照原来构造来构造DAGDAG结点的顺序结点的顺序( (即即n5n5、n6n6、n7n7、n8)n8)依次依次进行的。实际上，我们还可以采用其它顺序进行的。实际上，我们还可以采用其它顺序( (如如自下而上自下而上) )重写，只要其中的任何一个内部结点重写，只要其

38、中的任何一个内部结点是在其后继结点之后被重写并且转移语句是在其后继结点之后被重写并且转移语句( (如果如果有的话有的话) )仍然是基本块的最后一个语句即可。仍然是基本块的最后一个语句即可。编编 译译 原原 理理2022年3月17日7.27.2循环优化循环优化首结点首结点：从它开始到有向图中任何结点都从它开始到有向图中任何结点都有一条通路的结点。有一条通路的结点。 一个一个程序流图程序流图是具有唯一首结点的有向图。是具有唯一首结点的有向图。 程序流图（控制流程图或流图程序流图（控制流程图或流图 ）：三元组三元组G=(NG=(N，E E，n n0 0) )N N：结点（基本块）集：结点（基本块）集

39、E E：边集：边集n n0 0：首结点。：首结点。编编 译译 原原 理理2022年3月17日(1) read X(2) read Y(3) R=X % Y(4) if R=0 goto (8)(5) X=Y(6) Y=R(7) goto (3)(8) write Y(9) halt(1) read X(2) read Y (3) RX%Y (4) if R0 goto(8) (5) XY (6) YR (7) goto(3) (8) write Y (9) haltB1B2B3B4图73 求最大公因子的程序流图编编 译译 原原 理理2022年3月17日 我们知道，该程序的基本块分别为：我们知道

40、，该程序的基本块分别为：(1)(2)(1)(2)，(3)(4)(3)(4)，(5)(6)(7)(5)(6)(7)和和(8)(9)(8)(9)，按构造，按构造流图结点间有向边的方法，我们得到该程序的程流图结点间有向边的方法，我们得到该程序的程序流图如图序流图如图7 73 3所示。所示。 有了程序流图，我们就可以对所要讨论的有了程序流图，我们就可以对所要讨论的循环结构给出定义。在程序流图中，我们称具有循环结构给出定义。在程序流图中，我们称具有下列性质的结点序列为一个循环：下列性质的结点序列为一个循环：编编 译译 原原 理理2022年3月17日 (1) (1) 它们是强连通的，其中任意两个结点之它们

41、是强连通的，其中任意两个结点之间必有一条通路，而且该通路上各结点都属于该间必有一条通路，而且该通路上各结点都属于该结点序列；如果序列只包含一个结点，则必有一结点序列；如果序列只包含一个结点，则必有一条有向边从该结点引到其自身。条有向边从该结点引到其自身。 (2) (2) 它们中间有一个而且只有一个是入口结它们中间有一个而且只有一个是入口结点。点。 所谓入口结点，是指序列中具有下述性质的所谓入口结点，是指序列中具有下述性质的结点：从序列外某结点有一条有向边引到它，或结点：从序列外某结点有一条有向边引到它，或者它就是程序流图的首结点。者它就是程序流图的首结点。 编编 译译 原原 理理2022年3月

42、17日 例如，对图例如，对图7 73 3所示的程序流图，由上所示的程序流图，由上述循环的定义可知，结点序列述循环的定义可知，结点序列B2B2，B3B3是是程序中的一个循环，其中，程序中的一个循环，其中，B2B2是循环的惟是循环的惟一入口结点。一入口结点。 对图对图7 74 4所示的程序流图，所示的程序流图，编编 译译 原原 理理2022年3月17日1243576图74 程序流图 结点序列结点序列6因其只有一个结点因其只有一个结点且有一有向边引到自身，并且且有一有向边引到自身，并且只有惟一的入口结点只有惟一的入口结点6，故是，故是我们所定义的循环；而我们所定义的循环；而2, 3, 4, 5, 6

43、, 7中的任意两个结点中的任意两个结点之间都存在通路之间都存在通路(即为强连通即为强连通)，且有惟一的入口结点且有惟一的入口结点2，故也是，故也是我们所定义的循环；此外，我们所定义的循环；此外，4, 5, 6, 7也是强连通且有惟一也是强连通且有惟一入口结点入口结点4，虽然到入口结点，虽然到入口结点4的的有向边不止一条，但仍然是我们有向边不止一条，但仍然是我们所定义的循环。所定义的循环。而而2, 4和和2, 3, 4，它们虽然，它们虽然是强连通的，但却存在两个入是强连通的，但却存在两个入口结点口结点2、4，故不是我们所定，故不是我们所定义的循环；义的循环；4, 5, 7和和4, 6, 7也因其

44、存在两个入口结点也因其存在两个入口结点4、7而不是我们所定义的循环。而不是我们所定义的循环。编编 译译 原原 理理2022年3月17日 7.2.2 7.2.2 循环的查栈循环的查栈 1 1必经结点集必经结点集 为了找出程序流图中的循环，需要分析流图为了找出程序流图中的循环，需要分析流图中结点的控制关系，为此我们引入必经结点和必中结点的控制关系，为此我们引入必经结点和必经结点集的定义。经结点集的定义。 在程序流图中，对任意结点在程序流图中，对任意结点m m和和n n，如果从流，如果从流图的首结点出发，到达图的首结点出发，到达n n的任一通路都要经过的任一通路都要经过m m，则称则称m m是是n

45、n的必经结点，记为的必经结点，记为m DOM nm DOM n；流图中结；流图中结点点n n的所有必经结点的集合称为结点的所有必经结点的集合称为结点n n的必经结点的必经结点集，记为集，记为D(n)D(n)。编编 译译 原原 理理2022年3月17日 显然，循环的入口结点是循环中所有结点的显然，循环的入口结点是循环中所有结点的必经结点；此外，对任何结点必经结点；此外，对任何结点n n来说都有来说都有n DOM nn DOM n。 如果把如果把DOMDOM看作流图结点集上定义的一个关看作流图结点集上定义的一个关系，则由定义容易看出它具有下述性质：系，则由定义容易看出它具有下述性质： (1) (1

46、) 自反性：对流图中任意结点自反性：对流图中任意结点a a，都有，都有a a DOM aDOM a。 (2) (2) 传递性：对流图中任意结点传递性：对流图中任意结点a a、b b、c c，若存在若存在a DOM ba DOM b和和b DOM c,b DOM c,则必有则必有a DOM ca DOM c。 (3) (3) 反对称性：若存在反对称性：若存在a DOM ba DOM b和和b DOM ab DOM a，则必有则必有a=ba=b。编编 译译 原原 理理2022年3月17日 例例7.2 7.2 求图求图7 74 4中流图各结点的中流图各结点的D(n)D(n)。 解答解答 考察图考察图

47、7 74 4的流图并由必经结点的定的流图并由必经结点的定义容易看出：首结点义容易看出：首结点1 1是所有结点的必经结点；是所有结点的必经结点；结点结点2 2是除去结点是除去结点1 1之外所有结点的必经结点；结之外所有结点的必经结点；结点点4 4是结点是结点4 4、5 5、6 6、7 7的必经结点；而结点的必经结点；而结点3 3、5 5、6 6、7 7都只是其自身的必经结点。因此，直接由定都只是其自身的必经结点。因此，直接由定义和义和DOMDOM的性质可求得：的性质可求得：编编 译译 原原 理理2022年3月17日D(1)=1D(1)=1D(2)=1D(2)=1，22D(3)=1D(3)=1，2

48、 2，33D(4)=1D(4)=1，2 2，44D(5)=1D(5)=1，2 2，4 4，55D(6)=1D(6)=1，2 2，4 4，66D(7)=1D(7)=1，2 2，4 4，771243576编编 译译 原原 理理2022年3月17日 下面我们给出求流图下面我们给出求流图G=(NG=(N，E E，n0)n0)的所有结点的所有结点n n的必经结的必经结点集点集D(n)D(n)的算法；其中，的算法；其中，P(n)P(n)代表结点代表结点n n的前驱结点集，它可的前驱结点集，它可以从边集以从边集E E中直接求出。中直接求出。 D(n0)=n0;D(n0)=n0; for (nN for (n

49、Nn0) D(n)=N; /n0) D(n)=N; /* *置初值置初值* */ / change=true; change=true; while (change) while (change) change=false; change=false; for (nN for (nNn0)n0) m mi i P(n) new=n P(n) new=nD(mD(m1 1)D(m)D(m2 2) D(m) D(m3 3) ) if (new!=D(n) if (new!=D(n) change=true; change=true; D(n)=new; D(n)=new; 编编 译译 原原 理理2

50、022年3月17日nink1nk2nknnj图75 ni为nj的必经结点示意 编编 译译 原原 理理2022年3月17日例例7.3 7.3 应用求流图必经结点集的应用求流图必经结点集的算法求图算法求图7 74 4流图各结点流图各结点n n的的D(n)D(n)。 解答解答 算法求解过程如下：算法求解过程如下： 首先置初值：首先置初值： D(1)=1D(1)=1 D(2)=D(3)=D(4)=D(5)=D(6)=D(7)D(2)=D(3)=D(4)=D(5)=D(6)=D(7) =1,2,3,4,5,6,7=1,2,3,4,5,6,7 置置changechange为为falsefalse，然后从结

51、点，然后从结点2 2到结点到结点7 7依次执行第二个依次执行第二个forfor循环。循环。1243576编编 译译 原原 理理2022年3月17日对结点对结点2 2，因，因 new=2D(1)D(4)new=2D(1)D(4)=211,2,3,4,5,6,7=211,2,3,4,5,6,7=21=1,2=21=1,2但迭代前但迭代前D(2)=1,2,3,4,5,6,7D(2)=1,2,3,4,5,6,7，故故D(2)newD(2)new，因此置，因此置change=truechange=true并令并令D(2)=1,2D(2)=1,2。对结点对结点3 3，因，因 new=3D(2)=31,2=

52、1,2,new=3D(2)=31,2=1,2,33但迭代前但迭代前D(3)=1,2,3,4,5,6,7D(3)=1,2,3,4,5,6,7，故故D(3) newD(3) new，因此令，因此令D(3)=1D(3)=1，2 2，33。其余各结点按照上述步骤可求出：其余各结点按照上述步骤可求出：D(4)=4D(2)D(3)D(7)=4D(4)=4D(2)D(3)D(7)=41,21,2,31,2,3,4,5,6,1,21,2,31,2,3,4,5,6,7=1,2,47=1,2,41243576编编 译译 原原 理理2022年3月17日D(5)=5D(4)=1,2,4,5D(5)=5D(4)=1,2

53、,4,5D(6)=6D(4)=1,2,4,6D(6)=6D(4)=1,2,4,6D(7)=7D(5)D(6)=7D(7)=7D(5)D(6)=71,2,4,51,2,4,6=1,1,2,4,51,2,4,6=1,2,4,72,4,7一次迭代完毕后，因一次迭代完毕后，因changechange为为truetrue，故还要进行下一次，故还要进行下一次迭代。迭代。先令先令changechange为为falsefalse，然后继，然后继续从结点续从结点2 2到结点到结点7 7依次执行依次执行第二个第二个forfor循环。循环。对结点对结点2 2，因，因 new=2D(1)D(4) new=2D(1)D

54、(4) =211,2,4=211,2,4=21=1,2=21=1,21243576编编 译译 原原 理理2022年3月17日 而迭代前而迭代前D(2)=1,2D(2)=1,2，所，所以以D(2)=newD(2)=new，故，故D(2)D(2)不变。不变。 对结点对结点3 3，因，因 new=3D(2) new=3D(2) =31,2=1,2,3=31,2=1,2,3 及迭代前及迭代前D(3)=1,2,3D(3)=1,2,3，所以所以D(3)=newD(3)=new，故，故D(3)D(3)不变。不变。对其余结点对其余结点n(n=4n(n=47)7)求出的求出的newnew均有均有D(n)=new

55、D(n)=new，所以第二，所以第二次迭代后次迭代后changechange为为falsefalse，迭，迭代结束，第一次迭代求出的代结束，第一次迭代求出的各个各个D(n)D(n)就是最后的结果。就是最后的结果。1243576编编 译译 原原 理理2022年3月17日 2 2回边回边 查找循环的方法是：首先应用必经结点集来查找循环的方法是：首先应用必经结点集来求出流图中的回边，然后利用回边找出流图中的求出流图中的回边，然后利用回边找出流图中的循环的。循环的。 回边的定义如下：假设回边的定义如下：假设abab是流图中一条有是流图中一条有向边，如果向边，如果b DOM ab DOM a，则称，则称

56、abab是流图中的一条是流图中的一条回边。回边。 对于一已知流图对于一已知流图G G，只要求出各结点，只要求出各结点n n的必经的必经结点集，就可以立即求出流图中的所有回边。在结点集，就可以立即求出流图中的所有回边。在求出流图求出流图G G中的所有回边后，就可以求出流图中中的所有回边后，就可以求出流图中的循环。如果已知有向边的循环。如果已知有向边ndnd是一条回边，则由是一条回边，则由它组成的循环就是由结点它组成的循环就是由结点d d、结点、结点n n以及有通路到以及有通路到达达n n 但该通路不经过但该通路不经过d d的所有结点组成的。的所有结点组成的。编编 译译 原原 理理2022年3月1

57、7日例例7.4 7.4 求出图求出图7 74 4流图的所有流图的所有回边。回边。 解答解答 (1) (1) 已知已知D(6)=1,2,4,6D(6)=1,2,4,6，因存在因存在6666且且6 DOM 66 DOM 6，故，故6666是回边；是回边； (2) (2) 已知已知D(7)=1,2,4,7D(7)=1,2,4,7，因存在因存在7474且且4 DOM 74 DOM 7，故，故7474是回边；是回边； (3) (3) 已知已知D(4)=1,2,4D(4)=1,2,4，因，因存在存在4242且且2 DOM 42 DOM 4，故，故4242是是回边。容易看出，其它有向边回边。容易看出，其它有

58、向边都不是回边。都不是回边。1243576编编 译译 原原 理理2022年3月17日寻找由回边组成循环的算法如下：寻找由回边组成循环的算法如下：main (main () ) stack= stack=空空;/;/* *stackstack是一个工作栈是一个工作栈* */ / loop=d;/ loop=d;/* *looploop是所求的循环是所求的循环* */ / insert(m); insert(m); while (stack while (stack非空非空) ) 弹出弹出stackstack栈顶元素栈顶元素m;m; for (pP(m) / for (pP(m) /* *P(m)

59、P(m)为结点为结点m m的前驱结点集的前驱结点集* */ / insert (p); insert (p); void insert (m)void insert (m) if (m if (mloop) loop) loop=loopm; loop=loopm; 把把m m压入栈压入栈stack;stack; 1243576编编 译译 原原 理理2022年3月17日 此算法在求回边此算法在求回边ndnd组组成循环的所有结点的方法是：成循环的所有结点的方法是：由于循环以由于循环以d d为其惟一入口，为其惟一入口，n n是循环的一个出口，只要是循环的一个出口，只要n n不同时是循环入口不同时是

60、循环入口d d，那么，那么n n的所有前驱就应属于循环。的所有前驱就应属于循环。在求出在求出n n的所有前驱之后，的所有前驱之后，只要它们不是循环入口只要它们不是循环入口d d，就应再继续求出它们的前驱，就应再继续求出它们的前驱，而这些新求出的所有前驱也而这些新求出的所有前驱也应属于循环。然后再对新求应属于循环。然后再对新求出的所有前驱重复上述过程，出的所有前驱重复上述过程，直到所求出的前驱都是直到所求出的前驱都是d d为为止。止。1243576编编 译译 原原 理理2022年3月17日 3 3可归约流图可归约流图 一个流图被称为可归一个流图被称为可归约的，当且仅当流图中约的，当且仅当流图中除