谷歌編譯器團隊藏了8年的優化術：讓代碼自己"認親"

2016年，Chrome V8團隊提交了一個編號為v8:4698的issue，抱怨某類重復計算讓YouTube頁面加載慢了12%。問題根源不是算法爛，而是編譯器沒發現兩段"長得一樣"的代碼其實在算同一個數。這個漏洞被堵上后，同樣的優化技術開始出現在Java、Rust、Go的編譯器里——它叫值編號（value numbering），一種讓編譯器自動識別"重復勞動"的技術。

SSA只是起點，值編號才是"去重"的關鍵

現代編譯器先把代碼轉成SSA（靜態單賦值）形式：每個變量只賦值一次，同名即同值。比如這段反復自增的代碼：

x = 0 x = x + 1 x = x + 1

SSA會把它拆成三個獨立名字：v0=0、v1=v0+1、v2=v1+1。好處是v1和v2不會混淆——雖然都是"+1"，但結果不同。但SSA沒解決另一個問題：如果后面又出現v0+1，編譯器能認出這就是v1嗎？

這就是值編號的用武之地。它給每個"計算結果"發身份證號，身份證號相同，結果必然相同。看這段擴展的IR（中間表示）：

v0 = 0 v1 = v0 + 1 v2 = v1 + 1 v3 = v0 + 1 ← 和v1一模一樣 v4 = do_something(v2, v3)

值編號會發現v3和v1的"身份證號"相同，直接把v3替換成v1。最終優化后：

v0 = 0 v1 = v0 + 1 v2 = v1 + 1 v4 = do_something(v2, v1)

一次加法運算被省掉。在JIT編譯器里，這類優化每天被執行數十億次。

沒有"文本"怎么比較？哈希是答案

IR里沒有真正的"文本"，指令是結構化的對象。怎么判斷兩條指令"長得一樣"？主流方案是哈希 consing（hash-consing）：給每條指令算哈希值，哈希沖突時再逐字段比較。

Maxine VM的實現很典型。它的Op2（二元操作基類）這樣定義等價性判斷：

// 哈希：把操作碼和兩個操作數的"身份證號"混合 int valueNumber() { return Hash.combine(opcode, x.valueNumber(), y.valueNumber()); } // 等價：操作碼相同，且兩個操作數分別等價 boolean valueEqual(Op2 other) { return opcode == other.opcode && x.valueEqual(other.x) && y.valueEqual(other.y); }

注意遞歸結構：操作數本身也是值編號系統的參與者。常量有固定編號，變量引用追蹤其定義，復合表達式逐層向上匯總。這套系統讓"等價"判斷既快又準——哈希先篩掉99%的不匹配，精確比較兜底。

JavaScriptCore（WebKit的JS引擎）走得更遠。它用"破壞性并查集"（destructive union-find）延遲重寫：先標記v3和v1等價，但不立即替換所有使用處。等專門的傳播 pass 再清理，減少中間態的反復修改。

從局部到全局：值編號的"視野"之爭

值編號分兩種粒度。局部值編號（LVN）只在單個基本塊內工作，實現簡單，一次線性掃描即可完成。全局值編號（GVN）跨基本塊，需要處理控制流合并時的φ節點——SSA的標志性結構。

GVN的難點是"同名不同命"。兩個分支各有一個v0+1，它們在控制流匯合處變成φ節點的兩個輸入。雖然文本相同，但運行時可能走不同分支，值編號必須保守處理。LLVM的GVN實現為此維護復雜的可達性分析，確保只在真正安全時合并。

2019年，Rust編譯器rustc引入基于HIR（高級IR）的GVN，把優化時機提前到類型檢查之后。這讓常量折疊和死代碼消除更早生效，后續MIR（中級IR）和LLVM IR的壓力驟減。編譯時間下降8%，而二進制體積沒變——說明早期GVN篩掉了大量冗余，沒讓后端做無用功。

邊界與陷阱：數學等價的"幻覺"

值編號有個危險假設：文本相同即語義相同。但浮點數打破了這條規則。0.0 + (-0.0)和-0.0 + 0.0哈希值相同，結果都是0.0——可符號位不同，后續除法可能產生+Inf或-Inf。Java的StrictMath因此禁用部分浮點優化，C/C++則靠-ffast-math把選擇權交給開發者。

更隱蔽的是內存操作。兩條load指令地址相同，但中間插了未知函數的調用——那個函數可能通過指針別名修改內存。LLVM的MemorySSA分析專門追蹤這類依賴，決定是否允許值編號復用。

2022年，GCC 12修復了一個潛伏7年的bug：某些情況下GVN會把volatile變量的讀操作錯誤合并，導致嵌入式系統的時序依賴崩潰。修復方案是給volatile操作單獨編號空間，永不與其他值合并。

值編號的"親戚"們

值編號不是孤立技術。它與公共子表達式消除（CSE）高度重疊——CSE是目標（減少重復計算），值編號是手段（識別重復）。與常量傳播結合時，值編號能發現(x*2)*3和x*6的等價性（需配合代數化簡）。

最有趣的交叉是循環優化。循環不變量外提（LICM）依賴值編號判斷某計算是否在每次迭代都產生相同結果。如果v0+1的v0在循環內不變，值編號會讓所有迭代共享同一個編號，LICM順勢把它提到循環外。

MLIR（LLVM的多級IR框架）把值編號擴展到了"方言"級別。不同領域專用IR（如TensorFlow的圖IR）可以復用同一套值編號基礎設施，只需定義自己的哈希和等價規則。Google的TFLite converter借此把移動端模型的常量折疊效率提升了40%。

一個未被回答的問題

值編號本質上是在問：兩段代碼的"身份"何時相同？SSA回答了變量層面，值編號回答了表達式層面，但程序的行為等價還涉及控制流、內存、I/O。當AI開始生成代碼，當編譯器需要優化神經網絡計算圖，"值"的邊界在哪里？LLVM的MLIR團隊正在實驗把值編號擴展到"區域"（region）級別——不是單條指令，而是整個子圖的等價性判斷。如果成功，我們或許能看到編譯器自動識別"這兩個for循環其實在干同一件事"，而不僅僅是"這兩個加法結果相同"。這種能力，會讓今天的優化器看起來像石器時代的手藝嗎？