Compass: Synthesis of Term Rewriting Systems with Bounded Completeness
Term rewriting is an important part of many optimizing compilers: the compiler engineer specifies a set of rewrite rules, and the compiler applies them to simplify programs. A rule set is convergent (confluent and terminating) and complete, if every term reaches, under any rule application order, a unique normal form that ideally is the smallest term among all semantically equivalent terms. Such rule sets are hard to construct manually, so compilers rely on rule sets without guarantees and heuristic application orders, or on equality saturation, which explores all rewrites in an e-graph but loses its guarantees when time or memory runs out before saturation, which is not uncommon in practice.
We present Compass, an algorithm that synthesizes rewrite rule sets that are convergent and complete for all ground terms up to a given size. Compass builds the rule set inductively over the term size and uses the system synthesized so far to prune the enumeration of candidate terms. We prove ground convergence and ground completeness and mechanize the proof in Lean. For theories with a finite universe, Compass provably terminates with a rule set that is convergent and complete for ground terms of all sizes.
In our evaluation on boolean, integer, and bitvector theories, greedy rewriting with Compass’s rule sets simplifies terms better and faster than equality saturation. Compass also compares favorably against Ruler and unfailing Knuth-Bendix completion in synthesis time, rule coverage, and simplification power.