论文部分内容阅读
随着高级编程语言和微处理器技术的不断发展，编译优化问题的复杂程度在迅速增加。现代优化编译器通常采用几十个甚至上百个优化遍来对程序进行优化以覆盖尽可能多的优化机会。由于优化之间复杂的相互作用关系，不同的优化排列组合序列产生出的代码会存在很大的性能差异。尽管在优化序列的搜索方法上投入了大量的研究工作，由于整个搜索空间的大小随优化算法数量的增加而呈指数级增长，该类方法仍然面临着严峻的挑战。解决或缓解这个问题的一个有效途径是建立更一般的优化问题模型并设计优化能力更强的优化算法，以同时包含多个不同优化遍的全部排列组合效果。
标量优化是用于减少程序中的计算数量或降低计算强度的一类优化技术。由于实际应用中的各种标量优化算法功能单一，只能解决标量优化问题的一个特定子集，几乎所有的优化编译器都会同时选择多个不同的标量优化算法组合使用以实现优化功能的互补，而有些优化算法可能还需要被重复使用多次以发掘由于应用其它优化而带来的二次优化机会。这导致标量优化的最优序列选择问题尤为困难。许多研究工作试图设计优化能力更强的标量优化算法，从而替代多个特殊算法以减少优化数量并改进优化效果。其中，程序的值流图表示方法为标量优化问题建立了更一般的问题模型。基于值流图的标量优化技术具有更强的优化能力，能够包含或优于多个常用标量优化算法的全部排列组合效果。
然而，基于值流图的标量优化技术所依赖的庞大数据结构（值流图）和在其上进行的效率极低的数据流分析是阻碍该技术被实际应用的致命障碍。到目前为止，所有已发布的研究成果都只停留在理论层次的讨论上，没有一个成功的应用实例。本文工作针对现有基于值流图的标量优化技术中存在的缺陷，提出了相应的解决方案，解决了构造和表示值流图的效率问题，解决了按需扩展值流图的问题，整合了部分冗余消除、复制传播和部分死计算消除优化，以及在真实的环境中进行了实现并解决了实际应用中遇到的问题。本文的主要贡献包括：
1.提出了一种基于静态单赋值形式的高效的完全值编号算法。该算法检测局部等值关系的能力等同于构造值流图过程中使用的等值分析算法，但只需要一个全局的结构化划分有向无环图来表示分析过程中和最终产生的等值关系，因此具有较高的运行效率。在实际应用中，其运行效率与其它基于静态单赋值的非完全值编号算法相近。本文还利用存储静态单赋值形式对该算法进行了扩展，使其能够检测访存操作间的等值关系。该算法是高效地建立和表示值流图的基础。同时，该算法对程序验证技术也具有应用价值。
2.提出了一种用于高效表示程序中全局等值关系的表示法--精简值流图。它是静态单赋值形式的扩展，将程序中不同计算间的流敏感等值关系显式包含在程序的中间表示中。它表示程序中全局等值关系的能力等同于传统的值流图，但其复杂程度却远低于传统的值流图。这为提高基于值流图的优化技术的运行效率，并最终将其推向实用奠定了基础。
3.提出了一种基于精简值流图的最优语义代码移动算法。该算法是从基于值流图的最优语义代码移动算法转换而来。由于使用了精简值流图，算法具有较高的运行效率。除此之外，新算法在分析安全属性的过程中会按需扩展精简值流图，从而能够得到取得Herbrand最优性所需的全部等值关系。该算法还整合了复制传播和部分死计算消除优化，并且还能够很容易对其进行扩展以增加强度降低等标量优化功能，可以作为多种标量优化技术的统一框架。
4.在新的最优语义代码移动算法的基础上增加了一种考虑寄存器压力和跳转代价的收益模型，使代码移动优化变得更加智能。增加了该收益模型后，代码移动将不再简单地以最大程度减少计算数量为目标，而是综合权衡减少计算数量带来的收益和增加寄存器压力及跳转指令所产生的代价。在某些情况下，甚至可以增加冗余计算以降低寄存器压力或减少跳转指令。该收益模型在大多数情况下能避免或减轻优化算法，尤其是优化能力很强的最优算法的过度优化的问题。
5.在工业级编译器PKUnity编译器中实现了本文提出的优化技术，在基于X86处理器和自主知识产权的UniCore处理器两个不同体系结构类型的平台上进行了实验，并都取得了较好的优化效果。这是首个基于值流图的优化技术在真实环境中的应用。同时该项工作也为进一步改进PKUnity译器中的标量优化技术奠定了良好的理论和实践基础。