diff gcc/tree-ssa-loop-unswitch.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
line wrap: on
line diff
--- a/gcc/tree-ssa-loop-unswitch.c	Sun Aug 21 07:07:55 2011 +0900
+++ b/gcc/tree-ssa-loop-unswitch.c	Fri Oct 27 22:46:09 2017 +0900
@@ -1,5 +1,5 @@
 /* Loop unswitching.
-   Copyright (C) 2004, 2005, 2007, 2008, 2010 Free Software Foundation, Inc.
+   Copyright (C) 2004-2017 Free Software Foundation, Inc.
 
 This file is part of GCC.
 
@@ -20,18 +20,24 @@
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
-#include "tm.h"
+#include "backend.h"
 #include "tree.h"
-#include "tm_p.h"
-#include "basic-block.h"
-#include "output.h"
-#include "tree-flow.h"
-#include "tree-dump.h"
-#include "timevar.h"
+#include "gimple.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "fold-const.h"
+#include "gimplify.h"
+#include "tree-cfg.h"
+#include "tree-ssa.h"
+#include "tree-ssa-loop-niter.h"
+#include "tree-ssa-loop.h"
+#include "tree-into-ssa.h"
 #include "cfgloop.h"
 #include "params.h"
-#include "tree-pass.h"
 #include "tree-inline.h"
+#include "gimple-iterator.h"
+#include "cfghooks.h"
+#include "tree-ssa-loop-manip.h"
 
 /* This file implements the loop unswitching, i.e. transformation of loops like
 
@@ -72,40 +78,30 @@
 static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
 static bool tree_unswitch_single_loop (struct loop *, int);
 static tree tree_may_unswitch_on (basic_block, struct loop *);
+static bool tree_unswitch_outer_loop (struct loop *);
+static edge find_loop_guard (struct loop *);
+static bool empty_bb_without_guard_p (struct loop *, basic_block);
+static bool used_outside_loop_p (struct loop *, tree);
+static void hoist_guard (struct loop *, edge);
+static bool check_exit_phi (struct loop *);
+static tree get_vop_from_header (struct loop *);
 
 /* Main entry point.  Perform loop unswitching on all suitable loops.  */
 
 unsigned int
 tree_ssa_unswitch_loops (void)
 {
-  loop_iterator li;
   struct loop *loop;
   bool changed = false;
 
-  /* Go through inner loops (only original ones).  */
-  FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
+  /* Go through all loops starting from innermost.  */
+  FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
     {
-      if (dump_file && (dump_flags & TDF_DETAILS))
-        fprintf (dump_file, ";; Considering loop %d\n", loop->num);
-
-      /* Do not unswitch in cold regions. */
-      if (optimize_loop_for_size_p (loop))
-        {
-          if (dump_file && (dump_flags & TDF_DETAILS))
-            fprintf (dump_file, ";; Not unswitching cold loops\n");
-          continue;
-        }
-
-      /* The loop should not be too large, to limit code growth. */
-      if (tree_num_loop_insns (loop, &eni_size_weights)
-          > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
-        {
-          if (dump_file && (dump_flags & TDF_DETAILS))
-            fprintf (dump_file, ";; Not unswitching, loop too big\n");
-          continue;
-        }
-
-      changed |= tree_unswitch_single_loop (loop, 0);
+      if (!loop->inner)
+	/* Unswitch innermost loop.  */
+	changed |= tree_unswitch_single_loop (loop, 0);
+      else
+	changed |= tree_unswitch_outer_loop (loop);
     }
 
   if (changed)
@@ -113,21 +109,97 @@
   return 0;
 }
 
+/* Return TRUE if an SSA_NAME maybe undefined and is therefore
+   unsuitable for unswitching.  STMT is the statement we are
+   considering for unswitching and LOOP is the loop it appears in.  */
+
+static bool
+is_maybe_undefined (const tree name, gimple *stmt, struct loop *loop)
+{
+  /* The loop header is the only block we can trivially determine that
+     will always be executed.  If the comparison is in the loop
+     header, we know it's OK to unswitch on it.  */
+  if (gimple_bb (stmt) == loop->header)
+    return false;
+
+  auto_bitmap visited_ssa;
+  auto_vec<tree> worklist;
+  worklist.safe_push (name);
+  bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name));
+  while (!worklist.is_empty ())
+    {
+      tree t = worklist.pop ();
+
+      /* If it's obviously undefined, avoid further computations.  */
+      if (ssa_undefined_value_p (t, true))
+	return true;
+
+      if (ssa_defined_default_def_p (t))
+	continue;
+
+      gimple *def = SSA_NAME_DEF_STMT (t);
+
+      /* Check that all the PHI args are fully defined.  */
+      if (gphi *phi = dyn_cast <gphi *> (def))
+	{
+	  for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
+	    {
+	      tree t = gimple_phi_arg_def (phi, i);
+	      /* If an SSA has already been seen, it may be a loop,
+		 but we can continue and ignore this use.  Otherwise,
+		 add the SSA_NAME to the queue and visit it later.  */
+	      if (TREE_CODE (t) == SSA_NAME
+		  && bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
+		worklist.safe_push (t);
+	    }
+	  continue;
+	}
+
+      /* Uses in stmts always executed when the region header executes
+	 are fine.  */
+      if (dominated_by_p (CDI_DOMINATORS, loop->header, gimple_bb (def)))
+	continue;
+
+      /* Handle calls and memory loads conservatively.  */
+      if (!is_gimple_assign (def)
+	  || (gimple_assign_single_p (def)
+	      && gimple_vuse (def)))
+	return true;
+
+      /* Check that any SSA names used to define NAME are also fully
+	 defined.  */
+      use_operand_p use_p;
+      ssa_op_iter iter;
+      FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE)
+	{
+	  tree t = USE_FROM_PTR (use_p);
+	  /* If an SSA has already been seen, it may be a loop,
+	     but we can continue and ignore this use.  Otherwise,
+	     add the SSA_NAME to the queue and visit it later.  */
+	  if (bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
+	    worklist.safe_push (t);
+	}
+    }
+  return false;
+}
+
 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
    basic blocks (for what it means see comments below).  */
 
 static tree
 tree_may_unswitch_on (basic_block bb, struct loop *loop)
 {
-  gimple stmt, def;
+  gimple *last, *def;
+  gcond *stmt;
   tree cond, use;
   basic_block def_bb;
   ssa_op_iter iter;
 
   /* BB must end in a simple conditional jump.  */
-  stmt = last_stmt (bb);
-  if (!stmt || gimple_code (stmt) != GIMPLE_COND)
+  last = last_stmt (bb);
+  if (!last || gimple_code (last) != GIMPLE_COND)
     return NULL_TREE;
+  stmt = as_a <gcond *> (last);
 
   /* To keep the things simple, we do not directly remove the conditions,
      but just replace tests with 0 != 0 resp. 1 != 0.  Prevent the infinite
@@ -143,6 +215,10 @@
       if (def_bb
 	  && flow_bb_inside_loop_p (loop, def_bb))
 	return NULL_TREE;
+      /* Unswitching on undefined values would introduce undefined
+	 behavior that the original program might never exercise.  */
+      if (is_maybe_undefined (use, stmt, loop))
+	return NULL_TREE;
     }
 
   cond = build2 (gimple_cond_code (stmt), boolean_type_node,
@@ -159,7 +235,7 @@
 simplify_using_entry_checks (struct loop *loop, tree cond)
 {
   edge e = loop_preheader_edge (loop);
-  gimple stmt;
+  gimple *stmt;
 
   while (1)
     {
@@ -179,7 +255,7 @@
 	return cond;
 
       e = single_pred_edge (e->src);
-      if (e->src == ENTRY_BLOCK_PTR)
+      if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
 	return cond;
     }
 }
@@ -195,8 +271,43 @@
   struct loop *nloop;
   unsigned i, found;
   tree cond = NULL_TREE;
-  gimple stmt;
+  gimple *stmt;
   bool changed = false;
+  HOST_WIDE_INT iterations;
+
+  /* Perform initial tests if unswitch is eligible.  */
+  if (num == 0)
+    {
+      /* Do not unswitch in cold regions. */
+      if (optimize_loop_for_size_p (loop))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, ";; Not unswitching cold loops\n");
+	  return false;
+	}
+
+      /* The loop should not be too large, to limit code growth. */
+      if (tree_num_loop_insns (loop, &eni_size_weights)
+	  > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, ";; Not unswitching, loop too big\n");
+	  return false;
+	}
+
+      /* If the loop is not expected to iterate, there is no need
+	 for unswitching.  */
+      iterations = estimated_loop_iterations_int (loop);
+      if (iterations < 0)
+        iterations = likely_max_loop_iterations_int (loop);
+      if (iterations >= 0 && iterations <= 1)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, ";; Not unswitching, loop is not expected"
+		     " to iterate\n");
+	  return false;
+	}
+    }
 
   i = 0;
   bbs = get_loop_body (loop);
@@ -229,13 +340,15 @@
       if (integer_nonzerop (cond))
 	{
 	  /* Remove false path.  */
-	  gimple_cond_set_condition_from_tree (stmt, boolean_true_node);
+	  gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
+					       boolean_true_node);
 	  changed = true;
 	}
       else if (integer_zerop (cond))
 	{
 	  /* Remove true path.  */
-	  gimple_cond_set_condition_from_tree (stmt, boolean_false_node);
+	  gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
+					       boolean_false_node);
 	  changed = true;
 	}
       /* Do not unswitch too much.  */
@@ -293,13 +406,14 @@
 
 	  if (EDGE_COUNT (b->succs) == 2)
 	    {
-	      gimple stmt = last_stmt (b);
+	      gimple *stmt = last_stmt (b);
 	      if (stmt
 		  && gimple_code (stmt) == GIMPLE_COND)
 		{
-		  if (gimple_cond_true_p (stmt))
+		  gcond *cond_stmt = as_a <gcond *> (stmt);
+		  if (gimple_cond_true_p (cond_stmt))
 		    flags = EDGE_FALSE_VALUE;
-		  else if (gimple_cond_false_p (stmt))
+		  else if (gimple_cond_false_p (cond_stmt))
 		    flags = EDGE_TRUE_VALUE;
 		}
 	    }
@@ -366,7 +480,7 @@
 tree_unswitch_loop (struct loop *loop,
 		    basic_block unswitch_on, tree cond)
 {
-  unsigned prob_true;
+  profile_probability prob_true;
   edge edge_true, edge_false;
 
   /* Some sanity checking.  */
@@ -377,6 +491,528 @@
   extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
   prob_true = edge_true->probability;
   return loop_version (loop, unshare_expr (cond),
-		       NULL, prob_true, prob_true,
-		       REG_BR_PROB_BASE - prob_true, false);
+		       NULL, prob_true,
+		       prob_true.invert (),
+		       prob_true, prob_true.invert (),
+		       false);
+}
+
+/* Unswitch outer loops by hoisting invariant guard on
+   inner loop without code duplication.  */
+static bool
+tree_unswitch_outer_loop (struct loop *loop)
+{
+  edge exit, guard;
+  HOST_WIDE_INT iterations;
+
+  gcc_assert (loop->inner);
+  if (loop->inner->next)
+    return false;
+  /* Accept loops with single exit only which is not from inner loop.  */
+  exit = single_exit (loop);
+  if (!exit || exit->src->loop_father != loop)
+    return false;
+  /* Check that phi argument of exit edge is not defined inside loop.  */
+  if (!check_exit_phi (loop))
+    return false;
+  /* If the loop is not expected to iterate, there is no need
+      for unswitching.  */
+  iterations = estimated_loop_iterations_int (loop);
+  if (iterations < 0)
+    iterations = likely_max_loop_iterations_int (loop);
+  if (iterations >= 0 && iterations <= 1)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, ";; Not unswitching, loop is not expected"
+		 " to iterate\n");
+      return false;
+    }
+
+  bool changed = false;
+  while ((guard = find_loop_guard (loop)))
+    {
+      if (! changed)
+	rewrite_virtuals_into_loop_closed_ssa (loop);
+      hoist_guard (loop, guard);
+      changed = true;
+    }
+  return changed;
+}
+
+/* Checks if the body of the LOOP is within an invariant guard.  If this
+   is the case, returns the edge that jumps over the real body of the loop,
+   otherwise returns NULL.  */
+
+static edge
+find_loop_guard (struct loop *loop)
+{
+  basic_block header = loop->header;
+  edge guard_edge, te, fe;
+  basic_block *body = NULL;
+  unsigned i;
+  tree use;
+  ssa_op_iter iter;
+
+  /* We check for the following situation:
+
+     while (1)
+       {
+	 [header]]
+         loop_phi_nodes;
+	 something1;
+	 if (cond1)
+	   body;
+	 nvar = phi(orig, bvar) ... for all variables changed in body;
+	 [guard_end]
+	 something2;
+	 if (cond2)
+	   break;
+	 something3;
+       }
+
+     where:
+
+     1) cond1 is loop invariant
+     2) If cond1 is false, then the loop is essentially empty; i.e.,
+	a) nothing in something1, something2 and something3 has side
+	   effects
+	b) anything defined in something1, something2 and something3
+	   is not used outside of the loop.  */
+
+  gcond *cond;
+  do
+    {
+      basic_block next = NULL;
+      if (single_succ_p (header))
+	next = single_succ (header);
+      else
+	{
+	  cond = dyn_cast <gcond *> (last_stmt (header));
+	  if (! cond)
+	    return NULL;
+	  extract_true_false_edges_from_block (header, &te, &fe);
+	  /* Make sure to skip earlier hoisted guards that are left
+	     in place as if (true).  */
+	  if (gimple_cond_true_p (cond))
+	    next = te->dest;
+	  else if (gimple_cond_false_p (cond))
+	    next = fe->dest;
+	  else
+	    break;
+	}
+      /* Never traverse a backedge.  */
+      if (header->loop_father->header == next)
+	return NULL;
+      header = next;
+    }
+  while (1);
+  if (!flow_bb_inside_loop_p (loop, te->dest)
+      || !flow_bb_inside_loop_p (loop, fe->dest))
+    return NULL;
+
+  if (just_once_each_iteration_p (loop, te->dest)
+      || (single_succ_p (te->dest)
+	  && just_once_each_iteration_p (loop, single_succ (te->dest))))
+    {
+      if (just_once_each_iteration_p (loop, fe->dest))
+	return NULL;
+      guard_edge = te;
+    }
+  else if (just_once_each_iteration_p (loop, fe->dest)
+	   || (single_succ_p (fe->dest)
+	       && just_once_each_iteration_p (loop, single_succ (fe->dest))))
+    guard_edge = fe;
+  else
+    return NULL;
+
+  /* Guard edge must skip inner loop.  */
+  if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header,
+      guard_edge == fe ? te->dest : fe->dest))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Guard edge %d --> %d is not around the loop!\n",
+		 guard_edge->src->index, guard_edge->dest->index);
+      return NULL;
+    }
+  if (guard_edge->dest == loop->latch)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Guard edge destination is loop latch.\n");
+      return NULL;
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file,
+	     "Considering guard %d -> %d in loop %d\n",
+	     guard_edge->src->index, guard_edge->dest->index, loop->num);
+  /* Check if condition operands do not have definitions inside loop since
+     any bb copying is not performed.  */
+  FOR_EACH_SSA_TREE_OPERAND (use, cond, iter, SSA_OP_USE)
+    {
+      gimple *def = SSA_NAME_DEF_STMT (use);
+      basic_block def_bb = gimple_bb (def);
+      if (def_bb
+          && flow_bb_inside_loop_p (loop, def_bb))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "  guard operands have definitions"
+				" inside loop\n");
+	  return NULL;
+	}
+    }
+
+  body = get_loop_body (loop);
+  for (i = 0; i < loop->num_nodes; i++)
+    {
+      basic_block bb = body[i];
+      if (bb->loop_father != loop)
+	continue;
+      if (bb->flags & BB_IRREDUCIBLE_LOOP)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "Block %d is marked as irreducible in loop\n",
+		      bb->index);
+	  guard_edge = NULL;
+	  goto end;
+	}
+      if (!empty_bb_without_guard_p (loop, bb))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "  block %d has side effects\n", bb->index);
+	  guard_edge = NULL;
+	  goto end;
+	}
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "  suitable to hoist\n");
+end:
+  if (body)
+    free (body);
+  return guard_edge;
+}
+
+/* Returns true if
+   1) no statement in BB has side effects
+   2) assuming that edge GUARD is always taken, all definitions in BB
+      are noy used outside of the loop.
+   KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
+   PROCESSED is a set of ssa names for that we already tested whether they
+   are invariant or not.  */
+
+static bool
+empty_bb_without_guard_p (struct loop *loop, basic_block bb)
+{
+  basic_block exit_bb = single_exit (loop)->src;
+  bool may_be_used_outside = (bb == exit_bb
+			      || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb));
+  tree name;
+  ssa_op_iter op_iter;
+
+  /* Phi nodes do not have side effects, but their results might be used
+     outside of the loop.  */
+  if (may_be_used_outside)
+    {
+      for (gphi_iterator gsi = gsi_start_phis (bb);
+	   !gsi_end_p (gsi); gsi_next (&gsi))
+	{
+	  gphi *phi = gsi.phi ();
+	  name = PHI_RESULT (phi);
+	  if (virtual_operand_p (name))
+	    continue;
+
+	  if (used_outside_loop_p (loop, name))
+	    return false;
+	}
+    }
+
+  for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
+       !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple *stmt = gsi_stmt (gsi);
+      if (gimple_has_side_effects (stmt))
+	return false;
+
+      if (gimple_vdef(stmt))
+	return false;
+
+      FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF)
+	{
+	  if (may_be_used_outside
+	      && used_outside_loop_p (loop, name))
+	    return false;
+	}
+    }
+  return true;
 }
+
+/* Return true if NAME is used outside of LOOP.  */
+
+static bool
+used_outside_loop_p (struct loop *loop, tree name)
+{
+  imm_use_iterator it;
+  use_operand_p use;
+
+  FOR_EACH_IMM_USE_FAST (use, it, name)
+    {
+      gimple *stmt = USE_STMT (use);
+      if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
+	return true;
+    }
+
+  return false;
+}
+
+/* Return argument for loop preheader edge in header virtual phi if any.  */
+
+static tree
+get_vop_from_header (struct loop *loop)
+{
+  for (gphi_iterator gsi = gsi_start_phis (loop->header);
+       !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gphi *phi = gsi.phi ();
+      if (!virtual_operand_p (gimple_phi_result (phi)))
+	continue;
+      return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
+    }
+  return NULL_TREE;
+}
+
+/* Move the check of GUARD outside of LOOP.  */
+
+static void
+hoist_guard (struct loop *loop, edge guard)
+{
+  edge exit = single_exit (loop);
+  edge preh = loop_preheader_edge (loop);
+  basic_block pre_header = preh->src;
+  basic_block bb;
+  edge te, fe, e, new_edge;
+  gimple *stmt;
+  basic_block guard_bb = guard->src;
+  edge not_guard;
+  gimple_stmt_iterator gsi;
+  int flags = 0;
+  bool fix_dom_of_exit;
+  gcond *cond_stmt, *new_cond_stmt;
+
+  bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest);
+  fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb);
+  gsi = gsi_last_bb (guard_bb);
+  stmt = gsi_stmt (gsi);
+  gcc_assert (gimple_code (stmt) == GIMPLE_COND);
+  cond_stmt = as_a <gcond *> (stmt);
+  extract_true_false_edges_from_block (guard_bb, &te, &fe);
+  /* Insert guard to PRE_HEADER.  */
+  if (!empty_block_p (pre_header))
+    gsi = gsi_last_bb (pre_header);
+  else
+    gsi = gsi_start_bb (pre_header);
+  /* Create copy of COND_STMT.  */
+  new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
+				     gimple_cond_lhs (cond_stmt),
+				     gimple_cond_rhs (cond_stmt),
+				     NULL_TREE, NULL_TREE);
+  gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT);
+  /* Convert COND_STMT to true/false conditional.  */
+  if (guard == te)
+    gimple_cond_make_false (cond_stmt);
+  else
+    gimple_cond_make_true (cond_stmt);
+  update_stmt (cond_stmt);
+  /* Create new loop pre-header.  */
+  e = split_block (pre_header, last_stmt (pre_header));
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "  Moving guard %i->%i (prob ",
+	       guard->src->index, guard->dest->index);
+      guard->probability.dump (dump_file);
+      fprintf (dump_file, ") to bb %i, new preheader is %i\n",
+	       e->src->index, e->dest->index);
+    }
+
+  gcc_assert (loop_preheader_edge (loop)->src == e->dest);
+
+  if (guard == fe)
+    {
+      e->flags = EDGE_TRUE_VALUE;
+      flags |= EDGE_FALSE_VALUE;
+      not_guard = te;
+    }
+  else
+    {
+      e->flags = EDGE_FALSE_VALUE;
+      flags |= EDGE_TRUE_VALUE;
+      not_guard = fe;
+    }
+  new_edge = make_edge (pre_header, exit->dest, flags);
+
+  /* Determine the probability that we skip the loop.  Assume that loop has
+     same average number of iterations regardless outcome of guard.  */
+  new_edge->probability = guard->probability;
+  profile_count skip_count = guard->src->count > 0
+		   ? guard->count ().apply_scale (pre_header->count,
+					       guard->src->count)
+		   : guard->count ().apply_probability (new_edge->probability);
+
+  if (skip_count > e->count ())
+    {
+      fprintf (dump_file, "  Capping count; expect profile inconsistency\n");
+      skip_count = e->count ();
+    }
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "  Estimated probability of skipping loop is ");
+      new_edge->probability.dump (dump_file);
+      fprintf (dump_file, "\n");
+    }
+
+  /* Update profile after the transform:
+
+     First decrease count of path from newly hoisted loop guard
+     to loop header...  */
+  e->probability = new_edge->probability.invert ();
+  e->dest->count = e->count ();
+  e->dest->frequency = EDGE_FREQUENCY (e);
+
+  /* ... now update profile to represent that original guard will be optimized
+     away ...  */
+  guard->probability = profile_probability::never ();
+  not_guard->probability = profile_probability::always ();
+
+  /* ... finally scale everything in the loop except for guarded basic blocks
+     where profile does not change.  */
+  basic_block *body = get_loop_body (loop);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "  Scaling nonguarded BBs in loop:");
+  for (unsigned int i = 0; i < loop->num_nodes; i++)
+    {
+      basic_block bb = body[i];
+      if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, " %i", bb->index);
+	  if (e->probability.initialized_p ())
+            scale_bbs_frequencies (&bb, 1, e->probability);
+  	}
+    }
+
+  if (fix_dom_of_exit)
+    set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header);
+  /* Add NEW_ADGE argument for all phi in post-header block.  */
+  bb = exit->dest;
+  for (gphi_iterator gsi = gsi_start_phis (bb);
+       !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gphi *phi = gsi.phi ();
+      tree arg;
+      if (virtual_operand_p (gimple_phi_result (phi)))
+	{
+	  arg = get_vop_from_header (loop);
+	  if (arg == NULL_TREE)
+	    /* Use exit edge argument.  */
+	    arg =  PHI_ARG_DEF_FROM_EDGE (phi, exit);
+	  add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
+	}
+      else
+	{
+	  /* Use exit edge argument.  */
+	  arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
+	  add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
+	}
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "\n  guard hoisted.\n");
+
+  free (body);
+}
+
+/* Return true if phi argument for exit edge can be used
+   for edge around loop.  */
+
+static bool
+check_exit_phi (struct loop *loop)
+{
+  edge exit = single_exit (loop);
+  basic_block pre_header = loop_preheader_edge (loop)->src;
+
+  for (gphi_iterator gsi = gsi_start_phis (exit->dest);
+       !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gphi *phi = gsi.phi ();
+      tree arg;
+      gimple *def;
+      basic_block def_bb;
+      if (virtual_operand_p (gimple_phi_result (phi)))
+	continue;
+      arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
+      if (TREE_CODE (arg) != SSA_NAME)
+	continue;
+      def = SSA_NAME_DEF_STMT (arg);
+      if (!def)
+	continue;
+      def_bb = gimple_bb (def);
+      if (!def_bb)
+	continue;
+      if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb))
+	/* Definition inside loop!  */
+	return false;
+      /* Check loop closed phi invariant.  */
+      if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header))
+	return false;
+    }
+  return true;
+}
+
+/* Loop unswitching pass.  */
+
+namespace {
+
+const pass_data pass_data_tree_unswitch =
+{
+  GIMPLE_PASS, /* type */
+  "unswitch", /* name */
+  OPTGROUP_LOOP, /* optinfo_flags */
+  TV_TREE_LOOP_UNSWITCH, /* tv_id */
+  PROP_cfg, /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  0, /* todo_flags_finish */
+};
+
+class pass_tree_unswitch : public gimple_opt_pass
+{
+public:
+  pass_tree_unswitch (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
+  {}
+
+  /* opt_pass methods: */
+  virtual bool gate (function *) { return flag_unswitch_loops != 0; }
+  virtual unsigned int execute (function *);
+
+}; // class pass_tree_unswitch
+
+unsigned int
+pass_tree_unswitch::execute (function *fun)
+{
+  if (number_of_loops (fun) <= 1)
+    return 0;
+
+  return tree_ssa_unswitch_loops ();
+}
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_tree_unswitch (gcc::context *ctxt)
+{
+  return new pass_tree_unswitch (ctxt);
+}
+
+