Re: [PATCH][RFC] Fix PR57656

[Richard Biener <rguenther at suse dot de>]

On Mon, 24 Jun 2013, Richard Biener wrote:

> 
> This fixes the miscompile in PR57656 - folding of
> 
>   int t = 1 - (a - b) / c;
> 
> to
> 
>   int t = (b - a) / c + 1;
> 
> which introduces intermediate undefined overflow for
> a == -1 and b == INT_MAX.
> 
> There seems to be a mix of assumptions of the context
> negate_expr_p is called in - for example the comments
> and the code suggests that when checking whether
> negate_expr_p (A - B) is true then we assume there
> is a user-written - (A - B) expression (and thus
> we'll at most remove an overflow).  But we happily
> recurse for binary operands (which means re-associating
> the negate with the operation) for multiplications
> and divisions.  Considering - ((A - B) * C) then the
> folding to (B - A) * C _introduces_ an intermediate
> overflow if C is zero and A == -1 and B == INT_MAX.
> So with the notion that the input is always a negation
> present in user code the recursion is wrong.  And
> if not, then at least the MINUS_EXPR case is wrong.
> 
> For maximum benefit the API should probably be split
> so that it specifies whether there is a negation in
> place that we want to remove or not which we then
> can use for the recursion.
> 
> Anyway - here is a patch that fixes the testcase by
> simply avoiding the recursion in the division case,
> handling only two obvious cases as any re-org as
> outlined above is certainly not good for backporting.
> (and a re-org attempt should probably try to unify
> the three functions negate_expr_p, negate_expr and
> fold_negate_expr again)
> 
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
> 
> Any comments?  Is the patch below ok for trunk and branches
> in the mean time?

Re-bootstrapped and tested on x86_64-unknown-linux-gnu and
committed on trunk sofar.

Richard.

> 
> Thanks,
> Richard.
> 
> 2013-06-24  Richard Biener  <rguenther@suse.de>
> 
> 	PR middle-end/57656
> 	* fold-const.c (negate_expr_p): Fix division case.
> 	(negate_expr): Likewise.
> 
> 	* gcc.dg/torture/pr57656.c: New testcase.
> 
> Index: gcc/fold-const.c
> ===================================================================
> *** gcc/fold-const.c	(revision 200363)
> --- gcc/fold-const.c	(working copy)
> *************** negate_expr_p (tree t)
> *** 483,493 ****
>   	 and actually traps on some architectures.  But if overflow is
>   	 undefined, we can negate, because - (INT_MIN / 1) is an
>   	 overflow.  */
> !       if (INTEGRAL_TYPE_P (TREE_TYPE (t))
> ! 	  && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (t)))
> !         break;
> !       return negate_expr_p (TREE_OPERAND (t, 1))
> !              || negate_expr_p (TREE_OPERAND (t, 0));
>   
>       case NOP_EXPR:
>         /* Negate -((double)float) as (double)(-float).  */
> --- 483,506 ----
>   	 and actually traps on some architectures.  But if overflow is
>   	 undefined, we can negate, because - (INT_MIN / 1) is an
>   	 overflow.  */
> !       if (INTEGRAL_TYPE_P (TREE_TYPE (t)))
> ! 	{
> ! 	  if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (t)))
> ! 	    break;
> ! 	  /* If overflow is undefined then we have to be careful because
> ! 	     we ask whether it's ok to associate the negate with the
> ! 	     division which is not ok for example for
> ! 	     -((a - b) / c) where (-(a - b)) / c may invoke undefined
> ! 	     overflow because of negating INT_MIN.  So do not use
> ! 	     negate_expr_p here but open-code the two important cases.  */
> ! 	  if (TREE_CODE (TREE_OPERAND (t, 0)) == NEGATE_EXPR
> ! 	      || (TREE_CODE (TREE_OPERAND (t, 0)) == INTEGER_CST
> ! 		  && may_negate_without_overflow_p (TREE_OPERAND (t, 0))))
> ! 	    return true;
> ! 	}
> !       else if (negate_expr_p (TREE_OPERAND (t, 0)))
> ! 	return true;
> !       return negate_expr_p (TREE_OPERAND (t, 1));
>   
>       case NOP_EXPR:
>         /* Negate -((double)float) as (double)(-float).  */
> *************** fold_negate_expr (location_t loc, tree t
> *** 682,697 ****
>   	      return fold_build2_loc (loc, TREE_CODE (t), type,
>   				  TREE_OPERAND (t, 0), negate_expr (tem));
>   	    }
>             tem = TREE_OPERAND (t, 0);
> !           if (negate_expr_p (tem))
> ! 	    {
> ! 	      if (INTEGRAL_TYPE_P (type)
> ! 		  && (TREE_CODE (tem) != INTEGER_CST
> ! 		      || tree_int_cst_equal (tem, TYPE_MIN_VALUE (type))))
> ! 		fold_overflow_warning (warnmsg, WARN_STRICT_OVERFLOW_MISC);
> ! 	      return fold_build2_loc (loc, TREE_CODE (t), type,
> ! 				  negate_expr (tem), TREE_OPERAND (t, 1));
> ! 	    }
>           }
>         break;
>   
> --- 695,714 ----
>   	      return fold_build2_loc (loc, TREE_CODE (t), type,
>   				  TREE_OPERAND (t, 0), negate_expr (tem));
>   	    }
> + 	  /* If overflow is undefined then we have to be careful because
> + 	     we ask whether it's ok to associate the negate with the
> + 	     division which is not ok for example for
> + 	     -((a - b) / c) where (-(a - b)) / c may invoke undefined
> + 	     overflow because of negating INT_MIN.  So do not use
> + 	     negate_expr_p here but open-code the two important cases.  */
>             tem = TREE_OPERAND (t, 0);
> ! 	  if ((INTEGRAL_TYPE_P (type)
> ! 	       && (TREE_CODE (tem) == NEGATE_EXPR
> ! 		   || (TREE_CODE (tem) == INTEGER_CST
> ! 		       && may_negate_without_overflow_p (tem))))
> ! 	      || !INTEGRAL_TYPE_P (type))
> ! 	    return fold_build2_loc (loc, TREE_CODE (t), type,
> ! 				    negate_expr (tem), TREE_OPERAND (t, 1));
>           }
>         break;
>   
> Index: gcc/testsuite/gcc.dg/torture/pr57656.c
> ===================================================================
> *** gcc/testsuite/gcc.dg/torture/pr57656.c	(revision 0)
> --- gcc/testsuite/gcc.dg/torture/pr57656.c	(working copy)
> ***************
> *** 0 ****
> --- 1,13 ----
> + /* { dg-do run } */
> + /* { dg-options "-fstrict-overflow" } */
> + 
> + int main (void)
> + {
> +   int a = -1;
> +   int b = __INT_MAX__;
> +   int c = 2;
> +   int t = 1 - ((a - b) / c);  // t = 1 - ( __INT_MIN__ / 2 )
> +   if (t != (1 - (-1 - __INT_MAX__) / 2))
> +     __builtin_abort();
> +   return 0;
> + }
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend