From patchwork Thu Aug 11 18:16:45 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 109656 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 1E67DB700E for ; Fri, 12 Aug 2011 04:17:56 +1000 (EST) Received: (qmail 5735 invoked by alias); 11 Aug 2011 18:17:55 -0000 Received: (qmail 5705 invoked by uid 22791); 11 Aug 2011 18:17:47 -0000 X-SWARE-Spam-Status: No, hits=-1.2 required=5.0 tests=AWL, BAYES_20, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, TW_CF, TW_GB X-Spam-Check-By: sourceware.org Received: from mail-qw0-f47.google.com (HELO mail-qw0-f47.google.com) (209.85.216.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 11 Aug 2011 18:17:26 +0000 Received: by qwh5 with SMTP id 5so1356602qwh.20 for ; Thu, 11 Aug 2011 11:17:25 -0700 (PDT) Received: by 10.229.67.11 with SMTP id p11mr7703005qci.49.1313086645217; Thu, 11 Aug 2011 11:17:25 -0700 (PDT) MIME-Version: 1.0 Received: by 10.229.181.206 with HTTP; Thu, 11 Aug 2011 11:16:45 -0700 (PDT) In-Reply-To: References: <4E42FFA4.6080102@grosser.es> <4E4416EE.5090300@grosser.es> From: Sebastian Pop Date: Thu, 11 Aug 2011 13:16:45 -0500 Message-ID: Subject: Re: [graphite] Move to cloog.org interface To: Tobias Grosser , Sven Verdoolaege Cc: gcc-patches@gcc.gnu.org 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 On Thu, Aug 11, 2011 at 13:03, Sebastian Pop wrote: > On Thu, Aug 11, 2011 at 12:52, Tobias Grosser wrote: >> I will commit this patch after the configure changes are in (and meanwhile >> no further improvements were suggested for this patch). > > Ok, thanks.  Let's hope we will have a configure maintainer that has some > spare cycles to go over your first 3 patches. > > I will post my patches that convert graphite to ISL on top of your patches. I am following the PET (Polyhedral Extraction Tool) git://repo.or.cz/pet.git code as suggested by Tobias and Sven in order to help with the translation of graphite to ISL. Here is where I am right now: I am building the ISL counterpart for scop->context pbb->domain pdr->accesses and I still have to translate to ISL the original and transformed scattering. The plan is to build the ISL representation in parallel with PPL data structs, then make sure that ISL sets and maps contain valid data, and then move away from PPL data structures one by one. I would appreciate preliminary remarks on these patches. Thanks, Sebastian From 872bd33a1967d7a3dc00330f56d073f2a9f6fc13 Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Wed, 10 Aug 2011 13:08:37 -0500 Subject: [PATCH 10/10] add pdr->accesses and pdr->extent --- gcc/graphite-cloog-util.c | 24 +++++++ gcc/graphite-cloog-util.h | 2 + gcc/graphite-poly.c | 7 ++- gcc/graphite-poly.h | 4 +- gcc/graphite-sese-to-poly.c | 161 ++++++++++++++++++++++++++++++++++++++++--- 5 files changed, 186 insertions(+), 12 deletions(-) diff --git a/gcc/graphite-cloog-util.c b/gcc/graphite-cloog-util.c index c5abde8..8d46acb 100644 --- a/gcc/graphite-cloog-util.c +++ b/gcc/graphite-cloog-util.c @@ -428,6 +428,18 @@ debug_isl_set (isl_set *s) isl_ctx_free (ctx); } +/* Prints an isl_map M to stderr. */ + +DEBUG_FUNCTION void +debug_isl_map (isl_map *m) +{ + isl_ctx *ctx = isl_ctx_alloc (); + isl_printer *pp = isl_printer_to_file (ctx, stderr); + pp = isl_printer_print_map (pp, m); + isl_printer_free (pp); + isl_ctx_free (ctx); +} + /* Prints an isl_pw_aff A to stderr. */ DEBUG_FUNCTION void @@ -452,4 +464,16 @@ debug_isl_aff (isl_aff *a) isl_ctx_free (ctx); } +/* Prints an isl_id I to stderr. */ + +DEBUG_FUNCTION void +debug_isl_id (isl_id *i) +{ + isl_ctx *ctx = isl_ctx_alloc (); + isl_printer *pp = isl_printer_to_file (ctx, stderr); + pp = isl_printer_print_id (pp, i); + isl_printer_free (pp); + isl_ctx_free (ctx); +} + #endif diff --git a/gcc/graphite-cloog-util.h b/gcc/graphite-cloog-util.h index 3d10845..a72ff6c 100644 --- a/gcc/graphite-cloog-util.h +++ b/gcc/graphite-cloog-util.h @@ -36,8 +36,10 @@ void openscop_read_polyhedron_matrix (FILE *, ppl_Polyhedron_t *, int *, int *, extern int *openscop_read_N_int (FILE *, int); void debug_isl_set (isl_set *); +void debug_isl_map (isl_map *); void debug_isl_pwaff (isl_pw_aff *); void debug_isl_aff (isl_aff *); +void debug_isl_id (isl_id *); static inline bool isl_set_is_equal_ppl_polyhedron (isl_set *s1, ppl_const_Polyhedron_t ph, diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c index c5b32d6..c084634 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 0ca46ab..019f99f 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 dc1fad8..1d31392 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -670,6 +670,27 @@ isl_id_for_loop (scop_p s, loop_p l) 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; + const char *name = get_name (DR_BASE_OBJECT (dr)); + + if (name) + id = isl_id_alloc (s->ctx, name, dr); + else + { + char *name1 = XNEWVEC (char, 1); + sprintf (name1, "A"); + id = isl_id_alloc (s->ctx, name1, dr); + XDELETEVEC (name1); + } + + return id; +} + /* Extract an affine expression from the ssa_name E. */ static isl_pw_aff * @@ -1912,8 +1933,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) { @@ -1934,6 +1956,37 @@ 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); + + /* FIXME: This function will be renamed isl_map_insert_dims and + documented in a later version of ISL (current ISL is 0.07). */ + index_map = isl_map_insert (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); + + return isl_map_intersect (map, index_map); } /* Add to ACCESSES polyhedron equalities defining the access functions @@ -1941,8 +1994,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) @@ -1975,9 +2029,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 @@ -1985,8 +2043,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) { @@ -2024,6 +2083,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 @@ -2042,6 +2147,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. */ @@ -2054,6 +2161,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); @@ -2062,9 +2172,40 @@ 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 (scop->context); + int nb_in = isl_dim_size (dc, isl_dim_set); + int nb_out = 1 + DR_NUM_DIMENSIONS (dr); + int nbp = scop_nb_params (scop); + isl_dim *dim = isl_dim_alloc (scop->ctx, nbp, nb_in, nb_out); + int i; + + for (i = 0; i < nbp; i++) + dim = isl_dim_set_dim_id (dim, isl_dim_param, i, + isl_dim_get_dim_id (dc, isl_dim_param, i)); + for (i = 0; i < nb_in; i++) + dim = isl_dim_set_dim_id (dim, isl_dim_in, i, + isl_dim_get_dim_id (dc, isl_dim_set, i)); + + acc = isl_map_universe (dim); + acc = isl_map_set_tuple_id (acc, isl_dim_out, isl_id_for_dr (scop, dr)); + isl_dim_free (dc); + } + + 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); @@ -2075,7 +2216,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. */ -- 1.7.4.1