[PATCH 2/2] Fix PR47594: Build signed niter expressions

[Sebastian Pop <sebpop at gmail dot com>]

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                          |   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.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-08-01  Richard Henderson  <rth@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.pop@amd.com>
+
+	PR middle-end/47594
+	* gfortran.dg/graphite/run-id-pr47594.f90: New.
+
 2011-08-01  Jason Merrill  <jason@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