經典最佳化：內聯、摺疊、迴圈

內聯：那把解鎖其餘一切的鑰匙

到現在你已經能讀懂 LLVM IR、也看得懂一個 pass 如何改寫它。本篇要叫出那些真正值回票價的 pass 的名字，而第一個就是拱心石。內聯把一個對函式的呼叫，換成那個函式本體的一份拷貝，就地貼進呼叫點，並把引數代換進參數。呼叫一個像 square(x) 這樣只是回傳 x * x 的小幫手，內聯之後那個呼叫就單純變成原地的 x * x——不用跳出去、也不用跳回來。立即的好處是你免付任何呼叫慣例的稅：不用堆引數、不用存暫存器、沒有返回位址、也沒有序言與收尾。

但省下的呼叫開銷，再怎麼真實，也只是小獎品。內聯排在管線最前面的真正理由，是它摧毀了一道邊界。內聯之前，編譯器只能把你的小幫手當成黑盒子：它看不出呼叫端永遠傳進一個常數，小幫手也看不出呼叫端拿那個結果去做什麼。把本體貼進來，最佳化器忽然看著的是一整段攤平的程式碼，引數的已知值與本體的計算肩並肩地住在一起。本篇其餘的每一個最佳化——摺疊、死碼移除、迴圈工作——如今都拿到一塊大得多、也透明得多的區域去咀嚼。內聯與其說是一種最佳化，不如說是各種最佳化的促成者。

摺疊與傳播：讓常數流動起來

下一個家族，正是內聯餵養的對象。常數摺疊在編譯期算掉任何輸入全是已知常數的操作：3 + 4 的 IR 直接被換成 7，而 60 * 60 * 24 在程式跑起來之前就變成字面常數 86400。常數傳播是它的搭檔——當一個值已知是常數，那個值之後的每一個使用處都被換成那個常數本身。這兩者攜手並進、彼此餵養：把一個常數傳播進一個運算式，那個運算式現在輸入全是常數，於是把它摺疊掉；摺疊出的結果本身又是一個新常數，可以再傳播得更遠。

after inlining a call with a constant argument:

    n  = 5            // propagated in from the caller
    t1 = n * n        // propagate n=5  ->  t1 = 5 * 5
    t2 = t1 + 1       //   fold 5*5=25  ->  t1 = 25
                      //   propagate    ->  t2 = 25 + 1
                      //   fold         ->  t2 = 26

    if (t2 > 100)     // propagate t2=26 -> if (26 > 100)
        slow_path();  //   fold          -> if (false)  -> branch is dead
    else
        fast_path();  // only this survives

Fold + propagate together collapsed the arithmetic AND killed a branch.

常數傳播與摺疊來回乒乓，直到算術消失、且某個分支可被證明永遠不會走——此時死碼消除就把慢路徑整個刪掉。這整串連鎖反應，是內聯把常數 5 帶進視野裡才解鎖的。

看看那串連鎖反應在最後做了什麼：一旦條件摺疊成常數，整整一個分支就變得可被證明不可達。這把接力棒交給了死碼消除，它刪除任何結果從不被觀察的計算——而你在 SSA 那篇導引裡已經看過，一旦每個名字只有單一定義，這件事為何近乎平凡。一個同門的清理工作，共同子運算式消除，會察覺同一個運算式以相同輸入被算了兩次（兩處各自的 a * b，而其間 a 與 b 都沒變），只留一份、重用它的結果。這些都不稀奇；合在一起，它們就是讓 -O2 程式碼比你手寫的緊實得多的家常本領。

迴圈：時間真正花掉的地方

程式幾乎把全部的時間都花在迴圈裡，所以最佳化器在那裡打得最兇。第一個、也最直觀的迴圈變換是 迴圈不變式碼外提，通常叫做 LICM。如果迴圈本體裡的某個計算，每一次迭代都產生相同的值——它只依賴迴圈裡不會變的東西——那就沒有理由每一圈都重算一次。LICM 把那個計算外提到迴圈之上，讓它恰好只跑一次。一個典型的犯人，是本體每一趟都重算的陣列長度、或某個「指標加偏移」的位址；把它拉出來，一個原本把那份工作做了一百萬次的迴圈，現在只做一次。

第二個是 強度削減：把一個昂貴的操作換成一個算出同樣結果、卻更便宜的。教科書案例是一個用計數器 i 去索引陣列的迴圈，每次迭代把位元組位址算成 base + i * 4。乘法比加法貴，而跨迭代 i 每次只增加 1，所以 i * 4 每次只增加 4。編譯器把那個重複的乘法，變成一個它每趟往前推 4 的「滾動位址」——乘法變成了加法。強度削減也涵蓋這類把戲：把 x * 8 變成移位 x << 3、把除以一個常數 2 的次方變成移位，因為移位與加法遠比一般的乘法與除法便宜。

展開與向量化：每趟做更多事

就算是一個很緊的迴圈，每次迭代也得付一份與真正工作無關的固定成本：把計數器加一、拿它跟上界比、跳回頂端。迴圈展開藉由在一次迭代裡把本體貼上好幾份，來稀釋那份開銷。把一個迴圈展開 4 倍，它在檢查計數器之前就做了四個元素份量的工作，於是每四個有用操作才付一次每迭代的記帳，而不是每一個都付。它也給後端一段更長、筆直的指令序列去排程與重疊，這是管線化的 CPU 最愛的。代價是更大的程式碼，以及一個麻煩的餘數——如果迴圈次數不是 4 的倍數，編譯器會發出一個小小的尾迴圈，去收拾剩下的那幾次迭代。

展開為那件壓軸好戲鋪好了舞台：自動向量化。現代 CPU 有 SIMD 指令——單一指令、多筆資料——一口氣對一整個向量的值動作，比方說用一條指令把八對 32 位元數字相加。如果你迴圈的各次迭代彼此獨立，編譯器就能把迴圈改寫成每一趟用這些寬指令處理一向量份量的元素，而不是一次一個。一個一次一個把一百萬個浮點數加總的迴圈，可以變成一個一次加八個的迴圈，對同一個答案大約八倍地減少指令數。向量化正是現代硬體上最大的數值加速來自之處，而它直接建立在上面那些迴圈工作之上。

誠實地談談為什麼向量化這麼常點不著火，因為理由很有教育意義。編譯器只在它能證明各次迭代真正獨立時才會向量化，而有三件事經常擋下這個證明：迴圈攜帶的相依性（每次迭代讀取前一次寫入的東西）、可能的別名（兩個編譯器無法證明相異的指標，於是透過其一寫入也許會改變另一個讀到的東西），以及本體裡糾結的控制流程。這就是為什麼一個在你看來顯然可平行的迴圈，可能仍維持純量——也是為什麼編譯器提供向量化報告（試試 clang 的 -Rpass=loop-vectorize 或 -Rpass-missed），逐一告訴你它對每個迴圈做了什麼、又是什麼擋住了它。

這些 pass 如何串成一場連鎖反應

這些最佳化沒有任何單獨一個就是故事的全部；魔法在於它們如何把工作交給彼此，正如你在 LLVM 那篇導引裡看過的 pass 排序所做的。標準的鏈條是這樣跑的：內聯把一個被呼叫者貼進來、抹去一道邊界；常數傳播把呼叫端已知的值推進貼進來的本體；摺疊把如今已是常數的算術塌縮掉；一個摺疊出的條件讓某個分支可被證明已死；死碼消除刪掉那個不可達的分支、以及只有它用到的任何計算。每一步本身都很簡單，但每一步都創造出下一步所需要的機會。

內聯：把被呼叫函式的本體就地貼進呼叫點，讓呼叫端的事實與被呼叫端的程式碼肩並肩坐在一起，中間沒有邊界。
傳播：把每個如今已知值的使用處換成那個常數本身，將呼叫端的常數推進貼進來的本體深處。
摺疊：在編譯期算掉任何輸入全是常數的操作，於是 5 * 5 + 1 直接變成 26。
消除：一個摺疊成常數的條件讓某個分支不可達，於是死碼消除刪掉那個分支、以及只有它用到的一切。
在迴圈上重複：本體如今更小更清晰，把不變式外提、把乘法削減成加法、展開，並在各次迭代獨立之處向量化。

兩個誠實的框架，能讓這一切保持在正確的視角。第一，這裡每一個改寫都由你在第 1 篇遇過的同一條單一規則授權——彷彿規則：只要可觀察行為不變，編譯器就能用任何方式改寫你的程式碼，這正是為什麼一個被刪掉的變數、或一個被摺疊的計算，仍然是一次正確的編譯。第二，這一切都不是你該指望它去修好爛演算法的魔法：最佳化器讓你的程式碼更快，不是讓你的點子更好，它沒辦法把一個平方的迴圈變成線性的。叫得出這些 pass 的名字，最有用之處不在手動微調，而在讀懂 -O2 產出了什麼——以及理解為什麼，當未定義行為讓最佳化器假設了太多，同一套機械裝置就能讓一個臭蟲在 -O0 消失、在 -O2 咬人，而那正是下一篇導引接手之處。