4.2 中間表示：三址碼與 SSA#

為什麼需要中間表示#

若編譯器直接從 AST 產生機器碼，每種「語言 × 機器」組合都要重寫最佳化。1960 年代的 UNCOL 計畫、1970 年代 Pascal 的 P-code（Niklaus Wirth, 1970s 初，讓 Pascal 可攜到任何有 P-code 直譯器的機器）、Smalltalk-80 的 bytecode 都是「一次編譯、多處執行」的嘗試。編譯器內部的中間表示（Intermediate Representation, IR）則追求另一件事：成為最佳化的工作台——與語言無關、與機器大致無關、結構適合分析變換。

三址碼（Three-Address Code, TAC）#

三址碼每條指令最多三個位址（兩個運算元、一個結果）：

t1 = b + c
t2 = a * t1
x  = t2

複雜運算式被拉平成線性指令序列，臨時變數顯式化。控制流用標籤與 goto：

  if x < 10 goto L1
  t = x * 2
  goto L2
L1:
  t = x + 1
L2:
  y = t

指令集通常包含：二元/一元運算、複製、無條件/條件跳轉、索引取址、參數傳遞、呼叫與回返。TAC 可實作為四元組（op, arg1, arg2, result）陣列或靜態單指派鏈結串列。Wirth 的 P-code 與 Java bytecode 都可視為 TAC 的堆疊機變體。

從 AST 產生 TAC（語意動作驅動）：

gen(E, target):
  case Num(n):  emit(target = n)
  case Var(x):  emit(target = x)
  case BinOp(op, a, b):
    t1 = new_temp(); gen(a, t1)
    t2 = new_temp(); gen(b, t2)
    emit(target = t1 op t2)
  case Assign(x, e):
    gen(e, x)

SSA：靜態單指派形式#

SSA（Static Single Assignment） 由 IBM 的 Ron Cytron、Jeanne Ferrante、Barry Rosen、Mark Wegman、Ken Zadeck 於 1980 年代末提出（關鍵論文 1991 年發表），並在 Bowen Alpern 等人的 IBM PL.8 編譯器中實現。核心規則只有一條：

每個變數只被賦值一次。

賦值第二次時改用新編號，在控制流匯合點以 ** \(\phi\) 函數**合併不同路徑上的值：

原始:                SSA:
if (c) x = 1;        if (c) x1 = 1;
else    x = 2;       else    x2 = 2;
y = x + 1;           y = phi(x1, x2) + 1;

\(\phi\) 函數是「虛擬的」：它選擇由哪條前驅邊進來的那個版本。實作時 \(\phi\) 變成平行複製或機器特定指令（x86 無此指令，需在暫存器配置後消除）。

放置 \(\phi\) 的演算法#

迭代支配邊界法（Cytron et al.）：對每個變數 v，計算所有賦值點集合 \(S_v\) ； \(\phi\) 需放在 \(S_v\) 的支配邊界（dominance frontier）。支配（dominance）：節點 A 支配 B 表示所有從進入點到 B 的路徑都經過 A；支配樹可用 Lengauer–Tarjan 演算法（1979） \(O(n\,\alpha(n))\) 求得。

放置 phi(Sv):
  worklist = Sv; W = Sv
  while W 非空:
    取出 X
    for Y in DF(X):          // X 的支配邊界
      if Y 尚無 v 的 phi:
        在 Y 插入 v 的 phi
        if Y not in W: W += Y

最小 SSA 與修剪 SSA：避免插入「之後永遠不會用」的 \(\phi\) （需 liveness 資訊）。

為何 SSA 是最佳化的黃金表示#

use-def 鏈顯式化：每個使用的定義唯一，資料流分析從「集合」變成「跟著編號走」，常數傳播、死碼刪除變得簡單且強。
稀疏性：分析成本與程式大小近似線性，而非傳統位元向量法的「程式大小 × 變數數」。
命名即價值：兩個 SSA 名相同 ⇔ 同一值，全域值編號（GVN）等最佳化因此自然。

現代 IR（LLVM IR、Swift SIL、Rust MIR）皆為 SSA 形式，或以 SSA 為基礎再附加語言特性。

IR 的其他形式#

形式	代表	適合
樹狀/圖	AST、DAG	高階變換、公共子表示式
線性三址碼	TAC、LLVM IR 指令	資料流分析
堆疊機	JVM bytecode、CPython bytecode	直譯、可攜
CPS / ANF	函數式編譯器	尾呼叫、控制流重構

小結#

三址碼把結構化程式拉平，是理解指令選擇的基礎。
SSA（Cytron et al., 1991）以「單指派 + \(\phi\) 」重塑資料流分析，支配邊界是其數學核心。
現代編譯器的中端（LLVM 的 opt、GCC 的 GIMPLE）都以 SSA 為基礎，第 5 章的最佳化皆在此形式上進行。