From: "Perry E. Metzger" <perry@imsi.com>
Date: Thu, 7 Jul 94 11:09:46 PDT
To: cypherpunks@toad.com
Subject: Superoptimizers
In-Reply-To: <9407071722.AA05853@ralph.sybgate.sybase.com>
Message-ID: <9407071809.AA04050@snark.imsi.com>
MIME-Version: 1.0
Content-Type: text/plain



The "superoptimizer" is an invention of Dr. Henry Massalin. Basically,
you take a real complete machine description at the register level (of
course they exist -- how do you think they do instruction set
simulations these days?) and exhaustively search for the shortest or
fastest (your pick) program that performs a given task. Henry invented
a number of smart tricks to speed up the search dramatically -- even
so, more than about a dozen or 15 instructions and you will find
yourself waiting an unacceptable period. However, for short sequences
that need to have the hell optimized out of them its great -- it does
wonders for inner loops in signal processing applications, for
example. It has some big limitations -- you can't do pointer stuff,
for example. However, its been of enormous help to Henry in real-world
problems.

I was under the impression that the technique was now well known (but
not widely implemented). I suppose I was wrong on that.

Henry's own implementations (all assembler and very fast) are
unavailable, but the FSF distributes something called "Gnu Superopt"
that performs a similar task -- since it does its work in C its a LOT
slower.


Jamie Lawrence says:
> At  4:47 PM 07/07/94 +0100, Graham Toal wrote:
> 
> >PS I dunno what superoptimisizer Perry is talking about but I've
> >never heard of a real one that works.  You have to feed in a complete
> >machine description at register transfer level and i don't know if
> >those exist for real machines; also the problem is almost certainly
> >exponential time for a *guaranteed* solution as Perry claims is
> >possible.
> 
> The only tool I have ever seen that created real results was a tool that
> caused more headaches than solutions. (Inside, proprietary tool, can't
> go into details) It only worked on its native platform  and one could
> feed it up to about 4K of code to analyse.