在现代编译器架构中，中端优化器扮演着连接前端 IR 与后端代码生成的关键角色。Cranelift 作为 WebAssembly 运行时 Wasmtime 的核心代码生成器，近年来在其优化 pipeline 中引入了一种独特的数据结构 —— 无环 e-graph（acyclic e-graph，简称 aegraph）。这一设计并非简单地追随学术界对 e-graph 的热潮，而是在实际工程约束下做出的务实选择。本文将解析 aegraph 的核心设计理念，以及它如何影响寄存器分配与指令调度的效率。

从传递顺序问题到统一优化框架

Cranelift 在 2022 年引入 e-graph 优化的动机，源于一个经典的编译器工程难题：传递顺序问题（pass-ordering problem）。考虑这样一个场景：全局值编号（GVN）会将表达式规范化为唯一形式，而冗余负载消除（RLE）则需要识别可以合并的内存操作。如果分别运行这两个优化 pass，它们往往需要多次迭代才能收敛 —— 先运行 RLE 消除一个冗余 load，再运行 GVN 看到新出现的等价形式，再运行 RLE 消除由 GVN 产生的新冗余。这种串行迭代不仅效率低下，而且难以保证找到最优解。

传统的解决思路是手动编排 pass 的执行顺序，或者依赖经验性的启发式规则。但这种方法的缺陷在于：不同优化之间存在复杂的交互，手动编排难以覆盖所有场景。Cranelift 的方案是构建一个统一的优化框架，让所有优化 pass 在同一个数据表示上协同工作。这个框架的核心就是 aegraph。

aegraph 的设计借鉴了 sea-of-nodes 的思想：在优化过程中，将纯计算（无副作用的运算符）从控制流图中 “解放” 出来，让它们在数据流图中自由漂浮。这种表示的优势在于：所有等价的表达式可以被自动合并 —— 因为位置信息被移除，相同的计算自然会指向同一个节点。这相当于在构建 IR 时就自动完成了全局值编号的工作。

无环约束的工程化妥协

标准的 e-graph（如 egg 框架实现的）采用 equality saturation（等价饱和）策略：构建一个包含所有等价形式的超大图，然后通过迭代重写不断扩展可能性空间，最后用成本函数提取最优形式。这种方法在理论上是 “最优” 的，但在生产级编译器中面临两个严峻挑战。

首先是膨胀问题：e-graph 中的等价类可能指数级增长，因为每条 rewrite 规则都可能产生新的等价形式，即使规则本身看起来是 “简化” 的其二，传统的 e-graph 需要维护双向的使用者 - 定义者关系，以便在发现新等价时重新规范化所有使用者。这在大型函数上会产生显著的内存和缓存压力。

Cranelift 的关键洞察是：输入的 SSA 形式本身就是无环的（数据流环只能通过 phi 节点存在），而 eager rewriting（积极重写）策略可以保持这种无环性质。具体做法是：当创建一个新节点时，立即应用所有适用的重写规则，然后将原形式与优化后的形式通过 union 节点连接起来。由于从不回溯更新已有节点，无环性得以保持，同时只需要单次遍历即可完成所有优化。

对寄存器分配与指令调度的间接影响

aegraph 优化器对寄存器分配和指令调度的提升，主要体现在以下几个方面。

在寄存器分配层面，由于优化在更抽象的数据流图上完成，很多冗余计算在进入寄存器分配阶段之前就已经被消除。这意味着需要分配到物理寄存器的虚拟寄存器数量更少，live range 更短，发生寄存器冲突的概率也相应降低。Cranelift 的寄存器分配器基于 liverange 分析，在优化后更干净的 IR 上能够做出更精准的溢出决策。

在指令调度层面，aegraph 的 “展开”（elaboration）阶段提供了天然的调度机会。所谓的 scoped elaboration 算法在将纯计算节点放回控制流图时，实际上在进行一种隐式的代码 motion。循环不变代码移动（LICM）可以作为展开策略的一部分实现：只有当计算不依赖循环内部定义的变量时，才将其调度到循环入口之前。这种按需展开的机制，使得调度决策与优化阶段自然融合。

值得注意的是，Cranelift 的评测数据显示了一个 somewhat surprising 的结论：aegraph 的多表示能力（在同一等价类中保留多个可选表达式）在实际工作负载中收益极为有限。平均每个等价类只包含 1.13 个节点，这意味着大多数情况下只有一个 “明显更好” 的表达式。多表示带来的收益（约 0.1% 性能提升）与维护其数据结构的开销相比，几乎可以忽略。这一结论对编译器工程实践具有重要的参考价值：在追求理论完备性之前，应当先用真实工作负载验证复杂优化是否真的必要。

实践启示

Cranelift 的 aegraph 实践揭示了编译器优化中的一个重要权衡：理论上的优雅与工程上的务实之间的取舍。传统的 e-graph 方法提供了更强大的表达能力，但生产级编译器需要在编译时间与生成代码质量之间找到平衡。无环约束加 eager rewriting 的组合，在保留 e-graph 核心优势的同时，将性能开销控制在可接受范围内（约 7-8% 的额外编译时间）。

对于其他编译器项目而言，Cranelift 的经验表明：在引入复杂优化框架之前，应当首先建立基准测试，理解目标工作负载的实际优化空间；其次，优先实现那些收益明确、代价较小的优化（如 sea-of-nodes 表示带来的自动 GVN）；对于收益不确定的复杂特性，可以通过开关控制来评估其实际贡献。

参考资料

  • Chris Fallin, "The acyclic e-graph: Cranelift's mid-end optimizer", 2026
  • Cranelift GitHub Repository, bytecodealliance/wasmtime