Preserve the original program while using graphite.

Earlier, graphite used to translate portions of the original program after
scop-detection in order to represent the SCoP into polyhedral model.  This was
required because each basic block was represented as independent basic block in
the polyhedral model. So all the cross-basic-block dependencies were translated
out-of-ssa.

With this patch those dependencies are also exposed to the ISL, so there is no
need to modify the original structure of the program.

After this patch we should be able to enable graphite at some default
optimization level.

Highlights:
Remove cross bb scalar to array translation
For reductions, add support for more than just INT_CST
Early bailout on codegen.
Verify loop-closed ssa structure during copy of renames
The uses of exprs should come from bb which dominates the bb
Collect the init value of close phi in loop-guard
Do not follow vuses for close-phi, postpone loop-close phi until the
    corresponding loop-phi is processed
Bail out if no bb found to place cond/loop -phis
Move insertion of liveouts at the end of codegen
Insert loop-phis in the loop-header.

This patch passes regtest and bootstrap with BOOT_CFLAGS='-O2 -fgraphite-identity -floop-nest-optimize'

2015-11-11  Aditya Kumar  <aditya.k7@samsung.com>
      Sebastian Pop  <s.pop@samsung.com>

	* graphite-isl-ast-to-gimple.c (class translate_isl_ast_to_gimple):
	  New member codegen_error
	(translate_isl_ast_for_loop): Remove call to single_succ_edge and early return.
	(translate_isl_ast_node_user): Early return in case of error.
	(translate_isl_ast_to_gimple::translate_isl_ast): Same.
	(translate_isl_ast_to_gimple::translate_pending_phi_nodes): New.
	(add_parameters_to_ivs_params): Remove macro.
	(graphite_regenerate_ast_isl): Add if_region pointer to region.
	* graphite-poly.c (new_poly_dr): Remove macro.
	(print_pdr): Same.
	(new_gimple_poly_bb): Same.
	(free_gimple_poly_bb): Same.
	(print_scop_params): Same.
	* graphite-poly.h (struct poly_dr): Same.
	(struct poly_bb): Add new_bb.
	(gbb_from_bb): Remove dead code.
	(pbb_from_bb): Same.
	* graphite-scop-detection.c (parameter_index_in_region_1): Same.
	(parameter_index_in_region): Same.
	(find_scop_parameters): Same.
	(build_cross_bb_scalars_def): New.
	(build_cross_bb_scalars_use): New.
	(graphite_find_cross_bb_scalar_vars): New
	(try_generate_gimple_bb): Reads and Writes.
	(build_alias_set): Move.
	(gather_bbs::before_dom_children): Gather bbs visited.
	(build_scops): call build_alias_set.
	* graphite-sese-to-poly.c (phi_arg_in_outermost_loop): Delete.
	(remove_simple_copy_phi): Delete.
	(remove_invariant_phi): Delete.
	(simple_copy_phi_p): Delete.
	(reduction_phi_p): Delete.
	(isl_id_for_dr): Remove unused param.
	(parameter_index_in_region_1): Remove macro usage.
	(set_scop_parameter_dim): Same.
	(add_param_constraints): Same.
	(add_conditions_to_constraints): Same
	(build_scop_iteration_domain): Same.
	(pdr_add_alias_set): Comment.
	(add_scalar_version_numbers): New.
	(build_poly_dr): ISL id.
	(build_scop_drs): Move.
	(build_poly_sr_1): Same.
	(insert_stmts): Remove.
	(build_poly_sr): New.
	(new_pbb_from_pbb): Delete.
	(insert_out_of_ssa_copy_on_edge): Delete.
	(create_zero_dim_array): Delete.
	(scalar_close_phi_node_p): Delete.
	(propagate_expr_outside_region): Delete.
	(rewrite_close_phi_out_of_ssa): Delete.
	(rewrite_phi_out_of_ssa): Delete.
	(rewrite_degenerate_phi): Delete.
	(rewrite_reductions_out_of_ssa): Delete.
	(rewrite_cross_bb_scalar_dependence): Delete.
	(handle_scalar_deps_crossing_scop_limits):
	(rewrite_cross_bb_scalar_deps): Delete.
	(build_poly_scop): Remove calls to out-of-ssa functions.
	* graphite.c (graphite_transform_loops): Early return in case of codegen error.
	* sese.c (debug_rename_map_1): Delete.
	(debug_rename_map): Delete.
	(sese_record_loop): Remove macro.
	(build_sese_loop_nests): Same.
	(new_sese_info): Same.
	(free_sese_info): Same.
	(sese_insert_phis_for_liveouts):
	(is_loop_closed_ssa_use): New.
	(number_of_phi_nodes): New.
	(bb_contains_loop_close_phi_nodes): New.
	(bb_contains_loop_phi_nodes): New.
	(phi_uses_name): New.
	(is_valid_rename):
	(get_rename): Add old_bb and loop_phi for more precise matching of
	exprs.
	(set_rename): Pass region.
	(later_of_the_two): New.
	(gsi_insert_earliest): New.
	(collect_all_ssa_names): New.
	(substitute_ssa_name): New.
	(rename_all_uses): New.
	(get_rename_from_scev): New.
	(rename_uses): Pass old_bb for more precise matching of exprs.
	(get_def_bb_for_const): New.
	(get_new_name): New.
	(get_loc): New.
	(get_edges): New.
	(copy_loop_phi_args): New.
	(copy_loop_phi_nodes): New.
	(get_loop_init_value): New.
	(find_init_value): New.
	(find_init_value_close_phi): New.
	(copy_loop_close_phi_args): New.
	(copy_loop_close_phi_nodes): New.
	(add_phi_arg_for_new_expr): New.
	(copy_cond_phi_args): New.
	(copy_cond_phi_nodes): New.
	(copy_phi_nodes): New.
	(should_copy_to_new_region): New.
	(set_rename_for_each_def): New.
	(graphite_copy_stmts_from_block): Early return in case of error.
	(copy_bb_and_scalar_dependences): Same.
	* sese.h (vec_find): New.
	(SESE_PARAMS): Delete.
	(SESE_LOOPS): Delete.
	(SESE_LOOP_NEST): Delete.
	(sese_contains_loop): Remove macro usage.
	(sese_nb_params): Same.
	(struct gimple_poly_bb): Added read_scalar_refs, write_scalar_refs.

Co-Authored-By: Sebastian Pop <s.pop@samsung.com>

From-SVN: r230200

9 files changed, 1953 insertions, 950 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index efbd38f..fcf0bf6 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,117 @@
+2015-11-11  Aditya Kumar  <aditya.k7@samsung.com>
+	    Sebastian Pop  <s.pop@samsung.com>
+
+	* graphite-isl-ast-to-gimple.c (class translate_isl_ast_to_gimple):
+	New member codegen_error
+	(translate_isl_ast_for_loop): Remove call to single_succ_edge and
+	early return.
+	(translate_isl_ast_node_user): Early return in case of error.
+	(translate_isl_ast_to_gimple::translate_isl_ast): Same.
+	(translate_isl_ast_to_gimple::translate_pending_phi_nodes): New.
+	(add_parameters_to_ivs_params): Remove macro.
+	(graphite_regenerate_ast_isl): Add if_region pointer to region.
+	* graphite-poly.c (new_poly_dr): Remove macro.
+	(print_pdr): Same.
+	(new_gimple_poly_bb): Same.
+	(free_gimple_poly_bb): Same.
+	(print_scop_params): Same.
+	* graphite-poly.h (struct poly_dr): Same.
+	(struct poly_bb): Add new_bb.
+	(gbb_from_bb): Remove dead code.
+	(pbb_from_bb): Same.
+	* graphite-scop-detection.c (parameter_index_in_region_1): Same.
+	(parameter_index_in_region): Same.
+	(find_scop_parameters): Same.
+	(build_cross_bb_scalars_def): New.
+	(build_cross_bb_scalars_use): New.
+	(graphite_find_cross_bb_scalar_vars): New
+	(try_generate_gimple_bb): Reads and Writes.
+	(build_alias_set): Move.
+	(gather_bbs::before_dom_children): Gather bbs visited.
+	(build_scops): call build_alias_set.
+	* graphite-sese-to-poly.c (phi_arg_in_outermost_loop): Delete.
+	(remove_simple_copy_phi): Delete.
+	(remove_invariant_phi): Delete.
+	(simple_copy_phi_p): Delete.
+	(reduction_phi_p): Delete.
+	(isl_id_for_dr): Remove unused param.
+	(parameter_index_in_region_1): Remove macro usage.
+	(set_scop_parameter_dim): Same.
+	(add_param_constraints): Same.
+	(add_conditions_to_constraints): Same
+	(build_scop_iteration_domain): Same.
+	(pdr_add_alias_set): Comment.
+	(add_scalar_version_numbers): New.
+	(build_poly_dr): ISL id.
+	(build_scop_drs): Move.
+	(build_poly_sr_1): Same.
+	(insert_stmts): Remove.
+	(build_poly_sr): New.
+	(new_pbb_from_pbb): Delete.
+	(insert_out_of_ssa_copy_on_edge): Delete.
+	(create_zero_dim_array): Delete.
+	(scalar_close_phi_node_p): Delete.
+	(propagate_expr_outside_region): Delete.
+	(rewrite_close_phi_out_of_ssa): Delete.
+	(rewrite_phi_out_of_ssa): Delete.
+	(rewrite_degenerate_phi): Delete.
+	(rewrite_reductions_out_of_ssa): Delete.
+	(rewrite_cross_bb_scalar_dependence): Delete.
+	(handle_scalar_deps_crossing_scop_limits):
+	(rewrite_cross_bb_scalar_deps): Delete.
+	(build_poly_scop): Remove calls to out-of-ssa functions.
+	* graphite.c (graphite_transform_loops): Early return in case of
+	codegen error.
+	* sese.c (debug_rename_map_1): Delete.
+	(debug_rename_map): Delete.
+	(sese_record_loop): Remove macro.
+	(build_sese_loop_nests): Same.
+	(new_sese_info): Same.
+	(free_sese_info): Same.
+	(sese_insert_phis_for_liveouts):
+	(is_loop_closed_ssa_use): New.
+	(number_of_phi_nodes): New.
+	(bb_contains_loop_close_phi_nodes): New.
+	(bb_contains_loop_phi_nodes): New.
+	(phi_uses_name): New.
+	(is_valid_rename):
+	(get_rename): Add old_bb and loop_phi for more precise matching of
+	exprs.
+	(set_rename): Pass region.
+	(later_of_the_two): New.
+	(gsi_insert_earliest): New.
+	(collect_all_ssa_names): New.
+	(substitute_ssa_name): New.
+	(rename_all_uses): New.
+	(get_rename_from_scev): New.
+	(rename_uses): Pass old_bb for more precise matching of exprs.
+	(get_def_bb_for_const): New.
+	(get_new_name): New.
+	(get_loc): New.
+	(get_edges): New.
+	(copy_loop_phi_args): New.
+	(copy_loop_phi_nodes): New.
+	(get_loop_init_value): New.
+	(find_init_value): New.
+	(find_init_value_close_phi): New.
+	(copy_loop_close_phi_args): New.
+	(copy_loop_close_phi_nodes): New.
+	(add_phi_arg_for_new_expr): New.
+	(copy_cond_phi_args): New.
+	(copy_cond_phi_nodes): New.
+	(copy_phi_nodes): New.
+	(should_copy_to_new_region): New.
+	(set_rename_for_each_def): New.
+	(graphite_copy_stmts_from_block): Early return in case of error.
+	(copy_bb_and_scalar_dependences): Same.
+	* sese.h (vec_find): New.
+	(SESE_PARAMS): Delete.
+	(SESE_LOOPS): Delete.
+	(SESE_LOOP_NEST): Delete.
+	(sese_contains_loop): Remove macro usage.
+	(sese_nb_params): Same.
+	(struct gimple_poly_bb): Added read_scalar_refs, write_scalar_refs.
+
 2015-11-11  Abderrazek Zaafrani  <a.zaafrani@samsung.com>
 
 	* graphite-sese-to-poly.c (build_scop_original_schedule): Call
diff --git a/gcc/graphite-isl-ast-to-gimple.c b/gcc/graphite-isl-ast-to-gimple.c
index 628fc90..7fa4ce3 100644
--- a/gcc/graphite-isl-ast-to-gimple.c
+++ b/gcc/graphite-isl-ast-to-gimple.c
@@ -63,11 +63,7 @@ extern "C" {
 #include <map>
 #include "graphite-isl-ast-to-gimple.h"
 #include "tree-cfg.h"
-
-/* This flag is set when an error occurred during the translation of
-   ISL AST to Gimple.  */
-
-static bool graphite_regenerate_error;
+#include "gimple-pretty-print.h"
 
 /* We always try to use signed 128 bit types, but fall back to smaller types
    in case a platform does not provide types of these sizes. In the future we
@@ -132,7 +128,7 @@ class translate_isl_ast_to_gimple
 {
  public:
   translate_isl_ast_to_gimple (sese_info_p r)
-    : region (r)
+    : region (r), codegen_error (false)
   { }
 
   /* Translates an ISL AST node NODE to GCC representation in the
@@ -261,8 +257,17 @@ class translate_isl_ast_to_gimple
   void build_iv_mapping (vec<tree> iv_map, gimple_poly_bb_p gbb,
 			 __isl_keep isl_ast_expr *user_expr, ivs_params &ip,
 			 sese_l &region);
+
+  void translate_pending_phi_nodes (void);
+
+  bool codegen_error_p () { return codegen_error; }
+
 private:
   sese_info_p region;
+
+  /* This flag is set when an error occurred during the translation of ISL AST
+     to Gimple.  */
+  bool codegen_error;
 };
 
 /* Return the tree variable that corresponds to the given isl ast identifier
@@ -575,13 +580,15 @@ translate_isl_ast_for_loop (loop_p context_loop,
   edge to_body = single_succ_edge (loop->header);
   basic_block after = to_body->dest;
 
-  /* Create a basic block for loop close phi nodes.  */
-  last_e = single_succ_edge (split_edge (last_e));
-
   /* Translate the body of the loop.  */
   isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
   next_e = translate_isl_ast (loop, for_body, to_body, ip);
   isl_ast_node_free (for_body);
+
+  /* Early return if we failed to translate loop body.  */
+  if (!next_e || codegen_error)
+    return NULL;
+
   redirect_edge_succ_nodup (next_e, after);
   set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
 
@@ -770,14 +777,17 @@ translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
 			     edge next_e, ivs_params &ip)
 {
   gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user);
+
   isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node);
   isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0);
   gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id);
+
   isl_id *name_id = isl_ast_expr_get_id (name_expr);
   poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id);
   gcc_assert (pbb);
+
   gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
-  vec<tree> iv_map;
+
   isl_ast_expr_free (name_expr);
   isl_id_free (name_id);
 
@@ -785,6 +795,7 @@ translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
 	      "The entry block should not even appear within a scop");
 
   int nb_loops = number_of_loops (cfun);
+  vec<tree> iv_map;
   iv_map.create (nb_loops);
   iv_map.safe_grow_cleared (nb_loops);
 
@@ -793,23 +804,35 @@ translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
 
   if (dump_file)
     {
-      fprintf (dump_file, "[codegen] copying");
+      fprintf (dump_file, "[codegen] copying from basic block\n");
       print_loops_bb (dump_file, GBB_BB (gbb), 0, 3);
+      fprintf (dump_file, "\n[codegen] to new basic block\n");
+      print_loops_bb (dump_file, next_e->src, 0, 3);
     }
 
   next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb),
 					   pbb->scop->scop_info, next_e,
 					   iv_map,
-					   &graphite_regenerate_error);
+					   &codegen_error);
+  if (codegen_error)
+    return NULL;
+
   if (dump_file)
     {
-      fprintf (dump_file, "[codegen] to");
+      fprintf (dump_file, "\n[codegen] (after copy) new basic block\n");
       print_loops_bb (dump_file, next_e->src, 0, 3);
     }
 
   iv_map.release ();
   mark_virtual_operands_for_renaming (cfun);
   update_ssa (TODO_update_ssa);
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "\n[codegen] (after update SSA) new basic block\n");
+      print_loops_bb (dump_file, next_e->src, 0, 3);
+    }
+
   return next_e;
 }
 
@@ -881,6 +904,9 @@ translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop,
 						__isl_keep isl_ast_node *node,
 						edge next_e, ivs_params &ip)
 {
+  if (codegen_error)
+    return NULL;
+
   switch (isl_ast_node_get_type (node))
     {
     case isl_ast_node_error:
@@ -906,6 +932,47 @@ translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop,
     }
 }
 
+/* Patch the missing arguments of the phi nodes.  */
+
+void
+translate_isl_ast_to_gimple::translate_pending_phi_nodes ()
+{
+  int i;
+  phi_rename *rename;
+  FOR_EACH_VEC_ELT (region->incomplete_phis, i, rename)
+    {
+      gphi *old_phi = rename->first;
+      gphi *new_phi = rename->second;
+      basic_block old_bb = gimple_bb (old_phi);
+      basic_block new_bb = gimple_bb (new_phi);
+
+      /* First edge is the init edge and second is the back edge.  */
+      init_back_edge_pair_t ibp_old_bb = get_edges (old_bb);
+      init_back_edge_pair_t ibp_new_bb = get_edges (new_bb);
+
+      if (dump_file)
+	{
+	  fprintf (dump_file, "\n[codegen] translating pending old-phi: ");
+	  print_gimple_stmt (dump_file, old_phi, 0, 0);
+	}
+
+      auto_vec <tree, 1> iv_map;
+      if (bb_contains_loop_phi_nodes (new_bb))
+	copy_loop_phi_args (old_phi, ibp_old_bb, new_phi,
+			    ibp_new_bb, region, false);
+      else if (bb_contains_loop_close_phi_nodes (new_bb))
+	copy_loop_close_phi_args (old_bb, new_bb, region, false);
+      else if (!copy_cond_phi_args (old_phi, new_phi, iv_map, region, false))
+	gcc_unreachable ();
+
+      if (dump_file)
+	{
+	  fprintf (dump_file, "[codegen] to new-phi: ");
+	  print_gimple_stmt (dump_file, new_phi, 0, 0);
+	}
+    }
+}
+
 /* Prints NODE to FILE.  */
 
 void
@@ -926,13 +993,13 @@ add_parameters_to_ivs_params (scop_p scop, ivs_params &ip)
 {
   sese_info_p region = scop->scop_info;
   unsigned nb_parameters = isl_set_dim (scop->param_context, isl_dim_param);
-  gcc_assert (nb_parameters == SESE_PARAMS (region).length ());
+  gcc_assert (nb_parameters == region->params.length ());
   unsigned i;
   for (i = 0; i < nb_parameters; i++)
     {
       isl_id *tmp_id = isl_set_get_dim_id (scop->param_context,
                                            isl_dim_param, i);
-      ip[tmp_id] = SESE_PARAMS (region)[i];
+      ip[tmp_id] = region->params[i];
     }
 }
 
@@ -1101,7 +1168,6 @@ graphite_regenerate_ast_isl (scop_p scop)
   ivs_params ip;
 
   timevar_push (TV_GRAPHITE_CODE_GEN);
-  graphite_regenerate_error = false;
   root_node = scop_to_isl_ast (scop, ip);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -1115,30 +1181,47 @@ graphite_regenerate_ast_isl (scop_p scop)
   graphite_verify ();
 
   if_region = move_sese_in_condition (region);
-  sese_insert_phis_for_liveouts (region,
-				 if_region->region->region.exit->src,
-				 if_region->false_region->region.exit,
-				 if_region->true_region->region.exit);
+  region->if_region = if_region;
   recompute_all_dominators ();
-  graphite_verify ();
 
   context_loop = region->region.entry->src->loop_father;
 
   translate_isl_ast_to_gimple t(region);
   edge e = single_succ_edge (if_region->true_region->region.entry->dest);
-  split_edge (e);
-  t.translate_isl_ast (context_loop, root_node, e, ip);
+  basic_block bb = split_edge (e);
+  /* Update the true_region exit edge.  */
+  region->if_region->true_region->region.exit = single_succ_edge (bb);
 
-  mark_virtual_operands_for_renaming (cfun);
-  update_ssa (TODO_update_ssa);
-
-  graphite_verify ();
-  scev_reset ();
-  recompute_all_dominators ();
-  graphite_verify ();
-
-  if (graphite_regenerate_error)
-    set_ifsese_condition (if_region, integer_zero_node);
+  t.translate_isl_ast (context_loop, root_node, e, ip);
+  if (t.codegen_error_p ())
+    {
+      if (dump_file)
+	fprintf (dump_file, "\n[codegen] unsuccessful, "
+		 "reverting back to the original code.");
+      set_ifsese_condition (if_region, integer_zero_node);
+    }
+  else
+    {
+      t.translate_pending_phi_nodes ();
+      if (!t.codegen_error_p ())
+	{
+	  sese_insert_phis_for_liveouts (region,
+					 if_region->region->region.exit->src,
+					 if_region->false_region->region.exit,
+					 if_region->true_region->region.exit);
+	  mark_virtual_operands_for_renaming (cfun);
+	  update_ssa (TODO_update_ssa);
+
+
+	  graphite_verify ();
+	  scev_reset ();
+	  recompute_all_dominators ();
+	  graphite_verify ();
+	}
+      else if (dump_file)
+	fprintf (dump_file, "\n[codegen] unsuccessful in translating "
+		 "pending phis, reverting back to the original code.");
+    }
 
   free (if_region->true_region);
   free (if_region->region);
@@ -1161,6 +1244,6 @@ graphite_regenerate_ast_isl (scop_p scop)
 	       num_no_dependency);
     }
 
-  return !graphite_regenerate_error;
+  return !t.codegen_error_p ();
 }
 #endif  /* HAVE_isl */
diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c
index 36c3061..5928b4c 100644
--- a/gcc/graphite-poly.c
+++ b/gcc/graphite-poly.c
@@ -132,21 +132,19 @@ apply_poly_transforms (scop_p scop)
    NB_SUBSCRIPTS.  */
 
 void
-new_poly_dr (poly_bb_p pbb, enum poly_dr_type type, data_reference_p cdr,
-	     graphite_dim_t nb_subscripts,
+new_poly_dr (poly_bb_p pbb, gimple *stmt, enum poly_dr_type type,
 	     isl_map *acc, isl_set *subscript_sizes)
 {
   static int id = 0;
   poly_dr_p pdr = XNEW (struct poly_dr);
 
+  pdr->stmt = stmt;
   PDR_ID (pdr) = id++;
   PDR_NB_REFS (pdr) = 1;
   PDR_PBB (pdr) = pbb;
   pdr->accesses = acc;
   pdr->subscript_sizes = subscript_sizes;
   PDR_TYPE (pdr) = type;
-  PDR_CDR (pdr) = cdr;
-  PDR_NB_SUBSCRIPTS (pdr) = nb_subscripts;
   PBB_DRS (pbb).safe_push (pdr);
 }
 
@@ -226,6 +224,8 @@ print_pdr (FILE *file, poly_dr_p pdr)
       gcc_unreachable ();
     }
 
+  fprintf (file, "in gimple stmt: ");
+  print_gimple_stmt (file, pdr->stmt, 0, 0);
   fprintf (file, "data accesses: ");
   print_isl_map (file, pdr->accesses);
   fprintf (file, "subscript sizes: ");
@@ -244,14 +244,14 @@ debug_pdr (poly_dr_p pdr)
 /* Store the GRAPHITE representation of BB.  */
 
 gimple_poly_bb_p
-new_gimple_poly_bb (basic_block bb, vec<data_reference_p> drs)
+new_gimple_poly_bb (basic_block bb, vec<data_reference_p> drs,
+		    vec<scalar_use> reads, vec<tree> writes)
 {
-  gimple_poly_bb_p gbb;
-
-  gbb = XNEW (struct gimple_poly_bb);
-  bb->aux = gbb;
+  gimple_poly_bb_p gbb = XNEW (struct gimple_poly_bb);
   GBB_BB (gbb) = bb;
   GBB_DATA_REFS (gbb) = drs;
+  gbb->read_scalar_refs = reads;
+  gbb->write_scalar_refs = writes;
   GBB_CONDITIONS (gbb).create (0);
   GBB_CONDITION_CASES (gbb).create (0);
 
@@ -264,10 +264,10 @@ void
 free_gimple_poly_bb (gimple_poly_bb_p gbb)
 {
   free_data_refs (GBB_DATA_REFS (gbb));
-
   GBB_CONDITIONS (gbb).release ();
   GBB_CONDITION_CASES (gbb).release ();
-  GBB_BB (gbb)->aux = 0;
+  gbb->read_scalar_refs.release ();
+  gbb->write_scalar_refs.release ();
   XDELETE (gbb);
 }
 
@@ -477,13 +477,13 @@ print_pbb (FILE *file, poly_bb_p pbb)
 void
 print_scop_params (FILE *file, scop_p scop)
 {
-  if (SESE_PARAMS (scop->scop_info).is_empty ())
+  if (scop->scop_info->params.is_empty ())
     return;
 
   int i;
   tree t;
   fprintf (file, "parameters (");
-  FOR_EACH_VEC_ELT (SESE_PARAMS (scop->scop_info), i, t)
+  FOR_EACH_VEC_ELT (scop->scop_info->params, i, t)
     {
       print_generic_expr (file, t, 0);
       fprintf (file, ", ");
diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h
index b35431a..3fcbbaf 100644
--- a/gcc/graphite-poly.h
+++ b/gcc/graphite-poly.h
@@ -58,8 +58,8 @@ struct poly_dr
   /* The number of data refs identical to this one in the PBB.  */
   int nb_refs;
 
-  /* A pointer to compiler's data reference description.  */
-  data_reference_p compiler_dr;
+  /* A pointer to the gimple stmt containing this reference.  */
+  gimple *stmt;
 
   /* A pointer to the PBB that contains this data reference.  */
   poly_bb_p pbb;
@@ -181,21 +181,16 @@ struct poly_dr
      In the example, the vector "R C O I L P" is "7 7 3 2 0 1".  */
   isl_map *accesses;
   isl_set *subscript_sizes;
-
-  /* The number of subscripts.  */
-  graphite_dim_t nb_subscripts;
 };
 
 #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)
 #define PDR_ACCESSES(PDR) (NULL)
-#define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts)
 
-void new_poly_dr (poly_bb_p, enum poly_dr_type, data_reference_p,
-		  graphite_dim_t, isl_map *, isl_set *);
+void new_poly_dr (poly_bb_p, gimple *, enum poly_dr_type,
+		  isl_map *, isl_set *);
 void free_poly_dr (poly_dr_p);
 void debug_pdr (poly_dr_p);
 void print_pdr (FILE *, poly_dr_p);
@@ -270,6 +265,9 @@ struct poly_bb
 
   /* True when this PBB contains only a reduction statement.  */
   bool is_reduction;
+
+  /* The last basic block generated for this pbb.  */
+  basic_block new_bb;
 };
 
 #define PBB_BLACK_BOX(PBB) ((gimple_poly_bb_p) PBB->black_box)
@@ -314,22 +312,6 @@ extern bool optimize_isl (scop_p);
 extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, mpz_t);
 extern void debug_gmp_value (mpz_t);
 
-/* Returns a gimple_bb from BB.  */
-
-static inline gimple_poly_bb_p
-gbb_from_bb (basic_block bb)
-{
-  return (gimple_poly_bb_p) bb->aux;
-}
-
-/* The poly_bb of the BB.  */
-
-static inline poly_bb_p
-pbb_from_bb (basic_block bb)
-{
-  return GBB_PBB (gbb_from_bb (bb));
-}
-
 /* The basic block of the PBB.  */
 
 static inline basic_block
@@ -446,7 +428,8 @@ struct scop
 
 extern scop_p new_scop (edge, edge);
 extern void free_scop (scop_p);
-extern gimple_poly_bb_p new_gimple_poly_bb (basic_block, vec<data_reference_p>);
+extern gimple_poly_bb_p new_gimple_poly_bb (basic_block, vec<data_reference_p>,
+					    vec<scalar_use>, vec<tree>);
 extern void free_gimple_poly_bb (gimple_poly_bb_p);
 extern void print_generated_program (FILE *, scop_p);
 extern void debug_generated_program (scop_p);
diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
index 9fb8264..a7179d9 100644
--- a/gcc/graphite-scop-detection.c
+++ b/gcc/graphite-scop-detection.c
@@ -1507,7 +1507,7 @@ parameter_index_in_region_1 (tree name, sese_info_p region)
 
   gcc_assert (TREE_CODE (name) == SSA_NAME);
 
-  FOR_EACH_VEC_ELT (SESE_PARAMS (region), i, p)
+  FOR_EACH_VEC_ELT (region->params, i, p)
     if (p == name)
       return i;
 
@@ -1536,8 +1536,8 @@ parameter_index_in_region (tree name, sese_info_p region)
   if (i != -1)
     return i;
 
-  i = SESE_PARAMS (region).length ();
-  SESE_PARAMS (region).safe_push (name);
+  i = region->params.length ();
+  region->params.safe_push (name);
   return i;
 }
 
@@ -1635,7 +1635,7 @@ find_scop_parameters (scop_p scop)
   struct loop *loop;
 
   /* Find the parameters used in the loop bounds.  */
-  FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), i, loop)
+  FOR_EACH_VEC_ELT (region->loop_nest, i, loop)
     {
       tree nb_iters = number_of_latch_executions (loop);
 
@@ -1655,6 +1655,94 @@ find_scop_parameters (scop_p scop)
   scop_set_nb_params (scop, nbp);
 }
 
+/* Record DEF if it is used in other bbs different than DEF_BB in the SCOP.  */
+
+static void
+build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb,
+			     vec<tree> *writes)
+{
+  gcc_assert (def);
+  if (!is_gimple_reg (def))
+    return;
+
+  /* Do not gather scalar variables that can be analyzed by SCEV as they can be
+     generated out of the induction variables.  */
+  if (scev_analyzable_p (def, scop->scop_info->region))
+    return;
+
+  gimple *use_stmt;
+  imm_use_iterator imm_iter;
+  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
+    if (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt))
+      {
+	writes->safe_push (def);
+	DEBUG_PRINT (dp << "Adding scalar write:\n";
+		     print_generic_expr (dump_file, def, 0);
+		     dp << "From stmt:\n";
+		     print_gimple_stmt (dump_file,
+					SSA_NAME_DEF_STMT (def), 0, 0));
+	/* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
+	   before all the uses have been visited.  */
+	BREAK_FROM_IMM_USE_STMT (imm_iter);
+      }
+}
+
+/* Record DEF if it is used in other bbs different than DEF_BB in the SCOP.  */
+
+static void
+build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
+			    vec<scalar_use> *reads)
+{
+  gcc_assert (use);
+  if (!is_gimple_reg (use))
+    return;
+
+  /* Do not gather scalar variables that can be analyzed by SCEV as they can be
+     generated out of the induction variables.  */
+  if (scev_analyzable_p (use, scop->scop_info->region))
+    return;
+
+  gimple *def_stmt = SSA_NAME_DEF_STMT (use);
+  if (gimple_bb (def_stmt) != gimple_bb (use_stmt))
+    {
+      DEBUG_PRINT (dp << "Adding scalar read:\n";
+		   print_generic_expr (dump_file, use, 0);
+		   dp << "From stmt:\n";
+		   print_gimple_stmt (dump_file, use_stmt, 0, 0));
+      reads->safe_push (std::make_pair (use_stmt, use));
+    }
+}
+
+/* Record all scalar variables that are defined and used in different BBs of the
+   SCOP.  */
+
+static void
+graphite_find_cross_bb_scalar_vars (scop_p scop, gimple *stmt,
+				    vec<scalar_use> *reads, vec<tree> *writes)
+{
+  tree def;
+
+  if (gimple_code (stmt) == GIMPLE_ASSIGN)
+    def = gimple_assign_lhs (stmt);
+  else if (gimple_code (stmt) == GIMPLE_CALL)
+    def = gimple_call_lhs (stmt);
+  else if (gimple_code (stmt) == GIMPLE_PHI)
+    def = gimple_phi_result (stmt);
+  else
+    return;
+
+
+  build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), writes);
+
+  ssa_op_iter iter;
+  use_operand_p use_p;
+  FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
+    {
+      tree use = USE_FROM_PTR (use_p);
+      build_cross_bb_scalars_use (scop, use, stmt, reads);
+    }
+}
+
 /* Generates a polyhedral black box only if the bb contains interesting
    information.  */
 
@@ -1662,7 +1750,12 @@ static gimple_poly_bb_p
 try_generate_gimple_bb (scop_p scop, basic_block bb)
 {
   vec<data_reference_p> drs;
-  drs.create (5);
+  drs.create (3);
+  vec<tree> writes;
+  writes.create (3);
+  vec<scalar_use> reads;
+  reads.create (3);
+
   sese_l region = scop->scop_info->region;
   loop_p nest = outermost_loop_in_sese (region, bb);
 
@@ -1670,17 +1763,58 @@ try_generate_gimple_bb (scop_p scop, basic_block bb)
   if (!loop_in_sese_p (loop, region))
     loop = nest;
 
-  gimple_stmt_iterator gsi;
-  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+  for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
+       gsi_next (&gsi))
     {
       gimple *stmt = gsi_stmt (gsi);
       if (is_gimple_debug (stmt))
 	continue;
 
       graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
+      graphite_find_cross_bb_scalar_vars (scop, stmt, &reads, &writes);
     }
 
-  return new_gimple_poly_bb (bb, drs);
+  for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
+       gsi_next (&psi))
+    if (!virtual_operand_p (gimple_phi_result (psi.phi ())))
+      graphite_find_cross_bb_scalar_vars (scop, psi.phi (), &reads, &writes);
+
+  if (drs.is_empty () && writes.is_empty () && reads.is_empty ())
+    return NULL;
+
+  return new_gimple_poly_bb (bb, drs, reads, writes);
+}
+
+/* Compute alias-sets for all data references in DRS.  */
+
+static void
+build_alias_set (scop_p scop)
+{
+  int num_vertices = scop->drs.length ();
+  struct graph *g = new_graph (num_vertices);
+  dr_info *dr1, *dr2;
+  int i, j;
+  int *all_vertices;
+
+  FOR_EACH_VEC_ELT (scop->drs, i, dr1)
+    for (j = i+1; scop->drs.iterate (j, &dr2); j++)
+      if (dr_may_alias_p (dr1->dr, dr2->dr, true))
+	{
+	  add_edge (g, i, j);
+	  add_edge (g, j, i);
+	}
+
+  all_vertices = XNEWVEC (int, num_vertices);
+  for (i = 0; i < num_vertices; i++)
+    all_vertices[i] = i;
+
+  graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL);
+  free (all_vertices);
+
+  for (i = 0; i < g->n_vertices; i++)
+    scop->drs[i].alias_set = g->vertices[i].component + 1;
+
+  free_graph (g);
 }
 
 /* Gather BBs and conditions for a SCOP.  */
@@ -1728,11 +1862,19 @@ gather_bbs::before_dom_children (basic_block bb)
   scop->scop_info->bbs.safe_push (bb);
 
   gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
+  if (!gbb)
+    return;
+
   GBB_CONDITIONS (gbb) = conditions.copy ();
   GBB_CONDITION_CASES (gbb) = cases.copy ();
 
   poly_bb_p pbb = new_poly_bb (scop, gbb);
   scop->pbbs.safe_push (pbb);
+
+  int i;
+  data_reference_p dr;
+  FOR_EACH_VEC_ELT (gbb->data_refs, i, dr)
+    scop->drs.safe_push (dr_info (dr, pbb));
 }
 
 /* Call-back for dom_walk executed after visiting the dominated
@@ -1776,6 +1918,8 @@ build_scops (vec<scop_p> *scops)
       /* Record all basic blocks and their conditions in REGION.  */
       gather_bbs (CDI_DOMINATORS, scop).walk (cfun->cfg->x_entry_block_ptr);
 
+      build_alias_set (scop);
+
       /* Do not optimize a scop containing only PBBs that do not belong
 	 to any loops.  */
       if (sb.nb_pbbs_in_loops (scop) == 0)
@@ -1807,7 +1951,6 @@ build_scops (vec<scop_p> *scops)
 		          << scop_nb_params (scop)
 		          << " larger than --param graphite-max-nb-scop-params="
 		          << max_dim << ".\n");
-
 	  free_scop (scop);
 	  continue;
 	}
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 3c24512..83acc4a 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -75,124 +75,6 @@ tree_int_to_gmp (tree t, mpz_t res)
   wi::to_mpz (t, res, TYPE_SIGN (TREE_TYPE (t)));
 }
 
-/* Returns the index of the PHI argument defined in the outermost
-   loop.  */
-
-static size_t
-phi_arg_in_outermost_loop (gphi *phi)
-{
-  loop_p loop = gimple_bb (phi)->loop_father;
-  size_t i, res = 0;
-
-  for (i = 0; i < gimple_phi_num_args (phi); i++)
-    if (!flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, i)->src))
-      {
-	loop = gimple_phi_arg_edge (phi, i)->src->loop_father;
-	res = i;
-      }
-
-  return res;
-}
-
-/* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
-   PSI by inserting on the loop ENTRY edge assignment "RES = INIT".  */
-
-static void
-remove_simple_copy_phi (gphi_iterator *psi)
-{
-  gphi *phi = psi->phi ();
-  tree res = gimple_phi_result (phi);
-  size_t entry = phi_arg_in_outermost_loop (phi);
-  tree init = gimple_phi_arg_def (phi, entry);
-  gassign *stmt = gimple_build_assign (res, init);
-  edge e = gimple_phi_arg_edge (phi, entry);
-
-  remove_phi_node (psi, false);
-  gsi_insert_on_edge_immediate (e, stmt);
-}
-
-/* Removes an invariant phi node at position PSI by inserting on the
-   loop ENTRY edge the assignment RES = INIT.  */
-
-static void
-remove_invariant_phi (sese_l &region, gphi_iterator *psi)
-{
-  gphi *phi = psi->phi ();
-  loop_p loop = loop_containing_stmt (phi);
-  tree res = gimple_phi_result (phi);
-  tree scev = scalar_evolution_in_region (region, loop, res);
-  size_t entry = phi_arg_in_outermost_loop (phi);
-  edge e = gimple_phi_arg_edge (phi, entry);
-  tree var;
-  gassign *stmt;
-  gimple_seq stmts = NULL;
-
-  if (tree_contains_chrecs (scev, NULL))
-    scev = gimple_phi_arg_def (phi, entry);
-
-  var = force_gimple_operand (scev, &stmts, true, NULL_TREE);
-  stmt = gimple_build_assign (res, var);
-  remove_phi_node (psi, false);
-
-  gimple_seq_add_stmt (&stmts, stmt);
-  gsi_insert_seq_on_edge (e, stmts);
-  gsi_commit_edge_inserts ();
-  SSA_NAME_DEF_STMT (res) = stmt;
-}
-
-/* Returns true when the phi node at PSI is of the form "a = phi (a, x)".  */
-
-static inline bool
-simple_copy_phi_p (gphi *phi)
-{
-  if (gimple_phi_num_args (phi) != 2)
-    return false;
-
-  tree res = gimple_phi_result (phi);
-  return (res == gimple_phi_arg_def (phi, 0)
-	  || res == gimple_phi_arg_def (phi, 1));
-}
-
-/* Returns true when the phi node at position PSI is a reduction phi
-   node in REGION.  Otherwise moves the pointer PSI to the next phi to
-   be considered.  */
-
-static bool
-reduction_phi_p (sese_l &region, gphi_iterator *psi)
-{
-  loop_p loop;
-  gphi *phi = psi->phi ();
-  tree res = gimple_phi_result (phi);
-
-  loop = loop_containing_stmt (phi);
-
-  if (simple_copy_phi_p (phi))
-    {
-      /* PRE introduces phi nodes like these, for an example,
-	 see id-5.f in the fortran graphite testsuite:
-
-	 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
-      */
-      remove_simple_copy_phi (psi);
-      return false;
-    }
-
-  if (scev_analyzable_p (res, region))
-    {
-      tree scev = scalar_evolution_in_region (region, loop, res);
-
-      if (evolution_function_is_invariant_p (scev, loop->num))
-	remove_invariant_phi (region, psi);
-      else
-	gsi_next (psi);
-
-      return false;
-    }
-
-  /* All the other cases are considered reductions.  */
-  return true;
-}
-
 /* Return an ISL identifier for the polyhedral basic block PBB.  */
 
 static isl_id *
@@ -532,14 +414,14 @@ isl_id_for_ssa_name (scop_p s, tree e)
   return id;
 }
 
-/* Return an ISL identifier for the data reference DR.  */
+/* Return an ISL identifier for the data reference DR.  Data references and
+   scalar references get the same isl_id.  They need to be comparable and are
+   distinguished through the first dimension, which contains the alias set or
+   SSA_NAME_VERSION number.  */
 
 static isl_id *
-isl_id_for_dr (scop_p s, data_reference_p dr ATTRIBUTE_UNUSED)
+isl_id_for_dr (scop_p s)
 {
-  /* Data references all get the same isl_id.  They need to be comparable
-     and are distinguished through the first dimension, which contains the
-     alias set number.  */
   return isl_id_alloc (s->isl_context, "", 0);
 }
 
@@ -612,7 +494,7 @@ parameter_index_in_region_1 (tree name, sese_info_p region)
 
   gcc_assert (TREE_CODE (name) == SSA_NAME);
 
-  FOR_EACH_VEC_ELT (SESE_PARAMS (region), i, p)
+  FOR_EACH_VEC_ELT (region->params, i, p)
     if (p == name)
       return i;
 
@@ -700,7 +582,7 @@ set_scop_parameter_dim (scop_p scop)
 
   unsigned i;
   tree e;
-  FOR_EACH_VEC_ELT (SESE_PARAMS (region), i, e)
+  FOR_EACH_VEC_ELT (region->params, i, e)
     space = isl_space_set_dim_id (space, isl_dim_param, i,
                                   isl_id_for_ssa_name (scop, e));
 
@@ -941,7 +823,7 @@ add_conditions_to_constraints (scop_p scop)
 static void
 add_param_constraints (scop_p scop, graphite_dim_t p)
 {
-  tree parameter = SESE_PARAMS (scop->scop_info)[p];
+  tree parameter = scop->scop_info->params[p];
   tree type = TREE_TYPE (parameter);
   tree lb = NULL_TREE;
   tree ub = NULL_TREE;
@@ -1021,7 +903,7 @@ build_scop_iteration_domain (scop_p scop)
 
   int i;
   struct loop *loop;
-  FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), i, loop)
+  FOR_EACH_VEC_ELT (region->loop_nest, i, loop)
     if (!loop_in_sese_p (loop_outer (loop), region->region))
       build_loop_iteration_domains (scop, loop, 0,
 				    isl_set_copy (scop->param_context), doms);
@@ -1057,12 +939,32 @@ pdr_add_alias_set (isl_map *acc, dr_info &dri)
 {
   isl_constraint *c = isl_equality_alloc
       (isl_local_space_from_space (isl_map_get_space (acc)));
+  /* Positive numbers for all alias sets.  */
   c = isl_constraint_set_constant_si (c, -dri.alias_set);
   c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1);
 
   return isl_map_add_constraint (acc, c);
 }
 
+/* Add a constrain to the ACCESSES polyhedron for the alias set of
+   data reference DR.  ACCESSP_NB_DIMS is the dimension of the
+   ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
+   domain.  */
+
+static isl_map *
+add_scalar_version_numbers (isl_map *acc, tree var)
+{
+  isl_constraint *c = isl_equality_alloc
+      (isl_local_space_from_space (isl_map_get_space (acc)));
+  int max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP);
+  /* Each scalar variables has a unique alias set number starting from
+     max_arrays.  */
+  c = isl_constraint_set_constant_si (c, -max_arrays - SSA_NAME_VERSION (var));
+  c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1);
+
+  return isl_map_add_constraint (acc, c);
+}
+
 /* Assign the affine expression INDEX to the output dimension POS of
    MAP and return the result.  */
 
@@ -1178,7 +1080,7 @@ pdr_add_data_dimensions (isl_set *subscript_sizes, scop_p scop,
   return subscript_sizes;
 }
 
-/* Build data accesses for DR in PBB.  */
+/* Build data accesses for DRI.  */
 
 static void
 build_poly_dr (dr_info &dri)
@@ -1188,6 +1090,7 @@ build_poly_dr (dr_info &dri)
   poly_bb_p pbb = dri.pbb;
   data_reference_p dr = dri.dr;
   scop_p scop = PBB_SCOP (pbb);
+  isl_id *id = isl_id_for_dr (scop);
 
   {
     isl_space *dc = isl_set_get_space (pbb->domain);
@@ -1196,14 +1099,13 @@ build_poly_dr (dr_info &dri)
 					   isl_dim_out, nb_out);
 
     acc = isl_map_universe (space);
-    acc = isl_map_set_tuple_id (acc, isl_dim_out, isl_id_for_dr (scop, dr));
+    acc = isl_map_set_tuple_id (acc, isl_dim_out, isl_id_copy (id));
   }
 
   acc = pdr_add_alias_set (acc, dri);
   acc = pdr_add_memory_accesses (acc, dri);
 
   {
-    isl_id *id = isl_id_for_dr (scop, dr);
     int nb = 1 + DR_NUM_DIMENSIONS (dr);
     isl_space *space = isl_space_set_alloc (scop->isl_context, 0, nb);
 
@@ -1214,614 +1116,72 @@ build_poly_dr (dr_info &dri)
     subscript_sizes = pdr_add_data_dimensions (subscript_sizes, scop, dr);
   }
 
-  new_poly_dr (pbb,
-	       DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
-	       dr, DR_NUM_DIMENSIONS (dr), acc, subscript_sizes);
-}
-
-/* Compute alias-sets for all data references in DRS.  */
-
-static void
-build_alias_set (scop_p scop)
-{
-  int num_vertices = scop->drs.length ();
-  struct graph *g = new_graph (num_vertices);
-  dr_info *dr1, *dr2;
-  int i, j;
-  int *all_vertices;
-
-  FOR_EACH_VEC_ELT (scop->drs, i, dr1)
-    for (j = i+1; scop->drs.iterate (j, &dr2); j++)
-      if (dr_may_alias_p (dr1->dr, dr2->dr, true))
-	{
-	  add_edge (g, i, j);
-	  add_edge (g, j, i);
-	}
-
-  all_vertices = XNEWVEC (int, num_vertices);
-  for (i = 0; i < num_vertices; i++)
-    all_vertices[i] = i;
-
-  graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL);
-  free (all_vertices);
-
-  for (i = 0; i < g->n_vertices; i++)
-    scop->drs[i].alias_set = g->vertices[i].component + 1;
-
-  free_graph (g);
-}
-
-/* Build data references in SCOP.  */
-
-static void
-build_scop_drs (scop_p scop)
-{
-  int i, j;
-  poly_bb_p pbb;
-
-  /* Remove all the PBBs that do not have data references: these basic
-     blocks are not handled in the polyhedral representation.  */
-  for (i = 0; scop->pbbs.iterate (i, &pbb); i++)
-    if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb)).is_empty ())
-      {
-	free_gimple_poly_bb (PBB_BLACK_BOX (pbb));
-	free_poly_bb (pbb);
-	scop->pbbs.ordered_remove (i);
-	i--;
-      }
-
-  data_reference_p dr;
-  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
-    if (pbb)
-      FOR_EACH_VEC_ELT (GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr)
-	scop->drs.safe_push (dr_info (dr, pbb));
-
-  build_alias_set (scop);
-
-  dr_info *dri;
-  FOR_EACH_VEC_ELT (scop->drs, i, dri)
-    build_poly_dr (*dri);
+  new_poly_dr (pbb, DR_STMT (dr), DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
+	       acc, subscript_sizes);
 }
 
-/* Analyze all the data references of STMTS and add them to the
-   GBB_DATA_REFS vector of BB.  */
-
 static void
-analyze_drs_in_stmts (scop_p scop, basic_block bb, vec<gimple *> stmts)
+build_poly_sr_1 (poly_bb_p pbb, gimple *stmt, tree var, enum poly_dr_type kind,
+		 isl_map *acc, isl_set *subscript_sizes)
 {
-  sese_l region = scop->scop_info->region;
-  if (!bb_in_sese_p (bb, region))
-    return;
-
-  loop_p nest = outermost_loop_in_sese (region, bb);
-  loop_p loop = bb->loop_father;
-  if (!loop_in_sese_p (loop, region))
-    loop = nest;
-
-  gimple_poly_bb_p gbb = gbb_from_bb (bb);
-
-  gimple *stmt;
-  int i;
-  FOR_EACH_VEC_ELT (stmts, i, stmt)
-    {
-      if (is_gimple_debug (stmt))
-	continue;
-
-      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
-   statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
-   on STMTS.  */
-
-static void
-insert_stmts (scop_p scop, gimple *stmt, gimple_seq stmts,
-	      gimple_stmt_iterator insert_gsi)
-{
-  gimple_stmt_iterator gsi;
-  auto_vec<gimple *, 3> x;
-
-  gimple_seq_add_stmt (&stmts, stmt);
-  for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
-    x.safe_push (gsi_stmt (gsi));
-
-  gsi_insert_seq_before (&insert_gsi, stmts, GSI_SAME_STMT);
-  analyze_drs_in_stmts (scop, gsi_bb (insert_gsi), x);
+  int max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP);
+  /* Each scalar variables has a unique alias set number starting from
+     max_arrays.  */
+  subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0,
+				    max_arrays + SSA_NAME_VERSION (var));
+
+  new_poly_dr (pbb, stmt, kind, add_scalar_version_numbers (acc, var),
+	       subscript_sizes);
 }
 
-/* Insert the assignment "RES := EXPR" just after AFTER_STMT.  */
+/* Record all cross basic block scalar variables in PBB.  */
 
 static void
-insert_out_of_ssa_copy (scop_p scop, tree res, tree expr, gimple *after_stmt)
+build_poly_sr (poly_bb_p pbb)
 {
-  gimple_stmt_iterator gsi;
-  auto_vec<gimple *, 3> x;
-  gimple_seq stmts;
-  tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
-  gassign *stmt = gimple_build_assign (unshare_expr (res), var);
-
-  gimple_seq_add_stmt (&stmts, stmt);
-
-  for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
-    x.safe_push (gsi_stmt (gsi));
-
-  if (gimple_code (after_stmt) == GIMPLE_PHI)
-    {
-      gsi = gsi_after_labels (gimple_bb (after_stmt));
-      gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
-    }
-  else
-    {
-      gsi = gsi_for_stmt (after_stmt);
-      gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
-    }
-
-  analyze_drs_in_stmts (scop, gimple_bb (after_stmt), x);
-}
-
-/* Creates a poly_bb_p for basic_block BB from the existing PBB.  */
-
-static void
-new_pbb_from_pbb (scop_p scop, poly_bb_p pbb, basic_block bb)
-{
-  vec<data_reference_p> drs;
-  drs.create (3);
+  scop_p scop = PBB_SCOP (pbb);
   gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
-  gimple_poly_bb_p gbb1 = new_gimple_poly_bb (bb, drs);
-  poly_bb_p pbb1 = new_poly_bb (scop, gbb1);
-  int index, n = scop->pbbs.length ();
-
-  for (index = 0; index < n; index++)
-    if (scop->pbbs[index] == pbb)
-      break;
-
-  pbb1->domain = isl_set_copy (pbb->domain);
-  pbb1->domain = isl_set_set_tuple_id (pbb1->domain,
-				       isl_id_for_pbb (scop, pbb1));
-
-  GBB_PBB (gbb1) = pbb1;
-  GBB_CONDITIONS (gbb1) = GBB_CONDITIONS (gbb).copy ();
-  GBB_CONDITION_CASES (gbb1) = GBB_CONDITION_CASES (gbb).copy ();
-  scop->pbbs.safe_insert (index + 1, pbb1);
-}
-
-/* Insert on edge E the assignment "RES := EXPR".  */
-
-static void
-insert_out_of_ssa_copy_on_edge (scop_p scop, edge e, tree res, tree expr)
-{
-  gimple_seq stmts = NULL;
-  tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
-  gimple *stmt = gimple_build_assign (unshare_expr (res), var);
-  auto_vec<gimple *, 3> x;
-
-  gimple_seq_add_stmt (&stmts, stmt);
-  gimple_stmt_iterator gsi;
-  for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
-    x.safe_push (gsi_stmt (gsi));
-
-  gsi_insert_seq_on_edge (e, stmts);
-  gsi_commit_edge_inserts ();
-  basic_block bb = gimple_bb (stmt);
-
-  if (!bb_in_sese_p (bb, scop->scop_info->region))
-    return;
-
-  if (!gbb_from_bb (bb))
-    new_pbb_from_pbb (scop, pbb_from_bb (e->src), bb);
-
-  analyze_drs_in_stmts (scop, bb, x);
-}
-
-/* Creates a zero dimension array of the same type as VAR.  */
-
-static tree
-create_zero_dim_array (tree var, const char *base_name)
-{
-  tree index_type = build_index_type (integer_zero_node);
-  tree elt_type = TREE_TYPE (var);
-  tree array_type = build_array_type (elt_type, index_type);
-  tree base = create_tmp_var (array_type, base_name);
-
-  return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
-		 NULL_TREE);
-}
-
-/* Returns true when PHI is a loop close phi node.  */
-
-static bool
-scalar_close_phi_node_p (gimple *phi)
-{
-  if (gimple_code (phi) != GIMPLE_PHI
-      || virtual_operand_p (gimple_phi_result (phi)))
-    return false;
-
-  /* Note that loop close phi nodes should have a single argument
-     because we translated the representation into a canonical form
-     before Graphite: see canonicalize_loop_closed_ssa_form.  */
-  return (gimple_phi_num_args (phi) == 1);
-}
-
-/* For a definition DEF in REGION, propagates the expression EXPR in
-   all the uses of DEF outside REGION.  */
+  vec<scalar_use> reads = gbb->read_scalar_refs;
+  vec<tree> writes = gbb->write_scalar_refs;
 
-static void
-propagate_expr_outside_region (tree def, tree expr, sese_l &region)
-{
-  gimple_seq stmts;
-  bool replaced_once = false;
-
-  gcc_assert (TREE_CODE (def) == SSA_NAME);
-
-  expr = force_gimple_operand (unshare_expr (expr), &stmts, true,
-			       NULL_TREE);
-
-  imm_use_iterator imm_iter;
-  gimple *use_stmt;
-  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
-    if (!is_gimple_debug (use_stmt)
-	&& !bb_in_sese_p (gimple_bb (use_stmt), region))
-      {
-	ssa_op_iter iter;
-	use_operand_p use_p;
-
-	FOR_EACH_PHI_OR_STMT_USE (use_p, use_stmt, iter, SSA_OP_ALL_USES)
-	  if (operand_equal_p (def, USE_FROM_PTR (use_p), 0)
-	      && (replaced_once = true))
-	    replace_exp (use_p, expr);
-
-	update_stmt (use_stmt);
-      }
-
-  if (replaced_once)
-    {
-      gsi_insert_seq_on_edge (region.entry, stmts);
-      gsi_commit_edge_inserts ();
-    }
-}
-
-/* Rewrite out of SSA the reduction phi node at PSI by creating a zero
-   dimension array for it.  */
-
-static void
-rewrite_close_phi_out_of_ssa (scop_p scop, gimple_stmt_iterator *psi)
-{
-  sese_l region = scop->scop_info->region;
-  gimple *phi = gsi_stmt (*psi);
-  tree res = gimple_phi_result (phi);
-  basic_block bb = gimple_bb (phi);
-  gimple_stmt_iterator gsi = gsi_after_labels (bb);
-  tree arg = gimple_phi_arg_def (phi, 0);
-  gimple *stmt;
-
-  /* Note that loop close phi nodes should have a single argument
-     because we translated the representation into a canonical form
-     before Graphite: see canonicalize_loop_closed_ssa_form.  */
-  gcc_assert (gimple_phi_num_args (phi) == 1);
-
-  /* The phi node can be a non close phi node, when its argument is
-     invariant, or a default definition.  */
-  if (is_gimple_min_invariant (arg)
-      || SSA_NAME_IS_DEFAULT_DEF (arg))
-    {
-      propagate_expr_outside_region (res, arg, region);
-      gsi_next (psi);
-      return;
-    }
-
-  else if (gimple_bb (SSA_NAME_DEF_STMT (arg))->loop_father == bb->loop_father)
-    {
-      propagate_expr_outside_region (res, arg, region);
-      stmt = gimple_build_assign (res, arg);
-      remove_phi_node (psi, false);
-      gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
-      return;
-    }
-
-  /* If res is scev analyzable and is not a scalar value, it is safe
-     to ignore the close phi node: it will be code generated in the
-     out of Graphite pass.  */
-  else if (scev_analyzable_p (res, region))
-    {
-      loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (res));
-      tree scev;
-
-      if (!loop_in_sese_p (loop, region))
-	{
-	  loop = loop_containing_stmt (SSA_NAME_DEF_STMT (arg));
-	  scev = scalar_evolution_in_region (region, loop, arg);
-	  scev = compute_overall_effect_of_inner_loop (loop, scev);
-	}
-      else
-	scev = scalar_evolution_in_region (region, loop, res);
-
-      if (tree_does_not_contain_chrecs (scev))
-	propagate_expr_outside_region (res, scev, region);
-
-      gsi_next (psi);
-      return;
-    }
-  else
-    {
-      tree zero_dim_array = create_zero_dim_array (res, "Close_Phi");
-
-      stmt = gimple_build_assign (res, unshare_expr (zero_dim_array));
-
-      if (TREE_CODE (arg) == SSA_NAME)
-	insert_out_of_ssa_copy (scop, zero_dim_array, arg,
-				SSA_NAME_DEF_STMT (arg));
-      else
-	insert_out_of_ssa_copy_on_edge (scop, single_pred_edge (bb),
-					zero_dim_array, arg);
-    }
-
-  remove_phi_node (psi, false);
-  SSA_NAME_DEF_STMT (res) = stmt;
-
-  insert_stmts (scop, stmt, NULL, gsi_after_labels (bb));
-}
-
-/* Rewrite out of SSA the reduction phi node at PSI by creating a zero
-   dimension array for it.  */
-
-static void
-rewrite_phi_out_of_ssa (scop_p scop, gphi_iterator *psi)
-{
-  gphi *phi = psi->phi ();
-  basic_block bb = gimple_bb (phi);
-  tree res = gimple_phi_result (phi);
-  tree zero_dim_array = create_zero_dim_array (res, "phi_out_of_ssa");
-
-  for (size_t i = 0; i < gimple_phi_num_args (phi); i++)
-    {
-      tree arg = gimple_phi_arg_def (phi, i);
-      edge e = gimple_phi_arg_edge (phi, i);
-
-      /* Avoid the insertion of code in the loop latch to please the
-	 pattern matching of the vectorizer.  */
-      if (TREE_CODE (arg) == SSA_NAME
-	  && !SSA_NAME_IS_DEFAULT_DEF (arg)
-	  && e->src == bb->loop_father->latch)
-	insert_out_of_ssa_copy (scop, zero_dim_array, arg,
-				SSA_NAME_DEF_STMT (arg));
-      else
-	insert_out_of_ssa_copy_on_edge (scop, e, zero_dim_array, arg);
-    }
-
-  gimple *stmt = gimple_build_assign (res, unshare_expr (zero_dim_array));
-  remove_phi_node (psi, false);
-  insert_stmts (scop, stmt, NULL, gsi_after_labels (bb));
-}
-
-/* Rewrite the degenerate phi node at position PSI from the degenerate
-   form "x = phi (y, y, ..., y)" to "x = y".  */
-
-static void
-rewrite_degenerate_phi (gphi_iterator *psi)
-{
-  gphi *phi = psi->phi ();
-  tree res = gimple_phi_result (phi);
-
-  basic_block bb = gimple_bb (phi);
-  tree rhs = degenerate_phi_result (phi);
-  gcc_assert (rhs);
-
-  gimple *stmt = gimple_build_assign (res, rhs);
-  remove_phi_node (psi, false);
-
-  gimple_stmt_iterator gsi = gsi_after_labels (bb);
-  gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
-}
-
-/* Rewrite out of SSA all the reduction phi nodes of SCOP.  */
+  isl_space *dc = isl_set_get_space (pbb->domain);
+  int nb_out = 1;
+  isl_space *space = isl_space_add_dims (isl_space_from_domain (dc),
+					 isl_dim_out, nb_out);
+  isl_id *id = isl_id_for_dr (scop);
+  space = isl_space_set_tuple_id (space, isl_dim_set, isl_id_copy (id));
+  isl_map *acc = isl_map_universe (isl_space_copy (space));
+  acc = isl_map_set_tuple_id (acc, isl_dim_out, id);
+  isl_set *subscript_sizes = isl_set_nat_universe (space);
 
-static void
-rewrite_reductions_out_of_ssa (scop_p scop)
-{
   int i;
-  basic_block bb;
-  FOR_EACH_VEC_ELT (scop->scop_info->bbs, i, bb)
-    for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);)
-      {
-	gphi *phi = psi.phi ();
-
-	if (virtual_operand_p (gimple_phi_result (phi)))
-	  {
-	    gsi_next (&psi);
-	    continue;
-	  }
-
-	if (gimple_phi_num_args (phi) > 1
-	    && degenerate_phi_result (phi))
-	  rewrite_degenerate_phi (&psi);
-
-	else if (scalar_close_phi_node_p (phi))
-	  rewrite_close_phi_out_of_ssa (scop, &psi);
-
-	else if (reduction_phi_p (scop->scop_info->region, &psi))
-	  rewrite_phi_out_of_ssa (scop, &psi);
-      }
-
-  update_ssa (TODO_update_ssa);
-  checking_verify_loop_closed_ssa (true);
-}
-
-/* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
-   read from ZERO_DIM_ARRAY.  */
-
-static void
-rewrite_cross_bb_scalar_dependence (scop_p scop, tree zero_dim_array,
-				    tree def, gimple *use_stmt)
-{
-  gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
-
-  tree name = copy_ssa_name (def);
-  gimple *name_stmt = gimple_build_assign (name, zero_dim_array);
-
-  gimple_assign_set_lhs (name_stmt, name);
-  insert_stmts (scop, name_stmt, NULL, gsi_for_stmt (use_stmt));
-
-  ssa_op_iter iter;
-  use_operand_p use_p;
-  FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
-    if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
-      replace_exp (use_p, name);
-
-  update_stmt (use_stmt);
-}
-
-/* For every definition DEF in the SCOP that is used outside the scop,
-   insert a closing-scop definition in the basic block just after this
-   SCOP.  */
-
-static void
-handle_scalar_deps_crossing_scop_limits (scop_p scop, tree def, gimple *stmt)
-{
-  tree var = create_tmp_reg (TREE_TYPE (def));
-  tree new_name = make_ssa_name (var, stmt);
-  bool needs_copy = false;
-  sese_l region = scop->scop_info->region;
-
-  imm_use_iterator imm_iter;
-  gimple *use_stmt;
-  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
-    {
-      if (!bb_in_sese_p (gimple_bb (use_stmt), region))
-	{
-	  use_operand_p use_p;
-	  FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
-	    {
-	      SET_USE (use_p, new_name);
-	    }
-	  update_stmt (use_stmt);
-	  needs_copy = true;
-	}
-    }
-
-  /* Insert in the empty BB just after the scop a use of DEF such
-     that the rewrite of cross_bb_scalar_dependences won't insert
-     arrays everywhere else.  */
-  if (needs_copy)
-    {
-      gimple *assign = gimple_build_assign (new_name, def);
-      gimple_stmt_iterator psi = gsi_after_labels (region.exit->dest);
-
-      update_stmt (assign);
-      gsi_insert_before (&psi, assign, GSI_SAME_STMT);
-    }
-}
-
-/* Rewrite the scalar dependences crossing the boundary of the BB
-   containing STMT with an array.  Return true when something has been
-   changed.  */
-
-static bool
-rewrite_cross_bb_scalar_deps (scop_p scop, gimple_stmt_iterator *gsi)
-{
-  sese_l region = scop->scop_info->region;
-  gimple *stmt = gsi_stmt (*gsi);
-  imm_use_iterator imm_iter;
-  tree def;
-  tree zero_dim_array = NULL_TREE;
-  gimple *use_stmt;
-  bool res = false;
-
-  switch (gimple_code (stmt))
-    {
-    case GIMPLE_ASSIGN:
-      def = gimple_assign_lhs (stmt);
-      break;
-
-    case GIMPLE_CALL:
-      def = gimple_call_lhs (stmt);
-      break;
-
-    default:
-      return false;
-    }
-
-  if (!def
-      || !is_gimple_reg (def))
-    return false;
-
-  if (scev_analyzable_p (def, region))
-    {
-      loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
-      tree scev = scalar_evolution_in_region (region, loop, def);
-
-      if (tree_contains_chrecs (scev, NULL))
-	return false;
-
-      propagate_expr_outside_region (def, scev, region);
-      return true;
-    }
-
-  basic_block def_bb = gimple_bb (stmt);
-
-  handle_scalar_deps_crossing_scop_limits (scop, def, stmt);
-
-  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
-    if (gphi *phi = dyn_cast <gphi *> (use_stmt))
-      {
-	res = true;
-	gphi_iterator psi = gsi_for_phi (phi);
-
-	if (scalar_close_phi_node_p (gsi_stmt (psi)))
-	  rewrite_close_phi_out_of_ssa (scop, &psi);
-	else
-	  rewrite_phi_out_of_ssa (scop, &psi);
-      }
-
-  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
-    if (gimple_code (use_stmt) != GIMPLE_PHI
-	&& def_bb != gimple_bb (use_stmt)
-	&& !is_gimple_debug (use_stmt)
-	&& (res = true))
-      {
-	if (!zero_dim_array)
-	  {
-	    zero_dim_array = create_zero_dim_array
-	      (def, "Cross_BB_scalar_dependence");
-	    insert_out_of_ssa_copy (scop, zero_dim_array, def,
-				    SSA_NAME_DEF_STMT (def));
-	    gsi_next (gsi);
-	  }
-
-	rewrite_cross_bb_scalar_dependence (scop, unshare_expr (zero_dim_array),
-					    def, use_stmt);
-      }
+  tree var;
+  FOR_EACH_VEC_ELT (writes, i, var)
+    build_poly_sr_1 (pbb, SSA_NAME_DEF_STMT (var), var, PDR_WRITE,
+		     isl_map_copy (acc), isl_set_copy (subscript_sizes));
 
-  update_ssa (TODO_update_ssa);
+  scalar_use *use;
+  FOR_EACH_VEC_ELT (reads, i, use)
+    build_poly_sr_1 (pbb, use->first, use->second, PDR_READ, isl_map_copy (acc),
+		     isl_set_copy (subscript_sizes));
 
-  return res;
+  isl_map_free (acc);
+  isl_set_free (subscript_sizes);
 }
 
-/* Rewrite out of SSA all the reduction phi nodes of SCOP.  */
+/* Build data references in SCOP.  */
 
 static void
-rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop)
+build_scop_drs (scop_p scop)
 {
-  gimple_stmt_iterator psi;
-  sese_l region = scop->scop_info->region;
-  bool changed = false;
-
-  /* Create an extra empty BB after the scop.  */
-  split_edge (region.exit);
-
   int i;
-  basic_block bb;
-  FOR_EACH_VEC_ELT (scop->scop_info->bbs, i, bb)
-    for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
-      changed |= rewrite_cross_bb_scalar_deps (scop, &psi);
+  dr_info *dri;
+  FOR_EACH_VEC_ELT (scop->drs, i, dri)
+    build_poly_dr (*dri);
 
-  if (changed)
-    {
-      scev_reset_htab ();
-      update_ssa (TODO_update_ssa);
-      checking_verify_loop_closed_ssa (true);
-    }
+  poly_bb_p pbb;
+  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
+    build_poly_sr (pbb);
 }
 
 /* Builds the polyhedral representation for a SESE region.  */
@@ -1834,13 +1194,6 @@ build_poly_scop (scop_p scop)
   build_scop_context (scop);
   add_conditions_to_constraints (scop);
 
-  /* Rewrite out of SSA only after having translated the
-     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.  */
-  rewrite_reductions_out_of_ssa (scop);
-  rewrite_cross_bb_scalar_deps_out_of_ssa (scop);
-
   build_scop_drs (scop);
   build_scop_minimal_scattering (scop);
   build_scop_original_schedule (scop);
diff --git a/gcc/graphite.c b/gcc/graphite.c
index 773203e..5316bc4 100644
--- a/gcc/graphite.c
+++ b/gcc/graphite.c
@@ -333,12 +333,16 @@ graphite_transform_loops (void)
 
 	if (dump_file && dump_flags)
 	  print_scop (dump_file, scop);
-
 	if (scop->poly_scop_p
-	    && apply_poly_transforms (scop)
-	    && graphite_regenerate_ast_isl (scop))
-	  need_cfg_cleanup_p = true;
-
+	    && apply_poly_transforms (scop))
+	  {
+	    need_cfg_cleanup_p = true;
+	    /* When code generation is not successful, do not continue
+	       generating code for the next scops: the IR has to be cleaned up
+	       and could be in an inconsistent state.  */
+	    if (!graphite_regenerate_ast_isl (scop))
+	      break;
+	  }
       }
 
   free_scops (scops);
diff --git a/gcc/sese.c b/gcc/sese.c
index 644c87c..5aa558b 100644
--- a/gcc/sese.c
+++ b/gcc/sese.c
@@ -25,6 +25,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "backend.h"
 #include "tree.h"
 #include "gimple.h"
+#include "cfganal.h"
 #include "cfghooks.h"
 #include "tree-pass.h"
 #include "ssa.h"
@@ -34,6 +35,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-eh.h"
 #include "gimplify.h"
 #include "gimple-iterator.h"
+#include "gimple-pretty-print.h"
 #include "gimplify-me.h"
 #include "tree-cfg.h"
 #include "tree-ssa-loop.h"
@@ -44,33 +46,6 @@ along with GCC; see the file COPYING3.  If not see
 #include "value-prof.h"
 #include "sese.h"
 #include "tree-ssa-propagate.h"
-#include "tree-hash-traits.h"
-
-/* Helper function for debug_rename_map.  */
-
-bool
-debug_rename_map_1 (tree_node *const &old_name, tree_node *const &expr,
-		    void *)
-{
-  fprintf (stderr, "(");
-  print_generic_expr (stderr, old_name, 0);
-  fprintf (stderr, ", ");
-  print_generic_expr (stderr, expr, 0);
-  fprintf (stderr, ")\n");
-  return true;
-}
-
-typedef hash_map<tree_ssa_name_hash, tree> rename_map_type;
-
-
-/* Print to stderr all the elements of RENAME_MAP.  */
-
-DEBUG_FUNCTION void
-debug_rename_map (rename_map_type *rename_map)
-{
-  rename_map->traverse <void *, debug_rename_map_1> (NULL);
-}
-
 
 /* Record LOOP as occurring in REGION.  */
 
@@ -80,8 +55,8 @@ sese_record_loop (sese_info_p region, loop_p loop)
   if (sese_contains_loop (region, loop))
     return;
 
-  bitmap_set_bit (SESE_LOOPS (region), loop->num);
-  SESE_LOOP_NEST (region).safe_push (loop);
+  bitmap_set_bit (region->loops, loop->num);
+  region->loop_nest.safe_push (loop);
 }
 
 /* Build the loop nests contained in REGION.  Returns true when the
@@ -108,16 +83,16 @@ build_sese_loop_nests (sese_info_p region)
   /* Make sure that the loops in the SESE_LOOP_NEST are ordered.  It
      can be the case that an inner loop is inserted before an outer
      loop.  To avoid this, semi-sort once.  */
-  FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), i, loop0)
+  FOR_EACH_VEC_ELT (region->loop_nest, i, loop0)
     {
-      if (SESE_LOOP_NEST (region).length () == i + 1)
+      if (region->loop_nest.length () == i + 1)
 	break;
 
-      loop1 = SESE_LOOP_NEST (region)[i + 1];
+      loop1 = region->loop_nest[i + 1];
       if (loop0->num > loop1->num)
 	{
-	  SESE_LOOP_NEST (region)[i] = loop1;
-	  SESE_LOOP_NEST (region)[i + 1] = loop0;
+	  region->loop_nest[i] = loop1;
+	  region->loop_nest[i + 1] = loop0;
 	}
     }
 }
@@ -256,10 +231,13 @@ new_sese_info (edge entry, edge exit)
 
   region->region.entry = entry;
   region->region.exit = exit;
-  SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
-  SESE_LOOP_NEST (region).create (3);
-  SESE_PARAMS (region).create (3);
+  region->loops = BITMAP_ALLOC (NULL);
+  region->loop_nest.create (3);
+  region->params.create (3);
+  region->rename_map = new rename_map_t;
+  region->copied_bb_map = new bb_map_t;
   region->bbs.create (3);
+  region->incomplete_phis.create (3);
 
   return region;
 }
@@ -269,11 +247,28 @@ new_sese_info (edge entry, edge exit)
 void
 free_sese_info (sese_info_p region)
 {
-  if (SESE_LOOPS (region))
-    SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
+  if (region->loops)
+    region->loops = BITMAP_ALLOC (NULL);
 
-  SESE_PARAMS (region).release ();
-  SESE_LOOP_NEST (region).release ();
+  region->params.release ();
+  region->loop_nest.release ();
+
+  for (rename_map_t::iterator it = region->rename_map->begin ();
+       it != region->rename_map->begin (); ++it)
+    (*it).second.release ();
+
+  for (bb_map_t::iterator it = region->copied_bb_map->begin ();
+       it != region->copied_bb_map->begin (); ++it)
+    (*it).second.release ();
+
+  delete region->rename_map;
+  delete region->copied_bb_map;
+
+  region->rename_map = NULL;
+  region->copied_bb_map = NULL;
+
+  region->bbs.release ();
+  region->incomplete_phis.release ();
 
   XDELETE (region);
 }
@@ -312,8 +307,11 @@ sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb,
   update_ssa (TODO_update_ssa);
 
   sese_build_liveouts (region, liveouts);
+
   EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
-    sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
+    if (!virtual_operand_p (ssa_name (i)))
+      sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
+
   BITMAP_FREE (liveouts);
 
   update_ssa (TODO_update_ssa);
@@ -351,37 +349,550 @@ get_false_edge_from_guard_bb (basic_block bb)
   return NULL;
 }
 
-/* Returns the expression associated to OLD_NAME in RENAME_MAP.  */
+/* Check if USE is defined in a basic block from where the definition of USE can
+ propagate from all the paths.  */
+
+static bool
+is_loop_closed_ssa_use (basic_block bb, tree use)
+{
+  if (TREE_CODE (use) != SSA_NAME)
+    return true;
+
+  /* We should not have a rename for virtual operands.  */
+  gcc_assert (!virtual_operand_p (use));
+
+  /* For close-phi nodes def always comes from a loop which has a back-edge.  */
+  if (bb_contains_loop_close_phi_nodes (bb))
+    return true;
+
+  gimple *def = SSA_NAME_DEF_STMT (use);
+  basic_block def_bb = gimple_bb (def);
+  return (!def_bb
+	  || flow_bb_inside_loop_p (def_bb->loop_father, bb));
+}
+
+/* Return the number of phi nodes in BB.  */
+
+static int
+number_of_phi_nodes (basic_block bb)
+{
+  int num_phis = 0;
+  for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
+       gsi_next (&psi))
+    num_phis++;
+  return num_phis;
+}
+
+/* Return true when BB contains loop close phi nodes.  */
+
+bool
+bb_contains_loop_close_phi_nodes (basic_block bb)
+{
+  return single_pred_p (bb)
+    && bb->loop_father != single_pred_edge (bb)->src->loop_father;
+}
+
+/* Return true when BB contains loop phi nodes.  */
+
+bool
+bb_contains_loop_phi_nodes (basic_block bb)
+{
+  gcc_assert (EDGE_COUNT (bb->preds) <= 2);
+
+  if (bb->preds->length () == 1)
+    return false;
+
+  unsigned depth = loop_depth (bb->loop_father);
+
+  edge preds[2] = { (*bb->preds)[0], (*bb->preds)[1] };
+
+  if (depth > loop_depth (preds[0]->src->loop_father)
+      || depth > loop_depth (preds[1]->src->loop_father))
+    return true;
+
+  /* When one of the edges correspond to the same loop father and other
+     doesn't.  */
+  if (bb->loop_father != preds[0]->src->loop_father
+      && bb->loop_father == preds[1]->src->loop_father)
+    return true;
+
+  if (bb->loop_father != preds[1]->src->loop_father
+      && bb->loop_father == preds[0]->src->loop_father)
+    return true;
+
+  return false;
+}
+
+/* Returns true if BB uses name in one of its PHIs.  */
+
+static bool
+phi_uses_name (basic_block bb, tree name)
+{
+  for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
+       gsi_next (&psi))
+    {
+      gphi *phi = psi.phi ();
+      for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
+	{
+	  tree use_arg = gimple_phi_arg_def (phi, i);
+	  if (use_arg == name)
+	    return true;
+	}
+    }
+  return false;
+}
+
+/* Return true if RENAME (defined in BB) is a valid use in NEW_BB.  The
+definition should flow into use, and the use should respect the loop-closed SSA
+form.  */
+
+static bool
+is_valid_rename (tree rename, basic_block def_bb,
+		 basic_block use_bb, bool loop_phi,
+		 tree old_name, basic_block old_bb)
+{
+  /* The def of the rename must either dominate the uses or come from a
+     back-edge.  Also the def must respect the loop closed ssa form.  */
+  if (!is_loop_closed_ssa_use (use_bb, rename))
+    {
+      if (dump_file)
+	{
+	  fprintf (dump_file, "\n[codegen] rename not in loop closed ssa:");
+	  print_generic_expr (dump_file, rename, 0);
+	}
+      return false;
+    }
+
+  if (dominated_by_p (CDI_DOMINATORS, use_bb, def_bb))
+    return true;
+
+  if (bb_contains_loop_phi_nodes (use_bb) && loop_phi)
+    {
+      /* The loop-header dominates the loop-body.  */
+      if (!dominated_by_p (CDI_DOMINATORS, def_bb, use_bb))
+	return false;
+
+      /* RENAME would be used in loop-phi.  */
+      gcc_assert (number_of_phi_nodes (use_bb));
+
+      /* For definitions coming from back edges, we should check that
+	 old_name is used in a loop PHI node.  */
+      if (phi_uses_name (old_bb, old_name))
+	return true;
+    }
+  return false;
+}
+
+/* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
+   NEW_BB from RENAME_MAP.  LOOP_PHI is true when we want to rename OLD_NAME
+   within a loop PHI instruction.  */
 
 static tree
-get_rename (rename_map_type *rename_map, tree old_name)
+get_rename (rename_map_t *rename_map, basic_block new_bb, tree old_name,
+	    basic_block old_bb, bool loop_phi)
 {
   gcc_assert (TREE_CODE (old_name) == SSA_NAME);
-  tree *expr = rename_map->get (old_name);
-  if (expr)
-    return *expr;
+  vec <tree> *renames = rename_map->get (old_name);
 
-  return NULL_TREE;
+  if (!renames || renames->is_empty ())
+    return NULL_TREE;
+
+  if (1 == renames->length ())
+    {
+      tree rename = (*renames)[0];
+      basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (rename));
+      if (is_valid_rename (rename, bb, new_bb, loop_phi, old_name, old_bb))
+	return rename;
+      return NULL_TREE;
+    }
+
+  /* More than one renames corresponding to the old_name.  Find the rename for
+     which the definition flows into usage at new_bb.  */
+  int i;
+  tree t1 = NULL_TREE, t2;
+  basic_block t1_bb = NULL;
+  FOR_EACH_VEC_ELT (*renames, i, t2)
+    {
+      basic_block t2_bb = gimple_bb (SSA_NAME_DEF_STMT (t2));
+
+      /* Defined in the same basic block as used.  */
+      if (t2_bb == new_bb)
+	return t2;
+
+      /* NEW_BB and T2_BB are in two unrelated if-clauses.  */
+      if (!dominated_by_p (CDI_DOMINATORS, new_bb, t2_bb))
+	continue;
+
+      /* Compute the nearest dominator.  */
+      if (!t1 || dominated_by_p (CDI_DOMINATORS, t2_bb, t1_bb))
+	{
+	  t1_bb = t2_bb;
+	  t1 = t2;
+	}
+      //if (is_valid_rename (rename, bb, new_bb, loop_phi, old_name, old_bb))
+      //return rename;
+    }
+
+  return t1;
 }
 
-/* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).  */
+/* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
+   When OLD_NAME and EXPR are the same we assert.  */
 
 static void
-set_rename (rename_map_type *rename_map, tree old_name, tree expr)
+set_rename (tree old_name, tree expr, sese_info_p region)
 {
   if (dump_file)
     {
-      fprintf (dump_file, "[codegen] setting rename: old_name = ");
+      fprintf (dump_file, "\n[codegen] setting rename: old_name = ");
       print_generic_expr (dump_file, old_name, 0);
       fprintf (dump_file, ", new_name = ");
       print_generic_expr (dump_file, expr, 0);
-      fprintf (dump_file, "\n");
     }
 
   if (old_name == expr)
     return;
 
-  rename_map->put (old_name, expr);
+  vec <tree> *renames = region->rename_map->get (old_name);
+
+  if (renames)
+    renames->safe_push (expr);
+  else
+    {
+      vec<tree> r;
+      r.create (2);
+      r.safe_push (expr);
+      region->rename_map->put (old_name, r);
+    }
+}
+
+/* Return an iterator to the instructions comes
+   last in the execution order.  Either GSI1 and GSI2 should belong
+   to the same basic block or one of their respective basic blocks
+   should dominate the other.  */
+
+gimple_stmt_iterator
+later_of_the_two (gimple_stmt_iterator gsi1, gimple_stmt_iterator gsi2)
+{
+  basic_block bb1 = gsi_bb (gsi1);
+  basic_block bb2 = gsi_bb (gsi2);
+
+  /* Find the iterator which is the latest.  */
+  if (bb1 == bb2)
+    {
+      /* For empty basic blocks gsis point to the end of the sequence.  Since
+	 there is no operator== defined for gimple_stmt_iterator and for gsis
+	 not pointing to a valid statement gsi_next would assert.  */
+      gimple_stmt_iterator gsi = gsi1;
+      do {
+	if (gsi_stmt (gsi) == gsi_stmt (gsi2))
+	  return gsi2;
+	gsi_next (&gsi);
+      } while (!gsi_end_p (gsi));
+
+      return gsi1;
+    }
+
+  /* Find the basic block closest to the basic block which defines stmt.  */
+  if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
+    return gsi1;
+
+  gcc_assert (dominated_by_p (CDI_DOMINATORS, bb2, bb1));
+  return gsi2;
+}
+
+/* Insert each statement from SEQ at its earliest insertion p.  */
+
+static void
+gsi_insert_earliest (gimple_seq seq, sese_info_p region)
+{
+  update_modified_stmts (seq);
+  sese_l &codegen_region = region->if_region->true_region->region;
+  basic_block begin_bb = get_entry_bb (codegen_region);
+
+  /* Inserting the gimple statements in a vector because gimple_seq behave
+     in strage ways when inserting the stmts from it into different basic
+     blocks one at a time.  */
+  auto_vec<gimple *, 3> stmts;
+  for (gimple_stmt_iterator gsi = gsi_start (seq); !gsi_end_p (gsi);
+       gsi_next (&gsi))
+    stmts.safe_push (gsi_stmt (gsi));
+
+  int i;
+  gimple *use_stmt;
+  FOR_EACH_VEC_ELT (stmts, i, use_stmt)
+    {
+      gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
+      gimple_stmt_iterator gsi_def_stmt = gsi_start_bb_nondebug (begin_bb);
+
+      use_operand_p use_p;
+      ssa_op_iter op_iter;
+      FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, op_iter, SSA_OP_USE)
+	{
+	  /* Iterator to the current def of use_p.  For function parameters or
+	     anything where def is not found, insert at the beginning of the
+	     generated region.  */
+	  gimple_stmt_iterator gsi_stmt = gsi_def_stmt;
+
+	  tree op = USE_FROM_PTR (use_p);
+	  gimple *stmt = SSA_NAME_DEF_STMT (op);
+	  if (stmt && (gimple_code (stmt) != GIMPLE_NOP))
+	    gsi_stmt = gsi_for_stmt (stmt);
+
+	  /* For region parameters, insert at the beginning of the generated
+	     region.  */
+	  if (!bb_in_sese_p (gsi_bb (gsi_stmt), codegen_region))
+	    {
+	      /* The parameter should have been inserted in the parameter
+		 map or it must have a scev.  */
+	      gsi_stmt = gsi_def_stmt;
+	    }
+
+	  gsi_def_stmt = later_of_the_two (gsi_stmt, gsi_def_stmt);
+	}
+
+      if (!gsi_stmt (gsi_def_stmt))
+	{
+	  gimple_stmt_iterator gsi = gsi_after_labels (gsi_bb (gsi_def_stmt));
+	  gsi_insert_before (&gsi, use_stmt, GSI_NEW_STMT);
+	}
+      else if (gimple_code (gsi_stmt (gsi_def_stmt)) == GIMPLE_PHI)
+	{
+	  gimple_stmt_iterator bsi
+	    = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt));
+	  /* Insert right after the PHI statements.  */
+	  gsi_insert_before (&bsi, use_stmt, GSI_NEW_STMT);
+	}
+      else
+	gsi_insert_after (&gsi_def_stmt, use_stmt, GSI_NEW_STMT);
+
+      if (dump_file)
+	{
+	  fprintf (dump_file, "\n[codegen] inserting statement: ");
+	  print_gimple_stmt (dump_file, use_stmt, 0, TDF_VOPS | TDF_MEMSYMS);
+	  print_loops_bb (dump_file, gimple_bb (use_stmt), 0, 3);
+	}
+    }
+}
+
+/* Collect all the operands of NEW_EXPR by recursively visiting each
+   operand.  */
+
+static void
+collect_all_ssa_names (tree new_expr, vec<tree> *vec_ssa, sese_info_p region)
+{
+
+  /* Rename all uses in new_expr.  */
+  if (TREE_CODE (new_expr) == SSA_NAME)
+    {
+      vec_ssa->safe_push (new_expr);
+      return;
+    }
+
+  /* Iterate over SSA_NAMES in NEW_EXPR.  */
+  for (int i = 0; i < (TREE_CODE_LENGTH (TREE_CODE (new_expr))); i++)
+    {
+      tree op = TREE_OPERAND (new_expr, i);
+      collect_all_ssa_names (op, vec_ssa, region);
+    }
+}
+
+static tree
+substitute_ssa_name (tree exp, tree f, tree r)
+{
+  enum tree_code code = TREE_CODE (exp);
+  tree op0, op1, op2, op3;
+  tree new_tree;
+
+  /* We handle TREE_LIST and COMPONENT_REF separately.  */
+  if (code == TREE_LIST)
+    {
+      op0 = substitute_ssa_name (TREE_CHAIN (exp), f, r);
+      op1 = substitute_ssa_name (TREE_VALUE (exp), f, r);
+      if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
+	return exp;
+
+      return tree_cons (TREE_PURPOSE (exp), op1, op0);
+    }
+  else if (code == COMPONENT_REF)
+    {
+      tree inner;
+
+      /* If this expression is getting a value from a PLACEHOLDER_EXPR
+	 and it is the right field, replace it with R.  */
+      for (inner = TREE_OPERAND (exp, 0);
+	   REFERENCE_CLASS_P (inner);
+	   inner = TREE_OPERAND (inner, 0))
+	;
+
+      /* The field.  */
+      op1 = TREE_OPERAND (exp, 1);
+
+      if (TREE_CODE (inner) == PLACEHOLDER_EXPR && op1 == f)
+	return r;
+
+      /* If this expression hasn't been completed let, leave it alone.  */
+      if (TREE_CODE (inner) == PLACEHOLDER_EXPR && !TREE_TYPE (inner))
+	return exp;
+
+      op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r);
+      if (op0 == TREE_OPERAND (exp, 0))
+	return exp;
+
+      new_tree
+	= fold_build3 (COMPONENT_REF, TREE_TYPE (exp), op0, op1, NULL_TREE);
+   }
+  else
+    switch (TREE_CODE_CLASS (code))
+      {
+      case tcc_constant:
+	return exp;
+
+      case tcc_declaration:
+	if (exp == f)
+	  return r;
+	else
+	  return exp;
+
+      case tcc_expression:
+	if (exp == f)
+	  return r;
+
+	/* Fall through...  */
+
+      case tcc_exceptional:
+      case tcc_unary:
+      case tcc_binary:
+      case tcc_comparison:
+      case tcc_reference:
+	switch (TREE_CODE_LENGTH (code))
+	  {
+	  case 0:
+	    if (exp == f)
+	      return r;
+	    return exp;
+
+	  case 1:
+	    op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r);
+	    if (op0 == TREE_OPERAND (exp, 0))
+	      return exp;
+
+	    new_tree = fold_build1 (code, TREE_TYPE (exp), op0);
+	    break;
+
+	  case 2:
+	    op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r);
+	    op1 = substitute_ssa_name (TREE_OPERAND (exp, 1), f, r);
+
+	    if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
+	      return exp;
+
+	    new_tree = fold_build2 (code, TREE_TYPE (exp), op0, op1);
+	    break;
+
+	  case 3:
+	    op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r);
+	    op1 = substitute_ssa_name (TREE_OPERAND (exp, 1), f, r);
+	    op2 = substitute_ssa_name (TREE_OPERAND (exp, 2), f, r);
+
+	    if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
+		&& op2 == TREE_OPERAND (exp, 2))
+	      return exp;
+
+	    new_tree = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
+	    break;
+
+	  case 4:
+	    op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r);
+	    op1 = substitute_ssa_name (TREE_OPERAND (exp, 1), f, r);
+	    op2 = substitute_ssa_name (TREE_OPERAND (exp, 2), f, r);
+	    op3 = substitute_ssa_name (TREE_OPERAND (exp, 3), f, r);
+
+	    if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
+		&& op2 == TREE_OPERAND (exp, 2)
+		&& op3 == TREE_OPERAND (exp, 3))
+	      return exp;
+
+	    new_tree
+	      = fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
+	    break;
+
+	  default:
+	    gcc_unreachable ();
+	  }
+	break;
+
+      case tcc_vl_exp:
+      default:
+	gcc_unreachable ();
+      }
+
+  TREE_READONLY (new_tree) |= TREE_READONLY (exp);
+
+  if (code == INDIRECT_REF || code == ARRAY_REF || code == ARRAY_RANGE_REF)
+    TREE_THIS_NOTRAP (new_tree) |= TREE_THIS_NOTRAP (exp);
+
+  return new_tree;
+}
+
+/* Rename all the operands of NEW_EXPR by recursively visiting each operand.  */
+
+static tree
+rename_all_uses (tree new_expr, basic_block new_bb, basic_block old_bb,
+		 sese_info_p region)
+{
+  vec<tree> ssa_names;
+  ssa_names.create (2);
+  collect_all_ssa_names (new_expr, &ssa_names, region);
+  tree t;
+  int i;
+  FOR_EACH_VEC_ELT (ssa_names, i, t)
+    {
+      if (tree r = get_rename (region->rename_map, new_bb, t, old_bb, false))
+	new_expr = substitute_ssa_name (new_expr, t, r);
+      /* else
+	 return NULL_TREE;*/
+    }
+
+  return new_expr;
+}
+
+static tree
+get_rename_from_scev (tree old_name, gimple_seq *stmts, loop_p loop,
+		      basic_block new_bb, basic_block old_bb,
+		      vec<tree> iv_map, sese_info_p region, bool *gloog_error)
+{
+  tree scev = scalar_evolution_in_region (region->region, loop, old_name);
+
+  /* At this point we should know the exact scev for each
+     scalar SSA_NAME used in the scop: all the other scalar
+     SSA_NAMEs should have been translated out of SSA using
+     arrays with one element.  */
+  tree new_expr;
+  if (chrec_contains_undetermined (scev))
+    {
+      *gloog_error = true;
+      return build_zero_cst (TREE_TYPE (old_name));
+    }
+
+    new_expr = chrec_apply_map (scev, iv_map);
+
+  /* The apply should produce an expression tree containing
+     the uses of the new induction variables.  We should be
+     able to use new_expr instead of the old_name in the newly
+     generated loop nest.  */
+  if (chrec_contains_undetermined (new_expr)
+      || tree_contains_chrecs (new_expr, NULL))
+    {
+      *gloog_error = true;
+      return build_zero_cst (TREE_TYPE (old_name));
+    }
+
+  new_expr = rename_all_uses (new_expr, new_bb, old_bb, region);
+
+  /* Replace the old_name with the new_expr.  */
+  return force_gimple_operand (unshare_expr (new_expr), stmts,
+			       true, NULL_TREE);
 }
 
 /* Renames the scalar uses of the statement COPY, using the
@@ -392,13 +903,10 @@ set_rename (rename_map_type *rename_map, tree old_name, tree expr)
    is set when the code generation cannot continue.  */
 
 static bool
-rename_uses (gimple *copy, rename_map_type *rename_map,
-	     gimple_stmt_iterator *gsi_tgt,
-	     sese_info_p region, loop_p loop, vec<tree> iv_map,
-	     bool *gloog_error)
+rename_uses (gimple *copy, gimple_stmt_iterator *gsi_tgt,
+	     basic_block old_bb, sese_info_p region,
+	     loop_p loop, vec<tree> iv_map, bool *gloog_error)
 {
-  use_operand_p use_p;
-  ssa_op_iter op_iter;
   bool changed = false;
 
   if (is_gimple_debug (copy))
@@ -413,23 +921,43 @@ rename_uses (gimple *copy, rename_map_type *rename_map,
       return false;
     }
 
+  if (dump_file)
+    {
+      fprintf (dump_file, "\n[codegen] renaming uses of stmt: ");
+      print_gimple_stmt (dump_file, copy, 0, 0);
+    }
+
+  use_operand_p use_p;
+  ssa_op_iter op_iter;
   FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_USE)
     {
       tree old_name = USE_FROM_PTR (use_p);
-      tree new_expr, scev;
-      gimple_seq stmts;
+
+      if (dump_file)
+	{
+	  fprintf (dump_file, "\n[codegen] renaming old_name = ");
+	  print_generic_expr (dump_file, old_name, 0);
+	}
 
       if (TREE_CODE (old_name) != SSA_NAME
 	  || SSA_NAME_IS_DEFAULT_DEF (old_name))
 	continue;
 
       changed = true;
-      new_expr = get_rename (rename_map, old_name);
+      tree new_expr = get_rename (region->rename_map, gsi_tgt->bb, old_name,
+				  old_bb, false);
+
       if (new_expr)
 	{
 	  tree type_old_name = TREE_TYPE (old_name);
 	  tree type_new_expr = TREE_TYPE (new_expr);
 
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "\n[codegen] from rename_map: new_name = ");
+	      print_generic_expr (dump_file, new_expr, 0);
+	    }
+
 	  if (type_old_name != type_new_expr
 	      || TREE_CODE (new_expr) != SSA_NAME)
 	    {
@@ -438,44 +966,28 @@ rename_uses (gimple *copy, rename_map_type *rename_map,
 	      if (!useless_type_conversion_p (type_old_name, type_new_expr))
 		new_expr = fold_convert (type_old_name, new_expr);
 
+	      gimple_seq stmts;
 	      new_expr = force_gimple_operand (new_expr, &stmts, true, var);
-	      gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT);
+	      gsi_insert_earliest (stmts, region);
 	    }
 
 	  replace_exp (use_p, new_expr);
 	  continue;
 	}
 
-      scev = scalar_evolution_in_region (region->region, loop, old_name);
-
-      /* At this point we should know the exact scev for each
-	 scalar SSA_NAME used in the scop: all the other scalar
-	 SSA_NAMEs should have been translated out of SSA using
-	 arrays with one element.  */
-      if (chrec_contains_undetermined (scev))
-	{
-	  *gloog_error = true;
-	  new_expr = build_zero_cst (TREE_TYPE (old_name));
-	}
-      else
-	new_expr = chrec_apply_map (scev, iv_map);
+      gimple_seq stmts;
+      new_expr = get_rename_from_scev (old_name, &stmts, loop, gimple_bb (copy),
+				       old_bb, iv_map, region, gloog_error);
+      if (!new_expr || *gloog_error)
+	return false;
 
-      /* The apply should produce an expression tree containing
-	 the uses of the new induction variables.  We should be
-	 able to use new_expr instead of the old_name in the newly
-	 generated loop nest.  */
-      if (chrec_contains_undetermined (new_expr)
-	  || tree_contains_chrecs (new_expr, NULL))
+      if (dump_file)
 	{
-	  *gloog_error = true;
-	  new_expr = build_zero_cst (TREE_TYPE (old_name));
+	  fprintf (dump_file, "\n[codegen] not in rename map, scev: ");
+	  print_generic_expr (dump_file, new_expr, 0);
 	}
-      else
-	/* Replace the old_name with the new_expr.  */
-	new_expr = force_gimple_operand (unshare_expr (new_expr), &stmts,
-					 true, NULL_TREE);
 
-      gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT);
+      gsi_insert_earliest (stmts, region);
       replace_exp (use_p, new_expr);
 
       if (TREE_CODE (new_expr) == INTEGER_CST
@@ -487,73 +999,726 @@ rename_uses (gimple *copy, rename_map_type *rename_map,
 	    recompute_tree_invariant_for_addr_expr (rhs);
 	}
 
-      set_rename (rename_map, old_name, new_expr);
+      set_rename (old_name, new_expr, region);
     }
 
   return changed;
 }
 
+/* Returns a basic block that could correspond to where a constant was defined
+   in the original code.  In the original code OLD_BB had the definition, we
+   need to find which basic block out of the copies of old_bb, in the new
+   region, should a definition correspond to if it has to reach BB.  */
+
+static basic_block
+get_def_bb_for_const (sese_info_p region, basic_block bb, basic_block old_bb)
+{
+  vec <basic_block> *bbs = region->copied_bb_map->get (old_bb);
+
+  if (!bbs || bbs->is_empty ())
+    return NULL;
+
+  if (1 == bbs->length ())
+    return (*bbs)[0];
+
+  int i;
+  basic_block b1 = NULL, b2;
+  FOR_EACH_VEC_ELT (*bbs, i, b2)
+    {
+      if (b2 == bb)
+	return bb;
+
+      /* BB and B2 are in two unrelated if-clauses.  */
+      if (!dominated_by_p (CDI_DOMINATORS, bb, b2))
+	continue;
+
+      /* Compute the nearest dominator.  */
+      if (!b1 || dominated_by_p (CDI_DOMINATORS, b2, b1))
+	b1 = b2;
+    }
+
+  gcc_assert (b1);
+  return b1;
+}
+
+/* LOOP_PHI is true when we want to rename an OP within a loop PHI
+   instruction.  */
+
+static tree
+get_new_name (sese_info_p region, basic_block new_bb, tree op,
+	      basic_block old_bb, bool loop_phi)
+{
+  if (TREE_CODE (op) == INTEGER_CST
+      || TREE_CODE (op) == REAL_CST
+      || TREE_CODE (op) == COMPLEX_CST
+      || TREE_CODE (op) == VECTOR_CST)
+    return op;
+
+  return get_rename (region->rename_map, new_bb, op, old_bb, loop_phi);
+}
+
+/* Return a debug location for OP.  */
+
+static location_t
+get_loc (tree op)
+{
+  location_t loc = UNKNOWN_LOCATION;
+
+  if (TREE_CODE (op) == SSA_NAME)
+    loc = gimple_location (SSA_NAME_DEF_STMT (op));
+  return loc;
+}
+
+/* Returns the incoming edges of basic_block BB in the pair.  The first edge is
+   the init edge (from outside the loop) and the second one is the back edge
+   from the same loop.  */
+
+std::pair<edge, edge>
+get_edges (basic_block bb)
+{
+  std::pair<edge, edge> edges;
+  edge e;
+  edge_iterator ei;
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    if (bb->loop_father != e->src->loop_father)
+      edges.first = e;
+    else
+      edges.second = e;
+  return edges;
+}
+
+/* Copy the PHI arguments from OLD_PHI to the NEW_PHI.  The arguments to NEW_PHI
+   must be found unless they can be POSTPONEd for later.  */
+
+void
+copy_loop_phi_args (gphi *old_phi, init_back_edge_pair_t &ibp_old_bb,
+		    gphi *new_phi, init_back_edge_pair_t &ibp_new_bb,
+		    sese_info_p region, bool postpone)
+{
+  gcc_assert (gimple_phi_num_args (old_phi) == gimple_phi_num_args (new_phi));
+
+  basic_block new_bb = gimple_bb (new_phi);
+  for (unsigned i = 0; i < gimple_phi_num_args (old_phi); i++)
+    {
+      edge e;
+      if (gimple_phi_arg_edge (old_phi, i) == ibp_old_bb.first)
+	e = ibp_new_bb.first;
+      else
+	e = ibp_new_bb.second;
+
+      tree old_name = gimple_phi_arg_def (old_phi, i);
+      tree new_name = get_new_name (region, new_bb, old_name,
+				    gimple_bb (old_phi), true);
+      if (new_name)
+	{
+	  add_phi_arg (new_phi, new_name, e, get_loc (old_name));
+	  continue;
+	}
+
+      gimple *old_def_stmt = SSA_NAME_DEF_STMT (old_name);
+      if (!old_def_stmt || gimple_code (old_def_stmt) == GIMPLE_NOP)
+      /* If the phi arg was a function arg, or wasn't defined, just use the old
+	 name.  */
+	add_phi_arg (new_phi, old_name, e, get_loc (old_name));
+      else if (postpone)
+	{
+	  /* Postpone code gen for later for those back-edges we don't have the
+	     names yet.  */
+	  region->incomplete_phis.safe_push (std::make_pair (old_phi, new_phi));
+	  if (dump_file)
+	    fprintf (dump_file, "\n[codegen] postpone loop phi nodes: ");
+	}
+      else
+	/* Either we should add the arg to phi or, we should postpone.  */
+	gcc_unreachable ();
+    }
+}
+
+/* Copy loop phi nodes from BB to NEW_BB.  */
+
+static bool
+copy_loop_phi_nodes (basic_block bb, basic_block new_bb, sese_info_p region)
+{
+  if (dump_file)
+    fprintf (dump_file, "\n[codegen] copying loop phi nodes in bb_%d.",
+	     new_bb->index);
+
+  /* Loop phi nodes should have only two arguments.  */
+  gcc_assert (2 == EDGE_COUNT (bb->preds));
+
+  /* First edge is the init edge and second is the back edge.  */
+  init_back_edge_pair_t ibp_old_bb = get_edges (bb);
+
+  /* First edge is the init edge and second is the back edge.  */
+  init_back_edge_pair_t ibp_new_bb = get_edges (new_bb);
+
+  for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
+       gsi_next (&psi))
+    {
+      gphi *phi = psi.phi ();
+      tree res = gimple_phi_result (phi);
+      if (virtual_operand_p (res))
+	continue;
+      if (is_gimple_reg (res) && scev_analyzable_p (res, region->region))
+	continue;
+
+      gphi *new_phi = create_phi_node (SSA_NAME_VAR (res), new_bb);
+      tree new_res = create_new_def_for (res, new_phi,
+					 gimple_phi_result_ptr (new_phi));
+      set_rename (res, new_res, region);
+      copy_loop_phi_args (phi, ibp_old_bb, new_phi, ibp_new_bb, region, true);
+      update_stmt (new_phi);
+    }
+
+  return true;
+}
+
+/* Return the init value of PHI, the value coming from outside the loop.  */
+
+static tree
+get_loop_init_value (gphi *phi)
+{
+
+  loop_p loop = gimple_bb (phi)->loop_father;
+
+  edge e;
+  edge_iterator ei;
+  FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
+    if (e->src->loop_father != loop)
+      return gimple_phi_arg_def (phi, e->dest_idx);
+
+  return NULL_TREE;
+}
+
+/* Find the init value (the value which comes from outside the loop), of one of
+   the operands of DEF which is defined by a loop phi.  */
+
+static tree
+find_init_value (gimple *def)
+{
+  if (gimple_code (def) == GIMPLE_PHI)
+    return get_loop_init_value (as_a <gphi*> (def));
+
+  if (gimple_vuse (def))
+    return NULL_TREE;
+
+  ssa_op_iter iter;
+  use_operand_p use_p;
+  FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE)
+    {
+      tree use = USE_FROM_PTR (use_p);
+      if (TREE_CODE (use) == SSA_NAME)
+	{
+	  if (tree res = find_init_value (SSA_NAME_DEF_STMT (use)))
+	    return res;
+	}
+    }
+
+  return NULL_TREE;
+}
+
+/* Return the init value, the value coming from outside the loop.  */
+
+static tree
+find_init_value_close_phi (gphi *phi)
+{
+  gcc_assert (gimple_phi_num_args (phi) == 1);
+  tree use_arg = gimple_phi_arg_def (phi, 0);
+  gimple *def = SSA_NAME_DEF_STMT (use_arg);
+  return find_init_value (def);
+}
+
+/* Copy all the loop-close phi args from BB to NEW_BB.  */
+
+bool
+copy_loop_close_phi_args (basic_block old_bb, basic_block new_bb,
+			  sese_info_p region, bool postpone)
+{
+  /* The successor of bb having close phi should be a merge of the diamond
+     inserted to guard the loop during codegen.  */
+  basic_block close_phi_merge_bb = single_succ (new_bb);
+
+  for (gphi_iterator psi = gsi_start_phis (old_bb); !gsi_end_p (psi);
+       gsi_next (&psi))
+    {
+      gphi *phi = psi.phi ();
+      tree res = gimple_phi_result (phi);
+      if (virtual_operand_p (res))
+	continue;
+
+      if (is_gimple_reg (res) && scev_analyzable_p (res, region->region))
+	/* Loop close phi nodes should not be scev_analyzable_p.  */
+	gcc_unreachable ();
+
+      gphi *new_phi = create_phi_node (SSA_NAME_VAR (res), new_bb);
+      tree new_res = create_new_def_for (res, new_phi,
+					 gimple_phi_result_ptr (new_phi));
+      set_rename (res, new_res, region);
+
+      tree old_name = gimple_phi_arg_def (phi, 0);
+      tree new_name = get_new_name (region, new_bb, old_name, old_bb, false);
+
+      /* Predecessor basic blocks of a loop close phi should have been code
+	 generated before.  FIXME: This is fixable by merging PHIs from inner
+	 loops as well.  When we are looking at close-phi of an outer loop, and
+	 arguments flowing out of inner loop as not been collected by the
+	 outer-loop close phi, we will hit this situation.  For now we just bail
+	 out.  See: gfortran.dg/graphite/interchange-3.f90.  */
+      if (!new_name)
+	return false;
+
+      add_phi_arg (new_phi, new_name, single_pred_edge (new_bb),
+		   get_loc (old_name));
+      if (dump_file)
+	{
+	  fprintf (dump_file, "\n[codegen] Adding loop-closed phi: ");
+	  print_gimple_stmt (dump_file, new_phi, 0, 0);
+	}
+
+      update_stmt (new_phi);
+
+      /* When there is no loop guard around this codegenerated loop, there is no
+	 need to collect the close-phi arg.  */
+      if (2 != EDGE_COUNT (close_phi_merge_bb->preds))
+	continue;
+
+      /* Add a PHI in the close_phi_merge_bb for each close phi of the loop.  */
+      tree init = find_init_value_close_phi (new_phi);
+
+      /* A close phi must come from a loop-phi having an init value.  */
+      if (!init)
+	{
+	  gcc_assert (postpone);
+	  region->incomplete_phis.safe_push (std::make_pair (phi, new_phi));
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "\n[codegen] postpone close phi nodes: ");
+	      print_gimple_stmt (dump_file, new_phi, 0, 0);
+	    }
+	  continue;
+	}
+
+      gphi *merge_phi = create_phi_node (SSA_NAME_VAR (res),
+					 close_phi_merge_bb);
+      tree merge_res = create_new_def_for (res, merge_phi,
+					   gimple_phi_result_ptr (merge_phi));
+      set_rename (res, merge_res, region);
+
+      edge from_loop = single_succ_edge (new_bb);
+      add_phi_arg (merge_phi, new_res, from_loop, get_loc (old_name));
+
+      /* The edge coming from loop guard.  */
+      edge other = from_loop == (*close_phi_merge_bb->preds)[0]
+	? (*close_phi_merge_bb->preds)[1] : (*close_phi_merge_bb->preds)[0];
+
+      add_phi_arg (merge_phi, init, other, get_loc (old_name));
+      if (dump_file)
+	{
+	  fprintf (dump_file, "\n[codegen] Adding guard-phi: ");
+	  print_gimple_stmt (dump_file, merge_phi, 0, 0);
+	}
+
+      update_stmt (new_phi);
+    }
+
+  return true;
+}
+
+/* Copy loop close phi nodes from BB to NEW_BB.  */
+
+static bool
+copy_loop_close_phi_nodes (basic_block old_bb, basic_block new_bb,
+			   sese_info_p region)
+{
+  if (dump_file)
+    fprintf (dump_file, "\n[codegen] copying loop closed phi nodes in bb_%d.",
+	     new_bb->index);
+  /* Loop close phi nodes should have only one argument.  */
+  gcc_assert (1 == EDGE_COUNT (old_bb->preds));
+
+  return copy_loop_close_phi_args (old_bb, new_bb, region, true);
+}
+
+
+/* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
+   DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
+   other pred of OLD_BB as well.  If no such basic block exists then it is NULL.
+   NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
+   NULL.
+
+   Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
+   In this case DOMINATING_PRED = NULL.
+
+   Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
+
+   Returns true on successful copy of the args, false otherwise.  */
+
+static bool
+add_phi_arg_for_new_expr (tree old_phi_args[2], tree new_phi_args[2],
+			  edge old_bb_dominating_edge,
+			  edge old_bb_non_dominating_edge,
+			  gphi *phi, gphi *new_phi,
+			  basic_block new_bb, sese_info_p region)
+{
+  basic_block def_pred[2];
+  int not_found_bb_index = -1;
+  for (int i = 0; i < 2; i++)
+    {
+      /* If the corresponding def_bb could not be found the entry will be
+	 NULL.  */
+      if (TREE_CODE (old_phi_args[i]) == INTEGER_CST)
+	def_pred[i] = get_def_bb_for_const (region, new_bb,
+					 gimple_phi_arg_edge (phi, i)->src);
+      else
+	def_pred[i] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args[i]));
+      if (!def_pred[i])
+	{
+	  gcc_assert (not_found_bb_index == -1);
+	  not_found_bb_index = i;
+	}
+    }
+
+  /* Here we are pattern matching on the structure of CFG w.r.t. old one.  */
+  if (old_bb_dominating_edge)
+    {
+      return false;
+      basic_block new_pred1 = (*new_bb->preds)[0]->src;
+      basic_block new_pred2 = (*new_bb->preds)[1]->src;
+      vec <basic_block> *bbs
+	= region->copied_bb_map->get (old_bb_non_dominating_edge->src);
+      gcc_assert (bbs);
+      basic_block new_pred = NULL;
+      basic_block b;
+      int i;
+      FOR_EACH_VEC_ELT (*bbs, i, b)
+	if (new_pred1 == b || new_pred2 == b)
+	  {
+	    gcc_assert (!new_pred);
+	    new_pred = b;
+	  }
+
+      gcc_assert (new_pred);
+
+      edge new_non_dominating_edge = find_edge (new_pred, new_bb);
+      /* By the process of elimination we first insert insert phi-edge for
+	 non-dominating pred which is computed above and then we insert the
+	 remaining one.  */
+      int inserted_edge = 0;
+      for (; inserted_edge < 2; inserted_edge++)
+	{
+	  edge new_bb_pred_edge = gimple_phi_arg_edge (phi, inserted_edge);
+	  if (new_non_dominating_edge == new_bb_pred_edge)
+	    {
+	      add_phi_arg (new_phi, new_phi_args[inserted_edge],
+			   new_non_dominating_edge,
+			   get_loc (old_phi_args[inserted_edge]));
+	      break;
+	    }
+	}
+
+      int edge_dominating = 0;
+      if (inserted_edge == 0)
+	edge_dominating = 1;
+
+      edge new_dominating_edge = NULL;
+      for (int i; i < 2; i++)
+	{
+	  edge e = gimple_phi_arg_edge (new_phi, i);
+	  if (e != new_non_dominating_edge)
+	    new_dominating_edge = e;
+	}
+
+      add_phi_arg (new_phi, new_phi_args[edge_dominating], new_dominating_edge,
+		   get_loc (old_phi_args[inserted_edge]));
+    }
+  else
+    {
+      /* Classic diamond structure: both edges are non-dominating.  We need to
+	 find one unique edge then the other can be found be elimination.  If
+	 any definition (def_pred) dominates both the preds of new_bb then we
+	 bail out.  Entries of def_pred maybe NULL, in that case we must
+	 uniquely find pred with help of only one entry.  */
+      edge new_e[2] = { NULL, NULL };
+      for (int i = 0; i < 2; i++)
+	{
+	  edge e;
+	  edge_iterator ei;
+	  FOR_EACH_EDGE (e, ei, new_bb->preds)
+	    if (def_pred[i]
+		&& dominated_by_p (CDI_DOMINATORS, e->src, def_pred[i]))
+	      {
+		if (new_e[i])
+		  /* We do not know how to handle the case when def_pred
+		     dominates more than a predecessor.  */
+		  return false;
+		new_e[i] = e;
+	      }
+	}
+
+      gcc_assert (new_e[0] || new_e[1]);
+
+      /* Find the other edge by process of elimination.  */
+      if (not_found_bb_index != -1)
+	{
+	  gcc_assert (!new_e[not_found_bb_index]);
+	  int found_bb_index = not_found_bb_index == 1 ? 0 : 1;
+	  edge e;
+	  edge_iterator ei;
+	  FOR_EACH_EDGE (e, ei, new_bb->preds)
+	    {
+	      if (new_e[found_bb_index] == e)
+		continue;
+	      new_e[not_found_bb_index] = e;
+	    }
+	}
+
+      /* Add edges to phi args.  */
+      for (int i = 0; i < 2; i++)
+	add_phi_arg (new_phi, new_phi_args[i], new_e[i],
+		     get_loc (old_phi_args[i]));
+    }
+
+  return true;
+}
+
+/* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
+   region.  If postpone is true and it isn't possible to copy any arg of PHI,
+   the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated
+   later.  Returns false if the copying was unsuccessful.  */
+
+bool
+copy_cond_phi_args (gphi *phi, gphi *new_phi, vec<tree> iv_map,
+		    sese_info_p region, bool postpone)
+{
+  if (dump_file)
+    fprintf (dump_file, "\n[codegen] copying cond phi args: ");
+  gcc_assert (2 == gimple_phi_num_args (phi));
+
+  basic_block new_bb = gimple_bb (new_phi);
+  loop_p loop = gimple_bb (phi)->loop_father;
+
+  basic_block old_bb = gimple_bb (phi);
+  edge old_bb_non_dominating_edge = NULL, old_bb_dominating_edge = NULL;
+
+  edge e;
+  edge_iterator ei;
+  FOR_EACH_EDGE (e, ei, old_bb->preds)
+    if (!dominated_by_p (CDI_DOMINATORS, old_bb, e->src))
+      old_bb_non_dominating_edge = e;
+    else
+      old_bb_dominating_edge = e;
+
+  gcc_assert (!dominated_by_p (CDI_DOMINATORS, old_bb,
+			       old_bb_non_dominating_edge->src));
+
+  tree new_phi_args[2];
+  tree old_phi_args[2];
+
+  for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
+    {
+      tree old_name = gimple_phi_arg_def (phi, i);
+      tree new_name = get_new_name (region, new_bb, old_name, old_bb, false);
+      old_phi_args[i] = old_name;
+      if (new_name)
+	{
+	  new_phi_args [i] = new_name;
+	  continue;
+	}
+
+      if (vec_find (region->params, old_name))
+	{
+	  new_phi_args [i] = old_name;
+	  if (dump_file)
+	    {
+	      fprintf (dump_file,
+		       "\n[codegen] parameter argument to phi, new_expr: ");
+	      print_gimple_stmt (dump_file, new_phi, 0, 0);
+	    }
+	  continue;
+	}
+
+      /* If the phi-arg is scev-analyzeable but only in the first stage.  */
+      if (postpone && is_gimple_reg (old_name)
+	  && scev_analyzable_p (old_name, region->region))
+	{
+	  gimple_seq stmts;
+	  bool gloog_error = false;
+	  tree new_expr
+	    = get_rename_from_scev (old_name, &stmts, loop, new_bb,
+				    old_bb, iv_map, region, &gloog_error);
+	  if (gloog_error)
+	    return false;
+
+	  gcc_assert (new_expr);
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "\n[codegen] scev analyzeable, new_expr: ");
+	      print_generic_expr (dump_file, new_expr, 0);
+	    }
+	  gsi_insert_earliest (stmts, region);
+	  new_phi_args [i] = new_name;
+	  continue;
+	}
+
+      gimple *old_def_stmt = SSA_NAME_DEF_STMT (old_name);
+      if (!old_def_stmt || gimple_code (old_def_stmt) == GIMPLE_NOP)
+	/* If the phi arg was a function arg, or wasn't defined, just use the
+	   old name.  */
+	gcc_unreachable ();
+      else if (postpone)
+	{
+	  /* Postpone code gen for later for back-edges.  */
+	  region->incomplete_phis.safe_push (std::make_pair (phi, new_phi));
+
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "\n[codegen] postpone cond phi nodes: ");
+	      print_gimple_stmt (dump_file, new_phi, 0, 0);
+	    }
+
+	  new_phi_args [i] = NULL_TREE;
+	  continue;
+	}
+      else
+	gcc_unreachable ();
+    }
+
+  return add_phi_arg_for_new_expr (old_phi_args, new_phi_args,
+				   old_bb_dominating_edge,
+				   old_bb_non_dominating_edge,
+				   phi, new_phi, new_bb, region);
+}
+
+/* Copy cond phi nodes from BB to NEW_BB.  */
+
+static bool
+copy_cond_phi_nodes (basic_block bb, basic_block new_bb, vec<tree> iv_map,
+		     sese_info_p region)
+{
+
+  gcc_assert (!bb_contains_loop_close_phi_nodes (bb));
+
+  if (dump_file)
+    fprintf (dump_file, "\n[codegen] copying cond phi nodes in bb_%d:",
+	     new_bb->index);
+
+  /* Cond phi nodes should have exactly two arguments.  */
+  gcc_assert (2 == EDGE_COUNT (bb->preds));
+
+  for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
+       gsi_next (&psi))
+    {
+      gphi *phi = psi.phi ();
+      tree res = gimple_phi_result (phi);
+      if (virtual_operand_p (res))
+	continue;
+      if (is_gimple_reg (res) && scev_analyzable_p (res, region->region))
+	/* Cond phi nodes should not be scev_analyzable_p.  */
+	gcc_unreachable ();
+
+      gphi *new_phi = create_phi_node (SSA_NAME_VAR (res), new_bb);
+      tree new_res = create_new_def_for (res, new_phi,
+					 gimple_phi_result_ptr (new_phi));
+      set_rename (res, new_res, region);
+
+      if (!copy_cond_phi_args (phi, new_phi, iv_map, region, true))
+	return false;
+
+      update_stmt (new_phi);
+    }
+
+  return true;
+}
+
+/* Return true if STMT should be copied from region to the
+   new code-generated region.  LABELs, CONDITIONS, induction-variables
+   and region parameters need not be copied.  */
+
+static bool
+should_copy_to_new_region (gimple *stmt, sese_info_p region)
+{
+  /* Do not copy labels or conditions.  */
+  if (gimple_code (stmt) == GIMPLE_LABEL
+      || gimple_code (stmt) == GIMPLE_COND)
+    return false;
+
+  tree lhs;
+  /* Do not copy induction variables.  */
+  if (is_gimple_assign (stmt)
+      && (lhs = gimple_assign_lhs (stmt))
+      && TREE_CODE (lhs) == SSA_NAME
+      && is_gimple_reg (lhs)
+      && scev_analyzable_p (lhs, region->region))
+    return false;
+
+  return true;
+}
+
+/* Create new names for all the definitions created by COPY and
+   add replacement mappings for each new name.  */
+
+static void
+set_rename_for_each_def (gimple *stmt, sese_info_p region)
+{
+  def_operand_p def_p;
+  ssa_op_iter op_iter;
+  FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_ALL_DEFS)
+    {
+      tree old_name = DEF_FROM_PTR (def_p);
+      tree new_name = create_new_def_for (old_name, stmt, def_p);
+      set_rename (old_name, new_name, region);
+    }
+}
+
 /* Duplicates the statements of basic block BB into basic block NEW_BB
    and compute the new induction variables according to the IV_MAP.
    GLOOG_ERROR is set when the code generation cannot continue.  */
-
-static void
+static bool
 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
-				rename_map_type *rename_map,
 				vec<tree> iv_map, sese_info_p region,
 				bool *gloog_error)
 {
-  gimple_stmt_iterator gsi, gsi_tgt;
-  loop_p loop = bb->loop_father;
+  /* Iterator poining to the place where new statement (s) will be inserted.  */
+  gimple_stmt_iterator gsi_tgt = gsi_last_bb (new_bb);
 
-  gsi_tgt = gsi_start_bb (new_bb);
-  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+  for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
+       gsi_next (&gsi))
     {
-      def_operand_p def_p;
-      ssa_op_iter op_iter;
       gimple *stmt = gsi_stmt (gsi);
-      gimple *copy;
-      tree lhs;
-
-      /* Do not copy labels or conditions.  */
-      if (gimple_code (stmt) == GIMPLE_LABEL
-	  || gimple_code (stmt) == GIMPLE_COND)
-	continue;
-
-      /* Do not copy induction variables.  */
-      if (is_gimple_assign (stmt)
-	  && (lhs = gimple_assign_lhs (stmt))
-	  && TREE_CODE (lhs) == SSA_NAME
-	  && is_gimple_reg (lhs)
-	  && scev_analyzable_p (lhs, region->region))
+      if (!should_copy_to_new_region (stmt, region))
 	continue;
 
       /* Create a new copy of STMT and duplicate STMT's virtual
 	 operands.  */
-      copy = gimple_copy (stmt);
+      gimple *copy = gimple_copy (stmt);
       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
 
+      if (dump_file)
+	{
+	  fprintf (dump_file, "\n[codegen] inserting statement: ");
+	  print_gimple_stmt (dump_file, copy, 0, 0);
+	}
+
       maybe_duplicate_eh_stmt (copy, stmt);
       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
 
-      /* Create new names for all the definitions created by COPY and
-	 add replacement mappings for each new name.  */
-      FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
- 	{
- 	  tree old_name = DEF_FROM_PTR (def_p);
- 	  tree new_name = create_new_def_for (old_name, copy, def_p);
-	  set_rename (rename_map, old_name, new_name);
- 	}
+      /* Crete new names for each def in the copied stmt.  */
+      set_rename_for_each_def (copy, region);
 
-      if (rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map,
-		       gloog_error))
+      loop_p loop = bb->loop_father;
+      if (rename_uses (copy, &gsi_tgt, bb, region, loop, iv_map, gloog_error))
 	{
-	  gcc_assert (gsi_stmt (gsi_tgt) == copy);
 	  fold_stmt_inplace (&gsi_tgt);
+	  gcc_assert (gsi_stmt (gsi_tgt) == copy);
 	}
 
+      if (*gloog_error)
+	return false;
+
       update_stmt (copy);
     }
+
+  return true;
 }
 
 /* Copies BB and includes in the copied BB all the statements that can
@@ -564,17 +1729,127 @@ graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
 edge
 copy_bb_and_scalar_dependences (basic_block bb, sese_info_p region,
 				edge next_e, vec<tree> iv_map,
-				bool *gloog_error)
+				bool *codegen_err)
 {
+  int num_phis = number_of_phi_nodes (bb);
+
+  if (region->copied_bb_map->get (bb))
+    {
+      /* FIXME: We do not handle inner loop unrolling when the inner loop has
+	 phi-nodes.  In that case inner loop will be copied multiple times
+	 outside the region.  */
+      if (num_phis)
+	{
+	  *codegen_err = true;
+	  return NULL;
+	}
+    }
+
   basic_block new_bb = split_edge (next_e);
-  rename_map_type rename_map (10);
+  if (num_phis > 0 && bb_contains_loop_phi_nodes (bb))
+    {
+      basic_block phi_bb = next_e->dest->loop_father->header;
 
-  next_e = single_succ_edge (new_bb);
-  graphite_copy_stmts_from_block (bb, new_bb, &rename_map, iv_map, region,
-				  gloog_error);
-  remove_phi_nodes (new_bb);
+      /* At this point we are unable to codegenerate by still preserving the SSA
+	 structure because maybe the loop is completely unrolled and the PHIs
+	 and cross-bb scalar dependencies are untrackable w.r.t. the original
+	 code.  See gfortran.dg/graphite/pr29832.f90.  */
+      if (EDGE_COUNT (bb->preds) != EDGE_COUNT (phi_bb->preds))
+	{
+	  *codegen_err = true;
+	  return NULL;
+	}
 
-  return next_e;
+      if (dump_file)
+	fprintf (dump_file, "\n[codegen] bb_%d contains loop phi nodes",
+		 bb->index);
+      if (!copy_loop_phi_nodes (bb, phi_bb, region))
+	{
+	  *codegen_err = true;
+	  return NULL;
+	}
+    }
+  else if (bb_contains_loop_close_phi_nodes (bb))
+    {
+      if (dump_file)
+	fprintf (dump_file, "\n[codegen] bb_%d contains close phi nodes",
+		 bb->index);
+
+      /* Make sure that NEW_BB is the loop->exit->dest.  */
+      edge e = single_pred_edge (new_bb);
+      basic_block phi_bb = new_bb;
+      if (e->src->loop_father == e->dest->loop_father)
+	{
+	  /* This is one of the places which shows preserving original structure
+	     is not always possible, as we may need to insert close PHI for a
+	     loop where the latch does not have any mapping, or the mapping is
+	     ambiguous.  */
+	  basic_block old_loop_bb = single_pred_edge (bb)->src;
+	  vec <basic_block> *bbs = region->copied_bb_map->get (old_loop_bb);
+	  if (!bbs || bbs->length () != 1)
+	    {
+	      *codegen_err = true;
+	      return NULL;
+	    }
+
+	  basic_block new_loop_bb = (*bbs)[0];
+	  loop_p new_loop = new_loop_bb->loop_father;
+	  phi_bb = single_exit (new_loop)->dest;
+	  e = single_pred_edge (phi_bb);
+	}
+
+      gcc_assert (e->src->loop_father != e->dest->loop_father);
+
+      if (!copy_loop_close_phi_nodes (bb, phi_bb, region))
+	{
+	  *codegen_err = true;
+	  return NULL;
+	}
+    }
+  else if (num_phis > 0)
+    {
+      if (dump_file)
+	fprintf (dump_file, "\n[codegen] bb_%d contains cond phi nodes",
+		 bb->index);
+
+      basic_block phi_bb = single_pred (new_bb);
+      loop_p loop_father = new_bb->loop_father;
+
+      /* Move back until we find the block with two predecessors.  */
+      while (single_pred_p (phi_bb))
+	phi_bb = single_pred_edge (phi_bb)->src;
+
+      /* If a corresponding merge-point was not found, then abort codegen.  */
+      if (phi_bb->loop_father != loop_father
+	  || !copy_cond_phi_nodes (bb, phi_bb, iv_map, region))
+	{
+	  *codegen_err = true;
+	  return NULL;
+	}
+    }
+
+  if (dump_file)
+    fprintf (dump_file, "\n[codegen] copying from bb_%d to bb_%d",
+	     bb->index, new_bb->index);
+
+  vec <basic_block> *copied_bbs = region->copied_bb_map->get (bb);
+  if (copied_bbs)
+    copied_bbs->safe_push (new_bb);
+  else
+    {
+      vec<basic_block> bbs;
+      bbs.create (2);
+      bbs.safe_push (new_bb);
+      region->copied_bb_map->put (bb, bbs);
+    }
+
+  if (!graphite_copy_stmts_from_block (bb, new_bb, iv_map, region, codegen_err))
+    {
+      *codegen_err = true;
+      return NULL;
+    }
+
+  return single_succ_edge (new_bb);
 }
 
 /* Returns the outermost loop in SCOP that contains BB.  */
@@ -759,8 +2034,6 @@ set_ifsese_condition (ifsese if_region, tree condition)
 bool
 invariant_in_sese_p_rec (tree t, sese_l &region, bool *has_vdefs)
 {
-  ssa_op_iter iter;
-  use_operand_p use_p;
   if (!defined_in_sese_p (t, region))
     return true;
 
@@ -782,6 +2055,8 @@ invariant_in_sese_p_rec (tree t, sese_l &region, bool *has_vdefs)
   if (tree vuse = gimple_vuse (stmt))
     return invariant_in_sese_p_rec (vuse, region, has_vdefs);
 
+  ssa_op_iter iter;
+  use_operand_p use_p;
   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
     {
       tree use = USE_FROM_PTR (use_p);
diff --git a/gcc/sese.h b/gcc/sese.h
index b3d48b9..bce226a 100644
--- a/gcc/sese.h
+++ b/gcc/sese.h
@@ -22,6 +22,14 @@ along with GCC; see the file COPYING3.  If not see
 #ifndef GCC_SESE_H
 #define GCC_SESE_H
 
+typedef hash_map<basic_block, vec<basic_block> > bb_map_t;
+typedef hash_map<tree, vec<tree> > rename_map_t;
+typedef struct ifsese_s *ifsese;
+/* First phi is the new codegenerated phi second one is original phi.  */
+typedef std::pair <gphi *, gphi *> phi_rename;
+/* First edge is the init edge and second is the back edge w.r.t. a loop.  */
+typedef std::pair<edge, edge> init_back_edge_pair_t;
+
 /* A Single Entry, Single Exit region is a part of the CFG delimited
    by two edges.  */
 struct sese_l
@@ -50,6 +58,20 @@ get_exit_bb (sese_l &s)
   return s.exit->src;
 }
 
+/* Returns the index of V where ELEM can be found. -1 Otherwise.  */
+
+template<typename T>
+int
+vec_find (const vec<T> &v, const T &elem)
+{
+  int i;
+  T t;
+  FOR_EACH_VEC_ELT (v, i, t)
+    if (elem == t)
+      return i;
+  return -1;
+}
+
 /* A helper structure for bookkeeping information about a scop in graphite.  */
 typedef struct sese_info_t
 {
@@ -59,17 +81,29 @@ typedef struct sese_info_t
   /* Parameters used within the SCOP.  */
   vec<tree> params;
 
+  /* Maps an old name to one or more new names.  When there are several new
+     names, one has to select the definition corresponding to the immediate
+     dominator.  */
+  rename_map_t *rename_map;
+
   /* Loops completely contained in this SESE.  */
   bitmap loops;
   vec<loop_p> loop_nest;
 
   /* Basic blocks contained in this SESE.  */
   vec<basic_block> bbs;
-} *sese_info_p;
 
-#define SESE_PARAMS(S) (S->params)
-#define SESE_LOOPS(S) (S->loops)
-#define SESE_LOOP_NEST(S) (S->loop_nest)
+  /* Copied basic blocks indexed by the original bb.  */
+  bb_map_t *copied_bb_map;
+
+  /* A vector of phi nodes to be updated when all arguments are available.  The
+     pair contains first the old_phi and second the new_phi.  */
+  vec<phi_rename> incomplete_phis;
+
+  /* The condition region generated for this sese.  */
+  ifsese if_region;
+
+} *sese_info_p;
 
 extern sese_info_p new_sese_info (edge, edge);
 extern void free_sese_info (sese_info_p);
@@ -80,13 +114,23 @@ extern edge copy_bb_and_scalar_dependences (basic_block, sese_info_p, edge,
 extern struct loop *outermost_loop_in_sese (sese_l &, basic_block);
 extern tree scalar_evolution_in_region (sese_l &, loop_p, tree);
 extern bool invariant_in_sese_p_rec (tree, sese_l &, bool *);
+extern bool bb_contains_loop_phi_nodes (basic_block);
+extern bool bb_contains_loop_close_phi_nodes (basic_block);
+extern std::pair<edge, edge> get_edges (basic_block bb);
+extern void copy_loop_phi_args (gphi *, init_back_edge_pair_t &,
+				gphi *, init_back_edge_pair_t &,
+				sese_info_p, bool);
+extern bool copy_loop_close_phi_args (basic_block, basic_block,
+				      sese_info_p, bool);
+extern bool copy_cond_phi_args (gphi *, gphi *, vec<tree>,
+				sese_info_p, bool);
 
 /* Check that SESE contains LOOP.  */
 
 static inline bool
 sese_contains_loop (sese_info_p sese, struct loop *loop)
 {
-  return bitmap_bit_p (SESE_LOOPS (sese), loop->num);
+  return bitmap_bit_p (sese->loops, loop->num);
 }
 
 /* The number of parameters in REGION. */
@@ -94,7 +138,7 @@ sese_contains_loop (sese_info_p sese, struct loop *loop)
 static inline unsigned
 sese_nb_params (sese_info_p region)
 {
-  return SESE_PARAMS (region).length ();
+  return region->params.length ();
 }
 
 /* Checks whether BB is contained in the region delimited by ENTRY and
@@ -239,6 +283,8 @@ recompute_all_dominators (void)
   calculate_dominance_info (CDI_POST_DOMINATORS);
 }
 
+typedef std::pair <gimple *, tree> scalar_use;
+
 typedef struct gimple_poly_bb
 {
   basic_block bb;
@@ -267,6 +313,8 @@ typedef struct gimple_poly_bb
   vec<gimple *> conditions;
   vec<gimple *> condition_cases;
   vec<data_reference_p> data_refs;
+  vec<scalar_use> read_scalar_refs;
+  vec<tree> write_scalar_refs;
 } *gimple_poly_bb_p;
 
 #define GBB_BB(GBB) (GBB)->bb