[PATCH][RFC] Fix PR57656

[Richard Biener <rguenther at suse dot de>]

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?

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;
+ }