数据流优化概述

具体的优化方法详见各自的文档,这里只讲一下把它们组合起来之后得到的结果。

这些优化方法间不是独立的,某种优化可能会产生其它的优化机会,比如说:

  a = 1
  b = a + c

经过常量传播后变成

  a = 1
  b = 1 + c

此时可能a不再活跃,a = 1一句可以被死代码消除的过程删除。比较实际的例子是:公共表达式提取往往会产生很多复写语句,复写传播将这些复写语句的源操作数尽量向复写的源头传播,这样就会产生很多无用的复写语句,从而在死代码消除中被删除。

某种优化也可能阻止其它的优化进行,例如:

  if (b) {
    x + y; -> tmp = x + y;
  } else {
    x + y; -> tmp = x + y;
  }
  z = x + y; -> z = tmp;

如果先进行公共表达式提取,会导致if-else中的两个x + y都在后面被用到(从而z就不用再重复计算),而这两个多余的式子本来是可以被死代码删除给删掉的,现在则不能了。当然,最后的这个结果不是最优的根本原因还是在于我们实现的这些优化都是很初级的,如果能够使用更高级的优化技术,肯定还算可以把它优化到最简洁的形式。

一趟各种优化进行完之后,可能会产生新的优化机会,例如对下面的代码进行死代码消除(基于活跃变量分析):

  c = a + b
  d = b + c
  e = c + d
  ...
  z = x + y

如果z最后没有被用到,那么最后一句将被标记成死代码而删除,如果a-y也都没有在其它地方被用到,那么一轮死代码消除就会从中删除一条语句,不断迭代直到删光。可以想象这样的过程其实不是很高效:每轮计算中有大量的计算被重复了。虎书中给出了一些方法,可以尽量保存计算结果或者是在一趟优化中"看的更远",执行更多的优化。

或者,如果不是采用活跃变量分析来进行死代码消除,而是采用Faint Variables Analysis(我不知道怎么翻译),则可以一次性识别出这些语句都是死代码。关于Faint Variables Analysis可参考资料general-frameworks(从第22页起),这不在课程要求范围内。

我们的简单的优化器没有做这种特殊处理,采用的就是暴力的重复的方式:

pub fn optimize(&mut self) {
  crate::common_expr::work(self);
  crate::copy_prop::work(self);
  crate::const_prop::work(self);
  crate::aliveness::work(self);
}

pub fn optimizen(&mut self, n: u32) {
  for _ in 0..n { self.optimize(); }
}

测试代码中设定优化10次即停止,保证不会消耗太多的时间。请不要修改这个数字和各个优化执行的顺序,这涉及到判断大家的实现结果是否正确

Last updated