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