Exhaustive Phase Order Search Space Exploration and Evaluation

April 18, 2007
Prasad A. Kulkarni | Florida State University

Choosing the most appropriate optimization phase ordering has been a long standing problem in compiler optimizations. For most applications or functions different orders of applying optimization phases by a compiler typically result in different code generated, with potentially significant performance differences. At the same time it is universally acknowledged that a single ordering of optimization phases will not produce the best code for all functions or applications.

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 talk, I will explain the various techniques we used to: (1) significantly prune the optimization phase order search space so that it can be inexpensively enumerated in most cases, and (2) to reduce the number of program simulations required to evaluate program performance for each distinct phase ordering. These techniques made it possible to exhaustively evaluate the optimization phase order space in our compiler backend for each function in a reasonable amount of time for most of the functions in our benchmark suite. Later analysis of the phase order space revealed some interesting properties, which we used to improve our default compilation sequence.

Speaker Details

Prasad A. Kulkarni is currently a Ph.D. candidate in the Computer Science department at Florida State University. He received his M.S. degree in computer science from Florida State University in 2003. His research interests include static and dynamic compilation techniques, iterative compilation, and computer architecture. For his Ph.D. dissertation, he has explored various techniques to address the phase ordering problem in static optimizing compilers. He was awarded the prestigious IBM fellowship, in part for his success in this work. During his internship at IBM T.J. Watson research center, he investigated performance related issues in dynamic compilation systems for single and multi-processor architectures.