Patchwork Fix PR47594: Sign extend constants while translating to Graphite

login
register
mail settings
Submitter Sebastian Pop
Date July 30, 2011, 2:40 a.m.
Message ID <CAFk3UF8its_VK4xHToxsfU=378GKivQLQkUjMyxGKbc8dfitcA@mail.gmail.com>
Download mbox | patch
Permalink /patch/107471/
State New
Headers show

Comments

Sebastian Pop - July 30, 2011, 2:40 a.m.
Hi Richi,

On Thu, Jul 28, 2011 at 03:58, Richard Guenther <rguenther@suse.de> wrote:
> So maybe we can instead try to avoid using unsigned arithmetic
> for symbolic niters if the source does not have it unsigned?

Ok, so what about the attached patch that makes niter use the original
type as much as possible?  I.e. for the trivial cases that don't use division.
Regstrap in progress on amd64-linux.

Sebastian

Patch

From 7535ba784f9f5f0e7583bf77e5baadb386131bd6 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                          |   29 ++++++++++------
 6 files changed, 79 insertions(+), 17 deletions(-)
 create mode 100644 gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 738144d..9b22eed 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-07-29  Uros Bizjak  <ubizjak@gmail.com>
 
 	* config/i386/predicates.md (tp_or_register_operand): Remove predicate.
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 cf5ee2b..55f2e91 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-07-29  Rainer Orth  <ro@CeBiTec.Uni-Bielefeld.DE>
 
 	PR tree-optimization/47407
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..285577d 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,
@@ -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,10 @@  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);
   assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
 
   s = fold_build2 (MINUS_EXPR, niter_type,
@@ -1305,7 +1312,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 +1953,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 +2257,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