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"
29 #include "stor-layout.h"
30 #include "basic-block.h"
31 #include "gimple-pretty-print.h"
34 #include "gimple-iterator.h"
35 #include "gimplify-me.h"
36 #include "gimple-ssa.h"
37 #include "tree-phinodes.h"
38 #include "ssa-iterators.h"
39 #include "stringpool.h"
40 #include "tree-ssanames.h"
41 #include "tree-ssa-loop-ivopts.h"
42 #include "tree-ssa-loop-manip.h"
43 #include "tree-ssa-loop-niter.h"
44 #include "tree-pass.h"
50 #include "diagnostic-core.h"
51 #include "tree-chrec.h"
52 #include "tree-scalar-evolution.h"
53 #include "tree-vectorizer.h"
56 /* Loop Vectorization Pass.
58 This pass tries to vectorize loops.
60 For example, the vectorizer transforms the following simple loop:
62 short a[N]; short b[N]; short c[N]; int i;
68 as if it was manually vectorized by rewriting the source code into:
70 typedef int __attribute__((mode(V8HI))) v8hi;
71 short a[N]; short b[N]; short c[N]; int i;
72 v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
75 for (i=0; i<N/8; i++){
82 The main entry to this pass is vectorize_loops(), in which
83 the vectorizer applies a set of analyses on a given set of loops,
84 followed by the actual vectorization transformation for the loops that
85 had successfully passed the analysis phase.
86 Throughout this pass we make a distinction between two types of
87 data: scalars (which are represented by SSA_NAMES), and memory references
88 ("data-refs"). These two types of data require different handling both
89 during analysis and transformation. The types of data-refs that the
90 vectorizer currently supports are ARRAY_REFS which base is an array DECL
91 (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
92 accesses are required to have a simple (consecutive) access pattern.
96 The driver for the analysis phase is vect_analyze_loop().
97 It applies a set of analyses, some of which rely on the scalar evolution
98 analyzer (scev) developed by Sebastian Pop.
100 During the analysis phase the vectorizer records some information
101 per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
102 loop, as well as general information about the loop as a whole, which is
103 recorded in a "loop_vec_info" struct attached to each loop.
105 Transformation phase:
106 =====================
107 The loop transformation phase scans all the stmts in the loop, and
108 creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
109 the loop that needs to be vectorized. It inserts the vector code sequence
110 just before the scalar stmt S, and records a pointer to the vector code
111 in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
112 attached to S). This pointer will be used for the vectorization of following
113 stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
114 otherwise, we rely on dead code elimination for removing it.
116 For example, say stmt S1 was vectorized into stmt VS1:
119 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
122 To vectorize stmt S2, the vectorizer first finds the stmt that defines
123 the operand 'b' (S1), and gets the relevant vector def 'vb' from the
124 vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
125 resulting sequence would be:
128 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
130 S2: a = b; STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
132 Operands that are not SSA_NAMEs, are data-refs that appear in
133 load/store operations (like 'x[i]' in S1), and are handled differently.
137 Currently the only target specific information that is used is the
138 size of the vector (in bytes) - "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD".
139 Targets that can support different sizes of vectors, for now will need
140 to specify one value for "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD". More
141 flexibility will be added in the future.
143 Since we only vectorize operations which vector form can be
144 expressed using existing tree codes, to verify that an operation is
145 supported, the vectorizer checks the relevant optab at the relevant
146 machine_mode (e.g, optab_handler (add_optab, V8HImode)). If
147 the value found is CODE_FOR_nothing, then there's no target support, and
148 we can't vectorize the stmt.
150 For additional information on this project see:
151 http://gcc.gnu.org/projects/tree-ssa/vectorization.html
154 static void vect_estimate_min_profitable_iters (loop_vec_info
, int *, int *);
156 /* Function vect_determine_vectorization_factor
158 Determine the vectorization factor (VF). VF is the number of data elements
159 that are operated upon in parallel in a single iteration of the vectorized
160 loop. For example, when vectorizing a loop that operates on 4byte elements,
161 on a target with vector size (VS) 16byte, the VF is set to 4, since 4
162 elements can fit in a single vector register.
164 We currently support vectorization of loops in which all types operated upon
165 are of the same size. Therefore this function currently sets VF according to
166 the size of the types operated upon, and fails if there are multiple sizes
169 VF is also the factor by which the loop iterations are strip-mined, e.g.:
176 for (i=0; i<N; i+=VF){
177 a[i:VF] = b[i:VF] + c[i:VF];
182 vect_determine_vectorization_factor (loop_vec_info loop_vinfo
)
184 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
185 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
186 int nbbs
= loop
->num_nodes
;
187 gimple_stmt_iterator si
;
188 unsigned int vectorization_factor
= 0;
193 stmt_vec_info stmt_info
;
196 gimple stmt
, pattern_stmt
= NULL
;
197 gimple_seq pattern_def_seq
= NULL
;
198 gimple_stmt_iterator pattern_def_si
= gsi_none ();
199 bool analyze_pattern_stmt
= false;
201 if (dump_enabled_p ())
202 dump_printf_loc (MSG_NOTE
, vect_location
,
203 "=== vect_determine_vectorization_factor ===\n");
205 for (i
= 0; i
< nbbs
; i
++)
207 basic_block bb
= bbs
[i
];
209 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
212 stmt_info
= vinfo_for_stmt (phi
);
213 if (dump_enabled_p ())
215 dump_printf_loc (MSG_NOTE
, vect_location
, "==> examining phi: ");
216 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
217 dump_printf (MSG_NOTE
, "\n");
220 gcc_assert (stmt_info
);
222 if (STMT_VINFO_RELEVANT_P (stmt_info
))
224 gcc_assert (!STMT_VINFO_VECTYPE (stmt_info
));
225 scalar_type
= TREE_TYPE (PHI_RESULT (phi
));
227 if (dump_enabled_p ())
229 dump_printf_loc (MSG_NOTE
, vect_location
,
230 "get vectype for scalar type: ");
231 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
232 dump_printf (MSG_NOTE
, "\n");
235 vectype
= get_vectype_for_scalar_type (scalar_type
);
238 if (dump_enabled_p ())
240 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
241 "not vectorized: unsupported "
243 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
245 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
249 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
251 if (dump_enabled_p ())
253 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
254 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vectype
);
255 dump_printf (MSG_NOTE
, "\n");
258 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
259 if (dump_enabled_p ())
260 dump_printf_loc (MSG_NOTE
, vect_location
, "nunits = %d\n",
263 if (!vectorization_factor
264 || (nunits
> vectorization_factor
))
265 vectorization_factor
= nunits
;
269 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
) || analyze_pattern_stmt
;)
273 if (analyze_pattern_stmt
)
276 stmt
= gsi_stmt (si
);
278 stmt_info
= vinfo_for_stmt (stmt
);
280 if (dump_enabled_p ())
282 dump_printf_loc (MSG_NOTE
, vect_location
,
283 "==> examining statement: ");
284 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
285 dump_printf (MSG_NOTE
, "\n");
288 gcc_assert (stmt_info
);
290 /* Skip stmts which do not need to be vectorized. */
291 if ((!STMT_VINFO_RELEVANT_P (stmt_info
)
292 && !STMT_VINFO_LIVE_P (stmt_info
))
293 || gimple_clobber_p (stmt
))
295 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
296 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
297 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
298 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
301 stmt_info
= vinfo_for_stmt (pattern_stmt
);
302 if (dump_enabled_p ())
304 dump_printf_loc (MSG_NOTE
, vect_location
,
305 "==> examining pattern statement: ");
306 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
307 dump_printf (MSG_NOTE
, "\n");
312 if (dump_enabled_p ())
313 dump_printf_loc (MSG_NOTE
, vect_location
, "skip.\n");
318 else if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
319 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
320 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
321 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
322 analyze_pattern_stmt
= true;
324 /* If a pattern statement has def stmts, analyze them too. */
325 if (is_pattern_stmt_p (stmt_info
))
327 if (pattern_def_seq
== NULL
)
329 pattern_def_seq
= STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
);
330 pattern_def_si
= gsi_start (pattern_def_seq
);
332 else if (!gsi_end_p (pattern_def_si
))
333 gsi_next (&pattern_def_si
);
334 if (pattern_def_seq
!= NULL
)
336 gimple pattern_def_stmt
= NULL
;
337 stmt_vec_info pattern_def_stmt_info
= NULL
;
339 while (!gsi_end_p (pattern_def_si
))
341 pattern_def_stmt
= gsi_stmt (pattern_def_si
);
342 pattern_def_stmt_info
343 = vinfo_for_stmt (pattern_def_stmt
);
344 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info
)
345 || STMT_VINFO_LIVE_P (pattern_def_stmt_info
))
347 gsi_next (&pattern_def_si
);
350 if (!gsi_end_p (pattern_def_si
))
352 if (dump_enabled_p ())
354 dump_printf_loc (MSG_NOTE
, vect_location
,
355 "==> examining pattern def stmt: ");
356 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
357 pattern_def_stmt
, 0);
358 dump_printf (MSG_NOTE
, "\n");
361 stmt
= pattern_def_stmt
;
362 stmt_info
= pattern_def_stmt_info
;
366 pattern_def_si
= gsi_none ();
367 analyze_pattern_stmt
= false;
371 analyze_pattern_stmt
= false;
374 if (gimple_get_lhs (stmt
) == NULL_TREE
)
376 if (dump_enabled_p ())
378 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
379 "not vectorized: irregular stmt.");
380 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
,
382 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
387 if (VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt
))))
389 if (dump_enabled_p ())
391 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
392 "not vectorized: vector stmt in loop:");
393 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
394 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
399 if (STMT_VINFO_VECTYPE (stmt_info
))
401 /* The only case when a vectype had been already set is for stmts
402 that contain a dataref, or for "pattern-stmts" (stmts
403 generated by the vectorizer to represent/replace a certain
405 gcc_assert (STMT_VINFO_DATA_REF (stmt_info
)
406 || is_pattern_stmt_p (stmt_info
)
407 || !gsi_end_p (pattern_def_si
));
408 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
412 gcc_assert (!STMT_VINFO_DATA_REF (stmt_info
));
413 scalar_type
= TREE_TYPE (gimple_get_lhs (stmt
));
414 if (dump_enabled_p ())
416 dump_printf_loc (MSG_NOTE
, vect_location
,
417 "get vectype for scalar type: ");
418 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
419 dump_printf (MSG_NOTE
, "\n");
421 vectype
= get_vectype_for_scalar_type (scalar_type
);
424 if (dump_enabled_p ())
426 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
427 "not vectorized: unsupported "
429 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
431 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
436 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
438 if (dump_enabled_p ())
440 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
441 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vectype
);
442 dump_printf (MSG_NOTE
, "\n");
446 /* The vectorization factor is according to the smallest
447 scalar type (or the largest vector size, but we only
448 support one vector size per loop). */
449 scalar_type
= vect_get_smallest_scalar_type (stmt
, &dummy
,
451 if (dump_enabled_p ())
453 dump_printf_loc (MSG_NOTE
, vect_location
,
454 "get vectype for scalar type: ");
455 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
456 dump_printf (MSG_NOTE
, "\n");
458 vf_vectype
= get_vectype_for_scalar_type (scalar_type
);
461 if (dump_enabled_p ())
463 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
464 "not vectorized: unsupported data-type ");
465 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
467 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
472 if ((GET_MODE_SIZE (TYPE_MODE (vectype
))
473 != GET_MODE_SIZE (TYPE_MODE (vf_vectype
))))
475 if (dump_enabled_p ())
477 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
478 "not vectorized: different sized vector "
479 "types in statement, ");
480 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
482 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
483 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
485 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
490 if (dump_enabled_p ())
492 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
493 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vf_vectype
);
494 dump_printf (MSG_NOTE
, "\n");
497 nunits
= TYPE_VECTOR_SUBPARTS (vf_vectype
);
498 if (dump_enabled_p ())
499 dump_printf_loc (MSG_NOTE
, vect_location
, "nunits = %d\n", nunits
);
500 if (!vectorization_factor
501 || (nunits
> vectorization_factor
))
502 vectorization_factor
= nunits
;
504 if (!analyze_pattern_stmt
&& gsi_end_p (pattern_def_si
))
506 pattern_def_seq
= NULL
;
512 /* TODO: Analyze cost. Decide if worth while to vectorize. */
513 if (dump_enabled_p ())
514 dump_printf_loc (MSG_NOTE
, vect_location
, "vectorization factor = %d\n",
515 vectorization_factor
);
516 if (vectorization_factor
<= 1)
518 if (dump_enabled_p ())
519 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
520 "not vectorized: unsupported data-type\n");
523 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
529 /* Function vect_is_simple_iv_evolution.
531 FORNOW: A simple evolution of an induction variables in the loop is
532 considered a polynomial evolution. */
535 vect_is_simple_iv_evolution (unsigned loop_nb
, tree access_fn
, tree
* init
,
540 tree evolution_part
= evolution_part_in_loop_num (access_fn
, loop_nb
);
543 /* When there is no evolution in this loop, the evolution function
545 if (evolution_part
== NULL_TREE
)
548 /* When the evolution is a polynomial of degree >= 2
549 the evolution function is not "simple". */
550 if (tree_is_chrec (evolution_part
))
553 step_expr
= evolution_part
;
554 init_expr
= unshare_expr (initial_condition_in_loop_num (access_fn
, loop_nb
));
556 if (dump_enabled_p ())
558 dump_printf_loc (MSG_NOTE
, vect_location
, "step: ");
559 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, step_expr
);
560 dump_printf (MSG_NOTE
, ", init: ");
561 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, init_expr
);
562 dump_printf (MSG_NOTE
, "\n");
568 if (TREE_CODE (step_expr
) != INTEGER_CST
569 && (TREE_CODE (step_expr
) != SSA_NAME
570 || ((bb
= gimple_bb (SSA_NAME_DEF_STMT (step_expr
)))
571 && flow_bb_inside_loop_p (get_loop (cfun
, loop_nb
), bb
))
572 || (!INTEGRAL_TYPE_P (TREE_TYPE (step_expr
))
573 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
))
574 || !flag_associative_math
)))
575 && (TREE_CODE (step_expr
) != REAL_CST
576 || !flag_associative_math
))
578 if (dump_enabled_p ())
579 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
587 /* Function vect_analyze_scalar_cycles_1.
589 Examine the cross iteration def-use cycles of scalar variables
590 in LOOP. LOOP_VINFO represents the loop that is now being
591 considered for vectorization (can be LOOP, or an outer-loop
595 vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo
, struct loop
*loop
)
597 basic_block bb
= loop
->header
;
599 stack_vec
<gimple
, 64> worklist
;
600 gimple_stmt_iterator gsi
;
603 if (dump_enabled_p ())
604 dump_printf_loc (MSG_NOTE
, vect_location
,
605 "=== vect_analyze_scalar_cycles ===\n");
607 /* First - identify all inductions. Reduction detection assumes that all the
608 inductions have been identified, therefore, this order must not be
610 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
612 gimple phi
= gsi_stmt (gsi
);
613 tree access_fn
= NULL
;
614 tree def
= PHI_RESULT (phi
);
615 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (phi
);
617 if (dump_enabled_p ())
619 dump_printf_loc (MSG_NOTE
, vect_location
, "Analyze phi: ");
620 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
621 dump_printf (MSG_NOTE
, "\n");
624 /* Skip virtual phi's. The data dependences that are associated with
625 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
626 if (virtual_operand_p (def
))
629 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_unknown_def_type
;
631 /* Analyze the evolution function. */
632 access_fn
= analyze_scalar_evolution (loop
, def
);
635 STRIP_NOPS (access_fn
);
636 if (dump_enabled_p ())
638 dump_printf_loc (MSG_NOTE
, vect_location
,
639 "Access function of PHI: ");
640 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, access_fn
);
641 dump_printf (MSG_NOTE
, "\n");
643 STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
)
644 = evolution_part_in_loop_num (access_fn
, loop
->num
);
648 || !vect_is_simple_iv_evolution (loop
->num
, access_fn
, &init
, &step
)
649 || (LOOP_VINFO_LOOP (loop_vinfo
) != loop
650 && TREE_CODE (step
) != INTEGER_CST
))
652 worklist
.safe_push (phi
);
656 gcc_assert (STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
) != NULL_TREE
);
658 if (dump_enabled_p ())
659 dump_printf_loc (MSG_NOTE
, vect_location
, "Detected induction.\n");
660 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_induction_def
;
664 /* Second - identify all reductions and nested cycles. */
665 while (worklist
.length () > 0)
667 gimple phi
= worklist
.pop ();
668 tree def
= PHI_RESULT (phi
);
669 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (phi
);
673 if (dump_enabled_p ())
675 dump_printf_loc (MSG_NOTE
, vect_location
, "Analyze phi: ");
676 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
677 dump_printf (MSG_NOTE
, "\n");
680 gcc_assert (!virtual_operand_p (def
)
681 && STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_unknown_def_type
);
683 nested_cycle
= (loop
!= LOOP_VINFO_LOOP (loop_vinfo
));
684 reduc_stmt
= vect_force_simple_reduction (loop_vinfo
, phi
, !nested_cycle
,
690 if (dump_enabled_p ())
691 dump_printf_loc (MSG_NOTE
, vect_location
,
692 "Detected double reduction.\n");
694 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_double_reduction_def
;
695 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
696 vect_double_reduction_def
;
702 if (dump_enabled_p ())
703 dump_printf_loc (MSG_NOTE
, vect_location
,
704 "Detected vectorizable nested cycle.\n");
706 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_nested_cycle
;
707 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
712 if (dump_enabled_p ())
713 dump_printf_loc (MSG_NOTE
, vect_location
,
714 "Detected reduction.\n");
716 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_reduction_def
;
717 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
719 /* Store the reduction cycles for possible vectorization in
721 LOOP_VINFO_REDUCTIONS (loop_vinfo
).safe_push (reduc_stmt
);
726 if (dump_enabled_p ())
727 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
728 "Unknown def-use cycle pattern.\n");
733 /* Function vect_analyze_scalar_cycles.
735 Examine the cross iteration def-use cycles of scalar variables, by
736 analyzing the loop-header PHIs of scalar variables. Classify each
737 cycle as one of the following: invariant, induction, reduction, unknown.
738 We do that for the loop represented by LOOP_VINFO, and also to its
739 inner-loop, if exists.
740 Examples for scalar cycles:
755 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo
)
757 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
759 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
);
761 /* When vectorizing an outer-loop, the inner-loop is executed sequentially.
762 Reductions in such inner-loop therefore have different properties than
763 the reductions in the nest that gets vectorized:
764 1. When vectorized, they are executed in the same order as in the original
765 scalar loop, so we can't change the order of computation when
767 2. FIXME: Inner-loop reductions can be used in the inner-loop, so the
768 current checks are too strict. */
771 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
->inner
);
774 /* Function vect_get_loop_niters.
776 Determine how many iterations the loop is executed.
777 If an expression that represents the number of iterations
778 can be constructed, place it in NUMBER_OF_ITERATIONS.
779 Return the loop exit condition. */
782 vect_get_loop_niters (struct loop
*loop
, tree
*number_of_iterations
)
786 if (dump_enabled_p ())
787 dump_printf_loc (MSG_NOTE
, vect_location
,
788 "=== get_loop_niters ===\n");
789 niters
= number_of_exit_cond_executions (loop
);
791 if (niters
!= NULL_TREE
792 && niters
!= chrec_dont_know
)
794 *number_of_iterations
= niters
;
796 if (dump_enabled_p ())
798 dump_printf_loc (MSG_NOTE
, vect_location
, "==> get_loop_niters:");
799 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, *number_of_iterations
);
800 dump_printf (MSG_NOTE
, "\n");
804 return get_loop_exit_condition (loop
);
808 /* Function bb_in_loop_p
810 Used as predicate for dfs order traversal of the loop bbs. */
813 bb_in_loop_p (const_basic_block bb
, const void *data
)
815 const struct loop
*const loop
= (const struct loop
*)data
;
816 if (flow_bb_inside_loop_p (loop
, bb
))
822 /* Function new_loop_vec_info.
824 Create and initialize a new loop_vec_info struct for LOOP, as well as
825 stmt_vec_info structs for all the stmts in LOOP. */
828 new_loop_vec_info (struct loop
*loop
)
832 gimple_stmt_iterator si
;
833 unsigned int i
, nbbs
;
835 res
= (loop_vec_info
) xcalloc (1, sizeof (struct _loop_vec_info
));
836 LOOP_VINFO_LOOP (res
) = loop
;
838 bbs
= get_loop_body (loop
);
840 /* Create/Update stmt_info for all stmts in the loop. */
841 for (i
= 0; i
< loop
->num_nodes
; i
++)
843 basic_block bb
= bbs
[i
];
845 /* BBs in a nested inner-loop will have been already processed (because
846 we will have called vect_analyze_loop_form for any nested inner-loop).
847 Therefore, for stmts in an inner-loop we just want to update the
848 STMT_VINFO_LOOP_VINFO field of their stmt_info to point to the new
849 loop_info of the outer-loop we are currently considering to vectorize
850 (instead of the loop_info of the inner-loop).
851 For stmts in other BBs we need to create a stmt_info from scratch. */
852 if (bb
->loop_father
!= loop
)
855 gcc_assert (loop
->inner
&& bb
->loop_father
== loop
->inner
);
856 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
858 gimple phi
= gsi_stmt (si
);
859 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
860 loop_vec_info inner_loop_vinfo
=
861 STMT_VINFO_LOOP_VINFO (stmt_info
);
862 gcc_assert (loop
->inner
== LOOP_VINFO_LOOP (inner_loop_vinfo
));
863 STMT_VINFO_LOOP_VINFO (stmt_info
) = res
;
865 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
867 gimple stmt
= gsi_stmt (si
);
868 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
869 loop_vec_info inner_loop_vinfo
=
870 STMT_VINFO_LOOP_VINFO (stmt_info
);
871 gcc_assert (loop
->inner
== LOOP_VINFO_LOOP (inner_loop_vinfo
));
872 STMT_VINFO_LOOP_VINFO (stmt_info
) = res
;
877 /* bb in current nest. */
878 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
880 gimple phi
= gsi_stmt (si
);
881 gimple_set_uid (phi
, 0);
882 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, res
, NULL
));
885 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
887 gimple stmt
= gsi_stmt (si
);
888 gimple_set_uid (stmt
, 0);
889 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, res
, NULL
));
894 /* CHECKME: We want to visit all BBs before their successors (except for
895 latch blocks, for which this assertion wouldn't hold). In the simple
896 case of the loop forms we allow, a dfs order of the BBs would the same
897 as reversed postorder traversal, so we are safe. */
900 bbs
= XCNEWVEC (basic_block
, loop
->num_nodes
);
901 nbbs
= dfs_enumerate_from (loop
->header
, 0, bb_in_loop_p
,
902 bbs
, loop
->num_nodes
, loop
);
903 gcc_assert (nbbs
== loop
->num_nodes
);
905 LOOP_VINFO_BBS (res
) = bbs
;
906 LOOP_VINFO_NITERS (res
) = NULL
;
907 LOOP_VINFO_NITERS_UNCHANGED (res
) = NULL
;
908 LOOP_VINFO_COST_MODEL_MIN_ITERS (res
) = 0;
909 LOOP_VINFO_VECTORIZABLE_P (res
) = 0;
910 LOOP_PEELING_FOR_ALIGNMENT (res
) = 0;
911 LOOP_VINFO_VECT_FACTOR (res
) = 0;
912 LOOP_VINFO_LOOP_NEST (res
).create (3);
913 LOOP_VINFO_DATAREFS (res
).create (10);
914 LOOP_VINFO_DDRS (res
).create (10 * 10);
915 LOOP_VINFO_UNALIGNED_DR (res
) = NULL
;
916 LOOP_VINFO_MAY_MISALIGN_STMTS (res
).create (
917 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS
));
918 LOOP_VINFO_MAY_ALIAS_DDRS (res
).create (
919 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS
));
920 LOOP_VINFO_GROUPED_STORES (res
).create (10);
921 LOOP_VINFO_REDUCTIONS (res
).create (10);
922 LOOP_VINFO_REDUCTION_CHAINS (res
).create (10);
923 LOOP_VINFO_SLP_INSTANCES (res
).create (10);
924 LOOP_VINFO_SLP_UNROLLING_FACTOR (res
) = 1;
925 LOOP_VINFO_TARGET_COST_DATA (res
) = init_cost (loop
);
926 LOOP_VINFO_PEELING_FOR_GAPS (res
) = false;
927 LOOP_VINFO_OPERANDS_SWAPPED (res
) = false;
933 /* Function destroy_loop_vec_info.
935 Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
936 stmts in the loop. */
939 destroy_loop_vec_info (loop_vec_info loop_vinfo
, bool clean_stmts
)
944 gimple_stmt_iterator si
;
946 vec
<slp_instance
> slp_instances
;
947 slp_instance instance
;
953 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
955 bbs
= LOOP_VINFO_BBS (loop_vinfo
);
956 nbbs
= clean_stmts
? loop
->num_nodes
: 0;
957 swapped
= LOOP_VINFO_OPERANDS_SWAPPED (loop_vinfo
);
959 for (j
= 0; j
< nbbs
; j
++)
961 basic_block bb
= bbs
[j
];
962 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
963 free_stmt_vec_info (gsi_stmt (si
));
965 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); )
967 gimple stmt
= gsi_stmt (si
);
969 /* We may have broken canonical form by moving a constant
970 into RHS1 of a commutative op. Fix such occurrences. */
971 if (swapped
&& is_gimple_assign (stmt
))
973 enum tree_code code
= gimple_assign_rhs_code (stmt
);
975 if ((code
== PLUS_EXPR
976 || code
== POINTER_PLUS_EXPR
977 || code
== MULT_EXPR
)
978 && CONSTANT_CLASS_P (gimple_assign_rhs1 (stmt
)))
979 swap_ssa_operands (stmt
,
980 gimple_assign_rhs1_ptr (stmt
),
981 gimple_assign_rhs2_ptr (stmt
));
984 /* Free stmt_vec_info. */
985 free_stmt_vec_info (stmt
);
990 free (LOOP_VINFO_BBS (loop_vinfo
));
991 vect_destroy_datarefs (loop_vinfo
, NULL
);
992 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo
));
993 LOOP_VINFO_LOOP_NEST (loop_vinfo
).release ();
994 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).release ();
995 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
).release ();
996 slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
997 FOR_EACH_VEC_ELT (slp_instances
, j
, instance
)
998 vect_free_slp_instance (instance
);
1000 LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).release ();
1001 LOOP_VINFO_GROUPED_STORES (loop_vinfo
).release ();
1002 LOOP_VINFO_REDUCTIONS (loop_vinfo
).release ();
1003 LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
).release ();
1005 if (LOOP_VINFO_PEELING_HTAB (loop_vinfo
).is_created ())
1006 LOOP_VINFO_PEELING_HTAB (loop_vinfo
).dispose ();
1008 destroy_cost_data (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
));
1015 /* Function vect_analyze_loop_1.
1017 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1018 for it. The different analyses will record information in the
1019 loop_vec_info struct. This is a subset of the analyses applied in
1020 vect_analyze_loop, to be applied on an inner-loop nested in the loop
1021 that is now considered for (outer-loop) vectorization. */
1023 static loop_vec_info
1024 vect_analyze_loop_1 (struct loop
*loop
)
1026 loop_vec_info loop_vinfo
;
1028 if (dump_enabled_p ())
1029 dump_printf_loc (MSG_NOTE
, vect_location
,
1030 "===== analyze_loop_nest_1 =====\n");
1032 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
1034 loop_vinfo
= vect_analyze_loop_form (loop
);
1037 if (dump_enabled_p ())
1038 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1039 "bad inner-loop form.\n");
1047 /* Function vect_analyze_loop_form.
1049 Verify that certain CFG restrictions hold, including:
1050 - the loop has a pre-header
1051 - the loop has a single entry and exit
1052 - the loop exit condition is simple enough, and the number of iterations
1053 can be analyzed (a countable loop). */
1056 vect_analyze_loop_form (struct loop
*loop
)
1058 loop_vec_info loop_vinfo
;
1060 tree number_of_iterations
= NULL
;
1061 loop_vec_info inner_loop_vinfo
= NULL
;
1063 if (dump_enabled_p ())
1064 dump_printf_loc (MSG_NOTE
, vect_location
,
1065 "=== vect_analyze_loop_form ===\n");
1067 /* Different restrictions apply when we are considering an inner-most loop,
1068 vs. an outer (nested) loop.
1069 (FORNOW. May want to relax some of these restrictions in the future). */
1073 /* Inner-most loop. We currently require that the number of BBs is
1074 exactly 2 (the header and latch). Vectorizable inner-most loops
1085 if (loop
->num_nodes
!= 2)
1087 if (dump_enabled_p ())
1088 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1089 "not vectorized: control flow in loop.\n");
1093 if (empty_block_p (loop
->header
))
1095 if (dump_enabled_p ())
1096 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1097 "not vectorized: empty loop.\n");
1103 struct loop
*innerloop
= loop
->inner
;
1106 /* Nested loop. We currently require that the loop is doubly-nested,
1107 contains a single inner loop, and the number of BBs is exactly 5.
1108 Vectorizable outer-loops look like this:
1120 The inner-loop has the properties expected of inner-most loops
1121 as described above. */
1123 if ((loop
->inner
)->inner
|| (loop
->inner
)->next
)
1125 if (dump_enabled_p ())
1126 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1127 "not vectorized: multiple nested loops.\n");
1131 /* Analyze the inner-loop. */
1132 inner_loop_vinfo
= vect_analyze_loop_1 (loop
->inner
);
1133 if (!inner_loop_vinfo
)
1135 if (dump_enabled_p ())
1136 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1137 "not vectorized: Bad inner loop.\n");
1141 if (!expr_invariant_in_loop_p (loop
,
1142 LOOP_VINFO_NITERS (inner_loop_vinfo
)))
1144 if (dump_enabled_p ())
1145 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1146 "not vectorized: inner-loop count not"
1148 destroy_loop_vec_info (inner_loop_vinfo
, true);
1152 if (loop
->num_nodes
!= 5)
1154 if (dump_enabled_p ())
1155 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1156 "not vectorized: control flow in loop.\n");
1157 destroy_loop_vec_info (inner_loop_vinfo
, true);
1161 gcc_assert (EDGE_COUNT (innerloop
->header
->preds
) == 2);
1162 entryedge
= EDGE_PRED (innerloop
->header
, 0);
1163 if (EDGE_PRED (innerloop
->header
, 0)->src
== innerloop
->latch
)
1164 entryedge
= EDGE_PRED (innerloop
->header
, 1);
1166 if (entryedge
->src
!= loop
->header
1167 || !single_exit (innerloop
)
1168 || single_exit (innerloop
)->dest
!= EDGE_PRED (loop
->latch
, 0)->src
)
1170 if (dump_enabled_p ())
1171 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1172 "not vectorized: unsupported outerloop form.\n");
1173 destroy_loop_vec_info (inner_loop_vinfo
, true);
1177 if (dump_enabled_p ())
1178 dump_printf_loc (MSG_NOTE
, vect_location
,
1179 "Considering outer-loop vectorization.\n");
1182 if (!single_exit (loop
)
1183 || EDGE_COUNT (loop
->header
->preds
) != 2)
1185 if (dump_enabled_p ())
1187 if (!single_exit (loop
))
1188 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1189 "not vectorized: multiple exits.\n");
1190 else if (EDGE_COUNT (loop
->header
->preds
) != 2)
1191 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1192 "not vectorized: too many incoming edges.\n");
1194 if (inner_loop_vinfo
)
1195 destroy_loop_vec_info (inner_loop_vinfo
, true);
1199 /* We assume that the loop exit condition is at the end of the loop. i.e,
1200 that the loop is represented as a do-while (with a proper if-guard
1201 before the loop if needed), where the loop header contains all the
1202 executable statements, and the latch is empty. */
1203 if (!empty_block_p (loop
->latch
)
1204 || !gimple_seq_empty_p (phi_nodes (loop
->latch
)))
1206 if (dump_enabled_p ())
1207 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1208 "not vectorized: latch block not empty.\n");
1209 if (inner_loop_vinfo
)
1210 destroy_loop_vec_info (inner_loop_vinfo
, true);
1214 /* Make sure there exists a single-predecessor exit bb: */
1215 if (!single_pred_p (single_exit (loop
)->dest
))
1217 edge e
= single_exit (loop
);
1218 if (!(e
->flags
& EDGE_ABNORMAL
))
1220 split_loop_exit_edge (e
);
1221 if (dump_enabled_p ())
1222 dump_printf (MSG_NOTE
, "split exit edge.\n");
1226 if (dump_enabled_p ())
1227 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1228 "not vectorized: abnormal loop exit edge.\n");
1229 if (inner_loop_vinfo
)
1230 destroy_loop_vec_info (inner_loop_vinfo
, true);
1235 loop_cond
= vect_get_loop_niters (loop
, &number_of_iterations
);
1238 if (dump_enabled_p ())
1239 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1240 "not vectorized: complicated exit condition.\n");
1241 if (inner_loop_vinfo
)
1242 destroy_loop_vec_info (inner_loop_vinfo
, true);
1246 if (!number_of_iterations
)
1248 if (dump_enabled_p ())
1249 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1250 "not vectorized: number of iterations cannot be "
1252 if (inner_loop_vinfo
)
1253 destroy_loop_vec_info (inner_loop_vinfo
, true);
1257 if (chrec_contains_undetermined (number_of_iterations
))
1259 if (dump_enabled_p ())
1260 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1261 "Infinite number of iterations.\n");
1262 if (inner_loop_vinfo
)
1263 destroy_loop_vec_info (inner_loop_vinfo
, true);
1267 if (!NITERS_KNOWN_P (number_of_iterations
))
1269 if (dump_enabled_p ())
1271 dump_printf_loc (MSG_NOTE
, vect_location
,
1272 "Symbolic number of iterations is ");
1273 dump_generic_expr (MSG_NOTE
, TDF_DETAILS
, number_of_iterations
);
1274 dump_printf (MSG_NOTE
, "\n");
1277 else if (TREE_INT_CST_LOW (number_of_iterations
) == 0)
1279 if (dump_enabled_p ())
1280 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1281 "not vectorized: number of iterations = 0.\n");
1282 if (inner_loop_vinfo
)
1283 destroy_loop_vec_info (inner_loop_vinfo
, true);
1287 loop_vinfo
= new_loop_vec_info (loop
);
1288 LOOP_VINFO_NITERS (loop_vinfo
) = number_of_iterations
;
1289 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo
) = number_of_iterations
;
1291 STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond
)) = loop_exit_ctrl_vec_info_type
;
1293 /* CHECKME: May want to keep it around it in the future. */
1294 if (inner_loop_vinfo
)
1295 destroy_loop_vec_info (inner_loop_vinfo
, false);
1297 gcc_assert (!loop
->aux
);
1298 loop
->aux
= loop_vinfo
;
1303 /* Function vect_analyze_loop_operations.
1305 Scan the loop stmts and make sure they are all vectorizable. */
1308 vect_analyze_loop_operations (loop_vec_info loop_vinfo
, bool slp
)
1310 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1311 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1312 int nbbs
= loop
->num_nodes
;
1313 gimple_stmt_iterator si
;
1314 unsigned int vectorization_factor
= 0;
1317 stmt_vec_info stmt_info
;
1318 bool need_to_vectorize
= false;
1319 int min_profitable_iters
;
1320 int min_scalar_loop_bound
;
1322 bool only_slp_in_loop
= true, ok
;
1323 HOST_WIDE_INT max_niter
;
1324 HOST_WIDE_INT estimated_niter
;
1325 int min_profitable_estimate
;
1327 if (dump_enabled_p ())
1328 dump_printf_loc (MSG_NOTE
, vect_location
,
1329 "=== vect_analyze_loop_operations ===\n");
1331 gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo
));
1332 vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1335 /* If all the stmts in the loop can be SLPed, we perform only SLP, and
1336 vectorization factor of the loop is the unrolling factor required by
1337 the SLP instances. If that unrolling factor is 1, we say, that we
1338 perform pure SLP on loop - cross iteration parallelism is not
1340 for (i
= 0; i
< nbbs
; i
++)
1342 basic_block bb
= bbs
[i
];
1343 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1345 gimple stmt
= gsi_stmt (si
);
1346 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1347 gcc_assert (stmt_info
);
1348 if ((STMT_VINFO_RELEVANT_P (stmt_info
)
1349 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
1350 && !PURE_SLP_STMT (stmt_info
))
1351 /* STMT needs both SLP and loop-based vectorization. */
1352 only_slp_in_loop
= false;
1356 if (only_slp_in_loop
)
1357 vectorization_factor
= LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
);
1359 vectorization_factor
= least_common_multiple (vectorization_factor
,
1360 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
));
1362 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
1363 if (dump_enabled_p ())
1364 dump_printf_loc (MSG_NOTE
, vect_location
,
1365 "Updating vectorization factor to %d\n",
1366 vectorization_factor
);
1369 for (i
= 0; i
< nbbs
; i
++)
1371 basic_block bb
= bbs
[i
];
1373 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
1375 phi
= gsi_stmt (si
);
1378 stmt_info
= vinfo_for_stmt (phi
);
1379 if (dump_enabled_p ())
1381 dump_printf_loc (MSG_NOTE
, vect_location
, "examining phi: ");
1382 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
1383 dump_printf (MSG_NOTE
, "\n");
1386 /* Inner-loop loop-closed exit phi in outer-loop vectorization
1387 (i.e., a phi in the tail of the outer-loop). */
1388 if (! is_loop_header_bb_p (bb
))
1390 /* FORNOW: we currently don't support the case that these phis
1391 are not used in the outerloop (unless it is double reduction,
1392 i.e., this phi is vect_reduction_def), cause this case
1393 requires to actually do something here. */
1394 if ((!STMT_VINFO_RELEVANT_P (stmt_info
)
1395 || STMT_VINFO_LIVE_P (stmt_info
))
1396 && STMT_VINFO_DEF_TYPE (stmt_info
)
1397 != vect_double_reduction_def
)
1399 if (dump_enabled_p ())
1400 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1401 "Unsupported loop-closed phi in "
1406 /* If PHI is used in the outer loop, we check that its operand
1407 is defined in the inner loop. */
1408 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1413 if (gimple_phi_num_args (phi
) != 1)
1416 phi_op
= PHI_ARG_DEF (phi
, 0);
1417 if (TREE_CODE (phi_op
) != SSA_NAME
)
1420 op_def_stmt
= SSA_NAME_DEF_STMT (phi_op
);
1421 if (gimple_nop_p (op_def_stmt
)
1422 || !flow_bb_inside_loop_p (loop
, gimple_bb (op_def_stmt
))
1423 || !vinfo_for_stmt (op_def_stmt
))
1426 if (STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1427 != vect_used_in_outer
1428 && STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1429 != vect_used_in_outer_by_reduction
)
1436 gcc_assert (stmt_info
);
1438 if (STMT_VINFO_LIVE_P (stmt_info
))
1440 /* FORNOW: not yet supported. */
1441 if (dump_enabled_p ())
1442 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1443 "not vectorized: value used after loop.\n");
1447 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
1448 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_induction_def
)
1450 /* A scalar-dependence cycle that we don't support. */
1451 if (dump_enabled_p ())
1452 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1453 "not vectorized: scalar dependence cycle.\n");
1457 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1459 need_to_vectorize
= true;
1460 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
1461 ok
= vectorizable_induction (phi
, NULL
, NULL
);
1466 if (dump_enabled_p ())
1468 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1469 "not vectorized: relevant phi not "
1471 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, phi
, 0);
1472 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1478 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1480 gimple stmt
= gsi_stmt (si
);
1481 if (!gimple_clobber_p (stmt
)
1482 && !vect_analyze_stmt (stmt
, &need_to_vectorize
, NULL
))
1487 /* All operations in the loop are either irrelevant (deal with loop
1488 control, or dead), or only used outside the loop and can be moved
1489 out of the loop (e.g. invariants, inductions). The loop can be
1490 optimized away by scalar optimizations. We're better off not
1491 touching this loop. */
1492 if (!need_to_vectorize
)
1494 if (dump_enabled_p ())
1495 dump_printf_loc (MSG_NOTE
, vect_location
,
1496 "All the computation can be taken out of the loop.\n");
1497 if (dump_enabled_p ())
1498 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1499 "not vectorized: redundant loop. no profit to "
1504 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
) && dump_enabled_p ())
1505 dump_printf_loc (MSG_NOTE
, vect_location
,
1506 "vectorization_factor = %d, niters = "
1507 HOST_WIDE_INT_PRINT_DEC
"\n", vectorization_factor
,
1508 LOOP_VINFO_INT_NITERS (loop_vinfo
));
1510 if ((LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1511 && (LOOP_VINFO_INT_NITERS (loop_vinfo
) < vectorization_factor
))
1512 || ((max_niter
= max_stmt_executions_int (loop
)) != -1
1513 && (unsigned HOST_WIDE_INT
) max_niter
< vectorization_factor
))
1515 if (dump_enabled_p ())
1516 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1517 "not vectorized: iteration count too small.\n");
1518 if (dump_enabled_p ())
1519 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1520 "not vectorized: iteration count smaller than "
1521 "vectorization factor.\n");
1525 /* Analyze cost. Decide if worth while to vectorize. */
1527 /* Once VF is set, SLP costs should be updated since the number of created
1528 vector stmts depends on VF. */
1529 vect_update_slp_costs_according_to_vf (loop_vinfo
);
1531 vect_estimate_min_profitable_iters (loop_vinfo
, &min_profitable_iters
,
1532 &min_profitable_estimate
);
1533 LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo
) = min_profitable_iters
;
1535 if (min_profitable_iters
< 0)
1537 if (dump_enabled_p ())
1538 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1539 "not vectorized: vectorization not profitable.\n");
1540 if (dump_enabled_p ())
1541 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1542 "not vectorized: vector version will never be "
1547 min_scalar_loop_bound
= ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND
)
1548 * vectorization_factor
) - 1);
1551 /* Use the cost model only if it is more conservative than user specified
1554 th
= (unsigned) min_scalar_loop_bound
;
1555 if (min_profitable_iters
1556 && (!min_scalar_loop_bound
1557 || min_profitable_iters
> min_scalar_loop_bound
))
1558 th
= (unsigned) min_profitable_iters
;
1560 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1561 && LOOP_VINFO_INT_NITERS (loop_vinfo
) <= th
)
1563 if (dump_enabled_p ())
1564 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1565 "not vectorized: vectorization not profitable.\n");
1566 if (dump_enabled_p ())
1567 dump_printf_loc (MSG_NOTE
, vect_location
,
1568 "not vectorized: iteration count smaller than user "
1569 "specified loop bound parameter or minimum profitable "
1570 "iterations (whichever is more conservative).\n");
1574 if ((estimated_niter
= estimated_stmt_executions_int (loop
)) != -1
1575 && ((unsigned HOST_WIDE_INT
) estimated_niter
1576 <= MAX (th
, (unsigned)min_profitable_estimate
)))
1578 if (dump_enabled_p ())
1579 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1580 "not vectorized: estimated iteration count too "
1582 if (dump_enabled_p ())
1583 dump_printf_loc (MSG_NOTE
, vect_location
,
1584 "not vectorized: estimated iteration count smaller "
1585 "than specified loop bound parameter or minimum "
1586 "profitable iterations (whichever is more "
1587 "conservative).\n");
1591 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
)
1592 || ((int) tree_ctz (LOOP_VINFO_NITERS (loop_vinfo
))
1593 < exact_log2 (vectorization_factor
)))
1595 if (dump_enabled_p ())
1596 dump_printf_loc (MSG_NOTE
, vect_location
, "epilog loop required.\n");
1597 if (!vect_can_advance_ivs_p (loop_vinfo
))
1599 if (dump_enabled_p ())
1600 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1601 "not vectorized: can't create epilog loop 1.\n");
1604 if (!slpeel_can_duplicate_loop_p (loop
, single_exit (loop
)))
1606 if (dump_enabled_p ())
1607 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1608 "not vectorized: can't create epilog loop 2.\n");
1617 /* Function vect_analyze_loop_2.
1619 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1620 for it. The different analyses will record information in the
1621 loop_vec_info struct. */
1623 vect_analyze_loop_2 (loop_vec_info loop_vinfo
)
1625 bool ok
, slp
= false;
1626 int max_vf
= MAX_VECTORIZATION_FACTOR
;
1629 /* Find all data references in the loop (which correspond to vdefs/vuses)
1630 and analyze their evolution in the loop. Also adjust the minimal
1631 vectorization factor according to the loads and stores.
1633 FORNOW: Handle only simple, array references, which
1634 alignment can be forced, and aligned pointer-references. */
1636 ok
= vect_analyze_data_refs (loop_vinfo
, NULL
, &min_vf
);
1639 if (dump_enabled_p ())
1640 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1641 "bad data references.\n");
1645 /* Analyze the access patterns of the data-refs in the loop (consecutive,
1646 complex, etc.). FORNOW: Only handle consecutive access pattern. */
1648 ok
= vect_analyze_data_ref_accesses (loop_vinfo
, NULL
);
1651 if (dump_enabled_p ())
1652 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1653 "bad data access.\n");
1657 /* Classify all cross-iteration scalar data-flow cycles.
1658 Cross-iteration cycles caused by virtual phis are analyzed separately. */
1660 vect_analyze_scalar_cycles (loop_vinfo
);
1662 vect_pattern_recog (loop_vinfo
, NULL
);
1664 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
1666 ok
= vect_mark_stmts_to_be_vectorized (loop_vinfo
);
1669 if (dump_enabled_p ())
1670 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1671 "unexpected pattern.\n");
1675 /* Analyze data dependences between the data-refs in the loop
1676 and adjust the maximum vectorization factor according to
1678 FORNOW: fail at the first data dependence that we encounter. */
1680 ok
= vect_analyze_data_ref_dependences (loop_vinfo
, &max_vf
);
1684 if (dump_enabled_p ())
1685 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1686 "bad data dependence.\n");
1690 ok
= vect_determine_vectorization_factor (loop_vinfo
);
1693 if (dump_enabled_p ())
1694 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1695 "can't determine vectorization factor.\n");
1698 if (max_vf
< LOOP_VINFO_VECT_FACTOR (loop_vinfo
))
1700 if (dump_enabled_p ())
1701 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1702 "bad data dependence.\n");
1706 /* Analyze the alignment of the data-refs in the loop.
1707 Fail if a data reference is found that cannot be vectorized. */
1709 ok
= vect_analyze_data_refs_alignment (loop_vinfo
, NULL
);
1712 if (dump_enabled_p ())
1713 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1714 "bad data alignment.\n");
1718 /* Prune the list of ddrs to be tested at run-time by versioning for alias.
1719 It is important to call pruning after vect_analyze_data_ref_accesses,
1720 since we use grouping information gathered by interleaving analysis. */
1721 ok
= vect_prune_runtime_alias_test_list (loop_vinfo
);
1724 if (dump_enabled_p ())
1725 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1726 "too long list of versioning for alias "
1727 "run-time tests.\n");
1731 /* This pass will decide on using loop versioning and/or loop peeling in
1732 order to enhance the alignment of data references in the loop. */
1734 ok
= vect_enhance_data_refs_alignment (loop_vinfo
);
1737 if (dump_enabled_p ())
1738 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1739 "bad data alignment.\n");
1743 /* Check the SLP opportunities in the loop, analyze and build SLP trees. */
1744 ok
= vect_analyze_slp (loop_vinfo
, NULL
);
1747 /* Decide which possible SLP instances to SLP. */
1748 slp
= vect_make_slp_decision (loop_vinfo
);
1750 /* Find stmts that need to be both vectorized and SLPed. */
1751 vect_detect_hybrid_slp (loop_vinfo
);
1756 /* Scan all the operations in the loop and make sure they are
1759 ok
= vect_analyze_loop_operations (loop_vinfo
, slp
);
1762 if (dump_enabled_p ())
1763 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1764 "bad operation or unsupported loop bound.\n");
1771 /* Function vect_analyze_loop.
1773 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1774 for it. The different analyses will record information in the
1775 loop_vec_info struct. */
1777 vect_analyze_loop (struct loop
*loop
)
1779 loop_vec_info loop_vinfo
;
1780 unsigned int vector_sizes
;
1782 /* Autodetect first vector size we try. */
1783 current_vector_size
= 0;
1784 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
1786 if (dump_enabled_p ())
1787 dump_printf_loc (MSG_NOTE
, vect_location
,
1788 "===== analyze_loop_nest =====\n");
1790 if (loop_outer (loop
)
1791 && loop_vec_info_for_loop (loop_outer (loop
))
1792 && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop
))))
1794 if (dump_enabled_p ())
1795 dump_printf_loc (MSG_NOTE
, vect_location
,
1796 "outer-loop already vectorized.\n");
1802 /* Check the CFG characteristics of the loop (nesting, entry/exit). */
1803 loop_vinfo
= vect_analyze_loop_form (loop
);
1806 if (dump_enabled_p ())
1807 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1808 "bad loop form.\n");
1812 if (vect_analyze_loop_2 (loop_vinfo
))
1814 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
) = 1;
1819 destroy_loop_vec_info (loop_vinfo
, true);
1821 vector_sizes
&= ~current_vector_size
;
1822 if (vector_sizes
== 0
1823 || current_vector_size
== 0)
1826 /* Try the next biggest vector size. */
1827 current_vector_size
= 1 << floor_log2 (vector_sizes
);
1828 if (dump_enabled_p ())
1829 dump_printf_loc (MSG_NOTE
, vect_location
,
1830 "***** Re-trying analysis with "
1831 "vector size %d\n", current_vector_size
);
1836 /* Function reduction_code_for_scalar_code
1839 CODE - tree_code of a reduction operations.
1842 REDUC_CODE - the corresponding tree-code to be used to reduce the
1843 vector of partial results into a single scalar result (which
1844 will also reside in a vector) or ERROR_MARK if the operation is
1845 a supported reduction operation, but does not have such tree-code.
1847 Return FALSE if CODE currently cannot be vectorized as reduction. */
1850 reduction_code_for_scalar_code (enum tree_code code
,
1851 enum tree_code
*reduc_code
)
1856 *reduc_code
= REDUC_MAX_EXPR
;
1860 *reduc_code
= REDUC_MIN_EXPR
;
1864 *reduc_code
= REDUC_PLUS_EXPR
;
1872 *reduc_code
= ERROR_MARK
;
1881 /* Error reporting helper for vect_is_simple_reduction below. GIMPLE statement
1882 STMT is printed with a message MSG. */
1885 report_vect_op (int msg_type
, gimple stmt
, const char *msg
)
1887 dump_printf_loc (msg_type
, vect_location
, "%s", msg
);
1888 dump_gimple_stmt (msg_type
, TDF_SLIM
, stmt
, 0);
1889 dump_printf (msg_type
, "\n");
1893 /* Detect SLP reduction of the form:
1903 PHI is the reduction phi node (#a1 = phi <a5, a0> above)
1904 FIRST_STMT is the first reduction stmt in the chain
1905 (a2 = operation (a1)).
1907 Return TRUE if a reduction chain was detected. */
1910 vect_is_slp_reduction (loop_vec_info loop_info
, gimple phi
, gimple first_stmt
)
1912 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
1913 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
1914 enum tree_code code
;
1915 gimple current_stmt
= NULL
, loop_use_stmt
= NULL
, first
, next_stmt
;
1916 stmt_vec_info use_stmt_info
, current_stmt_info
;
1918 imm_use_iterator imm_iter
;
1919 use_operand_p use_p
;
1920 int nloop_uses
, size
= 0, n_out_of_loop_uses
;
1923 if (loop
!= vect_loop
)
1926 lhs
= PHI_RESULT (phi
);
1927 code
= gimple_assign_rhs_code (first_stmt
);
1931 n_out_of_loop_uses
= 0;
1932 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
1934 gimple use_stmt
= USE_STMT (use_p
);
1935 if (is_gimple_debug (use_stmt
))
1938 use_stmt
= USE_STMT (use_p
);
1940 /* Check if we got back to the reduction phi. */
1941 if (use_stmt
== phi
)
1943 loop_use_stmt
= use_stmt
;
1948 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
1950 if (vinfo_for_stmt (use_stmt
)
1951 && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (use_stmt
)))
1953 loop_use_stmt
= use_stmt
;
1958 n_out_of_loop_uses
++;
1960 /* There are can be either a single use in the loop or two uses in
1962 if (nloop_uses
> 1 || (n_out_of_loop_uses
&& nloop_uses
))
1969 /* We reached a statement with no loop uses. */
1970 if (nloop_uses
== 0)
1973 /* This is a loop exit phi, and we haven't reached the reduction phi. */
1974 if (gimple_code (loop_use_stmt
) == GIMPLE_PHI
)
1977 if (!is_gimple_assign (loop_use_stmt
)
1978 || code
!= gimple_assign_rhs_code (loop_use_stmt
)
1979 || !flow_bb_inside_loop_p (loop
, gimple_bb (loop_use_stmt
)))
1982 /* Insert USE_STMT into reduction chain. */
1983 use_stmt_info
= vinfo_for_stmt (loop_use_stmt
);
1986 current_stmt_info
= vinfo_for_stmt (current_stmt
);
1987 GROUP_NEXT_ELEMENT (current_stmt_info
) = loop_use_stmt
;
1988 GROUP_FIRST_ELEMENT (use_stmt_info
)
1989 = GROUP_FIRST_ELEMENT (current_stmt_info
);
1992 GROUP_FIRST_ELEMENT (use_stmt_info
) = loop_use_stmt
;
1994 lhs
= gimple_assign_lhs (loop_use_stmt
);
1995 current_stmt
= loop_use_stmt
;
1999 if (!found
|| loop_use_stmt
!= phi
|| size
< 2)
2002 /* Swap the operands, if needed, to make the reduction operand be the second
2004 lhs
= PHI_RESULT (phi
);
2005 next_stmt
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
2008 if (gimple_assign_rhs2 (next_stmt
) == lhs
)
2010 tree op
= gimple_assign_rhs1 (next_stmt
);
2011 gimple def_stmt
= NULL
;
2013 if (TREE_CODE (op
) == SSA_NAME
)
2014 def_stmt
= SSA_NAME_DEF_STMT (op
);
2016 /* Check that the other def is either defined in the loop
2017 ("vect_internal_def"), or it's an induction (defined by a
2018 loop-header phi-node). */
2020 && gimple_bb (def_stmt
)
2021 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2022 && (is_gimple_assign (def_stmt
)
2023 || is_gimple_call (def_stmt
)
2024 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2025 == vect_induction_def
2026 || (gimple_code (def_stmt
) == GIMPLE_PHI
2027 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2028 == vect_internal_def
2029 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
2031 lhs
= gimple_assign_lhs (next_stmt
);
2032 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
2040 tree op
= gimple_assign_rhs2 (next_stmt
);
2041 gimple def_stmt
= NULL
;
2043 if (TREE_CODE (op
) == SSA_NAME
)
2044 def_stmt
= SSA_NAME_DEF_STMT (op
);
2046 /* Check that the other def is either defined in the loop
2047 ("vect_internal_def"), or it's an induction (defined by a
2048 loop-header phi-node). */
2050 && gimple_bb (def_stmt
)
2051 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2052 && (is_gimple_assign (def_stmt
)
2053 || is_gimple_call (def_stmt
)
2054 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2055 == vect_induction_def
2056 || (gimple_code (def_stmt
) == GIMPLE_PHI
2057 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2058 == vect_internal_def
2059 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
2061 if (dump_enabled_p ())
2063 dump_printf_loc (MSG_NOTE
, vect_location
, "swapping oprnds: ");
2064 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, next_stmt
, 0);
2065 dump_printf (MSG_NOTE
, "\n");
2068 swap_ssa_operands (next_stmt
,
2069 gimple_assign_rhs1_ptr (next_stmt
),
2070 gimple_assign_rhs2_ptr (next_stmt
));
2071 update_stmt (next_stmt
);
2073 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (next_stmt
)))
2074 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
2080 lhs
= gimple_assign_lhs (next_stmt
);
2081 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
2084 /* Save the chain for further analysis in SLP detection. */
2085 first
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
2086 LOOP_VINFO_REDUCTION_CHAINS (loop_info
).safe_push (first
);
2087 GROUP_SIZE (vinfo_for_stmt (first
)) = size
;
2093 /* Function vect_is_simple_reduction_1
2095 (1) Detect a cross-iteration def-use cycle that represents a simple
2096 reduction computation. We look for the following pattern:
2101 a2 = operation (a3, a1)
2108 a2 = operation (a3, a1)
2111 1. operation is commutative and associative and it is safe to
2112 change the order of the computation (if CHECK_REDUCTION is true)
2113 2. no uses for a2 in the loop (a2 is used out of the loop)
2114 3. no uses of a1 in the loop besides the reduction operation
2115 4. no uses of a1 outside the loop.
2117 Conditions 1,4 are tested here.
2118 Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
2120 (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
2121 nested cycles, if CHECK_REDUCTION is false.
2123 (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
2127 inner loop (def of a3)
2130 If MODIFY is true it tries also to rework the code in-place to enable
2131 detection of more reduction patterns. For the time being we rewrite
2132 "res -= RHS" into "rhs += -RHS" when it seems worthwhile.
2136 vect_is_simple_reduction_1 (loop_vec_info loop_info
, gimple phi
,
2137 bool check_reduction
, bool *double_reduc
,
2140 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
2141 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
2142 edge latch_e
= loop_latch_edge (loop
);
2143 tree loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
2144 gimple def_stmt
, def1
= NULL
, def2
= NULL
;
2145 enum tree_code orig_code
, code
;
2146 tree op1
, op2
, op3
= NULL_TREE
, op4
= NULL_TREE
;
2150 imm_use_iterator imm_iter
;
2151 use_operand_p use_p
;
2154 *double_reduc
= false;
2156 /* If CHECK_REDUCTION is true, we assume inner-most loop vectorization,
2157 otherwise, we assume outer loop vectorization. */
2158 gcc_assert ((check_reduction
&& loop
== vect_loop
)
2159 || (!check_reduction
&& flow_loop_nested_p (vect_loop
, loop
)));
2161 name
= PHI_RESULT (phi
);
2163 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2165 gimple use_stmt
= USE_STMT (use_p
);
2166 if (is_gimple_debug (use_stmt
))
2169 if (!flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2171 if (dump_enabled_p ())
2172 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2173 "intermediate value used outside loop.\n");
2178 if (vinfo_for_stmt (use_stmt
)
2179 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt
)))
2183 if (dump_enabled_p ())
2184 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2185 "reduction used in loop.\n");
2190 if (TREE_CODE (loop_arg
) != SSA_NAME
)
2192 if (dump_enabled_p ())
2194 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2195 "reduction: not ssa_name: ");
2196 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, loop_arg
);
2197 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
2202 def_stmt
= SSA_NAME_DEF_STMT (loop_arg
);
2205 if (dump_enabled_p ())
2206 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2207 "reduction: no def_stmt.\n");
2211 if (!is_gimple_assign (def_stmt
) && gimple_code (def_stmt
) != GIMPLE_PHI
)
2213 if (dump_enabled_p ())
2215 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, def_stmt
, 0);
2216 dump_printf (MSG_NOTE
, "\n");
2221 if (is_gimple_assign (def_stmt
))
2223 name
= gimple_assign_lhs (def_stmt
);
2228 name
= PHI_RESULT (def_stmt
);
2233 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2235 gimple use_stmt
= USE_STMT (use_p
);
2236 if (is_gimple_debug (use_stmt
))
2238 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
))
2239 && vinfo_for_stmt (use_stmt
)
2240 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt
)))
2244 if (dump_enabled_p ())
2245 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2246 "reduction used in loop.\n");
2251 /* If DEF_STMT is a phi node itself, we expect it to have a single argument
2252 defined in the inner loop. */
2255 op1
= PHI_ARG_DEF (def_stmt
, 0);
2257 if (gimple_phi_num_args (def_stmt
) != 1
2258 || TREE_CODE (op1
) != SSA_NAME
)
2260 if (dump_enabled_p ())
2261 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2262 "unsupported phi node definition.\n");
2267 def1
= SSA_NAME_DEF_STMT (op1
);
2268 if (flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2270 && flow_bb_inside_loop_p (loop
->inner
, gimple_bb (def1
))
2271 && is_gimple_assign (def1
))
2273 if (dump_enabled_p ())
2274 report_vect_op (MSG_NOTE
, def_stmt
,
2275 "detected double reduction: ");
2277 *double_reduc
= true;
2284 code
= orig_code
= gimple_assign_rhs_code (def_stmt
);
2286 /* We can handle "res -= x[i]", which is non-associative by
2287 simply rewriting this into "res += -x[i]". Avoid changing
2288 gimple instruction for the first simple tests and only do this
2289 if we're allowed to change code at all. */
2290 if (code
== MINUS_EXPR
2292 && (op1
= gimple_assign_rhs1 (def_stmt
))
2293 && TREE_CODE (op1
) == SSA_NAME
2294 && SSA_NAME_DEF_STMT (op1
) == phi
)
2298 && (!commutative_tree_code (code
) || !associative_tree_code (code
)))
2300 if (dump_enabled_p ())
2301 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2302 "reduction: not commutative/associative: ");
2306 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
2308 if (code
!= COND_EXPR
)
2310 if (dump_enabled_p ())
2311 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2312 "reduction: not binary operation: ");
2317 op3
= gimple_assign_rhs1 (def_stmt
);
2318 if (COMPARISON_CLASS_P (op3
))
2320 op4
= TREE_OPERAND (op3
, 1);
2321 op3
= TREE_OPERAND (op3
, 0);
2324 op1
= gimple_assign_rhs2 (def_stmt
);
2325 op2
= gimple_assign_rhs3 (def_stmt
);
2327 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2329 if (dump_enabled_p ())
2330 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2331 "reduction: uses not ssa_names: ");
2338 op1
= gimple_assign_rhs1 (def_stmt
);
2339 op2
= gimple_assign_rhs2 (def_stmt
);
2341 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2343 if (dump_enabled_p ())
2344 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2345 "reduction: uses not ssa_names: ");
2351 type
= TREE_TYPE (gimple_assign_lhs (def_stmt
));
2352 if ((TREE_CODE (op1
) == SSA_NAME
2353 && !types_compatible_p (type
,TREE_TYPE (op1
)))
2354 || (TREE_CODE (op2
) == SSA_NAME
2355 && !types_compatible_p (type
, TREE_TYPE (op2
)))
2356 || (op3
&& TREE_CODE (op3
) == SSA_NAME
2357 && !types_compatible_p (type
, TREE_TYPE (op3
)))
2358 || (op4
&& TREE_CODE (op4
) == SSA_NAME
2359 && !types_compatible_p (type
, TREE_TYPE (op4
))))
2361 if (dump_enabled_p ())
2363 dump_printf_loc (MSG_NOTE
, vect_location
,
2364 "reduction: multiple types: operation type: ");
2365 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, type
);
2366 dump_printf (MSG_NOTE
, ", operands types: ");
2367 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2369 dump_printf (MSG_NOTE
, ",");
2370 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2374 dump_printf (MSG_NOTE
, ",");
2375 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2381 dump_printf (MSG_NOTE
, ",");
2382 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2385 dump_printf (MSG_NOTE
, "\n");
2391 /* Check that it's ok to change the order of the computation.
2392 Generally, when vectorizing a reduction we change the order of the
2393 computation. This may change the behavior of the program in some
2394 cases, so we need to check that this is ok. One exception is when
2395 vectorizing an outer-loop: the inner-loop is executed sequentially,
2396 and therefore vectorizing reductions in the inner-loop during
2397 outer-loop vectorization is safe. */
2399 /* CHECKME: check for !flag_finite_math_only too? */
2400 if (SCALAR_FLOAT_TYPE_P (type
) && !flag_associative_math
2403 /* Changing the order of operations changes the semantics. */
2404 if (dump_enabled_p ())
2405 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2406 "reduction: unsafe fp math optimization: ");
2409 else if (INTEGRAL_TYPE_P (type
) && TYPE_OVERFLOW_TRAPS (type
)
2412 /* Changing the order of operations changes the semantics. */
2413 if (dump_enabled_p ())
2414 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2415 "reduction: unsafe int math optimization: ");
2418 else if (SAT_FIXED_POINT_TYPE_P (type
) && check_reduction
)
2420 /* Changing the order of operations changes the semantics. */
2421 if (dump_enabled_p ())
2422 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2423 "reduction: unsafe fixed-point math optimization: ");
2427 /* If we detected "res -= x[i]" earlier, rewrite it into
2428 "res += -x[i]" now. If this turns out to be useless reassoc
2429 will clean it up again. */
2430 if (orig_code
== MINUS_EXPR
)
2432 tree rhs
= gimple_assign_rhs2 (def_stmt
);
2433 tree negrhs
= make_ssa_name (TREE_TYPE (rhs
), NULL
);
2434 gimple negate_stmt
= gimple_build_assign_with_ops (NEGATE_EXPR
, negrhs
,
2436 gimple_stmt_iterator gsi
= gsi_for_stmt (def_stmt
);
2437 set_vinfo_for_stmt (negate_stmt
, new_stmt_vec_info (negate_stmt
,
2439 gsi_insert_before (&gsi
, negate_stmt
, GSI_NEW_STMT
);
2440 gimple_assign_set_rhs2 (def_stmt
, negrhs
);
2441 gimple_assign_set_rhs_code (def_stmt
, PLUS_EXPR
);
2442 update_stmt (def_stmt
);
2445 /* Reduction is safe. We're dealing with one of the following:
2446 1) integer arithmetic and no trapv
2447 2) floating point arithmetic, and special flags permit this optimization
2448 3) nested cycle (i.e., outer loop vectorization). */
2449 if (TREE_CODE (op1
) == SSA_NAME
)
2450 def1
= SSA_NAME_DEF_STMT (op1
);
2452 if (TREE_CODE (op2
) == SSA_NAME
)
2453 def2
= SSA_NAME_DEF_STMT (op2
);
2455 if (code
!= COND_EXPR
2456 && ((!def1
|| gimple_nop_p (def1
)) && (!def2
|| gimple_nop_p (def2
))))
2458 if (dump_enabled_p ())
2459 report_vect_op (MSG_NOTE
, def_stmt
, "reduction: no defs for operands: ");
2463 /* Check that one def is the reduction def, defined by PHI,
2464 the other def is either defined in the loop ("vect_internal_def"),
2465 or it's an induction (defined by a loop-header phi-node). */
2467 if (def2
&& def2
== phi
2468 && (code
== COND_EXPR
2469 || !def1
|| gimple_nop_p (def1
)
2470 || !flow_bb_inside_loop_p (loop
, gimple_bb (def1
))
2471 || (def1
&& flow_bb_inside_loop_p (loop
, gimple_bb (def1
))
2472 && (is_gimple_assign (def1
)
2473 || is_gimple_call (def1
)
2474 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
2475 == vect_induction_def
2476 || (gimple_code (def1
) == GIMPLE_PHI
2477 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
2478 == vect_internal_def
2479 && !is_loop_header_bb_p (gimple_bb (def1
)))))))
2481 if (dump_enabled_p ())
2482 report_vect_op (MSG_NOTE
, def_stmt
, "detected reduction: ");
2486 if (def1
&& def1
== phi
2487 && (code
== COND_EXPR
2488 || !def2
|| gimple_nop_p (def2
)
2489 || !flow_bb_inside_loop_p (loop
, gimple_bb (def2
))
2490 || (def2
&& flow_bb_inside_loop_p (loop
, gimple_bb (def2
))
2491 && (is_gimple_assign (def2
)
2492 || is_gimple_call (def2
)
2493 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
2494 == vect_induction_def
2495 || (gimple_code (def2
) == GIMPLE_PHI
2496 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
2497 == vect_internal_def
2498 && !is_loop_header_bb_p (gimple_bb (def2
)))))))
2500 if (check_reduction
)
2502 /* Swap operands (just for simplicity - so that the rest of the code
2503 can assume that the reduction variable is always the last (second)
2505 if (dump_enabled_p ())
2506 report_vect_op (MSG_NOTE
, def_stmt
,
2507 "detected reduction: need to swap operands: ");
2509 swap_ssa_operands (def_stmt
, gimple_assign_rhs1_ptr (def_stmt
),
2510 gimple_assign_rhs2_ptr (def_stmt
));
2512 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (def_stmt
)))
2513 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
2517 if (dump_enabled_p ())
2518 report_vect_op (MSG_NOTE
, def_stmt
, "detected reduction: ");
2524 /* Try to find SLP reduction chain. */
2525 if (check_reduction
&& vect_is_slp_reduction (loop_info
, phi
, def_stmt
))
2527 if (dump_enabled_p ())
2528 report_vect_op (MSG_NOTE
, def_stmt
,
2529 "reduction: detected reduction chain: ");
2534 if (dump_enabled_p ())
2535 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2536 "reduction: unknown pattern: ");
2541 /* Wrapper around vect_is_simple_reduction_1, that won't modify code
2542 in-place. Arguments as there. */
2545 vect_is_simple_reduction (loop_vec_info loop_info
, gimple phi
,
2546 bool check_reduction
, bool *double_reduc
)
2548 return vect_is_simple_reduction_1 (loop_info
, phi
, check_reduction
,
2549 double_reduc
, false);
2552 /* Wrapper around vect_is_simple_reduction_1, which will modify code
2553 in-place if it enables detection of more reductions. Arguments
2557 vect_force_simple_reduction (loop_vec_info loop_info
, gimple phi
,
2558 bool check_reduction
, bool *double_reduc
)
2560 return vect_is_simple_reduction_1 (loop_info
, phi
, check_reduction
,
2561 double_reduc
, true);
2564 /* Calculate the cost of one scalar iteration of the loop. */
2566 vect_get_single_scalar_iteration_cost (loop_vec_info loop_vinfo
)
2568 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2569 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
2570 int nbbs
= loop
->num_nodes
, factor
, scalar_single_iter_cost
= 0;
2571 int innerloop_iters
, i
, stmt_cost
;
2573 /* Count statements in scalar loop. Using this as scalar cost for a single
2576 TODO: Add outer loop support.
2578 TODO: Consider assigning different costs to different scalar
2582 innerloop_iters
= 1;
2584 innerloop_iters
= 50; /* FIXME */
2586 for (i
= 0; i
< nbbs
; i
++)
2588 gimple_stmt_iterator si
;
2589 basic_block bb
= bbs
[i
];
2591 if (bb
->loop_father
== loop
->inner
)
2592 factor
= innerloop_iters
;
2596 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
2598 gimple stmt
= gsi_stmt (si
);
2599 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2601 if (!is_gimple_assign (stmt
) && !is_gimple_call (stmt
))
2604 /* Skip stmts that are not vectorized inside the loop. */
2606 && !STMT_VINFO_RELEVANT_P (stmt_info
)
2607 && (!STMT_VINFO_LIVE_P (stmt_info
)
2608 || !VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
2609 && !STMT_VINFO_IN_PATTERN_P (stmt_info
))
2612 if (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
)))
2614 if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))))
2615 stmt_cost
= vect_get_stmt_cost (scalar_load
);
2617 stmt_cost
= vect_get_stmt_cost (scalar_store
);
2620 stmt_cost
= vect_get_stmt_cost (scalar_stmt
);
2622 scalar_single_iter_cost
+= stmt_cost
* factor
;
2625 return scalar_single_iter_cost
;
2628 /* Calculate cost of peeling the loop PEEL_ITERS_PROLOGUE times. */
2630 vect_get_known_peeling_cost (loop_vec_info loop_vinfo
, int peel_iters_prologue
,
2631 int *peel_iters_epilogue
,
2632 int scalar_single_iter_cost
,
2633 stmt_vector_for_cost
*prologue_cost_vec
,
2634 stmt_vector_for_cost
*epilogue_cost_vec
)
2637 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2639 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
2641 *peel_iters_epilogue
= vf
/2;
2642 if (dump_enabled_p ())
2643 dump_printf_loc (MSG_NOTE
, vect_location
,
2644 "cost model: epilogue peel iters set to vf/2 "
2645 "because loop iterations are unknown .\n");
2647 /* If peeled iterations are known but number of scalar loop
2648 iterations are unknown, count a taken branch per peeled loop. */
2649 retval
= record_stmt_cost (prologue_cost_vec
, 2, cond_branch_taken
,
2650 NULL
, 0, vect_prologue
);
2654 int niters
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
2655 peel_iters_prologue
= niters
< peel_iters_prologue
?
2656 niters
: peel_iters_prologue
;
2657 *peel_iters_epilogue
= (niters
- peel_iters_prologue
) % vf
;
2658 /* If we need to peel for gaps, but no peeling is required, we have to
2659 peel VF iterations. */
2660 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) && !*peel_iters_epilogue
)
2661 *peel_iters_epilogue
= vf
;
2664 if (peel_iters_prologue
)
2665 retval
+= record_stmt_cost (prologue_cost_vec
,
2666 peel_iters_prologue
* scalar_single_iter_cost
,
2667 scalar_stmt
, NULL
, 0, vect_prologue
);
2668 if (*peel_iters_epilogue
)
2669 retval
+= record_stmt_cost (epilogue_cost_vec
,
2670 *peel_iters_epilogue
* scalar_single_iter_cost
,
2671 scalar_stmt
, NULL
, 0, vect_epilogue
);
2675 /* Function vect_estimate_min_profitable_iters
2677 Return the number of iterations required for the vector version of the
2678 loop to be profitable relative to the cost of the scalar version of the
2682 vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo
,
2683 int *ret_min_profitable_niters
,
2684 int *ret_min_profitable_estimate
)
2686 int min_profitable_iters
;
2687 int min_profitable_estimate
;
2688 int peel_iters_prologue
;
2689 int peel_iters_epilogue
;
2690 unsigned vec_inside_cost
= 0;
2691 int vec_outside_cost
= 0;
2692 unsigned vec_prologue_cost
= 0;
2693 unsigned vec_epilogue_cost
= 0;
2694 int scalar_single_iter_cost
= 0;
2695 int scalar_outside_cost
= 0;
2696 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2697 int npeel
= LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
);
2698 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2700 /* Cost model disabled. */
2701 if (unlimited_cost_model ())
2703 dump_printf_loc (MSG_NOTE
, vect_location
, "cost model disabled.\n");
2704 *ret_min_profitable_niters
= 0;
2705 *ret_min_profitable_estimate
= 0;
2709 /* Requires loop versioning tests to handle misalignment. */
2710 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
))
2712 /* FIXME: Make cost depend on complexity of individual check. */
2713 unsigned len
= LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).length ();
2714 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
2716 dump_printf (MSG_NOTE
,
2717 "cost model: Adding cost of checks for loop "
2718 "versioning to treat misalignment.\n");
2721 /* Requires loop versioning with alias checks. */
2722 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2724 /* FIXME: Make cost depend on complexity of individual check. */
2725 unsigned len
= LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
).length ();
2726 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
2728 dump_printf (MSG_NOTE
,
2729 "cost model: Adding cost of checks for loop "
2730 "versioning aliasing.\n");
2733 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2734 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2735 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_taken
, NULL
, 0,
2738 /* Count statements in scalar loop. Using this as scalar cost for a single
2741 TODO: Add outer loop support.
2743 TODO: Consider assigning different costs to different scalar
2746 scalar_single_iter_cost
= vect_get_single_scalar_iteration_cost (loop_vinfo
);
2748 /* Add additional cost for the peeled instructions in prologue and epilogue
2751 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
2752 at compile-time - we assume it's vf/2 (the worst would be vf-1).
2754 TODO: Build an expression that represents peel_iters for prologue and
2755 epilogue to be used in a run-time test. */
2759 peel_iters_prologue
= vf
/2;
2760 dump_printf (MSG_NOTE
, "cost model: "
2761 "prologue peel iters set to vf/2.\n");
2763 /* If peeling for alignment is unknown, loop bound of main loop becomes
2765 peel_iters_epilogue
= vf
/2;
2766 dump_printf (MSG_NOTE
, "cost model: "
2767 "epilogue peel iters set to vf/2 because "
2768 "peeling for alignment is unknown.\n");
2770 /* If peeled iterations are unknown, count a taken branch and a not taken
2771 branch per peeled loop. Even if scalar loop iterations are known,
2772 vector iterations are not known since peeled prologue iterations are
2773 not known. Hence guards remain the same. */
2774 (void) add_stmt_cost (target_cost_data
, 2, cond_branch_taken
,
2775 NULL
, 0, vect_prologue
);
2776 (void) add_stmt_cost (target_cost_data
, 2, cond_branch_not_taken
,
2777 NULL
, 0, vect_prologue
);
2778 /* FORNOW: Don't attempt to pass individual scalar instructions to
2779 the model; just assume linear cost for scalar iterations. */
2780 (void) add_stmt_cost (target_cost_data
,
2781 peel_iters_prologue
* scalar_single_iter_cost
,
2782 scalar_stmt
, NULL
, 0, vect_prologue
);
2783 (void) add_stmt_cost (target_cost_data
,
2784 peel_iters_epilogue
* scalar_single_iter_cost
,
2785 scalar_stmt
, NULL
, 0, vect_epilogue
);
2789 stmt_vector_for_cost prologue_cost_vec
, epilogue_cost_vec
;
2790 stmt_info_for_cost
*si
;
2792 void *data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2794 prologue_cost_vec
.create (2);
2795 epilogue_cost_vec
.create (2);
2796 peel_iters_prologue
= npeel
;
2798 (void) vect_get_known_peeling_cost (loop_vinfo
, peel_iters_prologue
,
2799 &peel_iters_epilogue
,
2800 scalar_single_iter_cost
,
2802 &epilogue_cost_vec
);
2804 FOR_EACH_VEC_ELT (prologue_cost_vec
, j
, si
)
2806 struct _stmt_vec_info
*stmt_info
2807 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
2808 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
2809 si
->misalign
, vect_prologue
);
2812 FOR_EACH_VEC_ELT (epilogue_cost_vec
, j
, si
)
2814 struct _stmt_vec_info
*stmt_info
2815 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
2816 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
2817 si
->misalign
, vect_epilogue
);
2820 prologue_cost_vec
.release ();
2821 epilogue_cost_vec
.release ();
2824 /* FORNOW: The scalar outside cost is incremented in one of the
2827 1. The vectorizer checks for alignment and aliasing and generates
2828 a condition that allows dynamic vectorization. A cost model
2829 check is ANDED with the versioning condition. Hence scalar code
2830 path now has the added cost of the versioning check.
2832 if (cost > th & versioning_check)
2835 Hence run-time scalar is incremented by not-taken branch cost.
2837 2. The vectorizer then checks if a prologue is required. If the
2838 cost model check was not done before during versioning, it has to
2839 be done before the prologue check.
2842 prologue = scalar_iters
2847 if (prologue == num_iters)
2850 Hence the run-time scalar cost is incremented by a taken branch,
2851 plus a not-taken branch, plus a taken branch cost.
2853 3. The vectorizer then checks if an epilogue is required. If the
2854 cost model check was not done before during prologue check, it
2855 has to be done with the epilogue check.
2861 if (prologue == num_iters)
2864 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
2867 Hence the run-time scalar cost should be incremented by 2 taken
2870 TODO: The back end may reorder the BBS's differently and reverse
2871 conditions/branch directions. Change the estimates below to
2872 something more reasonable. */
2874 /* If the number of iterations is known and we do not do versioning, we can
2875 decide whether to vectorize at compile time. Hence the scalar version
2876 do not carry cost model guard costs. */
2877 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
2878 || LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2879 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2881 /* Cost model check occurs at versioning. */
2882 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2883 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2884 scalar_outside_cost
+= vect_get_stmt_cost (cond_branch_not_taken
);
2887 /* Cost model check occurs at prologue generation. */
2888 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
) < 0)
2889 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
)
2890 + vect_get_stmt_cost (cond_branch_not_taken
);
2891 /* Cost model check occurs at epilogue generation. */
2893 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
);
2897 /* Complete the target-specific cost calculations. */
2898 finish_cost (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
), &vec_prologue_cost
,
2899 &vec_inside_cost
, &vec_epilogue_cost
);
2901 vec_outside_cost
= (int)(vec_prologue_cost
+ vec_epilogue_cost
);
2903 /* Calculate number of iterations required to make the vector version
2904 profitable, relative to the loop bodies only. The following condition
2906 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
2908 SIC = scalar iteration cost, VIC = vector iteration cost,
2909 VOC = vector outside cost, VF = vectorization factor,
2910 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
2911 SOC = scalar outside cost for run time cost model check. */
2913 if ((scalar_single_iter_cost
* vf
) > (int) vec_inside_cost
)
2915 if (vec_outside_cost
<= 0)
2916 min_profitable_iters
= 1;
2919 min_profitable_iters
= ((vec_outside_cost
- scalar_outside_cost
) * vf
2920 - vec_inside_cost
* peel_iters_prologue
2921 - vec_inside_cost
* peel_iters_epilogue
)
2922 / ((scalar_single_iter_cost
* vf
)
2925 if ((scalar_single_iter_cost
* vf
* min_profitable_iters
)
2926 <= (((int) vec_inside_cost
* min_profitable_iters
)
2927 + (((int) vec_outside_cost
- scalar_outside_cost
) * vf
)))
2928 min_profitable_iters
++;
2931 /* vector version will never be profitable. */
2934 if (dump_enabled_p ())
2935 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2936 "cost model: the vector iteration cost = %d "
2937 "divided by the scalar iteration cost = %d "
2938 "is greater or equal to the vectorization factor = %d"
2940 vec_inside_cost
, scalar_single_iter_cost
, vf
);
2941 *ret_min_profitable_niters
= -1;
2942 *ret_min_profitable_estimate
= -1;
2946 if (dump_enabled_p ())
2948 dump_printf_loc (MSG_NOTE
, vect_location
, "Cost model analysis: \n");
2949 dump_printf (MSG_NOTE
, " Vector inside of loop cost: %d\n",
2951 dump_printf (MSG_NOTE
, " Vector prologue cost: %d\n",
2953 dump_printf (MSG_NOTE
, " Vector epilogue cost: %d\n",
2955 dump_printf (MSG_NOTE
, " Scalar iteration cost: %d\n",
2956 scalar_single_iter_cost
);
2957 dump_printf (MSG_NOTE
, " Scalar outside cost: %d\n",
2958 scalar_outside_cost
);
2959 dump_printf (MSG_NOTE
, " Vector outside cost: %d\n",
2961 dump_printf (MSG_NOTE
, " prologue iterations: %d\n",
2962 peel_iters_prologue
);
2963 dump_printf (MSG_NOTE
, " epilogue iterations: %d\n",
2964 peel_iters_epilogue
);
2965 dump_printf (MSG_NOTE
,
2966 " Calculated minimum iters for profitability: %d\n",
2967 min_profitable_iters
);
2968 dump_printf (MSG_NOTE
, "\n");
2971 min_profitable_iters
=
2972 min_profitable_iters
< vf
? vf
: min_profitable_iters
;
2974 /* Because the condition we create is:
2975 if (niters <= min_profitable_iters)
2976 then skip the vectorized loop. */
2977 min_profitable_iters
--;
2979 if (dump_enabled_p ())
2980 dump_printf_loc (MSG_NOTE
, vect_location
,
2981 " Runtime profitability threshold = %d\n",
2982 min_profitable_iters
);
2984 *ret_min_profitable_niters
= min_profitable_iters
;
2986 /* Calculate number of iterations required to make the vector version
2987 profitable, relative to the loop bodies only.
2989 Non-vectorized variant is SIC * niters and it must win over vector
2990 variant on the expected loop trip count. The following condition must hold true:
2991 SIC * niters > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC + SOC */
2993 if (vec_outside_cost
<= 0)
2994 min_profitable_estimate
= 1;
2997 min_profitable_estimate
= ((vec_outside_cost
+ scalar_outside_cost
) * vf
2998 - vec_inside_cost
* peel_iters_prologue
2999 - vec_inside_cost
* peel_iters_epilogue
)
3000 / ((scalar_single_iter_cost
* vf
)
3003 min_profitable_estimate
--;
3004 min_profitable_estimate
= MAX (min_profitable_estimate
, min_profitable_iters
);
3005 if (dump_enabled_p ())
3006 dump_printf_loc (MSG_NOTE
, vect_location
,
3007 " Static estimate profitability threshold = %d\n",
3008 min_profitable_iters
);
3010 *ret_min_profitable_estimate
= min_profitable_estimate
;
3014 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
3015 functions. Design better to avoid maintenance issues. */
3017 /* Function vect_model_reduction_cost.
3019 Models cost for a reduction operation, including the vector ops
3020 generated within the strip-mine loop, the initial definition before
3021 the loop, and the epilogue code that must be generated. */
3024 vect_model_reduction_cost (stmt_vec_info stmt_info
, enum tree_code reduc_code
,
3027 int prologue_cost
= 0, epilogue_cost
= 0;
3028 enum tree_code code
;
3031 gimple stmt
, orig_stmt
;
3033 enum machine_mode mode
;
3034 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3035 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3036 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3038 /* Cost of reduction op inside loop. */
3039 unsigned inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
3040 stmt_info
, 0, vect_body
);
3041 stmt
= STMT_VINFO_STMT (stmt_info
);
3043 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3045 case GIMPLE_SINGLE_RHS
:
3046 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
)) == ternary_op
);
3047 reduction_op
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
3049 case GIMPLE_UNARY_RHS
:
3050 reduction_op
= gimple_assign_rhs1 (stmt
);
3052 case GIMPLE_BINARY_RHS
:
3053 reduction_op
= gimple_assign_rhs2 (stmt
);
3055 case GIMPLE_TERNARY_RHS
:
3056 reduction_op
= gimple_assign_rhs3 (stmt
);
3062 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
3065 if (dump_enabled_p ())
3067 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3068 "unsupported data-type ");
3069 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
3070 TREE_TYPE (reduction_op
));
3071 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3076 mode
= TYPE_MODE (vectype
);
3077 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
3080 orig_stmt
= STMT_VINFO_STMT (stmt_info
);
3082 code
= gimple_assign_rhs_code (orig_stmt
);
3084 /* Add in cost for initial definition. */
3085 prologue_cost
+= add_stmt_cost (target_cost_data
, 1, scalar_to_vec
,
3086 stmt_info
, 0, vect_prologue
);
3088 /* Determine cost of epilogue code.
3090 We have a reduction operator that will reduce the vector in one statement.
3091 Also requires scalar extract. */
3093 if (!nested_in_vect_loop_p (loop
, orig_stmt
))
3095 if (reduc_code
!= ERROR_MARK
)
3097 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1, vector_stmt
,
3098 stmt_info
, 0, vect_epilogue
);
3099 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1, vec_to_scalar
,
3100 stmt_info
, 0, vect_epilogue
);
3104 int vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
3106 TYPE_SIZE (TREE_TYPE (gimple_assign_lhs (orig_stmt
)));
3107 int element_bitsize
= tree_to_uhwi (bitsize
);
3108 int nelements
= vec_size_in_bits
/ element_bitsize
;
3110 optab
= optab_for_tree_code (code
, vectype
, optab_default
);
3112 /* We have a whole vector shift available. */
3113 if (VECTOR_MODE_P (mode
)
3114 && optab_handler (optab
, mode
) != CODE_FOR_nothing
3115 && optab_handler (vec_shr_optab
, mode
) != CODE_FOR_nothing
)
3117 /* Final reduction via vector shifts and the reduction operator.
3118 Also requires scalar extract. */
3119 epilogue_cost
+= add_stmt_cost (target_cost_data
,
3120 exact_log2 (nelements
) * 2,
3121 vector_stmt
, stmt_info
, 0,
3123 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1,
3124 vec_to_scalar
, stmt_info
, 0,
3128 /* Use extracts and reduction op for final reduction. For N
3129 elements, we have N extracts and N-1 reduction ops. */
3130 epilogue_cost
+= add_stmt_cost (target_cost_data
,
3131 nelements
+ nelements
- 1,
3132 vector_stmt
, stmt_info
, 0,
3137 if (dump_enabled_p ())
3138 dump_printf (MSG_NOTE
,
3139 "vect_model_reduction_cost: inside_cost = %d, "
3140 "prologue_cost = %d, epilogue_cost = %d .\n", inside_cost
,
3141 prologue_cost
, epilogue_cost
);
3147 /* Function vect_model_induction_cost.
3149 Models cost for induction operations. */
3152 vect_model_induction_cost (stmt_vec_info stmt_info
, int ncopies
)
3154 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3155 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3156 unsigned inside_cost
, prologue_cost
;
3158 /* loop cost for vec_loop. */
3159 inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
3160 stmt_info
, 0, vect_body
);
3162 /* prologue cost for vec_init and vec_step. */
3163 prologue_cost
= add_stmt_cost (target_cost_data
, 2, scalar_to_vec
,
3164 stmt_info
, 0, vect_prologue
);
3166 if (dump_enabled_p ())
3167 dump_printf_loc (MSG_NOTE
, vect_location
,
3168 "vect_model_induction_cost: inside_cost = %d, "
3169 "prologue_cost = %d .\n", inside_cost
, prologue_cost
);
3173 /* Function get_initial_def_for_induction
3176 STMT - a stmt that performs an induction operation in the loop.
3177 IV_PHI - the initial value of the induction variable
3180 Return a vector variable, initialized with the first VF values of
3181 the induction variable. E.g., for an iv with IV_PHI='X' and
3182 evolution S, for a vector of 4 units, we want to return:
3183 [X, X + S, X + 2*S, X + 3*S]. */
3186 get_initial_def_for_induction (gimple iv_phi
)
3188 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (iv_phi
);
3189 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
3190 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3193 edge pe
= loop_preheader_edge (loop
);
3194 struct loop
*iv_loop
;
3196 tree new_vec
, vec_init
, vec_step
, t
;
3200 gimple init_stmt
, induction_phi
, new_stmt
;
3201 tree induc_def
, vec_def
, vec_dest
;
3202 tree init_expr
, step_expr
;
3203 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3208 stmt_vec_info phi_info
= vinfo_for_stmt (iv_phi
);
3209 bool nested_in_vect_loop
= false;
3210 gimple_seq stmts
= NULL
;
3211 imm_use_iterator imm_iter
;
3212 use_operand_p use_p
;
3216 gimple_stmt_iterator si
;
3217 basic_block bb
= gimple_bb (iv_phi
);
3221 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
3222 if (nested_in_vect_loop_p (loop
, iv_phi
))
3224 nested_in_vect_loop
= true;
3225 iv_loop
= loop
->inner
;
3229 gcc_assert (iv_loop
== (gimple_bb (iv_phi
))->loop_father
);
3231 latch_e
= loop_latch_edge (iv_loop
);
3232 loop_arg
= PHI_ARG_DEF_FROM_EDGE (iv_phi
, latch_e
);
3234 access_fn
= analyze_scalar_evolution (iv_loop
, PHI_RESULT (iv_phi
));
3235 gcc_assert (access_fn
);
3236 STRIP_NOPS (access_fn
);
3237 ok
= vect_is_simple_iv_evolution (iv_loop
->num
, access_fn
,
3238 &init_expr
, &step_expr
);
3240 pe
= loop_preheader_edge (iv_loop
);
3242 vectype
= get_vectype_for_scalar_type (TREE_TYPE (init_expr
));
3243 resvectype
= get_vectype_for_scalar_type (TREE_TYPE (PHI_RESULT (iv_phi
)));
3244 gcc_assert (vectype
);
3245 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3246 ncopies
= vf
/ nunits
;
3248 gcc_assert (phi_info
);
3249 gcc_assert (ncopies
>= 1);
3251 /* Find the first insertion point in the BB. */
3252 si
= gsi_after_labels (bb
);
3254 /* Create the vector that holds the initial_value of the induction. */
3255 if (nested_in_vect_loop
)
3257 /* iv_loop is nested in the loop to be vectorized. init_expr had already
3258 been created during vectorization of previous stmts. We obtain it
3259 from the STMT_VINFO_VEC_STMT of the defining stmt. */
3260 tree iv_def
= PHI_ARG_DEF_FROM_EDGE (iv_phi
,
3261 loop_preheader_edge (iv_loop
));
3262 vec_init
= vect_get_vec_def_for_operand (iv_def
, iv_phi
, NULL
);
3263 /* If the initial value is not of proper type, convert it. */
3264 if (!useless_type_conversion_p (vectype
, TREE_TYPE (vec_init
)))
3266 new_stmt
= gimple_build_assign_with_ops
3268 vect_get_new_vect_var (vectype
, vect_simple_var
, "vec_iv_"),
3269 build1 (VIEW_CONVERT_EXPR
, vectype
, vec_init
), NULL_TREE
);
3270 vec_init
= make_ssa_name (gimple_assign_lhs (new_stmt
), new_stmt
);
3271 gimple_assign_set_lhs (new_stmt
, vec_init
);
3272 new_bb
= gsi_insert_on_edge_immediate (loop_preheader_edge (iv_loop
),
3274 gcc_assert (!new_bb
);
3275 set_vinfo_for_stmt (new_stmt
,
3276 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
3281 vec
<constructor_elt
, va_gc
> *v
;
3283 /* iv_loop is the loop to be vectorized. Create:
3284 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
3285 new_var
= vect_get_new_vect_var (TREE_TYPE (vectype
),
3286 vect_scalar_var
, "var_");
3287 new_name
= force_gimple_operand (fold_convert (TREE_TYPE (vectype
),
3289 &stmts
, false, new_var
);
3292 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
3293 gcc_assert (!new_bb
);
3296 vec_alloc (v
, nunits
);
3297 bool constant_p
= is_gimple_min_invariant (new_name
);
3298 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
3299 for (i
= 1; i
< nunits
; i
++)
3301 /* Create: new_name_i = new_name + step_expr */
3302 new_name
= fold_build2 (PLUS_EXPR
, TREE_TYPE (new_name
),
3303 new_name
, step_expr
);
3304 if (!is_gimple_min_invariant (new_name
))
3306 init_stmt
= gimple_build_assign (new_var
, new_name
);
3307 new_name
= make_ssa_name (new_var
, init_stmt
);
3308 gimple_assign_set_lhs (init_stmt
, new_name
);
3309 new_bb
= gsi_insert_on_edge_immediate (pe
, init_stmt
);
3310 gcc_assert (!new_bb
);
3311 if (dump_enabled_p ())
3313 dump_printf_loc (MSG_NOTE
, vect_location
,
3314 "created new init_stmt: ");
3315 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, init_stmt
, 0);
3316 dump_printf (MSG_NOTE
, "\n");
3320 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
3322 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
3324 new_vec
= build_vector_from_ctor (vectype
, v
);
3326 new_vec
= build_constructor (vectype
, v
);
3327 vec_init
= vect_init_vector (iv_phi
, new_vec
, vectype
, NULL
);
3331 /* Create the vector that holds the step of the induction. */
3332 if (nested_in_vect_loop
)
3333 /* iv_loop is nested in the loop to be vectorized. Generate:
3334 vec_step = [S, S, S, S] */
3335 new_name
= step_expr
;
3338 /* iv_loop is the loop to be vectorized. Generate:
3339 vec_step = [VF*S, VF*S, VF*S, VF*S] */
3340 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
)))
3342 expr
= build_int_cst (integer_type_node
, vf
);
3343 expr
= fold_convert (TREE_TYPE (step_expr
), expr
);
3346 expr
= build_int_cst (TREE_TYPE (step_expr
), vf
);
3347 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
3349 if (TREE_CODE (step_expr
) == SSA_NAME
)
3350 new_name
= vect_init_vector (iv_phi
, new_name
,
3351 TREE_TYPE (step_expr
), NULL
);
3354 t
= unshare_expr (new_name
);
3355 gcc_assert (CONSTANT_CLASS_P (new_name
)
3356 || TREE_CODE (new_name
) == SSA_NAME
);
3357 stepvectype
= get_vectype_for_scalar_type (TREE_TYPE (new_name
));
3358 gcc_assert (stepvectype
);
3359 new_vec
= build_vector_from_val (stepvectype
, t
);
3360 vec_step
= vect_init_vector (iv_phi
, new_vec
, stepvectype
, NULL
);
3363 /* Create the following def-use cycle:
3368 vec_iv = PHI <vec_init, vec_loop>
3372 vec_loop = vec_iv + vec_step; */
3374 /* Create the induction-phi that defines the induction-operand. */
3375 vec_dest
= vect_get_new_vect_var (vectype
, vect_simple_var
, "vec_iv_");
3376 induction_phi
= create_phi_node (vec_dest
, iv_loop
->header
);
3377 set_vinfo_for_stmt (induction_phi
,
3378 new_stmt_vec_info (induction_phi
, loop_vinfo
, NULL
));
3379 induc_def
= PHI_RESULT (induction_phi
);
3381 /* Create the iv update inside the loop */
3382 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, vec_dest
,
3383 induc_def
, vec_step
);
3384 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
3385 gimple_assign_set_lhs (new_stmt
, vec_def
);
3386 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3387 set_vinfo_for_stmt (new_stmt
, new_stmt_vec_info (new_stmt
, loop_vinfo
,
3390 /* Set the arguments of the phi node: */
3391 add_phi_arg (induction_phi
, vec_init
, pe
, UNKNOWN_LOCATION
);
3392 add_phi_arg (induction_phi
, vec_def
, loop_latch_edge (iv_loop
),
3396 /* In case that vectorization factor (VF) is bigger than the number
3397 of elements that we can fit in a vectype (nunits), we have to generate
3398 more than one vector stmt - i.e - we need to "unroll" the
3399 vector stmt by a factor VF/nunits. For more details see documentation
3400 in vectorizable_operation. */
3404 stmt_vec_info prev_stmt_vinfo
;
3405 /* FORNOW. This restriction should be relaxed. */
3406 gcc_assert (!nested_in_vect_loop
);
3408 /* Create the vector that holds the step of the induction. */
3409 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
)))
3411 expr
= build_int_cst (integer_type_node
, nunits
);
3412 expr
= fold_convert (TREE_TYPE (step_expr
), expr
);
3415 expr
= build_int_cst (TREE_TYPE (step_expr
), nunits
);
3416 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
3418 if (TREE_CODE (step_expr
) == SSA_NAME
)
3419 new_name
= vect_init_vector (iv_phi
, new_name
,
3420 TREE_TYPE (step_expr
), NULL
);
3421 t
= unshare_expr (new_name
);
3422 gcc_assert (CONSTANT_CLASS_P (new_name
)
3423 || TREE_CODE (new_name
) == SSA_NAME
);
3424 new_vec
= build_vector_from_val (stepvectype
, t
);
3425 vec_step
= vect_init_vector (iv_phi
, new_vec
, stepvectype
, NULL
);
3427 vec_def
= induc_def
;
3428 prev_stmt_vinfo
= vinfo_for_stmt (induction_phi
);
3429 for (i
= 1; i
< ncopies
; i
++)
3431 /* vec_i = vec_prev + vec_step */
3432 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, vec_dest
,
3434 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
3435 gimple_assign_set_lhs (new_stmt
, vec_def
);
3437 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3438 if (!useless_type_conversion_p (resvectype
, vectype
))
3440 new_stmt
= gimple_build_assign_with_ops
3442 vect_get_new_vect_var (resvectype
, vect_simple_var
,
3444 build1 (VIEW_CONVERT_EXPR
, resvectype
,
3445 gimple_assign_lhs (new_stmt
)), NULL_TREE
);
3446 gimple_assign_set_lhs (new_stmt
,
3448 (gimple_assign_lhs (new_stmt
), new_stmt
));
3449 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3451 set_vinfo_for_stmt (new_stmt
,
3452 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
3453 STMT_VINFO_RELATED_STMT (prev_stmt_vinfo
) = new_stmt
;
3454 prev_stmt_vinfo
= vinfo_for_stmt (new_stmt
);
3458 if (nested_in_vect_loop
)
3460 /* Find the loop-closed exit-phi of the induction, and record
3461 the final vector of induction results: */
3463 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
3465 if (!flow_bb_inside_loop_p (iv_loop
, gimple_bb (USE_STMT (use_p
))))
3467 exit_phi
= USE_STMT (use_p
);
3473 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (exit_phi
);
3474 /* FORNOW. Currently not supporting the case that an inner-loop induction
3475 is not used in the outer-loop (i.e. only outside the outer-loop). */
3476 gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo
)
3477 && !STMT_VINFO_LIVE_P (stmt_vinfo
));
3479 STMT_VINFO_VEC_STMT (stmt_vinfo
) = new_stmt
;
3480 if (dump_enabled_p ())
3482 dump_printf_loc (MSG_NOTE
, vect_location
,
3483 "vector of inductions after inner-loop:");
3484 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, new_stmt
, 0);
3485 dump_printf (MSG_NOTE
, "\n");
3491 if (dump_enabled_p ())
3493 dump_printf_loc (MSG_NOTE
, vect_location
,
3494 "transform induction: created def-use cycle: ");
3495 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, induction_phi
, 0);
3496 dump_printf (MSG_NOTE
, "\n");
3497 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
3498 SSA_NAME_DEF_STMT (vec_def
), 0);
3499 dump_printf (MSG_NOTE
, "\n");
3502 STMT_VINFO_VEC_STMT (phi_info
) = induction_phi
;
3503 if (!useless_type_conversion_p (resvectype
, vectype
))
3505 new_stmt
= gimple_build_assign_with_ops
3507 vect_get_new_vect_var (resvectype
, vect_simple_var
, "vec_iv_"),
3508 build1 (VIEW_CONVERT_EXPR
, resvectype
, induc_def
), NULL_TREE
);
3509 induc_def
= make_ssa_name (gimple_assign_lhs (new_stmt
), new_stmt
);
3510 gimple_assign_set_lhs (new_stmt
, induc_def
);
3511 si
= gsi_after_labels (bb
);
3512 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3513 set_vinfo_for_stmt (new_stmt
,
3514 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
3515 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_stmt
))
3516 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (induction_phi
));
3523 /* Function get_initial_def_for_reduction
3526 STMT - a stmt that performs a reduction operation in the loop.
3527 INIT_VAL - the initial value of the reduction variable
3530 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
3531 of the reduction (used for adjusting the epilog - see below).
3532 Return a vector variable, initialized according to the operation that STMT
3533 performs. This vector will be used as the initial value of the
3534 vector of partial results.
3536 Option1 (adjust in epilog): Initialize the vector as follows:
3537 add/bit or/xor: [0,0,...,0,0]
3538 mult/bit and: [1,1,...,1,1]
3539 min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
3540 and when necessary (e.g. add/mult case) let the caller know
3541 that it needs to adjust the result by init_val.
3543 Option2: Initialize the vector as follows:
3544 add/bit or/xor: [init_val,0,0,...,0]
3545 mult/bit and: [init_val,1,1,...,1]
3546 min/max/cond_expr: [init_val,init_val,...,init_val]
3547 and no adjustments are needed.
3549 For example, for the following code:
3555 STMT is 's = s + a[i]', and the reduction variable is 's'.
3556 For a vector of 4 units, we want to return either [0,0,0,init_val],
3557 or [0,0,0,0] and let the caller know that it needs to adjust
3558 the result at the end by 'init_val'.
3560 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
3561 initialization vector is simpler (same element in all entries), if
3562 ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
3564 A cost model should help decide between these two schemes. */
3567 get_initial_def_for_reduction (gimple stmt
, tree init_val
,
3568 tree
*adjustment_def
)
3570 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
3571 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
3572 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3573 tree scalar_type
= TREE_TYPE (init_val
);
3574 tree vectype
= get_vectype_for_scalar_type (scalar_type
);
3576 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3581 bool nested_in_vect_loop
= false;
3583 REAL_VALUE_TYPE real_init_val
= dconst0
;
3584 int int_init_val
= 0;
3585 gimple def_stmt
= NULL
;
3587 gcc_assert (vectype
);
3588 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3590 gcc_assert (POINTER_TYPE_P (scalar_type
) || INTEGRAL_TYPE_P (scalar_type
)
3591 || SCALAR_FLOAT_TYPE_P (scalar_type
));
3593 if (nested_in_vect_loop_p (loop
, stmt
))
3594 nested_in_vect_loop
= true;
3596 gcc_assert (loop
== (gimple_bb (stmt
))->loop_father
);
3598 /* In case of double reduction we only create a vector variable to be put
3599 in the reduction phi node. The actual statement creation is done in
3600 vect_create_epilog_for_reduction. */
3601 if (adjustment_def
&& nested_in_vect_loop
3602 && TREE_CODE (init_val
) == SSA_NAME
3603 && (def_stmt
= SSA_NAME_DEF_STMT (init_val
))
3604 && gimple_code (def_stmt
) == GIMPLE_PHI
3605 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
3606 && vinfo_for_stmt (def_stmt
)
3607 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
3608 == vect_double_reduction_def
)
3610 *adjustment_def
= NULL
;
3611 return vect_create_destination_var (init_val
, vectype
);
3614 if (TREE_CONSTANT (init_val
))
3616 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
3617 init_value
= build_real (scalar_type
, TREE_REAL_CST (init_val
));
3619 init_value
= build_int_cst (scalar_type
, TREE_INT_CST_LOW (init_val
));
3622 init_value
= init_val
;
3626 case WIDEN_SUM_EXPR
:
3634 /* ADJUSMENT_DEF is NULL when called from
3635 vect_create_epilog_for_reduction to vectorize double reduction. */
3638 if (nested_in_vect_loop
)
3639 *adjustment_def
= vect_get_vec_def_for_operand (init_val
, stmt
,
3642 *adjustment_def
= init_val
;
3645 if (code
== MULT_EXPR
)
3647 real_init_val
= dconst1
;
3651 if (code
== BIT_AND_EXPR
)
3654 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
3655 def_for_init
= build_real (scalar_type
, real_init_val
);
3657 def_for_init
= build_int_cst (scalar_type
, int_init_val
);
3659 /* Create a vector of '0' or '1' except the first element. */
3660 elts
= XALLOCAVEC (tree
, nunits
);
3661 for (i
= nunits
- 2; i
>= 0; --i
)
3662 elts
[i
+ 1] = def_for_init
;
3664 /* Option1: the first element is '0' or '1' as well. */
3667 elts
[0] = def_for_init
;
3668 init_def
= build_vector (vectype
, elts
);
3672 /* Option2: the first element is INIT_VAL. */
3674 if (TREE_CONSTANT (init_val
))
3675 init_def
= build_vector (vectype
, elts
);
3678 vec
<constructor_elt
, va_gc
> *v
;
3679 vec_alloc (v
, nunits
);
3680 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, init_val
);
3681 for (i
= 1; i
< nunits
; ++i
)
3682 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[i
]);
3683 init_def
= build_constructor (vectype
, v
);
3693 *adjustment_def
= NULL_TREE
;
3694 init_def
= vect_get_vec_def_for_operand (init_val
, stmt
, NULL
);
3698 init_def
= build_vector_from_val (vectype
, init_value
);
3709 /* Function vect_create_epilog_for_reduction
3711 Create code at the loop-epilog to finalize the result of a reduction
3714 VECT_DEFS is list of vector of partial results, i.e., the lhs's of vector
3715 reduction statements.
3716 STMT is the scalar reduction stmt that is being vectorized.
3717 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
3718 number of elements that we can fit in a vectype (nunits). In this case
3719 we have to generate more than one vector stmt - i.e - we need to "unroll"
3720 the vector stmt by a factor VF/nunits. For more details see documentation
3721 in vectorizable_operation.
3722 REDUC_CODE is the tree-code for the epilog reduction.
3723 REDUCTION_PHIS is a list of the phi-nodes that carry the reduction
3725 REDUC_INDEX is the index of the operand in the right hand side of the
3726 statement that is defined by REDUCTION_PHI.
3727 DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
3728 SLP_NODE is an SLP node containing a group of reduction statements. The
3729 first one in this group is STMT.
3732 1. Creates the reduction def-use cycles: sets the arguments for
3734 The loop-entry argument is the vectorized initial-value of the reduction.
3735 The loop-latch argument is taken from VECT_DEFS - the vector of partial
3737 2. "Reduces" each vector of partial results VECT_DEFS into a single result,
3738 by applying the operation specified by REDUC_CODE if available, or by
3739 other means (whole-vector shifts or a scalar loop).
3740 The function also creates a new phi node at the loop exit to preserve
3741 loop-closed form, as illustrated below.
3743 The flow at the entry to this function:
3746 vec_def = phi <null, null> # REDUCTION_PHI
3747 VECT_DEF = vector_stmt # vectorized form of STMT
3748 s_loop = scalar_stmt # (scalar) STMT
3750 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3754 The above is transformed by this function into:
3757 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3758 VECT_DEF = vector_stmt # vectorized form of STMT
3759 s_loop = scalar_stmt # (scalar) STMT
3761 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3762 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3763 v_out2 = reduce <v_out1>
3764 s_out3 = extract_field <v_out2, 0>
3765 s_out4 = adjust_result <s_out3>
3771 vect_create_epilog_for_reduction (vec
<tree
> vect_defs
, gimple stmt
,
3772 int ncopies
, enum tree_code reduc_code
,
3773 vec
<gimple
> reduction_phis
,
3774 int reduc_index
, bool double_reduc
,
3777 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3778 stmt_vec_info prev_phi_info
;
3780 enum machine_mode mode
;
3781 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3782 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
), *outer_loop
= NULL
;
3783 basic_block exit_bb
;
3786 gimple new_phi
= NULL
, phi
;
3787 gimple_stmt_iterator exit_gsi
;
3789 tree new_temp
= NULL_TREE
, new_dest
, new_name
, new_scalar_dest
;
3790 gimple epilog_stmt
= NULL
;
3791 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3793 tree bitsize
, bitpos
;
3794 tree adjustment_def
= NULL
;
3795 tree vec_initial_def
= NULL
;
3796 tree reduction_op
, expr
, def
;
3797 tree orig_name
, scalar_result
;
3798 imm_use_iterator imm_iter
, phi_imm_iter
;
3799 use_operand_p use_p
, phi_use_p
;
3800 bool extract_scalar_result
= false;
3801 gimple use_stmt
, orig_stmt
, reduction_phi
= NULL
;
3802 bool nested_in_vect_loop
= false;
3803 vec
<gimple
> new_phis
= vNULL
;
3804 vec
<gimple
> inner_phis
= vNULL
;
3805 enum vect_def_type dt
= vect_unknown_def_type
;
3807 vec
<tree
> scalar_results
= vNULL
;
3808 unsigned int group_size
= 1, k
, ratio
;
3809 vec
<tree
> vec_initial_defs
= vNULL
;
3811 bool slp_reduc
= false;
3812 tree new_phi_result
;
3813 gimple inner_phi
= NULL
;
3816 group_size
= SLP_TREE_SCALAR_STMTS (slp_node
).length ();
3818 if (nested_in_vect_loop_p (loop
, stmt
))
3822 nested_in_vect_loop
= true;
3823 gcc_assert (!slp_node
);
3826 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3828 case GIMPLE_SINGLE_RHS
:
3829 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
))
3831 reduction_op
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), reduc_index
);
3833 case GIMPLE_UNARY_RHS
:
3834 reduction_op
= gimple_assign_rhs1 (stmt
);
3836 case GIMPLE_BINARY_RHS
:
3837 reduction_op
= reduc_index
?
3838 gimple_assign_rhs2 (stmt
) : gimple_assign_rhs1 (stmt
);
3840 case GIMPLE_TERNARY_RHS
:
3841 reduction_op
= gimple_op (stmt
, reduc_index
+ 1);
3847 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
3848 gcc_assert (vectype
);
3849 mode
= TYPE_MODE (vectype
);
3851 /* 1. Create the reduction def-use cycle:
3852 Set the arguments of REDUCTION_PHIS, i.e., transform
3855 vec_def = phi <null, null> # REDUCTION_PHI
3856 VECT_DEF = vector_stmt # vectorized form of STMT
3862 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3863 VECT_DEF = vector_stmt # vectorized form of STMT
3866 (in case of SLP, do it for all the phis). */
3868 /* Get the loop-entry arguments. */
3870 vect_get_vec_defs (reduction_op
, NULL_TREE
, stmt
, &vec_initial_defs
,
3871 NULL
, slp_node
, reduc_index
);
3874 vec_initial_defs
.create (1);
3875 /* For the case of reduction, vect_get_vec_def_for_operand returns
3876 the scalar def before the loop, that defines the initial value
3877 of the reduction variable. */
3878 vec_initial_def
= vect_get_vec_def_for_operand (reduction_op
, stmt
,
3880 vec_initial_defs
.quick_push (vec_initial_def
);
3883 /* Set phi nodes arguments. */
3884 FOR_EACH_VEC_ELT (reduction_phis
, i
, phi
)
3886 tree vec_init_def
= vec_initial_defs
[i
];
3887 tree def
= vect_defs
[i
];
3888 for (j
= 0; j
< ncopies
; j
++)
3890 /* Set the loop-entry arg of the reduction-phi. */
3891 add_phi_arg (phi
, vec_init_def
, loop_preheader_edge (loop
),
3894 /* Set the loop-latch arg for the reduction-phi. */
3896 def
= vect_get_vec_def_for_stmt_copy (vect_unknown_def_type
, def
);
3898 add_phi_arg (phi
, def
, loop_latch_edge (loop
), UNKNOWN_LOCATION
);
3900 if (dump_enabled_p ())
3902 dump_printf_loc (MSG_NOTE
, vect_location
,
3903 "transform reduction: created def-use cycle: ");
3904 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
3905 dump_printf (MSG_NOTE
, "\n");
3906 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, SSA_NAME_DEF_STMT (def
), 0);
3907 dump_printf (MSG_NOTE
, "\n");
3910 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
3914 vec_initial_defs
.release ();
3916 /* 2. Create epilog code.
3917 The reduction epilog code operates across the elements of the vector
3918 of partial results computed by the vectorized loop.
3919 The reduction epilog code consists of:
3921 step 1: compute the scalar result in a vector (v_out2)
3922 step 2: extract the scalar result (s_out3) from the vector (v_out2)
3923 step 3: adjust the scalar result (s_out3) if needed.
3925 Step 1 can be accomplished using one the following three schemes:
3926 (scheme 1) using reduc_code, if available.
3927 (scheme 2) using whole-vector shifts, if available.
3928 (scheme 3) using a scalar loop. In this case steps 1+2 above are
3931 The overall epilog code looks like this:
3933 s_out0 = phi <s_loop> # original EXIT_PHI
3934 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3935 v_out2 = reduce <v_out1> # step 1
3936 s_out3 = extract_field <v_out2, 0> # step 2
3937 s_out4 = adjust_result <s_out3> # step 3
3939 (step 3 is optional, and steps 1 and 2 may be combined).
3940 Lastly, the uses of s_out0 are replaced by s_out4. */
3943 /* 2.1 Create new loop-exit-phis to preserve loop-closed form:
3944 v_out1 = phi <VECT_DEF>
3945 Store them in NEW_PHIS. */
3947 exit_bb
= single_exit (loop
)->dest
;
3948 prev_phi_info
= NULL
;
3949 new_phis
.create (vect_defs
.length ());
3950 FOR_EACH_VEC_ELT (vect_defs
, i
, def
)
3952 for (j
= 0; j
< ncopies
; j
++)
3954 tree new_def
= copy_ssa_name (def
, NULL
);
3955 phi
= create_phi_node (new_def
, exit_bb
);
3956 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, loop_vinfo
, NULL
));
3958 new_phis
.quick_push (phi
);
3961 def
= vect_get_vec_def_for_stmt_copy (dt
, def
);
3962 STMT_VINFO_RELATED_STMT (prev_phi_info
) = phi
;
3965 SET_PHI_ARG_DEF (phi
, single_exit (loop
)->dest_idx
, def
);
3966 prev_phi_info
= vinfo_for_stmt (phi
);
3970 /* The epilogue is created for the outer-loop, i.e., for the loop being
3971 vectorized. Create exit phis for the outer loop. */
3975 exit_bb
= single_exit (loop
)->dest
;
3976 inner_phis
.create (vect_defs
.length ());
3977 FOR_EACH_VEC_ELT (new_phis
, i
, phi
)
3979 tree new_result
= copy_ssa_name (PHI_RESULT (phi
), NULL
);
3980 gimple outer_phi
= create_phi_node (new_result
, exit_bb
);
3981 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
3983 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
3985 inner_phis
.quick_push (phi
);
3986 new_phis
[i
] = outer_phi
;
3987 prev_phi_info
= vinfo_for_stmt (outer_phi
);
3988 while (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
)))
3990 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
3991 new_result
= copy_ssa_name (PHI_RESULT (phi
), NULL
);
3992 outer_phi
= create_phi_node (new_result
, exit_bb
);
3993 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
3995 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
3997 STMT_VINFO_RELATED_STMT (prev_phi_info
) = outer_phi
;
3998 prev_phi_info
= vinfo_for_stmt (outer_phi
);
4003 exit_gsi
= gsi_after_labels (exit_bb
);
4005 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
4006 (i.e. when reduc_code is not available) and in the final adjustment
4007 code (if needed). Also get the original scalar reduction variable as
4008 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
4009 represents a reduction pattern), the tree-code and scalar-def are
4010 taken from the original stmt that the pattern-stmt (STMT) replaces.
4011 Otherwise (it is a regular reduction) - the tree-code and scalar-def
4012 are taken from STMT. */
4014 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
4017 /* Regular reduction */
4022 /* Reduction pattern */
4023 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (orig_stmt
);
4024 gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
));
4025 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo
) == stmt
);
4028 code
= gimple_assign_rhs_code (orig_stmt
);
4029 /* For MINUS_EXPR the initial vector is [init_val,0,...,0], therefore,
4030 partial results are added and not subtracted. */
4031 if (code
== MINUS_EXPR
)
4034 scalar_dest
= gimple_assign_lhs (orig_stmt
);
4035 scalar_type
= TREE_TYPE (scalar_dest
);
4036 scalar_results
.create (group_size
);
4037 new_scalar_dest
= vect_create_destination_var (scalar_dest
, NULL
);
4038 bitsize
= TYPE_SIZE (scalar_type
);
4040 /* In case this is a reduction in an inner-loop while vectorizing an outer
4041 loop - we don't need to extract a single scalar result at the end of the
4042 inner-loop (unless it is double reduction, i.e., the use of reduction is
4043 outside the outer-loop). The final vector of partial results will be used
4044 in the vectorized outer-loop, or reduced to a scalar result at the end of
4046 if (nested_in_vect_loop
&& !double_reduc
)
4047 goto vect_finalize_reduction
;
4049 /* SLP reduction without reduction chain, e.g.,
4053 b2 = operation (b1) */
4054 slp_reduc
= (slp_node
&& !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)));
4056 /* In case of reduction chain, e.g.,
4059 a3 = operation (a2),
4061 we may end up with more than one vector result. Here we reduce them to
4063 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4065 tree first_vect
= PHI_RESULT (new_phis
[0]);
4067 gimple new_vec_stmt
= NULL
;
4069 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4070 for (k
= 1; k
< new_phis
.length (); k
++)
4072 gimple next_phi
= new_phis
[k
];
4073 tree second_vect
= PHI_RESULT (next_phi
);
4075 tmp
= build2 (code
, vectype
, first_vect
, second_vect
);
4076 new_vec_stmt
= gimple_build_assign (vec_dest
, tmp
);
4077 first_vect
= make_ssa_name (vec_dest
, new_vec_stmt
);
4078 gimple_assign_set_lhs (new_vec_stmt
, first_vect
);
4079 gsi_insert_before (&exit_gsi
, new_vec_stmt
, GSI_SAME_STMT
);
4082 new_phi_result
= first_vect
;
4085 new_phis
.truncate (0);
4086 new_phis
.safe_push (new_vec_stmt
);
4090 new_phi_result
= PHI_RESULT (new_phis
[0]);
4092 /* 2.3 Create the reduction code, using one of the three schemes described
4093 above. In SLP we simply need to extract all the elements from the
4094 vector (without reducing them), so we use scalar shifts. */
4095 if (reduc_code
!= ERROR_MARK
&& !slp_reduc
)
4099 /*** Case 1: Create:
4100 v_out2 = reduc_expr <v_out1> */
4102 if (dump_enabled_p ())
4103 dump_printf_loc (MSG_NOTE
, vect_location
,
4104 "Reduce using direct vector reduction.\n");
4106 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4107 tmp
= build1 (reduc_code
, vectype
, new_phi_result
);
4108 epilog_stmt
= gimple_build_assign (vec_dest
, tmp
);
4109 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
4110 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4111 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4113 extract_scalar_result
= true;
4117 enum tree_code shift_code
= ERROR_MARK
;
4118 bool have_whole_vector_shift
= true;
4120 int element_bitsize
= tree_to_uhwi (bitsize
);
4121 int vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
4124 if (optab_handler (vec_shr_optab
, mode
) != CODE_FOR_nothing
)
4125 shift_code
= VEC_RSHIFT_EXPR
;
4127 have_whole_vector_shift
= false;
4129 /* Regardless of whether we have a whole vector shift, if we're
4130 emulating the operation via tree-vect-generic, we don't want
4131 to use it. Only the first round of the reduction is likely
4132 to still be profitable via emulation. */
4133 /* ??? It might be better to emit a reduction tree code here, so that
4134 tree-vect-generic can expand the first round via bit tricks. */
4135 if (!VECTOR_MODE_P (mode
))
4136 have_whole_vector_shift
= false;
4139 optab optab
= optab_for_tree_code (code
, vectype
, optab_default
);
4140 if (optab_handler (optab
, mode
) == CODE_FOR_nothing
)
4141 have_whole_vector_shift
= false;
4144 if (have_whole_vector_shift
&& !slp_reduc
)
4146 /*** Case 2: Create:
4147 for (offset = VS/2; offset >= element_size; offset/=2)
4149 Create: va' = vec_shift <va, offset>
4150 Create: va = vop <va, va'>
4153 if (dump_enabled_p ())
4154 dump_printf_loc (MSG_NOTE
, vect_location
,
4155 "Reduce using vector shifts\n");
4157 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4158 new_temp
= new_phi_result
;
4159 for (bit_offset
= vec_size_in_bits
/2;
4160 bit_offset
>= element_bitsize
;
4163 tree bitpos
= size_int (bit_offset
);
4165 epilog_stmt
= gimple_build_assign_with_ops (shift_code
,
4166 vec_dest
, new_temp
, bitpos
);
4167 new_name
= make_ssa_name (vec_dest
, epilog_stmt
);
4168 gimple_assign_set_lhs (epilog_stmt
, new_name
);
4169 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4171 epilog_stmt
= gimple_build_assign_with_ops (code
, vec_dest
,
4172 new_name
, new_temp
);
4173 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
4174 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4175 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4178 extract_scalar_result
= true;
4184 /*** Case 3: Create:
4185 s = extract_field <v_out2, 0>
4186 for (offset = element_size;
4187 offset < vector_size;
4188 offset += element_size;)
4190 Create: s' = extract_field <v_out2, offset>
4191 Create: s = op <s, s'> // For non SLP cases
4194 if (dump_enabled_p ())
4195 dump_printf_loc (MSG_NOTE
, vect_location
,
4196 "Reduce using scalar code.\n");
4198 vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
4199 FOR_EACH_VEC_ELT (new_phis
, i
, new_phi
)
4201 if (gimple_code (new_phi
) == GIMPLE_PHI
)
4202 vec_temp
= PHI_RESULT (new_phi
);
4204 vec_temp
= gimple_assign_lhs (new_phi
);
4205 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
, bitsize
,
4207 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4208 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4209 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4210 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4212 /* In SLP we don't need to apply reduction operation, so we just
4213 collect s' values in SCALAR_RESULTS. */
4215 scalar_results
.safe_push (new_temp
);
4217 for (bit_offset
= element_bitsize
;
4218 bit_offset
< vec_size_in_bits
;
4219 bit_offset
+= element_bitsize
)
4221 tree bitpos
= bitsize_int (bit_offset
);
4222 tree rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
,
4225 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4226 new_name
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4227 gimple_assign_set_lhs (epilog_stmt
, new_name
);
4228 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4232 /* In SLP we don't need to apply reduction operation, so
4233 we just collect s' values in SCALAR_RESULTS. */
4234 new_temp
= new_name
;
4235 scalar_results
.safe_push (new_name
);
4239 epilog_stmt
= gimple_build_assign_with_ops (code
,
4240 new_scalar_dest
, new_name
, new_temp
);
4241 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4242 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4243 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4248 /* The only case where we need to reduce scalar results in SLP, is
4249 unrolling. If the size of SCALAR_RESULTS is greater than
4250 GROUP_SIZE, we reduce them combining elements modulo
4254 tree res
, first_res
, new_res
;
4257 /* Reduce multiple scalar results in case of SLP unrolling. */
4258 for (j
= group_size
; scalar_results
.iterate (j
, &res
);
4261 first_res
= scalar_results
[j
% group_size
];
4262 new_stmt
= gimple_build_assign_with_ops (code
,
4263 new_scalar_dest
, first_res
, res
);
4264 new_res
= make_ssa_name (new_scalar_dest
, new_stmt
);
4265 gimple_assign_set_lhs (new_stmt
, new_res
);
4266 gsi_insert_before (&exit_gsi
, new_stmt
, GSI_SAME_STMT
);
4267 scalar_results
[j
% group_size
] = new_res
;
4271 /* Not SLP - we have one scalar to keep in SCALAR_RESULTS. */
4272 scalar_results
.safe_push (new_temp
);
4274 extract_scalar_result
= false;
4278 /* 2.4 Extract the final scalar result. Create:
4279 s_out3 = extract_field <v_out2, bitpos> */
4281 if (extract_scalar_result
)
4285 if (dump_enabled_p ())
4286 dump_printf_loc (MSG_NOTE
, vect_location
,
4287 "extract scalar result\n");
4289 if (BYTES_BIG_ENDIAN
)
4290 bitpos
= size_binop (MULT_EXPR
,
4291 bitsize_int (TYPE_VECTOR_SUBPARTS (vectype
) - 1),
4292 TYPE_SIZE (scalar_type
));
4294 bitpos
= bitsize_zero_node
;
4296 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, new_temp
, bitsize
, bitpos
);
4297 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4298 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4299 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4300 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4301 scalar_results
.safe_push (new_temp
);
4304 vect_finalize_reduction
:
4309 /* 2.5 Adjust the final result by the initial value of the reduction
4310 variable. (When such adjustment is not needed, then
4311 'adjustment_def' is zero). For example, if code is PLUS we create:
4312 new_temp = loop_exit_def + adjustment_def */
4316 gcc_assert (!slp_reduc
);
4317 if (nested_in_vect_loop
)
4319 new_phi
= new_phis
[0];
4320 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) == VECTOR_TYPE
);
4321 expr
= build2 (code
, vectype
, PHI_RESULT (new_phi
), adjustment_def
);
4322 new_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4326 new_temp
= scalar_results
[0];
4327 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) != VECTOR_TYPE
);
4328 expr
= build2 (code
, scalar_type
, new_temp
, adjustment_def
);
4329 new_dest
= vect_create_destination_var (scalar_dest
, scalar_type
);
4332 epilog_stmt
= gimple_build_assign (new_dest
, expr
);
4333 new_temp
= make_ssa_name (new_dest
, epilog_stmt
);
4334 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4335 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4336 if (nested_in_vect_loop
)
4338 set_vinfo_for_stmt (epilog_stmt
,
4339 new_stmt_vec_info (epilog_stmt
, loop_vinfo
,
4341 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (epilog_stmt
)) =
4342 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_phi
));
4345 scalar_results
.quick_push (new_temp
);
4347 scalar_results
[0] = new_temp
;
4350 scalar_results
[0] = new_temp
;
4352 new_phis
[0] = epilog_stmt
;
4355 /* 2.6 Handle the loop-exit phis. Replace the uses of scalar loop-exit
4356 phis with new adjusted scalar results, i.e., replace use <s_out0>
4361 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4362 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4363 v_out2 = reduce <v_out1>
4364 s_out3 = extract_field <v_out2, 0>
4365 s_out4 = adjust_result <s_out3>
4372 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4373 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4374 v_out2 = reduce <v_out1>
4375 s_out3 = extract_field <v_out2, 0>
4376 s_out4 = adjust_result <s_out3>
4381 /* In SLP reduction chain we reduce vector results into one vector if
4382 necessary, hence we set here GROUP_SIZE to 1. SCALAR_DEST is the LHS of
4383 the last stmt in the reduction chain, since we are looking for the loop
4385 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4387 scalar_dest
= gimple_assign_lhs (
4388 SLP_TREE_SCALAR_STMTS (slp_node
)[group_size
- 1]);
4392 /* In SLP we may have several statements in NEW_PHIS and REDUCTION_PHIS (in
4393 case that GROUP_SIZE is greater than vectorization factor). Therefore, we
4394 need to match SCALAR_RESULTS with corresponding statements. The first
4395 (GROUP_SIZE / number of new vector stmts) scalar results correspond to
4396 the first vector stmt, etc.
4397 (RATIO is equal to (GROUP_SIZE / number of new vector stmts)). */
4398 if (group_size
> new_phis
.length ())
4400 ratio
= group_size
/ new_phis
.length ();
4401 gcc_assert (!(group_size
% new_phis
.length ()));
4406 for (k
= 0; k
< group_size
; k
++)
4410 epilog_stmt
= new_phis
[k
/ ratio
];
4411 reduction_phi
= reduction_phis
[k
/ ratio
];
4413 inner_phi
= inner_phis
[k
/ ratio
];
4418 gimple current_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[k
];
4420 orig_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (current_stmt
));
4421 /* SLP statements can't participate in patterns. */
4422 gcc_assert (!orig_stmt
);
4423 scalar_dest
= gimple_assign_lhs (current_stmt
);
4427 /* Find the loop-closed-use at the loop exit of the original scalar
4428 result. (The reduction result is expected to have two immediate uses -
4429 one at the latch block, and one at the loop exit). */
4430 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
4431 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
)))
4432 && !is_gimple_debug (USE_STMT (use_p
)))
4433 phis
.safe_push (USE_STMT (use_p
));
4435 /* While we expect to have found an exit_phi because of loop-closed-ssa
4436 form we can end up without one if the scalar cycle is dead. */
4438 FOR_EACH_VEC_ELT (phis
, i
, exit_phi
)
4442 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
4445 /* FORNOW. Currently not supporting the case that an inner-loop
4446 reduction is not used in the outer-loop (but only outside the
4447 outer-loop), unless it is double reduction. */
4448 gcc_assert ((STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
4449 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
))
4452 STMT_VINFO_VEC_STMT (exit_phi_vinfo
) = epilog_stmt
;
4454 || STMT_VINFO_DEF_TYPE (exit_phi_vinfo
)
4455 != vect_double_reduction_def
)
4458 /* Handle double reduction:
4460 stmt1: s1 = phi <s0, s2> - double reduction phi (outer loop)
4461 stmt2: s3 = phi <s1, s4> - (regular) reduc phi (inner loop)
4462 stmt3: s4 = use (s3) - (regular) reduc stmt (inner loop)
4463 stmt4: s2 = phi <s4> - double reduction stmt (outer loop)
4465 At that point the regular reduction (stmt2 and stmt3) is
4466 already vectorized, as well as the exit phi node, stmt4.
4467 Here we vectorize the phi node of double reduction, stmt1, and
4468 update all relevant statements. */
4470 /* Go through all the uses of s2 to find double reduction phi
4471 node, i.e., stmt1 above. */
4472 orig_name
= PHI_RESULT (exit_phi
);
4473 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
4475 stmt_vec_info use_stmt_vinfo
;
4476 stmt_vec_info new_phi_vinfo
;
4477 tree vect_phi_init
, preheader_arg
, vect_phi_res
, init_def
;
4478 basic_block bb
= gimple_bb (use_stmt
);
4481 /* Check that USE_STMT is really double reduction phi
4483 if (gimple_code (use_stmt
) != GIMPLE_PHI
4484 || gimple_phi_num_args (use_stmt
) != 2
4485 || bb
->loop_father
!= outer_loop
)
4487 use_stmt_vinfo
= vinfo_for_stmt (use_stmt
);
4489 || STMT_VINFO_DEF_TYPE (use_stmt_vinfo
)
4490 != vect_double_reduction_def
)
4493 /* Create vector phi node for double reduction:
4494 vs1 = phi <vs0, vs2>
4495 vs1 was created previously in this function by a call to
4496 vect_get_vec_def_for_operand and is stored in
4498 vs2 is defined by INNER_PHI, the vectorized EXIT_PHI;
4499 vs0 is created here. */
4501 /* Create vector phi node. */
4502 vect_phi
= create_phi_node (vec_initial_def
, bb
);
4503 new_phi_vinfo
= new_stmt_vec_info (vect_phi
,
4504 loop_vec_info_for_loop (outer_loop
), NULL
);
4505 set_vinfo_for_stmt (vect_phi
, new_phi_vinfo
);
4507 /* Create vs0 - initial def of the double reduction phi. */
4508 preheader_arg
= PHI_ARG_DEF_FROM_EDGE (use_stmt
,
4509 loop_preheader_edge (outer_loop
));
4510 init_def
= get_initial_def_for_reduction (stmt
,
4511 preheader_arg
, NULL
);
4512 vect_phi_init
= vect_init_vector (use_stmt
, init_def
,
4515 /* Update phi node arguments with vs0 and vs2. */
4516 add_phi_arg (vect_phi
, vect_phi_init
,
4517 loop_preheader_edge (outer_loop
),
4519 add_phi_arg (vect_phi
, PHI_RESULT (inner_phi
),
4520 loop_latch_edge (outer_loop
), UNKNOWN_LOCATION
);
4521 if (dump_enabled_p ())
4523 dump_printf_loc (MSG_NOTE
, vect_location
,
4524 "created double reduction phi node: ");
4525 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, vect_phi
, 0);
4526 dump_printf (MSG_NOTE
, "\n");
4529 vect_phi_res
= PHI_RESULT (vect_phi
);
4531 /* Replace the use, i.e., set the correct vs1 in the regular
4532 reduction phi node. FORNOW, NCOPIES is always 1, so the
4533 loop is redundant. */
4534 use
= reduction_phi
;
4535 for (j
= 0; j
< ncopies
; j
++)
4537 edge pr_edge
= loop_preheader_edge (loop
);
4538 SET_PHI_ARG_DEF (use
, pr_edge
->dest_idx
, vect_phi_res
);
4539 use
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use
));
4546 if (nested_in_vect_loop
)
4555 /* Find the loop-closed-use at the loop exit of the original scalar
4556 result. (The reduction result is expected to have two immediate uses,
4557 one at the latch block, and one at the loop exit). For double
4558 reductions we are looking for exit phis of the outer loop. */
4559 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
4561 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
4563 if (!is_gimple_debug (USE_STMT (use_p
)))
4564 phis
.safe_push (USE_STMT (use_p
));
4568 if (double_reduc
&& gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
4570 tree phi_res
= PHI_RESULT (USE_STMT (use_p
));
4572 FOR_EACH_IMM_USE_FAST (phi_use_p
, phi_imm_iter
, phi_res
)
4574 if (!flow_bb_inside_loop_p (loop
,
4575 gimple_bb (USE_STMT (phi_use_p
)))
4576 && !is_gimple_debug (USE_STMT (phi_use_p
)))
4577 phis
.safe_push (USE_STMT (phi_use_p
));
4583 FOR_EACH_VEC_ELT (phis
, i
, exit_phi
)
4585 /* Replace the uses: */
4586 orig_name
= PHI_RESULT (exit_phi
);
4587 scalar_result
= scalar_results
[k
];
4588 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
4589 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
4590 SET_USE (use_p
, scalar_result
);
4596 scalar_results
.release ();
4597 inner_phis
.release ();
4598 new_phis
.release ();
4602 /* Function vectorizable_reduction.
4604 Check if STMT performs a reduction operation that can be vectorized.
4605 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4606 stmt to replace it, put it in VEC_STMT, and insert it at GSI.
4607 Return FALSE if not a vectorizable STMT, TRUE otherwise.
4609 This function also handles reduction idioms (patterns) that have been
4610 recognized in advance during vect_pattern_recog. In this case, STMT may be
4612 X = pattern_expr (arg0, arg1, ..., X)
4613 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
4614 sequence that had been detected and replaced by the pattern-stmt (STMT).
4616 In some cases of reduction patterns, the type of the reduction variable X is
4617 different than the type of the other arguments of STMT.
4618 In such cases, the vectype that is used when transforming STMT into a vector
4619 stmt is different than the vectype that is used to determine the
4620 vectorization factor, because it consists of a different number of elements
4621 than the actual number of elements that are being operated upon in parallel.
4623 For example, consider an accumulation of shorts into an int accumulator.
4624 On some targets it's possible to vectorize this pattern operating on 8
4625 shorts at a time (hence, the vectype for purposes of determining the
4626 vectorization factor should be V8HI); on the other hand, the vectype that
4627 is used to create the vector form is actually V4SI (the type of the result).
4629 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
4630 indicates what is the actual level of parallelism (V8HI in the example), so
4631 that the right vectorization factor would be derived. This vectype
4632 corresponds to the type of arguments to the reduction stmt, and should *NOT*
4633 be used to create the vectorized stmt. The right vectype for the vectorized
4634 stmt is obtained from the type of the result X:
4635 get_vectype_for_scalar_type (TREE_TYPE (X))
4637 This means that, contrary to "regular" reductions (or "regular" stmts in
4638 general), the following equation:
4639 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
4640 does *NOT* necessarily hold for reduction patterns. */
4643 vectorizable_reduction (gimple stmt
, gimple_stmt_iterator
*gsi
,
4644 gimple
*vec_stmt
, slp_tree slp_node
)
4648 tree loop_vec_def0
= NULL_TREE
, loop_vec_def1
= NULL_TREE
;
4649 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
4650 tree vectype_out
= STMT_VINFO_VECTYPE (stmt_info
);
4651 tree vectype_in
= NULL_TREE
;
4652 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
4653 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4654 enum tree_code code
, orig_code
, epilog_reduc_code
;
4655 enum machine_mode vec_mode
;
4657 optab optab
, reduc_optab
;
4658 tree new_temp
= NULL_TREE
;
4661 enum vect_def_type dt
;
4662 gimple new_phi
= NULL
;
4666 stmt_vec_info orig_stmt_info
;
4667 tree expr
= NULL_TREE
;
4671 stmt_vec_info prev_stmt_info
, prev_phi_info
;
4672 bool single_defuse_cycle
= false;
4673 tree reduc_def
= NULL_TREE
;
4674 gimple new_stmt
= NULL
;
4677 bool nested_cycle
= false, found_nested_cycle_def
= false;
4678 gimple reduc_def_stmt
= NULL
;
4679 /* The default is that the reduction variable is the last in statement. */
4680 int reduc_index
= 2;
4681 bool double_reduc
= false, dummy
;
4683 struct loop
* def_stmt_loop
, *outer_loop
= NULL
;
4685 gimple def_arg_stmt
;
4686 vec
<tree
> vec_oprnds0
= vNULL
;
4687 vec
<tree
> vec_oprnds1
= vNULL
;
4688 vec
<tree
> vect_defs
= vNULL
;
4689 vec
<gimple
> phis
= vNULL
;
4691 tree def0
, def1
, tem
, op0
, op1
= NULL_TREE
;
4693 /* In case of reduction chain we switch to the first stmt in the chain, but
4694 we don't update STMT_INFO, since only the last stmt is marked as reduction
4695 and has reduction properties. */
4696 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4697 stmt
= GROUP_FIRST_ELEMENT (stmt_info
);
4699 if (nested_in_vect_loop_p (loop
, stmt
))
4703 nested_cycle
= true;
4706 /* 1. Is vectorizable reduction? */
4707 /* Not supportable if the reduction variable is used in the loop, unless
4708 it's a reduction chain. */
4709 if (STMT_VINFO_RELEVANT (stmt_info
) > vect_used_in_outer
4710 && !GROUP_FIRST_ELEMENT (stmt_info
))
4713 /* Reductions that are not used even in an enclosing outer-loop,
4714 are expected to be "live" (used out of the loop). */
4715 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
4716 && !STMT_VINFO_LIVE_P (stmt_info
))
4719 /* Make sure it was already recognized as a reduction computation. */
4720 if (STMT_VINFO_DEF_TYPE (stmt_info
) != vect_reduction_def
4721 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_nested_cycle
)
4724 /* 2. Has this been recognized as a reduction pattern?
4726 Check if STMT represents a pattern that has been recognized
4727 in earlier analysis stages. For stmts that represent a pattern,
4728 the STMT_VINFO_RELATED_STMT field records the last stmt in
4729 the original sequence that constitutes the pattern. */
4731 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
4734 orig_stmt_info
= vinfo_for_stmt (orig_stmt
);
4735 gcc_assert (STMT_VINFO_IN_PATTERN_P (orig_stmt_info
));
4736 gcc_assert (!STMT_VINFO_IN_PATTERN_P (stmt_info
));
4739 /* 3. Check the operands of the operation. The first operands are defined
4740 inside the loop body. The last operand is the reduction variable,
4741 which is defined by the loop-header-phi. */
4743 gcc_assert (is_gimple_assign (stmt
));
4746 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
4748 case GIMPLE_SINGLE_RHS
:
4749 op_type
= TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
));
4750 if (op_type
== ternary_op
)
4752 tree rhs
= gimple_assign_rhs1 (stmt
);
4753 ops
[0] = TREE_OPERAND (rhs
, 0);
4754 ops
[1] = TREE_OPERAND (rhs
, 1);
4755 ops
[2] = TREE_OPERAND (rhs
, 2);
4756 code
= TREE_CODE (rhs
);
4762 case GIMPLE_BINARY_RHS
:
4763 code
= gimple_assign_rhs_code (stmt
);
4764 op_type
= TREE_CODE_LENGTH (code
);
4765 gcc_assert (op_type
== binary_op
);
4766 ops
[0] = gimple_assign_rhs1 (stmt
);
4767 ops
[1] = gimple_assign_rhs2 (stmt
);
4770 case GIMPLE_TERNARY_RHS
:
4771 code
= gimple_assign_rhs_code (stmt
);
4772 op_type
= TREE_CODE_LENGTH (code
);
4773 gcc_assert (op_type
== ternary_op
);
4774 ops
[0] = gimple_assign_rhs1 (stmt
);
4775 ops
[1] = gimple_assign_rhs2 (stmt
);
4776 ops
[2] = gimple_assign_rhs3 (stmt
);
4779 case GIMPLE_UNARY_RHS
:
4786 if (code
== COND_EXPR
&& slp_node
)
4789 scalar_dest
= gimple_assign_lhs (stmt
);
4790 scalar_type
= TREE_TYPE (scalar_dest
);
4791 if (!POINTER_TYPE_P (scalar_type
) && !INTEGRAL_TYPE_P (scalar_type
)
4792 && !SCALAR_FLOAT_TYPE_P (scalar_type
))
4795 /* Do not try to vectorize bit-precision reductions. */
4796 if ((TYPE_PRECISION (scalar_type
)
4797 != GET_MODE_PRECISION (TYPE_MODE (scalar_type
))))
4800 /* All uses but the last are expected to be defined in the loop.
4801 The last use is the reduction variable. In case of nested cycle this
4802 assumption is not true: we use reduc_index to record the index of the
4803 reduction variable. */
4804 for (i
= 0; i
< op_type
- 1; i
++)
4806 /* The condition of COND_EXPR is checked in vectorizable_condition(). */
4807 if (i
== 0 && code
== COND_EXPR
)
4810 is_simple_use
= vect_is_simple_use_1 (ops
[i
], stmt
, loop_vinfo
, NULL
,
4811 &def_stmt
, &def
, &dt
, &tem
);
4814 gcc_assert (is_simple_use
);
4816 if (dt
!= vect_internal_def
4817 && dt
!= vect_external_def
4818 && dt
!= vect_constant_def
4819 && dt
!= vect_induction_def
4820 && !(dt
== vect_nested_cycle
&& nested_cycle
))
4823 if (dt
== vect_nested_cycle
)
4825 found_nested_cycle_def
= true;
4826 reduc_def_stmt
= def_stmt
;
4831 is_simple_use
= vect_is_simple_use_1 (ops
[i
], stmt
, loop_vinfo
, NULL
,
4832 &def_stmt
, &def
, &dt
, &tem
);
4835 gcc_assert (is_simple_use
);
4836 if (!(dt
== vect_reduction_def
4837 || dt
== vect_nested_cycle
4838 || ((dt
== vect_internal_def
|| dt
== vect_external_def
4839 || dt
== vect_constant_def
|| dt
== vect_induction_def
)
4840 && nested_cycle
&& found_nested_cycle_def
)))
4842 /* For pattern recognized stmts, orig_stmt might be a reduction,
4843 but some helper statements for the pattern might not, or
4844 might be COND_EXPRs with reduction uses in the condition. */
4845 gcc_assert (orig_stmt
);
4848 if (!found_nested_cycle_def
)
4849 reduc_def_stmt
= def_stmt
;
4851 gcc_assert (gimple_code (reduc_def_stmt
) == GIMPLE_PHI
);
4853 gcc_assert (orig_stmt
== vect_is_simple_reduction (loop_vinfo
,
4859 gimple tmp
= vect_is_simple_reduction (loop_vinfo
, reduc_def_stmt
,
4860 !nested_cycle
, &dummy
);
4861 /* We changed STMT to be the first stmt in reduction chain, hence we
4862 check that in this case the first element in the chain is STMT. */
4863 gcc_assert (stmt
== tmp
4864 || GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp
)) == stmt
);
4867 if (STMT_VINFO_LIVE_P (vinfo_for_stmt (reduc_def_stmt
)))
4870 if (slp_node
|| PURE_SLP_STMT (stmt_info
))
4873 ncopies
= (LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4874 / TYPE_VECTOR_SUBPARTS (vectype_in
));
4876 gcc_assert (ncopies
>= 1);
4878 vec_mode
= TYPE_MODE (vectype_in
);
4880 if (code
== COND_EXPR
)
4882 if (!vectorizable_condition (stmt
, gsi
, NULL
, ops
[reduc_index
], 0, NULL
))
4884 if (dump_enabled_p ())
4885 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4886 "unsupported condition in reduction\n");
4893 /* 4. Supportable by target? */
4895 if (code
== LSHIFT_EXPR
|| code
== RSHIFT_EXPR
4896 || code
== LROTATE_EXPR
|| code
== RROTATE_EXPR
)
4898 /* Shifts and rotates are only supported by vectorizable_shifts,
4899 not vectorizable_reduction. */
4900 if (dump_enabled_p ())
4901 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4902 "unsupported shift or rotation.\n");
4906 /* 4.1. check support for the operation in the loop */
4907 optab
= optab_for_tree_code (code
, vectype_in
, optab_default
);
4910 if (dump_enabled_p ())
4911 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4917 if (optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
4919 if (dump_enabled_p ())
4920 dump_printf (MSG_NOTE
, "op not supported by target.\n");
4922 if (GET_MODE_SIZE (vec_mode
) != UNITS_PER_WORD
4923 || LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4924 < vect_min_worthwhile_factor (code
))
4927 if (dump_enabled_p ())
4928 dump_printf (MSG_NOTE
, "proceeding using word mode.\n");
4931 /* Worthwhile without SIMD support? */
4932 if (!VECTOR_MODE_P (TYPE_MODE (vectype_in
))
4933 && LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4934 < vect_min_worthwhile_factor (code
))
4936 if (dump_enabled_p ())
4937 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4938 "not worthwhile without SIMD support.\n");
4944 /* 4.2. Check support for the epilog operation.
4946 If STMT represents a reduction pattern, then the type of the
4947 reduction variable may be different than the type of the rest
4948 of the arguments. For example, consider the case of accumulation
4949 of shorts into an int accumulator; The original code:
4950 S1: int_a = (int) short_a;
4951 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
4954 STMT: int_acc = widen_sum <short_a, int_acc>
4957 1. The tree-code that is used to create the vector operation in the
4958 epilog code (that reduces the partial results) is not the
4959 tree-code of STMT, but is rather the tree-code of the original
4960 stmt from the pattern that STMT is replacing. I.e, in the example
4961 above we want to use 'widen_sum' in the loop, but 'plus' in the
4963 2. The type (mode) we use to check available target support
4964 for the vector operation to be created in the *epilog*, is
4965 determined by the type of the reduction variable (in the example
4966 above we'd check this: optab_handler (plus_optab, vect_int_mode])).
4967 However the type (mode) we use to check available target support
4968 for the vector operation to be created *inside the loop*, is
4969 determined by the type of the other arguments to STMT (in the
4970 example we'd check this: optab_handler (widen_sum_optab,
4973 This is contrary to "regular" reductions, in which the types of all
4974 the arguments are the same as the type of the reduction variable.
4975 For "regular" reductions we can therefore use the same vector type
4976 (and also the same tree-code) when generating the epilog code and
4977 when generating the code inside the loop. */
4981 /* This is a reduction pattern: get the vectype from the type of the
4982 reduction variable, and get the tree-code from orig_stmt. */
4983 orig_code
= gimple_assign_rhs_code (orig_stmt
);
4984 gcc_assert (vectype_out
);
4985 vec_mode
= TYPE_MODE (vectype_out
);
4989 /* Regular reduction: use the same vectype and tree-code as used for
4990 the vector code inside the loop can be used for the epilog code. */
4996 def_bb
= gimple_bb (reduc_def_stmt
);
4997 def_stmt_loop
= def_bb
->loop_father
;
4998 def_arg
= PHI_ARG_DEF_FROM_EDGE (reduc_def_stmt
,
4999 loop_preheader_edge (def_stmt_loop
));
5000 if (TREE_CODE (def_arg
) == SSA_NAME
5001 && (def_arg_stmt
= SSA_NAME_DEF_STMT (def_arg
))
5002 && gimple_code (def_arg_stmt
) == GIMPLE_PHI
5003 && flow_bb_inside_loop_p (outer_loop
, gimple_bb (def_arg_stmt
))
5004 && vinfo_for_stmt (def_arg_stmt
)
5005 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_arg_stmt
))
5006 == vect_double_reduction_def
)
5007 double_reduc
= true;
5010 epilog_reduc_code
= ERROR_MARK
;
5011 if (reduction_code_for_scalar_code (orig_code
, &epilog_reduc_code
))
5013 reduc_optab
= optab_for_tree_code (epilog_reduc_code
, vectype_out
,
5017 if (dump_enabled_p ())
5018 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5019 "no optab for reduction.\n");
5021 epilog_reduc_code
= ERROR_MARK
;
5025 && optab_handler (reduc_optab
, vec_mode
) == CODE_FOR_nothing
)
5027 if (dump_enabled_p ())
5028 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5029 "reduc op not supported by target.\n");
5031 epilog_reduc_code
= ERROR_MARK
;
5036 if (!nested_cycle
|| double_reduc
)
5038 if (dump_enabled_p ())
5039 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5040 "no reduc code for scalar code.\n");
5046 if (double_reduc
&& ncopies
> 1)
5048 if (dump_enabled_p ())
5049 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5050 "multiple types in double reduction\n");
5055 /* In case of widenning multiplication by a constant, we update the type
5056 of the constant to be the type of the other operand. We check that the
5057 constant fits the type in the pattern recognition pass. */
5058 if (code
== DOT_PROD_EXPR
5059 && !types_compatible_p (TREE_TYPE (ops
[0]), TREE_TYPE (ops
[1])))
5061 if (TREE_CODE (ops
[0]) == INTEGER_CST
)
5062 ops
[0] = fold_convert (TREE_TYPE (ops
[1]), ops
[0]);
5063 else if (TREE_CODE (ops
[1]) == INTEGER_CST
)
5064 ops
[1] = fold_convert (TREE_TYPE (ops
[0]), ops
[1]);
5067 if (dump_enabled_p ())
5068 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5069 "invalid types in dot-prod\n");
5075 if (!vec_stmt
) /* transformation not required. */
5077 if (!vect_model_reduction_cost (stmt_info
, epilog_reduc_code
, ncopies
))
5079 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
5085 if (dump_enabled_p ())
5086 dump_printf_loc (MSG_NOTE
, vect_location
, "transform reduction.\n");
5088 /* FORNOW: Multiple types are not supported for condition. */
5089 if (code
== COND_EXPR
)
5090 gcc_assert (ncopies
== 1);
5092 /* Create the destination vector */
5093 vec_dest
= vect_create_destination_var (scalar_dest
, vectype_out
);
5095 /* In case the vectorization factor (VF) is bigger than the number
5096 of elements that we can fit in a vectype (nunits), we have to generate
5097 more than one vector stmt - i.e - we need to "unroll" the
5098 vector stmt by a factor VF/nunits. For more details see documentation
5099 in vectorizable_operation. */
5101 /* If the reduction is used in an outer loop we need to generate
5102 VF intermediate results, like so (e.g. for ncopies=2):
5107 (i.e. we generate VF results in 2 registers).
5108 In this case we have a separate def-use cycle for each copy, and therefore
5109 for each copy we get the vector def for the reduction variable from the
5110 respective phi node created for this copy.
5112 Otherwise (the reduction is unused in the loop nest), we can combine
5113 together intermediate results, like so (e.g. for ncopies=2):
5117 (i.e. we generate VF/2 results in a single register).
5118 In this case for each copy we get the vector def for the reduction variable
5119 from the vectorized reduction operation generated in the previous iteration.
5122 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
)
5124 single_defuse_cycle
= true;
5128 epilog_copies
= ncopies
;
5130 prev_stmt_info
= NULL
;
5131 prev_phi_info
= NULL
;
5134 vec_num
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
5135 gcc_assert (TYPE_VECTOR_SUBPARTS (vectype_out
)
5136 == TYPE_VECTOR_SUBPARTS (vectype_in
));
5141 vec_oprnds0
.create (1);
5142 if (op_type
== ternary_op
)
5143 vec_oprnds1
.create (1);
5146 phis
.create (vec_num
);
5147 vect_defs
.create (vec_num
);
5149 vect_defs
.quick_push (NULL_TREE
);
5151 for (j
= 0; j
< ncopies
; j
++)
5153 if (j
== 0 || !single_defuse_cycle
)
5155 for (i
= 0; i
< vec_num
; i
++)
5157 /* Create the reduction-phi that defines the reduction
5159 new_phi
= create_phi_node (vec_dest
, loop
->header
);
5160 set_vinfo_for_stmt (new_phi
,
5161 new_stmt_vec_info (new_phi
, loop_vinfo
,
5163 if (j
== 0 || slp_node
)
5164 phis
.quick_push (new_phi
);
5168 if (code
== COND_EXPR
)
5170 gcc_assert (!slp_node
);
5171 vectorizable_condition (stmt
, gsi
, vec_stmt
,
5172 PHI_RESULT (phis
[0]),
5174 /* Multiple types are not supported for condition. */
5181 op0
= ops
[!reduc_index
];
5182 if (op_type
== ternary_op
)
5184 if (reduc_index
== 0)
5191 vect_get_vec_defs (op0
, op1
, stmt
, &vec_oprnds0
, &vec_oprnds1
,
5195 loop_vec_def0
= vect_get_vec_def_for_operand (ops
[!reduc_index
],
5197 vec_oprnds0
.quick_push (loop_vec_def0
);
5198 if (op_type
== ternary_op
)
5200 loop_vec_def1
= vect_get_vec_def_for_operand (op1
, stmt
,
5202 vec_oprnds1
.quick_push (loop_vec_def1
);
5210 enum vect_def_type dt
;
5214 vect_is_simple_use (ops
[!reduc_index
], stmt
, loop_vinfo
, NULL
,
5215 &dummy_stmt
, &dummy
, &dt
);
5216 loop_vec_def0
= vect_get_vec_def_for_stmt_copy (dt
,
5218 vec_oprnds0
[0] = loop_vec_def0
;
5219 if (op_type
== ternary_op
)
5221 vect_is_simple_use (op1
, stmt
, loop_vinfo
, NULL
, &dummy_stmt
,
5223 loop_vec_def1
= vect_get_vec_def_for_stmt_copy (dt
,
5225 vec_oprnds1
[0] = loop_vec_def1
;
5229 if (single_defuse_cycle
)
5230 reduc_def
= gimple_assign_lhs (new_stmt
);
5232 STMT_VINFO_RELATED_STMT (prev_phi_info
) = new_phi
;
5235 FOR_EACH_VEC_ELT (vec_oprnds0
, i
, def0
)
5238 reduc_def
= PHI_RESULT (phis
[i
]);
5241 if (!single_defuse_cycle
|| j
== 0)
5242 reduc_def
= PHI_RESULT (new_phi
);
5245 def1
= ((op_type
== ternary_op
)
5246 ? vec_oprnds1
[i
] : NULL
);
5247 if (op_type
== binary_op
)
5249 if (reduc_index
== 0)
5250 expr
= build2 (code
, vectype_out
, reduc_def
, def0
);
5252 expr
= build2 (code
, vectype_out
, def0
, reduc_def
);
5256 if (reduc_index
== 0)
5257 expr
= build3 (code
, vectype_out
, reduc_def
, def0
, def1
);
5260 if (reduc_index
== 1)
5261 expr
= build3 (code
, vectype_out
, def0
, reduc_def
, def1
);
5263 expr
= build3 (code
, vectype_out
, def0
, def1
, reduc_def
);
5267 new_stmt
= gimple_build_assign (vec_dest
, expr
);
5268 new_temp
= make_ssa_name (vec_dest
, new_stmt
);
5269 gimple_assign_set_lhs (new_stmt
, new_temp
);
5270 vect_finish_stmt_generation (stmt
, new_stmt
, gsi
);
5274 SLP_TREE_VEC_STMTS (slp_node
).quick_push (new_stmt
);
5275 vect_defs
.quick_push (new_temp
);
5278 vect_defs
[0] = new_temp
;
5285 STMT_VINFO_VEC_STMT (stmt_info
) = *vec_stmt
= new_stmt
;
5287 STMT_VINFO_RELATED_STMT (prev_stmt_info
) = new_stmt
;
5289 prev_stmt_info
= vinfo_for_stmt (new_stmt
);
5290 prev_phi_info
= vinfo_for_stmt (new_phi
);
5293 /* Finalize the reduction-phi (set its arguments) and create the
5294 epilog reduction code. */
5295 if ((!single_defuse_cycle
|| code
== COND_EXPR
) && !slp_node
)
5297 new_temp
= gimple_assign_lhs (*vec_stmt
);
5298 vect_defs
[0] = new_temp
;
5301 vect_create_epilog_for_reduction (vect_defs
, stmt
, epilog_copies
,
5302 epilog_reduc_code
, phis
, reduc_index
,
5303 double_reduc
, slp_node
);
5306 vect_defs
.release ();
5307 vec_oprnds0
.release ();
5308 vec_oprnds1
.release ();
5313 /* Function vect_min_worthwhile_factor.
5315 For a loop where we could vectorize the operation indicated by CODE,
5316 return the minimum vectorization factor that makes it worthwhile
5317 to use generic vectors. */
5319 vect_min_worthwhile_factor (enum tree_code code
)
5340 /* Function vectorizable_induction
5342 Check if PHI performs an induction computation that can be vectorized.
5343 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
5344 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
5345 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5348 vectorizable_induction (gimple phi
, gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
5351 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
5352 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
5353 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
5354 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5355 int nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
5356 int ncopies
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) / nunits
;
5359 gcc_assert (ncopies
>= 1);
5360 /* FORNOW. These restrictions should be relaxed. */
5361 if (nested_in_vect_loop_p (loop
, phi
))
5363 imm_use_iterator imm_iter
;
5364 use_operand_p use_p
;
5371 if (dump_enabled_p ())
5372 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5373 "multiple types in nested loop.\n");
5378 latch_e
= loop_latch_edge (loop
->inner
);
5379 loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
5380 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
5382 if (!flow_bb_inside_loop_p (loop
->inner
,
5383 gimple_bb (USE_STMT (use_p
))))
5385 exit_phi
= USE_STMT (use_p
);
5391 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
5392 if (!(STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
5393 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
)))
5395 if (dump_enabled_p ())
5396 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5397 "inner-loop induction only used outside "
5398 "of the outer vectorized loop.\n");
5404 if (!STMT_VINFO_RELEVANT_P (stmt_info
))
5407 /* FORNOW: SLP not supported. */
5408 if (STMT_SLP_TYPE (stmt_info
))
5411 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
);
5413 if (gimple_code (phi
) != GIMPLE_PHI
)
5416 if (!vec_stmt
) /* transformation not required. */
5418 STMT_VINFO_TYPE (stmt_info
) = induc_vec_info_type
;
5419 if (dump_enabled_p ())
5420 dump_printf_loc (MSG_NOTE
, vect_location
,
5421 "=== vectorizable_induction ===\n");
5422 vect_model_induction_cost (stmt_info
, ncopies
);
5428 if (dump_enabled_p ())
5429 dump_printf_loc (MSG_NOTE
, vect_location
, "transform induction phi.\n");
5431 vec_def
= get_initial_def_for_induction (phi
);
5432 *vec_stmt
= SSA_NAME_DEF_STMT (vec_def
);
5436 /* Function vectorizable_live_operation.
5438 STMT computes a value that is used outside the loop. Check if
5439 it can be supported. */
5442 vectorizable_live_operation (gimple stmt
,
5443 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
5446 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
5447 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
5448 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5454 enum vect_def_type dt
;
5455 enum tree_code code
;
5456 enum gimple_rhs_class rhs_class
;
5458 gcc_assert (STMT_VINFO_LIVE_P (stmt_info
));
5460 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_reduction_def
)
5463 if (!is_gimple_assign (stmt
))
5465 if (gimple_call_internal_p (stmt
)
5466 && gimple_call_internal_fn (stmt
) == IFN_GOMP_SIMD_LANE
5467 && gimple_call_lhs (stmt
)
5469 && TREE_CODE (gimple_call_arg (stmt
, 0)) == SSA_NAME
5471 == SSA_NAME_VAR (gimple_call_arg (stmt
, 0)))
5473 edge e
= single_exit (loop
);
5474 basic_block merge_bb
= e
->dest
;
5475 imm_use_iterator imm_iter
;
5476 use_operand_p use_p
;
5477 tree lhs
= gimple_call_lhs (stmt
);
5479 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
5481 gimple use_stmt
= USE_STMT (use_p
);
5482 if (gimple_code (use_stmt
) == GIMPLE_PHI
5483 || gimple_bb (use_stmt
) == merge_bb
)
5488 = build_int_cst (unsigned_type_node
,
5489 loop_vinfo
->vectorization_factor
- 1);
5490 SET_PHI_ARG_DEF (use_stmt
, e
->dest_idx
, vfm1
);
5500 if (TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
5503 /* FORNOW. CHECKME. */
5504 if (nested_in_vect_loop_p (loop
, stmt
))
5507 code
= gimple_assign_rhs_code (stmt
);
5508 op_type
= TREE_CODE_LENGTH (code
);
5509 rhs_class
= get_gimple_rhs_class (code
);
5510 gcc_assert (rhs_class
!= GIMPLE_UNARY_RHS
|| op_type
== unary_op
);
5511 gcc_assert (rhs_class
!= GIMPLE_BINARY_RHS
|| op_type
== binary_op
);
5513 /* FORNOW: support only if all uses are invariant. This means
5514 that the scalar operations can remain in place, unvectorized.
5515 The original last scalar value that they compute will be used. */
5517 for (i
= 0; i
< op_type
; i
++)
5519 if (rhs_class
== GIMPLE_SINGLE_RHS
)
5520 op
= TREE_OPERAND (gimple_op (stmt
, 1), i
);
5522 op
= gimple_op (stmt
, i
+ 1);
5524 && !vect_is_simple_use (op
, stmt
, loop_vinfo
, NULL
, &def_stmt
, &def
,
5527 if (dump_enabled_p ())
5528 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5529 "use not simple.\n");
5533 if (dt
!= vect_external_def
&& dt
!= vect_constant_def
)
5537 /* No transformation is required for the cases we currently support. */
5541 /* Kill any debug uses outside LOOP of SSA names defined in STMT. */
5544 vect_loop_kill_debug_uses (struct loop
*loop
, gimple stmt
)
5546 ssa_op_iter op_iter
;
5547 imm_use_iterator imm_iter
;
5548 def_operand_p def_p
;
5551 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
5553 FOR_EACH_IMM_USE_STMT (ustmt
, imm_iter
, DEF_FROM_PTR (def_p
))
5557 if (!is_gimple_debug (ustmt
))
5560 bb
= gimple_bb (ustmt
);
5562 if (!flow_bb_inside_loop_p (loop
, bb
))
5564 if (gimple_debug_bind_p (ustmt
))
5566 if (dump_enabled_p ())
5567 dump_printf_loc (MSG_NOTE
, vect_location
,
5568 "killing debug use\n");
5570 gimple_debug_bind_reset_value (ustmt
);
5571 update_stmt (ustmt
);
5580 /* Function vect_transform_loop.
5582 The analysis phase has determined that the loop is vectorizable.
5583 Vectorize the loop - created vectorized stmts to replace the scalar
5584 stmts in the loop, and update the loop exit condition. */
5587 vect_transform_loop (loop_vec_info loop_vinfo
)
5589 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5590 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
5591 int nbbs
= loop
->num_nodes
;
5592 gimple_stmt_iterator si
;
5595 int vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
5597 bool slp_scheduled
= false;
5598 unsigned int nunits
;
5599 gimple stmt
, pattern_stmt
;
5600 gimple_seq pattern_def_seq
= NULL
;
5601 gimple_stmt_iterator pattern_def_si
= gsi_none ();
5602 bool transform_pattern_stmt
= false;
5603 bool check_profitability
= false;
5605 /* Record number of iterations before we started tampering with the profile. */
5606 gcov_type expected_iterations
= expected_loop_iterations_unbounded (loop
);
5608 if (dump_enabled_p ())
5609 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vec_transform_loop ===\n");
5611 /* If profile is inprecise, we have chance to fix it up. */
5612 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
5613 expected_iterations
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
5615 /* Use the more conservative vectorization threshold. If the number
5616 of iterations is constant assume the cost check has been performed
5617 by our caller. If the threshold makes all loops profitable that
5618 run at least the vectorization factor number of times checking
5619 is pointless, too. */
5620 th
= ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND
)
5621 * LOOP_VINFO_VECT_FACTOR (loop_vinfo
)) - 1);
5622 th
= MAX (th
, LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo
));
5623 if (th
>= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) - 1
5624 && !LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
5626 if (dump_enabled_p ())
5627 dump_printf_loc (MSG_NOTE
, vect_location
,
5628 "Profitability threshold is %d loop iterations.\n",
5630 check_profitability
= true;
5633 /* Version the loop first, if required, so the profitability check
5636 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
5637 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
5639 vect_loop_versioning (loop_vinfo
, th
, check_profitability
);
5640 check_profitability
= false;
5643 /* Peel the loop if there are data refs with unknown alignment.
5644 Only one data ref with unknown store is allowed. */
5646 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
))
5648 vect_do_peeling_for_alignment (loop_vinfo
, th
, check_profitability
);
5649 check_profitability
= false;
5652 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
5653 compile time constant), or it is a constant that doesn't divide by the
5654 vectorization factor, then an epilog loop needs to be created.
5655 We therefore duplicate the loop: the original loop will be vectorized,
5656 and will compute the first (n/VF) iterations. The second copy of the loop
5657 will remain scalar and will compute the remaining (n%VF) iterations.
5658 (VF is the vectorization factor). */
5660 if ((int) tree_ctz (LOOP_VINFO_NITERS (loop_vinfo
))
5661 < exact_log2 (vectorization_factor
)
5662 || LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
))
5663 vect_do_peeling_for_loop_bound (loop_vinfo
, &ratio
,
5664 th
, check_profitability
);
5665 else if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
5666 ratio
= build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo
)),
5667 LOOP_VINFO_INT_NITERS (loop_vinfo
) / vectorization_factor
);
5670 tree ni_name
, ratio_mult_vf
;
5671 vect_generate_tmps_on_preheader (loop_vinfo
, &ni_name
, &ratio_mult_vf
,
5675 /* 1) Make sure the loop header has exactly two entries
5676 2) Make sure we have a preheader basic block. */
5678 gcc_assert (EDGE_COUNT (loop
->header
->preds
) == 2);
5680 split_edge (loop_preheader_edge (loop
));
5682 /* FORNOW: the vectorizer supports only loops which body consist
5683 of one basic block (header + empty latch). When the vectorizer will
5684 support more involved loop forms, the order by which the BBs are
5685 traversed need to be reconsidered. */
5687 for (i
= 0; i
< nbbs
; i
++)
5689 basic_block bb
= bbs
[i
];
5690 stmt_vec_info stmt_info
;
5693 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
5695 phi
= gsi_stmt (si
);
5696 if (dump_enabled_p ())
5698 dump_printf_loc (MSG_NOTE
, vect_location
,
5699 "------>vectorizing phi: ");
5700 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
5701 dump_printf (MSG_NOTE
, "\n");
5703 stmt_info
= vinfo_for_stmt (phi
);
5707 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
5708 vect_loop_kill_debug_uses (loop
, phi
);
5710 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
5711 && !STMT_VINFO_LIVE_P (stmt_info
))
5714 if ((TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
))
5715 != (unsigned HOST_WIDE_INT
) vectorization_factor
)
5716 && dump_enabled_p ())
5717 dump_printf_loc (MSG_NOTE
, vect_location
, "multiple-types.\n");
5719 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
5721 if (dump_enabled_p ())
5722 dump_printf_loc (MSG_NOTE
, vect_location
, "transform phi.\n");
5723 vect_transform_stmt (phi
, NULL
, NULL
, NULL
, NULL
);
5727 pattern_stmt
= NULL
;
5728 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
) || transform_pattern_stmt
;)
5732 if (transform_pattern_stmt
)
5733 stmt
= pattern_stmt
;
5736 stmt
= gsi_stmt (si
);
5737 /* During vectorization remove existing clobber stmts. */
5738 if (gimple_clobber_p (stmt
))
5740 unlink_stmt_vdef (stmt
);
5741 gsi_remove (&si
, true);
5742 release_defs (stmt
);
5747 if (dump_enabled_p ())
5749 dump_printf_loc (MSG_NOTE
, vect_location
,
5750 "------>vectorizing statement: ");
5751 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
5752 dump_printf (MSG_NOTE
, "\n");
5755 stmt_info
= vinfo_for_stmt (stmt
);
5757 /* vector stmts created in the outer-loop during vectorization of
5758 stmts in an inner-loop may not have a stmt_info, and do not
5759 need to be vectorized. */
5766 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
5767 vect_loop_kill_debug_uses (loop
, stmt
);
5769 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
5770 && !STMT_VINFO_LIVE_P (stmt_info
))
5772 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
5773 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
5774 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
5775 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
5777 stmt
= pattern_stmt
;
5778 stmt_info
= vinfo_for_stmt (stmt
);
5786 else if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
5787 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
5788 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
5789 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
5790 transform_pattern_stmt
= true;
5792 /* If pattern statement has def stmts, vectorize them too. */
5793 if (is_pattern_stmt_p (stmt_info
))
5795 if (pattern_def_seq
== NULL
)
5797 pattern_def_seq
= STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
);
5798 pattern_def_si
= gsi_start (pattern_def_seq
);
5800 else if (!gsi_end_p (pattern_def_si
))
5801 gsi_next (&pattern_def_si
);
5802 if (pattern_def_seq
!= NULL
)
5804 gimple pattern_def_stmt
= NULL
;
5805 stmt_vec_info pattern_def_stmt_info
= NULL
;
5807 while (!gsi_end_p (pattern_def_si
))
5809 pattern_def_stmt
= gsi_stmt (pattern_def_si
);
5810 pattern_def_stmt_info
5811 = vinfo_for_stmt (pattern_def_stmt
);
5812 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info
)
5813 || STMT_VINFO_LIVE_P (pattern_def_stmt_info
))
5815 gsi_next (&pattern_def_si
);
5818 if (!gsi_end_p (pattern_def_si
))
5820 if (dump_enabled_p ())
5822 dump_printf_loc (MSG_NOTE
, vect_location
,
5823 "==> vectorizing pattern def "
5825 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
5826 pattern_def_stmt
, 0);
5827 dump_printf (MSG_NOTE
, "\n");
5830 stmt
= pattern_def_stmt
;
5831 stmt_info
= pattern_def_stmt_info
;
5835 pattern_def_si
= gsi_none ();
5836 transform_pattern_stmt
= false;
5840 transform_pattern_stmt
= false;
5843 gcc_assert (STMT_VINFO_VECTYPE (stmt_info
));
5844 nunits
= (unsigned int) TYPE_VECTOR_SUBPARTS (
5845 STMT_VINFO_VECTYPE (stmt_info
));
5846 if (!STMT_SLP_TYPE (stmt_info
)
5847 && nunits
!= (unsigned int) vectorization_factor
5848 && dump_enabled_p ())
5849 /* For SLP VF is set according to unrolling factor, and not to
5850 vector size, hence for SLP this print is not valid. */
5851 dump_printf_loc (MSG_NOTE
, vect_location
,
5852 "multiple-types.\n");
5854 /* SLP. Schedule all the SLP instances when the first SLP stmt is
5856 if (STMT_SLP_TYPE (stmt_info
))
5860 slp_scheduled
= true;
5862 if (dump_enabled_p ())
5863 dump_printf_loc (MSG_NOTE
, vect_location
,
5864 "=== scheduling SLP instances ===\n");
5866 vect_schedule_slp (loop_vinfo
, NULL
);
5869 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
5870 if (!vinfo_for_stmt (stmt
) || PURE_SLP_STMT (stmt_info
))
5872 if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
5874 pattern_def_seq
= NULL
;
5881 /* -------- vectorize statement ------------ */
5882 if (dump_enabled_p ())
5883 dump_printf_loc (MSG_NOTE
, vect_location
, "transform statement.\n");
5885 grouped_store
= false;
5886 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, NULL
, NULL
);
5889 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
5891 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
5892 interleaving chain was completed - free all the stores in
5895 vect_remove_stores (GROUP_FIRST_ELEMENT (stmt_info
));
5900 /* Free the attached stmt_vec_info and remove the stmt. */
5901 gimple store
= gsi_stmt (si
);
5902 free_stmt_vec_info (store
);
5903 unlink_stmt_vdef (store
);
5904 gsi_remove (&si
, true);
5905 release_defs (store
);
5910 if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
5912 pattern_def_seq
= NULL
;
5918 slpeel_make_loop_iterate_ntimes (loop
, ratio
);
5920 /* Reduce loop iterations by the vectorization factor. */
5921 scale_loop_profile (loop
, GCOV_COMPUTE_SCALE (1, vectorization_factor
),
5922 expected_iterations
/ vectorization_factor
);
5923 loop
->nb_iterations_upper_bound
5924 = loop
->nb_iterations_upper_bound
.udiv (double_int::from_uhwi (vectorization_factor
),
5926 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
5927 && loop
->nb_iterations_upper_bound
!= double_int_zero
)
5928 loop
->nb_iterations_upper_bound
= loop
->nb_iterations_upper_bound
- double_int_one
;
5929 if (loop
->any_estimate
)
5931 loop
->nb_iterations_estimate
5932 = loop
->nb_iterations_estimate
.udiv (double_int::from_uhwi (vectorization_factor
),
5934 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
5935 && loop
->nb_iterations_estimate
!= double_int_zero
)
5936 loop
->nb_iterations_estimate
= loop
->nb_iterations_estimate
- double_int_one
;
5939 if (dump_enabled_p ())
5941 dump_printf_loc (MSG_NOTE
, vect_location
,
5942 "LOOP VECTORIZED\n");
5944 dump_printf_loc (MSG_NOTE
, vect_location
,
5945 "OUTER LOOP VECTORIZED\n");
5946 dump_printf (MSG_NOTE
, "\n");