Equality Saturation: A New Approach to Optimization

Details Equality Saturation: A New Approach to Optimization Equality Saturation: A New Approach to Optimization

2010-12-02

arxiv.org/abs/1012.1802v3

LMCS 7 (1:10) 2011

Computer Science

Programming Languages

80 pages, 39 figures

Scientific paper

10.2168/LMCS-7(1:10)2011

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.

Affiliated with

Also associated with

No associations

Rating

Equality Saturation: A New Approach to Optimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Equality Saturation: A New Approach to Optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Equality Saturation: A New Approach to Optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-604849