graphite-interchange.c (pbb_interchange_profitable_p): Adjust the strides by multiplying by PDR_NB_REFS.

2009-08-28  Sebastian Pop  <sebastian.pop@amd.com>

	* graphite-interchange.c (pbb_interchange_profitable_p): Adjust
	the strides by multiplying by PDR_NB_REFS.
	* graphite-poly.c (can_collapse_pdr): New.
	(pdr_find_duplicate): New.
	(new_poly_dr): Call pdr_find_duplicate.  Collapse duplicate PDRs.
	Initialize PDR_NB_REFS.
	* graphite-poly.h (struct poly_dr): Add field nb_refs.
	(PDR_NB_REFS): New.
	(new_poly_dr): Number of subscripts is a graphite_dim_t.

From-SVN: r151191

5 files changed, 101 insertions, 4 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 715cb56..d8df593 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,17 @@
 2009-08-28  Sebastian Pop  <sebastian.pop@amd.com>
 
+	* graphite-interchange.c (pbb_interchange_profitable_p): Adjust
+	the strides by multiplying by PDR_NB_REFS.
+	* graphite-poly.c (can_collapse_pdr): New.
+	(pdr_find_duplicate): New.
+	(new_poly_dr): Call pdr_find_duplicate.  Collapse duplicate PDRs.
+	Initialize PDR_NB_REFS.
+	* graphite-poly.h (struct poly_dr): Add field nb_refs.
+	(PDR_NB_REFS): New.
+	(new_poly_dr): Number of subscripts is a graphite_dim_t.
+
+2009-08-28  Sebastian Pop  <sebastian.pop@amd.com>
+
 	PR middle-end/40965
 	* graphite-poly.c (apply_poly_transforms): Remove legality test before
 	any transform.
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 06ae677..c7b8fcf 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,24 @@
 2009-08-25  Sebastian Pop  <sebastian.pop@amd.com>
 
+	* graphite-interchange.c (pbb_interchange_profitable_p): Adjust
+	the strides by multiplying by PDR_NB_REFS.
+	* graphite-poly.c (can_collapse_pdr): New.
+	(pdr_find_duplicate): New.
+	(new_poly_dr): Call pdr_find_duplicate.  Collapse duplicate PDRs.
+	Initialize PDR_NB_REFS.
+	* graphite-poly.h (struct poly_dr): Add field nb_refs.
+	(PDR_NB_REFS): New.
+	(new_poly_dr): Number of subscripts is a graphite_dim_t.
+
+2009-08-25  Sebastian Pop  <sebastian.pop@amd.com>
+
+	Revert one of the previous commits:
+	* graphite-dependences.c (graphite_legal_transform_bb): Avoid
+	the computation of symmetric data dependence relations.
+	(dependency_between_pbbs_p): Same.
+
+2009-08-25  Sebastian Pop  <sebastian.pop@amd.com>
+
 	PR middle-end/40965
 	* graphite-poly.c (apply_poly_transforms): Remove legality test before
 	any transform.
diff --git a/gcc/graphite-interchange.c b/gcc/graphite-interchange.c
index bf944c8..0a751d6 100644
--- a/gcc/graphite-interchange.c
+++ b/gcc/graphite-interchange.c
@@ -244,7 +244,7 @@ pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2,
 {
   int i;
   poly_dr_p pdr;
-  Value d1, d2, s;
+  Value d1, d2, s, n;
   bool res;
 
   gcc_assert (depth1 < depth2);
@@ -254,13 +254,18 @@ pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2,
   value_init (d2);
   value_set_si (d2, 0);
   value_init (s);
+  value_init (n);
 
   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
     {
+      value_set_si (n, PDR_NB_REFS (pdr));
+
       memory_stride_in_loop (s, depth1, pdr);
+      value_multiply (s, s, n);
       value_addto (d1, d1, s);
 
       memory_stride_in_loop (s, depth2, pdr);
+      value_multiply (s, s, n);
       value_addto (d2, d2, s);
     }
 
@@ -269,6 +274,7 @@ pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2,
   value_clear (d1);
   value_clear (d2);
   value_clear (s);
+  value_clear (n);
 
   return res;
 }
diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c
index 21bba6c6..3e005d4 100644
--- a/gcc/graphite-poly.c
+++ b/gcc/graphite-poly.c
@@ -261,6 +261,53 @@ apply_poly_transforms (scop_p scop)
   return transform_done;
 }
 
+/* Returns true when PDR in the same PBB and is a duplicate of the
+   data reference described by ACCESSES, TYPE, and NB_SUBSCRIPTS.  */
+
+static inline bool
+can_collapse_pdr (poly_dr_p pdr, poly_bb_p pbb,
+		  ppl_Pointset_Powerset_C_Polyhedron_t accesses,
+		  enum poly_dr_type type, graphite_dim_t nb_subscripts)
+{
+  bool res = false;
+  ppl_Pointset_Powerset_C_Polyhedron_t af, diff;
+
+  if (PDR_PBB (pdr) != pbb
+      || PDR_NB_SUBSCRIPTS (pdr) != nb_subscripts
+      || PDR_TYPE (pdr) != type)
+    return false;
+
+  ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
+    (&diff, accesses);
+  af = PDR_ACCESSES (pdr);
+  ppl_Pointset_Powerset_C_Polyhedron_difference_assign (diff, af);
+
+  if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (diff))
+    res = true;
+
+  ppl_delete_Pointset_Powerset_C_Polyhedron (diff);
+  return res;
+}
+
+/* Returns a duplicate of the data reference described by ACCESSES,
+   TYPE, and NB_SUBSCRIPTS in the vector PBB_DRS (PBB).  If there is
+   no duplicate, returns NULL.  */
+
+static inline poly_dr_p
+pdr_find_duplicate (poly_bb_p pbb,
+		    ppl_Pointset_Powerset_C_Polyhedron_t accesses,
+		    enum poly_dr_type type, graphite_dim_t nb_subscripts)
+{
+  int i;
+  poly_dr_p pdr;
+
+  for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
+    if (can_collapse_pdr (pdr, pbb, accesses, type, nb_subscripts))
+      return pdr;
+
+  return NULL;
+}
+
 /* Create a new polyhedral data reference and add it to PBB.  It is
    defined by its ACCESSES, its TYPE, and the number of subscripts
    NB_SUBSCRIPTS.  */
@@ -268,12 +315,21 @@ apply_poly_transforms (scop_p scop)
 void
 new_poly_dr (poly_bb_p pbb,
 	     ppl_Pointset_Powerset_C_Polyhedron_t accesses,
-	     enum poly_dr_type type, void *cdr, int nb_subscripts)
+	     enum poly_dr_type type, void *cdr, graphite_dim_t nb_subscripts)
 {
-  poly_dr_p pdr = XNEW (struct poly_dr);
   static int id = 0;
+  poly_dr_p pdr;
+  poly_dr_p same = pdr_find_duplicate (pbb, accesses, type, nb_subscripts);
+
+  if (same)
+    {
+      PDR_NB_REFS (same) += 1;
+      return;
+    }
 
+  pdr = XNEW (struct poly_dr);
   PDR_ID (pdr) = id++;
+  PDR_NB_REFS (pdr) = 1;
   PDR_PBB (pdr) = pbb;
   PDR_ACCESSES (pdr) = accesses;
   PDR_TYPE (pdr) = type;
diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h
index 10831af..8f7352a 100644
--- a/gcc/graphite-poly.h
+++ b/gcc/graphite-poly.h
@@ -56,6 +56,9 @@ struct poly_dr
   /* An identifier for this PDR.  */
   int id;
 
+  /* The number of data refs identical to this one in the PBB.  */
+  int nb_refs;
+
   /* A pointer to compiler's data reference description.  */
   void *compiler_dr;
 
@@ -137,6 +140,7 @@ struct poly_dr
 };
 
 #define PDR_ID(PDR) (PDR->id)
+#define PDR_NB_REFS(PDR) (PDR->nb_refs)
 #define PDR_CDR(PDR) (PDR->compiler_dr)
 #define PDR_PBB(PDR) (PDR->pbb)
 #define PDR_TYPE(PDR) (PDR->type)
@@ -144,7 +148,7 @@ struct poly_dr
 #define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts)
 
 void new_poly_dr (poly_bb_p, ppl_Pointset_Powerset_C_Polyhedron_t,
-		  enum poly_dr_type, void *, int);
+		  enum poly_dr_type, void *, graphite_dim_t);
 void free_poly_dr (poly_dr_p);
 void debug_pdr (poly_dr_p);
 void print_pdr (FILE *, poly_dr_p);