非巡回eグラフ：CraneliftのミドルエンドオプティマイザーAegraph

記事

• Cranelift（WebAssemblyコンパイラ）がミドルエンド最適化に非巡回eグラフ（aegraph）を採用
• Aegraphは複数の等価なプログラム表現を同時に保持し、より優れた最適化を実現
• パス順序問題を解消：GVN、DCEなどのパスを手動で並べる必要がなくなる
• 意外な発見：多値表現だけが主な利点ではない可能性がある

ディスカッション

• あるコンパイラエンジニアは「パス順序問題は誇張されている」と主張し、実際の主なユースケースはGVN＋ロード除去だと述べている
• Eグラフはコード生成だけでなく、型チェッカーやトレイトソルバーにも応用可能（Rustのトレイトソルバーが例として挙げられている）
• このアプローチの普及に貢献したeggライブラリ（egraphs-good.github.io）が参照されている
• Eグラフアプローチのコンパイル時間オーバーヘッドのトレードオフへの関心も高い

HN（Hacker News：技術系ニュースサイト）で議論する

原文（英語）: The acyclic e-graph: Cranelift’s mid-end optimizer