D. Whitfield
M. L. Soffa
ABSTRACT
As an approach to deriving an application order of optimizing transformations, a framework is developed for examining the interactions of the transformations. The framework is based on an axiomatic specification technique and includes both pre-conditions and post conditions that must exist before and after applying optimizations. For a selected set of optimizations, the framework is used to determine those interactions among the optimizations that can create conditions and those that can destroy conditions for applying other optimizations. From these interactions, an application order is derived to obtain the potential benefits of the optimizations that can be applied to a program. In some cases, the ordering of a pair of optimizations is unambiguous in that one optimization can either create or destroy the conditions for the other. In the few cases where there is a cyclic interaction, the ordering is resolved based on the perceived importance of the two optimizations.
- 1.Alfred Aho and Jeffrey Ullman, in Principles of Compiler Design, Addison-Wesley Publishing Co., Reading, MA, 1979. Google Scholar
Digital Library
- 2.Alfred Aho, Ravi Sethi, and Jeffrey Ullman, in Compilers Principles, Techniques, and Tools, Addison-Wesley Publishing Co., Reading, MA, 1986. Google ScholarDigital Library
- 3.Alexender Aiken and Alexandru Nicolau, "A Development Environment for Horizontal Microcode," IEEE Transactions of Software Engineering, vol. 14, no. 5, pp. 584-594, May 1988. Google ScholarDigital Library
- 4.Frances Allen, "Program Optimization," in Annual Review in Automatic Programming 5, ed. L. Bolliet et al., pp. 239-307, Pergammon Press, New York, 1969.Google Scholar
- 5.Frances Allen and John Cocke, "A Catalogue of Optimizing Transformations," in Design and Optimization of Compilers, ed. R. Rustin, pp. 1-30, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1971.Google Scholar
- 6.Randy Allen and Ken Kennedy, "Automatic Translation of FORTRAN Programs to Vector Form," A CM Transactions of Programming Languages and Systems, vol. 9, no. 4, pp. 491-542, October 1987. Google ScholarDigital Library
- 7.Jeanne Ferrante, Karl J. Ottenstein, and Joe D. Warren, "The Program Dependence Graph and its Use in Optimization," ACM TOPLAS, vol. 9, no. 3, pp. 319-349, 1987. Google ScholarDigital Library
- 8.Mahadevan Ganapathi and Charles N. Fischer, "Integrating Code Generation and Peephole Optimization," Acta lnformatica, vol. 25, no. 1, pp. 85- 109, Jan., 1988. Google ScholarDigital Library
- 9.C.A.R. H oare, "An Axiomatic Basis for Computer Programming," CACM, vol. 12, no. 10, pp. 576- 583, October 1969. Google ScholarDigital Library
- 10.David B. Loveman, "Program Improvement by Source-to-Source Transformation," JACM, vol. 24, no. 1, pp. 121-145, Jan 1977. Google ScholarDigital Library
- 11.David A. Padua and Michael J. Wolfe, "Advanced Compiler Optimizations for Supercomputers," Communications of the ACM, vol. 29, no. 12, pp. 1184-1201, Dec 1986. Google ScholarDigital Library
- 12.Lori L. Pollock and Mary Lou Sofia, "Incremental Global Optimization for Faster Recompilation,'" Proceedings of IEEE International Conference on Computer Languages '90, March 1990.Google Scholar
- 13.Michael Wolfe and Uptal Banerjee, "Data Dependence and Its Application to Parallel Processing," international Journal of Parallel Programming, vol. 16, no. 2, pp. 137-178, 1987. Google ScholarDigital Library
- 14.Michael Wolfe, in Optimizing Supercompilers for Supercomputers, The MIT Press, Cambridge, MA, 1989. Google ScholarDigital Library
Index Terms
- An approach to ordering optimizing transformations
Recommendations
An approach to ordering optimizing transformations
As an approach to deriving an application order of optimizing transformations, a framework is developed for examining the interactions of the transformations. The framework is based on an axiomatic specification technique and includes both pre-...
Structuring Optimizing Transformations and Proving Them Sound
A compiler optimization is sound if the optimized program that it produces is semantically equivalent to the input program. The proofs of semantic equivalence are usually tedious. To reduce the efforts required, we identify a set of common ...
Comments