text: /* Vectorizer Specific Loop Manipulations
     Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2012
     Free Software Foundation, Inc.
     Contributed by Dorit Naishlos <dorit@il.ibm.com>
     and Ira Rosen <irar@il.ibm.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/>.  */
  
  #include "config.h"
  #include "system.h"
  #include "coretypes.h"
  #include "tm.h"
  #include "ggc.h"
  #include "tree.h"
  #include "basic-block.h"
  #include "tree-pretty-print.h"
  #include "gimple-pretty-print.h"
  #include "tree-flow.h"
  #include "tree-dump.h"
  #include "cfgloop.h"
  #include "cfglayout.h"
  #include "diagnostic-core.h"
  #include "tree-scalar-evolution.h"
  #include "tree-vectorizer.h"
  #include "langhooks.h"
  
  /*************************************************************************
    Simple Loop Peeling Utilities
  
    Utilities to support loop peeling for vectorization purposes.
   *************************************************************************/
  
  
  /* Renames the use *OP_P.  */
  
  static void
  rename_use_op (use_operand_p op_p)
  {
    tree new_name;
  
    if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
      return;
  
    new_name = get_current_def (USE_FROM_PTR (op_p));
  
    /* Something defined outside of the loop.  */
    if (!new_name)
      return;
  
    /* An ordinary ssa name defined in the loop.  */
  
    SET_USE (op_p, new_name);
  }
  
  
  /* Renames the variables in basic block BB.  */
  
  void
  rename_variables_in_bb (basic_block bb)
  {
    gimple_stmt_iterator gsi;
    gimple stmt;
    use_operand_p use_p;
    ssa_op_iter iter;
    edge e;
    edge_iterator ei;
    struct loop *loop = bb->loop_father;
  
    for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
      {
        stmt = gsi_stmt (gsi);
        FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
  	rename_use_op (use_p);
      }
  
    FOR_EACH_EDGE (e, ei, bb->succs)
      {
        if (!flow_bb_inside_loop_p (loop, e->dest))
  	continue;
        for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
          rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (gsi_stmt (gsi), e));
      }
  }
  
  
  /* Renames variables in new generated LOOP.  */
  
  void
  rename_variables_in_loop (struct loop *loop)
  {
    unsigned i;
    basic_block *bbs;
  
    bbs = get_loop_body (loop);
  
    for (i = 0; i < loop->num_nodes; i++)
      rename_variables_in_bb (bbs[i]);
  
    free (bbs);
  }
  
  typedef struct
  {
    tree from, to;
    basic_block bb;
  } adjust_info;
  
  DEF_VEC_O(adjust_info);
  DEF_VEC_ALLOC_O_STACK(adjust_info);
  #define VEC_adjust_info_stack_alloc(alloc) VEC_stack_alloc (adjust_info, alloc)
  
  /* A stack of values to be adjusted in debug stmts.  We have to
     process them LIFO, so that the closest substitution applies.  If we
     processed them FIFO, without the stack, we might substitute uses
     with a PHI DEF that would soon become non-dominant, and when we got
     to the suitable one, it wouldn't have anything to substitute any
     more.  */
  static VEC(adjust_info, stack) *adjust_vec;
  
  /* Adjust any debug stmts that referenced AI->from values to use the
     loop-closed AI->to, if the references are dominated by AI->bb and
     not by the definition of AI->from.  */
  
  static void
  adjust_debug_stmts_now (adjust_info *ai)
  {
    basic_block bbphi = ai->bb;
    tree orig_def = ai->from;
    tree new_def = ai->to;
    imm_use_iterator imm_iter;
    gimple stmt;
    basic_block bbdef = gimple_bb (SSA_NAME_DEF_STMT (orig_def));
  
    gcc_assert (dom_info_available_p (CDI_DOMINATORS));
  
    /* Adjust any debug stmts that held onto non-loop-closed
       references.  */
    FOR_EACH_IMM_USE_STMT (stmt, imm_iter, orig_def)
      {
        use_operand_p use_p;
        basic_block bbuse;
  
        if (!is_gimple_debug (stmt))
  	continue;
  
        gcc_assert (gimple_debug_bind_p (stmt));
  
        bbuse = gimple_bb (stmt);
  
        if ((bbuse == bbphi
  	   || dominated_by_p (CDI_DOMINATORS, bbuse, bbphi))
  	  && !(bbuse == bbdef
  	       || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef)))
  	{
  	  if (new_def)
  	    FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
  	      SET_USE (use_p, new_def);
  	  else
  	    {
  	      gimple_debug_bind_reset_value (stmt);
  	      update_stmt (stmt);
  	    }
  	}
      }
  }
  
  /* Adjust debug stmts as scheduled before.  */
  
  static void
  adjust_vec_debug_stmts (void)
  {
    if (!MAY_HAVE_DEBUG_STMTS)
      return;
  
    gcc_assert (adjust_vec);
  
    while (!VEC_empty (adjust_info, adjust_vec))
      {
        adjust_debug_stmts_now (VEC_last (adjust_info, adjust_vec));
        VEC_pop (adjust_info, adjust_vec);
      }
  
    VEC_free (adjust_info, stack, adjust_vec);
  }
  
  /* Adjust any debug stmts that referenced FROM values to use the
     loop-closed TO, if the references are dominated by BB and not by
     the definition of FROM.  If adjust_vec is non-NULL, adjustments
     will be postponed until adjust_vec_debug_stmts is called.  */
  
  static void
  adjust_debug_stmts (tree from, tree to, basic_block bb)
  {
    adjust_info ai;
  
    if (MAY_HAVE_DEBUG_STMTS && TREE_CODE (from) == SSA_NAME
        && SSA_NAME_VAR (from) != gimple_vop (cfun))
      {
        ai.from = from;
        ai.to = to;
        ai.bb = bb;
  
        if (adjust_vec)
  	VEC_safe_push (adjust_info, stack, adjust_vec, &ai);
        else
  	adjust_debug_stmts_now (&ai);
      }
  }
  
  /* Change E's phi arg in UPDATE_PHI to NEW_DEF, and record information
     to adjust any debug stmts that referenced the old phi arg,
     presumably non-loop-closed references left over from other
     transformations.  */
  
  static void
  adjust_phi_and_debug_stmts (gimple update_phi, edge e, tree new_def)
  {
    tree orig_def = PHI_ARG_DEF_FROM_EDGE (update_phi, e);
  
    SET_PHI_ARG_DEF (update_phi, e->dest_idx, new_def);
  
    if (MAY_HAVE_DEBUG_STMTS)
      adjust_debug_stmts (orig_def, PHI_RESULT (update_phi),
  			gimple_bb (update_phi));
  }
  
  
  /* Update the PHI nodes of NEW_LOOP.
  
     NEW_LOOP is a duplicate of ORIG_LOOP.
     AFTER indicates whether NEW_LOOP executes before or after ORIG_LOOP:
     AFTER is true if NEW_LOOP executes after ORIG_LOOP, and false if it
     executes before it.  */
  
  static void
  slpeel_update_phis_for_duplicate_loop (struct loop *orig_loop,
  				       struct loop *new_loop, bool after)
  {
    tree new_ssa_name;
    gimple phi_new, phi_orig;
    tree def;
    edge orig_loop_latch = loop_latch_edge (orig_loop);
    edge orig_entry_e = loop_preheader_edge (orig_loop);
    edge new_loop_exit_e = single_exit (new_loop);
    edge new_loop_entry_e = loop_preheader_edge (new_loop);
    edge entry_arg_e = (after ? orig_loop_latch : orig_entry_e);
    gimple_stmt_iterator gsi_new, gsi_orig;
  
    /*
       step 1. For each loop-header-phi:
               Add the first phi argument for the phi in NEW_LOOP
              (the one associated with the entry of NEW_LOOP)
  
       step 2. For each loop-header-phi:
               Add the second phi argument for the phi in NEW_LOOP
              (the one associated with the latch of NEW_LOOP)
  
       step 3. Update the phis in the successor block of NEW_LOOP.
  
          case 1: NEW_LOOP was placed before ORIG_LOOP:
                  The successor block of NEW_LOOP is the header of ORIG_LOOP.
                  Updating the phis in the successor block can therefore be done
                  along with the scanning of the loop header phis, because the
                  header blocks of ORIG_LOOP and NEW_LOOP have exactly the same
                  phi nodes, organized in the same order.
  
          case 2: NEW_LOOP was placed after ORIG_LOOP:
                  The successor block of NEW_LOOP is the original exit block of
                  ORIG_LOOP - the phis to be updated are the loop-closed-ssa phis.
                  We postpone updating these phis to a later stage (when
                  loop guards are added).
     */
  
  
    /* Scan the phis in the headers of the old and new loops
       (they are organized in exactly the same order).  */
  
    for (gsi_new = gsi_start_phis (new_loop->header),
         gsi_orig = gsi_start_phis (orig_loop->header);
         !gsi_end_p (gsi_new) && !gsi_end_p (gsi_orig);
         gsi_next (&gsi_new), gsi_next (&gsi_orig))
      {
        source_location locus;
        phi_new = gsi_stmt (gsi_new);
        phi_orig = gsi_stmt (gsi_orig);
  
        /* step 1.  */
        def = PHI_ARG_DEF_FROM_EDGE (phi_orig, entry_arg_e);
        locus = gimple_phi_arg_location_from_edge (phi_orig, entry_arg_e);
        add_phi_arg (phi_new, def, new_loop_entry_e, locus);
  
        /* step 2.  */
        def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
        locus = gimple_phi_arg_location_from_edge (phi_orig, orig_loop_latch);
        if (TREE_CODE (def) != SSA_NAME)
          continue;
  
        new_ssa_name = get_current_def (def);
        if (!new_ssa_name)
  	{
  	  /* This only happens if there are no definitions
  	     inside the loop. use the phi_result in this case.  */
  	  new_ssa_name = PHI_RESULT (phi_new);
  	}
  
        /* An ordinary ssa name defined in the loop.  */
        add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop), locus);
  
        /* Drop any debug references outside the loop, if they would
  	 become ill-formed SSA.  */
        adjust_debug_stmts (def, NULL, single_exit (orig_loop)->dest);
  
        /* step 3 (case 1).  */
        if (!after)
          {
            gcc_assert (new_loop_exit_e == orig_entry_e);
  	  adjust_phi_and_debug_stmts (phi_orig, new_loop_exit_e, new_ssa_name);
          }
      }
  }
  
  
  /* Update PHI nodes for a guard of the LOOP.
  
     Input:
     - LOOP, GUARD_EDGE: LOOP is a loop for which we added guard code that
          controls whether LOOP is to be executed.  GUARD_EDGE is the edge that
          originates from the guard-bb, skips LOOP and reaches the (unique) exit
          bb of LOOP.  This loop-exit-bb is an empty bb with one successor.
          We denote this bb NEW_MERGE_BB because before the guard code was added
          it had a single predecessor (the LOOP header), and now it became a merge
          point of two paths - the path that ends with the LOOP exit-edge, and
          the path that ends with GUARD_EDGE.
     - NEW_EXIT_BB: New basic block that is added by this function between LOOP
          and NEW_MERGE_BB. It is used to place loop-closed-ssa-form exit-phis.
  
     ===> The CFG before the guard-code was added:
          LOOP_header_bb:
            loop_body
            if (exit_loop) goto update_bb
            else           goto LOOP_header_bb
          update_bb:
  
     ==> The CFG after the guard-code was added:
          guard_bb:
            if (LOOP_guard_condition) goto new_merge_bb
            else                      goto LOOP_header_bb
          LOOP_header_bb:
            loop_body
            if (exit_loop_condition) goto new_merge_bb
            else                     goto LOOP_header_bb
          new_merge_bb:
            goto update_bb
          update_bb:
  
     ==> The CFG after this function:
          guard_bb:
            if (LOOP_guard_condition) goto new_merge_bb
            else                      goto LOOP_header_bb
          LOOP_header_bb:
            loop_body
            if (exit_loop_condition) goto new_exit_bb
            else                     goto LOOP_header_bb
          new_exit_bb:
          new_merge_bb:
            goto update_bb
          update_bb:
  
     This function:
     1. creates and updates the relevant phi nodes to account for the new
        incoming edge (GUARD_EDGE) into NEW_MERGE_BB. This involves:
        1.1. Create phi nodes at NEW_MERGE_BB.
        1.2. Update the phi nodes at the successor of NEW_MERGE_BB (denoted
             UPDATE_BB).  UPDATE_BB was the exit-bb of LOOP before NEW_MERGE_BB
     2. preserves loop-closed-ssa-form by creating the required phi nodes
        at the exit of LOOP (i.e, in NEW_EXIT_BB).
  
     There are two flavors to this function:
  
     slpeel_update_phi_nodes_for_guard1:
       Here the guard controls whether we enter or skip LOOP, where LOOP is a
       prolog_loop (loop1 below), and the new phis created in NEW_MERGE_BB are
       for variables that have phis in the loop header.
  
     slpeel_update_phi_nodes_for_guard2:
       Here the guard controls whether we enter or skip LOOP, where LOOP is an
       epilog_loop (loop2 below), and the new phis created in NEW_MERGE_BB are
       for variables that have phis in the loop exit.
  
     I.E., the overall structure is:
  
          loop1_preheader_bb:
                  guard1 (goto loop1/merge1_bb)
          loop1
          loop1_exit_bb:
                  guard2 (goto merge1_bb/merge2_bb)
          merge1_bb
          loop2
          loop2_exit_bb
          merge2_bb
          next_bb
  
     slpeel_update_phi_nodes_for_guard1 takes care of creating phis in
     loop1_exit_bb and merge1_bb. These are entry phis (phis for the vars
     that have phis in loop1->header).
  
     slpeel_update_phi_nodes_for_guard2 takes care of creating phis in
     loop2_exit_bb and merge2_bb. These are exit phis (phis for the vars
     that have phis in next_bb). It also adds some of these phis to
     loop1_exit_bb.
  
     slpeel_update_phi_nodes_for_guard1 is always called before
     slpeel_update_phi_nodes_for_guard2. They are both needed in order
     to create correct data-flow and loop-closed-ssa-form.
  
     Generally slpeel_update_phi_nodes_for_guard1 creates phis for variables
     that change between iterations of a loop (and therefore have a phi-node
     at the loop entry), whereas slpeel_update_phi_nodes_for_guard2 creates
     phis for variables that are used out of the loop (and therefore have
     loop-closed exit phis). Some variables may be both updated between
     iterations and used after the loop. This is why in loop1_exit_bb we
     may need both entry_phis (created by slpeel_update_phi_nodes_for_guard1)
     and exit phis (created by slpeel_update_phi_nodes_for_guard2).
  
     - IS_NEW_LOOP: if IS_NEW_LOOP is true, then LOOP is a newly created copy of
       an original loop. i.e., we have:
  
             orig_loop
             guard_bb (goto LOOP/new_merge)
             new_loop <-- LOOP
             new_exit
             new_merge
             next_bb
  
       If IS_NEW_LOOP is false, then LOOP is an original loop, in which case we
       have:
  
             new_loop
             guard_bb (goto LOOP/new_merge)
             orig_loop <-- LOOP
             new_exit
             new_merge
             next_bb
  
       The SSA names defined in the original loop have a current
       reaching definition that that records the corresponding new
       ssa-name used in the new duplicated loop copy.
    */
  
  /* Function slpeel_update_phi_nodes_for_guard1
  
     Input:
     - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
     - DEFS - a bitmap of ssa names to mark new names for which we recorded
              information.
  
     In the context of the overall structure, we have:
  
          loop1_preheader_bb:
                  guard1 (goto loop1/merge1_bb)
  LOOP->  loop1
          loop1_exit_bb:
                  guard2 (goto merge1_bb/merge2_bb)
          merge1_bb
          loop2
          loop2_exit_bb
          merge2_bb
          next_bb
  
     For each name updated between loop iterations (i.e - for each name that has
     an entry (loop-header) phi in LOOP) we create a new phi in:
     1. merge1_bb (to account for the edge from guard1)
     2. loop1_exit_bb (an exit-phi to keep LOOP in loop-closed form)
  */
  
  static void
  slpeel_update_phi_nodes_for_guard1 (edge guard_edge, struct loop *loop,
                                      bool is_new_loop, basic_block *new_exit_bb,
                                      bitmap *defs)
  {
    gimple orig_phi, new_phi;
    gimple update_phi, update_phi2;
    tree guard_arg, loop_arg;
    basic_block new_merge_bb = guard_edge->dest;
    edge e = EDGE_SUCC (new_merge_bb, 0);
    basic_block update_bb = e->dest;
    basic_block orig_bb = loop->header;
    edge new_exit_e;
    tree current_new_name;
    gimple_stmt_iterator gsi_orig, gsi_update;
  
    /* Create new bb between loop and new_merge_bb.  */
    *new_exit_bb = split_edge (single_exit (loop));
  
    new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
  
    for (gsi_orig = gsi_start_phis (orig_bb),
         gsi_update = gsi_start_phis (update_bb);
         !gsi_end_p (gsi_orig) && !gsi_end_p (gsi_update);
         gsi_next (&gsi_orig), gsi_next (&gsi_update))
      {
        source_location loop_locus, guard_locus;
        orig_phi = gsi_stmt (gsi_orig);
        update_phi = gsi_stmt (gsi_update);
  
        /** 1. Handle new-merge-point phis  **/
  
        /* 1.1. Generate new phi node in NEW_MERGE_BB:  */
        new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
                                   new_merge_bb);
  
        /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
              of LOOP. Set the two phi args in NEW_PHI for these edges:  */
        loop_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, EDGE_SUCC (loop->latch, 0));
        loop_locus = gimple_phi_arg_location_from_edge (orig_phi,
  						      EDGE_SUCC (loop->latch,
  								 0));
        guard_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, loop_preheader_edge (loop));
        guard_locus
  	= gimple_phi_arg_location_from_edge (orig_phi,
  					     loop_preheader_edge (loop));
  
        add_phi_arg (new_phi, loop_arg, new_exit_e, loop_locus);
        add_phi_arg (new_phi, guard_arg, guard_edge, guard_locus);
  
        /* 1.3. Update phi in successor block.  */
        gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == loop_arg
                    || PHI_ARG_DEF_FROM_EDGE (update_phi, e) == guard_arg);
        adjust_phi_and_debug_stmts (update_phi, e, PHI_RESULT (new_phi));
        update_phi2 = new_phi;
  
  
        /** 2. Handle loop-closed-ssa-form phis  **/
  
        if (!is_gimple_reg (PHI_RESULT (orig_phi)))
  	continue;
  
        /* 2.1. Generate new phi node in NEW_EXIT_BB:  */
        new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
                                   *new_exit_bb);
  
        /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop.  */
        add_phi_arg (new_phi, loop_arg, single_exit (loop), loop_locus);
  
        /* 2.3. Update phi in successor of NEW_EXIT_BB:  */
        gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
        adjust_phi_and_debug_stmts (update_phi2, new_exit_e,
  				  PHI_RESULT (new_phi));
  
        /* 2.4. Record the newly created name with set_current_def.
           We want to find a name such that
                  name = get_current_def (orig_loop_name)
           and to set its current definition as follows:
                  set_current_def (name, new_phi_name)
  
           If LOOP is a new loop then loop_arg is already the name we're
           looking for. If LOOP is the original loop, then loop_arg is
           the orig_loop_name and the relevant name is recorded in its
           current reaching definition.  */
        if (is_new_loop)
          current_new_name = loop_arg;
        else
          {
            current_new_name = get_current_def (loop_arg);
  	  /* current_def is not available only if the variable does not
  	     change inside the loop, in which case we also don't care
  	     about recording a current_def for it because we won't be
  	     trying to create loop-exit-phis for it.  */
  	  if (!current_new_name)
  	    continue;
          }
        gcc_assert (get_current_def (current_new_name) == NULL_TREE);
  
        set_current_def (current_new_name, PHI_RESULT (new_phi));
        bitmap_set_bit (*defs, SSA_NAME_VERSION (current_new_name));
      }
  }
  
  
  /* Function slpeel_update_phi_nodes_for_guard2
  
     Input:
     - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
  
     In the context of the overall structure, we have:
  
          loop1_preheader_bb:
                  guard1 (goto loop1/merge1_bb)
          loop1
          loop1_exit_bb:
                  guard2 (goto merge1_bb/merge2_bb)
          merge1_bb
  LOOP->  loop2
          loop2_exit_bb
          merge2_bb
          next_bb
  
     For each name used out side the loop (i.e - for each name that has an exit
     phi in next_bb) we create a new phi in:
     1. merge2_bb (to account for the edge from guard_bb)
     2. loop2_exit_bb (an exit-phi to keep LOOP in loop-closed form)
     3. guard2 bb (an exit phi to keep the preceding loop in loop-closed form),
        if needed (if it wasn't handled by slpeel_update_phis_nodes_for_phi1).
  */
  
  static void
  slpeel_update_phi_nodes_for_guard2 (edge guard_edge, struct loop *loop,
                                      bool is_new_loop, basic_block *new_exit_bb)
  {
    gimple orig_phi, new_phi;
    gimple update_phi, update_phi2;
    tree guard_arg, loop_arg;
    basic_block new_merge_bb = guard_edge->dest;
    edge e = EDGE_SUCC (new_merge_bb, 0);
    basic_block update_bb = e->dest;
    edge new_exit_e;
    tree orig_def, orig_def_new_name;
    tree new_name, new_name2;
    tree arg;
    gimple_stmt_iterator gsi;
  
    /* Create new bb between loop and new_merge_bb.  */
    *new_exit_bb = split_edge (single_exit (loop));
  
    new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
  
    for (gsi = gsi_start_phis (update_bb); !gsi_end_p (gsi); gsi_next (&gsi))
      {
        update_phi = gsi_stmt (gsi);
        orig_phi = update_phi;
        orig_def = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
        /* This loop-closed-phi actually doesn't represent a use
           out of the loop - the phi arg is a constant.  */
        if (TREE_CODE (orig_def) != SSA_NAME)
          continue;
        orig_def_new_name = get_current_def (orig_def);
        arg = NULL_TREE;
  
        /** 1. Handle new-merge-point phis  **/
  
        /* 1.1. Generate new phi node in NEW_MERGE_BB:  */
        new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
                                   new_merge_bb);
  
        /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
              of LOOP. Set the two PHI args in NEW_PHI for these edges:  */
        new_name = orig_def;
        new_name2 = NULL_TREE;
        if (orig_def_new_name)
          {
            new_name = orig_def_new_name;
  	  /* Some variables have both loop-entry-phis and loop-exit-phis.
  	     Such variables were given yet newer names by phis placed in
  	     guard_bb by slpeel_update_phi_nodes_for_guard1. I.e:
  	     new_name2 = get_current_def (get_current_def (orig_name)).  */
            new_name2 = get_current_def (new_name);
          }
  
        if (is_new_loop)
          {
            guard_arg = orig_def;
            loop_arg = new_name;
          }
        else
          {
            guard_arg = new_name;
            loop_arg = orig_def;
          }
        if (new_name2)
          guard_arg = new_name2;
  
        add_phi_arg (new_phi, loop_arg, new_exit_e, UNKNOWN_LOCATION);
        add_phi_arg (new_phi, guard_arg, guard_edge, UNKNOWN_LOCATION);
  
        /* 1.3. Update phi in successor block.  */
        gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == orig_def);
        adjust_phi_and_debug_stmts (update_phi, e, PHI_RESULT (new_phi));
        update_phi2 = new_phi;
  
  
        /** 2. Handle loop-closed-ssa-form phis  **/
  
        /* 2.1. Generate new phi node in NEW_EXIT_BB:  */
        new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
                                   *new_exit_bb);
  
        /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop.  */
        add_phi_arg (new_phi, loop_arg, single_exit (loop), UNKNOWN_LOCATION);
  
        /* 2.3. Update phi in successor of NEW_EXIT_BB:  */
        gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
        adjust_phi_and_debug_stmts (update_phi2, new_exit_e,
  				  PHI_RESULT (new_phi));
  
  
        /** 3. Handle loop-closed-ssa-form phis for first loop  **/
  
        /* 3.1. Find the relevant names that need an exit-phi in
  	 GUARD_BB, i.e. names for which
  	 slpeel_update_phi_nodes_for_guard1 had not already created a
  	 phi node. This is the case for names that are used outside
  	 the loop (and therefore need an exit phi) but are not updated
  	 across loop iterations (and therefore don't have a
  	 loop-header-phi).
  
  	 slpeel_update_phi_nodes_for_guard1 is responsible for
  	 creating loop-exit phis in GUARD_BB for names that have a
  	 loop-header-phi.  When such a phi is created we also record
  	 the new name in its current definition.  If this new name
  	 exists, then guard_arg was set to this new name (see 1.2
  	 above).  Therefore, if guard_arg is not this new name, this
  	 is an indication that an exit-phi in GUARD_BB was not yet
  	 created, so we take care of it here.  */
        if (guard_arg == new_name2)
  	continue;
        arg = guard_arg;
  
        /* 3.2. Generate new phi node in GUARD_BB:  */
        new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
                                   guard_edge->src);
  
        /* 3.3. GUARD_BB has one incoming edge:  */
        gcc_assert (EDGE_COUNT (guard_edge->src->preds) == 1);
        add_phi_arg (new_phi, arg, EDGE_PRED (guard_edge->src, 0),
  		   UNKNOWN_LOCATION);
  
        /* 3.4. Update phi in successor of GUARD_BB:  */
        gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, guard_edge)
                                                                  == guard_arg);
        adjust_phi_and_debug_stmts (update_phi2, guard_edge,
  				  PHI_RESULT (new_phi));
      }
  }
  
  
  /* Make the LOOP iterate NITERS times. This is done by adding a new IV
     that starts at zero, increases by one and its limit is NITERS.
  
     Assumption: the exit-condition of LOOP is the last stmt in the loop.  */
  
  void
  slpeel_make_loop_iterate_ntimes (struct loop *loop, tree niters)
  {
    tree indx_before_incr, indx_after_incr;
    gimple cond_stmt;
    gimple orig_cond;
    edge exit_edge = single_exit (loop);
    gimple_stmt_iterator loop_cond_gsi;
    gimple_stmt_iterator incr_gsi;
    bool insert_after;
    tree init = build_int_cst (TREE_TYPE (niters), 0);
    tree step = build_int_cst (TREE_TYPE (niters), 1);
    LOC loop_loc;
    enum tree_code code;
  
    orig_cond = get_loop_exit_condition (loop);
    gcc_assert (orig_cond);
    loop_cond_gsi = gsi_for_stmt (orig_cond);
  
    standard_iv_increment_position (loop, &incr_gsi, &insert_after);
    create_iv (init, step, NULL_TREE, loop,
               &incr_gsi, insert_after, &indx_before_incr, &indx_after_incr);
  
    indx_after_incr = force_gimple_operand_gsi (&loop_cond_gsi, indx_after_incr,
  					      true, NULL_TREE, true,
  					      GSI_SAME_STMT);
    niters = force_gimple_operand_gsi (&loop_cond_gsi, niters, true, NULL_TREE,
  				     true, GSI_SAME_STMT);
  
    code = (exit_edge->flags & EDGE_TRUE_VALUE) ? GE_EXPR : LT_EXPR;
    cond_stmt = gimple_build_cond (code, indx_after_incr, niters, NULL_TREE,
  				 NULL_TREE);
  
    gsi_insert_before (&loop_cond_gsi, cond_stmt, GSI_SAME_STMT);
  
    /* Remove old loop exit test:  */
    gsi_remove (&loop_cond_gsi, true);
  
    loop_loc = find_loop_location (loop);
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
        if (loop_loc != UNKNOWN_LOC)
          fprintf (dump_file, "\nloop at %s:%d: ",
                   LOC_FILE (loop_loc), LOC_LINE (loop_loc));
        print_gimple_stmt (dump_file, cond_stmt, 0, TDF_SLIM);
      }
  
    loop->nb_iterations = niters;
  }
  
  
  /* Given LOOP this function generates a new copy of it and puts it
     on E which is either the entry or exit of LOOP.  */
  
  struct loop *
  slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, edge e)
  {
    struct loop *new_loop;
    basic_block *new_bbs, *bbs;
    bool at_exit;
    bool was_imm_dom;
    basic_block exit_dest;
    gimple phi;
    tree phi_arg;
    edge exit, new_exit;
    gimple_stmt_iterator gsi;
  
    at_exit = (e == single_exit (loop));
    if (!at_exit && e != loop_preheader_edge (loop))
      return NULL;
  
    bbs = get_loop_body (loop);
  
    /* Check whether duplication is possible.  */
    if (!can_copy_bbs_p (bbs, loop->num_nodes))
      {
        free (bbs);
        return NULL;
      }
  
    /* Generate new loop structure.  */
    new_loop = duplicate_loop (loop, loop_outer (loop));
    if (!new_loop)
      {
        free (bbs);
        return NULL;
      }
  
    exit_dest = single_exit (loop)->dest;
    was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS,
  					  exit_dest) == loop->header ?
  		 true : false);
  
    new_bbs = XNEWVEC (basic_block, loop->num_nodes);
  
    exit = single_exit (loop);
    copy_bbs (bbs, loop->num_nodes, new_bbs,
  	    &exit, 1, &new_exit, NULL,
  	    e->src);
  
    /* Duplicating phi args at exit bbs as coming
       also from exit of duplicated loop.  */
    for (gsi = gsi_start_phis (exit_dest); !gsi_end_p (gsi); gsi_next (&gsi))
      {
        phi = gsi_stmt (gsi);
        phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, single_exit (loop));
        if (phi_arg)
  	{
  	  edge new_loop_exit_edge;
  	  source_location locus;
  
  	  locus = gimple_phi_arg_location_from_edge (phi, single_exit (loop));
  	  if (EDGE_SUCC (new_loop->header, 0)->dest == new_loop->latch)
  	    new_loop_exit_edge = EDGE_SUCC (new_loop->header, 1);
  	  else
  	    new_loop_exit_edge = EDGE_SUCC (new_loop->header, 0);
  
  	  add_phi_arg (phi, phi_arg, new_loop_exit_edge, locus);
  	}
      }
  
    if (at_exit) /* Add the loop copy at exit.  */
      {
        redirect_edge_and_branch_force (e, new_loop->header);
        PENDING_STMT (e) = NULL;
        set_immediate_dominator (CDI_DOMINATORS, new_loop->header, e->src);
        if (was_imm_dom)
  	set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_loop->header);
      }
    else /* Add the copy at entry.  */
      {
        edge new_exit_e;
        edge entry_e = loop_preheader_edge (loop);
        basic_block preheader = entry_e->src;
  
        if (!flow_bb_inside_loop_p (new_loop,
  				  EDGE_SUCC (new_loop->header, 0)->dest))
          new_exit_e = EDGE_SUCC (new_loop->header, 0);
        else
  	new_exit_e = EDGE_SUCC (new_loop->header, 1);
  
        redirect_edge_and_branch_force (new_exit_e, loop->header);
        PENDING_STMT (new_exit_e) = NULL;
        set_immediate_dominator (CDI_DOMINATORS, loop->header,
  			       new_exit_e->src);
  
        /* We have to add phi args to the loop->header here as coming
  	 from new_exit_e edge.  */
        for (gsi = gsi_start_phis (loop->header);
             !gsi_end_p (gsi);
             gsi_next (&gsi))
  	{
  	  phi = gsi_stmt (gsi);
  	  phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, entry_e);
  	  if (phi_arg)
  	    add_phi_arg (phi, phi_arg, new_exit_e,
  			 gimple_phi_arg_location_from_edge (phi, entry_e));
  	}
  
        redirect_edge_and_branch_force (entry_e, new_loop->header);
        PENDING_STMT (entry_e) = NULL;
        set_immediate_dominator (CDI_DOMINATORS, new_loop->header, preheader);
      }
  
    free (new_bbs);
    free (bbs);
  
    return new_loop;
  }
  
  
  /* Given the condition statement COND, put it as the last statement
     of GUARD_BB; EXIT_BB is the basic block to skip the loop;
     Assumes that this is the single exit of the guarded loop.
     Returns the skip edge, inserts new stmts on the COND_EXPR_STMT_LIST.  */
  
  static edge
  slpeel_add_loop_guard (basic_block guard_bb, tree cond,
  		       gimple_seq cond_expr_stmt_list,
  		       basic_block exit_bb, basic_block dom_bb)
  {
    gimple_stmt_iterator gsi;
    edge new_e, enter_e;
    gimple cond_stmt;
    gimple_seq gimplify_stmt_list = NULL;
  
    enter_e = EDGE_SUCC (guard_bb, 0);
    enter_e->flags &= ~EDGE_FALLTHRU;
    enter_e->flags |= EDGE_FALSE_VALUE;
    gsi = gsi_last_bb (guard_bb);
  
    cond = force_gimple_operand (cond, &gimplify_stmt_list, true, NULL_TREE);
    if (gimplify_stmt_list)
      gimple_seq_add_seq (&cond_expr_stmt_list, gimplify_stmt_list);
    cond_stmt = gimple_build_cond (NE_EXPR,
  				 cond, build_int_cst (TREE_TYPE (cond), 0),
  				 NULL_TREE, NULL_TREE);
    if (cond_expr_stmt_list)
      gsi_insert_seq_after (&gsi, cond_expr_stmt_list, GSI_NEW_STMT);
  
    gsi = gsi_last_bb (guard_bb);
    gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
  
    /* Add new edge to connect guard block to the merge/loop-exit block.  */
    new_e = make_edge (guard_bb, exit_bb, EDGE_TRUE_VALUE);
    set_immediate_dominator (CDI_DOMINATORS, exit_bb, dom_bb);
    return new_e;
  }
  
  
  /* This function verifies that the following restrictions apply to LOOP:
     (1) it is innermost
     (2) it consists of exactly 2 basic blocks - header, and an empty latch.
     (3) it is single entry, single exit
     (4) its exit condition is the last stmt in the header
     (5) E is the entry/exit edge of LOOP.
   */
  
  bool
  slpeel_can_duplicate_loop_p (const struct loop *loop, const_edge e)
  {
    edge exit_e = single_exit (loop);
    edge entry_e = loop_preheader_edge (loop);
    gimple orig_cond = get_loop_exit_condition (loop);
    gimple_stmt_iterator loop_exit_gsi = gsi_last_bb (exit_e->src);
  
    if (need_ssa_update_p (cfun))
      return false;
  
    if (loop->inner
        /* All loops have an outer scope; the only case loop->outer is NULL is for
           the function itself.  */
        || !loop_outer (loop)
        || loop->num_nodes != 2
        || !empty_block_p (loop->latch)
        || !single_exit (loop)
        /* Verify that new loop exit condition can be trivially modified.  */
        || (!orig_cond || orig_cond != gsi_stmt (loop_exit_gsi))
        || (e != exit_e && e != entry_e))
      return false;
  
    return true;
  }
  
  #ifdef ENABLE_CHECKING
  static void
  slpeel_verify_cfg_after_peeling (struct loop *first_loop,
                                   struct loop *second_loop)
  {
    basic_block loop1_exit_bb = single_exit (first_loop)->dest;
    basic_block loop2_entry_bb = loop_preheader_edge (second_loop)->src;
    basic_block loop1_entry_bb = loop_preheader_edge (first_loop)->src;
  
    /* A guard that controls whether the second_loop is to be executed or skipped
       is placed in first_loop->exit.  first_loop->exit therefore has two
       successors - one is the preheader of second_loop, and the other is a bb
       after second_loop.
     */
    gcc_assert (EDGE_COUNT (loop1_exit_bb->succs) == 2);
  
    /* 1. Verify that one of the successors of first_loop->exit is the preheader
          of second_loop.  */
  
    /* The preheader of new_loop is expected to have two predecessors:
       first_loop->exit and the block that precedes first_loop.  */
  
    gcc_assert (EDGE_COUNT (loop2_entry_bb->preds) == 2
                && ((EDGE_PRED (loop2_entry_bb, 0)->src == loop1_exit_bb
                     && EDGE_PRED (loop2_entry_bb, 1)->src == loop1_entry_bb)
                 || (EDGE_PRED (loop2_entry_bb, 1)->src ==  loop1_exit_bb
                     && EDGE_PRED (loop2_entry_bb, 0)->src == loop1_entry_bb)));
  
    /* Verify that the other successor of first_loop->exit is after the
       second_loop.  */
    /* TODO */
  }
  #endif
  
  /* If the run time cost model check determines that vectorization is
     not profitable and hence scalar loop should be generated then set
     FIRST_NITERS to prologue peeled iterations. This will allow all the
     iterations to be executed in the prologue peeled scalar loop.  */
  
  static void
  set_prologue_iterations (basic_block bb_before_first_loop,
  			 tree *first_niters,
  			 struct loop *loop,
  			 unsigned int th)
  {
    edge e;
    basic_block cond_bb, then_bb;
    tree var, prologue_after_cost_adjust_name;
    gimple_stmt_iterator gsi;
    gimple newphi;
    edge e_true, e_false, e_fallthru;
    gimple cond_stmt;
    gimple_seq gimplify_stmt_list = NULL, stmts = NULL;
    tree cost_pre_condition = NULL_TREE;
    tree scalar_loop_iters =
      unshare_expr (LOOP_VINFO_NITERS_UNCHANGED (loop_vec_info_for_loop (loop)));
  
    e = single_pred_edge (bb_before_first_loop);
    cond_bb = split_edge(e);
  
    e = single_pred_edge (bb_before_first_loop);
    then_bb = split_edge(e);
    set_immediate_dominator (CDI_DOMINATORS, then_bb, cond_bb);
  
    e_false = make_single_succ_edge (cond_bb, bb_before_first_loop,
  				   EDGE_FALSE_VALUE);
    set_immediate_dominator (CDI_DOMINATORS, bb_before_first_loop, cond_bb);
  
    e_true = EDGE_PRED (then_bb, 0);
    e_true->flags &= ~EDGE_FALLTHRU;
    e_true->flags |= EDGE_TRUE_VALUE;
  
    e_fallthru = EDGE_SUCC (then_bb, 0);
  
    cost_pre_condition =
      fold_build2 (LE_EXPR, boolean_type_node, scalar_loop_iters,
  	         build_int_cst (TREE_TYPE (scalar_loop_iters), th));
    cost_pre_condition =
      force_gimple_operand (cost_pre_condition, &gimplify_stmt_list,
  			  true, NULL_TREE);
    cond_stmt = gimple_build_cond (NE_EXPR, cost_pre_condition,
  				 build_int_cst (TREE_TYPE (cost_pre_condition),
  						0), NULL_TREE, NULL_TREE);
  
    gsi = gsi_last_bb (cond_bb);
    if (gimplify_stmt_list)
      gsi_insert_seq_after (&gsi, gimplify_stmt_list, GSI_NEW_STMT);
  
    gsi = gsi_last_bb (cond_bb);
    gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
  
    var = create_tmp_var (TREE_TYPE (scalar_loop_iters),
  			"prologue_after_cost_adjust");
    add_referenced_var (var);
    prologue_after_cost_adjust_name =
      force_gimple_operand (scalar_loop_iters, &stmts, false, var);
  
    gsi = gsi_last_bb (then_bb);
    if (stmts)
      gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
  
    newphi = create_phi_node (var, bb_before_first_loop);
    add_phi_arg (newphi, prologue_after_cost_adjust_name, e_fallthru,
  	       UNKNOWN_LOCATION);
    add_phi_arg (newphi, *first_niters, e_false, UNKNOWN_LOCATION);
  
    *first_niters = PHI_RESULT (newphi);
  }
  
  /* Function slpeel_tree_peel_loop_to_edge.
  
     Peel the first (last) iterations of LOOP into a new prolog (epilog) loop
     that is placed on the entry (exit) edge E of LOOP. After this transformation
     we have two loops one after the other - first-loop iterates FIRST_NITERS
     times, and second-loop iterates the remainder NITERS - FIRST_NITERS times.
     If the cost model indicates that it is profitable to emit a scalar
     loop instead of the vector one, then the prolog (epilog) loop will iterate
     for the entire unchanged scalar iterations of the loop.
  
     Input:
     - LOOP: the loop to be peeled.
     - E: the exit or entry edge of LOOP.
          If it is the entry edge, we peel the first iterations of LOOP. In this
          case first-loop is LOOP, and second-loop is the newly created loop.
          If it is the exit edge, we peel the last iterations of LOOP. In this
          case, first-loop is the newly created loop, and second-loop is LOOP.
     - NITERS: the number of iterations that LOOP iterates.
     - FIRST_NITERS: the number of iterations that the first-loop should iterate.
     - UPDATE_FIRST_LOOP_COUNT:  specified whether this function is responsible
          for updating the loop bound of the first-loop to FIRST_NITERS.  If it
          is false, the caller of this function may want to take care of this
          (this can be useful if we don't want new stmts added to first-loop).
     - TH: cost model profitability threshold of iterations for vectorization.
     - CHECK_PROFITABILITY: specify whether cost model check has not occurred
                            during versioning and hence needs to occur during
  			  prologue generation or whether cost model check
  			  has not occurred during prologue generation and hence
  			  needs to occur during epilogue generation.
  
  
     Output:
     The function returns a pointer to the new loop-copy, or NULL if it failed
     to perform the transformation.
  
     The function generates two if-then-else guards: one before the first loop,
     and the other before the second loop:
     The first guard is:
       if (FIRST_NITERS == 0) then skip the first loop,
       and go directly to the second loop.
     The second guard is:
       if (FIRST_NITERS == NITERS) then skip the second loop.
  
     If the optional COND_EXPR and COND_EXPR_STMT_LIST arguments are given
     then the generated condition is combined with COND_EXPR and the
     statements in COND_EXPR_STMT_LIST are emitted together with it.
  
     FORNOW only simple loops are supported (see slpeel_can_duplicate_loop_p).
     FORNOW the resulting code will not be in loop-closed-ssa form.
  */
  
  static struct loop*
  slpeel_tree_peel_loop_to_edge (struct loop *loop,
  			       edge e, tree *first_niters,
  			       tree niters, bool update_first_loop_count,
  			       unsigned int th, bool check_profitability,
  			       tree cond_expr, gimple_seq cond_expr_stmt_list)
  {
    struct loop *new_loop = NULL, *first_loop, *second_loop;
    edge skip_e;
    tree pre_condition = NULL_TREE;
    bitmap definitions;
    basic_block bb_before_second_loop, bb_after_second_loop;
    basic_block bb_before_first_loop;
    basic_block bb_between_loops;
    basic_block new_exit_bb;
    gimple_stmt_iterator gsi;
    edge exit_e = single_exit (loop);
    LOC loop_loc;
    tree cost_pre_condition = NULL_TREE;
  
    if (!slpeel_can_duplicate_loop_p (loop, e))
      return NULL;
  
    /* We have to initialize cfg_hooks. Then, when calling
     cfg_hooks->split_edge, the function tree_split_edge
     is actually called and, when calling cfg_hooks->duplicate_block,
     the function tree_duplicate_bb is called.  */
    gimple_register_cfg_hooks ();
  
    /* If the loop has a virtual PHI, but exit bb doesn't, create a virtual PHI
       in the exit bb and rename all the uses after the loop.  This simplifies
       the *guard[12] routines, which assume loop closed SSA form for all PHIs
       (but normally loop closed SSA form doesn't require virtual PHIs to be
       in the same form).  Doing this early simplifies the checking what
       uses should be renamed.  */
    for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
      if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
        {
  	gimple phi = gsi_stmt (gsi);
  	for (gsi = gsi_start_phis (exit_e->dest);
  	     !gsi_end_p (gsi); gsi_next (&gsi))
  	  if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
  	    break;
  	if (gsi_end_p (gsi))
  	  {
  	    gimple new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (phi)),
  					      exit_e->dest);
  	    tree vop = PHI_ARG_DEF_FROM_EDGE (phi, EDGE_SUCC (loop->latch, 0));
  	    imm_use_iterator imm_iter;
  	    gimple stmt;
  	    tree new_vop = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)),
  					  new_phi);
  	    use_operand_p use_p;
  
  	    add_phi_arg (new_phi, vop, exit_e, UNKNOWN_LOCATION);
  	    gimple_phi_set_result (new_phi, new_vop);
  	    FOR_EACH_IMM_USE_STMT (stmt, imm_iter, vop)
  	      if (stmt != new_phi && gimple_bb (stmt) != loop->header)
  		FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
  		  SET_USE (use_p, new_vop);
  	  }
  	break;
        }
  
    /* 1. Generate a copy of LOOP and put it on E (E is the entry/exit of LOOP).
          Resulting CFG would be:
  
          first_loop:
          do {
          } while ...
  
          second_loop:
          do {
          } while ...
  
          orig_exit_bb:
     */
  
    if (!(new_loop = slpeel_tree_duplicate_loop_to_edge_cfg (loop, e)))
      {
        loop_loc = find_loop_location (loop);
        if (dump_file && (dump_flags & TDF_DETAILS))
          {
            if (loop_loc != UNKNOWN_LOC)
              fprintf (dump_file, "\n%s:%d: note: ",
                       LOC_FILE (loop_loc), LOC_LINE (loop_loc));
            fprintf (dump_file, "tree_duplicate_loop_to_edge_cfg failed.\n");
          }
        return NULL;
      }
  
    if (MAY_HAVE_DEBUG_STMTS)
      {
        gcc_assert (!adjust_vec);
        adjust_vec = VEC_alloc (adjust_info, stack, 32);
      }
  
    if (e == exit_e)
      {
        /* NEW_LOOP was placed after LOOP.  */
        first_loop = loop;
        second_loop = new_loop;
      }
    else
      {
        /* NEW_LOOP was placed before LOOP.  */
        first_loop = new_loop;
        second_loop = loop;
      }
  
    definitions = ssa_names_to_replace ();
    slpeel_update_phis_for_duplicate_loop (loop, new_loop, e == exit_e);
    rename_variables_in_loop (new_loop);
  
  
    /* 2.  Add the guard code in one of the following ways:
  
       2.a Add the guard that controls whether the first loop is executed.
           This occurs when this function is invoked for prologue or epilogue
  	 generation and when the cost model check can be done at compile time.
  
           Resulting CFG would be:
  
           bb_before_first_loop:
           if (FIRST_NITERS == 0) GOTO bb_before_second_loop
                                  GOTO first-loop
  
           first_loop:
           do {
           } while ...
  
           bb_before_second_loop:
  
           second_loop:
           do {
           } while ...
  
           orig_exit_bb:
  
       2.b Add the cost model check that allows the prologue
           to iterate for the entire unchanged scalar
           iterations of the loop in the event that the cost
           model indicates that the scalar loop is more
           profitable than the vector one. This occurs when
  	 this function is invoked for prologue generation
  	 and the cost model check needs to be done at run
  	 time.
  
           Resulting CFG after prologue peeling would be:
  
           if (scalar_loop_iterations <= th)
             FIRST_NITERS = scalar_loop_iterations
  
           bb_before_first_loop:
           if (FIRST_NITERS == 0) GOTO bb_before_second_loop
                                  GOTO first-loop
  
           first_loop:
           do {
           } while ...
  
           bb_before_second_loop:
  
           second_loop:
           do {
           } while ...
  
           orig_exit_bb:
  
       2.c Add the cost model check that allows the epilogue
           to iterate for the entire unchanged scalar
           iterations of the loop in the event that the cost
           model indicates that the scalar loop is more
           profitable than the vector one. This occurs when
  	 this function is invoked for epilogue generation
  	 and the cost model check needs to be done at run
  	 time.  This check is combined with any pre-existing
  	 check in COND_EXPR to avoid versioning.
  
           Resulting CFG after prologue peeling would be:
  
           bb_before_first_loop:
           if ((scalar_loop_iterations <= th)
               ||
               FIRST_NITERS == 0) GOTO bb_before_second_loop
                                  GOTO first-loop
  
           first_loop:
           do {
           } while ...
  
           bb_before_second_loop:
  
           second_loop:
           do {
           } while ...
  
           orig_exit_bb:
    */
  
    bb_before_first_loop = split_edge (loop_preheader_edge (first_loop));
    bb_before_second_loop = split_edge (single_exit (first_loop));
  
    /* Epilogue peeling.  */
    if (!update_first_loop_count)
      {
        pre_condition =
  	fold_build2 (LE_EXPR, boolean_type_node, *first_niters,
  		     build_int_cst (TREE_TYPE (*first_niters), 0));
        if (check_profitability)
  	{
  	  tree scalar_loop_iters
  	    = unshare_expr (LOOP_VINFO_NITERS_UNCHANGED
  					(loop_vec_info_for_loop (loop)));
  	  cost_pre_condition =
  	    fold_build2 (LE_EXPR, boolean_type_node, scalar_loop_iters,
  		         build_int_cst (TREE_TYPE (scalar_loop_iters), th));
  
  	  pre_condition = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
  				       cost_pre_condition, pre_condition);
  	}
        if (cond_expr)
  	{
  	  pre_condition =
  	    fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
  			 pre_condition,
  			 fold_build1 (TRUTH_NOT_EXPR, boolean_type_node,
  				      cond_expr));
  	}
      }
  
    /* Prologue peeling.  */
    else
      {
        if (check_profitability)
  	set_prologue_iterations (bb_before_first_loop, first_niters,
  				 loop, th);
  
        pre_condition =
  	fold_build2 (LE_EXPR, boolean_type_node, *first_niters,
  		     build_int_cst (TREE_TYPE (*first_niters), 0));
      }
  
    skip_e = slpeel_add_loop_guard (bb_before_first_loop, pre_condition,
  				  cond_expr_stmt_list,
                                    bb_before_second_loop, bb_before_first_loop);
    slpeel_update_phi_nodes_for_guard1 (skip_e, first_loop,
  				      first_loop == new_loop,
  				      &new_exit_bb, &definitions);
  
  
    /* 3. Add the guard that controls whether the second loop is executed.
          Resulting CFG would be:
  
          bb_before_first_loop:
          if (FIRST_NITERS == 0) GOTO bb_before_second_loop (skip first loop)
                                 GOTO first-loop
  
          first_loop:
          do {
          } while ...
  
          bb_between_loops:
          if (FIRST_NITERS == NITERS) GOTO bb_after_second_loop (skip second loop)
                                      GOTO bb_before_second_loop
  
          bb_before_second_loop:
  
          second_loop:
          do {
          } while ...
  
          bb_after_second_loop:
  
          orig_exit_bb:
     */
  
    bb_between_loops = new_exit_bb;
    bb_after_second_loop = split_edge (single_exit (second_loop));
  
    pre_condition =
  	fold_build2 (EQ_EXPR, boolean_type_node, *first_niters, niters);
    skip_e = slpeel_add_loop_guard (bb_between_loops, pre_condition, NULL,
                                    bb_after_second_loop, bb_before_first_loop);
    slpeel_update_phi_nodes_for_guard2 (skip_e, second_loop,
                                       second_loop == new_loop, &new_exit_bb);
  
    /* 4. Make first-loop iterate FIRST_NITERS times, if requested.
     */
    if (update_first_loop_count)
      slpeel_make_loop_iterate_ntimes (first_loop, *first_niters);
  
    BITMAP_FREE (definitions);
    delete_update_ssa ();
  
    adjust_vec_debug_stmts ();
  
    return new_loop;
  }
  
  /* Function vect_get_loop_location.
  
     Extract the location of the loop in the source code.
     If the loop is not well formed for vectorization, an estimated
     location is calculated.
     Return the loop location if succeed and NULL if not.  */
  
  LOC
  find_loop_location (struct loop *loop)
  {
    gimple stmt = NULL;
    basic_block bb;
    gimple_stmt_iterator si;
  
    if (!loop)
      return UNKNOWN_LOC;
  
    stmt = get_loop_exit_condition (loop);
  
    if (stmt && gimple_location (stmt) != UNKNOWN_LOC)
      return gimple_location (stmt);
  
    /* If we got here the loop is probably not "well formed",
       try to estimate the loop location */
  
    if (!loop->header)
      return UNKNOWN_LOC;
  
    bb = loop->header;
  
    for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
      {
        stmt = gsi_stmt (si);
        if (gimple_location (stmt) != UNKNOWN_LOC)
          return gimple_location (stmt);
      }
  
    return UNKNOWN_LOC;
  }
  
  
  /* This function builds ni_name = number of iterations loop executes
     on the loop preheader.  If SEQ is given the stmt is instead emitted
     there.  */
  
  static tree
  vect_build_loop_niters (loop_vec_info loop_vinfo, gimple_seq seq)
  {
    tree ni_name, var;
    gimple_seq stmts = NULL;
    edge pe;
    struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    tree ni = unshare_expr (LOOP_VINFO_NITERS (loop_vinfo));
  
    var = create_tmp_var (TREE_TYPE (ni), "niters");
    add_referenced_var (var);
    ni_name = force_gimple_operand (ni, &stmts, false, var);
  
    pe = loop_preheader_edge (loop);
    if (stmts)
      {
        if (seq)
  	gimple_seq_add_seq (&seq, stmts);
        else
  	{
  	  basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
  	  gcc_assert (!new_bb);
  	}
      }
  
    return ni_name;
  }
  
  
  /* This function generates the following statements:
  
   ni_name = number of iterations loop executes
   ratio = ni_name / vf
   ratio_mult_vf_name = ratio * vf
  
   and places them at the loop preheader edge or in COND_EXPR_STMT_LIST
   if that is non-NULL.  */
  
  static void
  vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo,
  				 tree *ni_name_ptr,
  				 tree *ratio_mult_vf_name_ptr,
  				 tree *ratio_name_ptr,
  				 gimple_seq cond_expr_stmt_list)
  {
  
    edge pe;
    basic_block new_bb;
    gimple_seq stmts;
    tree ni_name, ni_minus_gap_name;
    tree var;
    tree ratio_name;
    tree ratio_mult_vf_name;
    struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    tree ni = LOOP_VINFO_NITERS (loop_vinfo);
    int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
    tree log_vf;
  
    pe = loop_preheader_edge (loop);
  
    /* Generate temporary variable that contains
       number of iterations loop executes.  */
  
    ni_name = vect_build_loop_niters (loop_vinfo, cond_expr_stmt_list);
    log_vf = build_int_cst (TREE_TYPE (ni), exact_log2 (vf));
  
    /* If epilogue loop is required because of data accesses with gaps, we
       subtract one iteration from the total number of iterations here for
       correct calculation of RATIO.  */
    if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo))
      {
        ni_minus_gap_name = fold_build2 (MINUS_EXPR, TREE_TYPE (ni_name),
  				       ni_name,
  			               build_one_cst (TREE_TYPE (ni_name)));
        if (!is_gimple_val (ni_minus_gap_name))
  	{
  	  var = create_tmp_var (TREE_TYPE (ni), "ni_gap");
            add_referenced_var (var);
  
            stmts = NULL;
            ni_minus_gap_name = force_gimple_operand (ni_minus_gap_name, &stmts,
  						    true, var);
            if (cond_expr_stmt_list)
              gimple_seq_add_seq (&cond_expr_stmt_list, stmts);
            else
              {
                pe = loop_preheader_edge (loop);
                new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
                gcc_assert (!new_bb);
              }
          }
      }
    else
      ni_minus_gap_name = ni_name;
  
    /* Create: ratio = ni >> log2(vf) */
  
    ratio_name = fold_build2 (RSHIFT_EXPR, TREE_TYPE (ni_minus_gap_name),
  			    ni_minus_gap_name, log_vf);
    if (!is_gimple_val (ratio_name))
      {
        var = create_tmp_var (TREE_TYPE (ni), "bnd");
        add_referenced_var (var);
  
        stmts = NULL;
        ratio_name = force_gimple_operand (ratio_name, &stmts, true, var);
        if (cond_expr_stmt_list)
  	gimple_seq_add_seq (&cond_expr_stmt_list, stmts);
        else
  	{
  	  pe = loop_preheader_edge (loop);
  	  new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
  	  gcc_assert (!new_bb);
  	}
      }
  
    /* Create: ratio_mult_vf = ratio << log2 (vf).  */
  
    ratio_mult_vf_name = fold_build2 (LSHIFT_EXPR, TREE_TYPE (ratio_name),
  				    ratio_name, log_vf);
    if (!is_gimple_val (ratio_mult_vf_name))
      {
        var = create_tmp_var (TREE_TYPE (ni), "ratio_mult_vf");
        add_referenced_var (var);
  
        stmts = NULL;
        ratio_mult_vf_name = force_gimple_operand (ratio_mult_vf_name, &stmts,
  						 true, var);
        if (cond_expr_stmt_list)
  	gimple_seq_add_seq (&cond_expr_stmt_list, stmts);
        else
  	{
  	  pe = loop_preheader_edge (loop);
  	  new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
  	  gcc_assert (!new_bb);
  	}
      }
  
    *ni_name_ptr = ni_name;
    *ratio_mult_vf_name_ptr = ratio_mult_vf_name;
    *ratio_name_ptr = ratio_name;
  
    return;
  }
  
  /* Function vect_can_advance_ivs_p
  
     In case the number of iterations that LOOP iterates is unknown at compile
     time, an epilog loop will be generated, and the loop induction variables
     (IVs) will be "advanced" to the value they are supposed to take just before
     the epilog loop.  Here we check that the access function of the loop IVs
     and the expression that represents the loop bound are simple enough.
     These restrictions will be relaxed in the future.  */
  
  bool
  vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
  {
    struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    basic_block bb = loop->header;
    gimple phi;
    gimple_stmt_iterator gsi;
  
    /* Analyze phi functions of the loop header.  */
  
    if (vect_print_dump_info (REPORT_DETAILS))
      fprintf (vect_dump, "vect_can_advance_ivs_p:");
  
    for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
      {
        tree access_fn = NULL;
        tree evolution_part;
  
        phi = gsi_stmt (gsi);
        if (vect_print_dump_info (REPORT_DETAILS))
  	{
            fprintf (vect_dump, "Analyze phi: ");
            print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
  	}
  
        /* Skip virtual phi's. The data dependences that are associated with
           virtual defs/uses (i.e., memory accesses) are analyzed elsewhere.  */
  
        if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
  	{
  	  if (vect_print_dump_info (REPORT_DETAILS))
  	    fprintf (vect_dump, "virtual phi. skip.");
  	  continue;
  	}
  
        /* Skip reduction phis.  */
  
        if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (phi)) == vect_reduction_def)
          {
            if (vect_print_dump_info (REPORT_DETAILS))
              fprintf (vect_dump, "reduc phi. skip.");
            continue;
          }
  
        /* Analyze the evolution function.  */
  
        access_fn = instantiate_parameters
  	(loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
  
        if (!access_fn)
  	{
  	  if (vect_print_dump_info (REPORT_DETAILS))
  	    fprintf (vect_dump, "No Access function.");
  	  return false;
  	}
  
        if (vect_print_dump_info (REPORT_DETAILS))
          {
  	  fprintf (vect_dump, "Access function of PHI: ");
  	  print_generic_expr (vect_dump, access_fn, TDF_SLIM);
          }
  
        evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
  
        if (evolution_part == NULL_TREE)
          {
  	  if (vect_print_dump_info (REPORT_DETAILS))
  	    fprintf (vect_dump, "No evolution.");
  	  return false;
          }
  
        /* FORNOW: We do not transform initial conditions of IVs
  	 which evolution functions are a polynomial of degree >= 2.  */
  
        if (tree_is_chrec (evolution_part))
  	return false;
      }
  
    return true;
  }
  
  
  /*   Function vect_update_ivs_after_vectorizer.
  
       "Advance" the induction variables of LOOP to the value they should take
       after the execution of LOOP.  This is currently necessary because the
       vectorizer does not handle induction variables that are used after the
       loop.  Such a situation occurs when the last iterations of LOOP are
       peeled, because:
       1. We introduced new uses after LOOP for IVs that were not originally used
          after LOOP: the IVs of LOOP are now used by an epilog loop.
       2. LOOP is going to be vectorized; this means that it will iterate N/VF
          times, whereas the loop IVs should be bumped N times.
  
       Input:
       - LOOP - a loop that is going to be vectorized. The last few iterations
                of LOOP were peeled.
       - NITERS - the number of iterations that LOOP executes (before it is
                  vectorized). i.e, the number of times the ivs should be bumped.
       - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
                    coming out from LOOP on which there are uses of the LOOP ivs
  		  (this is the path from LOOP->exit to epilog_loop->preheader).
  
                    The new definitions of the ivs are placed in LOOP->exit.
                    The phi args associated with the edge UPDATE_E in the bb
                    UPDATE_E->dest are updated accordingly.
  
       Assumption 1: Like the rest of the vectorizer, this function assumes
       a single loop exit that has a single predecessor.
  
       Assumption 2: The phi nodes in the LOOP header and in update_bb are
       organized in the same order.
  
       Assumption 3: The access function of the ivs is simple enough (see
       vect_can_advance_ivs_p).  This assumption will be relaxed in the future.
  
       Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
       coming out of LOOP on which the ivs of LOOP are used (this is the path
       that leads to the epilog loop; other paths skip the epilog loop).  This
       path starts with the edge UPDATE_E, and its destination (denoted update_bb)
       needs to have its phis updated.
   */
  
  static void
  vect_update_ivs_after_vectorizer (loop_vec_info loop_vinfo, tree niters,
  				  edge update_e)
  {
    struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    basic_block exit_bb = single_exit (loop)->dest;
    gimple phi, phi1;
    gimple_stmt_iterator gsi, gsi1;
    basic_block update_bb = update_e->dest;
  
    /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
  
    /* Make sure there exists a single-predecessor exit bb:  */
    gcc_assert (single_pred_p (exit_bb));
  
    for (gsi = gsi_start_phis (loop->header), gsi1 = gsi_start_phis (update_bb);
         !gsi_end_p (gsi) && !gsi_end_p (gsi1);
         gsi_next (&gsi), gsi_next (&gsi1))
      {
        tree init_expr;
        tree step_expr, off;
        tree type;
        tree var, ni, ni_name;
        gimple_stmt_iterator last_gsi;
        stmt_vec_info stmt_info;
  
        phi = gsi_stmt (gsi);
        phi1 = gsi_stmt (gsi1);
        if (vect_print_dump_info (REPORT_DETAILS))
          {
            fprintf (vect_dump, "vect_update_ivs_after_vectorizer: phi: ");
  	  print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
          }
  
        /* Skip virtual phi's.  */
        if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
  	{
  	  if (vect_print_dump_info (REPORT_DETAILS))
  	    fprintf (vect_dump, "virtual phi. skip.");
  	  continue;
  	}
  
        /* Skip reduction phis.  */
        stmt_info = vinfo_for_stmt (phi);
        if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_reduction_def)
          {
            if (vect_print_dump_info (REPORT_DETAILS))
              fprintf (vect_dump, "reduc phi. skip.");
            continue;
          }
  
        type = TREE_TYPE (gimple_phi_result (phi));
        step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info);
        step_expr = unshare_expr (step_expr);
  
        /* FORNOW: We do not support IVs whose evolution function is a polynomial
           of degree >= 2 or exponential.  */
        gcc_assert (!tree_is_chrec (step_expr));
  
        init_expr = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
  
        off = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr),
  			 fold_convert (TREE_TYPE (step_expr), niters),
  			 step_expr);
        if (POINTER_TYPE_P (type))
  	ni = fold_build_pointer_plus (init_expr, off);
        else
  	ni = fold_build2 (PLUS_EXPR, type,
  			  init_expr, fold_convert (type, off));
  
        var = create_tmp_var (type, "tmp");
        add_referenced_var (var);
  
        last_gsi = gsi_last_bb (exit_bb);
        ni_name = force_gimple_operand_gsi (&last_gsi, ni, false, var,
  					  true, GSI_SAME_STMT);
  
        /* Fix phi expressions in the successor bb.  */
        adjust_phi_and_debug_stmts (phi1, update_e, ni_name);
      }
  }
  
  /* Return the more conservative threshold between the
     min_profitable_iters returned by the cost model and the user
     specified threshold, if provided.  */
  
  static unsigned int
  conservative_cost_threshold (loop_vec_info loop_vinfo,
  			     int min_profitable_iters)
  {
    unsigned int th;
    int min_scalar_loop_bound;
  
    min_scalar_loop_bound = ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND)
  			    * LOOP_VINFO_VECT_FACTOR (loop_vinfo)) - 1);
  
    /* Use the cost model only if it is more conservative than user specified
       threshold.  */
    th = (unsigned) min_scalar_loop_bound;
    if (min_profitable_iters
        && (!min_scalar_loop_bound
            || min_profitable_iters > min_scalar_loop_bound))
      th = (unsigned) min_profitable_iters;
  
    if (th && vect_print_dump_info (REPORT_COST))
      fprintf (vect_dump, "Profitability threshold is %u loop iterations.", th);
  
    return th;
  }
  
  /* Function vect_do_peeling_for_loop_bound
  
     Peel the last iterations of the loop represented by LOOP_VINFO.
     The peeled iterations form a new epilog loop.  Given that the loop now
     iterates NITERS times, the new epilog loop iterates
     NITERS % VECTORIZATION_FACTOR times.
  
     The original loop will later be made to iterate
     NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO).
  
     COND_EXPR and COND_EXPR_STMT_LIST are combined with a new generated
     test.  */
  
  void
  vect_do_peeling_for_loop_bound (loop_vec_info loop_vinfo, tree *ratio,
  				tree cond_expr, gimple_seq cond_expr_stmt_list)
  {
    tree ni_name, ratio_mult_vf_name;
    struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    struct loop *new_loop;
    edge update_e;
    basic_block preheader;
    int loop_num;
    bool check_profitability = false;
    unsigned int th = 0;
    int min_profitable_iters;
  
    if (vect_print_dump_info (REPORT_DETAILS))
      fprintf (vect_dump, "=== vect_do_peeling_for_loop_bound ===");
  
    initialize_original_copy_tables ();
  
    /* Generate the following variables on the preheader of original loop:
  
       ni_name = number of iteration the original loop executes
       ratio = ni_name / vf
       ratio_mult_vf_name = ratio * vf  */
    vect_generate_tmps_on_preheader (loop_vinfo, &ni_name,
  				   &ratio_mult_vf_name, ratio,
  				   cond_expr_stmt_list);
  
    loop_num  = loop->num;
  
    /* If cost model check not done during versioning and
       peeling for alignment.  */
    if (!LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
        && !LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo)
        && !LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo)
        && !cond_expr)
      {
        check_profitability = true;
  
        /* Get profitability threshold for vectorized loop.  */
        min_profitable_iters = LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo);
  
        th = conservative_cost_threshold (loop_vinfo,
  					min_profitable_iters);
      }
  
    new_loop = slpeel_tree_peel_loop_to_edge (loop, single_exit (loop),
                                              &ratio_mult_vf_name, ni_name, false,
                                              th, check_profitability,
  					    cond_expr, cond_expr_stmt_list);
    gcc_assert (new_loop);
    gcc_assert (loop_num == loop->num);
  #ifdef ENABLE_CHECKING
    slpeel_verify_cfg_after_peeling (loop, new_loop);
  #endif
  
    /* A guard that controls whether the new_loop is to be executed or skipped
       is placed in LOOP->exit.  LOOP->exit therefore has two successors - one
       is the preheader of NEW_LOOP, where the IVs from LOOP are used.  The other
       is a bb after NEW_LOOP, where these IVs are not used.  Find the edge that
       is on the path where the LOOP IVs are used and need to be updated.  */
  
    preheader = loop_preheader_edge (new_loop)->src;
    if (EDGE_PRED (preheader, 0)->src == single_exit (loop)->dest)
      update_e = EDGE_PRED (preheader, 0);
    else
      update_e = EDGE_PRED (preheader, 1);
  
    /* Update IVs of original loop as if they were advanced
       by ratio_mult_vf_name steps.  */
    vect_update_ivs_after_vectorizer (loop_vinfo, ratio_mult_vf_name, update_e);
  
    /* After peeling we have to reset scalar evolution analyzer.  */
    scev_reset ();
  
    free_original_copy_tables ();
  }
  
  
  /* Function vect_gen_niters_for_prolog_loop
  
     Set the number of iterations for the loop represented by LOOP_VINFO
     to the minimum between LOOP_NITERS (the original iteration count of the loop)
     and the misalignment of DR - the data reference recorded in
     LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO).  As a result, after the execution of
     this loop, the data reference DR will refer to an aligned location.
  
     The following computation is generated:
  
     If the misalignment of DR is known at compile time:
       addr_mis = int mis = DR_MISALIGNMENT (dr);
     Else, compute address misalignment in bytes:
       addr_mis = addr & (vectype_size - 1)
  
     prolog_niters = min (LOOP_NITERS, ((VF - addr_mis/elem_size)&(VF-1))/step)
  
     (elem_size = element type size; an element is the scalar element whose type
     is the inner type of the vectype)
  
     When the step of the data-ref in the loop is not 1 (as in interleaved data
     and SLP), the number of iterations of the prolog must be divided by the step
     (which is equal to the size of interleaved group).
  
     The above formulas assume that VF == number of elements in the vector. This
     may not hold when there are multiple-types in the loop.
     In this case, for some data-references in the loop the VF does not represent
     the number of elements that fit in the vector.  Therefore, instead of VF we
     use TYPE_VECTOR_SUBPARTS.  */
  
  static tree
  vect_gen_niters_for_prolog_loop (loop_vec_info loop_vinfo, tree loop_niters)
  {
    struct data_reference *dr = LOOP_VINFO_UNALIGNED_DR (loop_vinfo);
    struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    tree var;
    gimple_seq stmts;
    tree iters, iters_name;
    edge pe;
    basic_block new_bb;
    gimple dr_stmt = DR_STMT (dr);
    stmt_vec_info stmt_info = vinfo_for_stmt (dr_stmt);
    tree vectype = STMT_VINFO_VECTYPE (stmt_info);
    int vectype_align = TYPE_ALIGN (vectype) / BITS_PER_UNIT;
    tree niters_type = TREE_TYPE (loop_niters);
    int nelements = TYPE_VECTOR_SUBPARTS (vectype);
  
    pe = loop_preheader_edge (loop);
  
    if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) > 0)
      {
        int npeel = LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo);
  
        if (vect_print_dump_info (REPORT_DETAILS))
          fprintf (vect_dump, "known peeling = %d.", npeel);
  
        iters = build_int_cst (niters_type, npeel);
      }
    else
      {
        gimple_seq new_stmts = NULL;
        bool negative = tree_int_cst_compare (DR_STEP (dr), size_zero_node) < 0;
        tree offset = negative
  	  ? size_int (-TYPE_VECTOR_SUBPARTS (vectype) + 1) : NULL_TREE;
        tree start_addr = vect_create_addr_base_for_vector_ref (dr_stmt,
  						&new_stmts, offset, loop);
        tree ptr_type = TREE_TYPE (start_addr);
        tree size = TYPE_SIZE (ptr_type);
        tree type = lang_hooks.types.type_for_size (tree_low_cst (size, 1), 1);
        tree vectype_size_minus_1 = build_int_cst (type, vectype_align - 1);
        tree elem_size_log =
          build_int_cst (type, exact_log2 (vectype_align/nelements));
        tree nelements_minus_1 = build_int_cst (type, nelements - 1);
        tree nelements_tree = build_int_cst (type, nelements);
        tree byte_misalign;
        tree elem_misalign;
  
        new_bb = gsi_insert_seq_on_edge_immediate (pe, new_stmts);
        gcc_assert (!new_bb);
  
        /* Create:  byte_misalign = addr & (vectype_size - 1)  */
        byte_misalign =
          fold_build2 (BIT_AND_EXPR, type, fold_convert (type, start_addr), 
                       vectype_size_minus_1);
  
        /* Create:  elem_misalign = byte_misalign / element_size  */
        elem_misalign =
          fold_build2 (RSHIFT_EXPR, type, byte_misalign, elem_size_log);
  
        /* Create:  (niters_type) (nelements - elem_misalign)&(nelements - 1)  */
        if (negative)
  	iters = fold_build2 (MINUS_EXPR, type, elem_misalign, nelements_tree);
        else
  	iters = fold_build2 (MINUS_EXPR, type, nelements_tree, elem_misalign);
        iters = fold_build2 (BIT_AND_EXPR, type, iters, nelements_minus_1);
        iters = fold_convert (niters_type, iters);
      }
  
    /* Create:  prolog_loop_niters = min (iters, loop_niters) */
    /* If the loop bound is known at compile time we already verified that it is
       greater than vf; since the misalignment ('iters') is at most vf, there's
       no need to generate the MIN_EXPR in this case.  */
    if (TREE_CODE (loop_niters) != INTEGER_CST)
      iters = fold_build2 (MIN_EXPR, niters_type, iters, loop_niters);
  
    if (vect_print_dump_info (REPORT_DETAILS))
      {
        fprintf (vect_dump, "niters for prolog loop: ");
        print_generic_expr (vect_dump, iters, TDF_SLIM);
      }
  
    var = create_tmp_var (niters_type, "prolog_loop_niters");
    add_referenced_var (var);
    stmts = NULL;
    iters_name = force_gimple_operand (iters, &stmts, false, var);
  
    /* Insert stmt on loop preheader edge.  */
    if (stmts)
      {
        basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
        gcc_assert (!new_bb);
      }
  
    return iters_name;
  }
  
  
  /* Function vect_update_init_of_dr
  
     NITERS iterations were peeled from LOOP.  DR represents a data reference
     in LOOP.  This function updates the information recorded in DR to
     account for the fact that the first NITERS iterations had already been
     executed.  Specifically, it updates the OFFSET field of DR.  */
  
  static void
  vect_update_init_of_dr (struct data_reference *dr, tree niters)
  {
    tree offset = DR_OFFSET (dr);
  
    niters = fold_build2 (MULT_EXPR, sizetype,
  			fold_convert (sizetype, niters),
  			fold_convert (sizetype, DR_STEP (dr)));
    offset = fold_build2 (PLUS_EXPR, sizetype,
  			fold_convert (sizetype, offset), niters);
    DR_OFFSET (dr) = offset;
  }
  
  
  /* Function vect_update_inits_of_drs
  
     NITERS iterations were peeled from the loop represented by LOOP_VINFO.
     This function updates the information recorded for the data references in
     the loop to account for the fact that the first NITERS iterations had
     already been executed.  Specifically, it updates the initial_condition of
     the access_function of all the data_references in the loop.  */
  
  static void
  vect_update_inits_of_drs (loop_vec_info loop_vinfo, tree niters)
  {
    unsigned int i;
    VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
    struct data_reference *dr;
  
    if (vect_print_dump_info (REPORT_DETAILS))
      fprintf (vect_dump, "=== vect_update_inits_of_dr ===");
  
    FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
      vect_update_init_of_dr (dr, niters);
  }
  
  
  /* Function vect_do_peeling_for_alignment
  
     Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
     'niters' is set to the misalignment of one of the data references in the
     loop, thereby forcing it to refer to an aligned location at the beginning
     of the execution of this loop.  The data reference for which we are
     peeling is recorded in LOOP_VINFO_UNALIGNED_DR.  */
  
  void
  vect_do_peeling_for_alignment (loop_vec_info loop_vinfo)
  {
    struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    tree niters_of_prolog_loop, ni_name;
    tree n_iters;
    tree wide_prolog_niters;
    struct loop *new_loop;
    unsigned int th = 0;
    int min_profitable_iters;
  
    if (vect_print_dump_info (REPORT_DETAILS))
      fprintf (vect_dump, "=== vect_do_peeling_for_alignment ===");
  
    initialize_original_copy_tables ();
  
    ni_name = vect_build_loop_niters (loop_vinfo, NULL);
    niters_of_prolog_loop = vect_gen_niters_for_prolog_loop (loop_vinfo,
  							   ni_name);
  
    /* Get profitability threshold for vectorized loop.  */
    min_profitable_iters = LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo);
    th = conservative_cost_threshold (loop_vinfo,
  				    min_profitable_iters);
  
    /* Peel the prolog loop and iterate it niters_of_prolog_loop.  */
    new_loop =
      slpeel_tree_peel_loop_to_edge (loop, loop_preheader_edge (loop),
  				   &niters_of_prolog_loop, ni_name, true,
  				   th, true, NULL_TREE, NULL);
  
    gcc_assert (new_loop);
  #ifdef ENABLE_CHECKING
    slpeel_verify_cfg_after_peeling (new_loop, loop);
  #endif
  
    /* Update number of times loop executes.  */
    n_iters = LOOP_VINFO_NITERS (loop_vinfo);
    LOOP_VINFO_NITERS (loop_vinfo) = fold_build2 (MINUS_EXPR,
  		TREE_TYPE (n_iters), n_iters, niters_of_prolog_loop);
  
    if (types_compatible_p (sizetype, TREE_TYPE (niters_of_prolog_loop)))
      wide_prolog_niters = niters_of_prolog_loop;
    else
      {
        gimple_seq seq = NULL;
        edge pe = loop_preheader_edge (loop);
        tree wide_iters = fold_convert (sizetype, niters_of_prolog_loop);
        tree var = create_tmp_var (sizetype, "prolog_loop_adjusted_niters");
        add_referenced_var (var);
        wide_prolog_niters = force_gimple_operand (wide_iters, &seq, false,
                                                   var);
        if (seq)
  	{
  	  /* Insert stmt on loop preheader edge.  */
            basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, seq);
            gcc_assert (!new_bb);
          }
      }
  
    /* Update the init conditions of the access functions of all data refs.  */
    vect_update_inits_of_drs (loop_vinfo, wide_prolog_niters);
  
    /* After peeling we have to reset scalar evolution analyzer.  */
    scev_reset ();
  
    free_original_copy_tables ();
  }
  
  
  /* Function vect_create_cond_for_align_checks.
  
     Create a conditional expression that represents the alignment checks for
     all of data references (array element references) whose alignment must be
     checked at runtime.
  
     Input:
     COND_EXPR  - input conditional expression.  New conditions will be chained
                  with logical AND operation.
     LOOP_VINFO - two fields of the loop information are used.
                  LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
                  LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
  
     Output:
     COND_EXPR_STMT_LIST - statements needed to construct the conditional
                           expression.
     The returned value is the conditional expression to be used in the if
     statement that controls which version of the loop gets executed at runtime.
  
     The algorithm makes two assumptions:
       1) The number of bytes "n" in a vector is a power of 2.
       2) An address "a" is aligned if a%n is zero and that this
          test can be done as a&(n-1) == 0.  For example, for 16
          byte vectors the test is a&0xf == 0.  */
  
  static void
  vect_create_cond_for_align_checks (loop_vec_info loop_vinfo,
                                     tree *cond_expr,
  				   gimple_seq *cond_expr_stmt_list)
  {
    struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    VEC(gimple,heap) *may_misalign_stmts
      = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo);
    gimple ref_stmt;
    int mask = LOOP_VINFO_PTR_MASK (loop_vinfo);
    tree mask_cst;
    unsigned int i;
    tree psize;
    tree int_ptrsize_type;
    char tmp_name[20];
    tree or_tmp_name = NULL_TREE;
    tree and_tmp, and_tmp_name;
    gimple and_stmt;
    tree ptrsize_zero;
    tree part_cond_expr;
  
    /* Check that mask is one less than a power of 2, i.e., mask is
       all zeros followed by all ones.  */
    gcc_assert ((mask != 0) && ((mask & (mask+1)) == 0));
  
    /* CHECKME: what is the best integer or unsigned type to use to hold a
       cast from a pointer value?  */
    psize = TYPE_SIZE (ptr_type_node);
    int_ptrsize_type
      = lang_hooks.types.type_for_size (tree_low_cst (psize, 1), 0);
  
    /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address
       of the first vector of the i'th data reference. */
  
    FOR_EACH_VEC_ELT (gimple, may_misalign_stmts, i, ref_stmt)
      {
        gimple_seq new_stmt_list = NULL;
        tree addr_base;
        tree addr_tmp, addr_tmp_name;
        tree or_tmp, new_or_tmp_name;
        gimple addr_stmt, or_stmt;
        stmt_vec_info stmt_vinfo = vinfo_for_stmt (ref_stmt);
        tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
        bool negative = tree_int_cst_compare
  	(DR_STEP (STMT_VINFO_DATA_REF (stmt_vinfo)), size_zero_node) < 0;
        tree offset = negative
  	? size_int (-TYPE_VECTOR_SUBPARTS (vectype) + 1) : NULL_TREE;
  
        /* create: addr_tmp = (int)(address_of_first_vector) */
        addr_base =
  	vect_create_addr_base_for_vector_ref (ref_stmt, &new_stmt_list,
  					      offset, loop);
        if (new_stmt_list != NULL)
  	gimple_seq_add_seq (cond_expr_stmt_list, new_stmt_list);
  
        sprintf (tmp_name, "%s%d", "addr2int", i);
        addr_tmp = create_tmp_var (int_ptrsize_type, tmp_name);
        add_referenced_var (addr_tmp);
        addr_tmp_name = make_ssa_name (addr_tmp, NULL);
        addr_stmt = gimple_build_assign_with_ops (NOP_EXPR, addr_tmp_name,
  						addr_base, NULL_TREE);
        SSA_NAME_DEF_STMT (addr_tmp_name) = addr_stmt;
        gimple_seq_add_stmt (cond_expr_stmt_list, addr_stmt);
  
        /* The addresses are OR together.  */
  
        if (or_tmp_name != NULL_TREE)
          {
            /* create: or_tmp = or_tmp | addr_tmp */
            sprintf (tmp_name, "%s%d", "orptrs", i);
            or_tmp = create_tmp_var (int_ptrsize_type, tmp_name);
            add_referenced_var (or_tmp);
  	  new_or_tmp_name = make_ssa_name (or_tmp, NULL);
  	  or_stmt = gimple_build_assign_with_ops (BIT_IOR_EXPR,
  						  new_or_tmp_name,
  						  or_tmp_name, addr_tmp_name);
            SSA_NAME_DEF_STMT (new_or_tmp_name) = or_stmt;
  	  gimple_seq_add_stmt (cond_expr_stmt_list, or_stmt);
            or_tmp_name = new_or_tmp_name;
          }
        else
          or_tmp_name = addr_tmp_name;
  
      } /* end for i */
  
    mask_cst = build_int_cst (int_ptrsize_type, mask);
  
    /* create: and_tmp = or_tmp & mask  */
    and_tmp = create_tmp_var (int_ptrsize_type, "andmask" );
    add_referenced_var (and_tmp);
    and_tmp_name = make_ssa_name (and_tmp, NULL);
  
    and_stmt = gimple_build_assign_with_ops (BIT_AND_EXPR, and_tmp_name,
  					   or_tmp_name, mask_cst);
    SSA_NAME_DEF_STMT (and_tmp_name) = and_stmt;
    gimple_seq_add_stmt (cond_expr_stmt_list, and_stmt);
  
    /* Make and_tmp the left operand of the conditional test against zero.
       if and_tmp has a nonzero bit then some address is unaligned.  */
    ptrsize_zero = build_int_cst (int_ptrsize_type, 0);
    part_cond_expr = fold_build2 (EQ_EXPR, boolean_type_node,
  				and_tmp_name, ptrsize_zero);
    if (*cond_expr)
      *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
  			      *cond_expr, part_cond_expr);
    else
      *cond_expr = part_cond_expr;
  }
  
  
  /* Function vect_vfa_segment_size.
  
     Create an expression that computes the size of segment
     that will be accessed for a data reference.  The functions takes into
     account that realignment loads may access one more vector.
  
     Input:
       DR: The data reference.
       LENGTH_FACTOR: segment length to consider.
  
     Return an expression whose value is the size of segment which will be
     accessed by DR.  */
  
  static tree
  vect_vfa_segment_size (struct data_reference *dr, tree length_factor)
  {
    tree segment_length;
  
    if (!compare_tree_int (DR_STEP (dr), 0))
      segment_length = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)));
    else
      segment_length = size_binop (MULT_EXPR,
                                   fold_convert (sizetype, DR_STEP (dr)),
                                   fold_convert (sizetype, length_factor));
  
    if (vect_supportable_dr_alignment (dr, false)
          == dr_explicit_realign_optimized)
      {
        tree vector_size = TYPE_SIZE_UNIT
  			  (STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr))));
  
        segment_length = size_binop (PLUS_EXPR, segment_length, vector_size);
      }
    return segment_length;
  }
  
  
  /* Function vect_create_cond_for_alias_checks.
  
     Create a conditional expression that represents the run-time checks for
     overlapping of address ranges represented by a list of data references
     relations passed as input.
  
     Input:
     COND_EXPR  - input conditional expression.  New conditions will be chained
                  with logical AND operation.
     LOOP_VINFO - field LOOP_VINFO_MAY_ALIAS_STMTS contains the list of ddrs
  	        to be checked.
  
     Output:
     COND_EXPR - conditional expression.
     COND_EXPR_STMT_LIST - statements needed to construct the conditional
                           expression.
  
  
     The returned value is the conditional expression to be used in the if
     statement that controls which version of the loop gets executed at runtime.
  */
  
  static void
  vect_create_cond_for_alias_checks (loop_vec_info loop_vinfo,
  				   tree * cond_expr,
  				   gimple_seq * cond_expr_stmt_list)
  {
    struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    VEC (ddr_p, heap) * may_alias_ddrs =
      LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo);
    int vect_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
    tree scalar_loop_iters = LOOP_VINFO_NITERS (loop_vinfo);
  
    ddr_p ddr;
    unsigned int i;
    tree part_cond_expr, length_factor;
  
    /* Create expression
       ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
       || (load_ptr_0 + load_segment_length_0) <= store_ptr_0))
       &&
       ...
       &&
       ((store_ptr_n + store_segment_length_n) <= load_ptr_n)
       || (load_ptr_n + load_segment_length_n) <= store_ptr_n))  */
  
    if (VEC_empty (ddr_p, may_alias_ddrs))
      return;
  
    FOR_EACH_VEC_ELT (ddr_p, may_alias_ddrs, i, ddr)
      {
        struct data_reference *dr_a, *dr_b;
        gimple dr_group_first_a, dr_group_first_b;
        tree addr_base_a, addr_base_b;
        tree segment_length_a, segment_length_b;
        gimple stmt_a, stmt_b;
        tree seg_a_min, seg_a_max, seg_b_min, seg_b_max;
  
        dr_a = DDR_A (ddr);
        stmt_a = DR_STMT (DDR_A (ddr));
        dr_group_first_a = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_a));
        if (dr_group_first_a)
          {
  	  stmt_a = dr_group_first_a;
  	  dr_a = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt_a));
  	}
  
        dr_b = DDR_B (ddr);
        stmt_b = DR_STMT (DDR_B (ddr));
        dr_group_first_b = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_b));
        if (dr_group_first_b)
          {
  	  stmt_b = dr_group_first_b;
  	  dr_b = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt_b));
  	}
  
        addr_base_a =
          vect_create_addr_base_for_vector_ref (stmt_a, cond_expr_stmt_list,
  					      NULL_TREE, loop);
        addr_base_b =
          vect_create_addr_base_for_vector_ref (stmt_b, cond_expr_stmt_list,
  					      NULL_TREE, loop);
  
        if (!operand_equal_p (DR_STEP (dr_a), DR_STEP (dr_b), 0))
  	length_factor = scalar_loop_iters;
        else
  	length_factor = size_int (vect_factor);
        segment_length_a = vect_vfa_segment_size (dr_a, length_factor);
        segment_length_b = vect_vfa_segment_size (dr_b, length_factor);
  
        if (vect_print_dump_info (REPORT_DR_DETAILS))
  	{
  	  fprintf (vect_dump,
  		   "create runtime check for data references ");
  	  print_generic_expr (vect_dump, DR_REF (dr_a), TDF_SLIM);
  	  fprintf (vect_dump, " and ");
  	  print_generic_expr (vect_dump, DR_REF (dr_b), TDF_SLIM);
  	}
  
        seg_a_min = addr_base_a;
        seg_a_max = fold_build_pointer_plus (addr_base_a, segment_length_a);
        if (tree_int_cst_compare (DR_STEP (dr_a), size_zero_node) < 0)
  	seg_a_min = seg_a_max, seg_a_max = addr_base_a;
  
        seg_b_min = addr_base_b;
        seg_b_max = fold_build_pointer_plus (addr_base_b, segment_length_b);
        if (tree_int_cst_compare (DR_STEP (dr_b), size_zero_node) < 0)
  	seg_b_min = seg_b_max, seg_b_max = addr_base_b;
  
        part_cond_expr =
        	fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
  	  fold_build2 (LE_EXPR, boolean_type_node, seg_a_max, seg_b_min),
  	  fold_build2 (LE_EXPR, boolean_type_node, seg_b_max, seg_a_min));
  
        if (*cond_expr)
  	*cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
  				  *cond_expr, part_cond_expr);
        else
  	*cond_expr = part_cond_expr;
      }
  
    if (vect_print_dump_info (REPORT_VECTORIZED_LOCATIONS))
      fprintf (vect_dump, "created %u versioning for alias checks.\n",
               VEC_length (ddr_p, may_alias_ddrs));
  }
  
  
  /* Function vect_loop_versioning.
  
     If the loop has data references that may or may not be aligned or/and
     has data reference relations whose independence was not proven then
     two versions of the loop need to be generated, one which is vectorized
     and one which isn't.  A test is then generated to control which of the
     loops is executed.  The test checks for the alignment of all of the
     data references that may or may not be aligned.  An additional
     sequence of runtime tests is generated for each pairs of DDRs whose
     independence was not proven.  The vectorized version of loop is
     executed only if both alias and alignment tests are passed.
  
     The test generated to check which version of loop is executed
     is modified to also check for profitability as indicated by the
     cost model initially.
  
     The versioning precondition(s) are placed in *COND_EXPR and
     *COND_EXPR_STMT_LIST.  If DO_VERSIONING is true versioning is
     also performed, otherwise only the conditions are generated.  */
  
  void
  vect_loop_versioning (loop_vec_info loop_vinfo, bool do_versioning,
  		      tree *cond_expr, gimple_seq *cond_expr_stmt_list)
  {
    struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    basic_block condition_bb;
    gimple_stmt_iterator gsi, cond_exp_gsi;
    basic_block merge_bb;
    basic_block new_exit_bb;
    edge new_exit_e, e;
    gimple orig_phi, new_phi;
    tree arg;
    unsigned prob = 4 * REG_BR_PROB_BASE / 5;
    gimple_seq gimplify_stmt_list = NULL;
    tree scalar_loop_iters = LOOP_VINFO_NITERS (loop_vinfo);
    int min_profitable_iters = 0;
    unsigned int th;
  
    /* Get profitability threshold for vectorized loop.  */
    min_profitable_iters = LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo);
  
    th = conservative_cost_threshold (loop_vinfo,
  				    min_profitable_iters);
  
    *cond_expr =
      fold_build2 (GT_EXPR, boolean_type_node, scalar_loop_iters,
   	         build_int_cst (TREE_TYPE (scalar_loop_iters), th));
  
    *cond_expr = force_gimple_operand (*cond_expr, cond_expr_stmt_list,
  				     false, NULL_TREE);
  
    if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo))
        vect_create_cond_for_align_checks (loop_vinfo, cond_expr,
  					 cond_expr_stmt_list);
  
    if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
      vect_create_cond_for_alias_checks (loop_vinfo, cond_expr,
  				       cond_expr_stmt_list);
  
    *cond_expr =
      fold_build2 (NE_EXPR, boolean_type_node, *cond_expr, integer_zero_node);
    *cond_expr =
      force_gimple_operand (*cond_expr, &gimplify_stmt_list, true, NULL_TREE);
    gimple_seq_add_seq (cond_expr_stmt_list, gimplify_stmt_list);
  
    /* If we only needed the extra conditions and a new loop copy
       bail out here.  */
    if (!do_versioning)
      return;
  
    initialize_original_copy_tables ();
    loop_version (loop, *cond_expr, &condition_bb,
  		prob, prob, REG_BR_PROB_BASE - prob, true);
    free_original_copy_tables();
  
    /* Loop versioning violates an assumption we try to maintain during
       vectorization - that the loop exit block has a single predecessor.
       After versioning, the exit block of both loop versions is the same
       basic block (i.e. it has two predecessors). Just in order to simplify
       following transformations in the vectorizer, we fix this situation
       here by adding a new (empty) block on the exit-edge of the loop,
       with the proper loop-exit phis to maintain loop-closed-form.  */
  
    merge_bb = single_exit (loop)->dest;
    gcc_assert (EDGE_COUNT (merge_bb->preds) == 2);
    new_exit_bb = split_edge (single_exit (loop));
    new_exit_e = single_exit (loop);
    e = EDGE_SUCC (new_exit_bb, 0);
  
    for (gsi = gsi_start_phis (merge_bb); !gsi_end_p (gsi); gsi_next (&gsi))
      {
        orig_phi = gsi_stmt (gsi);
        new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
  				  new_exit_bb);
        arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
        add_phi_arg (new_phi, arg, new_exit_e,
  		   gimple_phi_arg_location_from_edge (orig_phi, e));
        adjust_phi_and_debug_stmts (orig_phi, e, PHI_RESULT (new_phi));
      }
  
    /* End loop-exit-fixes after versioning.  */
  
    update_ssa (TODO_update_ssa);
    if (*cond_expr_stmt_list)
      {
        cond_exp_gsi = gsi_last_bb (condition_bb);
        gsi_insert_seq_before (&cond_exp_gsi, *cond_expr_stmt_list,
  			     GSI_SAME_STMT);
        *cond_expr_stmt_list = NULL;
      }
    *cond_expr = NULL_TREE;
  }
  
  