優化編譯器
在計算機領域中，優化編譯器是一種試圖將程序的某種屬性最大化或者最小化的編譯器。一般而言，受影響的屬性包括了計算機程序的大小、執行時間以及內存占用，不同的優化編譯器會根據各自的着重點，對程序做出一定變換或者在不影響運行結果的情況下修改程序的結構，使得這些屬性更貼近理論上的最優值。
優化編譯器的核心是程序優化變換（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 [22 Aug 2013]. Bibcode:2013arXiv1308.4815G. arXiv:1308.4815
. （原始內容存檔 (PDF)於2022-10-09）. 已忽略未知參數|orig-date=(幫助)- Clinton F. Goss. Machine Code Optimization - Improving Executable Object Code (PhD論文). Courant Institute, New York University. 2013 [2023-05-28]. （原始內容存檔於2023-11-19）. 已忽略未知參數
|orig-date=(幫助)
- Clinton F. Goss. Machine Code Optimization - Improving Executable Object Code (PhD論文). Courant Institute, New York University. 2013 [2023-05-28]. （原始內容存檔於2023-11-19）. 已忽略未知參數
