ROVER: RTL Optimization via Verified E-Graph Rewriting

Samuel Coward, Theo Drane, George A. Constantinides

Abstract

ROVER is an automated optimization tool for hardware datapath designs (RTL) that leverages e-graphs and equality saturation to navigate complex design spaces. By integrating automated rewrite-rule discovery with a formally verified equivalence-checking pipeline, ROVER achieves area reductions of up to 63%, frequently surpassing the performance of both human experts and commercial synthesis tools.

Introduction

In semiconductor design, manual optimization of Register Transfer Level (RTL) code remains common because commercial logic synthesis tools often fail to identify optimal datapath architectures. Hardware optimization is inherently non-monotonic; achieving a highly efficient design frequently requires applying transformations that initially appear to degrade performance—such as duplicating operators—to unlock significant downstream simplifications. Traditional "destructive" rewriting tools, which replace one structure with another, are prone to local optima. ROVER addresses these challenges by treating optimization as a graph-rewriting problem supported by formal verification.

Methodology

ROVER introduces a robust pipeline for datapath optimization centered on three core innovations:

The ROVER optimization and verification pipeline
  1. E-Graphs and Equality Saturation: ROVER utilizes e-graphs to represent all discovered equivalent versions of a design simultaneously. This approach avoids the "phase-ordering problem," where the sequence of applied rules limits the final design quality.
  2. Automated Condition Synthesis: To handle the nuances of hardware bitvectors (e.g., bitwidth and signage), ROVER uses program synthesis and decision tree classifiers to automatically learn the validity conditions for rewrite rules.
  3. Verified Extraction: ROVER employs an Integer Linear Programming (ILP) model to select the optimal design from the e-graph, accounting for common sub-expression elimination. Crucially, it generates a "proof certificate"—a sequence of simple equivalences—that can be verified by industrial equivalence checkers (EC).

The system operates on VeriLang, a custom intermediate representation tailored for hardware bitvectors.

Key Insights: The Power of Non-Monotonicity

A defining characteristic of ROVER's approach is its ability to explore "worse" designs to find better ones.

Circuit area change during optimization

As shown in the optimization trace, the circuit area metric often increases significantly during the rewrite process before plummeting to a final state much lower than the original. This confirms that temporary design expansion is often a prerequisite for global optimization. Furthermore, ROVER adapts architectures based on bitwidth; for instance, it might switch from individual adders to a SUM-tree or Fused-Multiply-Add (FMA) structure as constraints change.

Evaluation and Results

ROVER was evaluated against industrial and academic benchmarks, including Intel media kernels and standard FIR filters. Key findings include:

  • Significant Area Savings: ROVER achieved a peak area reduction of 63% on Shift-Multiplier benchmarks.
  • Outperforming Experts: On an Intel Media Kernel previously optimized by human experts, ROVER reduced both area and delay by an additional 50%.
  • Synthesis Resilience: By exploring the design space, ROVER identifies "synthesis-friendly" RTL versions that commercial tools like Synopsys Design Compiler can optimize more effectively.
  • Efficient Verification: While industrial tools often time out on complex end-to-end comparisons, ROVER’s decomposed proof chain allows verification to complete in seconds.

Conclusion and Future Work

ROVER demonstrates the efficacy of e-graphs for hardware optimization. Future work will focus on incorporating more sophisticated timing and delay models into the cost function and improving the scalability of the ILP extraction process for larger e-graphs. Integrating formal theorem provers like ACL2 could further enhance the "correct-by-construction" nature of the synthesized rules.

Summary updated

Abstract

Manual register transfer level (RTL) design and optimization remains prevalent across the semiconductor industry because commercial logic and high-level synthesis tools are unable to match human designs. Our experience in industrial datapath design demonstrates that manual optimization can typically be decomposed into a sequence of local equivalence preserving transformations. By formulating datapath optimization as a graph rewriting problem we automate design space exploration in a tool we call ROVER.We develop a set of mixed precision RTL rewrite rules inspired by designers at Intel and an accompanying automated validation framework. A particular challenge in datapath design is to determine a productive order in which to apply transformations as this can be design dependent. ROVER resolves this problem by building upon the e-graph data structure, which compactly represents a design space of equivalent implementations. By applying rewrites to this data structure, ROVER generates a set of efficient and functionally equivalent design options. From the ROVER generated e-graph we select an efficient implementation. To accurately model the circuit area we develop a theoretical cost metric and then an integer linear programming model to extract the optimal implementation. To build trust in the generated design ROVER also produces a back-end verification certificate that can be checked using industrial tools.We apply ROVER to both Intel-provided and open-source benchmarks, and see up to a 63% reduction in circuit area. ROVER is also able to generate a customized library of distinct implementations from a given parameterizable RTL design, improving circuit area across the range of possible instantiations.
BibTeX
@article{coward2024rover,
  author = {Samuel Coward and Theo Drane and George A. Constantinides},
  title = {{ROVER: RTL Optimization via Verified E-Graph Rewriting}},
  journal = {IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.},
  year = {2024},
  url = {https://openreview.net/forum?id=8oF7IFyMlT},
}
Figure