Re: Effectiveness of compilers today

preston@dawn.cs.rice.edu (Preston Briggs)
Thu, 18 Feb 1993 04:15:03 GMT

          From comp.compilers

Related articles
[2 earlier articles]
Effectiveness of compilers today kanze@us-es.sel.de (1993-02-17)
Re: Effectiveness of compilers today jpab+@andrew.cmu.edu (Josh N. Pritikin) (1993-02-17)
Re: Effectiveness of compilers today burley@apple-gunkies.gnu.ai.mit.edu (1993-02-17)
Re: Effectiveness of compilers today jbuck@forney.berkeley.edu (1993-02-17)
Re: Effectiveness of compilers today napi@cs.indiana.edu (mohd hanafiah abdullah) (1993-02-17)
Re: Effectiveness of compilers today moss@cs.cmu.edu (1993-02-18)
Re: Effectiveness of compilers today preston@dawn.cs.rice.edu (1993-02-18)
Re: Effectiveness of compilers today roth@helena.cs.rice.edu (1993-02-18)
Superoptimizers (was Re: Effectiveness of compilers today) drw@zermelo.mit.edu (1993-02-18)
Re: Effectiveness of compilers today pardo@cs.washington.edu (1993-02-19)
Re: Effectiveness of compilers today kjb@cgl.citri.edu.au (1993-02-19)
Re: Effectiveness of compilers today kanze@us-es.sel.de (1993-02-20)
Re: Effectiveness of compilers today tchannon@black.demon.co.uk (1993-02-19)
[4 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: preston@dawn.cs.rice.edu (Preston Briggs)
Keywords: optimize
Organization: Rice University, Houston
References: 93-02-082 93-02-091
Date: Thu, 18 Feb 1993 04:15:03 GMT

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


Post a followup to this message

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