2 Copyright (C) 2003-2014 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com> and
4 Ira Rosen <irar@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
28 #include "stor-layout.h"
29 #include "basic-block.h"
30 #include "gimple-pretty-print.h"
31 #include "tree-ssa-alias.h"
32 #include "internal-fn.h"
33 #include "gimple-expr.h"
37 #include "gimple-iterator.h"
38 #include "gimplify-me.h"
39 #include "gimple-ssa.h"
40 #include "tree-phinodes.h"
41 #include "ssa-iterators.h"
42 #include "stringpool.h"
43 #include "tree-ssanames.h"
44 #include "tree-ssa-loop-ivopts.h"
45 #include "tree-ssa-loop-manip.h"
46 #include "tree-ssa-loop-niter.h"
47 #include "tree-pass.h"
53 #include "diagnostic-core.h"
54 #include "tree-chrec.h"
55 #include "tree-scalar-evolution.h"
56 #include "tree-vectorizer.h"
59 /* Loop Vectorization Pass.
61 This pass tries to vectorize loops.
63 For example, the vectorizer transforms the following simple loop:
65 short a[N]; short b[N]; short c[N]; int i;
71 as if it was manually vectorized by rewriting the source code into:
73 typedef int __attribute__((mode(V8HI))) v8hi;
74 short a[N]; short b[N]; short c[N]; int i;
75 v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
78 for (i=0; i<N/8; i++){
85 The main entry to this pass is vectorize_loops(), in which
86 the vectorizer applies a set of analyses on a given set of loops,
87 followed by the actual vectorization transformation for the loops that
88 had successfully passed the analysis phase.
89 Throughout this pass we make a distinction between two types of
90 data: scalars (which are represented by SSA_NAMES), and memory references
91 ("data-refs"). These two types of data require different handling both
92 during analysis and transformation. The types of data-refs that the
93 vectorizer currently supports are ARRAY_REFS which base is an array DECL
94 (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
95 accesses are required to have a simple (consecutive) access pattern.
99 The driver for the analysis phase is vect_analyze_loop().
100 It applies a set of analyses, some of which rely on the scalar evolution
101 analyzer (scev) developed by Sebastian Pop.
103 During the analysis phase the vectorizer records some information
104 per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
105 loop, as well as general information about the loop as a whole, which is
106 recorded in a "loop_vec_info" struct attached to each loop.
108 Transformation phase:
109 =====================
110 The loop transformation phase scans all the stmts in the loop, and
111 creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
112 the loop that needs to be vectorized. It inserts the vector code sequence
113 just before the scalar stmt S, and records a pointer to the vector code
114 in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
115 attached to S). This pointer will be used for the vectorization of following
116 stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
117 otherwise, we rely on dead code elimination for removing it.
119 For example, say stmt S1 was vectorized into stmt VS1:
122 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
125 To vectorize stmt S2, the vectorizer first finds the stmt that defines
126 the operand 'b' (S1), and gets the relevant vector def 'vb' from the
127 vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
128 resulting sequence would be:
131 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
133 S2: a = b; STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
135 Operands that are not SSA_NAMEs, are data-refs that appear in
136 load/store operations (like 'x[i]' in S1), and are handled differently.
140 Currently the only target specific information that is used is the
141 size of the vector (in bytes) - "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD".
142 Targets that can support different sizes of vectors, for now will need
143 to specify one value for "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD". More
144 flexibility will be added in the future.
146 Since we only vectorize operations which vector form can be
147 expressed using existing tree codes, to verify that an operation is
148 supported, the vectorizer checks the relevant optab at the relevant
149 machine_mode (e.g, optab_handler (add_optab, V8HImode)). If
150 the value found is CODE_FOR_nothing, then there's no target support, and
151 we can't vectorize the stmt.
153 For additional information on this project see:
154 http://gcc.gnu.org/projects/tree-ssa/vectorization.html
157 static void vect_estimate_min_profitable_iters (loop_vec_info
, int *, int *);
159 /* Function vect_determine_vectorization_factor
161 Determine the vectorization factor (VF). VF is the number of data elements
162 that are operated upon in parallel in a single iteration of the vectorized
163 loop. For example, when vectorizing a loop that operates on 4byte elements,
164 on a target with vector size (VS) 16byte, the VF is set to 4, since 4
165 elements can fit in a single vector register.
167 We currently support vectorization of loops in which all types operated upon
168 are of the same size. Therefore this function currently sets VF according to
169 the size of the types operated upon, and fails if there are multiple sizes
172 VF is also the factor by which the loop iterations are strip-mined, e.g.:
179 for (i=0; i<N; i+=VF){
180 a[i:VF] = b[i:VF] + c[i:VF];
185 vect_determine_vectorization_factor (loop_vec_info loop_vinfo
)
187 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
188 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
189 int nbbs
= loop
->num_nodes
;
190 gimple_stmt_iterator si
;
191 unsigned int vectorization_factor
= 0;
196 stmt_vec_info stmt_info
;
199 gimple stmt
, pattern_stmt
= NULL
;
200 gimple_seq pattern_def_seq
= NULL
;
201 gimple_stmt_iterator pattern_def_si
= gsi_none ();
202 bool analyze_pattern_stmt
= false;
204 if (dump_enabled_p ())
205 dump_printf_loc (MSG_NOTE
, vect_location
,
206 "=== vect_determine_vectorization_factor ===\n");
208 for (i
= 0; i
< nbbs
; i
++)
210 basic_block bb
= bbs
[i
];
212 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
215 stmt_info
= vinfo_for_stmt (phi
);
216 if (dump_enabled_p ())
218 dump_printf_loc (MSG_NOTE
, vect_location
, "==> examining phi: ");
219 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
220 dump_printf (MSG_NOTE
, "\n");
223 gcc_assert (stmt_info
);
225 if (STMT_VINFO_RELEVANT_P (stmt_info
))
227 gcc_assert (!STMT_VINFO_VECTYPE (stmt_info
));
228 scalar_type
= TREE_TYPE (PHI_RESULT (phi
));
230 if (dump_enabled_p ())
232 dump_printf_loc (MSG_NOTE
, vect_location
,
233 "get vectype for scalar type: ");
234 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
235 dump_printf (MSG_NOTE
, "\n");
238 vectype
= get_vectype_for_scalar_type (scalar_type
);
241 if (dump_enabled_p ())
243 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
244 "not vectorized: unsupported "
246 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
248 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
252 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
254 if (dump_enabled_p ())
256 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
257 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vectype
);
258 dump_printf (MSG_NOTE
, "\n");
261 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
262 if (dump_enabled_p ())
263 dump_printf_loc (MSG_NOTE
, vect_location
, "nunits = %d\n",
266 if (!vectorization_factor
267 || (nunits
> vectorization_factor
))
268 vectorization_factor
= nunits
;
272 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
) || analyze_pattern_stmt
;)
276 if (analyze_pattern_stmt
)
279 stmt
= gsi_stmt (si
);
281 stmt_info
= vinfo_for_stmt (stmt
);
283 if (dump_enabled_p ())
285 dump_printf_loc (MSG_NOTE
, vect_location
,
286 "==> examining statement: ");
287 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
288 dump_printf (MSG_NOTE
, "\n");
291 gcc_assert (stmt_info
);
293 /* Skip stmts which do not need to be vectorized. */
294 if ((!STMT_VINFO_RELEVANT_P (stmt_info
)
295 && !STMT_VINFO_LIVE_P (stmt_info
))
296 || gimple_clobber_p (stmt
))
298 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
299 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
300 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
301 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
304 stmt_info
= vinfo_for_stmt (pattern_stmt
);
305 if (dump_enabled_p ())
307 dump_printf_loc (MSG_NOTE
, vect_location
,
308 "==> examining pattern statement: ");
309 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
310 dump_printf (MSG_NOTE
, "\n");
315 if (dump_enabled_p ())
316 dump_printf_loc (MSG_NOTE
, vect_location
, "skip.\n");
321 else if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
322 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
323 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
324 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
325 analyze_pattern_stmt
= true;
327 /* If a pattern statement has def stmts, analyze them too. */
328 if (is_pattern_stmt_p (stmt_info
))
330 if (pattern_def_seq
== NULL
)
332 pattern_def_seq
= STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
);
333 pattern_def_si
= gsi_start (pattern_def_seq
);
335 else if (!gsi_end_p (pattern_def_si
))
336 gsi_next (&pattern_def_si
);
337 if (pattern_def_seq
!= NULL
)
339 gimple pattern_def_stmt
= NULL
;
340 stmt_vec_info pattern_def_stmt_info
= NULL
;
342 while (!gsi_end_p (pattern_def_si
))
344 pattern_def_stmt
= gsi_stmt (pattern_def_si
);
345 pattern_def_stmt_info
346 = vinfo_for_stmt (pattern_def_stmt
);
347 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info
)
348 || STMT_VINFO_LIVE_P (pattern_def_stmt_info
))
350 gsi_next (&pattern_def_si
);
353 if (!gsi_end_p (pattern_def_si
))
355 if (dump_enabled_p ())
357 dump_printf_loc (MSG_NOTE
, vect_location
,
358 "==> examining pattern def stmt: ");
359 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
360 pattern_def_stmt
, 0);
361 dump_printf (MSG_NOTE
, "\n");
364 stmt
= pattern_def_stmt
;
365 stmt_info
= pattern_def_stmt_info
;
369 pattern_def_si
= gsi_none ();
370 analyze_pattern_stmt
= false;
374 analyze_pattern_stmt
= false;
377 if (gimple_get_lhs (stmt
) == NULL_TREE
378 /* MASK_STORE has no lhs, but is ok. */
379 && (!is_gimple_call (stmt
)
380 || !gimple_call_internal_p (stmt
)
381 || gimple_call_internal_fn (stmt
) != IFN_MASK_STORE
))
383 if (is_gimple_call (stmt
))
385 /* Ignore calls with no lhs. These must be calls to
386 #pragma omp simd functions, and what vectorization factor
387 it really needs can't be determined until
388 vectorizable_simd_clone_call. */
389 if (!analyze_pattern_stmt
&& gsi_end_p (pattern_def_si
))
391 pattern_def_seq
= NULL
;
396 if (dump_enabled_p ())
398 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
399 "not vectorized: irregular stmt.");
400 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
,
402 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
407 if (VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt
))))
409 if (dump_enabled_p ())
411 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
412 "not vectorized: vector stmt in loop:");
413 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
414 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
419 if (STMT_VINFO_VECTYPE (stmt_info
))
421 /* The only case when a vectype had been already set is for stmts
422 that contain a dataref, or for "pattern-stmts" (stmts
423 generated by the vectorizer to represent/replace a certain
425 gcc_assert (STMT_VINFO_DATA_REF (stmt_info
)
426 || is_pattern_stmt_p (stmt_info
)
427 || !gsi_end_p (pattern_def_si
));
428 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
432 gcc_assert (!STMT_VINFO_DATA_REF (stmt_info
));
433 if (is_gimple_call (stmt
)
434 && gimple_call_internal_p (stmt
)
435 && gimple_call_internal_fn (stmt
) == IFN_MASK_STORE
)
436 scalar_type
= TREE_TYPE (gimple_call_arg (stmt
, 3));
438 scalar_type
= TREE_TYPE (gimple_get_lhs (stmt
));
439 if (dump_enabled_p ())
441 dump_printf_loc (MSG_NOTE
, vect_location
,
442 "get vectype for scalar type: ");
443 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
444 dump_printf (MSG_NOTE
, "\n");
446 vectype
= get_vectype_for_scalar_type (scalar_type
);
449 if (dump_enabled_p ())
451 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
452 "not vectorized: unsupported "
454 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
456 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
461 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
463 if (dump_enabled_p ())
465 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
466 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vectype
);
467 dump_printf (MSG_NOTE
, "\n");
471 /* The vectorization factor is according to the smallest
472 scalar type (or the largest vector size, but we only
473 support one vector size per loop). */
474 scalar_type
= vect_get_smallest_scalar_type (stmt
, &dummy
,
476 if (dump_enabled_p ())
478 dump_printf_loc (MSG_NOTE
, vect_location
,
479 "get vectype for scalar type: ");
480 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
481 dump_printf (MSG_NOTE
, "\n");
483 vf_vectype
= get_vectype_for_scalar_type (scalar_type
);
486 if (dump_enabled_p ())
488 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
489 "not vectorized: unsupported data-type ");
490 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
492 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
497 if ((GET_MODE_SIZE (TYPE_MODE (vectype
))
498 != GET_MODE_SIZE (TYPE_MODE (vf_vectype
))))
500 if (dump_enabled_p ())
502 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
503 "not vectorized: different sized vector "
504 "types in statement, ");
505 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
507 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
508 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
510 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
515 if (dump_enabled_p ())
517 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
518 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vf_vectype
);
519 dump_printf (MSG_NOTE
, "\n");
522 nunits
= TYPE_VECTOR_SUBPARTS (vf_vectype
);
523 if (dump_enabled_p ())
524 dump_printf_loc (MSG_NOTE
, vect_location
, "nunits = %d\n", nunits
);
525 if (!vectorization_factor
526 || (nunits
> vectorization_factor
))
527 vectorization_factor
= nunits
;
529 if (!analyze_pattern_stmt
&& gsi_end_p (pattern_def_si
))
531 pattern_def_seq
= NULL
;
537 /* TODO: Analyze cost. Decide if worth while to vectorize. */
538 if (dump_enabled_p ())
539 dump_printf_loc (MSG_NOTE
, vect_location
, "vectorization factor = %d\n",
540 vectorization_factor
);
541 if (vectorization_factor
<= 1)
543 if (dump_enabled_p ())
544 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
545 "not vectorized: unsupported data-type\n");
548 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
554 /* Function vect_is_simple_iv_evolution.
556 FORNOW: A simple evolution of an induction variables in the loop is
557 considered a polynomial evolution. */
560 vect_is_simple_iv_evolution (unsigned loop_nb
, tree access_fn
, tree
* init
,
565 tree evolution_part
= evolution_part_in_loop_num (access_fn
, loop_nb
);
568 /* When there is no evolution in this loop, the evolution function
570 if (evolution_part
== NULL_TREE
)
573 /* When the evolution is a polynomial of degree >= 2
574 the evolution function is not "simple". */
575 if (tree_is_chrec (evolution_part
))
578 step_expr
= evolution_part
;
579 init_expr
= unshare_expr (initial_condition_in_loop_num (access_fn
, loop_nb
));
581 if (dump_enabled_p ())
583 dump_printf_loc (MSG_NOTE
, vect_location
, "step: ");
584 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, step_expr
);
585 dump_printf (MSG_NOTE
, ", init: ");
586 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, init_expr
);
587 dump_printf (MSG_NOTE
, "\n");
593 if (TREE_CODE (step_expr
) != INTEGER_CST
594 && (TREE_CODE (step_expr
) != SSA_NAME
595 || ((bb
= gimple_bb (SSA_NAME_DEF_STMT (step_expr
)))
596 && flow_bb_inside_loop_p (get_loop (cfun
, loop_nb
), bb
))
597 || (!INTEGRAL_TYPE_P (TREE_TYPE (step_expr
))
598 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
))
599 || !flag_associative_math
)))
600 && (TREE_CODE (step_expr
) != REAL_CST
601 || !flag_associative_math
))
603 if (dump_enabled_p ())
604 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
612 /* Function vect_analyze_scalar_cycles_1.
614 Examine the cross iteration def-use cycles of scalar variables
615 in LOOP. LOOP_VINFO represents the loop that is now being
616 considered for vectorization (can be LOOP, or an outer-loop
620 vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo
, struct loop
*loop
)
622 basic_block bb
= loop
->header
;
624 auto_vec
<gimple
, 64> worklist
;
625 gimple_stmt_iterator gsi
;
628 if (dump_enabled_p ())
629 dump_printf_loc (MSG_NOTE
, vect_location
,
630 "=== vect_analyze_scalar_cycles ===\n");
632 /* First - identify all inductions. Reduction detection assumes that all the
633 inductions have been identified, therefore, this order must not be
635 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
637 gimple phi
= gsi_stmt (gsi
);
638 tree access_fn
= NULL
;
639 tree def
= PHI_RESULT (phi
);
640 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (phi
);
642 if (dump_enabled_p ())
644 dump_printf_loc (MSG_NOTE
, vect_location
, "Analyze phi: ");
645 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
646 dump_printf (MSG_NOTE
, "\n");
649 /* Skip virtual phi's. The data dependences that are associated with
650 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
651 if (virtual_operand_p (def
))
654 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_unknown_def_type
;
656 /* Analyze the evolution function. */
657 access_fn
= analyze_scalar_evolution (loop
, def
);
660 STRIP_NOPS (access_fn
);
661 if (dump_enabled_p ())
663 dump_printf_loc (MSG_NOTE
, vect_location
,
664 "Access function of PHI: ");
665 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, access_fn
);
666 dump_printf (MSG_NOTE
, "\n");
668 STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
)
669 = evolution_part_in_loop_num (access_fn
, loop
->num
);
673 || !vect_is_simple_iv_evolution (loop
->num
, access_fn
, &init
, &step
)
674 || (LOOP_VINFO_LOOP (loop_vinfo
) != loop
675 && TREE_CODE (step
) != INTEGER_CST
))
677 worklist
.safe_push (phi
);
681 gcc_assert (STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
) != NULL_TREE
);
683 if (dump_enabled_p ())
684 dump_printf_loc (MSG_NOTE
, vect_location
, "Detected induction.\n");
685 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_induction_def
;
689 /* Second - identify all reductions and nested cycles. */
690 while (worklist
.length () > 0)
692 gimple phi
= worklist
.pop ();
693 tree def
= PHI_RESULT (phi
);
694 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (phi
);
698 if (dump_enabled_p ())
700 dump_printf_loc (MSG_NOTE
, vect_location
, "Analyze phi: ");
701 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
702 dump_printf (MSG_NOTE
, "\n");
705 gcc_assert (!virtual_operand_p (def
)
706 && STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_unknown_def_type
);
708 nested_cycle
= (loop
!= LOOP_VINFO_LOOP (loop_vinfo
));
709 reduc_stmt
= vect_force_simple_reduction (loop_vinfo
, phi
, !nested_cycle
,
715 if (dump_enabled_p ())
716 dump_printf_loc (MSG_NOTE
, vect_location
,
717 "Detected double reduction.\n");
719 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_double_reduction_def
;
720 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
721 vect_double_reduction_def
;
727 if (dump_enabled_p ())
728 dump_printf_loc (MSG_NOTE
, vect_location
,
729 "Detected vectorizable nested cycle.\n");
731 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_nested_cycle
;
732 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
737 if (dump_enabled_p ())
738 dump_printf_loc (MSG_NOTE
, vect_location
,
739 "Detected reduction.\n");
741 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_reduction_def
;
742 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
744 /* Store the reduction cycles for possible vectorization in
746 LOOP_VINFO_REDUCTIONS (loop_vinfo
).safe_push (reduc_stmt
);
751 if (dump_enabled_p ())
752 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
753 "Unknown def-use cycle pattern.\n");
758 /* Function vect_analyze_scalar_cycles.
760 Examine the cross iteration def-use cycles of scalar variables, by
761 analyzing the loop-header PHIs of scalar variables. Classify each
762 cycle as one of the following: invariant, induction, reduction, unknown.
763 We do that for the loop represented by LOOP_VINFO, and also to its
764 inner-loop, if exists.
765 Examples for scalar cycles:
780 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo
)
782 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
784 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
);
786 /* When vectorizing an outer-loop, the inner-loop is executed sequentially.
787 Reductions in such inner-loop therefore have different properties than
788 the reductions in the nest that gets vectorized:
789 1. When vectorized, they are executed in the same order as in the original
790 scalar loop, so we can't change the order of computation when
792 2. FIXME: Inner-loop reductions can be used in the inner-loop, so the
793 current checks are too strict. */
796 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
->inner
);
800 /* Function vect_get_loop_niters.
802 Determine how many iterations the loop is executed and place it
803 in NUMBER_OF_ITERATIONS. Place the number of latch iterations
804 in NUMBER_OF_ITERATIONSM1.
806 Return the loop exit condition. */
809 vect_get_loop_niters (struct loop
*loop
, tree
*number_of_iterations
,
810 tree
*number_of_iterationsm1
)
814 if (dump_enabled_p ())
815 dump_printf_loc (MSG_NOTE
, vect_location
,
816 "=== get_loop_niters ===\n");
818 niters
= number_of_latch_executions (loop
);
819 *number_of_iterationsm1
= niters
;
821 /* We want the number of loop header executions which is the number
822 of latch executions plus one.
823 ??? For UINT_MAX latch executions this number overflows to zero
824 for loops like do { n++; } while (n != 0); */
825 if (niters
&& !chrec_contains_undetermined (niters
))
826 niters
= fold_build2 (PLUS_EXPR
, TREE_TYPE (niters
), unshare_expr (niters
),
827 build_int_cst (TREE_TYPE (niters
), 1));
828 *number_of_iterations
= niters
;
830 return get_loop_exit_condition (loop
);
834 /* Function bb_in_loop_p
836 Used as predicate for dfs order traversal of the loop bbs. */
839 bb_in_loop_p (const_basic_block bb
, const void *data
)
841 const struct loop
*const loop
= (const struct loop
*)data
;
842 if (flow_bb_inside_loop_p (loop
, bb
))
848 /* Function new_loop_vec_info.
850 Create and initialize a new loop_vec_info struct for LOOP, as well as
851 stmt_vec_info structs for all the stmts in LOOP. */
854 new_loop_vec_info (struct loop
*loop
)
858 gimple_stmt_iterator si
;
859 unsigned int i
, nbbs
;
861 res
= (loop_vec_info
) xcalloc (1, sizeof (struct _loop_vec_info
));
862 LOOP_VINFO_LOOP (res
) = loop
;
864 bbs
= get_loop_body (loop
);
866 /* Create/Update stmt_info for all stmts in the loop. */
867 for (i
= 0; i
< loop
->num_nodes
; i
++)
869 basic_block bb
= bbs
[i
];
871 /* BBs in a nested inner-loop will have been already processed (because
872 we will have called vect_analyze_loop_form for any nested inner-loop).
873 Therefore, for stmts in an inner-loop we just want to update the
874 STMT_VINFO_LOOP_VINFO field of their stmt_info to point to the new
875 loop_info of the outer-loop we are currently considering to vectorize
876 (instead of the loop_info of the inner-loop).
877 For stmts in other BBs we need to create a stmt_info from scratch. */
878 if (bb
->loop_father
!= loop
)
881 gcc_assert (loop
->inner
&& bb
->loop_father
== loop
->inner
);
882 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
884 gimple phi
= gsi_stmt (si
);
885 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
886 loop_vec_info inner_loop_vinfo
=
887 STMT_VINFO_LOOP_VINFO (stmt_info
);
888 gcc_assert (loop
->inner
== LOOP_VINFO_LOOP (inner_loop_vinfo
));
889 STMT_VINFO_LOOP_VINFO (stmt_info
) = res
;
891 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
893 gimple stmt
= gsi_stmt (si
);
894 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
895 loop_vec_info inner_loop_vinfo
=
896 STMT_VINFO_LOOP_VINFO (stmt_info
);
897 gcc_assert (loop
->inner
== LOOP_VINFO_LOOP (inner_loop_vinfo
));
898 STMT_VINFO_LOOP_VINFO (stmt_info
) = res
;
903 /* bb in current nest. */
904 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
906 gimple phi
= gsi_stmt (si
);
907 gimple_set_uid (phi
, 0);
908 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, res
, NULL
));
911 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
913 gimple stmt
= gsi_stmt (si
);
914 gimple_set_uid (stmt
, 0);
915 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, res
, NULL
));
920 /* CHECKME: We want to visit all BBs before their successors (except for
921 latch blocks, for which this assertion wouldn't hold). In the simple
922 case of the loop forms we allow, a dfs order of the BBs would the same
923 as reversed postorder traversal, so we are safe. */
926 bbs
= XCNEWVEC (basic_block
, loop
->num_nodes
);
927 nbbs
= dfs_enumerate_from (loop
->header
, 0, bb_in_loop_p
,
928 bbs
, loop
->num_nodes
, loop
);
929 gcc_assert (nbbs
== loop
->num_nodes
);
931 LOOP_VINFO_BBS (res
) = bbs
;
932 LOOP_VINFO_NITERSM1 (res
) = NULL
;
933 LOOP_VINFO_NITERS (res
) = NULL
;
934 LOOP_VINFO_NITERS_UNCHANGED (res
) = NULL
;
935 LOOP_VINFO_COST_MODEL_MIN_ITERS (res
) = 0;
936 LOOP_VINFO_VECTORIZABLE_P (res
) = 0;
937 LOOP_VINFO_PEELING_FOR_ALIGNMENT (res
) = 0;
938 LOOP_VINFO_VECT_FACTOR (res
) = 0;
939 LOOP_VINFO_LOOP_NEST (res
).create (3);
940 LOOP_VINFO_DATAREFS (res
).create (10);
941 LOOP_VINFO_DDRS (res
).create (10 * 10);
942 LOOP_VINFO_UNALIGNED_DR (res
) = NULL
;
943 LOOP_VINFO_MAY_MISALIGN_STMTS (res
).create (
944 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS
));
945 LOOP_VINFO_MAY_ALIAS_DDRS (res
).create (
946 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS
));
947 LOOP_VINFO_GROUPED_STORES (res
).create (10);
948 LOOP_VINFO_REDUCTIONS (res
).create (10);
949 LOOP_VINFO_REDUCTION_CHAINS (res
).create (10);
950 LOOP_VINFO_SLP_INSTANCES (res
).create (10);
951 LOOP_VINFO_SLP_UNROLLING_FACTOR (res
) = 1;
952 LOOP_VINFO_TARGET_COST_DATA (res
) = init_cost (loop
);
953 LOOP_VINFO_PEELING_FOR_GAPS (res
) = false;
954 LOOP_VINFO_PEELING_FOR_NITER (res
) = false;
955 LOOP_VINFO_OPERANDS_SWAPPED (res
) = false;
961 /* Function destroy_loop_vec_info.
963 Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
964 stmts in the loop. */
967 destroy_loop_vec_info (loop_vec_info loop_vinfo
, bool clean_stmts
)
972 gimple_stmt_iterator si
;
974 vec
<slp_instance
> slp_instances
;
975 slp_instance instance
;
981 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
983 bbs
= LOOP_VINFO_BBS (loop_vinfo
);
984 nbbs
= clean_stmts
? loop
->num_nodes
: 0;
985 swapped
= LOOP_VINFO_OPERANDS_SWAPPED (loop_vinfo
);
987 for (j
= 0; j
< nbbs
; j
++)
989 basic_block bb
= bbs
[j
];
990 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
991 free_stmt_vec_info (gsi_stmt (si
));
993 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); )
995 gimple stmt
= gsi_stmt (si
);
997 /* We may have broken canonical form by moving a constant
998 into RHS1 of a commutative op. Fix such occurrences. */
999 if (swapped
&& is_gimple_assign (stmt
))
1001 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1003 if ((code
== PLUS_EXPR
1004 || code
== POINTER_PLUS_EXPR
1005 || code
== MULT_EXPR
)
1006 && CONSTANT_CLASS_P (gimple_assign_rhs1 (stmt
)))
1007 swap_ssa_operands (stmt
,
1008 gimple_assign_rhs1_ptr (stmt
),
1009 gimple_assign_rhs2_ptr (stmt
));
1012 /* Free stmt_vec_info. */
1013 free_stmt_vec_info (stmt
);
1018 free (LOOP_VINFO_BBS (loop_vinfo
));
1019 vect_destroy_datarefs (loop_vinfo
, NULL
);
1020 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo
));
1021 LOOP_VINFO_LOOP_NEST (loop_vinfo
).release ();
1022 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).release ();
1023 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
).release ();
1024 slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
1025 FOR_EACH_VEC_ELT (slp_instances
, j
, instance
)
1026 vect_free_slp_instance (instance
);
1028 LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).release ();
1029 LOOP_VINFO_GROUPED_STORES (loop_vinfo
).release ();
1030 LOOP_VINFO_REDUCTIONS (loop_vinfo
).release ();
1031 LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
).release ();
1033 if (LOOP_VINFO_PEELING_HTAB (loop_vinfo
).is_created ())
1034 LOOP_VINFO_PEELING_HTAB (loop_vinfo
).dispose ();
1036 destroy_cost_data (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
));
1043 /* Function vect_analyze_loop_1.
1045 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1046 for it. The different analyses will record information in the
1047 loop_vec_info struct. This is a subset of the analyses applied in
1048 vect_analyze_loop, to be applied on an inner-loop nested in the loop
1049 that is now considered for (outer-loop) vectorization. */
1051 static loop_vec_info
1052 vect_analyze_loop_1 (struct loop
*loop
)
1054 loop_vec_info loop_vinfo
;
1056 if (dump_enabled_p ())
1057 dump_printf_loc (MSG_NOTE
, vect_location
,
1058 "===== analyze_loop_nest_1 =====\n");
1060 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
1062 loop_vinfo
= vect_analyze_loop_form (loop
);
1065 if (dump_enabled_p ())
1066 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1067 "bad inner-loop form.\n");
1075 /* Function vect_analyze_loop_form.
1077 Verify that certain CFG restrictions hold, including:
1078 - the loop has a pre-header
1079 - the loop has a single entry and exit
1080 - the loop exit condition is simple enough, and the number of iterations
1081 can be analyzed (a countable loop). */
1084 vect_analyze_loop_form (struct loop
*loop
)
1086 loop_vec_info loop_vinfo
;
1088 tree number_of_iterations
= NULL
, number_of_iterationsm1
= NULL
;
1089 loop_vec_info inner_loop_vinfo
= NULL
;
1091 if (dump_enabled_p ())
1092 dump_printf_loc (MSG_NOTE
, vect_location
,
1093 "=== vect_analyze_loop_form ===\n");
1095 /* Different restrictions apply when we are considering an inner-most loop,
1096 vs. an outer (nested) loop.
1097 (FORNOW. May want to relax some of these restrictions in the future). */
1101 /* Inner-most loop. We currently require that the number of BBs is
1102 exactly 2 (the header and latch). Vectorizable inner-most loops
1113 if (loop
->num_nodes
!= 2)
1115 if (dump_enabled_p ())
1116 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1117 "not vectorized: control flow in loop.\n");
1121 if (empty_block_p (loop
->header
))
1123 if (dump_enabled_p ())
1124 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1125 "not vectorized: empty loop.\n");
1131 struct loop
*innerloop
= loop
->inner
;
1134 /* Nested loop. We currently require that the loop is doubly-nested,
1135 contains a single inner loop, and the number of BBs is exactly 5.
1136 Vectorizable outer-loops look like this:
1148 The inner-loop has the properties expected of inner-most loops
1149 as described above. */
1151 if ((loop
->inner
)->inner
|| (loop
->inner
)->next
)
1153 if (dump_enabled_p ())
1154 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1155 "not vectorized: multiple nested loops.\n");
1159 /* Analyze the inner-loop. */
1160 inner_loop_vinfo
= vect_analyze_loop_1 (loop
->inner
);
1161 if (!inner_loop_vinfo
)
1163 if (dump_enabled_p ())
1164 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1165 "not vectorized: Bad inner loop.\n");
1169 if (!expr_invariant_in_loop_p (loop
,
1170 LOOP_VINFO_NITERS (inner_loop_vinfo
)))
1172 if (dump_enabled_p ())
1173 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1174 "not vectorized: inner-loop count not"
1176 destroy_loop_vec_info (inner_loop_vinfo
, true);
1180 if (loop
->num_nodes
!= 5)
1182 if (dump_enabled_p ())
1183 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1184 "not vectorized: control flow in loop.\n");
1185 destroy_loop_vec_info (inner_loop_vinfo
, true);
1189 gcc_assert (EDGE_COUNT (innerloop
->header
->preds
) == 2);
1190 entryedge
= EDGE_PRED (innerloop
->header
, 0);
1191 if (EDGE_PRED (innerloop
->header
, 0)->src
== innerloop
->latch
)
1192 entryedge
= EDGE_PRED (innerloop
->header
, 1);
1194 if (entryedge
->src
!= loop
->header
1195 || !single_exit (innerloop
)
1196 || single_exit (innerloop
)->dest
!= EDGE_PRED (loop
->latch
, 0)->src
)
1198 if (dump_enabled_p ())
1199 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1200 "not vectorized: unsupported outerloop form.\n");
1201 destroy_loop_vec_info (inner_loop_vinfo
, true);
1205 if (dump_enabled_p ())
1206 dump_printf_loc (MSG_NOTE
, vect_location
,
1207 "Considering outer-loop vectorization.\n");
1210 if (!single_exit (loop
)
1211 || EDGE_COUNT (loop
->header
->preds
) != 2)
1213 if (dump_enabled_p ())
1215 if (!single_exit (loop
))
1216 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1217 "not vectorized: multiple exits.\n");
1218 else if (EDGE_COUNT (loop
->header
->preds
) != 2)
1219 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1220 "not vectorized: too many incoming edges.\n");
1222 if (inner_loop_vinfo
)
1223 destroy_loop_vec_info (inner_loop_vinfo
, true);
1227 /* We assume that the loop exit condition is at the end of the loop. i.e,
1228 that the loop is represented as a do-while (with a proper if-guard
1229 before the loop if needed), where the loop header contains all the
1230 executable statements, and the latch is empty. */
1231 if (!empty_block_p (loop
->latch
)
1232 || !gimple_seq_empty_p (phi_nodes (loop
->latch
)))
1234 if (dump_enabled_p ())
1235 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1236 "not vectorized: latch block not empty.\n");
1237 if (inner_loop_vinfo
)
1238 destroy_loop_vec_info (inner_loop_vinfo
, true);
1242 /* Make sure there exists a single-predecessor exit bb: */
1243 if (!single_pred_p (single_exit (loop
)->dest
))
1245 edge e
= single_exit (loop
);
1246 if (!(e
->flags
& EDGE_ABNORMAL
))
1248 split_loop_exit_edge (e
);
1249 if (dump_enabled_p ())
1250 dump_printf (MSG_NOTE
, "split exit edge.\n");
1254 if (dump_enabled_p ())
1255 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1256 "not vectorized: abnormal loop exit edge.\n");
1257 if (inner_loop_vinfo
)
1258 destroy_loop_vec_info (inner_loop_vinfo
, true);
1263 loop_cond
= vect_get_loop_niters (loop
, &number_of_iterations
,
1264 &number_of_iterationsm1
);
1267 if (dump_enabled_p ())
1268 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1269 "not vectorized: complicated exit condition.\n");
1270 if (inner_loop_vinfo
)
1271 destroy_loop_vec_info (inner_loop_vinfo
, true);
1275 if (!number_of_iterations
1276 || chrec_contains_undetermined (number_of_iterations
))
1278 if (dump_enabled_p ())
1279 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1280 "not vectorized: number of iterations cannot be "
1282 if (inner_loop_vinfo
)
1283 destroy_loop_vec_info (inner_loop_vinfo
, true);
1287 if (integer_zerop (number_of_iterations
))
1289 if (dump_enabled_p ())
1290 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1291 "not vectorized: number of iterations = 0.\n");
1292 if (inner_loop_vinfo
)
1293 destroy_loop_vec_info (inner_loop_vinfo
, true);
1297 loop_vinfo
= new_loop_vec_info (loop
);
1298 LOOP_VINFO_NITERSM1 (loop_vinfo
) = number_of_iterationsm1
;
1299 LOOP_VINFO_NITERS (loop_vinfo
) = number_of_iterations
;
1300 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo
) = number_of_iterations
;
1302 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
1304 if (dump_enabled_p ())
1306 dump_printf_loc (MSG_NOTE
, vect_location
,
1307 "Symbolic number of iterations is ");
1308 dump_generic_expr (MSG_NOTE
, TDF_DETAILS
, number_of_iterations
);
1309 dump_printf (MSG_NOTE
, "\n");
1313 STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond
)) = loop_exit_ctrl_vec_info_type
;
1315 /* CHECKME: May want to keep it around it in the future. */
1316 if (inner_loop_vinfo
)
1317 destroy_loop_vec_info (inner_loop_vinfo
, false);
1319 gcc_assert (!loop
->aux
);
1320 loop
->aux
= loop_vinfo
;
1325 /* Function vect_analyze_loop_operations.
1327 Scan the loop stmts and make sure they are all vectorizable. */
1330 vect_analyze_loop_operations (loop_vec_info loop_vinfo
, bool slp
)
1332 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1333 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1334 int nbbs
= loop
->num_nodes
;
1335 gimple_stmt_iterator si
;
1336 unsigned int vectorization_factor
= 0;
1339 stmt_vec_info stmt_info
;
1340 bool need_to_vectorize
= false;
1341 int min_profitable_iters
;
1342 int min_scalar_loop_bound
;
1344 bool only_slp_in_loop
= true, ok
;
1345 HOST_WIDE_INT max_niter
;
1346 HOST_WIDE_INT estimated_niter
;
1347 int min_profitable_estimate
;
1349 if (dump_enabled_p ())
1350 dump_printf_loc (MSG_NOTE
, vect_location
,
1351 "=== vect_analyze_loop_operations ===\n");
1353 gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo
));
1354 vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1357 /* If all the stmts in the loop can be SLPed, we perform only SLP, and
1358 vectorization factor of the loop is the unrolling factor required by
1359 the SLP instances. If that unrolling factor is 1, we say, that we
1360 perform pure SLP on loop - cross iteration parallelism is not
1362 for (i
= 0; i
< nbbs
; i
++)
1364 basic_block bb
= bbs
[i
];
1365 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1367 gimple stmt
= gsi_stmt (si
);
1368 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1369 gcc_assert (stmt_info
);
1370 if ((STMT_VINFO_RELEVANT_P (stmt_info
)
1371 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
1372 && !PURE_SLP_STMT (stmt_info
))
1373 /* STMT needs both SLP and loop-based vectorization. */
1374 only_slp_in_loop
= false;
1378 if (only_slp_in_loop
)
1379 vectorization_factor
= LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
);
1381 vectorization_factor
= least_common_multiple (vectorization_factor
,
1382 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
));
1384 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
1385 if (dump_enabled_p ())
1386 dump_printf_loc (MSG_NOTE
, vect_location
,
1387 "Updating vectorization factor to %d\n",
1388 vectorization_factor
);
1391 for (i
= 0; i
< nbbs
; i
++)
1393 basic_block bb
= bbs
[i
];
1395 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
1397 phi
= gsi_stmt (si
);
1400 stmt_info
= vinfo_for_stmt (phi
);
1401 if (dump_enabled_p ())
1403 dump_printf_loc (MSG_NOTE
, vect_location
, "examining phi: ");
1404 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
1405 dump_printf (MSG_NOTE
, "\n");
1408 /* Inner-loop loop-closed exit phi in outer-loop vectorization
1409 (i.e., a phi in the tail of the outer-loop). */
1410 if (! is_loop_header_bb_p (bb
))
1412 /* FORNOW: we currently don't support the case that these phis
1413 are not used in the outerloop (unless it is double reduction,
1414 i.e., this phi is vect_reduction_def), cause this case
1415 requires to actually do something here. */
1416 if ((!STMT_VINFO_RELEVANT_P (stmt_info
)
1417 || STMT_VINFO_LIVE_P (stmt_info
))
1418 && STMT_VINFO_DEF_TYPE (stmt_info
)
1419 != vect_double_reduction_def
)
1421 if (dump_enabled_p ())
1422 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1423 "Unsupported loop-closed phi in "
1428 /* If PHI is used in the outer loop, we check that its operand
1429 is defined in the inner loop. */
1430 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1435 if (gimple_phi_num_args (phi
) != 1)
1438 phi_op
= PHI_ARG_DEF (phi
, 0);
1439 if (TREE_CODE (phi_op
) != SSA_NAME
)
1442 op_def_stmt
= SSA_NAME_DEF_STMT (phi_op
);
1443 if (gimple_nop_p (op_def_stmt
)
1444 || !flow_bb_inside_loop_p (loop
, gimple_bb (op_def_stmt
))
1445 || !vinfo_for_stmt (op_def_stmt
))
1448 if (STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1449 != vect_used_in_outer
1450 && STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1451 != vect_used_in_outer_by_reduction
)
1458 gcc_assert (stmt_info
);
1460 if (STMT_VINFO_LIVE_P (stmt_info
))
1462 /* FORNOW: not yet supported. */
1463 if (dump_enabled_p ())
1464 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1465 "not vectorized: value used after loop.\n");
1469 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
1470 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_induction_def
)
1472 /* A scalar-dependence cycle that we don't support. */
1473 if (dump_enabled_p ())
1474 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1475 "not vectorized: scalar dependence cycle.\n");
1479 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1481 need_to_vectorize
= true;
1482 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
1483 ok
= vectorizable_induction (phi
, NULL
, NULL
);
1488 if (dump_enabled_p ())
1490 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1491 "not vectorized: relevant phi not "
1493 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, phi
, 0);
1494 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
1500 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1502 gimple stmt
= gsi_stmt (si
);
1503 if (!gimple_clobber_p (stmt
)
1504 && !vect_analyze_stmt (stmt
, &need_to_vectorize
, NULL
))
1509 /* All operations in the loop are either irrelevant (deal with loop
1510 control, or dead), or only used outside the loop and can be moved
1511 out of the loop (e.g. invariants, inductions). The loop can be
1512 optimized away by scalar optimizations. We're better off not
1513 touching this loop. */
1514 if (!need_to_vectorize
)
1516 if (dump_enabled_p ())
1517 dump_printf_loc (MSG_NOTE
, vect_location
,
1518 "All the computation can be taken out of the loop.\n");
1519 if (dump_enabled_p ())
1520 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1521 "not vectorized: redundant loop. no profit to "
1526 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
) && dump_enabled_p ())
1527 dump_printf_loc (MSG_NOTE
, vect_location
,
1528 "vectorization_factor = %d, niters = "
1529 HOST_WIDE_INT_PRINT_DEC
"\n", vectorization_factor
,
1530 LOOP_VINFO_INT_NITERS (loop_vinfo
));
1532 if ((LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1533 && (LOOP_VINFO_INT_NITERS (loop_vinfo
) < vectorization_factor
))
1534 || ((max_niter
= max_stmt_executions_int (loop
)) != -1
1535 && (unsigned HOST_WIDE_INT
) max_niter
< vectorization_factor
))
1537 if (dump_enabled_p ())
1538 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1539 "not vectorized: iteration count too small.\n");
1540 if (dump_enabled_p ())
1541 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1542 "not vectorized: iteration count smaller than "
1543 "vectorization factor.\n");
1547 /* Analyze cost. Decide if worth while to vectorize. */
1549 /* Once VF is set, SLP costs should be updated since the number of created
1550 vector stmts depends on VF. */
1551 vect_update_slp_costs_according_to_vf (loop_vinfo
);
1553 vect_estimate_min_profitable_iters (loop_vinfo
, &min_profitable_iters
,
1554 &min_profitable_estimate
);
1555 LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo
) = min_profitable_iters
;
1557 if (min_profitable_iters
< 0)
1559 if (dump_enabled_p ())
1560 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1561 "not vectorized: vectorization not profitable.\n");
1562 if (dump_enabled_p ())
1563 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1564 "not vectorized: vector version will never be "
1569 min_scalar_loop_bound
= ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND
)
1570 * vectorization_factor
) - 1);
1573 /* Use the cost model only if it is more conservative than user specified
1576 th
= (unsigned) min_scalar_loop_bound
;
1577 if (min_profitable_iters
1578 && (!min_scalar_loop_bound
1579 || min_profitable_iters
> min_scalar_loop_bound
))
1580 th
= (unsigned) min_profitable_iters
;
1582 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1583 && LOOP_VINFO_INT_NITERS (loop_vinfo
) <= th
)
1585 if (dump_enabled_p ())
1586 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1587 "not vectorized: vectorization not profitable.\n");
1588 if (dump_enabled_p ())
1589 dump_printf_loc (MSG_NOTE
, vect_location
,
1590 "not vectorized: iteration count smaller than user "
1591 "specified loop bound parameter or minimum profitable "
1592 "iterations (whichever is more conservative).\n");
1596 if ((estimated_niter
= estimated_stmt_executions_int (loop
)) != -1
1597 && ((unsigned HOST_WIDE_INT
) estimated_niter
1598 <= MAX (th
, (unsigned)min_profitable_estimate
)))
1600 if (dump_enabled_p ())
1601 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1602 "not vectorized: estimated iteration count too "
1604 if (dump_enabled_p ())
1605 dump_printf_loc (MSG_NOTE
, vect_location
,
1606 "not vectorized: estimated iteration count smaller "
1607 "than specified loop bound parameter or minimum "
1608 "profitable iterations (whichever is more "
1609 "conservative).\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");
1768 /* Decide whether we need to create an epilogue loop to handle
1769 remaining scalar iterations. */
1770 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1771 && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
) > 0)
1773 if (ctz_hwi (LOOP_VINFO_INT_NITERS (loop_vinfo
)
1774 - LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
))
1775 < exact_log2 (LOOP_VINFO_VECT_FACTOR (loop_vinfo
)))
1776 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
) = true;
1778 else if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
)
1779 || (tree_ctz (LOOP_VINFO_NITERS (loop_vinfo
))
1780 < (unsigned)exact_log2 (LOOP_VINFO_VECT_FACTOR (loop_vinfo
))))
1781 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
) = true;
1783 /* If an epilogue loop is required make sure we can create one. */
1784 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
1785 || LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
))
1787 if (dump_enabled_p ())
1788 dump_printf_loc (MSG_NOTE
, vect_location
, "epilog loop required\n");
1789 if (!vect_can_advance_ivs_p (loop_vinfo
)
1790 || !slpeel_can_duplicate_loop_p (LOOP_VINFO_LOOP (loop_vinfo
),
1791 single_exit (LOOP_VINFO_LOOP
1794 if (dump_enabled_p ())
1795 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1796 "not vectorized: can't create required "
1805 /* Function vect_analyze_loop.
1807 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1808 for it. The different analyses will record information in the
1809 loop_vec_info struct. */
1811 vect_analyze_loop (struct loop
*loop
)
1813 loop_vec_info loop_vinfo
;
1814 unsigned int vector_sizes
;
1816 /* Autodetect first vector size we try. */
1817 current_vector_size
= 0;
1818 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
1820 if (dump_enabled_p ())
1821 dump_printf_loc (MSG_NOTE
, vect_location
,
1822 "===== analyze_loop_nest =====\n");
1824 if (loop_outer (loop
)
1825 && loop_vec_info_for_loop (loop_outer (loop
))
1826 && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop
))))
1828 if (dump_enabled_p ())
1829 dump_printf_loc (MSG_NOTE
, vect_location
,
1830 "outer-loop already vectorized.\n");
1836 /* Check the CFG characteristics of the loop (nesting, entry/exit). */
1837 loop_vinfo
= vect_analyze_loop_form (loop
);
1840 if (dump_enabled_p ())
1841 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1842 "bad loop form.\n");
1846 if (vect_analyze_loop_2 (loop_vinfo
))
1848 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
) = 1;
1853 destroy_loop_vec_info (loop_vinfo
, true);
1855 vector_sizes
&= ~current_vector_size
;
1856 if (vector_sizes
== 0
1857 || current_vector_size
== 0)
1860 /* Try the next biggest vector size. */
1861 current_vector_size
= 1 << floor_log2 (vector_sizes
);
1862 if (dump_enabled_p ())
1863 dump_printf_loc (MSG_NOTE
, vect_location
,
1864 "***** Re-trying analysis with "
1865 "vector size %d\n", current_vector_size
);
1870 /* Function reduction_code_for_scalar_code
1873 CODE - tree_code of a reduction operations.
1876 REDUC_CODE - the corresponding tree-code to be used to reduce the
1877 vector of partial results into a single scalar result (which
1878 will also reside in a vector) or ERROR_MARK if the operation is
1879 a supported reduction operation, but does not have such tree-code.
1881 Return FALSE if CODE currently cannot be vectorized as reduction. */
1884 reduction_code_for_scalar_code (enum tree_code code
,
1885 enum tree_code
*reduc_code
)
1890 *reduc_code
= REDUC_MAX_EXPR
;
1894 *reduc_code
= REDUC_MIN_EXPR
;
1898 *reduc_code
= REDUC_PLUS_EXPR
;
1906 *reduc_code
= ERROR_MARK
;
1915 /* Error reporting helper for vect_is_simple_reduction below. GIMPLE statement
1916 STMT is printed with a message MSG. */
1919 report_vect_op (int msg_type
, gimple stmt
, const char *msg
)
1921 dump_printf_loc (msg_type
, vect_location
, "%s", msg
);
1922 dump_gimple_stmt (msg_type
, TDF_SLIM
, stmt
, 0);
1923 dump_printf (msg_type
, "\n");
1927 /* Detect SLP reduction of the form:
1937 PHI is the reduction phi node (#a1 = phi <a5, a0> above)
1938 FIRST_STMT is the first reduction stmt in the chain
1939 (a2 = operation (a1)).
1941 Return TRUE if a reduction chain was detected. */
1944 vect_is_slp_reduction (loop_vec_info loop_info
, gimple phi
, gimple first_stmt
)
1946 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
1947 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
1948 enum tree_code code
;
1949 gimple current_stmt
= NULL
, loop_use_stmt
= NULL
, first
, next_stmt
;
1950 stmt_vec_info use_stmt_info
, current_stmt_info
;
1952 imm_use_iterator imm_iter
;
1953 use_operand_p use_p
;
1954 int nloop_uses
, size
= 0, n_out_of_loop_uses
;
1957 if (loop
!= vect_loop
)
1960 lhs
= PHI_RESULT (phi
);
1961 code
= gimple_assign_rhs_code (first_stmt
);
1965 n_out_of_loop_uses
= 0;
1966 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
1968 gimple use_stmt
= USE_STMT (use_p
);
1969 if (is_gimple_debug (use_stmt
))
1972 use_stmt
= USE_STMT (use_p
);
1974 /* Check if we got back to the reduction phi. */
1975 if (use_stmt
== phi
)
1977 loop_use_stmt
= use_stmt
;
1982 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
1984 if (vinfo_for_stmt (use_stmt
)
1985 && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (use_stmt
)))
1987 loop_use_stmt
= use_stmt
;
1992 n_out_of_loop_uses
++;
1994 /* There are can be either a single use in the loop or two uses in
1996 if (nloop_uses
> 1 || (n_out_of_loop_uses
&& nloop_uses
))
2003 /* We reached a statement with no loop uses. */
2004 if (nloop_uses
== 0)
2007 /* This is a loop exit phi, and we haven't reached the reduction phi. */
2008 if (gimple_code (loop_use_stmt
) == GIMPLE_PHI
)
2011 if (!is_gimple_assign (loop_use_stmt
)
2012 || code
!= gimple_assign_rhs_code (loop_use_stmt
)
2013 || !flow_bb_inside_loop_p (loop
, gimple_bb (loop_use_stmt
)))
2016 /* Insert USE_STMT into reduction chain. */
2017 use_stmt_info
= vinfo_for_stmt (loop_use_stmt
);
2020 current_stmt_info
= vinfo_for_stmt (current_stmt
);
2021 GROUP_NEXT_ELEMENT (current_stmt_info
) = loop_use_stmt
;
2022 GROUP_FIRST_ELEMENT (use_stmt_info
)
2023 = GROUP_FIRST_ELEMENT (current_stmt_info
);
2026 GROUP_FIRST_ELEMENT (use_stmt_info
) = loop_use_stmt
;
2028 lhs
= gimple_assign_lhs (loop_use_stmt
);
2029 current_stmt
= loop_use_stmt
;
2033 if (!found
|| loop_use_stmt
!= phi
|| size
< 2)
2036 /* Swap the operands, if needed, to make the reduction operand be the second
2038 lhs
= PHI_RESULT (phi
);
2039 next_stmt
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
2042 if (gimple_assign_rhs2 (next_stmt
) == lhs
)
2044 tree op
= gimple_assign_rhs1 (next_stmt
);
2045 gimple def_stmt
= NULL
;
2047 if (TREE_CODE (op
) == SSA_NAME
)
2048 def_stmt
= SSA_NAME_DEF_STMT (op
);
2050 /* Check that the other def is either defined in the loop
2051 ("vect_internal_def"), or it's an induction (defined by a
2052 loop-header phi-node). */
2054 && gimple_bb (def_stmt
)
2055 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2056 && (is_gimple_assign (def_stmt
)
2057 || is_gimple_call (def_stmt
)
2058 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2059 == vect_induction_def
2060 || (gimple_code (def_stmt
) == GIMPLE_PHI
2061 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2062 == vect_internal_def
2063 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
2065 lhs
= gimple_assign_lhs (next_stmt
);
2066 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
2074 tree op
= gimple_assign_rhs2 (next_stmt
);
2075 gimple def_stmt
= NULL
;
2077 if (TREE_CODE (op
) == SSA_NAME
)
2078 def_stmt
= SSA_NAME_DEF_STMT (op
);
2080 /* Check that the other def is either defined in the loop
2081 ("vect_internal_def"), or it's an induction (defined by a
2082 loop-header phi-node). */
2084 && gimple_bb (def_stmt
)
2085 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2086 && (is_gimple_assign (def_stmt
)
2087 || is_gimple_call (def_stmt
)
2088 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2089 == vect_induction_def
2090 || (gimple_code (def_stmt
) == GIMPLE_PHI
2091 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2092 == vect_internal_def
2093 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
2095 if (dump_enabled_p ())
2097 dump_printf_loc (MSG_NOTE
, vect_location
, "swapping oprnds: ");
2098 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, next_stmt
, 0);
2099 dump_printf (MSG_NOTE
, "\n");
2102 swap_ssa_operands (next_stmt
,
2103 gimple_assign_rhs1_ptr (next_stmt
),
2104 gimple_assign_rhs2_ptr (next_stmt
));
2105 update_stmt (next_stmt
);
2107 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (next_stmt
)))
2108 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
2114 lhs
= gimple_assign_lhs (next_stmt
);
2115 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
2118 /* Save the chain for further analysis in SLP detection. */
2119 first
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
2120 LOOP_VINFO_REDUCTION_CHAINS (loop_info
).safe_push (first
);
2121 GROUP_SIZE (vinfo_for_stmt (first
)) = size
;
2127 /* Function vect_is_simple_reduction_1
2129 (1) Detect a cross-iteration def-use cycle that represents a simple
2130 reduction computation. We look for the following pattern:
2135 a2 = operation (a3, a1)
2142 a2 = operation (a3, a1)
2145 1. operation is commutative and associative and it is safe to
2146 change the order of the computation (if CHECK_REDUCTION is true)
2147 2. no uses for a2 in the loop (a2 is used out of the loop)
2148 3. no uses of a1 in the loop besides the reduction operation
2149 4. no uses of a1 outside the loop.
2151 Conditions 1,4 are tested here.
2152 Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
2154 (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
2155 nested cycles, if CHECK_REDUCTION is false.
2157 (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
2161 inner loop (def of a3)
2164 If MODIFY is true it tries also to rework the code in-place to enable
2165 detection of more reduction patterns. For the time being we rewrite
2166 "res -= RHS" into "rhs += -RHS" when it seems worthwhile.
2170 vect_is_simple_reduction_1 (loop_vec_info loop_info
, gimple phi
,
2171 bool check_reduction
, bool *double_reduc
,
2174 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
2175 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
2176 edge latch_e
= loop_latch_edge (loop
);
2177 tree loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
2178 gimple def_stmt
, def1
= NULL
, def2
= NULL
;
2179 enum tree_code orig_code
, code
;
2180 tree op1
, op2
, op3
= NULL_TREE
, op4
= NULL_TREE
;
2184 imm_use_iterator imm_iter
;
2185 use_operand_p use_p
;
2188 *double_reduc
= false;
2190 /* If CHECK_REDUCTION is true, we assume inner-most loop vectorization,
2191 otherwise, we assume outer loop vectorization. */
2192 gcc_assert ((check_reduction
&& loop
== vect_loop
)
2193 || (!check_reduction
&& flow_loop_nested_p (vect_loop
, loop
)));
2195 name
= PHI_RESULT (phi
);
2197 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2199 gimple use_stmt
= USE_STMT (use_p
);
2200 if (is_gimple_debug (use_stmt
))
2203 if (!flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2205 if (dump_enabled_p ())
2206 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2207 "intermediate value used outside loop.\n");
2212 if (vinfo_for_stmt (use_stmt
)
2213 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt
)))
2217 if (dump_enabled_p ())
2218 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2219 "reduction used in loop.\n");
2224 if (TREE_CODE (loop_arg
) != SSA_NAME
)
2226 if (dump_enabled_p ())
2228 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2229 "reduction: not ssa_name: ");
2230 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, loop_arg
);
2231 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
2236 def_stmt
= SSA_NAME_DEF_STMT (loop_arg
);
2239 if (dump_enabled_p ())
2240 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2241 "reduction: no def_stmt.\n");
2245 if (!is_gimple_assign (def_stmt
) && gimple_code (def_stmt
) != GIMPLE_PHI
)
2247 if (dump_enabled_p ())
2249 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, def_stmt
, 0);
2250 dump_printf (MSG_NOTE
, "\n");
2255 if (is_gimple_assign (def_stmt
))
2257 name
= gimple_assign_lhs (def_stmt
);
2262 name
= PHI_RESULT (def_stmt
);
2267 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2269 gimple use_stmt
= USE_STMT (use_p
);
2270 if (is_gimple_debug (use_stmt
))
2272 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
))
2273 && vinfo_for_stmt (use_stmt
)
2274 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt
)))
2278 if (dump_enabled_p ())
2279 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2280 "reduction used in loop.\n");
2285 /* If DEF_STMT is a phi node itself, we expect it to have a single argument
2286 defined in the inner loop. */
2289 op1
= PHI_ARG_DEF (def_stmt
, 0);
2291 if (gimple_phi_num_args (def_stmt
) != 1
2292 || TREE_CODE (op1
) != SSA_NAME
)
2294 if (dump_enabled_p ())
2295 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2296 "unsupported phi node definition.\n");
2301 def1
= SSA_NAME_DEF_STMT (op1
);
2302 if (flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2304 && flow_bb_inside_loop_p (loop
->inner
, gimple_bb (def1
))
2305 && is_gimple_assign (def1
))
2307 if (dump_enabled_p ())
2308 report_vect_op (MSG_NOTE
, def_stmt
,
2309 "detected double reduction: ");
2311 *double_reduc
= true;
2318 code
= orig_code
= gimple_assign_rhs_code (def_stmt
);
2320 /* We can handle "res -= x[i]", which is non-associative by
2321 simply rewriting this into "res += -x[i]". Avoid changing
2322 gimple instruction for the first simple tests and only do this
2323 if we're allowed to change code at all. */
2324 if (code
== MINUS_EXPR
2326 && (op1
= gimple_assign_rhs1 (def_stmt
))
2327 && TREE_CODE (op1
) == SSA_NAME
2328 && SSA_NAME_DEF_STMT (op1
) == phi
)
2332 && (!commutative_tree_code (code
) || !associative_tree_code (code
)))
2334 if (dump_enabled_p ())
2335 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2336 "reduction: not commutative/associative: ");
2340 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
2342 if (code
!= COND_EXPR
)
2344 if (dump_enabled_p ())
2345 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2346 "reduction: not binary operation: ");
2351 op3
= gimple_assign_rhs1 (def_stmt
);
2352 if (COMPARISON_CLASS_P (op3
))
2354 op4
= TREE_OPERAND (op3
, 1);
2355 op3
= TREE_OPERAND (op3
, 0);
2358 op1
= gimple_assign_rhs2 (def_stmt
);
2359 op2
= gimple_assign_rhs3 (def_stmt
);
2361 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2363 if (dump_enabled_p ())
2364 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2365 "reduction: uses not ssa_names: ");
2372 op1
= gimple_assign_rhs1 (def_stmt
);
2373 op2
= gimple_assign_rhs2 (def_stmt
);
2375 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2377 if (dump_enabled_p ())
2378 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2379 "reduction: uses not ssa_names: ");
2385 type
= TREE_TYPE (gimple_assign_lhs (def_stmt
));
2386 if ((TREE_CODE (op1
) == SSA_NAME
2387 && !types_compatible_p (type
,TREE_TYPE (op1
)))
2388 || (TREE_CODE (op2
) == SSA_NAME
2389 && !types_compatible_p (type
, TREE_TYPE (op2
)))
2390 || (op3
&& TREE_CODE (op3
) == SSA_NAME
2391 && !types_compatible_p (type
, TREE_TYPE (op3
)))
2392 || (op4
&& TREE_CODE (op4
) == SSA_NAME
2393 && !types_compatible_p (type
, TREE_TYPE (op4
))))
2395 if (dump_enabled_p ())
2397 dump_printf_loc (MSG_NOTE
, vect_location
,
2398 "reduction: multiple types: operation type: ");
2399 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, type
);
2400 dump_printf (MSG_NOTE
, ", operands types: ");
2401 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2403 dump_printf (MSG_NOTE
, ",");
2404 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2408 dump_printf (MSG_NOTE
, ",");
2409 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2415 dump_printf (MSG_NOTE
, ",");
2416 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2419 dump_printf (MSG_NOTE
, "\n");
2425 /* Check that it's ok to change the order of the computation.
2426 Generally, when vectorizing a reduction we change the order of the
2427 computation. This may change the behavior of the program in some
2428 cases, so we need to check that this is ok. One exception is when
2429 vectorizing an outer-loop: the inner-loop is executed sequentially,
2430 and therefore vectorizing reductions in the inner-loop during
2431 outer-loop vectorization is safe. */
2433 /* CHECKME: check for !flag_finite_math_only too? */
2434 if (SCALAR_FLOAT_TYPE_P (type
) && !flag_associative_math
2437 /* Changing the order of operations changes the semantics. */
2438 if (dump_enabled_p ())
2439 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2440 "reduction: unsafe fp math optimization: ");
2443 else if (INTEGRAL_TYPE_P (type
) && TYPE_OVERFLOW_TRAPS (type
)
2446 /* Changing the order of operations changes the semantics. */
2447 if (dump_enabled_p ())
2448 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2449 "reduction: unsafe int math optimization: ");
2452 else if (SAT_FIXED_POINT_TYPE_P (type
) && check_reduction
)
2454 /* Changing the order of operations changes the semantics. */
2455 if (dump_enabled_p ())
2456 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2457 "reduction: unsafe fixed-point math optimization: ");
2461 /* If we detected "res -= x[i]" earlier, rewrite it into
2462 "res += -x[i]" now. If this turns out to be useless reassoc
2463 will clean it up again. */
2464 if (orig_code
== MINUS_EXPR
)
2466 tree rhs
= gimple_assign_rhs2 (def_stmt
);
2467 tree negrhs
= make_ssa_name (TREE_TYPE (rhs
), NULL
);
2468 gimple negate_stmt
= gimple_build_assign_with_ops (NEGATE_EXPR
, negrhs
,
2470 gimple_stmt_iterator gsi
= gsi_for_stmt (def_stmt
);
2471 set_vinfo_for_stmt (negate_stmt
, new_stmt_vec_info (negate_stmt
,
2473 gsi_insert_before (&gsi
, negate_stmt
, GSI_NEW_STMT
);
2474 gimple_assign_set_rhs2 (def_stmt
, negrhs
);
2475 gimple_assign_set_rhs_code (def_stmt
, PLUS_EXPR
);
2476 update_stmt (def_stmt
);
2479 /* Reduction is safe. We're dealing with one of the following:
2480 1) integer arithmetic and no trapv
2481 2) floating point arithmetic, and special flags permit this optimization
2482 3) nested cycle (i.e., outer loop vectorization). */
2483 if (TREE_CODE (op1
) == SSA_NAME
)
2484 def1
= SSA_NAME_DEF_STMT (op1
);
2486 if (TREE_CODE (op2
) == SSA_NAME
)
2487 def2
= SSA_NAME_DEF_STMT (op2
);
2489 if (code
!= COND_EXPR
2490 && ((!def1
|| gimple_nop_p (def1
)) && (!def2
|| gimple_nop_p (def2
))))
2492 if (dump_enabled_p ())
2493 report_vect_op (MSG_NOTE
, def_stmt
, "reduction: no defs for operands: ");
2497 /* Check that one def is the reduction def, defined by PHI,
2498 the other def is either defined in the loop ("vect_internal_def"),
2499 or it's an induction (defined by a loop-header phi-node). */
2501 if (def2
&& def2
== phi
2502 && (code
== COND_EXPR
2503 || !def1
|| gimple_nop_p (def1
)
2504 || !flow_bb_inside_loop_p (loop
, gimple_bb (def1
))
2505 || (def1
&& flow_bb_inside_loop_p (loop
, gimple_bb (def1
))
2506 && (is_gimple_assign (def1
)
2507 || is_gimple_call (def1
)
2508 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
2509 == vect_induction_def
2510 || (gimple_code (def1
) == GIMPLE_PHI
2511 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
2512 == vect_internal_def
2513 && !is_loop_header_bb_p (gimple_bb (def1
)))))))
2515 if (dump_enabled_p ())
2516 report_vect_op (MSG_NOTE
, def_stmt
, "detected reduction: ");
2520 if (def1
&& def1
== phi
2521 && (code
== COND_EXPR
2522 || !def2
|| gimple_nop_p (def2
)
2523 || !flow_bb_inside_loop_p (loop
, gimple_bb (def2
))
2524 || (def2
&& flow_bb_inside_loop_p (loop
, gimple_bb (def2
))
2525 && (is_gimple_assign (def2
)
2526 || is_gimple_call (def2
)
2527 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
2528 == vect_induction_def
2529 || (gimple_code (def2
) == GIMPLE_PHI
2530 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
2531 == vect_internal_def
2532 && !is_loop_header_bb_p (gimple_bb (def2
)))))))
2534 if (check_reduction
)
2536 /* Swap operands (just for simplicity - so that the rest of the code
2537 can assume that the reduction variable is always the last (second)
2539 if (dump_enabled_p ())
2540 report_vect_op (MSG_NOTE
, def_stmt
,
2541 "detected reduction: need to swap operands: ");
2543 swap_ssa_operands (def_stmt
, gimple_assign_rhs1_ptr (def_stmt
),
2544 gimple_assign_rhs2_ptr (def_stmt
));
2546 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (def_stmt
)))
2547 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
2551 if (dump_enabled_p ())
2552 report_vect_op (MSG_NOTE
, def_stmt
, "detected reduction: ");
2558 /* Try to find SLP reduction chain. */
2559 if (check_reduction
&& vect_is_slp_reduction (loop_info
, phi
, def_stmt
))
2561 if (dump_enabled_p ())
2562 report_vect_op (MSG_NOTE
, def_stmt
,
2563 "reduction: detected reduction chain: ");
2568 if (dump_enabled_p ())
2569 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2570 "reduction: unknown pattern: ");
2575 /* Wrapper around vect_is_simple_reduction_1, that won't modify code
2576 in-place. Arguments as there. */
2579 vect_is_simple_reduction (loop_vec_info loop_info
, gimple phi
,
2580 bool check_reduction
, bool *double_reduc
)
2582 return vect_is_simple_reduction_1 (loop_info
, phi
, check_reduction
,
2583 double_reduc
, false);
2586 /* Wrapper around vect_is_simple_reduction_1, which will modify code
2587 in-place if it enables detection of more reductions. Arguments
2591 vect_force_simple_reduction (loop_vec_info loop_info
, gimple phi
,
2592 bool check_reduction
, bool *double_reduc
)
2594 return vect_is_simple_reduction_1 (loop_info
, phi
, check_reduction
,
2595 double_reduc
, true);
2598 /* Calculate the cost of one scalar iteration of the loop. */
2600 vect_get_single_scalar_iteration_cost (loop_vec_info loop_vinfo
)
2602 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2603 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
2604 int nbbs
= loop
->num_nodes
, factor
, scalar_single_iter_cost
= 0;
2605 int innerloop_iters
, i
, stmt_cost
;
2607 /* Count statements in scalar loop. Using this as scalar cost for a single
2610 TODO: Add outer loop support.
2612 TODO: Consider assigning different costs to different scalar
2616 innerloop_iters
= 1;
2618 innerloop_iters
= 50; /* FIXME */
2620 for (i
= 0; i
< nbbs
; i
++)
2622 gimple_stmt_iterator si
;
2623 basic_block bb
= bbs
[i
];
2625 if (bb
->loop_father
== loop
->inner
)
2626 factor
= innerloop_iters
;
2630 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
2632 gimple stmt
= gsi_stmt (si
);
2633 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2635 if (!is_gimple_assign (stmt
) && !is_gimple_call (stmt
))
2638 /* Skip stmts that are not vectorized inside the loop. */
2640 && !STMT_VINFO_RELEVANT_P (stmt_info
)
2641 && (!STMT_VINFO_LIVE_P (stmt_info
)
2642 || !VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
2643 && !STMT_VINFO_IN_PATTERN_P (stmt_info
))
2646 if (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
)))
2648 if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))))
2649 stmt_cost
= vect_get_stmt_cost (scalar_load
);
2651 stmt_cost
= vect_get_stmt_cost (scalar_store
);
2654 stmt_cost
= vect_get_stmt_cost (scalar_stmt
);
2656 scalar_single_iter_cost
+= stmt_cost
* factor
;
2659 return scalar_single_iter_cost
;
2662 /* Calculate cost of peeling the loop PEEL_ITERS_PROLOGUE times. */
2664 vect_get_known_peeling_cost (loop_vec_info loop_vinfo
, int peel_iters_prologue
,
2665 int *peel_iters_epilogue
,
2666 int scalar_single_iter_cost
,
2667 stmt_vector_for_cost
*prologue_cost_vec
,
2668 stmt_vector_for_cost
*epilogue_cost_vec
)
2671 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2673 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
2675 *peel_iters_epilogue
= vf
/2;
2676 if (dump_enabled_p ())
2677 dump_printf_loc (MSG_NOTE
, vect_location
,
2678 "cost model: epilogue peel iters set to vf/2 "
2679 "because loop iterations are unknown .\n");
2681 /* If peeled iterations are known but number of scalar loop
2682 iterations are unknown, count a taken branch per peeled loop. */
2683 retval
= record_stmt_cost (prologue_cost_vec
, 2, cond_branch_taken
,
2684 NULL
, 0, vect_prologue
);
2688 int niters
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
2689 peel_iters_prologue
= niters
< peel_iters_prologue
?
2690 niters
: peel_iters_prologue
;
2691 *peel_iters_epilogue
= (niters
- peel_iters_prologue
) % vf
;
2692 /* If we need to peel for gaps, but no peeling is required, we have to
2693 peel VF iterations. */
2694 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) && !*peel_iters_epilogue
)
2695 *peel_iters_epilogue
= vf
;
2698 if (peel_iters_prologue
)
2699 retval
+= record_stmt_cost (prologue_cost_vec
,
2700 peel_iters_prologue
* scalar_single_iter_cost
,
2701 scalar_stmt
, NULL
, 0, vect_prologue
);
2702 if (*peel_iters_epilogue
)
2703 retval
+= record_stmt_cost (epilogue_cost_vec
,
2704 *peel_iters_epilogue
* scalar_single_iter_cost
,
2705 scalar_stmt
, NULL
, 0, vect_epilogue
);
2709 /* Function vect_estimate_min_profitable_iters
2711 Return the number of iterations required for the vector version of the
2712 loop to be profitable relative to the cost of the scalar version of the
2716 vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo
,
2717 int *ret_min_profitable_niters
,
2718 int *ret_min_profitable_estimate
)
2720 int min_profitable_iters
;
2721 int min_profitable_estimate
;
2722 int peel_iters_prologue
;
2723 int peel_iters_epilogue
;
2724 unsigned vec_inside_cost
= 0;
2725 int vec_outside_cost
= 0;
2726 unsigned vec_prologue_cost
= 0;
2727 unsigned vec_epilogue_cost
= 0;
2728 int scalar_single_iter_cost
= 0;
2729 int scalar_outside_cost
= 0;
2730 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2731 int npeel
= LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
);
2732 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2734 /* Cost model disabled. */
2735 if (unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo
)))
2737 dump_printf_loc (MSG_NOTE
, vect_location
, "cost model disabled.\n");
2738 *ret_min_profitable_niters
= 0;
2739 *ret_min_profitable_estimate
= 0;
2743 /* Requires loop versioning tests to handle misalignment. */
2744 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
))
2746 /* FIXME: Make cost depend on complexity of individual check. */
2747 unsigned len
= LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).length ();
2748 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
2750 dump_printf (MSG_NOTE
,
2751 "cost model: Adding cost of checks for loop "
2752 "versioning to treat misalignment.\n");
2755 /* Requires loop versioning with alias checks. */
2756 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2758 /* FIXME: Make cost depend on complexity of individual check. */
2759 unsigned len
= LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
).length ();
2760 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
2762 dump_printf (MSG_NOTE
,
2763 "cost model: Adding cost of checks for loop "
2764 "versioning aliasing.\n");
2767 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2768 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2769 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_taken
, NULL
, 0,
2772 /* Count statements in scalar loop. Using this as scalar cost for a single
2775 TODO: Add outer loop support.
2777 TODO: Consider assigning different costs to different scalar
2780 scalar_single_iter_cost
= vect_get_single_scalar_iteration_cost (loop_vinfo
);
2782 /* Add additional cost for the peeled instructions in prologue and epilogue
2785 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
2786 at compile-time - we assume it's vf/2 (the worst would be vf-1).
2788 TODO: Build an expression that represents peel_iters for prologue and
2789 epilogue to be used in a run-time test. */
2793 peel_iters_prologue
= vf
/2;
2794 dump_printf (MSG_NOTE
, "cost model: "
2795 "prologue peel iters set to vf/2.\n");
2797 /* If peeling for alignment is unknown, loop bound of main loop becomes
2799 peel_iters_epilogue
= vf
/2;
2800 dump_printf (MSG_NOTE
, "cost model: "
2801 "epilogue peel iters set to vf/2 because "
2802 "peeling for alignment is unknown.\n");
2804 /* If peeled iterations are unknown, count a taken branch and a not taken
2805 branch per peeled loop. Even if scalar loop iterations are known,
2806 vector iterations are not known since peeled prologue iterations are
2807 not known. Hence guards remain the same. */
2808 (void) add_stmt_cost (target_cost_data
, 2, cond_branch_taken
,
2809 NULL
, 0, vect_prologue
);
2810 (void) add_stmt_cost (target_cost_data
, 2, cond_branch_not_taken
,
2811 NULL
, 0, vect_prologue
);
2812 /* FORNOW: Don't attempt to pass individual scalar instructions to
2813 the model; just assume linear cost for scalar iterations. */
2814 (void) add_stmt_cost (target_cost_data
,
2815 peel_iters_prologue
* scalar_single_iter_cost
,
2816 scalar_stmt
, NULL
, 0, vect_prologue
);
2817 (void) add_stmt_cost (target_cost_data
,
2818 peel_iters_epilogue
* scalar_single_iter_cost
,
2819 scalar_stmt
, NULL
, 0, vect_epilogue
);
2823 stmt_vector_for_cost prologue_cost_vec
, epilogue_cost_vec
;
2824 stmt_info_for_cost
*si
;
2826 void *data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2828 prologue_cost_vec
.create (2);
2829 epilogue_cost_vec
.create (2);
2830 peel_iters_prologue
= npeel
;
2832 (void) vect_get_known_peeling_cost (loop_vinfo
, peel_iters_prologue
,
2833 &peel_iters_epilogue
,
2834 scalar_single_iter_cost
,
2836 &epilogue_cost_vec
);
2838 FOR_EACH_VEC_ELT (prologue_cost_vec
, j
, si
)
2840 struct _stmt_vec_info
*stmt_info
2841 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
2842 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
2843 si
->misalign
, vect_prologue
);
2846 FOR_EACH_VEC_ELT (epilogue_cost_vec
, j
, si
)
2848 struct _stmt_vec_info
*stmt_info
2849 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
2850 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
2851 si
->misalign
, vect_epilogue
);
2854 prologue_cost_vec
.release ();
2855 epilogue_cost_vec
.release ();
2858 /* FORNOW: The scalar outside cost is incremented in one of the
2861 1. The vectorizer checks for alignment and aliasing and generates
2862 a condition that allows dynamic vectorization. A cost model
2863 check is ANDED with the versioning condition. Hence scalar code
2864 path now has the added cost of the versioning check.
2866 if (cost > th & versioning_check)
2869 Hence run-time scalar is incremented by not-taken branch cost.
2871 2. The vectorizer then checks if a prologue is required. If the
2872 cost model check was not done before during versioning, it has to
2873 be done before the prologue check.
2876 prologue = scalar_iters
2881 if (prologue == num_iters)
2884 Hence the run-time scalar cost is incremented by a taken branch,
2885 plus a not-taken branch, plus a taken branch cost.
2887 3. The vectorizer then checks if an epilogue is required. If the
2888 cost model check was not done before during prologue check, it
2889 has to be done with the epilogue check.
2895 if (prologue == num_iters)
2898 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
2901 Hence the run-time scalar cost should be incremented by 2 taken
2904 TODO: The back end may reorder the BBS's differently and reverse
2905 conditions/branch directions. Change the estimates below to
2906 something more reasonable. */
2908 /* If the number of iterations is known and we do not do versioning, we can
2909 decide whether to vectorize at compile time. Hence the scalar version
2910 do not carry cost model guard costs. */
2911 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
2912 || LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2913 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2915 /* Cost model check occurs at versioning. */
2916 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2917 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2918 scalar_outside_cost
+= vect_get_stmt_cost (cond_branch_not_taken
);
2921 /* Cost model check occurs at prologue generation. */
2922 if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
) < 0)
2923 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
)
2924 + vect_get_stmt_cost (cond_branch_not_taken
);
2925 /* Cost model check occurs at epilogue generation. */
2927 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
);
2931 /* Complete the target-specific cost calculations. */
2932 finish_cost (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
), &vec_prologue_cost
,
2933 &vec_inside_cost
, &vec_epilogue_cost
);
2935 vec_outside_cost
= (int)(vec_prologue_cost
+ vec_epilogue_cost
);
2937 /* Calculate number of iterations required to make the vector version
2938 profitable, relative to the loop bodies only. The following condition
2940 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
2942 SIC = scalar iteration cost, VIC = vector iteration cost,
2943 VOC = vector outside cost, VF = vectorization factor,
2944 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
2945 SOC = scalar outside cost for run time cost model check. */
2947 if ((scalar_single_iter_cost
* vf
) > (int) vec_inside_cost
)
2949 if (vec_outside_cost
<= 0)
2950 min_profitable_iters
= 1;
2953 min_profitable_iters
= ((vec_outside_cost
- scalar_outside_cost
) * vf
2954 - vec_inside_cost
* peel_iters_prologue
2955 - vec_inside_cost
* peel_iters_epilogue
)
2956 / ((scalar_single_iter_cost
* vf
)
2959 if ((scalar_single_iter_cost
* vf
* min_profitable_iters
)
2960 <= (((int) vec_inside_cost
* min_profitable_iters
)
2961 + (((int) vec_outside_cost
- scalar_outside_cost
) * vf
)))
2962 min_profitable_iters
++;
2965 /* vector version will never be profitable. */
2968 if (LOOP_VINFO_LOOP (loop_vinfo
)->force_vect
)
2969 warning_at (vect_location
, OPT_Wopenmp_simd
, "vectorization "
2970 "did not happen for a simd loop");
2972 if (dump_enabled_p ())
2973 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2974 "cost model: the vector iteration cost = %d "
2975 "divided by the scalar iteration cost = %d "
2976 "is greater or equal to the vectorization factor = %d"
2978 vec_inside_cost
, scalar_single_iter_cost
, vf
);
2979 *ret_min_profitable_niters
= -1;
2980 *ret_min_profitable_estimate
= -1;
2984 if (dump_enabled_p ())
2986 dump_printf_loc (MSG_NOTE
, vect_location
, "Cost model analysis: \n");
2987 dump_printf (MSG_NOTE
, " Vector inside of loop cost: %d\n",
2989 dump_printf (MSG_NOTE
, " Vector prologue cost: %d\n",
2991 dump_printf (MSG_NOTE
, " Vector epilogue cost: %d\n",
2993 dump_printf (MSG_NOTE
, " Scalar iteration cost: %d\n",
2994 scalar_single_iter_cost
);
2995 dump_printf (MSG_NOTE
, " Scalar outside cost: %d\n",
2996 scalar_outside_cost
);
2997 dump_printf (MSG_NOTE
, " Vector outside cost: %d\n",
2999 dump_printf (MSG_NOTE
, " prologue iterations: %d\n",
3000 peel_iters_prologue
);
3001 dump_printf (MSG_NOTE
, " epilogue iterations: %d\n",
3002 peel_iters_epilogue
);
3003 dump_printf (MSG_NOTE
,
3004 " Calculated minimum iters for profitability: %d\n",
3005 min_profitable_iters
);
3006 dump_printf (MSG_NOTE
, "\n");
3009 min_profitable_iters
=
3010 min_profitable_iters
< vf
? vf
: min_profitable_iters
;
3012 /* Because the condition we create is:
3013 if (niters <= min_profitable_iters)
3014 then skip the vectorized loop. */
3015 min_profitable_iters
--;
3017 if (dump_enabled_p ())
3018 dump_printf_loc (MSG_NOTE
, vect_location
,
3019 " Runtime profitability threshold = %d\n",
3020 min_profitable_iters
);
3022 *ret_min_profitable_niters
= min_profitable_iters
;
3024 /* Calculate number of iterations required to make the vector version
3025 profitable, relative to the loop bodies only.
3027 Non-vectorized variant is SIC * niters and it must win over vector
3028 variant on the expected loop trip count. The following condition must hold true:
3029 SIC * niters > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC + SOC */
3031 if (vec_outside_cost
<= 0)
3032 min_profitable_estimate
= 1;
3035 min_profitable_estimate
= ((vec_outside_cost
+ scalar_outside_cost
) * vf
3036 - vec_inside_cost
* peel_iters_prologue
3037 - vec_inside_cost
* peel_iters_epilogue
)
3038 / ((scalar_single_iter_cost
* vf
)
3041 min_profitable_estimate
--;
3042 min_profitable_estimate
= MAX (min_profitable_estimate
, min_profitable_iters
);
3043 if (dump_enabled_p ())
3044 dump_printf_loc (MSG_NOTE
, vect_location
,
3045 " Static estimate profitability threshold = %d\n",
3046 min_profitable_iters
);
3048 *ret_min_profitable_estimate
= min_profitable_estimate
;
3052 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
3053 functions. Design better to avoid maintenance issues. */
3055 /* Function vect_model_reduction_cost.
3057 Models cost for a reduction operation, including the vector ops
3058 generated within the strip-mine loop, the initial definition before
3059 the loop, and the epilogue code that must be generated. */
3062 vect_model_reduction_cost (stmt_vec_info stmt_info
, enum tree_code reduc_code
,
3065 int prologue_cost
= 0, epilogue_cost
= 0;
3066 enum tree_code code
;
3069 gimple stmt
, orig_stmt
;
3071 enum machine_mode mode
;
3072 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3073 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3074 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3076 /* Cost of reduction op inside loop. */
3077 unsigned inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
3078 stmt_info
, 0, vect_body
);
3079 stmt
= STMT_VINFO_STMT (stmt_info
);
3081 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3083 case GIMPLE_SINGLE_RHS
:
3084 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
)) == ternary_op
);
3085 reduction_op
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
3087 case GIMPLE_UNARY_RHS
:
3088 reduction_op
= gimple_assign_rhs1 (stmt
);
3090 case GIMPLE_BINARY_RHS
:
3091 reduction_op
= gimple_assign_rhs2 (stmt
);
3093 case GIMPLE_TERNARY_RHS
:
3094 reduction_op
= gimple_assign_rhs3 (stmt
);
3100 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
3103 if (dump_enabled_p ())
3105 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3106 "unsupported data-type ");
3107 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
3108 TREE_TYPE (reduction_op
));
3109 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3114 mode
= TYPE_MODE (vectype
);
3115 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
3118 orig_stmt
= STMT_VINFO_STMT (stmt_info
);
3120 code
= gimple_assign_rhs_code (orig_stmt
);
3122 /* Add in cost for initial definition. */
3123 prologue_cost
+= add_stmt_cost (target_cost_data
, 1, scalar_to_vec
,
3124 stmt_info
, 0, vect_prologue
);
3126 /* Determine cost of epilogue code.
3128 We have a reduction operator that will reduce the vector in one statement.
3129 Also requires scalar extract. */
3131 if (!nested_in_vect_loop_p (loop
, orig_stmt
))
3133 if (reduc_code
!= ERROR_MARK
)
3135 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1, vector_stmt
,
3136 stmt_info
, 0, vect_epilogue
);
3137 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1, vec_to_scalar
,
3138 stmt_info
, 0, vect_epilogue
);
3142 int vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
3144 TYPE_SIZE (TREE_TYPE (gimple_assign_lhs (orig_stmt
)));
3145 int element_bitsize
= tree_to_uhwi (bitsize
);
3146 int nelements
= vec_size_in_bits
/ element_bitsize
;
3148 optab
= optab_for_tree_code (code
, vectype
, optab_default
);
3150 /* We have a whole vector shift available. */
3151 if (VECTOR_MODE_P (mode
)
3152 && optab_handler (optab
, mode
) != CODE_FOR_nothing
3153 && optab_handler (vec_shr_optab
, mode
) != CODE_FOR_nothing
)
3155 /* Final reduction via vector shifts and the reduction operator.
3156 Also requires scalar extract. */
3157 epilogue_cost
+= add_stmt_cost (target_cost_data
,
3158 exact_log2 (nelements
) * 2,
3159 vector_stmt
, stmt_info
, 0,
3161 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1,
3162 vec_to_scalar
, stmt_info
, 0,
3166 /* Use extracts and reduction op for final reduction. For N
3167 elements, we have N extracts and N-1 reduction ops. */
3168 epilogue_cost
+= add_stmt_cost (target_cost_data
,
3169 nelements
+ nelements
- 1,
3170 vector_stmt
, stmt_info
, 0,
3175 if (dump_enabled_p ())
3176 dump_printf (MSG_NOTE
,
3177 "vect_model_reduction_cost: inside_cost = %d, "
3178 "prologue_cost = %d, epilogue_cost = %d .\n", inside_cost
,
3179 prologue_cost
, epilogue_cost
);
3185 /* Function vect_model_induction_cost.
3187 Models cost for induction operations. */
3190 vect_model_induction_cost (stmt_vec_info stmt_info
, int ncopies
)
3192 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3193 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3194 unsigned inside_cost
, prologue_cost
;
3196 /* loop cost for vec_loop. */
3197 inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
3198 stmt_info
, 0, vect_body
);
3200 /* prologue cost for vec_init and vec_step. */
3201 prologue_cost
= add_stmt_cost (target_cost_data
, 2, scalar_to_vec
,
3202 stmt_info
, 0, vect_prologue
);
3204 if (dump_enabled_p ())
3205 dump_printf_loc (MSG_NOTE
, vect_location
,
3206 "vect_model_induction_cost: inside_cost = %d, "
3207 "prologue_cost = %d .\n", inside_cost
, prologue_cost
);
3211 /* Function get_initial_def_for_induction
3214 STMT - a stmt that performs an induction operation in the loop.
3215 IV_PHI - the initial value of the induction variable
3218 Return a vector variable, initialized with the first VF values of
3219 the induction variable. E.g., for an iv with IV_PHI='X' and
3220 evolution S, for a vector of 4 units, we want to return:
3221 [X, X + S, X + 2*S, X + 3*S]. */
3224 get_initial_def_for_induction (gimple iv_phi
)
3226 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (iv_phi
);
3227 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
3228 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3231 edge pe
= loop_preheader_edge (loop
);
3232 struct loop
*iv_loop
;
3234 tree new_vec
, vec_init
, vec_step
, t
;
3237 gimple init_stmt
, induction_phi
, new_stmt
;
3238 tree induc_def
, vec_def
, vec_dest
;
3239 tree init_expr
, step_expr
;
3240 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3244 stmt_vec_info phi_info
= vinfo_for_stmt (iv_phi
);
3245 bool nested_in_vect_loop
= false;
3246 gimple_seq stmts
= NULL
;
3247 imm_use_iterator imm_iter
;
3248 use_operand_p use_p
;
3252 gimple_stmt_iterator si
;
3253 basic_block bb
= gimple_bb (iv_phi
);
3257 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
3258 if (nested_in_vect_loop_p (loop
, iv_phi
))
3260 nested_in_vect_loop
= true;
3261 iv_loop
= loop
->inner
;
3265 gcc_assert (iv_loop
== (gimple_bb (iv_phi
))->loop_father
);
3267 latch_e
= loop_latch_edge (iv_loop
);
3268 loop_arg
= PHI_ARG_DEF_FROM_EDGE (iv_phi
, latch_e
);
3270 step_expr
= STMT_VINFO_LOOP_PHI_EVOLUTION_PART (phi_info
);
3271 gcc_assert (step_expr
!= NULL_TREE
);
3273 pe
= loop_preheader_edge (iv_loop
);
3274 init_expr
= PHI_ARG_DEF_FROM_EDGE (iv_phi
,
3275 loop_preheader_edge (iv_loop
));
3277 vectype
= get_vectype_for_scalar_type (TREE_TYPE (init_expr
));
3278 resvectype
= get_vectype_for_scalar_type (TREE_TYPE (PHI_RESULT (iv_phi
)));
3279 gcc_assert (vectype
);
3280 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3281 ncopies
= vf
/ nunits
;
3283 gcc_assert (phi_info
);
3284 gcc_assert (ncopies
>= 1);
3286 /* Convert the step to the desired type. */
3287 step_expr
= force_gimple_operand (fold_convert (TREE_TYPE (vectype
),
3289 &stmts
, true, NULL_TREE
);
3292 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
3293 gcc_assert (!new_bb
);
3296 /* Find the first insertion point in the BB. */
3297 si
= gsi_after_labels (bb
);
3299 /* Create the vector that holds the initial_value of the induction. */
3300 if (nested_in_vect_loop
)
3302 /* iv_loop is nested in the loop to be vectorized. init_expr had already
3303 been created during vectorization of previous stmts. We obtain it
3304 from the STMT_VINFO_VEC_STMT of the defining stmt. */
3305 vec_init
= vect_get_vec_def_for_operand (init_expr
, iv_phi
, NULL
);
3306 /* If the initial value is not of proper type, convert it. */
3307 if (!useless_type_conversion_p (vectype
, TREE_TYPE (vec_init
)))
3309 new_stmt
= gimple_build_assign_with_ops
3311 vect_get_new_vect_var (vectype
, vect_simple_var
, "vec_iv_"),
3312 build1 (VIEW_CONVERT_EXPR
, vectype
, vec_init
), NULL_TREE
);
3313 vec_init
= make_ssa_name (gimple_assign_lhs (new_stmt
), new_stmt
);
3314 gimple_assign_set_lhs (new_stmt
, vec_init
);
3315 new_bb
= gsi_insert_on_edge_immediate (loop_preheader_edge (iv_loop
),
3317 gcc_assert (!new_bb
);
3318 set_vinfo_for_stmt (new_stmt
,
3319 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
3324 vec
<constructor_elt
, va_gc
> *v
;
3326 /* iv_loop is the loop to be vectorized. Create:
3327 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
3328 new_var
= vect_get_new_vect_var (TREE_TYPE (vectype
),
3329 vect_scalar_var
, "var_");
3330 new_name
= force_gimple_operand (fold_convert (TREE_TYPE (vectype
),
3332 &stmts
, false, new_var
);
3335 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
3336 gcc_assert (!new_bb
);
3339 vec_alloc (v
, nunits
);
3340 bool constant_p
= is_gimple_min_invariant (new_name
);
3341 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
3342 for (i
= 1; i
< nunits
; i
++)
3344 /* Create: new_name_i = new_name + step_expr */
3345 new_name
= fold_build2 (PLUS_EXPR
, TREE_TYPE (new_name
),
3346 new_name
, step_expr
);
3347 if (!is_gimple_min_invariant (new_name
))
3349 init_stmt
= gimple_build_assign (new_var
, new_name
);
3350 new_name
= make_ssa_name (new_var
, init_stmt
);
3351 gimple_assign_set_lhs (init_stmt
, new_name
);
3352 new_bb
= gsi_insert_on_edge_immediate (pe
, init_stmt
);
3353 gcc_assert (!new_bb
);
3354 if (dump_enabled_p ())
3356 dump_printf_loc (MSG_NOTE
, vect_location
,
3357 "created new init_stmt: ");
3358 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, init_stmt
, 0);
3359 dump_printf (MSG_NOTE
, "\n");
3363 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
3365 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
3367 new_vec
= build_vector_from_ctor (vectype
, v
);
3369 new_vec
= build_constructor (vectype
, v
);
3370 vec_init
= vect_init_vector (iv_phi
, new_vec
, vectype
, NULL
);
3374 /* Create the vector that holds the step of the induction. */
3375 if (nested_in_vect_loop
)
3376 /* iv_loop is nested in the loop to be vectorized. Generate:
3377 vec_step = [S, S, S, S] */
3378 new_name
= step_expr
;
3381 /* iv_loop is the loop to be vectorized. Generate:
3382 vec_step = [VF*S, VF*S, VF*S, VF*S] */
3383 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
)))
3385 expr
= build_int_cst (integer_type_node
, vf
);
3386 expr
= fold_convert (TREE_TYPE (step_expr
), expr
);
3389 expr
= build_int_cst (TREE_TYPE (step_expr
), vf
);
3390 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
3392 if (TREE_CODE (step_expr
) == SSA_NAME
)
3393 new_name
= vect_init_vector (iv_phi
, new_name
,
3394 TREE_TYPE (step_expr
), NULL
);
3397 t
= unshare_expr (new_name
);
3398 gcc_assert (CONSTANT_CLASS_P (new_name
)
3399 || TREE_CODE (new_name
) == SSA_NAME
);
3400 stepvectype
= get_vectype_for_scalar_type (TREE_TYPE (new_name
));
3401 gcc_assert (stepvectype
);
3402 new_vec
= build_vector_from_val (stepvectype
, t
);
3403 vec_step
= vect_init_vector (iv_phi
, new_vec
, stepvectype
, NULL
);
3406 /* Create the following def-use cycle:
3411 vec_iv = PHI <vec_init, vec_loop>
3415 vec_loop = vec_iv + vec_step; */
3417 /* Create the induction-phi that defines the induction-operand. */
3418 vec_dest
= vect_get_new_vect_var (vectype
, vect_simple_var
, "vec_iv_");
3419 induction_phi
= create_phi_node (vec_dest
, iv_loop
->header
);
3420 set_vinfo_for_stmt (induction_phi
,
3421 new_stmt_vec_info (induction_phi
, loop_vinfo
, NULL
));
3422 induc_def
= PHI_RESULT (induction_phi
);
3424 /* Create the iv update inside the loop */
3425 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, vec_dest
,
3426 induc_def
, vec_step
);
3427 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
3428 gimple_assign_set_lhs (new_stmt
, vec_def
);
3429 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3430 set_vinfo_for_stmt (new_stmt
, new_stmt_vec_info (new_stmt
, loop_vinfo
,
3433 /* Set the arguments of the phi node: */
3434 add_phi_arg (induction_phi
, vec_init
, pe
, UNKNOWN_LOCATION
);
3435 add_phi_arg (induction_phi
, vec_def
, loop_latch_edge (iv_loop
),
3439 /* In case that vectorization factor (VF) is bigger than the number
3440 of elements that we can fit in a vectype (nunits), we have to generate
3441 more than one vector stmt - i.e - we need to "unroll" the
3442 vector stmt by a factor VF/nunits. For more details see documentation
3443 in vectorizable_operation. */
3447 stmt_vec_info prev_stmt_vinfo
;
3448 /* FORNOW. This restriction should be relaxed. */
3449 gcc_assert (!nested_in_vect_loop
);
3451 /* Create the vector that holds the step of the induction. */
3452 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr
)))
3454 expr
= build_int_cst (integer_type_node
, nunits
);
3455 expr
= fold_convert (TREE_TYPE (step_expr
), expr
);
3458 expr
= build_int_cst (TREE_TYPE (step_expr
), nunits
);
3459 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
3461 if (TREE_CODE (step_expr
) == SSA_NAME
)
3462 new_name
= vect_init_vector (iv_phi
, new_name
,
3463 TREE_TYPE (step_expr
), NULL
);
3464 t
= unshare_expr (new_name
);
3465 gcc_assert (CONSTANT_CLASS_P (new_name
)
3466 || TREE_CODE (new_name
) == SSA_NAME
);
3467 new_vec
= build_vector_from_val (stepvectype
, t
);
3468 vec_step
= vect_init_vector (iv_phi
, new_vec
, stepvectype
, NULL
);
3470 vec_def
= induc_def
;
3471 prev_stmt_vinfo
= vinfo_for_stmt (induction_phi
);
3472 for (i
= 1; i
< ncopies
; i
++)
3474 /* vec_i = vec_prev + vec_step */
3475 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, vec_dest
,
3477 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
3478 gimple_assign_set_lhs (new_stmt
, vec_def
);
3480 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3481 if (!useless_type_conversion_p (resvectype
, vectype
))
3483 new_stmt
= gimple_build_assign_with_ops
3485 vect_get_new_vect_var (resvectype
, vect_simple_var
,
3487 build1 (VIEW_CONVERT_EXPR
, resvectype
,
3488 gimple_assign_lhs (new_stmt
)), NULL_TREE
);
3489 gimple_assign_set_lhs (new_stmt
,
3491 (gimple_assign_lhs (new_stmt
), new_stmt
));
3492 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3494 set_vinfo_for_stmt (new_stmt
,
3495 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
3496 STMT_VINFO_RELATED_STMT (prev_stmt_vinfo
) = new_stmt
;
3497 prev_stmt_vinfo
= vinfo_for_stmt (new_stmt
);
3501 if (nested_in_vect_loop
)
3503 /* Find the loop-closed exit-phi of the induction, and record
3504 the final vector of induction results: */
3506 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
3508 if (!flow_bb_inside_loop_p (iv_loop
, gimple_bb (USE_STMT (use_p
))))
3510 exit_phi
= USE_STMT (use_p
);
3516 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (exit_phi
);
3517 /* FORNOW. Currently not supporting the case that an inner-loop induction
3518 is not used in the outer-loop (i.e. only outside the outer-loop). */
3519 gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo
)
3520 && !STMT_VINFO_LIVE_P (stmt_vinfo
));
3522 STMT_VINFO_VEC_STMT (stmt_vinfo
) = new_stmt
;
3523 if (dump_enabled_p ())
3525 dump_printf_loc (MSG_NOTE
, vect_location
,
3526 "vector of inductions after inner-loop:");
3527 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, new_stmt
, 0);
3528 dump_printf (MSG_NOTE
, "\n");
3534 if (dump_enabled_p ())
3536 dump_printf_loc (MSG_NOTE
, vect_location
,
3537 "transform induction: created def-use cycle: ");
3538 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, induction_phi
, 0);
3539 dump_printf (MSG_NOTE
, "\n");
3540 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
3541 SSA_NAME_DEF_STMT (vec_def
), 0);
3542 dump_printf (MSG_NOTE
, "\n");
3545 STMT_VINFO_VEC_STMT (phi_info
) = induction_phi
;
3546 if (!useless_type_conversion_p (resvectype
, vectype
))
3548 new_stmt
= gimple_build_assign_with_ops
3550 vect_get_new_vect_var (resvectype
, vect_simple_var
, "vec_iv_"),
3551 build1 (VIEW_CONVERT_EXPR
, resvectype
, induc_def
), NULL_TREE
);
3552 induc_def
= make_ssa_name (gimple_assign_lhs (new_stmt
), new_stmt
);
3553 gimple_assign_set_lhs (new_stmt
, induc_def
);
3554 si
= gsi_after_labels (bb
);
3555 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3556 set_vinfo_for_stmt (new_stmt
,
3557 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
3558 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_stmt
))
3559 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (induction_phi
));
3566 /* Function get_initial_def_for_reduction
3569 STMT - a stmt that performs a reduction operation in the loop.
3570 INIT_VAL - the initial value of the reduction variable
3573 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
3574 of the reduction (used for adjusting the epilog - see below).
3575 Return a vector variable, initialized according to the operation that STMT
3576 performs. This vector will be used as the initial value of the
3577 vector of partial results.
3579 Option1 (adjust in epilog): Initialize the vector as follows:
3580 add/bit or/xor: [0,0,...,0,0]
3581 mult/bit and: [1,1,...,1,1]
3582 min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
3583 and when necessary (e.g. add/mult case) let the caller know
3584 that it needs to adjust the result by init_val.
3586 Option2: Initialize the vector as follows:
3587 add/bit or/xor: [init_val,0,0,...,0]
3588 mult/bit and: [init_val,1,1,...,1]
3589 min/max/cond_expr: [init_val,init_val,...,init_val]
3590 and no adjustments are needed.
3592 For example, for the following code:
3598 STMT is 's = s + a[i]', and the reduction variable is 's'.
3599 For a vector of 4 units, we want to return either [0,0,0,init_val],
3600 or [0,0,0,0] and let the caller know that it needs to adjust
3601 the result at the end by 'init_val'.
3603 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
3604 initialization vector is simpler (same element in all entries), if
3605 ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
3607 A cost model should help decide between these two schemes. */
3610 get_initial_def_for_reduction (gimple stmt
, tree init_val
,
3611 tree
*adjustment_def
)
3613 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
3614 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
3615 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3616 tree scalar_type
= TREE_TYPE (init_val
);
3617 tree vectype
= get_vectype_for_scalar_type (scalar_type
);
3619 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3624 bool nested_in_vect_loop
= false;
3626 REAL_VALUE_TYPE real_init_val
= dconst0
;
3627 int int_init_val
= 0;
3628 gimple def_stmt
= NULL
;
3630 gcc_assert (vectype
);
3631 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3633 gcc_assert (POINTER_TYPE_P (scalar_type
) || INTEGRAL_TYPE_P (scalar_type
)
3634 || SCALAR_FLOAT_TYPE_P (scalar_type
));
3636 if (nested_in_vect_loop_p (loop
, stmt
))
3637 nested_in_vect_loop
= true;
3639 gcc_assert (loop
== (gimple_bb (stmt
))->loop_father
);
3641 /* In case of double reduction we only create a vector variable to be put
3642 in the reduction phi node. The actual statement creation is done in
3643 vect_create_epilog_for_reduction. */
3644 if (adjustment_def
&& nested_in_vect_loop
3645 && TREE_CODE (init_val
) == SSA_NAME
3646 && (def_stmt
= SSA_NAME_DEF_STMT (init_val
))
3647 && gimple_code (def_stmt
) == GIMPLE_PHI
3648 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
3649 && vinfo_for_stmt (def_stmt
)
3650 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
3651 == vect_double_reduction_def
)
3653 *adjustment_def
= NULL
;
3654 return vect_create_destination_var (init_val
, vectype
);
3657 if (TREE_CONSTANT (init_val
))
3659 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
3660 init_value
= build_real (scalar_type
, TREE_REAL_CST (init_val
));
3662 init_value
= build_int_cst (scalar_type
, TREE_INT_CST_LOW (init_val
));
3665 init_value
= init_val
;
3669 case WIDEN_SUM_EXPR
:
3677 /* ADJUSMENT_DEF is NULL when called from
3678 vect_create_epilog_for_reduction to vectorize double reduction. */
3681 if (nested_in_vect_loop
)
3682 *adjustment_def
= vect_get_vec_def_for_operand (init_val
, stmt
,
3685 *adjustment_def
= init_val
;
3688 if (code
== MULT_EXPR
)
3690 real_init_val
= dconst1
;
3694 if (code
== BIT_AND_EXPR
)
3697 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
3698 def_for_init
= build_real (scalar_type
, real_init_val
);
3700 def_for_init
= build_int_cst (scalar_type
, int_init_val
);
3702 /* Create a vector of '0' or '1' except the first element. */
3703 elts
= XALLOCAVEC (tree
, nunits
);
3704 for (i
= nunits
- 2; i
>= 0; --i
)
3705 elts
[i
+ 1] = def_for_init
;
3707 /* Option1: the first element is '0' or '1' as well. */
3710 elts
[0] = def_for_init
;
3711 init_def
= build_vector (vectype
, elts
);
3715 /* Option2: the first element is INIT_VAL. */
3717 if (TREE_CONSTANT (init_val
))
3718 init_def
= build_vector (vectype
, elts
);
3721 vec
<constructor_elt
, va_gc
> *v
;
3722 vec_alloc (v
, nunits
);
3723 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, init_val
);
3724 for (i
= 1; i
< nunits
; ++i
)
3725 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[i
]);
3726 init_def
= build_constructor (vectype
, v
);
3736 *adjustment_def
= NULL_TREE
;
3737 init_def
= vect_get_vec_def_for_operand (init_val
, stmt
, NULL
);
3741 init_def
= build_vector_from_val (vectype
, init_value
);
3752 /* Function vect_create_epilog_for_reduction
3754 Create code at the loop-epilog to finalize the result of a reduction
3757 VECT_DEFS is list of vector of partial results, i.e., the lhs's of vector
3758 reduction statements.
3759 STMT is the scalar reduction stmt that is being vectorized.
3760 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
3761 number of elements that we can fit in a vectype (nunits). In this case
3762 we have to generate more than one vector stmt - i.e - we need to "unroll"
3763 the vector stmt by a factor VF/nunits. For more details see documentation
3764 in vectorizable_operation.
3765 REDUC_CODE is the tree-code for the epilog reduction.
3766 REDUCTION_PHIS is a list of the phi-nodes that carry the reduction
3768 REDUC_INDEX is the index of the operand in the right hand side of the
3769 statement that is defined by REDUCTION_PHI.
3770 DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
3771 SLP_NODE is an SLP node containing a group of reduction statements. The
3772 first one in this group is STMT.
3775 1. Creates the reduction def-use cycles: sets the arguments for
3777 The loop-entry argument is the vectorized initial-value of the reduction.
3778 The loop-latch argument is taken from VECT_DEFS - the vector of partial
3780 2. "Reduces" each vector of partial results VECT_DEFS into a single result,
3781 by applying the operation specified by REDUC_CODE if available, or by
3782 other means (whole-vector shifts or a scalar loop).
3783 The function also creates a new phi node at the loop exit to preserve
3784 loop-closed form, as illustrated below.
3786 The flow at the entry to this function:
3789 vec_def = phi <null, null> # REDUCTION_PHI
3790 VECT_DEF = vector_stmt # vectorized form of STMT
3791 s_loop = scalar_stmt # (scalar) STMT
3793 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3797 The above is transformed by this function into:
3800 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3801 VECT_DEF = vector_stmt # vectorized form of STMT
3802 s_loop = scalar_stmt # (scalar) STMT
3804 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3805 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3806 v_out2 = reduce <v_out1>
3807 s_out3 = extract_field <v_out2, 0>
3808 s_out4 = adjust_result <s_out3>
3814 vect_create_epilog_for_reduction (vec
<tree
> vect_defs
, gimple stmt
,
3815 int ncopies
, enum tree_code reduc_code
,
3816 vec
<gimple
> reduction_phis
,
3817 int reduc_index
, bool double_reduc
,
3820 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3821 stmt_vec_info prev_phi_info
;
3823 enum machine_mode mode
;
3824 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3825 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
), *outer_loop
= NULL
;
3826 basic_block exit_bb
;
3829 gimple new_phi
= NULL
, phi
;
3830 gimple_stmt_iterator exit_gsi
;
3832 tree new_temp
= NULL_TREE
, new_dest
, new_name
, new_scalar_dest
;
3833 gimple epilog_stmt
= NULL
;
3834 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3836 tree bitsize
, bitpos
;
3837 tree adjustment_def
= NULL
;
3838 tree vec_initial_def
= NULL
;
3839 tree reduction_op
, expr
, def
;
3840 tree orig_name
, scalar_result
;
3841 imm_use_iterator imm_iter
, phi_imm_iter
;
3842 use_operand_p use_p
, phi_use_p
;
3843 bool extract_scalar_result
= false;
3844 gimple use_stmt
, orig_stmt
, reduction_phi
= NULL
;
3845 bool nested_in_vect_loop
= false;
3846 auto_vec
<gimple
> new_phis
;
3847 auto_vec
<gimple
> inner_phis
;
3848 enum vect_def_type dt
= vect_unknown_def_type
;
3850 auto_vec
<tree
> scalar_results
;
3851 unsigned int group_size
= 1, k
, ratio
;
3852 auto_vec
<tree
> vec_initial_defs
;
3853 auto_vec
<gimple
> phis
;
3854 bool slp_reduc
= false;
3855 tree new_phi_result
;
3856 gimple inner_phi
= NULL
;
3859 group_size
= SLP_TREE_SCALAR_STMTS (slp_node
).length ();
3861 if (nested_in_vect_loop_p (loop
, stmt
))
3865 nested_in_vect_loop
= true;
3866 gcc_assert (!slp_node
);
3869 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3871 case GIMPLE_SINGLE_RHS
:
3872 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
))
3874 reduction_op
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), reduc_index
);
3876 case GIMPLE_UNARY_RHS
:
3877 reduction_op
= gimple_assign_rhs1 (stmt
);
3879 case GIMPLE_BINARY_RHS
:
3880 reduction_op
= reduc_index
?
3881 gimple_assign_rhs2 (stmt
) : gimple_assign_rhs1 (stmt
);
3883 case GIMPLE_TERNARY_RHS
:
3884 reduction_op
= gimple_op (stmt
, reduc_index
+ 1);
3890 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
3891 gcc_assert (vectype
);
3892 mode
= TYPE_MODE (vectype
);
3894 /* 1. Create the reduction def-use cycle:
3895 Set the arguments of REDUCTION_PHIS, i.e., transform
3898 vec_def = phi <null, null> # REDUCTION_PHI
3899 VECT_DEF = vector_stmt # vectorized form of STMT
3905 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3906 VECT_DEF = vector_stmt # vectorized form of STMT
3909 (in case of SLP, do it for all the phis). */
3911 /* Get the loop-entry arguments. */
3913 vect_get_vec_defs (reduction_op
, NULL_TREE
, stmt
, &vec_initial_defs
,
3914 NULL
, slp_node
, reduc_index
);
3917 vec_initial_defs
.create (1);
3918 /* For the case of reduction, vect_get_vec_def_for_operand returns
3919 the scalar def before the loop, that defines the initial value
3920 of the reduction variable. */
3921 vec_initial_def
= vect_get_vec_def_for_operand (reduction_op
, stmt
,
3923 vec_initial_defs
.quick_push (vec_initial_def
);
3926 /* Set phi nodes arguments. */
3927 FOR_EACH_VEC_ELT (reduction_phis
, i
, phi
)
3929 tree vec_init_def
= vec_initial_defs
[i
];
3930 tree def
= vect_defs
[i
];
3931 for (j
= 0; j
< ncopies
; j
++)
3933 /* Set the loop-entry arg of the reduction-phi. */
3934 add_phi_arg (phi
, vec_init_def
, loop_preheader_edge (loop
),
3937 /* Set the loop-latch arg for the reduction-phi. */
3939 def
= vect_get_vec_def_for_stmt_copy (vect_unknown_def_type
, def
);
3941 add_phi_arg (phi
, def
, loop_latch_edge (loop
), UNKNOWN_LOCATION
);
3943 if (dump_enabled_p ())
3945 dump_printf_loc (MSG_NOTE
, vect_location
,
3946 "transform reduction: created def-use cycle: ");
3947 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
3948 dump_printf (MSG_NOTE
, "\n");
3949 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, SSA_NAME_DEF_STMT (def
), 0);
3950 dump_printf (MSG_NOTE
, "\n");
3953 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
3957 /* 2. Create epilog code.
3958 The reduction epilog code operates across the elements of the vector
3959 of partial results computed by the vectorized loop.
3960 The reduction epilog code consists of:
3962 step 1: compute the scalar result in a vector (v_out2)
3963 step 2: extract the scalar result (s_out3) from the vector (v_out2)
3964 step 3: adjust the scalar result (s_out3) if needed.
3966 Step 1 can be accomplished using one the following three schemes:
3967 (scheme 1) using reduc_code, if available.
3968 (scheme 2) using whole-vector shifts, if available.
3969 (scheme 3) using a scalar loop. In this case steps 1+2 above are
3972 The overall epilog code looks like this:
3974 s_out0 = phi <s_loop> # original EXIT_PHI
3975 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3976 v_out2 = reduce <v_out1> # step 1
3977 s_out3 = extract_field <v_out2, 0> # step 2
3978 s_out4 = adjust_result <s_out3> # step 3
3980 (step 3 is optional, and steps 1 and 2 may be combined).
3981 Lastly, the uses of s_out0 are replaced by s_out4. */
3984 /* 2.1 Create new loop-exit-phis to preserve loop-closed form:
3985 v_out1 = phi <VECT_DEF>
3986 Store them in NEW_PHIS. */
3988 exit_bb
= single_exit (loop
)->dest
;
3989 prev_phi_info
= NULL
;
3990 new_phis
.create (vect_defs
.length ());
3991 FOR_EACH_VEC_ELT (vect_defs
, i
, def
)
3993 for (j
= 0; j
< ncopies
; j
++)
3995 tree new_def
= copy_ssa_name (def
, NULL
);
3996 phi
= create_phi_node (new_def
, exit_bb
);
3997 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, loop_vinfo
, NULL
));
3999 new_phis
.quick_push (phi
);
4002 def
= vect_get_vec_def_for_stmt_copy (dt
, def
);
4003 STMT_VINFO_RELATED_STMT (prev_phi_info
) = phi
;
4006 SET_PHI_ARG_DEF (phi
, single_exit (loop
)->dest_idx
, def
);
4007 prev_phi_info
= vinfo_for_stmt (phi
);
4011 /* The epilogue is created for the outer-loop, i.e., for the loop being
4012 vectorized. Create exit phis for the outer loop. */
4016 exit_bb
= single_exit (loop
)->dest
;
4017 inner_phis
.create (vect_defs
.length ());
4018 FOR_EACH_VEC_ELT (new_phis
, i
, phi
)
4020 tree new_result
= copy_ssa_name (PHI_RESULT (phi
), NULL
);
4021 gimple outer_phi
= create_phi_node (new_result
, exit_bb
);
4022 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
4024 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
4026 inner_phis
.quick_push (phi
);
4027 new_phis
[i
] = outer_phi
;
4028 prev_phi_info
= vinfo_for_stmt (outer_phi
);
4029 while (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
)))
4031 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
4032 new_result
= copy_ssa_name (PHI_RESULT (phi
), NULL
);
4033 outer_phi
= create_phi_node (new_result
, exit_bb
);
4034 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
4036 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
4038 STMT_VINFO_RELATED_STMT (prev_phi_info
) = outer_phi
;
4039 prev_phi_info
= vinfo_for_stmt (outer_phi
);
4044 exit_gsi
= gsi_after_labels (exit_bb
);
4046 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
4047 (i.e. when reduc_code is not available) and in the final adjustment
4048 code (if needed). Also get the original scalar reduction variable as
4049 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
4050 represents a reduction pattern), the tree-code and scalar-def are
4051 taken from the original stmt that the pattern-stmt (STMT) replaces.
4052 Otherwise (it is a regular reduction) - the tree-code and scalar-def
4053 are taken from STMT. */
4055 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
4058 /* Regular reduction */
4063 /* Reduction pattern */
4064 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (orig_stmt
);
4065 gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
));
4066 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo
) == stmt
);
4069 code
= gimple_assign_rhs_code (orig_stmt
);
4070 /* For MINUS_EXPR the initial vector is [init_val,0,...,0], therefore,
4071 partial results are added and not subtracted. */
4072 if (code
== MINUS_EXPR
)
4075 scalar_dest
= gimple_assign_lhs (orig_stmt
);
4076 scalar_type
= TREE_TYPE (scalar_dest
);
4077 scalar_results
.create (group_size
);
4078 new_scalar_dest
= vect_create_destination_var (scalar_dest
, NULL
);
4079 bitsize
= TYPE_SIZE (scalar_type
);
4081 /* In case this is a reduction in an inner-loop while vectorizing an outer
4082 loop - we don't need to extract a single scalar result at the end of the
4083 inner-loop (unless it is double reduction, i.e., the use of reduction is
4084 outside the outer-loop). The final vector of partial results will be used
4085 in the vectorized outer-loop, or reduced to a scalar result at the end of
4087 if (nested_in_vect_loop
&& !double_reduc
)
4088 goto vect_finalize_reduction
;
4090 /* SLP reduction without reduction chain, e.g.,
4094 b2 = operation (b1) */
4095 slp_reduc
= (slp_node
&& !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)));
4097 /* In case of reduction chain, e.g.,
4100 a3 = operation (a2),
4102 we may end up with more than one vector result. Here we reduce them to
4104 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4106 tree first_vect
= PHI_RESULT (new_phis
[0]);
4108 gimple new_vec_stmt
= NULL
;
4110 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4111 for (k
= 1; k
< new_phis
.length (); k
++)
4113 gimple next_phi
= new_phis
[k
];
4114 tree second_vect
= PHI_RESULT (next_phi
);
4116 tmp
= build2 (code
, vectype
, first_vect
, second_vect
);
4117 new_vec_stmt
= gimple_build_assign (vec_dest
, tmp
);
4118 first_vect
= make_ssa_name (vec_dest
, new_vec_stmt
);
4119 gimple_assign_set_lhs (new_vec_stmt
, first_vect
);
4120 gsi_insert_before (&exit_gsi
, new_vec_stmt
, GSI_SAME_STMT
);
4123 new_phi_result
= first_vect
;
4126 new_phis
.truncate (0);
4127 new_phis
.safe_push (new_vec_stmt
);
4131 new_phi_result
= PHI_RESULT (new_phis
[0]);
4133 /* 2.3 Create the reduction code, using one of the three schemes described
4134 above. In SLP we simply need to extract all the elements from the
4135 vector (without reducing them), so we use scalar shifts. */
4136 if (reduc_code
!= ERROR_MARK
&& !slp_reduc
)
4140 /*** Case 1: Create:
4141 v_out2 = reduc_expr <v_out1> */
4143 if (dump_enabled_p ())
4144 dump_printf_loc (MSG_NOTE
, vect_location
,
4145 "Reduce using direct vector reduction.\n");
4147 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4148 tmp
= build1 (reduc_code
, vectype
, new_phi_result
);
4149 epilog_stmt
= gimple_build_assign (vec_dest
, tmp
);
4150 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
4151 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4152 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4154 extract_scalar_result
= true;
4158 enum tree_code shift_code
= ERROR_MARK
;
4159 bool have_whole_vector_shift
= true;
4161 int element_bitsize
= tree_to_uhwi (bitsize
);
4162 int vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
4165 if (optab_handler (vec_shr_optab
, mode
) != CODE_FOR_nothing
)
4166 shift_code
= VEC_RSHIFT_EXPR
;
4168 have_whole_vector_shift
= false;
4170 /* Regardless of whether we have a whole vector shift, if we're
4171 emulating the operation via tree-vect-generic, we don't want
4172 to use it. Only the first round of the reduction is likely
4173 to still be profitable via emulation. */
4174 /* ??? It might be better to emit a reduction tree code here, so that
4175 tree-vect-generic can expand the first round via bit tricks. */
4176 if (!VECTOR_MODE_P (mode
))
4177 have_whole_vector_shift
= false;
4180 optab optab
= optab_for_tree_code (code
, vectype
, optab_default
);
4181 if (optab_handler (optab
, mode
) == CODE_FOR_nothing
)
4182 have_whole_vector_shift
= false;
4185 if (have_whole_vector_shift
&& !slp_reduc
)
4187 /*** Case 2: Create:
4188 for (offset = VS/2; offset >= element_size; offset/=2)
4190 Create: va' = vec_shift <va, offset>
4191 Create: va = vop <va, va'>
4194 if (dump_enabled_p ())
4195 dump_printf_loc (MSG_NOTE
, vect_location
,
4196 "Reduce using vector shifts\n");
4198 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4199 new_temp
= new_phi_result
;
4200 for (bit_offset
= vec_size_in_bits
/2;
4201 bit_offset
>= element_bitsize
;
4204 tree bitpos
= size_int (bit_offset
);
4206 epilog_stmt
= gimple_build_assign_with_ops (shift_code
,
4207 vec_dest
, new_temp
, bitpos
);
4208 new_name
= make_ssa_name (vec_dest
, epilog_stmt
);
4209 gimple_assign_set_lhs (epilog_stmt
, new_name
);
4210 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4212 epilog_stmt
= gimple_build_assign_with_ops (code
, vec_dest
,
4213 new_name
, new_temp
);
4214 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
4215 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4216 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4219 extract_scalar_result
= true;
4225 /*** Case 3: Create:
4226 s = extract_field <v_out2, 0>
4227 for (offset = element_size;
4228 offset < vector_size;
4229 offset += element_size;)
4231 Create: s' = extract_field <v_out2, offset>
4232 Create: s = op <s, s'> // For non SLP cases
4235 if (dump_enabled_p ())
4236 dump_printf_loc (MSG_NOTE
, vect_location
,
4237 "Reduce using scalar code.\n");
4239 vec_size_in_bits
= tree_to_uhwi (TYPE_SIZE (vectype
));
4240 FOR_EACH_VEC_ELT (new_phis
, i
, new_phi
)
4242 if (gimple_code (new_phi
) == GIMPLE_PHI
)
4243 vec_temp
= PHI_RESULT (new_phi
);
4245 vec_temp
= gimple_assign_lhs (new_phi
);
4246 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
, bitsize
,
4248 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4249 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4250 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4251 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4253 /* In SLP we don't need to apply reduction operation, so we just
4254 collect s' values in SCALAR_RESULTS. */
4256 scalar_results
.safe_push (new_temp
);
4258 for (bit_offset
= element_bitsize
;
4259 bit_offset
< vec_size_in_bits
;
4260 bit_offset
+= element_bitsize
)
4262 tree bitpos
= bitsize_int (bit_offset
);
4263 tree rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
,
4266 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4267 new_name
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4268 gimple_assign_set_lhs (epilog_stmt
, new_name
);
4269 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4273 /* In SLP we don't need to apply reduction operation, so
4274 we just collect s' values in SCALAR_RESULTS. */
4275 new_temp
= new_name
;
4276 scalar_results
.safe_push (new_name
);
4280 epilog_stmt
= gimple_build_assign_with_ops (code
,
4281 new_scalar_dest
, new_name
, new_temp
);
4282 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4283 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4284 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4289 /* The only case where we need to reduce scalar results in SLP, is
4290 unrolling. If the size of SCALAR_RESULTS is greater than
4291 GROUP_SIZE, we reduce them combining elements modulo
4295 tree res
, first_res
, new_res
;
4298 /* Reduce multiple scalar results in case of SLP unrolling. */
4299 for (j
= group_size
; scalar_results
.iterate (j
, &res
);
4302 first_res
= scalar_results
[j
% group_size
];
4303 new_stmt
= gimple_build_assign_with_ops (code
,
4304 new_scalar_dest
, first_res
, res
);
4305 new_res
= make_ssa_name (new_scalar_dest
, new_stmt
);
4306 gimple_assign_set_lhs (new_stmt
, new_res
);
4307 gsi_insert_before (&exit_gsi
, new_stmt
, GSI_SAME_STMT
);
4308 scalar_results
[j
% group_size
] = new_res
;
4312 /* Not SLP - we have one scalar to keep in SCALAR_RESULTS. */
4313 scalar_results
.safe_push (new_temp
);
4315 extract_scalar_result
= false;
4319 /* 2.4 Extract the final scalar result. Create:
4320 s_out3 = extract_field <v_out2, bitpos> */
4322 if (extract_scalar_result
)
4326 if (dump_enabled_p ())
4327 dump_printf_loc (MSG_NOTE
, vect_location
,
4328 "extract scalar result\n");
4330 if (BYTES_BIG_ENDIAN
)
4331 bitpos
= size_binop (MULT_EXPR
,
4332 bitsize_int (TYPE_VECTOR_SUBPARTS (vectype
) - 1),
4333 TYPE_SIZE (scalar_type
));
4335 bitpos
= bitsize_zero_node
;
4337 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, new_temp
, bitsize
, bitpos
);
4338 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4339 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4340 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4341 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4342 scalar_results
.safe_push (new_temp
);
4345 vect_finalize_reduction
:
4350 /* 2.5 Adjust the final result by the initial value of the reduction
4351 variable. (When such adjustment is not needed, then
4352 'adjustment_def' is zero). For example, if code is PLUS we create:
4353 new_temp = loop_exit_def + adjustment_def */
4357 gcc_assert (!slp_reduc
);
4358 if (nested_in_vect_loop
)
4360 new_phi
= new_phis
[0];
4361 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) == VECTOR_TYPE
);
4362 expr
= build2 (code
, vectype
, PHI_RESULT (new_phi
), adjustment_def
);
4363 new_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4367 new_temp
= scalar_results
[0];
4368 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) != VECTOR_TYPE
);
4369 expr
= build2 (code
, scalar_type
, new_temp
, adjustment_def
);
4370 new_dest
= vect_create_destination_var (scalar_dest
, scalar_type
);
4373 epilog_stmt
= gimple_build_assign (new_dest
, expr
);
4374 new_temp
= make_ssa_name (new_dest
, epilog_stmt
);
4375 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4376 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4377 if (nested_in_vect_loop
)
4379 set_vinfo_for_stmt (epilog_stmt
,
4380 new_stmt_vec_info (epilog_stmt
, loop_vinfo
,
4382 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (epilog_stmt
)) =
4383 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_phi
));
4386 scalar_results
.quick_push (new_temp
);
4388 scalar_results
[0] = new_temp
;
4391 scalar_results
[0] = new_temp
;
4393 new_phis
[0] = epilog_stmt
;
4396 /* 2.6 Handle the loop-exit phis. Replace the uses of scalar loop-exit
4397 phis with new adjusted scalar results, i.e., replace use <s_out0>
4402 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4403 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4404 v_out2 = reduce <v_out1>
4405 s_out3 = extract_field <v_out2, 0>
4406 s_out4 = adjust_result <s_out3>
4413 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4414 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4415 v_out2 = reduce <v_out1>
4416 s_out3 = extract_field <v_out2, 0>
4417 s_out4 = adjust_result <s_out3>
4422 /* In SLP reduction chain we reduce vector results into one vector if
4423 necessary, hence we set here GROUP_SIZE to 1. SCALAR_DEST is the LHS of
4424 the last stmt in the reduction chain, since we are looking for the loop
4426 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4428 scalar_dest
= gimple_assign_lhs (
4429 SLP_TREE_SCALAR_STMTS (slp_node
)[group_size
- 1]);
4433 /* In SLP we may have several statements in NEW_PHIS and REDUCTION_PHIS (in
4434 case that GROUP_SIZE is greater than vectorization factor). Therefore, we
4435 need to match SCALAR_RESULTS with corresponding statements. The first
4436 (GROUP_SIZE / number of new vector stmts) scalar results correspond to
4437 the first vector stmt, etc.
4438 (RATIO is equal to (GROUP_SIZE / number of new vector stmts)). */
4439 if (group_size
> new_phis
.length ())
4441 ratio
= group_size
/ new_phis
.length ();
4442 gcc_assert (!(group_size
% new_phis
.length ()));
4447 for (k
= 0; k
< group_size
; k
++)
4451 epilog_stmt
= new_phis
[k
/ ratio
];
4452 reduction_phi
= reduction_phis
[k
/ ratio
];
4454 inner_phi
= inner_phis
[k
/ ratio
];
4459 gimple current_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[k
];
4461 orig_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (current_stmt
));
4462 /* SLP statements can't participate in patterns. */
4463 gcc_assert (!orig_stmt
);
4464 scalar_dest
= gimple_assign_lhs (current_stmt
);
4468 /* Find the loop-closed-use at the loop exit of the original scalar
4469 result. (The reduction result is expected to have two immediate uses -
4470 one at the latch block, and one at the loop exit). */
4471 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
4472 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
)))
4473 && !is_gimple_debug (USE_STMT (use_p
)))
4474 phis
.safe_push (USE_STMT (use_p
));
4476 /* While we expect to have found an exit_phi because of loop-closed-ssa
4477 form we can end up without one if the scalar cycle is dead. */
4479 FOR_EACH_VEC_ELT (phis
, i
, exit_phi
)
4483 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
4486 /* FORNOW. Currently not supporting the case that an inner-loop
4487 reduction is not used in the outer-loop (but only outside the
4488 outer-loop), unless it is double reduction. */
4489 gcc_assert ((STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
4490 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
))
4493 STMT_VINFO_VEC_STMT (exit_phi_vinfo
) = epilog_stmt
;
4495 || STMT_VINFO_DEF_TYPE (exit_phi_vinfo
)
4496 != vect_double_reduction_def
)
4499 /* Handle double reduction:
4501 stmt1: s1 = phi <s0, s2> - double reduction phi (outer loop)
4502 stmt2: s3 = phi <s1, s4> - (regular) reduc phi (inner loop)
4503 stmt3: s4 = use (s3) - (regular) reduc stmt (inner loop)
4504 stmt4: s2 = phi <s4> - double reduction stmt (outer loop)
4506 At that point the regular reduction (stmt2 and stmt3) is
4507 already vectorized, as well as the exit phi node, stmt4.
4508 Here we vectorize the phi node of double reduction, stmt1, and
4509 update all relevant statements. */
4511 /* Go through all the uses of s2 to find double reduction phi
4512 node, i.e., stmt1 above. */
4513 orig_name
= PHI_RESULT (exit_phi
);
4514 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
4516 stmt_vec_info use_stmt_vinfo
;
4517 stmt_vec_info new_phi_vinfo
;
4518 tree vect_phi_init
, preheader_arg
, vect_phi_res
, init_def
;
4519 basic_block bb
= gimple_bb (use_stmt
);
4522 /* Check that USE_STMT is really double reduction phi
4524 if (gimple_code (use_stmt
) != GIMPLE_PHI
4525 || gimple_phi_num_args (use_stmt
) != 2
4526 || bb
->loop_father
!= outer_loop
)
4528 use_stmt_vinfo
= vinfo_for_stmt (use_stmt
);
4530 || STMT_VINFO_DEF_TYPE (use_stmt_vinfo
)
4531 != vect_double_reduction_def
)
4534 /* Create vector phi node for double reduction:
4535 vs1 = phi <vs0, vs2>
4536 vs1 was created previously in this function by a call to
4537 vect_get_vec_def_for_operand and is stored in
4539 vs2 is defined by INNER_PHI, the vectorized EXIT_PHI;
4540 vs0 is created here. */
4542 /* Create vector phi node. */
4543 vect_phi
= create_phi_node (vec_initial_def
, bb
);
4544 new_phi_vinfo
= new_stmt_vec_info (vect_phi
,
4545 loop_vec_info_for_loop (outer_loop
), NULL
);
4546 set_vinfo_for_stmt (vect_phi
, new_phi_vinfo
);
4548 /* Create vs0 - initial def of the double reduction phi. */
4549 preheader_arg
= PHI_ARG_DEF_FROM_EDGE (use_stmt
,
4550 loop_preheader_edge (outer_loop
));
4551 init_def
= get_initial_def_for_reduction (stmt
,
4552 preheader_arg
, NULL
);
4553 vect_phi_init
= vect_init_vector (use_stmt
, init_def
,
4556 /* Update phi node arguments with vs0 and vs2. */
4557 add_phi_arg (vect_phi
, vect_phi_init
,
4558 loop_preheader_edge (outer_loop
),
4560 add_phi_arg (vect_phi
, PHI_RESULT (inner_phi
),
4561 loop_latch_edge (outer_loop
), UNKNOWN_LOCATION
);
4562 if (dump_enabled_p ())
4564 dump_printf_loc (MSG_NOTE
, vect_location
,
4565 "created double reduction phi node: ");
4566 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, vect_phi
, 0);
4567 dump_printf (MSG_NOTE
, "\n");
4570 vect_phi_res
= PHI_RESULT (vect_phi
);
4572 /* Replace the use, i.e., set the correct vs1 in the regular
4573 reduction phi node. FORNOW, NCOPIES is always 1, so the
4574 loop is redundant. */
4575 use
= reduction_phi
;
4576 for (j
= 0; j
< ncopies
; j
++)
4578 edge pr_edge
= loop_preheader_edge (loop
);
4579 SET_PHI_ARG_DEF (use
, pr_edge
->dest_idx
, vect_phi_res
);
4580 use
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use
));
4587 if (nested_in_vect_loop
)
4596 /* Find the loop-closed-use at the loop exit of the original scalar
4597 result. (The reduction result is expected to have two immediate uses,
4598 one at the latch block, and one at the loop exit). For double
4599 reductions we are looking for exit phis of the outer loop. */
4600 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
4602 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
4604 if (!is_gimple_debug (USE_STMT (use_p
)))
4605 phis
.safe_push (USE_STMT (use_p
));
4609 if (double_reduc
&& gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
4611 tree phi_res
= PHI_RESULT (USE_STMT (use_p
));
4613 FOR_EACH_IMM_USE_FAST (phi_use_p
, phi_imm_iter
, phi_res
)
4615 if (!flow_bb_inside_loop_p (loop
,
4616 gimple_bb (USE_STMT (phi_use_p
)))
4617 && !is_gimple_debug (USE_STMT (phi_use_p
)))
4618 phis
.safe_push (USE_STMT (phi_use_p
));
4624 FOR_EACH_VEC_ELT (phis
, i
, exit_phi
)
4626 /* Replace the uses: */
4627 orig_name
= PHI_RESULT (exit_phi
);
4628 scalar_result
= scalar_results
[k
];
4629 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
4630 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
4631 SET_USE (use_p
, scalar_result
);
4639 /* Function vectorizable_reduction.
4641 Check if STMT performs a reduction operation that can be vectorized.
4642 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4643 stmt to replace it, put it in VEC_STMT, and insert it at GSI.
4644 Return FALSE if not a vectorizable STMT, TRUE otherwise.
4646 This function also handles reduction idioms (patterns) that have been
4647 recognized in advance during vect_pattern_recog. In this case, STMT may be
4649 X = pattern_expr (arg0, arg1, ..., X)
4650 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
4651 sequence that had been detected and replaced by the pattern-stmt (STMT).
4653 In some cases of reduction patterns, the type of the reduction variable X is
4654 different than the type of the other arguments of STMT.
4655 In such cases, the vectype that is used when transforming STMT into a vector
4656 stmt is different than the vectype that is used to determine the
4657 vectorization factor, because it consists of a different number of elements
4658 than the actual number of elements that are being operated upon in parallel.
4660 For example, consider an accumulation of shorts into an int accumulator.
4661 On some targets it's possible to vectorize this pattern operating on 8
4662 shorts at a time (hence, the vectype for purposes of determining the
4663 vectorization factor should be V8HI); on the other hand, the vectype that
4664 is used to create the vector form is actually V4SI (the type of the result).
4666 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
4667 indicates what is the actual level of parallelism (V8HI in the example), so
4668 that the right vectorization factor would be derived. This vectype
4669 corresponds to the type of arguments to the reduction stmt, and should *NOT*
4670 be used to create the vectorized stmt. The right vectype for the vectorized
4671 stmt is obtained from the type of the result X:
4672 get_vectype_for_scalar_type (TREE_TYPE (X))
4674 This means that, contrary to "regular" reductions (or "regular" stmts in
4675 general), the following equation:
4676 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
4677 does *NOT* necessarily hold for reduction patterns. */
4680 vectorizable_reduction (gimple stmt
, gimple_stmt_iterator
*gsi
,
4681 gimple
*vec_stmt
, slp_tree slp_node
)
4685 tree loop_vec_def0
= NULL_TREE
, loop_vec_def1
= NULL_TREE
;
4686 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
4687 tree vectype_out
= STMT_VINFO_VECTYPE (stmt_info
);
4688 tree vectype_in
= NULL_TREE
;
4689 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
4690 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4691 enum tree_code code
, orig_code
, epilog_reduc_code
;
4692 enum machine_mode vec_mode
;
4694 optab optab
, reduc_optab
;
4695 tree new_temp
= NULL_TREE
;
4698 enum vect_def_type dt
;
4699 gimple new_phi
= NULL
;
4703 stmt_vec_info orig_stmt_info
;
4704 tree expr
= NULL_TREE
;
4708 stmt_vec_info prev_stmt_info
, prev_phi_info
;
4709 bool single_defuse_cycle
= false;
4710 tree reduc_def
= NULL_TREE
;
4711 gimple new_stmt
= NULL
;
4714 bool nested_cycle
= false, found_nested_cycle_def
= false;
4715 gimple reduc_def_stmt
= NULL
;
4716 /* The default is that the reduction variable is the last in statement. */
4717 int reduc_index
= 2;
4718 bool double_reduc
= false, dummy
;
4720 struct loop
* def_stmt_loop
, *outer_loop
= NULL
;
4722 gimple def_arg_stmt
;
4723 auto_vec
<tree
> vec_oprnds0
;
4724 auto_vec
<tree
> vec_oprnds1
;
4725 auto_vec
<tree
> vect_defs
;
4726 auto_vec
<gimple
> phis
;
4728 tree def0
, def1
, tem
, op0
, op1
= NULL_TREE
;
4730 /* In case of reduction chain we switch to the first stmt in the chain, but
4731 we don't update STMT_INFO, since only the last stmt is marked as reduction
4732 and has reduction properties. */
4733 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4734 stmt
= GROUP_FIRST_ELEMENT (stmt_info
);
4736 if (nested_in_vect_loop_p (loop
, stmt
))
4740 nested_cycle
= true;
4743 /* 1. Is vectorizable reduction? */
4744 /* Not supportable if the reduction variable is used in the loop, unless
4745 it's a reduction chain. */
4746 if (STMT_VINFO_RELEVANT (stmt_info
) > vect_used_in_outer
4747 && !GROUP_FIRST_ELEMENT (stmt_info
))
4750 /* Reductions that are not used even in an enclosing outer-loop,
4751 are expected to be "live" (used out of the loop). */
4752 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
4753 && !STMT_VINFO_LIVE_P (stmt_info
))
4756 /* Make sure it was already recognized as a reduction computation. */
4757 if (STMT_VINFO_DEF_TYPE (stmt_info
) != vect_reduction_def
4758 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_nested_cycle
)
4761 /* 2. Has this been recognized as a reduction pattern?
4763 Check if STMT represents a pattern that has been recognized
4764 in earlier analysis stages. For stmts that represent a pattern,
4765 the STMT_VINFO_RELATED_STMT field records the last stmt in
4766 the original sequence that constitutes the pattern. */
4768 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
4771 orig_stmt_info
= vinfo_for_stmt (orig_stmt
);
4772 gcc_assert (STMT_VINFO_IN_PATTERN_P (orig_stmt_info
));
4773 gcc_assert (!STMT_VINFO_IN_PATTERN_P (stmt_info
));
4776 /* 3. Check the operands of the operation. The first operands are defined
4777 inside the loop body. The last operand is the reduction variable,
4778 which is defined by the loop-header-phi. */
4780 gcc_assert (is_gimple_assign (stmt
));
4783 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
4785 case GIMPLE_SINGLE_RHS
:
4786 op_type
= TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
));
4787 if (op_type
== ternary_op
)
4789 tree rhs
= gimple_assign_rhs1 (stmt
);
4790 ops
[0] = TREE_OPERAND (rhs
, 0);
4791 ops
[1] = TREE_OPERAND (rhs
, 1);
4792 ops
[2] = TREE_OPERAND (rhs
, 2);
4793 code
= TREE_CODE (rhs
);
4799 case GIMPLE_BINARY_RHS
:
4800 code
= gimple_assign_rhs_code (stmt
);
4801 op_type
= TREE_CODE_LENGTH (code
);
4802 gcc_assert (op_type
== binary_op
);
4803 ops
[0] = gimple_assign_rhs1 (stmt
);
4804 ops
[1] = gimple_assign_rhs2 (stmt
);
4807 case GIMPLE_TERNARY_RHS
:
4808 code
= gimple_assign_rhs_code (stmt
);
4809 op_type
= TREE_CODE_LENGTH (code
);
4810 gcc_assert (op_type
== ternary_op
);
4811 ops
[0] = gimple_assign_rhs1 (stmt
);
4812 ops
[1] = gimple_assign_rhs2 (stmt
);
4813 ops
[2] = gimple_assign_rhs3 (stmt
);
4816 case GIMPLE_UNARY_RHS
:
4823 if (code
== COND_EXPR
&& slp_node
)
4826 scalar_dest
= gimple_assign_lhs (stmt
);
4827 scalar_type
= TREE_TYPE (scalar_dest
);
4828 if (!POINTER_TYPE_P (scalar_type
) && !INTEGRAL_TYPE_P (scalar_type
)
4829 && !SCALAR_FLOAT_TYPE_P (scalar_type
))
4832 /* Do not try to vectorize bit-precision reductions. */
4833 if ((TYPE_PRECISION (scalar_type
)
4834 != GET_MODE_PRECISION (TYPE_MODE (scalar_type
))))
4837 /* All uses but the last are expected to be defined in the loop.
4838 The last use is the reduction variable. In case of nested cycle this
4839 assumption is not true: we use reduc_index to record the index of the
4840 reduction variable. */
4841 for (i
= 0; i
< op_type
- 1; i
++)
4843 /* The condition of COND_EXPR is checked in vectorizable_condition(). */
4844 if (i
== 0 && code
== COND_EXPR
)
4847 is_simple_use
= vect_is_simple_use_1 (ops
[i
], stmt
, loop_vinfo
, NULL
,
4848 &def_stmt
, &def
, &dt
, &tem
);
4851 gcc_assert (is_simple_use
);
4853 if (dt
!= vect_internal_def
4854 && dt
!= vect_external_def
4855 && dt
!= vect_constant_def
4856 && dt
!= vect_induction_def
4857 && !(dt
== vect_nested_cycle
&& nested_cycle
))
4860 if (dt
== vect_nested_cycle
)
4862 found_nested_cycle_def
= true;
4863 reduc_def_stmt
= def_stmt
;
4868 is_simple_use
= vect_is_simple_use_1 (ops
[i
], stmt
, loop_vinfo
, NULL
,
4869 &def_stmt
, &def
, &dt
, &tem
);
4872 gcc_assert (is_simple_use
);
4873 if (!(dt
== vect_reduction_def
4874 || dt
== vect_nested_cycle
4875 || ((dt
== vect_internal_def
|| dt
== vect_external_def
4876 || dt
== vect_constant_def
|| dt
== vect_induction_def
)
4877 && nested_cycle
&& found_nested_cycle_def
)))
4879 /* For pattern recognized stmts, orig_stmt might be a reduction,
4880 but some helper statements for the pattern might not, or
4881 might be COND_EXPRs with reduction uses in the condition. */
4882 gcc_assert (orig_stmt
);
4885 if (!found_nested_cycle_def
)
4886 reduc_def_stmt
= def_stmt
;
4888 gcc_assert (gimple_code (reduc_def_stmt
) == GIMPLE_PHI
);
4890 gcc_assert (orig_stmt
== vect_is_simple_reduction (loop_vinfo
,
4896 gimple tmp
= vect_is_simple_reduction (loop_vinfo
, reduc_def_stmt
,
4897 !nested_cycle
, &dummy
);
4898 /* We changed STMT to be the first stmt in reduction chain, hence we
4899 check that in this case the first element in the chain is STMT. */
4900 gcc_assert (stmt
== tmp
4901 || GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp
)) == stmt
);
4904 if (STMT_VINFO_LIVE_P (vinfo_for_stmt (reduc_def_stmt
)))
4907 if (slp_node
|| PURE_SLP_STMT (stmt_info
))
4910 ncopies
= (LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4911 / TYPE_VECTOR_SUBPARTS (vectype_in
));
4913 gcc_assert (ncopies
>= 1);
4915 vec_mode
= TYPE_MODE (vectype_in
);
4917 if (code
== COND_EXPR
)
4919 if (!vectorizable_condition (stmt
, gsi
, NULL
, ops
[reduc_index
], 0, NULL
))
4921 if (dump_enabled_p ())
4922 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4923 "unsupported condition in reduction\n");
4930 /* 4. Supportable by target? */
4932 if (code
== LSHIFT_EXPR
|| code
== RSHIFT_EXPR
4933 || code
== LROTATE_EXPR
|| code
== RROTATE_EXPR
)
4935 /* Shifts and rotates are only supported by vectorizable_shifts,
4936 not vectorizable_reduction. */
4937 if (dump_enabled_p ())
4938 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4939 "unsupported shift or rotation.\n");
4943 /* 4.1. check support for the operation in the loop */
4944 optab
= optab_for_tree_code (code
, vectype_in
, optab_default
);
4947 if (dump_enabled_p ())
4948 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4954 if (optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
4956 if (dump_enabled_p ())
4957 dump_printf (MSG_NOTE
, "op not supported by target.\n");
4959 if (GET_MODE_SIZE (vec_mode
) != UNITS_PER_WORD
4960 || LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4961 < vect_min_worthwhile_factor (code
))
4964 if (dump_enabled_p ())
4965 dump_printf (MSG_NOTE
, "proceeding using word mode.\n");
4968 /* Worthwhile without SIMD support? */
4969 if (!VECTOR_MODE_P (TYPE_MODE (vectype_in
))
4970 && LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4971 < vect_min_worthwhile_factor (code
))
4973 if (dump_enabled_p ())
4974 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4975 "not worthwhile without SIMD support.\n");
4981 /* 4.2. Check support for the epilog operation.
4983 If STMT represents a reduction pattern, then the type of the
4984 reduction variable may be different than the type of the rest
4985 of the arguments. For example, consider the case of accumulation
4986 of shorts into an int accumulator; The original code:
4987 S1: int_a = (int) short_a;
4988 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
4991 STMT: int_acc = widen_sum <short_a, int_acc>
4994 1. The tree-code that is used to create the vector operation in the
4995 epilog code (that reduces the partial results) is not the
4996 tree-code of STMT, but is rather the tree-code of the original
4997 stmt from the pattern that STMT is replacing. I.e, in the example
4998 above we want to use 'widen_sum' in the loop, but 'plus' in the
5000 2. The type (mode) we use to check available target support
5001 for the vector operation to be created in the *epilog*, is
5002 determined by the type of the reduction variable (in the example
5003 above we'd check this: optab_handler (plus_optab, vect_int_mode])).
5004 However the type (mode) we use to check available target support
5005 for the vector operation to be created *inside the loop*, is
5006 determined by the type of the other arguments to STMT (in the
5007 example we'd check this: optab_handler (widen_sum_optab,
5010 This is contrary to "regular" reductions, in which the types of all
5011 the arguments are the same as the type of the reduction variable.
5012 For "regular" reductions we can therefore use the same vector type
5013 (and also the same tree-code) when generating the epilog code and
5014 when generating the code inside the loop. */
5018 /* This is a reduction pattern: get the vectype from the type of the
5019 reduction variable, and get the tree-code from orig_stmt. */
5020 orig_code
= gimple_assign_rhs_code (orig_stmt
);
5021 gcc_assert (vectype_out
);
5022 vec_mode
= TYPE_MODE (vectype_out
);
5026 /* Regular reduction: use the same vectype and tree-code as used for
5027 the vector code inside the loop can be used for the epilog code. */
5033 def_bb
= gimple_bb (reduc_def_stmt
);
5034 def_stmt_loop
= def_bb
->loop_father
;
5035 def_arg
= PHI_ARG_DEF_FROM_EDGE (reduc_def_stmt
,
5036 loop_preheader_edge (def_stmt_loop
));
5037 if (TREE_CODE (def_arg
) == SSA_NAME
5038 && (def_arg_stmt
= SSA_NAME_DEF_STMT (def_arg
))
5039 && gimple_code (def_arg_stmt
) == GIMPLE_PHI
5040 && flow_bb_inside_loop_p (outer_loop
, gimple_bb (def_arg_stmt
))
5041 && vinfo_for_stmt (def_arg_stmt
)
5042 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_arg_stmt
))
5043 == vect_double_reduction_def
)
5044 double_reduc
= true;
5047 epilog_reduc_code
= ERROR_MARK
;
5048 if (reduction_code_for_scalar_code (orig_code
, &epilog_reduc_code
))
5050 reduc_optab
= optab_for_tree_code (epilog_reduc_code
, vectype_out
,
5054 if (dump_enabled_p ())
5055 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5056 "no optab for reduction.\n");
5058 epilog_reduc_code
= ERROR_MARK
;
5062 && optab_handler (reduc_optab
, vec_mode
) == CODE_FOR_nothing
)
5064 if (dump_enabled_p ())
5065 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5066 "reduc op not supported by target.\n");
5068 epilog_reduc_code
= ERROR_MARK
;
5073 if (!nested_cycle
|| double_reduc
)
5075 if (dump_enabled_p ())
5076 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5077 "no reduc code for scalar code.\n");
5083 if (double_reduc
&& ncopies
> 1)
5085 if (dump_enabled_p ())
5086 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5087 "multiple types in double reduction\n");
5092 /* In case of widenning multiplication by a constant, we update the type
5093 of the constant to be the type of the other operand. We check that the
5094 constant fits the type in the pattern recognition pass. */
5095 if (code
== DOT_PROD_EXPR
5096 && !types_compatible_p (TREE_TYPE (ops
[0]), TREE_TYPE (ops
[1])))
5098 if (TREE_CODE (ops
[0]) == INTEGER_CST
)
5099 ops
[0] = fold_convert (TREE_TYPE (ops
[1]), ops
[0]);
5100 else if (TREE_CODE (ops
[1]) == INTEGER_CST
)
5101 ops
[1] = fold_convert (TREE_TYPE (ops
[0]), ops
[1]);
5104 if (dump_enabled_p ())
5105 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5106 "invalid types in dot-prod\n");
5112 if (!vec_stmt
) /* transformation not required. */
5114 if (!vect_model_reduction_cost (stmt_info
, epilog_reduc_code
, ncopies
))
5116 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
5122 if (dump_enabled_p ())
5123 dump_printf_loc (MSG_NOTE
, vect_location
, "transform reduction.\n");
5125 /* FORNOW: Multiple types are not supported for condition. */
5126 if (code
== COND_EXPR
)
5127 gcc_assert (ncopies
== 1);
5129 /* Create the destination vector */
5130 vec_dest
= vect_create_destination_var (scalar_dest
, vectype_out
);
5132 /* In case the vectorization factor (VF) is bigger than the number
5133 of elements that we can fit in a vectype (nunits), we have to generate
5134 more than one vector stmt - i.e - we need to "unroll" the
5135 vector stmt by a factor VF/nunits. For more details see documentation
5136 in vectorizable_operation. */
5138 /* If the reduction is used in an outer loop we need to generate
5139 VF intermediate results, like so (e.g. for ncopies=2):
5144 (i.e. we generate VF results in 2 registers).
5145 In this case we have a separate def-use cycle for each copy, and therefore
5146 for each copy we get the vector def for the reduction variable from the
5147 respective phi node created for this copy.
5149 Otherwise (the reduction is unused in the loop nest), we can combine
5150 together intermediate results, like so (e.g. for ncopies=2):
5154 (i.e. we generate VF/2 results in a single register).
5155 In this case for each copy we get the vector def for the reduction variable
5156 from the vectorized reduction operation generated in the previous iteration.
5159 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
)
5161 single_defuse_cycle
= true;
5165 epilog_copies
= ncopies
;
5167 prev_stmt_info
= NULL
;
5168 prev_phi_info
= NULL
;
5171 vec_num
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
5172 gcc_assert (TYPE_VECTOR_SUBPARTS (vectype_out
)
5173 == TYPE_VECTOR_SUBPARTS (vectype_in
));
5178 vec_oprnds0
.create (1);
5179 if (op_type
== ternary_op
)
5180 vec_oprnds1
.create (1);
5183 phis
.create (vec_num
);
5184 vect_defs
.create (vec_num
);
5186 vect_defs
.quick_push (NULL_TREE
);
5188 for (j
= 0; j
< ncopies
; j
++)
5190 if (j
== 0 || !single_defuse_cycle
)
5192 for (i
= 0; i
< vec_num
; i
++)
5194 /* Create the reduction-phi that defines the reduction
5196 new_phi
= create_phi_node (vec_dest
, loop
->header
);
5197 set_vinfo_for_stmt (new_phi
,
5198 new_stmt_vec_info (new_phi
, loop_vinfo
,
5200 if (j
== 0 || slp_node
)
5201 phis
.quick_push (new_phi
);
5205 if (code
== COND_EXPR
)
5207 gcc_assert (!slp_node
);
5208 vectorizable_condition (stmt
, gsi
, vec_stmt
,
5209 PHI_RESULT (phis
[0]),
5211 /* Multiple types are not supported for condition. */
5218 op0
= ops
[!reduc_index
];
5219 if (op_type
== ternary_op
)
5221 if (reduc_index
== 0)
5228 vect_get_vec_defs (op0
, op1
, stmt
, &vec_oprnds0
, &vec_oprnds1
,
5232 loop_vec_def0
= vect_get_vec_def_for_operand (ops
[!reduc_index
],
5234 vec_oprnds0
.quick_push (loop_vec_def0
);
5235 if (op_type
== ternary_op
)
5237 loop_vec_def1
= vect_get_vec_def_for_operand (op1
, stmt
,
5239 vec_oprnds1
.quick_push (loop_vec_def1
);
5247 enum vect_def_type dt
;
5251 vect_is_simple_use (ops
[!reduc_index
], stmt
, loop_vinfo
, NULL
,
5252 &dummy_stmt
, &dummy
, &dt
);
5253 loop_vec_def0
= vect_get_vec_def_for_stmt_copy (dt
,
5255 vec_oprnds0
[0] = loop_vec_def0
;
5256 if (op_type
== ternary_op
)
5258 vect_is_simple_use (op1
, stmt
, loop_vinfo
, NULL
, &dummy_stmt
,
5260 loop_vec_def1
= vect_get_vec_def_for_stmt_copy (dt
,
5262 vec_oprnds1
[0] = loop_vec_def1
;
5266 if (single_defuse_cycle
)
5267 reduc_def
= gimple_assign_lhs (new_stmt
);
5269 STMT_VINFO_RELATED_STMT (prev_phi_info
) = new_phi
;
5272 FOR_EACH_VEC_ELT (vec_oprnds0
, i
, def0
)
5275 reduc_def
= PHI_RESULT (phis
[i
]);
5278 if (!single_defuse_cycle
|| j
== 0)
5279 reduc_def
= PHI_RESULT (new_phi
);
5282 def1
= ((op_type
== ternary_op
)
5283 ? vec_oprnds1
[i
] : NULL
);
5284 if (op_type
== binary_op
)
5286 if (reduc_index
== 0)
5287 expr
= build2 (code
, vectype_out
, reduc_def
, def0
);
5289 expr
= build2 (code
, vectype_out
, def0
, reduc_def
);
5293 if (reduc_index
== 0)
5294 expr
= build3 (code
, vectype_out
, reduc_def
, def0
, def1
);
5297 if (reduc_index
== 1)
5298 expr
= build3 (code
, vectype_out
, def0
, reduc_def
, def1
);
5300 expr
= build3 (code
, vectype_out
, def0
, def1
, reduc_def
);
5304 new_stmt
= gimple_build_assign (vec_dest
, expr
);
5305 new_temp
= make_ssa_name (vec_dest
, new_stmt
);
5306 gimple_assign_set_lhs (new_stmt
, new_temp
);
5307 vect_finish_stmt_generation (stmt
, new_stmt
, gsi
);
5311 SLP_TREE_VEC_STMTS (slp_node
).quick_push (new_stmt
);
5312 vect_defs
.quick_push (new_temp
);
5315 vect_defs
[0] = new_temp
;
5322 STMT_VINFO_VEC_STMT (stmt_info
) = *vec_stmt
= new_stmt
;
5324 STMT_VINFO_RELATED_STMT (prev_stmt_info
) = new_stmt
;
5326 prev_stmt_info
= vinfo_for_stmt (new_stmt
);
5327 prev_phi_info
= vinfo_for_stmt (new_phi
);
5330 /* Finalize the reduction-phi (set its arguments) and create the
5331 epilog reduction code. */
5332 if ((!single_defuse_cycle
|| code
== COND_EXPR
) && !slp_node
)
5334 new_temp
= gimple_assign_lhs (*vec_stmt
);
5335 vect_defs
[0] = new_temp
;
5338 vect_create_epilog_for_reduction (vect_defs
, stmt
, epilog_copies
,
5339 epilog_reduc_code
, phis
, reduc_index
,
5340 double_reduc
, slp_node
);
5345 /* Function vect_min_worthwhile_factor.
5347 For a loop where we could vectorize the operation indicated by CODE,
5348 return the minimum vectorization factor that makes it worthwhile
5349 to use generic vectors. */
5351 vect_min_worthwhile_factor (enum tree_code code
)
5372 /* Function vectorizable_induction
5374 Check if PHI performs an induction computation that can be vectorized.
5375 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
5376 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
5377 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5380 vectorizable_induction (gimple phi
, gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
5383 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
5384 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
5385 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
5386 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5387 int nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
5388 int ncopies
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) / nunits
;
5391 gcc_assert (ncopies
>= 1);
5392 /* FORNOW. These restrictions should be relaxed. */
5393 if (nested_in_vect_loop_p (loop
, phi
))
5395 imm_use_iterator imm_iter
;
5396 use_operand_p use_p
;
5403 if (dump_enabled_p ())
5404 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5405 "multiple types in nested loop.\n");
5410 latch_e
= loop_latch_edge (loop
->inner
);
5411 loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
5412 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
5414 if (!flow_bb_inside_loop_p (loop
->inner
,
5415 gimple_bb (USE_STMT (use_p
))))
5417 exit_phi
= USE_STMT (use_p
);
5423 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
5424 if (!(STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
5425 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
)))
5427 if (dump_enabled_p ())
5428 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5429 "inner-loop induction only used outside "
5430 "of the outer vectorized loop.\n");
5436 if (!STMT_VINFO_RELEVANT_P (stmt_info
))
5439 /* FORNOW: SLP not supported. */
5440 if (STMT_SLP_TYPE (stmt_info
))
5443 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
);
5445 if (gimple_code (phi
) != GIMPLE_PHI
)
5448 if (!vec_stmt
) /* transformation not required. */
5450 STMT_VINFO_TYPE (stmt_info
) = induc_vec_info_type
;
5451 if (dump_enabled_p ())
5452 dump_printf_loc (MSG_NOTE
, vect_location
,
5453 "=== vectorizable_induction ===\n");
5454 vect_model_induction_cost (stmt_info
, ncopies
);
5460 if (dump_enabled_p ())
5461 dump_printf_loc (MSG_NOTE
, vect_location
, "transform induction phi.\n");
5463 vec_def
= get_initial_def_for_induction (phi
);
5464 *vec_stmt
= SSA_NAME_DEF_STMT (vec_def
);
5468 /* Function vectorizable_live_operation.
5470 STMT computes a value that is used outside the loop. Check if
5471 it can be supported. */
5474 vectorizable_live_operation (gimple stmt
,
5475 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
5478 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
5479 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
5480 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5486 enum vect_def_type dt
;
5487 enum tree_code code
;
5488 enum gimple_rhs_class rhs_class
;
5490 gcc_assert (STMT_VINFO_LIVE_P (stmt_info
));
5492 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_reduction_def
)
5495 if (!is_gimple_assign (stmt
))
5497 if (gimple_call_internal_p (stmt
)
5498 && gimple_call_internal_fn (stmt
) == IFN_GOMP_SIMD_LANE
5499 && gimple_call_lhs (stmt
)
5501 && TREE_CODE (gimple_call_arg (stmt
, 0)) == SSA_NAME
5503 == SSA_NAME_VAR (gimple_call_arg (stmt
, 0)))
5505 edge e
= single_exit (loop
);
5506 basic_block merge_bb
= e
->dest
;
5507 imm_use_iterator imm_iter
;
5508 use_operand_p use_p
;
5509 tree lhs
= gimple_call_lhs (stmt
);
5511 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
5513 gimple use_stmt
= USE_STMT (use_p
);
5514 if (gimple_code (use_stmt
) == GIMPLE_PHI
5515 || gimple_bb (use_stmt
) == merge_bb
)
5520 = build_int_cst (unsigned_type_node
,
5521 loop_vinfo
->vectorization_factor
- 1);
5522 SET_PHI_ARG_DEF (use_stmt
, e
->dest_idx
, vfm1
);
5532 if (TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
5535 /* FORNOW. CHECKME. */
5536 if (nested_in_vect_loop_p (loop
, stmt
))
5539 code
= gimple_assign_rhs_code (stmt
);
5540 op_type
= TREE_CODE_LENGTH (code
);
5541 rhs_class
= get_gimple_rhs_class (code
);
5542 gcc_assert (rhs_class
!= GIMPLE_UNARY_RHS
|| op_type
== unary_op
);
5543 gcc_assert (rhs_class
!= GIMPLE_BINARY_RHS
|| op_type
== binary_op
);
5545 /* FORNOW: support only if all uses are invariant. This means
5546 that the scalar operations can remain in place, unvectorized.
5547 The original last scalar value that they compute will be used. */
5549 for (i
= 0; i
< op_type
; i
++)
5551 if (rhs_class
== GIMPLE_SINGLE_RHS
)
5552 op
= TREE_OPERAND (gimple_op (stmt
, 1), i
);
5554 op
= gimple_op (stmt
, i
+ 1);
5556 && !vect_is_simple_use (op
, stmt
, loop_vinfo
, NULL
, &def_stmt
, &def
,
5559 if (dump_enabled_p ())
5560 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5561 "use not simple.\n");
5565 if (dt
!= vect_external_def
&& dt
!= vect_constant_def
)
5569 /* No transformation is required for the cases we currently support. */
5573 /* Kill any debug uses outside LOOP of SSA names defined in STMT. */
5576 vect_loop_kill_debug_uses (struct loop
*loop
, gimple stmt
)
5578 ssa_op_iter op_iter
;
5579 imm_use_iterator imm_iter
;
5580 def_operand_p def_p
;
5583 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
5585 FOR_EACH_IMM_USE_STMT (ustmt
, imm_iter
, DEF_FROM_PTR (def_p
))
5589 if (!is_gimple_debug (ustmt
))
5592 bb
= gimple_bb (ustmt
);
5594 if (!flow_bb_inside_loop_p (loop
, bb
))
5596 if (gimple_debug_bind_p (ustmt
))
5598 if (dump_enabled_p ())
5599 dump_printf_loc (MSG_NOTE
, vect_location
,
5600 "killing debug use\n");
5602 gimple_debug_bind_reset_value (ustmt
);
5603 update_stmt (ustmt
);
5613 /* This function builds ni_name = number of iterations. Statements
5614 are emitted on the loop preheader edge. */
5617 vect_build_loop_niters (loop_vec_info loop_vinfo
)
5619 tree ni
= unshare_expr (LOOP_VINFO_NITERS (loop_vinfo
));
5620 if (TREE_CODE (ni
) == INTEGER_CST
)
5625 gimple_seq stmts
= NULL
;
5626 edge pe
= loop_preheader_edge (LOOP_VINFO_LOOP (loop_vinfo
));
5628 var
= create_tmp_var (TREE_TYPE (ni
), "niters");
5629 ni_name
= force_gimple_operand (ni
, &stmts
, false, var
);
5631 gsi_insert_seq_on_edge_immediate (pe
, stmts
);
5638 /* This function generates the following statements:
5640 ni_name = number of iterations loop executes
5641 ratio = ni_name / vf
5642 ratio_mult_vf_name = ratio * vf
5644 and places them on the loop preheader edge. */
5647 vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo
,
5649 tree
*ratio_mult_vf_name_ptr
,
5650 tree
*ratio_name_ptr
)
5652 tree ni_minus_gap_name
;
5655 tree ratio_mult_vf_name
;
5656 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
5657 edge pe
= loop_preheader_edge (LOOP_VINFO_LOOP (loop_vinfo
));
5660 log_vf
= build_int_cst (TREE_TYPE (ni_name
), exact_log2 (vf
));
5662 /* If epilogue loop is required because of data accesses with gaps, we
5663 subtract one iteration from the total number of iterations here for
5664 correct calculation of RATIO. */
5665 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
))
5667 ni_minus_gap_name
= fold_build2 (MINUS_EXPR
, TREE_TYPE (ni_name
),
5669 build_one_cst (TREE_TYPE (ni_name
)));
5670 if (!is_gimple_val (ni_minus_gap_name
))
5672 var
= create_tmp_var (TREE_TYPE (ni_name
), "ni_gap");
5673 gimple stmts
= NULL
;
5674 ni_minus_gap_name
= force_gimple_operand (ni_minus_gap_name
, &stmts
,
5676 gsi_insert_seq_on_edge_immediate (pe
, stmts
);
5680 ni_minus_gap_name
= ni_name
;
5682 /* Create: ratio = ni >> log2(vf) */
5683 /* ??? As we have ni == number of latch executions + 1, ni could
5684 have overflown to zero. So avoid computing ratio based on ni
5685 but compute it using the fact that we know ratio will be at least
5686 one, thus via (ni - vf) >> log2(vf) + 1. */
5688 = fold_build2 (PLUS_EXPR
, TREE_TYPE (ni_name
),
5689 fold_build2 (RSHIFT_EXPR
, TREE_TYPE (ni_name
),
5690 fold_build2 (MINUS_EXPR
, TREE_TYPE (ni_name
),
5693 (TREE_TYPE (ni_name
), vf
)),
5695 build_int_cst (TREE_TYPE (ni_name
), 1));
5696 if (!is_gimple_val (ratio_name
))
5698 var
= create_tmp_var (TREE_TYPE (ni_name
), "bnd");
5699 gimple stmts
= NULL
;
5700 ratio_name
= force_gimple_operand (ratio_name
, &stmts
, true, var
);
5701 gsi_insert_seq_on_edge_immediate (pe
, stmts
);
5703 *ratio_name_ptr
= ratio_name
;
5705 /* Create: ratio_mult_vf = ratio << log2 (vf). */
5707 if (ratio_mult_vf_name_ptr
)
5709 ratio_mult_vf_name
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (ratio_name
),
5710 ratio_name
, log_vf
);
5711 if (!is_gimple_val (ratio_mult_vf_name
))
5713 var
= create_tmp_var (TREE_TYPE (ni_name
), "ratio_mult_vf");
5714 gimple stmts
= NULL
;
5715 ratio_mult_vf_name
= force_gimple_operand (ratio_mult_vf_name
, &stmts
,
5717 gsi_insert_seq_on_edge_immediate (pe
, stmts
);
5719 *ratio_mult_vf_name_ptr
= ratio_mult_vf_name
;
5726 /* Function vect_transform_loop.
5728 The analysis phase has determined that the loop is vectorizable.
5729 Vectorize the loop - created vectorized stmts to replace the scalar
5730 stmts in the loop, and update the loop exit condition. */
5733 vect_transform_loop (loop_vec_info loop_vinfo
)
5735 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5736 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
5737 int nbbs
= loop
->num_nodes
;
5738 gimple_stmt_iterator si
;
5741 int vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
5743 bool slp_scheduled
= false;
5744 gimple stmt
, pattern_stmt
;
5745 gimple_seq pattern_def_seq
= NULL
;
5746 gimple_stmt_iterator pattern_def_si
= gsi_none ();
5747 bool transform_pattern_stmt
= false;
5748 bool check_profitability
= false;
5750 /* Record number of iterations before we started tampering with the profile. */
5751 gcov_type expected_iterations
= expected_loop_iterations_unbounded (loop
);
5753 if (dump_enabled_p ())
5754 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vec_transform_loop ===\n");
5756 /* If profile is inprecise, we have chance to fix it up. */
5757 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
5758 expected_iterations
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
5760 /* Use the more conservative vectorization threshold. If the number
5761 of iterations is constant assume the cost check has been performed
5762 by our caller. If the threshold makes all loops profitable that
5763 run at least the vectorization factor number of times checking
5764 is pointless, too. */
5765 th
= ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND
)
5766 * LOOP_VINFO_VECT_FACTOR (loop_vinfo
)) - 1);
5767 th
= MAX (th
, LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo
));
5768 if (th
>= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) - 1
5769 && !LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
5771 if (dump_enabled_p ())
5772 dump_printf_loc (MSG_NOTE
, vect_location
,
5773 "Profitability threshold is %d loop iterations.\n",
5775 check_profitability
= true;
5778 /* Version the loop first, if required, so the profitability check
5781 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
5782 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
5784 vect_loop_versioning (loop_vinfo
, th
, check_profitability
);
5785 check_profitability
= false;
5788 tree ni_name
= vect_build_loop_niters (loop_vinfo
);
5789 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo
) = ni_name
;
5791 /* Peel the loop if there are data refs with unknown alignment.
5792 Only one data ref with unknown store is allowed. */
5794 if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
))
5796 vect_do_peeling_for_alignment (loop_vinfo
, ni_name
,
5797 th
, check_profitability
);
5798 check_profitability
= false;
5799 /* The above adjusts LOOP_VINFO_NITERS, so cause ni_name to
5801 ni_name
= NULL_TREE
;
5804 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
5805 compile time constant), or it is a constant that doesn't divide by the
5806 vectorization factor, then an epilog loop needs to be created.
5807 We therefore duplicate the loop: the original loop will be vectorized,
5808 and will compute the first (n/VF) iterations. The second copy of the loop
5809 will remain scalar and will compute the remaining (n%VF) iterations.
5810 (VF is the vectorization factor). */
5812 if (LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo
)
5813 || LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
))
5817 ni_name
= vect_build_loop_niters (loop_vinfo
);
5818 vect_generate_tmps_on_preheader (loop_vinfo
, ni_name
, &ratio_mult_vf
,
5820 vect_do_peeling_for_loop_bound (loop_vinfo
, ni_name
, ratio_mult_vf
,
5821 th
, check_profitability
);
5823 else if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
5824 ratio
= build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo
)),
5825 LOOP_VINFO_INT_NITERS (loop_vinfo
) / vectorization_factor
);
5829 ni_name
= vect_build_loop_niters (loop_vinfo
);
5830 vect_generate_tmps_on_preheader (loop_vinfo
, ni_name
, NULL
, &ratio
);
5833 /* 1) Make sure the loop header has exactly two entries
5834 2) Make sure we have a preheader basic block. */
5836 gcc_assert (EDGE_COUNT (loop
->header
->preds
) == 2);
5838 split_edge (loop_preheader_edge (loop
));
5840 /* FORNOW: the vectorizer supports only loops which body consist
5841 of one basic block (header + empty latch). When the vectorizer will
5842 support more involved loop forms, the order by which the BBs are
5843 traversed need to be reconsidered. */
5845 for (i
= 0; i
< nbbs
; i
++)
5847 basic_block bb
= bbs
[i
];
5848 stmt_vec_info stmt_info
;
5851 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
5853 phi
= gsi_stmt (si
);
5854 if (dump_enabled_p ())
5856 dump_printf_loc (MSG_NOTE
, vect_location
,
5857 "------>vectorizing phi: ");
5858 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
5859 dump_printf (MSG_NOTE
, "\n");
5861 stmt_info
= vinfo_for_stmt (phi
);
5865 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
5866 vect_loop_kill_debug_uses (loop
, phi
);
5868 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
5869 && !STMT_VINFO_LIVE_P (stmt_info
))
5872 if (STMT_VINFO_VECTYPE (stmt_info
)
5873 && (TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
))
5874 != (unsigned HOST_WIDE_INT
) vectorization_factor
)
5875 && dump_enabled_p ())
5876 dump_printf_loc (MSG_NOTE
, vect_location
, "multiple-types.\n");
5878 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
5880 if (dump_enabled_p ())
5881 dump_printf_loc (MSG_NOTE
, vect_location
, "transform phi.\n");
5882 vect_transform_stmt (phi
, NULL
, NULL
, NULL
, NULL
);
5886 pattern_stmt
= NULL
;
5887 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
) || transform_pattern_stmt
;)
5891 if (transform_pattern_stmt
)
5892 stmt
= pattern_stmt
;
5895 stmt
= gsi_stmt (si
);
5896 /* During vectorization remove existing clobber stmts. */
5897 if (gimple_clobber_p (stmt
))
5899 unlink_stmt_vdef (stmt
);
5900 gsi_remove (&si
, true);
5901 release_defs (stmt
);
5906 if (dump_enabled_p ())
5908 dump_printf_loc (MSG_NOTE
, vect_location
,
5909 "------>vectorizing statement: ");
5910 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
5911 dump_printf (MSG_NOTE
, "\n");
5914 stmt_info
= vinfo_for_stmt (stmt
);
5916 /* vector stmts created in the outer-loop during vectorization of
5917 stmts in an inner-loop may not have a stmt_info, and do not
5918 need to be vectorized. */
5925 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
5926 vect_loop_kill_debug_uses (loop
, stmt
);
5928 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
5929 && !STMT_VINFO_LIVE_P (stmt_info
))
5931 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
5932 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
5933 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
5934 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
5936 stmt
= pattern_stmt
;
5937 stmt_info
= vinfo_for_stmt (stmt
);
5945 else if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
5946 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
5947 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
5948 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
5949 transform_pattern_stmt
= true;
5951 /* If pattern statement has def stmts, vectorize them too. */
5952 if (is_pattern_stmt_p (stmt_info
))
5954 if (pattern_def_seq
== NULL
)
5956 pattern_def_seq
= STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
);
5957 pattern_def_si
= gsi_start (pattern_def_seq
);
5959 else if (!gsi_end_p (pattern_def_si
))
5960 gsi_next (&pattern_def_si
);
5961 if (pattern_def_seq
!= NULL
)
5963 gimple pattern_def_stmt
= NULL
;
5964 stmt_vec_info pattern_def_stmt_info
= NULL
;
5966 while (!gsi_end_p (pattern_def_si
))
5968 pattern_def_stmt
= gsi_stmt (pattern_def_si
);
5969 pattern_def_stmt_info
5970 = vinfo_for_stmt (pattern_def_stmt
);
5971 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info
)
5972 || STMT_VINFO_LIVE_P (pattern_def_stmt_info
))
5974 gsi_next (&pattern_def_si
);
5977 if (!gsi_end_p (pattern_def_si
))
5979 if (dump_enabled_p ())
5981 dump_printf_loc (MSG_NOTE
, vect_location
,
5982 "==> vectorizing pattern def "
5984 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
5985 pattern_def_stmt
, 0);
5986 dump_printf (MSG_NOTE
, "\n");
5989 stmt
= pattern_def_stmt
;
5990 stmt_info
= pattern_def_stmt_info
;
5994 pattern_def_si
= gsi_none ();
5995 transform_pattern_stmt
= false;
5999 transform_pattern_stmt
= false;
6002 if (STMT_VINFO_VECTYPE (stmt_info
))
6006 TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
6007 if (!STMT_SLP_TYPE (stmt_info
)
6008 && nunits
!= (unsigned int) vectorization_factor
6009 && dump_enabled_p ())
6010 /* For SLP VF is set according to unrolling factor, and not
6011 to vector size, hence for SLP this print is not valid. */
6012 dump_printf_loc (MSG_NOTE
, vect_location
, "multiple-types.\n");
6015 /* SLP. Schedule all the SLP instances when the first SLP stmt is
6017 if (STMT_SLP_TYPE (stmt_info
))
6021 slp_scheduled
= true;
6023 if (dump_enabled_p ())
6024 dump_printf_loc (MSG_NOTE
, vect_location
,
6025 "=== scheduling SLP instances ===\n");
6027 vect_schedule_slp (loop_vinfo
, NULL
);
6030 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
6031 if (!vinfo_for_stmt (stmt
) || PURE_SLP_STMT (stmt_info
))
6033 if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
6035 pattern_def_seq
= NULL
;
6042 /* -------- vectorize statement ------------ */
6043 if (dump_enabled_p ())
6044 dump_printf_loc (MSG_NOTE
, vect_location
, "transform statement.\n");
6046 grouped_store
= false;
6047 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, NULL
, NULL
);
6050 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
6052 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
6053 interleaving chain was completed - free all the stores in
6056 vect_remove_stores (GROUP_FIRST_ELEMENT (stmt_info
));
6061 /* Free the attached stmt_vec_info and remove the stmt. */
6062 gimple store
= gsi_stmt (si
);
6063 free_stmt_vec_info (store
);
6064 unlink_stmt_vdef (store
);
6065 gsi_remove (&si
, true);
6066 release_defs (store
);
6071 if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
6073 pattern_def_seq
= NULL
;
6079 slpeel_make_loop_iterate_ntimes (loop
, ratio
);
6081 /* Reduce loop iterations by the vectorization factor. */
6082 scale_loop_profile (loop
, GCOV_COMPUTE_SCALE (1, vectorization_factor
),
6083 expected_iterations
/ vectorization_factor
);
6084 loop
->nb_iterations_upper_bound
6085 = loop
->nb_iterations_upper_bound
.udiv (double_int::from_uhwi (vectorization_factor
),
6087 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
6088 && loop
->nb_iterations_upper_bound
!= double_int_zero
)
6089 loop
->nb_iterations_upper_bound
= loop
->nb_iterations_upper_bound
- double_int_one
;
6090 if (loop
->any_estimate
)
6092 loop
->nb_iterations_estimate
6093 = loop
->nb_iterations_estimate
.udiv (double_int::from_uhwi (vectorization_factor
),
6095 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
6096 && loop
->nb_iterations_estimate
!= double_int_zero
)
6097 loop
->nb_iterations_estimate
= loop
->nb_iterations_estimate
- double_int_one
;
6100 if (dump_enabled_p ())
6102 dump_printf_loc (MSG_NOTE
, vect_location
,
6103 "LOOP VECTORIZED\n");
6105 dump_printf_loc (MSG_NOTE
, vect_location
,
6106 "OUTER LOOP VECTORIZED\n");
6107 dump_printf (MSG_NOTE
, "\n");