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
Hello,
> > 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?
the problem is that for find_loop_niter_by_eval it is hard to determine
what the "right" type is; so it just counts the number of iterations in
integer_type_node, which works since the maximal value it may return is
something like 1024 (or whatever constant I wrote there).
I would recommend writing the test above like
!operand_equal_p (niter, convert (TREE_TYPE (niter), nit), 0)
Zdenek
> 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
> }