Basser Seminar Series

In Search of Near-Optimal Optimization Phase Orderings

David Whalley
Florida State University

TUESDAY, 21 February 2006, 4-5pm *NOTE CHANGE FROM USUAL TIME
Basser Conference Room (Madsen Building, Room G92)

Abstract

The phase-ordering problem is a long standing issue for compiler writers. Varying the order of applying optimization phases can produce different code with potentially significant performance variation between the best and worst performing instances. However, there is no universal optimization phase order that will produce the best code for all applications since the optimal order depends on the function being compiled, the compiler, and the architectural characteristics. Moreover, finding an optimal optimization phase sequence appears to be impractical as the attempted optimization phase space can be
huge for a even a single function.

A key insight to the phase ordering problem is that applying many different sequences of phases result in the same code being generated. In this presentation I will show that the actual optimization phase order space is not as large as earlier believed and can often be exhaustively enumerated for the optimization phases in our compiler. We analyze this space to capture probabilities regarding the relationships between phases and use these probabilities to significantly reduce the compilation time for a conventional compiler. We also analyze the performance of code generated by different phase orderings based on dynamic frequency measures of the function instances within the space, show that these dynamic frequency measures
correlate well to simulator processor cycle counts, and that the optimal ordering for the optimization phases in our compiler with respect to simulated measurements can often be determined in a short period of time. Finally, we apply the results or our analysis to study how adept a genetic algorithm is for finding optimal phase orderings within our compiler.

Speaker's biography

David Whalley received his PhD in CS from the University of Virginia in 1990. He is currently the E.P. Miles professor and chair of the Computer Science department at Florida State University. His research interests include low-level compiler optimizations, tools for supporting the development and maintenance of compilers, program performance evaluation tools, predicting execution time, computer architecture and embedded systems. Some of the techniques that he developed for new compiler optimizations and diagnostic tools are currently being applied in industrial and academic compilers. His research is currently supported by the National Science Foundation. More information about his background and research can be found on his home page, http://www.cs.fsu.edu/~whalley.