1991-SSA形式#
案件摘要#
1991 年，IBM 研究中心的 Cytron、Francesca、Knoop、Leeck、Reif、Wegman、Zadeck（Ron Cytron 等人）發表論文《Efficiently Computing Static Single Assignment Form and the Control Dependence Graph》，正式破解了「最小 SSA 形式的高效建構」這樁懸案。他們的推理鏈條乾淨俐落：支配樹 + 支配邊界（dominance frontier）兩個概念，讓 φ 函數的放置問題從「猜測與反覆修正」變成「一次算準」。從此 SSA 成為現代編譯器的通用中間表示——LLVM IR、GCC GIMPLE、V8 皆以它為骨幹。
前因 -- 為什麼會有這個案子#
- 多賦值變數的詛咒：傳統資料流分析中，一個變數在程式裡被賦值多次，優化器必須先算出「抵達定義（reaching definition）」——在每個使用點，到底是哪一次賦值生效？這是個不定方程組，要靠迭代求解。
- 迭代求解的代價：對 \(N\) 個定義、 \(E\) 條邊的資料流方程，迭代法最壞要 \(O(E \times N)\) 甚至更高，且每次優化後定義改變，整個分析要重算一遍。
- 前人的線索：1980s 末，Bowen 與 Alpern 等人在 IBM 提出變數「只賦值一次」的雛形想法，並注意到關鍵邊（critical edge，一個有多個後繼的節點連到一個有多個前驅的節點的邊）會妨礙 φ 的放置；Wegman 與 Zadeck 則發展了稀疏條件常數傳播。Cytron 等人把這些線索串成一個完整、可證明、高效的演算法。
線索與推理 -- 數學式、程式、理論#
核心洞察：每個變數只賦值一次#
SSA 的宣言只有一句話：讓每個變數在整個程式中只被賦值一次。原變數 \(x\) 的每次賦值變成新版本 \(x_1, x_2, x_3, \ldots\) ；在控制流匯合點，若兩條路徑帶來不同版本，就插入一個 φ（phi）函數來合併：
一旦每個變數只賦值一次，「抵達定義」問題瞬間退化為 \(O(1)\) 查表——使用點上的版本就是唯一的定義，根本不用再算。資料流方程組的迭代求解被徹底消滅。
最小 SSA 的放置問題：支配樹與支配邊界#
φ 該放在哪？不能亂放（會做出非最小 SSA），也不能放太少（會漏合併）。Cytron 等人給出兩個精確定義：
- 支配（dominance）：節點 \(d\) 支配節點 \(n\) （記作 \(d \ dom\ n\) ），若從入口到 \(n\) 的每一條路徑都必經 \(d\) 。
- 支配邊界（dominance frontier）：節點 \(n\) 的支配邊界 \(DF(n)\) 是所有满足「 \(n\) 支配某前驅、但 \(n\) 不嚴格支配自己」的節點 \(w\) 的集合：
直覺： \(DF(n)\) 就是「 \(n\) 的統治權剛好到此為止」的邊界地帶。Cytron 等人證明了關鍵定理：
其中 \(DF^+\) 是支配邊界的傳遞閉包（φ 本身也是一次賦值，會把邊界再往外推）。加上「對每條關鍵邊 (a,b) 沿 \(a\) 邊分裂節點」的預處理，演算法整體可在近線性時間 \(O(E \cdot \alpha(E))\) 內完成——一次算準，無需迭代。
轉換範例：before / after 對照#
原始程式（循環中多次賦值）：
// before：x 被賦值三次，使用點要算 reaching definition
while (i < n) {
if (c)
x = 1; // defs(x) 第 1 處
else
x = 2; // defs(x) 第 2 處
use(x); // 哪個 x 生效？必須資料流分析才知道
i = i + 1; // defs(i) 每圈都賦值
}
SSA 形式（每個變數只賦值一次，φ 合併版本）：
// after：i0, i1, x1, x2, x3 各只賦值一次
i0 = 0;
loop:
i1 = phi(i0, i2); // 匯合點：初值與循環值合併
if (c)
x1 = 1; // x 只賦值一次
else
x2 = 2;
x3 = phi(x1, x2); // 兩分支的 x 在此合併
use(x3); // O(1) 查表：就是 x3
i2 = i1 + 1;
if (i2 < n) goto loop;
use(x3) 不再需要任何分析——SSA 把「哪個定義生效」的資訊直接寫進變數名。
Python 模擬：計算支配邊界#
# 對控制流圖 (CFG) 計算支配邊界 DF(n)
# CFG 以字典表示：node -> set of successors
cfg = {
'entry': {'loop'},
'loop': {'then', 'else'},
'then': {'join'},
'else': {'join'},
'join': {'exit'},
'exit': set(),
}
nodes = list(cfg)
preds = {n: set() for n in nodes}
for u, succs in cfg.items():
for v in succs:
preds[v].add(u)
# 計算支配集合：迭代不動點（入口支配所有，其餘初始化為全集）
dom = {n: set(nodes) for n in nodes}
dom['entry'] = {'entry'}
changed = True
while changed:
changed = False
for n in nodes:
if n == 'entry':
continue
new = {n} | set.intersection(*(dom[p] for p in preds[n])) if preds[n] else {n}
if new != dom[n]:
dom[n] = new
changed = True
# 支配邊界：DF(n) = { w | n 支配某前驅 p，但 n 不嚴格支配 w }
DF = {n: set() for n in nodes}
for n in nodes:
for w in nodes:
if any(n in dom[p] and not (n in dom[w] and n != w) for p in preds[w]):
DF[n].add(w)
for n in nodes:
print(f"DF({n}) = {sorted(DF[n])}")
# 輸出：DF(loop) = ['exit'] 等——'loop' 的統治權在 'exit' 處終止，
# 因此循環變數的 φ 要沿著通往 exit 的邊界放置。
這段模擬印證了 Cytron 定理的結構：φ 的放置位置 = 支配邊界的聯集。實際編譯器（LLVM、GCC）用更快的半支配樹（semi-NCA）演算法算支配樹，但數學核心完全相同。
結案 -- 後果與影響#
- 優化變簡單：常數傳播（稀疏條件傳播）、死碼刪除（SSA 中無人使用的版本即死碼）、GVN（值編號，相同運算式直接共用版本）——原本需要全域資料流分析的優化，在 SSA 上都變成稀疏的、近線性時間的圖遍歷。
- 成為通用 IR：GCC 4.0 起的 GIMPLE、LLVM IR、V8 的 TurboFan IR、HotSpot 的 C2 圖——現代編譯器清一色以 SSA 為中間表示基礎，SSA 從論文變成整個產業的骨架。
- 理論延伸：SSA 與函數式語言的延續傳遞風格（CPS）被證明同構（Appel、Kelsey）；記憶體 SSA、Loop-Nest SSA 等延伸不斷出現。
- 考古定位：Cytron 等人 1991 論文被引用超過萬次，是編譯器史上被引用最多的論文之一——「支配樹 + 支配邊界」兩個概念，終結了資料流分析的迭代時代。
關鍵人物與文獻#
- Ron Cytron、Jeanne Ferrante、Barry Rosen、Mark Wegman、Kenneth Zadeck（IBM 研究中心）：1991 年 SSA 高效建構演算法。
- 文獻：
- R. Cytron et al., "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph," ACM TOPLAS 13(4), 1991.
- B. Alpern, M. Wegman, K. Zadeck, "Detecting Equality of Variables in Programs," POPL 1988.
- C. Lattner, V. Adve, "LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation," CGO 2004.