From patchwork Thu Sep 9 19:30:04 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 64326 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 4E47DB70EF for ; Fri, 10 Sep 2010 05:31:31 +1000 (EST) Received: (qmail 6526 invoked by alias); 9 Sep 2010 19:30:59 -0000 Received: (qmail 6337 invoked by uid 22791); 9 Sep 2010 19:30:55 -0000 X-SWARE-Spam-Status: No, hits=-1.9 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, T_TO_NO_BRKTS_FREEMAIL X-Spam-Check-By: sourceware.org Received: from mail-gw0-f47.google.com (HELO mail-gw0-f47.google.com) (74.125.83.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 09 Sep 2010 19:30:45 +0000 Received: by mail-gw0-f47.google.com with SMTP id 1so845324gwb.20 for ; Thu, 09 Sep 2010 12:30:44 -0700 (PDT) Received: by 10.100.126.11 with SMTP id y11mr663148anc.115.1284060644466; Thu, 09 Sep 2010 12:30:44 -0700 (PDT) Received: from napoca ([163.181.251.115]) by mx.google.com with ESMTPS id c19sm2384106ana.22.2010.09.09.12.30.42 (version=TLSv1/SSLv3 cipher=RC4-MD5); Thu, 09 Sep 2010 12:30:43 -0700 (PDT) Received: by napoca (sSMTP sendmail emulation); Thu, 09 Sep 2010 14:30:41 -0500 From: Sebastian Pop To: gcc-patches@gcc.gnu.org Cc: gcc-graphite@googlegroups.com, Sebastian Pop Subject: [PATCH 6/8] Fix pbb_number_of_iterations_at_time. Date: Thu, 9 Sep 2010 14:30:04 -0500 Message-Id: <1284060606-26216-6-git-send-email-sebpop@gmail.com> In-Reply-To: <1284060606-26216-1-git-send-email-sebpop@gmail.com> References: <1284060606-26216-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 2010-09-09 Sebastian Pop * graphite-poly.c (pbb_number_of_iterations): Removed. (pbb_number_of_iterations_at_time): Correctly compute the number of iterations in the transformed loop. * graphite-poly.h (pbb_number_of_iterations): Removed. --- gcc/ChangeLog.graphite | 7 ++ gcc/graphite-interchange.c | 2 +- gcc/graphite-poly.c | 143 ++++++++++++++++++++++++++++--------------- gcc/graphite-poly.h | 1 - 4 files changed, 101 insertions(+), 52 deletions(-) diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index 7d37d41..ea2c115 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,5 +1,12 @@ 2010-09-09 Sebastian Pop + * graphite-poly.c (pbb_number_of_iterations): Removed. + (pbb_number_of_iterations_at_time): Correctly compute the number + of iterations in the transformed loop. + * graphite-poly.h (pbb_number_of_iterations): Removed. + +2010-09-09 Sebastian Pop + * graphite-poly.h (lst_update_scattering_seq): Removed. (lst_update_scattering): Correctly handle outermost loop dewey renumbering. diff --git a/gcc/graphite-interchange.c b/gcc/graphite-interchange.c index 83027d3..e4cab49 100644 --- a/gcc/graphite-interchange.c +++ b/gcc/graphite-interchange.c @@ -320,7 +320,7 @@ pdr_stride_in_loop (mpz_t stride, graphite_dim_t depth, poly_dr_p pdr) { char *str; void (*gmp_free) (void *, size_t); - + fprintf (dump_file, "\nStride in BB_%d, DR_%d, depth %d:", pbb_index (pbb), PDR_ID (pdr), (int) depth); str = mpz_get_str (0, 10, stride); diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c index 4220c05..0a3cc1f 100644 --- a/gcc/graphite-poly.c +++ b/gcc/graphite-poly.c @@ -1623,72 +1623,115 @@ psct_scattering_dim_for_loop_depth (poly_bb_p pbb, graphite_dim_t loop_depth) gcc_unreachable (); } -/* Returns the number of iterations NITER of the loop around PBB at - depth LOOP_DEPTH. */ - -void -pbb_number_of_iterations (poly_bb_p pbb, - graphite_dim_t loop_depth, - mpz_t niter) -{ - ppl_Linear_Expression_t le; - ppl_dimension_type dim; - - ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dim); - ppl_new_Linear_Expression_with_dimension (&le, dim); - ppl_set_coef (le, pbb_iterator_dim (pbb, loop_depth), 1); - mpz_set_si (niter, -1); - ppl_max_for_le_pointset (PBB_DOMAIN (pbb), le, niter); - ppl_delete_Linear_Expression (le); -} - -/* Returns the number of iterations NITER of the loop around PBB at +/* Returns the number of iterations RES of the loop around PBB at time(scattering) dimension TIME_DEPTH. */ void pbb_number_of_iterations_at_time (poly_bb_p pbb, graphite_dim_t time_depth, - mpz_t niter) + mpz_t res) { - ppl_Pointset_Powerset_C_Polyhedron_t ext_domain, sctr; + ppl_Pointset_Powerset_C_Polyhedron_t domain, sctr_lb, sctr_ub; + ppl_dimension_type domain_dim, sctr_dim; ppl_Linear_Expression_t le; - ppl_dimension_type dim; - - /* Takes together domain and scattering polyhedrons, and composes - them into the bigger polyhedron that has the following format: + mpz_t lb, ub, diff, one; + int i; - t0..t_{n-1} | l0..l_{nlcl-1} | i0..i_{niter-1} | g0..g_{nparm-1} + ppl_Polyhedron_space_dimension (PBB_TRANSFORMED_SCATTERING (pbb), &sctr_dim); - where - | t0..t_{n-1} are time dimensions (scattering dimensions) - | l0..l_{nclc-1} are local variables in scattering function - | i0..i_{niter-1} are original iteration variables - | g0..g_{nparam-1} are global parameters. */ + ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron + (&domain, PBB_DOMAIN (pbb)); - ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sctr, - PBB_TRANSFORMED_SCATTERING (pbb)); + ppl_Pointset_Powerset_C_Polyhedron_space_dimension (domain, &domain_dim); + mpz_init (diff); + mpz_init (lb); + mpz_init (ub); + mpz_init (one); + mpz_set_si (one, 1); - /* Extend the iteration domain with the scattering dimensions: - 0..0 | 0..0 | i0..i_{niter-1} | g0..g_{nparm-1}. */ - ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron - (&ext_domain, PBB_DOMAIN (pbb)); - ppl_insert_dimensions_pointset (ext_domain, 0, - pbb_nb_scattering_transform (pbb) - + pbb_nb_local_vars (pbb)); + /* Compute the upper bound on the original iteration domain and add + that upper bound to the scattering. */ + ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron + (&sctr_ub, PBB_TRANSFORMED_SCATTERING (pbb)); + for (i = 0; i < (int) domain_dim; i++) + { + ppl_Linear_Expression_t eq; + ppl_Constraint_t pc; + ppl_Constraint_System_t cs; + ppl_Polyhedron_t ph; + ppl_Pointset_Powerset_C_Polyhedron_t pph; + + ppl_new_Linear_Expression_with_dimension (&le, domain_dim); + ppl_set_coef (le, i, 1); + ppl_min_for_le_pointset (domain, le, lb); + ppl_max_for_le_pointset (domain, le, ub); + mpz_sub (diff, ub, lb); + mpz_add (diff, diff, one); + + ppl_new_Linear_Expression_with_dimension (&eq, sctr_dim); + ppl_set_coef (eq, psct_iterator_dim (pbb, i), -1); + ppl_set_inhomogeneous_gmp (eq, diff); + + ppl_new_Constraint (&pc, eq, PPL_CONSTRAINT_TYPE_EQUAL); + ppl_new_Constraint_System_from_Constraint (&cs, pc); + ppl_new_C_Polyhedron_from_Constraint_System (&ph, cs); + ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph, ph); + ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_ub, pph); + + ppl_delete_Linear_Expression (le); + ppl_delete_Linear_Expression (eq); + ppl_delete_Polyhedron (ph); + ppl_delete_Pointset_Powerset_C_Polyhedron (pph); + ppl_delete_Constraint (pc); + ppl_delete_Constraint_System (cs); + } - /* Add to sctr the extended domain. */ - ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr, ext_domain); + /* Compute the lower bound on the original iteration domain. */ + ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron + (&sctr_lb, PBB_TRANSFORMED_SCATTERING (pbb)); + for (i = 0; i < (int) domain_dim; i++) + { + ppl_Linear_Expression_t eq; + ppl_Constraint_t pc; + ppl_Constraint_System_t cs; + ppl_Polyhedron_t ph; + ppl_Pointset_Powerset_C_Polyhedron_t pph; + + ppl_new_Linear_Expression_with_dimension (&le, domain_dim); + ppl_set_coef (le, i, 1); + ppl_min_for_le_pointset (domain, le, lb); + + ppl_new_Linear_Expression_with_dimension (&eq, sctr_dim); + ppl_set_coef (eq, psct_iterator_dim (pbb, i), -1); + ppl_set_inhomogeneous_gmp (eq, lb); + + ppl_new_Constraint (&pc, eq, PPL_CONSTRAINT_TYPE_EQUAL); + ppl_new_Constraint_System_from_Constraint (&cs, pc); + ppl_new_C_Polyhedron_from_Constraint_System (&ph, cs); + ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph, ph); + ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_lb, pph); + + ppl_delete_Linear_Expression (le); + ppl_delete_Linear_Expression (eq); + ppl_delete_Polyhedron (ph); + ppl_delete_Pointset_Powerset_C_Polyhedron (pph); + ppl_delete_Constraint (pc); + ppl_delete_Constraint_System (cs); + } /* Extract the number of iterations. */ - ppl_Pointset_Powerset_C_Polyhedron_space_dimension (sctr, &dim); - ppl_new_Linear_Expression_with_dimension (&le, dim); + ppl_new_Linear_Expression_with_dimension (&le, sctr_dim); ppl_set_coef (le, time_depth, 1); - mpz_set_si (niter, -1); - ppl_max_for_le_pointset (sctr, le, niter); + ppl_min_for_le_pointset (sctr_lb, le, lb); + ppl_max_for_le_pointset (sctr_ub, le, ub); + mpz_sub (res, ub, lb); - ppl_delete_Linear_Expression (le); - ppl_delete_Pointset_Powerset_C_Polyhedron (sctr); - ppl_delete_Pointset_Powerset_C_Polyhedron (ext_domain); + mpz_clear (one); + mpz_clear (diff); + mpz_clear (lb); + mpz_clear (ub); + ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_ub); + ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_lb); } /* Translates LOOP to LST. */ diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h index e93c2ad..98ce124 100644 --- a/gcc/graphite-poly.h +++ b/gcc/graphite-poly.h @@ -414,7 +414,6 @@ extern void debug_iteration_domains (scop_p, int); extern bool scop_do_interchange (scop_p); extern bool scop_do_strip_mine (scop_p); extern bool scop_do_block (scop_p); -extern void pbb_number_of_iterations (poly_bb_p, graphite_dim_t, mpz_t); extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, mpz_t); extern void pbb_remove_duplicate_pdrs (poly_bb_p);