Compiler Optimization-Space Exploration [abstract] (IEEE Xplore, PDF)
Spyridon Triantafyllis, Manish Vachharajani, Neil Vachharajani, and David I. August
Proceedings of the 2003 International Symposium on Code
Generation and Optimization (CGO), March 2003.
Winner Best Paper Award.
To meet the demands of modern architectures, optimizing
compilers must incorporate an ever larger number of increasingly
complex transformation algorithms. Since code transformations may
often degrade performance or interfere with subsequent
transformations, compilers employ predictive heuristics to guide
optimizations by predicting their effects a
priori. Unfortunately, the unpredictability of optimization
interaction and the irregularity of today's wide-issue machines
severely limit the accuracy of these heuristics. As a result, compiler
writers may temper high variance optimizations with overly
conservative heuristics or may exclude these optimizations
entirely. While this process results in a compiler capable of
generating good average code quality across the target benchmark set,
it is at the cost of missed optimization opportunities in individual
code segments. To replace predictive heuristics, researchers have
proposed compilers which explore many optimization options, selecting
the best one a posteriori. Unfortunately, these existing
iterative compilation techniques are not practical for reasons of
compile time and applicability. In this paper, we present the Optimization-Space Exploration (OSE)
compiler organization, the first practical iterative compilation
strategy applicable to optimizations in general-purpose
compilers. Instead of replacing predictive heuristics, OSE uses the
compiler writer's knowledge encoded in the heuristics to select a
small number of promising optimization alternatives for a given code
segment. Compile time is limited by evaluating only these alternatives
for hot code segments using a general compiletime performance
estimator. An OSE-enhanced version of Intel's highly-tuned,
aggressively optimizing production compiler for IA-64 yields a
significant performance improvement, more than 20% in some cases, on
Itanium for SPEC codes.