Re: Any further work on superoptimizer?

On 2 Feb 92 16:26:08 GMT, hrubin@pop.stat.purdue.edu (Herman Rubin) said:
> If one has a program of even moderate size, the number of
> branches possible will undoubtedly exceed the size of the
> universe, and even with the fastest computing procedures
> consistent with current physics (NOT engineering), the
> analysis could never be completed.


certainly true. the superoptimizer is only applicable to small code
fragments. nobody claims otherwise.


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


nf fact, this is exactly the sort of thing the superoptimizer *is* capable
of, and that is one of the things that makes it very interesting. i think
another explanation of what it does is in order: the SO searches *all*
code sequences shorter than the input sequence. it returns the shortest
one it finds that has the same semantics as the input. how it prunes the
search tree, and how it checks the semantics quickly are what make it a
non-trivial program.


--
scott draves, spot@cs.cmu.edu
--

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