graphite-dependences.c (reduction_dr_1): New.

2009-10-06  Sebastian Pop  <sebastian.pop@amd.com>

	* graphite-dependences.c (reduction_dr_1): New.
	(reduction_dr_p): New.
	(graphite_legal_transform_dr): Call reduction_dr_p.
	(reduction_ddr): Renamed reduction_ddr_p.
	* graphite-poly.h (same_pdr_p): New.
	(number_of_write_pdrs): New.
	* graphite-sese-to-poly.c (nb_data_writes_in_bb): New.
	(split_reduction_stmt): Do not split reduction statements
	when there are no writes to memory.
	(translate_scalar_reduction_to_array_for_stmt): Insert the
	memory reduction statement just after the scalar reduction statement.

	* gcc.dg/graphite/interchange-10.c: Updated to differ from interchange-4.c.
	Un-XFAIL-ed.
	* gcc.dg/graphite/interchange-3.c: Un-XFAIL-ed.
	* gcc.dg/graphite/interchange-4.c: Un-XFAIL-ed.

From-SVN: r154564

6 files changed, 116 insertions, 7 deletions

diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 57db61d..7fe430e 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,24 @@
 2009-10-06  Sebastian Pop  <sebastian.pop@amd.com>
 
+	* graphite-dependences.c (reduction_dr_1): New.
+	(reduction_dr_p): New.
+	(graphite_legal_transform_dr): Call reduction_dr_p.
+	(reduction_ddr): Renamed reduction_ddr_p.
+	* graphite-poly.h (same_pdr_p): New.
+	(number_of_write_pdrs): New.
+	* graphite-sese-to-poly.c (nb_data_writes_in_bb): New.
+	(split_reduction_stmt): Do not split reduction statements
+	when there are no writes to memory.
+	(translate_scalar_reduction_to_array_for_stmt): Insert the
+	memory reduction statement just after the scalar reduction statement.
+
+	* gcc.dg/graphite/interchange-10.c: Updated to differ from interchange-4.c.
+	Un-XFAIL-ed.
+	* gcc.dg/graphite/interchange-3.c: Un-XFAIL-ed.
+	* gcc.dg/graphite/interchange-4.c: Un-XFAIL-ed.
+
+2009-10-06  Sebastian Pop  <sebastian.pop@amd.com>
+
 	* graphite-interchange.c (lst_apply_interchange): New.
 	(lst_interchange_profitable_p): New.
 	(lst_try_interchange_loops): New.
diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
index 2e777b3..12b48f8 100644
--- a/gcc/graphite-dependences.c
+++ b/gcc/graphite-dependences.c
@@ -524,6 +524,45 @@ pddr_original_scattering (poly_bb_p pbb1, poly_bb_p pbb2,
   return pddr;
 }
 
+/* Return true when the data dependence relation between the data
+   references PDR1 belonging to PBB1 and PDR2 is part of a
+   reduction.  */
+
+static inline bool
+reduction_dr_1 (poly_bb_p pbb1, poly_dr_p pdr1, poly_dr_p pdr2)
+{
+  int i;
+  poly_dr_p pdr;
+
+  /* PBB1 should be a reduction PBB.  Reduction PBBs should have only
+     one write.  */
+  gcc_assert (PBB_IS_REDUCTION (pbb1)
+	      && number_of_write_pdrs (pbb1) == 1);
+
+  for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr); i++)
+    if (PDR_TYPE (pdr) == PDR_WRITE)
+      break;
+
+  return same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2);
+}
+
+/* Return true when the data dependence relation between the data
+   references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is
+   part of a reduction.  */
+
+static inline bool
+reduction_dr_p (poly_bb_p pbb1, poly_bb_p pbb2,
+		poly_dr_p pdr1, poly_dr_p pdr2)
+{
+  if (PBB_IS_REDUCTION (pbb1))
+    return reduction_dr_1 (pbb1, pdr1, pdr2);
+
+  if (PBB_IS_REDUCTION (pbb2))
+    return reduction_dr_1 (pbb2, pdr2, pdr1);
+
+  return false;
+}
+
 /* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
    and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
    functions.  */
@@ -542,6 +581,9 @@ graphite_legal_transform_dr (poly_bb_p pbb1, poly_bb_p pbb2,
   ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
   ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
 
+  if (reduction_dr_p (pbb1, pbb2, pdr1, pdr2))
+    return true;
+
   pddr = pddr_original_scattering (pbb1, pbb2, pdr1, pdr2);
   if (!pddr)
     return true;
@@ -589,7 +631,7 @@ graphite_legal_transform_dr (poly_bb_p pbb1, poly_bb_p pbb2,
    part of a reduction.  */
 
 static inline bool
-reduction_ddr (poly_bb_p pbb1, poly_bb_p pbb2)
+reduction_ddr_p (poly_bb_p pbb1, poly_bb_p pbb2)
 {
   return pbb1 == pbb2 && PBB_IS_REDUCTION (pbb1);
 }
@@ -609,7 +651,7 @@ graphite_legal_transform_bb (poly_bb_p pbb1, poly_bb_p pbb2)
   if (!PBB_PDR_DUPLICATES_REMOVED (pbb2))
     pbb_remove_duplicate_pdrs (pbb2);
 
-  if (reduction_ddr (pbb1, pbb2))
+  if (reduction_ddr_p (pbb1, pbb2))
     return true;
 
   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h
index f9e59db..b3541d6 100644
--- a/gcc/graphite-poly.h
+++ b/gcc/graphite-poly.h
@@ -248,6 +248,17 @@ pdr_may_write_p (poly_dr_p pdr)
   return PDR_TYPE (pdr) == PDR_MAY_WRITE;
 }
 
+/* Return true when PDR1 and PDR2 are similar data accesses: they have
+   the same base array, and the same access functions.  */
+
+static inline bool
+same_pdr_p (poly_dr_p pdr1, poly_dr_p pdr2)
+{
+  return PDR_TYPE (pdr1) == PDR_TYPE (pdr2)
+    && PDR_NB_SUBSCRIPTS (pdr1) == PDR_NB_SUBSCRIPTS (pdr2)
+    && PDR_BASE_OBJECT_SET (pdr1) == PDR_BASE_OBJECT_SET (pdr2);
+}
+
 typedef struct poly_scattering *poly_scattering_p;
 
 struct poly_scattering
@@ -351,6 +362,22 @@ extern void pbb_number_of_iterations (poly_bb_p, graphite_dim_t, Value);
 extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, Value);
 extern void pbb_remove_duplicate_pdrs (poly_bb_p);
 
+/* Return the number of write data references in PBB.  */
+
+static inline int
+number_of_write_pdrs (poly_bb_p pbb)
+{
+  int res = 0;
+  int i;
+  poly_dr_p pdr;
+
+  for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
+    if (PDR_TYPE (pdr) == PDR_WRITE)
+      res++;
+
+  return res;
+}
+
 /* The index of the PBB.  */
 
 static inline int
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 807e287..75d10c6 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -2213,6 +2213,22 @@ nb_pbbs_in_loops (scop_p scop)
   return res;
 }
 
+/* Return the number of data references in BB that write in
+   memory.  */
+
+static int
+nb_data_writes_in_bb (basic_block bb)
+{
+  int res = 0;
+  gimple_stmt_iterator gsi;
+
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    if (gimple_vdef (gsi_stmt (gsi)))
+      res++;
+
+  return res;
+}
+
 /* Splits STMT out of its current BB.  */
 
 static basic_block
@@ -2222,6 +2238,11 @@ split_reduction_stmt (gimple stmt)
   basic_block bb = gimple_bb (stmt);
   edge e;
 
+  /* Do not split basic blocks with no writes to memory: the reduction
+     will be the only write to memory.  */
+  if (nb_data_writes_in_bb (bb) == 0)
+    return bb;
+
   split_block (bb, stmt);
 
   gsi = gsi_last_bb (bb);
@@ -2444,7 +2465,7 @@ translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt,
   gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
 
   assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
-  insert_gsi = gsi_last_bb (bb);
+  insert_gsi = gsi_for_stmt (stmt);
   gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT);
 }
 
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-3.c b/gcc/testsuite/gcc.dg/graphite/interchange-3.c
index 72880e3..c2a6744 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-3.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-3.c
@@ -17,5 +17,5 @@ int foo(int N, int *res)
       *res = sum + N;
 }
 
-/* { 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-4.c b/gcc/testsuite/gcc.dg/graphite/interchange-4.c
index ae52964..c0ec7fa 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-4.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-4.c
@@ -7,14 +7,14 @@ int foo(int N, int *res)
 {
   int i, j;
   double sum = 0;
-  for (i = 0; i < N; i++)	
+  for (i = 0; i < N; i++)
     for (j = 0; j < N; j++)
       sum = sum + u[i + 1335 * j];
-  
+
   for (i = 0; i < N; i++)
     u[1336 * i] *= 2;
   *res = sum + N;
 }
 
-/* { 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" } } */