编译原理chapter10 优化

编译原理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优化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优化10.2局部优化1.基本块及流图基本块：程序中一顺序执行的语句系列，其中只有一个入口和一个出口，第一个语句为入口，最后一个语句为出口。对于给定的一个程序，可以将其划分为一系列的基本块，分别在块内进行局部优化（基本块内的优化）。以下先给出划分基本块的算法。①.求出程序中可做基本块入口的语句，它们是：Ⅰ.程序的第一条语句；Ⅱ.能由条件转移语句或无条件转移语句转移到的语句；Ⅲ.紧跟在条件转移语句后面的语句。编译原理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为下标，表示初值；Ⅱ.内部结点：以运算符为标记；Ⅲ.各结点可附加多个标识符，表示这些标识符等价，且具有该结点的值。编译原理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.3循环优化对循环中的代码可以实行代码外提、强度削弱和删除归纳变量等优化。