Re: Optimization Question

[Toon Moene <toon at moene dot indiv dot nluug dot nl>]

Stephen L Moshier wrote:
> 
>   >        a=b*(c+d)  I
>   >
>   > versus
>   >        a=b*c+b*d  II
>   >
>   > The current snapshot doesn't recognize the equivalence and simply
>   > generates two fmuls and and a faddp for case II (only one fmuls
>   >for
>   > I).  Is this something that could be build into the optimization?
> 
> gcc does not currently have this capability.
> 
> Please, no!
> Floating point arithmetic does not obey  the associative law.
> This transformation should never be allowed, in any programming language.

Welcome to the Wondrous World of Fortran ;-)

To quote the draft F2K standard (but I'm sure this has been there for a
long long time):

<QUOTE>
7.1.8.3  Evaluation of numeric intrinsic operations

The rules given in 7.2.1 [sic, a forward reference - I hate that]
specify the interpretation of a numeric intrinsic operation [defines
precedence rules and order of evaluation at equal precedence].  Once the
interpretation has been established in accordance with those rules, the
processor [note the Fortranese: processor = compiler + run-time + CPU]
may evaluate any mathematically equivalent expression, provided that the
integrity of parentheses is not violated [note that !].

...

{Note 7.24}

...

Expression		Allowable alternative form
...
X * Y - X * Z		X * ( Y - Z )
...
Expression		Nonallowable alternative form
...
X * ( Y - Z )		X * Y - X * Z
{end note}

In addition to the parentheses required to establish the desired
interpretation, parentheses may be included to restrict the alternative
forms that may be used by the processor in the actual evaluation of the
expression.  This is useful for controlling the magnitude and accuracy
of intermediate values developed during the evaluation of an expression.
</QUOTE>

In Other Words:  If you, the programmer, write X * Y - X * Z instead of
(X * Y) - (X * Z), we, the compiler, may assume that you Don't Care.

This is one of the reasons why I get very nervous when people want to
compile IEEE-754 conformant _Fortran_ programs, because they need to be
language laywers too.  Not that many valid Fortran programs specify
IEEE-conformant computations (in the sense that they specify a unique
computation leading to a single correct result).

In fact, I wouldn't be surprised if it would be possible to prove a
stronger result - that the following is actually a Theorem:

Let VF(n) be the set of Valid Fortran programs of length n and VFIC(n)
the set of Valid Fortran programs specifying a IEEE-754 conformant
computation of length n.

Notation:  Card(S) is the cardinal number of set S.

Conjecture:

       Card(VFIC(n))
lim    ------------- = 0
n->oo   Card(VF(n))

[ I have found a marvelous proof of this; unfortunately, the margin
  of this mail is too small to contain it ]

-- 
Toon Moene (toon@moene.indiv.nluug.nl)
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Phone: +31 346 214290; Fax: +31 346 214286
GNU Fortran: http://world.std.com/~burley/g77.html