Subject: Re: Comments on the "Report of the Numerics Working Group"

From: [email-masked]
Date: Thu, 10 Sep 1998 16:44:34 -0400

Joseph Darcy writes:

>>    Does the "associativefp" modifier relax the rules on the use of fused
>>    multiply accumulated? The rules described in the proposal are good
for
>>    "avoiding surprises", but they do disable some optimizations.

>  Do you have some particular optimization in mind?

Jose Moreire replies:

Yes. The proposal mentions common subexpression elimination for one. As
another example, consider the computation of the expression:

a*b + c*d + e*f + g*h

My understanding from the proposal is that, in default mode in PowerPC,
this needs to be evaluated as:

fmac(a,b,fmac(c,d,fmac(e,f,g*h)))

However, depending on my microarchitecture, I may want to evaluate it as:

fmac(a,b,c*d) + fmac(e,f,g*h)

This actually has more instructions, but schedules better in a pipeline.

Regarding the whole topic of algorithmic replacement, it may not be a
reality now, but we should be careful in denying Java of some future
development in compiler technology.

Joseph Darcy writes:
>>    interest, the following transformation is performed by current
Fortran
>>    compilers:
>>    the code
>>    do i = 1,n
>>       x[i] = float(i)
>>    end do
>>    is transformed to:
>>    xi = 0.0
>>    do i = 1,n
>>       xi = xi + 1.0
>>       x[i] = xi
>>    end do

>>    This is an important optimization, since it eliminates the need to
keep
>>    the "i" index and replaces a type conversion by an addition.

> As long as the compiler knows how big n is (and can act accordingly)
> this optimization can be performed in current Java.  For example, if n
> is less than 2^(number of significand bits in the format of x) than
> the transformation works fine.  However, if n is larger than this
> value, the "optimized" code will just keep assigning the same number
> to all subsequent array locations (adding 1.0 to xi will get rounded
> away).  In the original code, the large integers will be rounded when
> assigned to the array locations so the value of these locations can be
> larger than the value in previous locations (i.e. for large i, every
> other array location will be larger than the one before it, etc.).

Jose Moreira replies:

I don't see how the transformation above can be legal in current Java. In
the original case, each value of x[i] is subject to a single rounding
error. In the transformed code, the rounding errors accumulate. If this has
to do with the particulars of 1.0, then replace it by any other value that
can cause a problem (Pi for instance).

---

From: "Joseph D. Darcy" <[email-masked]>
Date: Thu, 10 Sep 1998 14:43:22 -0700 (PDT)

> fmac(a,b,fmac(c,d,fmac(e,f,g*h)))

Yes, that is the intended default semantics for fused mac.  In
general, the associativefp option needs tighter specifications (such
as nailing down the feature interactions you have pointed out) before
it can be implemented.

> development in compiler technology.

Compiler textbooks gravely warn that any optimization that changes the
computed answer is illegal.  Of course this conservatism is only true
in compiler textbooks.  However, I think there is a qualitative
difference between an optimization that restructures a programmer's
code and an optimization that basically ignores a programmer's code
and uses something else.  The programmer may be using an algorithm for
properties other than its speed and those other properties can easily
be broken if another algorithm is substituted.

> can cause a problem (Pi for instance).

Small integers are exactly representable as floating point numbers.
Therefore, 2.0 + 1.0 yields 3.0 exactly.  For the float format, this
holds until the integers get larger in magnitude than 16,777,216.  In
other words, for integer floats smaller in absolute value than 2^24,
adding 1.0 has no rounding error; the operation is exact.  Therefore,
until adding 1.0 does cause rounding errors, the transformed program
is functionally equivalent to the original.  So if the loop was
something like for(i=0; i<=100; i++){...} a Java compiler could
perform the transformation.

-Joe Darcy
[email-masked]