课件演示文稿第十章

1、 什么是代码优化优化技术简介第十章代码优化第十章代码优化某些编译程序在中间代码或目标代码生成之后要对生成的代码进行优化。所谓优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也不同，在同一范围内，可进行多种优化 优化分类优化分类: :按阶段分按阶段分与机器无关的优化与机器无关的优化 对中间代码进行对中间代码进行 依赖于机器的优化依赖于机器的优化 对目标代码进行对目标代码进行根据优化所涉及的程序范围分成:(1)局部优化:(基本块)(2)循环优化:对循环中的代码进行优

2、化(3)全局优化:大范围的优化优化工作 数据流分析 控制流分析 优化技术简介1.删除多余运算2.循环不变代码外提3.强度削弱4.变换循环控制条件5.合并已知量与复写传播6.删除无用赋值例：P:=0for :=1 to 20 do P:=P+A*B(1)P:=0(2):=1(3)T1:=4*(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=4*(7)T5:=addr(B)-4(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11):=+1(12)if =20 goto(3)1.删除多余运算2.循环不变代码外提(1)P:=0(2):=1(3)T1:=4*(4)

3、T2:=addr(A)-4(5)T3:=T2T1(6)T4:=4*(7)T5:=addr(B)-4(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11):=+1(12)if =20 goto(3)(1)P:=0(2):=1(3)T1:=4*(5)T3:=T2T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11):=+1(12)if =20 goto(3)(4)T2:=addr(A)-4(7)T5:=addr(B)-4(6)T4:=T13.强度削弱(1)P:=0(2):=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:

4、=4*(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11):=+1(12)if =20 goto(3)(1)P:=0(2):=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):=+1(12)if =20 goto(5)(3)T1:=4*I(3)T1:=T1+44.变换循环控制条件5.合并已知量与复写传播(1)P:=0(2):=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T

5、1:=4*(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11):=+1(3)T1:=T1+4(12)if =20 goto(5)(1)P:=0(2):=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T1 (9)T7:=T3*T6(10)P:=P+T7(11):=+1(3)T1:=T1+4(12)if T1 =80 goto(5)(3)T1:=46.删除无用赋值(1)P:=0(2):=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)

6、T1:=4(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T1(9)T7:=T3*T6(10)P:=P+T7(11):=+1(3)T1:=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)局部优化：基本块内的优化基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。入口语句：、程序的第一个语句；或者，、条件转移语句或无条件

7、转移语句的转移目 标语句；或者、紧跟在条件转移语句后面的语句。 划分基本块的算法：、求出四元式程序之中各个基本块的入口语 句。、对每一入口语句，构造其所属的基本块。 它是由该语句到下一入口语句（不包括下 一入口语句），或到一转移语句（包括该 转移语句），或到一停语句（包括该停语 句）之间的语句序列组成的。、凡未被纳入某一基本块的语句，都是程序 中控制流程无法到达的语句，因而也是不 会被执行到的语句，我们可以把它们删除。 (1)P:=0(2):=1B1(3)T1:=4*(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=4*(7)T5:=addr(B)-4(8)T6:=T5T4

8、B2(9)T7:=T3*T6(10)P:=P+T7(11):=+1(12)if = C goto L2(6) B:=B+1(7) goto L1(8) L2: write (A)(9) halt基本块的基本块的DAG表示表示DAG Directed Acyclic Graph 无环路有向图n1n2n3n4n1n2n3n5n4n6n7n8n9在一个有向图中，我们称任一有向边ninj（或表示为有序对（ni,nj）中的结点ni为结点nj的前驱（父结），结点nj为结点ni的后继（子结）。又称任一有向边序列n1n2, n2n3,nk1nk为从结点n1到结点nk的一条通路。如果其中n1=nk，则称通路为环

9、路。该结点序列也记为（n1 ,n2,nk）。n1n2n3n4n1n2n3n5n4n6n7n8n9图中有向图的通路（n2 ,n2）和（n3 ,n4 ,n3）就是环路。如果有向图中任一通路都不是环路，则称该有向图为无环路有向图，简称DAG。 有向图就是一个DAG。在DAG中，如果（n1 ,n2, nk）是其中一条通路，则称结点n1为结点nk的祖先，结点nk为结点n1的后代。我们这一节中要用到的有向图，是一种其结点带有标记或附加信息的DAG： 1、图的叶结点，即无后继的结点，以一标识符（变量名）或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址，则用addr（A）作为该

10、结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。2、图的内部结点，即有后继的结点以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。3、图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。 上述这种DAG可用来描述计算过程，又称描述计算过程的DAG。在以下的讨论中，我们简称DAG。一个基本块，可用一个DAG来表示。下面列出各种四元式及相对应的DAG的结点形式。1、图中ni为结点编号2、结点下面的符号（运算符、标识符或常 数）是各结点的标记3、各结点右边的标识符是结点的附加标识符。 基本块的基本块的DAG表示与构

11、造表示与构造DAG结点结点n1 A B n2 A op n1 B四元式四元式0型：型：A:=B(:=,B,A) 1型型: A:=op B(op,B,A)2型型: A:=B op C(op, B, C,A) n3 Aop n1 n2B Cn1n2n1n3n1n2用DAG进行基本块的优化仅含0，1，2型四元式的基本块的DAG构造算法:首先，DAG为空。对基本块的每一四元式，依次执行：DAG构造算法构造算法、如果NODE（B）无定义，则构造一标记为B的叶结点并定义NODE（B）为这个结点；如果当前四元式是0型，则记NODE(B)的值为n，转4。如果当前四元式是1型，则转2(1）。如果当前四元式是2型

12、，则：()如果NODE(1)无定义，则构造一标记为C的叶结点并定义NODE(C) 为这个结点；() 转2 .(2)。2、（1）如果NODE(B)是标记为常数的叶结点 ，则转2(3)，否则转3.（1）。（2）如果NODE(B)和NODE(C)都是标记为常数的叶结点，则转2.（4），否则转3.（2）。（3）执行op B（即合并已知量），令得到的新常数为P。如果NODE(B)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4.。（4）执行B op C（即合并已知量），令得到的新常数为P。如果NODE(B)或NODE(C)是

13、处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4。3、（1）检查DAG中是否已有一结点，其唯一 后 继为NODE(B)，且标记为op（即找公共子表 达式）。如果没有，则构造该结点n，否则就 把已有的结点作为它的结点并设该结点为n，转4.（2）检查中DAG中是否已有一结点，其左后继 为NODE(B)，其右后继为NODE(C)，且标记为 op（即找公共子表达式）。如果没有，则构造该 结点n，否则就把已有的结点作为它的结点并设 该结点为n，转4.。 4、 如果NODE（A）无定义，则把A附加在结点n上并令NODE（A）=

14、n；否则先把A从NODE（A）结点上的附加标识符集中删除（注意，如果NODE（A）是叶结点，则其标记A不删除），把A附加到新结点n上并令NODE（A）= n。转处理下一四元式。 而后，我们可由DAG重新生成原基本块的一优化的代码序列。 构造以下基本块构造以下基本块G的的DAG。 To 3.14 (a)n1T0:=3.14 T0 T1 3.14 6.28 (b)n2n1T0:=3.14T1:=2*T0 T2 + T0 T1 3.14 6.28 R r (c)n2n5n3n1n4T0:=3.14T1:=2*T0T2:=R+r A * T2 + T0 T1 3.14 6.28 R r (d)n2n5

15、n3n1n4n6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2 A,B * T2 + T0 T1 3.14 6.28 R r (e)n2n5n3n1n4n6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=A A,B * T2 + T0 T1,T3 3.14 6.28 R r (f)n2n5n3n1n4n6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0 A,B * T2,T4 + T0 T1,T3 3.14 6.28 R r (g)n2n5n3n1n4n6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:

16、=AT3:=2*T0T4:=R+r A,B,T5 * T2,T4 + T0 T1,T3 3.14 6.28 R r (h)n2n5n3n1n4n6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rT0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rB:=T5*T6DAG的应用我们将四元式表示成DAG后，可以利用DAG进

17、行优化首先由DAG构造优化的四元式序列在构造相应的DAG的过程中已经进行了一些基本的优化工作而后，可由DAG重新生成原基本块的一个优化的代码序列T0:=3.14T1:=6.28T3:=6.28T2:=R+rT4:=T2A:=6.28*T2T5:=AT6:=R-rB:=A*T6T0:=3.14T1:=6.28T3:=6.28T2:=R+rT4:=T2A:=6.28*T2T5:=AT6:=R-rB:=A*T6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rB:=T5*T6优化后：优化后：例：赋值语句例：赋值语句 T

18、4:=A+B-(E-(C+D)四元式序列四元式序列GT1：=A+BT2：=C+DT3：=E-T2T4：=T1-T3DAG： A B E C Dn9n3n8n1n2n7n6n4n5 T4 T1 T3 T2 + - - + 控制流分析和循环优化：控制流程图（流图）：具有唯一首结点的有向图G=（N，E，n0） N：结点集 基本块集 E：有向边集 n0：首结点 包含程序第一个语句的基本块分析程序流图中结点间的关系m DOM n 定义（定义（必经结点） 在程序流图中,对任意两个结点m和n,如果从流图的首结点出发,到达n的任意通路都要经过m,则称m是n的必经结点,记为m DOM n集集 定义定义 结点结点n的