In search of near-optimal optimization phase orderings

ABSTRACT

Phase ordering is a long standing challenge for traditional optimizing compilers. Varying the order of applying optimization phases to a program can produce different code, with potentially significant performance variation amongst them. A key insight to addressing the phase ordering problem is that many different optimization sequences produce the same code. In an earlier study, we used this observation to restate the phase ordering problem to concentrate on finding all distinct function instances that can be produced due to different phase orderings, instead of attempting to generate code for all possible optimization sequences. Using a novel search algorithm we were able to show that it is possible to exhaustively enumerate the set of all possible function instances that can be produced by different phase orderings in our compiler for most of the functions in our benchmark suite [1]. Finding the optimal function instance within this set for almost any dynamic measure of performance still appears impractical since that would involve execution/simulation of all generated function instances. To find the dynamically optimal function instance we exploit the observation that the enumeration space for a function typically contains a very small number of distinct control flow paths. We simulate only one function instance from each group of function instances having the identical control flow, and use that information to estimate the dynamic performance of the remaining functions in that group. We further show that the estimated dynamic frequency counts obtained by using our method correlate extremely well to simulated processor cycle counts. Thus, by using our measure of dynamic frequencies to identify a small number of the best performing function instances we can often find the optimal phase ordering for a function within a reasonable amount of time. Finally, we perform a case study to evaluate how adept our genetic algorithm is for finding optimal phase orderings within our compiler, and demonstrate how the algorithm can be improved.

REFERENCES

• 1: Prasad A. Kulkarni , David B. Whalley , Gary S. Tyson , Jack W. Davidson, Exhaustive Optimization Phase Order Space Exploration, Proceedings of the International Symposium on Code Generation and Optimization, p.306-318, March 26-29, 2006 [doi>10.1109/CGO.2006.15]
• 2: Steven R. Vegdahl, Phase coupling and constant generation in an optimizing microcode compiler, Proceedings of the 15th annual workshop on Microprogramming, p.125-133, October 05-07, 1982, Palo Alto, California, United States
• 3: D. Whitfield , M. L. Soffa, An approach to ordering optimizing transformations, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.137-146, March 14-16, 1990, Seattle, Washington, United States
• 4: Keith D. Cooper , Philip J. Schielke , Devika Subramanian, Optimizing for reduced code space using genetic algorithms, Proceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems, p.1-9, May 05-05, 1999, Atlanta, Georgia, United States
• 5: Prasad Kulkarni , Wankang Zhao , Hwashin Moon , Kyunghwan Cho , David Whalley , Jack Davidson , Mark Bailey , Yunheung Paek , Kyle Gallivan, Finding effective optimization phase sequences, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 6: T. Kisuki , P. M. W. Knijnenburg , M. F. P. O'Boyle, Combined Selection of Tile Sizes and Unroll Factors Using Iterative Compilation, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.237, October 15-19, 2000
• 7: Spyridon Triantafyllis , Manish Vachharajani , Neil Vachharajani , David I. August, Compiler optimization-space exploration, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 8: Prasad Kulkarni , Stephen Hines , Jason Hiser , David Whalley , Jack Davidson , Douglas Jones, Fast searches for effective optimization phase sequences, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 9: Deborah L. Whitfield , Mary Lou Soffa, An approach for exploring code improving transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.1053-1084, Nov. 1997 [doi>10.1145/267959.267960]
• 10: Min Zhao , Bruce R. Childers , Mary Lou Soffa, A Model-Based Framework: An Approach for Profit-Driven Optimization, Proceedings of the international symposium on Code generation and optimization, p.317-327, March 20-23, 2005 [doi>10.1109/CGO.2005.2]
• 11: L. Almagor , Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steven W. Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, Finding effective compilation sequences, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
• 12: F. Bodin, T. Kisuki, P.M.W. Knijnenburg, M.F.P. O'Boyle, , and E. Rohou. Iterative compilation in a non-linear optimisation space. Proc. Workshop on Profile and Feedback Directed Compilation. Organized in conjuction with PACT'98, 1998.
• 13: Prasad A. Kulkarni , Stephen R. Hines , David B. Whalley , Jason D. Hiser , Jack W. Davidson , Douglas L. Jones, Fast and efficient searches for effective optimization-phase sequences, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.2, p.165-198, June 2005 [doi>10.1145/1071604.1071607]
• 14: Toru Kisuki , Peter M. W. Knijnenburg , Michael F. P. O'Boyle , François Bodin , Harry A. G. Wijshoff, A Feasibility Study in Iterative Compilation, Proceedings of the Second International Symposium on High Performance Computing, p.121-132, May 26-28, 1999
• 15: Elana D. Granston and Anne Holler. Automatic recommendation of compiler options. 4th Workshop of Feedback-Directed and Dynamic Optimization, December 2001.
• 16: K. Chow and Y. Wu. Feedback-directed selection and characterization of compiler optimizatons. Proc. 2nd Workshop on Feedback Directed Optimization, 1999.
• 17: M. Haneda , P. M. W. Knijnenburg , H. A. G. Wijshoff, Generating new general compiler optimization settings, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088171]
• 18: P.M.W. Knijnenburg, T. Kisuki, K. Gallivan, and M.F.P. O'Boyle. The effect of cache models on iterative compilation for combined tiling and unrolling. In Proc. FDDO-3, pages 31--40, 2000.
• 19: Tim A. Wagner , Vance Maverick , Susan L. Graham , Michael A. Harrison, Accurate static estimators for program optimization, ACM SIGPLAN Notices, v.29 n.6, p.85-96, June 1994
• 20: Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steven Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, ACME: adaptive compilation made efficient, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 21: M. E. Benitez , J. W. Davidson, A portable global optimizer and linker, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.329-338, June 20-24, 1988, Atlanta, Georgia, United States
• 22: Doug Burger , Todd M. Austin, The SimpleScalar tool set, version 2.0, ACM SIGARCH Computer Architecture News, v.25 n.3, p.13-25, June 1997 [doi>10.1145/268806.268810]
• 23: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop on, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 24: W. Peterson and D. Brown. Cyclic codes for error detection. In Proceedings of the IRE, volume 49, pages 228--235, January 1961.
• 25: Jack W. Davidson and David B. Whalley. A design environment for addressing architecture and compiler interactions. Microprocessors and Microsystems, 15(9):459--472, November 1991.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

General Terms:
Algorithms, Measurement, Performance

Keywords:
exhaustive search, genetic algorithms, phase ordering