A graph-based iterative compiler pass selection and phase ordering approach
- 13 June 2016
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 51 (5), 21-30
- https://doi.org/10.1145/2980930.2907959
Abstract
Nowadays compilers include tens or hundreds of optimization passes, which makes it difficult to find sequences of optimizations that achieve compiled code more optimized than the one obtained using typical compiler options such as -O2 and -O3. The problem involves both the selection of the compiler passes to use and their ordering in the compilation pipeline. The improvement achieved by the use of custom phase orders for each function can be significant, and thus important to satisfy strict requirements such as the ones present in high-performance embedded computing systems. In this paper we present a new and fast iterative approach to the phase selection and ordering challenges resulting in compiled code with higher performance than the one achieved with the standard optimization levels of the LLVM compiler. The obtained performance improvements are comparable with the ones achieved by other iterative approaches while requiring considerably less time and resources. Our approach is based on sampling over a graph representing transitions between compiler passes. We performed a number of experiments targeting the LEON3 microarchitecture using the Clang/LLVM 3.7 compiler, considering 140 LLVM passes and a set of 42 representative signal and image processing C functions. An exhaustive cross-validation shows our new exploration method is able to achieve a geometric mean performance speedup of 1.28x over the best individually selected -OX flag when considering 100,000 iterations; versus geometric mean speedups from 1.16x to 1.25x obtained with state-of-the-art iterative methods not using the graph. From the set of exploration methods tested, our new method is the only one consistently finding compiler sequences that result in performance improvements when considering 100 or less exploration iterations. Specifically, it achieved geometric mean speedups of 1.08x and 1.16x for 10 and 100 iterations, respectively.Keywords
Funding Information
- Fundação para a Ciência e a Tecnologia (SFRH/BD/82606/2011)
- NORTE 2020 (NORTE-01-0145-FEDER-000020)
This publication has 18 references indexed in Scilit:
- Use of Previously Acquired Positioning of Optimizations for Phase Ordering ExplorationPublished by Association for Computing Machinery (ACM) ,2015
- Performance potential of optimization phase selection during dynamic JIT compilationACM SIGPLAN Notices, 2013
- Finding good optimization sequences covering program spaceACM Transactions on Architecture and Code Optimization, 2013
- Deconstructing iterative optimizationACM Transactions on Architecture and Code Optimization, 2012
- Milepost GCC: Machine Learning Enabled Self-tuning CompilerInternational Journal of Parallel Programming, 2011
- Improving both the performance benefits and speed of optimization phase sequence searchesACM SIGPLAN Notices, 2010
- Practical exhaustive optimization phase order exploration and evaluationACM Transactions on Architecture and Code Optimization, 2009
- Exploring the structure of the space of compilation sequences using randomized search algorithmsThe Journal of Supercomputing, 2006
- Finding effective compilation sequencesACM SIGPLAN Notices, 2004
- Fast searches for effective optimization phase sequencesACM SIGPLAN Notices, 2004