TY - GEN
T1 - Practical automatic loop specialization
AU - Oh, Taewook
AU - Kim, Hanjun
AU - Johnson, Nick P.
AU - Lee, Jae W.
AU - August, David I.
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
KW - Loop specialization
KW - Partial evaluation
KW - Profile based optimization
KW - Program specialization
UR - http://www.scopus.com/inward/record.url?scp=84875684265&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84875684265&partnerID=8YFLogxK
U2 - 10.1145/2451116.2451161
DO - 10.1145/2451116.2451161
M3 - Conference contribution
AN - SCOPUS:84875684265
SN - 9781450318709
T3 - International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS
SP - 419
EP - 430
BT - ASPLOS 2013 - 18th International Conference on Architectural Support for Programming Languages and Operating Systems
T2 - 18th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2013
Y2 - 16 March 2013 through 20 March 2013
ER -