re PR tree-optimization/30317 (VRP cannot extract a range from (unsigned int) i + 0x0ffffffff > 4)

2008-03-28  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/30317
	PR tree-optimization/30911
	PR tree-optimization/34793
	* tree-vrp.c (set_and_canonicalize_value_range): New function.
	(struct assert_locus_d): New member EXPR.
	(register_new_assert_for): Add EXPR parameter to support
	ASSERT_EXPR <name, expr OP limit>.
	(register_edge_assert_for_1): Adjust callers.
	(find_assert_locations): Likewise.
	(process_assert_insertions_for): Build condition from
	expression.
	(extract_range_from_assert): Handle ASSERT_EXPRs
	of the form ASSERT_EXPR <name, expr OP limit>.
	(register_edge_assert_for_2): New helper registering
	asserts for comparisons.  Recognize range tests of the form
	(unsigned)i - CST1 OP CST2.
	(register_edge_assert_for_1): Use it.
	(register_edge_assert_for): Likewise.
	* tree.def (ASSERT_EXPR): Document extra allowed conditional
	expressions.
	(needs_overflow_infinity): Integer sub-types
	do not need overflow infinities.
	(vrp_val_is_max): The extreme values of integer sub-types
	are those of the base type.
	(vrp_val_is_min): Likewise.

	* gcc.dg/tree-ssa/vrp35.c: New testcase.
	* gcc.dg/tree-ssa/vrp36.c: Likewise.
	* gcc.dg/tree-ssa/vrp37.c: Likewise.

From-SVN: r133680

1 files changed, 227 insertions, 54 deletions

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 64f6000..a70d1b6 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -71,6 +71,9 @@ struct assert_locus_d
   /* Value being compared against.  */
   tree val;
 
+  /* Expression to compare.  */
+  tree expr;
+
   /* Next node in the linked list.  */
   struct assert_locus_d *next;
 };
@@ -109,7 +112,11 @@ static int *vr_phi_edge_counts;
 static inline bool
 needs_overflow_infinity (const_tree type)
 {
-  return INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type);
+  return (INTEGRAL_TYPE_P (type)
+	  && !TYPE_OVERFLOW_WRAPS (type)
+	  /* Integer sub-types never overflow as they are never
+	     operands of arithmetic operators.  */
+	  && !(TREE_TYPE (type) && TREE_TYPE (type) != type));
 }
 
 /* Return whether TYPE can support our overflow infinity
@@ -231,7 +238,12 @@ avoid_overflow_infinity (tree val)
 static inline bool
 vrp_val_is_max (const_tree val)
 {
-  tree type_max = TYPE_MAX_VALUE (TREE_TYPE (val));
+  tree type_max, type = TREE_TYPE (val);
+
+  /* For integer sub-types the values for the base type are relevant.  */
+  if (TREE_TYPE (type))
+    type = TREE_TYPE (type);
+  type_max = TYPE_MAX_VALUE (type);
 
   return (val == type_max
 	  || (type_max != NULL_TREE
@@ -244,7 +256,12 @@ vrp_val_is_max (const_tree val)
 static inline bool
 vrp_val_is_min (const_tree val)
 {
-  tree type_min = TYPE_MIN_VALUE (TREE_TYPE (val));
+  tree type_min, type = TREE_TYPE (val);
+
+  /* For integer sub-types the values for the base type are relevant.  */
+  if (TREE_TYPE (type))
+    type = TREE_TYPE (type);
+  type_min = TYPE_MIN_VALUE (type);
 
   return (val == type_min
 	  || (type_min != NULL_TREE
@@ -300,6 +317,18 @@ nonnull_arg_p (const_tree arg)
 }
 
 
+/* Set value range VR to VR_VARYING.  */
+
+static inline void
+set_value_range_to_varying (value_range_t *vr)
+{
+  vr->type = VR_VARYING;
+  vr->min = vr->max = NULL_TREE;
+  if (vr->equiv)
+    bitmap_clear (vr->equiv);
+}
+
+
 /* Set value range VR to {T, MIN, MAX, EQUIV}.  */
 
 static void
@@ -352,24 +381,57 @@ set_value_range (value_range_t *vr, enum value_range_type t, tree min,
 }
 
 
-/* Copy value range FROM into value range TO.  */
+/* Set value range VR to the canonical form of {T, MIN, MAX, EQUIV}.
+   This means adjusting T, MIN and MAX representing the case of a
+   wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
+   as anti-rage ~[MAX+1, MIN-1].  Likewise for wrapping anti-ranges.
+   In corner cases where MAX+1 or MIN-1 wraps this will fall back
+   to varying.
+   This routine exists to ease canonicalization in the case where we
+   extract ranges from var + CST op limit.  */
 
-static inline void
-copy_value_range (value_range_t *to, value_range_t *from)
+static void
+set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t,
+				  tree min, tree max, bitmap equiv)
 {
-  set_value_range (to, from->type, from->min, from->max, from->equiv);
-}
+  tree one, tmp;
 
+  if ((t != VR_RANGE
+       && t != VR_ANTI_RANGE)
+      || TREE_CODE (min) != INTEGER_CST
+      || TREE_CODE (max) != INTEGER_CST
+      || !tree_int_cst_lt (max, min))
+    {
+      set_value_range (vr, t, min, max, equiv);
+      return;
+    }
 
-/* Set value range VR to VR_VARYING.  */
+  /* Wrong order for min and max, to swap them and the VR type we need
+     to adjust them.  */
+  one = build_int_cst (TREE_TYPE (min), 1);
+  tmp = int_const_binop (PLUS_EXPR, max, one, 0);
+  max = int_const_binop (MINUS_EXPR, min, one, 0);
+  min = tmp;
+
+  /* There's one corner case, if we had [C+1, C] before we now have
+     that again.  But this represents an empty value range, so drop
+     to varying in this case.  */
+  if (tree_int_cst_lt (max, min))
+    {
+      set_value_range_to_varying (vr);
+      return;
+    }
+
+  t = t == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
+  set_value_range (vr, t, min, max, equiv);
+}
+
+/* Copy value range FROM into value range TO.  */
 
 static inline void
-set_value_range_to_varying (value_range_t *vr)
+copy_value_range (value_range_t *to, value_range_t *from)
 {
-  vr->type = VR_VARYING;
-  vr->min = vr->max = NULL_TREE;
-  if (vr->equiv)
-    bitmap_clear (vr->equiv);
+  set_value_range (to, from->type, from->min, from->max, from->equiv);
 }
 
 /* Set value range VR to a single value.  This function is only called
@@ -1102,20 +1164,24 @@ extract_range_from_assert (value_range_t *vr_p, tree expr)
   gcc_assert (COMPARISON_CLASS_P (cond));
 
   /* Find VAR in the ASSERT_EXPR conditional.  */
-  if (var == TREE_OPERAND (cond, 0))
+  if (var == TREE_OPERAND (cond, 0)
+      || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR
+      || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR)
     {
       /* If the predicate is of the form VAR COMP LIMIT, then we just
 	 take LIMIT from the RHS and use the same comparison code.  */
-      limit = TREE_OPERAND (cond, 1);
       cond_code = TREE_CODE (cond);
+      limit = TREE_OPERAND (cond, 1);
+      cond = TREE_OPERAND (cond, 0);
     }
   else
     {
       /* If the predicate is of the form LIMIT COMP VAR, then we need
 	 to flip around the comparison code to create the proper range
 	 for VAR.  */
-      limit = TREE_OPERAND (cond, 0);
       cond_code = swap_tree_comparison (TREE_CODE (cond));
+      limit = TREE_OPERAND (cond, 0);
+      cond = TREE_OPERAND (cond, 1);
     }
 
   limit = avoid_overflow_infinity (limit);
@@ -1159,8 +1225,43 @@ extract_range_from_assert (value_range_t *vr_p, tree expr)
      instance, ASSERT_EXPR <x_2, x_2 <= b_4>.  If b_4 is ~[2, 10],
      then b_4 takes on the ranges [-INF, 1] and [11, +INF].  There is
      no single range for x_2 that could describe LE_EXPR, so we might
-     as well build the range [b_4, +INF] for it.  */
-  if (cond_code == EQ_EXPR)
+     as well build the range [b_4, +INF] for it.
+     One special case we handle is extracting a range from a
+     range test encoded as (unsigned)var + CST <= limit.  */
+  if (TREE_CODE (cond) == NOP_EXPR
+      || TREE_CODE (cond) == PLUS_EXPR)
+    {
+      tree cst2 = NULL_TREE;
+
+      if (TREE_CODE (cond) == PLUS_EXPR)
+        {
+          min = TREE_OPERAND (cond, 1);
+	  cst2 = fold_build1 (NEGATE_EXPR, TREE_TYPE (min), min);
+          min = fold_convert (TREE_TYPE (var), cst2);
+	  cond = TREE_OPERAND (cond, 0);
+	}
+      else
+	min = build_int_cst (TREE_TYPE (var), 0);
+
+      if (cst2 != NULL_TREE)
+        max = int_const_binop (PLUS_EXPR, limit, min, 0);
+      else
+	max = limit;
+      max = fold_convert (TREE_TYPE (var), max);
+
+      /* We can transform a max, min range to an anti-range or
+         vice-versa.  Use set_and_canonicalize_value_range which does
+	 this for us.  */
+      if (cond_code == LE_EXPR)
+        set_and_canonicalize_value_range (vr_p, VR_RANGE,
+					  min, max, vr_p->equiv);
+      else if (cond_code == GT_EXPR)
+        set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE,
+					  min, max, vr_p->equiv);
+      else
+	gcc_unreachable ();
+    }
+  else if (cond_code == EQ_EXPR)
     {
       enum value_range_type range_type;
 
@@ -3388,9 +3489,9 @@ debug_all_asserts (void)
 
 
 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
-   'NAME COMP_CODE VAL' at a location that dominates block BB or
+   'EXPR COMP_CODE VAL' at a location that dominates block BB or
    E->DEST, then register this location as a possible insertion point
-   for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>.
+   for ASSERT_EXPR <NAME, EXPR COMP_CODE VAL>.
 
    BB, E and SI provide the exact insertion point for the new
    ASSERT_EXPR.  If BB is NULL, then the ASSERT_EXPR is to be inserted
@@ -3399,7 +3500,7 @@ debug_all_asserts (void)
    must not be NULL.  */
 
 static void
-register_new_assert_for (tree name,
+register_new_assert_for (tree name, tree expr,
 			 enum tree_code comp_code,
 			 tree val,
 			 basic_block bb,
@@ -3453,7 +3554,9 @@ register_new_assert_for (tree name,
     {
       if (loc->comp_code == comp_code
 	  && (loc->val == val
-	      || operand_equal_p (loc->val, val, 0)))
+	      || operand_equal_p (loc->val, val, 0))
+	  && (loc->expr == expr
+	      || operand_equal_p (loc->expr, expr, 0)))
 	{
 	  /* If the assertion NAME COMP_CODE VAL has already been
 	     registered at a basic block that dominates DEST_BB, then
@@ -3500,6 +3603,7 @@ register_new_assert_for (tree name,
   n->si = si;
   n->comp_code = comp_code;
   n->val = val;
+  n->expr = expr;
   n->next = NULL;
 
   if (last_loc)
@@ -3588,6 +3692,94 @@ extract_code_and_val_from_cond (tree name, tree cond, bool invert,
   return true;
 }
 
+/* Try to register an edge assertion for SSA name NAME on edge E for
+   the condition COND contributing to the conditional jump pointed to by BSI.
+   Invert the condition COND if INVERT is true.
+   Return true if an assertion for NAME could be registered.  */
+
+static bool
+register_edge_assert_for_2 (tree name, edge e, block_stmt_iterator bsi,
+			    tree cond, bool invert)
+{
+  tree val;
+  enum tree_code comp_code;
+  bool retval = false;
+
+  if (!extract_code_and_val_from_cond (name, cond, invert, &comp_code, &val))
+    return false;
+
+  /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
+     reachable from E.  */
+  if (TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name))
+      && !has_single_use (name))
+    {
+      register_new_assert_for (name, name, comp_code, val, NULL, e, bsi);
+      retval = true;
+    }
+
+  /* In the case of NAME <= CST and NAME being defined as
+     NAME = (unsigned) NAME2 + CST2 we can assert NAME2 >= -CST2
+     and NAME2 <= CST - CST2.  We can do the same for NAME > CST.
+     This catches range and anti-range tests.  */
+  if ((comp_code == LE_EXPR
+       || comp_code == GT_EXPR)
+      && TREE_CODE (val) == INTEGER_CST
+      && TYPE_UNSIGNED (TREE_TYPE (val)))
+    {
+      tree def_stmt = SSA_NAME_DEF_STMT (name);
+      tree cst2 = NULL_TREE, name2 = NULL_TREE;
+
+      /* Extract CST2 from the (optional) addition.  */
+      if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
+	  && TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == PLUS_EXPR)
+	{
+	  name2 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
+	  cst2 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 1);
+	  if (TREE_CODE (name2) == SSA_NAME
+	      && TREE_CODE (cst2) == INTEGER_CST)
+	    def_stmt = SSA_NAME_DEF_STMT (name2);
+	}
+
+      /* Extract NAME2 from the (optional) cast.  */
+      if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
+          && TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == NOP_EXPR)
+	name2 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
+
+      if (name2 != NULL_TREE
+      	  && TREE_CODE (name2) == SSA_NAME
+	  && (cst2 == NULL_TREE
+	      || TREE_CODE (cst2) == INTEGER_CST)
+	  && TREE_CODE (TREE_TYPE (name2)) == INTEGER_TYPE
+	  && TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name2))
+	  && !has_single_use (name2))
+	{
+	  tree tmp;
+
+	  /* Build an expression for the range test.  */
+	  tmp = name2;
+	  if (TREE_TYPE (name) != TREE_TYPE (name2))
+	    tmp = build1 (NOP_EXPR, TREE_TYPE (name), tmp);
+	  if (cst2 != NULL_TREE)
+	    tmp = build2 (PLUS_EXPR, TREE_TYPE (name), tmp, cst2);
+
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "Adding assert for ");
+	      print_generic_expr (dump_file, name2, 0);
+	      fprintf (dump_file, " from ");
+	      print_generic_expr (dump_file, tmp, 0);
+	      fprintf (dump_file, "\n");
+	    }
+
+	  register_new_assert_for (name2, tmp, comp_code, val, NULL, e, bsi);
+
+	  retval = true;
+	}
+    }
+
+  return retval;
+}
+
 /* OP is an operand of a truth value expression which is known to have
    a particular value.  Register any asserts for OP and for any
    operands in OP's defining statement. 
@@ -3615,7 +3807,7 @@ register_edge_assert_for_1 (tree op, enum tree_code code,
   if (!has_single_use (op))
     {
       val = build_int_cst (TREE_TYPE (op), 0);
-      register_new_assert_for (op, code, val, NULL, e, bsi);
+      register_new_assert_for (op, op, code, val, NULL, e, bsi);
       retval = true;
     }
 
@@ -3634,26 +3826,10 @@ register_edge_assert_for_1 (tree op, enum tree_code code,
       tree op0 = TREE_OPERAND (rhs, 0);
       tree op1 = TREE_OPERAND (rhs, 1);
 
-      /* Conditionally register an assert for each SSA_NAME in the
-	 comparison.  */
-      if (TREE_CODE (op0) == SSA_NAME
-	  && !has_single_use (op0)
-	  && extract_code_and_val_from_cond (op0, rhs,
-					     invert, &code, &val))
-	{
-	  register_new_assert_for (op0, code, val, NULL, e, bsi);
-	  retval = true;
-	}
-
-      /* Similarly for the second operand of the comparison.  */
-      if (TREE_CODE (op1) == SSA_NAME
-	  && !has_single_use (op1)
-	  && extract_code_and_val_from_cond (op1, rhs,
-					     invert, &code, &val))
-	{
-	  register_new_assert_for (op1, code, val, NULL, e, bsi);
-	  retval = true;
-	}
+      if (TREE_CODE (op0) == SSA_NAME)
+        retval |= register_edge_assert_for_2 (op0, e, bsi, rhs, invert);
+      if (TREE_CODE (op1) == SSA_NAME)
+        retval |= register_edge_assert_for_2 (op1, e, bsi, rhs, invert);
     }
   else if ((code == NE_EXPR
 	    && (TREE_CODE (rhs) == TRUTH_AND_EXPR
@@ -3713,13 +3889,9 @@ register_edge_assert_for (tree name, edge e, block_stmt_iterator si, tree cond)
 				       &comp_code, &val))
     return false;
 
-  /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
-     reachable from E.  */
-  if (TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
-    {
-      register_new_assert_for (name, comp_code, val, NULL, e, si);
-      retval = true;
-    }
+  /* Register ASSERT_EXPRs for name.  */
+  retval |= register_edge_assert_for_2 (name, e, si, cond, is_else_edge);
+
 
   /* If COND is effectively an equality test of an SSA_NAME against
      the value zero or one, then we may be able to assert values
@@ -4126,7 +4298,7 @@ find_assert_locations (basic_block bb)
 			 conversion.  */
 		      if (! has_single_use (t))
 			{
-			  register_new_assert_for (t, comp_code, value,
+			  register_new_assert_for (t, t, comp_code, value,
 						   bb, NULL, si);
 			  need_assert = true;
 			}
@@ -4138,7 +4310,8 @@ find_assert_locations (basic_block bb)
 		 ASSERT_EXPR would do nothing but increase compile time.  */
 	      if (!has_single_use (op))
 		{
-		  register_new_assert_for (op, comp_code, value, bb, NULL, si);
+		  register_new_assert_for (op, op, comp_code, value,
+					   bb, NULL, si);
 		  need_assert = true;
 		}
 	    }
@@ -4183,7 +4356,7 @@ process_assert_insertions_for (tree name, assert_locus_t loc)
   edge_iterator ei;
   edge e;
 
-  cond = build2 (loc->comp_code, boolean_type_node, name, loc->val);
+  cond = build2 (loc->comp_code, boolean_type_node, loc->expr, loc->val);
   assert_expr = build_assert_expr_for (cond, name);
 
   if (loc->e)