编译原理 第5章代码优化

上章主要内容回顾属性文法中间代码的形式赋值语句的翻译布尔表达式的翻译控制流语句的翻译第五章代码优化概述局部优化循环优化全局优化概述代码优化示例一、代码优化概述代码优化的含义:对代码进行各种等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加快，或占用存储空间减少，或两者都有，代码优化的目的是提高目标程序的质量。三条优化原则：（1）等价:是指不改变程序的运行结果；（2）有效:主要指优化后的代码运行时间较短,以及占用的存储空间较小。（3）合算:应尽可能以较低的代价取得较好的优化效果。代码优化的时机：优化可在编译的各个阶段进行。最主要的时机是在语法、语义分析生成中间代码之后，在中间代码上进行。这一类优化不依赖于具体的计算机，而取决于语言的结构。代码优化的分类：依据是否与机器相关分（1）与机器相关的优化在目标代码生成之后进行，针对的是目标代码。优化内容包括：寄存器优化、多处理器优化、特殊指令优化、无用指令消除等。（2）与机器无关的优化在中间代码生成之后进行，针对的是中间代码。与机器无关的优化更具有普遍意义，可以适用于多种物理机器的代码生成程序。源代码前端中间代码代码生成目标代码中间代码优化目标代码优化依据优化所涉及的程序范围分（1）局部优化——针对基本程序块（2）循环优化——针对循环体（3）全局优化——针对整个程序代码优化实例:例：P:=0forI:=1to20doP:=P+a[I]*b[I]1.删除多余运算2.代码外提3.强度削弱4.变换循环控制条件5.合并已知量6.复写传播7.删除无用赋值优化技术简介：1.删除多余运算（删除公共子表达式）(3)、(6)计算出的值相等(4*I），且从（3）到（6）没有对I进行赋值，所以可以将(6)变换为T4：=T1。2.代码外提减少循环中代码总数的一个重要办法是代码外提。这种将循环不变运算，即其结果独立于循环次数的表达式，提到循环前面，使之只在循环外计算一次。在这里，(4)、(7)外提。(1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=a-4(5)T3:=T2[T1](6)T4:=4*I(7)T5:=b-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)IfI=20goto(3)B1B2T4:=T1优化技术简介：3.强度削弱把强度大的运算换算成强度小的运算，如乘方变乘法，乘法变加法等等。对于本例中，由于T1与I是线性关系，每次I增1，T1增4，所以可以把循环中计算T1值的乘法运算变换成在循环前进行一次乘法运算，而在循环中将其变成加法运算。即(3)外提，在(12)前增加一条语句(3′)T1：=T1+4(1)P:=0(2)I:=1(4)T2:=a-4(7)T5:=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)B1B2(3′)T1:=T1+4优化技术简介：4.变换循环控制条件在上面的代码中，I和T1始终保持T1=4*I的线性关系，这样可以把将(12)的循环控制条件I=20变换成T1=80，这样变换后整个程序的运行结果不变，但若I在循环后不会被引用，则四元式（11）可以从循环中删除。(1)P:=0(2)I:=1(4)T2:=a-4(7)T5:=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)B1B2T1=80优化技术简介：5.合并已知量与复写传播在四元式（3）计算4*I时，I必为1，所以（3）中的4*I的两个运算对象都是编译时的已知量，可在编译时计算出它的值，即（3）可变为T1：=4。这叫合并已知量。另外，（6）把T1的值复写到T4中，四元式（8）要引用T4的值，而（6）到（8）之间未改变T4和T1的值，则（8）可改为T6：=T5[T1]之后运算结果保持不变。这种变换称为复写转播。(1)P:=0(2)I:=1(4)T2:=a-4(7)T5:=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(3′)T1:=T1+4(12)IfT1=80goto(5)B1B2(3)T1:=4（8）T6:=T5[T1]优化技术简介：6.删除无用赋值T4和I未被引用，相关赋值语句可删除。(1)P:=0(2)I:=1(4)T2:=a-4(7)T5:=b-4(3)T1:=4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(3′)T1:=T1+4(12)IfT1=80goto(5）B1B2(1)P:=0(4)T2:=a-4(7)T5:=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）B1B2(1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=a-4(5)T3:=T2[T1](6)T4:=4*I(7)T5:=b-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)IfI=20goto(3)B1B2优化前优化后优化后的代码序列具有以下特点：（1）减少了循环体内可执行代码，由10条减至6条，总代码由12条减至10条。（2）减少了做乘法运算的次数，由3次降为1次。（3）减少了全程范围内使用的变量，如I,T4等变量。注意：虽然经过一系列优化后的代码其执行效率明显提高，但是优化工作越多，编译系统的代价就会越大。因此，对某种程序设计语言翻译要实施什么优化，应该视语言的特点具体分析，力争设计一个最适合本语言特点的优化策略。二、局部优化局部优化是指对代码的每一个线性部分所进行的优化，使得在这个线性部分只存在一个入口和一个出口，而这个线性部分我们称之为基本块。1.基本块定义所谓基本块，是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是该序列的第一个语句，出口就是该序列的最后一个语句。对一个基本块来说，执行时只能从其入口进入，从其出口退出。对一个给定的程序，我们可以把它划分为一系列基本块，在各个基本块范围内进行的优化称为局部优化。划分基本块的关键问题是准确定义入口和出口语句。2.划分基本块的算法（1）确定满足以下条件的入口语句①代码序列的第一个语句；②能由条件转移语句或无条件转移语句转移到的语句；③紧跟在条件转移语句后面的语句。（2）确定满足以下条件的出口语句①下一个入口语句的前导语句；②转移语句(包括转移语句自身)；③停语句(包括停语句自身)。一个入口语句对应一个基本块。构造某入口语句对应的基本块的方法是：该基本块由该入口语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句）或到一停语句（包括该停语句）之间的代码序列组成。3.划分基本块的例子例1：对于右图中的代码段：由规则①，语句（1）是入口语句；由规则②，语句（3）是入口语句；由规则③，跟随语句（12）的语句是入口语句；这样，语句（1）和（2）构成一个基本块B1，语句（3）-（12）构成一个基本块B2。(1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=a-4(5)T3:=T2[T1](6)T4:=4*I(7)T5:=b-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)IfI=20goto(3)B1B2基本块内可进行的优化包括：删除公共子表达式、复写传播、合并已知量、删除无用赋值等。优化技术简介中1、5、6是局部优化，即基本块优化。例2：考察下面求最大公因子的三地址代码程序：(1) readX(2) readY(3) R=X%Y(4) ifR=0goto(8)(5) X=Y(6) Y=R(7) goto(3)(8) writeY(9) halt4.基本块的DAG表示DAG(DirectedAcyclicGraph)是一种有向图，常常用来对基本块进行优化。一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG：n5n3n4T2Rr+n1T03.14n2T16.28n6A,B*(1)图的叶结点以一标识符(变量名)或常数作为标记，表示该结点代表该变量或常数的值。(2)图的内部结点以一运算符作为标记，表示该结点代表应用该运算符对其直接后继结点所代表的值进行运算的结果。(3)图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。一个基本块由一个四元式序列组成，且每一个四元式都可以用相应的DAG结点表示。图5-1给出了不同四元式和与其对应的DAG结点形式。图5-1四元式与DAG结点图中，各结点圆圈中的ni是构造DAG过程中各结点的编号，而各结点下面的符号(运算符、标识符或常数)是各结点的标记，各结点右边的标识符是结点上的附加标识符。除了对应转移语句的结点右边可附加一语句位置来指示转移目标外，其余各类结点的右边只允许附加标识符。除对应于数组元素赋值的结点(标记为[]= )有三个后继外，其余结点最多只有两个后继。5.DAG进行基本块优化的基本思想首先按基本块内的四元式序列顺序将所有的四元式构造成一个DAG，然后按构造结点的次序将DAG还原成四元式序列。由于在构造DAG的同时已做了局部优化，所以最后所得到的是优化过的四元式序列。6.DAG进行基本块优化的例子试构造以下基本块的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*T6n1T03.14(1)T0=3.14n3n1n2T16.283.142*(2)T1=2*T0T0n5n3n4T2Rr+(3)T2=R+rn1T03.14n2T16.28n5n3n4T2Rr+(4)A=T1*T2n1T03.14n2T16.28n6A*n5n3n4T2Rr+(5)B=An1T03.14n2T16.28n6A,B*n5n3n4T2Rr+(6)T3=2*T0n1T03.14n2T1,T36.28n6A,B*n5n3n4T2,T4Rr+(7)T4=R+rn1T03.14n2T1,T36.28n6A,B*n5n3n4T2,T4Rr+(8)T5=T3*T4n1T03.14n2T1,T36.28n6A,B,T5*n5n3n4T2,T4Rr+(9)T6=R-rn1T03.14n2T1,T36.28n6A,B,T5*n7T6-n5n3n4T2,T4Rr+(10)B=T5*T6n1T03.14n2T1,T36.28n6A,T5*n7T6-n8*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*T6n5n3n4T2,T4Rr+(10)B=T5*T6n1T03.14n2T1,T36.28n6A,T5*n7T6-n8*B根据DAG结点的构造顺序，按照图（10），写出相应四元式：在构造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*T6n13.14T0n26.28T1n3Rn4rn5