Compiler optimization-space exploration

S. Triantafyllis, M. Vachharajani, N. Vachharajani, David I. August

Research output: Chapter in Book/Report/Conference proceedingConference contribution

115 Citations (Scopus)

Abstract

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. 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 compile-time 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.

Original languageEnglish (US)
Title of host publicationInternational Symposium on Code Generation and Optimization, CGO 2003
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages204-215
Number of pages12
ISBN (Electronic)076951913X, 9780769519135
DOIs
StatePublished - Jan 1 2003
EventInternational Symposium on Code Generation and Optimization, CGO 2003 - San Francisco, United States
Duration: Mar 23 2003Mar 26 2003

Publication series

NameInternational Symposium on Code Generation and Optimization, CGO 2003

Other

OtherInternational Symposium on Code Generation and Optimization, CGO 2003
CountryUnited States
CitySan Francisco
Period3/23/033/26/03

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture

Cite this

Triantafyllis, S., Vachharajani, M., Vachharajani, N., & August, D. I. (2003). Compiler optimization-space exploration. In International Symposium on Code Generation and Optimization, CGO 2003 (pp. 204-215). [1191546] (International Symposium on Code Generation and Optimization, CGO 2003). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CGO.2003.1191546
Triantafyllis, S. ; Vachharajani, M. ; Vachharajani, N. ; August, David I. / Compiler optimization-space exploration. International Symposium on Code Generation and Optimization, CGO 2003. Institute of Electrical and Electronics Engineers Inc., 2003. pp. 204-215 (International Symposium on Code Generation and Optimization, CGO 2003).
@inproceedings{e7589276796e4e368feb516391122ace,
title = "Compiler optimization-space exploration",
abstract = "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. 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 compile-time 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.",
author = "S. Triantafyllis and M. Vachharajani and N. Vachharajani and August, {David I.}",
year = "2003",
month = "1",
day = "1",
doi = "https://doi.org/10.1109/CGO.2003.1191546",
language = "English (US)",
series = "International Symposium on Code Generation and Optimization, CGO 2003",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "204--215",
booktitle = "International Symposium on Code Generation and Optimization, CGO 2003",
address = "United States",

}

Triantafyllis, S, Vachharajani, M, Vachharajani, N & August, DI 2003, Compiler optimization-space exploration. in International Symposium on Code Generation and Optimization, CGO 2003., 1191546, International Symposium on Code Generation and Optimization, CGO 2003, Institute of Electrical and Electronics Engineers Inc., pp. 204-215, International Symposium on Code Generation and Optimization, CGO 2003, San Francisco, United States, 3/23/03. https://doi.org/10.1109/CGO.2003.1191546

Compiler optimization-space exploration. / Triantafyllis, S.; Vachharajani, M.; Vachharajani, N.; August, David I.

International Symposium on Code Generation and Optimization, CGO 2003. Institute of Electrical and Electronics Engineers Inc., 2003. p. 204-215 1191546 (International Symposium on Code Generation and Optimization, CGO 2003).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Compiler optimization-space exploration

AU - Triantafyllis, S.

AU - Vachharajani, M.

AU - Vachharajani, N.

AU - August, David I.

PY - 2003/1/1

Y1 - 2003/1/1

N2 - 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. 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 compile-time 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.

AB - 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. 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 compile-time 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.

UR - http://www.scopus.com/inward/record.url?scp=67650534864&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67650534864&partnerID=8YFLogxK

U2 - https://doi.org/10.1109/CGO.2003.1191546

DO - https://doi.org/10.1109/CGO.2003.1191546

M3 - Conference contribution

T3 - International Symposium on Code Generation and Optimization, CGO 2003

SP - 204

EP - 215

BT - International Symposium on Code Generation and Optimization, CGO 2003

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Triantafyllis S, Vachharajani M, Vachharajani N, August DI. Compiler optimization-space exploration. In International Symposium on Code Generation and Optimization, CGO 2003. Institute of Electrical and Electronics Engineers Inc. 2003. p. 204-215. 1191546. (International Symposium on Code Generation and Optimization, CGO 2003). https://doi.org/10.1109/CGO.2003.1191546