论文部分内容阅读
表达式的部分冗余消除（Partial Redundancy Elimination，PRE）优化是非常重要的体系结构无关的编译优化，作为全局的标量优化，它涵括循环不变量外提优化和公共子表达式消除优化。由于安全性的限制，常规部分冗余消除优化不能够完全消除程序中存在的部分冗余，也就不能够最优化程序性能。因此，有必要放松该安全性限制，本文称之为前瞻部分冗余消除优化。静态单点赋值（Static Single Assignment，SSA）形式由于包括内生的使用—定义关系，并且基于SSA的数据流分析复杂性只与问题的规模相关，而不取决于程序自身的规模。所以，现代编译器大多基于SSA形式进行全局的稀疏数据流分析，进而实现全局的标量优化。本论文提出了基于SSA形式的前瞻部分冗余消除最优化算法，包括计算最优和生命期最优。计算最优意味着程序执行时该目标表达式的计算次数最少，而生命期最优是指新引入的变量的活跃范围最短。论文的主要贡献包括:1.给定应用程序剖析信息，首次提出基于SSA形式的最优化前瞻部分冗余消除算法，本文称之为MC-SSAPRE算法。MC-SSAPRE根据目标表达式SSA形式中生成网络流，并得到该流网络的最小切割。本文还详细证明了根据最小切割的代码移动满足计算最优和生命期最优。较之既往的工作，MC-SSAPRE更为高效，因为其基于SSA形式，数据流分析的复杂度从O(N2)降为O(N)，并且会生成更精简的网络流；MC-SSAPRE只需要基本快执行频度信息，而不是更为重量级的控制流边的频度信息；同时，由于现代编译器大多采用SSA形式，所以较之基于位向量（bit-vector）的算法，MC-SSAPRE更为实用。我们在开源的path64编译器中实现了MC-SSAPRE算法，实验表明，SPECCPU2006在IntelNehalem平台上性能可平均提高2%以上。2.对于常规部分冗余消除，本文基于网络流的最小切割的模型，提出不同于SSAPRE算法的MF-SSAPRE算法。在实现上，MF-SSAPRE和MC-SSAPRE共用绝大部分的步骤。较之SSAPRE算法而言，该算法更加简单易懂，编译器工程师也更容易实现。