* [PATCH 09/10] Expect at least the version 0.11 of PPL.
2011-01-15 9:09 [PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear Sebastian Pop
@ 2011-01-15 9:09 ` Sebastian Pop
2011-01-15 9:09 ` [PATCH 05/10] speedup compilation Sebastian Pop
` (9 subsequent siblings)
10 siblings, 0 replies; 21+ messages in thread
From: Sebastian Pop @ 2011-01-15 9:09 UTC (permalink / raw)
To: gcc-patches; +Cc: rguenther, gcc-graphite, Sebastian Pop
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
toplev/
* configure: Regenerated.
* configure.ac: Check for version 0.11 (or later revision) of PPL.
toplev/gcc/
* doc/install.texi: Update the expected version number of PPL to 0.11.
* graphite-ppl.c (ppl_powerset_is_empty): Remove now dead code under
#if PPL_VERSION_MINOR < 11.
---
ChangeLog.graphite | 5 +++++
configure | 6 +++---
configure.ac | 4 ++--
gcc/ChangeLog.graphite | 6 ++++++
gcc/doc/install.texi | 2 +-
gcc/graphite-ppl.c | 10 ----------
6 files changed, 17 insertions(+), 16 deletions(-)
diff --git a/ChangeLog.graphite b/ChangeLog.graphite
index e0e5725..987aefa 100644
--- a/ChangeLog.graphite
+++ b/ChangeLog.graphite
@@ -1,3 +1,8 @@
+2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+
+ * configure: Regenerated.
+ * configure.ac: Check for version 0.11 (or later revision) of PPL.
+
2011-01-13 Tobias Grosser <grosser@fim.uni-passau.de>
* configure: Regenerated.
diff --git a/configure b/configure
index e1ed49f..ac55cfb 100755
--- a/configure
+++ b/configure
@@ -5709,8 +5709,8 @@ fi
if test "x$with_ppl" != "xno" -a "${ENABLE_PPL_CHECK}" = "yes"; then
saved_CFLAGS="$CFLAGS"
CFLAGS="$CFLAGS $pplinc $gmpinc"
- { $as_echo "$as_me:${as_lineno-$LINENO}: checking for version 0.10 (or later revision) of PPL" >&5
-$as_echo_n "checking for version 0.10 (or later revision) of PPL... " >&6; }
+ { $as_echo "$as_me:${as_lineno-$LINENO}: checking for version 0.11 (or later revision) of PPL" >&5
+$as_echo_n "checking for version 0.11 (or later revision) of PPL... " >&6; }
cat confdefs.h - <<_ACEOF >conftest.$ac_ext
/* end confdefs.h. */
#include "ppl_c.h"
@@ -5718,7 +5718,7 @@ int
main ()
{
- #if PPL_VERSION_MAJOR != 0 || PPL_VERSION_MINOR < 10
+ #if PPL_VERSION_MAJOR != 0 || PPL_VERSION_MINOR < 11
choke me
#endif
diff --git a/configure.ac b/configure.ac
index 1ff3047..877b3b7 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1637,9 +1637,9 @@ ENABLE_PPL_CHECK=yes)
if test "x$with_ppl" != "xno" -a "${ENABLE_PPL_CHECK}" = "yes"; then
saved_CFLAGS="$CFLAGS"
CFLAGS="$CFLAGS $pplinc $gmpinc"
- AC_MSG_CHECKING([for version 0.10 (or later revision) of PPL])
+ AC_MSG_CHECKING([for version 0.11 (or later revision) of PPL])
AC_TRY_COMPILE([#include "ppl_c.h"],[
- #if PPL_VERSION_MAJOR != 0 || PPL_VERSION_MINOR < 10
+ #if PPL_VERSION_MAJOR != 0 || PPL_VERSION_MINOR < 11
choke me
#endif
], [AC_MSG_RESULT([yes])], [AC_MSG_RESULT([no]); ppllibs= ; pplinc= ; with_ppl=no ])
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 51a5407..8328af3 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,11 @@
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+ * doc/install.texi: Update the expected version number of PPL to 0.11.
+ * graphite-ppl.c (ppl_powerset_is_empty): Remove now dead code under
+ #if PPL_VERSION_MINOR < 11.
+
+2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+
* graphite-dependences.c (new_poly_ddr): Inlined into
dependence_polyhedron.
(free_poly_ddr): Moved close by new_poly_ddr.
diff --git a/gcc/doc/install.texi b/gcc/doc/install.texi
index 650754e..b47049b 100644
--- a/gcc/doc/install.texi
+++ b/gcc/doc/install.texi
@@ -332,7 +332,7 @@ and @option{--with-mpc-include}. Alternatively, if an MPC source
distribution is found in a subdirectory of your GCC sources named
@file{mpc}, it will be built together with GCC@.
-@item Parma Polyhedra Library (PPL) version 0.10
+@item Parma Polyhedra Library (PPL) version 0.11
Necessary to build GCC with the Graphite loop optimizations.
It can be downloaded from @uref{http://www.cs.unipr.it/ppl/Download/}.
diff --git a/gcc/graphite-ppl.c b/gcc/graphite-ppl.c
index d879d78..1a08362 100644
--- a/gcc/graphite-ppl.c
+++ b/gcc/graphite-ppl.c
@@ -525,15 +525,6 @@ bool
ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps,
int nb_params ATTRIBUTE_UNUSED)
{
-#if PPL_VERSION_MAJOR == 0 && PPL_VERSION_MINOR < 11
- /* On PPL 0.10,
- ppl_Pointset_Powerset_C_Polyhedron_contains_integer_point (ps)
- takes too long on some cases and so we call _is_empty instead. */
- return ppl_Pointset_Powerset_C_Polyhedron_is_empty (ps);
-
-#else
- /* On PPL 0.11 or later, we can check for integer feasibility using
- the PIP solver. */
ppl_PIP_Problem_t pip;
ppl_dimension_type d;
ppl_const_Constraint_System_t pcs;
@@ -585,7 +576,6 @@ ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps,
free (ds);
return !has_integer_solutions;
-#endif
}
#endif
--
1.7.1
^ permalink raw reply [flat|nested] 21+ messages in thread* [PATCH 05/10] speedup compilation
2011-01-15 9:09 [PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear Sebastian Pop
2011-01-15 9:09 ` [PATCH 09/10] Expect at least the version 0.11 of PPL Sebastian Pop
@ 2011-01-15 9:09 ` Sebastian Pop
2011-01-15 9:09 ` [PATCH 02/10] Print the data dependence polyhedron in the PPL format Sebastian Pop
` (8 subsequent siblings)
10 siblings, 0 replies; 21+ messages in thread
From: Sebastian Pop @ 2011-01-15 9:09 UTC (permalink / raw)
To: gcc-patches; +Cc: rguenther, gcc-graphite, Sebastian Pop
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
* graphite-dependences.c (build_lexicographical_constraint): Stop the
iteration when the bag of constraints is empty.
---
gcc/ChangeLog.graphite | 5 +++++
gcc/graphite-dependences.c | 7 ++++++-
2 files changed, 11 insertions(+), 1 deletions(-)
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 4368926..470428a 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,10 @@
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+ * graphite-dependences.c (build_lexicographical_constraint): Stop the
+ iteration when the bag of constraints is empty.
+
+2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+
* graphite-poly.c (pbb_remove_duplicate_pdrs): Make it work.
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
index 474bd9a..cb2241b 100644
--- a/gcc/graphite-dependences.c
+++ b/gcc/graphite-dependences.c
@@ -335,7 +335,9 @@ dr_equality_constraints (graphite_dim_t dim,
/* Builds scheduling inequality constraints: when DIRECTION is
1 builds a GE constraint,
0 builds an EQ constraint,
- -1 builds a LE constraint. */
+ -1 builds a LE constraint.
+ DIM is the dimension of the scheduling space.
+ POS and POS + OFFSET are the dimensions that are related. */
static ppl_Pointset_Powerset_C_Polyhedron_t
build_pairwise_scheduling (graphite_dim_t dim,
@@ -418,6 +420,9 @@ build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag, sceq);
ppl_delete_Pointset_Powerset_C_Polyhedron (sceq);
+ if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (bag))
+ break;
+
lex = build_pairwise_scheduling (dim, i + 1, offset, direction);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
--
1.7.1
^ permalink raw reply [flat|nested] 21+ messages in thread* [PATCH 02/10] Print the data dependence polyhedron in the PPL format.
2011-01-15 9:09 [PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear Sebastian Pop
2011-01-15 9:09 ` [PATCH 09/10] Expect at least the version 0.11 of PPL Sebastian Pop
2011-01-15 9:09 ` [PATCH 05/10] speedup compilation Sebastian Pop
@ 2011-01-15 9:09 ` Sebastian Pop
2011-01-15 9:09 ` [PATCH 06/10] Correct the precedence relation Sebastian Pop
` (7 subsequent siblings)
10 siblings, 0 replies; 21+ messages in thread
From: Sebastian Pop @ 2011-01-15 9:09 UTC (permalink / raw)
To: gcc-patches; +Cc: rguenther, gcc-graphite, Sebastian Pop
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
* graphite-dependences.c (print_pddr): Call
ppl_io_fprint_Pointset_Powerset_C_Polyhedron.
---
gcc/ChangeLog.graphite | 5 +++++
gcc/graphite-dependences.c | 1 +
2 files changed, 6 insertions(+), 0 deletions(-)
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 64df5cd..d3bb503 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,10 @@
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+ * graphite-dependences.c (print_pddr): Call
+ ppl_io_fprint_Pointset_Powerset_C_Polyhedron.
+
+2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+
* graphite-ppl.c (debug_gmp_value): New.
* graphite-ppl.h (debug_gmp_value): Declared.
diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
index 18eed4c..474bd9a 100644
--- a/gcc/graphite-dependences.c
+++ b/gcc/graphite-dependences.c
@@ -181,6 +181,7 @@ print_pddr (FILE *file, poly_ddr_p pddr)
fprintf (file, "\n dependence polyhedron (\n");
print_dependence_polyhedron_layout (file, pddr);
ppl_print_powerset_matrix (file, PDDR_DDP (pddr));
+ ppl_io_fprint_Pointset_Powerset_C_Polyhedron (file, PDDR_DDP (pddr));
fprintf (file, ")\n");
}
--
1.7.1
^ permalink raw reply [flat|nested] 21+ messages in thread* [PATCH 06/10] Correct the precedence relation.
2011-01-15 9:09 [PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear Sebastian Pop
` (2 preceding siblings ...)
2011-01-15 9:09 ` [PATCH 02/10] Print the data dependence polyhedron in the PPL format Sebastian Pop
@ 2011-01-15 9:09 ` Sebastian Pop
2011-01-15 9:09 ` [PATCH 04/10] Fix pbb_remove_duplicate_pdrs Sebastian Pop
` (6 subsequent siblings)
10 siblings, 0 replies; 21+ messages in thread
From: Sebastian Pop @ 2011-01-15 9:09 UTC (permalink / raw)
To: gcc-patches; +Cc: rguenther, gcc-graphite, Sebastian Pop
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
* graphite-dependences.c (build_pairwise_scheduling): Correctly compute
the "a followed by b" relation and document it.
---
gcc/ChangeLog.graphite | 5 +++++
gcc/graphite-dependences.c | 15 ++++++++++-----
2 files changed, 15 insertions(+), 5 deletions(-)
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 470428a..86ba9c9 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,10 @@
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+ * graphite-dependences.c (build_pairwise_scheduling): Correctly compute
+ the "a followed by b" relation and document it.
+
+2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+
* graphite-dependences.c (build_lexicographical_constraint): Stop the
iteration when the bag of constraints is empty.
diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
index cb2241b..5e4e087 100644
--- a/gcc/graphite-dependences.c
+++ b/gcc/graphite-dependences.c
@@ -348,23 +348,28 @@ build_pairwise_scheduling (graphite_dim_t dim,
ppl_Pointset_Powerset_C_Polyhedron_t res;
ppl_Polyhedron_t equalities;
ppl_Constraint_t cstr;
+ graphite_dim_t a = pos;
+ graphite_dim_t b = pos + offset;
ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0);
switch (direction)
{
- case -1:
- cstr = ppl_build_relation (dim, pos, pos + offset, 1,
+ case 1:
+ /* Builds "a + 1 <= b. */
+ cstr = ppl_build_relation (dim, a, b, 1,
PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
break;
case 0:
- cstr = ppl_build_relation (dim, pos, pos + offset, 0,
+ /* Builds "a = b. */
+ cstr = ppl_build_relation (dim, a, b, 0,
PPL_CONSTRAINT_TYPE_EQUAL);
break;
- case 1:
- cstr = ppl_build_relation (dim, pos, pos + offset, -1,
+ case -1:
+ /* Builds "a >= b + 1. */
+ cstr = ppl_build_relation (dim, a, b, -1,
PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
break;
--
1.7.1
^ permalink raw reply [flat|nested] 21+ messages in thread* [PATCH 04/10] Fix pbb_remove_duplicate_pdrs.
2011-01-15 9:09 [PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear Sebastian Pop
` (3 preceding siblings ...)
2011-01-15 9:09 ` [PATCH 06/10] Correct the precedence relation Sebastian Pop
@ 2011-01-15 9:09 ` Sebastian Pop
2011-01-15 9:09 ` [PATCH 01/10] Add debug_gmp_value Sebastian Pop
` (5 subsequent siblings)
10 siblings, 0 replies; 21+ messages in thread
From: Sebastian Pop @ 2011-01-15 9:09 UTC (permalink / raw)
To: gcc-patches; +Cc: rguenther, gcc-graphite, Sebastian Pop
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
* graphite-poly.c (pbb_remove_duplicate_pdrs): Make it work.
---
gcc/ChangeLog.graphite | 4 ++++
gcc/graphite-poly.c | 13 +++++++------
2 files changed, 11 insertions(+), 6 deletions(-)
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 4324a6e..4368926 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,9 @@
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+ * graphite-poly.c (pbb_remove_duplicate_pdrs): Make it work.
+
+2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+
* graphite-interchange.c (lst_interchange_profitable_p): Takes a loop
nest and two loop depths as parameters.
(lst_try_interchange_loops): Call lst_interchange_profitable_p after
diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c
index 9d44d0e..99f1a6f 100644
--- a/gcc/graphite-poly.c
+++ b/gcc/graphite-poly.c
@@ -813,15 +813,16 @@ pbb_remove_duplicate_pdrs (poly_bb_p pbb)
{
int i, j;
poly_dr_p pdr1, pdr2;
- unsigned n = VEC_length (poly_dr_p, PBB_DRS (pbb));
- VEC (poly_dr_p, heap) *collapsed = VEC_alloc (poly_dr_p, heap, n);
FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr1)
- FOR_EACH_VEC_ELT (poly_dr_p, collapsed, j, pdr2)
- if (!can_collapse_pdrs (pdr1, pdr2))
- VEC_quick_push (poly_dr_p, collapsed, pdr1);
+ for (j = i + 1; VEC_iterate (poly_dr_p, PBB_DRS (pbb), j, pdr2); j++)
+ if (can_collapse_pdrs (pdr1, pdr2))
+ {
+ PDR_NB_REFS (pdr1) += PDR_NB_REFS (pdr2);
+ free_poly_dr (pdr2);
+ VEC_ordered_remove (poly_dr_p, PBB_DRS (pbb), j);
+ }
- VEC_free (poly_dr_p, heap, collapsed);
PBB_PDR_DUPLICATES_REMOVED (pbb) = true;
}
--
1.7.1
^ permalink raw reply [flat|nested] 21+ messages in thread* [PATCH 01/10] Add debug_gmp_value.
2011-01-15 9:09 [PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear Sebastian Pop
` (4 preceding siblings ...)
2011-01-15 9:09 ` [PATCH 04/10] Fix pbb_remove_duplicate_pdrs Sebastian Pop
@ 2011-01-15 9:09 ` Sebastian Pop
2011-01-15 9:09 ` [PATCH 08/10] Minimize the number of expensive calls to ppl_powerset_is_empty Sebastian Pop
` (4 subsequent siblings)
10 siblings, 0 replies; 21+ messages in thread
From: Sebastian Pop @ 2011-01-15 9:09 UTC (permalink / raw)
To: gcc-patches; +Cc: rguenther, gcc-graphite, Sebastian Pop
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
* graphite-ppl.c (debug_gmp_value): New.
* graphite-ppl.h (debug_gmp_value): Declared.
---
gcc/ChangeLog.graphite | 5 +++++
gcc/graphite-ppl.c | 13 +++++++++++++
gcc/graphite-ppl.h | 1 +
3 files changed, 19 insertions(+), 0 deletions(-)
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index f681a63..64df5cd 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,3 +1,8 @@
+2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+
+ * graphite-ppl.c (debug_gmp_value): New.
+ * graphite-ppl.h (debug_gmp_value): Declared.
+
2011-01-13 Tobias Grosser <grosser@fim.uni-passau.de>
* doc/install.texi: Document availability of cloog-0.16
diff --git a/gcc/graphite-ppl.c b/gcc/graphite-ppl.c
index fffa3ee..3013b33 100644
--- a/gcc/graphite-ppl.c
+++ b/gcc/graphite-ppl.c
@@ -502,4 +502,17 @@ ppl_build_relation (int dim, int pos1, int pos2, int c,
return cstr;
}
+/* Print to STDERR the GMP value VAL. */
+
+DEBUG_FUNCTION void
+debug_gmp_value (mpz_t val)
+{
+ char *str = mpz_get_str (0, 10, val);
+ void (*gmp_free) (void *, size_t);
+
+ fprintf (stderr, "%s", str);
+ mp_get_memory_functions (NULL, NULL, &gmp_free);
+ (*gmp_free) (str, strlen (str) + 1);
+}
+
#endif
diff --git a/gcc/graphite-ppl.h b/gcc/graphite-ppl.h
index ec5d3c5..f6c279b 100644
--- a/gcc/graphite-ppl.h
+++ b/gcc/graphite-ppl.h
@@ -46,6 +46,7 @@ void ppl_min_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t,
ppl_Linear_Expression_t, mpz_t);
ppl_Constraint_t ppl_build_relation (int, int, int, int,
enum ppl_enum_Constraint_Type);
+void debug_gmp_value (mpz_t);
/* Assigns to RES the value of the INTEGER_CST T. */
--
1.7.1
^ permalink raw reply [flat|nested] 21+ messages in thread* [PATCH 08/10] Minimize the number of expensive calls to ppl_powerset_is_empty.
2011-01-15 9:09 [PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear Sebastian Pop
` (5 preceding siblings ...)
2011-01-15 9:09 ` [PATCH 01/10] Add debug_gmp_value Sebastian Pop
@ 2011-01-15 9:09 ` Sebastian Pop
2011-01-15 9:28 ` [PATCH 10/10] Remove the temporary array for reductions written to memory Sebastian Pop
` (3 subsequent siblings)
10 siblings, 0 replies; 21+ messages in thread
From: Sebastian Pop @ 2011-01-15 9:09 UTC (permalink / raw)
To: gcc-patches; +Cc: rguenther, gcc-graphite, Sebastian Pop
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
* graphite-dependences.c (new_poly_ddr): Inlined into
dependence_polyhedron.
(free_poly_ddr): Moved close by new_poly_ddr.
(dependence_polyhedron_1): Renamed dependence_polyhedron.
Early return NULL when ppl_powerset_is_empty returns true.
(dependence_polyhedron): Renamed new_poly_ddr. Call only once
poly_drs_may_alias_p. Avoid one call to ppl_powerset_is_empty.
(graphite_legal_transform_dr): Call new_poly_ddr.
(graphite_carried_dependence_level_k): Same.
(dot_original_deps_stmt_1): Renamed dot_deps_stmt_2. Use new_poly_ddr.
(dot_transformed_deps_stmt_1): Removed.
(dot_deps_stmt_1): Call dot_deps_stmt_2.
(dot_original_deps): Renamed dot_deps_2. Call new_poly_ddr.
(dot_deps_1): Call dot_deps_2.
---
gcc/ChangeLog.graphite | 17 ++++
gcc/graphite-dependences.c | 190 +++++++++++++++----------------------------
2 files changed, 83 insertions(+), 124 deletions(-)
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index b844d04..51a5407 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,22 @@
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+ * graphite-dependences.c (new_poly_ddr): Inlined into
+ dependence_polyhedron.
+ (free_poly_ddr): Moved close by new_poly_ddr.
+ (dependence_polyhedron_1): Renamed dependence_polyhedron.
+ Early return NULL when ppl_powerset_is_empty returns true.
+ (dependence_polyhedron): Renamed new_poly_ddr. Call only once
+ poly_drs_may_alias_p. Avoid one call to ppl_powerset_is_empty.
+ (graphite_legal_transform_dr): Call new_poly_ddr.
+ (graphite_carried_dependence_level_k): Same.
+ (dot_original_deps_stmt_1): Renamed dot_deps_stmt_2. Use new_poly_ddr.
+ (dot_transformed_deps_stmt_1): Removed.
+ (dot_deps_stmt_1): Call dot_deps_stmt_2.
+ (dot_original_deps): Renamed dot_deps_2. Call new_poly_ddr.
+ (dot_deps_1): Call dot_deps_2.
+
+2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+
* graphite-dependences.c (new_poly_dr): Call ppl_powerset_is_empty.
(build_lexicographical_constraint): Same.
(dependence_polyhedron_1): Same.
diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
index b7f9442..144f7b0 100644
--- a/gcc/graphite-dependences.c
+++ b/gcc/graphite-dependences.c
@@ -37,43 +37,6 @@ along with GCC; see the file COPYING3. If not see
#include "graphite-dependences.h"
#include "graphite-cloog-util.h"
-/* Returns a new polyhedral Data Dependence Relation (DDR). SOURCE is
- the source data reference, SINK is the sink data reference. When
- the Data Dependence Polyhedron DDP is not NULL or not empty, SOURCE
- and SINK are in dependence as described by DDP. */
-
-static poly_ddr_p
-new_poly_ddr (poly_dr_p source, poly_dr_p sink,
- ppl_Pointset_Powerset_C_Polyhedron_t ddp,
- bool original_scattering_p)
-{
- poly_ddr_p pddr = XNEW (struct poly_ddr);
-
- PDDR_SOURCE (pddr) = source;
- PDDR_SINK (pddr) = sink;
- PDDR_DDP (pddr) = ddp;
- PDDR_ORIGINAL_SCATTERING_P (pddr) = original_scattering_p;
-
- if (!ddp
- || ppl_powerset_is_empty (ddp,
- scop_nb_params (PBB_SCOP (PDR_PBB (source)))))
- PDDR_KIND (pddr) = no_dependence;
- else
- PDDR_KIND (pddr) = has_dependence;
-
- return pddr;
-}
-
-/* Free the poly_ddr_p P. */
-
-void
-free_poly_ddr (void *p)
-{
- poly_ddr_p pddr = (poly_ddr_p) p;
- ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr));
- free (pddr);
-}
-
/* Comparison function for poly_ddr hash table. */
int
@@ -459,8 +422,8 @@ build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
relation, from PDR2 to PDR1. */
static ppl_Pointset_Powerset_C_Polyhedron_t
-dependence_polyhedron_1 (poly_dr_p pdr1, poly_dr_p pdr2,
- int direction, bool original_scattering_p)
+dependence_polyhedron (poly_dr_p pdr1, poly_dr_p pdr2,
+ int direction, bool original_scattering_p)
{
poly_bb_p pbb1 = PDR_PBB (pdr1);
poly_bb_p pbb2 = PDR_PBB (pdr2);
@@ -480,6 +443,7 @@ dependence_polyhedron_1 (poly_dr_p pdr1, poly_dr_p pdr2,
ppl_Pointset_Powerset_C_Polyhedron_t res;
ppl_Pointset_Powerset_C_Polyhedron_t idr1, idr2;
ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq;
+ ppl_Pointset_Powerset_C_Polyhedron_t lex;
gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2));
@@ -513,16 +477,14 @@ dependence_polyhedron_1 (poly_dr_p pdr1, poly_dr_p pdr2,
ppl_delete_Pointset_Powerset_C_Polyhedron (idr2);
ppl_delete_Pointset_Powerset_C_Polyhedron (dreq);
- if (!ppl_powerset_is_empty (res, gdim))
- {
- ppl_Pointset_Powerset_C_Polyhedron_t lex =
- build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2),
+ if (ppl_powerset_is_empty (res, gdim))
+ return NULL;
+
+ lex = build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2),
tdim1 + ddim1, gdim, direction);
- ppl_delete_Pointset_Powerset_C_Polyhedron (res);
- res = lex;
- }
+ ppl_delete_Pointset_Powerset_C_Polyhedron (res);
- return res;
+ return lex;
}
/* Build the dependence polyhedron for data references PDR1 and PDR2.
@@ -533,12 +495,12 @@ dependence_polyhedron_1 (poly_dr_p pdr1, poly_dr_p pdr2,
relation, from PDR2 to PDR1. */
static poly_ddr_p
-dependence_polyhedron (poly_dr_p pdr1, poly_dr_p pdr2,
- int direction, bool original_scattering_p)
+new_poly_ddr (poly_dr_p pdr1, poly_dr_p pdr2,
+ int direction, bool original_scattering_p)
{
PTR *x = NULL;
poly_ddr_p res;
- ppl_Pointset_Powerset_C_Polyhedron_t ddp;
+ bool may_alias;
/* Return the PDDR from the cache if it already has been computed. */
if (original_scattering_p)
@@ -555,28 +517,51 @@ dependence_polyhedron (poly_dr_p pdr1, poly_dr_p pdr2,
return (poly_ddr_p) *x;
}
- if ((pdr_read_p (pdr1) && pdr_read_p (pdr2))
- || PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2)
- || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2)
- || !poly_drs_may_alias_p (pdr1, pdr2))
- ddp = NULL;
- else
- ddp = dependence_polyhedron_1 (pdr1, pdr2, direction,
- original_scattering_p);
+ res = XNEW (struct poly_ddr);
+ PDDR_SOURCE (res) = pdr1;
+ PDDR_SINK (res) = pdr2;
+ PDDR_DDP (res) = NULL;
+ PDDR_ORIGINAL_SCATTERING_P (res) = original_scattering_p;
+ PDDR_KIND (res) = unknown_dependence;
- res = new_poly_ddr (pdr1, pdr2, ddp, original_scattering_p);
+ may_alias = poly_drs_may_alias_p (pdr1, pdr2);
if (!(pdr_read_p (pdr1) && pdr_read_p (pdr2))
&& PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2)
- && poly_drs_may_alias_p (pdr1, pdr2))
+ && may_alias)
PDDR_KIND (res) = unknown_dependence;
+ else if (!(pdr_read_p (pdr1) && pdr_read_p (pdr2))
+ && PDR_BASE_OBJECT_SET (pdr1) == PDR_BASE_OBJECT_SET (pdr2)
+ && PDR_NB_SUBSCRIPTS (pdr1) == PDR_NB_SUBSCRIPTS (pdr2)
+ && may_alias)
+ {
+ PDDR_DDP (res) = dependence_polyhedron (pdr1, pdr2, direction,
+ original_scattering_p);
+ if (PDDR_DDP (res))
+ PDDR_KIND (res) = has_dependence;
+ else
+ PDDR_KIND (res) = no_dependence;
+ }
+ else
+ PDDR_KIND (res) = no_dependence;
+
if (original_scattering_p)
*x = res;
return res;
}
+/* Free the data dependence relation poly_ddr_p P. */
+
+void
+free_poly_ddr (void *p)
+{
+ poly_ddr_p pddr = (poly_ddr_p) p;
+ ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr));
+ free (pddr);
+}
+
/* Return true when the data dependence relation between the data
references PDR1 belonging to PBB1 and PDR2 is part of a
reduction. */
@@ -636,7 +621,7 @@ graphite_legal_transform_dr (poly_dr_p pdr1, poly_dr_p pdr2)
we get an empty intersection when the transform is legal:
i.e. the transform should reverse no dependences, and so PT, the
reversed transformed PDDR, should have no constraint from PO. */
- opddr = dependence_polyhedron (pdr1, pdr2, 1, true);
+ opddr = new_poly_ddr (pdr1, pdr2, 1, true);
if (PDDR_KIND (opddr) == unknown_dependence)
return false;
@@ -647,7 +632,7 @@ graphite_legal_transform_dr (poly_dr_p pdr1, poly_dr_p pdr2)
if (pddr_is_empty (opddr))
return true;
- tpddr = dependence_polyhedron (pdr1, pdr2, -1, false);
+ tpddr = new_poly_ddr (pdr1, pdr2, -1, false);
if (PDDR_KIND (tpddr) == unknown_dependence)
{
@@ -896,7 +881,7 @@ graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
graphite_dim_t ddim1 = pbb_dim_iter_domain (PDR_PBB (pdr1));
ppl_dimension_type dim;
bool empty_p;
- poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false);
+ poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, false);
if (PDDR_KIND (pddr) == unknown_dependence)
{
@@ -946,36 +931,12 @@ dependency_between_pbbs_p (poly_bb_p pbb1, poly_bb_p pbb2, int level)
return false;
}
-/* Pretty print to FILE all the original data dependences of SCoP in
- DOT format. */
+/* When ORIG is true, pretty print to FILE all the original data
+ dependences of SCoP in DOT format, otherwise print the transformed
+ data deps. */
static void
-dot_original_deps_stmt_1 (FILE *file, scop_p scop)
-{
- int i, j, k, l;
- poly_bb_p pbb1, pbb2;
- poly_dr_p pdr1, pdr2;
-
- FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1)
- FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2)
- {
- FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), k, pdr1)
- FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), l, pdr2)
- if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true)))
- {
- fprintf (file, "OS%d -> OS%d\n",
- pbb_index (pbb1), pbb_index (pbb2));
- goto done;
- }
- done:;
- }
-}
-
-/* Pretty print to FILE all the transformed data dependences of SCoP in
- DOT format. */
-
-static void
-dot_transformed_deps_stmt_1 (FILE *file, scop_p scop)
+dot_deps_stmt_2 (FILE *file, scop_p scop, bool orig)
{
int i, j, k, l;
poly_bb_p pbb1, pbb2;
@@ -987,11 +948,11 @@ dot_transformed_deps_stmt_1 (FILE *file, scop_p scop)
FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), k, pdr1)
FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), l, pdr2)
{
- poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false);
+ poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, orig);
if (!pddr_is_empty (pddr))
{
- fprintf (file, "TS%d -> TS%d\n",
+ fprintf (file, orig ? "OS%d -> OS%d\n" : "TS%d -> TS%d\n",
pbb_index (pbb1), pbb_index (pbb2));
free_poly_ddr (pddr);
@@ -1004,7 +965,6 @@ dot_transformed_deps_stmt_1 (FILE *file, scop_p scop)
}
}
-
/* Pretty print to FILE all the data dependences of SCoP in DOT
format. */
@@ -1013,37 +973,18 @@ dot_deps_stmt_1 (FILE *file, scop_p scop)
{
fputs ("digraph all {\n", file);
- dot_original_deps_stmt_1 (file, scop);
- dot_transformed_deps_stmt_1 (file, scop);
+ dot_deps_stmt_2 (file, scop, true);
+ dot_deps_stmt_2 (file, scop, false);
fputs ("}\n\n", file);
}
-/* Pretty print to FILE all the original data dependences of SCoP in
- DOT format. */
-
-static void
-dot_original_deps (FILE *file, scop_p scop)
-{
- int i, j, k, l;
- poly_bb_p pbb1, pbb2;
- poly_dr_p pdr1, pdr2;
-
- FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1)
- FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2)
- FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), k, pdr1)
- FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), l, pdr2)
- if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true)))
- fprintf (file, "OS%d_D%d -> OS%d_D%d\n",
- pbb_index (pbb1), PDR_ID (pdr1),
- pbb_index (pbb2), PDR_ID (pdr2));
-}
-
-/* Pretty print to FILE all the transformed data dependences of SCoP in
- DOT format. */
+/* When ORIG is true, pretty print to FILE all the original data
+ dependences of SCoP in DOT format, otherwise print the transformed
+ data deps. */
static void
-dot_transformed_deps (FILE *file, scop_p scop)
+dot_deps_2 (FILE *file, scop_p scop, bool orig)
{
int i, j, k, l;
poly_bb_p pbb1, pbb2;
@@ -1053,11 +994,12 @@ dot_transformed_deps (FILE *file, scop_p scop)
FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2)
FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), k, pdr1)
FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), l, pdr2)
- {
- poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false);
+ {
+ poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, orig);
if (!pddr_is_empty (pddr))
- fprintf (file, "TS%d_D%d -> TS%d_D%d\n",
+ fprintf (file, orig
+ ? "OS%d_D%d -> OS%d_D%d\n" : "TS%d_D%d -> TS%d_D%d\n",
pbb_index (pbb1), PDR_ID (pdr1),
pbb_index (pbb2), PDR_ID (pdr2));
@@ -1073,8 +1015,8 @@ dot_deps_1 (FILE *file, scop_p scop)
{
fputs ("digraph all {\n", file);
- dot_original_deps (file, scop);
- dot_transformed_deps (file, scop);
+ dot_deps_2 (file, scop, true);
+ dot_deps_2 (file, scop, false);
fputs ("}\n\n", file);
}
--
1.7.1
^ permalink raw reply [flat|nested] 21+ messages in thread* [PATCH 10/10] Remove the temporary array for reductions written to memory.
2011-01-15 9:09 [PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear Sebastian Pop
` (6 preceding siblings ...)
2011-01-15 9:09 ` [PATCH 08/10] Minimize the number of expensive calls to ppl_powerset_is_empty Sebastian Pop
@ 2011-01-15 9:28 ` Sebastian Pop
[not found] ` <AANLkTikHnNc5jznpHA51TySErrZ=7tiMYBFowcxLqk1a@mail.gmail.com>
2011-01-15 10:09 ` [PATCH 03/10] Test the profitability of interchange on the perfect nest Sebastian Pop
` (2 subsequent siblings)
10 siblings, 1 reply; 21+ messages in thread
From: Sebastian Pop @ 2011-01-15 9:28 UTC (permalink / raw)
To: gcc-patches; +Cc: rguenther, gcc-graphite, Sebastian Pop
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
* graphite-sese-to-poly.c
(translate_scalar_reduction_to_array_for_stmt): Call unshare_expr.
(close_phi_written_to_memory): New.
(translate_scalar_reduction_to_array): Call close_phi_written_to_memory
and unshare_expr.
* gcc.dg/graphite/block-0.c: Un-XFAILed.
* gcc.dg/graphite/block-1.c: Un-XFAILed.
* gcc.dg/graphite/block-7.c: Un-XFAILed.
* gcc.dg/graphite/block-8.c: Un-XFAILed.
* gcc.dg/graphite/interchange-12.c: Un-XFAILed.
* gcc.dg/graphite/interchange-14.c: Un-XFAILed.
* gcc.dg/graphite/interchange-15.c: Un-XFAILed.
* gcc.dg/graphite/interchange-8.c: Un-XFAILed.
* gcc.dg/graphite/interchange-mvt.c: Un-XFAILed.
---
gcc/ChangeLog.graphite | 18 +++++++++
gcc/graphite-sese-to-poly.c | 43 ++++++++++++++++++-----
gcc/testsuite/gcc.dg/graphite/block-0.c | 4 +-
gcc/testsuite/gcc.dg/graphite/block-1.c | 5 ++-
gcc/testsuite/gcc.dg/graphite/block-7.c | 2 +-
gcc/testsuite/gcc.dg/graphite/block-8.c | 2 +-
gcc/testsuite/gcc.dg/graphite/interchange-12.c | 5 +--
gcc/testsuite/gcc.dg/graphite/interchange-14.c | 5 +--
gcc/testsuite/gcc.dg/graphite/interchange-15.c | 2 +-
gcc/testsuite/gcc.dg/graphite/interchange-8.c | 5 ++-
gcc/testsuite/gcc.dg/graphite/interchange-mvt.c | 2 +-
11 files changed, 69 insertions(+), 24 deletions(-)
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 8328af3..b0f609d 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,23 @@
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+ * graphite-sese-to-poly.c
+ (translate_scalar_reduction_to_array_for_stmt): Call unshare_expr.
+ (close_phi_written_to_memory): New.
+ (translate_scalar_reduction_to_array): Call close_phi_written_to_memory
+ and unshare_expr.
+
+ * gcc.dg/graphite/block-0.c: Un-XFAILed.
+ * gcc.dg/graphite/block-1.c: Un-XFAILed.
+ * gcc.dg/graphite/block-7.c: Un-XFAILed.
+ * gcc.dg/graphite/block-8.c: Un-XFAILed.
+ * gcc.dg/graphite/interchange-12.c: Un-XFAILed.
+ * gcc.dg/graphite/interchange-14.c: Un-XFAILed.
+ * gcc.dg/graphite/interchange-15.c: Un-XFAILed.
+ * gcc.dg/graphite/interchange-8.c: Un-XFAILed.
+ * gcc.dg/graphite/interchange-mvt.c: Un-XFAILed.
+
+2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+
* doc/install.texi: Update the expected version number of PPL to 0.11.
* graphite-ppl.c (ppl_powerset_is_empty): Remove now dead code under
#if PPL_VERSION_MINOR < 11.
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index ae01490..88eee71 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -2903,12 +2903,12 @@ translate_scalar_reduction_to_array_for_stmt (scop_p scop, tree red,
gimple stmt, gimple loop_phi)
{
tree res = gimple_phi_result (loop_phi);
- gimple assign = gimple_build_assign (res, red);
+ gimple assign = gimple_build_assign (res, unshare_expr (red));
gimple_stmt_iterator gsi;
insert_stmts (scop, assign, NULL, gsi_after_labels (gimple_bb (loop_phi)));
- assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
+ assign = gimple_build_assign (unshare_expr (red), gimple_assign_lhs (stmt));
gsi = gsi_for_stmt (stmt);
gsi_next (&gsi);
insert_stmts (scop, assign, NULL, gsi);
@@ -2949,6 +2949,29 @@ remove_phi (gimple phi)
remove_phi_node (&gsi, false);
}
+/* When the result of a CLOSE_PHI is written to a memory location,
+ return a pointer to that memory reference, otherwise return
+ NULL_TREE. */
+
+static tree
+close_phi_written_to_memory (gimple close_phi)
+{
+ imm_use_iterator imm_iter;
+ tree res, def = gimple_phi_result (close_phi);
+ use_operand_p use_p;
+ gimple stmt;
+
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
+ if ((stmt = USE_STMT (use_p))
+ && gimple_code (stmt) == GIMPLE_ASSIGN
+ && (res = gimple_assign_lhs (stmt))
+ && (TREE_CODE (res) == ARRAY_REF
+ || TREE_CODE (res) == MEM_REF))
+ return res;
+
+ return NULL_TREE;
+}
+
/* Rewrite out of SSA the reduction described by the loop phi nodes
IN, and the close phi nodes OUT. IN and OUT are structured by loop
levels like this:
@@ -2964,9 +2987,9 @@ translate_scalar_reduction_to_array (scop_p scop,
VEC (gimple, heap) *in,
VEC (gimple, heap) *out)
{
- unsigned int i;
gimple loop_phi;
- tree red = NULL_TREE;
+ unsigned int i = VEC_length (gimple, out) - 1;
+ tree red = close_phi_written_to_memory (VEC_index (gimple, out, i));
FOR_EACH_VEC_ELT (gimple, in, i, loop_phi)
{
@@ -2980,8 +3003,10 @@ translate_scalar_reduction_to_array (scop_p scop,
PBB_IS_REDUCTION (pbb) = true;
gcc_assert (close_phi == loop_phi);
- red = create_zero_dim_array
- (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction");
+ if (!red)
+ red = create_zero_dim_array
+ (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction");
+
translate_scalar_reduction_to_array_for_stmt
(scop, red, stmt, VEC_index (gimple, in, 1));
continue;
@@ -2989,11 +3014,11 @@ translate_scalar_reduction_to_array (scop_p scop,
if (i == VEC_length (gimple, in) - 1)
{
- insert_out_of_ssa_copy (scop, gimple_phi_result (close_phi), red,
- close_phi);
+ insert_out_of_ssa_copy (scop, gimple_phi_result (close_phi),
+ unshare_expr (red), close_phi);
insert_out_of_ssa_copy_on_edge
(scop, edge_initial_value_for_loop_phi (loop_phi),
- red, initial_value_for_loop_phi (loop_phi));
+ unshare_expr (red), initial_value_for_loop_phi (loop_phi));
}
remove_phi (loop_phi);
diff --git a/gcc/testsuite/gcc.dg/graphite/block-0.c b/gcc/testsuite/gcc.dg/graphite/block-0.c
index d772743..9bf9712 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-0.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-0.c
@@ -12,7 +12,7 @@ foo (void)
int j;
int i;
- /* This should be blocked. */
+ /* This is not blocked as it is not profitable. */
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
a[j] = a[i] + 1;
@@ -42,5 +42,5 @@ main (void)
return 0;
}
-/* { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-not "will be loop blocked" "graphite" } } */
/* { dg-final { cleanup-tree-dump "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/block-1.c b/gcc/testsuite/gcc.dg/graphite/block-1.c
index 876d6f0..d335345 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-1.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-1.c
@@ -17,6 +17,7 @@ main (void)
int A[MAX * MAX];
int B[MAX * MAX];
+ /* These loops should be loop blocked. */
for (i = 0; i < MAX; i++)
for (j = 0; j < MAX; j++)
{
@@ -24,10 +25,12 @@ main (void)
B[i*MAX + j] = j;
}
+ /* These loops should be loop blocked. */
for (i = 0; i < MAX; i++)
for (j = 0; j < MAX; j++)
A[i*MAX + j] += B[j*MAX + i];
+ /* These loops should be loop blocked. */
for(i = 0; i < MAX; i++)
for(j = 0; j < MAX; j++)
sum += A[i*MAX + j];
@@ -42,5 +45,5 @@ main (void)
return 0;
}
-/* { dg-final { scan-tree-dump-times "will be loop blocked" 2 "graphite" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "will be loop blocked" 3 "graphite" } } */
/* { dg-final { cleanup-tree-dump "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/block-7.c b/gcc/testsuite/gcc.dg/graphite/block-7.c
index 6f33651..fbbe1f3 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-7.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-7.c
@@ -53,5 +53,5 @@ main (void)
return 0;
}
-/* { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" } } */
/* { dg-final { cleanup-tree-dump "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/block-8.c b/gcc/testsuite/gcc.dg/graphite/block-8.c
index 4e7e5b5..9c1c9ce 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-8.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-8.c
@@ -54,5 +54,5 @@ main (void)
return 0;
}
-/* { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" } } */
/* { dg-final { cleanup-tree-dump "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-12.c b/gcc/testsuite/gcc.dg/graphite/interchange-12.c
index f569b78..fc27b4c 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-12.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-12.c
@@ -14,8 +14,7 @@ matmult (void)
{
int i, j, k;
- /* This should be interchanged twice: (i, k) and (j, i). The
- resulting nest should look like this (k, i, j). */
+ /* Loops J and K should be interchanged. */
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
{
@@ -54,5 +53,5 @@ main (void)
return 0;
}
-/* { dg-final { scan-tree-dump-times "will be interchanged" 2 "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-14.c b/gcc/testsuite/gcc.dg/graphite/interchange-14.c
index 00b7f82..53809b5 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-14.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-14.c
@@ -18,8 +18,7 @@ matmult (void)
for (j = 0; j < N; j++)
A[i][j] = 0;
- /* This should be interchanged twice: (i, k) and (j, i). The
- resulting nest should look like this (k, i, j). */
+ /* Loops J and K should be interchanged. */
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
for (k = 0; k < N; k++)
@@ -55,5 +54,5 @@ main (void)
return 0;
}
-/* { dg-final { scan-tree-dump-times "will be interchanged" 2 "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 bfb8a73..9eeef66 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-15.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-15.c
@@ -48,6 +48,6 @@ main (void)
return 0;
}
-/* { 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 e084bd8..ca99dbc 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-8.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-8.c
@@ -11,7 +11,8 @@ foo (void)
{
int i, j, k, l;
- /* Loops K and L should be interchanged. */
+ /* Loops (L, J) are interchanged, and then loops (J and K) are
+ interchanged. The result is a nest starting with (K, J, L). */
for (l = 0; l < 4; l++)
{
for (k = 0; k < 4; k++)
@@ -81,5 +82,5 @@ main (void)
return 0;
}
-/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "will be interchanged" 2 "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 61e73c1..ee262e9 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c
@@ -58,6 +58,6 @@ main (void)
return 0;
}
-/* { 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" } } */
--
1.7.1
^ permalink raw reply [flat|nested] 21+ messages in thread* [PATCH 03/10] Test the profitability of interchange on the perfect nest.
2011-01-15 9:09 [PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear Sebastian Pop
` (7 preceding siblings ...)
2011-01-15 9:28 ` [PATCH 10/10] Remove the temporary array for reductions written to memory Sebastian Pop
@ 2011-01-15 10:09 ` Sebastian Pop
2011-01-15 10:54 ` [PATCH 07/10] Use PIP to determine the integer feasibility of a constraint system Sebastian Pop
2011-01-17 6:31 ` [PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear Jack Howarth
10 siblings, 0 replies; 21+ messages in thread
From: Sebastian Pop @ 2011-01-15 10:09 UTC (permalink / raw)
To: gcc-patches; +Cc: rguenther, gcc-graphite, Sebastian Pop
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
* graphite-interchange.c (lst_interchange_profitable_p): Takes a loop
nest and two loop depths as parameters.
(lst_try_interchange_loops): Call lst_interchange_profitable_p after
lst_perfect_nestify.
---
gcc/ChangeLog.graphite | 7 +++++++
gcc/graphite-interchange.c | 16 +++++++---------
2 files changed, 14 insertions(+), 9 deletions(-)
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index d3bb503..4324a6e 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,12 @@
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+ * graphite-interchange.c (lst_interchange_profitable_p): Takes a loop
+ nest and two loop depths as parameters.
+ (lst_try_interchange_loops): Call lst_interchange_profitable_p after
+ lst_perfect_nestify.
+
+2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+
* graphite-dependences.c (print_pddr): Call
ppl_io_fprint_Pointset_Powerset_C_Polyhedron.
diff --git a/gcc/graphite-interchange.c b/gcc/graphite-interchange.c
index b90c4e7..934839a 100644
--- a/gcc/graphite-interchange.c
+++ b/gcc/graphite-interchange.c
@@ -446,20 +446,18 @@ memory_strides_in_loop (lst_p loop, graphite_dim_t depth, mpz_t strides)
profitable to interchange the loops at DEPTH1 and DEPTH2. */
static bool
-lst_interchange_profitable_p (lst_p loop1, lst_p loop2)
+lst_interchange_profitable_p (lst_p nest, int depth1, int depth2)
{
mpz_t d1, d2;
bool res;
- gcc_assert (loop1 && loop2
- && LST_LOOP_P (loop1) && LST_LOOP_P (loop2)
- && lst_depth (loop1) < lst_depth (loop2));
+ gcc_assert (depth1 < depth2);
mpz_init (d1);
mpz_init (d2);
- memory_strides_in_loop (loop1, lst_depth (loop1), d1);
- memory_strides_in_loop (loop2, lst_depth (loop2), d2);
+ memory_strides_in_loop (nest, depth1, d1);
+ memory_strides_in_loop (nest, depth2, d2);
res = mpz_cmp (d1, d2) < 0;
@@ -592,12 +590,12 @@ lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2)
lst_p before = NULL, nest = NULL, after = NULL;
- if (!lst_interchange_profitable_p (loop1, loop2))
- return false;
-
if (!lst_perfectly_nested_p (loop1, loop2))
lst_perfect_nestify (loop1, loop2, &before, &nest, &after);
+ if (!lst_interchange_profitable_p (loop2, depth1, depth2))
+ return false;
+
lst_apply_interchange (loop2, depth1, depth2);
/* Sync the transformed LST information and the PBB scatterings
--
1.7.1
^ permalink raw reply [flat|nested] 21+ messages in thread* [PATCH 07/10] Use PIP to determine the integer feasibility of a constraint system.
2011-01-15 9:09 [PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear Sebastian Pop
` (8 preceding siblings ...)
2011-01-15 10:09 ` [PATCH 03/10] Test the profitability of interchange on the perfect nest Sebastian Pop
@ 2011-01-15 10:54 ` Sebastian Pop
2011-01-15 18:54 ` Sven Verdoolaege
2011-01-17 6:31 ` [PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear Jack Howarth
10 siblings, 1 reply; 21+ messages in thread
From: Sebastian Pop @ 2011-01-15 10:54 UTC (permalink / raw)
To: gcc-patches; +Cc: rguenther, gcc-graphite, Sebastian Pop
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
* graphite-dependences.c (new_poly_dr): Call ppl_powerset_is_empty.
(build_lexicographical_constraint): Same.
(dependence_polyhedron_1): Same.
(graphite_legal_transform_dr): Same.
(graphite_carried_dependence_level_k): Same.
* graphite-ppl.c (ppl_powerset_is_empty): New.
* graphite-ppl.h (ppl_powerset_is_empty): Declared.
* tree-data-ref.c (dump_data_reference): Print the basic block index.
* gcc.dg/graphite/block-0.c: Add documentation.
* gcc.dg/graphite/block-4.c: Same.
* gcc.dg/graphite/block-7.c: Same.
* gcc.dg/graphite/block-8.c: New.
* gcc.dg/graphite/interchange-1.c: Un-XFAILed.
* gcc.dg/graphite/interchange-11.c: Un-XFAILed.
* gcc.dg/graphite/interchange-12.c: Add documentation.
* gcc.dg/graphite/interchange-13.c: New.
* gcc.dg/graphite/interchange-14.c: New.
* gcc.dg/graphite/interchange-15.c: New.
* gcc.dg/graphite/interchange-8.c: Add documentation.
* gcc.dg/graphite/interchange-mvt.c: Same.
---
gcc/ChangeLog.graphite | 24 ++++++++
gcc/graphite-dependences.c | 23 ++++---
gcc/graphite-ppl.c | 73 +++++++++++++++++++++++
gcc/graphite-ppl.h | 2 +
gcc/testsuite/gcc.dg/graphite/block-0.c | 1 +
gcc/testsuite/gcc.dg/graphite/block-4.c | 2 +
gcc/testsuite/gcc.dg/graphite/block-7.c | 1 +
gcc/testsuite/gcc.dg/graphite/block-8.c | 58 ++++++++++++++++++
gcc/testsuite/gcc.dg/graphite/interchange-1.c | 4 +-
gcc/testsuite/gcc.dg/graphite/interchange-11.c | 3 +-
gcc/testsuite/gcc.dg/graphite/interchange-12.c | 4 +-
gcc/testsuite/gcc.dg/graphite/interchange-13.c | 54 +++++++++++++++++
gcc/testsuite/gcc.dg/graphite/interchange-14.c | 59 ++++++++++++++++++
gcc/testsuite/gcc.dg/graphite/interchange-15.c | 53 ++++++++++++++++
gcc/testsuite/gcc.dg/graphite/interchange-8.c | 2 +-
gcc/testsuite/gcc.dg/graphite/interchange-mvt.c | 1 +
gcc/tree-data-ref.c | 4 +-
17 files changed, 353 insertions(+), 15 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/graphite/block-8.c
create mode 100644 gcc/testsuite/gcc.dg/graphite/interchange-13.c
create mode 100644 gcc/testsuite/gcc.dg/graphite/interchange-14.c
create mode 100644 gcc/testsuite/gcc.dg/graphite/interchange-15.c
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 86ba9c9..b844d04 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,29 @@
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+ * graphite-dependences.c (new_poly_dr): Call ppl_powerset_is_empty.
+ (build_lexicographical_constraint): Same.
+ (dependence_polyhedron_1): Same.
+ (graphite_legal_transform_dr): Same.
+ (graphite_carried_dependence_level_k): Same.
+ * graphite-ppl.c (ppl_powerset_is_empty): New.
+ * graphite-ppl.h (ppl_powerset_is_empty): Declared.
+ * tree-data-ref.c (dump_data_reference): Print the basic block index.
+
+ * gcc.dg/graphite/block-0.c: Add documentation.
+ * gcc.dg/graphite/block-4.c: Same.
+ * gcc.dg/graphite/block-7.c: Same.
+ * gcc.dg/graphite/block-8.c: New.
+ * gcc.dg/graphite/interchange-1.c: Un-XFAILed.
+ * gcc.dg/graphite/interchange-11.c: Un-XFAILed.
+ * gcc.dg/graphite/interchange-12.c: Add documentation.
+ * gcc.dg/graphite/interchange-13.c: New.
+ * gcc.dg/graphite/interchange-14.c: New.
+ * gcc.dg/graphite/interchange-15.c: New.
+ * gcc.dg/graphite/interchange-8.c: Add documentation.
+ * gcc.dg/graphite/interchange-mvt.c: Same.
+
+2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+
* graphite-dependences.c (build_pairwise_scheduling): Correctly compute
the "a followed by b" relation and document it.
diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
index 5e4e087..b7f9442 100644
--- a/gcc/graphite-dependences.c
+++ b/gcc/graphite-dependences.c
@@ -54,7 +54,9 @@ new_poly_ddr (poly_dr_p source, poly_dr_p sink,
PDDR_DDP (pddr) = ddp;
PDDR_ORIGINAL_SCATTERING_P (pddr) = original_scattering_p;
- if (!ddp || ppl_Pointset_Powerset_C_Polyhedron_is_empty (ddp))
+ if (!ddp
+ || ppl_powerset_is_empty (ddp,
+ scop_nb_params (PBB_SCOP (PDR_PBB (source)))))
PDDR_KIND (pddr) = no_dependence;
else
PDDR_KIND (pddr) = has_dependence;
@@ -395,13 +397,14 @@ build_pairwise_scheduling (graphite_dim_t dim,
the BAG polyhedron: T1|I1|T2|I2|S1|S2|G. When DIRECTION is set to
1, compute the direct dependence from PDR1 to PDR2, and when
DIRECTION is -1, compute the reversed dependence relation, from
- PDR2 to PDR1. */
+ PDR2 to PDR1. GDIM is the number of parameters in the scop. */
static ppl_Pointset_Powerset_C_Polyhedron_t
build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
graphite_dim_t dim,
graphite_dim_t tdim,
graphite_dim_t offset,
+ graphite_dim_t gdim,
int direction)
{
graphite_dim_t i;
@@ -412,7 +415,7 @@ build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
lex = build_pairwise_scheduling (dim, 0, offset, direction);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
- if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex))
+ if (!ppl_powerset_is_empty (lex, gdim))
ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
@@ -425,13 +428,13 @@ build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag, sceq);
ppl_delete_Pointset_Powerset_C_Polyhedron (sceq);
- if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (bag))
+ if (ppl_powerset_is_empty (bag, gdim))
break;
lex = build_pairwise_scheduling (dim, i + 1, offset, direction);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
- if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex))
+ if (!ppl_powerset_is_empty (lex, gdim))
ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
@@ -510,11 +513,11 @@ dependence_polyhedron_1 (poly_dr_p pdr1, poly_dr_p pdr2,
ppl_delete_Pointset_Powerset_C_Polyhedron (idr2);
ppl_delete_Pointset_Powerset_C_Polyhedron (dreq);
- if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res))
+ if (!ppl_powerset_is_empty (res, gdim))
{
ppl_Pointset_Powerset_C_Polyhedron_t lex =
build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2),
- tdim1 + ddim1, direction);
+ tdim1 + ddim1, gdim, direction);
ppl_delete_Pointset_Powerset_C_Polyhedron (res);
res = lex;
}
@@ -683,7 +686,8 @@ graphite_legal_transform_dr (poly_dr_p pdr1, poly_dr_p pdr2)
ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, pt);
- is_empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (po_temp);
+ is_empty_p = ppl_powerset_is_empty (po_temp,
+ scop_nb_params (PBB_SCOP (pbb1)));
ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp);
free_poly_ddr (tpddr);
@@ -911,7 +915,8 @@ graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
eqpp = build_pairwise_scheduling (dim, level, tdim1 + ddim1, 1);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po);
- empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp);
+ empty_p = ppl_powerset_is_empty
+ (eqpp, scop_nb_params (PBB_SCOP (PDR_PBB (pdr1))));
ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
free_poly_ddr (pddr);
diff --git a/gcc/graphite-ppl.c b/gcc/graphite-ppl.c
index 3013b33..d879d78 100644
--- a/gcc/graphite-ppl.c
+++ b/gcc/graphite-ppl.c
@@ -515,4 +515,77 @@ debug_gmp_value (mpz_t val)
(*gmp_free) (str, strlen (str) + 1);
}
+/* Checks for integer feasibility: returns true when the powerset
+ polyhedron PS has no integer solutions. NB_PARAMS is the number of
+ dimensions used as parameters in PS. If DIM is the dimension of
+ PS, the parameter dimensions are in between DIM - NB_PARAMS and
+ DIM. */
+
+bool
+ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps,
+ int nb_params ATTRIBUTE_UNUSED)
+{
+#if PPL_VERSION_MAJOR == 0 && PPL_VERSION_MINOR < 11
+ /* On PPL 0.10,
+ ppl_Pointset_Powerset_C_Polyhedron_contains_integer_point (ps)
+ takes too long on some cases and so we call _is_empty instead. */
+ return ppl_Pointset_Powerset_C_Polyhedron_is_empty (ps);
+
+#else
+ /* On PPL 0.11 or later, we can check for integer feasibility using
+ the PIP solver. */
+ ppl_PIP_Problem_t pip;
+ ppl_dimension_type d;
+ ppl_const_Constraint_System_t pcs;
+ ppl_Constraint_System_const_iterator_t first, last;
+ ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
+ int i;
+ bool has_integer_solutions = false;
+ ppl_dimension_type *ds;
+ int dim_first_parameter;
+
+ if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (ps))
+ return true;
+
+ ppl_Pointset_Powerset_C_Polyhedron_space_dimension (ps, &d);
+ dim_first_parameter = d - nb_params;
+ ds = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, nb_params);
+
+ for (i = 0; i < nb_params; i++)
+ ds[i] = dim_first_parameter + i;
+
+ ppl_new_Constraint_System_const_iterator (&first);
+ ppl_new_Constraint_System_const_iterator (&last);
+ ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
+ ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
+
+ for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it),
+ ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end);
+ !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
+ ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
+ {
+ ppl_const_Polyhedron_t ph;
+ ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
+
+ ppl_Polyhedron_get_constraints (ph, &pcs);
+ ppl_Constraint_System_begin (pcs, first);
+ ppl_Constraint_System_end (pcs, last);
+
+ ppl_new_PIP_Problem_from_constraints (&pip, d, first, last, nb_params, ds);
+ has_integer_solutions |= ppl_PIP_Problem_is_satisfiable (pip);
+
+ ppl_delete_PIP_Problem (pip);
+ }
+
+ ppl_delete_Constraint_System_const_iterator (first);
+ ppl_delete_Constraint_System_const_iterator (last);
+ ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
+ ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
+ if (ds)
+ free (ds);
+
+ return !has_integer_solutions;
+#endif
+}
+
#endif
diff --git a/gcc/graphite-ppl.h b/gcc/graphite-ppl.h
index f6c279b..f6c3ad3 100644
--- a/gcc/graphite-ppl.h
+++ b/gcc/graphite-ppl.h
@@ -47,6 +47,8 @@ void ppl_min_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t,
ppl_Constraint_t ppl_build_relation (int, int, int, int,
enum ppl_enum_Constraint_Type);
void debug_gmp_value (mpz_t);
+bool ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t, int);
+
/* Assigns to RES the value of the INTEGER_CST T. */
diff --git a/gcc/testsuite/gcc.dg/graphite/block-0.c b/gcc/testsuite/gcc.dg/graphite/block-0.c
index af02363..d772743 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-0.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-0.c
@@ -12,6 +12,7 @@ foo (void)
int j;
int i;
+ /* This should be blocked. */
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
a[j] = a[i] + 1;
diff --git a/gcc/testsuite/gcc.dg/graphite/block-4.c b/gcc/testsuite/gcc.dg/graphite/block-4.c
index ac22ec3..eb98f04 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-4.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-4.c
@@ -15,11 +15,13 @@ foo (void)
{
int i, j, k;
+ /* This should NOT be blocked: each loop iterates only 24 times. */
for (i = 0; i < 24; i++)
for (j = 0; j < 24; j++)
for (k = 0; k < 24; k++)
A[i][j] = B[i][k] * C[k][j];
+ /* This should be blocked. */
for (i = 0; i < M; i++)
for (j = 0; j < M; j++)
for (k = 0; k < M; k++)
diff --git a/gcc/testsuite/gcc.dg/graphite/block-7.c b/gcc/testsuite/gcc.dg/graphite/block-7.c
index 07c626c..6f33651 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-7.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-7.c
@@ -14,6 +14,7 @@ matmult (void)
{
int i, j, k;
+ /* This should be blocked. */
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
{
diff --git a/gcc/testsuite/gcc.dg/graphite/block-8.c b/gcc/testsuite/gcc.dg/graphite/block-8.c
new file mode 100644
index 0000000..4e7e5b5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/block-8.c
@@ -0,0 +1,58 @@
+/* { dg-require-effective-target size32plus } */
+
+#define DEBUG 0
+#if DEBUG
+#include <stdio.h>
+#endif
+
+#define N 200
+
+int A[N][N], B[N][N], C[N][N];
+
+static void __attribute__((noinline))
+matmult (void)
+{
+ int i, j, k;
+
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ A[i][j] = 0;
+
+ /* This should be blocked. */
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ for (k = 0; k < N; k++)
+ A[i][j] += B[i][k] * C[k][j];
+}
+
+extern void abort ();
+
+int
+main (void)
+{
+ int i, j, res = 0;
+
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ {
+ B[i][j] = j;
+ C[i][j] = i;
+ }
+
+ matmult ();
+
+ for (i = 0; i < N; i++)
+ res += A[i][i];
+
+#if DEBUG
+ fprintf (stderr, "res = %d \n", res);
+#endif
+
+ if (res != 529340000)
+ abort ();
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" { xfail *-*-* } } } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-1.c b/gcc/testsuite/gcc.dg/graphite/interchange-1.c
index 787124f..b4559d1 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-1.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-1.c
@@ -15,6 +15,7 @@ foo (int N)
int i, j;
double sum = 0.0;
+ /* These two loops should be interchanged. */
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
@@ -48,6 +49,5 @@ main (void)
return 0;
}
-
-/* { 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-11.c b/gcc/testsuite/gcc.dg/graphite/interchange-11.c
index 95b60b8..491fda1 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-11.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-11.c
@@ -13,6 +13,7 @@ foo (int N, int *res)
int i, j;
double sum = 0.0;
+ /* These two loops should be interchanged. */
for (i = 0; i < 1335; i++)
{
for (j = 0; j < 1335; j++)
@@ -45,5 +46,5 @@ main (void)
return 0;
}
-/* { 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-12.c b/gcc/testsuite/gcc.dg/graphite/interchange-12.c
index 16c0ddb..f569b78 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-12.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-12.c
@@ -14,6 +14,8 @@ matmult (void)
{
int i, j, k;
+ /* This should be interchanged twice: (i, k) and (j, i). The
+ resulting nest should look like this (k, i, j). */
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
{
@@ -52,5 +54,5 @@ main (void)
return 0;
}
-/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "will be interchanged" 2 "graphite" { xfail *-*-* } } } */
/* { dg-final { cleanup-tree-dump "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-13.c b/gcc/testsuite/gcc.dg/graphite/interchange-13.c
new file mode 100644
index 0000000..a8bf23b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-13.c
@@ -0,0 +1,54 @@
+/* { dg-require-effective-target size32plus } */
+
+/* Formerly known as ltrans-1.c */
+
+#define DEBUG 0
+#if DEBUG
+#include <stdio.h>
+#endif
+
+double u[25];
+
+static int __attribute__((noinline))
+foo (int N)
+{
+ int i, j;
+ double sum = 0.0;
+
+ /* These two loops should be interchanged. */
+ for (i = 0; i < N; i++)
+ {
+ for (j = 0; j < N; j++)
+ sum = sum + u[i + 5 * j];
+
+ u[6 * i] *= 2;
+ }
+
+ return sum + N + u[6];
+}
+
+extern void abort ();
+
+int
+main (void)
+{
+ int i, j, res;
+
+ for (i = 0; i < 25; i++)
+ u[i] = 2;
+
+ res = foo (5);
+
+#if DEBUG
+ fprintf (stderr, "res = %d \n", res);
+#endif
+
+ if (res != 59)
+ abort ();
+
+ return 0;
+}
+
+
+/* { 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-14.c b/gcc/testsuite/gcc.dg/graphite/interchange-14.c
new file mode 100644
index 0000000..00b7f82
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-14.c
@@ -0,0 +1,59 @@
+/* { dg-require-effective-target size32plus } */
+
+#define DEBUG 0
+#if DEBUG
+#include <stdio.h>
+#endif
+
+#define N 200
+
+int A[N][N], B[N][N], C[N][N];
+
+static void __attribute__((noinline))
+matmult (void)
+{
+ int i, j, k;
+
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ A[i][j] = 0;
+
+ /* This should be interchanged twice: (i, k) and (j, i). The
+ resulting nest should look like this (k, i, j). */
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ for (k = 0; k < N; k++)
+ A[i][j] += B[i][k] * C[k][j];
+}
+
+extern void abort ();
+
+int
+main (void)
+{
+ int i, j, res = 0;
+
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ {
+ B[i][j] = j;
+ C[i][j] = i;
+ }
+
+ matmult ();
+
+ for (i = 0; i < N; i++)
+ res += A[i][i];
+
+#if DEBUG
+ fprintf (stderr, "res = %d \n", res);
+#endif
+
+ if (res != 529340000)
+ abort ();
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "will be interchanged" 2 "graphite" { xfail *-*-* } } } */
+/* { 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
new file mode 100644
index 0000000..bfb8a73
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-15.c
@@ -0,0 +1,53 @@
+/* { dg-require-effective-target size32plus } */
+
+#define DEBUG 0
+#if DEBUG
+#include <stdio.h>
+#endif
+
+#define NMAX 2000
+
+static int x[NMAX], a[NMAX][NMAX];
+
+static int __attribute__((noinline))
+mvt (long N)
+{
+ int i,j;
+
+ /* These two loops should be interchanged. */
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ x[i] += a[j][i];
+
+ return x[1];
+}
+
+extern void abort ();
+
+int
+main (void)
+{
+ int i, j, res;
+
+ for (i = 0; i < NMAX; i++)
+ for (j = 0; j < NMAX; j++)
+ a[i][j] = j;
+
+ for (i = 0; i < NMAX; i++)
+ x[i] = i;
+
+ res = mvt (NMAX);
+
+#if DEBUG
+ fprintf (stderr, "res = %d \n", res);
+#endif
+
+ if (res != 2001)
+ abort ();
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */
+/* { 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 8c07b6f..e084bd8 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-8.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-8.c
@@ -11,6 +11,7 @@ foo (void)
{
int i, j, k, l;
+ /* Loops K and L should be interchanged. */
for (l = 0; l < 4; l++)
{
for (k = 0; k < 4; k++)
@@ -80,6 +81,5 @@ main (void)
return 0;
}
-/* Loops K and L should be interchanged. */
/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */
/* { 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 62a9c46..61e73c1 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c
@@ -19,6 +19,7 @@ mvt (long N)
for (j = 0; j < N; j++)
x1[i] = x1[i] + a[i][j] * y1[j];
+ /* These two loops should be interchanged. */
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
x2[i] = x2[i] + a[j][i] * y2[j];
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 3de3234..ccc0091 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -193,7 +193,9 @@ dump_data_reference (FILE *outf,
{
unsigned int i;
- fprintf (outf, "#(Data Ref: \n# stmt: ");
+ fprintf (outf, "#(Data Ref: \n");
+ fprintf (outf, "# bb: %d \n", gimple_bb (DR_STMT (dr))->index);
+ fprintf (outf, "# stmt: ");
print_gimple_stmt (outf, DR_STMT (dr), 0, 0);
fprintf (outf, "# ref: ");
print_generic_stmt (outf, DR_REF (dr), 0);
--
1.7.1
^ permalink raw reply [flat|nested] 21+ messages in thread* Re: [PATCH 07/10] Use PIP to determine the integer feasibility of a constraint system.
2011-01-15 10:54 ` [PATCH 07/10] Use PIP to determine the integer feasibility of a constraint system Sebastian Pop
@ 2011-01-15 18:54 ` Sven Verdoolaege
2011-01-15 22:08 ` Sebastian Pop
0 siblings, 1 reply; 21+ messages in thread
From: Sven Verdoolaege @ 2011-01-15 18:54 UTC (permalink / raw)
To: Sebastian Pop; +Cc: gcc-patches, rguenther, gcc-graphite
On Sat, Jan 15, 2011 at 03:05:12AM -0600, Sebastian Pop wrote:
> +bool
> +ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps,
> + int nb_params ATTRIBUTE_UNUSED)
Why would you have to know the number of parameters to check
whether a set is empty? That makes no sense.
skimo
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH 07/10] Use PIP to determine the integer feasibility of a constraint system.
2011-01-15 18:54 ` Sven Verdoolaege
@ 2011-01-15 22:08 ` Sebastian Pop
2011-01-15 22:27 ` Sven Verdoolaege
0 siblings, 1 reply; 21+ messages in thread
From: Sebastian Pop @ 2011-01-15 22:08 UTC (permalink / raw)
To: Sven Verdoolaege; +Cc: gcc-patches, rguenther, gcc-graphite
On Sat, Jan 15, 2011 at 11:10, Sven Verdoolaege <skimo@kotnet.org> wrote:
> On Sat, Jan 15, 2011 at 03:05:12AM -0600, Sebastian Pop wrote:
>> +bool
>> +ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps,
>> + int nb_params ATTRIBUTE_UNUSED)
>
> Why would you have to know the number of parameters to check
> whether a set is empty? That makes no sense.
To create a PIP problem, PPL asks for the dimensions containing parameters.
http://www.cs.unipr.it/ppl/Documentation/user/ppl-user-c-interface-0.11-html/interfaceppl__PIP__Problem__tag.html#a51082042eaafc2db84f50f28d3d5b646
In all the constraint systems, the parameters are the last nb_params dimensions.
Sebastian
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH 07/10] Use PIP to determine the integer feasibility of a constraint system.
2011-01-15 22:08 ` Sebastian Pop
@ 2011-01-15 22:27 ` Sven Verdoolaege
2011-01-17 10:43 ` [PATCH] Pass 0 as the number of parameters to PIP when testing for integer feasibility Sebastian Pop
0 siblings, 1 reply; 21+ messages in thread
From: Sven Verdoolaege @ 2011-01-15 22:27 UTC (permalink / raw)
To: Sebastian Pop; +Cc: gcc-patches, rguenther, gcc-graphite
On Sat, Jan 15, 2011 at 12:53:23PM -0600, Sebastian Pop wrote:
> On Sat, Jan 15, 2011 at 11:10, Sven Verdoolaege <skimo@kotnet.org> wrote:
> > On Sat, Jan 15, 2011 at 03:05:12AM -0600, Sebastian Pop wrote:
> >> +bool
> >> +ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps,
> >> + Â Â Â Â Â Â Â Â Â Â int nb_params ATTRIBUTE_UNUSED)
> >
> > Why would you have to know the number of parameters to check
> > whether a set is empty? Â That makes no sense.
>
> To create a PIP problem, PPL asks for the dimensions containing parameters.
So? Just tell it that there are no parameters (or that all dimensions
are parameters). For checking whether a set is empty, it does not matter
whether a dimension represents a parameter or not.
skimo
^ permalink raw reply [flat|nested] 21+ messages in thread
* [PATCH] Pass 0 as the number of parameters to PIP when testing for integer feasibility.
2011-01-15 22:27 ` Sven Verdoolaege
@ 2011-01-17 10:43 ` Sebastian Pop
0 siblings, 0 replies; 21+ messages in thread
From: Sebastian Pop @ 2011-01-17 10:43 UTC (permalink / raw)
To: gcc-patches; +Cc: rguenther, gcc-graphite, skimo, Sebastian Pop
2011-01-17 Sebastian Pop <sebastian.pop@amd.com>
* graphite-dependences.c (build_lexicographical_constraint): Remove the
gdim parameter.
(build_lexicographical_constraint): Adjust call to ppl_powerset_is_empty.
(dependence_polyhedron): Same.
(graphite_legal_transform_dr): Same.
(graphite_carried_dependence_level_k): Same.
* graphite-ppl.c (ppl_powerset_is_empty): Remove the nb_params parameter.
* graphite-ppl.h (ppl_powerset_is_empty): Adjust declaration.
---
gcc/ChangeLog.graphite | 11 +++++++++++
gcc/graphite-dependences.c | 19 ++++++++-----------
gcc/graphite-ppl.c | 21 +++------------------
gcc/graphite-ppl.h | 2 +-
4 files changed, 23 insertions(+), 30 deletions(-)
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index b0f609d..3912934 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,3 +1,14 @@
+2011-01-17 Sebastian Pop <sebastian.pop@amd.com>
+
+ * graphite-dependences.c (build_lexicographical_constraint): Remove the
+ gdim parameter.
+ (build_lexicographical_constraint): Adjust call to ppl_powerset_is_empty.
+ (dependence_polyhedron): Same.
+ (graphite_legal_transform_dr): Same.
+ (graphite_carried_dependence_level_k): Same.
+ * graphite-ppl.c (ppl_powerset_is_empty): Remove the nb_params parameter.
+ * graphite-ppl.h (ppl_powerset_is_empty): Adjust declaration.
+
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
* graphite-sese-to-poly.c
diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
index 144f7b0..252a987 100644
--- a/gcc/graphite-dependences.c
+++ b/gcc/graphite-dependences.c
@@ -360,14 +360,13 @@ build_pairwise_scheduling (graphite_dim_t dim,
the BAG polyhedron: T1|I1|T2|I2|S1|S2|G. When DIRECTION is set to
1, compute the direct dependence from PDR1 to PDR2, and when
DIRECTION is -1, compute the reversed dependence relation, from
- PDR2 to PDR1. GDIM is the number of parameters in the scop. */
+ PDR2 to PDR1. */
static ppl_Pointset_Powerset_C_Polyhedron_t
build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
graphite_dim_t dim,
graphite_dim_t tdim,
graphite_dim_t offset,
- graphite_dim_t gdim,
int direction)
{
graphite_dim_t i;
@@ -378,7 +377,7 @@ build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
lex = build_pairwise_scheduling (dim, 0, offset, direction);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
- if (!ppl_powerset_is_empty (lex, gdim))
+ if (!ppl_powerset_is_empty (lex))
ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
@@ -391,13 +390,13 @@ build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag, sceq);
ppl_delete_Pointset_Powerset_C_Polyhedron (sceq);
- if (ppl_powerset_is_empty (bag, gdim))
+ if (ppl_powerset_is_empty (bag))
break;
lex = build_pairwise_scheduling (dim, i + 1, offset, direction);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
- if (!ppl_powerset_is_empty (lex, gdim))
+ if (!ppl_powerset_is_empty (lex))
ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
@@ -477,11 +476,11 @@ dependence_polyhedron (poly_dr_p pdr1, poly_dr_p pdr2,
ppl_delete_Pointset_Powerset_C_Polyhedron (idr2);
ppl_delete_Pointset_Powerset_C_Polyhedron (dreq);
- if (ppl_powerset_is_empty (res, gdim))
+ if (ppl_powerset_is_empty (res))
return NULL;
lex = build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2),
- tdim1 + ddim1, gdim, direction);
+ tdim1 + ddim1, direction);
ppl_delete_Pointset_Powerset_C_Polyhedron (res);
return lex;
@@ -671,8 +670,7 @@ graphite_legal_transform_dr (poly_dr_p pdr1, poly_dr_p pdr2)
ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, pt);
- is_empty_p = ppl_powerset_is_empty (po_temp,
- scop_nb_params (PBB_SCOP (pbb1)));
+ is_empty_p = ppl_powerset_is_empty (po_temp);
ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp);
free_poly_ddr (tpddr);
@@ -900,8 +898,7 @@ graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
eqpp = build_pairwise_scheduling (dim, level, tdim1 + ddim1, 1);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po);
- empty_p = ppl_powerset_is_empty
- (eqpp, scop_nb_params (PBB_SCOP (PDR_PBB (pdr1))));
+ empty_p = ppl_powerset_is_empty (eqpp);
ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
free_poly_ddr (pddr);
diff --git a/gcc/graphite-ppl.c b/gcc/graphite-ppl.c
index 1a08362..9762ca4 100644
--- a/gcc/graphite-ppl.c
+++ b/gcc/graphite-ppl.c
@@ -516,35 +516,22 @@ debug_gmp_value (mpz_t val)
}
/* Checks for integer feasibility: returns true when the powerset
- polyhedron PS has no integer solutions. NB_PARAMS is the number of
- dimensions used as parameters in PS. If DIM is the dimension of
- PS, the parameter dimensions are in between DIM - NB_PARAMS and
- DIM. */
+ polyhedron PS has no integer solutions. */
bool
-ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps,
- int nb_params ATTRIBUTE_UNUSED)
+ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps)
{
ppl_PIP_Problem_t pip;
ppl_dimension_type d;
ppl_const_Constraint_System_t pcs;
ppl_Constraint_System_const_iterator_t first, last;
ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
- int i;
bool has_integer_solutions = false;
- ppl_dimension_type *ds;
- int dim_first_parameter;
if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (ps))
return true;
ppl_Pointset_Powerset_C_Polyhedron_space_dimension (ps, &d);
- dim_first_parameter = d - nb_params;
- ds = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, nb_params);
-
- for (i = 0; i < nb_params; i++)
- ds[i] = dim_first_parameter + i;
-
ppl_new_Constraint_System_const_iterator (&first);
ppl_new_Constraint_System_const_iterator (&last);
ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
@@ -562,7 +549,7 @@ ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps,
ppl_Constraint_System_begin (pcs, first);
ppl_Constraint_System_end (pcs, last);
- ppl_new_PIP_Problem_from_constraints (&pip, d, first, last, nb_params, ds);
+ ppl_new_PIP_Problem_from_constraints (&pip, d, first, last, 0, NULL);
has_integer_solutions |= ppl_PIP_Problem_is_satisfiable (pip);
ppl_delete_PIP_Problem (pip);
@@ -572,8 +559,6 @@ ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps,
ppl_delete_Constraint_System_const_iterator (last);
ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
- if (ds)
- free (ds);
return !has_integer_solutions;
}
diff --git a/gcc/graphite-ppl.h b/gcc/graphite-ppl.h
index f6c3ad3..695d01f 100644
--- a/gcc/graphite-ppl.h
+++ b/gcc/graphite-ppl.h
@@ -47,7 +47,7 @@ void ppl_min_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t,
ppl_Constraint_t ppl_build_relation (int, int, int, int,
enum ppl_enum_Constraint_Type);
void debug_gmp_value (mpz_t);
-bool ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t, int);
+bool ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t);
/* Assigns to RES the value of the INTEGER_CST T. */
--
1.7.1
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear
2011-01-15 9:09 [PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear Sebastian Pop
` (9 preceding siblings ...)
2011-01-15 10:54 ` [PATCH 07/10] Use PIP to determine the integer feasibility of a constraint system Sebastian Pop
@ 2011-01-17 6:31 ` Jack Howarth
10 siblings, 0 replies; 21+ messages in thread
From: Jack Howarth @ 2011-01-17 6:31 UTC (permalink / raw)
To: Sebastian Pop; +Cc: gcc-patches, rguenther, gcc-graphite
On Sat, Jan 15, 2011 at 03:05:05AM -0600, Sebastian Pop wrote:
> Hi Richi,
>
> Here is the first part of the patch to remove the lambda framework.
> These patches un-xfail most of the transforms that we wanted to see
> with -floop-interchange and that were part of the testsuite of
> -ftree-loop-linear:
>
> gcc.dg/graphite/block-0.c
> gcc.dg/graphite/block-1.c
> gcc.dg/graphite/block-4.c
> gcc.dg/graphite/block-7.c
> gcc.dg/graphite/block-8.c
> gcc.dg/graphite/interchange-1.c
> gcc.dg/graphite/interchange-11.c
> gcc.dg/graphite/interchange-12.c
> gcc.dg/graphite/interchange-13.c
> gcc.dg/graphite/interchange-14.c
> gcc.dg/graphite/interchange-15.c
> gcc.dg/graphite/interchange-8.c
> gcc.dg/graphite/interchange-mvt.c
>
> The only xfails remaining to be fixed before removing the lambda
> framework are:
> - interchange-2.c: some problem linked to the scop detection
> - interchange-3.f90: data dependence analysis does not validate the interchange.
> I will continue my investigation on these two xfails.
>
> With the patches, the Graphite testsuite has the following XFAILs:
>
> block-4.c:59:/* { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" { xfail *-*-* } } } */
> interchange-2.c:55:/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */
> pr35356-3.c:39:/* { dg-final { scan-tree-dump-times "loop_1" 0 "graphite" { xfail *-*-* } } } */
> pr37485.c:31:/* { dg-final { scan-tree-dump-times "Loop blocked" 1 "graphite" { xfail *-*-* }} } */
>
> block-1.f90:11:! { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" { xfail *-*-* } } }
> block-2.f:20:! { dg-final { scan-tree-dump-times "will be loop blocked" 2 "graphite" { xfail *-*-* } } }
> block-3.f90:15:! { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite" { xfail *-*-* } } }
> block-3.f90:16:! { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" { xfail *-*-* } } }
> block-4.f90:18:! { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite" { xfail *-*-* } } }
> block-4.f90:19:! { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" { xfail *-*-* } } }
> interchange-1.f:44:! { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } }
> interchange-3.f90:27:! { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } }
> pr14741.f90:27:! { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite" { xfail *-*-* } } }
> pr14741.f90:28:! { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" { xfail *-*-* } } }
> scop-1.f:12:! { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite" { xfail *-*-* } } }
>
> I'm committing these patches to the graphite branch for regstrap and
> SPEC testing.
Regression tests for these 10 patches on x86_64-apple-darwin10 shows no graphite regressions...
http://gcc.gnu.org/ml/gcc-testresults/2011-01/msg01391.html
>
> Sebastian Pop (10):
> Add debug_gmp_value.
> Print the data dependence polyhedron in the PPL format.
> Test the profitability of interchange on the perfect nest.
> Fix pbb_remove_duplicate_pdrs.
> speedup compilation
> Correct the precedence relation.
> Use PIP to determine the integer feasibility of a constraint system.
> Minimize the number of expensive calls to ppl_powerset_is_empty.
> Expect at least the version 0.11 of PPL.
> Remove the temporary array for reductions written to memory.
>
> ChangeLog.graphite | 5 +
> configure | 6 +-
> configure.ac | 4 +-
> gcc/ChangeLog.graphite | 96 ++++++++++
> gcc/doc/install.texi | 2 +-
> gcc/graphite-dependences.c | 226 +++++++++--------------
> gcc/graphite-interchange.c | 16 +-
> gcc/graphite-poly.c | 13 +-
> gcc/graphite-ppl.c | 76 ++++++++
> gcc/graphite-ppl.h | 3 +
> gcc/graphite-sese-to-poly.c | 43 ++++-
> gcc/testsuite/gcc.dg/graphite/block-0.c | 3 +-
> gcc/testsuite/gcc.dg/graphite/block-1.c | 5 +-
> gcc/testsuite/gcc.dg/graphite/block-4.c | 2 +
> gcc/testsuite/gcc.dg/graphite/block-7.c | 3 +-
> gcc/testsuite/gcc.dg/graphite/block-8.c | 58 ++++++
> gcc/testsuite/gcc.dg/graphite/interchange-1.c | 4 +-
> gcc/testsuite/gcc.dg/graphite/interchange-11.c | 3 +-
> gcc/testsuite/gcc.dg/graphite/interchange-12.c | 3 +-
> gcc/testsuite/gcc.dg/graphite/interchange-13.c | 54 ++++++
> gcc/testsuite/gcc.dg/graphite/interchange-14.c | 58 ++++++
> gcc/testsuite/gcc.dg/graphite/interchange-15.c | 53 ++++++
> gcc/testsuite/gcc.dg/graphite/interchange-8.c | 5 +-
> gcc/testsuite/gcc.dg/graphite/interchange-mvt.c | 3 +-
> gcc/tree-data-ref.c | 4 +-
> 25 files changed, 573 insertions(+), 175 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/graphite/block-8.c
> create mode 100644 gcc/testsuite/gcc.dg/graphite/interchange-13.c
> create mode 100644 gcc/testsuite/gcc.dg/graphite/interchange-14.c
> create mode 100644 gcc/testsuite/gcc.dg/graphite/interchange-15.c
^ permalink raw reply [flat|nested] 21+ messages in thread