From patchwork Sat Dec 25 06:26:51 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 76662 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 53985B70DF for ; Sat, 25 Dec 2010 17:27:53 +1100 (EST) Received: (qmail 30752 invoked by alias); 25 Dec 2010 06:27:51 -0000 Received: (qmail 30740 invoked by uid 22791); 25 Dec 2010 06:27:49 -0000 X-SWARE-Spam-Status: No, hits=0.2 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, FSL_RU_URL, RCVD_IN_DNSWL_LOW, TW_TM, T_TO_NO_BRKTS_FREEMAIL X-Spam-Check-By: sourceware.org Received: from mail-gy0-f175.google.com (HELO mail-gy0-f175.google.com) (209.85.160.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sat, 25 Dec 2010 06:27:44 +0000 Received: by gyh20 with SMTP id 20so3336941gyh.20 for ; Fri, 24 Dec 2010 22:27:43 -0800 (PST) Received: by 10.151.7.10 with SMTP id k10mr14640325ybi.62.1293258462991; Fri, 24 Dec 2010 22:27:42 -0800 (PST) Received: from napoca (adsl-75-54-87-199.dsl.austtx.sbcglobal.net [75.54.87.199]) by mx.google.com with ESMTPS id r41sm7668710yba.4.2010.12.24.22.27.40 (version=TLSv1/SSLv3 cipher=RC4-MD5); Fri, 24 Dec 2010 22:27:42 -0800 (PST) Received: by napoca (sSMTP sendmail emulation); Sat, 25 Dec 2010 00:27:39 -0600 From: Sebastian Pop To: gcc-patches@gcc.gnu.org Cc: gcc-graphite@googlegroups.com, amonakov@ispras.ru, kayrick@ispras.ru, abel@ispras.ru, basile@starynkevitch.net, grosser@fim.uni-passau.de, Sebastian Pop Subject: [PATCH 2/4] Conservatively estimate subscript upper bound from the loop iteration domain. Date: Sat, 25 Dec 2010 00:26:51 -0600 Message-Id: <1293258413-29902-3-git-send-email-sebpop@gmail.com> In-Reply-To: References: 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 2010-12-25 Alexander Monakov * graphite-dependences.c (graphite_outer_subscript_bound): New. (graphite_carried_dependence_level_k): Export. * graphite-dependences.h (graphite_outer_subscript_bound): Declare. (graphite_carried_dependence_level_k): Ditto. --- gcc/ChangeLog.graphite | 7 +++ gcc/graphite-dependences.c | 130 +++++++++++++++++++++++++++++++++++++++++++- gcc/graphite-dependences.h | 3 + 3 files changed, 139 insertions(+), 1 deletions(-) diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index 9d03354..d667086 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,3 +1,10 @@ +2010-12-25 Alexander Monakov + + * graphite-dependences.c (graphite_outer_subscript_bound): New. + (graphite_carried_dependence_level_k): Export. + * graphite-dependences.h (graphite_outer_subscript_bound): Declare. + (graphite_carried_dependence_level_k): Ditto. + 2010-12-25 Alexey Kravets * graphite-clast-to-gimple.c (struct clast_name_index): Move diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c index 3986de4..6eeaf60 100644 --- a/gcc/graphite-dependences.c +++ b/gcc/graphite-dependences.c @@ -47,6 +47,7 @@ along with GCC; see the file COPYING3. If not see #include "graphite.h" #include "graphite-poly.h" #include "graphite-dependences.h" +#include "graphite-cloog-util.h" /* Returns a new polyhedral Data Dependence Relation (DDR). SOURCE is the source data reference, SINK is the sink data reference. When @@ -752,10 +753,137 @@ graphite_legal_transform (scop_p scop) return true; } +/* Return a tree with upper bound on PDR's outermost index (if PDR's outermost + type is INDIRECT_REF), or NULL if the bound could not be found. */ + +tree +graphite_outer_subscript_bound (poly_dr_p pdr, + bool minmax ATTRIBUTE_UNUSED) +{ + tree bound_tree = NULL_TREE; + poly_bb_p pbb = PDR_PBB (pdr); + graphite_dim_t tdim = pbb_nb_scattering_transform (pbb); + graphite_dim_t ddim = pbb_dim_iter_domain (pbb); + + graphite_dim_t sdim = PDR_NB_SUBSCRIPTS (pdr) + 1; + graphite_dim_t dim1 = pdr_dim (pdr); + + scop_p scop = PBB_SCOP (pbb); + graphite_dim_t gdim = scop_nb_params (scop); + + graphite_dim_t dim = tdim + dim1; + + ppl_Pointset_Powerset_C_Polyhedron_t isc, idr, res; + + combine_context_id_scat (&isc, pbb, false); + ppl_insert_dimensions_pointset (isc, tdim + ddim, sdim); + idr = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr), ddim, ddim + gdim, + tdim, 0); + + ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 0); + ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, isc); + ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr); + + ppl_delete_Pointset_Powerset_C_Polyhedron (isc); + ppl_delete_Pointset_Powerset_C_Polyhedron (idr); + + { + ppl_Linear_Expression_t le; + ppl_Coefficient_t coef; + mpz_t v; + unsigned i; + + mpz_init (v); + mpz_set_si (v, 1); + ppl_new_Coefficient (&coef); + ppl_assign_Coefficient_from_mpz_t (coef, v); + + ppl_new_Linear_Expression_with_dimension (&le, dim); + + for (i = 0; i < dim - sdim + 1 - gdim; i++) + ppl_Pointset_Powerset_C_Polyhedron_affine_image (res, i, le, coef); + } + + { + ppl_dimension_type *ds = XNEWVEC (ppl_dimension_type, dim - gdim - 1); + unsigned i, pos, sub1_dim = dim - sdim + 1 - gdim; + for (i = 0, pos = 0; i < dim - gdim; i++) + if (i != sub1_dim) + ds[pos++] = i; + + ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (res, ds, + dim + - gdim + - 1); + XDELETEVEC (ds); + } + + { + ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end; + ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it); + ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end); + + for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (res, it), + ppl_Pointset_Powerset_C_Polyhedron_iterator_end (res, end); + !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end); + ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it)) + { + ppl_const_Polyhedron_t ph; + CloogMatrix *mat; + int i; + unsigned j; + + ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph); + mat = new_Cloog_Matrix_from_ppl_Polyhedron (ph); + + for (i = 0; i < (int) mat->NbRows; i++) + if (mpz_cmp_si (mat->p[i][0], 0) == 0 + && mpz_cmp_si (mat->p[i][1], 0) != 0) + { + bound_tree = size_zero_node; + break; + } + else if (mpz_cmp_si (mat->p[i][0], 1) == 0 + && mpz_cmp_si (mat->p[i][1], 0) < 0) + { + tree dt = gmp_cst_to_tree (sizetype, mat->p[i][1]); + tree t = gmp_cst_to_tree (sizetype, mat->p[i][gdim+2]); + + for (j = 0; j < gdim; j++) + { + tree p, vt = gmp_cst_to_tree (sizetype, mat->p[i][j+2]); + + p = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), j); + p = fold_convert (sizetype, p); + p = fold_build2 (MULT_EXPR, sizetype, vt, p); + t = fold_build2 (PLUS_EXPR, sizetype, t, p); + } + + dt = fold_build1 (NEGATE_EXPR, sizetype, dt); + t = fold_build2 (FLOOR_DIV_EXPR, sizetype, t, dt); + + if (!bound_tree) + bound_tree = t; + else + bound_tree = fold_build2 (MIN_EXPR, sizetype, + bound_tree, t); + } + + cloog_matrix_free (mat); + } + + ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it); + ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end); + } + + ppl_delete_Pointset_Powerset_C_Polyhedron (res); + return bound_tree; +} + /* Returns TRUE when the dependence polyhedron between PDR1 and PDR2 represents a loop carried dependence at level LEVEL. */ -static bool +bool graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2, int level) { diff --git a/gcc/graphite-dependences.h b/gcc/graphite-dependences.h index f6f4fea..01196b2 100644 --- a/gcc/graphite-dependences.h +++ b/gcc/graphite-dependences.h @@ -24,6 +24,8 @@ along with GCC; see the file COPYING3. If not see extern bool graphite_legal_transform (scop_p); extern bool dependency_between_pbbs_p (poly_bb_p, poly_bb_p, int); +extern bool graphite_carried_dependence_level_k (poly_dr_p, poly_dr_p, int); + enum poly_dependence_kind { unknown_dependence, no_dependence, @@ -58,6 +60,7 @@ extern hashval_t hash_poly_ddr_p (const void *); extern void free_poly_ddr (void *); extern void dot_deps (scop_p); extern void dot_deps_stmt (scop_p); +extern tree graphite_outer_subscript_bound (poly_dr_p, bool); extern void print_pddr (FILE *, poly_ddr_p); extern void debug_pddr (poly_ddr_p);