* tree-vrp.c (simplify_using_ranges): Kill.

        (vrp_finalize): Remove call to simplify_using_ranges.
        (simplify_stmt_using_ranges): New function extracted from
        simplify_using_ranges.
        (simplify_div_or_mod_using_ranges): Likewise.
        (simplify_abs_using_ranges): Likewise.
        (simplify_cond_using_ranges): New function.
        * tree-flow.h (simplify_stmt_using_ranges): Prototype.
        * tree-ssa-propagate.c (substitute_and_fold): Call
        simplify_stmt_using_ranges if we have range information.

        * gcc.dg/tree-ssa/vrp17.c: New test.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@101685 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 185 insertions, 107 deletions

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 1167e3816cd..91be397db2c 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -3493,127 +3493,211 @@ varying:
   return SSA_PROP_VARYING;
 }
 
-/* Walk through the IL simplifying expressions using knowledge
-   gathered by VRP.  */
+/* Simplify a division or modulo operator to a right shift or
+   bitwise and if the first operand is unsigned or is greater
+   than zero and the second operand is an exact power of two.  */
 
 static void
-simplify_using_ranges (void)
+simplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code)
 {
-  basic_block bb;
+  tree val = NULL;
+  tree op = TREE_OPERAND (rhs, 0);
+  value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
 
-  FOR_EACH_BB (bb)
+  if (TYPE_UNSIGNED (TREE_TYPE (op)))
+    {
+      val = integer_one_node;
+    }
+  else
+    {
+      val = compare_range_with_value (GT_EXPR, vr, integer_zero_node);
+    }
+
+  if (val && integer_onep (val))
     {
-      block_stmt_iterator bsi;
+      tree t;
+      tree op0 = TREE_OPERAND (rhs, 0);
+      tree op1 = TREE_OPERAND (rhs, 1);
+
+      if (rhs_code == TRUNC_DIV_EXPR)
+	{
+	  t = build_int_cst (NULL_TREE, tree_log2 (op1));
+	  t = build (RSHIFT_EXPR, TREE_TYPE (op0), op0, t);
+	}
+      else
+	{
+	  t = build_int_cst (TREE_TYPE (op1), 1);
+	  t = int_const_binop (MINUS_EXPR, op1, t, 0);
+	  t = fold_convert (TREE_TYPE (op0), t);
+	  t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t);
+	}
 
-      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+      TREE_OPERAND (stmt, 1) = t;
+      update_stmt (stmt);
+    }
+}
+
+/* If the operand to an ABS_EXPR is >= 0, then eliminate the
+   ABS_EXPR.  If the operand is <= 0, then simplify the
+   ABS_EXPR into a NEGATE_EXPR.  */
+
+static void
+simplify_abs_using_ranges (tree stmt, tree rhs)
+{
+  tree val = NULL;
+  tree op = TREE_OPERAND (rhs, 0);
+  tree type = TREE_TYPE (op);
+  value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
+
+  if (TYPE_UNSIGNED (type))
+    {
+      val = integer_zero_node;
+    }
+  else if (vr)
+    {
+      val = compare_range_with_value (LE_EXPR, vr, integer_zero_node);
+      if (!val)
 	{
-	  tree stmt = bsi_stmt (bsi);
+	  val = compare_range_with_value (GE_EXPR, vr, integer_zero_node);
 
-	  if (TREE_CODE (stmt) == MODIFY_EXPR)
+	  if (val)
 	    {
-	      tree rhs = TREE_OPERAND (stmt, 1);
-	      enum tree_code rhs_code = TREE_CODE (rhs);
-
-	      /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
-		 and BIT_AND_EXPR respectively if the first operand is greater
-		 than zero and the second operand is an exact power of two.  */
-	      if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
-		  && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
-		  && integer_pow2p (TREE_OPERAND (rhs, 1)))
-		{
-		  tree val = NULL;
-		  tree op = TREE_OPERAND (rhs, 0);
-		  value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
-
-		  if (TYPE_UNSIGNED (TREE_TYPE (op)))
-		    {
-		      val = integer_one_node;
-		    }
-		  else
-		    {
-		      val = compare_range_with_value (GT_EXPR, vr,
-						      integer_zero_node);
-		    }
-
-		  if (val && integer_onep (val))
-		    {
-		      tree t;
-		      tree op0 = TREE_OPERAND (rhs, 0);
-		      tree op1 = TREE_OPERAND (rhs, 1);
-
-		      if (rhs_code == TRUNC_DIV_EXPR)
-			{
-			  t = build_int_cst (NULL_TREE, tree_log2 (op1));
-			  t = build (RSHIFT_EXPR, TREE_TYPE (op0), op0, t);
-			}
-		      else
-			{
-			  t = build_int_cst (TREE_TYPE (op1), 1);
-			  t = int_const_binop (MINUS_EXPR, op1, t, 0);
-			  t = fold_convert (TREE_TYPE (op0), t);
-			  t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t);
-			}
-
-		      TREE_OPERAND (stmt, 1) = t;
-		      update_stmt (stmt);
-		    }
+	      if (integer_zerop (val))
+		val = integer_one_node;
+	      else if (integer_onep (val))
+		val = integer_zero_node;
+	    }
+	}
+
+      if (val
+	  && (integer_onep (val) || integer_zerop (val)))
+	{
+	  tree t;
 
+	  if (integer_onep (val))
+	    t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
+	  else
+	    t = op;
+
+	  TREE_OPERAND (stmt, 1) = t;
+	  update_stmt (stmt);
+	}
+    }
+}
+
+/* Simplify a conditional using a relational operator to an equality
+   test if the range information indicates only one value can satisfy
+   the original conditional.  */
+
+static void
+simplify_cond_using_ranges (tree stmt)
+{
+  tree cond = COND_EXPR_COND (stmt);
+  tree op0 = TREE_OPERAND (cond, 0);
+  tree op1 = TREE_OPERAND (cond, 1);
+  enum tree_code cond_code = TREE_CODE (cond);
+
+  if (cond_code != NE_EXPR
+      && cond_code != EQ_EXPR
+      && TREE_CODE (op0) == SSA_NAME
+      && INTEGRAL_TYPE_P (TREE_TYPE (op0))
+      && is_gimple_min_invariant (op1))
+    {
+      value_range_t *vr = get_value_range (op0);
+	  
+      /* If we have range information for OP0, then we might be
+	 able to simplify this conditional. */
+      if (vr->type == VR_RANGE)
+	{
+	  tree min = NULL;
+	  tree max = NULL;
+
+	  /* Extract minimum/maximum values which satisfy the
+	     the conditional as it was written.  */
+	  if (cond_code == LE_EXPR || cond_code == LT_EXPR)
+	    {
+	      min = TYPE_MIN_VALUE (TREE_TYPE (op0));
+
+	      max = op1;
+	      if (cond_code == LT_EXPR)
+		{
+		  tree one = build_int_cst (TREE_TYPE (op0), 1);
+		  max = fold (build (MINUS_EXPR, TREE_TYPE (op0), max, one));
 		}
+	    }
+	  else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
+	    {
+	      max = TYPE_MAX_VALUE (TREE_TYPE (op0));
 
-	      /* Transform ABS (X) into X or -X as appropriate.  */
-	      if (rhs_code == ABS_EXPR
-		  && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
-		  && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
+	      min = op1;
+	      if (cond_code == GT_EXPR)
 		{
-		  tree val = NULL;
-		  tree op = TREE_OPERAND (rhs, 0);
-		  tree type = TREE_TYPE (op);
-		  value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
-
-		  if (TYPE_UNSIGNED (type))
-		    {
-		      val = integer_zero_node;
-		    }
-		  else if (vr)
-		    {
-		      val = compare_range_with_value (LE_EXPR, vr,
-						      integer_zero_node);
-		      if (!val)
-			{
-			  val = compare_range_with_value (GE_EXPR, vr,
-							  integer_zero_node);
-
-			  if (val)
-			    {
-			      if (integer_zerop (val))
-				val = integer_one_node;
-			      else if (integer_onep (val))
-				val = integer_zero_node;
-			    }
-			}
-
-		      if (val
-			  && (integer_onep (val) || integer_zerop (val)))
-			{
-			  tree t;
-
-			  if (integer_onep (val))
-			    t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
-			  else
-			    t = op;
-
-			  TREE_OPERAND (stmt, 1) = t;
-			  update_stmt (stmt);
-			}
-		    }
+		  tree one = build_int_cst (TREE_TYPE (op0), 1);
+		  max = fold (build (PLUS_EXPR, TREE_TYPE (op0), max, one));
 		}
 	    }
 
-	  /* TODO.  Simplify conditionals.   */
+	  /* Now refine the minimum and maximum values using any
+	     value range information we have for op0.  */
+	  if (min && max)
+	    {
+	      if (compare_values (vr->min, min) == -1)
+		min = min;
+	      else
+		min = vr->min;
+	      if (compare_values (vr->max, max) == 1)
+		max = max;
+	      else
+		max = vr->max;
+
+	      /* If the new min/max values have converged to a
+		 single value, then there is only one value which
+		 can satisfy the condition.  Rewrite the condition
+		 to test for equality.  */
+	      if (min == max
+		  && is_gimple_min_invariant (min))
+		{
+		  COND_EXPR_COND (stmt)
+		    = build (EQ_EXPR, boolean_type_node, op0, min);
+		  update_stmt (stmt);
+		}
+	    }
 	}
     }
 }
 
+/* Simplify STMT using ranges if possible.  */
+
+void
+simplify_stmt_using_ranges (tree stmt)
+{
+  if (TREE_CODE (stmt) == MODIFY_EXPR)
+    {
+      tree rhs = TREE_OPERAND (stmt, 1);
+      enum tree_code rhs_code = TREE_CODE (rhs);
+
+      /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
+	 and BIT_AND_EXPR respectively if the first operand is greater
+	 than zero and the second operand is an exact power of two.  */
+      if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
+	  && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
+	  && integer_pow2p (TREE_OPERAND (rhs, 1)))
+	simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code);
+
+      /* Transform ABS (X) into X or -X as appropriate.  */
+      if (rhs_code == ABS_EXPR
+	  && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
+	  && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
+	simplify_abs_using_ranges (stmt, rhs);
+    }
+  else if (TREE_CODE (stmt) == COND_EXPR
+	   && COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
+    {
+      simplify_cond_using_ranges (stmt);
+    }
+}
+
+
 
 /* Traverse all the blocks folding conditionals with known ranges.  */
 
@@ -3657,12 +3741,6 @@ vrp_finalize (void)
 
   substitute_and_fold (single_val_range, true);
 
-  /* One could argue all simplifications should be done here
-     rather than using substitute_and_fold since this code
-     is going to have to perform a complete walk through the
-     IL anyway.  */
-  simplify_using_ranges ();
-
   /* Free allocated memory.  */
   for (i = 0; i < num_ssa_names; i++)
     if (vr_value[i])