Caviar: An E-Graph Based TRS for Automatic Code Optimization

Smail Kourta, Adel Abderahmane Namani, Fatima Benbouzid-Si Tayeb, Kim Hazelwood, Chris Cummins, Hugh Leather, Riyadh Baghdadi

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Term Rewriting Systems (TRSs) are used in compilers to simplify and prove expressions. State-of-The-Art TRSs in compilers use a greedy algorithm that applies a set of rewriting rules in a predefined order (where some of the rules are not axiomatic). This leads to a loss of the ability to simplify certain expressions. E-graphs and equality saturation sidestep this issue by representing the different equivalent expressions in a compact manner from which the optimal expression can be extracted. While an e-graph-based TRS can be more powerful than a TRS that uses a greedy algorithm, it is slower because expressions may have a large or sometimes infinite number of equivalent expressions. Accelerating e-graph construction is crucial for making the use of e-graphs practical in compilers. In this paper, we present Caviar, an e-graph-based TRS for proving expressions within compilers. The main advantage of Caviar is its speed. It can prove expressions much faster than base e-graph TRSs. It relies on three techniques: 1) a technique that stops e-graphs from growing when the goal is reached, called Iteration Level Check; 2) a mechanism that balances exploration and exploitation in the equality saturation algorithm, called Pulsing Caviar; 3) a technique to stop e-graph construction before reaching saturation when a non-provable pattern is detected, called Non-Provable Patterns Detection (NPPD). We evaluate caviar on Halide, an optimizing compiler that relies on a greedy-Algorithm-based TRS to simplify and prove its expressions. The proposed techniques allow Caviar to accelerate e-graph expansion for the task of proving expressions. They also allow Caviar to prove expressions that Halide's TRS cannot prove while being only 0.68x slower. Caviar is publicly available at: <a></a>.

Original languageEnglish (US)
Title of host publicationCC 2022 - Proceedings of the 31st ACM SIGPLAN International Conference on Compiler Construction
EditorsBernhard Egger, Aaron Smith
PublisherAssociation for Computing Machinery, Inc
Number of pages11
ISBN (Electronic)9781450391832
StatePublished - Sep 19 2022
Event31st ACM SIGPLAN International Conference on Compiler Construction, CC 2022 - Virtual, Online, Korea, Republic of
Duration: Apr 2 2022Apr 3 2022

Publication series

NameCC 2022 - Proceedings of the 31st ACM SIGPLAN International Conference on Compiler Construction


Conference31st ACM SIGPLAN International Conference on Compiler Construction, CC 2022
Country/TerritoryKorea, Republic of
CityVirtual, Online


  • Algebraic expressions simplification
  • Equality Graphs
  • Equality Saturation
  • Term Rewriting Systems

ASJC Scopus subject areas

  • Hardware and Architecture
  • Signal Processing
  • Software


Dive into the research topics of 'Caviar: An E-Graph Based TRS for Automatic Code Optimization'. Together they form a unique fingerprint.

Cite this