Compiler Optimization-Space Exploration

To meet the demands of modern architectures, optimizing compilers must incorporate an ever larger number of increas-ingly complex transformation algorithms. Since code transfor-mations may often degrade performance or interfere with sub-sequent transformations, compilers employ predictive heuris-tics 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 en-tirely. While this process results in a compiler capable of gen-erating good average code quality across the target benchmark set, it is at the cost of missed optimization opportunities in in-dividual code segments. To replace predictive heuristics, researchers have proposed compilers which explore many optimization options, select-ing the best one a posteriori. Unfortunately, these existing it-erative compilation techniques are not practical for reasons of compile time and applicability. In this paper, we present the Optimization-SpaceExploration (OSE) compiler organiza-tion, the first practical iterative compilation strategy applica-ble 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 num-ber 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 compile-time performance estimator. An OSE-enhanced version of Intel’s highly-tuned, aggressively optimizing production com-piler for IA-64 yields a significant performance improvement, more than 20 % in some cases, on Itanium for SPEC codes. 1.