This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: [lno] ICE with large unsigned loop bound
- From: Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>
- To: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- Cc: Falk Hueffner <hueffner at informatik dot uni-tuebingen dot de>, gcc at gcc dot gnu dot org, Sebastian Pop <pop at cri dot ensmp dot fr>
- Date: Mon, 10 May 2004 16:01:41 +0200
- Subject: Re: [lno] ICE with large unsigned loop bound
- References: <87k6zlsb6j.fsf@informatik.uni-tuebingen.de> <20040509184302.GA20509@atrey.karlin.mff.cuni.cz>
On Sun, May 09, 2004 at 08:43:02PM +0200, Zdenek Dvorak wrote:
>
> it definitely should be the type of the induction variable (better said,
> its unsigned variant). Unfortunately there are quite a few such type
> wrong relicts from the earlier versions of the scev analysis :-(.
> Sebastian, could you please fix this one (and other related you come
> over)?
>
Yes, however if I change the types of these to chrec_type (chrec0)
I have an ICE in:
internal compiler error: in canonicalize_loop_induction_variables,
at tree-ssa-loop-ivcanon.c:220
because the type you expect to see for "nit" is integer_type_node:
nit = find_loop_niter_by_eval (loop, &ex);
if (ex == exit
&& TREE_CODE (nit) == INTEGER_CST
&& !operand_equal_p (niter, nit, 0))
abort ();
I have to fix it by converting "niter" to integer_type_node, and
avoiding the operand_equal_p test. However I'm not sure whether this
is the right fix.
&& !integer_zerop (fold (build (MINUS_EXPR, integer_type_node,
convert (integer_type_node, niter),
convert (integer_type_node, nit)))))
Maybe the find_loop_niter_by_eval has to return the loop count
converted to the right type instead of integer_type_node?
Bootstrapped on i686-pc-linux-gnu and amd64-unknown-freebsd5.2
* tree-chrec.h (build_chrec_top_type): Disabled, return chrec_top.
* tree-scalar-evolution.c (first_iteration_non_satisfying_noev_ev,
first_iteration_non_satisfying_ev_noev): Use the type of the chrec
instead of integer_type_node when folding operations.
(number_of_iterations_to_overflow): New.
(first_iteration_non_satisfying_ev_ev): Implement some cases.
(set_nb_iterations_in_loop): Return chrec_top on overflow.
(follow_ssa_edge_in_rhs): Handle type conversions "a = (type) rhs".
* tree-ssa-loop-ivcanon.c (canonicalize_loop_induction_variables):
Use the folder instead of the operand_equal_p for verifying the
number of iterations.
Index: tree-chrec.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-chrec.h,v
retrieving revision 1.1.2.18
diff -c -3 -p -r1.1.2.18 tree-chrec.h
*** tree-chrec.h 7 May 2004 10:00:09 -0000 1.1.2.18
--- tree-chrec.h 10 May 2004 13:58:06 -0000
*************** build_peeled_chrec (unsigned loop_num,
*** 159,164 ****
--- 159,168 ----
static inline tree
build_chrec_top_type (tree type)
{
+ /* Disabled for now: it is not used, and libjava fails to build on
+ amd64. */
+ return chrec_top;
+
if (type != NULL_TREE)
{
enum tree_code code = TREE_CODE (type);
Index: tree-data-ref.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-data-ref.h,v
retrieving revision 1.1.2.11
diff -c -3 -p -r1.1.2.11 tree-data-ref.h
*** tree-data-ref.h 6 May 2004 14:36:40 -0000 1.1.2.11
--- tree-data-ref.h 10 May 2004 13:58:06 -0000
*************** extern void dump_data_dependence_directi
*** 163,171 ****
/* Inline functions. */
- static inline bool array_base_name_differ_p (struct data_reference *, struct data_reference *);
-
-
/* This is the simplest data dependence test: determines whether the
data references A and B access the same array. */
--- 163,168 ----
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.c,v
retrieving revision 1.1.2.44
diff -c -3 -p -r1.1.2.44 tree-scalar-evolution.c
*** tree-scalar-evolution.c 30 Apr 2004 23:38:49 -0000 1.1.2.44
--- tree-scalar-evolution.c 10 May 2004 13:58:06 -0000
*************** first_iteration_non_satisfying_noev_ev (
*** 1180,1191 ****
|| tree_does_not_contain_chrecs (chrec0))
/* Example: "while (2 <= {3, +, -1}_2)". */
nb_iters = tree_fold_plus
! (integer_type_node,
! tree_fold_floor_div (integer_type_node,
! tree_fold_minus (integer_type_node,
! init1, init0),
! tree_fold_abs (integer_type_node,
! step1)),
integer_one_node);
else
/* Example: "while ({2, +, 1}_1 <= {3, +, -1}_2)". */
--- 1180,1189 ----
|| tree_does_not_contain_chrecs (chrec0))
/* Example: "while (2 <= {3, +, -1}_2)". */
nb_iters = tree_fold_plus
! (type1,
! tree_fold_floor_div (type1,
! tree_fold_minus (type1, init1, init0),
! tree_fold_abs (type1, step1)),
integer_one_node);
else
/* Example: "while ({2, +, 1}_1 <= {3, +, -1}_2)". */
*************** first_iteration_non_satisfying_noev_ev (
*** 1196,1202 ****
if (tree_is_gt (init0,
tree_fold_plus
(type1, init1, tree_fold_multiply
! (integer_type_node, nb_iters, step1)), &val)
&& val)
return nb_iters;
--- 1194,1200 ----
if (tree_is_gt (init0,
tree_fold_plus
(type1, init1, tree_fold_multiply
! (type1, nb_iters, step1)), &val)
&& val)
return nb_iters;
*************** first_iteration_non_satisfying_noev_ev (
*** 1240,1246 ****
|| tree_does_not_contain_chrecs (chrec0))
/* Example: "while (2 < {3, +, -1}_2)". */
nb_iters = tree_fold_ceil_div
! (integer_type_node,
tree_fold_minus (type1, init1, init0),
tree_fold_abs (type1, step1));
else
--- 1238,1244 ----
|| tree_does_not_contain_chrecs (chrec0))
/* Example: "while (2 < {3, +, -1}_2)". */
nb_iters = tree_fold_ceil_div
! (type1,
tree_fold_minus (type1, init1, init0),
tree_fold_abs (type1, step1));
else
*************** first_iteration_non_satisfying_noev_ev (
*** 1252,1258 ****
if (tree_is_ge (init0,
tree_fold_plus
(type1, init1, tree_fold_multiply
! (integer_type_node, nb_iters, step1)), &val)
&& val)
return nb_iters;
--- 1250,1256 ----
if (tree_is_ge (init0,
tree_fold_plus
(type1, init1, tree_fold_multiply
! (type1, nb_iters, step1)), &val)
&& val)
return nb_iters;
*************** first_iteration_non_satisfying_noev_ev (
*** 1304,1315 ****
{
if (tree_is_gt (init0, init1, &val) && val)
{
! tree diff = tree_fold_minus (integer_type_node,
! init0, init1);
! if (tree_fold_divides_p (integer_type_node, step1, diff))
/* Example: "while (3 != {2, +, 1}_2)". */
! nb_iters = tree_fold_exact_div
! (integer_type_node, diff, step1);
else
/* Example: "while (3 != {2, +, 2}_2)". */
return chrec_top;
--- 1302,1311 ----
{
if (tree_is_gt (init0, init1, &val) && val)
{
! tree diff = tree_fold_minus (type1, init0, init1);
! if (tree_fold_divides_p (type1, step1, diff))
/* Example: "while (3 != {2, +, 1}_2)". */
! nb_iters = tree_fold_exact_div (type1, diff, step1);
else
/* Example: "while (3 != {2, +, 2}_2)". */
return chrec_top;
*************** first_iteration_non_satisfying_noev_ev (
*** 1330,1342 ****
{
if (tree_is_lt (init0, init1, &val) && val)
{
! tree diff = tree_fold_minus (integer_type_node,
! init1, init0);
! if (tree_fold_divides_p (integer_type_node, step1, diff))
/* Example: "while (2 != {3, +, -1}_2)". */
nb_iters = tree_fold_exact_div
! (integer_type_node, diff,
! tree_fold_abs (integer_type_node, step1));
else
/* Example: "while (2 != {3, +, -2}_2)". */
return chrec_top;
--- 1326,1336 ----
{
if (tree_is_lt (init0, init1, &val) && val)
{
! tree diff = tree_fold_minus (type1, init1, init0);
! if (tree_fold_divides_p (type1, step1, diff))
/* Example: "while (2 != {3, +, -1}_2)". */
nb_iters = tree_fold_exact_div
! (type1, diff, tree_fold_abs (type1, step1));
else
/* Example: "while (2 != {3, +, -2}_2)". */
return chrec_top;
*************** first_iteration_non_satisfying_noev_ev (
*** 1354,1360 ****
if (tree_is_eq (init0,
tree_fold_plus
(type1, init1, tree_fold_multiply
! (integer_type_node, nb_iters, step1)), &val)
&& val)
return nb_iters;
--- 1348,1354 ----
if (tree_is_eq (init0,
tree_fold_plus
(type1, init1, tree_fold_multiply
! (type1, nb_iters, step1)), &val)
&& val)
return nb_iters;
*************** first_iteration_non_satisfying_ev_noev (
*** 1440,1449 ****
|| tree_does_not_contain_chrecs (chrec1))
/* Example: "while ({2, +, 1}_2 <= 3)". */
nb_iters = tree_fold_plus
! (integer_type_node,
! tree_fold_floor_div (integer_type_node,
! tree_fold_minus (integer_type_node,
! init1, init0),
step0),
integer_one_node);
else
--- 1434,1442 ----
|| tree_does_not_contain_chrecs (chrec1))
/* Example: "while ({2, +, 1}_2 <= 3)". */
nb_iters = tree_fold_plus
! (type0,
! tree_fold_floor_div (type0,
! tree_fold_minus (type0, init1, init0),
step0),
integer_one_node);
else
*************** first_iteration_non_satisfying_ev_noev (
*** 1454,1460 ****
/* Verify the result. */
if (tree_is_gt (tree_fold_plus
(type0, init0, tree_fold_multiply
! (integer_type_node, nb_iters, step0)), init1, &val)
&& val)
return nb_iters;
--- 1447,1453 ----
/* Verify the result. */
if (tree_is_gt (tree_fold_plus
(type0, init0, tree_fold_multiply
! (type0, nb_iters, step0)), init1, &val)
&& val)
return nb_iters;
*************** first_iteration_non_satisfying_ev_noev (
*** 1496,1513 ****
|| tree_does_not_contain_chrecs (chrec1))
/* Example: "while ({2, +, 1}_2 < 3)". */
nb_iters = tree_fold_ceil_div
! (integer_type_node,
! tree_fold_minus (integer_type_node, init1, init0),
! step0);
else
/* Example: "while ({2, +, 1}_2 < {3, +, 1}_1)". */
return chrec_top;
}
/* Verify the result. */
! if (tree_is_ge (tree_fold_plus
! (type0, init0, tree_fold_multiply
! (integer_type_node, nb_iters, step0)), init1, &val)
&& val)
return nb_iters;
--- 1489,1505 ----
|| tree_does_not_contain_chrecs (chrec1))
/* Example: "while ({2, +, 1}_2 < 3)". */
nb_iters = tree_fold_ceil_div
! (type0, tree_fold_minus (type0, init1, init0), step0);
else
/* Example: "while ({2, +, 1}_2 < {3, +, 1}_1)". */
return chrec_top;
}
/* Verify the result. */
! if (tree_is_ge (tree_fold_plus (type0, init0,
! tree_fold_multiply (type0, nb_iters,
! step0)),
! init1, &val)
&& val)
return nb_iters;
*************** first_iteration_non_satisfying_ev_noev (
*** 1559,1570 ****
{
if (tree_is_lt (init0, init1, &val) && val)
{
! tree diff = tree_fold_minus (integer_type_node,
! init1, init0);
! if (tree_fold_divides_p (integer_type_node, step0, diff))
/* Example: "while ({2, +, 1}_2 != 3)". */
! nb_iters = tree_fold_exact_div
! (integer_type_node, diff, step0);
else
/* Example: "while ({2, +, 2}_2 != 3)". */
return chrec_top;
--- 1551,1560 ----
{
if (tree_is_lt (init0, init1, &val) && val)
{
! tree diff = tree_fold_minus (type0, init1, init0);
! if (tree_fold_divides_p (type0, step0, diff))
/* Example: "while ({2, +, 1}_2 != 3)". */
! nb_iters = tree_fold_exact_div (type0, diff, step0);
else
/* Example: "while ({2, +, 2}_2 != 3)". */
return chrec_top;
*************** first_iteration_non_satisfying_ev_noev (
*** 1585,1597 ****
{
if (tree_is_gt (init0, init1, &val) && val)
{
! tree diff = tree_fold_minus (integer_type_node,
! init0, init1);
! if (tree_fold_divides_p (integer_type_node, step0, diff))
/* Example: "while ({3, +, -1}_2 != 2)". */
nb_iters = tree_fold_exact_div
! (integer_type_node, diff,
! tree_fold_abs (integer_type_node, step0));
else
/* Example: "while ({3, +, -2}_2 != 2)". */
return chrec_top;
--- 1575,1586 ----
{
if (tree_is_gt (init0, init1, &val) && val)
{
! tree diff = tree_fold_minus (type0, init0, init1);
! if (tree_fold_divides_p (type0, step0, diff))
/* Example: "while ({3, +, -1}_2 != 2)". */
nb_iters = tree_fold_exact_div
! (type0, diff, tree_fold_abs (integer_type_node,
! step0));
else
/* Example: "while ({3, +, -2}_2 != 2)". */
return chrec_top;
*************** first_iteration_non_satisfying_ev_noev (
*** 1608,1614 ****
/* Verify the result. */
if (tree_is_eq (tree_fold_plus
(type0, init0, tree_fold_multiply
! (integer_type_node, nb_iters, step0)), init1, &val)
&& val)
return nb_iters;
else
--- 1597,1603 ----
/* Verify the result. */
if (tree_is_eq (tree_fold_plus
(type0, init0, tree_fold_multiply
! (type0, nb_iters, step0)), init1, &val)
&& val)
return nb_iters;
else
*************** first_iteration_non_satisfying_ev_noev (
*** 1623,1642 ****
return chrec_top;
}
/* Helper function for the case when both CHREC0 and CHREC1 has an
evolution in the considered loop. */
static tree
first_iteration_non_satisfying_ev_ev (enum tree_code code,
! unsigned loop_nb ATTRIBUTE_UNUSED,
! tree chrec0 ATTRIBUTE_UNUSED,
! tree chrec1 ATTRIBUTE_UNUSED)
{
switch (code)
{
case LE_EXPR:
-
case LT_EXPR:
case EQ_EXPR:
--- 1612,1727 ----
return chrec_top;
}
+ static inline tree
+ number_of_iterations_to_overflow (tree type, tree init, tree step)
+ {
+ return tree_fold_plus
+ (integer_type_node, integer_one_node,
+ tree_fold_ceil_div (integer_type_node,
+ tree_fold_minus (integer_type_node,
+ TYPE_MAX_VALUE (type), init),
+ step));
+ }
+
/* Helper function for the case when both CHREC0 and CHREC1 has an
evolution in the considered loop. */
static tree
first_iteration_non_satisfying_ev_ev (enum tree_code code,
! unsigned loop_nb,
! tree chrec0,
! tree chrec1)
{
+ bool val = false;
+ tree init0, init1, step0, step1;
+ tree type0, type1;
+ tree nb_iters;
+ int sign_step0, sign_step1;
+
+ if (evolution_function_is_multivariate (chrec0)
+ || evolution_function_is_multivariate (chrec1))
+ /* For the moment, don't handle these quite difficult cases. */
+ return chrec_top;
+
+ init0 = CHREC_LEFT (chrec0);
+ step0 = CHREC_RIGHT (chrec0);
+ init1 = CHREC_LEFT (chrec1);
+ step1 = CHREC_RIGHT (chrec1);
+ if (!no_evolution_in_loop_p (init0, loop_nb, &val)
+ || val == false
+ || !no_evolution_in_loop_p (init1, loop_nb, &val)
+ || val == false
+ || TREE_CODE (step0) != INTEGER_CST
+ || TREE_CODE (step1) != INTEGER_CST)
+ /* For the moment, we deal only with INTEGER_CSTs. */
+ return chrec_top;
+
+ sign_step0 = tree_int_cst_sgn (step0);
+ sign_step1 = tree_int_cst_sgn (step1);
+ type0 = chrec_type (chrec0);
+ type1 = chrec_type (chrec1);
+
+ debug_generic_expr (chrec0);
+ debug_generic_expr (chrec1);
+
switch (code)
{
case LE_EXPR:
case LT_EXPR:
+ {
+ if (tree_is_gt (init0, init1, &val) && val)
+ return integer_zero_node;
+
+ if (sign_step0 > 0 && sign_step1 > 0)
+ {
+ if (tree_is_eq (step0, step1, &val) && val)
+ {
+ /* The loop ends after an overflow, for example:
+ "while ({1, +, 2}_1 <= {2, +, 2}_1)". */
+ if (type0 != type1)
+ return chrec_top;
+
+ return number_of_iterations_to_overflow (type1, init1, step1);
+ }
+
+ if (tree_is_gt (step0, step1, &val) && val)
+ {
+ /* "while ({0, +, 2}_1 <= {2, +, 1}_1)". */
+ nb_iters = tree_fold_plus
+ (integer_type_node,
+ ((code == LE_EXPR) ?
+ build_int_cst (integer_type_node, 2) : integer_one_node),
+ tree_fold_ceil_div
+ (integer_type_node,
+ tree_fold_minus (integer_type_node, init1, init0),
+ tree_fold_minus (integer_type_node, step0, step1)));
+
+ /* Verify that chrec1 is not overflowing after nb_iters. */
+ if (!TREE_OVERFLOW (chrec_apply (CHREC_VARIABLE (chrec1),
+ chrec1, nb_iters)))
+ return nb_iters;
+
+ if (type0 != type1)
+ return chrec_top;
+
+ return number_of_iterations_to_overflow (type1, init1, step1);
+ }
+
+ return chrec_top;
+ }
+
+ else if (sign_step0 < 0 && sign_step1 < 0)
+ return chrec_top;
+
+ else if (sign_step0 < 0 && sign_step1 > 0)
+ return chrec_top;
+
+ else if (sign_step0 > 0 && sign_step1 < 0)
+ return chrec_top;
+
+ else
+ return chrec_top;
+ }
case EQ_EXPR:
*************** set_nb_iterations_in_loop (struct loop *
*** 1766,1773 ****
count of the loop in order to be compatible with the other
nb_iter computations in loop-iv. This also allows the
representation of nb_iters that are equal to MAX_INT. */
! if (TREE_CODE (res) == INTEGER_CST
! && TREE_INT_CST_LOW (res) == 0)
res = chrec_top;
if (dump_file && (dump_flags & TDF_DETAILS))
--- 1851,1858 ----
count of the loop in order to be compatible with the other
nb_iter computations in loop-iv. This also allows the
representation of nb_iters that are equal to MAX_INT. */
! if ((TREE_CODE (res) == INTEGER_CST && TREE_INT_CST_LOW (res) == 0)
! || TREE_OVERFLOW (res))
res = chrec_top;
if (dump_file && (dump_flags & TDF_DETAILS))
*************** follow_ssa_edge_in_rhs (struct loop *loo
*** 1962,1967 ****
--- 2047,2059 ----
*/
switch (TREE_CODE (rhs))
{
+ case NOP_EXPR:
+ /* This assignment is under the form "a_1 = (cast) rhs. */
+ res = follow_ssa_edge_in_rhs (loop, TREE_OPERAND (rhs, 0), halting_phi,
+ evolution_of_loop);
+ *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), *evolution_of_loop);
+ break;
+
case INTEGER_CST:
/* This assignment is under the form "a_1 = 7". */
res = false;
Index: tree-ssa-loop-ivcanon.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-ivcanon.c,v
retrieving revision 1.1.2.8
diff -c -3 -p -r1.1.2.8 tree-ssa-loop-ivcanon.c
*** tree-ssa-loop-ivcanon.c 30 Apr 2004 23:38:49 -0000 1.1.2.8
--- tree-ssa-loop-ivcanon.c 10 May 2004 13:58:06 -0000
*************** canonicalize_loop_induction_variables (s
*** 216,222 ****
if (ex == exit
&& TREE_CODE (nit) == INTEGER_CST
! && !operand_equal_p (niter, nit, 0))
abort ();
#endif
}
--- 216,224 ----
if (ex == exit
&& TREE_CODE (nit) == INTEGER_CST
! && !integer_zerop (fold (build (MINUS_EXPR, integer_type_node,
! convert (integer_type_node, niter),
! convert (integer_type_node, nit)))))
abort ();
#endif
}