From patchwork Mon Aug 15 07:12:56 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 110004 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 01055B6F70 for ; Mon, 15 Aug 2011 17:15:48 +1000 (EST) Received: (qmail 14283 invoked by alias); 15 Aug 2011 07:14:36 -0000 Received: (qmail 13999 invoked by uid 22791); 15 Aug 2011 07:14:30 -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:13 +0000 Received: by ywe9 with SMTP id 9so3118924ywe.20 for ; Mon, 15 Aug 2011 00:14:13 -0700 (PDT) Received: by 10.236.176.7 with SMTP id a7mr11388025yhm.176.1313392453090; Mon, 15 Aug 2011 00:14:13 -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 q25sm4620302yhm.62.2011.08.15.00.14.11 (version=TLSv1/SSLv3 cipher=OTHER); Mon, 15 Aug 2011 00:14:12 -0700 (PDT) Received: by napoca (sSMTP sendmail emulation); Mon, 15 Aug 2011 02:14:10 -0500 From: Sebastian Pop To: skimo@kotnet.org, tobias@grosser.es Cc: gcc-patches@gcc.gnu.org, Sebastian Pop Subject: [PATCH 17/20] use isl's datadep analysis Date: Mon, 15 Aug 2011 02:12:56 -0500 Message-Id: <1313392379-1525-17-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-dependences.c | 169 ++++++++++++++++++++++- gcc/graphite-poly.c | 8 + gcc/graphite-poly.h | 3 + gcc/testsuite/gcc.dg/graphite/interchange-14.c | 3 +- gcc/testsuite/gcc.dg/graphite/interchange-15.c | 3 +- gcc/testsuite/gcc.dg/graphite/interchange-8.c | 2 +- gcc/testsuite/gcc.dg/graphite/interchange-mvt.c | 3 +- 7 files changed, 183 insertions(+), 8 deletions(-) diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c index 9ba2731..eb8d40f 100644 --- a/gcc/graphite-dependences.c +++ b/gcc/graphite-dependences.c @@ -25,6 +25,7 @@ along with GCC; see the file COPYING3. If not see #include #include #include +#include #include #include #endif @@ -722,6 +723,151 @@ graphite_legal_transform_bb (poly_bb_p pbb1, poly_bb_p pbb2) return true; } +/* Add the constraints from the set S to the domain of MAP. */ + +static isl_map * +constrain_domain (isl_map *map, isl_set *s) +{ + isl_dim *d = isl_map_get_dim (map); + isl_id *id = isl_dim_get_tuple_id (d, isl_dim_in); + + s = isl_set_set_tuple_id (s, id); + isl_dim_free (d); + return isl_map_intersect_domain (map, s); +} + +/* Constrain pdr->accesses with pdr->extent and pbb->domain. */ + +static isl_map * +add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb) +{ + isl_map *x = isl_map_intersect_range (isl_map_copy (pdr->accesses), + isl_set_copy (pdr->extent)); + x = constrain_domain (x, isl_set_copy (pbb->domain)); + return x; +} + +/* Returns all the memory reads in SCOP. */ + +static isl_union_map * +scop_get_sink (scop_p scop) +{ + int i, j; + poly_bb_p pbb; + poly_dr_p pdr; + isl_dim *dim = isl_dim_from_domain (isl_set_get_dim (scop->context)); + isl_union_map *res = isl_union_map_empty (dim); + + FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) + { + FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), j, pdr) + if (pdr_read_p (pdr)) + res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb)); + } + + return res; +} + +/* Returns all the memory must writes in SCOP. */ + +static isl_union_map * +scop_get_must_source (scop_p scop) +{ + int i, j; + poly_bb_p pbb; + poly_dr_p pdr; + isl_dim *dim = isl_dim_from_domain (isl_set_get_dim (scop->context)); + isl_union_map *res = isl_union_map_empty (dim); + + FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) + { + FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), j, pdr) + if (pdr_write_p (pdr)) + res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb)); + } + + return res; +} + +/* Returns all the memory may writes in SCOP. */ + +static isl_union_map * +scop_get_may_source (scop_p scop) +{ + int i, j; + poly_bb_p pbb; + poly_dr_p pdr; + isl_dim *dim = isl_dim_from_domain (isl_set_get_dim (scop->context)); + isl_union_map *res = isl_union_map_empty (dim); + + FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) + { + FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), j, pdr) + if (pdr_may_write_p (pdr)) + res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb)); + } + + return res; +} + +/* Returns all the original schedules in SCOP. */ + +static isl_union_map * +scop_get_original_schedule (scop_p scop) +{ + int i; + poly_bb_p pbb; + isl_dim *dim = isl_dim_from_domain (isl_set_get_dim (scop->context)); + isl_union_map *res = isl_union_map_empty (dim); + + FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) + { + res = isl_union_map_add_map + (res, constrain_domain (isl_map_copy (pbb->schedule), + isl_set_copy (pbb->domain))); + } + + return res; +} + +/* Returns all the transformed schedules in SCOP. */ + +static isl_union_map * +scop_get_transformed_schedule (scop_p scop) +{ + int i; + poly_bb_p pbb; + isl_dim *dim = isl_dim_from_domain (isl_set_get_dim (scop->context)); + isl_union_map *res = isl_union_map_empty (dim); + + FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) + { + res = isl_union_map_add_map + (res, constrain_domain (isl_map_copy (pbb->transformed), + isl_set_copy (pbb->domain))); + } + + return res; +} + +/* Return true when SCHEDULE does not violate the data dependences DEPS. */ + +static bool +no_violations (isl_union_map *schedule, isl_union_map *deps) +{ + bool res; + isl_dim *dim = isl_dim_reverse (isl_union_map_get_dim (schedule)); + isl_map *lex = isl_map_lex_ge (dim); + + deps = isl_union_map_apply_domain (deps, isl_union_map_copy (schedule)); + deps = isl_union_map_apply_range (deps, schedule); + deps = isl_union_map_intersect (deps, isl_union_map_from_map (lex)); + res = isl_union_map_is_empty (deps); + + isl_union_map_free (deps); + return res; +} + /* Iterates over the SCOP and detect whether the transformed schedule is correct. */ @@ -730,9 +876,31 @@ graphite_legal_transform (scop_p scop) { int i, j; poly_bb_p pbb1, pbb2; + int res; + isl_union_map *transformed; timevar_push (TV_GRAPHITE_DATA_DEPS); + if (!scop->must_deps) + { + isl_union_map *sink = scop_get_sink (scop); + isl_union_map *must_source = scop_get_must_source (scop); + isl_union_map *may_source = scop_get_may_source (scop); + isl_union_map *original = scop_get_original_schedule (scop); + res = isl_union_map_compute_flow (sink, must_source, may_source, + original, &scop->must_deps, &scop->may_deps, + &scop->must_no_source, &scop->may_no_source); + gcc_assert (res == 0); + } + + transformed = scop_get_transformed_schedule (scop); + res = (no_violations (isl_union_map_copy (transformed), + isl_union_map_copy (scop->must_deps)) + && no_violations (transformed, isl_union_map_copy (scop->may_deps))); + + timevar_pop (TV_GRAPHITE_DATA_DEPS); + return res; + FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1) FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2) if (!graphite_legal_transform_bb (pbb1, pbb2)) @@ -741,7 +909,6 @@ graphite_legal_transform (scop_p scop) return false; } - timevar_pop (TV_GRAPHITE_DATA_DEPS); return true; } diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c index 2835311..10e9fc0 100644 --- a/gcc/graphite-poly.c +++ b/gcc/graphite-poly.c @@ -1028,6 +1028,10 @@ new_scop (void *region) SCOP_CONTEXT (scop) = NULL; scop->context = NULL; + scop->must_deps = NULL; + scop->may_deps = NULL; + scop->must_no_source = NULL; + scop->may_no_source = NULL; scop_set_region (scop, region); SCOP_BBS (scop) = VEC_alloc (poly_bb_p, heap, 3); SCOP_ORIGINAL_PDDRS (scop) = htab_create (10, hash_poly_ddr_p, @@ -1057,6 +1061,10 @@ free_scop (scop_p scop) ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop)); isl_set_free (scop->context); + isl_union_map_free (scop->must_deps); + isl_union_map_free (scop->may_deps); + isl_union_map_free (scop->must_no_source); + isl_union_map_free (scop->may_no_source); htab_delete (SCOP_ORIGINAL_PDDRS (scop)); free_lst (SCOP_ORIGINAL_SCHEDULE (scop)); free_lst (SCOP_TRANSFORMED_SCHEDULE (scop)); diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h index bf537b1..5ae7fad 100644 --- a/gcc/graphite-poly.h +++ b/gcc/graphite-poly.h @@ -1436,6 +1436,9 @@ struct scop /* The context used internally by ISL. */ isl_ctx *ctx; + /* The original dependence information. */ + isl_union_map *must_deps, *may_deps, *must_no_source, *may_no_source; + /* A hashtable of the data dependence relations for the original scattering. */ htab_t original_pddrs; diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-14.c b/gcc/testsuite/gcc.dg/graphite/interchange-14.c index cf62033..53809b5 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-14.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-14.c @@ -54,6 +54,5 @@ main (void) return 0; } -/* PRE destroys the perfect nest and we can't cope with that yet. */ -/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */ +/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" } } */ /* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-15.c b/gcc/testsuite/gcc.dg/graphite/interchange-15.c index ee7aed6..9eeef66 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-15.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-15.c @@ -48,7 +48,6 @@ main (void) return 0; } -/* PRE destroys the perfect nest and we can't cope with that yet. */ -/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */ +/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" } } */ /* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-8.c b/gcc/testsuite/gcc.dg/graphite/interchange-8.c index ca99dbc..120a83c 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-8.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-8.c @@ -82,5 +82,5 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "will be interchanged" 2 "graphite" } } */ +/* { dg-final { scan-tree-dump-times "will be interchanged" 4 "graphite" } } */ /* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c b/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c index 11f8b2a..ee262e9 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c @@ -58,7 +58,6 @@ main (void) return 0; } -/* PRE destroys the perfect nest and we can't cope with that yet. */ -/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */ +/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" } } */ /* { dg-final { cleanup-tree-dump "graphite" } } */