Exhaustive Phase Order Search Space Exploration and Evaluation

Опубликовано 6 сентября 2016, 16:17

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.