编译原理-上课课件第10章代码优化

第10章代码优化❤❤❤2代码优化的目标减少目标程序所占用的存储空间；(空间少)提高目标程序的运行速度。(时间短)优化可以在编译的不同阶段进行，通常优化可以再中间代码和目标代码生成之后进行。本章讨论的是对中间代码进行等价变换。3

根据优化所涉及的程序范围，中间代码优化分为三类：代码优化的分类

对一段顺序语句序列优化。

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

根据基本块的定义，它是一个按顺序执行的代码序列，而且只能从它的唯一入口进入，从其唯一的出口退出，期间不发生任何分叉。任何控制转移四元式出口语句所转向的目标语句入口语句71.程序的第一个语句；或者，

2.条件转移语句或无条件转移语句的转移目标语句；或者

3.紧跟在条件转移语句后面的语句。入口语句8划分基本块的步骤1、求四元式序列中各个基本块的入口语句。2、对每一入口语句，构造所属的基本块，该基本块由：（1）该入口语句到下一入口语句（不包括下一入口语句）之间的语句序列组成；或，（2）该入口语句到一转移语句（包括该转移语句）之间的语句序列组成；或，（3）该入口语句到一停语句（包括该停语句）之间的语句序列组成。3、凡是未包含在某一基本块中的语句，都是程序中控制流程不可达的语句，可删除它们。9例子(1)reada(2)readb(3)r:=amodb(4)ifr=0goto(8)(5)a:=b(6)b:=r(7)goto(3)(8)writeb(9)haltB1B2B3B410二、程序控制流程图（流图）定义：以基本块为结点，控制程序流向作为有向边，画出的有向图称为流图。特点：

具有唯一首结点的有向图；

从首结点开始到流图中任何结点都有通路。如果一个结点的基本块的入口语句是程序的第一条语句，则称此结点为首结点。一个控制流程图可表示成一个三元组：G=(N，E，n0)N：所有结点(基本块)集；E：所有有向边集；n0：首结点。12有向边

当下述条件有一个成立时，从结点i有一有向边引向结点j：①基本块j在程序的位置紧跟在i后，且i的出口语句不是无条件转移或停语句；②i的出口是goto(S)或ifgoto(S)，而(S)是j的入口语句。

ij13例子：构造以下程序的流图B1B2B4B3B1B2B3B4(1)reada(2)readb(3)r:=amodb(4)ifr=0goto(8)(5)a:=b(6)b:=r(7)goto(3)(8)writeb(9)halt§10.2局部优化15局部优化是指基本块内的优化。对于一个给定的程序，可以把它划分为一系列的基本块。在各个基本块内分别进行优化。16一、局部优化种类在一个基本块内，可以进行合并已知量、删除公共子表达式和删除无用赋值三种优化措施。合并已知量是指在编译时就对表达式中能计算的部分先计算，并用该值替换这部分表达式，而不必生成相应的代码。删除公共子表达式就是使基本块内相同的子表达式只计算一次，把重复计算的表达式删去，从而避免多余的运算。变量A被定值后不再被引用或未经引用又发生了对A的第二次定值，则前一定值为无用赋值，应删掉。17二、基本块的DAG表示DAGDirectedAcyclicGraph无环路有向图定义：(1)在一个有向图中，若结点ni有弧指向结点nj，则ni是nj的父结点，nj是ni的子结点；(2)若n1,n2,…,nk间存在有向弧n1n2…nk，则称n1到nk之间存在一条通路，若n1=nk，则称该通路为环路；(3)若有向图中任意通路都不是环路，则称该图为无环路有向图（DAG）。18基本块的DAG表示优化中用到的有向图是一种结点带有下述标记或附加信息的DGA:(1)图的叶结点以一标识符或常数做标记，表示该结点代表该变量或常数的值。(2)图的内部结点以一运算符作为标记；(3)图中各个结点上可能附加一个或多个标识符，表示这些标识符具有该结点所代表的值，简称附标。19四元式对应的DAG结点形式按其四元式对应结点的后继个数分成四种类型：0型、1型、2型、3型。0型：1型：2型：20例子：构造以下基本块的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*T621三、用DAG实现基本块优化DAG图可做到如下三种优化：(1)合并已知量对任何一个四元式，如果其中参与运算的对象都是编译时的已知量，那么合并已知量，并用合并后算出的常量生成一个叶结点；(2)利用公共子表达式，删除多余运算

对具有公共子表达式的所有四元式，只产生一个计算该表达式值的内部节点，把那些赋值的变量附加到该节点上。(3)删除无用赋值

如果某变量被赋值之后，随后又被赋新值，那么可删除对变量的前一个赋值。24n8n6n7n5n3n1n2n43.14T06.28T1,T3Rr+-T6T2,T4A,T5**B(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*T6由DAG生成优化后的代码序列25注意事项若结点有多个附标A1，A2，…，An，

有两种情况：(1)若结点是叶结点，标记为B，则A1:=B，A2:=B，…，An:=B；(2)若为内部结点，则除第一附标A1外，其他附标生成A2:=A1，A3:=A1，…，An:=A1。26DAG在基本块优化中的作用

将一基本块的每一个四元式依次表示成对应的一个DAG，再按原来构造DAG结点的顺序重写四元式序列，便可得到“合并已知常量”、“删除无用赋值”、“删除多余运算”后的等价基本块。对于出了基本块以后不再引用的名字，可以不生成对其进行的赋值运算，而用临时变量存放相应的运算结果。27例：试对基本块P

(1)应用DAG进行优化，

(2)假定只有R、H在基本块出口是活跃的,写出优化后的四元式序列。S0:=2S1:=3/S0S2:=T-CS3:=T+CR:=S0/S3H:=RS4:=3/S1S5:=T+CS6:=S4/S5H:=S6*S2S02n0S11.5n1-n4S2TCn2n3S3n5+R/n6,H,S4,S5,S6H*n729S0:=2S4:=2S1:=1.5S2:=T-CS3:=T+CS5:=S3R:=2/S3S6:=RH:=R*S2(1)应用DAG进行优化30S0:=2S4:=2S1:=1.5S2:=T-CS3:=T+CS5:=S3R:=2/S3S6:=RH:=R*S2S2:=T-CS3:=T+CR:=2/S3H:=R*S2(2)假定只有R、H在基本块出口是活跃的§10.3循环优化32循环就是程序中那些可能反复执行的代码序列。因为循环中的代码要反复执行，所以必须着重考虑循环的代码优化。首先要找出程序中的循环，这就需要对程序的控制流程进行分析。使用控制流程图对循环给出定义。33一、循环的性质

在程序流图中，称具有下列性质的结点序列为一个循环：

1.它们是强连通的。

2.它们中间有且只有一个是入口结点。34强连通一组结点是强连通的，即：其中任意两个结点之间，必有一条通路，使得它们之间相互可达；该通路上各结点都属于该结点序列。注意：如果序列中只有一个结点，则必有一有向边从该结点引到其自身。35入口结点

所谓入口结点，是指序列中具有下述性质的结点：从序列外某结点，有一有向边引到它，或者它就是程序流图的首结点。36定义：在程序流图中具有唯一入口结点的强连通子图。

二、循环的定义注意：从循环外要进入循环，必须首先经过循环的入口结点。124365737三、循环的查找

上面给出了构成循环应具备的条件，为了找到程序流图中的循环，需要分析流图中结点间的控制关系。为此引入必经结点和必经结点集的定义。必经结点：对任意两个结点d和n，若从首结点出发，到达n的各条通路都必须经过的结点d，称d为n的必经结点，记作dDOMn。必经结点集：n的全部必经结点的集合，记作D(n)。39设结点n的父结点是P1，P2，…，Pk，则：D(n)={n}∪

(∩D(Pi))1≤i≤k求必经结点集的算法40举例D(1)={1}D(2)={1,2}D(3)={1,2,3}D(4)={1,2,4}D(5)={1,2,4,5}D(6)={1,2,4,6}D(7)={1,2,4,7}124365741循环的查找—回边回边：设ab是流图中一条有向边，若bdoma，则称ab时流图中的一条回边。1243657图中的回边有：66，74，4242查找循环算法每一条回边构成一个循环：设nd是回边，则该回边构成的循环包括下列结点：n、d以及不经过d能到达n的所有结点。1243657回边42 循环={4,2,3,7,5,6}回边74 循环={7，4，5，6}回边66 循环={6}44查找循环算法(1)找出回边nd；(2)则n、d必定属于nd回边组成的循环L中，L:={n,d}(3)若n≠d且n的父节点n’不在L中，则将它添如L中，L:=L∪{n’}(4)对(3)求出的父节点n重复(3)，直至不再有新节点加入为止。45四、循环优化在找出了程序流图中的循环之后，就可以针对每个循环进行优化工作。循环优化的三种重要技术：

1.代码外提

2.删除归纳变量

3.强度削弱46用例子初步理解优化措施P:=0forI:=1to20doP:=P+A[I]*B[I]471.删除多余运算(删除公共子表达式)

对于两个相同的表达式计算，若它的计算结果相同，则没必要重复的生成两条运算指令。(1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2[T1](6)T4:=4*I(7)T5:=addr(B)-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(3)T4:=T1482.代码外提把结果独立于循环执行次数的表达式提到循环的前面。(1)P:=0(2)I:=1(3)T1:=4*I(5)T3:=T2[T1](8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(3)(4)T2:=addr(A)-4(7)T5:=addr(B)-4(6)T4:=T1493.强度削弱把强度大的运算换算成强度小的运算。如把乘法换算成加法。(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(5)(3)T1:=4*I(3‘)T1:=T1+450(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)ifI<=20goto(5)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)ifgoto(5)(3)T1:=4T1T1<=80

4.变换循环控制条件5.合并已知量与复写传播516.删除无用赋值(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)ifT1<=80goto(5)(1)P:=0(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(3’)T1:=T1+4(12)ifT1<=80goto(5)52循环优化的一些基本概念点：程序中某一个四元式的位置；定值点：对某变量赋值或输入值的四元式位置；引用点：引用某变量的四元式位置；53变量A的到达与定值：d是A的定值点，u是A的引用点，存在一条从d到u的通路，并此路上没有A的其他定值点，称d点对A的定值能达到u点。活跃：存在一条从p点开始的通路，在这条通路上引用了变量A在p点的值，则称A在p点是活跃的。54循环不变运算定义：形如(s)A:=BopC四元式，若(1)B、C为常量；(2)到达(s)点的B、C定值点都在循环外；则(s)为循环不变运算，A、B、C为循环不变量。55前置结点实行代码外提时，在循环入口结点前建立一个新结点(基本块)，称作循环的前置结点。56代码外提的安全性是不是所有循环不变运算的代码都能外提到前置结点中？不是！下面举例说明几种不合法的代码外提。B1→B2→B4→B557入口结点出口结点B1→B2’→B2→B4→B5循环不变运算代码外提j=1j=2原因：B3不是循环出口B4的必经结点。B1→B2→B3→B4→B2→B4→B5入口结点出口结点循环不变运算j=358代码外提B1→B2’→B2→B3→B4→B2→B4→B5j=2原因：循环中还有i的其他定值点。59B1→B2’→B2→B3→B4→B2→B4→B5B1→B2→B3→B4→B2→B4→B5入口结点出口结点循环不变运算j=1代码外提原因：循环中的B3中有对i的引用，但到达此处的定值并不仅是B4中的i:=2。j=260代码外提条件1)该不变运算所在结点(基本块)必须是循环出口结点的必经结点或者该不变运算所定值的不变量在循环出口之后不是活跃的。2)循环内不变运算所定值的变量只有唯一的一个定值点，即在其他地方未再定值。3)外提循环不变运算(s)A:=BopC时循环内所有A的引用点必须而且仅是(s)所能到达的。61归纳变量定义：