編譯器拿來自言自語的那種語言
在上一篇導引裡，你走過了整條編譯器管線：前端把你的文字剖析成一棵樹並檢查它說得通，後端發出真正的指令，而夾在中間的，正是真正的聰明之處發生的地方。那個「中間」就是我們現在落腳的地方。中端做的第一件事，就是把你的原始文字徹底丟掉。它並不最佳化 C、不最佳化 Rust、也不最佳化 C++——那些太糾結了，滿是語法與特例。它反而把你的程式翻譯成它自己的私房語言，叫做中介表示法，簡稱 IR，從此以後它只對 IR 進行推理。
為什麼要費事弄出第三種語言，它既不是你的原始碼、也不是機器的指令？因為一個好的 IR 刻意地簡單而規則，那種簡單規則是兩端都不具備的。它沒有巢狀的運算式、沒有語法糖；每個操作只對具名的值做一件小事。經典的形態是三位址碼，其中每條指令最多指名一個運算子與三個運算元——典型上是兩個輸入、一個輸出，就像 t1 = a + b。一個雜亂的原始運算式，例如 x = a + b * c，會變成一小串扁平的序列，每一步恰好只含一個操作，每個中間值都被賦予一個全新的名字。
source: x = a + b * c;
three-address code:
t1 = b * c
t2 = a + t1
x = t2
Notice: each line has one operator and a fresh result name.
The nested tree is gone; the order of evaluation is now explicit.IR 值回票價還有第二個理由，而這個是工程上的。如果你支援 5 種原始語言與 4 種目標晶片，從每種語言直接走到每種晶片，那是 20 個各自獨立的翻譯器。把所有東西都漏斗般地匯入一個共享的 IR，你就只要寫 5 個前端加 4 個後端——是 9 個零件，不是 20 個——而你在 IR 上寫的每一個最佳化，都同時嘉惠了全部 5 種語言與全部 4 種晶片。正是這一個決定，讓 IR 坐落在管線的腰部，又窄又共享，語言們在它上方扇形匯入，機器們在它下方扇形散出。
那個惱人的障礙：一個意思變來變去的名字
純粹的三位址碼已經比原始碼好得多了，但它仍從你原本的程式裡帶來一個麻煩：一個變數可以被賦值不只一次。看一個叫做 x 的值。如果你問「x 在這裡是什麼？」，誠實的答案是「看哪一次賦值最近執行過」，而那取決於控制流程——走了哪個分支、迴圈轉了幾圈。編譯器想做的每一項分析，都得拖著這個「x 的哪一個定義抵達了這個使用處？」的問題，而要橫跨分支與迴圈去回答它，是真的很麻煩。
這裡有一幅關於這個痛點的具體圖像。假設 x = 1，接著一個 if 分支可能做 x = 2，然後你讀取 x。單一名字 x 有兩個定義，而哪一個抵達那個讀取，取決於那個分支。任何想要（比方說）把一個常數傳遞進那個讀取的最佳化，都得先證明哪一個定義在那裡是有效的——而它得對每個變數、在每個使用處、遍及整個函式，重做一遍這個推理。名字 x 身兼太多職務，而這種過載正是那個障礙。
那個妙招：讓每個名字恰好只被賦值一次
這個修法說出來簡單得驚人，後果卻很深遠。改寫 IR，讓每個變數恰好只被賦值一次。這就是靜態單一賦值，幾乎總是被稱為 SSA 形式。每當原本的程式會重新賦值 x，你就改為發明一個全新的名字：第一個變成 x1、第二個 x2、第三個 x3，而每個使用處都被改寫成指向定義它的那個特定版本。如今，一個名字與定義它的那條指令是同一回事。問「x2 是什麼？」，恰好只有一個答案，恰好在一個地方算出來——不需要任何控制流程的偵探工作。
「靜態」這個詞很重要，也是常見的混淆點：它的意思是每個名字在程式的文字裡恰好出現在一次賦值的左邊，並不是說那個值在程式執行時只被算一次。一個定義在迴圈本體裡的名字，例如 i2，只有一條定義指令，卻會執行成千上萬次——單一賦值是靜態程式碼的性質，不是動態執行的性質。把這點釐清之後，好處立竿見影。因為每個名字都有唯一的定義，「哪一個定義抵達這個使用處？」根本就不再是個問題了；那個使用處直接就指名了它的定義。那些原本糾纏成一團的「抵達定義」分析最佳化，塌縮成了一次平凡的查表。
分支匯合之處：phi 節點
有一個地方，「一名一定義」的規則看似會破功，而解決它正是 SSA 全部的魔法所在。回到那個 if 分支：分支前 x1 = 1、分支裡 x2 = 2，然後你讀取 x。在匯合點之後，那個讀取該用哪個名字——x1 還是 x2？這真的取決於走了哪條路徑，所以沒有一個單一的答案可以事先寫死。SSA 用一條放在匯合處的特殊偽指令來解決，那就是 phi 節點。它讀起來像是 x3 = phi(來自直落邊的 x1，來自分支邊的 x2)：如果控制是從第一個前驅區塊抵達的，它就選 x1；如果是從另一個抵達的，就選 x2；並定義一個全新的名字 x3，供之後每個使用處指涉。
before SSA: after SSA:
x = 1; x1 = 1
if (cond) branch cond -> B_then, B_join
x = 2; B_then: x2 = 2; jump B_join
use(x); B_join: x3 = phi(x1 from entry, x2 from B_then)
use(x3)
The phi node sits at the merge and picks the right incoming
version based on which block control came from.兩條誠實的但書，能讓 phi 節點不再像是障眼法。第一，phi 不是 CPU 能執行的真正指令——沒有任何晶片有「依你從哪個區塊來而挑一個值」的運算碼。它純粹是 IR 內部的一個標籤。當編譯器在前往機器碼的路上離開 SSA 時，它會在前驅區塊的結尾插入普通的複製指令來移除每一個 phi（在一條進入邊上放 x3 = x1、在另一條上放 x3 = x2），而暫存器配置器接著大多會讓這些複製消失。第二，phi 節點正是為什麼一個繞著迴圈往回流的值仍然遵守單一賦值：迴圈標頭帶著一個 phi，把初始值與來自前一次迭代的值合併起來，讓迴圈變數即使每一圈都明顯改變，卻仍只有一個定義。
為什麼最佳化器愛上了 SSA
這一整套機械裝置之所以存在，是為了讓最佳化既更簡單又更強，而值得從頭到尾看一個運作的例子。拿死碼消除來說，它刪除結果從未被使用的計算。在 SSA 裡這變得簡單到幾乎令人尷尬：既然每個名字恰好只有一個定義，一個值「死了」恰好就等於它的名字出現在零個後續使用處。掃一遍 IR，把每個被使用的名字標記起來，然後刪除任何沒被標記的名字的定義指令——不需要流程分析、不需要對重新賦值進行推理，只需要數一數每個名字的使用次數。常數傳遞也同樣直接：如果 x2 被定義為 x2 = 7，那麼 x2 的每一個讀者——而且關於那些讀者是誰毫無歧義——都可以被遞上字面常數 7。
這些最佳化以小而專注的編譯階段（pass）形式運行，每一個讀取 IR 並把它改寫一點點，而 SSA 正是讓它們能乾淨地串接起來的關鍵：一個 pass 摺疊一個常數，使得某個分支永遠被走，使得某個區塊變得不可達，使得下一個 pass 得以刪除它——而因為 IR 自始至終都保持在 SSA 裡，每個 pass 都不需要全域的重新分析就能信任它所看到的名字。這正是為什麼正式的編譯器如此廣泛地採用了 SSA。最著名的例子 LLVM IR，就是一個基於 SSA 的三位址 IR，而下一篇導引整篇都奉獻給閱讀它、並看著它的 pass 管線轉換真實的程式碼。