This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Fix another VRP bug


Eric Botcazou wrote:
> > Hmm, this was fixed a different way and it is not really a bug in VRP
> > but in scev when figuring out if a scev probably wraps.
> >
> > See <http://gcc.gnu.org/ml/gcc-patches/2005-09/msg00040.html>.
> 
> 1. Sebastian did first say "And the problem is in VRP" then did not mention 
> VRP in his post: http://gcc.gnu.org/ml/gcc-patches/2005-09/msg00040.html.
> 
> Sebastian?  (Btw, less terse posts about bugs would not be superfluous :-)
> 

Sorry.  The problem as I understand is not in VRP but in
scev_probably_wraps_p that sometimes produces wrong results.

> 2. I do think there is a bug in VRP, as my longish message was painfully 
> trying to explain.  Whether or not Sebastian's fix is real or papering over 
> it is another debate.
> 

It fixes the bug testcase but nothing more: IOW it is papering.  I
have another patch that is too big but I didn't make it compile, but
it changes too many things.  Attached is the patch on which I've
worked, not tested, but I have to go now... (sorry, they are closing
the doors for the weekend at 6:45 pm).

Sebastian

Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1537
diff -d -u -p -r1.1537 Makefile.in
--- Makefile.in	29 Aug 2005 13:52:32 -0000	1.1537
+++ Makefile.in	31 Aug 2005 16:09:49 -0000
@@ -1944,7 +1944,7 @@ tree-browser.o : tree-browser.c tree-bro
    $(TREE_H) tree-inline.h $(DIAGNOSTIC_H) $(HASHTAB_H) \
    $(TM_H) coretypes.h
 tree-chrec.o: tree-chrec.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
-   $(GGC_H) $(TREE_H) real.h tree-chrec.h tree-pass.h $(PARAMS_H) \
+   $(TREE_H) real.h $(SCEV_H) tree-pass.h $(PARAMS_H) \
    $(DIAGNOSTIC_H) $(VARRAY_H) $(CFGLOOP_H) $(TREE_FLOW_H)
 tree-scalar-evolution.o: tree-scalar-evolution.c $(CONFIG_H) $(SYSTEM_H) \
    coretypes.h $(TM_H) $(GGC_H) $(TREE_H) real.h $(RTL_H) \
Index: cfgloop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.h,v
retrieving revision 1.51
diff -d -u -p -r1.51 cfgloop.h
--- cfgloop.h	24 Aug 2005 07:56:53 -0000	1.51
+++ cfgloop.h	31 Aug 2005 16:09:49 -0000
@@ -162,6 +162,9 @@ struct loop
      if there is no estimation.  */
   tree estimated_nb_iterations;
 
+  /* Exit statement corresponding to the estimated_nb_iterations.  */
+  tree estimated_exit_stmt;
+
   /* Upper bound on number of iterations of a loop.  */
   struct nb_iter_bound *bounds;
 
Index: tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-chrec.c,v
retrieving revision 2.25
diff -d -u -p -r2.25 tree-chrec.c
--- tree-chrec.c	21 Aug 2005 10:59:13 -0000	2.25
+++ tree-chrec.c	31 Aug 2005 16:09:50 -0000
@@ -36,6 +36,7 @@ Software Foundation, 51 Franklin Street,
 #include "cfgloop.h"
 #include "tree-flow.h"
 #include "tree-chrec.h"
+#include "tree-scalar-evolution.h"
 #include "tree-pass.h"
 #include "params.h"
 
@@ -1183,3 +1184,211 @@ chrec_type (tree chrec)
   
   return TREE_TYPE (chrec);
 }
+
+/* Return true when the property is decidable, false otherwise.  Set
+   INCREASING to true when BASE + STEP*I is proved monotonically
+   increasing, and to false when the sequence is decreasing.  
+     
+   Def: A sequence is said monotone iff it is an ascending or
+   descending chain: that is, for each successive elements (s_i,
+   s_{i+1}) in the sequence, s_i < s_{i+1} for an ascending chain, or
+   for each successive elements s_i > s_{i+1} for a descending
+   chain.  */
+
+bool
+monotonically_increasing_scev (tree type, tree base, tree step,
+			       struct loop *loop, bool *increasing)
+{
+  tree diff, bound_a, bound_b, type_mid_value, niter;
+  int ca, cb, cm;
+
+  niter = estimated_nb_iterations (loop);
+  if (chrec_contains_undetermined (niter))
+    return false;
+
+  /* For signed types without wrapping, the property is simple to
+     compute.  */
+  if (!flag_wrapv && !TYPE_UNSIGNED (type))
+    {
+      tree base_plus_step = fold_build2 (PLUS_EXPR, type, base, step);
+
+      switch (compare_values (base, base_plus_step))
+	{
+	case -1:
+	  *increasing = true;
+	  return true;
+
+	case 1:
+	  *increasing = false;
+	  return true;
+
+	default:
+	  return false;
+	}
+    }
+  
+  /* Computing this property for wrapping types requires more
+     attention.  */
+
+  /* In unsigned wrapping type semantics, an affine sequence BASE +
+     I*STEP with NITER elements is:
+     - monotonically increasing iff 0 < STEP <= A <= MID, and
+     - monotonically decreasing iff MID <= B <= STEP < MAX, with:
+     A = (MAX - BASE) /[floor] NITER,
+     B = (BASE - MIN) /[floor] NITER.
+     MIN = TYPE_MIN_VALUE
+     MAX = TYPE_MAX_VALUE
+     MID = (TYPE_MAX_VALUE - TYPE_MIN_VALUE) / 2
+  */
+  if (TYPE_UNSIGNED (type))
+    {
+      diff = fold_build2 (MINUS_EXPR, type, TYPE_MAX_VALUE (type),
+			  TYPE_MIN_VALUE (type));
+      type_mid_value = fold_build2 (FLOOR_DIV_EXPR, type, diff,
+				    build_int_cst_type (type, 2));
+      cm = compare_values (step, type_mid_value);
+    }
+
+  /* In signed wrapping type semantics, an affine sequence BASE +
+     I*STEP with NITER elements is:
+     - monotonically increasing iff 0 < STEP <= A <= MAX, and
+     - monotonically decreasing iff MIN <= B <= STEP < 0, with:
+     A = (MAX - BASE) /[floor] NITER,
+     B = (BASE - MIN) /[floor] NITER.
+     MIN = TYPE_MIN_VALUE
+     MAX = TYPE_MAX_VALUE
+  */
+  else
+    cm = compare_values (integer_zero_node, step);
+
+  if (cm == -1)
+    {
+      diff = fold_build2 (MINUS_EXPR, type, TYPE_MAX_VALUE (type), base);
+      bound_a = fold_build2 (FLOOR_DIV_EXPR, type, diff, niter);
+
+      /* Either wrapping, or constant.  */
+      if (compare_values (bound_a, integer_zero_node) == 0)
+	return false;
+
+      ca = compare_values (step, bound_a);
+      if (ca == -1)
+	{
+	  *increasing = true;
+	  return true;
+	}
+    }
+
+  else if (cm == 1)
+    {
+      diff = fold_build2 (MINUS_EXPR, type, base, TYPE_MIN_VALUE (type));
+      bound_b = fold_build2 (FLOOR_DIV_EXPR, type, diff, niter);
+
+      /* Either wrapping, or constant.  */
+      if (compare_values (bound_b, integer_zero_node) == 0)
+	return false;
+
+      cb = compare_values (step, bound_b);
+      if (cb == 1)
+	{
+	  *increasing = false;
+	  return true;
+	}
+    }
+
+  /* The property is not decidable.  */
+  return false;
+}
+
+/* Compute the bounds of CHREC as an interval [MIN, MAX].  AT_STMT is
+   the statement that contains the analyzed scalar.  When the property
+   cannot be computed, MIN and MAX are set to NULL_TREE, otherwise MIN
+   and MAX are set to INTEGER_CST.  */
+
+void
+bounding_box_for_scev (tree chrec, tree at_stmt, struct loops *loops,
+		       tree *min, tree *max, bool *anti_range)
+{
+  struct loop *loop;
+  tree type, base, step;
+  bool init_is_max, unknown_max, increasing;
+
+  /* Default values: don't know.  */
+  *anti_range = false;
+  *min = NULL_TREE;
+  *max = NULL_TREE;
+
+  if (chrec_contains_undetermined (chrec))
+    return;
+  
+  type = chrec_type (chrec);
+  if (POINTER_TYPE_P (type))
+    return;
+
+  /* Safely set MIN and MAX to the bounds of the type.  */
+  *min = TYPE_MIN_VALUE (type);
+  *max = TYPE_MAX_VALUE (type);
+
+  if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
+    return;
+
+  loop = CHREC_LOOP (loops, chrec);
+  base = initial_condition_in_loop_num (chrec, loop->num);
+  step = evolution_part_in_loop_num (chrec, loop->num);
+
+  /* If either STEP or BASE is symbolic, it is impossible to prove
+     that the sequence does not wrap: give up.  */
+  if (step == NULL_TREE
+      || base == NULL_TREE
+      || !is_gimple_min_invariant (step)
+      || !is_gimple_min_invariant (base)
+      || TREE_CODE (base) == REAL_CST
+      || TREE_CODE (step) == REAL_CST)
+    return;
+
+  if (scev_probably_wraps_p (type, base, step, at_stmt, loop,
+			     &init_is_max, &unknown_max)
+      || unknown_max)
+    return;
+
+  if (monotonically_increasing_scev (type, base, step, loop, &increasing))
+    {
+      tree last_value;
+      tree niter = estimated_nb_iterations (loop);
+
+      if (chrec_contains_undetermined (niter))
+	last_value = increasing ? TYPE_MAX_VALUE (type) : TYPE_MIN_VALUE (type);
+      else
+	{
+	  if (at_stmt && stmt_dominates_stmt_p (estimated_exit_stmt (loop),
+						at_stmt))
+	    {
+	      tree niter1 = fold_build2 (MINUS_EXPR, type, niter,
+					 integer_one_node);
+	      last_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, niter1);
+	    }
+	  else
+	    last_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, niter);
+	}
+
+      /* A wrapping sequence.  */
+      if ((increasing && compare_values (base, last_value) == 1)
+	  || (!increasing && compare_values (base, last_value) == -1))
+	{
+	  /* When we can prove that the sequence wraps a single time,
+	     it is possible to express the bounding box in terms of
+	     anti ranges.  */
+	  if (compare_values (base, integer_zero_node) == 0
+	      && TYPE_UNSIGNED (type))
+	    {
+	      *anti_range = true;
+	      *min = increasing ? last_value : base;
+	      *max = increasing ? base : last_value;
+	    }
+	  return;
+	}
+
+      *min = increasing ? base : last_value;
+      *max = increasing ? last_value : base;
+    }
+}
+
Index: tree-chrec.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-chrec.h,v
retrieving revision 2.10
diff -d -u -p -r2.10 tree-chrec.h
--- tree-chrec.h	25 Jun 2005 02:01:16 -0000	2.10
+++ tree-chrec.h	31 Aug 2005 16:09:50 -0000
@@ -27,6 +27,7 @@ Software Foundation, 51 Franklin Street,
 #define CHREC_LEFT(NODE)          TREE_OPERAND (NODE, 1)
 #define CHREC_RIGHT(NODE)         TREE_OPERAND (NODE, 2)
 #define CHREC_VARIABLE(NODE)      TREE_INT_CST_LOW (CHREC_VAR (NODE))
+#define CHREC_LOOP(LOOPS, NODE)   (LOOPS->parray[CHREC_VARIABLE (NODE)])
 
 
 
@@ -90,6 +91,10 @@ extern bool tree_contains_chrecs (tree, 
 extern bool evolution_function_is_affine_multivariate_p (tree);
 extern bool evolution_function_is_univariate_p (tree);
 extern unsigned nb_vars_in_chrec (tree);
+extern bool monotonically_increasing_scev (tree, tree, tree, struct loop *,
+					   bool *);
+extern void bounding_box_for_scev (tree, tree, struct loops *, tree *, tree *,
+				   bool *);
 
 
 
Index: tree-scalar-evolution.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.h,v
retrieving revision 2.7
diff -d -u -p -r2.7 tree-scalar-evolution.h
--- tree-scalar-evolution.h	25 Jun 2005 02:01:31 -0000	2.7
+++ tree-scalar-evolution.h	31 Aug 2005 16:09:50 -0000
@@ -22,6 +22,9 @@ Software Foundation, 51 Franklin Street,
 #ifndef GCC_TREE_SCALAR_EVOLUTION_H
 #define GCC_TREE_SCALAR_EVOLUTION_H
 
+extern bool stmt_dominates_stmt_p (tree, tree);
+extern tree estimated_nb_iterations (struct loop *);
+extern tree estimated_exit_stmt (struct loop *);
 extern tree number_of_iterations_in_loop (struct loop *);
 extern tree get_loop_exit_condition (struct loop *);
 
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.40
diff -d -u -p -r2.40 tree-ssa-loop-niter.c
--- tree-ssa-loop-niter.c	23 Aug 2005 08:15:13 -0000	2.40
+++ tree-ssa-loop-niter.c	31 Aug 2005 16:09:50 -0000
@@ -1395,7 +1395,10 @@ compute_estimated_nb_iterations (struct 
 	&& (chrec_contains_undetermined (loop->estimated_nb_iterations)
 	    /* Or when the current estimation is smaller.  */
 	    || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations)))
-      loop->estimated_nb_iterations = bound->bound;
+      {
+	loop->estimated_nb_iterations = bound->bound;
+	loop->estimated_exit_stmt = bound->at_stmt;
+      }
 }
 
 /* The following analyzers are extracting informations on the bounds
@@ -1515,8 +1518,9 @@ estimate_numbers_of_iterations_loop (str
   unsigned i, n_exits;
   struct tree_niter_desc niter_desc;
 
-  /* Give up if we already have tried to compute an estimation.  */
-  if (loop->estimated_nb_iterations == chrec_dont_know
+  if (loop == NULL
+      /* Give up if we already have tried to compute an estimation.  */
+      || loop->estimated_nb_iterations == chrec_dont_know
       /* Or when we already have an estimation.  */
       || (loop->estimated_nb_iterations != NULL_TREE
 	  && TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST))
@@ -1553,14 +1557,29 @@ void
 estimate_numbers_of_iterations (struct loops *loops)
 {
   unsigned i;
-  struct loop *loop;
 
   for (i = 1; i < loops->num; i++)
-    {
-      loop = loops->parray[i];
-      if (loop)
-	estimate_numbers_of_iterations_loop (loop);
-    }
+    estimate_numbers_of_iterations_loop (loops->parray[i]);
+}
+
+/* Access loop->estimated_nb_iterations with this function that
+   guarantees that the field is properly initialized.  */
+
+tree
+estimated_nb_iterations (struct loop *loop)
+{
+  estimate_numbers_of_iterations_loop (loop);
+  return loop->estimated_nb_iterations;
+}
+
+/* Access loop->estimated_exit_stmt that returns the statement that
+   contains the exit of the loop for the estimated niter.  */
+
+tree
+estimated_exit_stmt (struct loop *loop)
+{
+  estimate_numbers_of_iterations_loop (loop);
+  return loop->estimated_exit_stmt;
 }
 
 /* If A > B, returns -1.  If A == B, returns 0.  If A < B, returns 1.
@@ -1592,7 +1611,7 @@ compare_trees (tree a, tree b)
 
 /* Returns true if statement S1 dominates statement S2.  */
 
-static bool
+bool
 stmt_dominates_stmt_p (tree s1, tree s2)
 {
   basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
Index: tree-vrp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-vrp.c,v
retrieving revision 2.53
diff -d -u -p -r2.53 tree-vrp.c
--- tree-vrp.c	28 Aug 2005 21:08:28 -0000	2.53
+++ tree-vrp.c	31 Aug 2005 16:09:50 -0000
@@ -45,9 +45,6 @@ static sbitmap found_in_subgraph;
    inside adjust_range_with_scev.  */
 static struct loops *cfg_loops;
 
-/* Local functions.  */
-static int compare_values (tree val1, tree val2);
-
 /* Location information for ASSERT_EXPRs.  Each instance of this
    structure describes an ASSERT_EXPR for an SSA name.  Since a single
    SSA name may have more than one assertion associated with it, these
@@ -403,7 +400,7 @@ vrp_expr_computes_nonzero (tree expr)
    This is similar to tree_int_cst_compare but supports pointer values
    and values that cannot be compared at compile time.  */
 
-static int
+int
 compare_values (tree val1, tree val2)
 {
   if (val1 == val2)
@@ -1533,8 +1530,8 @@ static void
 adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt,
 			tree var)
 {
-  tree init, step, chrec;
-  bool init_is_max, unknown_max;
+  bool anti_range;
+  tree chrec, min, max;
 
   /* TODO.  Don't adjust anti-ranges.  An anti-range may provide
      better opportunities than a regular range, but I'm not sure.  */
@@ -1542,77 +1539,16 @@ adjust_range_with_scev (value_range_t *v
     return;
 
   chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
-  if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
-    return;
-
-  init = initial_condition_in_loop_num (chrec, loop->num);
-  step = evolution_part_in_loop_num (chrec, loop->num);
-
-  /* If STEP is symbolic, we can't know whether INIT will be the
-     minimum or maximum value in the range.  */
-  if (step == NULL_TREE
-      || !is_gimple_min_invariant (step))
-    return;
-
-  /* Do not adjust ranges when chrec may wrap.  */
-  if (scev_probably_wraps_p (chrec_type (chrec), init, step, stmt,
-			     cfg_loops->parray[CHREC_VARIABLE (chrec)],
-			     &init_is_max, &unknown_max)
-      || unknown_max)
+  bounding_box_for_scev (chrec, stmt, cfg_loops, &min, &max, &anti_range);
+  if (min == NULL_TREE || max == NULL_TREE)
     return;
 
-  if (!POINTER_TYPE_P (TREE_TYPE (init))
-      && (vr->type == VR_VARYING || vr->type == VR_UNDEFINED))
-    {
-      /* For VARYING or UNDEFINED ranges, just about anything we get
-	 from scalar evolutions should be better.  */
-      if (init_is_max)
-	set_value_range (vr, VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (init)),
-	                 init, vr->equiv);
-      else
-	set_value_range (vr, VR_RANGE, init, TYPE_MAX_VALUE (TREE_TYPE (init)),
-	                 vr->equiv);
-    }
-  else if (vr->type == VR_RANGE)
-    {
-      tree min = vr->min;
-      tree max = vr->max;
-
-      if (init_is_max)
-	{
-	  /* INIT is the maximum value.  If INIT is lower than VR->MAX
-	     but no smaller than VR->MIN, set VR->MAX to INIT.  */
-	  if (compare_values (init, max) == -1)
-	    {
-	      max = init;
-
-	      /* If we just created an invalid range with the minimum
-		 greater than the maximum, take the minimum all the
-		 way to -INF.  */
-	      if (compare_values (min, max) == 1)
-		min = TYPE_MIN_VALUE (TREE_TYPE (min));
-	    }
-	}
-      else
-	{
-	  /* If INIT is bigger than VR->MIN, set VR->MIN to INIT.  */
-	  if (compare_values (init, min) == 1)
-	    {
-	      min = init;
-
-	      /* If we just created an invalid range with the minimum
-		 greater than the maximum, take the maximum all the
-		 way to +INF.  */
-	      if (compare_values (min, max) == 1)
-		max = TYPE_MAX_VALUE (TREE_TYPE (max));
-	    }
-	}
-
-      set_value_range (vr, VR_RANGE, min, max, vr->equiv);
-    }
+  if (anti_range)
+    set_value_range (vr, VR_ANTI_RANGE, min, max, vr->equiv);
+  else
+    set_value_range (vr, VR_RANGE, min, max, vr->equiv);
 }
 
-
 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
    
    - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.754
diff -d -u -p -r1.754 tree.h
--- tree.h	23 Aug 2005 07:28:13 -0000	1.754
+++ tree.h	31 Aug 2005 16:09:50 -0000
@@ -4190,4 +4190,7 @@ extern unsigned HOST_WIDE_INT compute_bu
 /* In expr.c.  */
 extern unsigned HOST_WIDE_INT highest_pow2_factor (tree);
 
+/* In tree-vrp.c */
+extern int compare_values (tree, tree);
+
 #endif  /* GCC_TREE_H  */



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]