最佳化編譯器
在電腦領域中，最佳化編譯器是一種試圖將程式的某種屬性最大化或者最小化的編譯器。一般而言，受影響的屬性包括了電腦程式的大小、執行時間以及主記憶體占用，不同的最佳化編譯器會根據各自的著重點，對程式做出一定變換或者在不影響執行結果的情況下修改程式的結構，使得這些屬性更貼近理論上的最佳值。
最佳化編譯器的核心是程式最佳化變換（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）.
