Re: Effectiveness of compilers today

jbuck@forney.berkeley.edu (Joe Buck) writes:


>The GNU superoptimizer uses exhaustive search. This means that its
>behavior is exponential.


>How fast its performance degrades as more instructions are required
>depends on how good its heuristics are, but you can't get away from the
>combinatorial explosion.


I'm no fan of exponential algorithms, but in defense of the superoptimizer
work, I'll point out that it is used at compiler-generation time, not at
compile time. Thus, it is possible to let it crunch away for a week
without impacting the eventual user.


It's similar to the idea of writing an exponential routine to search for
better ways to convert integer-multiply-by-a-constant to shifts, adds, and
subtracts. There are known routines that do a good job, but an optimal
translation requires exponential search. Therefore, build a searcher that
tries to beat your normal routine and let it run for a while (days, weeks,
...). Anytime it does a better job, write the result down and put it in a
hash table that you query before calling the normal routine.


Unfortunately, these things have somewhat limited applicability. You can
use them to find nice translations of particular idioms that programmers
_might_ use; but wouldn't it be nice to attack the code that the
programmer really did write (e.g., most programs multiply by 4 and 8, easy
cases; very few programs multiply by 123456789).


Preston Briggs
--

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