/* If-conversion for vectorizer.
   Copyright (C) 2004-2017 Free Software Foundation, Inc.
   Contributed by Devang Patel <dpatel@apple.com>

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

/* This pass implements a tree level if-conversion of loops.  Its
   initial goal is to help the vectorizer to vectorize loops with
   conditions.

   A short description of if-conversion:

     o Decide if a loop is if-convertible or not.
     o Walk all loop basic blocks in breadth first order (BFS order).
       o Remove conditional statements (at the end of basic block)
         and propagate condition into destination basic blocks'
	 predicate list.
       o Replace modify expression with conditional modify expression
         using current basic block's condition.
     o Merge all basic blocks
       o Replace phi nodes with conditional modify expr
       o Merge all basic blocks into header

     Sample transformation:

     INPUT
     -----

     # i_23 = PHI <0(0), i_18(10)>;
     <L0>:;
     j_15 = A[i_23];
     if (j_15 > 41) goto <L1>; else goto <L17>;

     <L17>:;
     goto <bb 3> (<L3>);

     <L1>:;

     # iftmp.2_4 = PHI <0(8), 42(2)>;
     <L3>:;
     A[i_23] = iftmp.2_4;
     i_18 = i_23 + 1;
     if (i_18 <= 15) goto <L19>; else goto <L18>;

     <L19>:;
     goto <bb 1> (<L0>);

     <L18>:;

     OUTPUT
     ------

     # i_23 = PHI <0(0), i_18(10)>;
     <L0>:;
     j_15 = A[i_23];

     <L3>:;
     iftmp.2_4 = j_15 > 41 ? 42 : 0;
     A[i_23] = iftmp.2_4;
     i_18 = i_23 + 1;
     if (i_18 <= 15) goto <L19>; else goto <L18>;

     <L19>:;
     goto <bb 1> (<L0>);

     <L18>:;
*/

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "cfghooks.h"
#include "tree-pass.h"
#include "ssa.h"
#include "expmed.h"
#include "optabs-query.h"
#include "gimple-pretty-print.h"
#include "alias.h"
#include "fold-const.h"
#include "stor-layout.h"
#include "gimple-fold.h"
#include "gimplify.h"
#include "gimple-iterator.h"
#include "gimplify-me.h"
#include "tree-cfg.h"
#include "tree-into-ssa.h"
#include "tree-ssa.h"
#include "cfgloop.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-ssa-loop.h"
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop-ivopts.h"
#include "tree-ssa-address.h"
#include "dbgcnt.h"
#include "tree-hash-traits.h"
#include "varasm.h"
#include "builtins.h"
#include "params.h"
#include "cfganal.h"

/* Only handle PHIs with no more arguments unless we are asked to by
   simd pragma.  */
#define MAX_PHI_ARG_NUM \
  ((unsigned) PARAM_VALUE (PARAM_MAX_TREE_IF_CONVERSION_PHI_ARGS))

/* Indicate if new load/store that needs to be predicated is introduced
   during if conversion.  */
static bool any_pred_load_store;

/* Indicate if there are any complicated PHIs that need to be handled in
   if-conversion.  Complicated PHI has more than two arguments and can't
   be degenerated to two arguments PHI.  See more information in comment
   before phi_convertible_by_degenerating_args.  */
static bool any_complicated_phi;

/* Hash for struct innermost_loop_behavior.  It depends on the user to
   free the memory.  */

struct innermost_loop_behavior_hash : nofree_ptr_hash <innermost_loop_behavior>
{
  static inline hashval_t hash (const value_type &);
  static inline bool equal (const value_type &,
			    const compare_type &);
};

inline hashval_t
innermost_loop_behavior_hash::hash (const value_type &e)
{
  hashval_t hash;

  hash = iterative_hash_expr (e->base_address, 0);
  hash = iterative_hash_expr (e->offset, hash);
  hash = iterative_hash_expr (e->init, hash);
  return iterative_hash_expr (e->step, hash);
}

inline bool
innermost_loop_behavior_hash::equal (const value_type &e1,
				     const compare_type &e2)
{
  if ((e1->base_address && !e2->base_address)
      || (!e1->base_address && e2->base_address)
      || (!e1->offset && e2->offset)
      || (e1->offset && !e2->offset)
      || (!e1->init && e2->init)
      || (e1->init && !e2->init)
      || (!e1->step && e2->step)
      || (e1->step && !e2->step))
    return false;

  if (e1->base_address && e2->base_address
      && !operand_equal_p (e1->base_address, e2->base_address, 0))
    return false;
  if (e1->offset && e2->offset
      && !operand_equal_p (e1->offset, e2->offset, 0))
    return false;
  if (e1->init && e2->init
      && !operand_equal_p (e1->init, e2->init, 0))
    return false;
  if (e1->step && e2->step
      && !operand_equal_p (e1->step, e2->step, 0))
    return false;

  return true;
}

/* List of basic blocks in if-conversion-suitable order.  */
static basic_block *ifc_bbs;

/* Hash table to store <DR's innermost loop behavior, DR> pairs.  */
static hash_map<innermost_loop_behavior_hash,
		data_reference_p> *innermost_DR_map;

/* Hash table to store <base reference, DR> pairs.  */
static hash_map<tree_operand_hash, data_reference_p> *baseref_DR_map;

/* Structure used to predicate basic blocks.  This is attached to the
   ->aux field of the BBs in the loop to be if-converted.  */
struct bb_predicate {

  /* The condition under which this basic block is executed.  */
  tree predicate;

  /* PREDICATE is gimplified, and the sequence of statements is
     recorded here, in order to avoid the duplication of computations
     that occur in previous conditions.  See PR44483.  */
  gimple_seq predicate_gimplified_stmts;
};

/* Returns true when the basic block BB has a predicate.  */

static inline bool
bb_has_predicate (basic_block bb)
{
  return bb->aux != NULL;
}

/* Returns the gimplified predicate for basic block BB.  */

static inline tree
bb_predicate (basic_block bb)
{
  return ((struct bb_predicate *) bb->aux)->predicate;
}

/* Sets the gimplified predicate COND for basic block BB.  */

static inline void
set_bb_predicate (basic_block bb, tree cond)
{
  gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR
	       && is_gimple_condexpr (TREE_OPERAND (cond, 0)))
	      || is_gimple_condexpr (cond));
  ((struct bb_predicate *) bb->aux)->predicate = cond;
}

/* Returns the sequence of statements of the gimplification of the
   predicate for basic block BB.  */

static inline gimple_seq
bb_predicate_gimplified_stmts (basic_block bb)
{
  return ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts;
}

/* Sets the sequence of statements STMTS of the gimplification of the
   predicate for basic block BB.  */

static inline void
set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
{
  ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts = stmts;
}

/* Adds the sequence of statements STMTS to the sequence of statements
   of the predicate for basic block BB.  */

static inline void
add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
{
  gimple_seq_add_seq_without_update
    (&(((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts), stmts);
}

/* Initializes to TRUE the predicate of basic block BB.  */

static inline void
init_bb_predicate (basic_block bb)
{
  bb->aux = XNEW (struct bb_predicate);
  set_bb_predicate_gimplified_stmts (bb, NULL);
  set_bb_predicate (bb, boolean_true_node);
}

/* Release the SSA_NAMEs associated with the predicate of basic block BB,
   but don't actually free it.  */

static inline void
release_bb_predicate (basic_block bb)
{
  gimple_seq stmts = bb_predicate_gimplified_stmts (bb);
  if (stmts)
    {
      if (flag_checking)
	for (gimple_stmt_iterator i = gsi_start (stmts);
	     !gsi_end_p (i); gsi_next (&i))
	  gcc_assert (! gimple_use_ops (gsi_stmt (i)));

      set_bb_predicate_gimplified_stmts (bb, NULL);
    }
}

/* Free the predicate of basic block BB.  */

static inline void
free_bb_predicate (basic_block bb)
{
  if (!bb_has_predicate (bb))
    return;

  release_bb_predicate (bb);
  free (bb->aux);
  bb->aux = NULL;
}

/* Reinitialize predicate of BB with the true predicate.  */

static inline void
reset_bb_predicate (basic_block bb)
{
  if (!bb_has_predicate (bb))
    init_bb_predicate (bb);
  else
    {
      release_bb_predicate (bb);
      set_bb_predicate (bb, boolean_true_node);
    }
}

/* Returns a new SSA_NAME of type TYPE that is assigned the value of
   the expression EXPR.  Inserts the statement created for this
   computation before GSI and leaves the iterator GSI at the same
   statement.  */

static tree
ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi)
{
  tree new_name = make_temp_ssa_name (type, NULL, "_ifc_");
  gimple *stmt = gimple_build_assign (new_name, expr);
  gimple_set_vuse (stmt, gimple_vuse (gsi_stmt (*gsi)));
  gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
  return new_name;
}

/* Return true when COND is a false predicate.  */

static inline bool
is_false_predicate (tree cond)
{
  return (cond != NULL_TREE
	  && (cond == boolean_false_node
	      || integer_zerop (cond)));
}

/* Return true when COND is a true predicate.  */

static inline bool
is_true_predicate (tree cond)
{
  return (cond == NULL_TREE
	  || cond == boolean_true_node
	  || integer_onep (cond));
}

/* Returns true when BB has a predicate that is not trivial: true or
   NULL_TREE.  */

static inline bool
is_predicated (basic_block bb)
{
  return !is_true_predicate (bb_predicate (bb));
}

/* Parses the predicate COND and returns its comparison code and
   operands OP0 and OP1.  */

static enum tree_code
parse_predicate (tree cond, tree *op0, tree *op1)
{
  gimple *s;

  if (TREE_CODE (cond) == SSA_NAME
      && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond)))
    {
      if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
	{
	  *op0 = gimple_assign_rhs1 (s);
	  *op1 = gimple_assign_rhs2 (s);
	  return gimple_assign_rhs_code (s);
	}

      else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR)
	{
	  tree op = gimple_assign_rhs1 (s);
	  tree type = TREE_TYPE (op);
	  enum tree_code code = parse_predicate (op, op0, op1);

	  return code == ERROR_MARK ? ERROR_MARK
	    : invert_tree_comparison (code, HONOR_NANS (type));
	}

      return ERROR_MARK;
    }

  if (COMPARISON_CLASS_P (cond))
    {
      *op0 = TREE_OPERAND (cond, 0);
      *op1 = TREE_OPERAND (cond, 1);
      return TREE_CODE (cond);
    }

  return ERROR_MARK;
}

/* Returns the fold of predicate C1 OR C2 at location LOC.  */

static tree
fold_or_predicates (location_t loc, tree c1, tree c2)
{
  tree op1a, op1b, op2a, op2b;
  enum tree_code code1 = parse_predicate (c1, &op1a, &op1b);
  enum tree_code code2 = parse_predicate (c2, &op2a, &op2b);

  if (code1 != ERROR_MARK && code2 != ERROR_MARK)
    {
      tree t = maybe_fold_or_comparisons (code1, op1a, op1b,
					  code2, op2a, op2b);
      if (t)
	return t;
    }

  return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2);
}

/* Returns either a COND_EXPR or the folded expression if the folded
   expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
   a constant or a SSA_NAME. */

static tree
fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs)
{
  tree rhs1, lhs1, cond_expr;

  /* If COND is comparison r != 0 and r has boolean type, convert COND
     to SSA_NAME to accept by vect bool pattern.  */
  if (TREE_CODE (cond) == NE_EXPR)
    {
      tree op0 = TREE_OPERAND (cond, 0);
      tree op1 = TREE_OPERAND (cond, 1);
      if (TREE_CODE (op0) == SSA_NAME
	  && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
	  && (integer_zerop (op1)))
	cond = op0;
    }
  cond_expr = fold_ternary (COND_EXPR, type, cond, rhs, lhs);

  if (cond_expr == NULL_TREE)
    return build3 (COND_EXPR, type, cond, rhs, lhs);

  STRIP_USELESS_TYPE_CONVERSION (cond_expr);

  if (is_gimple_val (cond_expr))
    return cond_expr;

  if (TREE_CODE (cond_expr) == ABS_EXPR)
    {
      rhs1 = TREE_OPERAND (cond_expr, 1);
      STRIP_USELESS_TYPE_CONVERSION (rhs1);
      if (is_gimple_val (rhs1))
	return build1 (ABS_EXPR, type, rhs1);
    }

  if (TREE_CODE (cond_expr) == MIN_EXPR
      || TREE_CODE (cond_expr) == MAX_EXPR)
    {
      lhs1 = TREE_OPERAND (cond_expr, 0);
      STRIP_USELESS_TYPE_CONVERSION (lhs1);
      rhs1 = TREE_OPERAND (cond_expr, 1);
      STRIP_USELESS_TYPE_CONVERSION (rhs1);
      if (is_gimple_val (rhs1) && is_gimple_val (lhs1))
	return build2 (TREE_CODE (cond_expr), type, lhs1, rhs1);
    }
  return build3 (COND_EXPR, type, cond, rhs, lhs);
}

/* Add condition NC to the predicate list of basic block BB.  LOOP is
   the loop to be if-converted. Use predicate of cd-equivalent block
   for join bb if it exists: we call basic blocks bb1 and bb2 
   cd-equivalent if they are executed under the same condition.  */

static inline void
add_to_predicate_list (struct loop *loop, basic_block bb, tree nc)
{
  tree bc, *tp;
  basic_block dom_bb;

  if (is_true_predicate (nc))
    return;

  /* If dominance tells us this basic block is always executed,
     don't record any predicates for it.  */
  if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
    return;

  dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
  /* We use notion of cd equivalence to get simpler predicate for
     join block, e.g. if join block has 2 predecessors with predicates
     p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
     p1 & p2 | p1 & !p2.  */
  if (dom_bb != loop->header
      && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb)
    {
      gcc_assert (flow_bb_inside_loop_p (loop, dom_bb));
      bc = bb_predicate (dom_bb);
      if (!is_true_predicate (bc))
	set_bb_predicate (bb, bc);
      else
	gcc_assert (is_true_predicate (bb_predicate (bb)));
      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n",
		 dom_bb->index, bb->index);
      return;
    }

  if (!is_predicated (bb))
    bc = nc;
  else
    {
      bc = bb_predicate (bb);
      bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc);
      if (is_true_predicate (bc))
	{
	  reset_bb_predicate (bb);
	  return;
	}
    }

  /* Allow a TRUTH_NOT_EXPR around the main predicate.  */
  if (TREE_CODE (bc) == TRUTH_NOT_EXPR)
    tp = &TREE_OPERAND (bc, 0);
  else
    tp = &bc;
  if (!is_gimple_condexpr (*tp))
    {
      gimple_seq stmts;
      *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE);
      add_bb_predicate_gimplified_stmts (bb, stmts);
    }
  set_bb_predicate (bb, bc);
}

/* Add the condition COND to the previous condition PREV_COND, and add
   this to the predicate list of the destination of edge E.  LOOP is
   the loop to be if-converted.  */

static void
add_to_dst_predicate_list (struct loop *loop, edge e,
			   tree prev_cond, tree cond)
{
  if (!flow_bb_inside_loop_p (loop, e->dest))
    return;

  if (!is_true_predicate (prev_cond))
    cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
			prev_cond, cond);

  if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->dest))
    add_to_predicate_list (loop, e->dest, cond);
}

/* Return true if one of the successor edges of BB exits LOOP.  */

static bool
bb_with_exit_edge_p (struct loop *loop, basic_block bb)
{
  edge e;
  edge_iterator ei;

  FOR_EACH_EDGE (e, ei, bb->succs)
    if (loop_exit_edge_p (loop, e))
      return true;

  return false;
}

/* Given PHI which has more than two arguments, this function checks if
   it's if-convertible by degenerating its arguments.  Specifically, if
   below two conditions are satisfied:

     1) Number of PHI arguments with different values equals to 2 and one
	argument has the only occurrence.
     2) The edge corresponding to the unique argument isn't critical edge.

   Such PHI can be handled as PHIs have only two arguments.  For example,
   below PHI:

     res = PHI <A_1(e1), A_1(e2), A_2(e3)>;

   can be transformed into:

     res = (predicate of e3) ? A_2 : A_1;

   Return TRUE if it is the case, FALSE otherwise.  */

static bool
phi_convertible_by_degenerating_args (gphi *phi)
{
  edge e;
  tree arg, t1 = NULL, t2 = NULL;
  unsigned int i, i1 = 0, i2 = 0, n1 = 0, n2 = 0;
  unsigned int num_args = gimple_phi_num_args (phi);

  gcc_assert (num_args > 2);

  for (i = 0; i < num_args; i++)
    {
      arg = gimple_phi_arg_def (phi, i);
      if (t1 == NULL || operand_equal_p (t1, arg, 0))
	{
	  n1++;
	  i1 = i;
	  t1 = arg;
	}
      else if (t2 == NULL || operand_equal_p (t2, arg, 0))
	{
	  n2++;
	  i2 = i;
	  t2 = arg;
	}
      else
	return false;
    }

  if (n1 != 1 && n2 != 1)
    return false;

  /* Check if the edge corresponding to the unique arg is critical.  */
  e = gimple_phi_arg_edge (phi, (n1 == 1) ? i1 : i2);
  if (EDGE_COUNT (e->src->succs) > 1)
    return false;

  return true;
}

/* Return true when PHI is if-convertible.  PHI is part of loop LOOP
   and it belongs to basic block BB.  Note at this point, it is sure
   that PHI is if-convertible.  This function updates global variable
   ANY_COMPLICATED_PHI if PHI is complicated.  */

static bool
if_convertible_phi_p (struct loop *loop, basic_block bb, gphi *phi)
{
  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file, "-------------------------\n");
      print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
    }

  if (bb != loop->header
      && gimple_phi_num_args (phi) > 2
      && !phi_convertible_by_degenerating_args (phi))
    any_complicated_phi = true;

  return true;
}

/* Records the status of a data reference.  This struct is attached to
   each DR->aux field.  */

struct ifc_dr {
  bool rw_unconditionally;
  bool w_unconditionally;
  bool written_at_least_once;

  tree rw_predicate;
  tree w_predicate;
  tree base_w_predicate;
};

#define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
#define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
#define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
#define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)

/* Iterates over DR's and stores refs, DR and base refs, DR pairs in
   HASH tables.  While storing them in HASH table, it checks if the
   reference is unconditionally read or written and stores that as a flag
   information.  For base reference it checks if it is written atlest once
   unconditionally and stores it as flag information along with DR.
   In other words for every data reference A in STMT there exist other
   accesses to a data reference with the same base with predicates that
   add up (OR-up) to the true predicate: this ensures that the data
   reference A is touched (read or written) on every iteration of the
   if-converted loop.  */
static void
hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a)
{

  data_reference_p *master_dr, *base_master_dr;
  tree base_ref = DR_BASE_OBJECT (a);
  innermost_loop_behavior *innermost = &DR_INNERMOST (a);
  tree ca = bb_predicate (gimple_bb (DR_STMT (a)));
  bool exist1, exist2;

  master_dr = &innermost_DR_map->get_or_insert (innermost, &exist1);
  if (!exist1)
    *master_dr = a;

  if (DR_IS_WRITE (a))
    {
      IFC_DR (*master_dr)->w_predicate
	= fold_or_predicates (UNKNOWN_LOCATION, ca,
			      IFC_DR (*master_dr)->w_predicate);
      if (is_true_predicate (IFC_DR (*master_dr)->w_predicate))
	DR_W_UNCONDITIONALLY (*master_dr) = true;
    }
  IFC_DR (*master_dr)->rw_predicate
    = fold_or_predicates (UNKNOWN_LOCATION, ca,
			  IFC_DR (*master_dr)->rw_predicate);
  if (is_true_predicate (IFC_DR (*master_dr)->rw_predicate))
    DR_RW_UNCONDITIONALLY (*master_dr) = true;

  if (DR_IS_WRITE (a))
    {
      base_master_dr = &baseref_DR_map->get_or_insert (base_ref, &exist2);
      if (!exist2)
	*base_master_dr = a;
      IFC_DR (*base_master_dr)->base_w_predicate
	= fold_or_predicates (UNKNOWN_LOCATION, ca,
			      IFC_DR (*base_master_dr)->base_w_predicate);
      if (is_true_predicate (IFC_DR (*base_master_dr)->base_w_predicate))
	DR_BASE_W_UNCONDITIONALLY (*base_master_dr) = true;
    }
}

/* Return TRUE if can prove the index IDX of an array reference REF is
   within array bound.  Return false otherwise.  */

static bool
idx_within_array_bound (tree ref, tree *idx, void *dta)
{
  bool overflow;
  widest_int niter, valid_niter, delta, wi_step;
  tree ev, init, step;
  tree low, high;
  struct loop *loop = (struct loop*) dta;

  /* Only support within-bound access for array references.  */
  if (TREE_CODE (ref) != ARRAY_REF)
    return false;

  /* For arrays at the end of the structure, we are not guaranteed that they
     do not really extend over their declared size.  However, for arrays of
     size greater than one, this is unlikely to be intended.  */
  if (array_at_struct_end_p (ref))
    return false;

  ev = analyze_scalar_evolution (loop, *idx);
  ev = instantiate_parameters (loop, ev);
  init = initial_condition (ev);
  step = evolution_part_in_loop_num (ev, loop->num);

  if (!init || TREE_CODE (init) != INTEGER_CST
      || (step && TREE_CODE (step) != INTEGER_CST))
    return false;

  low = array_ref_low_bound (ref);
  high = array_ref_up_bound (ref);

  /* The case of nonconstant bounds could be handled, but it would be
     complicated.  */
  if (TREE_CODE (low) != INTEGER_CST
      || !high || TREE_CODE (high) != INTEGER_CST)
    return false;

  /* Check if the intial idx is within bound.  */
  if (wi::to_widest (init) < wi::to_widest (low)
      || wi::to_widest (init) > wi::to_widest (high))
    return false;

  /* The idx is always within bound.  */
  if (!step || integer_zerop (step))
    return true;

  if (!max_loop_iterations (loop, &niter))
    return false;

  if (wi::to_widest (step) < 0)
    {
      delta = wi::to_widest (init) - wi::to_widest (low);
      wi_step = -wi::to_widest (step);
    }
  else
    {
      delta = wi::to_widest (high) - wi::to_widest (init);
      wi_step = wi::to_widest (step);
    }

  valid_niter = wi::div_floor (delta, wi_step, SIGNED, &overflow);
  /* The iteration space of idx is within array bound.  */
  if (!overflow && niter <= valid_niter)
    return true;

  return false;
}

/* Return TRUE if ref is a within bound array reference.  */

static bool
ref_within_array_bound (gimple *stmt, tree ref)
{
  struct loop *loop = loop_containing_stmt (stmt);

  gcc_assert (loop != NULL);
  return for_each_index (&ref, idx_within_array_bound, loop);
}


/* Given a memory reference expression T, return TRUE if base object
   it refers to is writable.  The base object of a memory reference
   is the main object being referenced, which is returned by function
   get_base_address.  */

static bool
base_object_writable (tree ref)
{
  tree base_tree = get_base_address (ref);

  return (base_tree
	  && DECL_P (base_tree)
	  && decl_binds_to_current_def_p (base_tree)
	  && !TREE_READONLY (base_tree));
}

/* Return true when the memory references of STMT won't trap in the
   if-converted code.  There are two things that we have to check for:

   - writes to memory occur to writable memory: if-conversion of
   memory writes transforms the conditional memory writes into
   unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
   into "A[i] = cond ? foo : A[i]", and as the write to memory may not
   be executed at all in the original code, it may be a readonly
   memory.  To check that A is not const-qualified, we check that
   there exists at least an unconditional write to A in the current
   function.

   - reads or writes to memory are valid memory accesses for every
   iteration.  To check that the memory accesses are correctly formed
   and that we are allowed to read and write in these locations, we
   check that the memory accesses to be if-converted occur at every
   iteration unconditionally.

   Returns true for the memory reference in STMT, same memory reference
   is read or written unconditionally atleast once and the base memory
   reference is written unconditionally once.  This is to check reference
   will not write fault.  Also retuns true if the memory reference is
   unconditionally read once then we are conditionally writing to memory
   which is defined as read and write and is bound to the definition
   we are seeing.  */
static bool
ifcvt_memrefs_wont_trap (gimple *stmt, vec<data_reference_p> drs)
{
  data_reference_p *master_dr, *base_master_dr;
  data_reference_p a = drs[gimple_uid (stmt) - 1];

  tree base = DR_BASE_OBJECT (a);
  innermost_loop_behavior *innermost = &DR_INNERMOST (a);

  gcc_assert (DR_STMT (a) == stmt);
  gcc_assert (DR_BASE_ADDRESS (a) || DR_OFFSET (a)
              || DR_INIT (a) || DR_STEP (a));

  master_dr = innermost_DR_map->get (innermost);
  gcc_assert (master_dr != NULL);

  base_master_dr = baseref_DR_map->get (base);

  /* If a is unconditionally written to it doesn't trap.  */
  if (DR_W_UNCONDITIONALLY (*master_dr))
    return true;

  /* If a is unconditionally accessed then ...

     Even a is conditional access, we can treat it as an unconditional
     one if it's an array reference and all its index are within array
     bound.  */
  if (DR_RW_UNCONDITIONALLY (*master_dr)
      || ref_within_array_bound (stmt, DR_REF (a)))
    {
      /* an unconditional read won't trap.  */
      if (DR_IS_READ (a))
	return true;

      /* an unconditionaly write won't trap if the base is written
         to unconditionally.  */
      if (base_master_dr
	  && DR_BASE_W_UNCONDITIONALLY (*base_master_dr))
	return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES);
      /* or the base is known to be not readonly.  */
      else if (base_object_writable (DR_REF (a)))
	return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES);
    }

  return false;
}

/* Return true if STMT could be converted into a masked load or store
   (conditional load or store based on a mask computed from bb predicate).  */

static bool
ifcvt_can_use_mask_load_store (gimple *stmt)
{
  tree lhs, ref;
  machine_mode mode;
  basic_block bb = gimple_bb (stmt);
  bool is_load;

  if (!(flag_tree_loop_vectorize || bb->loop_father->force_vectorize)
      || bb->loop_father->dont_vectorize
      || !gimple_assign_single_p (stmt)
      || gimple_has_volatile_ops (stmt))
    return false;

  /* Check whether this is a load or store.  */
  lhs = gimple_assign_lhs (stmt);
  if (gimple_store_p (stmt))
    {
      if (!is_gimple_val (gimple_assign_rhs1 (stmt)))
	return false;
      is_load = false;
      ref = lhs;
    }
  else if (gimple_assign_load_p (stmt))
    {
      is_load = true;
      ref = gimple_assign_rhs1 (stmt);
    }
  else
    return false;

  if (may_be_nonaddressable_p (ref))
    return false;

  /* Mask should be integer mode of the same size as the load/store
     mode.  */
  mode = TYPE_MODE (TREE_TYPE (lhs));
  if (int_mode_for_mode (mode) == BLKmode
      || VECTOR_MODE_P (mode))
    return false;

  if (can_vec_mask_load_store_p (mode, VOIDmode, is_load))
    return true;

  return false;
}

/* Return true when STMT is if-convertible.

   GIMPLE_ASSIGN statement is not if-convertible if,
   - it is not movable,
   - it could trap,
   - LHS is not var decl.  */

static bool
if_convertible_gimple_assign_stmt_p (gimple *stmt,
				     vec<data_reference_p> refs)
{
  tree lhs = gimple_assign_lhs (stmt);

  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file, "-------------------------\n");
      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    }

  if (!is_gimple_reg_type (TREE_TYPE (lhs)))
    return false;

  /* Some of these constrains might be too conservative.  */
  if (stmt_ends_bb_p (stmt)
      || gimple_has_volatile_ops (stmt)
      || (TREE_CODE (lhs) == SSA_NAME
          && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
      || gimple_has_side_effects (stmt))
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
        fprintf (dump_file, "stmt not suitable for ifcvt\n");
      return false;
    }

  /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
     in between if_convertible_loop_p and combine_blocks
     we can perform loop versioning.  */
  gimple_set_plf (stmt, GF_PLF_2, false);

  if ((! gimple_vuse (stmt)
       || gimple_could_trap_p_1 (stmt, false, false)
       || ! ifcvt_memrefs_wont_trap (stmt, refs))
      && gimple_could_trap_p (stmt))
    {
      if (ifcvt_can_use_mask_load_store (stmt))
	{
	  gimple_set_plf (stmt, GF_PLF_2, true);
	  any_pred_load_store = true;
	  return true;
	}
      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file, "tree could trap...\n");
      return false;
    }

  /* When if-converting stores force versioning, likewise if we
     ended up generating store data races.  */
  if (gimple_vdef (stmt))
    any_pred_load_store = true;

  return true;
}

/* Return true when STMT is if-convertible.

   A statement is if-convertible if:
   - it is an if-convertible GIMPLE_ASSIGN,
   - it is a GIMPLE_LABEL or a GIMPLE_COND,
   - it is builtins call.  */

static bool
if_convertible_stmt_p (gimple *stmt, vec<data_reference_p> refs)
{
  switch (gimple_code (stmt))
    {
    case GIMPLE_LABEL:
    case GIMPLE_DEBUG:
    case GIMPLE_COND:
      return true;

    case GIMPLE_ASSIGN:
      return if_convertible_gimple_assign_stmt_p (stmt, refs);

    case GIMPLE_CALL:
      {
	tree fndecl = gimple_call_fndecl (stmt);
	if (fndecl)
	  {
	    int flags = gimple_call_flags (stmt);
	    if ((flags & ECF_CONST)
		&& !(flags & ECF_LOOPING_CONST_OR_PURE)
		/* We can only vectorize some builtins at the moment,
		   so restrict if-conversion to those.  */
		&& DECL_BUILT_IN (fndecl))
	      return true;
	  }
	return false;
      }

    default:
      /* Don't know what to do with 'em so don't do anything.  */
      if (dump_file && (dump_flags & TDF_DETAILS))
	{
	  fprintf (dump_file, "don't know what to do\n");
	  print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
	}
      return false;
    }

  return true;
}

/* Assumes that BB has more than 1 predecessors.
   Returns false if at least one successor is not on critical edge
   and true otherwise.  */

static inline bool
all_preds_critical_p (basic_block bb)
{
  edge e;
  edge_iterator ei;

  FOR_EACH_EDGE (e, ei, bb->preds)
    if (EDGE_COUNT (e->src->succs) == 1)
      return false;
  return true;
}

/* Returns true if at least one successor in on critical edge.  */
static inline bool
has_pred_critical_p (basic_block bb)
{
  edge e;
  edge_iterator ei;

  FOR_EACH_EDGE (e, ei, bb->preds)
    if (EDGE_COUNT (e->src->succs) > 1)
      return true;
  return false;
}

/* Return true when BB is if-convertible.  This routine does not check
   basic block's statements and phis.

   A basic block is not if-convertible if:
   - it is non-empty and it is after the exit block (in BFS order),
   - it is after the exit block but before the latch,
   - its edges are not normal.

   EXIT_BB is the basic block containing the exit of the LOOP.  BB is
   inside LOOP.  */

static bool
if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
{
  edge e;
  edge_iterator ei;

  if (dump_file && (dump_flags & TDF_DETAILS))
    fprintf (dump_file, "----------[%d]-------------\n", bb->index);

  if (EDGE_COUNT (bb->succs) > 2)
    return false;

  if (exit_bb)
    {
      if (bb != loop->latch)
	{
	  if (dump_file && (dump_flags & TDF_DETAILS))
	    fprintf (dump_file, "basic block after exit bb but before latch\n");
	  return false;
	}
      else if (!empty_block_p (bb))
	{
	  if (dump_file && (dump_flags & TDF_DETAILS))
	    fprintf (dump_file, "non empty basic block after exit bb\n");
	  return false;
	}
      else if (bb == loop->latch
	       && bb != exit_bb
	       && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
	  {
	    if (dump_file && (dump_flags & TDF_DETAILS))
	      fprintf (dump_file, "latch is not dominated by exit_block\n");
	    return false;
	  }
    }

  /* Be less adventurous and handle only normal edges.  */
  FOR_EACH_EDGE (e, ei, bb->succs)
    if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
      {
	if (dump_file && (dump_flags & TDF_DETAILS))
	  fprintf (dump_file, "Difficult to handle edges\n");
	return false;
      }

  return true;
}

/* Return true when all predecessor blocks of BB are visited.  The
   VISITED bitmap keeps track of the visited blocks.  */

static bool
pred_blocks_visited_p (basic_block bb, bitmap *visited)
{
  edge e;
  edge_iterator ei;
  FOR_EACH_EDGE (e, ei, bb->preds)
    if (!bitmap_bit_p (*visited, e->src->index))
      return false;

  return true;
}

/* Get body of a LOOP in suitable order for if-conversion.  It is
   caller's responsibility to deallocate basic block list.
   If-conversion suitable order is, breadth first sort (BFS) order
   with an additional constraint: select a block only if all its
   predecessors are already selected.  */

static basic_block *
get_loop_body_in_if_conv_order (const struct loop *loop)
{
  basic_block *blocks, *blocks_in_bfs_order;
  basic_block bb;
  bitmap visited;
  unsigned int index = 0;
  unsigned int visited_count = 0;

  gcc_assert (loop->num_nodes);
  gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));

  blocks = XCNEWVEC (basic_block, loop->num_nodes);
  visited = BITMAP_ALLOC (NULL);

  blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);

  index = 0;
  while (index < loop->num_nodes)
    {
      bb = blocks_in_bfs_order [index];

      if (bb->flags & BB_IRREDUCIBLE_LOOP)
	{
	  free (blocks_in_bfs_order);
	  BITMAP_FREE (visited);
	  free (blocks);
	  return NULL;
	}

      if (!bitmap_bit_p (visited, bb->index))
	{
	  if (pred_blocks_visited_p (bb, &visited)
	      || bb == loop->header)
	    {
	      /* This block is now visited.  */
	      bitmap_set_bit (visited, bb->index);
	      blocks[visited_count++] = bb;
	    }
	}

      index++;

      if (index == loop->num_nodes
	  && visited_count != loop->num_nodes)
	/* Not done yet.  */
	index = 0;
    }
  free (blocks_in_bfs_order);
  BITMAP_FREE (visited);
  return blocks;
}

/* Returns true when the analysis of the predicates for all the basic
   blocks in LOOP succeeded.

   predicate_bbs first allocates the predicates of the basic blocks.
   These fields are then initialized with the tree expressions
   representing the predicates under which a basic block is executed
   in the LOOP.  As the loop->header is executed at each iteration, it
   has the "true" predicate.  Other statements executed under a
   condition are predicated with that condition, for example

   | if (x)
   |   S1;
   | else
   |   S2;

   S1 will be predicated with "x", and
   S2 will be predicated with "!x".  */

static void
predicate_bbs (loop_p loop)
{
  unsigned int i;

  for (i = 0; i < loop->num_nodes; i++)
    init_bb_predicate (ifc_bbs[i]);

  for (i = 0; i < loop->num_nodes; i++)
    {
      basic_block bb = ifc_bbs[i];
      tree cond;
      gimple *stmt;

      /* The loop latch and loop exit block are always executed and
	 have no extra conditions to be processed: skip them.  */
      if (bb == loop->latch
	  || bb_with_exit_edge_p (loop, bb))
	{
	  reset_bb_predicate (bb);
	  continue;
	}

      cond = bb_predicate (bb);
      stmt = last_stmt (bb);
      if (stmt && gimple_code (stmt) == GIMPLE_COND)
	{
	  tree c2;
	  edge true_edge, false_edge;
	  location_t loc = gimple_location (stmt);
	  tree c = build2_loc (loc, gimple_cond_code (stmt),
				    boolean_type_node,
				    gimple_cond_lhs (stmt),
				    gimple_cond_rhs (stmt));

	  /* Add new condition into destination's predicate list.  */
	  extract_true_false_edges_from_block (gimple_bb (stmt),
					       &true_edge, &false_edge);

	  /* If C is true, then TRUE_EDGE is taken.  */
	  add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond),
				     unshare_expr (c));

	  /* If C is false, then FALSE_EDGE is taken.  */
	  c2 = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node,
			   unshare_expr (c));
	  add_to_dst_predicate_list (loop, false_edge,
				     unshare_expr (cond), c2);

	  cond = NULL_TREE;
	}

      /* If current bb has only one successor, then consider it as an
	 unconditional goto.  */
      if (single_succ_p (bb))
	{
	  basic_block bb_n = single_succ (bb);

	  /* The successor bb inherits the predicate of its
	     predecessor.  If there is no predicate in the predecessor
	     bb, then consider the successor bb as always executed.  */
	  if (cond == NULL_TREE)
	    cond = boolean_true_node;

	  add_to_predicate_list (loop, bb_n, cond);
	}
    }

  /* The loop header is always executed.  */
  reset_bb_predicate (loop->header);
  gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL
	      && bb_predicate_gimplified_stmts (loop->latch) == NULL);
}

/* Build region by adding loop pre-header and post-header blocks.  */

static vec<basic_block>
build_region (struct loop *loop)
{
  vec<basic_block> region = vNULL;
  basic_block exit_bb = NULL;

  gcc_assert (ifc_bbs);
  /* The first element is loop pre-header.  */
  region.safe_push (loop_preheader_edge (loop)->src);

  for (unsigned int i = 0; i < loop->num_nodes; i++)
    {
      basic_block bb = ifc_bbs[i];
      region.safe_push (bb);
      /* Find loop postheader.  */
      edge e;
      edge_iterator ei;
      FOR_EACH_EDGE (e, ei, bb->succs)
	if (loop_exit_edge_p (loop, e))
	  {
	      exit_bb = e->dest;
	      break;
	  }
    }
  /* The last element is loop post-header.  */
  gcc_assert (exit_bb);
  region.safe_push (exit_bb);
  return region;
}

/* Return true when LOOP is if-convertible.  This is a helper function
   for if_convertible_loop_p.  REFS and DDRS are initialized and freed
   in if_convertible_loop_p.  */

static bool
if_convertible_loop_p_1 (struct loop *loop, vec<data_reference_p> *refs)
{
  unsigned int i;
  basic_block exit_bb = NULL;
  vec<basic_block> region;

  if (find_data_references_in_loop (loop, refs) == chrec_dont_know)
    return false;

  calculate_dominance_info (CDI_DOMINATORS);

  /* Allow statements that can be handled during if-conversion.  */
  ifc_bbs = get_loop_body_in_if_conv_order (loop);
  if (!ifc_bbs)
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file, "Irreducible loop\n");
      return false;
    }

  for (i = 0; i < loop->num_nodes; i++)
    {
      basic_block bb = ifc_bbs[i];

      if (!if_convertible_bb_p (loop, bb, exit_bb))
	return false;

      if (bb_with_exit_edge_p (loop, bb))
	exit_bb = bb;
    }

  for (i = 0; i < loop->num_nodes; i++)
    {
      basic_block bb = ifc_bbs[i];
      gimple_stmt_iterator gsi;

      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
	switch (gimple_code (gsi_stmt (gsi)))
	  {
	  case GIMPLE_LABEL:
	  case GIMPLE_ASSIGN:
	  case GIMPLE_CALL:
	  case GIMPLE_DEBUG:
	  case GIMPLE_COND:
	    gimple_set_uid (gsi_stmt (gsi), 0);
	    break;
	  default:
	    return false;
	  }
    }

  data_reference_p dr;

  innermost_DR_map
	  = new hash_map<innermost_loop_behavior_hash, data_reference_p>;
  baseref_DR_map = new hash_map<tree_operand_hash, data_reference_p>;

  /* Compute post-dominator tree locally.  */
  region = build_region (loop);
  calculate_dominance_info_for_region (CDI_POST_DOMINATORS, region);

  predicate_bbs (loop);

  /* Free post-dominator tree since it is not used after predication.  */
  free_dominance_info_for_region (cfun, CDI_POST_DOMINATORS, region);
  region.release ();

  for (i = 0; refs->iterate (i, &dr); i++)
    {
      tree ref = DR_REF (dr);

      dr->aux = XNEW (struct ifc_dr);
      DR_BASE_W_UNCONDITIONALLY (dr) = false;
      DR_RW_UNCONDITIONALLY (dr) = false;
      DR_W_UNCONDITIONALLY (dr) = false;
      IFC_DR (dr)->rw_predicate = boolean_false_node;
      IFC_DR (dr)->w_predicate = boolean_false_node;
      IFC_DR (dr)->base_w_predicate = boolean_false_node;
      if (gimple_uid (DR_STMT (dr)) == 0)
	gimple_set_uid (DR_STMT (dr), i + 1);

      /* If DR doesn't have innermost loop behavior or it's a compound
         memory reference, we synthesize its innermost loop behavior
         for hashing.  */
      if (TREE_CODE (ref) == COMPONENT_REF
          || TREE_CODE (ref) == IMAGPART_EXPR
          || TREE_CODE (ref) == REALPART_EXPR
          || !(DR_BASE_ADDRESS (dr) || DR_OFFSET (dr)
	       || DR_INIT (dr) || DR_STEP (dr)))
        {
          while (TREE_CODE (ref) == COMPONENT_REF
	         || TREE_CODE (ref) == IMAGPART_EXPR
	         || TREE_CODE (ref) == REALPART_EXPR)
	    ref = TREE_OPERAND (ref, 0);

          DR_BASE_ADDRESS (dr) = ref;
          DR_OFFSET (dr) = NULL;
          DR_INIT (dr) = NULL;
          DR_STEP (dr) = NULL;
          DR_ALIGNED_TO (dr) = NULL;
        }
      hash_memrefs_baserefs_and_store_DRs_read_written_info (dr);
    }

  for (i = 0; i < loop->num_nodes; i++)
    {
      basic_block bb = ifc_bbs[i];
      gimple_stmt_iterator itr;

      /* Check the if-convertibility of statements in predicated BBs.  */
      if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
	for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
	  if (!if_convertible_stmt_p (gsi_stmt (itr), *refs))
	    return false;
    }

  /* Checking PHIs needs to be done after stmts, as the fact whether there
     are any masked loads or stores affects the tests.  */
  for (i = 0; i < loop->num_nodes; i++)
    {
      basic_block bb = ifc_bbs[i];
      gphi_iterator itr;

      for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
	if (!if_convertible_phi_p (loop, bb, itr.phi ()))
	  return false;
    }

  if (dump_file)
    fprintf (dump_file, "Applying if-conversion\n");

  return true;
}

/* Return true when LOOP is if-convertible.
   LOOP is if-convertible if:
   - it is innermost,
   - it has two or more basic blocks,
   - it has only one exit,
   - loop header is not the exit edge,
   - if its basic blocks and phi nodes are if convertible.  */

static bool
if_convertible_loop_p (struct loop *loop)
{
  edge e;
  edge_iterator ei;
  bool res = false;
  vec<data_reference_p> refs;

  /* Handle only innermost loop.  */
  if (!loop || loop->inner)
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file, "not innermost loop\n");
      return false;
    }

  /* If only one block, no need for if-conversion.  */
  if (loop->num_nodes <= 2)
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file, "less than 2 basic blocks\n");
      return false;
    }

  /* More than one loop exit is too much to handle.  */
  if (!single_exit (loop))
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file, "multiple exits\n");
      return false;
    }

  /* If one of the loop header's edge is an exit edge then do not
     apply if-conversion.  */
  FOR_EACH_EDGE (e, ei, loop->header->succs)
    if (loop_exit_edge_p (loop, e))
      return false;

  refs.create (5);
  res = if_convertible_loop_p_1 (loop, &refs);

  data_reference_p dr;
  unsigned int i;
  for (i = 0; refs.iterate (i, &dr); i++)
    free (dr->aux);

  free_data_refs (refs);

  delete innermost_DR_map;
  innermost_DR_map = NULL;

  delete baseref_DR_map;
  baseref_DR_map = NULL;

  return res;
}

/* Returns true if def-stmt for phi argument ARG is simple increment/decrement
   which is in predicated basic block.
   In fact, the following PHI pattern is searching:
      loop-header:
	reduc_1 = PHI <..., reduc_2>
      ...
	if (...)
	  reduc_3 = ...
	reduc_2 = PHI <reduc_1, reduc_3>

   ARG_0 and ARG_1 are correspondent PHI arguments.
   REDUC, OP0 and OP1 contain reduction stmt and its operands.
   EXTENDED is true if PHI has > 2 arguments.  */

static bool
is_cond_scalar_reduction (gimple *phi, gimple **reduc, tree arg_0, tree arg_1,
			  tree *op0, tree *op1, bool extended)
{
  tree lhs, r_op1, r_op2;
  gimple *stmt;
  gimple *header_phi = NULL;
  enum tree_code reduction_op;
  basic_block bb = gimple_bb (phi);
  struct loop *loop = bb->loop_father;
  edge latch_e = loop_latch_edge (loop);
  imm_use_iterator imm_iter;
  use_operand_p use_p;
  edge e;
  edge_iterator ei;
  bool result = false;
  if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME)
    return false;

  if (!extended && gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI)
    {
      lhs = arg_1;
      header_phi = SSA_NAME_DEF_STMT (arg_0);
      stmt = SSA_NAME_DEF_STMT (arg_1);
    }
  else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI)
    {
      lhs = arg_0;
      header_phi = SSA_NAME_DEF_STMT (arg_1);
      stmt = SSA_NAME_DEF_STMT (arg_0);
    }
  else
    return false;
  if (gimple_bb (header_phi) != loop->header)
    return false;

  if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi))
    return false;

  if (gimple_code (stmt) != GIMPLE_ASSIGN
      || gimple_has_volatile_ops (stmt))
    return false;

  if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
    return false;

  if (!is_predicated (gimple_bb (stmt)))
    return false;

  /* Check that stmt-block is predecessor of phi-block.  */
  FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
    if (e->dest == bb)
      {
	result = true;
	break;
      }
  if (!result)
    return false;

  if (!has_single_use (lhs))
    return false;

  reduction_op = gimple_assign_rhs_code (stmt);
  if (reduction_op != PLUS_EXPR && reduction_op != MINUS_EXPR)
    return false;
  r_op1 = gimple_assign_rhs1 (stmt);
  r_op2 = gimple_assign_rhs2 (stmt);

  /* Make R_OP1 to hold reduction variable.  */
  if (r_op2 == PHI_RESULT (header_phi)
      && reduction_op == PLUS_EXPR)
    std::swap (r_op1, r_op2);
  else if (r_op1 != PHI_RESULT (header_phi))
    return false;

  /* Check that R_OP1 is used in reduction stmt or in PHI only.  */
  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1)
    {
      gimple *use_stmt = USE_STMT (use_p);
      if (is_gimple_debug (use_stmt))
	continue;
      if (use_stmt == stmt)
	continue;
      if (gimple_code (use_stmt) != GIMPLE_PHI)
	return false;
    }

  *op0 = r_op1; *op1 = r_op2;
  *reduc = stmt;
  return true;
}

/* Converts conditional scalar reduction into unconditional form, e.g.
     bb_4
       if (_5 != 0) goto bb_5 else goto bb_6
     end_bb_4
     bb_5
       res_6 = res_13 + 1;
     end_bb_5
     bb_6
       # res_2 = PHI <res_13(4), res_6(5)>
     end_bb_6

   will be converted into sequence
    _ifc__1 = _5 != 0 ? 1 : 0;
    res_2 = res_13 + _ifc__1;
  Argument SWAP tells that arguments of conditional expression should be
  swapped.
  Returns rhs of resulting PHI assignment.  */

static tree
convert_scalar_cond_reduction (gimple *reduc, gimple_stmt_iterator *gsi,
			       tree cond, tree op0, tree op1, bool swap)
{
  gimple_stmt_iterator stmt_it;
  gimple *new_assign;
  tree rhs;
  tree rhs1 = gimple_assign_rhs1 (reduc);
  tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_");
  tree c;
  tree zero = build_zero_cst (TREE_TYPE (rhs1));

  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file, "Found cond scalar reduction.\n");
      print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM);
    }

  /* Build cond expression using COND and constant operand
     of reduction rhs.  */
  c = fold_build_cond_expr (TREE_TYPE (rhs1),
			    unshare_expr (cond),
			    swap ? zero : op1,
			    swap ? op1 : zero);

  /* Create assignment stmt and insert it at GSI.  */
  new_assign = gimple_build_assign (tmp, c);
  gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
  /* Build rhs for unconditional increment/decrement.  */
  rhs = fold_build2 (gimple_assign_rhs_code (reduc),
		     TREE_TYPE (rhs1), op0, tmp);

  /* Delete original reduction stmt.  */
  stmt_it = gsi_for_stmt (reduc);
  gsi_remove (&stmt_it, true);
  release_defs (reduc);
  return rhs;
}

/* Produce condition for all occurrences of ARG in PHI node.  */

static tree
gen_phi_arg_condition (gphi *phi, vec<int> *occur,
		       gimple_stmt_iterator *gsi)
{
  int len;
  int i;
  tree cond = NULL_TREE;
  tree c;
  edge e;

  len = occur->length ();
  gcc_assert (len > 0);
  for (i = 0; i < len; i++)
    {
      e = gimple_phi_arg_edge (phi, (*occur)[i]);
      c = bb_predicate (e->src);
      if (is_true_predicate (c))
	{
	  cond = c;
	  break;
	}
      c = force_gimple_operand_gsi_1 (gsi, unshare_expr (c),
				      is_gimple_condexpr, NULL_TREE,
				      true, GSI_SAME_STMT);
      if (cond != NULL_TREE)
	{
	  /* Must build OR expression.  */
	  cond = fold_or_predicates (EXPR_LOCATION (c), c, cond);
	  cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
					     is_gimple_condexpr, NULL_TREE,
					     true, GSI_SAME_STMT);
	}
      else
	cond = c;
    }
  gcc_assert (cond != NULL_TREE);
  return cond;
}

/* Local valueization callback that follows all-use SSA edges.  */

static tree
ifcvt_follow_ssa_use_edges (tree val)
{
  return val;
}

/* Replace a scalar PHI node with a COND_EXPR using COND as condition.
   This routine can handle PHI nodes with more than two arguments.

   For example,
     S1: A = PHI <x1(1), x2(5)>
   is converted into,
     S2: A = cond ? x1 : x2;

   The generated code is inserted at GSI that points to the top of
   basic block's statement list.
   If PHI node has more than two arguments a chain of conditional
   expression is produced.  */


static void
predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi)
{
  gimple *new_stmt = NULL, *reduc;
  tree rhs, res, arg0, arg1, op0, op1, scev;
  tree cond;
  unsigned int index0;
  unsigned int max, args_len;
  edge e;
  basic_block bb;
  unsigned int i;

  res = gimple_phi_result (phi);
  if (virtual_operand_p (res))
    return;

  if ((rhs = degenerate_phi_result (phi))
      || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father,
					    res))
	  && !chrec_contains_undetermined (scev)
	  && scev != res
	  && (rhs = gimple_phi_arg_def (phi, 0))))
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
	{
	  fprintf (dump_file, "Degenerate phi!\n");
	  print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
	}
      new_stmt = gimple_build_assign (res, rhs);
      gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
      update_stmt (new_stmt);
      return;
    }

  bb = gimple_bb (phi);
  if (EDGE_COUNT (bb->preds) == 2)
    {
      /* Predicate ordinary PHI node with 2 arguments.  */
      edge first_edge, second_edge;
      basic_block true_bb;
      first_edge = EDGE_PRED (bb, 0);
      second_edge = EDGE_PRED (bb, 1);
      cond = bb_predicate (first_edge->src);
      if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
	std::swap (first_edge, second_edge);
      if (EDGE_COUNT (first_edge->src->succs) > 1)
	{
	  cond = bb_predicate (second_edge->src);
	  if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
	    cond = TREE_OPERAND (cond, 0);
	  else
	    first_edge = second_edge;
	}
      else
	cond = bb_predicate (first_edge->src);
      /* Gimplify the condition to a valid cond-expr conditonal operand.  */
      cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
					 is_gimple_condexpr, NULL_TREE,
					 true, GSI_SAME_STMT);
      true_bb = first_edge->src;
      if (EDGE_PRED (bb, 1)->src == true_bb)
	{
	  arg0 = gimple_phi_arg_def (phi, 1);
	  arg1 = gimple_phi_arg_def (phi, 0);
	}
      else
	{
	  arg0 = gimple_phi_arg_def (phi, 0);
	  arg1 = gimple_phi_arg_def (phi, 1);
	}
      if (is_cond_scalar_reduction (phi, &reduc, arg0, arg1,
				    &op0, &op1, false))
	/* Convert reduction stmt into vectorizable form.  */
	rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
					     true_bb != gimple_bb (reduc));
      else
	/* Build new RHS using selected condition and arguments.  */
	rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
				    arg0, arg1);
      new_stmt = gimple_build_assign (res, rhs);
      gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
      gimple_stmt_iterator new_gsi = gsi_for_stmt (new_stmt);
      fold_stmt (&new_gsi, ifcvt_follow_ssa_use_edges);
      update_stmt (new_stmt);

      if (dump_file && (dump_flags & TDF_DETAILS))
	{
	  fprintf (dump_file, "new phi replacement stmt\n");
	  print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
	}
      return;
    }

  /* Create hashmap for PHI node which contain vector of argument indexes
     having the same value.  */
  bool swap = false;
  hash_map<tree_operand_hash, auto_vec<int> > phi_arg_map;
  unsigned int num_args = gimple_phi_num_args (phi);
  int max_ind = -1;
  /* Vector of different PHI argument values.  */
  auto_vec<tree> args (num_args);

  /* Compute phi_arg_map.  */
  for (i = 0; i < num_args; i++)
    {
      tree arg;

      arg = gimple_phi_arg_def (phi, i);
      if (!phi_arg_map.get (arg))
	args.quick_push (arg);
      phi_arg_map.get_or_insert (arg).safe_push (i);
    }

  /* Determine element with max number of occurrences.  */
  max_ind = -1;
  max = 1;
  args_len = args.length ();
  for (i = 0; i < args_len; i++)
    {
      unsigned int len;
      if ((len = phi_arg_map.get (args[i])->length ()) > max)
	{
	  max_ind = (int) i;
	  max = len;
	}
    }

  /* Put element with max number of occurences to the end of ARGS.  */
  if (max_ind != -1 && max_ind +1 != (int) args_len)
    std::swap (args[args_len - 1], args[max_ind]);

  /* Handle one special case when number of arguments with different values
     is equal 2 and one argument has the only occurrence.  Such PHI can be
     handled as if would have only 2 arguments.  */
  if (args_len == 2 && phi_arg_map.get (args[0])->length () == 1)
    {
      vec<int> *indexes;
      indexes = phi_arg_map.get (args[0]);
      index0 = (*indexes)[0];
      arg0 = args[0];
      arg1 = args[1];
      e = gimple_phi_arg_edge (phi, index0);
      cond = bb_predicate (e->src);
      if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
	{
	  swap = true;
	  cond = TREE_OPERAND (cond, 0);
	}
      /* Gimplify the condition to a valid cond-expr conditonal operand.  */
      cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
					 is_gimple_condexpr, NULL_TREE,
					 true, GSI_SAME_STMT);
      if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1,
				      &op0, &op1, true)))
	rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
				    swap? arg1 : arg0,
				    swap? arg0 : arg1);
      else
	/* Convert reduction stmt into vectorizable form.  */
	rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
					     swap);
      new_stmt = gimple_build_assign (res, rhs);
      gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
      update_stmt (new_stmt);
    }
  else
    {
      /* Common case.  */
      vec<int> *indexes;
      tree type = TREE_TYPE (gimple_phi_result (phi));
      tree lhs;
      arg1 = args[1];
      for (i = 0; i < args_len; i++)
	{
	  arg0 = args[i];
	  indexes = phi_arg_map.get (args[i]);
	  if (i != args_len - 1)
	    lhs = make_temp_ssa_name (type, NULL, "_ifc_");
	  else
	    lhs = res;
	  cond = gen_phi_arg_condition (phi, indexes, gsi);
	  rhs = fold_build_cond_expr (type, unshare_expr (cond),
				      arg0, arg1);
	  new_stmt = gimple_build_assign (lhs, rhs);
	  gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
	  update_stmt (new_stmt);
	  arg1 = lhs;
	}
    }

  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file, "new extended phi replacement stmt\n");
      print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
    }
}

/* Replaces in LOOP all the scalar phi nodes other than those in the
   LOOP->header block with conditional modify expressions.  */

static void
predicate_all_scalar_phis (struct loop *loop)
{
  basic_block bb;
  unsigned int orig_loop_num_nodes = loop->num_nodes;
  unsigned int i;

  for (i = 1; i < orig_loop_num_nodes; i++)
    {
      gphi *phi;
      gimple_stmt_iterator gsi;
      gphi_iterator phi_gsi;
      bb = ifc_bbs[i];

      if (bb == loop->header)
	continue;

      phi_gsi = gsi_start_phis (bb);
      if (gsi_end_p (phi_gsi))
	continue;

      gsi = gsi_after_labels (bb);
      while (!gsi_end_p (phi_gsi))
	{
	  phi = phi_gsi.phi ();
	  if (virtual_operand_p (gimple_phi_result (phi)))
	    gsi_next (&phi_gsi);
	  else
	    {
	      predicate_scalar_phi (phi, &gsi);
	      remove_phi_node (&phi_gsi, false);
	    }
	}
    }
}

/* Insert in each basic block of LOOP the statements produced by the
   gimplification of the predicates.  */

static void
insert_gimplified_predicates (loop_p loop)
{
  unsigned int i;

  for (i = 0; i < loop->num_nodes; i++)
    {
      basic_block bb = ifc_bbs[i];
      gimple_seq stmts;
      if (!is_predicated (bb))
	gcc_assert (bb_predicate_gimplified_stmts (bb) == NULL);
      if (!is_predicated (bb))
	{
	  /* Do not insert statements for a basic block that is not
	     predicated.  Also make sure that the predicate of the
	     basic block is set to true.  */
	  reset_bb_predicate (bb);
	  continue;
	}

      stmts = bb_predicate_gimplified_stmts (bb);
      if (stmts)
	{
	  if (any_pred_load_store)
	    {
	      /* Insert the predicate of the BB just after the label,
		 as the if-conversion of memory writes will use this
		 predicate.  */
	      gimple_stmt_iterator gsi = gsi_after_labels (bb);
	      gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
	    }
	  else
	    {
	      /* Insert the predicate of the BB at the end of the BB
		 as this would reduce the register pressure: the only
		 use of this predicate will be in successor BBs.  */
	      gimple_stmt_iterator gsi = gsi_last_bb (bb);

	      if (gsi_end_p (gsi)
		  || stmt_ends_bb_p (gsi_stmt (gsi)))
		gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
	      else
		gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
	    }

	  /* Once the sequence is code generated, set it to NULL.  */
	  set_bb_predicate_gimplified_stmts (bb, NULL);
	}
    }
}

/* Helper function for predicate_mem_writes. Returns index of existent
   mask if it was created for given SIZE and -1 otherwise.  */

static int
mask_exists (int size, vec<int> vec)
{
  unsigned int ix;
  int v;
  FOR_EACH_VEC_ELT (vec, ix, v)
    if (v == size)
      return (int) ix;
  return -1;
}

/* Predicate each write to memory in LOOP.

   This function transforms control flow constructs containing memory
   writes of the form:

   | for (i = 0; i < N; i++)
   |   if (cond)
   |     A[i] = expr;

   into the following form that does not contain control flow:

   | for (i = 0; i < N; i++)
   |   A[i] = cond ? expr : A[i];

   The original CFG looks like this:

   | bb_0
   |   i = 0
   | end_bb_0
   |
   | bb_1
   |   if (i < N) goto bb_5 else goto bb_2
   | end_bb_1
   |
   | bb_2
   |   cond = some_computation;
   |   if (cond) goto bb_3 else goto bb_4
   | end_bb_2
   |
   | bb_3
   |   A[i] = expr;
   |   goto bb_4
   | end_bb_3
   |
   | bb_4
   |   goto bb_1
   | end_bb_4

   insert_gimplified_predicates inserts the computation of the COND
   expression at the beginning of the destination basic block:

   | bb_0
   |   i = 0
   | end_bb_0
   |
   | bb_1
   |   if (i < N) goto bb_5 else goto bb_2
   | end_bb_1
   |
   | bb_2
   |   cond = some_computation;
   |   if (cond) goto bb_3 else goto bb_4
   | end_bb_2
   |
   | bb_3
   |   cond = some_computation;
   |   A[i] = expr;
   |   goto bb_4
   | end_bb_3
   |
   | bb_4
   |   goto bb_1
   | end_bb_4

   predicate_mem_writes is then predicating the memory write as follows:

   | bb_0
   |   i = 0
   | end_bb_0
   |
   | bb_1
   |   if (i < N) goto bb_5 else goto bb_2
   | end_bb_1
   |
   | bb_2
   |   if (cond) goto bb_3 else goto bb_4
   | end_bb_2
   |
   | bb_3
   |   cond = some_computation;
   |   A[i] = cond ? expr : A[i];
   |   goto bb_4
   | end_bb_3
   |
   | bb_4
   |   goto bb_1
   | end_bb_4

   and finally combine_blocks removes the basic block boundaries making
   the loop vectorizable:

   | bb_0
   |   i = 0
   |   if (i < N) goto bb_5 else goto bb_1
   | end_bb_0
   |
   | bb_1
   |   cond = some_computation;
   |   A[i] = cond ? expr : A[i];
   |   if (i < N) goto bb_5 else goto bb_4
   | end_bb_1
   |
   | bb_4
   |   goto bb_1
   | end_bb_4
*/

static void
predicate_mem_writes (loop_p loop)
{
  unsigned int i, orig_loop_num_nodes = loop->num_nodes;
  auto_vec<int, 1> vect_sizes;
  auto_vec<tree, 1> vect_masks;

  for (i = 1; i < orig_loop_num_nodes; i++)
    {
      gimple_stmt_iterator gsi;
      basic_block bb = ifc_bbs[i];
      tree cond = bb_predicate (bb);
      bool swap;
      gimple *stmt;
      int index;

      if (is_true_predicate (cond))
	continue;

      swap = false;
      if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
	{
	  swap = true;
	  cond = TREE_OPERAND (cond, 0);
	}

      vect_sizes.truncate (0);
      vect_masks.truncate (0);

      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
	{
	  if (!gimple_assign_single_p (stmt = gsi_stmt (gsi)))
	    ;
	  else if (is_false_predicate (cond)
		   && gimple_vdef (stmt))
	    {
	      unlink_stmt_vdef (stmt);
	      gsi_remove (&gsi, true);
	      release_defs (stmt);
	      continue;
	    }
	  else if (gimple_plf (stmt, GF_PLF_2))
	    {
	      tree lhs = gimple_assign_lhs (stmt);
	      tree rhs = gimple_assign_rhs1 (stmt);
	      tree ref, addr, ptr, mask;
	      gimple *new_stmt;
	      gimple_seq stmts = NULL;
	      int bitsize = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs)));
	      ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs;
	      mark_addressable (ref);
	      addr = force_gimple_operand_gsi (&gsi, build_fold_addr_expr (ref),
					       true, NULL_TREE, true,
					       GSI_SAME_STMT);
	      if (!vect_sizes.is_empty ()
		  && (index = mask_exists (bitsize, vect_sizes)) != -1)
		/* Use created mask.  */
		mask = vect_masks[index];
	      else
		{
		  if (COMPARISON_CLASS_P (cond))
		    mask = gimple_build (&stmts, TREE_CODE (cond),
					 boolean_type_node,
					 TREE_OPERAND (cond, 0),
					 TREE_OPERAND (cond, 1));
		  else
		    mask = cond;

		  if (swap)
		    {
		      tree true_val
			= constant_boolean_node (true, TREE_TYPE (mask));
		      mask = gimple_build (&stmts, BIT_XOR_EXPR,
					   TREE_TYPE (mask), mask, true_val);
		    }
		  gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);

		  mask = ifc_temp_var (TREE_TYPE (mask), mask, &gsi);
		  /* Save mask and its size for further use.  */
		  vect_sizes.safe_push (bitsize);
		  vect_masks.safe_push (mask);
		}
	      ptr = build_int_cst (reference_alias_ptr_type (ref),
				   get_object_alignment (ref));
	      /* Copy points-to info if possible.  */
	      if (TREE_CODE (addr) == SSA_NAME && !SSA_NAME_PTR_INFO (addr))
		copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr),
			       ref);
	      if (TREE_CODE (lhs) == SSA_NAME)
		{
		  new_stmt
		    = gimple_build_call_internal (IFN_MASK_LOAD, 3, addr,
						  ptr, mask);
		  gimple_call_set_lhs (new_stmt, lhs);
		  gimple_set_vuse (new_stmt, gimple_vuse (stmt));
		}
	      else
		{
		  new_stmt
		    = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr,
						  mask, rhs);
		  gimple_set_vuse (new_stmt, gimple_vuse (stmt));
		  gimple_set_vdef (new_stmt, gimple_vdef (stmt));
		  SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
		}

	      gsi_replace (&gsi, new_stmt, true);
	    }
	  else if (gimple_vdef (stmt))
	    {
	      tree lhs = gimple_assign_lhs (stmt);
	      tree rhs = gimple_assign_rhs1 (stmt);
	      tree type = TREE_TYPE (lhs);

	      lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
	      rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
	      if (swap)
		std::swap (lhs, rhs);
	      cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond),
						 is_gimple_condexpr, NULL_TREE,
						 true, GSI_SAME_STMT);
	      rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs);
	      gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
	      update_stmt (stmt);
	    }
	  gsi_next (&gsi);
	}
    }
}

/* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
   other than the exit and latch of the LOOP.  Also resets the
   GIMPLE_DEBUG information.  */

static void
remove_conditions_and_labels (loop_p loop)
{
  gimple_stmt_iterator gsi;
  unsigned int i;

  for (i = 0; i < loop->num_nodes; i++)
    {
      basic_block bb = ifc_bbs[i];

      if (bb_with_exit_edge_p (loop, bb)
        || bb == loop->latch)
      continue;

      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
	switch (gimple_code (gsi_stmt (gsi)))
	  {
	  case GIMPLE_COND:
	  case GIMPLE_LABEL:
	    gsi_remove (&gsi, true);
	    break;

	  case GIMPLE_DEBUG:
	    /* ??? Should there be conditional GIMPLE_DEBUG_BINDs?  */
	    if (gimple_debug_bind_p (gsi_stmt (gsi)))
	      {
		gimple_debug_bind_reset_value (gsi_stmt (gsi));
		update_stmt (gsi_stmt (gsi));
	      }
	    gsi_next (&gsi);
	    break;

	  default:
	    gsi_next (&gsi);
	  }
    }
}

/* Combine all the basic blocks from LOOP into one or two super basic
   blocks.  Replace PHI nodes with conditional modify expressions.  */

static void
combine_blocks (struct loop *loop)
{
  basic_block bb, exit_bb, merge_target_bb;
  unsigned int orig_loop_num_nodes = loop->num_nodes;
  unsigned int i;
  edge e;
  edge_iterator ei;

  remove_conditions_and_labels (loop);
  insert_gimplified_predicates (loop);
  predicate_all_scalar_phis (loop);

  if (any_pred_load_store)
    predicate_mem_writes (loop);

  /* Merge basic blocks: first remove all the edges in the loop,
     except for those from the exit block.  */
  exit_bb = NULL;
  bool *predicated = XNEWVEC (bool, orig_loop_num_nodes);
  for (i = 0; i < orig_loop_num_nodes; i++)
    {
      bb = ifc_bbs[i];
      predicated[i] = !is_true_predicate (bb_predicate (bb));
      free_bb_predicate (bb);
      if (bb_with_exit_edge_p (loop, bb))
	{
	  gcc_assert (exit_bb == NULL);
	  exit_bb = bb;
	}
    }
  gcc_assert (exit_bb != loop->latch);

  for (i = 1; i < orig_loop_num_nodes; i++)
    {
      bb = ifc_bbs[i];

      for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
	{
	  if (e->src == exit_bb)
	    ei_next (&ei);
	  else
	    remove_edge (e);
	}
    }

  if (exit_bb != NULL)
    {
      if (exit_bb != loop->header)
	{
	  /* Connect this node to loop header.  */
	  make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
	  set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
	}

      /* Redirect non-exit edges to loop->latch.  */
      FOR_EACH_EDGE (e, ei, exit_bb->succs)
	{
	  if (!loop_exit_edge_p (loop, e))
	    redirect_edge_and_branch (e, loop->latch);
	}
      set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
    }
  else
    {
      /* If the loop does not have an exit, reconnect header and latch.  */
      make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
      set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
    }

  merge_target_bb = loop->header;

  /* Get at the virtual def valid for uses starting at the first block
     we merge into the header.  Without a virtual PHI the loop has the
     same virtual use on all stmts.  */
  gphi *vphi = get_virtual_phi (loop->header);
  tree last_vdef = NULL_TREE;
  if (vphi)
    {
      last_vdef = gimple_phi_result (vphi);
      for (gimple_stmt_iterator gsi = gsi_start_bb (loop->header);
	   ! gsi_end_p (gsi); gsi_next (&gsi))
	if (gimple_vdef (gsi_stmt (gsi)))
	  last_vdef = gimple_vdef (gsi_stmt (gsi));
    }
  for (i = 1; i < orig_loop_num_nodes; i++)
    {
      gimple_stmt_iterator gsi;
      gimple_stmt_iterator last;

      bb = ifc_bbs[i];

      if (bb == exit_bb || bb == loop->latch)
	continue;

      /* We release virtual PHIs late because we have to propagate them
         out using the current VUSE.  The def might be the one used
	 after the loop.  */
      vphi = get_virtual_phi (bb);
      if (vphi)
	{
	  imm_use_iterator iter;
	  use_operand_p use_p;
	  gimple *use_stmt;
	  FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi))
	    {
	      FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
		SET_USE (use_p, last_vdef);
	    }
	  gsi = gsi_for_stmt (vphi); 
	  remove_phi_node (&gsi, true);
	}

      /* Make stmts member of loop->header and clear range info from all stmts
	 in BB which is now no longer executed conditional on a predicate we
	 could have derived it from.  */
      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
	{
	  gimple *stmt = gsi_stmt (gsi);
	  gimple_set_bb (stmt, merge_target_bb);
	  /* Update virtual operands.  */
	  if (last_vdef)
	    {
	      use_operand_p use_p = ssa_vuse_operand (stmt);
	      if (use_p
		  && USE_FROM_PTR (use_p) != last_vdef)
		SET_USE (use_p, last_vdef);
	      if (gimple_vdef (stmt))
		last_vdef = gimple_vdef (stmt);
	    }
	  if (predicated[i])
	    {
	      ssa_op_iter i;
	      tree op;
	      FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF)
		reset_flow_sensitive_info (op);
	    }
	}

      /* Update stmt list.  */
      last = gsi_last_bb (merge_target_bb);
      gsi_insert_seq_after_without_update (&last, bb_seq (bb), GSI_NEW_STMT);
      set_bb_seq (bb, NULL);

      delete_basic_block (bb);
    }

  /* If possible, merge loop header to the block with the exit edge.
     This reduces the number of basic blocks to two, to please the
     vectorizer that handles only loops with two nodes.  */
  if (exit_bb
      && exit_bb != loop->header)
    {
      /* We release virtual PHIs late because we have to propagate them
         out using the current VUSE.  The def might be the one used
	 after the loop.  */
      vphi = get_virtual_phi (exit_bb);
      if (vphi)
	{
	  imm_use_iterator iter;
	  use_operand_p use_p;
	  gimple *use_stmt;
	  FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi))
	    {
	      FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
		SET_USE (use_p, last_vdef);
	    }
	  gimple_stmt_iterator gsi = gsi_for_stmt (vphi); 
	  remove_phi_node (&gsi, true);
	}

      if (can_merge_blocks_p (loop->header, exit_bb))
	merge_blocks (loop->header, exit_bb);
    }

  free (ifc_bbs);
  ifc_bbs = NULL;
  free (predicated);
}

/* Version LOOP before if-converting it; the original loop
   will be if-converted, the new copy of the loop will not,
   and the LOOP_VECTORIZED internal call will be guarding which
   loop to execute.  The vectorizer pass will fold this
   internal call into either true or false. 

   Note that this function intentionally invalidates profile.  Both edges
   out of LOOP_VECTORIZED must have 100% probability so the profile remains
   consistent after the condition is folded in the vectorizer.  */

static struct loop *
version_loop_for_if_conversion (struct loop *loop)
{
  basic_block cond_bb;
  tree cond = make_ssa_name (boolean_type_node);
  struct loop *new_loop;
  gimple *g;
  gimple_stmt_iterator gsi;
  unsigned int save_length;

  g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2,
				  build_int_cst (integer_type_node, loop->num),
				  integer_zero_node);
  gimple_call_set_lhs (g, cond);

  /* Save BB->aux around loop_version as that uses the same field.  */
  save_length = loop->inner ? loop->inner->num_nodes : loop->num_nodes;
  void **saved_preds = XALLOCAVEC (void *, save_length);
  for (unsigned i = 0; i < save_length; i++)
    saved_preds[i] = ifc_bbs[i]->aux;

  initialize_original_copy_tables ();
  /* At this point we invalidate porfile confistency until IFN_LOOP_VECTORIZED
     is re-merged in the vectorizer.  */
  new_loop = loop_version (loop, cond, &cond_bb,
			   REG_BR_PROB_BASE, REG_BR_PROB_BASE,
			   REG_BR_PROB_BASE, REG_BR_PROB_BASE, true);
  free_original_copy_tables ();

  for (unsigned i = 0; i < save_length; i++)
    ifc_bbs[i]->aux = saved_preds[i];

  if (new_loop == NULL)
    return NULL;

  new_loop->dont_vectorize = true;
  new_loop->force_vectorize = false;
  gsi = gsi_last_bb (cond_bb);
  gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num));
  gsi_insert_before (&gsi, g, GSI_SAME_STMT);
  update_ssa (TODO_update_ssa);
  return new_loop;
}

/* Return true when LOOP satisfies the follow conditions that will
   allow it to be recognized by the vectorizer for outer-loop
   vectorization:
    - The loop is not the root node of the loop tree.
    - The loop has exactly one inner loop.
    - The loop has a single exit.
    - The loop header has a single successor, which is the inner
      loop header.
    - Each of the inner and outer loop latches have a single
      predecessor.
    - The loop exit block has a single predecessor, which is the
      inner loop's exit block.  */

static bool
versionable_outer_loop_p (struct loop *loop)
{
  if (!loop_outer (loop)
      || loop->dont_vectorize
      || !loop->inner
      || loop->inner->next
      || !single_exit (loop)
      || !single_succ_p (loop->header)
      || single_succ (loop->header) != loop->inner->header
      || !single_pred_p (loop->latch)
      || !single_pred_p (loop->inner->latch))
    return false;

  basic_block outer_exit = single_pred (loop->latch);
  basic_block inner_exit = single_pred (loop->inner->latch);

  if (!single_pred_p (outer_exit) || single_pred (outer_exit) != inner_exit)
    return false;

  if (dump_file)
    fprintf (dump_file, "Found vectorizable outer loop for versioning\n");

  return true;
}

/* Performs splitting of critical edges.  Skip splitting and return false
   if LOOP will not be converted because:

     - LOOP is not well formed.
     - LOOP has PHI with more than MAX_PHI_ARG_NUM arguments.

   Last restriction is valid only if AGGRESSIVE_IF_CONV is false.  */

static bool
ifcvt_split_critical_edges (struct loop *loop, bool aggressive_if_conv)
{
  basic_block *body;
  basic_block bb;
  unsigned int num = loop->num_nodes;
  unsigned int i;
  gimple *stmt;
  edge e;
  edge_iterator ei;
  auto_vec<edge> critical_edges;

  /* Loop is not well formed.  */
  if (num <= 2 || loop->inner || !single_exit (loop))
    return false;

  body = get_loop_body (loop);
  for (i = 0; i < num; i++)
    {
      bb = body[i];
      if (!aggressive_if_conv
	  && phi_nodes (bb)
	  && EDGE_COUNT (bb->preds) > MAX_PHI_ARG_NUM)
	{
	  if (dump_file && (dump_flags & TDF_DETAILS))
	    fprintf (dump_file,
		     "BB %d has complicated PHI with more than %u args.\n",
		     bb->index, MAX_PHI_ARG_NUM);

	  free (body);
	  return false;
	}
      if (bb == loop->latch || bb_with_exit_edge_p (loop, bb))
	continue;

      stmt = last_stmt (bb);
      /* Skip basic blocks not ending with conditional branch.  */
      if (!stmt || gimple_code (stmt) != GIMPLE_COND)
	continue;

      FOR_EACH_EDGE (e, ei, bb->succs)
	if (EDGE_CRITICAL_P (e) && e->dest->loop_father == loop)
	  critical_edges.safe_push (e);
    }
  free (body);

  while (critical_edges.length () > 0)
    {
      e = critical_edges.pop ();
      /* Don't split if bb can be predicated along non-critical edge.  */
      if (EDGE_COUNT (e->dest->preds) > 2 || all_preds_critical_p (e->dest))
	split_edge (e);
    }

  return true;
}

/* Delete redundant statements produced by predication which prevents
   loop vectorization.  */

static void
ifcvt_local_dce (basic_block bb)
{
  gimple *stmt;
  gimple *stmt1;
  gimple *phi;
  gimple_stmt_iterator gsi;
  auto_vec<gimple *> worklist;
  enum gimple_code code;
  use_operand_p use_p;
  imm_use_iterator imm_iter;

  worklist.create (64);
  /* Consider all phi as live statements.  */
  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    {
      phi = gsi_stmt (gsi);
      gimple_set_plf (phi, GF_PLF_2, true);
      worklist.safe_push (phi);
    }
  /* Consider load/store statements, CALL and COND as live.  */
  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    {
      stmt = gsi_stmt (gsi);
      if (gimple_store_p (stmt)
	  || gimple_assign_load_p (stmt)
	  || is_gimple_debug (stmt))
	{
	  gimple_set_plf (stmt, GF_PLF_2, true);
	  worklist.safe_push (stmt);
	  continue;
	}
      code = gimple_code (stmt);
      if (code == GIMPLE_COND || code == GIMPLE_CALL)
	{
	  gimple_set_plf (stmt, GF_PLF_2, true);
	  worklist.safe_push (stmt);
	  continue;
	}
      gimple_set_plf (stmt, GF_PLF_2, false);

      if (code == GIMPLE_ASSIGN)
	{
	  tree lhs = gimple_assign_lhs (stmt);
	  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
	    {
	      stmt1 = USE_STMT (use_p);
	      if (gimple_bb (stmt1) != bb)
		{
		  gimple_set_plf (stmt, GF_PLF_2, true);
		  worklist.safe_push (stmt);
		  break;
		}
	    }
	}
    }
  /* Propagate liveness through arguments of live stmt.  */
  while (worklist.length () > 0)
    {
      ssa_op_iter iter;
      use_operand_p use_p;
      tree use;

      stmt = worklist.pop ();
      FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
	{
	  use = USE_FROM_PTR (use_p);
	  if (TREE_CODE (use) != SSA_NAME)
	    continue;
	  stmt1 = SSA_NAME_DEF_STMT (use);
	  if (gimple_bb (stmt1) != bb
	      || gimple_plf (stmt1, GF_PLF_2))
	    continue;
	  gimple_set_plf (stmt1, GF_PLF_2, true);
	  worklist.safe_push (stmt1);
	}
    }
  /* Delete dead statements.  */
  gsi = gsi_start_bb (bb);
  while (!gsi_end_p (gsi))
    {
      stmt = gsi_stmt (gsi);
      if (gimple_plf (stmt, GF_PLF_2))
	{
	  gsi_next (&gsi);
	  continue;
	}
      if (dump_file && (dump_flags & TDF_DETAILS))
	{
	  fprintf (dump_file, "Delete dead stmt in bb#%d\n", bb->index);
	  print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
	}
      gsi_remove (&gsi, true);
      release_defs (stmt);
    }
}

/* If-convert LOOP when it is legal.  For the moment this pass has no
   profitability analysis.  Returns non-zero todo flags when something
   changed.  */

unsigned int
tree_if_conversion (struct loop *loop)
{
  unsigned int todo = 0;
  bool aggressive_if_conv;
  struct loop *rloop;

 again:
  rloop = NULL;
  ifc_bbs = NULL;
  any_pred_load_store = false;
  any_complicated_phi = false;

  /* Apply more aggressive if-conversion when loop or its outer loop were
     marked with simd pragma.  When that's the case, we try to if-convert
     loop containing PHIs with more than MAX_PHI_ARG_NUM arguments.  */
  aggressive_if_conv = loop->force_vectorize;
  if (!aggressive_if_conv)
    {
      struct loop *outer_loop = loop_outer (loop);
      if (outer_loop && outer_loop->force_vectorize)
	aggressive_if_conv = true;
    }

  if (!ifcvt_split_critical_edges (loop, aggressive_if_conv))
    goto cleanup;

  if (!if_convertible_loop_p (loop)
      || !dbg_cnt (if_conversion_tree))
    goto cleanup;

  if ((any_pred_load_store || any_complicated_phi)
      && ((!flag_tree_loop_vectorize && !loop->force_vectorize)
	  || loop->dont_vectorize))
    goto cleanup;

  /* Since we have no cost model, always version loops unless the user
     specified -ftree-loop-if-convert or unless versioning is required.
     Either version this loop, or if the pattern is right for outer-loop
     vectorization, version the outer loop.  In the latter case we will
     still if-convert the original inner loop.  */
  if (any_pred_load_store
      || any_complicated_phi
      || flag_tree_loop_if_convert != 1)
    {
      struct loop *vloop
	= (versionable_outer_loop_p (loop_outer (loop))
	   ? loop_outer (loop) : loop);
      struct loop *nloop = version_loop_for_if_conversion (vloop);
      if (nloop == NULL)
	goto cleanup;
      if (vloop != loop)
	{
	  /* If versionable_outer_loop_p decided to version the
	     outer loop, version also the inner loop of the non-vectorized
	     loop copy.  So we transform:
	      loop1
		loop2
	     into:
	      if (LOOP_VECTORIZED (1, 3))
		{
		  loop1
		    loop2
		}
	      else
		loop3 (copy of loop1)
		  if (LOOP_VECTORIZED (4, 5))
		    loop4 (copy of loop2)
		  else
		    loop5 (copy of loop4)  */
	  gcc_assert (nloop->inner && nloop->inner->next == NULL);
	  rloop = nloop->inner;
	}
    }

  /* Now all statements are if-convertible.  Combine all the basic
     blocks into one huge basic block doing the if-conversion
     on-the-fly.  */
  combine_blocks (loop);

  /* Delete dead predicate computations.  */
  ifcvt_local_dce (loop->header);

  todo |= TODO_cleanup_cfg;

 cleanup:
  if (ifc_bbs)
    {
      unsigned int i;

      for (i = 0; i < loop->num_nodes; i++)
	free_bb_predicate (ifc_bbs[i]);

      free (ifc_bbs);
      ifc_bbs = NULL;
    }
  if (rloop != NULL)
    {
      loop = rloop;
      goto again;
    }

  return todo;
}

/* Tree if-conversion pass management.  */

namespace {

const pass_data pass_data_if_conversion =
{
  GIMPLE_PASS, /* type */
  "ifcvt", /* name */
  OPTGROUP_NONE, /* optinfo_flags */
  TV_TREE_LOOP_IFCVT, /* tv_id */
  ( PROP_cfg | PROP_ssa ), /* properties_required */
  0, /* properties_provided */
  0, /* properties_destroyed */
  0, /* todo_flags_start */
  0, /* todo_flags_finish */
};

class pass_if_conversion : public gimple_opt_pass
{
public:
  pass_if_conversion (gcc::context *ctxt)
    : gimple_opt_pass (pass_data_if_conversion, ctxt)
  {}

  /* opt_pass methods: */
  virtual bool gate (function *);
  virtual unsigned int execute (function *);

}; // class pass_if_conversion

bool
pass_if_conversion::gate (function *fun)
{
  return (((flag_tree_loop_vectorize || fun->has_force_vectorize_loops)
	   && flag_tree_loop_if_convert != 0)
	  || flag_tree_loop_if_convert == 1);
}

unsigned int
pass_if_conversion::execute (function *fun)
{
  struct loop *loop;
  unsigned todo = 0;

  if (number_of_loops (fun) <= 1)
    return 0;

  FOR_EACH_LOOP (loop, 0)
    if (flag_tree_loop_if_convert == 1
	|| ((flag_tree_loop_vectorize || loop->force_vectorize)
	    && !loop->dont_vectorize))
      todo |= tree_if_conversion (loop);

  if (flag_checking)
    {
      basic_block bb;
      FOR_EACH_BB_FN (bb, fun)
	gcc_assert (!bb->aux);
    }

  return todo;
}

} // anon namespace

gimple_opt_pass *
make_pass_if_conversion (gcc::context *ctxt)
{
  return new pass_if_conversion (ctxt);
}