优化对代码进行的变换必须遵守以下原则等价原则经PPT课件.ppt

。例见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;(多余运算)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;:=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;:=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;,若它的结果在循环中不变,可将这些代码提到循环外,以避免循环执行。例:while(i<=llimit-2)…变换为:t:=llimit-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<()B2中的i每循环一次增值1,T2与i保持线性关系,B3中的j每循环一次递减1,T4与j保持线性关系,我们称这些变量为归纳变量,T2、T4强度削弱后,i和j仅在B4中引用,因此可将i和j的赋值语句删除,并将B4改为:ifT2>=,则应直接给出结果,而无须保留表达式。例:i:=1;T:=4*i;变换为:i:=1;T:=4;8经前述各种优化处理后,最终的中间代码如下:i:=m-1;j:=n;T1:=4*n;v:=a[T1];T2