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

preston@dawn.cs.rice.edu (Preston Briggs)
Fri, 19 Feb 1993 17:55:17 GMT

          From comp.compilers

Related articles
Effectiveness of compilers today andreasa@dhhalden.no (1993-02-14)
Superoptimizers (was Re: Effectiveness of compilers today) drw@zermelo.mit.edu (1993-02-18)
Re: Superoptimizers (was Re: Effectiveness of compilers today) preston@dawn.cs.rice.edu (1993-02-19)
Program Analysis (Was: Superoptimizers) tdarcos@access.digex.com (Paul Robinson) (1993-02-20)
Re: Superoptimizers (was Re: Effectiveness of compilers today) pardo@cs.washington.edu (1993-02-21)
| List of all articles for this month |

Newsgroups: comp.compilers
From: preston@dawn.cs.rice.edu (Preston Briggs)
Keywords: optimize
Organization: Rice University, Houston
References: 93-02-082 93-02-099
Date: Fri, 19 Feb 1993 17:55:17 GMT

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
--


Post a followup to this message

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