Equality Saturation for Datapath Synthesis: A Pathway to Pareto Optimality

Equality saturation, originally developed in the late 1970s for use in automated theorem provers, has been recently advanced to perform scalable rule-based rewriting for optimizations in various domains, such as program synthesis, compiler optimization, and datapath synthesis. Constructing an e-graph using rewrite rules that preserve program functionality, equality saturation addresses phase ordering problems in rewriting-driven optimizations. This promising approach shows significant potential for achieving Pareto optimality. This paper provides a brief introduction to equality saturation and the open-source tool egg, and highlights its potential application in optimizing datapaths in both RTL and high-level synthesis. We include case studies and outline the opportunities for future work in both datapath and logic synthesis using equality saturation.