按年被提到
20102025 · 1 次2026
编程语言与编译器›类型系统与函数式语言·arXiv:1012.1802 · cs.PL

Equality Saturation: A New Approach to Optimization

Ross Tate, Michael Stepp, Zachary Tatlock, Sorin Lerner · 2010
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2025-05-15 · 最近 2026-03-25
2不同的人
2活跃月份
2讨论串
45被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Optimizations in a traditional compiler are applied sequentially, with each optimization destructively modifying the program to produce a transformed program that is then passed to the next optimization. We present a new approach for structuring the optimization phase of a compiler. In our approach, optimizations take the form of equality analyses that add equality information to a common intermediate representation. The optimizer works by repeatedly applying these analyses to infer equivalences between program fragments, thus saturating the intermediate representation with equalities. Once saturated, the intermediate representation encodes multiple optimized versions of the input program. At this point, a profitability heuristic picks the final optimized program from the various programs represented in the saturated representation. Our proposed way of structuring optimizers has a variety of benefits over previous approaches: our approach obviates the need to worry about optimization ordering, enables the use of a global optimization heuristic that selects among fully optimized programs, and can be used to perform translation validation, even on compilers other than our own. We present our approach, formalize it, and describe our choice of intermediate representation. We also present experimental results showing that our approach is practical in terms of time and space overhead, is effective at discovering intricate optimization opportunities, and is effective at performing translation validation for a realistic optimizer.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论thesz · 2025-05

“One can have obvious but repetitive optimizations with symbolic programming [1]. [1] https://arxiv.org/abs/1012.1802 Strange that AlphaEvolve authors do not compare their work to what is achievable by equality saturation. An implementation of equality saturation can take interesting integrals with very simple rules [2]. [2] https://github.com/alt-romes…”

AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms原评论 ↗
评论slwvx · 2026-03

“From https://arxiv.org/abs/1012.1802 we read the following about "equality saturation" which was a new term to me: >... We present a new approach for structuring the optimization phase of a compiler. In our approach, optimizations take the form of equality analyses that add equality information to a common intermediate representation. The optimizer work…”

Equality Saturation for Optimizing High-Level Julia IR原评论 ↗