优化编译器
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在电脑领域中,优化编译器是一种试图将程序的某种属性最大化或者最小化的编译器。一般而言,受影响的属性包括了电脑程序的大小、执行时间以及内存占用,不同的优化编译器会根据各自的着重点,对程序做出一定变换或者在不影响运行结果的情况下修改程序的结构,使得这些属性更贴近理论上的最优值。
优化编译器的核心是程序优化变换(optimizing transformations),该类算法的目的是将原有程序,替换成资源消耗更低、运行时间更短,但语义上与原有程序等价的新程序。这些算法有一部分是NP完全的,甚至是不可判定的。与此同时,一些算法的优化能力也有可能受到编译时长限制(如即时编译)、程序开发机器的性能等问题所影响,因此编译器的开发者在设计优化算法时,需要考虑到这些因素并加以权衡。也是由于这些因素,鲜有程序在优化以后是真正做到最优的。[1]
足够智慧的优化编译器,因为能够自动化各种优化技巧的应用,对于大幅提升软件开发效率有着莫大的重要性。
优化类型
可供编译器使用的优化算法数量繁多,因此人们经常根据这些算法的某些特性,将其归类为几大类型。
作用域
最常见的分类方式是根据作用域分类优化算法,以下将根据每个算法类型的作用域大小顺序排列。
窥孔优化
这类算法通常会执行于编译的后面阶段,核心是寻找特定的指令序列,并将该序列替换成性能更好的指令序列。该算法的可视范围极小,往往只能同时窥看几条指令,故名曰窥孔优化(指其犹如通过窥孔观察程序)。[1]
本地优化
这类优化仅会考虑单一基本块(Basic block)内的资讯,也是编译器中非常常见的优化类型。[2] 由于基本块内不需要考虑到程序的控制流,这类优化的分析算法相对简单并且实现难度较低,但也有可能会因此无法发现部分优化机会。
全局优化
又称过程内优化(Intraprocedural optimization)。这类算法在运行时会考虑到函数的整体,即函数内的所有基本块以及基本块之间的控制流,因此拥有更多能够用于优化程序的资讯。这类算法的劣势在于其算法更为复杂,所需的计算量更多。[2]
循环优化
这类优化专门针对程序中的循环,常见例子有循环不变代码外提。由于许多程序会在循环内耗费许多运行时间,这类优化往往能对程序性能带来显著的影响。
预知性存储优化
这类优化会将程序中的特定存储操作前移,即使在一般的线程与锁的环境下这种前移是不被允许的。由于这些被前移的存储操作,需提前得知其即将储存的数值为何,因此这类算法在一定意义上存在着预知性。实际上,这些储存值会因为常数传播等操作,在编译时其具体数值便已得知。这类算法放宽了编译器重新排列存储顺序的限制,目的是在保留正确同步程序的语义的前提下,部分重新排列程序代码的执行顺序以提升性能。[3]
链接时优化
又称过程间优化(Interprocedural optimization)。这个类型包含了常见的内联展开优化,允许编译器将被调用函数直接展开到调用函数内,以此增加可发现的优化机会,并消除调用函数带来的性能开销。
机器码优化
这类算法相对以上优化而言非常罕见,执行于程序已经被链接为可执行文件以后。这种算法的优势在于其覆盖了整个程序的作用域,使得宏压缩等优化手段成为可能,例如通过折叠常见的指令序列,来达到节省空间的目的。[4]
除了使用作用域作为优化算法的分类标准,另有两种常见的分类标准。
编程语言依赖性
大多数高级语言都有共同的编程结构和抽象手法,例如决策上使用 if、switch、case,循环上使用 for、while、do-while,封装上使用结构、对象等等。 因此,存在一些优化技术可以跨编程语言使用。然而,也有语言因为其种种特性,使得某些优化变得非常困难,而这类语言则需为其设计一套专属的优化手法。例如使用垃圾回收器等自动内存管理机制的语言(如Java),经常需要用到逃逸分析优化以降低创建对象的性能开销,而C语言等系统语言则因为内存由程序员手动管理,导致了这项优化针对C语言的有效性大幅降低。
目标机器依赖性
许多针对抽象编程概念(循环、对象、结构)的优化实际上与编译器的目标机器无关,这类算法能够被同一个编译器内的多个后端共享。与此同时,也存在不少优化算法只对某一平台有效,因此人们也经常根据目标机器的依赖性对这些算法进行分类。
共同优化方向
许多优化算法都存在一定的优化方向,如:
- 对常见场景进行优化
- 避免产生冗余的计算
- 减少冗余代码
- 降低程序的跳转数量,尽量转换成无分支程序
- 增加局部性 (Locality)
- 最大化利用内存层次结构
- 将程序并行化
- 编译器拥有的资讯越详细,算法的优化效果越好
- 利用在运行时获得的资讯,进行分析引导优化(Profile-Guided Optimization)
- 折减表达式的计算强度(Strength reduction)
具体优化手段
参考
- ^ 1.0 1.1 Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. Compilers: principles, techniques, and tools Reprinted, with corr., [36. Druck]. Reading, Mass.: Addison-Wesley. ISBN 0-201-10088-6.
- ^ 2.0 2.1 Cooper, Keith D.; Torczon, Linda. Engineering a compiler Nachdr. San Francisco, Calif.: Morgan Kaufmann. 2004. ISBN 978-1-55860-698-2.
- ^ MSDN - Prescient Store Actions. Microsoft. [2014-03-15]. (原始内容存档于2017-05-20).
- ^ Clinton F. Goss. Machine Code Optimization - Improving Executable Object Code (PDF) (Ph.D. dissertation). Computer Science Department Technical Report #246. Courant Institute, New York University. August 2013 [First published June 1986] [22 Aug 2013]. Bibcode:2013arXiv1308.4815G. arXiv:1308.4815
. (原始内容存档 (PDF)于2022-10-09).
- Clinton F. Goss. Machine Code Optimization - Improving Executable Object Code (PhD论文). Courant Institute, New York University. 2013 [1986] [2023-05-28]. (原始内容存档于2023-11-19).
|