編譯器構造/最佳化
在現代計算機上，如果編譯器能夠在幾秒鐘內翻譯一箇中等大小的源程式（比如大約 1000 行），那麼它就可以被認為具有令人滿意的效能。獲得具有令人滿意效能的編譯器的方法與獲得任何效能良好的程式的方法大致相同。
- 使用好的演算法進行設計。
- 確保你的資料結構與演算法相匹配。
- 使用具有乾淨簡單介面的模組進行結構化。
- 使用清晰直觀的程式碼進行實現。
- 當存在整體效能問題時
- 以合理的細節測量實際效能。
- 識別有問題的區域。
- 重新設計和重新實現這些問題區域。
在本書中，我們將考慮各種演算法和資料結構，並討論它們對效能的可能影響。
請注意，實際測量至關重要，因為問題往往並不像你猜測的那樣。對於你的初始實現，你可能已經選擇了已知效能較差的簡單演算法，以便快速獲得可執行的程式。然而，你仍然應該詳細測量效能，因為可能存在其他來源導致（至少部分）你的問題。
- 如果你非常幸運，你的實現語言可能有一些可選的功能，用於選擇性地測量 CPU 時間。注意，只對少數關鍵例程啟用此功能；計時開銷很容易超過小型例程的執行時間，並扭曲結果。
- 更常見的情況是，你不走運，必須在選定例程中顯式新增計時程式碼；確保你可以輕鬆地停用它並在需要時啟用它。通常，你必須在例程的開頭和結尾插入對某些 CPU 計時例程的呼叫，然後減去這兩個值以獲得該例程的時間，其中將包括該例程呼叫的任何例程的時間。
多年來，人們報告了對實際編譯器效能的各種測量結果。已知會導致問題的特定區域包括
- 對於每個源字元，在詞法分析期間進行多次例程呼叫。
- 在詞法分析期間跳過空格。
- 跳過註釋。
- 在語法分析期間解碼緊密打包的解析表。
- 在語義分析期間在名稱表中查詢內容。
- 確定某個名稱是保留關鍵字還是使用者可定義的識別符號。
可以在維基百科的編譯器最佳化文章中找到最佳化方法的廣泛列表。最佳化是一個非常豐富且複雜的主題，因此本章只嘗試介紹基礎知識。
編譯器內的最佳化關注的是以某種方式改進生成的程式碼，同時確保結果相同。從技術上講，本章更合適的名稱可能是“改進”，因為編譯器只嘗試改程序序員請求的操作。最佳化分為三類
- 速度；改進生成的程式碼的執行時效能。這是最常見的最佳化
- 空間；減少生成的程式碼的大小
- 安全性；減少資料結構被破壞的可能性（例如，確保不會寫入非法陣列元素）
不幸的是，許多“速度”最佳化會使程式碼變大，而許多“空間”最佳化會使程式碼變慢——這被稱為空間時間權衡。
常見的最佳化演算法處理特定情況
- 無用程式碼消除
- 公共子表示式消除
- 複製傳播
- 程式碼移動
- 歸納變數消除
- 強度削弱
- 函式分塊
無用程式碼消除是一種大小最佳化（儘管它也會帶來一些速度提升），旨在從生成的程式碼中刪除邏輯上不可能的語句。無用程式碼是在任何情況下都不會執行的程式碼，無論輸入如何。
考慮以下程式
a = 5
if (a != 5) {
// Some complicated calculation
}
...
很明顯，複雜的計算永遠不會執行；由於在if語句之前分配給a的最後一個值是常量，因此我們可以在編譯時計算結果。簡單地替換引數會得到if (5 != 5)，結果為false。由於if(false)語句的主體永遠不會執行——它是無用程式碼，因此我們可以重寫程式碼
a = 5 // Some statements
該演算法用於識別和刪除無用程式碼部分
公共子表示式消除是一種速度最佳化，它旨在透過程式碼流識別表示式（或表示式的一部分）來減少不必要的重新計算，這些表示式將計算出相同的值：如果表示式以前已經計算過並且運算元的值自上次計算以來沒有改變，則可以避免重新計算表示式。
考慮以下程式
a = b + c d = e + f g = b + c
在上面的示例中，第一條和最後一條語句的右側是相同的，並且運算元的值在兩條語句之間沒有改變；因此，可以認為此表示式具有公共子表示式。
可以透過將公共子表示式的值儲存在可以快取其結果的臨時變數中來避免公共子表示式。應用公共子表示式消除技術後，程式將變為
t0 = b + c a = t0 d = e + f g = t0
因此，在最後一條語句中，避免了重新計算表示式b + c。
給定一個賦值語句 x=y，將後面對 x 的使用替換為 y，前提是沒有對 x 或 y 進行中間賦值。在這裡，程式碼將變小。例如
x[i]=a;
sum=x[i]+a;
instead of this we can use:
x[i]=a;
sum=a+a;
For x[i]=a, is copy statements.Use of 'a' for 'x[i]', whenever possible after copy statement.Here it may not appear to be code improvement, but opens up scope for other optimizations.
這種最佳化技術主要用於減少程式中的原始碼行數。例如，考慮下面的程式碼
for (i = 0; i < n; ++i) {
x = y + z;
a[i] = 6 * i + x * x;
}
計算x = y + z和x * x可以移到迴圈之外，因為它們在迴圈內是不變的——它們在迴圈的迭代中不會改變——所以我們的最佳化程式碼將類似於以下程式碼
x = y + z;
t1 = x * x;
for (i = 0; i < n; ++i) {
a[i] = 6 * i + t1;
}
此程式碼可以進一步最佳化。例如，強度削弱可以刪除迴圈內的兩個乘法運算（6*i和a[i]）。
另一個程式碼移動的例子
for(i=0;i<10;i++)
{
a = a + c;
}
在上述程式碼中，a = a + c 可以移到 'for' 迴圈之外，新程式碼為
a = a + 10*c;
如果一個變數在迴圈的每次迭代中增加或減少一個固定量，則該變數被稱為歸納變數。例如
for(i=0; i<10; i++)
{
j=17*i;
}
這裡 i、j 是歸納變數。如果迴圈中有兩個或多個歸納變數，則可能可以消除除一個以外的所有變數。最終，我們可以從這個迴圈中消除 j。
這個概念指的是編譯器最佳化方法，即用更便宜的機器指令替換一些機器指令，同時保持結果等效。由於一些運算子具有不同的強度，即在記憶體中使用不同的空間。這種最佳化型別可以生成很高的收益，尤其是在針對不同的硬體時，編譯器可以瞭解它可以利用的細微差異。
例如，*(乘法) 的強度“高於”+(加法)。
因此，在這種最佳化型別中，強度更高的運算子將被強度更低的運算子替換。
示例
假設
Length(S1 || S2)
其中 S1 和 S2 有一些值。
因此，如果我們應用該規則，則
Length(S1 || S2) ---(被替換為)--> [Length(S1) + Length(S2)]
因為 + 操作比 || 更便宜。
並且從上面的例子可以清楚地看出，結果不會改變。
函式分塊是一種編譯器最佳化，用於提高程式碼區域性性。透過分析資訊，將很少執行的程式碼移出主函式體。這使得包含很少執行程式碼的記憶體頁面可以被換出。