Practical Exhaustive Optimization Phase Order Exploration and Evaluation

Title: Practical Exhaustive Optimization Phase Order Exploration and Evaluation

Prasad Kulkarni, David Whalley, Gary Tyson, and Jack Davidson

Abstract:

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 paper we show that it is possible to exhaustively evaluate the optimization phase order space in our compiler back end for each function on the ARM-Linux platform in a reasonable amount of time for most of the functions in our benchmark suite. To achieve this goal we used various techniques to significantly prune the optimization phase order search space so that it can be inexpensively enumerated in most cases, and to reduce the number of program simulations required to evaluate program performance for each distinct phase ordering. The techniques described are applicable to other compilers in which it is desirable to find the best phase ordering for most functions in a reasonable amount of time. We also describe some interesting properties of the optimization phase order space, which will prove useful for further studies in related problems in compilers.

Compiler Used:

We used the VPO compiler backend for these experiments. The version of the VPO compiler backend used can be downloaded via this link: Download VPO Backend

Benchmarks:

We used benchmarks from the MiBench benchmark suite. All benchmark files that are input to the VPO compiler backend are available here. These files are generated by the compiler frontend, which is based on EDG and cannot be open-sourced. The source code for the MiBench benchmarks themselves can be downloaded via the link here

Raw Tests Data:

We are releasing the raw data gathered by our experiments described in this paper so that it can be analyzed by other researchers as well. The data is in a compressed format. The link for the directory structure for downloading the data is here. Although the files are not encoded, in a strict sense of the word, you may need some basic information regarding how we represent the data in order to interpret the data. Some basic information to interpret the data files is available here.

We hope that providing this information will help other researchers working on the phase ordering problem better understand the optimization phase order space. We hope that this will spawn additional research, and help compilers improve the quality of their generated codes. Please get in touch with us to explore collaboration opportunities or if you need help with any of this information.

Back to home page.