Re: Counting Bits

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.

In one test I fed it approx 60 lines of code. It built a database
of 1.2 gigabytes, crunched for about 20 days, and bombed. This repeated
for quite a while. Someone eventually got it to work, and it really
did provide a pretty optimal solution. I have to wonder if people could
have done it in less than 4 months...


-j
--
"Blah Blah Blah"
___________________________________________________________________
Jamie Lawrence                                  <jamiel@sybase.com>

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.