LCOV - code coverage report
Current view: top level - gcc - tree-vect-loop-manip.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 80.9 % 1958 1585
Test Date: 2026-11-14 16:39:50 Functions: 83.3 % 48 40
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Vectorizer Specific Loop Manipulations
       2              :    Copyright (C) 2003-2026 Free Software Foundation, Inc.
       3              :    Contributed by Dorit Naishlos <dorit@il.ibm.com>
       4              :    and Ira Rosen <irar@il.ibm.com>
       5              : 
       6              : This file is part of GCC.
       7              : 
       8              : GCC is free software; you can redistribute it and/or modify it under
       9              : the terms of the GNU General Public License as published by the Free
      10              : Software Foundation; either version 3, or (at your option) any later
      11              : version.
      12              : 
      13              : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      14              : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      15              : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      16              : for more details.
      17              : 
      18              : You should have received a copy of the GNU General Public License
      19              : along with GCC; see the file COPYING3.  If not see
      20              : <http://www.gnu.org/licenses/>.  */
      21              : 
      22              : #include "config.h"
      23              : #include "system.h"
      24              : #include "coretypes.h"
      25              : #include "backend.h"
      26              : #include "tree.h"
      27              : #include "gimple.h"
      28              : #include "cfghooks.h"
      29              : #include "tree-pass.h"
      30              : #include "ssa.h"
      31              : #include "fold-const.h"
      32              : #include "cfganal.h"
      33              : #include "gimplify.h"
      34              : #include "gimple-iterator.h"
      35              : #include "gimplify-me.h"
      36              : #include "tree-cfg.h"
      37              : #include "tree-ssa-loop-manip.h"
      38              : #include "tree-into-ssa.h"
      39              : #include "tree-ssa.h"
      40              : #include "cfgloop.h"
      41              : #include "tree-scalar-evolution.h"
      42              : #include "tree-vectorizer.h"
      43              : #include "tree-ssa-loop-ivopts.h"
      44              : #include "gimple-fold.h"
      45              : #include "tree-ssa-loop-niter.h"
      46              : #include "internal-fn.h"
      47              : #include "stor-layout.h"
      48              : #include "optabs-query.h"
      49              : #include "vec-perm-indices.h"
      50              : #include "insn-config.h"
      51              : #include "rtl.h"
      52              : #include "recog.h"
      53              : #include "langhooks.h"
      54              : #include "tree-vector-builder.h"
      55              : #include "optabs-tree.h"
      56              : 
      57              : 
      58              : /*************************************************************************
      59              :   Simple Loop Peeling Utilities
      60              : 
      61              :   Utilities to support loop peeling for vectorization purposes.
      62              :  *************************************************************************/
      63              : 
      64              : 
      65              : /* Renames the use *OP_P.  */
      66              : 
      67              : static void
      68       929464 : rename_use_op (use_operand_p op_p)
      69              : {
      70       929464 :   tree new_name;
      71              : 
      72       929464 :   if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
      73              :     return;
      74              : 
      75       927123 :   new_name = get_current_def (USE_FROM_PTR (op_p));
      76              : 
      77              :   /* Something defined outside of the loop.  */
      78       927123 :   if (!new_name)
      79              :     return;
      80              : 
      81              :   /* An ordinary ssa name defined in the loop.  */
      82              : 
      83       799966 :   SET_USE (op_p, new_name);
      84              : }
      85              : 
      86              : 
      87              : /* Renames the variables in basic block BB.  Allow renaming  of PHI arguments
      88              :    on edges incoming from outer-block header if RENAME_FROM_OUTER_LOOP is
      89              :    true.  */
      90              : 
      91              : static void
      92       113030 : rename_variables_in_bb (basic_block bb, bool rename_from_outer_loop)
      93              : {
      94       113030 :   gimple *stmt;
      95       113030 :   use_operand_p use_p;
      96       113030 :   ssa_op_iter iter;
      97       113030 :   edge e;
      98       113030 :   edge_iterator ei;
      99       113030 :   class loop *loop = bb->loop_father;
     100       113030 :   class loop *outer_loop = NULL;
     101              : 
     102       113030 :   if (rename_from_outer_loop)
     103              :     {
     104          843 :       gcc_assert (loop);
     105          843 :       outer_loop = loop_outer (loop);
     106              :     }
     107              : 
     108       758156 :   for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
     109       532096 :        gsi_next (&gsi))
     110              :     {
     111       532096 :       stmt = gsi_stmt (gsi);
     112      1306184 :       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
     113       774088 :         rename_use_op (use_p);
     114              :     }
     115              : 
     116       230255 :   FOR_EACH_EDGE (e, ei, bb->preds)
     117              :     {
     118       117225 :       if (!flow_bb_inside_loop_p (loop, e->src))
     119              :         {
     120        36036 :           if (!rename_from_outer_loop)
     121        35768 :             continue;
     122          268 :           if (e->src != outer_loop->header)
     123              :             {
     124          154 :               if (outer_loop->inner->next)
     125              :                 {
     126              :                   /* If outer_loop has 2 inner loops, allow there to
     127              :                      be an extra basic block which decides which of the
     128              :                      two loops to use using LOOP_VECTORIZED.  */
     129          150 :                   if (!single_pred_p (e->src)
     130           22 :                       || single_pred (e->src) != outer_loop->header)
     131          128 :                     continue;
     132              :                 }
     133              :             }
     134              :         }
     135       187111 :       for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
     136       105782 :            gsi_next (&gsi))
     137       105782 :         rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (gsi.phi (), e));
     138              :     }
     139       113030 : }
     140              : 
     141              : 
     142              : struct adjust_info
     143              : {
     144              :   tree from, to;
     145              :   basic_block bb;
     146              : };
     147              : 
     148              : /* A stack of values to be adjusted in debug stmts.  We have to
     149              :    process them LIFO, so that the closest substitution applies.  If we
     150              :    processed them FIFO, without the stack, we might substitute uses
     151              :    with a PHI DEF that would soon become non-dominant, and when we got
     152              :    to the suitable one, it wouldn't have anything to substitute any
     153              :    more.  */
     154              : static vec<adjust_info, va_heap> adjust_vec;
     155              : 
     156              : /* Adjust any debug stmts that referenced AI->from values to use the
     157              :    loop-closed AI->to, if the references are dominated by AI->bb and
     158              :    not by the definition of AI->from.  */
     159              : 
     160              : static void
     161        79163 : adjust_debug_stmts_now (adjust_info *ai)
     162              : {
     163        79163 :   basic_block bbphi = ai->bb;
     164        79163 :   tree orig_def = ai->from;
     165        79163 :   tree new_def = ai->to;
     166        79163 :   imm_use_iterator imm_iter;
     167        79163 :   gimple *stmt;
     168        79163 :   basic_block bbdef = gimple_bb (SSA_NAME_DEF_STMT (orig_def));
     169              : 
     170        79163 :   gcc_assert (dom_info_available_p (CDI_DOMINATORS));
     171              : 
     172              :   /* Adjust any debug stmts that held onto non-loop-closed
     173              :      references.  */
     174       311783 :   FOR_EACH_IMM_USE_STMT (stmt, imm_iter, orig_def)
     175              :     {
     176       232620 :       use_operand_p use_p;
     177       232620 :       basic_block bbuse;
     178              : 
     179       232620 :       if (!is_gimple_debug (stmt))
     180       174776 :         continue;
     181              : 
     182        57844 :       gcc_assert (gimple_debug_bind_p (stmt));
     183              : 
     184        57844 :       bbuse = gimple_bb (stmt);
     185              : 
     186        57844 :       if ((bbuse == bbphi
     187        57844 :            || dominated_by_p (CDI_DOMINATORS, bbuse, bbphi))
     188        59878 :           && !(bbuse == bbdef
     189         1017 :                || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef)))
     190              :         {
     191            0 :           if (new_def)
     192            0 :             FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
     193            0 :               SET_USE (use_p, new_def);
     194              :           else
     195              :             {
     196            0 :               gimple_debug_bind_reset_value (stmt);
     197            0 :               update_stmt (stmt);
     198              :             }
     199              :         }
     200        79163 :     }
     201        79163 : }
     202              : 
     203              : /* Adjust debug stmts as scheduled before.  */
     204              : 
     205              : static void
     206        34657 : adjust_vec_debug_stmts (void)
     207              : {
     208        34657 :   if (!MAY_HAVE_DEBUG_BIND_STMTS)
     209              :     return;
     210              : 
     211        12821 :   gcc_assert (adjust_vec.exists ());
     212              : 
     213        91873 :   while (!adjust_vec.is_empty ())
     214              :     {
     215        79052 :       adjust_debug_stmts_now (&adjust_vec.last ());
     216        79052 :       adjust_vec.pop ();
     217              :     }
     218              : }
     219              : 
     220              : /* Adjust any debug stmts that referenced FROM values to use the
     221              :    loop-closed TO, if the references are dominated by BB and not by
     222              :    the definition of FROM.  If adjust_vec is non-NULL, adjustments
     223              :    will be postponed until adjust_vec_debug_stmts is called.  */
     224              : 
     225              : static void
     226       108944 : adjust_debug_stmts (tree from, tree to, basic_block bb)
     227              : {
     228       108944 :   adjust_info ai;
     229              : 
     230       108944 :   if (MAY_HAVE_DEBUG_BIND_STMTS
     231       108944 :       && TREE_CODE (from) == SSA_NAME
     232        98845 :       && ! SSA_NAME_IS_DEFAULT_DEF (from)
     233       206325 :       && ! virtual_operand_p (from))
     234              :     {
     235        79163 :       ai.from = from;
     236        79163 :       ai.to = to;
     237        79163 :       ai.bb = bb;
     238              : 
     239        79163 :       if (adjust_vec.exists ())
     240        79052 :         adjust_vec.safe_push (ai);
     241              :       else
     242          111 :         adjust_debug_stmts_now (&ai);
     243              :     }
     244       108944 : }
     245              : 
     246              : /* Change E's phi arg in UPDATE_PHI to NEW_DEF, and record information
     247              :    to adjust any debug stmts that referenced the old phi arg,
     248              :    presumably non-loop-closed references left over from other
     249              :    transformations.  */
     250              : 
     251              : static void
     252       222937 : adjust_phi_and_debug_stmts (gimple *update_phi, edge e, tree new_def)
     253              : {
     254       222937 :   tree orig_def = PHI_ARG_DEF_FROM_EDGE (update_phi, e);
     255              : 
     256       222937 :   gcc_assert (TREE_CODE (orig_def) != SSA_NAME
     257              :               || orig_def != new_def);
     258              : 
     259       222937 :   SET_PHI_ARG_DEF (update_phi, e->dest_idx, new_def);
     260              : 
     261       222937 :   if (MAY_HAVE_DEBUG_BIND_STMTS)
     262        85602 :     adjust_debug_stmts (orig_def, PHI_RESULT (update_phi),
     263              :                         gimple_bb (update_phi));
     264       222937 : }
     265              : 
     266              : /* Define one loop rgroup control CTRL from loop LOOP.  INIT_CTRL is the value
     267              :    that the control should have during the first iteration and NEXT_CTRL is the
     268              :    value that it should have on subsequent iterations.  */
     269              : 
     270              : static void
     271           92 : vect_set_loop_control (class loop *loop, tree ctrl, tree init_ctrl,
     272              :                        tree next_ctrl)
     273              : {
     274           92 :   gphi *phi = create_phi_node (ctrl, loop->header);
     275           92 :   add_phi_arg (phi, init_ctrl, loop_preheader_edge (loop), UNKNOWN_LOCATION);
     276           92 :   add_phi_arg (phi, next_ctrl, loop_latch_edge (loop), UNKNOWN_LOCATION);
     277           92 : }
     278              : 
     279              : /* Add SEQ to the end of LOOP's preheader block.  */
     280              : 
     281              : static void
     282           24 : add_preheader_seq (class loop *loop, gimple_seq seq)
     283              : {
     284           24 :   if (seq)
     285              :     {
     286           19 :       edge pe = loop_preheader_edge (loop);
     287           19 :       basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, seq);
     288           19 :       gcc_assert (!new_bb);
     289              :     }
     290           24 : }
     291              : 
     292              : /* Add SEQ to the beginning of LOOP's header block.  */
     293              : 
     294              : static void
     295            0 : add_header_seq (class loop *loop, gimple_seq seq)
     296              : {
     297            0 :   if (seq)
     298              :     {
     299            0 :       gimple_stmt_iterator gsi = gsi_after_labels (loop->header);
     300            0 :       gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
     301              :     }
     302            0 : }
     303              : 
     304              : /* Return true if the target can interleave elements of two vectors.
     305              :    OFFSET is 0 if the first half of the vectors should be interleaved
     306              :    or 1 if the second half should.  When returning true, store the
     307              :    associated permutation in INDICES.  */
     308              : 
     309              : static bool
     310            0 : interleave_supported_p (vec_perm_indices *indices, tree vectype,
     311              :                         unsigned int offset)
     312              : {
     313            0 :   poly_uint64 nelts = TYPE_VECTOR_SUBPARTS (vectype);
     314            0 :   poly_uint64 base = exact_div (nelts, 2) * offset;
     315            0 :   vec_perm_builder sel (nelts, 2, 3);
     316            0 :   for (unsigned int i = 0; i < 3; ++i)
     317              :     {
     318            0 :       sel.quick_push (base + i);
     319            0 :       sel.quick_push (base + i + nelts);
     320              :     }
     321            0 :   indices->new_vector (sel, 2, nelts);
     322            0 :   return can_vec_perm_const_p (TYPE_MODE (vectype), TYPE_MODE (vectype),
     323            0 :                                *indices);
     324            0 : }
     325              : 
     326              : /* Check if its possible to use permutes to define the masks in DEST_RGM using
     327              :    the masks in SRC_RGM, given that the former has twice as many masks as the
     328              :    latter.  Return true on success.
     329              : 
     330              :    Optionally, if SEQ is non-null add new statements for the permutation to SEQ.
     331              :    Additionally, if SRC_MASKS and DST_MASKS are defined, use these instead
     332              :    of the masks from SRC_RGM and DST_RGM.  */
     333              : 
     334              : static bool
     335            0 : vect_maybe_permute_loop_masks (gimple_seq *seq,
     336              :                                rgroup_controls *dest_rgm,
     337              :                                rgroup_controls *src_rgm,
     338              :                                vec<tree> dst_controls,
     339              :                                vec<tree> src_controls)
     340              : {
     341            0 :   tree src_masktype = src_rgm->type;
     342            0 :   tree dest_masktype = dest_rgm->type;
     343            0 :   if (!src_masktype && !seq)
     344              :     return false;
     345            0 :   machine_mode src_mode = TYPE_MODE (src_masktype);
     346            0 :   insn_code icode1, icode2;
     347              : 
     348            0 :   if (dest_rgm->max_nscalars_per_iter <= src_rgm->max_nscalars_per_iter
     349            0 :       && (icode1 = optab_handler (vec_unpacku_hi_optab,
     350              :                                   src_mode)) != CODE_FOR_nothing
     351            0 :       && (icode2 = optab_handler (vec_unpacku_lo_optab,
     352              :                                   src_mode)) != CODE_FOR_nothing)
     353              :     {
     354              :       /* Unpacking the source masks gives at least as many mask bits as
     355              :          we need.  We can then VIEW_CONVERT any excess bits away.  */
     356            0 :       machine_mode dest_mode = insn_data[icode1].operand[0].mode;
     357            0 :       gcc_assert (dest_mode == insn_data[icode2].operand[0].mode);
     358            0 :       tree unpack_masktype = vect_halve_mask_nunits (src_masktype, dest_mode);
     359            0 :       if (!seq)
     360              :         return true;
     361            0 :       for (unsigned int i = 0; i < dst_controls.length (); ++i)
     362              :         {
     363            0 :           tree src = src_controls[i / 2];
     364            0 :           tree dest = dst_controls[i];
     365            0 :           tree_code code = ((i & 1) == (BYTES_BIG_ENDIAN ? 0 : 1)
     366            0 :                             ? VEC_UNPACK_HI_EXPR
     367              :                             : VEC_UNPACK_LO_EXPR);
     368            0 :           gassign *stmt;
     369            0 :           if (dest_masktype == unpack_masktype)
     370            0 :             stmt = gimple_build_assign (dest, code, src);
     371              :           else
     372              :             {
     373            0 :               tree temp = make_ssa_name (unpack_masktype);
     374            0 :               stmt = gimple_build_assign (temp, code, src);
     375            0 :               gimple_seq_add_stmt (seq, stmt);
     376            0 :               stmt = gimple_build_assign (dest, VIEW_CONVERT_EXPR,
     377              :                                           build1 (VIEW_CONVERT_EXPR,
     378              :                                                   dest_masktype, temp));
     379              :             }
     380            0 :           gimple_seq_add_stmt (seq, stmt);
     381              :         }
     382              :       return true;
     383              :     }
     384            0 :   vec_perm_indices indices[2];
     385            0 :   if (dest_masktype == src_masktype
     386            0 :       && interleave_supported_p (&indices[0], src_masktype, 0)
     387            0 :       && interleave_supported_p (&indices[1], src_masktype, 1))
     388              :     {
     389            0 :       if (!seq)
     390              :         return true;
     391              :       /* The destination requires twice as many mask bits as the source, so
     392              :          we can use interleaving permutes to double up the number of bits.  */
     393              :       tree masks[2];
     394            0 :       for (unsigned int i = 0; i < 2; ++i)
     395            0 :         masks[i] = vect_gen_perm_mask_checked (src_masktype, indices[i]);
     396            0 :       for (unsigned int i = 0; i < dst_controls.length (); ++i)
     397              :         {
     398            0 :           tree src = src_controls[i / 2];
     399            0 :           tree dest = dst_controls[i];
     400            0 :           gimple *stmt = gimple_build_assign (dest, VEC_PERM_EXPR,
     401            0 :                                               src, src, masks[i & 1]);
     402            0 :           gimple_seq_add_stmt (seq, stmt);
     403              :         }
     404              :       return true;
     405              :     }
     406              :   return false;
     407            0 : }
     408              : 
     409              : static bool
     410            0 : vect_maybe_permute_loop_masks (gimple_seq *seq,
     411              :                                rgroup_controls *dest_rgm,
     412              :                                rgroup_controls *src_rgm)
     413              : {
     414            0 :   return vect_maybe_permute_loop_masks (seq, dest_rgm, src_rgm,
     415            0 :                                         dest_rgm->controls, src_rgm->controls);
     416              : }
     417              : 
     418              : /* Populate DEST_RGM->controls, given that they should add up to STEP.
     419              : 
     420              :      STEP = MIN_EXPR <ivtmp_34, VF>;
     421              : 
     422              :      First length (MIN (X, VF/N)):
     423              :        loop_len_15 = MIN_EXPR <STEP, VF/N>;
     424              : 
     425              :      Second length:
     426              :        tmp = STEP - loop_len_15;
     427              :        loop_len_16 = MIN (tmp, VF/N);
     428              : 
     429              :      Third length:
     430              :        tmp2 = tmp - loop_len_16;
     431              :        loop_len_17 = MIN (tmp2, VF/N);
     432              : 
     433              :      Last length:
     434              :        loop_len_18 = tmp2 - loop_len_17;
     435              : */
     436              : 
     437              : static void
     438            0 : vect_adjust_loop_lens_control (tree iv_type, gimple_seq *seq,
     439              :                                rgroup_controls *dest_rgm, tree step)
     440              : {
     441            0 :   tree ctrl_type = dest_rgm->type;
     442            0 :   poly_uint64 nitems_per_ctrl
     443            0 :     = TYPE_VECTOR_SUBPARTS (ctrl_type) * dest_rgm->factor;
     444            0 :   tree length_limit = build_int_cst (iv_type, nitems_per_ctrl);
     445              : 
     446            0 :   for (unsigned int i = 0; i < dest_rgm->controls.length (); ++i)
     447              :     {
     448            0 :       tree ctrl = dest_rgm->controls[i];
     449            0 :       if (i == 0)
     450              :         {
     451              :           /* First iteration: MIN (X, VF/N) capped to the range [0, VF/N].  */
     452            0 :           gassign *assign
     453            0 :             = gimple_build_assign (ctrl, MIN_EXPR, step, length_limit);
     454            0 :           gimple_seq_add_stmt (seq, assign);
     455              :         }
     456            0 :       else if (i == dest_rgm->controls.length () - 1)
     457              :         {
     458              :           /* Last iteration: Remain capped to the range [0, VF/N].  */
     459            0 :           gassign *assign = gimple_build_assign (ctrl, MINUS_EXPR, step,
     460            0 :                                                  dest_rgm->controls[i - 1]);
     461            0 :           gimple_seq_add_stmt (seq, assign);
     462              :         }
     463              :       else
     464              :         {
     465              :           /* (MIN (remain, VF*I/N)) capped to the range [0, VF/N].  */
     466            0 :           step = gimple_build (seq, MINUS_EXPR, iv_type, step,
     467            0 :                                dest_rgm->controls[i - 1]);
     468            0 :           gassign *assign
     469            0 :             = gimple_build_assign (ctrl, MIN_EXPR, step, length_limit);
     470            0 :           gimple_seq_add_stmt (seq, assign);
     471              :         }
     472              :     }
     473            0 : }
     474              : 
     475              : /* Stores the standard position for induction variable increment in belonging to
     476              :    LOOP_EXIT (just before the exit condition of the given exit to BSI.
     477              :    INSERT_AFTER is set to true if the increment should be inserted after
     478              :    *BSI.  */
     479              : 
     480              : void
     481           99 : vect_iv_increment_position (edge loop_exit, gimple_stmt_iterator *bsi,
     482              :                             bool *insert_after)
     483              : {
     484           99 :   basic_block bb = loop_exit->src;
     485           99 :   *bsi = gsi_last_bb (bb);
     486           99 :   *insert_after = false;
     487           99 : }
     488              : 
     489              : /* Get the virtual operand live on E.  The precondition on this is valid
     490              :    immediate dominators and an actual virtual definition dominating E.  */
     491              : /* ???  Costly band-aid.  For the use in question we can populate a
     492              :    live-on-exit/end-of-BB virtual operand when copying stmts.  */
     493              : 
     494              : static tree
     495           39 : get_live_virtual_operand_on_edge (edge e)
     496              : {
     497           39 :   basic_block bb = e->src;
     498           67 :   do
     499              :     {
     500          329 :       for (auto gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
     501              :         {
     502          256 :           gimple *stmt = gsi_stmt (gsi);
     503          485 :           if (gimple_vdef (stmt))
     504           39 :             return gimple_vdef (stmt);
     505          419 :           if (gimple_vuse (stmt))
     506              :             return gimple_vuse (stmt);
     507              :         }
     508           20 :       if (gphi *vphi = get_virtual_phi (bb))
     509            6 :         return gimple_phi_result (vphi);
     510           14 :       bb = get_immediate_dominator (CDI_DOMINATORS, bb);
     511           14 :     }
     512              :   while (1);
     513              : }
     514              : 
     515              : /* Helper for vect_set_loop_condition_partial_vectors.  Generate definitions
     516              :    for all the rgroup controls in RGC and return a control that is nonzero
     517              :    when the loop needs to iterate.  Add any new preheader statements to
     518              :    PREHEADER_SEQ.  Use LOOP_COND_GSI to insert code before the exit gcond.
     519              : 
     520              :    RGC belongs to loop LOOP.  The loop originally iterated NITERS
     521              :    times and has been vectorized according to LOOP_VINFO.
     522              : 
     523              :    If NITERS_SKIP is nonnull, the first iteration of the vectorized loop
     524              :    starts with NITERS_SKIP dummy iterations of the scalar loop before
     525              :    the real work starts.  The mask elements for these dummy iterations
     526              :    must be 0, to ensure that the extra iterations do not have an effect.
     527              : 
     528              :    It is known that:
     529              : 
     530              :      NITERS * RGC->max_nscalars_per_iter * RGC->factor
     531              : 
     532              :    does not overflow.  However, MIGHT_WRAP_P says whether an induction
     533              :    variable that starts at 0 and has step:
     534              : 
     535              :      VF * RGC->max_nscalars_per_iter * RGC->factor
     536              : 
     537              :    might overflow before hitting a value above:
     538              : 
     539              :      (NITERS + NITERS_SKIP) * RGC->max_nscalars_per_iter * RGC->factor
     540              : 
     541              :    This means that we cannot guarantee that such an induction variable
     542              :    would ever hit a value that produces a set of all-false masks or zero
     543              :    lengths for RGC.
     544              : 
     545              :    Note: the cost of the code generated by this function is modeled
     546              :    by vect_estimate_min_profitable_iters, so changes here may need
     547              :    corresponding changes there.  */
     548              : 
     549              : static tree
     550            0 : vect_set_loop_controls_directly (class loop *loop, loop_vec_info loop_vinfo,
     551              :                                  gimple_seq *preheader_seq,
     552              :                                  gimple_seq *header_seq,
     553              :                                  gimple_stmt_iterator loop_cond_gsi,
     554              :                                  rgroup_controls *rgc, tree niters,
     555              :                                  tree niters_skip, bool might_wrap_p,
     556              :                                  tree *iv_step, tree *compare_step)
     557              : {
     558            0 :   tree compare_type = LOOP_VINFO_RGROUP_COMPARE_TYPE (loop_vinfo);
     559            0 :   tree iv_type = LOOP_VINFO_RGROUP_IV_TYPE (loop_vinfo);
     560            0 :   bool use_masks_p = LOOP_VINFO_FULLY_MASKED_P (loop_vinfo);
     561              : 
     562            0 :   tree ctrl_type = rgc->type;
     563            0 :   unsigned int nitems_per_iter = rgc->max_nscalars_per_iter * rgc->factor;
     564            0 :   poly_uint64 nitems_per_ctrl = TYPE_VECTOR_SUBPARTS (ctrl_type) * rgc->factor;
     565            0 :   tree length_limit = NULL_TREE;
     566              :   /* For length, we need length_limit to ensure length in range.  */
     567            0 :   if (!use_masks_p)
     568            0 :     length_limit = build_int_cst (compare_type, nitems_per_ctrl);
     569              : 
     570              :   /* Calculate the maximum number of item values that the rgroup
     571              :      handles in total, the number that it handles for each iteration
     572              :      of the vector loop, and the number that it should skip during the
     573              :      first iteration of the vector loop.  */
     574            0 :   tree nitems_total = niters;
     575            0 :   tree nitems_vf
     576            0 :     = build_int_cst (iv_type, LOOP_VINFO_VECT_FACTOR (loop_vinfo));
     577            0 :   tree nitems_step
     578            0 :     = LOOP_VINFO_IV_INCREMENT_INVARIANT_P (loop_vinfo)
     579            0 :         ? gimple_convert (preheader_seq, iv_type,
     580              :                           LOOP_VINFO_IV_INCREMENT (loop_vinfo))
     581            0 :         : gimple_convert (&loop_cond_gsi, true, GSI_SAME_STMT, UNKNOWN_LOCATION,
     582              :                           iv_type, LOOP_VINFO_IV_INCREMENT (loop_vinfo));
     583              : 
     584            0 :   tree nitems_skip = niters_skip;
     585            0 :   if (nitems_per_iter != 1)
     586              :     {
     587              :       /* We checked before setting LOOP_VINFO_USING_PARTIAL_VECTORS_P that
     588              :          these multiplications don't overflow.  */
     589            0 :       tree compare_factor = build_int_cst (compare_type, nitems_per_iter);
     590            0 :       tree iv_factor = build_int_cst (iv_type, nitems_per_iter);
     591            0 :       nitems_total = gimple_build (preheader_seq, MULT_EXPR, compare_type,
     592              :                                    nitems_total, compare_factor);
     593            0 :       nitems_vf = gimple_build (preheader_seq, MULT_EXPR, iv_type,
     594              :                                   nitems_vf, iv_factor);
     595            0 :       nitems_step = LOOP_VINFO_IV_INCREMENT_INVARIANT_P (loop_vinfo)
     596            0 :                       ? gimple_build (preheader_seq, MULT_EXPR, iv_type,
     597              :                                       nitems_step, iv_factor)
     598            0 :                       : gimple_build (&loop_cond_gsi, true, GSI_SAME_STMT,
     599              :                                       UNKNOWN_LOCATION, MULT_EXPR, iv_type,
     600              :                                       nitems_step, iv_factor);
     601            0 :       if (nitems_skip)
     602            0 :         nitems_skip = gimple_build (preheader_seq, MULT_EXPR, compare_type,
     603              :                                     nitems_skip, compare_factor);
     604              :     }
     605              : 
     606              :   /* Create an induction variable that counts the number of items
     607              :      processed.  */
     608            0 :   tree index_before_incr, index_after_incr;
     609            0 :   gimple_stmt_iterator incr_gsi;
     610            0 :   bool insert_after;
     611            0 :   standard_iv_increment_position (loop, &incr_gsi, &insert_after);
     612              : 
     613            0 :   if (LOOP_VINFO_USING_DECREMENTING_IV_P (loop_vinfo))
     614              :     {
     615              :       /* Create an IV that counts down from niters_total and whose step
     616              :          is the (variable) amount processed in the current iteration:
     617              :            ...
     618              :            _10 = (unsigned long) count_12(D);
     619              :            ...
     620              :            # ivtmp_9 = PHI <ivtmp_35(6), _10(5)>
     621              :            _36 = (MIN_EXPR | SELECT_VL) <ivtmp_9, POLY_INT_CST [4, 4]>;
     622              :            ...
     623              :            vect__4.8_28 = .LEN_LOAD (_17, 32B, _36, 0);
     624              :            ...
     625              :            ivtmp_35 = ivtmp_9 - POLY_INT_CST [4, 4];
     626              :            ...
     627              :            if (ivtmp_9 > POLY_INT_CST [4, 4])
     628              :              goto <bb 4>; [83.33%]
     629              :            else
     630              :              goto <bb 5>; [16.67%]
     631              :       */
     632            0 :       nitems_total = gimple_convert (preheader_seq, iv_type, nitems_total);
     633            0 :       tree step = rgc->controls.length () == 1 ? rgc->controls[0]
     634            0 :                                                : make_ssa_name (iv_type);
     635              :       /* Create decrement IV.  */
     636            0 :       if (LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo))
     637              :         {
     638            0 :           create_iv (nitems_total, MINUS_EXPR, step, NULL_TREE, loop, &incr_gsi,
     639              :                      insert_after, &index_before_incr, &index_after_incr);
     640            0 :           tree vectype = build_zero_cst (rgc->type);
     641            0 :           tree len = gimple_build (header_seq, IFN_SELECT_VL, iv_type,
     642              :                                    index_before_incr, nitems_vf,
     643              :                                    vectype);
     644            0 :           gimple_seq_add_stmt (header_seq, gimple_build_assign (step, len));
     645            0 :           len = gimple_convert (header_seq, sizetype, len);
     646              : 
     647              :           /* Remove the previous initialization of IV_INCREMENT to VARYING.  */
     648            0 :           gimple *varying_def
     649            0 :             = SSA_NAME_DEF_STMT (LOOP_VINFO_IV_INCREMENT (loop_vinfo));
     650            0 :           auto def_gsi = gsi_for_stmt (varying_def);
     651            0 :           gsi_remove (&def_gsi, true);
     652              : 
     653              :           /* Set the LOOP_VINFO_IV_INCREMENT to be len.  */
     654            0 :           gassign* assign_iv_increment
     655            0 :             = gimple_build_assign (LOOP_VINFO_IV_INCREMENT (loop_vinfo), len);
     656            0 :           gimple_seq_add_stmt (header_seq, assign_iv_increment);
     657              :         }
     658              :       else
     659              :         {
     660            0 :           create_iv (nitems_total, MINUS_EXPR, nitems_step, NULL_TREE, loop,
     661              :                      &incr_gsi, insert_after, &index_before_incr,
     662              :                      &index_after_incr);
     663            0 :           gimple_seq_add_stmt (header_seq,
     664            0 :                                gimple_build_assign (step, MIN_EXPR,
     665              :                                                     index_before_incr,
     666              :                                                     nitems_step));
     667              :         }
     668            0 :       *iv_step = step;
     669            0 :       *compare_step = nitems_vf;
     670            0 :       return LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo) ? index_after_incr
     671            0 :                                                        : index_before_incr;
     672              :     }
     673              : 
     674              :   /* Create increment IV.  */
     675            0 :   create_iv (build_int_cst (iv_type, 0), PLUS_EXPR, nitems_step, NULL_TREE,
     676              :              loop, &incr_gsi, insert_after, &index_before_incr,
     677              :              &index_after_incr,
     678            0 :              LOOP_VINFO_IV_INCREMENT_INVARIANT_P (loop_vinfo));
     679              : 
     680            0 :   tree zero_index = build_int_cst (compare_type, 0);
     681            0 :   tree test_index, test_limit, first_limit;
     682            0 :   if (might_wrap_p)
     683              :     {
     684              :       /* In principle the loop should stop iterating once the incremented
     685              :          IV reaches a value greater than or equal to:
     686              : 
     687              :            NITEMS_TOTAL +[infinite-prec] NITEMS_SKIP
     688              : 
     689              :          However, there's no guarantee that this addition doesn't overflow
     690              :          the comparison type, or that the IV hits a value above it before
     691              :          wrapping around.  We therefore adjust the limit down by one
     692              :          IV step:
     693              : 
     694              :            (NITEMS_TOTAL +[infinite-prec] NITEMS_SKIP)
     695              :            -[infinite-prec] NITEMS_STEP
     696              : 
     697              :          and compare the IV against this limit _before_ incrementing it.
     698              :          Since the comparison type is unsigned, we actually want the
     699              :          subtraction to saturate at zero:
     700              : 
     701              :            (NITEMS_TOTAL +[infinite-prec] NITEMS_SKIP)
     702              :            -[sat] NITEMS_STEP
     703              : 
     704              :          And since NITEMS_SKIP < NITEMS_STEP, we can reassociate this as:
     705              : 
     706              :            NITEMS_TOTAL -[sat] (NITEMS_STEP - NITEMS_SKIP)
     707              : 
     708              :          where the rightmost subtraction can be done directly in
     709              :          COMPARE_TYPE.  */
     710            0 :       test_index = index_before_incr;
     711            0 :       tree adjust = gimple_convert (preheader_seq, compare_type,
     712              :                                     nitems_vf);
     713            0 :       if (nitems_skip)
     714            0 :         adjust = gimple_build (preheader_seq, MINUS_EXPR, compare_type,
     715              :                                adjust, nitems_skip);
     716            0 :       test_limit = gimple_build (preheader_seq, MAX_EXPR, compare_type,
     717              :                                  nitems_total, adjust);
     718            0 :       test_limit = gimple_build (preheader_seq, MINUS_EXPR, compare_type,
     719              :                                  test_limit, adjust);
     720              : 
     721              :       /* Get a safe limit for the first iteration.  */
     722            0 :       if (nitems_skip)
     723              :         {
     724              :           /* The first vector iteration can handle at most NITEMS_STEP
     725              :              items.  NITEMS_STEP <= CONST_LIMIT, and adding
     726              :              NITEMS_SKIP to that cannot overflow.  */
     727            0 :           tree const_limit = build_int_cst (compare_type,
     728            0 :                                             LOOP_VINFO_VECT_FACTOR (loop_vinfo)
     729            0 :                                             * nitems_per_iter);
     730            0 :           first_limit = gimple_build (preheader_seq, MIN_EXPR, compare_type,
     731              :                                       nitems_total, const_limit);
     732            0 :           first_limit = gimple_build (preheader_seq, PLUS_EXPR, compare_type,
     733              :                                       first_limit, nitems_skip);
     734              :         }
     735              :       else
     736              :         /* For the first iteration it doesn't matter whether the IV hits
     737              :            a value above NITEMS_TOTAL.  That only matters for the latch
     738              :            condition.  */
     739              :         first_limit = nitems_total;
     740              :     }
     741              :   else
     742              :     {
     743              :       /* Test the incremented IV, which will always hit a value above
     744              :          the bound before wrapping.  */
     745            0 :       test_index = index_after_incr;
     746            0 :       test_limit = nitems_total;
     747            0 :       if (nitems_skip)
     748            0 :         test_limit = gimple_build (preheader_seq, PLUS_EXPR, compare_type,
     749              :                                    test_limit, nitems_skip);
     750              : 
     751              :       first_limit = test_limit;
     752              :     }
     753              : 
     754              :   /* Convert the IV value to the comparison type (either a no-op or
     755              :      a demotion).  */
     756            0 :   gimple_seq test_seq = NULL;
     757            0 :   test_index = gimple_convert (&test_seq, compare_type, test_index);
     758            0 :   gsi_insert_seq_after (&incr_gsi, test_seq, GSI_NEW_STMT);
     759              : 
     760              :   /* Provide a definition of each control in the group.  */
     761            0 :   tree next_ctrl = NULL_TREE;
     762            0 :   tree ctrl;
     763            0 :   unsigned int i;
     764            0 :   FOR_EACH_VEC_ELT_REVERSE (rgc->controls, i, ctrl)
     765              :     {
     766              :       /* Previous controls will cover BIAS items.  This control covers the
     767              :          next batch.  */
     768            0 :       poly_uint64 bias = nitems_per_ctrl * i;
     769            0 :       tree bias_tree = build_int_cst (compare_type, bias);
     770              : 
     771              :       /* See whether the first iteration of the vector loop is known
     772              :          to have a full control.  */
     773            0 :       poly_uint64 const_limit;
     774            0 :       bool first_iteration_full
     775            0 :         = (poly_int_tree_p (first_limit, &const_limit)
     776            0 :            && known_ge (const_limit, (i + 1) * nitems_per_ctrl));
     777              : 
     778              :       /* Rather than have a new IV that starts at BIAS and goes up to
     779              :          TEST_LIMIT, prefer to use the same 0-based IV for each control
     780              :          and adjust the bound down by BIAS.  */
     781            0 :       tree this_test_limit = test_limit;
     782            0 :       if (i != 0)
     783              :         {
     784            0 :           this_test_limit = gimple_build (preheader_seq, MAX_EXPR,
     785              :                                           compare_type, this_test_limit,
     786              :                                           bias_tree);
     787            0 :           this_test_limit = gimple_build (preheader_seq, MINUS_EXPR,
     788              :                                           compare_type, this_test_limit,
     789              :                                           bias_tree);
     790              :         }
     791              : 
     792              :       /* Create the initial control.  First include all items that
     793              :          are within the loop limit.  */
     794            0 :       tree init_ctrl = NULL_TREE;
     795            0 :       if (!first_iteration_full)
     796              :         {
     797            0 :           tree start, end;
     798            0 :           if (first_limit == test_limit)
     799              :             {
     800              :               /* Use a natural test between zero (the initial IV value)
     801              :                  and the loop limit.  The "else" block would be valid too,
     802              :                  but this choice can avoid the need to load BIAS_TREE into
     803              :                  a register.  */
     804              :               start = zero_index;
     805              :               end = this_test_limit;
     806              :             }
     807              :           else
     808              :             {
     809              :               /* FIRST_LIMIT is the maximum number of items handled by the
     810              :                  first iteration of the vector loop.  Test the portion
     811              :                  associated with this control.  */
     812            0 :               start = bias_tree;
     813            0 :               end = first_limit;
     814              :             }
     815              : 
     816            0 :           if (use_masks_p)
     817            0 :             init_ctrl = vect_gen_while (preheader_seq, ctrl_type,
     818              :                                         start, end, "max_mask");
     819              :           else
     820              :             {
     821            0 :               init_ctrl = make_temp_ssa_name (compare_type, NULL, "max_len");
     822            0 :               gimple_seq seq = vect_gen_len (init_ctrl, start,
     823              :                                              end, length_limit);
     824            0 :               gimple_seq_add_seq (preheader_seq, seq);
     825              :             }
     826              :         }
     827              : 
     828              :       /* Now AND out the bits that are within the number of skipped
     829              :          items.  */
     830            0 :       poly_uint64 const_skip;
     831            0 :       if (nitems_skip
     832            0 :           && !(poly_int_tree_p (nitems_skip, &const_skip)
     833            0 :                && known_le (const_skip, bias)))
     834              :         {
     835            0 :           gcc_assert (use_masks_p);
     836            0 :           tree unskipped_mask = vect_gen_while_not (preheader_seq, ctrl_type,
     837              :                                                     bias_tree, nitems_skip);
     838            0 :           if (init_ctrl)
     839            0 :             init_ctrl = gimple_build (preheader_seq, BIT_AND_EXPR, ctrl_type,
     840              :                                       init_ctrl, unskipped_mask);
     841              :           else
     842              :             init_ctrl = unskipped_mask;
     843              :         }
     844              : 
     845            0 :       if (!init_ctrl)
     846              :         {
     847              :           /* First iteration is full.  */
     848            0 :           if (use_masks_p)
     849            0 :             init_ctrl = build_minus_one_cst (ctrl_type);
     850              :           else
     851              :             init_ctrl = length_limit;
     852              :         }
     853              : 
     854              :       /* Get the control value for the next iteration of the loop.  */
     855            0 :       if (use_masks_p)
     856              :         {
     857            0 :           gimple_seq stmts = NULL;
     858            0 :           next_ctrl = vect_gen_while (&stmts, ctrl_type, test_index,
     859              :                                       this_test_limit, "next_mask");
     860            0 :           gsi_insert_seq_after (&incr_gsi, stmts, GSI_SAME_STMT);
     861              :         }
     862              :       else
     863              :         {
     864            0 :           next_ctrl = make_temp_ssa_name (compare_type, NULL, "next_len");
     865            0 :           gimple_seq seq = vect_gen_len (next_ctrl, test_index, this_test_limit,
     866              :                                          length_limit);
     867            0 :           gsi_insert_seq_after (&incr_gsi, seq, GSI_SAME_STMT);
     868              :         }
     869              : 
     870            0 :       vect_set_loop_control (loop, ctrl, init_ctrl, next_ctrl);
     871              :     }
     872              : 
     873            0 :   int partial_load_bias = LOOP_VINFO_PARTIAL_LOAD_STORE_BIAS (loop_vinfo);
     874            0 :   if (partial_load_bias != 0)
     875              :     {
     876            0 :       tree adjusted_len = rgc->bias_adjusted_ctrl;
     877            0 :       gassign *minus = gimple_build_assign (adjusted_len, PLUS_EXPR,
     878            0 :                                             rgc->controls[0],
     879              :                                             build_int_cst
     880            0 :                                             (TREE_TYPE (rgc->controls[0]),
     881            0 :                                              partial_load_bias));
     882            0 :       gimple_seq_add_stmt (header_seq, minus);
     883              :     }
     884              : 
     885              :   return next_ctrl;
     886              : }
     887              : 
     888              : /* Set up the iteration condition and rgroup controls for LOOP, given
     889              :    that LOOP_VINFO_USING_PARTIAL_VECTORS_P is true for the vectorized
     890              :    loop.  LOOP_VINFO describes the vectorization of LOOP.  NITERS is
     891              :    the number of iterations of the original scalar loop that should be
     892              :    handled by the vector loop.  NITERS_MAYBE_ZERO is as for
     893              :    vect_set_loop_condition.  Return the branch-back condition for the caller
     894              :    to insert.  */
     895              : 
     896              : static gcond *
     897            0 : vect_set_loop_condition_partial_vectors (class loop *loop, edge exit_edge,
     898              :                                          loop_vec_info loop_vinfo, tree niters,
     899              :                                          bool niters_maybe_zero,
     900              :                                          gimple_stmt_iterator loop_cond_gsi)
     901              : {
     902            0 :   gimple_seq preheader_seq = NULL;
     903            0 :   gimple_seq header_seq = NULL;
     904              : 
     905            0 :   bool use_masks_p = LOOP_VINFO_FULLY_MASKED_P (loop_vinfo);
     906            0 :   tree compare_type = LOOP_VINFO_RGROUP_COMPARE_TYPE (loop_vinfo);
     907            0 :   unsigned int compare_precision = TYPE_PRECISION (compare_type);
     908              : 
     909              :   /* Type of the initial value of NITERS.  */
     910            0 :   tree ni_actual_type = TREE_TYPE (niters);
     911            0 :   unsigned int ni_actual_precision = TYPE_PRECISION (ni_actual_type);
     912            0 :   tree niters_skip = LOOP_VINFO_MASK_SKIP_NITERS (loop_vinfo);
     913            0 :   if (niters_skip)
     914            0 :     niters_skip = gimple_convert (&preheader_seq, compare_type, niters_skip);
     915              : 
     916              :   /* Convert NITERS to the same size as the compare.  */
     917            0 :   if (compare_precision > ni_actual_precision
     918            0 :       && niters_maybe_zero)
     919              :     {
     920              :       /* We know that there is always at least one iteration, so if the
     921              :          count is zero then it must have wrapped.  Cope with this by
     922              :          subtracting 1 before the conversion and adding 1 to the result.  */
     923            0 :       gcc_assert (TYPE_UNSIGNED (ni_actual_type));
     924            0 :       niters = gimple_build (&preheader_seq, PLUS_EXPR, ni_actual_type,
     925              :                              niters, build_minus_one_cst (ni_actual_type));
     926            0 :       niters = gimple_convert (&preheader_seq, compare_type, niters);
     927            0 :       niters = gimple_build (&preheader_seq, PLUS_EXPR, compare_type,
     928              :                              niters, build_one_cst (compare_type));
     929              :     }
     930              :   else
     931            0 :     niters = gimple_convert (&preheader_seq, compare_type, niters);
     932              : 
     933              :   /* Iterate over all the rgroups and fill in their controls.  We could use
     934              :      the first control from any rgroup for the loop condition; here we
     935              :      arbitrarily pick the last.  */
     936            0 :   tree test_ctrl = NULL_TREE;
     937            0 :   tree iv_step = NULL_TREE;
     938            0 :   tree compare_step = NULL_TREE;
     939            0 :   rgroup_controls *rgc;
     940            0 :   rgroup_controls *iv_rgc = nullptr;
     941            0 :   unsigned int i;
     942            0 :   auto_vec<rgroup_controls> *controls = use_masks_p
     943            0 :                                           ? &LOOP_VINFO_MASKS (loop_vinfo).rgc_vec
     944              :                                           : &LOOP_VINFO_LENS (loop_vinfo);
     945            0 :   FOR_EACH_VEC_ELT (*controls, i, rgc)
     946            0 :     if (!rgc->controls.is_empty ())
     947              :       {
     948              :         /* First try using permutes.  This adds a single vector
     949              :            instruction to the loop for each mask, but needs no extra
     950              :            loop invariants or IVs.  */
     951            0 :         unsigned int nmasks = i + 1;
     952            0 :         if (use_masks_p && (nmasks & 1) == 0)
     953              :           {
     954            0 :             rgroup_controls *half_rgc = &(*controls)[nmasks / 2 - 1];
     955            0 :             if (!half_rgc->controls.is_empty ()
     956            0 :                 && vect_maybe_permute_loop_masks (&header_seq, rgc, half_rgc))
     957            0 :               continue;
     958              :           }
     959              : 
     960            0 :         if (!LOOP_VINFO_USING_DECREMENTING_IV_P (loop_vinfo)
     961            0 :             || !iv_rgc
     962            0 :             || (iv_rgc->max_nscalars_per_iter * iv_rgc->factor
     963            0 :                 != rgc->max_nscalars_per_iter * rgc->factor))
     964              :           {
     965              :             /* See whether zero-based IV would ever generate all-false masks
     966              :                or zero length before wrapping around.  */
     967            0 :             bool might_wrap_p = vect_rgroup_iv_might_wrap_p (loop_vinfo, rgc);
     968              : 
     969              :             /* Set up all controls for this group.  */
     970            0 :             test_ctrl
     971            0 :               = vect_set_loop_controls_directly (loop, loop_vinfo,
     972              :                                                  &preheader_seq, &header_seq,
     973              :                                                  loop_cond_gsi, rgc, niters,
     974              :                                                  niters_skip, might_wrap_p,
     975              :                                                  &iv_step, &compare_step);
     976              : 
     977            0 :             iv_rgc = rgc;
     978              :           }
     979              : 
     980            0 :         if (LOOP_VINFO_USING_DECREMENTING_IV_P (loop_vinfo)
     981            0 :             && rgc->controls.length () > 1)
     982              :           {
     983              :             /* vect_set_loop_controls_directly creates an IV whose step
     984              :                is equal to the expected sum of RGC->controls.  Use that
     985              :                information to populate RGC->controls.  */
     986            0 :             tree iv_type = LOOP_VINFO_RGROUP_IV_TYPE (loop_vinfo);
     987            0 :             gcc_assert (iv_step);
     988            0 :             vect_adjust_loop_lens_control (iv_type, &header_seq, rgc, iv_step);
     989              :           }
     990              :       }
     991              : 
     992              :   /* Emit all accumulated statements.  */
     993            0 :   add_preheader_seq (loop, preheader_seq);
     994            0 :   add_header_seq (loop, header_seq);
     995              : 
     996              :   /* Get a boolean result that tells us whether to iterate.  */
     997            0 :   gcond *cond_stmt;
     998            0 :   if (LOOP_VINFO_USING_DECREMENTING_IV_P (loop_vinfo)
     999            0 :       && !LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo))
    1000              :     {
    1001            0 :       gcc_assert (compare_step);
    1002            0 :       tree_code code = (exit_edge->flags & EDGE_TRUE_VALUE) ? LE_EXPR : GT_EXPR;
    1003            0 :       cond_stmt = gimple_build_cond (code, test_ctrl, compare_step, NULL_TREE,
    1004              :                                      NULL_TREE);
    1005            0 :     }
    1006              :   else
    1007              :     {
    1008            0 :       tree_code code = (exit_edge->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
    1009            0 :       tree zero_ctrl = build_zero_cst (TREE_TYPE (test_ctrl));
    1010            0 :       cond_stmt
    1011            0 :         = gimple_build_cond (code, test_ctrl, zero_ctrl, NULL_TREE, NULL_TREE);
    1012              :     }
    1013              :   /* The loop iterates (NITERS - 1) / VF + 1 times.
    1014              :      Subtract one from this to get the latch count.  */
    1015            0 :   tree step = build_int_cst (compare_type,
    1016            0 :                              LOOP_VINFO_VECT_FACTOR (loop_vinfo));
    1017            0 :   tree niters_minus_one = fold_build2 (PLUS_EXPR, compare_type, niters,
    1018              :                                        build_minus_one_cst (compare_type));
    1019            0 :   loop->nb_iterations = fold_build2 (TRUNC_DIV_EXPR, compare_type,
    1020              :                                      niters_minus_one, step);
    1021              : 
    1022            0 :   return cond_stmt;
    1023              : }
    1024              : 
    1025              : /* Set up the iteration condition and rgroup controls for LOOP in AVX512
    1026              :    style, given that LOOP_VINFO_USING_PARTIAL_VECTORS_P is true for the
    1027              :    vectorized loop.  LOOP_VINFO describes the vectorization of LOOP.  NITERS is
    1028              :    the number of iterations of the original scalar loop that should be
    1029              :    handled by the vector loop.  NITERS_MAYBE_ZERO is as for
    1030              :    vect_set_loop_condition.  Return the branch-back condition for the caller
    1031              :    to insert.  */
    1032              : 
    1033              : static gcond *
    1034           24 : vect_set_loop_condition_partial_vectors_avx512 (class loop *loop,
    1035              :                                          edge exit_edge,
    1036              :                                          loop_vec_info loop_vinfo, tree niters,
    1037              :                                          bool niters_maybe_zero)
    1038              : {
    1039           24 :   tree niters_skip = LOOP_VINFO_MASK_SKIP_NITERS (loop_vinfo);
    1040           24 :   tree iv_type = LOOP_VINFO_RGROUP_IV_TYPE (loop_vinfo);
    1041           24 :   poly_uint64 vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
    1042           24 :   tree orig_niters = niters;
    1043           24 :   gimple_seq preheader_seq = NULL;
    1044              : 
    1045              :   /* Create an IV that counts down from niters and whose step
    1046              :      is the number of iterations processed in the current iteration.
    1047              :      Produce the controls with compares like the following.
    1048              : 
    1049              :        # iv_2 = PHI <niters, iv_3>
    1050              :        rem_4 = MIN <iv_2, VF>;
    1051              :        remv_6 = { rem_4, rem_4, rem_4, ... }
    1052              :        mask_5 = { 0, 0, 1, 1, 2, 2, ... } < remv6;
    1053              :        iv_3 = iv_2 - VF;
    1054              :        if (iv_2 > VF)
    1055              :          continue;
    1056              : 
    1057              :      Where the constant is built with elements at most VF - 1 and
    1058              :      repetitions according to max_nscalars_per_iter which is guaranteed
    1059              :      to be the same within a group.  */
    1060              : 
    1061              :   /* Convert NITERS to the determined IV type.  */
    1062           24 :   if (TYPE_PRECISION (iv_type) > TYPE_PRECISION (TREE_TYPE (niters))
    1063           24 :       && niters_maybe_zero)
    1064              :     {
    1065              :       /* We know that there is always at least one iteration, so if the
    1066              :          count is zero then it must have wrapped.  Cope with this by
    1067              :          subtracting 1 before the conversion and adding 1 to the result.  */
    1068            0 :       gcc_assert (TYPE_UNSIGNED (TREE_TYPE (niters)));
    1069            0 :       niters = gimple_build (&preheader_seq, PLUS_EXPR, TREE_TYPE (niters),
    1070            0 :                              niters, build_minus_one_cst (TREE_TYPE (niters)));
    1071            0 :       niters = gimple_convert (&preheader_seq, iv_type, niters);
    1072            0 :       niters = gimple_build (&preheader_seq, PLUS_EXPR, iv_type,
    1073              :                              niters, build_one_cst (iv_type));
    1074              :     }
    1075              :   else
    1076           24 :     niters = gimple_convert (&preheader_seq, iv_type, niters);
    1077              : 
    1078              :   /* Bias the initial value of the IV in case we need to skip iterations
    1079              :      at the beginning.  */
    1080           24 :   tree niters_adj = niters;
    1081           24 :   if (niters_skip)
    1082              :     {
    1083            2 :       tree skip = gimple_convert (&preheader_seq, iv_type, niters_skip);
    1084            2 :       niters_adj = gimple_build (&preheader_seq, PLUS_EXPR,
    1085              :                                  iv_type, niters, skip);
    1086              :     }
    1087              : 
    1088           24 :   gimple_stmt_iterator incr_gsi;
    1089           24 :   tree index_before_incr, index_after_incr;
    1090           24 :   bool insert_after;
    1091           24 :   standard_iv_increment_position (loop, &incr_gsi, &insert_after);
    1092              : 
    1093              :   /* The iteration step is the vectorization factor.  */
    1094           24 :   tree iv_step = gimple_convert (&preheader_seq, iv_type,
    1095              :                                  LOOP_VINFO_IV_INCREMENT (loop_vinfo));
    1096              : 
    1097              :   /* Create the decrement IV.  */
    1098           24 :   create_iv (niters_adj, MINUS_EXPR, iv_step, NULL_TREE, loop,
    1099              :              &incr_gsi, insert_after, &index_before_incr,
    1100              :              &index_after_incr);
    1101              : 
    1102              :   /* Iterate over all the rgroups and fill in their controls.  */
    1103          105 :   for (auto &rgc : LOOP_VINFO_MASKS (loop_vinfo).rgc_vec)
    1104              :     {
    1105           33 :       if (rgc.controls.is_empty ())
    1106            7 :         continue;
    1107              : 
    1108           26 :       tree ctrl_type = rgc.type;
    1109           26 :       poly_uint64 nitems_per_ctrl = TYPE_VECTOR_SUBPARTS (ctrl_type);
    1110              : 
    1111           26 :       tree vectype = rgc.compare_type;
    1112              : 
    1113              :       /* index_after_incr is the IV specifying the remaining iterations in
    1114              :          the next iteration.  */
    1115           26 :       tree rem = index_after_incr;
    1116              :       /* When the data type for the compare to produce the mask is
    1117              :          smaller than the IV type we need to saturate.  Saturate to
    1118              :          the smallest possible value (IV_TYPE) so we only have to
    1119              :          saturate once (CSE will catch redundant ones we add).  */
    1120           26 :       if (TYPE_PRECISION (TREE_TYPE (vectype)) < TYPE_PRECISION (iv_type))
    1121            9 :         rem = gimple_build (&incr_gsi, false, GSI_CONTINUE_LINKING,
    1122              :                             UNKNOWN_LOCATION,
    1123            9 :                             MIN_EXPR, TREE_TYPE (rem), rem, iv_step);
    1124           26 :       rem = gimple_convert (&incr_gsi, false, GSI_CONTINUE_LINKING,
    1125           26 :                             UNKNOWN_LOCATION, TREE_TYPE (vectype), rem);
    1126              : 
    1127              :       /* Build a data vector composed of the remaining iterations.  */
    1128           26 :       rem = gimple_build_vector_from_val (&incr_gsi, false, GSI_CONTINUE_LINKING,
    1129              :                                           UNKNOWN_LOCATION, vectype, rem);
    1130              : 
    1131              :       /* Provide a definition of each vector in the control group.  */
    1132           26 :       tree next_ctrl = NULL_TREE;
    1133           26 :       tree first_rem = NULL_TREE;
    1134           26 :       tree ctrl;
    1135           26 :       unsigned int i;
    1136          177 :       FOR_EACH_VEC_ELT_REVERSE (rgc.controls, i, ctrl)
    1137              :         {
    1138              :           /* Previous controls will cover BIAS items.  This control covers the
    1139              :              next batch.  */
    1140           92 :           poly_uint64 bias = nitems_per_ctrl * i;
    1141              : 
    1142              :           /* Build the constant to compare the remaining iters against,
    1143              :              this is sth like { 0, 0, 1, 1, 2, 2, 3, 3, ... } appropriately
    1144              :              split into pieces.  */
    1145           92 :           unsigned n = TYPE_VECTOR_SUBPARTS (ctrl_type).to_constant ();
    1146           92 :           tree_vector_builder builder (vectype, n, 1);
    1147         1418 :           for (unsigned i = 0; i < n; ++i)
    1148              :             {
    1149         1234 :               unsigned HOST_WIDE_INT val
    1150         1234 :                 = (i + bias.to_constant ()) / rgc.max_nscalars_per_iter;
    1151         1234 :               gcc_assert (val < vf.to_constant ());
    1152         1234 :               builder.quick_push (build_int_cst (TREE_TYPE (vectype), val));
    1153              :             }
    1154           92 :           tree cmp_series = builder.build ();
    1155              : 
    1156              :           /* Create the initial control.  First include all items that
    1157              :              are within the loop limit.  */
    1158           92 :           tree init_ctrl = NULL_TREE;
    1159           92 :           poly_uint64 const_limit;
    1160              :           /* See whether the first iteration of the vector loop is known
    1161              :              to have a full control.  */
    1162           92 :           if (poly_int_tree_p (niters, &const_limit)
    1163           92 :               && known_ge (const_limit, (i + 1) * nitems_per_ctrl))
    1164            3 :             init_ctrl = build_minus_one_cst (ctrl_type);
    1165              :           else
    1166              :             {
    1167              :               /* The remaining work items initially are niters.  Saturate,
    1168              :                  splat and compare.  */
    1169           89 :               if (!first_rem)
    1170              :                 {
    1171           23 :                   first_rem = niters;
    1172           23 :                   if (TYPE_PRECISION (TREE_TYPE (vectype))
    1173           23 :                       < TYPE_PRECISION (iv_type))
    1174            9 :                     first_rem = gimple_build (&preheader_seq,
    1175            9 :                                               MIN_EXPR, TREE_TYPE (first_rem),
    1176              :                                               first_rem, iv_step);
    1177           23 :                   first_rem = gimple_convert (&preheader_seq, TREE_TYPE (vectype),
    1178              :                                               first_rem);
    1179           23 :                   first_rem = gimple_build_vector_from_val (&preheader_seq,
    1180              :                                                             vectype, first_rem);
    1181              :                 }
    1182           89 :               init_ctrl = gimple_build (&preheader_seq, LT_EXPR, ctrl_type,
    1183              :                                         cmp_series, first_rem);
    1184              :             }
    1185              : 
    1186              :           /* Now AND out the bits that are within the number of skipped
    1187              :              items.  */
    1188           92 :           poly_uint64 const_skip;
    1189           92 :           if (niters_skip
    1190           92 :               && !(poly_int_tree_p (niters_skip, &const_skip)
    1191            2 :                    && known_le (const_skip, bias)))
    1192              :             {
    1193              :               /* For integer mode masks it's cheaper to shift out the bits
    1194              :                  since that avoids loading a constant.  */
    1195            2 :               gcc_assert (GET_MODE_CLASS (TYPE_MODE (ctrl_type)) == MODE_INT);
    1196            2 :               init_ctrl = gimple_build (&preheader_seq, VIEW_CONVERT_EXPR,
    1197            2 :                                         lang_hooks.types.type_for_mode
    1198            2 :                                           (TYPE_MODE (ctrl_type), 1),
    1199              :                                         init_ctrl);
    1200              :               /* ???  But when the shift amount isn't constant this requires
    1201              :                  a round-trip to GRPs.  We could apply the bias to either
    1202              :                  side of the compare instead.  */
    1203            4 :               tree shift = gimple_build (&preheader_seq, MINUS_EXPR,
    1204            2 :                                          TREE_TYPE (niters_skip), niters_skip,
    1205            2 :                                          build_int_cst (TREE_TYPE (niters_skip),
    1206            2 :                                                         bias));
    1207            4 :               shift = gimple_build (&preheader_seq, MULT_EXPR,
    1208            2 :                                     TREE_TYPE (niters_skip), shift,
    1209            2 :                                     build_int_cst (TREE_TYPE (niters_skip),
    1210            2 :                                                    rgc.max_nscalars_per_iter));
    1211            2 :               init_ctrl = gimple_build (&preheader_seq, LSHIFT_EXPR,
    1212            2 :                                         TREE_TYPE (init_ctrl),
    1213              :                                         init_ctrl, shift);
    1214            2 :               init_ctrl = gimple_build (&preheader_seq, VIEW_CONVERT_EXPR,
    1215              :                                         ctrl_type, init_ctrl);
    1216              :             }
    1217              : 
    1218              :           /* Get the control value for the next iteration of the loop.  */
    1219           92 :           next_ctrl = gimple_build (&incr_gsi, false, GSI_CONTINUE_LINKING,
    1220              :                                     UNKNOWN_LOCATION,
    1221              :                                     LT_EXPR, ctrl_type, cmp_series, rem);
    1222              : 
    1223           92 :           vect_set_loop_control (loop, ctrl, init_ctrl, next_ctrl);
    1224           92 :         }
    1225              :     }
    1226              : 
    1227              :   /* Emit all accumulated statements.  */
    1228           24 :   add_preheader_seq (loop, preheader_seq);
    1229              : 
    1230              :   /* Adjust the exit test using the decrementing IV.  */
    1231           24 :   tree_code code = (exit_edge->flags & EDGE_TRUE_VALUE) ? LE_EXPR : GT_EXPR;
    1232              :   /* When we peel for alignment with niter_skip != 0 this can
    1233              :      cause niter + niter_skip to wrap and since we are comparing the
    1234              :      value before the decrement here we get a false early exit.
    1235              :      We can't compare the value after decrement either because that
    1236              :      decrement could wrap as well as we're not doing a saturating
    1237              :      decrement.  To avoid this situation we force a larger
    1238              :      iv_type.  */
    1239           24 :   gcond *cond_stmt = gimple_build_cond (code, index_before_incr, iv_step,
    1240              :                                         NULL_TREE, NULL_TREE);
    1241              :   /* The loop iterates (NITERS - 1 + NITERS_SKIP) / VF + 1 times.
    1242              :      Subtract one from this to get the latch count.  */
    1243           24 :   tree niters_minus_one
    1244           24 :     = fold_build2 (PLUS_EXPR, TREE_TYPE (orig_niters), orig_niters,
    1245              :                    build_minus_one_cst (TREE_TYPE (orig_niters)));
    1246           24 :   tree niters_adj2 = fold_convert (iv_type, niters_minus_one);
    1247           24 :   if (niters_skip)
    1248            2 :     niters_adj2 = fold_build2 (PLUS_EXPR, iv_type, niters_minus_one,
    1249              :                                fold_convert (iv_type, niters_skip));
    1250           24 :   loop->nb_iterations = fold_build2 (TRUNC_DIV_EXPR, iv_type,
    1251              :                                      niters_adj2, iv_step);
    1252              : 
    1253           24 :   return cond_stmt;
    1254              : }
    1255              : 
    1256              : 
    1257              : /* Like vect_set_loop_condition, but handle the case in which the vector
    1258              :    loop handles exactly VF scalars per iteration.  Return the branch-back
    1259              :    condition for the caller to insert.  */
    1260              : 
    1261              : static gcond *
    1262        64765 : vect_set_loop_condition_normal (loop_vec_info loop_vinfo, edge exit_edge,
    1263              :                                 class loop *loop, tree niters, tree step,
    1264              :                                 tree final_iv, bool niters_maybe_zero)
    1265              : {
    1266        64765 :   tree indx_before_incr, indx_after_incr;
    1267        64765 :   gcond *cond_stmt;
    1268        64765 :   edge pe = loop_preheader_edge (loop);
    1269        64765 :   gimple_stmt_iterator incr_gsi;
    1270        64765 :   bool insert_after;
    1271        64765 :   enum tree_code code;
    1272        64765 :   tree niters_type = TREE_TYPE (niters);
    1273              : 
    1274        64765 :   tree init, limit;
    1275        64765 :   if (!niters_maybe_zero && integer_onep (step))
    1276              :     {
    1277              :       /* In this case we can use a simple 0-based IV:
    1278              : 
    1279              :          A:
    1280              :            x = 0;
    1281              :            do
    1282              :              {
    1283              :                ...
    1284              :                x += 1;
    1285              :              }
    1286              :            while (x < NITERS);  */
    1287        64765 :       code = (exit_edge->flags & EDGE_TRUE_VALUE) ? GE_EXPR : LT_EXPR;
    1288        64765 :       init = build_zero_cst (niters_type);
    1289        64765 :       limit = niters;
    1290              :     }
    1291              :   else
    1292              :     {
    1293              :       /* The following works for all values of NITERS except 0:
    1294              : 
    1295              :          B:
    1296              :            x = 0;
    1297              :            do
    1298              :              {
    1299              :                ...
    1300              :                x += STEP;
    1301              :              }
    1302              :            while (x <= NITERS - STEP);
    1303              : 
    1304              :          so that the loop continues to iterate if x + STEP - 1 < NITERS
    1305              :          but stops if x + STEP - 1 >= NITERS.
    1306              : 
    1307              :          However, if NITERS is zero, x never hits a value above NITERS - STEP
    1308              :          before wrapping around.  There are two obvious ways of dealing with
    1309              :          this:
    1310              : 
    1311              :          - start at STEP - 1 and compare x before incrementing it
    1312              :          - start at -1 and compare x after incrementing it
    1313              : 
    1314              :          The latter is simpler and is what we use.  The loop in this case
    1315              :          looks like:
    1316              : 
    1317              :          C:
    1318              :            x = -1;
    1319              :            do
    1320              :              {
    1321              :                ...
    1322              :                x += STEP;
    1323              :              }
    1324              :            while (x < NITERS - STEP);
    1325              : 
    1326              :          In both cases the loop limit is NITERS - STEP.  */
    1327            0 :       gimple_seq seq = NULL;
    1328            0 :       limit = force_gimple_operand (niters, &seq, true, NULL_TREE);
    1329            0 :       limit = gimple_build (&seq, MINUS_EXPR, TREE_TYPE (limit), limit, step);
    1330            0 :       if (seq)
    1331              :         {
    1332            0 :           basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, seq);
    1333            0 :           gcc_assert (!new_bb);
    1334              :         }
    1335            0 :       if (niters_maybe_zero)
    1336              :         {
    1337              :           /* Case C.  */
    1338            0 :           code = (exit_edge->flags & EDGE_TRUE_VALUE) ? GE_EXPR : LT_EXPR;
    1339            0 :           init = build_all_ones_cst (niters_type);
    1340              :         }
    1341              :       else
    1342              :         {
    1343              :           /* Case B.  */
    1344            0 :           code = (exit_edge->flags & EDGE_TRUE_VALUE) ? GT_EXPR : LE_EXPR;
    1345            0 :           init = build_zero_cst (niters_type);
    1346              :         }
    1347              :     }
    1348              : 
    1349        64765 :   standard_iv_increment_position (loop, &incr_gsi, &insert_after);
    1350       129530 :   create_iv (init, PLUS_EXPR, step, NULL_TREE, loop,
    1351              :              &incr_gsi, insert_after,
    1352              :              &indx_before_incr, &indx_after_incr,
    1353        64323 :              !loop_vinfo || LOOP_VINFO_IV_INCREMENT_INVARIANT_P (loop_vinfo));
    1354              : 
    1355        64765 :   cond_stmt = gimple_build_cond (code, indx_after_incr, limit, NULL_TREE,
    1356              :                                  NULL_TREE);
    1357              : 
    1358              :   /* Record the number of latch iterations.  */
    1359        64765 :   if (limit == niters)
    1360              :     /* Case A: the loop iterates NITERS times.  Subtract one to get the
    1361              :        latch count.  */
    1362        64765 :     loop->nb_iterations = fold_build2 (MINUS_EXPR, niters_type, niters,
    1363              :                                        build_int_cst (niters_type, 1));
    1364              :   else
    1365              :     /* Case B or C: the loop iterates (NITERS - STEP) / STEP + 1 times.
    1366              :        Subtract one from this to get the latch count.  */
    1367            0 :     loop->nb_iterations = fold_build2 (TRUNC_DIV_EXPR, niters_type,
    1368              :                                        limit, step);
    1369              : 
    1370        64765 :   if (final_iv)
    1371              :     {
    1372            0 :       gassign *assign;
    1373            0 :       tree phi_dest
    1374            0 :         = integer_zerop (init) ? final_iv : copy_ssa_name (indx_after_incr);
    1375              :       /* Make sure to maintain LC SSA form here and elide the subtraction
    1376              :          if the value is zero.  */
    1377            0 :       gphi *phi = create_phi_node (phi_dest, exit_edge->dest);
    1378            0 :       add_phi_arg (phi, indx_after_incr, exit_edge, UNKNOWN_LOCATION);
    1379            0 :       if (!integer_zerop (init))
    1380              :         {
    1381            0 :           assign = gimple_build_assign (final_iv, MINUS_EXPR, phi_dest, init);
    1382            0 :           gimple_stmt_iterator gsi
    1383            0 :             = gsi_after_labels (LOOP_VINFO_MAIN_EXIT (loop_vinfo)->dest);
    1384            0 :           gsi_insert_before (&gsi, assign, GSI_SAME_STMT);
    1385              :         }
    1386              :     }
    1387              : 
    1388        64765 :   return cond_stmt;
    1389              : }
    1390              : 
    1391              : /* If we're using fully-masked loops, make LOOP iterate:
    1392              : 
    1393              :       N == (NITERS - 1) / STEP + 1
    1394              : 
    1395              :    times.  When NITERS is zero, this is equivalent to making the loop
    1396              :    execute (1 << M) / STEP times, where M is the precision of NITERS.
    1397              :    NITERS_MAYBE_ZERO is true if this last case might occur.
    1398              : 
    1399              :    If we're not using fully-masked loops, make LOOP iterate:
    1400              : 
    1401              :       N == (NITERS - STEP) / STEP + 1
    1402              : 
    1403              :    times, where NITERS is known to be outside the range [1, STEP - 1].
    1404              :    This is equivalent to making the loop execute NITERS / STEP times
    1405              :    when NITERS is nonzero and (1 << M) / STEP times otherwise.
    1406              :    NITERS_MAYBE_ZERO again indicates whether this last case might occur.
    1407              : 
    1408              :    If FINAL_IV is nonnull, it is an SSA name that should be set to
    1409              :    N * STEP on exit from the loop.
    1410              : 
    1411              :    Assumption: the exit-condition of LOOP is the last stmt in the loop.  */
    1412              : 
    1413              : void
    1414        64789 : vect_set_loop_condition (class loop *loop, edge loop_e, loop_vec_info loop_vinfo,
    1415              :                          tree niters, tree step, tree final_iv,
    1416              :                          bool niters_maybe_zero)
    1417              : {
    1418        64789 :   gcond *cond_stmt;
    1419        64789 :   gcond *orig_cond = get_loop_exit_condition (loop_e);
    1420        64789 :   gimple_stmt_iterator loop_cond_gsi = gsi_for_stmt (orig_cond);
    1421              : 
    1422              :   /* Check to see whether we will be replacing final_IV below.  Because of the
    1423              :      various replacement strategies (assign vs PHI) just remove it now and
    1424              :      leave the SSA name to be rebuild below.  */
    1425        64789 :   if (final_iv && TREE_CODE (final_iv) == SSA_NAME)
    1426              :     {
    1427            0 :       gimple *def = SSA_NAME_DEF_STMT (final_iv);
    1428            0 :       if (gimple_call_internal_p (def, IFN_VARYING))
    1429              :         {
    1430            0 :           gimple_stmt_iterator gsi = gsi_for_stmt (def);
    1431            0 :           gsi_remove (&gsi, true);
    1432              :         }
    1433              :     }
    1434              : 
    1435        64789 :   if (loop_vinfo && LOOP_VINFO_USING_PARTIAL_VECTORS_P (loop_vinfo))
    1436              :     {
    1437           24 :       if (LOOP_VINFO_PARTIAL_VECTORS_STYLE (loop_vinfo) == vect_partial_vectors_avx512)
    1438           24 :         cond_stmt = vect_set_loop_condition_partial_vectors_avx512 (loop, loop_e,
    1439              :                                                                     loop_vinfo,
    1440              :                                                                     niters,
    1441              :                                                                     niters_maybe_zero);
    1442              :       else
    1443            0 :         cond_stmt = vect_set_loop_condition_partial_vectors (loop, loop_e,
    1444              :                                                              loop_vinfo,
    1445              :                                                              niters,
    1446              :                                                              niters_maybe_zero,
    1447              :                                                              loop_cond_gsi);
    1448              :     }
    1449              :   else
    1450        64765 :     cond_stmt = vect_set_loop_condition_normal (loop_vinfo, loop_e, loop,
    1451              :                                                 niters,
    1452              :                                                 step, final_iv,
    1453              :                                                 niters_maybe_zero);
    1454              : 
    1455              :   /* A peeled early-break loop is entered only when it has at least one
    1456              :      vector iteration to execute.  Test the IV after that iteration rather
    1457              :      than before it, regardless of the style of loop control.  */
    1458        64789 :   if (loop_vinfo && LOOP_VINFO_EARLY_BREAKS_VECT_PEELED (loop_vinfo))
    1459              :     {
    1460              :       /* Move the IV exit test from the header to the latch, so that it
    1461              :          follows the early exits in the loop body.  */
    1462           54 :       basic_block latch = loop->latch;
    1463           54 :       edge latch_e = single_succ_edge (latch);
    1464           54 :       int exit_flags = loop_e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
    1465              : 
    1466           54 :       latch_e->flags &= ~(EDGE_FALLTHRU | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
    1467           54 :       latch_e->flags |= (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE) ^ exit_flags;
    1468           54 :       edge latch_exit_edge = make_edge (latch, loop_e->dest, exit_flags);
    1469           54 :       latch_exit_edge->probability = loop_e->probability;
    1470           54 :       latch_exit_edge->count () = loop_e->count ();
    1471           54 :       copy_phi_arg_into_existing_phi (loop_e, latch_exit_edge);
    1472           54 :       if (gphi *vphi = get_virtual_phi (latch_exit_edge->dest))
    1473           29 :         SET_PHI_ARG_DEF_ON_EDGE (vphi, latch_exit_edge,
    1474              :                                  get_live_virtual_operand_on_edge
    1475              :                                    (latch_exit_edge));
    1476           54 :       gimple_stmt_iterator latch_gsi = gsi_last_bb (latch);
    1477           54 :       gsi_insert_after (&latch_gsi, cond_stmt, GSI_NEW_STMT);
    1478           54 :       LOOP_VINFO_MAIN_EXIT (loop_vinfo) = latch_exit_edge;
    1479              : 
    1480           54 :       if (loop_e->flags & EDGE_TRUE_VALUE)
    1481            6 :         gimple_cond_make_false (orig_cond);
    1482              :       else
    1483           48 :         gimple_cond_make_true (orig_cond);
    1484           54 :       update_stmt (orig_cond);
    1485              :     }
    1486              :   else
    1487              :     {
    1488        64735 :       gsi_insert_before (&loop_cond_gsi, cond_stmt, GSI_SAME_STMT);
    1489        64735 :       stmt_vec_info orig_cond_info;
    1490        64735 :       if (loop_vinfo
    1491        64735 :           && (orig_cond_info = loop_vinfo->lookup_stmt (orig_cond)))
    1492        64293 :         loop_vinfo->remove_stmt (orig_cond_info);
    1493              :       else
    1494          442 :         gsi_remove (&loop_cond_gsi, true);
    1495              :     }
    1496              : 
    1497        64789 :   if (loop_vinfo && LOOP_VINFO_USING_PARTIAL_VECTORS_P (loop_vinfo)
    1498           24 :       && final_iv)
    1499              :     {
    1500            0 :       gassign *assign = gimple_build_assign (final_iv, niters);
    1501            0 :       gsi_insert_on_edge_immediate (LOOP_VINFO_MAIN_EXIT (loop_vinfo), assign);
    1502              :     }
    1503              : 
    1504        64789 :   if (dump_enabled_p ())
    1505        11741 :     dump_printf_loc (MSG_NOTE, vect_location, "New loop exit condition: %G",
    1506              :                      (gimple *) cond_stmt);
    1507        64789 : }
    1508              : 
    1509              : /* Given LOOP this function generates a new copy of it and puts it
    1510              :    on E which is either the entry or exit of LOOP.  If SCALAR_LOOP is
    1511              :    non-NULL, assume LOOP and SCALAR_LOOP are equivalent and copy the
    1512              :    basic blocks from SCALAR_LOOP instead of LOOP, but to either the
    1513              :    entry or exit of LOOP.  If FLOW_LOOPS then connect LOOP to SCALAR_LOOP as a
    1514              :    continuation.  This is correct for cases where one loop continues from the
    1515              :    other like in the vectorizer, but not true for uses in e.g. loop distribution
    1516              :    where the contents of the loop body are split but the iteration space of both
    1517              :    copies remains the same.
    1518              : 
    1519              :    If UPDATED_DOMS is not NULL it is update with the list of basic blocks whose
    1520              :    dominators were updated during the peeling.  When doing early break vectorization
    1521              :    then LOOP_VINFO needs to be provided and is used to keep track of any newly created
    1522              :    memory references that need to be updated should we decide to vectorize.  */
    1523              : 
    1524              : class loop *
    1525        35896 : slpeel_tree_duplicate_loop_to_edge_cfg (class loop *loop, edge loop_exit,
    1526              :                                         class loop *scalar_loop,
    1527              :                                         edge scalar_exit, edge e, edge *new_e,
    1528              :                                         bool flow_loops,
    1529              :                                         vec<basic_block> *updated_doms,
    1530              :                                         bool uncounted_p, bool create_main_e,
    1531              :                                         bool redirect_exits)
    1532              : {
    1533        35896 :   class loop *new_loop;
    1534        35896 :   basic_block *new_bbs, *bbs, *pbbs;
    1535        35896 :   bool at_exit;
    1536        35896 :   bool was_imm_dom;
    1537        35896 :   basic_block exit_dest;
    1538        35896 :   edge exit, new_exit;
    1539        35896 :   bool duplicate_outer_loop = false;
    1540              : 
    1541        35896 :   exit = loop_exit;
    1542        35896 :   at_exit = (e == exit);
    1543        35896 :   if (!at_exit && e != loop_preheader_edge (loop))
    1544              :     return NULL;
    1545              : 
    1546        35896 :   if (scalar_loop == NULL)
    1547              :     {
    1548        34368 :       scalar_loop = loop;
    1549        34368 :       scalar_exit = loop_exit;
    1550              :     }
    1551         1528 :   else if (scalar_loop == loop)
    1552            0 :     scalar_exit = loop_exit;
    1553              :   else
    1554              :     {
    1555              :       /* Loop has been version, match exits up using the aux index.  */
    1556         4584 :       for (edge exit : get_loop_exit_edges (scalar_loop))
    1557         1528 :         if (exit->aux == loop_exit->aux)
    1558              :           {
    1559         1528 :             scalar_exit = exit;
    1560         1528 :             break;
    1561         1528 :           }
    1562              : 
    1563         1528 :       gcc_assert (scalar_exit);
    1564              :     }
    1565              : 
    1566        35896 :   bbs = XNEWVEC (basic_block, scalar_loop->num_nodes + 1);
    1567        35896 :   pbbs = bbs + 1;
    1568        35896 :   get_loop_body_with_size (scalar_loop, pbbs, scalar_loop->num_nodes);
    1569              :   /* Allow duplication of outer loops.  */
    1570        35896 :   if (scalar_loop->inner)
    1571          128 :     duplicate_outer_loop = true;
    1572              : 
    1573              :   /* Generate new loop structure.  */
    1574        35896 :   new_loop = duplicate_loop (scalar_loop, loop_outer (scalar_loop));
    1575        35896 :   duplicate_subloops (scalar_loop, new_loop);
    1576              : 
    1577        35896 :   exit_dest = exit->dest;
    1578        35896 :   was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS,
    1579        35896 :                                           exit_dest) == exit->src ?
    1580              :                  true : false);
    1581              : 
    1582              :   /* Also copy the pre-header, this avoids jumping through hoops to
    1583              :      duplicate the loop entry PHI arguments.  Create an empty
    1584              :      pre-header unconditionally for this.  */
    1585        35896 :   basic_block preheader = split_edge (loop_preheader_edge (scalar_loop));
    1586        35896 :   edge entry_e = single_pred_edge (preheader);
    1587        35896 :   bbs[0] = preheader;
    1588        35896 :   new_bbs = XNEWVEC (basic_block, scalar_loop->num_nodes + 1);
    1589              : 
    1590        35896 :   copy_bbs (bbs, scalar_loop->num_nodes + 1, new_bbs,
    1591              :             &scalar_exit, 1, &new_exit, NULL,
    1592              :             at_exit ? loop->latch : e->src, true);
    1593        35896 :   exit = loop_exit;
    1594        35896 :   basic_block new_preheader = new_bbs[0];
    1595              : 
    1596        35896 :   gcc_assert (new_exit);
    1597              : 
    1598              :   /* Record the new loop exit information.  new_loop doesn't have SCEV data and
    1599              :      so we must initialize the exit information.  */
    1600        35896 :   if (new_e)
    1601        34657 :     *new_e = new_exit;
    1602              : 
    1603              :   /* Before installing PHI arguments make sure that the edges
    1604              :      into them match that of the scalar loop we analyzed.  This
    1605              :      makes sure the SLP tree matches up between the main vectorized
    1606              :      loop and the epilogue vectorized copies.  */
    1607        35896 :   if (single_succ_edge (preheader)->dest_idx
    1608        35896 :       != single_succ_edge (new_bbs[0])->dest_idx)
    1609              :     {
    1610        31723 :       basic_block swap_bb = new_bbs[1];
    1611        31723 :       gcc_assert (EDGE_COUNT (swap_bb->preds) == 2);
    1612        31723 :       std::swap (EDGE_PRED (swap_bb, 0), EDGE_PRED (swap_bb, 1));
    1613        31723 :       EDGE_PRED (swap_bb, 0)->dest_idx = 0;
    1614        31723 :       EDGE_PRED (swap_bb, 1)->dest_idx = 1;
    1615              :     }
    1616        35896 :   if (duplicate_outer_loop)
    1617              :     {
    1618          128 :       class loop *new_inner_loop = get_loop_copy (scalar_loop->inner);
    1619          128 :       if (loop_preheader_edge (scalar_loop)->dest_idx
    1620          128 :           != loop_preheader_edge (new_inner_loop)->dest_idx)
    1621              :         {
    1622          104 :           basic_block swap_bb = new_inner_loop->header;
    1623          104 :           gcc_assert (EDGE_COUNT (swap_bb->preds) == 2);
    1624          104 :           std::swap (EDGE_PRED (swap_bb, 0), EDGE_PRED (swap_bb, 1));
    1625          104 :           EDGE_PRED (swap_bb, 0)->dest_idx = 0;
    1626          104 :           EDGE_PRED (swap_bb, 1)->dest_idx = 1;
    1627              :         }
    1628              :     }
    1629              : 
    1630        35896 :   add_phi_args_after_copy (new_bbs, scalar_loop->num_nodes + 1, NULL);
    1631              : 
    1632              :   /* Skip new preheader since it's deleted if copy loop is added at entry.  */
    1633       148926 :   for (unsigned i = (at_exit ? 0 : 1); i < scalar_loop->num_nodes + 1; i++)
    1634       113030 :     rename_variables_in_bb (new_bbs[i], duplicate_outer_loop);
    1635              : 
    1636              :   /* Rename the exit uses.  */
    1637       144827 :   for (edge exit : get_loop_exit_edges (new_loop))
    1638        37139 :     for (auto gsi = gsi_start_phis (exit->dest);
    1639        86733 :          !gsi_end_p (gsi); gsi_next (&gsi))
    1640              :       {
    1641        49594 :         tree orig_def = PHI_ARG_DEF_FROM_EDGE (gsi.phi (), exit);
    1642        49594 :         rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (gsi.phi (), exit));
    1643        49594 :         if (MAY_HAVE_DEBUG_BIND_STMTS)
    1644        23342 :           adjust_debug_stmts (orig_def, PHI_RESULT (gsi.phi ()), exit->dest);
    1645        35896 :       }
    1646              : 
    1647        35896 :   auto loop_exits = get_loop_exit_edges (loop);
    1648        35896 :   bool has_multiple_exits_p = loop_exits.length () > 1;
    1649              : 
    1650              :   /* If REDIRECT_EXITS is false we leave the alternative exits untouched and
    1651              :      treat the duplication as if the loop only had the main exit.  */
    1652        35896 :   bool redirect_multiple_exits_p = redirect_exits && has_multiple_exits_p;
    1653        35896 :   auto_vec<basic_block> doms;
    1654              : 
    1655        35896 :   if (at_exit) /* Add the loop copy at exit.  */
    1656              :     {
    1657        34215 :       if (scalar_loop != loop && new_exit->dest != exit_dest)
    1658              :         {
    1659         1524 :           new_exit = redirect_edge_and_branch (new_exit, exit_dest);
    1660         1524 :           flush_pending_stmts (new_exit);
    1661              :         }
    1662              : 
    1663        34215 :       bool need_virtual_phi = get_virtual_phi (loop->header);
    1664              : 
    1665              :       /* For the main loop exit preserve the LC PHI nodes.  For vectorization
    1666              :          we need them to continue or finalize reductions.  Since we do not
    1667              :          copy the loop exit blocks we have to materialize PHIs at the
    1668              :          new destination before redirecting edges.  */
    1669        34215 :       for (auto gsi_from = gsi_start_phis (loop_exit->dest);
    1670        80884 :            !gsi_end_p (gsi_from); gsi_next (&gsi_from))
    1671              :         {
    1672        46669 :           tree res = gimple_phi_result (*gsi_from);
    1673        46669 :           create_phi_node (copy_ssa_name (res), new_preheader);
    1674              :         }
    1675        34215 :       edge e = redirect_edge_and_branch (loop_exit, new_preheader);
    1676        34215 :       gcc_assert (e == loop_exit);
    1677        34215 :       flush_pending_stmts (loop_exit);
    1678        34215 :       set_immediate_dominator (CDI_DOMINATORS, new_preheader, loop_exit->src);
    1679              : 
    1680              :       /* If we ended up choosing an exit leading to a path not using memory
    1681              :          we can end up without a virtual LC PHI.  Create it when it is
    1682              :          needed because of the epilog loop continuation.  */
    1683        34215 :       if (need_virtual_phi && !get_virtual_phi (loop_exit->dest))
    1684              :         {
    1685            8 :           tree header_def = gimple_phi_result (get_virtual_phi (loop->header));
    1686            8 :           gphi *vphi = create_phi_node (copy_ssa_name (header_def),
    1687              :                                         new_preheader);
    1688            8 :           add_phi_arg (vphi, get_live_virtual_operand_on_edge (loop_exit),
    1689              :                        loop_exit, UNKNOWN_LOCATION);
    1690              :         }
    1691              : 
    1692        34215 :       basic_block main_loop_exit_block = new_preheader;
    1693        34215 :       basic_block alt_loop_exit_block = new_preheader;
    1694              :       /* When we redirect the other exits create the CFG
    1695              :          below to funnel everything through the merge block:
    1696              :                    | loop_exit               | alt1   | altN
    1697              :                    v                         v   ...  v
    1698              :             main_loop_exit_block:       alt_loop_exit_block:
    1699              :                    |                      /
    1700              :                    v                     v
    1701              :             new_preheader:
    1702              :          where in the new preheader we need merge PHIs for
    1703              :          the continuation values into the epilogue header.
    1704              :          Do not bother with exit PHIs for the early exits but
    1705              :          their live virtual operand.  We'll fix up things below.  */
    1706        34215 :       if (redirect_multiple_exits_p || uncounted_p)
    1707              :         {
    1708          676 :           edge loop_e = single_succ_edge (new_preheader);
    1709          676 :           new_preheader = split_edge (loop_e);
    1710              : 
    1711          676 :         if (redirect_exits)
    1712              :           {
    1713          670 :             gphi *vphi = NULL;
    1714          670 :             alt_loop_exit_block = new_preheader;
    1715         3482 :             for (auto exit : loop_exits)
    1716         1472 :               if (exit != loop_exit)
    1717              :                 {
    1718          802 :                   tree vphi_def = NULL_TREE;
    1719          802 :                   if (gphi *evphi = get_virtual_phi (exit->dest))
    1720          495 :                     vphi_def = gimple_phi_arg_def_from_edge (evphi, exit);
    1721          802 :                   edge res
    1722          802 :                     = redirect_edge_and_branch (exit, alt_loop_exit_block);
    1723          802 :                   gcc_assert (res == exit);
    1724          802 :                   redirect_edge_var_map_clear (exit);
    1725              : 
    1726          802 :                   if (alt_loop_exit_block == new_preheader)
    1727          645 :                     alt_loop_exit_block = split_edge (exit);
    1728          802 :                   if (!need_virtual_phi)
    1729          315 :                     continue;
    1730              : 
    1731              :                   /* When the edge has no virtual LC PHI get at the live
    1732              :                      virtual operand by other means.  */
    1733          487 :                   if (!vphi_def)
    1734            2 :                     vphi_def = get_live_virtual_operand_on_edge (exit);
    1735              : 
    1736          487 :                   if (!vphi)
    1737          441 :                     vphi = create_phi_node (copy_ssa_name (vphi_def),
    1738              :                                           alt_loop_exit_block);
    1739              :                   else
    1740              :                     /* Edge redirection might re-allocate the PHI node
    1741              :                        so we have to rediscover it.  */
    1742           46 :                     vphi = get_virtual_phi (alt_loop_exit_block);
    1743          487 :                   add_phi_arg (vphi, vphi_def, exit, UNKNOWN_LOCATION);
    1744              :                 }
    1745              :           }
    1746              : 
    1747          676 :           set_immediate_dominator (CDI_DOMINATORS, new_preheader,
    1748              :                                    loop->header);
    1749              : 
    1750              :           /* Fix up the profile counts of the new exit blocks.
    1751              :              main_loop_exit_block was created by duplicating the
    1752              :              preheader, so needs its count scaling according to the main
    1753              :              exit edge's probability.  The remaining count from the
    1754              :              preheader goes to the alt_loop_exit_block, since all
    1755              :              alternative exits have been redirected there.  */
    1756          676 :           main_loop_exit_block->count = loop_exit->count ();
    1757          676 :           alt_loop_exit_block->count
    1758          676 :             = preheader->count - main_loop_exit_block->count;
    1759              :         }
    1760              : 
    1761              :       /* Adjust the epilog loop PHI entry values to continue iteration.
    1762              :          This adds remaining necessary LC PHI nodes to the main exit
    1763              :          and creates merge PHIs when we have multiple exits with
    1764              :          their appropriate continuation.  */
    1765        34215 :       if (flow_loops)
    1766              :         {
    1767        34215 :           edge loop_entry = single_succ_edge (new_preheader);
    1768        34215 :           bool peeled_iters = (uncounted_p
    1769        34215 :                                || single_pred (loop->latch) != loop_exit->src);
    1770              : 
    1771              :           /* Record the new SSA names in the cache so that we can skip
    1772              :              materializing them again when we fill in the rest of the LC SSA
    1773              :              variables.  */
    1774        34215 :           hash_map <tree, tree> new_phi_args;
    1775        34215 :           for (auto psi = gsi_start_phis (main_loop_exit_block);
    1776        80892 :                !gsi_end_p (psi); gsi_next (&psi))
    1777              :             {
    1778        46677 :               gphi *phi = *psi;
    1779        46677 :               tree new_arg = gimple_phi_arg_def_from_edge (phi, loop_exit);
    1780        46677 :               if (TREE_CODE (new_arg) != SSA_NAME)
    1781          288 :                 continue;
    1782              : 
    1783              :               /* If the loop doesn't have a virtual def then only possibly keep
    1784              :                  the epilog LC PHI for it and avoid creating new defs.  */
    1785        46478 :               if (virtual_operand_p (new_arg) && !need_virtual_phi)
    1786              :                 {
    1787           89 :                   auto gsi = gsi_for_stmt (phi);
    1788           89 :                   remove_phi_node (&gsi, true);
    1789           89 :                   continue;
    1790           89 :                 }
    1791              : 
    1792              :               /* If we decided not to remove the PHI node we should also not
    1793              :                  rematerialize it later on.  */
    1794        46389 :               new_phi_args.put (new_arg, gimple_phi_result (phi));
    1795              :             }
    1796              : 
    1797              :           /* Create the merge PHI nodes in new_preheader and populate the
    1798              :              arguments for the exits.  */
    1799        34215 :           if (redirect_multiple_exits_p)
    1800              :             {
    1801          645 :               for (auto gsi_from = gsi_start_phis (loop->header),
    1802          645 :                    gsi_to = gsi_start_phis (new_loop->header);
    1803         2336 :                    !gsi_end_p (gsi_from) && !gsi_end_p (gsi_to);
    1804         1691 :                    gsi_next (&gsi_from), gsi_next (&gsi_to))
    1805              :                 {
    1806         1691 :                   gimple *from_phi = gsi_stmt (gsi_from);
    1807         1691 :                   gimple *to_phi = gsi_stmt (gsi_to);
    1808              : 
    1809              :                   /* When the vector loop is peeled then we need to use the
    1810              :                      value at start of the loop, otherwise the main loop exit
    1811              :                      should use the final iter value.  */
    1812         1691 :                   tree new_arg;
    1813         1691 :                   if (peeled_iters)
    1814          105 :                     new_arg = gimple_phi_result (from_phi);
    1815              :                   else
    1816         1586 :                     new_arg = PHI_ARG_DEF_FROM_EDGE (from_phi,
    1817              :                                                      loop_latch_edge (loop));
    1818              : 
    1819              :                   /* Check if we've already created a new phi node during edge
    1820              :                      redirection and re-use it if so.  Otherwise create a
    1821              :                      LC PHI node to feed the merge PHI.  */
    1822         1691 :                   tree *res;
    1823         3382 :                   if (virtual_operand_p (new_arg))
    1824              :                     {
    1825              :                       /* Use the existing virtual LC SSA from exit block.  */
    1826          441 :                       gphi *vphi = get_virtual_phi (main_loop_exit_block);
    1827          441 :                       new_arg = gimple_phi_result (vphi);
    1828              :                     }
    1829         1250 :                   else if ((res = new_phi_args.get (new_arg)))
    1830          102 :                     new_arg = *res;
    1831              :                   else
    1832              :                     {
    1833              :                       /* Create the LC PHI node for the exit.  */
    1834         1148 :                       tree new_def = copy_ssa_name (new_arg);
    1835         1148 :                       gphi *lc_phi
    1836         1148 :                           = create_phi_node (new_def, main_loop_exit_block);
    1837         1148 :                       SET_PHI_ARG_DEF (lc_phi, 0, new_arg);
    1838         1148 :                       new_arg = new_def;
    1839              :                     }
    1840              : 
    1841              :                   /* Create the PHI node in the merge block merging the
    1842              :                      main and early exit values.  */
    1843         1691 :                   tree new_res = copy_ssa_name (gimple_phi_result (from_phi));
    1844         1691 :                   gphi *lcssa_phi = create_phi_node (new_res, new_preheader);
    1845         1691 :                   edge main_e = single_succ_edge (main_loop_exit_block);
    1846         1691 :                   SET_PHI_ARG_DEF_ON_EDGE (lcssa_phi, main_e, new_arg);
    1847              : 
    1848              :                   /* And adjust the epilog entry value.  */
    1849         1691 :                   adjust_phi_and_debug_stmts (to_phi, loop_entry, new_res);
    1850              :                 }
    1851              :             }
    1852              : 
    1853          645 :           if (redirect_multiple_exits_p)
    1854              :             {
    1855              :               /* After creating the merge PHIs handle the early exits those
    1856              :                  should use the values at the start of the loop.  */
    1857          645 :               for (auto gsi_from = gsi_start_phis (loop->header),
    1858          645 :                    gsi_to = gsi_start_phis (new_preheader);
    1859         2336 :                    !gsi_end_p (gsi_from) && !gsi_end_p (gsi_to);
    1860         1691 :                    gsi_next (&gsi_from), gsi_next (&gsi_to))
    1861              :                 {
    1862         1691 :                   gimple *from_phi = gsi_stmt (gsi_from);
    1863         1691 :                   gimple *to_phi = gsi_stmt (gsi_to);
    1864              : 
    1865              :                   /* Now update the virtual PHI nodes with the right value.  */
    1866         1691 :                   tree alt_arg = gimple_phi_result (from_phi);
    1867         3382 :                   if (virtual_operand_p (alt_arg))
    1868              :                     {
    1869          441 :                       gphi *vphi = get_virtual_phi (alt_loop_exit_block);
    1870          441 :                       alt_arg = gimple_phi_result (vphi);
    1871              :                     }
    1872              :                   /* For other live args we didn't create LC PHI nodes.
    1873              :                      Do so here.  */
    1874              :                   else
    1875              :                     {
    1876         1250 :                       tree alt_def = copy_ssa_name (alt_arg);
    1877         1250 :                       gphi *lc_phi
    1878         1250 :                         = create_phi_node (alt_def, alt_loop_exit_block);
    1879         4063 :                       for (unsigned i = 0; i < gimple_phi_num_args (lc_phi);
    1880              :                            ++i)
    1881         1563 :                         SET_PHI_ARG_DEF (lc_phi, i, alt_arg);
    1882              :                       alt_arg = alt_def;
    1883              :                     }
    1884              : 
    1885              :                   /* The merge PHIs live in NEW_PREHEADER; their
    1886              :                      alternative argument always comes from the
    1887              :                      successor edge of ALT_LOOP_EXIT_BLOCK.  */
    1888         1691 :                   edge alt_e = single_succ_edge (alt_loop_exit_block);
    1889         1691 :                   SET_PHI_ARG_DEF_ON_EDGE (to_phi, alt_e, alt_arg);
    1890              :                 }
    1891              :             }
    1892              : 
    1893              :           /* For the single exit case only create the missing LC PHI nodes
    1894              :              for the continuation of the loop IVs that are not also already
    1895              :              reductions and thus had LC PHI nodes on the exit already.  When
    1896              :              we are not redirecting the alternative exits the layout is:
    1897              : 
    1898              :                    loop_exit ---> new_preheader ---> epilog
    1899              :                    alt_exit ---------------> original dest
    1900              :            */
    1901          645 :           if (!redirect_multiple_exits_p)
    1902              :             {
    1903        33570 :               for (auto gsi_from = gsi_start_phis (loop->header),
    1904        33570 :                    gsi_to = gsi_start_phis (new_loop->header);
    1905       127783 :                    !gsi_end_p (gsi_from) && !gsi_end_p (gsi_to);
    1906        94213 :                    gsi_next (&gsi_from), gsi_next (&gsi_to))
    1907              :                 {
    1908        94213 :                   gimple *from_phi = gsi_stmt (gsi_from);
    1909        94213 :                   gimple *to_phi = gsi_stmt (gsi_to);
    1910        94213 :                   tree new_arg;
    1911              : 
    1912              :                   /* Use the value on the exiting path.  When the exit is from
    1913              :                      the latch edge we want the post-iteration value on that
    1914              :                      edge; when the exit is from the loop header (before the
    1915              :                      latch ever executes) we must use the current header value,
    1916              :                      otherwise we pick up a name that was never defined.  */
    1917        94213 :                   if (!has_multiple_exits_p && !uncounted_p)
    1918        93896 :                     new_arg = PHI_ARG_DEF_FROM_EDGE (from_phi,
    1919              :                                                      loop_latch_edge (loop));
    1920              :                   else
    1921          317 :                     new_arg = gimple_phi_result (from_phi);
    1922              : 
    1923              :                   /* Re-use the virtual LC PHI we already built when we are not
    1924              :                      redirecting the other exits to avoid creating duplicate
    1925              :                      virtual SSA names.  */
    1926       188426 :                   if (virtual_operand_p (new_arg))
    1927              :                     {
    1928        25710 :                       if (gphi *vphi = get_virtual_phi (main_loop_exit_block))
    1929              :                         {
    1930        25710 :                           adjust_phi_and_debug_stmts (to_phi, loop_entry,
    1931              :                                                       gimple_phi_result (vphi));
    1932        43709 :                           continue;
    1933              :                         }
    1934              :                     }
    1935              : 
    1936              :                   /* Check if we've already created a new phi node during edge
    1937              :                      redirection.  If we have, only propagate the value
    1938              :                      downwards.  */
    1939        68503 :                   if (tree *res = new_phi_args.get (new_arg))
    1940              :                     {
    1941              :                       /* Check if the new dest block already contains a use.  */
    1942        17999 :                       gimple *stmt = SSA_NAME_DEF_STMT (*res);
    1943              : 
    1944              :                       /* If the value already exist, just update the destination
    1945              :                          and if it doesn't we want a new node.  */
    1946        17999 :                       if (gimple_bb (stmt) == main_loop_exit_block)
    1947              :                         {
    1948        17999 :                           adjust_phi_and_debug_stmts (to_phi, loop_entry, *res);
    1949        17999 :                           continue;
    1950              :                         }
    1951              :                       else
    1952            0 :                         new_arg = *res;
    1953              :                     }
    1954              : 
    1955        50504 :                   tree new_res = copy_ssa_name (gimple_phi_result (from_phi));
    1956        50504 :                   gphi *lcssa_phi = create_phi_node (new_res, main_loop_exit_block);
    1957        50504 :                   SET_PHI_ARG_DEF (lcssa_phi, loop_exit->dest_idx, new_arg);
    1958        50504 :                   adjust_phi_and_debug_stmts (to_phi, loop_entry, new_res);
    1959              :                 }
    1960              :             }
    1961        34215 :         }
    1962              : 
    1963        34215 :       if (was_imm_dom || duplicate_outer_loop)
    1964        33941 :         set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_exit->src);
    1965              : 
    1966              :       /* And remove the non-necessary forwarder again.  Keep the other
    1967              :          one so we have a proper pre-header for the loop at the exit edge.  */
    1968        34215 :       redirect_edge_pred (single_succ_edge (preheader),
    1969              :                           single_pred (preheader));
    1970        34215 :       delete_basic_block (preheader);
    1971        34215 :       set_immediate_dominator (CDI_DOMINATORS, scalar_loop->header,
    1972        34215 :                                loop_preheader_edge (scalar_loop)->src);
    1973              : 
    1974              :       /* Finally after wiring the new epilogue we need to update its main exit
    1975              :          to the original function exit we recorded.  Other exits are already
    1976              :          correct.  */
    1977        34215 :       if (has_multiple_exits_p || uncounted_p)
    1978              :         {
    1979          888 :           class loop *update_loop = new_loop;
    1980          888 :           doms = get_all_dominated_blocks (CDI_DOMINATORS, loop->header);
    1981        19930 :           for (unsigned i = 0; i < doms.length (); ++i)
    1982        19042 :             if (flow_bb_inside_loop_p (loop, doms[i]))
    1983         2777 :               doms.unordered_remove (i);
    1984              : 
    1985         4566 :           for (edge e : get_loop_exit_edges (update_loop))
    1986              :             {
    1987         1902 :               edge ex;
    1988         1902 :               edge_iterator ei;
    1989         3844 :               FOR_EACH_EDGE (ex, ei, e->dest->succs)
    1990              :                 {
    1991              :                   /* Find the first non-fallthrough block as fall-throughs can't
    1992              :                      dominate other blocks.  */
    1993         1942 :                   if (single_succ_p (ex->dest))
    1994              :                     {
    1995         1072 :                       doms.safe_push (ex->dest);
    1996         1072 :                       ex = single_succ_edge (ex->dest);
    1997              :                     }
    1998         1942 :                   doms.safe_push (ex->dest);
    1999              :                 }
    2000         1902 :               doms.safe_push (e->dest);
    2001          888 :             }
    2002              : 
    2003          888 :           iterate_fix_dominators (CDI_DOMINATORS, doms, false);
    2004          888 :           if (updated_doms)
    2005          888 :             updated_doms->safe_splice (doms);
    2006              :         }
    2007              :     }
    2008              :   else /* Add the copy at entry.  */
    2009              :     {
    2010              :       /* Copy the current loop LC PHI nodes between the original loop exit
    2011              :          block and the new loop header.  This allows us to later split the
    2012              :          preheader block and still find the right LC nodes.  */
    2013         1681 :       if (flow_loops)
    2014          442 :         for (auto gsi_from = gsi_start_phis (new_loop->header),
    2015          442 :              gsi_to = gsi_start_phis (loop->header);
    2016         1366 :              !gsi_end_p (gsi_from) && !gsi_end_p (gsi_to);
    2017          924 :              gsi_next (&gsi_from), gsi_next (&gsi_to))
    2018              :           {
    2019          924 :             gimple *from_phi = gsi_stmt (gsi_from);
    2020          924 :             gimple *to_phi = gsi_stmt (gsi_to);
    2021          924 :             tree new_arg = PHI_ARG_DEF_FROM_EDGE (from_phi,
    2022              :                                                   loop_latch_edge (new_loop));
    2023          924 :             adjust_phi_and_debug_stmts (to_phi, loop_preheader_edge (loop),
    2024              :                                         new_arg);
    2025              :           }
    2026              : 
    2027         1681 :       if (scalar_loop != loop)
    2028              :         {
    2029              :           /* Remove the non-necessary forwarder of scalar_loop again.  */
    2030            4 :           redirect_edge_pred (single_succ_edge (preheader),
    2031              :                               single_pred (preheader));
    2032            4 :           delete_basic_block (preheader);
    2033            4 :           set_immediate_dominator (CDI_DOMINATORS, scalar_loop->header,
    2034            4 :                                    loop_preheader_edge (scalar_loop)->src);
    2035            4 :           preheader = split_edge (loop_preheader_edge (loop));
    2036            4 :           entry_e = single_pred_edge (preheader);
    2037              :         }
    2038              : 
    2039         1681 :       redirect_edge_and_branch_force (entry_e, new_preheader);
    2040         1681 :       flush_pending_stmts (entry_e);
    2041         1681 :       set_immediate_dominator (CDI_DOMINATORS, new_preheader, entry_e->src);
    2042              : 
    2043              : 
    2044              :       /* `vect_set_loop_condition' replaces the condition in the main exit of
    2045              :          loop.  For counted loops, this is the IV counting exit, so in the case
    2046              :          of the prolog loop, we are replacing the old IV counting exit limit of
    2047              :          total loop niters for the new limit of the prolog niters, as desired.
    2048              :          For uncounted loops, we don't have an IV-counting exit to replace, so
    2049              :          we add a dummy exit to be consumed by `vect_set_loop_condition' later
    2050              :          on.  */
    2051         1681 :       if (create_main_e)
    2052              :         {
    2053           31 :           edge to_latch_e = single_pred_edge (new_loop->latch);
    2054           31 :           bool latch_is_false = to_latch_e->flags & EDGE_FALSE_VALUE ? true
    2055              :                                                                      : false;
    2056              : 
    2057              :           /* Add new bb for duplicate exit.  */
    2058           31 :           basic_block bbcond = split_edge (to_latch_e);
    2059           31 :           gimple_stmt_iterator a = gsi_last_bb (bbcond);
    2060              : 
    2061              :           /* Fix flags for the edge leading to the latch.  */
    2062           31 :           to_latch_e = find_edge (bbcond, new_loop->latch);
    2063           31 :           to_latch_e->flags &= ~EDGE_FALLTHRU;
    2064           31 :           to_latch_e->flags |= latch_is_false ? EDGE_FALSE_VALUE
    2065              :                                               : EDGE_TRUE_VALUE;
    2066              : 
    2067              :           /* Build the condition.  */
    2068           31 :           tree cone = build_int_cst (sizetype, 1);
    2069           31 :           tree czero = build_int_cst (sizetype, 0);
    2070           31 :           gcond *cond_copy = gimple_build_cond (NE_EXPR, cone, czero, NULL_TREE,
    2071              :                                                 NULL_TREE);
    2072              : 
    2073           31 :           gsi_insert_after (&a, cond_copy, GSI_NEW_STMT);
    2074              : 
    2075              :           /* Add edge for exiting the loop via new condition.  */
    2076           38 :           edge dup_exit = make_edge (bbcond, new_exit->dest, latch_is_false
    2077              :                                 ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE);
    2078              : 
    2079           31 :           profile_probability probability = profile_probability::even ();
    2080           31 :           to_latch_e->probability = dup_exit->probability = probability;
    2081              : 
    2082           31 :           set_immediate_dominator (CDI_DOMINATORS, dup_exit->src,
    2083              :                                    new_exit->src);
    2084           31 :           new_exit = dup_exit;
    2085           31 :           *new_e = new_exit;
    2086              :         }
    2087              : 
    2088         1681 :       redirect_edge_and_branch_force (new_exit, preheader);
    2089         1681 :       flush_pending_stmts (new_exit);
    2090         1681 :       set_immediate_dominator (CDI_DOMINATORS, preheader, new_exit->src);
    2091              : 
    2092              :       /* And remove the non-necessary forwarder again.  Keep the other
    2093              :          one so we have a proper pre-header for the loop at the exit edge.  */
    2094         1681 :       redirect_edge_pred (single_succ_edge (new_preheader),
    2095              :                           single_pred (new_preheader));
    2096         1681 :       delete_basic_block (new_preheader);
    2097         1681 :       set_immediate_dominator (CDI_DOMINATORS, new_loop->header,
    2098         1681 :                                loop_preheader_edge (new_loop)->src);
    2099              : 
    2100              :       /* Update dominators for multiple exits.  */
    2101         1681 :       if (has_multiple_exits_p || create_main_e)
    2102              :         {
    2103         1173 :           for (edge alt_e : loop_exits)
    2104              :             {
    2105          465 :               if ((alt_e == loop_exit) && !create_main_e)
    2106          205 :                 continue;
    2107          260 :               basic_block old_dom
    2108          260 :                 = get_immediate_dominator (CDI_DOMINATORS, alt_e->dest);
    2109          260 :               if (flow_bb_inside_loop_p (loop, old_dom))
    2110              :                 {
    2111          101 :                   auto_vec<basic_block, 8> queue;
    2112          101 :                   for (auto son = first_dom_son (CDI_DOMINATORS, old_dom);
    2113          327 :                        son; son = next_dom_son (CDI_DOMINATORS, son))
    2114          226 :                     if (!flow_bb_inside_loop_p (loop, son))
    2115          125 :                       queue.safe_push (son);
    2116          428 :                   for (auto son : queue)
    2117          125 :                     set_immediate_dominator (CDI_DOMINATORS,
    2118              :                                              son, get_bb_copy (old_dom));
    2119          101 :                 }
    2120              :             }
    2121              :         }
    2122              : 
    2123              :       /* When loop_exit != scalar_exit due to if-conversion loop versioning,
    2124              :          the `scalar_exit' now has two incoming edges, one from the if-converted
    2125              :          and one from the peeled prolog loop.  It is therefore dominated by a
    2126              :          common block between these.  Update its dominator accordingly.  */
    2127          236 :       if (create_main_e && loop_exit != scalar_exit)
    2128            0 :         set_immediate_dominator (CDI_DOMINATORS, scalar_exit->dest,
    2129              :                                  recompute_dominator (CDI_DOMINATORS,
    2130              :                                                       scalar_exit->dest));
    2131              :     }
    2132              : 
    2133        35896 :   free (new_bbs);
    2134        35896 :   free (bbs);
    2135              : 
    2136        35896 :   checking_verify_dominators (CDI_DOMINATORS);
    2137              : 
    2138        35896 :   return new_loop;
    2139        35896 : }
    2140              : 
    2141              : 
    2142              : /* Given the condition expression COND, put it as the last statement of
    2143              :    GUARD_BB; set both edges' probability; set dominator of GUARD_TO to
    2144              :    DOM_BB; return the skip edge.  GUARD_TO is the target basic block to
    2145              :    skip the loop.  PROBABILITY is the skip edge's probability.  Mark the
    2146              :    new edge as irreducible if IRREDUCIBLE_P is true.  */
    2147              : 
    2148              : static edge
    2149        51788 : slpeel_add_loop_guard (basic_block guard_bb, tree cond,
    2150              :                        basic_block guard_to, basic_block dom_bb,
    2151              :                        profile_probability probability, bool irreducible_p)
    2152              : {
    2153        51788 :   gimple_stmt_iterator gsi;
    2154        51788 :   edge new_e, enter_e;
    2155        51788 :   gcond *cond_stmt;
    2156        51788 :   gimple_seq gimplify_stmt_list = NULL;
    2157              : 
    2158        51788 :   enter_e = EDGE_SUCC (guard_bb, 0);
    2159        51788 :   enter_e->flags &= ~EDGE_FALLTHRU;
    2160        51788 :   enter_e->flags |= EDGE_FALSE_VALUE;
    2161        51788 :   gsi = gsi_last_bb (guard_bb);
    2162              : 
    2163        51788 :   cond = force_gimple_operand_1 (cond, &gimplify_stmt_list,
    2164              :                                  is_gimple_condexpr_for_cond, NULL_TREE);
    2165        51788 :   if (gimplify_stmt_list)
    2166        23286 :     gsi_insert_seq_after (&gsi, gimplify_stmt_list, GSI_NEW_STMT);
    2167              : 
    2168        51788 :   cond_stmt = gimple_build_cond_from_tree (cond, NULL_TREE, NULL_TREE);
    2169        51788 :   gsi = gsi_last_bb (guard_bb);
    2170        51788 :   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
    2171              : 
    2172              :   /* Add new edge to connect guard block to the merge/loop-exit block.  */
    2173        51788 :   new_e = make_edge (guard_bb, guard_to, EDGE_TRUE_VALUE);
    2174              : 
    2175        51788 :   new_e->probability = probability;
    2176        51788 :   if (irreducible_p)
    2177           14 :     new_e->flags |= EDGE_IRREDUCIBLE_LOOP;
    2178              : 
    2179        51788 :   enter_e->probability = probability.invert ();
    2180        51788 :   set_immediate_dominator (CDI_DOMINATORS, guard_to, dom_bb);
    2181              : 
    2182              :   /* Split enter_e to preserve LOOPS_HAVE_PREHEADERS.  */
    2183        51788 :   if (enter_e->dest->loop_father->header == enter_e->dest)
    2184          491 :     split_edge (enter_e);
    2185              : 
    2186        51788 :   return new_e;
    2187              : }
    2188              : 
    2189              : 
    2190              : /* This function verifies that the following restrictions apply to LOOP:
    2191              :    (1) it consists of exactly 2 basic blocks - header, and an empty latch
    2192              :        for innermost loop and 5 basic blocks for outer-loop.
    2193              :    (2) it is single entry, single exit
    2194              :    (3) its exit condition is the last stmt in the header
    2195              :    (4) E is the entry/exit edge of LOOP.
    2196              :  */
    2197              : 
    2198              : bool
    2199       530376 : slpeel_can_duplicate_loop_p (const class loop *loop, const_edge exit_e,
    2200              :                              const_edge e)
    2201              : {
    2202       530376 :   edge entry_e = loop_preheader_edge (loop);
    2203       530376 :   gcond *orig_cond = get_loop_exit_condition (exit_e);
    2204       530376 :   gimple_stmt_iterator loop_exit_gsi = gsi_last_bb (exit_e->src);
    2205              : 
    2206              :   /* All loops have an outer scope; the only case loop->outer is NULL is for
    2207              :      the function itself.  */
    2208       530376 :   if (!loop_outer (loop)
    2209       530376 :       || !empty_block_p (loop->latch)
    2210              :       || !exit_e
    2211              :       /* Verify that new loop exit condition can be trivially modified.  */
    2212       530376 :       || (!orig_cond || orig_cond != gsi_stmt (loop_exit_gsi))
    2213      1060752 :       || (e != exit_e && e != entry_e))
    2214              :     return false;
    2215              : 
    2216       530376 :   basic_block *bbs = XNEWVEC (basic_block, loop->num_nodes);
    2217       530376 :   get_loop_body_with_size (loop, bbs, loop->num_nodes);
    2218       530376 :   bool ret = can_copy_bbs_p (bbs, loop->num_nodes);
    2219       530376 :   free (bbs);
    2220       530376 :   return ret;
    2221              : }
    2222              : 
    2223              : /* Function find_loop_location.
    2224              : 
    2225              :    Extract the location of the loop in the source code.
    2226              :    If the loop is not well formed for vectorization, an estimated
    2227              :    location is calculated.
    2228              :    Return the loop location if succeed and NULL if not.  */
    2229              : 
    2230              : dump_user_location_t
    2231      3679478 : find_loop_location (class loop *loop)
    2232              : {
    2233      3679478 :   gimple *stmt = NULL;
    2234      3679478 :   basic_block bb;
    2235      3679478 :   gimple_stmt_iterator si;
    2236              : 
    2237      3679478 :   if (!loop)
    2238            0 :     return dump_user_location_t ();
    2239              : 
    2240              :   /* For the root of the loop tree return the function location.  */
    2241      3679478 :   if (!loop_outer (loop))
    2242            0 :     return dump_user_location_t::from_function_decl (cfun->decl);
    2243              : 
    2244      3679478 :   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
    2245              :     {
    2246              :       /* We only care about the loop location, so use any exit with location
    2247              :          information.  */
    2248     11533787 :       for (edge e : get_loop_exit_edges (loop))
    2249              :         {
    2250      3777742 :           stmt = get_loop_exit_condition (e);
    2251              : 
    2252      3777742 :           if (stmt
    2253      3777742 :               && LOCATION_LOCUS (gimple_location (stmt)) > BUILTINS_LOCATION)
    2254      3222259 :             return stmt;
    2255      3679478 :         }
    2256              :     }
    2257              : 
    2258              :   /* If we got here the loop is probably not "well formed",
    2259              :      try to estimate the loop location */
    2260              : 
    2261       457219 :   if (!loop->header)
    2262            0 :     return dump_user_location_t ();
    2263              : 
    2264       457219 :   bb = loop->header;
    2265              : 
    2266      1616923 :   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
    2267              :     {
    2268      1040149 :       stmt = gsi_stmt (si);
    2269      1040149 :       if (LOCATION_LOCUS (gimple_location (stmt)) > BUILTINS_LOCATION)
    2270       337664 :         return stmt;
    2271              :     }
    2272              : 
    2273       119555 :   return dump_user_location_t ();
    2274              : }
    2275              : 
    2276              : /* Return true if the phi described by STMT_INFO defines an IV of the
    2277              :    loop to be vectorized.  */
    2278              : 
    2279              : static bool
    2280      1419615 : iv_phi_p (stmt_vec_info stmt_info)
    2281              : {
    2282      1419615 :   gphi *phi = as_a <gphi *> (stmt_info->stmt);
    2283      2839230 :   if (virtual_operand_p (PHI_RESULT (phi)))
    2284              :     return false;
    2285              : 
    2286      1129247 :   if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_reduction_def
    2287      1129247 :       || STMT_VINFO_DEF_TYPE (stmt_info) == vect_double_reduction_def)
    2288       160293 :     return false;
    2289              : 
    2290              :   return true;
    2291              : }
    2292              : 
    2293              : /* Return true if vectorizer can peel for nonlinear iv.  */
    2294              : static bool
    2295        12026 : vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo,
    2296              :                               stmt_vec_info stmt_info)
    2297              : {
    2298        12026 :   enum vect_induction_op_type induction_type
    2299              :     = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (stmt_info);
    2300        12026 :   tree niters_skip;
    2301              :   /* Init_expr will be update by vect_update_ivs_after_vectorizer,
    2302              :      if niters or vf is unknown:
    2303              :      For shift, when shift mount >= precision, there would be UD.
    2304              :      For mult, don't known how to generate
    2305              :      init_expr * pow (step, niters) for variable niters.
    2306              :      For neg unknown niters are ok, since niters of vectorized main loop
    2307              :      will always be multiple of 2.
    2308              :      See also PR113163,  PR114196 and PR114485.  */
    2309        12026 :   if (!LOOP_VINFO_VECT_FACTOR (loop_vinfo).is_constant ()
    2310        12026 :       || LOOP_VINFO_USING_PARTIAL_VECTORS_P (loop_vinfo)
    2311        12026 :       || (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
    2312         7065 :           && induction_type != vect_step_op_neg))
    2313              :     {
    2314         6866 :       if (dump_enabled_p ())
    2315           12 :         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
    2316              :                          "Peeling for epilogue is not supported"
    2317              :                          " for this nonlinear induction"
    2318              :                          " when iteration count is unknown or"
    2319              :                          " when using partial vectorization.\n");
    2320              :       return false;
    2321              :     }
    2322              : 
    2323         5160 :   if (LOOP_VINFO_EARLY_BREAKS (loop_vinfo)
    2324          512 :       && (induction_type == vect_step_op_mul
    2325              :           || induction_type == vect_step_op_shl
    2326          512 :           || induction_type == vect_step_op_shr))
    2327              :     {
    2328          512 :       if (dump_enabled_p ())
    2329          412 :         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
    2330              :                          "Peeling for is not supported for nonlinear %s"
    2331              :                          " induction using partial vectorization.\n",
    2332              :                          induction_type == vect_step_op_mul
    2333              :                          ? "mult" : "shift");
    2334              :       return false;
    2335              :     }
    2336              : 
    2337              :   /* Avoid compile time hog on vect_peel_nonlinear_iv_init.  */
    2338         4648 :   if (induction_type == vect_step_op_mul)
    2339              :     {
    2340          407 :       tree step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info);
    2341          407 :       tree type = TREE_TYPE (step_expr);
    2342              : 
    2343          808 :       if (wi::exact_log2 (wi::to_wide (step_expr)) == -1
    2344          407 :           && LOOP_VINFO_INT_NITERS(loop_vinfo) >= TYPE_PRECISION (type))
    2345              :         {
    2346            6 :           if (dump_enabled_p ())
    2347            6 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
    2348              :                              "Avoid compile time hog on"
    2349              :                              " vect_peel_nonlinear_iv_init"
    2350              :                              " for nonlinear induction vec_step_op_mul"
    2351              :                              " when iteration count is too big.\n");
    2352              :           return false;
    2353              :         }
    2354              :     }
    2355              : 
    2356              :   /* Also doesn't support peel for neg when niter is variable.
    2357              :      ??? generate something like niter_expr & 1 ? init_expr : -init_expr?  */
    2358         4642 :   niters_skip = LOOP_VINFO_MASK_SKIP_NITERS (loop_vinfo);
    2359         4642 :   if ((niters_skip != NULL_TREE
    2360            0 :        && (TREE_CODE (niters_skip) != INTEGER_CST
    2361            0 :            || (HOST_WIDE_INT) TREE_INT_CST_LOW (niters_skip) < 0))
    2362         4642 :       || (!vect_use_loop_mask_for_alignment_p (loop_vinfo)
    2363         4642 :           && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0))
    2364              :     {
    2365            4 :       if (dump_enabled_p ())
    2366            0 :         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
    2367              :                          "Peeling for alignment is not supported"
    2368              :                          " for nonlinear induction when niters_skip"
    2369              :                          " is not constant.\n");
    2370              :       return false;
    2371              :     }
    2372              : 
    2373              :   return true;
    2374              : }
    2375              : 
    2376              : /* Function vect_can_advance_ivs_p
    2377              : 
    2378              :    In case the number of iterations that LOOP iterates is unknown at compile
    2379              :    time, an epilog loop will be generated, and the loop induction variables
    2380              :    (IVs) will be "advanced" to the value they are supposed to take just before
    2381              :    the epilog loop.  Here we check that the access function of the loop IVs
    2382              :    and the expression that represents the loop bound are simple enough.
    2383              :    These restrictions will be relaxed in the future.  */
    2384              : 
    2385              : bool
    2386       538785 : vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
    2387              : {
    2388       538785 :   class loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    2389       538785 :   basic_block bb = loop->header;
    2390       538785 :   gphi_iterator gsi;
    2391              : 
    2392              :   /* Analyze phi functions of the loop header.  */
    2393              : 
    2394       538785 :   if (dump_enabled_p ())
    2395        27432 :     dump_printf_loc (MSG_NOTE, vect_location, "vect_can_advance_ivs_p:\n");
    2396      1851909 :   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    2397              :     {
    2398      1322020 :       tree evolution_part;
    2399      1322020 :       enum vect_induction_op_type induction_type;
    2400              : 
    2401      1322020 :       gphi *phi = gsi.phi ();
    2402      1322020 :       stmt_vec_info phi_info = loop_vinfo->lookup_stmt (phi);
    2403      1322020 :       if (dump_enabled_p ())
    2404        77315 :         dump_printf_loc (MSG_NOTE, vect_location, "Analyze phi: %G",
    2405              :                          phi_info->stmt);
    2406              : 
    2407              :       /* Skip virtual phi's. The data dependences that are associated with
    2408              :          virtual defs/uses (i.e., memory accesses) are analyzed elsewhere.
    2409              : 
    2410              :          Skip reduction phis.  */
    2411      1322020 :       if (!iv_phi_p (phi_info))
    2412              :         {
    2413       406419 :           if (dump_enabled_p ())
    2414        27384 :             dump_printf_loc (MSG_NOTE, vect_location,
    2415              :                              "reduc or virtual phi. skip.\n");
    2416       406419 :           continue;
    2417              :         }
    2418              : 
    2419       915601 :       induction_type = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (phi_info);
    2420       915601 :       if (induction_type != vect_step_op_add)
    2421              :         {
    2422        12026 :           if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, phi_info))
    2423              :             return false;
    2424              : 
    2425         4638 :           continue;
    2426              :         }
    2427              : 
    2428              :       /* Analyze the evolution function.  */
    2429              : 
    2430       903575 :       evolution_part = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (phi_info);
    2431       903575 :       if (evolution_part == NULL_TREE)
    2432              :         {
    2433         1492 :           if (dump_enabled_p ())
    2434           81 :             dump_printf (MSG_MISSED_OPTIMIZATION,
    2435              :                          "No access function or evolution.\n");
    2436              :           return false;
    2437              :         }
    2438              : 
    2439              :       /* FORNOW: We do not transform initial conditions of IVs
    2440              :          which evolution functions are not invariants in the loop.  */
    2441              : 
    2442       902083 :       if (!expr_invariant_in_loop_p (loop, evolution_part))
    2443              :         {
    2444           16 :           if (dump_enabled_p ())
    2445            0 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
    2446              :                              "evolution not invariant in loop.\n");
    2447              :           return false;
    2448              :         }
    2449              : 
    2450              :       /* FORNOW: We do not transform initial conditions of IVs
    2451              :          which evolution functions are a polynomial of degree >= 2.  */
    2452              : 
    2453      2215191 :       if (tree_is_chrec (evolution_part))
    2454              :         {
    2455            0 :           if (dump_enabled_p ())
    2456            0 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
    2457              :                              "evolution is chrec.\n");
    2458              :           return false;
    2459              :         }
    2460              :     }
    2461              : 
    2462              :   return true;
    2463              : }
    2464              : 
    2465              : 
    2466              : /*   Function vect_update_ivs_after_vectorizer.
    2467              : 
    2468              :      "Advance" the induction variables of LOOP to the value they should take
    2469              :      after the execution of LOOP.  This is currently necessary because the
    2470              :      vectorizer does not handle induction variables that are used after the
    2471              :      loop.  Such a situation occurs when the last iterations of LOOP are
    2472              :      peeled, because:
    2473              :      1. We introduced new uses after LOOP for IVs that were not originally used
    2474              :         after LOOP: the IVs of LOOP are now used by an epilog loop.
    2475              :      2. LOOP is going to be vectorized; this means that it will iterate N/VF
    2476              :         times, whereas the loop IVs should be bumped N times.
    2477              : 
    2478              :      Input:
    2479              :      - LOOP - a loop that is going to be vectorized. The last few iterations
    2480              :               of LOOP were peeled.
    2481              :      - NITERS - the number of iterations that LOOP executes (before it is
    2482              :                 vectorized). i.e, the number of times the ivs should be bumped.
    2483              :      - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
    2484              :                   coming out from LOOP on which there are uses of the LOOP ivs
    2485              :                   (this is the path from LOOP->exit to epilog_loop->preheader).
    2486              : 
    2487              :                   The new definitions of the ivs are placed in LOOP->exit.
    2488              :                   The phi args associated with the edge UPDATE_E in the bb
    2489              :                   UPDATE_E->dest are updated accordingly.
    2490              : 
    2491              :      - EARLY_EXIT_P - Indicates whether the exit is an early exit rather than
    2492              :                       the main latch exit.
    2493              : 
    2494              :      Assumption 1: Like the rest of the vectorizer, this function assumes
    2495              :      a single loop exit that has a single predecessor.
    2496              : 
    2497              :      Assumption 2: The phi nodes in the LOOP header and in update_bb are
    2498              :      organized in the same order.
    2499              : 
    2500              :      Assumption 3: The access function of the ivs is simple enough (see
    2501              :      vect_can_advance_ivs_p).  This assumption will be relaxed in the future.
    2502              : 
    2503              :      Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
    2504              :      coming out of LOOP on which the ivs of LOOP are used (this is the path
    2505              :      that leads to the epilog loop; other paths skip the epilog loop).  This
    2506              :      path starts with the edge UPDATE_E, and its destination (denoted update_bb)
    2507              :      needs to have its phis updated.
    2508              :  */
    2509              : 
    2510              : static void
    2511        34860 : vect_update_ivs_after_vectorizer (loop_vec_info loop_vinfo,
    2512              :                                   tree niters, edge update_e,
    2513              :                                   bool early_exit_p)
    2514              : {
    2515        34860 :   gphi_iterator gsi, gsi1;
    2516        34860 :   class loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    2517        34860 :   basic_block update_bb = update_e->dest;
    2518        34860 :   basic_block exit_bb = update_e->src;
    2519              :   /* Check to see if this is an empty loop pre-header block.  If it exists
    2520              :      we need to use the edge from that block -> loop header for updates but
    2521              :      must use the original exit_bb to add any new adjustment because there
    2522              :      can be a skip_epilog edge bypassing the epilog and so the loop pre-header
    2523              :      too.  */
    2524        34940 :   if (empty_block_p (update_bb) && single_succ_p (update_bb))
    2525              :     {
    2526           80 :       update_e = single_succ_edge (update_bb);
    2527           80 :       update_bb = update_e->dest;
    2528              :     }
    2529        34860 :   gimple_stmt_iterator last_gsi = gsi_last_bb (exit_bb);
    2530              : 
    2531        34860 :   for (gsi = gsi_start_phis (loop->header), gsi1 = gsi_start_phis (update_bb);
    2532       132455 :        !gsi_end_p (gsi) && !gsi_end_p (gsi1);
    2533        97595 :        gsi_next (&gsi), gsi_next (&gsi1))
    2534              :     {
    2535        97595 :       tree init_expr;
    2536        97595 :       tree step_expr;
    2537        97595 :       tree type;
    2538        97595 :       tree var, ni, ni_name;
    2539              : 
    2540        97595 :       gphi *phi = gsi.phi ();
    2541        97595 :       gphi *phi1 = gsi1.phi ();
    2542        97595 :       stmt_vec_info phi_info = loop_vinfo->lookup_stmt (phi);
    2543        97595 :       if (dump_enabled_p ())
    2544        13126 :         dump_printf_loc (MSG_NOTE, vect_location,
    2545              :                          "vect_update_ivs_after_vectorizer: phi: %G",
    2546              :                          (gimple *) phi);
    2547              : 
    2548              :       /* Skip reduction and virtual phis.  */
    2549        97595 :       if (!iv_phi_p (phi_info))
    2550              :         {
    2551        44242 :           if (dump_enabled_p ())
    2552         5130 :             dump_printf_loc (MSG_NOTE, vect_location,
    2553              :                              "reduc or virtual phi. skip.\n");
    2554        44242 :           continue;
    2555              :         }
    2556              : 
    2557        53353 :       type = TREE_TYPE (gimple_phi_result (phi));
    2558        53353 :       step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (phi_info);
    2559        53353 :       step_expr = unshare_expr (step_expr);
    2560              : 
    2561              :       /* FORNOW: We do not support IVs whose evolution function is a polynomial
    2562              :          of degree >= 2 or exponential.  */
    2563        53353 :       gcc_assert (!tree_is_chrec (step_expr));
    2564              : 
    2565        53353 :       init_expr = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
    2566        53353 :       gimple_seq stmts = NULL;
    2567        53353 :       enum vect_induction_op_type induction_type
    2568              :         = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (phi_info);
    2569              : 
    2570        53353 :       if (induction_type == vect_step_op_add)
    2571              :         {
    2572              :           /* Use an unsigned type because we compute 'off' without
    2573              :              accounting for 'init_expr', thus the computation might
    2574              :              overflow.  Note we can also have FP inductions.  */
    2575       106440 :           tree ctype = (INTEGRAL_TYPE_P (TREE_TYPE (step_expr))
    2576       106434 :                         ? unsigned_type_for (TREE_TYPE (step_expr))
    2577        53220 :                         : TREE_TYPE (step_expr));
    2578        53220 :           tree off = fold_build2 (MULT_EXPR, ctype,
    2579              :                                   fold_convert (ctype, niters),
    2580              :                                   fold_convert (ctype, step_expr));
    2581        53220 :           ni = fold_convert (type,
    2582              :                              fold_build2 (PLUS_EXPR, ctype,
    2583              :                                           fold_convert (ctype, init_expr),
    2584              :                                           off));
    2585              :         }
    2586              :       /* Don't bother call vect_peel_nonlinear_iv_init.  */
    2587          133 :       else if (induction_type == vect_step_op_neg)
    2588              :         ni = init_expr;
    2589              :       else
    2590           83 :         ni = vect_peel_nonlinear_iv_init (&stmts, init_expr,
    2591              :                                           niters, step_expr,
    2592              :                                           induction_type, early_exit_p);
    2593              : 
    2594        53353 :       var = create_tmp_var (type, "tmp");
    2595              : 
    2596        53353 :       gimple_seq new_stmts = NULL;
    2597        53353 :       ni_name = force_gimple_operand (ni, &new_stmts, false, var);
    2598              : 
    2599              :       /* Exit_bb shouldn't be empty, but we also can't insert after a ctrl
    2600              :          statements.  */
    2601        53353 :       if (!gsi_end_p (last_gsi) && !is_ctrl_stmt (gsi_stmt (last_gsi)))
    2602              :         {
    2603          315 :           gsi_insert_seq_after (&last_gsi, stmts, GSI_SAME_STMT);
    2604          315 :           gsi_insert_seq_after (&last_gsi, new_stmts, GSI_SAME_STMT);
    2605              :         }
    2606              :       else
    2607              :         {
    2608        53038 :           gsi_insert_seq_before (&last_gsi, stmts, GSI_SAME_STMT);
    2609        53038 :           gsi_insert_seq_before (&last_gsi, new_stmts, GSI_SAME_STMT);
    2610              :         }
    2611              : 
    2612              :       /* Update the PHI argument on the requested edge.  */
    2613        53353 :       adjust_phi_and_debug_stmts (phi1, update_e, ni_name);
    2614              :     }
    2615        34860 : }
    2616              : 
    2617              : /* Return a gimple value containing the misalignment (measured in vector
    2618              :    elements) for the loop described by LOOP_VINFO, i.e. how many elements
    2619              :    it is away from a perfectly aligned address.  Add any new statements
    2620              :    to SEQ.  */
    2621              : 
    2622              : static tree
    2623          214 : get_misalign_in_elems (gimple **seq, loop_vec_info loop_vinfo)
    2624              : {
    2625          214 :   dr_vec_info *dr_info = LOOP_VINFO_UNALIGNED_DR (loop_vinfo);
    2626          214 :   stmt_vec_info stmt_info = dr_info->stmt;
    2627          214 :   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
    2628              : 
    2629          214 :   poly_uint64 target_align = DR_TARGET_ALIGNMENT (dr_info);
    2630          214 :   unsigned HOST_WIDE_INT target_align_c;
    2631          214 :   tree target_align_minus_1;
    2632              : 
    2633          214 :   bool negative = tree_int_cst_compare (DR_STEP (dr_info->dr),
    2634          214 :                                         size_zero_node) < 0;
    2635          214 :   tree offset = (negative
    2636          214 :                  ? size_int ((-TYPE_VECTOR_SUBPARTS (vectype) + 1)
    2637              :                              * TREE_INT_CST_LOW
    2638              :                                  (TYPE_SIZE_UNIT (TREE_TYPE (vectype))))
    2639          211 :                  : size_zero_node);
    2640          214 :   tree start_addr = vect_create_addr_base_for_vector_ref (loop_vinfo,
    2641              :                                                           stmt_info, seq,
    2642              :                                                           offset);
    2643          214 :   tree type = unsigned_type_for (TREE_TYPE (start_addr));
    2644          214 :   if (target_align.is_constant (&target_align_c))
    2645          214 :     target_align_minus_1 = build_int_cst (type, target_align_c - 1);
    2646              :   else
    2647              :     {
    2648              :       tree vla = build_int_cst (type, target_align);
    2649              :       target_align_minus_1 = fold_build2 (MINUS_EXPR, type, vla,
    2650              :                                           build_int_cst (type, 1));
    2651              :     }
    2652              : 
    2653          214 :   HOST_WIDE_INT elem_size
    2654          214 :     = int_cst_value (TYPE_SIZE_UNIT (TREE_TYPE (vectype)));
    2655          428 :   tree elem_size_log = build_int_cst (type, exact_log2 (elem_size));
    2656              : 
    2657              :   /* Create:  misalign_in_bytes = addr & (target_align - 1).  */
    2658          214 :   tree int_start_addr = fold_convert (type, start_addr);
    2659          214 :   tree misalign_in_bytes = fold_build2 (BIT_AND_EXPR, type, int_start_addr,
    2660              :                                         target_align_minus_1);
    2661              : 
    2662              :   /* Create:  misalign_in_elems = misalign_in_bytes / element_size.  */
    2663          214 :   tree misalign_in_elems = fold_build2 (RSHIFT_EXPR, type, misalign_in_bytes,
    2664              :                                         elem_size_log);
    2665              : 
    2666          214 :   return misalign_in_elems;
    2667              : }
    2668              : 
    2669              : /* Function vect_gen_prolog_loop_niters
    2670              : 
    2671              :    Generate the number of iterations which should be peeled as prolog for the
    2672              :    loop represented by LOOP_VINFO.  It is calculated as the misalignment of
    2673              :    DR - the data reference recorded in LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO).
    2674              :    As a result, after the execution of this loop, the data reference DR will
    2675              :    refer to an aligned location.  The following computation is generated:
    2676              : 
    2677              :    If the misalignment of DR is known at compile time:
    2678              :      addr_mis = int mis = DR_MISALIGNMENT (dr);
    2679              :    Else, compute address misalignment in bytes:
    2680              :      addr_mis = addr & (target_align - 1)
    2681              : 
    2682              :    prolog_niters = ((VF - addr_mis/elem_size)&(VF-1))/step
    2683              : 
    2684              :    (elem_size = element type size; an element is the scalar element whose type
    2685              :    is the inner type of the vectype)
    2686              : 
    2687              :    The computations will be emitted at the end of BB.  We also compute and
    2688              :    store upper bound (included) of the result in BOUND.
    2689              : 
    2690              :    When the step of the data-ref in the loop is not 1 (as in interleaved data
    2691              :    and SLP), the number of iterations of the prolog must be divided by the step
    2692              :    (which is equal to the size of interleaved group).
    2693              : 
    2694              :    The above formulas assume that VF == number of elements in the vector. This
    2695              :    may not hold when there are multiple-types in the loop.
    2696              :    In this case, for some data-references in the loop the VF does not represent
    2697              :    the number of elements that fit in the vector.  Therefore, instead of VF we
    2698              :    use TYPE_VECTOR_SUBPARTS.  */
    2699              : 
    2700              : static tree
    2701          442 : vect_gen_prolog_loop_niters (loop_vec_info loop_vinfo,
    2702              :                              basic_block bb, poly_int64 *bound)
    2703              : {
    2704          442 :   dr_vec_info *dr_info = LOOP_VINFO_UNALIGNED_DR (loop_vinfo);
    2705          442 :   tree var;
    2706          442 :   tree niters_type
    2707          442 :     = LOOP_VINFO_NITERS_UNCOUNTED_P (loop_vinfo) ? sizetype
    2708          442 :                                                  : TREE_TYPE (LOOP_VINFO_NITERS
    2709              :                                                               (loop_vinfo));
    2710          442 :   gimple_seq stmts = NULL, new_stmts = NULL;
    2711          442 :   tree iters, iters_name;
    2712          442 :   stmt_vec_info stmt_info = dr_info->stmt;
    2713          442 :   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
    2714          442 :   poly_uint64 target_align = DR_TARGET_ALIGNMENT (dr_info);
    2715              : 
    2716          442 :   if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) > 0)
    2717              :     {
    2718          228 :       int npeel = LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo);
    2719              : 
    2720          228 :       if (dump_enabled_p ())
    2721          217 :         dump_printf_loc (MSG_NOTE, vect_location,
    2722              :                          "known peeling = %d.\n", npeel);
    2723              : 
    2724          228 :       iters = build_int_cst (niters_type, npeel);
    2725          228 :       *bound = LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo);
    2726              :     }
    2727              :   else
    2728              :     {
    2729          214 :       tree misalign_in_elems = get_misalign_in_elems (&stmts, loop_vinfo);
    2730          214 :       tree type = TREE_TYPE (misalign_in_elems);
    2731          214 :       HOST_WIDE_INT elem_size
    2732          214 :         = int_cst_value (TYPE_SIZE_UNIT (TREE_TYPE (vectype)));
    2733              :       /* We only do prolog peeling if the target alignment is known at compile
    2734              :          time.  */
    2735          214 :       poly_uint64 align_in_elems =
    2736          214 :         exact_div (target_align, elem_size);
    2737          214 :       tree align_in_elems_minus_1 =
    2738          214 :         build_int_cst (type, align_in_elems - 1);
    2739          214 :       tree align_in_elems_tree = build_int_cst (type, align_in_elems);
    2740              : 
    2741              :       /* Create:  (niters_type) ((align_in_elems - misalign_in_elems)
    2742              :                                  & (align_in_elems - 1)).  */
    2743          214 :       bool negative = tree_int_cst_compare (DR_STEP (dr_info->dr),
    2744          214 :                                             size_zero_node) < 0;
    2745          214 :       if (negative)
    2746            3 :         iters = fold_build2 (MINUS_EXPR, type, misalign_in_elems,
    2747              :                              align_in_elems_tree);
    2748              :       else
    2749          211 :         iters = fold_build2 (MINUS_EXPR, type, align_in_elems_tree,
    2750              :                              misalign_in_elems);
    2751          214 :       iters = fold_build2 (BIT_AND_EXPR, type, iters, align_in_elems_minus_1);
    2752          214 :       iters = fold_convert (niters_type, iters);
    2753          214 :       *bound = align_in_elems;
    2754              :     }
    2755              : 
    2756              :   /* Alignment peeling cannot consume more scalar iterations than the loop
    2757              :      actually has.  If the requested peel count is larger than the scalar
    2758              :      iteration count, limit the peeled iterations to niters.  Otherwise we would
    2759              :      model the prologue as executing iterations that the original loop would
    2760              :      never execute.  */
    2761          442 :   if (LOOP_VINFO_USING_PARTIAL_VECTORS_P (loop_vinfo)
    2762            0 :       && !LOOP_VINFO_NITERS_UNCOUNTED_P (loop_vinfo))
    2763              :     {
    2764            0 :       tree niters = LOOP_VINFO_NITERS (loop_vinfo);
    2765            0 :       if (!types_compatible_p (niters_type, TREE_TYPE (niters)))
    2766            0 :        niters = fold_convert (niters_type, niters);
    2767            0 :       iters = fold_build2 (MIN_EXPR, niters_type, iters, niters);
    2768              :     }
    2769              : 
    2770          442 :   if (dump_enabled_p ())
    2771          288 :     dump_printf_loc (MSG_NOTE, vect_location,
    2772              :                      "niters for prolog loop: %T\n", iters);
    2773              : 
    2774          442 :   var = create_tmp_var (niters_type, "prolog_loop_niters");
    2775          442 :   iters_name = force_gimple_operand (iters, &new_stmts, false, var);
    2776              : 
    2777          442 :   if (new_stmts)
    2778          214 :     gimple_seq_add_seq (&stmts, new_stmts);
    2779          442 :   if (stmts)
    2780              :     {
    2781          214 :       gcc_assert (single_succ_p (bb));
    2782          214 :       gimple_stmt_iterator gsi = gsi_last_bb (bb);
    2783          214 :       if (gsi_end_p (gsi))
    2784           54 :         gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
    2785              :       else
    2786          160 :         gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
    2787              :     }
    2788          442 :   return iters_name;
    2789              : }
    2790              : 
    2791              : 
    2792              : /* Function vect_update_init_of_dr
    2793              : 
    2794              :    If CODE is PLUS, the vector loop starts NITERS iterations after the
    2795              :    scalar one, otherwise CODE is MINUS and the vector loop starts NITERS
    2796              :    iterations before the scalar one (using masking to skip inactive
    2797              :    elements).  This function updates the information recorded in DR to
    2798              :    account for the difference.  Specifically, it updates the OFFSET
    2799              :    field of DR_INFO.  */
    2800              : 
    2801              : static void
    2802        24737 : vect_update_init_of_dr (dr_vec_info *dr_info, tree niters, tree_code code)
    2803              : {
    2804        24737 :   struct data_reference *dr = dr_info->dr;
    2805        24737 :   tree offset = dr_info->offset;
    2806        24737 :   if (!offset)
    2807        24737 :     offset = build_zero_cst (sizetype);
    2808              : 
    2809        24737 :   niters = fold_build2 (MULT_EXPR, sizetype,
    2810              :                         fold_convert (sizetype, niters),
    2811              :                         fold_convert (sizetype, DR_STEP (dr)));
    2812        24737 :   offset = fold_build2 (code, sizetype,
    2813              :                         fold_convert (sizetype, offset), niters);
    2814        24737 :   dr_info->offset = offset;
    2815        24737 : }
    2816              : 
    2817              : 
    2818              : /* Function vect_update_inits_of_drs
    2819              : 
    2820              :    Apply vect_update_inits_of_dr to all accesses in LOOP_VINFO.
    2821              :    CODE and NITERS are as for vect_update_inits_of_dr.  */
    2822              : 
    2823              : void
    2824         7390 : vect_update_inits_of_drs (loop_vec_info loop_vinfo, tree niters,
    2825              :                           tree_code code)
    2826              : {
    2827         7390 :   unsigned int i;
    2828         7390 :   vec<data_reference_p> datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
    2829         7390 :   struct data_reference *dr;
    2830              : 
    2831         7390 :   DUMP_VECT_SCOPE ("vect_update_inits_of_dr");
    2832              : 
    2833              :   /* Adjust niters to sizetype.  We used to insert the stmts on loop preheader
    2834              :      here, but since we might use these niters to update the epilogues niters
    2835              :      and data references we can't insert them here as this definition might not
    2836              :      always dominate its uses.  */
    2837         7390 :   if (!types_compatible_p (sizetype, TREE_TYPE (niters)))
    2838         4713 :     niters = fold_convert (sizetype, niters);
    2839              : 
    2840        39823 :   FOR_EACH_VEC_ELT (datarefs, i, dr)
    2841              :     {
    2842        25158 :       dr_vec_info *dr_info = loop_vinfo->lookup_dr (dr);
    2843        25158 :       if (!STMT_VINFO_GATHER_SCATTER_P (dr_info->stmt)
    2844        24737 :           && !STMT_VINFO_SIMD_LANE_ACCESS_P (dr_info->stmt))
    2845        24737 :         vect_update_init_of_dr (dr_info, niters, code);
    2846              :     }
    2847         7390 : }
    2848              : 
    2849              : /* For the information recorded in LOOP_VINFO prepare the loop for peeling
    2850              :    by masking.  This involves calculating the number of iterations to
    2851              :    be peeled and then aligning all memory references appropriately.  */
    2852              : 
    2853              : void
    2854            2 : vect_prepare_for_masked_peels (loop_vec_info loop_vinfo)
    2855              : {
    2856            2 :   tree misalign_in_elems;
    2857            2 :   tree type = TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo));
    2858              : 
    2859            2 :   gcc_assert (vect_use_loop_mask_for_alignment_p (loop_vinfo));
    2860              : 
    2861              :   /* From the information recorded in LOOP_VINFO get the number of iterations
    2862              :      that need to be skipped via masking.  */
    2863            2 :   if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) > 0)
    2864              :     {
    2865            2 :       poly_int64 misalign = (LOOP_VINFO_VECT_FACTOR (loop_vinfo)
    2866            2 :                              - LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo));
    2867            2 :       misalign_in_elems = build_int_cst (type, misalign);
    2868              :     }
    2869              :   else
    2870              :     {
    2871            0 :       gimple_seq seq1 = NULL, seq2 = NULL;
    2872            0 :       misalign_in_elems = get_misalign_in_elems (&seq1, loop_vinfo);
    2873            0 :       misalign_in_elems = fold_convert (type, misalign_in_elems);
    2874            0 :       misalign_in_elems = force_gimple_operand (misalign_in_elems,
    2875              :                                                 &seq2, true, NULL_TREE);
    2876            0 :       gimple_seq_add_seq (&seq1, seq2);
    2877            0 :       if (seq1)
    2878              :         {
    2879            0 :           edge pe = loop_preheader_edge (LOOP_VINFO_LOOP (loop_vinfo));
    2880            0 :           basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, seq1);
    2881            0 :           gcc_assert (!new_bb);
    2882              :         }
    2883              :     }
    2884              : 
    2885            2 :   if (dump_enabled_p ())
    2886            1 :     dump_printf_loc (MSG_NOTE, vect_location,
    2887              :                      "misalignment for fully-masked loop: %T\n",
    2888              :                      misalign_in_elems);
    2889              : 
    2890            2 :   LOOP_VINFO_MASK_SKIP_NITERS (loop_vinfo) = misalign_in_elems;
    2891              : 
    2892            2 :   vect_update_inits_of_drs (loop_vinfo, misalign_in_elems, MINUS_EXPR);
    2893            2 : }
    2894              : 
    2895              : /* This function builds ni_name = number of iterations.  Statements
    2896              :    are emitted on the loop preheader edge.  If NEW_VAR_P is not NULL, set
    2897              :    it to TRUE if new ssa_var is generated.  */
    2898              : 
    2899              : tree
    2900        64834 : vect_build_loop_niters (loop_vec_info loop_vinfo, bool *new_var_p)
    2901              : {
    2902        64834 :   if (LOOP_VINFO_NITERS_UNCOUNTED_P (loop_vinfo))
    2903              :     return NULL_TREE;
    2904        64758 :   tree ni = unshare_expr (LOOP_VINFO_NITERS (loop_vinfo));
    2905        64758 :   if (TREE_CODE (ni) == INTEGER_CST)
    2906              :     return ni;
    2907              :   else
    2908              :     {
    2909        26602 :       tree ni_name, var;
    2910        26602 :       gimple_seq stmts = NULL;
    2911        26602 :       edge pe = loop_preheader_edge (LOOP_VINFO_LOOP (loop_vinfo));
    2912              : 
    2913        26602 :       var = create_tmp_var (TREE_TYPE (ni), "niters");
    2914        26602 :       ni_name = force_gimple_operand (ni, &stmts, false, var);
    2915        26602 :       if (stmts)
    2916              :         {
    2917        25510 :           gsi_insert_seq_on_edge_immediate (pe, stmts);
    2918        25510 :           if (new_var_p != NULL)
    2919          224 :             *new_var_p = true;
    2920              :         }
    2921              : 
    2922        26602 :       return ni_name;
    2923              :     }
    2924              : }
    2925              : 
    2926              : /* Calculate the number of iterations above which vectorized loop will be
    2927              :    preferred than scalar loop.  NITERS_PROLOG is the number of iterations
    2928              :    of prolog loop.  If it's integer const, the integer number is also passed
    2929              :    in INT_NITERS_PROLOG.  BOUND_PROLOG is the upper bound (inclusive) of the
    2930              :    number of iterations of the prolog loop.  BOUND_EPILOG is the corresponding
    2931              :    value for the epilog loop.  If CHECK_PROFITABILITY is true, TH is the
    2932              :    threshold below which the scalar (rather than vectorized) loop will be
    2933              :    executed.  This function stores the upper bound (inclusive) of the result
    2934              :    in BOUND_SCALAR.  */
    2935              : 
    2936              : static tree
    2937        25518 : vect_gen_scalar_loop_niters (tree niters_prolog, int int_niters_prolog,
    2938              :                              poly_int64 bound_prolog, poly_int64 bound_epilog,
    2939              :                              int th, poly_uint64 *bound_scalar,
    2940              :                              bool check_profitability)
    2941              : {
    2942        25518 :   tree type = TREE_TYPE (niters_prolog);
    2943        25518 :   tree niters = fold_build2 (PLUS_EXPR, type, niters_prolog,
    2944              :                              build_int_cst (type, bound_epilog));
    2945              : 
    2946        25518 :   *bound_scalar = bound_prolog + bound_epilog;
    2947        25518 :   if (check_profitability)
    2948              :     {
    2949              :       /* TH indicates the minimum niters of vectorized loop, while we
    2950              :          compute the maximum niters of scalar loop.  */
    2951        16277 :       th--;
    2952              :       /* Peeling for constant times.  */
    2953        16277 :       if (int_niters_prolog >= 0)
    2954              :         {
    2955        16238 :           *bound_scalar = upper_bound (int_niters_prolog + bound_epilog, th);
    2956        16238 :           return build_int_cst (type, *bound_scalar);
    2957              :         }
    2958              :       /* Peeling an unknown number of times.  Note that both BOUND_PROLOG
    2959              :          and BOUND_EPILOG are inclusive upper bounds.  */
    2960           39 :       if (known_ge (th, bound_prolog + bound_epilog))
    2961              :         {
    2962            0 :           *bound_scalar = th;
    2963            0 :           return build_int_cst (type, th);
    2964              :         }
    2965              :       /* Need to do runtime comparison.  */
    2966           39 :       else if (maybe_gt (th, bound_epilog))
    2967              :         {
    2968           39 :           *bound_scalar = upper_bound (*bound_scalar, th);
    2969           39 :           return fold_build2 (MAX_EXPR, type,
    2970              :                               build_int_cst (type, th), niters);
    2971              :         }
    2972              :     }
    2973              :   return niters;
    2974              : }
    2975              : 
    2976              : /* NITERS is the number of times that the original scalar loop executes
    2977              :    after peeling.  Work out the maximum number of iterations N that can
    2978              :    be handled by the vectorized form of the loop and then either:
    2979              : 
    2980              :    a) set *STEP_VECTOR_PTR to the vectorization factor and generate:
    2981              : 
    2982              :         niters_vector = N
    2983              : 
    2984              :    b) set *STEP_VECTOR_PTR to one and generate:
    2985              : 
    2986              :         niters_vector = N / vf
    2987              : 
    2988              :    In both cases, store niters_vector in *NITERS_VECTOR_PTR and add
    2989              :    any new statements on the loop preheader edge.  NITERS_NO_OVERFLOW
    2990              :    is true if NITERS doesn't overflow (i.e. if NITERS is always nonzero).
    2991              : 
    2992              :    Case (a) is used for LOOP_VINFO_USING_PARTIAL_VECTORS_P or if VF is
    2993              :    variable.  As stated above, NITERS_VECTOR then equals the number
    2994              :    of scalar iterations and vect_set_loop_condition will handle the
    2995              :    step.  As opposed to (b) we don't know anything about NITER_VECTOR's
    2996              :    range here.
    2997              : */
    2998              : 
    2999              : void
    3000        34992 : vect_gen_vector_loop_niters (loop_vec_info loop_vinfo, tree niters,
    3001              :                              tree *niters_vector_ptr, tree *step_vector_ptr,
    3002              :                              bool niters_no_overflow)
    3003              : {
    3004        34992 :   tree ni_minus_gap, var;
    3005        34992 :   tree niters_vector, step_vector;
    3006        34992 :   tree type = niters ? TREE_TYPE (niters) : sizetype;
    3007        34992 :   poly_uint64 vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
    3008        34992 :   edge pe = loop_preheader_edge (LOOP_VINFO_LOOP (loop_vinfo));
    3009              : 
    3010              :   /* With a counting exit before the loop body, the final scalar iteration
    3011              :      only tests that exit.  Exclude it from both the vector trip count and
    3012              :      the masks, since the vector loop tests its bound after executing the
    3013              :      body.  */
    3014        34992 :   if (LOOP_VINFO_EARLY_BREAKS_VECT_PEELED (loop_vinfo))
    3015           54 :     niters = fold_build2 (MINUS_EXPR, type, niters, build_one_cst (type));
    3016              : 
    3017              :   /* If epilogue loop is required because of data accesses with gaps, we
    3018              :      subtract one iteration from the total number of iterations here for
    3019              :      correct calculation of RATIO.  */
    3020        34992 :   if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo))
    3021              :     {
    3022          406 :       ni_minus_gap = fold_build2 (MINUS_EXPR, type, niters,
    3023              :                                   build_one_cst (type));
    3024          406 :       if (!is_gimple_val (ni_minus_gap))
    3025              :         {
    3026          190 :           var = create_tmp_var (type, "ni_gap");
    3027          190 :           gimple *stmts = NULL;
    3028          190 :           ni_minus_gap = force_gimple_operand (ni_minus_gap, &stmts,
    3029              :                                                true, var);
    3030          190 :           gsi_insert_seq_on_edge_immediate (pe, stmts);
    3031              :         }
    3032              :     }
    3033              :   else
    3034              :     ni_minus_gap = niters;
    3035              : 
    3036              :   /* To silence some unexpected warnings, simply initialize to 0. */
    3037        34992 :   unsigned HOST_WIDE_INT const_vf = 0;
    3038        34992 :   if (vf.is_constant (&const_vf)
    3039        34992 :       && !LOOP_VINFO_USING_PARTIAL_VECTORS_P (loop_vinfo)
    3040        34968 :       && LOOP_VINFO_IV_INCREMENT_INVARIANT_P (loop_vinfo))
    3041              :     {
    3042              :       /* Create: niters / vf, which is equivalent to niters >> log2(vf) when
    3043              :                  vf is a power of two, and when not we approximate using a
    3044              :                  truncating division.  */
    3045              :       /* If it's known that niters == number of latch executions + 1 doesn't
    3046              :          overflow, we can generate niters / vf; otherwise we generate
    3047              :          (niters - vf) / vf + 1 by using the fact that we know ratio
    3048              :          will be at least one.  */
    3049        34968 :       tree var_vf = build_int_cst (type, const_vf);
    3050        34968 :       if (niters_no_overflow)
    3051        34763 :         niters_vector = fold_build2 (TRUNC_DIV_EXPR, type, ni_minus_gap,
    3052              :                                      var_vf);
    3053              :       else
    3054          205 :         niters_vector
    3055          205 :           = fold_build2 (PLUS_EXPR, type,
    3056              :                          fold_build2 (TRUNC_DIV_EXPR, type,
    3057              :                                       fold_build2 (MINUS_EXPR, type,
    3058              :                                                    ni_minus_gap,
    3059              :                                                    var_vf),
    3060              :                                       var_vf),
    3061              :                          build_int_cst (type, 1));
    3062        34968 :       step_vector = build_one_cst (type);
    3063              :     }
    3064              :   else
    3065              :     {
    3066           24 :       niters_vector = ni_minus_gap;
    3067           24 :       step_vector = build_int_cst (type, vf);
    3068              :     }
    3069              : 
    3070        34992 :   if (!is_gimple_val (niters_vector))
    3071              :     {
    3072        26370 :       var = create_tmp_var (type, "bnd");
    3073        26370 :       gimple_seq stmts = NULL;
    3074        26370 :       niters_vector = force_gimple_operand (niters_vector, &stmts, true, var);
    3075        26370 :       gsi_insert_seq_on_edge_immediate (pe, stmts);
    3076              :       /* Peeling algorithm guarantees that vector loop bound is at least ONE,
    3077              :          we set range information to make niters analyzer's life easier.
    3078              :          Note the number of latch iteration value can be TYPE_MAX_VALUE so
    3079              :          we have to represent the vector niter TYPE_MAX_VALUE + 1 / vf.  */
    3080        26370 :       if (stmts != NULL
    3081        26370 :           && integer_onep (step_vector))
    3082              :         {
    3083        26351 :           if (niters_no_overflow)
    3084              :             {
    3085        26164 :               int_range<1> vr (type,
    3086        52328 :                                wi::one (TYPE_PRECISION (type)),
    3087        52328 :                                wi::div_trunc (wi::max_value
    3088        26164 :                                               (TYPE_PRECISION (type),
    3089        26164 :                                                TYPE_SIGN (type)),
    3090              :                                               const_vf,
    3091        52328 :                                               TYPE_SIGN (type)));
    3092        26164 :               set_range_info (niters_vector, vr);
    3093        26164 :             }
    3094              :           /* For VF == 1 the vector IV might also overflow so we cannot
    3095              :              assert a minimum value of 1.  */
    3096          187 :           else if (const_vf > 1)
    3097              :             {
    3098          151 :               int_range<1> vr (type,
    3099          302 :                                wi::one (TYPE_PRECISION (type)),
    3100          453 :                                wi::rshift (wi::max_value (TYPE_PRECISION (type),
    3101          151 :                                                           TYPE_SIGN (type))
    3102          302 :                                            - (const_vf - 1),
    3103          302 :                                            exact_log2 (const_vf), TYPE_SIGN (type))
    3104          604 :                                + 1);
    3105          151 :               set_range_info (niters_vector, vr);
    3106          151 :             }
    3107              :         }
    3108              :     }
    3109        34992 :   *niters_vector_ptr = niters_vector;
    3110        34992 :   *step_vector_ptr = step_vector;
    3111              : 
    3112        34992 :   return;
    3113              : }
    3114              : 
    3115              : /* Finds the amount IV's should be incremented by each iteration.
    3116              :    Stored in LOOP_VINFO_IV_INCREMENT.  */
    3117              : 
    3118              : tree
    3119        64392 : vect_get_loop_iv_increment (loop_vec_info loop_vinfo)
    3120              : {
    3121        64392 :   if (LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo))
    3122              :     {
    3123              :       /* For now, set this as varying.
    3124              :          Fill this in later when building the loop controls.  */
    3125            0 :       tree iv_increment = make_temp_ssa_name (sizetype, NULL, "iv_increment");
    3126              : 
    3127            0 :       gcall *varying_call = gimple_build_call_internal (IFN_VARYING, 0);
    3128            0 :       gimple_call_set_lhs (varying_call, iv_increment);
    3129              : 
    3130            0 :       gimple_stmt_iterator gsi = gsi_after_labels (loop_vinfo->loop->header);
    3131            0 :       gsi_insert_before (&gsi, varying_call, GSI_NEW_STMT);
    3132              : 
    3133            0 :       return iv_increment;
    3134              :     }
    3135              :   else
    3136        64392 :     return build_int_cst (sizetype, LOOP_VINFO_VECT_FACTOR (loop_vinfo));
    3137              : }
    3138              : 
    3139              : /* Given NITERS_VECTOR which is the number of iterations for vectorized
    3140              :    loop specified by LOOP_VINFO after vectorization, compute the number
    3141              :    of iterations before vectorization (niters_vector * vf) and store it
    3142              :    to NITERS_VECTOR_MULT_VF_PTR.  */
    3143              : 
    3144              : static void
    3145        34170 : vect_gen_vector_loop_niters_mult_vf (loop_vec_info loop_vinfo,
    3146              :                                      tree niters_vector,
    3147              :                                      tree *niters_vector_mult_vf_ptr)
    3148              : {
    3149              :   /* We should be using a step_vector of VF if VF is variable.  */
    3150        34170 :   int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo).to_constant ();
    3151        34170 :   tree type = TREE_TYPE (niters_vector);
    3152        34170 :   tree tree_vf = build_int_cst (type, vf);
    3153        34170 :   basic_block exit_bb = LOOP_VINFO_MAIN_EXIT (loop_vinfo)->dest;
    3154              : 
    3155        34170 :   gcc_assert (niters_vector_mult_vf_ptr != NULL);
    3156        34170 :   tree niters_vector_mult_vf = fold_build2 (MULT_EXPR, type,
    3157              :                                             niters_vector, tree_vf);
    3158              : 
    3159        34170 :   if (!is_gimple_val (niters_vector_mult_vf))
    3160              :     {
    3161        25573 :       tree var = create_tmp_var (type, "niters_vector_mult_vf");
    3162        25573 :       gimple_seq stmts = NULL;
    3163        25573 :       niters_vector_mult_vf = force_gimple_operand (niters_vector_mult_vf,
    3164              :                                                     &stmts, true, var);
    3165        25573 :       gimple_stmt_iterator gsi = gsi_start_bb (exit_bb);
    3166        25573 :       gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
    3167              :     }
    3168        34170 :   *niters_vector_mult_vf_ptr = niters_vector_mult_vf;
    3169        34170 : }
    3170              : 
    3171              : /* Function slpeel_add_loop_guard adds guard skipping from the beginning
    3172              :    of SKIP_LOOP to the beginning of UPDATE_LOOP.  GUARD_EDGE and MERGE_EDGE
    3173              :    are two pred edges of the merge point before UPDATE_LOOP.  The two loops
    3174              :    appear like below:
    3175              : 
    3176              :        guard_bb:
    3177              :          if (cond)
    3178              :            goto merge_bb;
    3179              :          else
    3180              :            goto skip_loop;
    3181              : 
    3182              :      skip_loop:
    3183              :        header_a:
    3184              :          i_1 = PHI<i_0, i_2>;
    3185              :          ...
    3186              :          i_2 = i_1 + 1;
    3187              :          if (cond_a)
    3188              :            goto latch_a;
    3189              :          else
    3190              :            goto exit_a;
    3191              :        latch_a:
    3192              :          goto header_a;
    3193              : 
    3194              :        exit_a:
    3195              :          i_5 = PHI<i_2>;
    3196              : 
    3197              :        merge_bb:
    3198              :          ;; PHI (i_x = PHI<i_0, i_5>) to be created at merge point.
    3199              : 
    3200              :      update_loop:
    3201              :        header_b:
    3202              :          i_3 = PHI<i_5, i_4>;  ;; Use of i_5 to be replaced with i_x.
    3203              :          ...
    3204              :          i_4 = i_3 + 1;
    3205              :          if (cond_b)
    3206              :            goto latch_b;
    3207              :          else
    3208              :            goto exit_bb;
    3209              :        latch_b:
    3210              :          goto header_b;
    3211              : 
    3212              :        exit_bb:
    3213              : 
    3214              :    This function creates PHI nodes at merge_bb and replaces the use of i_5
    3215              :    in the update_loop's PHI node with the result of new PHI result.  */
    3216              : 
    3217              : static void
    3218        25960 : slpeel_update_phi_nodes_for_guard1 (class loop *skip_loop,
    3219              :                                     class loop *update_loop,
    3220              :                                     edge guard_edge, edge merge_edge)
    3221              : {
    3222        25960 :   location_t merge_loc, guard_loc;
    3223        25960 :   edge orig_e = loop_preheader_edge (skip_loop);
    3224        25960 :   edge update_e = loop_preheader_edge (update_loop);
    3225        25960 :   gphi_iterator gsi_orig, gsi_update;
    3226              : 
    3227        25960 :   for ((gsi_orig = gsi_start_phis (skip_loop->header),
    3228        25960 :         gsi_update = gsi_start_phis (update_loop->header));
    3229        94648 :        !gsi_end_p (gsi_orig) && !gsi_end_p (gsi_update);
    3230        68688 :        gsi_next (&gsi_orig), gsi_next (&gsi_update))
    3231              :     {
    3232        68688 :       gphi *orig_phi = gsi_orig.phi ();
    3233        68688 :       gphi *update_phi = gsi_update.phi ();
    3234              : 
    3235              :       /* Generate new phi node at merge bb of the guard.  */
    3236        68688 :       tree new_res = copy_ssa_name (PHI_RESULT (orig_phi));
    3237        68688 :       gphi *new_phi = create_phi_node (new_res, guard_edge->dest);
    3238              : 
    3239              :       /* Merge bb has two incoming edges: GUARD_EDGE and MERGE_EDGE.  Set the
    3240              :          args in NEW_PHI for these edges.  */
    3241        68688 :       tree merge_arg = PHI_ARG_DEF_FROM_EDGE (update_phi, update_e);
    3242        68688 :       tree guard_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, orig_e);
    3243        68688 :       merge_loc = gimple_phi_arg_location_from_edge (update_phi, update_e);
    3244        68688 :       guard_loc = gimple_phi_arg_location_from_edge (orig_phi, orig_e);
    3245        68688 :       add_phi_arg (new_phi, merge_arg, merge_edge, merge_loc);
    3246        68688 :       add_phi_arg (new_phi, guard_arg, guard_edge, guard_loc);
    3247              : 
    3248              :       /* Update phi in UPDATE_PHI.  */
    3249        68688 :       adjust_phi_and_debug_stmts (update_phi, update_e, new_res);
    3250              :     }
    3251        25960 : }
    3252              : 
    3253              : /* LOOP_VINFO is an epilogue loop whose corresponding main loop can be skipped.
    3254              :    Return a value that equals:
    3255              : 
    3256              :    - MAIN_LOOP_VALUE when LOOP_VINFO is entered from the main loop and
    3257              :    - SKIP_VALUE when the main loop is skipped.  */
    3258              : 
    3259              : tree
    3260         3788 : vect_get_main_loop_result (loop_vec_info loop_vinfo, tree main_loop_value,
    3261              :                            tree skip_value)
    3262              : {
    3263         3788 :   gcc_assert (loop_vinfo->main_loop_edge);
    3264              : 
    3265         3788 :   tree phi_result = make_ssa_name (TREE_TYPE (main_loop_value));
    3266         3788 :   basic_block bb = loop_vinfo->main_loop_edge->dest;
    3267         3788 :   gphi *new_phi = create_phi_node (phi_result, bb);
    3268         3788 :   add_phi_arg (new_phi, main_loop_value, loop_vinfo->main_loop_edge,
    3269              :                UNKNOWN_LOCATION);
    3270         3788 :   add_phi_arg (new_phi, skip_value,
    3271              :                loop_vinfo->skip_main_loop_edge, UNKNOWN_LOCATION);
    3272         3788 :   return phi_result;
    3273              : }
    3274              : 
    3275              : /* Function vect_do_peeling.
    3276              : 
    3277              :    Input:
    3278              :    - LOOP_VINFO: Represent a loop to be vectorized, which looks like:
    3279              : 
    3280              :        preheader:
    3281              :      LOOP:
    3282              :        header_bb:
    3283              :          loop_body
    3284              :          if (exit_loop_cond) goto exit_bb
    3285              :          else                goto header_bb
    3286              :        exit_bb:
    3287              : 
    3288              :    - NITERS: The number of iterations of the loop.
    3289              :    - NITERSM1: The number of iterations of the loop's latch.
    3290              :    - NITERS_NO_OVERFLOW: No overflow in computing NITERS.
    3291              :    - TH, CHECK_PROFITABILITY: Threshold of niters to vectorize loop if
    3292              :                               CHECK_PROFITABILITY is true.
    3293              :    Output:
    3294              :    - *NITERS_VECTOR and *STEP_VECTOR describe how the main loop should
    3295              :      iterate after vectorization; see vect_set_loop_condition for details.
    3296              :    - *NITERS_VECTOR_MULT_VF_VAR is either null or an SSA name that
    3297              :      should be set to the number of scalar iterations handled by the
    3298              :      vector loop.  The SSA name is only used on exit from the loop.
    3299              : 
    3300              :    This function peels prolog and epilog from the loop, adds guards skipping
    3301              :    PROLOG and EPILOG for various conditions.  As a result, the changed CFG
    3302              :    would look like:
    3303              : 
    3304              :        guard_bb_1:
    3305              :          if (prefer_scalar_loop) goto merge_bb_1
    3306              :          else                    goto guard_bb_2
    3307              : 
    3308              :        guard_bb_2:
    3309              :          if (skip_prolog) goto merge_bb_2
    3310              :          else             goto prolog_preheader
    3311              : 
    3312              :        prolog_preheader:
    3313              :      PROLOG:
    3314              :        prolog_header_bb:
    3315              :          prolog_body
    3316              :          if (exit_prolog_cond) goto prolog_exit_bb
    3317              :          else                  goto prolog_header_bb
    3318              :        prolog_exit_bb:
    3319              : 
    3320              :        merge_bb_2:
    3321              : 
    3322              :        vector_preheader:
    3323              :      VECTOR LOOP:
    3324              :        vector_header_bb:
    3325              :          vector_body
    3326              :          if (exit_vector_cond) goto vector_exit_bb
    3327              :          else                  goto vector_header_bb
    3328              :        vector_exit_bb:
    3329              : 
    3330              :        guard_bb_3:
    3331              :          if (skip_epilog) goto merge_bb_3
    3332              :          else             goto epilog_preheader
    3333              : 
    3334              :        merge_bb_1:
    3335              : 
    3336              :        epilog_preheader:
    3337              :      EPILOG:
    3338              :        epilog_header_bb:
    3339              :          epilog_body
    3340              :          if (exit_epilog_cond) goto merge_bb_3
    3341              :          else                  goto epilog_header_bb
    3342              : 
    3343              :        merge_bb_3:
    3344              : 
    3345              :    Note this function peels prolog and epilog only if it's necessary,
    3346              :    as well as guards.
    3347              :    This function returns the epilogue loop if a decision was made to vectorize
    3348              :    it, otherwise NULL.
    3349              : 
    3350              :    The analysis resulting in this epilogue loop's loop_vec_info was performed
    3351              :    in the same vect_analyze_loop call as the main loop's.  At that time
    3352              :    vect_analyze_loop constructs a list of accepted loop_vec_info's for lower
    3353              :    vectorization factors than the main loop.  This list is chained in the
    3354              :    loop's loop_vec_info in the 'epilogue_vinfo' member.  When we decide to
    3355              :    vectorize the epilogue loop for a lower vectorization factor, the
    3356              :    loop_vec_info in epilogue_vinfo is updated and linked to the epilogue loop.
    3357              :    This is later used to vectorize the epilogue.
    3358              :    The reason the loop_vec_info needs updating is that it was
    3359              :    constructed based on the original main loop, and the epilogue loop is a
    3360              :    copy of this loop, so all links pointing to statements in the original loop
    3361              :    need updating.  Furthermore, these loop_vec_infos share the
    3362              :    data_reference's records, which will also need to be updated.
    3363              : 
    3364              :    TODO: Guard for prefer_scalar_loop should be emitted along with
    3365              :    versioning conditions if loop versioning is needed.  */
    3366              : 
    3367              : 
    3368              : class loop *
    3369        64392 : vect_do_peeling (loop_vec_info loop_vinfo, tree niters, tree nitersm1,
    3370              :                  tree *niters_vector, tree *step_vector,
    3371              :                  tree *niters_vector_mult_vf_var, int th,
    3372              :                  bool check_profitability, bool niters_no_overflow,
    3373              :                  tree *advance)
    3374              : {
    3375        64392 :   edge e, guard_e;
    3376        64392 :   tree type = niters ? TREE_TYPE (niters) : sizetype;
    3377        64392 :   tree guard_cond;
    3378        64392 :   basic_block guard_bb, guard_to;
    3379        64392 :   profile_probability prob_prolog, prob_vector, prob_epilog;
    3380        64392 :   int estimated_vf;
    3381        64392 :   int prolog_peeling = 0;
    3382        64392 :   bool vect_epilogues = loop_vinfo->epilogue_vinfo != NULL;
    3383        64392 :   bool uncounted_p = LOOP_VINFO_NITERS_UNCOUNTED_P (loop_vinfo);
    3384              : 
    3385        64392 :   if (!vect_use_loop_mask_for_alignment_p (loop_vinfo))
    3386        64390 :     prolog_peeling = LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo);
    3387              : 
    3388        64392 :   poly_uint64 vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
    3389        64392 :   poly_uint64 bound_epilog = 0;
    3390        64392 :   if (!LOOP_VINFO_USING_PARTIAL_VECTORS_P (loop_vinfo)
    3391        64368 :       && LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo))
    3392        33848 :     bound_epilog += vf - 1;
    3393        64392 :   if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo))
    3394          406 :     bound_epilog += 1;
    3395              : 
    3396              :   /* For early breaks the scalar loop needs to execute at most VF times
    3397              :      to find the element that caused the break.  */
    3398        64392 :   if (LOOP_VINFO_EARLY_BREAKS (loop_vinfo)
    3399        64392 :       && (LOOP_VINFO_EARLY_BRK_NEEDS_EPILOG (loop_vinfo)
    3400          816 :           || LOOP_VINFO_EARLY_BREAKS_VECT_PEELED (loop_vinfo)))
    3401              :     bound_epilog = vf;
    3402              : 
    3403        64392 :   bool epilog_peeling = maybe_ne (bound_epilog, 0U);
    3404        64392 :   poly_uint64 bound_scalar = bound_epilog;
    3405              : 
    3406        64392 :   if (!LOOP_VINFO_EARLY_BRK_NEEDS_EPILOG (loop_vinfo) && dump_enabled_p ())
    3407         8549 :     dump_printf_loc (MSG_NOTE, vect_location,
    3408              :                      "early break does not require epilog.\n");
    3409              : 
    3410        64392 :   if (!prolog_peeling && !epilog_peeling)
    3411              :     return NULL;
    3412              : 
    3413              :   /* Before doing any peeling make sure to reset debug binds outside of
    3414              :      the loop referring to defs not in LC SSA.  */
    3415        34254 :   class loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    3416        34254 :   reset_debug_uses_outside_loop (loop, LOOP_VINFO_BBS (loop_vinfo),
    3417              :                                  loop->num_nodes);
    3418              : 
    3419        34254 :   prob_vector = profile_probability::guessed_always ().apply_scale (9, 10);
    3420        34254 :   estimated_vf = vect_vf_for_cost (loop_vinfo);
    3421        34254 :   if (estimated_vf == 2)
    3422         7427 :     estimated_vf = 3;
    3423        34254 :   prob_prolog = prob_epilog = profile_probability::guessed_always ()
    3424        34254 :                         .apply_scale (estimated_vf - 1, estimated_vf);
    3425              : 
    3426        34254 :   class loop *prolog = NULL, *epilog = NULL;
    3427        34254 :   class loop *first_loop = loop;
    3428        34254 :   bool irred_flag = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
    3429              : 
    3430              :   /* SSA form needs to be up-to-date since we are going to manually
    3431              :      update SSA form in slpeel_tree_duplicate_loop_to_edge_cfg and delete all
    3432              :      update SSA state after that, so we have to make sure to not lose any
    3433              :      pending update needs.  */
    3434        34254 :   gcc_assert (!need_ssa_update_p (cfun));
    3435              : 
    3436              :   /* If we're vectorizing an epilogue loop, we have ensured that the
    3437              :      virtual operand is in SSA form throughout the vectorized main loop.
    3438              :      Normally it is possible to trace the updated
    3439              :      vector-stmt vdefs back to scalar-stmt vdefs and vector-stmt vuses
    3440              :      back to scalar-stmt vuses, meaning that the effect of the SSA update
    3441              :      remains local to the main loop.  However, there are rare cases in
    3442              :      which the vectorized loop should have vdefs even when the original scalar
    3443              :      loop didn't.  For example, vectorizing a load with IFN_LOAD_LANES
    3444              :      introduces clobbers of the temporary vector array, which in turn
    3445              :      needs new vdefs.  If the scalar loop doesn't write to memory, these
    3446              :      new vdefs will be the only ones in the vector loop.
    3447              :      We are currently deferring updating virtual SSA form and creating
    3448              :      of a virtual PHI for this case so we do not have to make sure the
    3449              :      newly introduced virtual def is in LCSSA form.  */
    3450              : 
    3451        34254 :   if (MAY_HAVE_DEBUG_BIND_STMTS)
    3452              :     {
    3453        12754 :       gcc_assert (!adjust_vec.exists ());
    3454        12754 :       adjust_vec.create (32);
    3455              :     }
    3456        34254 :   initialize_original_copy_tables ();
    3457              : 
    3458              :   /* Record the anchor bb at which the guard should be placed if the scalar
    3459              :      loop might be preferred.  */
    3460        34254 :   basic_block anchor = loop_preheader_edge (loop)->src;
    3461              : 
    3462              :   /* Generate the number of iterations for the prolog loop.  We do this here
    3463              :      so that we can also get the upper bound on the number of iterations.  */
    3464        34254 :   tree niters_prolog;
    3465        34254 :   poly_int64 bound_prolog = 0;
    3466        34254 :   if (prolog_peeling)
    3467              :     {
    3468          442 :       niters_prolog = vect_gen_prolog_loop_niters (loop_vinfo, anchor,
    3469              :                                                    &bound_prolog);
    3470              :       /* If algonment peeling is known, we will always execute prolog.  */
    3471          442 :       if (TREE_CODE (niters_prolog) == INTEGER_CST)
    3472          228 :         prob_prolog = profile_probability::always ();
    3473              :     }
    3474              :   else
    3475        33812 :     niters_prolog = build_int_cst (type, 0);
    3476              : 
    3477        34254 :   loop_vec_info epilogue_vinfo = loop_vinfo->epilogue_vinfo;
    3478        34254 :   tree niters_vector_mult_vf = NULL_TREE;
    3479              :   /* Saving NITERs before the loop, as this may be changed by prologue.  */
    3480        34254 :   tree before_loop_niters = LOOP_VINFO_NITERS (loop_vinfo);
    3481        34254 :   edge update_e = NULL, skip_e = NULL;
    3482        34254 :   unsigned int lowest_vf = constant_lower_bound (vf);
    3483              :   /* Prolog loop may be skipped.  */
    3484        34254 :   bool skip_prolog = (prolog_peeling != 0);
    3485              :   /* Skip this loop to epilog when there are not enough iterations to enter this
    3486              :      vectorized loop.  If true we should perform runtime checks on the NITERS
    3487              :      to check whether we should skip the current vectorized loop.  If we know
    3488              :      the number of scalar iterations we may choose to add a runtime check if
    3489              :      this number "maybe" smaller than the number of iterations required
    3490              :      when we know the number of scalar iterations may potentially
    3491              :      be smaller than the number of iterations required to enter this loop, for
    3492              :      this we use the upper bounds on the prolog and epilog peeling.  When we
    3493              :      don't know the number of iterations and don't require versioning it is
    3494              :      because we have asserted that there are enough scalar iterations to enter
    3495              :      the main loop, so this skip is not necessary.  When we are versioning then
    3496              :      we only add such a skip if we have chosen to vectorize the epilogue.  */
    3497        34254 :   bool skip_vector = false;
    3498        34254 :   if (!uncounted_p)
    3499         8646 :     skip_vector = (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
    3500        42855 :                    ? maybe_lt (LOOP_VINFO_INT_NITERS (loop_vinfo),
    3501         8646 :                                bound_prolog + bound_epilog)
    3502        25618 :                    : (!LOOP_VINFO_USE_VERSIONING_WITHOUT_PEELING (loop_vinfo)
    3503          100 :                       || vect_epilogues));
    3504              : 
    3505              :   /* Epilog loop must be executed if the number of iterations for epilog
    3506              :      loop is known at compile time, otherwise we need to add a check at
    3507              :      the end of vector loop and skip to the end of epilog loop.  */
    3508        34254 :   bool skip_epilog = (prolog_peeling < 0
    3509        34040 :                       || !LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
    3510        34254 :                       || !vf.is_constant ());
    3511              :   /* PEELING_FOR_GAPS and peeling for early breaks are special because epilog
    3512              :      loop must be executed.  */
    3513        34254 :   if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo)
    3514        33848 :       || LOOP_VINFO_EARLY_BREAKS (loop_vinfo))
    3515         1302 :     skip_epilog = false;
    3516              : 
    3517        34254 :   class loop *scalar_loop = LOOP_VINFO_SCALAR_LOOP (loop_vinfo);
    3518        34254 :   auto_vec<profile_count> original_counts;
    3519        34254 :   basic_block *original_bbs = NULL;
    3520              : 
    3521        34254 :   if (skip_vector)
    3522              :     {
    3523        25518 :       split_edge (loop_preheader_edge (loop));
    3524              : 
    3525        25518 :       if (epilog_peeling && (vect_epilogues || scalar_loop == NULL))
    3526              :         {
    3527        24465 :           original_bbs = get_loop_body (loop);
    3528        98304 :           for (unsigned int i = 0; i < loop->num_nodes; i++)
    3529        49374 :             original_counts.safe_push(original_bbs[i]->count);
    3530              :         }
    3531              : 
    3532              :       /* Due to the order in which we peel prolog and epilog, we first
    3533              :          propagate probability to the whole loop.  The purpose is to
    3534              :          avoid adjusting probabilities of both prolog and vector loops
    3535              :          separately.  Note in this case, the probability of epilog loop
    3536              :          needs to be scaled back later.  */
    3537        25518 :       basic_block bb_before_loop = loop_preheader_edge (loop)->src;
    3538        25518 :       if (prob_vector.initialized_p ())
    3539              :         {
    3540        25518 :           scale_bbs_frequencies (&bb_before_loop, 1, prob_vector);
    3541        25518 :           scale_loop_profile (loop, prob_vector, -1);
    3542              :         }
    3543              :     }
    3544              : 
    3545        34254 :   if (vect_epilogues)
    3546              :     {
    3547              :       /* Make sure to set the epilogue's epilogue scalar loop, such that we can
    3548              :          use the original scalar loop as remaining epilogue if necessary.  */
    3549         6946 :       LOOP_VINFO_SCALAR_LOOP (epilogue_vinfo)
    3550         6946 :         = LOOP_VINFO_SCALAR_LOOP (loop_vinfo);
    3551         6946 :       LOOP_VINFO_SCALAR_MAIN_EXIT (epilogue_vinfo)
    3552         6946 :         = LOOP_VINFO_SCALAR_MAIN_EXIT (loop_vinfo);
    3553              :     }
    3554              : 
    3555        34254 :   if (prolog_peeling)
    3556              :     {
    3557          442 :       e = loop_preheader_edge (loop);
    3558          442 :       edge exit_e = LOOP_VINFO_MAIN_EXIT (loop_vinfo);
    3559          442 :       gcc_checking_assert (slpeel_can_duplicate_loop_p (loop, exit_e, e)
    3560              :                            && (!LOOP_VINFO_EARLY_BREAKS_VECT_PEELED (loop_vinfo)
    3561              :                                || uncounted_p));
    3562              : 
    3563              :       /* Peel prolog and put it on preheader edge of loop.  */
    3564          442 :       edge scalar_e = LOOP_VINFO_SCALAR_MAIN_EXIT (loop_vinfo);
    3565          442 :       edge prolog_e = NULL;
    3566          442 :       prolog = slpeel_tree_duplicate_loop_to_edge_cfg (loop, exit_e,
    3567              :                                                        scalar_loop, scalar_e,
    3568              :                                                        e, &prolog_e, true, NULL,
    3569              :                                                        uncounted_p, uncounted_p,
    3570              :                                                        false);
    3571              : 
    3572          442 :       gcc_assert (prolog);
    3573          442 :       prolog->force_vectorize = false;
    3574              :       /* Assumptions are only versioned for the main exit, others might
    3575              :          still be taken, so do not mislead later passes.  */
    3576          442 :       if (LOOP_VINFO_EARLY_BREAKS (loop_vinfo))
    3577          236 :         loop_constraint_clear (prolog, LOOP_C_FINITE);
    3578              : 
    3579          442 :       first_loop = prolog;
    3580          442 :       reset_original_copy_tables ();
    3581              : 
    3582              :       /* Update the number of iterations for prolog loop.  */
    3583          442 :       tree step_prolog = build_one_cst (TREE_TYPE (niters_prolog));
    3584          442 :       vect_set_loop_condition (prolog, prolog_e, NULL, niters_prolog,
    3585              :                                step_prolog, NULL_TREE, false);
    3586              : 
    3587              :       /* Skip the prolog loop.  */
    3588          442 :       if (skip_prolog)
    3589              :         {
    3590          442 :           guard_cond = fold_build2 (EQ_EXPR, boolean_type_node,
    3591              :                                     niters_prolog, build_int_cst (type, 0));
    3592          442 :           guard_bb = loop_preheader_edge (prolog)->src;
    3593          442 :           basic_block bb_after_prolog = loop_preheader_edge (loop)->src;
    3594          442 :           guard_to = split_edge (loop_preheader_edge (loop));
    3595          442 :           guard_e = slpeel_add_loop_guard (guard_bb, guard_cond,
    3596              :                                            guard_to, guard_bb,
    3597              :                                            prob_prolog.invert (),
    3598              :                                            irred_flag);
    3599         2028 :           for (edge alt_e : get_loop_exit_edges (prolog))
    3600              :             {
    3601          702 :               if (alt_e == prolog_e)
    3602          442 :                 continue;
    3603          260 :               basic_block old_dom
    3604          260 :                 = get_immediate_dominator (CDI_DOMINATORS, alt_e->dest);
    3605          260 :               if (flow_bb_inside_loop_p (prolog, old_dom))
    3606              :                 {
    3607          101 :                   auto_vec<basic_block, 8> queue;
    3608          101 :                   for (auto son = first_dom_son (CDI_DOMINATORS, old_dom);
    3609          327 :                        son; son = next_dom_son (CDI_DOMINATORS, son))
    3610          226 :                     if (!flow_bb_inside_loop_p (prolog, son))
    3611          125 :                       queue.safe_push (son);
    3612          428 :                   for (auto son : queue)
    3613          125 :                     set_immediate_dominator (CDI_DOMINATORS, son, guard_bb);
    3614          101 :                 }
    3615          442 :             }
    3616              : 
    3617          442 :           e = EDGE_PRED (guard_to, 0);
    3618          442 :           e = (e != guard_e ? e : EDGE_PRED (guard_to, 1));
    3619          442 :           slpeel_update_phi_nodes_for_guard1 (prolog, loop, guard_e, e);
    3620              : 
    3621          442 :           scale_bbs_frequencies (&bb_after_prolog, 1, prob_prolog);
    3622          442 :           scale_loop_profile (prolog, prob_prolog,
    3623          442 :                               estimated_poly_value (bound_prolog) - 1);
    3624              :         }
    3625              : 
    3626              :       /* Update init address of DRs.  */
    3627          442 :       vect_update_inits_of_drs (loop_vinfo, niters_prolog, PLUS_EXPR);
    3628          442 :       if (!uncounted_p)
    3629              :         {
    3630              :           /* Update niters for vector loop.  */
    3631          411 :           LOOP_VINFO_NITERS (loop_vinfo)
    3632          411 :             = fold_build2 (MINUS_EXPR, type, niters, niters_prolog);
    3633          411 :           LOOP_VINFO_NITERSM1 (loop_vinfo)
    3634          411 :             = fold_build2 (MINUS_EXPR, type,
    3635              :                            LOOP_VINFO_NITERSM1 (loop_vinfo), niters_prolog);
    3636              :         }
    3637          442 :       bool new_var_p = false;
    3638          442 :       niters = vect_build_loop_niters (loop_vinfo, &new_var_p);
    3639              :       /* It's guaranteed that vector loop bound before vectorization is at
    3640              :          least VF, so set range information for newly generated var.  */
    3641          442 :       if (new_var_p)
    3642              :         {
    3643          224 :           int_range<1> vr (type,
    3644          448 :                            wi::to_wide (build_int_cst (type, lowest_vf)),
    3645          448 :                            wi::to_wide (TYPE_MAX_VALUE (type)));
    3646          224 :           set_range_info (niters, vr);
    3647          224 :         }
    3648              : 
    3649              :       /* Prolog iterates at most bound_prolog times, latch iterates at
    3650              :          most bound_prolog - 1 times.  */
    3651          442 :       if (bound_prolog.is_constant ())
    3652          442 :         record_niter_bound (prolog, bound_prolog.to_constant () - 1, false,
    3653              :                             true);
    3654          442 :       delete_update_ssa ();
    3655          442 :       adjust_vec_debug_stmts ();
    3656          442 :       scev_reset ();
    3657              :     }
    3658        34254 :   basic_block bb_before_epilog = NULL;
    3659              : 
    3660        34254 :   if (epilog_peeling)
    3661              :     {
    3662        34215 :       e = LOOP_VINFO_MAIN_EXIT (loop_vinfo);
    3663        34215 :       gcc_checking_assert (slpeel_can_duplicate_loop_p (loop, e, e));
    3664              : 
    3665              :       /* Peel epilog and put it on exit edge of loop.  If we are vectorizing
    3666              :          said epilog then we should use a copy of the main loop as a starting
    3667              :          point.  This loop may have already had some preliminary transformations
    3668              :          to allow for more optimal vectorization, for example if-conversion.
    3669              :          If we are not vectorizing the epilog then we should use the scalar loop
    3670              :          as the transformations mentioned above make less or no sense when not
    3671              :          vectorizing.  */
    3672        34215 :       edge scalar_e = LOOP_VINFO_SCALAR_MAIN_EXIT (loop_vinfo);
    3673        34215 :       epilog = vect_epilogues ? get_loop_copy (loop) : scalar_loop;
    3674         6946 :       edge epilog_e = vect_epilogues ? e : scalar_e;
    3675        34215 :       edge new_epilog_e = NULL;
    3676        34215 :       auto_vec<basic_block> doms;
    3677        34215 :       bool early_break_peel_p = LOOP_VINFO_EARLY_BRK_NEEDS_EPILOG (loop_vinfo);
    3678        34215 :       epilog
    3679        34215 :         = slpeel_tree_duplicate_loop_to_edge_cfg (loop, e, epilog, epilog_e, e,
    3680              :                                                   &new_epilog_e, true, &doms,
    3681              :                                                   uncounted_p, false,
    3682              :                                                   early_break_peel_p);
    3683              : 
    3684        34215 :       LOOP_VINFO_EPILOGUE_MAIN_EXIT (loop_vinfo) = new_epilog_e;
    3685        34215 :       gcc_assert (epilog);
    3686        34215 :       gcc_assert (new_epilog_e);
    3687        34215 :       epilog->force_vectorize = false;
    3688              :       /* Assumptions are only versioned for the main exit, others might
    3689              :          still be taken, so do not mislead later passes.  */
    3690        34215 :       if (!vect_epilogues && LOOP_VINFO_EARLY_BREAKS (loop_vinfo))
    3691          888 :         loop_constraint_clear (epilog, LOOP_C_FINITE);
    3692        34215 :       bb_before_epilog = loop_preheader_edge (epilog)->src;
    3693              : 
    3694              :       /* Scalar version loop may be preferred.  In this case, add guard
    3695              :          and skip to epilog.  Note this only happens when the number of
    3696              :          iterations of loop is unknown at compile time, otherwise this
    3697              :          won't be vectorized.  */
    3698        34215 :       if (skip_vector)
    3699              :         {
    3700              :           /* Additional epilogue iteration is peeled if gap exists.  */
    3701        51036 :           tree t = vect_gen_scalar_loop_niters (niters_prolog, prolog_peeling,
    3702        25518 :                                                 bound_prolog, bound_epilog,
    3703              :                                                 th, &bound_scalar,
    3704              :                                                 check_profitability);
    3705              :           /* Build guard against NITERSM1 since NITERS may overflow.  */
    3706        25518 :           guard_cond = fold_build2 (LT_EXPR, boolean_type_node, nitersm1, t);
    3707        25518 :           guard_bb = anchor;
    3708        25518 :           guard_to = split_edge (loop_preheader_edge (epilog));
    3709        25518 :           guard_e = slpeel_add_loop_guard (guard_bb, guard_cond,
    3710              :                                            guard_to, guard_bb,
    3711              :                                            prob_vector.invert (),
    3712              :                                            irred_flag);
    3713        25518 :           skip_e = guard_e;
    3714        25518 :           e = EDGE_PRED (guard_to, 0);
    3715        25518 :           e = (e != guard_e ? e : EDGE_PRED (guard_to, 1));
    3716              : 
    3717              :           /* Handle any remaining dominator updates needed after
    3718              :              inserting the loop skip edge above.  */
    3719        25518 :           if (LOOP_VINFO_EARLY_BREAKS (loop_vinfo)
    3720          292 :               && prolog_peeling)
    3721              :             {
    3722              :               /* Adding a skip edge to skip a loop with multiple exits
    3723              :                  means the dominator of the join blocks for all exits shifts
    3724              :                  from the prolog skip guard to the loop skip guard.  */
    3725          165 :               auto prolog_skip_bb
    3726          165 :                 = single_pred (loop_preheader_edge (prolog)->src);
    3727          165 :               auto needs_update
    3728          165 :                 = get_dominated_by (CDI_DOMINATORS, prolog_skip_bb);
    3729              : 
    3730              :               /* Update everything except for the immediate children of
    3731              :                  the prolog skip block (the prolog and vector preheaders).
    3732              :                  Those should remain dominated by the prolog skip block itself,
    3733              :                  since the loop guard edge goes to the epilogue.  */
    3734          882 :               for (auto bb : needs_update)
    3735          387 :                 if (bb != EDGE_SUCC (prolog_skip_bb, 0)->dest
    3736          387 :                     && bb != EDGE_SUCC (prolog_skip_bb, 1)->dest)
    3737           57 :                   set_immediate_dominator (CDI_DOMINATORS, bb, guard_bb);
    3738          165 :             }
    3739              : 
    3740        25518 :           slpeel_update_phi_nodes_for_guard1 (first_loop, epilog, guard_e, e);
    3741              : 
    3742              :           /* Simply propagate profile info from guard_bb to guard_to which is
    3743              :              a merge point of control flow.  */
    3744        25518 :           profile_count old_count = guard_to->count;
    3745        25518 :           guard_to->count = guard_bb->count;
    3746              : 
    3747              :           /* Restore the counts of the epilog loop if we didn't use the scalar loop. */
    3748        25518 :           if (vect_epilogues || scalar_loop == NULL)
    3749              :             {
    3750        24465 :               gcc_assert(epilog->num_nodes == loop->num_nodes);
    3751        24465 :               basic_block *bbs = get_loop_body (epilog);
    3752        98304 :               for (unsigned int i = 0; i < epilog->num_nodes; i++)
    3753              :                 {
    3754        49374 :                   gcc_assert(get_bb_original (bbs[i]) == original_bbs[i]);
    3755        49374 :                   bbs[i]->count = original_counts[i];
    3756              :                 }
    3757        24465 :               free (bbs);
    3758        24465 :               free (original_bbs);
    3759              :             }
    3760         1053 :           else if (old_count.nonzero_p ())
    3761         1053 :             scale_loop_profile (epilog, guard_to->count.probability_in (old_count), -1);
    3762              : 
    3763              :           /* Only need to handle basic block before epilog loop if it's not
    3764              :              the guard_bb, which is the case when skip_vector is true.  */
    3765        25518 :           if (guard_bb != bb_before_epilog && single_pred_p (bb_before_epilog))
    3766        25374 :             bb_before_epilog->count = single_pred_edge (bb_before_epilog)->count ();
    3767        25518 :           bb_before_epilog = loop_preheader_edge (epilog)->src;
    3768              :         }
    3769              : 
    3770        34215 :       if (!uncounted_p)
    3771              :         {
    3772              :           /* If loop is peeled for non-zero constant times, now niters refers to
    3773              :              orig_niters - prolog_peeling, it won't overflow even the
    3774              :              orig_niters overflows.  */
    3775        34170 :           niters_no_overflow |= (prolog_peeling > 0);
    3776        34170 :           vect_gen_vector_loop_niters (loop_vinfo, niters,
    3777              :                                        niters_vector, step_vector,
    3778              :                                        niters_no_overflow);
    3779        34170 :           if (!integer_onep (*step_vector))
    3780              :             {
    3781              :               /* On exit from the loop we will have an easy way of calculating
    3782              :                  NITERS_VECTOR / STEP * STEP.  Install a dummy definition
    3783              :                  until then.  */
    3784            0 :               niters_vector_mult_vf
    3785            0 :                 = make_ssa_name (TREE_TYPE (*niters_vector));
    3786            0 :               edge exit_e = LOOP_VINFO_MAIN_EXIT (loop_vinfo);
    3787            0 :               gimple_stmt_iterator loop_cond_gsi
    3788            0 :                 = gsi_after_labels (exit_e->dest);
    3789              : 
    3790            0 :               gcall *tmp = gimple_build_call_internal (IFN_VARYING, 0);
    3791            0 :               gimple_call_set_lhs (tmp, niters_vector_mult_vf);
    3792            0 :               gsi_insert_before (&loop_cond_gsi, tmp, GSI_SAME_STMT);
    3793            0 :               *niters_vector_mult_vf_var = niters_vector_mult_vf;
    3794              :             }
    3795              :           else
    3796        34170 :             vect_gen_vector_loop_niters_mult_vf (loop_vinfo, *niters_vector,
    3797              :                                                  &niters_vector_mult_vf);
    3798              :           /* Update IVs of original loop as if they were advanced by
    3799              :              niters_vector_mult_vf steps.  */
    3800        34170 :           gcc_checking_assert (vect_can_advance_ivs_p (loop_vinfo));
    3801        34170 :           update_e = skip_vector ? e : loop_preheader_edge (epilog);
    3802              :         }
    3803        34215 :       if (LOOP_VINFO_EARLY_BREAKS (loop_vinfo))
    3804          888 :         update_e = single_succ_edge (LOOP_VINFO_MAIN_EXIT (loop_vinfo)->dest);
    3805              : 
    3806              :       /* If we have a peeled vector iteration we will never skip the epilog loop
    3807              :          and we can simplify the cfg a lot by not doing the edge split.  */
    3808        34215 :       if (skip_epilog
    3809        34215 :           || (LOOP_VINFO_EARLY_BREAKS (loop_vinfo)
    3810          888 :               && !LOOP_VINFO_EARLY_BREAKS_VECT_PEELED (loop_vinfo)))
    3811              :         {
    3812        25828 :           guard_cond = fold_build2 (EQ_EXPR, boolean_type_node,
    3813              :                                     niters, niters_vector_mult_vf);
    3814              : 
    3815        25828 :           guard_bb = LOOP_VINFO_MAIN_EXIT (loop_vinfo)->dest;
    3816        25828 :           edge epilog_e = LOOP_VINFO_EPILOGUE_MAIN_EXIT (loop_vinfo);
    3817        25828 :           guard_to = epilog_e->dest;
    3818        26343 :           guard_e = slpeel_add_loop_guard (guard_bb, guard_cond, guard_to,
    3819              :                                            skip_vector ? anchor : guard_bb,
    3820              :                                            prob_epilog.invert (),
    3821              :                                            irred_flag);
    3822              : 
    3823        25828 :           doms.safe_push (guard_to);
    3824        25828 :           if (vect_epilogues)
    3825         5659 :             epilogue_vinfo->skip_this_loop_edge = guard_e;
    3826        25828 :           edge main_iv = LOOP_VINFO_MAIN_EXIT (loop_vinfo);
    3827        25828 :           gphi_iterator gsi2 = gsi_start_phis (main_iv->dest);
    3828        25828 :           for (gphi_iterator gsi = gsi_start_phis (guard_to);
    3829        62739 :                !gsi_end_p (gsi); gsi_next (&gsi))
    3830              :             {
    3831              :               /* We are expecting all of the PHIs we have on epilog_e
    3832              :                  to be also on the main loop exit.  But sometimes
    3833              :                  a stray virtual definition can appear at epilog_e
    3834              :                  which we can then take as the same on all exits,
    3835              :                  we've removed the LC SSA PHI on the main exit before
    3836              :                  so we wouldn't need to create a loop PHI for it.  */
    3837        36911 :               if (virtual_operand_p (gimple_phi_result (*gsi))
    3838        36911 :                   && (gsi_end_p (gsi2)
    3839        37718 :                       || !virtual_operand_p (gimple_phi_result (*gsi2))))
    3840          170 :                 add_phi_arg (*gsi,
    3841           85 :                              gimple_phi_arg_def_from_edge (*gsi, epilog_e),
    3842              :                              guard_e, UNKNOWN_LOCATION);
    3843              :               else
    3844              :                 {
    3845        36826 :                   add_phi_arg (*gsi, gimple_phi_result (*gsi2), guard_e,
    3846              :                                UNKNOWN_LOCATION);
    3847        36826 :                   gsi_next (&gsi2);
    3848              :                 }
    3849              :             }
    3850              : 
    3851              :           /* Only need to handle basic block before epilog loop if it's not
    3852              :              the guard_bb, which is the case when skip_vector is true.  */
    3853        25828 :           if (guard_bb != bb_before_epilog)
    3854              :             {
    3855        25779 :               prob_epilog = prob_vector * prob_epilog + prob_vector.invert ();
    3856              : 
    3857        25779 :               scale_bbs_frequencies (&bb_before_epilog, 1, prob_epilog);
    3858              :             }
    3859        25828 :           scale_loop_profile (epilog, prob_epilog, -1);
    3860              :         }
    3861              : 
    3862              :       /* A counted main exit follows the completed vector iteration.
    3863              :          Uncounted loops must replay the exiting iteration to find the
    3864              :          scalar exit.  */
    3865        34215 :       tree vector_iters_vf = niters_vector_mult_vf;
    3866        34215 :       if (LOOP_VINFO_EARLY_BREAKS (loop_vinfo))
    3867              :         {
    3868          888 :           tree tmp_niters_vf
    3869          888 :             = make_ssa_name (LOOP_VINFO_EARLY_BRK_IV_TYPE (loop_vinfo));
    3870          888 :           gcall *tmp_call = gimple_build_call_internal (IFN_VARYING, 0);
    3871          888 :           gimple_call_set_lhs (tmp_call, tmp_niters_vf);
    3872          888 :           auto header_gsi = gsi_after_labels (loop->header);
    3873          888 :           gsi_insert_before (&header_gsi, tmp_call, GSI_SAME_STMT);
    3874              : 
    3875           45 :           if (!(LOOP_VINFO_NITERS_UNCOUNTED_P (loop_vinfo)
    3876          978 :                 && get_loop_exit_edges (loop).length () == 1)
    3877          902 :               && LOOP_VINFO_EARLY_BRK_NEEDS_EPILOG (loop_vinfo))
    3878              :             {
    3879          645 :               basic_block exit_bb = NULL;
    3880          645 :               edge update_e = NULL;
    3881              : 
    3882              :               /* Identify the early exit merge block.  I wish we had stored
    3883              :                  this.  */
    3884         1935 :               for (auto e : get_loop_exit_edges (loop))
    3885          645 :                 if (e != LOOP_VINFO_MAIN_EXIT (loop_vinfo))
    3886              :                   {
    3887          645 :                     exit_bb = e->dest;
    3888          645 :                     update_e = single_succ_edge (exit_bb);
    3889          645 :                     break;
    3890          645 :                   }
    3891          645 :               vect_update_ivs_after_vectorizer (loop_vinfo, tmp_niters_vf,
    3892              :                                                 update_e, true);
    3893              :             }
    3894          888 :           if (uncounted_p)
    3895           45 :             vector_iters_vf = tmp_niters_vf;
    3896              : 
    3897          888 :           LOOP_VINFO_EARLY_BRK_NITERS_VAR (loop_vinfo) = tmp_niters_vf;
    3898              :         }
    3899              : 
    3900        34215 :       vect_update_ivs_after_vectorizer (loop_vinfo, vector_iters_vf,
    3901              :                                        update_e, uncounted_p);
    3902              : 
    3903              :       /* Recalculate the dominators after adding the guard edge.  */
    3904        34215 :       if (LOOP_VINFO_EARLY_BREAKS (loop_vinfo))
    3905          888 :         iterate_fix_dominators (CDI_DOMINATORS, doms, false);
    3906              : 
    3907              :       /* When we do not have a loop-around edge to the epilog we know
    3908              :          the vector loop covered at least VF scalar iterations unless
    3909              :          we have early breaks.
    3910              :          Update any known upper bound with this knowledge.  */
    3911        34215 :       if (! skip_vector
    3912         8697 :           && ! LOOP_VINFO_EARLY_BREAKS (loop_vinfo))
    3913              :         {
    3914         8101 :           if (epilog->any_upper_bound)
    3915         8101 :             epilog->nb_iterations_upper_bound -= lowest_vf;
    3916         8101 :           if (epilog->any_likely_upper_bound)
    3917         8101 :             epilog->nb_iterations_likely_upper_bound -= lowest_vf;
    3918         8101 :           if (epilog->any_estimate)
    3919         8096 :             epilog->nb_iterations_estimate -= lowest_vf;
    3920              :         }
    3921              : 
    3922        34215 :       unsigned HOST_WIDE_INT bound;
    3923        34215 :       if (bound_scalar.is_constant (&bound))
    3924              :         {
    3925        34215 :           gcc_assert (bound != 0);
    3926              :           /* Adjust the upper bound by the extra peeled vector iteration if we
    3927              :              are an epilogue of an peeled vect loop and not VLA.  For VLA the
    3928              :              loop bounds are unknown.  */
    3929        68376 :           if (LOOP_VINFO_EARLY_BREAKS_VECT_PEELED (loop_vinfo)
    3930        34215 :               && vf.is_constant ())
    3931           99 :             bound += vf.to_constant ();
    3932              :           /* -1 to convert loop iterations to latch iterations.  */
    3933        34215 :           record_niter_bound (epilog, bound - 1, false, true);
    3934        34215 :           scale_loop_profile (epilog, profile_probability::always (),
    3935              :                               bound - 1);
    3936              :         }
    3937              : 
    3938        34215 :       delete_update_ssa ();
    3939        34215 :       adjust_vec_debug_stmts ();
    3940        34215 :       scev_reset ();
    3941        34215 :     }
    3942              : 
    3943        34254 :   if (vect_epilogues)
    3944              :     {
    3945         6946 :       epilog->aux = epilogue_vinfo;
    3946         6946 :       LOOP_VINFO_LOOP (epilogue_vinfo) = epilog;
    3947         6946 :       LOOP_VINFO_MAIN_EXIT (epilogue_vinfo)
    3948         6946 :         = LOOP_VINFO_EPILOGUE_MAIN_EXIT (loop_vinfo);
    3949              : 
    3950              :       /* We now must calculate the number of NITERS performed by the previous
    3951              :          loop and EPILOGUE_NITERS to be performed by the epilogue.  */
    3952         6946 :       tree niters = fold_build2 (PLUS_EXPR, TREE_TYPE (niters_vector_mult_vf),
    3953              :                                  niters_prolog, niters_vector_mult_vf);
    3954              : 
    3955              :       /* If skip_vector we may skip the previous loop, we insert a phi-node to
    3956              :          determine whether we are coming from the previous vectorized loop
    3957              :          using the update_e edge or the skip_vector basic block using the
    3958              :          skip_e edge.  */
    3959         6946 :       if (skip_vector)
    3960              :         {
    3961         5730 :           gcc_assert (update_e != NULL && skip_e != NULL);
    3962         5730 :           gphi *new_phi = create_phi_node (make_ssa_name (TREE_TYPE (niters)),
    3963              :                                            update_e->dest);
    3964         5730 :           tree new_ssa = make_ssa_name (TREE_TYPE (niters));
    3965         5730 :           gimple *stmt = gimple_build_assign (new_ssa, niters);
    3966         5730 :           gimple_stmt_iterator gsi;
    3967         5730 :           if (TREE_CODE (niters_vector_mult_vf) == SSA_NAME
    3968         5730 :               && SSA_NAME_DEF_STMT (niters_vector_mult_vf)->bb != NULL)
    3969              :             {
    3970         5730 :               gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (niters_vector_mult_vf));
    3971         5730 :               gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
    3972              :             }
    3973              :           else
    3974              :             {
    3975            0 :               gsi = gsi_last_bb (update_e->src);
    3976            0 :               gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
    3977              :             }
    3978              : 
    3979         5730 :           niters = new_ssa;
    3980         5730 :           add_phi_arg (new_phi, niters, update_e, UNKNOWN_LOCATION);
    3981         5730 :           add_phi_arg (new_phi, build_zero_cst (TREE_TYPE (niters)), skip_e,
    3982              :                        UNKNOWN_LOCATION);
    3983         5730 :           niters = PHI_RESULT (new_phi);
    3984         5730 :           epilogue_vinfo->main_loop_edge = update_e;
    3985         5730 :           epilogue_vinfo->skip_main_loop_edge = skip_e;
    3986              :         }
    3987              : 
    3988              :       /* Set ADVANCE to the number of iterations performed by the previous
    3989              :          loop and its prologue.  */
    3990         6946 :       *advance = niters;
    3991              : 
    3992              :       /* Subtract the number of iterations performed by the vectorized loop
    3993              :          from the number of total iterations.  */
    3994         6946 :       tree epilogue_niters = fold_build2 (MINUS_EXPR, TREE_TYPE (niters),
    3995              :                                           before_loop_niters,
    3996              :                                           niters);
    3997              : 
    3998         6946 :       LOOP_VINFO_NITERS (epilogue_vinfo) = epilogue_niters;
    3999         6946 :       LOOP_VINFO_NITERSM1 (epilogue_vinfo)
    4000         6946 :         = fold_build2 (MINUS_EXPR, TREE_TYPE (epilogue_niters),
    4001              :                        epilogue_niters,
    4002              :                        build_one_cst (TREE_TYPE (epilogue_niters)));
    4003              :     }
    4004              : 
    4005        34254 :   adjust_vec.release ();
    4006        34254 :   free_original_copy_tables ();
    4007              : 
    4008        34254 :   return vect_epilogues ? epilog : NULL;
    4009        34254 : }
    4010              : 
    4011              : /* Set *COND_EXPR to a tree that is true when both the original *COND_EXPR
    4012              :    and PART_COND_EXPR are true.  Treat a null *COND_EXPR as "true".  */
    4013              : 
    4014              : static void
    4015          320 : chain_cond_expr (tree *cond_expr, tree part_cond_expr)
    4016              : {
    4017          320 :   if (*cond_expr)
    4018          316 :     *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
    4019              :                               *cond_expr, part_cond_expr);
    4020              :   else
    4021            4 :     *cond_expr = part_cond_expr;
    4022          320 : }
    4023              : 
    4024              : /* Function vect_create_cond_for_align_checks.
    4025              : 
    4026              :    Create a conditional expression that represents the alignment checks for
    4027              :    all of data references (array element references) whose alignment must be
    4028              :    checked at runtime.
    4029              : 
    4030              :    Input:
    4031              :    COND_EXPR  - input conditional expression.  New conditions will be chained
    4032              :                 with logical AND operation.
    4033              :    LOOP_VINFO - three fields of the loop information are used.
    4034              :                 LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
    4035              :                 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
    4036              :                 LOOP_VINFO_ALLOW_MUTUAL_ALIGNMENT indicates which check applies.
    4037              : 
    4038              :    Output:
    4039              :    COND_EXPR_STMT_LIST - statements needed to construct the conditional
    4040              :                          expression.
    4041              :    The returned value is the conditional expression to be used in the if
    4042              :    statement that controls which version of the loop gets executed at runtime.
    4043              : 
    4044              :    Based on the boolean value of LOOP_VINFO_ALLOW_MUTUAL_ALIGNMENT, we decide
    4045              :    which type of check should be applied and create two different expressions
    4046              :    accordingly.
    4047              :      1) When LOOP_VINFO_ALLOW_MUTUAL_ALIGNMENT is false, we see if all data refs
    4048              :         to be checked are already aligned to an alignment boundary.  We create
    4049              :         an expression of "(a_1 | a_2 | a_3 | ... | a_n) & mask", where "a_i" is
    4050              :         the address of i'th data reference.
    4051              :      2) When LOOP_VINFO_ALLOW_MUTUAL_ALIGNMENT is true, we see if all data refs
    4052              :         can be aligned to a boundary after a certain amount of peeling, in other
    4053              :         words, their addresses have the same bottom bits according to the mask.
    4054              :         We create "((a_1 ^ a_2) | (a_2 ^ a_3) | ... | (a_n-1 ^ a_n)) & mask",
    4055              :         where "a_i" is the address of i'th data reference.
    4056              : 
    4057              :    Both algorithms make two assumptions:
    4058              :      1) The number of bytes "n" in a vector is a power of 2.
    4059              :      2) An address "a" is aligned if a%n is zero and that this
    4060              :         test can be done as a&(n-1) == 0.  For example, for 16
    4061              :         byte vectors the test is a&0xf == 0.  */
    4062              : 
    4063              : static void
    4064           75 : vect_create_cond_for_align_checks (loop_vec_info loop_vinfo,
    4065              :                                    tree *cond_expr,
    4066              :                                    gimple_seq *cond_expr_stmt_list)
    4067              : {
    4068           75 :   const vec<stmt_vec_info> &may_misalign_stmts
    4069              :     = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo);
    4070           75 :   stmt_vec_info stmt_info;
    4071           75 :   poly_uint64 mask = LOOP_VINFO_PTR_MASK (loop_vinfo);
    4072           75 :   tree mask_cst;
    4073           75 :   unsigned int i;
    4074           75 :   tree int_ptrsize_type;
    4075           75 :   char tmp_name[30];
    4076           75 :   tree or_tmp_name = NULL_TREE;
    4077           75 :   tree prev_addr_tmp_name = NULL_TREE;
    4078           75 :   tree and_tmp_name;
    4079           75 :   gimple *and_stmt;
    4080           75 :   tree ptrsize_zero;
    4081           75 :   tree part_cond_expr;
    4082              : 
    4083           75 :   gcc_assert (known_ne (mask, 0U));
    4084              : 
    4085           75 :   int_ptrsize_type = signed_type_for (ptr_type_node);
    4086              : 
    4087              :   /* If LOOP_VINFO_ALLOW_MUTUAL_ALIGNMENT is true, we should have at least two
    4088              :      datarefs to check the mutual alignment.  */
    4089           75 :   gcc_assert (may_misalign_stmts.length () > 1
    4090              :               || !LOOP_VINFO_ALLOW_MUTUAL_ALIGNMENT (loop_vinfo));
    4091              : 
    4092          286 :   FOR_EACH_VEC_ELT (may_misalign_stmts, i, stmt_info)
    4093              :     {
    4094          136 :       gimple_seq new_stmt_list = NULL;
    4095          136 :       tree addr_base;
    4096          136 :       tree addr_tmp_name;
    4097          136 :       tree xor_tmp_name;
    4098          136 :       tree new_or_tmp_name;
    4099          136 :       gimple *addr_stmt, *or_stmt, *xor_stmt;
    4100          136 :       tree vectype = STMT_VINFO_VECTYPE (stmt_info);
    4101          136 :       bool negative = tree_int_cst_compare
    4102          136 :         (DR_STEP (STMT_VINFO_DATA_REF (stmt_info)), size_zero_node) < 0;
    4103          136 :       tree offset = negative
    4104          136 :         ? size_int ((-TYPE_VECTOR_SUBPARTS (vectype) + 1)
    4105              :                     * TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (vectype))))
    4106           94 :         : size_zero_node;
    4107              : 
    4108              :       /* create: addr_tmp = (int)(address_of_first_vector) */
    4109          136 :       addr_base =
    4110          136 :         vect_create_addr_base_for_vector_ref (loop_vinfo,
    4111              :                                               stmt_info, &new_stmt_list,
    4112              :                                               offset);
    4113          136 :       if (new_stmt_list != NULL)
    4114           56 :         gimple_seq_add_seq (cond_expr_stmt_list, new_stmt_list);
    4115              : 
    4116          136 :       sprintf (tmp_name, "addr2int%d", i);
    4117          136 :       addr_tmp_name = make_temp_ssa_name (int_ptrsize_type, NULL, tmp_name);
    4118          136 :       addr_stmt = gimple_build_assign (addr_tmp_name, NOP_EXPR, addr_base);
    4119          136 :       gimple_seq_add_stmt (cond_expr_stmt_list, addr_stmt);
    4120              : 
    4121          136 :       if (LOOP_VINFO_ALLOW_MUTUAL_ALIGNMENT (loop_vinfo))
    4122              :         {
    4123              :           /* Create "((a_1 ^ a_2) | (a_2 ^ a_3) | ... | (a_n-1 ^ a_n)) & mask"
    4124              :              to check mutual alignment.  */
    4125           36 :           if (prev_addr_tmp_name != NULL_TREE)
    4126              :             {
    4127           18 :               sprintf (tmp_name, "xorptrs%d_%d", i - 1, i);
    4128           18 :               xor_tmp_name = make_temp_ssa_name (int_ptrsize_type, NULL,
    4129              :                                                  tmp_name);
    4130           18 :               xor_stmt = gimple_build_assign (xor_tmp_name, BIT_XOR_EXPR,
    4131              :                                               prev_addr_tmp_name,
    4132              :                                               addr_tmp_name);
    4133           18 :               gimple_seq_add_stmt (cond_expr_stmt_list, xor_stmt);
    4134           18 :               if (or_tmp_name == NULL_TREE)
    4135              :                 {
    4136              :                   /* Create the 1st XOR when the 2nd data ref is seen.  */
    4137              :                   or_tmp_name = xor_tmp_name;
    4138              :                 }
    4139              :               else
    4140              :                 {
    4141              :                   /* Create: or_tmp = or_tmp | new_xor_tmp.  */
    4142            0 :                   sprintf (tmp_name, "orxors%d", i - 1);
    4143            0 :                   new_or_tmp_name = make_temp_ssa_name (int_ptrsize_type, NULL,
    4144              :                                                         tmp_name);
    4145            0 :                   or_stmt = gimple_build_assign (new_or_tmp_name, BIT_IOR_EXPR,
    4146              :                                                  or_tmp_name, xor_tmp_name);
    4147            0 :                   gimple_seq_add_stmt (cond_expr_stmt_list, or_stmt);
    4148            0 :                   or_tmp_name = new_or_tmp_name;
    4149              :                 }
    4150              :             }
    4151              :           prev_addr_tmp_name = addr_tmp_name;
    4152              :         }
    4153              :       else
    4154              :         {
    4155              :           /* Create: "(a_1 | a_2 | a_3 | ... | a_n) & mask" to check if all
    4156              :              addresses are already aligned.  */
    4157          100 :           if (or_tmp_name != NULL_TREE)
    4158              :             {
    4159              :               /* Create: or_tmp = or_tmp | addr_tmp.  */
    4160           43 :               sprintf (tmp_name, "orptrs%d", i);
    4161           43 :               new_or_tmp_name = make_temp_ssa_name (int_ptrsize_type, NULL,
    4162              :                                                     tmp_name);
    4163           43 :               or_stmt = gimple_build_assign (new_or_tmp_name, BIT_IOR_EXPR,
    4164              :                                              or_tmp_name, addr_tmp_name);
    4165           43 :               gimple_seq_add_stmt (cond_expr_stmt_list, or_stmt);
    4166           43 :               or_tmp_name = new_or_tmp_name;
    4167              :             }
    4168              :           else
    4169              :             or_tmp_name = addr_tmp_name;
    4170              :         }
    4171              : 
    4172              :     } /* end for i */
    4173              : 
    4174           75 :   mask_cst = build_int_cst (int_ptrsize_type, mask);
    4175              : 
    4176              :   /* create: and_tmp = or_tmp & mask  */
    4177           75 :   and_tmp_name = make_temp_ssa_name (int_ptrsize_type, NULL, "andmask");
    4178              : 
    4179           75 :   and_stmt = gimple_build_assign (and_tmp_name, BIT_AND_EXPR,
    4180              :                                   or_tmp_name, mask_cst);
    4181           75 :   gimple_seq_add_stmt (cond_expr_stmt_list, and_stmt);
    4182              : 
    4183              :   /* Make and_tmp the left operand of the conditional test against zero.
    4184              :      if and_tmp has a nonzero bit then some address is unaligned.  */
    4185           75 :   ptrsize_zero = build_int_cst (int_ptrsize_type, 0);
    4186           75 :   part_cond_expr = fold_build2 (EQ_EXPR, boolean_type_node,
    4187              :                                 and_tmp_name, ptrsize_zero);
    4188           75 :   chain_cond_expr (cond_expr, part_cond_expr);
    4189           75 : }
    4190              : 
    4191              : /* Function vect_create_cond_for_vla_spec_read.
    4192              : 
    4193              :    Create a conditional expression that represents the run-time checks with
    4194              :    max speculative read amount in VLA modes.  We check two things:
    4195              :      1) if the max speculative read amount exceeds the min page size
    4196              :      2) if the VF is power-of-2 - done by checking the max read amount instead
    4197              : 
    4198              :    Input:
    4199              :    COND_EXPR  - input conditional expression.  New conditions will be chained
    4200              :                 with logical AND operation.
    4201              :    LOOP_VINFO - field LOOP_VINFO_MAX_SPEC_READ_AMOUNT contains the max
    4202              :                 possible speculative read amount in VLA modes.
    4203              : 
    4204              :    Output:
    4205              :    COND_EXPR - conditional expression.
    4206              : 
    4207              :    The returned COND_EXPR is the conditional expression to be used in the
    4208              :    if statement that controls which version of the loop gets executed at
    4209              :    runtime.  */
    4210              : 
    4211              : static void
    4212            0 : vect_create_cond_for_vla_spec_read (loop_vec_info loop_vinfo, tree *cond_expr)
    4213              : {
    4214            0 :   poly_uint64 read_amount_poly = LOOP_VINFO_MAX_SPEC_READ_AMOUNT (loop_vinfo);
    4215            0 :   tree amount = build_int_cst (long_unsigned_type_node, read_amount_poly);
    4216              : 
    4217              :   /* Both the read amount and the VF must be variants, and the read amount must
    4218              :      be a constant power-of-2 multiple of the VF.  */
    4219            0 :   unsigned HOST_WIDE_INT multiple;
    4220            0 :   gcc_assert (!read_amount_poly.is_constant ()
    4221              :               && !LOOP_VINFO_VECT_FACTOR (loop_vinfo).is_constant ()
    4222              :               && constant_multiple_p (read_amount_poly,
    4223              :                                       LOOP_VINFO_VECT_FACTOR (loop_vinfo),
    4224              :                                       &multiple)
    4225              :               && pow2p_hwi (multiple));
    4226              : 
    4227              :   tree cst_ul_zero = build_int_cstu (long_unsigned_type_node, 0U);
    4228              :   tree cst_ul_one = build_int_cstu (long_unsigned_type_node, 1U);
    4229              :   tree cst_ul_pagesize = build_int_cstu (long_unsigned_type_node,
    4230              :                                          (unsigned long) param_min_pagesize);
    4231              : 
    4232              :   /* Create an expression of "amount & (amount - 1) == 0".  */
    4233              :   tree amount_m1 = fold_build2 (MINUS_EXPR, long_unsigned_type_node,
    4234              :                                 amount, cst_ul_one);
    4235              :   tree amount_and_expr = fold_build2 (BIT_AND_EXPR, long_unsigned_type_node,
    4236              :                                       amount, amount_m1);
    4237              :   tree powof2_cond_expr = fold_build2 (EQ_EXPR, boolean_type_node,
    4238              :                                        amount_and_expr, cst_ul_zero);
    4239              :   chain_cond_expr (cond_expr, powof2_cond_expr);
    4240              : 
    4241              :   /* Create an expression of "amount <= cst_ul_pagesize".  */
    4242              :   tree pagesize_cond_expr = fold_build2 (LE_EXPR, boolean_type_node,
    4243              :                                          amount, cst_ul_pagesize);
    4244              :   chain_cond_expr (cond_expr, pagesize_cond_expr);
    4245              : }
    4246              : 
    4247              : /* If LOOP_VINFO_CHECK_UNEQUAL_ADDRS contains <A1, B1>, ..., <An, Bn>,
    4248              :    create a tree representation of: (&A1 != &B1) && ... && (&An != &Bn).
    4249              :    Set *COND_EXPR to a tree that is true when both the original *COND_EXPR
    4250              :    and this new condition are true.  Treat a null *COND_EXPR as "true".  */
    4251              : 
    4252              : static void
    4253         3375 : vect_create_cond_for_unequal_addrs (loop_vec_info loop_vinfo, tree *cond_expr)
    4254              : {
    4255         3375 :   const vec<vec_object_pair> &pairs
    4256              :     = LOOP_VINFO_CHECK_UNEQUAL_ADDRS (loop_vinfo);
    4257         3375 :   unsigned int i;
    4258         3375 :   vec_object_pair *pair;
    4259         3387 :   FOR_EACH_VEC_ELT (pairs, i, pair)
    4260              :     {
    4261           12 :       tree addr1 = build_fold_addr_expr (pair->first);
    4262           12 :       tree addr2 = build_fold_addr_expr (pair->second);
    4263           12 :       tree part_cond_expr = fold_build2 (NE_EXPR, boolean_type_node,
    4264              :                                          addr1, addr2);
    4265           12 :       chain_cond_expr (cond_expr, part_cond_expr);
    4266              :     }
    4267         3375 : }
    4268              : 
    4269              : /* Create an expression that is true when all lower-bound conditions for
    4270              :    the vectorized loop are met.  Chain this condition with *COND_EXPR.  */
    4271              : 
    4272              : static void
    4273         3375 : vect_create_cond_for_lower_bounds (loop_vec_info loop_vinfo, tree *cond_expr)
    4274              : {
    4275         3375 :   const vec<vec_lower_bound> &lower_bounds
    4276              :     = LOOP_VINFO_LOWER_BOUNDS (loop_vinfo);
    4277         3608 :   for (unsigned int i = 0; i < lower_bounds.length (); ++i)
    4278              :     {
    4279          233 :       tree expr = lower_bounds[i].expr;
    4280          233 :       tree type = unsigned_type_for (TREE_TYPE (expr));
    4281          233 :       expr = fold_convert (type, expr);
    4282          233 :       poly_uint64 bound = lower_bounds[i].min_value;
    4283          233 :       if (!lower_bounds[i].unsigned_p)
    4284              :         {
    4285           73 :           expr = fold_build2 (PLUS_EXPR, type, expr,
    4286              :                               build_int_cstu (type, bound - 1));
    4287           73 :           bound += bound - 1;
    4288              :         }
    4289          233 :       tree part_cond_expr = fold_build2 (GE_EXPR, boolean_type_node, expr,
    4290              :                                          build_int_cstu (type, bound));
    4291          233 :       chain_cond_expr (cond_expr, part_cond_expr);
    4292              :     }
    4293         3375 : }
    4294              : 
    4295              : /* Function vect_create_cond_for_alias_checks.
    4296              : 
    4297              :    Create a conditional expression that represents the run-time checks for
    4298              :    overlapping of address ranges represented by a list of data references
    4299              :    relations passed as input.
    4300              : 
    4301              :    Input:
    4302              :    COND_EXPR  - input conditional expression.  New conditions will be chained
    4303              :                 with logical AND operation.  If it is NULL, then the function
    4304              :                 is used to return the number of alias checks.
    4305              :    LOOP_VINFO - field LOOP_VINFO_MAY_ALIAS_STMTS contains the list of ddrs
    4306              :                 to be checked.
    4307              : 
    4308              :    Output:
    4309              :    COND_EXPR - conditional expression.
    4310              : 
    4311              :    The returned COND_EXPR is the conditional expression to be used in the if
    4312              :    statement that controls which version of the loop gets executed at runtime.
    4313              : */
    4314              : 
    4315              : void
    4316         3375 : vect_create_cond_for_alias_checks (loop_vec_info loop_vinfo, tree * cond_expr)
    4317              : {
    4318         3375 :   const vec<dr_with_seg_len_pair_t> &comp_alias_ddrs =
    4319              :     LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo);
    4320              : 
    4321         3375 :   if (comp_alias_ddrs.is_empty ())
    4322              :     return;
    4323              : 
    4324         3262 :   create_runtime_alias_checks (LOOP_VINFO_LOOP (loop_vinfo),
    4325              :                                &comp_alias_ddrs, cond_expr);
    4326         3262 :   if (dump_enabled_p ())
    4327         1340 :     dump_printf_loc (MSG_NOTE, vect_location,
    4328              :                      "created %u versioning for alias checks.\n",
    4329              :                      comp_alias_ddrs.length ());
    4330              : }
    4331              : 
    4332              : 
    4333              : /* Function vect_loop_versioning.
    4334              : 
    4335              :    If the loop has data references that may or may not be aligned or/and
    4336              :    has data reference relations whose independence was not proven then
    4337              :    two versions of the loop need to be generated, one which is vectorized
    4338              :    and one which isn't.  A test is then generated to control which of the
    4339              :    loops is executed.  The test checks for the alignment of all of the
    4340              :    data references that may or may not be aligned.  An additional
    4341              :    sequence of runtime tests is generated for each pairs of DDRs whose
    4342              :    independence was not proven.  The vectorized version of loop is
    4343              :    executed only if both alias and alignment tests are passed.
    4344              : 
    4345              :    The test generated to check which version of loop is executed
    4346              :    is modified to also check for profitability as indicated by the
    4347              :    cost model threshold TH.
    4348              : 
    4349              :    The versioning precondition(s) are placed in *COND_EXPR and
    4350              :    *COND_EXPR_STMT_LIST.  */
    4351              : 
    4352              : class loop *
    4353         3906 : vect_loop_versioning (loop_vec_info loop_vinfo,
    4354              :                       gimple *loop_vectorized_call)
    4355              : {
    4356         3906 :   class loop *loop = LOOP_VINFO_LOOP (loop_vinfo), *nloop;
    4357         3906 :   class loop *scalar_loop = LOOP_VINFO_SCALAR_LOOP (loop_vinfo);
    4358         3906 :   basic_block condition_bb;
    4359         3906 :   gphi_iterator gsi;
    4360         3906 :   gimple_stmt_iterator cond_exp_gsi;
    4361         3906 :   basic_block merge_bb;
    4362         3906 :   basic_block new_exit_bb;
    4363         3906 :   edge new_exit_e, e;
    4364         3906 :   gphi *orig_phi, *new_phi;
    4365         3906 :   tree cond_expr = NULL_TREE;
    4366         3906 :   tree arg;
    4367         3906 :   profile_probability prob = profile_probability::likely ();
    4368         3906 :   gimple_seq gimplify_stmt_list = NULL;
    4369         3906 :   tree scalar_loop_iters = LOOP_VINFO_NITERSM1 (loop_vinfo);
    4370         3906 :   bool version_align = LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo);
    4371         3906 :   bool version_spec_read = LOOP_REQUIRES_VERSIONING_FOR_SPEC_READ (loop_vinfo);
    4372         3906 :   bool version_alias = LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo);
    4373         3906 :   bool version_niter = LOOP_REQUIRES_VERSIONING_FOR_NITERS (loop_vinfo);
    4374         3906 :   poly_uint64 versioning_threshold
    4375              :     = LOOP_VINFO_VERSIONING_THRESHOLD (loop_vinfo);
    4376         3906 :   tree version_simd_if_cond
    4377              :     = LOOP_REQUIRES_VERSIONING_FOR_SIMD_IF_COND (loop_vinfo);
    4378         3906 :   unsigned th = LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo);
    4379         3906 :   bool uncounted_p = LOOP_VINFO_NITERS_UNCOUNTED_P (loop_vinfo);
    4380              : 
    4381              :   /* Start with the niter assumptions so they are split out together
    4382              :      with the cost model check, short-circuiting all other checks
    4383              :      since niter information is not valid when the assumptions do not
    4384              :      hold.  */
    4385         3906 :   if (version_niter)
    4386          448 :     cond_expr = LOOP_VINFO_NITERS_ASSUMPTIONS (loop_vinfo);
    4387              : 
    4388         3906 :   if (!uncounted_p
    4389              :       && vect_apply_runtime_profitability_check_p (loop_vinfo)
    4390              :       && !ordered_p (th, versioning_threshold))
    4391              :     {
    4392              :       tree expr = fold_build2 (GE_EXPR, boolean_type_node, scalar_loop_iters,
    4393              :                                build_int_cst (TREE_TYPE (scalar_loop_iters),
    4394              :                                               th - 1));
    4395              :       if (cond_expr)
    4396              :         cond_expr = fold_build2 (BIT_AND_EXPR, boolean_type_node,
    4397              :                                  expr, cond_expr);
    4398              :       else
    4399              :         cond_expr = expr;
    4400              :     }
    4401              : 
    4402         3906 :   if (!uncounted_p && maybe_ne (versioning_threshold, 0U))
    4403              :     {
    4404         3893 :       tree expr = fold_build2 (GE_EXPR, boolean_type_node, scalar_loop_iters,
    4405              :                                build_int_cst (TREE_TYPE (scalar_loop_iters),
    4406              :                                               versioning_threshold - 1));
    4407         3893 :       if (cond_expr)
    4408          448 :         cond_expr = fold_build2 (BIT_AND_EXPR, boolean_type_node,
    4409              :                                  expr, cond_expr);
    4410              :       else
    4411         3445 :         cond_expr = expr;
    4412              :     }
    4413              : 
    4414         3906 :   tree cost_name = NULL_TREE;
    4415         3906 :   gimple_seq cond_expr_stmt_list = NULL;
    4416         3906 :   profile_probability prob2 = profile_probability::always ();
    4417         3906 :   if (cond_expr
    4418         3893 :       && EXPR_P (cond_expr)
    4419         2806 :       && (version_niter
    4420         2806 :           || version_align
    4421              :           || version_alias
    4422         2311 :           || version_simd_if_cond))
    4423              :     {
    4424         2806 :       cost_name = cond_expr = force_gimple_operand_1 (unshare_expr (cond_expr),
    4425              :                                                       &cond_expr_stmt_list,
    4426              :                                                       is_gimple_val, NULL_TREE);
    4427              :       /* Split prob () into two so that the overall probability of passing
    4428              :          both the cost-model and versioning checks is the orig prob.  */
    4429         2806 :       prob2 = prob = prob.sqrt ();
    4430              :       /* Rewrite to defined if there was an niter versioning condition.
    4431              :          ???  We fail to be more selective with respect to niter may_be_zero
    4432              :          and assumptions.  */
    4433         2806 :       if (version_niter)
    4434         4012 :         for (auto gsi = gsi_start (cond_expr_stmt_list); !gsi_end_p (gsi);
    4435         3116 :              gsi_next (&gsi))
    4436         3116 :           if (gimple_needing_rewrite_undefined (gsi_stmt (gsi)))
    4437          117 :             rewrite_to_defined_unconditional (&gsi);
    4438              :     }
    4439              : 
    4440         3906 :   if (cond_expr)
    4441              :     {
    4442         3893 :       gimple_seq tem = NULL;
    4443         3893 :       cond_expr = force_gimple_operand_1 (unshare_expr (cond_expr),
    4444              :                                           &tem, is_gimple_condexpr_for_cond,
    4445              :                                           NULL_TREE);
    4446         3893 :       gimple_seq_add_seq (&cond_expr_stmt_list, tem);
    4447              :     }
    4448              : 
    4449         3906 :   if (version_align)
    4450           75 :     vect_create_cond_for_align_checks (loop_vinfo, &cond_expr,
    4451              :                                        &cond_expr_stmt_list);
    4452              : 
    4453         3906 :   if (version_spec_read)
    4454            0 :     vect_create_cond_for_vla_spec_read (loop_vinfo, &cond_expr);
    4455              : 
    4456         3906 :   if (version_alias)
    4457              :     {
    4458         3375 :       vect_create_cond_for_unequal_addrs (loop_vinfo, &cond_expr);
    4459         3375 :       vect_create_cond_for_lower_bounds (loop_vinfo, &cond_expr);
    4460         3375 :       vect_create_cond_for_alias_checks (loop_vinfo, &cond_expr);
    4461              :     }
    4462              : 
    4463         3906 :   if (version_simd_if_cond)
    4464              :     {
    4465           62 :       gcc_assert (dom_info_available_p (CDI_DOMINATORS));
    4466           62 :       if (flag_checking)
    4467           62 :         if (basic_block bb
    4468           62 :             = gimple_bb (SSA_NAME_DEF_STMT (version_simd_if_cond)))
    4469           62 :           gcc_assert (bb != loop->header
    4470              :                       && dominated_by_p (CDI_DOMINATORS, loop->header, bb)
    4471              :                       && (scalar_loop == NULL
    4472              :                           || (bb != scalar_loop->header
    4473              :                               && dominated_by_p (CDI_DOMINATORS,
    4474              :                                                  scalar_loop->header, bb))));
    4475           62 :       tree zero = build_zero_cst (TREE_TYPE (version_simd_if_cond));
    4476           62 :       tree c = fold_build2 (NE_EXPR, boolean_type_node,
    4477              :                             version_simd_if_cond, zero);
    4478           62 :       if (cond_expr)
    4479           62 :         cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
    4480              :                                  c, cond_expr);
    4481              :       else
    4482              :         cond_expr = c;
    4483           62 :       if (dump_enabled_p ())
    4484            5 :         dump_printf_loc (MSG_NOTE, vect_location,
    4485              :                          "created versioning for simd if condition check.\n");
    4486              :     }
    4487              : 
    4488         3906 :   cond_expr = force_gimple_operand_1 (unshare_expr (cond_expr),
    4489              :                                       &gimplify_stmt_list,
    4490              :                                       is_gimple_condexpr_for_cond, NULL_TREE);
    4491         3906 :   gimple_seq_add_seq (&cond_expr_stmt_list, gimplify_stmt_list);
    4492              : 
    4493              :   /* Compute the outermost loop cond_expr and cond_expr_stmt_list are
    4494              :      invariant in.  */
    4495         3906 :   class loop *outermost = outermost_invariant_loop_for_expr (loop, cond_expr);
    4496         3906 :   for (gimple_stmt_iterator gsi = gsi_start (cond_expr_stmt_list);
    4497        70785 :        !gsi_end_p (gsi); gsi_next (&gsi))
    4498              :     {
    4499        66879 :       gimple *stmt = gsi_stmt (gsi);
    4500        66879 :       update_stmt (stmt);
    4501        66879 :       ssa_op_iter iter;
    4502        66879 :       use_operand_p use_p;
    4503        66879 :       basic_block def_bb;
    4504       153878 :       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
    4505        86999 :         if ((def_bb = gimple_bb (SSA_NAME_DEF_STMT (USE_FROM_PTR (use_p))))
    4506        86999 :             && flow_bb_inside_loop_p (outermost, def_bb))
    4507         2629 :           outermost = superloop_at_depth (loop, bb_loop_depth (def_bb) + 1);
    4508              :     }
    4509              : 
    4510              :   /* Search for the outermost loop we can version.  Avoid versioning of
    4511              :      non-perfect nests but allow if-conversion versioned loops inside.  */
    4512         3906 :   class loop *loop_to_version = loop;
    4513         3906 :   if (flow_loop_nested_p (outermost, loop))
    4514              :     {
    4515         1518 :       if (dump_enabled_p ())
    4516          743 :         dump_printf_loc (MSG_NOTE, vect_location,
    4517              :                          "trying to apply versioning to outer loop %d\n",
    4518              :                          outermost->num);
    4519         1518 :       if (outermost->num == 0)
    4520         1442 :         outermost = superloop_at_depth (loop, 1);
    4521              :       /* And avoid applying versioning on non-perfect nests.  */
    4522              :       while (loop_to_version != outermost
    4523           99 :              && (e = single_exit (loop_outer (loop_to_version)))
    4524           80 :              && !(e->flags & EDGE_COMPLEX)
    4525           80 :              && (!loop_outer (loop_to_version)->inner->next
    4526           52 :                  || vect_loop_vectorized_call (loop_to_version))
    4527           32 :              && (!loop_outer (loop_to_version)->inner->next
    4528            4 :                  || !loop_outer (loop_to_version)->inner->next->next)
    4529         1580 :              && can_duplicate_loop_p (loop_outer (loop_to_version)))
    4530           30 :         loop_to_version = loop_outer (loop_to_version);
    4531              :     }
    4532              : 
    4533              :   /* Apply versioning.  If there is already a scalar version created by
    4534              :      if-conversion re-use that.  Note we cannot re-use the copy of
    4535              :      an if-converted outer-loop when vectorizing the inner loop only.  */
    4536         3906 :   gcond *cond;
    4537         3906 :   if ((!loop_to_version->inner || loop == loop_to_version)
    4538         3880 :       && loop_vectorized_call)
    4539              :     {
    4540           90 :       gcc_assert (scalar_loop);
    4541           90 :       condition_bb = gimple_bb (loop_vectorized_call);
    4542          180 :       cond = as_a <gcond *> (*gsi_last_bb (condition_bb));
    4543           90 :       gimple_cond_set_condition_from_tree (cond, cond_expr);
    4544           90 :       update_stmt (cond);
    4545              : 
    4546           90 :       if (cond_expr_stmt_list)
    4547              :         {
    4548           90 :           cond_exp_gsi = gsi_for_stmt (loop_vectorized_call);
    4549           90 :           gsi_insert_seq_before (&cond_exp_gsi, cond_expr_stmt_list,
    4550              :                                  GSI_SAME_STMT);
    4551              :         }
    4552              : 
    4553              :       /* if-conversion uses profile_probability::always () for both paths,
    4554              :          reset the paths probabilities appropriately.  */
    4555           90 :       edge te, fe;
    4556           90 :       extract_true_false_edges_from_block (condition_bb, &te, &fe);
    4557           90 :       te->probability = prob;
    4558           90 :       fe->probability = prob.invert ();
    4559              :       /* We can scale loops counts immediately but have to postpone
    4560              :          scaling the scalar loop because we re-use it during peeling.
    4561              : 
    4562              :          Ifcvt duplicates loop preheader, loop body and produces an basic
    4563              :          block after loop exit.  We need to scale all that.  */
    4564           90 :       basic_block preheader = loop_preheader_edge (loop_to_version)->src;
    4565           90 :       preheader->count = preheader->count.apply_probability (prob * prob2);
    4566           90 :       scale_loop_frequencies (loop_to_version, prob * prob2);
    4567              :       /* When the loop has multiple exits then we can only version itself.
    4568              :         This is denoted by loop_to_version == loop.  In this case we can
    4569              :         do the versioning by selecting the exit edge the vectorizer is
    4570              :         currently using.  */
    4571           90 :       edge exit_edge;
    4572           90 :       if (loop_to_version == loop)
    4573           90 :        exit_edge = LOOP_VINFO_MAIN_EXIT (loop_vinfo);
    4574              :       else
    4575            0 :        exit_edge = single_exit (loop_to_version);
    4576           90 :       exit_edge->dest->count = preheader->count;
    4577           90 :       LOOP_VINFO_SCALAR_LOOP_SCALING (loop_vinfo) = (prob * prob2).invert ();
    4578              : 
    4579           90 :       nloop = scalar_loop;
    4580           90 :       if (dump_enabled_p ())
    4581           90 :         dump_printf_loc (MSG_NOTE, vect_location,
    4582              :                          "reusing %sloop version created by if conversion\n",
    4583              :                          loop_to_version != loop ? "outer " : "");
    4584           90 :     }
    4585              :   else
    4586              :     {
    4587         3816 :       if (loop_to_version != loop
    4588         3816 :           && dump_enabled_p ())
    4589           13 :         dump_printf_loc (MSG_NOTE, vect_location,
    4590              :                          "applying loop versioning to outer loop %d\n",
    4591              :                          loop_to_version->num);
    4592              : 
    4593         3816 :       unsigned orig_pe_idx = loop_preheader_edge (loop)->dest_idx;
    4594              : 
    4595         3816 :       initialize_original_copy_tables ();
    4596         7632 :       nloop = loop_version (loop_to_version, cond_expr, &condition_bb,
    4597         3816 :                             prob * prob2, (prob * prob2).invert (),
    4598         3816 :                             prob * prob2, (prob * prob2).invert (),
    4599              :                             true);
    4600              : 
    4601              :       /* If the PHI nodes in the loop header were reallocated, we need to fix up
    4602              :          our internally stashed copies of those.  */
    4603         3816 :       if (loop_to_version == loop)
    4604         3790 :         for (auto gsi = gsi_start_phis (loop->header);
    4605        15032 :              !gsi_end_p (gsi); gsi_next (&gsi))
    4606        11242 :           loop_vinfo->resync_stmt_addr (gsi.phi ());
    4607              : 
    4608              :       /* We will later insert second conditional so overall outcome of
    4609              :          both is prob * prob2.  */
    4610         3816 :       edge true_e, false_e;
    4611         3816 :       extract_true_false_edges_from_block (condition_bb, &true_e, &false_e);
    4612         3816 :       true_e->probability = prob;
    4613         3816 :       false_e->probability = prob.invert ();
    4614         3816 :       gcc_assert (nloop);
    4615         3816 :       nloop = get_loop_copy (loop);
    4616              : 
    4617              :       /* For cycle vectorization with SLP we rely on the PHI arguments
    4618              :          appearing in the same order as the SLP node operands which for the
    4619              :          loop PHI nodes means the preheader edge dest index needs to remain
    4620              :          the same for the analyzed loop which also becomes the vectorized one.
    4621              :          Make it so in case the state after versioning differs by redirecting
    4622              :          the first edge into the header to the same destination which moves
    4623              :          it last.  */
    4624         3816 :       if (loop_preheader_edge (loop)->dest_idx != orig_pe_idx)
    4625              :         {
    4626          340 :           edge e = EDGE_PRED (loop->header, 0);
    4627          340 :           ssa_redirect_edge (e, e->dest);
    4628          340 :           flush_pending_stmts (e);
    4629              :         }
    4630         3816 :       gcc_assert (loop_preheader_edge (loop)->dest_idx == orig_pe_idx);
    4631              : 
    4632              :       /* Kill off IFN_LOOP_VECTORIZED_CALL in the copy, nobody will
    4633              :          reap those otherwise;  they also refer to the original
    4634              :          loops.  */
    4635              :       class loop *l = loop;
    4636         3820 :       while (gimple *call = vect_loop_vectorized_call (l))
    4637              :         {
    4638            4 :           call = SSA_NAME_DEF_STMT (get_current_def (gimple_call_lhs (call)));
    4639            4 :           fold_loop_internal_call (call, boolean_false_node);
    4640            4 :           l = loop_outer (l);
    4641            4 :         }
    4642         3816 :       free_original_copy_tables ();
    4643              : 
    4644         3816 :       if (cond_expr_stmt_list)
    4645              :         {
    4646         3789 :           cond_exp_gsi = gsi_last_bb (condition_bb);
    4647         3789 :           gsi_insert_seq_before (&cond_exp_gsi, cond_expr_stmt_list,
    4648              :                                  GSI_SAME_STMT);
    4649              :         }
    4650              : 
    4651              :       /* Loop versioning violates an assumption we try to maintain during
    4652              :          vectorization - that the loop exit block has a single predecessor.
    4653              :          After versioning, the exit block of both loop versions is the same
    4654              :          basic block (i.e. it has two predecessors). Just in order to simplify
    4655              :          following transformations in the vectorizer, we fix this situation
    4656              :          here by adding a new (empty) block on the exit-edge of the loop,
    4657              :          with the proper loop-exit phis to maintain loop-closed-form.
    4658              :          If loop versioning wasn't done from loop, but scalar_loop instead,
    4659              :          merge_bb will have already just a single successor.  */
    4660              : 
    4661              :       /* When the loop has multiple exits then we can only version itself.
    4662              :          This is denoted by loop_to_version == loop.  In this case we can
    4663              :          do the versioning by selecting the exit edge the vectorizer is
    4664              :          currently using.  */
    4665         3816 :       edge exit_edge;
    4666         3816 :       if (loop_to_version == loop)
    4667         3790 :         exit_edge = LOOP_VINFO_MAIN_EXIT (loop_vinfo);
    4668              :       else
    4669           26 :         exit_edge = single_exit (loop_to_version);
    4670              : 
    4671         3816 :       gcc_assert (exit_edge);
    4672         3816 :       merge_bb = exit_edge->dest;
    4673         3816 :       if (EDGE_COUNT (merge_bb->preds) >= 2)
    4674              :         {
    4675         3816 :           gcc_assert (EDGE_COUNT (merge_bb->preds) >= 2);
    4676         3816 :           new_exit_bb = split_edge (exit_edge);
    4677         3816 :           new_exit_e = exit_edge;
    4678         3816 :           e = EDGE_SUCC (new_exit_bb, 0);
    4679              : 
    4680         7884 :           for (gsi = gsi_start_phis (merge_bb); !gsi_end_p (gsi);
    4681         4068 :                gsi_next (&gsi))
    4682              :             {
    4683         4068 :               tree new_res;
    4684         4068 :               orig_phi = gsi.phi ();
    4685         4068 :               new_res = copy_ssa_name (PHI_RESULT (orig_phi));
    4686         4068 :               new_phi = create_phi_node (new_res, new_exit_bb);
    4687         4068 :               arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
    4688         4068 :               add_phi_arg (new_phi, arg, new_exit_e,
    4689              :                            gimple_phi_arg_location_from_edge (orig_phi, e));
    4690         4068 :               adjust_phi_and_debug_stmts (orig_phi, e, PHI_RESULT (new_phi));
    4691              :             }
    4692              :         }
    4693              : 
    4694         3816 :       update_ssa (TODO_update_ssa_no_phi);
    4695              :     }
    4696              : 
    4697              :   /* Split the cost model check off to a separate BB.  Costing assumes
    4698              :      this is the only thing we perform when we enter the scalar loop
    4699              :      from a failed cost decision.  */
    4700         3906 :   if (cost_name && TREE_CODE (cost_name) == SSA_NAME)
    4701              :     {
    4702         2806 :       gimple *def = SSA_NAME_DEF_STMT (cost_name);
    4703         2806 :       gcc_assert (gimple_bb (def) == condition_bb);
    4704              :       /* All uses of the cost check are 'true' after the check we
    4705              :          are going to insert.  */
    4706         2806 :       replace_uses_by (cost_name, boolean_true_node);
    4707              :       /* And we're going to build the new single use of it.  */
    4708         2806 :       gcond *cond = gimple_build_cond (NE_EXPR, cost_name, boolean_false_node,
    4709              :                                        NULL_TREE, NULL_TREE);
    4710         2806 :       edge e = split_block (gimple_bb (def), def);
    4711         2806 :       gimple_stmt_iterator gsi = gsi_for_stmt (def);
    4712         2806 :       gsi_insert_after (&gsi, cond, GSI_NEW_STMT);
    4713         2806 :       edge true_e, false_e;
    4714         2806 :       extract_true_false_edges_from_block (e->dest, &true_e, &false_e);
    4715         2806 :       e->flags &= ~EDGE_FALLTHRU;
    4716         2806 :       e->flags |= EDGE_TRUE_VALUE;
    4717         2806 :       edge e2 = make_edge (e->src, false_e->dest, EDGE_FALSE_VALUE);
    4718         2806 :       e->probability = prob2;
    4719         2806 :       e2->probability = prob2.invert ();
    4720         2806 :       e->dest->count = e->count ();
    4721         2806 :       set_immediate_dominator (CDI_DOMINATORS, false_e->dest, e->src);
    4722         2806 :       auto_vec<basic_block, 3> adj;
    4723         2806 :       for (basic_block son = first_dom_son (CDI_DOMINATORS, e->dest);
    4724         8386 :            son;
    4725         5580 :            son = next_dom_son (CDI_DOMINATORS, son))
    4726         8354 :         if (EDGE_COUNT (son->preds) > 1)
    4727         2774 :           adj.safe_push (son);
    4728        11192 :       for (auto son : adj)
    4729         2774 :         set_immediate_dominator (CDI_DOMINATORS, son, e->src);
    4730              :       //debug_bb (condition_bb);
    4731              :       //debug_bb (e->src);
    4732         2806 :     }
    4733              : 
    4734         3906 :   if (version_niter)
    4735              :     {
    4736              :       /* The versioned loop could be infinite, we need to clear existing
    4737              :          niter information which is copied from the original loop.  */
    4738          448 :       gcc_assert (loop_constraint_set_p (loop, LOOP_C_FINITE));
    4739          448 :       vect_free_loop_info_assumptions (nloop);
    4740              :     }
    4741              : 
    4742         3906 :   if (LOCATION_LOCUS (vect_location.get_location_t ()) != UNKNOWN_LOCATION
    4743         3906 :       && dump_enabled_p ())
    4744              :     {
    4745          885 :       if (version_alias)
    4746          774 :         dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | MSG_PRIORITY_USER_FACING,
    4747              :                          vect_location,
    4748              :                          "loop versioned for vectorization because of "
    4749              :                          "possible aliasing\n");
    4750          885 :       if (version_align)
    4751           60 :         dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | MSG_PRIORITY_USER_FACING,
    4752              :                          vect_location,
    4753              :                          "loop versioned for vectorization to enhance "
    4754              :                          "alignment\n");
    4755              : 
    4756              :     }
    4757              : 
    4758         3906 :   return nloop;
    4759              : }
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.