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