第10章代码优化

1、第第10章章 代码优化代码优化1代码优化的目标代码优化的目标减少目标程序所占用的存储空间；减少目标程序所占用的存储空间；( (空间少空间少) )提高目标程序的运行速度。提高目标程序的运行速度。( (时间短时间短) ) 优化优化可以在编译的不同阶段进行可以在编译的不同阶段进行，通常，通常优化可以再中间代码和目标代码生成之后进优化可以再中间代码和目标代码生成之后进行。本章行。本章讨论的是对中间代码进行等价变换。讨论的是对中间代码进行等价变换。2 根据优化所涉及的程序范围，中间代码根据优化所涉及的程序范围，中间代码优化分为三类：优化分为三类：代码优化的分类代码优化的分类 对对一段一段顺顺序序语句序列

2、语句序列优化。优化。 对中对中循环循环的的代码序列优化。代码序列优化。 在在整个整个程序程序范围内进行的范围内进行的优化。优化。局部优化局部优化循环优化循环优化全局优化全局优化310.1 基本块基本块与程序控制与程序控制流图流图4一、基本一、基本块块基本块：是指程序中一顺序执行的语句序列，基本块：是指程序中一顺序执行的语句序列，其中其中只有只有一个入口语句一个入口语句( (第一个语句第一个语句) )和一个和一个出口语句出口语句( (最后一个语句最后一个语句) )。 对于对于一个基本块来说，执行时只能从其一个基本块来说，执行时只能从其入口语句进入，从其出口语句退出。入口语句进入，从其出口语句退出

3、。5 根据基本块的定义，它是一个按顺序执根据基本块的定义，它是一个按顺序执行的代码序列，而且只能从它的唯一入口进行的代码序列，而且只能从它的唯一入口进入，从其唯一的出口退出，期间不发生任何入，从其唯一的出口退出，期间不发生任何分叉。分叉。任何控制转移四元式任何控制转移四元式出口语句出口语句所转向的目标语句所转向的目标语句入口语句入口语句6 1. 程序的第一个语句；程序的第一个语句；或者或者， 2. 条件转移语句或无条件转移语句的转条件转移语句或无条件转移语句的转 移目标语句；移目标语句；或者或者 3. 紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。入口语句入口语句7划分基本块的步

4、骤划分基本块的步骤1、求四元式序列中各个基本块的、求四元式序列中各个基本块的入口语句入口语句。2、对每一入口语句，构造所属的基本块，该基本块、对每一入口语句，构造所属的基本块，该基本块由：由：（1）该入口语句到下一入口语句（）该入口语句到下一入口语句（不包括不包括下一入口下一入口语句）之间的语句序列组成；或，语句）之间的语句序列组成；或，（2）该入口语句到一转移语句（）该入口语句到一转移语句（包括包括该转移语句）该转移语句）之间的语句序列组成；或，之间的语句序列组成；或，（3）该入口语句到一停语句（）该入口语句到一停语句（包括包括该停语句）之间该停语句）之间的语句序列组成。的语句序列组成。3、

5、凡是未包含在某一基本块中的语句，都是程序中、凡是未包含在某一基本块中的语句，都是程序中控制流程不可达的语句，可删除它们。控制流程不可达的语句，可删除它们。8例子例子 (1) read a (2) read b (3) r:=a mod b (4) if r=0 goto (8) (5) a:= b (6) b:= r (7) goto (3) (8) write b (9) haltB1B2B3B49二、程序控制二、程序控制流程图（流图）流程图（流图）定义：以基本块为结点，控制程序流向定义：以基本块为结点，控制程序流向作作 为有向边，画出的有向图称为流图。为有向边，画出的有向图称为流图。特点：

6、特点： 具有具有唯一唯一首结点的首结点的有向图；有向图； 从首结点开始到流图中任何结点都有通路。从首结点开始到流图中任何结点都有通路。 如果如果一个结点的基本块的入口语句是程一个结点的基本块的入口语句是程序的第一条语句，则称此结点为首结点。序的第一条语句，则称此结点为首结点。10一个控制流程图可表示成一个一个控制流程图可表示成一个三元组：三元组：G=(N，E，n0)N：所有结点：所有结点(基本块基本块)集；集；E：所有有向边集；：所有有向边集；n0 ：首结点。：首结点。11有向边有向边 当下述条件有一个成立时，从结点当下述条件有一个成立时，从结点i有有一有向边引向结点一有向边引向结点j： 基本

7、基本块块j在程序的位置紧跟在在程序的位置紧跟在i后，且后，且i的出的出口语句不是口语句不是无条件无条件转移或停语句；转移或停语句； i的出口是的出口是goto(S)或或if goto(S)，而，而(S)是是j的的入口语句。入口语句。 i j12例子：构造例子：构造以下程序的流图以下程序的流图B1B2B4B313B1B2B3B4 (1) read a (2) read b (3) r:=a mod b (4) if r=0 goto (8) (5) a:= b (6) b:= r (7) goto (3) (8) write b (9) halt10.2 局部优化局部优化14局部优化是指基本块内

8、的优化。局部优化是指基本块内的优化。对于一个给定的程序，可以把它划分为一系对于一个给定的程序，可以把它划分为一系列的基本块。在各个基本块内列的基本块。在各个基本块内分别分别进行优化。进行优化。15一、局部优化种类一、局部优化种类16 在一个基本块内，可以进行合并已知量、在一个基本块内，可以进行合并已知量、删除公共子表达式和删除无用赋值三种优化删除公共子表达式和删除无用赋值三种优化措施。措施。 合并已知量是合并已知量是指在编译时就对指在编译时就对表达式中能计算表达式中能计算的部分先计算，的部分先计算，并用该值替换这并用该值替换这部分表达式，而部分表达式，而不必生成相应的不必生成相应的代码。代码。

9、 删除公共子表删除公共子表达式就是使基本达式就是使基本块内相同的子表块内相同的子表达式只计算一次，达式只计算一次，把重复计算的表把重复计算的表达式删去，从而达式删去，从而避免多余的运算。避免多余的运算。 变量变量A被定值被定值后不再被引用或后不再被引用或未经引用又发生未经引用又发生了对了对A的第二次的第二次定值，则前一定定值，则前一定值为无用赋值，值为无用赋值，应删掉。应删掉。二、基本二、基本块的块的DAG表示表示DAG Directed Acyclic Graph 无环路有向图无环路有向图定义：定义：(1)在一个有向图中，若结点在一个有向图中，若结点ni有弧指向结点有弧指向结点nj，则则ni

10、是是nj的的父结点父结点，nj是是ni的的子结点子结点；(2)若若n1,n2,nk间存在有向弧间存在有向弧n1n2nk，则称则称n1到到nk之间存在一条之间存在一条通路通路，若，若n1=nk，则，则称该通路为称该通路为环路环路；(3)若有向图中任意通路都不是环路，则称该图若有向图中任意通路都不是环路，则称该图为为无环路有向图无环路有向图（DAG）。）。17基本块的基本块的DAG表示表示优化中用到的有向图是一种结点带有下述标优化中用到的有向图是一种结点带有下述标记或附加信息的记或附加信息的DGA:(1) 图图的叶结点以一标识符或常数做标记，的叶结点以一标识符或常数做标记，表示该结点代表该变量或常

11、数的值。表示该结点代表该变量或常数的值。(2) 图图的内部结点以一运算符作为标记；的内部结点以一运算符作为标记；(3) 图图中各个结点上可能附加一个或多个标中各个结点上可能附加一个或多个标识符，表示这些标识符具有该结点所代表识符，表示这些标识符具有该结点所代表的值，简称附标。的值，简称附标。18四元式对应的四元式对应的DAG结点形式结点形式按其四元式对应结点的后继个数分成四种类按其四元式对应结点的后继个数分成四种类型：型：0型、型、1型、型、2型、型、3型。型。0型型：1型：型：2型：型：19例子：构造例子：构造以下基本块的以下基本块的DAG20(1) T0:=3.14(2) T1:=2*T0

12、(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实现基本块优化实现基本块优化DAG图可做到如下三种优化：图可做到如下三种优化：(1) 合并已知量合并已知量 对任何一个四元式，如果其中参与运对任何一个四元式，如果其中参与运算的对象都是编译时的已知量，那么合并算的对象都是编译时的已知量，那么合并已知量，并用合并后算出的常量生成一个已知量，并用合并后算出的常量生成一个叶结点；叶结点；21(2) 利用公共子表达式，删除多余运算利用公共子表达式，删除多余

13、运算 对具有公共子表达式的所有四元式，只对具有公共子表达式的所有四元式，只产生一个计算该表达式值的内部节点，把那产生一个计算该表达式值的内部节点，把那些赋值的变量附加到该节点上。些赋值的变量附加到该节点上。22(3) 删除无用赋值删除无用赋值 如果如果某变量被赋值之后，随后又被赋新某变量被赋值之后，随后又被赋新值，那么可删除对变量的前一个赋值。值，那么可删除对变量的前一个赋值。23n8n8n6n6n7n7n5n5n3n3n1n1n2n2n4n43.14T06.28T1,T3Rr+-T6T2,T4A,T5*B(1) T0:=3.14(2) T1:=6.28(3) T3:=6.28(4) T2:=

14、R+r(5) T4:=T2(6) A:=6.28*T2(7) T5:=A(8) T6:=R-r(9) B:=A*T6由由DAG生成优化后的代码序列生成优化后的代码序列24注意事项注意事项 若若结点有多个附标结点有多个附标A1，A2，An， 有两种情况：有两种情况： (1) 若若结点是叶结点，标记为结点是叶结点，标记为B，则，则A1:=B，A2:=B，An:=B； (2) 若若为内部结点，则除第一附标为内部结点，则除第一附标A1外，其外，其他附标生成他附标生成A2:=A1，A3:=A1，An:=A1。 25DAG在基本块优化中的作用在基本块优化中的作用 将一基本块的每一个四元式依次表示成对应将一

15、基本块的每一个四元式依次表示成对应的一个的一个DAG，再按原来构造，再按原来构造DAG结点的顺结点的顺序重写四元式序列，便可得到序重写四元式序列，便可得到“合并已知常合并已知常量量”、“删除无用赋值删除无用赋值”、“删除多余运算删除多余运算”后的等价基本块。后的等价基本块。对于出了基本块以后不再引用的名字，可以对于出了基本块以后不再引用的名字，可以不生成对其进行的赋值运算，而用临时变量不生成对其进行的赋值运算，而用临时变量存放相应的运算结果。存放相应的运算结果。26例：试对基本块例：试对基本块P (1)应用应用DAG进行优化，进行优化， (2) 假定只有假定只有R、H在基本块出口是活跃的在基本

16、块出口是活跃的,写出优化后的四元式序列。写出优化后的四元式序列。27S0:=2S1:=3/S0S2:=T - CS3:=T + CR:=S0/S3H:=RS4:=3/S1S5:=T + CS6:=S4/S5H:=S6*S2 S0 2n0 S1 1.5n1-n4S2T Cn2n3S3n5+ R/n6, H ,S4,S5, S6 H*n728S0:=2S4:=2S1:=1.5S2:=T - CS3:=T + CS5:=S3R:=2/S3S6:=RH:=R*S229(1) 应用应用DAG进行优化进行优化S0:=2S4:=2S1:=1.5S2:=T - CS3:=T + CS5:=S3R:=2/S3S

17、6:=RH:=R*S2S2:=T - CS3:=T + CR:=2/S3H:=R*S2(2) 假定假定只有只有R、H在基本块出口是活跃在基本块出口是活跃的的3010.3 循环循环优化优化31循环就是程序中那些可能反复执行的代码序循环就是程序中那些可能反复执行的代码序列。因为循环中的代码要反复执行，所以必列。因为循环中的代码要反复执行，所以必须着重考虑循环的代码优化。须着重考虑循环的代码优化。首先要找出程序中的循环，这就需要对程序首先要找出程序中的循环，这就需要对程序的控制流程进行分析。的控制流程进行分析。使用使用控制流程图控制流程图对循环给出定义。对循环给出定义。32一、循环一、循环的性质的性

18、质 在程序流图中，称具有下列性质的在程序流图中，称具有下列性质的结点序列结点序列为一个循环：为一个循环： 1. 它们是它们是强连通强连通的。的。 2. 它们中间它们中间有且只有有且只有一个是一个是入口结点入口结点。33强连通强连通一组结点是强连通的，即：一组结点是强连通的，即：l 其中任意两个结点之间，必有一条通路，其中任意两个结点之间，必有一条通路，使得它们之间使得它们之间相互可达相互可达；l 该通路上各结点都属于该结点序列。该通路上各结点都属于该结点序列。34注意：如果序列中只有一个结点，则必有一注意：如果序列中只有一个结点，则必有一有向边从该结点引到其自身。有向边从该结点引到其自身。入口

19、结点入口结点 所谓入口结点，是指序列中具有下述性所谓入口结点，是指序列中具有下述性质的结点：质的结点： 从序列外某结点，有一有向边引到它，从序列外某结点，有一有向边引到它，或者或者它就是程序流图的首结点。它就是程序流图的首结点。35定义：在程序流图中具有定义：在程序流图中具有唯一入口结点的强连通子唯一入口结点的强连通子图。图。 二、循环二、循环的定义的定义36注意：从循环外要进入注意：从循环外要进入循环，必须首先经过循循环，必须首先经过循环的入口结点。环的入口结点。1243657三、循环三、循环的查找的查找 上面给出了构成循环应具备的条件，为上面给出了构成循环应具备的条件，为了找到程序流图中的

20、循环，需要分析流图中了找到程序流图中的循环，需要分析流图中结点间的控制关系。结点间的控制关系。 为此引入为此引入必经结点必经结点和和必经结点集必经结点集的定义。的定义。37v必经结点：对任意两个结点必经结点：对任意两个结点d和和n，若从首结，若从首结点出发，到达点出发，到达n的各条通路都必须经过的结的各条通路都必须经过的结点点d，称，称d为为n的必经结点，记作的必经结点，记作 d DOM n。v必经结点集：必经结点集：n的全部必经结点的集合，记的全部必经结点的集合，记作作D(n)。38 设设结点结点n的父结点的父结点是是P1，P2，Pk，则：，则：D(n)= n ( D(Pi) 1ik求必经结

21、点集的算法求必经结点集的算法39举例举例D(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,7401243657循环的查找循环的查找 回边回边回边：设回边：设ab是流图中一条是流图中一条有向边，若有向边，若b dom a，则称，则称ab时流图中的一条回边。时流图中的一条回边。411243657图中的回边有：图中的回边有：66，74，42查找循环算法查找循环算法每一条回边构成一个循环：每一条回边构成一个循环： 设设nd是回边，则该回边构成的循环是回边，则该回边构成的循环包括下列结点包括下列结点： n、d以及不经

22、过以及不经过d能到达能到达n的所有结点。的所有结点。42431243657回边回边42循环循环=4 , 2 , 3 , 7 , 5 , 6回边回边74循环循环=7，4，5，6回边回边66循环循环=6查找循环算法查找循环算法(1)找出回边找出回边nd；(2)则则n、d必定属于必定属于nd回边组成的循环回边组成的循环L中中， L:=n,d(3)若若n d且且n的父节点的父节点n不在不在L中，则将中，则将它添它添 加加L中，中，L:=L n(4)对对(3)求出的父节点求出的父节点n重复重复(3)，直至不再，直至不再有有 新新节点加入为止。节点加入为止。44四、循环四、循环优化优化在找出了程序流图中的

23、循环之后，就可以针在找出了程序流图中的循环之后，就可以针对每个循环进行优化工作。对每个循环进行优化工作。循环优化的三种重要技术：循环优化的三种重要技术： 1. 代码外提代码外提 2. 删除归纳变量删除归纳变量 3. 强度削弱强度削弱45用例子初步理解优化措施用例子初步理解优化措施P:=0for I:=1 to 20 do P:=P+AI*BI461.删除多余删除多余运算运算 (删除公共子表达式删除公共子表达式) 对于两个相同的表对于两个相同的表达式计算，若它的达式计算，若它的计算结果相同，则计算结果相同，则没必要重复的生成没必要重复的生成两条运算指令。两条运算指令。(1) P:=0(2) I:

24、=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 I=20 goto(3)T4:=T1472.代码外提代码外提 把结果独立于循环把结果独立于循环执行次数的表达式执行次数的表达式提到循环的前面。提到循环的前面。(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

25、(3)(4)T2:=addr(A)-4(7)T5:=addr(B)-4(6)T4:=T1483.强度削弱强度削弱 把强度大的运算换把强度大的运算换算成强度小的运算。算成强度小的运算。如把乘法换算成加如把乘法换算成加法。法。(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+449(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=

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

27、与复写传播506.删除无用赋值删除无用赋值(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(11)I:=I+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)51循环优化

28、的一些基本概念循环优化的一些基本概念点：程序中某一个四元式的位置点：程序中某一个四元式的位置；定值点：对某变量赋值或输入值的四元式位定值点：对某变量赋值或输入值的四元式位置置；引用点：引用某变量的四元式位置引用点：引用某变量的四元式位置；5253变量变量A的到达与定值：的到达与定值：d是是A的定值点，的定值点，u是是A的引用点，存在一条从的引用点，存在一条从d到到u的通路，并此路的通路，并此路上没有上没有A的其他定值点，称的其他定值点，称d点对点对A的定值能的定值能达到达到u点。点。活跃：存在一条从活跃：存在一条从p点开始的通路，在这条点开始的通路，在这条通路上引用了变量通路上引用了变量A在在

29、p点的值，则称点的值，则称A在在p点是活跃的。点是活跃的。循环不变运算循环不变运算定义：形如定义：形如(s) A:=B op C 四元式，若四元式，若(1) B、C为常量；为常量；(2) 到达到达(s)点的点的B、C定值点都在循环外；定值点都在循环外；则则(s)为循环不变运算，为循环不变运算，A、B、C为循环为循环不变量。不变量。54前置结点前置结点实行代码外提时，在循环实行代码外提时，在循环入口结点入口结点前建立一前建立一个新结点个新结点(基本块基本块)，称作循环的前置结点。，称作循环的前置结点。55代码外提的安全性代码外提的安全性是不是所有循环不变运算的代码都能外提到前是不是所有循环不变运

30、算的代码都能外提到前置结点中？置结点中？不是！不是！下面举例说明几种不合法的代码外提。下面举例说明几种不合法的代码外提。56B1B2B4B557入口入口结点结点出口出口结点结点B1B2 B2B4B5循环循环不变不变运算运算代码外代码外提提j=1j=2原因：原因：B3不是循环出口不是循环出口B4的必经结点。的必经结点。B1B2B3B4B2B4B5 入口入口结点结点出口出口结点结点循环循环不变不变运算运算j=358代码外代码外提提B1 B2 B2B3B4B2B4B5j=2原因原因：循环中还有：循环中还有i的其他定值点。的其他定值点。B1 B2 B2B3B4B2B4B5B1B2B3B4B2B4B55

31、9入口入口结点结点出口出口结点结点循环循环不变不变运算运算j=1代码外代码外提提原因原因：循环中的：循环中的B3中有对中有对i的引用，但到的引用，但到达此处的定值并不仅是达此处的定值并不仅是B4中的中的i:=2。j=2代码外提条件代码外提条件1)该不变运算所在结点该不变运算所在结点(基本块基本块)必须是循环出必须是循环出口结点的必经结点或者该不变运算所定值口结点的必经结点或者该不变运算所定值的不变量在循环出口之后不是活跃的。的不变量在循环出口之后不是活跃的。2)循环内不变运算所定值的变量只有唯一的循环内不变运算所定值的变量只有唯一的一个定值点，即在其他地方未再定值。一个定值点，即在其他地方未再

32、定值。3)外提循环不变运算外提循环不变运算(s) A:=B op C时循环内所时循环内所有有A的引用点必须而且仅是的引用点必须而且仅是(s)所能到达的。所能到达的。60归纳变量归纳变量定义：循环中变量定义：循环中变量I只有唯一的形如只有唯一的形如I:=IC的赋值，其中的赋值，其中C为循环不变量，则称为循环不变量，则称I为循环为循环中中基本归纳变量基本归纳变量。如果变量如果变量J与基本归纳变量与基本归纳变量I可规划为线性关可规划为线性关系系J:=C1*I+C2，其中，其中C1、C2为循环不变量，为循环不变量，则称则称J是是与与I同族的归纳变量同族的归纳变量。61强度削弱与删除归纳变量强度削弱与删除归纳变量 (1)利用循环不变运