Exact Pattern-Aware Extraction for Equality Saturation via Bounded-Depth Tree Covering
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).
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}
}
EUVIMED