phipps@garth.UUCP (Clay Phipps) (01/20/90)
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