From patchwork Wed Jun 29 17:35:19 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 102649 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 29DA4B6F18 for ; Thu, 30 Jun 2011 03:37:09 +1000 (EST) Received: (qmail 9507 invoked by alias); 29 Jun 2011 17:36:41 -0000 Received: (qmail 8619 invoked by uid 22791); 29 Jun 2011 17:36:36 -0000 X-SWARE-Spam-Status: No, hits=-2.3 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-gw0-f47.google.com (HELO mail-gw0-f47.google.com) (74.125.83.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 29 Jun 2011 17:36:15 +0000 Received: by gwb11 with SMTP id 11so635837gwb.20 for ; Wed, 29 Jun 2011 10:36:14 -0700 (PDT) Received: by 10.150.46.4 with SMTP id t4mr907084ybt.386.1309368974127; Wed, 29 Jun 2011 10:36:14 -0700 (PDT) Received: from napoca ([163.181.251.115]) by mx.google.com with ESMTPS id g12sm445410ybf.16.2011.06.29.10.36.11 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 29 Jun 2011 10:36:13 -0700 (PDT) Received: by napoca (sSMTP sendmail emulation); Wed, 29 Jun 2011 12:36:10 -0500 From: Sebastian Pop To: gcc-patches@gcc.gnu.org Cc: rguenther@suse.de, Sebastian Pop Subject: [PATCH 3/6] Fix PR47654: Loop blocking should strip-mine at least two loops. Date: Wed, 29 Jun 2011 12:35:19 -0500 Message-Id: <1309368922-25238-4-git-send-email-sebpop@gmail.com> In-Reply-To: <1309368922-25238-1-git-send-email-sebpop@gmail.com> References: <1309368922-25238-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 2011-06-29 Sebastian Pop PR tree-optimization/47654 * graphite-blocking.c (pbb_strip_mine_time_depth): Do not return bool. (lst_do_strip_mine_loop): Return an int. (lst_do_strip_mine): Same. (scop_do_strip_mine): Same. (scop_do_block): Loop blocking should strip-mine at least two loops. * graphite-interchange.c (lst_interchange_select_outer): Return an int. (scop_do_interchange): Same. * graphite-poly.h (scop_do_interchange): Update declaration. (scop_do_strip_mine): Same. * gcc.dg/graphite/block-pr47654.c: New. --- gcc/ChangeLog | 13 +++++ gcc/graphite-blocking.c | 59 +++++++++++-------------- gcc/graphite-interchange.c | 21 +++++---- gcc/graphite-poly.h | 4 +- gcc/testsuite/ChangeLog | 5 ++ gcc/testsuite/gcc.dg/graphite/block-pr47654.c | 25 ++++++++++ 6 files changed, 82 insertions(+), 45 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/graphite/block-pr47654.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index b0e3173..828559a 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,18 @@ 2011-06-29 Sebastian Pop + PR tree-optimization/47654 + * graphite-blocking.c (pbb_strip_mine_time_depth): Do not return bool. + (lst_do_strip_mine_loop): Return an int. + (lst_do_strip_mine): Same. + (scop_do_strip_mine): Same. + (scop_do_block): Loop blocking should strip-mine at least two loops. + * graphite-interchange.c (lst_interchange_select_outer): Return an int. + (scop_do_interchange): Same. + * graphite-poly.h (scop_do_interchange): Update declaration. + (scop_do_strip_mine): Same. + +2011-06-29 Sebastian Pop + * graphite-ppl.h (value_max): Correct computation of max. 2011-06-29 Sebastian Pop diff --git a/gcc/graphite-blocking.c b/gcc/graphite-blocking.c index bcd077a..967de9d 100644 --- a/gcc/graphite-blocking.c +++ b/gcc/graphite-blocking.c @@ -89,7 +89,7 @@ along with GCC; see the file COPYING3. If not see # } */ -static bool +static void pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride) { ppl_dimension_type iter, dim, strip; @@ -151,8 +151,6 @@ pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride) ppl_Polyhedron_add_constraint (res, new_cstr); ppl_delete_Constraint (new_cstr); } - - return true; } /* Returns true when strip mining with STRIDE of the loop LST is @@ -177,10 +175,10 @@ lst_strip_mine_profitable_p (lst_p lst, int stride) return res; } -/* Strip-mines all the loops of LST with STRIDE. Return true if it - did strip-mined some loops. */ +/* Strip-mines all the loops of LST with STRIDE. Return the number of + loops strip-mined. */ -static bool +static int lst_do_strip_mine_loop (lst_p lst, int depth, int stride) { int i; @@ -188,26 +186,26 @@ lst_do_strip_mine_loop (lst_p lst, int depth, int stride) poly_bb_p pbb; if (!lst) - return false; + return 0; if (LST_LOOP_P (lst)) { - bool res = false; + int res = 0; FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l) - res |= lst_do_strip_mine_loop (l, depth, stride); + res += lst_do_strip_mine_loop (l, depth, stride); return res; } pbb = LST_PBB (lst); - return pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth), - stride); + pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth), stride); + return 1; } /* Strip-mines all the loops of LST with STRIDE. When STRIDE is zero, - read the stride from the PARAM_LOOP_BLOCK_TILE_SIZE. Return true - if it did strip-mined some loops. + read the stride from the PARAM_LOOP_BLOCK_TILE_SIZE. Return the + number of strip-mined loops. Strip mining transforms a loop @@ -221,12 +219,12 @@ lst_do_strip_mine_loop (lst_p lst, int depth, int stride) | S (i = k + j); */ -static bool +static int lst_do_strip_mine (lst_p lst, int stride) { int i; lst_p l; - bool res = false; + int res = 0; int depth; if (!stride) @@ -237,23 +235,23 @@ lst_do_strip_mine (lst_p lst, int stride) return false; FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l) - res |= lst_do_strip_mine (l, stride); + res += lst_do_strip_mine (l, stride); depth = lst_depth (lst); if (depth >= 0 && lst_strip_mine_profitable_p (lst, stride)) { - res |= lst_do_strip_mine_loop (lst, lst_depth (lst), stride); + res += lst_do_strip_mine_loop (lst, lst_depth (lst), stride); lst_add_loop_under_loop (lst); } return res; } -/* Strip mines all the loops in SCOP. Returns true when some loops - have been strip-mined. */ +/* Strip mines all the loops in SCOP. Returns the number of + strip-mined loops. */ -bool +int scop_do_strip_mine (scop_p scop, int stride) { return lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), stride); @@ -265,27 +263,22 @@ scop_do_strip_mine (scop_p scop, int stride) bool scop_do_block (scop_p scop) { - bool strip_mined = false; - bool interchanged = false; - store_scattering (scop); - strip_mined = lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), 0); - interchanged = scop_do_interchange (scop); - - /* If we don't interchange loops, the strip mine alone will not be - profitable, and the transform is not a loop blocking: so revert - the transform. */ - if (!interchanged) + /* If we don't strip mine at least two loops, or not interchange + loops, the strip mine alone will not be profitable, and the + transform is not a loop blocking: so revert the transform. */ + if (lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), 0) < 2 + || scop_do_interchange (scop) == 0) { restore_scattering (scop); return false; } - else if (strip_mined && interchanged - && dump_file && (dump_flags & TDF_DETAILS)) + + if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "SCoP will be loop blocked.\n"); - return strip_mined || interchanged; + return true; } #endif diff --git a/gcc/graphite-interchange.c b/gcc/graphite-interchange.c index 934839a..cb4d32c 100644 --- a/gcc/graphite-interchange.c +++ b/gcc/graphite-interchange.c @@ -664,27 +664,27 @@ lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer, } /* Interchanges all the loops of LOOP and the loops of its body that - are considered profitable to interchange. Return true if it did - interchanged some loops. OUTER is the index in LST_SEQ (LOOP) that + are considered profitable to interchange. Return the number of + interchanged loops. OUTER is the index in LST_SEQ (LOOP) that points to the next outer loop to be considered for interchange. */ -static bool +static int lst_interchange_select_outer (scop_p scop, lst_p loop, int outer) { lst_p l; - bool res = false; + int res = 0; int i = 0; lst_p father; if (!loop || !LST_LOOP_P (loop)) - return false; + return 0; father = LST_LOOP_FATHER (loop); if (father) { while (lst_interchange_select_inner (scop, father, outer, loop)) { - res = true; + res++; loop = VEC_index (lst_p, LST_SEQ (father), outer); } } @@ -692,17 +692,18 @@ lst_interchange_select_outer (scop_p scop, lst_p loop, int outer) if (LST_LOOP_P (loop)) FOR_EACH_VEC_ELT (lst_p, LST_SEQ (loop), i, l) if (LST_LOOP_P (l)) - res |= lst_interchange_select_outer (scop, l, i); + res += lst_interchange_select_outer (scop, l, i); return res; } -/* Interchanges all the loop depths that are considered profitable for SCOP. */ +/* Interchanges all the loop depths that are considered profitable for + SCOP. Return the number of interchanged loops. */ -bool +int scop_do_interchange (scop_p scop) { - bool res = lst_interchange_select_outer + int res = lst_interchange_select_outer (scop, SCOP_TRANSFORMED_SCHEDULE (scop), 0); lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop)); diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h index 3bf87b0..417e99e 100644 --- a/gcc/graphite-poly.h +++ b/gcc/graphite-poly.h @@ -410,8 +410,8 @@ extern void print_iteration_domain (FILE *, poly_bb_p, int); extern void print_iteration_domains (FILE *, scop_p, int); extern void debug_iteration_domain (poly_bb_p, int); extern void debug_iteration_domains (scop_p, int); -extern bool scop_do_interchange (scop_p); -extern bool scop_do_strip_mine (scop_p, int); +extern int scop_do_interchange (scop_p); +extern int scop_do_strip_mine (scop_p, int); extern bool scop_do_block (scop_p); extern bool flatten_all_loops (scop_p); extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, mpz_t); diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index d30d8b0..6f35b5e 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2011-06-29 Sebastian Pop + + PR tree-optimization/47654 + * gcc.dg/graphite/block-pr47654.c: New. + 2011-06-29 Jason Merrill PR c++/45923 diff --git a/gcc/testsuite/gcc.dg/graphite/block-pr47654.c b/gcc/testsuite/gcc.dg/graphite/block-pr47654.c new file mode 100644 index 0000000..9cdeb0c --- /dev/null +++ b/gcc/testsuite/gcc.dg/graphite/block-pr47654.c @@ -0,0 +1,25 @@ +int a[128][40]; + +void __attribute__ ((noinline, noclone)) +foo (void) +{ + int i, j; + for (i = 0; i < 40; i++) + for (j = 0; j < 128; j++) + a[j][i] = 4; +} + +int +main () +{ + int i, j; + foo (); + for (i = 0; i < 40; i++) + for (j = 0; j < 128; j++) + if (a[j][i] != 4) + __builtin_abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-not "will be loop blocked" "graphite" } } */ +/* { dg-final { cleanup-tree-dump "graphite" } } */