第11章 代码优化

1、 11.1 11.1 优化技术简介优化技术简介 11.2 11.2 局部优化局部优化 11.3 11.3 控制流分析和循环优化控制流分析和循环优化第十一章第十一章 代码优化代码优化11.1 优化技术简介优化技术简介一、优化的原则一、优化的原则1 1、等价原则、等价原则优化后不改变原程序运行的功能。优化后不改变原程序运行的功能。2 2、有效原则、有效原则优化后产生的目标代码运行时间较短，占用空优化后产生的目标代码运行时间较短，占用空间较小。间较小。与机器无关的优化与机器无关的优化-中间代码优化。中间代码优化。依赖于机器的优化依赖于机器的优化-目标代码优化。目标代码优化。二、优化阶段二、优化阶段源

2、代码源代码中间代码中间代码目标代码目标代码中间代码优化中间代码优化目标代码优化目标代码优化三、优化分类三、优化分类(1)(1)局部优化局部优化:(:(基本块基本块) )(2)(2)循环优化循环优化: :对循环中的代码进行优化对循环中的代码进行优化(3)(3)全局优化全局优化: :在整个程序范围内的优化在整个程序范围内的优化四、常用优化技术简介四、常用优化技术简介1.1.删除多余运算删除多余运算2.2.循环不变代码外提循环不变代码外提3.3.强度削弱强度削弱4.4.变换循环控制条件变换循环控制条件5.5.合并已知量与复写传播合并已知量与复写传播6.6.删除无用赋值删除无用赋值例如：例如：（假设数

3、组元素占用空间为（假设数组元素占用空间为4 4个字节）个字节）P:=0P:=0for I:=1 to 20 dofor I:=1 to 20 do P:=P+AI P:=P+AI* *BIBI1.1.删除多余运算（删除公共子表达式）：删除多余运算（删除公共子表达式）：目的：提高目标代码速度。目的：提高目标代码速度。(6)T(6)T4 4:=:=4 4* *I I(7)T(7)T5 5:=addr(B):=addr(B)(8)T(8)T6 6:=T:=T5 5TT4 4 (9)T(9)T7 7:=T:=T3 3* *T T6 6(10)P:=P+T(10)P:=P+T7 7(11)I:=I+1(

4、11)I:=I+1(12)if I=20 goto(3)(12)if I=20 goto(3)(1)P:=0(1)P:=0(2)I:=0(2)I:=0(3)T(3)T1 1:=4:=4* *I I(4)T(4)T2 2:=addr(A):=addr(A)(5)T(5)T3 3:=T:=T2 2TT1 1 (7)T(7)T5 5:=addr(B):=addr(B)(8)T(8)T6 6:=T:=T5 5TT4 4 (9)T(9)T7 7:=T:=T3 3* *T T6 6(10)P:=P+T(10)P:=P+T7 7(11)I:=I+1(11)I:=I+1(12)if I=20 goto(3)(

5、12)if I=20 goto(3)(6)T(6)T4 4:=T1:=T1变址取数变址取数(1)P:=0(1)P:=0(2)I:=0(2)I:=0(3)T(3)T1 1:=4:=4* *I I(4)T(4)T2 2:=addr(A):=addr(A)(5)T(5)T3 3:=T:=T2 2TT1 1 目的：减少循环中代码总数。目的：减少循环中代码总数。方法：把循环不变运算，即其结果独立于循环方法：把循环不变运算，即其结果独立于循环执行次数的表达式提到循环的前面，使之只执行次数的表达式提到循环的前面，使之只在循环外计算一次。在循环外计算一次。2 2、代码外提、代码外提(1)P:=0(1)P:=0

6、(2)I:=0(2)I:=0(3)T(3)T1 1:=4:=4* *I I(4)T(4)T2 2:=addr(A):=addr(A)(5)T(5)T3 3:=T:=T2 2TT1 1 (6)T(6)T4 4:=T1:=T1(7)T(7)T5 5:=addr(B):=addr(B)(8)T(8)T6 6:=T5T4:=T5T4(9)T(9)T7 7:=T:=T3 3* *T T6 6(10)P:=P+T(10)P:=P+T7 7(11)I:=I+1(11)I:=I+1(12)if I=20 (12)if I=20 goto(3)goto(3)(1)P:=0(1)P:=0(2)I:=0(2)I:=

7、0(3)T(3)T1 1:=4:=4* *I I(5)T(5)T3 3:=T2T1:=T2T1(6)T4:=T1(6)T4:=T1(8)T(8)T6 6:=T5T4:=T5T4(9)T(9)T7 7:=T:=T3 3* *T T6 6(10)P:=P+T(10)P:=P+T7 7(11)I:=I+1(11)I:=I+1(12)if I=20 goto(3)(12)if I=20 goto(3)(4)T2:=addr(A)(4)T2:=addr(A)(7)T5:=addr(B)(7)T5:=addr(B)基本思想：把强度大的运算换算成强度小的。基本思想：把强度大的运算换算成强度小的。例如：例如：

8、a) ia) i* *2 = 22 = 2* *i = i+ii = i+ib) 0-1 = -1b) 0-1 = -1c) f/2.0 = fc) f/2.0 = f* *0.50.53.3.强度削弱强度削弱(1)P:=0(1)P:=0(2)I:=0(2)I:=0(4)T(4)T2 2:=addr(A):=addr(A)(7)T(7)T5 5:=addr(B):=addr(B)(3)T(3)T1 1:=4:=4* *I I(5)T(5)T3 3:=T2T1:=T2T1(6)T(6)T4 4:=T1:=T1(8)T(8)T6 6:=T5T4:=T5T4(9)T(9)T7 7:=T:=T3 3*

9、 *T T6 6(10)P:=P+T(10)P:=P+T7 7(11)I:=I+1(11)I:=I+1(12)if I=20 goto(3)(12)if I=20 goto(3) (1)P:=0 (1)P:=0 (2)I:=0 (2)I:=0 (4)T (4)T2 2:=addr(A):=addr(A) (7)T (7)T5 5:=addr(B):=addr(B) (5)T (5)T3 3:=T:=T2 2TT1 1 (6)T (6)T4 4:=T:=T1 1 (8)T (8)T6 6:=T:=T5 5TT4 4 (9)T (9)T7 7:=T:=T3 3* *T T6 6 (10)P:=P+

10、T (10)P:=P+T7 7 (11)I:=I+1 (11)I:=I+1 (12)if I=20 goto(5) (12)if I=20 goto(5)(3)T1:=4(3)T1:=4* *I I(3(3)T)T1 1:=T:=T1 1+4+44 4、变换循环控制条件、变换循环控制条件 经过变换后，有些变量不被引用，可以从循经过变换后，有些变量不被引用，可以从循环中删除。环中删除。(1)P:=0(1)P:=0(2)I:=0(2)I:=0(4)T(4)T2 2:=addr(A):=addr(A)(7)T(7)T5 5:=addr(B):=addr(B)(3)T(3)T1 1:=4:=4* *I

11、 I(5)T(5)T3 3:=T:=T2 2TT1 1 (6)T(6)T4 4:=T:=T1 1(8)T(8)T6 6:=T:=T5 5TT4 4 (9)T(9)T7 7:=T:=T3 3* *T T6 6(10)P:=P+T(10)P:=P+T7 7(11)I:=I+1(11)I:=I+1(3(3)T1:=T1+4)T1:=T1+4(12)if (12)if I=20I=20 goto(5) goto(5)(1)P:=0(1)P:=0(2)I:=1(2)I:=1(4)T(4)T2 2:=addr(A):=addr(A)(7)T(7)T5 5:=addr(B):=addr(B)(3)T(3)T

12、1 1:=4:=4* *I I(5)T(5)T3 3:=T:=T2 2TT1 1 (6)T(6)T4 4:=T:=T1 1(8)T(8)T6 6:=T:=T5 5T4 T4 (9)T(9)T7 7:=T:=T3 3* *T T6 6(10)P:=P+T(10)P:=P+T7 7(3(3)T)T1 1:=T:=T1 1+4+4(12)if goto(5)(12)if goto(5)T1 =80T1 =805 5、合并已知量与复写传播、合并已知量与复写传播 编码时的已知量编码时的已知量常数，可在编译时计算常数，可在编译时计算出它的值，这种变换称为出它的值，这种变换称为合并已知量合并已知量或或常常数

13、合并数合并。 通过复制后没有再改变的值可以互相替换，通过复制后没有再改变的值可以互相替换，不会改变程序的结果，这种变换称为不会改变程序的结果，这种变换称为复写复写传播。传播。(1)P:=0(1)P:=0(2)I:=0(2)I:=0(4)T(4)T2 2:=addr(A):=addr(A)(7)T(7)T5 5:=addr(B):=addr(B)(3) T(3) T1 1:=4:=4* *I I(5)T(5)T3 3:=T:=T2 2TT1 1 (6)T(6)T4 4:=T:=T1 1(8)T(8)T6 6:=T:=T5 5TT4 4 (9)T(9)T7 7:=T:=T3 3* *T T6 6(

14、10)P:=P+T(10)P:=P+T7 7(3(3)T)T1 1:=T:=T1 1+4+4(12)if T(12)if T1 1=80 goto(5)=80 goto(5)(1)P:=0(1)P:=0(2)I:=0(2)I:=0(4)T(4)T2 2:=addr(A):=addr(A)(7)T(7)T5 5:=addr(B):=addr(B)(5)T(5)T3 3:=T:=T2 2TT1 1 (6)T(6)T4 4:=T:=T1 1(9)T(9)T7 7:=T:=T3 3* *T T6 6(10)P:=P+T(10)P:=P+T7 7(3(3)T)T1 1:=T:=T1 1+4+4(12)i

15、f T(12)if T1 1=80 goto(5)=80 goto(5)(3)T(3)T1 1:=0:=0(8)T(8)T6 6:=T:=T5 5TT1 1 (1)P:=0(1)P:=0(2)I:=0(2)I:=0(4)T(4)T2 2:=addr(A):=addr(A)(7)T(7)T5 5:=addr(B):=addr(B)(3)T(3)T1 1:=0:=0(5)T(5)T3 3:=T:=T2 2TT1 1 (6)T(6)T4 4:=T:=T1 1(8)T(8)T6 6:=T:=T5 5T1T1(9)T(9)T7 7:=T:=T3 3* *T T6 6(10)P:=P+T(10)P:=P+

16、T7 7(3(3)T)T1 1:=T:=T1 1+4+4(12)if T(12)if T1 1=80 goto(5)=80 goto(5)(1)P:=0(1)P:=0(4)T(4)T2 2:=addr(A):=addr(A)(7)T(7)T5 5:=addr(B):=addr(B)(3)T(3)T1 1:=0:=0(5)T(5)T3 3:=T:=T2 2TT1 1 (8)T(8)T6 6:=T:=T5 5TT1 1 (9)T(9)T7 7:=T:=T3 3* *T T6 6(10)P:=P+T(10)P:=P+T7 7(3(3)T)T1 1:=T:=T1 1+4+4(12)if T(12)if

17、 T1 1=80 goto(5)=80 goto(5)6.6.删除无用赋值删除无用赋值11.211.2局部优化局部优化一、基本块一、基本块1 1、定义、定义 程序中一个只有一个入口和一个出口的一段顺程序中一个只有一个入口和一个出口的一段顺序执行的语句序列，称为程序的一个基本块。序执行的语句序列，称为程序的一个基本块。注：注：1)1)一个给定的程序，可以划分为一系列的基本一个给定的程序，可以划分为一系列的基本块。优化在各基本块中分别进行块。优化在各基本块中分别进行( (局部优化局部优化) )。 2)2)在运行基本块时，只能从其入口进入，从出在运行基本块时，只能从其入口进入，从出口退出。口退出。a

18、)a)求出各基本块的入口语句求出各基本块的入口语句 对四元式程序，各个对四元式程序，各个基本块的入口语句基本块的入口语句是：是： 1)1)程序的第一个语句程序的第一个语句 ； 2)2)能由条件转移语句和无条件转移语句转移到能由条件转移语句和无条件转移语句转移到达的语句；达的语句； 3)3)紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。2 2、划分基本块算法、划分基本块算法b)b)根据根据入口语句，构造其所属的基本块入口语句，构造其所属的基本块 一入口语句所属的基本块是由该入口语句到一入口语句所属的基本块是由该入口语句到下一入口语句下一入口语句( (不包括该入口语句不包括该入口语句

19、) )、或到一转、或到一转移语句移语句( (包括转移语句包括转移语句) )、或到一停、或到一停(halt)(halt)语句语句( (包括该语句包括该语句) )之间的语句序列组成。之间的语句序列组成。 C)C)删除不会被执行的语句删除不会被执行的语句 凡是没有纳入到任何一个基本块中的语句，凡是没有纳入到任何一个基本块中的语句，都是程序控制流程所无法到达的语句，即不会都是程序控制流程所无法到达的语句，即不会被执行到的语句，可将其删除。被执行到的语句，可将其删除。例：求最大公因子算法例：求最大公因子算法 begin read X; read Y; while (X mod Y0) do begin

20、T:=X mod Y; X:=Y; Y:=T end; write Y end(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(1)Read X(2)Read Y(3) T1:=X mod Y(4) If T10 goto (6)(6)T:=X mod Y(7)X:=Y(8)Y:=T(9)goto (3)(10)write Y(11)halt基本块的划分：基本块的划分：(1)Read X(2)Read

21、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(5)goto (10) 主要是进行已知量合并、删除公共子表达式、主要是进行已知量合并、删除公共子表达式、删除无用赋值。删除无用赋值。注：无用赋值有以下情形：注：无用赋值有以下情形： (a)(a)对某变量对某变量A A赋值后，在程序中没有引用；赋值后，在程序中没有引用； (b)(b)对某变量对某变量A A赋值后，在引用前又重新赋值；赋值后，在引用前又重新赋值； (c)(c)对某变量对某变量

22、A A进行自增赋值，且它仅仅被用在自进行自增赋值，且它仅仅被用在自增运算中。增运算中。对上面第一和第三种情况，应进行全局分析。对上面第一和第三种情况，应进行全局分析。3 3、块内优化、块内优化1 1、DAG(DAG(有向无环图有向无环图) )定义定义a)a)父子结点父子结点 若在一有向图中，结点若在一有向图中，结点n ni i有弧指向有弧指向n nj j，则称，则称n ni i是是n nj j的父结点，的父结点，n nj j是是n ni i的子结点。的子结点。b)b)路径与路径与环路环路 若在一有向图中，结点若在一有向图中，结点n n1 1 n n2 2 n nk k间存在有向间存在有向弧弧n

23、 n1 1n n2 2 n nk k, ,则称则称n n1 1 到到n nk k之间存在一条通路之间存在一条通路，若，若n n1 1n nk k则该路径称为环路；则该路径称为环路；c)c)有向无环图有向无环图 若有向图中任一路径都不是环路，则称该图为无若有向图中任一路径都不是环路，则称该图为无环路有向图。环路有向图。二、基本块的二、基本块的DAGDAG表示表示a)a)叶结点叶结点 没有子结点的结点称为叶结点，以一标识符没有子结点的结点称为叶结点，以一标识符( (变量名变量名) )或常或常数作为数作为标记标记。即该结点代表该变量或常数的值。即该结点代表该变量或常数的值。注：注：1)1)若叶结点代

24、表变量若叶结点代表变量a a的地址，则标记为的地址，则标记为addr(a)addr(a) 2) 2)通常把叶结点上作为标记的标识符加上下标通常把叶结点上作为标记的标识符加上下标0 0，以表示，以表示它是该变量的初值。它是该变量的初值。b)b)内部结点内部结点 以一运算符作为标记。即该结点代表应用该运算符对其后以一运算符作为标记。即该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。继结点所代表的值进行运算的结果。c)c)各结点上可能附加一个或多个标识符，表示这些标识符具有各结点上可能附加一个或多个标识符，表示这些标识符具有该结点所代表的值，简称该结点所代表的值，简称附标附标。2 2、D

25、AGDAG结点标记或附加信息结点标记或附加信息注：注：1)1)图中的有向弧都省去箭头。图中的有向弧都省去箭头。2)2)结点结点n ni i是构造是构造DAGDAG过程中给予各结点的过程中给予各结点的编号编号; ;3)3)各结点下面的符号（运算符、变量、常数）各结点下面的符号（运算符、变量、常数）是各结点的是各结点的标记标记; ;4)4)各结点右边的标识符是结点的各结点右边的标识符是结点的附标附标。n1n2n3BCAop例如：例如：A:=B op C A:=B op C 即四元式即四元式(op,B,C,A)(op,B,C,A)的的DAGDAG图为：图为： 根据其对应结点的根据其对应结点的子结点子

26、结点个数，可分为个数，可分为0 0型、型、1 1型、型、2 2型和型和3 3型四种类型。型四种类型。 A)0A)0型型A:=B,A:=B,即四元式即四元式(:=,B,_,A),(:=,B,_,A),其其DAGDAG结点为结点为0 0型：型：n1BA3 3、四元式的、四元式的DAGDAG结点类型结点类型B)1型型n1BAn2opA:=op BA:=op B，即四元式，即四元式(op,B,_,A)(op,B,_,A)，其，其DAGDAG结点为结点为1 1型：型：C)2C)2型型A:=B op CA:=B op C，即四元式，即四元式(op,B,C,A)(op,B,C,A)，其，其DAGDAG结结点

27、为点为2 2型；型；n1n2n3BCAopn1n2n3BCA=n1n2n3BC(s)ropif B rop C goto (s)if B rop C goto (s)即四元式即四元式(jrop,B,C,(s)(jrop,B,C,(s)其其DAGDAG结点为结点为2 2型型A:=BCA:=BC，即四元式，即四元式(=,BC,_,A)(=,BC,_,A)，其，其DAGDAG结点为结点为2 2型；型；变址取数变址取数D)3D)3型型n2n3n4BC=n1DDC:=BDC:=B即四元式即四元式(=,B,_,DC)(=,B,_,DC)，其，其DAGDAG结点为结点为3 3型：型：变址存数变址存数例：四元

28、式序列如下：例：四元式序列如下：A:=B+CA:=B+CB:=2B:=2* *A AD:=AD:=ADAGDAG图如右图如右: :n1n2n3BCA+n5Bn42*,Dnode(A)node(A)：返回与标识符：返回与标识符A A相应的最近建立的相应的最近建立的结点结点。a)a)初始化初始化 初始初始DAGDAG为空，无任何结点。为空，无任何结点。b)b)对基本块内每个四元式对基本块内每个四元式(op,A,B,C)(op,A,B,C)进行如下操作：进行如下操作： 1)1)如果如果node(A)node(A)无定义，则建立叶结点，标记为无定义，则建立叶结点，标记为A A，让，让node(A)no

29、de(A)等于这个结点。如果对于等于这个结点。如果对于2 2型四元式型四元式node(B)node(B)没有定义没有定义，则建立叶结点，这时标记为，则建立叶结点，这时标记为B B，且让，且让node(B)node(B)等于新建结点，等于新建结点，如果如果node(A)node(A)和和node(B)node(B)都是已知常量，则执行都是已知常量，则执行 A op BA op B（合并（合并常量）常量），得到新常量，得到新常量P P，为，为P P建立一个叶结点，标记为建立一个叶结点，标记为P P，如果，如果node(A)node(A)或或node(B)node(B)是建立当前四元式的新结点，则删

30、除它。是建立当前四元式的新结点，则删除它。 4 4、基本块的、基本块的DAGDAG构造算法构造算法2)2)对于三种四元式分别处理如下：对于三种四元式分别处理如下：( () )对于对于0 0型，让型，让n n是是node(A)node(A)。( () )对于对于1 1型，查看是否存在标记为型，查看是否存在标记为opop的结点，且的结点，且它有唯一的子结点它有唯一的子结点node(A)node(A)。如果不存在，则建立。如果不存在，则建立这样的结点，让这样的结点，让n n是找到或建立的结点。是找到或建立的结点。( () )对于对于2 2型，查看是否存在标记为型，查看是否存在标记为opop的结点，且

31、的结点，且其左右的子结点分别是其左右的子结点分别是node(A)node(A)和和node(B)node(B)。如果。如果不存在，则建立这样的结点，让不存在，则建立这样的结点，让n n是找到或建立的是找到或建立的结点。结点。例如：下面程序用来求圆环内外例如：下面程序用来求圆环内外圆周之和及圆环正反两面面积圆周之和及圆环正反两面面积之和。对其优化：之和。对其优化： Pi:=3.14Pi:=3.14 A: A:2 2* *PiPi* *(R+r);(R+r); B:=A; B:=A; B:=2 B:=2* * Pi Pi* *(R+r)(R+r)* *(R-r)(R-r)由语法制导翻译生成右边的四

32、元由语法制导翻译生成右边的四元式序列式序列(1)T0:=3.14(1)T0:=3.14(2)T1:=2(2)T1:=2* *T0T0(3)T2:=R+r(3)T2:=R+r(4)A:=T1(4)A:=T1* *T2T2(5)B:=A(5)B:=A(6)T3:=2(6)T3:=2* *T0T0(7)T4:=R+r(7)T4:=R+r(8)T5:=T3(8)T5:=T3* *T4T4(9)T6:=R-r(9)T6:=R-r(10)B:=T5(10)B:=T5* *T6T6*,T5*T6+ -,T3n5n7rn4n6n8(1)T0:=3.14(1)T0:=3.14(2)T1:=2(2)T1:=2*

33、*T0T0(3)T2:=R+r(3)T2:=R+r(4)A:=T1(4)A:=T1* *T2T2(5)B:=A(5)B:=A(6)T3:=2(6)T3:=2* *T0T0(7)T4:=R+r(7)T4:=R+r(8)T5:=T3(8)T5:=T3* *T4T4(9)T6:=R-r(9)T6:=R-r(10)B:=T5(10)B:=T5* *T6T6ABT2,T4n1T03.14n2T16.28n3R(1)T0:=3.14(1)T0:=3.14(2)T1:=2(2)T1:=2* *T0T0(3)T2:=R+r(3)T2:=R+r(5)B:=A(5)B:=A(6)T3:=2(6)T3:=2* *T

34、0T0(8)T5:=T3(8)T5:=T3* *T4T4(10)B:=T5(10)B:=T5* *T6T6B B1 1、可做到三种优化可做到三种优化 a a) )合并已知量合并已知量 对任何一个四元式，若其中参与运算的对象均是编译对任何一个四元式，若其中参与运算的对象均是编译时的已知量，则合并已知量，并用合并后算出的常量生成时的已知量，则合并已知量，并用合并后算出的常量生成一个叶结点。若参与运算的已知量的叶结点是当前四元式一个叶结点。若参与运算的已知量的叶结点是当前四元式建立的结果，则可删除。建立的结果，则可删除。 b)b)删除对变量的前一个赋值删除对变量的前一个赋值，即删除该变量的前一个附，

35、即删除该变量的前一个附标。标。 c)c)检查公共子表达式检查公共子表达式 对具有公共子表达式的所有四元式，只产生一个计算对具有公共子表达式的所有四元式，只产生一个计算该表达式值的内部结点，而将那些被赋值的变量附加到该该表达式值的内部结点，而将那些被赋值的变量附加到该结点。结点。三、三、DAGDAG在基本块优化中的作用在基本块优化中的作用2 2、利用利用DAGDAG图还原四元式序列图还原四元式序列 a)a)若为叶结点，无附标，则不生成任何四元式；若为叶结点，无附标，则不生成任何四元式； b)b)若为叶结点，标记为若为叶结点，标记为B B，附标为，附标为A A，则生成，则生成A:=BA:=B四元式

36、；若有多个附标，则生成值为四元式；若有多个附标，则生成值为B B的相应赋值的相应赋值语句四元式语句四元式 c)c)若为中间结点，有附标，则根据其标记若为中间结点，有附标，则根据其标记opop，生，生成相应四元式；若有多个附标，则除了第一个附标成相应四元式；若有多个附标，则除了第一个附标用于生成相应四元式，其它生成值为第一个附标的用于生成相应四元式，其它生成值为第一个附标的赋值语句四元式赋值语句四元式 d)d)若中间结点无附标，则添加一个临时附标若中间结点无附标，则添加一个临时附标SASA， 然后转然后转c)c)(9)B:=A(9)B:=A* *T T6 6(1)T(1)T0 0:=3.14:=

37、3.14(2)T(2)T1 1:=6.28:=6.28(3)T(3)T3 3:=6.28:=6.28(4)T(4)T2 2:=R+r:=R+r(5)T(5)T4 4:=T:=T2 2(6)A:=6.28(6)A:=6.28* *T T2 2(7)T(7)T5 5:=A:=A(8)T(8)T6 6:=R-r:=R-r B * A,T5 * T2,T4 T6 + - T0 T1,T3 3.14 6.28 R r (j)n2n5n3n7n1n4n6n83 3、获得其它优化信息、获得其它优化信息 a)a)在基本块外定值并在基本块内被引用的所有标识符，在基本块外定值并在基本块内被引用的所有标识符，就是作

38、为叶结点标记的那些就是作为叶结点标记的那些标识符标识符。 b)b)在基本块内被定值，且该值能在基本块后面被引用在基本块内被定值，且该值能在基本块后面被引用的所有标识符，就是的所有标识符，就是DAGDAG各结点上的那些附标。各结点上的那些附标。注：可利用上述信息，进一步删除四元式序列中其它情注：可利用上述信息，进一步删除四元式序列中其它情况的无用赋值，如：况的无用赋值，如：若某结点附标，在该基本块后面不会被引用，则不生成若某结点附标，在该基本块后面不会被引用，则不生成对该附标赋值的四元式；对该附标赋值的四元式；若某结点无附标，且无父结点，则不生成计算该结点值若某结点无附标，且无父结点，则不生成计

39、算该结点值的四元式；的四元式； 若两个相邻的四元式中的第一个四元式计算出来的值若两个相邻的四元式中的第一个四元式计算出来的值只在第二个四元式中被引用，则可合并这两个四元式。只在第二个四元式中被引用，则可合并这两个四元式。 (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*T6S1:=R+rA:=6.28*s1S2:=R-rB:=A*S2*,T5*T6+ -,T3n5n7rn4n6n8ABT2,T4n1T03.14n2T16.28n3RB

40、 B用用S1S1代替代替T2 ，用，用S2S2代替代替T6*,T5*T6+ -,T3n5n7rn4n6n8ABT2,T4n1T03.14n2T16.28n3RB B(1)T0:=3.14(1)T0:=3.14(2)T1:=2(2)T1:=2* *T0T0(3)T2:=R+r(3)T2:=R+r(4)A:=T1(4)A:=T1* *T2T2(5)B:=A(5)B:=A(6)T3:=2(6)T3:=2* *T0T0(7)T4:=R+r(7)T4:=R+r(8)T5:=T3(8)T5:=T3* *T4T4(9)T6:=R-r(9)T6:=R-r(10)B:=T5(10)B:=T5* *T6T6*,T

41、5*T6+ -,T3n5n7rn4n6n8ABT2,T4n1T03.14n2T16.28n3RB B(1)T0:=3.14(1)T0:=3.14(2)T1:=2(2)T1:=2* *T0T0(3)T2:=R+r(3)T2:=R+r(4)A:=T1(4)A:=T1* *T2T2(5)B:=A(5)B:=A(6)T3:=2(6)T3:=2* *T0T0(7)T4:=R+r(7)T4:=R+r(8)T5:=T3(8)T5:=T3* *T4T4(9)T6:=R-r(9)T6:=R-r(10)B:=T5(10)B:=T5* *T6T6*,T5*T6+ -,T3n5n7rn4n6n8ABT2,T4n1T0

42、3.14n2T16.28n3RB B(1)T0:=3.14(1)T0:=3.14(2)T1:=2(2)T1:=2* *T0T0(3)T2:=R+r(3)T2:=R+r(4)A:=T1(4)A:=T1* *T2T2(5)B:=A(5)B:=A(6)T3:=2(6)T3:=2* *T0T0(7)T4:=R+r(7)T4:=R+r(8)T5:=T3(8)T5:=T3* *T4T4(9)T6:=R-r(9)T6:=R-r(10)B:=T5(10)B:=T5* *T6T6一、控制流分析作用一、控制流分析作用1 1、是数据流程分析的基础、是数据流程分析的基础2 2、找出程序中的循环、找出程序中的循环注：注

43、：1)1)循环包括循环语句构成的循环及条件转移循环包括循环语句构成的循环及条件转移和无条件转移构成的循环。和无条件转移构成的循环。11.3 11.3 控制流分析和循环优化控制流分析和循环优化1 1、程序流图定义、程序流图定义 以基本块作为结点，控制程序流向作为有向弧，以基本块作为结点，控制程序流向作为有向弧，画出的图，称为程序流图。画出的图，称为程序流图。注：注：1)1)程序流图的特点是具有唯一首结点的有向图。程序流图的特点是具有唯一首结点的有向图。所谓首结点，是包含程序第一个语句的基本块。所谓首结点，是包含程序第一个语句的基本块。 2)2)从首结点沿着流图可到达任何结点。从首结点沿着流图可到

44、达任何结点。二、程序流图与必经结点集二、程序流图与必经结点集控制流程图（流图）：具有唯一首结点的有向图控制流程图（流图）：具有唯一首结点的有向图G=G= （N N，E E，n n0 0） N N：结点集：结点集( (基本块集基本块集) )E E：有向边集：有向边集 n n0 0：首结点：首结点, ,包含程序第一个包含程序第一个语句的基本块语句的基本块程序流图三元式定义程序流图三元式定义有向边集的构成：有向边集的构成： 满足下列条件之一时，结点满足下列条件之一时，结点i i到结点到结点j j有有向边：有有向边：基本块基本块j j在程序的位置紧跟在在程序的位置紧跟在i i后后, ,且且i i的出口

45、语句的出口语句不是无条件转移不是无条件转移goto(S)goto(S)或停语句或停语句i i的出口是的出口是goto(S)goto(S)或或ifif goto(S), goto(S),而而(S)(S)是是j j的的入口语句入口语句(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程序流图程序流图分析程序流图中结点间的关系分析程序流图中结点间的关系（1 1）m DOM n m DOM n 定义定义 在程序流图中在程序流图

46、中, ,对任意两个结点对任意两个结点m m和和n,n,如果从如果从流图的首结点出发流图的首结点出发, ,到达到达n n的任意通路都要经过的任意通路都要经过m,m,则称则称m m是是n n的必经结点的必经结点, ,记为记为m DOM n(m DOM n( a,a DOM a)a,a DOM a)必经结点集必经结点集定义定义 结点结点n n的所有必经结点的集合的所有必经结点的集合, ,称为结点称为结点n n的的必经结点集必经结点集, ,记为记为D(n).D(n).2 2、必经结点集、必经结点集定义定义1 1、基本思想、基本思想 根据一个结点的所有父结点的必经结点集，求出根据一个结点的所有父结点的必

47、经结点集，求出该结点的必经结点集。该结点的必经结点集。 若设结点若设结点n n的父结点是的父结点是P1,P2,P1,P2,PkPk，则，则D(n)=(D(P1)D(P2)D(n)=(D(P1)D(P2) D(Pk)n D(Pk)n2 2、具体实现方式、具体实现方式 使用迭代方法：比较相邻两次迭代结果，若相同，使用迭代方法：比较相邻两次迭代结果，若相同，则结束。则结束。三、求必经结点集算法三、求必经结点集算法求必经结点算法求必经结点算法输入输入: :一个流图，其结点集合一个流图，其结点集合N N，边集合，边集合E E，初始结点，初始结点n n0 0 输出输出: :关系关系 dom dom 方法方

48、法: :用下面的过程迭代计算用下面的过程迭代计算n n的必经结点集合的必经结点集合D(n)D(n)，最终，最终，d d在在D(n)D(n)中当且仅当中当且仅当d dom nd dom n。 (1)D(n(1)D(n0 0):=n):=n0 0 ； (2)for n in (N-n(2)for n in (N-n0 0) do D(n):=N) do D(n):=N；* *初始化结束初始化结束* * (3)while (3)while 任何任何D(n)D(n)出现变化出现变化 do do for n in (Nfor n in (N一一nn0 0) do ) do D(n):=n D(p);D(

49、n):=n D(p); 其中其中,p,p是是n n的父结点的父结点; ; 1234657各结点的必经结点集为：各结点的必经结点集为：D(1)=1D(1)=1D(2)=1,2D(2)=1,2D(3)=1,2,3D(3)=1,2,3D(4)=1,2,4D(4)=1,2,4D(5)=1,2,4,5D(5)=1,2,4,5D(6)=1,2,4,6D(6)=1,2,4,6D(7)=1,2,4,7D(7)=1,2,4,71 1、基本思想、基本思想 利用必经结点集求出流图中的回边，利用回边利用必经结点集求出流图中的回边，利用回边找出流图中的循环。找出流图中的循环。2 2、回边定义、回边定义 设设a ab b

50、是流图中一条有向边，若是流图中一条有向边，若b dom a b dom a ，则则a ab b是流图中一条回边。是流图中一条回边。四、查找循环算法四、查找循环算法例：求出下图的所有回边例：求出下图的所有回边1234657解：首先，求出必经结点集：解：首先，求出必经结点集：D(1)=1D(1)=1D(2)=1,2D(2)=1,2D(3)=1,2,3D(3)=1,2,3D(4)=1,2,4D(4)=1,2,4D(5)=1,2,4,5D(5)=1,2,4,5D(6)=1,2,4,6D(6)=1,2,4,6D(7)=1,2,4,7D(7)=1,2,4,7有有6 dom 6 ,4 dom 7 ,2 do

51、m 4故：故：66，74，42都是流图都是流图的回边。的回边。3 3、查找循环的算法、查找循环的算法1)1)找出回边找出回边n nd d；2)2)则则n,dn,d必定属于必定属于n nd d回边组成的循环回边组成的循环L L中，即中，即, , L:=n,d;L:=n,d;3)3)若若 ndnd且且n n的父结点的父结点nn不在不在L L中，则将它添至中，则将它添至L L中中，即，即L:=Ln;L:=Ln;4)4)对对3)3)求出的父结点求出的父结点n n重复执行重复执行3)3)，直至不再有新，直至不再有新结点加入结点加入L L为止。为止。 即即: :设设n nd d是回边，则该回边构成的循环包

52、括如是回边，则该回边构成的循环包括如下结点：下结点：n n、d d以及不经过以及不经过d d能到达能到达n n的所有结点。的所有结点。1234657回边对应的循环结点：回边对应的循环结点：667 442循环结点：循环结点：6循环结点：循环结点：7,4,5,6循环结点：循环结点：4,2,3,7,5,64 4、定理、定理 对于循环必定满足强连通，而且只有唯一入对于循环必定满足强连通，而且只有唯一入口点。口点。注：注：1)1)强连通是指循环中任意两个结点都有通路强连通是指循环中任意两个结点都有通路，单结点循环也有一弧指向自身。它保证了循环，单结点循环也有一弧指向自身。它保证了循环内各结点的代码都可反

53、复执行。内各结点的代码都可反复执行。 2)2)唯一入口点是指要到达循环内任意结点必唯一入口点是指要到达循环内任意结点必须经过此入口点。它保证了循环优化时，可将代须经过此入口点。它保证了循环优化时，可将代码外提到唯一入口点前的前置结点中。码外提到唯一入口点前的前置结点中。五、可归约流图五、可归约流图 当且仅当流图中除去回边外，当且仅当流图中除去回边外，其余的边构成一个无环路回其余的边构成一个无环路回路，就称流图为可归约流图。路，就称流图为可归约流图。 左图为可归约流图。左图为可归约流图。5 47 621 3 循环优化：三种重要技术循环优化：三种重要技术 代码外提：产生的结果独立于循环执行次数的代

54、码外提：产生的结果独立于循环执行次数的表达式，放到循环前面。表达式，放到循环前面。 强度削弱：把程序中执行时间较长的运算替换强度削弱：把程序中执行时间较长的运算替换为时间较短的运算。为时间较短的运算。 删除归纳变量：删除归纳变量： 对形如对形如I:=II:=I+ +C C的赋值的赋值 C C为循环不变量，称为循环不变量，称I I为为基本归纳变量。基本归纳变量。 对形如对形如J:=C1J:=C1* *I I+ +C2,C2,的赋值称的赋值称J J为归纳变量为归纳变量. .六、循环优化六、循环优化（一）、代码外提（一）、代码外提1 1、循环不变量定义、循环不变量定义 形如形如(s) A:=B op

55、 C(s) A:=B op C四元式，若四元式，若 (1)B(1)B、C C为常量；为常量； (2)(2)到达到达(s)(s)点的点的B B、C C定值点均在循环外；定值点均在循环外； (3)(3)到达到达(s)(s)点的点的B B、C C定值点虽在循环内，但只有一定值点虽在循环内，但只有一个定值点且已被标为循环不变运算。个定值点且已被标为循环不变运算。则则(s)(s)为循环不变运算，为循环不变运算，A A、B B、C C为循环不变量。为循环不变量。注：循环不变量不论循环执行多少次均始终保持不变，注：循环不变量不论循环执行多少次均始终保持不变，有可能外提到循环外，以提高运行速度。有可能外提到循环外，以提高运行速度。2 2、循环不变量外提条件、循环不变量外提条件a)a)该不变运算所在结点该不变运算所在结点( (基本块基本块) )必须是循环出必须是循环出口结点的必经结点或者该不变运算所定值的变口结点的必经结点或者该不变运算所定值的变