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

login
register
mail settings
Submitter Sebastian Pop
Date June 29, 2011, 5:35 p.m.
Message ID <1309368922-25238-7-git-send-email-sebpop@gmail.com>
Download mbox | patch
Permalink /patch/102650/
State New
Headers show

Comments

Sebastian Pop - June 29, 2011, 5:35 p.m.
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
Tobias Grosser - June 29, 2011, 11:34 p.m.
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

Patch

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;
+}