代码优化定义、方法和技术

1、代码优化定义、方法和技术教学目的：正确理解代码优化的定义和各种可能的优化概念；掌握用DAG表示进行局部优化的方法、循环优化技术。教学重点与难点：局部优化；DAG的构造与应用、循环优化。学时分配：4学时本章知识点：局部优化控制流分析和循环优化数据流的分析与全局优化优化技术简介 优 化编译前端代码优化器代码产生控制流分析数据流分析代码变换代码优化器的地位和结构首页结束1、优化的概念：优化的定义:对程序进行各种等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大，或占用存储空间减少，或两者都有。我们通常称这种变换为优化。11.1 优化技术简介首页结束 优化的目的是为了产生更高效

2、的代码。由优化编译程序提供的对代码的各种变换必须遵循下面的原则： 1)等价原则 主要指优化后的目标代码运行时间较短,以及占用的存储空间较小。 2)有效原则 使优化后所产生的目标代码运行时间确实较短，占用的空间确实较小 3）合算原则 应尽可能以较低的代价取得较好的优化效果2、优化的原则首页结束3、代码优化的基本方法按照与机器相关的程度，代码优化分为：与机器相关的优化：在生成目标程序时进行的，它在很大程度上与具体的计算机有关。 与机器无关的优化：在语法、语义分析生成中间代码之后，在中间代码上进行，这一类优化不依赖于具体的计算机，而取决于语言的结构。首页结束根据优化所涉及的程序范围分成:局部优化：基

3、本块范围内的优化：合并已知量消除公共子表达式，削减计算强度和删除无用代码循环优化：主要是基于循环的优化，包括循环不变式外提，归纳变量删除，计算强度削减。全局优化：主要是在整个程序范围内进行的优化。因为程序段是非线性的，因此需要分析程序的控制流和数据流，处理比较复杂。4、优化技术合并常量计算消除公共子表达式削减计算强度删除无用代码循环不变表达式外提归纳变量删除首页结束演示局限于基本块范围内的优化称为基本块内的优化或局部优化 。 1、基本块的定义 所谓基本块是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。 11.2 局部优化首页结束

4、划分四元式程序为基本块的算法如下：（1）求出四元式程序中各个基本块的入口语句，它们可以是下述语句之一：程序的第一个语句；2基本块的划分算法紧跟在条件转移语句后面的语句。能由条件转移语句或无条件转移语句转移到的目标语句；首页结束（2）对以上求出的每一入口语句构造其所属的基本块。它是由该入口语句到另一入口语句(不包括该入口语句)，或到一转移语句(包括该转移语句)，或到一停语句（包括该停语句)之间的语句序列组成的。（3)凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，将其删除。2基本块的划分算法首页结束【例如】有下列三地址代码程序：1）read X2）rea

5、d Y3）R：=X mod Y4）if R=0 goto (8)5) X:=Y6) Y:=R7) goto (3)8）write Y9) halt划分为4个基本块:B11）、2） B23)、4） B35）、 6）、7）B48）、9） 首页结束【例如】划分基本块(1) read (C)(2) A:= 0(3) B:= 1(4) L1: A:=A + B(5) if B= C goto L2(6) B:=B+1(7) goto L1(8) L2: write (A)(9) halt划分为4个基本块:B1（1）、（2）、（3） B2（4）、（5） B3（ 6）、（7）B4（8）、（9） 首页结束3、

6、基本块的变换基本块内可进行的优化： 合并已知常量和复写传播临时变量改名交换语句的位置删除公共子表达式删除无用代码首页结束删除公共子表达式 如果一个表达式E的值已计算过，并且在此之后E中变量的值没有改变，则称E为公共子表达式，为避免重复计算而删除，称为删除公共子表达式【例如】x:=(a+b)*c-(a+b)2t1=a+b;t2=t1*c;t3=a+b;t4=t32X:=t2-t4;t1=a+b; t2=t1*c;t4=t12 X:=t2-t4;变换后首页结束x+y*t-a*(x+y*t)/(y*t)(1)( *， y， t， t1 )(2)( +， x， t1， t2 )(3)( *， y，t，

7、 t3 )(4)( +， x， t3， t4 ) (5)( *， a，t4，t5 )(6)( *， y， t， t6 )(7)( /， t5，t1，t7 )(8)( -， t2， t7， t8 )消除公共子表达式之后：(1)( *， y，t， t1 )(2)( +， x， t1，t2 )(3)( *， a，t2，t5 )(4)( /， t5， t1， t7 )(5)( -， t2，t7，t8 )【例如】返回首页结束删除无用代码 若某些变量的值在整个程序中不再使用，那么这些变量的赋值对程序运行结果没有任何作用，那么就可以删除对这些变量赋值的代码，称为删除无用代码或删除无用赋值。【例如】若T7、T

8、8、T6在以后的程序中不再使用T6:=T2X:=T3T7:=T2T8:=T4aT2:=T5aT4:=T3变换后aT2:=T5aT4:=T3返回首页结束合并已知量a = 10 * 5 + 6 - b;t0 = 10;t1 = 5 ;t2 = t0 * t1 ;t3 = 6 ;t4 = t2 +t3 ；t5 = t4 b;a = t5 ; 合并后： t0 = 56 ; t1 = t0 b ;a = t1 ;首页结束【例】d = 2*3.14*r(1) ( *，2，t1 )(2) ( *，t1 ， r，t2 )(3) ( =，t2， ， d )的值在编译时刻就可以确定。(1) ( *，r，t2 )(

9、2) ( =，t2， ， d )首页结束返回复写传播 形成为f := g的赋值叫做复写语句。 。 优化过程中会大量引入复写。 复写传播变换的做法是在复写语句f:=g后，尽可能用g代表f 。 复写传播变换本身并不是优化，但它给其它优化如常量合并和死代码删除带来机会。t2 = t1 ;t3 = t2 * t1;t4 = t3 ;t5 = t3 * t2 ;c = t5 + t4 ;t3 = t1 * t1 ;t5 = t3 * t1 ;c = t5 + t3 ;【例】返回重新命名临时变量例如: t:=b+c u:=b+c返回交换语句次序目的：减少临时变量【例如】相邻两个语句t1:=b+c t2:=

10、x+yt2:=x+y t1:=b+c基本块优化的实现从四元式序列构造DAG ，然后再从DAG重写四元式。4、基本块的有向图DAG表示基本块内部优化实现的主要工具为： DAG(Directed Acyclic Graph的缩写) DAG :如果有向图中任一通路都不是环路,则称该有向图为无环路有向图，也称有向非循环图,简称DAG。 用DAG图表示各个值的计算/依赖关系。演示返回DAG图中结点的特点1.叶结点 标记:标识符名(变量名)或常数,写在结点下面。代表:该结点代表该变量或常数的值。地址的表示：Addr(A)通常将其标识符加上下标0,表示该变量的初值。2.内部结点标记:一个运算符号，写在结点下

11、面。代表:利用后续结点运算出来的值。3图中各个结点可能附加一个或多个标识符,表示这些标识符具有该结点所代表的值，同一个结点的标识符表示相同的值，写在结点右面。 四元式相应的DAG（1）A：= op B 1型该算法只对如下三种四元式构造DAG： 0型 A:=B l型 A:=op B 2型 A:=B op C op是双目运算符还可以是=或=。基本块的DAG构造算法输入：一个基本块输出：相应DAG图算法说明：通过逐个扫描四元式来逐渐建立DAG图。函数node(A)的值或者是一个结点的编号n或者无定义。如果是前一种情况，代表存在一个结点n，A是其上的标记或附加标识符。基本块的DAG构造算法首先DAG为

12、空。对基本块的每一四元式，依次执行：1如果NODE（B）无定义，则构造一标记为B的叶结点并定义NODE（B）为这个结点；如果当前四元式是0型，则记NODE(B)的值为n，转4。如果当前四元式是1型，则转2.(1)。如果当前四元式是2型，则： (I)如果NODE(C)无定义，则构造一标记为C的叶结点并定义NODE(C) 为这个结点； (II)转2.(2) 2（合并已知量）（1）如果NODE(B)是标记为常数的叶结点 ，则转2(3)，否则转3.（1）。（2）如果NODE(B)和NODE(C)都是标记为常数的叶结点，则转2.（4），否则转3.（2）。（3）执行op B（即合并已知量），令得到的新常数

13、为P。如果NODE(B)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4。（4）执行B op C（即合并已知量），令得到的新常数为P。如果NODE(B)或NODE(C)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4。基本块的DAG构造算法基本块的DAG构造算法 3（找公共子表达式）（1）检查DAG中是否已有一结点，其唯一后继为NODE(B)，且标记为op（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设

14、该结点为n，转4。（2）检查中DAG中是否已有一结点，其左后继为NODE(B)，其右后继为NODE(C)，且标记为op（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4。 4. （删除无用赋值语句）如果NODE(A)无定义，则把A附加在结点n上并令NODE(A)=n；否则先把A从NODE(A)结点上附加标识符集中删除（注意，如果NODE(A)是叶结点，则其标记A不删除），把A附加到新结点n上并令NODE(A)=n。转处理下一四元式。仅含0,1,2型四元式的基本块的DAG构造算法:首先：假定DAG为空，即没有任何结点。对基本块中的每一四元式依次执行

15、：【例】构造下列四元式序列的DAG图。(1) T0(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图重写四元式后得到如下优化的四元式序列：(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(删除无用代码) 【例】试对以下基本块B1应用D

16、AG进行优化。 B1: A:=B*C D:=B/C E:=A+D F:=E*2 G:=B*C H:=G*G F:=H*G L:=F M:=L 并就以下两种情况分别写出优化后的四元式序列：若某个变量在基本块后不被引用,可删除。（1）假设G、L、M在基本块后面被引用；（2）假设只有L在基本块后被引用。解：对于B1其DAG图：(1)若只有G、L、M在基本块后被引用，则优化为： G := B*C H := G*G L := H*G M := Ln1+*n3Bn2C*A,Gn4/En62n7F*n8H*F,L,MDn5n9 (2) 若只有L在基本块后被引用，则优化为： G := B*C H :=G*G

17、L := H*G11.3 控制流分析和循环的优化 定义：以基本块为结点，将控制流信息增加到基本块的集合上来表示一个程序而得到的有向图，称为程序流图。 如果一个结点的基本块入口语句是程序的第一条语句，则此结点为首结点。 如果在某个执行顺序中基本块B2紧接在基本块B1之后执行，则从B1到B2有一条有向边。一、程序流图【例如】有下列三地址代码程序，给出程序流程图。1）read X2）read Y3）R：=X mod Y4）if R=0 goto (8)5) X:=Y6) Y:=R7) goto (3)8）write Y9) halt演示【例】有下列三地址代码程序，给出程序流程图。(1）I:= 1(2

18、) if I 10 goto (15)(3) T1:=2*J(4) T2:= 10 * I(5) T3:=T2 + T1(6) T4:=add(A) 11(7) T5:=2 * J(8) T6:= 10 * I(9) T7:= T5 + T6(10) T8:=add(A) - 11 (11) T9:= T8T7(12）T4T3:= T9 + 1(13) I:= I + 1(14) goto (2)(15)演示循环是程序流图中具有唯一入口结点的强连通子图。说明：1.强连通的(任意两结点间,必有一条通路,且该通路上各结点都属于该结点序列)2.它们中间有且只有一个是入口结点。二、循环的查找必经结点：

19、在程序流图中，对任意两个结点m和n，若从流图的首结点出发，到达n的任一通路都要经过m，则称m是n的必经结点，记为 m DOM n,流图中结点n的所有必经结点的集合，称为结点n的必经结点集，记为D(n).回边：设n-m是流图中的一条有向边，且m DOM n,则称n-m是流图中的一条回边。【例】对下面语句划分基本块，画出程序流程图a:=1;if a=b then b:=1 else c:=1endif;d:=a+b1、翻译的四元式是：1）a:=12) IF a=b goto 4)3) goto 6)4)b:=1 5)goto 7)6)c:=17) d:=a+b;步骤：1、翻译为四元式2、划分基本块

20、，画程序流程图2、划分基本块，画程序流程图1）a:=12) IF a=b goto 4)3) goto 6)4)b:=1 5)goto 7)6)c:=17) d:=a+b;(1) read (C)(2) A:= 0(3) B:= 1(4) L1: A:=A + B(5) if B= C goto L2(6) B:=B+1(7) goto L1(8) L2: write (A)(9) halt【例】对下面语句划分基本块，画出程序流程图。【例如】 6 73 4 1 2 3 5 7 6 1 2 1 2 1 2 1必经结点 必经结点集D(6)=1,2,4,6D(1)=1D(2)=1,2D(3)=1,2

21、,3D(4)=1,2,4D(5)=1,2,4,5D(7)=1,2,4,7 3下图给出求回边n-d组成的循环的算法：procedure insen(m)； if m不属于loop then begin loop:loop Um； 把m下推进栈stack； end；*主程序* Stack：空； loop:d； insert(n)； while stack 非空 dObegin 把stack的栈顶元素m上托出去 for p P(m)dO insert(p)end 其中P(m)表示结点m的前驱结点集，stack为工作栈，loop为所求循环。insert为一过程。 算法的基本思想是：由于要求回边n-d组

22、成的循环，这个循环将以d为其唯入口，n是它的一个出口。若n不等于d，则n的所有前驱结点应属于循环。当求出n的所有前驱后，只要它们不是循环入口d，就应再求出它们的前驱，新求出的所有前驱也应属于循环。然后再对新求出的所有前驱，重复以上步骤，直到所求出的前驱是d为止。此时算法结束。回边 6 6循环 6 7 4 4,5,6,7 4 2 2,3,4,5,6,7 【例】 6 73 4 1 2 3 5 7 6 1 2 1 2 1 2 3 1四元式序列如下：1）J：=0;2)L1:I=0;3)IF I8 goto L34)L2:A:=B+C5)B:=D*C6)L3:IF B=0 goto L4;7)write

23、 B;8)goto L5;9)L4:I:=I+1;10)IF I8 goto L2;11)L5:J:=J+1;12)IF JB goto B4B1I:=2B:=I+YB3A:=A+1J:=M+NY:=Y-1IF YB goto B4B1I:=2B:=I+YB3A:=A+1Y:=Y-1IF Y 10 goto (15)(3) T1:=2*J(4) T2:= 10 * I(5) T3:=T2 + T1(6) T4:=add(A) 11(7) T5:=2 * J(8) T6:= 10 * I(9) T7:= T5 + T6(10) T8:=add(A) - 11 (11) T9:= T8T7(12）

24、T4T3:= T9 + 1(13) I:= I + 1(14) goto (2)(15) 划分基本块并划出流程图：（1）I := 1(2) If I 10 goto (15)(3) T1 :=2*J(4) T2 := 10 * I(5) T3 :=T2 + T1(6) T4 :=add(A) 11(7) T5 :=2 * J(8) T6 := 10 * I(9) T7 := T5 + T6(10) T8 :=add(A) - 11 (11) T9 := T8T7(12）T4T3 := T9 + 1(13) I: = I + 1(14) goto (2)(15)B1B2B3B4 代码外提后： （

25、1） I := 1(3) T1 := 2 * J(6) T4 := add(A) 11(7) T5 := 2 * J(8) T8 := add(A) - 11 ( (2) if I 10 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 （2）(15)B1B2B2B3B4（1） I ：= 1 (3) T1 := 2* J (6) T4 := add(A) 11 (7)

26、 T5 :=2 * J (10) T8 := add(A)-11 (4) T2 := 10 * I (8) T6 := 10 * I(2) If I 10 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 B2(15)B1B2B2B3B42 、强度消弱：指把程序中执行时间较长的运算替换为执行时间较短的运算 3、删除归纳变量再次强度消弱 如果，T2, T6出循环后不是活动变量，则

27、可在循环后删除。 (1) I := 1(3) T1 := 2 * J(6) T4 := add(A)-11(7) T5 :=2 * J(10) T8 := add(A)-11(4) T2 := 10*I(8) T6 := 10*I(5) T3 := T2 + T1(9) T7 := T6 + T5(2)if I 10 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 B2(15)B1B2B2B3(15

28、) (2) if T3R goto (15)(3) T1 := 2 * J(6) T4 :add(A) 11(7) T5 := 2 * J(10) T8 :=add(A) 11(4) T2 :=10 * I(8) T6 :=10 * I(5) T3 :=T2 + T1(9) T7 := T6 + T5(2) R = 100 + T1 （1） I ：= 1B1B2(11) T9 := T8T7(12) T4T3 :=T9 + 1(5) T3 := T3 + 10(9) T7 := T7 + 10(14) Goto B2B2B3解： 三地址代码： (1) I := 1 (2) j := 1B1例3

29、 试写出以下程序段 for I := 1 to M do for j := 1 to N do AI, j := BI, j 的三地址代码，然后求出其中的循环，并进行循环优化。 (3) If IM goto (30)(4) If jN goto (13)(5) T1 := I * N(6) T2 := T1 + j(7) T3 := N + 1(8) T4 := add(A)-T3(9) T5 := add(B)-T3(10) T4T2 := T5T2(11) j := j + 1(12) goto (4)(13) I := I+1(14) j :=1(15) goto (3)(30)B2B3

30、B4B5B6代码外提：（1）I := 1 (2) j := 1(7) T3 := N + 1(8) T4 := add(A)-T3(9) T5 := add(B)-T3(3) If IM goto (30)(5) T1 := I * N(4) If j N goto (13) (6) T2 := T1 + j (10) T4T2 := T5T2 (11) j := j + 1 (12) goto (4) (13) I := I + 1 (14) j := 1 (15) goto (3) (30)B1B2B2B3B3B4B5B6强度消弱：I := 1j := 1(7) T3 := N + 1(8

31、) T4 :=add(A)- T3(9) T5 :=add(B)-T3(5) T1 :=I * N (3) if I M goto (30)(4) If j N goto (13)(6) T2 := T1 + j(10) T4T2 := T5T2(11) j := j + 1(12) goto (4)(13) I := I + 1(5) T1 := T1 + N(14) j := 1(15) goto (3)(30)B1B2B2B3B4B5B6强度消弱(1):（1）I := 1 (2) j := 1(7) T3 := N + 1(8) T4 := add(A)-T3(9) T5 := add(B)-T3(5) T1 := I * N(3) If IM goto (30)(5) T2 := T1 + j(4) If j N goto (13) (10) T4T2 := T5T2 (11) j := j + 1 (6) T2 := T2 + 1 (12) goto (4) (13) I := I + 1 (5) T1 := I + N (14) j := 1 (15) goto (3) (30)B1B2B2B3B3B4B5B6 删除归