Prasad A. Kulkarni
Jack W. Davidson
Skip Abstract Section
Abstract
Choosing the most appropriate optimization phase ordering has been a long-standing problem in compiler optimizations. Exhaustive evaluation of all possible orderings of optimization phases for each function is generally dismissed as infeasible for production-quality compilers targeting accepted benchmarks. In this article, we show that it is possible to exhaustively evaluate the optimization phase order space for each function in a reasonable amount of time for most of the functions in our benchmark suite. To achieve this goal, we used various techniques to significantly prune the optimization phase order search space so that it can be inexpensively enumerated in most cases and reduce the number of program simulations required to evaluate program performance for each distinct phase ordering. The techniques described are applicable to other compilers in which it is desirable to find the best phase ordering for most functions in a reasonable amount of time. We also describe some interesting properties of the optimization phase order space, which will prove useful for further studies of related problems in compilers.
- Agakov, F., Bonilla, E., Cavazos, J., Franke, B., Fursin, G., O'Boyle, M. F. P., Thomson, J., Toussaint, M., and Williams, C. K. I. 2006. Using machine learning to focus iterative optimization. In Proceedings of the International Symposium on Code Generation and Optimization (CGO'06). IEEE, Los Alamitos, CA, 295--305. Google Scholar
Digital Library
- Almagor, L., Cooper, K. D., Grosul, A., Harvey, T. J., Reeves, S. W., Subramanian, D., Torczon, L., and Waterman, T. 2004. Finding effective compilation sequences. In Proceedings of the ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES '04). ACM, New York, 231--239. Google ScholarDigital Library
- Barr, M. and Massa, A. 2006. Programming Embedded Systems: With C and GNU Development Tools 2nd, Ed. O'Reilly Media, Inc, Sebastopol, CA. Google ScholarDigital Library
- Benitez, M. E. and Davidson, J. W. 1988. A portable global optimizer and linker. In Proceedings of the SIGPLAN'88 Conference on Programming Language Design and Implementation. ACM, New York, 329--338. Google ScholarDigital Library
- Bodin, F., Kisuki, T., Knijnenburg, P., O'Boyle, M., and Rohou, E. 1998. Iterative compilation in a non-linear optimisation space. In Proceedings of the Workshop on Profile and Feedback Directed Compilation.Google Scholar
- Burger, D. and Austin, T. M. 1997. The SimpleScalar tool set, version 2.0. SIGARCH Comput. Archit. News 25, 3, 13--25. Google ScholarDigital Library
- Cavazos, J. and O'Boyle, M. F. P. 2006. Method-specific dynamic compilation using logistic regression. In Proceedings of the 21st Annual ACM SIGPLAN Conference on Object-oriented Programming Systems, Languages, and Applications (OOPSLA'06). ACM, New York, 229--240. Google ScholarDigital Library
- Cooper, K., Grosul, A., Harvey, T., Reeves, S., Subramanian, D., Torczon, L., and Waterman, T. 2005. ACME: Adaptive compilation made efficient. In Proceedings of the ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES'05). ACM, New York, 69--78. Google ScholarDigital Library
- Cooper, K. D., Schielke, P. J., and Subramanian, D. 1999. Optimizing for reduced code space using genetic algorithms. In Proceedings of the Workshop on Languages, Compilers, and Tools for Embedded Systems. ACM, New York, 1--9. Google ScholarDigital Library
- Davidson, J. W. and Whalley, D. B. 1991. A design environment for addressing architecture and compiler interactions. Microproces. Microsyst. 15, 9, 459--472.Google ScholarCross Ref
- Engblom, J. 2007. Using simulation tools for embedded systems software development. http://www.embedded.com/columns/technicalinsights/199501500?_requestid=111267.Google Scholar
- Guthaus, M. R., Ringenberg, J. S., Ernst, D., Austin, T. M., Mudge, T., and Brown, R. B. 2001. MiBench: A free, commercially representative embedded benchmark suite. In Proceedings of the IEEE 4th Annual Workshop on Workload Characterization. IEEE, Los Alamitos, CA. Google ScholarDigital Library
- Hewlett-Packard. 2000. Parallel programming guide for hp-ux systems. http://docs.hp.com/en/B3909-90003/B3909-90003.pdf (page 74).Google Scholar
- Hoste, K. and khout, L. E. 2008. Cole: compiler optimization level exploration. In Proceedings of the 6th Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO'08). ACM, New York, 165--174. Google ScholarDigital Library
- Kisuki, T., Knijnenburg, P., and O'Boyle, M. 2000. Combined selection of tile sizes and unroll factors using iterative compilation. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques. IEEE, Los Alamitos, CA, 237--246. Google ScholarDigital Library
- Kisuki, T., Knijnenburg, P., O'Boyle, M., Bodin, F., and Wijshoff, H. 1999. A feasibility study in iterative compilation. In Proceedings of the 8th International Symposium of High-Performance Computing. IEEE, Los Alamitos, CA, 121--132. Google ScholarDigital Library
- Knijnenburg, P., Kisuki, T., Gallivan, K., and O'Boyle, M. 2000. The effect of cache models on iterative compilation for combined tiling and unrolling. In Proceedings of 3rd ACM Workshop on Feedback-Directed and Dynamic Optimization. ACM, New York, 31--40.Google Scholar
- Kulkarni, P., Hines, S., Hiser, J., Whalley, D., Davidson, J., and Jones, D. 2004. Fast searches for effective optimization phase sequences. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York, 171--182. Google ScholarDigital Library
- Kulkarni, P., Whalley, D., Tyson, G., and Davidson, J. 2006a. Exhaustive optimization phase order space exploration. In Proceedings of the 4th Annual IEEE/ACM International Symposium on Code Generation and Optimization. IEEE, Los Alamitos, CA, 306--318. Google ScholarDigital Library
- Kulkarni, P., Whalley, D., Tyson, G., and Davidson, J. 2006b. In search of near-optimal optimization phase orderings. In Proceedings of the ACM SIGPLAN/SIGBED Conference on Language, Compilers and Tool Support for Embedded Systems (LCTES '06). ACM, New York, 83--92. Google ScholarDigital Library
- Kulkarni, P., Whalley, D., Tyson, G., and Davidson, J. 2007. Evaluating heuristic optimization phase order search algorithms. In Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization. IEEE, Los Alamitos, CA. Google ScholarDigital Library
- Kulkarni, P., Zhao, W., Moon, H., Cho, K., Whalley, D., Davidson, J., Bailey, M., Paek, Y., and Gallivan, K. 2003. Finding effective optimization phase sequences. In Proceedings of the ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES '03). ACM, New York, 12--23. Google ScholarDigital Library
- Kulkarni, P. A., Hines, S. R., Whalley, D. B., Hiser, J. D., Davidson, J. W., and Jones, D. L. 2005. Fast and efficient searches for effective optimization-phase sequences. ACM Trans. Archit. Code Optimiz. 2, 2, 165--198. Google ScholarDigital Library
- Peterson, W. and Brown, D. 1961. Cyclic codes for error detection. In Proceedings of the Institute of Radio Engineers. 49, 228--235.Google Scholar
- Redhat. 2004. Gnupro 04r1 tools for embedded systems development. http://www.redhat.com/f/pdf/GNUPro-04r1-Embedded-AnnouncementLetter.pdf.Google Scholar
- Touati, S.-A.-A. and Barthou, D. 2006. On the decidability of phase ordering problem in optimizing compilation. In Proceedings of the 3rd Conference on Computing Frontiers (CF'06). ACM, New York, 147--156. Google ScholarDigital Library
- Triantafyllis, S., Vachharajani, M., Vachharajani, N., and August, D. I. 2003. Compiler optimization-space exploration. In Proceedings of the International Symposium on Code Generation and Optimization. IEEE, Los Alamitos, CA, 204--215. Google ScholarDigital Library
- Vegdahl, S. R. 1982. Phase coupling and constant generation in an optimizing microcode compiler. In Proceedings of the 15th Annual Workshop on Microprogramming. IEEE, Los Alamitos, CA, 125--133. Google ScholarDigital Library
- Virtutech. 2008. Virtualized software development white paper. http://www.virtutech.com/files/whitepapers/wp_simics.pdf.Google Scholar
- Wagner, T. A., Maverick, V., Graham, S. L., and Harrison, M. A. 1994. Accurate static estimators for program optimization. SIGPLAN Notices 29, 6, 85--96. Google ScholarDigital Library
- Weisstein, E. W. 2006. Correlation coefficient. from MathWorld—A Wolfram Web Resource. http://mathworld.wolfram.com/CorrelationCoefficient.html.Google Scholar
- Whitfield, D. L. and Soffa, M. L. 1990. An approach to ordering optimizing transformations. In Proceedings of the 2nd ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming. ACM, New York, 137--146. Google ScholarDigital Library
- Whitfield, D. L. and Soffa, M. L. 1997. An approach for exploring code improving transformations. ACM Trans. Program. Lang. Syst. 19, 6, 1053--1084. Google ScholarDigital Library
- Zhao, M., Childers, B., and Soffa, M. L. 2003. Predicting the impact of optimizations for embedded systems. In Proceedings of the ACM SIGPLAN Conference on Language, Compiler, and Tool for Embedded Systems (LCTES '03). ACM, New York, 1--11. Google ScholarDigital Library
- Zhao, M., Childers, B., and Soffa, M. L. 2005. A model-based framework: An approach for profit-driven optimization. In Proceedings of the International Symposium on Code Generation and Optimization. IEEE, Los Alamitos, CA, 317--327. Google ScholarDigital Library
Index Terms
- Practical exhaustive optimization phase order exploration and evaluation
Recommendations
Exhaustive Optimization Phase Order Space Exploration
CGO '06: Proceedings of the International Symposium on Code Generation and OptimizationThe phase-ordering problem is a long standing issue for compiler writers. Most optimizing compilers typically have numerous different code-improving phases, many of which can be applied in any order. These phases interact by enabling or disabling ...
Exploiting phase inter-dependencies for faster iterative compiler optimization phase order searches
CASES '13: Proceedings of the 2013 International Conference on Compilers, Architectures and Synthesis for Embedded SystemsThe problem of finding the most effective set and ordering of optimization phases to generate the best quality code is a fundamental issue in compiler optimization research. Unfortunately, the exorbitantly large phase order search spaces in current ...
Analyzing and addressing false interactions during compiler optimization phase ordering
Compiler optimization phase ordering is a fundamental, pervasive, and long-standing problem for optimizing compilers. This problem is caused by interacting optimization phases producing different codes when applied in different orders. Producing the ...
Comments