Re: Superoptimizers (was Re: Effectiveness of compilers today)

drw@zermelo.mit.edu (Dale R. Worley) writes:


>I've wondered if it's possible to have a program grovel the ASTs of a
>bunch of programs and extract out "common" combinations of operations that
>should be candidates for superoptimizer investigation.


One approach (which I associate with Davidson and Fraser) is to have the
compiler log exceptions (i.e., opportunities!) when it comes across them.


Consider my multiply example. We've got some general method that does
pretty well and an exception table that we use to record cases where the
general method is known to be less than optimal (presumably we've
investigated all the integers up to some k, say 1000). Anytime a number n
comes along that is bigger than k, we check the exception table. If
present, we emit the translation. If not present, we use our general
method and log the fact that some interesting new number has come along.
Run all your favorite code through the compiler (say, all the SPECmark
programs), then sic the exponential search on any numbers that show up in
the log. If you find an improvement, add it to the exception table.


I'd don't really like the multiply example (kind of small potatoes), but
other more interesting examples are possible. Davidson and Fraser used a
similar approach several years ago to build a peephole optimizer.


    title="Automatic Generation of Peephole Optimizations",
    author="Jack W. Davidson and Christopher W. Fraser",
    journal=sigplan,
    year=1984,
    month=jun,
    volume=19,
    number=6,
    note=pldi84,
    pages="111--116"


They use a slow but complete peephole optimizer at compile-generation time
to find patterns in a training set of programs. The patterns are then
used to build a fast peephole optimizer for production use.


Preston Briggs
--

Return to the comp.compilers page.
Search the comp.compilers archives again.