Practical Automatic Loop Specialization [abstract] (ACM DL, PDF) Taewook Oh, Hanjun Kim, Nick P. Johnson, Jae W. Lee, and David I. August Proceedings of the Eighteenth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), March 2013.
Program specialization optimizes a program with respect to known,
fixed inputs and other program invariants. 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 loops induced by the
input as concrete loops in the specialized binary. IPLS specializes
real-world 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 while increasing program size only by 7% when evaluated on
three script interpreters and eleven scripts each.
