2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com> and
4 Ira Rosen <irar@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "gimple-pretty-print.h"
31 #include "tree-flow.h"
32 #include "tree-pass.h"
38 #include "diagnostic-core.h"
39 #include "tree-chrec.h"
40 #include "tree-scalar-evolution.h"
41 #include "tree-vectorizer.h"
44 /* Loop Vectorization Pass.
46 This pass tries to vectorize loops.
48 For example, the vectorizer transforms the following simple loop:
50 short a[N]; short b[N]; short c[N]; int i;
56 as if it was manually vectorized by rewriting the source code into:
58 typedef int __attribute__((mode(V8HI))) v8hi;
59 short a[N]; short b[N]; short c[N]; int i;
60 v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
63 for (i=0; i<N/8; i++){
70 The main entry to this pass is vectorize_loops(), in which
71 the vectorizer applies a set of analyses on a given set of loops,
72 followed by the actual vectorization transformation for the loops that
73 had successfully passed the analysis phase.
74 Throughout this pass we make a distinction between two types of
75 data: scalars (which are represented by SSA_NAMES), and memory references
76 ("data-refs"). These two types of data require different handling both
77 during analysis and transformation. The types of data-refs that the
78 vectorizer currently supports are ARRAY_REFS which base is an array DECL
79 (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
80 accesses are required to have a simple (consecutive) access pattern.
84 The driver for the analysis phase is vect_analyze_loop().
85 It applies a set of analyses, some of which rely on the scalar evolution
86 analyzer (scev) developed by Sebastian Pop.
88 During the analysis phase the vectorizer records some information
89 per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
90 loop, as well as general information about the loop as a whole, which is
91 recorded in a "loop_vec_info" struct attached to each loop.
95 The loop transformation phase scans all the stmts in the loop, and
96 creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
97 the loop that needs to be vectorized. It inserts the vector code sequence
98 just before the scalar stmt S, and records a pointer to the vector code
99 in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
100 attached to S). This pointer will be used for the vectorization of following
101 stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
102 otherwise, we rely on dead code elimination for removing it.
104 For example, say stmt S1 was vectorized into stmt VS1:
107 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
110 To vectorize stmt S2, the vectorizer first finds the stmt that defines
111 the operand 'b' (S1), and gets the relevant vector def 'vb' from the
112 vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
113 resulting sequence would be:
116 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
118 S2: a = b; STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
120 Operands that are not SSA_NAMEs, are data-refs that appear in
121 load/store operations (like 'x[i]' in S1), and are handled differently.
125 Currently the only target specific information that is used is the
126 size of the vector (in bytes) - "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD".
127 Targets that can support different sizes of vectors, for now will need
128 to specify one value for "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD". More
129 flexibility will be added in the future.
131 Since we only vectorize operations which vector form can be
132 expressed using existing tree codes, to verify that an operation is
133 supported, the vectorizer checks the relevant optab at the relevant
134 machine_mode (e.g, optab_handler (add_optab, V8HImode)). If
135 the value found is CODE_FOR_nothing, then there's no target support, and
136 we can't vectorize the stmt.
138 For additional information on this project see:
139 http://gcc.gnu.org/projects/tree-ssa/vectorization.html
142 static void vect_estimate_min_profitable_iters (loop_vec_info
, int *, int *);
144 /* Function vect_determine_vectorization_factor
146 Determine the vectorization factor (VF). VF is the number of data elements
147 that are operated upon in parallel in a single iteration of the vectorized
148 loop. For example, when vectorizing a loop that operates on 4byte elements,
149 on a target with vector size (VS) 16byte, the VF is set to 4, since 4
150 elements can fit in a single vector register.
152 We currently support vectorization of loops in which all types operated upon
153 are of the same size. Therefore this function currently sets VF according to
154 the size of the types operated upon, and fails if there are multiple sizes
157 VF is also the factor by which the loop iterations are strip-mined, e.g.:
164 for (i=0; i<N; i+=VF){
165 a[i:VF] = b[i:VF] + c[i:VF];
170 vect_determine_vectorization_factor (loop_vec_info loop_vinfo
)
172 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
173 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
174 int nbbs
= loop
->num_nodes
;
175 gimple_stmt_iterator si
;
176 unsigned int vectorization_factor
= 0;
181 stmt_vec_info stmt_info
;
184 gimple stmt
, pattern_stmt
= NULL
;
185 gimple_seq pattern_def_seq
= NULL
;
186 gimple_stmt_iterator pattern_def_si
= gsi_none ();
187 bool analyze_pattern_stmt
= false;
189 if (dump_enabled_p ())
190 dump_printf_loc (MSG_NOTE
, vect_location
,
191 "=== vect_determine_vectorization_factor ===");
193 for (i
= 0; i
< nbbs
; i
++)
195 basic_block bb
= bbs
[i
];
197 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
200 stmt_info
= vinfo_for_stmt (phi
);
201 if (dump_enabled_p ())
203 dump_printf_loc (MSG_NOTE
, vect_location
, "==> examining phi: ");
204 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
207 gcc_assert (stmt_info
);
209 if (STMT_VINFO_RELEVANT_P (stmt_info
))
211 gcc_assert (!STMT_VINFO_VECTYPE (stmt_info
));
212 scalar_type
= TREE_TYPE (PHI_RESULT (phi
));
214 if (dump_enabled_p ())
216 dump_printf_loc (MSG_NOTE
, vect_location
,
217 "get vectype for scalar type: ");
218 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
221 vectype
= get_vectype_for_scalar_type (scalar_type
);
224 if (dump_enabled_p ())
226 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
227 "not vectorized: unsupported "
229 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
234 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
236 if (dump_enabled_p ())
238 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
239 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vectype
);
242 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
243 if (dump_enabled_p ())
244 dump_printf_loc (MSG_NOTE
, vect_location
, "nunits = %d", nunits
);
246 if (!vectorization_factor
247 || (nunits
> vectorization_factor
))
248 vectorization_factor
= nunits
;
252 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
) || analyze_pattern_stmt
;)
256 if (analyze_pattern_stmt
)
259 stmt
= gsi_stmt (si
);
261 stmt_info
= vinfo_for_stmt (stmt
);
263 if (dump_enabled_p ())
265 dump_printf_loc (MSG_NOTE
, vect_location
,
266 "==> examining statement: ");
267 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
270 gcc_assert (stmt_info
);
272 /* Skip stmts which do not need to be vectorized. */
273 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
274 && !STMT_VINFO_LIVE_P (stmt_info
))
276 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
277 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
278 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
279 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
282 stmt_info
= vinfo_for_stmt (pattern_stmt
);
283 if (dump_enabled_p ())
285 dump_printf_loc (MSG_NOTE
, vect_location
,
286 "==> examining pattern statement: ");
287 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
292 if (dump_enabled_p ())
293 dump_printf_loc (MSG_NOTE
, vect_location
, "skip.");
298 else 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
))))
302 analyze_pattern_stmt
= true;
304 /* If a pattern statement has def stmts, analyze them too. */
305 if (is_pattern_stmt_p (stmt_info
))
307 if (pattern_def_seq
== NULL
)
309 pattern_def_seq
= STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
);
310 pattern_def_si
= gsi_start (pattern_def_seq
);
312 else if (!gsi_end_p (pattern_def_si
))
313 gsi_next (&pattern_def_si
);
314 if (pattern_def_seq
!= NULL
)
316 gimple pattern_def_stmt
= NULL
;
317 stmt_vec_info pattern_def_stmt_info
= NULL
;
319 while (!gsi_end_p (pattern_def_si
))
321 pattern_def_stmt
= gsi_stmt (pattern_def_si
);
322 pattern_def_stmt_info
323 = vinfo_for_stmt (pattern_def_stmt
);
324 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info
)
325 || STMT_VINFO_LIVE_P (pattern_def_stmt_info
))
327 gsi_next (&pattern_def_si
);
330 if (!gsi_end_p (pattern_def_si
))
332 if (dump_enabled_p ())
334 dump_printf_loc (MSG_NOTE
, vect_location
,
335 "==> examining pattern def stmt: ");
336 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
337 pattern_def_stmt
, 0);
340 stmt
= pattern_def_stmt
;
341 stmt_info
= pattern_def_stmt_info
;
345 pattern_def_si
= gsi_none ();
346 analyze_pattern_stmt
= false;
350 analyze_pattern_stmt
= false;
353 if (gimple_get_lhs (stmt
) == NULL_TREE
)
355 if (dump_enabled_p ())
357 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
358 "not vectorized: irregular stmt.");
359 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
,
365 if (VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt
))))
367 if (dump_enabled_p ())
369 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
370 "not vectorized: vector stmt in loop:");
371 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
376 if (STMT_VINFO_VECTYPE (stmt_info
))
378 /* The only case when a vectype had been already set is for stmts
379 that contain a dataref, or for "pattern-stmts" (stmts
380 generated by the vectorizer to represent/replace a certain
382 gcc_assert (STMT_VINFO_DATA_REF (stmt_info
)
383 || is_pattern_stmt_p (stmt_info
)
384 || !gsi_end_p (pattern_def_si
));
385 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
389 gcc_assert (!STMT_VINFO_DATA_REF (stmt_info
));
390 scalar_type
= TREE_TYPE (gimple_get_lhs (stmt
));
391 if (dump_enabled_p ())
393 dump_printf_loc (MSG_NOTE
, vect_location
,
394 "get vectype for scalar type: ");
395 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
397 vectype
= get_vectype_for_scalar_type (scalar_type
);
400 if (dump_enabled_p ())
402 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
403 "not vectorized: unsupported "
405 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
411 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
413 if (dump_enabled_p ())
415 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
416 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vectype
);
420 /* The vectorization factor is according to the smallest
421 scalar type (or the largest vector size, but we only
422 support one vector size per loop). */
423 scalar_type
= vect_get_smallest_scalar_type (stmt
, &dummy
,
425 if (dump_enabled_p ())
427 dump_printf_loc (MSG_NOTE
, vect_location
,
428 "get vectype for scalar type: ");
429 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
431 vf_vectype
= get_vectype_for_scalar_type (scalar_type
);
434 if (dump_enabled_p ())
436 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
437 "not vectorized: unsupported data-type ");
438 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
444 if ((GET_MODE_SIZE (TYPE_MODE (vectype
))
445 != GET_MODE_SIZE (TYPE_MODE (vf_vectype
))))
447 if (dump_enabled_p ())
449 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
450 "not vectorized: different sized vector "
451 "types in statement, ");
452 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
454 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
455 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
461 if (dump_enabled_p ())
463 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
464 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vf_vectype
);
467 nunits
= TYPE_VECTOR_SUBPARTS (vf_vectype
);
468 if (dump_enabled_p ())
469 dump_printf_loc (MSG_NOTE
, vect_location
, "nunits = %d", nunits
);
470 if (!vectorization_factor
471 || (nunits
> vectorization_factor
))
472 vectorization_factor
= nunits
;
474 if (!analyze_pattern_stmt
&& gsi_end_p (pattern_def_si
))
476 pattern_def_seq
= NULL
;
482 /* TODO: Analyze cost. Decide if worth while to vectorize. */
483 if (dump_enabled_p ())
484 dump_printf_loc (MSG_NOTE
, vect_location
, "vectorization factor = %d",
485 vectorization_factor
);
486 if (vectorization_factor
<= 1)
488 if (dump_enabled_p ())
489 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
490 "not vectorized: unsupported data-type");
493 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
499 /* Function vect_is_simple_iv_evolution.
501 FORNOW: A simple evolution of an induction variables in the loop is
502 considered a polynomial evolution with constant step. */
505 vect_is_simple_iv_evolution (unsigned loop_nb
, tree access_fn
, tree
* init
,
510 tree evolution_part
= evolution_part_in_loop_num (access_fn
, loop_nb
);
512 /* When there is no evolution in this loop, the evolution function
514 if (evolution_part
== NULL_TREE
)
517 /* When the evolution is a polynomial of degree >= 2
518 the evolution function is not "simple". */
519 if (tree_is_chrec (evolution_part
))
522 step_expr
= evolution_part
;
523 init_expr
= unshare_expr (initial_condition_in_loop_num (access_fn
, loop_nb
));
525 if (dump_enabled_p ())
527 dump_printf_loc (MSG_NOTE
, vect_location
, "step: ");
528 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, step_expr
);
529 dump_printf (MSG_NOTE
, ", init: ");
530 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, init_expr
);
536 if (TREE_CODE (step_expr
) != INTEGER_CST
)
538 if (dump_enabled_p ())
539 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
547 /* Function vect_analyze_scalar_cycles_1.
549 Examine the cross iteration def-use cycles of scalar variables
550 in LOOP. LOOP_VINFO represents the loop that is now being
551 considered for vectorization (can be LOOP, or an outer-loop
555 vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo
, struct loop
*loop
)
557 basic_block bb
= loop
->header
;
559 vec
<gimple
> worklist
;
560 worklist
.create (64);
561 gimple_stmt_iterator gsi
;
564 if (dump_enabled_p ())
565 dump_printf_loc (MSG_NOTE
, vect_location
,
566 "=== vect_analyze_scalar_cycles ===");
568 /* First - identify all inductions. Reduction detection assumes that all the
569 inductions have been identified, therefore, this order must not be
571 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
573 gimple phi
= gsi_stmt (gsi
);
574 tree access_fn
= NULL
;
575 tree def
= PHI_RESULT (phi
);
576 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (phi
);
578 if (dump_enabled_p ())
580 dump_printf_loc (MSG_NOTE
, vect_location
, "Analyze phi: ");
581 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
584 /* Skip virtual phi's. The data dependences that are associated with
585 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
586 if (virtual_operand_p (def
))
589 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_unknown_def_type
;
591 /* Analyze the evolution function. */
592 access_fn
= analyze_scalar_evolution (loop
, def
);
595 STRIP_NOPS (access_fn
);
596 if (dump_enabled_p ())
598 dump_printf_loc (MSG_NOTE
, vect_location
,
599 "Access function of PHI: ");
600 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, access_fn
);
602 STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
)
603 = evolution_part_in_loop_num (access_fn
, loop
->num
);
607 || !vect_is_simple_iv_evolution (loop
->num
, access_fn
, &dumy
, &dumy
))
609 worklist
.safe_push (phi
);
613 gcc_assert (STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
) != NULL_TREE
);
615 if (dump_enabled_p ())
616 dump_printf_loc (MSG_NOTE
, vect_location
, "Detected induction.");
617 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_induction_def
;
621 /* Second - identify all reductions and nested cycles. */
622 while (worklist
.length () > 0)
624 gimple phi
= worklist
.pop ();
625 tree def
= PHI_RESULT (phi
);
626 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (phi
);
630 if (dump_enabled_p ())
632 dump_printf_loc (MSG_NOTE
, vect_location
, "Analyze phi: ");
633 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
636 gcc_assert (!virtual_operand_p (def
)
637 && STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_unknown_def_type
);
639 nested_cycle
= (loop
!= LOOP_VINFO_LOOP (loop_vinfo
));
640 reduc_stmt
= vect_force_simple_reduction (loop_vinfo
, phi
, !nested_cycle
,
646 if (dump_enabled_p ())
647 dump_printf_loc (MSG_NOTE
, vect_location
,
648 "Detected double reduction.");
650 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_double_reduction_def
;
651 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
652 vect_double_reduction_def
;
658 if (dump_enabled_p ())
659 dump_printf_loc (MSG_NOTE
, vect_location
,
660 "Detected vectorizable nested cycle.");
662 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_nested_cycle
;
663 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
668 if (dump_enabled_p ())
669 dump_printf_loc (MSG_NOTE
, vect_location
,
670 "Detected reduction.");
672 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_reduction_def
;
673 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
675 /* Store the reduction cycles for possible vectorization in
677 LOOP_VINFO_REDUCTIONS (loop_vinfo
).safe_push (reduc_stmt
);
682 if (dump_enabled_p ())
683 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
684 "Unknown def-use cycle pattern.");
691 /* Function vect_analyze_scalar_cycles.
693 Examine the cross iteration def-use cycles of scalar variables, by
694 analyzing the loop-header PHIs of scalar variables. Classify each
695 cycle as one of the following: invariant, induction, reduction, unknown.
696 We do that for the loop represented by LOOP_VINFO, and also to its
697 inner-loop, if exists.
698 Examples for scalar cycles:
713 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo
)
715 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
717 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
);
719 /* When vectorizing an outer-loop, the inner-loop is executed sequentially.
720 Reductions in such inner-loop therefore have different properties than
721 the reductions in the nest that gets vectorized:
722 1. When vectorized, they are executed in the same order as in the original
723 scalar loop, so we can't change the order of computation when
725 2. FIXME: Inner-loop reductions can be used in the inner-loop, so the
726 current checks are too strict. */
729 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
->inner
);
732 /* Function vect_get_loop_niters.
734 Determine how many iterations the loop is executed.
735 If an expression that represents the number of iterations
736 can be constructed, place it in NUMBER_OF_ITERATIONS.
737 Return the loop exit condition. */
740 vect_get_loop_niters (struct loop
*loop
, tree
*number_of_iterations
)
744 if (dump_enabled_p ())
745 dump_printf_loc (MSG_NOTE
, vect_location
,
746 "=== get_loop_niters ===");
747 niters
= number_of_exit_cond_executions (loop
);
749 if (niters
!= NULL_TREE
750 && niters
!= chrec_dont_know
)
752 *number_of_iterations
= niters
;
754 if (dump_enabled_p ())
756 dump_printf_loc (MSG_NOTE
, vect_location
, "==> get_loop_niters:");
757 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, *number_of_iterations
);
761 return get_loop_exit_condition (loop
);
765 /* Function bb_in_loop_p
767 Used as predicate for dfs order traversal of the loop bbs. */
770 bb_in_loop_p (const_basic_block bb
, const void *data
)
772 const struct loop
*const loop
= (const struct loop
*)data
;
773 if (flow_bb_inside_loop_p (loop
, bb
))
779 /* Function new_loop_vec_info.
781 Create and initialize a new loop_vec_info struct for LOOP, as well as
782 stmt_vec_info structs for all the stmts in LOOP. */
785 new_loop_vec_info (struct loop
*loop
)
789 gimple_stmt_iterator si
;
790 unsigned int i
, nbbs
;
792 res
= (loop_vec_info
) xcalloc (1, sizeof (struct _loop_vec_info
));
793 LOOP_VINFO_LOOP (res
) = loop
;
795 bbs
= get_loop_body (loop
);
797 /* Create/Update stmt_info for all stmts in the loop. */
798 for (i
= 0; i
< loop
->num_nodes
; i
++)
800 basic_block bb
= bbs
[i
];
802 /* BBs in a nested inner-loop will have been already processed (because
803 we will have called vect_analyze_loop_form for any nested inner-loop).
804 Therefore, for stmts in an inner-loop we just want to update the
805 STMT_VINFO_LOOP_VINFO field of their stmt_info to point to the new
806 loop_info of the outer-loop we are currently considering to vectorize
807 (instead of the loop_info of the inner-loop).
808 For stmts in other BBs we need to create a stmt_info from scratch. */
809 if (bb
->loop_father
!= loop
)
812 gcc_assert (loop
->inner
&& bb
->loop_father
== loop
->inner
);
813 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
815 gimple phi
= gsi_stmt (si
);
816 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
817 loop_vec_info inner_loop_vinfo
=
818 STMT_VINFO_LOOP_VINFO (stmt_info
);
819 gcc_assert (loop
->inner
== LOOP_VINFO_LOOP (inner_loop_vinfo
));
820 STMT_VINFO_LOOP_VINFO (stmt_info
) = res
;
822 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
824 gimple stmt
= gsi_stmt (si
);
825 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
826 loop_vec_info inner_loop_vinfo
=
827 STMT_VINFO_LOOP_VINFO (stmt_info
);
828 gcc_assert (loop
->inner
== LOOP_VINFO_LOOP (inner_loop_vinfo
));
829 STMT_VINFO_LOOP_VINFO (stmt_info
) = res
;
834 /* bb in current nest. */
835 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
837 gimple phi
= gsi_stmt (si
);
838 gimple_set_uid (phi
, 0);
839 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, res
, NULL
));
842 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
844 gimple stmt
= gsi_stmt (si
);
845 gimple_set_uid (stmt
, 0);
846 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, res
, NULL
));
851 /* CHECKME: We want to visit all BBs before their successors (except for
852 latch blocks, for which this assertion wouldn't hold). In the simple
853 case of the loop forms we allow, a dfs order of the BBs would the same
854 as reversed postorder traversal, so we are safe. */
857 bbs
= XCNEWVEC (basic_block
, loop
->num_nodes
);
858 nbbs
= dfs_enumerate_from (loop
->header
, 0, bb_in_loop_p
,
859 bbs
, loop
->num_nodes
, loop
);
860 gcc_assert (nbbs
== loop
->num_nodes
);
862 LOOP_VINFO_BBS (res
) = bbs
;
863 LOOP_VINFO_NITERS (res
) = NULL
;
864 LOOP_VINFO_NITERS_UNCHANGED (res
) = NULL
;
865 LOOP_VINFO_COST_MODEL_MIN_ITERS (res
) = 0;
866 LOOP_VINFO_VECTORIZABLE_P (res
) = 0;
867 LOOP_PEELING_FOR_ALIGNMENT (res
) = 0;
868 LOOP_VINFO_VECT_FACTOR (res
) = 0;
869 LOOP_VINFO_LOOP_NEST (res
).create (3);
870 LOOP_VINFO_DATAREFS (res
).create (10);
871 LOOP_VINFO_DDRS (res
).create (10 * 10);
872 LOOP_VINFO_UNALIGNED_DR (res
) = NULL
;
873 LOOP_VINFO_MAY_MISALIGN_STMTS (res
).create (
874 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS
));
875 LOOP_VINFO_MAY_ALIAS_DDRS (res
).create (
876 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS
));
877 LOOP_VINFO_GROUPED_STORES (res
).create (10);
878 LOOP_VINFO_REDUCTIONS (res
).create (10);
879 LOOP_VINFO_REDUCTION_CHAINS (res
).create (10);
880 LOOP_VINFO_SLP_INSTANCES (res
).create (10);
881 LOOP_VINFO_SLP_UNROLLING_FACTOR (res
) = 1;
882 LOOP_VINFO_PEELING_HTAB (res
) = NULL
;
883 LOOP_VINFO_TARGET_COST_DATA (res
) = init_cost (loop
);
884 LOOP_VINFO_PEELING_FOR_GAPS (res
) = false;
885 LOOP_VINFO_OPERANDS_SWAPPED (res
) = false;
891 /* Function destroy_loop_vec_info.
893 Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
894 stmts in the loop. */
897 destroy_loop_vec_info (loop_vec_info loop_vinfo
, bool clean_stmts
)
902 gimple_stmt_iterator si
;
904 vec
<slp_instance
> slp_instances
;
905 slp_instance instance
;
911 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
913 bbs
= LOOP_VINFO_BBS (loop_vinfo
);
914 nbbs
= clean_stmts
? loop
->num_nodes
: 0;
915 swapped
= LOOP_VINFO_OPERANDS_SWAPPED (loop_vinfo
);
917 for (j
= 0; j
< nbbs
; j
++)
919 basic_block bb
= bbs
[j
];
920 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
921 free_stmt_vec_info (gsi_stmt (si
));
923 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); )
925 gimple stmt
= gsi_stmt (si
);
927 /* We may have broken canonical form by moving a constant
928 into RHS1 of a commutative op. Fix such occurrences. */
929 if (swapped
&& is_gimple_assign (stmt
))
931 enum tree_code code
= gimple_assign_rhs_code (stmt
);
933 if ((code
== PLUS_EXPR
934 || code
== POINTER_PLUS_EXPR
935 || code
== MULT_EXPR
)
936 && CONSTANT_CLASS_P (gimple_assign_rhs1 (stmt
)))
937 swap_tree_operands (stmt
,
938 gimple_assign_rhs1_ptr (stmt
),
939 gimple_assign_rhs2_ptr (stmt
));
942 /* Free stmt_vec_info. */
943 free_stmt_vec_info (stmt
);
948 free (LOOP_VINFO_BBS (loop_vinfo
));
949 free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo
));
950 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo
));
951 LOOP_VINFO_LOOP_NEST (loop_vinfo
).release ();
952 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).release ();
953 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
).release ();
954 slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
955 FOR_EACH_VEC_ELT (slp_instances
, j
, instance
)
956 vect_free_slp_instance (instance
);
958 LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).release ();
959 LOOP_VINFO_GROUPED_STORES (loop_vinfo
).release ();
960 LOOP_VINFO_REDUCTIONS (loop_vinfo
).release ();
961 LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
).release ();
963 if (LOOP_VINFO_PEELING_HTAB (loop_vinfo
))
964 htab_delete (LOOP_VINFO_PEELING_HTAB (loop_vinfo
));
966 destroy_cost_data (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
));
973 /* Function vect_analyze_loop_1.
975 Apply a set of analyses on LOOP, and create a loop_vec_info struct
976 for it. The different analyses will record information in the
977 loop_vec_info struct. This is a subset of the analyses applied in
978 vect_analyze_loop, to be applied on an inner-loop nested in the loop
979 that is now considered for (outer-loop) vectorization. */
982 vect_analyze_loop_1 (struct loop
*loop
)
984 loop_vec_info loop_vinfo
;
986 if (dump_enabled_p ())
987 dump_printf_loc (MSG_NOTE
, vect_location
,
988 "===== analyze_loop_nest_1 =====");
990 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
992 loop_vinfo
= vect_analyze_loop_form (loop
);
995 if (dump_enabled_p ())
996 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
997 "bad inner-loop form.");
1005 /* Function vect_analyze_loop_form.
1007 Verify that certain CFG restrictions hold, including:
1008 - the loop has a pre-header
1009 - the loop has a single entry and exit
1010 - the loop exit condition is simple enough, and the number of iterations
1011 can be analyzed (a countable loop). */
1014 vect_analyze_loop_form (struct loop
*loop
)
1016 loop_vec_info loop_vinfo
;
1018 tree number_of_iterations
= NULL
;
1019 loop_vec_info inner_loop_vinfo
= NULL
;
1021 if (dump_enabled_p ())
1022 dump_printf_loc (MSG_NOTE
, vect_location
,
1023 "=== vect_analyze_loop_form ===");
1025 /* Different restrictions apply when we are considering an inner-most loop,
1026 vs. an outer (nested) loop.
1027 (FORNOW. May want to relax some of these restrictions in the future). */
1031 /* Inner-most loop. We currently require that the number of BBs is
1032 exactly 2 (the header and latch). Vectorizable inner-most loops
1043 if (loop
->num_nodes
!= 2)
1045 if (dump_enabled_p ())
1046 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1047 "not vectorized: control flow in loop.");
1051 if (empty_block_p (loop
->header
))
1053 if (dump_enabled_p ())
1054 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1055 "not vectorized: empty loop.");
1061 struct loop
*innerloop
= loop
->inner
;
1064 /* Nested loop. We currently require that the loop is doubly-nested,
1065 contains a single inner loop, and the number of BBs is exactly 5.
1066 Vectorizable outer-loops look like this:
1078 The inner-loop has the properties expected of inner-most loops
1079 as described above. */
1081 if ((loop
->inner
)->inner
|| (loop
->inner
)->next
)
1083 if (dump_enabled_p ())
1084 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1085 "not vectorized: multiple nested loops.");
1089 /* Analyze the inner-loop. */
1090 inner_loop_vinfo
= vect_analyze_loop_1 (loop
->inner
);
1091 if (!inner_loop_vinfo
)
1093 if (dump_enabled_p ())
1094 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1095 "not vectorized: Bad inner loop.");
1099 if (!expr_invariant_in_loop_p (loop
,
1100 LOOP_VINFO_NITERS (inner_loop_vinfo
)))
1102 if (dump_enabled_p ())
1103 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1104 "not vectorized: inner-loop count not invariant.");
1105 destroy_loop_vec_info (inner_loop_vinfo
, true);
1109 if (loop
->num_nodes
!= 5)
1111 if (dump_enabled_p ())
1112 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1113 "not vectorized: control flow in loop.");
1114 destroy_loop_vec_info (inner_loop_vinfo
, true);
1118 gcc_assert (EDGE_COUNT (innerloop
->header
->preds
) == 2);
1119 entryedge
= EDGE_PRED (innerloop
->header
, 0);
1120 if (EDGE_PRED (innerloop
->header
, 0)->src
== innerloop
->latch
)
1121 entryedge
= EDGE_PRED (innerloop
->header
, 1);
1123 if (entryedge
->src
!= loop
->header
1124 || !single_exit (innerloop
)
1125 || single_exit (innerloop
)->dest
!= EDGE_PRED (loop
->latch
, 0)->src
)
1127 if (dump_enabled_p ())
1128 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1129 "not vectorized: unsupported outerloop form.");
1130 destroy_loop_vec_info (inner_loop_vinfo
, true);
1134 if (dump_enabled_p ())
1135 dump_printf_loc (MSG_NOTE
, vect_location
,
1136 "Considering outer-loop vectorization.");
1139 if (!single_exit (loop
)
1140 || EDGE_COUNT (loop
->header
->preds
) != 2)
1142 if (dump_enabled_p ())
1144 if (!single_exit (loop
))
1145 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1146 "not vectorized: multiple exits.");
1147 else if (EDGE_COUNT (loop
->header
->preds
) != 2)
1148 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1149 "not vectorized: too many incoming edges.");
1151 if (inner_loop_vinfo
)
1152 destroy_loop_vec_info (inner_loop_vinfo
, true);
1156 /* We assume that the loop exit condition is at the end of the loop. i.e,
1157 that the loop is represented as a do-while (with a proper if-guard
1158 before the loop if needed), where the loop header contains all the
1159 executable statements, and the latch is empty. */
1160 if (!empty_block_p (loop
->latch
)
1161 || !gimple_seq_empty_p (phi_nodes (loop
->latch
)))
1163 if (dump_enabled_p ())
1164 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1165 "not vectorized: latch block not empty.");
1166 if (inner_loop_vinfo
)
1167 destroy_loop_vec_info (inner_loop_vinfo
, true);
1171 /* Make sure there exists a single-predecessor exit bb: */
1172 if (!single_pred_p (single_exit (loop
)->dest
))
1174 edge e
= single_exit (loop
);
1175 if (!(e
->flags
& EDGE_ABNORMAL
))
1177 split_loop_exit_edge (e
);
1178 if (dump_enabled_p ())
1179 dump_printf (MSG_NOTE
, "split exit edge.");
1183 if (dump_enabled_p ())
1184 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1185 "not vectorized: abnormal loop exit edge.");
1186 if (inner_loop_vinfo
)
1187 destroy_loop_vec_info (inner_loop_vinfo
, true);
1192 loop_cond
= vect_get_loop_niters (loop
, &number_of_iterations
);
1195 if (dump_enabled_p ())
1196 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1197 "not vectorized: complicated exit condition.");
1198 if (inner_loop_vinfo
)
1199 destroy_loop_vec_info (inner_loop_vinfo
, true);
1203 if (!number_of_iterations
)
1205 if (dump_enabled_p ())
1206 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1207 "not vectorized: number of iterations cannot be "
1209 if (inner_loop_vinfo
)
1210 destroy_loop_vec_info (inner_loop_vinfo
, true);
1214 if (chrec_contains_undetermined (number_of_iterations
))
1216 if (dump_enabled_p ())
1217 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1218 "Infinite number of iterations.");
1219 if (inner_loop_vinfo
)
1220 destroy_loop_vec_info (inner_loop_vinfo
, true);
1224 if (!NITERS_KNOWN_P (number_of_iterations
))
1226 if (dump_enabled_p ())
1228 dump_printf_loc (MSG_NOTE
, vect_location
,
1229 "Symbolic number of iterations is ");
1230 dump_generic_expr (MSG_NOTE
, TDF_DETAILS
, number_of_iterations
);
1233 else if (TREE_INT_CST_LOW (number_of_iterations
) == 0)
1235 if (dump_enabled_p ())
1236 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1237 "not vectorized: number of iterations = 0.");
1238 if (inner_loop_vinfo
)
1239 destroy_loop_vec_info (inner_loop_vinfo
, true);
1243 loop_vinfo
= new_loop_vec_info (loop
);
1244 LOOP_VINFO_NITERS (loop_vinfo
) = number_of_iterations
;
1245 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo
) = number_of_iterations
;
1247 STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond
)) = loop_exit_ctrl_vec_info_type
;
1249 /* CHECKME: May want to keep it around it in the future. */
1250 if (inner_loop_vinfo
)
1251 destroy_loop_vec_info (inner_loop_vinfo
, false);
1253 gcc_assert (!loop
->aux
);
1254 loop
->aux
= loop_vinfo
;
1259 /* Function vect_analyze_loop_operations.
1261 Scan the loop stmts and make sure they are all vectorizable. */
1264 vect_analyze_loop_operations (loop_vec_info loop_vinfo
, bool slp
)
1266 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1267 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1268 int nbbs
= loop
->num_nodes
;
1269 gimple_stmt_iterator si
;
1270 unsigned int vectorization_factor
= 0;
1273 stmt_vec_info stmt_info
;
1274 bool need_to_vectorize
= false;
1275 int min_profitable_iters
;
1276 int min_scalar_loop_bound
;
1278 bool only_slp_in_loop
= true, ok
;
1279 HOST_WIDE_INT max_niter
;
1280 HOST_WIDE_INT estimated_niter
;
1281 int min_profitable_estimate
;
1283 if (dump_enabled_p ())
1284 dump_printf_loc (MSG_NOTE
, vect_location
,
1285 "=== vect_analyze_loop_operations ===");
1287 gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo
));
1288 vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1291 /* If all the stmts in the loop can be SLPed, we perform only SLP, and
1292 vectorization factor of the loop is the unrolling factor required by
1293 the SLP instances. If that unrolling factor is 1, we say, that we
1294 perform pure SLP on loop - cross iteration parallelism is not
1296 for (i
= 0; i
< nbbs
; i
++)
1298 basic_block bb
= bbs
[i
];
1299 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1301 gimple stmt
= gsi_stmt (si
);
1302 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1303 gcc_assert (stmt_info
);
1304 if ((STMT_VINFO_RELEVANT_P (stmt_info
)
1305 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
1306 && !PURE_SLP_STMT (stmt_info
))
1307 /* STMT needs both SLP and loop-based vectorization. */
1308 only_slp_in_loop
= false;
1312 if (only_slp_in_loop
)
1313 vectorization_factor
= LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
);
1315 vectorization_factor
= least_common_multiple (vectorization_factor
,
1316 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
));
1318 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
1319 if (dump_enabled_p ())
1320 dump_printf_loc (MSG_NOTE
, vect_location
,
1321 "Updating vectorization factor to %d ",
1322 vectorization_factor
);
1325 for (i
= 0; i
< nbbs
; i
++)
1327 basic_block bb
= bbs
[i
];
1329 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
1331 phi
= gsi_stmt (si
);
1334 stmt_info
= vinfo_for_stmt (phi
);
1335 if (dump_enabled_p ())
1337 dump_printf_loc (MSG_NOTE
, vect_location
, "examining phi: ");
1338 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
1341 /* Inner-loop loop-closed exit phi in outer-loop vectorization
1342 (i.e., a phi in the tail of the outer-loop). */
1343 if (! is_loop_header_bb_p (bb
))
1345 /* FORNOW: we currently don't support the case that these phis
1346 are not used in the outerloop (unless it is double reduction,
1347 i.e., this phi is vect_reduction_def), cause this case
1348 requires to actually do something here. */
1349 if ((!STMT_VINFO_RELEVANT_P (stmt_info
)
1350 || STMT_VINFO_LIVE_P (stmt_info
))
1351 && STMT_VINFO_DEF_TYPE (stmt_info
)
1352 != vect_double_reduction_def
)
1354 if (dump_enabled_p ())
1355 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1356 "Unsupported loop-closed phi in "
1361 /* If PHI is used in the outer loop, we check that its operand
1362 is defined in the inner loop. */
1363 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1368 if (gimple_phi_num_args (phi
) != 1)
1371 phi_op
= PHI_ARG_DEF (phi
, 0);
1372 if (TREE_CODE (phi_op
) != SSA_NAME
)
1375 op_def_stmt
= SSA_NAME_DEF_STMT (phi_op
);
1377 || !flow_bb_inside_loop_p (loop
, gimple_bb (op_def_stmt
))
1378 || !vinfo_for_stmt (op_def_stmt
))
1381 if (STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1382 != vect_used_in_outer
1383 && STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1384 != vect_used_in_outer_by_reduction
)
1391 gcc_assert (stmt_info
);
1393 if (STMT_VINFO_LIVE_P (stmt_info
))
1395 /* FORNOW: not yet supported. */
1396 if (dump_enabled_p ())
1397 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1398 "not vectorized: value used after loop.");
1402 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
1403 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_induction_def
)
1405 /* A scalar-dependence cycle that we don't support. */
1406 if (dump_enabled_p ())
1407 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1408 "not vectorized: scalar dependence cycle.");
1412 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1414 need_to_vectorize
= true;
1415 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
1416 ok
= vectorizable_induction (phi
, NULL
, NULL
);
1421 if (dump_enabled_p ())
1423 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1424 "not vectorized: relevant phi not "
1426 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, phi
, 0);
1432 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1434 gimple stmt
= gsi_stmt (si
);
1435 if (!vect_analyze_stmt (stmt
, &need_to_vectorize
, NULL
))
1440 /* All operations in the loop are either irrelevant (deal with loop
1441 control, or dead), or only used outside the loop and can be moved
1442 out of the loop (e.g. invariants, inductions). The loop can be
1443 optimized away by scalar optimizations. We're better off not
1444 touching this loop. */
1445 if (!need_to_vectorize
)
1447 if (dump_enabled_p ())
1448 dump_printf_loc (MSG_NOTE
, vect_location
,
1449 "All the computation can be taken out of the loop.");
1450 if (dump_enabled_p ())
1451 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1452 "not vectorized: redundant loop. no profit to "
1457 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
) && dump_enabled_p ())
1458 dump_printf_loc (MSG_NOTE
, vect_location
,
1459 "vectorization_factor = %d, niters = "
1460 HOST_WIDE_INT_PRINT_DEC
, vectorization_factor
,
1461 LOOP_VINFO_INT_NITERS (loop_vinfo
));
1463 if ((LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1464 && (LOOP_VINFO_INT_NITERS (loop_vinfo
) < vectorization_factor
))
1465 || ((max_niter
= max_stmt_executions_int (loop
)) != -1
1466 && (unsigned HOST_WIDE_INT
) max_niter
< vectorization_factor
))
1468 if (dump_enabled_p ())
1469 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1470 "not vectorized: iteration count too small.");
1471 if (dump_enabled_p ())
1472 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1473 "not vectorized: iteration count smaller than "
1474 "vectorization factor.");
1478 /* Analyze cost. Decide if worth while to vectorize. */
1480 /* Once VF is set, SLP costs should be updated since the number of created
1481 vector stmts depends on VF. */
1482 vect_update_slp_costs_according_to_vf (loop_vinfo
);
1484 vect_estimate_min_profitable_iters (loop_vinfo
, &min_profitable_iters
,
1485 &min_profitable_estimate
);
1486 LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo
) = min_profitable_iters
;
1488 if (min_profitable_iters
< 0)
1490 if (dump_enabled_p ())
1491 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1492 "not vectorized: vectorization not profitable.");
1493 if (dump_enabled_p ())
1494 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1495 "not vectorized: vector version will never be "
1500 min_scalar_loop_bound
= ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND
)
1501 * vectorization_factor
) - 1);
1504 /* Use the cost model only if it is more conservative than user specified
1507 th
= (unsigned) min_scalar_loop_bound
;
1508 if (min_profitable_iters
1509 && (!min_scalar_loop_bound
1510 || min_profitable_iters
> min_scalar_loop_bound
))
1511 th
= (unsigned) min_profitable_iters
;
1513 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1514 && LOOP_VINFO_INT_NITERS (loop_vinfo
) <= th
)
1516 if (dump_enabled_p ())
1517 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1518 "not vectorized: vectorization not profitable.");
1519 if (dump_enabled_p ())
1520 dump_printf_loc (MSG_NOTE
, vect_location
,
1521 "not vectorized: iteration count smaller than user "
1522 "specified loop bound parameter or minimum profitable "
1523 "iterations (whichever is more conservative).");
1527 if ((estimated_niter
= estimated_stmt_executions_int (loop
)) != -1
1528 && ((unsigned HOST_WIDE_INT
) estimated_niter
1529 <= MAX (th
, (unsigned)min_profitable_estimate
)))
1531 if (dump_enabled_p ())
1532 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1533 "not vectorized: estimated iteration count too "
1535 if (dump_enabled_p ())
1536 dump_printf_loc (MSG_NOTE
, vect_location
,
1537 "not vectorized: estimated iteration count smaller "
1538 "than specified loop bound parameter or minimum "
1539 "profitable iterations (whichever is more "
1544 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1545 || LOOP_VINFO_INT_NITERS (loop_vinfo
) % vectorization_factor
!= 0
1546 || LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
))
1548 if (dump_enabled_p ())
1549 dump_printf_loc (MSG_NOTE
, vect_location
, "epilog loop required.");
1550 if (!vect_can_advance_ivs_p (loop_vinfo
))
1552 if (dump_enabled_p ())
1553 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1554 "not vectorized: can't create epilog loop 1.");
1557 if (!slpeel_can_duplicate_loop_p (loop
, single_exit (loop
)))
1559 if (dump_enabled_p ())
1560 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1561 "not vectorized: can't create epilog loop 2.");
1570 /* Function vect_analyze_loop_2.
1572 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1573 for it. The different analyses will record information in the
1574 loop_vec_info struct. */
1576 vect_analyze_loop_2 (loop_vec_info loop_vinfo
)
1578 bool ok
, slp
= false;
1579 int max_vf
= MAX_VECTORIZATION_FACTOR
;
1582 /* Find all data references in the loop (which correspond to vdefs/vuses)
1583 and analyze their evolution in the loop. Also adjust the minimal
1584 vectorization factor according to the loads and stores.
1586 FORNOW: Handle only simple, array references, which
1587 alignment can be forced, and aligned pointer-references. */
1589 ok
= vect_analyze_data_refs (loop_vinfo
, NULL
, &min_vf
);
1592 if (dump_enabled_p ())
1593 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1594 "bad data references.");
1598 /* Analyze the access patterns of the data-refs in the loop (consecutive,
1599 complex, etc.). FORNOW: Only handle consecutive access pattern. */
1601 ok
= vect_analyze_data_ref_accesses (loop_vinfo
, NULL
);
1604 if (dump_enabled_p ())
1605 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1606 "bad data access.");
1610 /* Classify all cross-iteration scalar data-flow cycles.
1611 Cross-iteration cycles caused by virtual phis are analyzed separately. */
1613 vect_analyze_scalar_cycles (loop_vinfo
);
1615 vect_pattern_recog (loop_vinfo
, NULL
);
1617 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
1619 ok
= vect_mark_stmts_to_be_vectorized (loop_vinfo
);
1622 if (dump_enabled_p ())
1623 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1624 "unexpected pattern.");
1628 /* Analyze data dependences between the data-refs in the loop
1629 and adjust the maximum vectorization factor according to
1631 FORNOW: fail at the first data dependence that we encounter. */
1633 ok
= vect_analyze_data_ref_dependences (loop_vinfo
, &max_vf
);
1637 if (dump_enabled_p ())
1638 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1639 "bad data dependence.");
1643 ok
= vect_determine_vectorization_factor (loop_vinfo
);
1646 if (dump_enabled_p ())
1647 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1648 "can't determine vectorization factor.");
1651 if (max_vf
< LOOP_VINFO_VECT_FACTOR (loop_vinfo
))
1653 if (dump_enabled_p ())
1654 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1655 "bad data dependence.");
1659 /* Analyze the alignment of the data-refs in the loop.
1660 Fail if a data reference is found that cannot be vectorized. */
1662 ok
= vect_analyze_data_refs_alignment (loop_vinfo
, NULL
);
1665 if (dump_enabled_p ())
1666 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1667 "bad data alignment.");
1671 /* Prune the list of ddrs to be tested at run-time by versioning for alias.
1672 It is important to call pruning after vect_analyze_data_ref_accesses,
1673 since we use grouping information gathered by interleaving analysis. */
1674 ok
= vect_prune_runtime_alias_test_list (loop_vinfo
);
1677 if (dump_enabled_p ())
1678 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1679 "too long list of versioning for alias "
1684 /* This pass will decide on using loop versioning and/or loop peeling in
1685 order to enhance the alignment of data references in the loop. */
1687 ok
= vect_enhance_data_refs_alignment (loop_vinfo
);
1690 if (dump_enabled_p ())
1691 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1692 "bad data alignment.");
1696 /* Check the SLP opportunities in the loop, analyze and build SLP trees. */
1697 ok
= vect_analyze_slp (loop_vinfo
, NULL
);
1700 /* Decide which possible SLP instances to SLP. */
1701 slp
= vect_make_slp_decision (loop_vinfo
);
1703 /* Find stmts that need to be both vectorized and SLPed. */
1704 vect_detect_hybrid_slp (loop_vinfo
);
1709 /* Scan all the operations in the loop and make sure they are
1712 ok
= vect_analyze_loop_operations (loop_vinfo
, slp
);
1715 if (dump_enabled_p ())
1716 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1717 "bad operation or unsupported loop bound.");
1724 /* Function vect_analyze_loop.
1726 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1727 for it. The different analyses will record information in the
1728 loop_vec_info struct. */
1730 vect_analyze_loop (struct loop
*loop
)
1732 loop_vec_info loop_vinfo
;
1733 unsigned int vector_sizes
;
1735 /* Autodetect first vector size we try. */
1736 current_vector_size
= 0;
1737 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
1739 if (dump_enabled_p ())
1740 dump_printf_loc (MSG_NOTE
, vect_location
,
1741 "===== analyze_loop_nest =====");
1743 if (loop_outer (loop
)
1744 && loop_vec_info_for_loop (loop_outer (loop
))
1745 && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop
))))
1747 if (dump_enabled_p ())
1748 dump_printf_loc (MSG_NOTE
, vect_location
,
1749 "outer-loop already vectorized.");
1755 /* Check the CFG characteristics of the loop (nesting, entry/exit). */
1756 loop_vinfo
= vect_analyze_loop_form (loop
);
1759 if (dump_enabled_p ())
1760 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1765 if (vect_analyze_loop_2 (loop_vinfo
))
1767 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
) = 1;
1772 destroy_loop_vec_info (loop_vinfo
, true);
1774 vector_sizes
&= ~current_vector_size
;
1775 if (vector_sizes
== 0
1776 || current_vector_size
== 0)
1779 /* Try the next biggest vector size. */
1780 current_vector_size
= 1 << floor_log2 (vector_sizes
);
1781 if (dump_enabled_p ())
1782 dump_printf_loc (MSG_NOTE
, vect_location
,
1783 "***** Re-trying analysis with "
1784 "vector size %d\n", current_vector_size
);
1789 /* Function reduction_code_for_scalar_code
1792 CODE - tree_code of a reduction operations.
1795 REDUC_CODE - the corresponding tree-code to be used to reduce the
1796 vector of partial results into a single scalar result (which
1797 will also reside in a vector) or ERROR_MARK if the operation is
1798 a supported reduction operation, but does not have such tree-code.
1800 Return FALSE if CODE currently cannot be vectorized as reduction. */
1803 reduction_code_for_scalar_code (enum tree_code code
,
1804 enum tree_code
*reduc_code
)
1809 *reduc_code
= REDUC_MAX_EXPR
;
1813 *reduc_code
= REDUC_MIN_EXPR
;
1817 *reduc_code
= REDUC_PLUS_EXPR
;
1825 *reduc_code
= ERROR_MARK
;
1834 /* Error reporting helper for vect_is_simple_reduction below. GIMPLE statement
1835 STMT is printed with a message MSG. */
1838 report_vect_op (int msg_type
, gimple stmt
, const char *msg
)
1840 dump_printf_loc (msg_type
, vect_location
, "%s", msg
);
1841 dump_gimple_stmt (msg_type
, TDF_SLIM
, stmt
, 0);
1845 /* Detect SLP reduction of the form:
1855 PHI is the reduction phi node (#a1 = phi <a5, a0> above)
1856 FIRST_STMT is the first reduction stmt in the chain
1857 (a2 = operation (a1)).
1859 Return TRUE if a reduction chain was detected. */
1862 vect_is_slp_reduction (loop_vec_info loop_info
, gimple phi
, gimple first_stmt
)
1864 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
1865 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
1866 enum tree_code code
;
1867 gimple current_stmt
= NULL
, loop_use_stmt
= NULL
, first
, next_stmt
;
1868 stmt_vec_info use_stmt_info
, current_stmt_info
;
1870 imm_use_iterator imm_iter
;
1871 use_operand_p use_p
;
1872 int nloop_uses
, size
= 0, n_out_of_loop_uses
;
1875 if (loop
!= vect_loop
)
1878 lhs
= PHI_RESULT (phi
);
1879 code
= gimple_assign_rhs_code (first_stmt
);
1883 n_out_of_loop_uses
= 0;
1884 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
1886 gimple use_stmt
= USE_STMT (use_p
);
1887 if (is_gimple_debug (use_stmt
))
1890 use_stmt
= USE_STMT (use_p
);
1892 /* Check if we got back to the reduction phi. */
1893 if (use_stmt
== phi
)
1895 loop_use_stmt
= use_stmt
;
1900 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
1902 if (vinfo_for_stmt (use_stmt
)
1903 && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (use_stmt
)))
1905 loop_use_stmt
= use_stmt
;
1910 n_out_of_loop_uses
++;
1912 /* There are can be either a single use in the loop or two uses in
1914 if (nloop_uses
> 1 || (n_out_of_loop_uses
&& nloop_uses
))
1921 /* We reached a statement with no loop uses. */
1922 if (nloop_uses
== 0)
1925 /* This is a loop exit phi, and we haven't reached the reduction phi. */
1926 if (gimple_code (loop_use_stmt
) == GIMPLE_PHI
)
1929 if (!is_gimple_assign (loop_use_stmt
)
1930 || code
!= gimple_assign_rhs_code (loop_use_stmt
)
1931 || !flow_bb_inside_loop_p (loop
, gimple_bb (loop_use_stmt
)))
1934 /* Insert USE_STMT into reduction chain. */
1935 use_stmt_info
= vinfo_for_stmt (loop_use_stmt
);
1938 current_stmt_info
= vinfo_for_stmt (current_stmt
);
1939 GROUP_NEXT_ELEMENT (current_stmt_info
) = loop_use_stmt
;
1940 GROUP_FIRST_ELEMENT (use_stmt_info
)
1941 = GROUP_FIRST_ELEMENT (current_stmt_info
);
1944 GROUP_FIRST_ELEMENT (use_stmt_info
) = loop_use_stmt
;
1946 lhs
= gimple_assign_lhs (loop_use_stmt
);
1947 current_stmt
= loop_use_stmt
;
1951 if (!found
|| loop_use_stmt
!= phi
|| size
< 2)
1954 /* Swap the operands, if needed, to make the reduction operand be the second
1956 lhs
= PHI_RESULT (phi
);
1957 next_stmt
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
1960 if (gimple_assign_rhs2 (next_stmt
) == lhs
)
1962 tree op
= gimple_assign_rhs1 (next_stmt
);
1963 gimple def_stmt
= NULL
;
1965 if (TREE_CODE (op
) == SSA_NAME
)
1966 def_stmt
= SSA_NAME_DEF_STMT (op
);
1968 /* Check that the other def is either defined in the loop
1969 ("vect_internal_def"), or it's an induction (defined by a
1970 loop-header phi-node). */
1972 && gimple_bb (def_stmt
)
1973 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
1974 && (is_gimple_assign (def_stmt
)
1975 || is_gimple_call (def_stmt
)
1976 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
1977 == vect_induction_def
1978 || (gimple_code (def_stmt
) == GIMPLE_PHI
1979 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
1980 == vect_internal_def
1981 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
1983 lhs
= gimple_assign_lhs (next_stmt
);
1984 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
1992 tree op
= gimple_assign_rhs2 (next_stmt
);
1993 gimple def_stmt
= NULL
;
1995 if (TREE_CODE (op
) == SSA_NAME
)
1996 def_stmt
= SSA_NAME_DEF_STMT (op
);
1998 /* Check that the other def is either defined in the loop
1999 ("vect_internal_def"), or it's an induction (defined by a
2000 loop-header phi-node). */
2002 && gimple_bb (def_stmt
)
2003 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2004 && (is_gimple_assign (def_stmt
)
2005 || is_gimple_call (def_stmt
)
2006 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2007 == vect_induction_def
2008 || (gimple_code (def_stmt
) == GIMPLE_PHI
2009 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2010 == vect_internal_def
2011 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
2013 if (dump_enabled_p ())
2015 dump_printf_loc (MSG_NOTE
, vect_location
, "swapping oprnds: ");
2016 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, next_stmt
, 0);
2019 swap_tree_operands (next_stmt
,
2020 gimple_assign_rhs1_ptr (next_stmt
),
2021 gimple_assign_rhs2_ptr (next_stmt
));
2022 update_stmt (next_stmt
);
2024 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (next_stmt
)))
2025 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
2031 lhs
= gimple_assign_lhs (next_stmt
);
2032 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
2035 /* Save the chain for further analysis in SLP detection. */
2036 first
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
2037 LOOP_VINFO_REDUCTION_CHAINS (loop_info
).safe_push (first
);
2038 GROUP_SIZE (vinfo_for_stmt (first
)) = size
;
2044 /* Function vect_is_simple_reduction_1
2046 (1) Detect a cross-iteration def-use cycle that represents a simple
2047 reduction computation. We look for the following pattern:
2052 a2 = operation (a3, a1)
2055 1. operation is commutative and associative and it is safe to
2056 change the order of the computation (if CHECK_REDUCTION is true)
2057 2. no uses for a2 in the loop (a2 is used out of the loop)
2058 3. no uses of a1 in the loop besides the reduction operation
2059 4. no uses of a1 outside the loop.
2061 Conditions 1,4 are tested here.
2062 Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
2064 (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
2065 nested cycles, if CHECK_REDUCTION is false.
2067 (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
2071 inner loop (def of a3)
2074 If MODIFY is true it tries also to rework the code in-place to enable
2075 detection of more reduction patterns. For the time being we rewrite
2076 "res -= RHS" into "rhs += -RHS" when it seems worthwhile.
2080 vect_is_simple_reduction_1 (loop_vec_info loop_info
, gimple phi
,
2081 bool check_reduction
, bool *double_reduc
,
2084 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
2085 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
2086 edge latch_e
= loop_latch_edge (loop
);
2087 tree loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
2088 gimple def_stmt
, def1
= NULL
, def2
= NULL
;
2089 enum tree_code orig_code
, code
;
2090 tree op1
, op2
, op3
= NULL_TREE
, op4
= NULL_TREE
;
2094 imm_use_iterator imm_iter
;
2095 use_operand_p use_p
;
2098 *double_reduc
= false;
2100 /* If CHECK_REDUCTION is true, we assume inner-most loop vectorization,
2101 otherwise, we assume outer loop vectorization. */
2102 gcc_assert ((check_reduction
&& loop
== vect_loop
)
2103 || (!check_reduction
&& flow_loop_nested_p (vect_loop
, loop
)));
2105 name
= PHI_RESULT (phi
);
2107 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2109 gimple use_stmt
= USE_STMT (use_p
);
2110 if (is_gimple_debug (use_stmt
))
2113 if (!flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2115 if (dump_enabled_p ())
2116 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2117 "intermediate value used outside loop.");
2122 if (vinfo_for_stmt (use_stmt
)
2123 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt
)))
2127 if (dump_enabled_p ())
2128 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2129 "reduction used in loop.");
2134 if (TREE_CODE (loop_arg
) != SSA_NAME
)
2136 if (dump_enabled_p ())
2138 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2139 "reduction: not ssa_name: ");
2140 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, loop_arg
);
2145 def_stmt
= SSA_NAME_DEF_STMT (loop_arg
);
2148 if (dump_enabled_p ())
2149 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2150 "reduction: no def_stmt.");
2154 if (!is_gimple_assign (def_stmt
) && gimple_code (def_stmt
) != GIMPLE_PHI
)
2156 if (dump_enabled_p ())
2157 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, def_stmt
, 0);
2161 if (is_gimple_assign (def_stmt
))
2163 name
= gimple_assign_lhs (def_stmt
);
2168 name
= PHI_RESULT (def_stmt
);
2173 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2175 gimple use_stmt
= USE_STMT (use_p
);
2176 if (is_gimple_debug (use_stmt
))
2178 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
))
2179 && vinfo_for_stmt (use_stmt
)
2180 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt
)))
2184 if (dump_enabled_p ())
2185 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2186 "reduction used in loop.");
2191 /* If DEF_STMT is a phi node itself, we expect it to have a single argument
2192 defined in the inner loop. */
2195 op1
= PHI_ARG_DEF (def_stmt
, 0);
2197 if (gimple_phi_num_args (def_stmt
) != 1
2198 || TREE_CODE (op1
) != SSA_NAME
)
2200 if (dump_enabled_p ())
2201 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2202 "unsupported phi node definition.");
2207 def1
= SSA_NAME_DEF_STMT (op1
);
2208 if (flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2210 && flow_bb_inside_loop_p (loop
->inner
, gimple_bb (def1
))
2211 && is_gimple_assign (def1
))
2213 if (dump_enabled_p ())
2214 report_vect_op (MSG_NOTE
, def_stmt
,
2215 "detected double reduction: ");
2217 *double_reduc
= true;
2224 code
= orig_code
= gimple_assign_rhs_code (def_stmt
);
2226 /* We can handle "res -= x[i]", which is non-associative by
2227 simply rewriting this into "res += -x[i]". Avoid changing
2228 gimple instruction for the first simple tests and only do this
2229 if we're allowed to change code at all. */
2230 if (code
== MINUS_EXPR
2232 && (op1
= gimple_assign_rhs1 (def_stmt
))
2233 && TREE_CODE (op1
) == SSA_NAME
2234 && SSA_NAME_DEF_STMT (op1
) == phi
)
2238 && (!commutative_tree_code (code
) || !associative_tree_code (code
)))
2240 if (dump_enabled_p ())
2241 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2242 "reduction: not commutative/associative: ");
2246 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
2248 if (code
!= COND_EXPR
)
2250 if (dump_enabled_p ())
2251 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2252 "reduction: not binary operation: ");
2257 op3
= gimple_assign_rhs1 (def_stmt
);
2258 if (COMPARISON_CLASS_P (op3
))
2260 op4
= TREE_OPERAND (op3
, 1);
2261 op3
= TREE_OPERAND (op3
, 0);
2264 op1
= gimple_assign_rhs2 (def_stmt
);
2265 op2
= gimple_assign_rhs3 (def_stmt
);
2267 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2269 if (dump_enabled_p ())
2270 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2271 "reduction: uses not ssa_names: ");
2278 op1
= gimple_assign_rhs1 (def_stmt
);
2279 op2
= gimple_assign_rhs2 (def_stmt
);
2281 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2283 if (dump_enabled_p ())
2284 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2285 "reduction: uses not ssa_names: ");
2291 type
= TREE_TYPE (gimple_assign_lhs (def_stmt
));
2292 if ((TREE_CODE (op1
) == SSA_NAME
2293 && !types_compatible_p (type
,TREE_TYPE (op1
)))
2294 || (TREE_CODE (op2
) == SSA_NAME
2295 && !types_compatible_p (type
, TREE_TYPE (op2
)))
2296 || (op3
&& TREE_CODE (op3
) == SSA_NAME
2297 && !types_compatible_p (type
, TREE_TYPE (op3
)))
2298 || (op4
&& TREE_CODE (op4
) == SSA_NAME
2299 && !types_compatible_p (type
, TREE_TYPE (op4
))))
2301 if (dump_enabled_p ())
2303 dump_printf_loc (MSG_NOTE
, vect_location
,
2304 "reduction: multiple types: operation type: ");
2305 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, type
);
2306 dump_printf (MSG_NOTE
, ", operands types: ");
2307 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2309 dump_printf (MSG_NOTE
, ",");
2310 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2314 dump_printf (MSG_NOTE
, ",");
2315 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2321 dump_printf (MSG_NOTE
, ",");
2322 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2330 /* Check that it's ok to change the order of the computation.
2331 Generally, when vectorizing a reduction we change the order of the
2332 computation. This may change the behavior of the program in some
2333 cases, so we need to check that this is ok. One exception is when
2334 vectorizing an outer-loop: the inner-loop is executed sequentially,
2335 and therefore vectorizing reductions in the inner-loop during
2336 outer-loop vectorization is safe. */
2338 /* CHECKME: check for !flag_finite_math_only too? */
2339 if (SCALAR_FLOAT_TYPE_P (type
) && !flag_associative_math
2342 /* Changing the order of operations changes the semantics. */
2343 if (dump_enabled_p ())
2344 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2345 "reduction: unsafe fp math optimization: ");
2348 else if (INTEGRAL_TYPE_P (type
) && TYPE_OVERFLOW_TRAPS (type
)
2351 /* Changing the order of operations changes the semantics. */
2352 if (dump_enabled_p ())
2353 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2354 "reduction: unsafe int math optimization: ");
2357 else if (SAT_FIXED_POINT_TYPE_P (type
) && check_reduction
)
2359 /* Changing the order of operations changes the semantics. */
2360 if (dump_enabled_p ())
2361 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2362 "reduction: unsafe fixed-point math optimization: ");
2366 /* If we detected "res -= x[i]" earlier, rewrite it into
2367 "res += -x[i]" now. If this turns out to be useless reassoc
2368 will clean it up again. */
2369 if (orig_code
== MINUS_EXPR
)
2371 tree rhs
= gimple_assign_rhs2 (def_stmt
);
2372 tree negrhs
= make_ssa_name (TREE_TYPE (rhs
), NULL
);
2373 gimple negate_stmt
= gimple_build_assign_with_ops (NEGATE_EXPR
, negrhs
,
2375 gimple_stmt_iterator gsi
= gsi_for_stmt (def_stmt
);
2376 set_vinfo_for_stmt (negate_stmt
, new_stmt_vec_info (negate_stmt
,
2378 gsi_insert_before (&gsi
, negate_stmt
, GSI_NEW_STMT
);
2379 gimple_assign_set_rhs2 (def_stmt
, negrhs
);
2380 gimple_assign_set_rhs_code (def_stmt
, PLUS_EXPR
);
2381 update_stmt (def_stmt
);
2384 /* Reduction is safe. We're dealing with one of the following:
2385 1) integer arithmetic and no trapv
2386 2) floating point arithmetic, and special flags permit this optimization
2387 3) nested cycle (i.e., outer loop vectorization). */
2388 if (TREE_CODE (op1
) == SSA_NAME
)
2389 def1
= SSA_NAME_DEF_STMT (op1
);
2391 if (TREE_CODE (op2
) == SSA_NAME
)
2392 def2
= SSA_NAME_DEF_STMT (op2
);
2394 if (code
!= COND_EXPR
2395 && ((!def1
|| gimple_nop_p (def1
)) && (!def2
|| gimple_nop_p (def2
))))
2397 if (dump_enabled_p ())
2398 report_vect_op (MSG_NOTE
, def_stmt
, "reduction: no defs for operands: ");
2402 /* Check that one def is the reduction def, defined by PHI,
2403 the other def is either defined in the loop ("vect_internal_def"),
2404 or it's an induction (defined by a loop-header phi-node). */
2406 if (def2
&& def2
== phi
2407 && (code
== COND_EXPR
2408 || !def1
|| gimple_nop_p (def1
)
2409 || (def1
&& flow_bb_inside_loop_p (loop
, gimple_bb (def1
))
2410 && (is_gimple_assign (def1
)
2411 || is_gimple_call (def1
)
2412 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
2413 == vect_induction_def
2414 || (gimple_code (def1
) == GIMPLE_PHI
2415 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
2416 == vect_internal_def
2417 && !is_loop_header_bb_p (gimple_bb (def1
)))))))
2419 if (dump_enabled_p ())
2420 report_vect_op (MSG_NOTE
, def_stmt
, "detected reduction: ");
2424 if (def1
&& def1
== phi
2425 && (code
== COND_EXPR
2426 || !def2
|| gimple_nop_p (def2
)
2427 || (def2
&& flow_bb_inside_loop_p (loop
, gimple_bb (def2
))
2428 && (is_gimple_assign (def2
)
2429 || is_gimple_call (def2
)
2430 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
2431 == vect_induction_def
2432 || (gimple_code (def2
) == GIMPLE_PHI
2433 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
2434 == vect_internal_def
2435 && !is_loop_header_bb_p (gimple_bb (def2
)))))))
2437 if (check_reduction
)
2439 /* Swap operands (just for simplicity - so that the rest of the code
2440 can assume that the reduction variable is always the last (second)
2442 if (dump_enabled_p ())
2443 report_vect_op (MSG_NOTE
, def_stmt
,
2444 "detected reduction: need to swap operands: ");
2446 swap_tree_operands (def_stmt
, gimple_assign_rhs1_ptr (def_stmt
),
2447 gimple_assign_rhs2_ptr (def_stmt
));
2449 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (def_stmt
)))
2450 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
2454 if (dump_enabled_p ())
2455 report_vect_op (MSG_NOTE
, def_stmt
, "detected reduction: ");
2461 /* Try to find SLP reduction chain. */
2462 if (check_reduction
&& vect_is_slp_reduction (loop_info
, phi
, def_stmt
))
2464 if (dump_enabled_p ())
2465 report_vect_op (MSG_NOTE
, def_stmt
,
2466 "reduction: detected reduction chain: ");
2471 if (dump_enabled_p ())
2472 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2473 "reduction: unknown pattern: ");
2478 /* Wrapper around vect_is_simple_reduction_1, that won't modify code
2479 in-place. Arguments as there. */
2482 vect_is_simple_reduction (loop_vec_info loop_info
, gimple phi
,
2483 bool check_reduction
, bool *double_reduc
)
2485 return vect_is_simple_reduction_1 (loop_info
, phi
, check_reduction
,
2486 double_reduc
, false);
2489 /* Wrapper around vect_is_simple_reduction_1, which will modify code
2490 in-place if it enables detection of more reductions. Arguments
2494 vect_force_simple_reduction (loop_vec_info loop_info
, gimple phi
,
2495 bool check_reduction
, bool *double_reduc
)
2497 return vect_is_simple_reduction_1 (loop_info
, phi
, check_reduction
,
2498 double_reduc
, true);
2501 /* Calculate the cost of one scalar iteration of the loop. */
2503 vect_get_single_scalar_iteration_cost (loop_vec_info loop_vinfo
)
2505 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2506 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
2507 int nbbs
= loop
->num_nodes
, factor
, scalar_single_iter_cost
= 0;
2508 int innerloop_iters
, i
, stmt_cost
;
2510 /* Count statements in scalar loop. Using this as scalar cost for a single
2513 TODO: Add outer loop support.
2515 TODO: Consider assigning different costs to different scalar
2519 innerloop_iters
= 1;
2521 innerloop_iters
= 50; /* FIXME */
2523 for (i
= 0; i
< nbbs
; i
++)
2525 gimple_stmt_iterator si
;
2526 basic_block bb
= bbs
[i
];
2528 if (bb
->loop_father
== loop
->inner
)
2529 factor
= innerloop_iters
;
2533 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
2535 gimple stmt
= gsi_stmt (si
);
2536 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2538 if (!is_gimple_assign (stmt
) && !is_gimple_call (stmt
))
2541 /* Skip stmts that are not vectorized inside the loop. */
2543 && !STMT_VINFO_RELEVANT_P (stmt_info
)
2544 && (!STMT_VINFO_LIVE_P (stmt_info
)
2545 || !VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
2546 && !STMT_VINFO_IN_PATTERN_P (stmt_info
))
2549 if (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
)))
2551 if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))))
2552 stmt_cost
= vect_get_stmt_cost (scalar_load
);
2554 stmt_cost
= vect_get_stmt_cost (scalar_store
);
2557 stmt_cost
= vect_get_stmt_cost (scalar_stmt
);
2559 scalar_single_iter_cost
+= stmt_cost
* factor
;
2562 return scalar_single_iter_cost
;
2565 /* Calculate cost of peeling the loop PEEL_ITERS_PROLOGUE times. */
2567 vect_get_known_peeling_cost (loop_vec_info loop_vinfo
, int peel_iters_prologue
,
2568 int *peel_iters_epilogue
,
2569 int scalar_single_iter_cost
,
2570 stmt_vector_for_cost
*prologue_cost_vec
,
2571 stmt_vector_for_cost
*epilogue_cost_vec
)
2574 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2576 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
2578 *peel_iters_epilogue
= vf
/2;
2579 if (dump_enabled_p ())
2580 dump_printf_loc (MSG_NOTE
, vect_location
,
2581 "cost model: epilogue peel iters set to vf/2 "
2582 "because loop iterations are unknown .");
2584 /* If peeled iterations are known but number of scalar loop
2585 iterations are unknown, count a taken branch per peeled loop. */
2586 retval
= record_stmt_cost (prologue_cost_vec
, 2, cond_branch_taken
,
2587 NULL
, 0, vect_prologue
);
2591 int niters
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
2592 peel_iters_prologue
= niters
< peel_iters_prologue
?
2593 niters
: peel_iters_prologue
;
2594 *peel_iters_epilogue
= (niters
- peel_iters_prologue
) % vf
;
2595 /* If we need to peel for gaps, but no peeling is required, we have to
2596 peel VF iterations. */
2597 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) && !*peel_iters_epilogue
)
2598 *peel_iters_epilogue
= vf
;
2601 if (peel_iters_prologue
)
2602 retval
+= record_stmt_cost (prologue_cost_vec
,
2603 peel_iters_prologue
* scalar_single_iter_cost
,
2604 scalar_stmt
, NULL
, 0, vect_prologue
);
2605 if (*peel_iters_epilogue
)
2606 retval
+= record_stmt_cost (epilogue_cost_vec
,
2607 *peel_iters_epilogue
* scalar_single_iter_cost
,
2608 scalar_stmt
, NULL
, 0, vect_epilogue
);
2612 /* Function vect_estimate_min_profitable_iters
2614 Return the number of iterations required for the vector version of the
2615 loop to be profitable relative to the cost of the scalar version of the
2619 vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo
,
2620 int *ret_min_profitable_niters
,
2621 int *ret_min_profitable_estimate
)
2623 int min_profitable_iters
;
2624 int min_profitable_estimate
;
2625 int peel_iters_prologue
;
2626 int peel_iters_epilogue
;
2627 unsigned vec_inside_cost
= 0;
2628 int vec_outside_cost
= 0;
2629 unsigned vec_prologue_cost
= 0;
2630 unsigned vec_epilogue_cost
= 0;
2631 int scalar_single_iter_cost
= 0;
2632 int scalar_outside_cost
= 0;
2633 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2634 int npeel
= LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
);
2635 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2637 /* Cost model disabled. */
2638 if (!flag_vect_cost_model
)
2640 dump_printf_loc (MSG_NOTE
, vect_location
, "cost model disabled.");
2641 *ret_min_profitable_niters
= 0;
2642 *ret_min_profitable_estimate
= 0;
2646 /* Requires loop versioning tests to handle misalignment. */
2647 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
))
2649 /* FIXME: Make cost depend on complexity of individual check. */
2650 unsigned len
= LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).length ();
2651 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
2653 dump_printf (MSG_NOTE
,
2654 "cost model: Adding cost of checks for loop "
2655 "versioning to treat misalignment.\n");
2658 /* Requires loop versioning with alias checks. */
2659 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2661 /* FIXME: Make cost depend on complexity of individual check. */
2662 unsigned len
= LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
).length ();
2663 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
2665 dump_printf (MSG_NOTE
,
2666 "cost model: Adding cost of checks for loop "
2667 "versioning aliasing.\n");
2670 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2671 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2672 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_taken
, NULL
, 0,
2675 /* Count statements in scalar loop. Using this as scalar cost for a single
2678 TODO: Add outer loop support.
2680 TODO: Consider assigning different costs to different scalar
2683 scalar_single_iter_cost
= vect_get_single_scalar_iteration_cost (loop_vinfo
);
2685 /* Add additional cost for the peeled instructions in prologue and epilogue
2688 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
2689 at compile-time - we assume it's vf/2 (the worst would be vf-1).
2691 TODO: Build an expression that represents peel_iters for prologue and
2692 epilogue to be used in a run-time test. */
2696 peel_iters_prologue
= vf
/2;
2697 dump_printf (MSG_NOTE
, "cost model: "
2698 "prologue peel iters set to vf/2.");
2700 /* If peeling for alignment is unknown, loop bound of main loop becomes
2702 peel_iters_epilogue
= vf
/2;
2703 dump_printf (MSG_NOTE
, "cost model: "
2704 "epilogue peel iters set to vf/2 because "
2705 "peeling for alignment is unknown.");
2707 /* If peeled iterations are unknown, count a taken branch and a not taken
2708 branch per peeled loop. Even if scalar loop iterations are known,
2709 vector iterations are not known since peeled prologue iterations are
2710 not known. Hence guards remain the same. */
2711 (void) add_stmt_cost (target_cost_data
, 2, cond_branch_taken
,
2712 NULL
, 0, vect_prologue
);
2713 (void) add_stmt_cost (target_cost_data
, 2, cond_branch_not_taken
,
2714 NULL
, 0, vect_prologue
);
2715 /* FORNOW: Don't attempt to pass individual scalar instructions to
2716 the model; just assume linear cost for scalar iterations. */
2717 (void) add_stmt_cost (target_cost_data
,
2718 peel_iters_prologue
* scalar_single_iter_cost
,
2719 scalar_stmt
, NULL
, 0, vect_prologue
);
2720 (void) add_stmt_cost (target_cost_data
,
2721 peel_iters_epilogue
* scalar_single_iter_cost
,
2722 scalar_stmt
, NULL
, 0, vect_epilogue
);
2726 stmt_vector_for_cost prologue_cost_vec
, epilogue_cost_vec
;
2727 stmt_info_for_cost
*si
;
2729 void *data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2731 prologue_cost_vec
.create (2);
2732 epilogue_cost_vec
.create (2);
2733 peel_iters_prologue
= npeel
;
2735 (void) vect_get_known_peeling_cost (loop_vinfo
, peel_iters_prologue
,
2736 &peel_iters_epilogue
,
2737 scalar_single_iter_cost
,
2739 &epilogue_cost_vec
);
2741 FOR_EACH_VEC_ELT (prologue_cost_vec
, j
, si
)
2743 struct _stmt_vec_info
*stmt_info
2744 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
2745 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
2746 si
->misalign
, vect_prologue
);
2749 FOR_EACH_VEC_ELT (epilogue_cost_vec
, j
, si
)
2751 struct _stmt_vec_info
*stmt_info
2752 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
2753 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
2754 si
->misalign
, vect_epilogue
);
2757 prologue_cost_vec
.release ();
2758 epilogue_cost_vec
.release ();
2761 /* FORNOW: The scalar outside cost is incremented in one of the
2764 1. The vectorizer checks for alignment and aliasing and generates
2765 a condition that allows dynamic vectorization. A cost model
2766 check is ANDED with the versioning condition. Hence scalar code
2767 path now has the added cost of the versioning check.
2769 if (cost > th & versioning_check)
2772 Hence run-time scalar is incremented by not-taken branch cost.
2774 2. The vectorizer then checks if a prologue is required. If the
2775 cost model check was not done before during versioning, it has to
2776 be done before the prologue check.
2779 prologue = scalar_iters
2784 if (prologue == num_iters)
2787 Hence the run-time scalar cost is incremented by a taken branch,
2788 plus a not-taken branch, plus a taken branch cost.
2790 3. The vectorizer then checks if an epilogue is required. If the
2791 cost model check was not done before during prologue check, it
2792 has to be done with the epilogue check.
2798 if (prologue == num_iters)
2801 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
2804 Hence the run-time scalar cost should be incremented by 2 taken
2807 TODO: The back end may reorder the BBS's differently and reverse
2808 conditions/branch directions. Change the estimates below to
2809 something more reasonable. */
2811 /* If the number of iterations is known and we do not do versioning, we can
2812 decide whether to vectorize at compile time. Hence the scalar version
2813 do not carry cost model guard costs. */
2814 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
2815 || LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2816 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2818 /* Cost model check occurs at versioning. */
2819 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2820 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2821 scalar_outside_cost
+= vect_get_stmt_cost (cond_branch_not_taken
);
2824 /* Cost model check occurs at prologue generation. */
2825 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
) < 0)
2826 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
)
2827 + vect_get_stmt_cost (cond_branch_not_taken
);
2828 /* Cost model check occurs at epilogue generation. */
2830 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
);
2834 /* Complete the target-specific cost calculations. */
2835 finish_cost (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
), &vec_prologue_cost
,
2836 &vec_inside_cost
, &vec_epilogue_cost
);
2838 vec_outside_cost
= (int)(vec_prologue_cost
+ vec_epilogue_cost
);
2840 /* Calculate number of iterations required to make the vector version
2841 profitable, relative to the loop bodies only. The following condition
2843 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
2845 SIC = scalar iteration cost, VIC = vector iteration cost,
2846 VOC = vector outside cost, VF = vectorization factor,
2847 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
2848 SOC = scalar outside cost for run time cost model check. */
2850 if ((scalar_single_iter_cost
* vf
) > (int) vec_inside_cost
)
2852 if (vec_outside_cost
<= 0)
2853 min_profitable_iters
= 1;
2856 min_profitable_iters
= ((vec_outside_cost
- scalar_outside_cost
) * vf
2857 - vec_inside_cost
* peel_iters_prologue
2858 - vec_inside_cost
* peel_iters_epilogue
)
2859 / ((scalar_single_iter_cost
* vf
)
2862 if ((scalar_single_iter_cost
* vf
* min_profitable_iters
)
2863 <= (((int) vec_inside_cost
* min_profitable_iters
)
2864 + (((int) vec_outside_cost
- scalar_outside_cost
) * vf
)))
2865 min_profitable_iters
++;
2868 /* vector version will never be profitable. */
2871 if (dump_enabled_p ())
2872 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2873 "cost model: the vector iteration cost = %d "
2874 "divided by the scalar iteration cost = %d "
2875 "is greater or equal to the vectorization factor = %d.",
2876 vec_inside_cost
, scalar_single_iter_cost
, vf
);
2877 *ret_min_profitable_niters
= -1;
2878 *ret_min_profitable_estimate
= -1;
2882 if (dump_enabled_p ())
2884 dump_printf_loc (MSG_NOTE
, vect_location
, "Cost model analysis: \n");
2885 dump_printf (MSG_NOTE
, " Vector inside of loop cost: %d\n",
2887 dump_printf (MSG_NOTE
, " Vector prologue cost: %d\n",
2889 dump_printf (MSG_NOTE
, " Vector epilogue cost: %d\n",
2891 dump_printf (MSG_NOTE
, " Scalar iteration cost: %d\n",
2892 scalar_single_iter_cost
);
2893 dump_printf (MSG_NOTE
, " Scalar outside cost: %d\n",
2894 scalar_outside_cost
);
2895 dump_printf (MSG_NOTE
, " Vector outside cost: %d\n",
2897 dump_printf (MSG_NOTE
, " prologue iterations: %d\n",
2898 peel_iters_prologue
);
2899 dump_printf (MSG_NOTE
, " epilogue iterations: %d\n",
2900 peel_iters_epilogue
);
2901 dump_printf (MSG_NOTE
,
2902 " Calculated minimum iters for profitability: %d\n",
2903 min_profitable_iters
);
2906 min_profitable_iters
=
2907 min_profitable_iters
< vf
? vf
: min_profitable_iters
;
2909 /* Because the condition we create is:
2910 if (niters <= min_profitable_iters)
2911 then skip the vectorized loop. */
2912 min_profitable_iters
--;
2914 if (dump_enabled_p ())
2915 dump_printf_loc (MSG_NOTE
, vect_location
,
2916 " Runtime profitability threshold = %d\n", min_profitable_iters
);
2918 *ret_min_profitable_niters
= min_profitable_iters
;
2920 /* Calculate number of iterations required to make the vector version
2921 profitable, relative to the loop bodies only.
2923 Non-vectorized variant is SIC * niters and it must win over vector
2924 variant on the expected loop trip count. The following condition must hold true:
2925 SIC * niters > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC + SOC */
2927 if (vec_outside_cost
<= 0)
2928 min_profitable_estimate
= 1;
2931 min_profitable_estimate
= ((vec_outside_cost
+ scalar_outside_cost
) * vf
2932 - vec_inside_cost
* peel_iters_prologue
2933 - vec_inside_cost
* peel_iters_epilogue
)
2934 / ((scalar_single_iter_cost
* vf
)
2937 min_profitable_estimate
--;
2938 min_profitable_estimate
= MAX (min_profitable_estimate
, min_profitable_iters
);
2939 if (dump_enabled_p ())
2940 dump_printf_loc (MSG_NOTE
, vect_location
,
2941 " Static estimate profitability threshold = %d\n",
2942 min_profitable_iters
);
2944 *ret_min_profitable_estimate
= min_profitable_estimate
;
2948 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
2949 functions. Design better to avoid maintenance issues. */
2951 /* Function vect_model_reduction_cost.
2953 Models cost for a reduction operation, including the vector ops
2954 generated within the strip-mine loop, the initial definition before
2955 the loop, and the epilogue code that must be generated. */
2958 vect_model_reduction_cost (stmt_vec_info stmt_info
, enum tree_code reduc_code
,
2961 int prologue_cost
= 0, epilogue_cost
= 0;
2962 enum tree_code code
;
2965 gimple stmt
, orig_stmt
;
2967 enum machine_mode mode
;
2968 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
2969 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2970 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2972 /* Cost of reduction op inside loop. */
2973 unsigned inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
2974 stmt_info
, 0, vect_body
);
2975 stmt
= STMT_VINFO_STMT (stmt_info
);
2977 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
2979 case GIMPLE_SINGLE_RHS
:
2980 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
)) == ternary_op
);
2981 reduction_op
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
2983 case GIMPLE_UNARY_RHS
:
2984 reduction_op
= gimple_assign_rhs1 (stmt
);
2986 case GIMPLE_BINARY_RHS
:
2987 reduction_op
= gimple_assign_rhs2 (stmt
);
2989 case GIMPLE_TERNARY_RHS
:
2990 reduction_op
= gimple_assign_rhs3 (stmt
);
2996 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
2999 if (dump_enabled_p ())
3001 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3002 "unsupported data-type ");
3003 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
3004 TREE_TYPE (reduction_op
));
3009 mode
= TYPE_MODE (vectype
);
3010 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
3013 orig_stmt
= STMT_VINFO_STMT (stmt_info
);
3015 code
= gimple_assign_rhs_code (orig_stmt
);
3017 /* Add in cost for initial definition. */
3018 prologue_cost
+= add_stmt_cost (target_cost_data
, 1, scalar_to_vec
,
3019 stmt_info
, 0, vect_prologue
);
3021 /* Determine cost of epilogue code.
3023 We have a reduction operator that will reduce the vector in one statement.
3024 Also requires scalar extract. */
3026 if (!nested_in_vect_loop_p (loop
, orig_stmt
))
3028 if (reduc_code
!= ERROR_MARK
)
3030 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1, vector_stmt
,
3031 stmt_info
, 0, vect_epilogue
);
3032 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1, vec_to_scalar
,
3033 stmt_info
, 0, vect_epilogue
);
3037 int vec_size_in_bits
= tree_low_cst (TYPE_SIZE (vectype
), 1);
3039 TYPE_SIZE (TREE_TYPE (gimple_assign_lhs (orig_stmt
)));
3040 int element_bitsize
= tree_low_cst (bitsize
, 1);
3041 int nelements
= vec_size_in_bits
/ element_bitsize
;
3043 optab
= optab_for_tree_code (code
, vectype
, optab_default
);
3045 /* We have a whole vector shift available. */
3046 if (VECTOR_MODE_P (mode
)
3047 && optab_handler (optab
, mode
) != CODE_FOR_nothing
3048 && optab_handler (vec_shr_optab
, mode
) != CODE_FOR_nothing
)
3050 /* Final reduction via vector shifts and the reduction operator.
3051 Also requires scalar extract. */
3052 epilogue_cost
+= add_stmt_cost (target_cost_data
,
3053 exact_log2 (nelements
) * 2,
3054 vector_stmt
, stmt_info
, 0,
3056 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1,
3057 vec_to_scalar
, stmt_info
, 0,
3061 /* Use extracts and reduction op for final reduction. For N
3062 elements, we have N extracts and N-1 reduction ops. */
3063 epilogue_cost
+= add_stmt_cost (target_cost_data
,
3064 nelements
+ nelements
- 1,
3065 vector_stmt
, stmt_info
, 0,
3070 if (dump_enabled_p ())
3071 dump_printf (MSG_NOTE
,
3072 "vect_model_reduction_cost: inside_cost = %d, "
3073 "prologue_cost = %d, epilogue_cost = %d .", inside_cost
,
3074 prologue_cost
, epilogue_cost
);
3080 /* Function vect_model_induction_cost.
3082 Models cost for induction operations. */
3085 vect_model_induction_cost (stmt_vec_info stmt_info
, int ncopies
)
3087 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3088 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3089 unsigned inside_cost
, prologue_cost
;
3091 /* loop cost for vec_loop. */
3092 inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
3093 stmt_info
, 0, vect_body
);
3095 /* prologue cost for vec_init and vec_step. */
3096 prologue_cost
= add_stmt_cost (target_cost_data
, 2, scalar_to_vec
,
3097 stmt_info
, 0, vect_prologue
);
3099 if (dump_enabled_p ())
3100 dump_printf_loc (MSG_NOTE
, vect_location
,
3101 "vect_model_induction_cost: inside_cost = %d, "
3102 "prologue_cost = %d .", inside_cost
, prologue_cost
);
3106 /* Function get_initial_def_for_induction
3109 STMT - a stmt that performs an induction operation in the loop.
3110 IV_PHI - the initial value of the induction variable
3113 Return a vector variable, initialized with the first VF values of
3114 the induction variable. E.g., for an iv with IV_PHI='X' and
3115 evolution S, for a vector of 4 units, we want to return:
3116 [X, X + S, X + 2*S, X + 3*S]. */
3119 get_initial_def_for_induction (gimple iv_phi
)
3121 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (iv_phi
);
3122 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
3123 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3127 edge pe
= loop_preheader_edge (loop
);
3128 struct loop
*iv_loop
;
3130 tree new_vec
, vec_init
, vec_step
, t
;
3134 gimple init_stmt
, induction_phi
, new_stmt
;
3135 tree induc_def
, vec_def
, vec_dest
;
3136 tree init_expr
, step_expr
;
3137 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3142 stmt_vec_info phi_info
= vinfo_for_stmt (iv_phi
);
3143 bool nested_in_vect_loop
= false;
3144 gimple_seq stmts
= NULL
;
3145 imm_use_iterator imm_iter
;
3146 use_operand_p use_p
;
3150 gimple_stmt_iterator si
;
3151 basic_block bb
= gimple_bb (iv_phi
);
3155 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
3156 if (nested_in_vect_loop_p (loop
, iv_phi
))
3158 nested_in_vect_loop
= true;
3159 iv_loop
= loop
->inner
;
3163 gcc_assert (iv_loop
== (gimple_bb (iv_phi
))->loop_father
);
3165 latch_e
= loop_latch_edge (iv_loop
);
3166 loop_arg
= PHI_ARG_DEF_FROM_EDGE (iv_phi
, latch_e
);
3168 access_fn
= analyze_scalar_evolution (iv_loop
, PHI_RESULT (iv_phi
));
3169 gcc_assert (access_fn
);
3170 STRIP_NOPS (access_fn
);
3171 ok
= vect_is_simple_iv_evolution (iv_loop
->num
, access_fn
,
3172 &init_expr
, &step_expr
);
3174 pe
= loop_preheader_edge (iv_loop
);
3176 scalar_type
= TREE_TYPE (init_expr
);
3177 vectype
= get_vectype_for_scalar_type (scalar_type
);
3178 resvectype
= get_vectype_for_scalar_type (TREE_TYPE (PHI_RESULT (iv_phi
)));
3179 gcc_assert (vectype
);
3180 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3181 ncopies
= vf
/ nunits
;
3183 gcc_assert (phi_info
);
3184 gcc_assert (ncopies
>= 1);
3186 /* Find the first insertion point in the BB. */
3187 si
= gsi_after_labels (bb
);
3189 /* Create the vector that holds the initial_value of the induction. */
3190 if (nested_in_vect_loop
)
3192 /* iv_loop is nested in the loop to be vectorized. init_expr had already
3193 been created during vectorization of previous stmts. We obtain it
3194 from the STMT_VINFO_VEC_STMT of the defining stmt. */
3195 tree iv_def
= PHI_ARG_DEF_FROM_EDGE (iv_phi
,
3196 loop_preheader_edge (iv_loop
));
3197 vec_init
= vect_get_vec_def_for_operand (iv_def
, iv_phi
, NULL
);
3198 /* If the initial value is not of proper type, convert it. */
3199 if (!useless_type_conversion_p (vectype
, TREE_TYPE (vec_init
)))
3201 new_stmt
= gimple_build_assign_with_ops
3203 vect_get_new_vect_var (vectype
, vect_simple_var
, "vec_iv_"),
3204 build1 (VIEW_CONVERT_EXPR
, vectype
, vec_init
), NULL_TREE
);
3205 vec_init
= make_ssa_name (gimple_assign_lhs (new_stmt
), new_stmt
);
3206 gimple_assign_set_lhs (new_stmt
, vec_init
);
3207 new_bb
= gsi_insert_on_edge_immediate (loop_preheader_edge (iv_loop
),
3209 gcc_assert (!new_bb
);
3210 set_vinfo_for_stmt (new_stmt
,
3211 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
3216 vec
<constructor_elt
, va_gc
> *v
;
3218 /* iv_loop is the loop to be vectorized. Create:
3219 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
3220 new_var
= vect_get_new_vect_var (scalar_type
, vect_scalar_var
, "var_");
3221 new_name
= force_gimple_operand (init_expr
, &stmts
, false, new_var
);
3224 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
3225 gcc_assert (!new_bb
);
3228 vec_alloc (v
, nunits
);
3229 bool constant_p
= is_gimple_min_invariant (new_name
);
3230 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
3231 for (i
= 1; i
< nunits
; i
++)
3233 /* Create: new_name_i = new_name + step_expr */
3234 enum tree_code code
= POINTER_TYPE_P (scalar_type
)
3235 ? POINTER_PLUS_EXPR
: PLUS_EXPR
;
3236 new_name
= fold_build2 (code
, scalar_type
, new_name
, step_expr
);
3237 if (!is_gimple_min_invariant (new_name
))
3239 init_stmt
= gimple_build_assign (new_var
, new_name
);
3240 new_name
= make_ssa_name (new_var
, init_stmt
);
3241 gimple_assign_set_lhs (init_stmt
, new_name
);
3242 new_bb
= gsi_insert_on_edge_immediate (pe
, init_stmt
);
3243 gcc_assert (!new_bb
);
3244 if (dump_enabled_p ())
3246 dump_printf_loc (MSG_NOTE
, vect_location
,
3247 "created new init_stmt: ");
3248 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, init_stmt
, 0);
3252 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
3254 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
3256 new_vec
= build_vector_from_ctor (vectype
, v
);
3258 new_vec
= build_constructor (vectype
, v
);
3259 vec_init
= vect_init_vector (iv_phi
, new_vec
, vectype
, NULL
);
3263 /* Create the vector that holds the step of the induction. */
3264 if (nested_in_vect_loop
)
3265 /* iv_loop is nested in the loop to be vectorized. Generate:
3266 vec_step = [S, S, S, S] */
3267 new_name
= step_expr
;
3270 /* iv_loop is the loop to be vectorized. Generate:
3271 vec_step = [VF*S, VF*S, VF*S, VF*S] */
3272 expr
= build_int_cst (TREE_TYPE (step_expr
), vf
);
3273 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
3277 t
= unshare_expr (new_name
);
3278 gcc_assert (CONSTANT_CLASS_P (new_name
));
3279 stepvectype
= get_vectype_for_scalar_type (TREE_TYPE (new_name
));
3280 gcc_assert (stepvectype
);
3281 new_vec
= build_vector_from_val (stepvectype
, t
);
3282 vec_step
= vect_init_vector (iv_phi
, new_vec
, stepvectype
, NULL
);
3285 /* Create the following def-use cycle:
3290 vec_iv = PHI <vec_init, vec_loop>
3294 vec_loop = vec_iv + vec_step; */
3296 /* Create the induction-phi that defines the induction-operand. */
3297 vec_dest
= vect_get_new_vect_var (vectype
, vect_simple_var
, "vec_iv_");
3298 induction_phi
= create_phi_node (vec_dest
, iv_loop
->header
);
3299 set_vinfo_for_stmt (induction_phi
,
3300 new_stmt_vec_info (induction_phi
, loop_vinfo
, NULL
));
3301 induc_def
= PHI_RESULT (induction_phi
);
3303 /* Create the iv update inside the loop */
3304 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, vec_dest
,
3305 induc_def
, vec_step
);
3306 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
3307 gimple_assign_set_lhs (new_stmt
, vec_def
);
3308 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3309 set_vinfo_for_stmt (new_stmt
, new_stmt_vec_info (new_stmt
, loop_vinfo
,
3312 /* Set the arguments of the phi node: */
3313 add_phi_arg (induction_phi
, vec_init
, pe
, UNKNOWN_LOCATION
);
3314 add_phi_arg (induction_phi
, vec_def
, loop_latch_edge (iv_loop
),
3318 /* In case that vectorization factor (VF) is bigger than the number
3319 of elements that we can fit in a vectype (nunits), we have to generate
3320 more than one vector stmt - i.e - we need to "unroll" the
3321 vector stmt by a factor VF/nunits. For more details see documentation
3322 in vectorizable_operation. */
3326 stmt_vec_info prev_stmt_vinfo
;
3327 /* FORNOW. This restriction should be relaxed. */
3328 gcc_assert (!nested_in_vect_loop
);
3330 /* Create the vector that holds the step of the induction. */
3331 expr
= build_int_cst (TREE_TYPE (step_expr
), nunits
);
3332 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
3334 t
= unshare_expr (new_name
);
3335 gcc_assert (CONSTANT_CLASS_P (new_name
));
3336 new_vec
= build_vector_from_val (stepvectype
, t
);
3337 vec_step
= vect_init_vector (iv_phi
, new_vec
, stepvectype
, NULL
);
3339 vec_def
= induc_def
;
3340 prev_stmt_vinfo
= vinfo_for_stmt (induction_phi
);
3341 for (i
= 1; i
< ncopies
; i
++)
3343 /* vec_i = vec_prev + vec_step */
3344 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, vec_dest
,
3346 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
3347 gimple_assign_set_lhs (new_stmt
, vec_def
);
3349 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3350 if (!useless_type_conversion_p (resvectype
, vectype
))
3352 new_stmt
= gimple_build_assign_with_ops
3354 vect_get_new_vect_var (resvectype
, vect_simple_var
,
3356 build1 (VIEW_CONVERT_EXPR
, resvectype
,
3357 gimple_assign_lhs (new_stmt
)), NULL_TREE
);
3358 gimple_assign_set_lhs (new_stmt
,
3360 (gimple_assign_lhs (new_stmt
), new_stmt
));
3361 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3363 set_vinfo_for_stmt (new_stmt
,
3364 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
3365 STMT_VINFO_RELATED_STMT (prev_stmt_vinfo
) = new_stmt
;
3366 prev_stmt_vinfo
= vinfo_for_stmt (new_stmt
);
3370 if (nested_in_vect_loop
)
3372 /* Find the loop-closed exit-phi of the induction, and record
3373 the final vector of induction results: */
3375 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
3377 if (!flow_bb_inside_loop_p (iv_loop
, gimple_bb (USE_STMT (use_p
))))
3379 exit_phi
= USE_STMT (use_p
);
3385 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (exit_phi
);
3386 /* FORNOW. Currently not supporting the case that an inner-loop induction
3387 is not used in the outer-loop (i.e. only outside the outer-loop). */
3388 gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo
)
3389 && !STMT_VINFO_LIVE_P (stmt_vinfo
));
3391 STMT_VINFO_VEC_STMT (stmt_vinfo
) = new_stmt
;
3392 if (dump_enabled_p ())
3394 dump_printf_loc (MSG_NOTE
, vect_location
,
3395 "vector of inductions after inner-loop:");
3396 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, new_stmt
, 0);
3402 if (dump_enabled_p ())
3404 dump_printf_loc (MSG_NOTE
, vect_location
,
3405 "transform induction: created def-use cycle: ");
3406 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, induction_phi
, 0);
3407 dump_printf (MSG_NOTE
, "\n");
3408 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
3409 SSA_NAME_DEF_STMT (vec_def
), 0);
3412 STMT_VINFO_VEC_STMT (phi_info
) = induction_phi
;
3413 if (!useless_type_conversion_p (resvectype
, vectype
))
3415 new_stmt
= gimple_build_assign_with_ops
3417 vect_get_new_vect_var (resvectype
, vect_simple_var
, "vec_iv_"),
3418 build1 (VIEW_CONVERT_EXPR
, resvectype
, induc_def
), NULL_TREE
);
3419 induc_def
= make_ssa_name (gimple_assign_lhs (new_stmt
), new_stmt
);
3420 gimple_assign_set_lhs (new_stmt
, induc_def
);
3421 si
= gsi_after_labels (bb
);
3422 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3423 set_vinfo_for_stmt (new_stmt
,
3424 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
3425 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_stmt
))
3426 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (induction_phi
));
3433 /* Function get_initial_def_for_reduction
3436 STMT - a stmt that performs a reduction operation in the loop.
3437 INIT_VAL - the initial value of the reduction variable
3440 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
3441 of the reduction (used for adjusting the epilog - see below).
3442 Return a vector variable, initialized according to the operation that STMT
3443 performs. This vector will be used as the initial value of the
3444 vector of partial results.
3446 Option1 (adjust in epilog): Initialize the vector as follows:
3447 add/bit or/xor: [0,0,...,0,0]
3448 mult/bit and: [1,1,...,1,1]
3449 min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
3450 and when necessary (e.g. add/mult case) let the caller know
3451 that it needs to adjust the result by init_val.
3453 Option2: Initialize the vector as follows:
3454 add/bit or/xor: [init_val,0,0,...,0]
3455 mult/bit and: [init_val,1,1,...,1]
3456 min/max/cond_expr: [init_val,init_val,...,init_val]
3457 and no adjustments are needed.
3459 For example, for the following code:
3465 STMT is 's = s + a[i]', and the reduction variable is 's'.
3466 For a vector of 4 units, we want to return either [0,0,0,init_val],
3467 or [0,0,0,0] and let the caller know that it needs to adjust
3468 the result at the end by 'init_val'.
3470 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
3471 initialization vector is simpler (same element in all entries), if
3472 ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
3474 A cost model should help decide between these two schemes. */
3477 get_initial_def_for_reduction (gimple stmt
, tree init_val
,
3478 tree
*adjustment_def
)
3480 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
3481 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
3482 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3483 tree scalar_type
= TREE_TYPE (init_val
);
3484 tree vectype
= get_vectype_for_scalar_type (scalar_type
);
3486 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3491 bool nested_in_vect_loop
= false;
3493 REAL_VALUE_TYPE real_init_val
= dconst0
;
3494 int int_init_val
= 0;
3495 gimple def_stmt
= NULL
;
3497 gcc_assert (vectype
);
3498 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3500 gcc_assert (POINTER_TYPE_P (scalar_type
) || INTEGRAL_TYPE_P (scalar_type
)
3501 || SCALAR_FLOAT_TYPE_P (scalar_type
));
3503 if (nested_in_vect_loop_p (loop
, stmt
))
3504 nested_in_vect_loop
= true;
3506 gcc_assert (loop
== (gimple_bb (stmt
))->loop_father
);
3508 /* In case of double reduction we only create a vector variable to be put
3509 in the reduction phi node. The actual statement creation is done in
3510 vect_create_epilog_for_reduction. */
3511 if (adjustment_def
&& nested_in_vect_loop
3512 && TREE_CODE (init_val
) == SSA_NAME
3513 && (def_stmt
= SSA_NAME_DEF_STMT (init_val
))
3514 && gimple_code (def_stmt
) == GIMPLE_PHI
3515 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
3516 && vinfo_for_stmt (def_stmt
)
3517 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
3518 == vect_double_reduction_def
)
3520 *adjustment_def
= NULL
;
3521 return vect_create_destination_var (init_val
, vectype
);
3524 if (TREE_CONSTANT (init_val
))
3526 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
3527 init_value
= build_real (scalar_type
, TREE_REAL_CST (init_val
));
3529 init_value
= build_int_cst (scalar_type
, TREE_INT_CST_LOW (init_val
));
3532 init_value
= init_val
;
3536 case WIDEN_SUM_EXPR
:
3544 /* ADJUSMENT_DEF is NULL when called from
3545 vect_create_epilog_for_reduction to vectorize double reduction. */
3548 if (nested_in_vect_loop
)
3549 *adjustment_def
= vect_get_vec_def_for_operand (init_val
, stmt
,
3552 *adjustment_def
= init_val
;
3555 if (code
== MULT_EXPR
)
3557 real_init_val
= dconst1
;
3561 if (code
== BIT_AND_EXPR
)
3564 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
3565 def_for_init
= build_real (scalar_type
, real_init_val
);
3567 def_for_init
= build_int_cst (scalar_type
, int_init_val
);
3569 /* Create a vector of '0' or '1' except the first element. */
3570 elts
= XALLOCAVEC (tree
, nunits
);
3571 for (i
= nunits
- 2; i
>= 0; --i
)
3572 elts
[i
+ 1] = def_for_init
;
3574 /* Option1: the first element is '0' or '1' as well. */
3577 elts
[0] = def_for_init
;
3578 init_def
= build_vector (vectype
, elts
);
3582 /* Option2: the first element is INIT_VAL. */
3584 if (TREE_CONSTANT (init_val
))
3585 init_def
= build_vector (vectype
, elts
);
3588 vec
<constructor_elt
, va_gc
> *v
;
3589 vec_alloc (v
, nunits
);
3590 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, init_val
);
3591 for (i
= 1; i
< nunits
; ++i
)
3592 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[i
]);
3593 init_def
= build_constructor (vectype
, v
);
3603 *adjustment_def
= NULL_TREE
;
3604 init_def
= vect_get_vec_def_for_operand (init_val
, stmt
, NULL
);
3608 init_def
= build_vector_from_val (vectype
, init_value
);
3619 /* Function vect_create_epilog_for_reduction
3621 Create code at the loop-epilog to finalize the result of a reduction
3624 VECT_DEFS is list of vector of partial results, i.e., the lhs's of vector
3625 reduction statements.
3626 STMT is the scalar reduction stmt that is being vectorized.
3627 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
3628 number of elements that we can fit in a vectype (nunits). In this case
3629 we have to generate more than one vector stmt - i.e - we need to "unroll"
3630 the vector stmt by a factor VF/nunits. For more details see documentation
3631 in vectorizable_operation.
3632 REDUC_CODE is the tree-code for the epilog reduction.
3633 REDUCTION_PHIS is a list of the phi-nodes that carry the reduction
3635 REDUC_INDEX is the index of the operand in the right hand side of the
3636 statement that is defined by REDUCTION_PHI.
3637 DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
3638 SLP_NODE is an SLP node containing a group of reduction statements. The
3639 first one in this group is STMT.
3642 1. Creates the reduction def-use cycles: sets the arguments for
3644 The loop-entry argument is the vectorized initial-value of the reduction.
3645 The loop-latch argument is taken from VECT_DEFS - the vector of partial
3647 2. "Reduces" each vector of partial results VECT_DEFS into a single result,
3648 by applying the operation specified by REDUC_CODE if available, or by
3649 other means (whole-vector shifts or a scalar loop).
3650 The function also creates a new phi node at the loop exit to preserve
3651 loop-closed form, as illustrated below.
3653 The flow at the entry to this function:
3656 vec_def = phi <null, null> # REDUCTION_PHI
3657 VECT_DEF = vector_stmt # vectorized form of STMT
3658 s_loop = scalar_stmt # (scalar) STMT
3660 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3664 The above is transformed by this function into:
3667 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3668 VECT_DEF = vector_stmt # vectorized form of STMT
3669 s_loop = scalar_stmt # (scalar) STMT
3671 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3672 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3673 v_out2 = reduce <v_out1>
3674 s_out3 = extract_field <v_out2, 0>
3675 s_out4 = adjust_result <s_out3>
3681 vect_create_epilog_for_reduction (vec
<tree
> vect_defs
, gimple stmt
,
3682 int ncopies
, enum tree_code reduc_code
,
3683 vec
<gimple
> reduction_phis
,
3684 int reduc_index
, bool double_reduc
,
3687 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3688 stmt_vec_info prev_phi_info
;
3690 enum machine_mode mode
;
3691 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3692 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
), *outer_loop
= NULL
;
3693 basic_block exit_bb
;
3696 gimple new_phi
= NULL
, phi
;
3697 gimple_stmt_iterator exit_gsi
;
3699 tree new_temp
= NULL_TREE
, new_dest
, new_name
, new_scalar_dest
;
3700 gimple epilog_stmt
= NULL
;
3701 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3703 tree bitsize
, bitpos
;
3704 tree adjustment_def
= NULL
;
3705 tree vec_initial_def
= NULL
;
3706 tree reduction_op
, expr
, def
;
3707 tree orig_name
, scalar_result
;
3708 imm_use_iterator imm_iter
, phi_imm_iter
;
3709 use_operand_p use_p
, phi_use_p
;
3710 bool extract_scalar_result
= false;
3711 gimple use_stmt
, orig_stmt
, reduction_phi
= NULL
;
3712 bool nested_in_vect_loop
= false;
3713 vec
<gimple
> new_phis
= vNULL
;
3714 vec
<gimple
> inner_phis
= vNULL
;
3715 enum vect_def_type dt
= vect_unknown_def_type
;
3717 vec
<tree
> scalar_results
= vNULL
;
3718 unsigned int group_size
= 1, k
, ratio
;
3719 vec
<tree
> vec_initial_defs
= vNULL
;
3721 bool slp_reduc
= false;
3722 tree new_phi_result
;
3723 gimple inner_phi
= NULL
;
3726 group_size
= SLP_TREE_SCALAR_STMTS (slp_node
).length ();
3728 if (nested_in_vect_loop_p (loop
, stmt
))
3732 nested_in_vect_loop
= true;
3733 gcc_assert (!slp_node
);
3736 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3738 case GIMPLE_SINGLE_RHS
:
3739 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
))
3741 reduction_op
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), reduc_index
);
3743 case GIMPLE_UNARY_RHS
:
3744 reduction_op
= gimple_assign_rhs1 (stmt
);
3746 case GIMPLE_BINARY_RHS
:
3747 reduction_op
= reduc_index
?
3748 gimple_assign_rhs2 (stmt
) : gimple_assign_rhs1 (stmt
);
3750 case GIMPLE_TERNARY_RHS
:
3751 reduction_op
= gimple_op (stmt
, reduc_index
+ 1);
3757 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
3758 gcc_assert (vectype
);
3759 mode
= TYPE_MODE (vectype
);
3761 /* 1. Create the reduction def-use cycle:
3762 Set the arguments of REDUCTION_PHIS, i.e., transform
3765 vec_def = phi <null, null> # REDUCTION_PHI
3766 VECT_DEF = vector_stmt # vectorized form of STMT
3772 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3773 VECT_DEF = vector_stmt # vectorized form of STMT
3776 (in case of SLP, do it for all the phis). */
3778 /* Get the loop-entry arguments. */
3780 vect_get_vec_defs (reduction_op
, NULL_TREE
, stmt
, &vec_initial_defs
,
3781 NULL
, slp_node
, reduc_index
);
3784 vec_initial_defs
.create (1);
3785 /* For the case of reduction, vect_get_vec_def_for_operand returns
3786 the scalar def before the loop, that defines the initial value
3787 of the reduction variable. */
3788 vec_initial_def
= vect_get_vec_def_for_operand (reduction_op
, stmt
,
3790 vec_initial_defs
.quick_push (vec_initial_def
);
3793 /* Set phi nodes arguments. */
3794 FOR_EACH_VEC_ELT (reduction_phis
, i
, phi
)
3796 tree vec_init_def
= vec_initial_defs
[i
];
3797 tree def
= vect_defs
[i
];
3798 for (j
= 0; j
< ncopies
; j
++)
3800 /* Set the loop-entry arg of the reduction-phi. */
3801 add_phi_arg (phi
, vec_init_def
, loop_preheader_edge (loop
),
3804 /* Set the loop-latch arg for the reduction-phi. */
3806 def
= vect_get_vec_def_for_stmt_copy (vect_unknown_def_type
, def
);
3808 add_phi_arg (phi
, def
, loop_latch_edge (loop
), UNKNOWN_LOCATION
);
3810 if (dump_enabled_p ())
3812 dump_printf_loc (MSG_NOTE
, vect_location
,
3813 "transform reduction: created def-use cycle: ");
3814 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
3815 dump_printf (MSG_NOTE
, "\n");
3816 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, SSA_NAME_DEF_STMT (def
), 0);
3819 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
3823 vec_initial_defs
.release ();
3825 /* 2. Create epilog code.
3826 The reduction epilog code operates across the elements of the vector
3827 of partial results computed by the vectorized loop.
3828 The reduction epilog code consists of:
3830 step 1: compute the scalar result in a vector (v_out2)
3831 step 2: extract the scalar result (s_out3) from the vector (v_out2)
3832 step 3: adjust the scalar result (s_out3) if needed.
3834 Step 1 can be accomplished using one the following three schemes:
3835 (scheme 1) using reduc_code, if available.
3836 (scheme 2) using whole-vector shifts, if available.
3837 (scheme 3) using a scalar loop. In this case steps 1+2 above are
3840 The overall epilog code looks like this:
3842 s_out0 = phi <s_loop> # original EXIT_PHI
3843 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3844 v_out2 = reduce <v_out1> # step 1
3845 s_out3 = extract_field <v_out2, 0> # step 2
3846 s_out4 = adjust_result <s_out3> # step 3
3848 (step 3 is optional, and steps 1 and 2 may be combined).
3849 Lastly, the uses of s_out0 are replaced by s_out4. */
3852 /* 2.1 Create new loop-exit-phis to preserve loop-closed form:
3853 v_out1 = phi <VECT_DEF>
3854 Store them in NEW_PHIS. */
3856 exit_bb
= single_exit (loop
)->dest
;
3857 prev_phi_info
= NULL
;
3858 new_phis
.create (vect_defs
.length ());
3859 FOR_EACH_VEC_ELT (vect_defs
, i
, def
)
3861 for (j
= 0; j
< ncopies
; j
++)
3863 tree new_def
= copy_ssa_name (def
, NULL
);
3864 phi
= create_phi_node (new_def
, exit_bb
);
3865 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, loop_vinfo
, NULL
));
3867 new_phis
.quick_push (phi
);
3870 def
= vect_get_vec_def_for_stmt_copy (dt
, def
);
3871 STMT_VINFO_RELATED_STMT (prev_phi_info
) = phi
;
3874 SET_PHI_ARG_DEF (phi
, single_exit (loop
)->dest_idx
, def
);
3875 prev_phi_info
= vinfo_for_stmt (phi
);
3879 /* The epilogue is created for the outer-loop, i.e., for the loop being
3880 vectorized. Create exit phis for the outer loop. */
3884 exit_bb
= single_exit (loop
)->dest
;
3885 inner_phis
.create (vect_defs
.length ());
3886 FOR_EACH_VEC_ELT (new_phis
, i
, phi
)
3888 tree new_result
= copy_ssa_name (PHI_RESULT (phi
), NULL
);
3889 gimple outer_phi
= create_phi_node (new_result
, exit_bb
);
3890 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
3892 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
3894 inner_phis
.quick_push (phi
);
3895 new_phis
[i
] = outer_phi
;
3896 prev_phi_info
= vinfo_for_stmt (outer_phi
);
3897 while (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
)))
3899 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
3900 new_result
= copy_ssa_name (PHI_RESULT (phi
), NULL
);
3901 outer_phi
= create_phi_node (new_result
, exit_bb
);
3902 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
3904 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
3906 STMT_VINFO_RELATED_STMT (prev_phi_info
) = outer_phi
;
3907 prev_phi_info
= vinfo_for_stmt (outer_phi
);
3912 exit_gsi
= gsi_after_labels (exit_bb
);
3914 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
3915 (i.e. when reduc_code is not available) and in the final adjustment
3916 code (if needed). Also get the original scalar reduction variable as
3917 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
3918 represents a reduction pattern), the tree-code and scalar-def are
3919 taken from the original stmt that the pattern-stmt (STMT) replaces.
3920 Otherwise (it is a regular reduction) - the tree-code and scalar-def
3921 are taken from STMT. */
3923 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
3926 /* Regular reduction */
3931 /* Reduction pattern */
3932 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (orig_stmt
);
3933 gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
));
3934 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo
) == stmt
);
3937 code
= gimple_assign_rhs_code (orig_stmt
);
3938 /* For MINUS_EXPR the initial vector is [init_val,0,...,0], therefore,
3939 partial results are added and not subtracted. */
3940 if (code
== MINUS_EXPR
)
3943 scalar_dest
= gimple_assign_lhs (orig_stmt
);
3944 scalar_type
= TREE_TYPE (scalar_dest
);
3945 scalar_results
.create (group_size
);
3946 new_scalar_dest
= vect_create_destination_var (scalar_dest
, NULL
);
3947 bitsize
= TYPE_SIZE (scalar_type
);
3949 /* In case this is a reduction in an inner-loop while vectorizing an outer
3950 loop - we don't need to extract a single scalar result at the end of the
3951 inner-loop (unless it is double reduction, i.e., the use of reduction is
3952 outside the outer-loop). The final vector of partial results will be used
3953 in the vectorized outer-loop, or reduced to a scalar result at the end of
3955 if (nested_in_vect_loop
&& !double_reduc
)
3956 goto vect_finalize_reduction
;
3958 /* SLP reduction without reduction chain, e.g.,
3962 b2 = operation (b1) */
3963 slp_reduc
= (slp_node
&& !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)));
3965 /* In case of reduction chain, e.g.,
3968 a3 = operation (a2),
3970 we may end up with more than one vector result. Here we reduce them to
3972 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
3974 tree first_vect
= PHI_RESULT (new_phis
[0]);
3976 gimple new_vec_stmt
= NULL
;
3978 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
3979 for (k
= 1; k
< new_phis
.length (); k
++)
3981 gimple next_phi
= new_phis
[k
];
3982 tree second_vect
= PHI_RESULT (next_phi
);
3984 tmp
= build2 (code
, vectype
, first_vect
, second_vect
);
3985 new_vec_stmt
= gimple_build_assign (vec_dest
, tmp
);
3986 first_vect
= make_ssa_name (vec_dest
, new_vec_stmt
);
3987 gimple_assign_set_lhs (new_vec_stmt
, first_vect
);
3988 gsi_insert_before (&exit_gsi
, new_vec_stmt
, GSI_SAME_STMT
);
3991 new_phi_result
= first_vect
;
3994 new_phis
.truncate (0);
3995 new_phis
.safe_push (new_vec_stmt
);
3999 new_phi_result
= PHI_RESULT (new_phis
[0]);
4001 /* 2.3 Create the reduction code, using one of the three schemes described
4002 above. In SLP we simply need to extract all the elements from the
4003 vector (without reducing them), so we use scalar shifts. */
4004 if (reduc_code
!= ERROR_MARK
&& !slp_reduc
)
4008 /*** Case 1: Create:
4009 v_out2 = reduc_expr <v_out1> */
4011 if (dump_enabled_p ())
4012 dump_printf_loc (MSG_NOTE
, vect_location
,
4013 "Reduce using direct vector reduction.");
4015 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4016 tmp
= build1 (reduc_code
, vectype
, new_phi_result
);
4017 epilog_stmt
= gimple_build_assign (vec_dest
, tmp
);
4018 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
4019 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4020 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4022 extract_scalar_result
= true;
4026 enum tree_code shift_code
= ERROR_MARK
;
4027 bool have_whole_vector_shift
= true;
4029 int element_bitsize
= tree_low_cst (bitsize
, 1);
4030 int vec_size_in_bits
= tree_low_cst (TYPE_SIZE (vectype
), 1);
4033 if (optab_handler (vec_shr_optab
, mode
) != CODE_FOR_nothing
)
4034 shift_code
= VEC_RSHIFT_EXPR
;
4036 have_whole_vector_shift
= false;
4038 /* Regardless of whether we have a whole vector shift, if we're
4039 emulating the operation via tree-vect-generic, we don't want
4040 to use it. Only the first round of the reduction is likely
4041 to still be profitable via emulation. */
4042 /* ??? It might be better to emit a reduction tree code here, so that
4043 tree-vect-generic can expand the first round via bit tricks. */
4044 if (!VECTOR_MODE_P (mode
))
4045 have_whole_vector_shift
= false;
4048 optab optab
= optab_for_tree_code (code
, vectype
, optab_default
);
4049 if (optab_handler (optab
, mode
) == CODE_FOR_nothing
)
4050 have_whole_vector_shift
= false;
4053 if (have_whole_vector_shift
&& !slp_reduc
)
4055 /*** Case 2: Create:
4056 for (offset = VS/2; offset >= element_size; offset/=2)
4058 Create: va' = vec_shift <va, offset>
4059 Create: va = vop <va, va'>
4062 if (dump_enabled_p ())
4063 dump_printf_loc (MSG_NOTE
, vect_location
,
4064 "Reduce using vector shifts");
4066 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4067 new_temp
= new_phi_result
;
4068 for (bit_offset
= vec_size_in_bits
/2;
4069 bit_offset
>= element_bitsize
;
4072 tree bitpos
= size_int (bit_offset
);
4074 epilog_stmt
= gimple_build_assign_with_ops (shift_code
,
4075 vec_dest
, new_temp
, bitpos
);
4076 new_name
= make_ssa_name (vec_dest
, epilog_stmt
);
4077 gimple_assign_set_lhs (epilog_stmt
, new_name
);
4078 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4080 epilog_stmt
= gimple_build_assign_with_ops (code
, vec_dest
,
4081 new_name
, new_temp
);
4082 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
4083 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4084 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4087 extract_scalar_result
= true;
4093 /*** Case 3: Create:
4094 s = extract_field <v_out2, 0>
4095 for (offset = element_size;
4096 offset < vector_size;
4097 offset += element_size;)
4099 Create: s' = extract_field <v_out2, offset>
4100 Create: s = op <s, s'> // For non SLP cases
4103 if (dump_enabled_p ())
4104 dump_printf_loc (MSG_NOTE
, vect_location
,
4105 "Reduce using scalar code. ");
4107 vec_size_in_bits
= tree_low_cst (TYPE_SIZE (vectype
), 1);
4108 FOR_EACH_VEC_ELT (new_phis
, i
, new_phi
)
4110 if (gimple_code (new_phi
) == GIMPLE_PHI
)
4111 vec_temp
= PHI_RESULT (new_phi
);
4113 vec_temp
= gimple_assign_lhs (new_phi
);
4114 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
, bitsize
,
4116 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4117 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4118 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4119 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4121 /* In SLP we don't need to apply reduction operation, so we just
4122 collect s' values in SCALAR_RESULTS. */
4124 scalar_results
.safe_push (new_temp
);
4126 for (bit_offset
= element_bitsize
;
4127 bit_offset
< vec_size_in_bits
;
4128 bit_offset
+= element_bitsize
)
4130 tree bitpos
= bitsize_int (bit_offset
);
4131 tree rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
,
4134 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4135 new_name
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4136 gimple_assign_set_lhs (epilog_stmt
, new_name
);
4137 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4141 /* In SLP we don't need to apply reduction operation, so
4142 we just collect s' values in SCALAR_RESULTS. */
4143 new_temp
= new_name
;
4144 scalar_results
.safe_push (new_name
);
4148 epilog_stmt
= gimple_build_assign_with_ops (code
,
4149 new_scalar_dest
, new_name
, new_temp
);
4150 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4151 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4152 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4157 /* The only case where we need to reduce scalar results in SLP, is
4158 unrolling. If the size of SCALAR_RESULTS is greater than
4159 GROUP_SIZE, we reduce them combining elements modulo
4163 tree res
, first_res
, new_res
;
4166 /* Reduce multiple scalar results in case of SLP unrolling. */
4167 for (j
= group_size
; scalar_results
.iterate (j
, &res
);
4170 first_res
= scalar_results
[j
% group_size
];
4171 new_stmt
= gimple_build_assign_with_ops (code
,
4172 new_scalar_dest
, first_res
, res
);
4173 new_res
= make_ssa_name (new_scalar_dest
, new_stmt
);
4174 gimple_assign_set_lhs (new_stmt
, new_res
);
4175 gsi_insert_before (&exit_gsi
, new_stmt
, GSI_SAME_STMT
);
4176 scalar_results
[j
% group_size
] = new_res
;
4180 /* Not SLP - we have one scalar to keep in SCALAR_RESULTS. */
4181 scalar_results
.safe_push (new_temp
);
4183 extract_scalar_result
= false;
4187 /* 2.4 Extract the final scalar result. Create:
4188 s_out3 = extract_field <v_out2, bitpos> */
4190 if (extract_scalar_result
)
4194 if (dump_enabled_p ())
4195 dump_printf_loc (MSG_NOTE
, vect_location
,
4196 "extract scalar result");
4198 if (BYTES_BIG_ENDIAN
)
4199 bitpos
= size_binop (MULT_EXPR
,
4200 bitsize_int (TYPE_VECTOR_SUBPARTS (vectype
) - 1),
4201 TYPE_SIZE (scalar_type
));
4203 bitpos
= bitsize_zero_node
;
4205 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, new_temp
, bitsize
, bitpos
);
4206 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4207 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4208 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4209 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4210 scalar_results
.safe_push (new_temp
);
4213 vect_finalize_reduction
:
4218 /* 2.5 Adjust the final result by the initial value of the reduction
4219 variable. (When such adjustment is not needed, then
4220 'adjustment_def' is zero). For example, if code is PLUS we create:
4221 new_temp = loop_exit_def + adjustment_def */
4225 gcc_assert (!slp_reduc
);
4226 if (nested_in_vect_loop
)
4228 new_phi
= new_phis
[0];
4229 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) == VECTOR_TYPE
);
4230 expr
= build2 (code
, vectype
, PHI_RESULT (new_phi
), adjustment_def
);
4231 new_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4235 new_temp
= scalar_results
[0];
4236 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) != VECTOR_TYPE
);
4237 expr
= build2 (code
, scalar_type
, new_temp
, adjustment_def
);
4238 new_dest
= vect_create_destination_var (scalar_dest
, scalar_type
);
4241 epilog_stmt
= gimple_build_assign (new_dest
, expr
);
4242 new_temp
= make_ssa_name (new_dest
, epilog_stmt
);
4243 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4244 SSA_NAME_DEF_STMT (new_temp
) = epilog_stmt
;
4245 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4246 if (nested_in_vect_loop
)
4248 set_vinfo_for_stmt (epilog_stmt
,
4249 new_stmt_vec_info (epilog_stmt
, loop_vinfo
,
4251 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (epilog_stmt
)) =
4252 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_phi
));
4255 scalar_results
.quick_push (new_temp
);
4257 scalar_results
[0] = new_temp
;
4260 scalar_results
[0] = new_temp
;
4262 new_phis
[0] = epilog_stmt
;
4265 /* 2.6 Handle the loop-exit phis. Replace the uses of scalar loop-exit
4266 phis with new adjusted scalar results, i.e., replace use <s_out0>
4271 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4272 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4273 v_out2 = reduce <v_out1>
4274 s_out3 = extract_field <v_out2, 0>
4275 s_out4 = adjust_result <s_out3>
4282 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4283 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4284 v_out2 = reduce <v_out1>
4285 s_out3 = extract_field <v_out2, 0>
4286 s_out4 = adjust_result <s_out3>
4291 /* In SLP reduction chain we reduce vector results into one vector if
4292 necessary, hence we set here GROUP_SIZE to 1. SCALAR_DEST is the LHS of
4293 the last stmt in the reduction chain, since we are looking for the loop
4295 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4297 scalar_dest
= gimple_assign_lhs (
4298 SLP_TREE_SCALAR_STMTS (slp_node
)[group_size
- 1]);
4302 /* In SLP we may have several statements in NEW_PHIS and REDUCTION_PHIS (in
4303 case that GROUP_SIZE is greater than vectorization factor). Therefore, we
4304 need to match SCALAR_RESULTS with corresponding statements. The first
4305 (GROUP_SIZE / number of new vector stmts) scalar results correspond to
4306 the first vector stmt, etc.
4307 (RATIO is equal to (GROUP_SIZE / number of new vector stmts)). */
4308 if (group_size
> new_phis
.length ())
4310 ratio
= group_size
/ new_phis
.length ();
4311 gcc_assert (!(group_size
% new_phis
.length ()));
4316 for (k
= 0; k
< group_size
; k
++)
4320 epilog_stmt
= new_phis
[k
/ ratio
];
4321 reduction_phi
= reduction_phis
[k
/ ratio
];
4323 inner_phi
= inner_phis
[k
/ ratio
];
4328 gimple current_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[k
];
4330 orig_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (current_stmt
));
4331 /* SLP statements can't participate in patterns. */
4332 gcc_assert (!orig_stmt
);
4333 scalar_dest
= gimple_assign_lhs (current_stmt
);
4337 /* Find the loop-closed-use at the loop exit of the original scalar
4338 result. (The reduction result is expected to have two immediate uses -
4339 one at the latch block, and one at the loop exit). */
4340 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
4341 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
4342 phis
.safe_push (USE_STMT (use_p
));
4344 /* We expect to have found an exit_phi because of loop-closed-ssa
4346 gcc_assert (!phis
.is_empty ());
4348 FOR_EACH_VEC_ELT (phis
, i
, exit_phi
)
4352 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
4355 /* FORNOW. Currently not supporting the case that an inner-loop
4356 reduction is not used in the outer-loop (but only outside the
4357 outer-loop), unless it is double reduction. */
4358 gcc_assert ((STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
4359 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
))
4362 STMT_VINFO_VEC_STMT (exit_phi_vinfo
) = epilog_stmt
;
4364 || STMT_VINFO_DEF_TYPE (exit_phi_vinfo
)
4365 != vect_double_reduction_def
)
4368 /* Handle double reduction:
4370 stmt1: s1 = phi <s0, s2> - double reduction phi (outer loop)
4371 stmt2: s3 = phi <s1, s4> - (regular) reduc phi (inner loop)
4372 stmt3: s4 = use (s3) - (regular) reduc stmt (inner loop)
4373 stmt4: s2 = phi <s4> - double reduction stmt (outer loop)
4375 At that point the regular reduction (stmt2 and stmt3) is
4376 already vectorized, as well as the exit phi node, stmt4.
4377 Here we vectorize the phi node of double reduction, stmt1, and
4378 update all relevant statements. */
4380 /* Go through all the uses of s2 to find double reduction phi
4381 node, i.e., stmt1 above. */
4382 orig_name
= PHI_RESULT (exit_phi
);
4383 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
4385 stmt_vec_info use_stmt_vinfo
;
4386 stmt_vec_info new_phi_vinfo
;
4387 tree vect_phi_init
, preheader_arg
, vect_phi_res
, init_def
;
4388 basic_block bb
= gimple_bb (use_stmt
);
4391 /* Check that USE_STMT is really double reduction phi
4393 if (gimple_code (use_stmt
) != GIMPLE_PHI
4394 || gimple_phi_num_args (use_stmt
) != 2
4395 || bb
->loop_father
!= outer_loop
)
4397 use_stmt_vinfo
= vinfo_for_stmt (use_stmt
);
4399 || STMT_VINFO_DEF_TYPE (use_stmt_vinfo
)
4400 != vect_double_reduction_def
)
4403 /* Create vector phi node for double reduction:
4404 vs1 = phi <vs0, vs2>
4405 vs1 was created previously in this function by a call to
4406 vect_get_vec_def_for_operand and is stored in
4408 vs2 is defined by INNER_PHI, the vectorized EXIT_PHI;
4409 vs0 is created here. */
4411 /* Create vector phi node. */
4412 vect_phi
= create_phi_node (vec_initial_def
, bb
);
4413 new_phi_vinfo
= new_stmt_vec_info (vect_phi
,
4414 loop_vec_info_for_loop (outer_loop
), NULL
);
4415 set_vinfo_for_stmt (vect_phi
, new_phi_vinfo
);
4417 /* Create vs0 - initial def of the double reduction phi. */
4418 preheader_arg
= PHI_ARG_DEF_FROM_EDGE (use_stmt
,
4419 loop_preheader_edge (outer_loop
));
4420 init_def
= get_initial_def_for_reduction (stmt
,
4421 preheader_arg
, NULL
);
4422 vect_phi_init
= vect_init_vector (use_stmt
, init_def
,
4425 /* Update phi node arguments with vs0 and vs2. */
4426 add_phi_arg (vect_phi
, vect_phi_init
,
4427 loop_preheader_edge (outer_loop
),
4429 add_phi_arg (vect_phi
, PHI_RESULT (inner_phi
),
4430 loop_latch_edge (outer_loop
), UNKNOWN_LOCATION
);
4431 if (dump_enabled_p ())
4433 dump_printf_loc (MSG_NOTE
, vect_location
,
4434 "created double reduction phi node: ");
4435 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, vect_phi
, 0);
4438 vect_phi_res
= PHI_RESULT (vect_phi
);
4440 /* Replace the use, i.e., set the correct vs1 in the regular
4441 reduction phi node. FORNOW, NCOPIES is always 1, so the
4442 loop is redundant. */
4443 use
= reduction_phi
;
4444 for (j
= 0; j
< ncopies
; j
++)
4446 edge pr_edge
= loop_preheader_edge (loop
);
4447 SET_PHI_ARG_DEF (use
, pr_edge
->dest_idx
, vect_phi_res
);
4448 use
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use
));
4455 if (nested_in_vect_loop
)
4464 /* Find the loop-closed-use at the loop exit of the original scalar
4465 result. (The reduction result is expected to have two immediate uses,
4466 one at the latch block, and one at the loop exit). For double
4467 reductions we are looking for exit phis of the outer loop. */
4468 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
4470 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
4471 phis
.safe_push (USE_STMT (use_p
));
4474 if (double_reduc
&& gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
4476 tree phi_res
= PHI_RESULT (USE_STMT (use_p
));
4478 FOR_EACH_IMM_USE_FAST (phi_use_p
, phi_imm_iter
, phi_res
)
4480 if (!flow_bb_inside_loop_p (loop
,
4481 gimple_bb (USE_STMT (phi_use_p
))))
4482 phis
.safe_push (USE_STMT (phi_use_p
));
4488 FOR_EACH_VEC_ELT (phis
, i
, exit_phi
)
4490 /* Replace the uses: */
4491 orig_name
= PHI_RESULT (exit_phi
);
4492 scalar_result
= scalar_results
[k
];
4493 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
4494 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
4495 SET_USE (use_p
, scalar_result
);
4501 scalar_results
.release ();
4502 inner_phis
.release ();
4503 new_phis
.release ();
4507 /* Function vectorizable_reduction.
4509 Check if STMT performs a reduction operation that can be vectorized.
4510 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4511 stmt to replace it, put it in VEC_STMT, and insert it at GSI.
4512 Return FALSE if not a vectorizable STMT, TRUE otherwise.
4514 This function also handles reduction idioms (patterns) that have been
4515 recognized in advance during vect_pattern_recog. In this case, STMT may be
4517 X = pattern_expr (arg0, arg1, ..., X)
4518 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
4519 sequence that had been detected and replaced by the pattern-stmt (STMT).
4521 In some cases of reduction patterns, the type of the reduction variable X is
4522 different than the type of the other arguments of STMT.
4523 In such cases, the vectype that is used when transforming STMT into a vector
4524 stmt is different than the vectype that is used to determine the
4525 vectorization factor, because it consists of a different number of elements
4526 than the actual number of elements that are being operated upon in parallel.
4528 For example, consider an accumulation of shorts into an int accumulator.
4529 On some targets it's possible to vectorize this pattern operating on 8
4530 shorts at a time (hence, the vectype for purposes of determining the
4531 vectorization factor should be V8HI); on the other hand, the vectype that
4532 is used to create the vector form is actually V4SI (the type of the result).
4534 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
4535 indicates what is the actual level of parallelism (V8HI in the example), so
4536 that the right vectorization factor would be derived. This vectype
4537 corresponds to the type of arguments to the reduction stmt, and should *NOT*
4538 be used to create the vectorized stmt. The right vectype for the vectorized
4539 stmt is obtained from the type of the result X:
4540 get_vectype_for_scalar_type (TREE_TYPE (X))
4542 This means that, contrary to "regular" reductions (or "regular" stmts in
4543 general), the following equation:
4544 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
4545 does *NOT* necessarily hold for reduction patterns. */
4548 vectorizable_reduction (gimple stmt
, gimple_stmt_iterator
*gsi
,
4549 gimple
*vec_stmt
, slp_tree slp_node
)
4553 tree loop_vec_def0
= NULL_TREE
, loop_vec_def1
= NULL_TREE
;
4554 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
4555 tree vectype_out
= STMT_VINFO_VECTYPE (stmt_info
);
4556 tree vectype_in
= NULL_TREE
;
4557 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
4558 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4559 enum tree_code code
, orig_code
, epilog_reduc_code
;
4560 enum machine_mode vec_mode
;
4562 optab optab
, reduc_optab
;
4563 tree new_temp
= NULL_TREE
;
4566 enum vect_def_type dt
;
4567 gimple new_phi
= NULL
;
4571 stmt_vec_info orig_stmt_info
;
4572 tree expr
= NULL_TREE
;
4576 stmt_vec_info prev_stmt_info
, prev_phi_info
;
4577 bool single_defuse_cycle
= false;
4578 tree reduc_def
= NULL_TREE
;
4579 gimple new_stmt
= NULL
;
4582 bool nested_cycle
= false, found_nested_cycle_def
= false;
4583 gimple reduc_def_stmt
= NULL
;
4584 /* The default is that the reduction variable is the last in statement. */
4585 int reduc_index
= 2;
4586 bool double_reduc
= false, dummy
;
4588 struct loop
* def_stmt_loop
, *outer_loop
= NULL
;
4590 gimple def_arg_stmt
;
4591 vec
<tree
> vec_oprnds0
= vNULL
;
4592 vec
<tree
> vec_oprnds1
= vNULL
;
4593 vec
<tree
> vect_defs
= vNULL
;
4594 vec
<gimple
> phis
= vNULL
;
4596 tree def0
, def1
, tem
, op0
, op1
= NULL_TREE
;
4598 /* In case of reduction chain we switch to the first stmt in the chain, but
4599 we don't update STMT_INFO, since only the last stmt is marked as reduction
4600 and has reduction properties. */
4601 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4602 stmt
= GROUP_FIRST_ELEMENT (stmt_info
);
4604 if (nested_in_vect_loop_p (loop
, stmt
))
4608 nested_cycle
= true;
4611 /* 1. Is vectorizable reduction? */
4612 /* Not supportable if the reduction variable is used in the loop, unless
4613 it's a reduction chain. */
4614 if (STMT_VINFO_RELEVANT (stmt_info
) > vect_used_in_outer
4615 && !GROUP_FIRST_ELEMENT (stmt_info
))
4618 /* Reductions that are not used even in an enclosing outer-loop,
4619 are expected to be "live" (used out of the loop). */
4620 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
4621 && !STMT_VINFO_LIVE_P (stmt_info
))
4624 /* Make sure it was already recognized as a reduction computation. */
4625 if (STMT_VINFO_DEF_TYPE (stmt_info
) != vect_reduction_def
4626 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_nested_cycle
)
4629 /* 2. Has this been recognized as a reduction pattern?
4631 Check if STMT represents a pattern that has been recognized
4632 in earlier analysis stages. For stmts that represent a pattern,
4633 the STMT_VINFO_RELATED_STMT field records the last stmt in
4634 the original sequence that constitutes the pattern. */
4636 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
4639 orig_stmt_info
= vinfo_for_stmt (orig_stmt
);
4640 gcc_assert (STMT_VINFO_IN_PATTERN_P (orig_stmt_info
));
4641 gcc_assert (!STMT_VINFO_IN_PATTERN_P (stmt_info
));
4644 /* 3. Check the operands of the operation. The first operands are defined
4645 inside the loop body. The last operand is the reduction variable,
4646 which is defined by the loop-header-phi. */
4648 gcc_assert (is_gimple_assign (stmt
));
4651 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
4653 case GIMPLE_SINGLE_RHS
:
4654 op_type
= TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
));
4655 if (op_type
== ternary_op
)
4657 tree rhs
= gimple_assign_rhs1 (stmt
);
4658 ops
[0] = TREE_OPERAND (rhs
, 0);
4659 ops
[1] = TREE_OPERAND (rhs
, 1);
4660 ops
[2] = TREE_OPERAND (rhs
, 2);
4661 code
= TREE_CODE (rhs
);
4667 case GIMPLE_BINARY_RHS
:
4668 code
= gimple_assign_rhs_code (stmt
);
4669 op_type
= TREE_CODE_LENGTH (code
);
4670 gcc_assert (op_type
== binary_op
);
4671 ops
[0] = gimple_assign_rhs1 (stmt
);
4672 ops
[1] = gimple_assign_rhs2 (stmt
);
4675 case GIMPLE_TERNARY_RHS
:
4676 code
= gimple_assign_rhs_code (stmt
);
4677 op_type
= TREE_CODE_LENGTH (code
);
4678 gcc_assert (op_type
== ternary_op
);
4679 ops
[0] = gimple_assign_rhs1 (stmt
);
4680 ops
[1] = gimple_assign_rhs2 (stmt
);
4681 ops
[2] = gimple_assign_rhs3 (stmt
);
4684 case GIMPLE_UNARY_RHS
:
4691 if (code
== COND_EXPR
&& slp_node
)
4694 scalar_dest
= gimple_assign_lhs (stmt
);
4695 scalar_type
= TREE_TYPE (scalar_dest
);
4696 if (!POINTER_TYPE_P (scalar_type
) && !INTEGRAL_TYPE_P (scalar_type
)
4697 && !SCALAR_FLOAT_TYPE_P (scalar_type
))
4700 /* Do not try to vectorize bit-precision reductions. */
4701 if ((TYPE_PRECISION (scalar_type
)
4702 != GET_MODE_PRECISION (TYPE_MODE (scalar_type
))))
4705 /* All uses but the last are expected to be defined in the loop.
4706 The last use is the reduction variable. In case of nested cycle this
4707 assumption is not true: we use reduc_index to record the index of the
4708 reduction variable. */
4709 for (i
= 0; i
< op_type
- 1; i
++)
4711 /* The condition of COND_EXPR is checked in vectorizable_condition(). */
4712 if (i
== 0 && code
== COND_EXPR
)
4715 is_simple_use
= vect_is_simple_use_1 (ops
[i
], stmt
, loop_vinfo
, NULL
,
4716 &def_stmt
, &def
, &dt
, &tem
);
4719 gcc_assert (is_simple_use
);
4721 if (dt
!= vect_internal_def
4722 && dt
!= vect_external_def
4723 && dt
!= vect_constant_def
4724 && dt
!= vect_induction_def
4725 && !(dt
== vect_nested_cycle
&& nested_cycle
))
4728 if (dt
== vect_nested_cycle
)
4730 found_nested_cycle_def
= true;
4731 reduc_def_stmt
= def_stmt
;
4736 is_simple_use
= vect_is_simple_use_1 (ops
[i
], stmt
, loop_vinfo
, NULL
,
4737 &def_stmt
, &def
, &dt
, &tem
);
4740 gcc_assert (is_simple_use
);
4741 if (!(dt
== vect_reduction_def
4742 || dt
== vect_nested_cycle
4743 || ((dt
== vect_internal_def
|| dt
== vect_external_def
4744 || dt
== vect_constant_def
|| dt
== vect_induction_def
)
4745 && nested_cycle
&& found_nested_cycle_def
)))
4747 /* For pattern recognized stmts, orig_stmt might be a reduction,
4748 but some helper statements for the pattern might not, or
4749 might be COND_EXPRs with reduction uses in the condition. */
4750 gcc_assert (orig_stmt
);
4753 if (!found_nested_cycle_def
)
4754 reduc_def_stmt
= def_stmt
;
4756 gcc_assert (gimple_code (reduc_def_stmt
) == GIMPLE_PHI
);
4758 gcc_assert (orig_stmt
== vect_is_simple_reduction (loop_vinfo
,
4764 gimple tmp
= vect_is_simple_reduction (loop_vinfo
, reduc_def_stmt
,
4765 !nested_cycle
, &dummy
);
4766 /* We changed STMT to be the first stmt in reduction chain, hence we
4767 check that in this case the first element in the chain is STMT. */
4768 gcc_assert (stmt
== tmp
4769 || GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp
)) == stmt
);
4772 if (STMT_VINFO_LIVE_P (vinfo_for_stmt (reduc_def_stmt
)))
4775 if (slp_node
|| PURE_SLP_STMT (stmt_info
))
4778 ncopies
= (LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4779 / TYPE_VECTOR_SUBPARTS (vectype_in
));
4781 gcc_assert (ncopies
>= 1);
4783 vec_mode
= TYPE_MODE (vectype_in
);
4785 if (code
== COND_EXPR
)
4787 if (!vectorizable_condition (stmt
, gsi
, NULL
, ops
[reduc_index
], 0, NULL
))
4789 if (dump_enabled_p ())
4790 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4791 "unsupported condition in reduction");
4798 /* 4. Supportable by target? */
4800 if (code
== LSHIFT_EXPR
|| code
== RSHIFT_EXPR
4801 || code
== LROTATE_EXPR
|| code
== RROTATE_EXPR
)
4803 /* Shifts and rotates are only supported by vectorizable_shifts,
4804 not vectorizable_reduction. */
4805 if (dump_enabled_p ())
4806 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4807 "unsupported shift or rotation.");
4811 /* 4.1. check support for the operation in the loop */
4812 optab
= optab_for_tree_code (code
, vectype_in
, optab_default
);
4815 if (dump_enabled_p ())
4816 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4822 if (optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
4824 if (dump_enabled_p ())
4825 dump_printf (MSG_NOTE
, "op not supported by target.");
4827 if (GET_MODE_SIZE (vec_mode
) != UNITS_PER_WORD
4828 || LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4829 < vect_min_worthwhile_factor (code
))
4832 if (dump_enabled_p ())
4833 dump_printf (MSG_NOTE
, "proceeding using word mode.");
4836 /* Worthwhile without SIMD support? */
4837 if (!VECTOR_MODE_P (TYPE_MODE (vectype_in
))
4838 && LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4839 < vect_min_worthwhile_factor (code
))
4841 if (dump_enabled_p ())
4842 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4843 "not worthwhile without SIMD support.");
4849 /* 4.2. Check support for the epilog operation.
4851 If STMT represents a reduction pattern, then the type of the
4852 reduction variable may be different than the type of the rest
4853 of the arguments. For example, consider the case of accumulation
4854 of shorts into an int accumulator; The original code:
4855 S1: int_a = (int) short_a;
4856 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
4859 STMT: int_acc = widen_sum <short_a, int_acc>
4862 1. The tree-code that is used to create the vector operation in the
4863 epilog code (that reduces the partial results) is not the
4864 tree-code of STMT, but is rather the tree-code of the original
4865 stmt from the pattern that STMT is replacing. I.e, in the example
4866 above we want to use 'widen_sum' in the loop, but 'plus' in the
4868 2. The type (mode) we use to check available target support
4869 for the vector operation to be created in the *epilog*, is
4870 determined by the type of the reduction variable (in the example
4871 above we'd check this: optab_handler (plus_optab, vect_int_mode])).
4872 However the type (mode) we use to check available target support
4873 for the vector operation to be created *inside the loop*, is
4874 determined by the type of the other arguments to STMT (in the
4875 example we'd check this: optab_handler (widen_sum_optab,
4878 This is contrary to "regular" reductions, in which the types of all
4879 the arguments are the same as the type of the reduction variable.
4880 For "regular" reductions we can therefore use the same vector type
4881 (and also the same tree-code) when generating the epilog code and
4882 when generating the code inside the loop. */
4886 /* This is a reduction pattern: get the vectype from the type of the
4887 reduction variable, and get the tree-code from orig_stmt. */
4888 orig_code
= gimple_assign_rhs_code (orig_stmt
);
4889 gcc_assert (vectype_out
);
4890 vec_mode
= TYPE_MODE (vectype_out
);
4894 /* Regular reduction: use the same vectype and tree-code as used for
4895 the vector code inside the loop can be used for the epilog code. */
4901 def_bb
= gimple_bb (reduc_def_stmt
);
4902 def_stmt_loop
= def_bb
->loop_father
;
4903 def_arg
= PHI_ARG_DEF_FROM_EDGE (reduc_def_stmt
,
4904 loop_preheader_edge (def_stmt_loop
));
4905 if (TREE_CODE (def_arg
) == SSA_NAME
4906 && (def_arg_stmt
= SSA_NAME_DEF_STMT (def_arg
))
4907 && gimple_code (def_arg_stmt
) == GIMPLE_PHI
4908 && flow_bb_inside_loop_p (outer_loop
, gimple_bb (def_arg_stmt
))
4909 && vinfo_for_stmt (def_arg_stmt
)
4910 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_arg_stmt
))
4911 == vect_double_reduction_def
)
4912 double_reduc
= true;
4915 epilog_reduc_code
= ERROR_MARK
;
4916 if (reduction_code_for_scalar_code (orig_code
, &epilog_reduc_code
))
4918 reduc_optab
= optab_for_tree_code (epilog_reduc_code
, vectype_out
,
4922 if (dump_enabled_p ())
4923 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4924 "no optab for reduction.");
4926 epilog_reduc_code
= ERROR_MARK
;
4930 && optab_handler (reduc_optab
, vec_mode
) == CODE_FOR_nothing
)
4932 if (dump_enabled_p ())
4933 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4934 "reduc op not supported by target.");
4936 epilog_reduc_code
= ERROR_MARK
;
4941 if (!nested_cycle
|| double_reduc
)
4943 if (dump_enabled_p ())
4944 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4945 "no reduc code for scalar code.");
4951 if (double_reduc
&& ncopies
> 1)
4953 if (dump_enabled_p ())
4954 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4955 "multiple types in double reduction");
4960 /* In case of widenning multiplication by a constant, we update the type
4961 of the constant to be the type of the other operand. We check that the
4962 constant fits the type in the pattern recognition pass. */
4963 if (code
== DOT_PROD_EXPR
4964 && !types_compatible_p (TREE_TYPE (ops
[0]), TREE_TYPE (ops
[1])))
4966 if (TREE_CODE (ops
[0]) == INTEGER_CST
)
4967 ops
[0] = fold_convert (TREE_TYPE (ops
[1]), ops
[0]);
4968 else if (TREE_CODE (ops
[1]) == INTEGER_CST
)
4969 ops
[1] = fold_convert (TREE_TYPE (ops
[0]), ops
[1]);
4972 if (dump_enabled_p ())
4973 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4974 "invalid types in dot-prod");
4980 if (!vec_stmt
) /* transformation not required. */
4982 if (!vect_model_reduction_cost (stmt_info
, epilog_reduc_code
, ncopies
))
4984 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
4990 if (dump_enabled_p ())
4991 dump_printf_loc (MSG_NOTE
, vect_location
, "transform reduction.");
4993 /* FORNOW: Multiple types are not supported for condition. */
4994 if (code
== COND_EXPR
)
4995 gcc_assert (ncopies
== 1);
4997 /* Create the destination vector */
4998 vec_dest
= vect_create_destination_var (scalar_dest
, vectype_out
);
5000 /* In case the vectorization factor (VF) is bigger than the number
5001 of elements that we can fit in a vectype (nunits), we have to generate
5002 more than one vector stmt - i.e - we need to "unroll" the
5003 vector stmt by a factor VF/nunits. For more details see documentation
5004 in vectorizable_operation. */
5006 /* If the reduction is used in an outer loop we need to generate
5007 VF intermediate results, like so (e.g. for ncopies=2):
5012 (i.e. we generate VF results in 2 registers).
5013 In this case we have a separate def-use cycle for each copy, and therefore
5014 for each copy we get the vector def for the reduction variable from the
5015 respective phi node created for this copy.
5017 Otherwise (the reduction is unused in the loop nest), we can combine
5018 together intermediate results, like so (e.g. for ncopies=2):
5022 (i.e. we generate VF/2 results in a single register).
5023 In this case for each copy we get the vector def for the reduction variable
5024 from the vectorized reduction operation generated in the previous iteration.
5027 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
)
5029 single_defuse_cycle
= true;
5033 epilog_copies
= ncopies
;
5035 prev_stmt_info
= NULL
;
5036 prev_phi_info
= NULL
;
5039 vec_num
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
5040 gcc_assert (TYPE_VECTOR_SUBPARTS (vectype_out
)
5041 == TYPE_VECTOR_SUBPARTS (vectype_in
));
5046 vec_oprnds0
.create (1);
5047 if (op_type
== ternary_op
)
5048 vec_oprnds1
.create (1);
5051 phis
.create (vec_num
);
5052 vect_defs
.create (vec_num
);
5054 vect_defs
.quick_push (NULL_TREE
);
5056 for (j
= 0; j
< ncopies
; j
++)
5058 if (j
== 0 || !single_defuse_cycle
)
5060 for (i
= 0; i
< vec_num
; i
++)
5062 /* Create the reduction-phi that defines the reduction
5064 new_phi
= create_phi_node (vec_dest
, loop
->header
);
5065 set_vinfo_for_stmt (new_phi
,
5066 new_stmt_vec_info (new_phi
, loop_vinfo
,
5068 if (j
== 0 || slp_node
)
5069 phis
.quick_push (new_phi
);
5073 if (code
== COND_EXPR
)
5075 gcc_assert (!slp_node
);
5076 vectorizable_condition (stmt
, gsi
, vec_stmt
,
5077 PHI_RESULT (phis
[0]),
5079 /* Multiple types are not supported for condition. */
5086 op0
= ops
[!reduc_index
];
5087 if (op_type
== ternary_op
)
5089 if (reduc_index
== 0)
5096 vect_get_vec_defs (op0
, op1
, stmt
, &vec_oprnds0
, &vec_oprnds1
,
5100 loop_vec_def0
= vect_get_vec_def_for_operand (ops
[!reduc_index
],
5102 vec_oprnds0
.quick_push (loop_vec_def0
);
5103 if (op_type
== ternary_op
)
5105 loop_vec_def1
= vect_get_vec_def_for_operand (op1
, stmt
,
5107 vec_oprnds1
.quick_push (loop_vec_def1
);
5115 enum vect_def_type dt
;
5119 vect_is_simple_use (ops
[!reduc_index
], stmt
, loop_vinfo
, NULL
,
5120 &dummy_stmt
, &dummy
, &dt
);
5121 loop_vec_def0
= vect_get_vec_def_for_stmt_copy (dt
,
5123 vec_oprnds0
[0] = loop_vec_def0
;
5124 if (op_type
== ternary_op
)
5126 vect_is_simple_use (op1
, stmt
, loop_vinfo
, NULL
, &dummy_stmt
,
5128 loop_vec_def1
= vect_get_vec_def_for_stmt_copy (dt
,
5130 vec_oprnds1
[0] = loop_vec_def1
;
5134 if (single_defuse_cycle
)
5135 reduc_def
= gimple_assign_lhs (new_stmt
);
5137 STMT_VINFO_RELATED_STMT (prev_phi_info
) = new_phi
;
5140 FOR_EACH_VEC_ELT (vec_oprnds0
, i
, def0
)
5143 reduc_def
= PHI_RESULT (phis
[i
]);
5146 if (!single_defuse_cycle
|| j
== 0)
5147 reduc_def
= PHI_RESULT (new_phi
);
5150 def1
= ((op_type
== ternary_op
)
5151 ? vec_oprnds1
[i
] : NULL
);
5152 if (op_type
== binary_op
)
5154 if (reduc_index
== 0)
5155 expr
= build2 (code
, vectype_out
, reduc_def
, def0
);
5157 expr
= build2 (code
, vectype_out
, def0
, reduc_def
);
5161 if (reduc_index
== 0)
5162 expr
= build3 (code
, vectype_out
, reduc_def
, def0
, def1
);
5165 if (reduc_index
== 1)
5166 expr
= build3 (code
, vectype_out
, def0
, reduc_def
, def1
);
5168 expr
= build3 (code
, vectype_out
, def0
, def1
, reduc_def
);
5172 new_stmt
= gimple_build_assign (vec_dest
, expr
);
5173 new_temp
= make_ssa_name (vec_dest
, new_stmt
);
5174 gimple_assign_set_lhs (new_stmt
, new_temp
);
5175 vect_finish_stmt_generation (stmt
, new_stmt
, gsi
);
5179 SLP_TREE_VEC_STMTS (slp_node
).quick_push (new_stmt
);
5180 vect_defs
.quick_push (new_temp
);
5183 vect_defs
[0] = new_temp
;
5190 STMT_VINFO_VEC_STMT (stmt_info
) = *vec_stmt
= new_stmt
;
5192 STMT_VINFO_RELATED_STMT (prev_stmt_info
) = new_stmt
;
5194 prev_stmt_info
= vinfo_for_stmt (new_stmt
);
5195 prev_phi_info
= vinfo_for_stmt (new_phi
);
5198 /* Finalize the reduction-phi (set its arguments) and create the
5199 epilog reduction code. */
5200 if ((!single_defuse_cycle
|| code
== COND_EXPR
) && !slp_node
)
5202 new_temp
= gimple_assign_lhs (*vec_stmt
);
5203 vect_defs
[0] = new_temp
;
5206 vect_create_epilog_for_reduction (vect_defs
, stmt
, epilog_copies
,
5207 epilog_reduc_code
, phis
, reduc_index
,
5208 double_reduc
, slp_node
);
5211 vect_defs
.release ();
5212 vec_oprnds0
.release ();
5213 vec_oprnds1
.release ();
5218 /* Function vect_min_worthwhile_factor.
5220 For a loop where we could vectorize the operation indicated by CODE,
5221 return the minimum vectorization factor that makes it worthwhile
5222 to use generic vectors. */
5224 vect_min_worthwhile_factor (enum tree_code code
)
5245 /* Function vectorizable_induction
5247 Check if PHI performs an induction computation that can be vectorized.
5248 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
5249 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
5250 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5253 vectorizable_induction (gimple phi
, gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
5256 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
5257 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
5258 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
5259 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5260 int nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
5261 int ncopies
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) / nunits
;
5264 gcc_assert (ncopies
>= 1);
5265 /* FORNOW. These restrictions should be relaxed. */
5266 if (nested_in_vect_loop_p (loop
, phi
))
5268 imm_use_iterator imm_iter
;
5269 use_operand_p use_p
;
5276 if (dump_enabled_p ())
5277 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5278 "multiple types in nested loop.");
5283 latch_e
= loop_latch_edge (loop
->inner
);
5284 loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
5285 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
5287 if (!flow_bb_inside_loop_p (loop
->inner
,
5288 gimple_bb (USE_STMT (use_p
))))
5290 exit_phi
= USE_STMT (use_p
);
5296 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
5297 if (!(STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
5298 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
)))
5300 if (dump_enabled_p ())
5301 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5302 "inner-loop induction only used outside "
5303 "of the outer vectorized loop.");
5309 if (!STMT_VINFO_RELEVANT_P (stmt_info
))
5312 /* FORNOW: SLP not supported. */
5313 if (STMT_SLP_TYPE (stmt_info
))
5316 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
);
5318 if (gimple_code (phi
) != GIMPLE_PHI
)
5321 if (!vec_stmt
) /* transformation not required. */
5323 STMT_VINFO_TYPE (stmt_info
) = induc_vec_info_type
;
5324 if (dump_enabled_p ())
5325 dump_printf_loc (MSG_NOTE
, vect_location
,
5326 "=== vectorizable_induction ===");
5327 vect_model_induction_cost (stmt_info
, ncopies
);
5333 if (dump_enabled_p ())
5334 dump_printf_loc (MSG_NOTE
, vect_location
, "transform induction phi.");
5336 vec_def
= get_initial_def_for_induction (phi
);
5337 *vec_stmt
= SSA_NAME_DEF_STMT (vec_def
);
5341 /* Function vectorizable_live_operation.
5343 STMT computes a value that is used outside the loop. Check if
5344 it can be supported. */
5347 vectorizable_live_operation (gimple stmt
,
5348 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
5349 gimple
*vec_stmt ATTRIBUTE_UNUSED
)
5351 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
5352 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
5353 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5359 enum vect_def_type dt
;
5360 enum tree_code code
;
5361 enum gimple_rhs_class rhs_class
;
5363 gcc_assert (STMT_VINFO_LIVE_P (stmt_info
));
5365 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_reduction_def
)
5368 if (!is_gimple_assign (stmt
))
5371 if (TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
5374 /* FORNOW. CHECKME. */
5375 if (nested_in_vect_loop_p (loop
, stmt
))
5378 code
= gimple_assign_rhs_code (stmt
);
5379 op_type
= TREE_CODE_LENGTH (code
);
5380 rhs_class
= get_gimple_rhs_class (code
);
5381 gcc_assert (rhs_class
!= GIMPLE_UNARY_RHS
|| op_type
== unary_op
);
5382 gcc_assert (rhs_class
!= GIMPLE_BINARY_RHS
|| op_type
== binary_op
);
5384 /* FORNOW: support only if all uses are invariant. This means
5385 that the scalar operations can remain in place, unvectorized.
5386 The original last scalar value that they compute will be used. */
5388 for (i
= 0; i
< op_type
; i
++)
5390 if (rhs_class
== GIMPLE_SINGLE_RHS
)
5391 op
= TREE_OPERAND (gimple_op (stmt
, 1), i
);
5393 op
= gimple_op (stmt
, i
+ 1);
5395 && !vect_is_simple_use (op
, stmt
, loop_vinfo
, NULL
, &def_stmt
, &def
,
5398 if (dump_enabled_p ())
5399 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5404 if (dt
!= vect_external_def
&& dt
!= vect_constant_def
)
5408 /* No transformation is required for the cases we currently support. */
5412 /* Kill any debug uses outside LOOP of SSA names defined in STMT. */
5415 vect_loop_kill_debug_uses (struct loop
*loop
, gimple stmt
)
5417 ssa_op_iter op_iter
;
5418 imm_use_iterator imm_iter
;
5419 def_operand_p def_p
;
5422 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
5424 FOR_EACH_IMM_USE_STMT (ustmt
, imm_iter
, DEF_FROM_PTR (def_p
))
5428 if (!is_gimple_debug (ustmt
))
5431 bb
= gimple_bb (ustmt
);
5433 if (!flow_bb_inside_loop_p (loop
, bb
))
5435 if (gimple_debug_bind_p (ustmt
))
5437 if (dump_enabled_p ())
5438 dump_printf_loc (MSG_NOTE
, vect_location
,
5439 "killing debug use");
5441 gimple_debug_bind_reset_value (ustmt
);
5442 update_stmt (ustmt
);
5451 /* Function vect_transform_loop.
5453 The analysis phase has determined that the loop is vectorizable.
5454 Vectorize the loop - created vectorized stmts to replace the scalar
5455 stmts in the loop, and update the loop exit condition. */
5458 vect_transform_loop (loop_vec_info loop_vinfo
)
5460 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5461 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
5462 int nbbs
= loop
->num_nodes
;
5463 gimple_stmt_iterator si
;
5466 int vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
5468 bool slp_scheduled
= false;
5469 unsigned int nunits
;
5470 gimple stmt
, pattern_stmt
;
5471 gimple_seq pattern_def_seq
= NULL
;
5472 gimple_stmt_iterator pattern_def_si
= gsi_none ();
5473 bool transform_pattern_stmt
= false;
5474 bool check_profitability
= false;
5476 /* Record number of iterations before we started tampering with the profile. */
5477 gcov_type expected_iterations
= expected_loop_iterations_unbounded (loop
);
5479 if (dump_enabled_p ())
5480 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vec_transform_loop ===");
5482 /* If profile is inprecise, we have chance to fix it up. */
5483 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
5484 expected_iterations
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
5486 /* Use the more conservative vectorization threshold. If the number
5487 of iterations is constant assume the cost check has been performed
5488 by our caller. If the threshold makes all loops profitable that
5489 run at least the vectorization factor number of times checking
5490 is pointless, too. */
5491 th
= ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND
)
5492 * LOOP_VINFO_VECT_FACTOR (loop_vinfo
)) - 1);
5493 th
= MAX (th
, LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo
));
5494 if (th
>= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) - 1
5495 && !LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
5497 if (dump_enabled_p ())
5498 dump_printf_loc (MSG_NOTE
, vect_location
,
5499 "Profitability threshold is %d loop iterations.", th
);
5500 check_profitability
= true;
5503 /* Peel the loop if there are data refs with unknown alignment.
5504 Only one data ref with unknown store is allowed. */
5506 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
))
5508 vect_do_peeling_for_alignment (loop_vinfo
, th
, check_profitability
);
5509 check_profitability
= false;
5512 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
5513 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
5515 vect_loop_versioning (loop_vinfo
, th
, check_profitability
);
5516 check_profitability
= false;
5519 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
5520 compile time constant), or it is a constant that doesn't divide by the
5521 vectorization factor, then an epilog loop needs to be created.
5522 We therefore duplicate the loop: the original loop will be vectorized,
5523 and will compute the first (n/VF) iterations. The second copy of the loop
5524 will remain scalar and will compute the remaining (n%VF) iterations.
5525 (VF is the vectorization factor). */
5527 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
5528 || (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
5529 && LOOP_VINFO_INT_NITERS (loop_vinfo
) % vectorization_factor
!= 0)
5530 || LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
))
5531 vect_do_peeling_for_loop_bound (loop_vinfo
, &ratio
,
5532 th
, check_profitability
);
5534 ratio
= build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo
)),
5535 LOOP_VINFO_INT_NITERS (loop_vinfo
) / vectorization_factor
);
5537 /* 1) Make sure the loop header has exactly two entries
5538 2) Make sure we have a preheader basic block. */
5540 gcc_assert (EDGE_COUNT (loop
->header
->preds
) == 2);
5542 split_edge (loop_preheader_edge (loop
));
5544 /* FORNOW: the vectorizer supports only loops which body consist
5545 of one basic block (header + empty latch). When the vectorizer will
5546 support more involved loop forms, the order by which the BBs are
5547 traversed need to be reconsidered. */
5549 for (i
= 0; i
< nbbs
; i
++)
5551 basic_block bb
= bbs
[i
];
5552 stmt_vec_info stmt_info
;
5555 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
5557 phi
= gsi_stmt (si
);
5558 if (dump_enabled_p ())
5560 dump_printf_loc (MSG_NOTE
, vect_location
,
5561 "------>vectorizing phi: ");
5562 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
5564 stmt_info
= vinfo_for_stmt (phi
);
5568 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
5569 vect_loop_kill_debug_uses (loop
, phi
);
5571 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
5572 && !STMT_VINFO_LIVE_P (stmt_info
))
5575 if ((TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
))
5576 != (unsigned HOST_WIDE_INT
) vectorization_factor
)
5577 && dump_enabled_p ())
5578 dump_printf_loc (MSG_NOTE
, vect_location
, "multiple-types.");
5580 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
5582 if (dump_enabled_p ())
5583 dump_printf_loc (MSG_NOTE
, vect_location
, "transform phi.");
5584 vect_transform_stmt (phi
, NULL
, NULL
, NULL
, NULL
);
5588 pattern_stmt
= NULL
;
5589 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
) || transform_pattern_stmt
;)
5593 if (transform_pattern_stmt
)
5594 stmt
= pattern_stmt
;
5596 stmt
= gsi_stmt (si
);
5598 if (dump_enabled_p ())
5600 dump_printf_loc (MSG_NOTE
, vect_location
,
5601 "------>vectorizing statement: ");
5602 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
5605 stmt_info
= vinfo_for_stmt (stmt
);
5607 /* vector stmts created in the outer-loop during vectorization of
5608 stmts in an inner-loop may not have a stmt_info, and do not
5609 need to be vectorized. */
5616 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
5617 vect_loop_kill_debug_uses (loop
, stmt
);
5619 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
5620 && !STMT_VINFO_LIVE_P (stmt_info
))
5622 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
5623 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
5624 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
5625 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
5627 stmt
= pattern_stmt
;
5628 stmt_info
= vinfo_for_stmt (stmt
);
5636 else if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
5637 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
5638 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
5639 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
5640 transform_pattern_stmt
= true;
5642 /* If pattern statement has def stmts, vectorize them too. */
5643 if (is_pattern_stmt_p (stmt_info
))
5645 if (pattern_def_seq
== NULL
)
5647 pattern_def_seq
= STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
);
5648 pattern_def_si
= gsi_start (pattern_def_seq
);
5650 else if (!gsi_end_p (pattern_def_si
))
5651 gsi_next (&pattern_def_si
);
5652 if (pattern_def_seq
!= NULL
)
5654 gimple pattern_def_stmt
= NULL
;
5655 stmt_vec_info pattern_def_stmt_info
= NULL
;
5657 while (!gsi_end_p (pattern_def_si
))
5659 pattern_def_stmt
= gsi_stmt (pattern_def_si
);
5660 pattern_def_stmt_info
5661 = vinfo_for_stmt (pattern_def_stmt
);
5662 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info
)
5663 || STMT_VINFO_LIVE_P (pattern_def_stmt_info
))
5665 gsi_next (&pattern_def_si
);
5668 if (!gsi_end_p (pattern_def_si
))
5670 if (dump_enabled_p ())
5672 dump_printf_loc (MSG_NOTE
, vect_location
,
5673 "==> vectorizing pattern def "
5675 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
5676 pattern_def_stmt
, 0);
5679 stmt
= pattern_def_stmt
;
5680 stmt_info
= pattern_def_stmt_info
;
5684 pattern_def_si
= gsi_none ();
5685 transform_pattern_stmt
= false;
5689 transform_pattern_stmt
= false;
5692 gcc_assert (STMT_VINFO_VECTYPE (stmt_info
));
5693 nunits
= (unsigned int) TYPE_VECTOR_SUBPARTS (
5694 STMT_VINFO_VECTYPE (stmt_info
));
5695 if (!STMT_SLP_TYPE (stmt_info
)
5696 && nunits
!= (unsigned int) vectorization_factor
5697 && dump_enabled_p ())
5698 /* For SLP VF is set according to unrolling factor, and not to
5699 vector size, hence for SLP this print is not valid. */
5700 dump_printf_loc (MSG_NOTE
, vect_location
,
5703 /* SLP. Schedule all the SLP instances when the first SLP stmt is
5705 if (STMT_SLP_TYPE (stmt_info
))
5709 slp_scheduled
= true;
5711 if (dump_enabled_p ())
5712 dump_printf_loc (MSG_NOTE
, vect_location
,
5713 "=== scheduling SLP instances ===");
5715 vect_schedule_slp (loop_vinfo
, NULL
);
5718 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
5719 if (!vinfo_for_stmt (stmt
) || PURE_SLP_STMT (stmt_info
))
5721 if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
5723 pattern_def_seq
= NULL
;
5730 /* -------- vectorize statement ------------ */
5731 if (dump_enabled_p ())
5732 dump_printf_loc (MSG_NOTE
, vect_location
, "transform statement.");
5734 grouped_store
= false;
5735 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, NULL
, NULL
);
5738 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
5740 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
5741 interleaving chain was completed - free all the stores in
5744 vect_remove_stores (GROUP_FIRST_ELEMENT (stmt_info
));
5749 /* Free the attached stmt_vec_info and remove the stmt. */
5750 gimple store
= gsi_stmt (si
);
5751 free_stmt_vec_info (store
);
5752 unlink_stmt_vdef (store
);
5753 gsi_remove (&si
, true);
5754 release_defs (store
);
5759 if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
5761 pattern_def_seq
= NULL
;
5767 slpeel_make_loop_iterate_ntimes (loop
, ratio
);
5769 /* Reduce loop iterations by the vectorization factor. */
5770 scale_loop_profile (loop
, GCOV_COMPUTE_SCALE (1, vectorization_factor
),
5771 expected_iterations
/ vectorization_factor
);
5772 loop
->nb_iterations_upper_bound
5773 = loop
->nb_iterations_upper_bound
.udiv (double_int::from_uhwi (vectorization_factor
),
5775 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
5776 && loop
->nb_iterations_upper_bound
!= double_int_zero
)
5777 loop
->nb_iterations_upper_bound
= loop
->nb_iterations_upper_bound
- double_int_one
;
5778 if (loop
->any_estimate
)
5780 loop
->nb_iterations_estimate
5781 = loop
->nb_iterations_estimate
.udiv (double_int::from_uhwi (vectorization_factor
),
5783 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
5784 && loop
->nb_iterations_estimate
!= double_int_zero
)
5785 loop
->nb_iterations_estimate
= loop
->nb_iterations_estimate
- double_int_one
;
5788 if (dump_enabled_p ())
5789 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
, "LOOP VECTORIZED.");
5790 if (loop
->inner
&& dump_enabled_p ())
5791 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
5792 "OUTER LOOP VECTORIZED.");