Combining analyses, combining optimizations

C Click, KD Cooper - ACM Transactions on Programming Languages …, 1995 - dl.acm.org
C Click, KD Cooper
ACM Transactions on Programming Languages and Systems (TOPLAS), 1995dl.acm.org
Modern optimizing compilers use several passes over a program's intermediate
representation to generate good code. Many of these optimizations exhibit a phase-ordering
problem. Getting the best code may require iterating optimizations until a fixed point is
reached. Combining these phases can lead to the discovery of more facts about the
program, exposing more opportunities for optimization. This article presents a framework for
describing optimizations. It shows how to combine two such frameworks and how to reason …
Modern optimizing compilers use several passes over a program's intermediate representation to generate good code. Many of these optimizations exhibit a phase-ordering problem. Getting the best code may require iterating optimizations until a fixed point is reached. Combining these phases can lead to the discovery of more facts about the program, exposing more opportunities for optimization. This article presents a framework for describing optimizations. It shows how to combine two such frameworks and how to reason about the properties of the resulting framework. The structure of the frame work provides insight into when a combination yields better results. To make the ideas more concrete, this article presents a framework for combining constant propagation, value numbering, and unreachable-code elimination. It is an open question as to what other frameworks can be combined in this way.
ACM Digital Library