[1/2] Fix PR47654: Compute LB and UB of a CLAST expression.

Hi,

this patch reimplements the computation of the GCC type for a CLAST
expression: we now compute the lower and upper bounds of a CLAST
expression before asking the question: which type could represent such
values.  The original implementation was very inaccurate, taking the
max types of binary expressions.  In the case of run-id-pr47654.c, we
ended up generating a signed char type that cannot represent the value
of the sum.

This passed the graphite testsuite.  I am currently regstrapping this
patch on amd64-linux.  Ok for trunk?

Thanks,
Sebastian

2011-02-22  Sebastian Pop  <sebastian.pop@amd.com>

	PR tree-optimization/47654
	* graphite-clast-to-gimple.c (gcc_type_for_interval): Call mpz_swap.
	(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_clast_expr_name): New.
	(lb_ub_for_clast_term): New.
	(lb_ub_for_clast_expr): New.
	(lb_ub_for_clast_red): New.
	(lb_ub_for_clast_bin): New.
	(gcc_type_for_clast_expr): Reimplemented.
	* graphite-ppl.h (value_min): New.
	(value_max): Fixed error.

	* gcc.dg/graphite/run-id-pr47654.c: New.
---
 gcc/ChangeLog                                  |   17 ++
 gcc/graphite-clast-to-gimple.c                 |  223 +++++++++++++++++-------
 gcc/graphite-ppl.h                             |   14 ++-
 gcc/testsuite/ChangeLog                        |    5 +
 gcc/testsuite/gcc.dg/graphite/run-id-pr47654.c |   24 +++
 5 files changed, 215 insertions(+), 68 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/graphite/run-id-pr47654.c

On Mon, 21 Feb 2011, Sebastian Pop wrote:

> Hi,
> 
> this patch reimplements the computation of the GCC type for a CLAST
> expression: we now compute the lower and upper bounds of a CLAST
> expression before asking the question: which type could represent such
> values.  The original implementation was very inaccurate, taking the
> max types of binary expressions.  In the case of run-id-pr47654.c, we
> ended up generating a signed char type that cannot represent the value
> of the sum.

So CLOOG basically assumes infinite precision integers with no
wrap-around?

> This passed the graphite testsuite.  I am currently regstrapping this
> patch on amd64-linux.  Ok for trunk?

Ok.

Thanks,
Richard.

> Thanks,
> Sebastian
> 
> 2011-02-22  Sebastian Pop  <sebastian.pop@amd.com>
> 
> 	PR tree-optimization/47654
> 	* graphite-clast-to-gimple.c (gcc_type_for_interval): Call mpz_swap.
> 	(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_clast_expr_name): New.
> 	(lb_ub_for_clast_term): New.
> 	(lb_ub_for_clast_expr): New.
> 	(lb_ub_for_clast_red): New.
> 	(lb_ub_for_clast_bin): New.
> 	(gcc_type_for_clast_expr): Reimplemented.
> 	* graphite-ppl.h (value_min): New.
> 	(value_max): Fixed error.
> 
> 	* gcc.dg/graphite/run-id-pr47654.c: New.
> ---
>  gcc/ChangeLog                                  |   17 ++
>  gcc/graphite-clast-to-gimple.c                 |  223 +++++++++++++++++-------
>  gcc/graphite-ppl.h                             |   14 ++-
>  gcc/testsuite/ChangeLog                        |    5 +
>  gcc/testsuite/gcc.dg/graphite/run-id-pr47654.c |   24 +++
>  5 files changed, 215 insertions(+), 68 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/graphite/run-id-pr47654.c
> 
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 6c3f6d4..c1676bb 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,20 @@
> +2011-02-22  Sebastian Pop  <sebastian.pop@amd.com>
> +
> +	PR tree-optimization/47654
> +	* graphite-clast-to-gimple.c (gcc_type_for_interval): Call mpz_swap.
> +	(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_clast_expr_name): New.
> +	(lb_ub_for_clast_term): New.
> +	(lb_ub_for_clast_expr): New.
> +	(lb_ub_for_clast_red): New.
> +	(lb_ub_for_clast_bin): New.
> +	(gcc_type_for_clast_expr): Reimplemented.
> +	* graphite-ppl.h (value_min): New.
> +	(value_max): Fixed error.
> +
>  2011-02-14  Ralf Wildenhues  <Ralf.Wildenhues@gmx.de>
>  
>  	* go/gccgo.texi (Top, Import and Export): Fix a typo and a
> diff --git a/gcc/graphite-clast-to-gimple.c b/gcc/graphite-clast-to-gimple.c
> index 47a03d5..1b57618 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
> @@ -431,7 +431,8 @@ precision_for_interval (mpz_t low, mpz_t up)
>    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)
> @@ -441,7 +442,9 @@ gcc_type_for_interval (mpz_t low, mpz_t up)
>    tree type;
>    enum machine_mode mode;
>  
> -  gcc_assert (mpz_cmp (low, up) <= 0);
> +  /* Just swap the two values to satisfy LOW <= UP.  */
> +  if (mpz_cmp (low, up) > 0)
> +    mpz_swap (low, up);
>  
>    prec_up = precision_for_value (up);
>    prec_int = precision_for_interval (low, up);
> @@ -475,111 +478,197 @@ gcc_type_for_interval (mpz_t low, mpz_t up)
>    return type;
>  }
>  
> -/* Return a type that could represent the integer value VAL, or
> -   otherwise return NULL_TREE.  */
> +/* Return the lower bound LB and upper bound UB of the clast_name N.  */
>  
> -static tree
> -gcc_type_for_value (mpz_t val)
> +static void
> +lb_ub_for_clast_expr_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)
>  {
> -  return gcc_type_for_interval (val, val);
> +  tree l, u;
> +  tree type = TREE_TYPE (clast_name_to_gcc (n, region, newivs,
> +					    newivs_index, params_index));
> +
> +  if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
> +    l = lower_bound_in_type (type, type);
> +  else
> +    l = TYPE_MIN_VALUE (type);
> +
> +  if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
> +    u = upper_bound_in_type (type, type);
> +  else
> +    u = TYPE_MAX_VALUE (type);
> +
> +  tree_int_to_gmp (l, lb);
> +  tree_int_to_gmp (u, ub);
>  }
>  
> -/* Return the type for the clast_term T used in STMT.  */
> +/* Return the lower bound LB and upper bound UB of the clast_term T.  */
>  
> -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_clast_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)
> +    {
> +      lb_ub_for_clast_expr_name ((clast_name_p) (t->var), region,
> +				 newivs, newivs_index, params_index, lb, ub);
> +      mpz_mul (lb, lb, t->val);
> +      mpz_mul (ub, ub, t->val);
> +    }
> +  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_clast_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_clast_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_clast_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_clast_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_clast_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_clast_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_clast_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_clast_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_clast_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_clast_bin ((struct clast_binary *) e, region,
> +			   newivs, newivs_index, params_index, lb, ub);
> +      break;
> +
> +    case clast_expr_name:
> +      lb_ub_for_clast_expr_name ((clast_name_p) e, region,
> +				 newivs, newivs_index, params_index, lb, ub);
> +      break;
>  
>      default:
>        gcc_unreachable ();
>      }
> +}
>  
> -  return NULL_TREE;
> +/* 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_clast_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 695d01f..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
> @@ -131,7 +142,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.  */
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index fb27e99..b6d9a92 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,8 @@
> +2011-02-22  Sebastian Pop  <sebastian.pop@amd.com>
> +
> +	PR tree-optimization/47654
> +	* gcc.dg/graphite/run-id-pr47654.c: New.
> +
>  2011-02-13  Tobias Burnus  <burnus@net-b.de>
>  
>  	* gfortran.dg/argument_checking_13.f90: Update dg-error.
> 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;
> +}
>

On Tue, Feb 22, 2011 at 03:58, Richard Guenther <rguenther@suse.de> wrote:
> So CLOOG basically assumes infinite precision integers with no
> wrap-around?

Yes, CLooG works on infinite precision integers.
Graphite adds the constraints that define the type bounds,
however it does not yet specify the wrapping arithmetic.

In Polly, Tobias is adding extra constraints to describe the
modulo arithmetic: like "the upper bound of the loop is N + M mod k",
whereas Graphite would just say "the upper bound of the loop is N + M".

>> This passed the graphite testsuite.  I am currently regstrapping this
>> patch on amd64-linux.  Ok for trunk?
>
> Ok.

One of the patches produced these fails:
FAIL: libgomp.graphite/force-parallel-1.c execution test
FAIL: libgomp.graphite/force-parallel-3.c execution test
FAIL: libgomp.graphite/force-parallel-9.c execution test

I will send out an updated patch.

Sebastian

On 02/22/2011 12:04 PM, Sebastian Pop wrote:
> On Tue, Feb 22, 2011 at 03:58, Richard Guenther<rguenther@suse.de>  wrote:
>> So CLOOG basically assumes infinite precision integers with no
>> wrap-around?
>
> Yes, CLooG works on infinite precision integers.
> Graphite adds the constraints that define the type bounds,
> however it does not yet specify the wrapping arithmetic.
>
> In Polly, Tobias is adding extra constraints to describe the
> modulo arithmetic: like "the upper bound of the loop is N + M mod k",
> whereas Graphite would just say "the upper bound of the loop is N + M".

This is not yet completely implemented. However cloog-isl does provide 
the ability to add such kind of information. It also provides the 
ability to derive the maximal/minimal possible value of the variables in 
the clast, through analyzing the polyhedral representation cloog used 
for code generation.

If this is implemented and works efficiently we can represent wrapping 
semantics in CLooG and the optimizers.

>>> This passed the graphite testsuite.  I am currently regstrapping this
>>> patch on amd64-linux.  Ok for trunk?
>>
>> Ok.
>
> One of the patches produced these fails:
> FAIL: libgomp.graphite/force-parallel-1.c execution test
> FAIL: libgomp.graphite/force-parallel-3.c execution test
> FAIL: libgomp.graphite/force-parallel-9.c execution test
>
> I will send out an updated patch.
>
> Sebastian