--- a/gcc/sese.c	Sun Aug 21 07:07:55 2011 +0900
+++ b/gcc/sese.c	Fri Oct 27 22:46:09 2017 +0900
@@ -1,6 +1,5 @@
 /* Single entry single exit control flow regions.
-   Copyright (C) 2008, 2009, 2010
-   Free Software Foundation, Inc.
+   Copyright (C) 2008-2017 Free Software Foundation, Inc.
    Contributed by Jan Sjodin <jan.sjodin@amd.com> and
    Sebastian Pop <sebastian.pop@amd.com>.
 
@@ -23,187 +22,45 @@
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
+#include "backend.h"
+#include "tree.h"
+#include "gimple.h"
+#include "cfghooks.h"
+#include "tree-pass.h"
+#include "ssa.h"
 #include "tree-pretty-print.h"
-#include "tree-flow.h"
+#include "fold-const.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"
+#include "tree-into-ssa.h"
 #include "cfgloop.h"
-#include "tree-chrec.h"
 #include "tree-data-ref.h"
 #include "tree-scalar-evolution.h"
-#include "tree-pass.h"
-#include "value-prof.h"
+#include "tree-ssa-propagate.h"
+#include "cfganal.h"
 #include "sese.h"
 
-/* Print to stderr the element ELT.  */
-
-static void
-debug_rename_elt (rename_map_elt elt)
-{
-  fprintf (stderr, "(");
-  print_generic_expr (stderr, elt->old_name, 0);
-  fprintf (stderr, ", ");
-  print_generic_expr (stderr, elt->expr, 0);
-  fprintf (stderr, ")\n");
-}
-
-/* Helper function for debug_rename_map.  */
-
-static int
-debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
-{
-  struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
-  debug_rename_elt (entry);
-  return 1;
-}
-
-/* Print to stderr all the elements of RENAME_MAP.  */
-
-DEBUG_FUNCTION void
-debug_rename_map (htab_t rename_map)
-{
-  htab_traverse (rename_map, debug_rename_map_1, NULL);
-}
-
-/* Computes a hash function for database element ELT.  */
-
-hashval_t
-rename_map_elt_info (const void *elt)
-{
-  return SSA_NAME_VERSION (((const struct rename_map_elt_s *) elt)->old_name);
-}
-
-/* Compares database elements E1 and E2.  */
-
-int
-eq_rename_map_elts (const void *e1, const void *e2)
-{
-  const struct rename_map_elt_s *elt1 = (const struct rename_map_elt_s *) e1;
-  const struct rename_map_elt_s *elt2 = (const struct rename_map_elt_s *) e2;
-
-  return (elt1->old_name == elt2->old_name);
-}
-
-
-
-/* Print to stderr the element ELT.  */
-
-static void
-debug_ivtype_elt (ivtype_map_elt elt)
-{
-  fprintf (stderr, "(%s, ", elt->cloog_iv);
-  print_generic_expr (stderr, elt->type, 0);
-  fprintf (stderr, ")\n");
-}
-
-/* Helper function for debug_ivtype_map.  */
-
-static int
-debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
-{
-  struct ivtype_map_elt_s *entry = (struct ivtype_map_elt_s *) *slot;
-  debug_ivtype_elt (entry);
-  return 1;
-}
-
-/* Print to stderr all the elements of MAP.  */
-
-DEBUG_FUNCTION void
-debug_ivtype_map (htab_t map)
-{
-  htab_traverse (map, debug_ivtype_map_1, NULL);
-}
-
-/* Computes a hash function for database element ELT.  */
-
-hashval_t
-ivtype_map_elt_info (const void *elt)
-{
-  return htab_hash_pointer (((const struct ivtype_map_elt_s *) elt)->cloog_iv);
-}
-
-/* Compares database elements E1 and E2.  */
-
-int
-eq_ivtype_map_elts (const void *e1, const void *e2)
-{
-  const struct ivtype_map_elt_s *elt1 = (const struct ivtype_map_elt_s *) e1;
-  const struct ivtype_map_elt_s *elt2 = (const struct ivtype_map_elt_s *) e2;
-
-  return (elt1->cloog_iv == elt2->cloog_iv);
-}
-
-
-
-/* Record LOOP as occuring in REGION.  */
-
-static void
-sese_record_loop (sese region, loop_p loop)
-{
-  if (sese_contains_loop (region, loop))
-    return;
-
-  bitmap_set_bit (SESE_LOOPS (region), loop->num);
-  VEC_safe_push (loop_p, heap, SESE_LOOP_NEST (region), loop);
-}
-
-/* Build the loop nests contained in REGION.  Returns true when the
-   operation was successful.  */
-
-void
-build_sese_loop_nests (sese region)
-{
-  unsigned i;
-  basic_block bb;
-  struct loop *loop0, *loop1;
-
-  FOR_EACH_BB (bb)
-    if (bb_in_sese_p (bb, region))
-      {
-	struct loop *loop = bb->loop_father;
-
-	/* Only add loops if they are completely contained in the SCoP.  */
-	if (loop->header == bb
-	    && bb_in_sese_p (loop->latch, region))
-	  sese_record_loop (region, loop);
-      }
-
-  /* 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 (loop_p, SESE_LOOP_NEST (region), i, loop0)
-    {
-      if (VEC_length (loop_p, SESE_LOOP_NEST (region)) == i + 1)
-	break;
-
-      loop1 = VEC_index (loop_p, SESE_LOOP_NEST (region), i + 1);
-      if (loop0->num > loop1->num)
-	{
-	  VEC_replace (loop_p, SESE_LOOP_NEST (region), i, loop1);
-	  VEC_replace (loop_p, SESE_LOOP_NEST (region), i + 1, loop0);
-	}
-    }
-}
-
 /* For a USE in BB, if BB is outside REGION, mark the USE in the
    LIVEOUTS set.  */
 
 static void
-sese_build_liveouts_use (sese region, bitmap liveouts, basic_block bb,
+sese_build_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb,
 			 tree use)
 {
-  unsigned ver;
-  basic_block def_bb;
-
+  gcc_assert (!bb_in_sese_p (bb, region->region));
   if (TREE_CODE (use) != SSA_NAME)
     return;
 
-  ver = SSA_NAME_VERSION (use);
-  def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
+  basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
 
-  if (!def_bb
-      || !bb_in_sese_p (def_bb, region)
-      || bb_in_sese_p (bb, region))
+  if (!def_bb || !bb_in_sese_p (def_bb, region->region))
     return;
 
+  unsigned ver = SSA_NAME_VERSION (use);
   bitmap_set_bit (liveouts, ver);
 }
 
@@ -211,117 +68,96 @@
    used in BB that is outside of the REGION.  */
 
 static void
-sese_build_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
+sese_build_liveouts_bb (sese_info_p region, basic_block bb)
 {
-  gimple_stmt_iterator bsi;
-  edge e;
-  edge_iterator ei;
   ssa_op_iter iter;
   use_operand_p use_p;
 
-  FOR_EACH_EDGE (e, ei, bb->succs)
-    for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
-      sese_build_liveouts_use (region, liveouts, bb,
-			       PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
+  for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
+       gsi_next (&bsi))
+    FOR_EACH_PHI_ARG (use_p, bsi.phi (), iter, SSA_OP_USE)
+      sese_build_liveouts_use (region, region->liveout,
+			       bb, USE_FROM_PTR (use_p));
 
-  for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+  for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
+       gsi_next (&bsi))
     {
-      gimple stmt = gsi_stmt (bsi);
+      gimple *stmt = gsi_stmt (bsi);
 
+      bitmap liveouts = region->liveout;
       if (is_gimple_debug (stmt))
-	continue;
+	liveouts = region->debug_liveout;
 
-      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
+      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
 	sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
     }
 }
 
-/* For a USE in BB, return true if BB is outside REGION and it's not
-   in the LIVEOUTS set.  */
-
-static bool
-sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb,
-		       tree use)
-{
-  unsigned ver;
-  basic_block def_bb;
-
-  if (TREE_CODE (use) != SSA_NAME)
-    return false;
-
-  ver = SSA_NAME_VERSION (use);
-
-  /* If it's in liveouts, the variable will get a new PHI node, and
-     the debug use will be properly adjusted.  */
-  if (bitmap_bit_p (liveouts, ver))
-    return false;
-
-  def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
-
-  if (!def_bb
-      || !bb_in_sese_p (def_bb, region)
-      || bb_in_sese_p (bb, region))
-    return false;
-
-  return true;
-}
-
 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
    are not marked as liveouts.  */
 
 static void
-sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
+sese_reset_debug_liveouts (sese_info_p region)
 {
-  gimple_stmt_iterator bsi;
-  ssa_op_iter iter;
-  use_operand_p use_p;
-
-  for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+  bitmap_iterator bi;
+  unsigned i;
+  EXECUTE_IF_AND_COMPL_IN_BITMAP (region->debug_liveout, region->liveout,
+				  0, i, bi)
     {
-      gimple stmt = gsi_stmt (bsi);
-
-      if (!is_gimple_debug (stmt))
-	continue;
-
-      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
-	if (sese_bad_liveouts_use (region, liveouts, bb,
-				   USE_FROM_PTR (use_p)))
-	  {
-	    gimple_debug_bind_reset_value (stmt);
-	    update_stmt (stmt);
-	    break;
-	  }
+      tree name = ssa_name (i);
+      auto_vec<gimple *, 4> stmts;
+      gimple *use_stmt;
+      imm_use_iterator use_iter;
+      FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
+	{
+	  if (! is_gimple_debug (use_stmt)
+	      || bb_in_sese_p (gimple_bb (use_stmt), region->region))
+	    continue;
+	  stmts.safe_push (use_stmt);
+	}
+      while (!stmts.is_empty ())
+	{
+	  gimple *stmt = stmts.pop ();
+	  gimple_debug_bind_reset_value (stmt);
+	  update_stmt (stmt);
+	}
     }
 }
 
 /* Build the LIVEOUTS of REGION: the set of variables defined inside
    and used outside the REGION.  */
 
-static void
-sese_build_liveouts (sese region, bitmap liveouts)
+void
+sese_build_liveouts (sese_info_p region)
 {
   basic_block bb;
 
-  FOR_EACH_BB (bb)
-    sese_build_liveouts_bb (region, liveouts, bb);
-  if (MAY_HAVE_DEBUG_INSNS)
-    FOR_EACH_BB (bb)
-      sese_reset_debug_liveouts_bb (region, liveouts, bb);
+  gcc_assert (region->liveout == NULL
+	      && region->debug_liveout == NULL);
+
+  region->liveout = BITMAP_ALLOC (NULL);
+  region->debug_liveout = BITMAP_ALLOC (NULL);
+
+  /* FIXME: We could start iterating form the successor of sese.  */
+  FOR_EACH_BB_FN (bb, cfun)
+    if (!bb_in_sese_p (bb, region->region))
+      sese_build_liveouts_bb (region, bb);
 }
 
 /* Builds a new SESE region from edges ENTRY and EXIT.  */
 
-sese
-new_sese (edge entry, edge exit)
+sese_info_p
+new_sese_info (edge entry, edge exit)
 {
-  sese region = XNEW (struct sese_s);
+  sese_info_p region = XNEW (struct sese_info_t);
 
-  SESE_ENTRY (region) = entry;
-  SESE_EXIT (region) = exit;
-  SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
-  SESE_LOOP_NEST (region) = VEC_alloc (loop_p, heap, 3);
-  SESE_ADD_PARAMS (region) = true;
-  SESE_PARAMS (region) = VEC_alloc (tree, heap, 3);
+  region->region.entry = entry;
+  region->region.exit = exit;
+  region->liveout = NULL;
+  region->debug_liveout = NULL;
+  region->params.create (3);
+  region->rename_map = new hash_map <tree, tree>;
+  region->bbs.create (3);
 
   return region;
 }
@@ -329,13 +165,15 @@
 /* Deletes REGION.  */
 
 void
-free_sese (sese region)
+free_sese_info (sese_info_p region)
 {
-  if (SESE_LOOPS (region))
-    SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
+  region->params.release ();
+  BITMAP_FREE (region->liveout);
+  BITMAP_FREE (region->debug_liveout);
 
-  VEC_free (tree, heap, SESE_PARAMS (region));
-  VEC_free (loop_p, heap, SESE_LOOP_NEST (region));
+  delete region->rename_map;
+  region->rename_map = NULL;
+  region->bbs.release ();
 
   XDELETE (region);
 }
@@ -345,12 +183,11 @@
 static void
 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
 {
-  gimple phi = create_phi_node (use, exit);
-
-  create_new_def_for (gimple_phi_result (phi), phi,
-		      gimple_phi_result_ptr (phi));
+  gphi *phi = create_phi_node (NULL_TREE, exit);
+  create_new_def_for (use, phi, gimple_phi_result_ptr (phi));
   add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
   add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
+  update_stmt (phi);
 }
 
 /* Insert in the block BB phi nodes for variables defined in REGION
@@ -365,21 +202,58 @@
 */
 
 void
-sese_insert_phis_for_liveouts (sese region, basic_block bb,
+sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb,
 			       edge false_e, edge true_e)
 {
+  if (MAY_HAVE_DEBUG_STMTS)
+    sese_reset_debug_liveouts (region);
+
   unsigned i;
   bitmap_iterator bi;
-  bitmap liveouts = BITMAP_ALLOC (NULL);
+  EXECUTE_IF_SET_IN_BITMAP (region->liveout, 0, i, bi)
+    if (!virtual_operand_p (ssa_name (i)))
+      sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
+}
+
+/* Returns the outermost loop in SCOP that contains BB.  */
 
-  update_ssa (TODO_update_ssa);
+struct loop *
+outermost_loop_in_sese_1 (sese_l &region, basic_block bb)
+{
+  struct loop *nest;
+
+  nest = bb->loop_father;
+  while (loop_outer (nest)
+	 && loop_in_sese_p (loop_outer (nest), region))
+    nest = loop_outer (nest);
+
+  return nest;
+}
 
-  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);
-  BITMAP_FREE (liveouts);
+/* Same as outermost_loop_in_sese_1, returns the outermost loop
+   containing BB in REGION, but makes sure that the returned loop
+   belongs to the REGION, and so this returns the first loop in the
+   REGION when the loop containing BB does not belong to REGION.  */
+
+loop_p
+outermost_loop_in_sese (sese_l &region, basic_block bb)
+{
+  loop_p nest = outermost_loop_in_sese_1 (region, bb);
 
-  update_ssa (TODO_update_ssa);
+  if (loop_in_sese_p (nest, region))
+    return nest;
+
+  /* When the basic block BB does not belong to a loop in the region,
+     return the first loop in the region.  */
+  nest = nest->inner;
+  while (nest)
+    if (loop_in_sese_p (nest, region))
+      break;
+    else
+      nest = nest->next;
+
+  gcc_assert (nest);
+  return nest;
 }
 
 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set.  */
@@ -414,324 +288,6 @@
   return NULL;
 }
 
-/* Returns the expression associated to OLD_NAME in RENAME_MAP.  */
-
-static tree
-get_rename (htab_t rename_map, tree old_name)
-{
-  struct rename_map_elt_s tmp;
-  PTR *slot;
-
-  gcc_assert (TREE_CODE (old_name) == SSA_NAME);
-  tmp.old_name = old_name;
-  slot = htab_find_slot (rename_map, &tmp, NO_INSERT);
-
-  if (slot && *slot)
-    return ((rename_map_elt) *slot)->expr;
-
-  return NULL_TREE;
-}
-
-/* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).  */
-
-static void
-set_rename (htab_t rename_map, tree old_name, tree expr)
-{
-  struct rename_map_elt_s tmp;
-  PTR *slot;
-
-  if (old_name == expr)
-    return;
-
-  tmp.old_name = old_name;
-  slot = htab_find_slot (rename_map, &tmp, INSERT);
-
-  if (!slot)
-    return;
-
-  if (*slot)
-    free (*slot);
-
-  *slot = new_rename_map_elt (old_name, expr);
-}
-
-/* Renames the scalar uses of the statement COPY, using the
-   substitution map RENAME_MAP, inserting the gimplification code at
-   GSI_TGT, for the translation REGION, with the original copied
-   statement in LOOP, and using the induction variable renaming map
-   IV_MAP.  Returns true when something has been renamed.  */
-
-static bool
-rename_uses (gimple copy, htab_t rename_map, gimple_stmt_iterator *gsi_tgt,
-	     sese region, loop_p loop, VEC (tree, heap) *iv_map)
-{
-  use_operand_p use_p;
-  ssa_op_iter op_iter;
-  bool changed = false;
-
-  if (is_gimple_debug (copy))
-    {
-      if (gimple_debug_bind_p (copy))
-	gimple_debug_bind_reset_value (copy);
-      else
-	gcc_unreachable ();
-
-      return false;
-    }
-
-  FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_ALL_USES)
-    {
-      tree old_name = USE_FROM_PTR (use_p);
-      tree new_expr, scev;
-      gimple_seq stmts;
-
-      if (TREE_CODE (old_name) != SSA_NAME
-	  || !is_gimple_reg (old_name)
-	  || SSA_NAME_IS_DEFAULT_DEF (old_name))
-	continue;
-
-      changed = true;
-      new_expr = get_rename (rename_map, old_name);
-      if (new_expr)
-	{
-	  tree type_old_name = TREE_TYPE (old_name);
-	  tree type_new_expr = TREE_TYPE (new_expr);
-
-	  if (type_old_name != type_new_expr
-	      || (TREE_CODE (new_expr) != SSA_NAME
-		  && is_gimple_reg (old_name)))
-	    {
-	      tree var = create_tmp_var (type_old_name, "var");
-
-	      if (type_old_name != type_new_expr)
-		new_expr = fold_convert (type_old_name, new_expr);
-
-	      new_expr = build2 (MODIFY_EXPR, type_old_name, var, new_expr);
-	      new_expr = force_gimple_operand (new_expr, &stmts, true, NULL);
-	      gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT);
-	    }
-
-	  replace_exp (use_p, new_expr);
-	  continue;
-	}
-
-      scev = scalar_evolution_in_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.  */
-      gcc_assert (!chrec_contains_undetermined (scev));
-
-      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.  */
-      gcc_assert (!chrec_contains_undetermined (new_expr)
-		  && !tree_contains_chrecs (new_expr, NULL));
-
-      /* 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);
-      replace_exp (use_p, new_expr);
-
-      if (TREE_CODE (new_expr) == INTEGER_CST
-	  && is_gimple_assign (copy))
-	{
-	  tree rhs = gimple_assign_rhs1 (copy);
-
-	  if (TREE_CODE (rhs) == ADDR_EXPR)
-	    recompute_tree_invariant_for_addr_expr (rhs);
-	}
-
-      set_rename (rename_map, old_name, new_expr);
-    }
-
-  return changed;
-}
-
-/* Duplicates the statements of basic block BB into basic block NEW_BB
-   and compute the new induction variables according to the IV_MAP.  */
-
-static void
-graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
-				htab_t rename_map,
-				VEC (tree, heap) *iv_map, sese region)
-{
-  gimple_stmt_iterator gsi, gsi_tgt;
-  loop_p loop = bb->loop_father;
-
-  gsi_tgt = gsi_start_bb (new_bb);
-  for (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))
-	continue;
-
-      /* Create a new copy of STMT and duplicate STMT's virtual
-	 operands.  */
-      copy = gimple_copy (stmt);
-      gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
-      mark_sym_for_renaming (gimple_vop (cfun));
-
-      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);
- 	}
-
-      if (rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map))
-	fold_stmt_inplace (copy);
-
-      update_stmt (copy);
-    }
-}
-
-/* Copies BB and includes in the copied BB all the statements that can
-   be reached following the use-def chains from the memory accesses,
-   and returns the next edge following this new block.  */
-
-edge
-copy_bb_and_scalar_dependences (basic_block bb, sese region,
-				edge next_e, VEC (tree, heap) *iv_map)
-{
-  basic_block new_bb = split_edge (next_e);
-  htab_t rename_map = htab_create (10, rename_map_elt_info,
-				   eq_rename_map_elts, free);
-
-  next_e = single_succ_edge (new_bb);
-  graphite_copy_stmts_from_block (bb, new_bb, rename_map, iv_map, region);
-  remove_phi_nodes (new_bb);
-  htab_delete (rename_map);
-
-  return next_e;
-}
-
-/* Returns the outermost loop in SCOP that contains BB.  */
-
-struct loop *
-outermost_loop_in_sese (sese region, basic_block bb)
-{
-  struct loop *nest;
-
-  nest = bb->loop_father;
-  while (loop_outer (nest)
-	 && loop_in_sese_p (loop_outer (nest), region))
-    nest = loop_outer (nest);
-
-  return nest;
-}
-
-/* Sets the false region of an IF_REGION to REGION.  */
-
-void
-if_region_set_false_region (ifsese if_region, sese region)
-{
-  basic_block condition = if_region_get_condition_block (if_region);
-  edge false_edge = get_false_edge_from_guard_bb (condition);
-  basic_block dummy = false_edge->dest;
-  edge entry_region = SESE_ENTRY (region);
-  edge exit_region = SESE_EXIT (region);
-  basic_block before_region = entry_region->src;
-  basic_block last_in_region = exit_region->src;
-  void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
-					  htab_hash_pointer (exit_region),
-					  NO_INSERT);
-
-  entry_region->flags = false_edge->flags;
-  false_edge->flags = exit_region->flags;
-
-  redirect_edge_pred (entry_region, condition);
-  redirect_edge_pred (exit_region, before_region);
-  redirect_edge_pred (false_edge, last_in_region);
-  redirect_edge_succ (false_edge, single_succ (dummy));
-  delete_basic_block (dummy);
-
-  exit_region->flags = EDGE_FALLTHRU;
-  recompute_all_dominators ();
-
-  SESE_EXIT (region) = false_edge;
-
-  if (if_region->false_region)
-    free (if_region->false_region);
-  if_region->false_region = region;
-
-  if (slot)
-    {
-      struct loop_exit *loop_exit = ggc_alloc_cleared_loop_exit ();
-
-      memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
-      htab_clear_slot (current_loops->exits, slot);
-
-      slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
-				       htab_hash_pointer (false_edge),
-				       INSERT);
-      loop_exit->e = false_edge;
-      *slot = loop_exit;
-      false_edge->src->loop_father->exits->next = loop_exit;
-    }
-}
-
-/* Creates an IFSESE with CONDITION on edge ENTRY.  */
-
-static ifsese
-create_if_region_on_edge (edge entry, tree condition)
-{
-  edge e;
-  edge_iterator ei;
-  sese sese_region = XNEW (struct sese_s);
-  sese true_region = XNEW (struct sese_s);
-  sese false_region = XNEW (struct sese_s);
-  ifsese if_region = XNEW (struct ifsese_s);
-  edge exit = create_empty_if_region_on_edge (entry, condition);
-
-  if_region->region = sese_region;
-  if_region->region->entry = entry;
-  if_region->region->exit = exit;
-
-  FOR_EACH_EDGE (e, ei, entry->dest->succs)
-    {
-      if (e->flags & EDGE_TRUE_VALUE)
-	{
-	  true_region->entry = e;
-	  true_region->exit = single_succ_edge (e->dest);
-	  if_region->true_region = true_region;
-	}
-      else if (e->flags & EDGE_FALSE_VALUE)
-	{
-	  false_region->entry = e;
-	  false_region->exit = single_succ_edge (e->dest);
-	  if_region->false_region = false_region;
-	}
-    }
-
-  return if_region;
-}
-
 /* Moves REGION in a condition expression:
    | if (1)
    |   ;
@@ -740,14 +296,36 @@
 */
 
 ifsese
-move_sese_in_condition (sese region)
+move_sese_in_condition (sese_info_p region)
 {
-  basic_block pred_block = split_edge (SESE_ENTRY (region));
-  ifsese if_region;
+  basic_block region_entry_dest = region->region.entry->dest;
+  basic_block pred_block = split_edge (region->region.entry);
+  basic_block merge_block = split_edge (region->region.exit);
 
-  SESE_ENTRY (region) = single_succ_edge (pred_block);
-  if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
-  if_region_set_false_region (if_region, region);
+  edge true_edge = make_edge (pred_block, merge_block, EDGE_TRUE_VALUE);
+  edge false_edge = find_edge (pred_block, region_entry_dest);
+  false_edge->flags &= ~EDGE_FALLTHRU;
+  false_edge->flags |= EDGE_FALSE_VALUE;
+  gimple_stmt_iterator gsi = gsi_last_bb (pred_block);
+  gcond *cond = gimple_build_cond (NE_EXPR, integer_one_node, integer_zero_node,
+				   NULL_TREE, NULL_TREE);
+  gsi_insert_after (&gsi, cond, GSI_CONTINUE_LINKING);
+  if (dom_info_available_p (CDI_DOMINATORS))
+    set_immediate_dominator (CDI_DOMINATORS, merge_block, pred_block);
+
+  ifsese if_region = XNEW (ifsese_s);
+  if_region->region = XCNEW (sese_info_t);
+  if_region->true_region = XCNEW (sese_info_t);
+  if_region->false_region = XCNEW (sese_info_t);
+  if_region->region->region.entry = single_pred_edge (pred_block);
+  if_region->region->region.exit = single_succ_edge (merge_block);
+  if_region->false_region->region.entry = false_edge;
+  if_region->false_region->region.exit = region->region.exit;
+  if_region->true_region->region.entry = true_edge;
+  if_region->true_region->region.exit
+    = single_succ_edge (split_edge (true_edge));
+
+  region->region = if_region->false_region->region;
 
   return if_region;
 }
@@ -762,12 +340,12 @@
 void
 set_ifsese_condition (ifsese if_region, tree condition)
 {
-  sese region = if_region->region;
-  edge entry = region->entry;
+  sese_info_p region = if_region->region;
+  edge entry = region->region.entry;
   basic_block bb = entry->dest;
-  gimple last = last_stmt (bb);
+  gimple *last = last_stmt (bb);
   gimple_stmt_iterator gsi = gsi_last_bb (bb);
-  gimple cond_stmt;
+  gcond *cond_stmt;
 
   gcc_assert (gimple_code (last) == GIMPLE_COND);
 
@@ -780,36 +358,145 @@
   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
 }
 
+/* Return true when T is defined outside REGION or when no definitions are
+   variant in REGION.  When HAS_VDEFS is a valid pointer, sets HAS_VDEFS to true
+   when T depends on memory that may change in REGION.  */
+
+bool
+invariant_in_sese_p_rec (tree t, const sese_l &region, bool *has_vdefs)
+{
+  if (!defined_in_sese_p (t, region))
+    return true;
+
+  gimple *stmt = SSA_NAME_DEF_STMT (t);
+
+  if (gimple_code (stmt) == GIMPLE_PHI
+      || gimple_code (stmt) == GIMPLE_CALL)
+    return false;
+
+  /* VDEF is variant when it is in the region.  */
+  if (gimple_vdef (stmt))
+    {
+      if (has_vdefs)
+	*has_vdefs = true;
+      return false;
+    }
+
+  /* A VUSE may or may not be variant following the 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);
+
+      if (!defined_in_sese_p (use, region))
+	continue;
+
+      if (!invariant_in_sese_p_rec (use, region, has_vdefs))
+	return false;
+    }
+
+  return true;
+}
+
+/* Return true when DEF can be analyzed in REGION by the scalar
+   evolution analyzer.  */
+
+bool
+scev_analyzable_p (tree def, sese_l &region)
+{
+  loop_p loop;
+  tree scev;
+  tree type = TREE_TYPE (def);
+
+  /* When Graphite generates code for a scev, the code generator
+     expresses the scev in function of a single induction variable.
+     This is unsafe for floating point computations, as it may replace
+     a floating point sum reduction with a multiplication.  The
+     following test returns false for non integer types to avoid such
+     problems.  */
+  if (!INTEGRAL_TYPE_P (type)
+      && !POINTER_TYPE_P (type))
+    return false;
+
+  loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
+  scev = scalar_evolution_in_region (region, loop, def);
+
+  return (!chrec_contains_undetermined (scev)
+	  && (TREE_CODE (scev) != SSA_NAME
+	      || !defined_in_sese_p (scev, region))
+	  && scev_is_linear_expression (scev)
+	  && (! loop
+	      || ! loop_in_sese_p (loop, region)
+	      || ! chrec_contains_symbols_defined_in_loop (scev, loop->num)));
+}
+
 /* Returns the scalar evolution of T in REGION.  Every variable that
    is not defined in the REGION is considered a parameter.  */
 
 tree
-scalar_evolution_in_region (sese region, loop_p loop, tree t)
+scalar_evolution_in_region (const sese_l &region, loop_p loop, tree t)
 {
-  gimple def;
-  struct loop *def_loop;
-  basic_block before = block_before_sese (region);
-
   /* SCOP parameters.  */
   if (TREE_CODE (t) == SSA_NAME
       && !defined_in_sese_p (t, region))
     return t;
 
-  if (TREE_CODE (t) != SSA_NAME
-      || loop_in_sese_p (loop, region))
-    return instantiate_scev (before, loop,
-			     analyze_scalar_evolution (loop, t));
+  if (!loop_in_sese_p (loop, region))
+    loop = NULL;
+
+  return instantiate_scev (region.entry, loop,
+			   analyze_scalar_evolution (loop, t));
+}
+
+/* Return true if BB is empty, contains only DEBUG_INSNs.  */
 
-  def = SSA_NAME_DEF_STMT (t);
-  def_loop = loop_containing_stmt (def);
+bool
+sese_trivially_empty_bb_p (basic_block bb)
+{         
+  gimple_stmt_iterator gsi;
+
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    if (gimple_code (gsi_stmt (gsi)) != GIMPLE_DEBUG
+	&& gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
+      return false;
+
+  return true;
+}
+
+/* Pretty print edge E to FILE.  */
 
-  if (loop_in_sese_p (def_loop, region))
-    {
-      t = analyze_scalar_evolution (def_loop, t);
-      def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
-      t = compute_overall_effect_of_inner_loop (def_loop, t);
-      return t;
-    }
-  else
-    return instantiate_scev (before, loop, t);
+void
+print_edge (FILE *file, const_edge e)
+{
+  fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index);
+}
+
+/* Pretty print sese S to FILE.  */
+
+void
+print_sese (FILE *file, const sese_l &s)
+{
+  fprintf (file, "(entry_"); print_edge (file, s.entry);
+  fprintf (file, ", exit_"); print_edge (file, s.exit);
+  fprintf (file, ")\n");
 }
+
+/* Pretty print edge E to STDERR.  */
+
+DEBUG_FUNCTION void
+debug_edge (const_edge e)
+{
+  print_edge (stderr, e);
+}
+
+/* Pretty print sese S to STDERR.  */
+
+DEBUG_FUNCTION void
+debug_sese (const sese_l &s)
+{
+  print_sese (stderr, s);
+}