Optimistic Loop Optimization

Johannes Doerfert, Tobias Grosser, Sebastian Hack

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

Abstract

Compilers use static analyses to justify program optimizations. As every optimization must preserve the semantics of the original program, static analysis typically fall-back to conservative approximations. Consequently, the set of states for which the optimization is invalid is overapproximated and potential optimization opportunities are missed. Instead of justifying the optimization statically, a compiler can also synthesize preconditions that imply the correctness of the optimizations and are checked at the runtime of the program. In this paper, we present a framework to collect, generalize, and simplify assumptions based on Presburger arithmetic. We introduce different assumptions necessary to enable a variety of complex loop transformations and derive a (close to) minimal set of preconditions to validate them at runtime. Our evaluation shows that the runtime verification introduces negligible overhead and that the assumptions we propose almost always hold true. On a large benchmark set including SPEC and NPB our technique increases the number of modeled non-trivial loop nests by a factor of 3.9×.
Original languageEnglish
Title of host publicationProceedings of the 2017 International Symposium on Code Generation and Optimization
Place of PublicationPiscataway, NJ, USA
PublisherWiley-IEEE Computer Seciety Press
Pages292-304
Number of pages13
ISBN (Print)978-1-5090-4931-8
Publication statusPublished - 4 Feb 2017
EventInternational Symposium on Code Generation and Optimization (CGO) 2017 - Austin, Texas, United States
Duration: 4 Feb 20178 Feb 2017

Publication series

NameCGO
PublisherIEEE Press

Conference

ConferenceInternational Symposium on Code Generation and Optimization (CGO) 2017
CountryUnited States
CityAustin, Texas
Period4/02/178/02/17

Keywords

  • Polyhedral Model
  • Presburger Precondition
  • Program Versioning
  • Static Analysis

Fingerprint Dive into the research topics of 'Optimistic Loop Optimization'. Together they form a unique fingerprint.

Cite this