[PATCH] Fix PR27116, rework negate_expr_p/negate_expr

[Richard Guenther <rguenther at suse dot de>]

This patch fixes PR27116 for real by rewoking negate_expr_p to avoid
introducing undefined overflow.  It splits a generic fold_negate_expr
from negate_expr that can be used in fold_unary, fixing a latent problem
with RSHIFT_EXPR folding which didn't get noticed because fold_unary
passed a tree with stripped types to negate_expr (this problem is latent
on the branches).  With this patch I also revert the folding parts of
the first fix for PR27116, as these are not necessary.

The patch is big enough as is, but as a followup I will try to remove
the second argument to fold_negate_expr and put the burden of stripping
type conversions and re-applying them afterwards to the caller as other
fold_* variants do.  But I think this is not appropriate for 4.2 and has
to wait for stage1.

Bootstrapped and tested on x86_64-unknown-linux-gnu for all languages
including Ada.

Ok for mainline?  Ok to fix the latent problem on the branch(es) as
obvious?

Thanks,
Richard.

:ADDPATCH middle-end:

2006-06-09  Richard Guenther  <rguenther@suse.de>

	PR middle-end/27116
	* fold-const.c (negate_expr_p): Do not introduce undefined
	overflow in negating INTEGER_CSTs.
	(fold_negate_expr): Rename from negate_expr.  Revert last
	change for folding BIT_NOT_EXPR.  Change semantics to
	return NULL_TREE for non-simplified negations.  Fix latent
	problem in folding of -RSHIFT_EXPR.
	(negate_expr): New function, wrap around fold_negate_expr
	but ensure building a tree always.
	(fold_unary): Use fold_negate_expr for folding NEGATE_EXPR.

	* gcc.dg/pr15785-1.c: Revert last change.
	* gcc.dg/torture/pr27116-2.c: New testcase.


Index: fold-const.c
===================================================================
*** fold-const.c	(revision 114506)
--- fold-const.c	(working copy)
*************** may_negate_without_overflow_p (tree t)
*** 923,929 ****
  }
  
  /* Determine whether an expression T can be cheaply negated using
!    the function negate_expr.  */
  
  static bool
  negate_expr_p (tree t)
--- 923,929 ----
  }
  
  /* Determine whether an expression T can be cheaply negated using
!    the function negate_expr without introducing undefined overflow.  */
  
  static bool
  negate_expr_p (tree t)
*************** negate_expr_p (tree t)
*** 939,945 ****
    switch (TREE_CODE (t))
      {
      case INTEGER_CST:
!       if (TYPE_UNSIGNED (type) || ! flag_trapv)
  	return true;
  
        /* Check that -CST will not overflow type.  */
--- 939,946 ----
    switch (TREE_CODE (t))
      {
      case INTEGER_CST:
!       if (TYPE_UNSIGNED (type)
! 	  || (flag_wrapv && ! flag_trapv))
  	return true;
  
        /* Check that -CST will not overflow type.  */
*************** negate_expr_p (tree t)
*** 1030,1057 ****
    return false;
  }
  
! /* Given T, an expression, return the negation of T.  Allow for T to be
!    null, in which case return null.  */
  
  static tree
! negate_expr (tree t)
  {
-   tree type;
    tree tem;
  
-   if (t == 0)
-     return 0;
- 
-   type = TREE_TYPE (t);
-   STRIP_SIGN_NOPS (t);
- 
    switch (TREE_CODE (t))
      {
      /* Convert - (~A) to A + 1.  */
      case BIT_NOT_EXPR:
!       if (INTEGRAL_TYPE_P (type)
!       	  && (TYPE_UNSIGNED (type)
! 	      || (flag_wrapv && !flag_trapv)))
          return fold_build2 (PLUS_EXPR, type, TREE_OPERAND (t, 0),
                              build_int_cst (type, 1));
        break;
--- 1031,1052 ----
    return false;
  }
  
! /* Given T, an expression, return a folded tree representing
!    (TYPE)-T, the negation of T converted to TYPE, or NULL_TREE, if no
!    simplification is possible.
!    If negate_expr_p would return true for T, NULL_TREE will never be
!    returned.  */
  
  static tree
! fold_negate_expr (tree type, tree t)
  {
    tree tem;
  
    switch (TREE_CODE (t))
      {
      /* Convert - (~A) to A + 1.  */
      case BIT_NOT_EXPR:
!       if (INTEGRAL_TYPE_P (type))
          return fold_build2 (PLUS_EXPR, type, TREE_OPERAND (t, 0),
                              build_int_cst (type, 1));
        break;
*************** negate_expr (tree t)
*** 1201,1207 ****
  	      && (unsigned HOST_WIDE_INT) (TYPE_PRECISION (type) - 1)
  		 == TREE_INT_CST_LOW (op1))
  	    {
! 	      tree ntype = TYPE_UNSIGNED (type)
  			   ? lang_hooks.types.signed_type (type)
  			   : lang_hooks.types.unsigned_type (type);
  	      tree temp = fold_convert (ntype, TREE_OPERAND (t, 0));
--- 1196,1202 ----
  	      && (unsigned HOST_WIDE_INT) (TYPE_PRECISION (type) - 1)
  		 == TREE_INT_CST_LOW (op1))
  	    {
! 	      tree ntype = TYPE_UNSIGNED (TREE_TYPE (t))
  			   ? lang_hooks.types.signed_type (type)
  			   : lang_hooks.types.unsigned_type (type);
  	      tree temp = fold_convert (ntype, TREE_OPERAND (t, 0));
*************** negate_expr (tree t)
*** 1215,1221 ****
        break;
      }
  
!   tem = fold_build1 (NEGATE_EXPR, TREE_TYPE (t), t);
    return fold_convert (type, tem);
  }
  
--- 1210,1238 ----
        break;
      }
  
!   return NULL_TREE;
! }
! 
! /* Like fold_negate_expr, but return a NEGATE_EXPR tree, if T can not be
!    negated in a simpler way.  Also allow for T to be NULL_TREE, in which case
!    return NULL_TREE. */
! 
! static tree
! negate_expr (tree t)
! {
!   tree type, tem;
! 
!   if (t == NULL_TREE)
!     return NULL_TREE;
! 
!   type = TREE_TYPE (t);
!   STRIP_SIGN_NOPS (t);
! 
!   tem = fold_negate_expr (type, t);
!   if (tem)
!     return tem;
! 
!   tem = build1 (NEGATE_EXPR, TREE_TYPE (t), t);
    return fold_convert (type, tem);
  }
  
*************** fold_unary (enum tree_code code, tree ty
*** 7521,7529 ****
        return fold_view_convert_expr (type, op0);
  
      case NEGATE_EXPR:
!       if (negate_expr_p (arg0))
! 	return fold_convert (type, negate_expr (arg0));
!       return NULL_TREE;
  
      case ABS_EXPR:
        if (TREE_CODE (arg0) == INTEGER_CST || TREE_CODE (arg0) == REAL_CST)
--- 7538,7544 ----
        return fold_view_convert_expr (type, op0);
  
      case NEGATE_EXPR:
!       return fold_negate_expr (type, arg0);
  
      case ABS_EXPR:
        if (TREE_CODE (arg0) == INTEGER_CST || TREE_CODE (arg0) == REAL_CST)
Index: testsuite/gcc.dg/pr15785-1.c
===================================================================
*** testsuite/gcc.dg/pr15785-1.c	(revision 114483)
--- testsuite/gcc.dg/pr15785-1.c	(working copy)
*************** void b (int x) {
*** 11,16 ****
--- 11,21 ----
  		link_error ();
  }
  
+ void c (int x) {
+ 	if (!(- (~x) - x))
+ 		link_error ();
+ }
+ 
  void d (int x) {
  	if (!(~ (-x) - x))
  		link_error ();
*************** void f (int x) {
*** 29,34 ****
--- 34,40 ----
  int main (int argc, char *argv[]) {
  	a(argc);
  	b(argc);
+ 	c(argc);
  	d(argc);
  	e(argc);
  	f(argc);
Index: testsuite/gcc.dg/torture/pr27116-2.c
===================================================================
*** testsuite/gcc.dg/torture/pr27116-2.c	(revision 0)
--- testsuite/gcc.dg/torture/pr27116-2.c	(revision 0)
***************
*** 0 ****
--- 1,13 ----
+ /* { dg-do run } */
+ 
+ extern void abort(void);
+ 
+ int main (void)
+ {
+     volatile long int n;
+     n = -2;
+ 
+     if ((-2147483647L - 1L) / (-n) != -1073741824L)
+ 	abort ();
+     return 0;
+ }