Fix ancient wrong-code with ?: (PR middle-end/81814)

This PR is about wrong-code and has gone undetected for over 10 years (!).
The issue is that e.g. the following

  (signed char) x == 0 ? (unsigned long long) x : 0

was wrongly folded to 0, because fold_cond_expr_with_comparison will fold
A != 0 ? A : 0 to 0.  But for x = 0x01000000 this is wrong: (signed char) is 0,
but (unsigned long long) x is not.  The culprit is operand_equal_for_comparison_p
which contains shorten_compare-like code which says that the above is safe to
fold.  The code harks back to 1992 so I thought it worth to just get rid of it.

But I did some measurements and it turns out that substituting operand_equal_p
for operand_equal_for_comparison_p prevents folding ~60000 times in bootstrap.
So I feel uneasy about removing the function completely. Instead, I propose to
remove just the part that is causing trouble.  (Maybe I should also delete the
first call to operand_equal_p in operand_equal_for_comparison_p.)

Bootstrapped/regtested on x86_64-linux, ok for trunk?  What about 7?

2017-08-17  Marek Polacek  <polacek@redhat.com>

	PR middle-end/81814
	* fold-const.c (operand_equal_for_comparison_p): Remove code that used
	to mimic what shorten_compare did.  Change the return type to bool.
	(fold_cond_expr_with_comparison): Update call to
	operand_equal_for_comparison_p.
	(fold_ternary_loc): Likewise.

	* gcc.dg/torture/pr81814.c: New test.


	Marek

On Thu, 17 Aug 2017, Marek Polacek wrote:

> This PR is about wrong-code and has gone undetected for over 10 years (!).
> The issue is that e.g. the following
> 
>   (signed char) x == 0 ? (unsigned long long) x : 0
> 
> was wrongly folded to 0, because fold_cond_expr_with_comparison will fold
> A != 0 ? A : 0 to 0.  But for x = 0x01000000 this is wrong: (signed char) is 0,
> but (unsigned long long) x is not.  The culprit is operand_equal_for_comparison_p
> which contains shorten_compare-like code which says that the above is safe to
> fold.  The code harks back to 1992 so I thought it worth to just get rid of it.
> 
> But I did some measurements and it turns out that substituting operand_equal_p
> for operand_equal_for_comparison_p prevents folding ~60000 times in bootstrap.
> So I feel uneasy about removing the function completely. Instead, I propose to
> remove just the part that is causing trouble.  (Maybe I should also delete the
> first call to operand_equal_p in operand_equal_for_comparison_p.)
> 
> Bootstrapped/regtested on x86_64-linux, ok for trunk?  What about 7?

Ok for trunk.  Do you have numbers for this patch variant as well?

It seems that with some refactoring the remaining transforms should
be easily expressible as match.pd patterns now.

Richard.

> 2017-08-17  Marek Polacek  <polacek@redhat.com>
> 
> 	PR middle-end/81814
> 	* fold-const.c (operand_equal_for_comparison_p): Remove code that used
> 	to mimic what shorten_compare did.  Change the return type to bool.
> 	(fold_cond_expr_with_comparison): Update call to
> 	operand_equal_for_comparison_p.
> 	(fold_ternary_loc): Likewise.
> 
> 	* gcc.dg/torture/pr81814.c: New test.
> 
> diff --git gcc/fold-const.c gcc/fold-const.c
> index 0a5b168c320..fef9b1a707a 100644
> --- gcc/fold-const.c
> +++ gcc/fold-const.c
> @@ -113,7 +113,6 @@ static tree negate_expr (tree);
>  static tree associate_trees (location_t, tree, tree, enum tree_code, tree);
>  static enum comparison_code comparison_to_compcode (enum tree_code);
>  static enum tree_code compcode_to_comparison (enum comparison_code);
> -static int operand_equal_for_comparison_p (tree, tree, tree);
>  static int twoval_comparison_p (tree, tree *, tree *, int *);
>  static tree eval_subst (location_t, tree, tree, tree, tree, tree);
>  static tree optimize_bit_field_compare (location_t, enum tree_code,
> @@ -3365,60 +3364,27 @@ operand_equal_p (const_tree arg0, const_tree arg1, unsigned int flags)
>  #undef OP_SAME_WITH_NULL
>  }
>  
> -/* Similar to operand_equal_p, but see if ARG0 might have been made by
> -   shorten_compare from ARG1 when ARG1 was being compared with OTHER.
> +/* Similar to operand_equal_p, but strip nops first.  */
>  
> -   When in doubt, return 0.  */
> -
> -static int
> -operand_equal_for_comparison_p (tree arg0, tree arg1, tree other)
> +static bool
> +operand_equal_for_comparison_p (tree arg0, tree arg1)
>  {
> -  int unsignedp1, unsignedpo;
> -  tree primarg0, primarg1, primother;
> -  unsigned int correct_width;
> -
>    if (operand_equal_p (arg0, arg1, 0))
> -    return 1;
> +    return true;
>  
>    if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0))
>        || ! INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
> -    return 0;
> +    return false;
>  
>    /* Discard any conversions that don't change the modes of ARG0 and ARG1
>       and see if the inner values are the same.  This removes any
>       signedness comparison, which doesn't matter here.  */
> -  primarg0 = arg0, primarg1 = arg1;
> -  STRIP_NOPS (primarg0);
> -  STRIP_NOPS (primarg1);
> -  if (operand_equal_p (primarg0, primarg1, 0))
> -    return 1;
> -
> -  /* Duplicate what shorten_compare does to ARG1 and see if that gives the
> -     actual comparison operand, ARG0.
> -
> -     First throw away any conversions to wider types
> -     already present in the operands.  */
> -
> -  primarg1 = get_narrower (arg1, &unsignedp1);
> -  primother = get_narrower (other, &unsignedpo);
> -
> -  correct_width = TYPE_PRECISION (TREE_TYPE (arg1));
> -  if (unsignedp1 == unsignedpo
> -      && TYPE_PRECISION (TREE_TYPE (primarg1)) < correct_width
> -      && TYPE_PRECISION (TREE_TYPE (primother)) < correct_width)
> -    {
> -      tree type = TREE_TYPE (arg0);
> -
> -      /* Make sure shorter operand is extended the right way
> -	 to match the longer operand.  */
> -      primarg1 = fold_convert (signed_or_unsigned_type_for
> -			       (unsignedp1, TREE_TYPE (primarg1)), primarg1);
> -
> -      if (operand_equal_p (arg0, fold_convert (type, primarg1), 0))
> -	return 1;
> -    }
> +  STRIP_NOPS (arg0);
> +  STRIP_NOPS (arg1);
> +  if (operand_equal_p (arg0, arg1, 0))
> +    return true;
>  
> -  return 0;
> +  return false;
>  }
>  
>  /* See if ARG is an expression that is either a comparison or is performing
> @@ -5300,7 +5266,7 @@ fold_cond_expr_with_comparison (location_t loc, tree type,
>       expressions will be false, so all four give B.  The min()
>       and max() versions would give a NaN instead.  */
>    if (!HONOR_SIGNED_ZEROS (element_mode (type))
> -      && operand_equal_for_comparison_p (arg01, arg2, arg00)
> +      && operand_equal_for_comparison_p (arg01, arg2)
>        /* Avoid these transformations if the COND_EXPR may be used
>  	 as an lvalue in the C++ front-end.  PR c++/19199.  */
>        && (in_gimple_form
> @@ -11357,8 +11323,7 @@ fold_ternary_loc (location_t loc, enum tree_code code, tree type,
>  
>           Also try swapping the arguments and inverting the conditional.  */
>        if (COMPARISON_CLASS_P (arg0)
> -	  && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
> -					     arg1, TREE_OPERAND (arg0, 1))
> +	  && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0), arg1)
>  	  && !HONOR_SIGNED_ZEROS (element_mode (arg1)))
>  	{
>  	  tem = fold_cond_expr_with_comparison (loc, type, arg0, op1, op2);
> @@ -11367,9 +11332,7 @@ fold_ternary_loc (location_t loc, enum tree_code code, tree type,
>  	}
>  
>        if (COMPARISON_CLASS_P (arg0)
> -	  && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
> -					     op2,
> -					     TREE_OPERAND (arg0, 1))
> +	  && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0), op2)
>  	  && !HONOR_SIGNED_ZEROS (element_mode (op2)))
>  	{
>  	  location_t loc0 = expr_location_or (arg0, loc);
> diff --git gcc/testsuite/gcc.dg/torture/pr81814.c gcc/testsuite/gcc.dg/torture/pr81814.c
> index e69de29bb2d..aaf7c7f3041 100644
> --- gcc/testsuite/gcc.dg/torture/pr81814.c
> +++ gcc/testsuite/gcc.dg/torture/pr81814.c
> @@ -0,0 +1,36 @@
> +/* PR middle-end/81814 */
> +/* { dg-do run } */
> +
> +int
> +main ()
> +{
> +  int i = 0x01000000;
> +  int a;
> +
> +  a = ((signed char) i) != 0 ? 0 : (unsigned long long int) i;
> +  if (a != 0x01000000)
> +    __builtin_abort ();
> +  a = ((signed short int) i) != 0 ? 0 : (unsigned long long int) i;
> +  if (a != 0x01000000)
> +    __builtin_abort ();
> +  a = ((unsigned short int) i) != 0 ? 0 : (unsigned long long int) i;
> +  if (a != 0x01000000)
> +    __builtin_abort ();
> +  a = ((unsigned char) i) != 0 ? 0 : (unsigned long long int) i;
> +  if (a != 0x01000000)
> +    __builtin_abort ();
> +  a = ((signed char) i) == 0 ? (unsigned long long int) i : 0;
> +  if (a != 0x01000000)
> +    __builtin_abort ();
> +  a = ((signed short int) i) == 0 ? (unsigned long long int) i : 0;
> +  if (a != 0x01000000)
> +    __builtin_abort ();
> +  a = ((unsigned short int) i) == 0 ? (unsigned long long int) i : 0;
> +  if (a != 0x01000000)
> +    __builtin_abort ();
> +  a = ((unsigned char) i) == 0 ? (unsigned long long int) i : 0;
> +  if (a != 0x01000000)
> +    __builtin_abort ();
> +
> +  return 0;
> +}
> 
> 	Marek
> 
>

On Thu, Aug 17, 2017 at 04:17:54PM +0200, Richard Biener wrote:
> On Thu, 17 Aug 2017, Marek Polacek wrote:
> 
> > This PR is about wrong-code and has gone undetected for over 10 years (!).
> > The issue is that e.g. the following
> > 
> >   (signed char) x == 0 ? (unsigned long long) x : 0
> > 
> > was wrongly folded to 0, because fold_cond_expr_with_comparison will fold
> > A != 0 ? A : 0 to 0.  But for x = 0x01000000 this is wrong: (signed char) is 0,
> > but (unsigned long long) x is not.  The culprit is operand_equal_for_comparison_p
> > which contains shorten_compare-like code which says that the above is safe to
> > fold.  The code harks back to 1992 so I thought it worth to just get rid of it.
> > 
> > But I did some measurements and it turns out that substituting operand_equal_p
> > for operand_equal_for_comparison_p prevents folding ~60000 times in bootstrap.
> > So I feel uneasy about removing the function completely. Instead, I propose to
> > remove just the part that is causing trouble.  (Maybe I should also delete the
> > first call to operand_equal_p in operand_equal_for_comparison_p.)
> > 
> > Bootstrapped/regtested on x86_64-linux, ok for trunk?  What about 7?
> 
> Ok for trunk.  Do you have numbers for this patch variant as well?

Thanks.  Yeah, I've gathered some, too.  This patch prevents calling
fold_cond_expr_with_comparison that would end up with non-NULL_TREE result
8322 times (all Ada files), this is the 
11325       if (COMPARISON_CLASS_P (arg0)
11326           && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0), arg1)
11327           && !HONOR_SIGNED_ZEROS (element_mode (arg1)))
case; plus 648 times in the 
11334       if (COMPARISON_CLASS_P (arg0)
11335           && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0), op2)
11336           && !HONOR_SIGNED_ZEROS (element_mode (op2)))
case (and a lot of that is coming from libgfortran/generated/*.c and reload.c).

> It seems that with some refactoring the remaining transforms should
> be easily expressible as match.pd patterns now.

That'd be great.

	Marek

On Thu, 17 Aug 2017, Marek Polacek wrote:

> On Thu, Aug 17, 2017 at 04:17:54PM +0200, Richard Biener wrote:
> > On Thu, 17 Aug 2017, Marek Polacek wrote:
> > 
> > > This PR is about wrong-code and has gone undetected for over 10 years (!).
> > > The issue is that e.g. the following
> > > 
> > >   (signed char) x == 0 ? (unsigned long long) x : 0
> > > 
> > > was wrongly folded to 0, because fold_cond_expr_with_comparison will fold
> > > A != 0 ? A : 0 to 0.  But for x = 0x01000000 this is wrong: (signed char) is 0,
> > > but (unsigned long long) x is not.  The culprit is operand_equal_for_comparison_p
> > > which contains shorten_compare-like code which says that the above is safe to
> > > fold.  The code harks back to 1992 so I thought it worth to just get rid of it.
> > > 
> > > But I did some measurements and it turns out that substituting operand_equal_p
> > > for operand_equal_for_comparison_p prevents folding ~60000 times in bootstrap.
> > > So I feel uneasy about removing the function completely. Instead, I propose to
> > > remove just the part that is causing trouble.  (Maybe I should also delete the
> > > first call to operand_equal_p in operand_equal_for_comparison_p.)
> > > 
> > > Bootstrapped/regtested on x86_64-linux, ok for trunk?  What about 7?
> > 
> > Ok for trunk.  Do you have numbers for this patch variant as well?
> 
> Thanks.  Yeah, I've gathered some, too.  This patch prevents calling
> fold_cond_expr_with_comparison that would end up with non-NULL_TREE result
> 8322 times (all Ada files), this is the 
> 11325       if (COMPARISON_CLASS_P (arg0)
> 11326           && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0), arg1)
> 11327           && !HONOR_SIGNED_ZEROS (element_mode (arg1)))
> case; plus 648 times in the 
> 11334       if (COMPARISON_CLASS_P (arg0)
> 11335           && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0), op2)
> 11336           && !HONOR_SIGNED_ZEROS (element_mode (op2)))
> case (and a lot of that is coming from libgfortran/generated/*.c and reload.c).

So you should be able to extract a C testcase?  I suspect sth like

  long foo (long x, int y)
  {
    return y > x ? y : x;
  }

to no longer be folded to return MAX_EXPR (x, (long) y).

That would be a shame btw.

Richard.

> 
> > It seems that with some refactoring the remaining transforms should
> > be easily expressible as match.pd patterns now.
> 
> That'd be great.
> 
> 	Marek
> 
>

On Thu, Aug 17, 2017 at 04:36:02PM +0200, Richard Biener wrote:
> On Thu, 17 Aug 2017, Marek Polacek wrote:
> 
> > On Thu, Aug 17, 2017 at 04:17:54PM +0200, Richard Biener wrote:
> > > On Thu, 17 Aug 2017, Marek Polacek wrote:
> > > 
> > > > This PR is about wrong-code and has gone undetected for over 10 years (!).
> > > > The issue is that e.g. the following
> > > > 
> > > >   (signed char) x == 0 ? (unsigned long long) x : 0
> > > > 
> > > > was wrongly folded to 0, because fold_cond_expr_with_comparison will fold
> > > > A != 0 ? A : 0 to 0.  But for x = 0x01000000 this is wrong: (signed char) is 0,
> > > > but (unsigned long long) x is not.  The culprit is operand_equal_for_comparison_p
> > > > which contains shorten_compare-like code which says that the above is safe to
> > > > fold.  The code harks back to 1992 so I thought it worth to just get rid of it.
> > > > 
> > > > But I did some measurements and it turns out that substituting operand_equal_p
> > > > for operand_equal_for_comparison_p prevents folding ~60000 times in bootstrap.
> > > > So I feel uneasy about removing the function completely. Instead, I propose to
> > > > remove just the part that is causing trouble.  (Maybe I should also delete the
> > > > first call to operand_equal_p in operand_equal_for_comparison_p.)
> > > > 
> > > > Bootstrapped/regtested on x86_64-linux, ok for trunk?  What about 7?
> > > 
> > > Ok for trunk.  Do you have numbers for this patch variant as well?
> > 
> > Thanks.  Yeah, I've gathered some, too.  This patch prevents calling
> > fold_cond_expr_with_comparison that would end up with non-NULL_TREE result
> > 8322 times (all Ada files), this is the 
> > 11325       if (COMPARISON_CLASS_P (arg0)
> > 11326           && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0), arg1)
> > 11327           && !HONOR_SIGNED_ZEROS (element_mode (arg1)))
> > case; plus 648 times in the 
> > 11334       if (COMPARISON_CLASS_P (arg0)
> > 11335           && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0), op2)
> > 11336           && !HONOR_SIGNED_ZEROS (element_mode (op2)))
> > case (and a lot of that is coming from libgfortran/generated/*.c and reload.c).
> 
> So you should be able to extract a C testcase?  I suspect sth like
> 
>   long foo (long x, int y)
>   {
>     return y > x ? y : x;
>   }
> 
> to no longer be folded to return MAX_EXPR (x, (long) y).

This is still folded to return MAX_EXPR <(long int) y, x>; so that's fine.
It's got to be something more complex that will not be handled now.  I'll
look tomorrow for a testcase.

	Marek

> So you should be able to extract a C testcase?  I suspect sth like
> 
>   long foo (long x, int y)
>   {
>     return y > x ? y : x;
>   }
> 
> to no longer be folded to return MAX_EXPR (x, (long) y).
> 
> That would be a shame btw.

Any news on this?  We're having regressions in Ada because of that, e.g.

  for U'Object_Size use 17179869280;
 -for U'Value_Size use  (((((#1 max 0) + 11) & -4) + 4) * 8) ;
 +for U'Value_Size use  (((((if (#1 > 0) then #1 else 0 end) + 11) & -4) + 4) 
* 8) ;
  for U'Alignment use 4;

which means that COND_EXPR is no longer turned into MAX_EXPR in TYPE_SIZE.

On Thu, 31 Aug 2017, Eric Botcazou wrote:

> > So you should be able to extract a C testcase?  I suspect sth like
> > 
> >   long foo (long x, int y)
> >   {
> >     return y > x ? y : x;
> >   }
> > 
> > to no longer be folded to return MAX_EXPR (x, (long) y).
> > 
> > That would be a shame btw.

Just checked and the above is still folded.

> Any news on this?  We're having regressions in Ada because of that, e.g.
> 
>   for U'Object_Size use 17179869280;
>  -for U'Value_Size use  (((((#1 max 0) + 11) & -4) + 4) * 8) ;
>  +for U'Value_Size use  (((((if (#1 > 0) then #1 else 0 end) + 11) & -4) + 4) 
> * 8) ;
>   for U'Alignment use 4;
> 
> which means that COND_EXPR is no longer turned into MAX_EXPR in TYPE_SIZE.

Can you file a bugreport and include a testcase for gnat.dg so that
we can reproduce?  Bonus points if you manage to create a C testcase
of course ;)

Richard.

> Can you file a bugreport and include a testcase for gnat.dg so that
> we can reproduce?  Bonus points if you manage to create a C testcase
> of course ;)

How can I collect them exactly? ;-)

unsigned long foo (int x)
{
  return x > 0 ? (unsigned long) x : 0UL;
}

On x86-64/Linux with GCC 7.2.1, the t.c.003t.original dump contains:

;; Function foo (null)
;; enabled by -tree-original


{
  return (long unsigned int) MAX_EXPR <x, 0>;
}

With mainline, it contains:

;; Function foo (null)
;; enabled by -tree-original


{
  return x > 0 ? (long unsigned int) x : 0;
}