Abstract
Important challenges for compiler optimization include determining what optimizations to apply, where to apply them and what is a good sequence in which to apply them. To address these challenges, an understanding of optimization properties is needed. We present a model-based framework, FOP, to determine how optimizations enable and disable one another. We combine the interaction and profitability properties to determine a "best" sequence for applying optimizations. FOP has three components: (1) a code model for the program, (2) optimization models that capture when optimizations are applicable and their actions, and (3) a resource model that expresses the hardware resources affected by optimizations. FOP determines interactions by comparing the create- and destroy-conditions of each optimization with the post conditions of other optimizations. We develop a technique with FOP to construct code-specific optimization sequences. Experimentally, we demonstrate that our approach achieves similarly good code quality as empirical techniques with less compile-time.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Almagor, L., Cooper, K., Grosul, A., Harvey, T., Reeves, S., Subramanian, D., Torczon, L., Waterman, T.: Finding Effective Compilation Sequences. In: Conf. On Languages, Compilers, and Tools for Embedded Systems (2004)
Bodík, R., Gupta, R., Soffa, M.L.: Complete removal of redundant expressions. SIGPLAN Not. 39(4) (April 2004)
Briggs, P., Cooper, K.D.: Effective Partial Redundancy Elimination. In: Conf. on Programming Language Design and Implementation (1994)
Coleman, S., McKinley, K.S.: Tile Size Selection Using Cache Organization and Data Layout. In: Conf. on Programming Language Design and Implementation (1995)
Ferrante, J., Ottenstein, K., Warren, J.: The program Dependence Graph and Its Use in Optimization. ACM Trans. on Programming Languages 9(3) (1987)
Jaramillo, C., Gupta, R., Soffa, M.L.: Comparison checking: An approach to avoid debugging of optimized code. In: Nierstrasz, O., Lemoine, M. (eds.) ESEC 1999 and ESEC-FSE 1999. LNCS, vol. 1687, p. 268. Springer, Heidelberg (1999)
Kulkarni, P., Hines, S., Hiser, J., Whalley, D., Davidson, J., Jones, D.: Fast Searches for Effective Optimization Phase Sequences. In: Conf. on Programming Language Design and Implementation (2004)
Kisuki, T., Knijnenburg, P.M.W., O’Boyle, M.F.P.: Combined Selection of Tile Size and Unroll Factors Using Iterative Compilation. In: Int’l. Conf. on Parallel Architectures and Compilation Techniques (2000)
Knuth, D.E., Bendix, P.B.: Simple word problems in universal algebras. In: Leech, J. (ed.) Computational problems in abstract algebra. Pergamon Press, Oxford (1970)
Kulkarni, P., Whalley, D.B., Tyson, G.S., Davidson, J.W.: Exhaustive Optimization Phase Order Space Exploration. In: Int’l. Symp. on Code Generation and Optimization (2006)
Kulkarni, P., Whalley, D.B., Tyson, G.S., Davidson, J.W.: Evaluating Heuristic Optimization Phase Order Search Algorithms. In: Int’l. Symp. on Code Generation and Optimization (2007)
Lacey, D.: Program Transformation using Temporal Logic Specifications. PhD dissertation, Univ. of Oxford (August 2003)
Lerner, S., Millstein, T., Chambers, C.: Automatically Proving the Correctness of compiler optimizations. In: Conf. on Programming Language Design and Implementation (2003)
Lacey, D., Jones, N., Wyk, E., Frederiksen, C.: Proving correctness of compiler optimizations by temporal logic. In: Symp. on Principles of Programming Languages (2002)
McKinley, K., Carr, S., Tseng, C.: Improving Data Locality with Loop Transformations. ACM Trans. on Programming Languages and Systems 18(4), 424–453 (1996)
Necula, G.C.: Translation validation for an optimizing compiler. In: Conf. on Programming Language Design and Implementation (2000)
Smith, M.D., Holloway, G.: An Introduction to Machine SUIF and Its Portable Libraries for Analysis and Optimization
Triantafyllis, S., Vachharajani, M., Vachharajani, N., August, D.I.: Compiler Optimization-space Exploration. In: Int’l. Symp. on Code Generation and Optimization (2003)
Triantafyllis, S., Vachharajani, M., August, D.I.: Compiler Optimization-space Exploration. Journal of Instruction-Level Parallelism (2005)
Whitfield, D., Soffa, M.L.: An Approach to Ordering optimizing transformations. In: Symp. on Principles and Practice of Parallel Programming (1990)
Whitfield, D., Soffa, M.L.: An Approach for Exploring Code Improving Transformations. ACM Trans. on Programming Languages and Systems 19(6), 1053–1084 (1997)
Yotov, K., Li, X., Ren, G., Cibulskis, M.: A Comparison of Empirical and Model-driven optimization. In: Conf. on Programming Language Design and Implementation (2003)
Zhao, M., Childers, B.R., Soffa, M.L.: A Model-based Framework: an Approach for Profit-driven Optimization. In: Int’l. Symp. on Code Generation and Optimization (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhao, M., Childers, B.R., Soffa, M.L. (2009). A Framework for Exploring Optimization Properties. In: de Moor, O., Schwartzbach, M.I. (eds) Compiler Construction. CC 2009. Lecture Notes in Computer Science, vol 5501. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00722-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-00722-4_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00721-7
Online ISBN: 978-3-642-00722-4
eBook Packages: Computer ScienceComputer Science (R0)