EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Exact Pattern-Aware Extraction for Equality Saturation via Bounded-Depth Tree Covering

Zi Cheng, Mengting Yuan, Lefei Zhang

Algorithms · 11.05.2026 · 19 (5) · 377

DOI: 10.3390/a19050377 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithms, online erschienen am 11.05.2026. Verfasst von Zi Cheng und 2 weiteren Autor:innen. Die Arbeit nennt 15 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Equality saturation explores equivalent program expressions via e-graphs, and its extraction step selects one representative per equivalence class to form an output tree. Standard extraction minimizes a decomposable per-node cost function that cannot capture multi-node structural patterns arising in SMT preprocessing and compiler instruction selection. We formalize pattern-aware extraction as a weighted pattern cover problem on AND-OR DAGs and establish its correspondence to tree covering in instruction selection. Three challenges arise when migrating tree covering to e-graphs: annotation ambiguity from multiple candidates per class, context-dependent selection from depth-2 templates, and DAG sharing conflict. We show that the coupled selection–tiling problem reduces to a tree DP with three mutually exclusive tile-role states, generalizing BURS tree covering from fixed trees to AND-OR DAGs. A bottom-up pass computes optimal DP values, and a top-down pass traces back decisions to produce the output tree. For template depth at most two, the algorithm computes an exact optimum in O(N·K·|P|·Cmax) time. The evaluation targets extraction-level coverage, since end-to-end performance additionally depends on rewrite-rule design and saturation completeness. On SMT-COMP benchmarks, the algorithm achieves up to 31× higher weighted pattern coverage than standard extraction. Depth-2 tiling contributes 45–51% additional improvement, with overhead within 1.5× of standard extraction.

Zitieren

APA

Cheng, Z., Yuan, M., & Zhang, L. (2026). Exact Pattern-Aware Extraction for Equality Saturation via Bounded-Depth Tree Covering. Algorithms, 19(5), 377. https://doi.org/10.3390/a19050377

Vancouver

Cheng Z, Yuan M, Zhang L. Exact Pattern-Aware Extraction for Equality Saturation via Bounded-Depth Tree Covering. Algorithms. 2026;19(5):377. doi:10.3390/a19050377

BibTeX
@article{Cheng2026,
  author = {Cheng, Zi and Yuan, Mengting and Zhang, Lefei},
  title = {Exact Pattern-Aware Extraction for Equality Saturation via Bounded-Depth Tree Covering},
  journal = {Algorithms},
  year = {2026},
  volume = {19},
  number = {5},
  pages = {377},
  doi = {10.3390/a19050377}
}
Kostenlos starten →