编译原理陈火旺版10-11章

优化对代码进行的变换必须遵守以下原则：1.等价原则:经优化的代码执行结果不变；2.有效原则:优化后确实执行时间短、占用空间少;3.合算原则:以较低的代价，换取较好的优化效果。第十章优化优化主要为两类：中间代码的优化(不依赖硬件)目标代码的优化(依赖硬件)本章讨论的优化主要指对中间代码进行等价的变换，使其成为执行效率更高的中间码。P272图10.1给出了代码优化的地位和结构。10.1概述1该语句段的中间代码见P274图10.2以下通过一个实例简介各种优化方法。例见P273中的C语言程序，以下为其部分语句： i=m-1;j=n;v=a[n]; While(1){ doi=i+1;while(a[i]<v); doj=j-1;while(a[j]>v); if(i>=j)break; x=a[i];a[i]=a[j];a[j]=x; } x=a[i];a[i]=a[n];a[n]=x;2i:=m-1;j:=n;T1:=4*n;v:=a[T1];i:=i+1;T2:=4*i;T3:=a[T2];ifT3<vgotoB2j:=j-1;T4:=4*j;T5:=a[T4];ifT5>vgotoB3ifi>=jgotoB6T6:=4*i;x:=a[T6];T7:=4*i;T8:=4*j;T9:=a[T8];a[T7]:=T9;T10:=4*j;a[T10]:=x;gotoB2T11:=4*i;x:=a[T11];T12:=4*i;T13:=4*n;T14:=a[T13];a[T12]:=T14;T15:=4*n;a[T15]:=x;B6B2B3B5B4B1每个数组元素占4个单元3一.删除公共子表达式（多余运算）T6:=4*i;x:=a[T6];T7:=4*i;

T8:=4*j;T9:=a[T8];a[T7]:=T9;T10:=4*j;a[T10]:=x;gotoB2B5T6:=4*i;x:=a[T6];T7:=T6;T8:=4*j;T9:=a[T8];a[T7]:=T9;T10:=T8;a[T10]:=x;GotoB2B5变换为：

因为：B2中已有T2:=4*i，且在进入B5前未改变过T2;B3中已有T4:=4*j，且在进入B5前未改变过T4;所以可将B5变换为：T6:=T2;x:=a[T6];T7:=T6;

T8:=T4;T9:=a[T8];a[T7]:=T9;T10:=T8;a[T10]:=x;GotoB2B54二.复写传播T6:=T2;x:=a[T6];T7:=T6;

T8:=T4;T9:=a[T8];a[T7]:=T9;T10:=T8;a[T10]:=x;GotoB2B5变换为：

T6:=T2;x:=a[T2];T7:=T2;T8:=T4;T9:=a[T4];a[T2]:=T9;T10:=T4;a[T4]:=x;GotoB2B5因为：B2中已有T3:=a[T2]，且在进入B5前未改变过T3;B3中已有T5:=a[T4]，且在进入B5前未改变过T5;所以可将B5变换为：T6:=T2;x:=T3;T7:=T2;T8:=T4;T9:=T5;a[T2]:=T5;T10:=T4;a[T4]:=T3;GotoB2B55三.删除无用代码T6:=T2;

x:=T3;T7:=T2;

T8:=T4;T9:=T5;a[T2]:=T5;T10:=T4;a[T4]:=T3;GotoB2B5对于如右图所示的B5，由于X,T6,T7,T8,T9,T10在程序中不再使用，因此可删除对这些变量的赋值语句。a[T2]:=T5;a[T4]:=T3;GotoB2对于B6可以像B5一样作相应的优化变换：T11:=4*i;x:=a[T11];T12:=4*i;T13:=4*n;T14:=a[T13];a[T12]:=T14;T15:=4*n;a[T15]:=x;B6变换为：

T11:=T2;x:=a[T2];T12:=T2;T13:=T1;T14:=a[T1];a[T2]:=T14;T15:=T1;a[T1]:=x;B6a[T2]:=v;a[T1]:=T3;B66四.代码外提对循环中的有些代码，若它的结果在循环中不变，可将这些代码提到循环外，以避免循环执行。例：while(i<=limit-2)…变换为：

t:=limit-2while(i<=t)…五.强度削弱循环中的代码，由于循环执行多遍，应尽量用+、-法取代*、/法等强度高的运算。i:=i+1;T2:=4*i;T3:=a[T2];ifT3<vgotoB2B2变换为：

T2:=4*i;i:=i+1;T2:=T2+4;T3:=a[T2];ifT3<vgotoB2B27六.删除归纳变量(图10.4）

B2中的i每循环一次增值1，T2与i保持线性关系，B3中的j每循环一次递减1，T4与j保持线性关系，我们称这些变量为归纳变量，T2、T4强度削弱后，i和j仅在B4中引用，因此可将i和j的赋值语句删除，并将B4改为:ifT2>=T4gotoB6七.合并已知量若某些表达式的运算量在编译时是已知的，则应直接给出结果，而无须保留表达式。例：i:=1;T:=4*i;变换为：

i:=1;T:=4;8经前述各种优化处理后，最终的中间代码如下：i:=m-1;j:=n;T1:=4*n;v:=a[T1];T2:=4*i;T4:=4*j;T2:=T2+4;T3:=a[T2];ifT3<vgotoB2T4:=T4+4;T5:=a[T4];ifT5>vgotoB3ifT2>=T4gotoB6a[T2]:=T5;a[T4]:=T3;gotoB2a[T2]:=V;a[T1]:=T3;B6B2B3B5B4B1910.2局部优化一.基本块及流图基本块：程序中一顺序执行的语句系列，其中只有一个入口和一个出口，第一个语句为入口，最后一个语句为出口。对于语句：x:=y+z我们称该语句对x定值，对y和z引用。如果一个变量在某语句之后还将被引用，则称变量在该点（语句）是活跃的。对于给定的一个程序，可以将其划分为一系列的基本块，分别在块内进行局部优化（基本块内的优化）。以下先给出划分基本块的算法。101.求出程序中可做基本块入口的语句，它们是：(1)程序的第一个语句；(2)能由条件转移语句或无条件转移语句转移到的语句；(3)紧跟在条件转移语句后面的语句。2.对以上入口语句，构造其所属的基本块：此入口语句到下一条入口语句前，或下一条跳转语句，或一条停语句的语句序列组成一个基本块。3.删除未被纳入任何基本块的语句。例: (5)x:=y(1)readx (6)y:=R(2)ready (7)goto(3)(3)R:=xmody (8)writey(4)ifR=0goto(8) (9)halt入口语句有：(1)(3)(8)(5)基本块有：{1,2}{3,4}{5,6,7}{8,9}113.代数变换：x:=y**2可变换为x:=y*y(强度削弱)以基本块为结点，构造程序的流程图，称为流图。如前例程序的流图为：B4writeyhaltreadxready R:=xmodyifR=0goto(8)x:=yy:=Rgoto(3)B1B2B3对基本块内的语句可以进行如下一些优化变换：1.合并已知量；2.交换语句位置:T1:=b+c若x,y均不为T1T2:=x+y b,c均不为T2

则可交换T1，T2两赋值语句12二.基本块的DAG表示及其应用一个基本块的DAG为如下形式的图：(1)叶子结点：以一个标识符或常数或变量的地址作为标记。标识符可以0为下标，表示初值；(2)内部结点：以运算符为标记；(3)各结点可附加多个标识符，表示这些标识符等价，且具有该结点的值。例见P282图10.9(补充一简单例子）构造基本块的DAG的算法见P282，以下简单介绍该算法。1.基本块的DAG表示131型：A:=OPB1、NODE(B)无定义，则构造叶结点n,NODE(B)=n；2、若B为常数，则计算OPB=>P,若NODE(P)无定义，则构造叶结点n,NODE(P)=n,执行0型2。3、若B非常数，查有无OPB子树：有：设NODE(OP)=n,执行0型2；

无：构造n结点OP,执行0型2。0型：A:=B

1、NODE(B)无定义，则构造叶结点n,NODE(B)=n；

2、NODE(A)有定义，则删除A在原结点的标记。

令NODE(A)=n。142型：A:=BOPC或A:=B[C]1、NODE(B)无定义，则构造叶结点B；NODE(C)无定义，则构造叶结点C；2、若B,C均为常数，则计算BOPC=>P,若NODE(P)无定义，则构造叶结点n,NODE(P)=n,执行0型2。3、若B,C不是常数，查有无BOPC子树：有：设NODE(OP)=n,执行0型2；

无：构造n结点OP,执行0型2

。在构造基本块的DAG时，当参与运算的结点均为常数时，已直接计算结果，生成新常数结点（合并已知量）。以下通过一个例子介绍基本块的DAG1586571343.146.28T0T1T3Rr*+-T6T2T4T5A*BB2例：T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R-r B:=T5*T6其DAG如右图所示：16由该图重写的代码序列如下：86571343.146.28T0T1T3Rr*+-T6T2T4T5A*BB2 T0:=3.14

T1:=6.28 T3:=6.28 T2:=R+r

T4:=T2 A:=6.28*T2

T5:=A T6:=R-r B:=A*T6已完成了如下优化：合并已知量；删除无用代码；(B:=A)删除公共子表达式。17对该基本块还可进行如下优化：

T0:=3.14 T1:=6.28 T3:=6.28 T2:=R+r

T4:=T2 A:=6.28*T2

T5:=A T6:=R-r B:=A*T6假设T0--T6在基本块后不再使用，即可删除对其的赋值，得到如下代码： T2:=R+r A:=6.28*T2 T6:=R-r B:=A*T6若调整语句顺序如下：T6:=R-rT2:=R+rA:=6.28*T2B:=A*T6将可得到更优的目标代码。18目标代码生成器的位置：源中间中间目标程序代码代码程序编译前端代码优化代码生成器

符号表

目标代码的形式：1、已定位的可立即执行的机器语言代码；2、可浮动的机器语言代码，需装配连接再执行；3、汇编语言目标代码，需汇编再执行。第十一章目标代码生成目标代码应具有高效性：目标代码较短；充分利用寄存器减少内存访问。1911.1一个简单的代码生成器P312中两个表给出了一个模拟机的指令系统(类似汇编)。仅介绍一个简单的目标代码生成方法：1、依次将每条中间代码变换成等价的若干条目标代码；2、基本块内考虑充分利用寄存器的问题。即：基本块内计算出的变量值尽量保留在寄存器中，直至寄存器另有用途或已到基本块的出口；引用变量时尽量用其在寄存器中的值。例现有赋值语句：A:=(B+C)*D+E其对应的中间