[PATCH][no-undefined-overflow] Teach VRP to produce *NV_EXPR, fix unsigned overflow detection in int_const_binop

[Richard Guenther <rguenther at suse dot de>]

Teaching VRP to produce *NV_EXPR at substitution time revealed some issues
with detection of unsigned integer overflow (which is required to function
correctly for some of the earlier fold patches as well).

Basically we are unable to detect overflow of 1u + -1u (and similar 
cases).  This is because add_double_with_sign for unsigned math does

    if (unsigned_p)
!     return (unsigned HOST_WIDE_INT) h < (unsigned HOST_WIDE_INT) h1;

but this is obviously not sufficient for equal h, h1.  Likewise we get
wrong overflow reporting from

      case MINUS_EXPR:
      case MINUSNV_EXPR:
        neg_double (int2l, int2h, &low, &hi);
        add_double (int1l, int1h, low, hi, &low, &hi);
!       overflow = OVERFLOW_SUM_SIGN (hi, int2h, int1h);
        break;

for the same reason.  For multiplication we better pass the sign as well.

Fixing this causes extra diagnostics for

void *foo[] = {};

as stor-layout.c computes the TYPE_SIZE as

            /* The initial subtraction should happen in the original type so
               that (possible) negative values are handled appropriately.  */
            length = size_binop (PLUS_EXPR, size_one_node,
                                 fold_convert (sizetype,
                                               fold_build2 (MINUS_EXPR,
                                                            TREE_TYPE (lb),
                                                            ub, lb)));

which has TREE_OVERFLOW set because we end up subtracting 1 from 0.  Thus
the ugly fixup.

It seems that while Ada folks think that sizetype arithmetic should not
overflow we make extra sure to include sizetype in the case of

        or OVERFLOWABLE is >0 and signed overflow occurs

for force_fit_type_double.  Which of course confuses me again about
sizetype.  In int_const_binop we call force_fit_type_double as

    t = force_fit_type_double (TREE_TYPE (arg1), low, hi, 1,
                               ((!uns || is_sizetype) && overflow)
                               | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2));

thus explicitly including sizetypes to get TREE_OVERFLOW always on
overflow.

Well, the stor-layout.c case seems to be the only necessary workaround
for this sofar, so I went ahead and installed the following patch.

Bootstrapped and tested on x86_64-unknown-linux-gnu for all lanugages
including Ada and obj-c++.

There are a bunch of new regressions (vectorizer and parloops, all
probably because they do not deal with unsigned *NV_EXPRs either).

Thanks,
Richard.

2009-03-09  Richard Guenther  <rguenther@suse.de>

	* tree.h (int_const_binop_1): Declare.
	* fold-const.c (add_double_with_sign): Fix unsigned overflow
	detection.
	(int_const_binop_1): Export.  Fix unsigned overflow detection.
	* stor-layout.c (layout_type): Drop TREE_OVERFLOW on TYPE_SIZE
	if appropriate.
	* tree-vrp.c (integral_range_p): New helper.
	(simplify_unary_for_nonwrapping): Likewise.
	(simplify_binary_for_nonwrapping): Likewise.
	(simplify_stmt_using_ranges): Call them.

Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c	(revision 144693)
--- gcc/tree-vrp.c	(working copy)
*************** simplify_switch_using_ranges (gimple stm
*** 6922,6927 ****
--- 6922,7053 ----
    return false;
  }
  
+ /* Return true if VR is a completely determined value-range with
+    constant bounds.  */
+ 
+ static bool
+ integral_range_p (value_range_t *vr)
+ {
+   if (vr->type != VR_RANGE
+       || TREE_CODE (vr->min) != INTEGER_CST
+       || TREE_CODE (vr->max) != INTEGER_CST
+       || is_overflow_infinity (vr->min)
+       || is_overflow_infinity (vr->max))
+     return false;
+   return true;
+ }
+ 
+ /* Simplify STMT and replace possibly wrapping operation codes with
+    non-wrapping ones if we can proved the operation does not wrap.  */
+ 
+ static bool
+ simplify_unary_for_nonwrapping (gimple stmt)
+ {
+   value_range_t *vr1 = get_value_range (gimple_assign_rhs1 (stmt));
+   enum tree_code code = gimple_assign_rhs_code (stmt);
+   tree type = gimple_expr_type (stmt);
+   tree tmp;
+ 
+   switch (code)
+     {
+     case NEGATE_EXPR:
+       /* Unsigned negate always wraps unless it operates on constant zero,
+ 	 which we better catched elsewhere.  Signed negate does not wrap
+ 	 if the range it operates on does not include the types minimal
+ 	 value.  */
+       if (!TYPE_UNSIGNED (type)
+ 	  && (tmp = compare_range_with_value (NE_EXPR, vr1,
+ 					      vrp_val_min (type), NULL))
+ 	  && integer_onep (tmp))
+ 	{
+ 	  gimple_assign_set_rhs_code (stmt, NEGATENV_EXPR);
+ 	  return true;
+ 	}
+       break;
+ 
+     default:
+       ;
+     }
+ 
+   return false;
+ }
+ 
+ /* Simplify STMT and replace possibly wrapping operation codes with
+    non-wrapping ones if we can proved the operation does not wrap.  */
+ 
+ static bool
+ simplify_binary_for_nonwrapping (gimple stmt)
+ {
+   value_range_t dvr;
+   value_range_t *vr1;
+   value_range_t *vr2;
+   enum tree_code code = gimple_assign_rhs_code (stmt);
+   tree type = gimple_expr_type (stmt);
+   unsigned HOST_WIDE_INT low;
+   HOST_WIDE_INT hi;
+ 
+   if (TREE_CODE (gimple_assign_rhs1 (stmt)) == INTEGER_CST)
+     {
+       dvr.type = VR_RANGE;
+       dvr.min = dvr.max = gimple_assign_rhs1 (stmt);
+       dvr.equiv = NULL;
+       vr1 = &dvr;
+     }
+   else if (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
+     vr1 = get_value_range (gimple_assign_rhs1 (stmt));
+   else
+     return false;
+ 
+   if (TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST
+       && vr1 != &dvr)
+     {
+       dvr.type = VR_RANGE;
+       dvr.min = dvr.max = gimple_assign_rhs2 (stmt);
+       dvr.equiv = NULL;
+       vr2 = &dvr;
+     }
+   else if (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
+     vr2 = get_value_range (gimple_assign_rhs2 (stmt));
+   else
+     return false;
+ 
+   if (!integral_range_p (vr1)
+       || !integral_range_p (vr2))
+     return false;
+ 
+   switch (code)
+     {
+     case MULT_EXPR:
+     case PLUS_EXPR:
+       if (int_const_binop_1 (code, vr1->min, vr2->min, &low, &hi)
+ 	  || fit_double_type (low, hi, &low, &hi, type)
+ 	  || int_const_binop_1 (code, vr1->max, vr2->max, &low, &hi)
+ 	  || fit_double_type (low, hi, &low, &hi, type))
+ 	return false;
+       gimple_assign_set_rhs_code (stmt, (code == PLUS_EXPR
+ 					 ? PLUSNV_EXPR : MULTNV_EXPR));
+       return true;
+ 
+     case MINUS_EXPR:
+       if (int_const_binop_1 (code, vr1->min, vr2->max, &low, &hi)
+ 	  || fit_double_type (low, hi, &low, &hi, type)
+ 	  || int_const_binop_1 (code, vr1->max, vr2->min, &low, &hi)
+ 	  || fit_double_type (low, hi, &low, &hi, type))
+ 	return false;
+       gimple_assign_set_rhs_code (stmt, MINUSNV_EXPR);
+       return true;
+ 
+     case POINTER_PLUS_EXPR:
+       /* FIXME.  */
+       break;
+ 
+     default:
+       ;
+     }
+ 
+   return false;
+ }
+ 
  /* Simplify STMT using ranges if possible.  */
  
  bool
*************** simplify_stmt_using_ranges (gimple_stmt_
*** 6965,6970 ****
--- 7091,7109 ----
  	    return simplify_abs_using_ranges (stmt);
  	  break;
  
+ 	case NEGATE_EXPR:
+ 	  if (INTEGRAL_TYPE_P (gimple_expr_type (stmt)))
+ 	    return simplify_unary_for_nonwrapping (stmt);
+ 	  break;
+ 
+ 	case PLUS_EXPR:
+ 	case MINUS_EXPR:
+ 	case MULT_EXPR:
+ 	case POINTER_PLUS_EXPR:
+ 	  if (INTEGRAL_TYPE_P (gimple_expr_type (stmt)))
+ 	    return simplify_binary_for_nonwrapping (stmt);
+ 	  break;
+ 
  	default:
  	  break;
  	}
Index: gcc/tree.h
===================================================================
*** gcc/tree.h	(revision 144693)
--- gcc/tree.h	(working copy)
*************** extern tree fold_unary_to_constant (enum
*** 4861,4866 ****
--- 4861,4868 ----
  extern tree fold_binary_to_constant (enum tree_code, tree, tree, tree);
  extern tree fold_read_from_constant_string (tree);
  extern tree int_const_binop (enum tree_code, const_tree, const_tree, int);
+ extern int int_const_binop_1 (enum tree_code, const_tree, const_tree,
+ 			      unsigned HOST_WIDE_INT *, HOST_WIDE_INT *);
  extern tree build_fold_addr_expr (tree);
  extern tree fold_build_cleanup_point_expr (tree type, tree expr);
  extern tree fold_strip_sign_ops (tree);
Index: gcc/fold-const.c
===================================================================
*** gcc/fold-const.c	(revision 144693)
--- gcc/fold-const.c	(working copy)
*************** add_double_with_sign (unsigned HOST_WIDE
*** 328,340 ****
    HOST_WIDE_INT h;
  
    l = l1 + l2;
!   h = h1 + h2 + (l < l1);
  
    *lv = l;
    *hv = h;
  
    if (unsigned_p)
!     return (unsigned HOST_WIDE_INT) h < (unsigned HOST_WIDE_INT) h1;
    else
      return OVERFLOW_SUM_SIGN (h1, h2, h);
  }
--- 328,344 ----
    HOST_WIDE_INT h;
  
    l = l1 + l2;
!   h = (HOST_WIDE_INT)((unsigned HOST_WIDE_INT)h1
! 		      + (unsigned HOST_WIDE_INT)h2
! 		      + (l < l1));
  
    *lv = l;
    *hv = h;
  
    if (unsigned_p)
!     return ((unsigned HOST_WIDE_INT) h < (unsigned HOST_WIDE_INT) h1
! 	    || (h == h1
! 		&& l < l1));
    else
      return OVERFLOW_SUM_SIGN (h1, h2, h);
  }
*************** int_binop_types_match_p (enum tree_code 
*** 1610,1616 ****
     to evaluate CODE at compile-time otherwise return 1 if the
     operation overflowed and 0 if not.  */
  
! static int
  int_const_binop_1 (enum tree_code code, const_tree arg1, const_tree arg2,
  		   unsigned HOST_WIDE_INT *lowp, HOST_WIDE_INT *hip)
  {
--- 1614,1620 ----
     to evaluate CODE at compile-time otherwise return 1 if the
     operation overflowed and 0 if not.  */
  
! int
  int_const_binop_1 (enum tree_code code, const_tree arg1, const_tree arg2,
  		   unsigned HOST_WIDE_INT *lowp, HOST_WIDE_INT *hip)
  {
*************** int_const_binop_1 (enum tree_code code, 
*** 1662,1680 ****
  
      case PLUS_EXPR:
      case PLUSNV_EXPR:
!       overflow = add_double (int1l, int1h, int2l, int2h, &low, &hi);
        break;
  
      case MINUS_EXPR:
      case MINUSNV_EXPR:
        neg_double (int2l, int2h, &low, &hi);
        add_double (int1l, int1h, low, hi, &low, &hi);
!       overflow = OVERFLOW_SUM_SIGN (hi, int2h, int1h);
        break;
  
      case MULT_EXPR:
      case MULTNV_EXPR:
!       overflow = mul_double (int1l, int1h, int2l, int2h, &low, &hi);
        break;
  
      case TRUNC_DIV_EXPR:
--- 1666,1691 ----
  
      case PLUS_EXPR:
      case PLUSNV_EXPR:
!       overflow = add_double_with_sign (int1l, int1h, int2l, int2h,
! 				       &low, &hi, uns);
        break;
  
      case MINUS_EXPR:
      case MINUSNV_EXPR:
        neg_double (int2l, int2h, &low, &hi);
        add_double (int1l, int1h, low, hi, &low, &hi);
!       if (uns)
! 	overflow = ((unsigned HOST_WIDE_INT) hi > (unsigned HOST_WIDE_INT) int1h
! 		    || (hi == int1h
! 			&& low > int1l));
!       else
! 	overflow = OVERFLOW_SUM_SIGN (hi, int2h, int1h);
        break;
  
      case MULT_EXPR:
      case MULTNV_EXPR:
!       overflow = mul_double_with_sign (int1l, int1h, int2l, int2h,
! 				       &low, &hi, uns);
        break;
  
      case TRUNC_DIV_EXPR:
Index: gcc/stor-layout.c
===================================================================
*** gcc/stor-layout.c	(revision 144693)
--- gcc/stor-layout.c	(working copy)
*************** layout_type (tree type)
*** 1751,1756 ****
--- 1751,1767 ----
  							    TREE_TYPE (lb),
  							    ub, lb)));
  
+ 	    /* Strip the overflow flag from the above computation if ub
+ 	       and lb didn't overflow itself.  */
+ 	    if (TREE_CODE (length) == INTEGER_CST
+ 		&& TREE_OVERFLOW (length)
+ 		&& (TREE_CODE (ub) != INTEGER_CST
+ 		    || !TREE_OVERFLOW (ub))
+ 		&& (TREE_CODE (lb) != INTEGER_CST
+ 		    || !TREE_OVERFLOW (lb)))
+ 	      length = build_int_cst_wide (sizetype, TREE_INT_CST_LOW (length),
+ 					   TREE_INT_CST_HIGH (length));
+ 
  	    /* Special handling for arrays of bits (for Chill).  */
  	    element_size = TYPE_SIZE (element);
  	    if (TYPE_PACKED (type) && INTEGRAL_TYPE_P (element)