Re: Any further work on superoptimizer?

In article 92-01-117 Dave Jones writes:
> I don't remember if it was the same paper, but at about that time I read
> an article about a "superoptimizer" that supposedly tried every possible
> code sequence shorter than the original, and with a semantic analyzer
> decided which if any effectively did the same thing. It would often come
> up with surprising sequences using the XOR trick and other obscurities.
> However, using no computer help, I coded up sequences that beat two of his
> "superoptimized" ones. I sent the code-fragments to the author, but never
> received a reply.


I'd be curious what they were. The superoptimizer had a somewhat restricted
instruction set to work with, which you may have exceeded, but if you didn't,
it's a bug. It's supposed to find *the* best way (although its metric may
have been instructions, not cycles). For example, branches were excluded.


The usual technique was to assemble the test code into memory, run it with
a short test vector, then a longer one, then try to prove the boolean
function computed equal to the desired one. In fact, you can run without
this last step (do it manually) if you pick your test vectors properly.


In article 92-02-010 Herman Rubin writes:
> But there is a much greater problem. It is not only necessary to consider
> rearrangements of code, but even totally different algorithms. I do not
> see how a superoptimizer just looking at the code could replace the usual
> multiplication scheme with any of the faster alternatives.


The superoptimizer tries all possible ways. Its job is to compute a
function. This bars it from computing approximations (weighting accuracy
vs. cost tradeoffs is not in its mandate) and random functions (it takes
a statistician to judge how random a random sequnce is).


One of the problems that was thrown at the superoptimizer was binary to
decimal conversion, as well as BCD to binary. It did division by 10 by
multiplying by .1 in 2-adic notation (see Knuth v.2), but the author had
been hoping for something better.
--
-Colin
--

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