The acyclic e-graph: Cranelift's mid-end optimizer
6 days ago
- #Cranelift
- #Compiler Optimization
- #E-Graphs
- Aegraph（无环e图）是Cranelift中间端优化器的核心数据结构，支持统一细粒度优化。
- 它通过将重写、规范化和代码移动集成到单个不动点循环中，解决了通道排序问题。
- 关键组件包括：纯操作符的节点海表示、用于转换回CFG的范围细化，以及保持无环性的急切重写。
- 联合节点允许高效的多重表示，无需传统e图开销，但基准测试显示对当前工作负载影响甚微。
- 提取采用简化的动态规划方法，忽略共享子结构，虽然高效但对于NP难问题并非最优。
- 评估表明，aegraph相比传统流水线可将代码性能提升约2%，编译时开销约为7-8%。
- 未来方向包括改进提取算法、控制流重写，以及集成目标特定的降级规则。