Adaptive ordering of code transformations in an optimizing compiler

It has long been known that the quality of the code produced by an optimizing compiler is dependent upon the ordering of transformations applied to the code. In this dissertation, we show that the best orderings vary in unpredictable ways according to the properties of the input code and performance objectives, making adaptation a necessity to obtain the best results. We further demonstrate the most practical techniques to search the spaces of transformation orderings. Our analysis of six exhaustively enumerated subspaces of limited size determines the choice and parameters of search algorithms described and implemented in this work: random sampling, greedy methods, variations of the stochastic hillclimber, and genetic algorithms. We then apply the search algorithms to the full spaces of all available transformations, which are too big to enumerate. We evaluate the performance and cost of running these algorithms and discuss the tradeoffs between the quality of discovered orderings and an effort to find them. Stochastic hillclimbers discover effective orderings within approximately 500 evaluations. Compared to a fixed ordering of transformations, they result in 5%--40% improvements for a variety of input programs and performance objectives. To reduce the computational overhead in finding these orderings, we introduce and analyze a novel approach to precise static estimation of runtime frequencies of basic blocks. Termed "Estimated Virtual Execution", this approach reduces the search time by 40%--60%