2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012,
3 2013 Free Software Foundation, Inc.
4 Contributed by Dorit Naishlos <dorit@il.ibm.com> and
5 Ira Rosen <irar@il.ibm.com>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
30 #include "basic-block.h"
31 #include "gimple-pretty-print.h"
32 #include "tree-flow.h"
33 #include "tree-pass.h"
39 #include "diagnostic-core.h"
40 #include "tree-chrec.h"
41 #include "tree-scalar-evolution.h"
42 #include "tree-vectorizer.h"
45 /* Loop Vectorization Pass.
47 This pass tries to vectorize loops.
49 For example, the vectorizer transforms the following simple loop:
51 short a[N]; short b[N]; short c[N]; int i;
57 as if it was manually vectorized by rewriting the source code into:
59 typedef int __attribute__((mode(V8HI))) v8hi;
60 short a[N]; short b[N]; short c[N]; int i;
61 v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
64 for (i=0; i<N/8; i++){
71 The main entry to this pass is vectorize_loops(), in which
72 the vectorizer applies a set of analyses on a given set of loops,
73 followed by the actual vectorization transformation for the loops that
74 had successfully passed the analysis phase.
75 Throughout this pass we make a distinction between two types of
76 data: scalars (which are represented by SSA_NAMES), and memory references
77 ("data-refs"). These two types of data require different handling both
78 during analysis and transformation. The types of data-refs that the
79 vectorizer currently supports are ARRAY_REFS which base is an array DECL
80 (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
81 accesses are required to have a simple (consecutive) access pattern.
85 The driver for the analysis phase is vect_analyze_loop().
86 It applies a set of analyses, some of which rely on the scalar evolution
87 analyzer (scev) developed by Sebastian Pop.
89 During the analysis phase the vectorizer records some information
90 per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
91 loop, as well as general information about the loop as a whole, which is
92 recorded in a "loop_vec_info" struct attached to each loop.
96 The loop transformation phase scans all the stmts in the loop, and
97 creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
98 the loop that needs to be vectorized. It inserts the vector code sequence
99 just before the scalar stmt S, and records a pointer to the vector code
100 in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
101 attached to S). This pointer will be used for the vectorization of following
102 stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
103 otherwise, we rely on dead code elimination for removing it.
105 For example, say stmt S1 was vectorized into stmt VS1:
108 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
111 To vectorize stmt S2, the vectorizer first finds the stmt that defines
112 the operand 'b' (S1), and gets the relevant vector def 'vb' from the
113 vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
114 resulting sequence would be:
117 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
119 S2: a = b; STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
121 Operands that are not SSA_NAMEs, are data-refs that appear in
122 load/store operations (like 'x[i]' in S1), and are handled differently.
126 Currently the only target specific information that is used is the
127 size of the vector (in bytes) - "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD".
128 Targets that can support different sizes of vectors, for now will need
129 to specify one value for "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD". More
130 flexibility will be added in the future.
132 Since we only vectorize operations which vector form can be
133 expressed using existing tree codes, to verify that an operation is
134 supported, the vectorizer checks the relevant optab at the relevant
135 machine_mode (e.g, optab_handler (add_optab, V8HImode)). If
136 the value found is CODE_FOR_nothing, then there's no target support, and
137 we can't vectorize the stmt.
139 For additional information on this project see:
140 http://gcc.gnu.org/projects/tree-ssa/vectorization.html
143 static void vect_estimate_min_profitable_iters (loop_vec_info
, int *, int *);
145 /* Function vect_determine_vectorization_factor
147 Determine the vectorization factor (VF). VF is the number of data elements
148 that are operated upon in parallel in a single iteration of the vectorized
149 loop. For example, when vectorizing a loop that operates on 4byte elements,
150 on a target with vector size (VS) 16byte, the VF is set to 4, since 4
151 elements can fit in a single vector register.
153 We currently support vectorization of loops in which all types operated upon
154 are of the same size. Therefore this function currently sets VF according to
155 the size of the types operated upon, and fails if there are multiple sizes
158 VF is also the factor by which the loop iterations are strip-mined, e.g.:
165 for (i=0; i<N; i+=VF){
166 a[i:VF] = b[i:VF] + c[i:VF];
171 vect_determine_vectorization_factor (loop_vec_info loop_vinfo
)
173 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
174 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
175 int nbbs
= loop
->num_nodes
;
176 gimple_stmt_iterator si
;
177 unsigned int vectorization_factor
= 0;
182 stmt_vec_info stmt_info
;
185 gimple stmt
, pattern_stmt
= NULL
;
186 gimple_seq pattern_def_seq
= NULL
;
187 gimple_stmt_iterator pattern_def_si
= gsi_none ();
188 bool analyze_pattern_stmt
= false;
190 if (dump_enabled_p ())
191 dump_printf_loc (MSG_NOTE
, vect_location
,
192 "=== vect_determine_vectorization_factor ===");
194 for (i
= 0; i
< nbbs
; i
++)
196 basic_block bb
= bbs
[i
];
198 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
201 stmt_info
= vinfo_for_stmt (phi
);
202 if (dump_enabled_p ())
204 dump_printf_loc (MSG_NOTE
, vect_location
, "==> examining phi: ");
205 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
208 gcc_assert (stmt_info
);
210 if (STMT_VINFO_RELEVANT_P (stmt_info
))
212 gcc_assert (!STMT_VINFO_VECTYPE (stmt_info
));
213 scalar_type
= TREE_TYPE (PHI_RESULT (phi
));
215 if (dump_enabled_p ())
217 dump_printf_loc (MSG_NOTE
, vect_location
,
218 "get vectype for scalar type: ");
219 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
222 vectype
= get_vectype_for_scalar_type (scalar_type
);
225 if (dump_enabled_p ())
227 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
228 "not vectorized: unsupported "
230 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
235 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
237 if (dump_enabled_p ())
239 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
240 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vectype
);
243 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
244 if (dump_enabled_p ())
245 dump_printf_loc (MSG_NOTE
, vect_location
, "nunits = %d", nunits
);
247 if (!vectorization_factor
248 || (nunits
> vectorization_factor
))
249 vectorization_factor
= nunits
;
253 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
) || analyze_pattern_stmt
;)
257 if (analyze_pattern_stmt
)
260 stmt
= gsi_stmt (si
);
262 stmt_info
= vinfo_for_stmt (stmt
);
264 if (dump_enabled_p ())
266 dump_printf_loc (MSG_NOTE
, vect_location
,
267 "==> examining statement: ");
268 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
271 gcc_assert (stmt_info
);
273 /* Skip stmts which do not need to be vectorized. */
274 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
275 && !STMT_VINFO_LIVE_P (stmt_info
))
277 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
278 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
279 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
280 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
283 stmt_info
= vinfo_for_stmt (pattern_stmt
);
284 if (dump_enabled_p ())
286 dump_printf_loc (MSG_NOTE
, vect_location
,
287 "==> examining pattern statement: ");
288 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
293 if (dump_enabled_p ())
294 dump_printf_loc (MSG_NOTE
, vect_location
, "skip.");
299 else if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
300 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
301 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
302 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
303 analyze_pattern_stmt
= true;
305 /* If a pattern statement has def stmts, analyze them too. */
306 if (is_pattern_stmt_p (stmt_info
))
308 if (pattern_def_seq
== NULL
)
310 pattern_def_seq
= STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
);
311 pattern_def_si
= gsi_start (pattern_def_seq
);
313 else if (!gsi_end_p (pattern_def_si
))
314 gsi_next (&pattern_def_si
);
315 if (pattern_def_seq
!= NULL
)
317 gimple pattern_def_stmt
= NULL
;
318 stmt_vec_info pattern_def_stmt_info
= NULL
;
320 while (!gsi_end_p (pattern_def_si
))
322 pattern_def_stmt
= gsi_stmt (pattern_def_si
);
323 pattern_def_stmt_info
324 = vinfo_for_stmt (pattern_def_stmt
);
325 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info
)
326 || STMT_VINFO_LIVE_P (pattern_def_stmt_info
))
328 gsi_next (&pattern_def_si
);
331 if (!gsi_end_p (pattern_def_si
))
333 if (dump_enabled_p ())
335 dump_printf_loc (MSG_NOTE
, vect_location
,
336 "==> examining pattern def stmt: ");
337 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
338 pattern_def_stmt
, 0);
341 stmt
= pattern_def_stmt
;
342 stmt_info
= pattern_def_stmt_info
;
346 pattern_def_si
= gsi_none ();
347 analyze_pattern_stmt
= false;
351 analyze_pattern_stmt
= false;
354 if (gimple_get_lhs (stmt
) == NULL_TREE
)
356 if (dump_enabled_p ())
358 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
359 "not vectorized: irregular stmt.");
360 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
,
366 if (VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt
))))
368 if (dump_enabled_p ())
370 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
371 "not vectorized: vector stmt in loop:");
372 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
377 if (STMT_VINFO_VECTYPE (stmt_info
))
379 /* The only case when a vectype had been already set is for stmts
380 that contain a dataref, or for "pattern-stmts" (stmts
381 generated by the vectorizer to represent/replace a certain
383 gcc_assert (STMT_VINFO_DATA_REF (stmt_info
)
384 || is_pattern_stmt_p (stmt_info
)
385 || !gsi_end_p (pattern_def_si
));
386 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
390 gcc_assert (!STMT_VINFO_DATA_REF (stmt_info
));
391 scalar_type
= TREE_TYPE (gimple_get_lhs (stmt
));
392 if (dump_enabled_p ())
394 dump_printf_loc (MSG_NOTE
, vect_location
,
395 "get vectype for scalar type: ");
396 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
398 vectype
= get_vectype_for_scalar_type (scalar_type
);
401 if (dump_enabled_p ())
403 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
404 "not vectorized: unsupported "
406 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
412 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
415 /* The vectorization factor is according to the smallest
416 scalar type (or the largest vector size, but we only
417 support one vector size per loop). */
418 scalar_type
= vect_get_smallest_scalar_type (stmt
, &dummy
,
420 if (dump_enabled_p ())
422 dump_printf_loc (MSG_NOTE
, vect_location
,
423 "get vectype for scalar type: ");
424 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, scalar_type
);
426 vf_vectype
= get_vectype_for_scalar_type (scalar_type
);
429 if (dump_enabled_p ())
431 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
432 "not vectorized: unsupported data-type ");
433 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
439 if ((GET_MODE_SIZE (TYPE_MODE (vectype
))
440 != GET_MODE_SIZE (TYPE_MODE (vf_vectype
))))
442 if (dump_enabled_p ())
444 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
445 "not vectorized: different sized vector "
446 "types in statement, ");
447 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
449 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
450 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
456 if (dump_enabled_p ())
458 dump_printf_loc (MSG_NOTE
, vect_location
, "vectype: ");
459 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, vf_vectype
);
462 nunits
= TYPE_VECTOR_SUBPARTS (vf_vectype
);
463 if (dump_enabled_p ())
464 dump_printf_loc (MSG_NOTE
, vect_location
, "nunits = %d", nunits
);
465 if (!vectorization_factor
466 || (nunits
> vectorization_factor
))
467 vectorization_factor
= nunits
;
469 if (!analyze_pattern_stmt
&& gsi_end_p (pattern_def_si
))
471 pattern_def_seq
= NULL
;
477 /* TODO: Analyze cost. Decide if worth while to vectorize. */
478 if (dump_enabled_p ())
479 dump_printf_loc (MSG_NOTE
, vect_location
, "vectorization factor = %d",
480 vectorization_factor
);
481 if (vectorization_factor
<= 1)
483 if (dump_enabled_p ())
484 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
485 "not vectorized: unsupported data-type");
488 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
494 /* Function vect_is_simple_iv_evolution.
496 FORNOW: A simple evolution of an induction variables in the loop is
497 considered a polynomial evolution with constant step. */
500 vect_is_simple_iv_evolution (unsigned loop_nb
, tree access_fn
, tree
* init
,
505 tree evolution_part
= evolution_part_in_loop_num (access_fn
, loop_nb
);
507 /* When there is no evolution in this loop, the evolution function
509 if (evolution_part
== NULL_TREE
)
512 /* When the evolution is a polynomial of degree >= 2
513 the evolution function is not "simple". */
514 if (tree_is_chrec (evolution_part
))
517 step_expr
= evolution_part
;
518 init_expr
= unshare_expr (initial_condition_in_loop_num (access_fn
, loop_nb
));
520 if (dump_enabled_p ())
522 dump_printf_loc (MSG_NOTE
, vect_location
, "step: ");
523 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, step_expr
);
524 dump_printf (MSG_NOTE
, ", init: ");
525 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, init_expr
);
531 if (TREE_CODE (step_expr
) != INTEGER_CST
)
533 if (dump_enabled_p ())
534 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
542 /* Function vect_analyze_scalar_cycles_1.
544 Examine the cross iteration def-use cycles of scalar variables
545 in LOOP. LOOP_VINFO represents the loop that is now being
546 considered for vectorization (can be LOOP, or an outer-loop
550 vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo
, struct loop
*loop
)
552 basic_block bb
= loop
->header
;
554 vec
<gimple
> worklist
;
555 worklist
.create (64);
556 gimple_stmt_iterator gsi
;
559 if (dump_enabled_p ())
560 dump_printf_loc (MSG_NOTE
, vect_location
,
561 "=== vect_analyze_scalar_cycles ===");
563 /* First - identify all inductions. Reduction detection assumes that all the
564 inductions have been identified, therefore, this order must not be
566 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
568 gimple phi
= gsi_stmt (gsi
);
569 tree access_fn
= NULL
;
570 tree def
= PHI_RESULT (phi
);
571 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (phi
);
573 if (dump_enabled_p ())
575 dump_printf_loc (MSG_NOTE
, vect_location
, "Analyze phi: ");
576 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
579 /* Skip virtual phi's. The data dependences that are associated with
580 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
581 if (virtual_operand_p (def
))
584 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_unknown_def_type
;
586 /* Analyze the evolution function. */
587 access_fn
= analyze_scalar_evolution (loop
, def
);
590 STRIP_NOPS (access_fn
);
591 if (dump_enabled_p ())
593 dump_printf_loc (MSG_NOTE
, vect_location
,
594 "Access function of PHI: ");
595 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, access_fn
);
597 STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
)
598 = evolution_part_in_loop_num (access_fn
, loop
->num
);
602 || !vect_is_simple_iv_evolution (loop
->num
, access_fn
, &dumy
, &dumy
))
604 worklist
.safe_push (phi
);
608 gcc_assert (STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
) != NULL_TREE
);
610 if (dump_enabled_p ())
611 dump_printf_loc (MSG_NOTE
, vect_location
, "Detected induction.");
612 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_induction_def
;
616 /* Second - identify all reductions and nested cycles. */
617 while (worklist
.length () > 0)
619 gimple phi
= worklist
.pop ();
620 tree def
= PHI_RESULT (phi
);
621 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (phi
);
625 if (dump_enabled_p ())
627 dump_printf_loc (MSG_NOTE
, vect_location
, "Analyze phi: ");
628 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
631 gcc_assert (!virtual_operand_p (def
)
632 && STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_unknown_def_type
);
634 nested_cycle
= (loop
!= LOOP_VINFO_LOOP (loop_vinfo
));
635 reduc_stmt
= vect_force_simple_reduction (loop_vinfo
, phi
, !nested_cycle
,
641 if (dump_enabled_p ())
642 dump_printf_loc (MSG_NOTE
, vect_location
,
643 "Detected double reduction.");
645 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_double_reduction_def
;
646 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
647 vect_double_reduction_def
;
653 if (dump_enabled_p ())
654 dump_printf_loc (MSG_NOTE
, vect_location
,
655 "Detected vectorizable nested cycle.");
657 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_nested_cycle
;
658 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
663 if (dump_enabled_p ())
664 dump_printf_loc (MSG_NOTE
, vect_location
,
665 "Detected reduction.");
667 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_reduction_def
;
668 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
670 /* Store the reduction cycles for possible vectorization in
672 LOOP_VINFO_REDUCTIONS (loop_vinfo
).safe_push (reduc_stmt
);
677 if (dump_enabled_p ())
678 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
679 "Unknown def-use cycle pattern.");
686 /* Function vect_analyze_scalar_cycles.
688 Examine the cross iteration def-use cycles of scalar variables, by
689 analyzing the loop-header PHIs of scalar variables. Classify each
690 cycle as one of the following: invariant, induction, reduction, unknown.
691 We do that for the loop represented by LOOP_VINFO, and also to its
692 inner-loop, if exists.
693 Examples for scalar cycles:
708 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo
)
710 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
712 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
);
714 /* When vectorizing an outer-loop, the inner-loop is executed sequentially.
715 Reductions in such inner-loop therefore have different properties than
716 the reductions in the nest that gets vectorized:
717 1. When vectorized, they are executed in the same order as in the original
718 scalar loop, so we can't change the order of computation when
720 2. FIXME: Inner-loop reductions can be used in the inner-loop, so the
721 current checks are too strict. */
724 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
->inner
);
727 /* Function vect_get_loop_niters.
729 Determine how many iterations the loop is executed.
730 If an expression that represents the number of iterations
731 can be constructed, place it in NUMBER_OF_ITERATIONS.
732 Return the loop exit condition. */
735 vect_get_loop_niters (struct loop
*loop
, tree
*number_of_iterations
)
739 if (dump_enabled_p ())
740 dump_printf_loc (MSG_NOTE
, vect_location
,
741 "=== get_loop_niters ===");
742 niters
= number_of_exit_cond_executions (loop
);
744 if (niters
!= NULL_TREE
745 && niters
!= chrec_dont_know
)
747 *number_of_iterations
= niters
;
749 if (dump_enabled_p ())
751 dump_printf_loc (MSG_NOTE
, vect_location
, "==> get_loop_niters:");
752 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, *number_of_iterations
);
756 return get_loop_exit_condition (loop
);
760 /* Function bb_in_loop_p
762 Used as predicate for dfs order traversal of the loop bbs. */
765 bb_in_loop_p (const_basic_block bb
, const void *data
)
767 const struct loop
*const loop
= (const struct loop
*)data
;
768 if (flow_bb_inside_loop_p (loop
, bb
))
774 /* Function new_loop_vec_info.
776 Create and initialize a new loop_vec_info struct for LOOP, as well as
777 stmt_vec_info structs for all the stmts in LOOP. */
780 new_loop_vec_info (struct loop
*loop
)
784 gimple_stmt_iterator si
;
785 unsigned int i
, nbbs
;
787 res
= (loop_vec_info
) xcalloc (1, sizeof (struct _loop_vec_info
));
788 LOOP_VINFO_LOOP (res
) = loop
;
790 bbs
= get_loop_body (loop
);
792 /* Create/Update stmt_info for all stmts in the loop. */
793 for (i
= 0; i
< loop
->num_nodes
; i
++)
795 basic_block bb
= bbs
[i
];
797 /* BBs in a nested inner-loop will have been already processed (because
798 we will have called vect_analyze_loop_form for any nested inner-loop).
799 Therefore, for stmts in an inner-loop we just want to update the
800 STMT_VINFO_LOOP_VINFO field of their stmt_info to point to the new
801 loop_info of the outer-loop we are currently considering to vectorize
802 (instead of the loop_info of the inner-loop).
803 For stmts in other BBs we need to create a stmt_info from scratch. */
804 if (bb
->loop_father
!= loop
)
807 gcc_assert (loop
->inner
&& bb
->loop_father
== loop
->inner
);
808 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
810 gimple phi
= gsi_stmt (si
);
811 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
812 loop_vec_info inner_loop_vinfo
=
813 STMT_VINFO_LOOP_VINFO (stmt_info
);
814 gcc_assert (loop
->inner
== LOOP_VINFO_LOOP (inner_loop_vinfo
));
815 STMT_VINFO_LOOP_VINFO (stmt_info
) = res
;
817 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
819 gimple stmt
= gsi_stmt (si
);
820 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
821 loop_vec_info inner_loop_vinfo
=
822 STMT_VINFO_LOOP_VINFO (stmt_info
);
823 gcc_assert (loop
->inner
== LOOP_VINFO_LOOP (inner_loop_vinfo
));
824 STMT_VINFO_LOOP_VINFO (stmt_info
) = res
;
829 /* bb in current nest. */
830 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
832 gimple phi
= gsi_stmt (si
);
833 gimple_set_uid (phi
, 0);
834 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, res
, NULL
));
837 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
839 gimple stmt
= gsi_stmt (si
);
840 gimple_set_uid (stmt
, 0);
841 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, res
, NULL
));
846 /* CHECKME: We want to visit all BBs before their successors (except for
847 latch blocks, for which this assertion wouldn't hold). In the simple
848 case of the loop forms we allow, a dfs order of the BBs would the same
849 as reversed postorder traversal, so we are safe. */
852 bbs
= XCNEWVEC (basic_block
, loop
->num_nodes
);
853 nbbs
= dfs_enumerate_from (loop
->header
, 0, bb_in_loop_p
,
854 bbs
, loop
->num_nodes
, loop
);
855 gcc_assert (nbbs
== loop
->num_nodes
);
857 LOOP_VINFO_BBS (res
) = bbs
;
858 LOOP_VINFO_NITERS (res
) = NULL
;
859 LOOP_VINFO_NITERS_UNCHANGED (res
) = NULL
;
860 LOOP_VINFO_COST_MODEL_MIN_ITERS (res
) = 0;
861 LOOP_VINFO_VECTORIZABLE_P (res
) = 0;
862 LOOP_PEELING_FOR_ALIGNMENT (res
) = 0;
863 LOOP_VINFO_VECT_FACTOR (res
) = 0;
864 LOOP_VINFO_LOOP_NEST (res
).create (3);
865 LOOP_VINFO_DATAREFS (res
).create (10);
866 LOOP_VINFO_DDRS (res
).create (10 * 10);
867 LOOP_VINFO_UNALIGNED_DR (res
) = NULL
;
868 LOOP_VINFO_MAY_MISALIGN_STMTS (res
).create (
869 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS
));
870 LOOP_VINFO_MAY_ALIAS_DDRS (res
).create (
871 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS
));
872 LOOP_VINFO_GROUPED_STORES (res
).create (10);
873 LOOP_VINFO_REDUCTIONS (res
).create (10);
874 LOOP_VINFO_REDUCTION_CHAINS (res
).create (10);
875 LOOP_VINFO_SLP_INSTANCES (res
).create (10);
876 LOOP_VINFO_SLP_UNROLLING_FACTOR (res
) = 1;
877 LOOP_VINFO_PEELING_HTAB (res
) = NULL
;
878 LOOP_VINFO_TARGET_COST_DATA (res
) = init_cost (loop
);
879 LOOP_VINFO_PEELING_FOR_GAPS (res
) = false;
880 LOOP_VINFO_OPERANDS_SWAPPED (res
) = false;
886 /* Function destroy_loop_vec_info.
888 Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
889 stmts in the loop. */
892 destroy_loop_vec_info (loop_vec_info loop_vinfo
, bool clean_stmts
)
897 gimple_stmt_iterator si
;
899 vec
<slp_instance
> slp_instances
;
900 slp_instance instance
;
906 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
908 bbs
= LOOP_VINFO_BBS (loop_vinfo
);
909 nbbs
= loop
->num_nodes
;
910 swapped
= LOOP_VINFO_OPERANDS_SWAPPED (loop_vinfo
);
914 free (LOOP_VINFO_BBS (loop_vinfo
));
915 free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo
));
916 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo
));
917 LOOP_VINFO_LOOP_NEST (loop_vinfo
).release ();
918 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).release ();
919 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
).release ();
926 for (j
= 0; j
< nbbs
; j
++)
928 basic_block bb
= bbs
[j
];
929 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
930 free_stmt_vec_info (gsi_stmt (si
));
932 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); )
934 gimple stmt
= gsi_stmt (si
);
936 /* We may have broken canonical form by moving a constant
937 into RHS1 of a commutative op. Fix such occurrences. */
938 if (swapped
&& is_gimple_assign (stmt
))
940 enum tree_code code
= gimple_assign_rhs_code (stmt
);
942 if ((code
== PLUS_EXPR
943 || code
== POINTER_PLUS_EXPR
944 || code
== MULT_EXPR
)
945 && CONSTANT_CLASS_P (gimple_assign_rhs1 (stmt
)))
946 swap_tree_operands (stmt
,
947 gimple_assign_rhs1_ptr (stmt
),
948 gimple_assign_rhs2_ptr (stmt
));
951 /* Free stmt_vec_info. */
952 free_stmt_vec_info (stmt
);
957 free (LOOP_VINFO_BBS (loop_vinfo
));
958 free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo
));
959 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo
));
960 LOOP_VINFO_LOOP_NEST (loop_vinfo
).release ();
961 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).release ();
962 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
).release ();
963 slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
964 FOR_EACH_VEC_ELT (slp_instances
, j
, instance
)
965 vect_free_slp_instance (instance
);
967 LOOP_VINFO_SLP_INSTANCES (loop_vinfo
).release ();
968 LOOP_VINFO_GROUPED_STORES (loop_vinfo
).release ();
969 LOOP_VINFO_REDUCTIONS (loop_vinfo
).release ();
970 LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
).release ();
972 if (LOOP_VINFO_PEELING_HTAB (loop_vinfo
))
973 htab_delete (LOOP_VINFO_PEELING_HTAB (loop_vinfo
));
975 destroy_cost_data (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
));
982 /* Function vect_analyze_loop_1.
984 Apply a set of analyses on LOOP, and create a loop_vec_info struct
985 for it. The different analyses will record information in the
986 loop_vec_info struct. This is a subset of the analyses applied in
987 vect_analyze_loop, to be applied on an inner-loop nested in the loop
988 that is now considered for (outer-loop) vectorization. */
991 vect_analyze_loop_1 (struct loop
*loop
)
993 loop_vec_info loop_vinfo
;
995 if (dump_enabled_p ())
996 dump_printf_loc (MSG_NOTE
, vect_location
,
997 "===== analyze_loop_nest_1 =====");
999 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
1001 loop_vinfo
= vect_analyze_loop_form (loop
);
1004 if (dump_enabled_p ())
1005 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1006 "bad inner-loop form.");
1014 /* Function vect_analyze_loop_form.
1016 Verify that certain CFG restrictions hold, including:
1017 - the loop has a pre-header
1018 - the loop has a single entry and exit
1019 - the loop exit condition is simple enough, and the number of iterations
1020 can be analyzed (a countable loop). */
1023 vect_analyze_loop_form (struct loop
*loop
)
1025 loop_vec_info loop_vinfo
;
1027 tree number_of_iterations
= NULL
;
1028 loop_vec_info inner_loop_vinfo
= NULL
;
1030 if (dump_enabled_p ())
1031 dump_printf_loc (MSG_NOTE
, vect_location
,
1032 "=== vect_analyze_loop_form ===");
1034 /* Different restrictions apply when we are considering an inner-most loop,
1035 vs. an outer (nested) loop.
1036 (FORNOW. May want to relax some of these restrictions in the future). */
1040 /* Inner-most loop. We currently require that the number of BBs is
1041 exactly 2 (the header and latch). Vectorizable inner-most loops
1052 if (loop
->num_nodes
!= 2)
1054 if (dump_enabled_p ())
1055 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1056 "not vectorized: control flow in loop.");
1060 if (empty_block_p (loop
->header
))
1062 if (dump_enabled_p ())
1063 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1064 "not vectorized: empty loop.");
1070 struct loop
*innerloop
= loop
->inner
;
1073 /* Nested loop. We currently require that the loop is doubly-nested,
1074 contains a single inner loop, and the number of BBs is exactly 5.
1075 Vectorizable outer-loops look like this:
1087 The inner-loop has the properties expected of inner-most loops
1088 as described above. */
1090 if ((loop
->inner
)->inner
|| (loop
->inner
)->next
)
1092 if (dump_enabled_p ())
1093 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1094 "not vectorized: multiple nested loops.");
1098 /* Analyze the inner-loop. */
1099 inner_loop_vinfo
= vect_analyze_loop_1 (loop
->inner
);
1100 if (!inner_loop_vinfo
)
1102 if (dump_enabled_p ())
1103 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1104 "not vectorized: Bad inner loop.");
1108 if (!expr_invariant_in_loop_p (loop
,
1109 LOOP_VINFO_NITERS (inner_loop_vinfo
)))
1111 if (dump_enabled_p ())
1112 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1113 "not vectorized: inner-loop count not invariant.");
1114 destroy_loop_vec_info (inner_loop_vinfo
, true);
1118 if (loop
->num_nodes
!= 5)
1120 if (dump_enabled_p ())
1121 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1122 "not vectorized: control flow in loop.");
1123 destroy_loop_vec_info (inner_loop_vinfo
, true);
1127 gcc_assert (EDGE_COUNT (innerloop
->header
->preds
) == 2);
1128 entryedge
= EDGE_PRED (innerloop
->header
, 0);
1129 if (EDGE_PRED (innerloop
->header
, 0)->src
== innerloop
->latch
)
1130 entryedge
= EDGE_PRED (innerloop
->header
, 1);
1132 if (entryedge
->src
!= loop
->header
1133 || !single_exit (innerloop
)
1134 || single_exit (innerloop
)->dest
!= EDGE_PRED (loop
->latch
, 0)->src
)
1136 if (dump_enabled_p ())
1137 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1138 "not vectorized: unsupported outerloop form.");
1139 destroy_loop_vec_info (inner_loop_vinfo
, true);
1143 if (dump_enabled_p ())
1144 dump_printf_loc (MSG_NOTE
, vect_location
,
1145 "Considering outer-loop vectorization.");
1148 if (!single_exit (loop
)
1149 || EDGE_COUNT (loop
->header
->preds
) != 2)
1151 if (dump_enabled_p ())
1153 if (!single_exit (loop
))
1154 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1155 "not vectorized: multiple exits.");
1156 else if (EDGE_COUNT (loop
->header
->preds
) != 2)
1157 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1158 "not vectorized: too many incoming edges.");
1160 if (inner_loop_vinfo
)
1161 destroy_loop_vec_info (inner_loop_vinfo
, true);
1165 /* We assume that the loop exit condition is at the end of the loop. i.e,
1166 that the loop is represented as a do-while (with a proper if-guard
1167 before the loop if needed), where the loop header contains all the
1168 executable statements, and the latch is empty. */
1169 if (!empty_block_p (loop
->latch
)
1170 || !gimple_seq_empty_p (phi_nodes (loop
->latch
)))
1172 if (dump_enabled_p ())
1173 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1174 "not vectorized: unexpected loop form.");
1175 if (inner_loop_vinfo
)
1176 destroy_loop_vec_info (inner_loop_vinfo
, true);
1180 /* Make sure there exists a single-predecessor exit bb: */
1181 if (!single_pred_p (single_exit (loop
)->dest
))
1183 edge e
= single_exit (loop
);
1184 if (!(e
->flags
& EDGE_ABNORMAL
))
1186 split_loop_exit_edge (e
);
1187 if (dump_enabled_p ())
1188 dump_printf (MSG_NOTE
, "split exit edge.");
1192 if (dump_enabled_p ())
1193 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1194 "not vectorized: abnormal loop exit edge.");
1195 if (inner_loop_vinfo
)
1196 destroy_loop_vec_info (inner_loop_vinfo
, true);
1201 loop_cond
= vect_get_loop_niters (loop
, &number_of_iterations
);
1204 if (dump_enabled_p ())
1205 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1206 "not vectorized: complicated exit condition.");
1207 if (inner_loop_vinfo
)
1208 destroy_loop_vec_info (inner_loop_vinfo
, true);
1212 if (!number_of_iterations
)
1214 if (dump_enabled_p ())
1215 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1216 "not vectorized: number of iterations cannot be "
1218 if (inner_loop_vinfo
)
1219 destroy_loop_vec_info (inner_loop_vinfo
, true);
1223 if (chrec_contains_undetermined (number_of_iterations
))
1225 if (dump_enabled_p ())
1226 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1227 "Infinite number of iterations.");
1228 if (inner_loop_vinfo
)
1229 destroy_loop_vec_info (inner_loop_vinfo
, true);
1233 if (!NITERS_KNOWN_P (number_of_iterations
))
1235 if (dump_enabled_p ())
1237 dump_printf_loc (MSG_NOTE
, vect_location
,
1238 "Symbolic number of iterations is ");
1239 dump_generic_expr (MSG_NOTE
, TDF_DETAILS
, number_of_iterations
);
1242 else if (TREE_INT_CST_LOW (number_of_iterations
) == 0)
1244 if (dump_enabled_p ())
1245 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1246 "not vectorized: number of iterations = 0.");
1247 if (inner_loop_vinfo
)
1248 destroy_loop_vec_info (inner_loop_vinfo
, false);
1252 loop_vinfo
= new_loop_vec_info (loop
);
1253 LOOP_VINFO_NITERS (loop_vinfo
) = number_of_iterations
;
1254 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo
) = number_of_iterations
;
1256 STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond
)) = loop_exit_ctrl_vec_info_type
;
1258 /* CHECKME: May want to keep it around it in the future. */
1259 if (inner_loop_vinfo
)
1260 destroy_loop_vec_info (inner_loop_vinfo
, false);
1262 gcc_assert (!loop
->aux
);
1263 loop
->aux
= loop_vinfo
;
1268 /* Function vect_analyze_loop_operations.
1270 Scan the loop stmts and make sure they are all vectorizable. */
1273 vect_analyze_loop_operations (loop_vec_info loop_vinfo
, bool slp
)
1275 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1276 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1277 int nbbs
= loop
->num_nodes
;
1278 gimple_stmt_iterator si
;
1279 unsigned int vectorization_factor
= 0;
1282 stmt_vec_info stmt_info
;
1283 bool need_to_vectorize
= false;
1284 int min_profitable_iters
;
1285 int min_scalar_loop_bound
;
1287 bool only_slp_in_loop
= true, ok
;
1288 HOST_WIDE_INT max_niter
;
1289 HOST_WIDE_INT estimated_niter
;
1290 int min_profitable_estimate
;
1292 if (dump_enabled_p ())
1293 dump_printf_loc (MSG_NOTE
, vect_location
,
1294 "=== vect_analyze_loop_operations ===");
1296 gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo
));
1297 vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1300 /* If all the stmts in the loop can be SLPed, we perform only SLP, and
1301 vectorization factor of the loop is the unrolling factor required by
1302 the SLP instances. If that unrolling factor is 1, we say, that we
1303 perform pure SLP on loop - cross iteration parallelism is not
1305 for (i
= 0; i
< nbbs
; i
++)
1307 basic_block bb
= bbs
[i
];
1308 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1310 gimple stmt
= gsi_stmt (si
);
1311 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1312 gcc_assert (stmt_info
);
1313 if ((STMT_VINFO_RELEVANT_P (stmt_info
)
1314 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
1315 && !PURE_SLP_STMT (stmt_info
))
1316 /* STMT needs both SLP and loop-based vectorization. */
1317 only_slp_in_loop
= false;
1321 if (only_slp_in_loop
)
1322 vectorization_factor
= LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
);
1324 vectorization_factor
= least_common_multiple (vectorization_factor
,
1325 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
));
1327 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
1328 if (dump_enabled_p ())
1329 dump_printf_loc (MSG_NOTE
, vect_location
,
1330 "Updating vectorization factor to %d ",
1331 vectorization_factor
);
1334 for (i
= 0; i
< nbbs
; i
++)
1336 basic_block bb
= bbs
[i
];
1338 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
1340 phi
= gsi_stmt (si
);
1343 stmt_info
= vinfo_for_stmt (phi
);
1344 if (dump_enabled_p ())
1346 dump_printf_loc (MSG_NOTE
, vect_location
, "examining phi: ");
1347 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
1350 /* Inner-loop loop-closed exit phi in outer-loop vectorization
1351 (i.e., a phi in the tail of the outer-loop). */
1352 if (! is_loop_header_bb_p (bb
))
1354 /* FORNOW: we currently don't support the case that these phis
1355 are not used in the outerloop (unless it is double reduction,
1356 i.e., this phi is vect_reduction_def), cause this case
1357 requires to actually do something here. */
1358 if ((!STMT_VINFO_RELEVANT_P (stmt_info
)
1359 || STMT_VINFO_LIVE_P (stmt_info
))
1360 && STMT_VINFO_DEF_TYPE (stmt_info
)
1361 != vect_double_reduction_def
)
1363 if (dump_enabled_p ())
1364 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1365 "Unsupported loop-closed phi in "
1370 /* If PHI is used in the outer loop, we check that its operand
1371 is defined in the inner loop. */
1372 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1377 if (gimple_phi_num_args (phi
) != 1)
1380 phi_op
= PHI_ARG_DEF (phi
, 0);
1381 if (TREE_CODE (phi_op
) != SSA_NAME
)
1384 op_def_stmt
= SSA_NAME_DEF_STMT (phi_op
);
1386 || !flow_bb_inside_loop_p (loop
, gimple_bb (op_def_stmt
))
1387 || !vinfo_for_stmt (op_def_stmt
))
1390 if (STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1391 != vect_used_in_outer
1392 && STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1393 != vect_used_in_outer_by_reduction
)
1400 gcc_assert (stmt_info
);
1402 if (STMT_VINFO_LIVE_P (stmt_info
))
1404 /* FORNOW: not yet supported. */
1405 if (dump_enabled_p ())
1406 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1407 "not vectorized: value used after loop.");
1411 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
1412 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_induction_def
)
1414 /* A scalar-dependence cycle that we don't support. */
1415 if (dump_enabled_p ())
1416 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1417 "not vectorized: scalar dependence cycle.");
1421 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1423 need_to_vectorize
= true;
1424 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
1425 ok
= vectorizable_induction (phi
, NULL
, NULL
);
1430 if (dump_enabled_p ())
1432 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1433 "not vectorized: relevant phi not "
1435 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, phi
, 0);
1441 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1443 gimple stmt
= gsi_stmt (si
);
1444 if (!vect_analyze_stmt (stmt
, &need_to_vectorize
, NULL
))
1449 /* All operations in the loop are either irrelevant (deal with loop
1450 control, or dead), or only used outside the loop and can be moved
1451 out of the loop (e.g. invariants, inductions). The loop can be
1452 optimized away by scalar optimizations. We're better off not
1453 touching this loop. */
1454 if (!need_to_vectorize
)
1456 if (dump_enabled_p ())
1457 dump_printf_loc (MSG_NOTE
, vect_location
,
1458 "All the computation can be taken out of the loop.");
1459 if (dump_enabled_p ())
1460 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1461 "not vectorized: redundant loop. no profit to "
1466 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
) && dump_enabled_p ())
1467 dump_printf_loc (MSG_NOTE
, vect_location
,
1468 "vectorization_factor = %d, niters = "
1469 HOST_WIDE_INT_PRINT_DEC
, vectorization_factor
,
1470 LOOP_VINFO_INT_NITERS (loop_vinfo
));
1472 if ((LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1473 && (LOOP_VINFO_INT_NITERS (loop_vinfo
) < vectorization_factor
))
1474 || ((max_niter
= max_stmt_executions_int (loop
)) != -1
1475 && (unsigned HOST_WIDE_INT
) max_niter
< vectorization_factor
))
1477 if (dump_enabled_p ())
1478 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1479 "not vectorized: iteration count too small.");
1480 if (dump_enabled_p ())
1481 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1482 "not vectorized: iteration count smaller than "
1483 "vectorization factor.");
1487 /* Analyze cost. Decide if worth while to vectorize. */
1489 /* Once VF is set, SLP costs should be updated since the number of created
1490 vector stmts depends on VF. */
1491 vect_update_slp_costs_according_to_vf (loop_vinfo
);
1493 vect_estimate_min_profitable_iters (loop_vinfo
, &min_profitable_iters
,
1494 &min_profitable_estimate
);
1495 LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo
) = min_profitable_iters
;
1497 if (min_profitable_iters
< 0)
1499 if (dump_enabled_p ())
1500 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1501 "not vectorized: vectorization not profitable.");
1502 if (dump_enabled_p ())
1503 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1504 "not vectorized: vector version will never be "
1509 min_scalar_loop_bound
= ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND
)
1510 * vectorization_factor
) - 1);
1513 /* Use the cost model only if it is more conservative than user specified
1516 th
= (unsigned) min_scalar_loop_bound
;
1517 if (min_profitable_iters
1518 && (!min_scalar_loop_bound
1519 || min_profitable_iters
> min_scalar_loop_bound
))
1520 th
= (unsigned) min_profitable_iters
;
1522 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1523 && LOOP_VINFO_INT_NITERS (loop_vinfo
) <= th
)
1525 if (dump_enabled_p ())
1526 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1527 "not vectorized: vectorization not profitable.");
1528 if (dump_enabled_p ())
1529 dump_printf_loc (MSG_NOTE
, vect_location
,
1530 "not vectorized: iteration count smaller than user "
1531 "specified loop bound parameter or minimum profitable "
1532 "iterations (whichever is more conservative).");
1536 if ((estimated_niter
= estimated_stmt_executions_int (loop
)) != -1
1537 && ((unsigned HOST_WIDE_INT
) estimated_niter
1538 <= MAX (th
, (unsigned)min_profitable_estimate
)))
1540 if (dump_enabled_p ())
1541 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1542 "not vectorized: estimated iteration count too "
1544 if (dump_enabled_p ())
1545 dump_printf_loc (MSG_NOTE
, vect_location
,
1546 "not vectorized: estimated iteration count smaller "
1547 "than specified loop bound parameter or minimum "
1548 "profitable iterations (whichever is more "
1553 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1554 || LOOP_VINFO_INT_NITERS (loop_vinfo
) % vectorization_factor
!= 0
1555 || LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
))
1557 if (dump_enabled_p ())
1558 dump_printf_loc (MSG_NOTE
, vect_location
, "epilog loop required.");
1559 if (!vect_can_advance_ivs_p (loop_vinfo
))
1561 if (dump_enabled_p ())
1562 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1563 "not vectorized: can't create epilog loop 1.");
1566 if (!slpeel_can_duplicate_loop_p (loop
, single_exit (loop
)))
1568 if (dump_enabled_p ())
1569 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1570 "not vectorized: can't create epilog loop 2.");
1579 /* Function vect_analyze_loop_2.
1581 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1582 for it. The different analyses will record information in the
1583 loop_vec_info struct. */
1585 vect_analyze_loop_2 (loop_vec_info loop_vinfo
)
1587 bool ok
, slp
= false;
1588 int max_vf
= MAX_VECTORIZATION_FACTOR
;
1591 /* Find all data references in the loop (which correspond to vdefs/vuses)
1592 and analyze their evolution in the loop. Also adjust the minimal
1593 vectorization factor according to the loads and stores.
1595 FORNOW: Handle only simple, array references, which
1596 alignment can be forced, and aligned pointer-references. */
1598 ok
= vect_analyze_data_refs (loop_vinfo
, NULL
, &min_vf
);
1601 if (dump_enabled_p ())
1602 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1603 "bad data references.");
1607 /* Classify all cross-iteration scalar data-flow cycles.
1608 Cross-iteration cycles caused by virtual phis are analyzed separately. */
1610 vect_analyze_scalar_cycles (loop_vinfo
);
1612 vect_pattern_recog (loop_vinfo
, NULL
);
1614 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
1616 ok
= vect_mark_stmts_to_be_vectorized (loop_vinfo
);
1619 if (dump_enabled_p ())
1620 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1621 "unexpected pattern.");
1625 /* Analyze data dependences between the data-refs in the loop
1626 and adjust the maximum vectorization factor according to
1628 FORNOW: fail at the first data dependence that we encounter. */
1630 ok
= vect_analyze_data_ref_dependences (loop_vinfo
, NULL
, &max_vf
);
1634 if (dump_enabled_p ())
1635 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1636 "bad data dependence.");
1640 ok
= vect_determine_vectorization_factor (loop_vinfo
);
1643 if (dump_enabled_p ())
1644 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1645 "can't determine vectorization factor.");
1648 if (max_vf
< LOOP_VINFO_VECT_FACTOR (loop_vinfo
))
1650 if (dump_enabled_p ())
1651 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1652 "bad data dependence.");
1656 /* Analyze the alignment of the data-refs in the loop.
1657 Fail if a data reference is found that cannot be vectorized. */
1659 ok
= vect_analyze_data_refs_alignment (loop_vinfo
, NULL
);
1662 if (dump_enabled_p ())
1663 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1664 "bad data alignment.");
1668 /* Analyze the access patterns of the data-refs in the loop (consecutive,
1669 complex, etc.). FORNOW: Only handle consecutive access pattern. */
1671 ok
= vect_analyze_data_ref_accesses (loop_vinfo
, NULL
);
1674 if (dump_enabled_p ())
1675 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1676 "bad data access.");
1680 /* Prune the list of ddrs to be tested at run-time by versioning for alias.
1681 It is important to call pruning after vect_analyze_data_ref_accesses,
1682 since we use grouping information gathered by interleaving analysis. */
1683 ok
= vect_prune_runtime_alias_test_list (loop_vinfo
);
1686 if (dump_enabled_p ())
1687 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1688 "too long list of versioning for alias "
1693 /* This pass will decide on using loop versioning and/or loop peeling in
1694 order to enhance the alignment of data references in the loop. */
1696 ok
= vect_enhance_data_refs_alignment (loop_vinfo
);
1699 if (dump_enabled_p ())
1700 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1701 "bad data alignment.");
1705 /* Check the SLP opportunities in the loop, analyze and build SLP trees. */
1706 ok
= vect_analyze_slp (loop_vinfo
, NULL
);
1709 /* Decide which possible SLP instances to SLP. */
1710 slp
= vect_make_slp_decision (loop_vinfo
);
1712 /* Find stmts that need to be both vectorized and SLPed. */
1713 vect_detect_hybrid_slp (loop_vinfo
);
1718 /* Scan all the operations in the loop and make sure they are
1721 ok
= vect_analyze_loop_operations (loop_vinfo
, slp
);
1724 if (dump_enabled_p ())
1725 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1726 "bad operation or unsupported loop bound.");
1733 /* Function vect_analyze_loop.
1735 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1736 for it. The different analyses will record information in the
1737 loop_vec_info struct. */
1739 vect_analyze_loop (struct loop
*loop
)
1741 loop_vec_info loop_vinfo
;
1742 unsigned int vector_sizes
;
1744 /* Autodetect first vector size we try. */
1745 current_vector_size
= 0;
1746 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
1748 if (dump_enabled_p ())
1749 dump_printf_loc (MSG_NOTE
, vect_location
,
1750 "===== analyze_loop_nest =====");
1752 if (loop_outer (loop
)
1753 && loop_vec_info_for_loop (loop_outer (loop
))
1754 && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop
))))
1756 if (dump_enabled_p ())
1757 dump_printf_loc (MSG_NOTE
, vect_location
,
1758 "outer-loop already vectorized.");
1764 /* Check the CFG characteristics of the loop (nesting, entry/exit). */
1765 loop_vinfo
= vect_analyze_loop_form (loop
);
1768 if (dump_enabled_p ())
1769 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1774 if (vect_analyze_loop_2 (loop_vinfo
))
1776 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
) = 1;
1781 destroy_loop_vec_info (loop_vinfo
, true);
1783 vector_sizes
&= ~current_vector_size
;
1784 if (vector_sizes
== 0
1785 || current_vector_size
== 0)
1788 /* Try the next biggest vector size. */
1789 current_vector_size
= 1 << floor_log2 (vector_sizes
);
1790 if (dump_enabled_p ())
1791 dump_printf_loc (MSG_NOTE
, vect_location
,
1792 "***** Re-trying analysis with "
1793 "vector size %d\n", current_vector_size
);
1798 /* Function reduction_code_for_scalar_code
1801 CODE - tree_code of a reduction operations.
1804 REDUC_CODE - the corresponding tree-code to be used to reduce the
1805 vector of partial results into a single scalar result (which
1806 will also reside in a vector) or ERROR_MARK if the operation is
1807 a supported reduction operation, but does not have such tree-code.
1809 Return FALSE if CODE currently cannot be vectorized as reduction. */
1812 reduction_code_for_scalar_code (enum tree_code code
,
1813 enum tree_code
*reduc_code
)
1818 *reduc_code
= REDUC_MAX_EXPR
;
1822 *reduc_code
= REDUC_MIN_EXPR
;
1826 *reduc_code
= REDUC_PLUS_EXPR
;
1834 *reduc_code
= ERROR_MARK
;
1843 /* Error reporting helper for vect_is_simple_reduction below. GIMPLE statement
1844 STMT is printed with a message MSG. */
1847 report_vect_op (int msg_type
, gimple stmt
, const char *msg
)
1849 dump_printf_loc (msg_type
, vect_location
, "%s", msg
);
1850 dump_gimple_stmt (msg_type
, TDF_SLIM
, stmt
, 0);
1854 /* Detect SLP reduction of the form:
1864 PHI is the reduction phi node (#a1 = phi <a5, a0> above)
1865 FIRST_STMT is the first reduction stmt in the chain
1866 (a2 = operation (a1)).
1868 Return TRUE if a reduction chain was detected. */
1871 vect_is_slp_reduction (loop_vec_info loop_info
, gimple phi
, gimple first_stmt
)
1873 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
1874 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
1875 enum tree_code code
;
1876 gimple current_stmt
= NULL
, loop_use_stmt
= NULL
, first
, next_stmt
;
1877 stmt_vec_info use_stmt_info
, current_stmt_info
;
1879 imm_use_iterator imm_iter
;
1880 use_operand_p use_p
;
1881 int nloop_uses
, size
= 0, n_out_of_loop_uses
;
1884 if (loop
!= vect_loop
)
1887 lhs
= PHI_RESULT (phi
);
1888 code
= gimple_assign_rhs_code (first_stmt
);
1892 n_out_of_loop_uses
= 0;
1893 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
1895 gimple use_stmt
= USE_STMT (use_p
);
1896 if (is_gimple_debug (use_stmt
))
1899 use_stmt
= USE_STMT (use_p
);
1901 /* Check if we got back to the reduction phi. */
1902 if (use_stmt
== phi
)
1904 loop_use_stmt
= use_stmt
;
1909 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
1911 if (vinfo_for_stmt (use_stmt
)
1912 && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (use_stmt
)))
1914 loop_use_stmt
= use_stmt
;
1919 n_out_of_loop_uses
++;
1921 /* There are can be either a single use in the loop or two uses in
1923 if (nloop_uses
> 1 || (n_out_of_loop_uses
&& nloop_uses
))
1930 /* We reached a statement with no loop uses. */
1931 if (nloop_uses
== 0)
1934 /* This is a loop exit phi, and we haven't reached the reduction phi. */
1935 if (gimple_code (loop_use_stmt
) == GIMPLE_PHI
)
1938 if (!is_gimple_assign (loop_use_stmt
)
1939 || code
!= gimple_assign_rhs_code (loop_use_stmt
)
1940 || !flow_bb_inside_loop_p (loop
, gimple_bb (loop_use_stmt
)))
1943 /* Insert USE_STMT into reduction chain. */
1944 use_stmt_info
= vinfo_for_stmt (loop_use_stmt
);
1947 current_stmt_info
= vinfo_for_stmt (current_stmt
);
1948 GROUP_NEXT_ELEMENT (current_stmt_info
) = loop_use_stmt
;
1949 GROUP_FIRST_ELEMENT (use_stmt_info
)
1950 = GROUP_FIRST_ELEMENT (current_stmt_info
);
1953 GROUP_FIRST_ELEMENT (use_stmt_info
) = loop_use_stmt
;
1955 lhs
= gimple_assign_lhs (loop_use_stmt
);
1956 current_stmt
= loop_use_stmt
;
1960 if (!found
|| loop_use_stmt
!= phi
|| size
< 2)
1963 /* Swap the operands, if needed, to make the reduction operand be the second
1965 lhs
= PHI_RESULT (phi
);
1966 next_stmt
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
1969 if (gimple_assign_rhs2 (next_stmt
) == lhs
)
1971 tree op
= gimple_assign_rhs1 (next_stmt
);
1972 gimple def_stmt
= NULL
;
1974 if (TREE_CODE (op
) == SSA_NAME
)
1975 def_stmt
= SSA_NAME_DEF_STMT (op
);
1977 /* Check that the other def is either defined in the loop
1978 ("vect_internal_def"), or it's an induction (defined by a
1979 loop-header phi-node). */
1981 && gimple_bb (def_stmt
)
1982 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
1983 && (is_gimple_assign (def_stmt
)
1984 || is_gimple_call (def_stmt
)
1985 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
1986 == vect_induction_def
1987 || (gimple_code (def_stmt
) == GIMPLE_PHI
1988 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
1989 == vect_internal_def
1990 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
1992 lhs
= gimple_assign_lhs (next_stmt
);
1993 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
2001 tree op
= gimple_assign_rhs2 (next_stmt
);
2002 gimple def_stmt
= NULL
;
2004 if (TREE_CODE (op
) == SSA_NAME
)
2005 def_stmt
= SSA_NAME_DEF_STMT (op
);
2007 /* Check that the other def is either defined in the loop
2008 ("vect_internal_def"), or it's an induction (defined by a
2009 loop-header phi-node). */
2011 && gimple_bb (def_stmt
)
2012 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2013 && (is_gimple_assign (def_stmt
)
2014 || is_gimple_call (def_stmt
)
2015 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2016 == vect_induction_def
2017 || (gimple_code (def_stmt
) == GIMPLE_PHI
2018 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2019 == vect_internal_def
2020 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
2022 if (dump_enabled_p ())
2024 dump_printf_loc (MSG_NOTE
, vect_location
, "swapping oprnds: ");
2025 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, next_stmt
, 0);
2028 swap_tree_operands (next_stmt
,
2029 gimple_assign_rhs1_ptr (next_stmt
),
2030 gimple_assign_rhs2_ptr (next_stmt
));
2031 update_stmt (next_stmt
);
2033 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (next_stmt
)))
2034 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
2040 lhs
= gimple_assign_lhs (next_stmt
);
2041 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
2044 /* Save the chain for further analysis in SLP detection. */
2045 first
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
2046 LOOP_VINFO_REDUCTION_CHAINS (loop_info
).safe_push (first
);
2047 GROUP_SIZE (vinfo_for_stmt (first
)) = size
;
2053 /* Function vect_is_simple_reduction_1
2055 (1) Detect a cross-iteration def-use cycle that represents a simple
2056 reduction computation. We look for the following pattern:
2061 a2 = operation (a3, a1)
2064 1. operation is commutative and associative and it is safe to
2065 change the order of the computation (if CHECK_REDUCTION is true)
2066 2. no uses for a2 in the loop (a2 is used out of the loop)
2067 3. no uses of a1 in the loop besides the reduction operation
2068 4. no uses of a1 outside the loop.
2070 Conditions 1,4 are tested here.
2071 Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
2073 (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
2074 nested cycles, if CHECK_REDUCTION is false.
2076 (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
2080 inner loop (def of a3)
2083 If MODIFY is true it tries also to rework the code in-place to enable
2084 detection of more reduction patterns. For the time being we rewrite
2085 "res -= RHS" into "rhs += -RHS" when it seems worthwhile.
2089 vect_is_simple_reduction_1 (loop_vec_info loop_info
, gimple phi
,
2090 bool check_reduction
, bool *double_reduc
,
2093 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
2094 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
2095 edge latch_e
= loop_latch_edge (loop
);
2096 tree loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
2097 gimple def_stmt
, def1
= NULL
, def2
= NULL
;
2098 enum tree_code orig_code
, code
;
2099 tree op1
, op2
, op3
= NULL_TREE
, op4
= NULL_TREE
;
2103 imm_use_iterator imm_iter
;
2104 use_operand_p use_p
;
2107 *double_reduc
= false;
2109 /* If CHECK_REDUCTION is true, we assume inner-most loop vectorization,
2110 otherwise, we assume outer loop vectorization. */
2111 gcc_assert ((check_reduction
&& loop
== vect_loop
)
2112 || (!check_reduction
&& flow_loop_nested_p (vect_loop
, loop
)));
2114 name
= PHI_RESULT (phi
);
2116 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2118 gimple use_stmt
= USE_STMT (use_p
);
2119 if (is_gimple_debug (use_stmt
))
2122 if (!flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2124 if (dump_enabled_p ())
2125 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2126 "intermediate value used outside loop.");
2131 if (vinfo_for_stmt (use_stmt
)
2132 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt
)))
2136 if (dump_enabled_p ())
2137 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2138 "reduction used in loop.");
2143 if (TREE_CODE (loop_arg
) != SSA_NAME
)
2145 if (dump_enabled_p ())
2147 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2148 "reduction: not ssa_name: ");
2149 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, loop_arg
);
2154 def_stmt
= SSA_NAME_DEF_STMT (loop_arg
);
2157 if (dump_enabled_p ())
2158 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2159 "reduction: no def_stmt.");
2163 if (!is_gimple_assign (def_stmt
) && gimple_code (def_stmt
) != GIMPLE_PHI
)
2165 if (dump_enabled_p ())
2166 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, def_stmt
, 0);
2170 if (is_gimple_assign (def_stmt
))
2172 name
= gimple_assign_lhs (def_stmt
);
2177 name
= PHI_RESULT (def_stmt
);
2182 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2184 gimple use_stmt
= USE_STMT (use_p
);
2185 if (is_gimple_debug (use_stmt
))
2187 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
))
2188 && vinfo_for_stmt (use_stmt
)
2189 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt
)))
2193 if (dump_enabled_p ())
2194 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2195 "reduction used in loop.");
2200 /* If DEF_STMT is a phi node itself, we expect it to have a single argument
2201 defined in the inner loop. */
2204 op1
= PHI_ARG_DEF (def_stmt
, 0);
2206 if (gimple_phi_num_args (def_stmt
) != 1
2207 || TREE_CODE (op1
) != SSA_NAME
)
2209 if (dump_enabled_p ())
2210 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2211 "unsupported phi node definition.");
2216 def1
= SSA_NAME_DEF_STMT (op1
);
2217 if (flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2219 && flow_bb_inside_loop_p (loop
->inner
, gimple_bb (def1
))
2220 && is_gimple_assign (def1
))
2222 if (dump_enabled_p ())
2223 report_vect_op (MSG_NOTE
, def_stmt
,
2224 "detected double reduction: ");
2226 *double_reduc
= true;
2233 code
= orig_code
= gimple_assign_rhs_code (def_stmt
);
2235 /* We can handle "res -= x[i]", which is non-associative by
2236 simply rewriting this into "res += -x[i]". Avoid changing
2237 gimple instruction for the first simple tests and only do this
2238 if we're allowed to change code at all. */
2239 if (code
== MINUS_EXPR
2241 && (op1
= gimple_assign_rhs1 (def_stmt
))
2242 && TREE_CODE (op1
) == SSA_NAME
2243 && SSA_NAME_DEF_STMT (op1
) == phi
)
2247 && (!commutative_tree_code (code
) || !associative_tree_code (code
)))
2249 if (dump_enabled_p ())
2250 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2251 "reduction: not commutative/associative: ");
2255 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
2257 if (code
!= COND_EXPR
)
2259 if (dump_enabled_p ())
2260 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2261 "reduction: not binary operation: ");
2266 op3
= gimple_assign_rhs1 (def_stmt
);
2267 if (COMPARISON_CLASS_P (op3
))
2269 op4
= TREE_OPERAND (op3
, 1);
2270 op3
= TREE_OPERAND (op3
, 0);
2273 op1
= gimple_assign_rhs2 (def_stmt
);
2274 op2
= gimple_assign_rhs3 (def_stmt
);
2276 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2278 if (dump_enabled_p ())
2279 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2280 "reduction: uses not ssa_names: ");
2287 op1
= gimple_assign_rhs1 (def_stmt
);
2288 op2
= gimple_assign_rhs2 (def_stmt
);
2290 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2292 if (dump_enabled_p ())
2293 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2294 "reduction: uses not ssa_names: ");
2300 type
= TREE_TYPE (gimple_assign_lhs (def_stmt
));
2301 if ((TREE_CODE (op1
) == SSA_NAME
2302 && !types_compatible_p (type
,TREE_TYPE (op1
)))
2303 || (TREE_CODE (op2
) == SSA_NAME
2304 && !types_compatible_p (type
, TREE_TYPE (op2
)))
2305 || (op3
&& TREE_CODE (op3
) == SSA_NAME
2306 && !types_compatible_p (type
, TREE_TYPE (op3
)))
2307 || (op4
&& TREE_CODE (op4
) == SSA_NAME
2308 && !types_compatible_p (type
, TREE_TYPE (op4
))))
2310 if (dump_enabled_p ())
2312 dump_printf_loc (MSG_NOTE
, vect_location
,
2313 "reduction: multiple types: operation type: ");
2314 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, type
);
2315 dump_printf (MSG_NOTE
, ", operands types: ");
2316 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2318 dump_printf (MSG_NOTE
, ",");
2319 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2323 dump_printf (MSG_NOTE
, ",");
2324 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2330 dump_printf (MSG_NOTE
, ",");
2331 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2339 /* Check that it's ok to change the order of the computation.
2340 Generally, when vectorizing a reduction we change the order of the
2341 computation. This may change the behavior of the program in some
2342 cases, so we need to check that this is ok. One exception is when
2343 vectorizing an outer-loop: the inner-loop is executed sequentially,
2344 and therefore vectorizing reductions in the inner-loop during
2345 outer-loop vectorization is safe. */
2347 /* CHECKME: check for !flag_finite_math_only too? */
2348 if (SCALAR_FLOAT_TYPE_P (type
) && !flag_associative_math
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 fp math optimization: ");
2357 else if (INTEGRAL_TYPE_P (type
) && TYPE_OVERFLOW_TRAPS (type
)
2360 /* Changing the order of operations changes the semantics. */
2361 if (dump_enabled_p ())
2362 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2363 "reduction: unsafe int math optimization: ");
2366 else if (SAT_FIXED_POINT_TYPE_P (type
) && check_reduction
)
2368 /* Changing the order of operations changes the semantics. */
2369 if (dump_enabled_p ())
2370 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2371 "reduction: unsafe fixed-point math optimization: ");
2375 /* If we detected "res -= x[i]" earlier, rewrite it into
2376 "res += -x[i]" now. If this turns out to be useless reassoc
2377 will clean it up again. */
2378 if (orig_code
== MINUS_EXPR
)
2380 tree rhs
= gimple_assign_rhs2 (def_stmt
);
2381 tree negrhs
= make_ssa_name (TREE_TYPE (rhs
), NULL
);
2382 gimple negate_stmt
= gimple_build_assign_with_ops (NEGATE_EXPR
, negrhs
,
2384 gimple_stmt_iterator gsi
= gsi_for_stmt (def_stmt
);
2385 set_vinfo_for_stmt (negate_stmt
, new_stmt_vec_info (negate_stmt
,
2387 gsi_insert_before (&gsi
, negate_stmt
, GSI_NEW_STMT
);
2388 gimple_assign_set_rhs2 (def_stmt
, negrhs
);
2389 gimple_assign_set_rhs_code (def_stmt
, PLUS_EXPR
);
2390 update_stmt (def_stmt
);
2393 /* Reduction is safe. We're dealing with one of the following:
2394 1) integer arithmetic and no trapv
2395 2) floating point arithmetic, and special flags permit this optimization
2396 3) nested cycle (i.e., outer loop vectorization). */
2397 if (TREE_CODE (op1
) == SSA_NAME
)
2398 def1
= SSA_NAME_DEF_STMT (op1
);
2400 if (TREE_CODE (op2
) == SSA_NAME
)
2401 def2
= SSA_NAME_DEF_STMT (op2
);
2403 if (code
!= COND_EXPR
2404 && ((!def1
|| gimple_nop_p (def1
)) && (!def2
|| gimple_nop_p (def2
))))
2406 if (dump_enabled_p ())
2407 report_vect_op (MSG_NOTE
, def_stmt
, "reduction: no defs for operands: ");
2411 /* Check that one def is the reduction def, defined by PHI,
2412 the other def is either defined in the loop ("vect_internal_def"),
2413 or it's an induction (defined by a loop-header phi-node). */
2415 if (def2
&& def2
== phi
2416 && (code
== COND_EXPR
2417 || !def1
|| gimple_nop_p (def1
)
2418 || (def1
&& flow_bb_inside_loop_p (loop
, gimple_bb (def1
))
2419 && (is_gimple_assign (def1
)
2420 || is_gimple_call (def1
)
2421 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
2422 == vect_induction_def
2423 || (gimple_code (def1
) == GIMPLE_PHI
2424 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
2425 == vect_internal_def
2426 && !is_loop_header_bb_p (gimple_bb (def1
)))))))
2428 if (dump_enabled_p ())
2429 report_vect_op (MSG_NOTE
, def_stmt
, "detected reduction: ");
2433 if (def1
&& def1
== phi
2434 && (code
== COND_EXPR
2435 || !def2
|| gimple_nop_p (def2
)
2436 || (def2
&& flow_bb_inside_loop_p (loop
, gimple_bb (def2
))
2437 && (is_gimple_assign (def2
)
2438 || is_gimple_call (def2
)
2439 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
2440 == vect_induction_def
2441 || (gimple_code (def2
) == GIMPLE_PHI
2442 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
2443 == vect_internal_def
2444 && !is_loop_header_bb_p (gimple_bb (def2
)))))))
2446 if (check_reduction
)
2448 /* Swap operands (just for simplicity - so that the rest of the code
2449 can assume that the reduction variable is always the last (second)
2451 if (dump_enabled_p ())
2452 report_vect_op (MSG_NOTE
, def_stmt
,
2453 "detected reduction: need to swap operands: ");
2455 swap_tree_operands (def_stmt
, gimple_assign_rhs1_ptr (def_stmt
),
2456 gimple_assign_rhs2_ptr (def_stmt
));
2458 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (def_stmt
)))
2459 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
2463 if (dump_enabled_p ())
2464 report_vect_op (MSG_NOTE
, def_stmt
, "detected reduction: ");
2470 /* Try to find SLP reduction chain. */
2471 if (check_reduction
&& vect_is_slp_reduction (loop_info
, phi
, def_stmt
))
2473 if (dump_enabled_p ())
2474 report_vect_op (MSG_NOTE
, def_stmt
,
2475 "reduction: detected reduction chain: ");
2480 if (dump_enabled_p ())
2481 report_vect_op (MSG_MISSED_OPTIMIZATION
, def_stmt
,
2482 "reduction: unknown pattern: ");
2487 /* Wrapper around vect_is_simple_reduction_1, that won't modify code
2488 in-place. Arguments as there. */
2491 vect_is_simple_reduction (loop_vec_info loop_info
, gimple phi
,
2492 bool check_reduction
, bool *double_reduc
)
2494 return vect_is_simple_reduction_1 (loop_info
, phi
, check_reduction
,
2495 double_reduc
, false);
2498 /* Wrapper around vect_is_simple_reduction_1, which will modify code
2499 in-place if it enables detection of more reductions. Arguments
2503 vect_force_simple_reduction (loop_vec_info loop_info
, gimple phi
,
2504 bool check_reduction
, bool *double_reduc
)
2506 return vect_is_simple_reduction_1 (loop_info
, phi
, check_reduction
,
2507 double_reduc
, true);
2510 /* Calculate the cost of one scalar iteration of the loop. */
2512 vect_get_single_scalar_iteration_cost (loop_vec_info loop_vinfo
)
2514 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2515 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
2516 int nbbs
= loop
->num_nodes
, factor
, scalar_single_iter_cost
= 0;
2517 int innerloop_iters
, i
, stmt_cost
;
2519 /* Count statements in scalar loop. Using this as scalar cost for a single
2522 TODO: Add outer loop support.
2524 TODO: Consider assigning different costs to different scalar
2528 innerloop_iters
= 1;
2530 innerloop_iters
= 50; /* FIXME */
2532 for (i
= 0; i
< nbbs
; i
++)
2534 gimple_stmt_iterator si
;
2535 basic_block bb
= bbs
[i
];
2537 if (bb
->loop_father
== loop
->inner
)
2538 factor
= innerloop_iters
;
2542 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
2544 gimple stmt
= gsi_stmt (si
);
2545 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2547 if (!is_gimple_assign (stmt
) && !is_gimple_call (stmt
))
2550 /* Skip stmts that are not vectorized inside the loop. */
2552 && !STMT_VINFO_RELEVANT_P (stmt_info
)
2553 && (!STMT_VINFO_LIVE_P (stmt_info
)
2554 || !VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
2555 && !STMT_VINFO_IN_PATTERN_P (stmt_info
))
2558 if (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
)))
2560 if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))))
2561 stmt_cost
= vect_get_stmt_cost (scalar_load
);
2563 stmt_cost
= vect_get_stmt_cost (scalar_store
);
2566 stmt_cost
= vect_get_stmt_cost (scalar_stmt
);
2568 scalar_single_iter_cost
+= stmt_cost
* factor
;
2571 return scalar_single_iter_cost
;
2574 /* Calculate cost of peeling the loop PEEL_ITERS_PROLOGUE times. */
2576 vect_get_known_peeling_cost (loop_vec_info loop_vinfo
, int peel_iters_prologue
,
2577 int *peel_iters_epilogue
,
2578 int scalar_single_iter_cost
,
2579 stmt_vector_for_cost
*prologue_cost_vec
,
2580 stmt_vector_for_cost
*epilogue_cost_vec
)
2583 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2585 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
2587 *peel_iters_epilogue
= vf
/2;
2588 if (dump_enabled_p ())
2589 dump_printf_loc (MSG_NOTE
, vect_location
,
2590 "cost model: epilogue peel iters set to vf/2 "
2591 "because loop iterations are unknown .");
2593 /* If peeled iterations are known but number of scalar loop
2594 iterations are unknown, count a taken branch per peeled loop. */
2595 retval
= record_stmt_cost (prologue_cost_vec
, 2, cond_branch_taken
,
2596 NULL
, 0, vect_prologue
);
2600 int niters
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
2601 peel_iters_prologue
= niters
< peel_iters_prologue
?
2602 niters
: peel_iters_prologue
;
2603 *peel_iters_epilogue
= (niters
- peel_iters_prologue
) % vf
;
2604 /* If we need to peel for gaps, but no peeling is required, we have to
2605 peel VF iterations. */
2606 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) && !*peel_iters_epilogue
)
2607 *peel_iters_epilogue
= vf
;
2610 if (peel_iters_prologue
)
2611 retval
+= record_stmt_cost (prologue_cost_vec
,
2612 peel_iters_prologue
* scalar_single_iter_cost
,
2613 scalar_stmt
, NULL
, 0, vect_prologue
);
2614 if (*peel_iters_epilogue
)
2615 retval
+= record_stmt_cost (epilogue_cost_vec
,
2616 *peel_iters_epilogue
* scalar_single_iter_cost
,
2617 scalar_stmt
, NULL
, 0, vect_epilogue
);
2621 /* Function vect_estimate_min_profitable_iters
2623 Return the number of iterations required for the vector version of the
2624 loop to be profitable relative to the cost of the scalar version of the
2628 vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo
,
2629 int *ret_min_profitable_niters
,
2630 int *ret_min_profitable_estimate
)
2632 int min_profitable_iters
;
2633 int min_profitable_estimate
;
2634 int peel_iters_prologue
;
2635 int peel_iters_epilogue
;
2636 unsigned vec_inside_cost
= 0;
2637 int vec_outside_cost
= 0;
2638 unsigned vec_prologue_cost
= 0;
2639 unsigned vec_epilogue_cost
= 0;
2640 int scalar_single_iter_cost
= 0;
2641 int scalar_outside_cost
= 0;
2642 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2643 int npeel
= LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
);
2644 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2646 /* Cost model disabled. */
2647 if (!flag_vect_cost_model
)
2649 dump_printf_loc (MSG_NOTE
, vect_location
, "cost model disabled.");
2650 *ret_min_profitable_niters
= 0;
2651 *ret_min_profitable_estimate
= 0;
2655 /* Requires loop versioning tests to handle misalignment. */
2656 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
))
2658 /* FIXME: Make cost depend on complexity of individual check. */
2659 unsigned len
= LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).length ();
2660 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
2662 dump_printf (MSG_NOTE
,
2663 "cost model: Adding cost of checks for loop "
2664 "versioning to treat misalignment.\n");
2667 /* Requires loop versioning with alias checks. */
2668 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2670 /* FIXME: Make cost depend on complexity of individual check. */
2671 unsigned len
= LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
).length ();
2672 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
2674 dump_printf (MSG_NOTE
,
2675 "cost model: Adding cost of checks for loop "
2676 "versioning aliasing.\n");
2679 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2680 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2681 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_taken
, NULL
, 0,
2684 /* Count statements in scalar loop. Using this as scalar cost for a single
2687 TODO: Add outer loop support.
2689 TODO: Consider assigning different costs to different scalar
2692 scalar_single_iter_cost
= vect_get_single_scalar_iteration_cost (loop_vinfo
);
2694 /* Add additional cost for the peeled instructions in prologue and epilogue
2697 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
2698 at compile-time - we assume it's vf/2 (the worst would be vf-1).
2700 TODO: Build an expression that represents peel_iters for prologue and
2701 epilogue to be used in a run-time test. */
2705 peel_iters_prologue
= vf
/2;
2706 dump_printf (MSG_NOTE
, "cost model: "
2707 "prologue peel iters set to vf/2.");
2709 /* If peeling for alignment is unknown, loop bound of main loop becomes
2711 peel_iters_epilogue
= vf
/2;
2712 dump_printf (MSG_NOTE
, "cost model: "
2713 "epilogue peel iters set to vf/2 because "
2714 "peeling for alignment is unknown.");
2716 /* If peeled iterations are unknown, count a taken branch and a not taken
2717 branch per peeled loop. Even if scalar loop iterations are known,
2718 vector iterations are not known since peeled prologue iterations are
2719 not known. Hence guards remain the same. */
2720 (void) add_stmt_cost (target_cost_data
, 2, cond_branch_taken
,
2721 NULL
, 0, vect_prologue
);
2722 (void) add_stmt_cost (target_cost_data
, 2, cond_branch_not_taken
,
2723 NULL
, 0, vect_prologue
);
2724 /* FORNOW: Don't attempt to pass individual scalar instructions to
2725 the model; just assume linear cost for scalar iterations. */
2726 (void) add_stmt_cost (target_cost_data
,
2727 peel_iters_prologue
* scalar_single_iter_cost
,
2728 scalar_stmt
, NULL
, 0, vect_prologue
);
2729 (void) add_stmt_cost (target_cost_data
,
2730 peel_iters_epilogue
* scalar_single_iter_cost
,
2731 scalar_stmt
, NULL
, 0, vect_epilogue
);
2735 stmt_vector_for_cost prologue_cost_vec
, epilogue_cost_vec
;
2736 stmt_info_for_cost
*si
;
2738 void *data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2740 prologue_cost_vec
.create (2);
2741 epilogue_cost_vec
.create (2);
2742 peel_iters_prologue
= npeel
;
2744 (void) vect_get_known_peeling_cost (loop_vinfo
, peel_iters_prologue
,
2745 &peel_iters_epilogue
,
2746 scalar_single_iter_cost
,
2748 &epilogue_cost_vec
);
2750 FOR_EACH_VEC_ELT (prologue_cost_vec
, j
, si
)
2752 struct _stmt_vec_info
*stmt_info
2753 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
2754 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
2755 si
->misalign
, vect_prologue
);
2758 FOR_EACH_VEC_ELT (epilogue_cost_vec
, j
, si
)
2760 struct _stmt_vec_info
*stmt_info
2761 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
2762 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
2763 si
->misalign
, vect_epilogue
);
2766 prologue_cost_vec
.release ();
2767 epilogue_cost_vec
.release ();
2770 /* FORNOW: The scalar outside cost is incremented in one of the
2773 1. The vectorizer checks for alignment and aliasing and generates
2774 a condition that allows dynamic vectorization. A cost model
2775 check is ANDED with the versioning condition. Hence scalar code
2776 path now has the added cost of the versioning check.
2778 if (cost > th & versioning_check)
2781 Hence run-time scalar is incremented by not-taken branch cost.
2783 2. The vectorizer then checks if a prologue is required. If the
2784 cost model check was not done before during versioning, it has to
2785 be done before the prologue check.
2788 prologue = scalar_iters
2793 if (prologue == num_iters)
2796 Hence the run-time scalar cost is incremented by a taken branch,
2797 plus a not-taken branch, plus a taken branch cost.
2799 3. The vectorizer then checks if an epilogue is required. If the
2800 cost model check was not done before during prologue check, it
2801 has to be done with the epilogue check.
2807 if (prologue == num_iters)
2810 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
2813 Hence the run-time scalar cost should be incremented by 2 taken
2816 TODO: The back end may reorder the BBS's differently and reverse
2817 conditions/branch directions. Change the estimates below to
2818 something more reasonable. */
2820 /* If the number of iterations is known and we do not do versioning, we can
2821 decide whether to vectorize at compile time. Hence the scalar version
2822 do not carry cost model guard costs. */
2823 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
2824 || LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2825 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2827 /* Cost model check occurs at versioning. */
2828 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2829 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2830 scalar_outside_cost
+= vect_get_stmt_cost (cond_branch_not_taken
);
2833 /* Cost model check occurs at prologue generation. */
2834 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
) < 0)
2835 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
)
2836 + vect_get_stmt_cost (cond_branch_not_taken
);
2837 /* Cost model check occurs at epilogue generation. */
2839 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
);
2843 /* Complete the target-specific cost calculations. */
2844 finish_cost (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
), &vec_prologue_cost
,
2845 &vec_inside_cost
, &vec_epilogue_cost
);
2847 vec_outside_cost
= (int)(vec_prologue_cost
+ vec_epilogue_cost
);
2849 /* Calculate number of iterations required to make the vector version
2850 profitable, relative to the loop bodies only. The following condition
2852 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
2854 SIC = scalar iteration cost, VIC = vector iteration cost,
2855 VOC = vector outside cost, VF = vectorization factor,
2856 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
2857 SOC = scalar outside cost for run time cost model check. */
2859 if ((scalar_single_iter_cost
* vf
) > (int) vec_inside_cost
)
2861 if (vec_outside_cost
<= 0)
2862 min_profitable_iters
= 1;
2865 min_profitable_iters
= ((vec_outside_cost
- scalar_outside_cost
) * vf
2866 - vec_inside_cost
* peel_iters_prologue
2867 - vec_inside_cost
* peel_iters_epilogue
)
2868 / ((scalar_single_iter_cost
* vf
)
2871 if ((scalar_single_iter_cost
* vf
* min_profitable_iters
)
2872 <= (((int) vec_inside_cost
* min_profitable_iters
)
2873 + (((int) vec_outside_cost
- scalar_outside_cost
) * vf
)))
2874 min_profitable_iters
++;
2877 /* vector version will never be profitable. */
2880 if (dump_enabled_p ())
2881 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2882 "cost model: the vector iteration cost = %d "
2883 "divided by the scalar iteration cost = %d "
2884 "is greater or equal to the vectorization factor = %d.",
2885 vec_inside_cost
, scalar_single_iter_cost
, vf
);
2886 *ret_min_profitable_niters
= -1;
2887 *ret_min_profitable_estimate
= -1;
2891 if (dump_enabled_p ())
2893 dump_printf_loc (MSG_NOTE
, vect_location
, "Cost model analysis: \n");
2894 dump_printf (MSG_NOTE
, " Vector inside of loop cost: %d\n",
2896 dump_printf (MSG_NOTE
, " Vector prologue cost: %d\n",
2898 dump_printf (MSG_NOTE
, " Vector epilogue cost: %d\n",
2900 dump_printf (MSG_NOTE
, " Scalar iteration cost: %d\n",
2901 scalar_single_iter_cost
);
2902 dump_printf (MSG_NOTE
, " Scalar outside cost: %d\n",
2903 scalar_outside_cost
);
2904 dump_printf (MSG_NOTE
, " Vector outside cost: %d\n",
2906 dump_printf (MSG_NOTE
, " prologue iterations: %d\n",
2907 peel_iters_prologue
);
2908 dump_printf (MSG_NOTE
, " epilogue iterations: %d\n",
2909 peel_iters_epilogue
);
2910 dump_printf (MSG_NOTE
,
2911 " Calculated minimum iters for profitability: %d\n",
2912 min_profitable_iters
);
2915 min_profitable_iters
=
2916 min_profitable_iters
< vf
? vf
: min_profitable_iters
;
2918 /* Because the condition we create is:
2919 if (niters <= min_profitable_iters)
2920 then skip the vectorized loop. */
2921 min_profitable_iters
--;
2923 if (dump_enabled_p ())
2924 dump_printf_loc (MSG_NOTE
, vect_location
,
2925 " Runtime profitability threshold = %d\n", min_profitable_iters
);
2927 *ret_min_profitable_niters
= min_profitable_iters
;
2929 /* Calculate number of iterations required to make the vector version
2930 profitable, relative to the loop bodies only.
2932 Non-vectorized variant is SIC * niters and it must win over vector
2933 variant on the expected loop trip count. The following condition must hold true:
2934 SIC * niters > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC + SOC */
2936 if (vec_outside_cost
<= 0)
2937 min_profitable_estimate
= 1;
2940 min_profitable_estimate
= ((vec_outside_cost
+ scalar_outside_cost
) * vf
2941 - vec_inside_cost
* peel_iters_prologue
2942 - vec_inside_cost
* peel_iters_epilogue
)
2943 / ((scalar_single_iter_cost
* vf
)
2946 min_profitable_estimate
--;
2947 min_profitable_estimate
= MAX (min_profitable_estimate
, min_profitable_iters
);
2948 if (dump_enabled_p ())
2949 dump_printf_loc (MSG_NOTE
, vect_location
,
2950 " Static estimate profitability threshold = %d\n",
2951 min_profitable_iters
);
2953 *ret_min_profitable_estimate
= min_profitable_estimate
;
2957 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
2958 functions. Design better to avoid maintenance issues. */
2960 /* Function vect_model_reduction_cost.
2962 Models cost for a reduction operation, including the vector ops
2963 generated within the strip-mine loop, the initial definition before
2964 the loop, and the epilogue code that must be generated. */
2967 vect_model_reduction_cost (stmt_vec_info stmt_info
, enum tree_code reduc_code
,
2970 int prologue_cost
= 0, epilogue_cost
= 0;
2971 enum tree_code code
;
2974 gimple stmt
, orig_stmt
;
2976 enum machine_mode mode
;
2977 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
2978 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2979 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2981 /* Cost of reduction op inside loop. */
2982 unsigned inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
2983 stmt_info
, 0, vect_body
);
2984 stmt
= STMT_VINFO_STMT (stmt_info
);
2986 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
2988 case GIMPLE_SINGLE_RHS
:
2989 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
)) == ternary_op
);
2990 reduction_op
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
2992 case GIMPLE_UNARY_RHS
:
2993 reduction_op
= gimple_assign_rhs1 (stmt
);
2995 case GIMPLE_BINARY_RHS
:
2996 reduction_op
= gimple_assign_rhs2 (stmt
);
2998 case GIMPLE_TERNARY_RHS
:
2999 reduction_op
= gimple_assign_rhs3 (stmt
);
3005 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
3008 if (dump_enabled_p ())
3010 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3011 "unsupported data-type ");
3012 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
3013 TREE_TYPE (reduction_op
));
3018 mode
= TYPE_MODE (vectype
);
3019 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
3022 orig_stmt
= STMT_VINFO_STMT (stmt_info
);
3024 code
= gimple_assign_rhs_code (orig_stmt
);
3026 /* Add in cost for initial definition. */
3027 prologue_cost
+= add_stmt_cost (target_cost_data
, 1, scalar_to_vec
,
3028 stmt_info
, 0, vect_prologue
);
3030 /* Determine cost of epilogue code.
3032 We have a reduction operator that will reduce the vector in one statement.
3033 Also requires scalar extract. */
3035 if (!nested_in_vect_loop_p (loop
, orig_stmt
))
3037 if (reduc_code
!= ERROR_MARK
)
3039 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1, vector_stmt
,
3040 stmt_info
, 0, vect_epilogue
);
3041 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1, vec_to_scalar
,
3042 stmt_info
, 0, vect_epilogue
);
3046 int vec_size_in_bits
= tree_low_cst (TYPE_SIZE (vectype
), 1);
3048 TYPE_SIZE (TREE_TYPE (gimple_assign_lhs (orig_stmt
)));
3049 int element_bitsize
= tree_low_cst (bitsize
, 1);
3050 int nelements
= vec_size_in_bits
/ element_bitsize
;
3052 optab
= optab_for_tree_code (code
, vectype
, optab_default
);
3054 /* We have a whole vector shift available. */
3055 if (VECTOR_MODE_P (mode
)
3056 && optab_handler (optab
, mode
) != CODE_FOR_nothing
3057 && optab_handler (vec_shr_optab
, mode
) != CODE_FOR_nothing
)
3059 /* Final reduction via vector shifts and the reduction operator.
3060 Also requires scalar extract. */
3061 epilogue_cost
+= add_stmt_cost (target_cost_data
,
3062 exact_log2 (nelements
) * 2,
3063 vector_stmt
, stmt_info
, 0,
3065 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1,
3066 vec_to_scalar
, stmt_info
, 0,
3070 /* Use extracts and reduction op for final reduction. For N
3071 elements, we have N extracts and N-1 reduction ops. */
3072 epilogue_cost
+= add_stmt_cost (target_cost_data
,
3073 nelements
+ nelements
- 1,
3074 vector_stmt
, stmt_info
, 0,
3079 if (dump_enabled_p ())
3080 dump_printf (MSG_NOTE
,
3081 "vect_model_reduction_cost: inside_cost = %d, "
3082 "prologue_cost = %d, epilogue_cost = %d .", inside_cost
,
3083 prologue_cost
, epilogue_cost
);
3089 /* Function vect_model_induction_cost.
3091 Models cost for induction operations. */
3094 vect_model_induction_cost (stmt_vec_info stmt_info
, int ncopies
)
3096 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3097 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
3098 unsigned inside_cost
, prologue_cost
;
3100 /* loop cost for vec_loop. */
3101 inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
3102 stmt_info
, 0, vect_body
);
3104 /* prologue cost for vec_init and vec_step. */
3105 prologue_cost
= add_stmt_cost (target_cost_data
, 2, scalar_to_vec
,
3106 stmt_info
, 0, vect_prologue
);
3108 if (dump_enabled_p ())
3109 dump_printf_loc (MSG_NOTE
, vect_location
,
3110 "vect_model_induction_cost: inside_cost = %d, "
3111 "prologue_cost = %d .", inside_cost
, prologue_cost
);
3115 /* Function get_initial_def_for_induction
3118 STMT - a stmt that performs an induction operation in the loop.
3119 IV_PHI - the initial value of the induction variable
3122 Return a vector variable, initialized with the first VF values of
3123 the induction variable. E.g., for an iv with IV_PHI='X' and
3124 evolution S, for a vector of 4 units, we want to return:
3125 [X, X + S, X + 2*S, X + 3*S]. */
3128 get_initial_def_for_induction (gimple iv_phi
)
3130 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (iv_phi
);
3131 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
3132 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3136 edge pe
= loop_preheader_edge (loop
);
3137 struct loop
*iv_loop
;
3139 tree new_vec
, vec_init
, vec_step
, t
;
3143 gimple init_stmt
, induction_phi
, new_stmt
;
3144 tree induc_def
, vec_def
, vec_dest
;
3145 tree init_expr
, step_expr
;
3146 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3151 stmt_vec_info phi_info
= vinfo_for_stmt (iv_phi
);
3152 bool nested_in_vect_loop
= false;
3153 gimple_seq stmts
= NULL
;
3154 imm_use_iterator imm_iter
;
3155 use_operand_p use_p
;
3159 gimple_stmt_iterator si
;
3160 basic_block bb
= gimple_bb (iv_phi
);
3164 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
3165 if (nested_in_vect_loop_p (loop
, iv_phi
))
3167 nested_in_vect_loop
= true;
3168 iv_loop
= loop
->inner
;
3172 gcc_assert (iv_loop
== (gimple_bb (iv_phi
))->loop_father
);
3174 latch_e
= loop_latch_edge (iv_loop
);
3175 loop_arg
= PHI_ARG_DEF_FROM_EDGE (iv_phi
, latch_e
);
3177 access_fn
= analyze_scalar_evolution (iv_loop
, PHI_RESULT (iv_phi
));
3178 gcc_assert (access_fn
);
3179 STRIP_NOPS (access_fn
);
3180 ok
= vect_is_simple_iv_evolution (iv_loop
->num
, access_fn
,
3181 &init_expr
, &step_expr
);
3183 pe
= loop_preheader_edge (iv_loop
);
3185 scalar_type
= TREE_TYPE (init_expr
);
3186 vectype
= get_vectype_for_scalar_type (scalar_type
);
3187 resvectype
= get_vectype_for_scalar_type (TREE_TYPE (PHI_RESULT (iv_phi
)));
3188 gcc_assert (vectype
);
3189 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3190 ncopies
= vf
/ nunits
;
3192 gcc_assert (phi_info
);
3193 gcc_assert (ncopies
>= 1);
3195 /* Find the first insertion point in the BB. */
3196 si
= gsi_after_labels (bb
);
3198 /* Create the vector that holds the initial_value of the induction. */
3199 if (nested_in_vect_loop
)
3201 /* iv_loop is nested in the loop to be vectorized. init_expr had already
3202 been created during vectorization of previous stmts. We obtain it
3203 from the STMT_VINFO_VEC_STMT of the defining stmt. */
3204 tree iv_def
= PHI_ARG_DEF_FROM_EDGE (iv_phi
,
3205 loop_preheader_edge (iv_loop
));
3206 vec_init
= vect_get_vec_def_for_operand (iv_def
, iv_phi
, NULL
);
3210 vec
<constructor_elt
, va_gc
> *v
;
3212 /* iv_loop is the loop to be vectorized. Create:
3213 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
3214 new_var
= vect_get_new_vect_var (scalar_type
, vect_scalar_var
, "var_");
3215 new_name
= force_gimple_operand (init_expr
, &stmts
, false, new_var
);
3218 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
3219 gcc_assert (!new_bb
);
3222 vec_alloc (v
, nunits
);
3223 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
3224 for (i
= 1; i
< nunits
; i
++)
3226 /* Create: new_name_i = new_name + step_expr */
3227 enum tree_code code
= POINTER_TYPE_P (scalar_type
)
3228 ? POINTER_PLUS_EXPR
: PLUS_EXPR
;
3229 init_stmt
= gimple_build_assign_with_ops (code
, new_var
,
3230 new_name
, step_expr
);
3231 new_name
= make_ssa_name (new_var
, init_stmt
);
3232 gimple_assign_set_lhs (init_stmt
, new_name
);
3234 new_bb
= gsi_insert_on_edge_immediate (pe
, init_stmt
);
3235 gcc_assert (!new_bb
);
3237 if (dump_enabled_p ())
3239 dump_printf_loc (MSG_NOTE
, vect_location
,
3240 "created new init_stmt: ");
3241 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, init_stmt
, 0);
3243 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
3245 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
3246 new_vec
= build_constructor (vectype
, v
);
3247 vec_init
= vect_init_vector (iv_phi
, new_vec
, vectype
, NULL
);
3251 /* Create the vector that holds the step of the induction. */
3252 if (nested_in_vect_loop
)
3253 /* iv_loop is nested in the loop to be vectorized. Generate:
3254 vec_step = [S, S, S, S] */
3255 new_name
= step_expr
;
3258 /* iv_loop is the loop to be vectorized. Generate:
3259 vec_step = [VF*S, VF*S, VF*S, VF*S] */
3260 expr
= build_int_cst (TREE_TYPE (step_expr
), vf
);
3261 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
3265 t
= unshare_expr (new_name
);
3266 gcc_assert (CONSTANT_CLASS_P (new_name
));
3267 stepvectype
= get_vectype_for_scalar_type (TREE_TYPE (new_name
));
3268 gcc_assert (stepvectype
);
3269 new_vec
= build_vector_from_val (stepvectype
, t
);
3270 vec_step
= vect_init_vector (iv_phi
, new_vec
, stepvectype
, NULL
);
3273 /* Create the following def-use cycle:
3278 vec_iv = PHI <vec_init, vec_loop>
3282 vec_loop = vec_iv + vec_step; */
3284 /* Create the induction-phi that defines the induction-operand. */
3285 vec_dest
= vect_get_new_vect_var (vectype
, vect_simple_var
, "vec_iv_");
3286 induction_phi
= create_phi_node (vec_dest
, iv_loop
->header
);
3287 set_vinfo_for_stmt (induction_phi
,
3288 new_stmt_vec_info (induction_phi
, loop_vinfo
, NULL
));
3289 induc_def
= PHI_RESULT (induction_phi
);
3291 /* Create the iv update inside the loop */
3292 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, vec_dest
,
3293 induc_def
, vec_step
);
3294 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
3295 gimple_assign_set_lhs (new_stmt
, vec_def
);
3296 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3297 set_vinfo_for_stmt (new_stmt
, new_stmt_vec_info (new_stmt
, loop_vinfo
,
3300 /* Set the arguments of the phi node: */
3301 add_phi_arg (induction_phi
, vec_init
, pe
, UNKNOWN_LOCATION
);
3302 add_phi_arg (induction_phi
, vec_def
, loop_latch_edge (iv_loop
),
3306 /* In case that vectorization factor (VF) is bigger than the number
3307 of elements that we can fit in a vectype (nunits), we have to generate
3308 more than one vector stmt - i.e - we need to "unroll" the
3309 vector stmt by a factor VF/nunits. For more details see documentation
3310 in vectorizable_operation. */
3314 stmt_vec_info prev_stmt_vinfo
;
3315 /* FORNOW. This restriction should be relaxed. */
3316 gcc_assert (!nested_in_vect_loop
);
3318 /* Create the vector that holds the step of the induction. */
3319 expr
= build_int_cst (TREE_TYPE (step_expr
), nunits
);
3320 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
3322 t
= unshare_expr (new_name
);
3323 gcc_assert (CONSTANT_CLASS_P (new_name
));
3324 new_vec
= build_vector_from_val (stepvectype
, t
);
3325 vec_step
= vect_init_vector (iv_phi
, new_vec
, stepvectype
, NULL
);
3327 vec_def
= induc_def
;
3328 prev_stmt_vinfo
= vinfo_for_stmt (induction_phi
);
3329 for (i
= 1; i
< ncopies
; i
++)
3331 /* vec_i = vec_prev + vec_step */
3332 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, vec_dest
,
3334 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
3335 gimple_assign_set_lhs (new_stmt
, vec_def
);
3337 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3338 if (!useless_type_conversion_p (resvectype
, vectype
))
3340 new_stmt
= gimple_build_assign_with_ops
3342 vect_get_new_vect_var (resvectype
, vect_simple_var
,
3344 build1 (VIEW_CONVERT_EXPR
, resvectype
,
3345 gimple_assign_lhs (new_stmt
)), NULL_TREE
);
3346 gimple_assign_set_lhs (new_stmt
,
3348 (gimple_assign_lhs (new_stmt
), new_stmt
));
3349 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3351 set_vinfo_for_stmt (new_stmt
,
3352 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
3353 STMT_VINFO_RELATED_STMT (prev_stmt_vinfo
) = new_stmt
;
3354 prev_stmt_vinfo
= vinfo_for_stmt (new_stmt
);
3358 if (nested_in_vect_loop
)
3360 /* Find the loop-closed exit-phi of the induction, and record
3361 the final vector of induction results: */
3363 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
3365 if (!flow_bb_inside_loop_p (iv_loop
, gimple_bb (USE_STMT (use_p
))))
3367 exit_phi
= USE_STMT (use_p
);
3373 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (exit_phi
);
3374 /* FORNOW. Currently not supporting the case that an inner-loop induction
3375 is not used in the outer-loop (i.e. only outside the outer-loop). */
3376 gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo
)
3377 && !STMT_VINFO_LIVE_P (stmt_vinfo
));
3379 STMT_VINFO_VEC_STMT (stmt_vinfo
) = new_stmt
;
3380 if (dump_enabled_p ())
3382 dump_printf_loc (MSG_NOTE
, vect_location
,
3383 "vector of inductions after inner-loop:");
3384 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, new_stmt
, 0);
3390 if (dump_enabled_p ())
3392 dump_printf_loc (MSG_NOTE
, vect_location
,
3393 "transform induction: created def-use cycle: ");
3394 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, induction_phi
, 0);
3395 dump_printf (MSG_NOTE
, "\n");
3396 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
3397 SSA_NAME_DEF_STMT (vec_def
), 0);
3400 STMT_VINFO_VEC_STMT (phi_info
) = induction_phi
;
3401 if (!useless_type_conversion_p (resvectype
, vectype
))
3403 new_stmt
= gimple_build_assign_with_ops
3405 vect_get_new_vect_var (resvectype
, vect_simple_var
, "vec_iv_"),
3406 build1 (VIEW_CONVERT_EXPR
, resvectype
, induc_def
), NULL_TREE
);
3407 induc_def
= make_ssa_name (gimple_assign_lhs (new_stmt
), new_stmt
);
3408 gimple_assign_set_lhs (new_stmt
, induc_def
);
3409 si
= gsi_after_labels (bb
);
3410 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3411 set_vinfo_for_stmt (new_stmt
,
3412 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
3413 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_stmt
))
3414 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (induction_phi
));
3421 /* Function get_initial_def_for_reduction
3424 STMT - a stmt that performs a reduction operation in the loop.
3425 INIT_VAL - the initial value of the reduction variable
3428 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
3429 of the reduction (used for adjusting the epilog - see below).
3430 Return a vector variable, initialized according to the operation that STMT
3431 performs. This vector will be used as the initial value of the
3432 vector of partial results.
3434 Option1 (adjust in epilog): Initialize the vector as follows:
3435 add/bit or/xor: [0,0,...,0,0]
3436 mult/bit and: [1,1,...,1,1]
3437 min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
3438 and when necessary (e.g. add/mult case) let the caller know
3439 that it needs to adjust the result by init_val.
3441 Option2: Initialize the vector as follows:
3442 add/bit or/xor: [init_val,0,0,...,0]
3443 mult/bit and: [init_val,1,1,...,1]
3444 min/max/cond_expr: [init_val,init_val,...,init_val]
3445 and no adjustments are needed.
3447 For example, for the following code:
3453 STMT is 's = s + a[i]', and the reduction variable is 's'.
3454 For a vector of 4 units, we want to return either [0,0,0,init_val],
3455 or [0,0,0,0] and let the caller know that it needs to adjust
3456 the result at the end by 'init_val'.
3458 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
3459 initialization vector is simpler (same element in all entries), if
3460 ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
3462 A cost model should help decide between these two schemes. */
3465 get_initial_def_for_reduction (gimple stmt
, tree init_val
,
3466 tree
*adjustment_def
)
3468 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
3469 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
3470 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3471 tree scalar_type
= TREE_TYPE (init_val
);
3472 tree vectype
= get_vectype_for_scalar_type (scalar_type
);
3474 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3479 bool nested_in_vect_loop
= false;
3481 REAL_VALUE_TYPE real_init_val
= dconst0
;
3482 int int_init_val
= 0;
3483 gimple def_stmt
= NULL
;
3485 gcc_assert (vectype
);
3486 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3488 gcc_assert (POINTER_TYPE_P (scalar_type
) || INTEGRAL_TYPE_P (scalar_type
)
3489 || SCALAR_FLOAT_TYPE_P (scalar_type
));
3491 if (nested_in_vect_loop_p (loop
, stmt
))
3492 nested_in_vect_loop
= true;
3494 gcc_assert (loop
== (gimple_bb (stmt
))->loop_father
);
3496 /* In case of double reduction we only create a vector variable to be put
3497 in the reduction phi node. The actual statement creation is done in
3498 vect_create_epilog_for_reduction. */
3499 if (adjustment_def
&& nested_in_vect_loop
3500 && TREE_CODE (init_val
) == SSA_NAME
3501 && (def_stmt
= SSA_NAME_DEF_STMT (init_val
))
3502 && gimple_code (def_stmt
) == GIMPLE_PHI
3503 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
3504 && vinfo_for_stmt (def_stmt
)
3505 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
3506 == vect_double_reduction_def
)
3508 *adjustment_def
= NULL
;
3509 return vect_create_destination_var (init_val
, vectype
);
3512 if (TREE_CONSTANT (init_val
))
3514 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
3515 init_value
= build_real (scalar_type
, TREE_REAL_CST (init_val
));
3517 init_value
= build_int_cst (scalar_type
, TREE_INT_CST_LOW (init_val
));
3520 init_value
= init_val
;
3524 case WIDEN_SUM_EXPR
:
3532 /* ADJUSMENT_DEF is NULL when called from
3533 vect_create_epilog_for_reduction to vectorize double reduction. */
3536 if (nested_in_vect_loop
)
3537 *adjustment_def
= vect_get_vec_def_for_operand (init_val
, stmt
,
3540 *adjustment_def
= init_val
;
3543 if (code
== MULT_EXPR
)
3545 real_init_val
= dconst1
;
3549 if (code
== BIT_AND_EXPR
)
3552 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
3553 def_for_init
= build_real (scalar_type
, real_init_val
);
3555 def_for_init
= build_int_cst (scalar_type
, int_init_val
);
3557 /* Create a vector of '0' or '1' except the first element. */
3558 elts
= XALLOCAVEC (tree
, nunits
);
3559 for (i
= nunits
- 2; i
>= 0; --i
)
3560 elts
[i
+ 1] = def_for_init
;
3562 /* Option1: the first element is '0' or '1' as well. */
3565 elts
[0] = def_for_init
;
3566 init_def
= build_vector (vectype
, elts
);
3570 /* Option2: the first element is INIT_VAL. */
3572 if (TREE_CONSTANT (init_val
))
3573 init_def
= build_vector (vectype
, elts
);
3576 vec
<constructor_elt
, va_gc
> *v
;
3577 vec_alloc (v
, nunits
);
3578 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, init_val
);
3579 for (i
= 1; i
< nunits
; ++i
)
3580 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[i
]);
3581 init_def
= build_constructor (vectype
, v
);
3591 *adjustment_def
= NULL_TREE
;
3592 init_def
= vect_get_vec_def_for_operand (init_val
, stmt
, NULL
);
3596 init_def
= build_vector_from_val (vectype
, init_value
);
3607 /* Function vect_create_epilog_for_reduction
3609 Create code at the loop-epilog to finalize the result of a reduction
3612 VECT_DEFS is list of vector of partial results, i.e., the lhs's of vector
3613 reduction statements.
3614 STMT is the scalar reduction stmt that is being vectorized.
3615 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
3616 number of elements that we can fit in a vectype (nunits). In this case
3617 we have to generate more than one vector stmt - i.e - we need to "unroll"
3618 the vector stmt by a factor VF/nunits. For more details see documentation
3619 in vectorizable_operation.
3620 REDUC_CODE is the tree-code for the epilog reduction.
3621 REDUCTION_PHIS is a list of the phi-nodes that carry the reduction
3623 REDUC_INDEX is the index of the operand in the right hand side of the
3624 statement that is defined by REDUCTION_PHI.
3625 DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
3626 SLP_NODE is an SLP node containing a group of reduction statements. The
3627 first one in this group is STMT.
3630 1. Creates the reduction def-use cycles: sets the arguments for
3632 The loop-entry argument is the vectorized initial-value of the reduction.
3633 The loop-latch argument is taken from VECT_DEFS - the vector of partial
3635 2. "Reduces" each vector of partial results VECT_DEFS into a single result,
3636 by applying the operation specified by REDUC_CODE if available, or by
3637 other means (whole-vector shifts or a scalar loop).
3638 The function also creates a new phi node at the loop exit to preserve
3639 loop-closed form, as illustrated below.
3641 The flow at the entry to this function:
3644 vec_def = phi <null, null> # REDUCTION_PHI
3645 VECT_DEF = vector_stmt # vectorized form of STMT
3646 s_loop = scalar_stmt # (scalar) STMT
3648 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3652 The above is transformed by this function into:
3655 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3656 VECT_DEF = vector_stmt # vectorized form of STMT
3657 s_loop = scalar_stmt # (scalar) STMT
3659 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3660 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3661 v_out2 = reduce <v_out1>
3662 s_out3 = extract_field <v_out2, 0>
3663 s_out4 = adjust_result <s_out3>
3669 vect_create_epilog_for_reduction (vec
<tree
> vect_defs
, gimple stmt
,
3670 int ncopies
, enum tree_code reduc_code
,
3671 vec
<gimple
> reduction_phis
,
3672 int reduc_index
, bool double_reduc
,
3675 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3676 stmt_vec_info prev_phi_info
;
3678 enum machine_mode mode
;
3679 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3680 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
), *outer_loop
= NULL
;
3681 basic_block exit_bb
;
3684 gimple new_phi
= NULL
, phi
;
3685 gimple_stmt_iterator exit_gsi
;
3687 tree new_temp
= NULL_TREE
, new_dest
, new_name
, new_scalar_dest
;
3688 gimple epilog_stmt
= NULL
;
3689 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3691 tree bitsize
, bitpos
;
3692 tree adjustment_def
= NULL
;
3693 tree vec_initial_def
= NULL
;
3694 tree reduction_op
, expr
, def
;
3695 tree orig_name
, scalar_result
;
3696 imm_use_iterator imm_iter
, phi_imm_iter
;
3697 use_operand_p use_p
, phi_use_p
;
3698 bool extract_scalar_result
= false;
3699 gimple use_stmt
, orig_stmt
, reduction_phi
= NULL
;
3700 bool nested_in_vect_loop
= false;
3701 vec
<gimple
> new_phis
= vNULL
;
3702 vec
<gimple
> inner_phis
= vNULL
;
3703 enum vect_def_type dt
= vect_unknown_def_type
;
3705 vec
<tree
> scalar_results
= vNULL
;
3706 unsigned int group_size
= 1, k
, ratio
;
3707 vec
<tree
> vec_initial_defs
= vNULL
;
3709 bool slp_reduc
= false;
3710 tree new_phi_result
;
3711 gimple inner_phi
= NULL
;
3714 group_size
= SLP_TREE_SCALAR_STMTS (slp_node
).length ();
3716 if (nested_in_vect_loop_p (loop
, stmt
))
3720 nested_in_vect_loop
= true;
3721 gcc_assert (!slp_node
);
3724 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3726 case GIMPLE_SINGLE_RHS
:
3727 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
))
3729 reduction_op
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), reduc_index
);
3731 case GIMPLE_UNARY_RHS
:
3732 reduction_op
= gimple_assign_rhs1 (stmt
);
3734 case GIMPLE_BINARY_RHS
:
3735 reduction_op
= reduc_index
?
3736 gimple_assign_rhs2 (stmt
) : gimple_assign_rhs1 (stmt
);
3738 case GIMPLE_TERNARY_RHS
:
3739 reduction_op
= gimple_op (stmt
, reduc_index
+ 1);
3745 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
3746 gcc_assert (vectype
);
3747 mode
= TYPE_MODE (vectype
);
3749 /* 1. Create the reduction def-use cycle:
3750 Set the arguments of REDUCTION_PHIS, i.e., transform
3753 vec_def = phi <null, null> # REDUCTION_PHI
3754 VECT_DEF = vector_stmt # vectorized form of STMT
3760 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3761 VECT_DEF = vector_stmt # vectorized form of STMT
3764 (in case of SLP, do it for all the phis). */
3766 /* Get the loop-entry arguments. */
3768 vect_get_vec_defs (reduction_op
, NULL_TREE
, stmt
, &vec_initial_defs
,
3769 NULL
, slp_node
, reduc_index
);
3772 vec_initial_defs
.create (1);
3773 /* For the case of reduction, vect_get_vec_def_for_operand returns
3774 the scalar def before the loop, that defines the initial value
3775 of the reduction variable. */
3776 vec_initial_def
= vect_get_vec_def_for_operand (reduction_op
, stmt
,
3778 vec_initial_defs
.quick_push (vec_initial_def
);
3781 /* Set phi nodes arguments. */
3782 FOR_EACH_VEC_ELT (reduction_phis
, i
, phi
)
3784 tree vec_init_def
= vec_initial_defs
[i
];
3785 tree def
= vect_defs
[i
];
3786 for (j
= 0; j
< ncopies
; j
++)
3788 /* Set the loop-entry arg of the reduction-phi. */
3789 add_phi_arg (phi
, vec_init_def
, loop_preheader_edge (loop
),
3792 /* Set the loop-latch arg for the reduction-phi. */
3794 def
= vect_get_vec_def_for_stmt_copy (vect_unknown_def_type
, def
);
3796 add_phi_arg (phi
, def
, loop_latch_edge (loop
), UNKNOWN_LOCATION
);
3798 if (dump_enabled_p ())
3800 dump_printf_loc (MSG_NOTE
, vect_location
,
3801 "transform reduction: created def-use cycle: ");
3802 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
3803 dump_printf (MSG_NOTE
, "\n");
3804 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, SSA_NAME_DEF_STMT (def
), 0);
3807 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
3811 vec_initial_defs
.release ();
3813 /* 2. Create epilog code.
3814 The reduction epilog code operates across the elements of the vector
3815 of partial results computed by the vectorized loop.
3816 The reduction epilog code consists of:
3818 step 1: compute the scalar result in a vector (v_out2)
3819 step 2: extract the scalar result (s_out3) from the vector (v_out2)
3820 step 3: adjust the scalar result (s_out3) if needed.
3822 Step 1 can be accomplished using one the following three schemes:
3823 (scheme 1) using reduc_code, if available.
3824 (scheme 2) using whole-vector shifts, if available.
3825 (scheme 3) using a scalar loop. In this case steps 1+2 above are
3828 The overall epilog code looks like this:
3830 s_out0 = phi <s_loop> # original EXIT_PHI
3831 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3832 v_out2 = reduce <v_out1> # step 1
3833 s_out3 = extract_field <v_out2, 0> # step 2
3834 s_out4 = adjust_result <s_out3> # step 3
3836 (step 3 is optional, and steps 1 and 2 may be combined).
3837 Lastly, the uses of s_out0 are replaced by s_out4. */
3840 /* 2.1 Create new loop-exit-phis to preserve loop-closed form:
3841 v_out1 = phi <VECT_DEF>
3842 Store them in NEW_PHIS. */
3844 exit_bb
= single_exit (loop
)->dest
;
3845 prev_phi_info
= NULL
;
3846 new_phis
.create (vect_defs
.length ());
3847 FOR_EACH_VEC_ELT (vect_defs
, i
, def
)
3849 for (j
= 0; j
< ncopies
; j
++)
3851 tree new_def
= copy_ssa_name (def
, NULL
);
3852 phi
= create_phi_node (new_def
, exit_bb
);
3853 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, loop_vinfo
, NULL
));
3855 new_phis
.quick_push (phi
);
3858 def
= vect_get_vec_def_for_stmt_copy (dt
, def
);
3859 STMT_VINFO_RELATED_STMT (prev_phi_info
) = phi
;
3862 SET_PHI_ARG_DEF (phi
, single_exit (loop
)->dest_idx
, def
);
3863 prev_phi_info
= vinfo_for_stmt (phi
);
3867 /* The epilogue is created for the outer-loop, i.e., for the loop being
3868 vectorized. Create exit phis for the outer loop. */
3872 exit_bb
= single_exit (loop
)->dest
;
3873 inner_phis
.create (vect_defs
.length ());
3874 FOR_EACH_VEC_ELT (new_phis
, i
, phi
)
3876 tree new_result
= copy_ssa_name (PHI_RESULT (phi
), NULL
);
3877 gimple outer_phi
= create_phi_node (new_result
, exit_bb
);
3878 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
3880 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
3882 inner_phis
.quick_push (phi
);
3883 new_phis
[i
] = outer_phi
;
3884 prev_phi_info
= vinfo_for_stmt (outer_phi
);
3885 while (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
)))
3887 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
3888 new_result
= copy_ssa_name (PHI_RESULT (phi
), NULL
);
3889 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 STMT_VINFO_RELATED_STMT (prev_phi_info
) = outer_phi
;
3895 prev_phi_info
= vinfo_for_stmt (outer_phi
);
3900 exit_gsi
= gsi_after_labels (exit_bb
);
3902 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
3903 (i.e. when reduc_code is not available) and in the final adjustment
3904 code (if needed). Also get the original scalar reduction variable as
3905 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
3906 represents a reduction pattern), the tree-code and scalar-def are
3907 taken from the original stmt that the pattern-stmt (STMT) replaces.
3908 Otherwise (it is a regular reduction) - the tree-code and scalar-def
3909 are taken from STMT. */
3911 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
3914 /* Regular reduction */
3919 /* Reduction pattern */
3920 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (orig_stmt
);
3921 gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
));
3922 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo
) == stmt
);
3925 code
= gimple_assign_rhs_code (orig_stmt
);
3926 /* For MINUS_EXPR the initial vector is [init_val,0,...,0], therefore,
3927 partial results are added and not subtracted. */
3928 if (code
== MINUS_EXPR
)
3931 scalar_dest
= gimple_assign_lhs (orig_stmt
);
3932 scalar_type
= TREE_TYPE (scalar_dest
);
3933 scalar_results
.create (group_size
);
3934 new_scalar_dest
= vect_create_destination_var (scalar_dest
, NULL
);
3935 bitsize
= TYPE_SIZE (scalar_type
);
3937 /* In case this is a reduction in an inner-loop while vectorizing an outer
3938 loop - we don't need to extract a single scalar result at the end of the
3939 inner-loop (unless it is double reduction, i.e., the use of reduction is
3940 outside the outer-loop). The final vector of partial results will be used
3941 in the vectorized outer-loop, or reduced to a scalar result at the end of
3943 if (nested_in_vect_loop
&& !double_reduc
)
3944 goto vect_finalize_reduction
;
3946 /* SLP reduction without reduction chain, e.g.,
3950 b2 = operation (b1) */
3951 slp_reduc
= (slp_node
&& !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)));
3953 /* In case of reduction chain, e.g.,
3956 a3 = operation (a2),
3958 we may end up with more than one vector result. Here we reduce them to
3960 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
3962 tree first_vect
= PHI_RESULT (new_phis
[0]);
3964 gimple new_vec_stmt
= NULL
;
3966 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
3967 for (k
= 1; k
< new_phis
.length (); k
++)
3969 gimple next_phi
= new_phis
[k
];
3970 tree second_vect
= PHI_RESULT (next_phi
);
3972 tmp
= build2 (code
, vectype
, first_vect
, second_vect
);
3973 new_vec_stmt
= gimple_build_assign (vec_dest
, tmp
);
3974 first_vect
= make_ssa_name (vec_dest
, new_vec_stmt
);
3975 gimple_assign_set_lhs (new_vec_stmt
, first_vect
);
3976 gsi_insert_before (&exit_gsi
, new_vec_stmt
, GSI_SAME_STMT
);
3979 new_phi_result
= first_vect
;
3982 new_phis
.truncate (0);
3983 new_phis
.safe_push (new_vec_stmt
);
3987 new_phi_result
= PHI_RESULT (new_phis
[0]);
3989 /* 2.3 Create the reduction code, using one of the three schemes described
3990 above. In SLP we simply need to extract all the elements from the
3991 vector (without reducing them), so we use scalar shifts. */
3992 if (reduc_code
!= ERROR_MARK
&& !slp_reduc
)
3996 /*** Case 1: Create:
3997 v_out2 = reduc_expr <v_out1> */
3999 if (dump_enabled_p ())
4000 dump_printf_loc (MSG_NOTE
, vect_location
,
4001 "Reduce using direct vector reduction.");
4003 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4004 tmp
= build1 (reduc_code
, vectype
, new_phi_result
);
4005 epilog_stmt
= gimple_build_assign (vec_dest
, tmp
);
4006 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
4007 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4008 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4010 extract_scalar_result
= true;
4014 enum tree_code shift_code
= ERROR_MARK
;
4015 bool have_whole_vector_shift
= true;
4017 int element_bitsize
= tree_low_cst (bitsize
, 1);
4018 int vec_size_in_bits
= tree_low_cst (TYPE_SIZE (vectype
), 1);
4021 if (optab_handler (vec_shr_optab
, mode
) != CODE_FOR_nothing
)
4022 shift_code
= VEC_RSHIFT_EXPR
;
4024 have_whole_vector_shift
= false;
4026 /* Regardless of whether we have a whole vector shift, if we're
4027 emulating the operation via tree-vect-generic, we don't want
4028 to use it. Only the first round of the reduction is likely
4029 to still be profitable via emulation. */
4030 /* ??? It might be better to emit a reduction tree code here, so that
4031 tree-vect-generic can expand the first round via bit tricks. */
4032 if (!VECTOR_MODE_P (mode
))
4033 have_whole_vector_shift
= false;
4036 optab optab
= optab_for_tree_code (code
, vectype
, optab_default
);
4037 if (optab_handler (optab
, mode
) == CODE_FOR_nothing
)
4038 have_whole_vector_shift
= false;
4041 if (have_whole_vector_shift
&& !slp_reduc
)
4043 /*** Case 2: Create:
4044 for (offset = VS/2; offset >= element_size; offset/=2)
4046 Create: va' = vec_shift <va, offset>
4047 Create: va = vop <va, va'>
4050 if (dump_enabled_p ())
4051 dump_printf_loc (MSG_NOTE
, vect_location
,
4052 "Reduce using vector shifts");
4054 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4055 new_temp
= new_phi_result
;
4056 for (bit_offset
= vec_size_in_bits
/2;
4057 bit_offset
>= element_bitsize
;
4060 tree bitpos
= size_int (bit_offset
);
4062 epilog_stmt
= gimple_build_assign_with_ops (shift_code
,
4063 vec_dest
, new_temp
, bitpos
);
4064 new_name
= make_ssa_name (vec_dest
, epilog_stmt
);
4065 gimple_assign_set_lhs (epilog_stmt
, new_name
);
4066 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4068 epilog_stmt
= gimple_build_assign_with_ops (code
, vec_dest
,
4069 new_name
, new_temp
);
4070 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
4071 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4072 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4075 extract_scalar_result
= true;
4081 /*** Case 3: Create:
4082 s = extract_field <v_out2, 0>
4083 for (offset = element_size;
4084 offset < vector_size;
4085 offset += element_size;)
4087 Create: s' = extract_field <v_out2, offset>
4088 Create: s = op <s, s'> // For non SLP cases
4091 if (dump_enabled_p ())
4092 dump_printf_loc (MSG_NOTE
, vect_location
,
4093 "Reduce using scalar code. ");
4095 vec_size_in_bits
= tree_low_cst (TYPE_SIZE (vectype
), 1);
4096 FOR_EACH_VEC_ELT (new_phis
, i
, new_phi
)
4098 if (gimple_code (new_phi
) == GIMPLE_PHI
)
4099 vec_temp
= PHI_RESULT (new_phi
);
4101 vec_temp
= gimple_assign_lhs (new_phi
);
4102 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
, bitsize
,
4104 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4105 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4106 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4107 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4109 /* In SLP we don't need to apply reduction operation, so we just
4110 collect s' values in SCALAR_RESULTS. */
4112 scalar_results
.safe_push (new_temp
);
4114 for (bit_offset
= element_bitsize
;
4115 bit_offset
< vec_size_in_bits
;
4116 bit_offset
+= element_bitsize
)
4118 tree bitpos
= bitsize_int (bit_offset
);
4119 tree rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
,
4122 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4123 new_name
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4124 gimple_assign_set_lhs (epilog_stmt
, new_name
);
4125 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4129 /* In SLP we don't need to apply reduction operation, so
4130 we just collect s' values in SCALAR_RESULTS. */
4131 new_temp
= new_name
;
4132 scalar_results
.safe_push (new_name
);
4136 epilog_stmt
= gimple_build_assign_with_ops (code
,
4137 new_scalar_dest
, new_name
, new_temp
);
4138 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4139 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4140 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4145 /* The only case where we need to reduce scalar results in SLP, is
4146 unrolling. If the size of SCALAR_RESULTS is greater than
4147 GROUP_SIZE, we reduce them combining elements modulo
4151 tree res
, first_res
, new_res
;
4154 /* Reduce multiple scalar results in case of SLP unrolling. */
4155 for (j
= group_size
; scalar_results
.iterate (j
, &res
);
4158 first_res
= scalar_results
[j
% group_size
];
4159 new_stmt
= gimple_build_assign_with_ops (code
,
4160 new_scalar_dest
, first_res
, res
);
4161 new_res
= make_ssa_name (new_scalar_dest
, new_stmt
);
4162 gimple_assign_set_lhs (new_stmt
, new_res
);
4163 gsi_insert_before (&exit_gsi
, new_stmt
, GSI_SAME_STMT
);
4164 scalar_results
[j
% group_size
] = new_res
;
4168 /* Not SLP - we have one scalar to keep in SCALAR_RESULTS. */
4169 scalar_results
.safe_push (new_temp
);
4171 extract_scalar_result
= false;
4175 /* 2.4 Extract the final scalar result. Create:
4176 s_out3 = extract_field <v_out2, bitpos> */
4178 if (extract_scalar_result
)
4182 if (dump_enabled_p ())
4183 dump_printf_loc (MSG_NOTE
, vect_location
,
4184 "extract scalar result");
4186 if (BYTES_BIG_ENDIAN
)
4187 bitpos
= size_binop (MULT_EXPR
,
4188 bitsize_int (TYPE_VECTOR_SUBPARTS (vectype
) - 1),
4189 TYPE_SIZE (scalar_type
));
4191 bitpos
= bitsize_zero_node
;
4193 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, new_temp
, bitsize
, bitpos
);
4194 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4195 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4196 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4197 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4198 scalar_results
.safe_push (new_temp
);
4201 vect_finalize_reduction
:
4206 /* 2.5 Adjust the final result by the initial value of the reduction
4207 variable. (When such adjustment is not needed, then
4208 'adjustment_def' is zero). For example, if code is PLUS we create:
4209 new_temp = loop_exit_def + adjustment_def */
4213 gcc_assert (!slp_reduc
);
4214 if (nested_in_vect_loop
)
4216 new_phi
= new_phis
[0];
4217 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) == VECTOR_TYPE
);
4218 expr
= build2 (code
, vectype
, PHI_RESULT (new_phi
), adjustment_def
);
4219 new_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4223 new_temp
= scalar_results
[0];
4224 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) != VECTOR_TYPE
);
4225 expr
= build2 (code
, scalar_type
, new_temp
, adjustment_def
);
4226 new_dest
= vect_create_destination_var (scalar_dest
, scalar_type
);
4229 epilog_stmt
= gimple_build_assign (new_dest
, expr
);
4230 new_temp
= make_ssa_name (new_dest
, epilog_stmt
);
4231 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4232 SSA_NAME_DEF_STMT (new_temp
) = epilog_stmt
;
4233 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4234 if (nested_in_vect_loop
)
4236 set_vinfo_for_stmt (epilog_stmt
,
4237 new_stmt_vec_info (epilog_stmt
, loop_vinfo
,
4239 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (epilog_stmt
)) =
4240 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_phi
));
4243 scalar_results
.quick_push (new_temp
);
4245 scalar_results
[0] = new_temp
;
4248 scalar_results
[0] = new_temp
;
4250 new_phis
[0] = epilog_stmt
;
4253 /* 2.6 Handle the loop-exit phis. Replace the uses of scalar loop-exit
4254 phis with new adjusted scalar results, i.e., replace use <s_out0>
4259 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4260 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4261 v_out2 = reduce <v_out1>
4262 s_out3 = extract_field <v_out2, 0>
4263 s_out4 = adjust_result <s_out3>
4270 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4271 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4272 v_out2 = reduce <v_out1>
4273 s_out3 = extract_field <v_out2, 0>
4274 s_out4 = adjust_result <s_out3>
4279 /* In SLP reduction chain we reduce vector results into one vector if
4280 necessary, hence we set here GROUP_SIZE to 1. SCALAR_DEST is the LHS of
4281 the last stmt in the reduction chain, since we are looking for the loop
4283 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4285 scalar_dest
= gimple_assign_lhs (
4286 SLP_TREE_SCALAR_STMTS (slp_node
)[group_size
- 1]);
4290 /* In SLP we may have several statements in NEW_PHIS and REDUCTION_PHIS (in
4291 case that GROUP_SIZE is greater than vectorization factor). Therefore, we
4292 need to match SCALAR_RESULTS with corresponding statements. The first
4293 (GROUP_SIZE / number of new vector stmts) scalar results correspond to
4294 the first vector stmt, etc.
4295 (RATIO is equal to (GROUP_SIZE / number of new vector stmts)). */
4296 if (group_size
> new_phis
.length ())
4298 ratio
= group_size
/ new_phis
.length ();
4299 gcc_assert (!(group_size
% new_phis
.length ()));
4304 for (k
= 0; k
< group_size
; k
++)
4308 epilog_stmt
= new_phis
[k
/ ratio
];
4309 reduction_phi
= reduction_phis
[k
/ ratio
];
4311 inner_phi
= inner_phis
[k
/ ratio
];
4316 gimple current_stmt
= SLP_TREE_SCALAR_STMTS (slp_node
)[k
];
4318 orig_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (current_stmt
));
4319 /* SLP statements can't participate in patterns. */
4320 gcc_assert (!orig_stmt
);
4321 scalar_dest
= gimple_assign_lhs (current_stmt
);
4325 /* Find the loop-closed-use at the loop exit of the original scalar
4326 result. (The reduction result is expected to have two immediate uses -
4327 one at the latch block, and one at the loop exit). */
4328 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
4329 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
4330 phis
.safe_push (USE_STMT (use_p
));
4332 /* We expect to have found an exit_phi because of loop-closed-ssa
4334 gcc_assert (!phis
.is_empty ());
4336 FOR_EACH_VEC_ELT (phis
, i
, exit_phi
)
4340 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
4343 /* FORNOW. Currently not supporting the case that an inner-loop
4344 reduction is not used in the outer-loop (but only outside the
4345 outer-loop), unless it is double reduction. */
4346 gcc_assert ((STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
4347 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
))
4350 STMT_VINFO_VEC_STMT (exit_phi_vinfo
) = epilog_stmt
;
4352 || STMT_VINFO_DEF_TYPE (exit_phi_vinfo
)
4353 != vect_double_reduction_def
)
4356 /* Handle double reduction:
4358 stmt1: s1 = phi <s0, s2> - double reduction phi (outer loop)
4359 stmt2: s3 = phi <s1, s4> - (regular) reduc phi (inner loop)
4360 stmt3: s4 = use (s3) - (regular) reduc stmt (inner loop)
4361 stmt4: s2 = phi <s4> - double reduction stmt (outer loop)
4363 At that point the regular reduction (stmt2 and stmt3) is
4364 already vectorized, as well as the exit phi node, stmt4.
4365 Here we vectorize the phi node of double reduction, stmt1, and
4366 update all relevant statements. */
4368 /* Go through all the uses of s2 to find double reduction phi
4369 node, i.e., stmt1 above. */
4370 orig_name
= PHI_RESULT (exit_phi
);
4371 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
4373 stmt_vec_info use_stmt_vinfo
;
4374 stmt_vec_info new_phi_vinfo
;
4375 tree vect_phi_init
, preheader_arg
, vect_phi_res
, init_def
;
4376 basic_block bb
= gimple_bb (use_stmt
);
4379 /* Check that USE_STMT is really double reduction phi
4381 if (gimple_code (use_stmt
) != GIMPLE_PHI
4382 || gimple_phi_num_args (use_stmt
) != 2
4383 || bb
->loop_father
!= outer_loop
)
4385 use_stmt_vinfo
= vinfo_for_stmt (use_stmt
);
4387 || STMT_VINFO_DEF_TYPE (use_stmt_vinfo
)
4388 != vect_double_reduction_def
)
4391 /* Create vector phi node for double reduction:
4392 vs1 = phi <vs0, vs2>
4393 vs1 was created previously in this function by a call to
4394 vect_get_vec_def_for_operand and is stored in
4396 vs2 is defined by INNER_PHI, the vectorized EXIT_PHI;
4397 vs0 is created here. */
4399 /* Create vector phi node. */
4400 vect_phi
= create_phi_node (vec_initial_def
, bb
);
4401 new_phi_vinfo
= new_stmt_vec_info (vect_phi
,
4402 loop_vec_info_for_loop (outer_loop
), NULL
);
4403 set_vinfo_for_stmt (vect_phi
, new_phi_vinfo
);
4405 /* Create vs0 - initial def of the double reduction phi. */
4406 preheader_arg
= PHI_ARG_DEF_FROM_EDGE (use_stmt
,
4407 loop_preheader_edge (outer_loop
));
4408 init_def
= get_initial_def_for_reduction (stmt
,
4409 preheader_arg
, NULL
);
4410 vect_phi_init
= vect_init_vector (use_stmt
, init_def
,
4413 /* Update phi node arguments with vs0 and vs2. */
4414 add_phi_arg (vect_phi
, vect_phi_init
,
4415 loop_preheader_edge (outer_loop
),
4417 add_phi_arg (vect_phi
, PHI_RESULT (inner_phi
),
4418 loop_latch_edge (outer_loop
), UNKNOWN_LOCATION
);
4419 if (dump_enabled_p ())
4421 dump_printf_loc (MSG_NOTE
, vect_location
,
4422 "created double reduction phi node: ");
4423 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, vect_phi
, 0);
4426 vect_phi_res
= PHI_RESULT (vect_phi
);
4428 /* Replace the use, i.e., set the correct vs1 in the regular
4429 reduction phi node. FORNOW, NCOPIES is always 1, so the
4430 loop is redundant. */
4431 use
= reduction_phi
;
4432 for (j
= 0; j
< ncopies
; j
++)
4434 edge pr_edge
= loop_preheader_edge (loop
);
4435 SET_PHI_ARG_DEF (use
, pr_edge
->dest_idx
, vect_phi_res
);
4436 use
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use
));
4443 if (nested_in_vect_loop
)
4452 /* Find the loop-closed-use at the loop exit of the original scalar
4453 result. (The reduction result is expected to have two immediate uses,
4454 one at the latch block, and one at the loop exit). For double
4455 reductions we are looking for exit phis of the outer loop. */
4456 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
4458 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
4459 phis
.safe_push (USE_STMT (use_p
));
4462 if (double_reduc
&& gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
4464 tree phi_res
= PHI_RESULT (USE_STMT (use_p
));
4466 FOR_EACH_IMM_USE_FAST (phi_use_p
, phi_imm_iter
, phi_res
)
4468 if (!flow_bb_inside_loop_p (loop
,
4469 gimple_bb (USE_STMT (phi_use_p
))))
4470 phis
.safe_push (USE_STMT (phi_use_p
));
4476 FOR_EACH_VEC_ELT (phis
, i
, exit_phi
)
4478 /* Replace the uses: */
4479 orig_name
= PHI_RESULT (exit_phi
);
4480 scalar_result
= scalar_results
[k
];
4481 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
4482 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
4483 SET_USE (use_p
, scalar_result
);
4489 scalar_results
.release ();
4490 new_phis
.release ();
4494 /* Function vectorizable_reduction.
4496 Check if STMT performs a reduction operation that can be vectorized.
4497 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4498 stmt to replace it, put it in VEC_STMT, and insert it at GSI.
4499 Return FALSE if not a vectorizable STMT, TRUE otherwise.
4501 This function also handles reduction idioms (patterns) that have been
4502 recognized in advance during vect_pattern_recog. In this case, STMT may be
4504 X = pattern_expr (arg0, arg1, ..., X)
4505 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
4506 sequence that had been detected and replaced by the pattern-stmt (STMT).
4508 In some cases of reduction patterns, the type of the reduction variable X is
4509 different than the type of the other arguments of STMT.
4510 In such cases, the vectype that is used when transforming STMT into a vector
4511 stmt is different than the vectype that is used to determine the
4512 vectorization factor, because it consists of a different number of elements
4513 than the actual number of elements that are being operated upon in parallel.
4515 For example, consider an accumulation of shorts into an int accumulator.
4516 On some targets it's possible to vectorize this pattern operating on 8
4517 shorts at a time (hence, the vectype for purposes of determining the
4518 vectorization factor should be V8HI); on the other hand, the vectype that
4519 is used to create the vector form is actually V4SI (the type of the result).
4521 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
4522 indicates what is the actual level of parallelism (V8HI in the example), so
4523 that the right vectorization factor would be derived. This vectype
4524 corresponds to the type of arguments to the reduction stmt, and should *NOT*
4525 be used to create the vectorized stmt. The right vectype for the vectorized
4526 stmt is obtained from the type of the result X:
4527 get_vectype_for_scalar_type (TREE_TYPE (X))
4529 This means that, contrary to "regular" reductions (or "regular" stmts in
4530 general), the following equation:
4531 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
4532 does *NOT* necessarily hold for reduction patterns. */
4535 vectorizable_reduction (gimple stmt
, gimple_stmt_iterator
*gsi
,
4536 gimple
*vec_stmt
, slp_tree slp_node
)
4540 tree loop_vec_def0
= NULL_TREE
, loop_vec_def1
= NULL_TREE
;
4541 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
4542 tree vectype_out
= STMT_VINFO_VECTYPE (stmt_info
);
4543 tree vectype_in
= NULL_TREE
;
4544 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
4545 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4546 enum tree_code code
, orig_code
, epilog_reduc_code
;
4547 enum machine_mode vec_mode
;
4549 optab optab
, reduc_optab
;
4550 tree new_temp
= NULL_TREE
;
4553 enum vect_def_type dt
;
4554 gimple new_phi
= NULL
;
4558 stmt_vec_info orig_stmt_info
;
4559 tree expr
= NULL_TREE
;
4563 stmt_vec_info prev_stmt_info
, prev_phi_info
;
4564 bool single_defuse_cycle
= false;
4565 tree reduc_def
= NULL_TREE
;
4566 gimple new_stmt
= NULL
;
4569 bool nested_cycle
= false, found_nested_cycle_def
= false;
4570 gimple reduc_def_stmt
= NULL
;
4571 /* The default is that the reduction variable is the last in statement. */
4572 int reduc_index
= 2;
4573 bool double_reduc
= false, dummy
;
4575 struct loop
* def_stmt_loop
, *outer_loop
= NULL
;
4577 gimple def_arg_stmt
;
4578 vec
<tree
> vec_oprnds0
= vNULL
;
4579 vec
<tree
> vec_oprnds1
= vNULL
;
4580 vec
<tree
> vect_defs
= vNULL
;
4581 vec
<gimple
> phis
= vNULL
;
4583 tree def0
, def1
, tem
, op0
, op1
= NULL_TREE
;
4585 /* In case of reduction chain we switch to the first stmt in the chain, but
4586 we don't update STMT_INFO, since only the last stmt is marked as reduction
4587 and has reduction properties. */
4588 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4589 stmt
= GROUP_FIRST_ELEMENT (stmt_info
);
4591 if (nested_in_vect_loop_p (loop
, stmt
))
4595 nested_cycle
= true;
4598 /* 1. Is vectorizable reduction? */
4599 /* Not supportable if the reduction variable is used in the loop, unless
4600 it's a reduction chain. */
4601 if (STMT_VINFO_RELEVANT (stmt_info
) > vect_used_in_outer
4602 && !GROUP_FIRST_ELEMENT (stmt_info
))
4605 /* Reductions that are not used even in an enclosing outer-loop,
4606 are expected to be "live" (used out of the loop). */
4607 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
4608 && !STMT_VINFO_LIVE_P (stmt_info
))
4611 /* Make sure it was already recognized as a reduction computation. */
4612 if (STMT_VINFO_DEF_TYPE (stmt_info
) != vect_reduction_def
4613 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_nested_cycle
)
4616 /* 2. Has this been recognized as a reduction pattern?
4618 Check if STMT represents a pattern that has been recognized
4619 in earlier analysis stages. For stmts that represent a pattern,
4620 the STMT_VINFO_RELATED_STMT field records the last stmt in
4621 the original sequence that constitutes the pattern. */
4623 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
4626 orig_stmt_info
= vinfo_for_stmt (orig_stmt
);
4627 gcc_assert (STMT_VINFO_IN_PATTERN_P (orig_stmt_info
));
4628 gcc_assert (!STMT_VINFO_IN_PATTERN_P (stmt_info
));
4631 /* 3. Check the operands of the operation. The first operands are defined
4632 inside the loop body. The last operand is the reduction variable,
4633 which is defined by the loop-header-phi. */
4635 gcc_assert (is_gimple_assign (stmt
));
4638 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
4640 case GIMPLE_SINGLE_RHS
:
4641 op_type
= TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
));
4642 if (op_type
== ternary_op
)
4644 tree rhs
= gimple_assign_rhs1 (stmt
);
4645 ops
[0] = TREE_OPERAND (rhs
, 0);
4646 ops
[1] = TREE_OPERAND (rhs
, 1);
4647 ops
[2] = TREE_OPERAND (rhs
, 2);
4648 code
= TREE_CODE (rhs
);
4654 case GIMPLE_BINARY_RHS
:
4655 code
= gimple_assign_rhs_code (stmt
);
4656 op_type
= TREE_CODE_LENGTH (code
);
4657 gcc_assert (op_type
== binary_op
);
4658 ops
[0] = gimple_assign_rhs1 (stmt
);
4659 ops
[1] = gimple_assign_rhs2 (stmt
);
4662 case GIMPLE_TERNARY_RHS
:
4663 code
= gimple_assign_rhs_code (stmt
);
4664 op_type
= TREE_CODE_LENGTH (code
);
4665 gcc_assert (op_type
== ternary_op
);
4666 ops
[0] = gimple_assign_rhs1 (stmt
);
4667 ops
[1] = gimple_assign_rhs2 (stmt
);
4668 ops
[2] = gimple_assign_rhs3 (stmt
);
4671 case GIMPLE_UNARY_RHS
:
4678 if (code
== COND_EXPR
&& slp_node
)
4681 scalar_dest
= gimple_assign_lhs (stmt
);
4682 scalar_type
= TREE_TYPE (scalar_dest
);
4683 if (!POINTER_TYPE_P (scalar_type
) && !INTEGRAL_TYPE_P (scalar_type
)
4684 && !SCALAR_FLOAT_TYPE_P (scalar_type
))
4687 /* Do not try to vectorize bit-precision reductions. */
4688 if ((TYPE_PRECISION (scalar_type
)
4689 != GET_MODE_PRECISION (TYPE_MODE (scalar_type
))))
4692 /* All uses but the last are expected to be defined in the loop.
4693 The last use is the reduction variable. In case of nested cycle this
4694 assumption is not true: we use reduc_index to record the index of the
4695 reduction variable. */
4696 for (i
= 0; i
< op_type
-1; i
++)
4698 /* The condition of COND_EXPR is checked in vectorizable_condition(). */
4699 if (i
== 0 && code
== COND_EXPR
)
4702 is_simple_use
= vect_is_simple_use_1 (ops
[i
], stmt
, loop_vinfo
, NULL
,
4703 &def_stmt
, &def
, &dt
, &tem
);
4706 gcc_assert (is_simple_use
);
4708 if (dt
!= vect_internal_def
4709 && dt
!= vect_external_def
4710 && dt
!= vect_constant_def
4711 && dt
!= vect_induction_def
4712 && !(dt
== vect_nested_cycle
&& nested_cycle
))
4715 if (dt
== vect_nested_cycle
)
4717 found_nested_cycle_def
= true;
4718 reduc_def_stmt
= def_stmt
;
4723 is_simple_use
= vect_is_simple_use_1 (ops
[i
], stmt
, loop_vinfo
, NULL
,
4724 &def_stmt
, &def
, &dt
, &tem
);
4727 gcc_assert (is_simple_use
);
4728 gcc_assert (dt
== vect_reduction_def
4729 || dt
== vect_nested_cycle
4730 || ((dt
== vect_internal_def
|| dt
== vect_external_def
4731 || dt
== vect_constant_def
|| dt
== vect_induction_def
)
4732 && nested_cycle
&& found_nested_cycle_def
));
4733 if (!found_nested_cycle_def
)
4734 reduc_def_stmt
= def_stmt
;
4736 gcc_assert (gimple_code (reduc_def_stmt
) == GIMPLE_PHI
);
4738 gcc_assert (orig_stmt
== vect_is_simple_reduction (loop_vinfo
,
4744 gimple tmp
= vect_is_simple_reduction (loop_vinfo
, reduc_def_stmt
,
4745 !nested_cycle
, &dummy
);
4746 /* We changed STMT to be the first stmt in reduction chain, hence we
4747 check that in this case the first element in the chain is STMT. */
4748 gcc_assert (stmt
== tmp
4749 || GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp
)) == stmt
);
4752 if (STMT_VINFO_LIVE_P (vinfo_for_stmt (reduc_def_stmt
)))
4755 if (slp_node
|| PURE_SLP_STMT (stmt_info
))
4758 ncopies
= (LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4759 / TYPE_VECTOR_SUBPARTS (vectype_in
));
4761 gcc_assert (ncopies
>= 1);
4763 vec_mode
= TYPE_MODE (vectype_in
);
4765 if (code
== COND_EXPR
)
4767 if (!vectorizable_condition (stmt
, gsi
, NULL
, ops
[reduc_index
], 0, NULL
))
4769 if (dump_enabled_p ())
4770 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4771 "unsupported condition in reduction");
4778 /* 4. Supportable by target? */
4780 /* 4.1. check support for the operation in the loop */
4781 optab
= optab_for_tree_code (code
, vectype_in
, optab_default
);
4784 if (dump_enabled_p ())
4785 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4791 if (optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
4793 if (dump_enabled_p ())
4794 dump_printf (MSG_NOTE
, "op not supported by target.");
4796 if (GET_MODE_SIZE (vec_mode
) != UNITS_PER_WORD
4797 || LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4798 < vect_min_worthwhile_factor (code
))
4801 if (dump_enabled_p ())
4802 dump_printf (MSG_NOTE
, "proceeding using word mode.");
4805 /* Worthwhile without SIMD support? */
4806 if (!VECTOR_MODE_P (TYPE_MODE (vectype_in
))
4807 && LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4808 < vect_min_worthwhile_factor (code
))
4810 if (dump_enabled_p ())
4811 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4812 "not worthwhile without SIMD support.");
4818 /* 4.2. Check support for the epilog operation.
4820 If STMT represents a reduction pattern, then the type of the
4821 reduction variable may be different than the type of the rest
4822 of the arguments. For example, consider the case of accumulation
4823 of shorts into an int accumulator; The original code:
4824 S1: int_a = (int) short_a;
4825 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
4828 STMT: int_acc = widen_sum <short_a, int_acc>
4831 1. The tree-code that is used to create the vector operation in the
4832 epilog code (that reduces the partial results) is not the
4833 tree-code of STMT, but is rather the tree-code of the original
4834 stmt from the pattern that STMT is replacing. I.e, in the example
4835 above we want to use 'widen_sum' in the loop, but 'plus' in the
4837 2. The type (mode) we use to check available target support
4838 for the vector operation to be created in the *epilog*, is
4839 determined by the type of the reduction variable (in the example
4840 above we'd check this: optab_handler (plus_optab, vect_int_mode])).
4841 However the type (mode) we use to check available target support
4842 for the vector operation to be created *inside the loop*, is
4843 determined by the type of the other arguments to STMT (in the
4844 example we'd check this: optab_handler (widen_sum_optab,
4847 This is contrary to "regular" reductions, in which the types of all
4848 the arguments are the same as the type of the reduction variable.
4849 For "regular" reductions we can therefore use the same vector type
4850 (and also the same tree-code) when generating the epilog code and
4851 when generating the code inside the loop. */
4855 /* This is a reduction pattern: get the vectype from the type of the
4856 reduction variable, and get the tree-code from orig_stmt. */
4857 orig_code
= gimple_assign_rhs_code (orig_stmt
);
4858 gcc_assert (vectype_out
);
4859 vec_mode
= TYPE_MODE (vectype_out
);
4863 /* Regular reduction: use the same vectype and tree-code as used for
4864 the vector code inside the loop can be used for the epilog code. */
4870 def_bb
= gimple_bb (reduc_def_stmt
);
4871 def_stmt_loop
= def_bb
->loop_father
;
4872 def_arg
= PHI_ARG_DEF_FROM_EDGE (reduc_def_stmt
,
4873 loop_preheader_edge (def_stmt_loop
));
4874 if (TREE_CODE (def_arg
) == SSA_NAME
4875 && (def_arg_stmt
= SSA_NAME_DEF_STMT (def_arg
))
4876 && gimple_code (def_arg_stmt
) == GIMPLE_PHI
4877 && flow_bb_inside_loop_p (outer_loop
, gimple_bb (def_arg_stmt
))
4878 && vinfo_for_stmt (def_arg_stmt
)
4879 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_arg_stmt
))
4880 == vect_double_reduction_def
)
4881 double_reduc
= true;
4884 epilog_reduc_code
= ERROR_MARK
;
4885 if (reduction_code_for_scalar_code (orig_code
, &epilog_reduc_code
))
4887 reduc_optab
= optab_for_tree_code (epilog_reduc_code
, vectype_out
,
4891 if (dump_enabled_p ())
4892 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4893 "no optab for reduction.");
4895 epilog_reduc_code
= ERROR_MARK
;
4899 && optab_handler (reduc_optab
, vec_mode
) == CODE_FOR_nothing
)
4901 if (dump_enabled_p ())
4902 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4903 "reduc op not supported by target.");
4905 epilog_reduc_code
= ERROR_MARK
;
4910 if (!nested_cycle
|| double_reduc
)
4912 if (dump_enabled_p ())
4913 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4914 "no reduc code for scalar code.");
4920 if (double_reduc
&& ncopies
> 1)
4922 if (dump_enabled_p ())
4923 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4924 "multiple types in double reduction");
4929 /* In case of widenning multiplication by a constant, we update the type
4930 of the constant to be the type of the other operand. We check that the
4931 constant fits the type in the pattern recognition pass. */
4932 if (code
== DOT_PROD_EXPR
4933 && !types_compatible_p (TREE_TYPE (ops
[0]), TREE_TYPE (ops
[1])))
4935 if (TREE_CODE (ops
[0]) == INTEGER_CST
)
4936 ops
[0] = fold_convert (TREE_TYPE (ops
[1]), ops
[0]);
4937 else if (TREE_CODE (ops
[1]) == INTEGER_CST
)
4938 ops
[1] = fold_convert (TREE_TYPE (ops
[0]), ops
[1]);
4941 if (dump_enabled_p ())
4942 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4943 "invalid types in dot-prod");
4949 if (!vec_stmt
) /* transformation not required. */
4951 if (!vect_model_reduction_cost (stmt_info
, epilog_reduc_code
, ncopies
))
4953 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
4959 if (dump_enabled_p ())
4960 dump_printf_loc (MSG_NOTE
, vect_location
, "transform reduction.");
4962 /* FORNOW: Multiple types are not supported for condition. */
4963 if (code
== COND_EXPR
)
4964 gcc_assert (ncopies
== 1);
4966 /* Create the destination vector */
4967 vec_dest
= vect_create_destination_var (scalar_dest
, vectype_out
);
4969 /* In case the vectorization factor (VF) is bigger than the number
4970 of elements that we can fit in a vectype (nunits), we have to generate
4971 more than one vector stmt - i.e - we need to "unroll" the
4972 vector stmt by a factor VF/nunits. For more details see documentation
4973 in vectorizable_operation. */
4975 /* If the reduction is used in an outer loop we need to generate
4976 VF intermediate results, like so (e.g. for ncopies=2):
4981 (i.e. we generate VF results in 2 registers).
4982 In this case we have a separate def-use cycle for each copy, and therefore
4983 for each copy we get the vector def for the reduction variable from the
4984 respective phi node created for this copy.
4986 Otherwise (the reduction is unused in the loop nest), we can combine
4987 together intermediate results, like so (e.g. for ncopies=2):
4991 (i.e. we generate VF/2 results in a single register).
4992 In this case for each copy we get the vector def for the reduction variable
4993 from the vectorized reduction operation generated in the previous iteration.
4996 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
)
4998 single_defuse_cycle
= true;
5002 epilog_copies
= ncopies
;
5004 prev_stmt_info
= NULL
;
5005 prev_phi_info
= NULL
;
5008 vec_num
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
5009 gcc_assert (TYPE_VECTOR_SUBPARTS (vectype_out
)
5010 == TYPE_VECTOR_SUBPARTS (vectype_in
));
5015 vec_oprnds0
.create (1);
5016 if (op_type
== ternary_op
)
5017 vec_oprnds1
.create (1);
5020 phis
.create (vec_num
);
5021 vect_defs
.create (vec_num
);
5023 vect_defs
.quick_push (NULL_TREE
);
5025 for (j
= 0; j
< ncopies
; j
++)
5027 if (j
== 0 || !single_defuse_cycle
)
5029 for (i
= 0; i
< vec_num
; i
++)
5031 /* Create the reduction-phi that defines the reduction
5033 new_phi
= create_phi_node (vec_dest
, loop
->header
);
5034 set_vinfo_for_stmt (new_phi
,
5035 new_stmt_vec_info (new_phi
, loop_vinfo
,
5037 if (j
== 0 || slp_node
)
5038 phis
.quick_push (new_phi
);
5042 if (code
== COND_EXPR
)
5044 gcc_assert (!slp_node
);
5045 vectorizable_condition (stmt
, gsi
, vec_stmt
,
5046 PHI_RESULT (phis
[0]),
5048 /* Multiple types are not supported for condition. */
5055 op0
= ops
[!reduc_index
];
5056 if (op_type
== ternary_op
)
5058 if (reduc_index
== 0)
5065 vect_get_vec_defs (op0
, op1
, stmt
, &vec_oprnds0
, &vec_oprnds1
,
5069 loop_vec_def0
= vect_get_vec_def_for_operand (ops
[!reduc_index
],
5071 vec_oprnds0
.quick_push (loop_vec_def0
);
5072 if (op_type
== ternary_op
)
5074 loop_vec_def1
= vect_get_vec_def_for_operand (op1
, stmt
,
5076 vec_oprnds1
.quick_push (loop_vec_def1
);
5084 enum vect_def_type dt
;
5088 vect_is_simple_use (ops
[!reduc_index
], stmt
, loop_vinfo
, NULL
,
5089 &dummy_stmt
, &dummy
, &dt
);
5090 loop_vec_def0
= vect_get_vec_def_for_stmt_copy (dt
,
5092 vec_oprnds0
[0] = loop_vec_def0
;
5093 if (op_type
== ternary_op
)
5095 vect_is_simple_use (op1
, stmt
, loop_vinfo
, NULL
, &dummy_stmt
,
5097 loop_vec_def1
= vect_get_vec_def_for_stmt_copy (dt
,
5099 vec_oprnds1
[0] = loop_vec_def1
;
5103 if (single_defuse_cycle
)
5104 reduc_def
= gimple_assign_lhs (new_stmt
);
5106 STMT_VINFO_RELATED_STMT (prev_phi_info
) = new_phi
;
5109 FOR_EACH_VEC_ELT (vec_oprnds0
, i
, def0
)
5112 reduc_def
= PHI_RESULT (phis
[i
]);
5115 if (!single_defuse_cycle
|| j
== 0)
5116 reduc_def
= PHI_RESULT (new_phi
);
5119 def1
= ((op_type
== ternary_op
)
5120 ? vec_oprnds1
[i
] : NULL
);
5121 if (op_type
== binary_op
)
5123 if (reduc_index
== 0)
5124 expr
= build2 (code
, vectype_out
, reduc_def
, def0
);
5126 expr
= build2 (code
, vectype_out
, def0
, reduc_def
);
5130 if (reduc_index
== 0)
5131 expr
= build3 (code
, vectype_out
, reduc_def
, def0
, def1
);
5134 if (reduc_index
== 1)
5135 expr
= build3 (code
, vectype_out
, def0
, reduc_def
, def1
);
5137 expr
= build3 (code
, vectype_out
, def0
, def1
, reduc_def
);
5141 new_stmt
= gimple_build_assign (vec_dest
, expr
);
5142 new_temp
= make_ssa_name (vec_dest
, new_stmt
);
5143 gimple_assign_set_lhs (new_stmt
, new_temp
);
5144 vect_finish_stmt_generation (stmt
, new_stmt
, gsi
);
5148 SLP_TREE_VEC_STMTS (slp_node
).quick_push (new_stmt
);
5149 vect_defs
.quick_push (new_temp
);
5152 vect_defs
[0] = new_temp
;
5159 STMT_VINFO_VEC_STMT (stmt_info
) = *vec_stmt
= new_stmt
;
5161 STMT_VINFO_RELATED_STMT (prev_stmt_info
) = new_stmt
;
5163 prev_stmt_info
= vinfo_for_stmt (new_stmt
);
5164 prev_phi_info
= vinfo_for_stmt (new_phi
);
5167 /* Finalize the reduction-phi (set its arguments) and create the
5168 epilog reduction code. */
5169 if ((!single_defuse_cycle
|| code
== COND_EXPR
) && !slp_node
)
5171 new_temp
= gimple_assign_lhs (*vec_stmt
);
5172 vect_defs
[0] = new_temp
;
5175 vect_create_epilog_for_reduction (vect_defs
, stmt
, epilog_copies
,
5176 epilog_reduc_code
, phis
, reduc_index
,
5177 double_reduc
, slp_node
);
5180 vec_oprnds0
.release ();
5181 vec_oprnds1
.release ();
5186 /* Function vect_min_worthwhile_factor.
5188 For a loop where we could vectorize the operation indicated by CODE,
5189 return the minimum vectorization factor that makes it worthwhile
5190 to use generic vectors. */
5192 vect_min_worthwhile_factor (enum tree_code code
)
5213 /* Function vectorizable_induction
5215 Check if PHI performs an induction computation that can be vectorized.
5216 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
5217 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
5218 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5221 vectorizable_induction (gimple phi
, gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
5224 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
5225 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
5226 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
5227 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5228 int nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
5229 int ncopies
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) / nunits
;
5232 gcc_assert (ncopies
>= 1);
5233 /* FORNOW. These restrictions should be relaxed. */
5234 if (nested_in_vect_loop_p (loop
, phi
))
5236 imm_use_iterator imm_iter
;
5237 use_operand_p use_p
;
5244 if (dump_enabled_p ())
5245 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5246 "multiple types in nested loop.");
5251 latch_e
= loop_latch_edge (loop
->inner
);
5252 loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
5253 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
5255 if (!flow_bb_inside_loop_p (loop
->inner
,
5256 gimple_bb (USE_STMT (use_p
))))
5258 exit_phi
= USE_STMT (use_p
);
5264 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
5265 if (!(STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
5266 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
)))
5268 if (dump_enabled_p ())
5269 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5270 "inner-loop induction only used outside "
5271 "of the outer vectorized loop.");
5277 if (!STMT_VINFO_RELEVANT_P (stmt_info
))
5280 /* FORNOW: SLP not supported. */
5281 if (STMT_SLP_TYPE (stmt_info
))
5284 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
);
5286 if (gimple_code (phi
) != GIMPLE_PHI
)
5289 if (!vec_stmt
) /* transformation not required. */
5291 STMT_VINFO_TYPE (stmt_info
) = induc_vec_info_type
;
5292 if (dump_enabled_p ())
5293 dump_printf_loc (MSG_NOTE
, vect_location
,
5294 "=== vectorizable_induction ===");
5295 vect_model_induction_cost (stmt_info
, ncopies
);
5301 if (dump_enabled_p ())
5302 dump_printf_loc (MSG_NOTE
, vect_location
, "transform induction phi.");
5304 vec_def
= get_initial_def_for_induction (phi
);
5305 *vec_stmt
= SSA_NAME_DEF_STMT (vec_def
);
5309 /* Function vectorizable_live_operation.
5311 STMT computes a value that is used outside the loop. Check if
5312 it can be supported. */
5315 vectorizable_live_operation (gimple stmt
,
5316 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
5317 gimple
*vec_stmt ATTRIBUTE_UNUSED
)
5319 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
5320 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
5321 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5327 enum vect_def_type dt
;
5328 enum tree_code code
;
5329 enum gimple_rhs_class rhs_class
;
5331 gcc_assert (STMT_VINFO_LIVE_P (stmt_info
));
5333 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_reduction_def
)
5336 if (!is_gimple_assign (stmt
))
5339 if (TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
5342 /* FORNOW. CHECKME. */
5343 if (nested_in_vect_loop_p (loop
, stmt
))
5346 code
= gimple_assign_rhs_code (stmt
);
5347 op_type
= TREE_CODE_LENGTH (code
);
5348 rhs_class
= get_gimple_rhs_class (code
);
5349 gcc_assert (rhs_class
!= GIMPLE_UNARY_RHS
|| op_type
== unary_op
);
5350 gcc_assert (rhs_class
!= GIMPLE_BINARY_RHS
|| op_type
== binary_op
);
5352 /* FORNOW: support only if all uses are invariant. This means
5353 that the scalar operations can remain in place, unvectorized.
5354 The original last scalar value that they compute will be used. */
5356 for (i
= 0; i
< op_type
; i
++)
5358 if (rhs_class
== GIMPLE_SINGLE_RHS
)
5359 op
= TREE_OPERAND (gimple_op (stmt
, 1), i
);
5361 op
= gimple_op (stmt
, i
+ 1);
5363 && !vect_is_simple_use (op
, stmt
, loop_vinfo
, NULL
, &def_stmt
, &def
,
5366 if (dump_enabled_p ())
5367 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5372 if (dt
!= vect_external_def
&& dt
!= vect_constant_def
)
5376 /* No transformation is required for the cases we currently support. */
5380 /* Kill any debug uses outside LOOP of SSA names defined in STMT. */
5383 vect_loop_kill_debug_uses (struct loop
*loop
, gimple stmt
)
5385 ssa_op_iter op_iter
;
5386 imm_use_iterator imm_iter
;
5387 def_operand_p def_p
;
5390 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
5392 FOR_EACH_IMM_USE_STMT (ustmt
, imm_iter
, DEF_FROM_PTR (def_p
))
5396 if (!is_gimple_debug (ustmt
))
5399 bb
= gimple_bb (ustmt
);
5401 if (!flow_bb_inside_loop_p (loop
, bb
))
5403 if (gimple_debug_bind_p (ustmt
))
5405 if (dump_enabled_p ())
5406 dump_printf_loc (MSG_NOTE
, vect_location
,
5407 "killing debug use");
5409 gimple_debug_bind_reset_value (ustmt
);
5410 update_stmt (ustmt
);
5419 /* Function vect_transform_loop.
5421 The analysis phase has determined that the loop is vectorizable.
5422 Vectorize the loop - created vectorized stmts to replace the scalar
5423 stmts in the loop, and update the loop exit condition. */
5426 vect_transform_loop (loop_vec_info loop_vinfo
)
5428 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5429 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
5430 int nbbs
= loop
->num_nodes
;
5431 gimple_stmt_iterator si
;
5434 int vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
5436 bool slp_scheduled
= false;
5437 unsigned int nunits
;
5438 gimple stmt
, pattern_stmt
;
5439 gimple_seq pattern_def_seq
= NULL
;
5440 gimple_stmt_iterator pattern_def_si
= gsi_none ();
5441 bool transform_pattern_stmt
= false;
5442 bool check_profitability
= false;
5444 /* Record number of iterations before we started tampering with the profile. */
5445 gcov_type expected_iterations
= expected_loop_iterations_unbounded (loop
);
5447 if (dump_enabled_p ())
5448 dump_printf_loc (MSG_NOTE
, vect_location
, "=== vec_transform_loop ===");
5450 /* If profile is inprecise, we have chance to fix it up. */
5451 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
5452 expected_iterations
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
5454 /* Use the more conservative vectorization threshold. If the number
5455 of iterations is constant assume the cost check has been performed
5456 by our caller. If the threshold makes all loops profitable that
5457 run at least the vectorization factor number of times checking
5458 is pointless, too. */
5459 th
= ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND
)
5460 * LOOP_VINFO_VECT_FACTOR (loop_vinfo
)) - 1);
5461 th
= MAX (th
, LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo
));
5462 if (th
>= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) - 1
5463 && !LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
5465 if (dump_enabled_p ())
5466 dump_printf_loc (MSG_NOTE
, vect_location
,
5467 "Profitability threshold is %d loop iterations.", th
);
5468 check_profitability
= true;
5471 /* Peel the loop if there are data refs with unknown alignment.
5472 Only one data ref with unknown store is allowed. */
5474 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
))
5476 vect_do_peeling_for_alignment (loop_vinfo
, th
, check_profitability
);
5477 check_profitability
= false;
5480 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
5481 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
5483 vect_loop_versioning (loop_vinfo
, th
, check_profitability
);
5484 check_profitability
= false;
5487 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
5488 compile time constant), or it is a constant that doesn't divide by the
5489 vectorization factor, then an epilog loop needs to be created.
5490 We therefore duplicate the loop: the original loop will be vectorized,
5491 and will compute the first (n/VF) iterations. The second copy of the loop
5492 will remain scalar and will compute the remaining (n%VF) iterations.
5493 (VF is the vectorization factor). */
5495 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
5496 || (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
5497 && LOOP_VINFO_INT_NITERS (loop_vinfo
) % vectorization_factor
!= 0)
5498 || LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
))
5499 vect_do_peeling_for_loop_bound (loop_vinfo
, &ratio
,
5500 th
, check_profitability
);
5502 ratio
= build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo
)),
5503 LOOP_VINFO_INT_NITERS (loop_vinfo
) / vectorization_factor
);
5505 /* 1) Make sure the loop header has exactly two entries
5506 2) Make sure we have a preheader basic block. */
5508 gcc_assert (EDGE_COUNT (loop
->header
->preds
) == 2);
5510 split_edge (loop_preheader_edge (loop
));
5512 /* FORNOW: the vectorizer supports only loops which body consist
5513 of one basic block (header + empty latch). When the vectorizer will
5514 support more involved loop forms, the order by which the BBs are
5515 traversed need to be reconsidered. */
5517 for (i
= 0; i
< nbbs
; i
++)
5519 basic_block bb
= bbs
[i
];
5520 stmt_vec_info stmt_info
;
5523 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
5525 phi
= gsi_stmt (si
);
5526 if (dump_enabled_p ())
5528 dump_printf_loc (MSG_NOTE
, vect_location
,
5529 "------>vectorizing phi: ");
5530 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, phi
, 0);
5532 stmt_info
= vinfo_for_stmt (phi
);
5536 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
5537 vect_loop_kill_debug_uses (loop
, phi
);
5539 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
5540 && !STMT_VINFO_LIVE_P (stmt_info
))
5543 if ((TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
))
5544 != (unsigned HOST_WIDE_INT
) vectorization_factor
)
5545 && dump_enabled_p ())
5546 dump_printf_loc (MSG_NOTE
, vect_location
, "multiple-types.");
5548 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
5550 if (dump_enabled_p ())
5551 dump_printf_loc (MSG_NOTE
, vect_location
, "transform phi.");
5552 vect_transform_stmt (phi
, NULL
, NULL
, NULL
, NULL
);
5556 pattern_stmt
= NULL
;
5557 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
) || transform_pattern_stmt
;)
5561 if (transform_pattern_stmt
)
5562 stmt
= pattern_stmt
;
5564 stmt
= gsi_stmt (si
);
5566 if (dump_enabled_p ())
5568 dump_printf_loc (MSG_NOTE
, vect_location
,
5569 "------>vectorizing statement: ");
5570 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
5573 stmt_info
= vinfo_for_stmt (stmt
);
5575 /* vector stmts created in the outer-loop during vectorization of
5576 stmts in an inner-loop may not have a stmt_info, and do not
5577 need to be vectorized. */
5584 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
5585 vect_loop_kill_debug_uses (loop
, stmt
);
5587 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
5588 && !STMT_VINFO_LIVE_P (stmt_info
))
5590 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
5591 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
5592 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
5593 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
5595 stmt
= pattern_stmt
;
5596 stmt_info
= vinfo_for_stmt (stmt
);
5604 else if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
5605 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
5606 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
5607 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
5608 transform_pattern_stmt
= true;
5610 /* If pattern statement has def stmts, vectorize them too. */
5611 if (is_pattern_stmt_p (stmt_info
))
5613 if (pattern_def_seq
== NULL
)
5615 pattern_def_seq
= STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
);
5616 pattern_def_si
= gsi_start (pattern_def_seq
);
5618 else if (!gsi_end_p (pattern_def_si
))
5619 gsi_next (&pattern_def_si
);
5620 if (pattern_def_seq
!= NULL
)
5622 gimple pattern_def_stmt
= NULL
;
5623 stmt_vec_info pattern_def_stmt_info
= NULL
;
5625 while (!gsi_end_p (pattern_def_si
))
5627 pattern_def_stmt
= gsi_stmt (pattern_def_si
);
5628 pattern_def_stmt_info
5629 = vinfo_for_stmt (pattern_def_stmt
);
5630 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info
)
5631 || STMT_VINFO_LIVE_P (pattern_def_stmt_info
))
5633 gsi_next (&pattern_def_si
);
5636 if (!gsi_end_p (pattern_def_si
))
5638 if (dump_enabled_p ())
5640 dump_printf_loc (MSG_NOTE
, vect_location
,
5641 "==> vectorizing pattern def "
5643 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
,
5644 pattern_def_stmt
, 0);
5647 stmt
= pattern_def_stmt
;
5648 stmt_info
= pattern_def_stmt_info
;
5652 pattern_def_si
= gsi_none ();
5653 transform_pattern_stmt
= false;
5657 transform_pattern_stmt
= false;
5660 gcc_assert (STMT_VINFO_VECTYPE (stmt_info
));
5661 nunits
= (unsigned int) TYPE_VECTOR_SUBPARTS (
5662 STMT_VINFO_VECTYPE (stmt_info
));
5663 if (!STMT_SLP_TYPE (stmt_info
)
5664 && nunits
!= (unsigned int) vectorization_factor
5665 && dump_enabled_p ())
5666 /* For SLP VF is set according to unrolling factor, and not to
5667 vector size, hence for SLP this print is not valid. */
5668 dump_printf_loc (MSG_NOTE
, vect_location
,
5671 /* SLP. Schedule all the SLP instances when the first SLP stmt is
5673 if (STMT_SLP_TYPE (stmt_info
))
5677 slp_scheduled
= true;
5679 if (dump_enabled_p ())
5680 dump_printf_loc (MSG_NOTE
, vect_location
,
5681 "=== scheduling SLP instances ===");
5683 vect_schedule_slp (loop_vinfo
, NULL
);
5686 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
5687 if (!vinfo_for_stmt (stmt
) || PURE_SLP_STMT (stmt_info
))
5689 if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
5691 pattern_def_seq
= NULL
;
5698 /* -------- vectorize statement ------------ */
5699 if (dump_enabled_p ())
5700 dump_printf_loc (MSG_NOTE
, vect_location
, "transform statement.");
5702 grouped_store
= false;
5703 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, NULL
, NULL
);
5706 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
5708 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
5709 interleaving chain was completed - free all the stores in
5712 vect_remove_stores (GROUP_FIRST_ELEMENT (stmt_info
));
5717 /* Free the attached stmt_vec_info and remove the stmt. */
5718 gimple store
= gsi_stmt (si
);
5719 free_stmt_vec_info (store
);
5720 unlink_stmt_vdef (store
);
5721 gsi_remove (&si
, true);
5722 release_defs (store
);
5727 if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
5729 pattern_def_seq
= NULL
;
5735 slpeel_make_loop_iterate_ntimes (loop
, ratio
);
5737 /* Reduce loop iterations by the vectorization factor. */
5738 scale_loop_profile (loop
, RDIV (REG_BR_PROB_BASE
, vectorization_factor
),
5739 expected_iterations
/ vectorization_factor
);
5740 loop
->nb_iterations_upper_bound
5741 = loop
->nb_iterations_upper_bound
.udiv (double_int::from_uhwi (vectorization_factor
),
5743 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
5744 && loop
->nb_iterations_upper_bound
!= double_int_zero
)
5745 loop
->nb_iterations_upper_bound
= loop
->nb_iterations_upper_bound
- double_int_one
;
5746 if (loop
->any_estimate
)
5748 loop
->nb_iterations_estimate
5749 = loop
->nb_iterations_estimate
.udiv (double_int::from_uhwi (vectorization_factor
),
5751 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
)
5752 && loop
->nb_iterations_estimate
!= double_int_zero
)
5753 loop
->nb_iterations_estimate
= loop
->nb_iterations_estimate
- double_int_one
;
5756 /* The memory tags and pointers in vectorized statements need to
5757 have their SSA forms updated. FIXME, why can't this be delayed
5758 until all the loops have been transformed? */
5759 update_ssa (TODO_update_ssa
);
5761 if (dump_enabled_p ())
5762 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
, "LOOP VECTORIZED.");
5763 if (loop
->inner
&& dump_enabled_p ())
5764 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
5765 "OUTER LOOP VECTORIZED.");