2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 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"
29 #include "basic-block.h"
30 #include "gimple-pretty-print.h"
31 #include "tree-flow.h"
32 #include "tree-pass.h"
38 #include "diagnostic-core.h"
39 #include "tree-chrec.h"
40 #include "tree-scalar-evolution.h"
41 #include "tree-vectorizer.h"
44 /* Loop Vectorization Pass.
46 This pass tries to vectorize loops.
48 For example, the vectorizer transforms the following simple loop:
50 short a[N]; short b[N]; short c[N]; int i;
56 as if it was manually vectorized by rewriting the source code into:
58 typedef int __attribute__((mode(V8HI))) v8hi;
59 short a[N]; short b[N]; short c[N]; int i;
60 v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
63 for (i=0; i<N/8; i++){
70 The main entry to this pass is vectorize_loops(), in which
71 the vectorizer applies a set of analyses on a given set of loops,
72 followed by the actual vectorization transformation for the loops that
73 had successfully passed the analysis phase.
74 Throughout this pass we make a distinction between two types of
75 data: scalars (which are represented by SSA_NAMES), and memory references
76 ("data-refs"). These two types of data require different handling both
77 during analysis and transformation. The types of data-refs that the
78 vectorizer currently supports are ARRAY_REFS which base is an array DECL
79 (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
80 accesses are required to have a simple (consecutive) access pattern.
84 The driver for the analysis phase is vect_analyze_loop().
85 It applies a set of analyses, some of which rely on the scalar evolution
86 analyzer (scev) developed by Sebastian Pop.
88 During the analysis phase the vectorizer records some information
89 per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
90 loop, as well as general information about the loop as a whole, which is
91 recorded in a "loop_vec_info" struct attached to each loop.
95 The loop transformation phase scans all the stmts in the loop, and
96 creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
97 the loop that needs to be vectorized. It inserts the vector code sequence
98 just before the scalar stmt S, and records a pointer to the vector code
99 in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
100 attached to S). This pointer will be used for the vectorization of following
101 stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
102 otherwise, we rely on dead code elimination for removing it.
104 For example, say stmt S1 was vectorized into stmt VS1:
107 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
110 To vectorize stmt S2, the vectorizer first finds the stmt that defines
111 the operand 'b' (S1), and gets the relevant vector def 'vb' from the
112 vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
113 resulting sequence would be:
116 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
118 S2: a = b; STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
120 Operands that are not SSA_NAMEs, are data-refs that appear in
121 load/store operations (like 'x[i]' in S1), and are handled differently.
125 Currently the only target specific information that is used is the
126 size of the vector (in bytes) - "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD".
127 Targets that can support different sizes of vectors, for now will need
128 to specify one value for "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD". More
129 flexibility will be added in the future.
131 Since we only vectorize operations which vector form can be
132 expressed using existing tree codes, to verify that an operation is
133 supported, the vectorizer checks the relevant optab at the relevant
134 machine_mode (e.g, optab_handler (add_optab, V8HImode)). If
135 the value found is CODE_FOR_nothing, then there's no target support, and
136 we can't vectorize the stmt.
138 For additional information on this project see:
139 http://gcc.gnu.org/projects/tree-ssa/vectorization.html
142 /* Function vect_determine_vectorization_factor
144 Determine the vectorization factor (VF). VF is the number of data elements
145 that are operated upon in parallel in a single iteration of the vectorized
146 loop. For example, when vectorizing a loop that operates on 4byte elements,
147 on a target with vector size (VS) 16byte, the VF is set to 4, since 4
148 elements can fit in a single vector register.
150 We currently support vectorization of loops in which all types operated upon
151 are of the same size. Therefore this function currently sets VF according to
152 the size of the types operated upon, and fails if there are multiple sizes
155 VF is also the factor by which the loop iterations are strip-mined, e.g.:
162 for (i=0; i<N; i+=VF){
163 a[i:VF] = b[i:VF] + c[i:VF];
168 vect_determine_vectorization_factor (loop_vec_info loop_vinfo
)
170 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
171 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
172 int nbbs
= loop
->num_nodes
;
173 gimple_stmt_iterator si
;
174 unsigned int vectorization_factor
= 0;
179 stmt_vec_info stmt_info
;
182 gimple stmt
, pattern_stmt
= NULL
;
183 gimple_seq pattern_def_seq
= NULL
;
184 gimple_stmt_iterator pattern_def_si
= gsi_none ();
185 bool analyze_pattern_stmt
= false;
187 if (vect_print_dump_info (REPORT_DETAILS
))
188 fprintf (vect_dump
, "=== vect_determine_vectorization_factor ===");
190 for (i
= 0; i
< nbbs
; i
++)
192 basic_block bb
= bbs
[i
];
194 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
197 stmt_info
= vinfo_for_stmt (phi
);
198 if (vect_print_dump_info (REPORT_DETAILS
))
200 fprintf (vect_dump
, "==> examining phi: ");
201 print_gimple_stmt (vect_dump
, phi
, 0, TDF_SLIM
);
204 gcc_assert (stmt_info
);
206 if (STMT_VINFO_RELEVANT_P (stmt_info
))
208 gcc_assert (!STMT_VINFO_VECTYPE (stmt_info
));
209 scalar_type
= TREE_TYPE (PHI_RESULT (phi
));
211 if (vect_print_dump_info (REPORT_DETAILS
))
213 fprintf (vect_dump
, "get vectype for scalar type: ");
214 print_generic_expr (vect_dump
, scalar_type
, TDF_SLIM
);
217 vectype
= get_vectype_for_scalar_type (scalar_type
);
220 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
223 "not vectorized: unsupported data-type ");
224 print_generic_expr (vect_dump
, scalar_type
, TDF_SLIM
);
228 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
230 if (vect_print_dump_info (REPORT_DETAILS
))
232 fprintf (vect_dump
, "vectype: ");
233 print_generic_expr (vect_dump
, vectype
, TDF_SLIM
);
236 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
237 if (vect_print_dump_info (REPORT_DETAILS
))
238 fprintf (vect_dump
, "nunits = %d", nunits
);
240 if (!vectorization_factor
241 || (nunits
> vectorization_factor
))
242 vectorization_factor
= nunits
;
246 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
) || analyze_pattern_stmt
;)
250 if (analyze_pattern_stmt
)
253 stmt
= gsi_stmt (si
);
255 stmt_info
= vinfo_for_stmt (stmt
);
257 if (vect_print_dump_info (REPORT_DETAILS
))
259 fprintf (vect_dump
, "==> examining statement: ");
260 print_gimple_stmt (vect_dump
, stmt
, 0, TDF_SLIM
);
263 gcc_assert (stmt_info
);
265 /* Skip stmts which do not need to be vectorized. */
266 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
267 && !STMT_VINFO_LIVE_P (stmt_info
))
269 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
270 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
271 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
272 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
275 stmt_info
= vinfo_for_stmt (pattern_stmt
);
276 if (vect_print_dump_info (REPORT_DETAILS
))
278 fprintf (vect_dump
, "==> examining pattern statement: ");
279 print_gimple_stmt (vect_dump
, stmt
, 0, TDF_SLIM
);
284 if (vect_print_dump_info (REPORT_DETAILS
))
285 fprintf (vect_dump
, "skip.");
290 else if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
291 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
292 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
293 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
294 analyze_pattern_stmt
= true;
296 /* If a pattern statement has def stmts, analyze them too. */
297 if (is_pattern_stmt_p (stmt_info
))
299 if (pattern_def_seq
== NULL
)
301 pattern_def_seq
= STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
);
302 pattern_def_si
= gsi_start (pattern_def_seq
);
304 else if (!gsi_end_p (pattern_def_si
))
305 gsi_next (&pattern_def_si
);
306 if (pattern_def_seq
!= NULL
)
308 gimple pattern_def_stmt
= NULL
;
309 stmt_vec_info pattern_def_stmt_info
= NULL
;
311 while (!gsi_end_p (pattern_def_si
))
313 pattern_def_stmt
= gsi_stmt (pattern_def_si
);
314 pattern_def_stmt_info
315 = vinfo_for_stmt (pattern_def_stmt
);
316 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info
)
317 || STMT_VINFO_LIVE_P (pattern_def_stmt_info
))
319 gsi_next (&pattern_def_si
);
322 if (!gsi_end_p (pattern_def_si
))
324 if (vect_print_dump_info (REPORT_DETAILS
))
327 "==> examining pattern def stmt: ");
328 print_gimple_stmt (vect_dump
, pattern_def_stmt
, 0,
332 stmt
= pattern_def_stmt
;
333 stmt_info
= pattern_def_stmt_info
;
337 pattern_def_si
= gsi_none ();
338 analyze_pattern_stmt
= false;
342 analyze_pattern_stmt
= false;
345 if (gimple_get_lhs (stmt
) == NULL_TREE
)
347 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
349 fprintf (vect_dump
, "not vectorized: irregular stmt.");
350 print_gimple_stmt (vect_dump
, stmt
, 0, TDF_SLIM
);
355 if (VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt
))))
357 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
359 fprintf (vect_dump
, "not vectorized: vector stmt in loop:");
360 print_gimple_stmt (vect_dump
, stmt
, 0, TDF_SLIM
);
365 if (STMT_VINFO_VECTYPE (stmt_info
))
367 /* The only case when a vectype had been already set is for stmts
368 that contain a dataref, or for "pattern-stmts" (stmts
369 generated by the vectorizer to represent/replace a certain
371 gcc_assert (STMT_VINFO_DATA_REF (stmt_info
)
372 || is_pattern_stmt_p (stmt_info
)
373 || !gsi_end_p (pattern_def_si
));
374 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
378 gcc_assert (!STMT_VINFO_DATA_REF (stmt_info
));
379 scalar_type
= TREE_TYPE (gimple_get_lhs (stmt
));
380 if (vect_print_dump_info (REPORT_DETAILS
))
382 fprintf (vect_dump
, "get vectype for scalar type: ");
383 print_generic_expr (vect_dump
, scalar_type
, TDF_SLIM
);
385 vectype
= get_vectype_for_scalar_type (scalar_type
);
388 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
391 "not vectorized: unsupported data-type ");
392 print_generic_expr (vect_dump
, scalar_type
, TDF_SLIM
);
397 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
400 /* The vectorization factor is according to the smallest
401 scalar type (or the largest vector size, but we only
402 support one vector size per loop). */
403 scalar_type
= vect_get_smallest_scalar_type (stmt
, &dummy
,
405 if (vect_print_dump_info (REPORT_DETAILS
))
407 fprintf (vect_dump
, "get vectype for scalar type: ");
408 print_generic_expr (vect_dump
, scalar_type
, TDF_SLIM
);
410 vf_vectype
= get_vectype_for_scalar_type (scalar_type
);
413 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
416 "not vectorized: unsupported data-type ");
417 print_generic_expr (vect_dump
, scalar_type
, TDF_SLIM
);
422 if ((GET_MODE_SIZE (TYPE_MODE (vectype
))
423 != GET_MODE_SIZE (TYPE_MODE (vf_vectype
))))
425 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
428 "not vectorized: different sized vector "
429 "types in statement, ");
430 print_generic_expr (vect_dump
, vectype
, TDF_SLIM
);
431 fprintf (vect_dump
, " and ");
432 print_generic_expr (vect_dump
, vf_vectype
, TDF_SLIM
);
437 if (vect_print_dump_info (REPORT_DETAILS
))
439 fprintf (vect_dump
, "vectype: ");
440 print_generic_expr (vect_dump
, vf_vectype
, TDF_SLIM
);
443 nunits
= TYPE_VECTOR_SUBPARTS (vf_vectype
);
444 if (vect_print_dump_info (REPORT_DETAILS
))
445 fprintf (vect_dump
, "nunits = %d", nunits
);
447 if (!vectorization_factor
448 || (nunits
> vectorization_factor
))
449 vectorization_factor
= nunits
;
451 if (!analyze_pattern_stmt
&& gsi_end_p (pattern_def_si
))
453 pattern_def_seq
= NULL
;
459 /* TODO: Analyze cost. Decide if worth while to vectorize. */
460 if (vect_print_dump_info (REPORT_DETAILS
))
461 fprintf (vect_dump
, "vectorization factor = %d", vectorization_factor
);
462 if (vectorization_factor
<= 1)
464 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
465 fprintf (vect_dump
, "not vectorized: unsupported data-type");
468 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
474 /* Function vect_is_simple_iv_evolution.
476 FORNOW: A simple evolution of an induction variables in the loop is
477 considered a polynomial evolution with constant step. */
480 vect_is_simple_iv_evolution (unsigned loop_nb
, tree access_fn
, tree
* init
,
485 tree evolution_part
= evolution_part_in_loop_num (access_fn
, loop_nb
);
487 /* When there is no evolution in this loop, the evolution function
489 if (evolution_part
== NULL_TREE
)
492 /* When the evolution is a polynomial of degree >= 2
493 the evolution function is not "simple". */
494 if (tree_is_chrec (evolution_part
))
497 step_expr
= evolution_part
;
498 init_expr
= unshare_expr (initial_condition_in_loop_num (access_fn
, loop_nb
));
500 if (vect_print_dump_info (REPORT_DETAILS
))
502 fprintf (vect_dump
, "step: ");
503 print_generic_expr (vect_dump
, step_expr
, TDF_SLIM
);
504 fprintf (vect_dump
, ", init: ");
505 print_generic_expr (vect_dump
, init_expr
, TDF_SLIM
);
511 if (TREE_CODE (step_expr
) != INTEGER_CST
)
513 if (vect_print_dump_info (REPORT_DETAILS
))
514 fprintf (vect_dump
, "step unknown.");
521 /* Function vect_analyze_scalar_cycles_1.
523 Examine the cross iteration def-use cycles of scalar variables
524 in LOOP. LOOP_VINFO represents the loop that is now being
525 considered for vectorization (can be LOOP, or an outer-loop
529 vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo
, struct loop
*loop
)
531 basic_block bb
= loop
->header
;
533 VEC(gimple
,heap
) *worklist
= VEC_alloc (gimple
, heap
, 64);
534 gimple_stmt_iterator gsi
;
537 if (vect_print_dump_info (REPORT_DETAILS
))
538 fprintf (vect_dump
, "=== vect_analyze_scalar_cycles ===");
540 /* First - identify all inductions. Reduction detection assumes that all the
541 inductions have been identified, therefore, this order must not be
543 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
545 gimple phi
= gsi_stmt (gsi
);
546 tree access_fn
= NULL
;
547 tree def
= PHI_RESULT (phi
);
548 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (phi
);
550 if (vect_print_dump_info (REPORT_DETAILS
))
552 fprintf (vect_dump
, "Analyze phi: ");
553 print_gimple_stmt (vect_dump
, phi
, 0, TDF_SLIM
);
556 /* Skip virtual phi's. The data dependences that are associated with
557 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
558 if (!is_gimple_reg (def
))
561 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_unknown_def_type
;
563 /* Analyze the evolution function. */
564 access_fn
= analyze_scalar_evolution (loop
, def
);
567 STRIP_NOPS (access_fn
);
568 if (vect_print_dump_info (REPORT_DETAILS
))
570 fprintf (vect_dump
, "Access function of PHI: ");
571 print_generic_expr (vect_dump
, access_fn
, TDF_SLIM
);
573 STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
)
574 = evolution_part_in_loop_num (access_fn
, loop
->num
);
578 || !vect_is_simple_iv_evolution (loop
->num
, access_fn
, &dumy
, &dumy
))
580 VEC_safe_push (gimple
, heap
, worklist
, phi
);
584 gcc_assert (STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo
) != NULL_TREE
);
586 if (vect_print_dump_info (REPORT_DETAILS
))
587 fprintf (vect_dump
, "Detected induction.");
588 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_induction_def
;
592 /* Second - identify all reductions and nested cycles. */
593 while (VEC_length (gimple
, worklist
) > 0)
595 gimple phi
= VEC_pop (gimple
, worklist
);
596 tree def
= PHI_RESULT (phi
);
597 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (phi
);
601 if (vect_print_dump_info (REPORT_DETAILS
))
603 fprintf (vect_dump
, "Analyze phi: ");
604 print_gimple_stmt (vect_dump
, phi
, 0, TDF_SLIM
);
607 gcc_assert (is_gimple_reg (def
));
608 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_unknown_def_type
);
610 nested_cycle
= (loop
!= LOOP_VINFO_LOOP (loop_vinfo
));
611 reduc_stmt
= vect_force_simple_reduction (loop_vinfo
, phi
, !nested_cycle
,
617 if (vect_print_dump_info (REPORT_DETAILS
))
618 fprintf (vect_dump
, "Detected double reduction.");
620 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_double_reduction_def
;
621 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
622 vect_double_reduction_def
;
628 if (vect_print_dump_info (REPORT_DETAILS
))
629 fprintf (vect_dump
, "Detected vectorizable nested cycle.");
631 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_nested_cycle
;
632 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
637 if (vect_print_dump_info (REPORT_DETAILS
))
638 fprintf (vect_dump
, "Detected reduction.");
640 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_reduction_def
;
641 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
643 /* Store the reduction cycles for possible vectorization in
645 VEC_safe_push (gimple
, heap
,
646 LOOP_VINFO_REDUCTIONS (loop_vinfo
),
652 if (vect_print_dump_info (REPORT_DETAILS
))
653 fprintf (vect_dump
, "Unknown def-use cycle pattern.");
656 VEC_free (gimple
, heap
, worklist
);
660 /* Function vect_analyze_scalar_cycles.
662 Examine the cross iteration def-use cycles of scalar variables, by
663 analyzing the loop-header PHIs of scalar variables. Classify each
664 cycle as one of the following: invariant, induction, reduction, unknown.
665 We do that for the loop represented by LOOP_VINFO, and also to its
666 inner-loop, if exists.
667 Examples for scalar cycles:
682 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo
)
684 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
686 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
);
688 /* When vectorizing an outer-loop, the inner-loop is executed sequentially.
689 Reductions in such inner-loop therefore have different properties than
690 the reductions in the nest that gets vectorized:
691 1. When vectorized, they are executed in the same order as in the original
692 scalar loop, so we can't change the order of computation when
694 2. FIXME: Inner-loop reductions can be used in the inner-loop, so the
695 current checks are too strict. */
698 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
->inner
);
701 /* Function vect_get_loop_niters.
703 Determine how many iterations the loop is executed.
704 If an expression that represents the number of iterations
705 can be constructed, place it in NUMBER_OF_ITERATIONS.
706 Return the loop exit condition. */
709 vect_get_loop_niters (struct loop
*loop
, tree
*number_of_iterations
)
713 if (vect_print_dump_info (REPORT_DETAILS
))
714 fprintf (vect_dump
, "=== get_loop_niters ===");
716 niters
= number_of_exit_cond_executions (loop
);
718 if (niters
!= NULL_TREE
719 && niters
!= chrec_dont_know
)
721 *number_of_iterations
= niters
;
723 if (vect_print_dump_info (REPORT_DETAILS
))
725 fprintf (vect_dump
, "==> get_loop_niters:" );
726 print_generic_expr (vect_dump
, *number_of_iterations
, TDF_SLIM
);
730 return get_loop_exit_condition (loop
);
734 /* Function bb_in_loop_p
736 Used as predicate for dfs order traversal of the loop bbs. */
739 bb_in_loop_p (const_basic_block bb
, const void *data
)
741 const struct loop
*const loop
= (const struct loop
*)data
;
742 if (flow_bb_inside_loop_p (loop
, bb
))
748 /* Function new_loop_vec_info.
750 Create and initialize a new loop_vec_info struct for LOOP, as well as
751 stmt_vec_info structs for all the stmts in LOOP. */
754 new_loop_vec_info (struct loop
*loop
)
758 gimple_stmt_iterator si
;
759 unsigned int i
, nbbs
;
761 res
= (loop_vec_info
) xcalloc (1, sizeof (struct _loop_vec_info
));
762 LOOP_VINFO_LOOP (res
) = loop
;
764 bbs
= get_loop_body (loop
);
766 /* Create/Update stmt_info for all stmts in the loop. */
767 for (i
= 0; i
< loop
->num_nodes
; i
++)
769 basic_block bb
= bbs
[i
];
771 /* BBs in a nested inner-loop will have been already processed (because
772 we will have called vect_analyze_loop_form for any nested inner-loop).
773 Therefore, for stmts in an inner-loop we just want to update the
774 STMT_VINFO_LOOP_VINFO field of their stmt_info to point to the new
775 loop_info of the outer-loop we are currently considering to vectorize
776 (instead of the loop_info of the inner-loop).
777 For stmts in other BBs we need to create a stmt_info from scratch. */
778 if (bb
->loop_father
!= loop
)
781 gcc_assert (loop
->inner
&& bb
->loop_father
== loop
->inner
);
782 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
784 gimple phi
= gsi_stmt (si
);
785 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
786 loop_vec_info inner_loop_vinfo
=
787 STMT_VINFO_LOOP_VINFO (stmt_info
);
788 gcc_assert (loop
->inner
== LOOP_VINFO_LOOP (inner_loop_vinfo
));
789 STMT_VINFO_LOOP_VINFO (stmt_info
) = res
;
791 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
793 gimple stmt
= gsi_stmt (si
);
794 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
795 loop_vec_info inner_loop_vinfo
=
796 STMT_VINFO_LOOP_VINFO (stmt_info
);
797 gcc_assert (loop
->inner
== LOOP_VINFO_LOOP (inner_loop_vinfo
));
798 STMT_VINFO_LOOP_VINFO (stmt_info
) = res
;
803 /* bb in current nest. */
804 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
806 gimple phi
= gsi_stmt (si
);
807 gimple_set_uid (phi
, 0);
808 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, res
, NULL
));
811 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
813 gimple stmt
= gsi_stmt (si
);
814 gimple_set_uid (stmt
, 0);
815 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, res
, NULL
));
820 /* CHECKME: We want to visit all BBs before their successors (except for
821 latch blocks, for which this assertion wouldn't hold). In the simple
822 case of the loop forms we allow, a dfs order of the BBs would the same
823 as reversed postorder traversal, so we are safe. */
826 bbs
= XCNEWVEC (basic_block
, loop
->num_nodes
);
827 nbbs
= dfs_enumerate_from (loop
->header
, 0, bb_in_loop_p
,
828 bbs
, loop
->num_nodes
, loop
);
829 gcc_assert (nbbs
== loop
->num_nodes
);
831 LOOP_VINFO_BBS (res
) = bbs
;
832 LOOP_VINFO_NITERS (res
) = NULL
;
833 LOOP_VINFO_NITERS_UNCHANGED (res
) = NULL
;
834 LOOP_VINFO_COST_MODEL_MIN_ITERS (res
) = 0;
835 LOOP_VINFO_VECTORIZABLE_P (res
) = 0;
836 LOOP_PEELING_FOR_ALIGNMENT (res
) = 0;
837 LOOP_VINFO_VECT_FACTOR (res
) = 0;
838 LOOP_VINFO_LOOP_NEST (res
) = VEC_alloc (loop_p
, heap
, 3);
839 LOOP_VINFO_DATAREFS (res
) = VEC_alloc (data_reference_p
, heap
, 10);
840 LOOP_VINFO_DDRS (res
) = VEC_alloc (ddr_p
, heap
, 10 * 10);
841 LOOP_VINFO_UNALIGNED_DR (res
) = NULL
;
842 LOOP_VINFO_MAY_MISALIGN_STMTS (res
) =
843 VEC_alloc (gimple
, heap
,
844 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS
));
845 LOOP_VINFO_MAY_ALIAS_DDRS (res
) =
846 VEC_alloc (ddr_p
, heap
,
847 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS
));
848 LOOP_VINFO_GROUPED_STORES (res
) = VEC_alloc (gimple
, heap
, 10);
849 LOOP_VINFO_REDUCTIONS (res
) = VEC_alloc (gimple
, heap
, 10);
850 LOOP_VINFO_REDUCTION_CHAINS (res
) = VEC_alloc (gimple
, heap
, 10);
851 LOOP_VINFO_SLP_INSTANCES (res
) = VEC_alloc (slp_instance
, heap
, 10);
852 LOOP_VINFO_SLP_UNROLLING_FACTOR (res
) = 1;
853 LOOP_VINFO_PEELING_HTAB (res
) = NULL
;
854 LOOP_VINFO_TARGET_COST_DATA (res
) = init_cost (loop
);
855 LOOP_VINFO_PEELING_FOR_GAPS (res
) = false;
856 LOOP_VINFO_OPERANDS_SWAPPED (res
) = false;
862 /* Function destroy_loop_vec_info.
864 Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
865 stmts in the loop. */
868 destroy_loop_vec_info (loop_vec_info loop_vinfo
, bool clean_stmts
)
873 gimple_stmt_iterator si
;
875 VEC (slp_instance
, heap
) *slp_instances
;
876 slp_instance instance
;
882 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
884 bbs
= LOOP_VINFO_BBS (loop_vinfo
);
885 nbbs
= loop
->num_nodes
;
886 swapped
= LOOP_VINFO_OPERANDS_SWAPPED (loop_vinfo
);
890 free (LOOP_VINFO_BBS (loop_vinfo
));
891 free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo
));
892 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo
));
893 VEC_free (loop_p
, heap
, LOOP_VINFO_LOOP_NEST (loop_vinfo
));
894 VEC_free (gimple
, heap
, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
));
895 VEC_free (ddr_p
, heap
, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
));
902 for (j
= 0; j
< nbbs
; j
++)
904 basic_block bb
= bbs
[j
];
905 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
906 free_stmt_vec_info (gsi_stmt (si
));
908 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); )
910 gimple stmt
= gsi_stmt (si
);
912 /* We may have broken canonical form by moving a constant
913 into RHS1 of a commutative op. Fix such occurrences. */
914 if (swapped
&& is_gimple_assign (stmt
))
916 enum tree_code code
= gimple_assign_rhs_code (stmt
);
918 if ((code
== PLUS_EXPR
919 || code
== POINTER_PLUS_EXPR
920 || code
== MULT_EXPR
)
921 && CONSTANT_CLASS_P (gimple_assign_rhs1 (stmt
)))
922 swap_tree_operands (stmt
,
923 gimple_assign_rhs1_ptr (stmt
),
924 gimple_assign_rhs2_ptr (stmt
));
927 /* Free stmt_vec_info. */
928 free_stmt_vec_info (stmt
);
933 free (LOOP_VINFO_BBS (loop_vinfo
));
934 free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo
));
935 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo
));
936 VEC_free (loop_p
, heap
, LOOP_VINFO_LOOP_NEST (loop_vinfo
));
937 VEC_free (gimple
, heap
, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
));
938 VEC_free (ddr_p
, heap
, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
));
939 slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
940 FOR_EACH_VEC_ELT (slp_instance
, slp_instances
, j
, instance
)
941 vect_free_slp_instance (instance
);
943 VEC_free (slp_instance
, heap
, LOOP_VINFO_SLP_INSTANCES (loop_vinfo
));
944 VEC_free (gimple
, heap
, LOOP_VINFO_GROUPED_STORES (loop_vinfo
));
945 VEC_free (gimple
, heap
, LOOP_VINFO_REDUCTIONS (loop_vinfo
));
946 VEC_free (gimple
, heap
, LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo
));
948 if (LOOP_VINFO_PEELING_HTAB (loop_vinfo
))
949 htab_delete (LOOP_VINFO_PEELING_HTAB (loop_vinfo
));
951 destroy_cost_data (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
));
958 /* Function vect_analyze_loop_1.
960 Apply a set of analyses on LOOP, and create a loop_vec_info struct
961 for it. The different analyses will record information in the
962 loop_vec_info struct. This is a subset of the analyses applied in
963 vect_analyze_loop, to be applied on an inner-loop nested in the loop
964 that is now considered for (outer-loop) vectorization. */
967 vect_analyze_loop_1 (struct loop
*loop
)
969 loop_vec_info loop_vinfo
;
971 if (vect_print_dump_info (REPORT_DETAILS
))
972 fprintf (vect_dump
, "===== analyze_loop_nest_1 =====");
974 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
976 loop_vinfo
= vect_analyze_loop_form (loop
);
979 if (vect_print_dump_info (REPORT_DETAILS
))
980 fprintf (vect_dump
, "bad inner-loop form.");
988 /* Function vect_analyze_loop_form.
990 Verify that certain CFG restrictions hold, including:
991 - the loop has a pre-header
992 - the loop has a single entry and exit
993 - the loop exit condition is simple enough, and the number of iterations
994 can be analyzed (a countable loop). */
997 vect_analyze_loop_form (struct loop
*loop
)
999 loop_vec_info loop_vinfo
;
1001 tree number_of_iterations
= NULL
;
1002 loop_vec_info inner_loop_vinfo
= NULL
;
1004 if (vect_print_dump_info (REPORT_DETAILS
))
1005 fprintf (vect_dump
, "=== vect_analyze_loop_form ===");
1007 /* Different restrictions apply when we are considering an inner-most loop,
1008 vs. an outer (nested) loop.
1009 (FORNOW. May want to relax some of these restrictions in the future). */
1013 /* Inner-most loop. We currently require that the number of BBs is
1014 exactly 2 (the header and latch). Vectorizable inner-most loops
1025 if (loop
->num_nodes
!= 2)
1027 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1028 fprintf (vect_dump
, "not vectorized: control flow in loop.");
1032 if (empty_block_p (loop
->header
))
1034 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1035 fprintf (vect_dump
, "not vectorized: empty loop.");
1041 struct loop
*innerloop
= loop
->inner
;
1044 /* Nested loop. We currently require that the loop is doubly-nested,
1045 contains a single inner loop, and the number of BBs is exactly 5.
1046 Vectorizable outer-loops look like this:
1058 The inner-loop has the properties expected of inner-most loops
1059 as described above. */
1061 if ((loop
->inner
)->inner
|| (loop
->inner
)->next
)
1063 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1064 fprintf (vect_dump
, "not vectorized: multiple nested loops.");
1068 /* Analyze the inner-loop. */
1069 inner_loop_vinfo
= vect_analyze_loop_1 (loop
->inner
);
1070 if (!inner_loop_vinfo
)
1072 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1073 fprintf (vect_dump
, "not vectorized: Bad inner loop.");
1077 if (!expr_invariant_in_loop_p (loop
,
1078 LOOP_VINFO_NITERS (inner_loop_vinfo
)))
1080 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1082 "not vectorized: inner-loop count not invariant.");
1083 destroy_loop_vec_info (inner_loop_vinfo
, true);
1087 if (loop
->num_nodes
!= 5)
1089 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1090 fprintf (vect_dump
, "not vectorized: control flow in loop.");
1091 destroy_loop_vec_info (inner_loop_vinfo
, true);
1095 gcc_assert (EDGE_COUNT (innerloop
->header
->preds
) == 2);
1096 entryedge
= EDGE_PRED (innerloop
->header
, 0);
1097 if (EDGE_PRED (innerloop
->header
, 0)->src
== innerloop
->latch
)
1098 entryedge
= EDGE_PRED (innerloop
->header
, 1);
1100 if (entryedge
->src
!= loop
->header
1101 || !single_exit (innerloop
)
1102 || single_exit (innerloop
)->dest
!= EDGE_PRED (loop
->latch
, 0)->src
)
1104 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1105 fprintf (vect_dump
, "not vectorized: unsupported outerloop form.");
1106 destroy_loop_vec_info (inner_loop_vinfo
, true);
1110 if (vect_print_dump_info (REPORT_DETAILS
))
1111 fprintf (vect_dump
, "Considering outer-loop vectorization.");
1114 if (!single_exit (loop
)
1115 || EDGE_COUNT (loop
->header
->preds
) != 2)
1117 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1119 if (!single_exit (loop
))
1120 fprintf (vect_dump
, "not vectorized: multiple exits.");
1121 else if (EDGE_COUNT (loop
->header
->preds
) != 2)
1122 fprintf (vect_dump
, "not vectorized: too many incoming edges.");
1124 if (inner_loop_vinfo
)
1125 destroy_loop_vec_info (inner_loop_vinfo
, true);
1129 /* We assume that the loop exit condition is at the end of the loop. i.e,
1130 that the loop is represented as a do-while (with a proper if-guard
1131 before the loop if needed), where the loop header contains all the
1132 executable statements, and the latch is empty. */
1133 if (!empty_block_p (loop
->latch
)
1134 || !gimple_seq_empty_p (phi_nodes (loop
->latch
)))
1136 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1137 fprintf (vect_dump
, "not vectorized: unexpected loop form.");
1138 if (inner_loop_vinfo
)
1139 destroy_loop_vec_info (inner_loop_vinfo
, true);
1143 /* Make sure there exists a single-predecessor exit bb: */
1144 if (!single_pred_p (single_exit (loop
)->dest
))
1146 edge e
= single_exit (loop
);
1147 if (!(e
->flags
& EDGE_ABNORMAL
))
1149 split_loop_exit_edge (e
);
1150 if (vect_print_dump_info (REPORT_DETAILS
))
1151 fprintf (vect_dump
, "split exit edge.");
1155 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1156 fprintf (vect_dump
, "not vectorized: abnormal loop exit edge.");
1157 if (inner_loop_vinfo
)
1158 destroy_loop_vec_info (inner_loop_vinfo
, true);
1163 loop_cond
= vect_get_loop_niters (loop
, &number_of_iterations
);
1166 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1167 fprintf (vect_dump
, "not vectorized: complicated exit condition.");
1168 if (inner_loop_vinfo
)
1169 destroy_loop_vec_info (inner_loop_vinfo
, true);
1173 if (!number_of_iterations
)
1175 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1177 "not vectorized: number of iterations cannot be computed.");
1178 if (inner_loop_vinfo
)
1179 destroy_loop_vec_info (inner_loop_vinfo
, true);
1183 if (chrec_contains_undetermined (number_of_iterations
))
1185 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1186 fprintf (vect_dump
, "Infinite number of iterations.");
1187 if (inner_loop_vinfo
)
1188 destroy_loop_vec_info (inner_loop_vinfo
, true);
1192 if (!NITERS_KNOWN_P (number_of_iterations
))
1194 if (vect_print_dump_info (REPORT_DETAILS
))
1196 fprintf (vect_dump
, "Symbolic number of iterations is ");
1197 print_generic_expr (vect_dump
, number_of_iterations
, TDF_DETAILS
);
1200 else if (TREE_INT_CST_LOW (number_of_iterations
) == 0)
1202 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1203 fprintf (vect_dump
, "not vectorized: number of iterations = 0.");
1204 if (inner_loop_vinfo
)
1205 destroy_loop_vec_info (inner_loop_vinfo
, false);
1209 loop_vinfo
= new_loop_vec_info (loop
);
1210 LOOP_VINFO_NITERS (loop_vinfo
) = number_of_iterations
;
1211 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo
) = number_of_iterations
;
1213 STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond
)) = loop_exit_ctrl_vec_info_type
;
1215 /* CHECKME: May want to keep it around it in the future. */
1216 if (inner_loop_vinfo
)
1217 destroy_loop_vec_info (inner_loop_vinfo
, false);
1219 gcc_assert (!loop
->aux
);
1220 loop
->aux
= loop_vinfo
;
1225 /* Function vect_analyze_loop_operations.
1227 Scan the loop stmts and make sure they are all vectorizable. */
1230 vect_analyze_loop_operations (loop_vec_info loop_vinfo
, bool slp
)
1232 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1233 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1234 int nbbs
= loop
->num_nodes
;
1235 gimple_stmt_iterator si
;
1236 unsigned int vectorization_factor
= 0;
1239 stmt_vec_info stmt_info
;
1240 bool need_to_vectorize
= false;
1241 int min_profitable_iters
;
1242 int min_scalar_loop_bound
;
1244 bool only_slp_in_loop
= true, ok
;
1245 HOST_WIDE_INT max_niter
;
1247 if (vect_print_dump_info (REPORT_DETAILS
))
1248 fprintf (vect_dump
, "=== vect_analyze_loop_operations ===");
1250 gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo
));
1251 vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1254 /* If all the stmts in the loop can be SLPed, we perform only SLP, and
1255 vectorization factor of the loop is the unrolling factor required by
1256 the SLP instances. If that unrolling factor is 1, we say, that we
1257 perform pure SLP on loop - cross iteration parallelism is not
1259 for (i
= 0; i
< nbbs
; i
++)
1261 basic_block bb
= bbs
[i
];
1262 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1264 gimple stmt
= gsi_stmt (si
);
1265 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1266 gcc_assert (stmt_info
);
1267 if ((STMT_VINFO_RELEVANT_P (stmt_info
)
1268 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
1269 && !PURE_SLP_STMT (stmt_info
))
1270 /* STMT needs both SLP and loop-based vectorization. */
1271 only_slp_in_loop
= false;
1275 if (only_slp_in_loop
)
1276 vectorization_factor
= LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
);
1278 vectorization_factor
= least_common_multiple (vectorization_factor
,
1279 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
));
1281 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
1282 if (vect_print_dump_info (REPORT_DETAILS
))
1283 fprintf (vect_dump
, "Updating vectorization factor to %d ",
1284 vectorization_factor
);
1287 for (i
= 0; i
< nbbs
; i
++)
1289 basic_block bb
= bbs
[i
];
1291 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
1293 phi
= gsi_stmt (si
);
1296 stmt_info
= vinfo_for_stmt (phi
);
1297 if (vect_print_dump_info (REPORT_DETAILS
))
1299 fprintf (vect_dump
, "examining phi: ");
1300 print_gimple_stmt (vect_dump
, phi
, 0, TDF_SLIM
);
1303 /* Inner-loop loop-closed exit phi in outer-loop vectorization
1304 (i.e., a phi in the tail of the outer-loop). */
1305 if (! is_loop_header_bb_p (bb
))
1307 /* FORNOW: we currently don't support the case that these phis
1308 are not used in the outerloop (unless it is double reduction,
1309 i.e., this phi is vect_reduction_def), cause this case
1310 requires to actually do something here. */
1311 if ((!STMT_VINFO_RELEVANT_P (stmt_info
)
1312 || STMT_VINFO_LIVE_P (stmt_info
))
1313 && STMT_VINFO_DEF_TYPE (stmt_info
)
1314 != vect_double_reduction_def
)
1316 if (vect_print_dump_info (REPORT_DETAILS
))
1318 "Unsupported loop-closed phi in outer-loop.");
1322 /* If PHI is used in the outer loop, we check that its operand
1323 is defined in the inner loop. */
1324 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1329 if (gimple_phi_num_args (phi
) != 1)
1332 phi_op
= PHI_ARG_DEF (phi
, 0);
1333 if (TREE_CODE (phi_op
) != SSA_NAME
)
1336 op_def_stmt
= SSA_NAME_DEF_STMT (phi_op
);
1338 || !flow_bb_inside_loop_p (loop
, gimple_bb (op_def_stmt
))
1339 || !vinfo_for_stmt (op_def_stmt
))
1342 if (STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1343 != vect_used_in_outer
1344 && STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt
))
1345 != vect_used_in_outer_by_reduction
)
1352 gcc_assert (stmt_info
);
1354 if (STMT_VINFO_LIVE_P (stmt_info
))
1356 /* FORNOW: not yet supported. */
1357 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1358 fprintf (vect_dump
, "not vectorized: value used after loop.");
1362 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
1363 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_induction_def
)
1365 /* A scalar-dependence cycle that we don't support. */
1366 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1367 fprintf (vect_dump
, "not vectorized: scalar dependence cycle.");
1371 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1373 need_to_vectorize
= true;
1374 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
1375 ok
= vectorizable_induction (phi
, NULL
, NULL
);
1380 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1383 "not vectorized: relevant phi not supported: ");
1384 print_gimple_stmt (vect_dump
, phi
, 0, TDF_SLIM
);
1390 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1392 gimple stmt
= gsi_stmt (si
);
1393 if (!vect_analyze_stmt (stmt
, &need_to_vectorize
, NULL
))
1398 /* All operations in the loop are either irrelevant (deal with loop
1399 control, or dead), or only used outside the loop and can be moved
1400 out of the loop (e.g. invariants, inductions). The loop can be
1401 optimized away by scalar optimizations. We're better off not
1402 touching this loop. */
1403 if (!need_to_vectorize
)
1405 if (vect_print_dump_info (REPORT_DETAILS
))
1407 "All the computation can be taken out of the loop.");
1408 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1410 "not vectorized: redundant loop. no profit to vectorize.");
1414 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1415 && vect_print_dump_info (REPORT_DETAILS
))
1417 "vectorization_factor = %d, niters = " HOST_WIDE_INT_PRINT_DEC
,
1418 vectorization_factor
, LOOP_VINFO_INT_NITERS (loop_vinfo
));
1420 if ((LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1421 && (LOOP_VINFO_INT_NITERS (loop_vinfo
) < vectorization_factor
))
1422 || ((max_niter
= max_stmt_executions_int (loop
)) != -1
1423 && (unsigned HOST_WIDE_INT
) max_niter
< vectorization_factor
))
1425 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1426 fprintf (vect_dump
, "not vectorized: iteration count too small.");
1427 if (vect_print_dump_info (REPORT_DETAILS
))
1428 fprintf (vect_dump
,"not vectorized: iteration count smaller than "
1429 "vectorization factor.");
1433 /* Analyze cost. Decide if worth while to vectorize. */
1435 /* Once VF is set, SLP costs should be updated since the number of created
1436 vector stmts depends on VF. */
1437 vect_update_slp_costs_according_to_vf (loop_vinfo
);
1439 min_profitable_iters
= vect_estimate_min_profitable_iters (loop_vinfo
);
1440 LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo
) = min_profitable_iters
;
1442 if (min_profitable_iters
< 0)
1444 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1445 fprintf (vect_dump
, "not vectorized: vectorization not profitable.");
1446 if (vect_print_dump_info (REPORT_DETAILS
))
1447 fprintf (vect_dump
, "not vectorized: vector version will never be "
1452 min_scalar_loop_bound
= ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND
)
1453 * vectorization_factor
) - 1);
1455 /* Use the cost model only if it is more conservative than user specified
1458 th
= (unsigned) min_scalar_loop_bound
;
1459 if (min_profitable_iters
1460 && (!min_scalar_loop_bound
1461 || min_profitable_iters
> min_scalar_loop_bound
))
1462 th
= (unsigned) min_profitable_iters
;
1464 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1465 && LOOP_VINFO_INT_NITERS (loop_vinfo
) <= th
)
1467 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1468 fprintf (vect_dump
, "not vectorized: vectorization not "
1470 if (vect_print_dump_info (REPORT_DETAILS
))
1471 fprintf (vect_dump
, "not vectorized: iteration count smaller than "
1472 "user specified loop bound parameter or minimum "
1473 "profitable iterations (whichever is more conservative).");
1477 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1478 || LOOP_VINFO_INT_NITERS (loop_vinfo
) % vectorization_factor
!= 0
1479 || LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
))
1481 if (vect_print_dump_info (REPORT_DETAILS
))
1482 fprintf (vect_dump
, "epilog loop required.");
1483 if (!vect_can_advance_ivs_p (loop_vinfo
))
1485 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1487 "not vectorized: can't create epilog loop 1.");
1490 if (!slpeel_can_duplicate_loop_p (loop
, single_exit (loop
)))
1492 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1494 "not vectorized: can't create epilog loop 2.");
1503 /* Function vect_analyze_loop_2.
1505 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1506 for it. The different analyses will record information in the
1507 loop_vec_info struct. */
1509 vect_analyze_loop_2 (loop_vec_info loop_vinfo
)
1511 bool ok
, slp
= false;
1512 int max_vf
= MAX_VECTORIZATION_FACTOR
;
1515 /* Find all data references in the loop (which correspond to vdefs/vuses)
1516 and analyze their evolution in the loop. Also adjust the minimal
1517 vectorization factor according to the loads and stores.
1519 FORNOW: Handle only simple, array references, which
1520 alignment can be forced, and aligned pointer-references. */
1522 ok
= vect_analyze_data_refs (loop_vinfo
, NULL
, &min_vf
);
1525 if (vect_print_dump_info (REPORT_DETAILS
))
1526 fprintf (vect_dump
, "bad data references.");
1530 /* Classify all cross-iteration scalar data-flow cycles.
1531 Cross-iteration cycles caused by virtual phis are analyzed separately. */
1533 vect_analyze_scalar_cycles (loop_vinfo
);
1535 vect_pattern_recog (loop_vinfo
, NULL
);
1537 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
1539 ok
= vect_mark_stmts_to_be_vectorized (loop_vinfo
);
1542 if (vect_print_dump_info (REPORT_DETAILS
))
1543 fprintf (vect_dump
, "unexpected pattern.");
1547 /* Analyze data dependences between the data-refs in the loop
1548 and adjust the maximum vectorization factor according to
1550 FORNOW: fail at the first data dependence that we encounter. */
1552 ok
= vect_analyze_data_ref_dependences (loop_vinfo
, NULL
, &max_vf
);
1556 if (vect_print_dump_info (REPORT_DETAILS
))
1557 fprintf (vect_dump
, "bad data dependence.");
1561 ok
= vect_determine_vectorization_factor (loop_vinfo
);
1564 if (vect_print_dump_info (REPORT_DETAILS
))
1565 fprintf (vect_dump
, "can't determine vectorization factor.");
1568 if (max_vf
< LOOP_VINFO_VECT_FACTOR (loop_vinfo
))
1570 if (vect_print_dump_info (REPORT_DETAILS
))
1571 fprintf (vect_dump
, "bad data dependence.");
1575 /* Analyze the alignment of the data-refs in the loop.
1576 Fail if a data reference is found that cannot be vectorized. */
1578 ok
= vect_analyze_data_refs_alignment (loop_vinfo
, NULL
);
1581 if (vect_print_dump_info (REPORT_DETAILS
))
1582 fprintf (vect_dump
, "bad data alignment.");
1586 /* Analyze the access patterns of the data-refs in the loop (consecutive,
1587 complex, etc.). FORNOW: Only handle consecutive access pattern. */
1589 ok
= vect_analyze_data_ref_accesses (loop_vinfo
, NULL
);
1592 if (vect_print_dump_info (REPORT_DETAILS
))
1593 fprintf (vect_dump
, "bad data access.");
1597 /* Prune the list of ddrs to be tested at run-time by versioning for alias.
1598 It is important to call pruning after vect_analyze_data_ref_accesses,
1599 since we use grouping information gathered by interleaving analysis. */
1600 ok
= vect_prune_runtime_alias_test_list (loop_vinfo
);
1603 if (vect_print_dump_info (REPORT_DETAILS
))
1604 fprintf (vect_dump
, "too long list of versioning for alias "
1609 /* This pass will decide on using loop versioning and/or loop peeling in
1610 order to enhance the alignment of data references in the loop. */
1612 ok
= vect_enhance_data_refs_alignment (loop_vinfo
);
1615 if (vect_print_dump_info (REPORT_DETAILS
))
1616 fprintf (vect_dump
, "bad data alignment.");
1620 /* Check the SLP opportunities in the loop, analyze and build SLP trees. */
1621 ok
= vect_analyze_slp (loop_vinfo
, NULL
);
1624 /* Decide which possible SLP instances to SLP. */
1625 slp
= vect_make_slp_decision (loop_vinfo
);
1627 /* Find stmts that need to be both vectorized and SLPed. */
1628 vect_detect_hybrid_slp (loop_vinfo
);
1633 /* Scan all the operations in the loop and make sure they are
1636 ok
= vect_analyze_loop_operations (loop_vinfo
, slp
);
1639 if (vect_print_dump_info (REPORT_DETAILS
))
1640 fprintf (vect_dump
, "bad operation or unsupported loop bound.");
1647 /* Function vect_analyze_loop.
1649 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1650 for it. The different analyses will record information in the
1651 loop_vec_info struct. */
1653 vect_analyze_loop (struct loop
*loop
)
1655 loop_vec_info loop_vinfo
;
1656 unsigned int vector_sizes
;
1658 /* Autodetect first vector size we try. */
1659 current_vector_size
= 0;
1660 vector_sizes
= targetm
.vectorize
.autovectorize_vector_sizes ();
1662 if (vect_print_dump_info (REPORT_DETAILS
))
1663 fprintf (vect_dump
, "===== analyze_loop_nest =====");
1665 if (loop_outer (loop
)
1666 && loop_vec_info_for_loop (loop_outer (loop
))
1667 && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop
))))
1669 if (vect_print_dump_info (REPORT_DETAILS
))
1670 fprintf (vect_dump
, "outer-loop already vectorized.");
1676 /* Check the CFG characteristics of the loop (nesting, entry/exit). */
1677 loop_vinfo
= vect_analyze_loop_form (loop
);
1680 if (vect_print_dump_info (REPORT_DETAILS
))
1681 fprintf (vect_dump
, "bad loop form.");
1685 if (vect_analyze_loop_2 (loop_vinfo
))
1687 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
) = 1;
1692 destroy_loop_vec_info (loop_vinfo
, true);
1694 vector_sizes
&= ~current_vector_size
;
1695 if (vector_sizes
== 0
1696 || current_vector_size
== 0)
1699 /* Try the next biggest vector size. */
1700 current_vector_size
= 1 << floor_log2 (vector_sizes
);
1701 if (vect_print_dump_info (REPORT_DETAILS
))
1702 fprintf (vect_dump
, "***** Re-trying analysis with "
1703 "vector size %d\n", current_vector_size
);
1708 /* Function reduction_code_for_scalar_code
1711 CODE - tree_code of a reduction operations.
1714 REDUC_CODE - the corresponding tree-code to be used to reduce the
1715 vector of partial results into a single scalar result (which
1716 will also reside in a vector) or ERROR_MARK if the operation is
1717 a supported reduction operation, but does not have such tree-code.
1719 Return FALSE if CODE currently cannot be vectorized as reduction. */
1722 reduction_code_for_scalar_code (enum tree_code code
,
1723 enum tree_code
*reduc_code
)
1728 *reduc_code
= REDUC_MAX_EXPR
;
1732 *reduc_code
= REDUC_MIN_EXPR
;
1736 *reduc_code
= REDUC_PLUS_EXPR
;
1744 *reduc_code
= ERROR_MARK
;
1753 /* Error reporting helper for vect_is_simple_reduction below. GIMPLE statement
1754 STMT is printed with a message MSG. */
1757 report_vect_op (gimple stmt
, const char *msg
)
1759 fprintf (vect_dump
, "%s", msg
);
1760 print_gimple_stmt (vect_dump
, stmt
, 0, TDF_SLIM
);
1764 /* Detect SLP reduction of the form:
1774 PHI is the reduction phi node (#a1 = phi <a5, a0> above)
1775 FIRST_STMT is the first reduction stmt in the chain
1776 (a2 = operation (a1)).
1778 Return TRUE if a reduction chain was detected. */
1781 vect_is_slp_reduction (loop_vec_info loop_info
, gimple phi
, gimple first_stmt
)
1783 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
1784 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
1785 enum tree_code code
;
1786 gimple current_stmt
= NULL
, loop_use_stmt
= NULL
, first
, next_stmt
;
1787 stmt_vec_info use_stmt_info
, current_stmt_info
;
1789 imm_use_iterator imm_iter
;
1790 use_operand_p use_p
;
1791 int nloop_uses
, size
= 0, n_out_of_loop_uses
;
1794 if (loop
!= vect_loop
)
1797 lhs
= PHI_RESULT (phi
);
1798 code
= gimple_assign_rhs_code (first_stmt
);
1802 n_out_of_loop_uses
= 0;
1803 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
1805 gimple use_stmt
= USE_STMT (use_p
);
1806 if (is_gimple_debug (use_stmt
))
1809 use_stmt
= USE_STMT (use_p
);
1811 /* Check if we got back to the reduction phi. */
1812 if (use_stmt
== phi
)
1814 loop_use_stmt
= use_stmt
;
1819 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
1821 if (vinfo_for_stmt (use_stmt
)
1822 && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (use_stmt
)))
1824 loop_use_stmt
= use_stmt
;
1829 n_out_of_loop_uses
++;
1831 /* There are can be either a single use in the loop or two uses in
1833 if (nloop_uses
> 1 || (n_out_of_loop_uses
&& nloop_uses
))
1840 /* We reached a statement with no loop uses. */
1841 if (nloop_uses
== 0)
1844 /* This is a loop exit phi, and we haven't reached the reduction phi. */
1845 if (gimple_code (loop_use_stmt
) == GIMPLE_PHI
)
1848 if (!is_gimple_assign (loop_use_stmt
)
1849 || code
!= gimple_assign_rhs_code (loop_use_stmt
)
1850 || !flow_bb_inside_loop_p (loop
, gimple_bb (loop_use_stmt
)))
1853 /* Insert USE_STMT into reduction chain. */
1854 use_stmt_info
= vinfo_for_stmt (loop_use_stmt
);
1857 current_stmt_info
= vinfo_for_stmt (current_stmt
);
1858 GROUP_NEXT_ELEMENT (current_stmt_info
) = loop_use_stmt
;
1859 GROUP_FIRST_ELEMENT (use_stmt_info
)
1860 = GROUP_FIRST_ELEMENT (current_stmt_info
);
1863 GROUP_FIRST_ELEMENT (use_stmt_info
) = loop_use_stmt
;
1865 lhs
= gimple_assign_lhs (loop_use_stmt
);
1866 current_stmt
= loop_use_stmt
;
1870 if (!found
|| loop_use_stmt
!= phi
|| size
< 2)
1873 /* Swap the operands, if needed, to make the reduction operand be the second
1875 lhs
= PHI_RESULT (phi
);
1876 next_stmt
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
1879 if (gimple_assign_rhs2 (next_stmt
) == lhs
)
1881 tree op
= gimple_assign_rhs1 (next_stmt
);
1882 gimple def_stmt
= NULL
;
1884 if (TREE_CODE (op
) == SSA_NAME
)
1885 def_stmt
= SSA_NAME_DEF_STMT (op
);
1887 /* Check that the other def is either defined in the loop
1888 ("vect_internal_def"), or it's an induction (defined by a
1889 loop-header phi-node). */
1891 && gimple_bb (def_stmt
)
1892 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
1893 && (is_gimple_assign (def_stmt
)
1894 || is_gimple_call (def_stmt
)
1895 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
1896 == vect_induction_def
1897 || (gimple_code (def_stmt
) == GIMPLE_PHI
1898 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
1899 == vect_internal_def
1900 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
1902 lhs
= gimple_assign_lhs (next_stmt
);
1903 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
1911 tree op
= gimple_assign_rhs2 (next_stmt
);
1912 gimple def_stmt
= NULL
;
1914 if (TREE_CODE (op
) == SSA_NAME
)
1915 def_stmt
= SSA_NAME_DEF_STMT (op
);
1917 /* Check that the other def is either defined in the loop
1918 ("vect_internal_def"), or it's an induction (defined by a
1919 loop-header phi-node). */
1921 && gimple_bb (def_stmt
)
1922 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
1923 && (is_gimple_assign (def_stmt
)
1924 || is_gimple_call (def_stmt
)
1925 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
1926 == vect_induction_def
1927 || (gimple_code (def_stmt
) == GIMPLE_PHI
1928 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
1929 == vect_internal_def
1930 && !is_loop_header_bb_p (gimple_bb (def_stmt
)))))
1932 if (vect_print_dump_info (REPORT_DETAILS
))
1934 fprintf (vect_dump
, "swapping oprnds: ");
1935 print_gimple_stmt (vect_dump
, next_stmt
, 0, TDF_SLIM
);
1938 swap_tree_operands (next_stmt
,
1939 gimple_assign_rhs1_ptr (next_stmt
),
1940 gimple_assign_rhs2_ptr (next_stmt
));
1941 update_stmt (next_stmt
);
1943 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (next_stmt
)))
1944 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
1950 lhs
= gimple_assign_lhs (next_stmt
);
1951 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
1954 /* Save the chain for further analysis in SLP detection. */
1955 first
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt
));
1956 VEC_safe_push (gimple
, heap
, LOOP_VINFO_REDUCTION_CHAINS (loop_info
), first
);
1957 GROUP_SIZE (vinfo_for_stmt (first
)) = size
;
1963 /* Function vect_is_simple_reduction_1
1965 (1) Detect a cross-iteration def-use cycle that represents a simple
1966 reduction computation. We look for the following pattern:
1971 a2 = operation (a3, a1)
1974 1. operation is commutative and associative and it is safe to
1975 change the order of the computation (if CHECK_REDUCTION is true)
1976 2. no uses for a2 in the loop (a2 is used out of the loop)
1977 3. no uses of a1 in the loop besides the reduction operation
1978 4. no uses of a1 outside the loop.
1980 Conditions 1,4 are tested here.
1981 Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
1983 (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
1984 nested cycles, if CHECK_REDUCTION is false.
1986 (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
1990 inner loop (def of a3)
1993 If MODIFY is true it tries also to rework the code in-place to enable
1994 detection of more reduction patterns. For the time being we rewrite
1995 "res -= RHS" into "rhs += -RHS" when it seems worthwhile.
1999 vect_is_simple_reduction_1 (loop_vec_info loop_info
, gimple phi
,
2000 bool check_reduction
, bool *double_reduc
,
2003 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
2004 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
2005 edge latch_e
= loop_latch_edge (loop
);
2006 tree loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
2007 gimple def_stmt
, def1
= NULL
, def2
= NULL
;
2008 enum tree_code orig_code
, code
;
2009 tree op1
, op2
, op3
= NULL_TREE
, op4
= NULL_TREE
;
2013 imm_use_iterator imm_iter
;
2014 use_operand_p use_p
;
2017 *double_reduc
= false;
2019 /* If CHECK_REDUCTION is true, we assume inner-most loop vectorization,
2020 otherwise, we assume outer loop vectorization. */
2021 gcc_assert ((check_reduction
&& loop
== vect_loop
)
2022 || (!check_reduction
&& flow_loop_nested_p (vect_loop
, loop
)));
2024 name
= PHI_RESULT (phi
);
2026 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2028 gimple use_stmt
= USE_STMT (use_p
);
2029 if (is_gimple_debug (use_stmt
))
2032 if (!flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
)))
2034 if (vect_print_dump_info (REPORT_DETAILS
))
2035 fprintf (vect_dump
, "intermediate value used outside loop.");
2040 if (vinfo_for_stmt (use_stmt
)
2041 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt
)))
2045 if (vect_print_dump_info (REPORT_DETAILS
))
2046 fprintf (vect_dump
, "reduction used in loop.");
2051 if (TREE_CODE (loop_arg
) != SSA_NAME
)
2053 if (vect_print_dump_info (REPORT_DETAILS
))
2055 fprintf (vect_dump
, "reduction: not ssa_name: ");
2056 print_generic_expr (vect_dump
, loop_arg
, TDF_SLIM
);
2061 def_stmt
= SSA_NAME_DEF_STMT (loop_arg
);
2064 if (vect_print_dump_info (REPORT_DETAILS
))
2065 fprintf (vect_dump
, "reduction: no def_stmt.");
2069 if (!is_gimple_assign (def_stmt
) && gimple_code (def_stmt
) != GIMPLE_PHI
)
2071 if (vect_print_dump_info (REPORT_DETAILS
))
2072 print_gimple_stmt (vect_dump
, def_stmt
, 0, TDF_SLIM
);
2076 if (is_gimple_assign (def_stmt
))
2078 name
= gimple_assign_lhs (def_stmt
);
2083 name
= PHI_RESULT (def_stmt
);
2088 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
2090 gimple use_stmt
= USE_STMT (use_p
);
2091 if (is_gimple_debug (use_stmt
))
2093 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
))
2094 && vinfo_for_stmt (use_stmt
)
2095 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt
)))
2099 if (vect_print_dump_info (REPORT_DETAILS
))
2100 fprintf (vect_dump
, "reduction used in loop.");
2105 /* If DEF_STMT is a phi node itself, we expect it to have a single argument
2106 defined in the inner loop. */
2109 op1
= PHI_ARG_DEF (def_stmt
, 0);
2111 if (gimple_phi_num_args (def_stmt
) != 1
2112 || TREE_CODE (op1
) != SSA_NAME
)
2114 if (vect_print_dump_info (REPORT_DETAILS
))
2115 fprintf (vect_dump
, "unsupported phi node definition.");
2120 def1
= SSA_NAME_DEF_STMT (op1
);
2121 if (flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2123 && flow_bb_inside_loop_p (loop
->inner
, gimple_bb (def1
))
2124 && is_gimple_assign (def1
))
2126 if (vect_print_dump_info (REPORT_DETAILS
))
2127 report_vect_op (def_stmt
, "detected double reduction: ");
2129 *double_reduc
= true;
2136 code
= orig_code
= gimple_assign_rhs_code (def_stmt
);
2138 /* We can handle "res -= x[i]", which is non-associative by
2139 simply rewriting this into "res += -x[i]". Avoid changing
2140 gimple instruction for the first simple tests and only do this
2141 if we're allowed to change code at all. */
2142 if (code
== MINUS_EXPR
2144 && (op1
= gimple_assign_rhs1 (def_stmt
))
2145 && TREE_CODE (op1
) == SSA_NAME
2146 && SSA_NAME_DEF_STMT (op1
) == phi
)
2150 && (!commutative_tree_code (code
) || !associative_tree_code (code
)))
2152 if (vect_print_dump_info (REPORT_DETAILS
))
2153 report_vect_op (def_stmt
, "reduction: not commutative/associative: ");
2157 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
2159 if (code
!= COND_EXPR
)
2161 if (vect_print_dump_info (REPORT_DETAILS
))
2162 report_vect_op (def_stmt
, "reduction: not binary operation: ");
2167 op3
= gimple_assign_rhs1 (def_stmt
);
2168 if (COMPARISON_CLASS_P (op3
))
2170 op4
= TREE_OPERAND (op3
, 1);
2171 op3
= TREE_OPERAND (op3
, 0);
2174 op1
= gimple_assign_rhs2 (def_stmt
);
2175 op2
= gimple_assign_rhs3 (def_stmt
);
2177 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2179 if (vect_print_dump_info (REPORT_DETAILS
))
2180 report_vect_op (def_stmt
, "reduction: uses not ssa_names: ");
2187 op1
= gimple_assign_rhs1 (def_stmt
);
2188 op2
= gimple_assign_rhs2 (def_stmt
);
2190 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
2192 if (vect_print_dump_info (REPORT_DETAILS
))
2193 report_vect_op (def_stmt
, "reduction: uses not ssa_names: ");
2199 type
= TREE_TYPE (gimple_assign_lhs (def_stmt
));
2200 if ((TREE_CODE (op1
) == SSA_NAME
2201 && !types_compatible_p (type
,TREE_TYPE (op1
)))
2202 || (TREE_CODE (op2
) == SSA_NAME
2203 && !types_compatible_p (type
, TREE_TYPE (op2
)))
2204 || (op3
&& TREE_CODE (op3
) == SSA_NAME
2205 && !types_compatible_p (type
, TREE_TYPE (op3
)))
2206 || (op4
&& TREE_CODE (op4
) == SSA_NAME
2207 && !types_compatible_p (type
, TREE_TYPE (op4
))))
2209 if (vect_print_dump_info (REPORT_DETAILS
))
2211 fprintf (vect_dump
, "reduction: multiple types: operation type: ");
2212 print_generic_expr (vect_dump
, type
, TDF_SLIM
);
2213 fprintf (vect_dump
, ", operands types: ");
2214 print_generic_expr (vect_dump
, TREE_TYPE (op1
), TDF_SLIM
);
2215 fprintf (vect_dump
, ",");
2216 print_generic_expr (vect_dump
, TREE_TYPE (op2
), TDF_SLIM
);
2219 fprintf (vect_dump
, ",");
2220 print_generic_expr (vect_dump
, TREE_TYPE (op3
), TDF_SLIM
);
2225 fprintf (vect_dump
, ",");
2226 print_generic_expr (vect_dump
, TREE_TYPE (op4
), TDF_SLIM
);
2233 /* Check that it's ok to change the order of the computation.
2234 Generally, when vectorizing a reduction we change the order of the
2235 computation. This may change the behavior of the program in some
2236 cases, so we need to check that this is ok. One exception is when
2237 vectorizing an outer-loop: the inner-loop is executed sequentially,
2238 and therefore vectorizing reductions in the inner-loop during
2239 outer-loop vectorization is safe. */
2241 /* CHECKME: check for !flag_finite_math_only too? */
2242 if (SCALAR_FLOAT_TYPE_P (type
) && !flag_associative_math
2245 /* Changing the order of operations changes the semantics. */
2246 if (vect_print_dump_info (REPORT_DETAILS
))
2247 report_vect_op (def_stmt
, "reduction: unsafe fp math optimization: ");
2250 else if (INTEGRAL_TYPE_P (type
) && TYPE_OVERFLOW_TRAPS (type
)
2253 /* Changing the order of operations changes the semantics. */
2254 if (vect_print_dump_info (REPORT_DETAILS
))
2255 report_vect_op (def_stmt
, "reduction: unsafe int math optimization: ");
2258 else if (SAT_FIXED_POINT_TYPE_P (type
) && check_reduction
)
2260 /* Changing the order of operations changes the semantics. */
2261 if (vect_print_dump_info (REPORT_DETAILS
))
2262 report_vect_op (def_stmt
,
2263 "reduction: unsafe fixed-point math optimization: ");
2267 /* If we detected "res -= x[i]" earlier, rewrite it into
2268 "res += -x[i]" now. If this turns out to be useless reassoc
2269 will clean it up again. */
2270 if (orig_code
== MINUS_EXPR
)
2272 tree rhs
= gimple_assign_rhs2 (def_stmt
);
2273 tree negrhs
= make_ssa_name (SSA_NAME_VAR (rhs
), NULL
);
2274 gimple negate_stmt
= gimple_build_assign_with_ops (NEGATE_EXPR
, negrhs
,
2276 gimple_stmt_iterator gsi
= gsi_for_stmt (def_stmt
);
2277 set_vinfo_for_stmt (negate_stmt
, new_stmt_vec_info (negate_stmt
,
2279 gsi_insert_before (&gsi
, negate_stmt
, GSI_NEW_STMT
);
2280 gimple_assign_set_rhs2 (def_stmt
, negrhs
);
2281 gimple_assign_set_rhs_code (def_stmt
, PLUS_EXPR
);
2282 update_stmt (def_stmt
);
2285 /* Reduction is safe. We're dealing with one of the following:
2286 1) integer arithmetic and no trapv
2287 2) floating point arithmetic, and special flags permit this optimization
2288 3) nested cycle (i.e., outer loop vectorization). */
2289 if (TREE_CODE (op1
) == SSA_NAME
)
2290 def1
= SSA_NAME_DEF_STMT (op1
);
2292 if (TREE_CODE (op2
) == SSA_NAME
)
2293 def2
= SSA_NAME_DEF_STMT (op2
);
2295 if (code
!= COND_EXPR
2296 && ((!def1
|| gimple_nop_p (def1
)) && (!def2
|| gimple_nop_p (def2
))))
2298 if (vect_print_dump_info (REPORT_DETAILS
))
2299 report_vect_op (def_stmt
, "reduction: no defs for operands: ");
2303 /* Check that one def is the reduction def, defined by PHI,
2304 the other def is either defined in the loop ("vect_internal_def"),
2305 or it's an induction (defined by a loop-header phi-node). */
2307 if (def2
&& def2
== phi
2308 && (code
== COND_EXPR
2309 || !def1
|| gimple_nop_p (def1
)
2310 || (def1
&& flow_bb_inside_loop_p (loop
, gimple_bb (def1
))
2311 && (is_gimple_assign (def1
)
2312 || is_gimple_call (def1
)
2313 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
2314 == vect_induction_def
2315 || (gimple_code (def1
) == GIMPLE_PHI
2316 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
2317 == vect_internal_def
2318 && !is_loop_header_bb_p (gimple_bb (def1
)))))))
2320 if (vect_print_dump_info (REPORT_DETAILS
))
2321 report_vect_op (def_stmt
, "detected reduction: ");
2325 if (def1
&& def1
== phi
2326 && (code
== COND_EXPR
2327 || !def2
|| gimple_nop_p (def2
)
2328 || (def2
&& flow_bb_inside_loop_p (loop
, gimple_bb (def2
))
2329 && (is_gimple_assign (def2
)
2330 || is_gimple_call (def2
)
2331 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
2332 == vect_induction_def
2333 || (gimple_code (def2
) == GIMPLE_PHI
2334 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
2335 == vect_internal_def
2336 && !is_loop_header_bb_p (gimple_bb (def2
)))))))
2338 if (check_reduction
)
2340 /* Swap operands (just for simplicity - so that the rest of the code
2341 can assume that the reduction variable is always the last (second)
2343 if (vect_print_dump_info (REPORT_DETAILS
))
2344 report_vect_op (def_stmt
,
2345 "detected reduction: need to swap operands: ");
2347 swap_tree_operands (def_stmt
, gimple_assign_rhs1_ptr (def_stmt
),
2348 gimple_assign_rhs2_ptr (def_stmt
));
2350 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (def_stmt
)))
2351 LOOP_VINFO_OPERANDS_SWAPPED (loop_info
) = true;
2355 if (vect_print_dump_info (REPORT_DETAILS
))
2356 report_vect_op (def_stmt
, "detected reduction: ");
2362 /* Try to find SLP reduction chain. */
2363 if (check_reduction
&& vect_is_slp_reduction (loop_info
, phi
, def_stmt
))
2365 if (vect_print_dump_info (REPORT_DETAILS
))
2366 report_vect_op (def_stmt
, "reduction: detected reduction chain: ");
2371 if (vect_print_dump_info (REPORT_DETAILS
))
2372 report_vect_op (def_stmt
, "reduction: unknown pattern: ");
2377 /* Wrapper around vect_is_simple_reduction_1, that won't modify code
2378 in-place. Arguments as there. */
2381 vect_is_simple_reduction (loop_vec_info loop_info
, gimple phi
,
2382 bool check_reduction
, bool *double_reduc
)
2384 return vect_is_simple_reduction_1 (loop_info
, phi
, check_reduction
,
2385 double_reduc
, false);
2388 /* Wrapper around vect_is_simple_reduction_1, which will modify code
2389 in-place if it enables detection of more reductions. Arguments
2393 vect_force_simple_reduction (loop_vec_info loop_info
, gimple phi
,
2394 bool check_reduction
, bool *double_reduc
)
2396 return vect_is_simple_reduction_1 (loop_info
, phi
, check_reduction
,
2397 double_reduc
, true);
2400 /* Calculate the cost of one scalar iteration of the loop. */
2402 vect_get_single_scalar_iteration_cost (loop_vec_info loop_vinfo
)
2404 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2405 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
2406 int nbbs
= loop
->num_nodes
, factor
, scalar_single_iter_cost
= 0;
2407 int innerloop_iters
, i
, stmt_cost
;
2409 /* Count statements in scalar loop. Using this as scalar cost for a single
2412 TODO: Add outer loop support.
2414 TODO: Consider assigning different costs to different scalar
2418 innerloop_iters
= 1;
2420 innerloop_iters
= 50; /* FIXME */
2422 for (i
= 0; i
< nbbs
; i
++)
2424 gimple_stmt_iterator si
;
2425 basic_block bb
= bbs
[i
];
2427 if (bb
->loop_father
== loop
->inner
)
2428 factor
= innerloop_iters
;
2432 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
2434 gimple stmt
= gsi_stmt (si
);
2435 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2437 if (!is_gimple_assign (stmt
) && !is_gimple_call (stmt
))
2440 /* Skip stmts that are not vectorized inside the loop. */
2442 && !STMT_VINFO_RELEVANT_P (stmt_info
)
2443 && (!STMT_VINFO_LIVE_P (stmt_info
)
2444 || !VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
2445 && !STMT_VINFO_IN_PATTERN_P (stmt_info
))
2448 if (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
)))
2450 if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt
))))
2451 stmt_cost
= vect_get_stmt_cost (scalar_load
);
2453 stmt_cost
= vect_get_stmt_cost (scalar_store
);
2456 stmt_cost
= vect_get_stmt_cost (scalar_stmt
);
2458 scalar_single_iter_cost
+= stmt_cost
* factor
;
2461 return scalar_single_iter_cost
;
2464 /* Calculate cost of peeling the loop PEEL_ITERS_PROLOGUE times. */
2466 vect_get_known_peeling_cost (loop_vec_info loop_vinfo
, int peel_iters_prologue
,
2467 int *peel_iters_epilogue
,
2468 int scalar_single_iter_cost
,
2469 stmt_vector_for_cost
*prologue_cost_vec
,
2470 stmt_vector_for_cost
*epilogue_cost_vec
)
2473 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2475 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
2477 *peel_iters_epilogue
= vf
/2;
2478 if (vect_print_dump_info (REPORT_COST
))
2479 fprintf (vect_dump
, "cost model: "
2480 "epilogue peel iters set to vf/2 because "
2481 "loop iterations are unknown .");
2483 /* If peeled iterations are known but number of scalar loop
2484 iterations are unknown, count a taken branch per peeled loop. */
2485 retval
= record_stmt_cost (prologue_cost_vec
, 2, cond_branch_taken
,
2486 NULL
, 0, vect_prologue
);
2490 int niters
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
2491 peel_iters_prologue
= niters
< peel_iters_prologue
?
2492 niters
: peel_iters_prologue
;
2493 *peel_iters_epilogue
= (niters
- peel_iters_prologue
) % vf
;
2494 /* If we need to peel for gaps, but no peeling is required, we have to
2495 peel VF iterations. */
2496 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) && !*peel_iters_epilogue
)
2497 *peel_iters_epilogue
= vf
;
2500 if (peel_iters_prologue
)
2501 retval
+= record_stmt_cost (prologue_cost_vec
,
2502 peel_iters_prologue
* scalar_single_iter_cost
,
2503 scalar_stmt
, NULL
, 0, vect_prologue
);
2504 if (*peel_iters_epilogue
)
2505 retval
+= record_stmt_cost (epilogue_cost_vec
,
2506 *peel_iters_epilogue
* scalar_single_iter_cost
,
2507 scalar_stmt
, NULL
, 0, vect_epilogue
);
2511 /* Function vect_estimate_min_profitable_iters
2513 Return the number of iterations required for the vector version of the
2514 loop to be profitable relative to the cost of the scalar version of the
2517 TODO: Take profile info into account before making vectorization
2518 decisions, if available. */
2521 vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo
)
2523 int min_profitable_iters
;
2524 int peel_iters_prologue
;
2525 int peel_iters_epilogue
;
2526 unsigned vec_inside_cost
= 0;
2527 int vec_outside_cost
= 0;
2528 unsigned vec_prologue_cost
= 0;
2529 unsigned vec_epilogue_cost
= 0;
2530 int scalar_single_iter_cost
= 0;
2531 int scalar_outside_cost
= 0;
2532 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2533 int npeel
= LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
);
2534 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2536 /* Cost model disabled. */
2537 if (!flag_vect_cost_model
)
2539 if (vect_print_dump_info (REPORT_COST
))
2540 fprintf (vect_dump
, "cost model disabled.");
2544 /* Requires loop versioning tests to handle misalignment. */
2545 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
))
2547 /* FIXME: Make cost depend on complexity of individual check. */
2548 unsigned len
= VEC_length (gimple
,
2549 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
));
2550 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
2552 if (vect_print_dump_info (REPORT_COST
))
2553 fprintf (vect_dump
, "cost model: Adding cost of checks for loop "
2554 "versioning to treat misalignment.\n");
2557 /* Requires loop versioning with alias checks. */
2558 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2560 /* FIXME: Make cost depend on complexity of individual check. */
2561 unsigned len
= VEC_length (ddr_p
, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
));
2562 (void) add_stmt_cost (target_cost_data
, len
, vector_stmt
, NULL
, 0,
2564 if (vect_print_dump_info (REPORT_COST
))
2565 fprintf (vect_dump
, "cost model: Adding cost of checks for loop "
2566 "versioning aliasing.\n");
2569 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2570 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2571 (void) add_stmt_cost (target_cost_data
, 1, cond_branch_taken
, NULL
, 0,
2574 /* Count statements in scalar loop. Using this as scalar cost for a single
2577 TODO: Add outer loop support.
2579 TODO: Consider assigning different costs to different scalar
2582 scalar_single_iter_cost
= vect_get_single_scalar_iteration_cost (loop_vinfo
);
2584 /* Add additional cost for the peeled instructions in prologue and epilogue
2587 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
2588 at compile-time - we assume it's vf/2 (the worst would be vf-1).
2590 TODO: Build an expression that represents peel_iters for prologue and
2591 epilogue to be used in a run-time test. */
2595 peel_iters_prologue
= vf
/2;
2596 if (vect_print_dump_info (REPORT_COST
))
2597 fprintf (vect_dump
, "cost model: "
2598 "prologue peel iters set to vf/2.");
2600 /* If peeling for alignment is unknown, loop bound of main loop becomes
2602 peel_iters_epilogue
= vf
/2;
2603 if (vect_print_dump_info (REPORT_COST
))
2604 fprintf (vect_dump
, "cost model: "
2605 "epilogue peel iters set to vf/2 because "
2606 "peeling for alignment is unknown .");
2608 /* If peeled iterations are unknown, count a taken branch and a not taken
2609 branch per peeled loop. Even if scalar loop iterations are known,
2610 vector iterations are not known since peeled prologue iterations are
2611 not known. Hence guards remain the same. */
2612 (void) add_stmt_cost (target_cost_data
, 2, cond_branch_taken
,
2613 NULL
, 0, vect_prologue
);
2614 (void) add_stmt_cost (target_cost_data
, 2, cond_branch_not_taken
,
2615 NULL
, 0, vect_prologue
);
2616 /* FORNOW: Don't attempt to pass individual scalar instructions to
2617 the model; just assume linear cost for scalar iterations. */
2618 (void) add_stmt_cost (target_cost_data
,
2619 peel_iters_prologue
* scalar_single_iter_cost
,
2620 scalar_stmt
, NULL
, 0, vect_prologue
);
2621 (void) add_stmt_cost (target_cost_data
,
2622 peel_iters_epilogue
* scalar_single_iter_cost
,
2623 scalar_stmt
, NULL
, 0, vect_epilogue
);
2627 stmt_vector_for_cost prologue_cost_vec
, epilogue_cost_vec
;
2628 stmt_info_for_cost
*si
;
2630 void *data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2632 prologue_cost_vec
= VEC_alloc (stmt_info_for_cost
, heap
, 2);
2633 epilogue_cost_vec
= VEC_alloc (stmt_info_for_cost
, heap
, 2);
2634 peel_iters_prologue
= npeel
;
2636 (void) vect_get_known_peeling_cost (loop_vinfo
, peel_iters_prologue
,
2637 &peel_iters_epilogue
,
2638 scalar_single_iter_cost
,
2640 &epilogue_cost_vec
);
2642 FOR_EACH_VEC_ELT (stmt_info_for_cost
, prologue_cost_vec
, j
, si
)
2644 struct _stmt_vec_info
*stmt_info
2645 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
2646 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
2647 si
->misalign
, vect_prologue
);
2650 FOR_EACH_VEC_ELT (stmt_info_for_cost
, epilogue_cost_vec
, j
, si
)
2652 struct _stmt_vec_info
*stmt_info
2653 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
2654 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
2655 si
->misalign
, vect_epilogue
);
2658 VEC_free (stmt_info_for_cost
, heap
, prologue_cost_vec
);
2659 VEC_free (stmt_info_for_cost
, heap
, epilogue_cost_vec
);
2662 /* FORNOW: The scalar outside cost is incremented in one of the
2665 1. The vectorizer checks for alignment and aliasing and generates
2666 a condition that allows dynamic vectorization. A cost model
2667 check is ANDED with the versioning condition. Hence scalar code
2668 path now has the added cost of the versioning check.
2670 if (cost > th & versioning_check)
2673 Hence run-time scalar is incremented by not-taken branch cost.
2675 2. The vectorizer then checks if a prologue is required. If the
2676 cost model check was not done before during versioning, it has to
2677 be done before the prologue check.
2680 prologue = scalar_iters
2685 if (prologue == num_iters)
2688 Hence the run-time scalar cost is incremented by a taken branch,
2689 plus a not-taken branch, plus a taken branch cost.
2691 3. The vectorizer then checks if an epilogue is required. If the
2692 cost model check was not done before during prologue check, it
2693 has to be done with the epilogue check.
2699 if (prologue == num_iters)
2702 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
2705 Hence the run-time scalar cost should be incremented by 2 taken
2708 TODO: The back end may reorder the BBS's differently and reverse
2709 conditions/branch directions. Change the estimates below to
2710 something more reasonable. */
2712 /* If the number of iterations is known and we do not do versioning, we can
2713 decide whether to vectorize at compile time. Hence the scalar version
2714 do not carry cost model guard costs. */
2715 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
2716 || LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2717 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2719 /* Cost model check occurs at versioning. */
2720 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2721 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2722 scalar_outside_cost
+= vect_get_stmt_cost (cond_branch_not_taken
);
2725 /* Cost model check occurs at prologue generation. */
2726 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
) < 0)
2727 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
)
2728 + vect_get_stmt_cost (cond_branch_not_taken
);
2729 /* Cost model check occurs at epilogue generation. */
2731 scalar_outside_cost
+= 2 * vect_get_stmt_cost (cond_branch_taken
);
2735 /* Complete the target-specific cost calculations. */
2736 finish_cost (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
), &vec_prologue_cost
,
2737 &vec_inside_cost
, &vec_epilogue_cost
);
2739 vec_outside_cost
= (int)(vec_prologue_cost
+ vec_epilogue_cost
);
2741 /* Calculate number of iterations required to make the vector version
2742 profitable, relative to the loop bodies only. The following condition
2744 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
2746 SIC = scalar iteration cost, VIC = vector iteration cost,
2747 VOC = vector outside cost, VF = vectorization factor,
2748 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
2749 SOC = scalar outside cost for run time cost model check. */
2751 if ((scalar_single_iter_cost
* vf
) > (int) vec_inside_cost
)
2753 if (vec_outside_cost
<= 0)
2754 min_profitable_iters
= 1;
2757 min_profitable_iters
= ((vec_outside_cost
- scalar_outside_cost
) * vf
2758 - vec_inside_cost
* peel_iters_prologue
2759 - vec_inside_cost
* peel_iters_epilogue
)
2760 / ((scalar_single_iter_cost
* vf
)
2763 if ((scalar_single_iter_cost
* vf
* min_profitable_iters
)
2764 <= (((int) vec_inside_cost
* min_profitable_iters
)
2765 + (((int) vec_outside_cost
- scalar_outside_cost
) * vf
)))
2766 min_profitable_iters
++;
2769 /* vector version will never be profitable. */
2772 if (vect_print_dump_info (REPORT_COST
))
2773 fprintf (vect_dump
, "cost model: the vector iteration cost = %d "
2774 "divided by the scalar iteration cost = %d "
2775 "is greater or equal to the vectorization factor = %d.",
2776 vec_inside_cost
, scalar_single_iter_cost
, vf
);
2780 if (vect_print_dump_info (REPORT_COST
))
2782 fprintf (vect_dump
, "Cost model analysis: \n");
2783 fprintf (vect_dump
, " Vector inside of loop cost: %d\n",
2785 fprintf (vect_dump
, " Vector prologue cost: %d\n",
2787 fprintf (vect_dump
, " Vector epilogue cost: %d\n",
2789 fprintf (vect_dump
, " Scalar iteration cost: %d\n",
2790 scalar_single_iter_cost
);
2791 fprintf (vect_dump
, " Scalar outside cost: %d\n", scalar_outside_cost
);
2792 fprintf (vect_dump
, " prologue iterations: %d\n",
2793 peel_iters_prologue
);
2794 fprintf (vect_dump
, " epilogue iterations: %d\n",
2795 peel_iters_epilogue
);
2796 fprintf (vect_dump
, " Calculated minimum iters for profitability: %d\n",
2797 min_profitable_iters
);
2800 min_profitable_iters
=
2801 min_profitable_iters
< vf
? vf
: min_profitable_iters
;
2803 /* Because the condition we create is:
2804 if (niters <= min_profitable_iters)
2805 then skip the vectorized loop. */
2806 min_profitable_iters
--;
2808 if (vect_print_dump_info (REPORT_COST
))
2809 fprintf (vect_dump
, " Profitability threshold = %d\n",
2810 min_profitable_iters
);
2812 return min_profitable_iters
;
2816 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
2817 functions. Design better to avoid maintenance issues. */
2819 /* Function vect_model_reduction_cost.
2821 Models cost for a reduction operation, including the vector ops
2822 generated within the strip-mine loop, the initial definition before
2823 the loop, and the epilogue code that must be generated. */
2826 vect_model_reduction_cost (stmt_vec_info stmt_info
, enum tree_code reduc_code
,
2829 int prologue_cost
= 0, epilogue_cost
= 0;
2830 enum tree_code code
;
2833 gimple stmt
, orig_stmt
;
2835 enum machine_mode mode
;
2836 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
2837 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2838 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2840 /* Cost of reduction op inside loop. */
2841 unsigned inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
2842 stmt_info
, 0, vect_body
);
2843 stmt
= STMT_VINFO_STMT (stmt_info
);
2845 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
2847 case GIMPLE_SINGLE_RHS
:
2848 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
)) == ternary_op
);
2849 reduction_op
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
2851 case GIMPLE_UNARY_RHS
:
2852 reduction_op
= gimple_assign_rhs1 (stmt
);
2854 case GIMPLE_BINARY_RHS
:
2855 reduction_op
= gimple_assign_rhs2 (stmt
);
2857 case GIMPLE_TERNARY_RHS
:
2858 reduction_op
= gimple_assign_rhs3 (stmt
);
2864 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
2867 if (vect_print_dump_info (REPORT_COST
))
2869 fprintf (vect_dump
, "unsupported data-type ");
2870 print_generic_expr (vect_dump
, TREE_TYPE (reduction_op
), TDF_SLIM
);
2875 mode
= TYPE_MODE (vectype
);
2876 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
2879 orig_stmt
= STMT_VINFO_STMT (stmt_info
);
2881 code
= gimple_assign_rhs_code (orig_stmt
);
2883 /* Add in cost for initial definition. */
2884 prologue_cost
+= add_stmt_cost (target_cost_data
, 1, scalar_to_vec
,
2885 stmt_info
, 0, vect_prologue
);
2887 /* Determine cost of epilogue code.
2889 We have a reduction operator that will reduce the vector in one statement.
2890 Also requires scalar extract. */
2892 if (!nested_in_vect_loop_p (loop
, orig_stmt
))
2894 if (reduc_code
!= ERROR_MARK
)
2896 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1, vector_stmt
,
2897 stmt_info
, 0, vect_epilogue
);
2898 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1, vec_to_scalar
,
2899 stmt_info
, 0, vect_epilogue
);
2903 int vec_size_in_bits
= tree_low_cst (TYPE_SIZE (vectype
), 1);
2905 TYPE_SIZE (TREE_TYPE (gimple_assign_lhs (orig_stmt
)));
2906 int element_bitsize
= tree_low_cst (bitsize
, 1);
2907 int nelements
= vec_size_in_bits
/ element_bitsize
;
2909 optab
= optab_for_tree_code (code
, vectype
, optab_default
);
2911 /* We have a whole vector shift available. */
2912 if (VECTOR_MODE_P (mode
)
2913 && optab_handler (optab
, mode
) != CODE_FOR_nothing
2914 && optab_handler (vec_shr_optab
, mode
) != CODE_FOR_nothing
)
2916 /* Final reduction via vector shifts and the reduction operator.
2917 Also requires scalar extract. */
2918 epilogue_cost
+= add_stmt_cost (target_cost_data
,
2919 exact_log2 (nelements
) * 2,
2920 vector_stmt
, stmt_info
, 0,
2922 epilogue_cost
+= add_stmt_cost (target_cost_data
, 1,
2923 vec_to_scalar
, stmt_info
, 0,
2927 /* Use extracts and reduction op for final reduction. For N
2928 elements, we have N extracts and N-1 reduction ops. */
2929 epilogue_cost
+= add_stmt_cost (target_cost_data
,
2930 nelements
+ nelements
- 1,
2931 vector_stmt
, stmt_info
, 0,
2936 if (vect_print_dump_info (REPORT_COST
))
2937 fprintf (vect_dump
, "vect_model_reduction_cost: inside_cost = %d, "
2938 "prologue_cost = %d, epilogue_cost = %d .", inside_cost
,
2939 prologue_cost
, epilogue_cost
);
2945 /* Function vect_model_induction_cost.
2947 Models cost for induction operations. */
2950 vect_model_induction_cost (stmt_vec_info stmt_info
, int ncopies
)
2952 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
2953 void *target_cost_data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
2954 unsigned inside_cost
, prologue_cost
;
2956 /* loop cost for vec_loop. */
2957 inside_cost
= add_stmt_cost (target_cost_data
, ncopies
, vector_stmt
,
2958 stmt_info
, 0, vect_body
);
2960 /* prologue cost for vec_init and vec_step. */
2961 prologue_cost
= add_stmt_cost (target_cost_data
, 2, scalar_to_vec
,
2962 stmt_info
, 0, vect_prologue
);
2964 if (vect_print_dump_info (REPORT_COST
))
2965 fprintf (vect_dump
, "vect_model_induction_cost: inside_cost = %d, "
2966 "prologue_cost = %d .", inside_cost
, prologue_cost
);
2970 /* Function get_initial_def_for_induction
2973 STMT - a stmt that performs an induction operation in the loop.
2974 IV_PHI - the initial value of the induction variable
2977 Return a vector variable, initialized with the first VF values of
2978 the induction variable. E.g., for an iv with IV_PHI='X' and
2979 evolution S, for a vector of 4 units, we want to return:
2980 [X, X + S, X + 2*S, X + 3*S]. */
2983 get_initial_def_for_induction (gimple iv_phi
)
2985 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (iv_phi
);
2986 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
2987 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2991 edge pe
= loop_preheader_edge (loop
);
2992 struct loop
*iv_loop
;
2994 tree vec
, vec_init
, vec_step
, t
;
2998 gimple init_stmt
, induction_phi
, new_stmt
;
2999 tree induc_def
, vec_def
, vec_dest
;
3000 tree init_expr
, step_expr
;
3001 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
3006 stmt_vec_info phi_info
= vinfo_for_stmt (iv_phi
);
3007 bool nested_in_vect_loop
= false;
3008 gimple_seq stmts
= NULL
;
3009 imm_use_iterator imm_iter
;
3010 use_operand_p use_p
;
3014 gimple_stmt_iterator si
;
3015 basic_block bb
= gimple_bb (iv_phi
);
3019 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
3020 if (nested_in_vect_loop_p (loop
, iv_phi
))
3022 nested_in_vect_loop
= true;
3023 iv_loop
= loop
->inner
;
3027 gcc_assert (iv_loop
== (gimple_bb (iv_phi
))->loop_father
);
3029 latch_e
= loop_latch_edge (iv_loop
);
3030 loop_arg
= PHI_ARG_DEF_FROM_EDGE (iv_phi
, latch_e
);
3032 access_fn
= analyze_scalar_evolution (iv_loop
, PHI_RESULT (iv_phi
));
3033 gcc_assert (access_fn
);
3034 STRIP_NOPS (access_fn
);
3035 ok
= vect_is_simple_iv_evolution (iv_loop
->num
, access_fn
,
3036 &init_expr
, &step_expr
);
3038 pe
= loop_preheader_edge (iv_loop
);
3040 scalar_type
= TREE_TYPE (init_expr
);
3041 vectype
= get_vectype_for_scalar_type (scalar_type
);
3042 resvectype
= get_vectype_for_scalar_type (TREE_TYPE (PHI_RESULT (iv_phi
)));
3043 gcc_assert (vectype
);
3044 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3045 ncopies
= vf
/ nunits
;
3047 gcc_assert (phi_info
);
3048 gcc_assert (ncopies
>= 1);
3050 /* Find the first insertion point in the BB. */
3051 si
= gsi_after_labels (bb
);
3053 /* Create the vector that holds the initial_value of the induction. */
3054 if (nested_in_vect_loop
)
3056 /* iv_loop is nested in the loop to be vectorized. init_expr had already
3057 been created during vectorization of previous stmts. We obtain it
3058 from the STMT_VINFO_VEC_STMT of the defining stmt. */
3059 tree iv_def
= PHI_ARG_DEF_FROM_EDGE (iv_phi
,
3060 loop_preheader_edge (iv_loop
));
3061 vec_init
= vect_get_vec_def_for_operand (iv_def
, iv_phi
, NULL
);
3065 VEC(constructor_elt
,gc
) *v
;
3067 /* iv_loop is the loop to be vectorized. Create:
3068 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
3069 new_var
= vect_get_new_vect_var (scalar_type
, vect_scalar_var
, "var_");
3070 new_name
= force_gimple_operand (init_expr
, &stmts
, false, new_var
);
3073 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
3074 gcc_assert (!new_bb
);
3077 v
= VEC_alloc (constructor_elt
, gc
, nunits
);
3078 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
3079 for (i
= 1; i
< nunits
; i
++)
3081 /* Create: new_name_i = new_name + step_expr */
3082 enum tree_code code
= POINTER_TYPE_P (scalar_type
)
3083 ? POINTER_PLUS_EXPR
: PLUS_EXPR
;
3084 init_stmt
= gimple_build_assign_with_ops (code
, new_var
,
3085 new_name
, step_expr
);
3086 new_name
= make_ssa_name (new_var
, init_stmt
);
3087 gimple_assign_set_lhs (init_stmt
, new_name
);
3089 new_bb
= gsi_insert_on_edge_immediate (pe
, init_stmt
);
3090 gcc_assert (!new_bb
);
3092 if (vect_print_dump_info (REPORT_DETAILS
))
3094 fprintf (vect_dump
, "created new init_stmt: ");
3095 print_gimple_stmt (vect_dump
, init_stmt
, 0, TDF_SLIM
);
3097 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, new_name
);
3099 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
3100 vec
= build_constructor (vectype
, v
);
3101 vec_init
= vect_init_vector (iv_phi
, vec
, vectype
, NULL
);
3105 /* Create the vector that holds the step of the induction. */
3106 if (nested_in_vect_loop
)
3107 /* iv_loop is nested in the loop to be vectorized. Generate:
3108 vec_step = [S, S, S, S] */
3109 new_name
= step_expr
;
3112 /* iv_loop is the loop to be vectorized. Generate:
3113 vec_step = [VF*S, VF*S, VF*S, VF*S] */
3114 expr
= build_int_cst (TREE_TYPE (step_expr
), vf
);
3115 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
3119 t
= unshare_expr (new_name
);
3120 gcc_assert (CONSTANT_CLASS_P (new_name
));
3121 stepvectype
= get_vectype_for_scalar_type (TREE_TYPE (new_name
));
3122 gcc_assert (stepvectype
);
3123 vec
= build_vector_from_val (stepvectype
, t
);
3124 vec_step
= vect_init_vector (iv_phi
, vec
, stepvectype
, NULL
);
3127 /* Create the following def-use cycle:
3132 vec_iv = PHI <vec_init, vec_loop>
3136 vec_loop = vec_iv + vec_step; */
3138 /* Create the induction-phi that defines the induction-operand. */
3139 vec_dest
= vect_get_new_vect_var (vectype
, vect_simple_var
, "vec_iv_");
3140 induction_phi
= create_phi_node (vec_dest
, iv_loop
->header
);
3141 set_vinfo_for_stmt (induction_phi
,
3142 new_stmt_vec_info (induction_phi
, loop_vinfo
, NULL
));
3143 induc_def
= PHI_RESULT (induction_phi
);
3145 /* Create the iv update inside the loop */
3146 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, vec_dest
,
3147 induc_def
, vec_step
);
3148 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
3149 gimple_assign_set_lhs (new_stmt
, vec_def
);
3150 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3151 set_vinfo_for_stmt (new_stmt
, new_stmt_vec_info (new_stmt
, loop_vinfo
,
3154 /* Set the arguments of the phi node: */
3155 add_phi_arg (induction_phi
, vec_init
, pe
, UNKNOWN_LOCATION
);
3156 add_phi_arg (induction_phi
, vec_def
, loop_latch_edge (iv_loop
),
3160 /* In case that vectorization factor (VF) is bigger than the number
3161 of elements that we can fit in a vectype (nunits), we have to generate
3162 more than one vector stmt - i.e - we need to "unroll" the
3163 vector stmt by a factor VF/nunits. For more details see documentation
3164 in vectorizable_operation. */
3168 stmt_vec_info prev_stmt_vinfo
;
3169 /* FORNOW. This restriction should be relaxed. */
3170 gcc_assert (!nested_in_vect_loop
);
3172 /* Create the vector that holds the step of the induction. */
3173 expr
= build_int_cst (TREE_TYPE (step_expr
), nunits
);
3174 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
3176 t
= unshare_expr (new_name
);
3177 gcc_assert (CONSTANT_CLASS_P (new_name
));
3178 vec
= build_vector_from_val (stepvectype
, t
);
3179 vec_step
= vect_init_vector (iv_phi
, vec
, stepvectype
, NULL
);
3181 vec_def
= induc_def
;
3182 prev_stmt_vinfo
= vinfo_for_stmt (induction_phi
);
3183 for (i
= 1; i
< ncopies
; i
++)
3185 /* vec_i = vec_prev + vec_step */
3186 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, vec_dest
,
3188 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
3189 gimple_assign_set_lhs (new_stmt
, vec_def
);
3191 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3192 if (!useless_type_conversion_p (resvectype
, vectype
))
3194 new_stmt
= gimple_build_assign_with_ops
3196 vect_get_new_vect_var (resvectype
, vect_simple_var
,
3198 build1 (VIEW_CONVERT_EXPR
, resvectype
,
3199 gimple_assign_lhs (new_stmt
)), NULL_TREE
);
3200 gimple_assign_set_lhs (new_stmt
,
3202 (gimple_assign_lhs (new_stmt
), new_stmt
));
3203 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3205 set_vinfo_for_stmt (new_stmt
,
3206 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
3207 STMT_VINFO_RELATED_STMT (prev_stmt_vinfo
) = new_stmt
;
3208 prev_stmt_vinfo
= vinfo_for_stmt (new_stmt
);
3212 if (nested_in_vect_loop
)
3214 /* Find the loop-closed exit-phi of the induction, and record
3215 the final vector of induction results: */
3217 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
3219 if (!flow_bb_inside_loop_p (iv_loop
, gimple_bb (USE_STMT (use_p
))))
3221 exit_phi
= USE_STMT (use_p
);
3227 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (exit_phi
);
3228 /* FORNOW. Currently not supporting the case that an inner-loop induction
3229 is not used in the outer-loop (i.e. only outside the outer-loop). */
3230 gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo
)
3231 && !STMT_VINFO_LIVE_P (stmt_vinfo
));
3233 STMT_VINFO_VEC_STMT (stmt_vinfo
) = new_stmt
;
3234 if (vect_print_dump_info (REPORT_DETAILS
))
3236 fprintf (vect_dump
, "vector of inductions after inner-loop:");
3237 print_gimple_stmt (vect_dump
, new_stmt
, 0, TDF_SLIM
);
3243 if (vect_print_dump_info (REPORT_DETAILS
))
3245 fprintf (vect_dump
, "transform induction: created def-use cycle: ");
3246 print_gimple_stmt (vect_dump
, induction_phi
, 0, TDF_SLIM
);
3247 fprintf (vect_dump
, "\n");
3248 print_gimple_stmt (vect_dump
, SSA_NAME_DEF_STMT (vec_def
), 0, TDF_SLIM
);
3251 STMT_VINFO_VEC_STMT (phi_info
) = induction_phi
;
3252 if (!useless_type_conversion_p (resvectype
, vectype
))
3254 new_stmt
= gimple_build_assign_with_ops
3256 vect_get_new_vect_var (resvectype
, vect_simple_var
, "vec_iv_"),
3257 build1 (VIEW_CONVERT_EXPR
, resvectype
, induc_def
), NULL_TREE
);
3258 induc_def
= make_ssa_name (gimple_assign_lhs (new_stmt
), new_stmt
);
3259 gimple_assign_set_lhs (new_stmt
, induc_def
);
3260 si
= gsi_start_bb (bb
);
3261 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
3262 set_vinfo_for_stmt (new_stmt
,
3263 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
3264 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_stmt
))
3265 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (induction_phi
));
3272 /* Function get_initial_def_for_reduction
3275 STMT - a stmt that performs a reduction operation in the loop.
3276 INIT_VAL - the initial value of the reduction variable
3279 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
3280 of the reduction (used for adjusting the epilog - see below).
3281 Return a vector variable, initialized according to the operation that STMT
3282 performs. This vector will be used as the initial value of the
3283 vector of partial results.
3285 Option1 (adjust in epilog): Initialize the vector as follows:
3286 add/bit or/xor: [0,0,...,0,0]
3287 mult/bit and: [1,1,...,1,1]
3288 min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
3289 and when necessary (e.g. add/mult case) let the caller know
3290 that it needs to adjust the result by init_val.
3292 Option2: Initialize the vector as follows:
3293 add/bit or/xor: [init_val,0,0,...,0]
3294 mult/bit and: [init_val,1,1,...,1]
3295 min/max/cond_expr: [init_val,init_val,...,init_val]
3296 and no adjustments are needed.
3298 For example, for the following code:
3304 STMT is 's = s + a[i]', and the reduction variable is 's'.
3305 For a vector of 4 units, we want to return either [0,0,0,init_val],
3306 or [0,0,0,0] and let the caller know that it needs to adjust
3307 the result at the end by 'init_val'.
3309 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
3310 initialization vector is simpler (same element in all entries), if
3311 ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
3313 A cost model should help decide between these two schemes. */
3316 get_initial_def_for_reduction (gimple stmt
, tree init_val
,
3317 tree
*adjustment_def
)
3319 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
3320 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
3321 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3322 tree scalar_type
= TREE_TYPE (init_val
);
3323 tree vectype
= get_vectype_for_scalar_type (scalar_type
);
3325 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3330 bool nested_in_vect_loop
= false;
3332 REAL_VALUE_TYPE real_init_val
= dconst0
;
3333 int int_init_val
= 0;
3334 gimple def_stmt
= NULL
;
3336 gcc_assert (vectype
);
3337 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3339 gcc_assert (POINTER_TYPE_P (scalar_type
) || INTEGRAL_TYPE_P (scalar_type
)
3340 || SCALAR_FLOAT_TYPE_P (scalar_type
));
3342 if (nested_in_vect_loop_p (loop
, stmt
))
3343 nested_in_vect_loop
= true;
3345 gcc_assert (loop
== (gimple_bb (stmt
))->loop_father
);
3347 /* In case of double reduction we only create a vector variable to be put
3348 in the reduction phi node. The actual statement creation is done in
3349 vect_create_epilog_for_reduction. */
3350 if (adjustment_def
&& nested_in_vect_loop
3351 && TREE_CODE (init_val
) == SSA_NAME
3352 && (def_stmt
= SSA_NAME_DEF_STMT (init_val
))
3353 && gimple_code (def_stmt
) == GIMPLE_PHI
3354 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
3355 && vinfo_for_stmt (def_stmt
)
3356 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
3357 == vect_double_reduction_def
)
3359 *adjustment_def
= NULL
;
3360 return vect_create_destination_var (init_val
, vectype
);
3363 if (TREE_CONSTANT (init_val
))
3365 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
3366 init_value
= build_real (scalar_type
, TREE_REAL_CST (init_val
));
3368 init_value
= build_int_cst (scalar_type
, TREE_INT_CST_LOW (init_val
));
3371 init_value
= init_val
;
3375 case WIDEN_SUM_EXPR
:
3383 /* ADJUSMENT_DEF is NULL when called from
3384 vect_create_epilog_for_reduction to vectorize double reduction. */
3387 if (nested_in_vect_loop
)
3388 *adjustment_def
= vect_get_vec_def_for_operand (init_val
, stmt
,
3391 *adjustment_def
= init_val
;
3394 if (code
== MULT_EXPR
)
3396 real_init_val
= dconst1
;
3400 if (code
== BIT_AND_EXPR
)
3403 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
3404 def_for_init
= build_real (scalar_type
, real_init_val
);
3406 def_for_init
= build_int_cst (scalar_type
, int_init_val
);
3408 /* Create a vector of '0' or '1' except the first element. */
3409 elts
= XALLOCAVEC (tree
, nunits
);
3410 for (i
= nunits
- 2; i
>= 0; --i
)
3411 elts
[i
+ 1] = def_for_init
;
3413 /* Option1: the first element is '0' or '1' as well. */
3416 elts
[0] = def_for_init
;
3417 init_def
= build_vector (vectype
, elts
);
3421 /* Option2: the first element is INIT_VAL. */
3423 if (TREE_CONSTANT (init_val
))
3424 init_def
= build_vector (vectype
, elts
);
3427 VEC(constructor_elt
,gc
) *v
;
3428 v
= VEC_alloc (constructor_elt
, gc
, nunits
);
3429 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, init_val
);
3430 for (i
= 1; i
< nunits
; ++i
)
3431 CONSTRUCTOR_APPEND_ELT (v
, NULL_TREE
, elts
[i
]);
3432 init_def
= build_constructor (vectype
, v
);
3442 *adjustment_def
= NULL_TREE
;
3443 init_def
= vect_get_vec_def_for_operand (init_val
, stmt
, NULL
);
3447 init_def
= build_vector_from_val (vectype
, init_value
);
3458 /* Function vect_create_epilog_for_reduction
3460 Create code at the loop-epilog to finalize the result of a reduction
3463 VECT_DEFS is list of vector of partial results, i.e., the lhs's of vector
3464 reduction statements.
3465 STMT is the scalar reduction stmt that is being vectorized.
3466 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
3467 number of elements that we can fit in a vectype (nunits). In this case
3468 we have to generate more than one vector stmt - i.e - we need to "unroll"
3469 the vector stmt by a factor VF/nunits. For more details see documentation
3470 in vectorizable_operation.
3471 REDUC_CODE is the tree-code for the epilog reduction.
3472 REDUCTION_PHIS is a list of the phi-nodes that carry the reduction
3474 REDUC_INDEX is the index of the operand in the right hand side of the
3475 statement that is defined by REDUCTION_PHI.
3476 DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
3477 SLP_NODE is an SLP node containing a group of reduction statements. The
3478 first one in this group is STMT.
3481 1. Creates the reduction def-use cycles: sets the arguments for
3483 The loop-entry argument is the vectorized initial-value of the reduction.
3484 The loop-latch argument is taken from VECT_DEFS - the vector of partial
3486 2. "Reduces" each vector of partial results VECT_DEFS into a single result,
3487 by applying the operation specified by REDUC_CODE if available, or by
3488 other means (whole-vector shifts or a scalar loop).
3489 The function also creates a new phi node at the loop exit to preserve
3490 loop-closed form, as illustrated below.
3492 The flow at the entry to this function:
3495 vec_def = phi <null, null> # REDUCTION_PHI
3496 VECT_DEF = vector_stmt # vectorized form of STMT
3497 s_loop = scalar_stmt # (scalar) STMT
3499 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3503 The above is transformed by this function into:
3506 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3507 VECT_DEF = vector_stmt # vectorized form of STMT
3508 s_loop = scalar_stmt # (scalar) STMT
3510 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3511 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3512 v_out2 = reduce <v_out1>
3513 s_out3 = extract_field <v_out2, 0>
3514 s_out4 = adjust_result <s_out3>
3520 vect_create_epilog_for_reduction (VEC (tree
, heap
) *vect_defs
, gimple stmt
,
3521 int ncopies
, enum tree_code reduc_code
,
3522 VEC (gimple
, heap
) *reduction_phis
,
3523 int reduc_index
, bool double_reduc
,
3526 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3527 stmt_vec_info prev_phi_info
;
3529 enum machine_mode mode
;
3530 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3531 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
), *outer_loop
= NULL
;
3532 basic_block exit_bb
;
3535 gimple new_phi
= NULL
, phi
;
3536 gimple_stmt_iterator exit_gsi
;
3538 tree new_temp
= NULL_TREE
, new_dest
, new_name
, new_scalar_dest
;
3539 gimple epilog_stmt
= NULL
;
3540 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3542 tree bitsize
, bitpos
;
3543 tree adjustment_def
= NULL
;
3544 tree vec_initial_def
= NULL
;
3545 tree reduction_op
, expr
, def
;
3546 tree orig_name
, scalar_result
;
3547 imm_use_iterator imm_iter
, phi_imm_iter
;
3548 use_operand_p use_p
, phi_use_p
;
3549 bool extract_scalar_result
= false;
3550 gimple use_stmt
, orig_stmt
, reduction_phi
= NULL
;
3551 bool nested_in_vect_loop
= false;
3552 VEC (gimple
, heap
) *new_phis
= NULL
;
3553 VEC (gimple
, heap
) *inner_phis
= NULL
;
3554 enum vect_def_type dt
= vect_unknown_def_type
;
3556 VEC (tree
, heap
) *scalar_results
= NULL
;
3557 unsigned int group_size
= 1, k
, ratio
;
3558 VEC (tree
, heap
) *vec_initial_defs
= NULL
;
3559 VEC (gimple
, heap
) *phis
;
3560 bool slp_reduc
= false;
3561 tree new_phi_result
;
3562 gimple inner_phi
= NULL
;
3565 group_size
= VEC_length (gimple
, SLP_TREE_SCALAR_STMTS (slp_node
));
3567 if (nested_in_vect_loop_p (loop
, stmt
))
3571 nested_in_vect_loop
= true;
3572 gcc_assert (!slp_node
);
3575 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3577 case GIMPLE_SINGLE_RHS
:
3578 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
))
3580 reduction_op
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), reduc_index
);
3582 case GIMPLE_UNARY_RHS
:
3583 reduction_op
= gimple_assign_rhs1 (stmt
);
3585 case GIMPLE_BINARY_RHS
:
3586 reduction_op
= reduc_index
?
3587 gimple_assign_rhs2 (stmt
) : gimple_assign_rhs1 (stmt
);
3589 case GIMPLE_TERNARY_RHS
:
3590 reduction_op
= gimple_op (stmt
, reduc_index
+ 1);
3596 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
3597 gcc_assert (vectype
);
3598 mode
= TYPE_MODE (vectype
);
3600 /* 1. Create the reduction def-use cycle:
3601 Set the arguments of REDUCTION_PHIS, i.e., transform
3604 vec_def = phi <null, null> # REDUCTION_PHI
3605 VECT_DEF = vector_stmt # vectorized form of STMT
3611 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3612 VECT_DEF = vector_stmt # vectorized form of STMT
3615 (in case of SLP, do it for all the phis). */
3617 /* Get the loop-entry arguments. */
3619 vect_get_vec_defs (reduction_op
, NULL_TREE
, stmt
, &vec_initial_defs
,
3620 NULL
, slp_node
, reduc_index
);
3623 vec_initial_defs
= VEC_alloc (tree
, heap
, 1);
3624 /* For the case of reduction, vect_get_vec_def_for_operand returns
3625 the scalar def before the loop, that defines the initial value
3626 of the reduction variable. */
3627 vec_initial_def
= vect_get_vec_def_for_operand (reduction_op
, stmt
,
3629 VEC_quick_push (tree
, vec_initial_defs
, vec_initial_def
);
3632 /* Set phi nodes arguments. */
3633 FOR_EACH_VEC_ELT (gimple
, reduction_phis
, i
, phi
)
3635 tree vec_init_def
= VEC_index (tree
, vec_initial_defs
, i
);
3636 tree def
= VEC_index (tree
, vect_defs
, i
);
3637 for (j
= 0; j
< ncopies
; j
++)
3639 /* Set the loop-entry arg of the reduction-phi. */
3640 add_phi_arg (phi
, vec_init_def
, loop_preheader_edge (loop
),
3643 /* Set the loop-latch arg for the reduction-phi. */
3645 def
= vect_get_vec_def_for_stmt_copy (vect_unknown_def_type
, def
);
3647 add_phi_arg (phi
, def
, loop_latch_edge (loop
), UNKNOWN_LOCATION
);
3649 if (vect_print_dump_info (REPORT_DETAILS
))
3651 fprintf (vect_dump
, "transform reduction: created def-use"
3653 print_gimple_stmt (vect_dump
, phi
, 0, TDF_SLIM
);
3654 fprintf (vect_dump
, "\n");
3655 print_gimple_stmt (vect_dump
, SSA_NAME_DEF_STMT (def
), 0,
3659 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
3663 VEC_free (tree
, heap
, vec_initial_defs
);
3665 /* 2. Create epilog code.
3666 The reduction epilog code operates across the elements of the vector
3667 of partial results computed by the vectorized loop.
3668 The reduction epilog code consists of:
3670 step 1: compute the scalar result in a vector (v_out2)
3671 step 2: extract the scalar result (s_out3) from the vector (v_out2)
3672 step 3: adjust the scalar result (s_out3) if needed.
3674 Step 1 can be accomplished using one the following three schemes:
3675 (scheme 1) using reduc_code, if available.
3676 (scheme 2) using whole-vector shifts, if available.
3677 (scheme 3) using a scalar loop. In this case steps 1+2 above are
3680 The overall epilog code looks like this:
3682 s_out0 = phi <s_loop> # original EXIT_PHI
3683 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3684 v_out2 = reduce <v_out1> # step 1
3685 s_out3 = extract_field <v_out2, 0> # step 2
3686 s_out4 = adjust_result <s_out3> # step 3
3688 (step 3 is optional, and steps 1 and 2 may be combined).
3689 Lastly, the uses of s_out0 are replaced by s_out4. */
3692 /* 2.1 Create new loop-exit-phis to preserve loop-closed form:
3693 v_out1 = phi <VECT_DEF>
3694 Store them in NEW_PHIS. */
3696 exit_bb
= single_exit (loop
)->dest
;
3697 prev_phi_info
= NULL
;
3698 new_phis
= VEC_alloc (gimple
, heap
, VEC_length (tree
, vect_defs
));
3699 FOR_EACH_VEC_ELT (tree
, vect_defs
, i
, def
)
3701 for (j
= 0; j
< ncopies
; j
++)
3703 phi
= create_phi_node (SSA_NAME_VAR (def
), exit_bb
);
3704 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, loop_vinfo
, NULL
));
3706 VEC_quick_push (gimple
, new_phis
, phi
);
3709 def
= vect_get_vec_def_for_stmt_copy (dt
, def
);
3710 STMT_VINFO_RELATED_STMT (prev_phi_info
) = phi
;
3713 SET_PHI_ARG_DEF (phi
, single_exit (loop
)->dest_idx
, def
);
3714 prev_phi_info
= vinfo_for_stmt (phi
);
3718 /* The epilogue is created for the outer-loop, i.e., for the loop being
3719 vectorized. Create exit phis for the outer loop. */
3723 exit_bb
= single_exit (loop
)->dest
;
3724 inner_phis
= VEC_alloc (gimple
, heap
, VEC_length (tree
, vect_defs
));
3725 FOR_EACH_VEC_ELT (gimple
, new_phis
, i
, phi
)
3727 gimple outer_phi
= create_phi_node (SSA_NAME_VAR (PHI_RESULT (phi
)),
3729 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
3731 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
3733 VEC_quick_push (gimple
, inner_phis
, phi
);
3734 VEC_replace (gimple
, new_phis
, i
, outer_phi
);
3735 prev_phi_info
= vinfo_for_stmt (outer_phi
);
3736 while (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
)))
3738 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
3739 outer_phi
= create_phi_node (SSA_NAME_VAR (PHI_RESULT (phi
)),
3741 SET_PHI_ARG_DEF (outer_phi
, single_exit (loop
)->dest_idx
,
3743 set_vinfo_for_stmt (outer_phi
, new_stmt_vec_info (outer_phi
,
3745 STMT_VINFO_RELATED_STMT (prev_phi_info
) = outer_phi
;
3746 prev_phi_info
= vinfo_for_stmt (outer_phi
);
3751 exit_gsi
= gsi_after_labels (exit_bb
);
3753 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
3754 (i.e. when reduc_code is not available) and in the final adjustment
3755 code (if needed). Also get the original scalar reduction variable as
3756 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
3757 represents a reduction pattern), the tree-code and scalar-def are
3758 taken from the original stmt that the pattern-stmt (STMT) replaces.
3759 Otherwise (it is a regular reduction) - the tree-code and scalar-def
3760 are taken from STMT. */
3762 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
3765 /* Regular reduction */
3770 /* Reduction pattern */
3771 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (orig_stmt
);
3772 gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
));
3773 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo
) == stmt
);
3776 code
= gimple_assign_rhs_code (orig_stmt
);
3777 /* For MINUS_EXPR the initial vector is [init_val,0,...,0], therefore,
3778 partial results are added and not subtracted. */
3779 if (code
== MINUS_EXPR
)
3782 scalar_dest
= gimple_assign_lhs (orig_stmt
);
3783 scalar_type
= TREE_TYPE (scalar_dest
);
3784 scalar_results
= VEC_alloc (tree
, heap
, group_size
);
3785 new_scalar_dest
= vect_create_destination_var (scalar_dest
, NULL
);
3786 bitsize
= TYPE_SIZE (scalar_type
);
3788 /* In case this is a reduction in an inner-loop while vectorizing an outer
3789 loop - we don't need to extract a single scalar result at the end of the
3790 inner-loop (unless it is double reduction, i.e., the use of reduction is
3791 outside the outer-loop). The final vector of partial results will be used
3792 in the vectorized outer-loop, or reduced to a scalar result at the end of
3794 if (nested_in_vect_loop
&& !double_reduc
)
3795 goto vect_finalize_reduction
;
3797 /* SLP reduction without reduction chain, e.g.,
3801 b2 = operation (b1) */
3802 slp_reduc
= (slp_node
&& !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)));
3804 /* In case of reduction chain, e.g.,
3807 a3 = operation (a2),
3809 we may end up with more than one vector result. Here we reduce them to
3811 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
3813 tree first_vect
= PHI_RESULT (VEC_index (gimple
, new_phis
, 0));
3815 gimple new_vec_stmt
= NULL
;
3817 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
3818 for (k
= 1; k
< VEC_length (gimple
, new_phis
); k
++)
3820 gimple next_phi
= VEC_index (gimple
, new_phis
, k
);
3821 tree second_vect
= PHI_RESULT (next_phi
);
3823 tmp
= build2 (code
, vectype
, first_vect
, second_vect
);
3824 new_vec_stmt
= gimple_build_assign (vec_dest
, tmp
);
3825 first_vect
= make_ssa_name (vec_dest
, new_vec_stmt
);
3826 gimple_assign_set_lhs (new_vec_stmt
, first_vect
);
3827 gsi_insert_before (&exit_gsi
, new_vec_stmt
, GSI_SAME_STMT
);
3830 new_phi_result
= first_vect
;
3833 VEC_truncate (gimple
, new_phis
, 0);
3834 VEC_safe_push (gimple
, heap
, new_phis
, new_vec_stmt
);
3838 new_phi_result
= PHI_RESULT (VEC_index (gimple
, new_phis
, 0));
3840 /* 2.3 Create the reduction code, using one of the three schemes described
3841 above. In SLP we simply need to extract all the elements from the
3842 vector (without reducing them), so we use scalar shifts. */
3843 if (reduc_code
!= ERROR_MARK
&& !slp_reduc
)
3847 /*** Case 1: Create:
3848 v_out2 = reduc_expr <v_out1> */
3850 if (vect_print_dump_info (REPORT_DETAILS
))
3851 fprintf (vect_dump
, "Reduce using direct vector reduction.");
3853 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
3854 tmp
= build1 (reduc_code
, vectype
, new_phi_result
);
3855 epilog_stmt
= gimple_build_assign (vec_dest
, tmp
);
3856 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
3857 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
3858 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
3860 extract_scalar_result
= true;
3864 enum tree_code shift_code
= ERROR_MARK
;
3865 bool have_whole_vector_shift
= true;
3867 int element_bitsize
= tree_low_cst (bitsize
, 1);
3868 int vec_size_in_bits
= tree_low_cst (TYPE_SIZE (vectype
), 1);
3871 if (optab_handler (vec_shr_optab
, mode
) != CODE_FOR_nothing
)
3872 shift_code
= VEC_RSHIFT_EXPR
;
3874 have_whole_vector_shift
= false;
3876 /* Regardless of whether we have a whole vector shift, if we're
3877 emulating the operation via tree-vect-generic, we don't want
3878 to use it. Only the first round of the reduction is likely
3879 to still be profitable via emulation. */
3880 /* ??? It might be better to emit a reduction tree code here, so that
3881 tree-vect-generic can expand the first round via bit tricks. */
3882 if (!VECTOR_MODE_P (mode
))
3883 have_whole_vector_shift
= false;
3886 optab optab
= optab_for_tree_code (code
, vectype
, optab_default
);
3887 if (optab_handler (optab
, mode
) == CODE_FOR_nothing
)
3888 have_whole_vector_shift
= false;
3891 if (have_whole_vector_shift
&& !slp_reduc
)
3893 /*** Case 2: Create:
3894 for (offset = VS/2; offset >= element_size; offset/=2)
3896 Create: va' = vec_shift <va, offset>
3897 Create: va = vop <va, va'>
3900 if (vect_print_dump_info (REPORT_DETAILS
))
3901 fprintf (vect_dump
, "Reduce using vector shifts");
3903 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
3904 new_temp
= new_phi_result
;
3905 for (bit_offset
= vec_size_in_bits
/2;
3906 bit_offset
>= element_bitsize
;
3909 tree bitpos
= size_int (bit_offset
);
3911 epilog_stmt
= gimple_build_assign_with_ops (shift_code
,
3912 vec_dest
, new_temp
, bitpos
);
3913 new_name
= make_ssa_name (vec_dest
, epilog_stmt
);
3914 gimple_assign_set_lhs (epilog_stmt
, new_name
);
3915 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
3917 epilog_stmt
= gimple_build_assign_with_ops (code
, vec_dest
,
3918 new_name
, new_temp
);
3919 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
3920 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
3921 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
3924 extract_scalar_result
= true;
3930 /*** Case 3: Create:
3931 s = extract_field <v_out2, 0>
3932 for (offset = element_size;
3933 offset < vector_size;
3934 offset += element_size;)
3936 Create: s' = extract_field <v_out2, offset>
3937 Create: s = op <s, s'> // For non SLP cases
3940 if (vect_print_dump_info (REPORT_DETAILS
))
3941 fprintf (vect_dump
, "Reduce using scalar code. ");
3943 vec_size_in_bits
= tree_low_cst (TYPE_SIZE (vectype
), 1);
3944 FOR_EACH_VEC_ELT (gimple
, new_phis
, i
, new_phi
)
3946 if (gimple_code (new_phi
) == GIMPLE_PHI
)
3947 vec_temp
= PHI_RESULT (new_phi
);
3949 vec_temp
= gimple_assign_lhs (new_phi
);
3950 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
, bitsize
,
3952 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
3953 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
3954 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
3955 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
3957 /* In SLP we don't need to apply reduction operation, so we just
3958 collect s' values in SCALAR_RESULTS. */
3960 VEC_safe_push (tree
, heap
, scalar_results
, new_temp
);
3962 for (bit_offset
= element_bitsize
;
3963 bit_offset
< vec_size_in_bits
;
3964 bit_offset
+= element_bitsize
)
3966 tree bitpos
= bitsize_int (bit_offset
);
3967 tree rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
,
3970 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
3971 new_name
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
3972 gimple_assign_set_lhs (epilog_stmt
, new_name
);
3973 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
3977 /* In SLP we don't need to apply reduction operation, so
3978 we just collect s' values in SCALAR_RESULTS. */
3979 new_temp
= new_name
;
3980 VEC_safe_push (tree
, heap
, scalar_results
, new_name
);
3984 epilog_stmt
= gimple_build_assign_with_ops (code
,
3985 new_scalar_dest
, new_name
, new_temp
);
3986 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
3987 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
3988 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
3993 /* The only case where we need to reduce scalar results in SLP, is
3994 unrolling. If the size of SCALAR_RESULTS is greater than
3995 GROUP_SIZE, we reduce them combining elements modulo
3999 tree res
, first_res
, new_res
;
4002 /* Reduce multiple scalar results in case of SLP unrolling. */
4003 for (j
= group_size
; VEC_iterate (tree
, scalar_results
, j
, res
);
4006 first_res
= VEC_index (tree
, scalar_results
, j
% group_size
);
4007 new_stmt
= gimple_build_assign_with_ops (code
,
4008 new_scalar_dest
, first_res
, res
);
4009 new_res
= make_ssa_name (new_scalar_dest
, new_stmt
);
4010 gimple_assign_set_lhs (new_stmt
, new_res
);
4011 gsi_insert_before (&exit_gsi
, new_stmt
, GSI_SAME_STMT
);
4012 VEC_replace (tree
, scalar_results
, j
% group_size
, new_res
);
4016 /* Not SLP - we have one scalar to keep in SCALAR_RESULTS. */
4017 VEC_safe_push (tree
, heap
, scalar_results
, new_temp
);
4019 extract_scalar_result
= false;
4023 /* 2.4 Extract the final scalar result. Create:
4024 s_out3 = extract_field <v_out2, bitpos> */
4026 if (extract_scalar_result
)
4030 if (vect_print_dump_info (REPORT_DETAILS
))
4031 fprintf (vect_dump
, "extract scalar result");
4033 if (BYTES_BIG_ENDIAN
)
4034 bitpos
= size_binop (MULT_EXPR
,
4035 bitsize_int (TYPE_VECTOR_SUBPARTS (vectype
) - 1),
4036 TYPE_SIZE (scalar_type
));
4038 bitpos
= bitsize_zero_node
;
4040 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, new_temp
, bitsize
, bitpos
);
4041 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
4042 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
4043 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4044 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4045 VEC_safe_push (tree
, heap
, scalar_results
, new_temp
);
4048 vect_finalize_reduction
:
4053 /* 2.5 Adjust the final result by the initial value of the reduction
4054 variable. (When such adjustment is not needed, then
4055 'adjustment_def' is zero). For example, if code is PLUS we create:
4056 new_temp = loop_exit_def + adjustment_def */
4060 gcc_assert (!slp_reduc
);
4061 if (nested_in_vect_loop
)
4063 new_phi
= VEC_index (gimple
, new_phis
, 0);
4064 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) == VECTOR_TYPE
);
4065 expr
= build2 (code
, vectype
, PHI_RESULT (new_phi
), adjustment_def
);
4066 new_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4070 new_temp
= VEC_index (tree
, scalar_results
, 0);
4071 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) != VECTOR_TYPE
);
4072 expr
= build2 (code
, scalar_type
, new_temp
, adjustment_def
);
4073 new_dest
= vect_create_destination_var (scalar_dest
, scalar_type
);
4076 epilog_stmt
= gimple_build_assign (new_dest
, expr
);
4077 new_temp
= make_ssa_name (new_dest
, epilog_stmt
);
4078 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
4079 SSA_NAME_DEF_STMT (new_temp
) = epilog_stmt
;
4080 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
4081 if (nested_in_vect_loop
)
4083 set_vinfo_for_stmt (epilog_stmt
,
4084 new_stmt_vec_info (epilog_stmt
, loop_vinfo
,
4086 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (epilog_stmt
)) =
4087 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_phi
));
4090 VEC_quick_push (tree
, scalar_results
, new_temp
);
4092 VEC_replace (tree
, scalar_results
, 0, new_temp
);
4095 VEC_replace (tree
, scalar_results
, 0, new_temp
);
4097 VEC_replace (gimple
, new_phis
, 0, epilog_stmt
);
4100 /* 2.6 Handle the loop-exit phis. Replace the uses of scalar loop-exit
4101 phis with new adjusted scalar results, i.e., replace use <s_out0>
4106 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4107 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4108 v_out2 = reduce <v_out1>
4109 s_out3 = extract_field <v_out2, 0>
4110 s_out4 = adjust_result <s_out3>
4117 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4118 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4119 v_out2 = reduce <v_out1>
4120 s_out3 = extract_field <v_out2, 0>
4121 s_out4 = adjust_result <s_out3>
4126 /* In SLP reduction chain we reduce vector results into one vector if
4127 necessary, hence we set here GROUP_SIZE to 1. SCALAR_DEST is the LHS of
4128 the last stmt in the reduction chain, since we are looking for the loop
4130 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4132 scalar_dest
= gimple_assign_lhs (VEC_index (gimple
,
4133 SLP_TREE_SCALAR_STMTS (slp_node
),
4138 /* In SLP we may have several statements in NEW_PHIS and REDUCTION_PHIS (in
4139 case that GROUP_SIZE is greater than vectorization factor). Therefore, we
4140 need to match SCALAR_RESULTS with corresponding statements. The first
4141 (GROUP_SIZE / number of new vector stmts) scalar results correspond to
4142 the first vector stmt, etc.
4143 (RATIO is equal to (GROUP_SIZE / number of new vector stmts)). */
4144 if (group_size
> VEC_length (gimple
, new_phis
))
4146 ratio
= group_size
/ VEC_length (gimple
, new_phis
);
4147 gcc_assert (!(group_size
% VEC_length (gimple
, new_phis
)));
4152 for (k
= 0; k
< group_size
; k
++)
4156 epilog_stmt
= VEC_index (gimple
, new_phis
, k
/ ratio
);
4157 reduction_phi
= VEC_index (gimple
, reduction_phis
, k
/ ratio
);
4159 inner_phi
= VEC_index (gimple
, inner_phis
, k
/ ratio
);
4164 gimple current_stmt
= VEC_index (gimple
,
4165 SLP_TREE_SCALAR_STMTS (slp_node
), k
);
4167 orig_stmt
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (current_stmt
));
4168 /* SLP statements can't participate in patterns. */
4169 gcc_assert (!orig_stmt
);
4170 scalar_dest
= gimple_assign_lhs (current_stmt
);
4173 phis
= VEC_alloc (gimple
, heap
, 3);
4174 /* Find the loop-closed-use at the loop exit of the original scalar
4175 result. (The reduction result is expected to have two immediate uses -
4176 one at the latch block, and one at the loop exit). */
4177 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
4178 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
4179 VEC_safe_push (gimple
, heap
, phis
, USE_STMT (use_p
));
4181 /* We expect to have found an exit_phi because of loop-closed-ssa
4183 gcc_assert (!VEC_empty (gimple
, phis
));
4185 FOR_EACH_VEC_ELT (gimple
, phis
, i
, exit_phi
)
4189 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
4192 /* FORNOW. Currently not supporting the case that an inner-loop
4193 reduction is not used in the outer-loop (but only outside the
4194 outer-loop), unless it is double reduction. */
4195 gcc_assert ((STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
4196 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
))
4199 STMT_VINFO_VEC_STMT (exit_phi_vinfo
) = epilog_stmt
;
4201 || STMT_VINFO_DEF_TYPE (exit_phi_vinfo
)
4202 != vect_double_reduction_def
)
4205 /* Handle double reduction:
4207 stmt1: s1 = phi <s0, s2> - double reduction phi (outer loop)
4208 stmt2: s3 = phi <s1, s4> - (regular) reduc phi (inner loop)
4209 stmt3: s4 = use (s3) - (regular) reduc stmt (inner loop)
4210 stmt4: s2 = phi <s4> - double reduction stmt (outer loop)
4212 At that point the regular reduction (stmt2 and stmt3) is
4213 already vectorized, as well as the exit phi node, stmt4.
4214 Here we vectorize the phi node of double reduction, stmt1, and
4215 update all relevant statements. */
4217 /* Go through all the uses of s2 to find double reduction phi
4218 node, i.e., stmt1 above. */
4219 orig_name
= PHI_RESULT (exit_phi
);
4220 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
4222 stmt_vec_info use_stmt_vinfo
;
4223 stmt_vec_info new_phi_vinfo
;
4224 tree vect_phi_init
, preheader_arg
, vect_phi_res
, init_def
;
4225 basic_block bb
= gimple_bb (use_stmt
);
4228 /* Check that USE_STMT is really double reduction phi
4230 if (gimple_code (use_stmt
) != GIMPLE_PHI
4231 || gimple_phi_num_args (use_stmt
) != 2
4232 || bb
->loop_father
!= outer_loop
)
4234 use_stmt_vinfo
= vinfo_for_stmt (use_stmt
);
4236 || STMT_VINFO_DEF_TYPE (use_stmt_vinfo
)
4237 != vect_double_reduction_def
)
4240 /* Create vector phi node for double reduction:
4241 vs1 = phi <vs0, vs2>
4242 vs1 was created previously in this function by a call to
4243 vect_get_vec_def_for_operand and is stored in
4245 vs2 is defined by INNER_PHI, the vectorized EXIT_PHI;
4246 vs0 is created here. */
4248 /* Create vector phi node. */
4249 vect_phi
= create_phi_node (vec_initial_def
, bb
);
4250 new_phi_vinfo
= new_stmt_vec_info (vect_phi
,
4251 loop_vec_info_for_loop (outer_loop
), NULL
);
4252 set_vinfo_for_stmt (vect_phi
, new_phi_vinfo
);
4254 /* Create vs0 - initial def of the double reduction phi. */
4255 preheader_arg
= PHI_ARG_DEF_FROM_EDGE (use_stmt
,
4256 loop_preheader_edge (outer_loop
));
4257 init_def
= get_initial_def_for_reduction (stmt
,
4258 preheader_arg
, NULL
);
4259 vect_phi_init
= vect_init_vector (use_stmt
, init_def
,
4262 /* Update phi node arguments with vs0 and vs2. */
4263 add_phi_arg (vect_phi
, vect_phi_init
,
4264 loop_preheader_edge (outer_loop
),
4266 add_phi_arg (vect_phi
, PHI_RESULT (inner_phi
),
4267 loop_latch_edge (outer_loop
), UNKNOWN_LOCATION
);
4268 if (vect_print_dump_info (REPORT_DETAILS
))
4270 fprintf (vect_dump
, "created double reduction phi "
4272 print_gimple_stmt (vect_dump
, vect_phi
, 0, TDF_SLIM
);
4275 vect_phi_res
= PHI_RESULT (vect_phi
);
4277 /* Replace the use, i.e., set the correct vs1 in the regular
4278 reduction phi node. FORNOW, NCOPIES is always 1, so the
4279 loop is redundant. */
4280 use
= reduction_phi
;
4281 for (j
= 0; j
< ncopies
; j
++)
4283 edge pr_edge
= loop_preheader_edge (loop
);
4284 SET_PHI_ARG_DEF (use
, pr_edge
->dest_idx
, vect_phi_res
);
4285 use
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use
));
4291 VEC_free (gimple
, heap
, phis
);
4292 if (nested_in_vect_loop
)
4300 phis
= VEC_alloc (gimple
, heap
, 3);
4301 /* Find the loop-closed-use at the loop exit of the original scalar
4302 result. (The reduction result is expected to have two immediate uses,
4303 one at the latch block, and one at the loop exit). For double
4304 reductions we are looking for exit phis of the outer loop. */
4305 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
4307 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
4308 VEC_safe_push (gimple
, heap
, phis
, USE_STMT (use_p
));
4311 if (double_reduc
&& gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
4313 tree phi_res
= PHI_RESULT (USE_STMT (use_p
));
4315 FOR_EACH_IMM_USE_FAST (phi_use_p
, phi_imm_iter
, phi_res
)
4317 if (!flow_bb_inside_loop_p (loop
,
4318 gimple_bb (USE_STMT (phi_use_p
))))
4319 VEC_safe_push (gimple
, heap
, phis
,
4320 USE_STMT (phi_use_p
));
4326 FOR_EACH_VEC_ELT (gimple
, phis
, i
, exit_phi
)
4328 /* Replace the uses: */
4329 orig_name
= PHI_RESULT (exit_phi
);
4330 scalar_result
= VEC_index (tree
, scalar_results
, k
);
4331 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
4332 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
4333 SET_USE (use_p
, scalar_result
);
4336 VEC_free (gimple
, heap
, phis
);
4339 VEC_free (tree
, heap
, scalar_results
);
4340 VEC_free (gimple
, heap
, new_phis
);
4344 /* Function vectorizable_reduction.
4346 Check if STMT performs a reduction operation that can be vectorized.
4347 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4348 stmt to replace it, put it in VEC_STMT, and insert it at GSI.
4349 Return FALSE if not a vectorizable STMT, TRUE otherwise.
4351 This function also handles reduction idioms (patterns) that have been
4352 recognized in advance during vect_pattern_recog. In this case, STMT may be
4354 X = pattern_expr (arg0, arg1, ..., X)
4355 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
4356 sequence that had been detected and replaced by the pattern-stmt (STMT).
4358 In some cases of reduction patterns, the type of the reduction variable X is
4359 different than the type of the other arguments of STMT.
4360 In such cases, the vectype that is used when transforming STMT into a vector
4361 stmt is different than the vectype that is used to determine the
4362 vectorization factor, because it consists of a different number of elements
4363 than the actual number of elements that are being operated upon in parallel.
4365 For example, consider an accumulation of shorts into an int accumulator.
4366 On some targets it's possible to vectorize this pattern operating on 8
4367 shorts at a time (hence, the vectype for purposes of determining the
4368 vectorization factor should be V8HI); on the other hand, the vectype that
4369 is used to create the vector form is actually V4SI (the type of the result).
4371 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
4372 indicates what is the actual level of parallelism (V8HI in the example), so
4373 that the right vectorization factor would be derived. This vectype
4374 corresponds to the type of arguments to the reduction stmt, and should *NOT*
4375 be used to create the vectorized stmt. The right vectype for the vectorized
4376 stmt is obtained from the type of the result X:
4377 get_vectype_for_scalar_type (TREE_TYPE (X))
4379 This means that, contrary to "regular" reductions (or "regular" stmts in
4380 general), the following equation:
4381 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
4382 does *NOT* necessarily hold for reduction patterns. */
4385 vectorizable_reduction (gimple stmt
, gimple_stmt_iterator
*gsi
,
4386 gimple
*vec_stmt
, slp_tree slp_node
)
4390 tree loop_vec_def0
= NULL_TREE
, loop_vec_def1
= NULL_TREE
;
4391 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
4392 tree vectype_out
= STMT_VINFO_VECTYPE (stmt_info
);
4393 tree vectype_in
= NULL_TREE
;
4394 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
4395 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4396 enum tree_code code
, orig_code
, epilog_reduc_code
;
4397 enum machine_mode vec_mode
;
4399 optab optab
, reduc_optab
;
4400 tree new_temp
= NULL_TREE
;
4403 enum vect_def_type dt
;
4404 gimple new_phi
= NULL
;
4408 stmt_vec_info orig_stmt_info
;
4409 tree expr
= NULL_TREE
;
4413 stmt_vec_info prev_stmt_info
, prev_phi_info
;
4414 bool single_defuse_cycle
= false;
4415 tree reduc_def
= NULL_TREE
;
4416 gimple new_stmt
= NULL
;
4419 bool nested_cycle
= false, found_nested_cycle_def
= false;
4420 gimple reduc_def_stmt
= NULL
;
4421 /* The default is that the reduction variable is the last in statement. */
4422 int reduc_index
= 2;
4423 bool double_reduc
= false, dummy
;
4425 struct loop
* def_stmt_loop
, *outer_loop
= NULL
;
4427 gimple def_arg_stmt
;
4428 VEC (tree
, heap
) *vec_oprnds0
= NULL
, *vec_oprnds1
= NULL
, *vect_defs
= NULL
;
4429 VEC (gimple
, heap
) *phis
= NULL
;
4431 tree def0
, def1
, tem
, op0
, op1
= NULL_TREE
;
4433 /* In case of reduction chain we switch to the first stmt in the chain, but
4434 we don't update STMT_INFO, since only the last stmt is marked as reduction
4435 and has reduction properties. */
4436 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
4437 stmt
= GROUP_FIRST_ELEMENT (stmt_info
);
4439 if (nested_in_vect_loop_p (loop
, stmt
))
4443 nested_cycle
= true;
4446 /* 1. Is vectorizable reduction? */
4447 /* Not supportable if the reduction variable is used in the loop, unless
4448 it's a reduction chain. */
4449 if (STMT_VINFO_RELEVANT (stmt_info
) > vect_used_in_outer
4450 && !GROUP_FIRST_ELEMENT (stmt_info
))
4453 /* Reductions that are not used even in an enclosing outer-loop,
4454 are expected to be "live" (used out of the loop). */
4455 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
4456 && !STMT_VINFO_LIVE_P (stmt_info
))
4459 /* Make sure it was already recognized as a reduction computation. */
4460 if (STMT_VINFO_DEF_TYPE (stmt_info
) != vect_reduction_def
4461 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_nested_cycle
)
4464 /* 2. Has this been recognized as a reduction pattern?
4466 Check if STMT represents a pattern that has been recognized
4467 in earlier analysis stages. For stmts that represent a pattern,
4468 the STMT_VINFO_RELATED_STMT field records the last stmt in
4469 the original sequence that constitutes the pattern. */
4471 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
4474 orig_stmt_info
= vinfo_for_stmt (orig_stmt
);
4475 gcc_assert (STMT_VINFO_RELATED_STMT (orig_stmt_info
) == stmt
);
4476 gcc_assert (STMT_VINFO_IN_PATTERN_P (orig_stmt_info
));
4477 gcc_assert (!STMT_VINFO_IN_PATTERN_P (stmt_info
));
4480 /* 3. Check the operands of the operation. The first operands are defined
4481 inside the loop body. The last operand is the reduction variable,
4482 which is defined by the loop-header-phi. */
4484 gcc_assert (is_gimple_assign (stmt
));
4487 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
4489 case GIMPLE_SINGLE_RHS
:
4490 op_type
= TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
));
4491 if (op_type
== ternary_op
)
4493 tree rhs
= gimple_assign_rhs1 (stmt
);
4494 ops
[0] = TREE_OPERAND (rhs
, 0);
4495 ops
[1] = TREE_OPERAND (rhs
, 1);
4496 ops
[2] = TREE_OPERAND (rhs
, 2);
4497 code
= TREE_CODE (rhs
);
4503 case GIMPLE_BINARY_RHS
:
4504 code
= gimple_assign_rhs_code (stmt
);
4505 op_type
= TREE_CODE_LENGTH (code
);
4506 gcc_assert (op_type
== binary_op
);
4507 ops
[0] = gimple_assign_rhs1 (stmt
);
4508 ops
[1] = gimple_assign_rhs2 (stmt
);
4511 case GIMPLE_TERNARY_RHS
:
4512 code
= gimple_assign_rhs_code (stmt
);
4513 op_type
= TREE_CODE_LENGTH (code
);
4514 gcc_assert (op_type
== ternary_op
);
4515 ops
[0] = gimple_assign_rhs1 (stmt
);
4516 ops
[1] = gimple_assign_rhs2 (stmt
);
4517 ops
[2] = gimple_assign_rhs3 (stmt
);
4520 case GIMPLE_UNARY_RHS
:
4527 if (code
== COND_EXPR
&& slp_node
)
4530 scalar_dest
= gimple_assign_lhs (stmt
);
4531 scalar_type
= TREE_TYPE (scalar_dest
);
4532 if (!POINTER_TYPE_P (scalar_type
) && !INTEGRAL_TYPE_P (scalar_type
)
4533 && !SCALAR_FLOAT_TYPE_P (scalar_type
))
4536 /* Do not try to vectorize bit-precision reductions. */
4537 if ((TYPE_PRECISION (scalar_type
)
4538 != GET_MODE_PRECISION (TYPE_MODE (scalar_type
))))
4541 /* All uses but the last are expected to be defined in the loop.
4542 The last use is the reduction variable. In case of nested cycle this
4543 assumption is not true: we use reduc_index to record the index of the
4544 reduction variable. */
4545 for (i
= 0; i
< op_type
-1; i
++)
4547 /* The condition of COND_EXPR is checked in vectorizable_condition(). */
4548 if (i
== 0 && code
== COND_EXPR
)
4551 is_simple_use
= vect_is_simple_use_1 (ops
[i
], stmt
, loop_vinfo
, NULL
,
4552 &def_stmt
, &def
, &dt
, &tem
);
4555 gcc_assert (is_simple_use
);
4557 if (dt
!= vect_internal_def
4558 && dt
!= vect_external_def
4559 && dt
!= vect_constant_def
4560 && dt
!= vect_induction_def
4561 && !(dt
== vect_nested_cycle
&& nested_cycle
))
4564 if (dt
== vect_nested_cycle
)
4566 found_nested_cycle_def
= true;
4567 reduc_def_stmt
= def_stmt
;
4572 is_simple_use
= vect_is_simple_use_1 (ops
[i
], stmt
, loop_vinfo
, NULL
,
4573 &def_stmt
, &def
, &dt
, &tem
);
4576 gcc_assert (is_simple_use
);
4577 gcc_assert (dt
== vect_reduction_def
4578 || dt
== vect_nested_cycle
4579 || ((dt
== vect_internal_def
|| dt
== vect_external_def
4580 || dt
== vect_constant_def
|| dt
== vect_induction_def
)
4581 && nested_cycle
&& found_nested_cycle_def
));
4582 if (!found_nested_cycle_def
)
4583 reduc_def_stmt
= def_stmt
;
4585 gcc_assert (gimple_code (reduc_def_stmt
) == GIMPLE_PHI
);
4587 gcc_assert (orig_stmt
== vect_is_simple_reduction (loop_vinfo
,
4593 gimple tmp
= vect_is_simple_reduction (loop_vinfo
, reduc_def_stmt
,
4594 !nested_cycle
, &dummy
);
4595 /* We changed STMT to be the first stmt in reduction chain, hence we
4596 check that in this case the first element in the chain is STMT. */
4597 gcc_assert (stmt
== tmp
4598 || GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp
)) == stmt
);
4601 if (STMT_VINFO_LIVE_P (vinfo_for_stmt (reduc_def_stmt
)))
4604 if (slp_node
|| PURE_SLP_STMT (stmt_info
))
4607 ncopies
= (LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4608 / TYPE_VECTOR_SUBPARTS (vectype_in
));
4610 gcc_assert (ncopies
>= 1);
4612 vec_mode
= TYPE_MODE (vectype_in
);
4614 if (code
== COND_EXPR
)
4616 if (!vectorizable_condition (stmt
, gsi
, NULL
, ops
[reduc_index
], 0, NULL
))
4618 if (vect_print_dump_info (REPORT_DETAILS
))
4619 fprintf (vect_dump
, "unsupported condition in reduction");
4626 /* 4. Supportable by target? */
4628 /* 4.1. check support for the operation in the loop */
4629 optab
= optab_for_tree_code (code
, vectype_in
, optab_default
);
4632 if (vect_print_dump_info (REPORT_DETAILS
))
4633 fprintf (vect_dump
, "no optab.");
4638 if (optab_handler (optab
, vec_mode
) == CODE_FOR_nothing
)
4640 if (vect_print_dump_info (REPORT_DETAILS
))
4641 fprintf (vect_dump
, "op not supported by target.");
4643 if (GET_MODE_SIZE (vec_mode
) != UNITS_PER_WORD
4644 || LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4645 < vect_min_worthwhile_factor (code
))
4648 if (vect_print_dump_info (REPORT_DETAILS
))
4649 fprintf (vect_dump
, "proceeding using word mode.");
4652 /* Worthwhile without SIMD support? */
4653 if (!VECTOR_MODE_P (TYPE_MODE (vectype_in
))
4654 && LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
4655 < vect_min_worthwhile_factor (code
))
4657 if (vect_print_dump_info (REPORT_DETAILS
))
4658 fprintf (vect_dump
, "not worthwhile without SIMD support.");
4664 /* 4.2. Check support for the epilog operation.
4666 If STMT represents a reduction pattern, then the type of the
4667 reduction variable may be different than the type of the rest
4668 of the arguments. For example, consider the case of accumulation
4669 of shorts into an int accumulator; The original code:
4670 S1: int_a = (int) short_a;
4671 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
4674 STMT: int_acc = widen_sum <short_a, int_acc>
4677 1. The tree-code that is used to create the vector operation in the
4678 epilog code (that reduces the partial results) is not the
4679 tree-code of STMT, but is rather the tree-code of the original
4680 stmt from the pattern that STMT is replacing. I.e, in the example
4681 above we want to use 'widen_sum' in the loop, but 'plus' in the
4683 2. The type (mode) we use to check available target support
4684 for the vector operation to be created in the *epilog*, is
4685 determined by the type of the reduction variable (in the example
4686 above we'd check this: optab_handler (plus_optab, vect_int_mode])).
4687 However the type (mode) we use to check available target support
4688 for the vector operation to be created *inside the loop*, is
4689 determined by the type of the other arguments to STMT (in the
4690 example we'd check this: optab_handler (widen_sum_optab,
4693 This is contrary to "regular" reductions, in which the types of all
4694 the arguments are the same as the type of the reduction variable.
4695 For "regular" reductions we can therefore use the same vector type
4696 (and also the same tree-code) when generating the epilog code and
4697 when generating the code inside the loop. */
4701 /* This is a reduction pattern: get the vectype from the type of the
4702 reduction variable, and get the tree-code from orig_stmt. */
4703 orig_code
= gimple_assign_rhs_code (orig_stmt
);
4704 gcc_assert (vectype_out
);
4705 vec_mode
= TYPE_MODE (vectype_out
);
4709 /* Regular reduction: use the same vectype and tree-code as used for
4710 the vector code inside the loop can be used for the epilog code. */
4716 def_bb
= gimple_bb (reduc_def_stmt
);
4717 def_stmt_loop
= def_bb
->loop_father
;
4718 def_arg
= PHI_ARG_DEF_FROM_EDGE (reduc_def_stmt
,
4719 loop_preheader_edge (def_stmt_loop
));
4720 if (TREE_CODE (def_arg
) == SSA_NAME
4721 && (def_arg_stmt
= SSA_NAME_DEF_STMT (def_arg
))
4722 && gimple_code (def_arg_stmt
) == GIMPLE_PHI
4723 && flow_bb_inside_loop_p (outer_loop
, gimple_bb (def_arg_stmt
))
4724 && vinfo_for_stmt (def_arg_stmt
)
4725 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_arg_stmt
))
4726 == vect_double_reduction_def
)
4727 double_reduc
= true;
4730 epilog_reduc_code
= ERROR_MARK
;
4731 if (reduction_code_for_scalar_code (orig_code
, &epilog_reduc_code
))
4733 reduc_optab
= optab_for_tree_code (epilog_reduc_code
, vectype_out
,
4737 if (vect_print_dump_info (REPORT_DETAILS
))
4738 fprintf (vect_dump
, "no optab for reduction.");
4740 epilog_reduc_code
= ERROR_MARK
;
4744 && optab_handler (reduc_optab
, vec_mode
) == CODE_FOR_nothing
)
4746 if (vect_print_dump_info (REPORT_DETAILS
))
4747 fprintf (vect_dump
, "reduc op not supported by target.");
4749 epilog_reduc_code
= ERROR_MARK
;
4754 if (!nested_cycle
|| double_reduc
)
4756 if (vect_print_dump_info (REPORT_DETAILS
))
4757 fprintf (vect_dump
, "no reduc code for scalar code.");
4763 if (double_reduc
&& ncopies
> 1)
4765 if (vect_print_dump_info (REPORT_DETAILS
))
4766 fprintf (vect_dump
, "multiple types in double reduction");
4771 /* In case of widenning multiplication by a constant, we update the type
4772 of the constant to be the type of the other operand. We check that the
4773 constant fits the type in the pattern recognition pass. */
4774 if (code
== DOT_PROD_EXPR
4775 && !types_compatible_p (TREE_TYPE (ops
[0]), TREE_TYPE (ops
[1])))
4777 if (TREE_CODE (ops
[0]) == INTEGER_CST
)
4778 ops
[0] = fold_convert (TREE_TYPE (ops
[1]), ops
[0]);
4779 else if (TREE_CODE (ops
[1]) == INTEGER_CST
)
4780 ops
[1] = fold_convert (TREE_TYPE (ops
[0]), ops
[1]);
4783 if (vect_print_dump_info (REPORT_DETAILS
))
4784 fprintf (vect_dump
, "invalid types in dot-prod");
4790 if (!vec_stmt
) /* transformation not required. */
4792 if (!vect_model_reduction_cost (stmt_info
, epilog_reduc_code
, ncopies
))
4794 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
4800 if (vect_print_dump_info (REPORT_DETAILS
))
4801 fprintf (vect_dump
, "transform reduction.");
4803 /* FORNOW: Multiple types are not supported for condition. */
4804 if (code
== COND_EXPR
)
4805 gcc_assert (ncopies
== 1);
4807 /* Create the destination vector */
4808 vec_dest
= vect_create_destination_var (scalar_dest
, vectype_out
);
4810 /* In case the vectorization factor (VF) is bigger than the number
4811 of elements that we can fit in a vectype (nunits), we have to generate
4812 more than one vector stmt - i.e - we need to "unroll" the
4813 vector stmt by a factor VF/nunits. For more details see documentation
4814 in vectorizable_operation. */
4816 /* If the reduction is used in an outer loop we need to generate
4817 VF intermediate results, like so (e.g. for ncopies=2):
4822 (i.e. we generate VF results in 2 registers).
4823 In this case we have a separate def-use cycle for each copy, and therefore
4824 for each copy we get the vector def for the reduction variable from the
4825 respective phi node created for this copy.
4827 Otherwise (the reduction is unused in the loop nest), we can combine
4828 together intermediate results, like so (e.g. for ncopies=2):
4832 (i.e. we generate VF/2 results in a single register).
4833 In this case for each copy we get the vector def for the reduction variable
4834 from the vectorized reduction operation generated in the previous iteration.
4837 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
)
4839 single_defuse_cycle
= true;
4843 epilog_copies
= ncopies
;
4845 prev_stmt_info
= NULL
;
4846 prev_phi_info
= NULL
;
4849 vec_num
= SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node
);
4850 gcc_assert (TYPE_VECTOR_SUBPARTS (vectype_out
)
4851 == TYPE_VECTOR_SUBPARTS (vectype_in
));
4856 vec_oprnds0
= VEC_alloc (tree
, heap
, 1);
4857 if (op_type
== ternary_op
)
4858 vec_oprnds1
= VEC_alloc (tree
, heap
, 1);
4861 phis
= VEC_alloc (gimple
, heap
, vec_num
);
4862 vect_defs
= VEC_alloc (tree
, heap
, vec_num
);
4864 VEC_quick_push (tree
, vect_defs
, NULL_TREE
);
4866 for (j
= 0; j
< ncopies
; j
++)
4868 if (j
== 0 || !single_defuse_cycle
)
4870 for (i
= 0; i
< vec_num
; i
++)
4872 /* Create the reduction-phi that defines the reduction
4874 new_phi
= create_phi_node (vec_dest
, loop
->header
);
4875 set_vinfo_for_stmt (new_phi
,
4876 new_stmt_vec_info (new_phi
, loop_vinfo
,
4878 if (j
== 0 || slp_node
)
4879 VEC_quick_push (gimple
, phis
, new_phi
);
4883 if (code
== COND_EXPR
)
4885 gcc_assert (!slp_node
);
4886 vectorizable_condition (stmt
, gsi
, vec_stmt
,
4887 PHI_RESULT (VEC_index (gimple
, phis
, 0)),
4889 /* Multiple types are not supported for condition. */
4896 op0
= ops
[!reduc_index
];
4897 if (op_type
== ternary_op
)
4899 if (reduc_index
== 0)
4906 vect_get_vec_defs (op0
, op1
, stmt
, &vec_oprnds0
, &vec_oprnds1
,
4910 loop_vec_def0
= vect_get_vec_def_for_operand (ops
[!reduc_index
],
4912 VEC_quick_push (tree
, vec_oprnds0
, loop_vec_def0
);
4913 if (op_type
== ternary_op
)
4915 loop_vec_def1
= vect_get_vec_def_for_operand (op1
, stmt
,
4917 VEC_quick_push (tree
, vec_oprnds1
, loop_vec_def1
);
4925 enum vect_def_type dt
;
4929 vect_is_simple_use (ops
[!reduc_index
], stmt
, loop_vinfo
, NULL
,
4930 &dummy_stmt
, &dummy
, &dt
);
4931 loop_vec_def0
= vect_get_vec_def_for_stmt_copy (dt
,
4933 VEC_replace (tree
, vec_oprnds0
, 0, loop_vec_def0
);
4934 if (op_type
== ternary_op
)
4936 vect_is_simple_use (op1
, stmt
, loop_vinfo
, NULL
, &dummy_stmt
,
4938 loop_vec_def1
= vect_get_vec_def_for_stmt_copy (dt
,
4940 VEC_replace (tree
, vec_oprnds1
, 0, loop_vec_def1
);
4944 if (single_defuse_cycle
)
4945 reduc_def
= gimple_assign_lhs (new_stmt
);
4947 STMT_VINFO_RELATED_STMT (prev_phi_info
) = new_phi
;
4950 FOR_EACH_VEC_ELT (tree
, vec_oprnds0
, i
, def0
)
4953 reduc_def
= PHI_RESULT (VEC_index (gimple
, phis
, i
));
4956 if (!single_defuse_cycle
|| j
== 0)
4957 reduc_def
= PHI_RESULT (new_phi
);
4960 def1
= ((op_type
== ternary_op
)
4961 ? VEC_index (tree
, vec_oprnds1
, i
) : NULL
);
4962 if (op_type
== binary_op
)
4964 if (reduc_index
== 0)
4965 expr
= build2 (code
, vectype_out
, reduc_def
, def0
);
4967 expr
= build2 (code
, vectype_out
, def0
, reduc_def
);
4971 if (reduc_index
== 0)
4972 expr
= build3 (code
, vectype_out
, reduc_def
, def0
, def1
);
4975 if (reduc_index
== 1)
4976 expr
= build3 (code
, vectype_out
, def0
, reduc_def
, def1
);
4978 expr
= build3 (code
, vectype_out
, def0
, def1
, reduc_def
);
4982 new_stmt
= gimple_build_assign (vec_dest
, expr
);
4983 new_temp
= make_ssa_name (vec_dest
, new_stmt
);
4984 gimple_assign_set_lhs (new_stmt
, new_temp
);
4985 vect_finish_stmt_generation (stmt
, new_stmt
, gsi
);
4989 VEC_quick_push (gimple
, SLP_TREE_VEC_STMTS (slp_node
), new_stmt
);
4990 VEC_quick_push (tree
, vect_defs
, new_temp
);
4993 VEC_replace (tree
, vect_defs
, 0, new_temp
);
5000 STMT_VINFO_VEC_STMT (stmt_info
) = *vec_stmt
= new_stmt
;
5002 STMT_VINFO_RELATED_STMT (prev_stmt_info
) = new_stmt
;
5004 prev_stmt_info
= vinfo_for_stmt (new_stmt
);
5005 prev_phi_info
= vinfo_for_stmt (new_phi
);
5008 /* Finalize the reduction-phi (set its arguments) and create the
5009 epilog reduction code. */
5010 if ((!single_defuse_cycle
|| code
== COND_EXPR
) && !slp_node
)
5012 new_temp
= gimple_assign_lhs (*vec_stmt
);
5013 VEC_replace (tree
, vect_defs
, 0, new_temp
);
5016 vect_create_epilog_for_reduction (vect_defs
, stmt
, epilog_copies
,
5017 epilog_reduc_code
, phis
, reduc_index
,
5018 double_reduc
, slp_node
);
5020 VEC_free (gimple
, heap
, phis
);
5021 VEC_free (tree
, heap
, vec_oprnds0
);
5023 VEC_free (tree
, heap
, vec_oprnds1
);
5028 /* Function vect_min_worthwhile_factor.
5030 For a loop where we could vectorize the operation indicated by CODE,
5031 return the minimum vectorization factor that makes it worthwhile
5032 to use generic vectors. */
5034 vect_min_worthwhile_factor (enum tree_code code
)
5055 /* Function vectorizable_induction
5057 Check if PHI performs an induction computation that can be vectorized.
5058 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
5059 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
5060 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5063 vectorizable_induction (gimple phi
, gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
5066 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
5067 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
5068 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
5069 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5070 int nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
5071 int ncopies
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) / nunits
;
5074 gcc_assert (ncopies
>= 1);
5075 /* FORNOW. These restrictions should be relaxed. */
5076 if (nested_in_vect_loop_p (loop
, phi
))
5078 imm_use_iterator imm_iter
;
5079 use_operand_p use_p
;
5086 if (vect_print_dump_info (REPORT_DETAILS
))
5087 fprintf (vect_dump
, "multiple types in nested loop.");
5092 latch_e
= loop_latch_edge (loop
->inner
);
5093 loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
5094 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
5096 if (!flow_bb_inside_loop_p (loop
->inner
,
5097 gimple_bb (USE_STMT (use_p
))))
5099 exit_phi
= USE_STMT (use_p
);
5105 stmt_vec_info exit_phi_vinfo
= vinfo_for_stmt (exit_phi
);
5106 if (!(STMT_VINFO_RELEVANT_P (exit_phi_vinfo
)
5107 && !STMT_VINFO_LIVE_P (exit_phi_vinfo
)))
5109 if (vect_print_dump_info (REPORT_DETAILS
))
5110 fprintf (vect_dump
, "inner-loop induction only used outside "
5111 "of the outer vectorized loop.");
5117 if (!STMT_VINFO_RELEVANT_P (stmt_info
))
5120 /* FORNOW: SLP not supported. */
5121 if (STMT_SLP_TYPE (stmt_info
))
5124 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
);
5126 if (gimple_code (phi
) != GIMPLE_PHI
)
5129 if (!vec_stmt
) /* transformation not required. */
5131 STMT_VINFO_TYPE (stmt_info
) = induc_vec_info_type
;
5132 if (vect_print_dump_info (REPORT_DETAILS
))
5133 fprintf (vect_dump
, "=== vectorizable_induction ===");
5134 vect_model_induction_cost (stmt_info
, ncopies
);
5140 if (vect_print_dump_info (REPORT_DETAILS
))
5141 fprintf (vect_dump
, "transform induction phi.");
5143 vec_def
= get_initial_def_for_induction (phi
);
5144 *vec_stmt
= SSA_NAME_DEF_STMT (vec_def
);
5148 /* Function vectorizable_live_operation.
5150 STMT computes a value that is used outside the loop. Check if
5151 it can be supported. */
5154 vectorizable_live_operation (gimple stmt
,
5155 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
5156 gimple
*vec_stmt ATTRIBUTE_UNUSED
)
5158 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
5159 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
5160 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5166 enum vect_def_type dt
;
5167 enum tree_code code
;
5168 enum gimple_rhs_class rhs_class
;
5170 gcc_assert (STMT_VINFO_LIVE_P (stmt_info
));
5172 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_reduction_def
)
5175 if (!is_gimple_assign (stmt
))
5178 if (TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
5181 /* FORNOW. CHECKME. */
5182 if (nested_in_vect_loop_p (loop
, stmt
))
5185 code
= gimple_assign_rhs_code (stmt
);
5186 op_type
= TREE_CODE_LENGTH (code
);
5187 rhs_class
= get_gimple_rhs_class (code
);
5188 gcc_assert (rhs_class
!= GIMPLE_UNARY_RHS
|| op_type
== unary_op
);
5189 gcc_assert (rhs_class
!= GIMPLE_BINARY_RHS
|| op_type
== binary_op
);
5191 /* FORNOW: support only if all uses are invariant. This means
5192 that the scalar operations can remain in place, unvectorized.
5193 The original last scalar value that they compute will be used. */
5195 for (i
= 0; i
< op_type
; i
++)
5197 if (rhs_class
== GIMPLE_SINGLE_RHS
)
5198 op
= TREE_OPERAND (gimple_op (stmt
, 1), i
);
5200 op
= gimple_op (stmt
, i
+ 1);
5202 && !vect_is_simple_use (op
, stmt
, loop_vinfo
, NULL
, &def_stmt
, &def
,
5205 if (vect_print_dump_info (REPORT_DETAILS
))
5206 fprintf (vect_dump
, "use not simple.");
5210 if (dt
!= vect_external_def
&& dt
!= vect_constant_def
)
5214 /* No transformation is required for the cases we currently support. */
5218 /* Kill any debug uses outside LOOP of SSA names defined in STMT. */
5221 vect_loop_kill_debug_uses (struct loop
*loop
, gimple stmt
)
5223 ssa_op_iter op_iter
;
5224 imm_use_iterator imm_iter
;
5225 def_operand_p def_p
;
5228 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
5230 FOR_EACH_IMM_USE_STMT (ustmt
, imm_iter
, DEF_FROM_PTR (def_p
))
5234 if (!is_gimple_debug (ustmt
))
5237 bb
= gimple_bb (ustmt
);
5239 if (!flow_bb_inside_loop_p (loop
, bb
))
5241 if (gimple_debug_bind_p (ustmt
))
5243 if (vect_print_dump_info (REPORT_DETAILS
))
5244 fprintf (vect_dump
, "killing debug use");
5246 gimple_debug_bind_reset_value (ustmt
);
5247 update_stmt (ustmt
);
5256 /* Function vect_transform_loop.
5258 The analysis phase has determined that the loop is vectorizable.
5259 Vectorize the loop - created vectorized stmts to replace the scalar
5260 stmts in the loop, and update the loop exit condition. */
5263 vect_transform_loop (loop_vec_info loop_vinfo
)
5265 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5266 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
5267 int nbbs
= loop
->num_nodes
;
5268 gimple_stmt_iterator si
;
5271 int vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
5273 bool slp_scheduled
= false;
5274 unsigned int nunits
;
5275 gimple stmt
, pattern_stmt
;
5276 gimple_seq pattern_def_seq
= NULL
;
5277 gimple_stmt_iterator pattern_def_si
= gsi_none ();
5278 bool transform_pattern_stmt
= false;
5279 bool check_profitability
;
5282 if (vect_print_dump_info (REPORT_DETAILS
))
5283 fprintf (vect_dump
, "=== vec_transform_loop ===");
5285 /* Use the more conservative vectorization threshold. If the number
5286 of iterations is constant assume the cost check has been performed
5287 by our caller. If the threshold makes all loops profitable that
5288 run at least the vectorization factor number of times checking
5289 is pointless, too. */
5290 th
= ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND
)
5291 * LOOP_VINFO_VECT_FACTOR (loop_vinfo
)) - 1);
5292 th
= MAX (th
, LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo
));
5293 if (th
>= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) - 1
5294 && !LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
5296 if (vect_print_dump_info (REPORT_COST
))
5298 "Profitability threshold is %d loop iterations.", th
);
5299 check_profitability
= true;
5302 /* Peel the loop if there are data refs with unknown alignment.
5303 Only one data ref with unknown store is allowed. */
5305 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
))
5307 vect_do_peeling_for_alignment (loop_vinfo
, th
, check_profitability
);
5308 check_profitability
= false;
5311 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
5312 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
5314 vect_loop_versioning (loop_vinfo
, th
, check_profitability
);
5315 check_profitability
= false;
5318 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
5319 compile time constant), or it is a constant that doesn't divide by the
5320 vectorization factor, then an epilog loop needs to be created.
5321 We therefore duplicate the loop: the original loop will be vectorized,
5322 and will compute the first (n/VF) iterations. The second copy of the loop
5323 will remain scalar and will compute the remaining (n%VF) iterations.
5324 (VF is the vectorization factor). */
5326 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
5327 || (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
5328 && LOOP_VINFO_INT_NITERS (loop_vinfo
) % vectorization_factor
!= 0)
5329 || LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
))
5330 vect_do_peeling_for_loop_bound (loop_vinfo
, &ratio
,
5331 th
, check_profitability
);
5333 ratio
= build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo
)),
5334 LOOP_VINFO_INT_NITERS (loop_vinfo
) / vectorization_factor
);
5336 /* 1) Make sure the loop header has exactly two entries
5337 2) Make sure we have a preheader basic block. */
5339 gcc_assert (EDGE_COUNT (loop
->header
->preds
) == 2);
5341 split_edge (loop_preheader_edge (loop
));
5343 /* FORNOW: the vectorizer supports only loops which body consist
5344 of one basic block (header + empty latch). When the vectorizer will
5345 support more involved loop forms, the order by which the BBs are
5346 traversed need to be reconsidered. */
5348 for (i
= 0; i
< nbbs
; i
++)
5350 basic_block bb
= bbs
[i
];
5351 stmt_vec_info stmt_info
;
5354 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
5356 phi
= gsi_stmt (si
);
5357 if (vect_print_dump_info (REPORT_DETAILS
))
5359 fprintf (vect_dump
, "------>vectorizing phi: ");
5360 print_gimple_stmt (vect_dump
, phi
, 0, TDF_SLIM
);
5362 stmt_info
= vinfo_for_stmt (phi
);
5366 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
5367 vect_loop_kill_debug_uses (loop
, phi
);
5369 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
5370 && !STMT_VINFO_LIVE_P (stmt_info
))
5373 if ((TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
))
5374 != (unsigned HOST_WIDE_INT
) vectorization_factor
)
5375 && vect_print_dump_info (REPORT_DETAILS
))
5376 fprintf (vect_dump
, "multiple-types.");
5378 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
5380 if (vect_print_dump_info (REPORT_DETAILS
))
5381 fprintf (vect_dump
, "transform phi.");
5382 vect_transform_stmt (phi
, NULL
, NULL
, NULL
, NULL
);
5386 pattern_stmt
= NULL
;
5387 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
) || transform_pattern_stmt
;)
5391 if (transform_pattern_stmt
)
5392 stmt
= pattern_stmt
;
5394 stmt
= gsi_stmt (si
);
5396 if (vect_print_dump_info (REPORT_DETAILS
))
5398 fprintf (vect_dump
, "------>vectorizing statement: ");
5399 print_gimple_stmt (vect_dump
, stmt
, 0, TDF_SLIM
);
5402 stmt_info
= vinfo_for_stmt (stmt
);
5404 /* vector stmts created in the outer-loop during vectorization of
5405 stmts in an inner-loop may not have a stmt_info, and do not
5406 need to be vectorized. */
5413 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
5414 vect_loop_kill_debug_uses (loop
, stmt
);
5416 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
5417 && !STMT_VINFO_LIVE_P (stmt_info
))
5419 if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
5420 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
5421 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
5422 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
5424 stmt
= pattern_stmt
;
5425 stmt_info
= vinfo_for_stmt (stmt
);
5433 else if (STMT_VINFO_IN_PATTERN_P (stmt_info
)
5434 && (pattern_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
))
5435 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt
))
5436 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt
))))
5437 transform_pattern_stmt
= true;
5439 /* If pattern statement has def stmts, vectorize them too. */
5440 if (is_pattern_stmt_p (stmt_info
))
5442 if (pattern_def_seq
== NULL
)
5444 pattern_def_seq
= STMT_VINFO_PATTERN_DEF_SEQ (stmt_info
);
5445 pattern_def_si
= gsi_start (pattern_def_seq
);
5447 else if (!gsi_end_p (pattern_def_si
))
5448 gsi_next (&pattern_def_si
);
5449 if (pattern_def_seq
!= NULL
)
5451 gimple pattern_def_stmt
= NULL
;
5452 stmt_vec_info pattern_def_stmt_info
= NULL
;
5454 while (!gsi_end_p (pattern_def_si
))
5456 pattern_def_stmt
= gsi_stmt (pattern_def_si
);
5457 pattern_def_stmt_info
5458 = vinfo_for_stmt (pattern_def_stmt
);
5459 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info
)
5460 || STMT_VINFO_LIVE_P (pattern_def_stmt_info
))
5462 gsi_next (&pattern_def_si
);
5465 if (!gsi_end_p (pattern_def_si
))
5467 if (vect_print_dump_info (REPORT_DETAILS
))
5469 fprintf (vect_dump
, "==> vectorizing pattern def"
5471 print_gimple_stmt (vect_dump
, pattern_def_stmt
, 0,
5475 stmt
= pattern_def_stmt
;
5476 stmt_info
= pattern_def_stmt_info
;
5480 pattern_def_si
= gsi_none ();
5481 transform_pattern_stmt
= false;
5485 transform_pattern_stmt
= false;
5488 gcc_assert (STMT_VINFO_VECTYPE (stmt_info
));
5489 nunits
= (unsigned int) TYPE_VECTOR_SUBPARTS (
5490 STMT_VINFO_VECTYPE (stmt_info
));
5491 if (!STMT_SLP_TYPE (stmt_info
)
5492 && nunits
!= (unsigned int) vectorization_factor
5493 && vect_print_dump_info (REPORT_DETAILS
))
5494 /* For SLP VF is set according to unrolling factor, and not to
5495 vector size, hence for SLP this print is not valid. */
5496 fprintf (vect_dump
, "multiple-types.");
5498 /* SLP. Schedule all the SLP instances when the first SLP stmt is
5500 if (STMT_SLP_TYPE (stmt_info
))
5504 slp_scheduled
= true;
5506 if (vect_print_dump_info (REPORT_DETAILS
))
5507 fprintf (vect_dump
, "=== scheduling SLP instances ===");
5509 vect_schedule_slp (loop_vinfo
, NULL
);
5512 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
5513 if (!vinfo_for_stmt (stmt
) || PURE_SLP_STMT (stmt_info
))
5515 if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
5517 pattern_def_seq
= NULL
;
5524 /* -------- vectorize statement ------------ */
5525 if (vect_print_dump_info (REPORT_DETAILS
))
5526 fprintf (vect_dump
, "transform statement.");
5528 grouped_store
= false;
5529 is_store
= vect_transform_stmt (stmt
, &si
, &grouped_store
, NULL
, NULL
);
5532 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
5534 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
5535 interleaving chain was completed - free all the stores in
5538 vect_remove_stores (GROUP_FIRST_ELEMENT (stmt_info
));
5543 /* Free the attached stmt_vec_info and remove the stmt. */
5544 gimple store
= gsi_stmt (si
);
5545 free_stmt_vec_info (store
);
5546 unlink_stmt_vdef (store
);
5547 gsi_remove (&si
, true);
5548 release_defs (store
);
5553 if (!transform_pattern_stmt
&& gsi_end_p (pattern_def_si
))
5555 pattern_def_seq
= NULL
;
5561 slpeel_make_loop_iterate_ntimes (loop
, ratio
);
5563 /* The memory tags and pointers in vectorized statements need to
5564 have their SSA forms updated. FIXME, why can't this be delayed
5565 until all the loops have been transformed? */
5566 update_ssa (TODO_update_ssa
);
5568 if (vect_print_dump_info (REPORT_VECTORIZED_LOCATIONS
))
5569 fprintf (vect_dump
, "LOOP VECTORIZED.");
5570 if (loop
->inner
&& vect_print_dump_info (REPORT_VECTORIZED_LOCATIONS
))
5571 fprintf (vect_dump
, "OUTER LOOP VECTORIZED.");