This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH 1/2] Fix PR47654: Compute LB and UB of a CLAST expression.
- From: Richard Guenther <rguenther at suse dot de>
- To: Sebastian Pop <sebpop at gmail dot com>
- Cc: gcc-patches at gcc dot gnu dot org, gcc-graphite at googlegroups dot com
- Date: Tue, 22 Feb 2011 10:58:23 +0100 (CET)
- Subject: Re: [PATCH 1/2] Fix PR47654: Compute LB and UB of a CLAST expression.
- References: <1298328907-22399-1-git-send-email-sebpop@gmail.com>
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;
> +}
>
--
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex