《编译原理第9章》由会员分享，可在线阅读，更多相关《编译原理第9章（77页珍藏版）》请在金锄头文库上搜索。
1、第第9 9章章 代码优化代码优化9/18/20241目录9.1 优化技术简介优化技术简介9.2 局部优化局部优化9.3 控制流分析和循环优化控制流分析和循环优化9/18/202429.1 优化技术简介一、代码优化的目的一、代码优化的目的提高目标代码的运行效率。提高目标代码的运行效率。注：效率是指目标代码运行时间较短，占注：效率是指目标代码运行时间较短，占有空间较少。有空间较少。二、代码优化的实质二、代码优化的实质代码优化实际上是对代码进行代码优化实际上是对代码进行等价等价变变换，由一组代码变成换，由一组代码变成运行结果相同运行结果相同的另的另一组代码。一组代码。9/18/20243与机器无关的
2、优化与机器无关的优化-对中间代码进行；对中间代码进行；依赖于机器的优化依赖于机器的优化-对目标代码进行对目标代码进行三、优化阶段三、优化阶段9/18/20244四、优化分类四、优化分类 根据优化所涉及的程序范围分成根据优化所涉及的程序范围分成: :(1)(1)局部优化局部优化:(:(基本块基本块) )(2)(2)循环优化循环优化: :对循环中的代码进行优化对循环中的代码进行优化(3)(3)全局优化全局优化: :在整个程序范围内的优化在整个程序范围内的优化9/18/20245五、常用优化技术简介五、常用优化技术简介1.删除多余运算删除多余运算2.循环不变代码外提循环不变代码外提3.强度削弱强度削
3、弱4.变换循环控制条件变换循环控制条件5.合并已知量与复写传播合并已知量与复写传播6.删除无用赋值删除无用赋值9/18/20246目的：提高目标代码速度。目的：提高目标代码速度。例如：例如：P:=0for I:=1 to 20 do P:=P+AI*BI1.删除多余运算（删除公共子表达式）：删除多余运算（删除公共子表达式）：9/18/20247(1)P:=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)P:=P+T7(11)I:=I+1(12)if
4、 I=20 goto(3)(1)P:=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)P:=P+T7(11)I:=I+1(12)if I=20 goto(3)9/18/20248 减少循环中代码总数的重要办法。减少循环中代码总数的重要办法。方法：把方法：把循环不变运算循环不变运算，即其结果独立于循环执行，即其结果独立于循环执行次数的表达式提到循环的前面，使之只在循环外次数的表达式提到循环的前面，使之只在循环外计算一次。计算一次。例如：例如：P:=0f
5、or I:=1 to 20 do P:=P+AI*BI2、代码外提、代码外提9/18/20249(1)P:=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)P:=P+T7(11)I:=I+1(12)if I=20 goto(3)(1)P:=0(2)I:=1(3)T1:=4*I(5)T3:=T2T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if I=20 goto(3)(4)T2:=addr(A)-
6、4(7)T5:=addr(B)-4(6)T4:=T19/18/202410基本思想：把强度大的运算换算成强度小的。基本思想：把强度大的运算换算成强度小的。例如：例如：a) i*2 = 2*i = i+i = i1b) i/2 = (int)(i*0.5)c) 0-1 = -1d) f*2 = 2.0 * f = f + fe) f/2.0 = f*0.53.强度削弱强度削弱9/18/202411(1)P:=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(1
7、0)P:=P+T7(11)I:=I+1(12)if I=20 goto(3)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if I=20 goto(5)(3)T1:=4*I(3)T1:=T1+49/18/2024124、变换循环控制条件如果在循环体内存在一个变量如果在循环体内存在一个变量T 与循环与循环控制变量控制变量I保持线性关系，同时在循环保持线性关系，同时在循环后面不引用后面不引用I，而而除去除去I又不影响程
8、序结又不影响程序结果，则可以由果，则可以由T 取代的控制循环次数的取代的控制循环次数的作用。从循环中删除这这种方法称为作用。从循环中删除这这种方法称为变变换循环控制条件换循环控制条件，或称为，或称为删除归纳变量删除归纳变量。9/18/202413(1)P:=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)P:=P+T7(11)I:=I+1(3)T1:=T1+4(12)if I=20 goto(5)(1)P:=0(2)I:=1(4)T2:=addr(A
9、)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4 (9)T7:=T3*T6(10)P:=P+T7(3)T1:=T1+4(12)if T1 =80 goto(5)9/18/2024145、合并已知量与复写传播、合并已知量与复写传播已知量就是指常数或在编译时就能确定其值的已知量就是指常数或在编译时就能确定其值的变量。变量。若参加运算的两个对象在编译时都是已知量，若参加运算的两个对象在编译时都是已知量，则可以在编译时候直接计算出它们的运算结果，则可以在编译时候直接计算出它们的运算结果，不必等到程序运行时再计算，这种变换称为不必等
10、到程序运行时再计算，这种变换称为合合并已知量并已知量或或常数合并常数合并。复写传播复写传播是指尽量不引用那些在程序中仅仅只是指尽量不引用那些在程序中仅仅只传递信息而不改变其值，也不影响程序运行结传递信息而不改变其值，也不影响程序运行结果的变量。果的变量。通过通过复制后没有再改变的值复制后没有再改变的值可以互相替换，不可以互相替换，不会改变程序的结果会改变程序的结果。9/18/202415(1)P:=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)P
11、:=P+T7(3)T1:=T1+4(12)if T1=80 goto(5)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)(5)T3:=T2T1(6)T4:=T1(9)T7:=T3*T6(10)P:=P+T7(3)T1:=T1+4(12)if T1=80 goto(5)(3)T1:=4(8)T6:=T5T19/18/202416(1)P:=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)P:=P+T7(3)T1:=
12、T1+4(12)if T1=80 goto(5)(1)P:=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)P:=P+T7(3)T1:=T1+4(12)if T1=80 goto(5)6.删除无用赋值删除无用赋值9/18/202417局部优化：基本块内的优化局部优化：基本块内的优化9.2局部优化局部优化一、基本块一、基本块1、定义、定义程序中一个程序中一个只有一个入口和一个出口只有一个入口和一个出口的一段顺序执行的一段顺序执行的语句序列，称为程序的一个基本块。的语句序列，称为程序的一个
13、基本块。注：注：1)一个给定的程序，可以划分为一系列的基本块。一个给定的程序，可以划分为一系列的基本块。优化在各基本块中分别进行。优化在各基本块中分别进行。2)局部优化就是局限于基本块范围内的优化局部优化就是局限于基本块范围内的优化。3)在运行基本块时，只能从其入口进入，从出口退在运行基本块时，只能从其入口进入，从出口退出。出。9/18/202418a)求出各基本块的入口语句求出各基本块的入口语句对四元式程序，各个对四元式程序，各个基本块的入口语句基本块的入口语句是：是：1)程序的程序的第一个语句第一个语句；或；或2)能由条件转移语句和无条件转移语句能由条件转移语句和无条件转移语句转移到达转移
14、到达的的语句；或语句；或3)紧跟在紧跟在条件转移语句条件转移语句后面的语句。后面的语句。注：注：若条件语句由真转移和假转移两条语句组成，若条件语句由真转移和假转移两条语句组成，则跟在转移语句后面的语句是指假转移语句后面的则跟在转移语句后面的语句是指假转移语句后面的一条语句。一条语句。2、划分基本块算法、划分基本块算法9/18/202419b)根据根据入口语句，构造其所属的基本块入口语句，构造其所属的基本块一一入口语句所属的基本块入口语句所属的基本块是由该入口语是由该入口语句到句到:下一入口语句下一入口语句(不包括该入口语句不包括该入口语句);或到一转移语句或到一转移语句(包括转移语句包括转移语
15、句);或到一停或到一停(halt)语句语句(包括该语句包括该语句)之间的语句序列组成。之间的语句序列组成。C)删除不会被执行的语句删除不会被执行的语句凡是没有纳入到任何一个基本块中的语句，凡是没有纳入到任何一个基本块中的语句，都是程序控制流程所无法到达的语句，即都是程序控制流程所无法到达的语句，即不会被执行到的语句，可将其删除。不会被执行到的语句，可将其删除。9/18/202420例：求最大公因子算法 begin read X; read Y; while (X mod Y0) do begin T:=X mod Y; X:=Y; Y:=T end; write Y end(1)ReadX(2
16、)ReadY(3)T1:=XmodY(4)IfT10goto(6)(5)goto(10)(6)T:=XmodY(7)X:=Y(8)Y:=T(9)goto(3)(10)writeY(11)halt四元式序列：四元式序列：9/18/202421(1)Read X(2)Read Y(3) T1:=X mod Y(4) If T10 goto (6)(5)goto (10)(6)T:=X mod Y(7)X:=Y(8)Y:=T(9)goto (3)(10)write Y(11)halt基本块的划分：基本块的划分：9/18/202422主要是进行主要是进行已知量合并、删除公共子表达式、已知量合并、删除公
17、共子表达式、删除无用赋值。删除无用赋值。注：仅在一个基本块中，是否是注：仅在一个基本块中，是否是无用赋值无用赋值很难判很难判断。这是因为，无用赋值有以下情形：断。这是因为，无用赋值有以下情形：(a)对某变量对某变量A赋值后，在程序中没有引用；赋值后，在程序中没有引用；(b)对某变量对某变量A赋值后，在引用前又重新赋值；赋值后，在引用前又重新赋值；(c)对某变量对某变量A进行自增赋值，且它仅仅被用在进行自增赋值，且它仅仅被用在自增运算中。自增运算中。对上面第一和第三种情况，应进行全局分析。对上面第一和第三种情况，应进行全局分析。3、块内优化9/18/2024231、DAG(有向无环图有向无环图)
18、定义定义a)父子结点父子结点若在一有向图中，结点若在一有向图中，结点ni有弧指向有弧指向nj，则称则称ni是是nj的父结点，的父结点，nj是是ni的子结点。的子结点。B)路径与路径与环路环路若在一有向图中，结点若在一有向图中，结点n1n2nk间存在有间存在有向弧向弧n1n2nk,则称则称n1到到nk之间存在一之间存在一条通路，若条通路，若n1nk则该路径称为环路；则该路径称为环路；c)有向无环图有向无环图若有向图中任一路径都不是环路，则称该图若有向图中任一路径都不是环路，则称该图为无环路有向图。为无环路有向图。二、基本块的二、基本块的DAG表示表示9/18/202424a)叶结点叶结点以一以一
19、标识符标识符(变量名变量名)或常数或常数作为标记。即，该结点作为标记。即，该结点代表该变量或常数的值。代表该变量或常数的值。注：注：1)若叶结点代表变量若叶结点代表变量a的地址，则标记为的地址，则标记为addr(a)。2)通常把叶结点上作为标记的标识符加上下标通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。以表示它是该变量的初值。b)内部结点内部结点以一以一运算符运算符作为标记。即，该结点代表应用该运算作为标记。即，该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。符对其后继结点所代表的值进行运算的结果。c)附标附标：图中各个结点上可能：图中各个结点上可能附加一个或
20、多个标识符附加一个或多个标识符，表示这些标识符具有该结点所代表的值，这简称表示这些标识符具有该结点所代表的值，这简称附标附标。2、DAG结点标记或结点标记或附标附标9/18/202425例如：A:=B op C 即四元式(op,B,C,A)的DAG图为：注：注：1)图中的有向弧都省去箭头。图中的有向弧都省去箭头。2)结点结点ni是构造是构造DAG过程中给予各结点的过程中给予各结点的编号编号;3)各结点各结点下面下面的符号（运算符、变量、常数）是各结的符号（运算符、变量、常数）是各结点的标记点的标记;4)各结点各结点右边右边的标识符是结点的附标的标识符是结点的附标。n1n2n3BCAop9/18
21、/202426根据其对应结点的子结点个数，可分为根据其对应结点的子结点个数，可分为0型、型、1型、型、2型和型和3型四种类型。型四种类型。A)0型型A:=B,GOTO(S)即四元式即四元式(:=,B,_,A),其其DAG结点为结点为0型：型：n1BA3、四元式、四元式的的DAG结点类型结点类型n1S9/18/202427B)1型型A:=opB，即四元式即四元式(op,B,_,A)，其，其DAG结结点为点为1型：型：n1BAn2op9/18/202428C)2型型A:=BopC，即四元式即四元式(op,B,C,A)，其，其DAG结点为结点为2型；型；A:=BC，即四元式即四元式(=,BC,_,A
22、)，其，其DAG结点为结点为2型；型；ifBropCgoto(s)即四元式即四元式(jrop,B,C,(s)其其DAG结点为结点为2型型n1n2n3BCAopn1n2n3BCA=n1n2n3BC(s)rop9/18/202429D)3型型DC:=B即四元式即四元式(=,B,_,DC)，其，其DAG结点为结点为3型：型：n2n3n4BC=n1D9/18/202430说明：说明：大写字母（大写字母（A、B）表示四元式中变量名；表示四元式中变量名；Node(A):表示表示A在在DAG中的相应结点，其值可以为中的相应结点，其值可以为n或无定义。或无定义。N表示表示DAG中的一个结点值。中的一个结点值。
23、由基本块构造由基本块构造DAG的算法如下：的算法如下：将元表和结点表置空。将元表和结点表置空。对基本块内每个四元式对基本块内每个四元式(op,B,C,A)进行如下操作：进行如下操作：1)查元表中有无结点查元表中有无结点B，有则返回其序号，无则建有则返回其序号，无则建立该结点并返回序号；立该结点并返回序号；2)若四元式类型为若四元式类型为0型，则不做任何操作；型，则不做任何操作；4 4、基本块的、基本块的DAG构造算法构造算法9/18/2024313)若四元式类型为若四元式类型为1型型(即：即：A:=OPB)，则则IFnode(B).标记常量标记常量THEN/*叶叶*/执行执行OPB得值得值P/
24、*合并已知量合并已知量*/,若若node(B)是当前四元式建立的，就删去。是当前四元式建立的，就删去。查有无查有无node(P)结点，有就返回结点序号，结点，有就返回结点序号，没有就建立并返回其序号没有就建立并返回其序号ELSE查结点表是否有一结点，其后继为查结点表是否有一结点，其后继为node(B)，标标记记为为OP，有就返回结点序号，没有就建立并返回其序有就返回结点序号，没有就建立并返回其序号号9/18/2024324)若四元式类型为若四元式类型为2型型(即：即：A:=BOPC)，则，则，查元表中有无结点查元表中有无结点node(C),有就返回结点序号，没有就返回结点序号，没有就建立并返回
25、其序号有就建立并返回其序号;IF(node(B).标记常量标记常量)AND(node(C).标记常量标记常量)执行执行BOPC得值得值P/*合并已知量合并已知量*/若若node(B),node(C)是当前四元式建立的，就删去是当前四元式建立的，就删去;查有无结点查有无结点node(P),有就返回结点序号，没有就建有就返回结点序号，没有就建立并返回其序号立并返回其序号;ELSE查结点表是否有一结点，其左后继为查结点表是否有一结点，其左后继为node(B)且右且右后继为后继为node(C)，标记为标记为OP，有就返回结点序号，没有有就返回结点序号，没有就建立并返回其序号。就建立并返回其序号。;9/
26、18/2024335)如果如果NODE（A）无定义，则把无定义，则把A附加在结点附加在结点n上并令上并令NODE（A）n；否则先把否则先把A从从NODE（A）结点上的附加标识符集中删除（注意，如果结点上的附加标识符集中删除（注意，如果NODE（A）是叶结点，则其标记是叶结点，则其标记A不删除），把不删除），把A附加到新结点附加到新结点n上并令上并令NODE（A）n。转处理下转处理下一四元式。一四元式。9/18/202434例如：下面程序用来求圆环内外例如：下面程序用来求圆环内外圆周之和及圆环正反两面面积圆周之和及圆环正反两面面积之和。对其优化：之和。对其优化： Pi:=3.14 A:2*Pi*
27、(R+r); B:=A; B:=2* Pi*(R+r)*(R-r)由语法制导翻译生成右边的四元由语法制导翻译生成右边的四元式序列式序列(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为四元式程序段构造为四元式程序段构造DAG.9/18/202435(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(1
28、0)B:=T5*T69/18/202436(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*T69/18/202437(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*T69/18/202438(1)T0:=3.14(2)T1:=2* T0(3)T2:=R+r(4)A:=T1*T
29、2(5)B:=A(6)T3:=2* T0(7)T4:=R+r(8)T5:=T3*T4(9)T6:=R-r(10)B:=T5*T69/18/202439(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*T69/18/202440(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
30、9/18/202441(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*T69/18/202442(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*T69/18/202443(1)T0:=3.14(2)T1:=2* T0(3)T2:=R+r(4)A:=T1*T2(5)B:=A(6
31、)T3:=2* T0(7)T4:=R+r(8)T5:=T3*T4(9)T6:=R-r(10)B:=T5*T69/18/202444(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*T69/18/2024451、可做到三种优化可做到三种优化a)合并已知量合并已知量对任何一个四元式，若其中参与运算的对象均是编译对任何一个四元式，若其中参与运算的对象均是编译时的已知量，则合并已知量，并用合并后算出的常量生时的已知量，则合并已知量，并用合并后算
32、出的常量生成一个叶结点。若参与运算的已知量的叶结点是当前四成一个叶结点。若参与运算的已知量的叶结点是当前四元式建立的结果，则可删除。元式建立的结果，则可删除。b)删除对变量的前一个赋值删除对变量的前一个赋值，即删除该变量的前一个附，即删除该变量的前一个附标。标。c)检查公共子表达式检查公共子表达式对具有公共子表达式的所有四元式，只产生一个计算对具有公共子表达式的所有四元式，只产生一个计算该表达式值的内部结点，而将那些被赋值的变量附加到该表达式值的内部结点，而将那些被赋值的变量附加到该结点。该结点。三、DAG在基本块优化中的作用9/18/2024462、利用利用DAG图还原四元式序列图还原四元式
33、序列a)若为叶结点，无附标，则不生成任何四元式；若为叶结点，无附标，则不生成任何四元式；b)若为叶结点，标记为若为叶结点，标记为B，附标为附标为A，则生成则生成A:=B四元四元式；若有多个附标，则生成值为式；若有多个附标，则生成值为B的相应赋值语句四元的相应赋值语句四元式式c)若为中间结点，有附标，则根据其标记若为中间结点，有附标，则根据其标记op，生成相应生成相应四元式四元式(如如A:=BopC,A:=opB,A:=BC或或ifBropCgoto(s)；若有多个附标，则除了第一个附标用于生成相应四若有多个附标，则除了第一个附标用于生成相应四元式，其它生成值为第一个附标的赋值语句四元式元式，其
34、它生成值为第一个附标的赋值语句四元式d)若中间结点无附标，则添加一个临时附标若中间结点无附标，则添加一个临时附标SA，然后然后转转c)9/18/202447(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*T69/18/2024483、获得其它优化信息、获得其它优化信息a)在基本块外定值并在基本块内被引用的所有标识符，在基本块外定值并在基本块内被引用的所有标识符，就是作为叶结点标记的那些标识符。就是作为叶结点标记的那些标识符。b)在基本块内被在基本块内被定值定值，
35、且该值能在基本块后面被引用，且该值能在基本块后面被引用的所有标识符，就是的所有标识符，就是DAG各结点上的那些各结点上的那些附标附标。注：可利用上述信息，进一步删除四元式序列中其它注：可利用上述信息，进一步删除四元式序列中其它情况的无用赋值，如，若某结点附标，在该基本块后情况的无用赋值，如，若某结点附标，在该基本块后面不会被引用，则不生成对该附标赋值的四元式；若面不会被引用，则不生成对该附标赋值的四元式；若某结点无附标或其附标在基本块后面不会被引用，且某结点无附标或其附标在基本块后面不会被引用，且无父结点，则不生成计算该结点值的四元式；若两个无父结点，则不生成计算该结点值的四元式；若两个相邻的
36、四元式中的第一个四元式计算出来的值只在第相邻的四元式中的第一个四元式计算出来的值只在第二个四元式中被引用，则可合并这两个四元式。二个四元式中被引用，则可合并这两个四元式。9/18/202449(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(1)S1:=R+r(2)A:=6.28*s1(3)S2:=R-r(4)B:=A*S29/18/202450一、控制流分析作用一、控制流分析作用1、是数据流程分析的基础、是数据流程分析的基础2、找出程序中的循环、找出程序中
37、的循环注：注：1)循环包括循环语句构成的循环及条件循环包括循环语句构成的循环及条件转移和无条件转移构成的循环。转移和无条件转移构成的循环。2)为了为了找出程序中的循环，也需要进行找出程序中的循环，也需要进行程序程序数据流程分析。数据流程分析。9.3控制流分析和循环优化控制流分析和循环优化9/18/2024511、程序流图定义程序流图定义以以基本块基本块作为结点，作为结点，控制程序流向控制程序流向作为有向作为有向弧，画出的图，称为程序流图。弧，画出的图，称为程序流图。注；注；1)程序流图的特点是具有程序流图的特点是具有唯一首结点唯一首结点的有的有向图。所谓向图。所谓首结点首结点，是包含程序第一个
38、语句的，是包含程序第一个语句的基本块。基本块。2)从首结点沿着流图可到达任何结点。从首结点沿着流图可到达任何结点。二、程序流图与必经结点集二、程序流图与必经结点集9/18/202452程序流图程序流图（流图）（流图）：具有唯一首结点的有向图：具有唯一首结点的有向图G=（N，E，n0）N：结点集：结点集基本块集基本块集E：有向边集：有向边集n0：首结点：首结点包含程序第一个包含程序第一个语句的基本块语句的基本块程序流图三元式定义程序流图三元式定义9/18/202453有向边集的构成：有向边集的构成：满足下列条件之一时，结点满足下列条件之一时，结点I到到结点结点j有有向有有向边：边：基本块基本块j
39、在程序的位置在程序的位置紧跟紧跟在在i后后,且且i的出口的出口语句语句不是不是无条件转移无条件转移goto(S)或或停语句停语句i的出口是的出口是goto(S)或或ifgoto(S),而而(S)是是j的的入口语句入口语句9/18/202454(1) Read X(2) Read Y(3) T1:=X mod Y(4) If T1=0 goto (8)(5)X:=Y(6)Y:=T1(7)goto (3)(8)write Y(9)haltB1B2B3B4B1B2B3B4程序流图9/18/202455分析程序流图中结点间的关系分析程序流图中结点间的关系（1）m DOM n 定义定义 在程序流图中在程
40、序流图中,对任意两个结点对任意两个结点m和和n,如果从流图的如果从流图的首结点出发首结点出发,到达到达n的任意的任意通路都要经过通路都要经过m,则称则称m是是n的必经结点的必经结点,记为记为m DOM n ( a,a DOM a)（2）必经结点必经结点集集 定义定义 结点结点n的所有的所有必经结点必经结点的集合的集合,称为结称为结点点n的必经结点集的必经结点集,记为记为D(n).2、必经结点集定义9/18/2024561234657各结点的必经结点集为：各结点的必经结点集为：D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,6D(
41、7)=1,2,4,79/18/202457（3）必经结点）必经结点DOM的性质的性质自反性：自反性： a,a DOM a传递性：对流图中的任意结点传递性：对流图中的任意结点a,b和和c，若若a DOM b, b DOM c, 则有则有a DOM c。反对称性：若反对称性：若a DOM b且且 b DOM a，则则有有a=b.DOM关系是一个偏序关系。关系是一个偏序关系。9/18/2024581、基本思想基本思想根据一个结点的所有父结点的必经结点集，根据一个结点的所有父结点的必经结点集，求出该结点的必经结点集。求出该结点的必经结点集。若设结点若设结点n的父结点是的父结点是P1,P2,Pk，则，则
42、D(n)=(D(P1)D(P2) D(Pk)n2、具体实现方式具体实现方式使用迭代方法：比较相邻两次迭代结果，若使用迭代方法：比较相邻两次迭代结果，若相同，则结束。相同，则结束。三、求必经结点集算法三、求必经结点集算法9/18/2024593、算法算法设全部结点集合为设全部结点集合为N，首结点为首结点为n0，D(n0)=n0;fornN-N0doD(n):=N;/*置初值置初值*/change=TRUE;whilechange/*完成若干迭代完成若干迭代*/change=FALSE;fornN-N0do/*完成一次迭代完成一次迭代*/newd=(D(P1)D(P2)D(Pk)n;ifD(n)n
43、ewdchange=TRUE;D(n):=NEWD9/18/202460注：注：此算法中没有规定计算结点的顺序，此算法中没有规定计算结点的顺序，若顺序选的不好，效率可能很低。所以使若顺序选的不好，效率可能很低。所以使用算法之前先将流图中各结点排序，此序用算法之前先将流图中各结点排序，此序为深度为主排序。为深度为主排序。9/18/2024611、基本思想、基本思想利用必经结点集求出流图中的回边，利用回边利用必经结点集求出流图中的回边，利用回边找出流图中的循环。找出流图中的循环。2、回边定义、回边定义设设ab是流图中一条有向边，若是流图中一条有向边，若bdoma，则，则ab是流图中一条回边。是流图
44、中一条回边。注：注：1)可应用必经结点集求出流图中的回边。可应用必经结点集求出流图中的回边。2)设设nd是回边，则该回边构成的循环包括如下是回边，则该回边构成的循环包括如下结点：结点：n、d以及不经过以及不经过d能到达能到达n的所有结点。的所有结点。四、查找循环算法四、查找循环算法9/18/202462例：求出下图的所有回边例：求出下图的所有回边1234657D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,6D(7)=1,2,4,7有有6dom6,4dom7,2dom4故：故：66，74，42都是流图的都是流图的回边。回边。解：
45、首先，求出必经结点集：解：首先，求出必经结点集：9/18/2024633、查找循环的算法、查找循环的算法1)找出回边找出回边nd；2)则则n,d必定属于必定属于nd回边组成的循环回边组成的循环L中，即中，即,L:=n,d;3)若若nd且且n的父结点的父结点n不在不在L中，则中，则将它添至将它添至L中，即中，即L:=Ln;4)对对3)求出的父结点求出的父结点n重复执行重复执行3)，直至，直至不再有新结点加入不再有新结点加入L为止。为止。9/18/2024641234657回边对应的循环结点：回边对应的循环结点：667442循环结点：循环结点：6循环结点：循环结点：7,4,5,6循环结点：循环结点
46、：4,2,3,7,5,69/18/2024654、定理、定理对于对于循环循环必定满足强连通，而且只有唯一入必定满足强连通，而且只有唯一入口点。口点。注：注：1)强连通是指循环中强连通是指循环中任意两个结点都有通路任意两个结点都有通路，单结点循环也有一弧指向自身。它保证了循环单结点循环也有一弧指向自身。它保证了循环内各结点的代码都可反复执行。内各结点的代码都可反复执行。2)唯一入口点是指要到达唯一入口点是指要到达循环内任意结点必循环内任意结点必须经过此入口点须经过此入口点。它保证了循环优化时，可将。它保证了循环优化时，可将代码外提到唯一入口点前的前置结点中。代码外提到唯一入口点前的前置结点中。9
47、/18/202466五、可归约流图五、可归约流图当且仅当流图中除去当且仅当流图中除去回边外，其余的边构回边外，其余的边构成一个无环路回路，成一个无环路回路，就称流图为可归约流就称流图为可归约流图。图。左图为可归约流图。左图为可归约流图。54762139/18/202467循环优化：三种重要技术循环优化：三种重要技术代码外提：产生的结果独立于循环执行次数的代码外提：产生的结果独立于循环执行次数的表达式，放到循环前面。表达式，放到循环前面。强度削弱：把程序中执行时间较长的运算替换强度削弱：把程序中执行时间较长的运算替换为时间较短的运算。为时间较短的运算。删除归纳变量：删除归纳变量： 对形如对形如I
48、:=I+C的赋值的赋值 C为循环不变量，为循环不变量，称称I为为基本归纳变量。基本归纳变量。对形如对形如J:=C1*I+C2,C2,的赋值称的赋值称J为归纳变量为归纳变量六、六、循环优化循环优化9/18/202468（一）、代码外提（一）、代码外提1、循环不变量定义、循环不变量定义形如形如(s)A:=BopC四元式，若四元式，若(1)B、C为常量；为常量；(2)到达到达(s)点的点的B、C定值点均在循环外；定值点均在循环外；(3)到达到达(s)点的点的B、C定值点虽在循环内，但只定值点虽在循环内，但只有一个定值点且已被标为循环不变运算。有一个定值点且已被标为循环不变运算。则则(s)为循环不变运
49、算，为循环不变运算，A、B、C为循环不变量。为循环不变量。注：循环不变量不论循环执行多少次均始终保注：循环不变量不论循环执行多少次均始终保持不变，有可能外提到循环外，以提高运行速持不变，有可能外提到循环外，以提高运行速度。度。9/18/2024692、循环不变量外提条件、循环不变量外提条件a)该不变运算所在结点该不变运算所在结点(基本块基本块)必须是循必须是循环环出口结点的必经结点出口结点的必经结点或者该不变运算所或者该不变运算所定值的变量在循环出口之后是定值的变量在循环出口之后是不活跃的不活跃的；b)循环内不变运算所定值的变量只有循环内不变运算所定值的变量只有唯一唯一的一个定值点的一个定值点
50、；c)外提循环不变运算外提循环不变运算(s)A:=BopC时循环时循环内所有内所有A的引用点必须且仅是的引用点必须且仅是(s)所能到所能到达的。达的。9/18/202470 A:=5 A:=3 B:=AB1B2B3B4B5假定程序两次执行途径假定程序两次执行途径分别为：分别为：B1,B2,B4,B5,出口后出口后B=5;B1,B2,B3,B4,B5,出口后出口后B3；若若A:=3外提，则上述两条外提，则上述两条途径执行结果均为途径执行结果均为B=3。注意：其原因就是注意：其原因就是B3不是不是B4的必经结点，而且的必经结点，而且A在在出口是活跃的。出口是活跃的。前提a示例9/18/202471
51、2、循环不变量外提条件、循环不变量外提条件a)该不变运算所在结点该不变运算所在结点(基本块基本块)必须是循必须是循环出口结点的必经结点或者该不变运算所环出口结点的必经结点或者该不变运算所定值的变量在循环出口之后是不活跃的；定值的变量在循环出口之后是不活跃的；b)循环内不变运算所定值的变量只有唯一循环内不变运算所定值的变量只有唯一的一个定值点；的一个定值点；c)外提循环不变运算外提循环不变运算(s)A:=BopC时循环时循环内所有内所有A的引用点必须且仅是的引用点必须且仅是(s)所能到所能到达的。达的。9/18/202472前提前提b示例示例 A:=5 A:=3 B:=AB1B2B3B4假定程序
52、外提前执行途径为：假定程序外提前执行途径为：B1,B2,B3,B4,B2,B4,出口后出口后B=5;A:=5外提后执行相同的执行途外提后执行相同的执行途径出口后径出口后B3；注意：注意：A有两个定值点。有两个定值点。9/18/2024732、循环不变量外提条件、循环不变量外提条件a)该不变运算所在结点该不变运算所在结点(基本块基本块)必须是循必须是循环出口结点的必经结点或者该不变运算所环出口结点的必经结点或者该不变运算所定值的变量在循环出口之后是不活跃的；定值的变量在循环出口之后是不活跃的；b)循环内不变运算所定值的变量只有唯一循环内不变运算所定值的变量只有唯一的一个定值点；的一个定值点；c)
53、外提循环不变运算外提循环不变运算(s)A:=BopC时循环时循环内所有内所有A的引用点必须且仅是的引用点必须且仅是(s)所能到所能到达的。达的。9/18/202474前提c示例 A:=5 B:=A+1 A:=2B1B2B3B4假定程序外提前执行途径为：假定程序外提前执行途径为：B1,B2,B3,出口后出口后B=6;A:=2外提后执行相同的执行途外提后执行相同的执行途径出口后径出口后B3；注意：原因是注意：原因是B3当中引用的当中引用的A值值不仅不仅B4中中A的定值可到达，的定值可到达，B1中中A的定值也能到达。的定值也能到达。9/18/2024753、外提、外提算法基本思想算法基本思想寻找符合循环不变量外提条件的不变运算，寻找符合循环不变量外提条件的不变运算，进行外提。并外提到前置结点。进行外提。并外提到前置结点。4、前置结点、前置结点实行代码外提时，在循环入口结点前面建实行代码外提时，在循环入口结点前面建立一个新结点立一个新结点(基本块基本块)，即前置结点。，即前置结点。注：注：1)前置结点是唯一的，循环中外提的代前置结点是唯一的，循环中外提的代码将全部放到前置结点中。码将全部放到前置结点中。2)前置结点以循环入口结点为其唯一后继。前置结点以循环入口结点为其唯一后继。9/18/202476作业P267：4、5、79/18/202477
