From patchwork Mon Aug 15 07:12:53 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 110005 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 1BC68B6F70 for ; Mon, 15 Aug 2011 17:15:59 +1000 (EST) Received: (qmail 14347 invoked by alias); 15 Aug 2011 07:14:37 -0000 Received: (qmail 13868 invoked by uid 22791); 15 Aug 2011 07:14:29 -0000 X-SWARE-Spam-Status: No, hits=-2.6 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-yw0-f47.google.com (HELO mail-yw0-f47.google.com) (209.85.213.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 15 Aug 2011 07:14:05 +0000 Received: by ywe9 with SMTP id 9so3118890ywe.20 for ; Mon, 15 Aug 2011 00:14:04 -0700 (PDT) Received: by 10.150.1.20 with SMTP id 20mr4511246yba.103.1313392444637; Mon, 15 Aug 2011 00:14:04 -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 j8sm3561777ybf.19.2011.08.15.00.14.02 (version=TLSv1/SSLv3 cipher=OTHER); Mon, 15 Aug 2011 00:14:04 -0700 (PDT) Received: by napoca (sSMTP sendmail emulation); Mon, 15 Aug 2011 02:14:01 -0500 From: Sebastian Pop To: skimo@kotnet.org, tobias@grosser.es Cc: gcc-patches@gcc.gnu.org, Sebastian Pop Subject: [PATCH 14/20] add pdr->accesses and pdr->extent Date: Mon, 15 Aug 2011 02:12:53 -0500 Message-Id: <1313392379-1525-14-git-send-email-sebpop@gmail.com> In-Reply-To: <1313392379-1525-1-git-send-email-sebpop@gmail.com> References: <1313392379-1525-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 --- gcc/graphite-poly.c | 7 ++- gcc/graphite-poly.h | 4 +- gcc/graphite-sese-to-poly.c | 149 ++++++++++++++++++++++++++++++++++++++++--- 3 files changed, 148 insertions(+), 12 deletions(-) diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c index 3d81372..2835311 100644 --- a/gcc/graphite-poly.c +++ b/gcc/graphite-poly.c @@ -847,7 +847,8 @@ pbb_remove_duplicate_pdrs (poly_bb_p pbb) void new_poly_dr (poly_bb_p pbb, int dr_base_object_set, ppl_Pointset_Powerset_C_Polyhedron_t accesses, - enum poly_dr_type type, void *cdr, graphite_dim_t nb_subscripts) + enum poly_dr_type type, void *cdr, graphite_dim_t nb_subscripts, + isl_map *acc, isl_set *extent) { static int id = 0; poly_dr_p pdr = XNEW (struct poly_dr); @@ -857,6 +858,8 @@ new_poly_dr (poly_bb_p pbb, int dr_base_object_set, PDR_NB_REFS (pdr) = 1; PDR_PBB (pdr) = pbb; PDR_ACCESSES (pdr) = accesses; + pdr->accesses = acc; + pdr->extent = extent; PDR_TYPE (pdr) = type; PDR_CDR (pdr) = cdr; PDR_NB_SUBSCRIPTS (pdr) = nb_subscripts; @@ -869,6 +872,8 @@ void free_poly_dr (poly_dr_p pdr) { ppl_delete_Pointset_Powerset_C_Polyhedron (PDR_ACCESSES (pdr)); + isl_map_free (pdr->accesses); + isl_set_free (pdr->extent); XDELETE (pdr); } diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h index b6e5277..b05e2e7 100644 --- a/gcc/graphite-poly.h +++ b/gcc/graphite-poly.h @@ -182,6 +182,7 @@ struct poly_dr In the example, the vector "R C O I L P" is "7 7 3 2 0 1". */ ppl_Pointset_Powerset_C_Polyhedron_t _accesses; isl_map *accesses; + isl_set *extent; /* Data reference's base object set number, we must assure 2 pdrs are in the same base object set before dependency checking. */ @@ -201,7 +202,8 @@ struct poly_dr #define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts) void new_poly_dr (poly_bb_p, int, ppl_Pointset_Powerset_C_Polyhedron_t, - enum poly_dr_type, void *, graphite_dim_t); + enum poly_dr_type, void *, graphite_dim_t, isl_map *, + isl_set *); void free_poly_dr (poly_dr_p); void debug_pdr (poly_dr_p, int); void print_pdr (FILE *, poly_dr_p, int); diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index 9407a8d..bc1fd21 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -707,6 +707,27 @@ isl_id_for_ssa_name (scop_p s, tree e) return id; } +/* Return an ISL identifier for the data reference DR. */ + +static isl_id * +isl_id_for_dr (scop_p s, data_reference_p dr) +{ + isl_id *id; + tree e = DR_BASE_ADDRESS (dr) ? DR_BASE_ADDRESS (dr) : DR_BASE_OBJECT (dr); + const char *name = get_name (e); + + if (name) + id = isl_id_alloc (s->ctx, name, dr); + else + { + char name1[1]; + snprintf (name1, sizeof (name1), "A"); + id = isl_id_alloc (s->ctx, name1, e); + } + + return id; +} + /* Extract an affine expression from the ssa_name E. */ static isl_pw_aff * @@ -2024,8 +2045,9 @@ build_scop_iteration_domain (scop_p scop) ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration domain. */ -static void -pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr, +static isl_map * +pdr_add_alias_set (isl_map *acc, + ppl_Polyhedron_t accesses, data_reference_p dr, ppl_dimension_type accessp_nb_dims, ppl_dimension_type dom_nb_dims) { @@ -2046,6 +2068,36 @@ pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr, ppl_delete_Linear_Expression (alias); ppl_delete_Constraint (cstr); + + { + isl_constraint *c = isl_equality_alloc (isl_map_get_dim (acc)); + c = isl_constraint_set_constant_si (c, -alias_set_num); + c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1); + + return isl_map_add_constraint (acc, c); + } +} + +/* Assign the affine expression INDEX to the output dimension POS of + MAP and return the result. */ + +static isl_map * +set_index (isl_map *map, int pos, isl_pw_aff *index) +{ + isl_map *index_map; + int len = isl_map_dim (map, isl_dim_out); + isl_id *id; + + index_map = isl_map_from_pw_aff (index); + index_map = isl_map_insert_dims (index_map, isl_dim_out, 0, pos); + index_map = isl_map_add_dims (index_map, isl_dim_out, len - pos - 1); + + id = isl_map_get_tuple_id (map, isl_dim_out); + index_map = isl_map_set_tuple_id (index_map, isl_dim_out, id); + id = isl_map_get_tuple_id (map, isl_dim_in); + index_map = isl_map_set_tuple_id (index_map, isl_dim_in, id); + + return isl_map_intersect (map, index_map); } /* Add to ACCESSES polyhedron equalities defining the access functions @@ -2053,8 +2105,9 @@ pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr, polyhedron, DOM_NB_DIMS is the dimension of the iteration domain. PBB is the poly_bb_p that contains the data reference DR. */ -static void -pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr, +static isl_map * +pdr_add_memory_accesses (isl_map *acc, + ppl_Polyhedron_t accesses, data_reference_p dr, ppl_dimension_type accessp_nb_dims, ppl_dimension_type dom_nb_dims, poly_bb_p pbb) @@ -2087,9 +2140,13 @@ pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr, ppl_delete_Linear_Expression (fn); ppl_delete_Linear_Expression (access); ppl_delete_Constraint (cstr); + + acc = set_index (acc, i + 1, extract_affine (scop, afn)); } mpz_clear (v); + + return acc; } /* Add constrains representing the size of the accessed data to the @@ -2097,8 +2154,9 @@ pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr, ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration domain. */ -static void -pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr, +static isl_set * +pdr_add_data_dimensions (isl_set *extent, scop_p scop, + ppl_Polyhedron_t accesses, data_reference_p dr, ppl_dimension_type accessp_nb_dims, ppl_dimension_type dom_nb_dims) { @@ -2136,6 +2194,52 @@ pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr, high = array_ref_up_bound (ref); + if (host_integerp (low, 0) + && high + && host_integerp (high, 0) + /* 1-element arrays at end of structures may extend over + their declared size. */ + && !(array_at_struct_end_p (ref) + && operand_equal_p (low, high, 0))) + { + isl_id *id; + isl_aff *aff; + isl_set *univ, *lbs, *ubs; + isl_pw_aff *index; + isl_dim *dim; + isl_set *valid; + int nbl = isl_set_dim (scop->context, isl_dim_set); + int nbs = isl_set_dim (extent, isl_dim_set); + isl_pw_aff *lb = extract_affine_int (scop, low); + isl_pw_aff *ub = extract_affine_int (scop, high); + + /* high >= 0 */ + valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub)); + scop->context = isl_set_intersect (scop->context, valid); + + /* Make the dimension of LB and UB to be exactly NBS. */ + lb = isl_pw_aff_drop_dims (lb, isl_dim_set, 0, nbl - 1); + ub = isl_pw_aff_drop_dims (ub, isl_dim_set, 0, nbl - 1); + lb = isl_pw_aff_add_dims (lb, isl_dim_set, nbs - 1); + ub = isl_pw_aff_add_dims (ub, isl_dim_set, nbs - 1); + + dim = isl_set_get_dim (extent); + aff = isl_aff_zero (isl_local_space_from_dim (dim)); + aff = isl_aff_add_coefficient_si (aff, isl_dim_set, i, 1); + univ = isl_set_universe (isl_aff_get_dim (aff)); + index = isl_pw_aff_alloc (univ, aff); + + id = isl_set_get_tuple_id (extent); + lb = isl_pw_aff_set_tuple_id (lb, isl_id_copy (id)); + ub = isl_pw_aff_set_tuple_id (ub, id); + + /* low <= sub_i <= high */ + lbs = isl_pw_aff_ge_set (isl_pw_aff_copy (index), lb); + ubs = isl_pw_aff_le_set (index, ub); + extent = isl_set_intersect (extent, lbs); + extent = isl_set_intersect (extent, ubs); + } + /* high - subscript >= 0 */ if (high && host_integerp (high, 0) /* 1-element arrays at end of structures may extend over @@ -2154,6 +2258,8 @@ pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr, ppl_delete_Constraint (cstr); } } + + return extent; } /* Build data accesses for DR in PBB. */ @@ -2166,6 +2272,9 @@ build_poly_dr (data_reference_p dr, poly_bb_p pbb) ppl_dimension_type dom_nb_dims; ppl_dimension_type accessp_nb_dims; int dr_base_object_set; + isl_map *acc; + isl_set *extent; + scop_p scop = PBB_SCOP (pbb); ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dom_nb_dims); @@ -2173,9 +2282,29 @@ build_poly_dr (data_reference_p dr, poly_bb_p pbb) ppl_new_C_Polyhedron_from_space_dimension (&accesses, accessp_nb_dims, 0); - pdr_add_alias_set (accesses, dr, accessp_nb_dims, dom_nb_dims); - pdr_add_memory_accesses (accesses, dr, accessp_nb_dims, dom_nb_dims, pbb); - pdr_add_data_dimensions (accesses, dr, accessp_nb_dims, dom_nb_dims); + { + isl_dim *dc = isl_set_get_dim (pbb->domain); + int nb_out = 1 + DR_NUM_DIMENSIONS (dr); + isl_dim *dim = isl_dim_add (isl_dim_from_domain (dc), isl_dim_out, nb_out); + + acc = isl_map_universe (dim); + acc = isl_map_set_tuple_id (acc, isl_dim_out, isl_id_for_dr (scop, dr)); + } + + acc = pdr_add_alias_set (acc, accesses, dr, accessp_nb_dims, dom_nb_dims); + acc = pdr_add_memory_accesses (acc, accesses, dr, accessp_nb_dims, + dom_nb_dims, pbb); + + { + isl_id *id = isl_id_for_dr (scop, dr); + int nb = 1 + DR_NUM_DIMENSIONS (dr); + isl_dim *dim = isl_dim_set_alloc (scop->ctx, 0, nb); + + dim = isl_dim_set_tuple_id (dim, isl_dim_set, id); + extent = isl_set_nat_universe (dim); + extent = pdr_add_data_dimensions (extent, scop, accesses, dr, + accessp_nb_dims, dom_nb_dims); + } ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps, accesses); @@ -2186,7 +2315,7 @@ build_poly_dr (data_reference_p dr, poly_bb_p pbb) new_poly_dr (pbb, dr_base_object_set, accesses_ps, DR_IS_READ (dr) ? PDR_READ : PDR_WRITE, - dr, DR_NUM_DIMENSIONS (dr)); + dr, DR_NUM_DIMENSIONS (dr), acc, extent); } /* Write to FILE the alias graph of data references in DIMACS format. */