Finding effective compilation sequences

ABSTRACT

Most modern compilers operate by applying a fixed, program-independent sequence of optimizations to all programs. Compiler writers choose a single "compilation sequence", or perhaps a couple of compilation sequences. In choosing a sequence, they may consider performance of benchmarks or other important codes. These sequences are intended as general-purpose tools, accessible through command-line flags such as -O2 and -O3.Specific compilation sequences make a significant difference in the quality of the generated code, whether compiling for speed, for space, or for other metrics. A single universal compilation sequence does not produce the best results over all programs [8, 10, 29, 32]. Finding an optimal program-specific compilation sequence is difficult because the space of potential sequences is huge and the interactions between optimizations are poorly understood. Moreover, there is no systematic exploration of the costs and benefits of searching for good (i.e., within a certain percentage of optimal) program-specific compilation sequences.In this paper, we perform a large experimental study of the space of compilation sequences over a set of known benchmarks, using our prototype adaptive compiler. Our goal is to characterize these spaces and to determine if it is cost-effective to construct custom compilation sequences. We report on five exhaustive enumerations which demonstrate that 80% of the local minima in the space are within 5 to 10% of the optimal solution. We describe three algorithms tailored to search such spaces and report on experiments that use these algorithms to find good compilation sequences. These experiments suggest that properties observed in the enumerations hold for larger search spaces and larger programs. Our findings indicate that for the cost of 200 to 4,550 compilations, we can find custom sequences that are 15 to 25% better than the human-designed fixed-sequence originally used in our compiler.

REFERENCES

• 1: B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
• 2: Shumeet Baluja , Scott Davies, Fast probabilistic modeling for combinatorial optimization, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.469-476, July 1998, Madison, Wisconsin, United States
• 3: D. Bernstein , M. Golumbic , y. Mansour , R. Pinter , D. Goldin , H. Krawczyk , I. Nahshon, Spill code minimization techniques for optimizing compliers, ACM SIGPLAN Notices, v.24 n.7, p.258-263, July 1989
• 4: Preston Briggs , Keith D. Cooper, Effective partial redundancy elimination, ACM SIGPLAN Notices, v.29 n.6, p.159-170, June 1994
• 5: Preston Briggs , Keith D. Cooper , L. Taylor Simpson, Value numbering, Software—Practice & Experience, v.27 n.6, p.701-724, June 1997 [doi>10.1002/(SICI)1097-024X(199706)27:6<701::AID-SPE104>3.3.CO;2-S]
• 6: G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins, and P. W. Markstein. Register allocation via graph coloring. Computer Languages, 6(1):47--57, Jan. 1981.
• 7: K. Chow and Y. Wu. Feedback-directed selection and characterization of compiler optimizations. In Proceedings of the 4th Workshop on Feedback-Directed and Dynamic Optimization (FDDO-4), Dec. 2001.
• 8: 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
• 9: Keith D. Cooper , L. Taylor Simpson , Christopher A. Vick, Operator strength reduction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.5, p.603-625, September 2001 [doi>10.1145/504709.504710]
• 10: Keith D. Cooper , Devika Subramanian , Linda Torczon, Adaptive Optimizing Compilers for the 21st Century, The Journal of Supercomputing, v.23 n.1, p.7-22, August 2002 [doi>10.1023/A:1015729001611]
• 11: K. D. Cooper and L. Torczon. Engineering a Compiler. Morgan-Kaufmann Publishers, 2003.
• 12: K. D. Cooper and T. Waterman. Investigating adaptive compilation using the MIPSPro compiler. In Proceedings of the 2003 Los Alamos Computer Science Institute Symposium. Los Alamos Computer Science Institute (LACSI), Oct. 2003.
• 13: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 14: Jack W. Davidson , Christopher W. Fraser, The Design and Application of a Retargetable Peephole Optimizer, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.191-202, April 1980 [doi>10.1145/357094.357098]
• 15: George E. Forsythe , Michael A. Malcolm , Cleve B. Moler, Computer Methods for Mathematical Computations, Prentice Hall Professional Technical Reference, 1977
• 16: Matteo Frigo, A fast Fourier transform compiler, ACM SIGPLAN Notices, v.34 n.5, p.169-180, May 1999
• 17: M. Frigo and S. G. Johnson. FFTW: An adaptive software architecture for the FFT. In Proceedings of the 1998 ICASSP Conference, volume 3, pages 1381--1384, 1998.
• 18: E. D. Granston and A. Holler. Automatic recommendation of compiler options. In Proceedings of the 4th Workshop on Feedback-Directed and Dynamic Optimization (FDDO-4), Dec. 2001.
• 19: L. Johnsson. Private communication. Discussion regarding algorithm choice in the Thinking Machine numerical libraries., Oct. 2003.
• 20: 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
• 21: T. Kisuki, P. M. Knijnenburg, M. F. O'Boyle, and H. Wijsho. Iterative compilation in program optimization. In Proceedings of 8th Workshop on Compilers for Parallel Computers, CPC 2000, pages 35--44, Jan. 2000.
• 22: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, ACM SIGPLAN Notices, v.27 n.7, p.224-234, July 1992
• 23: 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
• 24: Gabriel Marin , John Mellor-Crummey, Cross-architecture performance predictions for scientific applications using parameterized models, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 25: Dragan Mirkovic, Automatic Performance Tuning in the UHFFT Library, Proceedings of the International Conference on Computational Sciences-Part I, p.71-80, May 28-30, 2001
• 26: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• 27: B. Selman and S. Kirkpatrick. Critical behavior in the computational cost of satisfiability testing. Artificial Intelligence, 81(1-2):273--295, 1996.
• 28: Loren Taylor Simpson , Keith D. Cooper, Value-driven redundancy elimination, 1996
• 29: 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
• 30: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]
• 31: R. C. Whaley, A. Petitet, and J. J. Dongarra. Automated empirical optimization of software and the ATLAS project. Parallel Computing, 27(1--2):3--25, 2001.
• 32: 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]
• 33: Min Zhao , Bruce Childers , Mary Lou Soffa, Predicting the impact of optimizations for embedded systems, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Experimentation, Languages, Performance

Keywords:
adaptive compilers, learning models