E-morphic: Scalable Equality Saturation for Structural Exploration in Logic Synthesis

Chen Chen, Guangyu Hu, Cunxi Yu, Yuzhe Ma, Hongce Zhang

Introduction

Logic synthesis is a cornerstone of modern chip design, transforming high-level hardware descriptions into optimized networks of logic gates. A persistent challenge in this field is structural bias: the quality of the final technology mapping is heavily constrained by the initial structure of the logic graph. While traditional "lossless synthesis" attempts to mitigate this by providing multiple structural alternatives, these methods are often limited to local transformations and struggle with global optimization.

Equality saturation, powered by the e-graph data structure, offers a powerful alternative by simultaneously exploring a vast space of equivalent circuit structures. However, existing e-graph tools have historically failed to scale beyond small designs (typically under 40,000 nodes). E-morphic addresses these scalability bottlenecks, enabling equality saturation for industry-scale logic synthesis.

The E-morphic Framework

E-morphic is designed to augment traditional logic optimization flows by performing deep structural exploration when a circuit is already near a local optimum. The framework introduces several key innovations to ensure scalability and efficiency.

The E-morphic workflow integrating e-graph initialization, simulated annealing-based extraction, and ML-driven QoR evaluation.

Key Methodological Innovations

  1. Direct DAG-to-DAG Conversion: Traditional tools represent circuits as "S-expressions" (nested lists), which leads to exponential memory bloat for Directed Acyclic Graphs (DAGs) with high node sharing. E-morphic implements a direct graph-to-graph conversion, eliminating this primary memory bottleneck.
  2. Solution-Space Pruning: To manage the complexity of the e-graph, E-morphic filters out redundant nodes that do not contribute to cost reduction, significantly narrowing the search space for the extraction phase.
  3. Simulated Annealing (SA) Extractor: Unlike standard greedy extractors that often converge on local minima, E-morphic employs a Simulated Annealing approach. This probabilistic method allows the explorer to accept temporary increases in cost to eventually discover globally superior structures.
  4. Dual-Model Cost Estimation: To balance accuracy and speed, E-morphic utilizes a "Golden Model" based on the ABC static library for final evaluations and a Graph Neural Network (GNN)-based model for rapid Quality of Result (QoR) estimation during the iterative search process.

Experimental Evaluation

The framework was evaluated using the EPFL benchmark suite, encompassing a wide range of logic circuits from multipliers to memory controllers. The GNN-based cost estimator was trained on the OpenABC-D dataset, utilizing approximately 40,000 structural samples to predict area and delay metrics accurately.

Key Results and Insights

E-morphic demonstrates a significant breakthrough in both scalability and optimization quality. By treating the circuit as a graph throughout the pipeline, the tool successfully processed designs with over 400,000 nodes—a 10x improvement over previous state-of-the-art methods.

Comparison of delay reduction between independent optimization passes and E-morphic structural exploration.
  • Quality of Result (QoR): Compared to high-performance delay-optimization flows in the industry-standard ABC tool, E-morphic achieved an average 12.54% reduction in area and a 7.29% reduction in delay across large-scale benchmarks.
  • Computational Efficiency: The direct DAG-to-DAG conversion is orders of magnitude faster than S-expression-based methods. For complex circuits like hyp, E-morphic completed conversion in seconds, whereas previous tools frequently timed out.
  • Machine Learning Integration: The GNN-based cost model enabled a 28% runtime saving during the extraction process with minimal impact on the final result quality.

Conclusion and Future Work

E-morphic proves that equality saturation can be scaled to handle modern, large-scale logic designs. By strategically positioning e-graph exploration after traditional optimization passes, it effectively breaks through structural plateaus. While the GNN model currently exhibits a Mean Absolute Percentage Error (MAPE) of 25.2%, future improvements in predictive accuracy could further enhance performance. The authors suggest that these scalable techniques could be extended to other domains, such as High-Level Synthesis (HLS) and FPGA-specific optimizations.

Summary updated

BibTeX
@inproceedings{chen2025e,
  author = {Chen Chen and Guangyu Hu and Cunxi Yu and Yuzhe Ma and Hongce Zhang},
  title = {{E-morphic: Scalable Equality Saturation for Structural Exploration in Logic Synthesis}},
  booktitle = {DAC},
  year = {2025},
  doi = {10.1109/dac63849.2025.11133110},
}
Figure