Emit SIMD moves as mov
[official-gcc.git] / gcc / tree-vect-loop.c
blobd601296ab3e4280773184ce25cd249bf7c424957
1 /* Loop Vectorization
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com> and
4 Ira Rosen <irar@il.ibm.com>
6 This file is part of GCC.
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.
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.
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/>. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "backend.h"
26 #include "target.h"
27 #include "rtl.h"
28 #include "tree.h"
29 #include "gimple.h"
30 #include "cfghooks.h"
31 #include "tree-pass.h"
32 #include "ssa.h"
33 #include "optabs-tree.h"
34 #include "diagnostic-core.h"
35 #include "fold-const.h"
36 #include "stor-layout.h"
37 #include "cfganal.h"
38 #include "gimplify.h"
39 #include "gimple-iterator.h"
40 #include "gimplify-me.h"
41 #include "tree-ssa-loop-ivopts.h"
42 #include "tree-ssa-loop-manip.h"
43 #include "tree-ssa-loop-niter.h"
44 #include "tree-ssa-loop.h"
45 #include "cfgloop.h"
46 #include "params.h"
47 #include "tree-scalar-evolution.h"
48 #include "tree-vectorizer.h"
49 #include "gimple-fold.h"
50 #include "cgraph.h"
51 #include "tree-cfg.h"
52 #include "tree-if-conv.h"
54 /* Loop Vectorization Pass.
56 This pass tries to vectorize loops.
58 For example, the vectorizer transforms the following simple loop:
60 short a[N]; short b[N]; short c[N]; int i;
62 for (i=0; i<N; i++){
63 a[i] = b[i] + c[i];
66 as if it was manually vectorized by rewriting the source code into:
68 typedef int __attribute__((mode(V8HI))) v8hi;
69 short a[N]; short b[N]; short c[N]; int i;
70 v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
71 v8hi va, vb, vc;
73 for (i=0; i<N/8; i++){
74 vb = pb[i];
75 vc = pc[i];
76 va = vb + vc;
77 pa[i] = va;
80 The main entry to this pass is vectorize_loops(), in which
81 the vectorizer applies a set of analyses on a given set of loops,
82 followed by the actual vectorization transformation for the loops that
83 had successfully passed the analysis phase.
84 Throughout this pass we make a distinction between two types of
85 data: scalars (which are represented by SSA_NAMES), and memory references
86 ("data-refs"). These two types of data require different handling both
87 during analysis and transformation. The types of data-refs that the
88 vectorizer currently supports are ARRAY_REFS which base is an array DECL
89 (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
90 accesses are required to have a simple (consecutive) access pattern.
92 Analysis phase:
93 ===============
94 The driver for the analysis phase is vect_analyze_loop().
95 It applies a set of analyses, some of which rely on the scalar evolution
96 analyzer (scev) developed by Sebastian Pop.
98 During the analysis phase the vectorizer records some information
99 per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
100 loop, as well as general information about the loop as a whole, which is
101 recorded in a "loop_vec_info" struct attached to each loop.
103 Transformation phase:
104 =====================
105 The loop transformation phase scans all the stmts in the loop, and
106 creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
107 the loop that needs to be vectorized. It inserts the vector code sequence
108 just before the scalar stmt S, and records a pointer to the vector code
109 in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
110 attached to S). This pointer will be used for the vectorization of following
111 stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
112 otherwise, we rely on dead code elimination for removing it.
114 For example, say stmt S1 was vectorized into stmt VS1:
116 VS1: vb = px[i];
117 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
118 S2: a = b;
120 To vectorize stmt S2, the vectorizer first finds the stmt that defines
121 the operand 'b' (S1), and gets the relevant vector def 'vb' from the
122 vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
123 resulting sequence would be:
125 VS1: vb = px[i];
126 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
127 VS2: va = vb;
128 S2: a = b; STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
130 Operands that are not SSA_NAMEs, are data-refs that appear in
131 load/store operations (like 'x[i]' in S1), and are handled differently.
133 Target modeling:
134 =================
135 Currently the only target specific information that is used is the
136 size of the vector (in bytes) - "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD".
137 Targets that can support different sizes of vectors, for now will need
138 to specify one value for "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD". More
139 flexibility will be added in the future.
141 Since we only vectorize operations which vector form can be
142 expressed using existing tree codes, to verify that an operation is
143 supported, the vectorizer checks the relevant optab at the relevant
144 machine_mode (e.g, optab_handler (add_optab, V8HImode)). If
145 the value found is CODE_FOR_nothing, then there's no target support, and
146 we can't vectorize the stmt.
148 For additional information on this project see:
149 http://gcc.gnu.org/projects/tree-ssa/vectorization.html
152 static void vect_estimate_min_profitable_iters (loop_vec_info, int *, int *);
154 /* Function vect_determine_vectorization_factor
156 Determine the vectorization factor (VF). VF is the number of data elements
157 that are operated upon in parallel in a single iteration of the vectorized
158 loop. For example, when vectorizing a loop that operates on 4byte elements,
159 on a target with vector size (VS) 16byte, the VF is set to 4, since 4
160 elements can fit in a single vector register.
162 We currently support vectorization of loops in which all types operated upon
163 are of the same size. Therefore this function currently sets VF according to
164 the size of the types operated upon, and fails if there are multiple sizes
165 in the loop.
167 VF is also the factor by which the loop iterations are strip-mined, e.g.:
168 original loop:
169 for (i=0; i<N; i++){
170 a[i] = b[i] + c[i];
173 vectorized loop:
174 for (i=0; i<N; i+=VF){
175 a[i:VF] = b[i:VF] + c[i:VF];
179 static bool
180 vect_determine_vectorization_factor (loop_vec_info loop_vinfo)
182 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
183 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
184 unsigned nbbs = loop->num_nodes;
185 unsigned int vectorization_factor = 0;
186 tree scalar_type = NULL_TREE;
187 gphi *phi;
188 tree vectype;
189 unsigned int nunits;
190 stmt_vec_info stmt_info;
191 unsigned i;
192 HOST_WIDE_INT dummy;
193 gimple *stmt, *pattern_stmt = NULL;
194 gimple_seq pattern_def_seq = NULL;
195 gimple_stmt_iterator pattern_def_si = gsi_none ();
196 bool analyze_pattern_stmt = false;
197 bool bool_result;
198 auto_vec<stmt_vec_info> mask_producers;
200 if (dump_enabled_p ())
201 dump_printf_loc (MSG_NOTE, vect_location,
202 "=== vect_determine_vectorization_factor ===\n");
204 for (i = 0; i < nbbs; i++)
206 basic_block bb = bbs[i];
208 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
209 gsi_next (&si))
211 phi = si.phi ();
212 stmt_info = vinfo_for_stmt (phi);
213 if (dump_enabled_p ())
215 dump_printf_loc (MSG_NOTE, vect_location, "==> examining phi: ");
216 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
219 gcc_assert (stmt_info);
221 if (STMT_VINFO_RELEVANT_P (stmt_info)
222 || STMT_VINFO_LIVE_P (stmt_info))
224 gcc_assert (!STMT_VINFO_VECTYPE (stmt_info));
225 scalar_type = TREE_TYPE (PHI_RESULT (phi));
227 if (dump_enabled_p ())
229 dump_printf_loc (MSG_NOTE, vect_location,
230 "get vectype for scalar type: ");
231 dump_generic_expr (MSG_NOTE, TDF_SLIM, scalar_type);
232 dump_printf (MSG_NOTE, "\n");
235 vectype = get_vectype_for_scalar_type (scalar_type);
236 if (!vectype)
238 if (dump_enabled_p ())
240 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
241 "not vectorized: unsupported "
242 "data-type ");
243 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
244 scalar_type);
245 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
247 return false;
249 STMT_VINFO_VECTYPE (stmt_info) = vectype;
251 if (dump_enabled_p ())
253 dump_printf_loc (MSG_NOTE, vect_location, "vectype: ");
254 dump_generic_expr (MSG_NOTE, TDF_SLIM, vectype);
255 dump_printf (MSG_NOTE, "\n");
258 nunits = TYPE_VECTOR_SUBPARTS (vectype);
259 if (dump_enabled_p ())
260 dump_printf_loc (MSG_NOTE, vect_location, "nunits = %d\n",
261 nunits);
263 if (!vectorization_factor
264 || (nunits > vectorization_factor))
265 vectorization_factor = nunits;
269 for (gimple_stmt_iterator si = gsi_start_bb (bb);
270 !gsi_end_p (si) || analyze_pattern_stmt;)
272 tree vf_vectype;
274 if (analyze_pattern_stmt)
275 stmt = pattern_stmt;
276 else
277 stmt = gsi_stmt (si);
279 stmt_info = vinfo_for_stmt (stmt);
281 if (dump_enabled_p ())
283 dump_printf_loc (MSG_NOTE, vect_location,
284 "==> examining statement: ");
285 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
288 gcc_assert (stmt_info);
290 /* Skip stmts which do not need to be vectorized. */
291 if ((!STMT_VINFO_RELEVANT_P (stmt_info)
292 && !STMT_VINFO_LIVE_P (stmt_info))
293 || gimple_clobber_p (stmt))
295 if (STMT_VINFO_IN_PATTERN_P (stmt_info)
296 && (pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info))
297 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt))
298 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt))))
300 stmt = pattern_stmt;
301 stmt_info = vinfo_for_stmt (pattern_stmt);
302 if (dump_enabled_p ())
304 dump_printf_loc (MSG_NOTE, vect_location,
305 "==> examining pattern statement: ");
306 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
309 else
311 if (dump_enabled_p ())
312 dump_printf_loc (MSG_NOTE, vect_location, "skip.\n");
313 gsi_next (&si);
314 continue;
317 else if (STMT_VINFO_IN_PATTERN_P (stmt_info)
318 && (pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info))
319 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt))
320 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt))))
321 analyze_pattern_stmt = true;
323 /* If a pattern statement has def stmts, analyze them too. */
324 if (is_pattern_stmt_p (stmt_info))
326 if (pattern_def_seq == NULL)
328 pattern_def_seq = STMT_VINFO_PATTERN_DEF_SEQ (stmt_info);
329 pattern_def_si = gsi_start (pattern_def_seq);
331 else if (!gsi_end_p (pattern_def_si))
332 gsi_next (&pattern_def_si);
333 if (pattern_def_seq != NULL)
335 gimple *pattern_def_stmt = NULL;
336 stmt_vec_info pattern_def_stmt_info = NULL;
338 while (!gsi_end_p (pattern_def_si))
340 pattern_def_stmt = gsi_stmt (pattern_def_si);
341 pattern_def_stmt_info
342 = vinfo_for_stmt (pattern_def_stmt);
343 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info)
344 || STMT_VINFO_LIVE_P (pattern_def_stmt_info))
345 break;
346 gsi_next (&pattern_def_si);
349 if (!gsi_end_p (pattern_def_si))
351 if (dump_enabled_p ())
353 dump_printf_loc (MSG_NOTE, vect_location,
354 "==> examining pattern def stmt: ");
355 dump_gimple_stmt (MSG_NOTE, TDF_SLIM,
356 pattern_def_stmt, 0);
359 stmt = pattern_def_stmt;
360 stmt_info = pattern_def_stmt_info;
362 else
364 pattern_def_si = gsi_none ();
365 analyze_pattern_stmt = false;
368 else
369 analyze_pattern_stmt = false;
372 if (gimple_get_lhs (stmt) == NULL_TREE
373 /* MASK_STORE has no lhs, but is ok. */
374 && (!is_gimple_call (stmt)
375 || !gimple_call_internal_p (stmt)
376 || gimple_call_internal_fn (stmt) != IFN_MASK_STORE))
378 if (is_gimple_call (stmt))
380 /* Ignore calls with no lhs. These must be calls to
381 #pragma omp simd functions, and what vectorization factor
382 it really needs can't be determined until
383 vectorizable_simd_clone_call. */
384 if (!analyze_pattern_stmt && gsi_end_p (pattern_def_si))
386 pattern_def_seq = NULL;
387 gsi_next (&si);
389 continue;
391 if (dump_enabled_p ())
393 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
394 "not vectorized: irregular stmt.");
395 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt,
398 return false;
401 if (VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt))))
403 if (dump_enabled_p ())
405 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
406 "not vectorized: vector stmt in loop:");
407 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
409 return false;
412 bool_result = false;
414 if (STMT_VINFO_VECTYPE (stmt_info))
416 /* The only case when a vectype had been already set is for stmts
417 that contain a dataref, or for "pattern-stmts" (stmts
418 generated by the vectorizer to represent/replace a certain
419 idiom). */
420 gcc_assert (STMT_VINFO_DATA_REF (stmt_info)
421 || is_pattern_stmt_p (stmt_info)
422 || !gsi_end_p (pattern_def_si));
423 vectype = STMT_VINFO_VECTYPE (stmt_info);
425 else
427 gcc_assert (!STMT_VINFO_DATA_REF (stmt_info));
428 if (gimple_call_internal_p (stmt, IFN_MASK_STORE))
429 scalar_type = TREE_TYPE (gimple_call_arg (stmt, 3));
430 else
431 scalar_type = TREE_TYPE (gimple_get_lhs (stmt));
433 /* Bool ops don't participate in vectorization factor
434 computation. For comparison use compared types to
435 compute a factor. */
436 if (VECT_SCALAR_BOOLEAN_TYPE_P (scalar_type)
437 && is_gimple_assign (stmt)
438 && gimple_assign_rhs_code (stmt) != COND_EXPR)
440 if (STMT_VINFO_RELEVANT_P (stmt_info)
441 || STMT_VINFO_LIVE_P (stmt_info))
442 mask_producers.safe_push (stmt_info);
443 bool_result = true;
445 if (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
446 == tcc_comparison
447 && !VECT_SCALAR_BOOLEAN_TYPE_P
448 (TREE_TYPE (gimple_assign_rhs1 (stmt))))
449 scalar_type = TREE_TYPE (gimple_assign_rhs1 (stmt));
450 else
452 if (!analyze_pattern_stmt && gsi_end_p (pattern_def_si))
454 pattern_def_seq = NULL;
455 gsi_next (&si);
457 continue;
461 if (dump_enabled_p ())
463 dump_printf_loc (MSG_NOTE, vect_location,
464 "get vectype for scalar type: ");
465 dump_generic_expr (MSG_NOTE, TDF_SLIM, scalar_type);
466 dump_printf (MSG_NOTE, "\n");
468 vectype = get_vectype_for_scalar_type (scalar_type);
469 if (!vectype)
471 if (dump_enabled_p ())
473 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
474 "not vectorized: unsupported "
475 "data-type ");
476 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
477 scalar_type);
478 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
480 return false;
483 if (!bool_result)
484 STMT_VINFO_VECTYPE (stmt_info) = vectype;
486 if (dump_enabled_p ())
488 dump_printf_loc (MSG_NOTE, vect_location, "vectype: ");
489 dump_generic_expr (MSG_NOTE, TDF_SLIM, vectype);
490 dump_printf (MSG_NOTE, "\n");
494 /* Don't try to compute VF out scalar types if we stmt
495 produces boolean vector. Use result vectype instead. */
496 if (VECTOR_BOOLEAN_TYPE_P (vectype))
497 vf_vectype = vectype;
498 else
500 /* The vectorization factor is according to the smallest
501 scalar type (or the largest vector size, but we only
502 support one vector size per loop). */
503 if (!bool_result)
504 scalar_type = vect_get_smallest_scalar_type (stmt, &dummy,
505 &dummy);
506 if (dump_enabled_p ())
508 dump_printf_loc (MSG_NOTE, vect_location,
509 "get vectype for scalar type: ");
510 dump_generic_expr (MSG_NOTE, TDF_SLIM, scalar_type);
511 dump_printf (MSG_NOTE, "\n");
513 vf_vectype = get_vectype_for_scalar_type (scalar_type);
515 if (!vf_vectype)
517 if (dump_enabled_p ())
519 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
520 "not vectorized: unsupported data-type ");
521 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
522 scalar_type);
523 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
525 return false;
528 if ((GET_MODE_SIZE (TYPE_MODE (vectype))
529 != GET_MODE_SIZE (TYPE_MODE (vf_vectype))))
531 if (dump_enabled_p ())
533 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
534 "not vectorized: different sized vector "
535 "types in statement, ");
536 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
537 vectype);
538 dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
539 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
540 vf_vectype);
541 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
543 return false;
546 if (dump_enabled_p ())
548 dump_printf_loc (MSG_NOTE, vect_location, "vectype: ");
549 dump_generic_expr (MSG_NOTE, TDF_SLIM, vf_vectype);
550 dump_printf (MSG_NOTE, "\n");
553 nunits = TYPE_VECTOR_SUBPARTS (vf_vectype);
554 if (dump_enabled_p ())
555 dump_printf_loc (MSG_NOTE, vect_location, "nunits = %d\n", nunits);
556 if (!vectorization_factor
557 || (nunits > vectorization_factor))
558 vectorization_factor = nunits;
560 if (!analyze_pattern_stmt && gsi_end_p (pattern_def_si))
562 pattern_def_seq = NULL;
563 gsi_next (&si);
568 /* TODO: Analyze cost. Decide if worth while to vectorize. */
569 if (dump_enabled_p ())
570 dump_printf_loc (MSG_NOTE, vect_location, "vectorization factor = %d\n",
571 vectorization_factor);
572 if (vectorization_factor <= 1)
574 if (dump_enabled_p ())
575 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
576 "not vectorized: unsupported data-type\n");
577 return false;
579 LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
581 for (i = 0; i < mask_producers.length (); i++)
583 tree mask_type = NULL;
585 stmt = STMT_VINFO_STMT (mask_producers[i]);
587 if (is_gimple_assign (stmt)
588 && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison
589 && !VECT_SCALAR_BOOLEAN_TYPE_P
590 (TREE_TYPE (gimple_assign_rhs1 (stmt))))
592 scalar_type = TREE_TYPE (gimple_assign_rhs1 (stmt));
593 mask_type = get_mask_type_for_scalar_type (scalar_type);
595 if (!mask_type)
597 if (dump_enabled_p ())
598 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
599 "not vectorized: unsupported mask\n");
600 return false;
603 else
605 tree rhs;
606 ssa_op_iter iter;
607 gimple *def_stmt;
608 enum vect_def_type dt;
610 FOR_EACH_SSA_TREE_OPERAND (rhs, stmt, iter, SSA_OP_USE)
612 if (!vect_is_simple_use (rhs, mask_producers[i]->vinfo,
613 &def_stmt, &dt, &vectype))
615 if (dump_enabled_p ())
617 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
618 "not vectorized: can't compute mask type "
619 "for statement, ");
620 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt,
623 return false;
626 /* No vectype probably means external definition.
627 Allow it in case there is another operand which
628 allows to determine mask type. */
629 if (!vectype)
630 continue;
632 if (!mask_type)
633 mask_type = vectype;
634 else if (TYPE_VECTOR_SUBPARTS (mask_type)
635 != TYPE_VECTOR_SUBPARTS (vectype))
637 if (dump_enabled_p ())
639 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
640 "not vectorized: different sized masks "
641 "types in statement, ");
642 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
643 mask_type);
644 dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
645 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
646 vectype);
647 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
649 return false;
651 else if (VECTOR_BOOLEAN_TYPE_P (mask_type)
652 != VECTOR_BOOLEAN_TYPE_P (vectype))
654 if (dump_enabled_p ())
656 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
657 "not vectorized: mixed mask and "
658 "nonmask vector types in statement, ");
659 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
660 mask_type);
661 dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
662 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
663 vectype);
664 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
666 return false;
670 /* We may compare boolean value loaded as vector of integers.
671 Fix mask_type in such case. */
672 if (mask_type
673 && !VECTOR_BOOLEAN_TYPE_P (mask_type)
674 && gimple_code (stmt) == GIMPLE_ASSIGN
675 && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison)
676 mask_type = build_same_sized_truth_vector_type (mask_type);
679 /* No mask_type should mean loop invariant predicate.
680 This is probably a subject for optimization in
681 if-conversion. */
682 if (!mask_type)
684 if (dump_enabled_p ())
686 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
687 "not vectorized: can't compute mask type "
688 "for statement, ");
689 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt,
692 return false;
695 STMT_VINFO_VECTYPE (mask_producers[i]) = mask_type;
698 return true;
702 /* Function vect_is_simple_iv_evolution.
704 FORNOW: A simple evolution of an induction variables in the loop is
705 considered a polynomial evolution. */
707 static bool
708 vect_is_simple_iv_evolution (unsigned loop_nb, tree access_fn, tree * init,
709 tree * step)
711 tree init_expr;
712 tree step_expr;
713 tree evolution_part = evolution_part_in_loop_num (access_fn, loop_nb);
714 basic_block bb;
716 /* When there is no evolution in this loop, the evolution function
717 is not "simple". */
718 if (evolution_part == NULL_TREE)
719 return false;
721 /* When the evolution is a polynomial of degree >= 2
722 the evolution function is not "simple". */
723 if (tree_is_chrec (evolution_part))
724 return false;
726 step_expr = evolution_part;
727 init_expr = unshare_expr (initial_condition_in_loop_num (access_fn, loop_nb));
729 if (dump_enabled_p ())
731 dump_printf_loc (MSG_NOTE, vect_location, "step: ");
732 dump_generic_expr (MSG_NOTE, TDF_SLIM, step_expr);
733 dump_printf (MSG_NOTE, ", init: ");
734 dump_generic_expr (MSG_NOTE, TDF_SLIM, init_expr);
735 dump_printf (MSG_NOTE, "\n");
738 *init = init_expr;
739 *step = step_expr;
741 if (TREE_CODE (step_expr) != INTEGER_CST
742 && (TREE_CODE (step_expr) != SSA_NAME
743 || ((bb = gimple_bb (SSA_NAME_DEF_STMT (step_expr)))
744 && flow_bb_inside_loop_p (get_loop (cfun, loop_nb), bb))
745 || (!INTEGRAL_TYPE_P (TREE_TYPE (step_expr))
746 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr))
747 || !flag_associative_math)))
748 && (TREE_CODE (step_expr) != REAL_CST
749 || !flag_associative_math))
751 if (dump_enabled_p ())
752 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
753 "step unknown.\n");
754 return false;
757 return true;
760 /* Function vect_analyze_scalar_cycles_1.
762 Examine the cross iteration def-use cycles of scalar variables
763 in LOOP. LOOP_VINFO represents the loop that is now being
764 considered for vectorization (can be LOOP, or an outer-loop
765 enclosing LOOP). */
767 static void
768 vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo, struct loop *loop)
770 basic_block bb = loop->header;
771 tree init, step;
772 auto_vec<gimple *, 64> worklist;
773 gphi_iterator gsi;
774 bool double_reduc;
776 if (dump_enabled_p ())
777 dump_printf_loc (MSG_NOTE, vect_location,
778 "=== vect_analyze_scalar_cycles ===\n");
780 /* First - identify all inductions. Reduction detection assumes that all the
781 inductions have been identified, therefore, this order must not be
782 changed. */
783 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
785 gphi *phi = gsi.phi ();
786 tree access_fn = NULL;
787 tree def = PHI_RESULT (phi);
788 stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
790 if (dump_enabled_p ())
792 dump_printf_loc (MSG_NOTE, vect_location, "Analyze phi: ");
793 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
796 /* Skip virtual phi's. The data dependences that are associated with
797 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
798 if (virtual_operand_p (def))
799 continue;
801 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_unknown_def_type;
803 /* Analyze the evolution function. */
804 access_fn = analyze_scalar_evolution (loop, def);
805 if (access_fn)
807 STRIP_NOPS (access_fn);
808 if (dump_enabled_p ())
810 dump_printf_loc (MSG_NOTE, vect_location,
811 "Access function of PHI: ");
812 dump_generic_expr (MSG_NOTE, TDF_SLIM, access_fn);
813 dump_printf (MSG_NOTE, "\n");
815 STMT_VINFO_LOOP_PHI_EVOLUTION_BASE_UNCHANGED (stmt_vinfo)
816 = initial_condition_in_loop_num (access_fn, loop->num);
817 STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo)
818 = evolution_part_in_loop_num (access_fn, loop->num);
821 if (!access_fn
822 || !vect_is_simple_iv_evolution (loop->num, access_fn, &init, &step)
823 || (LOOP_VINFO_LOOP (loop_vinfo) != loop
824 && TREE_CODE (step) != INTEGER_CST))
826 worklist.safe_push (phi);
827 continue;
830 gcc_assert (STMT_VINFO_LOOP_PHI_EVOLUTION_BASE_UNCHANGED (stmt_vinfo)
831 != NULL_TREE);
832 gcc_assert (STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo) != NULL_TREE);
834 if (dump_enabled_p ())
835 dump_printf_loc (MSG_NOTE, vect_location, "Detected induction.\n");
836 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def;
840 /* Second - identify all reductions and nested cycles. */
841 while (worklist.length () > 0)
843 gimple *phi = worklist.pop ();
844 tree def = PHI_RESULT (phi);
845 stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
846 gimple *reduc_stmt;
848 if (dump_enabled_p ())
850 dump_printf_loc (MSG_NOTE, vect_location, "Analyze phi: ");
851 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
854 gcc_assert (!virtual_operand_p (def)
855 && STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_unknown_def_type);
857 reduc_stmt = vect_force_simple_reduction (loop_vinfo, phi,
858 &double_reduc, false);
859 if (reduc_stmt)
861 if (double_reduc)
863 if (dump_enabled_p ())
864 dump_printf_loc (MSG_NOTE, vect_location,
865 "Detected double reduction.\n");
867 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_double_reduction_def;
868 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
869 vect_double_reduction_def;
871 else
873 if (loop != LOOP_VINFO_LOOP (loop_vinfo))
875 if (dump_enabled_p ())
876 dump_printf_loc (MSG_NOTE, vect_location,
877 "Detected vectorizable nested cycle.\n");
879 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_nested_cycle;
880 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
881 vect_nested_cycle;
883 else
885 if (dump_enabled_p ())
886 dump_printf_loc (MSG_NOTE, vect_location,
887 "Detected reduction.\n");
889 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_reduction_def;
890 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
891 vect_reduction_def;
892 /* Store the reduction cycles for possible vectorization in
893 loop-aware SLP. */
894 LOOP_VINFO_REDUCTIONS (loop_vinfo).safe_push (reduc_stmt);
898 else
899 if (dump_enabled_p ())
900 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
901 "Unknown def-use cycle pattern.\n");
906 /* Function vect_analyze_scalar_cycles.
908 Examine the cross iteration def-use cycles of scalar variables, by
909 analyzing the loop-header PHIs of scalar variables. Classify each
910 cycle as one of the following: invariant, induction, reduction, unknown.
911 We do that for the loop represented by LOOP_VINFO, and also to its
912 inner-loop, if exists.
913 Examples for scalar cycles:
915 Example1: reduction:
917 loop1:
918 for (i=0; i<N; i++)
919 sum += a[i];
921 Example2: induction:
923 loop2:
924 for (i=0; i<N; i++)
925 a[i] = i; */
927 static void
928 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
930 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
932 vect_analyze_scalar_cycles_1 (loop_vinfo, loop);
934 /* When vectorizing an outer-loop, the inner-loop is executed sequentially.
935 Reductions in such inner-loop therefore have different properties than
936 the reductions in the nest that gets vectorized:
937 1. When vectorized, they are executed in the same order as in the original
938 scalar loop, so we can't change the order of computation when
939 vectorizing them.
940 2. FIXME: Inner-loop reductions can be used in the inner-loop, so the
941 current checks are too strict. */
943 if (loop->inner)
944 vect_analyze_scalar_cycles_1 (loop_vinfo, loop->inner);
947 /* Transfer group and reduction information from STMT to its pattern stmt. */
949 static void
950 vect_fixup_reduc_chain (gimple *stmt)
952 gimple *firstp = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt));
953 gimple *stmtp;
954 gcc_assert (!GROUP_FIRST_ELEMENT (vinfo_for_stmt (firstp))
955 && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)));
956 GROUP_SIZE (vinfo_for_stmt (firstp)) = GROUP_SIZE (vinfo_for_stmt (stmt));
959 stmtp = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt));
960 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmtp)) = firstp;
961 stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt));
962 if (stmt)
963 GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmtp))
964 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt));
966 while (stmt);
967 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmtp)) = vect_reduction_def;
970 /* Fixup scalar cycles that now have their stmts detected as patterns. */
972 static void
973 vect_fixup_scalar_cycles_with_patterns (loop_vec_info loop_vinfo)
975 gimple *first;
976 unsigned i;
978 FOR_EACH_VEC_ELT (LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo), i, first)
979 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (first)))
981 gimple *next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (first));
982 while (next)
984 if (! STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (next)))
985 break;
986 next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next));
988 /* If not all stmt in the chain are patterns try to handle
989 the chain without patterns. */
990 if (! next)
992 vect_fixup_reduc_chain (first);
993 LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo)[i]
994 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first));
999 /* Function vect_get_loop_niters.
1001 Determine how many iterations the loop is executed and place it
1002 in NUMBER_OF_ITERATIONS. Place the number of latch iterations
1003 in NUMBER_OF_ITERATIONSM1. Place the condition under which the
1004 niter information holds in ASSUMPTIONS.
1006 Return the loop exit condition. */
1009 static gcond *
1010 vect_get_loop_niters (struct loop *loop, tree *assumptions,
1011 tree *number_of_iterations, tree *number_of_iterationsm1)
1013 edge exit = single_exit (loop);
1014 struct tree_niter_desc niter_desc;
1015 tree niter_assumptions, niter, may_be_zero;
1016 gcond *cond = get_loop_exit_condition (loop);
1018 *assumptions = boolean_true_node;
1019 *number_of_iterationsm1 = chrec_dont_know;
1020 *number_of_iterations = chrec_dont_know;
1021 if (dump_enabled_p ())
1022 dump_printf_loc (MSG_NOTE, vect_location,
1023 "=== get_loop_niters ===\n");
1025 if (!exit)
1026 return cond;
1028 niter = chrec_dont_know;
1029 may_be_zero = NULL_TREE;
1030 niter_assumptions = boolean_true_node;
1031 if (!number_of_iterations_exit_assumptions (loop, exit, &niter_desc, NULL)
1032 || chrec_contains_undetermined (niter_desc.niter))
1033 return cond;
1035 niter_assumptions = niter_desc.assumptions;
1036 may_be_zero = niter_desc.may_be_zero;
1037 niter = niter_desc.niter;
1039 if (may_be_zero && integer_zerop (may_be_zero))
1040 may_be_zero = NULL_TREE;
1042 if (may_be_zero)
1044 if (COMPARISON_CLASS_P (may_be_zero))
1046 /* Try to combine may_be_zero with assumptions, this can simplify
1047 computation of niter expression. */
1048 if (niter_assumptions && !integer_nonzerop (niter_assumptions))
1049 niter_assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1050 niter_assumptions,
1051 fold_build1 (TRUTH_NOT_EXPR,
1052 boolean_type_node,
1053 may_be_zero));
1054 else
1055 niter = fold_build3 (COND_EXPR, TREE_TYPE (niter), may_be_zero,
1056 build_int_cst (TREE_TYPE (niter), 0), niter);
1058 may_be_zero = NULL_TREE;
1060 else if (integer_nonzerop (may_be_zero))
1062 *number_of_iterationsm1 = build_int_cst (TREE_TYPE (niter), 0);
1063 *number_of_iterations = build_int_cst (TREE_TYPE (niter), 1);
1064 return cond;
1066 else
1067 return cond;
1070 *assumptions = niter_assumptions;
1071 *number_of_iterationsm1 = niter;
1073 /* We want the number of loop header executions which is the number
1074 of latch executions plus one.
1075 ??? For UINT_MAX latch executions this number overflows to zero
1076 for loops like do { n++; } while (n != 0); */
1077 if (niter && !chrec_contains_undetermined (niter))
1078 niter = fold_build2 (PLUS_EXPR, TREE_TYPE (niter), unshare_expr (niter),
1079 build_int_cst (TREE_TYPE (niter), 1));
1080 *number_of_iterations = niter;
1082 return cond;
1085 /* Function bb_in_loop_p
1087 Used as predicate for dfs order traversal of the loop bbs. */
1089 static bool
1090 bb_in_loop_p (const_basic_block bb, const void *data)
1092 const struct loop *const loop = (const struct loop *)data;
1093 if (flow_bb_inside_loop_p (loop, bb))
1094 return true;
1095 return false;
1099 /* Function new_loop_vec_info.
1101 Create and initialize a new loop_vec_info struct for LOOP, as well as
1102 stmt_vec_info structs for all the stmts in LOOP. */
1104 static loop_vec_info
1105 new_loop_vec_info (struct loop *loop)
1107 loop_vec_info res;
1108 basic_block *bbs;
1109 gimple_stmt_iterator si;
1110 unsigned int i, nbbs;
1112 res = (loop_vec_info) xcalloc (1, sizeof (struct _loop_vec_info));
1113 res->kind = vec_info::loop;
1114 LOOP_VINFO_LOOP (res) = loop;
1116 bbs = get_loop_body (loop);
1118 /* Create/Update stmt_info for all stmts in the loop. */
1119 for (i = 0; i < loop->num_nodes; i++)
1121 basic_block bb = bbs[i];
1123 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
1125 gimple *phi = gsi_stmt (si);
1126 gimple_set_uid (phi, 0);
1127 set_vinfo_for_stmt (phi, new_stmt_vec_info (phi, res));
1130 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1132 gimple *stmt = gsi_stmt (si);
1133 gimple_set_uid (stmt, 0);
1134 set_vinfo_for_stmt (stmt, new_stmt_vec_info (stmt, res));
1138 /* CHECKME: We want to visit all BBs before their successors (except for
1139 latch blocks, for which this assertion wouldn't hold). In the simple
1140 case of the loop forms we allow, a dfs order of the BBs would the same
1141 as reversed postorder traversal, so we are safe. */
1143 free (bbs);
1144 bbs = XCNEWVEC (basic_block, loop->num_nodes);
1145 nbbs = dfs_enumerate_from (loop->header, 0, bb_in_loop_p,
1146 bbs, loop->num_nodes, loop);
1147 gcc_assert (nbbs == loop->num_nodes);
1149 LOOP_VINFO_BBS (res) = bbs;
1150 LOOP_VINFO_NITERSM1 (res) = NULL;
1151 LOOP_VINFO_NITERS (res) = NULL;
1152 LOOP_VINFO_NITERS_UNCHANGED (res) = NULL;
1153 LOOP_VINFO_NITERS_ASSUMPTIONS (res) = NULL;
1154 LOOP_VINFO_COST_MODEL_THRESHOLD (res) = 0;
1155 LOOP_VINFO_VECTORIZABLE_P (res) = 0;
1156 LOOP_VINFO_PEELING_FOR_ALIGNMENT (res) = 0;
1157 LOOP_VINFO_VECT_FACTOR (res) = 0;
1158 LOOP_VINFO_LOOP_NEST (res) = vNULL;
1159 LOOP_VINFO_DATAREFS (res) = vNULL;
1160 LOOP_VINFO_DDRS (res) = vNULL;
1161 LOOP_VINFO_UNALIGNED_DR (res) = NULL;
1162 LOOP_VINFO_MAY_MISALIGN_STMTS (res) = vNULL;
1163 LOOP_VINFO_MAY_ALIAS_DDRS (res) = vNULL;
1164 LOOP_VINFO_GROUPED_STORES (res) = vNULL;
1165 LOOP_VINFO_REDUCTIONS (res) = vNULL;
1166 LOOP_VINFO_REDUCTION_CHAINS (res) = vNULL;
1167 LOOP_VINFO_SLP_INSTANCES (res) = vNULL;
1168 LOOP_VINFO_SLP_UNROLLING_FACTOR (res) = 1;
1169 LOOP_VINFO_TARGET_COST_DATA (res) = init_cost (loop);
1170 LOOP_VINFO_PEELING_FOR_GAPS (res) = false;
1171 LOOP_VINFO_PEELING_FOR_NITER (res) = false;
1172 LOOP_VINFO_OPERANDS_SWAPPED (res) = false;
1173 LOOP_VINFO_ORIG_LOOP_INFO (res) = NULL;
1175 return res;
1179 /* Function destroy_loop_vec_info.
1181 Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
1182 stmts in the loop. */
1184 void
1185 destroy_loop_vec_info (loop_vec_info loop_vinfo, bool clean_stmts)
1187 struct loop *loop;
1188 basic_block *bbs;
1189 int nbbs;
1190 gimple_stmt_iterator si;
1191 int j;
1192 vec<slp_instance> slp_instances;
1193 slp_instance instance;
1194 bool swapped;
1196 if (!loop_vinfo)
1197 return;
1199 loop = LOOP_VINFO_LOOP (loop_vinfo);
1201 bbs = LOOP_VINFO_BBS (loop_vinfo);
1202 nbbs = clean_stmts ? loop->num_nodes : 0;
1203 swapped = LOOP_VINFO_OPERANDS_SWAPPED (loop_vinfo);
1205 for (j = 0; j < nbbs; j++)
1207 basic_block bb = bbs[j];
1208 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
1209 free_stmt_vec_info (gsi_stmt (si));
1211 for (si = gsi_start_bb (bb); !gsi_end_p (si); )
1213 gimple *stmt = gsi_stmt (si);
1215 /* We may have broken canonical form by moving a constant
1216 into RHS1 of a commutative op. Fix such occurrences. */
1217 if (swapped && is_gimple_assign (stmt))
1219 enum tree_code code = gimple_assign_rhs_code (stmt);
1221 if ((code == PLUS_EXPR
1222 || code == POINTER_PLUS_EXPR
1223 || code == MULT_EXPR)
1224 && CONSTANT_CLASS_P (gimple_assign_rhs1 (stmt)))
1225 swap_ssa_operands (stmt,
1226 gimple_assign_rhs1_ptr (stmt),
1227 gimple_assign_rhs2_ptr (stmt));
1228 else if (code == COND_EXPR
1229 && CONSTANT_CLASS_P (gimple_assign_rhs2 (stmt)))
1231 tree cond_expr = gimple_assign_rhs1 (stmt);
1232 enum tree_code cond_code = TREE_CODE (cond_expr);
1234 if (TREE_CODE_CLASS (cond_code) == tcc_comparison)
1236 bool honor_nans = HONOR_NANS (TREE_OPERAND (cond_expr,
1237 0));
1238 cond_code = invert_tree_comparison (cond_code,
1239 honor_nans);
1240 if (cond_code != ERROR_MARK)
1242 TREE_SET_CODE (cond_expr, cond_code);
1243 swap_ssa_operands (stmt,
1244 gimple_assign_rhs2_ptr (stmt),
1245 gimple_assign_rhs3_ptr (stmt));
1251 /* Free stmt_vec_info. */
1252 free_stmt_vec_info (stmt);
1253 gsi_next (&si);
1257 free (LOOP_VINFO_BBS (loop_vinfo));
1258 vect_destroy_datarefs (loop_vinfo);
1259 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo));
1260 LOOP_VINFO_LOOP_NEST (loop_vinfo).release ();
1261 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).release ();
1262 LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo).release ();
1263 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo).release ();
1264 slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
1265 FOR_EACH_VEC_ELT (slp_instances, j, instance)
1266 vect_free_slp_instance (instance);
1268 LOOP_VINFO_SLP_INSTANCES (loop_vinfo).release ();
1269 LOOP_VINFO_GROUPED_STORES (loop_vinfo).release ();
1270 LOOP_VINFO_REDUCTIONS (loop_vinfo).release ();
1271 LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo).release ();
1273 destroy_cost_data (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo));
1274 loop_vinfo->scalar_cost_vec.release ();
1276 free (loop_vinfo);
1277 loop->aux = NULL;
1281 /* Calculate the cost of one scalar iteration of the loop. */
1282 static void
1283 vect_compute_single_scalar_iteration_cost (loop_vec_info loop_vinfo)
1285 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1286 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1287 int nbbs = loop->num_nodes, factor, scalar_single_iter_cost = 0;
1288 int innerloop_iters, i;
1290 /* Count statements in scalar loop. Using this as scalar cost for a single
1291 iteration for now.
1293 TODO: Add outer loop support.
1295 TODO: Consider assigning different costs to different scalar
1296 statements. */
1298 /* FORNOW. */
1299 innerloop_iters = 1;
1300 if (loop->inner)
1301 innerloop_iters = 50; /* FIXME */
1303 for (i = 0; i < nbbs; i++)
1305 gimple_stmt_iterator si;
1306 basic_block bb = bbs[i];
1308 if (bb->loop_father == loop->inner)
1309 factor = innerloop_iters;
1310 else
1311 factor = 1;
1313 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1315 gimple *stmt = gsi_stmt (si);
1316 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1318 if (!is_gimple_assign (stmt) && !is_gimple_call (stmt))
1319 continue;
1321 /* Skip stmts that are not vectorized inside the loop. */
1322 if (stmt_info
1323 && !STMT_VINFO_RELEVANT_P (stmt_info)
1324 && (!STMT_VINFO_LIVE_P (stmt_info)
1325 || !VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info)))
1326 && !STMT_VINFO_IN_PATTERN_P (stmt_info))
1327 continue;
1329 vect_cost_for_stmt kind;
1330 if (STMT_VINFO_DATA_REF (stmt_info))
1332 if (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info)))
1333 kind = scalar_load;
1334 else
1335 kind = scalar_store;
1337 else
1338 kind = scalar_stmt;
1340 scalar_single_iter_cost
1341 += record_stmt_cost (&LOOP_VINFO_SCALAR_ITERATION_COST (loop_vinfo),
1342 factor, kind, stmt_info, 0, vect_prologue);
1345 LOOP_VINFO_SINGLE_SCALAR_ITERATION_COST (loop_vinfo)
1346 = scalar_single_iter_cost;
1350 /* Function vect_analyze_loop_form_1.
1352 Verify that certain CFG restrictions hold, including:
1353 - the loop has a pre-header
1354 - the loop has a single entry and exit
1355 - the loop exit condition is simple enough
1356 - the number of iterations can be analyzed, i.e, a countable loop. The
1357 niter could be analyzed under some assumptions. */
1359 bool
1360 vect_analyze_loop_form_1 (struct loop *loop, gcond **loop_cond,
1361 tree *assumptions, tree *number_of_iterationsm1,
1362 tree *number_of_iterations, gcond **inner_loop_cond)
1364 if (dump_enabled_p ())
1365 dump_printf_loc (MSG_NOTE, vect_location,
1366 "=== vect_analyze_loop_form ===\n");
1368 /* Different restrictions apply when we are considering an inner-most loop,
1369 vs. an outer (nested) loop.
1370 (FORNOW. May want to relax some of these restrictions in the future). */
1372 if (!loop->inner)
1374 /* Inner-most loop. We currently require that the number of BBs is
1375 exactly 2 (the header and latch). Vectorizable inner-most loops
1376 look like this:
1378 (pre-header)
1380 header <--------+
1381 | | |
1382 | +--> latch --+
1384 (exit-bb) */
1386 if (loop->num_nodes != 2)
1388 if (dump_enabled_p ())
1389 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1390 "not vectorized: control flow in loop.\n");
1391 return false;
1394 if (empty_block_p (loop->header))
1396 if (dump_enabled_p ())
1397 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1398 "not vectorized: empty loop.\n");
1399 return false;
1402 else
1404 struct loop *innerloop = loop->inner;
1405 edge entryedge;
1407 /* Nested loop. We currently require that the loop is doubly-nested,
1408 contains a single inner loop, and the number of BBs is exactly 5.
1409 Vectorizable outer-loops look like this:
1411 (pre-header)
1413 header <---+
1415 inner-loop |
1417 tail ------+
1419 (exit-bb)
1421 The inner-loop has the properties expected of inner-most loops
1422 as described above. */
1424 if ((loop->inner)->inner || (loop->inner)->next)
1426 if (dump_enabled_p ())
1427 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1428 "not vectorized: multiple nested loops.\n");
1429 return false;
1432 if (loop->num_nodes != 5)
1434 if (dump_enabled_p ())
1435 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1436 "not vectorized: control flow in loop.\n");
1437 return false;
1440 entryedge = loop_preheader_edge (innerloop);
1441 if (entryedge->src != loop->header
1442 || !single_exit (innerloop)
1443 || single_exit (innerloop)->dest != EDGE_PRED (loop->latch, 0)->src)
1445 if (dump_enabled_p ())
1446 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1447 "not vectorized: unsupported outerloop form.\n");
1448 return false;
1451 /* Analyze the inner-loop. */
1452 tree inner_niterm1, inner_niter, inner_assumptions;
1453 if (! vect_analyze_loop_form_1 (loop->inner, inner_loop_cond,
1454 &inner_assumptions, &inner_niterm1,
1455 &inner_niter, NULL)
1456 /* Don't support analyzing niter under assumptions for inner
1457 loop. */
1458 || !integer_onep (inner_assumptions))
1460 if (dump_enabled_p ())
1461 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1462 "not vectorized: Bad inner loop.\n");
1463 return false;
1466 if (!expr_invariant_in_loop_p (loop, inner_niter))
1468 if (dump_enabled_p ())
1469 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1470 "not vectorized: inner-loop count not"
1471 " invariant.\n");
1472 return false;
1475 if (dump_enabled_p ())
1476 dump_printf_loc (MSG_NOTE, vect_location,
1477 "Considering outer-loop vectorization.\n");
1480 if (!single_exit (loop)
1481 || EDGE_COUNT (loop->header->preds) != 2)
1483 if (dump_enabled_p ())
1485 if (!single_exit (loop))
1486 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1487 "not vectorized: multiple exits.\n");
1488 else if (EDGE_COUNT (loop->header->preds) != 2)
1489 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1490 "not vectorized: too many incoming edges.\n");
1492 return false;
1495 /* We assume that the loop exit condition is at the end of the loop. i.e,
1496 that the loop is represented as a do-while (with a proper if-guard
1497 before the loop if needed), where the loop header contains all the
1498 executable statements, and the latch is empty. */
1499 if (!empty_block_p (loop->latch)
1500 || !gimple_seq_empty_p (phi_nodes (loop->latch)))
1502 if (dump_enabled_p ())
1503 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1504 "not vectorized: latch block not empty.\n");
1505 return false;
1508 /* Make sure the exit is not abnormal. */
1509 edge e = single_exit (loop);
1510 if (e->flags & EDGE_ABNORMAL)
1512 if (dump_enabled_p ())
1513 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1514 "not vectorized: abnormal loop exit edge.\n");
1515 return false;
1518 *loop_cond = vect_get_loop_niters (loop, assumptions, number_of_iterations,
1519 number_of_iterationsm1);
1520 if (!*loop_cond)
1522 if (dump_enabled_p ())
1523 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1524 "not vectorized: complicated exit condition.\n");
1525 return false;
1528 if (integer_zerop (*assumptions)
1529 || !*number_of_iterations
1530 || chrec_contains_undetermined (*number_of_iterations))
1532 if (dump_enabled_p ())
1533 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1534 "not vectorized: number of iterations cannot be "
1535 "computed.\n");
1536 return false;
1539 if (integer_zerop (*number_of_iterations))
1541 if (dump_enabled_p ())
1542 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1543 "not vectorized: number of iterations = 0.\n");
1544 return false;
1547 return true;
1550 /* Analyze LOOP form and return a loop_vec_info if it is of suitable form. */
1552 loop_vec_info
1553 vect_analyze_loop_form (struct loop *loop)
1555 tree assumptions, number_of_iterations, number_of_iterationsm1;
1556 gcond *loop_cond, *inner_loop_cond = NULL;
1558 if (! vect_analyze_loop_form_1 (loop, &loop_cond,
1559 &assumptions, &number_of_iterationsm1,
1560 &number_of_iterations, &inner_loop_cond))
1561 return NULL;
1563 loop_vec_info loop_vinfo = new_loop_vec_info (loop);
1564 LOOP_VINFO_NITERSM1 (loop_vinfo) = number_of_iterationsm1;
1565 LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
1566 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo) = number_of_iterations;
1567 if (!integer_onep (assumptions))
1569 /* We consider to vectorize this loop by versioning it under
1570 some assumptions. In order to do this, we need to clear
1571 existing information computed by scev and niter analyzer. */
1572 scev_reset_htab ();
1573 free_numbers_of_iterations_estimates (loop);
1574 /* Also set flag for this loop so that following scev and niter
1575 analysis are done under the assumptions. */
1576 loop_constraint_set (loop, LOOP_C_FINITE);
1577 /* Also record the assumptions for versioning. */
1578 LOOP_VINFO_NITERS_ASSUMPTIONS (loop_vinfo) = assumptions;
1581 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
1583 if (dump_enabled_p ())
1585 dump_printf_loc (MSG_NOTE, vect_location,
1586 "Symbolic number of iterations is ");
1587 dump_generic_expr (MSG_NOTE, TDF_DETAILS, number_of_iterations);
1588 dump_printf (MSG_NOTE, "\n");
1592 STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond)) = loop_exit_ctrl_vec_info_type;
1593 if (inner_loop_cond)
1594 STMT_VINFO_TYPE (vinfo_for_stmt (inner_loop_cond))
1595 = loop_exit_ctrl_vec_info_type;
1597 gcc_assert (!loop->aux);
1598 loop->aux = loop_vinfo;
1599 return loop_vinfo;
1604 /* Scan the loop stmts and dependent on whether there are any (non-)SLP
1605 statements update the vectorization factor. */
1607 static void
1608 vect_update_vf_for_slp (loop_vec_info loop_vinfo)
1610 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1611 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1612 int nbbs = loop->num_nodes;
1613 unsigned int vectorization_factor;
1614 int i;
1616 if (dump_enabled_p ())
1617 dump_printf_loc (MSG_NOTE, vect_location,
1618 "=== vect_update_vf_for_slp ===\n");
1620 vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1621 gcc_assert (vectorization_factor != 0);
1623 /* If all the stmts in the loop can be SLPed, we perform only SLP, and
1624 vectorization factor of the loop is the unrolling factor required by
1625 the SLP instances. If that unrolling factor is 1, we say, that we
1626 perform pure SLP on loop - cross iteration parallelism is not
1627 exploited. */
1628 bool only_slp_in_loop = true;
1629 for (i = 0; i < nbbs; i++)
1631 basic_block bb = bbs[i];
1632 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
1633 gsi_next (&si))
1635 gimple *stmt = gsi_stmt (si);
1636 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1637 if (STMT_VINFO_IN_PATTERN_P (stmt_info)
1638 && STMT_VINFO_RELATED_STMT (stmt_info))
1640 stmt = STMT_VINFO_RELATED_STMT (stmt_info);
1641 stmt_info = vinfo_for_stmt (stmt);
1643 if ((STMT_VINFO_RELEVANT_P (stmt_info)
1644 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info)))
1645 && !PURE_SLP_STMT (stmt_info))
1646 /* STMT needs both SLP and loop-based vectorization. */
1647 only_slp_in_loop = false;
1651 if (only_slp_in_loop)
1653 dump_printf_loc (MSG_NOTE, vect_location,
1654 "Loop contains only SLP stmts\n");
1655 vectorization_factor = LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo);
1657 else
1659 dump_printf_loc (MSG_NOTE, vect_location,
1660 "Loop contains SLP and non-SLP stmts\n");
1661 vectorization_factor
1662 = least_common_multiple (vectorization_factor,
1663 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo));
1666 LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
1667 if (dump_enabled_p ())
1668 dump_printf_loc (MSG_NOTE, vect_location,
1669 "Updating vectorization factor to %d\n",
1670 vectorization_factor);
1673 /* Function vect_analyze_loop_operations.
1675 Scan the loop stmts and make sure they are all vectorizable. */
1677 static bool
1678 vect_analyze_loop_operations (loop_vec_info loop_vinfo)
1680 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1681 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1682 int nbbs = loop->num_nodes;
1683 int i;
1684 stmt_vec_info stmt_info;
1685 bool need_to_vectorize = false;
1686 bool ok;
1688 if (dump_enabled_p ())
1689 dump_printf_loc (MSG_NOTE, vect_location,
1690 "=== vect_analyze_loop_operations ===\n");
1692 for (i = 0; i < nbbs; i++)
1694 basic_block bb = bbs[i];
1696 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
1697 gsi_next (&si))
1699 gphi *phi = si.phi ();
1700 ok = true;
1702 stmt_info = vinfo_for_stmt (phi);
1703 if (dump_enabled_p ())
1705 dump_printf_loc (MSG_NOTE, vect_location, "examining phi: ");
1706 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
1708 if (virtual_operand_p (gimple_phi_result (phi)))
1709 continue;
1711 /* Inner-loop loop-closed exit phi in outer-loop vectorization
1712 (i.e., a phi in the tail of the outer-loop). */
1713 if (! is_loop_header_bb_p (bb))
1715 /* FORNOW: we currently don't support the case that these phis
1716 are not used in the outerloop (unless it is double reduction,
1717 i.e., this phi is vect_reduction_def), cause this case
1718 requires to actually do something here. */
1719 if (STMT_VINFO_LIVE_P (stmt_info)
1720 && STMT_VINFO_DEF_TYPE (stmt_info)
1721 != vect_double_reduction_def)
1723 if (dump_enabled_p ())
1724 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1725 "Unsupported loop-closed phi in "
1726 "outer-loop.\n");
1727 return false;
1730 /* If PHI is used in the outer loop, we check that its operand
1731 is defined in the inner loop. */
1732 if (STMT_VINFO_RELEVANT_P (stmt_info))
1734 tree phi_op;
1735 gimple *op_def_stmt;
1737 if (gimple_phi_num_args (phi) != 1)
1738 return false;
1740 phi_op = PHI_ARG_DEF (phi, 0);
1741 if (TREE_CODE (phi_op) != SSA_NAME)
1742 return false;
1744 op_def_stmt = SSA_NAME_DEF_STMT (phi_op);
1745 if (gimple_nop_p (op_def_stmt)
1746 || !flow_bb_inside_loop_p (loop, gimple_bb (op_def_stmt))
1747 || !vinfo_for_stmt (op_def_stmt))
1748 return false;
1750 if (STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt))
1751 != vect_used_in_outer
1752 && STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt))
1753 != vect_used_in_outer_by_reduction)
1754 return false;
1757 continue;
1760 gcc_assert (stmt_info);
1762 if ((STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_scope
1763 || STMT_VINFO_LIVE_P (stmt_info))
1764 && STMT_VINFO_DEF_TYPE (stmt_info) != vect_induction_def)
1766 /* A scalar-dependence cycle that we don't support. */
1767 if (dump_enabled_p ())
1768 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1769 "not vectorized: scalar dependence cycle.\n");
1770 return false;
1773 if (STMT_VINFO_RELEVANT_P (stmt_info))
1775 need_to_vectorize = true;
1776 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def
1777 && ! PURE_SLP_STMT (stmt_info))
1778 ok = vectorizable_induction (phi, NULL, NULL, NULL);
1781 if (ok && STMT_VINFO_LIVE_P (stmt_info))
1782 ok = vectorizable_live_operation (phi, NULL, NULL, -1, NULL);
1784 if (!ok)
1786 if (dump_enabled_p ())
1788 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1789 "not vectorized: relevant phi not "
1790 "supported: ");
1791 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, phi, 0);
1793 return false;
1797 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
1798 gsi_next (&si))
1800 gimple *stmt = gsi_stmt (si);
1801 if (!gimple_clobber_p (stmt)
1802 && !vect_analyze_stmt (stmt, &need_to_vectorize, NULL))
1803 return false;
1805 } /* bbs */
1807 /* All operations in the loop are either irrelevant (deal with loop
1808 control, or dead), or only used outside the loop and can be moved
1809 out of the loop (e.g. invariants, inductions). The loop can be
1810 optimized away by scalar optimizations. We're better off not
1811 touching this loop. */
1812 if (!need_to_vectorize)
1814 if (dump_enabled_p ())
1815 dump_printf_loc (MSG_NOTE, vect_location,
1816 "All the computation can be taken out of the loop.\n");
1817 if (dump_enabled_p ())
1818 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1819 "not vectorized: redundant loop. no profit to "
1820 "vectorize.\n");
1821 return false;
1824 return true;
1828 /* Function vect_analyze_loop_2.
1830 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1831 for it. The different analyses will record information in the
1832 loop_vec_info struct. */
1833 static bool
1834 vect_analyze_loop_2 (loop_vec_info loop_vinfo, bool &fatal)
1836 bool ok;
1837 int max_vf = MAX_VECTORIZATION_FACTOR;
1838 int min_vf = 2;
1839 unsigned int n_stmts = 0;
1841 /* The first group of checks is independent of the vector size. */
1842 fatal = true;
1844 /* Find all data references in the loop (which correspond to vdefs/vuses)
1845 and analyze their evolution in the loop. */
1847 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1849 loop_p loop = LOOP_VINFO_LOOP (loop_vinfo);
1850 if (!find_loop_nest (loop, &LOOP_VINFO_LOOP_NEST (loop_vinfo)))
1852 if (dump_enabled_p ())
1853 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1854 "not vectorized: loop nest containing two "
1855 "or more consecutive inner loops cannot be "
1856 "vectorized\n");
1857 return false;
1860 for (unsigned i = 0; i < loop->num_nodes; i++)
1861 for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]);
1862 !gsi_end_p (gsi); gsi_next (&gsi))
1864 gimple *stmt = gsi_stmt (gsi);
1865 if (is_gimple_debug (stmt))
1866 continue;
1867 ++n_stmts;
1868 if (!find_data_references_in_stmt (loop, stmt,
1869 &LOOP_VINFO_DATAREFS (loop_vinfo)))
1871 if (is_gimple_call (stmt) && loop->safelen)
1873 tree fndecl = gimple_call_fndecl (stmt), op;
1874 if (fndecl != NULL_TREE)
1876 cgraph_node *node = cgraph_node::get (fndecl);
1877 if (node != NULL && node->simd_clones != NULL)
1879 unsigned int j, n = gimple_call_num_args (stmt);
1880 for (j = 0; j < n; j++)
1882 op = gimple_call_arg (stmt, j);
1883 if (DECL_P (op)
1884 || (REFERENCE_CLASS_P (op)
1885 && get_base_address (op)))
1886 break;
1888 op = gimple_call_lhs (stmt);
1889 /* Ignore #pragma omp declare simd functions
1890 if they don't have data references in the
1891 call stmt itself. */
1892 if (j == n
1893 && !(op
1894 && (DECL_P (op)
1895 || (REFERENCE_CLASS_P (op)
1896 && get_base_address (op)))))
1897 continue;
1901 if (dump_enabled_p ())
1902 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1903 "not vectorized: loop contains function "
1904 "calls or data references that cannot "
1905 "be analyzed\n");
1906 return false;
1910 /* Analyze the data references and also adjust the minimal
1911 vectorization factor according to the loads and stores. */
1913 ok = vect_analyze_data_refs (loop_vinfo, &min_vf);
1914 if (!ok)
1916 if (dump_enabled_p ())
1917 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1918 "bad data references.\n");
1919 return false;
1922 /* Classify all cross-iteration scalar data-flow cycles.
1923 Cross-iteration cycles caused by virtual phis are analyzed separately. */
1924 vect_analyze_scalar_cycles (loop_vinfo);
1926 vect_pattern_recog (loop_vinfo);
1928 vect_fixup_scalar_cycles_with_patterns (loop_vinfo);
1930 /* Analyze the access patterns of the data-refs in the loop (consecutive,
1931 complex, etc.). FORNOW: Only handle consecutive access pattern. */
1933 ok = vect_analyze_data_ref_accesses (loop_vinfo);
1934 if (!ok)
1936 if (dump_enabled_p ())
1937 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1938 "bad data access.\n");
1939 return false;
1942 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
1944 ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
1945 if (!ok)
1947 if (dump_enabled_p ())
1948 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1949 "unexpected pattern.\n");
1950 return false;
1953 /* While the rest of the analysis below depends on it in some way. */
1954 fatal = false;
1956 /* Analyze data dependences between the data-refs in the loop
1957 and adjust the maximum vectorization factor according to
1958 the dependences.
1959 FORNOW: fail at the first data dependence that we encounter. */
1961 ok = vect_analyze_data_ref_dependences (loop_vinfo, &max_vf);
1962 if (!ok
1963 || max_vf < min_vf)
1965 if (dump_enabled_p ())
1966 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1967 "bad data dependence.\n");
1968 return false;
1971 ok = vect_determine_vectorization_factor (loop_vinfo);
1972 if (!ok)
1974 if (dump_enabled_p ())
1975 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1976 "can't determine vectorization factor.\n");
1977 return false;
1979 if (max_vf < LOOP_VINFO_VECT_FACTOR (loop_vinfo))
1981 if (dump_enabled_p ())
1982 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1983 "bad data dependence.\n");
1984 return false;
1987 /* Compute the scalar iteration cost. */
1988 vect_compute_single_scalar_iteration_cost (loop_vinfo);
1990 int saved_vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1991 HOST_WIDE_INT estimated_niter;
1992 unsigned th;
1993 int min_scalar_loop_bound;
1995 /* Check the SLP opportunities in the loop, analyze and build SLP trees. */
1996 ok = vect_analyze_slp (loop_vinfo, n_stmts);
1997 if (!ok)
1998 return false;
2000 /* If there are any SLP instances mark them as pure_slp. */
2001 bool slp = vect_make_slp_decision (loop_vinfo);
2002 if (slp)
2004 /* Find stmts that need to be both vectorized and SLPed. */
2005 vect_detect_hybrid_slp (loop_vinfo);
2007 /* Update the vectorization factor based on the SLP decision. */
2008 vect_update_vf_for_slp (loop_vinfo);
2011 /* This is the point where we can re-start analysis with SLP forced off. */
2012 start_over:
2014 /* Now the vectorization factor is final. */
2015 unsigned vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2016 gcc_assert (vectorization_factor != 0);
2018 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo) && dump_enabled_p ())
2019 dump_printf_loc (MSG_NOTE, vect_location,
2020 "vectorization_factor = %d, niters = "
2021 HOST_WIDE_INT_PRINT_DEC "\n", vectorization_factor,
2022 LOOP_VINFO_INT_NITERS (loop_vinfo));
2024 HOST_WIDE_INT max_niter
2025 = likely_max_stmt_executions_int (LOOP_VINFO_LOOP (loop_vinfo));
2026 if ((LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
2027 && (LOOP_VINFO_INT_NITERS (loop_vinfo) < vectorization_factor))
2028 || (max_niter != -1
2029 && (unsigned HOST_WIDE_INT) max_niter < vectorization_factor))
2031 if (dump_enabled_p ())
2032 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2033 "not vectorized: iteration count smaller than "
2034 "vectorization factor.\n");
2035 return false;
2038 /* Analyze the alignment of the data-refs in the loop.
2039 Fail if a data reference is found that cannot be vectorized. */
2041 ok = vect_analyze_data_refs_alignment (loop_vinfo);
2042 if (!ok)
2044 if (dump_enabled_p ())
2045 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2046 "bad data alignment.\n");
2047 return false;
2050 /* Prune the list of ddrs to be tested at run-time by versioning for alias.
2051 It is important to call pruning after vect_analyze_data_ref_accesses,
2052 since we use grouping information gathered by interleaving analysis. */
2053 ok = vect_prune_runtime_alias_test_list (loop_vinfo);
2054 if (!ok)
2055 return false;
2057 /* Do not invoke vect_enhance_data_refs_alignment for eplilogue
2058 vectorization. */
2059 if (!LOOP_VINFO_EPILOGUE_P (loop_vinfo))
2061 /* This pass will decide on using loop versioning and/or loop peeling in
2062 order to enhance the alignment of data references in the loop. */
2063 ok = vect_enhance_data_refs_alignment (loop_vinfo);
2064 if (!ok)
2066 if (dump_enabled_p ())
2067 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2068 "bad data alignment.\n");
2069 return false;
2073 if (slp)
2075 /* Analyze operations in the SLP instances. Note this may
2076 remove unsupported SLP instances which makes the above
2077 SLP kind detection invalid. */
2078 unsigned old_size = LOOP_VINFO_SLP_INSTANCES (loop_vinfo).length ();
2079 vect_slp_analyze_operations (LOOP_VINFO_SLP_INSTANCES (loop_vinfo),
2080 LOOP_VINFO_TARGET_COST_DATA (loop_vinfo));
2081 if (LOOP_VINFO_SLP_INSTANCES (loop_vinfo).length () != old_size)
2082 goto again;
2085 /* Scan all the remaining operations in the loop that are not subject
2086 to SLP and make sure they are vectorizable. */
2087 ok = vect_analyze_loop_operations (loop_vinfo);
2088 if (!ok)
2090 if (dump_enabled_p ())
2091 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2092 "bad operation or unsupported loop bound.\n");
2093 return false;
2096 /* If epilog loop is required because of data accesses with gaps,
2097 one additional iteration needs to be peeled. Check if there is
2098 enough iterations for vectorization. */
2099 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo)
2100 && LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
2102 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2103 tree scalar_niters = LOOP_VINFO_NITERSM1 (loop_vinfo);
2105 if (wi::to_widest (scalar_niters) < vf)
2107 if (dump_enabled_p ())
2108 dump_printf_loc (MSG_NOTE, vect_location,
2109 "loop has no enough iterations to support"
2110 " peeling for gaps.\n");
2111 return false;
2115 /* Analyze cost. Decide if worth while to vectorize. */
2116 int min_profitable_estimate, min_profitable_iters;
2117 vect_estimate_min_profitable_iters (loop_vinfo, &min_profitable_iters,
2118 &min_profitable_estimate);
2120 if (min_profitable_iters < 0)
2122 if (dump_enabled_p ())
2123 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2124 "not vectorized: vectorization not profitable.\n");
2125 if (dump_enabled_p ())
2126 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2127 "not vectorized: vector version will never be "
2128 "profitable.\n");
2129 goto again;
2132 min_scalar_loop_bound = ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND)
2133 * vectorization_factor) - 1);
2135 /* Use the cost model only if it is more conservative than user specified
2136 threshold. */
2137 th = (unsigned) min_scalar_loop_bound;
2138 if (min_profitable_iters
2139 && (!min_scalar_loop_bound
2140 || min_profitable_iters > min_scalar_loop_bound))
2141 th = (unsigned) min_profitable_iters;
2143 LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo) = th;
2145 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
2146 && LOOP_VINFO_INT_NITERS (loop_vinfo) <= th)
2148 if (dump_enabled_p ())
2149 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2150 "not vectorized: vectorization not profitable.\n");
2151 if (dump_enabled_p ())
2152 dump_printf_loc (MSG_NOTE, vect_location,
2153 "not vectorized: iteration count smaller than user "
2154 "specified loop bound parameter or minimum profitable "
2155 "iterations (whichever is more conservative).\n");
2156 goto again;
2159 estimated_niter
2160 = estimated_stmt_executions_int (LOOP_VINFO_LOOP (loop_vinfo));
2161 if (estimated_niter == -1)
2162 estimated_niter = max_niter;
2163 if (estimated_niter != -1
2164 && ((unsigned HOST_WIDE_INT) estimated_niter
2165 <= MAX (th, (unsigned)min_profitable_estimate)))
2167 if (dump_enabled_p ())
2168 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2169 "not vectorized: estimated iteration count too "
2170 "small.\n");
2171 if (dump_enabled_p ())
2172 dump_printf_loc (MSG_NOTE, vect_location,
2173 "not vectorized: estimated iteration count smaller "
2174 "than specified loop bound parameter or minimum "
2175 "profitable iterations (whichever is more "
2176 "conservative).\n");
2177 goto again;
2180 /* Decide whether we need to create an epilogue loop to handle
2181 remaining scalar iterations. */
2182 th = ((LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo) + 1)
2183 / LOOP_VINFO_VECT_FACTOR (loop_vinfo))
2184 * LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2186 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
2187 && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) > 0)
2189 if (ctz_hwi (LOOP_VINFO_INT_NITERS (loop_vinfo)
2190 - LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo))
2191 < exact_log2 (LOOP_VINFO_VECT_FACTOR (loop_vinfo)))
2192 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo) = true;
2194 else if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo)
2195 || (tree_ctz (LOOP_VINFO_NITERS (loop_vinfo))
2196 < (unsigned)exact_log2 (LOOP_VINFO_VECT_FACTOR (loop_vinfo))
2197 /* In case of versioning, check if the maximum number of
2198 iterations is greater than th. If they are identical,
2199 the epilogue is unnecessary. */
2200 && (!LOOP_REQUIRES_VERSIONING (loop_vinfo)
2201 || (unsigned HOST_WIDE_INT) max_niter > th)))
2202 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo) = true;
2204 /* If an epilogue loop is required make sure we can create one. */
2205 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo)
2206 || LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo))
2208 if (dump_enabled_p ())
2209 dump_printf_loc (MSG_NOTE, vect_location, "epilog loop required\n");
2210 if (!vect_can_advance_ivs_p (loop_vinfo)
2211 || !slpeel_can_duplicate_loop_p (LOOP_VINFO_LOOP (loop_vinfo),
2212 single_exit (LOOP_VINFO_LOOP
2213 (loop_vinfo))))
2215 if (dump_enabled_p ())
2216 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2217 "not vectorized: can't create required "
2218 "epilog loop\n");
2219 goto again;
2223 /* During peeling, we need to check if number of loop iterations is
2224 enough for both peeled prolog loop and vector loop. This check
2225 can be merged along with threshold check of loop versioning, so
2226 increase threshold for this case if necessary. */
2227 if (LOOP_REQUIRES_VERSIONING (loop_vinfo)
2228 && (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo)
2229 || LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo)))
2231 unsigned niters_th;
2233 /* Niters for peeled prolog loop. */
2234 if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0)
2236 struct data_reference *dr = LOOP_VINFO_UNALIGNED_DR (loop_vinfo);
2237 tree vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr)));
2239 niters_th = TYPE_VECTOR_SUBPARTS (vectype) - 1;
2241 else
2242 niters_th = LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo);
2244 /* Niters for at least one iteration of vectorized loop. */
2245 niters_th += LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2246 /* One additional iteration because of peeling for gap. */
2247 if (!LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo))
2248 niters_th++;
2249 if (LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo) < niters_th)
2250 LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo) = niters_th;
2253 gcc_assert (vectorization_factor
2254 == (unsigned)LOOP_VINFO_VECT_FACTOR (loop_vinfo));
2256 /* Ok to vectorize! */
2257 return true;
2259 again:
2260 /* Try again with SLP forced off but if we didn't do any SLP there is
2261 no point in re-trying. */
2262 if (!slp)
2263 return false;
2265 /* If there are reduction chains re-trying will fail anyway. */
2266 if (! LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo).is_empty ())
2267 return false;
2269 /* Likewise if the grouped loads or stores in the SLP cannot be handled
2270 via interleaving or lane instructions. */
2271 slp_instance instance;
2272 slp_tree node;
2273 unsigned i, j;
2274 FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (loop_vinfo), i, instance)
2276 stmt_vec_info vinfo;
2277 vinfo = vinfo_for_stmt
2278 (SLP_TREE_SCALAR_STMTS (SLP_INSTANCE_TREE (instance))[0]);
2279 if (! STMT_VINFO_GROUPED_ACCESS (vinfo))
2280 continue;
2281 vinfo = vinfo_for_stmt (STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo));
2282 unsigned int size = STMT_VINFO_GROUP_SIZE (vinfo);
2283 tree vectype = STMT_VINFO_VECTYPE (vinfo);
2284 if (! vect_store_lanes_supported (vectype, size)
2285 && ! vect_grouped_store_supported (vectype, size))
2286 return false;
2287 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (instance), j, node)
2289 vinfo = vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (node)[0]);
2290 vinfo = vinfo_for_stmt (STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo));
2291 bool single_element_p = !STMT_VINFO_GROUP_NEXT_ELEMENT (vinfo);
2292 size = STMT_VINFO_GROUP_SIZE (vinfo);
2293 vectype = STMT_VINFO_VECTYPE (vinfo);
2294 if (! vect_load_lanes_supported (vectype, size)
2295 && ! vect_grouped_load_supported (vectype, single_element_p,
2296 size))
2297 return false;
2301 if (dump_enabled_p ())
2302 dump_printf_loc (MSG_NOTE, vect_location,
2303 "re-trying with SLP disabled\n");
2305 /* Roll back state appropriately. No SLP this time. */
2306 slp = false;
2307 /* Restore vectorization factor as it were without SLP. */
2308 LOOP_VINFO_VECT_FACTOR (loop_vinfo) = saved_vectorization_factor;
2309 /* Free the SLP instances. */
2310 FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (loop_vinfo), j, instance)
2311 vect_free_slp_instance (instance);
2312 LOOP_VINFO_SLP_INSTANCES (loop_vinfo).release ();
2313 /* Reset SLP type to loop_vect on all stmts. */
2314 for (i = 0; i < LOOP_VINFO_LOOP (loop_vinfo)->num_nodes; ++i)
2316 basic_block bb = LOOP_VINFO_BBS (loop_vinfo)[i];
2317 for (gimple_stmt_iterator si = gsi_start_phis (bb);
2318 !gsi_end_p (si); gsi_next (&si))
2320 stmt_vec_info stmt_info = vinfo_for_stmt (gsi_stmt (si));
2321 STMT_SLP_TYPE (stmt_info) = loop_vect;
2323 for (gimple_stmt_iterator si = gsi_start_bb (bb);
2324 !gsi_end_p (si); gsi_next (&si))
2326 stmt_vec_info stmt_info = vinfo_for_stmt (gsi_stmt (si));
2327 STMT_SLP_TYPE (stmt_info) = loop_vect;
2328 if (STMT_VINFO_IN_PATTERN_P (stmt_info))
2330 stmt_info = vinfo_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info));
2331 STMT_SLP_TYPE (stmt_info) = loop_vect;
2332 for (gimple_stmt_iterator pi
2333 = gsi_start (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info));
2334 !gsi_end_p (pi); gsi_next (&pi))
2336 gimple *pstmt = gsi_stmt (pi);
2337 STMT_SLP_TYPE (vinfo_for_stmt (pstmt)) = loop_vect;
2342 /* Free optimized alias test DDRS. */
2343 LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo).release ();
2344 /* Reset target cost data. */
2345 destroy_cost_data (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo));
2346 LOOP_VINFO_TARGET_COST_DATA (loop_vinfo)
2347 = init_cost (LOOP_VINFO_LOOP (loop_vinfo));
2348 /* Reset assorted flags. */
2349 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo) = false;
2350 LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo) = false;
2351 LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo) = 0;
2353 goto start_over;
2356 /* Function vect_analyze_loop.
2358 Apply a set of analyses on LOOP, and create a loop_vec_info struct
2359 for it. The different analyses will record information in the
2360 loop_vec_info struct. If ORIG_LOOP_VINFO is not NULL epilogue must
2361 be vectorized. */
2362 loop_vec_info
2363 vect_analyze_loop (struct loop *loop, loop_vec_info orig_loop_vinfo)
2365 loop_vec_info loop_vinfo;
2366 unsigned int vector_sizes;
2368 /* Autodetect first vector size we try. */
2369 current_vector_size = 0;
2370 vector_sizes = targetm.vectorize.autovectorize_vector_sizes ();
2372 if (dump_enabled_p ())
2373 dump_printf_loc (MSG_NOTE, vect_location,
2374 "===== analyze_loop_nest =====\n");
2376 if (loop_outer (loop)
2377 && loop_vec_info_for_loop (loop_outer (loop))
2378 && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop))))
2380 if (dump_enabled_p ())
2381 dump_printf_loc (MSG_NOTE, vect_location,
2382 "outer-loop already vectorized.\n");
2383 return NULL;
2386 while (1)
2388 /* Check the CFG characteristics of the loop (nesting, entry/exit). */
2389 loop_vinfo = vect_analyze_loop_form (loop);
2390 if (!loop_vinfo)
2392 if (dump_enabled_p ())
2393 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2394 "bad loop form.\n");
2395 return NULL;
2398 bool fatal = false;
2400 if (orig_loop_vinfo)
2401 LOOP_VINFO_ORIG_LOOP_INFO (loop_vinfo) = orig_loop_vinfo;
2403 if (vect_analyze_loop_2 (loop_vinfo, fatal))
2405 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1;
2407 return loop_vinfo;
2410 destroy_loop_vec_info (loop_vinfo, true);
2412 vector_sizes &= ~current_vector_size;
2413 if (fatal
2414 || vector_sizes == 0
2415 || current_vector_size == 0)
2416 return NULL;
2418 /* Try the next biggest vector size. */
2419 current_vector_size = 1 << floor_log2 (vector_sizes);
2420 if (dump_enabled_p ())
2421 dump_printf_loc (MSG_NOTE, vect_location,
2422 "***** Re-trying analysis with "
2423 "vector size %d\n", current_vector_size);
2428 /* Function reduction_code_for_scalar_code
2430 Input:
2431 CODE - tree_code of a reduction operations.
2433 Output:
2434 REDUC_CODE - the corresponding tree-code to be used to reduce the
2435 vector of partial results into a single scalar result, or ERROR_MARK
2436 if the operation is a supported reduction operation, but does not have
2437 such a tree-code.
2439 Return FALSE if CODE currently cannot be vectorized as reduction. */
2441 static bool
2442 reduction_code_for_scalar_code (enum tree_code code,
2443 enum tree_code *reduc_code)
2445 switch (code)
2447 case MAX_EXPR:
2448 *reduc_code = REDUC_MAX_EXPR;
2449 return true;
2451 case MIN_EXPR:
2452 *reduc_code = REDUC_MIN_EXPR;
2453 return true;
2455 case PLUS_EXPR:
2456 *reduc_code = REDUC_PLUS_EXPR;
2457 return true;
2459 case MULT_EXPR:
2460 case MINUS_EXPR:
2461 case BIT_IOR_EXPR:
2462 case BIT_XOR_EXPR:
2463 case BIT_AND_EXPR:
2464 *reduc_code = ERROR_MARK;
2465 return true;
2467 default:
2468 return false;
2473 /* Error reporting helper for vect_is_simple_reduction below. GIMPLE statement
2474 STMT is printed with a message MSG. */
2476 static void
2477 report_vect_op (dump_flags_t msg_type, gimple *stmt, const char *msg)
2479 dump_printf_loc (msg_type, vect_location, "%s", msg);
2480 dump_gimple_stmt (msg_type, TDF_SLIM, stmt, 0);
2484 /* Detect SLP reduction of the form:
2486 #a1 = phi <a5, a0>
2487 a2 = operation (a1)
2488 a3 = operation (a2)
2489 a4 = operation (a3)
2490 a5 = operation (a4)
2492 #a = phi <a5>
2494 PHI is the reduction phi node (#a1 = phi <a5, a0> above)
2495 FIRST_STMT is the first reduction stmt in the chain
2496 (a2 = operation (a1)).
2498 Return TRUE if a reduction chain was detected. */
2500 static bool
2501 vect_is_slp_reduction (loop_vec_info loop_info, gimple *phi,
2502 gimple *first_stmt)
2504 struct loop *loop = (gimple_bb (phi))->loop_father;
2505 struct loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
2506 enum tree_code code;
2507 gimple *current_stmt = NULL, *loop_use_stmt = NULL, *first, *next_stmt;
2508 stmt_vec_info use_stmt_info, current_stmt_info;
2509 tree lhs;
2510 imm_use_iterator imm_iter;
2511 use_operand_p use_p;
2512 int nloop_uses, size = 0, n_out_of_loop_uses;
2513 bool found = false;
2515 if (loop != vect_loop)
2516 return false;
2518 lhs = PHI_RESULT (phi);
2519 code = gimple_assign_rhs_code (first_stmt);
2520 while (1)
2522 nloop_uses = 0;
2523 n_out_of_loop_uses = 0;
2524 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
2526 gimple *use_stmt = USE_STMT (use_p);
2527 if (is_gimple_debug (use_stmt))
2528 continue;
2530 /* Check if we got back to the reduction phi. */
2531 if (use_stmt == phi)
2533 loop_use_stmt = use_stmt;
2534 found = true;
2535 break;
2538 if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
2540 loop_use_stmt = use_stmt;
2541 nloop_uses++;
2543 else
2544 n_out_of_loop_uses++;
2546 /* There are can be either a single use in the loop or two uses in
2547 phi nodes. */
2548 if (nloop_uses > 1 || (n_out_of_loop_uses && nloop_uses))
2549 return false;
2552 if (found)
2553 break;
2555 /* We reached a statement with no loop uses. */
2556 if (nloop_uses == 0)
2557 return false;
2559 /* This is a loop exit phi, and we haven't reached the reduction phi. */
2560 if (gimple_code (loop_use_stmt) == GIMPLE_PHI)
2561 return false;
2563 if (!is_gimple_assign (loop_use_stmt)
2564 || code != gimple_assign_rhs_code (loop_use_stmt)
2565 || !flow_bb_inside_loop_p (loop, gimple_bb (loop_use_stmt)))
2566 return false;
2568 /* Insert USE_STMT into reduction chain. */
2569 use_stmt_info = vinfo_for_stmt (loop_use_stmt);
2570 if (current_stmt)
2572 current_stmt_info = vinfo_for_stmt (current_stmt);
2573 GROUP_NEXT_ELEMENT (current_stmt_info) = loop_use_stmt;
2574 GROUP_FIRST_ELEMENT (use_stmt_info)
2575 = GROUP_FIRST_ELEMENT (current_stmt_info);
2577 else
2578 GROUP_FIRST_ELEMENT (use_stmt_info) = loop_use_stmt;
2580 lhs = gimple_assign_lhs (loop_use_stmt);
2581 current_stmt = loop_use_stmt;
2582 size++;
2585 if (!found || loop_use_stmt != phi || size < 2)
2586 return false;
2588 /* Swap the operands, if needed, to make the reduction operand be the second
2589 operand. */
2590 lhs = PHI_RESULT (phi);
2591 next_stmt = GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt));
2592 while (next_stmt)
2594 if (gimple_assign_rhs2 (next_stmt) == lhs)
2596 tree op = gimple_assign_rhs1 (next_stmt);
2597 gimple *def_stmt = NULL;
2599 if (TREE_CODE (op) == SSA_NAME)
2600 def_stmt = SSA_NAME_DEF_STMT (op);
2602 /* Check that the other def is either defined in the loop
2603 ("vect_internal_def"), or it's an induction (defined by a
2604 loop-header phi-node). */
2605 if (def_stmt
2606 && gimple_bb (def_stmt)
2607 && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
2608 && (is_gimple_assign (def_stmt)
2609 || is_gimple_call (def_stmt)
2610 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
2611 == vect_induction_def
2612 || (gimple_code (def_stmt) == GIMPLE_PHI
2613 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
2614 == vect_internal_def
2615 && !is_loop_header_bb_p (gimple_bb (def_stmt)))))
2617 lhs = gimple_assign_lhs (next_stmt);
2618 next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
2619 continue;
2622 return false;
2624 else
2626 tree op = gimple_assign_rhs2 (next_stmt);
2627 gimple *def_stmt = NULL;
2629 if (TREE_CODE (op) == SSA_NAME)
2630 def_stmt = SSA_NAME_DEF_STMT (op);
2632 /* Check that the other def is either defined in the loop
2633 ("vect_internal_def"), or it's an induction (defined by a
2634 loop-header phi-node). */
2635 if (def_stmt
2636 && gimple_bb (def_stmt)
2637 && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
2638 && (is_gimple_assign (def_stmt)
2639 || is_gimple_call (def_stmt)
2640 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
2641 == vect_induction_def
2642 || (gimple_code (def_stmt) == GIMPLE_PHI
2643 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
2644 == vect_internal_def
2645 && !is_loop_header_bb_p (gimple_bb (def_stmt)))))
2647 if (dump_enabled_p ())
2649 dump_printf_loc (MSG_NOTE, vect_location, "swapping oprnds: ");
2650 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, next_stmt, 0);
2653 swap_ssa_operands (next_stmt,
2654 gimple_assign_rhs1_ptr (next_stmt),
2655 gimple_assign_rhs2_ptr (next_stmt));
2656 update_stmt (next_stmt);
2658 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (next_stmt)))
2659 LOOP_VINFO_OPERANDS_SWAPPED (loop_info) = true;
2661 else
2662 return false;
2665 lhs = gimple_assign_lhs (next_stmt);
2666 next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
2669 /* Save the chain for further analysis in SLP detection. */
2670 first = GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt));
2671 LOOP_VINFO_REDUCTION_CHAINS (loop_info).safe_push (first);
2672 GROUP_SIZE (vinfo_for_stmt (first)) = size;
2674 return true;
2678 /* Function vect_is_simple_reduction
2680 (1) Detect a cross-iteration def-use cycle that represents a simple
2681 reduction computation. We look for the following pattern:
2683 loop_header:
2684 a1 = phi < a0, a2 >
2685 a3 = ...
2686 a2 = operation (a3, a1)
2690 a3 = ...
2691 loop_header:
2692 a1 = phi < a0, a2 >
2693 a2 = operation (a3, a1)
2695 such that:
2696 1. operation is commutative and associative and it is safe to
2697 change the order of the computation
2698 2. no uses for a2 in the loop (a2 is used out of the loop)
2699 3. no uses of a1 in the loop besides the reduction operation
2700 4. no uses of a1 outside the loop.
2702 Conditions 1,4 are tested here.
2703 Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
2705 (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
2706 nested cycles.
2708 (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
2709 reductions:
2711 a1 = phi < a0, a2 >
2712 inner loop (def of a3)
2713 a2 = phi < a3 >
2715 (4) Detect condition expressions, ie:
2716 for (int i = 0; i < N; i++)
2717 if (a[i] < val)
2718 ret_val = a[i];
2722 static gimple *
2723 vect_is_simple_reduction (loop_vec_info loop_info, gimple *phi,
2724 bool *double_reduc,
2725 bool need_wrapping_integral_overflow,
2726 enum vect_reduction_type *v_reduc_type)
2728 struct loop *loop = (gimple_bb (phi))->loop_father;
2729 struct loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
2730 gimple *def_stmt, *def1 = NULL, *def2 = NULL, *phi_use_stmt = NULL;
2731 enum tree_code orig_code, code;
2732 tree op1, op2, op3 = NULL_TREE, op4 = NULL_TREE;
2733 tree type;
2734 int nloop_uses;
2735 tree name;
2736 imm_use_iterator imm_iter;
2737 use_operand_p use_p;
2738 bool phi_def;
2740 *double_reduc = false;
2741 *v_reduc_type = TREE_CODE_REDUCTION;
2743 name = PHI_RESULT (phi);
2744 /* ??? If there are no uses of the PHI result the inner loop reduction
2745 won't be detected as possibly double-reduction by vectorizable_reduction
2746 because that tries to walk the PHI arg from the preheader edge which
2747 can be constant. See PR60382. */
2748 if (has_zero_uses (name))
2749 return NULL;
2750 nloop_uses = 0;
2751 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
2753 gimple *use_stmt = USE_STMT (use_p);
2754 if (is_gimple_debug (use_stmt))
2755 continue;
2757 if (!flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
2759 if (dump_enabled_p ())
2760 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2761 "intermediate value used outside loop.\n");
2763 return NULL;
2766 nloop_uses++;
2767 if (nloop_uses > 1)
2769 if (dump_enabled_p ())
2770 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2771 "reduction value used in loop.\n");
2772 return NULL;
2775 phi_use_stmt = use_stmt;
2778 edge latch_e = loop_latch_edge (loop);
2779 tree loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
2780 if (TREE_CODE (loop_arg) != SSA_NAME)
2782 if (dump_enabled_p ())
2784 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2785 "reduction: not ssa_name: ");
2786 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, loop_arg);
2787 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
2789 return NULL;
2792 def_stmt = SSA_NAME_DEF_STMT (loop_arg);
2793 if (is_gimple_assign (def_stmt))
2795 name = gimple_assign_lhs (def_stmt);
2796 phi_def = false;
2798 else if (gimple_code (def_stmt) == GIMPLE_PHI)
2800 name = PHI_RESULT (def_stmt);
2801 phi_def = true;
2803 else
2805 if (dump_enabled_p ())
2807 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2808 "reduction: unhandled reduction operation: ");
2809 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, def_stmt, 0);
2811 return NULL;
2814 nloop_uses = 0;
2815 auto_vec<gphi *, 3> lcphis;
2816 if (flow_bb_inside_loop_p (loop, gimple_bb (def_stmt)))
2817 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
2819 gimple *use_stmt = USE_STMT (use_p);
2820 if (is_gimple_debug (use_stmt))
2821 continue;
2822 if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
2823 nloop_uses++;
2824 else
2825 /* We can have more than one loop-closed PHI. */
2826 lcphis.safe_push (as_a <gphi *> (use_stmt));
2827 if (nloop_uses > 1)
2829 if (dump_enabled_p ())
2830 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2831 "reduction used in loop.\n");
2832 return NULL;
2836 /* If DEF_STMT is a phi node itself, we expect it to have a single argument
2837 defined in the inner loop. */
2838 if (phi_def)
2840 op1 = PHI_ARG_DEF (def_stmt, 0);
2842 if (gimple_phi_num_args (def_stmt) != 1
2843 || TREE_CODE (op1) != SSA_NAME)
2845 if (dump_enabled_p ())
2846 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2847 "unsupported phi node definition.\n");
2849 return NULL;
2852 def1 = SSA_NAME_DEF_STMT (op1);
2853 if (gimple_bb (def1)
2854 && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
2855 && loop->inner
2856 && flow_bb_inside_loop_p (loop->inner, gimple_bb (def1))
2857 && is_gimple_assign (def1)
2858 && flow_bb_inside_loop_p (loop->inner, gimple_bb (phi_use_stmt)))
2860 if (dump_enabled_p ())
2861 report_vect_op (MSG_NOTE, def_stmt,
2862 "detected double reduction: ");
2864 *double_reduc = true;
2865 return def_stmt;
2868 return NULL;
2871 /* If we are vectorizing an inner reduction we are executing that
2872 in the original order only in case we are not dealing with a
2873 double reduction. */
2874 bool check_reduction = true;
2875 if (flow_loop_nested_p (vect_loop, loop))
2877 gphi *lcphi;
2878 unsigned i;
2879 check_reduction = false;
2880 FOR_EACH_VEC_ELT (lcphis, i, lcphi)
2881 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (lcphi))
2883 gimple *use_stmt = USE_STMT (use_p);
2884 if (is_gimple_debug (use_stmt))
2885 continue;
2886 if (! flow_bb_inside_loop_p (vect_loop, gimple_bb (use_stmt)))
2887 check_reduction = true;
2891 bool nested_in_vect_loop = flow_loop_nested_p (vect_loop, loop);
2892 code = orig_code = gimple_assign_rhs_code (def_stmt);
2894 /* We can handle "res -= x[i]", which is non-associative by
2895 simply rewriting this into "res += -x[i]". Avoid changing
2896 gimple instruction for the first simple tests and only do this
2897 if we're allowed to change code at all. */
2898 if (code == MINUS_EXPR
2899 && (op1 = gimple_assign_rhs1 (def_stmt))
2900 && TREE_CODE (op1) == SSA_NAME
2901 && SSA_NAME_DEF_STMT (op1) == phi)
2902 code = PLUS_EXPR;
2904 if (code == COND_EXPR)
2906 if (! nested_in_vect_loop)
2907 *v_reduc_type = COND_REDUCTION;
2909 op3 = gimple_assign_rhs1 (def_stmt);
2910 if (COMPARISON_CLASS_P (op3))
2912 op4 = TREE_OPERAND (op3, 1);
2913 op3 = TREE_OPERAND (op3, 0);
2916 op1 = gimple_assign_rhs2 (def_stmt);
2917 op2 = gimple_assign_rhs3 (def_stmt);
2919 else if (!commutative_tree_code (code) || !associative_tree_code (code))
2921 if (dump_enabled_p ())
2922 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
2923 "reduction: not commutative/associative: ");
2924 return NULL;
2926 else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
2928 op1 = gimple_assign_rhs1 (def_stmt);
2929 op2 = gimple_assign_rhs2 (def_stmt);
2931 else
2933 if (dump_enabled_p ())
2934 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
2935 "reduction: not handled operation: ");
2936 return NULL;
2939 if (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op2) != SSA_NAME)
2941 if (dump_enabled_p ())
2942 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
2943 "reduction: both uses not ssa_names: ");
2945 return NULL;
2948 type = TREE_TYPE (gimple_assign_lhs (def_stmt));
2949 if ((TREE_CODE (op1) == SSA_NAME
2950 && !types_compatible_p (type,TREE_TYPE (op1)))
2951 || (TREE_CODE (op2) == SSA_NAME
2952 && !types_compatible_p (type, TREE_TYPE (op2)))
2953 || (op3 && TREE_CODE (op3) == SSA_NAME
2954 && !types_compatible_p (type, TREE_TYPE (op3)))
2955 || (op4 && TREE_CODE (op4) == SSA_NAME
2956 && !types_compatible_p (type, TREE_TYPE (op4))))
2958 if (dump_enabled_p ())
2960 dump_printf_loc (MSG_NOTE, vect_location,
2961 "reduction: multiple types: operation type: ");
2962 dump_generic_expr (MSG_NOTE, TDF_SLIM, type);
2963 dump_printf (MSG_NOTE, ", operands types: ");
2964 dump_generic_expr (MSG_NOTE, TDF_SLIM,
2965 TREE_TYPE (op1));
2966 dump_printf (MSG_NOTE, ",");
2967 dump_generic_expr (MSG_NOTE, TDF_SLIM,
2968 TREE_TYPE (op2));
2969 if (op3)
2971 dump_printf (MSG_NOTE, ",");
2972 dump_generic_expr (MSG_NOTE, TDF_SLIM,
2973 TREE_TYPE (op3));
2976 if (op4)
2978 dump_printf (MSG_NOTE, ",");
2979 dump_generic_expr (MSG_NOTE, TDF_SLIM,
2980 TREE_TYPE (op4));
2982 dump_printf (MSG_NOTE, "\n");
2985 return NULL;
2988 /* Check that it's ok to change the order of the computation.
2989 Generally, when vectorizing a reduction we change the order of the
2990 computation. This may change the behavior of the program in some
2991 cases, so we need to check that this is ok. One exception is when
2992 vectorizing an outer-loop: the inner-loop is executed sequentially,
2993 and therefore vectorizing reductions in the inner-loop during
2994 outer-loop vectorization is safe. */
2996 if (*v_reduc_type != COND_REDUCTION
2997 && check_reduction)
2999 /* CHECKME: check for !flag_finite_math_only too? */
3000 if (SCALAR_FLOAT_TYPE_P (type) && !flag_associative_math)
3002 /* Changing the order of operations changes the semantics. */
3003 if (dump_enabled_p ())
3004 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
3005 "reduction: unsafe fp math optimization: ");
3006 return NULL;
3008 else if (INTEGRAL_TYPE_P (type))
3010 if (!operation_no_trapping_overflow (type, code))
3012 /* Changing the order of operations changes the semantics. */
3013 if (dump_enabled_p ())
3014 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
3015 "reduction: unsafe int math optimization"
3016 " (overflow traps): ");
3017 return NULL;
3019 if (need_wrapping_integral_overflow
3020 && !TYPE_OVERFLOW_WRAPS (type)
3021 && operation_can_overflow (code))
3023 /* Changing the order of operations changes the semantics. */
3024 if (dump_enabled_p ())
3025 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
3026 "reduction: unsafe int math optimization"
3027 " (overflow doesn't wrap): ");
3028 return NULL;
3031 else if (SAT_FIXED_POINT_TYPE_P (type))
3033 /* Changing the order of operations changes the semantics. */
3034 if (dump_enabled_p ())
3035 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
3036 "reduction: unsafe fixed-point math optimization: ");
3037 return NULL;
3041 /* Reduction is safe. We're dealing with one of the following:
3042 1) integer arithmetic and no trapv
3043 2) floating point arithmetic, and special flags permit this optimization
3044 3) nested cycle (i.e., outer loop vectorization). */
3045 if (TREE_CODE (op1) == SSA_NAME)
3046 def1 = SSA_NAME_DEF_STMT (op1);
3048 if (TREE_CODE (op2) == SSA_NAME)
3049 def2 = SSA_NAME_DEF_STMT (op2);
3051 if (code != COND_EXPR
3052 && ((!def1 || gimple_nop_p (def1)) && (!def2 || gimple_nop_p (def2))))
3054 if (dump_enabled_p ())
3055 report_vect_op (MSG_NOTE, def_stmt, "reduction: no defs for operands: ");
3056 return NULL;
3059 /* Check that one def is the reduction def, defined by PHI,
3060 the other def is either defined in the loop ("vect_internal_def"),
3061 or it's an induction (defined by a loop-header phi-node). */
3063 if (def2 && def2 == phi
3064 && (code == COND_EXPR
3065 || !def1 || gimple_nop_p (def1)
3066 || !flow_bb_inside_loop_p (loop, gimple_bb (def1))
3067 || (def1 && flow_bb_inside_loop_p (loop, gimple_bb (def1))
3068 && (is_gimple_assign (def1)
3069 || is_gimple_call (def1)
3070 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1))
3071 == vect_induction_def
3072 || (gimple_code (def1) == GIMPLE_PHI
3073 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1))
3074 == vect_internal_def
3075 && !is_loop_header_bb_p (gimple_bb (def1)))))))
3077 if (dump_enabled_p ())
3078 report_vect_op (MSG_NOTE, def_stmt, "detected reduction: ");
3079 return def_stmt;
3082 if (def1 && def1 == phi
3083 && (code == COND_EXPR
3084 || !def2 || gimple_nop_p (def2)
3085 || !flow_bb_inside_loop_p (loop, gimple_bb (def2))
3086 || (def2 && flow_bb_inside_loop_p (loop, gimple_bb (def2))
3087 && (is_gimple_assign (def2)
3088 || is_gimple_call (def2)
3089 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2))
3090 == vect_induction_def
3091 || (gimple_code (def2) == GIMPLE_PHI
3092 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2))
3093 == vect_internal_def
3094 && !is_loop_header_bb_p (gimple_bb (def2)))))))
3096 if (! nested_in_vect_loop && orig_code != MINUS_EXPR)
3098 /* Check if we can swap operands (just for simplicity - so that
3099 the rest of the code can assume that the reduction variable
3100 is always the last (second) argument). */
3101 if (code == COND_EXPR)
3103 /* Swap cond_expr by inverting the condition. */
3104 tree cond_expr = gimple_assign_rhs1 (def_stmt);
3105 enum tree_code invert_code = ERROR_MARK;
3106 enum tree_code cond_code = TREE_CODE (cond_expr);
3108 if (TREE_CODE_CLASS (cond_code) == tcc_comparison)
3110 bool honor_nans = HONOR_NANS (TREE_OPERAND (cond_expr, 0));
3111 invert_code = invert_tree_comparison (cond_code, honor_nans);
3113 if (invert_code != ERROR_MARK)
3115 TREE_SET_CODE (cond_expr, invert_code);
3116 swap_ssa_operands (def_stmt,
3117 gimple_assign_rhs2_ptr (def_stmt),
3118 gimple_assign_rhs3_ptr (def_stmt));
3120 else
3122 if (dump_enabled_p ())
3123 report_vect_op (MSG_NOTE, def_stmt,
3124 "detected reduction: cannot swap operands "
3125 "for cond_expr");
3126 return NULL;
3129 else
3130 swap_ssa_operands (def_stmt, gimple_assign_rhs1_ptr (def_stmt),
3131 gimple_assign_rhs2_ptr (def_stmt));
3133 if (dump_enabled_p ())
3134 report_vect_op (MSG_NOTE, def_stmt,
3135 "detected reduction: need to swap operands: ");
3137 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (def_stmt)))
3138 LOOP_VINFO_OPERANDS_SWAPPED (loop_info) = true;
3140 else
3142 if (dump_enabled_p ())
3143 report_vect_op (MSG_NOTE, def_stmt, "detected reduction: ");
3146 return def_stmt;
3149 /* Try to find SLP reduction chain. */
3150 if (! nested_in_vect_loop
3151 && code != COND_EXPR
3152 && vect_is_slp_reduction (loop_info, phi, def_stmt))
3154 if (dump_enabled_p ())
3155 report_vect_op (MSG_NOTE, def_stmt,
3156 "reduction: detected reduction chain: ");
3158 return def_stmt;
3161 if (dump_enabled_p ())
3162 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
3163 "reduction: unknown pattern: ");
3165 return NULL;
3168 /* Wrapper around vect_is_simple_reduction, which will modify code
3169 in-place if it enables detection of more reductions. Arguments
3170 as there. */
3172 gimple *
3173 vect_force_simple_reduction (loop_vec_info loop_info, gimple *phi,
3174 bool *double_reduc,
3175 bool need_wrapping_integral_overflow)
3177 enum vect_reduction_type v_reduc_type;
3178 gimple *def = vect_is_simple_reduction (loop_info, phi, double_reduc,
3179 need_wrapping_integral_overflow,
3180 &v_reduc_type);
3181 if (def)
3183 stmt_vec_info reduc_def_info = vinfo_for_stmt (phi);
3184 STMT_VINFO_REDUC_TYPE (reduc_def_info) = v_reduc_type;
3185 STMT_VINFO_REDUC_DEF (reduc_def_info) = def;
3187 return def;
3190 /* Calculate cost of peeling the loop PEEL_ITERS_PROLOGUE times. */
3192 vect_get_known_peeling_cost (loop_vec_info loop_vinfo, int peel_iters_prologue,
3193 int *peel_iters_epilogue,
3194 stmt_vector_for_cost *scalar_cost_vec,
3195 stmt_vector_for_cost *prologue_cost_vec,
3196 stmt_vector_for_cost *epilogue_cost_vec)
3198 int retval = 0;
3199 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
3201 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
3203 *peel_iters_epilogue = vf/2;
3204 if (dump_enabled_p ())
3205 dump_printf_loc (MSG_NOTE, vect_location,
3206 "cost model: epilogue peel iters set to vf/2 "
3207 "because loop iterations are unknown .\n");
3209 /* If peeled iterations are known but number of scalar loop
3210 iterations are unknown, count a taken branch per peeled loop. */
3211 retval = record_stmt_cost (prologue_cost_vec, 1, cond_branch_taken,
3212 NULL, 0, vect_prologue);
3213 retval = record_stmt_cost (prologue_cost_vec, 1, cond_branch_taken,
3214 NULL, 0, vect_epilogue);
3216 else
3218 int niters = LOOP_VINFO_INT_NITERS (loop_vinfo);
3219 peel_iters_prologue = niters < peel_iters_prologue ?
3220 niters : peel_iters_prologue;
3221 *peel_iters_epilogue = (niters - peel_iters_prologue) % vf;
3222 /* If we need to peel for gaps, but no peeling is required, we have to
3223 peel VF iterations. */
3224 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo) && !*peel_iters_epilogue)
3225 *peel_iters_epilogue = vf;
3228 stmt_info_for_cost *si;
3229 int j;
3230 if (peel_iters_prologue)
3231 FOR_EACH_VEC_ELT (*scalar_cost_vec, j, si)
3233 stmt_vec_info stmt_info
3234 = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
3235 retval += record_stmt_cost (prologue_cost_vec,
3236 si->count * peel_iters_prologue,
3237 si->kind, stmt_info, si->misalign,
3238 vect_prologue);
3240 if (*peel_iters_epilogue)
3241 FOR_EACH_VEC_ELT (*scalar_cost_vec, j, si)
3243 stmt_vec_info stmt_info
3244 = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
3245 retval += record_stmt_cost (epilogue_cost_vec,
3246 si->count * *peel_iters_epilogue,
3247 si->kind, stmt_info, si->misalign,
3248 vect_epilogue);
3251 return retval;
3254 /* Function vect_estimate_min_profitable_iters
3256 Return the number of iterations required for the vector version of the
3257 loop to be profitable relative to the cost of the scalar version of the
3258 loop.
3260 *RET_MIN_PROFITABLE_NITERS is a cost model profitability threshold
3261 of iterations for vectorization. -1 value means loop vectorization
3262 is not profitable. This returned value may be used for dynamic
3263 profitability check.
3265 *RET_MIN_PROFITABLE_ESTIMATE is a profitability threshold to be used
3266 for static check against estimated number of iterations. */
3268 static void
3269 vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo,
3270 int *ret_min_profitable_niters,
3271 int *ret_min_profitable_estimate)
3273 int min_profitable_iters;
3274 int min_profitable_estimate;
3275 int peel_iters_prologue;
3276 int peel_iters_epilogue;
3277 unsigned vec_inside_cost = 0;
3278 int vec_outside_cost = 0;
3279 unsigned vec_prologue_cost = 0;
3280 unsigned vec_epilogue_cost = 0;
3281 int scalar_single_iter_cost = 0;
3282 int scalar_outside_cost = 0;
3283 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
3284 int npeel = LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo);
3285 void *target_cost_data = LOOP_VINFO_TARGET_COST_DATA (loop_vinfo);
3287 /* Cost model disabled. */
3288 if (unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo)))
3290 dump_printf_loc (MSG_NOTE, vect_location, "cost model disabled.\n");
3291 *ret_min_profitable_niters = 0;
3292 *ret_min_profitable_estimate = 0;
3293 return;
3296 /* Requires loop versioning tests to handle misalignment. */
3297 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo))
3299 /* FIXME: Make cost depend on complexity of individual check. */
3300 unsigned len = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).length ();
3301 (void) add_stmt_cost (target_cost_data, len, vector_stmt, NULL, 0,
3302 vect_prologue);
3303 dump_printf (MSG_NOTE,
3304 "cost model: Adding cost of checks for loop "
3305 "versioning to treat misalignment.\n");
3308 /* Requires loop versioning with alias checks. */
3309 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
3311 /* FIXME: Make cost depend on complexity of individual check. */
3312 unsigned len = LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo).length ();
3313 (void) add_stmt_cost (target_cost_data, len, vector_stmt, NULL, 0,
3314 vect_prologue);
3315 dump_printf (MSG_NOTE,
3316 "cost model: Adding cost of checks for loop "
3317 "versioning aliasing.\n");
3320 /* Requires loop versioning with niter checks. */
3321 if (LOOP_REQUIRES_VERSIONING_FOR_NITERS (loop_vinfo))
3323 /* FIXME: Make cost depend on complexity of individual check. */
3324 (void) add_stmt_cost (target_cost_data, 1, vector_stmt, NULL, 0,
3325 vect_prologue);
3326 dump_printf (MSG_NOTE,
3327 "cost model: Adding cost of checks for loop "
3328 "versioning niters.\n");
3331 if (LOOP_REQUIRES_VERSIONING (loop_vinfo))
3332 (void) add_stmt_cost (target_cost_data, 1, cond_branch_taken, NULL, 0,
3333 vect_prologue);
3335 /* Count statements in scalar loop. Using this as scalar cost for a single
3336 iteration for now.
3338 TODO: Add outer loop support.
3340 TODO: Consider assigning different costs to different scalar
3341 statements. */
3343 scalar_single_iter_cost
3344 = LOOP_VINFO_SINGLE_SCALAR_ITERATION_COST (loop_vinfo);
3346 /* Add additional cost for the peeled instructions in prologue and epilogue
3347 loop.
3349 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
3350 at compile-time - we assume it's vf/2 (the worst would be vf-1).
3352 TODO: Build an expression that represents peel_iters for prologue and
3353 epilogue to be used in a run-time test. */
3355 if (npeel < 0)
3357 peel_iters_prologue = vf/2;
3358 dump_printf (MSG_NOTE, "cost model: "
3359 "prologue peel iters set to vf/2.\n");
3361 /* If peeling for alignment is unknown, loop bound of main loop becomes
3362 unknown. */
3363 peel_iters_epilogue = vf/2;
3364 dump_printf (MSG_NOTE, "cost model: "
3365 "epilogue peel iters set to vf/2 because "
3366 "peeling for alignment is unknown.\n");
3368 /* If peeled iterations are unknown, count a taken branch and a not taken
3369 branch per peeled loop. Even if scalar loop iterations are known,
3370 vector iterations are not known since peeled prologue iterations are
3371 not known. Hence guards remain the same. */
3372 (void) add_stmt_cost (target_cost_data, 1, cond_branch_taken,
3373 NULL, 0, vect_prologue);
3374 (void) add_stmt_cost (target_cost_data, 1, cond_branch_not_taken,
3375 NULL, 0, vect_prologue);
3376 (void) add_stmt_cost (target_cost_data, 1, cond_branch_taken,
3377 NULL, 0, vect_epilogue);
3378 (void) add_stmt_cost (target_cost_data, 1, cond_branch_not_taken,
3379 NULL, 0, vect_epilogue);
3380 stmt_info_for_cost *si;
3381 int j;
3382 FOR_EACH_VEC_ELT (LOOP_VINFO_SCALAR_ITERATION_COST (loop_vinfo), j, si)
3384 struct _stmt_vec_info *stmt_info
3385 = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
3386 (void) add_stmt_cost (target_cost_data,
3387 si->count * peel_iters_prologue,
3388 si->kind, stmt_info, si->misalign,
3389 vect_prologue);
3390 (void) add_stmt_cost (target_cost_data,
3391 si->count * peel_iters_epilogue,
3392 si->kind, stmt_info, si->misalign,
3393 vect_epilogue);
3396 else
3398 stmt_vector_for_cost prologue_cost_vec, epilogue_cost_vec;
3399 stmt_info_for_cost *si;
3400 int j;
3401 void *data = LOOP_VINFO_TARGET_COST_DATA (loop_vinfo);
3403 prologue_cost_vec.create (2);
3404 epilogue_cost_vec.create (2);
3405 peel_iters_prologue = npeel;
3407 (void) vect_get_known_peeling_cost (loop_vinfo, peel_iters_prologue,
3408 &peel_iters_epilogue,
3409 &LOOP_VINFO_SCALAR_ITERATION_COST
3410 (loop_vinfo),
3411 &prologue_cost_vec,
3412 &epilogue_cost_vec);
3414 FOR_EACH_VEC_ELT (prologue_cost_vec, j, si)
3416 struct _stmt_vec_info *stmt_info
3417 = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
3418 (void) add_stmt_cost (data, si->count, si->kind, stmt_info,
3419 si->misalign, vect_prologue);
3422 FOR_EACH_VEC_ELT (epilogue_cost_vec, j, si)
3424 struct _stmt_vec_info *stmt_info
3425 = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
3426 (void) add_stmt_cost (data, si->count, si->kind, stmt_info,
3427 si->misalign, vect_epilogue);
3430 prologue_cost_vec.release ();
3431 epilogue_cost_vec.release ();
3434 /* FORNOW: The scalar outside cost is incremented in one of the
3435 following ways:
3437 1. The vectorizer checks for alignment and aliasing and generates
3438 a condition that allows dynamic vectorization. A cost model
3439 check is ANDED with the versioning condition. Hence scalar code
3440 path now has the added cost of the versioning check.
3442 if (cost > th & versioning_check)
3443 jmp to vector code
3445 Hence run-time scalar is incremented by not-taken branch cost.
3447 2. The vectorizer then checks if a prologue is required. If the
3448 cost model check was not done before during versioning, it has to
3449 be done before the prologue check.
3451 if (cost <= th)
3452 prologue = scalar_iters
3453 if (prologue == 0)
3454 jmp to vector code
3455 else
3456 execute prologue
3457 if (prologue == num_iters)
3458 go to exit
3460 Hence the run-time scalar cost is incremented by a taken branch,
3461 plus a not-taken branch, plus a taken branch cost.
3463 3. The vectorizer then checks if an epilogue is required. If the
3464 cost model check was not done before during prologue check, it
3465 has to be done with the epilogue check.
3467 if (prologue == 0)
3468 jmp to vector code
3469 else
3470 execute prologue
3471 if (prologue == num_iters)
3472 go to exit
3473 vector code:
3474 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
3475 jmp to epilogue
3477 Hence the run-time scalar cost should be incremented by 2 taken
3478 branches.
3480 TODO: The back end may reorder the BBS's differently and reverse
3481 conditions/branch directions. Change the estimates below to
3482 something more reasonable. */
3484 /* If the number of iterations is known and we do not do versioning, we can
3485 decide whether to vectorize at compile time. Hence the scalar version
3486 do not carry cost model guard costs. */
3487 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
3488 || LOOP_REQUIRES_VERSIONING (loop_vinfo))
3490 /* Cost model check occurs at versioning. */
3491 if (LOOP_REQUIRES_VERSIONING (loop_vinfo))
3492 scalar_outside_cost += vect_get_stmt_cost (cond_branch_not_taken);
3493 else
3495 /* Cost model check occurs at prologue generation. */
3496 if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0)
3497 scalar_outside_cost += 2 * vect_get_stmt_cost (cond_branch_taken)
3498 + vect_get_stmt_cost (cond_branch_not_taken);
3499 /* Cost model check occurs at epilogue generation. */
3500 else
3501 scalar_outside_cost += 2 * vect_get_stmt_cost (cond_branch_taken);
3505 /* Complete the target-specific cost calculations. */
3506 finish_cost (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo), &vec_prologue_cost,
3507 &vec_inside_cost, &vec_epilogue_cost);
3509 vec_outside_cost = (int)(vec_prologue_cost + vec_epilogue_cost);
3511 if (dump_enabled_p ())
3513 dump_printf_loc (MSG_NOTE, vect_location, "Cost model analysis: \n");
3514 dump_printf (MSG_NOTE, " Vector inside of loop cost: %d\n",
3515 vec_inside_cost);
3516 dump_printf (MSG_NOTE, " Vector prologue cost: %d\n",
3517 vec_prologue_cost);
3518 dump_printf (MSG_NOTE, " Vector epilogue cost: %d\n",
3519 vec_epilogue_cost);
3520 dump_printf (MSG_NOTE, " Scalar iteration cost: %d\n",
3521 scalar_single_iter_cost);
3522 dump_printf (MSG_NOTE, " Scalar outside cost: %d\n",
3523 scalar_outside_cost);
3524 dump_printf (MSG_NOTE, " Vector outside cost: %d\n",
3525 vec_outside_cost);
3526 dump_printf (MSG_NOTE, " prologue iterations: %d\n",
3527 peel_iters_prologue);
3528 dump_printf (MSG_NOTE, " epilogue iterations: %d\n",
3529 peel_iters_epilogue);
3532 /* Calculate number of iterations required to make the vector version
3533 profitable, relative to the loop bodies only. The following condition
3534 must hold true:
3535 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
3536 where
3537 SIC = scalar iteration cost, VIC = vector iteration cost,
3538 VOC = vector outside cost, VF = vectorization factor,
3539 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
3540 SOC = scalar outside cost for run time cost model check. */
3542 if ((scalar_single_iter_cost * vf) > (int) vec_inside_cost)
3544 if (vec_outside_cost <= 0)
3545 min_profitable_iters = 1;
3546 else
3548 min_profitable_iters = ((vec_outside_cost - scalar_outside_cost) * vf
3549 - vec_inside_cost * peel_iters_prologue
3550 - vec_inside_cost * peel_iters_epilogue)
3551 / ((scalar_single_iter_cost * vf)
3552 - vec_inside_cost);
3554 if ((scalar_single_iter_cost * vf * min_profitable_iters)
3555 <= (((int) vec_inside_cost * min_profitable_iters)
3556 + (((int) vec_outside_cost - scalar_outside_cost) * vf)))
3557 min_profitable_iters++;
3560 /* vector version will never be profitable. */
3561 else
3563 if (LOOP_VINFO_LOOP (loop_vinfo)->force_vectorize)
3564 warning_at (vect_location, OPT_Wopenmp_simd, "vectorization "
3565 "did not happen for a simd loop");
3567 if (dump_enabled_p ())
3568 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3569 "cost model: the vector iteration cost = %d "
3570 "divided by the scalar iteration cost = %d "
3571 "is greater or equal to the vectorization factor = %d"
3572 ".\n",
3573 vec_inside_cost, scalar_single_iter_cost, vf);
3574 *ret_min_profitable_niters = -1;
3575 *ret_min_profitable_estimate = -1;
3576 return;
3579 dump_printf (MSG_NOTE,
3580 " Calculated minimum iters for profitability: %d\n",
3581 min_profitable_iters);
3583 min_profitable_iters =
3584 min_profitable_iters < vf ? vf : min_profitable_iters;
3586 /* Because the condition we create is:
3587 if (niters <= min_profitable_iters)
3588 then skip the vectorized loop. */
3589 min_profitable_iters--;
3591 if (dump_enabled_p ())
3592 dump_printf_loc (MSG_NOTE, vect_location,
3593 " Runtime profitability threshold = %d\n",
3594 min_profitable_iters);
3596 *ret_min_profitable_niters = min_profitable_iters;
3598 /* Calculate number of iterations required to make the vector version
3599 profitable, relative to the loop bodies only.
3601 Non-vectorized variant is SIC * niters and it must win over vector
3602 variant on the expected loop trip count. The following condition must hold true:
3603 SIC * niters > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC + SOC */
3605 if (vec_outside_cost <= 0)
3606 min_profitable_estimate = 1;
3607 else
3609 min_profitable_estimate = ((vec_outside_cost + scalar_outside_cost) * vf
3610 - vec_inside_cost * peel_iters_prologue
3611 - vec_inside_cost * peel_iters_epilogue)
3612 / ((scalar_single_iter_cost * vf)
3613 - vec_inside_cost);
3615 min_profitable_estimate --;
3616 min_profitable_estimate = MAX (min_profitable_estimate, min_profitable_iters);
3617 if (dump_enabled_p ())
3618 dump_printf_loc (MSG_NOTE, vect_location,
3619 " Static estimate profitability threshold = %d\n",
3620 min_profitable_estimate);
3622 *ret_min_profitable_estimate = min_profitable_estimate;
3625 /* Writes into SEL a mask for a vec_perm, equivalent to a vec_shr by OFFSET
3626 vector elements (not bits) for a vector of mode MODE. */
3627 static void
3628 calc_vec_perm_mask_for_shift (enum machine_mode mode, unsigned int offset,
3629 unsigned char *sel)
3631 unsigned int i, nelt = GET_MODE_NUNITS (mode);
3633 for (i = 0; i < nelt; i++)
3634 sel[i] = (i + offset) & (2*nelt - 1);
3637 /* Checks whether the target supports whole-vector shifts for vectors of mode
3638 MODE. This is the case if _either_ the platform handles vec_shr_optab, _or_
3639 it supports vec_perm_const with masks for all necessary shift amounts. */
3640 static bool
3641 have_whole_vector_shift (enum machine_mode mode)
3643 if (optab_handler (vec_shr_optab, mode) != CODE_FOR_nothing)
3644 return true;
3646 if (direct_optab_handler (vec_perm_const_optab, mode) == CODE_FOR_nothing)
3647 return false;
3649 unsigned int i, nelt = GET_MODE_NUNITS (mode);
3650 unsigned char *sel = XALLOCAVEC (unsigned char, nelt);
3652 for (i = nelt/2; i >= 1; i/=2)
3654 calc_vec_perm_mask_for_shift (mode, i, sel);
3655 if (!can_vec_perm_p (mode, false, sel))
3656 return false;
3658 return true;
3661 /* Return the reduction operand (with index REDUC_INDEX) of STMT. */
3663 static tree
3664 get_reduction_op (gimple *stmt, int reduc_index)
3666 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
3668 case GIMPLE_SINGLE_RHS:
3669 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt))
3670 == ternary_op);
3671 return TREE_OPERAND (gimple_assign_rhs1 (stmt), reduc_index);
3672 case GIMPLE_UNARY_RHS:
3673 return gimple_assign_rhs1 (stmt);
3674 case GIMPLE_BINARY_RHS:
3675 return (reduc_index
3676 ? gimple_assign_rhs2 (stmt) : gimple_assign_rhs1 (stmt));
3677 case GIMPLE_TERNARY_RHS:
3678 return gimple_op (stmt, reduc_index + 1);
3679 default:
3680 gcc_unreachable ();
3684 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
3685 functions. Design better to avoid maintenance issues. */
3687 /* Function vect_model_reduction_cost.
3689 Models cost for a reduction operation, including the vector ops
3690 generated within the strip-mine loop, the initial definition before
3691 the loop, and the epilogue code that must be generated. */
3693 static void
3694 vect_model_reduction_cost (stmt_vec_info stmt_info, enum tree_code reduc_code,
3695 int ncopies)
3697 int prologue_cost = 0, epilogue_cost = 0;
3698 enum tree_code code;
3699 optab optab;
3700 tree vectype;
3701 gimple *orig_stmt;
3702 machine_mode mode;
3703 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3704 struct loop *loop = NULL;
3705 void *target_cost_data;
3707 if (loop_vinfo)
3709 loop = LOOP_VINFO_LOOP (loop_vinfo);
3710 target_cost_data = LOOP_VINFO_TARGET_COST_DATA (loop_vinfo);
3712 else
3713 target_cost_data = BB_VINFO_TARGET_COST_DATA (STMT_VINFO_BB_VINFO (stmt_info));
3715 /* Condition reductions generate two reductions in the loop. */
3716 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION)
3717 ncopies *= 2;
3719 /* Cost of reduction op inside loop. */
3720 unsigned inside_cost = add_stmt_cost (target_cost_data, ncopies, vector_stmt,
3721 stmt_info, 0, vect_body);
3723 vectype = STMT_VINFO_VECTYPE (stmt_info);
3724 mode = TYPE_MODE (vectype);
3725 orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
3727 if (!orig_stmt)
3728 orig_stmt = STMT_VINFO_STMT (stmt_info);
3730 code = gimple_assign_rhs_code (orig_stmt);
3732 /* Add in cost for initial definition.
3733 For cond reduction we have four vectors: initial index, step, initial
3734 result of the data reduction, initial value of the index reduction. */
3735 int prologue_stmts = STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
3736 == COND_REDUCTION ? 4 : 1;
3737 prologue_cost += add_stmt_cost (target_cost_data, prologue_stmts,
3738 scalar_to_vec, stmt_info, 0,
3739 vect_prologue);
3741 /* Determine cost of epilogue code.
3743 We have a reduction operator that will reduce the vector in one statement.
3744 Also requires scalar extract. */
3746 if (!loop || !nested_in_vect_loop_p (loop, orig_stmt))
3748 if (reduc_code != ERROR_MARK)
3750 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION)
3752 /* An EQ stmt and an COND_EXPR stmt. */
3753 epilogue_cost += add_stmt_cost (target_cost_data, 2,
3754 vector_stmt, stmt_info, 0,
3755 vect_epilogue);
3756 /* Reduction of the max index and a reduction of the found
3757 values. */
3758 epilogue_cost += add_stmt_cost (target_cost_data, 2,
3759 vec_to_scalar, stmt_info, 0,
3760 vect_epilogue);
3761 /* A broadcast of the max value. */
3762 epilogue_cost += add_stmt_cost (target_cost_data, 1,
3763 scalar_to_vec, stmt_info, 0,
3764 vect_epilogue);
3766 else
3768 epilogue_cost += add_stmt_cost (target_cost_data, 1, vector_stmt,
3769 stmt_info, 0, vect_epilogue);
3770 epilogue_cost += add_stmt_cost (target_cost_data, 1,
3771 vec_to_scalar, stmt_info, 0,
3772 vect_epilogue);
3775 else
3777 int vec_size_in_bits = tree_to_uhwi (TYPE_SIZE (vectype));
3778 tree bitsize =
3779 TYPE_SIZE (TREE_TYPE (gimple_assign_lhs (orig_stmt)));
3780 int element_bitsize = tree_to_uhwi (bitsize);
3781 int nelements = vec_size_in_bits / element_bitsize;
3783 optab = optab_for_tree_code (code, vectype, optab_default);
3785 /* We have a whole vector shift available. */
3786 if (VECTOR_MODE_P (mode)
3787 && optab_handler (optab, mode) != CODE_FOR_nothing
3788 && have_whole_vector_shift (mode))
3790 /* Final reduction via vector shifts and the reduction operator.
3791 Also requires scalar extract. */
3792 epilogue_cost += add_stmt_cost (target_cost_data,
3793 exact_log2 (nelements) * 2,
3794 vector_stmt, stmt_info, 0,
3795 vect_epilogue);
3796 epilogue_cost += add_stmt_cost (target_cost_data, 1,
3797 vec_to_scalar, stmt_info, 0,
3798 vect_epilogue);
3800 else
3801 /* Use extracts and reduction op for final reduction. For N
3802 elements, we have N extracts and N-1 reduction ops. */
3803 epilogue_cost += add_stmt_cost (target_cost_data,
3804 nelements + nelements - 1,
3805 vector_stmt, stmt_info, 0,
3806 vect_epilogue);
3810 if (dump_enabled_p ())
3811 dump_printf (MSG_NOTE,
3812 "vect_model_reduction_cost: inside_cost = %d, "
3813 "prologue_cost = %d, epilogue_cost = %d .\n", inside_cost,
3814 prologue_cost, epilogue_cost);
3818 /* Function vect_model_induction_cost.
3820 Models cost for induction operations. */
3822 static void
3823 vect_model_induction_cost (stmt_vec_info stmt_info, int ncopies)
3825 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3826 void *target_cost_data = LOOP_VINFO_TARGET_COST_DATA (loop_vinfo);
3827 unsigned inside_cost, prologue_cost;
3829 if (PURE_SLP_STMT (stmt_info))
3830 return;
3832 /* loop cost for vec_loop. */
3833 inside_cost = add_stmt_cost (target_cost_data, ncopies, vector_stmt,
3834 stmt_info, 0, vect_body);
3836 /* prologue cost for vec_init and vec_step. */
3837 prologue_cost = add_stmt_cost (target_cost_data, 2, scalar_to_vec,
3838 stmt_info, 0, vect_prologue);
3840 if (dump_enabled_p ())
3841 dump_printf_loc (MSG_NOTE, vect_location,
3842 "vect_model_induction_cost: inside_cost = %d, "
3843 "prologue_cost = %d .\n", inside_cost, prologue_cost);
3848 /* Function get_initial_def_for_reduction
3850 Input:
3851 STMT - a stmt that performs a reduction operation in the loop.
3852 INIT_VAL - the initial value of the reduction variable
3854 Output:
3855 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
3856 of the reduction (used for adjusting the epilog - see below).
3857 Return a vector variable, initialized according to the operation that STMT
3858 performs. This vector will be used as the initial value of the
3859 vector of partial results.
3861 Option1 (adjust in epilog): Initialize the vector as follows:
3862 add/bit or/xor: [0,0,...,0,0]
3863 mult/bit and: [1,1,...,1,1]
3864 min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
3865 and when necessary (e.g. add/mult case) let the caller know
3866 that it needs to adjust the result by init_val.
3868 Option2: Initialize the vector as follows:
3869 add/bit or/xor: [init_val,0,0,...,0]
3870 mult/bit and: [init_val,1,1,...,1]
3871 min/max/cond_expr: [init_val,init_val,...,init_val]
3872 and no adjustments are needed.
3874 For example, for the following code:
3876 s = init_val;
3877 for (i=0;i<n;i++)
3878 s = s + a[i];
3880 STMT is 's = s + a[i]', and the reduction variable is 's'.
3881 For a vector of 4 units, we want to return either [0,0,0,init_val],
3882 or [0,0,0,0] and let the caller know that it needs to adjust
3883 the result at the end by 'init_val'.
3885 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
3886 initialization vector is simpler (same element in all entries), if
3887 ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
3889 A cost model should help decide between these two schemes. */
3891 tree
3892 get_initial_def_for_reduction (gimple *stmt, tree init_val,
3893 tree *adjustment_def)
3895 stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
3896 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
3897 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
3898 tree scalar_type = TREE_TYPE (init_val);
3899 tree vectype = get_vectype_for_scalar_type (scalar_type);
3900 int nunits;
3901 enum tree_code code = gimple_assign_rhs_code (stmt);
3902 tree def_for_init;
3903 tree init_def;
3904 tree *elts;
3905 int i;
3906 bool nested_in_vect_loop = false;
3907 REAL_VALUE_TYPE real_init_val = dconst0;
3908 int int_init_val = 0;
3909 gimple *def_stmt = NULL;
3910 gimple_seq stmts = NULL;
3912 gcc_assert (vectype);
3913 nunits = TYPE_VECTOR_SUBPARTS (vectype);
3915 gcc_assert (POINTER_TYPE_P (scalar_type) || INTEGRAL_TYPE_P (scalar_type)
3916 || SCALAR_FLOAT_TYPE_P (scalar_type));
3918 if (nested_in_vect_loop_p (loop, stmt))
3919 nested_in_vect_loop = true;
3920 else
3921 gcc_assert (loop == (gimple_bb (stmt))->loop_father);
3923 /* In case of double reduction we only create a vector variable to be put
3924 in the reduction phi node. The actual statement creation is done in
3925 vect_create_epilog_for_reduction. */
3926 if (adjustment_def && nested_in_vect_loop
3927 && TREE_CODE (init_val) == SSA_NAME
3928 && (def_stmt = SSA_NAME_DEF_STMT (init_val))
3929 && gimple_code (def_stmt) == GIMPLE_PHI
3930 && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
3931 && vinfo_for_stmt (def_stmt)
3932 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
3933 == vect_double_reduction_def)
3935 *adjustment_def = NULL;
3936 return vect_create_destination_var (init_val, vectype);
3939 /* In case of a nested reduction do not use an adjustment def as
3940 that case is not supported by the epilogue generation correctly
3941 if ncopies is not one. */
3942 if (adjustment_def && nested_in_vect_loop)
3944 *adjustment_def = NULL;
3945 return vect_get_vec_def_for_operand (init_val, stmt);
3948 switch (code)
3950 case WIDEN_SUM_EXPR:
3951 case DOT_PROD_EXPR:
3952 case SAD_EXPR:
3953 case PLUS_EXPR:
3954 case MINUS_EXPR:
3955 case BIT_IOR_EXPR:
3956 case BIT_XOR_EXPR:
3957 case MULT_EXPR:
3958 case BIT_AND_EXPR:
3959 /* ADJUSMENT_DEF is NULL when called from
3960 vect_create_epilog_for_reduction to vectorize double reduction. */
3961 if (adjustment_def)
3962 *adjustment_def = init_val;
3964 if (code == MULT_EXPR)
3966 real_init_val = dconst1;
3967 int_init_val = 1;
3970 if (code == BIT_AND_EXPR)
3971 int_init_val = -1;
3973 if (SCALAR_FLOAT_TYPE_P (scalar_type))
3974 def_for_init = build_real (scalar_type, real_init_val);
3975 else
3976 def_for_init = build_int_cst (scalar_type, int_init_val);
3978 /* Create a vector of '0' or '1' except the first element. */
3979 elts = XALLOCAVEC (tree, nunits);
3980 for (i = nunits - 2; i >= 0; --i)
3981 elts[i + 1] = def_for_init;
3983 /* Option1: the first element is '0' or '1' as well. */
3984 if (adjustment_def)
3986 elts[0] = def_for_init;
3987 init_def = build_vector (vectype, elts);
3988 break;
3991 /* Option2: the first element is INIT_VAL. */
3992 elts[0] = init_val;
3993 if (TREE_CONSTANT (init_val))
3994 init_def = build_vector (vectype, elts);
3995 else
3997 vec<constructor_elt, va_gc> *v;
3998 vec_alloc (v, nunits);
3999 CONSTRUCTOR_APPEND_ELT (v, NULL_TREE, init_val);
4000 for (i = 1; i < nunits; ++i)
4001 CONSTRUCTOR_APPEND_ELT (v, NULL_TREE, elts[i]);
4002 init_def = build_constructor (vectype, v);
4005 break;
4007 case MIN_EXPR:
4008 case MAX_EXPR:
4009 case COND_EXPR:
4010 if (adjustment_def)
4012 *adjustment_def = NULL_TREE;
4013 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_vinfo) != COND_REDUCTION)
4015 init_def = vect_get_vec_def_for_operand (init_val, stmt);
4016 break;
4019 init_val = gimple_convert (&stmts, TREE_TYPE (vectype), init_val);
4020 if (! gimple_seq_empty_p (stmts))
4021 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
4022 init_def = build_vector_from_val (vectype, init_val);
4023 break;
4025 default:
4026 gcc_unreachable ();
4029 return init_def;
4032 /* Function vect_create_epilog_for_reduction
4034 Create code at the loop-epilog to finalize the result of a reduction
4035 computation.
4037 VECT_DEFS is list of vector of partial results, i.e., the lhs's of vector
4038 reduction statements.
4039 STMT is the scalar reduction stmt that is being vectorized.
4040 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
4041 number of elements that we can fit in a vectype (nunits). In this case
4042 we have to generate more than one vector stmt - i.e - we need to "unroll"
4043 the vector stmt by a factor VF/nunits. For more details see documentation
4044 in vectorizable_operation.
4045 REDUC_CODE is the tree-code for the epilog reduction.
4046 REDUCTION_PHIS is a list of the phi-nodes that carry the reduction
4047 computation.
4048 REDUC_INDEX is the index of the operand in the right hand side of the
4049 statement that is defined by REDUCTION_PHI.
4050 DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
4051 SLP_NODE is an SLP node containing a group of reduction statements. The
4052 first one in this group is STMT.
4053 INDUCTION_INDEX is the index of the loop for condition reductions.
4054 Otherwise it is undefined.
4056 This function:
4057 1. Creates the reduction def-use cycles: sets the arguments for
4058 REDUCTION_PHIS:
4059 The loop-entry argument is the vectorized initial-value of the reduction.
4060 The loop-latch argument is taken from VECT_DEFS - the vector of partial
4061 sums.
4062 2. "Reduces" each vector of partial results VECT_DEFS into a single result,
4063 by applying the operation specified by REDUC_CODE if available, or by
4064 other means (whole-vector shifts or a scalar loop).
4065 The function also creates a new phi node at the loop exit to preserve
4066 loop-closed form, as illustrated below.
4068 The flow at the entry to this function:
4070 loop:
4071 vec_def = phi <null, null> # REDUCTION_PHI
4072 VECT_DEF = vector_stmt # vectorized form of STMT
4073 s_loop = scalar_stmt # (scalar) STMT
4074 loop_exit:
4075 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4076 use <s_out0>
4077 use <s_out0>
4079 The above is transformed by this function into:
4081 loop:
4082 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
4083 VECT_DEF = vector_stmt # vectorized form of STMT
4084 s_loop = scalar_stmt # (scalar) STMT
4085 loop_exit:
4086 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4087 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4088 v_out2 = reduce <v_out1>
4089 s_out3 = extract_field <v_out2, 0>
4090 s_out4 = adjust_result <s_out3>
4091 use <s_out4>
4092 use <s_out4>
4095 static void
4096 vect_create_epilog_for_reduction (vec<tree> vect_defs, gimple *stmt,
4097 int ncopies, enum tree_code reduc_code,
4098 vec<gimple *> reduction_phis,
4099 int reduc_index, bool double_reduc,
4100 slp_tree slp_node, tree induction_index)
4102 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4103 stmt_vec_info prev_phi_info;
4104 tree vectype;
4105 machine_mode mode;
4106 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
4107 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo), *outer_loop = NULL;
4108 basic_block exit_bb;
4109 tree scalar_dest;
4110 tree scalar_type;
4111 gimple *new_phi = NULL, *phi;
4112 gimple_stmt_iterator exit_gsi;
4113 tree vec_dest;
4114 tree new_temp = NULL_TREE, new_dest, new_name, new_scalar_dest;
4115 gimple *epilog_stmt = NULL;
4116 enum tree_code code = gimple_assign_rhs_code (stmt);
4117 gimple *exit_phi;
4118 tree bitsize;
4119 tree adjustment_def = NULL;
4120 tree vec_initial_def = NULL;
4121 tree reduction_op, expr, def, initial_def = NULL;
4122 tree orig_name, scalar_result;
4123 imm_use_iterator imm_iter, phi_imm_iter;
4124 use_operand_p use_p, phi_use_p;
4125 gimple *use_stmt, *orig_stmt, *reduction_phi = NULL;
4126 bool nested_in_vect_loop = false;
4127 auto_vec<gimple *> new_phis;
4128 auto_vec<gimple *> inner_phis;
4129 enum vect_def_type dt = vect_unknown_def_type;
4130 int j, i;
4131 auto_vec<tree> scalar_results;
4132 unsigned int group_size = 1, k, ratio;
4133 auto_vec<tree> vec_initial_defs;
4134 auto_vec<gimple *> phis;
4135 bool slp_reduc = false;
4136 tree new_phi_result;
4137 gimple *inner_phi = NULL;
4139 if (slp_node)
4140 group_size = SLP_TREE_SCALAR_STMTS (slp_node).length ();
4142 if (nested_in_vect_loop_p (loop, stmt))
4144 outer_loop = loop;
4145 loop = loop->inner;
4146 nested_in_vect_loop = true;
4147 gcc_assert (!slp_node);
4150 reduction_op = get_reduction_op (stmt, reduc_index);
4152 vectype = get_vectype_for_scalar_type (TREE_TYPE (reduction_op));
4153 gcc_assert (vectype);
4154 mode = TYPE_MODE (vectype);
4156 /* 1. Create the reduction def-use cycle:
4157 Set the arguments of REDUCTION_PHIS, i.e., transform
4159 loop:
4160 vec_def = phi <null, null> # REDUCTION_PHI
4161 VECT_DEF = vector_stmt # vectorized form of STMT
4164 into:
4166 loop:
4167 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
4168 VECT_DEF = vector_stmt # vectorized form of STMT
4171 (in case of SLP, do it for all the phis). */
4173 /* Get the loop-entry arguments. */
4174 enum vect_def_type initial_def_dt = vect_unknown_def_type;
4175 if (slp_node)
4176 vect_get_vec_defs (reduction_op, NULL_TREE, stmt, &vec_initial_defs,
4177 NULL, slp_node, reduc_index);
4178 else
4180 /* Get at the scalar def before the loop, that defines the initial value
4181 of the reduction variable. */
4182 gimple *def_stmt = SSA_NAME_DEF_STMT (reduction_op);
4183 initial_def = PHI_ARG_DEF_FROM_EDGE (def_stmt,
4184 loop_preheader_edge (loop));
4185 vect_is_simple_use (initial_def, loop_vinfo, &def_stmt, &initial_def_dt);
4186 vec_initial_def = get_initial_def_for_reduction (stmt, initial_def,
4187 &adjustment_def);
4188 vec_initial_defs.create (1);
4189 vec_initial_defs.quick_push (vec_initial_def);
4192 /* Set phi nodes arguments. */
4193 FOR_EACH_VEC_ELT (reduction_phis, i, phi)
4195 tree vec_init_def, def;
4196 gimple_seq stmts;
4197 vec_init_def = force_gimple_operand (vec_initial_defs[i], &stmts,
4198 true, NULL_TREE);
4199 if (stmts)
4200 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
4202 def = vect_defs[i];
4203 for (j = 0; j < ncopies; j++)
4205 if (j != 0)
4207 phi = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi));
4208 if (nested_in_vect_loop)
4209 vec_init_def
4210 = vect_get_vec_def_for_stmt_copy (initial_def_dt,
4211 vec_init_def);
4214 /* Set the loop-entry arg of the reduction-phi. */
4216 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
4217 == INTEGER_INDUC_COND_REDUCTION)
4219 /* Initialise the reduction phi to zero. This prevents initial
4220 values of non-zero interferring with the reduction op. */
4221 gcc_assert (ncopies == 1);
4222 gcc_assert (i == 0);
4224 tree vec_init_def_type = TREE_TYPE (vec_init_def);
4225 tree zero_vec = build_zero_cst (vec_init_def_type);
4227 add_phi_arg (as_a <gphi *> (phi), zero_vec,
4228 loop_preheader_edge (loop), UNKNOWN_LOCATION);
4230 else
4231 add_phi_arg (as_a <gphi *> (phi), vec_init_def,
4232 loop_preheader_edge (loop), UNKNOWN_LOCATION);
4234 /* Set the loop-latch arg for the reduction-phi. */
4235 if (j > 0)
4236 def = vect_get_vec_def_for_stmt_copy (vect_unknown_def_type, def);
4238 add_phi_arg (as_a <gphi *> (phi), def, loop_latch_edge (loop),
4239 UNKNOWN_LOCATION);
4241 if (dump_enabled_p ())
4243 dump_printf_loc (MSG_NOTE, vect_location,
4244 "transform reduction: created def-use cycle: ");
4245 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
4246 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, SSA_NAME_DEF_STMT (def), 0);
4251 /* 2. Create epilog code.
4252 The reduction epilog code operates across the elements of the vector
4253 of partial results computed by the vectorized loop.
4254 The reduction epilog code consists of:
4256 step 1: compute the scalar result in a vector (v_out2)
4257 step 2: extract the scalar result (s_out3) from the vector (v_out2)
4258 step 3: adjust the scalar result (s_out3) if needed.
4260 Step 1 can be accomplished using one the following three schemes:
4261 (scheme 1) using reduc_code, if available.
4262 (scheme 2) using whole-vector shifts, if available.
4263 (scheme 3) using a scalar loop. In this case steps 1+2 above are
4264 combined.
4266 The overall epilog code looks like this:
4268 s_out0 = phi <s_loop> # original EXIT_PHI
4269 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4270 v_out2 = reduce <v_out1> # step 1
4271 s_out3 = extract_field <v_out2, 0> # step 2
4272 s_out4 = adjust_result <s_out3> # step 3
4274 (step 3 is optional, and steps 1 and 2 may be combined).
4275 Lastly, the uses of s_out0 are replaced by s_out4. */
4278 /* 2.1 Create new loop-exit-phis to preserve loop-closed form:
4279 v_out1 = phi <VECT_DEF>
4280 Store them in NEW_PHIS. */
4282 exit_bb = single_exit (loop)->dest;
4283 prev_phi_info = NULL;
4284 new_phis.create (vect_defs.length ());
4285 FOR_EACH_VEC_ELT (vect_defs, i, def)
4287 for (j = 0; j < ncopies; j++)
4289 tree new_def = copy_ssa_name (def);
4290 phi = create_phi_node (new_def, exit_bb);
4291 set_vinfo_for_stmt (phi, new_stmt_vec_info (phi, loop_vinfo));
4292 if (j == 0)
4293 new_phis.quick_push (phi);
4294 else
4296 def = vect_get_vec_def_for_stmt_copy (dt, def);
4297 STMT_VINFO_RELATED_STMT (prev_phi_info) = phi;
4300 SET_PHI_ARG_DEF (phi, single_exit (loop)->dest_idx, def);
4301 prev_phi_info = vinfo_for_stmt (phi);
4305 /* The epilogue is created for the outer-loop, i.e., for the loop being
4306 vectorized. Create exit phis for the outer loop. */
4307 if (double_reduc)
4309 loop = outer_loop;
4310 exit_bb = single_exit (loop)->dest;
4311 inner_phis.create (vect_defs.length ());
4312 FOR_EACH_VEC_ELT (new_phis, i, phi)
4314 tree new_result = copy_ssa_name (PHI_RESULT (phi));
4315 gphi *outer_phi = create_phi_node (new_result, exit_bb);
4316 SET_PHI_ARG_DEF (outer_phi, single_exit (loop)->dest_idx,
4317 PHI_RESULT (phi));
4318 set_vinfo_for_stmt (outer_phi, new_stmt_vec_info (outer_phi,
4319 loop_vinfo));
4320 inner_phis.quick_push (phi);
4321 new_phis[i] = outer_phi;
4322 prev_phi_info = vinfo_for_stmt (outer_phi);
4323 while (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi)))
4325 phi = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi));
4326 new_result = copy_ssa_name (PHI_RESULT (phi));
4327 outer_phi = create_phi_node (new_result, exit_bb);
4328 SET_PHI_ARG_DEF (outer_phi, single_exit (loop)->dest_idx,
4329 PHI_RESULT (phi));
4330 set_vinfo_for_stmt (outer_phi, new_stmt_vec_info (outer_phi,
4331 loop_vinfo));
4332 STMT_VINFO_RELATED_STMT (prev_phi_info) = outer_phi;
4333 prev_phi_info = vinfo_for_stmt (outer_phi);
4338 exit_gsi = gsi_after_labels (exit_bb);
4340 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
4341 (i.e. when reduc_code is not available) and in the final adjustment
4342 code (if needed). Also get the original scalar reduction variable as
4343 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
4344 represents a reduction pattern), the tree-code and scalar-def are
4345 taken from the original stmt that the pattern-stmt (STMT) replaces.
4346 Otherwise (it is a regular reduction) - the tree-code and scalar-def
4347 are taken from STMT. */
4349 orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
4350 if (!orig_stmt)
4352 /* Regular reduction */
4353 orig_stmt = stmt;
4355 else
4357 /* Reduction pattern */
4358 stmt_vec_info stmt_vinfo = vinfo_for_stmt (orig_stmt);
4359 gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo));
4360 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo) == stmt);
4363 code = gimple_assign_rhs_code (orig_stmt);
4364 /* For MINUS_EXPR the initial vector is [init_val,0,...,0], therefore,
4365 partial results are added and not subtracted. */
4366 if (code == MINUS_EXPR)
4367 code = PLUS_EXPR;
4369 scalar_dest = gimple_assign_lhs (orig_stmt);
4370 scalar_type = TREE_TYPE (scalar_dest);
4371 scalar_results.create (group_size);
4372 new_scalar_dest = vect_create_destination_var (scalar_dest, NULL);
4373 bitsize = TYPE_SIZE (scalar_type);
4375 /* In case this is a reduction in an inner-loop while vectorizing an outer
4376 loop - we don't need to extract a single scalar result at the end of the
4377 inner-loop (unless it is double reduction, i.e., the use of reduction is
4378 outside the outer-loop). The final vector of partial results will be used
4379 in the vectorized outer-loop, or reduced to a scalar result at the end of
4380 the outer-loop. */
4381 if (nested_in_vect_loop && !double_reduc)
4382 goto vect_finalize_reduction;
4384 /* SLP reduction without reduction chain, e.g.,
4385 # a1 = phi <a2, a0>
4386 # b1 = phi <b2, b0>
4387 a2 = operation (a1)
4388 b2 = operation (b1) */
4389 slp_reduc = (slp_node && !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)));
4391 /* In case of reduction chain, e.g.,
4392 # a1 = phi <a3, a0>
4393 a2 = operation (a1)
4394 a3 = operation (a2),
4396 we may end up with more than one vector result. Here we reduce them to
4397 one vector. */
4398 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
4400 tree first_vect = PHI_RESULT (new_phis[0]);
4401 tree tmp;
4402 gassign *new_vec_stmt = NULL;
4404 vec_dest = vect_create_destination_var (scalar_dest, vectype);
4405 for (k = 1; k < new_phis.length (); k++)
4407 gimple *next_phi = new_phis[k];
4408 tree second_vect = PHI_RESULT (next_phi);
4410 tmp = build2 (code, vectype, first_vect, second_vect);
4411 new_vec_stmt = gimple_build_assign (vec_dest, tmp);
4412 first_vect = make_ssa_name (vec_dest, new_vec_stmt);
4413 gimple_assign_set_lhs (new_vec_stmt, first_vect);
4414 gsi_insert_before (&exit_gsi, new_vec_stmt, GSI_SAME_STMT);
4417 new_phi_result = first_vect;
4418 if (new_vec_stmt)
4420 new_phis.truncate (0);
4421 new_phis.safe_push (new_vec_stmt);
4424 else
4425 new_phi_result = PHI_RESULT (new_phis[0]);
4427 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION)
4429 /* For condition reductions, we have a vector (NEW_PHI_RESULT) containing
4430 various data values where the condition matched and another vector
4431 (INDUCTION_INDEX) containing all the indexes of those matches. We
4432 need to extract the last matching index (which will be the index with
4433 highest value) and use this to index into the data vector.
4434 For the case where there were no matches, the data vector will contain
4435 all default values and the index vector will be all zeros. */
4437 /* Get various versions of the type of the vector of indexes. */
4438 tree index_vec_type = TREE_TYPE (induction_index);
4439 gcc_checking_assert (TYPE_UNSIGNED (index_vec_type));
4440 tree index_scalar_type = TREE_TYPE (index_vec_type);
4441 tree index_vec_cmp_type = build_same_sized_truth_vector_type
4442 (index_vec_type);
4444 /* Get an unsigned integer version of the type of the data vector. */
4445 int scalar_precision = GET_MODE_PRECISION (TYPE_MODE (scalar_type));
4446 tree scalar_type_unsigned = make_unsigned_type (scalar_precision);
4447 tree vectype_unsigned = build_vector_type
4448 (scalar_type_unsigned, TYPE_VECTOR_SUBPARTS (vectype));
4450 /* First we need to create a vector (ZERO_VEC) of zeros and another
4451 vector (MAX_INDEX_VEC) filled with the last matching index, which we
4452 can create using a MAX reduction and then expanding.
4453 In the case where the loop never made any matches, the max index will
4454 be zero. */
4456 /* Vector of {0, 0, 0,...}. */
4457 tree zero_vec = make_ssa_name (vectype);
4458 tree zero_vec_rhs = build_zero_cst (vectype);
4459 gimple *zero_vec_stmt = gimple_build_assign (zero_vec, zero_vec_rhs);
4460 gsi_insert_before (&exit_gsi, zero_vec_stmt, GSI_SAME_STMT);
4462 /* Find maximum value from the vector of found indexes. */
4463 tree max_index = make_ssa_name (index_scalar_type);
4464 gimple *max_index_stmt = gimple_build_assign (max_index, REDUC_MAX_EXPR,
4465 induction_index);
4466 gsi_insert_before (&exit_gsi, max_index_stmt, GSI_SAME_STMT);
4468 /* Vector of {max_index, max_index, max_index,...}. */
4469 tree max_index_vec = make_ssa_name (index_vec_type);
4470 tree max_index_vec_rhs = build_vector_from_val (index_vec_type,
4471 max_index);
4472 gimple *max_index_vec_stmt = gimple_build_assign (max_index_vec,
4473 max_index_vec_rhs);
4474 gsi_insert_before (&exit_gsi, max_index_vec_stmt, GSI_SAME_STMT);
4476 /* Next we compare the new vector (MAX_INDEX_VEC) full of max indexes
4477 with the vector (INDUCTION_INDEX) of found indexes, choosing values
4478 from the data vector (NEW_PHI_RESULT) for matches, 0 (ZERO_VEC)
4479 otherwise. Only one value should match, resulting in a vector
4480 (VEC_COND) with one data value and the rest zeros.
4481 In the case where the loop never made any matches, every index will
4482 match, resulting in a vector with all data values (which will all be
4483 the default value). */
4485 /* Compare the max index vector to the vector of found indexes to find
4486 the position of the max value. */
4487 tree vec_compare = make_ssa_name (index_vec_cmp_type);
4488 gimple *vec_compare_stmt = gimple_build_assign (vec_compare, EQ_EXPR,
4489 induction_index,
4490 max_index_vec);
4491 gsi_insert_before (&exit_gsi, vec_compare_stmt, GSI_SAME_STMT);
4493 /* Use the compare to choose either values from the data vector or
4494 zero. */
4495 tree vec_cond = make_ssa_name (vectype);
4496 gimple *vec_cond_stmt = gimple_build_assign (vec_cond, VEC_COND_EXPR,
4497 vec_compare, new_phi_result,
4498 zero_vec);
4499 gsi_insert_before (&exit_gsi, vec_cond_stmt, GSI_SAME_STMT);
4501 /* Finally we need to extract the data value from the vector (VEC_COND)
4502 into a scalar (MATCHED_DATA_REDUC). Logically we want to do a OR
4503 reduction, but because this doesn't exist, we can use a MAX reduction
4504 instead. The data value might be signed or a float so we need to cast
4505 it first.
4506 In the case where the loop never made any matches, the data values are
4507 all identical, and so will reduce down correctly. */
4509 /* Make the matched data values unsigned. */
4510 tree vec_cond_cast = make_ssa_name (vectype_unsigned);
4511 tree vec_cond_cast_rhs = build1 (VIEW_CONVERT_EXPR, vectype_unsigned,
4512 vec_cond);
4513 gimple *vec_cond_cast_stmt = gimple_build_assign (vec_cond_cast,
4514 VIEW_CONVERT_EXPR,
4515 vec_cond_cast_rhs);
4516 gsi_insert_before (&exit_gsi, vec_cond_cast_stmt, GSI_SAME_STMT);
4518 /* Reduce down to a scalar value. */
4519 tree data_reduc = make_ssa_name (scalar_type_unsigned);
4520 optab ot = optab_for_tree_code (REDUC_MAX_EXPR, vectype_unsigned,
4521 optab_default);
4522 gcc_assert (optab_handler (ot, TYPE_MODE (vectype_unsigned))
4523 != CODE_FOR_nothing);
4524 gimple *data_reduc_stmt = gimple_build_assign (data_reduc,
4525 REDUC_MAX_EXPR,
4526 vec_cond_cast);
4527 gsi_insert_before (&exit_gsi, data_reduc_stmt, GSI_SAME_STMT);
4529 /* Convert the reduced value back to the result type and set as the
4530 result. */
4531 tree data_reduc_cast = build1 (VIEW_CONVERT_EXPR, scalar_type,
4532 data_reduc);
4533 epilog_stmt = gimple_build_assign (new_scalar_dest, data_reduc_cast);
4534 new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
4535 gimple_assign_set_lhs (epilog_stmt, new_temp);
4536 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4537 scalar_results.safe_push (new_temp);
4540 /* 2.3 Create the reduction code, using one of the three schemes described
4541 above. In SLP we simply need to extract all the elements from the
4542 vector (without reducing them), so we use scalar shifts. */
4543 else if (reduc_code != ERROR_MARK && !slp_reduc)
4545 tree tmp;
4546 tree vec_elem_type;
4548 /* Case 1: Create:
4549 v_out2 = reduc_expr <v_out1> */
4551 if (dump_enabled_p ())
4552 dump_printf_loc (MSG_NOTE, vect_location,
4553 "Reduce using direct vector reduction.\n");
4555 vec_elem_type = TREE_TYPE (TREE_TYPE (new_phi_result));
4556 if (!useless_type_conversion_p (scalar_type, vec_elem_type))
4558 tree tmp_dest =
4559 vect_create_destination_var (scalar_dest, vec_elem_type);
4560 tmp = build1 (reduc_code, vec_elem_type, new_phi_result);
4561 epilog_stmt = gimple_build_assign (tmp_dest, tmp);
4562 new_temp = make_ssa_name (tmp_dest, epilog_stmt);
4563 gimple_assign_set_lhs (epilog_stmt, new_temp);
4564 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4566 tmp = build1 (NOP_EXPR, scalar_type, new_temp);
4568 else
4569 tmp = build1 (reduc_code, scalar_type, new_phi_result);
4571 epilog_stmt = gimple_build_assign (new_scalar_dest, tmp);
4572 new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
4573 gimple_assign_set_lhs (epilog_stmt, new_temp);
4574 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4576 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
4577 == INTEGER_INDUC_COND_REDUCTION)
4579 /* Earlier we set the initial value to be zero. Check the result
4580 and if it is zero then replace with the original initial
4581 value. */
4582 tree zero = build_zero_cst (scalar_type);
4583 tree zcompare = build2 (EQ_EXPR, boolean_type_node, new_temp, zero);
4585 tmp = make_ssa_name (new_scalar_dest);
4586 epilog_stmt = gimple_build_assign (tmp, COND_EXPR, zcompare,
4587 initial_def, new_temp);
4588 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4589 new_temp = tmp;
4592 scalar_results.safe_push (new_temp);
4594 else
4596 bool reduce_with_shift = have_whole_vector_shift (mode);
4597 int element_bitsize = tree_to_uhwi (bitsize);
4598 int vec_size_in_bits = tree_to_uhwi (TYPE_SIZE (vectype));
4599 tree vec_temp;
4601 /* Regardless of whether we have a whole vector shift, if we're
4602 emulating the operation via tree-vect-generic, we don't want
4603 to use it. Only the first round of the reduction is likely
4604 to still be profitable via emulation. */
4605 /* ??? It might be better to emit a reduction tree code here, so that
4606 tree-vect-generic can expand the first round via bit tricks. */
4607 if (!VECTOR_MODE_P (mode))
4608 reduce_with_shift = false;
4609 else
4611 optab optab = optab_for_tree_code (code, vectype, optab_default);
4612 if (optab_handler (optab, mode) == CODE_FOR_nothing)
4613 reduce_with_shift = false;
4616 if (reduce_with_shift && !slp_reduc)
4618 int nelements = vec_size_in_bits / element_bitsize;
4619 unsigned char *sel = XALLOCAVEC (unsigned char, nelements);
4621 int elt_offset;
4623 tree zero_vec = build_zero_cst (vectype);
4624 /* Case 2: Create:
4625 for (offset = nelements/2; offset >= 1; offset/=2)
4627 Create: va' = vec_shift <va, offset>
4628 Create: va = vop <va, va'>
4629 } */
4631 tree rhs;
4633 if (dump_enabled_p ())
4634 dump_printf_loc (MSG_NOTE, vect_location,
4635 "Reduce using vector shifts\n");
4637 vec_dest = vect_create_destination_var (scalar_dest, vectype);
4638 new_temp = new_phi_result;
4639 for (elt_offset = nelements / 2;
4640 elt_offset >= 1;
4641 elt_offset /= 2)
4643 calc_vec_perm_mask_for_shift (mode, elt_offset, sel);
4644 tree mask = vect_gen_perm_mask_any (vectype, sel);
4645 epilog_stmt = gimple_build_assign (vec_dest, VEC_PERM_EXPR,
4646 new_temp, zero_vec, mask);
4647 new_name = make_ssa_name (vec_dest, epilog_stmt);
4648 gimple_assign_set_lhs (epilog_stmt, new_name);
4649 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4651 epilog_stmt = gimple_build_assign (vec_dest, code, new_name,
4652 new_temp);
4653 new_temp = make_ssa_name (vec_dest, epilog_stmt);
4654 gimple_assign_set_lhs (epilog_stmt, new_temp);
4655 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4658 /* 2.4 Extract the final scalar result. Create:
4659 s_out3 = extract_field <v_out2, bitpos> */
4661 if (dump_enabled_p ())
4662 dump_printf_loc (MSG_NOTE, vect_location,
4663 "extract scalar result\n");
4665 rhs = build3 (BIT_FIELD_REF, scalar_type, new_temp,
4666 bitsize, bitsize_zero_node);
4667 epilog_stmt = gimple_build_assign (new_scalar_dest, rhs);
4668 new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
4669 gimple_assign_set_lhs (epilog_stmt, new_temp);
4670 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4671 scalar_results.safe_push (new_temp);
4673 else
4675 /* Case 3: Create:
4676 s = extract_field <v_out2, 0>
4677 for (offset = element_size;
4678 offset < vector_size;
4679 offset += element_size;)
4681 Create: s' = extract_field <v_out2, offset>
4682 Create: s = op <s, s'> // For non SLP cases
4683 } */
4685 if (dump_enabled_p ())
4686 dump_printf_loc (MSG_NOTE, vect_location,
4687 "Reduce using scalar code.\n");
4689 vec_size_in_bits = tree_to_uhwi (TYPE_SIZE (vectype));
4690 FOR_EACH_VEC_ELT (new_phis, i, new_phi)
4692 int bit_offset;
4693 if (gimple_code (new_phi) == GIMPLE_PHI)
4694 vec_temp = PHI_RESULT (new_phi);
4695 else
4696 vec_temp = gimple_assign_lhs (new_phi);
4697 tree rhs = build3 (BIT_FIELD_REF, scalar_type, vec_temp, bitsize,
4698 bitsize_zero_node);
4699 epilog_stmt = gimple_build_assign (new_scalar_dest, rhs);
4700 new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
4701 gimple_assign_set_lhs (epilog_stmt, new_temp);
4702 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4704 /* In SLP we don't need to apply reduction operation, so we just
4705 collect s' values in SCALAR_RESULTS. */
4706 if (slp_reduc)
4707 scalar_results.safe_push (new_temp);
4709 for (bit_offset = element_bitsize;
4710 bit_offset < vec_size_in_bits;
4711 bit_offset += element_bitsize)
4713 tree bitpos = bitsize_int (bit_offset);
4714 tree rhs = build3 (BIT_FIELD_REF, scalar_type, vec_temp,
4715 bitsize, bitpos);
4717 epilog_stmt = gimple_build_assign (new_scalar_dest, rhs);
4718 new_name = make_ssa_name (new_scalar_dest, epilog_stmt);
4719 gimple_assign_set_lhs (epilog_stmt, new_name);
4720 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4722 if (slp_reduc)
4724 /* In SLP we don't need to apply reduction operation, so
4725 we just collect s' values in SCALAR_RESULTS. */
4726 new_temp = new_name;
4727 scalar_results.safe_push (new_name);
4729 else
4731 epilog_stmt = gimple_build_assign (new_scalar_dest, code,
4732 new_name, new_temp);
4733 new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
4734 gimple_assign_set_lhs (epilog_stmt, new_temp);
4735 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4740 /* The only case where we need to reduce scalar results in SLP, is
4741 unrolling. If the size of SCALAR_RESULTS is greater than
4742 GROUP_SIZE, we reduce them combining elements modulo
4743 GROUP_SIZE. */
4744 if (slp_reduc)
4746 tree res, first_res, new_res;
4747 gimple *new_stmt;
4749 /* Reduce multiple scalar results in case of SLP unrolling. */
4750 for (j = group_size; scalar_results.iterate (j, &res);
4751 j++)
4753 first_res = scalar_results[j % group_size];
4754 new_stmt = gimple_build_assign (new_scalar_dest, code,
4755 first_res, res);
4756 new_res = make_ssa_name (new_scalar_dest, new_stmt);
4757 gimple_assign_set_lhs (new_stmt, new_res);
4758 gsi_insert_before (&exit_gsi, new_stmt, GSI_SAME_STMT);
4759 scalar_results[j % group_size] = new_res;
4762 else
4763 /* Not SLP - we have one scalar to keep in SCALAR_RESULTS. */
4764 scalar_results.safe_push (new_temp);
4768 vect_finalize_reduction:
4770 if (double_reduc)
4771 loop = loop->inner;
4773 /* 2.5 Adjust the final result by the initial value of the reduction
4774 variable. (When such adjustment is not needed, then
4775 'adjustment_def' is zero). For example, if code is PLUS we create:
4776 new_temp = loop_exit_def + adjustment_def */
4778 if (adjustment_def)
4780 gcc_assert (!slp_reduc);
4781 if (nested_in_vect_loop)
4783 new_phi = new_phis[0];
4784 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def)) == VECTOR_TYPE);
4785 expr = build2 (code, vectype, PHI_RESULT (new_phi), adjustment_def);
4786 new_dest = vect_create_destination_var (scalar_dest, vectype);
4788 else
4790 new_temp = scalar_results[0];
4791 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def)) != VECTOR_TYPE);
4792 expr = build2 (code, scalar_type, new_temp, adjustment_def);
4793 new_dest = vect_create_destination_var (scalar_dest, scalar_type);
4796 epilog_stmt = gimple_build_assign (new_dest, expr);
4797 new_temp = make_ssa_name (new_dest, epilog_stmt);
4798 gimple_assign_set_lhs (epilog_stmt, new_temp);
4799 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4800 if (nested_in_vect_loop)
4802 set_vinfo_for_stmt (epilog_stmt,
4803 new_stmt_vec_info (epilog_stmt, loop_vinfo));
4804 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (epilog_stmt)) =
4805 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_phi));
4807 if (!double_reduc)
4808 scalar_results.quick_push (new_temp);
4809 else
4810 scalar_results[0] = new_temp;
4812 else
4813 scalar_results[0] = new_temp;
4815 new_phis[0] = epilog_stmt;
4818 /* 2.6 Handle the loop-exit phis. Replace the uses of scalar loop-exit
4819 phis with new adjusted scalar results, i.e., replace use <s_out0>
4820 with use <s_out4>.
4822 Transform:
4823 loop_exit:
4824 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4825 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4826 v_out2 = reduce <v_out1>
4827 s_out3 = extract_field <v_out2, 0>
4828 s_out4 = adjust_result <s_out3>
4829 use <s_out0>
4830 use <s_out0>
4832 into:
4834 loop_exit:
4835 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4836 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4837 v_out2 = reduce <v_out1>
4838 s_out3 = extract_field <v_out2, 0>
4839 s_out4 = adjust_result <s_out3>
4840 use <s_out4>
4841 use <s_out4> */
4844 /* In SLP reduction chain we reduce vector results into one vector if
4845 necessary, hence we set here GROUP_SIZE to 1. SCALAR_DEST is the LHS of
4846 the last stmt in the reduction chain, since we are looking for the loop
4847 exit phi node. */
4848 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
4850 gimple *dest_stmt = SLP_TREE_SCALAR_STMTS (slp_node)[group_size - 1];
4851 /* Handle reduction patterns. */
4852 if (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (dest_stmt)))
4853 dest_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (dest_stmt));
4855 scalar_dest = gimple_assign_lhs (dest_stmt);
4856 group_size = 1;
4859 /* In SLP we may have several statements in NEW_PHIS and REDUCTION_PHIS (in
4860 case that GROUP_SIZE is greater than vectorization factor). Therefore, we
4861 need to match SCALAR_RESULTS with corresponding statements. The first
4862 (GROUP_SIZE / number of new vector stmts) scalar results correspond to
4863 the first vector stmt, etc.
4864 (RATIO is equal to (GROUP_SIZE / number of new vector stmts)). */
4865 if (group_size > new_phis.length ())
4867 ratio = group_size / new_phis.length ();
4868 gcc_assert (!(group_size % new_phis.length ()));
4870 else
4871 ratio = 1;
4873 for (k = 0; k < group_size; k++)
4875 if (k % ratio == 0)
4877 epilog_stmt = new_phis[k / ratio];
4878 reduction_phi = reduction_phis[k / ratio];
4879 if (double_reduc)
4880 inner_phi = inner_phis[k / ratio];
4883 if (slp_reduc)
4885 gimple *current_stmt = SLP_TREE_SCALAR_STMTS (slp_node)[k];
4887 orig_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (current_stmt));
4888 /* SLP statements can't participate in patterns. */
4889 gcc_assert (!orig_stmt);
4890 scalar_dest = gimple_assign_lhs (current_stmt);
4893 phis.create (3);
4894 /* Find the loop-closed-use at the loop exit of the original scalar
4895 result. (The reduction result is expected to have two immediate uses -
4896 one at the latch block, and one at the loop exit). */
4897 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, scalar_dest)
4898 if (!flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p)))
4899 && !is_gimple_debug (USE_STMT (use_p)))
4900 phis.safe_push (USE_STMT (use_p));
4902 /* While we expect to have found an exit_phi because of loop-closed-ssa
4903 form we can end up without one if the scalar cycle is dead. */
4905 FOR_EACH_VEC_ELT (phis, i, exit_phi)
4907 if (outer_loop)
4909 stmt_vec_info exit_phi_vinfo = vinfo_for_stmt (exit_phi);
4910 gphi *vect_phi;
4912 /* FORNOW. Currently not supporting the case that an inner-loop
4913 reduction is not used in the outer-loop (but only outside the
4914 outer-loop), unless it is double reduction. */
4915 gcc_assert ((STMT_VINFO_RELEVANT_P (exit_phi_vinfo)
4916 && !STMT_VINFO_LIVE_P (exit_phi_vinfo))
4917 || double_reduc);
4919 if (double_reduc)
4920 STMT_VINFO_VEC_STMT (exit_phi_vinfo) = inner_phi;
4921 else
4922 STMT_VINFO_VEC_STMT (exit_phi_vinfo) = epilog_stmt;
4923 if (!double_reduc
4924 || STMT_VINFO_DEF_TYPE (exit_phi_vinfo)
4925 != vect_double_reduction_def)
4926 continue;
4928 /* Handle double reduction:
4930 stmt1: s1 = phi <s0, s2> - double reduction phi (outer loop)
4931 stmt2: s3 = phi <s1, s4> - (regular) reduc phi (inner loop)
4932 stmt3: s4 = use (s3) - (regular) reduc stmt (inner loop)
4933 stmt4: s2 = phi <s4> - double reduction stmt (outer loop)
4935 At that point the regular reduction (stmt2 and stmt3) is
4936 already vectorized, as well as the exit phi node, stmt4.
4937 Here we vectorize the phi node of double reduction, stmt1, and
4938 update all relevant statements. */
4940 /* Go through all the uses of s2 to find double reduction phi
4941 node, i.e., stmt1 above. */
4942 orig_name = PHI_RESULT (exit_phi);
4943 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, orig_name)
4945 stmt_vec_info use_stmt_vinfo;
4946 stmt_vec_info new_phi_vinfo;
4947 tree vect_phi_init, preheader_arg, vect_phi_res, init_def;
4948 basic_block bb = gimple_bb (use_stmt);
4949 gimple *use;
4951 /* Check that USE_STMT is really double reduction phi
4952 node. */
4953 if (gimple_code (use_stmt) != GIMPLE_PHI
4954 || gimple_phi_num_args (use_stmt) != 2
4955 || bb->loop_father != outer_loop)
4956 continue;
4957 use_stmt_vinfo = vinfo_for_stmt (use_stmt);
4958 if (!use_stmt_vinfo
4959 || STMT_VINFO_DEF_TYPE (use_stmt_vinfo)
4960 != vect_double_reduction_def)
4961 continue;
4963 /* Create vector phi node for double reduction:
4964 vs1 = phi <vs0, vs2>
4965 vs1 was created previously in this function by a call to
4966 vect_get_vec_def_for_operand and is stored in
4967 vec_initial_def;
4968 vs2 is defined by INNER_PHI, the vectorized EXIT_PHI;
4969 vs0 is created here. */
4971 /* Create vector phi node. */
4972 vect_phi = create_phi_node (vec_initial_def, bb);
4973 new_phi_vinfo = new_stmt_vec_info (vect_phi,
4974 loop_vec_info_for_loop (outer_loop));
4975 set_vinfo_for_stmt (vect_phi, new_phi_vinfo);
4977 /* Create vs0 - initial def of the double reduction phi. */
4978 preheader_arg = PHI_ARG_DEF_FROM_EDGE (use_stmt,
4979 loop_preheader_edge (outer_loop));
4980 init_def = get_initial_def_for_reduction (stmt,
4981 preheader_arg, NULL);
4982 vect_phi_init = vect_init_vector (use_stmt, init_def,
4983 vectype, NULL);
4985 /* Update phi node arguments with vs0 and vs2. */
4986 add_phi_arg (vect_phi, vect_phi_init,
4987 loop_preheader_edge (outer_loop),
4988 UNKNOWN_LOCATION);
4989 add_phi_arg (vect_phi, PHI_RESULT (inner_phi),
4990 loop_latch_edge (outer_loop), UNKNOWN_LOCATION);
4991 if (dump_enabled_p ())
4993 dump_printf_loc (MSG_NOTE, vect_location,
4994 "created double reduction phi node: ");
4995 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, vect_phi, 0);
4998 vect_phi_res = PHI_RESULT (vect_phi);
5000 /* Replace the use, i.e., set the correct vs1 in the regular
5001 reduction phi node. FORNOW, NCOPIES is always 1, so the
5002 loop is redundant. */
5003 use = reduction_phi;
5004 for (j = 0; j < ncopies; j++)
5006 edge pr_edge = loop_preheader_edge (loop);
5007 SET_PHI_ARG_DEF (use, pr_edge->dest_idx, vect_phi_res);
5008 use = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use));
5014 phis.release ();
5015 if (nested_in_vect_loop)
5017 if (double_reduc)
5018 loop = outer_loop;
5019 else
5020 continue;
5023 phis.create (3);
5024 /* Find the loop-closed-use at the loop exit of the original scalar
5025 result. (The reduction result is expected to have two immediate uses,
5026 one at the latch block, and one at the loop exit). For double
5027 reductions we are looking for exit phis of the outer loop. */
5028 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, scalar_dest)
5030 if (!flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
5032 if (!is_gimple_debug (USE_STMT (use_p)))
5033 phis.safe_push (USE_STMT (use_p));
5035 else
5037 if (double_reduc && gimple_code (USE_STMT (use_p)) == GIMPLE_PHI)
5039 tree phi_res = PHI_RESULT (USE_STMT (use_p));
5041 FOR_EACH_IMM_USE_FAST (phi_use_p, phi_imm_iter, phi_res)
5043 if (!flow_bb_inside_loop_p (loop,
5044 gimple_bb (USE_STMT (phi_use_p)))
5045 && !is_gimple_debug (USE_STMT (phi_use_p)))
5046 phis.safe_push (USE_STMT (phi_use_p));
5052 FOR_EACH_VEC_ELT (phis, i, exit_phi)
5054 /* Replace the uses: */
5055 orig_name = PHI_RESULT (exit_phi);
5056 scalar_result = scalar_results[k];
5057 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, orig_name)
5058 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
5059 SET_USE (use_p, scalar_result);
5062 phis.release ();
5067 /* Function is_nonwrapping_integer_induction.
5069 Check if STMT (which is part of loop LOOP) both increments and
5070 does not cause overflow. */
5072 static bool
5073 is_nonwrapping_integer_induction (gimple *stmt, struct loop *loop)
5075 stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
5076 tree base = STMT_VINFO_LOOP_PHI_EVOLUTION_BASE_UNCHANGED (stmt_vinfo);
5077 tree step = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo);
5078 tree lhs_type = TREE_TYPE (gimple_phi_result (stmt));
5079 widest_int ni, max_loop_value, lhs_max;
5080 bool overflow = false;
5082 /* Make sure the loop is integer based. */
5083 if (TREE_CODE (base) != INTEGER_CST
5084 || TREE_CODE (step) != INTEGER_CST)
5085 return false;
5087 /* Check that the induction increments. */
5088 if (tree_int_cst_sgn (step) == -1)
5089 return false;
5091 /* Check that the max size of the loop will not wrap. */
5093 if (TYPE_OVERFLOW_UNDEFINED (lhs_type))
5094 return true;
5096 if (! max_stmt_executions (loop, &ni))
5097 return false;
5099 max_loop_value = wi::mul (wi::to_widest (step), ni, TYPE_SIGN (lhs_type),
5100 &overflow);
5101 if (overflow)
5102 return false;
5104 max_loop_value = wi::add (wi::to_widest (base), max_loop_value,
5105 TYPE_SIGN (lhs_type), &overflow);
5106 if (overflow)
5107 return false;
5109 return (wi::min_precision (max_loop_value, TYPE_SIGN (lhs_type))
5110 <= TYPE_PRECISION (lhs_type));
5113 /* Function vectorizable_reduction.
5115 Check if STMT performs a reduction operation that can be vectorized.
5116 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
5117 stmt to replace it, put it in VEC_STMT, and insert it at GSI.
5118 Return FALSE if not a vectorizable STMT, TRUE otherwise.
5120 This function also handles reduction idioms (patterns) that have been
5121 recognized in advance during vect_pattern_recog. In this case, STMT may be
5122 of this form:
5123 X = pattern_expr (arg0, arg1, ..., X)
5124 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
5125 sequence that had been detected and replaced by the pattern-stmt (STMT).
5127 This function also handles reduction of condition expressions, for example:
5128 for (int i = 0; i < N; i++)
5129 if (a[i] < value)
5130 last = a[i];
5131 This is handled by vectorising the loop and creating an additional vector
5132 containing the loop indexes for which "a[i] < value" was true. In the
5133 function epilogue this is reduced to a single max value and then used to
5134 index into the vector of results.
5136 In some cases of reduction patterns, the type of the reduction variable X is
5137 different than the type of the other arguments of STMT.
5138 In such cases, the vectype that is used when transforming STMT into a vector
5139 stmt is different than the vectype that is used to determine the
5140 vectorization factor, because it consists of a different number of elements
5141 than the actual number of elements that are being operated upon in parallel.
5143 For example, consider an accumulation of shorts into an int accumulator.
5144 On some targets it's possible to vectorize this pattern operating on 8
5145 shorts at a time (hence, the vectype for purposes of determining the
5146 vectorization factor should be V8HI); on the other hand, the vectype that
5147 is used to create the vector form is actually V4SI (the type of the result).
5149 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
5150 indicates what is the actual level of parallelism (V8HI in the example), so
5151 that the right vectorization factor would be derived. This vectype
5152 corresponds to the type of arguments to the reduction stmt, and should *NOT*
5153 be used to create the vectorized stmt. The right vectype for the vectorized
5154 stmt is obtained from the type of the result X:
5155 get_vectype_for_scalar_type (TREE_TYPE (X))
5157 This means that, contrary to "regular" reductions (or "regular" stmts in
5158 general), the following equation:
5159 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
5160 does *NOT* necessarily hold for reduction patterns. */
5162 bool
5163 vectorizable_reduction (gimple *stmt, gimple_stmt_iterator *gsi,
5164 gimple **vec_stmt, slp_tree slp_node)
5166 tree vec_dest;
5167 tree scalar_dest;
5168 tree loop_vec_def0 = NULL_TREE, loop_vec_def1 = NULL_TREE;
5169 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
5170 tree vectype_out = STMT_VINFO_VECTYPE (stmt_info);
5171 tree vectype_in = NULL_TREE;
5172 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
5173 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
5174 enum tree_code code, orig_code, epilog_reduc_code;
5175 machine_mode vec_mode;
5176 int op_type;
5177 optab optab, reduc_optab;
5178 tree new_temp = NULL_TREE;
5179 gimple *def_stmt;
5180 enum vect_def_type dt, cond_reduc_dt = vect_unknown_def_type;
5181 gphi *new_phi = NULL;
5182 tree scalar_type;
5183 bool is_simple_use;
5184 gimple *orig_stmt;
5185 stmt_vec_info orig_stmt_info;
5186 tree expr = NULL_TREE;
5187 int i;
5188 int ncopies;
5189 int epilog_copies;
5190 stmt_vec_info prev_stmt_info, prev_phi_info;
5191 bool single_defuse_cycle = false;
5192 tree reduc_def = NULL_TREE;
5193 gimple *new_stmt = NULL;
5194 int j;
5195 tree ops[3];
5196 bool nested_cycle = false, found_nested_cycle_def = false;
5197 gimple *reduc_def_stmt = NULL;
5198 bool double_reduc = false;
5199 basic_block def_bb;
5200 struct loop * def_stmt_loop, *outer_loop = NULL;
5201 tree def_arg;
5202 gimple *def_arg_stmt;
5203 auto_vec<tree> vec_oprnds0;
5204 auto_vec<tree> vec_oprnds1;
5205 auto_vec<tree> vect_defs;
5206 auto_vec<gimple *> phis;
5207 int vec_num;
5208 tree def0, def1, tem, op1 = NULL_TREE;
5209 bool first_p = true;
5210 tree cr_index_scalar_type = NULL_TREE, cr_index_vector_type = NULL_TREE;
5211 tree cond_reduc_val = NULL_TREE;
5213 /* In case of reduction chain we switch to the first stmt in the chain, but
5214 we don't update STMT_INFO, since only the last stmt is marked as reduction
5215 and has reduction properties. */
5216 if (GROUP_FIRST_ELEMENT (stmt_info)
5217 && GROUP_FIRST_ELEMENT (stmt_info) != stmt)
5219 stmt = GROUP_FIRST_ELEMENT (stmt_info);
5220 first_p = false;
5223 if (nested_in_vect_loop_p (loop, stmt))
5225 outer_loop = loop;
5226 loop = loop->inner;
5227 nested_cycle = true;
5230 /* 1. Is vectorizable reduction? */
5231 /* Not supportable if the reduction variable is used in the loop, unless
5232 it's a reduction chain. */
5233 if (STMT_VINFO_RELEVANT (stmt_info) > vect_used_in_outer
5234 && !GROUP_FIRST_ELEMENT (stmt_info))
5235 return false;
5237 /* Reductions that are not used even in an enclosing outer-loop,
5238 are expected to be "live" (used out of the loop). */
5239 if (STMT_VINFO_RELEVANT (stmt_info) == vect_unused_in_scope
5240 && !STMT_VINFO_LIVE_P (stmt_info))
5241 return false;
5243 /* Make sure it was already recognized as a reduction computation. */
5244 if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt)) != vect_reduction_def
5245 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt)) != vect_nested_cycle)
5246 return false;
5248 /* 2. Has this been recognized as a reduction pattern?
5250 Check if STMT represents a pattern that has been recognized
5251 in earlier analysis stages. For stmts that represent a pattern,
5252 the STMT_VINFO_RELATED_STMT field records the last stmt in
5253 the original sequence that constitutes the pattern. */
5255 orig_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt));
5256 if (orig_stmt)
5258 orig_stmt_info = vinfo_for_stmt (orig_stmt);
5259 gcc_assert (STMT_VINFO_IN_PATTERN_P (orig_stmt_info));
5260 gcc_assert (!STMT_VINFO_IN_PATTERN_P (stmt_info));
5263 /* 3. Check the operands of the operation. The first operands are defined
5264 inside the loop body. The last operand is the reduction variable,
5265 which is defined by the loop-header-phi. */
5267 gcc_assert (is_gimple_assign (stmt));
5269 /* Flatten RHS. */
5270 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
5272 case GIMPLE_BINARY_RHS:
5273 code = gimple_assign_rhs_code (stmt);
5274 op_type = TREE_CODE_LENGTH (code);
5275 gcc_assert (op_type == binary_op);
5276 ops[0] = gimple_assign_rhs1 (stmt);
5277 ops[1] = gimple_assign_rhs2 (stmt);
5278 break;
5280 case GIMPLE_TERNARY_RHS:
5281 code = gimple_assign_rhs_code (stmt);
5282 op_type = TREE_CODE_LENGTH (code);
5283 gcc_assert (op_type == ternary_op);
5284 ops[0] = gimple_assign_rhs1 (stmt);
5285 ops[1] = gimple_assign_rhs2 (stmt);
5286 ops[2] = gimple_assign_rhs3 (stmt);
5287 break;
5289 case GIMPLE_UNARY_RHS:
5290 return false;
5292 default:
5293 gcc_unreachable ();
5295 /* The default is that the reduction variable is the last in statement. */
5296 int reduc_index = op_type - 1;
5297 if (code == MINUS_EXPR)
5298 reduc_index = 0;
5300 if (code == COND_EXPR && slp_node)
5301 return false;
5303 scalar_dest = gimple_assign_lhs (stmt);
5304 scalar_type = TREE_TYPE (scalar_dest);
5305 if (!POINTER_TYPE_P (scalar_type) && !INTEGRAL_TYPE_P (scalar_type)
5306 && !SCALAR_FLOAT_TYPE_P (scalar_type))
5307 return false;
5309 /* Do not try to vectorize bit-precision reductions. */
5310 if ((TYPE_PRECISION (scalar_type)
5311 != GET_MODE_PRECISION (TYPE_MODE (scalar_type))))
5312 return false;
5314 /* All uses but the last are expected to be defined in the loop.
5315 The last use is the reduction variable. In case of nested cycle this
5316 assumption is not true: we use reduc_index to record the index of the
5317 reduction variable. */
5318 for (i = 0; i < op_type; i++)
5320 if (i == reduc_index)
5321 continue;
5323 /* The condition of COND_EXPR is checked in vectorizable_condition(). */
5324 if (i == 0 && code == COND_EXPR)
5325 continue;
5327 is_simple_use = vect_is_simple_use (ops[i], loop_vinfo,
5328 &def_stmt, &dt, &tem);
5329 if (!vectype_in)
5330 vectype_in = tem;
5331 gcc_assert (is_simple_use);
5333 if (dt != vect_internal_def
5334 && dt != vect_external_def
5335 && dt != vect_constant_def
5336 && dt != vect_induction_def
5337 && !(dt == vect_nested_cycle && nested_cycle))
5338 return false;
5340 if (dt == vect_nested_cycle)
5342 found_nested_cycle_def = true;
5343 reduc_def_stmt = def_stmt;
5344 reduc_index = i;
5347 if (i == 1 && code == COND_EXPR)
5349 /* Record how value of COND_EXPR is defined. */
5350 if (dt == vect_constant_def)
5352 cond_reduc_dt = dt;
5353 cond_reduc_val = ops[i];
5355 if (dt == vect_induction_def && def_stmt != NULL
5356 && is_nonwrapping_integer_induction (def_stmt, loop))
5357 cond_reduc_dt = dt;
5361 is_simple_use = vect_is_simple_use (ops[reduc_index], loop_vinfo,
5362 &def_stmt, &dt, &tem);
5363 if (!vectype_in)
5364 vectype_in = tem;
5365 gcc_assert (is_simple_use);
5366 if (!found_nested_cycle_def)
5367 reduc_def_stmt = def_stmt;
5369 if (reduc_def_stmt && gimple_code (reduc_def_stmt) != GIMPLE_PHI)
5370 return false;
5372 if (!(dt == vect_reduction_def
5373 || dt == vect_nested_cycle
5374 || ((dt == vect_internal_def || dt == vect_external_def
5375 || dt == vect_constant_def || dt == vect_induction_def)
5376 && nested_cycle && found_nested_cycle_def)))
5378 /* For pattern recognized stmts, orig_stmt might be a reduction,
5379 but some helper statements for the pattern might not, or
5380 might be COND_EXPRs with reduction uses in the condition. */
5381 gcc_assert (orig_stmt);
5382 return false;
5385 stmt_vec_info reduc_def_info = vinfo_for_stmt (reduc_def_stmt);
5386 enum vect_reduction_type v_reduc_type
5387 = STMT_VINFO_REDUC_TYPE (reduc_def_info);
5388 gimple *tmp = STMT_VINFO_REDUC_DEF (reduc_def_info);
5390 STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) = v_reduc_type;
5391 /* If we have a condition reduction, see if we can simplify it further. */
5392 if (v_reduc_type == COND_REDUCTION)
5394 if (cond_reduc_dt == vect_induction_def)
5396 if (dump_enabled_p ())
5397 dump_printf_loc (MSG_NOTE, vect_location,
5398 "condition expression based on "
5399 "integer induction.\n");
5400 STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
5401 = INTEGER_INDUC_COND_REDUCTION;
5404 /* Loop peeling modifies initial value of reduction PHI, which
5405 makes the reduction stmt to be transformed different to the
5406 original stmt analyzed. We need to record reduction code for
5407 CONST_COND_REDUCTION type reduction at analyzing stage, thus
5408 it can be used directly at transform stage. */
5409 if (STMT_VINFO_VEC_CONST_COND_REDUC_CODE (stmt_info) == MAX_EXPR
5410 || STMT_VINFO_VEC_CONST_COND_REDUC_CODE (stmt_info) == MIN_EXPR)
5412 /* Also set the reduction type to CONST_COND_REDUCTION. */
5413 gcc_assert (cond_reduc_dt == vect_constant_def);
5414 STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) = CONST_COND_REDUCTION;
5416 else if (cond_reduc_dt == vect_constant_def)
5418 enum vect_def_type cond_initial_dt;
5419 gimple *def_stmt = SSA_NAME_DEF_STMT (ops[reduc_index]);
5420 tree cond_initial_val
5421 = PHI_ARG_DEF_FROM_EDGE (def_stmt, loop_preheader_edge (loop));
5423 gcc_assert (cond_reduc_val != NULL_TREE);
5424 vect_is_simple_use (cond_initial_val, loop_vinfo,
5425 &def_stmt, &cond_initial_dt);
5426 if (cond_initial_dt == vect_constant_def
5427 && types_compatible_p (TREE_TYPE (cond_initial_val),
5428 TREE_TYPE (cond_reduc_val)))
5430 tree e = fold_build2 (LE_EXPR, boolean_type_node,
5431 cond_initial_val, cond_reduc_val);
5432 if (e && (integer_onep (e) || integer_zerop (e)))
5434 if (dump_enabled_p ())
5435 dump_printf_loc (MSG_NOTE, vect_location,
5436 "condition expression based on "
5437 "compile time constant.\n");
5438 /* Record reduction code at analysis stage. */
5439 STMT_VINFO_VEC_CONST_COND_REDUC_CODE (stmt_info)
5440 = integer_onep (e) ? MAX_EXPR : MIN_EXPR;
5441 STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
5442 = CONST_COND_REDUCTION;
5448 if (orig_stmt)
5449 gcc_assert (tmp == orig_stmt
5450 || GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp)) == orig_stmt);
5451 else
5452 /* We changed STMT to be the first stmt in reduction chain, hence we
5453 check that in this case the first element in the chain is STMT. */
5454 gcc_assert (stmt == tmp
5455 || GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp)) == stmt);
5457 if (STMT_VINFO_LIVE_P (vinfo_for_stmt (reduc_def_stmt)))
5458 return false;
5460 if (slp_node)
5461 ncopies = 1;
5462 else
5463 ncopies = (LOOP_VINFO_VECT_FACTOR (loop_vinfo)
5464 / TYPE_VECTOR_SUBPARTS (vectype_in));
5466 gcc_assert (ncopies >= 1);
5468 vec_mode = TYPE_MODE (vectype_in);
5470 if (code == COND_EXPR)
5472 /* Only call during the analysis stage, otherwise we'll lose
5473 STMT_VINFO_TYPE. */
5474 if (!vec_stmt && !vectorizable_condition (stmt, gsi, NULL,
5475 ops[reduc_index], 0, NULL))
5477 if (dump_enabled_p ())
5478 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5479 "unsupported condition in reduction\n");
5480 return false;
5483 else
5485 /* 4. Supportable by target? */
5487 if (code == LSHIFT_EXPR || code == RSHIFT_EXPR
5488 || code == LROTATE_EXPR || code == RROTATE_EXPR)
5490 /* Shifts and rotates are only supported by vectorizable_shifts,
5491 not vectorizable_reduction. */
5492 if (dump_enabled_p ())
5493 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5494 "unsupported shift or rotation.\n");
5495 return false;
5498 /* 4.1. check support for the operation in the loop */
5499 optab = optab_for_tree_code (code, vectype_in, optab_default);
5500 if (!optab)
5502 if (dump_enabled_p ())
5503 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5504 "no optab.\n");
5506 return false;
5509 if (optab_handler (optab, vec_mode) == CODE_FOR_nothing)
5511 if (dump_enabled_p ())
5512 dump_printf (MSG_NOTE, "op not supported by target.\n");
5514 if (GET_MODE_SIZE (vec_mode) != UNITS_PER_WORD
5515 || LOOP_VINFO_VECT_FACTOR (loop_vinfo)
5516 < vect_min_worthwhile_factor (code))
5517 return false;
5519 if (dump_enabled_p ())
5520 dump_printf (MSG_NOTE, "proceeding using word mode.\n");
5523 /* Worthwhile without SIMD support? */
5524 if (!VECTOR_MODE_P (TYPE_MODE (vectype_in))
5525 && LOOP_VINFO_VECT_FACTOR (loop_vinfo)
5526 < vect_min_worthwhile_factor (code))
5528 if (dump_enabled_p ())
5529 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5530 "not worthwhile without SIMD support.\n");
5532 return false;
5536 /* 4.2. Check support for the epilog operation.
5538 If STMT represents a reduction pattern, then the type of the
5539 reduction variable may be different than the type of the rest
5540 of the arguments. For example, consider the case of accumulation
5541 of shorts into an int accumulator; The original code:
5542 S1: int_a = (int) short_a;
5543 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
5545 was replaced with:
5546 STMT: int_acc = widen_sum <short_a, int_acc>
5548 This means that:
5549 1. The tree-code that is used to create the vector operation in the
5550 epilog code (that reduces the partial results) is not the
5551 tree-code of STMT, but is rather the tree-code of the original
5552 stmt from the pattern that STMT is replacing. I.e, in the example
5553 above we want to use 'widen_sum' in the loop, but 'plus' in the
5554 epilog.
5555 2. The type (mode) we use to check available target support
5556 for the vector operation to be created in the *epilog*, is
5557 determined by the type of the reduction variable (in the example
5558 above we'd check this: optab_handler (plus_optab, vect_int_mode])).
5559 However the type (mode) we use to check available target support
5560 for the vector operation to be created *inside the loop*, is
5561 determined by the type of the other arguments to STMT (in the
5562 example we'd check this: optab_handler (widen_sum_optab,
5563 vect_short_mode)).
5565 This is contrary to "regular" reductions, in which the types of all
5566 the arguments are the same as the type of the reduction variable.
5567 For "regular" reductions we can therefore use the same vector type
5568 (and also the same tree-code) when generating the epilog code and
5569 when generating the code inside the loop. */
5571 if (orig_stmt)
5573 /* This is a reduction pattern: get the vectype from the type of the
5574 reduction variable, and get the tree-code from orig_stmt. */
5575 gcc_assert (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
5576 == TREE_CODE_REDUCTION);
5577 orig_code = gimple_assign_rhs_code (orig_stmt);
5578 gcc_assert (vectype_out);
5579 vec_mode = TYPE_MODE (vectype_out);
5581 else
5583 /* Regular reduction: use the same vectype and tree-code as used for
5584 the vector code inside the loop can be used for the epilog code. */
5585 orig_code = code;
5587 if (code == MINUS_EXPR)
5588 orig_code = PLUS_EXPR;
5590 /* For simple condition reductions, replace with the actual expression
5591 we want to base our reduction around. */
5592 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == CONST_COND_REDUCTION)
5594 orig_code = STMT_VINFO_VEC_CONST_COND_REDUC_CODE (stmt_info);
5595 gcc_assert (orig_code == MAX_EXPR || orig_code == MIN_EXPR);
5597 else if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
5598 == INTEGER_INDUC_COND_REDUCTION)
5599 orig_code = MAX_EXPR;
5602 if (nested_cycle)
5604 def_bb = gimple_bb (reduc_def_stmt);
5605 def_stmt_loop = def_bb->loop_father;
5606 def_arg = PHI_ARG_DEF_FROM_EDGE (reduc_def_stmt,
5607 loop_preheader_edge (def_stmt_loop));
5608 if (TREE_CODE (def_arg) == SSA_NAME
5609 && (def_arg_stmt = SSA_NAME_DEF_STMT (def_arg))
5610 && gimple_code (def_arg_stmt) == GIMPLE_PHI
5611 && flow_bb_inside_loop_p (outer_loop, gimple_bb (def_arg_stmt))
5612 && vinfo_for_stmt (def_arg_stmt)
5613 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_arg_stmt))
5614 == vect_double_reduction_def)
5615 double_reduc = true;
5618 epilog_reduc_code = ERROR_MARK;
5620 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) != COND_REDUCTION)
5622 if (reduction_code_for_scalar_code (orig_code, &epilog_reduc_code))
5624 reduc_optab = optab_for_tree_code (epilog_reduc_code, vectype_out,
5625 optab_default);
5626 if (!reduc_optab)
5628 if (dump_enabled_p ())
5629 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5630 "no optab for reduction.\n");
5632 epilog_reduc_code = ERROR_MARK;
5634 else if (optab_handler (reduc_optab, vec_mode) == CODE_FOR_nothing)
5636 if (dump_enabled_p ())
5637 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5638 "reduc op not supported by target.\n");
5640 epilog_reduc_code = ERROR_MARK;
5643 /* When epilog_reduc_code is ERROR_MARK then a reduction will be
5644 generated in the epilog using multiple expressions. This does not
5645 work for condition reductions. */
5646 if (epilog_reduc_code == ERROR_MARK
5647 && (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
5648 == INTEGER_INDUC_COND_REDUCTION
5649 || STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
5650 == CONST_COND_REDUCTION))
5652 if (dump_enabled_p ())
5653 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5654 "no reduc code for scalar code.\n");
5655 return false;
5658 else
5660 if (!nested_cycle || double_reduc)
5662 if (dump_enabled_p ())
5663 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5664 "no reduc code for scalar code.\n");
5666 return false;
5670 else
5672 int scalar_precision = GET_MODE_PRECISION (TYPE_MODE (scalar_type));
5673 cr_index_scalar_type = make_unsigned_type (scalar_precision);
5674 cr_index_vector_type = build_vector_type
5675 (cr_index_scalar_type, TYPE_VECTOR_SUBPARTS (vectype_out));
5677 epilog_reduc_code = REDUC_MAX_EXPR;
5678 optab = optab_for_tree_code (REDUC_MAX_EXPR, cr_index_vector_type,
5679 optab_default);
5680 if (optab_handler (optab, TYPE_MODE (cr_index_vector_type))
5681 == CODE_FOR_nothing)
5683 if (dump_enabled_p ())
5684 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5685 "reduc max op not supported by target.\n");
5686 return false;
5690 if ((double_reduc
5691 || STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) != TREE_CODE_REDUCTION)
5692 && ncopies > 1)
5694 if (dump_enabled_p ())
5695 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5696 "multiple types in double reduction or condition "
5697 "reduction.\n");
5698 return false;
5701 /* In case of widenning multiplication by a constant, we update the type
5702 of the constant to be the type of the other operand. We check that the
5703 constant fits the type in the pattern recognition pass. */
5704 if (code == DOT_PROD_EXPR
5705 && !types_compatible_p (TREE_TYPE (ops[0]), TREE_TYPE (ops[1])))
5707 if (TREE_CODE (ops[0]) == INTEGER_CST)
5708 ops[0] = fold_convert (TREE_TYPE (ops[1]), ops[0]);
5709 else if (TREE_CODE (ops[1]) == INTEGER_CST)
5710 ops[1] = fold_convert (TREE_TYPE (ops[0]), ops[1]);
5711 else
5713 if (dump_enabled_p ())
5714 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5715 "invalid types in dot-prod\n");
5717 return false;
5721 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION)
5723 widest_int ni;
5725 if (! max_loop_iterations (loop, &ni))
5727 if (dump_enabled_p ())
5728 dump_printf_loc (MSG_NOTE, vect_location,
5729 "loop count not known, cannot create cond "
5730 "reduction.\n");
5731 return false;
5733 /* Convert backedges to iterations. */
5734 ni += 1;
5736 /* The additional index will be the same type as the condition. Check
5737 that the loop can fit into this less one (because we'll use up the
5738 zero slot for when there are no matches). */
5739 tree max_index = TYPE_MAX_VALUE (cr_index_scalar_type);
5740 if (wi::geu_p (ni, wi::to_widest (max_index)))
5742 if (dump_enabled_p ())
5743 dump_printf_loc (MSG_NOTE, vect_location,
5744 "loop size is greater than data size.\n");
5745 return false;
5749 if (!vec_stmt) /* transformation not required. */
5751 if (first_p)
5752 vect_model_reduction_cost (stmt_info, epilog_reduc_code, ncopies);
5753 STMT_VINFO_TYPE (stmt_info) = reduc_vec_info_type;
5754 return true;
5757 /* Transform. */
5759 if (dump_enabled_p ())
5760 dump_printf_loc (MSG_NOTE, vect_location, "transform reduction.\n");
5762 /* FORNOW: Multiple types are not supported for condition. */
5763 if (code == COND_EXPR)
5764 gcc_assert (ncopies == 1);
5766 /* Create the destination vector */
5767 vec_dest = vect_create_destination_var (scalar_dest, vectype_out);
5769 /* In case the vectorization factor (VF) is bigger than the number
5770 of elements that we can fit in a vectype (nunits), we have to generate
5771 more than one vector stmt - i.e - we need to "unroll" the
5772 vector stmt by a factor VF/nunits. For more details see documentation
5773 in vectorizable_operation. */
5775 /* If the reduction is used in an outer loop we need to generate
5776 VF intermediate results, like so (e.g. for ncopies=2):
5777 r0 = phi (init, r0)
5778 r1 = phi (init, r1)
5779 r0 = x0 + r0;
5780 r1 = x1 + r1;
5781 (i.e. we generate VF results in 2 registers).
5782 In this case we have a separate def-use cycle for each copy, and therefore
5783 for each copy we get the vector def for the reduction variable from the
5784 respective phi node created for this copy.
5786 Otherwise (the reduction is unused in the loop nest), we can combine
5787 together intermediate results, like so (e.g. for ncopies=2):
5788 r = phi (init, r)
5789 r = x0 + r;
5790 r = x1 + r;
5791 (i.e. we generate VF/2 results in a single register).
5792 In this case for each copy we get the vector def for the reduction variable
5793 from the vectorized reduction operation generated in the previous iteration.
5796 if (STMT_VINFO_RELEVANT (stmt_info) <= vect_used_only_live)
5798 single_defuse_cycle = true;
5799 epilog_copies = 1;
5801 else
5802 epilog_copies = ncopies;
5804 prev_stmt_info = NULL;
5805 prev_phi_info = NULL;
5806 if (slp_node)
5807 vec_num = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
5808 else
5810 vec_num = 1;
5811 vec_oprnds0.create (1);
5812 if (op_type == ternary_op)
5813 vec_oprnds1.create (1);
5816 phis.create (vec_num);
5817 vect_defs.create (vec_num);
5818 if (!slp_node)
5819 vect_defs.quick_push (NULL_TREE);
5821 for (j = 0; j < ncopies; j++)
5823 if (j == 0 || !single_defuse_cycle)
5825 for (i = 0; i < vec_num; i++)
5827 /* Create the reduction-phi that defines the reduction
5828 operand. */
5829 new_phi = create_phi_node (vec_dest, loop->header);
5830 set_vinfo_for_stmt (new_phi,
5831 new_stmt_vec_info (new_phi, loop_vinfo));
5832 if (j == 0 || slp_node)
5833 phis.quick_push (new_phi);
5837 if (code == COND_EXPR)
5839 gcc_assert (!slp_node);
5840 vectorizable_condition (stmt, gsi, vec_stmt,
5841 PHI_RESULT (phis[0]),
5842 reduc_index, NULL);
5843 /* Multiple types are not supported for condition. */
5844 break;
5847 /* Handle uses. */
5848 if (j == 0)
5850 if (slp_node)
5852 /* Get vec defs for all the operands except the reduction index,
5853 ensuring the ordering of the ops in the vector is kept. */
5854 auto_vec<tree, 3> slp_ops;
5855 auto_vec<vec<tree>, 3> vec_defs;
5857 slp_ops.quick_push (reduc_index == 0 ? NULL : ops[0]);
5858 slp_ops.quick_push (reduc_index == 1 ? NULL : ops[1]);
5859 if (op_type == ternary_op)
5860 slp_ops.quick_push (reduc_index == 2 ? NULL : ops[2]);
5862 vect_get_slp_defs (slp_ops, slp_node, &vec_defs, -1);
5864 vec_oprnds0.safe_splice (vec_defs[reduc_index == 0 ? 1 : 0]);
5865 vec_defs[reduc_index == 0 ? 1 : 0].release ();
5866 if (op_type == ternary_op)
5868 vec_oprnds1.safe_splice (vec_defs[reduc_index == 2 ? 1 : 2]);
5869 vec_defs[reduc_index == 2 ? 1 : 2].release ();
5872 else
5874 loop_vec_def0 = vect_get_vec_def_for_operand (ops[!reduc_index],
5875 stmt);
5876 vec_oprnds0.quick_push (loop_vec_def0);
5877 if (op_type == ternary_op)
5879 op1 = reduc_index == 0 ? ops[2] : ops[1];
5880 loop_vec_def1 = vect_get_vec_def_for_operand (op1, stmt);
5881 vec_oprnds1.quick_push (loop_vec_def1);
5885 else
5887 if (!slp_node)
5889 enum vect_def_type dt;
5890 gimple *dummy_stmt;
5892 vect_is_simple_use (ops[!reduc_index], loop_vinfo,
5893 &dummy_stmt, &dt);
5894 loop_vec_def0 = vect_get_vec_def_for_stmt_copy (dt,
5895 loop_vec_def0);
5896 vec_oprnds0[0] = loop_vec_def0;
5897 if (op_type == ternary_op)
5899 vect_is_simple_use (op1, loop_vinfo, &dummy_stmt, &dt);
5900 loop_vec_def1 = vect_get_vec_def_for_stmt_copy (dt,
5901 loop_vec_def1);
5902 vec_oprnds1[0] = loop_vec_def1;
5906 if (single_defuse_cycle)
5907 reduc_def = gimple_assign_lhs (new_stmt);
5909 STMT_VINFO_RELATED_STMT (prev_phi_info) = new_phi;
5912 FOR_EACH_VEC_ELT (vec_oprnds0, i, def0)
5914 if (slp_node)
5915 reduc_def = PHI_RESULT (phis[i]);
5916 else
5918 if (!single_defuse_cycle || j == 0)
5919 reduc_def = PHI_RESULT (new_phi);
5922 def1 = ((op_type == ternary_op)
5923 ? vec_oprnds1[i] : NULL);
5924 if (op_type == binary_op)
5926 if (reduc_index == 0)
5927 expr = build2 (code, vectype_out, reduc_def, def0);
5928 else
5929 expr = build2 (code, vectype_out, def0, reduc_def);
5931 else
5933 if (reduc_index == 0)
5934 expr = build3 (code, vectype_out, reduc_def, def0, def1);
5935 else
5937 if (reduc_index == 1)
5938 expr = build3 (code, vectype_out, def0, reduc_def, def1);
5939 else
5940 expr = build3 (code, vectype_out, def0, def1, reduc_def);
5944 new_stmt = gimple_build_assign (vec_dest, expr);
5945 new_temp = make_ssa_name (vec_dest, new_stmt);
5946 gimple_assign_set_lhs (new_stmt, new_temp);
5947 vect_finish_stmt_generation (stmt, new_stmt, gsi);
5949 if (slp_node)
5951 SLP_TREE_VEC_STMTS (slp_node).quick_push (new_stmt);
5952 vect_defs.quick_push (new_temp);
5954 else
5955 vect_defs[0] = new_temp;
5958 if (slp_node)
5959 continue;
5961 if (j == 0)
5962 STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
5963 else
5964 STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
5966 prev_stmt_info = vinfo_for_stmt (new_stmt);
5967 prev_phi_info = vinfo_for_stmt (new_phi);
5970 tree indx_before_incr, indx_after_incr, cond_name = NULL;
5972 /* Finalize the reduction-phi (set its arguments) and create the
5973 epilog reduction code. */
5974 if ((!single_defuse_cycle || code == COND_EXPR) && !slp_node)
5976 new_temp = gimple_assign_lhs (*vec_stmt);
5977 vect_defs[0] = new_temp;
5979 /* For cond reductions we want to create a new vector (INDEX_COND_EXPR)
5980 which is updated with the current index of the loop for every match of
5981 the original loop's cond_expr (VEC_STMT). This results in a vector
5982 containing the last time the condition passed for that vector lane.
5983 The first match will be a 1 to allow 0 to be used for non-matching
5984 indexes. If there are no matches at all then the vector will be all
5985 zeroes. */
5986 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION)
5988 int nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
5989 int k;
5991 gcc_assert (gimple_assign_rhs_code (*vec_stmt) == VEC_COND_EXPR);
5993 /* First we create a simple vector induction variable which starts
5994 with the values {1,2,3,...} (SERIES_VECT) and increments by the
5995 vector size (STEP). */
5997 /* Create a {1,2,3,...} vector. */
5998 tree *vtemp = XALLOCAVEC (tree, nunits_out);
5999 for (k = 0; k < nunits_out; ++k)
6000 vtemp[k] = build_int_cst (cr_index_scalar_type, k + 1);
6001 tree series_vect = build_vector (cr_index_vector_type, vtemp);
6003 /* Create a vector of the step value. */
6004 tree step = build_int_cst (cr_index_scalar_type, nunits_out);
6005 tree vec_step = build_vector_from_val (cr_index_vector_type, step);
6007 /* Create an induction variable. */
6008 gimple_stmt_iterator incr_gsi;
6009 bool insert_after;
6010 standard_iv_increment_position (loop, &incr_gsi, &insert_after);
6011 create_iv (series_vect, vec_step, NULL_TREE, loop, &incr_gsi,
6012 insert_after, &indx_before_incr, &indx_after_incr);
6014 /* Next create a new phi node vector (NEW_PHI_TREE) which starts
6015 filled with zeros (VEC_ZERO). */
6017 /* Create a vector of 0s. */
6018 tree zero = build_zero_cst (cr_index_scalar_type);
6019 tree vec_zero = build_vector_from_val (cr_index_vector_type, zero);
6021 /* Create a vector phi node. */
6022 tree new_phi_tree = make_ssa_name (cr_index_vector_type);
6023 new_phi = create_phi_node (new_phi_tree, loop->header);
6024 set_vinfo_for_stmt (new_phi,
6025 new_stmt_vec_info (new_phi, loop_vinfo));
6026 add_phi_arg (new_phi, vec_zero, loop_preheader_edge (loop),
6027 UNKNOWN_LOCATION);
6029 /* Now take the condition from the loops original cond_expr
6030 (VEC_STMT) and produce a new cond_expr (INDEX_COND_EXPR) which for
6031 every match uses values from the induction variable
6032 (INDEX_BEFORE_INCR) otherwise uses values from the phi node
6033 (NEW_PHI_TREE).
6034 Finally, we update the phi (NEW_PHI_TREE) to take the value of
6035 the new cond_expr (INDEX_COND_EXPR). */
6037 /* Duplicate the condition from vec_stmt. */
6038 tree ccompare = unshare_expr (gimple_assign_rhs1 (*vec_stmt));
6040 /* Create a conditional, where the condition is taken from vec_stmt
6041 (CCOMPARE), then is the induction index (INDEX_BEFORE_INCR) and
6042 else is the phi (NEW_PHI_TREE). */
6043 tree index_cond_expr = build3 (VEC_COND_EXPR, cr_index_vector_type,
6044 ccompare, indx_before_incr,
6045 new_phi_tree);
6046 cond_name = make_ssa_name (cr_index_vector_type);
6047 gimple *index_condition = gimple_build_assign (cond_name,
6048 index_cond_expr);
6049 gsi_insert_before (&incr_gsi, index_condition, GSI_SAME_STMT);
6050 stmt_vec_info index_vec_info = new_stmt_vec_info (index_condition,
6051 loop_vinfo);
6052 STMT_VINFO_VECTYPE (index_vec_info) = cr_index_vector_type;
6053 set_vinfo_for_stmt (index_condition, index_vec_info);
6055 /* Update the phi with the vec cond. */
6056 add_phi_arg (new_phi, cond_name, loop_latch_edge (loop),
6057 UNKNOWN_LOCATION);
6061 vect_create_epilog_for_reduction (vect_defs, stmt, epilog_copies,
6062 epilog_reduc_code, phis, reduc_index,
6063 double_reduc, slp_node, cond_name);
6065 return true;
6068 /* Function vect_min_worthwhile_factor.
6070 For a loop where we could vectorize the operation indicated by CODE,
6071 return the minimum vectorization factor that makes it worthwhile
6072 to use generic vectors. */
6074 vect_min_worthwhile_factor (enum tree_code code)
6076 switch (code)
6078 case PLUS_EXPR:
6079 case MINUS_EXPR:
6080 case NEGATE_EXPR:
6081 return 4;
6083 case BIT_AND_EXPR:
6084 case BIT_IOR_EXPR:
6085 case BIT_XOR_EXPR:
6086 case BIT_NOT_EXPR:
6087 return 2;
6089 default:
6090 return INT_MAX;
6095 /* Function vectorizable_induction
6097 Check if PHI performs an induction computation that can be vectorized.
6098 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
6099 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
6100 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
6102 bool
6103 vectorizable_induction (gimple *phi,
6104 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
6105 gimple **vec_stmt, slp_tree slp_node)
6107 stmt_vec_info stmt_info = vinfo_for_stmt (phi);
6108 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
6109 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
6110 unsigned ncopies;
6111 bool nested_in_vect_loop = false;
6112 struct loop *iv_loop;
6113 tree vec_def;
6114 edge pe = loop_preheader_edge (loop);
6115 basic_block new_bb;
6116 tree new_vec, vec_init, vec_step, t;
6117 tree new_name;
6118 gimple *new_stmt;
6119 gphi *induction_phi;
6120 tree induc_def, vec_dest;
6121 tree init_expr, step_expr;
6122 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
6123 unsigned i;
6124 tree expr;
6125 gimple_seq stmts;
6126 imm_use_iterator imm_iter;
6127 use_operand_p use_p;
6128 gimple *exit_phi;
6129 edge latch_e;
6130 tree loop_arg;
6131 gimple_stmt_iterator si;
6132 basic_block bb = gimple_bb (phi);
6134 if (gimple_code (phi) != GIMPLE_PHI)
6135 return false;
6137 if (!STMT_VINFO_RELEVANT_P (stmt_info))
6138 return false;
6140 /* Make sure it was recognized as induction computation. */
6141 if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_induction_def)
6142 return false;
6144 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
6145 unsigned nunits = TYPE_VECTOR_SUBPARTS (vectype);
6147 if (slp_node)
6148 ncopies = 1;
6149 else
6150 ncopies = vf / nunits;
6151 gcc_assert (ncopies >= 1);
6153 /* FORNOW. These restrictions should be relaxed. */
6154 if (nested_in_vect_loop_p (loop, phi))
6156 imm_use_iterator imm_iter;
6157 use_operand_p use_p;
6158 gimple *exit_phi;
6159 edge latch_e;
6160 tree loop_arg;
6162 if (ncopies > 1)
6164 if (dump_enabled_p ())
6165 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
6166 "multiple types in nested loop.\n");
6167 return false;
6170 /* FORNOW: outer loop induction with SLP not supported. */
6171 if (STMT_SLP_TYPE (stmt_info))
6172 return false;
6174 exit_phi = NULL;
6175 latch_e = loop_latch_edge (loop->inner);
6176 loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
6177 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, loop_arg)
6179 gimple *use_stmt = USE_STMT (use_p);
6180 if (is_gimple_debug (use_stmt))
6181 continue;
6183 if (!flow_bb_inside_loop_p (loop->inner, gimple_bb (use_stmt)))
6185 exit_phi = use_stmt;
6186 break;
6189 if (exit_phi)
6191 stmt_vec_info exit_phi_vinfo = vinfo_for_stmt (exit_phi);
6192 if (!(STMT_VINFO_RELEVANT_P (exit_phi_vinfo)
6193 && !STMT_VINFO_LIVE_P (exit_phi_vinfo)))
6195 if (dump_enabled_p ())
6196 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
6197 "inner-loop induction only used outside "
6198 "of the outer vectorized loop.\n");
6199 return false;
6203 nested_in_vect_loop = true;
6204 iv_loop = loop->inner;
6206 else
6207 iv_loop = loop;
6208 gcc_assert (iv_loop == (gimple_bb (phi))->loop_father);
6210 if (!vec_stmt) /* transformation not required. */
6212 STMT_VINFO_TYPE (stmt_info) = induc_vec_info_type;
6213 if (dump_enabled_p ())
6214 dump_printf_loc (MSG_NOTE, vect_location,
6215 "=== vectorizable_induction ===\n");
6216 vect_model_induction_cost (stmt_info, ncopies);
6217 return true;
6220 /* Transform. */
6222 /* Compute a vector variable, initialized with the first VF values of
6223 the induction variable. E.g., for an iv with IV_PHI='X' and
6224 evolution S, for a vector of 4 units, we want to compute:
6225 [X, X + S, X + 2*S, X + 3*S]. */
6227 if (dump_enabled_p ())
6228 dump_printf_loc (MSG_NOTE, vect_location, "transform induction phi.\n");
6230 latch_e = loop_latch_edge (iv_loop);
6231 loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
6233 step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info);
6234 gcc_assert (step_expr != NULL_TREE);
6236 pe = loop_preheader_edge (iv_loop);
6237 init_expr = PHI_ARG_DEF_FROM_EDGE (phi,
6238 loop_preheader_edge (iv_loop));
6240 /* Convert the step to the desired type. */
6241 stmts = NULL;
6242 step_expr = gimple_convert (&stmts, TREE_TYPE (vectype), step_expr);
6243 if (stmts)
6245 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
6246 gcc_assert (!new_bb);
6249 /* Find the first insertion point in the BB. */
6250 si = gsi_after_labels (bb);
6252 /* For SLP induction we have to generate several IVs as for example
6253 with group size 3 we need [i, i, i, i + S] [i + S, i + S, i + 2*S, i + 2*S]
6254 [i + 2*S, i + 3*S, i + 3*S, i + 3*S]. The step is the same uniform
6255 [VF*S, VF*S, VF*S, VF*S] for all. */
6256 if (slp_node)
6258 /* Convert the init to the desired type. */
6259 stmts = NULL;
6260 init_expr = gimple_convert (&stmts, TREE_TYPE (vectype), init_expr);
6261 if (stmts)
6263 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
6264 gcc_assert (!new_bb);
6267 /* Generate [VF*S, VF*S, ... ]. */
6268 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr)))
6270 expr = build_int_cst (integer_type_node, vf);
6271 expr = fold_convert (TREE_TYPE (step_expr), expr);
6273 else
6274 expr = build_int_cst (TREE_TYPE (step_expr), vf);
6275 new_name = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr),
6276 expr, step_expr);
6277 if (! CONSTANT_CLASS_P (new_name))
6278 new_name = vect_init_vector (phi, new_name,
6279 TREE_TYPE (step_expr), NULL);
6280 new_vec = build_vector_from_val (vectype, new_name);
6281 vec_step = vect_init_vector (phi, new_vec, vectype, NULL);
6283 /* Now generate the IVs. */
6284 unsigned group_size = SLP_TREE_SCALAR_STMTS (slp_node).length ();
6285 unsigned nvects = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
6286 unsigned elts = nunits * nvects;
6287 unsigned nivs = least_common_multiple (group_size, nunits) / nunits;
6288 gcc_assert (elts % group_size == 0);
6289 tree elt = init_expr;
6290 unsigned ivn;
6291 for (ivn = 0; ivn < nivs; ++ivn)
6293 tree *elts = XALLOCAVEC (tree, nunits);
6294 bool constant_p = true;
6295 for (unsigned eltn = 0; eltn < nunits; ++eltn)
6297 if (ivn*nunits + eltn >= group_size
6298 && (ivn*nunits + eltn) % group_size == 0)
6300 stmts = NULL;
6301 elt = gimple_build (&stmts, PLUS_EXPR, TREE_TYPE (elt),
6302 elt, step_expr);
6303 if (stmts)
6305 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
6306 gcc_assert (!new_bb);
6309 if (! CONSTANT_CLASS_P (elt))
6310 constant_p = false;
6311 elts[eltn] = elt;
6313 if (constant_p)
6314 new_vec = build_vector (vectype, elts);
6315 else
6317 vec<constructor_elt, va_gc> *v;
6318 vec_alloc (v, nunits);
6319 for (i = 0; i < nunits; ++i)
6320 CONSTRUCTOR_APPEND_ELT (v, NULL_TREE, elts[i]);
6321 new_vec = build_constructor (vectype, v);
6323 vec_init = vect_init_vector (phi, new_vec, vectype, NULL);
6325 /* Create the induction-phi that defines the induction-operand. */
6326 vec_dest = vect_get_new_vect_var (vectype, vect_simple_var, "vec_iv_");
6327 induction_phi = create_phi_node (vec_dest, iv_loop->header);
6328 set_vinfo_for_stmt (induction_phi,
6329 new_stmt_vec_info (induction_phi, loop_vinfo));
6330 induc_def = PHI_RESULT (induction_phi);
6332 /* Create the iv update inside the loop */
6333 vec_def = make_ssa_name (vec_dest);
6334 new_stmt = gimple_build_assign (vec_def, PLUS_EXPR, induc_def, vec_step);
6335 gsi_insert_before (&si, new_stmt, GSI_SAME_STMT);
6336 set_vinfo_for_stmt (new_stmt, new_stmt_vec_info (new_stmt, loop_vinfo));
6338 /* Set the arguments of the phi node: */
6339 add_phi_arg (induction_phi, vec_init, pe, UNKNOWN_LOCATION);
6340 add_phi_arg (induction_phi, vec_def, loop_latch_edge (iv_loop),
6341 UNKNOWN_LOCATION);
6343 SLP_TREE_VEC_STMTS (slp_node).quick_push (induction_phi);
6346 /* Re-use IVs when we can. */
6347 if (ivn < nvects)
6349 unsigned vfp
6350 = least_common_multiple (group_size, nunits) / group_size;
6351 /* Generate [VF'*S, VF'*S, ... ]. */
6352 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr)))
6354 expr = build_int_cst (integer_type_node, vfp);
6355 expr = fold_convert (TREE_TYPE (step_expr), expr);
6357 else
6358 expr = build_int_cst (TREE_TYPE (step_expr), vfp);
6359 new_name = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr),
6360 expr, step_expr);
6361 if (! CONSTANT_CLASS_P (new_name))
6362 new_name = vect_init_vector (phi, new_name,
6363 TREE_TYPE (step_expr), NULL);
6364 new_vec = build_vector_from_val (vectype, new_name);
6365 vec_step = vect_init_vector (phi, new_vec, vectype, NULL);
6366 for (; ivn < nvects; ++ivn)
6368 gimple *iv = SLP_TREE_VEC_STMTS (slp_node)[ivn - nivs];
6369 tree def;
6370 if (gimple_code (iv) == GIMPLE_PHI)
6371 def = gimple_phi_result (iv);
6372 else
6373 def = gimple_assign_lhs (iv);
6374 new_stmt = gimple_build_assign (make_ssa_name (vectype),
6375 PLUS_EXPR,
6376 def, vec_step);
6377 if (gimple_code (iv) == GIMPLE_PHI)
6378 gsi_insert_before (&si, new_stmt, GSI_SAME_STMT);
6379 else
6381 gimple_stmt_iterator tgsi = gsi_for_stmt (iv);
6382 gsi_insert_after (&tgsi, new_stmt, GSI_CONTINUE_LINKING);
6384 set_vinfo_for_stmt (new_stmt,
6385 new_stmt_vec_info (new_stmt, loop_vinfo));
6386 SLP_TREE_VEC_STMTS (slp_node).quick_push (new_stmt);
6390 return true;
6393 /* Create the vector that holds the initial_value of the induction. */
6394 if (nested_in_vect_loop)
6396 /* iv_loop is nested in the loop to be vectorized. init_expr had already
6397 been created during vectorization of previous stmts. We obtain it
6398 from the STMT_VINFO_VEC_STMT of the defining stmt. */
6399 vec_init = vect_get_vec_def_for_operand (init_expr, phi);
6400 /* If the initial value is not of proper type, convert it. */
6401 if (!useless_type_conversion_p (vectype, TREE_TYPE (vec_init)))
6403 new_stmt
6404 = gimple_build_assign (vect_get_new_ssa_name (vectype,
6405 vect_simple_var,
6406 "vec_iv_"),
6407 VIEW_CONVERT_EXPR,
6408 build1 (VIEW_CONVERT_EXPR, vectype,
6409 vec_init));
6410 vec_init = gimple_assign_lhs (new_stmt);
6411 new_bb = gsi_insert_on_edge_immediate (loop_preheader_edge (iv_loop),
6412 new_stmt);
6413 gcc_assert (!new_bb);
6414 set_vinfo_for_stmt (new_stmt,
6415 new_stmt_vec_info (new_stmt, loop_vinfo));
6418 else
6420 vec<constructor_elt, va_gc> *v;
6422 /* iv_loop is the loop to be vectorized. Create:
6423 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
6424 stmts = NULL;
6425 new_name = gimple_convert (&stmts, TREE_TYPE (vectype), init_expr);
6427 vec_alloc (v, nunits);
6428 bool constant_p = is_gimple_min_invariant (new_name);
6429 CONSTRUCTOR_APPEND_ELT (v, NULL_TREE, new_name);
6430 for (i = 1; i < nunits; i++)
6432 /* Create: new_name_i = new_name + step_expr */
6433 new_name = gimple_build (&stmts, PLUS_EXPR, TREE_TYPE (new_name),
6434 new_name, step_expr);
6435 if (!is_gimple_min_invariant (new_name))
6436 constant_p = false;
6437 CONSTRUCTOR_APPEND_ELT (v, NULL_TREE, new_name);
6439 if (stmts)
6441 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
6442 gcc_assert (!new_bb);
6445 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
6446 if (constant_p)
6447 new_vec = build_vector_from_ctor (vectype, v);
6448 else
6449 new_vec = build_constructor (vectype, v);
6450 vec_init = vect_init_vector (phi, new_vec, vectype, NULL);
6454 /* Create the vector that holds the step of the induction. */
6455 if (nested_in_vect_loop)
6456 /* iv_loop is nested in the loop to be vectorized. Generate:
6457 vec_step = [S, S, S, S] */
6458 new_name = step_expr;
6459 else
6461 /* iv_loop is the loop to be vectorized. Generate:
6462 vec_step = [VF*S, VF*S, VF*S, VF*S] */
6463 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr)))
6465 expr = build_int_cst (integer_type_node, vf);
6466 expr = fold_convert (TREE_TYPE (step_expr), expr);
6468 else
6469 expr = build_int_cst (TREE_TYPE (step_expr), vf);
6470 new_name = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr),
6471 expr, step_expr);
6472 if (TREE_CODE (step_expr) == SSA_NAME)
6473 new_name = vect_init_vector (phi, new_name,
6474 TREE_TYPE (step_expr), NULL);
6477 t = unshare_expr (new_name);
6478 gcc_assert (CONSTANT_CLASS_P (new_name)
6479 || TREE_CODE (new_name) == SSA_NAME);
6480 new_vec = build_vector_from_val (vectype, t);
6481 vec_step = vect_init_vector (phi, new_vec, vectype, NULL);
6484 /* Create the following def-use cycle:
6485 loop prolog:
6486 vec_init = ...
6487 vec_step = ...
6488 loop:
6489 vec_iv = PHI <vec_init, vec_loop>
6491 STMT
6493 vec_loop = vec_iv + vec_step; */
6495 /* Create the induction-phi that defines the induction-operand. */
6496 vec_dest = vect_get_new_vect_var (vectype, vect_simple_var, "vec_iv_");
6497 induction_phi = create_phi_node (vec_dest, iv_loop->header);
6498 set_vinfo_for_stmt (induction_phi,
6499 new_stmt_vec_info (induction_phi, loop_vinfo));
6500 induc_def = PHI_RESULT (induction_phi);
6502 /* Create the iv update inside the loop */
6503 vec_def = make_ssa_name (vec_dest);
6504 new_stmt = gimple_build_assign (vec_def, PLUS_EXPR, induc_def, vec_step);
6505 gsi_insert_before (&si, new_stmt, GSI_SAME_STMT);
6506 set_vinfo_for_stmt (new_stmt, new_stmt_vec_info (new_stmt, loop_vinfo));
6508 /* Set the arguments of the phi node: */
6509 add_phi_arg (induction_phi, vec_init, pe, UNKNOWN_LOCATION);
6510 add_phi_arg (induction_phi, vec_def, loop_latch_edge (iv_loop),
6511 UNKNOWN_LOCATION);
6513 STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = induction_phi;
6515 /* In case that vectorization factor (VF) is bigger than the number
6516 of elements that we can fit in a vectype (nunits), we have to generate
6517 more than one vector stmt - i.e - we need to "unroll" the
6518 vector stmt by a factor VF/nunits. For more details see documentation
6519 in vectorizable_operation. */
6521 if (ncopies > 1)
6523 stmt_vec_info prev_stmt_vinfo;
6524 /* FORNOW. This restriction should be relaxed. */
6525 gcc_assert (!nested_in_vect_loop);
6527 /* Create the vector that holds the step of the induction. */
6528 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr)))
6530 expr = build_int_cst (integer_type_node, nunits);
6531 expr = fold_convert (TREE_TYPE (step_expr), expr);
6533 else
6534 expr = build_int_cst (TREE_TYPE (step_expr), nunits);
6535 new_name = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr),
6536 expr, step_expr);
6537 if (TREE_CODE (step_expr) == SSA_NAME)
6538 new_name = vect_init_vector (phi, new_name,
6539 TREE_TYPE (step_expr), NULL);
6540 t = unshare_expr (new_name);
6541 gcc_assert (CONSTANT_CLASS_P (new_name)
6542 || TREE_CODE (new_name) == SSA_NAME);
6543 new_vec = build_vector_from_val (vectype, t);
6544 vec_step = vect_init_vector (phi, new_vec, vectype, NULL);
6546 vec_def = induc_def;
6547 prev_stmt_vinfo = vinfo_for_stmt (induction_phi);
6548 for (i = 1; i < ncopies; i++)
6550 /* vec_i = vec_prev + vec_step */
6551 new_stmt = gimple_build_assign (vec_dest, PLUS_EXPR,
6552 vec_def, vec_step);
6553 vec_def = make_ssa_name (vec_dest, new_stmt);
6554 gimple_assign_set_lhs (new_stmt, vec_def);
6556 gsi_insert_before (&si, new_stmt, GSI_SAME_STMT);
6557 set_vinfo_for_stmt (new_stmt,
6558 new_stmt_vec_info (new_stmt, loop_vinfo));
6559 STMT_VINFO_RELATED_STMT (prev_stmt_vinfo) = new_stmt;
6560 prev_stmt_vinfo = vinfo_for_stmt (new_stmt);
6564 if (nested_in_vect_loop)
6566 /* Find the loop-closed exit-phi of the induction, and record
6567 the final vector of induction results: */
6568 exit_phi = NULL;
6569 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, loop_arg)
6571 gimple *use_stmt = USE_STMT (use_p);
6572 if (is_gimple_debug (use_stmt))
6573 continue;
6575 if (!flow_bb_inside_loop_p (iv_loop, gimple_bb (use_stmt)))
6577 exit_phi = use_stmt;
6578 break;
6581 if (exit_phi)
6583 stmt_vec_info stmt_vinfo = vinfo_for_stmt (exit_phi);
6584 /* FORNOW. Currently not supporting the case that an inner-loop induction
6585 is not used in the outer-loop (i.e. only outside the outer-loop). */
6586 gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo)
6587 && !STMT_VINFO_LIVE_P (stmt_vinfo));
6589 STMT_VINFO_VEC_STMT (stmt_vinfo) = new_stmt;
6590 if (dump_enabled_p ())
6592 dump_printf_loc (MSG_NOTE, vect_location,
6593 "vector of inductions after inner-loop:");
6594 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, new_stmt, 0);
6600 if (dump_enabled_p ())
6602 dump_printf_loc (MSG_NOTE, vect_location,
6603 "transform induction: created def-use cycle: ");
6604 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, induction_phi, 0);
6605 dump_gimple_stmt (MSG_NOTE, TDF_SLIM,
6606 SSA_NAME_DEF_STMT (vec_def), 0);
6609 return true;
6612 /* Function vectorizable_live_operation.
6614 STMT computes a value that is used outside the loop. Check if
6615 it can be supported. */
6617 bool
6618 vectorizable_live_operation (gimple *stmt,
6619 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
6620 slp_tree slp_node, int slp_index,
6621 gimple **vec_stmt)
6623 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
6624 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
6625 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
6626 imm_use_iterator imm_iter;
6627 tree lhs, lhs_type, bitsize, vec_bitsize;
6628 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
6629 int nunits = TYPE_VECTOR_SUBPARTS (vectype);
6630 int ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
6631 gimple *use_stmt;
6632 auto_vec<tree> vec_oprnds;
6634 gcc_assert (STMT_VINFO_LIVE_P (stmt_info));
6636 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_reduction_def)
6637 return false;
6639 /* FORNOW. CHECKME. */
6640 if (nested_in_vect_loop_p (loop, stmt))
6641 return false;
6643 /* If STMT is not relevant and it is a simple assignment and its inputs are
6644 invariant then it can remain in place, unvectorized. The original last
6645 scalar value that it computes will be used. */
6646 if (!STMT_VINFO_RELEVANT_P (stmt_info))
6648 gcc_assert (is_simple_and_all_uses_invariant (stmt, loop_vinfo));
6649 if (dump_enabled_p ())
6650 dump_printf_loc (MSG_NOTE, vect_location,
6651 "statement is simple and uses invariant. Leaving in "
6652 "place.\n");
6653 return true;
6656 if (!vec_stmt)
6657 /* No transformation required. */
6658 return true;
6660 /* If stmt has a related stmt, then use that for getting the lhs. */
6661 if (is_pattern_stmt_p (stmt_info))
6662 stmt = STMT_VINFO_RELATED_STMT (stmt_info);
6664 lhs = (is_a <gphi *> (stmt)) ? gimple_phi_result (stmt)
6665 : gimple_get_lhs (stmt);
6666 lhs_type = TREE_TYPE (lhs);
6668 bitsize = TYPE_SIZE (TREE_TYPE (vectype));
6669 vec_bitsize = TYPE_SIZE (vectype);
6671 /* Get the vectorized lhs of STMT and the lane to use (counted in bits). */
6672 tree vec_lhs, bitstart;
6673 if (slp_node)
6675 gcc_assert (slp_index >= 0);
6677 int num_scalar = SLP_TREE_SCALAR_STMTS (slp_node).length ();
6678 int num_vec = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
6680 /* Get the last occurrence of the scalar index from the concatenation of
6681 all the slp vectors. Calculate which slp vector it is and the index
6682 within. */
6683 int pos = (num_vec * nunits) - num_scalar + slp_index;
6684 int vec_entry = pos / nunits;
6685 int vec_index = pos % nunits;
6687 /* Get the correct slp vectorized stmt. */
6688 vec_lhs = gimple_get_lhs (SLP_TREE_VEC_STMTS (slp_node)[vec_entry]);
6690 /* Get entry to use. */
6691 bitstart = build_int_cst (unsigned_type_node, vec_index);
6692 bitstart = int_const_binop (MULT_EXPR, bitsize, bitstart);
6694 else
6696 enum vect_def_type dt = STMT_VINFO_DEF_TYPE (stmt_info);
6697 vec_lhs = vect_get_vec_def_for_operand_1 (stmt, dt);
6699 /* For multiple copies, get the last copy. */
6700 for (int i = 1; i < ncopies; ++i)
6701 vec_lhs = vect_get_vec_def_for_stmt_copy (vect_unknown_def_type,
6702 vec_lhs);
6704 /* Get the last lane in the vector. */
6705 bitstart = int_const_binop (MINUS_EXPR, vec_bitsize, bitsize);
6708 /* Create a new vectorized stmt for the uses of STMT and insert outside the
6709 loop. */
6710 gimple_seq stmts = NULL;
6711 tree bftype = TREE_TYPE (vectype);
6712 if (VECTOR_BOOLEAN_TYPE_P (vectype))
6713 bftype = build_nonstandard_integer_type (tree_to_uhwi (bitsize), 1);
6714 tree new_tree = build3 (BIT_FIELD_REF, bftype, vec_lhs, bitsize, bitstart);
6715 new_tree = force_gimple_operand (fold_convert (lhs_type, new_tree), &stmts,
6716 true, NULL_TREE);
6717 if (stmts)
6718 gsi_insert_seq_on_edge_immediate (single_exit (loop), stmts);
6720 /* Replace use of lhs with newly computed result. If the use stmt is a
6721 single arg PHI, just replace all uses of PHI result. It's necessary
6722 because lcssa PHI defining lhs may be before newly inserted stmt. */
6723 use_operand_p use_p;
6724 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs)
6725 if (!flow_bb_inside_loop_p (loop, gimple_bb (use_stmt))
6726 && !is_gimple_debug (use_stmt))
6728 if (gimple_code (use_stmt) == GIMPLE_PHI
6729 && gimple_phi_num_args (use_stmt) == 1)
6731 replace_uses_by (gimple_phi_result (use_stmt), new_tree);
6733 else
6735 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
6736 SET_USE (use_p, new_tree);
6738 update_stmt (use_stmt);
6741 return true;
6744 /* Kill any debug uses outside LOOP of SSA names defined in STMT. */
6746 static void
6747 vect_loop_kill_debug_uses (struct loop *loop, gimple *stmt)
6749 ssa_op_iter op_iter;
6750 imm_use_iterator imm_iter;
6751 def_operand_p def_p;
6752 gimple *ustmt;
6754 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_DEF)
6756 FOR_EACH_IMM_USE_STMT (ustmt, imm_iter, DEF_FROM_PTR (def_p))
6758 basic_block bb;
6760 if (!is_gimple_debug (ustmt))
6761 continue;
6763 bb = gimple_bb (ustmt);
6765 if (!flow_bb_inside_loop_p (loop, bb))
6767 if (gimple_debug_bind_p (ustmt))
6769 if (dump_enabled_p ())
6770 dump_printf_loc (MSG_NOTE, vect_location,
6771 "killing debug use\n");
6773 gimple_debug_bind_reset_value (ustmt);
6774 update_stmt (ustmt);
6776 else
6777 gcc_unreachable ();
6783 /* Given loop represented by LOOP_VINFO, return true if computation of
6784 LOOP_VINFO_NITERS (= LOOP_VINFO_NITERSM1 + 1) doesn't overflow, false
6785 otherwise. */
6787 static bool
6788 loop_niters_no_overflow (loop_vec_info loop_vinfo)
6790 /* Constant case. */
6791 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
6793 tree cst_niters = LOOP_VINFO_NITERS (loop_vinfo);
6794 tree cst_nitersm1 = LOOP_VINFO_NITERSM1 (loop_vinfo);
6796 gcc_assert (TREE_CODE (cst_niters) == INTEGER_CST);
6797 gcc_assert (TREE_CODE (cst_nitersm1) == INTEGER_CST);
6798 if (wi::to_widest (cst_nitersm1) < wi::to_widest (cst_niters))
6799 return true;
6802 widest_int max;
6803 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
6804 /* Check the upper bound of loop niters. */
6805 if (get_max_loop_iterations (loop, &max))
6807 tree type = TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo));
6808 signop sgn = TYPE_SIGN (type);
6809 widest_int type_max = widest_int::from (wi::max_value (type), sgn);
6810 if (max < type_max)
6811 return true;
6813 return false;
6816 /* Scale profiling counters by estimation for LOOP which is vectorized
6817 by factor VF. */
6819 static void
6820 scale_profile_for_vect_loop (struct loop *loop, unsigned vf)
6822 edge preheader = loop_preheader_edge (loop);
6823 /* Reduce loop iterations by the vectorization factor. */
6824 gcov_type new_est_niter = niter_for_unrolled_loop (loop, vf);
6825 profile_count freq_h = loop->header->count, freq_e = preheader->count;
6827 /* Use frequency only if counts are zero. */
6828 if (!(freq_h > 0) && !(freq_e > 0))
6830 freq_h = profile_count::from_gcov_type (loop->header->frequency);
6831 freq_e = profile_count::from_gcov_type (EDGE_FREQUENCY (preheader));
6833 if (freq_h > 0)
6835 gcov_type scale;
6837 /* Avoid dropping loop body profile counter to 0 because of zero count
6838 in loop's preheader. */
6839 if (!(freq_e > profile_count::from_gcov_type (1)))
6840 freq_e = profile_count::from_gcov_type (1);
6841 /* This should not overflow. */
6842 scale = freq_e.apply_scale (new_est_niter + 1, 1).probability_in (freq_h);
6843 scale_loop_frequencies (loop, scale, REG_BR_PROB_BASE);
6846 basic_block exit_bb = single_pred (loop->latch);
6847 edge exit_e = single_exit (loop);
6848 exit_e->count = loop_preheader_edge (loop)->count;
6849 exit_e->probability = REG_BR_PROB_BASE / (new_est_niter + 1);
6851 edge exit_l = single_pred_edge (loop->latch);
6852 int prob = exit_l->probability;
6853 exit_l->probability = REG_BR_PROB_BASE - exit_e->probability;
6854 exit_l->count = exit_bb->count - exit_e->count;
6855 if (prob > 0)
6856 scale_bbs_frequencies_int (&loop->latch, 1, exit_l->probability, prob);
6859 /* Function vect_transform_loop.
6861 The analysis phase has determined that the loop is vectorizable.
6862 Vectorize the loop - created vectorized stmts to replace the scalar
6863 stmts in the loop, and update the loop exit condition.
6864 Returns scalar epilogue loop if any. */
6866 struct loop *
6867 vect_transform_loop (loop_vec_info loop_vinfo)
6869 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
6870 struct loop *epilogue = NULL;
6871 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
6872 int nbbs = loop->num_nodes;
6873 int i;
6874 tree niters_vector = NULL;
6875 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
6876 bool grouped_store;
6877 bool slp_scheduled = false;
6878 gimple *stmt, *pattern_stmt;
6879 gimple_seq pattern_def_seq = NULL;
6880 gimple_stmt_iterator pattern_def_si = gsi_none ();
6881 bool transform_pattern_stmt = false;
6882 bool check_profitability = false;
6883 int th;
6885 if (dump_enabled_p ())
6886 dump_printf_loc (MSG_NOTE, vect_location, "=== vec_transform_loop ===\n");
6888 /* Use the more conservative vectorization threshold. If the number
6889 of iterations is constant assume the cost check has been performed
6890 by our caller. If the threshold makes all loops profitable that
6891 run at least the vectorization factor number of times checking
6892 is pointless, too. */
6893 th = LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo);
6894 if (th >= LOOP_VINFO_VECT_FACTOR (loop_vinfo) - 1
6895 && !LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
6897 if (dump_enabled_p ())
6898 dump_printf_loc (MSG_NOTE, vect_location,
6899 "Profitability threshold is %d loop iterations.\n",
6900 th);
6901 check_profitability = true;
6904 /* Make sure there exists a single-predecessor exit bb. Do this before
6905 versioning. */
6906 edge e = single_exit (loop);
6907 if (! single_pred_p (e->dest))
6909 split_loop_exit_edge (e);
6910 if (dump_enabled_p ())
6911 dump_printf (MSG_NOTE, "split exit edge\n");
6914 /* Version the loop first, if required, so the profitability check
6915 comes first. */
6917 if (LOOP_REQUIRES_VERSIONING (loop_vinfo))
6919 vect_loop_versioning (loop_vinfo, th, check_profitability);
6920 check_profitability = false;
6923 /* Make sure there exists a single-predecessor exit bb also on the
6924 scalar loop copy. Do this after versioning but before peeling
6925 so CFG structure is fine for both scalar and if-converted loop
6926 to make slpeel_duplicate_current_defs_from_edges face matched
6927 loop closed PHI nodes on the exit. */
6928 if (LOOP_VINFO_SCALAR_LOOP (loop_vinfo))
6930 e = single_exit (LOOP_VINFO_SCALAR_LOOP (loop_vinfo));
6931 if (! single_pred_p (e->dest))
6933 split_loop_exit_edge (e);
6934 if (dump_enabled_p ())
6935 dump_printf (MSG_NOTE, "split exit edge of scalar loop\n");
6939 tree niters = vect_build_loop_niters (loop_vinfo);
6940 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo) = niters;
6941 tree nitersm1 = unshare_expr (LOOP_VINFO_NITERSM1 (loop_vinfo));
6942 bool niters_no_overflow = loop_niters_no_overflow (loop_vinfo);
6943 epilogue = vect_do_peeling (loop_vinfo, niters, nitersm1, &niters_vector, th,
6944 check_profitability, niters_no_overflow);
6945 if (niters_vector == NULL_TREE)
6947 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
6948 niters_vector
6949 = build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo)),
6950 LOOP_VINFO_INT_NITERS (loop_vinfo) / vf);
6951 else
6952 vect_gen_vector_loop_niters (loop_vinfo, niters, &niters_vector,
6953 niters_no_overflow);
6956 /* 1) Make sure the loop header has exactly two entries
6957 2) Make sure we have a preheader basic block. */
6959 gcc_assert (EDGE_COUNT (loop->header->preds) == 2);
6961 split_edge (loop_preheader_edge (loop));
6963 /* FORNOW: the vectorizer supports only loops which body consist
6964 of one basic block (header + empty latch). When the vectorizer will
6965 support more involved loop forms, the order by which the BBs are
6966 traversed need to be reconsidered. */
6968 for (i = 0; i < nbbs; i++)
6970 basic_block bb = bbs[i];
6971 stmt_vec_info stmt_info;
6973 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
6974 gsi_next (&si))
6976 gphi *phi = si.phi ();
6977 if (dump_enabled_p ())
6979 dump_printf_loc (MSG_NOTE, vect_location,
6980 "------>vectorizing phi: ");
6981 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
6983 stmt_info = vinfo_for_stmt (phi);
6984 if (!stmt_info)
6985 continue;
6987 if (MAY_HAVE_DEBUG_STMTS && !STMT_VINFO_LIVE_P (stmt_info))
6988 vect_loop_kill_debug_uses (loop, phi);
6990 if (!STMT_VINFO_RELEVANT_P (stmt_info)
6991 && !STMT_VINFO_LIVE_P (stmt_info))
6992 continue;
6994 if (STMT_VINFO_VECTYPE (stmt_info)
6995 && (TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info))
6996 != (unsigned HOST_WIDE_INT) vf)
6997 && dump_enabled_p ())
6998 dump_printf_loc (MSG_NOTE, vect_location, "multiple-types.\n");
7000 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def
7001 && ! PURE_SLP_STMT (stmt_info))
7003 if (dump_enabled_p ())
7004 dump_printf_loc (MSG_NOTE, vect_location, "transform phi.\n");
7005 vect_transform_stmt (phi, NULL, NULL, NULL, NULL);
7009 pattern_stmt = NULL;
7010 for (gimple_stmt_iterator si = gsi_start_bb (bb);
7011 !gsi_end_p (si) || transform_pattern_stmt;)
7013 bool is_store;
7015 if (transform_pattern_stmt)
7016 stmt = pattern_stmt;
7017 else
7019 stmt = gsi_stmt (si);
7020 /* During vectorization remove existing clobber stmts. */
7021 if (gimple_clobber_p (stmt))
7023 unlink_stmt_vdef (stmt);
7024 gsi_remove (&si, true);
7025 release_defs (stmt);
7026 continue;
7030 if (dump_enabled_p ())
7032 dump_printf_loc (MSG_NOTE, vect_location,
7033 "------>vectorizing statement: ");
7034 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
7037 stmt_info = vinfo_for_stmt (stmt);
7039 /* vector stmts created in the outer-loop during vectorization of
7040 stmts in an inner-loop may not have a stmt_info, and do not
7041 need to be vectorized. */
7042 if (!stmt_info)
7044 gsi_next (&si);
7045 continue;
7048 if (MAY_HAVE_DEBUG_STMTS && !STMT_VINFO_LIVE_P (stmt_info))
7049 vect_loop_kill_debug_uses (loop, stmt);
7051 if (!STMT_VINFO_RELEVANT_P (stmt_info)
7052 && !STMT_VINFO_LIVE_P (stmt_info))
7054 if (STMT_VINFO_IN_PATTERN_P (stmt_info)
7055 && (pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info))
7056 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt))
7057 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt))))
7059 stmt = pattern_stmt;
7060 stmt_info = vinfo_for_stmt (stmt);
7062 else
7064 gsi_next (&si);
7065 continue;
7068 else if (STMT_VINFO_IN_PATTERN_P (stmt_info)
7069 && (pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info))
7070 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt))
7071 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt))))
7072 transform_pattern_stmt = true;
7074 /* If pattern statement has def stmts, vectorize them too. */
7075 if (is_pattern_stmt_p (stmt_info))
7077 if (pattern_def_seq == NULL)
7079 pattern_def_seq = STMT_VINFO_PATTERN_DEF_SEQ (stmt_info);
7080 pattern_def_si = gsi_start (pattern_def_seq);
7082 else if (!gsi_end_p (pattern_def_si))
7083 gsi_next (&pattern_def_si);
7084 if (pattern_def_seq != NULL)
7086 gimple *pattern_def_stmt = NULL;
7087 stmt_vec_info pattern_def_stmt_info = NULL;
7089 while (!gsi_end_p (pattern_def_si))
7091 pattern_def_stmt = gsi_stmt (pattern_def_si);
7092 pattern_def_stmt_info
7093 = vinfo_for_stmt (pattern_def_stmt);
7094 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info)
7095 || STMT_VINFO_LIVE_P (pattern_def_stmt_info))
7096 break;
7097 gsi_next (&pattern_def_si);
7100 if (!gsi_end_p (pattern_def_si))
7102 if (dump_enabled_p ())
7104 dump_printf_loc (MSG_NOTE, vect_location,
7105 "==> vectorizing pattern def "
7106 "stmt: ");
7107 dump_gimple_stmt (MSG_NOTE, TDF_SLIM,
7108 pattern_def_stmt, 0);
7111 stmt = pattern_def_stmt;
7112 stmt_info = pattern_def_stmt_info;
7114 else
7116 pattern_def_si = gsi_none ();
7117 transform_pattern_stmt = false;
7120 else
7121 transform_pattern_stmt = false;
7124 if (STMT_VINFO_VECTYPE (stmt_info))
7126 unsigned int nunits
7127 = (unsigned int)
7128 TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info));
7129 if (!STMT_SLP_TYPE (stmt_info)
7130 && nunits != (unsigned int) vf
7131 && dump_enabled_p ())
7132 /* For SLP VF is set according to unrolling factor, and not
7133 to vector size, hence for SLP this print is not valid. */
7134 dump_printf_loc (MSG_NOTE, vect_location, "multiple-types.\n");
7137 /* SLP. Schedule all the SLP instances when the first SLP stmt is
7138 reached. */
7139 if (STMT_SLP_TYPE (stmt_info))
7141 if (!slp_scheduled)
7143 slp_scheduled = true;
7145 if (dump_enabled_p ())
7146 dump_printf_loc (MSG_NOTE, vect_location,
7147 "=== scheduling SLP instances ===\n");
7149 vect_schedule_slp (loop_vinfo);
7152 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
7153 if (!vinfo_for_stmt (stmt) || PURE_SLP_STMT (stmt_info))
7155 if (!transform_pattern_stmt && gsi_end_p (pattern_def_si))
7157 pattern_def_seq = NULL;
7158 gsi_next (&si);
7160 continue;
7164 /* -------- vectorize statement ------------ */
7165 if (dump_enabled_p ())
7166 dump_printf_loc (MSG_NOTE, vect_location, "transform statement.\n");
7168 grouped_store = false;
7169 is_store = vect_transform_stmt (stmt, &si, &grouped_store, NULL, NULL);
7170 if (is_store)
7172 if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
7174 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
7175 interleaving chain was completed - free all the stores in
7176 the chain. */
7177 gsi_next (&si);
7178 vect_remove_stores (GROUP_FIRST_ELEMENT (stmt_info));
7180 else
7182 /* Free the attached stmt_vec_info and remove the stmt. */
7183 gimple *store = gsi_stmt (si);
7184 free_stmt_vec_info (store);
7185 unlink_stmt_vdef (store);
7186 gsi_remove (&si, true);
7187 release_defs (store);
7190 /* Stores can only appear at the end of pattern statements. */
7191 gcc_assert (!transform_pattern_stmt);
7192 pattern_def_seq = NULL;
7194 else if (!transform_pattern_stmt && gsi_end_p (pattern_def_si))
7196 pattern_def_seq = NULL;
7197 gsi_next (&si);
7199 } /* stmts in BB */
7200 } /* BBs in loop */
7202 slpeel_make_loop_iterate_ntimes (loop, niters_vector);
7204 scale_profile_for_vect_loop (loop, vf);
7206 /* The minimum number of iterations performed by the epilogue. This
7207 is 1 when peeling for gaps because we always need a final scalar
7208 iteration. */
7209 int min_epilogue_iters = LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo) ? 1 : 0;
7210 /* +1 to convert latch counts to loop iteration counts,
7211 -min_epilogue_iters to remove iterations that cannot be performed
7212 by the vector code. */
7213 int bias = 1 - min_epilogue_iters;
7214 /* In these calculations the "- 1" converts loop iteration counts
7215 back to latch counts. */
7216 if (loop->any_upper_bound)
7217 loop->nb_iterations_upper_bound
7218 = wi::udiv_floor (loop->nb_iterations_upper_bound + bias, vf) - 1;
7219 if (loop->any_likely_upper_bound)
7220 loop->nb_iterations_likely_upper_bound
7221 = wi::udiv_floor (loop->nb_iterations_likely_upper_bound + bias, vf) - 1;
7222 if (loop->any_estimate)
7223 loop->nb_iterations_estimate
7224 = wi::udiv_floor (loop->nb_iterations_estimate + bias, vf) - 1;
7226 if (dump_enabled_p ())
7228 if (!LOOP_VINFO_EPILOGUE_P (loop_vinfo))
7230 dump_printf_loc (MSG_NOTE, vect_location,
7231 "LOOP VECTORIZED\n");
7232 if (loop->inner)
7233 dump_printf_loc (MSG_NOTE, vect_location,
7234 "OUTER LOOP VECTORIZED\n");
7235 dump_printf (MSG_NOTE, "\n");
7237 else
7238 dump_printf_loc (MSG_NOTE, vect_location,
7239 "LOOP EPILOGUE VECTORIZED (VS=%d)\n",
7240 current_vector_size);
7243 /* Free SLP instances here because otherwise stmt reference counting
7244 won't work. */
7245 slp_instance instance;
7246 FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (loop_vinfo), i, instance)
7247 vect_free_slp_instance (instance);
7248 LOOP_VINFO_SLP_INSTANCES (loop_vinfo).release ();
7249 /* Clear-up safelen field since its value is invalid after vectorization
7250 since vectorized loop can have loop-carried dependencies. */
7251 loop->safelen = 0;
7253 /* Don't vectorize epilogue for epilogue. */
7254 if (LOOP_VINFO_EPILOGUE_P (loop_vinfo))
7255 epilogue = NULL;
7257 if (epilogue)
7259 unsigned int vector_sizes
7260 = targetm.vectorize.autovectorize_vector_sizes ();
7261 vector_sizes &= current_vector_size - 1;
7263 if (!PARAM_VALUE (PARAM_VECT_EPILOGUES_NOMASK))
7264 epilogue = NULL;
7265 else if (!vector_sizes)
7266 epilogue = NULL;
7267 else if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
7268 && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) >= 0)
7270 int smallest_vec_size = 1 << ctz_hwi (vector_sizes);
7271 int ratio = current_vector_size / smallest_vec_size;
7272 int eiters = LOOP_VINFO_INT_NITERS (loop_vinfo)
7273 - LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo);
7274 eiters = eiters % vf;
7276 epilogue->nb_iterations_upper_bound = eiters - 1;
7278 if (eiters < vf / ratio)
7279 epilogue = NULL;
7283 if (epilogue)
7285 epilogue->force_vectorize = loop->force_vectorize;
7286 epilogue->safelen = loop->safelen;
7287 epilogue->dont_vectorize = false;
7289 /* We may need to if-convert epilogue to vectorize it. */
7290 if (LOOP_VINFO_SCALAR_LOOP (loop_vinfo))
7291 tree_if_conversion (epilogue);
7294 return epilogue;
7297 /* The code below is trying to perform simple optimization - revert
7298 if-conversion for masked stores, i.e. if the mask of a store is zero
7299 do not perform it and all stored value producers also if possible.
7300 For example,
7301 for (i=0; i<n; i++)
7302 if (c[i])
7304 p1[i] += 1;
7305 p2[i] = p3[i] +2;
7307 this transformation will produce the following semi-hammock:
7309 if (!mask__ifc__42.18_165 == { 0, 0, 0, 0, 0, 0, 0, 0 })
7311 vect__11.19_170 = MASK_LOAD (vectp_p1.20_168, 0B, mask__ifc__42.18_165);
7312 vect__12.22_172 = vect__11.19_170 + vect_cst__171;
7313 MASK_STORE (vectp_p1.23_175, 0B, mask__ifc__42.18_165, vect__12.22_172);
7314 vect__18.25_182 = MASK_LOAD (vectp_p3.26_180, 0B, mask__ifc__42.18_165);
7315 vect__19.28_184 = vect__18.25_182 + vect_cst__183;
7316 MASK_STORE (vectp_p2.29_187, 0B, mask__ifc__42.18_165, vect__19.28_184);
7320 void
7321 optimize_mask_stores (struct loop *loop)
7323 basic_block *bbs = get_loop_body (loop);
7324 unsigned nbbs = loop->num_nodes;
7325 unsigned i;
7326 basic_block bb;
7327 struct loop *bb_loop;
7328 gimple_stmt_iterator gsi;
7329 gimple *stmt;
7330 auto_vec<gimple *> worklist;
7332 vect_location = find_loop_location (loop);
7333 /* Pick up all masked stores in loop if any. */
7334 for (i = 0; i < nbbs; i++)
7336 bb = bbs[i];
7337 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
7338 gsi_next (&gsi))
7340 stmt = gsi_stmt (gsi);
7341 if (gimple_call_internal_p (stmt, IFN_MASK_STORE))
7342 worklist.safe_push (stmt);
7346 free (bbs);
7347 if (worklist.is_empty ())
7348 return;
7350 /* Loop has masked stores. */
7351 while (!worklist.is_empty ())
7353 gimple *last, *last_store;
7354 edge e, efalse;
7355 tree mask;
7356 basic_block store_bb, join_bb;
7357 gimple_stmt_iterator gsi_to;
7358 tree vdef, new_vdef;
7359 gphi *phi;
7360 tree vectype;
7361 tree zero;
7363 last = worklist.pop ();
7364 mask = gimple_call_arg (last, 2);
7365 bb = gimple_bb (last);
7366 /* Create then_bb and if-then structure in CFG, then_bb belongs to
7367 the same loop as if_bb. It could be different to LOOP when two
7368 level loop-nest is vectorized and mask_store belongs to the inner
7369 one. */
7370 e = split_block (bb, last);
7371 bb_loop = bb->loop_father;
7372 gcc_assert (loop == bb_loop || flow_loop_nested_p (loop, bb_loop));
7373 join_bb = e->dest;
7374 store_bb = create_empty_bb (bb);
7375 add_bb_to_loop (store_bb, bb_loop);
7376 e->flags = EDGE_TRUE_VALUE;
7377 efalse = make_edge (bb, store_bb, EDGE_FALSE_VALUE);
7378 /* Put STORE_BB to likely part. */
7379 efalse->probability = PROB_UNLIKELY;
7380 store_bb->frequency = PROB_ALWAYS - EDGE_FREQUENCY (efalse);
7381 make_edge (store_bb, join_bb, EDGE_FALLTHRU);
7382 if (dom_info_available_p (CDI_DOMINATORS))
7383 set_immediate_dominator (CDI_DOMINATORS, store_bb, bb);
7384 if (dump_enabled_p ())
7385 dump_printf_loc (MSG_NOTE, vect_location,
7386 "Create new block %d to sink mask stores.",
7387 store_bb->index);
7388 /* Create vector comparison with boolean result. */
7389 vectype = TREE_TYPE (mask);
7390 zero = build_zero_cst (vectype);
7391 stmt = gimple_build_cond (EQ_EXPR, mask, zero, NULL_TREE, NULL_TREE);
7392 gsi = gsi_last_bb (bb);
7393 gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
7394 /* Create new PHI node for vdef of the last masked store:
7395 .MEM_2 = VDEF <.MEM_1>
7396 will be converted to
7397 .MEM.3 = VDEF <.MEM_1>
7398 and new PHI node will be created in join bb
7399 .MEM_2 = PHI <.MEM_1, .MEM_3>
7401 vdef = gimple_vdef (last);
7402 new_vdef = make_ssa_name (gimple_vop (cfun), last);
7403 gimple_set_vdef (last, new_vdef);
7404 phi = create_phi_node (vdef, join_bb);
7405 add_phi_arg (phi, new_vdef, EDGE_SUCC (store_bb, 0), UNKNOWN_LOCATION);
7407 /* Put all masked stores with the same mask to STORE_BB if possible. */
7408 while (true)
7410 gimple_stmt_iterator gsi_from;
7411 gimple *stmt1 = NULL;
7413 /* Move masked store to STORE_BB. */
7414 last_store = last;
7415 gsi = gsi_for_stmt (last);
7416 gsi_from = gsi;
7417 /* Shift GSI to the previous stmt for further traversal. */
7418 gsi_prev (&gsi);
7419 gsi_to = gsi_start_bb (store_bb);
7420 gsi_move_before (&gsi_from, &gsi_to);
7421 /* Setup GSI_TO to the non-empty block start. */
7422 gsi_to = gsi_start_bb (store_bb);
7423 if (dump_enabled_p ())
7425 dump_printf_loc (MSG_NOTE, vect_location,
7426 "Move stmt to created bb\n");
7427 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, last, 0);
7429 /* Move all stored value producers if possible. */
7430 while (!gsi_end_p (gsi))
7432 tree lhs;
7433 imm_use_iterator imm_iter;
7434 use_operand_p use_p;
7435 bool res;
7437 /* Skip debug statements. */
7438 if (is_gimple_debug (gsi_stmt (gsi)))
7440 gsi_prev (&gsi);
7441 continue;
7443 stmt1 = gsi_stmt (gsi);
7444 /* Do not consider statements writing to memory or having
7445 volatile operand. */
7446 if (gimple_vdef (stmt1)
7447 || gimple_has_volatile_ops (stmt1))
7448 break;
7449 gsi_from = gsi;
7450 gsi_prev (&gsi);
7451 lhs = gimple_get_lhs (stmt1);
7452 if (!lhs)
7453 break;
7455 /* LHS of vectorized stmt must be SSA_NAME. */
7456 if (TREE_CODE (lhs) != SSA_NAME)
7457 break;
7459 if (!VECTOR_TYPE_P (TREE_TYPE (lhs)))
7461 /* Remove dead scalar statement. */
7462 if (has_zero_uses (lhs))
7464 gsi_remove (&gsi_from, true);
7465 continue;
7469 /* Check that LHS does not have uses outside of STORE_BB. */
7470 res = true;
7471 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
7473 gimple *use_stmt;
7474 use_stmt = USE_STMT (use_p);
7475 if (is_gimple_debug (use_stmt))
7476 continue;
7477 if (gimple_bb (use_stmt) != store_bb)
7479 res = false;
7480 break;
7483 if (!res)
7484 break;
7486 if (gimple_vuse (stmt1)
7487 && gimple_vuse (stmt1) != gimple_vuse (last_store))
7488 break;
7490 /* Can move STMT1 to STORE_BB. */
7491 if (dump_enabled_p ())
7493 dump_printf_loc (MSG_NOTE, vect_location,
7494 "Move stmt to created bb\n");
7495 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt1, 0);
7497 gsi_move_before (&gsi_from, &gsi_to);
7498 /* Shift GSI_TO for further insertion. */
7499 gsi_prev (&gsi_to);
7501 /* Put other masked stores with the same mask to STORE_BB. */
7502 if (worklist.is_empty ()
7503 || gimple_call_arg (worklist.last (), 2) != mask
7504 || worklist.last () != stmt1)
7505 break;
7506 last = worklist.pop ();
7508 add_phi_arg (phi, gimple_vuse (last_store), e, UNKNOWN_LOCATION);