[PATCH 2/2] Fix PR47654: Loop blocking should strip-mine at least two loops.
Richard Guenther
rguenther@suse.de
Tue Feb 22 10:07:00 GMT 2011
On Mon, 21 Feb 2011, Sebastian Pop wrote:
> Hi,
>
> loop blocking is the composition of a strip mine of all the loops in a
> loop nest followed by a loop interchange. When strip mining cannot be
> performed on at least two loops, there is no point calling this a loop
> blocking. This patch counts the number of loops strip-mined and
> interchanged and undoes the transform when there are not enough loops
> strip-mined or interchanged.
>
> This passed the graphite testsuite. I am currently regstrapping this
> patch on amd64-linux. Ok for trunk?
Ok.
Thanks,
Richard.
> Thanks,
> Sebastian
>
> 2011-02-22 Sebastian Pop <sebastian.pop@amd.com>
>
> 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 c1676bb..8a7b8f9 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,6 +1,19 @@
> 2011-02-22 Sebastian Pop <sebastian.pop@amd.com>
>
> 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-02-22 Sebastian Pop <sebastian.pop@amd.com>
> +
> + PR tree-optimization/47654
> * graphite-clast-to-gimple.c (gcc_type_for_interval): Call mpz_swap.
> (gcc_type_for_value): Removed.
> (gcc_type_for_clast_term): Removed.
> 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 b6d9a92..4987aa9 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,6 +1,11 @@
> 2011-02-22 Sebastian Pop <sebastian.pop@amd.com>
>
> PR tree-optimization/47654
> + * gcc.dg/graphite/block-pr47654.c: New.
> +
> +2011-02-22 Sebastian Pop <sebastian.pop@amd.com>
> +
> + PR tree-optimization/47654
> * gcc.dg/graphite/run-id-pr47654.c: New.
>
> 2011-02-13 Tobias Burnus <burnus@net-b.de>
> 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" } } */
>
--
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex
More information about the Gcc-patches
mailing list