编译原理-第十章-代码优化

/第十章代码优化某些编译程序在中间代码或目标代码生成之后要对生成的代码进行优化。所谓优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也不同，在同一范围内，可进行多种优化。一般，优化工作阶段可在中间代码生成之后和（或）目标代码生成之后进行。中间代码的优化是对中间代码进行等价变换。目标代码的优化是在目标代码生成之后进行的，因为生成的目标代码对应于具体的计算机，因此，这一类优化在很大程度上依赖于具体的机器，我们不做详细讨论。另外依据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化三个不同的级别。局部优化指的是在只有一个入口、一个出口的基本程序块上进行的优化。循环优化对循环中的代码进行的优化。全局优化是在整个程序范围内进行的优化。本章重点：局部优化基本块的DAG表示第一节优化技术简介为了说明问题，我们来看下面这个例子，源程序是：P:=0ForI:=1to20doP:=P+A[I]*B[I];经过编译得到的中间代码如图10-1-1所示，这个程序段由B1和B2两个部分组成，B2是一个循环，假定机器按字节编址。那么，对于这个中间代码段，可进行如下这些优化。1、删除多余运算（删除公共子表达式）优化的目的在于使目标代码执行速度较快。图10-1-1中间代码（3）和（6）中都有4＊I的运算，而从（3）到（6）没有对I赋值，显然，两次计算机的值是相等的。所以，（6）的运算是多余的。我们可以把（6）变换成：T4:=T1。这种优化称为删除多余运算或称为删除公共子表达式。 B B1B2图10-1-1中间代码段(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)2、代码外提减少循环中代码总数的一个重要办法是代码外提。这种变换把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面。使之只在循环外计算一次，上例中，我们可以把（4）和（7）提到循环外。经过删除多余运算和代码外提后，代码变成图10-1-2。 B1B2图10-1-3强度削弱(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) B1B2图10-1-2删除公共子表达式和代码外提(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(12)ifI≤20goto(3)3、强度削弱强度削弱的思想是把强度大的运算换算成强度小的运算。例如把乘法运算换成加法运算等等。在图10-1-2的循环中，每循环一次，I的值增1，T1的值与I保持线性关系，每次总是增加4。因此，我们可以把循环中计算T1值的乘法运算变换成在循环前进行一次乘法运算，而在循环中将其变换成加法运算。变换后如图10-1-3所示。4、变换循环控制条件图10-1-3的代码中，I和T1始终保持T1=4*I的线性关系，这样可以把（12）的循环控制条件I≤20变换成T1≤80，这样整个程序的运行结果不变。这种变换称为变换循环控制条件。经过这一变换后，循环中I的值在循环后不会被引用，四元式（11）可以从循环中删除，这就是我们的目的所在。5、合并已知量与复写传播图10-1-3中，四元式（3）计算4*I时，I必为1。所以（3）中的4*I的两个运算对象都是编码时的已知量，可在编译时计算出它的值，即（3）可变为T1=4这种变换称为合并已知量。图10-1-3中，（6）把T1的值复写到T4中，四元式（8）要引用T4的值，而（6）到（8）之间未改变T4和T1的值，则（8）改为T6:=T5[T1]，之后运算结果保持不变。这种变换称为复写传播。图10-1-3经过变换循环控制条件，合并已知量和复写传播等变换后，变为图10-1-4。 B1B2图10-1-4(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[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3´)T1:=T1+4(12)ifI≤80goto(5) B1B2图10-1-5删除无用赋值(1)P:=0(4)T2:=addr(A)－4(7)T5:=addr(B)－4(3)T1:=4(5)T3:=T2[T1](8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(3´)T1:=T1+4(12)ifI≤80goto(5)6、删除无用赋值在图11.5中，（6）对T4赋值，但T4未被引用；另外，（2）和（11）对I赋6、删除无用赋值在图10-1-4中，（6）对T4赋值，但T4未被引用；另外，（2）和（11）对I赋值，但只有（11）引用I。所以，只要程序中其它地方不需要引用T4和I，则（6），（2）和（11）对程序的运行结果无任何作用。我们称之为无用赋值，无用赋值可以从程序中删除，如图10-1-5所示（设（6）（2）（11）为无用赋值）。比较图10-1-1和图10-1-5可看出，经过优化后的代码的执行效率提高了很多。当然，实现这些优化的代价也是很大的。第二节局部优化我们所说的局部优化是指基本块内的优化，所谓基本块，是指程序中一顺序执行语句序列，其中只有一个入口语句和一个出口语句。执行时只能从其入口语句进入，从其出口语句退出。对于一个给定的程序，我们可以把它划分为一系列的基本块。在各基本块的范围内分别进行优化。一、基本块的划分在介绍基本块的构造之前，我们先定义基本块的入口语句，所谓入口语句，严格地说来就是：1、程序的第一语句；或者，2、条件转移语句或无条件转移语句的转移目标语句；或者，3、紧跟在条件转移语句后面的语句。有了入口语句的概念之后，我们就可以给出划分中间代码（四元式程序）为基本块的算法，其步骤如下：1、求出四元式程序中各个基本块的入口语句。2、对每一入口语句，构造其所属的基本块。它是由该入口语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成的。3、凡未被纳入某一基本块的语句、都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，我们可以把它们删除。我们仍以上一节所述的例子来说明，对于图10-1-1中的代码段，由规则1，语句（1）是入口语句，由规则2，语句（3）是入口语句。由规则3，跟随语句（12）的语句是入口语句，这样，语句（1）和（2）构成一个基本块，语句（3）—（12）构成一个基本块，也即图10-1-1中的B1和B2。二、基本块的变换很多变换可作用于基本块而不改变它计算的表达式集合，这样的变换对改进代码的质量是很有用的。有两类重要的局部等价变换可用于基本块，它们是保结构的变换和代数变换。基本块的主要保结构变换是1、删除公共子表达式2、删除无用代码3、重新命名临时变量4、交换语句次序对于1和2，我们在第一节已经讨论过，在此简单讨论一下3和4。重新命名临时变量：假如有语句t:=b+c，其中t是临时变量。如果把这个语句改为u:=b+c，其中u是新的临时变量，并且把这个t的所有引用改成u，那么基本块的运算结果不变。交换语句次序：如果基本块有两个相邻的语句：t1:=b+ct2:=x+y当且仅当x和y都不是t1，b和c都不是t2时我们可以交换这两个语句的次序。有许多代数变换可以把基本块计算的表达式集合变换成代数等价的集合。其中有用的变换是那些可以简化表达式或用较快运算代替较慢运算的变换。例如：x:=x+0或x:=x*1这样的语句可以从基本块中删除而不改变它计算的表达式集合，又如x:=y**2的指数算符通常要用函数调用来实现，使用代数变换，这个语句可由快速、等价的语句x:=y*y来代替。第三节基本块的DAG表示n1n1n2n3n4n1n2n3n5n4n6n7n8n9图10-3-1有向图图10-3-2DAG先将我们所需使用的DAG作一说明。在一个有向图中，我们称任一有向边ni→nj（或表示为有序对（ni,nj））中的结点ni为结点nj的前驱（父结），结点nj为结点ni的后继（子结）。又称任一有向边序列n1→n2,n2→n3,…,nk—1→nk为从结点n1到结点nk的一条通路。如果其中n1=nk，则称通路为环路。该结点序列也记为（n1,n2,…,nk）。例如，图10-3-1中有向图的通路（n2,n2）和（n3,n4,n3）就是环路。如果有向图中任一通路都不是环路，则称该有向图为无环路有向图，简称DAG。图10-3-2的有向图就是一个DAG。在DAG中，如果（n1,n2,…,nk）是其中一条通路，则称结点n1为结点nk的祖先，结点nk为结点n1的后代。我们这一节中要用到的有向图，是一种其结点带有下述标记或附加信息的DAG：1、图的叶结点，即无后继的结点，以一标识符（变量名）或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来代表某变量A的位置，则用addr（A）作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。2、图的内部结点，即有后继的结点以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。3、图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。上述这种DAG可用来描述计算过程，又称描述计算过程的DAG。在以下的讨论中，我们简称DAG。下面讨论基本块的DAG表示与构造。一个基本块，可用一个DAG来表示。下面（图10-3-3）列出各种四元式及相对应的DAG的结点形式。图中ni为结点编号，结点下面的符号（运算符、标识符或常数）是各结点的标记，各结点右边的标识符是结点的附加标识符。四元式 DAG结点opBAnopBAn1An2Bn1（1）A：=opB（op，B，—，A）CCn2opAn3Bn1（2）A：=BopC（op，B，C，A）=[]=[]Cn2An3Bn1（3）A：=B[C]（=[]，B[C]，—，A）

rop

ropCn2(S)n3Bn1（4）ifBropCgoto(s)(jrop,B,C,(S))DDB[]=Cn3(S)90()n4n2n1N1(S)90()（5）D[C]：=B（[]=，B，—，D[C]）（6）goto(s)(j，—，—，(S))图10-3-3四元式与DAG结点接着给出一种构造基本的DAG算法。假设DAG各结点信息将用某种适当的数据结构来存放。并设有一个标识符（包括常数）与结点的对应表。NODE（A）是描述这种对应关系的一个函数，它的值或者是一个结点的编号n，或者无定义。前一个情况代表DAG中存在一个结点n,A是其上的标记或附加标识符。我们把图10-3-3中各形式的四元式按其对应结点的后继个数分为四类。其中，四元式（0）称为0型，（1）称为1型；（2）和（3）称为2型；（5）称为3型。对于3型四元式，由于对数组元素赋值的情形需特殊考虑，因此暂不讨论，对四元式（6）也不涉及，下面是仅含0,1,2型四元式的基本块的DAG构造算法。首先，DAG为空。对基本块的每一四元式，依次执行：1、如果NODE（B）无定义，则构造一标记为B的叶结点并定义NODE（B）为这个结点；如果当前四元式是0型，则记NODE（B）的值为n，转4。如果当前四元式是1型，则转2．（１）。如果当前四元式是2型，则：（1）如果NODE（C）无定义，则构造一标记为C的叶结点并定义NODE（C）为这个结点，（2）转2．（2）。2、（1）如果NODE（B）的标记为常数的叶结点，则转2（3），否则转3．（１）。（2）如果NODE（B）和NODE（C）都是标记为常数的叶结点，则转2．（4），否则转3．（2）。（3）执行opB（即合并已知量），令得到的新常数为P。如果NODE（B）是处理当前四元式时新构造出来的结点，则删除它。如果NODE（P）无定义，则构造一用P做标记的叶结点n。置NODE（P）=n，转4．。3、（1）检查DAG中是否已有一结点，其唯一后继为NODE（B），且标记为op（即找公共子表达式）。如果没有，则构造该结点，否则就把已有的结点作为它的结点并设该结点为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。转处理下一四元式。例1试构造以下基本块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*T6r=+R=+3.14=+3.14=+6.28=+r=+R=+3.14=+3.14=+6.28=+3.14=+6.28=+T1=++=+T2n5n3n4T0=+n1n2T1=+T0=+n1n2T0=+n1(a)(b)(c)TT2r=+3.14=+6.28=+T1=++=+T0=+n1n2T1=+n43.14=+6.28=+T1=+T0=+n1n2R=+r=+n3n4*=+T2A,Bn6n5+=+T2An5*=+n6R=+n3(d)(e)*=+r*=+r=+3.14=+6.28=+T1=++=+T0=+n1n2T1=+n4(f)(g)3.14=+6.28=+T1,T3=+T0=+n1n2R=+r=+n4*=+T2,T4A,Bn6n5+=+T2A,Bn5n6T1,T3=+R=+n3n3T0T1,T3+－T6T2,T4*n8n5n7*rn4Rn33.14n16.28n2A,B,T5n6(j)A,B,T5T0T1,T3+T6*n6rRn36.28n2－3.14n1n4T2,T4n7n5(i)A,B,T5T1,T3+*n6rRn36.28n23.14n1n4T2,T4n5(h)T0T0图10-3-4由四元式构造的DAG第四节代码生成概述代码生成是把经过语法分析或优化后的中间代码作为输入，将其转换成特定机器的机器语言或汇编语言作为输出，这样的转换程序称为代码生成器，因此，代码生成器的构造与输入的中间代码形式和输出的目标代码的机器结构密切相关。特别是高级语言和计算机的多种多样性为代码生成的理论研究和实现技术带来很大的复杂性。由于一个高级程序设计语言的目标代码需反复使用，因而，代码生成器的设计要着重考虑目标代码的质量问题。衡量目标代码的质量主要从占用空间和执行效率两个方面综合考虑。到底产生什么样的目标代码取决于具体的机器结构、指令格式、字长及寄存器的个数和种类，并与指令的语义和所用操作系统、存储管理等都密切相关。目标代码的执行效率在很大程度上依赖于寄存器的使用。第五节习题一、单项选择题1、优化可生成 的目标代码。 a．运行时间较短 b．占用存储空间较小c．运行时间短但占用内存空间大 d．运行时间短且占用存储空间小2、下列 优化方法不是针对循优化进行的。 a．强度削弱 b．删除归纳变量 c．删除多余运算 d．代码外提3、基本块内的优化为 。 a．代码外提，删除归纳变量 b．删除多余运算，删除无用赋值c．强度削弱，代码外提 d．循环展开，循环合并4、关于必经结点的二元关系，下列叙述中不正确的是 。 a．满足自反性 b．满足传递性 c．满足反对称性 d．满足对称性5、对一个基本块来说， 是正确的。 a．只有一个入口语句和一个出口语句 b．有一个入口语句和多个出口语句c．有多个入口语句和一个出口语句 d．有多个入口语句和多个出口语句6、在程序流图中，我们称具有下述性质 的结点序列为一个循环。 a．它们是非连通的且只有一个入口结点 b．它们是强连通的但有多个入口结点c．它们是非连通的但有多个入口结点 d．它们是强连通的且只有一个入口结点7、 不可能是目标代码。 a．汇编指令代码 b．可重定位指令代码 c．绝对指令代码 d．中间代码[解答]1、优化的目的是使目