2011-07-23 Sebastian Pop <sebastian....@amd.com> PR middle-end/47594 * graphite-scop-detection.c (graphite_can_represent_scev): Return false on TYPE_UNSIGNED. * graphite-sese-to-poly.c (scan_tree_for_params_int): Do not call double_int_sext. * tree-ssa-loop-niter.c (number_of_iterations_ne): Use the signed types for the trivial case, then convert to unsigned. (number_of_iterations_lt): Use the original signed types. (number_of_iterations_cond): Same. (find_loop_niter): Build signed integer constant. (loop_niter_by_eval): Same. --- gcc/ChangeLog | 14 ++++ gcc/graphite-scop-detection.c | 6 ++ gcc/graphite-sese-to-poly.c | 7 +-- gcc/testsuite/ChangeLog | 5 ++ .../gfortran.dg/graphite/run-id-pr47594.f90 | 35 +++++++++++ gcc/tree-ssa-loop-niter.c | 63 ++++++++++++++++---- 6 files changed, 113 insertions(+), 17 deletions(-) create mode 100644 gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 580c12f..33bd7b4 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,17 @@ +2011-07-23 Sebastian Pop <sebastian....@amd.com> + + PR middle-end/47594 + * graphite-scop-detection.c (graphite_can_represent_scev): Return false + on TYPE_UNSIGNED. + * graphite-sese-to-poly.c (scan_tree_for_params_int): Do not call + double_int_sext. + * tree-ssa-loop-niter.c (number_of_iterations_ne): Use the signed types + for the trivial case, then convert to unsigned. + (number_of_iterations_lt): Use the original signed types. + (number_of_iterations_cond): Same. + (find_loop_niter): Build signed integer constant. + (loop_niter_by_eval): Same. + 2011-08-01 Richard Henderson <r...@redhat.com> PR target/49881 diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c index 3460568..403ff23 100644 --- a/gcc/graphite-scop-detection.c +++ b/gcc/graphite-scop-detection.c @@ -196,6 +196,12 @@ graphite_can_represent_scev (tree scev) if (chrec_contains_undetermined (scev)) return false; + /* FIXME: As long as Graphite cannot handle wrap around effects of + induction variables, we discard them. */ + if (TYPE_UNSIGNED (TREE_TYPE (scev)) + && !POINTER_TYPE_P (TREE_TYPE (scev))) + return false; + switch (TREE_CODE (scev)) { case PLUS_EXPR: diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index 7e23c9d..d15f0b3 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -647,14 +647,9 @@ scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, mpz_t k) { mpz_t val; ppl_Coefficient_t coef; - tree type = TREE_TYPE (cst); mpz_init (val); - - /* Necessary to not get "-1 = 2^n - 1". */ - mpz_set_double_int (val, double_int_sext (tree_to_double_int (cst), - TYPE_PRECISION (type)), false); - + tree_int_to_gmp (cst, val); mpz_mul (val, val, k); ppl_new_Coefficient (&coef); ppl_assign_Coefficient_from_mpz_t (coef, val); diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 4ff8a10..1f8d049 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2011-07-23 Sebastian Pop <sebastian....@amd.com> + + PR middle-end/47594 + * gfortran.dg/graphite/run-id-pr47594.f90: New. + 2011-08-01 Jason Merrill <ja...@redhat.com> PR c++/49932 diff --git a/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90 b/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90 new file mode 100644 index 0000000..7f36fc6 --- /dev/null +++ b/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90 @@ -0,0 +1,35 @@ +! { dg-options "-O2 -fgraphite-identity" } + + Subroutine foo (N, M) + Integer N + Integer M + integer A(8,16) + integer B(8) + + B = (/ 2, 3, 5, 7, 11, 13, 17, 23 /) + + do I = 1, N + do J = I, M + A(J,2) = B(J) + end do + end do + + do I = 1, N + do J = I, M + if (A(J,2) /= B(J)) then + call abort () + endif + end do + end do + + Return + end + + + program main + + Call foo (16, 8) + + stop + end + diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 2ee3f6e..3bd9511 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -618,7 +618,7 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final, struct tree_niter_desc *niter, bool exit_must_be_taken, bounds *bnds) { - tree niter_type = unsigned_type_for (type); + tree niter_type = POINTER_TYPE_P (type) ? unsigned_type_for (type) : type; tree s, c, d, bits, assumption, tmp, bound; mpz_t max; @@ -627,10 +627,9 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final, niter->cmp = NE_EXPR; /* Rearrange the terms so that we get inequality S * i <> C, with S - positive. Also cast everything to the unsigned type. If IV does - not overflow, BNDS bounds the value of C. Also, this is the - case if the computation |FINAL - IV->base| does not overflow, i.e., - if BNDS->below in the result is nonnegative. */ + positive. If IV does not overflow, BNDS bounds the value of C. + Also, this is the case if the computation |FINAL - IV->base| does + not overflow, i.e., if BNDS->below in the result is nonnegative. */ if (tree_int_cst_sign_bit (iv->step)) { s = fold_convert (niter_type, @@ -648,6 +647,30 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final, fold_convert (niter_type, iv->base)); } + if ((TREE_CODE_CLASS (TREE_CODE (c)) == tcc_constant && TREE_OVERFLOW (c)) + || (TREE_CODE_CLASS (TREE_CODE (s)) == tcc_constant && TREE_OVERFLOW (s))) + { + niter_type = unsigned_type_for (type); + + if (tree_int_cst_sign_bit (iv->step)) + { + s = fold_convert (niter_type, + fold_build1 (NEGATE_EXPR, type, iv->step)); + c = fold_build2 (MINUS_EXPR, niter_type, + fold_convert (niter_type, iv->base), + fold_convert (niter_type, final)); + bounds_negate (bnds); + } + else + { + s = fold_convert (niter_type, iv->step); + c = fold_build2 (MINUS_EXPR, niter_type, + fold_convert (niter_type, final), + fold_convert (niter_type, iv->base)); + + } + } + mpz_init (max); number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds, exit_must_be_taken); @@ -663,7 +686,12 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final, /* Let nsd (step, size of mode) = d. If d does not divide c, the loop is infinite. Otherwise, the number of iterations is - (inverse(s/d) * (c/d)) mod (size of mode/d). */ + (inverse(s/d) * (c/d)) mod (size of mode/d). To compute this, we + need unsigned types, otherwise we end on overflows. */ + niter_type = unsigned_type_for (type); + s = fold_convert (niter_type, s); + c = fold_convert (niter_type, c); + bits = num_ending_zeros (s); bound = build_low_bits_mask (niter_type, (TYPE_PRECISION (niter_type) @@ -1022,7 +1050,7 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1, struct tree_niter_desc *niter, bool exit_must_be_taken, bounds *bnds) { - tree niter_type = unsigned_type_for (type); + tree niter_type = POINTER_TYPE_P (type) ? unsigned_type_for (type) : type; tree delta, step, s; mpz_t mstep, tmp; @@ -1043,6 +1071,15 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1, fold_convert (niter_type, iv1->base), fold_convert (niter_type, iv0->base)); + if (TREE_CODE_CLASS (TREE_CODE (delta)) == tcc_constant + && TREE_OVERFLOW (delta)) + { + niter_type = unsigned_type_for (type); + delta = fold_build2 (MINUS_EXPR, niter_type, + fold_convert (niter_type, iv1->base), + fold_convert (niter_type, iv0->base)); + } + /* First handle the special case that the step is +-1. */ if ((integer_onep (iv0->step) && integer_zerop (iv1->step)) || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step))) @@ -1098,7 +1135,11 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1, /* We determine the number of iterations as (delta + step - 1) / step. For this to work, we must know that iv1->base >= iv0->base - step + 1, - otherwise the loop does not roll. */ + otherwise the loop does not roll. To compute the division, we + use unsigned types. */ + niter_type = unsigned_type_for (type); + step = fold_convert (niter_type, step); + delta = fold_convert (niter_type, delta); assert_loop_rolls_lt (type, iv0, iv1, niter, bnds); s = fold_build2 (MINUS_EXPR, niter_type, @@ -1305,7 +1346,7 @@ number_of_iterations_cond (struct loop *loop, /* If the loop exits immediately, there is nothing to do. */ if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base))) { - niter->niter = build_zero_cst (unsigned_type_for (type)); + niter->niter = build_zero_cst (type); niter->max = double_int_zero; return true; } @@ -1946,7 +1987,7 @@ find_loop_niter (struct loop *loop, edge *exit) { /* We exit in the first iteration through this exit. We won't find anything better. */ - niter = build_zero_cst (unsigned_type_node); + niter = build_zero_cst (integer_type_node); *exit = ex; break; } @@ -2250,7 +2291,7 @@ loop_niter_by_eval (struct loop *loop, edge exit) fprintf (dump_file, "Proved that loop %d iterates %d times using brute force.\n", loop->num, i); - return build_int_cst (unsigned_type_node, i); + return build_int_cst (integer_type_node, i); } for (j = 0; j < 2; j++) -- 1.7.4.1