第7章代码优化资料.ppt

对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也可以同样考虑，最后，删除公共子表达式后的程序流图如图7–22所示。 图7–21 程序流图 图7–22 删除公共子表达式后的程序流图 2．复写传播 图7–22中的B5还可以进一步改进，四元式T6=T2把T2赋给了T6，而四元式x=a[T6]中引用了T6的值，但这中间并没有改变T6的值。因此，可以把x=a[T6]变换为x=a[T2]。这种变换称为复写传播。用复写传播的方法可以把B5变为： T6=T2 x=a[T2] T7=T2 T8=T4 T9=a[T4] a[T2]= T9 T10=T4 a[T4]=x goto B2 作进一步的考察可以发现，在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=T2 x= T3 T7=T2 T8=T4 T9=T5 a[T2]= T5 T10=T4 a[T4]= T3 goto B2 3．删除无用赋值 对于进行了复写传播后的B5，其中的变量x及临时变量T6、T7、T8、T9、T10在整个程序中不再使用，故可以删除对这些变量赋值的四元式。删除无用赋值后B5变为： a[T2]= T5 a[T4]= T3 goto B2 对B6进行相同的复写传播和删除无用赋值后变为： a[T2]= v a[T1]= T3 复写传播和删除无用赋值后的程序流图如图7-23所示。 图7–23 复写传播和删除无用赋值后的程序流图 4．代码外提 考察图7–23，没有发现可外提到循环之外的不变运算。 5．强度削弱 观察图7–23的内循环B3，每循环一次，j的值减1；而T4的值始终与j保持着T4=4*j的线性关系，即每循环一次，T4值随之减少4。因此，我们可以把循环中计算T4值的乘法运算变为在循环前进行一次乘法运算而在循环中进行减法运算。同样，对循环B2中的T2=4*i也可以进行强度削弱。经过强度削弱后的程序流图如图7-24所示。 6．删除归纳变量 由图7–24可知，B2中每循环一次，i值加1，T2与i之间保持着T2=4*i的线性关系；而B3中每循环一次，j值减1，T4与j之间保持着T4=4*j的线性关系。在对T2=4*i和T4=4*j进行了强度削弱后，i和j仅出现在条件句if I≥j goto B6中，其余地方不再被引用。因此，我们可以变换归纳变量而把此条件句变换为：if T2≥T4 goto B6。经过这种变换，我们又可以将无用赋值i=i+1和j=j–1删去。删除归纳变量后的程序流图如图7–25所示。 通过上述各种优化，最终得到图7–25的优化结果。比较图7–21和图7–25可知：B2和B3中的四元式从4条减为2条，而且一条是由乘法变为加法；B5中的四元式由9条变为3条，B6中的四元式由8条变为2条。以上这些优化对循环执行来说，效果是非常明显的。虽然B1的四元式由4条变为现在的B1和B2共6条，但因其仅被执行一次，所以影响甚微。 图7–24 强度削弱后的程序流图 图7–25 删除归纳变量后的程序流图 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * (1) ?S所在的结点是L的所有出口结点的必经结点； (2) ?A在L中其它地方未再定值； (3) ?L中的所有A的引用点只有S中A的定值才能到达。 对上述三个条件，我们给出图7–9所示的三种流图予以说明。 图7–9 代码外提的程序流图示例 对图7–9(a)，先将B3中的循环不变运算I=2外提到