第9章 代码优化

编译原理

CompilerTheory第九章代码优化9.1概述9.2基本块内的优化第9章代码优化29.1优化概述1.优化概念2.优化方法合并已知量删除多余运算代码外提强度消弱删除无用赋值31.优化概念等价原则：对程序或中间代码进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。有效原则：优化的目的在于既要设法缩小存储空间，又要尽量提高运行速度，而且更偏重于提高运行速度。合算原则：应尽可能以较低的代价取得较好的优化效果。4说明不同的用户要求的优化程度不同，有的可能不需要优化。解决办法是产生几个编译的版本：COM1：不优化；COM2：低级优化；COM3：高级优化；5优化分类与计算机无关的优化在源程序或中间语言一级上进行（讲）注重于程序的结构，对程序流程进行有效性、等价性处理。与计算机有关的优化依赖具体计算机的硬件环境，在生成目标代码时进行优化。6全局优化与局部优化从优化与源程序的关系出发，又可将优化分为：全局优化：以整个程序作为对象进行全面分析（如数据流分析）局部优化：(基本块内，循环)在特定范围内利用该范围的特点进行优化（讲）7优化方法——合并已知量例：A:=5*4+B;C:=2*3.14*R;5*42*3.14常数运算，不用运行即可知道结果，因此，可在编译时计算出结果。优化后：A:=20+B;C:=6.28*R8优化方法——删除多余运算删除多余运算：即找出公共子表达式A:=B*C*D+E;C:=B*C*D-E;T:=B*C*D;A:=T+E;C:=T-E;B:=B*C+E;A:=B*C-E;不能优化，∵B的值变了。910优化方法——代码外提将循环不变运算提到循环外。

FORI:=1TO1000DOA[I]:=B*C;循环不变运算11优化方法——强度消弱一般只用于循环中。

FORI:=1TO1000DOA[I]:=I*25;255075…A[1]A[2]A[3]优化方法——删除无用赋值无用赋值：

X:=B+C;A:=B-C;

A:=B*C;X:=B+C;A:=B-C;…

A:=B*C;

…若此句之后没有用到A的值，则此句为多余赋值;若此句之后也没有用到B、C的值，则对B、C的赋值也是无用的（∵B、C的赋值只是为A而用的）无用赋值的种类很多，要从整个程序来判断。129.2基本块内的优化基本块：指程序中一组顺序执行的语句序列，其中只有一个入口和一个出口，它们分别为第一个和最后一个运行的语句。对一个基本块来说，执行时只能从其入口进入，从其出口退出。1314划分基本块的方法(1)求出中间代码中各个基本块的入口语句。①

程序的第一个中间代码；②

能由转移代码转移到的中间代码；③

紧跟在条件转移代码后面的中间代码。(2)对每一入口中间代码，构造其基本块。由每一个入口中间代码到下一入口中间代码（不包括该入口中间代码）；由每一个入口中间代码到一转移中间代码（包括该转移中间代码）；由每一个入口中间代码到"停"中间代码(包括该"停"中间代码)之间的语句序列组成。⑶

凡未被纳入基本块中的中间代码，都是程序中控制流程无法到达，也是不会被执行到的，把它们从程序中删除。15示例ifAandBthenZ:=X+YelseZ:=X-Y;U:=P+Q*Z;V:=P-Q*Z;(1)T1:=AandB(2)IfT1=0goto6(3)T2:=X+Y(4)Z:=T2(5)goto8(6)T3:=X-Y(7)Z:=T2(8)T4:=Q*Z(9)T5:=P+T4(10)U:=T5(12)T6:=Q*Z(13)T7:=P-T4(14)V:=T7T1:=AandBT3:=X-YT2:=X+YT4:=Q*Z三地址码基本块基本块内的优化方法在一个基本块内通常有三种优化方法:合并已知量删除无用赋值（较困难）删除多余运算161.合并已知量如果源程序中某些运算的运算对象的值在编译时是已知的，则在编译时，就可以执行这些运算，从而不必在运行时再执行它们。如：A:=2*3.14+B

A:=6.28+B

I:=3+5I:=817示例I:=2+5;J:=I+3;K:=2*I+J;I:=J+K+M;I:=7;J:=10;K:=24;I:=34+M;实现方法：用一些T表使变量和已知值配对。Name(名字)Cons(常量)18合并已知量优化步骤若运算对象为T表中的量，则用相应的cons值代替它；若为形如Ti:=O1opO2的代码(op仅指+、-、*、/)，且两个运算对象均为常数，则合并常数，将所得结果与Ti一起填入T表,并删除此代码。若为形如A:=B的代码：若B为常数，则将A与此常数填入T表；若T表中已有A，则更新A的值。若B不为常数，但A在T表中，则将A从T表中删除19I:=2+5;J:=I+3;K:=2*I+J;I:=J+K+M;(1)T1:=2+5(2)I:=T1(3)T2:=I+3(4)J:=T2(5)T3:=2*I(6)T4:=T3+J(7)K:=T4(8)T5:=J+K(9)T6:=T5+M(10)I:=T6(1)I:=7;(2)J:=10;(3)K:=24(4)T6:=34+M(5)I:=T6优化前优化后T表NameconsT17I

7T210J10T314T424K24T534202.删除多余运算多余运算：在此计算之前已存在一个与它完全相同的运算，且该运算所依赖的全部变量中没有一个在这两次运算之间被别的运算所改变。A:=X*(Y-Z)B:=X/(Y-Z)T:=Y-Z;A:=X*T;B:=X/T;2122D:=D+C*B;A:=D+C*B;C:=D+C*B;(1)T1:=C*B;(2)T2:=D+T1;(3)D:=T2;(4)T3:=C*B;(5)T4:=D+T3;(6)A:=T4;(7)T5:=C*B(8)T6:=D+T5(9)C:=T6(1)T1:=C*B;(2)T2:=D+T1;(3)D:=T2;(4)T4:=D+T1;(5)A:=T4;(6)T6:=D+T1(7)C:=