第7章：代码优化

1、第7章代码优化词法分析器词法分析器语法分析器语法分析器中间代码生成器中间代码生成器优化段优化段源程序源程序单词符号单词符号语法单位语法单位四元式四元式表表格格管管理理出出错错处处理理目标代码生成器目标代码生成器四元式四元式目标代码目标代码 7.17.1 优化概述 优化是一种等价的、有效的程序变换。优化的目的是为了产生更高效的代码。由优化的编译程序提供的对代码的各种变换必须遵循下面的原则： 等价原则：是指经过优化后不应改变源程序运行的结果。 有效原则：经优化后所产生的目标代码运行时间较短，占用存储空间较小。 合算原则：应尽可能以较低的代价取得较好的优化效果。 编译前端编译前端代码优化器代码优化器

2、编译后端编译后端控制流分析控制流分析数据流分析数据流分析代码变换代码变换优化技术分类 代码优化实际上是对代码进行等价变换，由一组代码变成运行结果相同的另一组代码。 源程序一级的优化：对中间代码的优化，与机器无关,面向各种语言.主要包括：局部优化、循环优化、全局优化 目标代码的优化：与具体机器有关. .主要包括对寄存器的优化，多处理机的优化、特殊指令的优化等优化技术分类优化技术分类局部优化:程序中顺序执行的语句序列循环优化:程序中循环语句的优化全局优化:整个程序范围内的优化优化的种类：优化的种类：删除多余运算删除多余运算( (或称删除公用子表达式或称删除公用子表达式) )代码外提代码外提强度消弱

3、强度消弱变换循环控制条件变换循环控制条件合并已知量合并已知量复写传播复写传播删除无用赋值删除无用赋值中间代码优化举例 设、为两个一维数组，他们的初始地设、为两个一维数组，他们的初始地址分别为址分别为addr(A),addr(B), 源程序段是源程序段是 S=0 FOR (i=1,i=20;i+) S=S+Ai+Bi 假设机器按字节编制 根据程序流向的特点,分为B1,B2两块. B1是循环体外的语句,B2是可重复执行的循环语句序列 原则:通过等价变换,将尽量减少循环体中的语句,同时尽可能减少无实际意义的重复计算与赋值,尽可能降低机器运算强度,运算的级别.删除公共子表达式删除公共子表达式(删除多删

4、除多余运算余运算) 公共子表达式是指在一个基本程序块内计公共子表达式是指在一个基本程序块内计算结果相同的子表达式算结果相同的子表达式代码外提代码外提是指把循环不变的运算提到循环体前面是指把循环不变的运算提到循环体前面优化前的中间代码优化前的中间代码经删除公共子表达式和代码经删除公共子表达式和代码外提后的中间代码外提后的中间代码3.降低运算强度降低运算强度 主要指不改变运算结果的主要指不改变运算结果的前提下前提下,将程序执行时间长的将程序执行时间长的运算替换成执行时间短的运运算替换成执行时间短的运算降低运算级别算降低运算级别经强度削弱后的中间代码经强度削弱后的中间代码4.变换循环控制变量(删除归

5、纳变量)如果在循环体内存在一个变量(或临时变量)T与循环控制变量 i保持线性关系,同时在循环后面不引用I,而除去i又不影响程序运行结果,则可由T取代循环控制变量变量 I, 这种方法称为变换循环控制变量(删除归纳变量)5.合并已知量合并已知量是指若参加运算的两个对象在编译时都是已知量,则可以在编译时直接计算出它们的运算结果6.复写传播是指尽量不引用那些在程序中仅仅只传递信息而不改变其值,也不影响其运行结果的变量.经变换循环控制变量经变换循环控制变量, ,合并合并已知量已知量, ,复写传播后的中间复写传播后的中间代码代码7,删除无用赋值删除无用赋值减少无用的变量,使代码更简洁假(1) S=0(4)

6、 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)B2B1真经删除无用赋值后的经删除无用赋值后的中间代码中间代码 经过优化后经过优化后, ,代码具有以下特点代码具有以下特点: : (1)(1)减少了循环体内可执行代码减少了循环体内可执行代码:10:10条条6 6条条 (2)(2)减少了乘法运算次数减少了乘法运算次数:3:3次次1 1次次 (3)(3)减少了全程范围内使用的变量减少了全程范围内使用的变量:i,T:

7、i,T4 47.2 局部优化 合并已知量：运算对象是已知量，编译时直接计算它们的值，而不必等到程序运行时再计算。 删除公共子表达式：如果一个表达式E的值，前面已经算过，并且在这之后E的值没有改变，则E称为公共子表达式，则可以避免它的重复运算，称为删除公共子表达式。（删除多余运算） 删除无用赋值：如果一些变量的值在整个程序中不再被使用，则这些变量的赋值对程序的运算结果没有任何作用，则可以删除对这些变量赋值 的代码，称为删除无用赋值。 局部优化 基本块：一个基本块是指程序中一顺序执行的语句序列。其中只有一个入口和一个出口，入口就是其中第一个语句，出口就是最后一条语句。对于一个基本块来说，执行时只能

8、从其入口进入，从出口退出。 局限于基本块范围内的优化称为基本块内的优化，或称局部优化。 划分四元式程序为基本块的算法:1.求出四元式程序中各个基本块的入口语句:1) 程序第一个语句，或2) 能由条件转移语句或无条件转移语句转移到的语句，或3) 紧跟在条件转移语句后面的语句。2. 对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句) 、或一停语句(包括该停语句)之间的语句序列组成的。入口语句入口语句n入口语句入口语句m入口语句入口语句n转移语句转移语句m入口语句入口语句n停语句停语句m3. 凡未被纳入某一基本块中的语句

9、，都是程序不可到达的语句,可以从程序中删除。 例：划分基本块例：划分基本块(1)read X(2) read Y(3) C:=X mod Y(4) if C=0 goto (8)(5) X:=Y(6) Y:=C(7) goto (3)(8) write Y(9) halt1.求出四元式程序中各个基本块的入口求出四元式程序中各个基本块的入口语句语句:1) 程序第一个语句，或程序第一个语句，或2) 能由条件转移语句或无条件转移语能由条件转移语句或无条件转移语句转移到的语句，或句转移到的语句，或3) 紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。 例：划分基本块例：划分基本块(1)re

10、ad X(2) read Y(3) R:=X mod Y(4) if R=0 goto (8)(5) X:=Y(6) Y:=R(7) goto (3)(8) write Y(9) halt1.求出四元式程序中各个基本块的入口语求出四元式程序中各个基本块的入口语句句:1) 程序第一个语句程序第一个语句，或，或2) 能由条件转移语句或无条件转移语能由条件转移语句或无条件转移语句转移到的语句，或句转移到的语句，或3) 紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。 例：划分基本块例：划分基本块(1)read X(2) read Y(3) R:=X mod Y(4) if R=0 got

11、o (8)(5) X:=Y(6) Y:=R(7) goto (3)(8) write Y(9) halt1.求出四元式程序中各个基本块的入口语求出四元式程序中各个基本块的入口语句句:1) 程序第一个语句，或程序第一个语句，或2) 能由条件转移语句或无条件转移语能由条件转移语句或无条件转移语句转移到的语句句转移到的语句，或，或3) 紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。 例：划分基本块例：划分基本块(1)read X(2) read Y(3) R:=X mod Y(4) if R=0 goto (8)(5) X:=Y(6) Y:=R(7) goto (3)(8) write

12、 Y(9) halt1.求出四元式程序中各个基本块的入口语求出四元式程序中各个基本块的入口语句句:1) 程序第一个语句，或程序第一个语句，或2) 能由条件转移语句或无条件转移语能由条件转移语句或无条件转移语句转移到的语句句转移到的语句，或，或3) 紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。 例：划分基本块例：划分基本块(1)read X(2) read Y(3) R:=X mod Y(4) if R=0 goto (8)(5) X:=Y(6) Y:=R(7) goto (3)(8) write Y(9) halt1.求出四元式程序中各个基本块的入口语求出四元式程序中各个基本块

13、的入口语句句:1) 程序第一个语句，或程序第一个语句，或2) 能由条件转移语句或无条件转移语能由条件转移语句或无条件转移语句转移到的语句，或句转移到的语句，或3) 紧跟在条件转移语句后面的语句紧跟在条件转移语句后面的语句。 例：划分基本块例：划分基本块(1)read X(2) read Y(3) R:=X mod Y(4) if R=0 goto (8)(5) X:=Y(6) Y:=R(7) goto (3)(8) write Y(9) halt2. 对以上求出的对以上求出的每个入口语句，每个入口语句，确定其所属的基确定其所属的基本块。它是由该本块。它是由该入口语句到入口语句到下一下一入口语句

14、入口语句(不包括不包括该入口语句该入口语句)、或、或到到一转移语句一转移语句(包包括该转移语句括该转移语句)、或或一停语句一停语句(包括包括该停语句该停语句)之间的之间的语句序列组成的。语句序列组成的。 程序流图:(8) write Y(9) halt(5) X:=Y(6) Y:=R(7) goto (3)(3) R:=X mod Y(4) if R=0 goto (8)(1) read X(2) read YB1B2B3B4程序流图 以基本块作为结点，控制程序流向作为有向弧，画出的图，称为程序流图。 流图G=（N，E，n0） N：表示流图的有限结点集合，每一个结点对应一个基本块。 E：流图的

15、有向边集合； n0：表示唯一的首结点，包含程序第一个语句的基本块。程序流图程序流图每个流图以基本块为每个流图以基本块为结点结点。如果一个结点的基本。如果一个结点的基本块的入口语句是程序的第一条语句，则称此结点块的入口语句是程序的第一条语句，则称此结点为首结点为首结点。如果在某个执行顺序中，基本块。如果在某个执行顺序中，基本块B B2 2紧紧接在基本块接在基本块B B1 1之后执行，则从之后执行，则从B B1 1到到B B2 2有一条有向边。有一条有向边。即，如果即，如果有一个条件或无条件转移语句从有一个条件或无条件转移语句从B B1 1的最后一条的最后一条语句转移到语句转移到B B2 2的第一

16、条语句；或者的第一条语句；或者在程序的序列中，在程序的序列中，B B2 2紧接在紧接在B B1 1的后面，并且的后面，并且B B1 1的最后一条语句不是一个无条件转移语句。我的最后一条语句不是一个无条件转移语句。我们就说们就说B B1 1是是B B2 2的的前驱前驱，B B2 2是是B B1 1的的后继。后继。(1)read X(2) read Y(3) R:=X mod Y(4) if R=0 goto (8)(5) X:=Y(6) Y:=R(7) goto (3)(8) write Y(9) halt(8) write Y(9) halt(5) X:=Y(6) Y:=R(7) goto (

17、3)(3) R:=X mod Y(4) if R=0 goto (8)(1) read X(2) read YB1B2B3B4对下面的程序段划分基本块,构造程序的控制流图 (1) read c */1 (2) a:=0 (3)b:=1 (4)a:=a+b */2 (5)if bc goto (10) (6) b:=b+1 */3 (7)goto (4) (8)a:=a+1 (9)b:=a+2 (10)write a */4 (1)halt 基本块划分块号bfirstbLastb sucbpredb1(1)(3)2_2(4)(5)3、41、33(6)(7)224(10)(11)_2(1)read

18、 c 1(2) a:=0 (3)b:=1L1:(4)a:=a+b 2(5)if bc goto L2(6) b:=b+1 3(7) goto L1L2: (10) write A 4 (11) halt 程序流图:基本块的DAG图 DAG(Directed Acyclic Graph)是一种有向图,常常用来对基本块进行优化。基本块中的语句的计算过程可以用一张图表示出来，即一个基本块可用一个DAG图表示。 图表示法图表示法 图表示法图表示法DAGDAG抽象语法树抽象语法树 无循环有向图无循环有向图( (Directed Acyclic GraphDirected Acyclic Graph，简称

19、简称DAG)DAG)对表达式中的每个子表达式，对表达式中的每个子表达式，DAGDAG中都有一个中都有一个结点结点一个内部结点代表一个操作符，它的孩子代表一个内部结点代表一个操作符，它的孩子代表操作数操作数在一个在一个DAGDAG中代表公共子表达式的结点具有多中代表公共子表达式的结点具有多个父结点个父结点 a:=b*(-c)+b*(-c)的图表示法 assigna+*buminuscDAGassigna+*buminusc抽象语法树抽象语法树*buminusc抽象语法树抽象语法树对应的代码：对应的代码： T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5

20、assigna+*buminusc抽象语法树抽象语法树*buminuscDAG对应的代码：对应的代码： T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象语法树抽象语法树对应的代码：对应的代码： T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5 描述计算过程的描述计算过程的DAGDAG是一种带有下述标记或附加是一种带有下述标记或附加信息的信息的DAG:DAG:n13.14n3n4Rrn5+T2, T4 图的图的叶结点叶结点以一以一标识符标识符或或常数常数作为标记，表示该作为标记，表示该结点代表该变量或

21、常数的值结点代表该变量或常数的值; ; 图的图的内部结点内部结点以一以一运算符运算符作为作为标记，表示该结点代表应用该标记，表示该结点代表应用该运算符对其后继结点所代表的运算符对其后继结点所代表的值进行运算的结果值进行运算的结果; ; 图中各个结点上可能图中各个结点上可能附加一个或多个标识附加一个或多个标识符符( (称附加标识符称附加标识符) )表表示这些变量具有该结示这些变量具有该结点所代表的值。点所代表的值。借助DAG进行优化 利用DAG来进行优化的主要思想：将一基本块中的每一个四元式依次表示成对应的一个DAG，再按原来构造DAG结点的顺序重写四元式序列，便可得到“合并已知常量”、“删除无

22、用赋值”、“删除多余运算”后的等价基本块优化了的基本块 。 基本块的基本块的DAGDAG表示及应用表示及应用 一个基本块，可用一个一个基本块，可用一个DAGDAG来表示与各四来表示与各四元式相对应的元式相对应的DAGDAG结点形式结点形式: : 四元式四元式 DAG DAG 图图(0) 0型型: A:=B (:=，B，-，A) n1AB四元式四元式 DAG DAG 图图(1) 1型型: A:=op B (op，B，-，A)n1ABn2op(2) 2型型: A:=B op C (op，B，C，A)n2ABn1opn3C四元式四元式 DAG DAG 图图(3) 2型型: A:=BC (=，BC，-

23、，A) n2ABn1=n3C(4) 2型型: if B rop C goto (s) (jrop，B，C，(s)n2(s)Bn1ropn3C四元式四元式 DAG DAG 图图(5) 3型型: DC:=B (=，B，-，DC)(6) 0型型: goto (s) (j，-，-，(s)(s)n1n2Bn1=n4Cn3D例：赋值语句例：赋值语句T T4 4:=A+B-:=A+B-（E-E-（C+DC+D）四元式序列GT1:=A+BT2:=C+DT3:=E-T2T4:=T1-T3 A B E C Dn9n3n8n1n2n7n6n4n5 T4 T1 T3 T2 + - - +DAG: 例例7.3试构造以下

24、基本块试构造以下基本块G的的DAG(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 To 3.14 (a)n1(1) T(1) T0 0:=3.14:=3.14 T0 T1 3.14 6.28 (b)n2n1(1)T(1)T0 0:=3.14:=3.14(2)T(2)T1 1:=2:=2* *T T0 0(1)T(1)T0 0:=3.14:=3.14(2)T(2)T1 1:=2:=2* *T T0 0(3)T(3)

25、T2 2:=:=R+rR+r A * T2 + T0 T1 3.14 6.28 R r (d)n2n5n3n1n4n6(1)T(1)T0 0:=3.14:=3.14(2)T(2)T1 1:=2:=2* *T T0 0(3)T(3)T2 2:=:=R+rR+r(4)A:=T(4)A:=T1 1* *T T2 2 A,B * T2 + T0 T1 3.14 6.28 R r (e)n2n5n3n1n4n6(1)T(1)T0 0:=3.14:=3.14(2)T(2)T1 1:=2:=2* *T T0 0(3)T(3)T2 2:=:=R+rR+r(4)A:=T(4)A:=T1 1* *T T2 2(5

26、)B:=A(5)B:=A A,B * T2 + T0 T1,T3 3.14 6.28 R r (f)n2n5n3n1n4n6(1)T(1)T0 0:=3.14:=3.14(2)T(2)T1 1:=2:=2* *T T0 0(3)T(3)T2 2:=:=R+rR+r(4)A:=T(4)A:=T1 1* *T T2 2(5)B:=A(5)B:=A(6)T(6)T3 3:=2:=2* *T T0 0 A,B * T2,T4 + T0 T1,T3 3.14 6.28 R r (g)n2n5n3n1n4n6(1)T(1)T0 0:=3.14:=3.14(2)T(2)T1 1:=2:=2* *T T0 0

27、(3)T(3)T2 2:=:=R+rR+r(4)A:=T(4)A:=T1 1* *T T2 2(5)B:=A(5)B:=A(6)T(6)T3 3:=2:=2* *T T0 0(7)T(7)T4 4:=:=R+rR+r A,B,T5 * T2,T4 + T0 T1,T3 3.14 6.28 R r (h)n2n5n3n1n4n6(1)T(1)T0 0:=3.14:=3.14(2)T(2)T1 1:=2:=2* *T T0 0(3)T(3)T2 2:=:=R+rR+r(4)A:=T(4)A:=T1 1* *T T2 2(5)B:=A(5)B:=A(6)T(6)T3 3:=2:=2* *T T0 0

28、(7)T(7)T4 4:=:=R+rR+r(8)T(8)T5 5:=T:=T3 3* *T T4 4(1)T(1)T0 0:=3.14:=3.14(2)T(2)T1 1:=2:=2* *T T0 0(3)T(3)T2 2:=:=R+rR+r(4)A:=T(4)A:=T1 1* *T T2 2(5)B:=A(5)B:=A(6)T(6)T3 3:=2:=2* *T T0 0(7)T(7)T4 4:=:=R+rR+r(8)T(8)T5 5:=T:=T3 3* *T T4 4(9)T(9)T6 6:=R-r:=R-r(1) T0:=3.14n13.14T0n26.28T1n3n4Rrn5+T2n6*A, B, T3, T4, T5n7T6-n8*