[PATCH 2/2] Fix PR47654: Loop blocking should strip-mine at least two loops.
Sebastian Pop
sebpop@gmail.com
Tue Feb 22 00:54:00 GMT 2011
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?
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" } } */
--
1.7.1
More information about the Gcc-patches
mailing list