xref: /src/external/gpl3/gcc.old/dist/gcc/tree-ssa-loop-unswitch.cc

/* Loop unswitching.
   Copyright (C) 2004-2022 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 3, or (at your option) any
later version.

GCC is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.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 "tree-inline.h"
#include "gimple-iterator.h"
#include "cfghooks.h"
#include "tree-ssa-loop-manip.h"
#include "tree-vectorizer.h"

/* This file implements the loop unswitching, i.e. transformation of loops like

   while (A)
     {
       if (inv)
         B;

       X;

       if (!inv)
	 C;
     }

   where inv is the loop invariant, into

   if (inv)
     {
       while (A)
	 {
           B;
	   X;
	 }
     }
   else
     {
       while (A)
	 {
	   X;
	   C;
	 }
     }

   Inv is considered invariant iff the values it compares are both invariant;
   tree-ssa-loop-im.cc ensures that all the suitable conditions are in this
   shape.  */

static class loop *tree_unswitch_loop (class loop *, basic_block, tree);
static bool tree_unswitch_single_loop (class loop *, int);
static tree tree_may_unswitch_on (basic_block, class loop *);
static bool tree_unswitch_outer_loop (class loop *);
static edge find_loop_guard (class loop *, vec<gimple *>&);
static bool empty_bb_without_guard_p (class loop *, basic_block,
				      vec<gimple *>&);
static bool used_outside_loop_p (class loop *, tree, vec<gimple *>&);
static void hoist_guard (class loop *, edge);
static bool check_exit_phi (class loop *);
static tree get_vop_from_header (class loop *);

/* Main entry point.  Perform loop unswitching on all suitable loops.  */

unsigned int
tree_ssa_unswitch_loops (void)
{
  bool changed = false;

  /* Go through all loops starting from innermost.  */
  for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
    {
      if (!loop->inner)
	/* Unswitch innermost loop.  */
	changed |= tree_unswitch_single_loop (loop, 0);
      else
	changed |= tree_unswitch_outer_loop (loop);
    }

  if (changed)
    return TODO_cleanup_cfg;
  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, class 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, class loop *loop)
{
  gimple *last, *def;
  gcond *stmt;
  tree cond, use;
  basic_block def_bb;
  ssa_op_iter iter;

  /* BB must end in a simple conditional jump.  */
  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
     loop where we would unswitch again on such a condition.  */
  if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
    return NULL_TREE;

  /* Condition must be invariant.  */
  FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
    {
      def = SSA_NAME_DEF_STMT (use);
      def_bb = gimple_bb (def);
      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,
		 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));

  return cond;
}

/* Simplifies COND using checks in front of the entry of the LOOP.  Just very
   simplish (sufficient to prevent us from duplicating loop in unswitching
   unnecessarily).  */

static tree
simplify_using_entry_checks (class loop *loop, tree cond)
{
  edge e = loop_preheader_edge (loop);
  gimple *stmt;

  while (1)
    {
      stmt = last_stmt (e->src);
      if (stmt
	  && gimple_code (stmt) == GIMPLE_COND
	  && gimple_cond_code (stmt) == TREE_CODE (cond)
	  && operand_equal_p (gimple_cond_lhs (stmt),
			      TREE_OPERAND (cond, 0), 0)
	  && operand_equal_p (gimple_cond_rhs (stmt),
			      TREE_OPERAND (cond, 1), 0))
	return (e->flags & EDGE_TRUE_VALUE
		? boolean_true_node
		: boolean_false_node);

      if (!single_pred_p (e->src))
	return cond;

      e = single_pred_edge (e->src);
      if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
	return cond;
    }
}

/* Unswitch single LOOP.  NUM is number of unswitchings done; we do not allow
   it to grow too much, it is too easy to create example on that the code would
   grow exponentially.  */

static bool
tree_unswitch_single_loop (class loop *loop, int num)
{
  basic_block *bbs;
  class loop *nloop;
  unsigned i, found;
  tree cond = NULL_TREE;
  gimple *stmt;
  bool changed = false;
  HOST_WIDE_INT iterations;

  dump_user_location_t loc = find_loop_location (loop);

  /* 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_enabled_p ())
	    dump_printf_loc (MSG_NOTE, loc,
			     "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_max_unswitch_insns)
	{
	  if (dump_enabled_p ())
	    dump_printf_loc (MSG_NOTE, loc,
			     "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_enabled_p ())
	    dump_printf_loc (MSG_NOTE, loc,
			     "Not unswitching, loop is not expected"
			     " to iterate\n");
	  return false;
	}
    }

  i = 0;
  bbs = get_loop_body (loop);
  found = loop->num_nodes;

  while (1)
    {
      /* Find a bb to unswitch on.  */
      for (; i < loop->num_nodes; i++)
	if ((cond = tree_may_unswitch_on (bbs[i], loop)))
	  break;

      if (i == loop->num_nodes)
	{
	  if (dump_enabled_p ()
	      && num > param_max_unswitch_level)
	    dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
			     "Not unswitching anymore, hit max level\n");

	  if (found == loop->num_nodes)
	    {
	      free (bbs);
	      return changed;
	    }
	  break;
	}

      cond = simplify_using_entry_checks (loop, cond);
      stmt = last_stmt (bbs[i]);
      if (integer_nonzerop (cond))
	{
	  /* Remove false path.  */
	  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 (as_a <gcond *> (stmt),
					       boolean_false_node);
	  changed = true;
	}
      /* Do not unswitch too much.  */
      else if (num > param_max_unswitch_level)
	{
	  i++;
	  continue;
	}
      /* In nested tree_unswitch_single_loop first optimize all conditions
	 using entry checks, then discover still reachable blocks in the
	 loop and find the condition only among those still reachable bbs.  */
      else if (num != 0)
	{
	  if (found == loop->num_nodes)
	    found = i;
	  i++;
	  continue;
	}
      else
	{
	  found = i;
	  break;
	}

      update_stmt (stmt);
      i++;
    }

  if (num != 0)
    {
      basic_block *tos, *worklist;

      /* When called recursively, first do a quick discovery
	 of reachable bbs after the above changes and only
	 consider conditions in still reachable bbs.  */
      tos = worklist = XNEWVEC (basic_block, loop->num_nodes);

      for (i = 0; i < loop->num_nodes; i++)
	bbs[i]->flags &= ~BB_REACHABLE;

      /* Start with marking header.  */
      *tos++ = bbs[0];
      bbs[0]->flags |= BB_REACHABLE;

      /* Iterate: find everything reachable from what we've already seen
	 within the same innermost loop.  Don't look through false edges
	 if condition is always true or true edges if condition is
	 always false.  */
      while (tos != worklist)
	{
	  basic_block b = *--tos;
	  edge e;
	  edge_iterator ei;
	  int flags = 0;

	  if (EDGE_COUNT (b->succs) == 2)
	    {
	      gimple *stmt = last_stmt (b);
	      if (stmt
		  && gimple_code (stmt) == GIMPLE_COND)
		{
		  gcond *cond_stmt = as_a <gcond *> (stmt);
		  if (gimple_cond_true_p (cond_stmt))
		    flags = EDGE_FALSE_VALUE;
		  else if (gimple_cond_false_p (cond_stmt))
		    flags = EDGE_TRUE_VALUE;
		}
	    }

	  FOR_EACH_EDGE (e, ei, b->succs)
	    {
	      basic_block dest = e->dest;

	      if (dest->loop_father == loop
		  && !(dest->flags & BB_REACHABLE)
		  && !(e->flags & flags))
		{
		  *tos++ = dest;
		  dest->flags |= BB_REACHABLE;
		}
	    }
	}

      free (worklist);

      /* Find a bb to unswitch on.  */
      for (; found < loop->num_nodes; found++)
	if ((bbs[found]->flags & BB_REACHABLE)
	    && (cond = tree_may_unswitch_on (bbs[found], loop)))
	  break;

      if (found == loop->num_nodes)
	{
	  free (bbs);
	  return changed;
	}
    }

  if (dump_enabled_p ())
    dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
		     "Unswitching loop on condition: %G\n",
		     last_stmt (bbs[found]));

  initialize_original_copy_tables ();
  /* Unswitch the loop on this condition.  */
  nloop = tree_unswitch_loop (loop, bbs[found], cond);
  if (!nloop)
    {
      free_original_copy_tables ();
      free (bbs);
      return changed;
    }

  /* Update the SSA form after unswitching.  */
  update_ssa (TODO_update_ssa);
  free_original_copy_tables ();

  /* Invoke itself on modified loops.  */
  tree_unswitch_single_loop (nloop, num + 1);
  tree_unswitch_single_loop (loop, num + 1);
  free (bbs);
  return true;
}

/* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
   unswitching of innermost loops.  COND is the condition determining which
   loop is entered -- the new loop is entered if COND is true.  Returns NULL
   if impossible, new loop otherwise.  */

static class loop *
tree_unswitch_loop (class loop *loop,
		    basic_block unswitch_on, tree cond)
{
  profile_probability prob_true;
  edge edge_true, edge_false;

  /* Some sanity checking.  */
  gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
  gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
  gcc_assert (loop->inner == NULL);

  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.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 (class 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_enabled_p ())
	dump_printf_loc (MSG_MISSED_OPTIMIZATION, find_loop_location (loop),
			 "Not unswitching, loop is not expected"
			 " to iterate\n");
      return false;
    }

  bool changed = false;
  auto_vec<gimple *> dbg_to_reset;
  while ((guard = find_loop_guard (loop, dbg_to_reset)))
    {
      if (! changed)
	rewrite_virtuals_into_loop_closed_ssa (loop);
      hoist_guard (loop, guard);
      for (gimple *debug_stmt : dbg_to_reset)
	{
	  gimple_debug_bind_reset_value (debug_stmt);
	  update_stmt (debug_stmt);
	}
      dbg_to_reset.truncate (0);
      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 (class loop *loop, vec<gimple *> &dbg_to_reset)
{
  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 = safe_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;

  dump_user_location_t loc = find_loop_location (loop);

  /* Guard edge must skip inner loop.  */
  if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header,
      guard_edge == fe ? te->dest : fe->dest))
    {
      if (dump_enabled_p ())
	dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
			 "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_enabled_p ())
	dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
			 "Guard edge destination is loop latch.\n");
      return NULL;
    }

  if (dump_enabled_p ())
    dump_printf_loc (MSG_NOTE, loc,
		     "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_enabled_p ())
	    dump_printf_loc (MSG_NOTE, loc, "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_enabled_p ())
	    dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
			     "Block %d is marked as irreducible in loop\n",
			     bb->index);
	  guard_edge = NULL;
	  goto end;
	}
      if (!empty_bb_without_guard_p (loop, bb, dbg_to_reset))
	{
	  if (dump_enabled_p ())
	    dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
			     "Block %d has side effects\n", bb->index);
	  guard_edge = NULL;
	  goto end;
	}
    }

  if (dump_enabled_p ())
    dump_printf_loc (MSG_NOTE, loc,
		     "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.  Uses in debug stmts outside of the loop are
   pushed to DBG_TO_RESET.  */

static bool
empty_bb_without_guard_p (class loop *loop, basic_block bb,
			  vec<gimple *> &dbg_to_reset)
{
  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, dbg_to_reset))
	    return false;
	}
    }

  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;

      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, dbg_to_reset))
	    return false;
	}
    }
  return true;
}

/* Return true if NAME is used outside of LOOP.  Pushes debug stmts that
   have such uses to DBG_TO_RESET but do not consider such uses.  */

static bool
used_outside_loop_p (class loop *loop, tree name, vec<gimple *> &dbg_to_reset)
{
  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)))
	{
	  if (!is_gimple_debug (stmt))
	    return true;
	  dbg_to_reset.safe_push (stmt);
	}
    }

  return false;
}

/* Return argument for loop preheader edge in header virtual phi if any.  */

static tree
get_vop_from_header (class 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 (class 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.  */
  gsi = gsi_last_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));

  dump_user_location_t loc = find_loop_location (loop);

  if (dump_enabled_p ())
    {
      char buffer[64];
      guard->probability.dump (buffer);

      dump_printf_loc (MSG_NOTE, loc,
		       "Moving guard %i->%i (prob %s) to bb %i, "
		       "new preheader is %i\n",
		       guard->src->index, guard->dest->index,
		       buffer, 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.nonzero_p ()
		   ? 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_enabled_p ())
    {
      char buffer[64];
      new_edge->probability.dump (buffer);

      dump_printf_loc (MSG_NOTE, loc,
		       "Estimated probability of skipping loop is %s\n",
		       buffer);
    }

  /* 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 ();

  /* ... 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);

  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_enabled_p ())
	    dump_printf_loc (MSG_NOTE, loc,
			     "Scaling nonguarded BBs in loop: %i\n",
			     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_enabled_p ())
    dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
		     "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 (class 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);
}