学校课件编译原理第7章

1、 某些编译程序在中间代码或目标代码生某些编译程序在中间代码或目标代码生成之后要对生成的代码进行优化。成之后要对生成的代码进行优化。本章主要介绍：本章主要介绍：优化基本概念优化基本概念 基本块内的局部优化基本块内的局部优化 基于循环的优化基于循环的优化 什么是代码优化什么是代码优化 : : 对程序实施各种对程序实施各种等价变换等价变换, ,使得变换使得变换后程序能生成后程序能生成高效率高效率的目标代码。的目标代码。高效率高效率的目标代码是指的目标代码是指 : : 目标代码占用的存储空间少目标代码占用的存储空间少目标代码运行时间短目标代码运行时间短1. 1. 等价原则等价原则: : 保证等价性。保

2、证等价性。2. 2. 有效原则有效原则: : 有明显的效果。有明显的效果。3. 3. 合算原则合算原则: : 较低的代价取得较好的较低的代价取得较好的 优化效果。优化效果。代码优化的原则代码优化的原则代码优化的种类：代码优化的种类：v根据是否涉及根据是否涉及具体的计算机具体的计算机分为分为 : : 与机器有关的优化与机器有关的优化( (优化工作主要在目标代码级上进行优化工作主要在目标代码级上进行) )u 对寄存器的优化对寄存器的优化u 多处理机的优化多处理机的优化u特殊指令的优化等特殊指令的优化等与机器无关的优化与机器无关的优化 ( (优化工作主要在中间代码级上进行优化工作主要在中间代码级上进

3、行) )v根据优化对象所涉及的根据优化对象所涉及的程序范围程序范围分为分为 : : u局部优化局部优化 u循环优化循环优化 u全局优化全局优化 u局部优化局部优化 是指局限于程序基本块范围内的一种优化。是指局限于程序基本块范围内的一种优化。 局部优化包括局部优化包括: :l 合并已知量合并已知量l 删除公共子表达式删除公共子表达式( (删除多余的运算删除多余的运算) )l 删除无用赋值删除无用赋值u循环优化循环优化 是指对循环中的代码进行优化。是指对循环中的代码进行优化。 循环优化包括循环优化包括: :l 代码外提代码外提l 删除归纳变量删除归纳变量l 强度削弱强度削弱是在整个程序范围内进行的

4、优化是在整个程序范围内进行的优化, , 需需进行数据流分析进行数据流分析, , 花费代价很高。花费代价很高。u全局优化全局优化 S = 0；for ( i=1; i=20; i+ ) S = S + Ai* *Bi ； 优化处理优化处理 例例(1) S=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) S=S+T7(11) I=I+1(12) if I20 goto (3)B1B2 编译程序对其进行词法编译程序对其进行词法分析、语法分析、语

5、义分析分析、语法分析、语义分析和中间代码的生成和中间代码的生成, , 得到如得到如下一组三地址语句序列表示下一组三地址语句序列表示的中间代码：的中间代码： 在上图所示的中间代码中，根据程序在上图所示的中间代码中，根据程序流向的特点，分为流向的特点，分为B1、B2两块两块:B1是循环体外的语句序列是循环体外的语句序列B2是可重复执行的循环体语句序列是可重复执行的循环体语句序列1. 删除公共子表达删除公共子表达(删除多删除多 余运算余运算)公共子表达式是指在一个公共子表达式是指在一个基本块内计算结果相同的基本块内计算结果相同的子表达式。子表达式。对相同的子表达式只在第对相同的子表达式只在第一次出现

6、时计算且仅计算一次出现时计算且仅计算一次，将重复计算的表达一次，将重复计算的表达式删除。式删除。(1) S=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) S=S+T7(11) I=I+1(12) if I20 goto (3)B1B2 图图B2中公共子表达式中公共子表达式 4* *I 出现在四元式出现在四元式(3)和和(6)中，而从中，而从(3)到到(6)之间没有之间没有对子表达式中的变量对子表达式中的变量 I 重重新赋值，因此新赋值，

7、因此T1=T4，第，第二个二个4*I 是多余的运算，是多余的运算，可以删去，将原四元式改可以删去，将原四元式改为为 : (6) T4=T1 。 (1) S=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) S=S+T7(11) I=I+1(12) if I20 goto (3)B1B22. 代码外提代码外提 代码外提是指将循环代码外提是指将循环中的不变运算提到循环体中的不变运算提到循环体前面。前面。 图图B2中，四元式中，四元式 (4)T2

8、=addr(A) 4 (7)T5=addr(B) 4(1) S=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) S=S+T7(11) I=I+1(12) if I20 goto (3)B1B2由于由于addr(A)，addr(B)已知，已知，T2，T5的值不随的值不随循环的执行而变化，因循环的执行而变化，因此将四元式此将四元式(4)，(7)提到提到B2前面，得到下图前面，得到下图:(1) S=0(2) I=1(3) T1=4* *I(4) T2

9、=addr(A)4(5) T3=T2T1(6) T4=T1(7) T5=addr(B)4(8) T6=T5T4(9) T7=T3* *T6(10) S=S+T7(11) I=I+1(12) if I20 goto (3)B1B2(1) S=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) S=S+T7(11) I=I+1(12) if I20 goto (3)B1B23. 强度削弱强度削弱 强度削弱是指在不改变强度削弱是指在不改变运算结果的前提下

10、，将程运算结果的前提下，将程序中执行时间长的运算替序中执行时间长的运算替换成执行时间短的运算。换成执行时间短的运算。 对计算机上的二进制算对计算机上的二进制算术运算，作术运算，作加法一般比作加法一般比作乘法的速度快乘法的速度快。 图中四元式图中四元式(3)T1= 4* *I中，中，I是循环控制变量，每循环是循环控制变量，每循环一次，一次，I 增加一个步长值增加一个步长值 即即I 值加值加1 ,而而 T1的值增加的值增加4将将 (3) T1=4* *I 提到循环外提到循环外 循环体内改为循环体内改为 (3) T1= T1+ 4 得到下图。得到下图。(1) S=0(2) I=1(4) T2=add

11、r(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) S=S+T7(11) I=I+1(12) if I20 goto (3)B1B2(1) S=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) S=S+T7(11) I=I+1(12) if I20 goto (3)B1B2(1) S=0(2) I=1(4) T2=addr(A)4(7)

12、 T5=addr(B)4(3) T1=4* *I(5) T3=T2T1(6) T4=T1(8) T6=T5T4(9) T7=T3* *T6(10) S=S+T7(11) I=I+1(3) T1=T1+4(12) if I20 goto (3)B1B2(1) S=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) S=S+T7(11) I=I+1(3) T1=T1+4(12) if I20 goto (3)B1B24. 变换循环控制条件变换循环控制条

13、件 (删除归纳变量删除归纳变量) 在在B2中存在变量中存在变量 T 与循与循环控制变量环控制变量 I 保持线性关保持线性关系，则可由系，则可由T 取代取代 I , 因此因此对三地址语句对三地址语句 (12) 中的循中的循环控制条件环控制条件I 20 T180 (1) S=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) S=S+T7(11) I=I+1(3) T1=T1+4(12) if I20 goto (3)B1B2称这种变换为变换循环控制称

14、这种变换为变换循环控制条件条件,或称为删除归纳变量。或称为删除归纳变量。 变换循环控制条件后，变换循环控制条件后，三地址语句三地址语句 (11) I = I+1可可删除删除。 因为变量因为变量 I 是引用是引用 I 值来值来计算计算 I 值值, 称为对称为对 I 递归赋递归赋值值, I 称为循环中的归纳变称为循环中的归纳变量。量。 (1) S=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) S=S+T7(11) I=I+1(3) T1=T1+4

15、(12) if T180 goto (5)B1B25. 合并已知量合并已知量 已知量是指常数或在编已知量是指常数或在编译时就能确定其值的变量。译时就能确定其值的变量。 合并已知量是指若参加合并已知量是指若参加运算的两个对象在编译时运算的两个对象在编译时都是已知量，则可以在编都是已知量，则可以在编译时直接计算出它们的运译时直接计算出它们的运算结果。算结果。 图图B1中，四元式中，四元式(2) I=1，其后的两个四元式中没有其后的两个四元式中没有改变改变 I 值，这时四元式值，这时四元式 (3) T1= 4* *I 中参加运算的两个中参加运算的两个运算量均为已知运算量均为已知, 因此将因此将(3)

16、 变换为：变换为：T1=4，得到下图：，得到下图：(1) S=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) S=S+T7(11) I=I+1(3) T1=T1+4(12) if T180 goto (5)B1B2(1) S=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=T5T4(9) T7=T3* *T6(10) S=S+T7(11) I=I+

17、1(3) T1=T1+4(12) if T180 goto (5)B1B26. 复写传播复写传播 复写传播是指尽量复写传播是指尽量不引不引用那些在程序中仅仅只传递用那些在程序中仅仅只传递信息而不改变其值信息而不改变其值，也不影也不影响其运行结果的变量响其运行结果的变量。图中图中,T4 就是这样一种变量。就是这样一种变量。 (1) S=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) S=S+T7(11) I=I+1(3) T1=T1+4(12) if T

18、180 goto (5)B1B2 四元式四元式(6)T4=T1，下一个，下一个四元式四元式(8)T6=T5T4，这之，这之间间T4的值没有变化，因此将的值没有变化，因此将(8) 变换为变换为 : T6=T5T1 。 这时这时T4成为无用的赋值。成为无用的赋值。(1) S=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) S=S+T7(11) I=I+1(3) T1=T1+4(12) if T180 goto (5)B1B27. 删除无用赋值删除无用赋值

19、对赋值语句对赋值语句X=Y，若在，若在程序的任何地方都不引用程序的任何地方都不引用X，这时该语句执行与否对程这时该语句执行与否对程序运行结果没有任何作用，序运行结果没有任何作用，这种语句称为无用赋值语这种语句称为无用赋值语句，可以删除。句，可以删除。 (1) S=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) S=S+T7(3) T1=T1+4(12) if T180 goto (5)B1B2(1) S=0(2) I=1(3) T1=4* *I(4) T2=addr(A)4(5) T

20、3=T2T1(6) T4=4* *I(7) T5=addr(B)4(8) T6=T5T4(9) T7=T3* *T6(10) S=S+T7(11) I=I+1(12) if I20 goto (3)B1B2 比较优化前后的代码序列可以发现经过比较优化前后的代码序列可以发现经过优化后最终得到的代码序列具有以下特点优化后最终得到的代码序列具有以下特点: : u 减少了循环体内可执行代码，由减少了循环体内可执行代码，由10 条减至条减至6条。条。 u 减少了作乘法运算的次数，由减少了作乘法运算的次数，由3次降次降 为为1次。次。 u 减少了全程范围内使用的变量，如减少了全程范围内使用的变量，如I，

21、T4等变量。等变量。 由此可知，经过一系列优化后的代码由此可知，经过一系列优化后的代码其执行效率明显提高。当然优化工作越其执行效率明显提高。当然优化工作越多，编译系统的代价就会越大。因此，多，编译系统的代价就会越大。因此，对某种程序设计语言翻译要实施什么优对某种程序设计语言翻译要实施什么优化，就要视语言的特点具体分析，力争化，就要视语言的特点具体分析，力争设计一个最适应本语言特点的优化策略。设计一个最适应本语言特点的优化策略。 局部优化是指局限于程序基本块范围局部优化是指局限于程序基本块范围内的一种优化。内的一种优化。基本块基本块 所谓基本块是指程序中一组顺序执行所谓基本块是指程序中一组顺序执

22、行的语句序列的语句序列, ,其中其中只有一个入口语句和一个只有一个入口语句和一个出口语句出口语句。 划分基本块的方法划分基本块的方法1. 从四元式序列确定基本块的入口语句：从四元式序列确定基本块的入口语句：(1) 四元式序列的第一个语句四元式序列的第一个语句(2) 由条件转移语句或无条件转移语由条件转移语句或无条件转移语 句转移到的语句句转移到的语句(3) 紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。2. 确定基本块的出口语句：确定基本块的出口语句：(1) 下一个入口语句的前导语句下一个入口语句的前导语句(2) 转移语句转移语句(包括转移语句本身包括转移语句本身)(3) 停语句

23、停语句(包括停语句本身包括停语句本身)入口语句和出口语句之间组成一个基本块。入口语句和出口语句之间组成一个基本块。 3. 删去那些不属于任何基本块的语句，删去那些不属于任何基本块的语句， 因为控制流无法到达这些语句。因为控制流无法到达这些语句。划分基本块的方法划分基本块的方法例例 给以下四元式序列划分基本块。给以下四元式序列划分基本块。（1）read C（2）A=0（3）B=1（4）L1 : A=A+B（5）if BC goto L2（6）B=B+1（7）goto L1（8）L2 : write A（9）halt划分基本块的方法划分基本块的方法根据划分基本块的算法可以确定四元式根据划分基本块的

24、算法可以确定四元式(1)(4)(6)(8)是入口语句是入口语句; (3)(5)(7)(9)是出口语句，是出口语句，因此分为四个基本块因此分为四个基本块 （1）read C（2）A=0（3）B=1（4）L1: A=A+B（5）if BC goto L2（6） B=B+1（7） goto L1（8）L2: write A（9）halt（1）read C（2）A=0（3）B=1（4）L1 : A=A+B（5）if BC goto L2（6）B=B+1（7）goto L1（8）L2 : write A（9）halt利用利用DAG实现局部优化的思想：实现局部优化的思想： 首先对一个基本块构造一个首先对一

25、个基本块构造一个DAG( ( 无无环路有向图环路有向图 ) )，然后按构造结点的次序，然后按构造结点的次序将将DAG还原成四元式序列。还原成四元式序列。 构造构造DAG的同时已作了局部优化，那的同时已作了局部优化，那么最后得到的四元式序列已经经过了优么最后得到的四元式序列已经经过了优化。化。DAG ( DAG ( 无环路有向图无环路有向图 ) )n1n4n6n2n3n5n7n8n9 能够用来进行基本快优化的是结点能够用来进行基本快优化的是结点带有标记或附加信息的带有标记或附加信息的DAGDAG：n1Bn13.1416n1Addr(A)n3T1,T2n1Bn2COP 一个基本块由一系列四元式组成

26、，每个四一个基本块由一系列四元式组成，每个四元式都可以用相应元式都可以用相应 的的DAGDAG结点形式表式：结点形式表式：(1) A=Bn1AB(2) A= op Bn2Bn1AOP(3) A=B op Cn1Bn2Cn3Aop(4) A=BCn1Bn2Cn3A= 四元式与四元式与DAGDAG(5) if B rop C goto(S) n1Bn2Cn3(S)rop(6) DC=Bn1n2n3D C B(7) Goto (S)n1(S)四元式与四元式与DAGDAGn4构造构造DAGDAG算法算法1. 1.初始初始DAGDAG为空，无任何结点为空，无任何结点2.2.依次对基本块中的每一条中间代码

27、执行依次对基本块中的每一条中间代码执行3535操作操作3.A= B3.A= B 如果如果NODE(B) NODE(B) 没有定义，则建立叶结点，并设置没有定义，则建立叶结点，并设置标记标记B B，且让，且让NODE(B)=n NODE(B)=n 等于该结点；等于该结点；nB 如果如果A A无定义，则把无定义，则把A A附加到结点附加到结点n n上并令上并令NODE(A)=nNODE(A)=n；A 否则先把否则先把A A从从NODE(A)NODE(A)结点上的附结点上的附加标识符集中删除，加标识符集中删除， 再把再把A A附加到新结点附加到新结点n n上并令上并令NODE(A)=nNODE(A)

28、=n4 4、A=op BA=op B 如果如果NODE(B) NODE(B) 没有定义，则建立叶结点，并设置标没有定义，则建立叶结点，并设置标记记B B，且让，且让NODE(B)=n NODE(B)=n 等于该结点；等于该结点；nB 如果如果 NODE(B)NODE(B)是标记为常数的叶结点，是标记为常数的叶结点， 6.28A=-Bn -6.28p 则执行则执行 OP B(OP B(合并已知量合并已知量) )，令产生的新常数为，令产生的新常数为P P； 如果如果NODENODE（P P）无定义，则为）无定义，则为P P建立一个叶结点，标记建立一个叶结点，标记为为P P，n=NODE(P)n=N

29、ODE(P)； 如果如果NODE(B) NODE(B) 是处理当前中间是处理当前中间代码时建立的结点，则删除它。代码时建立的结点，则删除它。 如果如果A A无定义，则把无定义，则把A A附加到结点附加到结点n n上并令上并令NODE(A)=nNODE(A)=n；否则先把；否则先把A A从从NODE(A)NODE(A)结点上的附加结点上的附加标识符集中删除，再把标识符集中删除，再把A A附加到新结点附加到新结点n n上并令上并令NODE(A)=nNODE(A)=n否则，查看是否存在否则，查看是否存在OPOP的结点，的结点，nopiBA 若存在，且它有唯一若存在，且它有唯一的子结点的子结点NODE

30、(B)NODE(B)， 让让n n等于找到的结点；等于找到的结点； 如果不存在，如果不存在，则建立这样的结点，让则建立这样的结点，让n n等于建立该结点等于建立该结点5.5.对于对于A=B op CA=B op C型中间代码，型中间代码， 如果如果NODE(B)NODE(B)和和NODE(C)NODE(C)都是已知量，都是已知量， T2=R+rn3Rn4r T1=2*T0n26.28T1 如果如果NODE(B),NODE(B), NODE(C)NODE(C)没有定义，没有定义，则建立叶结点，并设置标记则建立叶结点，并设置标记B B、C C且让且让NODE(B)NODE(B)、 NODE(C)N

31、ODE(C)等于该结点；等于该结点；则执行则执行 B OP C(B OP C(合并已知量合并已知量) )，令产生的新常数为，令产生的新常数为P P；如果如果NODENODE（P P）无定义，则为）无定义，则为P P建立一个叶结点，标记为建立一个叶结点，标记为P P，n=NODE(P)n=NODE(P)；如果如果NODE(B)NODE(B)或或NODE(C)NODE(C)是处理是处理当前中间代码时建立的结点，则删除它当前中间代码时建立的结点，则删除它 若存在，且其左右子结点若存在，且其左右子结点为为NODE(B)NODE(B)，NODE(c)NODE(c)，让，让n n等于找到的结点；等于找到的

32、结点； n3n4Rrn1 +寻找公寻找公共表达共表达式式T2如果如果A A无定义，则把无定义，则把A A附加到结点附加到结点n n上并令上并令NODE(A)=nNODE(A)=n；否则先把否则先把A A从从NODE(A)NODE(A)结点上的附加标识符集中删除，结点上的附加标识符集中删除，再把再把A A附加到新结点附加到新结点n n上并令上并令NODE(A)=nNODE(A)=n下面是前面介绍的基本块的下面是前面介绍的基本块的DAGDAG生成过程生成过程删除无用删除无用赋值赋值 T2=R+r如如果不存在，则建立这样的结点，让果不存在，则建立这样的结点，让n n等于建立的结点等于建立的结点否则，

33、查看否则，查看OPOP结点，结点，n1n7n2n6n8n5n3n43.14T06.28T1Rr+T2*A ,B,T3,T4,T5-T6*BDAG 生成过程生成过程 T0=3.14 T1=2*T0 T2=R+r A=T1*T2 B=A T3=2*T0 T6=R-rB=T5*T6 T5=T3*T4 T4=R+r此时应此时应去掉去掉Bn1n7n2n6n8n5n3n43.14T06.28T1Rr+T2*A,T3,T4,T5-T6*B生成生成 DAG合并了已知量合并了已知量 为无用赋值，已删除为无用赋值，已删除 是公共子表达式是公共子表达式 T0=3.14 T1=2*T0 T2=R+r A=T1*T2

34、B=A T3=2*T0 T4=R+r T5=T3*T4 T6=R-r B=T5*T6 T0=3.14 T1=6.28 T3=6.28 T2=R+r T4=T2 A=6.28*T2 T5=A T6=R-r B=A*T6 按照构造按照构造DAG结点的顺序，结点的顺序，对每一个结点写出其相应的四元式对每一个结点写出其相应的四元式表示。表示。假设假设T0T0、T1T1、T2T2、T3T3、T4T4、T5T5、T6T6在后面的基本块中都不使用，在后面的基本块中都不使用，S1S1，S2S2为存放中间结果的临时变量。为存放中间结果的临时变量。S1=R+rA=6.28*S1S2=R-rB=A*S2在基本块中应

35、用：合并已知量、在基本块中应用：合并已知量、临时变量改名等优化技术，可将上述临时变量改名等优化技术，可将上述代码变换为：代码变换为：S1=R-rS2=R+rA=6.28*S2B=A*S1 T0=3.14 T1=6.28 T3=6.28 T2=R+r T4=T2 A=6.28*T2 T5=A T6=R-r B=A*T6 7.3 7.3 循环优化循环优化 对循环语句对循环语句, , 因为循环需要反复执行，因为循环需要反复执行，所以对循环实施优化无疑会显著提高目标所以对循环实施优化无疑会显著提高目标代码的执行效率。代码的执行效率。 循环优化包括：循环优化包括： 代码外提代码外提 强度削弱强度削弱 删

36、除归纳变量删除归纳变量 7.3.1 7.3.1 程序流图与循环程序流图与循环 一个程序的控制流程图（简称为程序一个程序的控制流程图（简称为程序流图或流图）流图或流图）G是一个三元组是一个三元组 G=(N，n0，E)。其中：。其中： 控制流程图控制流程图 N N表示流图的有限结点集，流图中每一表示流图的有限结点集，流图中每一 个结点对应程序中的一个基本块，因个结点对应程序中的一个基本块，因 此，此，N N实质上就是一个程序的基本块集。实质上就是一个程序的基本块集。 n0表示唯一的首结点，流图的首结点是表示唯一的首结点，流图的首结点是 包含程序第一个语句的基本块。包含程序第一个语句的基本块。 E表

37、示流图的有向边集。表示流图的有向边集。 7.3.1 7.3.1 程序流图与循环程序流图与循环循环查找循环查找7.3.2 7.3.2 循环查找循环查找 为了找出流图中的循环，为了找出流图中的循环，需分析流图需分析流图中结点间的控制关系。中结点间的控制关系。因此引入必经结因此引入必经结点和必经结点集的概念。点和必经结点集的概念。7.3.2 7.3.2 循环查找循环查找必经结点必经结点 在程序流图中，对任意两个结点在程序流图中，对任意两个结点a和和b，若从，若从流图的首结点出发，流图的首结点出发，到达到达a的任一通路都要经过的任一通路都要经过b，则称则称b是是a的必经结点，记为的必经结点，记为b D

38、OM a。性质：性质：（1）自反性：）自反性： 流图中任意结点流图中任意结点a,有有a DOM a（2）传递性：流图中任意结点）传递性：流图中任意结点a,b和和c,若若a DOM b和和 b DOM c,则则a DOM c（3）反对称性：若）反对称性：若a DOM b和和 b DOM a，则，则 a=b 必经结点集必经结点集 流图中结点流图中结点a的所有必经结点的集合称为结点的所有必经结点的集合称为结点a的必的必经结点集，记为经结点集，记为D(a)。一个结点的必经结点集，有以下特点：一个结点的必经结点集，有以下特点：（1）流图的首结点是图中所有结点的必经结点；）流图的首结点是图中所有结点的必经

39、结点；（2）循环的入口结点是循环中所有结点的必经结点；）循环的入口结点是循环中所有结点的必经结点；（3）每一个结点）每一个结点a的必经结点集的必经结点集D(a)=aU(a的所有前的所有前驱结点集的必经结点集的交集），驱结点集的必经结点集的交集），即即D(a)=aU(n a的的所有前驱结点集）。所有前驱结点集）。 7.3.2 7.3.2 循环查找循环查找B1B2B3B4B5B6B7B8D(B8) = B1, B2, B7, B8 流图中各结点的必经结点集：流图中各结点的必经结点集：例例D(B1) = B1D(B2) = B1, B2D(B3) = B1, B2, B3D(B4) = B1, B2

40、, B3, B4D(B5) = B1, B2, B3,B5D(B6) = B1, B2, B3, B6D(B7) = B1, B2, B7求流图中的回边求流图中的回边 设设ab是流图中的一条有向边，是流图中的一条有向边，若若b DOM a，则称，则称ab是流图中的一是流图中的一条条回边回边。7.3.2 7.3.2 循环查找循环查找流图中的回边流图中的回边： 因为因为B2 DOM B7，所以，所以B7B2是流图中的回边，是流图中的回边，且是流图中的唯一回边。且是流图中的唯一回边。 7.3.2 7.3.2 循环查找循环查找B1B2B3B4B5B6B7B8求循环的算法思想：求循环的算法思想： 回边回边n到到d组成的循环组成的循环: d是循环的入是循环的入口，口，n是循环的出口，循环出口是循环的出口，循环出口n的前