From patchwork Thu Jul 21 18:31:08 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 106138 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 5DA45B6EE8 for ; Fri, 22 Jul 2011 04:32:40 +1000 (EST) Received: (qmail 21811 invoked by alias); 21 Jul 2011 18:32:06 -0000 Received: (qmail 21355 invoked by uid 22791); 21 Jul 2011 18:31:59 -0000 X-SWARE-Spam-Status: No, hits=-2.5 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, TW_TM, T_TO_NO_BRKTS_FREEMAIL X-Spam-Check-By: sourceware.org Received: from mail-yw0-f47.google.com (HELO mail-yw0-f47.google.com) (209.85.213.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 21 Jul 2011 18:31:42 +0000 Received: by ywa12 with SMTP id 12so890370ywa.20 for ; Thu, 21 Jul 2011 11:31:41 -0700 (PDT) Received: by 10.91.43.1 with SMTP id v1mr1045462agj.114.1311273101286; Thu, 21 Jul 2011 11:31:41 -0700 (PDT) Received: from napoca (adsl-99-184-92-236.dsl.austtx.sbcglobal.net [99.184.92.236]) by mx.google.com with ESMTPS id o7sm1821791anj.10.2011.07.21.11.31.39 (version=TLSv1/SSLv3 cipher=OTHER); Thu, 21 Jul 2011 11:31:40 -0700 (PDT) Received: by napoca (sSMTP sendmail emulation); Thu, 21 Jul 2011 13:31:38 -0500 From: Sebastian Pop To: gcc-patches@gcc.gnu.org Cc: rguenther@suse.de, tobias@grosser.es, Sebastian Pop Subject: [PATCH 08/10] Compute once and cache the LB and UB for each clast_name. Date: Thu, 21 Jul 2011 13:31:08 -0500 Message-Id: <1311273070-12128-9-git-send-email-sebpop@gmail.com> In-Reply-To: <1311273070-12128-1-git-send-email-sebpop@gmail.com> References: <1311273070-12128-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 2011-07-21 Sebastian Pop * graphite-clast-to-gimple.c (struct clast_name_index): Add lb and ub fields. (new_clast_name_index): Add lb and ub parameters. (free_clast_name_index): New. (clast_name_to_lb_ub): New. (save_clast_name_index): Add lb and ub parameters. (compute_bounds_for_param): New. (type_for_level): Removed. (type_for_clast_for): Removed level parameter. Do not call type_for_level. (graphite_create_new_loop): Store the lb and ub for the clast_name of the iterator of the loop that has been generated. (graphite_create_new_loop_guard): Remove parameter level. (create_params_index): Store the lb and ub of each parameter. (gloog): Use free_clast_name_index. Pass to create_params_index the current scop. --- gcc/ChangeLog | 19 +++++ gcc/graphite-clast-to-gimple.c | 144 ++++++++++++++++++++++++++++------------ 2 files changed, 121 insertions(+), 42 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 03fe015..485afca 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,24 @@ 2011-07-21 Sebastian Pop + * graphite-clast-to-gimple.c (struct clast_name_index): Add lb + and ub fields. + (new_clast_name_index): Add lb and ub parameters. + (free_clast_name_index): New. + (clast_name_to_lb_ub): New. + (save_clast_name_index): Add lb and ub parameters. + (compute_bounds_for_param): New. + (type_for_level): Removed. + (type_for_clast_for): Removed level parameter. Do not call + type_for_level. + (graphite_create_new_loop): Store the lb and ub for the clast_name + of the iterator of the loop that has been generated. + (graphite_create_new_loop_guard): Remove parameter level. + (create_params_index): Store the lb and ub of each parameter. + (gloog): Use free_clast_name_index. Pass to create_params_index + the current scop. + +2011-07-21 Sebastian Pop + * graphite-clast-to-gimple.c (max_signed_precision_type): Removed. (max_precision_type): Inline max_signed_precision_type. (type_for_clast_red): Use max_precision_type. diff --git a/gcc/graphite-clast-to-gimple.c b/gcc/graphite-clast-to-gimple.c index 495b0b7..6bc84d2 100644 --- a/gcc/graphite-clast-to-gimple.c +++ b/gcc/graphite-clast-to-gimple.c @@ -57,28 +57,46 @@ graphite_verify (void) } /* Stores the INDEX in a vector and the loop nesting LEVEL for a given - clast NAME. */ + clast NAME. LB and UB represent the exact lower and upper bounds + that can be inferred from the polyhedral representation. */ typedef struct clast_name_index { int index; int level; + mpz_t lb, ub; const char *name; } *clast_name_index_p; /* Returns a pointer to a new element of type clast_name_index_p built - from NAME, LEVEL, and INDEX. */ + from NAME, INDEX, LEVEL, LB, and UB. */ static inline clast_name_index_p -new_clast_name_index (const char *name, int index, int level) +new_clast_name_index (const char *name, int index, int level, + mpz_t lb, mpz_t ub) { clast_name_index_p res = XNEW (struct clast_name_index); res->name = name; res->level = level; res->index = index; + mpz_init (res->lb); + mpz_init (res->ub); + mpz_set (res->lb, lb); + mpz_set (res->ub, ub); return res; } +/* Free the memory taken by a clast_name_index struct. */ + +static void +free_clast_name_index (void *ptr) +{ + struct clast_name_index *c = (struct clast_name_index *) ptr; + mpz_clear (c->lb); + mpz_clear (c->ub); + free (ptr); +} + /* For a given clast NAME, returns -1 if NAME is not in the INDEX_TABLE, otherwise returns the loop level for the induction variable NAME, or if it is a parameter, the parameter number in the @@ -130,11 +148,40 @@ clast_name_to_index (clast_name_p name, htab_t index_table) return -1; } +/* For a given clast NAME, initializes the lower and upper bounds LB + and UB stored in the INDEX_TABLE. Returns true when NAME has been + found in the INDEX_TABLE, false otherwise. */ + +static inline bool +clast_name_to_lb_ub (clast_name_p name, htab_t index_table, mpz_t lb, mpz_t ub) +{ + struct clast_name_index tmp; + PTR *slot; + +#ifdef CLOOG_ORG + gcc_assert (name->type == clast_expr_name); + tmp.name = ((const struct clast_name *) name)->name; +#else + tmp.name = name; +#endif + + slot = htab_find_slot (index_table, &tmp, NO_INSERT); + + if (slot && *slot) + { + mpz_set (lb, ((struct clast_name_index *) *slot)->lb); + mpz_set (ub, ((struct clast_name_index *) *slot)->ub); + return true; + } + + return false; +} + /* Records in INDEX_TABLE the INDEX and LEVEL for NAME. */ static inline void save_clast_name_index (htab_t index_table, const char *name, - int index, int level) + int index, int level, mpz_t lb, mpz_t ub) { struct clast_name_index tmp; PTR *slot; @@ -146,7 +193,7 @@ save_clast_name_index (htab_t index_table, const char *name, { free (*slot); - *slot = new_clast_name_index (name, index, level); + *slot = new_clast_name_index (name, index, level, lb, ub); } } @@ -579,6 +626,24 @@ graphite_create_new_guard (edge entry_edge, struct clast_guard *stmt, return exit_edge; } +/* Compute the lower bound LOW and upper bound UP for the parameter + PARAM in scop SCOP based on the constraints in the context. */ + +static void +compute_bounds_for_param (scop_p scop, int param, mpz_t low, mpz_t up) +{ + ppl_Linear_Expression_t le; + + /* Prepare the linear expression corresponding to the parameter that + we want to maximize/minimize. */ + ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop)); + ppl_set_coef (le, param, 1); + + ppl_max_for_le_pointset (SCOP_CONTEXT (scop), le, up); + ppl_min_for_le_pointset (SCOP_CONTEXT (scop), le, low); + ppl_delete_Linear_Expression (le); +} + /* 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 @@ -608,26 +673,6 @@ compute_bounds_for_level (poly_bb_p pbb, int level, mpz_t low, mpz_t up) 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 -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 = 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. @@ -671,18 +716,12 @@ clast_get_body_of_loop (struct clast_stmt *stmt) from STMT_FOR. */ static tree -type_for_clast_for (struct clast_for *stmt_for, int level, - ivs_params_p ip) +type_for_clast_for (struct clast_for *stmt_for, ivs_params_p ip) { - 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); tree lb_type = type_for_clast_expr (stmt_for->LB, ip); tree ub_type = type_for_clast_expr (stmt_for->UB, ip); - return max_precision_type - (lb_type, max_precision_type (ub_type, type_for_level (pbb, level))); + return max_precision_type (lb_type, ub_type); } /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an @@ -698,6 +737,12 @@ graphite_create_new_loop (edge entry_edge, struct clast_for *stmt, loop_p outer, tree type, tree lb, tree ub, int level, ivs_params_p ip) { + mpz_t low, up; + + struct clast_user_stmt *body + = clast_get_body_of_loop ((struct clast_stmt *) stmt); + poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (body->statement); + tree stride = gmp_cst_to_tree (type, stmt->stride); tree ivvar = create_tmp_var (type, "graphite_IV"); tree iv, iv_after_increment; @@ -707,8 +752,13 @@ graphite_create_new_loop (edge entry_edge, struct clast_for *stmt, add_referenced_var (ivvar); + mpz_init (low); + mpz_init (up); + compute_bounds_for_level (pbb, level, low, up); save_clast_name_index (ip->newivs_index, stmt->iterator, - VEC_length (tree, *(ip->newivs)), level); + VEC_length (tree, *(ip->newivs)), level, low, up); + mpz_clear (low); + mpz_clear (up); VEC_safe_push (tree, heap, *(ip->newivs), iv); return loop; } @@ -862,13 +912,13 @@ translate_clast_user (struct clast_user_stmt *stmt, edge next_e, static edge graphite_create_new_loop_guard (edge entry_edge, struct clast_for *stmt, - int level, tree *type, tree *lb, tree *ub, + tree *type, tree *lb, tree *ub, ivs_params_p ip) { tree cond_expr; edge exit_edge; - *type = type_for_clast_for (stmt, level, ip); + *type = type_for_clast_for (stmt, ip); *lb = clast_to_gcc_expression (*type, stmt->LB, ip); *ub = clast_to_gcc_expression (*type, stmt->UB, ip); @@ -943,7 +993,7 @@ translate_clast_for (loop_p context_loop, struct clast_for *stmt, edge next_e, htab_t bb_pbb_mapping, int level, ivs_params_p ip) { tree type, lb, ub; - edge last_e = graphite_create_new_loop_guard (next_e, stmt, level, &type, + edge last_e = graphite_create_new_loop_guard (next_e, stmt, &type, &lb, &ub, ip); edge true_e = get_true_edge_from_guard_bb (next_e->dest); @@ -1361,14 +1411,24 @@ debug_generated_program (scop_p scop) back from CLooG names to GCC trees. */ static void -create_params_index (htab_t index_table, CloogProgram *prog) { +create_params_index (scop_p scop, htab_t index_table, CloogProgram *prog) { CloogNames* names = cloog_program_names (prog); int nb_parameters = cloog_names_nb_parameters (names); char **parameters = cloog_names_parameters (names); int i; + mpz_t lb, ub; + + mpz_init (lb); + mpz_init (ub); for (i = 0; i < nb_parameters; i++) - save_clast_name_index (index_table, parameters[i], i, i); + { + compute_bounds_for_param (scop, i, lb, ub); + save_clast_name_index (index_table, parameters[i], i, i, lb, ub); + } + + mpz_clear (lb); + mpz_clear (ub); } /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for @@ -1412,11 +1472,11 @@ gloog (scop_p scop, htab_t bb_pbb_mapping) context_loop = SESE_ENTRY (region)->src->loop_father; newivs_index = htab_create (10, clast_name_index_elt_info, - eq_clast_name_indexes, free); + eq_clast_name_indexes, free_clast_name_index); params_index = htab_create (10, clast_name_index_elt_info, - eq_clast_name_indexes, free); + eq_clast_name_indexes, free_clast_name_index); - create_params_index (params_index, pc.prog); + create_params_index (scop, params_index, pc.prog); ip.newivs = &newivs; ip.newivs_index = newivs_index;