LCS Publication Details
Publication Title: Meta Optimization: Improving Compiler Heuristics with Machine Learning
Publication Author: Stephenson, Mark
Additional Authors: Saman Amarasinghe, Martin Martin, Una-May O'Reilly
LCS Document Number: MIT-LCS-TM-634
Publication Date: 12-3-2002
LCS Group: Computer Architecture
Additional URL:
Compiler writers have crafted many heuristics over the years to (approximately) solve NP-hard problems efficiently. Finding a heuristic that performs well on a broad range of applications is a tedious and difficult process. This paper introduces Meta Optimization, a methodology for automatically fine-tuning compiler heuristics. Meta Optimization uses machine-learning techniques to automatically search an optimization's solution space. We implemented Meta Optimization on top of Trimaran to test its efficacy. By `evolving' Trimaran's hyperblock selection optimization for a particular benchmark, our system achieves impressive speedups. Application-specific heuristics obtain an average speedup of 23% (up to 43%) for the applications in our suite. Furthermore, by evolving a compiler's heuristic over several benchmarks, we can create effective, general-purpose compilers. The best general-purpose heuristic our system found improved Trimaran's hyperblock selection algorithm by an average of 25% on our training set, and 9% on a completely unrelated test set. We further test the applicability of our system on Trimaran's priority-based coloring register allocator. For this well-studied optimization we were able to specialize the compiler for individual applications, achieving an average speedup of 6%.
To obtain this publication:

To purchase a printed copy of this publication please contact MIT Document Services.