+/* Add SEQ to the end of LOOP's preheader block. */
+
+static void
+add_preheader_seq (class loop *loop, gimple_seq seq)
+{
+ if (seq)
+ {
+ edge pe = loop_preheader_edge (loop);
+ basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, seq);
+ gcc_assert (!new_bb);
+ }
+}
+
+/* Add SEQ to the beginning of LOOP's header block. */
+
+static void
+add_header_seq (class loop *loop, gimple_seq seq)
+{
+ if (seq)
+ {
+ gimple_stmt_iterator gsi = gsi_after_labels (loop->header);
+ gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
+ }
+}
+
+/* Return true if the target can interleave elements of two vectors.
+ OFFSET is 0 if the first half of the vectors should be interleaved
+ or 1 if the second half should. When returning true, store the
+ associated permutation in INDICES. */
+
+static bool
+interleave_supported_p (vec_perm_indices *indices, tree vectype,
+ unsigned int offset)
+{
+ poly_uint64 nelts = TYPE_VECTOR_SUBPARTS (vectype);
+ poly_uint64 base = exact_div (nelts, 2) * offset;
+ vec_perm_builder sel (nelts, 2, 3);
+ for (unsigned int i = 0; i < 3; ++i)
+ {
+ sel.quick_push (base + i);
+ sel.quick_push (base + i + nelts);
+ }
+ indices->new_vector (sel, 2, nelts);
+ return can_vec_perm_const_p (TYPE_MODE (vectype), *indices);
+}
+
+/* Try to use permutes to define the masks in DEST_RGM using the masks
+ in SRC_RGM, given that the former has twice as many masks as the
+ latter. Return true on success, adding any new statements to SEQ. */
+
+static bool
+vect_maybe_permute_loop_masks (gimple_seq *seq, rgroup_controls *dest_rgm,
+ rgroup_controls *src_rgm)
+{
+ tree src_masktype = src_rgm->type;
+ tree dest_masktype = dest_rgm->type;
+ machine_mode src_mode = TYPE_MODE (src_masktype);
+ insn_code icode1, icode2;
+ if (dest_rgm->max_nscalars_per_iter <= src_rgm->max_nscalars_per_iter
+ && (icode1 = optab_handler (vec_unpacku_hi_optab,
+ src_mode)) != CODE_FOR_nothing
+ && (icode2 = optab_handler (vec_unpacku_lo_optab,
+ src_mode)) != CODE_FOR_nothing)
+ {
+ /* Unpacking the source masks gives at least as many mask bits as
+ we need. We can then VIEW_CONVERT any excess bits away. */
+ machine_mode dest_mode = insn_data[icode1].operand[0].mode;
+ gcc_assert (dest_mode == insn_data[icode2].operand[0].mode);
+ tree unpack_masktype = vect_halve_mask_nunits (src_masktype, dest_mode);
+ for (unsigned int i = 0; i < dest_rgm->controls.length (); ++i)
+ {
+ tree src = src_rgm->controls[i / 2];
+ tree dest = dest_rgm->controls[i];
+ tree_code code = ((i & 1) == (BYTES_BIG_ENDIAN ? 0 : 1)
+ ? VEC_UNPACK_HI_EXPR
+ : VEC_UNPACK_LO_EXPR);
+ gassign *stmt;
+ if (dest_masktype == unpack_masktype)
+ stmt = gimple_build_assign (dest, code, src);
+ else
+ {
+ tree temp = make_ssa_name (unpack_masktype);
+ stmt = gimple_build_assign (temp, code, src);
+ gimple_seq_add_stmt (seq, stmt);
+ stmt = gimple_build_assign (dest, VIEW_CONVERT_EXPR,
+ build1 (VIEW_CONVERT_EXPR,
+ dest_masktype, temp));
+ }
+ gimple_seq_add_stmt (seq, stmt);
+ }
+ return true;
+ }
+ vec_perm_indices indices[2];
+ if (dest_masktype == src_masktype
+ && interleave_supported_p (&indices[0], src_masktype, 0)
+ && interleave_supported_p (&indices[1], src_masktype, 1))
+ {
+ /* The destination requires twice as many mask bits as the source, so
+ we can use interleaving permutes to double up the number of bits. */
+ tree masks[2];
+ for (unsigned int i = 0; i < 2; ++i)
+ masks[i] = vect_gen_perm_mask_checked (src_masktype, indices[i]);
+ for (unsigned int i = 0; i < dest_rgm->controls.length (); ++i)
+ {
+ tree src = src_rgm->controls[i / 2];
+ tree dest = dest_rgm->controls[i];
+ gimple *stmt = gimple_build_assign (dest, VEC_PERM_EXPR,
+ src, src, masks[i & 1]);
+ gimple_seq_add_stmt (seq, stmt);
+ }
+ return true;
+ }
+ return false;
+}
+
+/* Helper for vect_set_loop_condition_partial_vectors. Generate definitions
+ for all the rgroup controls in RGC and return a control that is nonzero
+ when the loop needs to iterate. Add any new preheader statements to
+ PREHEADER_SEQ. Use LOOP_COND_GSI to insert code before the exit gcond.
+
+ RGC belongs to loop LOOP. The loop originally iterated NITERS
+ times and has been vectorized according to LOOP_VINFO.
+
+ If NITERS_SKIP is nonnull, the first iteration of the vectorized loop
+ starts with NITERS_SKIP dummy iterations of the scalar loop before
+ the real work starts. The mask elements for these dummy iterations
+ must be 0, to ensure that the extra iterations do not have an effect.
+
+ It is known that:
+
+ NITERS * RGC->max_nscalars_per_iter * RGC->factor
+
+ does not overflow. However, MIGHT_WRAP_P says whether an induction
+ variable that starts at 0 and has step:
+
+ VF * RGC->max_nscalars_per_iter * RGC->factor
+
+ might overflow before hitting a value above:
+
+ (NITERS + NITERS_SKIP) * RGC->max_nscalars_per_iter * RGC->factor
+
+ This means that we cannot guarantee that such an induction variable
+ would ever hit a value that produces a set of all-false masks or zero
+ lengths for RGC.
+
+ Note: the cost of the code generated by this function is modeled
+ by vect_estimate_min_profitable_iters, so changes here may need
+ corresponding changes there. */
+
+static tree
+vect_set_loop_controls_directly (class loop *loop, loop_vec_info loop_vinfo,
+ gimple_seq *preheader_seq,
+ gimple_stmt_iterator loop_cond_gsi,
+ rgroup_controls *rgc, tree niters,
+ tree niters_skip, bool might_wrap_p)
+{
+ tree compare_type = LOOP_VINFO_RGROUP_COMPARE_TYPE (loop_vinfo);
+ tree iv_type = LOOP_VINFO_RGROUP_IV_TYPE (loop_vinfo);
+ bool use_masks_p = LOOP_VINFO_FULLY_MASKED_P (loop_vinfo);
+
+ tree ctrl_type = rgc->type;
+ unsigned int nitems_per_iter = rgc->max_nscalars_per_iter * rgc->factor;
+ poly_uint64 nitems_per_ctrl = TYPE_VECTOR_SUBPARTS (ctrl_type) * rgc->factor;
+ poly_uint64 vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
+ tree length_limit = NULL_TREE;
+ /* For length, we need length_limit to ensure length in range. */
+ if (!use_masks_p)
+ length_limit = build_int_cst (compare_type, nitems_per_ctrl);
+
+ /* Calculate the maximum number of item values that the rgroup
+ handles in total, the number that it handles for each iteration
+ of the vector loop, and the number that it should skip during the
+ first iteration of the vector loop. */
+ tree nitems_total = niters;
+ tree nitems_step = build_int_cst (iv_type, vf);
+ tree nitems_skip = niters_skip;
+ if (nitems_per_iter != 1)
+ {
+ /* We checked before setting LOOP_VINFO_USING_PARTIAL_VECTORS_P that
+ these multiplications don't overflow. */
+ tree compare_factor = build_int_cst (compare_type, nitems_per_iter);
+ tree iv_factor = build_int_cst (iv_type, nitems_per_iter);
+ nitems_total = gimple_build (preheader_seq, MULT_EXPR, compare_type,
+ nitems_total, compare_factor);
+ nitems_step = gimple_build (preheader_seq, MULT_EXPR, iv_type,
+ nitems_step, iv_factor);
+ if (nitems_skip)
+ nitems_skip = gimple_build (preheader_seq, MULT_EXPR, compare_type,
+ nitems_skip, compare_factor);
+ }
+
+ /* Create an induction variable that counts the number of items
+ processed. */
+ tree index_before_incr, index_after_incr;
+ gimple_stmt_iterator incr_gsi;
+ bool insert_after;
+ standard_iv_increment_position (loop, &incr_gsi, &insert_after);
+ create_iv (build_int_cst (iv_type, 0), nitems_step, NULL_TREE, loop,
+ &incr_gsi, insert_after, &index_before_incr, &index_after_incr);
+
+ tree zero_index = build_int_cst (compare_type, 0);
+ tree test_index, test_limit, first_limit;
+ gimple_stmt_iterator *test_gsi;
+ if (might_wrap_p)
+ {
+ /* In principle the loop should stop iterating once the incremented
+ IV reaches a value greater than or equal to:
+
+ NITEMS_TOTAL +[infinite-prec] NITEMS_SKIP
+
+ However, there's no guarantee that this addition doesn't overflow
+ the comparison type, or that the IV hits a value above it before
+ wrapping around. We therefore adjust the limit down by one
+ IV step:
+
+ (NITEMS_TOTAL +[infinite-prec] NITEMS_SKIP)
+ -[infinite-prec] NITEMS_STEP
+
+ and compare the IV against this limit _before_ incrementing it.
+ Since the comparison type is unsigned, we actually want the
+ subtraction to saturate at zero:
+
+ (NITEMS_TOTAL +[infinite-prec] NITEMS_SKIP)
+ -[sat] NITEMS_STEP
+
+ And since NITEMS_SKIP < NITEMS_STEP, we can reassociate this as:
+
+ NITEMS_TOTAL -[sat] (NITEMS_STEP - NITEMS_SKIP)
+
+ where the rightmost subtraction can be done directly in
+ COMPARE_TYPE. */
+ test_index = index_before_incr;
+ tree adjust = gimple_convert (preheader_seq, compare_type,
+ nitems_step);
+ if (nitems_skip)
+ adjust = gimple_build (preheader_seq, MINUS_EXPR, compare_type,
+ adjust, nitems_skip);
+ test_limit = gimple_build (preheader_seq, MAX_EXPR, compare_type,
+ nitems_total, adjust);
+ test_limit = gimple_build (preheader_seq, MINUS_EXPR, compare_type,
+ test_limit, adjust);
+ test_gsi = &incr_gsi;
+
+ /* Get a safe limit for the first iteration. */
+ if (nitems_skip)
+ {
+ /* The first vector iteration can handle at most NITEMS_STEP
+ items. NITEMS_STEP <= CONST_LIMIT, and adding
+ NITEMS_SKIP to that cannot overflow. */
+ tree const_limit = build_int_cst (compare_type,
+ LOOP_VINFO_VECT_FACTOR (loop_vinfo)
+ * nitems_per_iter);
+ first_limit = gimple_build (preheader_seq, MIN_EXPR, compare_type,
+ nitems_total, const_limit);
+ first_limit = gimple_build (preheader_seq, PLUS_EXPR, compare_type,
+ first_limit, nitems_skip);
+ }
+ else
+ /* For the first iteration it doesn't matter whether the IV hits
+ a value above NITEMS_TOTAL. That only matters for the latch
+ condition. */
+ first_limit = nitems_total;
+ }
+ else
+ {
+ /* Test the incremented IV, which will always hit a value above
+ the bound before wrapping. */
+ test_index = index_after_incr;
+ test_limit = nitems_total;
+ if (nitems_skip)
+ test_limit = gimple_build (preheader_seq, PLUS_EXPR, compare_type,
+ test_limit, nitems_skip);
+ test_gsi = &loop_cond_gsi;
+
+ first_limit = test_limit;
+ }
+
+ /* Convert the IV value to the comparison type (either a no-op or
+ a demotion). */
+ gimple_seq test_seq = NULL;
+ test_index = gimple_convert (&test_seq, compare_type, test_index);
+ gsi_insert_seq_before (test_gsi, test_seq, GSI_SAME_STMT);
+
+ /* Provide a definition of each control in the group. */
+ tree next_ctrl = NULL_TREE;
+ tree ctrl;
+ unsigned int i;
+ FOR_EACH_VEC_ELT_REVERSE (rgc->controls, i, ctrl)
+ {
+ /* Previous controls will cover BIAS items. This control covers the
+ next batch. */
+ poly_uint64 bias = nitems_per_ctrl * i;
+ tree bias_tree = build_int_cst (compare_type, bias);
+
+ /* See whether the first iteration of the vector loop is known
+ to have a full control. */
+ poly_uint64 const_limit;
+ bool first_iteration_full
+ = (poly_int_tree_p (first_limit, &const_limit)
+ && known_ge (const_limit, (i + 1) * nitems_per_ctrl));
+
+ /* Rather than have a new IV that starts at BIAS and goes up to
+ TEST_LIMIT, prefer to use the same 0-based IV for each control
+ and adjust the bound down by BIAS. */
+ tree this_test_limit = test_limit;
+ if (i != 0)
+ {
+ this_test_limit = gimple_build (preheader_seq, MAX_EXPR,
+ compare_type, this_test_limit,
+ bias_tree);
+ this_test_limit = gimple_build (preheader_seq, MINUS_EXPR,
+ compare_type, this_test_limit,
+ bias_tree);
+ }
+
+ /* Create the initial control. First include all items that
+ are within the loop limit. */
+ tree init_ctrl = NULL_TREE;
+ if (!first_iteration_full)
+ {
+ tree start, end;
+ if (first_limit == test_limit)
+ {
+ /* Use a natural test between zero (the initial IV value)
+ and the loop limit. The "else" block would be valid too,
+ but this choice can avoid the need to load BIAS_TREE into
+ a register. */
+ start = zero_index;
+ end = this_test_limit;
+ }
+ else
+ {
+ /* FIRST_LIMIT is the maximum number of items handled by the
+ first iteration of the vector loop. Test the portion
+ associated with this control. */
+ start = bias_tree;
+ end = first_limit;
+ }
+
+ if (use_masks_p)
+ {
+ init_ctrl = make_temp_ssa_name (ctrl_type, NULL, "max_mask");
+ gimple *tmp_stmt = vect_gen_while (init_ctrl, start, end);
+ gimple_seq_add_stmt (preheader_seq, tmp_stmt);
+ }
+ else
+ {
+ init_ctrl = make_temp_ssa_name (compare_type, NULL, "max_len");
+ gimple_seq seq = vect_gen_len (init_ctrl, start,
+ end, length_limit);
+ gimple_seq_add_seq (preheader_seq, seq);
+ }
+ }
+
+ /* Now AND out the bits that are within the number of skipped
+ items. */
+ poly_uint64 const_skip;
+ if (nitems_skip
+ && !(poly_int_tree_p (nitems_skip, &const_skip)
+ && known_le (const_skip, bias)))
+ {
+ gcc_assert (use_masks_p);
+ tree unskipped_mask = vect_gen_while_not (preheader_seq, ctrl_type,
+ bias_tree, nitems_skip);
+ if (init_ctrl)
+ init_ctrl = gimple_build (preheader_seq, BIT_AND_EXPR, ctrl_type,
+ init_ctrl, unskipped_mask);
+ else
+ init_ctrl = unskipped_mask;
+ }
+
+ if (!init_ctrl)
+ {
+ /* First iteration is full. */
+ if (use_masks_p)
+ init_ctrl = build_minus_one_cst (ctrl_type);
+ else
+ init_ctrl = length_limit;
+ }
+
+ /* Get the control value for the next iteration of the loop. */
+ if (use_masks_p)
+ {
+ next_ctrl = make_temp_ssa_name (ctrl_type, NULL, "next_mask");
+ gcall *call = vect_gen_while (next_ctrl, test_index, this_test_limit);
+ gsi_insert_before (test_gsi, call, GSI_SAME_STMT);
+ }
+ else
+ {
+ next_ctrl = make_temp_ssa_name (compare_type, NULL, "next_len");
+ gimple_seq seq = vect_gen_len (next_ctrl, test_index, this_test_limit,
+ length_limit);
+ gsi_insert_seq_before (test_gsi, seq, GSI_SAME_STMT);
+ }
+
+ vect_set_loop_control (loop, ctrl, init_ctrl, next_ctrl);
+ }
+ return next_ctrl;
+}
+
+/* Set up the iteration condition and rgroup controls for LOOP, given
+ that LOOP_VINFO_USING_PARTIAL_VECTORS_P is true for the vectorized
+ loop. LOOP_VINFO describes the vectorization of LOOP. NITERS is
+ the number of iterations of the original scalar loop that should be
+ handled by the vector loop. NITERS_MAYBE_ZERO and FINAL_IV are as
+ for vect_set_loop_condition.
+
+ Insert the branch-back condition before LOOP_COND_GSI and return the
+ final gcond. */
+
+static gcond *
+vect_set_loop_condition_partial_vectors (class loop *loop,
+ loop_vec_info loop_vinfo, tree niters,
+ tree final_iv, bool niters_maybe_zero,
+ gimple_stmt_iterator loop_cond_gsi)
+{
+ gimple_seq preheader_seq = NULL;
+ gimple_seq header_seq = NULL;
+
+ bool use_masks_p = LOOP_VINFO_FULLY_MASKED_P (loop_vinfo);
+ tree compare_type = LOOP_VINFO_RGROUP_COMPARE_TYPE (loop_vinfo);
+ unsigned int compare_precision = TYPE_PRECISION (compare_type);
+ tree orig_niters = niters;
+
+ /* Type of the initial value of NITERS. */
+ tree ni_actual_type = TREE_TYPE (niters);
+ unsigned int ni_actual_precision = TYPE_PRECISION (ni_actual_type);
+ tree niters_skip = LOOP_VINFO_MASK_SKIP_NITERS (loop_vinfo);
+
+ /* Convert NITERS to the same size as the compare. */
+ if (compare_precision > ni_actual_precision
+ && niters_maybe_zero)
+ {
+ /* We know that there is always at least one iteration, so if the
+ count is zero then it must have wrapped. Cope with this by
+ subtracting 1 before the conversion and adding 1 to the result. */
+ gcc_assert (TYPE_UNSIGNED (ni_actual_type));
+ niters = gimple_build (&preheader_seq, PLUS_EXPR, ni_actual_type,
+ niters, build_minus_one_cst (ni_actual_type));
+ niters = gimple_convert (&preheader_seq, compare_type, niters);
+ niters = gimple_build (&preheader_seq, PLUS_EXPR, compare_type,
+ niters, build_one_cst (compare_type));
+ }
+ else
+ niters = gimple_convert (&preheader_seq, compare_type, niters);
+
+ /* Iterate over all the rgroups and fill in their controls. We could use
+ the first control from any rgroup for the loop condition; here we
+ arbitrarily pick the last. */
+ tree test_ctrl = NULL_TREE;
+ rgroup_controls *rgc;
+ unsigned int i;
+ auto_vec<rgroup_controls> *controls = use_masks_p
+ ? &LOOP_VINFO_MASKS (loop_vinfo)
+ : &LOOP_VINFO_LENS (loop_vinfo);
+ FOR_EACH_VEC_ELT (*controls, i, rgc)
+ if (!rgc->controls.is_empty ())
+ {
+ /* First try using permutes. This adds a single vector
+ instruction to the loop for each mask, but needs no extra
+ loop invariants or IVs. */
+ unsigned int nmasks = i + 1;
+ if (use_masks_p && (nmasks & 1) == 0)
+ {
+ rgroup_controls *half_rgc = &(*controls)[nmasks / 2 - 1];
+ if (!half_rgc->controls.is_empty ()
+ && vect_maybe_permute_loop_masks (&header_seq, rgc, half_rgc))
+ continue;
+ }
+
+ /* See whether zero-based IV would ever generate all-false masks
+ or zero length before wrapping around. */
+ bool might_wrap_p = vect_rgroup_iv_might_wrap_p (loop_vinfo, rgc);
+
+ /* Set up all controls for this group. */
+ test_ctrl = vect_set_loop_controls_directly (loop, loop_vinfo,
+ &preheader_seq,
+ loop_cond_gsi, rgc,
+ niters, niters_skip,
+ might_wrap_p);
+ }
+
+ /* Emit all accumulated statements. */
+ add_preheader_seq (loop, preheader_seq);
+ add_header_seq (loop, header_seq);
+
+ /* Get a boolean result that tells us whether to iterate. */
+ edge exit_edge = single_exit (loop);
+ tree_code code = (exit_edge->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
+ tree zero_ctrl = build_zero_cst (TREE_TYPE (test_ctrl));
+ gcond *cond_stmt = gimple_build_cond (code, test_ctrl, zero_ctrl,
+ NULL_TREE, NULL_TREE);
+ gsi_insert_before (&loop_cond_gsi, cond_stmt, GSI_SAME_STMT);
+
+ /* The loop iterates (NITERS - 1) / VF + 1 times.
+ Subtract one from this to get the latch count. */
+ tree step = build_int_cst (compare_type,
+ LOOP_VINFO_VECT_FACTOR (loop_vinfo));
+ tree niters_minus_one = fold_build2 (PLUS_EXPR, compare_type, niters,
+ build_minus_one_cst (compare_type));
+ loop->nb_iterations = fold_build2 (TRUNC_DIV_EXPR, compare_type,
+ niters_minus_one, step);
+
+ if (final_iv)
+ {
+ gassign *assign = gimple_build_assign (final_iv, orig_niters);
+ gsi_insert_on_edge_immediate (single_exit (loop), assign);
+ }
+
+ return cond_stmt;
+}
+
+/* Like vect_set_loop_condition, but handle the case in which the vector
+ loop handles exactly VF scalars per iteration. */
+
+static gcond *
+vect_set_loop_condition_normal (class loop *loop, tree niters, tree step,
+ tree final_iv, bool niters_maybe_zero,
+ gimple_stmt_iterator loop_cond_gsi)