Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!mintaka!spdcc!ima!esegue!compilers-sender
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.compilers
Subject: Re: Aggressive optimization
Keywords: optimize, design
Message-ID: <1990Oct18.223231.22315@esegue.segue.boston.ma.us>
Date: 18 Oct 90 17:18:00 GMT
References: <1458@exodus.Eng.Sun.COM> <13405:Oct1800:22:5690@kramden.acf.nyu.edu> <2301@wn1.sci.kun.nl>
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Organization: IR
Lines: 55
Approved: compilers@esegue.segue.boston.ma.us

[Copied from comp.lang.misc -John]

In article <2301@wn1.sci.kun.nl> eerke@cs.kun.nl (Eerke Boiten) writes:
  [ after my description of the most general optimization technique ]
> A useful technique, indeed (called "strength reduction" in optimising
> compilers, "finite differencing" in transformational programming).

Huh? The strength reduction and finite differencing that CS majors learn
is absolutely trivial compared to what anyone can do by hand. As I said,
walking through an array is only the simplest example.

Does anyone have a compiler that can introduce a non-linear intermediate
expression and reduce around it? If so, I'm impressed. How advanced is
the symbolic algebra system included in the compiler? Can it take
advantage of range constraints, so that if it knows that x is between 0
and 7, it might set up a table to calculate ((1<<(x+2))-1)/10 quickly?
Can it manipulate floor and ceiling expressions? Can it introduce
invariants to figure out range constraints? These are all part of that
single, fundamental optimization technique.

I know, compilers are improving. Some optimizers fully automate the
dullest, most machine-dependent part of optimization---viz., figuring
out how often loops or branches are executed in practice, seeing how
long machine instructions take, and deciding on that basis whether a
given optimization is worthwhile. I really appreciate that. I won't stop
hand optimization because of it.

> >And I'm not going to introduce subtle bugs in weird cases with unsafe
> >program transformations.
> Tell me, what do you mean by unsafe program transformations? 
> Hand optimisations?

``Neither -O3 nor -O4 should be used when compiling either device
drivers, or programs that modify external variables from within signal
handlers.''

> Of course, finite differencing is relatively safe
> since you introduce redundant information most of the time.

It's exactly this attitude of ``finite differencing is the only
optimization in the world'' that leads people to think that hand
optimization is useless. Both the attitude and the conclusion are
wrong.

> By the way, there *are* systems that help you in
> applying source-level optimisations.

I'm perfectly willing to use whatever's out there. I'm not willing to
pretend that current compilers can figure out any reasonable level of
optimization for me.

---Dan
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue.  Meta-mail to compilers-request@esegue.