From patchwork Mon Feb 21 22:55:06 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 83886 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 24DF1B7080 for ; Tue, 22 Feb 2011 09:55:25 +1100 (EST) Received: (qmail 24257 invoked by alias); 21 Feb 2011 22:55:22 -0000 Received: (qmail 24247 invoked by uid 22791); 21 Feb 2011 22:55:20 -0000 X-SWARE-Spam-Status: No, hits=-2.3 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, T_TO_NO_BRKTS_FREEMAIL X-Spam-Check-By: sourceware.org Received: from mail-vw0-f47.google.com (HELO mail-vw0-f47.google.com) (209.85.212.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 21 Feb 2011 22:55:14 +0000 Received: by vws4 with SMTP id 4so844146vws.20 for ; Mon, 21 Feb 2011 14:55:12 -0800 (PST) Received: by 10.52.157.74 with SMTP id wk10mr2852927vdb.25.1298328912189; Mon, 21 Feb 2011 14:55:12 -0800 (PST) Received: from napoca ([163.181.251.115]) by mx.google.com with ESMTPS id n13sm2584629vcr.41.2011.02.21.14.55.09 (version=TLSv1/SSLv3 cipher=OTHER); Mon, 21 Feb 2011 14:55:11 -0800 (PST) Received: by napoca (sSMTP sendmail emulation); Mon, 21 Feb 2011 16:55:08 -0600 From: Sebastian Pop To: gcc-patches@gcc.gnu.org Cc: rguenther@suse.de, gcc-graphite@googlegroups.com, Sebastian Pop Subject: [PATCH 1/2] Fix PR47654: Compute LB and UB of a CLAST expression. Date: Mon, 21 Feb 2011 16:55:06 -0600 Message-Id: <1298328907-22399-1-git-send-email-sebpop@gmail.com> X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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 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 + + 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 * 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 + + PR tree-optimization/47654 + * gcc.dg/graphite/run-id-pr47654.c: New. + 2011-02-13 Tobias Burnus * 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; +}