非循環 e-graph：Cranelift 的中端優化器

背景

本文探討了 Cranelift 編譯器如何利用「無環 e-graph」（aegraph）作為其中端優化器的核心數據結構。作者 Chris Fallin 詳細說明了為了克服傳統 e-graph 在生產環境中可能導致的效能瓶頸，Cranelift 如何結合 Sea-of-nodes 概念與單一固定點循環（fixpoint loop），解決編譯器設計中長久以來的「優化順序問題」（pass-ordering problem），並在編譯速度與優化品質之間取得平衡。

社群觀點

針對 Cranelift 引入 e-graph 的做法，編譯器社群展開了深入的技術辯論。部分資深開發者如 pizlonator 對「優化順序問題」的嚴重性持保留態度，認為在實際開發中，這並非不可逾越的障礙。他指出，雖然 GVN 與負載消除（load elimination）的交互作用確實存在挑戰，但通常可以透過將兩者整合進同一個 pass 來解決。他更擔心 e-graph 的框架過於受限，未來若要加入無法以 e-graph 表達的複雜優化（如涉及高階類型推斷或逃逸分析的抽象解釋），這種架構可能會增加不必要的複雜性。

然而，作者 Chris Fallin 回應指出，Cranelift 的定位與 JavaScript JIT 不同，其目標是在極快的編譯速度下完成核心優化。他強調 aegraph 的真正價值在於提供了一個統一的框架，讓多種重寫規則能在單一循環中協作，而不需要反覆執行多個獨立的優化 pass。這種觀點得到了部分研究者的認同，認為 e-graph 的「等價飽和」並非其唯一的魔力來源，真正的關鍵在於如何有效地管理多種等價表示。

討論中也觸及了 Sea-of-nodes 結構的利弊。titzer 提到 V8 的 TurboFan 與 Graal IR 在這方面的不同實踐，指出將控制流與副作用（effects）顯式化雖然強大，但也帶來了調試困難與迴圈轉換複雜化等副作用。他觀察到 V8 團隊近期轉向更傳統的 IR 結構，部分原因在於 Sea-of-nodes 的學習曲線極高，且在大型圖表下的維護成本巨大。此外，也有開發者分享了 e-graph 在特殊領域的應用，例如在密碼學編譯器或 Rust 類型檢查器中，利用類似 e-graph 的等價關係處理邏輯，顯示出這種數據結構在傳統編譯優化之外的廣泛潛力。

延伸閱讀

在討論串中，參與者提到了多個與 e-graph 及 IR 設計相關的資源。包括專門處理等價飽和的庫 egg (egraphs-good.github.io)，以及將此概念引入 MLIR 的 Tamagoyaki 專案。針對類型系統與 Datalog 的結合，Niko Matsakis 關於 Rust 特徵求解器的部落格文章，以及 eqlog 與 egglog 等工具，提供了將 e-graph 應用於靜態分析的理論基礎。此外，關於 Sea-of-nodes 的爭議，Coffee Compiler Club 中 Cliff Click 與 V8 團隊的討論也是深入了解該架構缺陷與優勢的重要參考。