A unifying framework for optimizing transformations
Deborah Whitfield · 1992
As an approach to understanding the properties of traditional compiler optimizations and parallelizing optimizations that are frequently applied to program code to increase the degree of parallelism, a Unifying Framework for Optimizing Transformations (UFOT) was developed for specifying optimizations and automatically producing optimizers. For a selected set of optimizations, the framework is used to determine those interactions among the optimizations that can create and those that can destroy conditions for applying other optimizations. From these interactions, an application order is derived that attempts to maximize the potential benefits of the optimizations that can be applied to a program. The framework is also used to create a General Optimization Specification Language (GOSpeL) whose implementation culminates in the development of an optimizer generator (GENesis) that automatically produces optimizers from specifications. The specifications are input into the generator, and code is produced for applying the specified optimizations. The optimizations are applied to an extended intermediate representation of a source program, thus making GENesis generally source language independent. GENesis is powerful in that it can generate optimizations that require global conditions, which are needed for traditional and parallelizing optimizations. A prototype implementation of GENesis has been constructed and numerous optimizers have been produced and verified. A variety of experiments have been performed and numerous results have been determined. Experimentation indicates that many theoretical interactions occur in practice, and application points for some optimizations are rarely found. The experiments also indicate that different orderings of optimizations are needed for different code segments of the same program. Thus, optimizations should be applied on a code segment basis rather than to an entire program. Experimentation was also performed to examine the cost of applying an optimization and the expected benefit. It was found that the cost of some optimizations as compared to their benefit is prohibitive, and in some cases the cost of an optimization can be reduced by carefully specifying the optimization. It was also found that the cost of some optimizations varies significantly with different implementations produced by the optimizer generator.