[PATCH] Fix another VRP bug
Sebastian Pop
sebastian.pop@cri.ensmp.fr
Sat Sep 3 16:43:00 GMT 2005
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 */
More information about the Gcc-patches
mailing list