2 Copyright (C) 2003-2013 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"
28 #include "stor-layout.h"
29 #include "basic-block.h"
30 #include "gimple-pretty-print.h"
31 #include "tree-ssa-alias.h"
32 #include "internal-fn.h"
33 #include "gimple-expr.h"
37 #include "gimple-iterator.h"
38 #include "gimplify-me.h"
39 #include "gimple-ssa.h"
40 #include "tree-phinodes.h"
41 #include "ssa-iterators.h"
42 #include "stringpool.h"
43 #include "tree-ssanames.h"
44 #include "tree-ssa-loop-ivopts.h"
45 #include "tree-ssa-loop-manip.h"
46 #include "tree-ssa-loop-niter.h"
47 #include "tree-pass.h"
53 #include "diagnostic-core.h"
54 #include "tree-chrec.h"
55 #include "tree-scalar-evolution.h"
56 #include "tree-vectorizer.h"
59 /* Loop Vectorization Pass.
61 This pass tries to vectorize loops.
63 For example, the vectorizer transforms the following simple loop:
65 short a[N]; short b[N]; short c[N]; int i;
71 as if it was manually vectorized by rewriting the source code into:
73 typedef int __attribute__((mode(V8HI))) v8hi;
74 short a[N]; short b[N]; short c[N]; int i;
75 v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
78 for (i=0; i<N/8; i++){
85 The main entry to this pass is vectorize_loops(), in which
86 the vectorizer applies a set of analyses on a given set of loops,
87 followed by the actual vectorization transformation for the loops that
88 had successfully passed the analysis phase.
89 Throughout this pass we make a distinction between two types of
90 data: scalars (which are represented by SSA_NAMES), and memory references
91 ("data-refs"). These two types of data require different handling both
92 during analysis and transformation. The types of data-refs that the
93 vectorizer currently supports are ARRAY_REFS which base is an array DECL
94 (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
95 accesses are required to have a simple (consecutive) access pattern.
99 The driver for the analysis phase is vect_analyze_loop().
100 It applies a set of analyses, some of which rely on the scalar evolution
101 analyzer (scev) developed by Sebastian Pop.
103 During the analysis phase the vectorizer records some information
104 per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
105 loop, as well as general information about the loop as a whole, which is
106 recorded in a "loop_vec_info" struct attached to each loop.
108 Transformation phase:
109 =====================
110 The loop transformation phase scans all the stmts in the loop, and
111 creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
112 the loop that needs to be vectorized. It inserts the vector code sequence
113 just before the scalar stmt S, and records a pointer to the vector code
114 in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
115 attached to S). This pointer will be used for the vectorization of following
116 stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
117 otherwise, we rely on dead code elimination for removing it.
119 For example, say stmt S1 was vectorized into stmt VS1:
122 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
125 To vectorize stmt S2, the vectorizer first finds the stmt that defines
126 the operand 'b' (S1), and gets the relevant vector def 'vb' from the
127 vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
128 resulting sequence would be:
131 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
133 S2: a = b; STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
135 Operands that are not SSA_NAMEs, are data-refs that appear in
136 load/store operations (like 'x[i]' in S1), and are handled differently.
140 Currently the only target specific information that is used is the
141 size of the vector (in bytes) - "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD".
142 Targets that can support different sizes of vectors, for now will need
143 to specify one value for "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD". More
144 flexibility will be added in the future.
146 Since we only vectorize operations which vector form can be
147 expressed using existing tree codes, to verify that an operation is
148 supported, the vectorizer checks the relevant optab at the relevant
149 machine_mode (e.g, optab_handler (add_optab, V8HImode)). If
150 the value found is CODE_FOR_nothing, then there's no target support, and
151 we can't vectorize the stmt.
153 For additional information on this project see:
154 http://gcc.gnu.org/projects/tree-ssa/vectorization.html
157 static void vect_estimate_min_profitable_iters (loop_vec_info
, int *, int *);
159 /* Function vect_determine_vectorization_factor
161 Determine the vectorization factor (VF). VF is the number of data elements
162 that are operated upon in parallel in a single iteration of the vectorized
163 loop. For example, when vectorizing a loop that operates on 4byte elements,
164 on a target with vector size (VS) 16byte, the VF is set to 4, since 4
165 elements can fit in a single vector register.
167 We currently support vectorization of loops in which all types operated upon
168 are of the same size. Therefore this function currently sets VF according to
169 the size of the types operated upon, and fails if there are multiple sizes
172 VF is also the factor by which the loop iterations are strip-mined, e.g.:
179 for (i=0; i<N; i+=VF){
180 a[i:VF] = b[i:VF] + c[i:VF];
185 vect_determine_vectorization_factor (loop_vec_info loop_vinfo
)
187 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
188 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
189 int nbbs
= loop
->num_nodes
;
190 gimple_stmt_iterator si
;
191 unsigned int vectorization_factor
= 0;
196 stmt_vec_info stmt_info
;
199 gimple stmt
, pattern_stmt
= NULL
;
200 gimple_seq pattern_def_seq
= NULL
;
201 gimple_stmt_iterator pattern_def_si
= gsi_none ();
202 bool analyze_pattern_stmt
= false;
204 if (dump_enabled_p ())
205 dump_printf_loc (MSG_NOTE
, vect_location
,
206 "=== vect_determine_vectorization_factor ===\n");
208 for (i
= 0; i
< nbbs
; i
++)
210 basic_block bb
= bbs
[i
];
212 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
215 stmt_info
= vinfo_for_stmt (phi
);
216 if (dump_enabled_p ())
218 dump_printf_loc (MSG_NOTE
, vect_location
, "==> examining phi: ");
219 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
220 dump_printf (MSG_NOTE
, "\n");
223 gcc_assert (stmt_info
);
225 if (STMT_VINFO_RELEVANT_P (stmt_info
))
227 gcc_assert (!STMT_VINFO_VECTYPE (stmt_info
));
228 scalar_type
= TREE_TYPE (PHI_RESULT (phi
));
230 if (dump_enabled_p ())
232 dump_printf_loc (MSG_NOTE
, vect_location
,
233 "get vectype for scalar type: ");
234 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
235 dump_printf (MSG_NOTE
, "\n");
238 vectype
= get_vectype_for_scalar_type (scalar_type
);
241 if (dump_enabled_p ())
243 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
244 "not vectorized: unsupported "
246 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
248 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
252 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
254 if (dump_enabled_p ())
256 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
257 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vectype
);
258 dump_printf (MSG_NOTE
, "\n");
261 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
262 if (dump_enabled_p ())
263 dump_printf_loc (MSG_NOTE
, vect_location
, "nunits = %d\n",
266 if (!vectorization_factor
267 || (nunits
> vectorization_factor
))
268 vectorization_factor
= nunits
;
272 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
) || analyze_pattern_stmt
;)
276 if (analyze_pattern_stmt
)
279 stmt
= gsi_stmt (si
);
281 stmt_info
= vinfo_for_stmt (stmt
);
283 if (dump_enabled_p ())
285 dump_printf_loc (MSG_NOTE
, vect_location
,
286 "==> examining statement: ");
287 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
288 dump_printf (MSG_NOTE
, "\n");
291 gcc_assert (stmt_info
);
293 /* Skip stmts which do not need to be vectorized. */
294 if ((!STMT_VINFO_RELEVANT_P (stmt_info
)
295 && !STMT_VINFO_LIVE_P (stmt_info
))
296 || gimple_clobber_p (stmt
))
298 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
299 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
300 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
301 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
304 stmt_info
= vinfo_for_stmt (pattern_stmt
);
305 if (dump_enabled_p ())
307 dump_printf_loc (MSG_NOTE
, vect_location
,
308 "==> examining pattern statement: ");
309 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
310 dump_printf (MSG_NOTE
, "\n");
315 if (dump_enabled_p ())
316 dump_printf_loc (MSG_NOTE
, vect_location
, "skip.\n");
321 else if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
322 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
323 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
324 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
325 analyze_pattern_stmt
= true;
327 /* If a pattern statement has def stmts, analyze them too. */
328 if (is_pattern_stmt_p (stmt_info
))
330 if (pattern_def_seq
== NULL
)
332 pattern_def_seq
= STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
);
333 pattern_def_si
= gsi_start (pattern_def_seq
);
335 else if (!gsi_end_p (pattern_def_si
))
336 gsi_next (&pattern_def_si
);
337 if (pattern_def_seq
!= NULL
)
339 gimple pattern_def_stmt
= NULL
;
340 stmt_vec_info pattern_def_stmt_info
= NULL
;
342 while (!gsi_end_p (pattern_def_si
))
344 pattern_def_stmt
= gsi_stmt (pattern_def_si
);
345 pattern_def_stmt_info
346 = vinfo_for_stmt (pattern_def_stmt
);
347 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info
)
348 || STMT_VINFO_LIVE_P (pattern_def_stmt_info
))
350 gsi_next (&pattern_def_si
);
353 if (!gsi_end_p (pattern_def_si
))
355 if (dump_enabled_p ())
357 dump_printf_loc (MSG_NOTE
, vect_location
,
358 "==> examining pattern def stmt: ");
359 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
360 pattern_def_stmt
, 0);
361 dump_printf (MSG_NOTE
, "\n");
364 stmt
= pattern_def_stmt
;
365 stmt_info
= pattern_def_stmt_info
;
369 pattern_def_si
= gsi_none ();
370 analyze_pattern_stmt
= false;
374 analyze_pattern_stmt
= false;
377 if (gimple_get_lhs (stmt
) == NULL_TREE
)
379 if (is_gimple_call (stmt
))
381 /* Ignore calls with no lhs. These must be calls to
382 #pragma omp simd functions, and what vectorization factor
383 it really needs can't be determined until
384 vectorizable_simd_clone_call. */
385 if (!analyze_pattern_stmt
&& gsi_end_p (pattern_def_si
))
387 pattern_def_seq
= NULL
;
392 if (dump_enabled_p ())
394 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
395 "not vectorized: irregular stmt.");
396 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
,
398 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
403 if (VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt
))))
405 if (dump_enabled_p ())
407 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
408 "not vectorized: vector stmt in loop:");
409 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
410 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
415 if (STMT_VINFO_VECTYPE (stmt_info
))
417 /* The only case when a vectype had been already set is for stmts
418 that contain a dataref, or for "pattern-stmts" (stmts
419 generated by the vectorizer to represent/replace a certain
421 gcc_assert (STMT_VINFO_DATA_REF (stmt_info
)
422 || is_pattern_stmt_p (stmt_info
)
423 || !gsi_end_p (pattern_def_si
));
424 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
428 gcc_assert (!STMT_VINFO_DATA_REF (stmt_info
));
429 scalar_type
= TREE_TYPE (gimple_get_lhs (stmt
));
430 if (dump_enabled_p ())
432 dump_printf_loc (MSG_NOTE
, vect_location
,
433 "get vectype for scalar type: ");
434 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
435 dump_printf (MSG_NOTE
, "\n");
437 vectype
= get_vectype_for_scalar_type (scalar_type
);
440 if (dump_enabled_p ())
442 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
443 "not vectorized: unsupported "
445 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
447 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
452 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
454 if (dump_enabled_p ())
456 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
457 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vectype
);
458 dump_printf (MSG_NOTE
, "\n");
462 /* The vectorization factor is according to the smallest
463 scalar type (or the largest vector size, but we only
464 support one vector size per loop). */
465 scalar_type
= vect_get_smallest_scalar_type (stmt
, &dummy
,
467 if (dump_enabled_p ())
469 dump_printf_loc (MSG_NOTE
, vect_location
,
470 "get vectype for scalar type: ");
471 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
472 dump_printf (MSG_NOTE
, "\n");
474 vf_vectype
= get_vectype_for_scalar_type (scalar_type
);
477 if (dump_enabled_p ())
479 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
480 "not vectorized: unsupported data-type ");
481 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
483 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
488 if ((GET_MODE_SIZE (TYPE_MODE (vectype
))
489 != GET_MODE_SIZE (TYPE_MODE (vf_vectype
))))
491 if (dump_enabled_p ())
493 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
494 "not vectorized: different sized vector "
495 "types in statement, ");
496 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
498 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
499 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
501 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
506 if (dump_enabled_p ())
508 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
509 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vf_vectype
);
510 dump_printf (MSG_NOTE
, "\n");
513 nunits
= TYPE_VECTOR_SUBPARTS (vf_vectype
);
514 if (dump_enabled_p ())
515 dump_printf_loc (MSG_NOTE
, vect_location
, "nunits = %d\n", nunits
);
516 if (!vectorization_factor
517 || (nunits
> vectorization_factor
))
518 vectorization_factor
= nunits
;
520 if (!analyze_pattern_stmt
&& gsi_end_p (pattern_def_si
))
522 pattern_def_seq
= NULL
;
528 /* TODO: Analyze cost. Decide if worth while to vectorize. */
529 if (dump_enabled_p ())
530 dump_printf_loc (MSG_NOTE
, vect_location
, "vectorization factor = %d\n",
531 vectorization_factor
);
532 if (vectorization_factor
<= 1)
534 if (dump_enabled_p ())
535 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
536 "not vectorized: unsupported data-type\n");
539 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
545 /* Function vect_is_simple_iv_evolution.
547 FORNOW: A simple evolution of an induction variables in the loop is
548 considered a polynomial evolution. */
551 vect_is_simple_iv_evolution (unsigned loop_nb
, tree access_fn
, tree
* init
,
556 tree evolution_part
= evolution_part_in_loop_num (access_fn
, loop_nb
);
559 /* When there is no evolution in this loop, the evolution function
561 if (evolution_part
== NULL_TREE
)
564 /* When the evolution is a polynomial of degree >= 2
565 the evolution function is not "simple". */
566 if (tree_is_chrec (evolution_part
))
569 step_expr
= evolution_part
;
570 init_expr
= unshare_expr (initial_condition_in_loop_num (access_fn
, loop_nb
));
572 if (dump_enabled_p ())
574 dump_printf_loc (MSG_NOTE
, vect_location
, "step: ");
575 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, step_expr
);
576 dump_printf (MSG_NOTE
, ", init: ");
577 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, init_expr
);
578 dump_printf (MSG_NOTE
, "\n");
584 if (TREE_CODE (step_expr
) != INTEGER_CST
585 && (TREE_CODE (step_expr
) != SSA_NAME
586 || ((bb
= gimple_bb (SSA_NAME_DEF_STMT (step_expr
)))
587 && flow_bb_inside_loop_p (get_loop (cfun
, loop_nb
), bb
))
588 || (!INTEGRAL_TYPE_P (TREE_TYPE (step_expr
))
589 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
))
590 || !flag_associative_math
)))
591 && (TREE_CODE (step_expr
) != REAL_CST
592 || !flag_associative_math
))
594 if (dump_enabled_p ())
595 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
603 /* Function vect_analyze_scalar_cycles_1.
605 Examine the cross iteration def-use cycles of scalar variables
606 in LOOP. LOOP_VINFO represents the loop that is now being
607 considered for vectorization (can be LOOP, or an outer-loop
611 vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo
, struct loop
*loop
)
613 basic_block bb
= loop
->header
;
615 stack_vec
<gimple
, 64> worklist
;
616 gimple_stmt_iterator gsi
;
619 if (dump_enabled_p ())
620 dump_printf_loc (MSG_NOTE
, vect_location
,
621 "=== vect_analyze_scalar_cycles ===\n");
623 /* First - identify all inductions. Reduction detection assumes that all the
624 inductions have been identified, therefore, this order must not be
626 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
628 gimple phi
= gsi_stmt (gsi
);
629 tree access_fn
= NULL
;
630 tree def
= PHI_RESULT (phi
);
631 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (phi
);
633 if (dump_enabled_p ())
635 dump_printf_loc (MSG_NOTE
, vect_location
, "Analyze phi: ");
636 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
637 dump_printf (MSG_NOTE
, "\n");
640 /* Skip virtual phi's. The data dependences that are associated with
641 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
642 if (virtual_operand_p (def
))
645 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_unknown_def_type
;
647 /* Analyze the evolution function. */
648 access_fn
= analyze_scalar_evolution (loop
, def
);
651 STRIP_NOPS (access_fn
);
652 if (dump_enabled_p ())
654 dump_printf_loc (MSG_NOTE
, vect_location
,
655 "Access function of PHI: ");
656 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, access_fn
);
657 dump_printf (MSG_NOTE
, "\n");
659 STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
)
660 = evolution_part_in_loop_num (access_fn
, loop
->num
);
664 || !vect_is_simple_iv_evolution (loop
->num
, access_fn
, &init
, &step
)
665 || (LOOP_VINFO_LOOP (loop_vinfo
) != loop
666 && TREE_CODE (step
) != INTEGER_CST
))
668 worklist
.safe_push (phi
);
672 gcc_assert (STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
) != NULL_TREE
);
674 if (dump_enabled_p ())
675 dump_printf_loc (MSG_NOTE
, vect_location
, "Detected induction.\n");
676 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_induction_def
;
680 /* Second - identify all reductions and nested cycles. */
681 while (worklist
.length () > 0)
683 gimple phi
= worklist
.pop ();
684 tree def
= PHI_RESULT (phi
);
685 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (phi
);
689 if (dump_enabled_p ())
691 dump_printf_loc (MSG_NOTE
, vect_location
, "Analyze phi: ");
692 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
693 dump_printf (MSG_NOTE
, "\n");
696 gcc_assert (!virtual_operand_p (def
)
697 && STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_unknown_def_type
);
699 nested_cycle
= (loop
!= LOOP_VINFO_LOOP (loop_vinfo
));
700 reduc_stmt
= vect_force_simple_reduction (loop_vinfo
, phi
, !nested_cycle
,
706 if (dump_enabled_p ())
707 dump_printf_loc (MSG_NOTE
, vect_location
,
708 "Detected double reduction.\n");
710 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_double_reduction_def
;
711 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
712 vect_double_reduction_def
;
718 if (dump_enabled_p ())
719 dump_printf_loc (MSG_NOTE
, vect_location
,
720 "Detected vectorizable nested cycle.\n");
722 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_nested_cycle
;
723 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
728 if (dump_enabled_p ())
729 dump_printf_loc (MSG_NOTE
, vect_location
,
730 "Detected reduction.\n");
732 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_reduction_def
;
733 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
735 /* Store the reduction cycles for possible vectorization in
737 LOOP_VINFO_REDUCTIONS (loop_vinfo
).safe_push (reduc_stmt
);
742 if (dump_enabled_p ())
743 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
744 "Unknown def-use cycle pattern.\n");
749 /* Function vect_analyze_scalar_cycles.
751 Examine the cross iteration def-use cycles of scalar variables, by
752 analyzing the loop-header PHIs of scalar variables. Classify each
753 cycle as one of the following: invariant, induction, reduction, unknown.
754 We do that for the loop represented by LOOP_VINFO, and also to its
755 inner-loop, if exists.
756 Examples for scalar cycles:
771 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo
)
773 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
775 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
);
777 /* When vectorizing an outer-loop, the inner-loop is executed sequentially.
778 Reductions in such inner-loop therefore have different properties than
779 the reductions in the nest that gets vectorized:
780 1. When vectorized, they are executed in the same order as in the original
781 scalar loop, so we can't change the order of computation when
783 2. FIXME: Inner-loop reductions can be used in the inner-loop, so the
784 current checks are too strict. */
787 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
->inner
);
791 /* Function vect_get_loop_niters.
793 Determine how many iterations the loop is executed and place it
794 in NUMBER_OF_ITERATIONS.
796 Return the loop exit condition. */
799 vect_get_loop_niters (struct loop
*loop
, tree
*number_of_iterations
)
803 if (dump_enabled_p ())
804 dump_printf_loc (MSG_NOTE
, vect_location
,
805 "=== get_loop_niters ===\n");
807 niters
= number_of_latch_executions (loop
);
808 /* We want the number of loop header executions which is the number
809 of latch executions plus one.
810 ??? For UINT_MAX latch executions this number overflows to zero
811 for loops like do { n++; } while (n != 0); */
812 if (niters
&& !chrec_contains_undetermined (niters
))
813 niters
= fold_build2 (PLUS_EXPR
, TREE_TYPE (niters
), niters
,
814 build_int_cst (TREE_TYPE (niters
), 1));
815 *number_of_iterations
= niters
;
817 return get_loop_exit_condition (loop
);
821 /* Function bb_in_loop_p
823 Used as predicate for dfs order traversal of the loop bbs. */
826 bb_in_loop_p (const_basic_block bb
, const void *data
)
828 const struct loop
*const loop
= (const struct loop
*)data
;
829 if (flow_bb_inside_loop_p (loop
, bb
))
835 /* Function new_loop_vec_info.
837 Create and initialize a new loop_vec_info struct for LOOP, as well as
838 stmt_vec_info structs for all the stmts in LOOP. */
841 new_loop_vec_info (struct loop
*loop
)
845 gimple_stmt_iterator si
;
846 unsigned int i
, nbbs
;
848 res
= (loop_vec_info
) xcalloc (1, sizeof (struct _loop_vec_info
));
849 LOOP_VINFO_LOOP (res
) = loop
;
851 bbs
= get_loop_body (loop
);
853 /* Create/Update stmt_info for all stmts in the loop. */
854 for (i
= 0; i
< loop
->num_nodes
; i
++)
856 basic_block bb
= bbs
[i
];
858 /* BBs in a nested inner-loop will have been already processed (because
859 we will have called vect_analyze_loop_form for any nested inner-loop).
860 Therefore, for stmts in an inner-loop we just want to update the
861 STMT_VINFO_LOOP_VINFO field of their stmt_info to point to the new
862 loop_info of the outer-loop we are currently considering to vectorize
863 (instead of the loop_info of the inner-loop).
864 For stmts in other BBs we need to create a stmt_info from scratch. */
865 if (bb
->loop_father
!= loop
)
868 gcc_assert (loop
->inner
&& bb
->loop_father
== loop
->inner
);
869 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
871 gimple phi
= gsi_stmt (si
);
872 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
873 loop_vec_info inner_loop_vinfo
=
874 STMT_VINFO_LOOP_VINFO (stmt_info
);
875 gcc_assert (loop
->inner
== LOOP_VINFO_LOOP (inner_loop_vinfo
));
876 STMT_VINFO_LOOP_VINFO (stmt_info
) = res
;
878 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
880 gimple stmt
= gsi_stmt (si
);
881 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
882 loop_vec_info inner_loop_vinfo
=
883 STMT_VINFO_LOOP_VINFO (stmt_info
);
884 gcc_assert (loop
->inner
== LOOP_VINFO_LOOP (inner_loop_vinfo
));
885 STMT_VINFO_LOOP_VINFO (stmt_info
) = res
;
890 /* bb in current nest. */
891 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
893 gimple phi
= gsi_stmt (si
);
894 gimple_set_uid (phi
, 0);
895 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, res
, NULL
));
898 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
900 gimple stmt
= gsi_stmt (si
);
901 gimple_set_uid (stmt
, 0);
902 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, res
, NULL
));
907 /* CHECKME: We want to visit all BBs before their successors (except for
908 latch blocks, for which this assertion wouldn't hold). In the simple
909 case of the loop forms we allow, a dfs order of the BBs would the same
910 as reversed postorder traversal, so we are safe. */
913 bbs
= XCNEWVEC (basic_block
, loop
->num_nodes
);
914 nbbs
= dfs_enumerate_from (loop
->header
, 0, bb_in_loop_p
,
915 bbs
, loop
->num_nodes
, loop
);
916 gcc_assert (nbbs
== loop
->num_nodes
);
918 LOOP_VINFO_BBS (res
) = bbs
;
919 LOOP_VINFO_NITERS (res
) = NULL
;
920 LOOP_VINFO_NITERS_UNCHANGED (res
) = NULL
;
921 LOOP_VINFO_COST_MODEL_MIN_ITERS (res
) = 0;
922 LOOP_VINFO_VECTORIZABLE_P (res
) = 0;
923 LOOP_VINFO_PEELING_FOR_ALIGNMENT (res
) = 0;
924 LOOP_VINFO_VECT_FACTOR (res
) = 0;
925 LOOP_VINFO_LOOP_NEST (res
).create (3);
926 LOOP_VINFO_DATAREFS (res
).create (10);
927 LOOP_VINFO_DDRS (res
).create (10 * 10);
928 LOOP_VINFO_UNALIGNED_DR (res
) = NULL
;
929 LOOP_VINFO_MAY_MISALIGN_STMTS (res
).create (
930 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS
));
931 LOOP_VINFO_MAY_ALIAS_DDRS (res
).create (
932 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS
));
933 LOOP_VINFO_GROUPED_STORES (res
).create (10);
934 LOOP_VINFO_REDUCTIONS (res
).create (10);
935 LOOP_VINFO_REDUCTION_CHAINS (res
).create (10);
936 LOOP_VINFO_SLP_INSTANCES (res
).create (10);
937 LOOP_VINFO_SLP_UNROLLING_FACTOR (res
) = 1;
938 LOOP_VINFO_TARGET_COST_DATA (res
) = init_cost (loop
);
939 LOOP_VINFO_PEELING_FOR_GAPS (res
) = false;
940 LOOP_VINFO_PEELING_FOR_NITER (res
) = false;
941 LOOP_VINFO_OPERANDS_SWAPPED (res
) = false;
947 /* Function destroy_loop_vec_info.
949 Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
950 stmts in the loop. */
953 destroy_loop_vec_info (loop_vec_info loop_vinfo
, bool clean_stmts
)
958 gimple_stmt_iterator si
;
960 vec
<slp_instance
> slp_instances
;
961 slp_instance instance
;
967 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
969 bbs
= LOOP_VINFO_BBS (loop_vinfo
);
970 nbbs
= clean_stmts
? loop
->num_nodes
: 0;
971 swapped
= LOOP_VINFO_OPERANDS_SWAPPED (loop_vinfo
);
973 for (j
= 0; j
< nbbs
; j
++)
975 basic_block bb
= bbs
[j
];
976 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
977 free_stmt_vec_info (gsi_stmt (si
));
979 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); )
981 gimple stmt
= gsi_stmt (si
);
983 /* We may have broken canonical form by moving a constant
984 into RHS1 of a commutative op. Fix such occurrences. */
985 if (swapped
&& is_gimple_assign (stmt
))
987 enum tree_code code
= gimple_assign_rhs_code (stmt
);
989 if ((code
== PLUS_EXPR
990 || code
== POINTER_PLUS_EXPR
991 || code
== MULT_EXPR
)
992 && CONSTANT_CLASS_P (gimple_assign_rhs1 (stmt
)))
993 swap_ssa_operands (stmt
,
994 gimple_assign_rhs1_ptr (stmt
),
995 gimple_assign_rhs2_ptr (stmt
));
998 /* Free stmt_vec_info. */
999 free_stmt_vec_info (stmt
);
1004 free (LOOP_VINFO_BBS (loop_vinfo
));
1005 vect_destroy_datarefs (loop_vinfo
, NULL
);
1006 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo
));
1007 LOOP_VINFO_LOOP_NEST (loop_vinfo
).release ();
1008 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).release ();
1009 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
).release ();
1010 slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
1011 FOR_EACH_VEC_ELT (slp_instances
, j
, instance
)
1012 vect_free_slp_instance (instance
);
1014 LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).release ();
1015 LOOP_VINFO_GROUPED_STORES (loop_vinfo
).release ();
1016 LOOP_VINFO_REDUCTIONS (loop_vinfo
).release ();
1017 LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
).release ();
1019 if (LOOP_VINFO_PEELING_HTAB (loop_vinfo
).is_created ())
1020 LOOP_VINFO_PEELING_HTAB (loop_vinfo
).dispose ();
1022 destroy_cost_data (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
));
1029 /* Function vect_analyze_loop_1.
1031 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1032 for it. The different analyses will record information in the
1033 loop_vec_info struct. This is a subset of the analyses applied in
1034 vect_analyze_loop, to be applied on an inner-loop nested in the loop
1035 that is now considered for (outer-loop) vectorization. */
1037 static loop_vec_info
1038 vect_analyze_loop_1 (struct loop
*loop
)
1040 loop_vec_info loop_vinfo
;
1042 if (dump_enabled_p ())
1043 dump_printf_loc (MSG_NOTE
, vect_location
,
1044 "===== analyze_loop_nest_1 =====\n");
1046 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
1048 loop_vinfo
= vect_analyze_loop_form (loop
);
1051 if (dump_enabled_p ())
1052 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1053 "bad inner-loop form.\n");
1061 /* Function vect_analyze_loop_form.
1063 Verify that certain CFG restrictions hold, including:
1064 - the loop has a pre-header
1065 - the loop has a single entry and exit
1066 - the loop exit condition is simple enough, and the number of iterations
1067 can be analyzed (a countable loop). */
1070 vect_analyze_loop_form (struct loop
*loop
)
1072 loop_vec_info loop_vinfo
;
1074 tree number_of_iterations
= NULL
;
1075 loop_vec_info inner_loop_vinfo
= NULL
;
1077 if (dump_enabled_p ())
1078 dump_printf_loc (MSG_NOTE
, vect_location
,
1079 "=== vect_analyze_loop_form ===\n");
1081 /* Different restrictions apply when we are considering an inner-most loop,
1082 vs. an outer (nested) loop.
1083 (FORNOW. May want to relax some of these restrictions in the future). */
1087 /* Inner-most loop. We currently require that the number of BBs is
1088 exactly 2 (the header and latch). Vectorizable inner-most loops
1099 if (loop
->num_nodes
!= 2)
1101 if (dump_enabled_p ())
1102 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1103 "not vectorized: control flow in loop.\n");
1107 if (empty_block_p (loop
->header
))
1109 if (dump_enabled_p ())
1110 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1111 "not vectorized: empty loop.\n");
1117 struct loop
*innerloop
= loop
->inner
;
1120 /* Nested loop. We currently require that the loop is doubly-nested,
1121 contains a single inner loop, and the number of BBs is exactly 5.
1122 Vectorizable outer-loops look like this:
1134 The inner-loop has the properties expected of inner-most loops
1135 as described above. */
1137 if ((loop
->inner
)->inner
|| (loop
->inner
)->next
)
1139 if (dump_enabled_p ())
1140 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1141 "not vectorized: multiple nested loops.\n");
1145 /* Analyze the inner-loop. */
1146 inner_loop_vinfo
= vect_analyze_loop_1 (loop
->inner
);
1147 if (!inner_loop_vinfo
)
1149 if (dump_enabled_p ())
1150 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1151 "not vectorized: Bad inner loop.\n");
1155 if (!expr_invariant_in_loop_p (loop
,
1156 LOOP_VINFO_NITERS (inner_loop_vinfo
)))
1158 if (dump_enabled_p ())
1159 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1160 "not vectorized: inner-loop count not"
1162 destroy_loop_vec_info (inner_loop_vinfo
, true);
1166 if (loop
->num_nodes
!= 5)
1168 if (dump_enabled_p ())
1169 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1170 "not vectorized: control flow in loop.\n");
1171 destroy_loop_vec_info (inner_loop_vinfo
, true);
1175 gcc_assert (EDGE_COUNT (innerloop
->header
->preds
) == 2);
1176 entryedge
= EDGE_PRED (innerloop
->header
, 0);
1177 if (EDGE_PRED (innerloop
->header
, 0)->src
== innerloop
->latch
)
1178 entryedge
= EDGE_PRED (innerloop
->header
, 1);
1180 if (entryedge
->src
!= loop
->header
1181 || !single_exit (innerloop
)
1182 || single_exit (innerloop
)->dest
!= EDGE_PRED (loop
->latch
, 0)->src
)
1184 if (dump_enabled_p ())
1185 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1186 "not vectorized: unsupported outerloop form.\n");
1187 destroy_loop_vec_info (inner_loop_vinfo
, true);
1191 if (dump_enabled_p ())
1192 dump_printf_loc (MSG_NOTE
, vect_location
,
1193 "Considering outer-loop vectorization.\n");
1196 if (!single_exit (loop
)
1197 || EDGE_COUNT (loop
->header
->preds
) != 2)
1199 if (dump_enabled_p ())
1201 if (!single_exit (loop
))
1202 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1203 "not vectorized: multiple exits.\n");
1204 else if (EDGE_COUNT (loop
->header
->preds
) != 2)
1205 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1206 "not vectorized: too many incoming edges.\n");
1208 if (inner_loop_vinfo
)
1209 destroy_loop_vec_info (inner_loop_vinfo
, true);
1213 /* We assume that the loop exit condition is at the end of the loop. i.e,
1214 that the loop is represented as a do-while (with a proper if-guard
1215 before the loop if needed), where the loop header contains all the
1216 executable statements, and the latch is empty. */
1217 if (!empty_block_p (loop
->latch
)
1218 || !gimple_seq_empty_p (phi_nodes (loop
->latch
)))
1220 if (dump_enabled_p ())
1221 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1222 "not vectorized: latch block not empty.\n");
1223 if (inner_loop_vinfo
)
1224 destroy_loop_vec_info (inner_loop_vinfo
, true);
1228 /* Make sure there exists a single-predecessor exit bb: */
1229 if (!single_pred_p (single_exit (loop
)->dest
))
1231 edge e
= single_exit (loop
);
1232 if (!(e
->flags
& EDGE_ABNORMAL
))
1234 split_loop_exit_edge (e
);
1235 if (dump_enabled_p ())
1236 dump_printf (MSG_NOTE
, "split exit edge.\n");
1240 if (dump_enabled_p ())
1241 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1242 "not vectorized: abnormal loop exit edge.\n");
1243 if (inner_loop_vinfo
)
1244 destroy_loop_vec_info (inner_loop_vinfo
, true);
1249 loop_cond
= vect_get_loop_niters (loop
, &number_of_iterations
);
1252 if (dump_enabled_p ())
1253 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1254 "not vectorized: complicated exit condition.\n");
1255 if (inner_loop_vinfo
)
1256 destroy_loop_vec_info (inner_loop_vinfo
, true);
1260 if (!number_of_iterations
1261 || chrec_contains_undetermined (number_of_iterations
))
1263 if (dump_enabled_p ())
1264 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1265 "not vectorized: number of iterations cannot be "
1267 if (inner_loop_vinfo
)
1268 destroy_loop_vec_info (inner_loop_vinfo
, true);
1272 if (integer_zerop (number_of_iterations
))
1274 if (dump_enabled_p ())
1275 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1276 "not vectorized: number of iterations = 0.\n");
1277 if (inner_loop_vinfo
)
1278 destroy_loop_vec_info (inner_loop_vinfo
, true);
1282 loop_vinfo
= new_loop_vec_info (loop
);
1283 LOOP_VINFO_NITERS (loop_vinfo
) = number_of_iterations
;
1284 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo
) = number_of_iterations
;
1286 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
1288 if (dump_enabled_p ())
1290 dump_printf_loc (MSG_NOTE
, vect_location
,
1291 "Symbolic number of iterations is ");
1292 dump_generic_expr (MSG_NOTE
, TDF_DETAILS
, number_of_iterations
);
1293 dump_printf (MSG_NOTE
, "\n");
1297 STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond
)) = loop_exit_ctrl_vec_info_type
;
1299 /* CHECKME: May want to keep it around it in the future. */
1300 if (inner_loop_vinfo
)
1301 destroy_loop_vec_info (inner_loop_vinfo
, false);
1303 gcc_assert (!loop
->aux
);
1304 loop
->aux
= loop_vinfo
;
1309 /* Function vect_analyze_loop_operations.
1311 Scan the loop stmts and make sure they are all vectorizable. */
1314 vect_analyze_loop_operations (loop_vec_info loop_vinfo
, bool slp
)
1316 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1317 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1318 int nbbs
= loop
->num_nodes
;
1319 gimple_stmt_iterator si
;
1320 unsigned int vectorization_factor
= 0;
1323 stmt_vec_info stmt_info
;
1324 bool need_to_vectorize
= false;
1325 int min_profitable_iters
;
1326 int min_scalar_loop_bound
;
1328 bool only_slp_in_loop
= true, ok
;
1329 HOST_WIDE_INT max_niter
;
1330 HOST_WIDE_INT estimated_niter
;
1331 int min_profitable_estimate
;
1333 if (dump_enabled_p ())
1334 dump_printf_loc (MSG_NOTE
, vect_location
,
1335 "=== vect_analyze_loop_operations ===\n");
1337 gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo
));
1338 vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1341 /* If all the stmts in the loop can be SLPed, we perform only SLP, and
1342 vectorization factor of the loop is the unrolling factor required by
1343 the SLP instances. If that unrolling factor is 1, we say, that we
1344 perform pure SLP on loop - cross iteration parallelism is not
1346 for (i
= 0; i
< nbbs
; i
++)
1348 basic_block bb
= bbs
[i
];
1349 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1351 gimple stmt
= gsi_stmt (si
);
1352 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1353 gcc_assert (stmt_info
);
1354 if ((STMT_VINFO_RELEVANT_P (stmt_info
)
1355 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
1356 && !PURE_SLP_STMT (stmt_info
))
1357 /* STMT needs both SLP and loop-based vectorization. */
1358 only_slp_in_loop
= false;
1362 if (only_slp_in_loop
)
1363 vectorization_factor
= LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
);
1365 vectorization_factor
= least_common_multiple (vectorization_factor
,
1366 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
));
1368 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
1369 if (dump_enabled_p ())
1370 dump_printf_loc (MSG_NOTE
, vect_location
,
1371 "Updating vectorization factor to %d\n",
1372 vectorization_factor
);
1375 for (i
= 0; i
< nbbs
; i
++)
1377 basic_block bb
= bbs
[i
];
1379 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
1381 phi
= gsi_stmt (si
);
1384 stmt_info
= vinfo_for_stmt (phi
);
1385 if (dump_enabled_p ())
1387 dump_printf_loc (MSG_NOTE
, vect_location
, "examining phi: ");
1388 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
1389 dump_printf (MSG_NOTE
, "\n");
1392 /* Inner-loop loop-closed exit phi in outer-loop vectorization
1393 (i.e., a phi in the tail of the outer-loop). */
1394 if (! is_loop_header_bb_p (bb
))
1396 /* FORNOW: we currently don't support the case that these phis
1397 are not used in the outerloop (unless it is double reduction,
1398 i.e., this phi is vect_reduction_def), cause this case
1399 requires to actually do something here. */
1400 if ((!STMT_VINFO_RELEVANT_P (stmt_info
)
1401 || STMT_VINFO_LIVE_P (stmt_info
))
1402 && STMT_VINFO_DEF_TYPE (stmt_info
)
1403 != vect_double_reduction_def
)
1405 if (dump_enabled_p ())
1406 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1407 "Unsupported loop-closed phi in "
1412 /* If PHI is used in the outer loop, we check that its operand
1413 is defined in the inner loop. */
1414 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1419 if (gimple_phi_num_args (phi
) != 1)
1422 phi_op
= PHI_ARG_DEF (phi
, 0);
1423 if (TREE_CODE (phi_op
) != SSA_NAME
)
1426 op_def_stmt
= SSA_NAME_DEF_STMT (phi_op
);
1427 if (gimple_nop_p (op_def_stmt
)
1428 || !flow_bb_inside_loop_p (loop
, gimple_bb (op_def_stmt
))
1429 || !vinfo_for_stmt (op_def_stmt
))
1432 if (STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1433 != vect_used_in_outer
1434 && STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1435 != vect_used_in_outer_by_reduction
)
1442 gcc_assert (stmt_info
);
1444 if (STMT_VINFO_LIVE_P (stmt_info
))
1446 /* FORNOW: not yet supported. */
1447 if (dump_enabled_p ())
1448 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1449 "not vectorized: value used after loop.\n");
1453 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
1454 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_induction_def
)
1456 /* A scalar-dependence cycle that we don't support. */
1457 if (dump_enabled_p ())
1458 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1459 "not vectorized: scalar dependence cycle.\n");
1463 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1465 need_to_vectorize
= true;
1466 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
1467 ok
= vectorizable_induction (phi
, NULL
, NULL
);
1472 if (dump_enabled_p ())
1474 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1475 "not vectorized: relevant phi not "
1477 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, phi
, 0);
1478 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1484 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1486 gimple stmt
= gsi_stmt (si
);
1487 if (!gimple_clobber_p (stmt
)
1488 && !vect_analyze_stmt (stmt
, &need_to_vectorize
, NULL
))
1493 /* All operations in the loop are either irrelevant (deal with loop
1494 control, or dead), or only used outside the loop and can be moved
1495 out of the loop (e.g. invariants, inductions). The loop can be
1496 optimized away by scalar optimizations. We're better off not
1497 touching this loop. */
1498 if (!need_to_vectorize
)
1500 if (dump_enabled_p ())
1501 dump_printf_loc (MSG_NOTE
, vect_location
,
1502 "All the computation can be taken out of the loop.\n");
1503 if (dump_enabled_p ())
1504 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1505 "not vectorized: redundant loop. no profit to "
1510 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
) && dump_enabled_p ())
1511 dump_printf_loc (MSG_NOTE
, vect_location
,
1512 "vectorization_factor = %d, niters = "
1513 HOST_WIDE_INT_PRINT_DEC
"\n", vectorization_factor
,
1514 LOOP_VINFO_INT_NITERS (loop_vinfo
));
1516 if ((LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1517 && (LOOP_VINFO_INT_NITERS (loop_vinfo
) < vectorization_factor
))
1518 || ((max_niter
= max_stmt_executions_int (loop
)) != -1
1519 && (unsigned HOST_WIDE_INT
) max_niter
< vectorization_factor
))
1521 if (dump_enabled_p ())
1522 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1523 "not vectorized: iteration count too small.\n");
1524 if (dump_enabled_p ())
1525 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1526 "not vectorized: iteration count smaller than "
1527 "vectorization factor.\n");
1531 /* Analyze cost. Decide if worth while to vectorize. */
1533 /* Once VF is set, SLP costs should be updated since the number of created
1534 vector stmts depends on VF. */
1535 vect_update_slp_costs_according_to_vf (loop_vinfo
);
1537 vect_estimate_min_profitable_iters (loop_vinfo
, &min_profitable_iters
,
1538 &min_profitable_estimate
);
1539 LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo
) = min_profitable_iters
;
1541 if (min_profitable_iters
< 0)
1543 if (dump_enabled_p ())
1544 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1545 "not vectorized: vectorization not profitable.\n");
1546 if (dump_enabled_p ())
1547 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1548 "not vectorized: vector version will never be "
1553 min_scalar_loop_bound
= ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND
)
1554 * vectorization_factor
) - 1);
1557 /* Use the cost model only if it is more conservative than user specified
1560 th
= (unsigned) min_scalar_loop_bound
;
1561 if (min_profitable_iters
1562 && (!min_scalar_loop_bound
1563 || min_profitable_iters
> min_scalar_loop_bound
))
1564 th
= (unsigned) min_profitable_iters
;
1566 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1567 && LOOP_VINFO_INT_NITERS (loop_vinfo
) <= th
)
1569 if (dump_enabled_p ())
1570 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1571 "not vectorized: vectorization not profitable.\n");
1572 if (dump_enabled_p ())
1573 dump_printf_loc (MSG_NOTE
, vect_location
,
1574 "not vectorized: iteration count smaller than user "
1575 "specified loop bound parameter or minimum profitable "
1576 "iterations (whichever is more conservative).\n");
1580 if ((estimated_niter
= estimated_stmt_executions_int (loop
)) != -1
1581 && ((unsigned HOST_WIDE_INT
) estimated_niter
1582 <= MAX (th
, (unsigned)min_profitable_estimate
)))
1584 if (dump_enabled_p ())
1585 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1586 "not vectorized: estimated iteration count too "
1588 if (dump_enabled_p ())
1589 dump_printf_loc (MSG_NOTE
, vect_location
,
1590 "not vectorized: estimated iteration count smaller "
1591 "than specified loop bound parameter or minimum "
1592 "profitable iterations (whichever is more "
1593 "conservative).\n");
1601 /* Function vect_analyze_loop_2.
1603 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1604 for it. The different analyses will record information in the
1605 loop_vec_info struct. */
1607 vect_analyze_loop_2 (loop_vec_info loop_vinfo
)
1609 bool ok
, slp
= false;
1610 int max_vf
= MAX_VECTORIZATION_FACTOR
;
1613 /* Find all data references in the loop (which correspond to vdefs/vuses)
1614 and analyze their evolution in the loop. Also adjust the minimal
1615 vectorization factor according to the loads and stores.
1617 FORNOW: Handle only simple, array references, which
1618 alignment can be forced, and aligned pointer-references. */
1620 ok
= vect_analyze_data_refs (loop_vinfo
, NULL
, &min_vf
);
1623 if (dump_enabled_p ())
1624 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1625 "bad data references.\n");
1629 /* Analyze the access patterns of the data-refs in the loop (consecutive,
1630 complex, etc.). FORNOW: Only handle consecutive access pattern. */
1632 ok
= vect_analyze_data_ref_accesses (loop_vinfo
, NULL
);
1635 if (dump_enabled_p ())
1636 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1637 "bad data access.\n");
1641 /* Classify all cross-iteration scalar data-flow cycles.
1642 Cross-iteration cycles caused by virtual phis are analyzed separately. */
1644 vect_analyze_scalar_cycles (loop_vinfo
);
1646 vect_pattern_recog (loop_vinfo
, NULL
);
1648 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
1650 ok
= vect_mark_stmts_to_be_vectorized (loop_vinfo
);
1653 if (dump_enabled_p ())
1654 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1655 "unexpected pattern.\n");
1659 /* Analyze data dependences between the data-refs in the loop
1660 and adjust the maximum vectorization factor according to
1662 FORNOW: fail at the first data dependence that we encounter. */
1664 ok
= vect_analyze_data_ref_dependences (loop_vinfo
, &max_vf
);
1668 if (dump_enabled_p ())
1669 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1670 "bad data dependence.\n");
1674 ok
= vect_determine_vectorization_factor (loop_vinfo
);
1677 if (dump_enabled_p ())
1678 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1679 "can't determine vectorization factor.\n");
1682 if (max_vf
< LOOP_VINFO_VECT_FACTOR (loop_vinfo
))
1684 if (dump_enabled_p ())
1685 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1686 "bad data dependence.\n");
1690 /* Analyze the alignment of the data-refs in the loop.
1691 Fail if a data reference is found that cannot be vectorized. */
1693 ok
= vect_analyze_data_refs_alignment (loop_vinfo
, NULL
);
1696 if (dump_enabled_p ())
1697 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1698 "bad data alignment.\n");
1702 /* Prune the list of ddrs to be tested at run-time by versioning for alias.
1703 It is important to call pruning after vect_analyze_data_ref_accesses,
1704 since we use grouping information gathered by interleaving analysis. */
1705 ok
= vect_prune_runtime_alias_test_list (loop_vinfo
);
1708 if (dump_enabled_p ())
1709 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1710 "too long list of versioning for alias "
1711 "run-time tests.\n");
1715 /* This pass will decide on using loop versioning and/or loop peeling in
1716 order to enhance the alignment of data references in the loop. */
1718 ok
= vect_enhance_data_refs_alignment (loop_vinfo
);
1721 if (dump_enabled_p ())
1722 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1723 "bad data alignment.\n");
1727 /* Check the SLP opportunities in the loop, analyze and build SLP trees. */
1728 ok
= vect_analyze_slp (loop_vinfo
, NULL
);
1731 /* Decide which possible SLP instances to SLP. */
1732 slp
= vect_make_slp_decision (loop_vinfo
);
1734 /* Find stmts that need to be both vectorized and SLPed. */
1735 vect_detect_hybrid_slp (loop_vinfo
);
1740 /* Scan all the operations in the loop and make sure they are
1743 ok
= vect_analyze_loop_operations (loop_vinfo
, slp
);
1746 if (dump_enabled_p ())
1747 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1748 "bad operation or unsupported loop bound.\n");
1752 /* Decide whether we need to create an epilogue loop to handle
1753 remaining scalar iterations. */
1754 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1755 && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
) > 0)
1757 if (ctz_hwi (LOOP_VINFO_INT_NITERS (loop_vinfo
)
1758 - LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
))
1759 < exact_log2 (LOOP_VINFO_VECT_FACTOR (loop_vinfo
)))
1760 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
) = true;
1762 else if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
)
1763 || (tree_ctz (LOOP_VINFO_NITERS (loop_vinfo
))
1764 < (unsigned)exact_log2 (LOOP_VINFO_VECT_FACTOR (loop_vinfo
))))
1765 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
) = true;
1767 /* If an epilogue loop is required make sure we can create one. */
1768 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
1769 || LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
))
1771 if (dump_enabled_p ())
1772 dump_printf_loc (MSG_NOTE
, vect_location
, "epilog loop required\n");
1773 if (!vect_can_advance_ivs_p (loop_vinfo
)
1774 || !slpeel_can_duplicate_loop_p (LOOP_VINFO_LOOP (loop_vinfo
),
1775 single_exit (LOOP_VINFO_LOOP
1778 if (dump_enabled_p ())
1779 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1780 "not vectorized: can't create required "
1789 /* Function vect_analyze_loop.
1791 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1792 for it. The different analyses will record information in the
1793 loop_vec_info struct. */
1795 vect_analyze_loop (struct loop
*loop
)
1797 loop_vec_info loop_vinfo
;
1798 unsigned int vector_sizes
;
1800 /* Autodetect first vector size we try. */
1801 current_vector_size
= 0;
1802 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
1804 if (dump_enabled_p ())
1805 dump_printf_loc (MSG_NOTE
, vect_location
,
1806 "===== analyze_loop_nest =====\n");
1808 if (loop_outer (loop
)
1809 && loop_vec_info_for_loop (loop_outer (loop
))
1810 && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop
))))
1812 if (dump_enabled_p ())
1813 dump_printf_loc (MSG_NOTE
, vect_location
,
1814 "outer-loop already vectorized.\n");
1820 /* Check the CFG characteristics of the loop (nesting, entry/exit). */
1821 loop_vinfo
= vect_analyze_loop_form (loop
);
1824 if (dump_enabled_p ())
1825 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1826 "bad loop form.\n");
1830 if (vect_analyze_loop_2 (loop_vinfo
))
1832 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
) = 1;
1837 destroy_loop_vec_info (loop_vinfo
, true);
1839 vector_sizes
&= ~current_vector_size
;
1840 if (vector_sizes
== 0
1841 || current_vector_size
== 0)
1844 /* Try the next biggest vector size. */
1845 current_vector_size
= 1 << floor_log2 (vector_sizes
);
1846 if (dump_enabled_p ())
1847 dump_printf_loc (MSG_NOTE
, vect_location
,
1848 "***** Re-trying analysis with "
1849 "vector size %d\n", current_vector_size
);
1854 /* Function reduction_code_for_scalar_code
1857 CODE - tree_code of a reduction operations.
1860 REDUC_CODE - the corresponding tree-code to be used to reduce the
1861 vector of partial results into a single scalar result (which
1862 will also reside in a vector) or ERROR_MARK if the operation is
1863 a supported reduction operation, but does not have such tree-code.
1865 Return FALSE if CODE currently cannot be vectorized as reduction. */
1868 reduction_code_for_scalar_code (enum tree_code code
,
1869 enum tree_code
*reduc_code
)
1874 *reduc_code
= REDUC_MAX_EXPR
;
1878 *reduc_code
= REDUC_MIN_EXPR
;
1882 *reduc_code
= REDUC_PLUS_EXPR
;
1890 *reduc_code
= ERROR_MARK
;
1899 /* Error reporting helper for vect_is_simple_reduction below. GIMPLE statement
1900 STMT is printed with a message MSG. */
1903 report_vect_op (int msg_type
, gimple stmt
, const char *msg
)
1905 dump_printf_loc (msg_type
, vect_location
, "%s", msg
);
1906 dump_gimple_stmt (msg_type
, TDF_SLIM
, stmt
, 0);
1907 dump_printf (msg_type
, "\n");
1911 /* Detect SLP reduction of the form:
1921 PHI is the reduction phi node (#a1 = phi <a5, a0> above)
1922 FIRST_STMT is the first reduction stmt in the chain
1923 (a2 = operation (a1)).
1925 Return TRUE if a reduction chain was detected. */
1928 vect_is_slp_reduction (loop_vec_info loop_info
, gimple phi
, gimple first_stmt
)
1930 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
1931 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
1932 enum tree_code code
;
1933 gimple current_stmt
= NULL
, loop_use_stmt
= NULL
, first
, next_stmt
;
1934 stmt_vec_info use_stmt_info
, current_stmt_info
;
1936 imm_use_iterator imm_iter
;
1937 use_operand_p use_p
;
1938 int nloop_uses
, size
= 0, n_out_of_loop_uses
;
1941 if (loop
!= vect_loop
)
1944 lhs
= PHI_RESULT (phi
);
1945 code
= gimple_assign_rhs_code (first_stmt
);
1949 n_out_of_loop_uses
= 0;
1950 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
1952 gimple use_stmt
= USE_STMT (use_p
);
1953 if (is_gimple_debug (use_stmt
))
1956 use_stmt
= USE_STMT (use_p
);
1958 /* Check if we got back to the reduction phi. */
1959 if (use_stmt
== phi
)
1961 loop_use_stmt
= use_stmt
;
1966 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
1968 if (vinfo_for_stmt (use_stmt
)
1969 && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (use_stmt
)))
1971 loop_use_stmt
= use_stmt
;
1976 n_out_of_loop_uses
++;
1978 /* There are can be either a single use in the loop or two uses in
1980 if (nloop_uses
> 1 || (n_out_of_loop_uses
&& nloop_uses
))
1987 /* We reached a statement with no loop uses. */
1988 if (nloop_uses
== 0)
1991 /* This is a loop exit phi, and we haven't reached the reduction phi. */
1992 if (gimple_code (loop_use_stmt
) == GIMPLE_PHI
)
1995 if (!is_gimple_assign (loop_use_stmt
)
1996 || code
!= gimple_assign_rhs_code (loop_use_stmt
)
1997 || !flow_bb_inside_loop_p (loop
, gimple_bb (loop_use_stmt
)))
2000 /* Insert USE_STMT into reduction chain. */
2001 use_stmt_info
= vinfo_for_stmt (loop_use_stmt
);
2004 current_stmt_info
= vinfo_for_stmt (current_stmt
);
2005 GROUP_NEXT_ELEMENT (current_stmt_info
) = loop_use_stmt
;
2006 GROUP_FIRST_ELEMENT (use_stmt_info
)
2007 = GROUP_FIRST_ELEMENT (current_stmt_info
);
2010 GROUP_FIRST_ELEMENT (use_stmt_info
) = loop_use_stmt
;
2012 lhs
= gimple_assign_lhs (loop_use_stmt
);
2013 current_stmt
= loop_use_stmt
;
2017 if (!found
|| loop_use_stmt
!= phi
|| size
< 2)
2020 /* Swap the operands, if needed, to make the reduction operand be the second
2022 lhs
= PHI_RESULT (phi
);
2023 next_stmt
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
2026 if (gimple_assign_rhs2 (next_stmt
) == lhs
)
2028 tree op
= gimple_assign_rhs1 (next_stmt
);
2029 gimple def_stmt
= NULL
;
2031 if (TREE_CODE (op
) == SSA_NAME
)
2032 def_stmt
= SSA_NAME_DEF_STMT (op
);
2034 /* Check that the other def is either defined in the loop
2035 ("vect_internal_def"), or it's an induction (defined by a
2036 loop-header phi-node). */
2038 && gimple_bb (def_stmt
)
2039 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2040 && (is_gimple_assign (def_stmt
)
2041 || is_gimple_call (def_stmt
)
2042 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2043 == vect_induction_def
2044 || (gimple_code (def_stmt
) == GIMPLE_PHI
2045 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2046 == vect_internal_def
2047 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
2049 lhs
= gimple_assign_lhs (next_stmt
);
2050 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
2058 tree op
= gimple_assign_rhs2 (next_stmt
);
2059 gimple def_stmt
= NULL
;
2061 if (TREE_CODE (op
) == SSA_NAME
)
2062 def_stmt
= SSA_NAME_DEF_STMT (op
);
2064 /* Check that the other def is either defined in the loop
2065 ("vect_internal_def"), or it's an induction (defined by a
2066 loop-header phi-node). */
2068 && gimple_bb (def_stmt
)
2069 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2070 && (is_gimple_assign (def_stmt
)
2071 || is_gimple_call (def_stmt
)
2072 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2073 == vect_induction_def
2074 || (gimple_code (def_stmt
) == GIMPLE_PHI
2075 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2076 == vect_internal_def
2077 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
2079 if (dump_enabled_p ())
2081 dump_printf_loc (MSG_NOTE
, vect_location
, "swapping oprnds: ");
2082 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, next_stmt
, 0);
2083 dump_printf (MSG_NOTE
, "\n");
2086 swap_ssa_operands (next_stmt
,
2087 gimple_assign_rhs1_ptr (next_stmt
),
2088 gimple_assign_rhs2_ptr (next_stmt
));
2089 update_stmt (next_stmt
);
2091 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (next_stmt
)))
2092 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
2098 lhs
= gimple_assign_lhs (next_stmt
);
2099 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
2102 /* Save the chain for further analysis in SLP detection. */
2103 first
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
2104 LOOP_VINFO_REDUCTION_CHAINS (loop_info
).safe_push (first
);
2105 GROUP_SIZE (vinfo_for_stmt (first
)) = size
;
2111 /* Function vect_is_simple_reduction_1
2113 (1) Detect a cross-iteration def-use cycle that represents a simple
2114 reduction computation. We look for the following pattern:
2119 a2 = operation (a3, a1)
2126 a2 = operation (a3, a1)
2129 1. operation is commutative and associative and it is safe to
2130 change the order of the computation (if CHECK_REDUCTION is true)
2131 2. no uses for a2 in the loop (a2 is used out of the loop)
2132 3. no uses of a1 in the loop besides the reduction operation
2133 4. no uses of a1 outside the loop.
2135 Conditions 1,4 are tested here.
2136 Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
2138 (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
2139 nested cycles, if CHECK_REDUCTION is false.
2141 (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
2145 inner loop (def of a3)
2148 If MODIFY is true it tries also to rework the code in-place to enable
2149 detection of more reduction patterns. For the time being we rewrite
2150 "res -= RHS" into "rhs += -RHS" when it seems worthwhile.
2154 vect_is_simple_reduction_1 (loop_vec_info loop_info
, gimple phi
,
2155 bool check_reduction
, bool *double_reduc
,
2158 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
2159 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
2160 edge latch_e
= loop_latch_edge (loop
);
2161 tree loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
2162 gimple def_stmt
, def1
= NULL
, def2
= NULL
;
2163 enum tree_code orig_code
, code
;
2164 tree op1
, op2
, op3
= NULL_TREE
, op4
= NULL_TREE
;
2168 imm_use_iterator imm_iter
;
2169 use_operand_p use_p
;
2172 *double_reduc
= false;
2174 /* If CHECK_REDUCTION is true, we assume inner-most loop vectorization,
2175 otherwise, we assume outer loop vectorization. */
2176 gcc_assert ((check_reduction
&& loop
== vect_loop
)
2177 || (!check_reduction
&& flow_loop_nested_p (vect_loop
, loop
)));
2179 name
= PHI_RESULT (phi
);
2181 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2183 gimple use_stmt
= USE_STMT (use_p
);
2184 if (is_gimple_debug (use_stmt
))
2187 if (!flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2189 if (dump_enabled_p ())
2190 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2191 "intermediate value used outside loop.\n");
2196 if (vinfo_for_stmt (use_stmt
)
2197 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt
)))
2201 if (dump_enabled_p ())
2202 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2203 "reduction used in loop.\n");
2208 if (TREE_CODE (loop_arg
) != SSA_NAME
)
2210 if (dump_enabled_p ())
2212 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2213 "reduction: not ssa_name: ");
2214 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, loop_arg
);
2215 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
2220 def_stmt
= SSA_NAME_DEF_STMT (loop_arg
);
2223 if (dump_enabled_p ())
2224 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2225 "reduction: no def_stmt.\n");
2229 if (!is_gimple_assign (def_stmt
) && gimple_code (def_stmt
) != GIMPLE_PHI
)
2231 if (dump_enabled_p ())
2233 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, def_stmt
, 0);
2234 dump_printf (MSG_NOTE
, "\n");
2239 if (is_gimple_assign (def_stmt
))
2241 name
= gimple_assign_lhs (def_stmt
);
2246 name
= PHI_RESULT (def_stmt
);
2251 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2253 gimple use_stmt
= USE_STMT (use_p
);
2254 if (is_gimple_debug (use_stmt
))
2256 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
))
2257 && vinfo_for_stmt (use_stmt
)
2258 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt
)))
2262 if (dump_enabled_p ())
2263 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2264 "reduction used in loop.\n");
2269 /* If DEF_STMT is a phi node itself, we expect it to have a single argument
2270 defined in the inner loop. */
2273 op1
= PHI_ARG_DEF (def_stmt
, 0);
2275 if (gimple_phi_num_args (def_stmt
) != 1
2276 || TREE_CODE (op1
) != SSA_NAME
)
2278 if (dump_enabled_p ())
2279 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2280 "unsupported phi node definition.\n");
2285 def1
= SSA_NAME_DEF_STMT (op1
);
2286 if (flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2288 && flow_bb_inside_loop_p (loop
->inner
, gimple_bb (def1
))
2289 && is_gimple_assign (def1
))
2291 if (dump_enabled_p ())
2292 report_vect_op (MSG_NOTE
, def_stmt
,
2293 "detected double reduction: ");
2295 *double_reduc
= true;
2302 code
= orig_code
= gimple_assign_rhs_code (def_stmt
);
2304 /* We can handle "res -= x[i]", which is non-associative by
2305 simply rewriting this into "res += -x[i]". Avoid changing
2306 gimple instruction for the first simple tests and only do this
2307 if we're allowed to change code at all. */
2308 if (code
== MINUS_EXPR
2310 && (op1
= gimple_assign_rhs1 (def_stmt
))
2311 && TREE_CODE (op1
) == SSA_NAME
2312 && SSA_NAME_DEF_STMT (op1
) == phi
)
2316 && (!commutative_tree_code (code
) || !associative_tree_code (code
)))
2318 if (dump_enabled_p ())
2319 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2320 "reduction: not commutative/associative: ");
2324 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
2326 if (code
!= COND_EXPR
)
2328 if (dump_enabled_p ())
2329 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2330 "reduction: not binary operation: ");
2335 op3
= gimple_assign_rhs1 (def_stmt
);
2336 if (COMPARISON_CLASS_P (op3
))
2338 op4
= TREE_OPERAND (op3
, 1);
2339 op3
= TREE_OPERAND (op3
, 0);
2342 op1
= gimple_assign_rhs2 (def_stmt
);
2343 op2
= gimple_assign_rhs3 (def_stmt
);
2345 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2347 if (dump_enabled_p ())
2348 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2349 "reduction: uses not ssa_names: ");
2356 op1
= gimple_assign_rhs1 (def_stmt
);
2357 op2
= gimple_assign_rhs2 (def_stmt
);
2359 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2361 if (dump_enabled_p ())
2362 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2363 "reduction: uses not ssa_names: ");
2369 type
= TREE_TYPE (gimple_assign_lhs (def_stmt
));
2370 if ((TREE_CODE (op1
) == SSA_NAME
2371 && !types_compatible_p (type
,TREE_TYPE (op1
)))
2372 || (TREE_CODE (op2
) == SSA_NAME
2373 && !types_compatible_p (type
, TREE_TYPE (op2
)))
2374 || (op3
&& TREE_CODE (op3
) == SSA_NAME
2375 && !types_compatible_p (type
, TREE_TYPE (op3
)))
2376 || (op4
&& TREE_CODE (op4
) == SSA_NAME
2377 && !types_compatible_p (type
, TREE_TYPE (op4
))))
2379 if (dump_enabled_p ())
2381 dump_printf_loc (MSG_NOTE
, vect_location
,
2382 "reduction: multiple types: operation type: ");
2383 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, type
);
2384 dump_printf (MSG_NOTE
, ", operands types: ");
2385 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2387 dump_printf (MSG_NOTE
, ",");
2388 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2392 dump_printf (MSG_NOTE
, ",");
2393 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2399 dump_printf (MSG_NOTE
, ",");
2400 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2403 dump_printf (MSG_NOTE
, "\n");
2409 /* Check that it's ok to change the order of the computation.
2410 Generally, when vectorizing a reduction we change the order of the
2411 computation. This may change the behavior of the program in some
2412 cases, so we need to check that this is ok. One exception is when
2413 vectorizing an outer-loop: the inner-loop is executed sequentially,
2414 and therefore vectorizing reductions in the inner-loop during
2415 outer-loop vectorization is safe. */
2417 /* CHECKME: check for !flag_finite_math_only too? */
2418 if (SCALAR_FLOAT_TYPE_P (type
) && !flag_associative_math
2421 /* Changing the order of operations changes the semantics. */
2422 if (dump_enabled_p ())
2423 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2424 "reduction: unsafe fp math optimization: ");
2427 else if (INTEGRAL_TYPE_P (type
) && TYPE_OVERFLOW_TRAPS (type
)
2430 /* Changing the order of operations changes the semantics. */
2431 if (dump_enabled_p ())
2432 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2433 "reduction: unsafe int math optimization: ");
2436 else if (SAT_FIXED_POINT_TYPE_P (type
) && check_reduction
)
2438 /* Changing the order of operations changes the semantics. */
2439 if (dump_enabled_p ())
2440 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2441 "reduction: unsafe fixed-point math optimization: ");
2445 /* If we detected "res -= x[i]" earlier, rewrite it into
2446 "res += -x[i]" now. If this turns out to be useless reassoc
2447 will clean it up again. */
2448 if (orig_code
== MINUS_EXPR
)
2450 tree rhs
= gimple_assign_rhs2 (def_stmt
);
2451 tree negrhs
= make_ssa_name (TREE_TYPE (rhs
), NULL
);
2452 gimple negate_stmt
= gimple_build_assign_with_ops (NEGATE_EXPR
, negrhs
,
2454 gimple_stmt_iterator gsi
= gsi_for_stmt (def_stmt
);
2455 set_vinfo_for_stmt (negate_stmt
, new_stmt_vec_info (negate_stmt
,
2457 gsi_insert_before (&gsi
, negate_stmt
, GSI_NEW_STMT
);
2458 gimple_assign_set_rhs2 (def_stmt
, negrhs
);
2459 gimple_assign_set_rhs_code (def_stmt
, PLUS_EXPR
);
2460 update_stmt (def_stmt
);
2463 /* Reduction is safe. We're dealing with one of the following:
2464 1) integer arithmetic and no trapv
2465 2) floating point arithmetic, and special flags permit this optimization
2466 3) nested cycle (i.e., outer loop vectorization). */
2467 if (TREE_CODE (op1
) == SSA_NAME
)
2468 def1
= SSA_NAME_DEF_STMT (op1
);
2470 if (TREE_CODE (op2
) == SSA_NAME
)
2471 def2
= SSA_NAME_DEF_STMT (op2
);
2473 if (code
!= COND_EXPR
2474 && ((!def1
|| gimple_nop_p (def1
)) && (!def2
|| gimple_nop_p (def2
))))
2476 if (dump_enabled_p ())
2477 report_vect_op (MSG_NOTE
, def_stmt
, "reduction: no defs for operands: ");
2481 /* Check that one def is the reduction def, defined by PHI,
2482 the other def is either defined in the loop ("vect_internal_def"),
2483 or it's an induction (defined by a loop-header phi-node). */
2485 if (def2
&& def2
== phi
2486 && (code
== COND_EXPR
2487 || !def1
|| gimple_nop_p (def1
)
2488 || !flow_bb_inside_loop_p (loop
, gimple_bb (def1
))
2489 || (def1
&& flow_bb_inside_loop_p (loop
, gimple_bb (def1
))
2490 && (is_gimple_assign (def1
)
2491 || is_gimple_call (def1
)
2492 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
2493 == vect_induction_def
2494 || (gimple_code (def1
) == GIMPLE_PHI
2495 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
2496 == vect_internal_def
2497 && !is_loop_header_bb_p (gimple_bb (def1
)))))))
2499 if (dump_enabled_p ())
2500 report_vect_op (MSG_NOTE
, def_stmt
, "detected reduction: ");
2504 if (def1
&& def1
== phi
2505 && (code
== COND_EXPR
2506 || !def2
|| gimple_nop_p (def2
)
2507 || !flow_bb_inside_loop_p (loop
, gimple_bb (def2
))
2508 || (def2
&& flow_bb_inside_loop_p (loop
, gimple_bb (def2
))
2509 && (is_gimple_assign (def2
)
2510 || is_gimple_call (def2
)
2511 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
2512 == vect_induction_def
2513 || (gimple_code (def2
) == GIMPLE_PHI
2514 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
2515 == vect_internal_def
2516 && !is_loop_header_bb_p (gimple_bb (def2
)))))))
2518 if (check_reduction
)
2520 /* Swap operands (just for simplicity - so that the rest of the code
2521 can assume that the reduction variable is always the last (second)
2523 if (dump_enabled_p ())
2524 report_vect_op (MSG_NOTE
, def_stmt
,
2525 "detected reduction: need to swap operands: ");
2527 swap_ssa_operands (def_stmt
, gimple_assign_rhs1_ptr (def_stmt
),
2528 gimple_assign_rhs2_ptr (def_stmt
));
2530 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (def_stmt
)))
2531 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
2535 if (dump_enabled_p ())
2536 report_vect_op (MSG_NOTE
, def_stmt
, "detected reduction: ");
2542 /* Try to find SLP reduction chain. */
2543 if (check_reduction
&& vect_is_slp_reduction (loop_info
, phi
, def_stmt
))
2545 if (dump_enabled_p ())
2546 report_vect_op (MSG_NOTE
, def_stmt
,
2547 "reduction: detected reduction chain: ");
2552 if (dump_enabled_p ())
2553 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2554 "reduction: unknown pattern: ");
2559 /* Wrapper around vect_is_simple_reduction_1, that won't modify code
2560 in-place. Arguments as there. */
2563 vect_is_simple_reduction (loop_vec_info loop_info
, gimple phi
,
2564 bool check_reduction
, bool *double_reduc
)
2566 return vect_is_simple_reduction_1 (loop_info
, phi
, check_reduction
,
2567 double_reduc
, false);
2570 /* Wrapper around vect_is_simple_reduction_1, which will modify code
2571 in-place if it enables detection of more reductions. Arguments
2575 vect_force_simple_reduction (loop_vec_info loop_info
, gimple phi
,
2576 bool check_reduction
, bool *double_reduc
)
2578 return vect_is_simple_reduction_1 (loop_info
, phi
, check_reduction
,
2579 double_reduc
, true);
2582 /* Calculate the cost of one scalar iteration of the loop. */
2584 vect_get_single_scalar_iteration_cost (loop_vec_info loop_vinfo
)
2586 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2587 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
2588 int nbbs
= loop
->num_nodes
, factor
, scalar_single_iter_cost
= 0;
2589 int innerloop_iters
, i
, stmt_cost
;
2591 /* Count statements in scalar loop. Using this as scalar cost for a single
2594 TODO: Add outer loop support.
2596 TODO: Consider assigning different costs to different scalar
2600 innerloop_iters
= 1;
2602 innerloop_iters
= 50; /* FIXME */
2604 for (i
= 0; i
< nbbs
; i
++)
2606 gimple_stmt_iterator si
;
2607 basic_block bb
= bbs
[i
];
2609 if (bb
->loop_father
== loop
->inner
)
2610 factor
= innerloop_iters
;
2614 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
2616 gimple stmt
= gsi_stmt (si
);
2617 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2619 if (!is_gimple_assign (stmt
) && !is_gimple_call (stmt
))
2622 /* Skip stmts that are not vectorized inside the loop. */
2624 && !STMT_VINFO_RELEVANT_P (stmt_info
)
2625 && (!STMT_VINFO_LIVE_P (stmt_info
)
2626 || !VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
2627 && !STMT_VINFO_IN_PATTERN_P (stmt_info
))
2630 if (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
)))
2632 if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))))
2633 stmt_cost
= vect_get_stmt_cost (scalar_load
);
2635 stmt_cost
= vect_get_stmt_cost (scalar_store
);
2638 stmt_cost
= vect_get_stmt_cost (scalar_stmt
);
2640 scalar_single_iter_cost
+= stmt_cost
* factor
;
2643 return scalar_single_iter_cost
;
2646 /* Calculate cost of peeling the loop PEEL_ITERS_PROLOGUE times. */
2648 vect_get_known_peeling_cost (loop_vec_info loop_vinfo
, int peel_iters_prologue
,
2649 int *peel_iters_epilogue
,
2650 int scalar_single_iter_cost
,
2651 stmt_vector_for_cost
*prologue_cost_vec
,
2652 stmt_vector_for_cost
*epilogue_cost_vec
)
2655 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2657 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
2659 *peel_iters_epilogue
= vf
/2;
2660 if (dump_enabled_p ())
2661 dump_printf_loc (MSG_NOTE
, vect_location
,
2662 "cost model: epilogue peel iters set to vf/2 "
2663 "because loop iterations are unknown .\n");
2665 /* If peeled iterations are known but number of scalar loop
2666 iterations are unknown, count a taken branch per peeled loop. */
2667 retval
= record_stmt_cost (prologue_cost_vec
, 2, cond_branch_taken
,
2668 NULL
, 0, vect_prologue
);
2672 int niters
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
2673 peel_iters_prologue
= niters
< peel_iters_prologue
?
2674 niters
: peel_iters_prologue
;
2675 *peel_iters_epilogue
= (niters
- peel_iters_prologue
) % vf
;
2676 /* If we need to peel for gaps, but no peeling is required, we have to
2677 peel VF iterations. */
2678 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) && !*peel_iters_epilogue
)
2679 *peel_iters_epilogue
= vf
;
2682 if (peel_iters_prologue
)
2683 retval
+= record_stmt_cost (prologue_cost_vec
,
2684 peel_iters_prologue
* scalar_single_iter_cost
,
2685 scalar_stmt
, NULL
, 0, vect_prologue
);
2686 if (*peel_iters_epilogue
)
2687 retval
+= record_stmt_cost (epilogue_cost_vec
,
2688 *peel_iters_epilogue
* scalar_single_iter_cost
,
2689 scalar_stmt
, NULL
, 0, vect_epilogue
);
2693 /* Function vect_estimate_min_profitable_iters
2695 Return the number of iterations required for the vector version of the
2696 loop to be profitable relative to the cost of the scalar version of the
2700 vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo
,
2701 int *ret_min_profitable_niters
,
2702 int *ret_min_profitable_estimate
)
2704 int min_profitable_iters
;
2705 int min_profitable_estimate
;
2706 int peel_iters_prologue
;
2707 int peel_iters_epilogue
;
2708 unsigned vec_inside_cost
= 0;
2709 int vec_outside_cost
= 0;
2710 unsigned vec_prologue_cost
= 0;
2711 unsigned vec_epilogue_cost
= 0;
2712 int scalar_single_iter_cost
= 0;
2713 int scalar_outside_cost
= 0;
2714 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2715 int npeel
= LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
);
2716 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2718 /* Cost model disabled. */
2719 if (unlimited_cost_model ())
2721 dump_printf_loc (MSG_NOTE
, vect_location
, "cost model disabled.\n");
2722 *ret_min_profitable_niters
= 0;
2723 *ret_min_profitable_estimate
= 0;
2727 /* Requires loop versioning tests to handle misalignment. */
2728 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
))
2730 /* FIXME: Make cost depend on complexity of individual check. */
2731 unsigned len
= LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).length ();
2732 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
2734 dump_printf (MSG_NOTE
,
2735 "cost model: Adding cost of checks for loop "
2736 "versioning to treat misalignment.\n");
2739 /* Requires loop versioning with alias checks. */
2740 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2742 /* FIXME: Make cost depend on complexity of individual check. */
2743 unsigned len
= LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
).length ();
2744 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
2746 dump_printf (MSG_NOTE
,
2747 "cost model: Adding cost of checks for loop "
2748 "versioning aliasing.\n");
2751 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2752 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2753 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_taken
, NULL
, 0,
2756 /* Count statements in scalar loop. Using this as scalar cost for a single
2759 TODO: Add outer loop support.
2761 TODO: Consider assigning different costs to different scalar
2764 scalar_single_iter_cost
= vect_get_single_scalar_iteration_cost (loop_vinfo
);
2766 /* Add additional cost for the peeled instructions in prologue and epilogue
2769 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
2770 at compile-time - we assume it's vf/2 (the worst would be vf-1).
2772 TODO: Build an expression that represents peel_iters for prologue and
2773 epilogue to be used in a run-time test. */
2777 peel_iters_prologue
= vf
/2;
2778 dump_printf (MSG_NOTE
, "cost model: "
2779 "prologue peel iters set to vf/2.\n");
2781 /* If peeling for alignment is unknown, loop bound of main loop becomes
2783 peel_iters_epilogue
= vf
/2;
2784 dump_printf (MSG_NOTE
, "cost model: "
2785 "epilogue peel iters set to vf/2 because "
2786 "peeling for alignment is unknown.\n");
2788 /* If peeled iterations are unknown, count a taken branch and a not taken
2789 branch per peeled loop. Even if scalar loop iterations are known,
2790 vector iterations are not known since peeled prologue iterations are
2791 not known. Hence guards remain the same. */
2792 (void) add_stmt_cost (target_cost_data
, 2, cond_branch_taken
,
2793 NULL
, 0, vect_prologue
);
2794 (void) add_stmt_cost (target_cost_data
, 2, cond_branch_not_taken
,
2795 NULL
, 0, vect_prologue
);
2796 /* FORNOW: Don't attempt to pass individual scalar instructions to
2797 the model; just assume linear cost for scalar iterations. */
2798 (void) add_stmt_cost (target_cost_data
,
2799 peel_iters_prologue
* scalar_single_iter_cost
,
2800 scalar_stmt
, NULL
, 0, vect_prologue
);
2801 (void) add_stmt_cost (target_cost_data
,
2802 peel_iters_epilogue
* scalar_single_iter_cost
,
2803 scalar_stmt
, NULL
, 0, vect_epilogue
);
2807 stmt_vector_for_cost prologue_cost_vec
, epilogue_cost_vec
;
2808 stmt_info_for_cost
*si
;
2810 void *data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2812 prologue_cost_vec
.create (2);
2813 epilogue_cost_vec
.create (2);
2814 peel_iters_prologue
= npeel
;
2816 (void) vect_get_known_peeling_cost (loop_vinfo
, peel_iters_prologue
,
2817 &peel_iters_epilogue
,
2818 scalar_single_iter_cost
,
2820 &epilogue_cost_vec
);
2822 FOR_EACH_VEC_ELT (prologue_cost_vec
, j
, si
)
2824 struct _stmt_vec_info
*stmt_info
2825 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
2826 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
2827 si
->misalign
, vect_prologue
);
2830 FOR_EACH_VEC_ELT (epilogue_cost_vec
, j
, si
)
2832 struct _stmt_vec_info
*stmt_info
2833 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
2834 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
2835 si
->misalign
, vect_epilogue
);
2838 prologue_cost_vec
.release ();
2839 epilogue_cost_vec
.release ();
2842 /* FORNOW: The scalar outside cost is incremented in one of the
2845 1. The vectorizer checks for alignment and aliasing and generates
2846 a condition that allows dynamic vectorization. A cost model
2847 check is ANDED with the versioning condition. Hence scalar code
2848 path now has the added cost of the versioning check.
2850 if (cost > th & versioning_check)
2853 Hence run-time scalar is incremented by not-taken branch cost.
2855 2. The vectorizer then checks if a prologue is required. If the
2856 cost model check was not done before during versioning, it has to
2857 be done before the prologue check.
2860 prologue = scalar_iters
2865 if (prologue == num_iters)
2868 Hence the run-time scalar cost is incremented by a taken branch,
2869 plus a not-taken branch, plus a taken branch cost.
2871 3. The vectorizer then checks if an epilogue is required. If the
2872 cost model check was not done before during prologue check, it
2873 has to be done with the epilogue check.
2879 if (prologue == num_iters)
2882 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
2885 Hence the run-time scalar cost should be incremented by 2 taken
2888 TODO: The back end may reorder the BBS's differently and reverse
2889 conditions/branch directions. Change the estimates below to
2890 something more reasonable. */
2892 /* If the number of iterations is known and we do not do versioning, we can
2893 decide whether to vectorize at compile time. Hence the scalar version
2894 do not carry cost model guard costs. */
2895 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
2896 || LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2897 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2899 /* Cost model check occurs at versioning. */
2900 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2901 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2902 scalar_outside_cost
+= vect_get_stmt_cost (cond_branch_not_taken
);
2905 /* Cost model check occurs at prologue generation. */
2906 if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
) < 0)
2907 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
)
2908 + vect_get_stmt_cost (cond_branch_not_taken
);
2909 /* Cost model check occurs at epilogue generation. */
2911 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
);
2915 /* Complete the target-specific cost calculations. */
2916 finish_cost (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
), &vec_prologue_cost
,
2917 &vec_inside_cost
, &vec_epilogue_cost
);
2919 vec_outside_cost
= (int)(vec_prologue_cost
+ vec_epilogue_cost
);
2921 /* Calculate number of iterations required to make the vector version
2922 profitable, relative to the loop bodies only. The following condition
2924 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
2926 SIC = scalar iteration cost, VIC = vector iteration cost,
2927 VOC = vector outside cost, VF = vectorization factor,
2928 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
2929 SOC = scalar outside cost for run time cost model check. */
2931 if ((scalar_single_iter_cost
* vf
) > (int) vec_inside_cost
)
2933 if (vec_outside_cost
<= 0)
2934 min_profitable_iters
= 1;
2937 min_profitable_iters
= ((vec_outside_cost
- scalar_outside_cost
) * vf
2938 - vec_inside_cost
* peel_iters_prologue
2939 - vec_inside_cost
* peel_iters_epilogue
)
2940 / ((scalar_single_iter_cost
* vf
)
2943 if ((scalar_single_iter_cost
* vf
* min_profitable_iters
)
2944 <= (((int) vec_inside_cost
* min_profitable_iters
)
2945 + (((int) vec_outside_cost
- scalar_outside_cost
) * vf
)))
2946 min_profitable_iters
++;
2949 /* vector version will never be profitable. */
2952 if (dump_enabled_p ())
2953 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2954 "cost model: the vector iteration cost = %d "
2955 "divided by the scalar iteration cost = %d "
2956 "is greater or equal to the vectorization factor = %d"
2958 vec_inside_cost
, scalar_single_iter_cost
, vf
);
2959 *ret_min_profitable_niters
= -1;
2960 *ret_min_profitable_estimate
= -1;
2964 if (dump_enabled_p ())
2966 dump_printf_loc (MSG_NOTE
, vect_location
, "Cost model analysis: \n");
2967 dump_printf (MSG_NOTE
, " Vector inside of loop cost: %d\n",
2969 dump_printf (MSG_NOTE
, " Vector prologue cost: %d\n",
2971 dump_printf (MSG_NOTE
, " Vector epilogue cost: %d\n",
2973 dump_printf (MSG_NOTE
, " Scalar iteration cost: %d\n",
2974 scalar_single_iter_cost
);
2975 dump_printf (MSG_NOTE
, " Scalar outside cost: %d\n",
2976 scalar_outside_cost
);
2977 dump_printf (MSG_NOTE
, " Vector outside cost: %d\n",
2979 dump_printf (MSG_NOTE
, " prologue iterations: %d\n",
2980 peel_iters_prologue
);
2981 dump_printf (MSG_NOTE
, " epilogue iterations: %d\n",
2982 peel_iters_epilogue
);
2983 dump_printf (MSG_NOTE
,
2984 " Calculated minimum iters for profitability: %d\n",
2985 min_profitable_iters
);
2986 dump_printf (MSG_NOTE
, "\n");
2989 min_profitable_iters
=
2990 min_profitable_iters
< vf
? vf
: min_profitable_iters
;
2992 /* Because the condition we create is:
2993 if (niters <= min_profitable_iters)
2994 then skip the vectorized loop. */
2995 min_profitable_iters
--;
2997 if (dump_enabled_p ())
2998 dump_printf_loc (MSG_NOTE
, vect_location
,
2999 " Runtime profitability threshold = %d\n",
3000 min_profitable_iters
);
3002 *ret_min_profitable_niters
= min_profitable_iters
;
3004 /* Calculate number of iterations required to make the vector version
3005 profitable, relative to the loop bodies only.
3007 Non-vectorized variant is SIC * niters and it must win over vector
3008 variant on the expected loop trip count. The following condition must hold true:
3009 SIC * niters > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC + SOC */
3011 if (vec_outside_cost
<= 0)
3012 min_profitable_estimate
= 1;
3015 min_profitable_estimate
= ((vec_outside_cost
+ scalar_outside_cost
) * vf
3016 - vec_inside_cost
* peel_iters_prologue
3017 - vec_inside_cost
* peel_iters_epilogue
)
3018 / ((scalar_single_iter_cost
* vf
)
3021 min_profitable_estimate
--;
3022 min_profitable_estimate
= MAX (min_profitable_estimate
, min_profitable_iters
);
3023 if (dump_enabled_p ())
3024 dump_printf_loc (MSG_NOTE
, vect_location
,
3025 " Static estimate profitability threshold = %d\n",
3026 min_profitable_iters
);
3028 *ret_min_profitable_estimate
= min_profitable_estimate
;
3032 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
3033 functions. Design better to avoid maintenance issues. */
3035 /* Function vect_model_reduction_cost.
3037 Models cost for a reduction operation, including the vector ops
3038 generated within the strip-mine loop, the initial definition before
3039 the loop, and the epilogue code that must be generated. */
3042 vect_model_reduction_cost (stmt_vec_info stmt_info
, enum tree_code reduc_code
,
3045 int prologue_cost
= 0, epilogue_cost
= 0;
3046 enum tree_code code
;
3049 gimple stmt
, orig_stmt
;
3051 enum machine_mode mode
;
3052 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3053 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3054 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3056 /* Cost of reduction op inside loop. */
3057 unsigned inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
3058 stmt_info
, 0, vect_body
);
3059 stmt
= STMT_VINFO_STMT (stmt_info
);
3061 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3063 case GIMPLE_SINGLE_RHS
:
3064 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
)) == ternary_op
);
3065 reduction_op
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
3067 case GIMPLE_UNARY_RHS
:
3068 reduction_op
= gimple_assign_rhs1 (stmt
);
3070 case GIMPLE_BINARY_RHS
:
3071 reduction_op
= gimple_assign_rhs2 (stmt
);
3073 case GIMPLE_TERNARY_RHS
:
3074 reduction_op
= gimple_assign_rhs3 (stmt
);
3080 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
3083 if (dump_enabled_p ())
3085 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3086 "unsupported data-type ");
3087 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
3088 TREE_TYPE (reduction_op
));
3089 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3094 mode
= TYPE_MODE (vectype
);
3095 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
3098 orig_stmt
= STMT_VINFO_STMT (stmt_info
);
3100 code
= gimple_assign_rhs_code (orig_stmt
);
3102 /* Add in cost for initial definition. */
3103 prologue_cost
+= add_stmt_cost (target_cost_data
, 1, scalar_to_vec
,
3104 stmt_info
, 0, vect_prologue
);
3106 /* Determine cost of epilogue code.
3108 We have a reduction operator that will reduce the vector in one statement.
3109 Also requires scalar extract. */
3111 if (!nested_in_vect_loop_p (loop
, orig_stmt
))
3113 if (reduc_code
!= ERROR_MARK
)
3115 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1, vector_stmt
,
3116 stmt_info
, 0, vect_epilogue
);
3117 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1, vec_to_scalar
,
3118 stmt_info
, 0, vect_epilogue
);
3122 int vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
3124 TYPE_SIZE (TREE_TYPE (gimple_assign_lhs (orig_stmt
)));
3125 int element_bitsize
= tree_to_uhwi (bitsize
);
3126 int nelements
= vec_size_in_bits
/ element_bitsize
;
3128 optab
= optab_for_tree_code (code
, vectype
, optab_default
);
3130 /* We have a whole vector shift available. */
3131 if (VECTOR_MODE_P (mode
)
3132 && optab_handler (optab
, mode
) != CODE_FOR_nothing
3133 && optab_handler (vec_shr_optab
, mode
) != CODE_FOR_nothing
)
3135 /* Final reduction via vector shifts and the reduction operator.
3136 Also requires scalar extract. */
3137 epilogue_cost
+= add_stmt_cost (target_cost_data
,
3138 exact_log2 (nelements
) * 2,
3139 vector_stmt
, stmt_info
, 0,
3141 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1,
3142 vec_to_scalar
, stmt_info
, 0,
3146 /* Use extracts and reduction op for final reduction. For N
3147 elements, we have N extracts and N-1 reduction ops. */
3148 epilogue_cost
+= add_stmt_cost (target_cost_data
,
3149 nelements
+ nelements
- 1,
3150 vector_stmt
, stmt_info
, 0,
3155 if (dump_enabled_p ())
3156 dump_printf (MSG_NOTE
,
3157 "vect_model_reduction_cost: inside_cost = %d, "
3158 "prologue_cost = %d, epilogue_cost = %d .\n", inside_cost
,
3159 prologue_cost
, epilogue_cost
);
3165 /* Function vect_model_induction_cost.
3167 Models cost for induction operations. */
3170 vect_model_induction_cost (stmt_vec_info stmt_info
, int ncopies
)
3172 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3173 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3174 unsigned inside_cost
, prologue_cost
;
3176 /* loop cost for vec_loop. */
3177 inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
3178 stmt_info
, 0, vect_body
);
3180 /* prologue cost for vec_init and vec_step. */
3181 prologue_cost
= add_stmt_cost (target_cost_data
, 2, scalar_to_vec
,
3182 stmt_info
, 0, vect_prologue
);
3184 if (dump_enabled_p ())
3185 dump_printf_loc (MSG_NOTE
, vect_location
,
3186 "vect_model_induction_cost: inside_cost = %d, "
3187 "prologue_cost = %d .\n", inside_cost
, prologue_cost
);
3191 /* Function get_initial_def_for_induction
3194 STMT - a stmt that performs an induction operation in the loop.
3195 IV_PHI - the initial value of the induction variable
3198 Return a vector variable, initialized with the first VF values of
3199 the induction variable. E.g., for an iv with IV_PHI='X' and
3200 evolution S, for a vector of 4 units, we want to return:
3201 [X, X + S, X + 2*S, X + 3*S]. */
3204 get_initial_def_for_induction (gimple iv_phi
)
3206 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (iv_phi
);
3207 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
3208 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3211 edge pe
= loop_preheader_edge (loop
);
3212 struct loop
*iv_loop
;
3214 tree new_vec
, vec_init
, vec_step
, t
;
3217 gimple init_stmt
, induction_phi
, new_stmt
;
3218 tree induc_def
, vec_def
, vec_dest
;
3219 tree init_expr
, step_expr
;
3220 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3224 stmt_vec_info phi_info
= vinfo_for_stmt (iv_phi
);
3225 bool nested_in_vect_loop
= false;
3226 gimple_seq stmts
= NULL
;
3227 imm_use_iterator imm_iter
;
3228 use_operand_p use_p
;
3232 gimple_stmt_iterator si
;
3233 basic_block bb
= gimple_bb (iv_phi
);
3237 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
3238 if (nested_in_vect_loop_p (loop
, iv_phi
))
3240 nested_in_vect_loop
= true;
3241 iv_loop
= loop
->inner
;
3245 gcc_assert (iv_loop
== (gimple_bb (iv_phi
))->loop_father
);
3247 latch_e
= loop_latch_edge (iv_loop
);
3248 loop_arg
= PHI_ARG_DEF_FROM_EDGE (iv_phi
, latch_e
);
3250 step_expr
= STMT_VINFO_LOOP_PHI_EVOLUTION_PART (phi_info
);
3251 gcc_assert (step_expr
!= NULL_TREE
);
3253 pe
= loop_preheader_edge (iv_loop
);
3254 init_expr
= PHI_ARG_DEF_FROM_EDGE (iv_phi
,
3255 loop_preheader_edge (iv_loop
));
3257 vectype
= get_vectype_for_scalar_type (TREE_TYPE (init_expr
));
3258 resvectype
= get_vectype_for_scalar_type (TREE_TYPE (PHI_RESULT (iv_phi
)));
3259 gcc_assert (vectype
);
3260 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3261 ncopies
= vf
/ nunits
;
3263 gcc_assert (phi_info
);
3264 gcc_assert (ncopies
>= 1);
3266 /* Convert the step to the desired type. */
3267 step_expr
= force_gimple_operand (fold_convert (TREE_TYPE (vectype
),
3269 &stmts
, true, NULL_TREE
);
3272 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
3273 gcc_assert (!new_bb
);
3276 /* Find the first insertion point in the BB. */
3277 si
= gsi_after_labels (bb
);
3279 /* Create the vector that holds the initial_value of the induction. */
3280 if (nested_in_vect_loop
)
3282 /* iv_loop is nested in the loop to be vectorized. init_expr had already
3283 been created during vectorization of previous stmts. We obtain it
3284 from the STMT_VINFO_VEC_STMT of the defining stmt. */
3285 vec_init
= vect_get_vec_def_for_operand (init_expr
, iv_phi
, NULL
);
3286 /* If the initial value is not of proper type, convert it. */
3287 if (!useless_type_conversion_p (vectype
, TREE_TYPE (vec_init
)))
3289 new_stmt
= gimple_build_assign_with_ops
3291 vect_get_new_vect_var (vectype
, vect_simple_var
, "vec_iv_"),
3292 build1 (VIEW_CONVERT_EXPR
, vectype
, vec_init
), NULL_TREE
);
3293 vec_init
= make_ssa_name (gimple_assign_lhs (new_stmt
), new_stmt
);
3294 gimple_assign_set_lhs (new_stmt
, vec_init
);
3295 new_bb
= gsi_insert_on_edge_immediate (loop_preheader_edge (iv_loop
),
3297 gcc_assert (!new_bb
);
3298 set_vinfo_for_stmt (new_stmt
,
3299 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
3304 vec
<constructor_elt
, va_gc
> *v
;
3306 /* iv_loop is the loop to be vectorized. Create:
3307 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
3308 new_var
= vect_get_new_vect_var (TREE_TYPE (vectype
),
3309 vect_scalar_var
, "var_");
3310 new_name
= force_gimple_operand (fold_convert (TREE_TYPE (vectype
),
3312 &stmts
, false, new_var
);
3315 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
3316 gcc_assert (!new_bb
);
3319 vec_alloc (v
, nunits
);
3320 bool constant_p
= is_gimple_min_invariant (new_name
);
3321 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
3322 for (i
= 1; i
< nunits
; i
++)
3324 /* Create: new_name_i = new_name + step_expr */
3325 new_name
= fold_build2 (PLUS_EXPR
, TREE_TYPE (new_name
),
3326 new_name
, step_expr
);
3327 if (!is_gimple_min_invariant (new_name
))
3329 init_stmt
= gimple_build_assign (new_var
, new_name
);
3330 new_name
= make_ssa_name (new_var
, init_stmt
);
3331 gimple_assign_set_lhs (init_stmt
, new_name
);
3332 new_bb
= gsi_insert_on_edge_immediate (pe
, init_stmt
);
3333 gcc_assert (!new_bb
);
3334 if (dump_enabled_p ())
3336 dump_printf_loc (MSG_NOTE
, vect_location
,
3337 "created new init_stmt: ");
3338 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, init_stmt
, 0);
3339 dump_printf (MSG_NOTE
, "\n");
3343 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
3345 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
3347 new_vec
= build_vector_from_ctor (vectype
, v
);
3349 new_vec
= build_constructor (vectype
, v
);
3350 vec_init
= vect_init_vector (iv_phi
, new_vec
, vectype
, NULL
);
3354 /* Create the vector that holds the step of the induction. */
3355 if (nested_in_vect_loop
)
3356 /* iv_loop is nested in the loop to be vectorized. Generate:
3357 vec_step = [S, S, S, S] */
3358 new_name
= step_expr
;
3361 /* iv_loop is the loop to be vectorized. Generate:
3362 vec_step = [VF*S, VF*S, VF*S, VF*S] */
3363 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
)))
3365 expr
= build_int_cst (integer_type_node
, vf
);
3366 expr
= fold_convert (TREE_TYPE (step_expr
), expr
);
3369 expr
= build_int_cst (TREE_TYPE (step_expr
), vf
);
3370 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
3372 if (TREE_CODE (step_expr
) == SSA_NAME
)
3373 new_name
= vect_init_vector (iv_phi
, new_name
,
3374 TREE_TYPE (step_expr
), NULL
);
3377 t
= unshare_expr (new_name
);
3378 gcc_assert (CONSTANT_CLASS_P (new_name
)
3379 || TREE_CODE (new_name
) == SSA_NAME
);
3380 stepvectype
= get_vectype_for_scalar_type (TREE_TYPE (new_name
));
3381 gcc_assert (stepvectype
);
3382 new_vec
= build_vector_from_val (stepvectype
, t
);
3383 vec_step
= vect_init_vector (iv_phi
, new_vec
, stepvectype
, NULL
);
3386 /* Create the following def-use cycle:
3391 vec_iv = PHI <vec_init, vec_loop>
3395 vec_loop = vec_iv + vec_step; */
3397 /* Create the induction-phi that defines the induction-operand. */
3398 vec_dest
= vect_get_new_vect_var (vectype
, vect_simple_var
, "vec_iv_");
3399 induction_phi
= create_phi_node (vec_dest
, iv_loop
->header
);
3400 set_vinfo_for_stmt (induction_phi
,
3401 new_stmt_vec_info (induction_phi
, loop_vinfo
, NULL
));
3402 induc_def
= PHI_RESULT (induction_phi
);
3404 /* Create the iv update inside the loop */
3405 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, vec_dest
,
3406 induc_def
, vec_step
);
3407 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
3408 gimple_assign_set_lhs (new_stmt
, vec_def
);
3409 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3410 set_vinfo_for_stmt (new_stmt
, new_stmt_vec_info (new_stmt
, loop_vinfo
,
3413 /* Set the arguments of the phi node: */
3414 add_phi_arg (induction_phi
, vec_init
, pe
, UNKNOWN_LOCATION
);
3415 add_phi_arg (induction_phi
, vec_def
, loop_latch_edge (iv_loop
),
3419 /* In case that vectorization factor (VF) is bigger than the number
3420 of elements that we can fit in a vectype (nunits), we have to generate
3421 more than one vector stmt - i.e - we need to "unroll" the
3422 vector stmt by a factor VF/nunits. For more details see documentation
3423 in vectorizable_operation. */
3427 stmt_vec_info prev_stmt_vinfo
;
3428 /* FORNOW. This restriction should be relaxed. */
3429 gcc_assert (!nested_in_vect_loop
);
3431 /* Create the vector that holds the step of the induction. */
3432 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
)))
3434 expr
= build_int_cst (integer_type_node
, nunits
);
3435 expr
= fold_convert (TREE_TYPE (step_expr
), expr
);
3438 expr
= build_int_cst (TREE_TYPE (step_expr
), nunits
);
3439 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
3441 if (TREE_CODE (step_expr
) == SSA_NAME
)
3442 new_name
= vect_init_vector (iv_phi
, new_name
,
3443 TREE_TYPE (step_expr
), NULL
);
3444 t
= unshare_expr (new_name
);
3445 gcc_assert (CONSTANT_CLASS_P (new_name
)
3446 || TREE_CODE (new_name
) == SSA_NAME
);
3447 new_vec
= build_vector_from_val (stepvectype
, t
);
3448 vec_step
= vect_init_vector (iv_phi
, new_vec
, stepvectype
, NULL
);
3450 vec_def
= induc_def
;
3451 prev_stmt_vinfo
= vinfo_for_stmt (induction_phi
);
3452 for (i
= 1; i
< ncopies
; i
++)
3454 /* vec_i = vec_prev + vec_step */
3455 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, vec_dest
,
3457 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
3458 gimple_assign_set_lhs (new_stmt
, vec_def
);
3460 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3461 if (!useless_type_conversion_p (resvectype
, vectype
))
3463 new_stmt
= gimple_build_assign_with_ops
3465 vect_get_new_vect_var (resvectype
, vect_simple_var
,
3467 build1 (VIEW_CONVERT_EXPR
, resvectype
,
3468 gimple_assign_lhs (new_stmt
)), NULL_TREE
);
3469 gimple_assign_set_lhs (new_stmt
,
3471 (gimple_assign_lhs (new_stmt
), new_stmt
));
3472 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3474 set_vinfo_for_stmt (new_stmt
,
3475 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
3476 STMT_VINFO_RELATED_STMT (prev_stmt_vinfo
) = new_stmt
;
3477 prev_stmt_vinfo
= vinfo_for_stmt (new_stmt
);
3481 if (nested_in_vect_loop
)
3483 /* Find the loop-closed exit-phi of the induction, and record
3484 the final vector of induction results: */
3486 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
3488 if (!flow_bb_inside_loop_p (iv_loop
, gimple_bb (USE_STMT (use_p
))))
3490 exit_phi
= USE_STMT (use_p
);
3496 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (exit_phi
);
3497 /* FORNOW. Currently not supporting the case that an inner-loop induction
3498 is not used in the outer-loop (i.e. only outside the outer-loop). */
3499 gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo
)
3500 && !STMT_VINFO_LIVE_P (stmt_vinfo
));
3502 STMT_VINFO_VEC_STMT (stmt_vinfo
) = new_stmt
;
3503 if (dump_enabled_p ())
3505 dump_printf_loc (MSG_NOTE
, vect_location
,
3506 "vector of inductions after inner-loop:");
3507 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, new_stmt
, 0);
3508 dump_printf (MSG_NOTE
, "\n");
3514 if (dump_enabled_p ())
3516 dump_printf_loc (MSG_NOTE
, vect_location
,
3517 "transform induction: created def-use cycle: ");
3518 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, induction_phi
, 0);
3519 dump_printf (MSG_NOTE
, "\n");
3520 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
3521 SSA_NAME_DEF_STMT (vec_def
), 0);
3522 dump_printf (MSG_NOTE
, "\n");
3525 STMT_VINFO_VEC_STMT (phi_info
) = induction_phi
;
3526 if (!useless_type_conversion_p (resvectype
, vectype
))
3528 new_stmt
= gimple_build_assign_with_ops
3530 vect_get_new_vect_var (resvectype
, vect_simple_var
, "vec_iv_"),
3531 build1 (VIEW_CONVERT_EXPR
, resvectype
, induc_def
), NULL_TREE
);
3532 induc_def
= make_ssa_name (gimple_assign_lhs (new_stmt
), new_stmt
);
3533 gimple_assign_set_lhs (new_stmt
, induc_def
);
3534 si
= gsi_after_labels (bb
);
3535 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3536 set_vinfo_for_stmt (new_stmt
,
3537 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
3538 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_stmt
))
3539 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (induction_phi
));
3546 /* Function get_initial_def_for_reduction
3549 STMT - a stmt that performs a reduction operation in the loop.
3550 INIT_VAL - the initial value of the reduction variable
3553 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
3554 of the reduction (used for adjusting the epilog - see below).
3555 Return a vector variable, initialized according to the operation that STMT
3556 performs. This vector will be used as the initial value of the
3557 vector of partial results.
3559 Option1 (adjust in epilog): Initialize the vector as follows:
3560 add/bit or/xor: [0,0,...,0,0]
3561 mult/bit and: [1,1,...,1,1]
3562 min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
3563 and when necessary (e.g. add/mult case) let the caller know
3564 that it needs to adjust the result by init_val.
3566 Option2: Initialize the vector as follows:
3567 add/bit or/xor: [init_val,0,0,...,0]
3568 mult/bit and: [init_val,1,1,...,1]
3569 min/max/cond_expr: [init_val,init_val,...,init_val]
3570 and no adjustments are needed.
3572 For example, for the following code:
3578 STMT is 's = s + a[i]', and the reduction variable is 's'.
3579 For a vector of 4 units, we want to return either [0,0,0,init_val],
3580 or [0,0,0,0] and let the caller know that it needs to adjust
3581 the result at the end by 'init_val'.
3583 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
3584 initialization vector is simpler (same element in all entries), if
3585 ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
3587 A cost model should help decide between these two schemes. */
3590 get_initial_def_for_reduction (gimple stmt
, tree init_val
,
3591 tree
*adjustment_def
)
3593 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
3594 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
3595 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3596 tree scalar_type
= TREE_TYPE (init_val
);
3597 tree vectype
= get_vectype_for_scalar_type (scalar_type
);
3599 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3604 bool nested_in_vect_loop
= false;
3606 REAL_VALUE_TYPE real_init_val
= dconst0
;
3607 int int_init_val
= 0;
3608 gimple def_stmt
= NULL
;
3610 gcc_assert (vectype
);
3611 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3613 gcc_assert (POINTER_TYPE_P (scalar_type
) || INTEGRAL_TYPE_P (scalar_type
)
3614 || SCALAR_FLOAT_TYPE_P (scalar_type
));
3616 if (nested_in_vect_loop_p (loop
, stmt
))
3617 nested_in_vect_loop
= true;
3619 gcc_assert (loop
== (gimple_bb (stmt
))->loop_father
);
3621 /* In case of double reduction we only create a vector variable to be put
3622 in the reduction phi node. The actual statement creation is done in
3623 vect_create_epilog_for_reduction. */
3624 if (adjustment_def
&& nested_in_vect_loop
3625 && TREE_CODE (init_val
) == SSA_NAME
3626 && (def_stmt
= SSA_NAME_DEF_STMT (init_val
))
3627 && gimple_code (def_stmt
) == GIMPLE_PHI
3628 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
3629 && vinfo_for_stmt (def_stmt
)
3630 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
3631 == vect_double_reduction_def
)
3633 *adjustment_def
= NULL
;
3634 return vect_create_destination_var (init_val
, vectype
);
3637 if (TREE_CONSTANT (init_val
))
3639 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
3640 init_value
= build_real (scalar_type
, TREE_REAL_CST (init_val
));
3642 init_value
= build_int_cst (scalar_type
, TREE_INT_CST_LOW (init_val
));
3645 init_value
= init_val
;
3649 case WIDEN_SUM_EXPR
:
3657 /* ADJUSMENT_DEF is NULL when called from
3658 vect_create_epilog_for_reduction to vectorize double reduction. */
3661 if (nested_in_vect_loop
)
3662 *adjustment_def
= vect_get_vec_def_for_operand (init_val
, stmt
,
3665 *adjustment_def
= init_val
;
3668 if (code
== MULT_EXPR
)
3670 real_init_val
= dconst1
;
3674 if (code
== BIT_AND_EXPR
)
3677 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
3678 def_for_init
= build_real (scalar_type
, real_init_val
);
3680 def_for_init
= build_int_cst (scalar_type
, int_init_val
);
3682 /* Create a vector of '0' or '1' except the first element. */
3683 elts
= XALLOCAVEC (tree
, nunits
);
3684 for (i
= nunits
- 2; i
>= 0; --i
)
3685 elts
[i
+ 1] = def_for_init
;
3687 /* Option1: the first element is '0' or '1' as well. */
3690 elts
[0] = def_for_init
;
3691 init_def
= build_vector (vectype
, elts
);
3695 /* Option2: the first element is INIT_VAL. */
3697 if (TREE_CONSTANT (init_val
))
3698 init_def
= build_vector (vectype
, elts
);
3701 vec
<constructor_elt
, va_gc
> *v
;
3702 vec_alloc (v
, nunits
);
3703 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, init_val
);
3704 for (i
= 1; i
< nunits
; ++i
)
3705 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[i
]);
3706 init_def
= build_constructor (vectype
, v
);
3716 *adjustment_def
= NULL_TREE
;
3717 init_def
= vect_get_vec_def_for_operand (init_val
, stmt
, NULL
);
3721 init_def
= build_vector_from_val (vectype
, init_value
);
3732 /* Function vect_create_epilog_for_reduction
3734 Create code at the loop-epilog to finalize the result of a reduction
3737 VECT_DEFS is list of vector of partial results, i.e., the lhs's of vector
3738 reduction statements.
3739 STMT is the scalar reduction stmt that is being vectorized.
3740 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
3741 number of elements that we can fit in a vectype (nunits). In this case
3742 we have to generate more than one vector stmt - i.e - we need to "unroll"
3743 the vector stmt by a factor VF/nunits. For more details see documentation
3744 in vectorizable_operation.
3745 REDUC_CODE is the tree-code for the epilog reduction.
3746 REDUCTION_PHIS is a list of the phi-nodes that carry the reduction
3748 REDUC_INDEX is the index of the operand in the right hand side of the
3749 statement that is defined by REDUCTION_PHI.
3750 DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
3751 SLP_NODE is an SLP node containing a group of reduction statements. The
3752 first one in this group is STMT.
3755 1. Creates the reduction def-use cycles: sets the arguments for
3757 The loop-entry argument is the vectorized initial-value of the reduction.
3758 The loop-latch argument is taken from VECT_DEFS - the vector of partial
3760 2. "Reduces" each vector of partial results VECT_DEFS into a single result,
3761 by applying the operation specified by REDUC_CODE if available, or by
3762 other means (whole-vector shifts or a scalar loop).
3763 The function also creates a new phi node at the loop exit to preserve
3764 loop-closed form, as illustrated below.
3766 The flow at the entry to this function:
3769 vec_def = phi <null, null> # REDUCTION_PHI
3770 VECT_DEF = vector_stmt # vectorized form of STMT
3771 s_loop = scalar_stmt # (scalar) STMT
3773 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3777 The above is transformed by this function into:
3780 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3781 VECT_DEF = vector_stmt # vectorized form of STMT
3782 s_loop = scalar_stmt # (scalar) STMT
3784 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3785 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3786 v_out2 = reduce <v_out1>
3787 s_out3 = extract_field <v_out2, 0>
3788 s_out4 = adjust_result <s_out3>
3794 vect_create_epilog_for_reduction (vec
<tree
> vect_defs
, gimple stmt
,
3795 int ncopies
, enum tree_code reduc_code
,
3796 vec
<gimple
> reduction_phis
,
3797 int reduc_index
, bool double_reduc
,
3800 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3801 stmt_vec_info prev_phi_info
;
3803 enum machine_mode mode
;
3804 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3805 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
), *outer_loop
= NULL
;
3806 basic_block exit_bb
;
3809 gimple new_phi
= NULL
, phi
;
3810 gimple_stmt_iterator exit_gsi
;
3812 tree new_temp
= NULL_TREE
, new_dest
, new_name
, new_scalar_dest
;
3813 gimple epilog_stmt
= NULL
;
3814 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3816 tree bitsize
, bitpos
;
3817 tree adjustment_def
= NULL
;
3818 tree vec_initial_def
= NULL
;
3819 tree reduction_op
, expr
, def
;
3820 tree orig_name
, scalar_result
;
3821 imm_use_iterator imm_iter
, phi_imm_iter
;
3822 use_operand_p use_p
, phi_use_p
;
3823 bool extract_scalar_result
= false;
3824 gimple use_stmt
, orig_stmt
, reduction_phi
= NULL
;
3825 bool nested_in_vect_loop
= false;
3826 auto_vec
<gimple
> new_phis
;
3827 auto_vec
<gimple
> inner_phis
;
3828 enum vect_def_type dt
= vect_unknown_def_type
;
3830 auto_vec
<tree
> scalar_results
;
3831 unsigned int group_size
= 1, k
, ratio
;
3832 auto_vec
<tree
> vec_initial_defs
;
3833 auto_vec
<gimple
> phis
;
3834 bool slp_reduc
= false;
3835 tree new_phi_result
;
3836 gimple inner_phi
= NULL
;
3839 group_size
= SLP_TREE_SCALAR_STMTS (slp_node
).length ();
3841 if (nested_in_vect_loop_p (loop
, stmt
))
3845 nested_in_vect_loop
= true;
3846 gcc_assert (!slp_node
);
3849 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3851 case GIMPLE_SINGLE_RHS
:
3852 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
))
3854 reduction_op
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), reduc_index
);
3856 case GIMPLE_UNARY_RHS
:
3857 reduction_op
= gimple_assign_rhs1 (stmt
);
3859 case GIMPLE_BINARY_RHS
:
3860 reduction_op
= reduc_index
?
3861 gimple_assign_rhs2 (stmt
) : gimple_assign_rhs1 (stmt
);
3863 case GIMPLE_TERNARY_RHS
:
3864 reduction_op
= gimple_op (stmt
, reduc_index
+ 1);
3870 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
3871 gcc_assert (vectype
);
3872 mode
= TYPE_MODE (vectype
);
3874 /* 1. Create the reduction def-use cycle:
3875 Set the arguments of REDUCTION_PHIS, i.e., transform
3878 vec_def = phi <null, null> # REDUCTION_PHI
3879 VECT_DEF = vector_stmt # vectorized form of STMT
3885 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3886 VECT_DEF = vector_stmt # vectorized form of STMT
3889 (in case of SLP, do it for all the phis). */
3891 /* Get the loop-entry arguments. */
3893 vect_get_vec_defs (reduction_op
, NULL_TREE
, stmt
, &vec_initial_defs
,
3894 NULL
, slp_node
, reduc_index
);
3897 vec_initial_defs
.create (1);
3898 /* For the case of reduction, vect_get_vec_def_for_operand returns
3899 the scalar def before the loop, that defines the initial value
3900 of the reduction variable. */
3901 vec_initial_def
= vect_get_vec_def_for_operand (reduction_op
, stmt
,
3903 vec_initial_defs
.quick_push (vec_initial_def
);
3906 /* Set phi nodes arguments. */
3907 FOR_EACH_VEC_ELT (reduction_phis
, i
, phi
)
3909 tree vec_init_def
= vec_initial_defs
[i
];
3910 tree def
= vect_defs
[i
];
3911 for (j
= 0; j
< ncopies
; j
++)
3913 /* Set the loop-entry arg of the reduction-phi. */
3914 add_phi_arg (phi
, vec_init_def
, loop_preheader_edge (loop
),
3917 /* Set the loop-latch arg for the reduction-phi. */
3919 def
= vect_get_vec_def_for_stmt_copy (vect_unknown_def_type
, def
);
3921 add_phi_arg (phi
, def
, loop_latch_edge (loop
), UNKNOWN_LOCATION
);
3923 if (dump_enabled_p ())
3925 dump_printf_loc (MSG_NOTE
, vect_location
,
3926 "transform reduction: created def-use cycle: ");
3927 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
3928 dump_printf (MSG_NOTE
, "\n");
3929 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, SSA_NAME_DEF_STMT (def
), 0);
3930 dump_printf (MSG_NOTE
, "\n");
3933 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
3937 /* 2. Create epilog code.
3938 The reduction epilog code operates across the elements of the vector
3939 of partial results computed by the vectorized loop.
3940 The reduction epilog code consists of:
3942 step 1: compute the scalar result in a vector (v_out2)
3943 step 2: extract the scalar result (s_out3) from the vector (v_out2)
3944 step 3: adjust the scalar result (s_out3) if needed.
3946 Step 1 can be accomplished using one the following three schemes:
3947 (scheme 1) using reduc_code, if available.
3948 (scheme 2) using whole-vector shifts, if available.
3949 (scheme 3) using a scalar loop. In this case steps 1+2 above are
3952 The overall epilog code looks like this:
3954 s_out0 = phi <s_loop> # original EXIT_PHI
3955 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3956 v_out2 = reduce <v_out1> # step 1
3957 s_out3 = extract_field <v_out2, 0> # step 2
3958 s_out4 = adjust_result <s_out3> # step 3
3960 (step 3 is optional, and steps 1 and 2 may be combined).
3961 Lastly, the uses of s_out0 are replaced by s_out4. */
3964 /* 2.1 Create new loop-exit-phis to preserve loop-closed form:
3965 v_out1 = phi <VECT_DEF>
3966 Store them in NEW_PHIS. */
3968 exit_bb
= single_exit (loop
)->dest
;
3969 prev_phi_info
= NULL
;
3970 new_phis
.create (vect_defs
.length ());
3971 FOR_EACH_VEC_ELT (vect_defs
, i
, def
)
3973 for (j
= 0; j
< ncopies
; j
++)
3975 tree new_def
= copy_ssa_name (def
, NULL
);
3976 phi
= create_phi_node (new_def
, exit_bb
);
3977 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, loop_vinfo
, NULL
));
3979 new_phis
.quick_push (phi
);
3982 def
= vect_get_vec_def_for_stmt_copy (dt
, def
);
3983 STMT_VINFO_RELATED_STMT (prev_phi_info
) = phi
;
3986 SET_PHI_ARG_DEF (phi
, single_exit (loop
)->dest_idx
, def
);
3987 prev_phi_info
= vinfo_for_stmt (phi
);
3991 /* The epilogue is created for the outer-loop, i.e., for the loop being
3992 vectorized. Create exit phis for the outer loop. */
3996 exit_bb
= single_exit (loop
)->dest
;
3997 inner_phis
.create (vect_defs
.length ());
3998 FOR_EACH_VEC_ELT (new_phis
, i
, phi
)
4000 tree new_result
= copy_ssa_name (PHI_RESULT (phi
), NULL
);
4001 gimple outer_phi
= create_phi_node (new_result
, exit_bb
);
4002 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
4004 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
4006 inner_phis
.quick_push (phi
);
4007 new_phis
[i
] = outer_phi
;
4008 prev_phi_info
= vinfo_for_stmt (outer_phi
);
4009 while (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
)))
4011 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
4012 new_result
= copy_ssa_name (PHI_RESULT (phi
), NULL
);
4013 outer_phi
= create_phi_node (new_result
, exit_bb
);
4014 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
4016 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
4018 STMT_VINFO_RELATED_STMT (prev_phi_info
) = outer_phi
;
4019 prev_phi_info
= vinfo_for_stmt (outer_phi
);
4024 exit_gsi
= gsi_after_labels (exit_bb
);
4026 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
4027 (i.e. when reduc_code is not available) and in the final adjustment
4028 code (if needed). Also get the original scalar reduction variable as
4029 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
4030 represents a reduction pattern), the tree-code and scalar-def are
4031 taken from the original stmt that the pattern-stmt (STMT) replaces.
4032 Otherwise (it is a regular reduction) - the tree-code and scalar-def
4033 are taken from STMT. */
4035 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
4038 /* Regular reduction */
4043 /* Reduction pattern */
4044 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (orig_stmt
);
4045 gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
));
4046 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo
) == stmt
);
4049 code
= gimple_assign_rhs_code (orig_stmt
);
4050 /* For MINUS_EXPR the initial vector is [init_val,0,...,0], therefore,
4051 partial results are added and not subtracted. */
4052 if (code
== MINUS_EXPR
)
4055 scalar_dest
= gimple_assign_lhs (orig_stmt
);
4056 scalar_type
= TREE_TYPE (scalar_dest
);
4057 scalar_results
.create (group_size
);
4058 new_scalar_dest
= vect_create_destination_var (scalar_dest
, NULL
);
4059 bitsize
= TYPE_SIZE (scalar_type
);
4061 /* In case this is a reduction in an inner-loop while vectorizing an outer
4062 loop - we don't need to extract a single scalar result at the end of the
4063 inner-loop (unless it is double reduction, i.e., the use of reduction is
4064 outside the outer-loop). The final vector of partial results will be used
4065 in the vectorized outer-loop, or reduced to a scalar result at the end of
4067 if (nested_in_vect_loop
&& !double_reduc
)
4068 goto vect_finalize_reduction
;
4070 /* SLP reduction without reduction chain, e.g.,
4074 b2 = operation (b1) */
4075 slp_reduc
= (slp_node
&& !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)));
4077 /* In case of reduction chain, e.g.,
4080 a3 = operation (a2),
4082 we may end up with more than one vector result. Here we reduce them to
4084 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4086 tree first_vect
= PHI_RESULT (new_phis
[0]);
4088 gimple new_vec_stmt
= NULL
;
4090 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4091 for (k
= 1; k
< new_phis
.length (); k
++)
4093 gimple next_phi
= new_phis
[k
];
4094 tree second_vect
= PHI_RESULT (next_phi
);
4096 tmp
= build2 (code
, vectype
, first_vect
, second_vect
);
4097 new_vec_stmt
= gimple_build_assign (vec_dest
, tmp
);
4098 first_vect
= make_ssa_name (vec_dest
, new_vec_stmt
);
4099 gimple_assign_set_lhs (new_vec_stmt
, first_vect
);
4100 gsi_insert_before (&exit_gsi
, new_vec_stmt
, GSI_SAME_STMT
);
4103 new_phi_result
= first_vect
;
4106 new_phis
.truncate (0);
4107 new_phis
.safe_push (new_vec_stmt
);
4111 new_phi_result
= PHI_RESULT (new_phis
[0]);
4113 /* 2.3 Create the reduction code, using one of the three schemes described
4114 above. In SLP we simply need to extract all the elements from the
4115 vector (without reducing them), so we use scalar shifts. */
4116 if (reduc_code
!= ERROR_MARK
&& !slp_reduc
)
4120 /*** Case 1: Create:
4121 v_out2 = reduc_expr <v_out1> */
4123 if (dump_enabled_p ())
4124 dump_printf_loc (MSG_NOTE
, vect_location
,
4125 "Reduce using direct vector reduction.\n");
4127 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4128 tmp
= build1 (reduc_code
, vectype
, new_phi_result
);
4129 epilog_stmt
= gimple_build_assign (vec_dest
, tmp
);
4130 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
4131 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4132 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4134 extract_scalar_result
= true;
4138 enum tree_code shift_code
= ERROR_MARK
;
4139 bool have_whole_vector_shift
= true;
4141 int element_bitsize
= tree_to_uhwi (bitsize
);
4142 int vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
4145 if (optab_handler (vec_shr_optab
, mode
) != CODE_FOR_nothing
)
4146 shift_code
= VEC_RSHIFT_EXPR
;
4148 have_whole_vector_shift
= false;
4150 /* Regardless of whether we have a whole vector shift, if we're
4151 emulating the operation via tree-vect-generic, we don't want
4152 to use it. Only the first round of the reduction is likely
4153 to still be profitable via emulation. */
4154 /* ??? It might be better to emit a reduction tree code here, so that
4155 tree-vect-generic can expand the first round via bit tricks. */
4156 if (!VECTOR_MODE_P (mode
))
4157 have_whole_vector_shift
= false;
4160 optab optab
= optab_for_tree_code (code
, vectype
, optab_default
);
4161 if (optab_handler (optab
, mode
) == CODE_FOR_nothing
)
4162 have_whole_vector_shift
= false;
4165 if (have_whole_vector_shift
&& !slp_reduc
)
4167 /*** Case 2: Create:
4168 for (offset = VS/2; offset >= element_size; offset/=2)
4170 Create: va' = vec_shift <va, offset>
4171 Create: va = vop <va, va'>
4174 if (dump_enabled_p ())
4175 dump_printf_loc (MSG_NOTE
, vect_location
,
4176 "Reduce using vector shifts\n");
4178 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4179 new_temp
= new_phi_result
;
4180 for (bit_offset
= vec_size_in_bits
/2;
4181 bit_offset
>= element_bitsize
;
4184 tree bitpos
= size_int (bit_offset
);
4186 epilog_stmt
= gimple_build_assign_with_ops (shift_code
,
4187 vec_dest
, new_temp
, bitpos
);
4188 new_name
= make_ssa_name (vec_dest
, epilog_stmt
);
4189 gimple_assign_set_lhs (epilog_stmt
, new_name
);
4190 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4192 epilog_stmt
= gimple_build_assign_with_ops (code
, vec_dest
,
4193 new_name
, new_temp
);
4194 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
4195 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4196 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4199 extract_scalar_result
= true;
4205 /*** Case 3: Create:
4206 s = extract_field <v_out2, 0>
4207 for (offset = element_size;
4208 offset < vector_size;
4209 offset += element_size;)
4211 Create: s' = extract_field <v_out2, offset>
4212 Create: s = op <s, s'> // For non SLP cases
4215 if (dump_enabled_p ())
4216 dump_printf_loc (MSG_NOTE
, vect_location
,
4217 "Reduce using scalar code.\n");
4219 vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
4220 FOR_EACH_VEC_ELT (new_phis
, i
, new_phi
)
4222 if (gimple_code (new_phi
) == GIMPLE_PHI
)
4223 vec_temp
= PHI_RESULT (new_phi
);
4225 vec_temp
= gimple_assign_lhs (new_phi
);
4226 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
, bitsize
,
4228 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4229 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4230 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4231 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4233 /* In SLP we don't need to apply reduction operation, so we just
4234 collect s' values in SCALAR_RESULTS. */
4236 scalar_results
.safe_push (new_temp
);
4238 for (bit_offset
= element_bitsize
;
4239 bit_offset
< vec_size_in_bits
;
4240 bit_offset
+= element_bitsize
)
4242 tree bitpos
= bitsize_int (bit_offset
);
4243 tree rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
,
4246 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4247 new_name
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4248 gimple_assign_set_lhs (epilog_stmt
, new_name
);
4249 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4253 /* In SLP we don't need to apply reduction operation, so
4254 we just collect s' values in SCALAR_RESULTS. */
4255 new_temp
= new_name
;
4256 scalar_results
.safe_push (new_name
);
4260 epilog_stmt
= gimple_build_assign_with_ops (code
,
4261 new_scalar_dest
, new_name
, new_temp
);
4262 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4263 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4264 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4269 /* The only case where we need to reduce scalar results in SLP, is
4270 unrolling. If the size of SCALAR_RESULTS is greater than
4271 GROUP_SIZE, we reduce them combining elements modulo
4275 tree res
, first_res
, new_res
;
4278 /* Reduce multiple scalar results in case of SLP unrolling. */
4279 for (j
= group_size
; scalar_results
.iterate (j
, &res
);
4282 first_res
= scalar_results
[j
% group_size
];
4283 new_stmt
= gimple_build_assign_with_ops (code
,
4284 new_scalar_dest
, first_res
, res
);
4285 new_res
= make_ssa_name (new_scalar_dest
, new_stmt
);
4286 gimple_assign_set_lhs (new_stmt
, new_res
);
4287 gsi_insert_before (&exit_gsi
, new_stmt
, GSI_SAME_STMT
);
4288 scalar_results
[j
% group_size
] = new_res
;
4292 /* Not SLP - we have one scalar to keep in SCALAR_RESULTS. */
4293 scalar_results
.safe_push (new_temp
);
4295 extract_scalar_result
= false;
4299 /* 2.4 Extract the final scalar result. Create:
4300 s_out3 = extract_field <v_out2, bitpos> */
4302 if (extract_scalar_result
)
4306 if (dump_enabled_p ())
4307 dump_printf_loc (MSG_NOTE
, vect_location
,
4308 "extract scalar result\n");
4310 if (BYTES_BIG_ENDIAN
)
4311 bitpos
= size_binop (MULT_EXPR
,
4312 bitsize_int (TYPE_VECTOR_SUBPARTS (vectype
) - 1),
4313 TYPE_SIZE (scalar_type
));
4315 bitpos
= bitsize_zero_node
;
4317 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, new_temp
, bitsize
, bitpos
);
4318 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4319 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4320 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4321 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4322 scalar_results
.safe_push (new_temp
);
4325 vect_finalize_reduction
:
4330 /* 2.5 Adjust the final result by the initial value of the reduction
4331 variable. (When such adjustment is not needed, then
4332 'adjustment_def' is zero). For example, if code is PLUS we create:
4333 new_temp = loop_exit_def + adjustment_def */
4337 gcc_assert (!slp_reduc
);
4338 if (nested_in_vect_loop
)
4340 new_phi
= new_phis
[0];
4341 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) == VECTOR_TYPE
);
4342 expr
= build2 (code
, vectype
, PHI_RESULT (new_phi
), adjustment_def
);
4343 new_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4347 new_temp
= scalar_results
[0];
4348 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) != VECTOR_TYPE
);
4349 expr
= build2 (code
, scalar_type
, new_temp
, adjustment_def
);
4350 new_dest
= vect_create_destination_var (scalar_dest
, scalar_type
);
4353 epilog_stmt
= gimple_build_assign (new_dest
, expr
);
4354 new_temp
= make_ssa_name (new_dest
, epilog_stmt
);
4355 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4356 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4357 if (nested_in_vect_loop
)
4359 set_vinfo_for_stmt (epilog_stmt
,
4360 new_stmt_vec_info (epilog_stmt
, loop_vinfo
,
4362 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (epilog_stmt
)) =
4363 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_phi
));
4366 scalar_results
.quick_push (new_temp
);
4368 scalar_results
[0] = new_temp
;
4371 scalar_results
[0] = new_temp
;
4373 new_phis
[0] = epilog_stmt
;
4376 /* 2.6 Handle the loop-exit phis. Replace the uses of scalar loop-exit
4377 phis with new adjusted scalar results, i.e., replace use <s_out0>
4382 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4383 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4384 v_out2 = reduce <v_out1>
4385 s_out3 = extract_field <v_out2, 0>
4386 s_out4 = adjust_result <s_out3>
4393 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4394 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4395 v_out2 = reduce <v_out1>
4396 s_out3 = extract_field <v_out2, 0>
4397 s_out4 = adjust_result <s_out3>
4402 /* In SLP reduction chain we reduce vector results into one vector if
4403 necessary, hence we set here GROUP_SIZE to 1. SCALAR_DEST is the LHS of
4404 the last stmt in the reduction chain, since we are looking for the loop
4406 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4408 scalar_dest
= gimple_assign_lhs (
4409 SLP_TREE_SCALAR_STMTS (slp_node
)[group_size
- 1]);
4413 /* In SLP we may have several statements in NEW_PHIS and REDUCTION_PHIS (in
4414 case that GROUP_SIZE is greater than vectorization factor). Therefore, we
4415 need to match SCALAR_RESULTS with corresponding statements. The first
4416 (GROUP_SIZE / number of new vector stmts) scalar results correspond to
4417 the first vector stmt, etc.
4418 (RATIO is equal to (GROUP_SIZE / number of new vector stmts)). */
4419 if (group_size
> new_phis
.length ())
4421 ratio
= group_size
/ new_phis
.length ();
4422 gcc_assert (!(group_size
% new_phis
.length ()));
4427 for (k
= 0; k
< group_size
; k
++)
4431 epilog_stmt
= new_phis
[k
/ ratio
];
4432 reduction_phi
= reduction_phis
[k
/ ratio
];
4434 inner_phi
= inner_phis
[k
/ ratio
];
4439 gimple current_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[k
];
4441 orig_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (current_stmt
));
4442 /* SLP statements can't participate in patterns. */
4443 gcc_assert (!orig_stmt
);
4444 scalar_dest
= gimple_assign_lhs (current_stmt
);
4448 /* Find the loop-closed-use at the loop exit of the original scalar
4449 result. (The reduction result is expected to have two immediate uses -
4450 one at the latch block, and one at the loop exit). */
4451 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
4452 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
)))
4453 && !is_gimple_debug (USE_STMT (use_p
)))
4454 phis
.safe_push (USE_STMT (use_p
));
4456 /* While we expect to have found an exit_phi because of loop-closed-ssa
4457 form we can end up without one if the scalar cycle is dead. */
4459 FOR_EACH_VEC_ELT (phis
, i
, exit_phi
)
4463 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
4466 /* FORNOW. Currently not supporting the case that an inner-loop
4467 reduction is not used in the outer-loop (but only outside the
4468 outer-loop), unless it is double reduction. */
4469 gcc_assert ((STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
4470 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
))
4473 STMT_VINFO_VEC_STMT (exit_phi_vinfo
) = epilog_stmt
;
4475 || STMT_VINFO_DEF_TYPE (exit_phi_vinfo
)
4476 != vect_double_reduction_def
)
4479 /* Handle double reduction:
4481 stmt1: s1 = phi <s0, s2> - double reduction phi (outer loop)
4482 stmt2: s3 = phi <s1, s4> - (regular) reduc phi (inner loop)
4483 stmt3: s4 = use (s3) - (regular) reduc stmt (inner loop)
4484 stmt4: s2 = phi <s4> - double reduction stmt (outer loop)
4486 At that point the regular reduction (stmt2 and stmt3) is
4487 already vectorized, as well as the exit phi node, stmt4.
4488 Here we vectorize the phi node of double reduction, stmt1, and
4489 update all relevant statements. */
4491 /* Go through all the uses of s2 to find double reduction phi
4492 node, i.e., stmt1 above. */
4493 orig_name
= PHI_RESULT (exit_phi
);
4494 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
4496 stmt_vec_info use_stmt_vinfo
;
4497 stmt_vec_info new_phi_vinfo
;
4498 tree vect_phi_init
, preheader_arg
, vect_phi_res
, init_def
;
4499 basic_block bb
= gimple_bb (use_stmt
);
4502 /* Check that USE_STMT is really double reduction phi
4504 if (gimple_code (use_stmt
) != GIMPLE_PHI
4505 || gimple_phi_num_args (use_stmt
) != 2
4506 || bb
->loop_father
!= outer_loop
)
4508 use_stmt_vinfo
= vinfo_for_stmt (use_stmt
);
4510 || STMT_VINFO_DEF_TYPE (use_stmt_vinfo
)
4511 != vect_double_reduction_def
)
4514 /* Create vector phi node for double reduction:
4515 vs1 = phi <vs0, vs2>
4516 vs1 was created previously in this function by a call to
4517 vect_get_vec_def_for_operand and is stored in
4519 vs2 is defined by INNER_PHI, the vectorized EXIT_PHI;
4520 vs0 is created here. */
4522 /* Create vector phi node. */
4523 vect_phi
= create_phi_node (vec_initial_def
, bb
);
4524 new_phi_vinfo
= new_stmt_vec_info (vect_phi
,
4525 loop_vec_info_for_loop (outer_loop
), NULL
);
4526 set_vinfo_for_stmt (vect_phi
, new_phi_vinfo
);
4528 /* Create vs0 - initial def of the double reduction phi. */
4529 preheader_arg
= PHI_ARG_DEF_FROM_EDGE (use_stmt
,
4530 loop_preheader_edge (outer_loop
));
4531 init_def
= get_initial_def_for_reduction (stmt
,
4532 preheader_arg
, NULL
);
4533 vect_phi_init
= vect_init_vector (use_stmt
, init_def
,
4536 /* Update phi node arguments with vs0 and vs2. */
4537 add_phi_arg (vect_phi
, vect_phi_init
,
4538 loop_preheader_edge (outer_loop
),
4540 add_phi_arg (vect_phi
, PHI_RESULT (inner_phi
),
4541 loop_latch_edge (outer_loop
), UNKNOWN_LOCATION
);
4542 if (dump_enabled_p ())
4544 dump_printf_loc (MSG_NOTE
, vect_location
,
4545 "created double reduction phi node: ");
4546 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, vect_phi
, 0);
4547 dump_printf (MSG_NOTE
, "\n");
4550 vect_phi_res
= PHI_RESULT (vect_phi
);
4552 /* Replace the use, i.e., set the correct vs1 in the regular
4553 reduction phi node. FORNOW, NCOPIES is always 1, so the
4554 loop is redundant. */
4555 use
= reduction_phi
;
4556 for (j
= 0; j
< ncopies
; j
++)
4558 edge pr_edge
= loop_preheader_edge (loop
);
4559 SET_PHI_ARG_DEF (use
, pr_edge
->dest_idx
, vect_phi_res
);
4560 use
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use
));
4567 if (nested_in_vect_loop
)
4576 /* Find the loop-closed-use at the loop exit of the original scalar
4577 result. (The reduction result is expected to have two immediate uses,
4578 one at the latch block, and one at the loop exit). For double
4579 reductions we are looking for exit phis of the outer loop. */
4580 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
4582 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
4584 if (!is_gimple_debug (USE_STMT (use_p
)))
4585 phis
.safe_push (USE_STMT (use_p
));
4589 if (double_reduc
&& gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
4591 tree phi_res
= PHI_RESULT (USE_STMT (use_p
));
4593 FOR_EACH_IMM_USE_FAST (phi_use_p
, phi_imm_iter
, phi_res
)
4595 if (!flow_bb_inside_loop_p (loop
,
4596 gimple_bb (USE_STMT (phi_use_p
)))
4597 && !is_gimple_debug (USE_STMT (phi_use_p
)))
4598 phis
.safe_push (USE_STMT (phi_use_p
));
4604 FOR_EACH_VEC_ELT (phis
, i
, exit_phi
)
4606 /* Replace the uses: */
4607 orig_name
= PHI_RESULT (exit_phi
);
4608 scalar_result
= scalar_results
[k
];
4609 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
4610 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
4611 SET_USE (use_p
, scalar_result
);
4619 /* Function vectorizable_reduction.
4621 Check if STMT performs a reduction operation that can be vectorized.
4622 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4623 stmt to replace it, put it in VEC_STMT, and insert it at GSI.
4624 Return FALSE if not a vectorizable STMT, TRUE otherwise.
4626 This function also handles reduction idioms (patterns) that have been
4627 recognized in advance during vect_pattern_recog. In this case, STMT may be
4629 X = pattern_expr (arg0, arg1, ..., X)
4630 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
4631 sequence that had been detected and replaced by the pattern-stmt (STMT).
4633 In some cases of reduction patterns, the type of the reduction variable X is
4634 different than the type of the other arguments of STMT.
4635 In such cases, the vectype that is used when transforming STMT into a vector
4636 stmt is different than the vectype that is used to determine the
4637 vectorization factor, because it consists of a different number of elements
4638 than the actual number of elements that are being operated upon in parallel.
4640 For example, consider an accumulation of shorts into an int accumulator.
4641 On some targets it's possible to vectorize this pattern operating on 8
4642 shorts at a time (hence, the vectype for purposes of determining the
4643 vectorization factor should be V8HI); on the other hand, the vectype that
4644 is used to create the vector form is actually V4SI (the type of the result).
4646 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
4647 indicates what is the actual level of parallelism (V8HI in the example), so
4648 that the right vectorization factor would be derived. This vectype
4649 corresponds to the type of arguments to the reduction stmt, and should *NOT*
4650 be used to create the vectorized stmt. The right vectype for the vectorized
4651 stmt is obtained from the type of the result X:
4652 get_vectype_for_scalar_type (TREE_TYPE (X))
4654 This means that, contrary to "regular" reductions (or "regular" stmts in
4655 general), the following equation:
4656 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
4657 does *NOT* necessarily hold for reduction patterns. */
4660 vectorizable_reduction (gimple stmt
, gimple_stmt_iterator
*gsi
,
4661 gimple
*vec_stmt
, slp_tree slp_node
)
4665 tree loop_vec_def0
= NULL_TREE
, loop_vec_def1
= NULL_TREE
;
4666 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
4667 tree vectype_out
= STMT_VINFO_VECTYPE (stmt_info
);
4668 tree vectype_in
= NULL_TREE
;
4669 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
4670 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4671 enum tree_code code
, orig_code
, epilog_reduc_code
;
4672 enum machine_mode vec_mode
;
4674 optab optab
, reduc_optab
;
4675 tree new_temp
= NULL_TREE
;
4678 enum vect_def_type dt
;
4679 gimple new_phi
= NULL
;
4683 stmt_vec_info orig_stmt_info
;
4684 tree expr
= NULL_TREE
;
4688 stmt_vec_info prev_stmt_info
, prev_phi_info
;
4689 bool single_defuse_cycle
= false;
4690 tree reduc_def
= NULL_TREE
;
4691 gimple new_stmt
= NULL
;
4694 bool nested_cycle
= false, found_nested_cycle_def
= false;
4695 gimple reduc_def_stmt
= NULL
;
4696 /* The default is that the reduction variable is the last in statement. */
4697 int reduc_index
= 2;
4698 bool double_reduc
= false, dummy
;
4700 struct loop
* def_stmt_loop
, *outer_loop
= NULL
;
4702 gimple def_arg_stmt
;
4703 auto_vec
<tree
> vec_oprnds0
;
4704 auto_vec
<tree
> vec_oprnds1
;
4705 auto_vec
<tree
> vect_defs
;
4706 auto_vec
<gimple
> phis
;
4708 tree def0
, def1
, tem
, op0
, op1
= NULL_TREE
;
4710 /* In case of reduction chain we switch to the first stmt in the chain, but
4711 we don't update STMT_INFO, since only the last stmt is marked as reduction
4712 and has reduction properties. */
4713 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4714 stmt
= GROUP_FIRST_ELEMENT (stmt_info
);
4716 if (nested_in_vect_loop_p (loop
, stmt
))
4720 nested_cycle
= true;
4723 /* 1. Is vectorizable reduction? */
4724 /* Not supportable if the reduction variable is used in the loop, unless
4725 it's a reduction chain. */
4726 if (STMT_VINFO_RELEVANT (stmt_info
) > vect_used_in_outer
4727 && !GROUP_FIRST_ELEMENT (stmt_info
))
4730 /* Reductions that are not used even in an enclosing outer-loop,
4731 are expected to be "live" (used out of the loop). */
4732 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
4733 && !STMT_VINFO_LIVE_P (stmt_info
))
4736 /* Make sure it was already recognized as a reduction computation. */
4737 if (STMT_VINFO_DEF_TYPE (stmt_info
) != vect_reduction_def
4738 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_nested_cycle
)
4741 /* 2. Has this been recognized as a reduction pattern?
4743 Check if STMT represents a pattern that has been recognized
4744 in earlier analysis stages. For stmts that represent a pattern,
4745 the STMT_VINFO_RELATED_STMT field records the last stmt in
4746 the original sequence that constitutes the pattern. */
4748 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
4751 orig_stmt_info
= vinfo_for_stmt (orig_stmt
);
4752 gcc_assert (STMT_VINFO_IN_PATTERN_P (orig_stmt_info
));
4753 gcc_assert (!STMT_VINFO_IN_PATTERN_P (stmt_info
));
4756 /* 3. Check the operands of the operation. The first operands are defined
4757 inside the loop body. The last operand is the reduction variable,
4758 which is defined by the loop-header-phi. */
4760 gcc_assert (is_gimple_assign (stmt
));
4763 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
4765 case GIMPLE_SINGLE_RHS
:
4766 op_type
= TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
));
4767 if (op_type
== ternary_op
)
4769 tree rhs
= gimple_assign_rhs1 (stmt
);
4770 ops
[0] = TREE_OPERAND (rhs
, 0);
4771 ops
[1] = TREE_OPERAND (rhs
, 1);
4772 ops
[2] = TREE_OPERAND (rhs
, 2);
4773 code
= TREE_CODE (rhs
);
4779 case GIMPLE_BINARY_RHS
:
4780 code
= gimple_assign_rhs_code (stmt
);
4781 op_type
= TREE_CODE_LENGTH (code
);
4782 gcc_assert (op_type
== binary_op
);
4783 ops
[0] = gimple_assign_rhs1 (stmt
);
4784 ops
[1] = gimple_assign_rhs2 (stmt
);
4787 case GIMPLE_TERNARY_RHS
:
4788 code
= gimple_assign_rhs_code (stmt
);
4789 op_type
= TREE_CODE_LENGTH (code
);
4790 gcc_assert (op_type
== ternary_op
);
4791 ops
[0] = gimple_assign_rhs1 (stmt
);
4792 ops
[1] = gimple_assign_rhs2 (stmt
);
4793 ops
[2] = gimple_assign_rhs3 (stmt
);
4796 case GIMPLE_UNARY_RHS
:
4803 if (code
== COND_EXPR
&& slp_node
)
4806 scalar_dest
= gimple_assign_lhs (stmt
);
4807 scalar_type
= TREE_TYPE (scalar_dest
);
4808 if (!POINTER_TYPE_P (scalar_type
) && !INTEGRAL_TYPE_P (scalar_type
)
4809 && !SCALAR_FLOAT_TYPE_P (scalar_type
))
4812 /* Do not try to vectorize bit-precision reductions. */
4813 if ((TYPE_PRECISION (scalar_type
)
4814 != GET_MODE_PRECISION (TYPE_MODE (scalar_type
))))
4817 /* All uses but the last are expected to be defined in the loop.
4818 The last use is the reduction variable. In case of nested cycle this
4819 assumption is not true: we use reduc_index to record the index of the
4820 reduction variable. */
4821 for (i
= 0; i
< op_type
- 1; i
++)
4823 /* The condition of COND_EXPR is checked in vectorizable_condition(). */
4824 if (i
== 0 && code
== COND_EXPR
)
4827 is_simple_use
= vect_is_simple_use_1 (ops
[i
], stmt
, loop_vinfo
, NULL
,
4828 &def_stmt
, &def
, &dt
, &tem
);
4831 gcc_assert (is_simple_use
);
4833 if (dt
!= vect_internal_def
4834 && dt
!= vect_external_def
4835 && dt
!= vect_constant_def
4836 && dt
!= vect_induction_def
4837 && !(dt
== vect_nested_cycle
&& nested_cycle
))
4840 if (dt
== vect_nested_cycle
)
4842 found_nested_cycle_def
= true;
4843 reduc_def_stmt
= def_stmt
;
4848 is_simple_use
= vect_is_simple_use_1 (ops
[i
], stmt
, loop_vinfo
, NULL
,
4849 &def_stmt
, &def
, &dt
, &tem
);
4852 gcc_assert (is_simple_use
);
4853 if (!(dt
== vect_reduction_def
4854 || dt
== vect_nested_cycle
4855 || ((dt
== vect_internal_def
|| dt
== vect_external_def
4856 || dt
== vect_constant_def
|| dt
== vect_induction_def
)
4857 && nested_cycle
&& found_nested_cycle_def
)))
4859 /* For pattern recognized stmts, orig_stmt might be a reduction,
4860 but some helper statements for the pattern might not, or
4861 might be COND_EXPRs with reduction uses in the condition. */
4862 gcc_assert (orig_stmt
);
4865 if (!found_nested_cycle_def
)
4866 reduc_def_stmt
= def_stmt
;
4868 gcc_assert (gimple_code (reduc_def_stmt
) == GIMPLE_PHI
);
4870 gcc_assert (orig_stmt
== vect_is_simple_reduction (loop_vinfo
,
4876 gimple tmp
= vect_is_simple_reduction (loop_vinfo
, reduc_def_stmt
,
4877 !nested_cycle
, &dummy
);
4878 /* We changed STMT to be the first stmt in reduction chain, hence we
4879 check that in this case the first element in the chain is STMT. */
4880 gcc_assert (stmt
== tmp
4881 || GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp
)) == stmt
);
4884 if (STMT_VINFO_LIVE_P (vinfo_for_stmt (reduc_def_stmt
)))
4887 if (slp_node
|| PURE_SLP_STMT (stmt_info
))
4890 ncopies
= (LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4891 / TYPE_VECTOR_SUBPARTS (vectype_in
));
4893 gcc_assert (ncopies
>= 1);
4895 vec_mode
= TYPE_MODE (vectype_in
);
4897 if (code
== COND_EXPR
)
4899 if (!vectorizable_condition (stmt
, gsi
, NULL
, ops
[reduc_index
], 0, NULL
))
4901 if (dump_enabled_p ())
4902 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4903 "unsupported condition in reduction\n");
4910 /* 4. Supportable by target? */
4912 if (code
== LSHIFT_EXPR
|| code
== RSHIFT_EXPR
4913 || code
== LROTATE_EXPR
|| code
== RROTATE_EXPR
)
4915 /* Shifts and rotates are only supported by vectorizable_shifts,
4916 not vectorizable_reduction. */
4917 if (dump_enabled_p ())
4918 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4919 "unsupported shift or rotation.\n");
4923 /* 4.1. check support for the operation in the loop */
4924 optab
= optab_for_tree_code (code
, vectype_in
, optab_default
);
4927 if (dump_enabled_p ())
4928 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4934 if (optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
4936 if (dump_enabled_p ())
4937 dump_printf (MSG_NOTE
, "op not supported by target.\n");
4939 if (GET_MODE_SIZE (vec_mode
) != UNITS_PER_WORD
4940 || LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4941 < vect_min_worthwhile_factor (code
))
4944 if (dump_enabled_p ())
4945 dump_printf (MSG_NOTE
, "proceeding using word mode.\n");
4948 /* Worthwhile without SIMD support? */
4949 if (!VECTOR_MODE_P (TYPE_MODE (vectype_in
))
4950 && LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4951 < vect_min_worthwhile_factor (code
))
4953 if (dump_enabled_p ())
4954 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4955 "not worthwhile without SIMD support.\n");
4961 /* 4.2. Check support for the epilog operation.
4963 If STMT represents a reduction pattern, then the type of the
4964 reduction variable may be different than the type of the rest
4965 of the arguments. For example, consider the case of accumulation
4966 of shorts into an int accumulator; The original code:
4967 S1: int_a = (int) short_a;
4968 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
4971 STMT: int_acc = widen_sum <short_a, int_acc>
4974 1. The tree-code that is used to create the vector operation in the
4975 epilog code (that reduces the partial results) is not the
4976 tree-code of STMT, but is rather the tree-code of the original
4977 stmt from the pattern that STMT is replacing. I.e, in the example
4978 above we want to use 'widen_sum' in the loop, but 'plus' in the
4980 2. The type (mode) we use to check available target support
4981 for the vector operation to be created in the *epilog*, is
4982 determined by the type of the reduction variable (in the example
4983 above we'd check this: optab_handler (plus_optab, vect_int_mode])).
4984 However the type (mode) we use to check available target support
4985 for the vector operation to be created *inside the loop*, is
4986 determined by the type of the other arguments to STMT (in the
4987 example we'd check this: optab_handler (widen_sum_optab,
4990 This is contrary to "regular" reductions, in which the types of all
4991 the arguments are the same as the type of the reduction variable.
4992 For "regular" reductions we can therefore use the same vector type
4993 (and also the same tree-code) when generating the epilog code and
4994 when generating the code inside the loop. */
4998 /* This is a reduction pattern: get the vectype from the type of the
4999 reduction variable, and get the tree-code from orig_stmt. */
5000 orig_code
= gimple_assign_rhs_code (orig_stmt
);
5001 gcc_assert (vectype_out
);
5002 vec_mode
= TYPE_MODE (vectype_out
);
5006 /* Regular reduction: use the same vectype and tree-code as used for
5007 the vector code inside the loop can be used for the epilog code. */
5013 def_bb
= gimple_bb (reduc_def_stmt
);
5014 def_stmt_loop
= def_bb
->loop_father
;
5015 def_arg
= PHI_ARG_DEF_FROM_EDGE (reduc_def_stmt
,
5016 loop_preheader_edge (def_stmt_loop
));
5017 if (TREE_CODE (def_arg
) == SSA_NAME
5018 && (def_arg_stmt
= SSA_NAME_DEF_STMT (def_arg
))
5019 && gimple_code (def_arg_stmt
) == GIMPLE_PHI
5020 && flow_bb_inside_loop_p (outer_loop
, gimple_bb (def_arg_stmt
))
5021 && vinfo_for_stmt (def_arg_stmt
)
5022 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_arg_stmt
))
5023 == vect_double_reduction_def
)
5024 double_reduc
= true;
5027 epilog_reduc_code
= ERROR_MARK
;
5028 if (reduction_code_for_scalar_code (orig_code
, &epilog_reduc_code
))
5030 reduc_optab
= optab_for_tree_code (epilog_reduc_code
, vectype_out
,
5034 if (dump_enabled_p ())
5035 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5036 "no optab for reduction.\n");
5038 epilog_reduc_code
= ERROR_MARK
;
5042 && optab_handler (reduc_optab
, vec_mode
) == CODE_FOR_nothing
)
5044 if (dump_enabled_p ())
5045 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5046 "reduc op not supported by target.\n");
5048 epilog_reduc_code
= ERROR_MARK
;
5053 if (!nested_cycle
|| double_reduc
)
5055 if (dump_enabled_p ())
5056 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5057 "no reduc code for scalar code.\n");
5063 if (double_reduc
&& ncopies
> 1)
5065 if (dump_enabled_p ())
5066 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5067 "multiple types in double reduction\n");
5072 /* In case of widenning multiplication by a constant, we update the type
5073 of the constant to be the type of the other operand. We check that the
5074 constant fits the type in the pattern recognition pass. */
5075 if (code
== DOT_PROD_EXPR
5076 && !types_compatible_p (TREE_TYPE (ops
[0]), TREE_TYPE (ops
[1])))
5078 if (TREE_CODE (ops
[0]) == INTEGER_CST
)
5079 ops
[0] = fold_convert (TREE_TYPE (ops
[1]), ops
[0]);
5080 else if (TREE_CODE (ops
[1]) == INTEGER_CST
)
5081 ops
[1] = fold_convert (TREE_TYPE (ops
[0]), ops
[1]);
5084 if (dump_enabled_p ())
5085 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5086 "invalid types in dot-prod\n");
5092 if (!vec_stmt
) /* transformation not required. */
5094 if (!vect_model_reduction_cost (stmt_info
, epilog_reduc_code
, ncopies
))
5096 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
5102 if (dump_enabled_p ())
5103 dump_printf_loc (MSG_NOTE
, vect_location
, "transform reduction.\n");
5105 /* FORNOW: Multiple types are not supported for condition. */
5106 if (code
== COND_EXPR
)
5107 gcc_assert (ncopies
== 1);
5109 /* Create the destination vector */
5110 vec_dest
= vect_create_destination_var (scalar_dest
, vectype_out
);
5112 /* In case the vectorization factor (VF) is bigger than the number
5113 of elements that we can fit in a vectype (nunits), we have to generate
5114 more than one vector stmt - i.e - we need to "unroll" the
5115 vector stmt by a factor VF/nunits. For more details see documentation
5116 in vectorizable_operation. */
5118 /* If the reduction is used in an outer loop we need to generate
5119 VF intermediate results, like so (e.g. for ncopies=2):
5124 (i.e. we generate VF results in 2 registers).
5125 In this case we have a separate def-use cycle for each copy, and therefore
5126 for each copy we get the vector def for the reduction variable from the
5127 respective phi node created for this copy.
5129 Otherwise (the reduction is unused in the loop nest), we can combine
5130 together intermediate results, like so (e.g. for ncopies=2):
5134 (i.e. we generate VF/2 results in a single register).
5135 In this case for each copy we get the vector def for the reduction variable
5136 from the vectorized reduction operation generated in the previous iteration.
5139 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
)
5141 single_defuse_cycle
= true;
5145 epilog_copies
= ncopies
;
5147 prev_stmt_info
= NULL
;
5148 prev_phi_info
= NULL
;
5151 vec_num
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
5152 gcc_assert (TYPE_VECTOR_SUBPARTS (vectype_out
)
5153 == TYPE_VECTOR_SUBPARTS (vectype_in
));
5158 vec_oprnds0
.create (1);
5159 if (op_type
== ternary_op
)
5160 vec_oprnds1
.create (1);
5163 phis
.create (vec_num
);
5164 vect_defs
.create (vec_num
);
5166 vect_defs
.quick_push (NULL_TREE
);
5168 for (j
= 0; j
< ncopies
; j
++)
5170 if (j
== 0 || !single_defuse_cycle
)
5172 for (i
= 0; i
< vec_num
; i
++)
5174 /* Create the reduction-phi that defines the reduction
5176 new_phi
= create_phi_node (vec_dest
, loop
->header
);
5177 set_vinfo_for_stmt (new_phi
,
5178 new_stmt_vec_info (new_phi
, loop_vinfo
,
5180 if (j
== 0 || slp_node
)
5181 phis
.quick_push (new_phi
);
5185 if (code
== COND_EXPR
)
5187 gcc_assert (!slp_node
);
5188 vectorizable_condition (stmt
, gsi
, vec_stmt
,
5189 PHI_RESULT (phis
[0]),
5191 /* Multiple types are not supported for condition. */
5198 op0
= ops
[!reduc_index
];
5199 if (op_type
== ternary_op
)
5201 if (reduc_index
== 0)
5208 vect_get_vec_defs (op0
, op1
, stmt
, &vec_oprnds0
, &vec_oprnds1
,
5212 loop_vec_def0
= vect_get_vec_def_for_operand (ops
[!reduc_index
],
5214 vec_oprnds0
.quick_push (loop_vec_def0
);
5215 if (op_type
== ternary_op
)
5217 loop_vec_def1
= vect_get_vec_def_for_operand (op1
, stmt
,
5219 vec_oprnds1
.quick_push (loop_vec_def1
);
5227 enum vect_def_type dt
;
5231 vect_is_simple_use (ops
[!reduc_index
], stmt
, loop_vinfo
, NULL
,
5232 &dummy_stmt
, &dummy
, &dt
);
5233 loop_vec_def0
= vect_get_vec_def_for_stmt_copy (dt
,
5235 vec_oprnds0
[0] = loop_vec_def0
;
5236 if (op_type
== ternary_op
)
5238 vect_is_simple_use (op1
, stmt
, loop_vinfo
, NULL
, &dummy_stmt
,
5240 loop_vec_def1
= vect_get_vec_def_for_stmt_copy (dt
,
5242 vec_oprnds1
[0] = loop_vec_def1
;
5246 if (single_defuse_cycle
)
5247 reduc_def
= gimple_assign_lhs (new_stmt
);
5249 STMT_VINFO_RELATED_STMT (prev_phi_info
) = new_phi
;
5252 FOR_EACH_VEC_ELT (vec_oprnds0
, i
, def0
)
5255 reduc_def
= PHI_RESULT (phis
[i
]);
5258 if (!single_defuse_cycle
|| j
== 0)
5259 reduc_def
= PHI_RESULT (new_phi
);
5262 def1
= ((op_type
== ternary_op
)
5263 ? vec_oprnds1
[i
] : NULL
);
5264 if (op_type
== binary_op
)
5266 if (reduc_index
== 0)
5267 expr
= build2 (code
, vectype_out
, reduc_def
, def0
);
5269 expr
= build2 (code
, vectype_out
, def0
, reduc_def
);
5273 if (reduc_index
== 0)
5274 expr
= build3 (code
, vectype_out
, reduc_def
, def0
, def1
);
5277 if (reduc_index
== 1)
5278 expr
= build3 (code
, vectype_out
, def0
, reduc_def
, def1
);
5280 expr
= build3 (code
, vectype_out
, def0
, def1
, reduc_def
);
5284 new_stmt
= gimple_build_assign (vec_dest
, expr
);
5285 new_temp
= make_ssa_name (vec_dest
, new_stmt
);
5286 gimple_assign_set_lhs (new_stmt
, new_temp
);
5287 vect_finish_stmt_generation (stmt
, new_stmt
, gsi
);
5291 SLP_TREE_VEC_STMTS (slp_node
).quick_push (new_stmt
);
5292 vect_defs
.quick_push (new_temp
);
5295 vect_defs
[0] = new_temp
;
5302 STMT_VINFO_VEC_STMT (stmt_info
) = *vec_stmt
= new_stmt
;
5304 STMT_VINFO_RELATED_STMT (prev_stmt_info
) = new_stmt
;
5306 prev_stmt_info
= vinfo_for_stmt (new_stmt
);
5307 prev_phi_info
= vinfo_for_stmt (new_phi
);
5310 /* Finalize the reduction-phi (set its arguments) and create the
5311 epilog reduction code. */
5312 if ((!single_defuse_cycle
|| code
== COND_EXPR
) && !slp_node
)
5314 new_temp
= gimple_assign_lhs (*vec_stmt
);
5315 vect_defs
[0] = new_temp
;
5318 vect_create_epilog_for_reduction (vect_defs
, stmt
, epilog_copies
,
5319 epilog_reduc_code
, phis
, reduc_index
,
5320 double_reduc
, slp_node
);
5325 /* Function vect_min_worthwhile_factor.
5327 For a loop where we could vectorize the operation indicated by CODE,
5328 return the minimum vectorization factor that makes it worthwhile
5329 to use generic vectors. */
5331 vect_min_worthwhile_factor (enum tree_code code
)
5352 /* Function vectorizable_induction
5354 Check if PHI performs an induction computation that can be vectorized.
5355 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
5356 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
5357 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5360 vectorizable_induction (gimple phi
, gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
5363 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
5364 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
5365 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
5366 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5367 int nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
5368 int ncopies
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) / nunits
;
5371 gcc_assert (ncopies
>= 1);
5372 /* FORNOW. These restrictions should be relaxed. */
5373 if (nested_in_vect_loop_p (loop
, phi
))
5375 imm_use_iterator imm_iter
;
5376 use_operand_p use_p
;
5383 if (dump_enabled_p ())
5384 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5385 "multiple types in nested loop.\n");
5390 latch_e
= loop_latch_edge (loop
->inner
);
5391 loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
5392 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
5394 if (!flow_bb_inside_loop_p (loop
->inner
,
5395 gimple_bb (USE_STMT (use_p
))))
5397 exit_phi
= USE_STMT (use_p
);
5403 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
5404 if (!(STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
5405 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
)))
5407 if (dump_enabled_p ())
5408 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5409 "inner-loop induction only used outside "
5410 "of the outer vectorized loop.\n");
5416 if (!STMT_VINFO_RELEVANT_P (stmt_info
))
5419 /* FORNOW: SLP not supported. */
5420 if (STMT_SLP_TYPE (stmt_info
))
5423 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
);
5425 if (gimple_code (phi
) != GIMPLE_PHI
)
5428 if (!vec_stmt
) /* transformation not required. */
5430 STMT_VINFO_TYPE (stmt_info
) = induc_vec_info_type
;
5431 if (dump_enabled_p ())
5432 dump_printf_loc (MSG_NOTE
, vect_location
,
5433 "=== vectorizable_induction ===\n");
5434 vect_model_induction_cost (stmt_info
, ncopies
);
5440 if (dump_enabled_p ())
5441 dump_printf_loc (MSG_NOTE
, vect_location
, "transform induction phi.\n");
5443 vec_def
= get_initial_def_for_induction (phi
);
5444 *vec_stmt
= SSA_NAME_DEF_STMT (vec_def
);
5448 /* Function vectorizable_live_operation.
5450 STMT computes a value that is used outside the loop. Check if
5451 it can be supported. */
5454 vectorizable_live_operation (gimple stmt
,
5455 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
5458 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
5459 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
5460 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5466 enum vect_def_type dt
;
5467 enum tree_code code
;
5468 enum gimple_rhs_class rhs_class
;
5470 gcc_assert (STMT_VINFO_LIVE_P (stmt_info
));
5472 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_reduction_def
)
5475 if (!is_gimple_assign (stmt
))
5477 if (gimple_call_internal_p (stmt
)
5478 && gimple_call_internal_fn (stmt
) == IFN_GOMP_SIMD_LANE
5479 && gimple_call_lhs (stmt
)
5481 && TREE_CODE (gimple_call_arg (stmt
, 0)) == SSA_NAME
5483 == SSA_NAME_VAR (gimple_call_arg (stmt
, 0)))
5485 edge e
= single_exit (loop
);
5486 basic_block merge_bb
= e
->dest
;
5487 imm_use_iterator imm_iter
;
5488 use_operand_p use_p
;
5489 tree lhs
= gimple_call_lhs (stmt
);
5491 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
5493 gimple use_stmt
= USE_STMT (use_p
);
5494 if (gimple_code (use_stmt
) == GIMPLE_PHI
5495 || gimple_bb (use_stmt
) == merge_bb
)
5500 = build_int_cst (unsigned_type_node
,
5501 loop_vinfo
->vectorization_factor
- 1);
5502 SET_PHI_ARG_DEF (use_stmt
, e
->dest_idx
, vfm1
);
5512 if (TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
5515 /* FORNOW. CHECKME. */
5516 if (nested_in_vect_loop_p (loop
, stmt
))
5519 code
= gimple_assign_rhs_code (stmt
);
5520 op_type
= TREE_CODE_LENGTH (code
);
5521 rhs_class
= get_gimple_rhs_class (code
);
5522 gcc_assert (rhs_class
!= GIMPLE_UNARY_RHS
|| op_type
== unary_op
);
5523 gcc_assert (rhs_class
!= GIMPLE_BINARY_RHS
|| op_type
== binary_op
);
5525 /* FORNOW: support only if all uses are invariant. This means
5526 that the scalar operations can remain in place, unvectorized.
5527 The original last scalar value that they compute will be used. */
5529 for (i
= 0; i
< op_type
; i
++)
5531 if (rhs_class
== GIMPLE_SINGLE_RHS
)
5532 op
= TREE_OPERAND (gimple_op (stmt
, 1), i
);
5534 op
= gimple_op (stmt
, i
+ 1);
5536 && !vect_is_simple_use (op
, stmt
, loop_vinfo
, NULL
, &def_stmt
, &def
,
5539 if (dump_enabled_p ())
5540 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5541 "use not simple.\n");
5545 if (dt
!= vect_external_def
&& dt
!= vect_constant_def
)
5549 /* No transformation is required for the cases we currently support. */
5553 /* Kill any debug uses outside LOOP of SSA names defined in STMT. */
5556 vect_loop_kill_debug_uses (struct loop
*loop
, gimple stmt
)
5558 ssa_op_iter op_iter
;
5559 imm_use_iterator imm_iter
;
5560 def_operand_p def_p
;
5563 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
5565 FOR_EACH_IMM_USE_STMT (ustmt
, imm_iter
, DEF_FROM_PTR (def_p
))
5569 if (!is_gimple_debug (ustmt
))
5572 bb
= gimple_bb (ustmt
);
5574 if (!flow_bb_inside_loop_p (loop
, bb
))
5576 if (gimple_debug_bind_p (ustmt
))
5578 if (dump_enabled_p ())
5579 dump_printf_loc (MSG_NOTE
, vect_location
,
5580 "killing debug use\n");
5582 gimple_debug_bind_reset_value (ustmt
);
5583 update_stmt (ustmt
);
5593 /* This function builds ni_name = number of iterations. Statements
5594 are emitted on the loop preheader edge. */
5597 vect_build_loop_niters (loop_vec_info loop_vinfo
)
5599 tree ni
= unshare_expr (LOOP_VINFO_NITERS (loop_vinfo
));
5600 if (TREE_CODE (ni
) == INTEGER_CST
)
5605 gimple_seq stmts
= NULL
;
5606 edge pe
= loop_preheader_edge (LOOP_VINFO_LOOP (loop_vinfo
));
5608 var
= create_tmp_var (TREE_TYPE (ni
), "niters");
5609 ni_name
= force_gimple_operand (ni
, &stmts
, false, var
);
5611 gsi_insert_seq_on_edge_immediate (pe
, stmts
);
5618 /* This function generates the following statements:
5620 ni_name = number of iterations loop executes
5621 ratio = ni_name / vf
5622 ratio_mult_vf_name = ratio * vf
5624 and places them on the loop preheader edge. */
5627 vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo
,
5629 tree
*ratio_mult_vf_name_ptr
,
5630 tree
*ratio_name_ptr
)
5632 tree ni_minus_gap_name
;
5635 tree ratio_mult_vf_name
;
5636 tree ni
= LOOP_VINFO_NITERS (loop_vinfo
);
5637 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
5638 edge pe
= loop_preheader_edge (LOOP_VINFO_LOOP (loop_vinfo
));
5641 log_vf
= build_int_cst (TREE_TYPE (ni
), exact_log2 (vf
));
5643 /* If epilogue loop is required because of data accesses with gaps, we
5644 subtract one iteration from the total number of iterations here for
5645 correct calculation of RATIO. */
5646 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
))
5648 ni_minus_gap_name
= fold_build2 (MINUS_EXPR
, TREE_TYPE (ni_name
),
5650 build_one_cst (TREE_TYPE (ni_name
)));
5651 if (!is_gimple_val (ni_minus_gap_name
))
5653 var
= create_tmp_var (TREE_TYPE (ni
), "ni_gap");
5654 gimple stmts
= NULL
;
5655 ni_minus_gap_name
= force_gimple_operand (ni_minus_gap_name
, &stmts
,
5657 gsi_insert_seq_on_edge_immediate (pe
, stmts
);
5661 ni_minus_gap_name
= ni_name
;
5663 /* Create: ratio = ni >> log2(vf) */
5665 ratio_name
= fold_build2 (RSHIFT_EXPR
, TREE_TYPE (ni_minus_gap_name
),
5666 ni_minus_gap_name
, log_vf
);
5667 if (!is_gimple_val (ratio_name
))
5669 var
= create_tmp_var (TREE_TYPE (ni
), "bnd");
5670 gimple stmts
= NULL
;
5671 ratio_name
= force_gimple_operand (ratio_name
, &stmts
, true, var
);
5672 gsi_insert_seq_on_edge_immediate (pe
, stmts
);
5674 *ratio_name_ptr
= ratio_name
;
5676 /* Create: ratio_mult_vf = ratio << log2 (vf). */
5678 if (ratio_mult_vf_name_ptr
)
5680 ratio_mult_vf_name
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (ratio_name
),
5681 ratio_name
, log_vf
);
5682 if (!is_gimple_val (ratio_mult_vf_name
))
5684 var
= create_tmp_var (TREE_TYPE (ni
), "ratio_mult_vf");
5685 gimple stmts
= NULL
;
5686 ratio_mult_vf_name
= force_gimple_operand (ratio_mult_vf_name
, &stmts
,
5688 gsi_insert_seq_on_edge_immediate (pe
, stmts
);
5690 *ratio_mult_vf_name_ptr
= ratio_mult_vf_name
;
5697 /* Function vect_transform_loop.
5699 The analysis phase has determined that the loop is vectorizable.
5700 Vectorize the loop - created vectorized stmts to replace the scalar
5701 stmts in the loop, and update the loop exit condition. */
5704 vect_transform_loop (loop_vec_info loop_vinfo
)
5706 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5707 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
5708 int nbbs
= loop
->num_nodes
;
5709 gimple_stmt_iterator si
;
5712 int vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
5714 bool slp_scheduled
= false;
5715 gimple stmt
, pattern_stmt
;
5716 gimple_seq pattern_def_seq
= NULL
;
5717 gimple_stmt_iterator pattern_def_si
= gsi_none ();
5718 bool transform_pattern_stmt
= false;
5719 bool check_profitability
= false;
5721 /* Record number of iterations before we started tampering with the profile. */
5722 gcov_type expected_iterations
= expected_loop_iterations_unbounded (loop
);
5724 if (dump_enabled_p ())
5725 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vec_transform_loop ===\n");
5727 /* If profile is inprecise, we have chance to fix it up. */
5728 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
5729 expected_iterations
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
5731 /* Use the more conservative vectorization threshold. If the number
5732 of iterations is constant assume the cost check has been performed
5733 by our caller. If the threshold makes all loops profitable that
5734 run at least the vectorization factor number of times checking
5735 is pointless, too. */
5736 th
= ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND
)
5737 * LOOP_VINFO_VECT_FACTOR (loop_vinfo
)) - 1);
5738 th
= MAX (th
, LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo
));
5739 if (th
>= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) - 1
5740 && !LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
5742 if (dump_enabled_p ())
5743 dump_printf_loc (MSG_NOTE
, vect_location
,
5744 "Profitability threshold is %d loop iterations.\n",
5746 check_profitability
= true;
5749 /* Version the loop first, if required, so the profitability check
5752 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
5753 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
5755 vect_loop_versioning (loop_vinfo
, th
, check_profitability
);
5756 check_profitability
= false;
5759 tree ni_name
= vect_build_loop_niters (loop_vinfo
);
5760 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo
) = ni_name
;
5762 /* Peel the loop if there are data refs with unknown alignment.
5763 Only one data ref with unknown store is allowed. */
5765 if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
))
5767 vect_do_peeling_for_alignment (loop_vinfo
, ni_name
,
5768 th
, check_profitability
);
5769 check_profitability
= false;
5770 /* The above adjusts LOOP_VINFO_NITERS, so cause ni_name to
5772 ni_name
= NULL_TREE
;
5775 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
5776 compile time constant), or it is a constant that doesn't divide by the
5777 vectorization factor, then an epilog loop needs to be created.
5778 We therefore duplicate the loop: the original loop will be vectorized,
5779 and will compute the first (n/VF) iterations. The second copy of the loop
5780 will remain scalar and will compute the remaining (n%VF) iterations.
5781 (VF is the vectorization factor). */
5783 if (LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
)
5784 || LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
))
5788 ni_name
= vect_build_loop_niters (loop_vinfo
);
5789 vect_generate_tmps_on_preheader (loop_vinfo
, ni_name
, &ratio_mult_vf
,
5791 vect_do_peeling_for_loop_bound (loop_vinfo
, ni_name
, ratio_mult_vf
,
5792 th
, check_profitability
);
5794 else if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
5795 ratio
= build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo
)),
5796 LOOP_VINFO_INT_NITERS (loop_vinfo
) / vectorization_factor
);
5800 ni_name
= vect_build_loop_niters (loop_vinfo
);
5801 vect_generate_tmps_on_preheader (loop_vinfo
, ni_name
, NULL
, &ratio
);
5804 /* 1) Make sure the loop header has exactly two entries
5805 2) Make sure we have a preheader basic block. */
5807 gcc_assert (EDGE_COUNT (loop
->header
->preds
) == 2);
5809 split_edge (loop_preheader_edge (loop
));
5811 /* FORNOW: the vectorizer supports only loops which body consist
5812 of one basic block (header + empty latch). When the vectorizer will
5813 support more involved loop forms, the order by which the BBs are
5814 traversed need to be reconsidered. */
5816 for (i
= 0; i
< nbbs
; i
++)
5818 basic_block bb
= bbs
[i
];
5819 stmt_vec_info stmt_info
;
5822 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
5824 phi
= gsi_stmt (si
);
5825 if (dump_enabled_p ())
5827 dump_printf_loc (MSG_NOTE
, vect_location
,
5828 "------>vectorizing phi: ");
5829 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
5830 dump_printf (MSG_NOTE
, "\n");
5832 stmt_info
= vinfo_for_stmt (phi
);
5836 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
5837 vect_loop_kill_debug_uses (loop
, phi
);
5839 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
5840 && !STMT_VINFO_LIVE_P (stmt_info
))
5843 if ((TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
))
5844 != (unsigned HOST_WIDE_INT
) vectorization_factor
)
5845 && dump_enabled_p ())
5846 dump_printf_loc (MSG_NOTE
, vect_location
, "multiple-types.\n");
5848 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
5850 if (dump_enabled_p ())
5851 dump_printf_loc (MSG_NOTE
, vect_location
, "transform phi.\n");
5852 vect_transform_stmt (phi
, NULL
, NULL
, NULL
, NULL
);
5856 pattern_stmt
= NULL
;
5857 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
) || transform_pattern_stmt
;)
5861 if (transform_pattern_stmt
)
5862 stmt
= pattern_stmt
;
5865 stmt
= gsi_stmt (si
);
5866 /* During vectorization remove existing clobber stmts. */
5867 if (gimple_clobber_p (stmt
))
5869 unlink_stmt_vdef (stmt
);
5870 gsi_remove (&si
, true);
5871 release_defs (stmt
);
5876 if (dump_enabled_p ())
5878 dump_printf_loc (MSG_NOTE
, vect_location
,
5879 "------>vectorizing statement: ");
5880 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
5881 dump_printf (MSG_NOTE
, "\n");
5884 stmt_info
= vinfo_for_stmt (stmt
);
5886 /* vector stmts created in the outer-loop during vectorization of
5887 stmts in an inner-loop may not have a stmt_info, and do not
5888 need to be vectorized. */
5895 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
5896 vect_loop_kill_debug_uses (loop
, stmt
);
5898 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
5899 && !STMT_VINFO_LIVE_P (stmt_info
))
5901 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
5902 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
5903 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
5904 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
5906 stmt
= pattern_stmt
;
5907 stmt_info
= vinfo_for_stmt (stmt
);
5915 else if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
5916 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
5917 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
5918 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
5919 transform_pattern_stmt
= true;
5921 /* If pattern statement has def stmts, vectorize them too. */
5922 if (is_pattern_stmt_p (stmt_info
))
5924 if (pattern_def_seq
== NULL
)
5926 pattern_def_seq
= STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
);
5927 pattern_def_si
= gsi_start (pattern_def_seq
);
5929 else if (!gsi_end_p (pattern_def_si
))
5930 gsi_next (&pattern_def_si
);
5931 if (pattern_def_seq
!= NULL
)
5933 gimple pattern_def_stmt
= NULL
;
5934 stmt_vec_info pattern_def_stmt_info
= NULL
;
5936 while (!gsi_end_p (pattern_def_si
))
5938 pattern_def_stmt
= gsi_stmt (pattern_def_si
);
5939 pattern_def_stmt_info
5940 = vinfo_for_stmt (pattern_def_stmt
);
5941 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info
)
5942 || STMT_VINFO_LIVE_P (pattern_def_stmt_info
))
5944 gsi_next (&pattern_def_si
);
5947 if (!gsi_end_p (pattern_def_si
))
5949 if (dump_enabled_p ())
5951 dump_printf_loc (MSG_NOTE
, vect_location
,
5952 "==> vectorizing pattern def "
5954 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
5955 pattern_def_stmt
, 0);
5956 dump_printf (MSG_NOTE
, "\n");
5959 stmt
= pattern_def_stmt
;
5960 stmt_info
= pattern_def_stmt_info
;
5964 pattern_def_si
= gsi_none ();
5965 transform_pattern_stmt
= false;
5969 transform_pattern_stmt
= false;
5972 if (STMT_VINFO_VECTYPE (stmt_info
))
5976 TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
5977 if (!STMT_SLP_TYPE (stmt_info
)
5978 && nunits
!= (unsigned int) vectorization_factor
5979 && dump_enabled_p ())
5980 /* For SLP VF is set according to unrolling factor, and not
5981 to vector size, hence for SLP this print is not valid. */
5982 dump_printf_loc (MSG_NOTE
, vect_location
, "multiple-types.\n");
5985 /* SLP. Schedule all the SLP instances when the first SLP stmt is
5987 if (STMT_SLP_TYPE (stmt_info
))
5991 slp_scheduled
= true;
5993 if (dump_enabled_p ())
5994 dump_printf_loc (MSG_NOTE
, vect_location
,
5995 "=== scheduling SLP instances ===\n");
5997 vect_schedule_slp (loop_vinfo
, NULL
);
6000 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
6001 if (!vinfo_for_stmt (stmt
) || PURE_SLP_STMT (stmt_info
))
6003 if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
6005 pattern_def_seq
= NULL
;
6012 /* -------- vectorize statement ------------ */
6013 if (dump_enabled_p ())
6014 dump_printf_loc (MSG_NOTE
, vect_location
, "transform statement.\n");
6016 grouped_store
= false;
6017 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, NULL
, NULL
);
6020 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
6022 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
6023 interleaving chain was completed - free all the stores in
6026 vect_remove_stores (GROUP_FIRST_ELEMENT (stmt_info
));
6031 /* Free the attached stmt_vec_info and remove the stmt. */
6032 gimple store
= gsi_stmt (si
);
6033 free_stmt_vec_info (store
);
6034 unlink_stmt_vdef (store
);
6035 gsi_remove (&si
, true);
6036 release_defs (store
);
6041 if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
6043 pattern_def_seq
= NULL
;
6049 slpeel_make_loop_iterate_ntimes (loop
, ratio
);
6051 /* Reduce loop iterations by the vectorization factor. */
6052 scale_loop_profile (loop
, GCOV_COMPUTE_SCALE (1, vectorization_factor
),
6053 expected_iterations
/ vectorization_factor
);
6054 loop
->nb_iterations_upper_bound
6055 = loop
->nb_iterations_upper_bound
.udiv (double_int::from_uhwi (vectorization_factor
),
6057 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
6058 && loop
->nb_iterations_upper_bound
!= double_int_zero
)
6059 loop
->nb_iterations_upper_bound
= loop
->nb_iterations_upper_bound
- double_int_one
;
6060 if (loop
->any_estimate
)
6062 loop
->nb_iterations_estimate
6063 = loop
->nb_iterations_estimate
.udiv (double_int::from_uhwi (vectorization_factor
),
6065 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
6066 && loop
->nb_iterations_estimate
!= double_int_zero
)
6067 loop
->nb_iterations_estimate
= loop
->nb_iterations_estimate
- double_int_one
;
6070 if (dump_enabled_p ())
6072 dump_printf_loc (MSG_NOTE
, vect_location
,
6073 "LOOP VECTORIZED\n");
6075 dump_printf_loc (MSG_NOTE
, vect_location
,
6076 "OUTER LOOP VECTORIZED\n");
6077 dump_printf (MSG_NOTE
, "\n");