搜索
编译原理chapter10优化Chapter10优化编译原理chapter10优化10.1概述10.2局部优化10.3循环优化*10.4数据流分析编译原理chapter10优化优化主要为两类：中间代码的优化(不依赖硬件)目标代码的优化(依赖硬件)本章讨论的优化主要指对中间代码进行等价的变换，使其成为执行效率更高的中间码。编译前端代码优化器代码产生控制流分析数据流分析代码变换代码优化器的地位和结构编译原理chapter10优化10.1概述优化对代码进行的变换必须遵守以下原则：1.等价原则:经优化的代码执行结果不变；2.有效原则:优化后确实执行时间短、占用空间少;3.合算原则:以较低的代价，换取较好的优化效果。以下通过一个实例简介各种优化方法。编译原理chapter10优化例：voidquicksort(intm,intn){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;quicksort(m,j);quicksort(i+1,n);}编译原理chapter10优化快速排序首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。无序的记录序列无序记录子序列(1)无序子序列(2)枢轴一次划分分别进行快速排序编译原理chapter10优化i=m-1;j=n;T1=4*n;v=a[T1];i=i+1;T2=4*i;T3=a[T2];ifT3vgotoB2j=j-1;T4=4*j;T5=a[T4];ifT5vgotoB3ifi=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个单元编译原理chapter10优化1.删除公共子表达式（多余运算）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变换为：T6=T2;x=a[T6];T7=T6;T8=T4;T9=a[T8];a[T7]=T9;T10=T8;a[T10]=x;GotoB2B5i=i+1;T2=4*i;T3=a[T2];ifT3vgotoB2B2j=j-1;T4=4*j;T5=a[T4];ifT5vgotoB3B3编译原理chapter10优化2.复写传播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;GotoB2B5i=i+1;T2=4*i;T3=a[T2];ifT3vgotoB2B2j=j-1;T4=4*j;T5=a[T4];ifT5vgotoB3B3T6=T2;x=T3;T7=T2;T8=T4;T9=T5;a[T2]=T5;T10=T4;a[T4]=T3;GotoB2B5编译原理chapter10优化3.删除无用代码T6=T2;x=T3;T7=T2;T8=T4;T9=T5;a[T2]=T5;T10=T4;a[T4]=T3;GotoB2B5a[T2]=T5;a[T4]=T3;GotoB2B5T11=4*i;x=a[T11];T12=4*i;T13=4*n;T14=a[T13];a[T12]=T14;T15=4*n;a[T15]=x;B6变换为：a[T2]=v;a[T1]=T3;B6编译原理chapter10优化4.代码外提对循环中的有些代码，若它的结果在循环中不变，可将这些代码提到循环外，以避免循环执行。例：while(i=limit-2)…变换为：t=limit-2;while(i=t)…5.强度削弱循环中的代码，由于循环执行多遍，应尽量用+、-法取代*、/法等强度高的运算。i=i+1;T2=4*i;T3=a[T2];ifT3vgotoB2B2变换为：T2=4*i;i=i+1;T2=T2+4;T3=a[T2];ifT3vgotoB2B2编译原理chapter10优化6.删除归纳变量我们称这些变量为归纳变量，T2、T4强度削弱后，i和j仅在B4中引用，因此可将i和j的赋值语句删除ifi=jgotoB6B4变换为：ifT2=T4gotoB6B4i=i+1;T2=4*i;T3=a[T2];ifT3vgotoB2B2j=j-1;T4=4*j;T5=a[T4];ifT5vgotoB3B37.合并已知量例：i=1;T=4*i;变换为：i=1;T=4;编译原理chapter10优化经前述各种优化处理后，最终的中间代码如下：i=m-1;j=n;T1=4*n;v=a[T1];T2=4*i;T4=4*j;T2=T2+4;T3=a[T2];ifT3vgotoB2T4=T4+4;T5=a[T4];ifT5vgotoB3ifT2=T4gotoB6a[T2]=T5;a[T4]=T3;gotoB2a[T2]=V;a[T1]=T3;B6B2B3B5B4B1编译原理chapter10优化1.删除公共子表达式（多余运算）常用的优化技术：2.复写传播3.删除无用代码4.代码外提5.强度削弱6.删除归纳变量7.合并已知量编译原理chapter10优化10.2局部优化1.基本块及流图基本块：程序中一顺序执行的语句系列，其中只有一个入口和一个出口，第一个语句为入口，最后一个语句为出口。对于给定的一个程序，可以将其划分为一系列的基本块，分别在块内进行局部优化（基本块内的优化）。以下先给出划分基本块的算法。①求出程序中可做基本块入口的语句，它们是：Ⅰ.程序的第一条语句；Ⅱ.能由条件转移语句或无条件转移语句转移到的语句；Ⅲ.紧跟在条件转移语句后面的语句。例:(5)x=y(1)readx(6)y=R(2)ready(7)goto(3)(3)R=x%y(8)writey(4)ifR=0goto(8)(9)halt入口语句有：(1)(3)(5)(8)编译原理chapter10优化②对以上入口语句，构造其所属的基本块：此入口语句到下一条入口语句前，或下一条跳转语句前，或一条停语句前的语句序列组成一个基本块。③删除未被纳入任何基本块的语句。例:(5)x=y(1)readx(6)y=R(2)ready(7)goto(3)(3)R=x%y(8)writey(4)ifR=0goto(8)(9)halt入口语句有：(1)(3)(5)(8)基本块有：{1,2}{3,4}{5,6,7}{8,9}编译原理chapter10优化例:(5)x=y(1)readx(6)y=R(2)ready(7)goto(3)(3)R=x%y(8)writey(4)ifR=0goto(8)(9)haltB4writeyhaltreadxreadyR=x%yifR=0goto(8)x=yy=Rgoto(3)B1B2B3编译原理chapter10优化对基本块内的语句可以进行如下一些优化变换：③代数变换以基本块为结点，构造程序的流程图，称为流图。①合并已知量②交换语句位置x=pow(y,2);可变换为x=y*y;(强度削弱)编译原理chapter10优化2.基本块的DAG表示及其应用①基本块的DAG表示一个基本块的DAG为如下形式的图：Ⅰ.叶子结点：以一个标识符或常数或变量的地址作为标记。标识符可以0为下标，表示初值；Ⅱ.内部结点：以运算符为标记；Ⅲ.各结点可附加多个标识符，表示这些标识符等价，且具有该结点的值。n3A，C+n1Bn220编译原理chapter10优化(0)A:=Bn1AB(1)A:=opBn1Aopn2B(2)A:=BopCn3Aopn1Bn2C四元式与DAG结点对应图编译原理chapter10优化(3)A:=B[C](4)ifBropCgoto(S)(5)D[C]:=Bn3A=[]n1Bn2C四元式与DAG结点对应图n3(S)ropn1Bn2Cn4[]=n1Dn2Cn3B(6)goto(S)n1(S)编译原理chapter10优化例：T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T6T03.14T16.282435T216ABT3T4T57T6Rr+*-8*B重写的代码序列如下：T0=3.14T1=6.28T3=6.28T2=R+rT4=T2A=6.28*T2T5=AT6=R-rB=T5*T6编译原理chapter10优化假设T0--T6在基本块后不再使用，即可删除对其的赋值，得到如下代码：对该基本块还可进行如下优化：T0=3.14T1=6.28T3=6.28T2=R+rT4=T2A=6.28*T2T5=AT6=R-rB=T5*T6T2:=R+rA:=6.28*T2T6:=R-rB:=A*T6变换为：T6:=R-rT2:=R+rA:=6.28*T2B:=A*T6变换为：编译原理chapter10优化例题（自学）[例10.1]试对以下基本块B1应用DAG进行优化。B1:A:=B*CD:=B/CE:=A+DF:=E*2G:=B*CH:=G*GF:=H*GL:=FM:=L并就以下两种情况分别写出优化后的四元式序列：（1）假设G、L、M在基本块后被引用；第十章优化编译原理chapter10优化（2）假设只有L在基本块后被引用。解：对于B1其DAG图：第十章优化n1Bn2Cn3*A,Gn4/Dn5+En62n7F*n8*Hn9*F,L,M(1)若只有G、L、M在基本块后被引用，则优化为：G:=B*CH:=G*GL:=H*GM:=LA:=B*CD:=B/CE:=A+DF:=E*2G:=B*CH:=G*GF:=H*GL:=FM:=L编译原理chapter10优化(2)若只有L在基本块后被引用，则优化为：G:=B*CH:=G*GL:=H*G第十章优化编译原理chapter10优化10.3循环优化对循环中的代码可以实行代码外提、强度削弱和删除归纳变量等优化。1．代码外提循环中的代码要随着循环反复执行，但其中某些运算的结果并不因循环而改变，对于这种不随循环变化的运算，可以将其外提到循环外。这样，程序的运行结果仍保持不变，但程序的运行效率却提高了。我们称这种优化为代码外提。编译原理chapter10优化•实行代码外提时，在循环入口结点前面建立一个新结点(基本块)，称为循环的前置结点。循环前置结点以循环入口结点为其唯一后继，原来流图中从循环外引到循环入口结点的有向边改成引到循环前置结点，如图10.10所示。•因为在我们所定义的循环结构中，其入口结点是唯一的，所以前置结点也是唯一的。循环中外提的代码将统统外提到前置结点中。•编译原理chapter10优化前置结点循环L…入口结点…循环L…入口结点…图10.10给循环建立前置结点编译原理chapter10优化•但是，循环中的不变运算并不是在任何情况下都可以外提的；对循环L中的不变运算:S：A=BopC或A=opB或A=B，要求满足下述条件(A在离开循环L后仍是活跃的)：(1)S所在的结点是循环L的所有出口结点的必经结点；(2) A在循环L中其它地方未再定值；(3) 循环L中的所有A的引用点只有S中A的定值才能到达。例p288-289图10.11-14。编译原理chapter10优化Chapter11目标代码生成编译原理chapter1