Recent compilers offer a vast number of multilayered optimizations targeting different code segments of an application. Choosing among these optimizations can significantly impact the performance of the code being optimized. The selection of the right set of compiler optimizations for a particular code segment is a very hard problem, but finding the best ordering of these optimizations adds further complexity. Finding the best ordering represents a long standing problem in compilation research, named the phase-ordering problem. The traditional approach of constructing compiler heuristics to solve this problem simply cannot cope with the enormous complexity of choosing the right ordering of optimizations for every code segment in an application. This article proposes an automatic optimization framework we call MiCOMP, which Mitigates the Compiler Phase-ordering problem. We perform phase ordering of the optimizations in LLVM's highest optimization level using optimization sub-sequences and machine learning. The idea is to cluster the optimization passes of LLVM's O3 setting into different clusters to predict the speedup of a complete sequence of all the optimization clusters instead of having to deal with the ordering of more than 60 different individual optimizations. The predictive model uses (1) dynamic features, (2) an encoded version of the compiler sequence, and (3) an exploration heuristic to tackle the problem. Experimental results using the LLVM compiler framework and the Cbench suite show the effectiveness of the proposed clustering and encoding techniques to application-based reordering of passes, while using a number of predictive models. We perform statistical analysis on the results and compare against (1) random iterative compilation, (2) standard optimization levels, and (3) two recent prediction approaches. We show that MiCOMP's iterative compilation using its sub-sequences can reach an average performance speedup of 1.31 (up to 1.51). Additionally, we demonstrate that MiCOMP's prediction model outperforms the -O1, -O2, and -O3 optimization levels within using just a few predictions and reduces the prediction error rate down to only 5%. Overall, it achieves 90% of the available speedup by exploring less than 0.001% of the optimization space. utoronto.ca; A. Bignoli, G. Palermo, and C. Silvano, DEIB, Via G. Ponzio 34/5, Milan, Italy; emails: andrea.bignoli@mail. polimi.it, {gianluca.palermo, cristina.silvano}@polimi.it; S. Kulkarni and J. Cavazos, EECIS, Newark, DE 19716, USA; emails: {sameer, cavazos}@udel.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.  Compiler developers design optimization passes to transform each code segment of a program to generate an optimized version of an application. Code segment can be a basic block, a function, a source file, or the whole program. The optimizations can be applied at different stages of the compilation process. Optimizing source code by hand is a tedious and long task; therefore, compiler optimizations are provided to automatically transform the code. However, code optimizations are dependent on programming language, application, and architecture. Additionally, the word optimization is a misnomer and there is no guarantee the transformed code will perform better than the original version. Aggressive optimizations might even degrade the performance of the code. Understanding the behavior of the optimizations, their actual effects on the source code, and the interaction of the optimizations to each other are complex modeling problems. The problem is particularly difficult because compiler developers have to deal with hundreds of different optimizations that can be applied during the different compilation phases and this generates the phase-ordering problem. The phase-ordering problem has been an open problem in the field of compiler research for many decades [32, 56] . The inability of researchers to solve the phaseordering problem has led to significant advances in the simpler problem of selecting the right set of optimizations, but even this problem has yet to be solved [8, 12, 15] . This process of selecting the right optimizations for each code segment is typically done manually, and the sequence of optimizations is constructed with little insight on the interaction between the preceding compiler optimizations in the sequence. Manually constructing heuristics to select the right sequence of compiler optimizations is infeasible given the ever growing number of compiler optimizations being integrated into compiler frameworks. As an example, GCC has more than 200 compiler passes, and LLVM's clang and LLVM's opt have more than 100 transformations. Additionally, these optimizations are applied at very different phases of the compilation, including analysis passes and loop-nest passes. Most optimization flags are turned off by default, and compiler developers rely on software developers to know which optimizations will benefit their code. Compiler developers provide standard optimization levels, e.g., -O1, -O2, -Os, to introduce a fixed sequence of compiler optimizations that, on average, can bring good performance on a set of benchmarks the compiler developers tested. Finding the best ordering of compiler optimizations can have substantial benefits for performance metrics such as execution time, power consumption, and code size. To this end, using predefined optimizations usually is not good enough to bring the best achievable application-specific performance. In this article, we propose the MiCOMP framework to mitigate the complexity of the phase-ordering problem. So far, there are two potential techniques we could use to predict good optimization orders for the code being optimized:
Iterative compilation has been proved an effective technique for tackling both the problems of choosing the right set of transformations and for ordering them to maximize their effectiveness REF .
MiCOMP: Mitigating the Compiler Phase-Ordering Problem Using Optimization Sub-Sequences and Machine Learning
TACO
Computer Science