Fast and Effective Solutions to the Phase Ordering Problem

The phase ordering problem has been a long-standing problem in compiler optimizations. Different orderings of applying optimization phases by a compiler can result in different code generated, with potentially significant performance differences for many applications or even functions within applications. At the same time it is universally acknowledged that a single ordering of optimization phases will not produce the best code for all functions. The strict performance constraints in applications for embedded and high performance systems is making it increasingly important to quickly find the optimal or near-optimal order of applying optimization phases so that efficient code can be produced. Given the huge search space of all possible orderings of optimization phases, finding the optimal phase ordering for each function was generally considered intractable. Furthermore, heuristic approaches to address the phase ordering problem frequently take too long to converge on a good solution. In this dissertation I will first describe two complimentary approaches to achieve faster searches for effective optimization sequences when using a genetic algorithm. We then further leverage our observation of huge redundancies in the typical phase order space to make exhaustive evaluation of the entire phase order space practical in most cases. We also analyze various properties of the optimization phase order space, and show how such analysis can be used to generate faster conventional compilers, and enhance commonly employed heuristic approaches to produce better solutions faster.