Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Fariborz Jahanian]

[-- Attachment #1.1: Type: text/plain, Size: 2267 bytes --]

>
> In the following code the repeated multiplication is folded into a 
> single operation (multiplication by Infinity),
> when compiled for apple-ppc-darwin target.
> For different values of "x" this leads to undeserved or absent 
> floating point exceptions, and breaks some of
> the elementary math functions in Libm. Occurs at optimization O1 and 
> higher.
>
> /* test */
> static const double C = 0x1.0p1023;
>
> double foo(double x)
> {
>         return ( ( (x * C) * C ) * C );
> }
>
> This is done in routine: simplify_rhs_and_lookup_avail_expr(...) which 
> is preceded with this comment:
>
>  /* If we have z = (x OP C1), see if we earlier had x = y OP C2.
>      If OP is associative, create and fold (y OP C2) OP C1 which
>      should result in (y OP C3), use that as the RHS for the
>      assignment.  Add minus to this, as we handle it specially below.  
> */
>
> But in:
>
>  Section 5.1.2.3 Program execution of the Programming languages — C  
> standard we read:
>
> 13 EXAMPLE 5 Rearrangement for floating-point expressions is often 
> restricted because of limitations in precision as well as range. The 
> implementation cannot generally apply the mathematical associative 
> rules for addition or multiplication, nor the distributive rule, 
> because of roundoff error, eveninthe absence of overflowand underflow. 
>  Likewise, implementations cannot generally replace decimal constants 
> in order to rearrange expressions. Inthe following fragment, 
> rearrangements suggested by mathematical rules for real numbers are 
> often not valid (see F.8).
> double x, y, z;
> /*... */
> x=(x*y)*z;
> //not equivalent to
> x*=y*z;
>
> Any comments from math. experts on this alias is appreciated.
>
> - Thanks, fariborz (fjahanian@apple.com)


Here is the patch. It has been bootstrapped, dejagnu tested on 
apple-ppc-darwin.

OK for fsf mainline?

- thanks, fariborz (fjahanian@apple.com)

ChangeLog:

2004-10-05  Fariborz Jahanian <fjahanian@apple.com>

         * tree-ssa-dom.c (associative_fp_binop): New function.
         (simplify_rhs_and_lookup_avail_expr): Disallow associativity
         and constant folding of floating point MULT_EXPR/PLUS_EXPR
         expressions.


[-- Attachment #1.2: Type: text/enriched, Size: 2303 bytes --]

<excerpt>

In the following code the repeated multiplication is folded into a
single operation (multiplication by Infinity),

when compiled for apple-ppc-darwin target.

For different values of "x" this leads to undeserved or absent
floating point exceptions, and breaks some of

the elementary math functions in Libm. Occurs at optimization O1 and
higher. 


/* test */

static const double C = 0x1.0p1023;


double foo(double x)

{

        return ( ( (x * C) * C ) * C );

}


This is done in routine:
<color><param>FFF8,18B7,27D1</param>simplify_rhs_and_lookup_avail_expr(...)</color>
which is preceded with this comment:


 /* If we have z = (x OP C1), see if we earlier had x = y OP C2.

     If OP is associative, create and fold (y OP C2) OP C1 which

     should result in (y OP C3), use that as the RHS for the

     assignment.  Add minus to this, as we handle it specially below. 
*/


But in:


 Section 5.1.2.3 Program execution of the Programming languages — C 
standard we read:


13 EXAMPLE 5 Rearrangement for floating-point expressions is often
restricted because of limitations in precision as well as range. The
implementation cannot generally apply the mathematical associative
rules for addition or multiplication, nor the distributive rule,
because of roundoff error, eveninthe absence of overflowand underflow. 
Likewise, implementations cannot generally replace decimal constants
in order to rearrange expressions. Inthe following fragment,
rearrangements suggested by mathematical rules for real numbers are
often not valid (see F.8). 

double x, y, z; 

/*... */ 

x=(x*y)*z;

//not equivalent to

x*=y*z; 


Any comments from math. experts on this alias is appreciated.


- Thanks, fariborz (fjahanian@apple.com)

</excerpt>


Here is the patch. It has been bootstrapped, dejagnu tested on
apple-ppc-darwin.


OK for fsf mainline?


- thanks, fariborz (fjahanian@apple.com)


ChangeLog:


2004-10-05  Fariborz Jahanian <<fjahanian@apple.com>


        * tree-ssa-dom.c (associative_fp_binop): New function.

        (simplify_rhs_and_lookup_avail_expr): Disallow associativity

        and constant folding of floating point MULT_EXPR/PLUS_EXPR 

        expressions.



[-- Attachment #2: fsf-patch-tree-ssa-dom.txt --]
[-- Type: text/plain, Size: 2039 bytes --]

Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dom.c,v
retrieving revision 2.56
diff -c -p -r2.56 tree-ssa-dom.c
*** tree-ssa-dom.c	29 Sep 2004 02:50:46 -0000	2.56
--- tree-ssa-dom.c	5 Oct 2004 16:53:05 -0000
*************** static void restore_currdefs_to_original
*** 266,271 ****
--- 266,272 ----
  static void register_definitions_for_stmt (tree);
  static edge single_incoming_edge_ignoring_loop_edges (basic_block);
  static void restore_nonzero_vars_to_original_value (void);
+ static inline bool associative_fp_binop (tree);
  
  /* Local version of fold that doesn't introduce cruft.  */
  
*************** record_equality (tree x, tree y)
*** 1547,1552 ****
--- 1548,1563 ----
    record_const_or_copy_1 (x, y, prev_x);
  }
  
+ /* return true, if it is ok to do folding of an associative expression */ 
+ static inline bool
+ associative_fp_binop (tree exp)
+ {
+   enum tree_code code = TREE_CODE (exp);
+   return !(!flag_unsafe_math_optimizations
+            && (code == MULT_EXPR || code == PLUS_EXPR)
+            && FLOAT_TYPE_P (TREE_TYPE (exp)));
+ }
+ 
  /* STMT is a MODIFY_EXPR for which we were unable to find RHS in the
     hash tables.  Try to simplify the RHS using whatever equivalences
     we may have recorded.
*************** simplify_rhs_and_lookup_avail_expr (stru
*** 1606,1612 ****
  	  tree rhs_def_rhs = TREE_OPERAND (rhs_def_stmt, 1);
  	  enum tree_code rhs_def_code = TREE_CODE (rhs_def_rhs);
  
! 	  if (rhs_code == rhs_def_code
  	      || (rhs_code == PLUS_EXPR && rhs_def_code == MINUS_EXPR)
  	      || (rhs_code == MINUS_EXPR && rhs_def_code == PLUS_EXPR))
  	    {
--- 1617,1623 ----
  	  tree rhs_def_rhs = TREE_OPERAND (rhs_def_stmt, 1);
  	  enum tree_code rhs_def_code = TREE_CODE (rhs_def_rhs);
  
! 	  if ((rhs_code == rhs_def_code && associative_fp_binop (rhs))
  	      || (rhs_code == PLUS_EXPR && rhs_def_code == MINUS_EXPR)
  	      || (rhs_code == MINUS_EXPR && rhs_def_code == PLUS_EXPR))
  	    {

[-- Attachment #3.1: Type: text/plain, Size: 2 bytes --]




[-- Attachment #3.2: Type: text/enriched, Size: 3 bytes --]

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Geoffrey Keating]

Fariborz Jahanian <fjahanian@apple.com> writes:

> OK for fsf mainline?

No, not OK.

> - thanks, fariborz (fjahanian@apple.com)
> 
> ChangeLog:
> 
> 2004-10-05 Fariborz Jahanian <fjahanian@apple.com>
> 
>         * tree-ssa-dom.c (associative_fp_binop): New function.
>         (simplify_rhs_and_lookup_avail_expr): Disallow associativity
>         and constant folding of floating point MULT_EXPR/PLUS_EXPR
>         expressions.
> 
> 
> Index: tree-ssa-dom.c
> ===================================================================
> RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dom.c,v
> retrieving revision 2.56
> diff -c -p -r2.56 tree-ssa-dom.c
> *** tree-ssa-dom.c	29 Sep 2004 02:50:46 -0000	2.56
> --- tree-ssa-dom.c	5 Oct 2004 16:53:05 -0000
> *************** static void restore_currdefs_to_original
> *** 266,271 ****
> --- 266,272 ----
>   static void register_definitions_for_stmt (tree);
>   static edge single_incoming_edge_ignoring_loop_edges (basic_block);
>   static void restore_nonzero_vars_to_original_value (void);
> + static inline bool associative_fp_binop (tree);
>   
>   /* Local version of fold that doesn't introduce cruft.  */
>   
> *************** record_equality (tree x, tree y)
> *** 1547,1552 ****
> --- 1548,1563 ----
>     record_const_or_copy_1 (x, y, prev_x);
>   }
>   
> + /* return true, if it is ok to do folding of an associative expression */ 
> + static inline bool
> + associative_fp_binop (tree exp)
> + {
> +   enum tree_code code = TREE_CODE (exp);
> +   return !(!flag_unsafe_math_optimizations

This flag is not clearly the right one.  Why did you pick it from the
alternatives?

> +            && (code == MULT_EXPR || code == PLUS_EXPR)
> +            && FLOAT_TYPE_P (TREE_TYPE (exp)));

This function appears to disallow folding

(x * 2.0) * 2.0

into

x * 4.0

which seems to me to be valid.

Please provide a testcase as part of the patch in proper dejagnu format.

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Andrew Pinski]

On Oct 5, 2004, at 3:52 PM, Geoffrey Keating wrote:

> Fariborz Jahanian <fjahanian@apple.com> writes:
>
>> OK for fsf mainline?
>
> No, not OK.
>
>> - thanks, fariborz (fjahanian@apple.com)
>>
>> ChangeLog:
>>
>> 2004-10-05 Fariborz Jahanian <fjahanian@apple.com>
>>
>>         * tree-ssa-dom.c (associative_fp_binop): New function.
>>         (simplify_rhs_and_lookup_avail_expr): Disallow associativity
>>         and constant folding of floating point MULT_EXPR/PLUS_EXPR
>>         expressions.


>> +   enum tree_code code = TREE_CODE (exp);
>> +   return !(!flag_unsafe_math_optimizations
>
> This flag is not clearly the right one.  Why did you pick it from the
> alternatives?

Why is this not right flag, it is used other places which we do the same
thing.

>> +            && (code == MULT_EXPR || code == PLUS_EXPR)
>> +            && FLOAT_TYPE_P (TREE_TYPE (exp)));
>
> This function appears to disallow folding
>
> (x * 2.0) * 2.0
>
> into
>
> x * 4.0
>
> which seems to me to be valid.

Also this is a valid transformation only if the constants will generate
a power of 2.

-- Pinski

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Fariborz Jahanian]

On Oct 5, 2004, at 12:52 PM, Geoffrey Keating wrote:

> Fariborz Jahanian <fjahanian@apple.com> writes:
>
>> OK for fsf mainline?
>
> No, not OK.
>
>> - thanks, fariborz (fjahanian@apple.com)
>>
>> ChangeLog:
>>
>> 2004-10-05 Fariborz Jahanian <fjahanian@apple.com>
>>
>>         * tree-ssa-dom.c (associative_fp_binop): New function.
>>         (simplify_rhs_and_lookup_avail_expr): Disallow associativity
>>         and constant folding of floating point MULT_EXPR/PLUS_EXPR
>>         expressions.
>>
>>
>> Index: tree-ssa-dom.c
>> ===================================================================
>> RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dom.c,v
>> retrieving revision 2.56
>> diff -c -p -r2.56 tree-ssa-dom.c
>> *** tree-ssa-dom.c	29 Sep 2004 02:50:46 -0000	2.56
>> --- tree-ssa-dom.c	5 Oct 2004 16:53:05 -0000
>> *************** static void restore_currdefs_to_original
>> *** 266,271 ****
>> --- 266,272 ----
>>   static void register_definitions_for_stmt (tree);
>>   static edge single_incoming_edge_ignoring_loop_edges (basic_block);
>>   static void restore_nonzero_vars_to_original_value (void);
>> + static inline bool associative_fp_binop (tree);
>>
>>   /* Local version of fold that doesn't introduce cruft.  */
>>
>> *************** record_equality (tree x, tree y)
>> *** 1547,1552 ****
>> --- 1548,1563 ----
>>     record_const_or_copy_1 (x, y, prev_x);
>>   }
>>
>> + /* return true, if it is ok to do folding of an associative 
>> expression */
>> + static inline bool
>> + associative_fp_binop (tree exp)
>> + {
>> +   enum tree_code code = TREE_CODE (exp);
>> +   return !(!flag_unsafe_math_optimizations
>
> This flag is not clearly the right one.  Why did you pick it from the
> alternatives?

Which alternatives? flag_unsafe_math_optimizations was mentioned as the 
one
to check for by all people who commented on this thread.

>
>> +            && (code == MULT_EXPR || code == PLUS_EXPR)
>> +            && FLOAT_TYPE_P (TREE_TYPE (exp)));
>
> This function appears to disallow folding
>
> (x * 2.0) * 2.0
>
> into
>
> x * 4.0
>
> which seems to me to be valid.

Wording of ANSIC disallows such foldings even if it is safe sometimes.


>
> Please provide a testcase as part of the patch in proper dejagnu 
> format.
>

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Gabriel Dos Reis]

Geoffrey Keating <geoffk@geoffk.org> writes:

[...]

| > + static inline bool
| > + associative_fp_binop (tree exp)
| > + {
| > +   enum tree_code code = TREE_CODE (exp);
| > +   return !(!flag_unsafe_math_optimizations
| 
| This flag is not clearly the right one.  Why did you pick it from the
| alternatives?

That flag is clearly the right flag to pick.  See the explanation he gave.
It contains an example that illustrates the problem too.

-- Gaby

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Geoff Keating]

[-- Attachment #1: Type: text/plain, Size: 627 bytes --]


On 05/10/2004, at 1:04 PM, Fariborz Jahanian wrote:

>>> +            && (code == MULT_EXPR || code == PLUS_EXPR)
>>> +            && FLOAT_TYPE_P (TREE_TYPE (exp)));
>>
>> This function appears to disallow folding
>>
>> (x * 2.0) * 2.0
>>
>> into
>>
>> x * 4.0
>>
>> which seems to me to be valid.
>
> Wording of ANSIC disallows such foldings even if it is safe sometimes.

Could you explain why you think the standard says this?  The quote you 
gave said "In the following fragment, rearrangements suggested by 
mathematical rules for real numbers are often not valid" but it did not 
say that they were *always* not valid.

[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2410 bytes --]

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Geoff Keating]

[-- Attachment #1: Type: text/plain, Size: 736 bytes --]


On 05/10/2004, at 1:12 PM, Gabriel Dos Reis wrote:

> Geoffrey Keating <geoffk@geoffk.org> writes:
>
> [...]
>
> | > + static inline bool
> | > + associative_fp_binop (tree exp)
> | > + {
> | > +   enum tree_code code = TREE_CODE (exp);
> | > +   return !(!flag_unsafe_math_optimizations
> |
> | This flag is not clearly the right one.  Why did you pick it from the
> | alternatives?
>
> That flag is clearly the right flag to pick.  See the explanation he 
> gave.
> It contains an example that illustrates the problem too.

Fariborz said

> For different values of "x" this leads to undeserved or absent 
> floating point exceptions

So, why not flag_trapping_math?  The case involves an infinity, what 
about flag_finite_math_only?

[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2410 bytes --]

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Gabriel Dos Reis]

Geoff Keating <geoffk@geoffk.org> writes:

| On 05/10/2004, at 1:12 PM, Gabriel Dos Reis wrote:
| 
| > Geoffrey Keating <geoffk@geoffk.org> writes:
| >
| > [...]
| >
| > | > + static inline bool
| > | > + associative_fp_binop (tree exp)
| > | > + {
| > | > +   enum tree_code code = TREE_CODE (exp);
| > | > +   return !(!flag_unsafe_math_optimizations
| > |
| > | This flag is not clearly the right one.  Why did you pick it from the
| > | alternatives?
| >
| > That flag is clearly the right flag to pick.  See the explanation he
| > gave.
| > It contains an example that illustrates the problem too.
| 
| Fariborz said
| 
| > For different values of "x" this leads to undeserved or absent
| > floating point exceptions
| 
| So, why not flag_trapping_math?

Because fundamentally the rearragement leads to wrong code generation
which implies that, you get floating point exception if the result
raises an exception -- but it could be a finite value completely wrong
that leads your airplane crash later.  The exception is just *one*
manifestation of that wrongness.  So testing for flag_trapping_math is wrong.

|  The case involves an infinity, what
| about flag_finite_math_only?

Because the result could be finite but wrong.  So testing for
flag_trapping is wrong.

Really, the issue is straight.  The flag hee tested was the right to pick.

-- Gaby

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Gabriel Dos Reis]

Geoff Keating <geoffk@geoffk.org> writes:

| On 05/10/2004, at 1:04 PM, Fariborz Jahanian wrote:
| 
| >>> +            && (code == MULT_EXPR || code == PLUS_EXPR)
| >>> +            && FLOAT_TYPE_P (TREE_TYPE (exp)));
| >>
| >> This function appears to disallow folding
| >>
| >> (x * 2.0) * 2.0
| >>
| >> into
| >>
| >> x * 4.0
| >>
| >> which seems to me to be valid.
| >
| > Wording of ANSIC disallows such foldings even if it is safe sometimes.
| 
| Could you explain why you think the standard says this?  The quote you
| gave said "In the following fragment, rearrangements suggested by
| mathematical rules for real numbers are often not valid" but it did
| not say that they were *always* not valid.

But it does not say they are always valid either.

I'm having real trouble following your logic.

We apply transformations under the name of optimizations only when we
know that they are always valid under the usual conditions.  Here,
the reassociation is a general unsafe transformation for floating
point data type.

-- Gaby

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Fariborz Jahanian]

On Oct 5, 2004, at 1:53 PM, Geoff Keating wrote:

>>
>> Wording of ANSIC disallows such foldings even if it is safe sometimes.
>
> Could you explain why you think the standard says this?  The quote you 
> gave said "In the following fragment, rearrangements suggested by 
> mathematical rules for real numbers are often not valid" but it did 
> not say that they were *always* not valid.

The section uses such words as 'often restricted', 'generally invalid' 
'cannot generally replace'. So, I posed this as
the question and consensus was that we should place this under 
-funsafe-math-optimizations flag. Almost all
optimization placed under above flag is 'sometimes' valid and yet we 
place them under this flag. I don't
see a difference in this case.

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Gabriel Dos Reis]

Fariborz Jahanian <fjahanian@apple.com> writes:

| On Oct 5, 2004, at 1:53 PM, Geoff Keating wrote:
| 
| >>
| >> Wording of ANSIC disallows such foldings even if it is safe sometimes.
| >
| > Could you explain why you think the standard says this?  The quote
| > you gave said "In the following fragment, rearrangements suggested
| > by mathematical rules for real numbers are often not valid" but it
| > did not say that they were *always* not valid.
| 
| The section uses such words as 'often restricted', 'generally invalid'
| 'cannot generally replace'. So, I posed this as
| the question and consensus was that we should place this under
| -funsafe-math-optimizations flag. Almost all
| optimization placed under above flag is 'sometimes' valid and yet we
| place them under this flag.

Yes, and that is what we agreed on after repeated long debates.

| I don't see a difference in this case.

Right.

-- Gaby

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Geoff Keating]

[-- Attachment #1: Type: text/plain, Size: 1762 bytes --]


On 05/10/2004, at 2:04 PM, Gabriel Dos Reis wrote:

> Geoff Keating <geoffk@geoffk.org> writes:
>
> | On 05/10/2004, at 1:04 PM, Fariborz Jahanian wrote:
> |
> | >>> +            && (code == MULT_EXPR || code == PLUS_EXPR)
> | >>> +            && FLOAT_TYPE_P (TREE_TYPE (exp)));
> | >>
> | >> This function appears to disallow folding
> | >>
> | >> (x * 2.0) * 2.0
> | >>
> | >> into
> | >>
> | >> x * 4.0
> | >>
> | >> which seems to me to be valid.
> | >
> | > Wording of ANSIC disallows such foldings even if it is safe 
> sometimes.
> |
> | Could you explain why you think the standard says this?  The quote 
> you
> | gave said "In the following fragment, rearrangements suggested by
> | mathematical rules for real numbers are often not valid" but it did
> | not say that they were *always* not valid.
>
> But it does not say they are always valid either.

Are you claiming that the folding I describe above is *not* valid?

> I'm having real trouble following your logic.

I pointed out that the standard says ! forall (rearrangement, is valid) 
and that Fariborz was claiming that forall (rearrangement, ! is valid), 
and that this does not follow.  I also pointed out that exists 
(rearrangement, is valid), which implies ! forall (rearrangement, ! is 
valid).

> We apply transformations under the name of optimizations only when we
> know that they are always valid under the usual conditions.  Here,
> the reassociation is a general unsafe transformation for floating
> point data type.

No, we don't!  Nearly every optimisation we make is not valid under 
"usual conditions".  What we do is we test to see whether the proper 
conditions for the optimisation are met, so that if the test succeeds 
the optimization is valid under *all* conditions.

[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2410 bytes --]

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Dale Johannesen]

On 05/10/2004, at 1:12 PM, Gabriel Dos Reis wrote:
>
>> Geoffrey Keating <geoffk@geoffk.org> writes:
>> That flag is clearly the right flag to pick.  See the explanation he 
>> gave.
>> It contains an example that illustrates the problem too.
>
> Fariborz said
>
>> For different values of "x" this leads to undeserved or absent 
>> floating point exceptions
>
> So, why not flag_trapping_math?  The case involves an infinity, what 
> about flag_finite_math_only?

It is not just exceptions.  It is possible that X* (C*C) would 
overflow, or lose some low-order bits,
where (X*C)*C would not, for large C and small X.

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Gabriel Dos Reis]

Geoff Keating <geoffk@geoffk.org> writes:

| On 05/10/2004, at 2:04 PM, Gabriel Dos Reis wrote:
| 
| > Geoff Keating <geoffk@geoffk.org> writes:
| >
| > | On 05/10/2004, at 1:04 PM, Fariborz Jahanian wrote:
| > |
| > | >>> +            && (code == MULT_EXPR || code == PLUS_EXPR)
| > | >>> +            && FLOAT_TYPE_P (TREE_TYPE (exp)));
| > | >>
| > | >> This function appears to disallow folding
| > | >>
| > | >> (x * 2.0) * 2.0
| > | >>
| > | >> into
| > | >>
| > | >> x * 4.0
| > | >>
| > | >> which seems to me to be valid.
| > | >
| > | > Wording of ANSIC disallows such foldings even if it is safe
| > sometimes.
| > |
| > | Could you explain why you think the standard says this?  The quote
| > you
| > | gave said "In the following fragment, rearrangements suggested by
| > | mathematical rules for real numbers are often not valid" but it did
| > | not say that they were *always* not valid.
| >
| > But it does not say they are always valid either.
| 
| Are you claiming that the folding I describe above is *not* valid?

Exactly which folding?

   (x * 2.0) * 2.0

?

The routine under discussion is not designed to handle just that case.
It is designed handled more general case, and in the case case, your
transformation does not hold.
Now, are you suggesting to have -ffold-multiplication-by-2.0-and-2.0?

I would not object to that, even thought I'm of the opinion that new
flags should be introduced only if they are really needed.


| > I'm having real trouble following your logic.
| 
| I pointed out that the standard says !

I follow that part.  The part I do not follow is the logic you used in
the subsequent sentences.

| forall (rearrangement, is valid)

No.

| and that Fariborz was claiming that
| forall (rearrangement, ! is valid),

Yes, and he is right.

| and that this does not follow.

Huh?

| I also pointed out that exists (rearrangement, is valid), which
| implies ! forall (rearrangement, ! is valid).
| 
| > We apply transformations under the name of optimizations only when we
| > know that they are always valid under the usual conditions.  Here,
| > the reassociation is a general unsafe transformation for floating
| > point data type.
| 
| No, we don't!

Please look at the codes that do the transformations.  Roger Sayle has
always been very careful in guarding them.

| Nearly every optimisation we make is not valid under
| "usual conditions". 

Huh?

| What we do is we test to see whether the proper
| conditions for the optimisation are met, so that if the test succeeds
| the optimization is valid under *all* conditions.

Huh?

And what are you "proper conditions" are you using here?  None of
those you listed in a different message is sufficient.  

However, the flag tested in the patch covers the cases where the
dubious transformation is being applied.

-- Gaby

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Geoff Keating]

[-- Attachment #1: Type: text/plain, Size: 1023 bytes --]


On 05/10/2004, at 2:08 PM, Dale Johannesen wrote:

> On 05/10/2004, at 1:12 PM, Gabriel Dos Reis wrote:
>>
>>> Geoffrey Keating <geoffk@geoffk.org> writes:
>>> That flag is clearly the right flag to pick.  See the explanation he 
>>> gave.
>>> It contains an example that illustrates the problem too.
>>
>> Fariborz said
>>
>>> For different values of "x" this leads to undeserved or absent 
>>> floating point exceptions
>>
>> So, why not flag_trapping_math?  The case involves an infinity, what 
>> about flag_finite_math_only?
>
> It is not just exceptions.  It is possible that X* (C*C) would 
> overflow, or lose some low-order bits,
> where (X*C)*C would not, for large C and small X.

OK.  I am not going to re-design Fariborz's patch for him in an e-mail 
exchange.  It is clear that the explanation of the patch is inadequate 
to determine whether or not the patch is correct, so the patch is 
rejected.  Fariborz, please re-post the patch with a better 
explanation, and addressing the other points I mentioned.

[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2410 bytes --]

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Gabriel Dos Reis]

Geoff Keating <geoffk@geoffk.org> writes:

| On 05/10/2004, at 2:08 PM, Dale Johannesen wrote:
| 
| > On 05/10/2004, at 1:12 PM, Gabriel Dos Reis wrote:
| >>
| >>> Geoffrey Keating <geoffk@geoffk.org> writes:
| >>> That flag is clearly the right flag to pick.  See the explanation
| >>> he gave.
| >>> It contains an example that illustrates the problem too.
| >>
| >> Fariborz said
| >>
| >>> For different values of "x" this leads to undeserved or absent
| >>> floating point exceptions
| >>
| >> So, why not flag_trapping_math?  The case involves an infinity,
| >> what about flag_finite_math_only?
| >
| > It is not just exceptions.  It is possible that X* (C*C) would
| > overflow, or lose some low-order bits,
| > where (X*C)*C would not, for large C and small X.
| 
| OK.  I am not going to re-design Fariborz's patch for him in an e-mail
| exchange.  It is clear that the explanation of the patch is inadequate
| to determine whether or not the patch is correct, so the patch is
| rejected.  Fariborz, please re-post the patch with a better
| explanation, and addressing the other points I mentioned.

Which other points?

  (1) clearly, flag_finite_math_only is not adquate
  (2) clearly, flag_trapping_math is not adequate
  (3) clearly, testing both is not adequate

I found his explanation rather clear, as to what the root of the
problem is. 

Your reaction is rather difficult to follow.

-- Gaby

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Fariborz Jahanian]

On Oct 5, 2004, at 2:29 PM, Geoff Keating wrote:
>>  following your logic.
>
> I pointed out that the standard says ! forall (rearrangement, is 
> valid) and that Fariborz was claiming that forall (rearrangement, ! is 
> valid), and that this does not follow.  I also pointed out that exists 
> (rearrangement, is valid), which implies ! forall (rearrangement, ! is 
> valid).

To use your notation, You are saying that sometimes (rearrangement, is 
valid). And such cases belong
to -funsafe-math-optimisations.

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Fariborz Jahanian]

On Oct 5, 2004, at 2:46 PM, Geoff Keating wrote:

> OK.  I am not going to re-design Fariborz's patch for him in an e-mail 
> exchange.  It is clear that the explanation of the patch is inadequate 
> to determine whether or not the patch is correct, so the patch is 
> rejected.  Fariborz, please re-post the patch with a better 
> explanation, and addressing the other points I mentioned.

I can submit a new patch  summarizing what were discussed in the 
thread, if you think this is
good use of my time :).

- fariborz

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Fariborz Jahanian]

[-- Attachment #1: Type: text/plain, Size: 3731 bytes --]


On Oct 5, 2004, at 2:46 PM, Geoff Keating wrote:

>
> OK.  I am not going to re-design Fariborz's patch for him in an e-mail 
> exchange.  It is clear that the explanation of the patch is inadequate 
> to determine whether or not the patch is correct, so the patch is 
> rejected.  Fariborz, please re-post the patch with a better 
> explanation, and addressing the other points I mentioned.


I have a new patch description which, I hope, addresses Geoff's 
questions. Also, I have attached a dejagnu-style
test case.

- fariborz (fjahanian@apple.com)

Abstract: In the following code the repeated multiplication is folded 
into a single
operation (multiplication by Infinity), when compiled for 
apple-ppc-darwin target.
For different values of "x" this leads to undeserved or absent floating 
point
exceptions, and breaks some of the elementary math functions in Libm. 
Occurs
at optimization O1 and higher.

/* test */
static const double C = 0x1.0p1023;

double foo(double x)
{
         return ( ( (x * C) * C ) * C );
}

Section 5.1.2.3 Program execution of the Programming languages C  
standard says:

13 EXAMPLE 5 Rearrangement for floating-point expressions is often 
restricted because of limitations
in precision as well as range. The implementation cannot generally 
apply the mathematical associative
rules for addition or multiplication, nor the distributive rule, 
because of roundoff error, even
in the absence of overflowand underflow.  Likewise, implementations 
cannot generally replace decimal
constants in order to rearrange expressions. In the following fragment, 
rearrangements suggested by
mathematical rules for real numbers are often not valid (see F.8).
double x, y, z;
/*... */
x=(x*y)*z;
//not equivalent to
x*=y*z;

So, such optimization cannot take place under general optimization 
flags.
Question remains, under which flag should we place this specific unsafe 
optiomization?
There has been three suggestions, I will address each, one by one.

1. Do this optimization when flag_trapping_math is 0 (default is 1).
"Zero means that floating-point math operations cannot generate a
(user-visible) trap". This includes overflow, underflow. This certainly
can be the flag to check for. But such an optimization may cause finite
results which could be incorrect without causing a trap, for example,
a roundoff error.

2. Do this optimization when flag_finite_math_only is 1 (default is 0).
"Allow optimizations for floating-point arithmetic that assume that
arguments and results are not NaNs or +-Infs". Again, result of such
an optimization can be finite but wrong.

3. -funsafe-math-optimizations
    "Allow optimizations for floating-point arithmetic that (a) assume
    that arguments and results are valid and (b) may violate IEEE or
    ANSI standards".
    Such an optimization is in violation of Section 5.1.2.3 of ANSI 
standards
    as noted in above.

    Above flag has been used for the following case, among others:

    from negate_expr_p(tree) in fold-const.c

       case PLUS_EXPR:
       if (FLOAT_TYPE_P (type) && !flag_unsafe_math_optimizations)
         return false;
       /* -(A + B) -> (-B) - A.  */
         ...
       /* -(A + B) -> (-A) - B.  */
         ...

    So, it seems that flag_unsafe_math_optimizations has been used in
    other situations to disallow certain optimizations which are in 
violation of ANSI
    standards. This is the flag that I check for in my patch.


ChangeLog:

2004-10-05  Fariborz Jahanian <fjahanian@apple.com>

         * tree-ssa-dom.c (associative_fp_binop): New function.
         (simplify_rhs_and_lookup_avail_expr): Disallow associativity
         and constant folding of floating point MULT_EXPR/PLUS_EXPR
         expressions.


[-- Attachment #2: fsf-patch-tree-ssa-dom.txt --]
[-- Type: text/plain, Size: 2060 bytes --]

Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dom.c,v
retrieving revision 2.56
diff -c -p -r2.56 tree-ssa-dom.c
*** tree-ssa-dom.c	29 Sep 2004 02:50:46 -0000	2.56
--- tree-ssa-dom.c	5 Oct 2004 19:51:39 -0000
*************** static void restore_currdefs_to_original
*** 266,271 ****
--- 266,272 ----
  static void register_definitions_for_stmt (tree);
  static edge single_incoming_edge_ignoring_loop_edges (basic_block);
  static void restore_nonzero_vars_to_original_value (void);
+ static inline bool unsafe_associative_fp_binop (tree);
  
  /* Local version of fold that doesn't introduce cruft.  */
  
*************** record_equality (tree x, tree y)
*** 1547,1552 ****
--- 1548,1563 ----
    record_const_or_copy_1 (x, y, prev_x);
  }
  
+ /* return true, if it is ok to do folding of an associative expression */ 
+ static inline bool
+ unsafe_associative_fp_binop (tree exp)
+ {
+   enum tree_code code = TREE_CODE (exp);
+   return !(!flag_unsafe_math_optimizations
+            && (code == MULT_EXPR || code == PLUS_EXPR)
+            && FLOAT_TYPE_P (TREE_TYPE (exp)));
+ }
+ 
  /* STMT is a MODIFY_EXPR for which we were unable to find RHS in the
     hash tables.  Try to simplify the RHS using whatever equivalences
     we may have recorded.
*************** simplify_rhs_and_lookup_avail_expr (stru
*** 1606,1612 ****
  	  tree rhs_def_rhs = TREE_OPERAND (rhs_def_stmt, 1);
  	  enum tree_code rhs_def_code = TREE_CODE (rhs_def_rhs);
  
! 	  if (rhs_code == rhs_def_code
  	      || (rhs_code == PLUS_EXPR && rhs_def_code == MINUS_EXPR)
  	      || (rhs_code == MINUS_EXPR && rhs_def_code == PLUS_EXPR))
  	    {
--- 1617,1623 ----
  	  tree rhs_def_rhs = TREE_OPERAND (rhs_def_stmt, 1);
  	  enum tree_code rhs_def_code = TREE_CODE (rhs_def_rhs);
  
! 	  if ((rhs_code == rhs_def_code && unsafe_associative_fp_binop (rhs))
  	      || (rhs_code == PLUS_EXPR && rhs_def_code == MINUS_EXPR)
  	      || (rhs_code == MINUS_EXPR && rhs_def_code == PLUS_EXPR))
  	    {

[-- Attachment #3: Type: text/plain, Size: 7 bytes --]

  
    

[-- Attachment #4: unsafe-fp-assoc.c --]
[-- Type: text/plain, Size: 280 bytes --]

/* { dg-do run { target powerpc*-*-* } } */
/* { dg-options "-O1" */

extern void abort(void);

static const double C = 0x1.0p1023;

double foo(double x)
{
        return ( ( (x * C) * C ) * C);
}

int main ()
{
  double d = foo (0.0);
  if (d != 0.0)
   abort ();

  return 0;
}

[-- Attachment #5: Type: text/plain, Size: 2 bytes --]

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Geoff Keating]

[-- Attachment #1: Type: text/plain, Size: 4468 bytes --]


On 06/10/2004, at 10:11 AM, Fariborz Jahanian wrote:

>
> On Oct 5, 2004, at 2:46 PM, Geoff Keating wrote:
>
>>
>> OK.  I am not going to re-design Fariborz's patch for him in an 
>> e-mail exchange.  It is clear that the explanation of the patch is 
>> inadequate to determine whether or not the patch is correct, so the 
>> patch is rejected.  Fariborz, please re-post the patch with a better 
>> explanation, and addressing the other points I mentioned.
>
>
> I have a new patch description which, I hope, addresses Geoff's 
> questions. Also, I have attached a dejagnu-style
> test case.

No, do not "attach" it.  Make it *part of the patch*, so that I can see 
where you are planning to put it in the tree.  Also, why is it limited 
to running on powerpc?  Why is it forcing -O1?

> - fariborz (fjahanian@apple.com)
>
> Abstract: In the following code the repeated multiplication is folded 
> into a single
> operation (multiplication by Infinity), when compiled for 
> apple-ppc-darwin target.
> For different values of "x" this leads to undeserved or absent 
> floating point
> exceptions, and breaks some of the elementary math functions in Libm. 
> Occurs
> at optimization O1 and higher.
>
> /* test */
> static const double C = 0x1.0p1023;
>
> double foo(double x)
> {
>         return ( ( (x * C) * C ) * C );
> }
>
> Section 5.1.2.3 Program execution of the Programming languages C  
> standard says:
>
> 13 EXAMPLE 5 Rearrangement for floating-point expressions is often 
> restricted because of limitations
> in precision as well as range. The implementation cannot generally 
> apply the mathematical associative
> rules for addition or multiplication, nor the distributive rule, 
> because of roundoff error, even
> in the absence of overflowand underflow.  Likewise, implementations 
> cannot generally replace decimal
> constants in order to rearrange expressions. In the following 
> fragment, rearrangements suggested by
> mathematical rules for real numbers are often not valid (see F.8).
> double x, y, z;
> /*... */
> x=(x*y)*z;
> //not equivalent to
> x*=y*z;
>
> So, such optimization cannot take place under general optimization 
> flags.
> Question remains, under which flag should we place this specific 
> unsafe optiomization?
> There has been three suggestions, I will address each, one by one.
>
> 1. Do this optimization when flag_trapping_math is 0 (default is 1).
> "Zero means that floating-point math operations cannot generate a
> (user-visible) trap". This includes overflow, underflow. This certainly
> can be the flag to check for. But such an optimization may cause finite
> results which could be incorrect without causing a trap, for example,
> a roundoff error.
>
> 2. Do this optimization when flag_finite_math_only is 1 (default is 0).
> "Allow optimizations for floating-point arithmetic that assume that
> arguments and results are not NaNs or +-Infs". Again, result of such
> an optimization can be finite but wrong.
>
> 3. -funsafe-math-optimizations
>    "Allow optimizations for floating-point arithmetic that (a) assume
>    that arguments and results are valid and (b) may violate IEEE or
>    ANSI standards".
>    Such an optimization is in violation of Section 5.1.2.3 of ANSI 
> standards
>    as noted in above.
>
>    Above flag has been used for the following case, among others:
>
>    from negate_expr_p(tree) in fold-const.c
>
>       case PLUS_EXPR:
>       if (FLOAT_TYPE_P (type) && !flag_unsafe_math_optimizations)
>         return false;
>       /* -(A + B) -> (-B) - A.  */
>         ...
>       /* -(A + B) -> (-A) - B.  */
>         ...
>
>    So, it seems that flag_unsafe_math_optimizations has been used in
>    other situations to disallow certain optimizations which are in 
> violation of ANSI
>    standards. This is the flag that I check for in my patch.

Your explanation is still wrong, but I don't think you understand the 
situation well enough to come up with a correct explanation, so I'm 
giving up on that part.  I would suggest, though, that in future you 
ask an expert about standards or floating-point questions.

>
> ChangeLog:
>
> 2004-10-05  Fariborz Jahanian <fjahanian@apple.com>
>
>         * tree-ssa-dom.c (associative_fp_binop): New function.
>         (simplify_rhs_and_lookup_avail_expr): Disallow associativity
>         and constant folding of floating point MULT_EXPR/PLUS_EXPR
>         expressions.
>
> <fsf-patch-tree-ssa-dom.txt>    <unsafe-fp-assoc.c>
>

[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2410 bytes --]

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Fariborz Jahanian]

On Oct 6, 2004, at 11:38 AM, Geoff Keating wrote:

>
> On 06/10/2004, at 10:11 AM, Fariborz Jahanian wrote:
>
>>
>> On Oct 5, 2004, at 2:46 PM, Geoff Keating wrote:
>>
>>>
>>> OK.  I am not going to re-design Fariborz's patch for him in an 
>>> e-mail exchange.  It is clear that the explanation of the patch is 
>>> inadequate to determine whether or not the patch is correct, so the 
>>> patch is rejected.  Fariborz, please re-post the patch with a better 
>>> explanation, and addressing the other points I mentioned.
>>
>>
>> I have a new patch description which, I hope, addresses Geoff's 
>> questions. Also, I have attached a dejagnu-style
>> test case.
>
> No, do not "attach" it.  Make it *part of the patch*, so that I can 
> see where you are planning to put it in the tree.  Also, why is it 
> limited to running on powerpc?  Why is it forcing -O1?

Every body attaches a test case to the patch describing the patch. 
Sorry, I don't understand you here. This test
case goes under gcc.dg directory (if this is the question you are 
raising). Also, -O1 shows the problem. So,
test case shows the problem with -O1. I will remove powerpc in test 
case.

>
>> - fariborz (fjahanian@apple.com)
>>
>> Abstract: In the following code the repeated multiplication is folded 
>> into a single
>> operation (multiplication by Infinity), when compiled for 
>> apple-ppc-darwin target.
>> For different values of "x" this leads to undeserved or absent 
>> floating point
>> exceptions, and breaks some of the elementary math functions in Libm. 
>> Occurs
>> at optimization O1 and higher.
>>
>> /* test */
>> static const double C = 0x1.0p1023;
>>
>> double foo(double x)
>> {
>>         return ( ( (x * C) * C ) * C );
>> }
>>
>> Section 5.1.2.3 Program execution of the Programming languages C  
>> standard says:
>>
>> 13 EXAMPLE 5 Rearrangement for floating-point expressions is often 
>> restricted because of limitations
>> in precision as well as range. The implementation cannot generally 
>> apply the mathematical associative
>> rules for addition or multiplication, nor the distributive rule, 
>> because of roundoff error, even
>> in the absence of overflowand underflow.  Likewise, implementations 
>> cannot generally replace decimal
>> constants in order to rearrange expressions. In the following 
>> fragment, rearrangements suggested by
>> mathematical rules for real numbers are often not valid (see F.8).
>> double x, y, z;
>> /*... */
>> x=(x*y)*z;
>> //not equivalent to
>> x*=y*z;
>>
>> So, such optimization cannot take place under general optimization 
>> flags.
>> Question remains, under which flag should we place this specific 
>> unsafe optiomization?
>> There has been three suggestions, I will address each, one by one.
>>
>> 1. Do this optimization when flag_trapping_math is 0 (default is 1).
>> "Zero means that floating-point math operations cannot generate a
>> (user-visible) trap". This includes overflow, underflow. This 
>> certainly
>> can be the flag to check for. But such an optimization may cause 
>> finite
>> results which could be incorrect without causing a trap, for example,
>> a roundoff error.
>>
>> 2. Do this optimization when flag_finite_math_only is 1 (default is 
>> 0).
>> "Allow optimizations for floating-point arithmetic that assume that
>> arguments and results are not NaNs or +-Infs". Again, result of such
>> an optimization can be finite but wrong.
>>
>> 3. -funsafe-math-optimizations
>>    "Allow optimizations for floating-point arithmetic that (a) assume
>>    that arguments and results are valid and (b) may violate IEEE or
>>    ANSI standards".
>>    Such an optimization is in violation of Section 5.1.2.3 of ANSI 
>> standards
>>    as noted in above.
>>
>>    Above flag has been used for the following case, among others:
>>
>>    from negate_expr_p(tree) in fold-const.c
>>
>>       case PLUS_EXPR:
>>       if (FLOAT_TYPE_P (type) && !flag_unsafe_math_optimizations)
>>         return false;
>>       /* -(A + B) -> (-B) - A.  */
>>         ...
>>       /* -(A + B) -> (-A) - B.  */
>>         ...
>>
>>    So, it seems that flag_unsafe_math_optimizations has been used in
>>    other situations to disallow certain optimizations which are in 
>> violation of ANSI
>>    standards. This is the flag that I check for in my patch.
>
> Your explanation is still wrong, but I don't think you understand the 
> situation well enough to come up with a correct explanation, so I'm 
> giving up on that part.  I would suggest, though, that in future you 
> ask an expert about standards or floating-point questions.

I tried, I tried. I sent the patch as request for comments and received 
responses from several  people;
including Dale, Gaby, you, and Roger.  I am sure you will find an 
expert among this panel. Please go
back and read the extensive thread of the past two days. BTW, this bug 
was filed by Steve Peters at
Apple who most of us consider an expert on FP issues.

- fariborz


>
>>
>> ChangeLog:
>>
>> 2004-10-05  Fariborz Jahanian <fjahanian@apple.com>
>>
>>         * tree-ssa-dom.c (associative_fp_binop): New function.
>>         (simplify_rhs_and_lookup_avail_expr): Disallow associativity
>>         and constant folding of floating point MULT_EXPR/PLUS_EXPR
>>         expressions.
>>
>> <fsf-patch-tree-ssa-dom.txt>    <unsafe-fp-assoc.c>
>>

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Gabriel Dos Reis]

| giving up on that part.  I would suggest, though, that in future you
| ask an expert about standards or floating-point questions.

I believe that is what he did in his original message.

-- Gaby

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Richard Henderson]

On Tue, Oct 05, 2004 at 04:02:33PM -0400, Andrew Pinski wrote:
> Also this is a valid transformation only if the constants will generate
> a power of 2.

No, it's valid any time the product of the constants is directly
representable.  We have the information to determine that in real.c.


r~

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Fariborz Jahanian]

[-- Attachment #1: Type: text/plain, Size: 412 bytes --]

Offline, Geoff has suggested some changes for the approval. Here it is.

thanks, fariborz (fjahanian@apple.com).


ChangeLog:

2004-10-06  Fariborz Jahanian <fjahanian@apple.com>

         * tree-ssa-dom.c (unsafe_associative_fp_binop): New function.
         (simplify_rhs_and_lookup_avail_expr): Disallow associativity
         and constant folding of floating point MULT_EXPR/PLUS_EXPR
         expressions.


[-- Attachment #2: fsf-patch-tree-ssa-dom.txt --]
[-- Type: text/plain, Size: 2728 bytes --]

Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dom.c,v
retrieving revision 2.56
diff -c -p -r2.56 tree-ssa-dom.c
*** tree-ssa-dom.c	29 Sep 2004 02:50:46 -0000	2.56
--- tree-ssa-dom.c	6 Oct 2004 23:59:44 -0000
*************** static void restore_currdefs_to_original
*** 266,271 ****
--- 266,272 ----
  static void register_definitions_for_stmt (tree);
  static edge single_incoming_edge_ignoring_loop_edges (basic_block);
  static void restore_nonzero_vars_to_original_value (void);
+ static inline bool unsafe_associative_fp_binop (tree);
  
  /* Local version of fold that doesn't introduce cruft.  */
  
*************** record_equality (tree x, tree y)
*** 1547,1552 ****
--- 1548,1563 ----
    record_const_or_copy_1 (x, y, prev_x);
  }
  
+ /* return true, if it is ok to do folding of an associative expression */ 
+ static inline bool
+ unsafe_associative_fp_binop (tree exp)
+ {
+   enum tree_code code = TREE_CODE (exp);
+   return !(!flag_unsafe_math_optimizations
+            && (code == MULT_EXPR || code == PLUS_EXPR)
+            && FLOAT_TYPE_P (TREE_TYPE (exp)));
+ }
+ 
  /* STMT is a MODIFY_EXPR for which we were unable to find RHS in the
     hash tables.  Try to simplify the RHS using whatever equivalences
     we may have recorded.
*************** simplify_rhs_and_lookup_avail_expr (stru
*** 1606,1612 ****
  	  tree rhs_def_rhs = TREE_OPERAND (rhs_def_stmt, 1);
  	  enum tree_code rhs_def_code = TREE_CODE (rhs_def_rhs);
  
! 	  if (rhs_code == rhs_def_code
  	      || (rhs_code == PLUS_EXPR && rhs_def_code == MINUS_EXPR)
  	      || (rhs_code == MINUS_EXPR && rhs_def_code == PLUS_EXPR))
  	    {
--- 1617,1623 ----
  	  tree rhs_def_rhs = TREE_OPERAND (rhs_def_stmt, 1);
  	  enum tree_code rhs_def_code = TREE_CODE (rhs_def_rhs);
  
! 	  if ((rhs_code == rhs_def_code && unsafe_associative_fp_binop (rhs))
  	      || (rhs_code == PLUS_EXPR && rhs_def_code == MINUS_EXPR)
  	      || (rhs_code == MINUS_EXPR && rhs_def_code == PLUS_EXPR))
  	    {
Index: testsuite/gcc.c-torture/execute/ieee/unsafe-fp-assoc.c
===================================================================
RCS file: testsuite/gcc.c-torture/execute/ieee/unsafe-fp-assoc.c
diff -N testsuite/gcc.c-torture/execute/ieee/unsafe-fp-assoc.c
*** /dev/null	1 Jan 1970 00:00:00 -0000
--- testsuite/gcc.c-torture/execute/ieee/unsafe-fp-assoc.c	6 Oct 2004 23:59:49 -0000
***************
*** 0 ****
--- 1,17 ----
+ extern void abort(void);
+ 
+ static const double C = 0x1.0p1023;
+ 
+ double foo(double x)
+ {
+         return ( ( (x * C) * C ) * C);
+ }
+ 
+ int main ()
+ {
+   double d = foo (0.0);
+   if (d != 0.0)
+    abort ();
+ 
+   return 0;
+ }

[-- Attachment #3: Type: text/plain, Size: 4 bytes --]



	

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Mark Mitchell]

Fariborz Jahanian wrote:

> Offline, Geoff has suggested some changes for the approval. Here it is.
>
>+ /* return true, if it is ok to do folding of an associative expression */ 
>+ static inline bool
>+ unsafe_associative_fp_binop (tree exp)
>  
>
This is a style violations.  The comment should begin with a capital 
latter, end with a period, followed by two spaces, before the "*/".  
And, you must describe the parameter, which should be named in ALL CAPS 
in the comment.  Please fix before check-in.

-- 
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Richard Henderson]

On Wed, Oct 06, 2004 at 05:05:08PM -0700, Fariborz Jahanian wrote:
>         * tree-ssa-dom.c (unsafe_associative_fp_binop): New function.
>         (simplify_rhs_and_lookup_avail_expr): Disallow associativity
>         and constant folding of floating point MULT_EXPR/PLUS_EXPR
>         expressions.

If you apply this, I'll immediately file a PR for a regression
and assign it to you.

You should allow 

	X op C1 op C2
to combine to
	X op C3

if C1 op C2 is exactly representable.  Which happens very often.

The information for whether or not C1 op C2 is representable is
available from real.c during the computation of the composite,
so there's absolutely reason not to use it.



r~

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Richard Henderson]

On Wed, Oct 06, 2004 at 05:05:08PM -0700, Fariborz Jahanian wrote:
> + static const double C = 0x1.0p1023;

Also, 2**1023 is not a good number to choose at random.  It will
fail for targets that use a smaller "double", like some versions
of SH.  Just use DBL_MAX instead.


r~

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Ziemowit Laski]

On 7 Oct 2004, at 13.38, Richard Henderson wrote:

> On Wed, Oct 06, 2004 at 05:05:08PM -0700, Fariborz Jahanian wrote:
>>         * tree-ssa-dom.c (unsafe_associative_fp_binop): New function.
>>         (simplify_rhs_and_lookup_avail_expr): Disallow associativity
>>         and constant folding of floating point MULT_EXPR/PLUS_EXPR
>>         expressions.
>
> If you apply this, I'll immediately file a PR for a regression
> and assign it to you.
>
> You should allow
>
> 	X op C1 op C2
> to combine to
> 	X op C3
>
> if C1 op C2 is exactly representable.  Which happens very often.

Yes, but don't 'X op C1' and 'X op C3' also need to be exactly 
representable?

--Zem

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Gabriel Dos Reis]

Richard Henderson <rth@redhat.com> writes:

| On Wed, Oct 06, 2004 at 05:05:08PM -0700, Fariborz Jahanian wrote:
| >         * tree-ssa-dom.c (unsafe_associative_fp_binop): New function.
| >         (simplify_rhs_and_lookup_avail_expr): Disallow associativity
| >         and constant folding of floating point MULT_EXPR/PLUS_EXPR
| >         expressions.
| 
| If you apply this, I'll immediately file a PR for a regression
| and assign it to you.
| 
| You should allow 
| 
| 	X op C1 op C2
| to combine to
| 	X op C3
| 
| if C1 op C2 is exactly representable. 

Only if C3 does not overflow, which is the root of the issue why this
transformation is unsafe in general.

-- Gaby

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Richard Henderson]

On Thu, Oct 07, 2004 at 03:49:45PM -0500, Gabriel Dos Reis wrote:
> Richard Henderson <rth@redhat.com> writes:
> 
> | On Wed, Oct 06, 2004 at 05:05:08PM -0700, Fariborz Jahanian wrote:
> | >         * tree-ssa-dom.c (unsafe_associative_fp_binop): New function.
> | >         (simplify_rhs_and_lookup_avail_expr): Disallow associativity
> | >         and constant folding of floating point MULT_EXPR/PLUS_EXPR
> | >         expressions.
> | 
> | If you apply this, I'll immediately file a PR for a regression
> | and assign it to you.
> | 
> | You should allow 
> | 
> | 	X op C1 op C2
> | to combine to
> | 	X op C3
> | 
> | if C1 op C2 is exactly representable. 
> 
> Only if C3 does not overflow, which is the root of the issue why this
> transformation is unsafe in general.

Well, overflow is a subset of "not exactly representable", yes.

But more than that, (X * 0.3 * 3) would not be folded because bits
would be lost off the least-significant end.  Which is surely the
more serious folding error.

If we were only concerned about overflow, we should be checking
HONOR_INFINITIES instead of flag_unsafe_math_optimizations.


r~

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Richard Henderson]

On Thu, Oct 07, 2004 at 01:43:41PM -0700, Ziemowit Laski wrote:
> >You should allow
> >
> >	X op C1 op C2
> >to combine to
> >	X op C3
> >
> >if C1 op C2 is exactly representable.  Which happens very often.
> 
> Yes, but don't 'X op C1' and 'X op C3' also need to be exactly 
> representable?

Not so far as I can determine.  What specifically leads you 
to believe this?


r~

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Fariborz Jahanian]

On Oct 7, 2004, at 1:49 PM, Gabriel Dos Reis wrote:

> Richard Henderson <rth@redhat.com> writes:
>
> | On Wed, Oct 06, 2004 at 05:05:08PM -0700, Fariborz Jahanian wrote:
> | >         * tree-ssa-dom.c (unsafe_associative_fp_binop): New 
> function.
> | >         (simplify_rhs_and_lookup_avail_expr): Disallow 
> associativity
> | >         and constant folding of floating point MULT_EXPR/PLUS_EXPR
> | >         expressions.
> |
> | If you apply this, I'll immediately file a PR for a regression
> | and assign it to you.
> |
> | You should allow
> |
> | 	X op C1 op C2
> | to combine to
> | 	X op C3
> |
> | if C1 op C2 is exactly representable.
>
> Only if C3 does not overflow, which is the root of the issue why this
> transformation is unsafe in general.

do_multiply routine does return 'true' for inexact results. But I am 
not sure, if this is one of them.
Can we rely on math routines in real.c to tell us the 'exact' from 
'inextact' ops?

- fariborz

>
> -- Gaby

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Gabriel Dos Reis]

Richard Henderson <rth@redhat.com> writes:

| On Thu, Oct 07, 2004 at 03:49:45PM -0500, Gabriel Dos Reis wrote:
| > Richard Henderson <rth@redhat.com> writes:
| > 
| > | On Wed, Oct 06, 2004 at 05:05:08PM -0700, Fariborz Jahanian wrote:
| > | >         * tree-ssa-dom.c (unsafe_associative_fp_binop): New function.
| > | >         (simplify_rhs_and_lookup_avail_expr): Disallow associativity
| > | >         and constant folding of floating point MULT_EXPR/PLUS_EXPR
| > | >         expressions.
| > | 
| > | If you apply this, I'll immediately file a PR for a regression
| > | and assign it to you.
| > | 
| > | You should allow 
| > | 
| > | 	X op C1 op C2
| > | to combine to
| > | 	X op C3
| > | 
| > | if C1 op C2 is exactly representable. 
| > 
| > Only if C3 does not overflow, which is the root of the issue why this
| > transformation is unsafe in general.
| 
| Well, overflow is a subset of "not exactly representable", yes.

Yes, but that was not the point I was making.

| But more than that, (X * 0.3 * 3) would not be folded because bits
| would be lost off the least-significant end.  Which is surely the
| more serious folding error.

My point was that it does not suffice that C1 and C2 be exactly
representable, we also need C3 not to overflow.

| If we were only concerned about overflow, we should be checking
| HONOR_INFINITIES instead of flag_unsafe_math_optimizations.

We're not only concerned about overflow.  See above for the point of
my remark.

-- Gaby

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Ziemowit Laski]

On 7 Oct 2004, at 14.17, Richard Henderson wrote:

> On Thu, Oct 07, 2004 at 01:43:41PM -0700, Ziemowit Laski wrote:
>>> You should allow
>>>
>>> 	X op C1 op C2
>>> to combine to
>>> 	X op C3
>>>
>>> if C1 op C2 is exactly representable.  Which happens very often.
>>
>> Yes, but don't 'X op C1' and 'X op C3' also need to be exactly
>> representable?
>
> Not so far as I can determine.  What specifically leads you
> to believe this?

Actually, I overshot a bit. :-(  You need to know that 'X op C1'
and 'C1 op C2' are exactly representable.  Otherwise, you may have

    (X op C1) op C2 != X op (C1 op C2)

which is why this folding is unsafe in the general case.

Actually, Dale just popped his head in and suggested that the folding
might be OK if C1 == C2. :-)

--Zem

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Richard Henderson]

On Thu, Oct 07, 2004 at 02:18:45PM -0700, Fariborz Jahanian wrote:
> Can we rely on math routines in real.c to tell us the 'exact' from 
> 'inextact' ops?

Yes, in that if we find a bug it's considered a bug in real.c.
But I am aware of no such problems at the moment.

Note that you have to check more than just the result of do_multiply,
since that only returns true if bits are lost in the internal 
representation.  You also have to check for inexact results when
rounding the result to the target format.

Also, rather than exporting do_multiply, as I'm guessing you're
about to do, make real_arithmetic return true for inexact.


r~

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Fariborz Jahanian]

On Oct 7, 2004, at 2:33 PM, Ziemowit Laski wrote:
>
> Actually, I overshot a bit. :-(  You need to know that 'X op C1'
> and 'C1 op C2' are exactly representable.  Otherwise, you may have
>
>    (X op C1) op C2 != X op (C1 op C2)
>
> which is why this folding is unsafe in the general case.

Yes. Take the case that (C1 op C2) is exactly representable *and* X op 
(C1 op C2)
overflows but (X  op C1) op C2 does not overflow.

- fariborz

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Dale Johannesen]

On Oct 7, 2004, at 2:33 PM, Ziemowit Laski wrote:
> Actually, I overshot a bit. :-(  You need to know that 'X op C1'
> and 'C1 op C2' are exactly representable.  Otherwise, you may have
>
>    (X op C1) op C2 != X op (C1 op C2)
>
> which is why this folding is unsafe in the general case.

X is unknown, so we can't say anything much about (X op C1)
at compile time.

It is possible that (X op C1) would overflow or lose precision
when the second form would not, even if (C1 op C2) is exactly
representable;  consider X and C1 very large, C2==1/C1.

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Fariborz Jahanian]

On Oct 7, 2004, at 2:39 PM, Richard Henderson wrote:

>
> Also, rather than exporting do_multiply, as I'm guessing you're
> about to do, make real_arithmetic return true for inexact.

Thanks for the info. No I was not planning to do anything, considering 
the traffic this thread
has created. I will wait for dust to settle before I do actual coding.

- fariborz

>
>
> r~

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Dale Johannesen]

On Oct 7, 2004, at 2:45 PM, Dale Johannesen wrote:
> On Oct 7, 2004, at 2:33 PM, Ziemowit Laski wrote:
>> Actually, I overshot a bit. :-(  You need to know that 'X op C1'
>> and 'C1 op C2' are exactly representable.  Otherwise, you may have
>>
>>    (X op C1) op C2 != X op (C1 op C2)
>>
>> which is why this folding is unsafe in the general case.
>
> X is unknown, so we can't say anything much about (X op C1)
> at compile time.
>
> It is possible that (X op C1) would overflow or lose precision
> when the second form would not, even if (C1 op C2) is exactly
> representable;  consider X and C1 very large, C2==1/C1.

Offhand it seems that the combination might be safe if C1 op C2 is
representable, and  C1 and C2 both "move the result in the same 
direction",
i.e. both absolute values >1 or both <1 for multiplication, both 
positive or
both negative for addition and subtraction.  (Obviously it's OK if one 
of
them is 0 but I assume this is handled elsewhere.)  Does this seem 
right?

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Fariborz Jahanian]

On Oct 7, 2004, at 2:58 PM, Dale Johannesen wrote:

> On Oct 7, 2004, at 2:45 PM, Dale Johannesen wrote:
>
> Offhand it seems that the combination might be safe if C1 op C2 is
> representable, and  C1 and C2 both "move the result in the same 
> direction",
> i.e. both absolute values >1 or both <1 for multiplication, both 
> positive or
> both negative for addition and subtraction.  (Obviously it's OK if one 
> of
> them is 0 but I assume this is handled elsewhere.)  Does this seem 
> right?

Seems right to me. It certainly rules out the scenario I presented in 
my previous email.
If this is the necessary condition, then is it sufficient to produce 
identical results?

- fj

>

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Joseph S. Myers]

On Thu, 7 Oct 2004, Dale Johannesen wrote:

> Offhand it seems that the combination might be safe if C1 op C2 is
> representable, and  C1 and C2 both "move the result in the same direction",
> i.e. both absolute values >1 or both <1 for multiplication, both positive or
> both negative for addition and subtraction.  (Obviously it's OK if one of
> them is 0 but I assume this is handled elsewhere.)  Does this seem right?

A previous discussion of this sort of thing mentioned the case of x * 0.25 
== 0 but x * 0.5 == x so x * 0.5 * 0.5 != x * 0.25, for small x and 
rounding towards positive infinity with -frounding-math.

-- 
Joseph S. Myers               http://www.srcf.ucam.org/~jsm28/gcc/
    jsm@polyomino.org.uk (personal mail)
    joseph@codesourcery.com (CodeSourcery mail)
    jsm28@gcc.gnu.org (Bugzilla assignments and CCs)

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Dale Johannesen]

On Oct 7, 2004, at 3:10 PM, Joseph S. Myers wrote:
> On Thu, 7 Oct 2004, Dale Johannesen wrote:
>
>> Offhand it seems that the combination might be safe if C1 op C2 is
>> representable, and  C1 and C2 both "move the result in the same 
>> direction",
>> i.e. both absolute values >1 or both <1 for multiplication, both 
>> positive or
>> both negative for addition and subtraction.  (Obviously it's OK if 
>> one of
>> them is 0 but I assume this is handled elsewhere.)  Does this seem 
>> right?
>
> A previous discussion of this sort of thing mentioned the case of x * 
> 0.25
> == 0 but x * 0.5 == x so x * 0.5 * 0.5 != x * 0.25, for small x and
> rounding towards positive infinity with -frounding-math.

OK.  Did the previous discussion arrive at a rule for cases that *are* 
safe?

Adding Steve Peters, in Apple's numerics group, who understands this 
stuff.
Only fair since his bug report started the whole thing (3813473).  
Steve, the
issue is that people do not want to disallow folding
    (x op C1)  op C2
in cases where it safe to fold (for multiplication, C1==C2==2 has been
mentioned several times).  Can we identify such cases?
  

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Richard Henderson]

On Thu, Oct 07, 2004 at 02:58:53PM -0700, Dale Johannesen wrote:
> >It is possible that (X op C1) would overflow or lose precision
> >when the second form would not, even if (C1 op C2) is exactly
> >representable;  consider X and C1 very large, C2==1/C1.
> 
> Offhand it seems that the combination might be safe if C1 op C2 is
> representable, and  C1 and C2 both "move the result in the same 
> direction", i.e. both absolute values >1 or both <1 for multiplication,
> both positive or both negative for addition and subtraction.

Ho hum.

        0x3f000001 * 3 = 0x3fc00002
        0x3fc00002 * 3 = 0x40900002

        0x3f000001 * 9 = 0x40900001

So it looks like the only thing we can fold for multiply is
C2 a power of B, the base of the floating point format.

I've exhaustively tested 2 * 3 -> 6 for single precision, so I'm
certain I havn't made a mistake in intuition for that particular
case.  I can't see anything about how fp multiplication works 
that would contradict this -- the fraction doesn't change, so the
resultant fraction shouldn't change.  Only the exponent changes,
and if we verify "moves in the same direction" then we shouldn't
hit silly things with edge conditions.


r~

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Richard Henderson]

On Thu, Oct 07, 2004 at 10:10:57PM +0000, Joseph S. Myers wrote:
> A previous discussion of this sort of thing mentioned the case of x * 0.25 
> == 0 but x * 0.5 == x so x * 0.5 * 0.5 != x * 0.25, for small x and 
> rounding towards positive infinity with -frounding-math.

Hmm?  For what X does this hold?  I can't find one for floats.


r~

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Joseph S. Myers]

On Thu, 7 Oct 2004, Richard Henderson wrote:

> On Thu, Oct 07, 2004 at 10:10:57PM +0000, Joseph S. Myers wrote:
> > A previous discussion of this sort of thing mentioned the case of x * 0.25 
> > == 0 but x * 0.5 == x so x * 0.5 * 0.5 != x * 0.25, for small x and 
> > rounding towards positive infinity with -frounding-math.
> 
> Hmm?  For what X does this hold?  I can't find one for floats.

I can't find a reference to this discussion right now and I think it must 
have been some other rounding mode, but the idea was that half the 
smallest floating point value rounded to the same value but a quarter of 
it rounded to zero

-- 
Joseph S. Myers               http://www.srcf.ucam.org/~jsm28/gcc/
    jsm@polyomino.org.uk (personal mail)
    joseph@codesourcery.com (CodeSourcery mail)
    jsm28@gcc.gnu.org (Bugzilla assignments and CCs)

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Richard Henderson]

On Thu, Oct 07, 2004 at 11:18:34PM +0000, Joseph S. Myers wrote:
> I can't find a reference to this discussion right now and I think it must 
> have been some other rounding mode, but the idea was that half the 
> smallest floating point value rounded to the same value but a quarter of 
> it rounded to zero

I modified my test program to iterate through all of the rounding
modes, and still couldn't find such a case.

For the record, and in case someone can identify a bug that would
have caused this case to be missed, the test program follows.  I
ran the test program on ia64 to avoid any possibility of mucking
up with extended precision on x86.



r~



#include <fenv.h>

#define hide(x) \
  ({ __typeof (x) x_ = (x); asm ("" : "=frg"(x_) : "0"(x_)); x_; })

void test(void)
{
  int i;
  union {
    float f;
    int i;
  } u;

  for (i = 0; i < 1<<24; i++)
    {
      float f, t0, t1, t2;
      u.i = i;
      f = u.f;

      t0 = hide(f * 0.5f);
      t1 = hide(t0 * 0.5f);
      t2 = hide(f * 0.25f);

      if (t1 != t2)
	{
	  printf ("%.10a: %.10a != %.10a\n", f, t1, t2);
	  abort ();
	}
    }
}

int main()
{
  int r;

  for (r = 0; r < 4; ++r)
    {
      int m;
      switch (r)
	{
	case 0:
	  m = FE_TOWARDZERO;
	  break;
	case 1:
	  m = FE_DOWNWARD;
	  break;
	case 2:
	  m = FE_TONEAREST;
	  break;
	case 3:
	  m = FE_UPWARD;
	  break;
	}
      fesetround (m);
      test ();
    }

  return 0;
}

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Roger Sayle]

On Thu, 7 Oct 2004, Richard Henderson wrote:
> On Thu, Oct 07, 2004 at 11:18:34PM +0000, Joseph S. Myers wrote:
> > I can't find a reference to this discussion right now and I think it must
> > have been some other rounding mode, but the idea was that half the
> > smallest floating point value rounded to the same value but a quarter of
> > it rounded to zero
>
> I modified my test program to iterate through all of the rounding
> modes, and still couldn't find such a case.
>
> For the record, and in case someone can identify a bug that would
> have caused this case to be missed, the test program follows.  I
> ran the test program on ia64 to avoid any possibility of mucking
> up with extended precision on x86.

I think that converting (x * C1) * C2 into x * (C1 * C2) is "unsafe"
in IEEE arithmetic even if C1 and C2 are powers of two, and C1*C2 is
perfectly representable (as returned by real.c's do_multiply).
Consider C1 = 2.0, C2 = 0.5 and x = FLT_MAX.

Similar arguments hold for (X + C1) + C2 where C1 is 1.0 and C2 is -1.0,
and X is 1e-20.  Though I think MIN_EXPR and MAX_EXPR are always safe.

My feeling is that unless someone feels its worth going to effort of
implementing Dale's checks explicitly for multiplications by powers of
two with either both positive or both negative exponents, that we should
do what we've always done for floating point reassociation and guard it
with flag_unsafe_math_optimizations.

Yes, we loose optimization opportunities in many cases where operands
are valid, as pointed out by Geoff K., but the GCC philosophy has been
to preserve the behaviour of IEEE semantics for all possible operand
values by default.  Intel and Microsoft's compilers default to their
equivalent of -ffast-math, which should be used by anyone considering
running SPEC.

Reassociating any floating point operations in tree-ssa without testing
either flag_unsafe_math_optimizations or explicit detailed checks of
operand values is a regression from gcc 3.4.x and earlier releases.
Has anyone checked how "paranoia" performs on mainline since tree-ssa?

Roger
--

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Roger Sayle]

On Thu, 7 Oct 2004, Roger Sayle wrote:
> My feeling is that unless someone feels its worth going to effort of
> implementing Dale's checks explicitly for multiplications by powers of
> two with either both positive or both negative exponents, that we should
> do what we've always done for floating point reassociation and guard it
> with flag_unsafe_math_optimizations.

Thinking more about the necessary and sufficient conditions for
converting (x * C1) * C2 into x * (C1 * C2), I believe that it
is sufficent that the signs of the IEEE exponents match, and either
C1 or C2 is a power of two.

To counter one of RTH's recent suggestions that HONOR_INFINITIES
should be used instead of flag_unsafe_math_optimizations, it's easy
to show that swapping co-efficients (x * C1) * C2 where C1 = O.5,
C2 = 2.0 and x is epsilon, produces the same "exponent truncation"
but with underflow rather than overflow.  i.e. this isn't a infinity
specific restriction.

It should also be pointed out that with -fsignaling-nans, (x * C1) * C2
raises more floating point exceptions that x * (C1*C2), so reassociation
also has to be disallowed when flag_signaling_nans.

Once again, flag_unsafe_math_optimizations is the way its been done
in the past, and potentially the easiest way to fix the current
regressions.

Roger
--

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Roger Sayle]

Hi Fariborz,

Has this issue been filed as a PR in bugzilla yet?  I've just tried
some tests on mainline and I'm shocked at the unsafe transformations
being performed by the tree-ssa optimizers.

If you've not already done so, make sure this is targeted at 4.0.0
with critical priority (a potential show stopper), then to keep RTH
and Geoff K happy, also file a low priority enhancement request that
(X * 2.0) * 2.0 gets optimized.  The first is a severe regression from
all previous GCC releases, the latter isn't and possibly may not even
be suitable for stage3.  If it makes people more comfortable, feel free
to assign the enhancement request to me.  I wouldn't want either issue
to get lost.


My concern now is how much the performance benefits of the tree-ssa
merge were exagerated by the fact that we've been performing these
unsafe mathematical transformations.  Fixing this problem may hurt
our SPECfp2000 scores   :<

Roger
--

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Gabriel Dos Reis]

Roger Sayle <roger@eyesopen.com> writes:

| On Thu, 7 Oct 2004, Roger Sayle wrote:
| > My feeling is that unless someone feels its worth going to effort of
| > implementing Dale's checks explicitly for multiplications by powers of
| > two with either both positive or both negative exponents, that we should
| > do what we've always done for floating point reassociation and guard it
| > with flag_unsafe_math_optimizations.
| 
| Thinking more about the necessary and sufficient conditions for
| converting (x * C1) * C2 into x * (C1 * C2), I believe that it
| is sufficent that the signs of the IEEE exponents match, and either
| C1 or C2 is a power of two.

Are you sure?

Consider C1 == C2 == highest power of 2 in double.  Then, take
X == 1/C1.

| To counter one of RTH's recent suggestions that HONOR_INFINITIES
| should be used instead of flag_unsafe_math_optimizations, it's easy
| to show that swapping co-efficients (x * C1) * C2 where C1 = O.5,
| C2 = 2.0 and x is epsilon, produces the same "exponent truncation"
| but with underflow rather than overflow.  i.e. this isn't a infinity
| specific restriction.

Indeed.  

I do not understand why it is believed that this issue has to do with
only exceptions or infinities.

[...]

| Once again, flag_unsafe_math_optimizations is the way its been done
| in the past, and potentially the easiest way to fix the current
| regressions.

Completely agreed.

-- Gaby

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Gabriel Dos Reis]

Roger Sayle <roger@eyesopen.com> writes:

[...]

| My concern now is how much the performance benefits of the tree-ssa
| merge were exagerated by the fact that we've been performing these
| unsafe mathematical transformations.  Fixing this problem may hurt
| our SPECfp2000 scores   :<

he he :-)  That IS a bit cynical :-)

-- Gaby

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Geoff Keating]

[-- Attachment #1: Type: text/plain, Size: 237 bytes --]


On 07/10/2004, at 8:41 PM, Roger Sayle wrote:

> Fixing this problem may hurt our SPECfp2000 scores   :<

Only if you don't run SPECfp with -ffast-math.  (The SPEC rules appear 
to specifically allow the use of flags like -ffast-math.)

[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2410 bytes --]

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Fariborz Jahanian]

On Oct 7, 2004, at 7:37 PM, Roger Sayle wrote:

>
> On Thu, 7 Oct 2004, Richard Henderson wrote:
>> On Thu, Oct 07, 2004 at 11:18:34PM +0000, Joseph S. Myers wrote:
>>> I can't find a reference to this discussion right now and I think it 
>>> must
>>> have been some other rounding mode, but the idea was that half the
>>> smallest floating point value rounded to the same value but a 
>>> quarter of
>>> it rounded to zero
>>
>> I modified my test program to iterate through all of the rounding
>> modes, and still couldn't find such a case.
>>
>> For the record, and in case someone can identify a bug that would
>> have caused this case to be missed, the test program follows.  I
>> ran the test program on ia64 to avoid any possibility of mucking
>> up with extended precision on x86.
>
> I think that converting (x * C1) * C2 into x * (C1 * C2) is "unsafe"
> in IEEE arithmetic even if C1 and C2 are powers of two, and C1*C2 is
> perfectly representable (as returned by real.c's do_multiply).
> Consider C1 = 2.0, C2 = 0.5 and x = FLT_MAX.
>
> Similar arguments hold for (X + C1) + C2 where C1 is 1.0 and C2 is 
> -1.0,
> and X is 1e-20.  Though I think MIN_EXPR and MAX_EXPR are always safe.
>
> My feeling is that unless someone feels its worth going to effort of
> implementing Dale's checks explicitly for multiplications by powers of
> two with either both positive or both negative exponents, that we 
> should
> do what we've always done for floating point reassociation and guard it
> with flag_unsafe_math_optimizations.
>
> Yes, we loose optimization opportunities in many cases where operands
> are valid, as pointed out by Geoff K., but the GCC philosophy has been
> to preserve the behaviour of IEEE semantics for all possible operand
> values by default.  Intel and Microsoft's compilers default to their
> equivalent of -ffast-math, which should be used by anyone considering
> running SPEC.
>
> Reassociating any floating point operations in tree-ssa without testing
> either flag_unsafe_math_optimizations or explicit detailed checks of
> operand values is a regression from gcc 3.4.x and earlier releases.
> Has anyone checked how "paranoia" performs on mainline since tree-ssa?
>

Ditto. I may also note that this optimization was not intentionally 
added to fold-const.
It is a by product of code added to the tree-ssa side of things in 
routine
simplify_rhs_and_lookup_avail_expr. I would like to add, that there are
numerous other constant foldings which have been placed under 
flag_unsafe_math_optimizations.
In none of those cases  gcc goes out of its way to check for conditions 
which make it
safe to do the folding outside of flag_unsafe_math_optimizations, as is 
being suggested
by some in this thread. Let's also not forget about compile-time speed 
implication of such
rigorous checking.

- fariborz

> Roger
> --
>

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Fariborz Jahanian]

On Oct 7, 2004, at 8:41 PM, Roger Sayle wrote:

>
> Hi Fariborz,
>
> Has this issue been filed as a PR in bugzilla yet?  I've just tried
> some tests on mainline and I'm shocked at the unsafe transformations
> being performed by the tree-ssa optimizers.

I will file a PR.

>
> If you've not already done so, make sure this is targeted at 4.0.0
> with critical priority (a potential show stopper), then to keep RTH
> and Geoff K happy, also file a low priority enhancement request that

I am not sure how. I can check-in my change as the fix for regression 
and then
file a PR for enhancements as you suggested. But RTH considers (X 
*2.0)*2.0
not getting optimized as a regression and not an enhancement. I wait 
for a decision
before filing this other PR.

> (X * 2.0) * 2.0 gets optimized.  The first is a severe regression from
> all previous GCC releases, the latter isn't and possibly may not even
> be suitable for stage3.  If it makes people more comfortable, feel free
> to assign the enhancement request to me.  I wouldn't want either issue
> to get lost.
>
>
> My concern now is how much the performance benefits of the tree-ssa
> merge were exagerated by the fact that we've been performing these
> unsafe mathematical transformations.  Fixing this problem may hurt
> our SPECfp2000 scores   :<

We build SPECs (at least for apple-ppc-darwin with -fast-math).

- Fariborz

>
> Roger
> --
>

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Dale Johannesen]

On Oct 7, 2004, at 10:12 PM, Geoff Keating wrote:
> On 07/10/2004, at 8:41 PM, Roger Sayle wrote:
>
>> Fixing this problem may hurt our SPECfp2000 scores   :<
>
> Only if you don't run SPECfp with -ffast-math.  (The SPEC rules appear 
> to specifically allow the use of flags like -ffast-math.)

No.  The SPEC (2000) rules address the point specifically:

   2.2.5 Floating point reordering allowed

    Base results may use flags which affect the numerical accuracy or
    sensitivity by reordering floating-point operations based on 
algebraic
    identities.

Apple indeed uses -ffast-math for its SPEC results, and I expect 
everybody
else does too (they should be).    So whatever we do about this issue 
will
not affect SPEC.

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Dale Johannesen]

On Oct 8, 2004, at 10:23 AM, Dale Johannesen wrote:

> On Oct 7, 2004, at 10:12 PM, Geoff Keating wrote:
>> On 07/10/2004, at 8:41 PM, Roger Sayle wrote:
>>
>>> Fixing this problem may hurt our SPECfp2000 scores   :<
>>
>> Only if you don't run SPECfp with -ffast-math.  (The SPEC rules 
>> appear to specifically allow the use of flags like -ffast-math.)
>
> No.

Er, I mean yes, sorry, read that as "disallow" somehow.

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Richard Henderson]

On Thu, Oct 07, 2004 at 08:58:00PM -0600, Roger Sayle wrote:
> To counter one of RTH's recent suggestions that HONOR_INFINITIES
> should be used instead of flag_unsafe_math_optimizations...

That was not a suggestion, it was countering a previous
misstatement of a claim I made.


r~

Re: Patch gcc-4.0 should not apply mathematical associative rules for

[Kai Henningsen]

gdr@cs.tamu.edu (Gabriel Dos Reis)  wrote on 07.10.04 in <m3y8iiteaa.fsf@merlin.cs.tamu.edu>:

> Richard Henderson <rth@redhat.com> writes:
>
> | On Thu, Oct 07, 2004 at 03:49:45PM -0500, Gabriel Dos Reis wrote:
> | > Richard Henderson <rth@redhat.com> writes:
> | >
> | > | On Wed, Oct 06, 2004 at 05:05:08PM -0700, Fariborz Jahanian wrote:
> | > | >         * tree-ssa-dom.c (unsafe_associative_fp_binop): New
> | > | >         function. (simplify_rhs_and_lookup_avail_expr): Disallow
> | > | >         associativity and constant folding of floating point
> | > | >         MULT_EXPR/PLUS_EXPR expressions.
> | > |
> | > | If you apply this, I'll immediately file a PR for a regression
> | > | and assign it to you.
> | > |
> | > | You should allow
> | > |
> | > | 	X op C1 op C2
> | > | to combine to
> | > | 	X op C3
> | > |
> | > | if C1 op C2 is exactly representable.
> | >
> | > Only if C3 does not overflow, which is the root of the issue why this
> | > transformation is unsafe in general.
> |
> | Well, overflow is a subset of "not exactly representable", yes.
>
> Yes, but that was not the point I was making.
>
> | But more than that, (X * 0.3 * 3) would not be folded because bits
> | would be lost off the least-significant end.  Which is surely the
> | more serious folding error.
>
> My point was that it does not suffice that C1 and C2 be exactly
> representable, we also need C3 not to overflow.

Look above. The original statement was NOT "C1 and C2 are exactly  
representable". It was "C1 op C2 is exactly representable". Which, as  
Richard points out, includes that it does not overflow.

MfG Kai

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Fariborz Jahanian]

On Oct 7, 2004, at 8:41 PM, Roger Sayle wrote:

>
> Hi Fariborz,
>
> Has this issue been filed as a PR in bugzilla yet?  I've just tried
> some tests on mainline and I'm shocked at the unsafe transformations
> being performed by the tree-ssa optimizers.
>
> If you've not already done so, make sure this is targeted at 4.0.0
> with critical priority (a potential show stopper), then to keep RTH
> and Geoff K happy, also file a low priority enhancement request that
> (X * 2.0) * 2.0 gets optimized.  The first is a severe regression from

I filed PR/17892 (P1) to track the unsafe transformation. My patch is 
the
fix for this PR. If I file the 2nd PR for the enhancement request, is 
this OK
for every one?

- fariborz

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Geoffrey Keating]

Richard Henderson <rth@redhat.com> writes:

> On Thu, Oct 07, 2004 at 02:58:53PM -0700, Dale Johannesen wrote:
> > >It is possible that (X op C1) would overflow or lose precision
> > >when the second form would not, even if (C1 op C2) is exactly
> > >representable;  consider X and C1 very large, C2==1/C1.
> > 
> > Offhand it seems that the combination might be safe if C1 op C2 is
> > representable, and  C1 and C2 both "move the result in the same 
> > direction", i.e. both absolute values >1 or both <1 for multiplication,
> > both positive or both negative for addition and subtraction.
> 
> Ho hum.
> 
>         0x3f000001 * 3 = 0x3fc00002
>         0x3fc00002 * 3 = 0x40900002
> 
>         0x3f000001 * 9 = 0x40900001
> 
> So it looks like the only thing we can fold for multiply is
> C2 a power of B, the base of the floating point format.
> 
> I've exhaustively tested 2 * 3 -> 6 for single precision, so I'm
> certain I havn't made a mistake in intuition for that particular
> case.  I can't see anything about how fp multiplication works 
> that would contradict this -- the fraction doesn't change, so the
> resultant fraction shouldn't change.  Only the exponent changes,
> and if we verify "moves in the same direction" then we shouldn't
> hit silly things with edge conditions.

You can also do this if C1 is a power of B.

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Andrew Haley]

Richard Kenner writes:
 >     I think that converting (x * C1) * C2 into x * (C1 * C2) is "unsafe"
 >     in IEEE arithmetic even if C1 and C2 are powers of two, and C1*C2 is
 >     perfectly representable (as returned by real.c's do_multiply).
 >     Consider C1 = 2.0, C2 = 0.5 and x = FLT_MAX.
 > 
 > Is it really *required* to overflow if an intermediate result overflows but
 > the result of the entire operation is representable?

I think so.

F.7.1  Environment management

IEC 60559 requires that floating-point operations implicitly raise
floating-point exception status flags ... [when FENV_ACCESS ] is "on",
these changes to the floating-point state are treated as side-effects
with respect to sequence points.

Andrew.

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Richard Kenner]

    I think that converting (x * C1) * C2 into x * (C1 * C2) is "unsafe"
    in IEEE arithmetic even if C1 and C2 are powers of two, and C1*C2 is
    perfectly representable (as returned by real.c's do_multiply).
    Consider C1 = 2.0, C2 = 0.5 and x = FLT_MAX.

Is it really *required* to overflow if an intermediate result overflows but
the result of the entire operation is representable?  Certainly Ada allows
producing the "correct" result in that case and so the optimization is
valid.  Do the other language standards forbid it?

Re: Patch gcc-4.0 should not apply mathematical associative rules for addition or multiplication

[Roger Sayle]

On Tue, 5 Oct 2004, Gabriel Dos Reis wrote:
> | Here is the patch. It has been bootstrapped, dejagnu tested on
> | apple-ppc-darwin.
> |
> | OK for fsf mainline?
>
> Unless, you hear objections from Roger Sayle, I think it is OK with the
> caveat of renaming associative_fp_binop to unsafe_associative_fp_binop.

I have no objections.  Ok for mainline, by me.

Roger
--