From patchwork Mon Aug 15 07:12:51 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 110003 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 6B889B6F82 for ; Mon, 15 Aug 2011 17:15:41 +1000 (EST) Received: (qmail 14173 invoked by alias); 15 Aug 2011 07:14:34 -0000 Received: (qmail 13860 invoked by uid 22791); 15 Aug 2011 07:14:28 -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, TW_GB, 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; Mon, 15 Aug 2011 07:13:59 +0000 Received: by gyg4 with SMTP id 4so3147600gyg.20 for ; Mon, 15 Aug 2011 00:13:58 -0700 (PDT) Received: by 10.236.165.4 with SMTP id d4mr10986980yhl.225.1313392438758; Mon, 15 Aug 2011 00:13:58 -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 f4sm3531999yhn.55.2011.08.15.00.13.56 (version=TLSv1/SSLv3 cipher=OTHER); Mon, 15 Aug 2011 00:13:58 -0700 (PDT) Received: by napoca (sSMTP sendmail emulation); Mon, 15 Aug 2011 02:13:55 -0500 From: Sebastian Pop To: skimo@kotnet.org, tobias@grosser.es Cc: gcc-patches@gcc.gnu.org, Sebastian Pop Subject: [PATCH 12/20] add pbb->domain Date: Mon, 15 Aug 2011 02:12:51 -0500 Message-Id: <1313392379-1525-12-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 | 12 +++- gcc/graphite-poly.h | 6 ++ gcc/graphite-sese-to-poly.c | 205 +++++++++++++++++++++++++++++++++++-------- 3 files changed, 187 insertions(+), 36 deletions(-) diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c index fd2703b..ce0649b 100644 --- a/gcc/graphite-poly.c +++ b/gcc/graphite-poly.c @@ -880,6 +880,7 @@ new_poly_bb (scop_p scop, void *black_box) poly_bb_p pbb = XNEW (struct poly_bb); PBB_DOMAIN (pbb) = NULL; + pbb->domain = NULL; PBB_SCOP (pbb) = scop; pbb_set_black_box (pbb, black_box); PBB_TRANSFORMED (pbb) = NULL; @@ -901,7 +902,10 @@ free_poly_bb (poly_bb_p pbb) int i; poly_dr_p pdr; - ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb)); + if (PBB_DOMAIN (pbb)) + ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb)); + + isl_set_free (pbb->domain); if (PBB_TRANSFORMED (pbb)) poly_scattering_free (PBB_TRANSFORMED (pbb)); @@ -1096,6 +1100,12 @@ print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity) graphite_dim_t i; gimple_bb_p gbb = PBB_BLACK_BOX (pbb); + { + isl_printer *pp = isl_printer_to_file (PBB_SCOP (pbb)->ctx, file); + pp = isl_printer_print_set (pp, pbb->domain); + isl_printer_free (pp); + } + if (!PBB_DOMAIN (pbb)) return; diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h index bb8771d..3483ef0 100644 --- a/gcc/graphite-poly.h +++ b/gcc/graphite-poly.h @@ -502,6 +502,12 @@ pbb_dim_iter_domain (const struct poly_bb *pbb) { scop_p scop = PBB_SCOP (pbb); ppl_dimension_type dim; + isl_dim *d = isl_set_get_dim (pbb->domain); + graphite_dim_t res = isl_dim_size (d, isl_dim_set); + + isl_dim_free (d); + if (0) + return res; ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dim); return dim - scop_nb_params (scop); diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index 9723427..20bcf1f 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -658,20 +658,6 @@ isl_id_for_ssa_name (scop_p s, tree e) return id; } -/* Return an ISL identifier from the loop L. */ - -static isl_id * -isl_id_for_loop (scop_p s, loop_p l) -{ - isl_id *id; - char name[50]; - - snprintf (name, sizeof (name), "L_%d", l ? l->num : -1); - id = isl_id_alloc (s->ctx, name, l); - - return id; -} - /* Extract an affine expression from the ssa_name E. */ static isl_pw_aff * @@ -1182,10 +1168,6 @@ find_scop_parameters (scop_p scop) dim = isl_dim_set_dim_id (dim, isl_dim_param, i, isl_id_for_ssa_name (scop, e)); - for (i = 0; i < nbl; i++) - dim = isl_dim_set_dim_id (dim, isl_dim_set, i, - isl_id_for_loop (scop, get_loop (i))); - scop->context = isl_set_universe (dim); } } @@ -1263,7 +1245,8 @@ add_upper_bounds_from_estimated_nit (scop_p scop, double_int nit, static void build_loop_iteration_domains (scop_p scop, struct loop *loop, ppl_Polyhedron_t outer_ph, int nb, - ppl_Pointset_Powerset_C_Polyhedron_t *domains) + ppl_Pointset_Powerset_C_Polyhedron_t *domains, + isl_set *outer, isl_set **doms) { int i; ppl_Polyhedron_t ph; @@ -1271,6 +1254,15 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop, ppl_dimension_type dim = nb + 1 + scop_nb_params (scop); sese region = SCOP_REGION (scop); + isl_set *inner = isl_set_copy (outer); + isl_dim *dimension = isl_set_get_dim (scop->context); + int pos = loop->num; + isl_int v; + mpz_t g; + + mpz_init (g); + isl_int_init (v); + { ppl_const_Constraint_System_t pcs; ppl_dimension_type *map @@ -1301,8 +1293,16 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop, ppl_delete_Linear_Expression (lb_expr); ppl_Polyhedron_add_constraint (ph, lb); ppl_delete_Constraint (lb); + + { + isl_constraint *c = isl_inequality_alloc (isl_dim_copy (dimension)); + + c = isl_constraint_set_coefficient_si (c, isl_dim_set, pos, 1); + inner = isl_set_add_constraint (inner, c); + } } + /* loop_i <= cst_nb_iters */ if (TREE_CODE (nb_iters) == INTEGER_CST) { ppl_Constraint_t ub; @@ -1310,14 +1310,25 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop, ppl_new_Linear_Expression_with_dimension (&ub_expr, dim); - /* loop_i <= cst_nb_iters */ ppl_set_coef (ub_expr, nb, -1); ppl_set_inhomogeneous_tree (ub_expr, nb_iters); ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); ppl_Polyhedron_add_constraint (ph, ub); ppl_delete_Linear_Expression (ub_expr); ppl_delete_Constraint (ub); + + { + isl_constraint *c = isl_inequality_alloc (isl_dim_copy (dimension)); + + c = isl_constraint_set_coefficient_si (c, isl_dim_set, pos, -1); + tree_int_to_gmp (nb_iters, g); + isl_int_set_gmp (v, g); + c = isl_constraint_set_constant (c, v); + inner = isl_set_add_constraint (inner, c); + } } + + /* loop_i <= expr_nb_iters */ else if (!chrec_contains_undetermined (nb_iters)) { mpz_t one; @@ -1337,6 +1348,15 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop, scop->context = isl_set_intersect (scop->context, isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff))); + { + isl_local_space *ls = isl_local_space_from_dim (isl_dim_copy (dimension)); + isl_aff *al = isl_aff_set_coefficient_si + (isl_aff_zero (ls), isl_dim_set, pos, 1); + isl_set *le = isl_pw_aff_le_set (isl_pw_aff_from_aff (al), + isl_pw_aff_copy (aff)); + inner = isl_set_intersect (inner, le); + } + if (max_stmt_executions (loop, true, &nit)) { add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr); @@ -1361,7 +1381,6 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop, } } - /* loop_i <= expr_nb_iters */ ppl_set_coef (ub_expr, nb, -1); ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); ppl_Polyhedron_add_constraint (ph, ub); @@ -1372,17 +1391,51 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop, gcc_unreachable (); if (loop->inner && loop_in_sese_p (loop->inner, region)) - build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains); + build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains, + isl_set_copy (inner), doms); if (nb != 0 && loop->next && loop_in_sese_p (loop->next, region)) - build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains); + build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains, + isl_set_copy (outer), doms); ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&domains[loop->num], ph); - ppl_delete_Polyhedron (ph); + + + { + isl_dim *dc = isl_set_get_dim (scop->context); + int nb_out = isl_dim_size (dc, isl_dim_set); + isl_dim *dim = isl_dim_add (isl_dim_from_domain (dc), isl_dim_out, + nb_out); + isl_map *map = isl_map_identity (dim); + loop_p outer; + + /* Set all the loops that are not part of the current loop nest to + 0. This includes the outermost loop (i.e., loop_0 is the body + of the function). This is needed for the data dependence + analysis to work, as otherwise all these dimensions would not + be bounded. */ + for (i = 0; i < nb_out; i++) + if (i == 0 + || !(outer = get_loop (i)) + || (loop != outer + && !flow_loop_nested_p (outer, loop))) + { + isl_constraint *c = isl_equality_alloc (isl_map_get_dim (map)); + c = isl_constraint_set_coefficient_si (c, isl_dim_out, i, 1); + map = isl_map_add_constraint (map, c); + } + + doms[loop->num] = isl_set_apply (inner, map); + } + + isl_set_free (outer); + isl_dim_free (dimension); + isl_int_clear (v); + mpz_clear (g); } /* Returns a linear expression for tree T evaluated in PBB. */ @@ -1494,6 +1547,19 @@ add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt, ppl_delete_Linear_Expression (right); } +/* Returns a linear expression for tree T evaluated in PBB. */ + +static isl_pw_aff * +create_pw_aff_from_tree (poly_bb_p pbb, tree t) +{ + scop_p scop = PBB_SCOP (pbb); + + t = scalar_evolution_in_region (SCOP_REGION (scop), pbb_loop (pbb), t); + gcc_assert (!automatically_generated_chrec_p (t)); + + return extract_affine (scop, t); +} + /* Add conditional statement STMT to pbb. CODE is used as the comparision operator. This allows us to invert the condition or to handle inequalities. */ @@ -1514,6 +1580,48 @@ add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code) } else add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code); + + { + isl_pw_aff *lhs = create_pw_aff_from_tree (pbb, gimple_cond_lhs (stmt)); + isl_pw_aff *rhs = create_pw_aff_from_tree (pbb, gimple_cond_rhs (stmt)); + isl_set *cond; + + switch (code) + { + case LT_EXPR: + cond = isl_pw_aff_lt_set (lhs, rhs); + break; + + case GT_EXPR: + cond = isl_pw_aff_gt_set (lhs, rhs); + break; + + case LE_EXPR: + cond = isl_pw_aff_le_set (lhs, rhs); + break; + + case GE_EXPR: + cond = isl_pw_aff_ge_set (lhs, rhs); + break; + + case EQ_EXPR: + cond = isl_pw_aff_eq_set (lhs, rhs); + break; + + case NE_EXPR: + cond = isl_pw_aff_ne_set (lhs, rhs); + break; + + default: + isl_pw_aff_free(lhs); + isl_pw_aff_free(rhs); + return; + } + + cond = isl_set_coalesce (cond); + cond = isl_set_set_tuple_id (cond, isl_set_get_tuple_id (pbb->domain)); + pbb->domain = isl_set_intersect (pbb->domain, cond); + } } /* Add conditions to the domain of PBB. */ @@ -1810,31 +1918,56 @@ build_scop_iteration_domain (scop_p scop) int nb_loops = number_of_loops (); ppl_Pointset_Powerset_C_Polyhedron_t *domains = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t, nb_loops); + isl_set **doms = XNEWVEC (isl_set *, nb_loops); for (i = 0; i < nb_loops; i++) - domains[i] = NULL; + { + domains[i] = NULL; + doms[i] = NULL; + } ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0); FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop) if (!loop_in_sese_p (loop_outer (loop), region)) - build_loop_iteration_domains (scop, loop, ph, 0, domains); + build_loop_iteration_domains (scop, loop, ph, 0, domains, + isl_set_copy (scop->context), doms); FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) - if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]) - ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron - (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t) - domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]); - else - ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron - (&PBB_DOMAIN (pbb), ph); + { + loop = pbb_loop (pbb); + + if (domains[loop->num]) + ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron + (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t) + domains[loop->num]); + else + ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron + (&PBB_DOMAIN (pbb), ph); + + if (doms[loop->num]) + pbb->domain = isl_set_copy (doms[loop->num]); + else + pbb->domain = isl_set_copy (scop->context); + + pbb->domain = isl_set_set_tuple_id (pbb->domain, + isl_id_for_pbb (scop, pbb)); + + } for (i = 0; i < nb_loops; i++) - if (domains[i]) - ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]); + { + if (domains[i]) + ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]); + + if (doms[i]) + isl_set_free (doms[i]); + } ppl_delete_Polyhedron (ph); free (domains); + + free (doms); } /* Add a constrain to the ACCESSES polyhedron for the alias set of @@ -2459,6 +2592,8 @@ new_pbb_from_pbb (scop_p scop, poly_bb_p pbb, basic_block bb) ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron (&PBB_DOMAIN (pbb1), PBB_DOMAIN (pbb)); + pbb1->domain = isl_set_copy (pbb->domain); + GBB_PBB (gbb1) = pbb1; GBB_CONDITIONS (gbb1) = VEC_copy (gimple, heap, GBB_CONDITIONS (gbb)); GBB_CONDITION_CASES (gbb1) = VEC_copy (gimple, heap, GBB_CONDITION_CASES (gbb));