From 0abb53c250949cd22cacbf3ed0b69604665c2949 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Fri, 29 Jul 2011 14:35:56 -0500
Subject: [PATCH 2/2] Fix PR47594: Build signed niter expressions
2011-07-23 Sebastian Pop <sebastian.pop@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 | 30 +++++++++++------
6 files changed, 80 insertions(+), 17 deletions(-)
create mode 100644 gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90
@@ -1,3 +1,17 @@
+2011-07-23 Sebastian Pop <sebastian.pop@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-07-29 Uros Bizjak <ubizjak@gmail.com>
* config/i386/predicates.md (tp_or_register_operand): Remove predicate.
@@ -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:
@@ -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);
@@ -1,3 +1,8 @@
+2011-07-23 Sebastian Pop <sebastian.pop@amd.com>
+
+ PR middle-end/47594
+ * gfortran.dg/graphite/run-id-pr47594.f90: New.
+
2011-07-29 Rainer Orth <ro@CeBiTec.Uni-Bielefeld.DE>
PR tree-optimization/47407
new file mode 100644
@@ -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
+
@@ -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,
@@ -663,7 +662,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 +1026,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;
@@ -1098,7 +1102,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 +1313,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 +1954,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 +2258,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