2 Copyright (C) 2003-2015 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"
46 #include "tree-scalar-evolution.h"
47 #include "tree-vectorizer.h"
48 #include "gimple-fold.h"
51 /* Loop Vectorization Pass.
53 This pass tries to vectorize loops.
55 For example, the vectorizer transforms the following simple loop:
57 short a[N]; short b[N]; short c[N]; int i;
63 as if it was manually vectorized by rewriting the source code into:
65 typedef int __attribute__((mode(V8HI))) v8hi;
66 short a[N]; short b[N]; short c[N]; int i;
67 v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
70 for (i=0; i<N/8; i++){
77 The main entry to this pass is vectorize_loops(), in which
78 the vectorizer applies a set of analyses on a given set of loops,
79 followed by the actual vectorization transformation for the loops that
80 had successfully passed the analysis phase.
81 Throughout this pass we make a distinction between two types of
82 data: scalars (which are represented by SSA_NAMES), and memory references
83 ("data-refs"). These two types of data require different handling both
84 during analysis and transformation. The types of data-refs that the
85 vectorizer currently supports are ARRAY_REFS which base is an array DECL
86 (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
87 accesses are required to have a simple (consecutive) access pattern.
91 The driver for the analysis phase is vect_analyze_loop().
92 It applies a set of analyses, some of which rely on the scalar evolution
93 analyzer (scev) developed by Sebastian Pop.
95 During the analysis phase the vectorizer records some information
96 per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
97 loop, as well as general information about the loop as a whole, which is
98 recorded in a "loop_vec_info" struct attached to each loop.
100 Transformation phase:
101 =====================
102 The loop transformation phase scans all the stmts in the loop, and
103 creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
104 the loop that needs to be vectorized. It inserts the vector code sequence
105 just before the scalar stmt S, and records a pointer to the vector code
106 in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
107 attached to S). This pointer will be used for the vectorization of following
108 stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
109 otherwise, we rely on dead code elimination for removing it.
111 For example, say stmt S1 was vectorized into stmt VS1:
114 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
117 To vectorize stmt S2, the vectorizer first finds the stmt that defines
118 the operand 'b' (S1), and gets the relevant vector def 'vb' from the
119 vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
120 resulting sequence would be:
123 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
125 S2: a = b; STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
127 Operands that are not SSA_NAMEs, are data-refs that appear in
128 load/store operations (like 'x[i]' in S1), and are handled differently.
132 Currently the only target specific information that is used is the
133 size of the vector (in bytes) - "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD".
134 Targets that can support different sizes of vectors, for now will need
135 to specify one value for "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD". More
136 flexibility will be added in the future.
138 Since we only vectorize operations which vector form can be
139 expressed using existing tree codes, to verify that an operation is
140 supported, the vectorizer checks the relevant optab at the relevant
141 machine_mode (e.g, optab_handler (add_optab, V8HImode)). If
142 the value found is CODE_FOR_nothing, then there's no target support, and
143 we can't vectorize the stmt.
145 For additional information on this project see:
146 http://gcc.gnu.org/projects/tree-ssa/vectorization.html
149 static void vect_estimate_min_profitable_iters (loop_vec_info
, int *, int *);
151 /* Function vect_determine_vectorization_factor
153 Determine the vectorization factor (VF). VF is the number of data elements
154 that are operated upon in parallel in a single iteration of the vectorized
155 loop. For example, when vectorizing a loop that operates on 4byte elements,
156 on a target with vector size (VS) 16byte, the VF is set to 4, since 4
157 elements can fit in a single vector register.
159 We currently support vectorization of loops in which all types operated upon
160 are of the same size. Therefore this function currently sets VF according to
161 the size of the types operated upon, and fails if there are multiple sizes
164 VF is also the factor by which the loop iterations are strip-mined, e.g.:
171 for (i=0; i<N; i+=VF){
172 a[i:VF] = b[i:VF] + c[i:VF];
177 vect_determine_vectorization_factor (loop_vec_info loop_vinfo
)
179 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
180 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
181 unsigned nbbs
= loop
->num_nodes
;
182 unsigned int vectorization_factor
= 0;
187 stmt_vec_info stmt_info
;
190 gimple
*stmt
, *pattern_stmt
= NULL
;
191 gimple_seq pattern_def_seq
= NULL
;
192 gimple_stmt_iterator pattern_def_si
= gsi_none ();
193 bool analyze_pattern_stmt
= false;
195 auto_vec
<stmt_vec_info
> mask_producers
;
197 if (dump_enabled_p ())
198 dump_printf_loc (MSG_NOTE
, vect_location
,
199 "=== vect_determine_vectorization_factor ===\n");
201 for (i
= 0; i
< nbbs
; i
++)
203 basic_block bb
= bbs
[i
];
205 for (gphi_iterator si
= gsi_start_phis (bb
); !gsi_end_p (si
);
209 stmt_info
= vinfo_for_stmt (phi
);
210 if (dump_enabled_p ())
212 dump_printf_loc (MSG_NOTE
, vect_location
, "==> examining phi: ");
213 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
214 dump_printf (MSG_NOTE
, "\n");
217 gcc_assert (stmt_info
);
219 if (STMT_VINFO_RELEVANT_P (stmt_info
))
221 gcc_assert (!STMT_VINFO_VECTYPE (stmt_info
));
222 scalar_type
= TREE_TYPE (PHI_RESULT (phi
));
224 if (dump_enabled_p ())
226 dump_printf_loc (MSG_NOTE
, vect_location
,
227 "get vectype for scalar type: ");
228 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
229 dump_printf (MSG_NOTE
, "\n");
232 vectype
= get_vectype_for_scalar_type (scalar_type
);
235 if (dump_enabled_p ())
237 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
238 "not vectorized: unsupported "
240 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
242 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
246 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
248 if (dump_enabled_p ())
250 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
251 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vectype
);
252 dump_printf (MSG_NOTE
, "\n");
255 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
256 if (dump_enabled_p ())
257 dump_printf_loc (MSG_NOTE
, vect_location
, "nunits = %d\n",
260 if (!vectorization_factor
261 || (nunits
> vectorization_factor
))
262 vectorization_factor
= nunits
;
266 for (gimple_stmt_iterator si
= gsi_start_bb (bb
);
267 !gsi_end_p (si
) || analyze_pattern_stmt
;)
271 if (analyze_pattern_stmt
)
274 stmt
= gsi_stmt (si
);
276 stmt_info
= vinfo_for_stmt (stmt
);
278 if (dump_enabled_p ())
280 dump_printf_loc (MSG_NOTE
, vect_location
,
281 "==> examining statement: ");
282 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
283 dump_printf (MSG_NOTE
, "\n");
286 gcc_assert (stmt_info
);
288 /* Skip stmts which do not need to be vectorized. */
289 if ((!STMT_VINFO_RELEVANT_P (stmt_info
)
290 && !STMT_VINFO_LIVE_P (stmt_info
))
291 || gimple_clobber_p (stmt
))
293 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
294 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
295 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
296 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
299 stmt_info
= vinfo_for_stmt (pattern_stmt
);
300 if (dump_enabled_p ())
302 dump_printf_loc (MSG_NOTE
, vect_location
,
303 "==> examining pattern statement: ");
304 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
305 dump_printf (MSG_NOTE
, "\n");
310 if (dump_enabled_p ())
311 dump_printf_loc (MSG_NOTE
, vect_location
, "skip.\n");
316 else if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
317 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
318 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
319 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
320 analyze_pattern_stmt
= true;
322 /* If a pattern statement has def stmts, analyze them too. */
323 if (is_pattern_stmt_p (stmt_info
))
325 if (pattern_def_seq
== NULL
)
327 pattern_def_seq
= STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
);
328 pattern_def_si
= gsi_start (pattern_def_seq
);
330 else if (!gsi_end_p (pattern_def_si
))
331 gsi_next (&pattern_def_si
);
332 if (pattern_def_seq
!= NULL
)
334 gimple
*pattern_def_stmt
= NULL
;
335 stmt_vec_info pattern_def_stmt_info
= NULL
;
337 while (!gsi_end_p (pattern_def_si
))
339 pattern_def_stmt
= gsi_stmt (pattern_def_si
);
340 pattern_def_stmt_info
341 = vinfo_for_stmt (pattern_def_stmt
);
342 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info
)
343 || STMT_VINFO_LIVE_P (pattern_def_stmt_info
))
345 gsi_next (&pattern_def_si
);
348 if (!gsi_end_p (pattern_def_si
))
350 if (dump_enabled_p ())
352 dump_printf_loc (MSG_NOTE
, vect_location
,
353 "==> examining pattern def stmt: ");
354 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
355 pattern_def_stmt
, 0);
356 dump_printf (MSG_NOTE
, "\n");
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
,
397 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
402 if (VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt
))))
404 if (dump_enabled_p ())
406 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
407 "not vectorized: vector stmt in loop:");
408 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
409 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
416 if (STMT_VINFO_VECTYPE (stmt_info
))
418 /* The only case when a vectype had been already set is for stmts
419 that contain a dataref, or for "pattern-stmts" (stmts
420 generated by the vectorizer to represent/replace a certain
422 gcc_assert (STMT_VINFO_DATA_REF (stmt_info
)
423 || is_pattern_stmt_p (stmt_info
)
424 || !gsi_end_p (pattern_def_si
));
425 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
429 gcc_assert (!STMT_VINFO_DATA_REF (stmt_info
));
430 if (is_gimple_call (stmt
)
431 && gimple_call_internal_p (stmt
)
432 && gimple_call_internal_fn (stmt
) == IFN_MASK_STORE
)
433 scalar_type
= TREE_TYPE (gimple_call_arg (stmt
, 3));
435 scalar_type
= TREE_TYPE (gimple_get_lhs (stmt
));
437 /* Bool ops don't participate in vectorization factor
438 computation. For comparison use compared types to
440 if (TREE_CODE (scalar_type
) == BOOLEAN_TYPE
)
442 if (STMT_VINFO_RELEVANT_P (stmt_info
))
443 mask_producers
.safe_push (stmt_info
);
446 if (gimple_code (stmt
) == GIMPLE_ASSIGN
447 && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt
))
449 && TREE_CODE (TREE_TYPE (gimple_assign_rhs1 (stmt
)))
451 scalar_type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
454 if (!analyze_pattern_stmt
&& gsi_end_p (pattern_def_si
))
456 pattern_def_seq
= NULL
;
463 if (dump_enabled_p ())
465 dump_printf_loc (MSG_NOTE
, vect_location
,
466 "get vectype for scalar type: ");
467 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
468 dump_printf (MSG_NOTE
, "\n");
470 vectype
= get_vectype_for_scalar_type (scalar_type
);
473 if (dump_enabled_p ())
475 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
476 "not vectorized: unsupported "
478 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
480 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
486 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
488 if (dump_enabled_p ())
490 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
491 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vectype
);
492 dump_printf (MSG_NOTE
, "\n");
496 /* Don't try to compute VF out scalar types if we stmt
497 produces boolean vector. Use result vectype instead. */
498 if (VECTOR_BOOLEAN_TYPE_P (vectype
))
499 vf_vectype
= vectype
;
502 /* The vectorization factor is according to the smallest
503 scalar type (or the largest vector size, but we only
504 support one vector size per loop). */
506 scalar_type
= vect_get_smallest_scalar_type (stmt
, &dummy
,
508 if (dump_enabled_p ())
510 dump_printf_loc (MSG_NOTE
, vect_location
,
511 "get vectype for scalar type: ");
512 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
513 dump_printf (MSG_NOTE
, "\n");
515 vf_vectype
= get_vectype_for_scalar_type (scalar_type
);
519 if (dump_enabled_p ())
521 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
522 "not vectorized: unsupported data-type ");
523 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
525 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
530 if ((GET_MODE_SIZE (TYPE_MODE (vectype
))
531 != GET_MODE_SIZE (TYPE_MODE (vf_vectype
))))
533 if (dump_enabled_p ())
535 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
536 "not vectorized: different sized vector "
537 "types in statement, ");
538 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
540 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
541 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
543 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
548 if (dump_enabled_p ())
550 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
551 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vf_vectype
);
552 dump_printf (MSG_NOTE
, "\n");
555 nunits
= TYPE_VECTOR_SUBPARTS (vf_vectype
);
556 if (dump_enabled_p ())
557 dump_printf_loc (MSG_NOTE
, vect_location
, "nunits = %d\n", nunits
);
558 if (!vectorization_factor
559 || (nunits
> vectorization_factor
))
560 vectorization_factor
= nunits
;
562 if (!analyze_pattern_stmt
&& gsi_end_p (pattern_def_si
))
564 pattern_def_seq
= NULL
;
570 /* TODO: Analyze cost. Decide if worth while to vectorize. */
571 if (dump_enabled_p ())
572 dump_printf_loc (MSG_NOTE
, vect_location
, "vectorization factor = %d\n",
573 vectorization_factor
);
574 if (vectorization_factor
<= 1)
576 if (dump_enabled_p ())
577 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
578 "not vectorized: unsupported data-type\n");
581 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
583 for (i
= 0; i
< mask_producers
.length (); i
++)
585 tree mask_type
= NULL
;
587 stmt
= STMT_VINFO_STMT (mask_producers
[i
]);
589 if (gimple_code (stmt
) == GIMPLE_ASSIGN
590 && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt
)) == tcc_comparison
591 && TREE_CODE (TREE_TYPE (gimple_assign_rhs1 (stmt
))) != BOOLEAN_TYPE
)
593 scalar_type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
594 mask_type
= get_mask_type_for_scalar_type (scalar_type
);
598 if (dump_enabled_p ())
599 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
600 "not vectorized: unsupported mask\n");
609 enum vect_def_type dt
;
611 FOR_EACH_SSA_TREE_OPERAND (rhs
, stmt
, iter
, SSA_OP_USE
)
613 if (!vect_is_simple_use (rhs
, mask_producers
[i
]->vinfo
,
614 &def_stmt
, &dt
, &vectype
))
616 if (dump_enabled_p ())
618 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
619 "not vectorized: can't compute mask type "
621 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
,
623 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
628 /* No vectype probably means external definition.
629 Allow it in case there is another operand which
630 allows to determine mask type. */
636 else if (TYPE_VECTOR_SUBPARTS (mask_type
)
637 != TYPE_VECTOR_SUBPARTS (vectype
))
639 if (dump_enabled_p ())
641 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
642 "not vectorized: different sized masks "
643 "types in statement, ");
644 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
646 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
647 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
649 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
653 else if (VECTOR_BOOLEAN_TYPE_P (mask_type
)
654 != VECTOR_BOOLEAN_TYPE_P (vectype
))
656 if (dump_enabled_p ())
658 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
659 "not vectorized: mixed mask and "
660 "nonmask vector types in statement, ");
661 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
663 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
664 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
666 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
672 /* We may compare boolean value loaded as vector of integers.
673 Fix mask_type in such case. */
675 && !VECTOR_BOOLEAN_TYPE_P (mask_type
)
676 && gimple_code (stmt
) == GIMPLE_ASSIGN
677 && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt
)) == tcc_comparison
)
678 mask_type
= build_same_sized_truth_vector_type (mask_type
);
681 /* No mask_type should mean loop invariant predicate.
682 This is probably a subject for optimization in
686 if (dump_enabled_p ())
688 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
689 "not vectorized: can't compute mask type "
691 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
,
693 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
698 STMT_VINFO_VECTYPE (mask_producers
[i
]) = mask_type
;
705 /* Function vect_is_simple_iv_evolution.
707 FORNOW: A simple evolution of an induction variables in the loop is
708 considered a polynomial evolution. */
711 vect_is_simple_iv_evolution (unsigned loop_nb
, tree access_fn
, tree
* init
,
716 tree evolution_part
= evolution_part_in_loop_num (access_fn
, loop_nb
);
719 /* When there is no evolution in this loop, the evolution function
721 if (evolution_part
== NULL_TREE
)
724 /* When the evolution is a polynomial of degree >= 2
725 the evolution function is not "simple". */
726 if (tree_is_chrec (evolution_part
))
729 step_expr
= evolution_part
;
730 init_expr
= unshare_expr (initial_condition_in_loop_num (access_fn
, loop_nb
));
732 if (dump_enabled_p ())
734 dump_printf_loc (MSG_NOTE
, vect_location
, "step: ");
735 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, step_expr
);
736 dump_printf (MSG_NOTE
, ", init: ");
737 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, init_expr
);
738 dump_printf (MSG_NOTE
, "\n");
744 if (TREE_CODE (step_expr
) != INTEGER_CST
745 && (TREE_CODE (step_expr
) != SSA_NAME
746 || ((bb
= gimple_bb (SSA_NAME_DEF_STMT (step_expr
)))
747 && flow_bb_inside_loop_p (get_loop (cfun
, loop_nb
), bb
))
748 || (!INTEGRAL_TYPE_P (TREE_TYPE (step_expr
))
749 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
))
750 || !flag_associative_math
)))
751 && (TREE_CODE (step_expr
) != REAL_CST
752 || !flag_associative_math
))
754 if (dump_enabled_p ())
755 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
763 /* Function vect_analyze_scalar_cycles_1.
765 Examine the cross iteration def-use cycles of scalar variables
766 in LOOP. LOOP_VINFO represents the loop that is now being
767 considered for vectorization (can be LOOP, or an outer-loop
771 vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo
, struct loop
*loop
)
773 basic_block bb
= loop
->header
;
775 auto_vec
<gimple
*, 64> worklist
;
779 if (dump_enabled_p ())
780 dump_printf_loc (MSG_NOTE
, vect_location
,
781 "=== vect_analyze_scalar_cycles ===\n");
783 /* First - identify all inductions. Reduction detection assumes that all the
784 inductions have been identified, therefore, this order must not be
786 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
788 gphi
*phi
= gsi
.phi ();
789 tree access_fn
= NULL
;
790 tree def
= PHI_RESULT (phi
);
791 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (phi
);
793 if (dump_enabled_p ())
795 dump_printf_loc (MSG_NOTE
, vect_location
, "Analyze phi: ");
796 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
797 dump_printf (MSG_NOTE
, "\n");
800 /* Skip virtual phi's. The data dependences that are associated with
801 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
802 if (virtual_operand_p (def
))
805 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_unknown_def_type
;
807 /* Analyze the evolution function. */
808 access_fn
= analyze_scalar_evolution (loop
, def
);
811 STRIP_NOPS (access_fn
);
812 if (dump_enabled_p ())
814 dump_printf_loc (MSG_NOTE
, vect_location
,
815 "Access function of PHI: ");
816 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, access_fn
);
817 dump_printf (MSG_NOTE
, "\n");
819 STMT_VINFO_LOOP_PHI_EVOLUTION_BASE_UNCHANGED (stmt_vinfo
)
820 = initial_condition_in_loop_num (access_fn
, loop
->num
);
821 STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
)
822 = evolution_part_in_loop_num (access_fn
, loop
->num
);
826 || !vect_is_simple_iv_evolution (loop
->num
, access_fn
, &init
, &step
)
827 || (LOOP_VINFO_LOOP (loop_vinfo
) != loop
828 && TREE_CODE (step
) != INTEGER_CST
))
830 worklist
.safe_push (phi
);
834 gcc_assert (STMT_VINFO_LOOP_PHI_EVOLUTION_BASE_UNCHANGED (stmt_vinfo
)
836 gcc_assert (STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
) != NULL_TREE
);
838 if (dump_enabled_p ())
839 dump_printf_loc (MSG_NOTE
, vect_location
, "Detected induction.\n");
840 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_induction_def
;
844 /* Second - identify all reductions and nested cycles. */
845 while (worklist
.length () > 0)
847 gimple
*phi
= worklist
.pop ();
848 tree def
= PHI_RESULT (phi
);
849 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (phi
);
853 if (dump_enabled_p ())
855 dump_printf_loc (MSG_NOTE
, vect_location
, "Analyze phi: ");
856 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
857 dump_printf (MSG_NOTE
, "\n");
860 gcc_assert (!virtual_operand_p (def
)
861 && STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_unknown_def_type
);
863 nested_cycle
= (loop
!= LOOP_VINFO_LOOP (loop_vinfo
));
864 reduc_stmt
= vect_force_simple_reduction (loop_vinfo
, phi
, !nested_cycle
,
865 &double_reduc
, false);
870 if (dump_enabled_p ())
871 dump_printf_loc (MSG_NOTE
, vect_location
,
872 "Detected double reduction.\n");
874 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_double_reduction_def
;
875 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
876 vect_double_reduction_def
;
882 if (dump_enabled_p ())
883 dump_printf_loc (MSG_NOTE
, vect_location
,
884 "Detected vectorizable nested cycle.\n");
886 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_nested_cycle
;
887 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
892 if (dump_enabled_p ())
893 dump_printf_loc (MSG_NOTE
, vect_location
,
894 "Detected reduction.\n");
896 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_reduction_def
;
897 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
899 /* Store the reduction cycles for possible vectorization in
901 LOOP_VINFO_REDUCTIONS (loop_vinfo
).safe_push (reduc_stmt
);
906 if (dump_enabled_p ())
907 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
908 "Unknown def-use cycle pattern.\n");
913 /* Function vect_analyze_scalar_cycles.
915 Examine the cross iteration def-use cycles of scalar variables, by
916 analyzing the loop-header PHIs of scalar variables. Classify each
917 cycle as one of the following: invariant, induction, reduction, unknown.
918 We do that for the loop represented by LOOP_VINFO, and also to its
919 inner-loop, if exists.
920 Examples for scalar cycles:
935 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo
)
937 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
939 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
);
941 /* When vectorizing an outer-loop, the inner-loop is executed sequentially.
942 Reductions in such inner-loop therefore have different properties than
943 the reductions in the nest that gets vectorized:
944 1. When vectorized, they are executed in the same order as in the original
945 scalar loop, so we can't change the order of computation when
947 2. FIXME: Inner-loop reductions can be used in the inner-loop, so the
948 current checks are too strict. */
951 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
->inner
);
954 /* Transfer group and reduction information from STMT to its pattern stmt. */
957 vect_fixup_reduc_chain (gimple
*stmt
)
959 gimple
*firstp
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt
));
961 gcc_assert (!GROUP_FIRST_ELEMENT (vinfo_for_stmt (firstp
))
962 && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)));
963 GROUP_SIZE (vinfo_for_stmt (firstp
)) = GROUP_SIZE (vinfo_for_stmt (stmt
));
966 stmtp
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt
));
967 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmtp
)) = firstp
;
968 stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
));
970 GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmtp
))
971 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt
));
974 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmtp
)) = vect_reduction_def
;
977 /* Fixup scalar cycles that now have their stmts detected as patterns. */
980 vect_fixup_scalar_cycles_with_patterns (loop_vec_info loop_vinfo
)
985 FOR_EACH_VEC_ELT (LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
), i
, first
)
986 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (first
)))
988 vect_fixup_reduc_chain (first
);
989 LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
)[i
]
990 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first
));
994 /* Function vect_get_loop_niters.
996 Determine how many iterations the loop is executed and place it
997 in NUMBER_OF_ITERATIONS. Place the number of latch iterations
998 in NUMBER_OF_ITERATIONSM1.
1000 Return the loop exit condition. */
1004 vect_get_loop_niters (struct loop
*loop
, tree
*number_of_iterations
,
1005 tree
*number_of_iterationsm1
)
1009 if (dump_enabled_p ())
1010 dump_printf_loc (MSG_NOTE
, vect_location
,
1011 "=== get_loop_niters ===\n");
1013 niters
= number_of_latch_executions (loop
);
1014 *number_of_iterationsm1
= niters
;
1016 /* We want the number of loop header executions which is the number
1017 of latch executions plus one.
1018 ??? For UINT_MAX latch executions this number overflows to zero
1019 for loops like do { n++; } while (n != 0); */
1020 if (niters
&& !chrec_contains_undetermined (niters
))
1021 niters
= fold_build2 (PLUS_EXPR
, TREE_TYPE (niters
), unshare_expr (niters
),
1022 build_int_cst (TREE_TYPE (niters
), 1));
1023 *number_of_iterations
= niters
;
1025 return get_loop_exit_condition (loop
);
1029 /* Function bb_in_loop_p
1031 Used as predicate for dfs order traversal of the loop bbs. */
1034 bb_in_loop_p (const_basic_block bb
, const void *data
)
1036 const struct loop
*const loop
= (const struct loop
*)data
;
1037 if (flow_bb_inside_loop_p (loop
, bb
))
1043 /* Function new_loop_vec_info.
1045 Create and initialize a new loop_vec_info struct for LOOP, as well as
1046 stmt_vec_info structs for all the stmts in LOOP. */
1048 static loop_vec_info
1049 new_loop_vec_info (struct loop
*loop
)
1053 gimple_stmt_iterator si
;
1054 unsigned int i
, nbbs
;
1056 res
= (loop_vec_info
) xcalloc (1, sizeof (struct _loop_vec_info
));
1057 res
->kind
= vec_info::loop
;
1058 LOOP_VINFO_LOOP (res
) = loop
;
1060 bbs
= get_loop_body (loop
);
1062 /* Create/Update stmt_info for all stmts in the loop. */
1063 for (i
= 0; i
< loop
->num_nodes
; i
++)
1065 basic_block bb
= bbs
[i
];
1067 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
1069 gimple
*phi
= gsi_stmt (si
);
1070 gimple_set_uid (phi
, 0);
1071 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, res
));
1074 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1076 gimple
*stmt
= gsi_stmt (si
);
1077 gimple_set_uid (stmt
, 0);
1078 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, res
));
1082 /* CHECKME: We want to visit all BBs before their successors (except for
1083 latch blocks, for which this assertion wouldn't hold). In the simple
1084 case of the loop forms we allow, a dfs order of the BBs would the same
1085 as reversed postorder traversal, so we are safe. */
1088 bbs
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1089 nbbs
= dfs_enumerate_from (loop
->header
, 0, bb_in_loop_p
,
1090 bbs
, loop
->num_nodes
, loop
);
1091 gcc_assert (nbbs
== loop
->num_nodes
);
1093 LOOP_VINFO_BBS (res
) = bbs
;
1094 LOOP_VINFO_NITERSM1 (res
) = NULL
;
1095 LOOP_VINFO_NITERS (res
) = NULL
;
1096 LOOP_VINFO_NITERS_UNCHANGED (res
) = NULL
;
1097 LOOP_VINFO_COST_MODEL_THRESHOLD (res
) = 0;
1098 LOOP_VINFO_VECTORIZABLE_P (res
) = 0;
1099 LOOP_VINFO_PEELING_FOR_ALIGNMENT (res
) = 0;
1100 LOOP_VINFO_VECT_FACTOR (res
) = 0;
1101 LOOP_VINFO_LOOP_NEST (res
) = vNULL
;
1102 LOOP_VINFO_DATAREFS (res
) = vNULL
;
1103 LOOP_VINFO_DDRS (res
) = vNULL
;
1104 LOOP_VINFO_UNALIGNED_DR (res
) = NULL
;
1105 LOOP_VINFO_MAY_MISALIGN_STMTS (res
) = vNULL
;
1106 LOOP_VINFO_MAY_ALIAS_DDRS (res
) = vNULL
;
1107 LOOP_VINFO_GROUPED_STORES (res
) = vNULL
;
1108 LOOP_VINFO_REDUCTIONS (res
) = vNULL
;
1109 LOOP_VINFO_REDUCTION_CHAINS (res
) = vNULL
;
1110 LOOP_VINFO_SLP_INSTANCES (res
) = vNULL
;
1111 LOOP_VINFO_SLP_UNROLLING_FACTOR (res
) = 1;
1112 LOOP_VINFO_TARGET_COST_DATA (res
) = init_cost (loop
);
1113 LOOP_VINFO_PEELING_FOR_GAPS (res
) = false;
1114 LOOP_VINFO_PEELING_FOR_NITER (res
) = false;
1115 LOOP_VINFO_OPERANDS_SWAPPED (res
) = false;
1121 /* Function destroy_loop_vec_info.
1123 Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
1124 stmts in the loop. */
1127 destroy_loop_vec_info (loop_vec_info loop_vinfo
, bool clean_stmts
)
1132 gimple_stmt_iterator si
;
1134 vec
<slp_instance
> slp_instances
;
1135 slp_instance instance
;
1141 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1143 bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1144 nbbs
= clean_stmts
? loop
->num_nodes
: 0;
1145 swapped
= LOOP_VINFO_OPERANDS_SWAPPED (loop_vinfo
);
1147 for (j
= 0; j
< nbbs
; j
++)
1149 basic_block bb
= bbs
[j
];
1150 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
1151 free_stmt_vec_info (gsi_stmt (si
));
1153 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); )
1155 gimple
*stmt
= gsi_stmt (si
);
1157 /* We may have broken canonical form by moving a constant
1158 into RHS1 of a commutative op. Fix such occurrences. */
1159 if (swapped
&& is_gimple_assign (stmt
))
1161 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1163 if ((code
== PLUS_EXPR
1164 || code
== POINTER_PLUS_EXPR
1165 || code
== MULT_EXPR
)
1166 && CONSTANT_CLASS_P (gimple_assign_rhs1 (stmt
)))
1167 swap_ssa_operands (stmt
,
1168 gimple_assign_rhs1_ptr (stmt
),
1169 gimple_assign_rhs2_ptr (stmt
));
1172 /* Free stmt_vec_info. */
1173 free_stmt_vec_info (stmt
);
1178 free (LOOP_VINFO_BBS (loop_vinfo
));
1179 vect_destroy_datarefs (loop_vinfo
);
1180 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo
));
1181 LOOP_VINFO_LOOP_NEST (loop_vinfo
).release ();
1182 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).release ();
1183 LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo
).release ();
1184 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
).release ();
1185 slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
1186 FOR_EACH_VEC_ELT (slp_instances
, j
, instance
)
1187 vect_free_slp_instance (instance
);
1189 LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).release ();
1190 LOOP_VINFO_GROUPED_STORES (loop_vinfo
).release ();
1191 LOOP_VINFO_REDUCTIONS (loop_vinfo
).release ();
1192 LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
).release ();
1194 destroy_cost_data (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
));
1195 loop_vinfo
->scalar_cost_vec
.release ();
1202 /* Calculate the cost of one scalar iteration of the loop. */
1204 vect_compute_single_scalar_iteration_cost (loop_vec_info loop_vinfo
)
1206 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1207 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1208 int nbbs
= loop
->num_nodes
, factor
, scalar_single_iter_cost
= 0;
1209 int innerloop_iters
, i
;
1211 /* Count statements in scalar loop. Using this as scalar cost for a single
1214 TODO: Add outer loop support.
1216 TODO: Consider assigning different costs to different scalar
1220 innerloop_iters
= 1;
1222 innerloop_iters
= 50; /* FIXME */
1224 for (i
= 0; i
< nbbs
; i
++)
1226 gimple_stmt_iterator si
;
1227 basic_block bb
= bbs
[i
];
1229 if (bb
->loop_father
== loop
->inner
)
1230 factor
= innerloop_iters
;
1234 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1236 gimple
*stmt
= gsi_stmt (si
);
1237 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1239 if (!is_gimple_assign (stmt
) && !is_gimple_call (stmt
))
1242 /* Skip stmts that are not vectorized inside the loop. */
1244 && !STMT_VINFO_RELEVANT_P (stmt_info
)
1245 && (!STMT_VINFO_LIVE_P (stmt_info
)
1246 || !VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
1247 && !STMT_VINFO_IN_PATTERN_P (stmt_info
))
1250 vect_cost_for_stmt kind
;
1251 if (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
)))
1253 if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))))
1256 kind
= scalar_store
;
1261 scalar_single_iter_cost
1262 += record_stmt_cost (&LOOP_VINFO_SCALAR_ITERATION_COST (loop_vinfo
),
1263 factor
, kind
, NULL
, 0, vect_prologue
);
1266 LOOP_VINFO_SINGLE_SCALAR_ITERATION_COST (loop_vinfo
)
1267 = scalar_single_iter_cost
;
1271 /* Function vect_analyze_loop_form_1.
1273 Verify that certain CFG restrictions hold, including:
1274 - the loop has a pre-header
1275 - the loop has a single entry and exit
1276 - the loop exit condition is simple enough, and the number of iterations
1277 can be analyzed (a countable loop). */
1280 vect_analyze_loop_form_1 (struct loop
*loop
, gcond
**loop_cond
,
1281 tree
*number_of_iterationsm1
,
1282 tree
*number_of_iterations
, gcond
**inner_loop_cond
)
1284 if (dump_enabled_p ())
1285 dump_printf_loc (MSG_NOTE
, vect_location
,
1286 "=== vect_analyze_loop_form ===\n");
1288 /* Different restrictions apply when we are considering an inner-most loop,
1289 vs. an outer (nested) loop.
1290 (FORNOW. May want to relax some of these restrictions in the future). */
1294 /* Inner-most loop. We currently require that the number of BBs is
1295 exactly 2 (the header and latch). Vectorizable inner-most loops
1306 if (loop
->num_nodes
!= 2)
1308 if (dump_enabled_p ())
1309 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1310 "not vectorized: control flow in loop.\n");
1314 if (empty_block_p (loop
->header
))
1316 if (dump_enabled_p ())
1317 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1318 "not vectorized: empty loop.\n");
1324 struct loop
*innerloop
= loop
->inner
;
1327 /* Nested loop. We currently require that the loop is doubly-nested,
1328 contains a single inner loop, and the number of BBs is exactly 5.
1329 Vectorizable outer-loops look like this:
1341 The inner-loop has the properties expected of inner-most loops
1342 as described above. */
1344 if ((loop
->inner
)->inner
|| (loop
->inner
)->next
)
1346 if (dump_enabled_p ())
1347 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1348 "not vectorized: multiple nested loops.\n");
1352 if (loop
->num_nodes
!= 5)
1354 if (dump_enabled_p ())
1355 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1356 "not vectorized: control flow in loop.\n");
1360 entryedge
= loop_preheader_edge (innerloop
);
1361 if (entryedge
->src
!= loop
->header
1362 || !single_exit (innerloop
)
1363 || single_exit (innerloop
)->dest
!= EDGE_PRED (loop
->latch
, 0)->src
)
1365 if (dump_enabled_p ())
1366 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1367 "not vectorized: unsupported outerloop form.\n");
1371 /* Analyze the inner-loop. */
1372 tree inner_niterm1
, inner_niter
;
1373 if (! vect_analyze_loop_form_1 (loop
->inner
, inner_loop_cond
,
1374 &inner_niterm1
, &inner_niter
, NULL
))
1376 if (dump_enabled_p ())
1377 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1378 "not vectorized: Bad inner loop.\n");
1382 if (!expr_invariant_in_loop_p (loop
, inner_niter
))
1384 if (dump_enabled_p ())
1385 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1386 "not vectorized: inner-loop count not"
1391 if (dump_enabled_p ())
1392 dump_printf_loc (MSG_NOTE
, vect_location
,
1393 "Considering outer-loop vectorization.\n");
1396 if (!single_exit (loop
)
1397 || EDGE_COUNT (loop
->header
->preds
) != 2)
1399 if (dump_enabled_p ())
1401 if (!single_exit (loop
))
1402 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1403 "not vectorized: multiple exits.\n");
1404 else if (EDGE_COUNT (loop
->header
->preds
) != 2)
1405 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1406 "not vectorized: too many incoming edges.\n");
1411 /* We assume that the loop exit condition is at the end of the loop. i.e,
1412 that the loop is represented as a do-while (with a proper if-guard
1413 before the loop if needed), where the loop header contains all the
1414 executable statements, and the latch is empty. */
1415 if (!empty_block_p (loop
->latch
)
1416 || !gimple_seq_empty_p (phi_nodes (loop
->latch
)))
1418 if (dump_enabled_p ())
1419 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1420 "not vectorized: latch block not empty.\n");
1424 /* Make sure there exists a single-predecessor exit bb: */
1425 if (!single_pred_p (single_exit (loop
)->dest
))
1427 edge e
= single_exit (loop
);
1428 if (!(e
->flags
& EDGE_ABNORMAL
))
1430 split_loop_exit_edge (e
);
1431 if (dump_enabled_p ())
1432 dump_printf (MSG_NOTE
, "split exit edge.\n");
1436 if (dump_enabled_p ())
1437 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1438 "not vectorized: abnormal loop exit edge.\n");
1443 *loop_cond
= vect_get_loop_niters (loop
, number_of_iterations
,
1444 number_of_iterationsm1
);
1447 if (dump_enabled_p ())
1448 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1449 "not vectorized: complicated exit condition.\n");
1453 if (!*number_of_iterations
1454 || chrec_contains_undetermined (*number_of_iterations
))
1456 if (dump_enabled_p ())
1457 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1458 "not vectorized: number of iterations cannot be "
1463 if (integer_zerop (*number_of_iterations
))
1465 if (dump_enabled_p ())
1466 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1467 "not vectorized: number of iterations = 0.\n");
1474 /* Analyze LOOP form and return a loop_vec_info if it is of suitable form. */
1477 vect_analyze_loop_form (struct loop
*loop
)
1479 tree number_of_iterations
, number_of_iterationsm1
;
1480 gcond
*loop_cond
, *inner_loop_cond
= NULL
;
1482 if (! vect_analyze_loop_form_1 (loop
, &loop_cond
, &number_of_iterationsm1
,
1483 &number_of_iterations
, &inner_loop_cond
))
1486 loop_vec_info loop_vinfo
= new_loop_vec_info (loop
);
1487 LOOP_VINFO_NITERSM1 (loop_vinfo
) = number_of_iterationsm1
;
1488 LOOP_VINFO_NITERS (loop_vinfo
) = number_of_iterations
;
1489 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo
) = number_of_iterations
;
1491 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
1493 if (dump_enabled_p ())
1495 dump_printf_loc (MSG_NOTE
, vect_location
,
1496 "Symbolic number of iterations is ");
1497 dump_generic_expr (MSG_NOTE
, TDF_DETAILS
, number_of_iterations
);
1498 dump_printf (MSG_NOTE
, "\n");
1502 STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond
)) = loop_exit_ctrl_vec_info_type
;
1503 if (inner_loop_cond
)
1504 STMT_VINFO_TYPE (vinfo_for_stmt (inner_loop_cond
))
1505 = loop_exit_ctrl_vec_info_type
;
1507 gcc_assert (!loop
->aux
);
1508 loop
->aux
= loop_vinfo
;
1514 /* Scan the loop stmts and dependent on whether there are any (non-)SLP
1515 statements update the vectorization factor. */
1518 vect_update_vf_for_slp (loop_vec_info loop_vinfo
)
1520 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1521 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1522 int nbbs
= loop
->num_nodes
;
1523 unsigned int vectorization_factor
;
1526 if (dump_enabled_p ())
1527 dump_printf_loc (MSG_NOTE
, vect_location
,
1528 "=== vect_update_vf_for_slp ===\n");
1530 vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1531 gcc_assert (vectorization_factor
!= 0);
1533 /* If all the stmts in the loop can be SLPed, we perform only SLP, and
1534 vectorization factor of the loop is the unrolling factor required by
1535 the SLP instances. If that unrolling factor is 1, we say, that we
1536 perform pure SLP on loop - cross iteration parallelism is not
1538 bool only_slp_in_loop
= true;
1539 for (i
= 0; i
< nbbs
; i
++)
1541 basic_block bb
= bbs
[i
];
1542 for (gimple_stmt_iterator si
= gsi_start_bb (bb
); !gsi_end_p (si
);
1545 gimple
*stmt
= gsi_stmt (si
);
1546 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1547 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
1548 && STMT_VINFO_RELATED_STMT (stmt_info
))
1550 stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
1551 stmt_info
= vinfo_for_stmt (stmt
);
1553 if ((STMT_VINFO_RELEVANT_P (stmt_info
)
1554 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
1555 && !PURE_SLP_STMT (stmt_info
))
1556 /* STMT needs both SLP and loop-based vectorization. */
1557 only_slp_in_loop
= false;
1561 if (only_slp_in_loop
)
1562 vectorization_factor
= LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
);
1564 vectorization_factor
1565 = least_common_multiple (vectorization_factor
,
1566 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
));
1568 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
1569 if (dump_enabled_p ())
1570 dump_printf_loc (MSG_NOTE
, vect_location
,
1571 "Updating vectorization factor to %d\n",
1572 vectorization_factor
);
1575 /* Function vect_analyze_loop_operations.
1577 Scan the loop stmts and make sure they are all vectorizable. */
1580 vect_analyze_loop_operations (loop_vec_info loop_vinfo
)
1582 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1583 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1584 int nbbs
= loop
->num_nodes
;
1586 stmt_vec_info stmt_info
;
1587 bool need_to_vectorize
= false;
1590 if (dump_enabled_p ())
1591 dump_printf_loc (MSG_NOTE
, vect_location
,
1592 "=== vect_analyze_loop_operations ===\n");
1594 for (i
= 0; i
< nbbs
; i
++)
1596 basic_block bb
= bbs
[i
];
1598 for (gphi_iterator si
= gsi_start_phis (bb
); !gsi_end_p (si
);
1601 gphi
*phi
= si
.phi ();
1604 stmt_info
= vinfo_for_stmt (phi
);
1605 if (dump_enabled_p ())
1607 dump_printf_loc (MSG_NOTE
, vect_location
, "examining phi: ");
1608 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
1609 dump_printf (MSG_NOTE
, "\n");
1611 if (virtual_operand_p (gimple_phi_result (phi
)))
1614 /* Inner-loop loop-closed exit phi in outer-loop vectorization
1615 (i.e., a phi in the tail of the outer-loop). */
1616 if (! is_loop_header_bb_p (bb
))
1618 /* FORNOW: we currently don't support the case that these phis
1619 are not used in the outerloop (unless it is double reduction,
1620 i.e., this phi is vect_reduction_def), cause this case
1621 requires to actually do something here. */
1622 if ((!STMT_VINFO_RELEVANT_P (stmt_info
)
1623 || STMT_VINFO_LIVE_P (stmt_info
))
1624 && STMT_VINFO_DEF_TYPE (stmt_info
)
1625 != vect_double_reduction_def
)
1627 if (dump_enabled_p ())
1628 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1629 "Unsupported loop-closed phi in "
1634 /* If PHI is used in the outer loop, we check that its operand
1635 is defined in the inner loop. */
1636 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1639 gimple
*op_def_stmt
;
1641 if (gimple_phi_num_args (phi
) != 1)
1644 phi_op
= PHI_ARG_DEF (phi
, 0);
1645 if (TREE_CODE (phi_op
) != SSA_NAME
)
1648 op_def_stmt
= SSA_NAME_DEF_STMT (phi_op
);
1649 if (gimple_nop_p (op_def_stmt
)
1650 || !flow_bb_inside_loop_p (loop
, gimple_bb (op_def_stmt
))
1651 || !vinfo_for_stmt (op_def_stmt
))
1654 if (STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1655 != vect_used_in_outer
1656 && STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1657 != vect_used_in_outer_by_reduction
)
1664 gcc_assert (stmt_info
);
1666 if (STMT_VINFO_LIVE_P (stmt_info
))
1668 /* FORNOW: not yet supported. */
1669 if (dump_enabled_p ())
1670 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1671 "not vectorized: value used after loop.\n");
1675 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
1676 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_induction_def
)
1678 /* A scalar-dependence cycle that we don't support. */
1679 if (dump_enabled_p ())
1680 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1681 "not vectorized: scalar dependence cycle.\n");
1685 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1687 need_to_vectorize
= true;
1688 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
1689 ok
= vectorizable_induction (phi
, NULL
, NULL
);
1694 if (dump_enabled_p ())
1696 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1697 "not vectorized: relevant phi not "
1699 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, phi
, 0);
1700 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1706 for (gimple_stmt_iterator si
= gsi_start_bb (bb
); !gsi_end_p (si
);
1709 gimple
*stmt
= gsi_stmt (si
);
1710 if (!gimple_clobber_p (stmt
)
1711 && !vect_analyze_stmt (stmt
, &need_to_vectorize
, NULL
))
1716 /* All operations in the loop are either irrelevant (deal with loop
1717 control, or dead), or only used outside the loop and can be moved
1718 out of the loop (e.g. invariants, inductions). The loop can be
1719 optimized away by scalar optimizations. We're better off not
1720 touching this loop. */
1721 if (!need_to_vectorize
)
1723 if (dump_enabled_p ())
1724 dump_printf_loc (MSG_NOTE
, vect_location
,
1725 "All the computation can be taken out of the loop.\n");
1726 if (dump_enabled_p ())
1727 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1728 "not vectorized: redundant loop. no profit to "
1737 /* Function vect_analyze_loop_2.
1739 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1740 for it. The different analyses will record information in the
1741 loop_vec_info struct. */
1743 vect_analyze_loop_2 (loop_vec_info loop_vinfo
, bool &fatal
)
1746 int max_vf
= MAX_VECTORIZATION_FACTOR
;
1748 unsigned int n_stmts
= 0;
1750 /* The first group of checks is independent of the vector size. */
1753 /* Find all data references in the loop (which correspond to vdefs/vuses)
1754 and analyze their evolution in the loop. */
1756 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1758 loop_p loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1759 if (!find_loop_nest (loop
, &LOOP_VINFO_LOOP_NEST (loop_vinfo
)))
1761 if (dump_enabled_p ())
1762 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1763 "not vectorized: loop contains function calls"
1764 " or data references that cannot be analyzed\n");
1768 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
1769 for (gimple_stmt_iterator gsi
= gsi_start_bb (bbs
[i
]);
1770 !gsi_end_p (gsi
); gsi_next (&gsi
))
1772 gimple
*stmt
= gsi_stmt (gsi
);
1773 if (is_gimple_debug (stmt
))
1776 if (!find_data_references_in_stmt (loop
, stmt
,
1777 &LOOP_VINFO_DATAREFS (loop_vinfo
)))
1779 if (is_gimple_call (stmt
) && loop
->safelen
)
1781 tree fndecl
= gimple_call_fndecl (stmt
), op
;
1782 if (fndecl
!= NULL_TREE
)
1784 cgraph_node
*node
= cgraph_node::get (fndecl
);
1785 if (node
!= NULL
&& node
->simd_clones
!= NULL
)
1787 unsigned int j
, n
= gimple_call_num_args (stmt
);
1788 for (j
= 0; j
< n
; j
++)
1790 op
= gimple_call_arg (stmt
, j
);
1792 || (REFERENCE_CLASS_P (op
)
1793 && get_base_address (op
)))
1796 op
= gimple_call_lhs (stmt
);
1797 /* Ignore #pragma omp declare simd functions
1798 if they don't have data references in the
1799 call stmt itself. */
1803 || (REFERENCE_CLASS_P (op
)
1804 && get_base_address (op
)))))
1809 if (dump_enabled_p ())
1810 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1811 "not vectorized: loop contains function "
1812 "calls or data references that cannot "
1818 /* Analyze the data references and also adjust the minimal
1819 vectorization factor according to the loads and stores. */
1821 ok
= vect_analyze_data_refs (loop_vinfo
, &min_vf
);
1824 if (dump_enabled_p ())
1825 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1826 "bad data references.\n");
1830 /* Classify all cross-iteration scalar data-flow cycles.
1831 Cross-iteration cycles caused by virtual phis are analyzed separately. */
1832 vect_analyze_scalar_cycles (loop_vinfo
);
1834 vect_pattern_recog (loop_vinfo
);
1836 vect_fixup_scalar_cycles_with_patterns (loop_vinfo
);
1838 /* Analyze the access patterns of the data-refs in the loop (consecutive,
1839 complex, etc.). FORNOW: Only handle consecutive access pattern. */
1841 ok
= vect_analyze_data_ref_accesses (loop_vinfo
);
1844 if (dump_enabled_p ())
1845 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1846 "bad data access.\n");
1850 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
1852 ok
= vect_mark_stmts_to_be_vectorized (loop_vinfo
);
1855 if (dump_enabled_p ())
1856 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1857 "unexpected pattern.\n");
1861 /* While the rest of the analysis below depends on it in some way. */
1864 /* Analyze data dependences between the data-refs in the loop
1865 and adjust the maximum vectorization factor according to
1867 FORNOW: fail at the first data dependence that we encounter. */
1869 ok
= vect_analyze_data_ref_dependences (loop_vinfo
, &max_vf
);
1873 if (dump_enabled_p ())
1874 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1875 "bad data dependence.\n");
1879 ok
= vect_determine_vectorization_factor (loop_vinfo
);
1882 if (dump_enabled_p ())
1883 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1884 "can't determine vectorization factor.\n");
1887 if (max_vf
< LOOP_VINFO_VECT_FACTOR (loop_vinfo
))
1889 if (dump_enabled_p ())
1890 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1891 "bad data dependence.\n");
1895 /* Compute the scalar iteration cost. */
1896 vect_compute_single_scalar_iteration_cost (loop_vinfo
);
1898 int saved_vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1899 HOST_WIDE_INT estimated_niter
;
1901 int min_scalar_loop_bound
;
1903 /* Check the SLP opportunities in the loop, analyze and build SLP trees. */
1904 ok
= vect_analyze_slp (loop_vinfo
, n_stmts
);
1908 /* If there are any SLP instances mark them as pure_slp. */
1909 bool slp
= vect_make_slp_decision (loop_vinfo
);
1912 /* Find stmts that need to be both vectorized and SLPed. */
1913 vect_detect_hybrid_slp (loop_vinfo
);
1915 /* Update the vectorization factor based on the SLP decision. */
1916 vect_update_vf_for_slp (loop_vinfo
);
1919 /* This is the point where we can re-start analysis with SLP forced off. */
1922 /* Now the vectorization factor is final. */
1923 unsigned vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1924 gcc_assert (vectorization_factor
!= 0);
1926 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
) && dump_enabled_p ())
1927 dump_printf_loc (MSG_NOTE
, vect_location
,
1928 "vectorization_factor = %d, niters = "
1929 HOST_WIDE_INT_PRINT_DEC
"\n", vectorization_factor
,
1930 LOOP_VINFO_INT_NITERS (loop_vinfo
));
1932 HOST_WIDE_INT max_niter
1933 = max_stmt_executions_int (LOOP_VINFO_LOOP (loop_vinfo
));
1934 if ((LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1935 && (LOOP_VINFO_INT_NITERS (loop_vinfo
) < vectorization_factor
))
1937 && (unsigned HOST_WIDE_INT
) max_niter
< vectorization_factor
))
1939 if (dump_enabled_p ())
1940 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1941 "not vectorized: iteration count smaller than "
1942 "vectorization factor.\n");
1946 /* Analyze the alignment of the data-refs in the loop.
1947 Fail if a data reference is found that cannot be vectorized. */
1949 ok
= vect_analyze_data_refs_alignment (loop_vinfo
);
1952 if (dump_enabled_p ())
1953 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1954 "bad data alignment.\n");
1958 /* Prune the list of ddrs to be tested at run-time by versioning for alias.
1959 It is important to call pruning after vect_analyze_data_ref_accesses,
1960 since we use grouping information gathered by interleaving analysis. */
1961 ok
= vect_prune_runtime_alias_test_list (loop_vinfo
);
1964 if (dump_enabled_p ())
1965 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1966 "number of versioning for alias "
1967 "run-time tests exceeds %d "
1968 "(--param vect-max-version-for-alias-checks)\n",
1969 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS
));
1973 /* This pass will decide on using loop versioning and/or loop peeling in
1974 order to enhance the alignment of data references in the loop. */
1975 ok
= vect_enhance_data_refs_alignment (loop_vinfo
);
1978 if (dump_enabled_p ())
1979 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1980 "bad data alignment.\n");
1986 /* Analyze operations in the SLP instances. Note this may
1987 remove unsupported SLP instances which makes the above
1988 SLP kind detection invalid. */
1989 unsigned old_size
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).length ();
1990 vect_slp_analyze_operations (LOOP_VINFO_SLP_INSTANCES (loop_vinfo
),
1991 LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
));
1992 if (LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).length () != old_size
)
1996 /* Scan all the remaining operations in the loop that are not subject
1997 to SLP and make sure they are vectorizable. */
1998 ok
= vect_analyze_loop_operations (loop_vinfo
);
2001 if (dump_enabled_p ())
2002 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2003 "bad operation or unsupported loop bound.\n");
2007 /* Analyze cost. Decide if worth while to vectorize. */
2008 int min_profitable_estimate
, min_profitable_iters
;
2009 vect_estimate_min_profitable_iters (loop_vinfo
, &min_profitable_iters
,
2010 &min_profitable_estimate
);
2012 if (min_profitable_iters
< 0)
2014 if (dump_enabled_p ())
2015 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2016 "not vectorized: vectorization not profitable.\n");
2017 if (dump_enabled_p ())
2018 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2019 "not vectorized: vector version will never be "
2024 min_scalar_loop_bound
= ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND
)
2025 * vectorization_factor
) - 1);
2027 /* Use the cost model only if it is more conservative than user specified
2029 th
= (unsigned) min_scalar_loop_bound
;
2030 if (min_profitable_iters
2031 && (!min_scalar_loop_bound
2032 || min_profitable_iters
> min_scalar_loop_bound
))
2033 th
= (unsigned) min_profitable_iters
;
2035 LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo
) = th
;
2037 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
2038 && LOOP_VINFO_INT_NITERS (loop_vinfo
) <= th
)
2040 if (dump_enabled_p ())
2041 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2042 "not vectorized: vectorization not profitable.\n");
2043 if (dump_enabled_p ())
2044 dump_printf_loc (MSG_NOTE
, vect_location
,
2045 "not vectorized: iteration count smaller than user "
2046 "specified loop bound parameter or minimum profitable "
2047 "iterations (whichever is more conservative).\n");
2052 = estimated_stmt_executions_int (LOOP_VINFO_LOOP (loop_vinfo
));
2053 if (estimated_niter
!= -1
2054 && ((unsigned HOST_WIDE_INT
) estimated_niter
2055 <= MAX (th
, (unsigned)min_profitable_estimate
)))
2057 if (dump_enabled_p ())
2058 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2059 "not vectorized: estimated iteration count too "
2061 if (dump_enabled_p ())
2062 dump_printf_loc (MSG_NOTE
, vect_location
,
2063 "not vectorized: estimated iteration count smaller "
2064 "than specified loop bound parameter or minimum "
2065 "profitable iterations (whichever is more "
2066 "conservative).\n");
2070 /* Decide whether we need to create an epilogue loop to handle
2071 remaining scalar iterations. */
2072 th
= ((LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo
) + 1)
2073 / LOOP_VINFO_VECT_FACTOR (loop_vinfo
))
2074 * LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2076 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
2077 && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
) > 0)
2079 if (ctz_hwi (LOOP_VINFO_INT_NITERS (loop_vinfo
)
2080 - LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
))
2081 < exact_log2 (LOOP_VINFO_VECT_FACTOR (loop_vinfo
)))
2082 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
) = true;
2084 else if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
)
2085 || (tree_ctz (LOOP_VINFO_NITERS (loop_vinfo
))
2086 < (unsigned)exact_log2 (LOOP_VINFO_VECT_FACTOR (loop_vinfo
))
2087 /* In case of versioning, check if the maximum number of
2088 iterations is greater than th. If they are identical,
2089 the epilogue is unnecessary. */
2090 && ((!LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
)
2091 && !LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
))
2092 || (unsigned HOST_WIDE_INT
) max_niter
> th
)))
2093 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
) = true;
2095 /* If an epilogue loop is required make sure we can create one. */
2096 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
2097 || LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
))
2099 if (dump_enabled_p ())
2100 dump_printf_loc (MSG_NOTE
, vect_location
, "epilog loop required\n");
2101 if (!vect_can_advance_ivs_p (loop_vinfo
)
2102 || !slpeel_can_duplicate_loop_p (LOOP_VINFO_LOOP (loop_vinfo
),
2103 single_exit (LOOP_VINFO_LOOP
2106 if (dump_enabled_p ())
2107 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2108 "not vectorized: can't create required "
2114 gcc_assert (vectorization_factor
2115 == (unsigned)LOOP_VINFO_VECT_FACTOR (loop_vinfo
));
2117 /* Ok to vectorize! */
2121 /* Try again with SLP forced off but if we didn't do any SLP there is
2122 no point in re-trying. */
2126 /* Likewise if the grouped loads or stores in the SLP cannot be handled
2127 via interleaving or lane instructions or if there were any SLP
2129 slp_instance instance
;
2132 FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (loop_vinfo
), i
, instance
)
2134 stmt_vec_info vinfo
;
2135 vinfo
= vinfo_for_stmt
2136 (SLP_TREE_SCALAR_STMTS (SLP_INSTANCE_TREE (instance
))[0]);
2137 if (! STMT_VINFO_GROUPED_ACCESS (vinfo
))
2139 vinfo
= vinfo_for_stmt (STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo
));
2140 unsigned int size
= STMT_VINFO_GROUP_SIZE (vinfo
);
2141 tree vectype
= STMT_VINFO_VECTYPE (vinfo
);
2142 if (! vect_store_lanes_supported (vectype
, size
)
2143 && ! vect_grouped_store_supported (vectype
, size
))
2145 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (instance
), j
, node
)
2147 vinfo
= vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (node
)[0]);
2148 vinfo
= vinfo_for_stmt (STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo
));
2149 size
= STMT_VINFO_GROUP_SIZE (vinfo
);
2150 vectype
= STMT_VINFO_VECTYPE (vinfo
);
2151 if (! vect_load_lanes_supported (vectype
, size
)
2152 && ! vect_grouped_load_supported (vectype
, size
))
2157 if (dump_enabled_p ())
2158 dump_printf_loc (MSG_NOTE
, vect_location
,
2159 "re-trying with SLP disabled\n");
2161 /* Roll back state appropriately. No SLP this time. */
2163 /* Restore vectorization factor as it were without SLP. */
2164 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = saved_vectorization_factor
;
2165 /* Free the SLP instances. */
2166 FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (loop_vinfo
), j
, instance
)
2167 vect_free_slp_instance (instance
);
2168 LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).release ();
2169 /* Reset SLP type to loop_vect on all stmts. */
2170 for (i
= 0; i
< LOOP_VINFO_LOOP (loop_vinfo
)->num_nodes
; ++i
)
2172 basic_block bb
= LOOP_VINFO_BBS (loop_vinfo
)[i
];
2173 for (gimple_stmt_iterator si
= gsi_start_bb (bb
);
2174 !gsi_end_p (si
); gsi_next (&si
))
2176 stmt_vec_info stmt_info
= vinfo_for_stmt (gsi_stmt (si
));
2177 if (STMT_VINFO_IN_PATTERN_P (stmt_info
))
2179 gcc_assert (STMT_SLP_TYPE (stmt_info
) == loop_vect
);
2180 stmt_info
= vinfo_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info
));
2182 STMT_SLP_TYPE (stmt_info
) = loop_vect
;
2185 /* Free optimized alias test DDRS. */
2186 LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo
).release ();
2187 /* Reset target cost data. */
2188 destroy_cost_data (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
));
2189 LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
)
2190 = init_cost (LOOP_VINFO_LOOP (loop_vinfo
));
2191 /* Reset assorted flags. */
2192 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
) = false;
2193 LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) = false;
2194 LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo
) = 0;
2199 /* Function vect_analyze_loop.
2201 Apply a set of analyses on LOOP, and create a loop_vec_info struct
2202 for it. The different analyses will record information in the
2203 loop_vec_info struct. */
2205 vect_analyze_loop (struct loop
*loop
)
2207 loop_vec_info loop_vinfo
;
2208 unsigned int vector_sizes
;
2210 /* Autodetect first vector size we try. */
2211 current_vector_size
= 0;
2212 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
2214 if (dump_enabled_p ())
2215 dump_printf_loc (MSG_NOTE
, vect_location
,
2216 "===== analyze_loop_nest =====\n");
2218 if (loop_outer (loop
)
2219 && loop_vec_info_for_loop (loop_outer (loop
))
2220 && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop
))))
2222 if (dump_enabled_p ())
2223 dump_printf_loc (MSG_NOTE
, vect_location
,
2224 "outer-loop already vectorized.\n");
2230 /* Check the CFG characteristics of the loop (nesting, entry/exit). */
2231 loop_vinfo
= vect_analyze_loop_form (loop
);
2234 if (dump_enabled_p ())
2235 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2236 "bad loop form.\n");
2241 if (vect_analyze_loop_2 (loop_vinfo
, fatal
))
2243 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
) = 1;
2248 destroy_loop_vec_info (loop_vinfo
, true);
2250 vector_sizes
&= ~current_vector_size
;
2252 || vector_sizes
== 0
2253 || current_vector_size
== 0)
2256 /* Try the next biggest vector size. */
2257 current_vector_size
= 1 << floor_log2 (vector_sizes
);
2258 if (dump_enabled_p ())
2259 dump_printf_loc (MSG_NOTE
, vect_location
,
2260 "***** Re-trying analysis with "
2261 "vector size %d\n", current_vector_size
);
2266 /* Function reduction_code_for_scalar_code
2269 CODE - tree_code of a reduction operations.
2272 REDUC_CODE - the corresponding tree-code to be used to reduce the
2273 vector of partial results into a single scalar result, or ERROR_MARK
2274 if the operation is a supported reduction operation, but does not have
2277 Return FALSE if CODE currently cannot be vectorized as reduction. */
2280 reduction_code_for_scalar_code (enum tree_code code
,
2281 enum tree_code
*reduc_code
)
2286 *reduc_code
= REDUC_MAX_EXPR
;
2290 *reduc_code
= REDUC_MIN_EXPR
;
2294 *reduc_code
= REDUC_PLUS_EXPR
;
2302 *reduc_code
= ERROR_MARK
;
2311 /* Error reporting helper for vect_is_simple_reduction below. GIMPLE statement
2312 STMT is printed with a message MSG. */
2315 report_vect_op (int msg_type
, gimple
*stmt
, const char *msg
)
2317 dump_printf_loc (msg_type
, vect_location
, "%s", msg
);
2318 dump_gimple_stmt (msg_type
, TDF_SLIM
, stmt
, 0);
2319 dump_printf (msg_type
, "\n");
2323 /* Detect SLP reduction of the form:
2333 PHI is the reduction phi node (#a1 = phi <a5, a0> above)
2334 FIRST_STMT is the first reduction stmt in the chain
2335 (a2 = operation (a1)).
2337 Return TRUE if a reduction chain was detected. */
2340 vect_is_slp_reduction (loop_vec_info loop_info
, gimple
*phi
,
2343 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
2344 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
2345 enum tree_code code
;
2346 gimple
*current_stmt
= NULL
, *loop_use_stmt
= NULL
, *first
, *next_stmt
;
2347 stmt_vec_info use_stmt_info
, current_stmt_info
;
2349 imm_use_iterator imm_iter
;
2350 use_operand_p use_p
;
2351 int nloop_uses
, size
= 0, n_out_of_loop_uses
;
2354 if (loop
!= vect_loop
)
2357 lhs
= PHI_RESULT (phi
);
2358 code
= gimple_assign_rhs_code (first_stmt
);
2362 n_out_of_loop_uses
= 0;
2363 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2365 gimple
*use_stmt
= USE_STMT (use_p
);
2366 if (is_gimple_debug (use_stmt
))
2369 /* Check if we got back to the reduction phi. */
2370 if (use_stmt
== phi
)
2372 loop_use_stmt
= use_stmt
;
2377 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2379 loop_use_stmt
= use_stmt
;
2383 n_out_of_loop_uses
++;
2385 /* There are can be either a single use in the loop or two uses in
2387 if (nloop_uses
> 1 || (n_out_of_loop_uses
&& nloop_uses
))
2394 /* We reached a statement with no loop uses. */
2395 if (nloop_uses
== 0)
2398 /* This is a loop exit phi, and we haven't reached the reduction phi. */
2399 if (gimple_code (loop_use_stmt
) == GIMPLE_PHI
)
2402 if (!is_gimple_assign (loop_use_stmt
)
2403 || code
!= gimple_assign_rhs_code (loop_use_stmt
)
2404 || !flow_bb_inside_loop_p (loop
, gimple_bb (loop_use_stmt
)))
2407 /* Insert USE_STMT into reduction chain. */
2408 use_stmt_info
= vinfo_for_stmt (loop_use_stmt
);
2411 current_stmt_info
= vinfo_for_stmt (current_stmt
);
2412 GROUP_NEXT_ELEMENT (current_stmt_info
) = loop_use_stmt
;
2413 GROUP_FIRST_ELEMENT (use_stmt_info
)
2414 = GROUP_FIRST_ELEMENT (current_stmt_info
);
2417 GROUP_FIRST_ELEMENT (use_stmt_info
) = loop_use_stmt
;
2419 lhs
= gimple_assign_lhs (loop_use_stmt
);
2420 current_stmt
= loop_use_stmt
;
2424 if (!found
|| loop_use_stmt
!= phi
|| size
< 2)
2427 /* Swap the operands, if needed, to make the reduction operand be the second
2429 lhs
= PHI_RESULT (phi
);
2430 next_stmt
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
2433 if (gimple_assign_rhs2 (next_stmt
) == lhs
)
2435 tree op
= gimple_assign_rhs1 (next_stmt
);
2436 gimple
*def_stmt
= NULL
;
2438 if (TREE_CODE (op
) == SSA_NAME
)
2439 def_stmt
= SSA_NAME_DEF_STMT (op
);
2441 /* Check that the other def is either defined in the loop
2442 ("vect_internal_def"), or it's an induction (defined by a
2443 loop-header phi-node). */
2445 && gimple_bb (def_stmt
)
2446 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2447 && (is_gimple_assign (def_stmt
)
2448 || is_gimple_call (def_stmt
)
2449 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2450 == vect_induction_def
2451 || (gimple_code (def_stmt
) == GIMPLE_PHI
2452 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2453 == vect_internal_def
2454 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
2456 lhs
= gimple_assign_lhs (next_stmt
);
2457 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
2465 tree op
= gimple_assign_rhs2 (next_stmt
);
2466 gimple
*def_stmt
= NULL
;
2468 if (TREE_CODE (op
) == SSA_NAME
)
2469 def_stmt
= SSA_NAME_DEF_STMT (op
);
2471 /* Check that the other def is either defined in the loop
2472 ("vect_internal_def"), or it's an induction (defined by a
2473 loop-header phi-node). */
2475 && gimple_bb (def_stmt
)
2476 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2477 && (is_gimple_assign (def_stmt
)
2478 || is_gimple_call (def_stmt
)
2479 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2480 == vect_induction_def
2481 || (gimple_code (def_stmt
) == GIMPLE_PHI
2482 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2483 == vect_internal_def
2484 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
2486 if (dump_enabled_p ())
2488 dump_printf_loc (MSG_NOTE
, vect_location
, "swapping oprnds: ");
2489 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, next_stmt
, 0);
2490 dump_printf (MSG_NOTE
, "\n");
2493 swap_ssa_operands (next_stmt
,
2494 gimple_assign_rhs1_ptr (next_stmt
),
2495 gimple_assign_rhs2_ptr (next_stmt
));
2496 update_stmt (next_stmt
);
2498 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (next_stmt
)))
2499 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
2505 lhs
= gimple_assign_lhs (next_stmt
);
2506 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
2509 /* Save the chain for further analysis in SLP detection. */
2510 first
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
2511 LOOP_VINFO_REDUCTION_CHAINS (loop_info
).safe_push (first
);
2512 GROUP_SIZE (vinfo_for_stmt (first
)) = size
;
2518 /* Function vect_is_simple_reduction_1
2520 (1) Detect a cross-iteration def-use cycle that represents a simple
2521 reduction computation. We look for the following pattern:
2526 a2 = operation (a3, a1)
2533 a2 = operation (a3, a1)
2536 1. operation is commutative and associative and it is safe to
2537 change the order of the computation (if CHECK_REDUCTION is true)
2538 2. no uses for a2 in the loop (a2 is used out of the loop)
2539 3. no uses of a1 in the loop besides the reduction operation
2540 4. no uses of a1 outside the loop.
2542 Conditions 1,4 are tested here.
2543 Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
2545 (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
2546 nested cycles, if CHECK_REDUCTION is false.
2548 (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
2552 inner loop (def of a3)
2555 (4) Detect condition expressions, ie:
2556 for (int i = 0; i < N; i++)
2563 vect_is_simple_reduction (loop_vec_info loop_info
, gimple
*phi
,
2564 bool check_reduction
, bool *double_reduc
,
2565 bool need_wrapping_integral_overflow
,
2566 enum vect_reduction_type
*v_reduc_type
)
2568 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
2569 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
2570 edge latch_e
= loop_latch_edge (loop
);
2571 tree loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
2572 gimple
*def_stmt
, *def1
= NULL
, *def2
= NULL
;
2573 enum tree_code orig_code
, code
;
2574 tree op1
, op2
, op3
= NULL_TREE
, op4
= NULL_TREE
;
2578 imm_use_iterator imm_iter
;
2579 use_operand_p use_p
;
2582 *double_reduc
= false;
2583 *v_reduc_type
= TREE_CODE_REDUCTION
;
2585 /* If CHECK_REDUCTION is true, we assume inner-most loop vectorization,
2586 otherwise, we assume outer loop vectorization. */
2587 gcc_assert ((check_reduction
&& loop
== vect_loop
)
2588 || (!check_reduction
&& flow_loop_nested_p (vect_loop
, loop
)));
2590 name
= PHI_RESULT (phi
);
2591 /* ??? If there are no uses of the PHI result the inner loop reduction
2592 won't be detected as possibly double-reduction by vectorizable_reduction
2593 because that tries to walk the PHI arg from the preheader edge which
2594 can be constant. See PR60382. */
2595 if (has_zero_uses (name
))
2598 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2600 gimple
*use_stmt
= USE_STMT (use_p
);
2601 if (is_gimple_debug (use_stmt
))
2604 if (!flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2606 if (dump_enabled_p ())
2607 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2608 "intermediate value used outside loop.\n");
2616 if (dump_enabled_p ())
2617 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2618 "reduction used in loop.\n");
2623 if (TREE_CODE (loop_arg
) != SSA_NAME
)
2625 if (dump_enabled_p ())
2627 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2628 "reduction: not ssa_name: ");
2629 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, loop_arg
);
2630 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
2635 def_stmt
= SSA_NAME_DEF_STMT (loop_arg
);
2638 if (dump_enabled_p ())
2639 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2640 "reduction: no def_stmt.\n");
2644 if (!is_gimple_assign (def_stmt
) && gimple_code (def_stmt
) != GIMPLE_PHI
)
2646 if (dump_enabled_p ())
2648 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, def_stmt
, 0);
2649 dump_printf (MSG_NOTE
, "\n");
2654 if (is_gimple_assign (def_stmt
))
2656 name
= gimple_assign_lhs (def_stmt
);
2661 name
= PHI_RESULT (def_stmt
);
2666 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2668 gimple
*use_stmt
= USE_STMT (use_p
);
2669 if (is_gimple_debug (use_stmt
))
2671 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2675 if (dump_enabled_p ())
2676 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2677 "reduction used in loop.\n");
2682 /* If DEF_STMT is a phi node itself, we expect it to have a single argument
2683 defined in the inner loop. */
2686 op1
= PHI_ARG_DEF (def_stmt
, 0);
2688 if (gimple_phi_num_args (def_stmt
) != 1
2689 || TREE_CODE (op1
) != SSA_NAME
)
2691 if (dump_enabled_p ())
2692 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2693 "unsupported phi node definition.\n");
2698 def1
= SSA_NAME_DEF_STMT (op1
);
2699 if (gimple_bb (def1
)
2700 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2702 && flow_bb_inside_loop_p (loop
->inner
, gimple_bb (def1
))
2703 && is_gimple_assign (def1
))
2705 if (dump_enabled_p ())
2706 report_vect_op (MSG_NOTE
, def_stmt
,
2707 "detected double reduction: ");
2709 *double_reduc
= true;
2716 code
= orig_code
= gimple_assign_rhs_code (def_stmt
);
2718 /* We can handle "res -= x[i]", which is non-associative by
2719 simply rewriting this into "res += -x[i]". Avoid changing
2720 gimple instruction for the first simple tests and only do this
2721 if we're allowed to change code at all. */
2722 if (code
== MINUS_EXPR
2723 && (op1
= gimple_assign_rhs1 (def_stmt
))
2724 && TREE_CODE (op1
) == SSA_NAME
2725 && SSA_NAME_DEF_STMT (op1
) == phi
)
2728 if (check_reduction
)
2730 if (code
== COND_EXPR
)
2731 *v_reduc_type
= COND_REDUCTION
;
2732 else if (!commutative_tree_code (code
) || !associative_tree_code (code
))
2734 if (dump_enabled_p ())
2735 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2736 "reduction: not commutative/associative: ");
2741 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
2743 if (code
!= COND_EXPR
)
2745 if (dump_enabled_p ())
2746 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2747 "reduction: not binary operation: ");
2752 op3
= gimple_assign_rhs1 (def_stmt
);
2753 if (COMPARISON_CLASS_P (op3
))
2755 op4
= TREE_OPERAND (op3
, 1);
2756 op3
= TREE_OPERAND (op3
, 0);
2759 op1
= gimple_assign_rhs2 (def_stmt
);
2760 op2
= gimple_assign_rhs3 (def_stmt
);
2762 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2764 if (dump_enabled_p ())
2765 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2766 "reduction: uses not ssa_names: ");
2773 op1
= gimple_assign_rhs1 (def_stmt
);
2774 op2
= gimple_assign_rhs2 (def_stmt
);
2776 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2778 if (dump_enabled_p ())
2779 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2780 "reduction: uses not ssa_names: ");
2786 type
= TREE_TYPE (gimple_assign_lhs (def_stmt
));
2787 if ((TREE_CODE (op1
) == SSA_NAME
2788 && !types_compatible_p (type
,TREE_TYPE (op1
)))
2789 || (TREE_CODE (op2
) == SSA_NAME
2790 && !types_compatible_p (type
, TREE_TYPE (op2
)))
2791 || (op3
&& TREE_CODE (op3
) == SSA_NAME
2792 && !types_compatible_p (type
, TREE_TYPE (op3
)))
2793 || (op4
&& TREE_CODE (op4
) == SSA_NAME
2794 && !types_compatible_p (type
, TREE_TYPE (op4
))))
2796 if (dump_enabled_p ())
2798 dump_printf_loc (MSG_NOTE
, vect_location
,
2799 "reduction: multiple types: operation type: ");
2800 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, type
);
2801 dump_printf (MSG_NOTE
, ", operands types: ");
2802 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2804 dump_printf (MSG_NOTE
, ",");
2805 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2809 dump_printf (MSG_NOTE
, ",");
2810 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2816 dump_printf (MSG_NOTE
, ",");
2817 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2820 dump_printf (MSG_NOTE
, "\n");
2826 /* Check that it's ok to change the order of the computation.
2827 Generally, when vectorizing a reduction we change the order of the
2828 computation. This may change the behavior of the program in some
2829 cases, so we need to check that this is ok. One exception is when
2830 vectorizing an outer-loop: the inner-loop is executed sequentially,
2831 and therefore vectorizing reductions in the inner-loop during
2832 outer-loop vectorization is safe. */
2834 if (*v_reduc_type
!= COND_REDUCTION
)
2836 /* CHECKME: check for !flag_finite_math_only too? */
2837 if (SCALAR_FLOAT_TYPE_P (type
) && !flag_associative_math
2840 /* Changing the order of operations changes the semantics. */
2841 if (dump_enabled_p ())
2842 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2843 "reduction: unsafe fp math optimization: ");
2846 else if (INTEGRAL_TYPE_P (type
) && check_reduction
)
2848 if (!operation_no_trapping_overflow (type
, code
))
2850 /* Changing the order of operations changes the semantics. */
2851 if (dump_enabled_p ())
2852 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2853 "reduction: unsafe int math optimization"
2854 " (overflow traps): ");
2857 if (need_wrapping_integral_overflow
2858 && !TYPE_OVERFLOW_WRAPS (type
)
2859 && operation_can_overflow (code
))
2861 /* Changing the order of operations changes the semantics. */
2862 if (dump_enabled_p ())
2863 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2864 "reduction: unsafe int math optimization"
2865 " (overflow doesn't wrap): ");
2869 else if (SAT_FIXED_POINT_TYPE_P (type
) && check_reduction
)
2871 /* Changing the order of operations changes the semantics. */
2872 if (dump_enabled_p ())
2873 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2874 "reduction: unsafe fixed-point math optimization: ");
2879 /* Reduction is safe. We're dealing with one of the following:
2880 1) integer arithmetic and no trapv
2881 2) floating point arithmetic, and special flags permit this optimization
2882 3) nested cycle (i.e., outer loop vectorization). */
2883 if (TREE_CODE (op1
) == SSA_NAME
)
2884 def1
= SSA_NAME_DEF_STMT (op1
);
2886 if (TREE_CODE (op2
) == SSA_NAME
)
2887 def2
= SSA_NAME_DEF_STMT (op2
);
2889 if (code
!= COND_EXPR
2890 && ((!def1
|| gimple_nop_p (def1
)) && (!def2
|| gimple_nop_p (def2
))))
2892 if (dump_enabled_p ())
2893 report_vect_op (MSG_NOTE
, def_stmt
, "reduction: no defs for operands: ");
2897 /* Check that one def is the reduction def, defined by PHI,
2898 the other def is either defined in the loop ("vect_internal_def"),
2899 or it's an induction (defined by a loop-header phi-node). */
2901 if (def2
&& def2
== phi
2902 && (code
== COND_EXPR
2903 || !def1
|| gimple_nop_p (def1
)
2904 || !flow_bb_inside_loop_p (loop
, gimple_bb (def1
))
2905 || (def1
&& flow_bb_inside_loop_p (loop
, gimple_bb (def1
))
2906 && (is_gimple_assign (def1
)
2907 || is_gimple_call (def1
)
2908 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
2909 == vect_induction_def
2910 || (gimple_code (def1
) == GIMPLE_PHI
2911 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
2912 == vect_internal_def
2913 && !is_loop_header_bb_p (gimple_bb (def1
)))))))
2915 if (dump_enabled_p ())
2916 report_vect_op (MSG_NOTE
, def_stmt
, "detected reduction: ");
2920 if (def1
&& def1
== phi
2921 && (code
== COND_EXPR
2922 || !def2
|| gimple_nop_p (def2
)
2923 || !flow_bb_inside_loop_p (loop
, gimple_bb (def2
))
2924 || (def2
&& flow_bb_inside_loop_p (loop
, gimple_bb (def2
))
2925 && (is_gimple_assign (def2
)
2926 || is_gimple_call (def2
)
2927 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
2928 == vect_induction_def
2929 || (gimple_code (def2
) == GIMPLE_PHI
2930 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
2931 == vect_internal_def
2932 && !is_loop_header_bb_p (gimple_bb (def2
)))))))
2935 && orig_code
!= MINUS_EXPR
)
2937 if (code
== COND_EXPR
)
2939 /* No current known use where this case would be useful. */
2940 if (dump_enabled_p ())
2941 report_vect_op (MSG_NOTE
, def_stmt
,
2942 "detected reduction: cannot currently swap "
2943 "operands for cond_expr");
2947 /* Swap operands (just for simplicity - so that the rest of the code
2948 can assume that the reduction variable is always the last (second)
2950 if (dump_enabled_p ())
2951 report_vect_op (MSG_NOTE
, def_stmt
,
2952 "detected reduction: need to swap operands: ");
2954 swap_ssa_operands (def_stmt
, gimple_assign_rhs1_ptr (def_stmt
),
2955 gimple_assign_rhs2_ptr (def_stmt
));
2957 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (def_stmt
)))
2958 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
2962 if (dump_enabled_p ())
2963 report_vect_op (MSG_NOTE
, def_stmt
, "detected reduction: ");
2969 /* Try to find SLP reduction chain. */
2970 if (check_reduction
&& code
!= COND_EXPR
2971 && vect_is_slp_reduction (loop_info
, phi
, def_stmt
))
2973 if (dump_enabled_p ())
2974 report_vect_op (MSG_NOTE
, def_stmt
,
2975 "reduction: detected reduction chain: ");
2980 if (dump_enabled_p ())
2981 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2982 "reduction: unknown pattern: ");
2987 /* Wrapper around vect_is_simple_reduction_1, which will modify code
2988 in-place if it enables detection of more reductions. Arguments
2992 vect_force_simple_reduction (loop_vec_info loop_info
, gimple
*phi
,
2993 bool check_reduction
, bool *double_reduc
,
2994 bool need_wrapping_integral_overflow
)
2996 enum vect_reduction_type v_reduc_type
;
2997 return vect_is_simple_reduction (loop_info
, phi
, check_reduction
,
2999 need_wrapping_integral_overflow
,
3003 /* Calculate cost of peeling the loop PEEL_ITERS_PROLOGUE times. */
3005 vect_get_known_peeling_cost (loop_vec_info loop_vinfo
, int peel_iters_prologue
,
3006 int *peel_iters_epilogue
,
3007 stmt_vector_for_cost
*scalar_cost_vec
,
3008 stmt_vector_for_cost
*prologue_cost_vec
,
3009 stmt_vector_for_cost
*epilogue_cost_vec
)
3012 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3014 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
3016 *peel_iters_epilogue
= vf
/2;
3017 if (dump_enabled_p ())
3018 dump_printf_loc (MSG_NOTE
, vect_location
,
3019 "cost model: epilogue peel iters set to vf/2 "
3020 "because loop iterations are unknown .\n");
3022 /* If peeled iterations are known but number of scalar loop
3023 iterations are unknown, count a taken branch per peeled loop. */
3024 retval
= record_stmt_cost (prologue_cost_vec
, 1, cond_branch_taken
,
3025 NULL
, 0, vect_prologue
);
3026 retval
= record_stmt_cost (prologue_cost_vec
, 1, cond_branch_taken
,
3027 NULL
, 0, vect_epilogue
);
3031 int niters
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
3032 peel_iters_prologue
= niters
< peel_iters_prologue
?
3033 niters
: peel_iters_prologue
;
3034 *peel_iters_epilogue
= (niters
- peel_iters_prologue
) % vf
;
3035 /* If we need to peel for gaps, but no peeling is required, we have to
3036 peel VF iterations. */
3037 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) && !*peel_iters_epilogue
)
3038 *peel_iters_epilogue
= vf
;
3041 stmt_info_for_cost
*si
;
3043 if (peel_iters_prologue
)
3044 FOR_EACH_VEC_ELT (*scalar_cost_vec
, j
, si
)
3045 retval
+= record_stmt_cost (prologue_cost_vec
,
3046 si
->count
* peel_iters_prologue
,
3047 si
->kind
, NULL
, si
->misalign
,
3049 if (*peel_iters_epilogue
)
3050 FOR_EACH_VEC_ELT (*scalar_cost_vec
, j
, si
)
3051 retval
+= record_stmt_cost (epilogue_cost_vec
,
3052 si
->count
* *peel_iters_epilogue
,
3053 si
->kind
, NULL
, si
->misalign
,
3059 /* Function vect_estimate_min_profitable_iters
3061 Return the number of iterations required for the vector version of the
3062 loop to be profitable relative to the cost of the scalar version of the
3066 vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo
,
3067 int *ret_min_profitable_niters
,
3068 int *ret_min_profitable_estimate
)
3070 int min_profitable_iters
;
3071 int min_profitable_estimate
;
3072 int peel_iters_prologue
;
3073 int peel_iters_epilogue
;
3074 unsigned vec_inside_cost
= 0;
3075 int vec_outside_cost
= 0;
3076 unsigned vec_prologue_cost
= 0;
3077 unsigned vec_epilogue_cost
= 0;
3078 int scalar_single_iter_cost
= 0;
3079 int scalar_outside_cost
= 0;
3080 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3081 int npeel
= LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
);
3082 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3084 /* Cost model disabled. */
3085 if (unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo
)))
3087 dump_printf_loc (MSG_NOTE
, vect_location
, "cost model disabled.\n");
3088 *ret_min_profitable_niters
= 0;
3089 *ret_min_profitable_estimate
= 0;
3093 /* Requires loop versioning tests to handle misalignment. */
3094 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
))
3096 /* FIXME: Make cost depend on complexity of individual check. */
3097 unsigned len
= LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).length ();
3098 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
3100 dump_printf (MSG_NOTE
,
3101 "cost model: Adding cost of checks for loop "
3102 "versioning to treat misalignment.\n");
3105 /* Requires loop versioning with alias checks. */
3106 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
3108 /* FIXME: Make cost depend on complexity of individual check. */
3109 unsigned len
= LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo
).length ();
3110 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
3112 dump_printf (MSG_NOTE
,
3113 "cost model: Adding cost of checks for loop "
3114 "versioning aliasing.\n");
3117 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
3118 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
3119 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_taken
, NULL
, 0,
3122 /* Count statements in scalar loop. Using this as scalar cost for a single
3125 TODO: Add outer loop support.
3127 TODO: Consider assigning different costs to different scalar
3130 scalar_single_iter_cost
3131 = LOOP_VINFO_SINGLE_SCALAR_ITERATION_COST (loop_vinfo
);
3133 /* Add additional cost for the peeled instructions in prologue and epilogue
3136 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
3137 at compile-time - we assume it's vf/2 (the worst would be vf-1).
3139 TODO: Build an expression that represents peel_iters for prologue and
3140 epilogue to be used in a run-time test. */
3144 peel_iters_prologue
= vf
/2;
3145 dump_printf (MSG_NOTE
, "cost model: "
3146 "prologue peel iters set to vf/2.\n");
3148 /* If peeling for alignment is unknown, loop bound of main loop becomes
3150 peel_iters_epilogue
= vf
/2;
3151 dump_printf (MSG_NOTE
, "cost model: "
3152 "epilogue peel iters set to vf/2 because "
3153 "peeling for alignment is unknown.\n");
3155 /* If peeled iterations are unknown, count a taken branch and a not taken
3156 branch per peeled loop. Even if scalar loop iterations are known,
3157 vector iterations are not known since peeled prologue iterations are
3158 not known. Hence guards remain the same. */
3159 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_taken
,
3160 NULL
, 0, vect_prologue
);
3161 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_not_taken
,
3162 NULL
, 0, vect_prologue
);
3163 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_taken
,
3164 NULL
, 0, vect_epilogue
);
3165 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_not_taken
,
3166 NULL
, 0, vect_epilogue
);
3167 stmt_info_for_cost
*si
;
3169 FOR_EACH_VEC_ELT (LOOP_VINFO_SCALAR_ITERATION_COST (loop_vinfo
), j
, si
)
3171 struct _stmt_vec_info
*stmt_info
3172 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
3173 (void) add_stmt_cost (target_cost_data
,
3174 si
->count
* peel_iters_prologue
,
3175 si
->kind
, stmt_info
, si
->misalign
,
3177 (void) add_stmt_cost (target_cost_data
,
3178 si
->count
* peel_iters_epilogue
,
3179 si
->kind
, stmt_info
, si
->misalign
,
3185 stmt_vector_for_cost prologue_cost_vec
, epilogue_cost_vec
;
3186 stmt_info_for_cost
*si
;
3188 void *data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3190 prologue_cost_vec
.create (2);
3191 epilogue_cost_vec
.create (2);
3192 peel_iters_prologue
= npeel
;
3194 (void) vect_get_known_peeling_cost (loop_vinfo
, peel_iters_prologue
,
3195 &peel_iters_epilogue
,
3196 &LOOP_VINFO_SCALAR_ITERATION_COST
3199 &epilogue_cost_vec
);
3201 FOR_EACH_VEC_ELT (prologue_cost_vec
, j
, si
)
3203 struct _stmt_vec_info
*stmt_info
3204 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
3205 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
3206 si
->misalign
, vect_prologue
);
3209 FOR_EACH_VEC_ELT (epilogue_cost_vec
, j
, si
)
3211 struct _stmt_vec_info
*stmt_info
3212 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
3213 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
3214 si
->misalign
, vect_epilogue
);
3217 prologue_cost_vec
.release ();
3218 epilogue_cost_vec
.release ();
3221 /* FORNOW: The scalar outside cost is incremented in one of the
3224 1. The vectorizer checks for alignment and aliasing and generates
3225 a condition that allows dynamic vectorization. A cost model
3226 check is ANDED with the versioning condition. Hence scalar code
3227 path now has the added cost of the versioning check.
3229 if (cost > th & versioning_check)
3232 Hence run-time scalar is incremented by not-taken branch cost.
3234 2. The vectorizer then checks if a prologue is required. If the
3235 cost model check was not done before during versioning, it has to
3236 be done before the prologue check.
3239 prologue = scalar_iters
3244 if (prologue == num_iters)
3247 Hence the run-time scalar cost is incremented by a taken branch,
3248 plus a not-taken branch, plus a taken branch cost.
3250 3. The vectorizer then checks if an epilogue is required. If the
3251 cost model check was not done before during prologue check, it
3252 has to be done with the epilogue check.
3258 if (prologue == num_iters)
3261 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
3264 Hence the run-time scalar cost should be incremented by 2 taken
3267 TODO: The back end may reorder the BBS's differently and reverse
3268 conditions/branch directions. Change the estimates below to
3269 something more reasonable. */
3271 /* If the number of iterations is known and we do not do versioning, we can
3272 decide whether to vectorize at compile time. Hence the scalar version
3273 do not carry cost model guard costs. */
3274 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
3275 || LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
3276 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
3278 /* Cost model check occurs at versioning. */
3279 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
3280 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
3281 scalar_outside_cost
+= vect_get_stmt_cost (cond_branch_not_taken
);
3284 /* Cost model check occurs at prologue generation. */
3285 if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
) < 0)
3286 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
)
3287 + vect_get_stmt_cost (cond_branch_not_taken
);
3288 /* Cost model check occurs at epilogue generation. */
3290 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
);
3294 /* Complete the target-specific cost calculations. */
3295 finish_cost (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
), &vec_prologue_cost
,
3296 &vec_inside_cost
, &vec_epilogue_cost
);
3298 vec_outside_cost
= (int)(vec_prologue_cost
+ vec_epilogue_cost
);
3300 if (dump_enabled_p ())
3302 dump_printf_loc (MSG_NOTE
, vect_location
, "Cost model analysis: \n");
3303 dump_printf (MSG_NOTE
, " Vector inside of loop cost: %d\n",
3305 dump_printf (MSG_NOTE
, " Vector prologue cost: %d\n",
3307 dump_printf (MSG_NOTE
, " Vector epilogue cost: %d\n",
3309 dump_printf (MSG_NOTE
, " Scalar iteration cost: %d\n",
3310 scalar_single_iter_cost
);
3311 dump_printf (MSG_NOTE
, " Scalar outside cost: %d\n",
3312 scalar_outside_cost
);
3313 dump_printf (MSG_NOTE
, " Vector outside cost: %d\n",
3315 dump_printf (MSG_NOTE
, " prologue iterations: %d\n",
3316 peel_iters_prologue
);
3317 dump_printf (MSG_NOTE
, " epilogue iterations: %d\n",
3318 peel_iters_epilogue
);
3321 /* Calculate number of iterations required to make the vector version
3322 profitable, relative to the loop bodies only. The following condition
3324 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
3326 SIC = scalar iteration cost, VIC = vector iteration cost,
3327 VOC = vector outside cost, VF = vectorization factor,
3328 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
3329 SOC = scalar outside cost for run time cost model check. */
3331 if ((scalar_single_iter_cost
* vf
) > (int) vec_inside_cost
)
3333 if (vec_outside_cost
<= 0)
3334 min_profitable_iters
= 1;
3337 min_profitable_iters
= ((vec_outside_cost
- scalar_outside_cost
) * vf
3338 - vec_inside_cost
* peel_iters_prologue
3339 - vec_inside_cost
* peel_iters_epilogue
)
3340 / ((scalar_single_iter_cost
* vf
)
3343 if ((scalar_single_iter_cost
* vf
* min_profitable_iters
)
3344 <= (((int) vec_inside_cost
* min_profitable_iters
)
3345 + (((int) vec_outside_cost
- scalar_outside_cost
) * vf
)))
3346 min_profitable_iters
++;
3349 /* vector version will never be profitable. */
3352 if (LOOP_VINFO_LOOP (loop_vinfo
)->force_vectorize
)
3353 warning_at (vect_location
, OPT_Wopenmp_simd
, "vectorization "
3354 "did not happen for a simd loop");
3356 if (dump_enabled_p ())
3357 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3358 "cost model: the vector iteration cost = %d "
3359 "divided by the scalar iteration cost = %d "
3360 "is greater or equal to the vectorization factor = %d"
3362 vec_inside_cost
, scalar_single_iter_cost
, vf
);
3363 *ret_min_profitable_niters
= -1;
3364 *ret_min_profitable_estimate
= -1;
3368 dump_printf (MSG_NOTE
,
3369 " Calculated minimum iters for profitability: %d\n",
3370 min_profitable_iters
);
3372 min_profitable_iters
=
3373 min_profitable_iters
< vf
? vf
: min_profitable_iters
;
3375 /* Because the condition we create is:
3376 if (niters <= min_profitable_iters)
3377 then skip the vectorized loop. */
3378 min_profitable_iters
--;
3380 if (dump_enabled_p ())
3381 dump_printf_loc (MSG_NOTE
, vect_location
,
3382 " Runtime profitability threshold = %d\n",
3383 min_profitable_iters
);
3385 *ret_min_profitable_niters
= min_profitable_iters
;
3387 /* Calculate number of iterations required to make the vector version
3388 profitable, relative to the loop bodies only.
3390 Non-vectorized variant is SIC * niters and it must win over vector
3391 variant on the expected loop trip count. The following condition must hold true:
3392 SIC * niters > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC + SOC */
3394 if (vec_outside_cost
<= 0)
3395 min_profitable_estimate
= 1;
3398 min_profitable_estimate
= ((vec_outside_cost
+ scalar_outside_cost
) * vf
3399 - vec_inside_cost
* peel_iters_prologue
3400 - vec_inside_cost
* peel_iters_epilogue
)
3401 / ((scalar_single_iter_cost
* vf
)
3404 min_profitable_estimate
--;
3405 min_profitable_estimate
= MAX (min_profitable_estimate
, min_profitable_iters
);
3406 if (dump_enabled_p ())
3407 dump_printf_loc (MSG_NOTE
, vect_location
,
3408 " Static estimate profitability threshold = %d\n",
3409 min_profitable_iters
);
3411 *ret_min_profitable_estimate
= min_profitable_estimate
;
3414 /* Writes into SEL a mask for a vec_perm, equivalent to a vec_shr by OFFSET
3415 vector elements (not bits) for a vector of mode MODE. */
3417 calc_vec_perm_mask_for_shift (enum machine_mode mode
, unsigned int offset
,
3420 unsigned int i
, nelt
= GET_MODE_NUNITS (mode
);
3422 for (i
= 0; i
< nelt
; i
++)
3423 sel
[i
] = (i
+ offset
) & (2*nelt
- 1);
3426 /* Checks whether the target supports whole-vector shifts for vectors of mode
3427 MODE. This is the case if _either_ the platform handles vec_shr_optab, _or_
3428 it supports vec_perm_const with masks for all necessary shift amounts. */
3430 have_whole_vector_shift (enum machine_mode mode
)
3432 if (optab_handler (vec_shr_optab
, mode
) != CODE_FOR_nothing
)
3435 if (direct_optab_handler (vec_perm_const_optab
, mode
) == CODE_FOR_nothing
)
3438 unsigned int i
, nelt
= GET_MODE_NUNITS (mode
);
3439 unsigned char *sel
= XALLOCAVEC (unsigned char, nelt
);
3441 for (i
= nelt
/2; i
>= 1; i
/=2)
3443 calc_vec_perm_mask_for_shift (mode
, i
, sel
);
3444 if (!can_vec_perm_p (mode
, false, sel
))
3450 /* Return the reduction operand (with index REDUC_INDEX) of STMT. */
3453 get_reduction_op (gimple
*stmt
, int reduc_index
)
3455 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3457 case GIMPLE_SINGLE_RHS
:
3458 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
))
3460 return TREE_OPERAND (gimple_assign_rhs1 (stmt
), reduc_index
);
3461 case GIMPLE_UNARY_RHS
:
3462 return gimple_assign_rhs1 (stmt
);
3463 case GIMPLE_BINARY_RHS
:
3465 ? gimple_assign_rhs2 (stmt
) : gimple_assign_rhs1 (stmt
));
3466 case GIMPLE_TERNARY_RHS
:
3467 return gimple_op (stmt
, reduc_index
+ 1);
3473 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
3474 functions. Design better to avoid maintenance issues. */
3476 /* Function vect_model_reduction_cost.
3478 Models cost for a reduction operation, including the vector ops
3479 generated within the strip-mine loop, the initial definition before
3480 the loop, and the epilogue code that must be generated. */
3483 vect_model_reduction_cost (stmt_vec_info stmt_info
, enum tree_code reduc_code
,
3484 int ncopies
, int reduc_index
)
3486 int prologue_cost
= 0, epilogue_cost
= 0;
3487 enum tree_code code
;
3490 gimple
*stmt
, *orig_stmt
;
3493 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3494 struct loop
*loop
= NULL
;
3495 void *target_cost_data
;
3499 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3500 target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3503 target_cost_data
= BB_VINFO_TARGET_COST_DATA (STMT_VINFO_BB_VINFO (stmt_info
));
3505 /* Condition reductions generate two reductions in the loop. */
3506 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
)
3509 /* Cost of reduction op inside loop. */
3510 unsigned inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
3511 stmt_info
, 0, vect_body
);
3512 stmt
= STMT_VINFO_STMT (stmt_info
);
3514 reduction_op
= get_reduction_op (stmt
, reduc_index
);
3516 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
3519 if (dump_enabled_p ())
3521 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3522 "unsupported data-type ");
3523 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
3524 TREE_TYPE (reduction_op
));
3525 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3530 mode
= TYPE_MODE (vectype
);
3531 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
3534 orig_stmt
= STMT_VINFO_STMT (stmt_info
);
3536 code
= gimple_assign_rhs_code (orig_stmt
);
3538 /* Add in cost for initial definition.
3539 For cond reduction we have four vectors: initial index, step, initial
3540 result of the data reduction, initial value of the index reduction. */
3541 int prologue_stmts
= STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
3542 == COND_REDUCTION
? 4 : 1;
3543 prologue_cost
+= add_stmt_cost (target_cost_data
, prologue_stmts
,
3544 scalar_to_vec
, stmt_info
, 0,
3547 /* Determine cost of epilogue code.
3549 We have a reduction operator that will reduce the vector in one statement.
3550 Also requires scalar extract. */
3552 if (!loop
|| !nested_in_vect_loop_p (loop
, orig_stmt
))
3554 if (reduc_code
!= ERROR_MARK
)
3556 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
)
3558 /* An EQ stmt and an COND_EXPR stmt. */
3559 epilogue_cost
+= add_stmt_cost (target_cost_data
, 2,
3560 vector_stmt
, stmt_info
, 0,
3562 /* Reduction of the max index and a reduction of the found
3564 epilogue_cost
+= add_stmt_cost (target_cost_data
, 2,
3565 vec_to_scalar
, stmt_info
, 0,
3567 /* A broadcast of the max value. */
3568 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1,
3569 scalar_to_vec
, stmt_info
, 0,
3574 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1, vector_stmt
,
3575 stmt_info
, 0, vect_epilogue
);
3576 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1,
3577 vec_to_scalar
, stmt_info
, 0,
3583 int vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
3585 TYPE_SIZE (TREE_TYPE (gimple_assign_lhs (orig_stmt
)));
3586 int element_bitsize
= tree_to_uhwi (bitsize
);
3587 int nelements
= vec_size_in_bits
/ element_bitsize
;
3589 optab
= optab_for_tree_code (code
, vectype
, optab_default
);
3591 /* We have a whole vector shift available. */
3592 if (VECTOR_MODE_P (mode
)
3593 && optab_handler (optab
, mode
) != CODE_FOR_nothing
3594 && have_whole_vector_shift (mode
))
3596 /* Final reduction via vector shifts and the reduction operator.
3597 Also requires scalar extract. */
3598 epilogue_cost
+= add_stmt_cost (target_cost_data
,
3599 exact_log2 (nelements
) * 2,
3600 vector_stmt
, stmt_info
, 0,
3602 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1,
3603 vec_to_scalar
, stmt_info
, 0,
3607 /* Use extracts and reduction op for final reduction. For N
3608 elements, we have N extracts and N-1 reduction ops. */
3609 epilogue_cost
+= add_stmt_cost (target_cost_data
,
3610 nelements
+ nelements
- 1,
3611 vector_stmt
, stmt_info
, 0,
3616 if (dump_enabled_p ())
3617 dump_printf (MSG_NOTE
,
3618 "vect_model_reduction_cost: inside_cost = %d, "
3619 "prologue_cost = %d, epilogue_cost = %d .\n", inside_cost
,
3620 prologue_cost
, epilogue_cost
);
3626 /* Function vect_model_induction_cost.
3628 Models cost for induction operations. */
3631 vect_model_induction_cost (stmt_vec_info stmt_info
, int ncopies
)
3633 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3634 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3635 unsigned inside_cost
, prologue_cost
;
3637 /* loop cost for vec_loop. */
3638 inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
3639 stmt_info
, 0, vect_body
);
3641 /* prologue cost for vec_init and vec_step. */
3642 prologue_cost
= add_stmt_cost (target_cost_data
, 2, scalar_to_vec
,
3643 stmt_info
, 0, vect_prologue
);
3645 if (dump_enabled_p ())
3646 dump_printf_loc (MSG_NOTE
, vect_location
,
3647 "vect_model_induction_cost: inside_cost = %d, "
3648 "prologue_cost = %d .\n", inside_cost
, prologue_cost
);
3652 /* Function get_initial_def_for_induction
3655 STMT - a stmt that performs an induction operation in the loop.
3656 IV_PHI - the initial value of the induction variable
3659 Return a vector variable, initialized with the first VF values of
3660 the induction variable. E.g., for an iv with IV_PHI='X' and
3661 evolution S, for a vector of 4 units, we want to return:
3662 [X, X + S, X + 2*S, X + 3*S]. */
3665 get_initial_def_for_induction (gimple
*iv_phi
)
3667 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (iv_phi
);
3668 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
3669 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3672 edge pe
= loop_preheader_edge (loop
);
3673 struct loop
*iv_loop
;
3675 tree new_vec
, vec_init
, vec_step
, t
;
3678 gphi
*induction_phi
;
3679 tree induc_def
, vec_def
, vec_dest
;
3680 tree init_expr
, step_expr
;
3681 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3685 stmt_vec_info phi_info
= vinfo_for_stmt (iv_phi
);
3686 bool nested_in_vect_loop
= false;
3688 imm_use_iterator imm_iter
;
3689 use_operand_p use_p
;
3693 gimple_stmt_iterator si
;
3694 basic_block bb
= gimple_bb (iv_phi
);
3698 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
3699 if (nested_in_vect_loop_p (loop
, iv_phi
))
3701 nested_in_vect_loop
= true;
3702 iv_loop
= loop
->inner
;
3706 gcc_assert (iv_loop
== (gimple_bb (iv_phi
))->loop_father
);
3708 latch_e
= loop_latch_edge (iv_loop
);
3709 loop_arg
= PHI_ARG_DEF_FROM_EDGE (iv_phi
, latch_e
);
3711 step_expr
= STMT_VINFO_LOOP_PHI_EVOLUTION_PART (phi_info
);
3712 gcc_assert (step_expr
!= NULL_TREE
);
3714 pe
= loop_preheader_edge (iv_loop
);
3715 init_expr
= PHI_ARG_DEF_FROM_EDGE (iv_phi
,
3716 loop_preheader_edge (iv_loop
));
3718 vectype
= get_vectype_for_scalar_type (TREE_TYPE (init_expr
));
3719 resvectype
= get_vectype_for_scalar_type (TREE_TYPE (PHI_RESULT (iv_phi
)));
3720 gcc_assert (vectype
);
3721 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3722 ncopies
= vf
/ nunits
;
3724 gcc_assert (phi_info
);
3725 gcc_assert (ncopies
>= 1);
3727 /* Convert the step to the desired type. */
3729 step_expr
= gimple_convert (&stmts
, TREE_TYPE (vectype
), step_expr
);
3732 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
3733 gcc_assert (!new_bb
);
3736 /* Find the first insertion point in the BB. */
3737 si
= gsi_after_labels (bb
);
3739 /* Create the vector that holds the initial_value of the induction. */
3740 if (nested_in_vect_loop
)
3742 /* iv_loop is nested in the loop to be vectorized. init_expr had already
3743 been created during vectorization of previous stmts. We obtain it
3744 from the STMT_VINFO_VEC_STMT of the defining stmt. */
3745 vec_init
= vect_get_vec_def_for_operand (init_expr
, iv_phi
);
3746 /* If the initial value is not of proper type, convert it. */
3747 if (!useless_type_conversion_p (vectype
, TREE_TYPE (vec_init
)))
3750 = gimple_build_assign (vect_get_new_ssa_name (vectype
,
3754 build1 (VIEW_CONVERT_EXPR
, vectype
,
3756 vec_init
= gimple_assign_lhs (new_stmt
);
3757 new_bb
= gsi_insert_on_edge_immediate (loop_preheader_edge (iv_loop
),
3759 gcc_assert (!new_bb
);
3760 set_vinfo_for_stmt (new_stmt
,
3761 new_stmt_vec_info (new_stmt
, loop_vinfo
));
3766 vec
<constructor_elt
, va_gc
> *v
;
3768 /* iv_loop is the loop to be vectorized. Create:
3769 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
3771 new_name
= gimple_convert (&stmts
, TREE_TYPE (vectype
), init_expr
);
3773 vec_alloc (v
, nunits
);
3774 bool constant_p
= is_gimple_min_invariant (new_name
);
3775 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
3776 for (i
= 1; i
< nunits
; i
++)
3778 /* Create: new_name_i = new_name + step_expr */
3779 new_name
= gimple_build (&stmts
, PLUS_EXPR
, TREE_TYPE (new_name
),
3780 new_name
, step_expr
);
3781 if (!is_gimple_min_invariant (new_name
))
3783 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
3787 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
3788 gcc_assert (!new_bb
);
3791 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
3793 new_vec
= build_vector_from_ctor (vectype
, v
);
3795 new_vec
= build_constructor (vectype
, v
);
3796 vec_init
= vect_init_vector (iv_phi
, new_vec
, vectype
, NULL
);
3800 /* Create the vector that holds the step of the induction. */
3801 if (nested_in_vect_loop
)
3802 /* iv_loop is nested in the loop to be vectorized. Generate:
3803 vec_step = [S, S, S, S] */
3804 new_name
= step_expr
;
3807 /* iv_loop is the loop to be vectorized. Generate:
3808 vec_step = [VF*S, VF*S, VF*S, VF*S] */
3809 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
)))
3811 expr
= build_int_cst (integer_type_node
, vf
);
3812 expr
= fold_convert (TREE_TYPE (step_expr
), expr
);
3815 expr
= build_int_cst (TREE_TYPE (step_expr
), vf
);
3816 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
3818 if (TREE_CODE (step_expr
) == SSA_NAME
)
3819 new_name
= vect_init_vector (iv_phi
, new_name
,
3820 TREE_TYPE (step_expr
), NULL
);
3823 t
= unshare_expr (new_name
);
3824 gcc_assert (CONSTANT_CLASS_P (new_name
)
3825 || TREE_CODE (new_name
) == SSA_NAME
);
3826 stepvectype
= get_vectype_for_scalar_type (TREE_TYPE (new_name
));
3827 gcc_assert (stepvectype
);
3828 new_vec
= build_vector_from_val (stepvectype
, t
);
3829 vec_step
= vect_init_vector (iv_phi
, new_vec
, stepvectype
, NULL
);
3832 /* Create the following def-use cycle:
3837 vec_iv = PHI <vec_init, vec_loop>
3841 vec_loop = vec_iv + vec_step; */
3843 /* Create the induction-phi that defines the induction-operand. */
3844 vec_dest
= vect_get_new_vect_var (vectype
, vect_simple_var
, "vec_iv_");
3845 induction_phi
= create_phi_node (vec_dest
, iv_loop
->header
);
3846 set_vinfo_for_stmt (induction_phi
,
3847 new_stmt_vec_info (induction_phi
, loop_vinfo
));
3848 induc_def
= PHI_RESULT (induction_phi
);
3850 /* Create the iv update inside the loop */
3851 new_stmt
= gimple_build_assign (vec_dest
, PLUS_EXPR
, induc_def
, vec_step
);
3852 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
3853 gimple_assign_set_lhs (new_stmt
, vec_def
);
3854 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3855 set_vinfo_for_stmt (new_stmt
, new_stmt_vec_info (new_stmt
, loop_vinfo
));
3857 /* Set the arguments of the phi node: */
3858 add_phi_arg (induction_phi
, vec_init
, pe
, UNKNOWN_LOCATION
);
3859 add_phi_arg (induction_phi
, vec_def
, loop_latch_edge (iv_loop
),
3863 /* In case that vectorization factor (VF) is bigger than the number
3864 of elements that we can fit in a vectype (nunits), we have to generate
3865 more than one vector stmt - i.e - we need to "unroll" the
3866 vector stmt by a factor VF/nunits. For more details see documentation
3867 in vectorizable_operation. */
3871 stmt_vec_info prev_stmt_vinfo
;
3872 /* FORNOW. This restriction should be relaxed. */
3873 gcc_assert (!nested_in_vect_loop
);
3875 /* Create the vector that holds the step of the induction. */
3876 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
)))
3878 expr
= build_int_cst (integer_type_node
, nunits
);
3879 expr
= fold_convert (TREE_TYPE (step_expr
), expr
);
3882 expr
= build_int_cst (TREE_TYPE (step_expr
), nunits
);
3883 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
3885 if (TREE_CODE (step_expr
) == SSA_NAME
)
3886 new_name
= vect_init_vector (iv_phi
, new_name
,
3887 TREE_TYPE (step_expr
), NULL
);
3888 t
= unshare_expr (new_name
);
3889 gcc_assert (CONSTANT_CLASS_P (new_name
)
3890 || TREE_CODE (new_name
) == SSA_NAME
);
3891 new_vec
= build_vector_from_val (stepvectype
, t
);
3892 vec_step
= vect_init_vector (iv_phi
, new_vec
, stepvectype
, NULL
);
3894 vec_def
= induc_def
;
3895 prev_stmt_vinfo
= vinfo_for_stmt (induction_phi
);
3896 for (i
= 1; i
< ncopies
; i
++)
3898 /* vec_i = vec_prev + vec_step */
3899 new_stmt
= gimple_build_assign (vec_dest
, PLUS_EXPR
,
3901 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
3902 gimple_assign_set_lhs (new_stmt
, vec_def
);
3904 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3905 if (!useless_type_conversion_p (resvectype
, vectype
))
3908 = gimple_build_assign
3909 (vect_get_new_vect_var (resvectype
, vect_simple_var
,
3912 build1 (VIEW_CONVERT_EXPR
, resvectype
,
3913 gimple_assign_lhs (new_stmt
)));
3914 gimple_assign_set_lhs (new_stmt
,
3916 (gimple_assign_lhs (new_stmt
), new_stmt
));
3917 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3919 set_vinfo_for_stmt (new_stmt
,
3920 new_stmt_vec_info (new_stmt
, loop_vinfo
));
3921 STMT_VINFO_RELATED_STMT (prev_stmt_vinfo
) = new_stmt
;
3922 prev_stmt_vinfo
= vinfo_for_stmt (new_stmt
);
3926 if (nested_in_vect_loop
)
3928 /* Find the loop-closed exit-phi of the induction, and record
3929 the final vector of induction results: */
3931 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
3933 gimple
*use_stmt
= USE_STMT (use_p
);
3934 if (is_gimple_debug (use_stmt
))
3937 if (!flow_bb_inside_loop_p (iv_loop
, gimple_bb (use_stmt
)))
3939 exit_phi
= use_stmt
;
3945 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (exit_phi
);
3946 /* FORNOW. Currently not supporting the case that an inner-loop induction
3947 is not used in the outer-loop (i.e. only outside the outer-loop). */
3948 gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo
)
3949 && !STMT_VINFO_LIVE_P (stmt_vinfo
));
3951 STMT_VINFO_VEC_STMT (stmt_vinfo
) = new_stmt
;
3952 if (dump_enabled_p ())
3954 dump_printf_loc (MSG_NOTE
, vect_location
,
3955 "vector of inductions after inner-loop:");
3956 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, new_stmt
, 0);
3957 dump_printf (MSG_NOTE
, "\n");
3963 if (dump_enabled_p ())
3965 dump_printf_loc (MSG_NOTE
, vect_location
,
3966 "transform induction: created def-use cycle: ");
3967 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, induction_phi
, 0);
3968 dump_printf (MSG_NOTE
, "\n");
3969 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
3970 SSA_NAME_DEF_STMT (vec_def
), 0);
3971 dump_printf (MSG_NOTE
, "\n");
3974 STMT_VINFO_VEC_STMT (phi_info
) = induction_phi
;
3975 if (!useless_type_conversion_p (resvectype
, vectype
))
3977 new_stmt
= gimple_build_assign (vect_get_new_vect_var (resvectype
,
3981 build1 (VIEW_CONVERT_EXPR
, resvectype
,
3983 induc_def
= make_ssa_name (gimple_assign_lhs (new_stmt
), new_stmt
);
3984 gimple_assign_set_lhs (new_stmt
, induc_def
);
3985 si
= gsi_after_labels (bb
);
3986 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3987 set_vinfo_for_stmt (new_stmt
,
3988 new_stmt_vec_info (new_stmt
, loop_vinfo
));
3989 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_stmt
))
3990 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (induction_phi
));
3997 /* Function get_initial_def_for_reduction
4000 STMT - a stmt that performs a reduction operation in the loop.
4001 INIT_VAL - the initial value of the reduction variable
4004 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
4005 of the reduction (used for adjusting the epilog - see below).
4006 Return a vector variable, initialized according to the operation that STMT
4007 performs. This vector will be used as the initial value of the
4008 vector of partial results.
4010 Option1 (adjust in epilog): Initialize the vector as follows:
4011 add/bit or/xor: [0,0,...,0,0]
4012 mult/bit and: [1,1,...,1,1]
4013 min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
4014 and when necessary (e.g. add/mult case) let the caller know
4015 that it needs to adjust the result by init_val.
4017 Option2: Initialize the vector as follows:
4018 add/bit or/xor: [init_val,0,0,...,0]
4019 mult/bit and: [init_val,1,1,...,1]
4020 min/max/cond_expr: [init_val,init_val,...,init_val]
4021 and no adjustments are needed.
4023 For example, for the following code:
4029 STMT is 's = s + a[i]', and the reduction variable is 's'.
4030 For a vector of 4 units, we want to return either [0,0,0,init_val],
4031 or [0,0,0,0] and let the caller know that it needs to adjust
4032 the result at the end by 'init_val'.
4034 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
4035 initialization vector is simpler (same element in all entries), if
4036 ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
4038 A cost model should help decide between these two schemes. */
4041 get_initial_def_for_reduction (gimple
*stmt
, tree init_val
,
4042 tree
*adjustment_def
)
4044 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
4045 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
4046 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4047 tree scalar_type
= TREE_TYPE (init_val
);
4048 tree vectype
= get_vectype_for_scalar_type (scalar_type
);
4050 enum tree_code code
= gimple_assign_rhs_code (stmt
);
4055 bool nested_in_vect_loop
= false;
4057 REAL_VALUE_TYPE real_init_val
= dconst0
;
4058 int int_init_val
= 0;
4059 gimple
*def_stmt
= NULL
;
4061 gcc_assert (vectype
);
4062 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
4064 gcc_assert (POINTER_TYPE_P (scalar_type
) || INTEGRAL_TYPE_P (scalar_type
)
4065 || SCALAR_FLOAT_TYPE_P (scalar_type
));
4067 if (nested_in_vect_loop_p (loop
, stmt
))
4068 nested_in_vect_loop
= true;
4070 gcc_assert (loop
== (gimple_bb (stmt
))->loop_father
);
4072 /* In case of double reduction we only create a vector variable to be put
4073 in the reduction phi node. The actual statement creation is done in
4074 vect_create_epilog_for_reduction. */
4075 if (adjustment_def
&& nested_in_vect_loop
4076 && TREE_CODE (init_val
) == SSA_NAME
4077 && (def_stmt
= SSA_NAME_DEF_STMT (init_val
))
4078 && gimple_code (def_stmt
) == GIMPLE_PHI
4079 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
4080 && vinfo_for_stmt (def_stmt
)
4081 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
4082 == vect_double_reduction_def
)
4084 *adjustment_def
= NULL
;
4085 return vect_create_destination_var (init_val
, vectype
);
4088 if (TREE_CONSTANT (init_val
))
4090 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
4091 init_value
= build_real (scalar_type
, TREE_REAL_CST (init_val
));
4093 init_value
= build_int_cst (scalar_type
, TREE_INT_CST_LOW (init_val
));
4096 init_value
= init_val
;
4100 case WIDEN_SUM_EXPR
:
4109 /* ADJUSMENT_DEF is NULL when called from
4110 vect_create_epilog_for_reduction to vectorize double reduction. */
4113 if (nested_in_vect_loop
)
4114 *adjustment_def
= vect_get_vec_def_for_operand (init_val
, stmt
);
4116 *adjustment_def
= init_val
;
4119 if (code
== MULT_EXPR
)
4121 real_init_val
= dconst1
;
4125 if (code
== BIT_AND_EXPR
)
4128 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
4129 def_for_init
= build_real (scalar_type
, real_init_val
);
4131 def_for_init
= build_int_cst (scalar_type
, int_init_val
);
4133 /* Create a vector of '0' or '1' except the first element. */
4134 elts
= XALLOCAVEC (tree
, nunits
);
4135 for (i
= nunits
- 2; i
>= 0; --i
)
4136 elts
[i
+ 1] = def_for_init
;
4138 /* Option1: the first element is '0' or '1' as well. */
4141 elts
[0] = def_for_init
;
4142 init_def
= build_vector (vectype
, elts
);
4146 /* Option2: the first element is INIT_VAL. */
4148 if (TREE_CONSTANT (init_val
))
4149 init_def
= build_vector (vectype
, elts
);
4152 vec
<constructor_elt
, va_gc
> *v
;
4153 vec_alloc (v
, nunits
);
4154 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, init_val
);
4155 for (i
= 1; i
< nunits
; ++i
)
4156 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[i
]);
4157 init_def
= build_constructor (vectype
, v
);
4167 *adjustment_def
= NULL_TREE
;
4168 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_vinfo
) != COND_REDUCTION
)
4170 init_def
= vect_get_vec_def_for_operand (init_val
, stmt
);
4174 init_def
= build_vector_from_val (vectype
, init_value
);
4184 /* Function vect_create_epilog_for_reduction
4186 Create code at the loop-epilog to finalize the result of a reduction
4189 VECT_DEFS is list of vector of partial results, i.e., the lhs's of vector
4190 reduction statements.
4191 STMT is the scalar reduction stmt that is being vectorized.
4192 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
4193 number of elements that we can fit in a vectype (nunits). In this case
4194 we have to generate more than one vector stmt - i.e - we need to "unroll"
4195 the vector stmt by a factor VF/nunits. For more details see documentation
4196 in vectorizable_operation.
4197 REDUC_CODE is the tree-code for the epilog reduction.
4198 REDUCTION_PHIS is a list of the phi-nodes that carry the reduction
4200 REDUC_INDEX is the index of the operand in the right hand side of the
4201 statement that is defined by REDUCTION_PHI.
4202 DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
4203 SLP_NODE is an SLP node containing a group of reduction statements. The
4204 first one in this group is STMT.
4205 INDUCTION_INDEX is the index of the loop for condition reductions.
4206 Otherwise it is undefined.
4209 1. Creates the reduction def-use cycles: sets the arguments for
4211 The loop-entry argument is the vectorized initial-value of the reduction.
4212 The loop-latch argument is taken from VECT_DEFS - the vector of partial
4214 2. "Reduces" each vector of partial results VECT_DEFS into a single result,
4215 by applying the operation specified by REDUC_CODE if available, or by
4216 other means (whole-vector shifts or a scalar loop).
4217 The function also creates a new phi node at the loop exit to preserve
4218 loop-closed form, as illustrated below.
4220 The flow at the entry to this function:
4223 vec_def = phi <null, null> # REDUCTION_PHI
4224 VECT_DEF = vector_stmt # vectorized form of STMT
4225 s_loop = scalar_stmt # (scalar) STMT
4227 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4231 The above is transformed by this function into:
4234 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
4235 VECT_DEF = vector_stmt # vectorized form of STMT
4236 s_loop = scalar_stmt # (scalar) STMT
4238 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4239 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4240 v_out2 = reduce <v_out1>
4241 s_out3 = extract_field <v_out2, 0>
4242 s_out4 = adjust_result <s_out3>
4248 vect_create_epilog_for_reduction (vec
<tree
> vect_defs
, gimple
*stmt
,
4249 int ncopies
, enum tree_code reduc_code
,
4250 vec
<gimple
*> reduction_phis
,
4251 int reduc_index
, bool double_reduc
,
4252 slp_tree slp_node
, tree induction_index
)
4254 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
4255 stmt_vec_info prev_phi_info
;
4258 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
4259 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
), *outer_loop
= NULL
;
4260 basic_block exit_bb
;
4263 gimple
*new_phi
= NULL
, *phi
;
4264 gimple_stmt_iterator exit_gsi
;
4266 tree new_temp
= NULL_TREE
, new_dest
, new_name
, new_scalar_dest
;
4267 gimple
*epilog_stmt
= NULL
;
4268 enum tree_code code
= gimple_assign_rhs_code (stmt
);
4271 tree adjustment_def
= NULL
;
4272 tree vec_initial_def
= NULL
;
4273 tree reduction_op
, expr
, def
, initial_def
= NULL
;
4274 tree orig_name
, scalar_result
;
4275 imm_use_iterator imm_iter
, phi_imm_iter
;
4276 use_operand_p use_p
, phi_use_p
;
4277 gimple
*use_stmt
, *orig_stmt
, *reduction_phi
= NULL
;
4278 bool nested_in_vect_loop
= false;
4279 auto_vec
<gimple
*> new_phis
;
4280 auto_vec
<gimple
*> inner_phis
;
4281 enum vect_def_type dt
= vect_unknown_def_type
;
4283 auto_vec
<tree
> scalar_results
;
4284 unsigned int group_size
= 1, k
, ratio
;
4285 auto_vec
<tree
> vec_initial_defs
;
4286 auto_vec
<gimple
*> phis
;
4287 bool slp_reduc
= false;
4288 tree new_phi_result
;
4289 gimple
*inner_phi
= NULL
;
4292 group_size
= SLP_TREE_SCALAR_STMTS (slp_node
).length ();
4294 if (nested_in_vect_loop_p (loop
, stmt
))
4298 nested_in_vect_loop
= true;
4299 gcc_assert (!slp_node
);
4302 reduction_op
= get_reduction_op (stmt
, reduc_index
);
4304 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
4305 gcc_assert (vectype
);
4306 mode
= TYPE_MODE (vectype
);
4308 /* 1. Create the reduction def-use cycle:
4309 Set the arguments of REDUCTION_PHIS, i.e., transform
4312 vec_def = phi <null, null> # REDUCTION_PHI
4313 VECT_DEF = vector_stmt # vectorized form of STMT
4319 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
4320 VECT_DEF = vector_stmt # vectorized form of STMT
4323 (in case of SLP, do it for all the phis). */
4325 /* Get the loop-entry arguments. */
4327 vect_get_vec_defs (reduction_op
, NULL_TREE
, stmt
, &vec_initial_defs
,
4328 NULL
, slp_node
, reduc_index
);
4331 /* Get at the scalar def before the loop, that defines the initial value
4332 of the reduction variable. */
4333 gimple
*def_stmt
= SSA_NAME_DEF_STMT (reduction_op
);
4334 initial_def
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
4335 loop_preheader_edge (loop
));
4336 vec_initial_defs
.create (1);
4337 vec_initial_def
= get_initial_def_for_reduction (stmt
, initial_def
,
4339 vec_initial_defs
.quick_push (vec_initial_def
);
4342 /* Set phi nodes arguments. */
4343 FOR_EACH_VEC_ELT (reduction_phis
, i
, phi
)
4345 tree vec_init_def
, def
;
4347 vec_init_def
= force_gimple_operand (vec_initial_defs
[i
], &stmts
,
4349 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
4351 for (j
= 0; j
< ncopies
; j
++)
4353 /* Set the loop-entry arg of the reduction-phi. */
4355 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
4356 == INTEGER_INDUC_COND_REDUCTION
)
4358 /* Initialise the reduction phi to zero. This prevents initial
4359 values of non-zero interferring with the reduction op. */
4360 gcc_assert (ncopies
== 1);
4361 gcc_assert (i
== 0);
4363 tree vec_init_def_type
= TREE_TYPE (vec_init_def
);
4364 tree zero_vec
= build_zero_cst (vec_init_def_type
);
4366 add_phi_arg (as_a
<gphi
*> (phi
), zero_vec
,
4367 loop_preheader_edge (loop
), UNKNOWN_LOCATION
);
4370 add_phi_arg (as_a
<gphi
*> (phi
), vec_init_def
,
4371 loop_preheader_edge (loop
), UNKNOWN_LOCATION
);
4373 /* Set the loop-latch arg for the reduction-phi. */
4375 def
= vect_get_vec_def_for_stmt_copy (vect_unknown_def_type
, def
);
4377 add_phi_arg (as_a
<gphi
*> (phi
), def
, loop_latch_edge (loop
),
4380 if (dump_enabled_p ())
4382 dump_printf_loc (MSG_NOTE
, vect_location
,
4383 "transform reduction: created def-use cycle: ");
4384 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
4385 dump_printf (MSG_NOTE
, "\n");
4386 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, SSA_NAME_DEF_STMT (def
), 0);
4387 dump_printf (MSG_NOTE
, "\n");
4390 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
4394 /* 2. Create epilog code.
4395 The reduction epilog code operates across the elements of the vector
4396 of partial results computed by the vectorized loop.
4397 The reduction epilog code consists of:
4399 step 1: compute the scalar result in a vector (v_out2)
4400 step 2: extract the scalar result (s_out3) from the vector (v_out2)
4401 step 3: adjust the scalar result (s_out3) if needed.
4403 Step 1 can be accomplished using one the following three schemes:
4404 (scheme 1) using reduc_code, if available.
4405 (scheme 2) using whole-vector shifts, if available.
4406 (scheme 3) using a scalar loop. In this case steps 1+2 above are
4409 The overall epilog code looks like this:
4411 s_out0 = phi <s_loop> # original EXIT_PHI
4412 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4413 v_out2 = reduce <v_out1> # step 1
4414 s_out3 = extract_field <v_out2, 0> # step 2
4415 s_out4 = adjust_result <s_out3> # step 3
4417 (step 3 is optional, and steps 1 and 2 may be combined).
4418 Lastly, the uses of s_out0 are replaced by s_out4. */
4421 /* 2.1 Create new loop-exit-phis to preserve loop-closed form:
4422 v_out1 = phi <VECT_DEF>
4423 Store them in NEW_PHIS. */
4425 exit_bb
= single_exit (loop
)->dest
;
4426 prev_phi_info
= NULL
;
4427 new_phis
.create (vect_defs
.length ());
4428 FOR_EACH_VEC_ELT (vect_defs
, i
, def
)
4430 for (j
= 0; j
< ncopies
; j
++)
4432 tree new_def
= copy_ssa_name (def
);
4433 phi
= create_phi_node (new_def
, exit_bb
);
4434 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, loop_vinfo
));
4436 new_phis
.quick_push (phi
);
4439 def
= vect_get_vec_def_for_stmt_copy (dt
, def
);
4440 STMT_VINFO_RELATED_STMT (prev_phi_info
) = phi
;
4443 SET_PHI_ARG_DEF (phi
, single_exit (loop
)->dest_idx
, def
);
4444 prev_phi_info
= vinfo_for_stmt (phi
);
4448 /* The epilogue is created for the outer-loop, i.e., for the loop being
4449 vectorized. Create exit phis for the outer loop. */
4453 exit_bb
= single_exit (loop
)->dest
;
4454 inner_phis
.create (vect_defs
.length ());
4455 FOR_EACH_VEC_ELT (new_phis
, i
, phi
)
4457 tree new_result
= copy_ssa_name (PHI_RESULT (phi
));
4458 gphi
*outer_phi
= create_phi_node (new_result
, exit_bb
);
4459 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
4461 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
4463 inner_phis
.quick_push (phi
);
4464 new_phis
[i
] = outer_phi
;
4465 prev_phi_info
= vinfo_for_stmt (outer_phi
);
4466 while (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
)))
4468 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
4469 new_result
= copy_ssa_name (PHI_RESULT (phi
));
4470 outer_phi
= create_phi_node (new_result
, exit_bb
);
4471 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
4473 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
4475 STMT_VINFO_RELATED_STMT (prev_phi_info
) = outer_phi
;
4476 prev_phi_info
= vinfo_for_stmt (outer_phi
);
4481 exit_gsi
= gsi_after_labels (exit_bb
);
4483 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
4484 (i.e. when reduc_code is not available) and in the final adjustment
4485 code (if needed). Also get the original scalar reduction variable as
4486 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
4487 represents a reduction pattern), the tree-code and scalar-def are
4488 taken from the original stmt that the pattern-stmt (STMT) replaces.
4489 Otherwise (it is a regular reduction) - the tree-code and scalar-def
4490 are taken from STMT. */
4492 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
4495 /* Regular reduction */
4500 /* Reduction pattern */
4501 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (orig_stmt
);
4502 gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
));
4503 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo
) == stmt
);
4506 code
= gimple_assign_rhs_code (orig_stmt
);
4507 /* For MINUS_EXPR the initial vector is [init_val,0,...,0], therefore,
4508 partial results are added and not subtracted. */
4509 if (code
== MINUS_EXPR
)
4512 scalar_dest
= gimple_assign_lhs (orig_stmt
);
4513 scalar_type
= TREE_TYPE (scalar_dest
);
4514 scalar_results
.create (group_size
);
4515 new_scalar_dest
= vect_create_destination_var (scalar_dest
, NULL
);
4516 bitsize
= TYPE_SIZE (scalar_type
);
4518 /* In case this is a reduction in an inner-loop while vectorizing an outer
4519 loop - we don't need to extract a single scalar result at the end of the
4520 inner-loop (unless it is double reduction, i.e., the use of reduction is
4521 outside the outer-loop). The final vector of partial results will be used
4522 in the vectorized outer-loop, or reduced to a scalar result at the end of
4524 if (nested_in_vect_loop
&& !double_reduc
)
4525 goto vect_finalize_reduction
;
4527 /* SLP reduction without reduction chain, e.g.,
4531 b2 = operation (b1) */
4532 slp_reduc
= (slp_node
&& !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)));
4534 /* In case of reduction chain, e.g.,
4537 a3 = operation (a2),
4539 we may end up with more than one vector result. Here we reduce them to
4541 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4543 tree first_vect
= PHI_RESULT (new_phis
[0]);
4545 gassign
*new_vec_stmt
= NULL
;
4547 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4548 for (k
= 1; k
< new_phis
.length (); k
++)
4550 gimple
*next_phi
= new_phis
[k
];
4551 tree second_vect
= PHI_RESULT (next_phi
);
4553 tmp
= build2 (code
, vectype
, first_vect
, second_vect
);
4554 new_vec_stmt
= gimple_build_assign (vec_dest
, tmp
);
4555 first_vect
= make_ssa_name (vec_dest
, new_vec_stmt
);
4556 gimple_assign_set_lhs (new_vec_stmt
, first_vect
);
4557 gsi_insert_before (&exit_gsi
, new_vec_stmt
, GSI_SAME_STMT
);
4560 new_phi_result
= first_vect
;
4563 new_phis
.truncate (0);
4564 new_phis
.safe_push (new_vec_stmt
);
4568 new_phi_result
= PHI_RESULT (new_phis
[0]);
4570 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
)
4572 /* For condition reductions, we have a vector (NEW_PHI_RESULT) containing
4573 various data values where the condition matched and another vector
4574 (INDUCTION_INDEX) containing all the indexes of those matches. We
4575 need to extract the last matching index (which will be the index with
4576 highest value) and use this to index into the data vector.
4577 For the case where there were no matches, the data vector will contain
4578 all default values and the index vector will be all zeros. */
4580 /* Get various versions of the type of the vector of indexes. */
4581 tree index_vec_type
= TREE_TYPE (induction_index
);
4582 gcc_checking_assert (TYPE_UNSIGNED (index_vec_type
));
4583 tree index_scalar_type
= TREE_TYPE (index_vec_type
);
4584 tree index_vec_cmp_type
= build_same_sized_truth_vector_type
4587 /* Get an unsigned integer version of the type of the data vector. */
4588 int scalar_precision
= GET_MODE_PRECISION (TYPE_MODE (scalar_type
));
4589 tree scalar_type_unsigned
= make_unsigned_type (scalar_precision
);
4590 tree vectype_unsigned
= build_vector_type
4591 (scalar_type_unsigned
, TYPE_VECTOR_SUBPARTS (vectype
));
4593 /* First we need to create a vector (ZERO_VEC) of zeros and another
4594 vector (MAX_INDEX_VEC) filled with the last matching index, which we
4595 can create using a MAX reduction and then expanding.
4596 In the case where the loop never made any matches, the max index will
4599 /* Vector of {0, 0, 0,...}. */
4600 tree zero_vec
= make_ssa_name (vectype
);
4601 tree zero_vec_rhs
= build_zero_cst (vectype
);
4602 gimple
*zero_vec_stmt
= gimple_build_assign (zero_vec
, zero_vec_rhs
);
4603 gsi_insert_before (&exit_gsi
, zero_vec_stmt
, GSI_SAME_STMT
);
4605 /* Find maximum value from the vector of found indexes. */
4606 tree max_index
= make_ssa_name (index_scalar_type
);
4607 gimple
*max_index_stmt
= gimple_build_assign (max_index
, REDUC_MAX_EXPR
,
4609 gsi_insert_before (&exit_gsi
, max_index_stmt
, GSI_SAME_STMT
);
4611 /* Vector of {max_index, max_index, max_index,...}. */
4612 tree max_index_vec
= make_ssa_name (index_vec_type
);
4613 tree max_index_vec_rhs
= build_vector_from_val (index_vec_type
,
4615 gimple
*max_index_vec_stmt
= gimple_build_assign (max_index_vec
,
4617 gsi_insert_before (&exit_gsi
, max_index_vec_stmt
, GSI_SAME_STMT
);
4619 /* Next we compare the new vector (MAX_INDEX_VEC) full of max indexes
4620 with the vector (INDUCTION_INDEX) of found indexes, choosing values
4621 from the data vector (NEW_PHI_RESULT) for matches, 0 (ZERO_VEC)
4622 otherwise. Only one value should match, resulting in a vector
4623 (VEC_COND) with one data value and the rest zeros.
4624 In the case where the loop never made any matches, every index will
4625 match, resulting in a vector with all data values (which will all be
4626 the default value). */
4628 /* Compare the max index vector to the vector of found indexes to find
4629 the position of the max value. */
4630 tree vec_compare
= make_ssa_name (index_vec_cmp_type
);
4631 gimple
*vec_compare_stmt
= gimple_build_assign (vec_compare
, EQ_EXPR
,
4634 gsi_insert_before (&exit_gsi
, vec_compare_stmt
, GSI_SAME_STMT
);
4636 /* Use the compare to choose either values from the data vector or
4638 tree vec_cond
= make_ssa_name (vectype
);
4639 gimple
*vec_cond_stmt
= gimple_build_assign (vec_cond
, VEC_COND_EXPR
,
4640 vec_compare
, new_phi_result
,
4642 gsi_insert_before (&exit_gsi
, vec_cond_stmt
, GSI_SAME_STMT
);
4644 /* Finally we need to extract the data value from the vector (VEC_COND)
4645 into a scalar (MATCHED_DATA_REDUC). Logically we want to do a OR
4646 reduction, but because this doesn't exist, we can use a MAX reduction
4647 instead. The data value might be signed or a float so we need to cast
4649 In the case where the loop never made any matches, the data values are
4650 all identical, and so will reduce down correctly. */
4652 /* Make the matched data values unsigned. */
4653 tree vec_cond_cast
= make_ssa_name (vectype_unsigned
);
4654 tree vec_cond_cast_rhs
= build1 (VIEW_CONVERT_EXPR
, vectype_unsigned
,
4656 gimple
*vec_cond_cast_stmt
= gimple_build_assign (vec_cond_cast
,
4659 gsi_insert_before (&exit_gsi
, vec_cond_cast_stmt
, GSI_SAME_STMT
);
4661 /* Reduce down to a scalar value. */
4662 tree data_reduc
= make_ssa_name (scalar_type_unsigned
);
4663 optab ot
= optab_for_tree_code (REDUC_MAX_EXPR
, vectype_unsigned
,
4665 gcc_assert (optab_handler (ot
, TYPE_MODE (vectype_unsigned
))
4666 != CODE_FOR_nothing
);
4667 gimple
*data_reduc_stmt
= gimple_build_assign (data_reduc
,
4670 gsi_insert_before (&exit_gsi
, data_reduc_stmt
, GSI_SAME_STMT
);
4672 /* Convert the reduced value back to the result type and set as the
4674 tree data_reduc_cast
= build1 (VIEW_CONVERT_EXPR
, scalar_type
,
4676 epilog_stmt
= gimple_build_assign (new_scalar_dest
, data_reduc_cast
);
4677 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4678 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4679 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4680 scalar_results
.safe_push (new_temp
);
4683 /* 2.3 Create the reduction code, using one of the three schemes described
4684 above. In SLP we simply need to extract all the elements from the
4685 vector (without reducing them), so we use scalar shifts. */
4686 else if (reduc_code
!= ERROR_MARK
&& !slp_reduc
)
4691 /*** Case 1: Create:
4692 v_out2 = reduc_expr <v_out1> */
4694 if (dump_enabled_p ())
4695 dump_printf_loc (MSG_NOTE
, vect_location
,
4696 "Reduce using direct vector reduction.\n");
4698 vec_elem_type
= TREE_TYPE (TREE_TYPE (new_phi_result
));
4699 if (!useless_type_conversion_p (scalar_type
, vec_elem_type
))
4702 vect_create_destination_var (scalar_dest
, vec_elem_type
);
4703 tmp
= build1 (reduc_code
, vec_elem_type
, new_phi_result
);
4704 epilog_stmt
= gimple_build_assign (tmp_dest
, tmp
);
4705 new_temp
= make_ssa_name (tmp_dest
, epilog_stmt
);
4706 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4707 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4709 tmp
= build1 (NOP_EXPR
, scalar_type
, new_temp
);
4712 tmp
= build1 (reduc_code
, scalar_type
, new_phi_result
);
4714 epilog_stmt
= gimple_build_assign (new_scalar_dest
, tmp
);
4715 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4716 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4717 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4719 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
4720 == INTEGER_INDUC_COND_REDUCTION
)
4722 /* Earlier we set the initial value to be zero. Check the result
4723 and if it is zero then replace with the original initial
4725 tree zero
= build_zero_cst (scalar_type
);
4726 tree zcompare
= build2 (EQ_EXPR
, boolean_type_node
, new_temp
, zero
);
4728 tmp
= make_ssa_name (new_scalar_dest
);
4729 epilog_stmt
= gimple_build_assign (tmp
, COND_EXPR
, zcompare
,
4730 initial_def
, new_temp
);
4731 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4735 scalar_results
.safe_push (new_temp
);
4739 bool reduce_with_shift
= have_whole_vector_shift (mode
);
4740 int element_bitsize
= tree_to_uhwi (bitsize
);
4741 int vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
4744 /* Regardless of whether we have a whole vector shift, if we're
4745 emulating the operation via tree-vect-generic, we don't want
4746 to use it. Only the first round of the reduction is likely
4747 to still be profitable via emulation. */
4748 /* ??? It might be better to emit a reduction tree code here, so that
4749 tree-vect-generic can expand the first round via bit tricks. */
4750 if (!VECTOR_MODE_P (mode
))
4751 reduce_with_shift
= false;
4754 optab optab
= optab_for_tree_code (code
, vectype
, optab_default
);
4755 if (optab_handler (optab
, mode
) == CODE_FOR_nothing
)
4756 reduce_with_shift
= false;
4759 if (reduce_with_shift
&& !slp_reduc
)
4761 int nelements
= vec_size_in_bits
/ element_bitsize
;
4762 unsigned char *sel
= XALLOCAVEC (unsigned char, nelements
);
4766 tree zero_vec
= build_zero_cst (vectype
);
4767 /*** Case 2: Create:
4768 for (offset = nelements/2; offset >= 1; offset/=2)
4770 Create: va' = vec_shift <va, offset>
4771 Create: va = vop <va, va'>
4776 if (dump_enabled_p ())
4777 dump_printf_loc (MSG_NOTE
, vect_location
,
4778 "Reduce using vector shifts\n");
4780 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4781 new_temp
= new_phi_result
;
4782 for (elt_offset
= nelements
/ 2;
4786 calc_vec_perm_mask_for_shift (mode
, elt_offset
, sel
);
4787 tree mask
= vect_gen_perm_mask_any (vectype
, sel
);
4788 epilog_stmt
= gimple_build_assign (vec_dest
, VEC_PERM_EXPR
,
4789 new_temp
, zero_vec
, mask
);
4790 new_name
= make_ssa_name (vec_dest
, epilog_stmt
);
4791 gimple_assign_set_lhs (epilog_stmt
, new_name
);
4792 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4794 epilog_stmt
= gimple_build_assign (vec_dest
, code
, new_name
,
4796 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
4797 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4798 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4801 /* 2.4 Extract the final scalar result. Create:
4802 s_out3 = extract_field <v_out2, bitpos> */
4804 if (dump_enabled_p ())
4805 dump_printf_loc (MSG_NOTE
, vect_location
,
4806 "extract scalar result\n");
4808 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, new_temp
,
4809 bitsize
, bitsize_zero_node
);
4810 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4811 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4812 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4813 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4814 scalar_results
.safe_push (new_temp
);
4818 /*** Case 3: Create:
4819 s = extract_field <v_out2, 0>
4820 for (offset = element_size;
4821 offset < vector_size;
4822 offset += element_size;)
4824 Create: s' = extract_field <v_out2, offset>
4825 Create: s = op <s, s'> // For non SLP cases
4828 if (dump_enabled_p ())
4829 dump_printf_loc (MSG_NOTE
, vect_location
,
4830 "Reduce using scalar code.\n");
4832 vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
4833 FOR_EACH_VEC_ELT (new_phis
, i
, new_phi
)
4836 if (gimple_code (new_phi
) == GIMPLE_PHI
)
4837 vec_temp
= PHI_RESULT (new_phi
);
4839 vec_temp
= gimple_assign_lhs (new_phi
);
4840 tree rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
, bitsize
,
4842 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4843 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4844 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4845 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4847 /* In SLP we don't need to apply reduction operation, so we just
4848 collect s' values in SCALAR_RESULTS. */
4850 scalar_results
.safe_push (new_temp
);
4852 for (bit_offset
= element_bitsize
;
4853 bit_offset
< vec_size_in_bits
;
4854 bit_offset
+= element_bitsize
)
4856 tree bitpos
= bitsize_int (bit_offset
);
4857 tree rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
,
4860 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4861 new_name
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4862 gimple_assign_set_lhs (epilog_stmt
, new_name
);
4863 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4867 /* In SLP we don't need to apply reduction operation, so
4868 we just collect s' values in SCALAR_RESULTS. */
4869 new_temp
= new_name
;
4870 scalar_results
.safe_push (new_name
);
4874 epilog_stmt
= gimple_build_assign (new_scalar_dest
, code
,
4875 new_name
, new_temp
);
4876 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4877 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4878 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4883 /* The only case where we need to reduce scalar results in SLP, is
4884 unrolling. If the size of SCALAR_RESULTS is greater than
4885 GROUP_SIZE, we reduce them combining elements modulo
4889 tree res
, first_res
, new_res
;
4892 /* Reduce multiple scalar results in case of SLP unrolling. */
4893 for (j
= group_size
; scalar_results
.iterate (j
, &res
);
4896 first_res
= scalar_results
[j
% group_size
];
4897 new_stmt
= gimple_build_assign (new_scalar_dest
, code
,
4899 new_res
= make_ssa_name (new_scalar_dest
, new_stmt
);
4900 gimple_assign_set_lhs (new_stmt
, new_res
);
4901 gsi_insert_before (&exit_gsi
, new_stmt
, GSI_SAME_STMT
);
4902 scalar_results
[j
% group_size
] = new_res
;
4906 /* Not SLP - we have one scalar to keep in SCALAR_RESULTS. */
4907 scalar_results
.safe_push (new_temp
);
4911 vect_finalize_reduction
:
4916 /* 2.5 Adjust the final result by the initial value of the reduction
4917 variable. (When such adjustment is not needed, then
4918 'adjustment_def' is zero). For example, if code is PLUS we create:
4919 new_temp = loop_exit_def + adjustment_def */
4923 gcc_assert (!slp_reduc
);
4924 if (nested_in_vect_loop
)
4926 new_phi
= new_phis
[0];
4927 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) == VECTOR_TYPE
);
4928 expr
= build2 (code
, vectype
, PHI_RESULT (new_phi
), adjustment_def
);
4929 new_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4933 new_temp
= scalar_results
[0];
4934 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) != VECTOR_TYPE
);
4935 expr
= build2 (code
, scalar_type
, new_temp
, adjustment_def
);
4936 new_dest
= vect_create_destination_var (scalar_dest
, scalar_type
);
4939 epilog_stmt
= gimple_build_assign (new_dest
, expr
);
4940 new_temp
= make_ssa_name (new_dest
, epilog_stmt
);
4941 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4942 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4943 if (nested_in_vect_loop
)
4945 set_vinfo_for_stmt (epilog_stmt
,
4946 new_stmt_vec_info (epilog_stmt
, loop_vinfo
));
4947 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (epilog_stmt
)) =
4948 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_phi
));
4951 scalar_results
.quick_push (new_temp
);
4953 scalar_results
[0] = new_temp
;
4956 scalar_results
[0] = new_temp
;
4958 new_phis
[0] = epilog_stmt
;
4961 /* 2.6 Handle the loop-exit phis. Replace the uses of scalar loop-exit
4962 phis with new adjusted scalar results, i.e., replace use <s_out0>
4967 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4968 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4969 v_out2 = reduce <v_out1>
4970 s_out3 = extract_field <v_out2, 0>
4971 s_out4 = adjust_result <s_out3>
4978 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4979 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4980 v_out2 = reduce <v_out1>
4981 s_out3 = extract_field <v_out2, 0>
4982 s_out4 = adjust_result <s_out3>
4987 /* In SLP reduction chain we reduce vector results into one vector if
4988 necessary, hence we set here GROUP_SIZE to 1. SCALAR_DEST is the LHS of
4989 the last stmt in the reduction chain, since we are looking for the loop
4991 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4993 gimple
*dest_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[group_size
- 1];
4994 /* Handle reduction patterns. */
4995 if (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (dest_stmt
)))
4996 dest_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (dest_stmt
));
4998 scalar_dest
= gimple_assign_lhs (dest_stmt
);
5002 /* In SLP we may have several statements in NEW_PHIS and REDUCTION_PHIS (in
5003 case that GROUP_SIZE is greater than vectorization factor). Therefore, we
5004 need to match SCALAR_RESULTS with corresponding statements. The first
5005 (GROUP_SIZE / number of new vector stmts) scalar results correspond to
5006 the first vector stmt, etc.
5007 (RATIO is equal to (GROUP_SIZE / number of new vector stmts)). */
5008 if (group_size
> new_phis
.length ())
5010 ratio
= group_size
/ new_phis
.length ();
5011 gcc_assert (!(group_size
% new_phis
.length ()));
5016 for (k
= 0; k
< group_size
; k
++)
5020 epilog_stmt
= new_phis
[k
/ ratio
];
5021 reduction_phi
= reduction_phis
[k
/ ratio
];
5023 inner_phi
= inner_phis
[k
/ ratio
];
5028 gimple
*current_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[k
];
5030 orig_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (current_stmt
));
5031 /* SLP statements can't participate in patterns. */
5032 gcc_assert (!orig_stmt
);
5033 scalar_dest
= gimple_assign_lhs (current_stmt
);
5037 /* Find the loop-closed-use at the loop exit of the original scalar
5038 result. (The reduction result is expected to have two immediate uses -
5039 one at the latch block, and one at the loop exit). */
5040 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
5041 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
)))
5042 && !is_gimple_debug (USE_STMT (use_p
)))
5043 phis
.safe_push (USE_STMT (use_p
));
5045 /* While we expect to have found an exit_phi because of loop-closed-ssa
5046 form we can end up without one if the scalar cycle is dead. */
5048 FOR_EACH_VEC_ELT (phis
, i
, exit_phi
)
5052 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
5055 /* FORNOW. Currently not supporting the case that an inner-loop
5056 reduction is not used in the outer-loop (but only outside the
5057 outer-loop), unless it is double reduction. */
5058 gcc_assert ((STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
5059 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
))
5063 STMT_VINFO_VEC_STMT (exit_phi_vinfo
) = inner_phi
;
5065 STMT_VINFO_VEC_STMT (exit_phi_vinfo
) = epilog_stmt
;
5067 || STMT_VINFO_DEF_TYPE (exit_phi_vinfo
)
5068 != vect_double_reduction_def
)
5071 /* Handle double reduction:
5073 stmt1: s1 = phi <s0, s2> - double reduction phi (outer loop)
5074 stmt2: s3 = phi <s1, s4> - (regular) reduc phi (inner loop)
5075 stmt3: s4 = use (s3) - (regular) reduc stmt (inner loop)
5076 stmt4: s2 = phi <s4> - double reduction stmt (outer loop)
5078 At that point the regular reduction (stmt2 and stmt3) is
5079 already vectorized, as well as the exit phi node, stmt4.
5080 Here we vectorize the phi node of double reduction, stmt1, and
5081 update all relevant statements. */
5083 /* Go through all the uses of s2 to find double reduction phi
5084 node, i.e., stmt1 above. */
5085 orig_name
= PHI_RESULT (exit_phi
);
5086 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
5088 stmt_vec_info use_stmt_vinfo
;
5089 stmt_vec_info new_phi_vinfo
;
5090 tree vect_phi_init
, preheader_arg
, vect_phi_res
, init_def
;
5091 basic_block bb
= gimple_bb (use_stmt
);
5094 /* Check that USE_STMT is really double reduction phi
5096 if (gimple_code (use_stmt
) != GIMPLE_PHI
5097 || gimple_phi_num_args (use_stmt
) != 2
5098 || bb
->loop_father
!= outer_loop
)
5100 use_stmt_vinfo
= vinfo_for_stmt (use_stmt
);
5102 || STMT_VINFO_DEF_TYPE (use_stmt_vinfo
)
5103 != vect_double_reduction_def
)
5106 /* Create vector phi node for double reduction:
5107 vs1 = phi <vs0, vs2>
5108 vs1 was created previously in this function by a call to
5109 vect_get_vec_def_for_operand and is stored in
5111 vs2 is defined by INNER_PHI, the vectorized EXIT_PHI;
5112 vs0 is created here. */
5114 /* Create vector phi node. */
5115 vect_phi
= create_phi_node (vec_initial_def
, bb
);
5116 new_phi_vinfo
= new_stmt_vec_info (vect_phi
,
5117 loop_vec_info_for_loop (outer_loop
));
5118 set_vinfo_for_stmt (vect_phi
, new_phi_vinfo
);
5120 /* Create vs0 - initial def of the double reduction phi. */
5121 preheader_arg
= PHI_ARG_DEF_FROM_EDGE (use_stmt
,
5122 loop_preheader_edge (outer_loop
));
5123 init_def
= get_initial_def_for_reduction (stmt
,
5124 preheader_arg
, NULL
);
5125 vect_phi_init
= vect_init_vector (use_stmt
, init_def
,
5128 /* Update phi node arguments with vs0 and vs2. */
5129 add_phi_arg (vect_phi
, vect_phi_init
,
5130 loop_preheader_edge (outer_loop
),
5132 add_phi_arg (vect_phi
, PHI_RESULT (inner_phi
),
5133 loop_latch_edge (outer_loop
), UNKNOWN_LOCATION
);
5134 if (dump_enabled_p ())
5136 dump_printf_loc (MSG_NOTE
, vect_location
,
5137 "created double reduction phi node: ");
5138 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, vect_phi
, 0);
5139 dump_printf (MSG_NOTE
, "\n");
5142 vect_phi_res
= PHI_RESULT (vect_phi
);
5144 /* Replace the use, i.e., set the correct vs1 in the regular
5145 reduction phi node. FORNOW, NCOPIES is always 1, so the
5146 loop is redundant. */
5147 use
= reduction_phi
;
5148 for (j
= 0; j
< ncopies
; j
++)
5150 edge pr_edge
= loop_preheader_edge (loop
);
5151 SET_PHI_ARG_DEF (use
, pr_edge
->dest_idx
, vect_phi_res
);
5152 use
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use
));
5159 if (nested_in_vect_loop
)
5168 /* Find the loop-closed-use at the loop exit of the original scalar
5169 result. (The reduction result is expected to have two immediate uses,
5170 one at the latch block, and one at the loop exit). For double
5171 reductions we are looking for exit phis of the outer loop. */
5172 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
5174 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
5176 if (!is_gimple_debug (USE_STMT (use_p
)))
5177 phis
.safe_push (USE_STMT (use_p
));
5181 if (double_reduc
&& gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
5183 tree phi_res
= PHI_RESULT (USE_STMT (use_p
));
5185 FOR_EACH_IMM_USE_FAST (phi_use_p
, phi_imm_iter
, phi_res
)
5187 if (!flow_bb_inside_loop_p (loop
,
5188 gimple_bb (USE_STMT (phi_use_p
)))
5189 && !is_gimple_debug (USE_STMT (phi_use_p
)))
5190 phis
.safe_push (USE_STMT (phi_use_p
));
5196 FOR_EACH_VEC_ELT (phis
, i
, exit_phi
)
5198 /* Replace the uses: */
5199 orig_name
= PHI_RESULT (exit_phi
);
5200 scalar_result
= scalar_results
[k
];
5201 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
5202 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
5203 SET_USE (use_p
, scalar_result
);
5211 /* Function is_nonwrapping_integer_induction.
5213 Check if STMT (which is part of loop LOOP) both increments and
5214 does not cause overflow. */
5217 is_nonwrapping_integer_induction (gimple
*stmt
, struct loop
*loop
)
5219 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
5220 tree base
= STMT_VINFO_LOOP_PHI_EVOLUTION_BASE_UNCHANGED (stmt_vinfo
);
5221 tree step
= STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
);
5222 tree lhs_type
= TREE_TYPE (gimple_phi_result (stmt
));
5223 widest_int ni
, max_loop_value
, lhs_max
;
5224 bool overflow
= false;
5226 /* Make sure the loop is integer based. */
5227 if (TREE_CODE (base
) != INTEGER_CST
5228 || TREE_CODE (step
) != INTEGER_CST
)
5231 /* Check that the induction increments. */
5232 if (tree_int_cst_sgn (step
) == -1)
5235 /* Check that the max size of the loop will not wrap. */
5237 if (TYPE_OVERFLOW_UNDEFINED (lhs_type
))
5240 if (! max_stmt_executions (loop
, &ni
))
5243 max_loop_value
= wi::mul (wi::to_widest (step
), ni
, TYPE_SIGN (lhs_type
),
5248 max_loop_value
= wi::add (wi::to_widest (base
), max_loop_value
,
5249 TYPE_SIGN (lhs_type
), &overflow
);
5253 return (wi::min_precision (max_loop_value
, TYPE_SIGN (lhs_type
))
5254 <= TYPE_PRECISION (lhs_type
));
5257 /* Function vectorizable_reduction.
5259 Check if STMT performs a reduction operation that can be vectorized.
5260 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
5261 stmt to replace it, put it in VEC_STMT, and insert it at GSI.
5262 Return FALSE if not a vectorizable STMT, TRUE otherwise.
5264 This function also handles reduction idioms (patterns) that have been
5265 recognized in advance during vect_pattern_recog. In this case, STMT may be
5267 X = pattern_expr (arg0, arg1, ..., X)
5268 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
5269 sequence that had been detected and replaced by the pattern-stmt (STMT).
5271 This function also handles reduction of condition expressions, for example:
5272 for (int i = 0; i < N; i++)
5275 This is handled by vectorising the loop and creating an additional vector
5276 containing the loop indexes for which "a[i] < value" was true. In the
5277 function epilogue this is reduced to a single max value and then used to
5278 index into the vector of results.
5280 In some cases of reduction patterns, the type of the reduction variable X is
5281 different than the type of the other arguments of STMT.
5282 In such cases, the vectype that is used when transforming STMT into a vector
5283 stmt is different than the vectype that is used to determine the
5284 vectorization factor, because it consists of a different number of elements
5285 than the actual number of elements that are being operated upon in parallel.
5287 For example, consider an accumulation of shorts into an int accumulator.
5288 On some targets it's possible to vectorize this pattern operating on 8
5289 shorts at a time (hence, the vectype for purposes of determining the
5290 vectorization factor should be V8HI); on the other hand, the vectype that
5291 is used to create the vector form is actually V4SI (the type of the result).
5293 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
5294 indicates what is the actual level of parallelism (V8HI in the example), so
5295 that the right vectorization factor would be derived. This vectype
5296 corresponds to the type of arguments to the reduction stmt, and should *NOT*
5297 be used to create the vectorized stmt. The right vectype for the vectorized
5298 stmt is obtained from the type of the result X:
5299 get_vectype_for_scalar_type (TREE_TYPE (X))
5301 This means that, contrary to "regular" reductions (or "regular" stmts in
5302 general), the following equation:
5303 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
5304 does *NOT* necessarily hold for reduction patterns. */
5307 vectorizable_reduction (gimple
*stmt
, gimple_stmt_iterator
*gsi
,
5308 gimple
**vec_stmt
, slp_tree slp_node
)
5312 tree loop_vec_def0
= NULL_TREE
, loop_vec_def1
= NULL_TREE
;
5313 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
5314 tree vectype_out
= STMT_VINFO_VECTYPE (stmt_info
);
5315 tree vectype_in
= NULL_TREE
;
5316 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
5317 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5318 enum tree_code code
, orig_code
, epilog_reduc_code
;
5319 machine_mode vec_mode
;
5321 optab optab
, reduc_optab
;
5322 tree new_temp
= NULL_TREE
;
5324 enum vect_def_type dt
;
5325 gphi
*new_phi
= NULL
;
5329 stmt_vec_info orig_stmt_info
;
5330 tree expr
= NULL_TREE
;
5334 stmt_vec_info prev_stmt_info
, prev_phi_info
;
5335 bool single_defuse_cycle
= false;
5336 tree reduc_def
= NULL_TREE
;
5337 gimple
*new_stmt
= NULL
;
5340 bool nested_cycle
= false, found_nested_cycle_def
= false;
5341 gimple
*reduc_def_stmt
= NULL
;
5342 bool double_reduc
= false, dummy
;
5344 struct loop
* def_stmt_loop
, *outer_loop
= NULL
;
5346 gimple
*def_arg_stmt
;
5347 auto_vec
<tree
> vec_oprnds0
;
5348 auto_vec
<tree
> vec_oprnds1
;
5349 auto_vec
<tree
> vect_defs
;
5350 auto_vec
<gimple
*> phis
;
5352 tree def0
, def1
, tem
, op0
, op1
= NULL_TREE
;
5353 bool first_p
= true;
5354 tree cr_index_scalar_type
= NULL_TREE
, cr_index_vector_type
= NULL_TREE
;
5355 gimple
*cond_expr_induction_def_stmt
= NULL
;
5357 /* In case of reduction chain we switch to the first stmt in the chain, but
5358 we don't update STMT_INFO, since only the last stmt is marked as reduction
5359 and has reduction properties. */
5360 if (GROUP_FIRST_ELEMENT (stmt_info
)
5361 && GROUP_FIRST_ELEMENT (stmt_info
) != stmt
)
5363 stmt
= GROUP_FIRST_ELEMENT (stmt_info
);
5367 if (nested_in_vect_loop_p (loop
, stmt
))
5371 nested_cycle
= true;
5374 /* 1. Is vectorizable reduction? */
5375 /* Not supportable if the reduction variable is used in the loop, unless
5376 it's a reduction chain. */
5377 if (STMT_VINFO_RELEVANT (stmt_info
) > vect_used_in_outer
5378 && !GROUP_FIRST_ELEMENT (stmt_info
))
5381 /* Reductions that are not used even in an enclosing outer-loop,
5382 are expected to be "live" (used out of the loop). */
5383 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
5384 && !STMT_VINFO_LIVE_P (stmt_info
))
5387 /* Make sure it was already recognized as a reduction computation. */
5388 if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) != vect_reduction_def
5389 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) != vect_nested_cycle
)
5392 /* 2. Has this been recognized as a reduction pattern?
5394 Check if STMT represents a pattern that has been recognized
5395 in earlier analysis stages. For stmts that represent a pattern,
5396 the STMT_VINFO_RELATED_STMT field records the last stmt in
5397 the original sequence that constitutes the pattern. */
5399 orig_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt
));
5402 orig_stmt_info
= vinfo_for_stmt (orig_stmt
);
5403 gcc_assert (STMT_VINFO_IN_PATTERN_P (orig_stmt_info
));
5404 gcc_assert (!STMT_VINFO_IN_PATTERN_P (stmt_info
));
5407 /* 3. Check the operands of the operation. The first operands are defined
5408 inside the loop body. The last operand is the reduction variable,
5409 which is defined by the loop-header-phi. */
5411 gcc_assert (is_gimple_assign (stmt
));
5414 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
5416 case GIMPLE_SINGLE_RHS
:
5417 op_type
= TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
));
5418 if (op_type
== ternary_op
)
5420 tree rhs
= gimple_assign_rhs1 (stmt
);
5421 ops
[0] = TREE_OPERAND (rhs
, 0);
5422 ops
[1] = TREE_OPERAND (rhs
, 1);
5423 ops
[2] = TREE_OPERAND (rhs
, 2);
5424 code
= TREE_CODE (rhs
);
5430 case GIMPLE_BINARY_RHS
:
5431 code
= gimple_assign_rhs_code (stmt
);
5432 op_type
= TREE_CODE_LENGTH (code
);
5433 gcc_assert (op_type
== binary_op
);
5434 ops
[0] = gimple_assign_rhs1 (stmt
);
5435 ops
[1] = gimple_assign_rhs2 (stmt
);
5438 case GIMPLE_TERNARY_RHS
:
5439 code
= gimple_assign_rhs_code (stmt
);
5440 op_type
= TREE_CODE_LENGTH (code
);
5441 gcc_assert (op_type
== ternary_op
);
5442 ops
[0] = gimple_assign_rhs1 (stmt
);
5443 ops
[1] = gimple_assign_rhs2 (stmt
);
5444 ops
[2] = gimple_assign_rhs3 (stmt
);
5447 case GIMPLE_UNARY_RHS
:
5453 /* The default is that the reduction variable is the last in statement. */
5454 int reduc_index
= op_type
- 1;
5455 if (code
== MINUS_EXPR
)
5458 if (code
== COND_EXPR
&& slp_node
)
5461 scalar_dest
= gimple_assign_lhs (stmt
);
5462 scalar_type
= TREE_TYPE (scalar_dest
);
5463 if (!POINTER_TYPE_P (scalar_type
) && !INTEGRAL_TYPE_P (scalar_type
)
5464 && !SCALAR_FLOAT_TYPE_P (scalar_type
))
5467 /* Do not try to vectorize bit-precision reductions. */
5468 if ((TYPE_PRECISION (scalar_type
)
5469 != GET_MODE_PRECISION (TYPE_MODE (scalar_type
))))
5472 /* All uses but the last are expected to be defined in the loop.
5473 The last use is the reduction variable. In case of nested cycle this
5474 assumption is not true: we use reduc_index to record the index of the
5475 reduction variable. */
5476 for (i
= 0; i
< op_type
; i
++)
5478 if (i
== reduc_index
)
5481 /* The condition of COND_EXPR is checked in vectorizable_condition(). */
5482 if (i
== 0 && code
== COND_EXPR
)
5485 is_simple_use
= vect_is_simple_use (ops
[i
], loop_vinfo
,
5486 &def_stmt
, &dt
, &tem
);
5489 gcc_assert (is_simple_use
);
5491 if (dt
!= vect_internal_def
5492 && dt
!= vect_external_def
5493 && dt
!= vect_constant_def
5494 && dt
!= vect_induction_def
5495 && !(dt
== vect_nested_cycle
&& nested_cycle
))
5498 if (dt
== vect_nested_cycle
)
5500 found_nested_cycle_def
= true;
5501 reduc_def_stmt
= def_stmt
;
5505 if (i
== 1 && code
== COND_EXPR
&& dt
== vect_induction_def
)
5506 cond_expr_induction_def_stmt
= def_stmt
;
5509 is_simple_use
= vect_is_simple_use (ops
[reduc_index
], loop_vinfo
,
5510 &def_stmt
, &dt
, &tem
);
5513 gcc_assert (is_simple_use
);
5514 if (!found_nested_cycle_def
)
5515 reduc_def_stmt
= def_stmt
;
5517 if (reduc_def_stmt
&& gimple_code (reduc_def_stmt
) != GIMPLE_PHI
)
5520 if (!(dt
== vect_reduction_def
5521 || dt
== vect_nested_cycle
5522 || ((dt
== vect_internal_def
|| dt
== vect_external_def
5523 || dt
== vect_constant_def
|| dt
== vect_induction_def
)
5524 && nested_cycle
&& found_nested_cycle_def
)))
5526 /* For pattern recognized stmts, orig_stmt might be a reduction,
5527 but some helper statements for the pattern might not, or
5528 might be COND_EXPRs with reduction uses in the condition. */
5529 gcc_assert (orig_stmt
);
5533 enum vect_reduction_type v_reduc_type
;
5534 gimple
*tmp
= vect_is_simple_reduction (loop_vinfo
, reduc_def_stmt
,
5535 !nested_cycle
, &dummy
, false,
5538 /* If we have a condition reduction, see if we can simplify it further. */
5539 if (v_reduc_type
== COND_REDUCTION
5540 && cond_expr_induction_def_stmt
!= NULL
5541 && is_nonwrapping_integer_induction (cond_expr_induction_def_stmt
, loop
))
5543 if (dump_enabled_p ())
5544 dump_printf_loc (MSG_NOTE
, vect_location
,
5545 "condition expression based on integer induction.\n");
5546 STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) = INTEGER_INDUC_COND_REDUCTION
;
5549 STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) = v_reduc_type
;
5552 gcc_assert (tmp
== orig_stmt
5553 || GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp
)) == orig_stmt
);
5555 /* We changed STMT to be the first stmt in reduction chain, hence we
5556 check that in this case the first element in the chain is STMT. */
5557 gcc_assert (stmt
== tmp
5558 || GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp
)) == stmt
);
5560 if (STMT_VINFO_LIVE_P (vinfo_for_stmt (reduc_def_stmt
)))
5563 if (slp_node
|| PURE_SLP_STMT (stmt_info
))
5566 ncopies
= (LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
5567 / TYPE_VECTOR_SUBPARTS (vectype_in
));
5569 gcc_assert (ncopies
>= 1);
5571 vec_mode
= TYPE_MODE (vectype_in
);
5573 if (code
== COND_EXPR
)
5575 /* Only call during the analysis stage, otherwise we'll lose
5577 if (!vec_stmt
&& !vectorizable_condition (stmt
, gsi
, NULL
,
5578 ops
[reduc_index
], 0, NULL
))
5580 if (dump_enabled_p ())
5581 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5582 "unsupported condition in reduction\n");
5588 /* 4. Supportable by target? */
5590 if (code
== LSHIFT_EXPR
|| code
== RSHIFT_EXPR
5591 || code
== LROTATE_EXPR
|| code
== RROTATE_EXPR
)
5593 /* Shifts and rotates are only supported by vectorizable_shifts,
5594 not vectorizable_reduction. */
5595 if (dump_enabled_p ())
5596 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5597 "unsupported shift or rotation.\n");
5601 /* 4.1. check support for the operation in the loop */
5602 optab
= optab_for_tree_code (code
, vectype_in
, optab_default
);
5605 if (dump_enabled_p ())
5606 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5612 if (optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
5614 if (dump_enabled_p ())
5615 dump_printf (MSG_NOTE
, "op not supported by target.\n");
5617 if (GET_MODE_SIZE (vec_mode
) != UNITS_PER_WORD
5618 || LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
5619 < vect_min_worthwhile_factor (code
))
5622 if (dump_enabled_p ())
5623 dump_printf (MSG_NOTE
, "proceeding using word mode.\n");
5626 /* Worthwhile without SIMD support? */
5627 if (!VECTOR_MODE_P (TYPE_MODE (vectype_in
))
5628 && LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
5629 < vect_min_worthwhile_factor (code
))
5631 if (dump_enabled_p ())
5632 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5633 "not worthwhile without SIMD support.\n");
5639 /* 4.2. Check support for the epilog operation.
5641 If STMT represents a reduction pattern, then the type of the
5642 reduction variable may be different than the type of the rest
5643 of the arguments. For example, consider the case of accumulation
5644 of shorts into an int accumulator; The original code:
5645 S1: int_a = (int) short_a;
5646 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
5649 STMT: int_acc = widen_sum <short_a, int_acc>
5652 1. The tree-code that is used to create the vector operation in the
5653 epilog code (that reduces the partial results) is not the
5654 tree-code of STMT, but is rather the tree-code of the original
5655 stmt from the pattern that STMT is replacing. I.e, in the example
5656 above we want to use 'widen_sum' in the loop, but 'plus' in the
5658 2. The type (mode) we use to check available target support
5659 for the vector operation to be created in the *epilog*, is
5660 determined by the type of the reduction variable (in the example
5661 above we'd check this: optab_handler (plus_optab, vect_int_mode])).
5662 However the type (mode) we use to check available target support
5663 for the vector operation to be created *inside the loop*, is
5664 determined by the type of the other arguments to STMT (in the
5665 example we'd check this: optab_handler (widen_sum_optab,
5668 This is contrary to "regular" reductions, in which the types of all
5669 the arguments are the same as the type of the reduction variable.
5670 For "regular" reductions we can therefore use the same vector type
5671 (and also the same tree-code) when generating the epilog code and
5672 when generating the code inside the loop. */
5676 /* This is a reduction pattern: get the vectype from the type of the
5677 reduction variable, and get the tree-code from orig_stmt. */
5678 gcc_assert (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
5679 == TREE_CODE_REDUCTION
);
5680 orig_code
= gimple_assign_rhs_code (orig_stmt
);
5681 gcc_assert (vectype_out
);
5682 vec_mode
= TYPE_MODE (vectype_out
);
5686 /* Regular reduction: use the same vectype and tree-code as used for
5687 the vector code inside the loop can be used for the epilog code. */
5690 if (code
== MINUS_EXPR
)
5691 orig_code
= PLUS_EXPR
;
5693 /* For simple condition reductions, replace with the actual expression
5694 we want to base our reduction around. */
5695 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
5696 == INTEGER_INDUC_COND_REDUCTION
)
5697 orig_code
= MAX_EXPR
;
5702 def_bb
= gimple_bb (reduc_def_stmt
);
5703 def_stmt_loop
= def_bb
->loop_father
;
5704 def_arg
= PHI_ARG_DEF_FROM_EDGE (reduc_def_stmt
,
5705 loop_preheader_edge (def_stmt_loop
));
5706 if (TREE_CODE (def_arg
) == SSA_NAME
5707 && (def_arg_stmt
= SSA_NAME_DEF_STMT (def_arg
))
5708 && gimple_code (def_arg_stmt
) == GIMPLE_PHI
5709 && flow_bb_inside_loop_p (outer_loop
, gimple_bb (def_arg_stmt
))
5710 && vinfo_for_stmt (def_arg_stmt
)
5711 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_arg_stmt
))
5712 == vect_double_reduction_def
)
5713 double_reduc
= true;
5716 epilog_reduc_code
= ERROR_MARK
;
5718 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == TREE_CODE_REDUCTION
5719 || STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
5720 == INTEGER_INDUC_COND_REDUCTION
)
5722 if (reduction_code_for_scalar_code (orig_code
, &epilog_reduc_code
))
5724 reduc_optab
= optab_for_tree_code (epilog_reduc_code
, vectype_out
,
5728 if (dump_enabled_p ())
5729 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5730 "no optab for reduction.\n");
5732 epilog_reduc_code
= ERROR_MARK
;
5734 else if (optab_handler (reduc_optab
, vec_mode
) == CODE_FOR_nothing
)
5736 optab
= scalar_reduc_to_vector (reduc_optab
, vectype_out
);
5737 if (optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
5739 if (dump_enabled_p ())
5740 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5741 "reduc op not supported by target.\n");
5743 epilog_reduc_code
= ERROR_MARK
;
5747 /* When epilog_reduc_code is ERROR_MARK then a reduction will be
5748 generated in the epilog using multiple expressions. This does not
5749 work for condition reductions. */
5750 if (epilog_reduc_code
== ERROR_MARK
5751 && STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
5752 == INTEGER_INDUC_COND_REDUCTION
)
5754 if (dump_enabled_p ())
5755 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5756 "no reduc code for scalar code.\n");
5762 if (!nested_cycle
|| double_reduc
)
5764 if (dump_enabled_p ())
5765 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5766 "no reduc code for scalar code.\n");
5774 int scalar_precision
= GET_MODE_PRECISION (TYPE_MODE (scalar_type
));
5775 cr_index_scalar_type
= make_unsigned_type (scalar_precision
);
5776 cr_index_vector_type
= build_vector_type
5777 (cr_index_scalar_type
, TYPE_VECTOR_SUBPARTS (vectype_out
));
5779 epilog_reduc_code
= REDUC_MAX_EXPR
;
5780 optab
= optab_for_tree_code (REDUC_MAX_EXPR
, cr_index_vector_type
,
5782 if (optab_handler (optab
, TYPE_MODE (cr_index_vector_type
))
5783 == CODE_FOR_nothing
)
5785 if (dump_enabled_p ())
5786 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5787 "reduc max op not supported by target.\n");
5793 || STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
5794 || STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
5795 == INTEGER_INDUC_COND_REDUCTION
)
5798 if (dump_enabled_p ())
5799 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5800 "multiple types in double reduction or condition "
5805 /* In case of widenning multiplication by a constant, we update the type
5806 of the constant to be the type of the other operand. We check that the
5807 constant fits the type in the pattern recognition pass. */
5808 if (code
== DOT_PROD_EXPR
5809 && !types_compatible_p (TREE_TYPE (ops
[0]), TREE_TYPE (ops
[1])))
5811 if (TREE_CODE (ops
[0]) == INTEGER_CST
)
5812 ops
[0] = fold_convert (TREE_TYPE (ops
[1]), ops
[0]);
5813 else if (TREE_CODE (ops
[1]) == INTEGER_CST
)
5814 ops
[1] = fold_convert (TREE_TYPE (ops
[0]), ops
[1]);
5817 if (dump_enabled_p ())
5818 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5819 "invalid types in dot-prod\n");
5825 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
)
5829 if (! max_loop_iterations (loop
, &ni
))
5831 if (dump_enabled_p ())
5832 dump_printf_loc (MSG_NOTE
, vect_location
,
5833 "loop count not known, cannot create cond "
5837 /* Convert backedges to iterations. */
5840 /* The additional index will be the same type as the condition. Check
5841 that the loop can fit into this less one (because we'll use up the
5842 zero slot for when there are no matches). */
5843 tree max_index
= TYPE_MAX_VALUE (cr_index_scalar_type
);
5844 if (wi::geu_p (ni
, wi::to_widest (max_index
)))
5846 if (dump_enabled_p ())
5847 dump_printf_loc (MSG_NOTE
, vect_location
,
5848 "loop size is greater than data size.\n");
5853 if (!vec_stmt
) /* transformation not required. */
5856 && !vect_model_reduction_cost (stmt_info
, epilog_reduc_code
, ncopies
,
5859 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
5865 if (dump_enabled_p ())
5866 dump_printf_loc (MSG_NOTE
, vect_location
, "transform reduction.\n");
5868 /* FORNOW: Multiple types are not supported for condition. */
5869 if (code
== COND_EXPR
)
5870 gcc_assert (ncopies
== 1);
5872 /* Create the destination vector */
5873 vec_dest
= vect_create_destination_var (scalar_dest
, vectype_out
);
5875 /* In case the vectorization factor (VF) is bigger than the number
5876 of elements that we can fit in a vectype (nunits), we have to generate
5877 more than one vector stmt - i.e - we need to "unroll" the
5878 vector stmt by a factor VF/nunits. For more details see documentation
5879 in vectorizable_operation. */
5881 /* If the reduction is used in an outer loop we need to generate
5882 VF intermediate results, like so (e.g. for ncopies=2):
5887 (i.e. we generate VF results in 2 registers).
5888 In this case we have a separate def-use cycle for each copy, and therefore
5889 for each copy we get the vector def for the reduction variable from the
5890 respective phi node created for this copy.
5892 Otherwise (the reduction is unused in the loop nest), we can combine
5893 together intermediate results, like so (e.g. for ncopies=2):
5897 (i.e. we generate VF/2 results in a single register).
5898 In this case for each copy we get the vector def for the reduction variable
5899 from the vectorized reduction operation generated in the previous iteration.
5902 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
)
5904 single_defuse_cycle
= true;
5908 epilog_copies
= ncopies
;
5910 prev_stmt_info
= NULL
;
5911 prev_phi_info
= NULL
;
5913 vec_num
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
5917 vec_oprnds0
.create (1);
5918 if (op_type
== ternary_op
)
5919 vec_oprnds1
.create (1);
5922 phis
.create (vec_num
);
5923 vect_defs
.create (vec_num
);
5925 vect_defs
.quick_push (NULL_TREE
);
5927 for (j
= 0; j
< ncopies
; j
++)
5929 if (j
== 0 || !single_defuse_cycle
)
5931 for (i
= 0; i
< vec_num
; i
++)
5933 /* Create the reduction-phi that defines the reduction
5935 new_phi
= create_phi_node (vec_dest
, loop
->header
);
5936 set_vinfo_for_stmt (new_phi
,
5937 new_stmt_vec_info (new_phi
, loop_vinfo
));
5938 if (j
== 0 || slp_node
)
5939 phis
.quick_push (new_phi
);
5943 if (code
== COND_EXPR
)
5945 gcc_assert (!slp_node
);
5946 vectorizable_condition (stmt
, gsi
, vec_stmt
,
5947 PHI_RESULT (phis
[0]),
5949 /* Multiple types are not supported for condition. */
5956 op0
= ops
[!reduc_index
];
5957 if (op_type
== ternary_op
)
5959 if (reduc_index
== 0)
5966 vect_get_vec_defs (op0
, op1
, stmt
, &vec_oprnds0
, &vec_oprnds1
,
5970 loop_vec_def0
= vect_get_vec_def_for_operand (ops
[!reduc_index
],
5972 vec_oprnds0
.quick_push (loop_vec_def0
);
5973 if (op_type
== ternary_op
)
5975 loop_vec_def1
= vect_get_vec_def_for_operand (op1
, stmt
);
5976 vec_oprnds1
.quick_push (loop_vec_def1
);
5984 enum vect_def_type dt
;
5987 vect_is_simple_use (ops
[!reduc_index
], loop_vinfo
,
5989 loop_vec_def0
= vect_get_vec_def_for_stmt_copy (dt
,
5991 vec_oprnds0
[0] = loop_vec_def0
;
5992 if (op_type
== ternary_op
)
5994 vect_is_simple_use (op1
, loop_vinfo
, &dummy_stmt
, &dt
);
5995 loop_vec_def1
= vect_get_vec_def_for_stmt_copy (dt
,
5997 vec_oprnds1
[0] = loop_vec_def1
;
6001 if (single_defuse_cycle
)
6002 reduc_def
= gimple_assign_lhs (new_stmt
);
6004 STMT_VINFO_RELATED_STMT (prev_phi_info
) = new_phi
;
6007 FOR_EACH_VEC_ELT (vec_oprnds0
, i
, def0
)
6010 reduc_def
= PHI_RESULT (phis
[i
]);
6013 if (!single_defuse_cycle
|| j
== 0)
6014 reduc_def
= PHI_RESULT (new_phi
);
6017 def1
= ((op_type
== ternary_op
)
6018 ? vec_oprnds1
[i
] : NULL
);
6019 if (op_type
== binary_op
)
6021 if (reduc_index
== 0)
6022 expr
= build2 (code
, vectype_out
, reduc_def
, def0
);
6024 expr
= build2 (code
, vectype_out
, def0
, reduc_def
);
6028 if (reduc_index
== 0)
6029 expr
= build3 (code
, vectype_out
, reduc_def
, def0
, def1
);
6032 if (reduc_index
== 1)
6033 expr
= build3 (code
, vectype_out
, def0
, reduc_def
, def1
);
6035 expr
= build3 (code
, vectype_out
, def0
, def1
, reduc_def
);
6039 new_stmt
= gimple_build_assign (vec_dest
, expr
);
6040 new_temp
= make_ssa_name (vec_dest
, new_stmt
);
6041 gimple_assign_set_lhs (new_stmt
, new_temp
);
6042 vect_finish_stmt_generation (stmt
, new_stmt
, gsi
);
6046 SLP_TREE_VEC_STMTS (slp_node
).quick_push (new_stmt
);
6047 vect_defs
.quick_push (new_temp
);
6050 vect_defs
[0] = new_temp
;
6057 STMT_VINFO_VEC_STMT (stmt_info
) = *vec_stmt
= new_stmt
;
6059 STMT_VINFO_RELATED_STMT (prev_stmt_info
) = new_stmt
;
6061 prev_stmt_info
= vinfo_for_stmt (new_stmt
);
6062 prev_phi_info
= vinfo_for_stmt (new_phi
);
6065 tree indx_before_incr
, indx_after_incr
, cond_name
= NULL
;
6067 /* Finalize the reduction-phi (set its arguments) and create the
6068 epilog reduction code. */
6069 if ((!single_defuse_cycle
|| code
== COND_EXPR
) && !slp_node
)
6071 new_temp
= gimple_assign_lhs (*vec_stmt
);
6072 vect_defs
[0] = new_temp
;
6074 /* For cond reductions we want to create a new vector (INDEX_COND_EXPR)
6075 which is updated with the current index of the loop for every match of
6076 the original loop's cond_expr (VEC_STMT). This results in a vector
6077 containing the last time the condition passed for that vector lane.
6078 The first match will be a 1 to allow 0 to be used for non-matching
6079 indexes. If there are no matches at all then the vector will be all
6081 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
)
6083 int nunits_out
= TYPE_VECTOR_SUBPARTS (vectype_out
);
6086 gcc_assert (gimple_assign_rhs_code (*vec_stmt
) == VEC_COND_EXPR
);
6088 /* First we create a simple vector induction variable which starts
6089 with the values {1,2,3,...} (SERIES_VECT) and increments by the
6090 vector size (STEP). */
6092 /* Create a {1,2,3,...} vector. */
6093 tree
*vtemp
= XALLOCAVEC (tree
, nunits_out
);
6094 for (k
= 0; k
< nunits_out
; ++k
)
6095 vtemp
[k
] = build_int_cst (cr_index_scalar_type
, k
+ 1);
6096 tree series_vect
= build_vector (cr_index_vector_type
, vtemp
);
6098 /* Create a vector of the step value. */
6099 tree step
= build_int_cst (cr_index_scalar_type
, nunits_out
);
6100 tree vec_step
= build_vector_from_val (cr_index_vector_type
, step
);
6102 /* Create an induction variable. */
6103 gimple_stmt_iterator incr_gsi
;
6105 standard_iv_increment_position (loop
, &incr_gsi
, &insert_after
);
6106 create_iv (series_vect
, vec_step
, NULL_TREE
, loop
, &incr_gsi
,
6107 insert_after
, &indx_before_incr
, &indx_after_incr
);
6109 /* Next create a new phi node vector (NEW_PHI_TREE) which starts
6110 filled with zeros (VEC_ZERO). */
6112 /* Create a vector of 0s. */
6113 tree zero
= build_zero_cst (cr_index_scalar_type
);
6114 tree vec_zero
= build_vector_from_val (cr_index_vector_type
, zero
);
6116 /* Create a vector phi node. */
6117 tree new_phi_tree
= make_ssa_name (cr_index_vector_type
);
6118 new_phi
= create_phi_node (new_phi_tree
, loop
->header
);
6119 set_vinfo_for_stmt (new_phi
,
6120 new_stmt_vec_info (new_phi
, loop_vinfo
));
6121 add_phi_arg (new_phi
, vec_zero
, loop_preheader_edge (loop
),
6124 /* Now take the condition from the loops original cond_expr
6125 (VEC_STMT) and produce a new cond_expr (INDEX_COND_EXPR) which for
6126 every match uses values from the induction variable
6127 (INDEX_BEFORE_INCR) otherwise uses values from the phi node
6129 Finally, we update the phi (NEW_PHI_TREE) to take the value of
6130 the new cond_expr (INDEX_COND_EXPR). */
6132 /* Turn the condition from vec_stmt into an ssa name. */
6133 gimple_stmt_iterator vec_stmt_gsi
= gsi_for_stmt (*vec_stmt
);
6134 tree ccompare
= gimple_assign_rhs1 (*vec_stmt
);
6135 tree ccompare_name
= make_ssa_name (TREE_TYPE (ccompare
));
6136 gimple
*ccompare_stmt
= gimple_build_assign (ccompare_name
,
6138 gsi_insert_before (&vec_stmt_gsi
, ccompare_stmt
, GSI_SAME_STMT
);
6139 gimple_assign_set_rhs1 (*vec_stmt
, ccompare_name
);
6140 update_stmt (*vec_stmt
);
6142 /* Create a conditional, where the condition is taken from vec_stmt
6143 (CCOMPARE_NAME), then is the induction index (INDEX_BEFORE_INCR)
6144 and else is the phi (NEW_PHI_TREE). */
6145 tree index_cond_expr
= build3 (VEC_COND_EXPR
, cr_index_vector_type
,
6146 ccompare_name
, indx_before_incr
,
6148 cond_name
= make_ssa_name (cr_index_vector_type
);
6149 gimple
*index_condition
= gimple_build_assign (cond_name
,
6151 gsi_insert_before (&incr_gsi
, index_condition
, GSI_SAME_STMT
);
6152 stmt_vec_info index_vec_info
= new_stmt_vec_info (index_condition
,
6154 STMT_VINFO_VECTYPE (index_vec_info
) = cr_index_vector_type
;
6155 set_vinfo_for_stmt (index_condition
, index_vec_info
);
6157 /* Update the phi with the vec cond. */
6158 add_phi_arg (new_phi
, cond_name
, loop_latch_edge (loop
),
6163 vect_create_epilog_for_reduction (vect_defs
, stmt
, epilog_copies
,
6164 epilog_reduc_code
, phis
, reduc_index
,
6165 double_reduc
, slp_node
, cond_name
);
6170 /* Function vect_min_worthwhile_factor.
6172 For a loop where we could vectorize the operation indicated by CODE,
6173 return the minimum vectorization factor that makes it worthwhile
6174 to use generic vectors. */
6176 vect_min_worthwhile_factor (enum tree_code code
)
6197 /* Function vectorizable_induction
6199 Check if PHI performs an induction computation that can be vectorized.
6200 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
6201 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
6202 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
6205 vectorizable_induction (gimple
*phi
,
6206 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
6209 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
6210 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
6211 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
6212 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
6213 int nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
6214 int ncopies
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) / nunits
;
6217 gcc_assert (ncopies
>= 1);
6218 /* FORNOW. These restrictions should be relaxed. */
6219 if (nested_in_vect_loop_p (loop
, phi
))
6221 imm_use_iterator imm_iter
;
6222 use_operand_p use_p
;
6229 if (dump_enabled_p ())
6230 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6231 "multiple types in nested loop.\n");
6236 latch_e
= loop_latch_edge (loop
->inner
);
6237 loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
6238 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
6240 gimple
*use_stmt
= USE_STMT (use_p
);
6241 if (is_gimple_debug (use_stmt
))
6244 if (!flow_bb_inside_loop_p (loop
->inner
, gimple_bb (use_stmt
)))
6246 exit_phi
= use_stmt
;
6252 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
6253 if (!(STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
6254 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
)))
6256 if (dump_enabled_p ())
6257 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6258 "inner-loop induction only used outside "
6259 "of the outer vectorized loop.\n");
6265 if (!STMT_VINFO_RELEVANT_P (stmt_info
))
6268 /* FORNOW: SLP not supported. */
6269 if (STMT_SLP_TYPE (stmt_info
))
6272 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
);
6274 if (gimple_code (phi
) != GIMPLE_PHI
)
6277 if (!vec_stmt
) /* transformation not required. */
6279 STMT_VINFO_TYPE (stmt_info
) = induc_vec_info_type
;
6280 if (dump_enabled_p ())
6281 dump_printf_loc (MSG_NOTE
, vect_location
,
6282 "=== vectorizable_induction ===\n");
6283 vect_model_induction_cost (stmt_info
, ncopies
);
6289 if (dump_enabled_p ())
6290 dump_printf_loc (MSG_NOTE
, vect_location
, "transform induction phi.\n");
6292 vec_def
= get_initial_def_for_induction (phi
);
6293 *vec_stmt
= SSA_NAME_DEF_STMT (vec_def
);
6297 /* Function vectorizable_live_operation.
6299 STMT computes a value that is used outside the loop. Check if
6300 it can be supported. */
6303 vectorizable_live_operation (gimple
*stmt
,
6304 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
6307 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
6308 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
6309 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
6314 gcc_assert (STMT_VINFO_LIVE_P (stmt_info
));
6316 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_reduction_def
)
6319 if (!is_gimple_assign (stmt
))
6321 if (gimple_call_internal_p (stmt
)
6322 && gimple_call_internal_fn (stmt
) == IFN_GOMP_SIMD_LANE
6323 && gimple_call_lhs (stmt
)
6325 && TREE_CODE (gimple_call_arg (stmt
, 0)) == SSA_NAME
6327 == SSA_NAME_VAR (gimple_call_arg (stmt
, 0)))
6329 edge e
= single_exit (loop
);
6330 basic_block merge_bb
= e
->dest
;
6331 imm_use_iterator imm_iter
;
6332 use_operand_p use_p
;
6333 tree lhs
= gimple_call_lhs (stmt
);
6335 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
6337 gimple
*use_stmt
= USE_STMT (use_p
);
6338 if (gimple_code (use_stmt
) == GIMPLE_PHI
6339 && gimple_bb (use_stmt
) == merge_bb
)
6344 = build_int_cst (unsigned_type_node
,
6345 loop_vinfo
->vectorization_factor
- 1);
6346 SET_PHI_ARG_DEF (use_stmt
, e
->dest_idx
, vfm1
);
6356 if (TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
6359 /* FORNOW. CHECKME. */
6360 if (nested_in_vect_loop_p (loop
, stmt
))
6363 /* FORNOW: support only if all uses are invariant. This means
6364 that the scalar operations can remain in place, unvectorized.
6365 The original last scalar value that they compute will be used. */
6366 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
6368 enum vect_def_type dt
= vect_uninitialized_def
;
6370 if (!vect_is_simple_use (op
, loop_vinfo
, &def_stmt
, &dt
))
6372 if (dump_enabled_p ())
6373 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6374 "use not simple.\n");
6378 if (dt
!= vect_external_def
&& dt
!= vect_constant_def
)
6382 /* No transformation is required for the cases we currently support. */
6386 /* Kill any debug uses outside LOOP of SSA names defined in STMT. */
6389 vect_loop_kill_debug_uses (struct loop
*loop
, gimple
*stmt
)
6391 ssa_op_iter op_iter
;
6392 imm_use_iterator imm_iter
;
6393 def_operand_p def_p
;
6396 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
6398 FOR_EACH_IMM_USE_STMT (ustmt
, imm_iter
, DEF_FROM_PTR (def_p
))
6402 if (!is_gimple_debug (ustmt
))
6405 bb
= gimple_bb (ustmt
);
6407 if (!flow_bb_inside_loop_p (loop
, bb
))
6409 if (gimple_debug_bind_p (ustmt
))
6411 if (dump_enabled_p ())
6412 dump_printf_loc (MSG_NOTE
, vect_location
,
6413 "killing debug use\n");
6415 gimple_debug_bind_reset_value (ustmt
);
6416 update_stmt (ustmt
);
6426 /* This function builds ni_name = number of iterations. Statements
6427 are emitted on the loop preheader edge. */
6430 vect_build_loop_niters (loop_vec_info loop_vinfo
)
6432 tree ni
= unshare_expr (LOOP_VINFO_NITERS (loop_vinfo
));
6433 if (TREE_CODE (ni
) == INTEGER_CST
)
6438 gimple_seq stmts
= NULL
;
6439 edge pe
= loop_preheader_edge (LOOP_VINFO_LOOP (loop_vinfo
));
6441 var
= create_tmp_var (TREE_TYPE (ni
), "niters");
6442 ni_name
= force_gimple_operand (ni
, &stmts
, false, var
);
6444 gsi_insert_seq_on_edge_immediate (pe
, stmts
);
6451 /* This function generates the following statements:
6453 ni_name = number of iterations loop executes
6454 ratio = ni_name / vf
6455 ratio_mult_vf_name = ratio * vf
6457 and places them on the loop preheader edge. */
6460 vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo
,
6462 tree
*ratio_mult_vf_name_ptr
,
6463 tree
*ratio_name_ptr
)
6465 tree ni_minus_gap_name
;
6468 tree ratio_mult_vf_name
;
6469 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
6470 edge pe
= loop_preheader_edge (LOOP_VINFO_LOOP (loop_vinfo
));
6473 log_vf
= build_int_cst (TREE_TYPE (ni_name
), exact_log2 (vf
));
6475 /* If epilogue loop is required because of data accesses with gaps, we
6476 subtract one iteration from the total number of iterations here for
6477 correct calculation of RATIO. */
6478 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
))
6480 ni_minus_gap_name
= fold_build2 (MINUS_EXPR
, TREE_TYPE (ni_name
),
6482 build_one_cst (TREE_TYPE (ni_name
)));
6483 if (!is_gimple_val (ni_minus_gap_name
))
6485 var
= create_tmp_var (TREE_TYPE (ni_name
), "ni_gap");
6486 gimple
*stmts
= NULL
;
6487 ni_minus_gap_name
= force_gimple_operand (ni_minus_gap_name
, &stmts
,
6489 gsi_insert_seq_on_edge_immediate (pe
, stmts
);
6493 ni_minus_gap_name
= ni_name
;
6495 /* Create: ratio = ni >> log2(vf) */
6496 /* ??? As we have ni == number of latch executions + 1, ni could
6497 have overflown to zero. So avoid computing ratio based on ni
6498 but compute it using the fact that we know ratio will be at least
6499 one, thus via (ni - vf) >> log2(vf) + 1. */
6501 = fold_build2 (PLUS_EXPR
, TREE_TYPE (ni_name
),
6502 fold_build2 (RSHIFT_EXPR
, TREE_TYPE (ni_name
),
6503 fold_build2 (MINUS_EXPR
, TREE_TYPE (ni_name
),
6506 (TREE_TYPE (ni_name
), vf
)),
6508 build_int_cst (TREE_TYPE (ni_name
), 1));
6509 if (!is_gimple_val (ratio_name
))
6511 var
= create_tmp_var (TREE_TYPE (ni_name
), "bnd");
6512 gimple
*stmts
= NULL
;
6513 ratio_name
= force_gimple_operand (ratio_name
, &stmts
, true, var
);
6514 gsi_insert_seq_on_edge_immediate (pe
, stmts
);
6516 *ratio_name_ptr
= ratio_name
;
6518 /* Create: ratio_mult_vf = ratio << log2 (vf). */
6520 if (ratio_mult_vf_name_ptr
)
6522 ratio_mult_vf_name
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (ratio_name
),
6523 ratio_name
, log_vf
);
6524 if (!is_gimple_val (ratio_mult_vf_name
))
6526 var
= create_tmp_var (TREE_TYPE (ni_name
), "ratio_mult_vf");
6527 gimple
*stmts
= NULL
;
6528 ratio_mult_vf_name
= force_gimple_operand (ratio_mult_vf_name
, &stmts
,
6530 gsi_insert_seq_on_edge_immediate (pe
, stmts
);
6532 *ratio_mult_vf_name_ptr
= ratio_mult_vf_name
;
6539 /* Function vect_transform_loop.
6541 The analysis phase has determined that the loop is vectorizable.
6542 Vectorize the loop - created vectorized stmts to replace the scalar
6543 stmts in the loop, and update the loop exit condition. */
6546 vect_transform_loop (loop_vec_info loop_vinfo
)
6548 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
6549 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
6550 int nbbs
= loop
->num_nodes
;
6553 int vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
6555 bool slp_scheduled
= false;
6556 gimple
*stmt
, *pattern_stmt
;
6557 gimple_seq pattern_def_seq
= NULL
;
6558 gimple_stmt_iterator pattern_def_si
= gsi_none ();
6559 bool transform_pattern_stmt
= false;
6560 bool check_profitability
= false;
6562 /* Record number of iterations before we started tampering with the profile. */
6563 gcov_type expected_iterations
= expected_loop_iterations_unbounded (loop
);
6565 if (dump_enabled_p ())
6566 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vec_transform_loop ===\n");
6568 /* If profile is inprecise, we have chance to fix it up. */
6569 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
6570 expected_iterations
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
6572 /* Use the more conservative vectorization threshold. If the number
6573 of iterations is constant assume the cost check has been performed
6574 by our caller. If the threshold makes all loops profitable that
6575 run at least the vectorization factor number of times checking
6576 is pointless, too. */
6577 th
= LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo
);
6578 if (th
>= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) - 1
6579 && !LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
6581 if (dump_enabled_p ())
6582 dump_printf_loc (MSG_NOTE
, vect_location
,
6583 "Profitability threshold is %d loop iterations.\n",
6585 check_profitability
= true;
6588 /* Version the loop first, if required, so the profitability check
6591 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
6592 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
6594 vect_loop_versioning (loop_vinfo
, th
, check_profitability
);
6595 check_profitability
= false;
6598 tree ni_name
= vect_build_loop_niters (loop_vinfo
);
6599 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo
) = ni_name
;
6601 /* Peel the loop if there are data refs with unknown alignment.
6602 Only one data ref with unknown store is allowed. */
6604 if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
))
6606 vect_do_peeling_for_alignment (loop_vinfo
, ni_name
,
6607 th
, check_profitability
);
6608 check_profitability
= false;
6609 /* The above adjusts LOOP_VINFO_NITERS, so cause ni_name to
6611 ni_name
= NULL_TREE
;
6614 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
6615 compile time constant), or it is a constant that doesn't divide by the
6616 vectorization factor, then an epilog loop needs to be created.
6617 We therefore duplicate the loop: the original loop will be vectorized,
6618 and will compute the first (n/VF) iterations. The second copy of the loop
6619 will remain scalar and will compute the remaining (n%VF) iterations.
6620 (VF is the vectorization factor). */
6622 if (LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
)
6623 || LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
))
6627 ni_name
= vect_build_loop_niters (loop_vinfo
);
6628 vect_generate_tmps_on_preheader (loop_vinfo
, ni_name
, &ratio_mult_vf
,
6630 vect_do_peeling_for_loop_bound (loop_vinfo
, ni_name
, ratio_mult_vf
,
6631 th
, check_profitability
);
6633 else if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
6634 ratio
= build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo
)),
6635 LOOP_VINFO_INT_NITERS (loop_vinfo
) / vectorization_factor
);
6639 ni_name
= vect_build_loop_niters (loop_vinfo
);
6640 vect_generate_tmps_on_preheader (loop_vinfo
, ni_name
, NULL
, &ratio
);
6643 /* 1) Make sure the loop header has exactly two entries
6644 2) Make sure we have a preheader basic block. */
6646 gcc_assert (EDGE_COUNT (loop
->header
->preds
) == 2);
6648 split_edge (loop_preheader_edge (loop
));
6650 /* FORNOW: the vectorizer supports only loops which body consist
6651 of one basic block (header + empty latch). When the vectorizer will
6652 support more involved loop forms, the order by which the BBs are
6653 traversed need to be reconsidered. */
6655 for (i
= 0; i
< nbbs
; i
++)
6657 basic_block bb
= bbs
[i
];
6658 stmt_vec_info stmt_info
;
6660 for (gphi_iterator si
= gsi_start_phis (bb
); !gsi_end_p (si
);
6663 gphi
*phi
= si
.phi ();
6664 if (dump_enabled_p ())
6666 dump_printf_loc (MSG_NOTE
, vect_location
,
6667 "------>vectorizing phi: ");
6668 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
6669 dump_printf (MSG_NOTE
, "\n");
6671 stmt_info
= vinfo_for_stmt (phi
);
6675 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
6676 vect_loop_kill_debug_uses (loop
, phi
);
6678 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
6679 && !STMT_VINFO_LIVE_P (stmt_info
))
6682 if (STMT_VINFO_VECTYPE (stmt_info
)
6683 && (TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
))
6684 != (unsigned HOST_WIDE_INT
) vectorization_factor
)
6685 && dump_enabled_p ())
6686 dump_printf_loc (MSG_NOTE
, vect_location
, "multiple-types.\n");
6688 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
6690 if (dump_enabled_p ())
6691 dump_printf_loc (MSG_NOTE
, vect_location
, "transform phi.\n");
6692 vect_transform_stmt (phi
, NULL
, NULL
, NULL
, NULL
);
6696 pattern_stmt
= NULL
;
6697 for (gimple_stmt_iterator si
= gsi_start_bb (bb
);
6698 !gsi_end_p (si
) || transform_pattern_stmt
;)
6702 if (transform_pattern_stmt
)
6703 stmt
= pattern_stmt
;
6706 stmt
= gsi_stmt (si
);
6707 /* During vectorization remove existing clobber stmts. */
6708 if (gimple_clobber_p (stmt
))
6710 unlink_stmt_vdef (stmt
);
6711 gsi_remove (&si
, true);
6712 release_defs (stmt
);
6717 if (dump_enabled_p ())
6719 dump_printf_loc (MSG_NOTE
, vect_location
,
6720 "------>vectorizing statement: ");
6721 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
6722 dump_printf (MSG_NOTE
, "\n");
6725 stmt_info
= vinfo_for_stmt (stmt
);
6727 /* vector stmts created in the outer-loop during vectorization of
6728 stmts in an inner-loop may not have a stmt_info, and do not
6729 need to be vectorized. */
6736 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
6737 vect_loop_kill_debug_uses (loop
, stmt
);
6739 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
6740 && !STMT_VINFO_LIVE_P (stmt_info
))
6742 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
6743 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
6744 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
6745 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
6747 stmt
= pattern_stmt
;
6748 stmt_info
= vinfo_for_stmt (stmt
);
6756 else if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
6757 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
6758 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
6759 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
6760 transform_pattern_stmt
= true;
6762 /* If pattern statement has def stmts, vectorize them too. */
6763 if (is_pattern_stmt_p (stmt_info
))
6765 if (pattern_def_seq
== NULL
)
6767 pattern_def_seq
= STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
);
6768 pattern_def_si
= gsi_start (pattern_def_seq
);
6770 else if (!gsi_end_p (pattern_def_si
))
6771 gsi_next (&pattern_def_si
);
6772 if (pattern_def_seq
!= NULL
)
6774 gimple
*pattern_def_stmt
= NULL
;
6775 stmt_vec_info pattern_def_stmt_info
= NULL
;
6777 while (!gsi_end_p (pattern_def_si
))
6779 pattern_def_stmt
= gsi_stmt (pattern_def_si
);
6780 pattern_def_stmt_info
6781 = vinfo_for_stmt (pattern_def_stmt
);
6782 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info
)
6783 || STMT_VINFO_LIVE_P (pattern_def_stmt_info
))
6785 gsi_next (&pattern_def_si
);
6788 if (!gsi_end_p (pattern_def_si
))
6790 if (dump_enabled_p ())
6792 dump_printf_loc (MSG_NOTE
, vect_location
,
6793 "==> vectorizing pattern def "
6795 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
6796 pattern_def_stmt
, 0);
6797 dump_printf (MSG_NOTE
, "\n");
6800 stmt
= pattern_def_stmt
;
6801 stmt_info
= pattern_def_stmt_info
;
6805 pattern_def_si
= gsi_none ();
6806 transform_pattern_stmt
= false;
6810 transform_pattern_stmt
= false;
6813 if (STMT_VINFO_VECTYPE (stmt_info
))
6817 TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
6818 if (!STMT_SLP_TYPE (stmt_info
)
6819 && nunits
!= (unsigned int) vectorization_factor
6820 && dump_enabled_p ())
6821 /* For SLP VF is set according to unrolling factor, and not
6822 to vector size, hence for SLP this print is not valid. */
6823 dump_printf_loc (MSG_NOTE
, vect_location
, "multiple-types.\n");
6826 /* SLP. Schedule all the SLP instances when the first SLP stmt is
6828 if (STMT_SLP_TYPE (stmt_info
))
6832 slp_scheduled
= true;
6834 if (dump_enabled_p ())
6835 dump_printf_loc (MSG_NOTE
, vect_location
,
6836 "=== scheduling SLP instances ===\n");
6838 vect_schedule_slp (loop_vinfo
);
6841 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
6842 if (!vinfo_for_stmt (stmt
) || PURE_SLP_STMT (stmt_info
))
6844 if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
6846 pattern_def_seq
= NULL
;
6853 /* -------- vectorize statement ------------ */
6854 if (dump_enabled_p ())
6855 dump_printf_loc (MSG_NOTE
, vect_location
, "transform statement.\n");
6857 grouped_store
= false;
6858 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, NULL
, NULL
);
6861 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
6863 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
6864 interleaving chain was completed - free all the stores in
6867 vect_remove_stores (GROUP_FIRST_ELEMENT (stmt_info
));
6871 /* Free the attached stmt_vec_info and remove the stmt. */
6872 gimple
*store
= gsi_stmt (si
);
6873 free_stmt_vec_info (store
);
6874 unlink_stmt_vdef (store
);
6875 gsi_remove (&si
, true);
6876 release_defs (store
);
6879 /* Stores can only appear at the end of pattern statements. */
6880 gcc_assert (!transform_pattern_stmt
);
6881 pattern_def_seq
= NULL
;
6883 else if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
6885 pattern_def_seq
= NULL
;
6891 slpeel_make_loop_iterate_ntimes (loop
, ratio
);
6893 /* Reduce loop iterations by the vectorization factor. */
6894 scale_loop_profile (loop
, GCOV_COMPUTE_SCALE (1, vectorization_factor
),
6895 expected_iterations
/ vectorization_factor
);
6896 loop
->nb_iterations_upper_bound
6897 = wi::udiv_floor (loop
->nb_iterations_upper_bound
, vectorization_factor
);
6898 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
6899 && loop
->nb_iterations_upper_bound
!= 0)
6900 loop
->nb_iterations_upper_bound
= loop
->nb_iterations_upper_bound
- 1;
6901 if (loop
->any_estimate
)
6903 loop
->nb_iterations_estimate
6904 = wi::udiv_floor (loop
->nb_iterations_estimate
, vectorization_factor
);
6905 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
6906 && loop
->nb_iterations_estimate
!= 0)
6907 loop
->nb_iterations_estimate
= loop
->nb_iterations_estimate
- 1;
6910 if (dump_enabled_p ())
6912 dump_printf_loc (MSG_NOTE
, vect_location
,
6913 "LOOP VECTORIZED\n");
6915 dump_printf_loc (MSG_NOTE
, vect_location
,
6916 "OUTER LOOP VECTORIZED\n");
6917 dump_printf (MSG_NOTE
, "\n");