[PATCH 3/6] Fix PR47654: Loop blocking should strip-mine at least two loops.

[PATCH 3/6] Fix PR47654: Loop blocking should strip-mine at least two loops.

[Sebastian Pop]

2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>

	PR tree-optimization/47654
	* graphite-blocking.c (pbb_strip_mine_time_depth): Do not return bool.
	(lst_do_strip_mine_loop): Return an int.
	(lst_do_strip_mine): Same.
	(scop_do_strip_mine): Same.
	(scop_do_block): Loop blocking should strip-mine at least two loops.
	* graphite-interchange.c (lst_interchange_select_outer): Return an int.
	(scop_do_interchange): Same.
	* graphite-poly.h (scop_do_interchange): Update declaration.
	(scop_do_strip_mine): Same.

	* gcc.dg/graphite/block-pr47654.c: New.
---
 gcc/ChangeLog                                 |   13 +++++
 gcc/graphite-blocking.c                       |   59 +++++++++++--------------
 gcc/graphite-interchange.c                    |   21 +++++----
 gcc/graphite-poly.h                           |    4 +-
 gcc/testsuite/ChangeLog                       |    5 ++
 gcc/testsuite/gcc.dg/graphite/block-pr47654.c |   25 ++++++++++
 6 files changed, 82 insertions(+), 45 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/graphite/block-pr47654.c

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index b0e3173..828559a 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,18 @@
 2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>
 
+	PR tree-optimization/47654
+	* graphite-blocking.c (pbb_strip_mine_time_depth): Do not return bool.
+	(lst_do_strip_mine_loop): Return an int.
+	(lst_do_strip_mine): Same.
+	(scop_do_strip_mine): Same.
+	(scop_do_block): Loop blocking should strip-mine at least two loops.
+	* graphite-interchange.c (lst_interchange_select_outer): Return an int.
+	(scop_do_interchange): Same.
+	* graphite-poly.h (scop_do_interchange): Update declaration.
+	(scop_do_strip_mine): Same.
+
+2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>
+
 	* graphite-ppl.h (value_max): Correct computation of max.
 
 2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>
diff --git a/gcc/graphite-blocking.c b/gcc/graphite-blocking.c
index bcd077a..967de9d 100644
--- a/gcc/graphite-blocking.c
+++ b/gcc/graphite-blocking.c
@@ -89,7 +89,7 @@ along with GCC; see the file COPYING3.  If not see
    # }
 */
 
-static bool
+static void
 pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride)
 {
   ppl_dimension_type iter, dim, strip;
@@ -151,8 +151,6 @@ pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride)
     ppl_Polyhedron_add_constraint (res, new_cstr);
     ppl_delete_Constraint (new_cstr);
   }
-
-  return true;
 }
 
 /* Returns true when strip mining with STRIDE of the loop LST is
@@ -177,10 +175,10 @@ lst_strip_mine_profitable_p (lst_p lst, int stride)
   return res;
 }
 
-/* Strip-mines all the loops of LST with STRIDE.  Return true if it
-   did strip-mined some loops.  */
+/* Strip-mines all the loops of LST with STRIDE.  Return the number of
+   loops strip-mined.  */
 
-static bool
+static int
 lst_do_strip_mine_loop (lst_p lst, int depth, int stride)
 {
   int i;
@@ -188,26 +186,26 @@ lst_do_strip_mine_loop (lst_p lst, int depth, int stride)
   poly_bb_p pbb;
 
   if (!lst)
-    return false;
+    return 0;
 
   if (LST_LOOP_P (lst))
     {
-      bool res = false;
+      int res = 0;
 
       FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
-	res |= lst_do_strip_mine_loop (l, depth, stride);
+	res += lst_do_strip_mine_loop (l, depth, stride);
 
       return res;
     }
 
   pbb = LST_PBB (lst);
-  return pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth),
-				    stride);
+  pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth), stride);
+  return 1;
 }
 
 /* Strip-mines all the loops of LST with STRIDE.  When STRIDE is zero,
-   read the stride from the PARAM_LOOP_BLOCK_TILE_SIZE.  Return true
-   if it did strip-mined some loops.
+   read the stride from the PARAM_LOOP_BLOCK_TILE_SIZE.  Return the
+   number of strip-mined loops.
 
    Strip mining transforms a loop
 
@@ -221,12 +219,12 @@ lst_do_strip_mine_loop (lst_p lst, int depth, int stride)
    |     S (i = k + j);
 */
 
-static bool
+static int
 lst_do_strip_mine (lst_p lst, int stride)
 {
   int i;
   lst_p l;
-  bool res = false;
+  int res = 0;
   int depth;
 
   if (!stride)
@@ -237,23 +235,23 @@ lst_do_strip_mine (lst_p lst, int stride)
     return false;
 
   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
-    res |= lst_do_strip_mine (l, stride);
+    res += lst_do_strip_mine (l, stride);
 
   depth = lst_depth (lst);
   if (depth >= 0
       && lst_strip_mine_profitable_p (lst, stride))
     {
-      res |= lst_do_strip_mine_loop (lst, lst_depth (lst), stride);
+      res += lst_do_strip_mine_loop (lst, lst_depth (lst), stride);
       lst_add_loop_under_loop (lst);
     }
 
   return res;
 }
 
-/* Strip mines all the loops in SCOP.  Returns true when some loops
-   have been strip-mined.  */
+/* Strip mines all the loops in SCOP.  Returns the number of
+   strip-mined loops.  */
 
-bool
+int
 scop_do_strip_mine (scop_p scop, int stride)
 {
   return lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), stride);
@@ -265,27 +263,22 @@ scop_do_strip_mine (scop_p scop, int stride)
 bool
 scop_do_block (scop_p scop)
 {
-  bool strip_mined = false;
-  bool interchanged = false;
-
   store_scattering (scop);
 
-  strip_mined = lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), 0);
-  interchanged = scop_do_interchange (scop);
-
-  /* If we don't interchange loops, the strip mine alone will not be
-     profitable, and the transform is not a loop blocking: so revert
-     the transform.  */
-  if (!interchanged)
+  /* If we don't strip mine at least two loops, or not interchange
+     loops, the strip mine alone will not be profitable, and the
+     transform is not a loop blocking: so revert the transform.  */
+  if (lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), 0) < 2
+      || scop_do_interchange (scop) == 0)
     {
       restore_scattering (scop);
       return false;
     }
-  else if (strip_mined && interchanged
-	   && dump_file && (dump_flags & TDF_DETAILS))
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "SCoP will be loop blocked.\n");
 
-  return strip_mined || interchanged;
+  return true;
 }
 
 #endif
diff --git a/gcc/graphite-interchange.c b/gcc/graphite-interchange.c
index 934839a..cb4d32c 100644
--- a/gcc/graphite-interchange.c
+++ b/gcc/graphite-interchange.c
@@ -664,27 +664,27 @@ lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer,
 }
 
 /* Interchanges all the loops of LOOP and the loops of its body that
-   are considered profitable to interchange.  Return true if it did
-   interchanged some loops.  OUTER is the index in LST_SEQ (LOOP) that
+   are considered profitable to interchange.  Return the number of
+   interchanged loops.  OUTER is the index in LST_SEQ (LOOP) that
    points to the next outer loop to be considered for interchange.  */
 
-static bool
+static int
 lst_interchange_select_outer (scop_p scop, lst_p loop, int outer)
 {
   lst_p l;
-  bool res = false;
+  int res = 0;
   int i = 0;
   lst_p father;
 
   if (!loop || !LST_LOOP_P (loop))
-    return false;
+    return 0;
 
   father = LST_LOOP_FATHER (loop);
   if (father)
     {
       while (lst_interchange_select_inner (scop, father, outer, loop))
 	{
-	  res = true;
+	  res++;
 	  loop = VEC_index (lst_p, LST_SEQ (father), outer);
 	}
     }
@@ -692,17 +692,18 @@ lst_interchange_select_outer (scop_p scop, lst_p loop, int outer)
   if (LST_LOOP_P (loop))
     FOR_EACH_VEC_ELT (lst_p, LST_SEQ (loop), i, l)
       if (LST_LOOP_P (l))
-	res |= lst_interchange_select_outer (scop, l, i);
+	res += lst_interchange_select_outer (scop, l, i);
 
   return res;
 }
 
-/* Interchanges all the loop depths that are considered profitable for SCOP.  */
+/* Interchanges all the loop depths that are considered profitable for
+   SCOP.  Return the number of interchanged loops.  */
 
-bool
+int
 scop_do_interchange (scop_p scop)
 {
-  bool res = lst_interchange_select_outer
+  int res = lst_interchange_select_outer
     (scop, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
 
   lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop));
diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h
index 3bf87b0..417e99e 100644
--- a/gcc/graphite-poly.h
+++ b/gcc/graphite-poly.h
@@ -410,8 +410,8 @@ extern void print_iteration_domain (FILE *, poly_bb_p, int);
 extern void print_iteration_domains (FILE *, scop_p, int);
 extern void debug_iteration_domain (poly_bb_p, int);
 extern void debug_iteration_domains (scop_p, int);
-extern bool scop_do_interchange (scop_p);
-extern bool scop_do_strip_mine (scop_p, int);
+extern int scop_do_interchange (scop_p);
+extern int scop_do_strip_mine (scop_p, int);
 extern bool scop_do_block (scop_p);
 extern bool flatten_all_loops (scop_p);
 extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, mpz_t);
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index d30d8b0..6f35b5e 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>
+
+	PR tree-optimization/47654
+	* gcc.dg/graphite/block-pr47654.c: New.
+
 2011-06-29  Jason Merrill  <jason@redhat.com>
 
 	PR c++/45923
diff --git a/gcc/testsuite/gcc.dg/graphite/block-pr47654.c b/gcc/testsuite/gcc.dg/graphite/block-pr47654.c
new file mode 100644
index 0000000..9cdeb0c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/block-pr47654.c
@@ -0,0 +1,25 @@
+int a[128][40];
+
+void __attribute__ ((noinline, noclone))
+foo (void)
+{
+  int i, j;
+  for (i = 0; i < 40; i++)
+    for (j = 0; j < 128; j++)
+      a[j][i] = 4;
+}
+
+int
+main ()
+{
+  int i, j;
+  foo ();
+  for (i = 0; i < 40; i++)
+    for (j = 0; j < 128; j++)
+      if (a[j][i] != 4)
+	__builtin_abort ();
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-not "will be loop blocked" "graphite" } } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
-- 
1.7.4.1

[PATCH 0/6] Fix PR47654

[Sebastian Pop]

Hi,
the following patch set fixes PR47654:

  Correct typo.
  Correct computation of max.
  Fix PR47654: Loop blocking should strip-mine at least two loops.
  Fix computation of precision.
  Compute the type of the IV based only on the CLAST bounds.
  Fix PR47654: Compute LB and UB of a CLAST expression.

First, "Loop blocking should strip-mine at least two loops" disables
loop blocking when the strip mine is not applied to at least two
loops.  In the testcase of this PR we have the first loop that does
not contain enough iterations to be strip mined:

  for (i = 0; i < 40; i++)
    for (j = 0; j < 128; j++)
      a[j][i] = 4;

The second interesting patch "Fix computation of precision" uses the
mpz_sizeinbase function instead of computing the log of the gmp value.

"Compute the type of the IV based only on the CLAST bounds" removes
the computation of the type of the induction variable based on the
polyhedral representation: this is a redundant information at the code
generation level, as cloog has already integrated this info in the
CLAST.

Finally, "Compute LB and UB of a CLAST expression" fixes the root
cause of PR47654: it reimplements the type computation based on the
low and up bounds of CLAST expressions.

This patch set passed bootstrap and test c,c++,fortran on amd64-linux.
Full bootstrap and test in progress on amd64-linux.  Ok for trunk?

Thanks,
Sebastian

 gcc/ChangeLog                                  |   53 +++
 gcc/graphite-blocking.c                        |   59 ++--
 gcc/graphite-clast-to-gimple.c                 |  417 ++++++++++--------------
 gcc/graphite-interchange.c                     |   21 +-
 gcc/graphite-poly.h                            |    4 +-
 gcc/graphite-ppl.h                             |   14 +-
 gcc/testsuite/ChangeLog                        |   10 +
 gcc/testsuite/gcc.dg/graphite/block-pr47654.c  |   25 ++
 gcc/testsuite/gcc.dg/graphite/run-id-pr47654.c |   24 ++
 9 files changed, 343 insertions(+), 284 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/graphite/block-pr47654.c
 create mode 100644 gcc/testsuite/gcc.dg/graphite/run-id-pr47654.c

-- 
1.7.4.1

[PATCH 1/6] Correct typo.

[Sebastian Pop]

2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>

	* graphite-clast-to-gimple.c (clast_name_to_index): Add missing space.
---
 gcc/ChangeLog                  |    4 ++++
 gcc/graphite-clast-to-gimple.c |    2 +-
 2 files changed, 5 insertions(+), 1 deletions(-)

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index e37d823..8be5adb 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,7 @@
+2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>
+
+	* graphite-clast-to-gimple.c (clast_name_to_index): Add missing space.
+
 2011-06-29  Eric Botcazou  <ebotcazou@adacore.com>
 
 	PR tree-optimization/49539
diff --git a/gcc/graphite-clast-to-gimple.c b/gcc/graphite-clast-to-gimple.c
index c8356d3..4a4c3d2 100644
--- a/gcc/graphite-clast-to-gimple.c
+++ b/gcc/graphite-clast-to-gimple.c
@@ -88,7 +88,7 @@ clast_name_to_index (clast_name_p name, htab_t index_table)
 
 #ifdef CLOOG_ORG
   gcc_assert (name->type == clast_expr_name);
-  tmp.name = ((const struct clast_name*) name)->name;
+  tmp.name = ((const struct clast_name *) name)->name;
 #else
   tmp.name = name;
 #endif
-- 
1.7.4.1

[PATCH 6/6] Fix PR47654: Compute LB and UB of a CLAST expression.

[Sebastian Pop]

2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>

	PR tree-optimization/47654
	* graphite-clast-to-gimple.c (gcc_type_for_value): Removed.
	(gcc_type_for_clast_term): Removed.
	(gcc_type_for_clast_red): Removed.
	(gcc_type_for_clast_bin): Removed.
	(lb_ub_for_expr_name): New.
	(lb_ub_for_term): New.
	(lb_ub_for_expr): New.
	(lb_ub_for_red): New.
	(lb_ub_for_bin): New.
	(gcc_type_for_clast_expr): Reimplemented.
	* graphite-ppl.h (value_min): New.

	* gcc.dg/graphite/run-id-pr47654.c: New.
---
 gcc/ChangeLog                                  |   15 ++
 gcc/graphite-clast-to-gimple.c                 |  281 ++++++++++++++++--------
 gcc/graphite-ppl.h                             |   11 +
 gcc/testsuite/ChangeLog                        |    5 +
 gcc/testsuite/gcc.dg/graphite/run-id-pr47654.c |   24 ++
 5 files changed, 240 insertions(+), 96 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/graphite/run-id-pr47654.c

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 3117f23..f69f7f8 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,20 @@
 2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>
 
+	PR tree-optimization/47654
+	* graphite-clast-to-gimple.c (gcc_type_for_value): Removed.
+	(gcc_type_for_clast_term): Removed.
+	(gcc_type_for_clast_red): Removed.
+	(gcc_type_for_clast_bin): Removed.
+	(lb_ub_for_expr_name): New.
+	(lb_ub_for_term): New.
+	(lb_ub_for_expr): New.
+	(lb_ub_for_red): New.
+	(lb_ub_for_bin): New.
+	(gcc_type_for_clast_expr): Reimplemented.
+	* graphite-ppl.h (value_min): New.
+
+2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>
+
 	* graphite-clast-to-gimple.c (compute_bounds_for_level): Removed.
 	(compute_type_for_level): Removed.
 	(clast_get_body_of_loop): Removed.
diff --git a/gcc/graphite-clast-to-gimple.c b/gcc/graphite-clast-to-gimple.c
index c8d76c1..686c921 100644
--- a/gcc/graphite-clast-to-gimple.c
+++ b/gcc/graphite-clast-to-gimple.c
@@ -379,147 +379,236 @@ clast_to_gcc_expression (tree type, struct clast_expr *e,
   return NULL_TREE;
 }
 
-/* Return a type that could represent the values between LOW and UP.
-   The value of LOW can be bigger than UP.  */
+/* Return the lower bound LB and upper bound UB of the clast_name N.  */
 
-static tree
-gcc_type_for_interval (mpz_t low, mpz_t up)
+static void
+lb_ub_for_name (clast_name_p n, sese region, VEC (tree, heap) *newivs,
+		htab_t newivs_index, htab_t params_index, mpz_t lb, mpz_t ub)
 {
-  bool unsigned_p;
-  tree type;
-  enum machine_mode mode;
-  int precision = MAX (mpz_sizeinbase (low, 2),
-		       mpz_sizeinbase (up, 2));
-
-  if (precision > BITS_PER_WORD)
-    {
-      gloog_error = true;
-      return integer_type_node;
-    }
+  tree l, u;
+  tree type = TREE_TYPE (clast_name_to_gcc (n, region, newivs,
+					    newivs_index, params_index));
 
-  if (mpz_cmp (low, up) <= 0)
-    unsigned_p = (mpz_sgn (low) >= 0);
+  if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
+    l = lower_bound_in_type (type, type);
   else
-    unsigned_p = (mpz_sgn (up) >= 0);
+    l = TYPE_MIN_VALUE (type);
 
-  mode = smallest_mode_for_size (precision, MODE_INT);
-  precision = GET_MODE_PRECISION (mode);
-  type = build_nonstandard_integer_type (precision, unsigned_p);
-
-  if (!type)
-    {
-      gloog_error = true;
-      return integer_type_node;
-    }
+  if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
+    u = upper_bound_in_type (type, type);
+  else
+    u = TYPE_MAX_VALUE (type);
 
-  return type;
+  tree_int_to_gmp (l, lb);
+  tree_int_to_gmp (u, ub);
 }
 
-/* Return a type that could represent the integer value VAL, or
-   otherwise return NULL_TREE.  */
-
-static tree
-gcc_type_for_value (mpz_t val)
-{
-  return gcc_type_for_interval (val, val);
-}
+/* Return the lower bound LB and upper bound UB of the clast_term T.  */
 
-/* Return the type for the clast_term T used in STMT.  */
-
-static tree
-gcc_type_for_clast_term (struct clast_term *t,
-			 sese region, VEC (tree, heap) *newivs,
-			 htab_t newivs_index, htab_t params_index)
+static void
+lb_ub_for_term (struct clast_term *t, sese region,
+		VEC (tree, heap) *newivs, htab_t newivs_index,
+		htab_t params_index, mpz_t lb, mpz_t ub)
 {
   gcc_assert (t->expr.type == clast_expr_term);
 
-  if (!t->var)
-    return gcc_type_for_value (t->val);
-
-  return TREE_TYPE (clast_name_to_gcc (t->var, region, newivs,
-				       newivs_index, params_index));
+  if (t->var)
+    {
+      mpz_t v;
+      lb_ub_for_name ((clast_name_p) (t->var), region, newivs, newivs_index,
+		      params_index, lb, ub);
+      mpz_init (v);
+      mpz_abs (v, t->val);
+      mpz_mul (lb, lb, v);
+      mpz_mul (ub, ub, v);
+      mpz_clear (v);
+    }
+  else
+    {
+      mpz_set (lb, t->val);
+      mpz_set (ub, t->val);
+    }
 }
 
-static tree
-gcc_type_for_clast_expr (struct clast_expr *, sese,
-			 VEC (tree, heap) *, htab_t, htab_t);
+static void
+lb_ub_for_expr (struct clast_expr *, sese, VEC (tree, heap) *, htab_t, htab_t,
+		mpz_t, mpz_t);
 
-/* Return the type for the clast_reduction R used in STMT.  */
+/* Return the lower bound LB and upper bound UB of the clast_reduction R.  */
 
-static tree
-gcc_type_for_clast_red (struct clast_reduction *r, sese region,
-			VEC (tree, heap) *newivs,
-			htab_t newivs_index, htab_t params_index)
+static void
+lb_ub_for_red (struct clast_reduction *r, sese region,
+	       VEC (tree, heap) *newivs, htab_t newivs_index,
+	       htab_t params_index, mpz_t lb, mpz_t ub)
 {
   int i;
-  tree type = NULL_TREE;
+  mpz_t l, u;
 
-  if (r->n == 1)
-    return gcc_type_for_clast_expr (r->elts[0], region, newivs,
-				    newivs_index, params_index);
+  lb_ub_for_expr (r->elts[0], region, newivs, newivs_index, params_index,
+		  lb, ub);
 
-  switch (r->type)
-    {
-    case clast_red_sum:
-    case clast_red_min:
-    case clast_red_max:
-      type = gcc_type_for_clast_expr (r->elts[0], region, newivs,
-				      newivs_index, params_index);
-      for (i = 1; i < r->n; i++)
-	type = max_precision_type (type, gcc_type_for_clast_expr
-				   (r->elts[i], region, newivs,
-				    newivs_index, params_index));
+  if (r->n == 1)
+    return;
 
-      return type;
+  mpz_init (l);
+  mpz_init (u);
 
-    default:
-      break;
+  for (i = 1; i < r->n; i++)
+    {
+      lb_ub_for_expr (r->elts[i], region, newivs, newivs_index, params_index,
+		      l, u);
+      switch (r->type)
+	{
+	case clast_red_sum:
+	  mpz_add (lb, lb, l);
+	  mpz_add (ub, ub, u);
+	  break;
+
+	case clast_red_min:
+	  value_min (lb, lb, l);
+	  value_min (ub, ub, u);
+	  break;
+
+	case clast_red_max:
+	  value_max (lb, lb, l);
+	  value_max (ub, ub, u);
+	  break;
+
+	default:
+	  gcc_unreachable ();
+	}
     }
 
-  gcc_unreachable ();
-  return NULL_TREE;
+  mpz_clear (l);
+  mpz_clear (u);
 }
 
 /* Return the type for the clast_binary B used in STMT.  */
 
-static tree
-gcc_type_for_clast_bin (struct clast_binary *b,
-			sese region, VEC (tree, heap) *newivs,
-			htab_t newivs_index, htab_t params_index)
+static void
+lb_ub_for_bin (struct clast_binary *b, sese region,
+	       VEC (tree, heap) *newivs, htab_t newivs_index,
+	       htab_t params_index, mpz_t lb, mpz_t ub)
 {
-  tree l = gcc_type_for_clast_expr ((struct clast_expr *) b->LHS, region,
-				    newivs, newivs_index, params_index);
-  tree r = gcc_type_for_value (b->RHS);
-  return max_signed_precision_type (l, r);
+  lb_ub_for_expr ((struct clast_expr *) b->LHS, region, newivs, newivs_index,
+		  params_index, lb, ub);
+
+  switch (b->type)
+    {
+    case clast_bin_cdiv:
+      mpz_cdiv_q (lb, lb, b->RHS);
+      mpz_cdiv_q (ub, ub, b->RHS);
+      break;
+
+    case clast_bin_fdiv:
+      mpz_fdiv_q (lb, lb, b->RHS);
+      mpz_fdiv_q (ub, ub, b->RHS);
+      break;
+
+    case clast_bin_div:
+      mpz_tdiv_q (lb, lb, b->RHS);
+      mpz_tdiv_q (ub, ub, b->RHS);
+      break;
+
+    case clast_bin_mod:
+      mpz_mod (lb, lb, b->RHS);
+      mpz_mod (ub, ub, b->RHS);
+      break;
+
+    default:
+      gcc_unreachable ();
+    }
 }
 
-/* Returns the type for the CLAST expression E when used in statement
-   STMT.  */
+/* Return the lower bound LB and upper bound UB of the clast_expr E.  */
 
-static tree
-gcc_type_for_clast_expr (struct clast_expr *e,
-			 sese region, VEC (tree, heap) *newivs,
-			 htab_t newivs_index, htab_t params_index)
+static void
+lb_ub_for_expr (struct clast_expr *e, sese region,
+		VEC (tree, heap) *newivs, htab_t newivs_index,
+		htab_t params_index, mpz_t lb, mpz_t ub)
 {
   switch (e->type)
     {
     case clast_expr_term:
-      return gcc_type_for_clast_term ((struct clast_term *) e, region,
-				      newivs, newivs_index, params_index);
+      lb_ub_for_term ((struct clast_term *) e, region, newivs,
+		      newivs_index, params_index, lb, ub);
+      break;
 
     case clast_expr_red:
-      return gcc_type_for_clast_red ((struct clast_reduction *) e, region,
-				     newivs, newivs_index, params_index);
+      lb_ub_for_red ((struct clast_reduction *) e, region, newivs,
+		     newivs_index, params_index, lb, ub);
+      break;
 
     case clast_expr_bin:
-      return gcc_type_for_clast_bin ((struct clast_binary *) e, region,
-				     newivs, newivs_index, params_index);
+      lb_ub_for_bin ((struct clast_binary *) e, region, newivs,
+		     newivs_index, params_index, lb, ub);
+      break;
+
+    case clast_expr_name:
+      lb_ub_for_name ((clast_name_p) e, region,
+		      newivs, newivs_index, params_index, lb, ub);
+      break;
 
     default:
       gcc_unreachable ();
     }
+}
 
-  return NULL_TREE;
+/* Return a type that could represent the values between LOW and UP.
+   The value of LOW can be bigger than UP.  */
+
+static tree
+gcc_type_for_interval (mpz_t low, mpz_t up)
+{
+  bool unsigned_p;
+  tree type;
+  enum machine_mode mode;
+  int precision = MAX (mpz_sizeinbase (low, 2),
+		       mpz_sizeinbase (up, 2));
+
+  if (precision > BITS_PER_WORD)
+    {
+      gloog_error = true;
+      return integer_type_node;
+    }
+
+  if (mpz_cmp (low, up) <= 0)
+    unsigned_p = (mpz_sgn (low) >= 0);
+  else
+    unsigned_p = (mpz_sgn (up) >= 0);
+
+  mode = smallest_mode_for_size (precision, MODE_INT);
+  precision = GET_MODE_PRECISION (mode);
+  type = build_nonstandard_integer_type (precision, unsigned_p);
+
+  if (!type)
+    {
+      gloog_error = true;
+      return integer_type_node;
+    }
+
+  return type;
+}
+
+/* Returns the type for the CLAST expression E in REGION.  */
+
+static tree
+gcc_type_for_clast_expr (struct clast_expr *e,
+			 sese region, VEC (tree, heap) *newivs,
+			 htab_t newivs_index, htab_t params_index)
+{
+  mpz_t lb, ub;
+  tree type;
+
+  mpz_init (lb);
+  mpz_init (ub);
+
+  lb_ub_for_expr (e, region, newivs, newivs_index, params_index, lb, ub);
+  type = gcc_type_for_interval (lb, ub);
+
+  mpz_clear (lb);
+  mpz_clear (ub);
+  return type;
 }
 
 /* Returns the type for the equation CLEQ.  */
diff --git a/gcc/graphite-ppl.h b/gcc/graphite-ppl.h
index 49bde61..5820e19 100644
--- a/gcc/graphite-ppl.h
+++ b/gcc/graphite-ppl.h
@@ -124,6 +124,17 @@ ppl_set_coef_tree (ppl_Linear_Expression_t e, ppl_dimension_type i, tree x)
   mpz_clear (v);
 }
 
+/* Sets RES to the min of V1 and V2.  */
+
+static inline void
+value_min (mpz_t res, mpz_t v1, mpz_t v2)
+{
+  if (mpz_cmp (v1, v2) < 0)
+    mpz_set (res, v1);
+  else
+    mpz_set (res, v2);
+}
+
 /* Sets RES to the max of V1 and V2.  */
 
 static inline void
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 6f35b5e..760a89f 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,6 +1,11 @@
 2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>
 
 	PR tree-optimization/47654
+	* gcc.dg/graphite/run-id-pr47654.c: New.
+
+2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>
+
+	PR tree-optimization/47654
 	* gcc.dg/graphite/block-pr47654.c: New.
 
 2011-06-29  Jason Merrill  <jason@redhat.com>
diff --git a/gcc/testsuite/gcc.dg/graphite/run-id-pr47654.c b/gcc/testsuite/gcc.dg/graphite/run-id-pr47654.c
new file mode 100644
index 0000000..c257f58
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/run-id-pr47654.c
@@ -0,0 +1,24 @@
+/* { dg-options "-O -floop-block" } */
+
+int a[128][40];
+
+void __attribute__ ((noinline, noclone))
+foo (void)
+{
+  int i, j;
+  for (i = 0; i < 40; i++)
+    for (j = 0; j < 128; j++)
+      a[j][i] = 4;
+}
+
+int
+main ()
+{
+  int i, j;
+  foo ();
+  for (i = 0; i < 40; i++)
+    for (j = 0; j < 128; j++)
+      if (a[j][i] != 4)
+	__builtin_abort ();
+  return 0;
+}
-- 
1.7.4.1

[PATCH 4/6] Fix computation of precision.

[Sebastian Pop]

2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>

	* graphite-clast-to-gimple.c (precision_for_value): Removed.
	(precision_for_interval): Removed.
	(gcc_type_for_interval): Use mpz_sizeinbase.
---
 gcc/ChangeLog                  |    6 +++
 gcc/graphite-clast-to-gimple.c |   77 +++++-----------------------------------
 2 files changed, 15 insertions(+), 68 deletions(-)

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 828559a..0616b10 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,11 @@
 2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>
 
+	* graphite-clast-to-gimple.c (precision_for_value): Removed.
+	(precision_for_interval): Removed.
+	(gcc_type_for_interval): Use mpz_sizeinbase.
+
+2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>
+
 	PR tree-optimization/47654
 	* graphite-blocking.c (pbb_strip_mine_time_depth): Do not return bool.
 	(lst_do_strip_mine_loop): Return an int.
diff --git a/gcc/graphite-clast-to-gimple.c b/gcc/graphite-clast-to-gimple.c
index 4a4c3d2..70031a0 100644
--- a/gcc/graphite-clast-to-gimple.c
+++ b/gcc/graphite-clast-to-gimple.c
@@ -379,72 +379,17 @@ clast_to_gcc_expression (tree type, struct clast_expr *e,
   return NULL_TREE;
 }
 
-/* Return the precision needed to represent the value VAL.  */
-
-static int
-precision_for_value (mpz_t val)
-{
-  mpz_t x, y, two;
-  int precision;
-
-  mpz_init (x);
-  mpz_init (y);
-  mpz_init (two);
-  mpz_set_si (x, 2);
-  mpz_set (y, val);
-  mpz_set_si (two, 2);
-  precision = 1;
-
-  if (mpz_sgn (y) < 0)
-    mpz_neg (y, y);
-
-  while (mpz_cmp (y, x) >= 0)
-    {
-      mpz_mul (x, x, two);
-      precision++;
-    }
-
-  mpz_clear (x);
-  mpz_clear (y);
-  mpz_clear (two);
-
-  return precision;
-}
-
-/* Return the precision needed to represent the values between LOW and
-   UP.  */
-
-static int
-precision_for_interval (mpz_t low, mpz_t up)
-{
-  mpz_t diff;
-  int precision;
-
-  gcc_assert (mpz_cmp (low, up) <= 0);
-
-  mpz_init (diff);
-  mpz_sub (diff, up, low);
-  precision = precision_for_value (diff);
-  mpz_clear (diff);
-
-  return precision;
-}
-
-/* Return a type that could represent the integer value VAL.  */
+/* Return a type that could represent the values between LOW and UP.
+   The value of LOW can be bigger than UP.  */
 
 static tree
 gcc_type_for_interval (mpz_t low, mpz_t up)
 {
-  bool unsigned_p = true;
-  int precision, prec_up, prec_int;
+  bool unsigned_p;
   tree type;
   enum machine_mode mode;
-
-  gcc_assert (mpz_cmp (low, up) <= 0);
-
-  prec_up = precision_for_value (up);
-  prec_int = precision_for_interval (low, up);
-  precision = MAX (prec_up, prec_int);
+  int precision = MAX (mpz_sizeinbase (low, 2),
+		       mpz_sizeinbase (up, 2));
 
   if (precision > BITS_PER_WORD)
     {
@@ -452,14 +397,10 @@ gcc_type_for_interval (mpz_t low, mpz_t up)
       return integer_type_node;
     }
 
-  if (mpz_sgn (low) <= 0)
-    unsigned_p = false;
-
-  else if (precision < BITS_PER_WORD)
-    {
-      unsigned_p = false;
-      precision++;
-    }
+  if (mpz_cmp (low, up) <= 0)
+    unsigned_p = (mpz_sgn (low) >= 0);
+  else
+    unsigned_p = (mpz_sgn (up) >= 0);
 
   mode = smallest_mode_for_size (precision, MODE_INT);
   precision = GET_MODE_PRECISION (mode);
-- 
1.7.4.1

[PATCH 2/6] Correct computation of max.

[Sebastian Pop]

2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>

	* graphite-ppl.h (value_max): Correct computation of max.
---
 gcc/ChangeLog      |    4 ++++
 gcc/graphite-ppl.h |    3 ++-
 2 files changed, 6 insertions(+), 1 deletions(-)

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 8be5adb..b0e3173 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,9 @@
 2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>
 
+	* graphite-ppl.h (value_max): Correct computation of max.
+
+2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>
+
 	* graphite-clast-to-gimple.c (clast_name_to_index): Add missing space.
 
 2011-06-29  Eric Botcazou  <ebotcazou@adacore.com>
diff --git a/gcc/graphite-ppl.h b/gcc/graphite-ppl.h
index 695d01f..49bde61 100644
--- a/gcc/graphite-ppl.h
+++ b/gcc/graphite-ppl.h
@@ -131,7 +131,8 @@ value_max (mpz_t res, mpz_t v1, mpz_t v2)
 {
   if (mpz_cmp (v1, v2) < 0)
     mpz_set (res, v2);
-  mpz_set (res, v1);
+  else
+    mpz_set (res, v1);
 }
 
 /* Builds a new identity map for dimension DIM.  */
-- 
1.7.4.1

[PATCH 5/6] Compute the type of the IV based only on the CLAST bounds.

[Sebastian Pop]

2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>

	* graphite-clast-to-gimple.c (compute_bounds_for_level): Removed.
	(compute_type_for_level): Removed.
	(clast_get_body_of_loop): Removed.
	(gcc_type_for_iv_of_clast_loop): Removed.
	(graphite_create_new_loop): Use max_precision_type.  Compute the type
	of the IV based only on the CLAST bounds.
	(translate_clast_for_loop): Do not pass level to
	graphite_create_new_loop.
---
 gcc/ChangeLog                  |   11 +++++
 gcc/graphite-clast-to-gimple.c |   95 +--------------------------------------
 2 files changed, 14 insertions(+), 92 deletions(-)

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 0616b10..3117f23 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,16 @@
 2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>
 
+	* graphite-clast-to-gimple.c (compute_bounds_for_level): Removed.
+	(compute_type_for_level): Removed.
+	(clast_get_body_of_loop): Removed.
+	(gcc_type_for_iv_of_clast_loop): Removed.
+	(graphite_create_new_loop): Use max_precision_type.  Compute the type
+	of the IV based only on the CLAST bounds.
+	(translate_clast_for_loop): Do not pass level to
+	graphite_create_new_loop.
+
+2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>
+
 	* graphite-clast-to-gimple.c (precision_for_value): Removed.
 	(precision_for_interval): Removed.
 	(gcc_type_for_interval): Use mpz_sizeinbase.
diff --git a/gcc/graphite-clast-to-gimple.c b/gcc/graphite-clast-to-gimple.c
index 70031a0..c8d76c1 100644
--- a/gcc/graphite-clast-to-gimple.c
+++ b/gcc/graphite-clast-to-gimple.c
@@ -603,94 +603,6 @@ graphite_create_new_guard (sese region, edge entry_edge,
   return exit_edge;
 }
 
-/* Compute the lower bound LOW and upper bound UP for the induction
-   variable at LEVEL for the statement PBB, based on the transformed
-   scattering of PBB: T|I|G|Cst, with T the scattering transform, I
-   the iteration domain, and G the context parameters.  */
-
-static void
-compute_bounds_for_level (poly_bb_p pbb, int level, mpz_t low, mpz_t up)
-{
-  ppl_Pointset_Powerset_C_Polyhedron_t ps;
-  ppl_Linear_Expression_t le;
-
-  combine_context_id_scat (&ps, pbb, false);
-
-  /* Prepare the linear expression corresponding to the level that we
-     want to maximize/minimize.  */
-  {
-    ppl_dimension_type dim = pbb_nb_scattering_transform (pbb)
-      + pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
-
-    ppl_new_Linear_Expression_with_dimension (&le, dim);
-    ppl_set_coef (le, 2 * level + 1, 1);
-  }
-
-  ppl_max_for_le_pointset (ps, le, up);
-  ppl_min_for_le_pointset (ps, le, low);
-  ppl_delete_Linear_Expression (le);
-  ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
-}
-
-/* Compute the type for the induction variable at LEVEL for the
-   statement PBB, based on the transformed schedule of PBB.  */
-
-static tree
-compute_type_for_level (poly_bb_p pbb, int level)
-{
-  mpz_t low, up;
-  tree type;
-
-  mpz_init (low);
-  mpz_init (up);
-
-  compute_bounds_for_level (pbb, level, low, up);
-  type = gcc_type_for_interval (low, up);
-
-  mpz_clear (low);
-  mpz_clear (up);
-  return type;
-}
-
-/* Walks a CLAST and returns the first statement in the body of a
-   loop.  */
-
-static struct clast_user_stmt *
-clast_get_body_of_loop (struct clast_stmt *stmt)
-{
-  if (!stmt
-      || CLAST_STMT_IS_A (stmt, stmt_user))
-    return (struct clast_user_stmt *) stmt;
-
-  if (CLAST_STMT_IS_A (stmt, stmt_for))
-    return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
-
-  if (CLAST_STMT_IS_A (stmt, stmt_guard))
-    return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
-
-  if (CLAST_STMT_IS_A (stmt, stmt_block))
-    return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
-
-  gcc_unreachable ();
-}
-
-/* Returns the type for the induction variable for the loop translated
-   from STMT_FOR.  */
-
-static tree
-gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for, int level,
-			       tree lb_type, tree ub_type)
-{
-  struct clast_stmt *stmt = (struct clast_stmt *) stmt_for;
-  struct clast_user_stmt *body = clast_get_body_of_loop (stmt);
-  CloogStatement *cs = body->statement;
-  poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
-
-  return max_signed_precision_type (lb_type, max_precision_type
-				    (ub_type, compute_type_for_level
-				     (pbb, level - 1)));
-}
-
 /* Creates a new LOOP corresponding to Cloog's STMT.  Inserts an
    induction variable for the new LOOP.  New LOOP is attached to CFG
    starting at ENTRY_EDGE.  LOOP is inserted into the loop tree and
@@ -703,13 +615,13 @@ static struct loop *
 graphite_create_new_loop (sese region, edge entry_edge,
 			  struct clast_for *stmt,
 			  loop_p outer, VEC (tree, heap) **newivs,
-			  htab_t newivs_index, htab_t params_index, int level)
+			  htab_t newivs_index, htab_t params_index)
 {
   tree lb_type = gcc_type_for_clast_expr (stmt->LB, region, *newivs,
 					  newivs_index, params_index);
   tree ub_type = gcc_type_for_clast_expr (stmt->UB, region, *newivs,
 					  newivs_index, params_index);
-  tree type = gcc_type_for_iv_of_clast_loop (stmt, level, lb_type, ub_type);
+  tree type = max_precision_type (lb_type, ub_type);
   tree lb = clast_to_gcc_expression (type, stmt->LB, region, *newivs,
 				     newivs_index, params_index);
   tree ub = clast_to_gcc_expression (type, stmt->UB, region, *newivs,
@@ -945,8 +857,7 @@ translate_clast_for_loop (sese region, loop_p context_loop,
 {
   struct loop *loop = graphite_create_new_loop (region, next_e, stmt,
  						context_loop, newivs,
- 						newivs_index, params_index,
-						level);
+						newivs_index, params_index);
   edge last_e = single_exit (loop);
   edge to_body = single_succ_edge (loop->header);
   basic_block after = to_body->dest;
-- 
1.7.4.1

Re: [PATCH 4/6] Fix computation of precision.

[Tobias Grosser]

On 06/29/2011 12:35 PM, Sebastian Pop wrote:
> 2011-06-29  Sebastian Pop<sebastian.pop@amd.com>
>
> 	* graphite-clast-to-gimple.c (precision_for_value): Removed.
> 	(precision_for_interval): Removed.
> 	(gcc_type_for_interval): Use mpz_sizeinbase.
> -/* Return a type that could represent the integer value VAL.  */
> +/* Return a type that could represent the values between LOW and UP.
> +   The value of LOW can be bigger than UP.  */
>
>   static tree
>   gcc_type_for_interval (mpz_t low, mpz_t up)
>   {

Hi Sebastian,

why do we continue to call low 'low' and up 'up', if we actually just 
have two values v1 and v2 where we do not know which one is larger? I 
think this wrong and probably comes because we pass the lower loop bound 
to val_one and the upper loop bound to val_two.

What about:

+/* Return a type that could represent all values between VAL_ONE and
+   VAL_TWO including VAL_ONE and VAL_TWO itself.  There is no
+   constraint on which of the two values is larger.  */

   static tree
- gcc_type_for_interval (mpz_t low, mpz_t up)
+ gcc_type_for_interval (mpz_t val_one, mpz_t val_two)
    {

> -  bool unsigned_p = true;
> -  int precision, prec_up, prec_int;
> +  bool unsigned_p;
>     tree type;
>     enum machine_mode mode;
> -
> -  gcc_assert (mpz_cmp (low, up)<= 0);
> -
> -  prec_up = precision_for_value (up);
> -  prec_int = precision_for_interval (low, up);
> -  precision = MAX (prec_up, prec_int);
> +  int precision = MAX (mpz_sizeinbase (low, 2),
> +		       mpz_sizeinbase (up, 2));
>
>     if (precision>  BITS_PER_WORD)
>       {
> @@ -452,14 +397,10 @@ gcc_type_for_interval (mpz_t low, mpz_t up)
>         return integer_type_node;
>       }
>
> -  if (mpz_sgn (low)<= 0)
> -    unsigned_p = false;
> -
> -  else if (precision<  BITS_PER_WORD)
> -    {
> -      unsigned_p = false;
> -      precision++;
> -    }
> +  if (mpz_cmp (low, up)<= 0)
> +    unsigned_p = (mpz_sgn (low)>= 0);
> +  else
> +    unsigned_p = (mpz_sgn (up)>= 0);

What about?

        unsigned_p = value_min(low, up) >= 0;

(You need to move the implementation of value_min to this patch)

>
>     mode = smallest_mode_for_size (precision, MODE_INT);
>     precision = GET_MODE_PRECISION (mode);

In general the new implementation looks a lot more elegant as the old 
one. What was the problem with the old one? That low could be larger 
than up and that the calculation in precision_for_interval was incorrect 
(or at least not understandable for me)?

The rest of the patch looks good.

Cheers
Tobi

Re: [PATCH 0/6] Fix PR47654

[Tobias Grosser]

On 06/29/2011 12:35 PM, Sebastian Pop wrote:
> Hi,
> the following patch set fixes PR47654:
>
>    Correct typo.
>    Correct computation of max.
>    Fix PR47654: Loop blocking should strip-mine at least two loops.
Those three look OK.

Cheers
Tobi

Re: [PATCH 5/6] Compute the type of the IV based only on the CLAST bounds.

[Tobias Grosser]

On 06/29/2011 12:35 PM, Sebastian Pop wrote:
> 2011-06-29  Sebastian Pop<sebastian.pop@amd.com>
>
> 	* graphite-clast-to-gimple.c (compute_bounds_for_level): Removed.
> 	(compute_type_for_level): Removed.
> 	(clast_get_body_of_loop): Removed.
> 	(gcc_type_for_iv_of_clast_loop): Removed.
> 	(graphite_create_new_loop): Use max_precision_type.  Compute the type
> 	of the IV based only on the CLAST bounds.
> 	(translate_clast_for_loop): Do not pass level to
> 	graphite_create_new_loop.

This one looks also OK.

Re: [PATCH 6/6] Fix PR47654: Compute LB and UB of a CLAST expression.

[Tobias Grosser]

On 06/29/2011 12:35 PM, Sebastian Pop wrote:
> 2011-06-29  Sebastian Pop<sebastian.pop@amd.com>
>
> 	PR tree-optimization/47654
> 	* graphite-clast-to-gimple.c (gcc_type_for_value): Removed.
> 	(gcc_type_for_clast_term): Removed.
> 	(gcc_type_for_clast_red): Removed.
> 	(gcc_type_for_clast_bin): Removed.
> 	(lb_ub_for_expr_name): New.
> 	(lb_ub_for_term): New.
> 	(lb_ub_for_expr): New.
> 	(lb_ub_for_red): New.
> 	(lb_ub_for_bin): New.
> 	(gcc_type_for_clast_expr): Reimplemented.
> 	* graphite-ppl.h (value_min): New.
>
> 	* gcc.dg/graphite/run-id-pr47654.c: New.

I think the approach you are taking here is correct (in terms of not 
producing wrong code).

However I am not sure if this will lead to the smallest type possible. 
As far as I understand you assume for both surrounding induction 
variables and parameters that their lb/ub values are the maximal/minimal 
possible values in their types. This is not incorrect, however I believe 
the constraints in Cloog may provide us with more information, 
especially if the context contains constraints on the parameters.

My dream would be to enhance CLooG such that it can provide information 
about the minimal an maximal value of each clast (sub)expression.

What types would you get for this code (i,j,k,m, n)?

for (i = 0 ; i < 2; i++)
   for (j = i ; j < i + 1; j++)
     for (k = j ; k < j + 1; k++)
       for (m = k ; m < k + 1; m++)
         for (n = m ; n < m + 1; n++)
           A[0] += A[n];

I am a little bit afraid that we will increase the type size by an order 
of magnitude (or at least one bit) for each nesting level.

Cheers
Tobi

Re: [PATCH 4/6] Fix computation of precision.

[Tobias Grosser]

On 06/30/2011 09:50 AM, Sebastian Pop wrote:
> On Wed, Jun 29, 2011 at 18:16, Tobias Grosser<tobias@grosser.es>  wrote:
>> why do we continue to call low 'low' and up 'up', if we actually just have
>> two values v1 and v2 where we do not know which one is larger? I think this
>> wrong and probably comes because we pass the lower loop bound to val_one and
>> the upper loop bound to val_two.
>>
>> What about:
>>
>> +/* Return a type that could represent all values between VAL_ONE and
>> +   VAL_TWO including VAL_ONE and VAL_TWO itself.  There is no
>> +   constraint on which of the two values is larger.  */
>>
>>   static tree
>> - gcc_type_for_interval (mpz_t low, mpz_t up)
>> + gcc_type_for_interval (mpz_t val_one, mpz_t val_two)
>>    {
>>
>
> Sounds good.  I will change the patch.
>
>>> -  bool unsigned_p = true;
>>> -  int precision, prec_up, prec_int;
>>> +  bool unsigned_p;
>>>     tree type;
>>>     enum machine_mode mode;
>>> -
>>> -  gcc_assert (mpz_cmp (low, up)<= 0);
>>> -
>>> -  prec_up = precision_for_value (up);
>>> -  prec_int = precision_for_interval (low, up);
>>> -  precision = MAX (prec_up, prec_int);
>>> +  int precision = MAX (mpz_sizeinbase (low, 2),
>>> +                      mpz_sizeinbase (up, 2));
>>>
>>>     if (precision>    BITS_PER_WORD)
>>>       {
>>> @@ -452,14 +397,10 @@ gcc_type_for_interval (mpz_t low, mpz_t up)
>>>         return integer_type_node;
>>>       }
>>>
>>> -  if (mpz_sgn (low)<= 0)
>>> -    unsigned_p = false;
>>> -
>>> -  else if (precision<    BITS_PER_WORD)
>>> -    {
>>> -      unsigned_p = false;
>>> -      precision++;
>>> -    }
>>> +  if (mpz_cmp (low, up)<= 0)
>>> +    unsigned_p = (mpz_sgn (low)>= 0);
>>> +  else
>>> +    unsigned_p = (mpz_sgn (up)>= 0);
>>
>> What about?
>>
>>        unsigned_p = value_min(low, up)>= 0;
>
> Ok.
>
>>
>> (You need to move the implementation of value_min to this patch)
>>
>>>
>>>     mode = smallest_mode_for_size (precision, MODE_INT);
>>>     precision = GET_MODE_PRECISION (mode);
>>
>> In general the new implementation looks a lot more elegant as the old one.
>> What was the problem with the old one? That low could be larger than up and
>
> I don't think that could happen, given that we have a
> gcc_assert (mpz_cmp (low, up)<= 0);
>
>> that the calculation in precision_for_interval was incorrect (or at least
>> not understandable for me)?
>
> There was an off by one problem in the computation of precision exposed
> by the patch "Compute LB and UB of a CLAST expression".

OK. From my side this patch is fine.

Tobi

Re: [PATCH 4/6] Fix computation of precision.

[Sebastian Pop]

On Wed, Jun 29, 2011 at 18:16, Tobias Grosser <tobias@grosser.es> wrote:
> why do we continue to call low 'low' and up 'up', if we actually just have
> two values v1 and v2 where we do not know which one is larger? I think this
> wrong and probably comes because we pass the lower loop bound to val_one and
> the upper loop bound to val_two.
>
> What about:
>
> +/* Return a type that could represent all values between VAL_ONE and
> +   VAL_TWO including VAL_ONE and VAL_TWO itself.  There is no
> +   constraint on which of the two values is larger.  */
>
>  static tree
> - gcc_type_for_interval (mpz_t low, mpz_t up)
> + gcc_type_for_interval (mpz_t val_one, mpz_t val_two)
>   {
>

Sounds good.  I will change the patch.

>> -  bool unsigned_p = true;
>> -  int precision, prec_up, prec_int;
>> +  bool unsigned_p;
>>    tree type;
>>    enum machine_mode mode;
>> -
>> -  gcc_assert (mpz_cmp (low, up)<= 0);
>> -
>> -  prec_up = precision_for_value (up);
>> -  prec_int = precision_for_interval (low, up);
>> -  precision = MAX (prec_up, prec_int);
>> +  int precision = MAX (mpz_sizeinbase (low, 2),
>> +                      mpz_sizeinbase (up, 2));
>>
>>    if (precision>  BITS_PER_WORD)
>>      {
>> @@ -452,14 +397,10 @@ gcc_type_for_interval (mpz_t low, mpz_t up)
>>        return integer_type_node;
>>      }
>>
>> -  if (mpz_sgn (low)<= 0)
>> -    unsigned_p = false;
>> -
>> -  else if (precision<  BITS_PER_WORD)
>> -    {
>> -      unsigned_p = false;
>> -      precision++;
>> -    }
>> +  if (mpz_cmp (low, up)<= 0)
>> +    unsigned_p = (mpz_sgn (low)>= 0);
>> +  else
>> +    unsigned_p = (mpz_sgn (up)>= 0);
>
> What about?
>
>       unsigned_p = value_min(low, up) >= 0;

Ok.

>
> (You need to move the implementation of value_min to this patch)
>
>>
>>    mode = smallest_mode_for_size (precision, MODE_INT);
>>    precision = GET_MODE_PRECISION (mode);
>
> In general the new implementation looks a lot more elegant as the old one.
> What was the problem with the old one? That low could be larger than up and

I don't think that could happen, given that we have a
gcc_assert (mpz_cmp (low, up)<= 0);

> that the calculation in precision_for_interval was incorrect (or at least
> not understandable for me)?

There was an off by one problem in the computation of precision exposed
by the patch "Compute LB and UB of a CLAST expression".

Sebastian

Re: [PATCH 4/6] Fix computation of precision.

[H.J. Lu]

On Wed, Jun 29, 2011 at 10:35 AM, Sebastian Pop <sebpop@gmail.com> wrote:
> 2011-06-29  Sebastian Pop  <sebastian.pop@amd.com>
>
>        * graphite-clast-to-gimple.c (precision_for_value): Removed.
>        (precision_for_interval): Removed.
>        (gcc_type_for_interval): Use mpz_sizeinbase.
> ---

This caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49649


-- 
H.J.