第8章代码优化.

编译原理第8章代码优化安庆师范学院计算机与信息学院本章目标解释优化的基本概念以及代码优化器的地位和结构说明编译程序进行代码变换应遵循的原则通过实例说明代码优化通常采用的基本方法介绍基本块的概念及其划分算法说明程序流图的构造方法介绍基本块的DAG表示方法介绍循环优化一般采用的方法教学内容8.1优化概述8.2局部优化8.3循环优化8.4本章小结8.1优化概述（1）优化的含义对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码，称这种变换为优化。（2）优化分类①根据编译阶段的不同划分与机器无关的中间代码优化依赖于机器的目标代码优化②根据优化对象所涉及的程序范围划分局部优化循环优化全局优化8.1优化概述（3）代码优化器的地位有很多技术和手段可以用于中间代码这一级上的优化。总体上讲在一个编译程序中优化器的地位和结构如下图：代码优化器编译前端控制流分析数据流分析代码变换代码产生8.1优化概述（4）代码优化遵循的原则优化的目的是为了产生更高效的代码。由优化编译程序提供的，对代码的各种变换必须遵循以下三个原则：①等价原则经过优化后不应改变程序运行的结果。②有效原则使优化后所产生的目标代码运行时间较短，占用的存储空间较小。③合算原则应尽可能以较低的代价取得较好的优化效果。8.1优化概述（5）常用的代码优化的方法①删除公共子表达式（删除多余运算）②复写传播③删除无用代码（删除无用赋值）④合并已知量⑤代码外提⑥强度削弱⑦删除归纳变量循环优化8.1优化概述（6）代码优化举例我们通过一个高级语言程序的例子来了解代码优化的全过程。下面是一个用C语言编写的快速排序子程序：voidquicksort(intm,intn){inti,j;intv,x;if(n=m)return;/*fragmentbeginshere*/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;/*fragmentendshere*/quicksort(m,j);quicksort(i+1,n);}8.1优化概述通过第6章的中间代码生成方法可以产生这个程序的中间代码。图8–2给出了程序中两个注解行之间的语句翻译成中间代码序列后所对应的程序流图，对图8–2程序流图的代码优化叙述如下。23232i:i1T:4*iT:a[T]ifTvgotoB45453j:j1T:4*jT:a[T]ifTvgotoB6ifijgotoB6678987910102T:4*ix:a[T]T:4*iT:4*jT:a[T]a[T]:TT:4*ja[T]:xgotoB11i:m1j:nT:4*nv:a[T]11111213141312141515T:4*ix:a[T]T:4*iT:4*nT:a[T]a[T]:TT:4*na[T]:x1B2B3B4B5B6B8.1优化概述①删除公共子表达式如果一个表达式E在前面已计算过，并且在这之后E中变量的值没有改变，则称E为公共子表达式。在图8–2的B5中分别把公共子表达式4*i和4*j的值赋给T7和T10，因此这种重复计算可以消除，即B5中的代码变换成：T6:=4*ix:=a[T6]T7:=4*iT8:=4*jT9:=a[T8]a[T7]:=T9T10:=4*ja[T10]:=xgotoB2T6:=4*ix:=a[T6]T7:=T6T8:=4*jT9:=a[T8]a[T7]:=T9T10:=T8a[T10]:=xgotoB28.1优化概述对B5删除了公共子表达式后，仍然要计算4*i和4*j，我们还可以在更大范围内来考虑删除公共子表达式的问题，即利用B3中的四元式T4:=4*j可以把B5中的代码T8:=4*j替换为T8:=T4。同样，利用B2中的赋值句T2:=4*i可以把B5中的代码T6:=4*i替换为T6:=T2。对于B6也可以同样考虑，最后，删除公共子表达式后的程序流图如图8–3所示。23232i:i1T:4*iT:a[T]ifTvgotoB45453j:j1T:4*jT:a[T]ifTvgotoB6ifijgotoB11i:m1j:nT:4*nv:a[T]1B2B3B4B5B6B62676849879108102T:Tx:a[T]T:TT:TT:a[T]a[T]:TT:Ta[T]:xgotoB1121112111311413121415115T:Tx:a[T]T:TT:TT:a[T]a[T]:TT:Ta[T]:x8.1优化概述②复写传播图8–3中的B5还可以进一步改进，四元式T6:=T2把T2赋给了T6，而四元式x:=a[T6]中引用了T6的值，但这中间并没有改变T6的值。因此，可以把x:=a[T6]变换为x:=a[T2]。这种变换称为复写传播。用复写传播的方法可以把B5变为：T6:=T2x:=a[T6]T7:=T6T8:=T4T9:=a[T8]a[T7]:=T9T10:=T8a[T10]:=xgotoB2T6:=T2x:=a[T2]T7:=T2T8:=T4T9:=a[T4]a[T2]:=T9T10:=T4a[T4]:=xgotoB28.1优化概述作进一步的考察可以发现，在B2中计算了T3:=a[T2]，因此在B5中可以删除公共子表达式，即把x:=a[T2]替换为x:=T3，并继续通过复写传播，把B5中的a[T4]:=x替换为a[T4]:=T3。同样，把B5中的T9:=a[T4]替换为T9:=T5，a[T2]:=T9替换为a[T2]:=T5。这样B5就变为：T6:=T2x:=T3T7:=T2T8:=T4T9:=T5a[T2]:=T5T10:=T4a[T4]:=T3gotoB2T6:=T2x:=a[T2]T7:=T2T8:=T4T9:=a[T4]a[T2]:=T9T10:=T4a[T4]:=xgotoB2复写传播的目的是：使得对某些变量的赋值变为无用。8.1优化概述③删除无用赋值对于进行了复写传播后的B5，其中的变量x及临时变量T6、T7、T8、T9、T10在整个程序中不再使用，故可以删除对这些变量赋值的代码。删除无用赋值后B5变为：a[T2]:=T5a[T4]:=T3gotoB2对B6进行相同的复写传播和删除无用赋值后变为：a[T2]:=va[T1]:=T3复写传播和删除无用赋值后的程序流图如图8-4所示。23232i:i1T:4*iT:a[T]ifTvgotoB45453j:j1T:4*jT:a[T]ifTvgotoB6ifijgotoB11i:m1j:nT:4*nv:a[T]1B2B3B4B5B6B25432a[T]:Ta[T]:TgotoB213a[T]:va[T]:T8.1优化概述④代码外提对于循环中的有些代码，如果它产生的结果在循环中是不变的，就可以把它提到循环外来，以避免每循环一次都要对这条代码进行运算。这种变换称之为代码外提。如：while(i=limit-2)…….可变换为：t:=limit-2while(i=t)……….考察图8–4，没有发现可外提到循环之外的不变运算。23232i:i1T:4*iT:a[T]ifTvgotoB45453j:j1T:4*jT:a[T]ifTvgotoB6ifijgotoB11i:m1j:nT:4*nv:a[T]1B2B3B4B5B6B25432a[T]:Ta[T]:TgotoB213a[T]:va[T]:T8.1优化概述⑤强度削弱观察图8–4的内循环B3，每循环一次，j的值减1；而T4的值始终与j保持着T4=4*j的线性关系，即每循环一次，T4值随之减少4。因此，我们可以把循环中计算T4值的乘法运算变为在循环前进行一次乘法运算而在循环中进行减法运算。同样，对循环B2中的T2=4*i也可以进行强度削弱。经过强度削弱后的程序流图如图8-5所示。6ifijgotoB1B2B3B4B5B6B25432a[T]:Ta[T]:TgotoB213a[T]:va[T]:T1124i:m1j:nT:4*nv:a[T]T:4*iT:4*j223232T:T4T:a[T]ifTvgotoB445453T:T4T:a[T]ifTvgotoB23232i:i1T:4*iT:a[T]ifTvgotoB45453j:j1T:4*jT:a[T]ifTvgotoB6ifijgotoB11i:m1j:nT:4*nv:a[T]1B2B3B4B5B6B25432a[T]:Ta[T]:TgotoB213a[T]:va[T]:T8.1优化概述⑥删除归纳变量由图8–4可知，B2中每循环一次，i值加1，T2与i之间保持着T2=4*i的线性关系；而B3中每循环一次，j值减1，T4与j之间保持着T4=4*j的线性关系。这种变量我们称之为归纳变量。在对T2=4*i和T4=4*j进行了强度削弱后，i和j仅出现在条件句ifi≥jgotoB6中，其余地方不再被引用。因此，我们可以变换归纳变量而把此条件句变换为：ifT2≥T4gotoB6。经过这种变换，我们又可以将无用赋值i=i+1和j=j–1删去。删除归纳变量后的程序流图如图8–6所示。23232i:i1T:4*iT:a[T]ifTvgotoB45453j:j1T:4*jT:a[T]ifTvgotoB6ifijgotoB11i:m1j:nT:4*nv:a[T]1B2B3B4B5B6B25432a[T]:Ta[T]:TgotoB213a[T]:va[T]:T6ifijgotoB1B2B3B4B5B6B25432a[T]:Ta[T]:TgotoB213a[T]:va[T]:T1124i:m1j:nT:4*nv:a[T]T:4*iT:4*j223232T:T4T:a[T]ifTvgotoB445453T:T4T:a[T]ifTvgotoB1B2B3B4B5B6B25432a[T]:Ta[T]:TgotoB213a[T]:va[T]:T1124i:m1j:nT:4*nv:a[T]T:4*iT:4*j223232T:T4T:a[T]ifTvgotoB445453T:T4T:a[T]ifTvgotoB246ifTgotoB8.1优化概述通过上述各种优化，最终得到图8–6的优化结果。比较图8–2和图8–6可知：B2和B3中的四元式从4条减为2条，而且一条是由乘法变为加法；B5中的四元式由9条变为3条，B6中的四元式由8条变为2条。以上这些优化对循环执行来说，效果是非常明显的。虽然B1的四元式由4条变为6条，但因其仅被执行一次，所以影响甚微。1B2B3B4B5B6B25432a[T]:Ta[T]:TgotoB213a[T]:va[T]:T1124i:m1j:nT:4*nv:a[T]T:4*iT:4*j223232T:T4T:a[T]ifTvgotoB445453T:T4T:a[T]ifTvgotoB246ifTgotoB返回8.2局部优化基本块及流图1基本块的DAG表示及其应用21、基本块及流图（1）基本块所谓基本块，是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。对