Improving compiler optimizations using machine learning
Date
2014
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
The number of optimizations that are available in modern day compilers are in their hundreds, and would only grow in number in the future. This increase in the number of optimizations available to the compiler is primarily due to the fact that each optimization would try and target specific code constructs and increase their efficiency by applying specific templates. As the optimizations target increasingly specific code constructs, increasing number of optimizations that are being applied to a specific code may have never been intended for the code that is presently being compiled. At present all compilers apply a given set of optimizations blindly to all the code being compiled by the compiler, with the assumption that the optimization would either increase the performance of the code or make no changes. This assumption would mean that either the optimizations are not aggressive enough to reach their full potential for fear of having unintended consequences, or mean that in certain cases even degrade code performance. Knowing which optimizations to apply from the hundreds available in modern day compilers becomes difficult and important at the same time. Our research in improving compiler optimization planning aims to solve this impasse.
Selective application of the optimizations from the vast number of available optimizations to the compilers is the key to increasing performance of the code being compiled. This selective application of the optimizations either involves extensive human involvement that would be (and probably already is) too complex and unsustainable or involve the use of intelligence embedded in the compiler itself. Performance improvement achieved using compiler optimizations without any input from an application developer provides this crucial boost to the application with no recurring associated cost. Another advantage of such techniques is that it can provide performance improvement over and above an already optimized code design.
The process of providing the compiler with such intelligence is the primary focus of this dissertation. The optimization plan of the compiler can be primarily divided into three different logical parts, Optimization Selection , Optimization Ordering , and Optimization Tuning ; we would present our research and specific solutions to improving all three of these steps involved in optimization planning. Optimization Selection is the processing of selecting the beneficial optimizations from a given set of optimizations. We present an optimization selection solution on the widely used GCC compiler used to compile a financial library. The financial library is used by one of the largest commercial financial firms to model their risk exposure, and the computational needs of this financial library are a significant chunk of the total computation needs of the firm. We achieve a speedup of 2% to 4% compared to the baseline, which could (if implemented) directly impact their extremely large annual computational budget.
Optimization Ordering is the process of arranging the order in which a set of optimizations are applied to a given piece of code. The application of multiple optimizations modify and transform the codes that they are applied to, and thus indirectly interact with each other, some of the optimizations are clean up optimizations and others could be enabling optimizations for another set of optimizations. Such interdependence of optimizations makes it more and more difficult to understand intuitively the right order to apply these optimizations, and generates the need for a method to generate good optimization orderings . This problem is usually referred to as phase ordering, and has been considered to be a difficult problem to solve in the past. In this dissertation we show that using source feature analysis in combination with machine learning algorithms can provide us with a robust heuristic in solving phase ordering. We use the Jikes RVM (Jikes Research Virtual Machine developed by IBM) to present our results and achieve a 4% to 8% improvement in the final performance of a given set of benchmarks.
Finally Optimization Tuning is the process of tuning a single optimization to improve its efficacy. The example of optimization tuning that we study in this dissertation is method inlining, We use the Java HotSpot Virtual Machine (the most commonly used Java VM developed by Sun Microsystems and now actively developed and maintained by Oracle) and Maxine VM (A Java Research VM developed by Oracle) to present our results in improving the performance of method inlining, and achieve a 10% to 14% improvement in performance. We also show an interesting twist to presenting the final machine learning heuristic in the form of a decision tree, and discuss the advantages of using this over an artificial neural network.