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
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
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/>. */
24 #include "coretypes.h"
31 #include "tree-pass.h"
33 #include "optabs-tree.h"
34 #include "diagnostic-core.h"
35 #include "fold-const.h"
36 #include "stor-layout.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"
47 #include "tree-scalar-evolution.h"
48 #include "tree-vectorizer.h"
49 #include "gimple-fold.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;
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;
73 for (i=0; i<N/8; i++){
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.
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:
117 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
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:
126 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
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.
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
167 VF is also the factor by which the loop iterations are strip-mined, e.g.:
174 for (i=0; i<N; i+=VF){
175 a[i:VF] = b[i:VF] + c[i:VF];
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
;
190 stmt_vec_info stmt_info
;
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;
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
);
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
);
238 if (dump_enabled_p ())
240 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
241 "not vectorized: unsupported "
243 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
245 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
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",
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
;)
274 if (analyze_pattern_stmt
)
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
))))
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);
311 if (dump_enabled_p ())
312 dump_printf_loc (MSG_NOTE
, vect_location
, "skip.\n");
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
))
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
;
364 pattern_def_si
= gsi_none ();
365 analyze_pattern_stmt
= false;
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
;
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
,
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);
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
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
);
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));
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
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
);
445 if (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt
))
447 && !VECT_SCALAR_BOOLEAN_TYPE_P
448 (TREE_TYPE (gimple_assign_rhs1 (stmt
))))
449 scalar_type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
452 if (!analyze_pattern_stmt
&& gsi_end_p (pattern_def_si
))
454 pattern_def_seq
= NULL
;
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
);
471 if (dump_enabled_p ())
473 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
474 "not vectorized: unsupported "
476 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
478 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
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
;
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). */
504 scalar_type
= vect_get_smallest_scalar_type (stmt
, &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
);
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
,
523 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
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
,
538 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
539 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
541 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
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
;
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");
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
);
597 if (dump_enabled_p ())
598 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
599 "not vectorized: unsupported mask\n");
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 "
620 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
,
626 /* No vectype probably means external definition.
627 Allow it in case there is another operand which
628 allows to determine mask type. */
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
,
644 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
645 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
647 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
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
,
661 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
662 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
664 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
670 /* We may compare boolean value loaded as vector of integers.
671 Fix mask_type in such case. */
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
684 if (dump_enabled_p ())
686 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
687 "not vectorized: can't compute mask type "
689 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
,
695 STMT_VINFO_VECTYPE (mask_producers
[i
]) = mask_type
;
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. */
708 vect_is_simple_iv_evolution (unsigned loop_nb
, tree access_fn
, tree
* init
,
713 tree evolution_part
= evolution_part_in_loop_num (access_fn
, loop_nb
);
716 /* When there is no evolution in this loop, the evolution function
718 if (evolution_part
== NULL_TREE
)
721 /* When the evolution is a polynomial of degree >= 2
722 the evolution function is not "simple". */
723 if (tree_is_chrec (evolution_part
))
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");
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
,
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
768 vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo
, struct loop
*loop
)
770 basic_block bb
= loop
->header
;
772 auto_vec
<gimple
*, 64> worklist
;
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
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
))
801 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_unknown_def_type
;
803 /* Analyze the evolution function. */
804 access_fn
= analyze_scalar_evolution (loop
, def
);
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
);
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
);
830 gcc_assert (STMT_VINFO_LOOP_PHI_EVOLUTION_BASE_UNCHANGED (stmt_vinfo
)
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
);
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);
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
;
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
)) =
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
)) =
892 /* Store the reduction cycles for possible vectorization in
893 loop-aware SLP if it was not detected as reduction
895 if (! GROUP_FIRST_ELEMENT (vinfo_for_stmt (reduc_stmt
)))
896 LOOP_VINFO_REDUCTIONS (loop_vinfo
).safe_push (reduc_stmt
);
901 if (dump_enabled_p ())
902 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
903 "Unknown def-use cycle pattern.\n");
908 /* Function vect_analyze_scalar_cycles.
910 Examine the cross iteration def-use cycles of scalar variables, by
911 analyzing the loop-header PHIs of scalar variables. Classify each
912 cycle as one of the following: invariant, induction, reduction, unknown.
913 We do that for the loop represented by LOOP_VINFO, and also to its
914 inner-loop, if exists.
915 Examples for scalar cycles:
930 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo
)
932 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
934 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
);
936 /* When vectorizing an outer-loop, the inner-loop is executed sequentially.
937 Reductions in such inner-loop therefore have different properties than
938 the reductions in the nest that gets vectorized:
939 1. When vectorized, they are executed in the same order as in the original
940 scalar loop, so we can't change the order of computation when
942 2. FIXME: Inner-loop reductions can be used in the inner-loop, so the
943 current checks are too strict. */
946 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
->inner
);
949 /* Transfer group and reduction information from STMT to its pattern stmt. */
952 vect_fixup_reduc_chain (gimple
*stmt
)
954 gimple
*firstp
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt
));
956 gcc_assert (!GROUP_FIRST_ELEMENT (vinfo_for_stmt (firstp
))
957 && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)));
958 GROUP_SIZE (vinfo_for_stmt (firstp
)) = GROUP_SIZE (vinfo_for_stmt (stmt
));
961 stmtp
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt
));
962 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmtp
)) = firstp
;
963 stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
));
965 GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmtp
))
966 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt
));
969 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmtp
)) = vect_reduction_def
;
972 /* Fixup scalar cycles that now have their stmts detected as patterns. */
975 vect_fixup_scalar_cycles_with_patterns (loop_vec_info loop_vinfo
)
980 FOR_EACH_VEC_ELT (LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
), i
, first
)
981 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (first
)))
983 gimple
*next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (first
));
986 if (! STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (next
)))
988 next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next
));
990 /* If not all stmt in the chain are patterns try to handle
991 the chain without patterns. */
994 vect_fixup_reduc_chain (first
);
995 LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
)[i
]
996 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first
));
1001 /* Function vect_get_loop_niters.
1003 Determine how many iterations the loop is executed and place it
1004 in NUMBER_OF_ITERATIONS. Place the number of latch iterations
1005 in NUMBER_OF_ITERATIONSM1. Place the condition under which the
1006 niter information holds in ASSUMPTIONS.
1008 Return the loop exit condition. */
1012 vect_get_loop_niters (struct loop
*loop
, tree
*assumptions
,
1013 tree
*number_of_iterations
, tree
*number_of_iterationsm1
)
1015 edge exit
= single_exit (loop
);
1016 struct tree_niter_desc niter_desc
;
1017 tree niter_assumptions
, niter
, may_be_zero
;
1018 gcond
*cond
= get_loop_exit_condition (loop
);
1020 *assumptions
= boolean_true_node
;
1021 *number_of_iterationsm1
= chrec_dont_know
;
1022 *number_of_iterations
= chrec_dont_know
;
1023 if (dump_enabled_p ())
1024 dump_printf_loc (MSG_NOTE
, vect_location
,
1025 "=== get_loop_niters ===\n");
1030 niter
= chrec_dont_know
;
1031 may_be_zero
= NULL_TREE
;
1032 niter_assumptions
= boolean_true_node
;
1033 if (!number_of_iterations_exit_assumptions (loop
, exit
, &niter_desc
, NULL
)
1034 || chrec_contains_undetermined (niter_desc
.niter
))
1037 niter_assumptions
= niter_desc
.assumptions
;
1038 may_be_zero
= niter_desc
.may_be_zero
;
1039 niter
= niter_desc
.niter
;
1041 if (may_be_zero
&& integer_zerop (may_be_zero
))
1042 may_be_zero
= NULL_TREE
;
1046 if (COMPARISON_CLASS_P (may_be_zero
))
1048 /* Try to combine may_be_zero with assumptions, this can simplify
1049 computation of niter expression. */
1050 if (niter_assumptions
&& !integer_nonzerop (niter_assumptions
))
1051 niter_assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1053 fold_build1 (TRUTH_NOT_EXPR
,
1057 niter
= fold_build3 (COND_EXPR
, TREE_TYPE (niter
), may_be_zero
,
1058 build_int_cst (TREE_TYPE (niter
), 0), niter
);
1060 may_be_zero
= NULL_TREE
;
1062 else if (integer_nonzerop (may_be_zero
))
1064 *number_of_iterationsm1
= build_int_cst (TREE_TYPE (niter
), 0);
1065 *number_of_iterations
= build_int_cst (TREE_TYPE (niter
), 1);
1072 *assumptions
= niter_assumptions
;
1073 *number_of_iterationsm1
= niter
;
1075 /* We want the number of loop header executions which is the number
1076 of latch executions plus one.
1077 ??? For UINT_MAX latch executions this number overflows to zero
1078 for loops like do { n++; } while (n != 0); */
1079 if (niter
&& !chrec_contains_undetermined (niter
))
1080 niter
= fold_build2 (PLUS_EXPR
, TREE_TYPE (niter
), unshare_expr (niter
),
1081 build_int_cst (TREE_TYPE (niter
), 1));
1082 *number_of_iterations
= niter
;
1087 /* Function bb_in_loop_p
1089 Used as predicate for dfs order traversal of the loop bbs. */
1092 bb_in_loop_p (const_basic_block bb
, const void *data
)
1094 const struct loop
*const loop
= (const struct loop
*)data
;
1095 if (flow_bb_inside_loop_p (loop
, bb
))
1101 /* Create and initialize a new loop_vec_info struct for LOOP_IN, as well as
1102 stmt_vec_info structs for all the stmts in LOOP_IN. */
1104 _loop_vec_info::_loop_vec_info (struct loop
*loop_in
)
1105 : vec_info (vec_info::loop
, init_cost (loop_in
)),
1107 bbs (XCNEWVEC (basic_block
, loop
->num_nodes
)),
1108 num_itersm1 (NULL_TREE
),
1109 num_iters (NULL_TREE
),
1110 num_iters_unchanged (NULL_TREE
),
1111 num_iters_assumptions (NULL_TREE
),
1113 vectorization_factor (0),
1114 unaligned_dr (NULL
),
1115 peeling_for_alignment (0),
1117 slp_unrolling_factor (1),
1118 single_scalar_iteration_cost (0),
1119 vectorizable (false),
1120 peeling_for_gaps (false),
1121 peeling_for_niter (false),
1122 operands_swapped (false),
1123 no_data_dependencies (false),
1124 has_mask_store (false),
1126 orig_loop_info (NULL
)
1128 /* Create/Update stmt_info for all stmts in the loop. */
1129 basic_block
*body
= get_loop_body (loop
);
1130 for (unsigned int i
= 0; i
< loop
->num_nodes
; i
++)
1132 basic_block bb
= body
[i
];
1133 gimple_stmt_iterator si
;
1135 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
1137 gimple
*phi
= gsi_stmt (si
);
1138 gimple_set_uid (phi
, 0);
1139 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, this));
1142 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1144 gimple
*stmt
= gsi_stmt (si
);
1145 gimple_set_uid (stmt
, 0);
1146 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, this));
1151 /* CHECKME: We want to visit all BBs before their successors (except for
1152 latch blocks, for which this assertion wouldn't hold). In the simple
1153 case of the loop forms we allow, a dfs order of the BBs would the same
1154 as reversed postorder traversal, so we are safe. */
1156 unsigned int nbbs
= dfs_enumerate_from (loop
->header
, 0, bb_in_loop_p
,
1157 bbs
, loop
->num_nodes
, loop
);
1158 gcc_assert (nbbs
== loop
->num_nodes
);
1162 /* Free all memory used by the _loop_vec_info, as well as all the
1163 stmt_vec_info structs of all the stmts in the loop. */
1165 _loop_vec_info::~_loop_vec_info ()
1168 gimple_stmt_iterator si
;
1171 nbbs
= loop
->num_nodes
;
1172 for (j
= 0; j
< nbbs
; j
++)
1174 basic_block bb
= bbs
[j
];
1175 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
1176 free_stmt_vec_info (gsi_stmt (si
));
1178 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); )
1180 gimple
*stmt
= gsi_stmt (si
);
1182 /* We may have broken canonical form by moving a constant
1183 into RHS1 of a commutative op. Fix such occurrences. */
1184 if (operands_swapped
&& is_gimple_assign (stmt
))
1186 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1188 if ((code
== PLUS_EXPR
1189 || code
== POINTER_PLUS_EXPR
1190 || code
== MULT_EXPR
)
1191 && CONSTANT_CLASS_P (gimple_assign_rhs1 (stmt
)))
1192 swap_ssa_operands (stmt
,
1193 gimple_assign_rhs1_ptr (stmt
),
1194 gimple_assign_rhs2_ptr (stmt
));
1195 else if (code
== COND_EXPR
1196 && CONSTANT_CLASS_P (gimple_assign_rhs2 (stmt
)))
1198 tree cond_expr
= gimple_assign_rhs1 (stmt
);
1199 enum tree_code cond_code
= TREE_CODE (cond_expr
);
1201 if (TREE_CODE_CLASS (cond_code
) == tcc_comparison
)
1203 bool honor_nans
= HONOR_NANS (TREE_OPERAND (cond_expr
,
1205 cond_code
= invert_tree_comparison (cond_code
,
1207 if (cond_code
!= ERROR_MARK
)
1209 TREE_SET_CODE (cond_expr
, cond_code
);
1210 swap_ssa_operands (stmt
,
1211 gimple_assign_rhs2_ptr (stmt
),
1212 gimple_assign_rhs3_ptr (stmt
));
1218 /* Free stmt_vec_info. */
1219 free_stmt_vec_info (stmt
);
1230 /* Calculate the cost of one scalar iteration of the loop. */
1232 vect_compute_single_scalar_iteration_cost (loop_vec_info loop_vinfo
)
1234 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1235 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1236 int nbbs
= loop
->num_nodes
, factor
, scalar_single_iter_cost
= 0;
1237 int innerloop_iters
, i
;
1239 /* Count statements in scalar loop. Using this as scalar cost for a single
1242 TODO: Add outer loop support.
1244 TODO: Consider assigning different costs to different scalar
1248 innerloop_iters
= 1;
1250 innerloop_iters
= 50; /* FIXME */
1252 for (i
= 0; i
< nbbs
; i
++)
1254 gimple_stmt_iterator si
;
1255 basic_block bb
= bbs
[i
];
1257 if (bb
->loop_father
== loop
->inner
)
1258 factor
= innerloop_iters
;
1262 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1264 gimple
*stmt
= gsi_stmt (si
);
1265 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1267 if (!is_gimple_assign (stmt
) && !is_gimple_call (stmt
))
1270 /* Skip stmts that are not vectorized inside the loop. */
1272 && !STMT_VINFO_RELEVANT_P (stmt_info
)
1273 && (!STMT_VINFO_LIVE_P (stmt_info
)
1274 || !VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
1275 && !STMT_VINFO_IN_PATTERN_P (stmt_info
))
1278 vect_cost_for_stmt kind
;
1279 if (STMT_VINFO_DATA_REF (stmt_info
))
1281 if (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info
)))
1284 kind
= scalar_store
;
1289 scalar_single_iter_cost
1290 += record_stmt_cost (&LOOP_VINFO_SCALAR_ITERATION_COST (loop_vinfo
),
1291 factor
, kind
, stmt_info
, 0, vect_prologue
);
1294 LOOP_VINFO_SINGLE_SCALAR_ITERATION_COST (loop_vinfo
)
1295 = scalar_single_iter_cost
;
1299 /* Function vect_analyze_loop_form_1.
1301 Verify that certain CFG restrictions hold, including:
1302 - the loop has a pre-header
1303 - the loop has a single entry and exit
1304 - the loop exit condition is simple enough
1305 - the number of iterations can be analyzed, i.e, a countable loop. The
1306 niter could be analyzed under some assumptions. */
1309 vect_analyze_loop_form_1 (struct loop
*loop
, gcond
**loop_cond
,
1310 tree
*assumptions
, tree
*number_of_iterationsm1
,
1311 tree
*number_of_iterations
, gcond
**inner_loop_cond
)
1313 if (dump_enabled_p ())
1314 dump_printf_loc (MSG_NOTE
, vect_location
,
1315 "=== vect_analyze_loop_form ===\n");
1317 /* Different restrictions apply when we are considering an inner-most loop,
1318 vs. an outer (nested) loop.
1319 (FORNOW. May want to relax some of these restrictions in the future). */
1323 /* Inner-most loop. We currently require that the number of BBs is
1324 exactly 2 (the header and latch). Vectorizable inner-most loops
1335 if (loop
->num_nodes
!= 2)
1337 if (dump_enabled_p ())
1338 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1339 "not vectorized: control flow in loop.\n");
1343 if (empty_block_p (loop
->header
))
1345 if (dump_enabled_p ())
1346 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1347 "not vectorized: empty loop.\n");
1353 struct loop
*innerloop
= loop
->inner
;
1356 /* Nested loop. We currently require that the loop is doubly-nested,
1357 contains a single inner loop, and the number of BBs is exactly 5.
1358 Vectorizable outer-loops look like this:
1370 The inner-loop has the properties expected of inner-most loops
1371 as described above. */
1373 if ((loop
->inner
)->inner
|| (loop
->inner
)->next
)
1375 if (dump_enabled_p ())
1376 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1377 "not vectorized: multiple nested loops.\n");
1381 if (loop
->num_nodes
!= 5)
1383 if (dump_enabled_p ())
1384 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1385 "not vectorized: control flow in loop.\n");
1389 entryedge
= loop_preheader_edge (innerloop
);
1390 if (entryedge
->src
!= loop
->header
1391 || !single_exit (innerloop
)
1392 || single_exit (innerloop
)->dest
!= EDGE_PRED (loop
->latch
, 0)->src
)
1394 if (dump_enabled_p ())
1395 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1396 "not vectorized: unsupported outerloop form.\n");
1400 /* Analyze the inner-loop. */
1401 tree inner_niterm1
, inner_niter
, inner_assumptions
;
1402 if (! vect_analyze_loop_form_1 (loop
->inner
, inner_loop_cond
,
1403 &inner_assumptions
, &inner_niterm1
,
1405 /* Don't support analyzing niter under assumptions for inner
1407 || !integer_onep (inner_assumptions
))
1409 if (dump_enabled_p ())
1410 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1411 "not vectorized: Bad inner loop.\n");
1415 if (!expr_invariant_in_loop_p (loop
, inner_niter
))
1417 if (dump_enabled_p ())
1418 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1419 "not vectorized: inner-loop count not"
1424 if (dump_enabled_p ())
1425 dump_printf_loc (MSG_NOTE
, vect_location
,
1426 "Considering outer-loop vectorization.\n");
1429 if (!single_exit (loop
)
1430 || EDGE_COUNT (loop
->header
->preds
) != 2)
1432 if (dump_enabled_p ())
1434 if (!single_exit (loop
))
1435 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1436 "not vectorized: multiple exits.\n");
1437 else if (EDGE_COUNT (loop
->header
->preds
) != 2)
1438 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1439 "not vectorized: too many incoming edges.\n");
1444 /* We assume that the loop exit condition is at the end of the loop. i.e,
1445 that the loop is represented as a do-while (with a proper if-guard
1446 before the loop if needed), where the loop header contains all the
1447 executable statements, and the latch is empty. */
1448 if (!empty_block_p (loop
->latch
)
1449 || !gimple_seq_empty_p (phi_nodes (loop
->latch
)))
1451 if (dump_enabled_p ())
1452 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1453 "not vectorized: latch block not empty.\n");
1457 /* Make sure the exit is not abnormal. */
1458 edge e
= single_exit (loop
);
1459 if (e
->flags
& EDGE_ABNORMAL
)
1461 if (dump_enabled_p ())
1462 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1463 "not vectorized: abnormal loop exit edge.\n");
1467 *loop_cond
= vect_get_loop_niters (loop
, assumptions
, number_of_iterations
,
1468 number_of_iterationsm1
);
1471 if (dump_enabled_p ())
1472 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1473 "not vectorized: complicated exit condition.\n");
1477 if (integer_zerop (*assumptions
)
1478 || !*number_of_iterations
1479 || chrec_contains_undetermined (*number_of_iterations
))
1481 if (dump_enabled_p ())
1482 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1483 "not vectorized: number of iterations cannot be "
1488 if (integer_zerop (*number_of_iterations
))
1490 if (dump_enabled_p ())
1491 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1492 "not vectorized: number of iterations = 0.\n");
1499 /* Analyze LOOP form and return a loop_vec_info if it is of suitable form. */
1502 vect_analyze_loop_form (struct loop
*loop
)
1504 tree assumptions
, number_of_iterations
, number_of_iterationsm1
;
1505 gcond
*loop_cond
, *inner_loop_cond
= NULL
;
1507 if (! vect_analyze_loop_form_1 (loop
, &loop_cond
,
1508 &assumptions
, &number_of_iterationsm1
,
1509 &number_of_iterations
, &inner_loop_cond
))
1512 loop_vec_info loop_vinfo
= new _loop_vec_info (loop
);
1513 LOOP_VINFO_NITERSM1 (loop_vinfo
) = number_of_iterationsm1
;
1514 LOOP_VINFO_NITERS (loop_vinfo
) = number_of_iterations
;
1515 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo
) = number_of_iterations
;
1516 if (!integer_onep (assumptions
))
1518 /* We consider to vectorize this loop by versioning it under
1519 some assumptions. In order to do this, we need to clear
1520 existing information computed by scev and niter analyzer. */
1522 free_numbers_of_iterations_estimates (loop
);
1523 /* Also set flag for this loop so that following scev and niter
1524 analysis are done under the assumptions. */
1525 loop_constraint_set (loop
, LOOP_C_FINITE
);
1526 /* Also record the assumptions for versioning. */
1527 LOOP_VINFO_NITERS_ASSUMPTIONS (loop_vinfo
) = assumptions
;
1530 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
1532 if (dump_enabled_p ())
1534 dump_printf_loc (MSG_NOTE
, vect_location
,
1535 "Symbolic number of iterations is ");
1536 dump_generic_expr (MSG_NOTE
, TDF_DETAILS
, number_of_iterations
);
1537 dump_printf (MSG_NOTE
, "\n");
1541 STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond
)) = loop_exit_ctrl_vec_info_type
;
1542 if (inner_loop_cond
)
1543 STMT_VINFO_TYPE (vinfo_for_stmt (inner_loop_cond
))
1544 = loop_exit_ctrl_vec_info_type
;
1546 gcc_assert (!loop
->aux
);
1547 loop
->aux
= loop_vinfo
;
1553 /* Scan the loop stmts and dependent on whether there are any (non-)SLP
1554 statements update the vectorization factor. */
1557 vect_update_vf_for_slp (loop_vec_info loop_vinfo
)
1559 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1560 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1561 int nbbs
= loop
->num_nodes
;
1562 unsigned int vectorization_factor
;
1565 if (dump_enabled_p ())
1566 dump_printf_loc (MSG_NOTE
, vect_location
,
1567 "=== vect_update_vf_for_slp ===\n");
1569 vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1570 gcc_assert (vectorization_factor
!= 0);
1572 /* If all the stmts in the loop can be SLPed, we perform only SLP, and
1573 vectorization factor of the loop is the unrolling factor required by
1574 the SLP instances. If that unrolling factor is 1, we say, that we
1575 perform pure SLP on loop - cross iteration parallelism is not
1577 bool only_slp_in_loop
= true;
1578 for (i
= 0; i
< nbbs
; i
++)
1580 basic_block bb
= bbs
[i
];
1581 for (gimple_stmt_iterator si
= gsi_start_bb (bb
); !gsi_end_p (si
);
1584 gimple
*stmt
= gsi_stmt (si
);
1585 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1586 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
1587 && STMT_VINFO_RELATED_STMT (stmt_info
))
1589 stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
1590 stmt_info
= vinfo_for_stmt (stmt
);
1592 if ((STMT_VINFO_RELEVANT_P (stmt_info
)
1593 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
1594 && !PURE_SLP_STMT (stmt_info
))
1595 /* STMT needs both SLP and loop-based vectorization. */
1596 only_slp_in_loop
= false;
1600 if (only_slp_in_loop
)
1602 dump_printf_loc (MSG_NOTE
, vect_location
,
1603 "Loop contains only SLP stmts\n");
1604 vectorization_factor
= LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
);
1608 dump_printf_loc (MSG_NOTE
, vect_location
,
1609 "Loop contains SLP and non-SLP stmts\n");
1610 vectorization_factor
1611 = least_common_multiple (vectorization_factor
,
1612 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
));
1615 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
1616 if (dump_enabled_p ())
1617 dump_printf_loc (MSG_NOTE
, vect_location
,
1618 "Updating vectorization factor to %d\n",
1619 vectorization_factor
);
1622 /* Function vect_analyze_loop_operations.
1624 Scan the loop stmts and make sure they are all vectorizable. */
1627 vect_analyze_loop_operations (loop_vec_info loop_vinfo
)
1629 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1630 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1631 int nbbs
= loop
->num_nodes
;
1633 stmt_vec_info stmt_info
;
1634 bool need_to_vectorize
= false;
1637 if (dump_enabled_p ())
1638 dump_printf_loc (MSG_NOTE
, vect_location
,
1639 "=== vect_analyze_loop_operations ===\n");
1641 for (i
= 0; i
< nbbs
; i
++)
1643 basic_block bb
= bbs
[i
];
1645 for (gphi_iterator si
= gsi_start_phis (bb
); !gsi_end_p (si
);
1648 gphi
*phi
= si
.phi ();
1651 stmt_info
= vinfo_for_stmt (phi
);
1652 if (dump_enabled_p ())
1654 dump_printf_loc (MSG_NOTE
, vect_location
, "examining phi: ");
1655 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
1657 if (virtual_operand_p (gimple_phi_result (phi
)))
1660 /* Inner-loop loop-closed exit phi in outer-loop vectorization
1661 (i.e., a phi in the tail of the outer-loop). */
1662 if (! is_loop_header_bb_p (bb
))
1664 /* FORNOW: we currently don't support the case that these phis
1665 are not used in the outerloop (unless it is double reduction,
1666 i.e., this phi is vect_reduction_def), cause this case
1667 requires to actually do something here. */
1668 if (STMT_VINFO_LIVE_P (stmt_info
)
1669 && STMT_VINFO_DEF_TYPE (stmt_info
)
1670 != vect_double_reduction_def
)
1672 if (dump_enabled_p ())
1673 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1674 "Unsupported loop-closed phi in "
1679 /* If PHI is used in the outer loop, we check that its operand
1680 is defined in the inner loop. */
1681 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1684 gimple
*op_def_stmt
;
1686 if (gimple_phi_num_args (phi
) != 1)
1689 phi_op
= PHI_ARG_DEF (phi
, 0);
1690 if (TREE_CODE (phi_op
) != SSA_NAME
)
1693 op_def_stmt
= SSA_NAME_DEF_STMT (phi_op
);
1694 if (gimple_nop_p (op_def_stmt
)
1695 || !flow_bb_inside_loop_p (loop
, gimple_bb (op_def_stmt
))
1696 || !vinfo_for_stmt (op_def_stmt
))
1699 if (STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1700 != vect_used_in_outer
1701 && STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1702 != vect_used_in_outer_by_reduction
)
1709 gcc_assert (stmt_info
);
1711 if ((STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
1712 || STMT_VINFO_LIVE_P (stmt_info
))
1713 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_induction_def
)
1715 /* A scalar-dependence cycle that we don't support. */
1716 if (dump_enabled_p ())
1717 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1718 "not vectorized: scalar dependence cycle.\n");
1722 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1724 need_to_vectorize
= true;
1725 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
1726 && ! PURE_SLP_STMT (stmt_info
))
1727 ok
= vectorizable_induction (phi
, NULL
, NULL
, NULL
);
1728 else if ((STMT_VINFO_DEF_TYPE (stmt_info
) == vect_reduction_def
1729 || STMT_VINFO_DEF_TYPE (stmt_info
) == vect_nested_cycle
)
1730 && ! PURE_SLP_STMT (stmt_info
))
1731 ok
= vectorizable_reduction (phi
, NULL
, NULL
, NULL
, NULL
);
1734 if (ok
&& STMT_VINFO_LIVE_P (stmt_info
))
1735 ok
= vectorizable_live_operation (phi
, NULL
, NULL
, -1, NULL
);
1739 if (dump_enabled_p ())
1741 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1742 "not vectorized: relevant phi not "
1744 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, phi
, 0);
1750 for (gimple_stmt_iterator si
= gsi_start_bb (bb
); !gsi_end_p (si
);
1753 gimple
*stmt
= gsi_stmt (si
);
1754 if (!gimple_clobber_p (stmt
)
1755 && !vect_analyze_stmt (stmt
, &need_to_vectorize
, NULL
, NULL
))
1760 /* All operations in the loop are either irrelevant (deal with loop
1761 control, or dead), or only used outside the loop and can be moved
1762 out of the loop (e.g. invariants, inductions). The loop can be
1763 optimized away by scalar optimizations. We're better off not
1764 touching this loop. */
1765 if (!need_to_vectorize
)
1767 if (dump_enabled_p ())
1768 dump_printf_loc (MSG_NOTE
, vect_location
,
1769 "All the computation can be taken out of the loop.\n");
1770 if (dump_enabled_p ())
1771 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1772 "not vectorized: redundant loop. no profit to "
1781 /* Function vect_analyze_loop_2.
1783 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1784 for it. The different analyses will record information in the
1785 loop_vec_info struct. */
1787 vect_analyze_loop_2 (loop_vec_info loop_vinfo
, bool &fatal
)
1790 int max_vf
= MAX_VECTORIZATION_FACTOR
;
1792 unsigned int n_stmts
= 0;
1794 /* The first group of checks is independent of the vector size. */
1797 /* Find all data references in the loop (which correspond to vdefs/vuses)
1798 and analyze their evolution in the loop. */
1800 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1802 loop_p loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1803 if (!find_loop_nest (loop
, &LOOP_VINFO_LOOP_NEST (loop_vinfo
)))
1805 if (dump_enabled_p ())
1806 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1807 "not vectorized: loop nest containing two "
1808 "or more consecutive inner loops cannot be "
1813 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
1814 for (gimple_stmt_iterator gsi
= gsi_start_bb (bbs
[i
]);
1815 !gsi_end_p (gsi
); gsi_next (&gsi
))
1817 gimple
*stmt
= gsi_stmt (gsi
);
1818 if (is_gimple_debug (stmt
))
1821 if (!find_data_references_in_stmt (loop
, stmt
,
1822 &LOOP_VINFO_DATAREFS (loop_vinfo
)))
1824 if (is_gimple_call (stmt
) && loop
->safelen
)
1826 tree fndecl
= gimple_call_fndecl (stmt
), op
;
1827 if (fndecl
!= NULL_TREE
)
1829 cgraph_node
*node
= cgraph_node::get (fndecl
);
1830 if (node
!= NULL
&& node
->simd_clones
!= NULL
)
1832 unsigned int j
, n
= gimple_call_num_args (stmt
);
1833 for (j
= 0; j
< n
; j
++)
1835 op
= gimple_call_arg (stmt
, j
);
1837 || (REFERENCE_CLASS_P (op
)
1838 && get_base_address (op
)))
1841 op
= gimple_call_lhs (stmt
);
1842 /* Ignore #pragma omp declare simd functions
1843 if they don't have data references in the
1844 call stmt itself. */
1848 || (REFERENCE_CLASS_P (op
)
1849 && get_base_address (op
)))))
1854 if (dump_enabled_p ())
1855 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1856 "not vectorized: loop contains function "
1857 "calls or data references that cannot "
1863 /* Analyze the data references and also adjust the minimal
1864 vectorization factor according to the loads and stores. */
1866 ok
= vect_analyze_data_refs (loop_vinfo
, &min_vf
);
1869 if (dump_enabled_p ())
1870 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1871 "bad data references.\n");
1875 /* Classify all cross-iteration scalar data-flow cycles.
1876 Cross-iteration cycles caused by virtual phis are analyzed separately. */
1877 vect_analyze_scalar_cycles (loop_vinfo
);
1879 vect_pattern_recog (loop_vinfo
);
1881 vect_fixup_scalar_cycles_with_patterns (loop_vinfo
);
1883 /* Analyze the access patterns of the data-refs in the loop (consecutive,
1884 complex, etc.). FORNOW: Only handle consecutive access pattern. */
1886 ok
= vect_analyze_data_ref_accesses (loop_vinfo
);
1889 if (dump_enabled_p ())
1890 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1891 "bad data access.\n");
1895 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
1897 ok
= vect_mark_stmts_to_be_vectorized (loop_vinfo
);
1900 if (dump_enabled_p ())
1901 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1902 "unexpected pattern.\n");
1906 /* While the rest of the analysis below depends on it in some way. */
1909 /* Analyze data dependences between the data-refs in the loop
1910 and adjust the maximum vectorization factor according to
1912 FORNOW: fail at the first data dependence that we encounter. */
1914 ok
= vect_analyze_data_ref_dependences (loop_vinfo
, &max_vf
);
1918 if (dump_enabled_p ())
1919 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1920 "bad data dependence.\n");
1924 ok
= vect_determine_vectorization_factor (loop_vinfo
);
1927 if (dump_enabled_p ())
1928 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1929 "can't determine vectorization factor.\n");
1932 if (max_vf
< LOOP_VINFO_VECT_FACTOR (loop_vinfo
))
1934 if (dump_enabled_p ())
1935 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1936 "bad data dependence.\n");
1940 /* Compute the scalar iteration cost. */
1941 vect_compute_single_scalar_iteration_cost (loop_vinfo
);
1943 int saved_vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1944 HOST_WIDE_INT estimated_niter
;
1946 int min_scalar_loop_bound
;
1948 /* Check the SLP opportunities in the loop, analyze and build SLP trees. */
1949 ok
= vect_analyze_slp (loop_vinfo
, n_stmts
);
1953 /* If there are any SLP instances mark them as pure_slp. */
1954 bool slp
= vect_make_slp_decision (loop_vinfo
);
1957 /* Find stmts that need to be both vectorized and SLPed. */
1958 vect_detect_hybrid_slp (loop_vinfo
);
1960 /* Update the vectorization factor based on the SLP decision. */
1961 vect_update_vf_for_slp (loop_vinfo
);
1964 /* This is the point where we can re-start analysis with SLP forced off. */
1967 /* Now the vectorization factor is final. */
1968 unsigned vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1969 gcc_assert (vectorization_factor
!= 0);
1971 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
) && dump_enabled_p ())
1972 dump_printf_loc (MSG_NOTE
, vect_location
,
1973 "vectorization_factor = %d, niters = "
1974 HOST_WIDE_INT_PRINT_DEC
"\n", vectorization_factor
,
1975 LOOP_VINFO_INT_NITERS (loop_vinfo
));
1977 HOST_WIDE_INT max_niter
1978 = likely_max_stmt_executions_int (LOOP_VINFO_LOOP (loop_vinfo
));
1979 if ((LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1980 && (LOOP_VINFO_INT_NITERS (loop_vinfo
) < vectorization_factor
))
1982 && (unsigned HOST_WIDE_INT
) max_niter
< vectorization_factor
))
1984 if (dump_enabled_p ())
1985 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1986 "not vectorized: iteration count smaller than "
1987 "vectorization factor.\n");
1991 /* Analyze the alignment of the data-refs in the loop.
1992 Fail if a data reference is found that cannot be vectorized. */
1994 ok
= vect_analyze_data_refs_alignment (loop_vinfo
);
1997 if (dump_enabled_p ())
1998 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1999 "bad data alignment.\n");
2003 /* Prune the list of ddrs to be tested at run-time by versioning for alias.
2004 It is important to call pruning after vect_analyze_data_ref_accesses,
2005 since we use grouping information gathered by interleaving analysis. */
2006 ok
= vect_prune_runtime_alias_test_list (loop_vinfo
);
2010 /* Do not invoke vect_enhance_data_refs_alignment for eplilogue
2012 if (!LOOP_VINFO_EPILOGUE_P (loop_vinfo
))
2014 /* This pass will decide on using loop versioning and/or loop peeling in
2015 order to enhance the alignment of data references in the loop. */
2016 ok
= vect_enhance_data_refs_alignment (loop_vinfo
);
2019 if (dump_enabled_p ())
2020 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2021 "bad data alignment.\n");
2028 /* Analyze operations in the SLP instances. Note this may
2029 remove unsupported SLP instances which makes the above
2030 SLP kind detection invalid. */
2031 unsigned old_size
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).length ();
2032 vect_slp_analyze_operations (LOOP_VINFO_SLP_INSTANCES (loop_vinfo
),
2033 LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
));
2034 if (LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).length () != old_size
)
2038 /* Scan all the remaining operations in the loop that are not subject
2039 to SLP and make sure they are vectorizable. */
2040 ok
= vect_analyze_loop_operations (loop_vinfo
);
2043 if (dump_enabled_p ())
2044 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2045 "bad operation or unsupported loop bound.\n");
2049 /* If epilog loop is required because of data accesses with gaps,
2050 one additional iteration needs to be peeled. Check if there is
2051 enough iterations for vectorization. */
2052 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
2053 && LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
2055 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2056 tree scalar_niters
= LOOP_VINFO_NITERSM1 (loop_vinfo
);
2058 if (wi::to_widest (scalar_niters
) < vf
)
2060 if (dump_enabled_p ())
2061 dump_printf_loc (MSG_NOTE
, vect_location
,
2062 "loop has no enough iterations to support"
2063 " peeling for gaps.\n");
2068 /* Analyze cost. Decide if worth while to vectorize. */
2069 int min_profitable_estimate
, min_profitable_iters
;
2070 vect_estimate_min_profitable_iters (loop_vinfo
, &min_profitable_iters
,
2071 &min_profitable_estimate
);
2073 if (min_profitable_iters
< 0)
2075 if (dump_enabled_p ())
2076 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2077 "not vectorized: vectorization not profitable.\n");
2078 if (dump_enabled_p ())
2079 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2080 "not vectorized: vector version will never be "
2085 min_scalar_loop_bound
= (PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND
)
2086 * vectorization_factor
);
2088 /* Use the cost model only if it is more conservative than user specified
2090 th
= (unsigned) MAX (min_scalar_loop_bound
, min_profitable_iters
);
2092 LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo
) = th
;
2094 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
2095 && LOOP_VINFO_INT_NITERS (loop_vinfo
) < th
)
2097 if (dump_enabled_p ())
2098 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2099 "not vectorized: vectorization not profitable.\n");
2100 if (dump_enabled_p ())
2101 dump_printf_loc (MSG_NOTE
, vect_location
,
2102 "not vectorized: iteration count smaller than user "
2103 "specified loop bound parameter or minimum profitable "
2104 "iterations (whichever is more conservative).\n");
2109 = estimated_stmt_executions_int (LOOP_VINFO_LOOP (loop_vinfo
));
2110 if (estimated_niter
== -1)
2111 estimated_niter
= max_niter
;
2112 if (estimated_niter
!= -1
2113 && ((unsigned HOST_WIDE_INT
) estimated_niter
2114 < MAX (th
, (unsigned) min_profitable_estimate
)))
2116 if (dump_enabled_p ())
2117 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2118 "not vectorized: estimated iteration count too "
2120 if (dump_enabled_p ())
2121 dump_printf_loc (MSG_NOTE
, vect_location
,
2122 "not vectorized: estimated iteration count smaller "
2123 "than specified loop bound parameter or minimum "
2124 "profitable iterations (whichever is more "
2125 "conservative).\n");
2129 /* Decide whether we need to create an epilogue loop to handle
2130 remaining scalar iterations. */
2131 th
= ((LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo
)
2132 / LOOP_VINFO_VECT_FACTOR (loop_vinfo
))
2133 * LOOP_VINFO_VECT_FACTOR (loop_vinfo
));
2135 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
2136 && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
) > 0)
2138 if (ctz_hwi (LOOP_VINFO_INT_NITERS (loop_vinfo
)
2139 - LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
))
2140 < exact_log2 (LOOP_VINFO_VECT_FACTOR (loop_vinfo
)))
2141 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
) = true;
2143 else if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
)
2144 || (tree_ctz (LOOP_VINFO_NITERS (loop_vinfo
))
2145 < (unsigned)exact_log2 (LOOP_VINFO_VECT_FACTOR (loop_vinfo
))
2146 /* In case of versioning, check if the maximum number of
2147 iterations is greater than th. If they are identical,
2148 the epilogue is unnecessary. */
2149 && (!LOOP_REQUIRES_VERSIONING (loop_vinfo
)
2150 || (unsigned HOST_WIDE_INT
) max_niter
> th
)))
2151 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
) = true;
2153 /* If an epilogue loop is required make sure we can create one. */
2154 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
2155 || LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
))
2157 if (dump_enabled_p ())
2158 dump_printf_loc (MSG_NOTE
, vect_location
, "epilog loop required\n");
2159 if (!vect_can_advance_ivs_p (loop_vinfo
)
2160 || !slpeel_can_duplicate_loop_p (LOOP_VINFO_LOOP (loop_vinfo
),
2161 single_exit (LOOP_VINFO_LOOP
2164 if (dump_enabled_p ())
2165 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2166 "not vectorized: can't create required "
2172 /* During peeling, we need to check if number of loop iterations is
2173 enough for both peeled prolog loop and vector loop. This check
2174 can be merged along with threshold check of loop versioning, so
2175 increase threshold for this case if necessary. */
2176 if (LOOP_REQUIRES_VERSIONING (loop_vinfo
)
2177 && (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
2178 || LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
)))
2182 /* Niters for peeled prolog loop. */
2183 if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
) < 0)
2185 struct data_reference
*dr
= LOOP_VINFO_UNALIGNED_DR (loop_vinfo
);
2186 tree vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr
)));
2188 niters_th
= TYPE_VECTOR_SUBPARTS (vectype
) - 1;
2191 niters_th
= LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
);
2193 /* Niters for at least one iteration of vectorized loop. */
2194 niters_th
+= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2195 /* One additional iteration because of peeling for gap. */
2196 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
))
2198 if (LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo
) < niters_th
)
2199 LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo
) = niters_th
;
2202 gcc_assert (vectorization_factor
2203 == (unsigned)LOOP_VINFO_VECT_FACTOR (loop_vinfo
));
2205 /* Ok to vectorize! */
2209 /* Try again with SLP forced off but if we didn't do any SLP there is
2210 no point in re-trying. */
2214 /* If there are reduction chains re-trying will fail anyway. */
2215 if (! LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
).is_empty ())
2218 /* Likewise if the grouped loads or stores in the SLP cannot be handled
2219 via interleaving or lane instructions. */
2220 slp_instance instance
;
2223 FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (loop_vinfo
), i
, instance
)
2225 stmt_vec_info vinfo
;
2226 vinfo
= vinfo_for_stmt
2227 (SLP_TREE_SCALAR_STMTS (SLP_INSTANCE_TREE (instance
))[0]);
2228 if (! STMT_VINFO_GROUPED_ACCESS (vinfo
))
2230 vinfo
= vinfo_for_stmt (STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo
));
2231 unsigned int size
= STMT_VINFO_GROUP_SIZE (vinfo
);
2232 tree vectype
= STMT_VINFO_VECTYPE (vinfo
);
2233 if (! vect_store_lanes_supported (vectype
, size
)
2234 && ! vect_grouped_store_supported (vectype
, size
))
2236 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (instance
), j
, node
)
2238 vinfo
= vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (node
)[0]);
2239 vinfo
= vinfo_for_stmt (STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo
));
2240 bool single_element_p
= !STMT_VINFO_GROUP_NEXT_ELEMENT (vinfo
);
2241 size
= STMT_VINFO_GROUP_SIZE (vinfo
);
2242 vectype
= STMT_VINFO_VECTYPE (vinfo
);
2243 if (! vect_load_lanes_supported (vectype
, size
)
2244 && ! vect_grouped_load_supported (vectype
, single_element_p
,
2250 if (dump_enabled_p ())
2251 dump_printf_loc (MSG_NOTE
, vect_location
,
2252 "re-trying with SLP disabled\n");
2254 /* Roll back state appropriately. No SLP this time. */
2256 /* Restore vectorization factor as it were without SLP. */
2257 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = saved_vectorization_factor
;
2258 /* Free the SLP instances. */
2259 FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (loop_vinfo
), j
, instance
)
2260 vect_free_slp_instance (instance
);
2261 LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).release ();
2262 /* Reset SLP type to loop_vect on all stmts. */
2263 for (i
= 0; i
< LOOP_VINFO_LOOP (loop_vinfo
)->num_nodes
; ++i
)
2265 basic_block bb
= LOOP_VINFO_BBS (loop_vinfo
)[i
];
2266 for (gimple_stmt_iterator si
= gsi_start_phis (bb
);
2267 !gsi_end_p (si
); gsi_next (&si
))
2269 stmt_vec_info stmt_info
= vinfo_for_stmt (gsi_stmt (si
));
2270 STMT_SLP_TYPE (stmt_info
) = loop_vect
;
2272 for (gimple_stmt_iterator si
= gsi_start_bb (bb
);
2273 !gsi_end_p (si
); gsi_next (&si
))
2275 stmt_vec_info stmt_info
= vinfo_for_stmt (gsi_stmt (si
));
2276 STMT_SLP_TYPE (stmt_info
) = loop_vect
;
2277 if (STMT_VINFO_IN_PATTERN_P (stmt_info
))
2279 stmt_info
= vinfo_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info
));
2280 STMT_SLP_TYPE (stmt_info
) = loop_vect
;
2281 for (gimple_stmt_iterator pi
2282 = gsi_start (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
));
2283 !gsi_end_p (pi
); gsi_next (&pi
))
2285 gimple
*pstmt
= gsi_stmt (pi
);
2286 STMT_SLP_TYPE (vinfo_for_stmt (pstmt
)) = loop_vect
;
2291 /* Free optimized alias test DDRS. */
2292 LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo
).release ();
2293 LOOP_VINFO_CHECK_UNEQUAL_ADDRS (loop_vinfo
).release ();
2294 /* Reset target cost data. */
2295 destroy_cost_data (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
));
2296 LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
)
2297 = init_cost (LOOP_VINFO_LOOP (loop_vinfo
));
2298 /* Reset assorted flags. */
2299 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
) = false;
2300 LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) = false;
2301 LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo
) = 0;
2306 /* Function vect_analyze_loop.
2308 Apply a set of analyses on LOOP, and create a loop_vec_info struct
2309 for it. The different analyses will record information in the
2310 loop_vec_info struct. If ORIG_LOOP_VINFO is not NULL epilogue must
2313 vect_analyze_loop (struct loop
*loop
, loop_vec_info orig_loop_vinfo
)
2315 loop_vec_info loop_vinfo
;
2316 unsigned int vector_sizes
;
2318 /* Autodetect first vector size we try. */
2319 current_vector_size
= 0;
2320 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
2322 if (dump_enabled_p ())
2323 dump_printf_loc (MSG_NOTE
, vect_location
,
2324 "===== analyze_loop_nest =====\n");
2326 if (loop_outer (loop
)
2327 && loop_vec_info_for_loop (loop_outer (loop
))
2328 && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop
))))
2330 if (dump_enabled_p ())
2331 dump_printf_loc (MSG_NOTE
, vect_location
,
2332 "outer-loop already vectorized.\n");
2338 /* Check the CFG characteristics of the loop (nesting, entry/exit). */
2339 loop_vinfo
= vect_analyze_loop_form (loop
);
2342 if (dump_enabled_p ())
2343 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2344 "bad loop form.\n");
2350 if (orig_loop_vinfo
)
2351 LOOP_VINFO_ORIG_LOOP_INFO (loop_vinfo
) = orig_loop_vinfo
;
2353 if (vect_analyze_loop_2 (loop_vinfo
, fatal
))
2355 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
) = 1;
2362 vector_sizes
&= ~current_vector_size
;
2364 || vector_sizes
== 0
2365 || current_vector_size
== 0)
2368 /* Try the next biggest vector size. */
2369 current_vector_size
= 1 << floor_log2 (vector_sizes
);
2370 if (dump_enabled_p ())
2371 dump_printf_loc (MSG_NOTE
, vect_location
,
2372 "***** Re-trying analysis with "
2373 "vector size %d\n", current_vector_size
);
2378 /* Function reduction_code_for_scalar_code
2381 CODE - tree_code of a reduction operations.
2384 REDUC_CODE - the corresponding tree-code to be used to reduce the
2385 vector of partial results into a single scalar result, or ERROR_MARK
2386 if the operation is a supported reduction operation, but does not have
2389 Return FALSE if CODE currently cannot be vectorized as reduction. */
2392 reduction_code_for_scalar_code (enum tree_code code
,
2393 enum tree_code
*reduc_code
)
2398 *reduc_code
= REDUC_MAX_EXPR
;
2402 *reduc_code
= REDUC_MIN_EXPR
;
2406 *reduc_code
= REDUC_PLUS_EXPR
;
2414 *reduc_code
= ERROR_MARK
;
2423 /* Error reporting helper for vect_is_simple_reduction below. GIMPLE statement
2424 STMT is printed with a message MSG. */
2427 report_vect_op (dump_flags_t msg_type
, gimple
*stmt
, const char *msg
)
2429 dump_printf_loc (msg_type
, vect_location
, "%s", msg
);
2430 dump_gimple_stmt (msg_type
, TDF_SLIM
, stmt
, 0);
2434 /* Detect SLP reduction of the form:
2444 PHI is the reduction phi node (#a1 = phi <a5, a0> above)
2445 FIRST_STMT is the first reduction stmt in the chain
2446 (a2 = operation (a1)).
2448 Return TRUE if a reduction chain was detected. */
2451 vect_is_slp_reduction (loop_vec_info loop_info
, gimple
*phi
,
2454 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
2455 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
2456 enum tree_code code
;
2457 gimple
*current_stmt
= NULL
, *loop_use_stmt
= NULL
, *first
, *next_stmt
;
2458 stmt_vec_info use_stmt_info
, current_stmt_info
;
2460 imm_use_iterator imm_iter
;
2461 use_operand_p use_p
;
2462 int nloop_uses
, size
= 0, n_out_of_loop_uses
;
2465 if (loop
!= vect_loop
)
2468 lhs
= PHI_RESULT (phi
);
2469 code
= gimple_assign_rhs_code (first_stmt
);
2473 n_out_of_loop_uses
= 0;
2474 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2476 gimple
*use_stmt
= USE_STMT (use_p
);
2477 if (is_gimple_debug (use_stmt
))
2480 /* Check if we got back to the reduction phi. */
2481 if (use_stmt
== phi
)
2483 loop_use_stmt
= use_stmt
;
2488 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2490 loop_use_stmt
= use_stmt
;
2494 n_out_of_loop_uses
++;
2496 /* There are can be either a single use in the loop or two uses in
2498 if (nloop_uses
> 1 || (n_out_of_loop_uses
&& nloop_uses
))
2505 /* We reached a statement with no loop uses. */
2506 if (nloop_uses
== 0)
2509 /* This is a loop exit phi, and we haven't reached the reduction phi. */
2510 if (gimple_code (loop_use_stmt
) == GIMPLE_PHI
)
2513 if (!is_gimple_assign (loop_use_stmt
)
2514 || code
!= gimple_assign_rhs_code (loop_use_stmt
)
2515 || !flow_bb_inside_loop_p (loop
, gimple_bb (loop_use_stmt
)))
2518 /* Insert USE_STMT into reduction chain. */
2519 use_stmt_info
= vinfo_for_stmt (loop_use_stmt
);
2522 current_stmt_info
= vinfo_for_stmt (current_stmt
);
2523 GROUP_NEXT_ELEMENT (current_stmt_info
) = loop_use_stmt
;
2524 GROUP_FIRST_ELEMENT (use_stmt_info
)
2525 = GROUP_FIRST_ELEMENT (current_stmt_info
);
2528 GROUP_FIRST_ELEMENT (use_stmt_info
) = loop_use_stmt
;
2530 lhs
= gimple_assign_lhs (loop_use_stmt
);
2531 current_stmt
= loop_use_stmt
;
2535 if (!found
|| loop_use_stmt
!= phi
|| size
< 2)
2538 /* Swap the operands, if needed, to make the reduction operand be the second
2540 lhs
= PHI_RESULT (phi
);
2541 next_stmt
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
2544 if (gimple_assign_rhs2 (next_stmt
) == lhs
)
2546 tree op
= gimple_assign_rhs1 (next_stmt
);
2547 gimple
*def_stmt
= NULL
;
2549 if (TREE_CODE (op
) == SSA_NAME
)
2550 def_stmt
= SSA_NAME_DEF_STMT (op
);
2552 /* Check that the other def is either defined in the loop
2553 ("vect_internal_def"), or it's an induction (defined by a
2554 loop-header phi-node). */
2556 && gimple_bb (def_stmt
)
2557 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2558 && (is_gimple_assign (def_stmt
)
2559 || is_gimple_call (def_stmt
)
2560 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2561 == vect_induction_def
2562 || (gimple_code (def_stmt
) == GIMPLE_PHI
2563 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2564 == vect_internal_def
2565 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
2567 lhs
= gimple_assign_lhs (next_stmt
);
2568 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
2576 tree op
= gimple_assign_rhs2 (next_stmt
);
2577 gimple
*def_stmt
= NULL
;
2579 if (TREE_CODE (op
) == SSA_NAME
)
2580 def_stmt
= SSA_NAME_DEF_STMT (op
);
2582 /* Check that the other def is either defined in the loop
2583 ("vect_internal_def"), or it's an induction (defined by a
2584 loop-header phi-node). */
2586 && gimple_bb (def_stmt
)
2587 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2588 && (is_gimple_assign (def_stmt
)
2589 || is_gimple_call (def_stmt
)
2590 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2591 == vect_induction_def
2592 || (gimple_code (def_stmt
) == GIMPLE_PHI
2593 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2594 == vect_internal_def
2595 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
2597 if (dump_enabled_p ())
2599 dump_printf_loc (MSG_NOTE
, vect_location
, "swapping oprnds: ");
2600 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, next_stmt
, 0);
2603 swap_ssa_operands (next_stmt
,
2604 gimple_assign_rhs1_ptr (next_stmt
),
2605 gimple_assign_rhs2_ptr (next_stmt
));
2606 update_stmt (next_stmt
);
2608 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (next_stmt
)))
2609 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
2615 lhs
= gimple_assign_lhs (next_stmt
);
2616 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
2619 /* Save the chain for further analysis in SLP detection. */
2620 first
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
2621 LOOP_VINFO_REDUCTION_CHAINS (loop_info
).safe_push (first
);
2622 GROUP_SIZE (vinfo_for_stmt (first
)) = size
;
2628 /* Function vect_is_simple_reduction
2630 (1) Detect a cross-iteration def-use cycle that represents a simple
2631 reduction computation. We look for the following pattern:
2636 a2 = operation (a3, a1)
2643 a2 = operation (a3, a1)
2646 1. operation is commutative and associative and it is safe to
2647 change the order of the computation
2648 2. no uses for a2 in the loop (a2 is used out of the loop)
2649 3. no uses of a1 in the loop besides the reduction operation
2650 4. no uses of a1 outside the loop.
2652 Conditions 1,4 are tested here.
2653 Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
2655 (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
2658 (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
2662 inner loop (def of a3)
2665 (4) Detect condition expressions, ie:
2666 for (int i = 0; i < N; i++)
2673 vect_is_simple_reduction (loop_vec_info loop_info
, gimple
*phi
,
2675 bool need_wrapping_integral_overflow
,
2676 enum vect_reduction_type
*v_reduc_type
)
2678 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
2679 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
2680 gimple
*def_stmt
, *def1
= NULL
, *def2
= NULL
, *phi_use_stmt
= NULL
;
2681 enum tree_code orig_code
, code
;
2682 tree op1
, op2
, op3
= NULL_TREE
, op4
= NULL_TREE
;
2686 imm_use_iterator imm_iter
;
2687 use_operand_p use_p
;
2690 *double_reduc
= false;
2691 *v_reduc_type
= TREE_CODE_REDUCTION
;
2693 tree phi_name
= PHI_RESULT (phi
);
2694 /* ??? If there are no uses of the PHI result the inner loop reduction
2695 won't be detected as possibly double-reduction by vectorizable_reduction
2696 because that tries to walk the PHI arg from the preheader edge which
2697 can be constant. See PR60382. */
2698 if (has_zero_uses (phi_name
))
2701 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, phi_name
)
2703 gimple
*use_stmt
= USE_STMT (use_p
);
2704 if (is_gimple_debug (use_stmt
))
2707 if (!flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2709 if (dump_enabled_p ())
2710 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2711 "intermediate value used outside loop.\n");
2719 if (dump_enabled_p ())
2720 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2721 "reduction value used in loop.\n");
2725 phi_use_stmt
= use_stmt
;
2728 edge latch_e
= loop_latch_edge (loop
);
2729 tree loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
2730 if (TREE_CODE (loop_arg
) != SSA_NAME
)
2732 if (dump_enabled_p ())
2734 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2735 "reduction: not ssa_name: ");
2736 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, loop_arg
);
2737 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
2742 def_stmt
= SSA_NAME_DEF_STMT (loop_arg
);
2743 if (is_gimple_assign (def_stmt
))
2745 name
= gimple_assign_lhs (def_stmt
);
2748 else if (gimple_code (def_stmt
) == GIMPLE_PHI
)
2750 name
= PHI_RESULT (def_stmt
);
2755 if (dump_enabled_p ())
2757 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2758 "reduction: unhandled reduction operation: ");
2759 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, def_stmt
, 0);
2764 if (! flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
)))
2768 auto_vec
<gphi
*, 3> lcphis
;
2769 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2771 gimple
*use_stmt
= USE_STMT (use_p
);
2772 if (is_gimple_debug (use_stmt
))
2774 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2777 /* We can have more than one loop-closed PHI. */
2778 lcphis
.safe_push (as_a
<gphi
*> (use_stmt
));
2781 if (dump_enabled_p ())
2782 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2783 "reduction used in loop.\n");
2788 /* If DEF_STMT is a phi node itself, we expect it to have a single argument
2789 defined in the inner loop. */
2792 op1
= PHI_ARG_DEF (def_stmt
, 0);
2794 if (gimple_phi_num_args (def_stmt
) != 1
2795 || TREE_CODE (op1
) != SSA_NAME
)
2797 if (dump_enabled_p ())
2798 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2799 "unsupported phi node definition.\n");
2804 def1
= SSA_NAME_DEF_STMT (op1
);
2805 if (gimple_bb (def1
)
2806 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2808 && flow_bb_inside_loop_p (loop
->inner
, gimple_bb (def1
))
2809 && is_gimple_assign (def1
)
2810 && flow_bb_inside_loop_p (loop
->inner
, gimple_bb (phi_use_stmt
)))
2812 if (dump_enabled_p ())
2813 report_vect_op (MSG_NOTE
, def_stmt
,
2814 "detected double reduction: ");
2816 *double_reduc
= true;
2823 /* If we are vectorizing an inner reduction we are executing that
2824 in the original order only in case we are not dealing with a
2825 double reduction. */
2826 bool check_reduction
= true;
2827 if (flow_loop_nested_p (vect_loop
, loop
))
2831 check_reduction
= false;
2832 FOR_EACH_VEC_ELT (lcphis
, i
, lcphi
)
2833 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_phi_result (lcphi
))
2835 gimple
*use_stmt
= USE_STMT (use_p
);
2836 if (is_gimple_debug (use_stmt
))
2838 if (! flow_bb_inside_loop_p (vect_loop
, gimple_bb (use_stmt
)))
2839 check_reduction
= true;
2843 bool nested_in_vect_loop
= flow_loop_nested_p (vect_loop
, loop
);
2844 code
= orig_code
= gimple_assign_rhs_code (def_stmt
);
2846 /* We can handle "res -= x[i]", which is non-associative by
2847 simply rewriting this into "res += -x[i]". Avoid changing
2848 gimple instruction for the first simple tests and only do this
2849 if we're allowed to change code at all. */
2850 if (code
== MINUS_EXPR
&& gimple_assign_rhs2 (def_stmt
) != phi_name
)
2853 if (code
== COND_EXPR
)
2855 if (! nested_in_vect_loop
)
2856 *v_reduc_type
= COND_REDUCTION
;
2858 op3
= gimple_assign_rhs1 (def_stmt
);
2859 if (COMPARISON_CLASS_P (op3
))
2861 op4
= TREE_OPERAND (op3
, 1);
2862 op3
= TREE_OPERAND (op3
, 0);
2864 if (op3
== phi_name
|| op4
== phi_name
)
2866 if (dump_enabled_p ())
2867 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2868 "reduction: condition depends on previous"
2873 op1
= gimple_assign_rhs2 (def_stmt
);
2874 op2
= gimple_assign_rhs3 (def_stmt
);
2876 else if (!commutative_tree_code (code
) || !associative_tree_code (code
))
2878 if (dump_enabled_p ())
2879 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2880 "reduction: not commutative/associative: ");
2883 else if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
2885 op1
= gimple_assign_rhs1 (def_stmt
);
2886 op2
= gimple_assign_rhs2 (def_stmt
);
2890 if (dump_enabled_p ())
2891 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2892 "reduction: not handled operation: ");
2896 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2898 if (dump_enabled_p ())
2899 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2900 "reduction: both uses not ssa_names: ");
2905 type
= TREE_TYPE (gimple_assign_lhs (def_stmt
));
2906 if ((TREE_CODE (op1
) == SSA_NAME
2907 && !types_compatible_p (type
,TREE_TYPE (op1
)))
2908 || (TREE_CODE (op2
) == SSA_NAME
2909 && !types_compatible_p (type
, TREE_TYPE (op2
)))
2910 || (op3
&& TREE_CODE (op3
) == SSA_NAME
2911 && !types_compatible_p (type
, TREE_TYPE (op3
)))
2912 || (op4
&& TREE_CODE (op4
) == SSA_NAME
2913 && !types_compatible_p (type
, TREE_TYPE (op4
))))
2915 if (dump_enabled_p ())
2917 dump_printf_loc (MSG_NOTE
, vect_location
,
2918 "reduction: multiple types: operation type: ");
2919 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, type
);
2920 dump_printf (MSG_NOTE
, ", operands types: ");
2921 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2923 dump_printf (MSG_NOTE
, ",");
2924 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2928 dump_printf (MSG_NOTE
, ",");
2929 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2935 dump_printf (MSG_NOTE
, ",");
2936 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2939 dump_printf (MSG_NOTE
, "\n");
2945 /* Check that it's ok to change the order of the computation.
2946 Generally, when vectorizing a reduction we change the order of the
2947 computation. This may change the behavior of the program in some
2948 cases, so we need to check that this is ok. One exception is when
2949 vectorizing an outer-loop: the inner-loop is executed sequentially,
2950 and therefore vectorizing reductions in the inner-loop during
2951 outer-loop vectorization is safe. */
2953 if (*v_reduc_type
!= COND_REDUCTION
2956 /* CHECKME: check for !flag_finite_math_only too? */
2957 if (SCALAR_FLOAT_TYPE_P (type
) && !flag_associative_math
)
2959 /* Changing the order of operations changes the semantics. */
2960 if (dump_enabled_p ())
2961 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2962 "reduction: unsafe fp math optimization: ");
2965 else if (INTEGRAL_TYPE_P (type
))
2967 if (!operation_no_trapping_overflow (type
, code
))
2969 /* Changing the order of operations changes the semantics. */
2970 if (dump_enabled_p ())
2971 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2972 "reduction: unsafe int math optimization"
2973 " (overflow traps): ");
2976 if (need_wrapping_integral_overflow
2977 && !TYPE_OVERFLOW_WRAPS (type
)
2978 && operation_can_overflow (code
))
2980 /* Changing the order of operations changes the semantics. */
2981 if (dump_enabled_p ())
2982 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2983 "reduction: unsafe int math optimization"
2984 " (overflow doesn't wrap): ");
2988 else if (SAT_FIXED_POINT_TYPE_P (type
))
2990 /* Changing the order of operations changes the semantics. */
2991 if (dump_enabled_p ())
2992 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2993 "reduction: unsafe fixed-point math optimization: ");
2998 /* Reduction is safe. We're dealing with one of the following:
2999 1) integer arithmetic and no trapv
3000 2) floating point arithmetic, and special flags permit this optimization
3001 3) nested cycle (i.e., outer loop vectorization). */
3002 if (TREE_CODE (op1
) == SSA_NAME
)
3003 def1
= SSA_NAME_DEF_STMT (op1
);
3005 if (TREE_CODE (op2
) == SSA_NAME
)
3006 def2
= SSA_NAME_DEF_STMT (op2
);
3008 if (code
!= COND_EXPR
3009 && ((!def1
|| gimple_nop_p (def1
)) && (!def2
|| gimple_nop_p (def2
))))
3011 if (dump_enabled_p ())
3012 report_vect_op (MSG_NOTE
, def_stmt
, "reduction: no defs for operands: ");
3016 /* Check that one def is the reduction def, defined by PHI,
3017 the other def is either defined in the loop ("vect_internal_def"),
3018 or it's an induction (defined by a loop-header phi-node). */
3020 if (def2
&& def2
== phi
3021 && (code
== COND_EXPR
3022 || !def1
|| gimple_nop_p (def1
)
3023 || !flow_bb_inside_loop_p (loop
, gimple_bb (def1
))
3024 || (def1
&& flow_bb_inside_loop_p (loop
, gimple_bb (def1
))
3025 && (is_gimple_assign (def1
)
3026 || is_gimple_call (def1
)
3027 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
3028 == vect_induction_def
3029 || (gimple_code (def1
) == GIMPLE_PHI
3030 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
3031 == vect_internal_def
3032 && !is_loop_header_bb_p (gimple_bb (def1
)))))))
3034 if (dump_enabled_p ())
3035 report_vect_op (MSG_NOTE
, def_stmt
, "detected reduction: ");
3039 if (def1
&& def1
== phi
3040 && (code
== COND_EXPR
3041 || !def2
|| gimple_nop_p (def2
)
3042 || !flow_bb_inside_loop_p (loop
, gimple_bb (def2
))
3043 || (def2
&& flow_bb_inside_loop_p (loop
, gimple_bb (def2
))
3044 && (is_gimple_assign (def2
)
3045 || is_gimple_call (def2
)
3046 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
3047 == vect_induction_def
3048 || (gimple_code (def2
) == GIMPLE_PHI
3049 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
3050 == vect_internal_def
3051 && !is_loop_header_bb_p (gimple_bb (def2
)))))))
3053 if (! nested_in_vect_loop
&& orig_code
!= MINUS_EXPR
)
3055 /* Check if we can swap operands (just for simplicity - so that
3056 the rest of the code can assume that the reduction variable
3057 is always the last (second) argument). */
3058 if (code
== COND_EXPR
)
3060 /* Swap cond_expr by inverting the condition. */
3061 tree cond_expr
= gimple_assign_rhs1 (def_stmt
);
3062 enum tree_code invert_code
= ERROR_MARK
;
3063 enum tree_code cond_code
= TREE_CODE (cond_expr
);
3065 if (TREE_CODE_CLASS (cond_code
) == tcc_comparison
)
3067 bool honor_nans
= HONOR_NANS (TREE_OPERAND (cond_expr
, 0));
3068 invert_code
= invert_tree_comparison (cond_code
, honor_nans
);
3070 if (invert_code
!= ERROR_MARK
)
3072 TREE_SET_CODE (cond_expr
, invert_code
);
3073 swap_ssa_operands (def_stmt
,
3074 gimple_assign_rhs2_ptr (def_stmt
),
3075 gimple_assign_rhs3_ptr (def_stmt
));
3079 if (dump_enabled_p ())
3080 report_vect_op (MSG_NOTE
, def_stmt
,
3081 "detected reduction: cannot swap operands "
3087 swap_ssa_operands (def_stmt
, gimple_assign_rhs1_ptr (def_stmt
),
3088 gimple_assign_rhs2_ptr (def_stmt
));
3090 if (dump_enabled_p ())
3091 report_vect_op (MSG_NOTE
, def_stmt
,
3092 "detected reduction: need to swap operands: ");
3094 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (def_stmt
)))
3095 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
3099 if (dump_enabled_p ())
3100 report_vect_op (MSG_NOTE
, def_stmt
, "detected reduction: ");
3106 /* Try to find SLP reduction chain. */
3107 if (! nested_in_vect_loop
3108 && code
!= COND_EXPR
3109 && orig_code
!= MINUS_EXPR
3110 && vect_is_slp_reduction (loop_info
, phi
, def_stmt
))
3112 if (dump_enabled_p ())
3113 report_vect_op (MSG_NOTE
, def_stmt
,
3114 "reduction: detected reduction chain: ");
3119 /* Dissolve group eventually half-built by vect_is_slp_reduction. */
3120 gimple
*first
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (def_stmt
));
3123 gimple
*next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (first
));
3124 GROUP_FIRST_ELEMENT (vinfo_for_stmt (first
)) = NULL
;
3125 GROUP_NEXT_ELEMENT (vinfo_for_stmt (first
)) = NULL
;
3129 /* Look for the expression computing loop_arg from loop PHI result. */
3130 auto_vec
<std::pair
<ssa_op_iter
, use_operand_p
> > path
;
3131 auto_bitmap visited
;
3132 tree lookfor
= PHI_RESULT (phi
);
3134 use_operand_p curr
= op_iter_init_phiuse (&curri
, as_a
<gphi
*>(phi
),
3136 while (USE_FROM_PTR (curr
) != loop_arg
)
3137 curr
= op_iter_next_use (&curri
);
3138 curri
.i
= curri
.numops
;
3141 path
.safe_push (std::make_pair (curri
, curr
));
3142 tree use
= USE_FROM_PTR (curr
);
3145 gimple
*def
= SSA_NAME_DEF_STMT (use
);
3146 if (gimple_nop_p (def
)
3147 || ! flow_bb_inside_loop_p (loop
, gimple_bb (def
)))
3152 std::pair
<ssa_op_iter
, use_operand_p
> x
= path
.pop ();
3156 curr
= op_iter_next_use (&curri
);
3157 /* Skip already visited or non-SSA operands (from iterating
3159 while (curr
!= NULL_USE_OPERAND_P
3160 && (TREE_CODE (USE_FROM_PTR (curr
)) != SSA_NAME
3161 || ! bitmap_set_bit (visited
,
3163 (USE_FROM_PTR (curr
)))));
3165 while (curr
== NULL_USE_OPERAND_P
&& ! path
.is_empty ());
3166 if (curr
== NULL_USE_OPERAND_P
)
3171 if (gimple_code (def
) == GIMPLE_PHI
)
3172 curr
= op_iter_init_phiuse (&curri
, as_a
<gphi
*>(def
), SSA_OP_USE
);
3174 curr
= op_iter_init_use (&curri
, def
, SSA_OP_USE
);
3175 while (curr
!= NULL_USE_OPERAND_P
3176 && (TREE_CODE (USE_FROM_PTR (curr
)) != SSA_NAME
3177 || ! bitmap_set_bit (visited
,
3179 (USE_FROM_PTR (curr
)))))
3180 curr
= op_iter_next_use (&curri
);
3181 if (curr
== NULL_USE_OPERAND_P
)
3186 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3188 dump_printf_loc (MSG_NOTE
, vect_location
,
3189 "reduction path: ");
3191 std::pair
<ssa_op_iter
, use_operand_p
> *x
;
3192 FOR_EACH_VEC_ELT (path
, i
, x
)
3194 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, USE_FROM_PTR (x
->second
));
3195 dump_printf (MSG_NOTE
, " ");
3197 dump_printf (MSG_NOTE
, "\n");
3200 /* Check whether the reduction path detected is valid. */
3201 bool fail
= path
.length () == 0;
3203 for (unsigned i
= 1; i
< path
.length (); ++i
)
3205 gimple
*use_stmt
= USE_STMT (path
[i
].second
);
3206 tree op
= USE_FROM_PTR (path
[i
].second
);
3207 if (! has_single_use (op
)
3208 || ! is_gimple_assign (use_stmt
))
3213 if (gimple_assign_rhs_code (use_stmt
) != code
)
3215 if (code
== PLUS_EXPR
3216 && gimple_assign_rhs_code (use_stmt
) == MINUS_EXPR
)
3218 /* Track whether we negate the reduction value each iteration. */
3219 if (gimple_assign_rhs2 (use_stmt
) == op
)
3229 if (! fail
&& ! neg
)
3232 if (dump_enabled_p ())
3234 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
3235 "reduction: unknown pattern: ");
3241 /* Wrapper around vect_is_simple_reduction, which will modify code
3242 in-place if it enables detection of more reductions. Arguments
3246 vect_force_simple_reduction (loop_vec_info loop_info
, gimple
*phi
,
3248 bool need_wrapping_integral_overflow
)
3250 enum vect_reduction_type v_reduc_type
;
3251 gimple
*def
= vect_is_simple_reduction (loop_info
, phi
, double_reduc
,
3252 need_wrapping_integral_overflow
,
3256 stmt_vec_info reduc_def_info
= vinfo_for_stmt (phi
);
3257 STMT_VINFO_REDUC_TYPE (reduc_def_info
) = v_reduc_type
;
3258 STMT_VINFO_REDUC_DEF (reduc_def_info
) = def
;
3259 reduc_def_info
= vinfo_for_stmt (def
);
3260 STMT_VINFO_REDUC_DEF (reduc_def_info
) = phi
;
3265 /* Calculate cost of peeling the loop PEEL_ITERS_PROLOGUE times. */
3267 vect_get_known_peeling_cost (loop_vec_info loop_vinfo
, int peel_iters_prologue
,
3268 int *peel_iters_epilogue
,
3269 stmt_vector_for_cost
*scalar_cost_vec
,
3270 stmt_vector_for_cost
*prologue_cost_vec
,
3271 stmt_vector_for_cost
*epilogue_cost_vec
)
3274 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3276 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
3278 *peel_iters_epilogue
= vf
/2;
3279 if (dump_enabled_p ())
3280 dump_printf_loc (MSG_NOTE
, vect_location
,
3281 "cost model: epilogue peel iters set to vf/2 "
3282 "because loop iterations are unknown .\n");
3284 /* If peeled iterations are known but number of scalar loop
3285 iterations are unknown, count a taken branch per peeled loop. */
3286 retval
= record_stmt_cost (prologue_cost_vec
, 1, cond_branch_taken
,
3287 NULL
, 0, vect_prologue
);
3288 retval
= record_stmt_cost (prologue_cost_vec
, 1, cond_branch_taken
,
3289 NULL
, 0, vect_epilogue
);
3293 int niters
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
3294 peel_iters_prologue
= niters
< peel_iters_prologue
?
3295 niters
: peel_iters_prologue
;
3296 *peel_iters_epilogue
= (niters
- peel_iters_prologue
) % vf
;
3297 /* If we need to peel for gaps, but no peeling is required, we have to
3298 peel VF iterations. */
3299 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) && !*peel_iters_epilogue
)
3300 *peel_iters_epilogue
= vf
;
3303 stmt_info_for_cost
*si
;
3305 if (peel_iters_prologue
)
3306 FOR_EACH_VEC_ELT (*scalar_cost_vec
, j
, si
)
3308 stmt_vec_info stmt_info
3309 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
3310 retval
+= record_stmt_cost (prologue_cost_vec
,
3311 si
->count
* peel_iters_prologue
,
3312 si
->kind
, stmt_info
, si
->misalign
,
3315 if (*peel_iters_epilogue
)
3316 FOR_EACH_VEC_ELT (*scalar_cost_vec
, j
, si
)
3318 stmt_vec_info stmt_info
3319 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
3320 retval
+= record_stmt_cost (epilogue_cost_vec
,
3321 si
->count
* *peel_iters_epilogue
,
3322 si
->kind
, stmt_info
, si
->misalign
,
3329 /* Function vect_estimate_min_profitable_iters
3331 Return the number of iterations required for the vector version of the
3332 loop to be profitable relative to the cost of the scalar version of the
3335 *RET_MIN_PROFITABLE_NITERS is a cost model profitability threshold
3336 of iterations for vectorization. -1 value means loop vectorization
3337 is not profitable. This returned value may be used for dynamic
3338 profitability check.
3340 *RET_MIN_PROFITABLE_ESTIMATE is a profitability threshold to be used
3341 for static check against estimated number of iterations. */
3344 vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo
,
3345 int *ret_min_profitable_niters
,
3346 int *ret_min_profitable_estimate
)
3348 int min_profitable_iters
;
3349 int min_profitable_estimate
;
3350 int peel_iters_prologue
;
3351 int peel_iters_epilogue
;
3352 unsigned vec_inside_cost
= 0;
3353 int vec_outside_cost
= 0;
3354 unsigned vec_prologue_cost
= 0;
3355 unsigned vec_epilogue_cost
= 0;
3356 int scalar_single_iter_cost
= 0;
3357 int scalar_outside_cost
= 0;
3358 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3359 int npeel
= LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
);
3360 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3362 /* Cost model disabled. */
3363 if (unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo
)))
3365 dump_printf_loc (MSG_NOTE
, vect_location
, "cost model disabled.\n");
3366 *ret_min_profitable_niters
= 0;
3367 *ret_min_profitable_estimate
= 0;
3371 /* Requires loop versioning tests to handle misalignment. */
3372 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
))
3374 /* FIXME: Make cost depend on complexity of individual check. */
3375 unsigned len
= LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).length ();
3376 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
3378 dump_printf (MSG_NOTE
,
3379 "cost model: Adding cost of checks for loop "
3380 "versioning to treat misalignment.\n");
3383 /* Requires loop versioning with alias checks. */
3384 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
3386 /* FIXME: Make cost depend on complexity of individual check. */
3387 unsigned len
= LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo
).length ();
3388 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
3390 len
= LOOP_VINFO_CHECK_UNEQUAL_ADDRS (loop_vinfo
).length ();
3392 /* Count LEN - 1 ANDs and LEN comparisons. */
3393 (void) add_stmt_cost (target_cost_data
, len
* 2 - 1, scalar_stmt
,
3394 NULL
, 0, vect_prologue
);
3395 dump_printf (MSG_NOTE
,
3396 "cost model: Adding cost of checks for loop "
3397 "versioning aliasing.\n");
3400 /* Requires loop versioning with niter checks. */
3401 if (LOOP_REQUIRES_VERSIONING_FOR_NITERS (loop_vinfo
))
3403 /* FIXME: Make cost depend on complexity of individual check. */
3404 (void) add_stmt_cost (target_cost_data
, 1, vector_stmt
, NULL
, 0,
3406 dump_printf (MSG_NOTE
,
3407 "cost model: Adding cost of checks for loop "
3408 "versioning niters.\n");
3411 if (LOOP_REQUIRES_VERSIONING (loop_vinfo
))
3412 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_taken
, NULL
, 0,
3415 /* Count statements in scalar loop. Using this as scalar cost for a single
3418 TODO: Add outer loop support.
3420 TODO: Consider assigning different costs to different scalar
3423 scalar_single_iter_cost
3424 = LOOP_VINFO_SINGLE_SCALAR_ITERATION_COST (loop_vinfo
);
3426 /* Add additional cost for the peeled instructions in prologue and epilogue
3429 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
3430 at compile-time - we assume it's vf/2 (the worst would be vf-1).
3432 TODO: Build an expression that represents peel_iters for prologue and
3433 epilogue to be used in a run-time test. */
3437 peel_iters_prologue
= vf
/2;
3438 dump_printf (MSG_NOTE
, "cost model: "
3439 "prologue peel iters set to vf/2.\n");
3441 /* If peeling for alignment is unknown, loop bound of main loop becomes
3443 peel_iters_epilogue
= vf
/2;
3444 dump_printf (MSG_NOTE
, "cost model: "
3445 "epilogue peel iters set to vf/2 because "
3446 "peeling for alignment is unknown.\n");
3448 /* If peeled iterations are unknown, count a taken branch and a not taken
3449 branch per peeled loop. Even if scalar loop iterations are known,
3450 vector iterations are not known since peeled prologue iterations are
3451 not known. Hence guards remain the same. */
3452 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_taken
,
3453 NULL
, 0, vect_prologue
);
3454 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_not_taken
,
3455 NULL
, 0, vect_prologue
);
3456 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_taken
,
3457 NULL
, 0, vect_epilogue
);
3458 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_not_taken
,
3459 NULL
, 0, vect_epilogue
);
3460 stmt_info_for_cost
*si
;
3462 FOR_EACH_VEC_ELT (LOOP_VINFO_SCALAR_ITERATION_COST (loop_vinfo
), j
, si
)
3464 struct _stmt_vec_info
*stmt_info
3465 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
3466 (void) add_stmt_cost (target_cost_data
,
3467 si
->count
* peel_iters_prologue
,
3468 si
->kind
, stmt_info
, si
->misalign
,
3470 (void) add_stmt_cost (target_cost_data
,
3471 si
->count
* peel_iters_epilogue
,
3472 si
->kind
, stmt_info
, si
->misalign
,
3478 stmt_vector_for_cost prologue_cost_vec
, epilogue_cost_vec
;
3479 stmt_info_for_cost
*si
;
3481 void *data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3483 prologue_cost_vec
.create (2);
3484 epilogue_cost_vec
.create (2);
3485 peel_iters_prologue
= npeel
;
3487 (void) vect_get_known_peeling_cost (loop_vinfo
, peel_iters_prologue
,
3488 &peel_iters_epilogue
,
3489 &LOOP_VINFO_SCALAR_ITERATION_COST
3492 &epilogue_cost_vec
);
3494 FOR_EACH_VEC_ELT (prologue_cost_vec
, j
, si
)
3496 struct _stmt_vec_info
*stmt_info
3497 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
3498 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
3499 si
->misalign
, vect_prologue
);
3502 FOR_EACH_VEC_ELT (epilogue_cost_vec
, j
, si
)
3504 struct _stmt_vec_info
*stmt_info
3505 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
3506 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
3507 si
->misalign
, vect_epilogue
);
3510 prologue_cost_vec
.release ();
3511 epilogue_cost_vec
.release ();
3514 /* FORNOW: The scalar outside cost is incremented in one of the
3517 1. The vectorizer checks for alignment and aliasing and generates
3518 a condition that allows dynamic vectorization. A cost model
3519 check is ANDED with the versioning condition. Hence scalar code
3520 path now has the added cost of the versioning check.
3522 if (cost > th & versioning_check)
3525 Hence run-time scalar is incremented by not-taken branch cost.
3527 2. The vectorizer then checks if a prologue is required. If the
3528 cost model check was not done before during versioning, it has to
3529 be done before the prologue check.
3532 prologue = scalar_iters
3537 if (prologue == num_iters)
3540 Hence the run-time scalar cost is incremented by a taken branch,
3541 plus a not-taken branch, plus a taken branch cost.
3543 3. The vectorizer then checks if an epilogue is required. If the
3544 cost model check was not done before during prologue check, it
3545 has to be done with the epilogue check.
3551 if (prologue == num_iters)
3554 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
3557 Hence the run-time scalar cost should be incremented by 2 taken
3560 TODO: The back end may reorder the BBS's differently and reverse
3561 conditions/branch directions. Change the estimates below to
3562 something more reasonable. */
3564 /* If the number of iterations is known and we do not do versioning, we can
3565 decide whether to vectorize at compile time. Hence the scalar version
3566 do not carry cost model guard costs. */
3567 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
3568 || LOOP_REQUIRES_VERSIONING (loop_vinfo
))
3570 /* Cost model check occurs at versioning. */
3571 if (LOOP_REQUIRES_VERSIONING (loop_vinfo
))
3572 scalar_outside_cost
+= vect_get_stmt_cost (cond_branch_not_taken
);
3575 /* Cost model check occurs at prologue generation. */
3576 if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
) < 0)
3577 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
)
3578 + vect_get_stmt_cost (cond_branch_not_taken
);
3579 /* Cost model check occurs at epilogue generation. */
3581 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
);
3585 /* Complete the target-specific cost calculations. */
3586 finish_cost (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
), &vec_prologue_cost
,
3587 &vec_inside_cost
, &vec_epilogue_cost
);
3589 vec_outside_cost
= (int)(vec_prologue_cost
+ vec_epilogue_cost
);
3591 if (dump_enabled_p ())
3593 dump_printf_loc (MSG_NOTE
, vect_location
, "Cost model analysis: \n");
3594 dump_printf (MSG_NOTE
, " Vector inside of loop cost: %d\n",
3596 dump_printf (MSG_NOTE
, " Vector prologue cost: %d\n",
3598 dump_printf (MSG_NOTE
, " Vector epilogue cost: %d\n",
3600 dump_printf (MSG_NOTE
, " Scalar iteration cost: %d\n",
3601 scalar_single_iter_cost
);
3602 dump_printf (MSG_NOTE
, " Scalar outside cost: %d\n",
3603 scalar_outside_cost
);
3604 dump_printf (MSG_NOTE
, " Vector outside cost: %d\n",
3606 dump_printf (MSG_NOTE
, " prologue iterations: %d\n",
3607 peel_iters_prologue
);
3608 dump_printf (MSG_NOTE
, " epilogue iterations: %d\n",
3609 peel_iters_epilogue
);
3612 /* Calculate number of iterations required to make the vector version
3613 profitable, relative to the loop bodies only. The following condition
3615 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
3617 SIC = scalar iteration cost, VIC = vector iteration cost,
3618 VOC = vector outside cost, VF = vectorization factor,
3619 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
3620 SOC = scalar outside cost for run time cost model check. */
3622 if ((scalar_single_iter_cost
* vf
) > (int) vec_inside_cost
)
3624 if (vec_outside_cost
<= 0)
3625 min_profitable_iters
= 0;
3628 min_profitable_iters
= ((vec_outside_cost
- scalar_outside_cost
) * vf
3629 - vec_inside_cost
* peel_iters_prologue
3630 - vec_inside_cost
* peel_iters_epilogue
)
3631 / ((scalar_single_iter_cost
* vf
)
3634 if ((scalar_single_iter_cost
* vf
* min_profitable_iters
)
3635 <= (((int) vec_inside_cost
* min_profitable_iters
)
3636 + (((int) vec_outside_cost
- scalar_outside_cost
) * vf
)))
3637 min_profitable_iters
++;
3640 /* vector version will never be profitable. */
3643 if (LOOP_VINFO_LOOP (loop_vinfo
)->force_vectorize
)
3644 warning_at (vect_location
, OPT_Wopenmp_simd
, "vectorization "
3645 "did not happen for a simd loop");
3647 if (dump_enabled_p ())
3648 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3649 "cost model: the vector iteration cost = %d "
3650 "divided by the scalar iteration cost = %d "
3651 "is greater or equal to the vectorization factor = %d"
3653 vec_inside_cost
, scalar_single_iter_cost
, vf
);
3654 *ret_min_profitable_niters
= -1;
3655 *ret_min_profitable_estimate
= -1;
3659 dump_printf (MSG_NOTE
,
3660 " Calculated minimum iters for profitability: %d\n",
3661 min_profitable_iters
);
3663 /* We want the vectorized loop to execute at least once. */
3664 if (min_profitable_iters
< (vf
+ peel_iters_prologue
+ peel_iters_epilogue
))
3665 min_profitable_iters
= vf
+ peel_iters_prologue
+ peel_iters_epilogue
;
3667 if (dump_enabled_p ())
3668 dump_printf_loc (MSG_NOTE
, vect_location
,
3669 " Runtime profitability threshold = %d\n",
3670 min_profitable_iters
);
3672 *ret_min_profitable_niters
= min_profitable_iters
;
3674 /* Calculate number of iterations required to make the vector version
3675 profitable, relative to the loop bodies only.
3677 Non-vectorized variant is SIC * niters and it must win over vector
3678 variant on the expected loop trip count. The following condition must hold true:
3679 SIC * niters > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC + SOC */
3681 if (vec_outside_cost
<= 0)
3682 min_profitable_estimate
= 0;
3685 min_profitable_estimate
= ((vec_outside_cost
+ scalar_outside_cost
) * vf
3686 - vec_inside_cost
* peel_iters_prologue
3687 - vec_inside_cost
* peel_iters_epilogue
)
3688 / ((scalar_single_iter_cost
* vf
)
3691 min_profitable_estimate
= MAX (min_profitable_estimate
, min_profitable_iters
);
3692 if (dump_enabled_p ())
3693 dump_printf_loc (MSG_NOTE
, vect_location
,
3694 " Static estimate profitability threshold = %d\n",
3695 min_profitable_estimate
);
3697 *ret_min_profitable_estimate
= min_profitable_estimate
;
3700 /* Writes into SEL a mask for a vec_perm, equivalent to a vec_shr by OFFSET
3701 vector elements (not bits) for a vector of mode MODE. */
3703 calc_vec_perm_mask_for_shift (machine_mode mode
, unsigned int offset
,
3706 unsigned int i
, nelt
= GET_MODE_NUNITS (mode
);
3708 for (i
= 0; i
< nelt
; i
++)
3709 sel
[i
] = (i
+ offset
) & (2*nelt
- 1);
3712 /* Checks whether the target supports whole-vector shifts for vectors of mode
3713 MODE. This is the case if _either_ the platform handles vec_shr_optab, _or_
3714 it supports vec_perm_const with masks for all necessary shift amounts. */
3716 have_whole_vector_shift (machine_mode mode
)
3718 if (optab_handler (vec_shr_optab
, mode
) != CODE_FOR_nothing
)
3721 if (direct_optab_handler (vec_perm_const_optab
, mode
) == CODE_FOR_nothing
)
3724 unsigned int i
, nelt
= GET_MODE_NUNITS (mode
);
3725 unsigned char *sel
= XALLOCAVEC (unsigned char, nelt
);
3727 for (i
= nelt
/2; i
>= 1; i
/=2)
3729 calc_vec_perm_mask_for_shift (mode
, i
, sel
);
3730 if (!can_vec_perm_p (mode
, false, sel
))
3736 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
3737 functions. Design better to avoid maintenance issues. */
3739 /* Function vect_model_reduction_cost.
3741 Models cost for a reduction operation, including the vector ops
3742 generated within the strip-mine loop, the initial definition before
3743 the loop, and the epilogue code that must be generated. */
3746 vect_model_reduction_cost (stmt_vec_info stmt_info
, enum tree_code reduc_code
,
3749 int prologue_cost
= 0, epilogue_cost
= 0;
3750 enum tree_code code
;
3755 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3756 struct loop
*loop
= NULL
;
3757 void *target_cost_data
;
3761 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3762 target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3765 target_cost_data
= BB_VINFO_TARGET_COST_DATA (STMT_VINFO_BB_VINFO (stmt_info
));
3767 /* Condition reductions generate two reductions in the loop. */
3768 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
)
3771 /* Cost of reduction op inside loop. */
3772 unsigned inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
3773 stmt_info
, 0, vect_body
);
3775 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3776 mode
= TYPE_MODE (vectype
);
3777 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
3780 orig_stmt
= STMT_VINFO_STMT (stmt_info
);
3782 code
= gimple_assign_rhs_code (orig_stmt
);
3784 /* Add in cost for initial definition.
3785 For cond reduction we have four vectors: initial index, step, initial
3786 result of the data reduction, initial value of the index reduction. */
3787 int prologue_stmts
= STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
3788 == COND_REDUCTION
? 4 : 1;
3789 prologue_cost
+= add_stmt_cost (target_cost_data
, prologue_stmts
,
3790 scalar_to_vec
, stmt_info
, 0,
3793 /* Determine cost of epilogue code.
3795 We have a reduction operator that will reduce the vector in one statement.
3796 Also requires scalar extract. */
3798 if (!loop
|| !nested_in_vect_loop_p (loop
, orig_stmt
))
3800 if (reduc_code
!= ERROR_MARK
)
3802 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
)
3804 /* An EQ stmt and an COND_EXPR stmt. */
3805 epilogue_cost
+= add_stmt_cost (target_cost_data
, 2,
3806 vector_stmt
, stmt_info
, 0,
3808 /* Reduction of the max index and a reduction of the found
3810 epilogue_cost
+= add_stmt_cost (target_cost_data
, 2,
3811 vec_to_scalar
, stmt_info
, 0,
3813 /* A broadcast of the max value. */
3814 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1,
3815 scalar_to_vec
, stmt_info
, 0,
3820 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1, vector_stmt
,
3821 stmt_info
, 0, vect_epilogue
);
3822 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1,
3823 vec_to_scalar
, stmt_info
, 0,
3827 else if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
)
3829 unsigned nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3830 /* Extraction of scalar elements. */
3831 epilogue_cost
+= add_stmt_cost (target_cost_data
, 2 * nunits
,
3832 vec_to_scalar
, stmt_info
, 0,
3834 /* Scalar max reductions via COND_EXPR / MAX_EXPR. */
3835 epilogue_cost
+= add_stmt_cost (target_cost_data
, 2 * nunits
- 3,
3836 scalar_stmt
, stmt_info
, 0,
3841 int vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
3843 TYPE_SIZE (TREE_TYPE (gimple_assign_lhs (orig_stmt
)));
3844 int element_bitsize
= tree_to_uhwi (bitsize
);
3845 int nelements
= vec_size_in_bits
/ element_bitsize
;
3847 if (code
== COND_EXPR
)
3850 optab
= optab_for_tree_code (code
, vectype
, optab_default
);
3852 /* We have a whole vector shift available. */
3853 if (optab
!= unknown_optab
3854 && VECTOR_MODE_P (mode
)
3855 && optab_handler (optab
, mode
) != CODE_FOR_nothing
3856 && have_whole_vector_shift (mode
))
3858 /* Final reduction via vector shifts and the reduction operator.
3859 Also requires scalar extract. */
3860 epilogue_cost
+= add_stmt_cost (target_cost_data
,
3861 exact_log2 (nelements
) * 2,
3862 vector_stmt
, stmt_info
, 0,
3864 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1,
3865 vec_to_scalar
, stmt_info
, 0,
3869 /* Use extracts and reduction op for final reduction. For N
3870 elements, we have N extracts and N-1 reduction ops. */
3871 epilogue_cost
+= add_stmt_cost (target_cost_data
,
3872 nelements
+ nelements
- 1,
3873 vector_stmt
, stmt_info
, 0,
3878 if (dump_enabled_p ())
3879 dump_printf (MSG_NOTE
,
3880 "vect_model_reduction_cost: inside_cost = %d, "
3881 "prologue_cost = %d, epilogue_cost = %d .\n", inside_cost
,
3882 prologue_cost
, epilogue_cost
);
3886 /* Function vect_model_induction_cost.
3888 Models cost for induction operations. */
3891 vect_model_induction_cost (stmt_vec_info stmt_info
, int ncopies
)
3893 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3894 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3895 unsigned inside_cost
, prologue_cost
;
3897 if (PURE_SLP_STMT (stmt_info
))
3900 /* loop cost for vec_loop. */
3901 inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
3902 stmt_info
, 0, vect_body
);
3904 /* prologue cost for vec_init and vec_step. */
3905 prologue_cost
= add_stmt_cost (target_cost_data
, 2, scalar_to_vec
,
3906 stmt_info
, 0, vect_prologue
);
3908 if (dump_enabled_p ())
3909 dump_printf_loc (MSG_NOTE
, vect_location
,
3910 "vect_model_induction_cost: inside_cost = %d, "
3911 "prologue_cost = %d .\n", inside_cost
, prologue_cost
);
3916 /* Function get_initial_def_for_reduction
3919 STMT - a stmt that performs a reduction operation in the loop.
3920 INIT_VAL - the initial value of the reduction variable
3923 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
3924 of the reduction (used for adjusting the epilog - see below).
3925 Return a vector variable, initialized according to the operation that STMT
3926 performs. This vector will be used as the initial value of the
3927 vector of partial results.
3929 Option1 (adjust in epilog): Initialize the vector as follows:
3930 add/bit or/xor: [0,0,...,0,0]
3931 mult/bit and: [1,1,...,1,1]
3932 min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
3933 and when necessary (e.g. add/mult case) let the caller know
3934 that it needs to adjust the result by init_val.
3936 Option2: Initialize the vector as follows:
3937 add/bit or/xor: [init_val,0,0,...,0]
3938 mult/bit and: [init_val,1,1,...,1]
3939 min/max/cond_expr: [init_val,init_val,...,init_val]
3940 and no adjustments are needed.
3942 For example, for the following code:
3948 STMT is 's = s + a[i]', and the reduction variable is 's'.
3949 For a vector of 4 units, we want to return either [0,0,0,init_val],
3950 or [0,0,0,0] and let the caller know that it needs to adjust
3951 the result at the end by 'init_val'.
3953 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
3954 initialization vector is simpler (same element in all entries), if
3955 ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
3957 A cost model should help decide between these two schemes. */
3960 get_initial_def_for_reduction (gimple
*stmt
, tree init_val
,
3961 tree
*adjustment_def
)
3963 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
3964 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
3965 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3966 tree scalar_type
= TREE_TYPE (init_val
);
3967 tree vectype
= get_vectype_for_scalar_type (scalar_type
);
3969 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3973 bool nested_in_vect_loop
= false;
3974 REAL_VALUE_TYPE real_init_val
= dconst0
;
3975 int int_init_val
= 0;
3976 gimple
*def_stmt
= NULL
;
3977 gimple_seq stmts
= NULL
;
3979 gcc_assert (vectype
);
3980 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3982 gcc_assert (POINTER_TYPE_P (scalar_type
) || INTEGRAL_TYPE_P (scalar_type
)
3983 || SCALAR_FLOAT_TYPE_P (scalar_type
));
3985 if (nested_in_vect_loop_p (loop
, stmt
))
3986 nested_in_vect_loop
= true;
3988 gcc_assert (loop
== (gimple_bb (stmt
))->loop_father
);
3990 /* In case of double reduction we only create a vector variable to be put
3991 in the reduction phi node. The actual statement creation is done in
3992 vect_create_epilog_for_reduction. */
3993 if (adjustment_def
&& nested_in_vect_loop
3994 && TREE_CODE (init_val
) == SSA_NAME
3995 && (def_stmt
= SSA_NAME_DEF_STMT (init_val
))
3996 && gimple_code (def_stmt
) == GIMPLE_PHI
3997 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
3998 && vinfo_for_stmt (def_stmt
)
3999 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
4000 == vect_double_reduction_def
)
4002 *adjustment_def
= NULL
;
4003 return vect_create_destination_var (init_val
, vectype
);
4006 /* In case of a nested reduction do not use an adjustment def as
4007 that case is not supported by the epilogue generation correctly
4008 if ncopies is not one. */
4009 if (adjustment_def
&& nested_in_vect_loop
)
4011 *adjustment_def
= NULL
;
4012 return vect_get_vec_def_for_operand (init_val
, stmt
);
4017 case WIDEN_SUM_EXPR
:
4027 /* ADJUSMENT_DEF is NULL when called from
4028 vect_create_epilog_for_reduction to vectorize double reduction. */
4030 *adjustment_def
= init_val
;
4032 if (code
== MULT_EXPR
)
4034 real_init_val
= dconst1
;
4038 if (code
== BIT_AND_EXPR
)
4041 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
4042 def_for_init
= build_real (scalar_type
, real_init_val
);
4044 def_for_init
= build_int_cst (scalar_type
, int_init_val
);
4046 /* Create a vector of '0' or '1' except the first element. */
4047 auto_vec
<tree
, 32> elts (nunits
);
4048 elts
.quick_grow (nunits
);
4049 for (i
= nunits
- 2; i
>= 0; --i
)
4050 elts
[i
+ 1] = def_for_init
;
4052 /* Option1: the first element is '0' or '1' as well. */
4055 elts
[0] = def_for_init
;
4057 init_def
= build_vector (vectype
, elts
);
4061 /* Option2: the first element is INIT_VAL. */
4063 if (TREE_CONSTANT (init_val
))
4064 init_def
= build_vector (vectype
, elts
);
4067 vec
<constructor_elt
, va_gc
> *v
;
4068 vec_alloc (v
, nunits
);
4069 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, init_val
);
4070 for (i
= 1; i
< nunits
; ++i
)
4071 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[i
]);
4072 init_def
= build_constructor (vectype
, v
);
4083 *adjustment_def
= NULL_TREE
;
4084 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_vinfo
) != COND_REDUCTION
)
4086 init_def
= vect_get_vec_def_for_operand (init_val
, stmt
);
4090 init_val
= gimple_convert (&stmts
, TREE_TYPE (vectype
), init_val
);
4091 if (! gimple_seq_empty_p (stmts
))
4092 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
4093 init_def
= build_vector_from_val (vectype
, init_val
);
4104 /* Get at the initial defs for the reduction PHIs in SLP_NODE.
4105 NUMBER_OF_VECTORS is the number of vector defs to create. */
4108 get_initial_defs_for_reduction (slp_tree slp_node
,
4109 vec
<tree
> *vec_oprnds
,
4110 unsigned int number_of_vectors
,
4111 enum tree_code code
, bool reduc_chain
)
4113 vec
<gimple
*> stmts
= SLP_TREE_SCALAR_STMTS (slp_node
);
4114 gimple
*stmt
= stmts
[0];
4115 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
4118 unsigned j
, number_of_places_left_in_vector
;
4119 tree vector_type
, scalar_type
;
4121 int group_size
= stmts
.length ();
4122 unsigned int vec_num
, i
;
4123 unsigned number_of_copies
= 1;
4125 voprnds
.create (number_of_vectors
);
4127 tree neutral_op
= NULL
;
4129 gimple_seq ctor_seq
= NULL
;
4131 vector_type
= STMT_VINFO_VECTYPE (stmt_vinfo
);
4132 scalar_type
= TREE_TYPE (vector_type
);
4133 nunits
= TYPE_VECTOR_SUBPARTS (vector_type
);
4135 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_reduction_def
);
4137 loop
= (gimple_bb (stmt
))->loop_father
;
4140 /* op is the reduction operand of the first stmt already. */
4141 /* For additional copies (see the explanation of NUMBER_OF_COPIES below)
4142 we need either neutral operands or the original operands. See
4143 get_initial_def_for_reduction() for details. */
4146 case WIDEN_SUM_EXPR
:
4153 neutral_op
= build_zero_cst (scalar_type
);
4157 neutral_op
= build_one_cst (scalar_type
);
4161 neutral_op
= build_all_ones_cst (scalar_type
);
4164 /* For MIN/MAX we don't have an easy neutral operand but
4165 the initial values can be used fine here. Only for
4166 a reduction chain we have to force a neutral element. */
4172 neutral_op
= PHI_ARG_DEF_FROM_EDGE (stmt
,
4173 loop_preheader_edge (loop
));
4177 gcc_assert (! reduc_chain
);
4181 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
4182 created vectors. It is greater than 1 if unrolling is performed.
4184 For example, we have two scalar operands, s1 and s2 (e.g., group of
4185 strided accesses of size two), while NUNITS is four (i.e., four scalars
4186 of this type can be packed in a vector). The output vector will contain
4187 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
4190 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
4191 containing the operands.
4193 For example, NUNITS is four as before, and the group size is 8
4194 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
4195 {s5, s6, s7, s8}. */
4197 number_of_copies
= nunits
* number_of_vectors
/ group_size
;
4199 number_of_places_left_in_vector
= nunits
;
4201 auto_vec
<tree
, 32> elts (nunits
);
4202 elts
.quick_grow (nunits
);
4203 for (j
= 0; j
< number_of_copies
; j
++)
4205 for (i
= group_size
- 1; stmts
.iterate (i
, &stmt
); i
--)
4208 /* Get the def before the loop. In reduction chain we have only
4209 one initial value. */
4210 if ((j
!= (number_of_copies
- 1)
4211 || (reduc_chain
&& i
!= 0))
4215 op
= PHI_ARG_DEF_FROM_EDGE (stmt
,
4216 loop_preheader_edge (loop
));
4218 /* Create 'vect_ = {op0,op1,...,opn}'. */
4219 number_of_places_left_in_vector
--;
4220 elts
[number_of_places_left_in_vector
] = op
;
4221 if (!CONSTANT_CLASS_P (op
))
4224 if (number_of_places_left_in_vector
== 0)
4227 vec_cst
= build_vector (vector_type
, elts
);
4230 vec
<constructor_elt
, va_gc
> *v
;
4232 vec_alloc (v
, nunits
);
4233 for (k
= 0; k
< nunits
; ++k
)
4234 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[k
]);
4235 vec_cst
= build_constructor (vector_type
, v
);
4238 gimple_stmt_iterator gsi
;
4239 init
= vect_init_vector (stmt
, vec_cst
, vector_type
, NULL
);
4240 if (ctor_seq
!= NULL
)
4242 gsi
= gsi_for_stmt (SSA_NAME_DEF_STMT (init
));
4243 gsi_insert_seq_before_without_update (&gsi
, ctor_seq
,
4247 voprnds
.quick_push (init
);
4249 number_of_places_left_in_vector
= nunits
;
4255 /* Since the vectors are created in the reverse order, we should invert
4257 vec_num
= voprnds
.length ();
4258 for (j
= vec_num
; j
!= 0; j
--)
4260 vop
= voprnds
[j
- 1];
4261 vec_oprnds
->quick_push (vop
);
4266 /* In case that VF is greater than the unrolling factor needed for the SLP
4267 group of stmts, NUMBER_OF_VECTORS to be created is greater than
4268 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
4269 to replicate the vectors. */
4270 while (number_of_vectors
> vec_oprnds
->length ())
4272 tree neutral_vec
= NULL
;
4277 neutral_vec
= build_vector_from_val (vector_type
, neutral_op
);
4279 vec_oprnds
->quick_push (neutral_vec
);
4283 for (i
= 0; vec_oprnds
->iterate (i
, &vop
) && i
< vec_num
; i
++)
4284 vec_oprnds
->quick_push (vop
);
4290 /* Function vect_create_epilog_for_reduction
4292 Create code at the loop-epilog to finalize the result of a reduction
4295 VECT_DEFS is list of vector of partial results, i.e., the lhs's of vector
4296 reduction statements.
4297 STMT is the scalar reduction stmt that is being vectorized.
4298 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
4299 number of elements that we can fit in a vectype (nunits). In this case
4300 we have to generate more than one vector stmt - i.e - we need to "unroll"
4301 the vector stmt by a factor VF/nunits. For more details see documentation
4302 in vectorizable_operation.
4303 REDUC_CODE is the tree-code for the epilog reduction.
4304 REDUCTION_PHIS is a list of the phi-nodes that carry the reduction
4306 REDUC_INDEX is the index of the operand in the right hand side of the
4307 statement that is defined by REDUCTION_PHI.
4308 DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
4309 SLP_NODE is an SLP node containing a group of reduction statements. The
4310 first one in this group is STMT.
4313 1. Creates the reduction def-use cycles: sets the arguments for
4315 The loop-entry argument is the vectorized initial-value of the reduction.
4316 The loop-latch argument is taken from VECT_DEFS - the vector of partial
4318 2. "Reduces" each vector of partial results VECT_DEFS into a single result,
4319 by applying the operation specified by REDUC_CODE if available, or by
4320 other means (whole-vector shifts or a scalar loop).
4321 The function also creates a new phi node at the loop exit to preserve
4322 loop-closed form, as illustrated below.
4324 The flow at the entry to this function:
4327 vec_def = phi <null, null> # REDUCTION_PHI
4328 VECT_DEF = vector_stmt # vectorized form of STMT
4329 s_loop = scalar_stmt # (scalar) STMT
4331 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4335 The above is transformed by this function into:
4338 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
4339 VECT_DEF = vector_stmt # vectorized form of STMT
4340 s_loop = scalar_stmt # (scalar) STMT
4342 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4343 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4344 v_out2 = reduce <v_out1>
4345 s_out3 = extract_field <v_out2, 0>
4346 s_out4 = adjust_result <s_out3>
4352 vect_create_epilog_for_reduction (vec
<tree
> vect_defs
, gimple
*stmt
,
4353 gimple
*reduc_def_stmt
,
4354 int ncopies
, enum tree_code reduc_code
,
4355 vec
<gimple
*> reduction_phis
,
4358 slp_instance slp_node_instance
)
4360 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
4361 stmt_vec_info prev_phi_info
;
4364 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
4365 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
), *outer_loop
= NULL
;
4366 basic_block exit_bb
;
4369 gimple
*new_phi
= NULL
, *phi
;
4370 gimple_stmt_iterator exit_gsi
;
4372 tree new_temp
= NULL_TREE
, new_dest
, new_name
, new_scalar_dest
;
4373 gimple
*epilog_stmt
= NULL
;
4374 enum tree_code code
= gimple_assign_rhs_code (stmt
);
4377 tree adjustment_def
= NULL
;
4378 tree vec_initial_def
= NULL
;
4379 tree expr
, def
, initial_def
= NULL
;
4380 tree orig_name
, scalar_result
;
4381 imm_use_iterator imm_iter
, phi_imm_iter
;
4382 use_operand_p use_p
, phi_use_p
;
4383 gimple
*use_stmt
, *orig_stmt
, *reduction_phi
= NULL
;
4384 bool nested_in_vect_loop
= false;
4385 auto_vec
<gimple
*> new_phis
;
4386 auto_vec
<gimple
*> inner_phis
;
4387 enum vect_def_type dt
= vect_unknown_def_type
;
4389 auto_vec
<tree
> scalar_results
;
4390 unsigned int group_size
= 1, k
, ratio
;
4391 auto_vec
<tree
> vec_initial_defs
;
4392 auto_vec
<gimple
*> phis
;
4393 bool slp_reduc
= false;
4394 tree new_phi_result
;
4395 gimple
*inner_phi
= NULL
;
4396 tree induction_index
= NULL_TREE
;
4399 group_size
= SLP_TREE_SCALAR_STMTS (slp_node
).length ();
4401 if (nested_in_vect_loop_p (loop
, stmt
))
4405 nested_in_vect_loop
= true;
4406 gcc_assert (!slp_node
);
4409 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
4410 gcc_assert (vectype
);
4411 mode
= TYPE_MODE (vectype
);
4413 /* 1. Create the reduction def-use cycle:
4414 Set the arguments of REDUCTION_PHIS, i.e., transform
4417 vec_def = phi <null, null> # REDUCTION_PHI
4418 VECT_DEF = vector_stmt # vectorized form of STMT
4424 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
4425 VECT_DEF = vector_stmt # vectorized form of STMT
4428 (in case of SLP, do it for all the phis). */
4430 /* Get the loop-entry arguments. */
4431 enum vect_def_type initial_def_dt
= vect_unknown_def_type
;
4434 unsigned vec_num
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
4435 vec_initial_defs
.reserve (vec_num
);
4436 get_initial_defs_for_reduction (slp_node_instance
->reduc_phis
,
4437 &vec_initial_defs
, vec_num
, code
,
4438 GROUP_FIRST_ELEMENT (stmt_info
));
4442 /* Get at the scalar def before the loop, that defines the initial value
4443 of the reduction variable. */
4445 initial_def
= PHI_ARG_DEF_FROM_EDGE (reduc_def_stmt
,
4446 loop_preheader_edge (loop
));
4447 vect_is_simple_use (initial_def
, loop_vinfo
, &def_stmt
, &initial_def_dt
);
4448 vec_initial_def
= get_initial_def_for_reduction (stmt
, initial_def
,
4450 vec_initial_defs
.create (1);
4451 vec_initial_defs
.quick_push (vec_initial_def
);
4454 /* Set phi nodes arguments. */
4455 FOR_EACH_VEC_ELT (reduction_phis
, i
, phi
)
4457 tree vec_init_def
, def
;
4459 vec_init_def
= force_gimple_operand (vec_initial_defs
[i
], &stmts
,
4462 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
4465 for (j
= 0; j
< ncopies
; j
++)
4469 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
4470 if (nested_in_vect_loop
)
4472 = vect_get_vec_def_for_stmt_copy (initial_def_dt
,
4476 /* Set the loop-entry arg of the reduction-phi. */
4478 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
4479 == INTEGER_INDUC_COND_REDUCTION
)
4481 /* Initialise the reduction phi to zero. This prevents initial
4482 values of non-zero interferring with the reduction op. */
4483 gcc_assert (ncopies
== 1);
4484 gcc_assert (i
== 0);
4486 tree vec_init_def_type
= TREE_TYPE (vec_init_def
);
4487 tree zero_vec
= build_zero_cst (vec_init_def_type
);
4489 add_phi_arg (as_a
<gphi
*> (phi
), zero_vec
,
4490 loop_preheader_edge (loop
), UNKNOWN_LOCATION
);
4493 add_phi_arg (as_a
<gphi
*> (phi
), vec_init_def
,
4494 loop_preheader_edge (loop
), UNKNOWN_LOCATION
);
4496 /* Set the loop-latch arg for the reduction-phi. */
4498 def
= vect_get_vec_def_for_stmt_copy (vect_unknown_def_type
, def
);
4500 add_phi_arg (as_a
<gphi
*> (phi
), def
, loop_latch_edge (loop
),
4503 if (dump_enabled_p ())
4505 dump_printf_loc (MSG_NOTE
, vect_location
,
4506 "transform reduction: created def-use cycle: ");
4507 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
4508 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, SSA_NAME_DEF_STMT (def
), 0);
4513 /* For cond reductions we want to create a new vector (INDEX_COND_EXPR)
4514 which is updated with the current index of the loop for every match of
4515 the original loop's cond_expr (VEC_STMT). This results in a vector
4516 containing the last time the condition passed for that vector lane.
4517 The first match will be a 1 to allow 0 to be used for non-matching
4518 indexes. If there are no matches at all then the vector will be all
4520 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
)
4522 tree indx_before_incr
, indx_after_incr
;
4523 int nunits_out
= TYPE_VECTOR_SUBPARTS (vectype
);
4526 gimple
*vec_stmt
= STMT_VINFO_VEC_STMT (stmt_info
);
4527 gcc_assert (gimple_assign_rhs_code (vec_stmt
) == VEC_COND_EXPR
);
4529 int scalar_precision
4530 = GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (vectype
)));
4531 tree cr_index_scalar_type
= make_unsigned_type (scalar_precision
);
4532 tree cr_index_vector_type
= build_vector_type
4533 (cr_index_scalar_type
, TYPE_VECTOR_SUBPARTS (vectype
));
4535 /* First we create a simple vector induction variable which starts
4536 with the values {1,2,3,...} (SERIES_VECT) and increments by the
4537 vector size (STEP). */
4539 /* Create a {1,2,3,...} vector. */
4540 auto_vec
<tree
, 32> vtemp (nunits_out
);
4541 for (k
= 0; k
< nunits_out
; ++k
)
4542 vtemp
.quick_push (build_int_cst (cr_index_scalar_type
, k
+ 1));
4543 tree series_vect
= build_vector (cr_index_vector_type
, vtemp
);
4545 /* Create a vector of the step value. */
4546 tree step
= build_int_cst (cr_index_scalar_type
, nunits_out
);
4547 tree vec_step
= build_vector_from_val (cr_index_vector_type
, step
);
4549 /* Create an induction variable. */
4550 gimple_stmt_iterator incr_gsi
;
4552 standard_iv_increment_position (loop
, &incr_gsi
, &insert_after
);
4553 create_iv (series_vect
, vec_step
, NULL_TREE
, loop
, &incr_gsi
,
4554 insert_after
, &indx_before_incr
, &indx_after_incr
);
4556 /* Next create a new phi node vector (NEW_PHI_TREE) which starts
4557 filled with zeros (VEC_ZERO). */
4559 /* Create a vector of 0s. */
4560 tree zero
= build_zero_cst (cr_index_scalar_type
);
4561 tree vec_zero
= build_vector_from_val (cr_index_vector_type
, zero
);
4563 /* Create a vector phi node. */
4564 tree new_phi_tree
= make_ssa_name (cr_index_vector_type
);
4565 new_phi
= create_phi_node (new_phi_tree
, loop
->header
);
4566 set_vinfo_for_stmt (new_phi
,
4567 new_stmt_vec_info (new_phi
, loop_vinfo
));
4568 add_phi_arg (as_a
<gphi
*> (new_phi
), vec_zero
,
4569 loop_preheader_edge (loop
), UNKNOWN_LOCATION
);
4571 /* Now take the condition from the loops original cond_expr
4572 (VEC_STMT) and produce a new cond_expr (INDEX_COND_EXPR) which for
4573 every match uses values from the induction variable
4574 (INDEX_BEFORE_INCR) otherwise uses values from the phi node
4576 Finally, we update the phi (NEW_PHI_TREE) to take the value of
4577 the new cond_expr (INDEX_COND_EXPR). */
4579 /* Duplicate the condition from vec_stmt. */
4580 tree ccompare
= unshare_expr (gimple_assign_rhs1 (vec_stmt
));
4582 /* Create a conditional, where the condition is taken from vec_stmt
4583 (CCOMPARE), then is the induction index (INDEX_BEFORE_INCR) and
4584 else is the phi (NEW_PHI_TREE). */
4585 tree index_cond_expr
= build3 (VEC_COND_EXPR
, cr_index_vector_type
,
4586 ccompare
, indx_before_incr
,
4588 induction_index
= make_ssa_name (cr_index_vector_type
);
4589 gimple
*index_condition
= gimple_build_assign (induction_index
,
4591 gsi_insert_before (&incr_gsi
, index_condition
, GSI_SAME_STMT
);
4592 stmt_vec_info index_vec_info
= new_stmt_vec_info (index_condition
,
4594 STMT_VINFO_VECTYPE (index_vec_info
) = cr_index_vector_type
;
4595 set_vinfo_for_stmt (index_condition
, index_vec_info
);
4597 /* Update the phi with the vec cond. */
4598 add_phi_arg (as_a
<gphi
*> (new_phi
), induction_index
,
4599 loop_latch_edge (loop
), UNKNOWN_LOCATION
);
4602 /* 2. Create epilog code.
4603 The reduction epilog code operates across the elements of the vector
4604 of partial results computed by the vectorized loop.
4605 The reduction epilog code consists of:
4607 step 1: compute the scalar result in a vector (v_out2)
4608 step 2: extract the scalar result (s_out3) from the vector (v_out2)
4609 step 3: adjust the scalar result (s_out3) if needed.
4611 Step 1 can be accomplished using one the following three schemes:
4612 (scheme 1) using reduc_code, if available.
4613 (scheme 2) using whole-vector shifts, if available.
4614 (scheme 3) using a scalar loop. In this case steps 1+2 above are
4617 The overall epilog code looks like this:
4619 s_out0 = phi <s_loop> # original EXIT_PHI
4620 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4621 v_out2 = reduce <v_out1> # step 1
4622 s_out3 = extract_field <v_out2, 0> # step 2
4623 s_out4 = adjust_result <s_out3> # step 3
4625 (step 3 is optional, and steps 1 and 2 may be combined).
4626 Lastly, the uses of s_out0 are replaced by s_out4. */
4629 /* 2.1 Create new loop-exit-phis to preserve loop-closed form:
4630 v_out1 = phi <VECT_DEF>
4631 Store them in NEW_PHIS. */
4633 exit_bb
= single_exit (loop
)->dest
;
4634 prev_phi_info
= NULL
;
4635 new_phis
.create (vect_defs
.length ());
4636 FOR_EACH_VEC_ELT (vect_defs
, i
, def
)
4638 for (j
= 0; j
< ncopies
; j
++)
4640 tree new_def
= copy_ssa_name (def
);
4641 phi
= create_phi_node (new_def
, exit_bb
);
4642 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, loop_vinfo
));
4644 new_phis
.quick_push (phi
);
4647 def
= vect_get_vec_def_for_stmt_copy (dt
, def
);
4648 STMT_VINFO_RELATED_STMT (prev_phi_info
) = phi
;
4651 SET_PHI_ARG_DEF (phi
, single_exit (loop
)->dest_idx
, def
);
4652 prev_phi_info
= vinfo_for_stmt (phi
);
4656 /* The epilogue is created for the outer-loop, i.e., for the loop being
4657 vectorized. Create exit phis for the outer loop. */
4661 exit_bb
= single_exit (loop
)->dest
;
4662 inner_phis
.create (vect_defs
.length ());
4663 FOR_EACH_VEC_ELT (new_phis
, i
, phi
)
4665 tree new_result
= copy_ssa_name (PHI_RESULT (phi
));
4666 gphi
*outer_phi
= create_phi_node (new_result
, exit_bb
);
4667 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
4669 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
4671 inner_phis
.quick_push (phi
);
4672 new_phis
[i
] = outer_phi
;
4673 prev_phi_info
= vinfo_for_stmt (outer_phi
);
4674 while (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
)))
4676 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
4677 new_result
= copy_ssa_name (PHI_RESULT (phi
));
4678 outer_phi
= create_phi_node (new_result
, exit_bb
);
4679 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
4681 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
4683 STMT_VINFO_RELATED_STMT (prev_phi_info
) = outer_phi
;
4684 prev_phi_info
= vinfo_for_stmt (outer_phi
);
4689 exit_gsi
= gsi_after_labels (exit_bb
);
4691 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
4692 (i.e. when reduc_code is not available) and in the final adjustment
4693 code (if needed). Also get the original scalar reduction variable as
4694 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
4695 represents a reduction pattern), the tree-code and scalar-def are
4696 taken from the original stmt that the pattern-stmt (STMT) replaces.
4697 Otherwise (it is a regular reduction) - the tree-code and scalar-def
4698 are taken from STMT. */
4700 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
4703 /* Regular reduction */
4708 /* Reduction pattern */
4709 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (orig_stmt
);
4710 gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
));
4711 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo
) == stmt
);
4714 code
= gimple_assign_rhs_code (orig_stmt
);
4715 /* For MINUS_EXPR the initial vector is [init_val,0,...,0], therefore,
4716 partial results are added and not subtracted. */
4717 if (code
== MINUS_EXPR
)
4720 scalar_dest
= gimple_assign_lhs (orig_stmt
);
4721 scalar_type
= TREE_TYPE (scalar_dest
);
4722 scalar_results
.create (group_size
);
4723 new_scalar_dest
= vect_create_destination_var (scalar_dest
, NULL
);
4724 bitsize
= TYPE_SIZE (scalar_type
);
4726 /* In case this is a reduction in an inner-loop while vectorizing an outer
4727 loop - we don't need to extract a single scalar result at the end of the
4728 inner-loop (unless it is double reduction, i.e., the use of reduction is
4729 outside the outer-loop). The final vector of partial results will be used
4730 in the vectorized outer-loop, or reduced to a scalar result at the end of
4732 if (nested_in_vect_loop
&& !double_reduc
)
4733 goto vect_finalize_reduction
;
4735 /* SLP reduction without reduction chain, e.g.,
4739 b2 = operation (b1) */
4740 slp_reduc
= (slp_node
&& !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)));
4742 /* In case of reduction chain, e.g.,
4745 a3 = operation (a2),
4747 we may end up with more than one vector result. Here we reduce them to
4749 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4751 tree first_vect
= PHI_RESULT (new_phis
[0]);
4752 gassign
*new_vec_stmt
= NULL
;
4753 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4754 for (k
= 1; k
< new_phis
.length (); k
++)
4756 gimple
*next_phi
= new_phis
[k
];
4757 tree second_vect
= PHI_RESULT (next_phi
);
4758 tree tem
= make_ssa_name (vec_dest
, new_vec_stmt
);
4759 new_vec_stmt
= gimple_build_assign (tem
, code
,
4760 first_vect
, second_vect
);
4761 gsi_insert_before (&exit_gsi
, new_vec_stmt
, GSI_SAME_STMT
);
4765 new_phi_result
= first_vect
;
4768 new_phis
.truncate (0);
4769 new_phis
.safe_push (new_vec_stmt
);
4772 /* Likewise if we couldn't use a single defuse cycle. */
4773 else if (ncopies
> 1)
4775 gcc_assert (new_phis
.length () == 1);
4776 tree first_vect
= PHI_RESULT (new_phis
[0]);
4777 gassign
*new_vec_stmt
= NULL
;
4778 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4779 gimple
*next_phi
= new_phis
[0];
4780 for (int k
= 1; k
< ncopies
; ++k
)
4782 next_phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next_phi
));
4783 tree second_vect
= PHI_RESULT (next_phi
);
4784 tree tem
= make_ssa_name (vec_dest
, new_vec_stmt
);
4785 new_vec_stmt
= gimple_build_assign (tem
, code
,
4786 first_vect
, second_vect
);
4787 gsi_insert_before (&exit_gsi
, new_vec_stmt
, GSI_SAME_STMT
);
4790 new_phi_result
= first_vect
;
4791 new_phis
.truncate (0);
4792 new_phis
.safe_push (new_vec_stmt
);
4795 new_phi_result
= PHI_RESULT (new_phis
[0]);
4797 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
4798 && reduc_code
!= ERROR_MARK
)
4800 /* For condition reductions, we have a vector (NEW_PHI_RESULT) containing
4801 various data values where the condition matched and another vector
4802 (INDUCTION_INDEX) containing all the indexes of those matches. We
4803 need to extract the last matching index (which will be the index with
4804 highest value) and use this to index into the data vector.
4805 For the case where there were no matches, the data vector will contain
4806 all default values and the index vector will be all zeros. */
4808 /* Get various versions of the type of the vector of indexes. */
4809 tree index_vec_type
= TREE_TYPE (induction_index
);
4810 gcc_checking_assert (TYPE_UNSIGNED (index_vec_type
));
4811 tree index_scalar_type
= TREE_TYPE (index_vec_type
);
4812 tree index_vec_cmp_type
= build_same_sized_truth_vector_type
4815 /* Get an unsigned integer version of the type of the data vector. */
4816 int scalar_precision
4817 = GET_MODE_PRECISION (SCALAR_TYPE_MODE (scalar_type
));
4818 tree scalar_type_unsigned
= make_unsigned_type (scalar_precision
);
4819 tree vectype_unsigned
= build_vector_type
4820 (scalar_type_unsigned
, TYPE_VECTOR_SUBPARTS (vectype
));
4822 /* First we need to create a vector (ZERO_VEC) of zeros and another
4823 vector (MAX_INDEX_VEC) filled with the last matching index, which we
4824 can create using a MAX reduction and then expanding.
4825 In the case where the loop never made any matches, the max index will
4828 /* Vector of {0, 0, 0,...}. */
4829 tree zero_vec
= make_ssa_name (vectype
);
4830 tree zero_vec_rhs
= build_zero_cst (vectype
);
4831 gimple
*zero_vec_stmt
= gimple_build_assign (zero_vec
, zero_vec_rhs
);
4832 gsi_insert_before (&exit_gsi
, zero_vec_stmt
, GSI_SAME_STMT
);
4834 /* Find maximum value from the vector of found indexes. */
4835 tree max_index
= make_ssa_name (index_scalar_type
);
4836 gimple
*max_index_stmt
= gimple_build_assign (max_index
, REDUC_MAX_EXPR
,
4838 gsi_insert_before (&exit_gsi
, max_index_stmt
, GSI_SAME_STMT
);
4840 /* Vector of {max_index, max_index, max_index,...}. */
4841 tree max_index_vec
= make_ssa_name (index_vec_type
);
4842 tree max_index_vec_rhs
= build_vector_from_val (index_vec_type
,
4844 gimple
*max_index_vec_stmt
= gimple_build_assign (max_index_vec
,
4846 gsi_insert_before (&exit_gsi
, max_index_vec_stmt
, GSI_SAME_STMT
);
4848 /* Next we compare the new vector (MAX_INDEX_VEC) full of max indexes
4849 with the vector (INDUCTION_INDEX) of found indexes, choosing values
4850 from the data vector (NEW_PHI_RESULT) for matches, 0 (ZERO_VEC)
4851 otherwise. Only one value should match, resulting in a vector
4852 (VEC_COND) with one data value and the rest zeros.
4853 In the case where the loop never made any matches, every index will
4854 match, resulting in a vector with all data values (which will all be
4855 the default value). */
4857 /* Compare the max index vector to the vector of found indexes to find
4858 the position of the max value. */
4859 tree vec_compare
= make_ssa_name (index_vec_cmp_type
);
4860 gimple
*vec_compare_stmt
= gimple_build_assign (vec_compare
, EQ_EXPR
,
4863 gsi_insert_before (&exit_gsi
, vec_compare_stmt
, GSI_SAME_STMT
);
4865 /* Use the compare to choose either values from the data vector or
4867 tree vec_cond
= make_ssa_name (vectype
);
4868 gimple
*vec_cond_stmt
= gimple_build_assign (vec_cond
, VEC_COND_EXPR
,
4869 vec_compare
, new_phi_result
,
4871 gsi_insert_before (&exit_gsi
, vec_cond_stmt
, GSI_SAME_STMT
);
4873 /* Finally we need to extract the data value from the vector (VEC_COND)
4874 into a scalar (MATCHED_DATA_REDUC). Logically we want to do a OR
4875 reduction, but because this doesn't exist, we can use a MAX reduction
4876 instead. The data value might be signed or a float so we need to cast
4878 In the case where the loop never made any matches, the data values are
4879 all identical, and so will reduce down correctly. */
4881 /* Make the matched data values unsigned. */
4882 tree vec_cond_cast
= make_ssa_name (vectype_unsigned
);
4883 tree vec_cond_cast_rhs
= build1 (VIEW_CONVERT_EXPR
, vectype_unsigned
,
4885 gimple
*vec_cond_cast_stmt
= gimple_build_assign (vec_cond_cast
,
4888 gsi_insert_before (&exit_gsi
, vec_cond_cast_stmt
, GSI_SAME_STMT
);
4890 /* Reduce down to a scalar value. */
4891 tree data_reduc
= make_ssa_name (scalar_type_unsigned
);
4892 optab ot
= optab_for_tree_code (REDUC_MAX_EXPR
, vectype_unsigned
,
4894 gcc_assert (optab_handler (ot
, TYPE_MODE (vectype_unsigned
))
4895 != CODE_FOR_nothing
);
4896 gimple
*data_reduc_stmt
= gimple_build_assign (data_reduc
,
4899 gsi_insert_before (&exit_gsi
, data_reduc_stmt
, GSI_SAME_STMT
);
4901 /* Convert the reduced value back to the result type and set as the
4903 gimple_seq stmts
= NULL
;
4904 new_temp
= gimple_build (&stmts
, VIEW_CONVERT_EXPR
, scalar_type
,
4906 gsi_insert_seq_before (&exit_gsi
, stmts
, GSI_SAME_STMT
);
4907 scalar_results
.safe_push (new_temp
);
4909 else if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
4910 && reduc_code
== ERROR_MARK
)
4912 /* Condition redution without supported REDUC_MAX_EXPR. Generate
4914 idx_val = induction_index[0];
4915 val = data_reduc[0];
4916 for (idx = 0, val = init, i = 0; i < nelts; ++i)
4917 if (induction_index[i] > idx_val)
4918 val = data_reduc[i], idx_val = induction_index[i];
4921 tree data_eltype
= TREE_TYPE (TREE_TYPE (new_phi_result
));
4922 tree idx_eltype
= TREE_TYPE (TREE_TYPE (induction_index
));
4923 unsigned HOST_WIDE_INT el_size
= tree_to_uhwi (TYPE_SIZE (idx_eltype
));
4924 unsigned HOST_WIDE_INT v_size
4925 = el_size
* TYPE_VECTOR_SUBPARTS (TREE_TYPE (induction_index
));
4926 tree idx_val
= NULL_TREE
, val
= NULL_TREE
;
4927 for (unsigned HOST_WIDE_INT off
= 0; off
< v_size
; off
+= el_size
)
4929 tree old_idx_val
= idx_val
;
4931 idx_val
= make_ssa_name (idx_eltype
);
4932 epilog_stmt
= gimple_build_assign (idx_val
, BIT_FIELD_REF
,
4933 build3 (BIT_FIELD_REF
, idx_eltype
,
4935 bitsize_int (el_size
),
4936 bitsize_int (off
)));
4937 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4938 val
= make_ssa_name (data_eltype
);
4939 epilog_stmt
= gimple_build_assign (val
, BIT_FIELD_REF
,
4940 build3 (BIT_FIELD_REF
,
4943 bitsize_int (el_size
),
4944 bitsize_int (off
)));
4945 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4948 tree new_idx_val
= idx_val
;
4950 if (off
!= v_size
- el_size
)
4952 new_idx_val
= make_ssa_name (idx_eltype
);
4953 epilog_stmt
= gimple_build_assign (new_idx_val
,
4956 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4958 new_val
= make_ssa_name (data_eltype
);
4959 epilog_stmt
= gimple_build_assign (new_val
,
4966 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4967 idx_val
= new_idx_val
;
4971 /* Convert the reduced value back to the result type and set as the
4973 gimple_seq stmts
= NULL
;
4974 val
= gimple_convert (&stmts
, scalar_type
, val
);
4975 gsi_insert_seq_before (&exit_gsi
, stmts
, GSI_SAME_STMT
);
4976 scalar_results
.safe_push (val
);
4979 /* 2.3 Create the reduction code, using one of the three schemes described
4980 above. In SLP we simply need to extract all the elements from the
4981 vector (without reducing them), so we use scalar shifts. */
4982 else if (reduc_code
!= ERROR_MARK
&& !slp_reduc
)
4988 v_out2 = reduc_expr <v_out1> */
4990 if (dump_enabled_p ())
4991 dump_printf_loc (MSG_NOTE
, vect_location
,
4992 "Reduce using direct vector reduction.\n");
4994 vec_elem_type
= TREE_TYPE (TREE_TYPE (new_phi_result
));
4995 if (!useless_type_conversion_p (scalar_type
, vec_elem_type
))
4998 vect_create_destination_var (scalar_dest
, vec_elem_type
);
4999 tmp
= build1 (reduc_code
, vec_elem_type
, new_phi_result
);
5000 epilog_stmt
= gimple_build_assign (tmp_dest
, tmp
);
5001 new_temp
= make_ssa_name (tmp_dest
, epilog_stmt
);
5002 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
5003 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
5005 tmp
= build1 (NOP_EXPR
, scalar_type
, new_temp
);
5008 tmp
= build1 (reduc_code
, scalar_type
, new_phi_result
);
5010 epilog_stmt
= gimple_build_assign (new_scalar_dest
, tmp
);
5011 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
5012 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
5013 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
5015 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
5016 == INTEGER_INDUC_COND_REDUCTION
)
5018 /* Earlier we set the initial value to be zero. Check the result
5019 and if it is zero then replace with the original initial
5021 tree zero
= build_zero_cst (scalar_type
);
5022 tree zcompare
= build2 (EQ_EXPR
, boolean_type_node
, new_temp
, zero
);
5024 tmp
= make_ssa_name (new_scalar_dest
);
5025 epilog_stmt
= gimple_build_assign (tmp
, COND_EXPR
, zcompare
,
5026 initial_def
, new_temp
);
5027 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
5031 scalar_results
.safe_push (new_temp
);
5035 bool reduce_with_shift
= have_whole_vector_shift (mode
);
5036 int element_bitsize
= tree_to_uhwi (bitsize
);
5037 int vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
5040 /* COND reductions all do the final reduction with MAX_EXPR. */
5041 if (code
== COND_EXPR
)
5044 /* Regardless of whether we have a whole vector shift, if we're
5045 emulating the operation via tree-vect-generic, we don't want
5046 to use it. Only the first round of the reduction is likely
5047 to still be profitable via emulation. */
5048 /* ??? It might be better to emit a reduction tree code here, so that
5049 tree-vect-generic can expand the first round via bit tricks. */
5050 if (!VECTOR_MODE_P (mode
))
5051 reduce_with_shift
= false;
5054 optab optab
= optab_for_tree_code (code
, vectype
, optab_default
);
5055 if (optab_handler (optab
, mode
) == CODE_FOR_nothing
)
5056 reduce_with_shift
= false;
5059 if (reduce_with_shift
&& !slp_reduc
)
5061 int nelements
= vec_size_in_bits
/ element_bitsize
;
5062 unsigned char *sel
= XALLOCAVEC (unsigned char, nelements
);
5066 tree zero_vec
= build_zero_cst (vectype
);
5068 for (offset = nelements/2; offset >= 1; offset/=2)
5070 Create: va' = vec_shift <va, offset>
5071 Create: va = vop <va, va'>
5076 if (dump_enabled_p ())
5077 dump_printf_loc (MSG_NOTE
, vect_location
,
5078 "Reduce using vector shifts\n");
5080 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
5081 new_temp
= new_phi_result
;
5082 for (elt_offset
= nelements
/ 2;
5086 calc_vec_perm_mask_for_shift (mode
, elt_offset
, sel
);
5087 tree mask
= vect_gen_perm_mask_any (vectype
, sel
);
5088 epilog_stmt
= gimple_build_assign (vec_dest
, VEC_PERM_EXPR
,
5089 new_temp
, zero_vec
, mask
);
5090 new_name
= make_ssa_name (vec_dest
, epilog_stmt
);
5091 gimple_assign_set_lhs (epilog_stmt
, new_name
);
5092 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
5094 epilog_stmt
= gimple_build_assign (vec_dest
, code
, new_name
,
5096 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
5097 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
5098 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
5101 /* 2.4 Extract the final scalar result. Create:
5102 s_out3 = extract_field <v_out2, bitpos> */
5104 if (dump_enabled_p ())
5105 dump_printf_loc (MSG_NOTE
, vect_location
,
5106 "extract scalar result\n");
5108 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, new_temp
,
5109 bitsize
, bitsize_zero_node
);
5110 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
5111 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
5112 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
5113 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
5114 scalar_results
.safe_push (new_temp
);
5119 s = extract_field <v_out2, 0>
5120 for (offset = element_size;
5121 offset < vector_size;
5122 offset += element_size;)
5124 Create: s' = extract_field <v_out2, offset>
5125 Create: s = op <s, s'> // For non SLP cases
5128 if (dump_enabled_p ())
5129 dump_printf_loc (MSG_NOTE
, vect_location
,
5130 "Reduce using scalar code.\n");
5132 vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
5133 FOR_EACH_VEC_ELT (new_phis
, i
, new_phi
)
5136 if (gimple_code (new_phi
) == GIMPLE_PHI
)
5137 vec_temp
= PHI_RESULT (new_phi
);
5139 vec_temp
= gimple_assign_lhs (new_phi
);
5140 tree rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
, bitsize
,
5142 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
5143 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
5144 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
5145 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
5147 /* In SLP we don't need to apply reduction operation, so we just
5148 collect s' values in SCALAR_RESULTS. */
5150 scalar_results
.safe_push (new_temp
);
5152 for (bit_offset
= element_bitsize
;
5153 bit_offset
< vec_size_in_bits
;
5154 bit_offset
+= element_bitsize
)
5156 tree bitpos
= bitsize_int (bit_offset
);
5157 tree rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
,
5160 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
5161 new_name
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
5162 gimple_assign_set_lhs (epilog_stmt
, new_name
);
5163 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
5167 /* In SLP we don't need to apply reduction operation, so
5168 we just collect s' values in SCALAR_RESULTS. */
5169 new_temp
= new_name
;
5170 scalar_results
.safe_push (new_name
);
5174 epilog_stmt
= gimple_build_assign (new_scalar_dest
, code
,
5175 new_name
, new_temp
);
5176 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
5177 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
5178 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
5183 /* The only case where we need to reduce scalar results in SLP, is
5184 unrolling. If the size of SCALAR_RESULTS is greater than
5185 GROUP_SIZE, we reduce them combining elements modulo
5189 tree res
, first_res
, new_res
;
5192 /* Reduce multiple scalar results in case of SLP unrolling. */
5193 for (j
= group_size
; scalar_results
.iterate (j
, &res
);
5196 first_res
= scalar_results
[j
% group_size
];
5197 new_stmt
= gimple_build_assign (new_scalar_dest
, code
,
5199 new_res
= make_ssa_name (new_scalar_dest
, new_stmt
);
5200 gimple_assign_set_lhs (new_stmt
, new_res
);
5201 gsi_insert_before (&exit_gsi
, new_stmt
, GSI_SAME_STMT
);
5202 scalar_results
[j
% group_size
] = new_res
;
5206 /* Not SLP - we have one scalar to keep in SCALAR_RESULTS. */
5207 scalar_results
.safe_push (new_temp
);
5210 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
5211 == INTEGER_INDUC_COND_REDUCTION
)
5213 /* Earlier we set the initial value to be zero. Check the result
5214 and if it is zero then replace with the original initial
5216 tree zero
= build_zero_cst (scalar_type
);
5217 tree zcompare
= build2 (EQ_EXPR
, boolean_type_node
, new_temp
, zero
);
5219 tree tmp
= make_ssa_name (new_scalar_dest
);
5220 epilog_stmt
= gimple_build_assign (tmp
, COND_EXPR
, zcompare
,
5221 initial_def
, new_temp
);
5222 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
5223 scalar_results
[0] = tmp
;
5227 vect_finalize_reduction
:
5232 /* 2.5 Adjust the final result by the initial value of the reduction
5233 variable. (When such adjustment is not needed, then
5234 'adjustment_def' is zero). For example, if code is PLUS we create:
5235 new_temp = loop_exit_def + adjustment_def */
5239 gcc_assert (!slp_reduc
);
5240 if (nested_in_vect_loop
)
5242 new_phi
= new_phis
[0];
5243 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) == VECTOR_TYPE
);
5244 expr
= build2 (code
, vectype
, PHI_RESULT (new_phi
), adjustment_def
);
5245 new_dest
= vect_create_destination_var (scalar_dest
, vectype
);
5249 new_temp
= scalar_results
[0];
5250 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) != VECTOR_TYPE
);
5251 expr
= build2 (code
, scalar_type
, new_temp
, adjustment_def
);
5252 new_dest
= vect_create_destination_var (scalar_dest
, scalar_type
);
5255 epilog_stmt
= gimple_build_assign (new_dest
, expr
);
5256 new_temp
= make_ssa_name (new_dest
, epilog_stmt
);
5257 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
5258 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
5259 if (nested_in_vect_loop
)
5261 set_vinfo_for_stmt (epilog_stmt
,
5262 new_stmt_vec_info (epilog_stmt
, loop_vinfo
));
5263 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (epilog_stmt
)) =
5264 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_phi
));
5267 scalar_results
.quick_push (new_temp
);
5269 scalar_results
[0] = new_temp
;
5272 scalar_results
[0] = new_temp
;
5274 new_phis
[0] = epilog_stmt
;
5277 /* 2.6 Handle the loop-exit phis. Replace the uses of scalar loop-exit
5278 phis with new adjusted scalar results, i.e., replace use <s_out0>
5283 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
5284 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
5285 v_out2 = reduce <v_out1>
5286 s_out3 = extract_field <v_out2, 0>
5287 s_out4 = adjust_result <s_out3>
5294 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
5295 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
5296 v_out2 = reduce <v_out1>
5297 s_out3 = extract_field <v_out2, 0>
5298 s_out4 = adjust_result <s_out3>
5303 /* In SLP reduction chain we reduce vector results into one vector if
5304 necessary, hence we set here GROUP_SIZE to 1. SCALAR_DEST is the LHS of
5305 the last stmt in the reduction chain, since we are looking for the loop
5307 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
5309 gimple
*dest_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[group_size
- 1];
5310 /* Handle reduction patterns. */
5311 if (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (dest_stmt
)))
5312 dest_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (dest_stmt
));
5314 scalar_dest
= gimple_assign_lhs (dest_stmt
);
5318 /* In SLP we may have several statements in NEW_PHIS and REDUCTION_PHIS (in
5319 case that GROUP_SIZE is greater than vectorization factor). Therefore, we
5320 need to match SCALAR_RESULTS with corresponding statements. The first
5321 (GROUP_SIZE / number of new vector stmts) scalar results correspond to
5322 the first vector stmt, etc.
5323 (RATIO is equal to (GROUP_SIZE / number of new vector stmts)). */
5324 if (group_size
> new_phis
.length ())
5326 ratio
= group_size
/ new_phis
.length ();
5327 gcc_assert (!(group_size
% new_phis
.length ()));
5332 for (k
= 0; k
< group_size
; k
++)
5336 epilog_stmt
= new_phis
[k
/ ratio
];
5337 reduction_phi
= reduction_phis
[k
/ ratio
];
5339 inner_phi
= inner_phis
[k
/ ratio
];
5344 gimple
*current_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[k
];
5346 orig_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (current_stmt
));
5347 /* SLP statements can't participate in patterns. */
5348 gcc_assert (!orig_stmt
);
5349 scalar_dest
= gimple_assign_lhs (current_stmt
);
5353 /* Find the loop-closed-use at the loop exit of the original scalar
5354 result. (The reduction result is expected to have two immediate uses -
5355 one at the latch block, and one at the loop exit). */
5356 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
5357 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
)))
5358 && !is_gimple_debug (USE_STMT (use_p
)))
5359 phis
.safe_push (USE_STMT (use_p
));
5361 /* While we expect to have found an exit_phi because of loop-closed-ssa
5362 form we can end up without one if the scalar cycle is dead. */
5364 FOR_EACH_VEC_ELT (phis
, i
, exit_phi
)
5368 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
5371 /* FORNOW. Currently not supporting the case that an inner-loop
5372 reduction is not used in the outer-loop (but only outside the
5373 outer-loop), unless it is double reduction. */
5374 gcc_assert ((STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
5375 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
))
5379 STMT_VINFO_VEC_STMT (exit_phi_vinfo
) = inner_phi
;
5381 STMT_VINFO_VEC_STMT (exit_phi_vinfo
) = epilog_stmt
;
5383 || STMT_VINFO_DEF_TYPE (exit_phi_vinfo
)
5384 != vect_double_reduction_def
)
5387 /* Handle double reduction:
5389 stmt1: s1 = phi <s0, s2> - double reduction phi (outer loop)
5390 stmt2: s3 = phi <s1, s4> - (regular) reduc phi (inner loop)
5391 stmt3: s4 = use (s3) - (regular) reduc stmt (inner loop)
5392 stmt4: s2 = phi <s4> - double reduction stmt (outer loop)
5394 At that point the regular reduction (stmt2 and stmt3) is
5395 already vectorized, as well as the exit phi node, stmt4.
5396 Here we vectorize the phi node of double reduction, stmt1, and
5397 update all relevant statements. */
5399 /* Go through all the uses of s2 to find double reduction phi
5400 node, i.e., stmt1 above. */
5401 orig_name
= PHI_RESULT (exit_phi
);
5402 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
5404 stmt_vec_info use_stmt_vinfo
;
5405 stmt_vec_info new_phi_vinfo
;
5406 tree vect_phi_init
, preheader_arg
, vect_phi_res
, init_def
;
5407 basic_block bb
= gimple_bb (use_stmt
);
5410 /* Check that USE_STMT is really double reduction phi
5412 if (gimple_code (use_stmt
) != GIMPLE_PHI
5413 || gimple_phi_num_args (use_stmt
) != 2
5414 || bb
->loop_father
!= outer_loop
)
5416 use_stmt_vinfo
= vinfo_for_stmt (use_stmt
);
5418 || STMT_VINFO_DEF_TYPE (use_stmt_vinfo
)
5419 != vect_double_reduction_def
)
5422 /* Create vector phi node for double reduction:
5423 vs1 = phi <vs0, vs2>
5424 vs1 was created previously in this function by a call to
5425 vect_get_vec_def_for_operand and is stored in
5427 vs2 is defined by INNER_PHI, the vectorized EXIT_PHI;
5428 vs0 is created here. */
5430 /* Create vector phi node. */
5431 vect_phi
= create_phi_node (vec_initial_def
, bb
);
5432 new_phi_vinfo
= new_stmt_vec_info (vect_phi
,
5433 loop_vec_info_for_loop (outer_loop
));
5434 set_vinfo_for_stmt (vect_phi
, new_phi_vinfo
);
5436 /* Create vs0 - initial def of the double reduction phi. */
5437 preheader_arg
= PHI_ARG_DEF_FROM_EDGE (use_stmt
,
5438 loop_preheader_edge (outer_loop
));
5439 init_def
= get_initial_def_for_reduction (stmt
,
5440 preheader_arg
, NULL
);
5441 vect_phi_init
= vect_init_vector (use_stmt
, init_def
,
5444 /* Update phi node arguments with vs0 and vs2. */
5445 add_phi_arg (vect_phi
, vect_phi_init
,
5446 loop_preheader_edge (outer_loop
),
5448 add_phi_arg (vect_phi
, PHI_RESULT (inner_phi
),
5449 loop_latch_edge (outer_loop
), UNKNOWN_LOCATION
);
5450 if (dump_enabled_p ())
5452 dump_printf_loc (MSG_NOTE
, vect_location
,
5453 "created double reduction phi node: ");
5454 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, vect_phi
, 0);
5457 vect_phi_res
= PHI_RESULT (vect_phi
);
5459 /* Replace the use, i.e., set the correct vs1 in the regular
5460 reduction phi node. FORNOW, NCOPIES is always 1, so the
5461 loop is redundant. */
5462 use
= reduction_phi
;
5463 for (j
= 0; j
< ncopies
; j
++)
5465 edge pr_edge
= loop_preheader_edge (loop
);
5466 SET_PHI_ARG_DEF (use
, pr_edge
->dest_idx
, vect_phi_res
);
5467 use
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use
));
5474 if (nested_in_vect_loop
)
5483 /* Find the loop-closed-use at the loop exit of the original scalar
5484 result. (The reduction result is expected to have two immediate uses,
5485 one at the latch block, and one at the loop exit). For double
5486 reductions we are looking for exit phis of the outer loop. */
5487 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
5489 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
5491 if (!is_gimple_debug (USE_STMT (use_p
)))
5492 phis
.safe_push (USE_STMT (use_p
));
5496 if (double_reduc
&& gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
5498 tree phi_res
= PHI_RESULT (USE_STMT (use_p
));
5500 FOR_EACH_IMM_USE_FAST (phi_use_p
, phi_imm_iter
, phi_res
)
5502 if (!flow_bb_inside_loop_p (loop
,
5503 gimple_bb (USE_STMT (phi_use_p
)))
5504 && !is_gimple_debug (USE_STMT (phi_use_p
)))
5505 phis
.safe_push (USE_STMT (phi_use_p
));
5511 FOR_EACH_VEC_ELT (phis
, i
, exit_phi
)
5513 /* Replace the uses: */
5514 orig_name
= PHI_RESULT (exit_phi
);
5515 scalar_result
= scalar_results
[k
];
5516 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
5517 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
5518 SET_USE (use_p
, scalar_result
);
5526 /* Function is_nonwrapping_integer_induction.
5528 Check if STMT (which is part of loop LOOP) both increments and
5529 does not cause overflow. */
5532 is_nonwrapping_integer_induction (gimple
*stmt
, struct loop
*loop
)
5534 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
5535 tree base
= STMT_VINFO_LOOP_PHI_EVOLUTION_BASE_UNCHANGED (stmt_vinfo
);
5536 tree step
= STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
);
5537 tree lhs_type
= TREE_TYPE (gimple_phi_result (stmt
));
5538 widest_int ni
, max_loop_value
, lhs_max
;
5539 bool overflow
= false;
5541 /* Make sure the loop is integer based. */
5542 if (TREE_CODE (base
) != INTEGER_CST
5543 || TREE_CODE (step
) != INTEGER_CST
)
5546 /* Check that the induction increments. */
5547 if (tree_int_cst_sgn (step
) == -1)
5550 /* Check that the max size of the loop will not wrap. */
5552 if (TYPE_OVERFLOW_UNDEFINED (lhs_type
))
5555 if (! max_stmt_executions (loop
, &ni
))
5558 max_loop_value
= wi::mul (wi::to_widest (step
), ni
, TYPE_SIGN (lhs_type
),
5563 max_loop_value
= wi::add (wi::to_widest (base
), max_loop_value
,
5564 TYPE_SIGN (lhs_type
), &overflow
);
5568 return (wi::min_precision (max_loop_value
, TYPE_SIGN (lhs_type
))
5569 <= TYPE_PRECISION (lhs_type
));
5572 /* Function vectorizable_reduction.
5574 Check if STMT performs a reduction operation that can be vectorized.
5575 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
5576 stmt to replace it, put it in VEC_STMT, and insert it at GSI.
5577 Return FALSE if not a vectorizable STMT, TRUE otherwise.
5579 This function also handles reduction idioms (patterns) that have been
5580 recognized in advance during vect_pattern_recog. In this case, STMT may be
5582 X = pattern_expr (arg0, arg1, ..., X)
5583 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
5584 sequence that had been detected and replaced by the pattern-stmt (STMT).
5586 This function also handles reduction of condition expressions, for example:
5587 for (int i = 0; i < N; i++)
5590 This is handled by vectorising the loop and creating an additional vector
5591 containing the loop indexes for which "a[i] < value" was true. In the
5592 function epilogue this is reduced to a single max value and then used to
5593 index into the vector of results.
5595 In some cases of reduction patterns, the type of the reduction variable X is
5596 different than the type of the other arguments of STMT.
5597 In such cases, the vectype that is used when transforming STMT into a vector
5598 stmt is different than the vectype that is used to determine the
5599 vectorization factor, because it consists of a different number of elements
5600 than the actual number of elements that are being operated upon in parallel.
5602 For example, consider an accumulation of shorts into an int accumulator.
5603 On some targets it's possible to vectorize this pattern operating on 8
5604 shorts at a time (hence, the vectype for purposes of determining the
5605 vectorization factor should be V8HI); on the other hand, the vectype that
5606 is used to create the vector form is actually V4SI (the type of the result).
5608 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
5609 indicates what is the actual level of parallelism (V8HI in the example), so
5610 that the right vectorization factor would be derived. This vectype
5611 corresponds to the type of arguments to the reduction stmt, and should *NOT*
5612 be used to create the vectorized stmt. The right vectype for the vectorized
5613 stmt is obtained from the type of the result X:
5614 get_vectype_for_scalar_type (TREE_TYPE (X))
5616 This means that, contrary to "regular" reductions (or "regular" stmts in
5617 general), the following equation:
5618 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
5619 does *NOT* necessarily hold for reduction patterns. */
5622 vectorizable_reduction (gimple
*stmt
, gimple_stmt_iterator
*gsi
,
5623 gimple
**vec_stmt
, slp_tree slp_node
,
5624 slp_instance slp_node_instance
)
5628 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
5629 tree vectype_out
= STMT_VINFO_VECTYPE (stmt_info
);
5630 tree vectype_in
= NULL_TREE
;
5631 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
5632 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5633 enum tree_code code
, orig_code
, epilog_reduc_code
;
5634 machine_mode vec_mode
;
5636 optab optab
, reduc_optab
;
5637 tree new_temp
= NULL_TREE
;
5639 enum vect_def_type dt
, cond_reduc_dt
= vect_unknown_def_type
;
5643 stmt_vec_info orig_stmt_info
= NULL
;
5647 stmt_vec_info prev_stmt_info
, prev_phi_info
;
5648 bool single_defuse_cycle
= false;
5649 gimple
*new_stmt
= NULL
;
5652 enum vect_def_type dts
[3];
5653 bool nested_cycle
= false, found_nested_cycle_def
= false;
5654 bool double_reduc
= false;
5656 struct loop
* def_stmt_loop
, *outer_loop
= NULL
;
5658 gimple
*def_arg_stmt
;
5659 auto_vec
<tree
> vec_oprnds0
;
5660 auto_vec
<tree
> vec_oprnds1
;
5661 auto_vec
<tree
> vec_oprnds2
;
5662 auto_vec
<tree
> vect_defs
;
5663 auto_vec
<gimple
*> phis
;
5666 bool first_p
= true;
5667 tree cr_index_scalar_type
= NULL_TREE
, cr_index_vector_type
= NULL_TREE
;
5668 tree cond_reduc_val
= NULL_TREE
;
5670 /* Make sure it was already recognized as a reduction computation. */
5671 if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) != vect_reduction_def
5672 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) != vect_nested_cycle
)
5675 if (nested_in_vect_loop_p (loop
, stmt
))
5679 nested_cycle
= true;
5682 /* In case of reduction chain we switch to the first stmt in the chain, but
5683 we don't update STMT_INFO, since only the last stmt is marked as reduction
5684 and has reduction properties. */
5685 if (GROUP_FIRST_ELEMENT (stmt_info
)
5686 && GROUP_FIRST_ELEMENT (stmt_info
) != stmt
)
5688 stmt
= GROUP_FIRST_ELEMENT (stmt_info
);
5692 if (gimple_code (stmt
) == GIMPLE_PHI
)
5694 /* Analysis is fully done on the reduction stmt invocation. */
5698 slp_node_instance
->reduc_phis
= slp_node
;
5700 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
5704 gimple
*reduc_stmt
= STMT_VINFO_REDUC_DEF (stmt_info
);
5705 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (reduc_stmt
)))
5706 reduc_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (reduc_stmt
));
5708 gcc_assert (is_gimple_assign (reduc_stmt
));
5709 for (unsigned k
= 1; k
< gimple_num_ops (reduc_stmt
); ++k
)
5711 tree op
= gimple_op (reduc_stmt
, k
);
5712 if (op
== gimple_phi_result (stmt
))
5715 && gimple_assign_rhs_code (reduc_stmt
) == COND_EXPR
)
5717 tem
= get_vectype_for_scalar_type (TREE_TYPE (op
));
5719 || TYPE_VECTOR_SUBPARTS (tem
) < TYPE_VECTOR_SUBPARTS (vectype_in
))
5723 gcc_assert (vectype_in
);
5728 ncopies
= (LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
5729 / TYPE_VECTOR_SUBPARTS (vectype_in
));
5731 use_operand_p use_p
;
5734 && (STMT_VINFO_RELEVANT (vinfo_for_stmt (reduc_stmt
))
5735 <= vect_used_only_live
)
5736 && single_imm_use (gimple_phi_result (stmt
), &use_p
, &use_stmt
)
5737 && (use_stmt
== reduc_stmt
5738 || (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use_stmt
))
5740 single_defuse_cycle
= true;
5742 /* Create the destination vector */
5743 scalar_dest
= gimple_assign_lhs (reduc_stmt
);
5744 vec_dest
= vect_create_destination_var (scalar_dest
, vectype_out
);
5747 /* The size vect_schedule_slp_instance computes is off for us. */
5748 vec_num
= ((LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
5749 * SLP_TREE_SCALAR_STMTS (slp_node
).length ())
5750 / TYPE_VECTOR_SUBPARTS (vectype_in
));
5754 /* Generate the reduction PHIs upfront. */
5755 prev_phi_info
= NULL
;
5756 for (j
= 0; j
< ncopies
; j
++)
5758 if (j
== 0 || !single_defuse_cycle
)
5760 for (i
= 0; i
< vec_num
; i
++)
5762 /* Create the reduction-phi that defines the reduction
5764 gimple
*new_phi
= create_phi_node (vec_dest
, loop
->header
);
5765 set_vinfo_for_stmt (new_phi
,
5766 new_stmt_vec_info (new_phi
, loop_vinfo
));
5769 SLP_TREE_VEC_STMTS (slp_node
).quick_push (new_phi
);
5773 STMT_VINFO_VEC_STMT (stmt_info
) = *vec_stmt
= new_phi
;
5775 STMT_VINFO_RELATED_STMT (prev_phi_info
) = new_phi
;
5776 prev_phi_info
= vinfo_for_stmt (new_phi
);
5785 /* 1. Is vectorizable reduction? */
5786 /* Not supportable if the reduction variable is used in the loop, unless
5787 it's a reduction chain. */
5788 if (STMT_VINFO_RELEVANT (stmt_info
) > vect_used_in_outer
5789 && !GROUP_FIRST_ELEMENT (stmt_info
))
5792 /* Reductions that are not used even in an enclosing outer-loop,
5793 are expected to be "live" (used out of the loop). */
5794 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
5795 && !STMT_VINFO_LIVE_P (stmt_info
))
5798 /* 2. Has this been recognized as a reduction pattern?
5800 Check if STMT represents a pattern that has been recognized
5801 in earlier analysis stages. For stmts that represent a pattern,
5802 the STMT_VINFO_RELATED_STMT field records the last stmt in
5803 the original sequence that constitutes the pattern. */
5805 orig_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt
));
5808 orig_stmt_info
= vinfo_for_stmt (orig_stmt
);
5809 gcc_assert (STMT_VINFO_IN_PATTERN_P (orig_stmt_info
));
5810 gcc_assert (!STMT_VINFO_IN_PATTERN_P (stmt_info
));
5813 /* 3. Check the operands of the operation. The first operands are defined
5814 inside the loop body. The last operand is the reduction variable,
5815 which is defined by the loop-header-phi. */
5817 gcc_assert (is_gimple_assign (stmt
));
5820 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
5822 case GIMPLE_BINARY_RHS
:
5823 code
= gimple_assign_rhs_code (stmt
);
5824 op_type
= TREE_CODE_LENGTH (code
);
5825 gcc_assert (op_type
== binary_op
);
5826 ops
[0] = gimple_assign_rhs1 (stmt
);
5827 ops
[1] = gimple_assign_rhs2 (stmt
);
5830 case GIMPLE_TERNARY_RHS
:
5831 code
= gimple_assign_rhs_code (stmt
);
5832 op_type
= TREE_CODE_LENGTH (code
);
5833 gcc_assert (op_type
== ternary_op
);
5834 ops
[0] = gimple_assign_rhs1 (stmt
);
5835 ops
[1] = gimple_assign_rhs2 (stmt
);
5836 ops
[2] = gimple_assign_rhs3 (stmt
);
5839 case GIMPLE_UNARY_RHS
:
5846 if (code
== COND_EXPR
&& slp_node
)
5849 scalar_dest
= gimple_assign_lhs (stmt
);
5850 scalar_type
= TREE_TYPE (scalar_dest
);
5851 if (!POINTER_TYPE_P (scalar_type
) && !INTEGRAL_TYPE_P (scalar_type
)
5852 && !SCALAR_FLOAT_TYPE_P (scalar_type
))
5855 /* Do not try to vectorize bit-precision reductions. */
5856 if (!type_has_mode_precision_p (scalar_type
))
5859 /* All uses but the last are expected to be defined in the loop.
5860 The last use is the reduction variable. In case of nested cycle this
5861 assumption is not true: we use reduc_index to record the index of the
5862 reduction variable. */
5863 gimple
*reduc_def_stmt
= NULL
;
5864 int reduc_index
= -1;
5865 for (i
= 0; i
< op_type
; i
++)
5867 /* The condition of COND_EXPR is checked in vectorizable_condition(). */
5868 if (i
== 0 && code
== COND_EXPR
)
5871 is_simple_use
= vect_is_simple_use (ops
[i
], loop_vinfo
,
5872 &def_stmt
, &dts
[i
], &tem
);
5874 gcc_assert (is_simple_use
);
5875 if (dt
== vect_reduction_def
)
5877 reduc_def_stmt
= def_stmt
;
5887 if (dt
!= vect_internal_def
5888 && dt
!= vect_external_def
5889 && dt
!= vect_constant_def
5890 && dt
!= vect_induction_def
5891 && !(dt
== vect_nested_cycle
&& nested_cycle
))
5894 if (dt
== vect_nested_cycle
)
5896 found_nested_cycle_def
= true;
5897 reduc_def_stmt
= def_stmt
;
5901 if (i
== 1 && code
== COND_EXPR
)
5903 /* Record how value of COND_EXPR is defined. */
5904 if (dt
== vect_constant_def
)
5907 cond_reduc_val
= ops
[i
];
5909 if (dt
== vect_induction_def
&& def_stmt
!= NULL
5910 && is_nonwrapping_integer_induction (def_stmt
, loop
))
5916 vectype_in
= vectype_out
;
5918 /* When vectorizing a reduction chain w/o SLP the reduction PHI is not
5919 directy used in stmt. */
5920 if (reduc_index
== -1)
5923 reduc_def_stmt
= STMT_VINFO_REDUC_DEF (orig_stmt_info
);
5925 reduc_def_stmt
= STMT_VINFO_REDUC_DEF (stmt_info
);
5928 if (! reduc_def_stmt
|| gimple_code (reduc_def_stmt
) != GIMPLE_PHI
)
5931 if (!(reduc_index
== -1
5932 || dts
[reduc_index
] == vect_reduction_def
5933 || dts
[reduc_index
] == vect_nested_cycle
5934 || ((dts
[reduc_index
] == vect_internal_def
5935 || dts
[reduc_index
] == vect_external_def
5936 || dts
[reduc_index
] == vect_constant_def
5937 || dts
[reduc_index
] == vect_induction_def
)
5938 && nested_cycle
&& found_nested_cycle_def
)))
5940 /* For pattern recognized stmts, orig_stmt might be a reduction,
5941 but some helper statements for the pattern might not, or
5942 might be COND_EXPRs with reduction uses in the condition. */
5943 gcc_assert (orig_stmt
);
5947 stmt_vec_info reduc_def_info
= vinfo_for_stmt (reduc_def_stmt
);
5948 enum vect_reduction_type v_reduc_type
5949 = STMT_VINFO_REDUC_TYPE (reduc_def_info
);
5950 gimple
*tmp
= STMT_VINFO_REDUC_DEF (reduc_def_info
);
5952 STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) = v_reduc_type
;
5953 /* If we have a condition reduction, see if we can simplify it further. */
5954 if (v_reduc_type
== COND_REDUCTION
)
5956 if (cond_reduc_dt
== vect_induction_def
)
5958 if (dump_enabled_p ())
5959 dump_printf_loc (MSG_NOTE
, vect_location
,
5960 "condition expression based on "
5961 "integer induction.\n");
5962 STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
5963 = INTEGER_INDUC_COND_REDUCTION
;
5966 /* Loop peeling modifies initial value of reduction PHI, which
5967 makes the reduction stmt to be transformed different to the
5968 original stmt analyzed. We need to record reduction code for
5969 CONST_COND_REDUCTION type reduction at analyzing stage, thus
5970 it can be used directly at transform stage. */
5971 if (STMT_VINFO_VEC_CONST_COND_REDUC_CODE (stmt_info
) == MAX_EXPR
5972 || STMT_VINFO_VEC_CONST_COND_REDUC_CODE (stmt_info
) == MIN_EXPR
)
5974 /* Also set the reduction type to CONST_COND_REDUCTION. */
5975 gcc_assert (cond_reduc_dt
== vect_constant_def
);
5976 STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) = CONST_COND_REDUCTION
;
5978 else if (cond_reduc_dt
== vect_constant_def
)
5980 enum vect_def_type cond_initial_dt
;
5981 gimple
*def_stmt
= SSA_NAME_DEF_STMT (ops
[reduc_index
]);
5982 tree cond_initial_val
5983 = PHI_ARG_DEF_FROM_EDGE (def_stmt
, loop_preheader_edge (loop
));
5985 gcc_assert (cond_reduc_val
!= NULL_TREE
);
5986 vect_is_simple_use (cond_initial_val
, loop_vinfo
,
5987 &def_stmt
, &cond_initial_dt
);
5988 if (cond_initial_dt
== vect_constant_def
5989 && types_compatible_p (TREE_TYPE (cond_initial_val
),
5990 TREE_TYPE (cond_reduc_val
)))
5992 tree e
= fold_binary (LE_EXPR
, boolean_type_node
,
5993 cond_initial_val
, cond_reduc_val
);
5994 if (e
&& (integer_onep (e
) || integer_zerop (e
)))
5996 if (dump_enabled_p ())
5997 dump_printf_loc (MSG_NOTE
, vect_location
,
5998 "condition expression based on "
5999 "compile time constant.\n");
6000 /* Record reduction code at analysis stage. */
6001 STMT_VINFO_VEC_CONST_COND_REDUC_CODE (stmt_info
)
6002 = integer_onep (e
) ? MAX_EXPR
: MIN_EXPR
;
6003 STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
6004 = CONST_COND_REDUCTION
;
6011 gcc_assert (tmp
== orig_stmt
6012 || GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp
)) == orig_stmt
);
6014 /* We changed STMT to be the first stmt in reduction chain, hence we
6015 check that in this case the first element in the chain is STMT. */
6016 gcc_assert (stmt
== tmp
6017 || GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp
)) == stmt
);
6019 if (STMT_VINFO_LIVE_P (vinfo_for_stmt (reduc_def_stmt
)))
6025 ncopies
= (LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
6026 / TYPE_VECTOR_SUBPARTS (vectype_in
));
6028 gcc_assert (ncopies
>= 1);
6030 vec_mode
= TYPE_MODE (vectype_in
);
6032 if (code
== COND_EXPR
)
6034 /* Only call during the analysis stage, otherwise we'll lose
6036 if (!vec_stmt
&& !vectorizable_condition (stmt
, gsi
, NULL
,
6037 ops
[reduc_index
], 0, NULL
))
6039 if (dump_enabled_p ())
6040 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6041 "unsupported condition in reduction\n");
6047 /* 4. Supportable by target? */
6049 if (code
== LSHIFT_EXPR
|| code
== RSHIFT_EXPR
6050 || code
== LROTATE_EXPR
|| code
== RROTATE_EXPR
)
6052 /* Shifts and rotates are only supported by vectorizable_shifts,
6053 not vectorizable_reduction. */
6054 if (dump_enabled_p ())
6055 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6056 "unsupported shift or rotation.\n");
6060 /* 4.1. check support for the operation in the loop */
6061 optab
= optab_for_tree_code (code
, vectype_in
, optab_default
);
6064 if (dump_enabled_p ())
6065 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6071 if (optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
6073 if (dump_enabled_p ())
6074 dump_printf (MSG_NOTE
, "op not supported by target.\n");
6076 if (GET_MODE_SIZE (vec_mode
) != UNITS_PER_WORD
6077 || LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
6078 < vect_min_worthwhile_factor (code
))
6081 if (dump_enabled_p ())
6082 dump_printf (MSG_NOTE
, "proceeding using word mode.\n");
6085 /* Worthwhile without SIMD support? */
6086 if (!VECTOR_MODE_P (TYPE_MODE (vectype_in
))
6087 && LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
6088 < vect_min_worthwhile_factor (code
))
6090 if (dump_enabled_p ())
6091 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6092 "not worthwhile without SIMD support.\n");
6098 /* 4.2. Check support for the epilog operation.
6100 If STMT represents a reduction pattern, then the type of the
6101 reduction variable may be different than the type of the rest
6102 of the arguments. For example, consider the case of accumulation
6103 of shorts into an int accumulator; The original code:
6104 S1: int_a = (int) short_a;
6105 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
6108 STMT: int_acc = widen_sum <short_a, int_acc>
6111 1. The tree-code that is used to create the vector operation in the
6112 epilog code (that reduces the partial results) is not the
6113 tree-code of STMT, but is rather the tree-code of the original
6114 stmt from the pattern that STMT is replacing. I.e, in the example
6115 above we want to use 'widen_sum' in the loop, but 'plus' in the
6117 2. The type (mode) we use to check available target support
6118 for the vector operation to be created in the *epilog*, is
6119 determined by the type of the reduction variable (in the example
6120 above we'd check this: optab_handler (plus_optab, vect_int_mode])).
6121 However the type (mode) we use to check available target support
6122 for the vector operation to be created *inside the loop*, is
6123 determined by the type of the other arguments to STMT (in the
6124 example we'd check this: optab_handler (widen_sum_optab,
6127 This is contrary to "regular" reductions, in which the types of all
6128 the arguments are the same as the type of the reduction variable.
6129 For "regular" reductions we can therefore use the same vector type
6130 (and also the same tree-code) when generating the epilog code and
6131 when generating the code inside the loop. */
6135 /* This is a reduction pattern: get the vectype from the type of the
6136 reduction variable, and get the tree-code from orig_stmt. */
6137 gcc_assert (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
6138 == TREE_CODE_REDUCTION
);
6139 orig_code
= gimple_assign_rhs_code (orig_stmt
);
6140 gcc_assert (vectype_out
);
6141 vec_mode
= TYPE_MODE (vectype_out
);
6145 /* Regular reduction: use the same vectype and tree-code as used for
6146 the vector code inside the loop can be used for the epilog code. */
6149 if (code
== MINUS_EXPR
)
6150 orig_code
= PLUS_EXPR
;
6152 /* For simple condition reductions, replace with the actual expression
6153 we want to base our reduction around. */
6154 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == CONST_COND_REDUCTION
)
6156 orig_code
= STMT_VINFO_VEC_CONST_COND_REDUC_CODE (stmt_info
);
6157 gcc_assert (orig_code
== MAX_EXPR
|| orig_code
== MIN_EXPR
);
6159 else if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
6160 == INTEGER_INDUC_COND_REDUCTION
)
6161 orig_code
= MAX_EXPR
;
6166 def_bb
= gimple_bb (reduc_def_stmt
);
6167 def_stmt_loop
= def_bb
->loop_father
;
6168 def_arg
= PHI_ARG_DEF_FROM_EDGE (reduc_def_stmt
,
6169 loop_preheader_edge (def_stmt_loop
));
6170 if (TREE_CODE (def_arg
) == SSA_NAME
6171 && (def_arg_stmt
= SSA_NAME_DEF_STMT (def_arg
))
6172 && gimple_code (def_arg_stmt
) == GIMPLE_PHI
6173 && flow_bb_inside_loop_p (outer_loop
, gimple_bb (def_arg_stmt
))
6174 && vinfo_for_stmt (def_arg_stmt
)
6175 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_arg_stmt
))
6176 == vect_double_reduction_def
)
6177 double_reduc
= true;
6180 epilog_reduc_code
= ERROR_MARK
;
6182 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) != COND_REDUCTION
)
6184 if (reduction_code_for_scalar_code (orig_code
, &epilog_reduc_code
))
6186 reduc_optab
= optab_for_tree_code (epilog_reduc_code
, vectype_out
,
6190 if (dump_enabled_p ())
6191 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6192 "no optab for reduction.\n");
6194 epilog_reduc_code
= ERROR_MARK
;
6196 else if (optab_handler (reduc_optab
, vec_mode
) == CODE_FOR_nothing
)
6198 if (dump_enabled_p ())
6199 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6200 "reduc op not supported by target.\n");
6202 epilog_reduc_code
= ERROR_MARK
;
6207 if (!nested_cycle
|| double_reduc
)
6209 if (dump_enabled_p ())
6210 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6211 "no reduc code for scalar code.\n");
6219 int scalar_precision
6220 = GET_MODE_PRECISION (SCALAR_TYPE_MODE (scalar_type
));
6221 cr_index_scalar_type
= make_unsigned_type (scalar_precision
);
6222 cr_index_vector_type
= build_vector_type
6223 (cr_index_scalar_type
, TYPE_VECTOR_SUBPARTS (vectype_out
));
6225 optab
= optab_for_tree_code (REDUC_MAX_EXPR
, cr_index_vector_type
,
6227 if (optab_handler (optab
, TYPE_MODE (cr_index_vector_type
))
6228 != CODE_FOR_nothing
)
6229 epilog_reduc_code
= REDUC_MAX_EXPR
;
6233 || STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) != TREE_CODE_REDUCTION
)
6236 if (dump_enabled_p ())
6237 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6238 "multiple types in double reduction or condition "
6243 /* In case of widenning multiplication by a constant, we update the type
6244 of the constant to be the type of the other operand. We check that the
6245 constant fits the type in the pattern recognition pass. */
6246 if (code
== DOT_PROD_EXPR
6247 && !types_compatible_p (TREE_TYPE (ops
[0]), TREE_TYPE (ops
[1])))
6249 if (TREE_CODE (ops
[0]) == INTEGER_CST
)
6250 ops
[0] = fold_convert (TREE_TYPE (ops
[1]), ops
[0]);
6251 else if (TREE_CODE (ops
[1]) == INTEGER_CST
)
6252 ops
[1] = fold_convert (TREE_TYPE (ops
[0]), ops
[1]);
6255 if (dump_enabled_p ())
6256 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6257 "invalid types in dot-prod\n");
6263 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
)
6267 if (! max_loop_iterations (loop
, &ni
))
6269 if (dump_enabled_p ())
6270 dump_printf_loc (MSG_NOTE
, vect_location
,
6271 "loop count not known, cannot create cond "
6275 /* Convert backedges to iterations. */
6278 /* The additional index will be the same type as the condition. Check
6279 that the loop can fit into this less one (because we'll use up the
6280 zero slot for when there are no matches). */
6281 tree max_index
= TYPE_MAX_VALUE (cr_index_scalar_type
);
6282 if (wi::geu_p (ni
, wi::to_widest (max_index
)))
6284 if (dump_enabled_p ())
6285 dump_printf_loc (MSG_NOTE
, vect_location
,
6286 "loop size is greater than data size.\n");
6291 /* In case the vectorization factor (VF) is bigger than the number
6292 of elements that we can fit in a vectype (nunits), we have to generate
6293 more than one vector stmt - i.e - we need to "unroll" the
6294 vector stmt by a factor VF/nunits. For more details see documentation
6295 in vectorizable_operation. */
6297 /* If the reduction is used in an outer loop we need to generate
6298 VF intermediate results, like so (e.g. for ncopies=2):
6303 (i.e. we generate VF results in 2 registers).
6304 In this case we have a separate def-use cycle for each copy, and therefore
6305 for each copy we get the vector def for the reduction variable from the
6306 respective phi node created for this copy.
6308 Otherwise (the reduction is unused in the loop nest), we can combine
6309 together intermediate results, like so (e.g. for ncopies=2):
6313 (i.e. we generate VF/2 results in a single register).
6314 In this case for each copy we get the vector def for the reduction variable
6315 from the vectorized reduction operation generated in the previous iteration.
6317 This only works when we see both the reduction PHI and its only consumer
6318 in vectorizable_reduction and there are no intermediate stmts
6320 use_operand_p use_p
;
6323 && (STMT_VINFO_RELEVANT (stmt_info
) <= vect_used_only_live
)
6324 && single_imm_use (gimple_phi_result (reduc_def_stmt
), &use_p
, &use_stmt
)
6325 && (use_stmt
== stmt
6326 || STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use_stmt
)) == stmt
))
6328 single_defuse_cycle
= true;
6332 epilog_copies
= ncopies
;
6334 /* If the reduction stmt is one of the patterns that have lane
6335 reduction embedded we cannot handle the case of ! single_defuse_cycle. */
6337 && ! single_defuse_cycle
)
6338 && (code
== DOT_PROD_EXPR
6339 || code
== WIDEN_SUM_EXPR
6340 || code
== SAD_EXPR
))
6342 if (dump_enabled_p ())
6343 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6344 "multi def-use cycle not possible for lane-reducing "
6345 "reduction operation\n");
6349 if (!vec_stmt
) /* transformation not required. */
6352 vect_model_reduction_cost (stmt_info
, epilog_reduc_code
, ncopies
);
6353 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
6359 if (dump_enabled_p ())
6360 dump_printf_loc (MSG_NOTE
, vect_location
, "transform reduction.\n");
6362 /* FORNOW: Multiple types are not supported for condition. */
6363 if (code
== COND_EXPR
)
6364 gcc_assert (ncopies
== 1);
6366 /* Create the destination vector */
6367 vec_dest
= vect_create_destination_var (scalar_dest
, vectype_out
);
6369 prev_stmt_info
= NULL
;
6370 prev_phi_info
= NULL
;
6372 vec_num
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
6376 vec_oprnds0
.create (1);
6377 vec_oprnds1
.create (1);
6378 if (op_type
== ternary_op
)
6379 vec_oprnds2
.create (1);
6382 phis
.create (vec_num
);
6383 vect_defs
.create (vec_num
);
6385 vect_defs
.quick_push (NULL_TREE
);
6388 phis
.splice (SLP_TREE_VEC_STMTS (slp_node_instance
->reduc_phis
));
6390 phis
.quick_push (STMT_VINFO_VEC_STMT (vinfo_for_stmt (reduc_def_stmt
)));
6392 for (j
= 0; j
< ncopies
; j
++)
6394 if (code
== COND_EXPR
)
6396 gcc_assert (!slp_node
);
6397 vectorizable_condition (stmt
, gsi
, vec_stmt
,
6398 PHI_RESULT (phis
[0]),
6400 /* Multiple types are not supported for condition. */
6409 /* Get vec defs for all the operands except the reduction index,
6410 ensuring the ordering of the ops in the vector is kept. */
6411 auto_vec
<tree
, 3> slp_ops
;
6412 auto_vec
<vec
<tree
>, 3> vec_defs
;
6414 slp_ops
.quick_push (ops
[0]);
6415 slp_ops
.quick_push (ops
[1]);
6416 if (op_type
== ternary_op
)
6417 slp_ops
.quick_push (ops
[2]);
6419 vect_get_slp_defs (slp_ops
, slp_node
, &vec_defs
);
6421 vec_oprnds0
.safe_splice (vec_defs
[0]);
6422 vec_defs
[0].release ();
6423 vec_oprnds1
.safe_splice (vec_defs
[1]);
6424 vec_defs
[1].release ();
6425 if (op_type
== ternary_op
)
6427 vec_oprnds2
.safe_splice (vec_defs
[2]);
6428 vec_defs
[2].release ();
6433 vec_oprnds0
.quick_push
6434 (vect_get_vec_def_for_operand (ops
[0], stmt
));
6435 vec_oprnds1
.quick_push
6436 (vect_get_vec_def_for_operand (ops
[1], stmt
));
6437 if (op_type
== ternary_op
)
6438 vec_oprnds2
.quick_push
6439 (vect_get_vec_def_for_operand (ops
[2], stmt
));
6446 gcc_assert (reduc_index
!= -1 || ! single_defuse_cycle
);
6448 if (single_defuse_cycle
&& reduc_index
== 0)
6449 vec_oprnds0
[0] = gimple_assign_lhs (new_stmt
);
6452 = vect_get_vec_def_for_stmt_copy (dts
[0], vec_oprnds0
[0]);
6453 if (single_defuse_cycle
&& reduc_index
== 1)
6454 vec_oprnds1
[0] = gimple_assign_lhs (new_stmt
);
6457 = vect_get_vec_def_for_stmt_copy (dts
[1], vec_oprnds1
[0]);
6458 if (op_type
== ternary_op
)
6460 if (single_defuse_cycle
&& reduc_index
== 2)
6461 vec_oprnds2
[0] = gimple_assign_lhs (new_stmt
);
6464 = vect_get_vec_def_for_stmt_copy (dts
[2], vec_oprnds2
[0]);
6469 FOR_EACH_VEC_ELT (vec_oprnds0
, i
, def0
)
6471 tree vop
[3] = { def0
, vec_oprnds1
[i
], NULL_TREE
};
6472 if (op_type
== ternary_op
)
6473 vop
[2] = vec_oprnds2
[i
];
6475 new_temp
= make_ssa_name (vec_dest
, new_stmt
);
6476 new_stmt
= gimple_build_assign (new_temp
, code
,
6477 vop
[0], vop
[1], vop
[2]);
6478 vect_finish_stmt_generation (stmt
, new_stmt
, gsi
);
6482 SLP_TREE_VEC_STMTS (slp_node
).quick_push (new_stmt
);
6483 vect_defs
.quick_push (new_temp
);
6486 vect_defs
[0] = new_temp
;
6493 STMT_VINFO_VEC_STMT (stmt_info
) = *vec_stmt
= new_stmt
;
6495 STMT_VINFO_RELATED_STMT (prev_stmt_info
) = new_stmt
;
6497 prev_stmt_info
= vinfo_for_stmt (new_stmt
);
6500 /* Finalize the reduction-phi (set its arguments) and create the
6501 epilog reduction code. */
6502 if ((!single_defuse_cycle
|| code
== COND_EXPR
) && !slp_node
)
6503 vect_defs
[0] = gimple_assign_lhs (*vec_stmt
);
6505 vect_create_epilog_for_reduction (vect_defs
, stmt
, reduc_def_stmt
,
6507 epilog_reduc_code
, phis
,
6508 double_reduc
, slp_node
, slp_node_instance
);
6513 /* Function vect_min_worthwhile_factor.
6515 For a loop where we could vectorize the operation indicated by CODE,
6516 return the minimum vectorization factor that makes it worthwhile
6517 to use generic vectors. */
6519 vect_min_worthwhile_factor (enum tree_code code
)
6540 /* Function vectorizable_induction
6542 Check if PHI performs an induction computation that can be vectorized.
6543 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
6544 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
6545 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
6548 vectorizable_induction (gimple
*phi
,
6549 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
6550 gimple
**vec_stmt
, slp_tree slp_node
)
6552 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
6553 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
6554 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
6556 bool nested_in_vect_loop
= false;
6557 struct loop
*iv_loop
;
6559 edge pe
= loop_preheader_edge (loop
);
6561 tree new_vec
, vec_init
, vec_step
, t
;
6564 gphi
*induction_phi
;
6565 tree induc_def
, vec_dest
;
6566 tree init_expr
, step_expr
;
6567 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
6571 imm_use_iterator imm_iter
;
6572 use_operand_p use_p
;
6576 gimple_stmt_iterator si
;
6577 basic_block bb
= gimple_bb (phi
);
6579 if (gimple_code (phi
) != GIMPLE_PHI
)
6582 if (!STMT_VINFO_RELEVANT_P (stmt_info
))
6585 /* Make sure it was recognized as induction computation. */
6586 if (STMT_VINFO_DEF_TYPE (stmt_info
) != vect_induction_def
)
6589 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
6590 unsigned nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
6595 ncopies
= vf
/ nunits
;
6596 gcc_assert (ncopies
>= 1);
6598 /* FORNOW. These restrictions should be relaxed. */
6599 if (nested_in_vect_loop_p (loop
, phi
))
6601 imm_use_iterator imm_iter
;
6602 use_operand_p use_p
;
6609 if (dump_enabled_p ())
6610 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6611 "multiple types in nested loop.\n");
6615 /* FORNOW: outer loop induction with SLP not supported. */
6616 if (STMT_SLP_TYPE (stmt_info
))
6620 latch_e
= loop_latch_edge (loop
->inner
);
6621 loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
6622 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
6624 gimple
*use_stmt
= USE_STMT (use_p
);
6625 if (is_gimple_debug (use_stmt
))
6628 if (!flow_bb_inside_loop_p (loop
->inner
, gimple_bb (use_stmt
)))
6630 exit_phi
= use_stmt
;
6636 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
6637 if (!(STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
6638 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
)))
6640 if (dump_enabled_p ())
6641 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6642 "inner-loop induction only used outside "
6643 "of the outer vectorized loop.\n");
6648 nested_in_vect_loop
= true;
6649 iv_loop
= loop
->inner
;
6653 gcc_assert (iv_loop
== (gimple_bb (phi
))->loop_father
);
6655 if (!vec_stmt
) /* transformation not required. */
6657 STMT_VINFO_TYPE (stmt_info
) = induc_vec_info_type
;
6658 if (dump_enabled_p ())
6659 dump_printf_loc (MSG_NOTE
, vect_location
,
6660 "=== vectorizable_induction ===\n");
6661 vect_model_induction_cost (stmt_info
, ncopies
);
6667 /* Compute a vector variable, initialized with the first VF values of
6668 the induction variable. E.g., for an iv with IV_PHI='X' and
6669 evolution S, for a vector of 4 units, we want to compute:
6670 [X, X + S, X + 2*S, X + 3*S]. */
6672 if (dump_enabled_p ())
6673 dump_printf_loc (MSG_NOTE
, vect_location
, "transform induction phi.\n");
6675 latch_e
= loop_latch_edge (iv_loop
);
6676 loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
6678 step_expr
= STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info
);
6679 gcc_assert (step_expr
!= NULL_TREE
);
6681 pe
= loop_preheader_edge (iv_loop
);
6682 init_expr
= PHI_ARG_DEF_FROM_EDGE (phi
,
6683 loop_preheader_edge (iv_loop
));
6685 /* Convert the step to the desired type. */
6687 step_expr
= gimple_convert (&stmts
, TREE_TYPE (vectype
), step_expr
);
6690 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
6691 gcc_assert (!new_bb
);
6694 /* Find the first insertion point in the BB. */
6695 si
= gsi_after_labels (bb
);
6697 /* For SLP induction we have to generate several IVs as for example
6698 with group size 3 we need [i, i, i, i + S] [i + S, i + S, i + 2*S, i + 2*S]
6699 [i + 2*S, i + 3*S, i + 3*S, i + 3*S]. The step is the same uniform
6700 [VF*S, VF*S, VF*S, VF*S] for all. */
6703 /* Convert the init to the desired type. */
6705 init_expr
= gimple_convert (&stmts
, TREE_TYPE (vectype
), init_expr
);
6708 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
6709 gcc_assert (!new_bb
);
6712 /* Generate [VF*S, VF*S, ... ]. */
6713 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
)))
6715 expr
= build_int_cst (integer_type_node
, vf
);
6716 expr
= fold_convert (TREE_TYPE (step_expr
), expr
);
6719 expr
= build_int_cst (TREE_TYPE (step_expr
), vf
);
6720 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
6722 if (! CONSTANT_CLASS_P (new_name
))
6723 new_name
= vect_init_vector (phi
, new_name
,
6724 TREE_TYPE (step_expr
), NULL
);
6725 new_vec
= build_vector_from_val (vectype
, new_name
);
6726 vec_step
= vect_init_vector (phi
, new_vec
, vectype
, NULL
);
6728 /* Now generate the IVs. */
6729 unsigned group_size
= SLP_TREE_SCALAR_STMTS (slp_node
).length ();
6730 unsigned nvects
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
6731 unsigned elts
= nunits
* nvects
;
6732 unsigned nivs
= least_common_multiple (group_size
, nunits
) / nunits
;
6733 gcc_assert (elts
% group_size
== 0);
6734 tree elt
= init_expr
;
6736 for (ivn
= 0; ivn
< nivs
; ++ivn
)
6738 auto_vec
<tree
, 32> elts (nunits
);
6739 bool constant_p
= true;
6740 for (unsigned eltn
= 0; eltn
< nunits
; ++eltn
)
6742 if (ivn
*nunits
+ eltn
>= group_size
6743 && (ivn
*nunits
+ eltn
) % group_size
== 0)
6746 elt
= gimple_build (&stmts
, PLUS_EXPR
, TREE_TYPE (elt
),
6750 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
6751 gcc_assert (!new_bb
);
6754 if (! CONSTANT_CLASS_P (elt
))
6756 elts
.quick_push (elt
);
6759 new_vec
= build_vector (vectype
, elts
);
6762 vec
<constructor_elt
, va_gc
> *v
;
6763 vec_alloc (v
, nunits
);
6764 for (i
= 0; i
< nunits
; ++i
)
6765 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[i
]);
6766 new_vec
= build_constructor (vectype
, v
);
6768 vec_init
= vect_init_vector (phi
, new_vec
, vectype
, NULL
);
6770 /* Create the induction-phi that defines the induction-operand. */
6771 vec_dest
= vect_get_new_vect_var (vectype
, vect_simple_var
, "vec_iv_");
6772 induction_phi
= create_phi_node (vec_dest
, iv_loop
->header
);
6773 set_vinfo_for_stmt (induction_phi
,
6774 new_stmt_vec_info (induction_phi
, loop_vinfo
));
6775 induc_def
= PHI_RESULT (induction_phi
);
6777 /* Create the iv update inside the loop */
6778 vec_def
= make_ssa_name (vec_dest
);
6779 new_stmt
= gimple_build_assign (vec_def
, PLUS_EXPR
, induc_def
, vec_step
);
6780 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
6781 set_vinfo_for_stmt (new_stmt
, new_stmt_vec_info (new_stmt
, loop_vinfo
));
6783 /* Set the arguments of the phi node: */
6784 add_phi_arg (induction_phi
, vec_init
, pe
, UNKNOWN_LOCATION
);
6785 add_phi_arg (induction_phi
, vec_def
, loop_latch_edge (iv_loop
),
6788 SLP_TREE_VEC_STMTS (slp_node
).quick_push (induction_phi
);
6791 /* Re-use IVs when we can. */
6795 = least_common_multiple (group_size
, nunits
) / group_size
;
6796 /* Generate [VF'*S, VF'*S, ... ]. */
6797 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
)))
6799 expr
= build_int_cst (integer_type_node
, vfp
);
6800 expr
= fold_convert (TREE_TYPE (step_expr
), expr
);
6803 expr
= build_int_cst (TREE_TYPE (step_expr
), vfp
);
6804 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
6806 if (! CONSTANT_CLASS_P (new_name
))
6807 new_name
= vect_init_vector (phi
, new_name
,
6808 TREE_TYPE (step_expr
), NULL
);
6809 new_vec
= build_vector_from_val (vectype
, new_name
);
6810 vec_step
= vect_init_vector (phi
, new_vec
, vectype
, NULL
);
6811 for (; ivn
< nvects
; ++ivn
)
6813 gimple
*iv
= SLP_TREE_VEC_STMTS (slp_node
)[ivn
- nivs
];
6815 if (gimple_code (iv
) == GIMPLE_PHI
)
6816 def
= gimple_phi_result (iv
);
6818 def
= gimple_assign_lhs (iv
);
6819 new_stmt
= gimple_build_assign (make_ssa_name (vectype
),
6822 if (gimple_code (iv
) == GIMPLE_PHI
)
6823 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
6826 gimple_stmt_iterator tgsi
= gsi_for_stmt (iv
);
6827 gsi_insert_after (&tgsi
, new_stmt
, GSI_CONTINUE_LINKING
);
6829 set_vinfo_for_stmt (new_stmt
,
6830 new_stmt_vec_info (new_stmt
, loop_vinfo
));
6831 SLP_TREE_VEC_STMTS (slp_node
).quick_push (new_stmt
);
6838 /* Create the vector that holds the initial_value of the induction. */
6839 if (nested_in_vect_loop
)
6841 /* iv_loop is nested in the loop to be vectorized. init_expr had already
6842 been created during vectorization of previous stmts. We obtain it
6843 from the STMT_VINFO_VEC_STMT of the defining stmt. */
6844 vec_init
= vect_get_vec_def_for_operand (init_expr
, phi
);
6845 /* If the initial value is not of proper type, convert it. */
6846 if (!useless_type_conversion_p (vectype
, TREE_TYPE (vec_init
)))
6849 = gimple_build_assign (vect_get_new_ssa_name (vectype
,
6853 build1 (VIEW_CONVERT_EXPR
, vectype
,
6855 vec_init
= gimple_assign_lhs (new_stmt
);
6856 new_bb
= gsi_insert_on_edge_immediate (loop_preheader_edge (iv_loop
),
6858 gcc_assert (!new_bb
);
6859 set_vinfo_for_stmt (new_stmt
,
6860 new_stmt_vec_info (new_stmt
, loop_vinfo
));
6865 vec
<constructor_elt
, va_gc
> *v
;
6867 /* iv_loop is the loop to be vectorized. Create:
6868 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
6870 new_name
= gimple_convert (&stmts
, TREE_TYPE (vectype
), init_expr
);
6872 vec_alloc (v
, nunits
);
6873 bool constant_p
= is_gimple_min_invariant (new_name
);
6874 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
6875 for (i
= 1; i
< nunits
; i
++)
6877 /* Create: new_name_i = new_name + step_expr */
6878 new_name
= gimple_build (&stmts
, PLUS_EXPR
, TREE_TYPE (new_name
),
6879 new_name
, step_expr
);
6880 if (!is_gimple_min_invariant (new_name
))
6882 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
6886 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
6887 gcc_assert (!new_bb
);
6890 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
6892 new_vec
= build_vector_from_ctor (vectype
, v
);
6894 new_vec
= build_constructor (vectype
, v
);
6895 vec_init
= vect_init_vector (phi
, new_vec
, vectype
, NULL
);
6899 /* Create the vector that holds the step of the induction. */
6900 if (nested_in_vect_loop
)
6901 /* iv_loop is nested in the loop to be vectorized. Generate:
6902 vec_step = [S, S, S, S] */
6903 new_name
= step_expr
;
6906 /* iv_loop is the loop to be vectorized. Generate:
6907 vec_step = [VF*S, VF*S, VF*S, VF*S] */
6908 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
)))
6910 expr
= build_int_cst (integer_type_node
, vf
);
6911 expr
= fold_convert (TREE_TYPE (step_expr
), expr
);
6914 expr
= build_int_cst (TREE_TYPE (step_expr
), vf
);
6915 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
6917 if (TREE_CODE (step_expr
) == SSA_NAME
)
6918 new_name
= vect_init_vector (phi
, new_name
,
6919 TREE_TYPE (step_expr
), NULL
);
6922 t
= unshare_expr (new_name
);
6923 gcc_assert (CONSTANT_CLASS_P (new_name
)
6924 || TREE_CODE (new_name
) == SSA_NAME
);
6925 new_vec
= build_vector_from_val (vectype
, t
);
6926 vec_step
= vect_init_vector (phi
, new_vec
, vectype
, NULL
);
6929 /* Create the following def-use cycle:
6934 vec_iv = PHI <vec_init, vec_loop>
6938 vec_loop = vec_iv + vec_step; */
6940 /* Create the induction-phi that defines the induction-operand. */
6941 vec_dest
= vect_get_new_vect_var (vectype
, vect_simple_var
, "vec_iv_");
6942 induction_phi
= create_phi_node (vec_dest
, iv_loop
->header
);
6943 set_vinfo_for_stmt (induction_phi
,
6944 new_stmt_vec_info (induction_phi
, loop_vinfo
));
6945 induc_def
= PHI_RESULT (induction_phi
);
6947 /* Create the iv update inside the loop */
6948 vec_def
= make_ssa_name (vec_dest
);
6949 new_stmt
= gimple_build_assign (vec_def
, PLUS_EXPR
, induc_def
, vec_step
);
6950 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
6951 set_vinfo_for_stmt (new_stmt
, new_stmt_vec_info (new_stmt
, loop_vinfo
));
6953 /* Set the arguments of the phi node: */
6954 add_phi_arg (induction_phi
, vec_init
, pe
, UNKNOWN_LOCATION
);
6955 add_phi_arg (induction_phi
, vec_def
, loop_latch_edge (iv_loop
),
6958 STMT_VINFO_VEC_STMT (stmt_info
) = *vec_stmt
= induction_phi
;
6960 /* In case that vectorization factor (VF) is bigger than the number
6961 of elements that we can fit in a vectype (nunits), we have to generate
6962 more than one vector stmt - i.e - we need to "unroll" the
6963 vector stmt by a factor VF/nunits. For more details see documentation
6964 in vectorizable_operation. */
6968 stmt_vec_info prev_stmt_vinfo
;
6969 /* FORNOW. This restriction should be relaxed. */
6970 gcc_assert (!nested_in_vect_loop
);
6972 /* Create the vector that holds the step of the induction. */
6973 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
)))
6975 expr
= build_int_cst (integer_type_node
, nunits
);
6976 expr
= fold_convert (TREE_TYPE (step_expr
), expr
);
6979 expr
= build_int_cst (TREE_TYPE (step_expr
), nunits
);
6980 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
6982 if (TREE_CODE (step_expr
) == SSA_NAME
)
6983 new_name
= vect_init_vector (phi
, new_name
,
6984 TREE_TYPE (step_expr
), NULL
);
6985 t
= unshare_expr (new_name
);
6986 gcc_assert (CONSTANT_CLASS_P (new_name
)
6987 || TREE_CODE (new_name
) == SSA_NAME
);
6988 new_vec
= build_vector_from_val (vectype
, t
);
6989 vec_step
= vect_init_vector (phi
, new_vec
, vectype
, NULL
);
6991 vec_def
= induc_def
;
6992 prev_stmt_vinfo
= vinfo_for_stmt (induction_phi
);
6993 for (i
= 1; i
< ncopies
; i
++)
6995 /* vec_i = vec_prev + vec_step */
6996 new_stmt
= gimple_build_assign (vec_dest
, PLUS_EXPR
,
6998 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
6999 gimple_assign_set_lhs (new_stmt
, vec_def
);
7001 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
7002 set_vinfo_for_stmt (new_stmt
,
7003 new_stmt_vec_info (new_stmt
, loop_vinfo
));
7004 STMT_VINFO_RELATED_STMT (prev_stmt_vinfo
) = new_stmt
;
7005 prev_stmt_vinfo
= vinfo_for_stmt (new_stmt
);
7009 if (nested_in_vect_loop
)
7011 /* Find the loop-closed exit-phi of the induction, and record
7012 the final vector of induction results: */
7014 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
7016 gimple
*use_stmt
= USE_STMT (use_p
);
7017 if (is_gimple_debug (use_stmt
))
7020 if (!flow_bb_inside_loop_p (iv_loop
, gimple_bb (use_stmt
)))
7022 exit_phi
= use_stmt
;
7028 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (exit_phi
);
7029 /* FORNOW. Currently not supporting the case that an inner-loop induction
7030 is not used in the outer-loop (i.e. only outside the outer-loop). */
7031 gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo
)
7032 && !STMT_VINFO_LIVE_P (stmt_vinfo
));
7034 STMT_VINFO_VEC_STMT (stmt_vinfo
) = new_stmt
;
7035 if (dump_enabled_p ())
7037 dump_printf_loc (MSG_NOTE
, vect_location
,
7038 "vector of inductions after inner-loop:");
7039 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, new_stmt
, 0);
7045 if (dump_enabled_p ())
7047 dump_printf_loc (MSG_NOTE
, vect_location
,
7048 "transform induction: created def-use cycle: ");
7049 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, induction_phi
, 0);
7050 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
7051 SSA_NAME_DEF_STMT (vec_def
), 0);
7057 /* Function vectorizable_live_operation.
7059 STMT computes a value that is used outside the loop. Check if
7060 it can be supported. */
7063 vectorizable_live_operation (gimple
*stmt
,
7064 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
7065 slp_tree slp_node
, int slp_index
,
7068 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
7069 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
7070 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
7071 imm_use_iterator imm_iter
;
7072 tree lhs
, lhs_type
, bitsize
, vec_bitsize
;
7073 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
7074 int nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
7075 int ncopies
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) / nunits
;
7077 auto_vec
<tree
> vec_oprnds
;
7079 gcc_assert (STMT_VINFO_LIVE_P (stmt_info
));
7081 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_reduction_def
)
7084 /* FORNOW. CHECKME. */
7085 if (nested_in_vect_loop_p (loop
, stmt
))
7088 /* If STMT is not relevant and it is a simple assignment and its inputs are
7089 invariant then it can remain in place, unvectorized. The original last
7090 scalar value that it computes will be used. */
7091 if (!STMT_VINFO_RELEVANT_P (stmt_info
))
7093 gcc_assert (is_simple_and_all_uses_invariant (stmt
, loop_vinfo
));
7094 if (dump_enabled_p ())
7095 dump_printf_loc (MSG_NOTE
, vect_location
,
7096 "statement is simple and uses invariant. Leaving in "
7102 /* No transformation required. */
7105 /* If stmt has a related stmt, then use that for getting the lhs. */
7106 if (is_pattern_stmt_p (stmt_info
))
7107 stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
7109 lhs
= (is_a
<gphi
*> (stmt
)) ? gimple_phi_result (stmt
)
7110 : gimple_get_lhs (stmt
);
7111 lhs_type
= TREE_TYPE (lhs
);
7113 bitsize
= TYPE_SIZE (TREE_TYPE (vectype
));
7114 vec_bitsize
= TYPE_SIZE (vectype
);
7116 /* Get the vectorized lhs of STMT and the lane to use (counted in bits). */
7117 tree vec_lhs
, bitstart
;
7120 gcc_assert (slp_index
>= 0);
7122 int num_scalar
= SLP_TREE_SCALAR_STMTS (slp_node
).length ();
7123 int num_vec
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
7125 /* Get the last occurrence of the scalar index from the concatenation of
7126 all the slp vectors. Calculate which slp vector it is and the index
7128 int pos
= (num_vec
* nunits
) - num_scalar
+ slp_index
;
7129 int vec_entry
= pos
/ nunits
;
7130 int vec_index
= pos
% nunits
;
7132 /* Get the correct slp vectorized stmt. */
7133 vec_lhs
= gimple_get_lhs (SLP_TREE_VEC_STMTS (slp_node
)[vec_entry
]);
7135 /* Get entry to use. */
7136 bitstart
= build_int_cst (unsigned_type_node
, vec_index
);
7137 bitstart
= int_const_binop (MULT_EXPR
, bitsize
, bitstart
);
7141 enum vect_def_type dt
= STMT_VINFO_DEF_TYPE (stmt_info
);
7142 vec_lhs
= vect_get_vec_def_for_operand_1 (stmt
, dt
);
7144 /* For multiple copies, get the last copy. */
7145 for (int i
= 1; i
< ncopies
; ++i
)
7146 vec_lhs
= vect_get_vec_def_for_stmt_copy (vect_unknown_def_type
,
7149 /* Get the last lane in the vector. */
7150 bitstart
= int_const_binop (MINUS_EXPR
, vec_bitsize
, bitsize
);
7153 /* Create a new vectorized stmt for the uses of STMT and insert outside the
7155 gimple_seq stmts
= NULL
;
7156 tree bftype
= TREE_TYPE (vectype
);
7157 if (VECTOR_BOOLEAN_TYPE_P (vectype
))
7158 bftype
= build_nonstandard_integer_type (tree_to_uhwi (bitsize
), 1);
7159 tree new_tree
= build3 (BIT_FIELD_REF
, bftype
, vec_lhs
, bitsize
, bitstart
);
7160 new_tree
= force_gimple_operand (fold_convert (lhs_type
, new_tree
), &stmts
,
7163 gsi_insert_seq_on_edge_immediate (single_exit (loop
), stmts
);
7165 /* Replace use of lhs with newly computed result. If the use stmt is a
7166 single arg PHI, just replace all uses of PHI result. It's necessary
7167 because lcssa PHI defining lhs may be before newly inserted stmt. */
7168 use_operand_p use_p
;
7169 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, lhs
)
7170 if (!flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
))
7171 && !is_gimple_debug (use_stmt
))
7173 if (gimple_code (use_stmt
) == GIMPLE_PHI
7174 && gimple_phi_num_args (use_stmt
) == 1)
7176 replace_uses_by (gimple_phi_result (use_stmt
), new_tree
);
7180 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
7181 SET_USE (use_p
, new_tree
);
7183 update_stmt (use_stmt
);
7189 /* Kill any debug uses outside LOOP of SSA names defined in STMT. */
7192 vect_loop_kill_debug_uses (struct loop
*loop
, gimple
*stmt
)
7194 ssa_op_iter op_iter
;
7195 imm_use_iterator imm_iter
;
7196 def_operand_p def_p
;
7199 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
7201 FOR_EACH_IMM_USE_STMT (ustmt
, imm_iter
, DEF_FROM_PTR (def_p
))
7205 if (!is_gimple_debug (ustmt
))
7208 bb
= gimple_bb (ustmt
);
7210 if (!flow_bb_inside_loop_p (loop
, bb
))
7212 if (gimple_debug_bind_p (ustmt
))
7214 if (dump_enabled_p ())
7215 dump_printf_loc (MSG_NOTE
, vect_location
,
7216 "killing debug use\n");
7218 gimple_debug_bind_reset_value (ustmt
);
7219 update_stmt (ustmt
);
7228 /* Given loop represented by LOOP_VINFO, return true if computation of
7229 LOOP_VINFO_NITERS (= LOOP_VINFO_NITERSM1 + 1) doesn't overflow, false
7233 loop_niters_no_overflow (loop_vec_info loop_vinfo
)
7235 /* Constant case. */
7236 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
7238 tree cst_niters
= LOOP_VINFO_NITERS (loop_vinfo
);
7239 tree cst_nitersm1
= LOOP_VINFO_NITERSM1 (loop_vinfo
);
7241 gcc_assert (TREE_CODE (cst_niters
) == INTEGER_CST
);
7242 gcc_assert (TREE_CODE (cst_nitersm1
) == INTEGER_CST
);
7243 if (wi::to_widest (cst_nitersm1
) < wi::to_widest (cst_niters
))
7248 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
7249 /* Check the upper bound of loop niters. */
7250 if (get_max_loop_iterations (loop
, &max
))
7252 tree type
= TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo
));
7253 signop sgn
= TYPE_SIGN (type
);
7254 widest_int type_max
= widest_int::from (wi::max_value (type
), sgn
);
7261 /* Scale profiling counters by estimation for LOOP which is vectorized
7265 scale_profile_for_vect_loop (struct loop
*loop
, unsigned vf
)
7267 edge preheader
= loop_preheader_edge (loop
);
7268 /* Reduce loop iterations by the vectorization factor. */
7269 gcov_type new_est_niter
= niter_for_unrolled_loop (loop
, vf
);
7270 profile_count freq_h
= loop
->header
->count
, freq_e
= preheader
->count
;
7272 /* Use frequency only if counts are zero. */
7273 if (!(freq_h
> 0) && !(freq_e
> 0))
7275 freq_h
= profile_count::from_gcov_type (loop
->header
->frequency
);
7276 freq_e
= profile_count::from_gcov_type (EDGE_FREQUENCY (preheader
));
7280 profile_probability p
;
7282 /* Avoid dropping loop body profile counter to 0 because of zero count
7283 in loop's preheader. */
7284 if (!(freq_e
> profile_count::from_gcov_type (1)))
7285 freq_e
= profile_count::from_gcov_type (1);
7286 p
= freq_e
.apply_scale (new_est_niter
+ 1, 1).probability_in (freq_h
);
7287 scale_loop_frequencies (loop
, p
);
7290 basic_block exit_bb
= single_pred (loop
->latch
);
7291 edge exit_e
= single_exit (loop
);
7292 exit_e
->count
= loop_preheader_edge (loop
)->count
;
7293 exit_e
->probability
= profile_probability::always ()
7294 .apply_scale (1, new_est_niter
+ 1);
7296 edge exit_l
= single_pred_edge (loop
->latch
);
7297 profile_probability prob
= exit_l
->probability
;
7298 exit_l
->probability
= exit_e
->probability
.invert ();
7299 exit_l
->count
= exit_bb
->count
- exit_e
->count
;
7300 if (prob
.initialized_p () && exit_l
->probability
.initialized_p ())
7301 scale_bbs_frequencies (&loop
->latch
, 1, exit_l
->probability
/ prob
);
7304 /* Function vect_transform_loop.
7306 The analysis phase has determined that the loop is vectorizable.
7307 Vectorize the loop - created vectorized stmts to replace the scalar
7308 stmts in the loop, and update the loop exit condition.
7309 Returns scalar epilogue loop if any. */
7312 vect_transform_loop (loop_vec_info loop_vinfo
)
7314 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
7315 struct loop
*epilogue
= NULL
;
7316 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
7317 int nbbs
= loop
->num_nodes
;
7319 tree niters_vector
= NULL
;
7320 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
7322 bool slp_scheduled
= false;
7323 gimple
*stmt
, *pattern_stmt
;
7324 gimple_seq pattern_def_seq
= NULL
;
7325 gimple_stmt_iterator pattern_def_si
= gsi_none ();
7326 bool transform_pattern_stmt
= false;
7327 bool check_profitability
= false;
7330 if (dump_enabled_p ())
7331 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vec_transform_loop ===\n");
7333 /* Use the more conservative vectorization threshold. If the number
7334 of iterations is constant assume the cost check has been performed
7335 by our caller. If the threshold makes all loops profitable that
7336 run at least the vectorization factor number of times checking
7337 is pointless, too. */
7338 th
= LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo
);
7339 if (th
>= LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
7340 && !LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
7342 if (dump_enabled_p ())
7343 dump_printf_loc (MSG_NOTE
, vect_location
,
7344 "Profitability threshold is %d loop iterations.\n",
7346 check_profitability
= true;
7349 /* Make sure there exists a single-predecessor exit bb. Do this before
7351 edge e
= single_exit (loop
);
7352 if (! single_pred_p (e
->dest
))
7354 split_loop_exit_edge (e
);
7355 if (dump_enabled_p ())
7356 dump_printf (MSG_NOTE
, "split exit edge\n");
7359 /* Version the loop first, if required, so the profitability check
7362 if (LOOP_REQUIRES_VERSIONING (loop_vinfo
))
7364 vect_loop_versioning (loop_vinfo
, th
, check_profitability
);
7365 check_profitability
= false;
7368 /* Make sure there exists a single-predecessor exit bb also on the
7369 scalar loop copy. Do this after versioning but before peeling
7370 so CFG structure is fine for both scalar and if-converted loop
7371 to make slpeel_duplicate_current_defs_from_edges face matched
7372 loop closed PHI nodes on the exit. */
7373 if (LOOP_VINFO_SCALAR_LOOP (loop_vinfo
))
7375 e
= single_exit (LOOP_VINFO_SCALAR_LOOP (loop_vinfo
));
7376 if (! single_pred_p (e
->dest
))
7378 split_loop_exit_edge (e
);
7379 if (dump_enabled_p ())
7380 dump_printf (MSG_NOTE
, "split exit edge of scalar loop\n");
7384 tree niters
= vect_build_loop_niters (loop_vinfo
);
7385 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo
) = niters
;
7386 tree nitersm1
= unshare_expr (LOOP_VINFO_NITERSM1 (loop_vinfo
));
7387 bool niters_no_overflow
= loop_niters_no_overflow (loop_vinfo
);
7388 epilogue
= vect_do_peeling (loop_vinfo
, niters
, nitersm1
, &niters_vector
, th
,
7389 check_profitability
, niters_no_overflow
);
7390 if (niters_vector
== NULL_TREE
)
7392 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
7394 = build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo
)),
7395 LOOP_VINFO_INT_NITERS (loop_vinfo
) / vf
);
7397 vect_gen_vector_loop_niters (loop_vinfo
, niters
, &niters_vector
,
7398 niters_no_overflow
);
7401 /* 1) Make sure the loop header has exactly two entries
7402 2) Make sure we have a preheader basic block. */
7404 gcc_assert (EDGE_COUNT (loop
->header
->preds
) == 2);
7406 split_edge (loop_preheader_edge (loop
));
7408 /* FORNOW: the vectorizer supports only loops which body consist
7409 of one basic block (header + empty latch). When the vectorizer will
7410 support more involved loop forms, the order by which the BBs are
7411 traversed need to be reconsidered. */
7413 for (i
= 0; i
< nbbs
; i
++)
7415 basic_block bb
= bbs
[i
];
7416 stmt_vec_info stmt_info
;
7418 for (gphi_iterator si
= gsi_start_phis (bb
); !gsi_end_p (si
);
7421 gphi
*phi
= si
.phi ();
7422 if (dump_enabled_p ())
7424 dump_printf_loc (MSG_NOTE
, vect_location
,
7425 "------>vectorizing phi: ");
7426 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
7428 stmt_info
= vinfo_for_stmt (phi
);
7432 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
7433 vect_loop_kill_debug_uses (loop
, phi
);
7435 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
7436 && !STMT_VINFO_LIVE_P (stmt_info
))
7439 if (STMT_VINFO_VECTYPE (stmt_info
)
7440 && (TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
))
7441 != (unsigned HOST_WIDE_INT
) vf
)
7442 && dump_enabled_p ())
7443 dump_printf_loc (MSG_NOTE
, vect_location
, "multiple-types.\n");
7445 if ((STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
7446 || STMT_VINFO_DEF_TYPE (stmt_info
) == vect_reduction_def
7447 || STMT_VINFO_DEF_TYPE (stmt_info
) == vect_nested_cycle
)
7448 && ! PURE_SLP_STMT (stmt_info
))
7450 if (dump_enabled_p ())
7451 dump_printf_loc (MSG_NOTE
, vect_location
, "transform phi.\n");
7452 vect_transform_stmt (phi
, NULL
, NULL
, NULL
, NULL
);
7456 pattern_stmt
= NULL
;
7457 for (gimple_stmt_iterator si
= gsi_start_bb (bb
);
7458 !gsi_end_p (si
) || transform_pattern_stmt
;)
7462 if (transform_pattern_stmt
)
7463 stmt
= pattern_stmt
;
7466 stmt
= gsi_stmt (si
);
7467 /* During vectorization remove existing clobber stmts. */
7468 if (gimple_clobber_p (stmt
))
7470 unlink_stmt_vdef (stmt
);
7471 gsi_remove (&si
, true);
7472 release_defs (stmt
);
7477 if (dump_enabled_p ())
7479 dump_printf_loc (MSG_NOTE
, vect_location
,
7480 "------>vectorizing statement: ");
7481 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
7484 stmt_info
= vinfo_for_stmt (stmt
);
7486 /* vector stmts created in the outer-loop during vectorization of
7487 stmts in an inner-loop may not have a stmt_info, and do not
7488 need to be vectorized. */
7495 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
7496 vect_loop_kill_debug_uses (loop
, stmt
);
7498 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
7499 && !STMT_VINFO_LIVE_P (stmt_info
))
7501 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
7502 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
7503 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
7504 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
7506 stmt
= pattern_stmt
;
7507 stmt_info
= vinfo_for_stmt (stmt
);
7515 else if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
7516 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
7517 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
7518 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
7519 transform_pattern_stmt
= true;
7521 /* If pattern statement has def stmts, vectorize them too. */
7522 if (is_pattern_stmt_p (stmt_info
))
7524 if (pattern_def_seq
== NULL
)
7526 pattern_def_seq
= STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
);
7527 pattern_def_si
= gsi_start (pattern_def_seq
);
7529 else if (!gsi_end_p (pattern_def_si
))
7530 gsi_next (&pattern_def_si
);
7531 if (pattern_def_seq
!= NULL
)
7533 gimple
*pattern_def_stmt
= NULL
;
7534 stmt_vec_info pattern_def_stmt_info
= NULL
;
7536 while (!gsi_end_p (pattern_def_si
))
7538 pattern_def_stmt
= gsi_stmt (pattern_def_si
);
7539 pattern_def_stmt_info
7540 = vinfo_for_stmt (pattern_def_stmt
);
7541 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info
)
7542 || STMT_VINFO_LIVE_P (pattern_def_stmt_info
))
7544 gsi_next (&pattern_def_si
);
7547 if (!gsi_end_p (pattern_def_si
))
7549 if (dump_enabled_p ())
7551 dump_printf_loc (MSG_NOTE
, vect_location
,
7552 "==> vectorizing pattern def "
7554 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
7555 pattern_def_stmt
, 0);
7558 stmt
= pattern_def_stmt
;
7559 stmt_info
= pattern_def_stmt_info
;
7563 pattern_def_si
= gsi_none ();
7564 transform_pattern_stmt
= false;
7568 transform_pattern_stmt
= false;
7571 if (STMT_VINFO_VECTYPE (stmt_info
))
7575 TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
7576 if (!STMT_SLP_TYPE (stmt_info
)
7577 && nunits
!= (unsigned int) vf
7578 && dump_enabled_p ())
7579 /* For SLP VF is set according to unrolling factor, and not
7580 to vector size, hence for SLP this print is not valid. */
7581 dump_printf_loc (MSG_NOTE
, vect_location
, "multiple-types.\n");
7584 /* SLP. Schedule all the SLP instances when the first SLP stmt is
7586 if (STMT_SLP_TYPE (stmt_info
))
7590 slp_scheduled
= true;
7592 if (dump_enabled_p ())
7593 dump_printf_loc (MSG_NOTE
, vect_location
,
7594 "=== scheduling SLP instances ===\n");
7596 vect_schedule_slp (loop_vinfo
);
7599 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
7600 if (!vinfo_for_stmt (stmt
) || PURE_SLP_STMT (stmt_info
))
7602 if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
7604 pattern_def_seq
= NULL
;
7611 /* -------- vectorize statement ------------ */
7612 if (dump_enabled_p ())
7613 dump_printf_loc (MSG_NOTE
, vect_location
, "transform statement.\n");
7615 grouped_store
= false;
7616 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, NULL
, NULL
);
7619 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
7621 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
7622 interleaving chain was completed - free all the stores in
7625 vect_remove_stores (GROUP_FIRST_ELEMENT (stmt_info
));
7629 /* Free the attached stmt_vec_info and remove the stmt. */
7630 gimple
*store
= gsi_stmt (si
);
7631 free_stmt_vec_info (store
);
7632 unlink_stmt_vdef (store
);
7633 gsi_remove (&si
, true);
7634 release_defs (store
);
7637 /* Stores can only appear at the end of pattern statements. */
7638 gcc_assert (!transform_pattern_stmt
);
7639 pattern_def_seq
= NULL
;
7641 else if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
7643 pattern_def_seq
= NULL
;
7649 slpeel_make_loop_iterate_ntimes (loop
, niters_vector
);
7651 scale_profile_for_vect_loop (loop
, vf
);
7653 /* The minimum number of iterations performed by the epilogue. This
7654 is 1 when peeling for gaps because we always need a final scalar
7656 int min_epilogue_iters
= LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) ? 1 : 0;
7657 /* +1 to convert latch counts to loop iteration counts,
7658 -min_epilogue_iters to remove iterations that cannot be performed
7659 by the vector code. */
7660 int bias
= 1 - min_epilogue_iters
;
7661 /* In these calculations the "- 1" converts loop iteration counts
7662 back to latch counts. */
7663 if (loop
->any_upper_bound
)
7664 loop
->nb_iterations_upper_bound
7665 = wi::udiv_floor (loop
->nb_iterations_upper_bound
+ bias
, vf
) - 1;
7666 if (loop
->any_likely_upper_bound
)
7667 loop
->nb_iterations_likely_upper_bound
7668 = wi::udiv_floor (loop
->nb_iterations_likely_upper_bound
+ bias
, vf
) - 1;
7669 if (loop
->any_estimate
)
7670 loop
->nb_iterations_estimate
7671 = wi::udiv_floor (loop
->nb_iterations_estimate
+ bias
, vf
) - 1;
7673 if (dump_enabled_p ())
7675 if (!LOOP_VINFO_EPILOGUE_P (loop_vinfo
))
7677 dump_printf_loc (MSG_NOTE
, vect_location
,
7678 "LOOP VECTORIZED\n");
7680 dump_printf_loc (MSG_NOTE
, vect_location
,
7681 "OUTER LOOP VECTORIZED\n");
7682 dump_printf (MSG_NOTE
, "\n");
7685 dump_printf_loc (MSG_NOTE
, vect_location
,
7686 "LOOP EPILOGUE VECTORIZED (VS=%d)\n",
7687 current_vector_size
);
7690 /* Free SLP instances here because otherwise stmt reference counting
7692 slp_instance instance
;
7693 FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (loop_vinfo
), i
, instance
)
7694 vect_free_slp_instance (instance
);
7695 LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).release ();
7696 /* Clear-up safelen field since its value is invalid after vectorization
7697 since vectorized loop can have loop-carried dependencies. */
7700 /* Don't vectorize epilogue for epilogue. */
7701 if (LOOP_VINFO_EPILOGUE_P (loop_vinfo
))
7706 unsigned int vector_sizes
7707 = targetm
.vectorize
.autovectorize_vector_sizes ();
7708 vector_sizes
&= current_vector_size
- 1;
7710 if (!PARAM_VALUE (PARAM_VECT_EPILOGUES_NOMASK
))
7712 else if (!vector_sizes
)
7714 else if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
7715 && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
) >= 0)
7717 int smallest_vec_size
= 1 << ctz_hwi (vector_sizes
);
7718 int ratio
= current_vector_size
/ smallest_vec_size
;
7719 int eiters
= LOOP_VINFO_INT_NITERS (loop_vinfo
)
7720 - LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
);
7721 eiters
= eiters
% vf
;
7723 epilogue
->nb_iterations_upper_bound
= eiters
- 1;
7725 if (eiters
< vf
/ ratio
)
7732 epilogue
->force_vectorize
= loop
->force_vectorize
;
7733 epilogue
->safelen
= loop
->safelen
;
7734 epilogue
->dont_vectorize
= false;
7736 /* We may need to if-convert epilogue to vectorize it. */
7737 if (LOOP_VINFO_SCALAR_LOOP (loop_vinfo
))
7738 tree_if_conversion (epilogue
);
7744 /* The code below is trying to perform simple optimization - revert
7745 if-conversion for masked stores, i.e. if the mask of a store is zero
7746 do not perform it and all stored value producers also if possible.
7754 this transformation will produce the following semi-hammock:
7756 if (!mask__ifc__42.18_165 == { 0, 0, 0, 0, 0, 0, 0, 0 })
7758 vect__11.19_170 = MASK_LOAD (vectp_p1.20_168, 0B, mask__ifc__42.18_165);
7759 vect__12.22_172 = vect__11.19_170 + vect_cst__171;
7760 MASK_STORE (vectp_p1.23_175, 0B, mask__ifc__42.18_165, vect__12.22_172);
7761 vect__18.25_182 = MASK_LOAD (vectp_p3.26_180, 0B, mask__ifc__42.18_165);
7762 vect__19.28_184 = vect__18.25_182 + vect_cst__183;
7763 MASK_STORE (vectp_p2.29_187, 0B, mask__ifc__42.18_165, vect__19.28_184);
7768 optimize_mask_stores (struct loop
*loop
)
7770 basic_block
*bbs
= get_loop_body (loop
);
7771 unsigned nbbs
= loop
->num_nodes
;
7774 struct loop
*bb_loop
;
7775 gimple_stmt_iterator gsi
;
7777 auto_vec
<gimple
*> worklist
;
7779 vect_location
= find_loop_location (loop
);
7780 /* Pick up all masked stores in loop if any. */
7781 for (i
= 0; i
< nbbs
; i
++)
7784 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
7787 stmt
= gsi_stmt (gsi
);
7788 if (gimple_call_internal_p (stmt
, IFN_MASK_STORE
))
7789 worklist
.safe_push (stmt
);
7794 if (worklist
.is_empty ())
7797 /* Loop has masked stores. */
7798 while (!worklist
.is_empty ())
7800 gimple
*last
, *last_store
;
7803 basic_block store_bb
, join_bb
;
7804 gimple_stmt_iterator gsi_to
;
7805 tree vdef
, new_vdef
;
7810 last
= worklist
.pop ();
7811 mask
= gimple_call_arg (last
, 2);
7812 bb
= gimple_bb (last
);
7813 /* Create then_bb and if-then structure in CFG, then_bb belongs to
7814 the same loop as if_bb. It could be different to LOOP when two
7815 level loop-nest is vectorized and mask_store belongs to the inner
7817 e
= split_block (bb
, last
);
7818 bb_loop
= bb
->loop_father
;
7819 gcc_assert (loop
== bb_loop
|| flow_loop_nested_p (loop
, bb_loop
));
7821 store_bb
= create_empty_bb (bb
);
7822 add_bb_to_loop (store_bb
, bb_loop
);
7823 e
->flags
= EDGE_TRUE_VALUE
;
7824 efalse
= make_edge (bb
, store_bb
, EDGE_FALSE_VALUE
);
7825 /* Put STORE_BB to likely part. */
7826 efalse
->probability
= profile_probability::unlikely ();
7827 store_bb
->frequency
= PROB_ALWAYS
- EDGE_FREQUENCY (efalse
);
7828 make_single_succ_edge (store_bb
, join_bb
, EDGE_FALLTHRU
);
7829 if (dom_info_available_p (CDI_DOMINATORS
))
7830 set_immediate_dominator (CDI_DOMINATORS
, store_bb
, bb
);
7831 if (dump_enabled_p ())
7832 dump_printf_loc (MSG_NOTE
, vect_location
,
7833 "Create new block %d to sink mask stores.",
7835 /* Create vector comparison with boolean result. */
7836 vectype
= TREE_TYPE (mask
);
7837 zero
= build_zero_cst (vectype
);
7838 stmt
= gimple_build_cond (EQ_EXPR
, mask
, zero
, NULL_TREE
, NULL_TREE
);
7839 gsi
= gsi_last_bb (bb
);
7840 gsi_insert_after (&gsi
, stmt
, GSI_SAME_STMT
);
7841 /* Create new PHI node for vdef of the last masked store:
7842 .MEM_2 = VDEF <.MEM_1>
7843 will be converted to
7844 .MEM.3 = VDEF <.MEM_1>
7845 and new PHI node will be created in join bb
7846 .MEM_2 = PHI <.MEM_1, .MEM_3>
7848 vdef
= gimple_vdef (last
);
7849 new_vdef
= make_ssa_name (gimple_vop (cfun
), last
);
7850 gimple_set_vdef (last
, new_vdef
);
7851 phi
= create_phi_node (vdef
, join_bb
);
7852 add_phi_arg (phi
, new_vdef
, EDGE_SUCC (store_bb
, 0), UNKNOWN_LOCATION
);
7854 /* Put all masked stores with the same mask to STORE_BB if possible. */
7857 gimple_stmt_iterator gsi_from
;
7858 gimple
*stmt1
= NULL
;
7860 /* Move masked store to STORE_BB. */
7862 gsi
= gsi_for_stmt (last
);
7864 /* Shift GSI to the previous stmt for further traversal. */
7866 gsi_to
= gsi_start_bb (store_bb
);
7867 gsi_move_before (&gsi_from
, &gsi_to
);
7868 /* Setup GSI_TO to the non-empty block start. */
7869 gsi_to
= gsi_start_bb (store_bb
);
7870 if (dump_enabled_p ())
7872 dump_printf_loc (MSG_NOTE
, vect_location
,
7873 "Move stmt to created bb\n");
7874 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, last
, 0);
7876 /* Move all stored value producers if possible. */
7877 while (!gsi_end_p (gsi
))
7880 imm_use_iterator imm_iter
;
7881 use_operand_p use_p
;
7884 /* Skip debug statements. */
7885 if (is_gimple_debug (gsi_stmt (gsi
)))
7890 stmt1
= gsi_stmt (gsi
);
7891 /* Do not consider statements writing to memory or having
7892 volatile operand. */
7893 if (gimple_vdef (stmt1
)
7894 || gimple_has_volatile_ops (stmt1
))
7898 lhs
= gimple_get_lhs (stmt1
);
7902 /* LHS of vectorized stmt must be SSA_NAME. */
7903 if (TREE_CODE (lhs
) != SSA_NAME
)
7906 if (!VECTOR_TYPE_P (TREE_TYPE (lhs
)))
7908 /* Remove dead scalar statement. */
7909 if (has_zero_uses (lhs
))
7911 gsi_remove (&gsi_from
, true);
7916 /* Check that LHS does not have uses outside of STORE_BB. */
7918 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
7921 use_stmt
= USE_STMT (use_p
);
7922 if (is_gimple_debug (use_stmt
))
7924 if (gimple_bb (use_stmt
) != store_bb
)
7933 if (gimple_vuse (stmt1
)
7934 && gimple_vuse (stmt1
) != gimple_vuse (last_store
))
7937 /* Can move STMT1 to STORE_BB. */
7938 if (dump_enabled_p ())
7940 dump_printf_loc (MSG_NOTE
, vect_location
,
7941 "Move stmt to created bb\n");
7942 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt1
, 0);
7944 gsi_move_before (&gsi_from
, &gsi_to
);
7945 /* Shift GSI_TO for further insertion. */
7948 /* Put other masked stores with the same mask to STORE_BB. */
7949 if (worklist
.is_empty ()
7950 || gimple_call_arg (worklist
.last (), 2) != mask
7951 || worklist
.last () != stmt1
)
7953 last
= worklist
.pop ();
7955 add_phi_arg (phi
, gimple_vuse (last_store
), e
, UNKNOWN_LOCATION
);