Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1009 > unrolled thread

Compiler optimization and floating point operations

Back to article view | Back to comp.compilers

Contents

  Compiler optimization and floating point operations Abid <abidmuslim@gmail.com> - 2013-10-23 13:47 -0700
    Re: Compiler optimization and floating point operations Cameron McInally <cameron.mcinally@nyu.edu> - 2013-10-23 22:55 -0400
    Re: Compiler optimization and floating point operations glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-10-24 02:56 +0000
    Re: Compiler optimization and floating point operations George Neuner <gneuner2@comcast.net> - 2013-10-24 07:41 -0400
      Re: Compiler optimization and floating point operations Jean-Marc Bourguet <jm@bourguet.org> - 2013-10-24 15:51 +0200
      Re: Compiler optimization and floating point operations "Steven G. Kargl" <sgk@troutmask.apl.washington.edu> - 2013-10-24 16:38 +0000
        Re: Compiler optimization and floating point operations christian.bau@cbau.wanadoo.co.uk - 2013-10-28 15:54 -0700
      Re: Compiler optimization and floating point operations George Neuner <gneuner2@comcast.net> - 2013-10-24 15:51 -0400
      Re: Compiler optimization and floating point operations glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-10-24 20:21 +0000
      Re: Compiler optimization and floating point operations christian.bau@cbau.wanadoo.co.uk - 2013-10-28 15:50 -0700
        Re: Compiler optimization and floating point operations Cameron McInally <cameron.mcinally@nyu.edu> - 2013-10-28 20:41 -0400

#1009 — Compiler optimization and floating point operations

Hi All:

Does back end compiler optimizations affect the floating point
accuracy? Is there any research work in this area?

Thanks,

Abid

[The answer to the first question is "sometimes", and there has been a
great deal of work in this area going back to the 1960s.  I know IBM
Fortran compilers that carefully preserve bit identical results in
regular and optimized code, and I know other compilers that freely
use all of the mathematical (but not arithmetic) equivalences that
Fortran allows. -John]

[toc] | [next] | [standalone]

#1010

Hey Abid,

On Wed, Oct 23, 2013 at 4:47 PM, Abid <abidmuslim@gmail.com> wrote:
> Does back end compiler optimizations affect the floating point
> accuracy?

Not all optimizations will affect floating point accuracy, but some
may. For example, an optimization that makes use of the associative
property or distributive property can have an impact. This is the
nature of the limited accuracy in floating point numbers.

Another common example is the use of FMA (Fused Multiply Add)
instructions. Although, using these instructions will most likely lead
to better accuracy, since there is only one rounding error applied to
the multiply and the add.

> Is there any research work in this area?

Yes, tons. Search for "floating point accuracy" and you will be sure
to find research going way back.

-Cameron

[toc] | [prev] | [next] | [standalone]

#1011

Abid <abidmuslim@gmail.com> wrote:

(snip)
> Does back end compiler optimizations affect the floating point
> accuracy? Is there any research work in this area?

As far as I know, the biggest cause of problems with optimization
is the extended precision of the registers in the Intel x87.

The original design of the 8087 was for a virtual stack that would
spill on overflow, and (what is the opposite of spill?) on underflow.

Not until the hardware was ready did anyone try to write the interrupt
routine to handle it, and it turned out not to be possible.  The
required state information was either not available, could not be
restored, or both.

Compilers could write temporary intermediates to memory in temporary
real format, but that is rare.

Next comes the complication of optimization. Common subexpression
elimination between statements, or in general keeping values in
registers, means that some values will retain extra precision, but you
(the programmer) don't know which ones. Even if you assign to a
variable and reload, the optimizer might keep it in a register.  (Many
compilers have an option to force the store, but that can slow things
down.)

I don't know about the research that might be done. The x87 has an
eight element stack. Research won't change that, though the use of SSE
avoids the problem (and advantage) of extended precision.

The technology for doing optimization is reasonably well understood.
Knowing which ones you should do it a different problem.

-- glen

[toc] | [prev] | [next] | [standalone]

#1012

On Wed, 23 Oct 2013 13:47:10 -0700 (PDT), Abid <abidmuslim@gmail.com>
wrote:

>Does back end compiler optimizations affect the floating point
>accuracy?

As John said, the answer is "sometimes".

FP hardware registers usually are wider than are the compiler's memory
storage formats (most often 32 and 64 bit IEEE).  The registers
typically carry a few to several extra bits of precision which are
lost when the value is stored to memory and then reloaded.

For maximum precision you want to keep intermediate values in
registers as much as possible, minimizing stores to and reloads from
memory.

For maximum consistency of results - across compiler modes or
different FPUs - you generally must do the opposite: aggressively
store and reload intermediate results before using them.  [On many
machines, clipping intermediate values can be done by moving them to
and from an integer register without actually going all the way to
memory. But however it is done, it slows the calculation.]

Floating point operations, in general, are not commutative: changing
the order of evaluation of sub-expressions can change the results.

Substitutions using mathematical equivalences can change the results
because floating point numbers are only an approximation of real
numbers - many real equivalences don't hold for FP math.

Using different FPUs may yield different results.  From the back end
POV this is important if there are multiple different hardware units
to choose from.  E.g., on the x86, the x87 FPU and the SIMD FPU have
different register widths and some corresponding instructions round
results differently.  It is safe to do unrelated calculations on
either unit, but you have to be extremely careful about using both to
work on different parts of the same calculation.


>Is there any research work in this area?

There has been quite a lot of work aimed at improving FP in the middle
(in the IR), but I'm not aware of any research specifically targeting
the back end.

George
[I think you mean they're not associative.  I don't know any situations
where a+b != b+a, but lots where a+(b+c) != (a+b)+c -John]

[toc] | [prev] | [next] | [standalone]

#1013

George Neuner <gneuner2@comcast.net> writes:

> [I think you mean they're not associative.  I don't know any situations
> where a+b != b+a, but lots where a+(b+c) != (a+b)+c -John]

You forgot about NaN ;-) (but I agree associative was probably intended).

Yours,
--
Jean-Marc
[How are NaNs not commutative? -John]

[toc] | [prev] | [next] | [standalone]

#1015

On Thu, 24 Oct 2013 15:51:59 +0200, Jean-Marc Bourguet wrote:

> George Neuner <gneuner2@comcast.net> writes:
>
>> [I think you mean they're not associative.  I don't know any situations
>> where a+b != b+a, but lots where a+(b+c) != (a+b)+c -John]
>
> You forgot about NaN ;-) (but I agree associative was probably intended).
>
> Yours,
> --
> Jean-Marc [How are NaNs not commutative? -John]

I believe Jean-Marc is referring to something like the following

#include <stdio.h>
int
main(void)
{
   float a, b;
   a = 0.;
   b = a / a;
   if (a + b != b + a) printf("fubar\n");
   return (0);
}

Can an optimizing compiler eliminate the if-statement?

--
steve
[If it does sufficient dataflow and constant substitutions so it can tell
that a+b will always be a NaN, I don't see why not. -John]

[toc] | [prev] | [next] | [standalone]

#1021

On Thursday, October 24, 2013 5:38:13 PM UTC+1, Steven G. Kargl wrote:
> #include <stdio.h>
> int
> main(void)
> {
>    float a, b;
>    a = 0.;
>    b = a / a;
>    if (a + b != b + a) printf("fubar\n");
>    return (0);
> }
>
> Can an optimizing compiler eliminate the if-statement?

It can eliminate the test because it will always be true (on IEEE
implementations where 0.0 / 0.0 is NaN).  It cannot eliminate the
if-statement because printf () should be called.

[toc] | [prev] | [next] | [standalone]

#1016

On Thu, 24 Oct 2013 07:41:12 -0400, George Neuner
<gneuner2@comcast.net> wrote:

>Floating point operations, in general, are not commutative: changing
>the order of evaluation of sub-expressions can change the results.

John replied:
>[I think you mean they're not associative.  I don't know any situations
>where a+b != b+a, but lots where a+(b+c) != (a+b)+c -John]

Yes, definitely "associative".  Thanks for the correction.
George

[toc] | [prev] | [next] | [standalone]

#1017

(snip, John wrote)

> [I think you mean they're not associative.  I don't know any
> situations where a+b != b+a, but lots where a+(b+c) != (a+b)+c -John]

I don't know of any with non-commutative addition, but there were
some Cray machines with non-commutative multiply.

For many Cray applications, getting a close answer fast is better
than the exact answer slow.

-- glen
[Oh, right. Can we safely assume that arithmetic model is dead? -John]

[toc] | [prev] | [next] | [standalone]

#1020

> [I think you mean they're not associative.  I don't know any situations
> where a+b != b+a, but lots where a+(b+c) != (a+b)+c -John]

Take fused multiply-add, and the expression a*b + c*d.
It can be evaluated either as fma (a, b, c*d) or fma (c, d, a*b).

It would seem natural that the code for a*b + c*d and for c*d + a*b
would be different, with different results.

[toc] | [prev] | [next] | [standalone]

#1022

On Mon, Oct 28, 2013 at 6:50 PM,  <christian.bau@cbau.wanadoo.co.uk> wrote:
>> [I think you mean they're not associative.  I don't know any situations
>> where a+b != b+a, but lots where a+(b+c) != (a+b)+c -John]
>
> Take fused multiply-add, and the expression a*b + c*d.
> It can be evaluated either as fma (a, b, c*d) or fma (c, d, a*b).
>
> It would seem natural that the code for a*b + c*d and for c*d + a*b
> would be different, with different results.

Right, that's called reassociation. The order of operations in the
expression tree has changed, so the finite precision rounding occurs
on different intermediate results. The same problem exists in some
floating point parallel reductions and such.

Most compilers will offer a directive, similar to FP_CONTRACT, for
such critical pieces of code. Some compilers [the good ones ;)] even
have flags to disable optimization passes that involve reassociation.

-Cameron

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web