Automatically constructing compiler optimization heuristics using supervised learning

Optimizing compilers use heuristics to control different aspects of compilation and to construct approximate solutions to hard compiler problems. Finding a heuristic that is effective for a broad range of applications is time-consuming and one of the most difficult tasks faced by compiler writers. In this dissertation, I introduce a new methodology called LOCO (Learning for Optimizing COmpilers) for constructing compiler heuristics automatically. In the context of Java JIT compilation, the efficiency of an optimization algorithm is important because time spent optimizing a program is part of the total running time of that program. We apply LOCO to construct new compiler heuristics that improve the efficiency of two classical compiler optimizations: instruction scheduling and register allocation. Instruction scheduling is one of the most effective compiler optimization algorithms, sometimes improving program speed by 10% or more—but it can also be expensive. We found that instruction scheduling often does not produce significant benefit and sometimes degrades speed. Using LOCO, we induced heuristics to predict which blocks benefit from scheduling. These “filters” choose whether or not to schedule each block. Using filters, we can dramatically reduce scheduling effort while only slightly degrading the benefit of scheduling. Like instruction scheduling, register allocation is an important and expensive optimization. However, unlike instruction scheduling, register allocation is a mandatory phase of compilation. We use LOCO to construct a “hybrid” register allocator, that controls the application of two different register allocation algorithms. One algorithm is expensive, but sometimes more effective. The other is more efficient, but sometimes less effective. A hybrid allocator chooses which algorithm to apply for each method. Using hybrid allocators we can dramatically reduce register allocation effort while still obtaining much of the additional benefit of the more expensive algorithm