Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!van-bc!ubc-cs!uw-beaver!Teknowledge.COM!unix!garth!phipps
From: phipps@garth.UUCP (Clay Phipps)
Newsgroups: comp.lang.misc
Subject: Obscure Expr. Optimization (Re: Educating FORTRAN programmers to use C)
Message-ID: <3557@garth.UUCP>
Date: 20 Jan 90 04:33:58 GMT
References: <1016@sdrc.UUCP> <1990Jan6.003158.2039@aqdata.uucp> <1024@sdrc.UUCP> <167@metapyr.UUCP> <15078@bfmny0.UU.NET> <16717@duke.cs.duke.edu> <1298@wrgate.WR.TEK.COM>
Reply-To: phipps@garth.UUCP (Clay Phipps)
Organization: Intergraph APD, in semiarid Palo Alto, CA
Lines: 76

In article <1298@wrgate.WR.TEK.COM>,
daniels@teklds.WR.TEK.COM (Scott Daniels) wrote:
>
>The really impressive optimizations will probably come from some system 
>that allows properties of the resulting abstractions to be defined 
>(as in Goguen's work on attaching theories to views).  

Hmmm.  Would you cite a reference or two to this work ?  Please ?

>This work may eventually lead to a system 
>which can attain (on a user type) the fabled optimization 
>(which knocked out a benchmark on a FORTRAN compiler):
>
>  for i = 1,90
   ^^^
A very forgiving FORTRAN compiler, it appears.

>    V = V + sin( PI / i ) ** 2 + cos( PI / i ) ** 2
>became
>  V = V + 90.0
>
>since the compiler knew (heavens knows why) that 
>  sin(x)**2 + cos(x)**2 = 1.

I don't consider that optimization to be one that requires divine
intervention, nor even divine consultation.  The identity is only:

             +           = 1
          /     \
       **         **
      /  \       /  \
   sin    2   cos    2
    |          |
    x          x   

I am assuming that "sin" and "cos" are standard intrinsic functions.

They can be handled without new-fangled theory if expression optimization 
is done using a generalized approach intended *in advance* to make it easy 
to incorporate benchmarksmanship like the above in a reasonably safe manner,
whether on on a sudden request from Sales or Marketing (backed by VPs 
salivating over big bucks from a possible sale from competitive bids),
or on the whim of a compiler-writer trying to find some technical
entertainment on a dreary Monday morning.

In particular, the internal representation must make references to 
built-in intrinsic functions approximately as easy and reliable 
to recognize and process as standard arithmetic operators like "+".  
It must also make it easy to compare separate expressions for equality.
At a previous computer systems company, the automatically vectorizing 
compiler to which I was assigned satisfied the latter, but not the former 
(it wasn't even close).  As a consequence, Strength-Reduction was designed 
for that compiler to work only with identities among arithmetic, logical, 
and relational operators.

Some mechanism to alert the optimizer to being fed a benchmark would 
provide an opportunity to keep the overhead down for real programs.

Without a "benchmarksmanship" flag, 90 iterations seems like an awful lot 
to unroll, unless the loop unroller is very sensitive to the complexity 
of the body of the loop.

I was more intrigued that (((...(y + 1)...+ 1) + 1) + 1) summed to 90,
not 89.99999998, until I remembered that 1.0 is exactly representable.  
Maybe I'm too paranoid about floating-point summation.  
A native-mode compiler ought to produce the same sum from a program, 
regardless of whether the summing is done by the compiler optimizer, or 
by the compiled program.
-- 
[The foregoing may or may not represent the position, if any, of my employer, ]
[ who is identified solely to allow the reader to account for personal biases.]
                                              
Clay Phipps 
Intergraph APD: 2400#4 Geng Road, Palo Alto, CA 94303; 415/852-2327
UseNet: {apple,ingr,pyramid,sri-unix}!garth!phipps
EcoNet: cphipps