graphite-dependences.c (reduction_ddr): New.

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

	* graphite-dependences.c (reduction_ddr): New.
	(graphite_legal_transform_bb): Call reduction_ddr.
	* graphite-poly.c (new_poly_bb): Pass a new bool parameter.
	Initialize PBB_IS_REDUCTION.
	* graphite-poly.h (struct poly_bb): New bool field is_reduction.
	(PBB_IS_REDUCTION): New.
	(new_poly_bb): Update declaration.
	* graphite-scop-detection.h (build_scop_bbs): Removed.
	(nb_reductions_in_loop): Removed.
	* graphite-sese-to-poly.c (try_generate_gimple_bb): Pass a sbitmap
	parameter for reductions.
	(try_generate_gimple_bb): Update call to new_poly_bb.
	(build_scop_bbs_1): Same.
	(build_scop_bbs): Same.
	(gsi_for_phi_node): New.
	(scalar_close_phi_node_p): Remove gcc_assert.
	(split_reduction_stmt): New.
	(is_reduction_operation_p): New.
	(phi_contains_arg): New.
	(follow_ssa_with_commutative_ops): New.
	(detect_commutative_reduction_arg): New.
	(detect_commutative_reduction_assign): New.
	(follow_inital_value_to_phi): New.
	(edge_initial_value_for_loop_phi): New.
	(initial_value_for_loop_phi): New.
	(detect_commutative_reduction): New.
	(translate_scalar_reduction_to_array_for_stmt): New.
	(insert_copyout): New.
	(insert_copyin): New.
	(translate_scalar_reduction_to_array): New.
	(rewrite_commutative_reductions_out_of_ssa_close_phi): New.
	(rewrite_commutative_reductions_out_of_ssa_loop): New.
	(rewrite_commutative_reductions_out_of_ssa): New.
	(build_poly_scop): Call rewrite_commutative_reductions_out_of_ssa.
	* sese.h (split_region_for_bb): New.

	* gcc.dg/graphite/graphite.exp (DEFAULT_CFLAGS_GRAPHITE_BLOCK): Add -ffast-math.
	* gcc.dg/graphite/interchange-1.c: Fix format.
	* gcc.dg/graphite/interchange-10.c: New.

From-SVN: r154561

9 files changed, 487 insertions, 20 deletions

diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 65d94fc..f8c3ff1 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,47 @@
 2009-10-05  Sebastian Pop  <sebastian.pop@amd.com>
 
+	* graphite-dependences.c (reduction_ddr): New.
+	(graphite_legal_transform_bb): Call reduction_ddr.
+	* graphite-poly.c (new_poly_bb): Pass a new bool parameter.
+	Initialize PBB_IS_REDUCTION.
+	* graphite-poly.h (struct poly_bb): New bool field is_reduction.
+	(PBB_IS_REDUCTION): New.
+	(new_poly_bb): Update declaration.
+	* graphite-scop-detection.h (build_scop_bbs): Removed.
+	(nb_reductions_in_loop): Removed.
+	* graphite-sese-to-poly.c (try_generate_gimple_bb): Pass a sbitmap
+	parameter for reductions.
+	(try_generate_gimple_bb): Update call to new_poly_bb.
+	(build_scop_bbs_1): Same.
+	(build_scop_bbs): Same.
+	(gsi_for_phi_node): New.
+	(scalar_close_phi_node_p): Remove gcc_assert.
+	(split_reduction_stmt): New.
+	(is_reduction_operation_p): New.
+	(phi_contains_arg): New.
+	(follow_ssa_with_commutative_ops): New.
+	(detect_commutative_reduction_arg): New.
+	(detect_commutative_reduction_assign): New.
+	(follow_inital_value_to_phi): New.
+	(edge_initial_value_for_loop_phi): New.
+	(initial_value_for_loop_phi): New.
+	(detect_commutative_reduction): New.
+	(translate_scalar_reduction_to_array_for_stmt): New.
+	(insert_copyout): New.
+	(insert_copyin): New.
+	(translate_scalar_reduction_to_array): New.
+	(rewrite_commutative_reductions_out_of_ssa_close_phi): New.
+	(rewrite_commutative_reductions_out_of_ssa_loop): New.
+	(rewrite_commutative_reductions_out_of_ssa): New.
+	(build_poly_scop): Call rewrite_commutative_reductions_out_of_ssa.
+	* sese.h (split_region_for_bb): New.
+
+	* gcc.dg/graphite/graphite.exp (DEFAULT_CFLAGS_GRAPHITE_BLOCK): Add -ffast-math.
+	* gcc.dg/graphite/interchange-1.c: Fix format.
+	* gcc.dg/graphite/interchange-10.c: New.
+
+2009-10-05  Sebastian Pop  <sebastian.pop@amd.com>
+
 	* graphite-sese-to-poly.c (insert_out_of_ssa_copy): Remove
 	buggy assert.
 
diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
index f7b8c73..2e777b3 100644
--- a/gcc/graphite-dependences.c
+++ b/gcc/graphite-dependences.c
@@ -585,6 +585,15 @@ graphite_legal_transform_dr (poly_bb_p pbb1, poly_bb_p pbb2,
   return is_empty_p;
 }
 
+/* Return true when the data dependence relation for PBB1 and PBB2 is
+   part of a reduction.  */
+
+static inline bool
+reduction_ddr (poly_bb_p pbb1, poly_bb_p pbb2)
+{
+  return pbb1 == pbb2 && PBB_IS_REDUCTION (pbb1);
+}
+
 /* Iterates over the data references of PBB1 and PBB2 and detect
    whether the transformed schedule is correct.  */
 
@@ -600,6 +609,9 @@ 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))
+    return true;
+
   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
     for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
       if (!graphite_legal_transform_dr (pbb1, pbb2, pdr1, pdr2))
diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c
index 142d3ed..e97b0a8 100644
--- a/gcc/graphite-poly.c
+++ b/gcc/graphite-poly.c
@@ -337,7 +337,7 @@ free_poly_dr (poly_dr_p pdr)
 /* Create a new polyhedral black box.  */
 
 void
-new_poly_bb (scop_p scop, void *black_box)
+new_poly_bb (scop_p scop, void *black_box, bool reduction)
 {
   poly_bb_p pbb = XNEW (struct poly_bb);
 
@@ -348,6 +348,7 @@ new_poly_bb (scop_p scop, void *black_box)
   PBB_SAVED (pbb) = NULL;
   PBB_ORIGINAL (pbb) = NULL;
   PBB_DRS (pbb) = VEC_alloc (poly_dr_p, heap, 3);
+  PBB_IS_REDUCTION (pbb) = reduction;
   VEC_safe_push (poly_bb_p, heap, SCOP_BBS (scop), pbb);
 }
 
diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h
index 955f12f..c397f6a 100644
--- a/gcc/graphite-poly.h
+++ b/gcc/graphite-poly.h
@@ -306,6 +306,9 @@ struct poly_bb
 
   /* True when the PDR duplicates have already been removed.  */
   bool pdr_duplicates_removed;
+
+  /* True when this PBB contains only a reduction statement.  */
+  bool is_reduction;
 };
 
 #define PBB_BLACK_BOX(PBB) ((gimple_bb_p) PBB->black_box)
@@ -320,8 +323,9 @@ struct poly_bb
 #define PBB_NB_LOCAL_VARIABLES(PBB) (PBB->transformed->nb_local_variables)
 #define PBB_NB_SCATTERING_TRANSFORM(PBB) (PBB->transformed->nb_scattering)
 #define PBB_PDR_DUPLICATES_REMOVED(PBB) (PBB->pdr_duplicates_removed)
+#define PBB_IS_REDUCTION(PBB) (PBB->is_reduction)
 
-extern void new_poly_bb (scop_p, void *);
+extern void new_poly_bb (scop_p, void *, bool);
 extern void free_poly_bb (poly_bb_p);
 extern void debug_loop_vec (poly_bb_p);
 extern void schedule_to_scattering (poly_bb_p, int);
diff --git a/gcc/graphite-scop-detection.h b/gcc/graphite-scop-detection.h
index 740816d..44c2223 100644
--- a/gcc/graphite-scop-detection.h
+++ b/gcc/graphite-scop-detection.h
@@ -21,7 +21,5 @@ along with GCC; see the file COPYING3.  If not see
 
 
 extern void build_scops (VEC (scop_p, heap) **);
-extern void build_scop_bbs (scop_p);
-extern int nb_reductions_in_loop (loop_p);
 extern void dot_all_scops (VEC (scop_p, heap) *);
 extern void dot_scop (scop_p);
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 22b412b..56f89cc 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -346,7 +346,7 @@ free_scops (VEC (scop_p, heap) *scops)
    information.  */
 
 static void
-try_generate_gimple_bb (scop_p scop, basic_block bb)
+try_generate_gimple_bb (scop_p scop, basic_block bb, sbitmap reductions)
 {
   VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
   loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
@@ -362,7 +362,8 @@ try_generate_gimple_bb (scop_p scop, basic_block bb)
   if (!graphite_stmt_p (SCOP_REGION (scop), bb, drs))
     free_data_refs (drs);
   else
-    new_poly_bb (scop, new_gimple_bb (bb, drs));
+    new_poly_bb (scop, new_gimple_bb (bb, drs), TEST_BIT (reductions,
+							  bb->index));
 }
 
 /* Returns true if all predecessors of BB, that are not dominated by BB, are
@@ -417,7 +418,7 @@ graphite_sort_dominated_info (VEC (basic_block, heap) *dom)
 /* Recursive helper function for build_scops_bbs.  */
 
 static void
-build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb)
+build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb, sbitmap reductions)
 {
   sese region = SCOP_REGION (scop);
   VEC (basic_block, heap) *dom;
@@ -426,7 +427,7 @@ build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb)
       || !bb_in_sese_p (bb, region))
     return;
 
-  try_generate_gimple_bb (scop, bb);
+  try_generate_gimple_bb (scop, bb, reductions);
   SET_BIT (visited, bb->index);
 
   dom = get_dominated_by (CDI_DOMINATORS, bb);
@@ -444,7 +445,7 @@ build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb)
       for (i = 0; VEC_iterate (basic_block, dom, i, dom_bb); i++)
 	if (all_non_dominated_preds_marked_p (dom_bb, visited))
 	  {
-	    build_scop_bbs_1 (scop, visited, dom_bb);
+	    build_scop_bbs_1 (scop, visited, dom_bb, reductions);
 	    VEC_unordered_remove (basic_block, dom, i);
 	    break;
 	  }
@@ -455,15 +456,14 @@ build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb)
 
 /* Gather the basic blocks belonging to the SCOP.  */
 
-void
-build_scop_bbs (scop_p scop)
+static void
+build_scop_bbs (scop_p scop, sbitmap reductions)
 {
   sbitmap visited = sbitmap_alloc (last_basic_block);
   sese region = SCOP_REGION (scop);
 
   sbitmap_zero (visited);
-  build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region));
-
+  build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region), reductions);
   sbitmap_free (visited);
 }
 
@@ -1857,6 +1857,22 @@ build_scop_drs (scop_p scop)
     build_pbb_drs (pbb);
 }
 
+/* Return a gsi at the position of the phi node STMT.  */
+
+static gimple_stmt_iterator
+gsi_for_phi_node (gimple stmt)
+{
+  gimple_stmt_iterator psi;
+  basic_block bb = gimple_bb (stmt);
+
+  for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
+    if (stmt == gsi_stmt (psi))
+      return psi;
+
+  gcc_unreachable ();
+  return psi;
+}
+
 /* Insert the assignment "RES := VAR" just after the definition of VAR.  */
 
 static void
@@ -1927,9 +1943,8 @@ create_zero_dim_array (tree var)
 static bool
 scalar_close_phi_node_p (gimple phi)
 {
-  gcc_assert (gimple_code (phi) == GIMPLE_PHI);
-
-  if (!is_gimple_reg (gimple_phi_result (phi)))
+  if (gimple_code (phi) != GIMPLE_PHI
+      || !is_gimple_reg (gimple_phi_result (phi)))
     return false;
 
   return (gimple_phi_num_args (phi) == 1);
@@ -2198,14 +2213,382 @@ nb_pbbs_in_loops (scop_p scop)
   return res;
 }
 
+/* Splits STMT out of its current BB.  */
+
+static basic_block
+split_reduction_stmt (gimple stmt)
+{
+  gimple_stmt_iterator gsi;
+  basic_block bb = gimple_bb (stmt);
+  edge e;
+
+  split_block (bb, stmt);
+
+  gsi = gsi_last_bb (bb);
+  gsi_prev (&gsi);
+  e = split_block (bb, gsi_stmt (gsi));
+
+  return e->dest;
+}
+
+/* Return true when stmt is a reduction operation.  */
+
+static inline bool
+is_reduction_operation_p (gimple stmt)
+{
+  return flag_associative_math
+    && commutative_tree_code (gimple_assign_rhs_code (stmt))
+    && associative_tree_code (gimple_assign_rhs_code (stmt));
+}
+
+/* Returns true when PHI contains an argument ARG.  */
+
+static bool
+phi_contains_arg (gimple phi, tree arg)
+{
+  size_t i;
+
+  for (i = 0; i < gimple_phi_num_args (phi); i++)
+    if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
+      return true;
+
+  return false;
+}
+
+/* Return a loop phi node that corresponds to a reduction containing LHS.  */
+
+static gimple
+follow_ssa_with_commutative_ops (tree arg, tree lhs)
+{
+  gimple stmt;
+
+  if (TREE_CODE (arg) != SSA_NAME)
+    return NULL;
+
+  stmt = SSA_NAME_DEF_STMT (arg);
+
+  if (gimple_code (stmt) == GIMPLE_PHI)
+    {
+      if (phi_contains_arg (stmt, lhs))
+	return stmt;
+      return NULL;
+    }
+
+  if (gimple_num_ops (stmt) == 2)
+    return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
+
+  if (is_reduction_operation_p (stmt))
+    {
+      gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
+
+      return res ? res :
+	follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
+    }
+
+  return NULL;
+}
+
+/* Detect commutative and associative scalar reductions starting at
+   the STMT.  */
+
+static gimple
+detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
+				  VEC (gimple, heap) **in,
+				  VEC (gimple, heap) **out)
+{
+  gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
+
+  if (phi)
+    {
+      VEC_safe_push (gimple, heap, *in, stmt);
+      VEC_safe_push (gimple, heap, *out, stmt);
+      return phi;
+    }
+
+  return NULL;
+}
+
+/* Detect commutative and associative scalar reductions starting at
+   the STMT.  */
+
+static gimple
+detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
+				     VEC (gimple, heap) **out)
+{
+  tree lhs = gimple_assign_lhs (stmt);
+
+  if (gimple_num_ops (stmt) == 2)
+    return detect_commutative_reduction_arg (lhs, stmt,
+					     gimple_assign_rhs1 (stmt),
+					     in, out);
+
+  if (is_reduction_operation_p (stmt))
+    {
+      gimple res = detect_commutative_reduction_arg (lhs, stmt,
+						     gimple_assign_rhs1 (stmt),
+						     in, out);
+      return res ? res
+	: detect_commutative_reduction_arg (lhs, stmt,
+					    gimple_assign_rhs2 (stmt),
+					    in, out);
+    }
+
+  return NULL;
+}
+
+/* Return a loop phi node that corresponds to a reduction containing LHS.  */
+
+static gimple
+follow_inital_value_to_phi (tree arg, tree lhs)
+{
+  gimple stmt;
+
+  if (!arg || TREE_CODE (arg) != SSA_NAME)
+    return NULL;
+
+  stmt = SSA_NAME_DEF_STMT (arg);
+
+  if (gimple_code (stmt) == GIMPLE_PHI
+      && phi_contains_arg (stmt, lhs))
+    return stmt;
+
+  return NULL;
+}
+
+
+/* Return the argument of the loop PHI that is the inital value coming
+   from outside the loop.  */
+
+static edge
+edge_initial_value_for_loop_phi (gimple phi)
+{
+  size_t i;
+
+  for (i = 0; i < gimple_phi_num_args (phi); i++)
+    {
+      edge e = gimple_phi_arg_edge (phi, i);
+
+      if (loop_depth (e->src->loop_father)
+	  < loop_depth (e->dest->loop_father))
+	return e;
+    }
+
+  return NULL;
+}
+
+/* Return the argument of the loop PHI that is the inital value coming
+   from outside the loop.  */
+
+static tree
+initial_value_for_loop_phi (gimple phi)
+{
+  size_t i;
+
+  for (i = 0; i < gimple_phi_num_args (phi); i++)
+    {
+      edge e = gimple_phi_arg_edge (phi, i);
+
+      if (loop_depth (e->src->loop_father)
+	  < loop_depth (e->dest->loop_father))
+	return gimple_phi_arg_def (phi, i);
+    }
+
+  return NULL_TREE;
+}
+
+/* Detect commutative and associative scalar reductions starting at
+   the loop closed phi node CLOSE_PHI.  */
+
+static gimple
+detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in,
+			      VEC (gimple, heap) **out)
+{
+  if (scalar_close_phi_node_p (stmt))
+    {
+      tree arg = gimple_phi_arg_def (stmt, 0);
+      gimple def = SSA_NAME_DEF_STMT (arg);
+      gimple loop_phi = detect_commutative_reduction (def, in, out);
+
+      if (loop_phi)
+	{
+	  tree lhs = gimple_phi_result (stmt);
+	  tree init = initial_value_for_loop_phi (loop_phi);
+	  gimple phi = follow_inital_value_to_phi (init, lhs);
+
+	  VEC_safe_push (gimple, heap, *in, loop_phi);
+	  VEC_safe_push (gimple, heap, *out, stmt);
+	  return phi;
+	}
+      else
+	return NULL;
+    }
+
+  if (gimple_code (stmt) == GIMPLE_ASSIGN)
+    return detect_commutative_reduction_assign (stmt, in, out);
+
+  return NULL;
+}
+
+/* Translate the scalar reduction statement STMT to an array RED
+   knowing that its recursive phi node is LOOP_PHI.  */
+
+static void
+translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt,
+					      gimple loop_phi)
+{
+  basic_block bb = gimple_bb (stmt);
+  gimple_stmt_iterator insert_gsi = gsi_after_labels (bb);
+  tree res = gimple_phi_result (loop_phi);
+  gimple assign = gimple_build_assign (res, red);
+
+  gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
+
+  assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
+  insert_gsi = gsi_last_bb (bb);
+  gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT);
+}
+
+/* Insert the assignment "result (CLOSE_PHI) = RED".  */
+
+static void
+insert_copyout (tree red, gimple close_phi)
+{
+  tree res = gimple_phi_result (close_phi);
+  basic_block bb = gimple_bb (close_phi);
+  gimple_stmt_iterator insert_gsi = gsi_after_labels (bb);
+  gimple assign = gimple_build_assign (res, red);
+
+  gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
+}
+
+/* Insert the assignment "RED = initial_value (LOOP_PHI)".  */
+
+static void
+insert_copyin (tree red, gimple loop_phi)
+{
+  gimple_seq stmts;
+  tree init = initial_value_for_loop_phi (loop_phi);
+  edge e = edge_initial_value_for_loop_phi (loop_phi);
+  basic_block bb = e->src;
+  gimple_stmt_iterator insert_gsi = gsi_last_bb (bb);
+  tree expr = build2 (MODIFY_EXPR, TREE_TYPE (init), red, init);
+
+  force_gimple_operand (expr, &stmts, true, NULL);
+  gsi_insert_seq_before (&insert_gsi, stmts, GSI_SAME_STMT);
+}
+
+/* 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:
+
+   IN: stmt, loop_n, ..., loop_0
+   OUT: stmt, close_n, ..., close_0
+
+   the first element is the reduction statement, and the next elements
+   are the loop and close phi nodes of each of the outer loops.  */
+
+static void
+translate_scalar_reduction_to_array (VEC (gimple, heap) *in,
+				     VEC (gimple, heap) *out,
+				     sbitmap reductions)
+{
+  unsigned int i;
+  gimple loop_phi;
+  tree red;
+  gimple_stmt_iterator gsi;
+
+  for (i = 0; VEC_iterate (gimple, in, i, loop_phi); i++)
+    {
+      gimple close_phi = VEC_index (gimple, out, i);
+
+      if (i == 0)
+	{
+	  gimple stmt = loop_phi;
+	  basic_block bb = split_reduction_stmt (stmt);
+
+	  SET_BIT (reductions, bb->index);
+	  gcc_assert (close_phi == loop_phi);
+
+	  red = create_zero_dim_array (gimple_assign_lhs (stmt));
+	  translate_scalar_reduction_to_array_for_stmt
+	    (red, stmt, VEC_index (gimple, in, 1));
+	  continue;
+	}
+
+      if (i == VEC_length (gimple, in) - 1)
+	{
+	  insert_copyout (red, close_phi);
+	  insert_copyin (red, loop_phi);
+	}
+
+      gsi = gsi_for_phi_node (loop_phi);
+      remove_phi_node (&gsi, false);
+
+      gsi = gsi_for_phi_node (close_phi);
+      remove_phi_node (&gsi, false);
+    }
+}
+
+/* Rewrites out of SSA a commutative reduction at CLOSE_PHI.  */
+
+static void
+rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi,
+						     sbitmap reductions)
+{
+  VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
+  VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
+
+  detect_commutative_reduction (close_phi, &in, &out);
+  if (VEC_length (gimple, in) > 0)
+    translate_scalar_reduction_to_array (in, out, reductions);
+
+  VEC_free (gimple, heap, in);
+  VEC_free (gimple, heap, out);
+}
+
+/* Rewrites all the commutative reductions from LOOP out of SSA.  */
+
+static void
+rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop,
+						sbitmap reductions)
+{
+  gimple_stmt_iterator gsi;
+  edge exit = single_exit (loop);
+
+  if (!exit)
+    return;
+
+  for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
+    rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi),
+							 reductions);
+}
+
+/* Rewrites all the commutative reductions from SCOP out of SSA.  */
+
+static void
+rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions)
+{
+  loop_iterator li;
+  loop_p loop;
+
+  FOR_EACH_LOOP (li, loop, 0)
+    if (loop_in_sese_p (loop, region))
+      rewrite_commutative_reductions_out_of_ssa_loop (loop, reductions);
+}
+
 /* Builds the polyhedral representation for a SESE region.  */
 
 bool
 build_poly_scop (scop_p scop)
 {
   sese region = SCOP_REGION (scop);
+  sbitmap reductions = sbitmap_alloc (last_basic_block * 2);
+
+  sbitmap_zero (reductions);
+  rewrite_commutative_reductions_out_of_ssa (region, reductions);
   rewrite_reductions_out_of_ssa (scop);
-  build_scop_bbs (scop);
+  build_scop_bbs (scop, reductions);
+  sbitmap_free (reductions);
 
   /* FIXME: This restriction is needed to avoid a problem in CLooG.
      Once CLooG is fixed, remove this guard.  Anyways, it makes no
diff --git a/gcc/sese.h b/gcc/sese.h
index ace63ba..ca167f5 100644
--- a/gcc/sese.h
+++ b/gcc/sese.h
@@ -188,6 +188,33 @@ sese_loop_depth (sese region, loop_p loop)
   return depth;
 }
 
+/* Splits BB to make a single entry single exit region.  */
+
+static inline sese
+split_region_for_bb (basic_block bb)
+{
+  edge entry, exit;
+
+  if (single_pred_p (bb))
+    entry = single_pred_edge (bb);
+  else
+    {
+      entry = split_block_after_labels (bb);
+      bb = single_succ (bb);
+    }
+
+  if (single_succ_p (bb))
+    exit = single_succ_edge (bb);
+  else
+    {
+      gimple_stmt_iterator gsi = gsi_last_bb (bb);
+      gsi_prev (&gsi);
+      exit = split_block (bb, gsi_stmt (gsi));
+    }
+
+  return new_sese (entry, exit);
+}
+
 /* Returns the block preceding the entry of a SESE.  */
 
 static inline basic_block
diff --git a/gcc/testsuite/gcc.dg/graphite/graphite.exp b/gcc/testsuite/gcc.dg/graphite/graphite.exp
index 57fb74c..ae0fa16 100644
--- a/gcc/testsuite/gcc.dg/graphite/graphite.exp
+++ b/gcc/testsuite/gcc.dg/graphite/graphite.exp
@@ -55,7 +55,7 @@ dg-runtest $id_files "" $DEFAULT_CFLAGS_GRAPHITE_IDENTITY
 foreach id_file $id_files {lremove wait_to_run_files $id_file}
 
 # Flags using for interchange-* files.
-set DEFAULT_CFLAGS_GRAPHITE_BLOCK "-O2 -fdump-tree-graphite-all -floop-interchange"
+set DEFAULT_CFLAGS_GRAPHITE_BLOCK "-O2 -fdump-tree-graphite-all -floop-interchange -ffast-math"
 set interchange_files [lsort [glob -nocomplain $srcdir/$subdir/interchange-*.c ] ]
 dg-runtest $interchange_files "" $DEFAULT_CFLAGS_GRAPHITE_BLOCK
 foreach interchange_file $interchange_files {lremove wait_to_run_files $interchange_file}
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-1.c b/gcc/testsuite/gcc.dg/graphite/interchange-1.c
index 339698a..cd9197d 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-1.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-1.c
@@ -12,11 +12,11 @@ int foo(int N, int *res)
     {
       for (j = 0; j < N; j++)
 	sum = sum + u[i + 1335 * j];
-      
+
       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" { xfail *-*-* } } } */
 /* { dg-final { cleanup-tree-dump "graphite" } } */