[PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear

[PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear

[Sebastian Pop]

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.

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

[PATCH 04/10] Fix pbb_remove_duplicate_pdrs.

[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

[PATCH 06/10] Correct the precedence relation.

[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

[PATCH 02/10] Print the data dependence polyhedron in the PPL format.

[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

[PATCH 08/10] Minimize the number of expensive calls to ppl_powerset_is_empty.

[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

[PATCH 05/10] speedup compilation

[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

[PATCH 01/10] Add debug_gmp_value.

[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

[PATCH 09/10] Expect at least the version 0.11 of PPL.

[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

[PATCH 10/10] Remove the temporary array for reductions written to memory.

[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

[PATCH 03/10] Test the profitability of interchange on the perfect nest.

[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

[PATCH 07/10] Use PIP to determine the integer feasibility of a constraint system.

[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

Re: [PATCH 07/10] Use PIP to determine the integer feasibility of a constraint system.

[Sven Verdoolaege]

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

Re: [PATCH 07/10] Use PIP to determine the integer feasibility of a constraint system.

[Sebastian Pop]

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

Re: [PATCH 07/10] Use PIP to determine the integer feasibility of a constraint system.

[Sven Verdoolaege]

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

Re: [PATCH 00/10] Make -floop-interchange catch almost all testcases of -ftree-loop-linear

[Jack Howarth]

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

[PATCH] Pass 0 as the number of parameters to PIP when testing for integer feasibility.

[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

Re: [PATCH 10/10] Remove the temporary array for reductions written to memory.

[Sebastian Pop]

Hi,

On Sat, Jan 15, 2011 at 03:21, Sebastian Pop <sebpop@gmail.com> wrote:
> Albert, Konrad,
>
> this patch fixes (without data dep analysis changes)
> the motivating example of Figures 1, 2, 3,... of:
> http://gcc.gnu.org/wiki/summit2010?action=AttachFile&do=get&target=trifunovic.pdf
>
> Sebastian
>
> On Sat, Jan 15, 2011 at 03:05, Sebastian Pop <sebpop@gmail.com> wrote:
>> 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.

This patch introduced a regression that I discussed with Tobias today
on the Graphite phone call.

This patch avoids the creation of temporary arrays when they are not
necessary, i.e., when the result of the reduction is written back to
memory.  Here is the diff before "0" and after "1" the patch on the
gimple representation of interchange-12.c

--- 0	2011-01-19 12:14:22.000000000 -0600
+++ 1	2011-01-19 12:15:52.000000000 -0600
@@ -81,17 +81,17 @@
         # .MEM_22 = VDEF <.MEM_35>
         A[i_31][j_32] = 0;
         # .MEM_7 = VDEF <.MEM_22>
-        Commutative_Associative_Reduction.5[0] = 0;
+        A[i_31][j_32] = 0;

       }
       bb_7 (preds = {bb_5 }, succs = {bb_17 })
       {
       <bb 7>:
         # VUSE <.MEM_38>
-        D.2738_23 = Commutative_Associative_Reduction.5[0];
-        A_I_I_lsm.4_44 = D.2738_23;
+        D.2737_23 = A[i_31][j_32];
+        A_I_I_lsm.4_44 = D.2737_23;
         # .MEM_54 = VDEF <.MEM_38>
-        Cross_BB_scalar_dependence.6[0] = A_I_I_lsm.4_44;
+        Cross_BB_scalar_dependence.5[0] = A_I_I_lsm.4_44;

       }
       bb_17 (preds = {bb_7 }, succs = {bb_14 })
@@ -103,7 +103,7 @@
       {
       <bb 14>:
         # VUSE <.MEM_54>
-        A_I_I_lsm.4_52 = Cross_BB_scalar_dependence.6[0];
+        A_I_I_lsm.4_52 = Cross_BB_scalar_dependence.5[0];
         # .MEM_43 = VDEF <.MEM_54>
         A[i_31][j_32] = A_I_I_lsm.4_52;
         j_13 = j_32 + 1;
@@ -121,7 +121,7 @@
           # k_33 = PHI <k_12(6), 0(4)>
           # .MEM_34 = PHI <.MEM_38(6), .MEM_7(4)>
           # VUSE <.MEM_34>
-          prephitmp.3_37 = Commutative_Associative_Reduction.5[0];
+          prephitmp.3_37 = A[i_31][j_32];
           # VUSE <.MEM_34>
           D.2722_8 = B[i_31][k_33];
           # VUSE <.MEM_34>
@@ -129,7 +129,7 @@
           D.2724_10 = D.2722_8 * D.2723_9;
           D.2725_11 = D.2724_10 + prephitmp.3_37;
           # .MEM_38 = VDEF <.MEM_34>
-          Commutative_Associative_Reduction.5[0] = D.2725_11;
+          A[i_31][j_32] = D.2725_11;
           k_12 = k_33 + 1;
           if (k_12 != 200)
             goto <bb 6>;

We now use the data reference A instead of creating the one-element
array Commutative_Associative_Reduction, and now we can interchange
the two loops as we know the access function for the data reference.

The problem occurs in 3 SPEC benchmarks reduced to:

      SUBROUTINE CAMB(RX2,RTX,NUM)
      DIMENSION RX2(NUM,NUM),RTX(NUM,NUM)
      DO I=1,NUM
        DO J=1,I
          DO M=1,NUM
            RX2(I,J)=RX2(I,J)+RTX(M,I)
          END DO
        END DO
      END DO
      IF (RX2(I,1).LE.EIGCT2) THEN
      RTX(I,1)=4.0D+00
      END IF
      END

For some reason (unimportant for now), the scop is bounded to the
innermost loop M.  RX2(I,J) is first scalar optimized such that the
reduction happens into a scalar:

        DO J=1,I
	  t = RX2(I,J)
          DO M=1,NUM
            t=t+RTX(M,I)
          END DO
	  RX2(I,J)=t
        END DO

and then when we rewrite the commutative associative reductions out of
SSA, we reintroduce the data reference RX2(I,J) in the loop nest.  The
access functions for RX2(I,J) are parameters of the scop, as they do
not variate in the scop (bounded to the innermost loop here).  As we
rewrite out-of-SSA quite late in the polyhedral translation, after the
parameters of the scop have already been determined, we fail in this
specific case because we introduce new parameters that are not
registered yet in the representation.  The first part of the patch to fix
this is to move the rewrite of reductions before parameters analysis:

diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 12b93b0..9184065 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -3159,6 +3159,9 @@ build_poly_scop (scop_p scop)
   if (!scop_ivs_can_be_represented (scop))
     return;

+  if (flag_associative_math)
+    rewrite_commutative_reductions_out_of_ssa (scop);
+
   build_sese_loop_nests (region);
   build_sese_conditions (region);
   find_scop_parameters (scop);
@@ -3175,8 +3178,6 @@ build_poly_scop (scop_p scop)
      representation to the polyhedral representation to avoid scev
      analysis failures.  That means that these functions will insert
      new data references that they create in the right place.  */
-  if (flag_associative_math)
-    rewrite_commutative_reductions_out_of_ssa (scop);
   rewrite_reductions_out_of_ssa (scop);
   rewrite_cross_bb_scalar_deps_out_of_ssa (scop);

But this is not enough, as rewrite_commutative_reductions_out_of_ssa
updates some parts of the polyhedral representation, and these should
now go away.  I am preparing a patch to fix all this.

Sebastian

[PATCH 0/3] Fix 3 SPEC compile fails

[Sebastian Pop]

Hi,

This patch set corrects the problem described earlier.  I am
committing this to the graphite branch for testing.

Sebastian Pop (3):
  Move rewrite_commutative_reductions_out_of_ssa before
    find_scop_parameters.
  Pass to dr_analyze_indices the analysis loop for subscripts.
  Only copy PBB_DOMAIN when it is initialized.

 gcc/ChangeLog.graphite                     |   32 ++++++++++++
 gcc/graphite-scop-detection.c              |    4 +-
 gcc/graphite-sese-to-poly.c                |   71 +++++++++++++++++++++++----
 gcc/testsuite/gfortran.dg/graphite/id-23.f |   13 +++++
 gcc/tree-data-ref.c                        |   31 +++++++------
 gcc/tree-data-ref.h                        |    4 +-
 gcc/tree-ssa-loop-prefetch.c               |    3 +-
 7 files changed, 129 insertions(+), 29 deletions(-)
 create mode 100644 gcc/testsuite/gfortran.dg/graphite/id-23.f

[PATCH 3/3] Only copy PBB_DOMAIN when it is initialized.

[Sebastian Pop]

2011-01-19  Sebastian Pop  <sebastian.pop@amd.com>

	* graphite-sese-to-poly.c (new_pbb_from_pbb): Only copy PBB_DOMAIN
	when it is initialized.

	* gfortran.dg/graphite/id-23.f: New.
---
 gcc/ChangeLog.graphite                     |    7 +++++++
 gcc/graphite-sese-to-poly.c                |    6 ++++--
 gcc/testsuite/gfortran.dg/graphite/id-23.f |   13 +++++++++++++
 3 files changed, 24 insertions(+), 2 deletions(-)
 create mode 100644 gcc/testsuite/gfortran.dg/graphite/id-23.f

diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 613dbc1..8a03a39 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,12 @@
 2011-01-19  Sebastian Pop  <sebastian.pop@amd.com>
 
+	* graphite-sese-to-poly.c (new_pbb_from_pbb): Only copy PBB_DOMAIN
+	when it is initialized.
+
+	* gfortran.dg/graphite/id-23.f: New.
+
+2011-01-19  Sebastian Pop  <sebastian.pop@amd.com>
+
 	* graphite-scop-detection.c (stmt_has_simple_data_refs_p): Update
 	call to graphite_find_data_references_in_stmt.
 	* graphite-sese-to-poly.c (outermost_loop_in_sese_1): New.
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 44d48f0..48ae6df 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -2152,9 +2152,11 @@ new_pbb_from_pbb (scop_p scop, poly_bb_p pbb, basic_block bb)
     if (VEC_index (poly_bb_p, SCOP_BBS (scop), index) == pbb)
       break;
 
+  if (PBB_DOMAIN (pbb))
+    ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
+      (&PBB_DOMAIN (pbb1), PBB_DOMAIN (pbb));
+
   GBB_PBB (gbb1) = pbb1;
-  ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
-    (&PBB_DOMAIN (pbb1), PBB_DOMAIN (pbb));
   GBB_CONDITIONS (gbb1) = VEC_copy (gimple, heap, GBB_CONDITIONS (gbb));
   GBB_CONDITION_CASES (gbb1) = VEC_copy (gimple, heap, GBB_CONDITION_CASES (gbb));
   VEC_safe_insert (poly_bb_p, heap, SCOP_BBS (scop), index + 1, pbb1);
diff --git a/gcc/testsuite/gfortran.dg/graphite/id-23.f b/gcc/testsuite/gfortran.dg/graphite/id-23.f
new file mode 100644
index 0000000..74c2928
--- /dev/null
+++ b/gcc/testsuite/gfortran.dg/graphite/id-23.f
@@ -0,0 +1,13 @@
+      SUBROUTINE CAMB(RX2,RTX,NUM)
+      DIMENSION RX2(NUM,NUM),RTX(NUM,NUM)
+      DO I=1,NUM
+        DO J=1,I
+          DO M=1,NUM
+            RX2(I,J)=RX2(I,J)+RTX(M,I)
+          END DO
+        END DO
+      END DO
+      IF (RX2(I,1).LE.EIGCT2) THEN
+      RTX(I,1)=4.0D+00
+      END IF
+      END
-- 
1.7.1

[PATCH 1/3] Move rewrite_commutative_reductions_out_of_ssa before find_scop_parameters.

[Sebastian Pop]

2011-01-19  Sebastian Pop  <sebastian.pop@amd.com>

	* graphite-sese-to-poly.c (build_poly_scop): Move
	rewrite_commutative_reductions_out_of_ssa before
	find_scop_parameters.
---
 gcc/ChangeLog.graphite      |    6 ++++++
 gcc/graphite-sese-to-poly.c |    5 +++--
 2 files changed, 9 insertions(+), 2 deletions(-)

diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index ed3e4ab..45e945c 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,3 +1,9 @@
+2011-01-19  Sebastian Pop  <sebastian.pop@amd.com>
+
+	* graphite-sese-to-poly.c (build_poly_scop): Move
+	rewrite_commutative_reductions_out_of_ssa before
+	find_scop_parameters.
+
 2011-01-18  Sebastian Pop  <sebastian.pop@amd.com>
 
 	PR tree-optimization/46970
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 12b93b0..9184065 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -3159,6 +3159,9 @@ build_poly_scop (scop_p scop)
   if (!scop_ivs_can_be_represented (scop))
     return;
 
+  if (flag_associative_math)
+    rewrite_commutative_reductions_out_of_ssa (scop);
+
   build_sese_loop_nests (region);
   build_sese_conditions (region);
   find_scop_parameters (scop);
@@ -3175,8 +3178,6 @@ build_poly_scop (scop_p scop)
      representation to the polyhedral representation to avoid scev
      analysis failures.  That means that these functions will insert
      new data references that they create in the right place.  */
-  if (flag_associative_math)
-    rewrite_commutative_reductions_out_of_ssa (scop);
   rewrite_reductions_out_of_ssa (scop);
   rewrite_cross_bb_scalar_deps_out_of_ssa (scop);
 
-- 
1.7.1

[PATCH 2/3] Pass to dr_analyze_indices the analysis loop for subscripts.

[Sebastian Pop]

2011-01-19  Sebastian Pop  <sebastian.pop@amd.com>

	* graphite-scop-detection.c (stmt_has_simple_data_refs_p): Update
	call to graphite_find_data_references_in_stmt.
	* graphite-sese-to-poly.c (outermost_loop_in_sese_1): New.
	(try_generate_gimple_bb): Call outermost_loop_in_sese_1.  Update
	call to graphite_find_data_references_in_stmt.
	(analyze_drs_in_stmts): Same.
	* tree-data-ref.c (dr_analyze_indices): Pass in parameter the loop
	in which the scalar analysis of indices is performed.
	(create_data_ref): Same.  Update call to dr_analyze_indices.
	(find_data_references_in_stmt): Update call to create_data_ref.
	(graphite_find_data_references_in_stmt): Same.
	* tree-data-ref.h (graphite_find_data_references_in_stmt): Update
	declaration.
	(create_data_ref): Same.
	* tree-ssa-loop-prefetch.c (determine_loop_nest_reuse): Update
	call to create_data_ref.
---
 gcc/ChangeLog.graphite        |   19 +++++++++++++
 gcc/graphite-scop-detection.c |    4 ++-
 gcc/graphite-sese-to-poly.c   |   60 ++++++++++++++++++++++++++++++++++++-----
 gcc/tree-data-ref.c           |   31 +++++++++++---------
 gcc/tree-data-ref.h           |    4 +-
 gcc/tree-ssa-loop-prefetch.c  |    3 +-
 6 files changed, 96 insertions(+), 25 deletions(-)

diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 45e945c..613dbc1 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,24 @@
 2011-01-19  Sebastian Pop  <sebastian.pop@amd.com>
 
+	* graphite-scop-detection.c (stmt_has_simple_data_refs_p): Update
+	call to graphite_find_data_references_in_stmt.
+	* graphite-sese-to-poly.c (outermost_loop_in_sese_1): New.
+	(try_generate_gimple_bb): Call outermost_loop_in_sese_1.  Update
+	call to graphite_find_data_references_in_stmt.
+	(analyze_drs_in_stmts): Same.
+	* tree-data-ref.c (dr_analyze_indices): Pass in parameter the loop
+	in which the scalar analysis of indices is performed.
+	(create_data_ref): Same.  Update call to dr_analyze_indices.
+	(find_data_references_in_stmt): Update call to create_data_ref.
+	(graphite_find_data_references_in_stmt): Same.
+	* tree-data-ref.h (graphite_find_data_references_in_stmt): Update
+	declaration.
+	(create_data_ref): Same.
+	* tree-ssa-loop-prefetch.c (determine_loop_nest_reuse): Update
+	call to create_data_ref.
+
+2011-01-19  Sebastian Pop  <sebastian.pop@amd.com>
+
 	* graphite-sese-to-poly.c (build_poly_scop): Move
 	rewrite_commutative_reductions_out_of_ssa before
 	find_scop_parameters.
diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
index e74e11e..ed30082 100644
--- a/gcc/graphite-scop-detection.c
+++ b/gcc/graphite-scop-detection.c
@@ -264,7 +264,9 @@ stmt_has_simple_data_refs_p (loop_p outermost_loop, gimple stmt)
   bool res = true;
   VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
 
-  graphite_find_data_references_in_stmt (outermost_loop, stmt, &drs);
+  graphite_find_data_references_in_stmt (outermost_loop,
+					 loop_containing_stmt (stmt),
+					 stmt, &drs);
 
   FOR_EACH_VEC_ELT (data_reference_p, drs, j, dr)
     for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 9184065..44d48f0 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -241,6 +241,32 @@ free_scops (VEC (scop_p, heap) *scops)
   VEC_free (scop_p, heap, scops);
 }
 
+/* Same as outermost_loop_in_sese, returns the outermost loop
+   containing BB in REGION, but makes sure that the returned loop
+   belongs to the REGION, and so this returns the first loop in the
+   REGION when the loop containing BB does not belong to REGION.  */
+
+static loop_p
+outermost_loop_in_sese_1 (sese region, basic_block bb)
+{
+  loop_p nest = outermost_loop_in_sese (region, bb);
+
+  if (loop_in_sese_p (nest, region))
+    return nest;
+
+  /* When the basic block BB does not belong to a loop in the region,
+     return the first loop in the region.  */
+  nest = nest->inner;
+  while (nest)
+    if (loop_in_sese_p (nest, region))
+      break;
+    else
+      nest = nest->next;
+
+  gcc_assert (nest);
+  return nest;
+}
+
 /* Generates a polyhedral black box only if the bb contains interesting
    information.  */
 
@@ -248,14 +274,23 @@ static gimple_bb_p
 try_generate_gimple_bb (scop_p scop, basic_block bb)
 {
   VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
-  loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
+  sese region = SCOP_REGION (scop);
+  loop_p nest = outermost_loop_in_sese_1 (region, bb);
   gimple_stmt_iterator gsi;
 
   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     {
       gimple stmt = gsi_stmt (gsi);
-      if (!is_gimple_debug (stmt))
-	graphite_find_data_references_in_stmt (nest, stmt, &drs);
+      loop_p loop;
+
+      if (is_gimple_debug (stmt))
+	continue;
+
+      loop = loop_containing_stmt (stmt);
+      if (!loop_in_sese_p (loop, region))
+	loop = nest;
+
+      graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
     }
 
   return new_gimple_bb (bb, drs);
@@ -2019,17 +2054,28 @@ analyze_drs_in_stmts (scop_p scop, basic_block bb, VEC (gimple, heap) *stmts)
   gimple_bb_p gbb;
   gimple stmt;
   int i;
+  sese region = SCOP_REGION (scop);
 
-  if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
+  if (!bb_in_sese_p (bb, region))
     return;
 
-  nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
+  nest = outermost_loop_in_sese_1 (region, bb);
   gbb = gbb_from_bb (bb);
 
   FOR_EACH_VEC_ELT (gimple, stmts, i, stmt)
-    if (!is_gimple_debug (stmt))
-      graphite_find_data_references_in_stmt (nest, stmt,
+    {
+      loop_p loop;
+
+      if (is_gimple_debug (stmt))
+	continue;
+
+      loop = loop_containing_stmt (stmt);
+      if (!loop_in_sese_p (loop, region))
+	loop = nest;
+
+      graphite_find_data_references_in_stmt (nest, loop, stmt,
 					     &GBB_DATA_REFS (gbb));
+    }
 }
 
 /* Insert STMT at the end of the STMTS sequence and then insert the
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 7a5fe89..9e5df7d 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -832,13 +832,11 @@ dr_analyze_innermost (struct data_reference *dr)
 }
 
 /* Determines the base object and the list of indices of memory reference
-   DR, analyzed in loop nest NEST.  */
+   DR, analyzed in LOOP and instantiated in loop nest NEST.  */
 
 static void
-dr_analyze_indices (struct data_reference *dr, struct loop *nest)
+dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
 {
-  gimple stmt = DR_STMT (dr);
-  struct loop *loop = loop_containing_stmt (stmt);
   VEC (tree, heap) *access_fns = NULL;
   tree ref = unshare_expr (DR_REF (dr)), aref = ref, op;
   tree base, off, access_fn = NULL_TREE;
@@ -947,11 +945,13 @@ free_data_ref (data_reference_p dr)
 
 /* Analyzes memory reference MEMREF accessed in STMT.  The reference
    is read if IS_READ is true, write otherwise.  Returns the
-   data_reference description of MEMREF.  NEST is the outermost loop of the
-   loop nest in that the reference should be analyzed.  */
+   data_reference description of MEMREF.  NEST is the outermost loop
+   in which the reference should be instantiated, LOOP is the loop in
+   which the data reference should be analyzed.  */
 
 struct data_reference *
-create_data_ref (struct loop *nest, tree memref, gimple stmt, bool is_read)
+create_data_ref (loop_p nest, loop_p loop, tree memref, gimple stmt,
+		 bool is_read)
 {
   struct data_reference *dr;
 
@@ -968,7 +968,7 @@ create_data_ref (struct loop *nest, tree memref, gimple stmt, bool is_read)
   DR_IS_READ (dr) = is_read;
 
   dr_analyze_innermost (dr);
-  dr_analyze_indices (dr, nest);
+  dr_analyze_indices (dr, nest, loop);
   dr_analyze_alias (dr);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -4253,7 +4253,8 @@ find_data_references_in_stmt (struct loop *nest, gimple stmt,
 
   FOR_EACH_VEC_ELT (data_ref_loc, references, i, ref)
     {
-      dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
+      dr = create_data_ref (nest, loop_containing_stmt (stmt),
+			    *ref->pos, stmt, ref->is_read);
       gcc_assert (dr != NULL);
 
       /* FIXME -- data dependence analysis does not work correctly for objects
@@ -4274,12 +4275,14 @@ find_data_references_in_stmt (struct loop *nest, gimple stmt,
   return ret;
 }
 
-/* Stores the data references in STMT to DATAREFS.  If there is an unanalyzable
-   reference, returns false, otherwise returns true.  NEST is the outermost
-   loop of the loop nest in which the references should be analyzed.  */
+/* Stores the data references in STMT to DATAREFS.  If there is an
+   unanalyzable reference, returns false, otherwise returns true.
+   NEST is the outermost loop of the loop nest in which the references
+   should be instantiated, LOOP is the loop in which the references
+   should be analyzed.  */
 
 bool
-graphite_find_data_references_in_stmt (struct loop *nest, gimple stmt,
+graphite_find_data_references_in_stmt (loop_p nest, loop_p loop, gimple stmt,
 				       VEC (data_reference_p, heap) **datarefs)
 {
   unsigned i;
@@ -4296,7 +4299,7 @@ graphite_find_data_references_in_stmt (struct loop *nest, gimple stmt,
 
   FOR_EACH_VEC_ELT (data_ref_loc, references, i, ref)
     {
-      dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
+      dr = create_data_ref (nest, loop, *ref->pos, stmt, ref->is_read);
       gcc_assert (dr != NULL);
       VEC_safe_push (data_reference_p, heap, *datarefs, dr);
     }
diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h
index 2e85677..55c1209 100644
--- a/gcc/tree-data-ref.h
+++ b/gcc/tree-data-ref.h
@@ -419,9 +419,9 @@ extern void free_data_ref (data_reference_p);
 extern void free_data_refs (VEC (data_reference_p, heap) *);
 extern bool find_data_references_in_stmt (struct loop *, gimple,
 					  VEC (data_reference_p, heap) **);
-extern bool graphite_find_data_references_in_stmt (struct loop *, gimple,
+extern bool graphite_find_data_references_in_stmt (loop_p, loop_p, gimple,
 						   VEC (data_reference_p, heap) **);
-struct data_reference *create_data_ref (struct loop *, tree, gimple, bool);
+struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple, bool);
 extern bool find_loop_nest (struct loop *, VEC (loop_p, heap) **);
 extern void compute_all_dependences (VEC (data_reference_p, heap) *,
 				     VEC (ddr_p, heap) **, VEC (loop_p, heap) *,
diff --git a/gcc/tree-ssa-loop-prefetch.c b/gcc/tree-ssa-loop-prefetch.c
index 59c65d3..d920ec6 100644
--- a/gcc/tree-ssa-loop-prefetch.c
+++ b/gcc/tree-ssa-loop-prefetch.c
@@ -1562,7 +1562,8 @@ determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs,
   for (gr = refs; gr; gr = gr->next)
     for (ref = gr->refs; ref; ref = ref->next)
       {
-	dr = create_data_ref (nest, ref->mem, ref->stmt, !ref->write_p);
+	dr = create_data_ref (nest, loop_containing_stmt (ref->stmt),
+			      ref->mem, ref->stmt, !ref->write_p);
 
 	if (dr)
 	  {
-- 
1.7.1