Practical automatic loop specialization

Taewook Oh, Hanjun Kim, Nick P. Johnson, Jae W. Lee, David I. August

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

5 Scopus citations

Abstract

Program specialization optimizes a program with respect to program invariants, including known, fixed inputs. These invariants can be used to enable optimizations that are otherwise unsound. In many applications, a program input induces predictable patterns of values across loop iterations, yet existing specializers cannot fully capitalize on this opportunity. To address this limitation, we present Invariant-induced Pattern based Loop Specialization (IPLS), the first fully-automatic specialization technique designed for everyday use on real applications. Using dynamic information-flow tracking, IPLS profiles the values of instructions that depend solely on invariants and recognizes repeating patterns across multiple iterations of hot loops. IPLS then specializes these loops, using those patterns to predict values across a large window of loop iterations. This enables aggressive optimization of the loop; conceptually, this optimization reconstructs recurring patterns induced by the input as concrete loops in the specialized binary. IPLS specializes realworld programs that prior techniques fail to specialize without requiring hints from the user. Experiments demonstrate a geomean speedup of 14.1% with a maximum speedup of 138% over the original codes when evaluated on three script interpreters and eleven scripts each.

Original languageEnglish (US)
Title of host publicationASPLOS 2013 - 18th International Conference on Architectural Support for Programming Languages and Operating Systems
Pages419-430
Number of pages12
DOIs
StatePublished - Apr 5 2013
Externally publishedYes
Event18th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2013 - Houston, TX, United States
Duration: Mar 16 2013Mar 20 2013

Publication series

NameInternational Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS

Other

Other18th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2013
CountryUnited States
CityHouston, TX
Period3/16/133/20/13

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture

Keywords

  • Loop specialization
  • Partial evaluation
  • Profile based optimization
  • Program specialization

Fingerprint Dive into the research topics of 'Practical automatic loop specialization'. Together they form a unique fingerprint.

  • Cite this

    Oh, T., Kim, H., Johnson, N. P., Lee, J. W., & August, D. I. (2013). Practical automatic loop specialization. In ASPLOS 2013 - 18th International Conference on Architectural Support for Programming Languages and Operating Systems (pp. 419-430). (International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS). https://doi.org/10.1145/2451116.2451161