2 Copyright (C) 2003-2016 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 gimple
*next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (first
));
991 if (! STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (next
)))
993 next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next
));
995 /* If not all stmt in the chain are patterns try to handle
996 the chain without patterns. */
999 vect_fixup_reduc_chain (first
);
1000 LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
)[i
]
1001 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first
));
1006 /* Function vect_get_loop_niters.
1008 Determine how many iterations the loop is executed and place it
1009 in NUMBER_OF_ITERATIONS. Place the number of latch iterations
1010 in NUMBER_OF_ITERATIONSM1.
1012 Return the loop exit condition. */
1016 vect_get_loop_niters (struct loop
*loop
, tree
*number_of_iterations
,
1017 tree
*number_of_iterationsm1
)
1021 if (dump_enabled_p ())
1022 dump_printf_loc (MSG_NOTE
, vect_location
,
1023 "=== get_loop_niters ===\n");
1025 niters
= number_of_latch_executions (loop
);
1026 *number_of_iterationsm1
= niters
;
1028 /* We want the number of loop header executions which is the number
1029 of latch executions plus one.
1030 ??? For UINT_MAX latch executions this number overflows to zero
1031 for loops like do { n++; } while (n != 0); */
1032 if (niters
&& !chrec_contains_undetermined (niters
))
1033 niters
= fold_build2 (PLUS_EXPR
, TREE_TYPE (niters
), unshare_expr (niters
),
1034 build_int_cst (TREE_TYPE (niters
), 1));
1035 *number_of_iterations
= niters
;
1037 return get_loop_exit_condition (loop
);
1041 /* Function bb_in_loop_p
1043 Used as predicate for dfs order traversal of the loop bbs. */
1046 bb_in_loop_p (const_basic_block bb
, const void *data
)
1048 const struct loop
*const loop
= (const struct loop
*)data
;
1049 if (flow_bb_inside_loop_p (loop
, bb
))
1055 /* Function new_loop_vec_info.
1057 Create and initialize a new loop_vec_info struct for LOOP, as well as
1058 stmt_vec_info structs for all the stmts in LOOP. */
1060 static loop_vec_info
1061 new_loop_vec_info (struct loop
*loop
)
1065 gimple_stmt_iterator si
;
1066 unsigned int i
, nbbs
;
1068 res
= (loop_vec_info
) xcalloc (1, sizeof (struct _loop_vec_info
));
1069 res
->kind
= vec_info::loop
;
1070 LOOP_VINFO_LOOP (res
) = loop
;
1072 bbs
= get_loop_body (loop
);
1074 /* Create/Update stmt_info for all stmts in the loop. */
1075 for (i
= 0; i
< loop
->num_nodes
; i
++)
1077 basic_block bb
= bbs
[i
];
1079 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
1081 gimple
*phi
= gsi_stmt (si
);
1082 gimple_set_uid (phi
, 0);
1083 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, res
));
1086 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1088 gimple
*stmt
= gsi_stmt (si
);
1089 gimple_set_uid (stmt
, 0);
1090 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, res
));
1094 /* CHECKME: We want to visit all BBs before their successors (except for
1095 latch blocks, for which this assertion wouldn't hold). In the simple
1096 case of the loop forms we allow, a dfs order of the BBs would the same
1097 as reversed postorder traversal, so we are safe. */
1100 bbs
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1101 nbbs
= dfs_enumerate_from (loop
->header
, 0, bb_in_loop_p
,
1102 bbs
, loop
->num_nodes
, loop
);
1103 gcc_assert (nbbs
== loop
->num_nodes
);
1105 LOOP_VINFO_BBS (res
) = bbs
;
1106 LOOP_VINFO_NITERSM1 (res
) = NULL
;
1107 LOOP_VINFO_NITERS (res
) = NULL
;
1108 LOOP_VINFO_NITERS_UNCHANGED (res
) = NULL
;
1109 LOOP_VINFO_COST_MODEL_THRESHOLD (res
) = 0;
1110 LOOP_VINFO_VECTORIZABLE_P (res
) = 0;
1111 LOOP_VINFO_PEELING_FOR_ALIGNMENT (res
) = 0;
1112 LOOP_VINFO_VECT_FACTOR (res
) = 0;
1113 LOOP_VINFO_LOOP_NEST (res
) = vNULL
;
1114 LOOP_VINFO_DATAREFS (res
) = vNULL
;
1115 LOOP_VINFO_DDRS (res
) = vNULL
;
1116 LOOP_VINFO_UNALIGNED_DR (res
) = NULL
;
1117 LOOP_VINFO_MAY_MISALIGN_STMTS (res
) = vNULL
;
1118 LOOP_VINFO_MAY_ALIAS_DDRS (res
) = vNULL
;
1119 LOOP_VINFO_GROUPED_STORES (res
) = vNULL
;
1120 LOOP_VINFO_REDUCTIONS (res
) = vNULL
;
1121 LOOP_VINFO_REDUCTION_CHAINS (res
) = vNULL
;
1122 LOOP_VINFO_SLP_INSTANCES (res
) = vNULL
;
1123 LOOP_VINFO_SLP_UNROLLING_FACTOR (res
) = 1;
1124 LOOP_VINFO_TARGET_COST_DATA (res
) = init_cost (loop
);
1125 LOOP_VINFO_PEELING_FOR_GAPS (res
) = false;
1126 LOOP_VINFO_PEELING_FOR_NITER (res
) = false;
1127 LOOP_VINFO_OPERANDS_SWAPPED (res
) = false;
1133 /* Function destroy_loop_vec_info.
1135 Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
1136 stmts in the loop. */
1139 destroy_loop_vec_info (loop_vec_info loop_vinfo
, bool clean_stmts
)
1144 gimple_stmt_iterator si
;
1146 vec
<slp_instance
> slp_instances
;
1147 slp_instance instance
;
1153 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1155 bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1156 nbbs
= clean_stmts
? loop
->num_nodes
: 0;
1157 swapped
= LOOP_VINFO_OPERANDS_SWAPPED (loop_vinfo
);
1159 for (j
= 0; j
< nbbs
; j
++)
1161 basic_block bb
= bbs
[j
];
1162 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
1163 free_stmt_vec_info (gsi_stmt (si
));
1165 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); )
1167 gimple
*stmt
= gsi_stmt (si
);
1169 /* We may have broken canonical form by moving a constant
1170 into RHS1 of a commutative op. Fix such occurrences. */
1171 if (swapped
&& is_gimple_assign (stmt
))
1173 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1175 if ((code
== PLUS_EXPR
1176 || code
== POINTER_PLUS_EXPR
1177 || code
== MULT_EXPR
)
1178 && CONSTANT_CLASS_P (gimple_assign_rhs1 (stmt
)))
1179 swap_ssa_operands (stmt
,
1180 gimple_assign_rhs1_ptr (stmt
),
1181 gimple_assign_rhs2_ptr (stmt
));
1184 /* Free stmt_vec_info. */
1185 free_stmt_vec_info (stmt
);
1190 free (LOOP_VINFO_BBS (loop_vinfo
));
1191 vect_destroy_datarefs (loop_vinfo
);
1192 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo
));
1193 LOOP_VINFO_LOOP_NEST (loop_vinfo
).release ();
1194 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).release ();
1195 LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo
).release ();
1196 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
).release ();
1197 slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
1198 FOR_EACH_VEC_ELT (slp_instances
, j
, instance
)
1199 vect_free_slp_instance (instance
);
1201 LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).release ();
1202 LOOP_VINFO_GROUPED_STORES (loop_vinfo
).release ();
1203 LOOP_VINFO_REDUCTIONS (loop_vinfo
).release ();
1204 LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
).release ();
1206 destroy_cost_data (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
));
1207 loop_vinfo
->scalar_cost_vec
.release ();
1214 /* Calculate the cost of one scalar iteration of the loop. */
1216 vect_compute_single_scalar_iteration_cost (loop_vec_info loop_vinfo
)
1218 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1219 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1220 int nbbs
= loop
->num_nodes
, factor
, scalar_single_iter_cost
= 0;
1221 int innerloop_iters
, i
;
1223 /* Count statements in scalar loop. Using this as scalar cost for a single
1226 TODO: Add outer loop support.
1228 TODO: Consider assigning different costs to different scalar
1232 innerloop_iters
= 1;
1234 innerloop_iters
= 50; /* FIXME */
1236 for (i
= 0; i
< nbbs
; i
++)
1238 gimple_stmt_iterator si
;
1239 basic_block bb
= bbs
[i
];
1241 if (bb
->loop_father
== loop
->inner
)
1242 factor
= innerloop_iters
;
1246 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1248 gimple
*stmt
= gsi_stmt (si
);
1249 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1251 if (!is_gimple_assign (stmt
) && !is_gimple_call (stmt
))
1254 /* Skip stmts that are not vectorized inside the loop. */
1256 && !STMT_VINFO_RELEVANT_P (stmt_info
)
1257 && (!STMT_VINFO_LIVE_P (stmt_info
)
1258 || !VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
1259 && !STMT_VINFO_IN_PATTERN_P (stmt_info
))
1262 vect_cost_for_stmt kind
;
1263 if (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
)))
1265 if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))))
1268 kind
= scalar_store
;
1273 scalar_single_iter_cost
1274 += record_stmt_cost (&LOOP_VINFO_SCALAR_ITERATION_COST (loop_vinfo
),
1275 factor
, kind
, NULL
, 0, vect_prologue
);
1278 LOOP_VINFO_SINGLE_SCALAR_ITERATION_COST (loop_vinfo
)
1279 = scalar_single_iter_cost
;
1283 /* Function vect_analyze_loop_form_1.
1285 Verify that certain CFG restrictions hold, including:
1286 - the loop has a pre-header
1287 - the loop has a single entry and exit
1288 - the loop exit condition is simple enough, and the number of iterations
1289 can be analyzed (a countable loop). */
1292 vect_analyze_loop_form_1 (struct loop
*loop
, gcond
**loop_cond
,
1293 tree
*number_of_iterationsm1
,
1294 tree
*number_of_iterations
, gcond
**inner_loop_cond
)
1296 if (dump_enabled_p ())
1297 dump_printf_loc (MSG_NOTE
, vect_location
,
1298 "=== vect_analyze_loop_form ===\n");
1300 /* Different restrictions apply when we are considering an inner-most loop,
1301 vs. an outer (nested) loop.
1302 (FORNOW. May want to relax some of these restrictions in the future). */
1306 /* Inner-most loop. We currently require that the number of BBs is
1307 exactly 2 (the header and latch). Vectorizable inner-most loops
1318 if (loop
->num_nodes
!= 2)
1320 if (dump_enabled_p ())
1321 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1322 "not vectorized: control flow in loop.\n");
1326 if (empty_block_p (loop
->header
))
1328 if (dump_enabled_p ())
1329 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1330 "not vectorized: empty loop.\n");
1336 struct loop
*innerloop
= loop
->inner
;
1339 /* Nested loop. We currently require that the loop is doubly-nested,
1340 contains a single inner loop, and the number of BBs is exactly 5.
1341 Vectorizable outer-loops look like this:
1353 The inner-loop has the properties expected of inner-most loops
1354 as described above. */
1356 if ((loop
->inner
)->inner
|| (loop
->inner
)->next
)
1358 if (dump_enabled_p ())
1359 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1360 "not vectorized: multiple nested loops.\n");
1364 if (loop
->num_nodes
!= 5)
1366 if (dump_enabled_p ())
1367 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1368 "not vectorized: control flow in loop.\n");
1372 entryedge
= loop_preheader_edge (innerloop
);
1373 if (entryedge
->src
!= loop
->header
1374 || !single_exit (innerloop
)
1375 || single_exit (innerloop
)->dest
!= EDGE_PRED (loop
->latch
, 0)->src
)
1377 if (dump_enabled_p ())
1378 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1379 "not vectorized: unsupported outerloop form.\n");
1383 /* Analyze the inner-loop. */
1384 tree inner_niterm1
, inner_niter
;
1385 if (! vect_analyze_loop_form_1 (loop
->inner
, inner_loop_cond
,
1386 &inner_niterm1
, &inner_niter
, NULL
))
1388 if (dump_enabled_p ())
1389 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1390 "not vectorized: Bad inner loop.\n");
1394 if (!expr_invariant_in_loop_p (loop
, inner_niter
))
1396 if (dump_enabled_p ())
1397 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1398 "not vectorized: inner-loop count not"
1403 if (dump_enabled_p ())
1404 dump_printf_loc (MSG_NOTE
, vect_location
,
1405 "Considering outer-loop vectorization.\n");
1408 if (!single_exit (loop
)
1409 || EDGE_COUNT (loop
->header
->preds
) != 2)
1411 if (dump_enabled_p ())
1413 if (!single_exit (loop
))
1414 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1415 "not vectorized: multiple exits.\n");
1416 else if (EDGE_COUNT (loop
->header
->preds
) != 2)
1417 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1418 "not vectorized: too many incoming edges.\n");
1423 /* We assume that the loop exit condition is at the end of the loop. i.e,
1424 that the loop is represented as a do-while (with a proper if-guard
1425 before the loop if needed), where the loop header contains all the
1426 executable statements, and the latch is empty. */
1427 if (!empty_block_p (loop
->latch
)
1428 || !gimple_seq_empty_p (phi_nodes (loop
->latch
)))
1430 if (dump_enabled_p ())
1431 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1432 "not vectorized: latch block not empty.\n");
1436 /* Make sure there exists a single-predecessor exit bb: */
1437 if (!single_pred_p (single_exit (loop
)->dest
))
1439 edge e
= single_exit (loop
);
1440 if (!(e
->flags
& EDGE_ABNORMAL
))
1442 split_loop_exit_edge (e
);
1443 if (dump_enabled_p ())
1444 dump_printf (MSG_NOTE
, "split exit edge.\n");
1448 if (dump_enabled_p ())
1449 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1450 "not vectorized: abnormal loop exit edge.\n");
1455 *loop_cond
= vect_get_loop_niters (loop
, number_of_iterations
,
1456 number_of_iterationsm1
);
1459 if (dump_enabled_p ())
1460 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1461 "not vectorized: complicated exit condition.\n");
1465 if (!*number_of_iterations
1466 || chrec_contains_undetermined (*number_of_iterations
))
1468 if (dump_enabled_p ())
1469 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1470 "not vectorized: number of iterations cannot be "
1475 if (integer_zerop (*number_of_iterations
))
1477 if (dump_enabled_p ())
1478 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1479 "not vectorized: number of iterations = 0.\n");
1486 /* Analyze LOOP form and return a loop_vec_info if it is of suitable form. */
1489 vect_analyze_loop_form (struct loop
*loop
)
1491 tree number_of_iterations
, number_of_iterationsm1
;
1492 gcond
*loop_cond
, *inner_loop_cond
= NULL
;
1494 if (! vect_analyze_loop_form_1 (loop
, &loop_cond
, &number_of_iterationsm1
,
1495 &number_of_iterations
, &inner_loop_cond
))
1498 loop_vec_info loop_vinfo
= new_loop_vec_info (loop
);
1499 LOOP_VINFO_NITERSM1 (loop_vinfo
) = number_of_iterationsm1
;
1500 LOOP_VINFO_NITERS (loop_vinfo
) = number_of_iterations
;
1501 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo
) = number_of_iterations
;
1503 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
1505 if (dump_enabled_p ())
1507 dump_printf_loc (MSG_NOTE
, vect_location
,
1508 "Symbolic number of iterations is ");
1509 dump_generic_expr (MSG_NOTE
, TDF_DETAILS
, number_of_iterations
);
1510 dump_printf (MSG_NOTE
, "\n");
1514 STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond
)) = loop_exit_ctrl_vec_info_type
;
1515 if (inner_loop_cond
)
1516 STMT_VINFO_TYPE (vinfo_for_stmt (inner_loop_cond
))
1517 = loop_exit_ctrl_vec_info_type
;
1519 gcc_assert (!loop
->aux
);
1520 loop
->aux
= loop_vinfo
;
1526 /* Scan the loop stmts and dependent on whether there are any (non-)SLP
1527 statements update the vectorization factor. */
1530 vect_update_vf_for_slp (loop_vec_info loop_vinfo
)
1532 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1533 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1534 int nbbs
= loop
->num_nodes
;
1535 unsigned int vectorization_factor
;
1538 if (dump_enabled_p ())
1539 dump_printf_loc (MSG_NOTE
, vect_location
,
1540 "=== vect_update_vf_for_slp ===\n");
1542 vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1543 gcc_assert (vectorization_factor
!= 0);
1545 /* If all the stmts in the loop can be SLPed, we perform only SLP, and
1546 vectorization factor of the loop is the unrolling factor required by
1547 the SLP instances. If that unrolling factor is 1, we say, that we
1548 perform pure SLP on loop - cross iteration parallelism is not
1550 bool only_slp_in_loop
= true;
1551 for (i
= 0; i
< nbbs
; i
++)
1553 basic_block bb
= bbs
[i
];
1554 for (gimple_stmt_iterator si
= gsi_start_bb (bb
); !gsi_end_p (si
);
1557 gimple
*stmt
= gsi_stmt (si
);
1558 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1559 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
1560 && STMT_VINFO_RELATED_STMT (stmt_info
))
1562 stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
1563 stmt_info
= vinfo_for_stmt (stmt
);
1565 if ((STMT_VINFO_RELEVANT_P (stmt_info
)
1566 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
1567 && !PURE_SLP_STMT (stmt_info
))
1568 /* STMT needs both SLP and loop-based vectorization. */
1569 only_slp_in_loop
= false;
1573 if (only_slp_in_loop
)
1574 vectorization_factor
= LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
);
1576 vectorization_factor
1577 = least_common_multiple (vectorization_factor
,
1578 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
));
1580 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
1581 if (dump_enabled_p ())
1582 dump_printf_loc (MSG_NOTE
, vect_location
,
1583 "Updating vectorization factor to %d\n",
1584 vectorization_factor
);
1587 /* Function vect_analyze_loop_operations.
1589 Scan the loop stmts and make sure they are all vectorizable. */
1592 vect_analyze_loop_operations (loop_vec_info loop_vinfo
)
1594 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1595 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1596 int nbbs
= loop
->num_nodes
;
1598 stmt_vec_info stmt_info
;
1599 bool need_to_vectorize
= false;
1602 if (dump_enabled_p ())
1603 dump_printf_loc (MSG_NOTE
, vect_location
,
1604 "=== vect_analyze_loop_operations ===\n");
1606 for (i
= 0; i
< nbbs
; i
++)
1608 basic_block bb
= bbs
[i
];
1610 for (gphi_iterator si
= gsi_start_phis (bb
); !gsi_end_p (si
);
1613 gphi
*phi
= si
.phi ();
1616 stmt_info
= vinfo_for_stmt (phi
);
1617 if (dump_enabled_p ())
1619 dump_printf_loc (MSG_NOTE
, vect_location
, "examining phi: ");
1620 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
1621 dump_printf (MSG_NOTE
, "\n");
1623 if (virtual_operand_p (gimple_phi_result (phi
)))
1626 /* Inner-loop loop-closed exit phi in outer-loop vectorization
1627 (i.e., a phi in the tail of the outer-loop). */
1628 if (! is_loop_header_bb_p (bb
))
1630 /* FORNOW: we currently don't support the case that these phis
1631 are not used in the outerloop (unless it is double reduction,
1632 i.e., this phi is vect_reduction_def), cause this case
1633 requires to actually do something here. */
1634 if ((!STMT_VINFO_RELEVANT_P (stmt_info
)
1635 || STMT_VINFO_LIVE_P (stmt_info
))
1636 && STMT_VINFO_DEF_TYPE (stmt_info
)
1637 != vect_double_reduction_def
)
1639 if (dump_enabled_p ())
1640 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1641 "Unsupported loop-closed phi in "
1646 /* If PHI is used in the outer loop, we check that its operand
1647 is defined in the inner loop. */
1648 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1651 gimple
*op_def_stmt
;
1653 if (gimple_phi_num_args (phi
) != 1)
1656 phi_op
= PHI_ARG_DEF (phi
, 0);
1657 if (TREE_CODE (phi_op
) != SSA_NAME
)
1660 op_def_stmt
= SSA_NAME_DEF_STMT (phi_op
);
1661 if (gimple_nop_p (op_def_stmt
)
1662 || !flow_bb_inside_loop_p (loop
, gimple_bb (op_def_stmt
))
1663 || !vinfo_for_stmt (op_def_stmt
))
1666 if (STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1667 != vect_used_in_outer
1668 && STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1669 != vect_used_in_outer_by_reduction
)
1676 gcc_assert (stmt_info
);
1678 if (STMT_VINFO_LIVE_P (stmt_info
))
1680 /* FORNOW: not yet supported. */
1681 if (dump_enabled_p ())
1682 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1683 "not vectorized: value used after loop.\n");
1687 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
1688 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_induction_def
)
1690 /* A scalar-dependence cycle that we don't support. */
1691 if (dump_enabled_p ())
1692 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1693 "not vectorized: scalar dependence cycle.\n");
1697 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1699 need_to_vectorize
= true;
1700 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
1701 ok
= vectorizable_induction (phi
, NULL
, NULL
);
1706 if (dump_enabled_p ())
1708 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1709 "not vectorized: relevant phi not "
1711 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, phi
, 0);
1712 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1718 for (gimple_stmt_iterator si
= gsi_start_bb (bb
); !gsi_end_p (si
);
1721 gimple
*stmt
= gsi_stmt (si
);
1722 if (!gimple_clobber_p (stmt
)
1723 && !vect_analyze_stmt (stmt
, &need_to_vectorize
, NULL
))
1728 /* All operations in the loop are either irrelevant (deal with loop
1729 control, or dead), or only used outside the loop and can be moved
1730 out of the loop (e.g. invariants, inductions). The loop can be
1731 optimized away by scalar optimizations. We're better off not
1732 touching this loop. */
1733 if (!need_to_vectorize
)
1735 if (dump_enabled_p ())
1736 dump_printf_loc (MSG_NOTE
, vect_location
,
1737 "All the computation can be taken out of the loop.\n");
1738 if (dump_enabled_p ())
1739 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1740 "not vectorized: redundant loop. no profit to "
1749 /* Function vect_analyze_loop_2.
1751 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1752 for it. The different analyses will record information in the
1753 loop_vec_info struct. */
1755 vect_analyze_loop_2 (loop_vec_info loop_vinfo
, bool &fatal
)
1758 int max_vf
= MAX_VECTORIZATION_FACTOR
;
1760 unsigned int n_stmts
= 0;
1762 /* The first group of checks is independent of the vector size. */
1765 /* Find all data references in the loop (which correspond to vdefs/vuses)
1766 and analyze their evolution in the loop. */
1768 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1770 loop_p loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1771 if (!find_loop_nest (loop
, &LOOP_VINFO_LOOP_NEST (loop_vinfo
)))
1773 if (dump_enabled_p ())
1774 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1775 "not vectorized: loop contains function calls"
1776 " or data references that cannot be analyzed\n");
1780 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
1781 for (gimple_stmt_iterator gsi
= gsi_start_bb (bbs
[i
]);
1782 !gsi_end_p (gsi
); gsi_next (&gsi
))
1784 gimple
*stmt
= gsi_stmt (gsi
);
1785 if (is_gimple_debug (stmt
))
1788 if (!find_data_references_in_stmt (loop
, stmt
,
1789 &LOOP_VINFO_DATAREFS (loop_vinfo
)))
1791 if (is_gimple_call (stmt
) && loop
->safelen
)
1793 tree fndecl
= gimple_call_fndecl (stmt
), op
;
1794 if (fndecl
!= NULL_TREE
)
1796 cgraph_node
*node
= cgraph_node::get (fndecl
);
1797 if (node
!= NULL
&& node
->simd_clones
!= NULL
)
1799 unsigned int j
, n
= gimple_call_num_args (stmt
);
1800 for (j
= 0; j
< n
; j
++)
1802 op
= gimple_call_arg (stmt
, j
);
1804 || (REFERENCE_CLASS_P (op
)
1805 && get_base_address (op
)))
1808 op
= gimple_call_lhs (stmt
);
1809 /* Ignore #pragma omp declare simd functions
1810 if they don't have data references in the
1811 call stmt itself. */
1815 || (REFERENCE_CLASS_P (op
)
1816 && get_base_address (op
)))))
1821 if (dump_enabled_p ())
1822 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1823 "not vectorized: loop contains function "
1824 "calls or data references that cannot "
1830 /* Analyze the data references and also adjust the minimal
1831 vectorization factor according to the loads and stores. */
1833 ok
= vect_analyze_data_refs (loop_vinfo
, &min_vf
);
1836 if (dump_enabled_p ())
1837 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1838 "bad data references.\n");
1842 /* Classify all cross-iteration scalar data-flow cycles.
1843 Cross-iteration cycles caused by virtual phis are analyzed separately. */
1844 vect_analyze_scalar_cycles (loop_vinfo
);
1846 vect_pattern_recog (loop_vinfo
);
1848 vect_fixup_scalar_cycles_with_patterns (loop_vinfo
);
1850 /* Analyze the access patterns of the data-refs in the loop (consecutive,
1851 complex, etc.). FORNOW: Only handle consecutive access pattern. */
1853 ok
= vect_analyze_data_ref_accesses (loop_vinfo
);
1856 if (dump_enabled_p ())
1857 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1858 "bad data access.\n");
1862 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
1864 ok
= vect_mark_stmts_to_be_vectorized (loop_vinfo
);
1867 if (dump_enabled_p ())
1868 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1869 "unexpected pattern.\n");
1873 /* While the rest of the analysis below depends on it in some way. */
1876 /* Analyze data dependences between the data-refs in the loop
1877 and adjust the maximum vectorization factor according to
1879 FORNOW: fail at the first data dependence that we encounter. */
1881 ok
= vect_analyze_data_ref_dependences (loop_vinfo
, &max_vf
);
1885 if (dump_enabled_p ())
1886 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1887 "bad data dependence.\n");
1891 ok
= vect_determine_vectorization_factor (loop_vinfo
);
1894 if (dump_enabled_p ())
1895 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1896 "can't determine vectorization factor.\n");
1899 if (max_vf
< LOOP_VINFO_VECT_FACTOR (loop_vinfo
))
1901 if (dump_enabled_p ())
1902 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1903 "bad data dependence.\n");
1907 /* Compute the scalar iteration cost. */
1908 vect_compute_single_scalar_iteration_cost (loop_vinfo
);
1910 int saved_vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1911 HOST_WIDE_INT estimated_niter
;
1913 int min_scalar_loop_bound
;
1915 /* Check the SLP opportunities in the loop, analyze and build SLP trees. */
1916 ok
= vect_analyze_slp (loop_vinfo
, n_stmts
);
1920 /* If there are any SLP instances mark them as pure_slp. */
1921 bool slp
= vect_make_slp_decision (loop_vinfo
);
1924 /* Find stmts that need to be both vectorized and SLPed. */
1925 vect_detect_hybrid_slp (loop_vinfo
);
1927 /* Update the vectorization factor based on the SLP decision. */
1928 vect_update_vf_for_slp (loop_vinfo
);
1931 /* This is the point where we can re-start analysis with SLP forced off. */
1934 /* Now the vectorization factor is final. */
1935 unsigned vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1936 gcc_assert (vectorization_factor
!= 0);
1938 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
) && dump_enabled_p ())
1939 dump_printf_loc (MSG_NOTE
, vect_location
,
1940 "vectorization_factor = %d, niters = "
1941 HOST_WIDE_INT_PRINT_DEC
"\n", vectorization_factor
,
1942 LOOP_VINFO_INT_NITERS (loop_vinfo
));
1944 HOST_WIDE_INT max_niter
1945 = max_stmt_executions_int (LOOP_VINFO_LOOP (loop_vinfo
));
1946 if ((LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1947 && (LOOP_VINFO_INT_NITERS (loop_vinfo
) < vectorization_factor
))
1949 && (unsigned HOST_WIDE_INT
) max_niter
< vectorization_factor
))
1951 if (dump_enabled_p ())
1952 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1953 "not vectorized: iteration count smaller than "
1954 "vectorization factor.\n");
1958 /* Analyze the alignment of the data-refs in the loop.
1959 Fail if a data reference is found that cannot be vectorized. */
1961 ok
= vect_analyze_data_refs_alignment (loop_vinfo
);
1964 if (dump_enabled_p ())
1965 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1966 "bad data alignment.\n");
1970 /* Prune the list of ddrs to be tested at run-time by versioning for alias.
1971 It is important to call pruning after vect_analyze_data_ref_accesses,
1972 since we use grouping information gathered by interleaving analysis. */
1973 ok
= vect_prune_runtime_alias_test_list (loop_vinfo
);
1976 if (dump_enabled_p ())
1977 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1978 "number of versioning for alias "
1979 "run-time tests exceeds %d "
1980 "(--param vect-max-version-for-alias-checks)\n",
1981 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS
));
1985 /* This pass will decide on using loop versioning and/or loop peeling in
1986 order to enhance the alignment of data references in the loop. */
1987 ok
= vect_enhance_data_refs_alignment (loop_vinfo
);
1990 if (dump_enabled_p ())
1991 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1992 "bad data alignment.\n");
1998 /* Analyze operations in the SLP instances. Note this may
1999 remove unsupported SLP instances which makes the above
2000 SLP kind detection invalid. */
2001 unsigned old_size
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).length ();
2002 vect_slp_analyze_operations (LOOP_VINFO_SLP_INSTANCES (loop_vinfo
),
2003 LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
));
2004 if (LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).length () != old_size
)
2008 /* Scan all the remaining operations in the loop that are not subject
2009 to SLP and make sure they are vectorizable. */
2010 ok
= vect_analyze_loop_operations (loop_vinfo
);
2013 if (dump_enabled_p ())
2014 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2015 "bad operation or unsupported loop bound.\n");
2019 /* Analyze cost. Decide if worth while to vectorize. */
2020 int min_profitable_estimate
, min_profitable_iters
;
2021 vect_estimate_min_profitable_iters (loop_vinfo
, &min_profitable_iters
,
2022 &min_profitable_estimate
);
2024 if (min_profitable_iters
< 0)
2026 if (dump_enabled_p ())
2027 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2028 "not vectorized: vectorization not profitable.\n");
2029 if (dump_enabled_p ())
2030 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2031 "not vectorized: vector version will never be "
2036 min_scalar_loop_bound
= ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND
)
2037 * vectorization_factor
) - 1);
2039 /* Use the cost model only if it is more conservative than user specified
2041 th
= (unsigned) min_scalar_loop_bound
;
2042 if (min_profitable_iters
2043 && (!min_scalar_loop_bound
2044 || min_profitable_iters
> min_scalar_loop_bound
))
2045 th
= (unsigned) min_profitable_iters
;
2047 LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo
) = th
;
2049 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
2050 && LOOP_VINFO_INT_NITERS (loop_vinfo
) <= th
)
2052 if (dump_enabled_p ())
2053 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2054 "not vectorized: vectorization not profitable.\n");
2055 if (dump_enabled_p ())
2056 dump_printf_loc (MSG_NOTE
, vect_location
,
2057 "not vectorized: iteration count smaller than user "
2058 "specified loop bound parameter or minimum profitable "
2059 "iterations (whichever is more conservative).\n");
2064 = estimated_stmt_executions_int (LOOP_VINFO_LOOP (loop_vinfo
));
2065 if (estimated_niter
!= -1
2066 && ((unsigned HOST_WIDE_INT
) estimated_niter
2067 <= MAX (th
, (unsigned)min_profitable_estimate
)))
2069 if (dump_enabled_p ())
2070 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2071 "not vectorized: estimated iteration count too "
2073 if (dump_enabled_p ())
2074 dump_printf_loc (MSG_NOTE
, vect_location
,
2075 "not vectorized: estimated iteration count smaller "
2076 "than specified loop bound parameter or minimum "
2077 "profitable iterations (whichever is more "
2078 "conservative).\n");
2082 /* Decide whether we need to create an epilogue loop to handle
2083 remaining scalar iterations. */
2084 th
= ((LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo
) + 1)
2085 / LOOP_VINFO_VECT_FACTOR (loop_vinfo
))
2086 * LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2088 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
2089 && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
) > 0)
2091 if (ctz_hwi (LOOP_VINFO_INT_NITERS (loop_vinfo
)
2092 - LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
))
2093 < exact_log2 (LOOP_VINFO_VECT_FACTOR (loop_vinfo
)))
2094 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
) = true;
2096 else if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
)
2097 || (tree_ctz (LOOP_VINFO_NITERS (loop_vinfo
))
2098 < (unsigned)exact_log2 (LOOP_VINFO_VECT_FACTOR (loop_vinfo
))
2099 /* In case of versioning, check if the maximum number of
2100 iterations is greater than th. If they are identical,
2101 the epilogue is unnecessary. */
2102 && ((!LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
)
2103 && !LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
))
2104 || (unsigned HOST_WIDE_INT
) max_niter
> th
)))
2105 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
) = true;
2107 /* If an epilogue loop is required make sure we can create one. */
2108 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
2109 || LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
))
2111 if (dump_enabled_p ())
2112 dump_printf_loc (MSG_NOTE
, vect_location
, "epilog loop required\n");
2113 if (!vect_can_advance_ivs_p (loop_vinfo
)
2114 || !slpeel_can_duplicate_loop_p (LOOP_VINFO_LOOP (loop_vinfo
),
2115 single_exit (LOOP_VINFO_LOOP
2118 if (dump_enabled_p ())
2119 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2120 "not vectorized: can't create required "
2126 gcc_assert (vectorization_factor
2127 == (unsigned)LOOP_VINFO_VECT_FACTOR (loop_vinfo
));
2129 /* Ok to vectorize! */
2133 /* Try again with SLP forced off but if we didn't do any SLP there is
2134 no point in re-trying. */
2138 /* If there are reduction chains re-trying will fail anyway. */
2139 if (! LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
).is_empty ())
2142 /* Likewise if the grouped loads or stores in the SLP cannot be handled
2143 via interleaving or lane instructions. */
2144 slp_instance instance
;
2147 FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (loop_vinfo
), i
, instance
)
2149 stmt_vec_info vinfo
;
2150 vinfo
= vinfo_for_stmt
2151 (SLP_TREE_SCALAR_STMTS (SLP_INSTANCE_TREE (instance
))[0]);
2152 if (! STMT_VINFO_GROUPED_ACCESS (vinfo
))
2154 vinfo
= vinfo_for_stmt (STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo
));
2155 unsigned int size
= STMT_VINFO_GROUP_SIZE (vinfo
);
2156 tree vectype
= STMT_VINFO_VECTYPE (vinfo
);
2157 if (! vect_store_lanes_supported (vectype
, size
)
2158 && ! vect_grouped_store_supported (vectype
, size
))
2160 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (instance
), j
, node
)
2162 vinfo
= vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (node
)[0]);
2163 vinfo
= vinfo_for_stmt (STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo
));
2164 size
= STMT_VINFO_GROUP_SIZE (vinfo
);
2165 vectype
= STMT_VINFO_VECTYPE (vinfo
);
2166 if (! vect_load_lanes_supported (vectype
, size
)
2167 && ! vect_grouped_load_supported (vectype
, size
))
2172 if (dump_enabled_p ())
2173 dump_printf_loc (MSG_NOTE
, vect_location
,
2174 "re-trying with SLP disabled\n");
2176 /* Roll back state appropriately. No SLP this time. */
2178 /* Restore vectorization factor as it were without SLP. */
2179 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = saved_vectorization_factor
;
2180 /* Free the SLP instances. */
2181 FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (loop_vinfo
), j
, instance
)
2182 vect_free_slp_instance (instance
);
2183 LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).release ();
2184 /* Reset SLP type to loop_vect on all stmts. */
2185 for (i
= 0; i
< LOOP_VINFO_LOOP (loop_vinfo
)->num_nodes
; ++i
)
2187 basic_block bb
= LOOP_VINFO_BBS (loop_vinfo
)[i
];
2188 for (gimple_stmt_iterator si
= gsi_start_bb (bb
);
2189 !gsi_end_p (si
); gsi_next (&si
))
2191 stmt_vec_info stmt_info
= vinfo_for_stmt (gsi_stmt (si
));
2192 STMT_SLP_TYPE (stmt_info
) = loop_vect
;
2193 if (STMT_VINFO_IN_PATTERN_P (stmt_info
))
2195 stmt_info
= vinfo_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info
));
2196 STMT_SLP_TYPE (stmt_info
) = loop_vect
;
2197 for (gimple_stmt_iterator pi
2198 = gsi_start (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
));
2199 !gsi_end_p (pi
); gsi_next (&pi
))
2201 gimple
*pstmt
= gsi_stmt (pi
);
2202 STMT_SLP_TYPE (vinfo_for_stmt (pstmt
)) = loop_vect
;
2207 /* Free optimized alias test DDRS. */
2208 LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo
).release ();
2209 /* Reset target cost data. */
2210 destroy_cost_data (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
));
2211 LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
)
2212 = init_cost (LOOP_VINFO_LOOP (loop_vinfo
));
2213 /* Reset assorted flags. */
2214 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
) = false;
2215 LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) = false;
2216 LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo
) = 0;
2221 /* Function vect_analyze_loop.
2223 Apply a set of analyses on LOOP, and create a loop_vec_info struct
2224 for it. The different analyses will record information in the
2225 loop_vec_info struct. */
2227 vect_analyze_loop (struct loop
*loop
)
2229 loop_vec_info loop_vinfo
;
2230 unsigned int vector_sizes
;
2232 /* Autodetect first vector size we try. */
2233 current_vector_size
= 0;
2234 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
2236 if (dump_enabled_p ())
2237 dump_printf_loc (MSG_NOTE
, vect_location
,
2238 "===== analyze_loop_nest =====\n");
2240 if (loop_outer (loop
)
2241 && loop_vec_info_for_loop (loop_outer (loop
))
2242 && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop
))))
2244 if (dump_enabled_p ())
2245 dump_printf_loc (MSG_NOTE
, vect_location
,
2246 "outer-loop already vectorized.\n");
2252 /* Check the CFG characteristics of the loop (nesting, entry/exit). */
2253 loop_vinfo
= vect_analyze_loop_form (loop
);
2256 if (dump_enabled_p ())
2257 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2258 "bad loop form.\n");
2263 if (vect_analyze_loop_2 (loop_vinfo
, fatal
))
2265 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
) = 1;
2270 destroy_loop_vec_info (loop_vinfo
, true);
2272 vector_sizes
&= ~current_vector_size
;
2274 || vector_sizes
== 0
2275 || current_vector_size
== 0)
2278 /* Try the next biggest vector size. */
2279 current_vector_size
= 1 << floor_log2 (vector_sizes
);
2280 if (dump_enabled_p ())
2281 dump_printf_loc (MSG_NOTE
, vect_location
,
2282 "***** Re-trying analysis with "
2283 "vector size %d\n", current_vector_size
);
2288 /* Function reduction_code_for_scalar_code
2291 CODE - tree_code of a reduction operations.
2294 REDUC_CODE - the corresponding tree-code to be used to reduce the
2295 vector of partial results into a single scalar result, or ERROR_MARK
2296 if the operation is a supported reduction operation, but does not have
2299 Return FALSE if CODE currently cannot be vectorized as reduction. */
2302 reduction_code_for_scalar_code (enum tree_code code
,
2303 enum tree_code
*reduc_code
)
2308 *reduc_code
= REDUC_MAX_EXPR
;
2312 *reduc_code
= REDUC_MIN_EXPR
;
2316 *reduc_code
= REDUC_PLUS_EXPR
;
2324 *reduc_code
= ERROR_MARK
;
2333 /* Error reporting helper for vect_is_simple_reduction below. GIMPLE statement
2334 STMT is printed with a message MSG. */
2337 report_vect_op (int msg_type
, gimple
*stmt
, const char *msg
)
2339 dump_printf_loc (msg_type
, vect_location
, "%s", msg
);
2340 dump_gimple_stmt (msg_type
, TDF_SLIM
, stmt
, 0);
2341 dump_printf (msg_type
, "\n");
2345 /* Detect SLP reduction of the form:
2355 PHI is the reduction phi node (#a1 = phi <a5, a0> above)
2356 FIRST_STMT is the first reduction stmt in the chain
2357 (a2 = operation (a1)).
2359 Return TRUE if a reduction chain was detected. */
2362 vect_is_slp_reduction (loop_vec_info loop_info
, gimple
*phi
,
2365 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
2366 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
2367 enum tree_code code
;
2368 gimple
*current_stmt
= NULL
, *loop_use_stmt
= NULL
, *first
, *next_stmt
;
2369 stmt_vec_info use_stmt_info
, current_stmt_info
;
2371 imm_use_iterator imm_iter
;
2372 use_operand_p use_p
;
2373 int nloop_uses
, size
= 0, n_out_of_loop_uses
;
2376 if (loop
!= vect_loop
)
2379 lhs
= PHI_RESULT (phi
);
2380 code
= gimple_assign_rhs_code (first_stmt
);
2384 n_out_of_loop_uses
= 0;
2385 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2387 gimple
*use_stmt
= USE_STMT (use_p
);
2388 if (is_gimple_debug (use_stmt
))
2391 /* Check if we got back to the reduction phi. */
2392 if (use_stmt
== phi
)
2394 loop_use_stmt
= use_stmt
;
2399 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2401 loop_use_stmt
= use_stmt
;
2405 n_out_of_loop_uses
++;
2407 /* There are can be either a single use in the loop or two uses in
2409 if (nloop_uses
> 1 || (n_out_of_loop_uses
&& nloop_uses
))
2416 /* We reached a statement with no loop uses. */
2417 if (nloop_uses
== 0)
2420 /* This is a loop exit phi, and we haven't reached the reduction phi. */
2421 if (gimple_code (loop_use_stmt
) == GIMPLE_PHI
)
2424 if (!is_gimple_assign (loop_use_stmt
)
2425 || code
!= gimple_assign_rhs_code (loop_use_stmt
)
2426 || !flow_bb_inside_loop_p (loop
, gimple_bb (loop_use_stmt
)))
2429 /* Insert USE_STMT into reduction chain. */
2430 use_stmt_info
= vinfo_for_stmt (loop_use_stmt
);
2433 current_stmt_info
= vinfo_for_stmt (current_stmt
);
2434 GROUP_NEXT_ELEMENT (current_stmt_info
) = loop_use_stmt
;
2435 GROUP_FIRST_ELEMENT (use_stmt_info
)
2436 = GROUP_FIRST_ELEMENT (current_stmt_info
);
2439 GROUP_FIRST_ELEMENT (use_stmt_info
) = loop_use_stmt
;
2441 lhs
= gimple_assign_lhs (loop_use_stmt
);
2442 current_stmt
= loop_use_stmt
;
2446 if (!found
|| loop_use_stmt
!= phi
|| size
< 2)
2449 /* Swap the operands, if needed, to make the reduction operand be the second
2451 lhs
= PHI_RESULT (phi
);
2452 next_stmt
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
2455 if (gimple_assign_rhs2 (next_stmt
) == lhs
)
2457 tree op
= gimple_assign_rhs1 (next_stmt
);
2458 gimple
*def_stmt
= NULL
;
2460 if (TREE_CODE (op
) == SSA_NAME
)
2461 def_stmt
= SSA_NAME_DEF_STMT (op
);
2463 /* Check that the other def is either defined in the loop
2464 ("vect_internal_def"), or it's an induction (defined by a
2465 loop-header phi-node). */
2467 && gimple_bb (def_stmt
)
2468 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2469 && (is_gimple_assign (def_stmt
)
2470 || is_gimple_call (def_stmt
)
2471 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2472 == vect_induction_def
2473 || (gimple_code (def_stmt
) == GIMPLE_PHI
2474 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2475 == vect_internal_def
2476 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
2478 lhs
= gimple_assign_lhs (next_stmt
);
2479 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
2487 tree op
= gimple_assign_rhs2 (next_stmt
);
2488 gimple
*def_stmt
= NULL
;
2490 if (TREE_CODE (op
) == SSA_NAME
)
2491 def_stmt
= SSA_NAME_DEF_STMT (op
);
2493 /* Check that the other def is either defined in the loop
2494 ("vect_internal_def"), or it's an induction (defined by a
2495 loop-header phi-node). */
2497 && gimple_bb (def_stmt
)
2498 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2499 && (is_gimple_assign (def_stmt
)
2500 || is_gimple_call (def_stmt
)
2501 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2502 == vect_induction_def
2503 || (gimple_code (def_stmt
) == GIMPLE_PHI
2504 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2505 == vect_internal_def
2506 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
2508 if (dump_enabled_p ())
2510 dump_printf_loc (MSG_NOTE
, vect_location
, "swapping oprnds: ");
2511 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, next_stmt
, 0);
2512 dump_printf (MSG_NOTE
, "\n");
2515 swap_ssa_operands (next_stmt
,
2516 gimple_assign_rhs1_ptr (next_stmt
),
2517 gimple_assign_rhs2_ptr (next_stmt
));
2518 update_stmt (next_stmt
);
2520 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (next_stmt
)))
2521 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
2527 lhs
= gimple_assign_lhs (next_stmt
);
2528 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
2531 /* Save the chain for further analysis in SLP detection. */
2532 first
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
2533 LOOP_VINFO_REDUCTION_CHAINS (loop_info
).safe_push (first
);
2534 GROUP_SIZE (vinfo_for_stmt (first
)) = size
;
2540 /* Function vect_is_simple_reduction_1
2542 (1) Detect a cross-iteration def-use cycle that represents a simple
2543 reduction computation. We look for the following pattern:
2548 a2 = operation (a3, a1)
2555 a2 = operation (a3, a1)
2558 1. operation is commutative and associative and it is safe to
2559 change the order of the computation (if CHECK_REDUCTION is true)
2560 2. no uses for a2 in the loop (a2 is used out of the loop)
2561 3. no uses of a1 in the loop besides the reduction operation
2562 4. no uses of a1 outside the loop.
2564 Conditions 1,4 are tested here.
2565 Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
2567 (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
2568 nested cycles, if CHECK_REDUCTION is false.
2570 (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
2574 inner loop (def of a3)
2577 (4) Detect condition expressions, ie:
2578 for (int i = 0; i < N; i++)
2585 vect_is_simple_reduction (loop_vec_info loop_info
, gimple
*phi
,
2586 bool check_reduction
, bool *double_reduc
,
2587 bool need_wrapping_integral_overflow
,
2588 enum vect_reduction_type
*v_reduc_type
)
2590 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
2591 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
2592 edge latch_e
= loop_latch_edge (loop
);
2593 tree loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
2594 gimple
*def_stmt
, *def1
= NULL
, *def2
= NULL
, *phi_use_stmt
= NULL
;
2595 enum tree_code orig_code
, code
;
2596 tree op1
, op2
, op3
= NULL_TREE
, op4
= NULL_TREE
;
2600 imm_use_iterator imm_iter
;
2601 use_operand_p use_p
;
2604 *double_reduc
= false;
2605 *v_reduc_type
= TREE_CODE_REDUCTION
;
2607 /* If CHECK_REDUCTION is true, we assume inner-most loop vectorization,
2608 otherwise, we assume outer loop vectorization. */
2609 gcc_assert ((check_reduction
&& loop
== vect_loop
)
2610 || (!check_reduction
&& flow_loop_nested_p (vect_loop
, loop
)));
2612 name
= PHI_RESULT (phi
);
2613 /* ??? If there are no uses of the PHI result the inner loop reduction
2614 won't be detected as possibly double-reduction by vectorizable_reduction
2615 because that tries to walk the PHI arg from the preheader edge which
2616 can be constant. See PR60382. */
2617 if (has_zero_uses (name
))
2620 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2622 gimple
*use_stmt
= USE_STMT (use_p
);
2623 if (is_gimple_debug (use_stmt
))
2626 if (!flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2628 if (dump_enabled_p ())
2629 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2630 "intermediate value used outside loop.\n");
2638 if (dump_enabled_p ())
2639 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2640 "reduction used in loop.\n");
2644 phi_use_stmt
= use_stmt
;
2647 if (TREE_CODE (loop_arg
) != SSA_NAME
)
2649 if (dump_enabled_p ())
2651 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2652 "reduction: not ssa_name: ");
2653 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, loop_arg
);
2654 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
2659 def_stmt
= SSA_NAME_DEF_STMT (loop_arg
);
2662 if (dump_enabled_p ())
2663 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2664 "reduction: no def_stmt.\n");
2668 if (!is_gimple_assign (def_stmt
) && gimple_code (def_stmt
) != GIMPLE_PHI
)
2670 if (dump_enabled_p ())
2672 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, def_stmt
, 0);
2673 dump_printf (MSG_NOTE
, "\n");
2678 if (is_gimple_assign (def_stmt
))
2680 name
= gimple_assign_lhs (def_stmt
);
2685 name
= PHI_RESULT (def_stmt
);
2690 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2692 gimple
*use_stmt
= USE_STMT (use_p
);
2693 if (is_gimple_debug (use_stmt
))
2695 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2699 if (dump_enabled_p ())
2700 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2701 "reduction used in loop.\n");
2706 /* If DEF_STMT is a phi node itself, we expect it to have a single argument
2707 defined in the inner loop. */
2710 op1
= PHI_ARG_DEF (def_stmt
, 0);
2712 if (gimple_phi_num_args (def_stmt
) != 1
2713 || TREE_CODE (op1
) != SSA_NAME
)
2715 if (dump_enabled_p ())
2716 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2717 "unsupported phi node definition.\n");
2722 def1
= SSA_NAME_DEF_STMT (op1
);
2723 if (gimple_bb (def1
)
2724 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2726 && flow_bb_inside_loop_p (loop
->inner
, gimple_bb (def1
))
2727 && is_gimple_assign (def1
)
2728 && flow_bb_inside_loop_p (loop
->inner
, gimple_bb (phi_use_stmt
)))
2730 if (dump_enabled_p ())
2731 report_vect_op (MSG_NOTE
, def_stmt
,
2732 "detected double reduction: ");
2734 *double_reduc
= true;
2741 code
= orig_code
= gimple_assign_rhs_code (def_stmt
);
2743 /* We can handle "res -= x[i]", which is non-associative by
2744 simply rewriting this into "res += -x[i]". Avoid changing
2745 gimple instruction for the first simple tests and only do this
2746 if we're allowed to change code at all. */
2747 if (code
== MINUS_EXPR
2748 && (op1
= gimple_assign_rhs1 (def_stmt
))
2749 && TREE_CODE (op1
) == SSA_NAME
2750 && SSA_NAME_DEF_STMT (op1
) == phi
)
2753 if (code
== COND_EXPR
)
2755 if (check_reduction
)
2756 *v_reduc_type
= COND_REDUCTION
;
2758 else if (!commutative_tree_code (code
) || !associative_tree_code (code
))
2760 if (dump_enabled_p ())
2761 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2762 "reduction: not commutative/associative: ");
2766 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
2768 if (code
!= COND_EXPR
)
2770 if (dump_enabled_p ())
2771 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2772 "reduction: not binary operation: ");
2777 op3
= gimple_assign_rhs1 (def_stmt
);
2778 if (COMPARISON_CLASS_P (op3
))
2780 op4
= TREE_OPERAND (op3
, 1);
2781 op3
= TREE_OPERAND (op3
, 0);
2784 op1
= gimple_assign_rhs2 (def_stmt
);
2785 op2
= gimple_assign_rhs3 (def_stmt
);
2787 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2789 if (dump_enabled_p ())
2790 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2791 "reduction: uses not ssa_names: ");
2798 op1
= gimple_assign_rhs1 (def_stmt
);
2799 op2
= gimple_assign_rhs2 (def_stmt
);
2801 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2803 if (dump_enabled_p ())
2804 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2805 "reduction: uses not ssa_names: ");
2811 type
= TREE_TYPE (gimple_assign_lhs (def_stmt
));
2812 if ((TREE_CODE (op1
) == SSA_NAME
2813 && !types_compatible_p (type
,TREE_TYPE (op1
)))
2814 || (TREE_CODE (op2
) == SSA_NAME
2815 && !types_compatible_p (type
, TREE_TYPE (op2
)))
2816 || (op3
&& TREE_CODE (op3
) == SSA_NAME
2817 && !types_compatible_p (type
, TREE_TYPE (op3
)))
2818 || (op4
&& TREE_CODE (op4
) == SSA_NAME
2819 && !types_compatible_p (type
, TREE_TYPE (op4
))))
2821 if (dump_enabled_p ())
2823 dump_printf_loc (MSG_NOTE
, vect_location
,
2824 "reduction: multiple types: operation type: ");
2825 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, type
);
2826 dump_printf (MSG_NOTE
, ", operands types: ");
2827 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2829 dump_printf (MSG_NOTE
, ",");
2830 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2834 dump_printf (MSG_NOTE
, ",");
2835 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2841 dump_printf (MSG_NOTE
, ",");
2842 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2845 dump_printf (MSG_NOTE
, "\n");
2851 /* Check that it's ok to change the order of the computation.
2852 Generally, when vectorizing a reduction we change the order of the
2853 computation. This may change the behavior of the program in some
2854 cases, so we need to check that this is ok. One exception is when
2855 vectorizing an outer-loop: the inner-loop is executed sequentially,
2856 and therefore vectorizing reductions in the inner-loop during
2857 outer-loop vectorization is safe. */
2859 if (*v_reduc_type
!= COND_REDUCTION
2862 /* CHECKME: check for !flag_finite_math_only too? */
2863 if (SCALAR_FLOAT_TYPE_P (type
) && !flag_associative_math
)
2865 /* Changing the order of operations changes the semantics. */
2866 if (dump_enabled_p ())
2867 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2868 "reduction: unsafe fp math optimization: ");
2871 else if (INTEGRAL_TYPE_P (type
))
2873 if (!operation_no_trapping_overflow (type
, code
))
2875 /* Changing the order of operations changes the semantics. */
2876 if (dump_enabled_p ())
2877 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2878 "reduction: unsafe int math optimization"
2879 " (overflow traps): ");
2882 if (need_wrapping_integral_overflow
2883 && !TYPE_OVERFLOW_WRAPS (type
)
2884 && operation_can_overflow (code
))
2886 /* Changing the order of operations changes the semantics. */
2887 if (dump_enabled_p ())
2888 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2889 "reduction: unsafe int math optimization"
2890 " (overflow doesn't wrap): ");
2894 else if (SAT_FIXED_POINT_TYPE_P (type
))
2896 /* Changing the order of operations changes the semantics. */
2897 if (dump_enabled_p ())
2898 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2899 "reduction: unsafe fixed-point math optimization: ");
2904 /* Reduction is safe. We're dealing with one of the following:
2905 1) integer arithmetic and no trapv
2906 2) floating point arithmetic, and special flags permit this optimization
2907 3) nested cycle (i.e., outer loop vectorization). */
2908 if (TREE_CODE (op1
) == SSA_NAME
)
2909 def1
= SSA_NAME_DEF_STMT (op1
);
2911 if (TREE_CODE (op2
) == SSA_NAME
)
2912 def2
= SSA_NAME_DEF_STMT (op2
);
2914 if (code
!= COND_EXPR
2915 && ((!def1
|| gimple_nop_p (def1
)) && (!def2
|| gimple_nop_p (def2
))))
2917 if (dump_enabled_p ())
2918 report_vect_op (MSG_NOTE
, def_stmt
, "reduction: no defs for operands: ");
2922 /* Check that one def is the reduction def, defined by PHI,
2923 the other def is either defined in the loop ("vect_internal_def"),
2924 or it's an induction (defined by a loop-header phi-node). */
2926 if (def2
&& def2
== phi
2927 && (code
== COND_EXPR
2928 || !def1
|| gimple_nop_p (def1
)
2929 || !flow_bb_inside_loop_p (loop
, gimple_bb (def1
))
2930 || (def1
&& flow_bb_inside_loop_p (loop
, gimple_bb (def1
))
2931 && (is_gimple_assign (def1
)
2932 || is_gimple_call (def1
)
2933 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
2934 == vect_induction_def
2935 || (gimple_code (def1
) == GIMPLE_PHI
2936 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
2937 == vect_internal_def
2938 && !is_loop_header_bb_p (gimple_bb (def1
)))))))
2940 if (dump_enabled_p ())
2941 report_vect_op (MSG_NOTE
, def_stmt
, "detected reduction: ");
2945 if (def1
&& def1
== phi
2946 && (code
== COND_EXPR
2947 || !def2
|| gimple_nop_p (def2
)
2948 || !flow_bb_inside_loop_p (loop
, gimple_bb (def2
))
2949 || (def2
&& flow_bb_inside_loop_p (loop
, gimple_bb (def2
))
2950 && (is_gimple_assign (def2
)
2951 || is_gimple_call (def2
)
2952 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
2953 == vect_induction_def
2954 || (gimple_code (def2
) == GIMPLE_PHI
2955 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
2956 == vect_internal_def
2957 && !is_loop_header_bb_p (gimple_bb (def2
)))))))
2960 && orig_code
!= MINUS_EXPR
)
2962 if (code
== COND_EXPR
)
2964 /* No current known use where this case would be useful. */
2965 if (dump_enabled_p ())
2966 report_vect_op (MSG_NOTE
, def_stmt
,
2967 "detected reduction: cannot currently swap "
2968 "operands for cond_expr");
2972 /* Swap operands (just for simplicity - so that the rest of the code
2973 can assume that the reduction variable is always the last (second)
2975 if (dump_enabled_p ())
2976 report_vect_op (MSG_NOTE
, def_stmt
,
2977 "detected reduction: need to swap operands: ");
2979 swap_ssa_operands (def_stmt
, gimple_assign_rhs1_ptr (def_stmt
),
2980 gimple_assign_rhs2_ptr (def_stmt
));
2982 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (def_stmt
)))
2983 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
2987 if (dump_enabled_p ())
2988 report_vect_op (MSG_NOTE
, def_stmt
, "detected reduction: ");
2994 /* Try to find SLP reduction chain. */
2995 if (check_reduction
&& code
!= COND_EXPR
2996 && vect_is_slp_reduction (loop_info
, phi
, def_stmt
))
2998 if (dump_enabled_p ())
2999 report_vect_op (MSG_NOTE
, def_stmt
,
3000 "reduction: detected reduction chain: ");
3005 if (dump_enabled_p ())
3006 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
3007 "reduction: unknown pattern: ");
3012 /* Wrapper around vect_is_simple_reduction_1, which will modify code
3013 in-place if it enables detection of more reductions. Arguments
3017 vect_force_simple_reduction (loop_vec_info loop_info
, gimple
*phi
,
3018 bool check_reduction
, bool *double_reduc
,
3019 bool need_wrapping_integral_overflow
)
3021 enum vect_reduction_type v_reduc_type
;
3022 return vect_is_simple_reduction (loop_info
, phi
, check_reduction
,
3024 need_wrapping_integral_overflow
,
3028 /* Calculate cost of peeling the loop PEEL_ITERS_PROLOGUE times. */
3030 vect_get_known_peeling_cost (loop_vec_info loop_vinfo
, int peel_iters_prologue
,
3031 int *peel_iters_epilogue
,
3032 stmt_vector_for_cost
*scalar_cost_vec
,
3033 stmt_vector_for_cost
*prologue_cost_vec
,
3034 stmt_vector_for_cost
*epilogue_cost_vec
)
3037 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3039 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
3041 *peel_iters_epilogue
= vf
/2;
3042 if (dump_enabled_p ())
3043 dump_printf_loc (MSG_NOTE
, vect_location
,
3044 "cost model: epilogue peel iters set to vf/2 "
3045 "because loop iterations are unknown .\n");
3047 /* If peeled iterations are known but number of scalar loop
3048 iterations are unknown, count a taken branch per peeled loop. */
3049 retval
= record_stmt_cost (prologue_cost_vec
, 1, cond_branch_taken
,
3050 NULL
, 0, vect_prologue
);
3051 retval
= record_stmt_cost (prologue_cost_vec
, 1, cond_branch_taken
,
3052 NULL
, 0, vect_epilogue
);
3056 int niters
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
3057 peel_iters_prologue
= niters
< peel_iters_prologue
?
3058 niters
: peel_iters_prologue
;
3059 *peel_iters_epilogue
= (niters
- peel_iters_prologue
) % vf
;
3060 /* If we need to peel for gaps, but no peeling is required, we have to
3061 peel VF iterations. */
3062 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) && !*peel_iters_epilogue
)
3063 *peel_iters_epilogue
= vf
;
3066 stmt_info_for_cost
*si
;
3068 if (peel_iters_prologue
)
3069 FOR_EACH_VEC_ELT (*scalar_cost_vec
, j
, si
)
3070 retval
+= record_stmt_cost (prologue_cost_vec
,
3071 si
->count
* peel_iters_prologue
,
3072 si
->kind
, NULL
, si
->misalign
,
3074 if (*peel_iters_epilogue
)
3075 FOR_EACH_VEC_ELT (*scalar_cost_vec
, j
, si
)
3076 retval
+= record_stmt_cost (epilogue_cost_vec
,
3077 si
->count
* *peel_iters_epilogue
,
3078 si
->kind
, NULL
, si
->misalign
,
3084 /* Function vect_estimate_min_profitable_iters
3086 Return the number of iterations required for the vector version of the
3087 loop to be profitable relative to the cost of the scalar version of the
3091 vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo
,
3092 int *ret_min_profitable_niters
,
3093 int *ret_min_profitable_estimate
)
3095 int min_profitable_iters
;
3096 int min_profitable_estimate
;
3097 int peel_iters_prologue
;
3098 int peel_iters_epilogue
;
3099 unsigned vec_inside_cost
= 0;
3100 int vec_outside_cost
= 0;
3101 unsigned vec_prologue_cost
= 0;
3102 unsigned vec_epilogue_cost
= 0;
3103 int scalar_single_iter_cost
= 0;
3104 int scalar_outside_cost
= 0;
3105 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3106 int npeel
= LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
);
3107 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3109 /* Cost model disabled. */
3110 if (unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo
)))
3112 dump_printf_loc (MSG_NOTE
, vect_location
, "cost model disabled.\n");
3113 *ret_min_profitable_niters
= 0;
3114 *ret_min_profitable_estimate
= 0;
3118 /* Requires loop versioning tests to handle misalignment. */
3119 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
))
3121 /* FIXME: Make cost depend on complexity of individual check. */
3122 unsigned len
= LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).length ();
3123 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
3125 dump_printf (MSG_NOTE
,
3126 "cost model: Adding cost of checks for loop "
3127 "versioning to treat misalignment.\n");
3130 /* Requires loop versioning with alias checks. */
3131 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
3133 /* FIXME: Make cost depend on complexity of individual check. */
3134 unsigned len
= LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo
).length ();
3135 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
3137 dump_printf (MSG_NOTE
,
3138 "cost model: Adding cost of checks for loop "
3139 "versioning aliasing.\n");
3142 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
3143 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
3144 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_taken
, NULL
, 0,
3147 /* Count statements in scalar loop. Using this as scalar cost for a single
3150 TODO: Add outer loop support.
3152 TODO: Consider assigning different costs to different scalar
3155 scalar_single_iter_cost
3156 = LOOP_VINFO_SINGLE_SCALAR_ITERATION_COST (loop_vinfo
);
3158 /* Add additional cost for the peeled instructions in prologue and epilogue
3161 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
3162 at compile-time - we assume it's vf/2 (the worst would be vf-1).
3164 TODO: Build an expression that represents peel_iters for prologue and
3165 epilogue to be used in a run-time test. */
3169 peel_iters_prologue
= vf
/2;
3170 dump_printf (MSG_NOTE
, "cost model: "
3171 "prologue peel iters set to vf/2.\n");
3173 /* If peeling for alignment is unknown, loop bound of main loop becomes
3175 peel_iters_epilogue
= vf
/2;
3176 dump_printf (MSG_NOTE
, "cost model: "
3177 "epilogue peel iters set to vf/2 because "
3178 "peeling for alignment is unknown.\n");
3180 /* If peeled iterations are unknown, count a taken branch and a not taken
3181 branch per peeled loop. Even if scalar loop iterations are known,
3182 vector iterations are not known since peeled prologue iterations are
3183 not known. Hence guards remain the same. */
3184 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_taken
,
3185 NULL
, 0, vect_prologue
);
3186 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_not_taken
,
3187 NULL
, 0, vect_prologue
);
3188 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_taken
,
3189 NULL
, 0, vect_epilogue
);
3190 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_not_taken
,
3191 NULL
, 0, vect_epilogue
);
3192 stmt_info_for_cost
*si
;
3194 FOR_EACH_VEC_ELT (LOOP_VINFO_SCALAR_ITERATION_COST (loop_vinfo
), j
, si
)
3196 struct _stmt_vec_info
*stmt_info
3197 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
3198 (void) add_stmt_cost (target_cost_data
,
3199 si
->count
* peel_iters_prologue
,
3200 si
->kind
, stmt_info
, si
->misalign
,
3202 (void) add_stmt_cost (target_cost_data
,
3203 si
->count
* peel_iters_epilogue
,
3204 si
->kind
, stmt_info
, si
->misalign
,
3210 stmt_vector_for_cost prologue_cost_vec
, epilogue_cost_vec
;
3211 stmt_info_for_cost
*si
;
3213 void *data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3215 prologue_cost_vec
.create (2);
3216 epilogue_cost_vec
.create (2);
3217 peel_iters_prologue
= npeel
;
3219 (void) vect_get_known_peeling_cost (loop_vinfo
, peel_iters_prologue
,
3220 &peel_iters_epilogue
,
3221 &LOOP_VINFO_SCALAR_ITERATION_COST
3224 &epilogue_cost_vec
);
3226 FOR_EACH_VEC_ELT (prologue_cost_vec
, j
, si
)
3228 struct _stmt_vec_info
*stmt_info
3229 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
3230 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
3231 si
->misalign
, vect_prologue
);
3234 FOR_EACH_VEC_ELT (epilogue_cost_vec
, j
, si
)
3236 struct _stmt_vec_info
*stmt_info
3237 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
3238 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
3239 si
->misalign
, vect_epilogue
);
3242 prologue_cost_vec
.release ();
3243 epilogue_cost_vec
.release ();
3246 /* FORNOW: The scalar outside cost is incremented in one of the
3249 1. The vectorizer checks for alignment and aliasing and generates
3250 a condition that allows dynamic vectorization. A cost model
3251 check is ANDED with the versioning condition. Hence scalar code
3252 path now has the added cost of the versioning check.
3254 if (cost > th & versioning_check)
3257 Hence run-time scalar is incremented by not-taken branch cost.
3259 2. The vectorizer then checks if a prologue is required. If the
3260 cost model check was not done before during versioning, it has to
3261 be done before the prologue check.
3264 prologue = scalar_iters
3269 if (prologue == num_iters)
3272 Hence the run-time scalar cost is incremented by a taken branch,
3273 plus a not-taken branch, plus a taken branch cost.
3275 3. The vectorizer then checks if an epilogue is required. If the
3276 cost model check was not done before during prologue check, it
3277 has to be done with the epilogue check.
3283 if (prologue == num_iters)
3286 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
3289 Hence the run-time scalar cost should be incremented by 2 taken
3292 TODO: The back end may reorder the BBS's differently and reverse
3293 conditions/branch directions. Change the estimates below to
3294 something more reasonable. */
3296 /* If the number of iterations is known and we do not do versioning, we can
3297 decide whether to vectorize at compile time. Hence the scalar version
3298 do not carry cost model guard costs. */
3299 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
3300 || LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
3301 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
3303 /* Cost model check occurs at versioning. */
3304 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
3305 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
3306 scalar_outside_cost
+= vect_get_stmt_cost (cond_branch_not_taken
);
3309 /* Cost model check occurs at prologue generation. */
3310 if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
) < 0)
3311 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
)
3312 + vect_get_stmt_cost (cond_branch_not_taken
);
3313 /* Cost model check occurs at epilogue generation. */
3315 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
);
3319 /* Complete the target-specific cost calculations. */
3320 finish_cost (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
), &vec_prologue_cost
,
3321 &vec_inside_cost
, &vec_epilogue_cost
);
3323 vec_outside_cost
= (int)(vec_prologue_cost
+ vec_epilogue_cost
);
3325 if (dump_enabled_p ())
3327 dump_printf_loc (MSG_NOTE
, vect_location
, "Cost model analysis: \n");
3328 dump_printf (MSG_NOTE
, " Vector inside of loop cost: %d\n",
3330 dump_printf (MSG_NOTE
, " Vector prologue cost: %d\n",
3332 dump_printf (MSG_NOTE
, " Vector epilogue cost: %d\n",
3334 dump_printf (MSG_NOTE
, " Scalar iteration cost: %d\n",
3335 scalar_single_iter_cost
);
3336 dump_printf (MSG_NOTE
, " Scalar outside cost: %d\n",
3337 scalar_outside_cost
);
3338 dump_printf (MSG_NOTE
, " Vector outside cost: %d\n",
3340 dump_printf (MSG_NOTE
, " prologue iterations: %d\n",
3341 peel_iters_prologue
);
3342 dump_printf (MSG_NOTE
, " epilogue iterations: %d\n",
3343 peel_iters_epilogue
);
3346 /* Calculate number of iterations required to make the vector version
3347 profitable, relative to the loop bodies only. The following condition
3349 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
3351 SIC = scalar iteration cost, VIC = vector iteration cost,
3352 VOC = vector outside cost, VF = vectorization factor,
3353 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
3354 SOC = scalar outside cost for run time cost model check. */
3356 if ((scalar_single_iter_cost
* vf
) > (int) vec_inside_cost
)
3358 if (vec_outside_cost
<= 0)
3359 min_profitable_iters
= 1;
3362 min_profitable_iters
= ((vec_outside_cost
- scalar_outside_cost
) * vf
3363 - vec_inside_cost
* peel_iters_prologue
3364 - vec_inside_cost
* peel_iters_epilogue
)
3365 / ((scalar_single_iter_cost
* vf
)
3368 if ((scalar_single_iter_cost
* vf
* min_profitable_iters
)
3369 <= (((int) vec_inside_cost
* min_profitable_iters
)
3370 + (((int) vec_outside_cost
- scalar_outside_cost
) * vf
)))
3371 min_profitable_iters
++;
3374 /* vector version will never be profitable. */
3377 if (LOOP_VINFO_LOOP (loop_vinfo
)->force_vectorize
)
3378 warning_at (vect_location
, OPT_Wopenmp_simd
, "vectorization "
3379 "did not happen for a simd loop");
3381 if (dump_enabled_p ())
3382 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3383 "cost model: the vector iteration cost = %d "
3384 "divided by the scalar iteration cost = %d "
3385 "is greater or equal to the vectorization factor = %d"
3387 vec_inside_cost
, scalar_single_iter_cost
, vf
);
3388 *ret_min_profitable_niters
= -1;
3389 *ret_min_profitable_estimate
= -1;
3393 dump_printf (MSG_NOTE
,
3394 " Calculated minimum iters for profitability: %d\n",
3395 min_profitable_iters
);
3397 min_profitable_iters
=
3398 min_profitable_iters
< vf
? vf
: min_profitable_iters
;
3400 /* Because the condition we create is:
3401 if (niters <= min_profitable_iters)
3402 then skip the vectorized loop. */
3403 min_profitable_iters
--;
3405 if (dump_enabled_p ())
3406 dump_printf_loc (MSG_NOTE
, vect_location
,
3407 " Runtime profitability threshold = %d\n",
3408 min_profitable_iters
);
3410 *ret_min_profitable_niters
= min_profitable_iters
;
3412 /* Calculate number of iterations required to make the vector version
3413 profitable, relative to the loop bodies only.
3415 Non-vectorized variant is SIC * niters and it must win over vector
3416 variant on the expected loop trip count. The following condition must hold true:
3417 SIC * niters > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC + SOC */
3419 if (vec_outside_cost
<= 0)
3420 min_profitable_estimate
= 1;
3423 min_profitable_estimate
= ((vec_outside_cost
+ scalar_outside_cost
) * vf
3424 - vec_inside_cost
* peel_iters_prologue
3425 - vec_inside_cost
* peel_iters_epilogue
)
3426 / ((scalar_single_iter_cost
* vf
)
3429 min_profitable_estimate
--;
3430 min_profitable_estimate
= MAX (min_profitable_estimate
, min_profitable_iters
);
3431 if (dump_enabled_p ())
3432 dump_printf_loc (MSG_NOTE
, vect_location
,
3433 " Static estimate profitability threshold = %d\n",
3434 min_profitable_estimate
);
3436 *ret_min_profitable_estimate
= min_profitable_estimate
;
3439 /* Writes into SEL a mask for a vec_perm, equivalent to a vec_shr by OFFSET
3440 vector elements (not bits) for a vector of mode MODE. */
3442 calc_vec_perm_mask_for_shift (enum machine_mode mode
, unsigned int offset
,
3445 unsigned int i
, nelt
= GET_MODE_NUNITS (mode
);
3447 for (i
= 0; i
< nelt
; i
++)
3448 sel
[i
] = (i
+ offset
) & (2*nelt
- 1);
3451 /* Checks whether the target supports whole-vector shifts for vectors of mode
3452 MODE. This is the case if _either_ the platform handles vec_shr_optab, _or_
3453 it supports vec_perm_const with masks for all necessary shift amounts. */
3455 have_whole_vector_shift (enum machine_mode mode
)
3457 if (optab_handler (vec_shr_optab
, mode
) != CODE_FOR_nothing
)
3460 if (direct_optab_handler (vec_perm_const_optab
, mode
) == CODE_FOR_nothing
)
3463 unsigned int i
, nelt
= GET_MODE_NUNITS (mode
);
3464 unsigned char *sel
= XALLOCAVEC (unsigned char, nelt
);
3466 for (i
= nelt
/2; i
>= 1; i
/=2)
3468 calc_vec_perm_mask_for_shift (mode
, i
, sel
);
3469 if (!can_vec_perm_p (mode
, false, sel
))
3475 /* Return the reduction operand (with index REDUC_INDEX) of STMT. */
3478 get_reduction_op (gimple
*stmt
, int reduc_index
)
3480 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3482 case GIMPLE_SINGLE_RHS
:
3483 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
))
3485 return TREE_OPERAND (gimple_assign_rhs1 (stmt
), reduc_index
);
3486 case GIMPLE_UNARY_RHS
:
3487 return gimple_assign_rhs1 (stmt
);
3488 case GIMPLE_BINARY_RHS
:
3490 ? gimple_assign_rhs2 (stmt
) : gimple_assign_rhs1 (stmt
));
3491 case GIMPLE_TERNARY_RHS
:
3492 return gimple_op (stmt
, reduc_index
+ 1);
3498 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
3499 functions. Design better to avoid maintenance issues. */
3501 /* Function vect_model_reduction_cost.
3503 Models cost for a reduction operation, including the vector ops
3504 generated within the strip-mine loop, the initial definition before
3505 the loop, and the epilogue code that must be generated. */
3508 vect_model_reduction_cost (stmt_vec_info stmt_info
, enum tree_code reduc_code
,
3509 int ncopies
, int reduc_index
)
3511 int prologue_cost
= 0, epilogue_cost
= 0;
3512 enum tree_code code
;
3515 gimple
*stmt
, *orig_stmt
;
3518 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3519 struct loop
*loop
= NULL
;
3520 void *target_cost_data
;
3524 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3525 target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3528 target_cost_data
= BB_VINFO_TARGET_COST_DATA (STMT_VINFO_BB_VINFO (stmt_info
));
3530 /* Condition reductions generate two reductions in the loop. */
3531 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
)
3534 /* Cost of reduction op inside loop. */
3535 unsigned inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
3536 stmt_info
, 0, vect_body
);
3537 stmt
= STMT_VINFO_STMT (stmt_info
);
3539 reduction_op
= get_reduction_op (stmt
, reduc_index
);
3541 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
3544 if (dump_enabled_p ())
3546 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3547 "unsupported data-type ");
3548 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
3549 TREE_TYPE (reduction_op
));
3550 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3555 mode
= TYPE_MODE (vectype
);
3556 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
3559 orig_stmt
= STMT_VINFO_STMT (stmt_info
);
3561 code
= gimple_assign_rhs_code (orig_stmt
);
3563 /* Add in cost for initial definition.
3564 For cond reduction we have four vectors: initial index, step, initial
3565 result of the data reduction, initial value of the index reduction. */
3566 int prologue_stmts
= STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
3567 == COND_REDUCTION
? 4 : 1;
3568 prologue_cost
+= add_stmt_cost (target_cost_data
, prologue_stmts
,
3569 scalar_to_vec
, stmt_info
, 0,
3572 /* Determine cost of epilogue code.
3574 We have a reduction operator that will reduce the vector in one statement.
3575 Also requires scalar extract. */
3577 if (!loop
|| !nested_in_vect_loop_p (loop
, orig_stmt
))
3579 if (reduc_code
!= ERROR_MARK
)
3581 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
)
3583 /* An EQ stmt and an COND_EXPR stmt. */
3584 epilogue_cost
+= add_stmt_cost (target_cost_data
, 2,
3585 vector_stmt
, stmt_info
, 0,
3587 /* Reduction of the max index and a reduction of the found
3589 epilogue_cost
+= add_stmt_cost (target_cost_data
, 2,
3590 vec_to_scalar
, stmt_info
, 0,
3592 /* A broadcast of the max value. */
3593 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1,
3594 scalar_to_vec
, stmt_info
, 0,
3599 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1, vector_stmt
,
3600 stmt_info
, 0, vect_epilogue
);
3601 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1,
3602 vec_to_scalar
, stmt_info
, 0,
3608 int vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
3610 TYPE_SIZE (TREE_TYPE (gimple_assign_lhs (orig_stmt
)));
3611 int element_bitsize
= tree_to_uhwi (bitsize
);
3612 int nelements
= vec_size_in_bits
/ element_bitsize
;
3614 optab
= optab_for_tree_code (code
, vectype
, optab_default
);
3616 /* We have a whole vector shift available. */
3617 if (VECTOR_MODE_P (mode
)
3618 && optab_handler (optab
, mode
) != CODE_FOR_nothing
3619 && have_whole_vector_shift (mode
))
3621 /* Final reduction via vector shifts and the reduction operator.
3622 Also requires scalar extract. */
3623 epilogue_cost
+= add_stmt_cost (target_cost_data
,
3624 exact_log2 (nelements
) * 2,
3625 vector_stmt
, stmt_info
, 0,
3627 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1,
3628 vec_to_scalar
, stmt_info
, 0,
3632 /* Use extracts and reduction op for final reduction. For N
3633 elements, we have N extracts and N-1 reduction ops. */
3634 epilogue_cost
+= add_stmt_cost (target_cost_data
,
3635 nelements
+ nelements
- 1,
3636 vector_stmt
, stmt_info
, 0,
3641 if (dump_enabled_p ())
3642 dump_printf (MSG_NOTE
,
3643 "vect_model_reduction_cost: inside_cost = %d, "
3644 "prologue_cost = %d, epilogue_cost = %d .\n", inside_cost
,
3645 prologue_cost
, epilogue_cost
);
3651 /* Function vect_model_induction_cost.
3653 Models cost for induction operations. */
3656 vect_model_induction_cost (stmt_vec_info stmt_info
, int ncopies
)
3658 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3659 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3660 unsigned inside_cost
, prologue_cost
;
3662 /* loop cost for vec_loop. */
3663 inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
3664 stmt_info
, 0, vect_body
);
3666 /* prologue cost for vec_init and vec_step. */
3667 prologue_cost
= add_stmt_cost (target_cost_data
, 2, scalar_to_vec
,
3668 stmt_info
, 0, vect_prologue
);
3670 if (dump_enabled_p ())
3671 dump_printf_loc (MSG_NOTE
, vect_location
,
3672 "vect_model_induction_cost: inside_cost = %d, "
3673 "prologue_cost = %d .\n", inside_cost
, prologue_cost
);
3677 /* Function get_initial_def_for_induction
3680 STMT - a stmt that performs an induction operation in the loop.
3681 IV_PHI - the initial value of the induction variable
3684 Return a vector variable, initialized with the first VF values of
3685 the induction variable. E.g., for an iv with IV_PHI='X' and
3686 evolution S, for a vector of 4 units, we want to return:
3687 [X, X + S, X + 2*S, X + 3*S]. */
3690 get_initial_def_for_induction (gimple
*iv_phi
)
3692 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (iv_phi
);
3693 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
3694 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3697 edge pe
= loop_preheader_edge (loop
);
3698 struct loop
*iv_loop
;
3700 tree new_vec
, vec_init
, vec_step
, t
;
3703 gphi
*induction_phi
;
3704 tree induc_def
, vec_def
, vec_dest
;
3705 tree init_expr
, step_expr
;
3706 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3710 stmt_vec_info phi_info
= vinfo_for_stmt (iv_phi
);
3711 bool nested_in_vect_loop
= false;
3713 imm_use_iterator imm_iter
;
3714 use_operand_p use_p
;
3718 gimple_stmt_iterator si
;
3719 basic_block bb
= gimple_bb (iv_phi
);
3723 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
3724 if (nested_in_vect_loop_p (loop
, iv_phi
))
3726 nested_in_vect_loop
= true;
3727 iv_loop
= loop
->inner
;
3731 gcc_assert (iv_loop
== (gimple_bb (iv_phi
))->loop_father
);
3733 latch_e
= loop_latch_edge (iv_loop
);
3734 loop_arg
= PHI_ARG_DEF_FROM_EDGE (iv_phi
, latch_e
);
3736 step_expr
= STMT_VINFO_LOOP_PHI_EVOLUTION_PART (phi_info
);
3737 gcc_assert (step_expr
!= NULL_TREE
);
3739 pe
= loop_preheader_edge (iv_loop
);
3740 init_expr
= PHI_ARG_DEF_FROM_EDGE (iv_phi
,
3741 loop_preheader_edge (iv_loop
));
3743 vectype
= get_vectype_for_scalar_type (TREE_TYPE (init_expr
));
3744 resvectype
= get_vectype_for_scalar_type (TREE_TYPE (PHI_RESULT (iv_phi
)));
3745 gcc_assert (vectype
);
3746 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3747 ncopies
= vf
/ nunits
;
3749 gcc_assert (phi_info
);
3750 gcc_assert (ncopies
>= 1);
3752 /* Convert the step to the desired type. */
3754 step_expr
= gimple_convert (&stmts
, TREE_TYPE (vectype
), step_expr
);
3757 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
3758 gcc_assert (!new_bb
);
3761 /* Find the first insertion point in the BB. */
3762 si
= gsi_after_labels (bb
);
3764 /* Create the vector that holds the initial_value of the induction. */
3765 if (nested_in_vect_loop
)
3767 /* iv_loop is nested in the loop to be vectorized. init_expr had already
3768 been created during vectorization of previous stmts. We obtain it
3769 from the STMT_VINFO_VEC_STMT of the defining stmt. */
3770 vec_init
= vect_get_vec_def_for_operand (init_expr
, iv_phi
);
3771 /* If the initial value is not of proper type, convert it. */
3772 if (!useless_type_conversion_p (vectype
, TREE_TYPE (vec_init
)))
3775 = gimple_build_assign (vect_get_new_ssa_name (vectype
,
3779 build1 (VIEW_CONVERT_EXPR
, vectype
,
3781 vec_init
= gimple_assign_lhs (new_stmt
);
3782 new_bb
= gsi_insert_on_edge_immediate (loop_preheader_edge (iv_loop
),
3784 gcc_assert (!new_bb
);
3785 set_vinfo_for_stmt (new_stmt
,
3786 new_stmt_vec_info (new_stmt
, loop_vinfo
));
3791 vec
<constructor_elt
, va_gc
> *v
;
3793 /* iv_loop is the loop to be vectorized. Create:
3794 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
3796 new_name
= gimple_convert (&stmts
, TREE_TYPE (vectype
), init_expr
);
3798 vec_alloc (v
, nunits
);
3799 bool constant_p
= is_gimple_min_invariant (new_name
);
3800 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
3801 for (i
= 1; i
< nunits
; i
++)
3803 /* Create: new_name_i = new_name + step_expr */
3804 new_name
= gimple_build (&stmts
, PLUS_EXPR
, TREE_TYPE (new_name
),
3805 new_name
, step_expr
);
3806 if (!is_gimple_min_invariant (new_name
))
3808 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
3812 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
3813 gcc_assert (!new_bb
);
3816 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
3818 new_vec
= build_vector_from_ctor (vectype
, v
);
3820 new_vec
= build_constructor (vectype
, v
);
3821 vec_init
= vect_init_vector (iv_phi
, new_vec
, vectype
, NULL
);
3825 /* Create the vector that holds the step of the induction. */
3826 if (nested_in_vect_loop
)
3827 /* iv_loop is nested in the loop to be vectorized. Generate:
3828 vec_step = [S, S, S, S] */
3829 new_name
= step_expr
;
3832 /* iv_loop is the loop to be vectorized. Generate:
3833 vec_step = [VF*S, VF*S, VF*S, VF*S] */
3834 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
)))
3836 expr
= build_int_cst (integer_type_node
, vf
);
3837 expr
= fold_convert (TREE_TYPE (step_expr
), expr
);
3840 expr
= build_int_cst (TREE_TYPE (step_expr
), vf
);
3841 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
3843 if (TREE_CODE (step_expr
) == SSA_NAME
)
3844 new_name
= vect_init_vector (iv_phi
, new_name
,
3845 TREE_TYPE (step_expr
), NULL
);
3848 t
= unshare_expr (new_name
);
3849 gcc_assert (CONSTANT_CLASS_P (new_name
)
3850 || TREE_CODE (new_name
) == SSA_NAME
);
3851 stepvectype
= get_vectype_for_scalar_type (TREE_TYPE (new_name
));
3852 gcc_assert (stepvectype
);
3853 new_vec
= build_vector_from_val (stepvectype
, t
);
3854 vec_step
= vect_init_vector (iv_phi
, new_vec
, stepvectype
, NULL
);
3857 /* Create the following def-use cycle:
3862 vec_iv = PHI <vec_init, vec_loop>
3866 vec_loop = vec_iv + vec_step; */
3868 /* Create the induction-phi that defines the induction-operand. */
3869 vec_dest
= vect_get_new_vect_var (vectype
, vect_simple_var
, "vec_iv_");
3870 induction_phi
= create_phi_node (vec_dest
, iv_loop
->header
);
3871 set_vinfo_for_stmt (induction_phi
,
3872 new_stmt_vec_info (induction_phi
, loop_vinfo
));
3873 induc_def
= PHI_RESULT (induction_phi
);
3875 /* Create the iv update inside the loop */
3876 new_stmt
= gimple_build_assign (vec_dest
, PLUS_EXPR
, induc_def
, vec_step
);
3877 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
3878 gimple_assign_set_lhs (new_stmt
, vec_def
);
3879 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3880 set_vinfo_for_stmt (new_stmt
, new_stmt_vec_info (new_stmt
, loop_vinfo
));
3882 /* Set the arguments of the phi node: */
3883 add_phi_arg (induction_phi
, vec_init
, pe
, UNKNOWN_LOCATION
);
3884 add_phi_arg (induction_phi
, vec_def
, loop_latch_edge (iv_loop
),
3888 /* In case that vectorization factor (VF) is bigger than the number
3889 of elements that we can fit in a vectype (nunits), we have to generate
3890 more than one vector stmt - i.e - we need to "unroll" the
3891 vector stmt by a factor VF/nunits. For more details see documentation
3892 in vectorizable_operation. */
3896 stmt_vec_info prev_stmt_vinfo
;
3897 /* FORNOW. This restriction should be relaxed. */
3898 gcc_assert (!nested_in_vect_loop
);
3900 /* Create the vector that holds the step of the induction. */
3901 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
)))
3903 expr
= build_int_cst (integer_type_node
, nunits
);
3904 expr
= fold_convert (TREE_TYPE (step_expr
), expr
);
3907 expr
= build_int_cst (TREE_TYPE (step_expr
), nunits
);
3908 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
3910 if (TREE_CODE (step_expr
) == SSA_NAME
)
3911 new_name
= vect_init_vector (iv_phi
, new_name
,
3912 TREE_TYPE (step_expr
), NULL
);
3913 t
= unshare_expr (new_name
);
3914 gcc_assert (CONSTANT_CLASS_P (new_name
)
3915 || TREE_CODE (new_name
) == SSA_NAME
);
3916 new_vec
= build_vector_from_val (stepvectype
, t
);
3917 vec_step
= vect_init_vector (iv_phi
, new_vec
, stepvectype
, NULL
);
3919 vec_def
= induc_def
;
3920 prev_stmt_vinfo
= vinfo_for_stmt (induction_phi
);
3921 for (i
= 1; i
< ncopies
; i
++)
3923 /* vec_i = vec_prev + vec_step */
3924 new_stmt
= gimple_build_assign (vec_dest
, PLUS_EXPR
,
3926 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
3927 gimple_assign_set_lhs (new_stmt
, vec_def
);
3929 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3930 if (!useless_type_conversion_p (resvectype
, vectype
))
3933 = gimple_build_assign
3934 (vect_get_new_vect_var (resvectype
, vect_simple_var
,
3937 build1 (VIEW_CONVERT_EXPR
, resvectype
,
3938 gimple_assign_lhs (new_stmt
)));
3939 gimple_assign_set_lhs (new_stmt
,
3941 (gimple_assign_lhs (new_stmt
), new_stmt
));
3942 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3944 set_vinfo_for_stmt (new_stmt
,
3945 new_stmt_vec_info (new_stmt
, loop_vinfo
));
3946 STMT_VINFO_RELATED_STMT (prev_stmt_vinfo
) = new_stmt
;
3947 prev_stmt_vinfo
= vinfo_for_stmt (new_stmt
);
3951 if (nested_in_vect_loop
)
3953 /* Find the loop-closed exit-phi of the induction, and record
3954 the final vector of induction results: */
3956 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
3958 gimple
*use_stmt
= USE_STMT (use_p
);
3959 if (is_gimple_debug (use_stmt
))
3962 if (!flow_bb_inside_loop_p (iv_loop
, gimple_bb (use_stmt
)))
3964 exit_phi
= use_stmt
;
3970 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (exit_phi
);
3971 /* FORNOW. Currently not supporting the case that an inner-loop induction
3972 is not used in the outer-loop (i.e. only outside the outer-loop). */
3973 gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo
)
3974 && !STMT_VINFO_LIVE_P (stmt_vinfo
));
3976 STMT_VINFO_VEC_STMT (stmt_vinfo
) = new_stmt
;
3977 if (dump_enabled_p ())
3979 dump_printf_loc (MSG_NOTE
, vect_location
,
3980 "vector of inductions after inner-loop:");
3981 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, new_stmt
, 0);
3982 dump_printf (MSG_NOTE
, "\n");
3988 if (dump_enabled_p ())
3990 dump_printf_loc (MSG_NOTE
, vect_location
,
3991 "transform induction: created def-use cycle: ");
3992 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, induction_phi
, 0);
3993 dump_printf (MSG_NOTE
, "\n");
3994 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
3995 SSA_NAME_DEF_STMT (vec_def
), 0);
3996 dump_printf (MSG_NOTE
, "\n");
3999 STMT_VINFO_VEC_STMT (phi_info
) = induction_phi
;
4000 if (!useless_type_conversion_p (resvectype
, vectype
))
4002 new_stmt
= gimple_build_assign (vect_get_new_vect_var (resvectype
,
4006 build1 (VIEW_CONVERT_EXPR
, resvectype
,
4008 induc_def
= make_ssa_name (gimple_assign_lhs (new_stmt
), new_stmt
);
4009 gimple_assign_set_lhs (new_stmt
, induc_def
);
4010 si
= gsi_after_labels (bb
);
4011 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
4012 set_vinfo_for_stmt (new_stmt
,
4013 new_stmt_vec_info (new_stmt
, loop_vinfo
));
4014 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_stmt
))
4015 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (induction_phi
));
4022 /* Function get_initial_def_for_reduction
4025 STMT - a stmt that performs a reduction operation in the loop.
4026 INIT_VAL - the initial value of the reduction variable
4029 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
4030 of the reduction (used for adjusting the epilog - see below).
4031 Return a vector variable, initialized according to the operation that STMT
4032 performs. This vector will be used as the initial value of the
4033 vector of partial results.
4035 Option1 (adjust in epilog): Initialize the vector as follows:
4036 add/bit or/xor: [0,0,...,0,0]
4037 mult/bit and: [1,1,...,1,1]
4038 min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
4039 and when necessary (e.g. add/mult case) let the caller know
4040 that it needs to adjust the result by init_val.
4042 Option2: Initialize the vector as follows:
4043 add/bit or/xor: [init_val,0,0,...,0]
4044 mult/bit and: [init_val,1,1,...,1]
4045 min/max/cond_expr: [init_val,init_val,...,init_val]
4046 and no adjustments are needed.
4048 For example, for the following code:
4054 STMT is 's = s + a[i]', and the reduction variable is 's'.
4055 For a vector of 4 units, we want to return either [0,0,0,init_val],
4056 or [0,0,0,0] and let the caller know that it needs to adjust
4057 the result at the end by 'init_val'.
4059 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
4060 initialization vector is simpler (same element in all entries), if
4061 ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
4063 A cost model should help decide between these two schemes. */
4066 get_initial_def_for_reduction (gimple
*stmt
, tree init_val
,
4067 tree
*adjustment_def
)
4069 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
4070 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
4071 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4072 tree scalar_type
= TREE_TYPE (init_val
);
4073 tree vectype
= get_vectype_for_scalar_type (scalar_type
);
4075 enum tree_code code
= gimple_assign_rhs_code (stmt
);
4080 bool nested_in_vect_loop
= false;
4081 REAL_VALUE_TYPE real_init_val
= dconst0
;
4082 int int_init_val
= 0;
4083 gimple
*def_stmt
= NULL
;
4084 gimple_seq stmts
= NULL
;
4086 gcc_assert (vectype
);
4087 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
4089 gcc_assert (POINTER_TYPE_P (scalar_type
) || INTEGRAL_TYPE_P (scalar_type
)
4090 || SCALAR_FLOAT_TYPE_P (scalar_type
));
4092 if (nested_in_vect_loop_p (loop
, stmt
))
4093 nested_in_vect_loop
= true;
4095 gcc_assert (loop
== (gimple_bb (stmt
))->loop_father
);
4097 /* In case of double reduction we only create a vector variable to be put
4098 in the reduction phi node. The actual statement creation is done in
4099 vect_create_epilog_for_reduction. */
4100 if (adjustment_def
&& nested_in_vect_loop
4101 && TREE_CODE (init_val
) == SSA_NAME
4102 && (def_stmt
= SSA_NAME_DEF_STMT (init_val
))
4103 && gimple_code (def_stmt
) == GIMPLE_PHI
4104 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
4105 && vinfo_for_stmt (def_stmt
)
4106 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
4107 == vect_double_reduction_def
)
4109 *adjustment_def
= NULL
;
4110 return vect_create_destination_var (init_val
, vectype
);
4113 /* In case of a nested reduction do not use an adjustment def as
4114 that case is not supported by the epilogue generation correctly
4115 if ncopies is not one. */
4116 if (adjustment_def
&& nested_in_vect_loop
)
4118 *adjustment_def
= NULL
;
4119 return vect_get_vec_def_for_operand (init_val
, stmt
);
4124 case WIDEN_SUM_EXPR
:
4133 /* ADJUSMENT_DEF is NULL when called from
4134 vect_create_epilog_for_reduction to vectorize double reduction. */
4136 *adjustment_def
= init_val
;
4138 if (code
== MULT_EXPR
)
4140 real_init_val
= dconst1
;
4144 if (code
== BIT_AND_EXPR
)
4147 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
4148 def_for_init
= build_real (scalar_type
, real_init_val
);
4150 def_for_init
= build_int_cst (scalar_type
, int_init_val
);
4152 /* Create a vector of '0' or '1' except the first element. */
4153 elts
= XALLOCAVEC (tree
, nunits
);
4154 for (i
= nunits
- 2; i
>= 0; --i
)
4155 elts
[i
+ 1] = def_for_init
;
4157 /* Option1: the first element is '0' or '1' as well. */
4160 elts
[0] = def_for_init
;
4161 init_def
= build_vector (vectype
, elts
);
4165 /* Option2: the first element is INIT_VAL. */
4167 if (TREE_CONSTANT (init_val
))
4168 init_def
= build_vector (vectype
, elts
);
4171 vec
<constructor_elt
, va_gc
> *v
;
4172 vec_alloc (v
, nunits
);
4173 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, init_val
);
4174 for (i
= 1; i
< nunits
; ++i
)
4175 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[i
]);
4176 init_def
= build_constructor (vectype
, v
);
4186 *adjustment_def
= NULL_TREE
;
4187 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_vinfo
) != COND_REDUCTION
)
4189 init_def
= vect_get_vec_def_for_operand (init_val
, stmt
);
4193 init_val
= gimple_convert (&stmts
, TREE_TYPE (vectype
), init_val
);
4194 if (! gimple_seq_empty_p (stmts
))
4195 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
4196 init_def
= build_vector_from_val (vectype
, init_val
);
4206 /* Function vect_create_epilog_for_reduction
4208 Create code at the loop-epilog to finalize the result of a reduction
4211 VECT_DEFS is list of vector of partial results, i.e., the lhs's of vector
4212 reduction statements.
4213 STMT is the scalar reduction stmt that is being vectorized.
4214 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
4215 number of elements that we can fit in a vectype (nunits). In this case
4216 we have to generate more than one vector stmt - i.e - we need to "unroll"
4217 the vector stmt by a factor VF/nunits. For more details see documentation
4218 in vectorizable_operation.
4219 REDUC_CODE is the tree-code for the epilog reduction.
4220 REDUCTION_PHIS is a list of the phi-nodes that carry the reduction
4222 REDUC_INDEX is the index of the operand in the right hand side of the
4223 statement that is defined by REDUCTION_PHI.
4224 DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
4225 SLP_NODE is an SLP node containing a group of reduction statements. The
4226 first one in this group is STMT.
4227 INDUCTION_INDEX is the index of the loop for condition reductions.
4228 Otherwise it is undefined.
4231 1. Creates the reduction def-use cycles: sets the arguments for
4233 The loop-entry argument is the vectorized initial-value of the reduction.
4234 The loop-latch argument is taken from VECT_DEFS - the vector of partial
4236 2. "Reduces" each vector of partial results VECT_DEFS into a single result,
4237 by applying the operation specified by REDUC_CODE if available, or by
4238 other means (whole-vector shifts or a scalar loop).
4239 The function also creates a new phi node at the loop exit to preserve
4240 loop-closed form, as illustrated below.
4242 The flow at the entry to this function:
4245 vec_def = phi <null, null> # REDUCTION_PHI
4246 VECT_DEF = vector_stmt # vectorized form of STMT
4247 s_loop = scalar_stmt # (scalar) STMT
4249 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4253 The above is transformed by this function into:
4256 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
4257 VECT_DEF = vector_stmt # vectorized form of STMT
4258 s_loop = scalar_stmt # (scalar) STMT
4260 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4261 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4262 v_out2 = reduce <v_out1>
4263 s_out3 = extract_field <v_out2, 0>
4264 s_out4 = adjust_result <s_out3>
4270 vect_create_epilog_for_reduction (vec
<tree
> vect_defs
, gimple
*stmt
,
4271 int ncopies
, enum tree_code reduc_code
,
4272 vec
<gimple
*> reduction_phis
,
4273 int reduc_index
, bool double_reduc
,
4274 slp_tree slp_node
, tree induction_index
)
4276 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
4277 stmt_vec_info prev_phi_info
;
4280 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
4281 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
), *outer_loop
= NULL
;
4282 basic_block exit_bb
;
4285 gimple
*new_phi
= NULL
, *phi
;
4286 gimple_stmt_iterator exit_gsi
;
4288 tree new_temp
= NULL_TREE
, new_dest
, new_name
, new_scalar_dest
;
4289 gimple
*epilog_stmt
= NULL
;
4290 enum tree_code code
= gimple_assign_rhs_code (stmt
);
4293 tree adjustment_def
= NULL
;
4294 tree vec_initial_def
= NULL
;
4295 tree reduction_op
, expr
, def
, initial_def
= NULL
;
4296 tree orig_name
, scalar_result
;
4297 imm_use_iterator imm_iter
, phi_imm_iter
;
4298 use_operand_p use_p
, phi_use_p
;
4299 gimple
*use_stmt
, *orig_stmt
, *reduction_phi
= NULL
;
4300 bool nested_in_vect_loop
= false;
4301 auto_vec
<gimple
*> new_phis
;
4302 auto_vec
<gimple
*> inner_phis
;
4303 enum vect_def_type dt
= vect_unknown_def_type
;
4305 auto_vec
<tree
> scalar_results
;
4306 unsigned int group_size
= 1, k
, ratio
;
4307 auto_vec
<tree
> vec_initial_defs
;
4308 auto_vec
<gimple
*> phis
;
4309 bool slp_reduc
= false;
4310 tree new_phi_result
;
4311 gimple
*inner_phi
= NULL
;
4314 group_size
= SLP_TREE_SCALAR_STMTS (slp_node
).length ();
4316 if (nested_in_vect_loop_p (loop
, stmt
))
4320 nested_in_vect_loop
= true;
4321 gcc_assert (!slp_node
);
4324 reduction_op
= get_reduction_op (stmt
, reduc_index
);
4326 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
4327 gcc_assert (vectype
);
4328 mode
= TYPE_MODE (vectype
);
4330 /* 1. Create the reduction def-use cycle:
4331 Set the arguments of REDUCTION_PHIS, i.e., transform
4334 vec_def = phi <null, null> # REDUCTION_PHI
4335 VECT_DEF = vector_stmt # vectorized form of STMT
4341 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
4342 VECT_DEF = vector_stmt # vectorized form of STMT
4345 (in case of SLP, do it for all the phis). */
4347 /* Get the loop-entry arguments. */
4348 enum vect_def_type initial_def_dt
= vect_unknown_def_type
;
4350 vect_get_vec_defs (reduction_op
, NULL_TREE
, stmt
, &vec_initial_defs
,
4351 NULL
, slp_node
, reduc_index
);
4354 /* Get at the scalar def before the loop, that defines the initial value
4355 of the reduction variable. */
4356 gimple
*def_stmt
= SSA_NAME_DEF_STMT (reduction_op
);
4357 initial_def
= PHI_ARG_DEF_FROM_EDGE (def_stmt
,
4358 loop_preheader_edge (loop
));
4359 vect_is_simple_use (initial_def
, loop_vinfo
, &def_stmt
, &initial_def_dt
);
4360 vec_initial_def
= get_initial_def_for_reduction (stmt
, initial_def
,
4362 vec_initial_defs
.create (1);
4363 vec_initial_defs
.quick_push (vec_initial_def
);
4366 /* Set phi nodes arguments. */
4367 FOR_EACH_VEC_ELT (reduction_phis
, i
, phi
)
4369 tree vec_init_def
, def
;
4371 vec_init_def
= force_gimple_operand (vec_initial_defs
[i
], &stmts
,
4373 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
4375 for (j
= 0; j
< ncopies
; j
++)
4379 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
4380 if (nested_in_vect_loop
)
4382 = vect_get_vec_def_for_stmt_copy (initial_def_dt
,
4386 /* Set the loop-entry arg of the reduction-phi. */
4388 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
4389 == INTEGER_INDUC_COND_REDUCTION
)
4391 /* Initialise the reduction phi to zero. This prevents initial
4392 values of non-zero interferring with the reduction op. */
4393 gcc_assert (ncopies
== 1);
4394 gcc_assert (i
== 0);
4396 tree vec_init_def_type
= TREE_TYPE (vec_init_def
);
4397 tree zero_vec
= build_zero_cst (vec_init_def_type
);
4399 add_phi_arg (as_a
<gphi
*> (phi
), zero_vec
,
4400 loop_preheader_edge (loop
), UNKNOWN_LOCATION
);
4403 add_phi_arg (as_a
<gphi
*> (phi
), vec_init_def
,
4404 loop_preheader_edge (loop
), UNKNOWN_LOCATION
);
4406 /* Set the loop-latch arg for the reduction-phi. */
4408 def
= vect_get_vec_def_for_stmt_copy (vect_unknown_def_type
, def
);
4410 add_phi_arg (as_a
<gphi
*> (phi
), def
, loop_latch_edge (loop
),
4413 if (dump_enabled_p ())
4415 dump_printf_loc (MSG_NOTE
, vect_location
,
4416 "transform reduction: created def-use cycle: ");
4417 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
4418 dump_printf (MSG_NOTE
, "\n");
4419 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, SSA_NAME_DEF_STMT (def
), 0);
4420 dump_printf (MSG_NOTE
, "\n");
4425 /* 2. Create epilog code.
4426 The reduction epilog code operates across the elements of the vector
4427 of partial results computed by the vectorized loop.
4428 The reduction epilog code consists of:
4430 step 1: compute the scalar result in a vector (v_out2)
4431 step 2: extract the scalar result (s_out3) from the vector (v_out2)
4432 step 3: adjust the scalar result (s_out3) if needed.
4434 Step 1 can be accomplished using one the following three schemes:
4435 (scheme 1) using reduc_code, if available.
4436 (scheme 2) using whole-vector shifts, if available.
4437 (scheme 3) using a scalar loop. In this case steps 1+2 above are
4440 The overall epilog code looks like this:
4442 s_out0 = phi <s_loop> # original EXIT_PHI
4443 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4444 v_out2 = reduce <v_out1> # step 1
4445 s_out3 = extract_field <v_out2, 0> # step 2
4446 s_out4 = adjust_result <s_out3> # step 3
4448 (step 3 is optional, and steps 1 and 2 may be combined).
4449 Lastly, the uses of s_out0 are replaced by s_out4. */
4452 /* 2.1 Create new loop-exit-phis to preserve loop-closed form:
4453 v_out1 = phi <VECT_DEF>
4454 Store them in NEW_PHIS. */
4456 exit_bb
= single_exit (loop
)->dest
;
4457 prev_phi_info
= NULL
;
4458 new_phis
.create (vect_defs
.length ());
4459 FOR_EACH_VEC_ELT (vect_defs
, i
, def
)
4461 for (j
= 0; j
< ncopies
; j
++)
4463 tree new_def
= copy_ssa_name (def
);
4464 phi
= create_phi_node (new_def
, exit_bb
);
4465 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, loop_vinfo
));
4467 new_phis
.quick_push (phi
);
4470 def
= vect_get_vec_def_for_stmt_copy (dt
, def
);
4471 STMT_VINFO_RELATED_STMT (prev_phi_info
) = phi
;
4474 SET_PHI_ARG_DEF (phi
, single_exit (loop
)->dest_idx
, def
);
4475 prev_phi_info
= vinfo_for_stmt (phi
);
4479 /* The epilogue is created for the outer-loop, i.e., for the loop being
4480 vectorized. Create exit phis for the outer loop. */
4484 exit_bb
= single_exit (loop
)->dest
;
4485 inner_phis
.create (vect_defs
.length ());
4486 FOR_EACH_VEC_ELT (new_phis
, i
, phi
)
4488 tree new_result
= copy_ssa_name (PHI_RESULT (phi
));
4489 gphi
*outer_phi
= create_phi_node (new_result
, exit_bb
);
4490 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
4492 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
4494 inner_phis
.quick_push (phi
);
4495 new_phis
[i
] = outer_phi
;
4496 prev_phi_info
= vinfo_for_stmt (outer_phi
);
4497 while (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
)))
4499 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
4500 new_result
= copy_ssa_name (PHI_RESULT (phi
));
4501 outer_phi
= create_phi_node (new_result
, exit_bb
);
4502 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
4504 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
4506 STMT_VINFO_RELATED_STMT (prev_phi_info
) = outer_phi
;
4507 prev_phi_info
= vinfo_for_stmt (outer_phi
);
4512 exit_gsi
= gsi_after_labels (exit_bb
);
4514 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
4515 (i.e. when reduc_code is not available) and in the final adjustment
4516 code (if needed). Also get the original scalar reduction variable as
4517 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
4518 represents a reduction pattern), the tree-code and scalar-def are
4519 taken from the original stmt that the pattern-stmt (STMT) replaces.
4520 Otherwise (it is a regular reduction) - the tree-code and scalar-def
4521 are taken from STMT. */
4523 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
4526 /* Regular reduction */
4531 /* Reduction pattern */
4532 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (orig_stmt
);
4533 gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
));
4534 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo
) == stmt
);
4537 code
= gimple_assign_rhs_code (orig_stmt
);
4538 /* For MINUS_EXPR the initial vector is [init_val,0,...,0], therefore,
4539 partial results are added and not subtracted. */
4540 if (code
== MINUS_EXPR
)
4543 scalar_dest
= gimple_assign_lhs (orig_stmt
);
4544 scalar_type
= TREE_TYPE (scalar_dest
);
4545 scalar_results
.create (group_size
);
4546 new_scalar_dest
= vect_create_destination_var (scalar_dest
, NULL
);
4547 bitsize
= TYPE_SIZE (scalar_type
);
4549 /* In case this is a reduction in an inner-loop while vectorizing an outer
4550 loop - we don't need to extract a single scalar result at the end of the
4551 inner-loop (unless it is double reduction, i.e., the use of reduction is
4552 outside the outer-loop). The final vector of partial results will be used
4553 in the vectorized outer-loop, or reduced to a scalar result at the end of
4555 if (nested_in_vect_loop
&& !double_reduc
)
4556 goto vect_finalize_reduction
;
4558 /* SLP reduction without reduction chain, e.g.,
4562 b2 = operation (b1) */
4563 slp_reduc
= (slp_node
&& !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)));
4565 /* In case of reduction chain, e.g.,
4568 a3 = operation (a2),
4570 we may end up with more than one vector result. Here we reduce them to
4572 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4574 tree first_vect
= PHI_RESULT (new_phis
[0]);
4576 gassign
*new_vec_stmt
= NULL
;
4578 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4579 for (k
= 1; k
< new_phis
.length (); k
++)
4581 gimple
*next_phi
= new_phis
[k
];
4582 tree second_vect
= PHI_RESULT (next_phi
);
4584 tmp
= build2 (code
, vectype
, first_vect
, second_vect
);
4585 new_vec_stmt
= gimple_build_assign (vec_dest
, tmp
);
4586 first_vect
= make_ssa_name (vec_dest
, new_vec_stmt
);
4587 gimple_assign_set_lhs (new_vec_stmt
, first_vect
);
4588 gsi_insert_before (&exit_gsi
, new_vec_stmt
, GSI_SAME_STMT
);
4591 new_phi_result
= first_vect
;
4594 new_phis
.truncate (0);
4595 new_phis
.safe_push (new_vec_stmt
);
4599 new_phi_result
= PHI_RESULT (new_phis
[0]);
4601 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
)
4603 /* For condition reductions, we have a vector (NEW_PHI_RESULT) containing
4604 various data values where the condition matched and another vector
4605 (INDUCTION_INDEX) containing all the indexes of those matches. We
4606 need to extract the last matching index (which will be the index with
4607 highest value) and use this to index into the data vector.
4608 For the case where there were no matches, the data vector will contain
4609 all default values and the index vector will be all zeros. */
4611 /* Get various versions of the type of the vector of indexes. */
4612 tree index_vec_type
= TREE_TYPE (induction_index
);
4613 gcc_checking_assert (TYPE_UNSIGNED (index_vec_type
));
4614 tree index_scalar_type
= TREE_TYPE (index_vec_type
);
4615 tree index_vec_cmp_type
= build_same_sized_truth_vector_type
4618 /* Get an unsigned integer version of the type of the data vector. */
4619 int scalar_precision
= GET_MODE_PRECISION (TYPE_MODE (scalar_type
));
4620 tree scalar_type_unsigned
= make_unsigned_type (scalar_precision
);
4621 tree vectype_unsigned
= build_vector_type
4622 (scalar_type_unsigned
, TYPE_VECTOR_SUBPARTS (vectype
));
4624 /* First we need to create a vector (ZERO_VEC) of zeros and another
4625 vector (MAX_INDEX_VEC) filled with the last matching index, which we
4626 can create using a MAX reduction and then expanding.
4627 In the case where the loop never made any matches, the max index will
4630 /* Vector of {0, 0, 0,...}. */
4631 tree zero_vec
= make_ssa_name (vectype
);
4632 tree zero_vec_rhs
= build_zero_cst (vectype
);
4633 gimple
*zero_vec_stmt
= gimple_build_assign (zero_vec
, zero_vec_rhs
);
4634 gsi_insert_before (&exit_gsi
, zero_vec_stmt
, GSI_SAME_STMT
);
4636 /* Find maximum value from the vector of found indexes. */
4637 tree max_index
= make_ssa_name (index_scalar_type
);
4638 gimple
*max_index_stmt
= gimple_build_assign (max_index
, REDUC_MAX_EXPR
,
4640 gsi_insert_before (&exit_gsi
, max_index_stmt
, GSI_SAME_STMT
);
4642 /* Vector of {max_index, max_index, max_index,...}. */
4643 tree max_index_vec
= make_ssa_name (index_vec_type
);
4644 tree max_index_vec_rhs
= build_vector_from_val (index_vec_type
,
4646 gimple
*max_index_vec_stmt
= gimple_build_assign (max_index_vec
,
4648 gsi_insert_before (&exit_gsi
, max_index_vec_stmt
, GSI_SAME_STMT
);
4650 /* Next we compare the new vector (MAX_INDEX_VEC) full of max indexes
4651 with the vector (INDUCTION_INDEX) of found indexes, choosing values
4652 from the data vector (NEW_PHI_RESULT) for matches, 0 (ZERO_VEC)
4653 otherwise. Only one value should match, resulting in a vector
4654 (VEC_COND) with one data value and the rest zeros.
4655 In the case where the loop never made any matches, every index will
4656 match, resulting in a vector with all data values (which will all be
4657 the default value). */
4659 /* Compare the max index vector to the vector of found indexes to find
4660 the position of the max value. */
4661 tree vec_compare
= make_ssa_name (index_vec_cmp_type
);
4662 gimple
*vec_compare_stmt
= gimple_build_assign (vec_compare
, EQ_EXPR
,
4665 gsi_insert_before (&exit_gsi
, vec_compare_stmt
, GSI_SAME_STMT
);
4667 /* Use the compare to choose either values from the data vector or
4669 tree vec_cond
= make_ssa_name (vectype
);
4670 gimple
*vec_cond_stmt
= gimple_build_assign (vec_cond
, VEC_COND_EXPR
,
4671 vec_compare
, new_phi_result
,
4673 gsi_insert_before (&exit_gsi
, vec_cond_stmt
, GSI_SAME_STMT
);
4675 /* Finally we need to extract the data value from the vector (VEC_COND)
4676 into a scalar (MATCHED_DATA_REDUC). Logically we want to do a OR
4677 reduction, but because this doesn't exist, we can use a MAX reduction
4678 instead. The data value might be signed or a float so we need to cast
4680 In the case where the loop never made any matches, the data values are
4681 all identical, and so will reduce down correctly. */
4683 /* Make the matched data values unsigned. */
4684 tree vec_cond_cast
= make_ssa_name (vectype_unsigned
);
4685 tree vec_cond_cast_rhs
= build1 (VIEW_CONVERT_EXPR
, vectype_unsigned
,
4687 gimple
*vec_cond_cast_stmt
= gimple_build_assign (vec_cond_cast
,
4690 gsi_insert_before (&exit_gsi
, vec_cond_cast_stmt
, GSI_SAME_STMT
);
4692 /* Reduce down to a scalar value. */
4693 tree data_reduc
= make_ssa_name (scalar_type_unsigned
);
4694 optab ot
= optab_for_tree_code (REDUC_MAX_EXPR
, vectype_unsigned
,
4696 gcc_assert (optab_handler (ot
, TYPE_MODE (vectype_unsigned
))
4697 != CODE_FOR_nothing
);
4698 gimple
*data_reduc_stmt
= gimple_build_assign (data_reduc
,
4701 gsi_insert_before (&exit_gsi
, data_reduc_stmt
, GSI_SAME_STMT
);
4703 /* Convert the reduced value back to the result type and set as the
4705 tree data_reduc_cast
= build1 (VIEW_CONVERT_EXPR
, scalar_type
,
4707 epilog_stmt
= gimple_build_assign (new_scalar_dest
, data_reduc_cast
);
4708 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4709 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4710 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4711 scalar_results
.safe_push (new_temp
);
4714 /* 2.3 Create the reduction code, using one of the three schemes described
4715 above. In SLP we simply need to extract all the elements from the
4716 vector (without reducing them), so we use scalar shifts. */
4717 else if (reduc_code
!= ERROR_MARK
&& !slp_reduc
)
4722 /*** Case 1: Create:
4723 v_out2 = reduc_expr <v_out1> */
4725 if (dump_enabled_p ())
4726 dump_printf_loc (MSG_NOTE
, vect_location
,
4727 "Reduce using direct vector reduction.\n");
4729 vec_elem_type
= TREE_TYPE (TREE_TYPE (new_phi_result
));
4730 if (!useless_type_conversion_p (scalar_type
, vec_elem_type
))
4733 vect_create_destination_var (scalar_dest
, vec_elem_type
);
4734 tmp
= build1 (reduc_code
, vec_elem_type
, new_phi_result
);
4735 epilog_stmt
= gimple_build_assign (tmp_dest
, tmp
);
4736 new_temp
= make_ssa_name (tmp_dest
, epilog_stmt
);
4737 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4738 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4740 tmp
= build1 (NOP_EXPR
, scalar_type
, new_temp
);
4743 tmp
= build1 (reduc_code
, scalar_type
, new_phi_result
);
4745 epilog_stmt
= gimple_build_assign (new_scalar_dest
, tmp
);
4746 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4747 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4748 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4750 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
4751 == INTEGER_INDUC_COND_REDUCTION
)
4753 /* Earlier we set the initial value to be zero. Check the result
4754 and if it is zero then replace with the original initial
4756 tree zero
= build_zero_cst (scalar_type
);
4757 tree zcompare
= build2 (EQ_EXPR
, boolean_type_node
, new_temp
, zero
);
4759 tmp
= make_ssa_name (new_scalar_dest
);
4760 epilog_stmt
= gimple_build_assign (tmp
, COND_EXPR
, zcompare
,
4761 initial_def
, new_temp
);
4762 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4766 scalar_results
.safe_push (new_temp
);
4770 bool reduce_with_shift
= have_whole_vector_shift (mode
);
4771 int element_bitsize
= tree_to_uhwi (bitsize
);
4772 int vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
4775 /* Regardless of whether we have a whole vector shift, if we're
4776 emulating the operation via tree-vect-generic, we don't want
4777 to use it. Only the first round of the reduction is likely
4778 to still be profitable via emulation. */
4779 /* ??? It might be better to emit a reduction tree code here, so that
4780 tree-vect-generic can expand the first round via bit tricks. */
4781 if (!VECTOR_MODE_P (mode
))
4782 reduce_with_shift
= false;
4785 optab optab
= optab_for_tree_code (code
, vectype
, optab_default
);
4786 if (optab_handler (optab
, mode
) == CODE_FOR_nothing
)
4787 reduce_with_shift
= false;
4790 if (reduce_with_shift
&& !slp_reduc
)
4792 int nelements
= vec_size_in_bits
/ element_bitsize
;
4793 unsigned char *sel
= XALLOCAVEC (unsigned char, nelements
);
4797 tree zero_vec
= build_zero_cst (vectype
);
4798 /*** Case 2: Create:
4799 for (offset = nelements/2; offset >= 1; offset/=2)
4801 Create: va' = vec_shift <va, offset>
4802 Create: va = vop <va, va'>
4807 if (dump_enabled_p ())
4808 dump_printf_loc (MSG_NOTE
, vect_location
,
4809 "Reduce using vector shifts\n");
4811 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4812 new_temp
= new_phi_result
;
4813 for (elt_offset
= nelements
/ 2;
4817 calc_vec_perm_mask_for_shift (mode
, elt_offset
, sel
);
4818 tree mask
= vect_gen_perm_mask_any (vectype
, sel
);
4819 epilog_stmt
= gimple_build_assign (vec_dest
, VEC_PERM_EXPR
,
4820 new_temp
, zero_vec
, mask
);
4821 new_name
= make_ssa_name (vec_dest
, epilog_stmt
);
4822 gimple_assign_set_lhs (epilog_stmt
, new_name
);
4823 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4825 epilog_stmt
= gimple_build_assign (vec_dest
, code
, new_name
,
4827 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
4828 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4829 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4832 /* 2.4 Extract the final scalar result. Create:
4833 s_out3 = extract_field <v_out2, bitpos> */
4835 if (dump_enabled_p ())
4836 dump_printf_loc (MSG_NOTE
, vect_location
,
4837 "extract scalar result\n");
4839 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, new_temp
,
4840 bitsize
, bitsize_zero_node
);
4841 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4842 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4843 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4844 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4845 scalar_results
.safe_push (new_temp
);
4849 /*** Case 3: Create:
4850 s = extract_field <v_out2, 0>
4851 for (offset = element_size;
4852 offset < vector_size;
4853 offset += element_size;)
4855 Create: s' = extract_field <v_out2, offset>
4856 Create: s = op <s, s'> // For non SLP cases
4859 if (dump_enabled_p ())
4860 dump_printf_loc (MSG_NOTE
, vect_location
,
4861 "Reduce using scalar code.\n");
4863 vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
4864 FOR_EACH_VEC_ELT (new_phis
, i
, new_phi
)
4867 if (gimple_code (new_phi
) == GIMPLE_PHI
)
4868 vec_temp
= PHI_RESULT (new_phi
);
4870 vec_temp
= gimple_assign_lhs (new_phi
);
4871 tree rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
, bitsize
,
4873 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4874 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4875 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4876 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4878 /* In SLP we don't need to apply reduction operation, so we just
4879 collect s' values in SCALAR_RESULTS. */
4881 scalar_results
.safe_push (new_temp
);
4883 for (bit_offset
= element_bitsize
;
4884 bit_offset
< vec_size_in_bits
;
4885 bit_offset
+= element_bitsize
)
4887 tree bitpos
= bitsize_int (bit_offset
);
4888 tree rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
,
4891 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4892 new_name
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4893 gimple_assign_set_lhs (epilog_stmt
, new_name
);
4894 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4898 /* In SLP we don't need to apply reduction operation, so
4899 we just collect s' values in SCALAR_RESULTS. */
4900 new_temp
= new_name
;
4901 scalar_results
.safe_push (new_name
);
4905 epilog_stmt
= gimple_build_assign (new_scalar_dest
, code
,
4906 new_name
, new_temp
);
4907 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4908 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4909 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4914 /* The only case where we need to reduce scalar results in SLP, is
4915 unrolling. If the size of SCALAR_RESULTS is greater than
4916 GROUP_SIZE, we reduce them combining elements modulo
4920 tree res
, first_res
, new_res
;
4923 /* Reduce multiple scalar results in case of SLP unrolling. */
4924 for (j
= group_size
; scalar_results
.iterate (j
, &res
);
4927 first_res
= scalar_results
[j
% group_size
];
4928 new_stmt
= gimple_build_assign (new_scalar_dest
, code
,
4930 new_res
= make_ssa_name (new_scalar_dest
, new_stmt
);
4931 gimple_assign_set_lhs (new_stmt
, new_res
);
4932 gsi_insert_before (&exit_gsi
, new_stmt
, GSI_SAME_STMT
);
4933 scalar_results
[j
% group_size
] = new_res
;
4937 /* Not SLP - we have one scalar to keep in SCALAR_RESULTS. */
4938 scalar_results
.safe_push (new_temp
);
4942 vect_finalize_reduction
:
4947 /* 2.5 Adjust the final result by the initial value of the reduction
4948 variable. (When such adjustment is not needed, then
4949 'adjustment_def' is zero). For example, if code is PLUS we create:
4950 new_temp = loop_exit_def + adjustment_def */
4954 gcc_assert (!slp_reduc
);
4955 if (nested_in_vect_loop
)
4957 new_phi
= new_phis
[0];
4958 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) == VECTOR_TYPE
);
4959 expr
= build2 (code
, vectype
, PHI_RESULT (new_phi
), adjustment_def
);
4960 new_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4964 new_temp
= scalar_results
[0];
4965 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) != VECTOR_TYPE
);
4966 expr
= build2 (code
, scalar_type
, new_temp
, adjustment_def
);
4967 new_dest
= vect_create_destination_var (scalar_dest
, scalar_type
);
4970 epilog_stmt
= gimple_build_assign (new_dest
, expr
);
4971 new_temp
= make_ssa_name (new_dest
, epilog_stmt
);
4972 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4973 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4974 if (nested_in_vect_loop
)
4976 set_vinfo_for_stmt (epilog_stmt
,
4977 new_stmt_vec_info (epilog_stmt
, loop_vinfo
));
4978 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (epilog_stmt
)) =
4979 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_phi
));
4982 scalar_results
.quick_push (new_temp
);
4984 scalar_results
[0] = new_temp
;
4987 scalar_results
[0] = new_temp
;
4989 new_phis
[0] = epilog_stmt
;
4992 /* 2.6 Handle the loop-exit phis. Replace the uses of scalar loop-exit
4993 phis with new adjusted scalar results, i.e., replace use <s_out0>
4998 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4999 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
5000 v_out2 = reduce <v_out1>
5001 s_out3 = extract_field <v_out2, 0>
5002 s_out4 = adjust_result <s_out3>
5009 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
5010 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
5011 v_out2 = reduce <v_out1>
5012 s_out3 = extract_field <v_out2, 0>
5013 s_out4 = adjust_result <s_out3>
5018 /* In SLP reduction chain we reduce vector results into one vector if
5019 necessary, hence we set here GROUP_SIZE to 1. SCALAR_DEST is the LHS of
5020 the last stmt in the reduction chain, since we are looking for the loop
5022 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
5024 gimple
*dest_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[group_size
- 1];
5025 /* Handle reduction patterns. */
5026 if (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (dest_stmt
)))
5027 dest_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (dest_stmt
));
5029 scalar_dest
= gimple_assign_lhs (dest_stmt
);
5033 /* In SLP we may have several statements in NEW_PHIS and REDUCTION_PHIS (in
5034 case that GROUP_SIZE is greater than vectorization factor). Therefore, we
5035 need to match SCALAR_RESULTS with corresponding statements. The first
5036 (GROUP_SIZE / number of new vector stmts) scalar results correspond to
5037 the first vector stmt, etc.
5038 (RATIO is equal to (GROUP_SIZE / number of new vector stmts)). */
5039 if (group_size
> new_phis
.length ())
5041 ratio
= group_size
/ new_phis
.length ();
5042 gcc_assert (!(group_size
% new_phis
.length ()));
5047 for (k
= 0; k
< group_size
; k
++)
5051 epilog_stmt
= new_phis
[k
/ ratio
];
5052 reduction_phi
= reduction_phis
[k
/ ratio
];
5054 inner_phi
= inner_phis
[k
/ ratio
];
5059 gimple
*current_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[k
];
5061 orig_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (current_stmt
));
5062 /* SLP statements can't participate in patterns. */
5063 gcc_assert (!orig_stmt
);
5064 scalar_dest
= gimple_assign_lhs (current_stmt
);
5068 /* Find the loop-closed-use at the loop exit of the original scalar
5069 result. (The reduction result is expected to have two immediate uses -
5070 one at the latch block, and one at the loop exit). */
5071 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
5072 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
)))
5073 && !is_gimple_debug (USE_STMT (use_p
)))
5074 phis
.safe_push (USE_STMT (use_p
));
5076 /* While we expect to have found an exit_phi because of loop-closed-ssa
5077 form we can end up without one if the scalar cycle is dead. */
5079 FOR_EACH_VEC_ELT (phis
, i
, exit_phi
)
5083 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
5086 /* FORNOW. Currently not supporting the case that an inner-loop
5087 reduction is not used in the outer-loop (but only outside the
5088 outer-loop), unless it is double reduction. */
5089 gcc_assert ((STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
5090 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
))
5094 STMT_VINFO_VEC_STMT (exit_phi_vinfo
) = inner_phi
;
5096 STMT_VINFO_VEC_STMT (exit_phi_vinfo
) = epilog_stmt
;
5098 || STMT_VINFO_DEF_TYPE (exit_phi_vinfo
)
5099 != vect_double_reduction_def
)
5102 /* Handle double reduction:
5104 stmt1: s1 = phi <s0, s2> - double reduction phi (outer loop)
5105 stmt2: s3 = phi <s1, s4> - (regular) reduc phi (inner loop)
5106 stmt3: s4 = use (s3) - (regular) reduc stmt (inner loop)
5107 stmt4: s2 = phi <s4> - double reduction stmt (outer loop)
5109 At that point the regular reduction (stmt2 and stmt3) is
5110 already vectorized, as well as the exit phi node, stmt4.
5111 Here we vectorize the phi node of double reduction, stmt1, and
5112 update all relevant statements. */
5114 /* Go through all the uses of s2 to find double reduction phi
5115 node, i.e., stmt1 above. */
5116 orig_name
= PHI_RESULT (exit_phi
);
5117 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
5119 stmt_vec_info use_stmt_vinfo
;
5120 stmt_vec_info new_phi_vinfo
;
5121 tree vect_phi_init
, preheader_arg
, vect_phi_res
, init_def
;
5122 basic_block bb
= gimple_bb (use_stmt
);
5125 /* Check that USE_STMT is really double reduction phi
5127 if (gimple_code (use_stmt
) != GIMPLE_PHI
5128 || gimple_phi_num_args (use_stmt
) != 2
5129 || bb
->loop_father
!= outer_loop
)
5131 use_stmt_vinfo
= vinfo_for_stmt (use_stmt
);
5133 || STMT_VINFO_DEF_TYPE (use_stmt_vinfo
)
5134 != vect_double_reduction_def
)
5137 /* Create vector phi node for double reduction:
5138 vs1 = phi <vs0, vs2>
5139 vs1 was created previously in this function by a call to
5140 vect_get_vec_def_for_operand and is stored in
5142 vs2 is defined by INNER_PHI, the vectorized EXIT_PHI;
5143 vs0 is created here. */
5145 /* Create vector phi node. */
5146 vect_phi
= create_phi_node (vec_initial_def
, bb
);
5147 new_phi_vinfo
= new_stmt_vec_info (vect_phi
,
5148 loop_vec_info_for_loop (outer_loop
));
5149 set_vinfo_for_stmt (vect_phi
, new_phi_vinfo
);
5151 /* Create vs0 - initial def of the double reduction phi. */
5152 preheader_arg
= PHI_ARG_DEF_FROM_EDGE (use_stmt
,
5153 loop_preheader_edge (outer_loop
));
5154 init_def
= get_initial_def_for_reduction (stmt
,
5155 preheader_arg
, NULL
);
5156 vect_phi_init
= vect_init_vector (use_stmt
, init_def
,
5159 /* Update phi node arguments with vs0 and vs2. */
5160 add_phi_arg (vect_phi
, vect_phi_init
,
5161 loop_preheader_edge (outer_loop
),
5163 add_phi_arg (vect_phi
, PHI_RESULT (inner_phi
),
5164 loop_latch_edge (outer_loop
), UNKNOWN_LOCATION
);
5165 if (dump_enabled_p ())
5167 dump_printf_loc (MSG_NOTE
, vect_location
,
5168 "created double reduction phi node: ");
5169 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, vect_phi
, 0);
5170 dump_printf (MSG_NOTE
, "\n");
5173 vect_phi_res
= PHI_RESULT (vect_phi
);
5175 /* Replace the use, i.e., set the correct vs1 in the regular
5176 reduction phi node. FORNOW, NCOPIES is always 1, so the
5177 loop is redundant. */
5178 use
= reduction_phi
;
5179 for (j
= 0; j
< ncopies
; j
++)
5181 edge pr_edge
= loop_preheader_edge (loop
);
5182 SET_PHI_ARG_DEF (use
, pr_edge
->dest_idx
, vect_phi_res
);
5183 use
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use
));
5190 if (nested_in_vect_loop
)
5199 /* Find the loop-closed-use at the loop exit of the original scalar
5200 result. (The reduction result is expected to have two immediate uses,
5201 one at the latch block, and one at the loop exit). For double
5202 reductions we are looking for exit phis of the outer loop. */
5203 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
5205 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
5207 if (!is_gimple_debug (USE_STMT (use_p
)))
5208 phis
.safe_push (USE_STMT (use_p
));
5212 if (double_reduc
&& gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
5214 tree phi_res
= PHI_RESULT (USE_STMT (use_p
));
5216 FOR_EACH_IMM_USE_FAST (phi_use_p
, phi_imm_iter
, phi_res
)
5218 if (!flow_bb_inside_loop_p (loop
,
5219 gimple_bb (USE_STMT (phi_use_p
)))
5220 && !is_gimple_debug (USE_STMT (phi_use_p
)))
5221 phis
.safe_push (USE_STMT (phi_use_p
));
5227 FOR_EACH_VEC_ELT (phis
, i
, exit_phi
)
5229 /* Replace the uses: */
5230 orig_name
= PHI_RESULT (exit_phi
);
5231 scalar_result
= scalar_results
[k
];
5232 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
5233 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
5234 SET_USE (use_p
, scalar_result
);
5242 /* Function is_nonwrapping_integer_induction.
5244 Check if STMT (which is part of loop LOOP) both increments and
5245 does not cause overflow. */
5248 is_nonwrapping_integer_induction (gimple
*stmt
, struct loop
*loop
)
5250 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
5251 tree base
= STMT_VINFO_LOOP_PHI_EVOLUTION_BASE_UNCHANGED (stmt_vinfo
);
5252 tree step
= STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
);
5253 tree lhs_type
= TREE_TYPE (gimple_phi_result (stmt
));
5254 widest_int ni
, max_loop_value
, lhs_max
;
5255 bool overflow
= false;
5257 /* Make sure the loop is integer based. */
5258 if (TREE_CODE (base
) != INTEGER_CST
5259 || TREE_CODE (step
) != INTEGER_CST
)
5262 /* Check that the induction increments. */
5263 if (tree_int_cst_sgn (step
) == -1)
5266 /* Check that the max size of the loop will not wrap. */
5268 if (TYPE_OVERFLOW_UNDEFINED (lhs_type
))
5271 if (! max_stmt_executions (loop
, &ni
))
5274 max_loop_value
= wi::mul (wi::to_widest (step
), ni
, TYPE_SIGN (lhs_type
),
5279 max_loop_value
= wi::add (wi::to_widest (base
), max_loop_value
,
5280 TYPE_SIGN (lhs_type
), &overflow
);
5284 return (wi::min_precision (max_loop_value
, TYPE_SIGN (lhs_type
))
5285 <= TYPE_PRECISION (lhs_type
));
5288 /* Function vectorizable_reduction.
5290 Check if STMT performs a reduction operation that can be vectorized.
5291 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
5292 stmt to replace it, put it in VEC_STMT, and insert it at GSI.
5293 Return FALSE if not a vectorizable STMT, TRUE otherwise.
5295 This function also handles reduction idioms (patterns) that have been
5296 recognized in advance during vect_pattern_recog. In this case, STMT may be
5298 X = pattern_expr (arg0, arg1, ..., X)
5299 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
5300 sequence that had been detected and replaced by the pattern-stmt (STMT).
5302 This function also handles reduction of condition expressions, for example:
5303 for (int i = 0; i < N; i++)
5306 This is handled by vectorising the loop and creating an additional vector
5307 containing the loop indexes for which "a[i] < value" was true. In the
5308 function epilogue this is reduced to a single max value and then used to
5309 index into the vector of results.
5311 In some cases of reduction patterns, the type of the reduction variable X is
5312 different than the type of the other arguments of STMT.
5313 In such cases, the vectype that is used when transforming STMT into a vector
5314 stmt is different than the vectype that is used to determine the
5315 vectorization factor, because it consists of a different number of elements
5316 than the actual number of elements that are being operated upon in parallel.
5318 For example, consider an accumulation of shorts into an int accumulator.
5319 On some targets it's possible to vectorize this pattern operating on 8
5320 shorts at a time (hence, the vectype for purposes of determining the
5321 vectorization factor should be V8HI); on the other hand, the vectype that
5322 is used to create the vector form is actually V4SI (the type of the result).
5324 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
5325 indicates what is the actual level of parallelism (V8HI in the example), so
5326 that the right vectorization factor would be derived. This vectype
5327 corresponds to the type of arguments to the reduction stmt, and should *NOT*
5328 be used to create the vectorized stmt. The right vectype for the vectorized
5329 stmt is obtained from the type of the result X:
5330 get_vectype_for_scalar_type (TREE_TYPE (X))
5332 This means that, contrary to "regular" reductions (or "regular" stmts in
5333 general), the following equation:
5334 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
5335 does *NOT* necessarily hold for reduction patterns. */
5338 vectorizable_reduction (gimple
*stmt
, gimple_stmt_iterator
*gsi
,
5339 gimple
**vec_stmt
, slp_tree slp_node
)
5343 tree loop_vec_def0
= NULL_TREE
, loop_vec_def1
= NULL_TREE
;
5344 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
5345 tree vectype_out
= STMT_VINFO_VECTYPE (stmt_info
);
5346 tree vectype_in
= NULL_TREE
;
5347 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
5348 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5349 enum tree_code code
, orig_code
, epilog_reduc_code
;
5350 machine_mode vec_mode
;
5352 optab optab
, reduc_optab
;
5353 tree new_temp
= NULL_TREE
;
5355 enum vect_def_type dt
;
5356 gphi
*new_phi
= NULL
;
5360 stmt_vec_info orig_stmt_info
;
5361 tree expr
= NULL_TREE
;
5365 stmt_vec_info prev_stmt_info
, prev_phi_info
;
5366 bool single_defuse_cycle
= false;
5367 tree reduc_def
= NULL_TREE
;
5368 gimple
*new_stmt
= NULL
;
5371 bool nested_cycle
= false, found_nested_cycle_def
= false;
5372 gimple
*reduc_def_stmt
= NULL
;
5373 bool double_reduc
= false, dummy
;
5375 struct loop
* def_stmt_loop
, *outer_loop
= NULL
;
5377 gimple
*def_arg_stmt
;
5378 auto_vec
<tree
> vec_oprnds0
;
5379 auto_vec
<tree
> vec_oprnds1
;
5380 auto_vec
<tree
> vect_defs
;
5381 auto_vec
<gimple
*> phis
;
5383 tree def0
, def1
, tem
, op0
, op1
= NULL_TREE
;
5384 bool first_p
= true;
5385 tree cr_index_scalar_type
= NULL_TREE
, cr_index_vector_type
= NULL_TREE
;
5386 gimple
*cond_expr_induction_def_stmt
= NULL
;
5388 /* In case of reduction chain we switch to the first stmt in the chain, but
5389 we don't update STMT_INFO, since only the last stmt is marked as reduction
5390 and has reduction properties. */
5391 if (GROUP_FIRST_ELEMENT (stmt_info
)
5392 && GROUP_FIRST_ELEMENT (stmt_info
) != stmt
)
5394 stmt
= GROUP_FIRST_ELEMENT (stmt_info
);
5398 if (nested_in_vect_loop_p (loop
, stmt
))
5402 nested_cycle
= true;
5405 /* 1. Is vectorizable reduction? */
5406 /* Not supportable if the reduction variable is used in the loop, unless
5407 it's a reduction chain. */
5408 if (STMT_VINFO_RELEVANT (stmt_info
) > vect_used_in_outer
5409 && !GROUP_FIRST_ELEMENT (stmt_info
))
5412 /* Reductions that are not used even in an enclosing outer-loop,
5413 are expected to be "live" (used out of the loop). */
5414 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
5415 && !STMT_VINFO_LIVE_P (stmt_info
))
5418 /* Make sure it was already recognized as a reduction computation. */
5419 if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) != vect_reduction_def
5420 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmt
)) != vect_nested_cycle
)
5423 /* 2. Has this been recognized as a reduction pattern?
5425 Check if STMT represents a pattern that has been recognized
5426 in earlier analysis stages. For stmts that represent a pattern,
5427 the STMT_VINFO_RELATED_STMT field records the last stmt in
5428 the original sequence that constitutes the pattern. */
5430 orig_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt
));
5433 orig_stmt_info
= vinfo_for_stmt (orig_stmt
);
5434 gcc_assert (STMT_VINFO_IN_PATTERN_P (orig_stmt_info
));
5435 gcc_assert (!STMT_VINFO_IN_PATTERN_P (stmt_info
));
5438 /* 3. Check the operands of the operation. The first operands are defined
5439 inside the loop body. The last operand is the reduction variable,
5440 which is defined by the loop-header-phi. */
5442 gcc_assert (is_gimple_assign (stmt
));
5445 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
5447 case GIMPLE_SINGLE_RHS
:
5448 op_type
= TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
));
5449 if (op_type
== ternary_op
)
5451 tree rhs
= gimple_assign_rhs1 (stmt
);
5452 ops
[0] = TREE_OPERAND (rhs
, 0);
5453 ops
[1] = TREE_OPERAND (rhs
, 1);
5454 ops
[2] = TREE_OPERAND (rhs
, 2);
5455 code
= TREE_CODE (rhs
);
5461 case GIMPLE_BINARY_RHS
:
5462 code
= gimple_assign_rhs_code (stmt
);
5463 op_type
= TREE_CODE_LENGTH (code
);
5464 gcc_assert (op_type
== binary_op
);
5465 ops
[0] = gimple_assign_rhs1 (stmt
);
5466 ops
[1] = gimple_assign_rhs2 (stmt
);
5469 case GIMPLE_TERNARY_RHS
:
5470 code
= gimple_assign_rhs_code (stmt
);
5471 op_type
= TREE_CODE_LENGTH (code
);
5472 gcc_assert (op_type
== ternary_op
);
5473 ops
[0] = gimple_assign_rhs1 (stmt
);
5474 ops
[1] = gimple_assign_rhs2 (stmt
);
5475 ops
[2] = gimple_assign_rhs3 (stmt
);
5478 case GIMPLE_UNARY_RHS
:
5484 /* The default is that the reduction variable is the last in statement. */
5485 int reduc_index
= op_type
- 1;
5486 if (code
== MINUS_EXPR
)
5489 if (code
== COND_EXPR
&& slp_node
)
5492 scalar_dest
= gimple_assign_lhs (stmt
);
5493 scalar_type
= TREE_TYPE (scalar_dest
);
5494 if (!POINTER_TYPE_P (scalar_type
) && !INTEGRAL_TYPE_P (scalar_type
)
5495 && !SCALAR_FLOAT_TYPE_P (scalar_type
))
5498 /* Do not try to vectorize bit-precision reductions. */
5499 if ((TYPE_PRECISION (scalar_type
)
5500 != GET_MODE_PRECISION (TYPE_MODE (scalar_type
))))
5503 /* All uses but the last are expected to be defined in the loop.
5504 The last use is the reduction variable. In case of nested cycle this
5505 assumption is not true: we use reduc_index to record the index of the
5506 reduction variable. */
5507 for (i
= 0; i
< op_type
; i
++)
5509 if (i
== reduc_index
)
5512 /* The condition of COND_EXPR is checked in vectorizable_condition(). */
5513 if (i
== 0 && code
== COND_EXPR
)
5516 is_simple_use
= vect_is_simple_use (ops
[i
], loop_vinfo
,
5517 &def_stmt
, &dt
, &tem
);
5520 gcc_assert (is_simple_use
);
5522 if (dt
!= vect_internal_def
5523 && dt
!= vect_external_def
5524 && dt
!= vect_constant_def
5525 && dt
!= vect_induction_def
5526 && !(dt
== vect_nested_cycle
&& nested_cycle
))
5529 if (dt
== vect_nested_cycle
)
5531 found_nested_cycle_def
= true;
5532 reduc_def_stmt
= def_stmt
;
5536 if (i
== 1 && code
== COND_EXPR
&& dt
== vect_induction_def
)
5537 cond_expr_induction_def_stmt
= def_stmt
;
5540 is_simple_use
= vect_is_simple_use (ops
[reduc_index
], loop_vinfo
,
5541 &def_stmt
, &dt
, &tem
);
5544 gcc_assert (is_simple_use
);
5545 if (!found_nested_cycle_def
)
5546 reduc_def_stmt
= def_stmt
;
5548 if (reduc_def_stmt
&& gimple_code (reduc_def_stmt
) != GIMPLE_PHI
)
5551 if (!(dt
== vect_reduction_def
5552 || dt
== vect_nested_cycle
5553 || ((dt
== vect_internal_def
|| dt
== vect_external_def
5554 || dt
== vect_constant_def
|| dt
== vect_induction_def
)
5555 && nested_cycle
&& found_nested_cycle_def
)))
5557 /* For pattern recognized stmts, orig_stmt might be a reduction,
5558 but some helper statements for the pattern might not, or
5559 might be COND_EXPRs with reduction uses in the condition. */
5560 gcc_assert (orig_stmt
);
5564 enum vect_reduction_type v_reduc_type
;
5565 gimple
*tmp
= vect_is_simple_reduction (loop_vinfo
, reduc_def_stmt
,
5566 !nested_cycle
, &dummy
, false,
5569 /* If we have a condition reduction, see if we can simplify it further. */
5570 if (v_reduc_type
== COND_REDUCTION
5571 && cond_expr_induction_def_stmt
!= NULL
5572 && is_nonwrapping_integer_induction (cond_expr_induction_def_stmt
, loop
))
5574 if (dump_enabled_p ())
5575 dump_printf_loc (MSG_NOTE
, vect_location
,
5576 "condition expression based on integer induction.\n");
5577 STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) = INTEGER_INDUC_COND_REDUCTION
;
5580 STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) = v_reduc_type
;
5583 gcc_assert (tmp
== orig_stmt
5584 || GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp
)) == orig_stmt
);
5586 /* We changed STMT to be the first stmt in reduction chain, hence we
5587 check that in this case the first element in the chain is STMT. */
5588 gcc_assert (stmt
== tmp
5589 || GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp
)) == stmt
);
5591 if (STMT_VINFO_LIVE_P (vinfo_for_stmt (reduc_def_stmt
)))
5594 if (slp_node
|| PURE_SLP_STMT (stmt_info
))
5597 ncopies
= (LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
5598 / TYPE_VECTOR_SUBPARTS (vectype_in
));
5600 gcc_assert (ncopies
>= 1);
5602 vec_mode
= TYPE_MODE (vectype_in
);
5604 if (code
== COND_EXPR
)
5606 /* Only call during the analysis stage, otherwise we'll lose
5608 if (!vec_stmt
&& !vectorizable_condition (stmt
, gsi
, NULL
,
5609 ops
[reduc_index
], 0, NULL
))
5611 if (dump_enabled_p ())
5612 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5613 "unsupported condition in reduction\n");
5619 /* 4. Supportable by target? */
5621 if (code
== LSHIFT_EXPR
|| code
== RSHIFT_EXPR
5622 || code
== LROTATE_EXPR
|| code
== RROTATE_EXPR
)
5624 /* Shifts and rotates are only supported by vectorizable_shifts,
5625 not vectorizable_reduction. */
5626 if (dump_enabled_p ())
5627 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5628 "unsupported shift or rotation.\n");
5632 /* 4.1. check support for the operation in the loop */
5633 optab
= optab_for_tree_code (code
, vectype_in
, optab_default
);
5636 if (dump_enabled_p ())
5637 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5643 if (optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
5645 if (dump_enabled_p ())
5646 dump_printf (MSG_NOTE
, "op not supported by target.\n");
5648 if (GET_MODE_SIZE (vec_mode
) != UNITS_PER_WORD
5649 || LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
5650 < vect_min_worthwhile_factor (code
))
5653 if (dump_enabled_p ())
5654 dump_printf (MSG_NOTE
, "proceeding using word mode.\n");
5657 /* Worthwhile without SIMD support? */
5658 if (!VECTOR_MODE_P (TYPE_MODE (vectype_in
))
5659 && LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
5660 < vect_min_worthwhile_factor (code
))
5662 if (dump_enabled_p ())
5663 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5664 "not worthwhile without SIMD support.\n");
5670 /* 4.2. Check support for the epilog operation.
5672 If STMT represents a reduction pattern, then the type of the
5673 reduction variable may be different than the type of the rest
5674 of the arguments. For example, consider the case of accumulation
5675 of shorts into an int accumulator; The original code:
5676 S1: int_a = (int) short_a;
5677 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
5680 STMT: int_acc = widen_sum <short_a, int_acc>
5683 1. The tree-code that is used to create the vector operation in the
5684 epilog code (that reduces the partial results) is not the
5685 tree-code of STMT, but is rather the tree-code of the original
5686 stmt from the pattern that STMT is replacing. I.e, in the example
5687 above we want to use 'widen_sum' in the loop, but 'plus' in the
5689 2. The type (mode) we use to check available target support
5690 for the vector operation to be created in the *epilog*, is
5691 determined by the type of the reduction variable (in the example
5692 above we'd check this: optab_handler (plus_optab, vect_int_mode])).
5693 However the type (mode) we use to check available target support
5694 for the vector operation to be created *inside the loop*, is
5695 determined by the type of the other arguments to STMT (in the
5696 example we'd check this: optab_handler (widen_sum_optab,
5699 This is contrary to "regular" reductions, in which the types of all
5700 the arguments are the same as the type of the reduction variable.
5701 For "regular" reductions we can therefore use the same vector type
5702 (and also the same tree-code) when generating the epilog code and
5703 when generating the code inside the loop. */
5707 /* This is a reduction pattern: get the vectype from the type of the
5708 reduction variable, and get the tree-code from orig_stmt. */
5709 gcc_assert (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
5710 == TREE_CODE_REDUCTION
);
5711 orig_code
= gimple_assign_rhs_code (orig_stmt
);
5712 gcc_assert (vectype_out
);
5713 vec_mode
= TYPE_MODE (vectype_out
);
5717 /* Regular reduction: use the same vectype and tree-code as used for
5718 the vector code inside the loop can be used for the epilog code. */
5721 if (code
== MINUS_EXPR
)
5722 orig_code
= PLUS_EXPR
;
5724 /* For simple condition reductions, replace with the actual expression
5725 we want to base our reduction around. */
5726 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
5727 == INTEGER_INDUC_COND_REDUCTION
)
5728 orig_code
= MAX_EXPR
;
5733 def_bb
= gimple_bb (reduc_def_stmt
);
5734 def_stmt_loop
= def_bb
->loop_father
;
5735 def_arg
= PHI_ARG_DEF_FROM_EDGE (reduc_def_stmt
,
5736 loop_preheader_edge (def_stmt_loop
));
5737 if (TREE_CODE (def_arg
) == SSA_NAME
5738 && (def_arg_stmt
= SSA_NAME_DEF_STMT (def_arg
))
5739 && gimple_code (def_arg_stmt
) == GIMPLE_PHI
5740 && flow_bb_inside_loop_p (outer_loop
, gimple_bb (def_arg_stmt
))
5741 && vinfo_for_stmt (def_arg_stmt
)
5742 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_arg_stmt
))
5743 == vect_double_reduction_def
)
5744 double_reduc
= true;
5747 epilog_reduc_code
= ERROR_MARK
;
5749 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == TREE_CODE_REDUCTION
5750 || STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
5751 == INTEGER_INDUC_COND_REDUCTION
)
5753 if (reduction_code_for_scalar_code (orig_code
, &epilog_reduc_code
))
5755 reduc_optab
= optab_for_tree_code (epilog_reduc_code
, vectype_out
,
5759 if (dump_enabled_p ())
5760 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5761 "no optab for reduction.\n");
5763 epilog_reduc_code
= ERROR_MARK
;
5765 else if (optab_handler (reduc_optab
, vec_mode
) == CODE_FOR_nothing
)
5767 if (dump_enabled_p ())
5768 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5769 "reduc op not supported by target.\n");
5771 epilog_reduc_code
= ERROR_MARK
;
5774 /* When epilog_reduc_code is ERROR_MARK then a reduction will be
5775 generated in the epilog using multiple expressions. This does not
5776 work for condition reductions. */
5777 if (epilog_reduc_code
== ERROR_MARK
5778 && STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
5779 == INTEGER_INDUC_COND_REDUCTION
)
5781 if (dump_enabled_p ())
5782 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5783 "no reduc code for scalar code.\n");
5789 if (!nested_cycle
|| double_reduc
)
5791 if (dump_enabled_p ())
5792 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5793 "no reduc code for scalar code.\n");
5801 int scalar_precision
= GET_MODE_PRECISION (TYPE_MODE (scalar_type
));
5802 cr_index_scalar_type
= make_unsigned_type (scalar_precision
);
5803 cr_index_vector_type
= build_vector_type
5804 (cr_index_scalar_type
, TYPE_VECTOR_SUBPARTS (vectype_out
));
5806 epilog_reduc_code
= REDUC_MAX_EXPR
;
5807 optab
= optab_for_tree_code (REDUC_MAX_EXPR
, cr_index_vector_type
,
5809 if (optab_handler (optab
, TYPE_MODE (cr_index_vector_type
))
5810 == CODE_FOR_nothing
)
5812 if (dump_enabled_p ())
5813 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5814 "reduc max op not supported by target.\n");
5820 || STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
5821 || STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
)
5822 == INTEGER_INDUC_COND_REDUCTION
)
5825 if (dump_enabled_p ())
5826 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5827 "multiple types in double reduction or condition "
5832 /* In case of widenning multiplication by a constant, we update the type
5833 of the constant to be the type of the other operand. We check that the
5834 constant fits the type in the pattern recognition pass. */
5835 if (code
== DOT_PROD_EXPR
5836 && !types_compatible_p (TREE_TYPE (ops
[0]), TREE_TYPE (ops
[1])))
5838 if (TREE_CODE (ops
[0]) == INTEGER_CST
)
5839 ops
[0] = fold_convert (TREE_TYPE (ops
[1]), ops
[0]);
5840 else if (TREE_CODE (ops
[1]) == INTEGER_CST
)
5841 ops
[1] = fold_convert (TREE_TYPE (ops
[0]), ops
[1]);
5844 if (dump_enabled_p ())
5845 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5846 "invalid types in dot-prod\n");
5852 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
)
5856 if (! max_loop_iterations (loop
, &ni
))
5858 if (dump_enabled_p ())
5859 dump_printf_loc (MSG_NOTE
, vect_location
,
5860 "loop count not known, cannot create cond "
5864 /* Convert backedges to iterations. */
5867 /* The additional index will be the same type as the condition. Check
5868 that the loop can fit into this less one (because we'll use up the
5869 zero slot for when there are no matches). */
5870 tree max_index
= TYPE_MAX_VALUE (cr_index_scalar_type
);
5871 if (wi::geu_p (ni
, wi::to_widest (max_index
)))
5873 if (dump_enabled_p ())
5874 dump_printf_loc (MSG_NOTE
, vect_location
,
5875 "loop size is greater than data size.\n");
5880 if (!vec_stmt
) /* transformation not required. */
5883 && !vect_model_reduction_cost (stmt_info
, epilog_reduc_code
, ncopies
,
5886 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
5892 if (dump_enabled_p ())
5893 dump_printf_loc (MSG_NOTE
, vect_location
, "transform reduction.\n");
5895 /* FORNOW: Multiple types are not supported for condition. */
5896 if (code
== COND_EXPR
)
5897 gcc_assert (ncopies
== 1);
5899 /* Create the destination vector */
5900 vec_dest
= vect_create_destination_var (scalar_dest
, vectype_out
);
5902 /* In case the vectorization factor (VF) is bigger than the number
5903 of elements that we can fit in a vectype (nunits), we have to generate
5904 more than one vector stmt - i.e - we need to "unroll" the
5905 vector stmt by a factor VF/nunits. For more details see documentation
5906 in vectorizable_operation. */
5908 /* If the reduction is used in an outer loop we need to generate
5909 VF intermediate results, like so (e.g. for ncopies=2):
5914 (i.e. we generate VF results in 2 registers).
5915 In this case we have a separate def-use cycle for each copy, and therefore
5916 for each copy we get the vector def for the reduction variable from the
5917 respective phi node created for this copy.
5919 Otherwise (the reduction is unused in the loop nest), we can combine
5920 together intermediate results, like so (e.g. for ncopies=2):
5924 (i.e. we generate VF/2 results in a single register).
5925 In this case for each copy we get the vector def for the reduction variable
5926 from the vectorized reduction operation generated in the previous iteration.
5929 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
)
5931 single_defuse_cycle
= true;
5935 epilog_copies
= ncopies
;
5937 prev_stmt_info
= NULL
;
5938 prev_phi_info
= NULL
;
5940 vec_num
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
5944 vec_oprnds0
.create (1);
5945 if (op_type
== ternary_op
)
5946 vec_oprnds1
.create (1);
5949 phis
.create (vec_num
);
5950 vect_defs
.create (vec_num
);
5952 vect_defs
.quick_push (NULL_TREE
);
5954 for (j
= 0; j
< ncopies
; j
++)
5956 if (j
== 0 || !single_defuse_cycle
)
5958 for (i
= 0; i
< vec_num
; i
++)
5960 /* Create the reduction-phi that defines the reduction
5962 new_phi
= create_phi_node (vec_dest
, loop
->header
);
5963 set_vinfo_for_stmt (new_phi
,
5964 new_stmt_vec_info (new_phi
, loop_vinfo
));
5965 if (j
== 0 || slp_node
)
5966 phis
.quick_push (new_phi
);
5970 if (code
== COND_EXPR
)
5972 gcc_assert (!slp_node
);
5973 vectorizable_condition (stmt
, gsi
, vec_stmt
,
5974 PHI_RESULT (phis
[0]),
5976 /* Multiple types are not supported for condition. */
5983 op0
= ops
[!reduc_index
];
5984 if (op_type
== ternary_op
)
5986 if (reduc_index
== 0)
5993 vect_get_vec_defs (op0
, op1
, stmt
, &vec_oprnds0
, &vec_oprnds1
,
5997 loop_vec_def0
= vect_get_vec_def_for_operand (ops
[!reduc_index
],
5999 vec_oprnds0
.quick_push (loop_vec_def0
);
6000 if (op_type
== ternary_op
)
6002 loop_vec_def1
= vect_get_vec_def_for_operand (op1
, stmt
);
6003 vec_oprnds1
.quick_push (loop_vec_def1
);
6011 enum vect_def_type dt
;
6014 vect_is_simple_use (ops
[!reduc_index
], loop_vinfo
,
6016 loop_vec_def0
= vect_get_vec_def_for_stmt_copy (dt
,
6018 vec_oprnds0
[0] = loop_vec_def0
;
6019 if (op_type
== ternary_op
)
6021 vect_is_simple_use (op1
, loop_vinfo
, &dummy_stmt
, &dt
);
6022 loop_vec_def1
= vect_get_vec_def_for_stmt_copy (dt
,
6024 vec_oprnds1
[0] = loop_vec_def1
;
6028 if (single_defuse_cycle
)
6029 reduc_def
= gimple_assign_lhs (new_stmt
);
6031 STMT_VINFO_RELATED_STMT (prev_phi_info
) = new_phi
;
6034 FOR_EACH_VEC_ELT (vec_oprnds0
, i
, def0
)
6037 reduc_def
= PHI_RESULT (phis
[i
]);
6040 if (!single_defuse_cycle
|| j
== 0)
6041 reduc_def
= PHI_RESULT (new_phi
);
6044 def1
= ((op_type
== ternary_op
)
6045 ? vec_oprnds1
[i
] : NULL
);
6046 if (op_type
== binary_op
)
6048 if (reduc_index
== 0)
6049 expr
= build2 (code
, vectype_out
, reduc_def
, def0
);
6051 expr
= build2 (code
, vectype_out
, def0
, reduc_def
);
6055 if (reduc_index
== 0)
6056 expr
= build3 (code
, vectype_out
, reduc_def
, def0
, def1
);
6059 if (reduc_index
== 1)
6060 expr
= build3 (code
, vectype_out
, def0
, reduc_def
, def1
);
6062 expr
= build3 (code
, vectype_out
, def0
, def1
, reduc_def
);
6066 new_stmt
= gimple_build_assign (vec_dest
, expr
);
6067 new_temp
= make_ssa_name (vec_dest
, new_stmt
);
6068 gimple_assign_set_lhs (new_stmt
, new_temp
);
6069 vect_finish_stmt_generation (stmt
, new_stmt
, gsi
);
6073 SLP_TREE_VEC_STMTS (slp_node
).quick_push (new_stmt
);
6074 vect_defs
.quick_push (new_temp
);
6077 vect_defs
[0] = new_temp
;
6084 STMT_VINFO_VEC_STMT (stmt_info
) = *vec_stmt
= new_stmt
;
6086 STMT_VINFO_RELATED_STMT (prev_stmt_info
) = new_stmt
;
6088 prev_stmt_info
= vinfo_for_stmt (new_stmt
);
6089 prev_phi_info
= vinfo_for_stmt (new_phi
);
6092 tree indx_before_incr
, indx_after_incr
, cond_name
= NULL
;
6094 /* Finalize the reduction-phi (set its arguments) and create the
6095 epilog reduction code. */
6096 if ((!single_defuse_cycle
|| code
== COND_EXPR
) && !slp_node
)
6098 new_temp
= gimple_assign_lhs (*vec_stmt
);
6099 vect_defs
[0] = new_temp
;
6101 /* For cond reductions we want to create a new vector (INDEX_COND_EXPR)
6102 which is updated with the current index of the loop for every match of
6103 the original loop's cond_expr (VEC_STMT). This results in a vector
6104 containing the last time the condition passed for that vector lane.
6105 The first match will be a 1 to allow 0 to be used for non-matching
6106 indexes. If there are no matches at all then the vector will be all
6108 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info
) == COND_REDUCTION
)
6110 int nunits_out
= TYPE_VECTOR_SUBPARTS (vectype_out
);
6113 gcc_assert (gimple_assign_rhs_code (*vec_stmt
) == VEC_COND_EXPR
);
6115 /* First we create a simple vector induction variable which starts
6116 with the values {1,2,3,...} (SERIES_VECT) and increments by the
6117 vector size (STEP). */
6119 /* Create a {1,2,3,...} vector. */
6120 tree
*vtemp
= XALLOCAVEC (tree
, nunits_out
);
6121 for (k
= 0; k
< nunits_out
; ++k
)
6122 vtemp
[k
] = build_int_cst (cr_index_scalar_type
, k
+ 1);
6123 tree series_vect
= build_vector (cr_index_vector_type
, vtemp
);
6125 /* Create a vector of the step value. */
6126 tree step
= build_int_cst (cr_index_scalar_type
, nunits_out
);
6127 tree vec_step
= build_vector_from_val (cr_index_vector_type
, step
);
6129 /* Create an induction variable. */
6130 gimple_stmt_iterator incr_gsi
;
6132 standard_iv_increment_position (loop
, &incr_gsi
, &insert_after
);
6133 create_iv (series_vect
, vec_step
, NULL_TREE
, loop
, &incr_gsi
,
6134 insert_after
, &indx_before_incr
, &indx_after_incr
);
6136 /* Next create a new phi node vector (NEW_PHI_TREE) which starts
6137 filled with zeros (VEC_ZERO). */
6139 /* Create a vector of 0s. */
6140 tree zero
= build_zero_cst (cr_index_scalar_type
);
6141 tree vec_zero
= build_vector_from_val (cr_index_vector_type
, zero
);
6143 /* Create a vector phi node. */
6144 tree new_phi_tree
= make_ssa_name (cr_index_vector_type
);
6145 new_phi
= create_phi_node (new_phi_tree
, loop
->header
);
6146 set_vinfo_for_stmt (new_phi
,
6147 new_stmt_vec_info (new_phi
, loop_vinfo
));
6148 add_phi_arg (new_phi
, vec_zero
, loop_preheader_edge (loop
),
6151 /* Now take the condition from the loops original cond_expr
6152 (VEC_STMT) and produce a new cond_expr (INDEX_COND_EXPR) which for
6153 every match uses values from the induction variable
6154 (INDEX_BEFORE_INCR) otherwise uses values from the phi node
6156 Finally, we update the phi (NEW_PHI_TREE) to take the value of
6157 the new cond_expr (INDEX_COND_EXPR). */
6159 /* Turn the condition from vec_stmt into an ssa name. */
6160 gimple_stmt_iterator vec_stmt_gsi
= gsi_for_stmt (*vec_stmt
);
6161 tree ccompare
= gimple_assign_rhs1 (*vec_stmt
);
6162 tree ccompare_name
= make_ssa_name (TREE_TYPE (ccompare
));
6163 gimple
*ccompare_stmt
= gimple_build_assign (ccompare_name
,
6165 gsi_insert_before (&vec_stmt_gsi
, ccompare_stmt
, GSI_SAME_STMT
);
6166 gimple_assign_set_rhs1 (*vec_stmt
, ccompare_name
);
6167 update_stmt (*vec_stmt
);
6169 /* Create a conditional, where the condition is taken from vec_stmt
6170 (CCOMPARE_NAME), then is the induction index (INDEX_BEFORE_INCR)
6171 and else is the phi (NEW_PHI_TREE). */
6172 tree index_cond_expr
= build3 (VEC_COND_EXPR
, cr_index_vector_type
,
6173 ccompare_name
, indx_before_incr
,
6175 cond_name
= make_ssa_name (cr_index_vector_type
);
6176 gimple
*index_condition
= gimple_build_assign (cond_name
,
6178 gsi_insert_before (&incr_gsi
, index_condition
, GSI_SAME_STMT
);
6179 stmt_vec_info index_vec_info
= new_stmt_vec_info (index_condition
,
6181 STMT_VINFO_VECTYPE (index_vec_info
) = cr_index_vector_type
;
6182 set_vinfo_for_stmt (index_condition
, index_vec_info
);
6184 /* Update the phi with the vec cond. */
6185 add_phi_arg (new_phi
, cond_name
, loop_latch_edge (loop
),
6190 vect_create_epilog_for_reduction (vect_defs
, stmt
, epilog_copies
,
6191 epilog_reduc_code
, phis
, reduc_index
,
6192 double_reduc
, slp_node
, cond_name
);
6197 /* Function vect_min_worthwhile_factor.
6199 For a loop where we could vectorize the operation indicated by CODE,
6200 return the minimum vectorization factor that makes it worthwhile
6201 to use generic vectors. */
6203 vect_min_worthwhile_factor (enum tree_code code
)
6224 /* Function vectorizable_induction
6226 Check if PHI performs an induction computation that can be vectorized.
6227 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
6228 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
6229 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
6232 vectorizable_induction (gimple
*phi
,
6233 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
6236 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
6237 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
6238 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
6239 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
6240 int nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
6241 int ncopies
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) / nunits
;
6244 gcc_assert (ncopies
>= 1);
6245 /* FORNOW. These restrictions should be relaxed. */
6246 if (nested_in_vect_loop_p (loop
, phi
))
6248 imm_use_iterator imm_iter
;
6249 use_operand_p use_p
;
6256 if (dump_enabled_p ())
6257 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6258 "multiple types in nested loop.\n");
6263 latch_e
= loop_latch_edge (loop
->inner
);
6264 loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
6265 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
6267 gimple
*use_stmt
= USE_STMT (use_p
);
6268 if (is_gimple_debug (use_stmt
))
6271 if (!flow_bb_inside_loop_p (loop
->inner
, gimple_bb (use_stmt
)))
6273 exit_phi
= use_stmt
;
6279 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
6280 if (!(STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
6281 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
)))
6283 if (dump_enabled_p ())
6284 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6285 "inner-loop induction only used outside "
6286 "of the outer vectorized loop.\n");
6292 if (!STMT_VINFO_RELEVANT_P (stmt_info
))
6295 /* FORNOW: SLP not supported. */
6296 if (STMT_SLP_TYPE (stmt_info
))
6299 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
);
6301 if (gimple_code (phi
) != GIMPLE_PHI
)
6304 if (!vec_stmt
) /* transformation not required. */
6306 STMT_VINFO_TYPE (stmt_info
) = induc_vec_info_type
;
6307 if (dump_enabled_p ())
6308 dump_printf_loc (MSG_NOTE
, vect_location
,
6309 "=== vectorizable_induction ===\n");
6310 vect_model_induction_cost (stmt_info
, ncopies
);
6316 if (dump_enabled_p ())
6317 dump_printf_loc (MSG_NOTE
, vect_location
, "transform induction phi.\n");
6319 vec_def
= get_initial_def_for_induction (phi
);
6320 *vec_stmt
= SSA_NAME_DEF_STMT (vec_def
);
6324 /* Function vectorizable_live_operation.
6326 STMT computes a value that is used outside the loop. Check if
6327 it can be supported. */
6330 vectorizable_live_operation (gimple
*stmt
,
6331 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
6334 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
6335 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
6336 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
6341 gcc_assert (STMT_VINFO_LIVE_P (stmt_info
));
6343 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_reduction_def
)
6346 if (!is_gimple_assign (stmt
))
6348 if (gimple_call_internal_p (stmt
)
6349 && gimple_call_internal_fn (stmt
) == IFN_GOMP_SIMD_LANE
6350 && gimple_call_lhs (stmt
)
6352 && TREE_CODE (gimple_call_arg (stmt
, 0)) == SSA_NAME
6354 == SSA_NAME_VAR (gimple_call_arg (stmt
, 0)))
6356 edge e
= single_exit (loop
);
6357 basic_block merge_bb
= e
->dest
;
6358 imm_use_iterator imm_iter
;
6359 use_operand_p use_p
;
6360 tree lhs
= gimple_call_lhs (stmt
);
6362 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
6364 gimple
*use_stmt
= USE_STMT (use_p
);
6365 if (gimple_code (use_stmt
) == GIMPLE_PHI
6366 && gimple_bb (use_stmt
) == merge_bb
)
6371 = build_int_cst (unsigned_type_node
,
6372 loop_vinfo
->vectorization_factor
- 1);
6373 SET_PHI_ARG_DEF (use_stmt
, e
->dest_idx
, vfm1
);
6383 if (TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
6386 /* FORNOW. CHECKME. */
6387 if (nested_in_vect_loop_p (loop
, stmt
))
6390 /* FORNOW: support only if all uses are invariant. This means
6391 that the scalar operations can remain in place, unvectorized.
6392 The original last scalar value that they compute will be used. */
6393 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
6395 enum vect_def_type dt
= vect_uninitialized_def
;
6397 if (!vect_is_simple_use (op
, loop_vinfo
, &def_stmt
, &dt
))
6399 if (dump_enabled_p ())
6400 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
6401 "use not simple.\n");
6405 if (dt
!= vect_external_def
&& dt
!= vect_constant_def
)
6409 /* No transformation is required for the cases we currently support. */
6413 /* Kill any debug uses outside LOOP of SSA names defined in STMT. */
6416 vect_loop_kill_debug_uses (struct loop
*loop
, gimple
*stmt
)
6418 ssa_op_iter op_iter
;
6419 imm_use_iterator imm_iter
;
6420 def_operand_p def_p
;
6423 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
6425 FOR_EACH_IMM_USE_STMT (ustmt
, imm_iter
, DEF_FROM_PTR (def_p
))
6429 if (!is_gimple_debug (ustmt
))
6432 bb
= gimple_bb (ustmt
);
6434 if (!flow_bb_inside_loop_p (loop
, bb
))
6436 if (gimple_debug_bind_p (ustmt
))
6438 if (dump_enabled_p ())
6439 dump_printf_loc (MSG_NOTE
, vect_location
,
6440 "killing debug use\n");
6442 gimple_debug_bind_reset_value (ustmt
);
6443 update_stmt (ustmt
);
6453 /* This function builds ni_name = number of iterations. Statements
6454 are emitted on the loop preheader edge. */
6457 vect_build_loop_niters (loop_vec_info loop_vinfo
)
6459 tree ni
= unshare_expr (LOOP_VINFO_NITERS (loop_vinfo
));
6460 if (TREE_CODE (ni
) == INTEGER_CST
)
6465 gimple_seq stmts
= NULL
;
6466 edge pe
= loop_preheader_edge (LOOP_VINFO_LOOP (loop_vinfo
));
6468 var
= create_tmp_var (TREE_TYPE (ni
), "niters");
6469 ni_name
= force_gimple_operand (ni
, &stmts
, false, var
);
6471 gsi_insert_seq_on_edge_immediate (pe
, stmts
);
6478 /* This function generates the following statements:
6480 ni_name = number of iterations loop executes
6481 ratio = ni_name / vf
6482 ratio_mult_vf_name = ratio * vf
6484 and places them on the loop preheader edge. */
6487 vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo
,
6489 tree
*ratio_mult_vf_name_ptr
,
6490 tree
*ratio_name_ptr
)
6492 tree ni_minus_gap_name
;
6495 tree ratio_mult_vf_name
;
6496 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
6497 edge pe
= loop_preheader_edge (LOOP_VINFO_LOOP (loop_vinfo
));
6500 log_vf
= build_int_cst (TREE_TYPE (ni_name
), exact_log2 (vf
));
6502 /* If epilogue loop is required because of data accesses with gaps, we
6503 subtract one iteration from the total number of iterations here for
6504 correct calculation of RATIO. */
6505 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
))
6507 ni_minus_gap_name
= fold_build2 (MINUS_EXPR
, TREE_TYPE (ni_name
),
6509 build_one_cst (TREE_TYPE (ni_name
)));
6510 if (!is_gimple_val (ni_minus_gap_name
))
6512 var
= create_tmp_var (TREE_TYPE (ni_name
), "ni_gap");
6513 gimple
*stmts
= NULL
;
6514 ni_minus_gap_name
= force_gimple_operand (ni_minus_gap_name
, &stmts
,
6516 gsi_insert_seq_on_edge_immediate (pe
, stmts
);
6520 ni_minus_gap_name
= ni_name
;
6522 /* Create: ratio = ni >> log2(vf) */
6523 /* ??? As we have ni == number of latch executions + 1, ni could
6524 have overflown to zero. So avoid computing ratio based on ni
6525 but compute it using the fact that we know ratio will be at least
6526 one, thus via (ni - vf) >> log2(vf) + 1. */
6528 = fold_build2 (PLUS_EXPR
, TREE_TYPE (ni_name
),
6529 fold_build2 (RSHIFT_EXPR
, TREE_TYPE (ni_name
),
6530 fold_build2 (MINUS_EXPR
, TREE_TYPE (ni_name
),
6533 (TREE_TYPE (ni_name
), vf
)),
6535 build_int_cst (TREE_TYPE (ni_name
), 1));
6536 if (!is_gimple_val (ratio_name
))
6538 var
= create_tmp_var (TREE_TYPE (ni_name
), "bnd");
6539 gimple
*stmts
= NULL
;
6540 ratio_name
= force_gimple_operand (ratio_name
, &stmts
, true, var
);
6541 gsi_insert_seq_on_edge_immediate (pe
, stmts
);
6543 *ratio_name_ptr
= ratio_name
;
6545 /* Create: ratio_mult_vf = ratio << log2 (vf). */
6547 if (ratio_mult_vf_name_ptr
)
6549 ratio_mult_vf_name
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (ratio_name
),
6550 ratio_name
, log_vf
);
6551 if (!is_gimple_val (ratio_mult_vf_name
))
6553 var
= create_tmp_var (TREE_TYPE (ni_name
), "ratio_mult_vf");
6554 gimple
*stmts
= NULL
;
6555 ratio_mult_vf_name
= force_gimple_operand (ratio_mult_vf_name
, &stmts
,
6557 gsi_insert_seq_on_edge_immediate (pe
, stmts
);
6559 *ratio_mult_vf_name_ptr
= ratio_mult_vf_name
;
6566 /* Function vect_transform_loop.
6568 The analysis phase has determined that the loop is vectorizable.
6569 Vectorize the loop - created vectorized stmts to replace the scalar
6570 stmts in the loop, and update the loop exit condition. */
6573 vect_transform_loop (loop_vec_info loop_vinfo
)
6575 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
6576 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
6577 int nbbs
= loop
->num_nodes
;
6580 int vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
6582 bool slp_scheduled
= false;
6583 gimple
*stmt
, *pattern_stmt
;
6584 gimple_seq pattern_def_seq
= NULL
;
6585 gimple_stmt_iterator pattern_def_si
= gsi_none ();
6586 bool transform_pattern_stmt
= false;
6587 bool check_profitability
= false;
6589 /* Record number of iterations before we started tampering with the profile. */
6590 gcov_type expected_iterations
= expected_loop_iterations_unbounded (loop
);
6592 if (dump_enabled_p ())
6593 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vec_transform_loop ===\n");
6595 /* If profile is inprecise, we have chance to fix it up. */
6596 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
6597 expected_iterations
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
6599 /* Use the more conservative vectorization threshold. If the number
6600 of iterations is constant assume the cost check has been performed
6601 by our caller. If the threshold makes all loops profitable that
6602 run at least the vectorization factor number of times checking
6603 is pointless, too. */
6604 th
= LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo
);
6605 if (th
>= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) - 1
6606 && !LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
6608 if (dump_enabled_p ())
6609 dump_printf_loc (MSG_NOTE
, vect_location
,
6610 "Profitability threshold is %d loop iterations.\n",
6612 check_profitability
= true;
6615 /* Version the loop first, if required, so the profitability check
6618 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
6619 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
6621 vect_loop_versioning (loop_vinfo
, th
, check_profitability
);
6622 check_profitability
= false;
6625 tree ni_name
= vect_build_loop_niters (loop_vinfo
);
6626 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo
) = ni_name
;
6628 /* Peel the loop if there are data refs with unknown alignment.
6629 Only one data ref with unknown store is allowed. */
6631 if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
))
6633 vect_do_peeling_for_alignment (loop_vinfo
, ni_name
,
6634 th
, check_profitability
);
6635 check_profitability
= false;
6636 /* The above adjusts LOOP_VINFO_NITERS, so cause ni_name to
6638 ni_name
= NULL_TREE
;
6641 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
6642 compile time constant), or it is a constant that doesn't divide by the
6643 vectorization factor, then an epilog loop needs to be created.
6644 We therefore duplicate the loop: the original loop will be vectorized,
6645 and will compute the first (n/VF) iterations. The second copy of the loop
6646 will remain scalar and will compute the remaining (n%VF) iterations.
6647 (VF is the vectorization factor). */
6649 if (LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
)
6650 || LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
))
6654 ni_name
= vect_build_loop_niters (loop_vinfo
);
6655 vect_generate_tmps_on_preheader (loop_vinfo
, ni_name
, &ratio_mult_vf
,
6657 vect_do_peeling_for_loop_bound (loop_vinfo
, ni_name
, ratio_mult_vf
,
6658 th
, check_profitability
);
6660 else if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
6661 ratio
= build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo
)),
6662 LOOP_VINFO_INT_NITERS (loop_vinfo
) / vectorization_factor
);
6666 ni_name
= vect_build_loop_niters (loop_vinfo
);
6667 vect_generate_tmps_on_preheader (loop_vinfo
, ni_name
, NULL
, &ratio
);
6670 /* 1) Make sure the loop header has exactly two entries
6671 2) Make sure we have a preheader basic block. */
6673 gcc_assert (EDGE_COUNT (loop
->header
->preds
) == 2);
6675 split_edge (loop_preheader_edge (loop
));
6677 /* FORNOW: the vectorizer supports only loops which body consist
6678 of one basic block (header + empty latch). When the vectorizer will
6679 support more involved loop forms, the order by which the BBs are
6680 traversed need to be reconsidered. */
6682 for (i
= 0; i
< nbbs
; i
++)
6684 basic_block bb
= bbs
[i
];
6685 stmt_vec_info stmt_info
;
6687 for (gphi_iterator si
= gsi_start_phis (bb
); !gsi_end_p (si
);
6690 gphi
*phi
= si
.phi ();
6691 if (dump_enabled_p ())
6693 dump_printf_loc (MSG_NOTE
, vect_location
,
6694 "------>vectorizing phi: ");
6695 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
6696 dump_printf (MSG_NOTE
, "\n");
6698 stmt_info
= vinfo_for_stmt (phi
);
6702 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
6703 vect_loop_kill_debug_uses (loop
, phi
);
6705 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
6706 && !STMT_VINFO_LIVE_P (stmt_info
))
6709 if (STMT_VINFO_VECTYPE (stmt_info
)
6710 && (TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
))
6711 != (unsigned HOST_WIDE_INT
) vectorization_factor
)
6712 && dump_enabled_p ())
6713 dump_printf_loc (MSG_NOTE
, vect_location
, "multiple-types.\n");
6715 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
6717 if (dump_enabled_p ())
6718 dump_printf_loc (MSG_NOTE
, vect_location
, "transform phi.\n");
6719 vect_transform_stmt (phi
, NULL
, NULL
, NULL
, NULL
);
6723 pattern_stmt
= NULL
;
6724 for (gimple_stmt_iterator si
= gsi_start_bb (bb
);
6725 !gsi_end_p (si
) || transform_pattern_stmt
;)
6729 if (transform_pattern_stmt
)
6730 stmt
= pattern_stmt
;
6733 stmt
= gsi_stmt (si
);
6734 /* During vectorization remove existing clobber stmts. */
6735 if (gimple_clobber_p (stmt
))
6737 unlink_stmt_vdef (stmt
);
6738 gsi_remove (&si
, true);
6739 release_defs (stmt
);
6744 if (dump_enabled_p ())
6746 dump_printf_loc (MSG_NOTE
, vect_location
,
6747 "------>vectorizing statement: ");
6748 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
6749 dump_printf (MSG_NOTE
, "\n");
6752 stmt_info
= vinfo_for_stmt (stmt
);
6754 /* vector stmts created in the outer-loop during vectorization of
6755 stmts in an inner-loop may not have a stmt_info, and do not
6756 need to be vectorized. */
6763 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
6764 vect_loop_kill_debug_uses (loop
, stmt
);
6766 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
6767 && !STMT_VINFO_LIVE_P (stmt_info
))
6769 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
6770 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
6771 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
6772 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
6774 stmt
= pattern_stmt
;
6775 stmt_info
= vinfo_for_stmt (stmt
);
6783 else if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
6784 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
6785 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
6786 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
6787 transform_pattern_stmt
= true;
6789 /* If pattern statement has def stmts, vectorize them too. */
6790 if (is_pattern_stmt_p (stmt_info
))
6792 if (pattern_def_seq
== NULL
)
6794 pattern_def_seq
= STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
);
6795 pattern_def_si
= gsi_start (pattern_def_seq
);
6797 else if (!gsi_end_p (pattern_def_si
))
6798 gsi_next (&pattern_def_si
);
6799 if (pattern_def_seq
!= NULL
)
6801 gimple
*pattern_def_stmt
= NULL
;
6802 stmt_vec_info pattern_def_stmt_info
= NULL
;
6804 while (!gsi_end_p (pattern_def_si
))
6806 pattern_def_stmt
= gsi_stmt (pattern_def_si
);
6807 pattern_def_stmt_info
6808 = vinfo_for_stmt (pattern_def_stmt
);
6809 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info
)
6810 || STMT_VINFO_LIVE_P (pattern_def_stmt_info
))
6812 gsi_next (&pattern_def_si
);
6815 if (!gsi_end_p (pattern_def_si
))
6817 if (dump_enabled_p ())
6819 dump_printf_loc (MSG_NOTE
, vect_location
,
6820 "==> vectorizing pattern def "
6822 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
6823 pattern_def_stmt
, 0);
6824 dump_printf (MSG_NOTE
, "\n");
6827 stmt
= pattern_def_stmt
;
6828 stmt_info
= pattern_def_stmt_info
;
6832 pattern_def_si
= gsi_none ();
6833 transform_pattern_stmt
= false;
6837 transform_pattern_stmt
= false;
6840 if (STMT_VINFO_VECTYPE (stmt_info
))
6844 TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
6845 if (!STMT_SLP_TYPE (stmt_info
)
6846 && nunits
!= (unsigned int) vectorization_factor
6847 && dump_enabled_p ())
6848 /* For SLP VF is set according to unrolling factor, and not
6849 to vector size, hence for SLP this print is not valid. */
6850 dump_printf_loc (MSG_NOTE
, vect_location
, "multiple-types.\n");
6853 /* SLP. Schedule all the SLP instances when the first SLP stmt is
6855 if (STMT_SLP_TYPE (stmt_info
))
6859 slp_scheduled
= true;
6861 if (dump_enabled_p ())
6862 dump_printf_loc (MSG_NOTE
, vect_location
,
6863 "=== scheduling SLP instances ===\n");
6865 vect_schedule_slp (loop_vinfo
);
6868 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
6869 if (!vinfo_for_stmt (stmt
) || PURE_SLP_STMT (stmt_info
))
6871 if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
6873 pattern_def_seq
= NULL
;
6880 /* -------- vectorize statement ------------ */
6881 if (dump_enabled_p ())
6882 dump_printf_loc (MSG_NOTE
, vect_location
, "transform statement.\n");
6884 grouped_store
= false;
6885 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, NULL
, NULL
);
6888 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
6890 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
6891 interleaving chain was completed - free all the stores in
6894 vect_remove_stores (GROUP_FIRST_ELEMENT (stmt_info
));
6898 /* Free the attached stmt_vec_info and remove the stmt. */
6899 gimple
*store
= gsi_stmt (si
);
6900 free_stmt_vec_info (store
);
6901 unlink_stmt_vdef (store
);
6902 gsi_remove (&si
, true);
6903 release_defs (store
);
6906 /* Stores can only appear at the end of pattern statements. */
6907 gcc_assert (!transform_pattern_stmt
);
6908 pattern_def_seq
= NULL
;
6910 else if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
6912 pattern_def_seq
= NULL
;
6918 slpeel_make_loop_iterate_ntimes (loop
, ratio
);
6920 /* Reduce loop iterations by the vectorization factor. */
6921 scale_loop_profile (loop
, GCOV_COMPUTE_SCALE (1, vectorization_factor
),
6922 expected_iterations
/ vectorization_factor
);
6923 loop
->nb_iterations_upper_bound
6924 = wi::udiv_floor (loop
->nb_iterations_upper_bound
, vectorization_factor
);
6925 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
6926 && loop
->nb_iterations_upper_bound
!= 0)
6927 loop
->nb_iterations_upper_bound
= loop
->nb_iterations_upper_bound
- 1;
6928 if (loop
->any_estimate
)
6930 loop
->nb_iterations_estimate
6931 = wi::udiv_floor (loop
->nb_iterations_estimate
, vectorization_factor
);
6932 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
6933 && loop
->nb_iterations_estimate
!= 0)
6934 loop
->nb_iterations_estimate
= loop
->nb_iterations_estimate
- 1;
6937 if (dump_enabled_p ())
6939 dump_printf_loc (MSG_NOTE
, vect_location
,
6940 "LOOP VECTORIZED\n");
6942 dump_printf_loc (MSG_NOTE
, vect_location
,
6943 "OUTER LOOP VECTORIZED\n");
6944 dump_printf (MSG_NOTE
, "\n");
6947 /* Free SLP instances here because otherwise stmt reference counting
6949 slp_instance instance
;
6950 FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (loop_vinfo
), i
, instance
)
6951 vect_free_slp_instance (instance
);
6952 LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).release ();
6955 /* The code below is trying to perform simple optimization - revert
6956 if-conversion for masked stores, i.e. if the mask of a store is zero
6957 do not perform it and all stored value producers also if possible.
6965 this transformation will produce the following semi-hammock:
6967 if (!mask__ifc__42.18_165 == { 0, 0, 0, 0, 0, 0, 0, 0 })
6969 vect__11.19_170 = MASK_LOAD (vectp_p1.20_168, 0B, mask__ifc__42.18_165);
6970 vect__12.22_172 = vect__11.19_170 + vect_cst__171;
6971 MASK_STORE (vectp_p1.23_175, 0B, mask__ifc__42.18_165, vect__12.22_172);
6972 vect__18.25_182 = MASK_LOAD (vectp_p3.26_180, 0B, mask__ifc__42.18_165);
6973 vect__19.28_184 = vect__18.25_182 + vect_cst__183;
6974 MASK_STORE (vectp_p2.29_187, 0B, mask__ifc__42.18_165, vect__19.28_184);
6979 optimize_mask_stores (struct loop
*loop
)
6981 basic_block
*bbs
= get_loop_body (loop
);
6982 unsigned nbbs
= loop
->num_nodes
;
6985 gimple_stmt_iterator gsi
;
6987 auto_vec
<gimple
*> worklist
;
6989 vect_location
= find_loop_location (loop
);
6990 /* Pick up all masked stores in loop if any. */
6991 for (i
= 0; i
< nbbs
; i
++)
6994 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
6997 stmt
= gsi_stmt (gsi
);
6998 if (is_gimple_call (stmt
)
6999 && gimple_call_internal_p (stmt
)
7000 && gimple_call_internal_fn (stmt
) == IFN_MASK_STORE
)
7001 worklist
.safe_push (stmt
);
7006 if (worklist
.is_empty ())
7009 /* Loop has masked stores. */
7010 while (!worklist
.is_empty ())
7012 gimple
*last
, *last_store
;
7015 basic_block store_bb
, join_bb
;
7016 gimple_stmt_iterator gsi_to
;
7017 tree vdef
, new_vdef
;
7022 last
= worklist
.pop ();
7023 mask
= gimple_call_arg (last
, 2);
7024 bb
= gimple_bb (last
);
7025 /* Create new bb. */
7026 e
= split_block (bb
, last
);
7028 store_bb
= create_empty_bb (bb
);
7029 add_bb_to_loop (store_bb
, loop
);
7030 e
->flags
= EDGE_TRUE_VALUE
;
7031 efalse
= make_edge (bb
, store_bb
, EDGE_FALSE_VALUE
);
7032 /* Put STORE_BB to likely part. */
7033 efalse
->probability
= PROB_UNLIKELY
;
7034 store_bb
->frequency
= PROB_ALWAYS
- EDGE_FREQUENCY (efalse
);
7035 make_edge (store_bb
, join_bb
, EDGE_FALLTHRU
);
7036 if (dom_info_available_p (CDI_DOMINATORS
))
7037 set_immediate_dominator (CDI_DOMINATORS
, store_bb
, bb
);
7038 if (dump_enabled_p ())
7039 dump_printf_loc (MSG_NOTE
, vect_location
,
7040 "Create new block %d to sink mask stores.",
7042 /* Create vector comparison with boolean result. */
7043 vectype
= TREE_TYPE (mask
);
7044 zero
= build_zero_cst (vectype
);
7045 stmt
= gimple_build_cond (EQ_EXPR
, mask
, zero
, NULL_TREE
, NULL_TREE
);
7046 gsi
= gsi_last_bb (bb
);
7047 gsi_insert_after (&gsi
, stmt
, GSI_SAME_STMT
);
7048 /* Create new PHI node for vdef of the last masked store:
7049 .MEM_2 = VDEF <.MEM_1>
7050 will be converted to
7051 .MEM.3 = VDEF <.MEM_1>
7052 and new PHI node will be created in join bb
7053 .MEM_2 = PHI <.MEM_1, .MEM_3>
7055 vdef
= gimple_vdef (last
);
7056 new_vdef
= make_ssa_name (gimple_vop (cfun
), last
);
7057 gimple_set_vdef (last
, new_vdef
);
7058 phi
= create_phi_node (vdef
, join_bb
);
7059 add_phi_arg (phi
, new_vdef
, EDGE_SUCC (store_bb
, 0), UNKNOWN_LOCATION
);
7061 /* Put all masked stores with the same mask to STORE_BB if possible. */
7064 gimple_stmt_iterator gsi_from
;
7065 gimple
*stmt1
= NULL
;
7067 /* Move masked store to STORE_BB. */
7069 gsi
= gsi_for_stmt (last
);
7071 /* Shift GSI to the previous stmt for further traversal. */
7073 gsi_to
= gsi_start_bb (store_bb
);
7074 gsi_move_before (&gsi_from
, &gsi_to
);
7075 /* Setup GSI_TO to the non-empty block start. */
7076 gsi_to
= gsi_start_bb (store_bb
);
7077 if (dump_enabled_p ())
7079 dump_printf_loc (MSG_NOTE
, vect_location
,
7080 "Move stmt to created bb\n");
7081 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, last
, 0);
7083 /* Move all stored value producers if possible. */
7084 while (!gsi_end_p (gsi
))
7087 imm_use_iterator imm_iter
;
7088 use_operand_p use_p
;
7091 /* Skip debug statements. */
7092 if (is_gimple_debug (gsi_stmt (gsi
)))
7094 stmt1
= gsi_stmt (gsi
);
7095 /* Do not consider statements writing to memory or having
7096 volatile operand. */
7097 if (gimple_vdef (stmt1
)
7098 || gimple_has_volatile_ops (stmt1
))
7102 lhs
= gimple_get_lhs (stmt1
);
7106 /* LHS of vectorized stmt must be SSA_NAME. */
7107 if (TREE_CODE (lhs
) != SSA_NAME
)
7110 if (!VECTOR_TYPE_P (TREE_TYPE (lhs
)))
7112 /* Remove dead scalar statement. */
7113 if (has_zero_uses (lhs
))
7115 gsi_remove (&gsi_from
, true);
7120 /* Check that LHS does not have uses outside of STORE_BB. */
7122 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
7125 use_stmt
= USE_STMT (use_p
);
7126 if (is_gimple_debug (use_stmt
))
7128 if (gimple_bb (use_stmt
) != store_bb
)
7137 if (gimple_vuse (stmt1
)
7138 && gimple_vuse (stmt1
) != gimple_vuse (last_store
))
7141 /* Can move STMT1 to STORE_BB. */
7142 if (dump_enabled_p ())
7144 dump_printf_loc (MSG_NOTE
, vect_location
,
7145 "Move stmt to created bb\n");
7146 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt1
, 0);
7148 gsi_move_before (&gsi_from
, &gsi_to
);
7149 /* Shift GSI_TO for further insertion. */
7152 /* Put other masked stores with the same mask to STORE_BB. */
7153 if (worklist
.is_empty ()
7154 || gimple_call_arg (worklist
.last (), 2) != mask
7155 || worklist
.last () != stmt1
)
7157 last
= worklist
.pop ();
7159 add_phi_arg (phi
, gimple_vuse (last_store
), e
, UNKNOWN_LOCATION
);