2011-01-25 Basile Starynkevitch <basile@starynkevitch.net>

        MELT branch merged with trunk rev 169225

	* configure.ac: the PPL minimal version number 0.11 is hardwired,
	as in trunk.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/melt-branch@169227 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 91 insertions, 135 deletions

diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
index a6a5254ed17..b9b1d1b5880 100644
--- a/gcc/graphite-dependences.c
+++ b/gcc/graphite-dependences.c
@@ -35,41 +35,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "graphite-ppl.h"
 #include "graphite-poly.h"
 #include "graphite-dependences.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_Pointset_Powerset_C_Polyhedron_is_empty (ddp))
-    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);
-}
+#include "graphite-cloog-util.h"
 
 /* Comparison function for poly_ddr hash table.  */
 
@@ -180,6 +146,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");
     }
 
@@ -333,7 +300,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,
@@ -344,23 +313,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;
 
@@ -403,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_Pointset_Powerset_C_Polyhedron_is_empty (lex))
+  if (!ppl_powerset_is_empty (lex))
     ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
 
   ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
@@ -416,10 +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))
+	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))
 	ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
 
       ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
@@ -444,8 +421,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);
@@ -465,6 +442,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));
 
@@ -498,16 +476,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_Pointset_Powerset_C_Polyhedron_is_empty (res))
-    {
-      ppl_Pointset_Powerset_C_Polyhedron_t lex =
-	build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2),
+  if (ppl_powerset_is_empty (res))
+    return NULL;
+
+  lex = build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2),
 					  tdim1 + ddim1, 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.
@@ -518,12 +494,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)
@@ -540,28 +516,50 @@ 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))
+	   && same_pdr_p (pdr1, 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.  */
@@ -573,10 +571,11 @@ reduction_dr_1 (poly_bb_p pbb1, poly_dr_p pdr1, poly_dr_p pdr2)
   poly_dr_p pdr;
 
   FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr)
-    if (PDR_TYPE (pdr) == PDR_WRITE)
-      break;
+    if (PDR_TYPE (pdr) == PDR_WRITE
+	&& same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2))
+      return true;
 
-  return same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2);
+  return false;
 }
 
 /* Return true when the data dependence relation between the data
@@ -621,7 +620,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;
@@ -632,7 +631,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)
     {
@@ -671,7 +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_Pointset_Powerset_C_Polyhedron_is_empty (po_temp);
+  is_empty_p = ppl_powerset_is_empty (po_temp);
 
   ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp);
   free_poly_ddr (tpddr);
@@ -753,7 +752,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)
     {
@@ -772,7 +771,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_Pointset_Powerset_C_Polyhedron_is_empty (eqpp);
+  empty_p = ppl_powerset_is_empty (eqpp);
 
   ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
   free_poly_ddr (pddr);
@@ -802,36 +801,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;
@@ -843,11 +818,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);
@@ -860,7 +835,6 @@ dot_transformed_deps_stmt_1 (FILE *file, scop_p scop)
       }
 }
 
-
 /* Pretty print to FILE all the data dependences of SCoP in DOT
    format.  */
 
@@ -869,37 +843,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;
@@ -909,11 +864,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));
 
@@ -929,8 +885,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);
 }