2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
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 "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
34 #include "cfglayout.h"
40 #include "tree-chrec.h"
41 #include "tree-scalar-evolution.h"
42 #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) - "UNITS_PER_SIMD_WORD". Targets that can
127 support different sizes of vectors, for now will need to specify one value
128 for "UNITS_PER_SIMD_WORD". More flexibility will be added in the future.
130 Since we only vectorize operations which vector form can be
131 expressed using existing tree codes, to verify that an operation is
132 supported, the vectorizer checks the relevant optab at the relevant
133 machine_mode (e.g, optab_handler (add_optab, V8HImode)->insn_code). If
134 the value found is CODE_FOR_nothing, then there's no target support, and
135 we can't vectorize the stmt.
137 For additional information on this project see:
138 http://gcc.gnu.org/projects/tree-ssa/vectorization.html
141 /* Function vect_determine_vectorization_factor
143 Determine the vectorization factor (VF). VF is the number of data elements
144 that are operated upon in parallel in a single iteration of the vectorized
145 loop. For example, when vectorizing a loop that operates on 4byte elements,
146 on a target with vector size (VS) 16byte, the VF is set to 4, since 4
147 elements can fit in a single vector register.
149 We currently support vectorization of loops in which all types operated upon
150 are of the same size. Therefore this function currently sets VF according to
151 the size of the types operated upon, and fails if there are multiple sizes
154 VF is also the factor by which the loop iterations are strip-mined, e.g.:
161 for (i=0; i<N; i+=VF){
162 a[i:VF] = b[i:VF] + c[i:VF];
167 vect_determine_vectorization_factor (loop_vec_info loop_vinfo
)
169 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
170 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
171 int nbbs
= loop
->num_nodes
;
172 gimple_stmt_iterator si
;
173 unsigned int vectorization_factor
= 0;
178 stmt_vec_info stmt_info
;
182 if (vect_print_dump_info (REPORT_DETAILS
))
183 fprintf (vect_dump
, "=== vect_determine_vectorization_factor ===");
185 for (i
= 0; i
< nbbs
; i
++)
187 basic_block bb
= bbs
[i
];
189 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
192 stmt_info
= vinfo_for_stmt (phi
);
193 if (vect_print_dump_info (REPORT_DETAILS
))
195 fprintf (vect_dump
, "==> examining phi: ");
196 print_gimple_stmt (vect_dump
, phi
, 0, TDF_SLIM
);
199 gcc_assert (stmt_info
);
201 if (STMT_VINFO_RELEVANT_P (stmt_info
))
203 gcc_assert (!STMT_VINFO_VECTYPE (stmt_info
));
204 scalar_type
= TREE_TYPE (PHI_RESULT (phi
));
206 if (vect_print_dump_info (REPORT_DETAILS
))
208 fprintf (vect_dump
, "get vectype for scalar type: ");
209 print_generic_expr (vect_dump
, scalar_type
, TDF_SLIM
);
212 vectype
= get_vectype_for_scalar_type (scalar_type
);
215 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
218 "not vectorized: unsupported data-type ");
219 print_generic_expr (vect_dump
, scalar_type
, TDF_SLIM
);
223 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
225 if (vect_print_dump_info (REPORT_DETAILS
))
227 fprintf (vect_dump
, "vectype: ");
228 print_generic_expr (vect_dump
, vectype
, TDF_SLIM
);
231 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
232 if (vect_print_dump_info (REPORT_DETAILS
))
233 fprintf (vect_dump
, "nunits = %d", nunits
);
235 if (!vectorization_factor
236 || (nunits
> vectorization_factor
))
237 vectorization_factor
= nunits
;
241 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
243 gimple stmt
= gsi_stmt (si
);
244 stmt_info
= vinfo_for_stmt (stmt
);
246 if (vect_print_dump_info (REPORT_DETAILS
))
248 fprintf (vect_dump
, "==> examining statement: ");
249 print_gimple_stmt (vect_dump
, stmt
, 0, TDF_SLIM
);
252 gcc_assert (stmt_info
);
254 /* skip stmts which do not need to be vectorized. */
255 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
256 && !STMT_VINFO_LIVE_P (stmt_info
))
258 if (vect_print_dump_info (REPORT_DETAILS
))
259 fprintf (vect_dump
, "skip.");
263 if (gimple_get_lhs (stmt
) == NULL_TREE
)
265 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
267 fprintf (vect_dump
, "not vectorized: irregular stmt.");
268 print_gimple_stmt (vect_dump
, stmt
, 0, TDF_SLIM
);
273 if (VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt
))))
275 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
277 fprintf (vect_dump
, "not vectorized: vector stmt in loop:");
278 print_gimple_stmt (vect_dump
, stmt
, 0, TDF_SLIM
);
283 if (STMT_VINFO_VECTYPE (stmt_info
))
285 /* The only case when a vectype had been already set is for stmts
286 that contain a dataref, or for "pattern-stmts" (stmts generated
287 by the vectorizer to represent/replace a certain idiom). */
288 gcc_assert (STMT_VINFO_DATA_REF (stmt_info
)
289 || is_pattern_stmt_p (stmt_info
));
290 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
294 gcc_assert (!STMT_VINFO_DATA_REF (stmt_info
)
295 && !is_pattern_stmt_p (stmt_info
));
297 scalar_type
= vect_get_smallest_scalar_type (stmt
, &dummy
,
299 if (vect_print_dump_info (REPORT_DETAILS
))
301 fprintf (vect_dump
, "get vectype for scalar type: ");
302 print_generic_expr (vect_dump
, scalar_type
, TDF_SLIM
);
305 vectype
= get_vectype_for_scalar_type (scalar_type
);
308 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
311 "not vectorized: unsupported data-type ");
312 print_generic_expr (vect_dump
, scalar_type
, TDF_SLIM
);
316 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
319 if (vect_print_dump_info (REPORT_DETAILS
))
321 fprintf (vect_dump
, "vectype: ");
322 print_generic_expr (vect_dump
, vectype
, TDF_SLIM
);
325 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
326 if (vect_print_dump_info (REPORT_DETAILS
))
327 fprintf (vect_dump
, "nunits = %d", nunits
);
329 if (!vectorization_factor
330 || (nunits
> vectorization_factor
))
331 vectorization_factor
= nunits
;
336 /* TODO: Analyze cost. Decide if worth while to vectorize. */
337 if (vect_print_dump_info (REPORT_DETAILS
))
338 fprintf (vect_dump
, "vectorization factor = %d", vectorization_factor
);
339 if (vectorization_factor
<= 1)
341 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
342 fprintf (vect_dump
, "not vectorized: unsupported data-type");
345 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
351 /* Function vect_is_simple_iv_evolution.
353 FORNOW: A simple evolution of an induction variables in the loop is
354 considered a polynomial evolution with constant step. */
357 vect_is_simple_iv_evolution (unsigned loop_nb
, tree access_fn
, tree
* init
,
362 tree evolution_part
= evolution_part_in_loop_num (access_fn
, loop_nb
);
364 /* When there is no evolution in this loop, the evolution function
366 if (evolution_part
== NULL_TREE
)
369 /* When the evolution is a polynomial of degree >= 2
370 the evolution function is not "simple". */
371 if (tree_is_chrec (evolution_part
))
374 step_expr
= evolution_part
;
375 init_expr
= unshare_expr (initial_condition_in_loop_num (access_fn
, loop_nb
));
377 if (vect_print_dump_info (REPORT_DETAILS
))
379 fprintf (vect_dump
, "step: ");
380 print_generic_expr (vect_dump
, step_expr
, TDF_SLIM
);
381 fprintf (vect_dump
, ", init: ");
382 print_generic_expr (vect_dump
, init_expr
, TDF_SLIM
);
388 if (TREE_CODE (step_expr
) != INTEGER_CST
)
390 if (vect_print_dump_info (REPORT_DETAILS
))
391 fprintf (vect_dump
, "step unknown.");
398 /* Function vect_analyze_scalar_cycles_1.
400 Examine the cross iteration def-use cycles of scalar variables
401 in LOOP. LOOP_VINFO represents the loop that is now being
402 considered for vectorization (can be LOOP, or an outer-loop
406 vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo
, struct loop
*loop
)
408 basic_block bb
= loop
->header
;
410 VEC(gimple
,heap
) *worklist
= VEC_alloc (gimple
, heap
, 64);
411 gimple_stmt_iterator gsi
;
414 if (vect_print_dump_info (REPORT_DETAILS
))
415 fprintf (vect_dump
, "=== vect_analyze_scalar_cycles ===");
417 /* First - identify all inductions. Reduction detection assumes that all the
418 inductions have been identified, therefore, this order must not be
420 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
422 gimple phi
= gsi_stmt (gsi
);
423 tree access_fn
= NULL
;
424 tree def
= PHI_RESULT (phi
);
425 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (phi
);
427 if (vect_print_dump_info (REPORT_DETAILS
))
429 fprintf (vect_dump
, "Analyze phi: ");
430 print_gimple_stmt (vect_dump
, phi
, 0, TDF_SLIM
);
433 /* Skip virtual phi's. The data dependences that are associated with
434 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
435 if (!is_gimple_reg (SSA_NAME_VAR (def
)))
438 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_unknown_def_type
;
440 /* Analyze the evolution function. */
441 access_fn
= analyze_scalar_evolution (loop
, def
);
442 if (access_fn
&& vect_print_dump_info (REPORT_DETAILS
))
444 fprintf (vect_dump
, "Access function of PHI: ");
445 print_generic_expr (vect_dump
, access_fn
, TDF_SLIM
);
449 || !vect_is_simple_iv_evolution (loop
->num
, access_fn
, &dumy
, &dumy
))
451 VEC_safe_push (gimple
, heap
, worklist
, phi
);
455 if (vect_print_dump_info (REPORT_DETAILS
))
456 fprintf (vect_dump
, "Detected induction.");
457 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_induction_def
;
461 /* Second - identify all reductions and nested cycles. */
462 while (VEC_length (gimple
, worklist
) > 0)
464 gimple phi
= VEC_pop (gimple
, worklist
);
465 tree def
= PHI_RESULT (phi
);
466 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (phi
);
470 if (vect_print_dump_info (REPORT_DETAILS
))
472 fprintf (vect_dump
, "Analyze phi: ");
473 print_gimple_stmt (vect_dump
, phi
, 0, TDF_SLIM
);
476 gcc_assert (is_gimple_reg (SSA_NAME_VAR (def
)));
477 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo
) == vect_unknown_def_type
);
479 nested_cycle
= (loop
!= LOOP_VINFO_LOOP (loop_vinfo
));
480 reduc_stmt
= vect_is_simple_reduction (loop_vinfo
, phi
, !nested_cycle
,
486 if (vect_print_dump_info (REPORT_DETAILS
))
487 fprintf (vect_dump
, "Detected double reduction.");
489 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_double_reduction_def
;
490 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
491 vect_double_reduction_def
;
497 if (vect_print_dump_info (REPORT_DETAILS
))
498 fprintf (vect_dump
, "Detected vectorizable nested cycle.");
500 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_nested_cycle
;
501 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
506 if (vect_print_dump_info (REPORT_DETAILS
))
507 fprintf (vect_dump
, "Detected reduction.");
509 STMT_VINFO_DEF_TYPE (stmt_vinfo
) = vect_reduction_def
;
510 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt
)) =
516 if (vect_print_dump_info (REPORT_DETAILS
))
517 fprintf (vect_dump
, "Unknown def-use cycle pattern.");
520 VEC_free (gimple
, heap
, worklist
);
524 /* Function vect_analyze_scalar_cycles.
526 Examine the cross iteration def-use cycles of scalar variables, by
527 analyzing the loop-header PHIs of scalar variables; Classify each
528 cycle as one of the following: invariant, induction, reduction, unknown.
529 We do that for the loop represented by LOOP_VINFO, and also to its
530 inner-loop, if exists.
531 Examples for scalar cycles:
546 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo
)
548 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
550 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
);
552 /* When vectorizing an outer-loop, the inner-loop is executed sequentially.
553 Reductions in such inner-loop therefore have different properties than
554 the reductions in the nest that gets vectorized:
555 1. When vectorized, they are executed in the same order as in the original
556 scalar loop, so we can't change the order of computation when
558 2. FIXME: Inner-loop reductions can be used in the inner-loop, so the
559 current checks are too strict. */
562 vect_analyze_scalar_cycles_1 (loop_vinfo
, loop
->inner
);
565 /* Function vect_get_loop_niters.
567 Determine how many iterations the loop is executed.
568 If an expression that represents the number of iterations
569 can be constructed, place it in NUMBER_OF_ITERATIONS.
570 Return the loop exit condition. */
573 vect_get_loop_niters (struct loop
*loop
, tree
*number_of_iterations
)
577 if (vect_print_dump_info (REPORT_DETAILS
))
578 fprintf (vect_dump
, "=== get_loop_niters ===");
580 niters
= number_of_exit_cond_executions (loop
);
582 if (niters
!= NULL_TREE
583 && niters
!= chrec_dont_know
)
585 *number_of_iterations
= niters
;
587 if (vect_print_dump_info (REPORT_DETAILS
))
589 fprintf (vect_dump
, "==> get_loop_niters:" );
590 print_generic_expr (vect_dump
, *number_of_iterations
, TDF_SLIM
);
594 return get_loop_exit_condition (loop
);
598 /* Function bb_in_loop_p
600 Used as predicate for dfs order traversal of the loop bbs. */
603 bb_in_loop_p (const_basic_block bb
, const void *data
)
605 const struct loop
*const loop
= (const struct loop
*)data
;
606 if (flow_bb_inside_loop_p (loop
, bb
))
612 /* Function new_loop_vec_info.
614 Create and initialize a new loop_vec_info struct for LOOP, as well as
615 stmt_vec_info structs for all the stmts in LOOP. */
618 new_loop_vec_info (struct loop
*loop
)
622 gimple_stmt_iterator si
;
623 unsigned int i
, nbbs
;
625 res
= (loop_vec_info
) xcalloc (1, sizeof (struct _loop_vec_info
));
626 LOOP_VINFO_LOOP (res
) = loop
;
628 bbs
= get_loop_body (loop
);
630 /* Create/Update stmt_info for all stmts in the loop. */
631 for (i
= 0; i
< loop
->num_nodes
; i
++)
633 basic_block bb
= bbs
[i
];
635 /* BBs in a nested inner-loop will have been already processed (because
636 we will have called vect_analyze_loop_form for any nested inner-loop).
637 Therefore, for stmts in an inner-loop we just want to update the
638 STMT_VINFO_LOOP_VINFO field of their stmt_info to point to the new
639 loop_info of the outer-loop we are currently considering to vectorize
640 (instead of the loop_info of the inner-loop).
641 For stmts in other BBs we need to create a stmt_info from scratch. */
642 if (bb
->loop_father
!= loop
)
645 gcc_assert (loop
->inner
&& bb
->loop_father
== loop
->inner
);
646 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
648 gimple phi
= gsi_stmt (si
);
649 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
650 loop_vec_info inner_loop_vinfo
=
651 STMT_VINFO_LOOP_VINFO (stmt_info
);
652 gcc_assert (loop
->inner
== LOOP_VINFO_LOOP (inner_loop_vinfo
));
653 STMT_VINFO_LOOP_VINFO (stmt_info
) = res
;
655 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
657 gimple stmt
= gsi_stmt (si
);
658 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
659 loop_vec_info inner_loop_vinfo
=
660 STMT_VINFO_LOOP_VINFO (stmt_info
);
661 gcc_assert (loop
->inner
== LOOP_VINFO_LOOP (inner_loop_vinfo
));
662 STMT_VINFO_LOOP_VINFO (stmt_info
) = res
;
667 /* bb in current nest. */
668 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
670 gimple phi
= gsi_stmt (si
);
671 gimple_set_uid (phi
, 0);
672 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, res
, NULL
));
675 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
677 gimple stmt
= gsi_stmt (si
);
678 gimple_set_uid (stmt
, 0);
679 set_vinfo_for_stmt (stmt
, new_stmt_vec_info (stmt
, res
, NULL
));
684 /* CHECKME: We want to visit all BBs before their successors (except for
685 latch blocks, for which this assertion wouldn't hold). In the simple
686 case of the loop forms we allow, a dfs order of the BBs would the same
687 as reversed postorder traversal, so we are safe. */
690 bbs
= XCNEWVEC (basic_block
, loop
->num_nodes
);
691 nbbs
= dfs_enumerate_from (loop
->header
, 0, bb_in_loop_p
,
692 bbs
, loop
->num_nodes
, loop
);
693 gcc_assert (nbbs
== loop
->num_nodes
);
695 LOOP_VINFO_BBS (res
) = bbs
;
696 LOOP_VINFO_NITERS (res
) = NULL
;
697 LOOP_VINFO_NITERS_UNCHANGED (res
) = NULL
;
698 LOOP_VINFO_COST_MODEL_MIN_ITERS (res
) = 0;
699 LOOP_VINFO_VECTORIZABLE_P (res
) = 0;
700 LOOP_PEELING_FOR_ALIGNMENT (res
) = 0;
701 LOOP_VINFO_VECT_FACTOR (res
) = 0;
702 LOOP_VINFO_DATAREFS (res
) = VEC_alloc (data_reference_p
, heap
, 10);
703 LOOP_VINFO_DDRS (res
) = VEC_alloc (ddr_p
, heap
, 10 * 10);
704 LOOP_VINFO_UNALIGNED_DR (res
) = NULL
;
705 LOOP_VINFO_MAY_MISALIGN_STMTS (res
) =
706 VEC_alloc (gimple
, heap
,
707 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS
));
708 LOOP_VINFO_MAY_ALIAS_DDRS (res
) =
709 VEC_alloc (ddr_p
, heap
,
710 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS
));
711 LOOP_VINFO_STRIDED_STORES (res
) = VEC_alloc (gimple
, heap
, 10);
712 LOOP_VINFO_SLP_INSTANCES (res
) = VEC_alloc (slp_instance
, heap
, 10);
713 LOOP_VINFO_SLP_UNROLLING_FACTOR (res
) = 1;
719 /* Function destroy_loop_vec_info.
721 Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
722 stmts in the loop. */
725 destroy_loop_vec_info (loop_vec_info loop_vinfo
, bool clean_stmts
)
730 gimple_stmt_iterator si
;
732 VEC (slp_instance
, heap
) *slp_instances
;
733 slp_instance instance
;
738 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
740 bbs
= LOOP_VINFO_BBS (loop_vinfo
);
741 nbbs
= loop
->num_nodes
;
745 free (LOOP_VINFO_BBS (loop_vinfo
));
746 free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo
));
747 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo
));
748 VEC_free (gimple
, heap
, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
));
755 for (j
= 0; j
< nbbs
; j
++)
757 basic_block bb
= bbs
[j
];
758 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
759 free_stmt_vec_info (gsi_stmt (si
));
761 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); )
763 gimple stmt
= gsi_stmt (si
);
764 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
768 /* Check if this is a "pattern stmt" (introduced by the
769 vectorizer during the pattern recognition pass). */
770 bool remove_stmt_p
= false;
771 gimple orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
774 stmt_vec_info orig_stmt_info
= vinfo_for_stmt (orig_stmt
);
776 && STMT_VINFO_IN_PATTERN_P (orig_stmt_info
))
777 remove_stmt_p
= true;
780 /* Free stmt_vec_info. */
781 free_stmt_vec_info (stmt
);
783 /* Remove dead "pattern stmts". */
785 gsi_remove (&si
, true);
791 free (LOOP_VINFO_BBS (loop_vinfo
));
792 free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo
));
793 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo
));
794 VEC_free (gimple
, heap
, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
));
795 VEC_free (ddr_p
, heap
, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
));
796 slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
797 for (j
= 0; VEC_iterate (slp_instance
, slp_instances
, j
, instance
); j
++)
798 vect_free_slp_instance (instance
);
800 VEC_free (slp_instance
, heap
, LOOP_VINFO_SLP_INSTANCES (loop_vinfo
));
801 VEC_free (gimple
, heap
, LOOP_VINFO_STRIDED_STORES (loop_vinfo
));
808 /* Function vect_analyze_loop_1.
810 Apply a set of analyses on LOOP, and create a loop_vec_info struct
811 for it. The different analyses will record information in the
812 loop_vec_info struct. This is a subset of the analyses applied in
813 vect_analyze_loop, to be applied on an inner-loop nested in the loop
814 that is now considered for (outer-loop) vectorization. */
817 vect_analyze_loop_1 (struct loop
*loop
)
819 loop_vec_info loop_vinfo
;
821 if (vect_print_dump_info (REPORT_DETAILS
))
822 fprintf (vect_dump
, "===== analyze_loop_nest_1 =====");
824 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
826 loop_vinfo
= vect_analyze_loop_form (loop
);
829 if (vect_print_dump_info (REPORT_DETAILS
))
830 fprintf (vect_dump
, "bad inner-loop form.");
838 /* Function vect_analyze_loop_form.
840 Verify that certain CFG restrictions hold, including:
841 - the loop has a pre-header
842 - the loop has a single entry and exit
843 - the loop exit condition is simple enough, and the number of iterations
844 can be analyzed (a countable loop). */
847 vect_analyze_loop_form (struct loop
*loop
)
849 loop_vec_info loop_vinfo
;
851 tree number_of_iterations
= NULL
;
852 loop_vec_info inner_loop_vinfo
= NULL
;
854 if (vect_print_dump_info (REPORT_DETAILS
))
855 fprintf (vect_dump
, "=== vect_analyze_loop_form ===");
857 /* Different restrictions apply when we are considering an inner-most loop,
858 vs. an outer (nested) loop.
859 (FORNOW. May want to relax some of these restrictions in the future). */
863 /* Inner-most loop. We currently require that the number of BBs is
864 exactly 2 (the header and latch). Vectorizable inner-most loops
875 if (loop
->num_nodes
!= 2)
877 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
878 fprintf (vect_dump
, "not vectorized: control flow in loop.");
882 if (empty_block_p (loop
->header
))
884 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
885 fprintf (vect_dump
, "not vectorized: empty loop.");
891 struct loop
*innerloop
= loop
->inner
;
894 /* Nested loop. We currently require that the loop is doubly-nested,
895 contains a single inner loop, and the number of BBs is exactly 5.
896 Vectorizable outer-loops look like this:
908 The inner-loop has the properties expected of inner-most loops
909 as described above. */
911 if ((loop
->inner
)->inner
|| (loop
->inner
)->next
)
913 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
914 fprintf (vect_dump
, "not vectorized: multiple nested loops.");
918 /* Analyze the inner-loop. */
919 inner_loop_vinfo
= vect_analyze_loop_1 (loop
->inner
);
920 if (!inner_loop_vinfo
)
922 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
923 fprintf (vect_dump
, "not vectorized: Bad inner loop.");
927 if (!expr_invariant_in_loop_p (loop
,
928 LOOP_VINFO_NITERS (inner_loop_vinfo
)))
930 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
932 "not vectorized: inner-loop count not invariant.");
933 destroy_loop_vec_info (inner_loop_vinfo
, true);
937 if (loop
->num_nodes
!= 5)
939 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
940 fprintf (vect_dump
, "not vectorized: control flow in loop.");
941 destroy_loop_vec_info (inner_loop_vinfo
, true);
945 gcc_assert (EDGE_COUNT (innerloop
->header
->preds
) == 2);
946 entryedge
= EDGE_PRED (innerloop
->header
, 0);
947 if (EDGE_PRED (innerloop
->header
, 0)->src
== innerloop
->latch
)
948 entryedge
= EDGE_PRED (innerloop
->header
, 1);
950 if (entryedge
->src
!= loop
->header
951 || !single_exit (innerloop
)
952 || single_exit (innerloop
)->dest
!= EDGE_PRED (loop
->latch
, 0)->src
)
954 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
955 fprintf (vect_dump
, "not vectorized: unsupported outerloop form.");
956 destroy_loop_vec_info (inner_loop_vinfo
, true);
960 if (vect_print_dump_info (REPORT_DETAILS
))
961 fprintf (vect_dump
, "Considering outer-loop vectorization.");
964 if (!single_exit (loop
)
965 || EDGE_COUNT (loop
->header
->preds
) != 2)
967 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
969 if (!single_exit (loop
))
970 fprintf (vect_dump
, "not vectorized: multiple exits.");
971 else if (EDGE_COUNT (loop
->header
->preds
) != 2)
972 fprintf (vect_dump
, "not vectorized: too many incoming edges.");
974 if (inner_loop_vinfo
)
975 destroy_loop_vec_info (inner_loop_vinfo
, true);
979 /* We assume that the loop exit condition is at the end of the loop. i.e,
980 that the loop is represented as a do-while (with a proper if-guard
981 before the loop if needed), where the loop header contains all the
982 executable statements, and the latch is empty. */
983 if (!empty_block_p (loop
->latch
)
984 || !gimple_seq_empty_p (phi_nodes (loop
->latch
)))
986 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
987 fprintf (vect_dump
, "not vectorized: unexpected loop form.");
988 if (inner_loop_vinfo
)
989 destroy_loop_vec_info (inner_loop_vinfo
, true);
993 /* Make sure there exists a single-predecessor exit bb: */
994 if (!single_pred_p (single_exit (loop
)->dest
))
996 edge e
= single_exit (loop
);
997 if (!(e
->flags
& EDGE_ABNORMAL
))
999 split_loop_exit_edge (e
);
1000 if (vect_print_dump_info (REPORT_DETAILS
))
1001 fprintf (vect_dump
, "split exit edge.");
1005 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1006 fprintf (vect_dump
, "not vectorized: abnormal loop exit edge.");
1007 if (inner_loop_vinfo
)
1008 destroy_loop_vec_info (inner_loop_vinfo
, true);
1013 loop_cond
= vect_get_loop_niters (loop
, &number_of_iterations
);
1016 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1017 fprintf (vect_dump
, "not vectorized: complicated exit condition.");
1018 if (inner_loop_vinfo
)
1019 destroy_loop_vec_info (inner_loop_vinfo
, true);
1023 if (!number_of_iterations
)
1025 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1027 "not vectorized: number of iterations cannot be computed.");
1028 if (inner_loop_vinfo
)
1029 destroy_loop_vec_info (inner_loop_vinfo
, true);
1033 if (chrec_contains_undetermined (number_of_iterations
))
1035 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
))
1036 fprintf (vect_dump
, "Infinite number of iterations.");
1037 if (inner_loop_vinfo
)
1038 destroy_loop_vec_info (inner_loop_vinfo
, true);
1042 if (!NITERS_KNOWN_P (number_of_iterations
))
1044 if (vect_print_dump_info (REPORT_DETAILS
))
1046 fprintf (vect_dump
, "Symbolic number of iterations is ");
1047 print_generic_expr (vect_dump
, number_of_iterations
, TDF_DETAILS
);
1050 else if (TREE_INT_CST_LOW (number_of_iterations
) == 0)
1052 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1053 fprintf (vect_dump
, "not vectorized: number of iterations = 0.");
1054 if (inner_loop_vinfo
)
1055 destroy_loop_vec_info (inner_loop_vinfo
, false);
1059 loop_vinfo
= new_loop_vec_info (loop
);
1060 LOOP_VINFO_NITERS (loop_vinfo
) = number_of_iterations
;
1061 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo
) = number_of_iterations
;
1063 STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond
)) = loop_exit_ctrl_vec_info_type
;
1065 /* CHECKME: May want to keep it around it in the future. */
1066 if (inner_loop_vinfo
)
1067 destroy_loop_vec_info (inner_loop_vinfo
, false);
1069 gcc_assert (!loop
->aux
);
1070 loop
->aux
= loop_vinfo
;
1075 /* Function vect_analyze_loop_operations.
1077 Scan the loop stmts and make sure they are all vectorizable. */
1080 vect_analyze_loop_operations (loop_vec_info loop_vinfo
)
1082 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1083 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1084 int nbbs
= loop
->num_nodes
;
1085 gimple_stmt_iterator si
;
1086 unsigned int vectorization_factor
= 0;
1089 stmt_vec_info stmt_info
;
1090 bool need_to_vectorize
= false;
1091 int min_profitable_iters
;
1092 int min_scalar_loop_bound
;
1094 bool only_slp_in_loop
= true, ok
;
1096 if (vect_print_dump_info (REPORT_DETAILS
))
1097 fprintf (vect_dump
, "=== vect_analyze_loop_operations ===");
1099 gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo
));
1100 vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1102 for (i
= 0; i
< nbbs
; i
++)
1104 basic_block bb
= bbs
[i
];
1106 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
1108 phi
= gsi_stmt (si
);
1111 stmt_info
= vinfo_for_stmt (phi
);
1112 if (vect_print_dump_info (REPORT_DETAILS
))
1114 fprintf (vect_dump
, "examining phi: ");
1115 print_gimple_stmt (vect_dump
, phi
, 0, TDF_SLIM
);
1118 if (! is_loop_header_bb_p (bb
))
1120 /* inner-loop loop-closed exit phi in outer-loop vectorization
1121 (i.e. a phi in the tail of the outer-loop).
1122 FORNOW: we currently don't support the case that these phis
1123 are not used in the outerloop (unless it is double reduction,
1124 i.e., this phi is vect_reduction_def), cause this case
1125 requires to actually do something here. */
1126 if ((!STMT_VINFO_RELEVANT_P (stmt_info
)
1127 || STMT_VINFO_LIVE_P (stmt_info
))
1128 && STMT_VINFO_DEF_TYPE (stmt_info
)
1129 != vect_double_reduction_def
)
1131 if (vect_print_dump_info (REPORT_DETAILS
))
1133 "Unsupported loop-closed phi in outer-loop.");
1139 gcc_assert (stmt_info
);
1141 if (STMT_VINFO_LIVE_P (stmt_info
))
1143 /* FORNOW: not yet supported. */
1144 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1145 fprintf (vect_dump
, "not vectorized: value used after loop.");
1149 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_used_in_scope
1150 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_induction_def
)
1152 /* A scalar-dependence cycle that we don't support. */
1153 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1154 fprintf (vect_dump
, "not vectorized: scalar dependence cycle.");
1158 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1160 need_to_vectorize
= true;
1161 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
1162 ok
= vectorizable_induction (phi
, NULL
, NULL
);
1167 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1170 "not vectorized: relevant phi not supported: ");
1171 print_gimple_stmt (vect_dump
, phi
, 0, TDF_SLIM
);
1177 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1179 gimple stmt
= gsi_stmt (si
);
1180 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1182 gcc_assert (stmt_info
);
1184 if (!vect_analyze_stmt (stmt
, &need_to_vectorize
, NULL
))
1187 if ((STMT_VINFO_RELEVANT_P (stmt_info
)
1188 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info
)))
1189 && !PURE_SLP_STMT (stmt_info
))
1191 /* STMT needs both SLP and loop-based vectorization. */
1192 only_slp_in_loop
= false;
1196 /* All operations in the loop are either irrelevant (deal with loop
1197 control, or dead), or only used outside the loop and can be moved
1198 out of the loop (e.g. invariants, inductions). The loop can be
1199 optimized away by scalar optimizations. We're better off not
1200 touching this loop. */
1201 if (!need_to_vectorize
)
1203 if (vect_print_dump_info (REPORT_DETAILS
))
1205 "All the computation can be taken out of the loop.");
1206 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1208 "not vectorized: redundant loop. no profit to vectorize.");
1212 /* If all the stmts in the loop can be SLPed, we perform only SLP, and
1213 vectorization factor of the loop is the unrolling factor required by the
1214 SLP instances. If that unrolling factor is 1, we say, that we perform
1215 pure SLP on loop - cross iteration parallelism is not exploited. */
1216 if (only_slp_in_loop
)
1217 vectorization_factor
= LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
);
1219 vectorization_factor
= least_common_multiple (vectorization_factor
,
1220 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo
));
1222 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
1224 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1225 && vect_print_dump_info (REPORT_DETAILS
))
1227 "vectorization_factor = %d, niters = " HOST_WIDE_INT_PRINT_DEC
,
1228 vectorization_factor
, LOOP_VINFO_INT_NITERS (loop_vinfo
));
1230 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1231 && (LOOP_VINFO_INT_NITERS (loop_vinfo
) < vectorization_factor
))
1233 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1234 fprintf (vect_dump
, "not vectorized: iteration count too small.");
1235 if (vect_print_dump_info (REPORT_DETAILS
))
1236 fprintf (vect_dump
,"not vectorized: iteration count smaller than "
1237 "vectorization factor.");
1241 /* Analyze cost. Decide if worth while to vectorize. */
1243 /* Once VF is set, SLP costs should be updated since the number of created
1244 vector stmts depends on VF. */
1245 vect_update_slp_costs_according_to_vf (loop_vinfo
);
1247 min_profitable_iters
= vect_estimate_min_profitable_iters (loop_vinfo
);
1248 LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo
) = min_profitable_iters
;
1250 if (min_profitable_iters
< 0)
1252 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1253 fprintf (vect_dump
, "not vectorized: vectorization not profitable.");
1254 if (vect_print_dump_info (REPORT_DETAILS
))
1255 fprintf (vect_dump
, "not vectorized: vector version will never be "
1260 min_scalar_loop_bound
= ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND
)
1261 * vectorization_factor
) - 1);
1263 /* Use the cost model only if it is more conservative than user specified
1266 th
= (unsigned) min_scalar_loop_bound
;
1267 if (min_profitable_iters
1268 && (!min_scalar_loop_bound
1269 || min_profitable_iters
> min_scalar_loop_bound
))
1270 th
= (unsigned) min_profitable_iters
;
1272 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1273 && LOOP_VINFO_INT_NITERS (loop_vinfo
) <= th
)
1275 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1276 fprintf (vect_dump
, "not vectorized: vectorization not "
1278 if (vect_print_dump_info (REPORT_DETAILS
))
1279 fprintf (vect_dump
, "not vectorized: iteration count smaller than "
1280 "user specified loop bound parameter or minimum "
1281 "profitable iterations (whichever is more conservative).");
1285 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
1286 || LOOP_VINFO_INT_NITERS (loop_vinfo
) % vectorization_factor
!= 0
1287 || LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
))
1289 if (vect_print_dump_info (REPORT_DETAILS
))
1290 fprintf (vect_dump
, "epilog loop required.");
1291 if (!vect_can_advance_ivs_p (loop_vinfo
))
1293 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1295 "not vectorized: can't create epilog loop 1.");
1298 if (!slpeel_can_duplicate_loop_p (loop
, single_exit (loop
)))
1300 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS
))
1302 "not vectorized: can't create epilog loop 2.");
1311 /* Function vect_analyze_loop.
1313 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1314 for it. The different analyses will record information in the
1315 loop_vec_info struct. */
1317 vect_analyze_loop (struct loop
*loop
)
1320 loop_vec_info loop_vinfo
;
1322 if (vect_print_dump_info (REPORT_DETAILS
))
1323 fprintf (vect_dump
, "===== analyze_loop_nest =====");
1325 if (loop_outer (loop
)
1326 && loop_vec_info_for_loop (loop_outer (loop
))
1327 && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop
))))
1329 if (vect_print_dump_info (REPORT_DETAILS
))
1330 fprintf (vect_dump
, "outer-loop already vectorized.");
1334 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
1336 loop_vinfo
= vect_analyze_loop_form (loop
);
1339 if (vect_print_dump_info (REPORT_DETAILS
))
1340 fprintf (vect_dump
, "bad loop form.");
1344 /* Find all data references in the loop (which correspond to vdefs/vuses)
1345 and analyze their evolution in the loop.
1347 FORNOW: Handle only simple, array references, which
1348 alignment can be forced, and aligned pointer-references. */
1350 ok
= vect_analyze_data_refs (loop_vinfo
, NULL
);
1353 if (vect_print_dump_info (REPORT_DETAILS
))
1354 fprintf (vect_dump
, "bad data references.");
1355 destroy_loop_vec_info (loop_vinfo
, true);
1359 /* Classify all cross-iteration scalar data-flow cycles.
1360 Cross-iteration cycles caused by virtual phis are analyzed separately. */
1362 vect_analyze_scalar_cycles (loop_vinfo
);
1364 vect_pattern_recog (loop_vinfo
);
1366 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
1368 ok
= vect_mark_stmts_to_be_vectorized (loop_vinfo
);
1371 if (vect_print_dump_info (REPORT_DETAILS
))
1372 fprintf (vect_dump
, "unexpected pattern.");
1373 destroy_loop_vec_info (loop_vinfo
, true);
1377 /* Analyze the alignment of the data-refs in the loop.
1378 Fail if a data reference is found that cannot be vectorized. */
1380 ok
= vect_analyze_data_refs_alignment (loop_vinfo
, NULL
);
1383 if (vect_print_dump_info (REPORT_DETAILS
))
1384 fprintf (vect_dump
, "bad data alignment.");
1385 destroy_loop_vec_info (loop_vinfo
, true);
1389 ok
= vect_determine_vectorization_factor (loop_vinfo
);
1392 if (vect_print_dump_info (REPORT_DETAILS
))
1393 fprintf (vect_dump
, "can't determine vectorization factor.");
1394 destroy_loop_vec_info (loop_vinfo
, true);
1398 /* Analyze data dependences between the data-refs in the loop.
1399 FORNOW: fail at the first data dependence that we encounter. */
1401 ok
= vect_analyze_data_ref_dependences (loop_vinfo
, NULL
);
1404 if (vect_print_dump_info (REPORT_DETAILS
))
1405 fprintf (vect_dump
, "bad data dependence.");
1406 destroy_loop_vec_info (loop_vinfo
, true);
1410 /* Analyze the access patterns of the data-refs in the loop (consecutive,
1411 complex, etc.). FORNOW: Only handle consecutive access pattern. */
1413 ok
= vect_analyze_data_ref_accesses (loop_vinfo
, NULL
);
1416 if (vect_print_dump_info (REPORT_DETAILS
))
1417 fprintf (vect_dump
, "bad data access.");
1418 destroy_loop_vec_info (loop_vinfo
, true);
1422 /* Prune the list of ddrs to be tested at run-time by versioning for alias.
1423 It is important to call pruning after vect_analyze_data_ref_accesses,
1424 since we use grouping information gathered by interleaving analysis. */
1425 ok
= vect_prune_runtime_alias_test_list (loop_vinfo
);
1428 if (vect_print_dump_info (REPORT_DETAILS
))
1429 fprintf (vect_dump
, "too long list of versioning for alias "
1431 destroy_loop_vec_info (loop_vinfo
, true);
1435 /* Check the SLP opportunities in the loop, analyze and build SLP trees. */
1436 ok
= vect_analyze_slp (loop_vinfo
, NULL
);
1439 /* Decide which possible SLP instances to SLP. */
1440 vect_make_slp_decision (loop_vinfo
);
1442 /* Find stmts that need to be both vectorized and SLPed. */
1443 vect_detect_hybrid_slp (loop_vinfo
);
1446 /* This pass will decide on using loop versioning and/or loop peeling in
1447 order to enhance the alignment of data references in the loop. */
1449 ok
= vect_enhance_data_refs_alignment (loop_vinfo
);
1452 if (vect_print_dump_info (REPORT_DETAILS
))
1453 fprintf (vect_dump
, "bad data alignment.");
1454 destroy_loop_vec_info (loop_vinfo
, true);
1458 /* Scan all the operations in the loop and make sure they are
1461 ok
= vect_analyze_loop_operations (loop_vinfo
);
1464 if (vect_print_dump_info (REPORT_DETAILS
))
1465 fprintf (vect_dump
, "bad operation or unsupported loop bound.");
1466 destroy_loop_vec_info (loop_vinfo
, true);
1470 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
) = 1;
1476 /* Function reduction_code_for_scalar_code
1479 CODE - tree_code of a reduction operations.
1482 REDUC_CODE - the corresponding tree-code to be used to reduce the
1483 vector of partial results into a single scalar result (which
1484 will also reside in a vector) or ERROR_MARK if the operation is
1485 a supported reduction operation, but does not have such tree-code.
1487 Return FALSE if CODE currently cannot be vectorized as reduction. */
1490 reduction_code_for_scalar_code (enum tree_code code
,
1491 enum tree_code
*reduc_code
)
1496 *reduc_code
= REDUC_MAX_EXPR
;
1500 *reduc_code
= REDUC_MIN_EXPR
;
1504 *reduc_code
= REDUC_PLUS_EXPR
;
1512 *reduc_code
= ERROR_MARK
;
1521 /* Error reporting helper for vect_is_simple_reduction below. GIMPLE statement
1522 STMT is printed with a message MSG. */
1525 report_vect_op (gimple stmt
, const char *msg
)
1527 fprintf (vect_dump
, "%s", msg
);
1528 print_gimple_stmt (vect_dump
, stmt
, 0, TDF_SLIM
);
1532 /* Function vect_is_simple_reduction
1534 (1) Detect a cross-iteration def-use cycle that represents a simple
1535 reduction computation. We look for the following pattern:
1540 a2 = operation (a3, a1)
1543 1. operation is commutative and associative and it is safe to
1544 change the order of the computation (if CHECK_REDUCTION is true)
1545 2. no uses for a2 in the loop (a2 is used out of the loop)
1546 3. no uses of a1 in the loop besides the reduction operation.
1548 Condition 1 is tested here.
1549 Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
1551 (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
1552 nested cycles, if CHECK_REDUCTION is false.
1554 (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
1558 inner loop (def of a3)
1563 vect_is_simple_reduction (loop_vec_info loop_info
, gimple phi
,
1564 bool check_reduction
, bool *double_reduc
)
1566 struct loop
*loop
= (gimple_bb (phi
))->loop_father
;
1567 struct loop
*vect_loop
= LOOP_VINFO_LOOP (loop_info
);
1568 edge latch_e
= loop_latch_edge (loop
);
1569 tree loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
1570 gimple def_stmt
, def1
= NULL
, def2
= NULL
;
1571 enum tree_code code
;
1572 tree op1
, op2
, op3
= NULL_TREE
, op4
= NULL_TREE
;
1576 imm_use_iterator imm_iter
;
1577 use_operand_p use_p
;
1580 *double_reduc
= false;
1582 /* If CHECK_REDUCTION is true, we assume inner-most loop vectorization,
1583 otherwise, we assume outer loop vectorization. */
1584 gcc_assert ((check_reduction
&& loop
== vect_loop
)
1585 || (!check_reduction
&& flow_loop_nested_p (vect_loop
, loop
)));
1587 name
= PHI_RESULT (phi
);
1589 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
1591 gimple use_stmt
= USE_STMT (use_p
);
1592 if (is_gimple_debug (use_stmt
))
1594 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
))
1595 && vinfo_for_stmt (use_stmt
)
1596 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt
)))
1600 if (vect_print_dump_info (REPORT_DETAILS
))
1601 fprintf (vect_dump
, "reduction used in loop.");
1606 if (TREE_CODE (loop_arg
) != SSA_NAME
)
1608 if (vect_print_dump_info (REPORT_DETAILS
))
1610 fprintf (vect_dump
, "reduction: not ssa_name: ");
1611 print_generic_expr (vect_dump
, loop_arg
, TDF_SLIM
);
1616 def_stmt
= SSA_NAME_DEF_STMT (loop_arg
);
1619 if (vect_print_dump_info (REPORT_DETAILS
))
1620 fprintf (vect_dump
, "reduction: no def_stmt.");
1624 if (!is_gimple_assign (def_stmt
) && gimple_code (def_stmt
) != GIMPLE_PHI
)
1626 if (vect_print_dump_info (REPORT_DETAILS
))
1627 print_gimple_stmt (vect_dump
, def_stmt
, 0, TDF_SLIM
);
1631 if (is_gimple_assign (def_stmt
))
1633 name
= gimple_assign_lhs (def_stmt
);
1638 name
= PHI_RESULT (def_stmt
);
1643 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
1645 gimple use_stmt
= USE_STMT (use_p
);
1646 if (is_gimple_debug (use_stmt
))
1648 if (flow_bb_inside_loop_p (loop
, gimple_bb (use_stmt
))
1649 && vinfo_for_stmt (use_stmt
)
1650 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt
)))
1654 if (vect_print_dump_info (REPORT_DETAILS
))
1655 fprintf (vect_dump
, "reduction used in loop.");
1660 /* If DEF_STMT is a phi node itself, we expect it to have a single argument
1661 defined in the inner loop. */
1664 op1
= PHI_ARG_DEF (def_stmt
, 0);
1666 if (gimple_phi_num_args (def_stmt
) != 1
1667 || TREE_CODE (op1
) != SSA_NAME
)
1669 if (vect_print_dump_info (REPORT_DETAILS
))
1670 fprintf (vect_dump
, "unsupported phi node definition.");
1675 def1
= SSA_NAME_DEF_STMT (op1
);
1676 if (flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
1678 && flow_bb_inside_loop_p (loop
->inner
, gimple_bb (def1
))
1679 && is_gimple_assign (def1
))
1681 if (vect_print_dump_info (REPORT_DETAILS
))
1682 report_vect_op (def_stmt
, "detected double reduction: ");
1684 *double_reduc
= true;
1691 code
= gimple_assign_rhs_code (def_stmt
);
1694 && (!commutative_tree_code (code
) || !associative_tree_code (code
)))
1696 if (vect_print_dump_info (REPORT_DETAILS
))
1697 report_vect_op (def_stmt
, "reduction: not commutative/associative: ");
1701 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
1703 if (code
!= COND_EXPR
)
1705 if (vect_print_dump_info (REPORT_DETAILS
))
1706 report_vect_op (def_stmt
, "reduction: not binary operation: ");
1711 op3
= TREE_OPERAND (gimple_assign_rhs1 (def_stmt
), 0);
1712 if (COMPARISON_CLASS_P (op3
))
1714 op4
= TREE_OPERAND (op3
, 1);
1715 op3
= TREE_OPERAND (op3
, 0);
1718 op1
= TREE_OPERAND (gimple_assign_rhs1 (def_stmt
), 1);
1719 op2
= TREE_OPERAND (gimple_assign_rhs1 (def_stmt
), 2);
1721 if (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op2
) != SSA_NAME
)
1723 if (vect_print_dump_info (REPORT_DETAILS
))
1724 report_vect_op (def_stmt
, "reduction: uses not ssa_names: ");
1731 op1
= gimple_assign_rhs1 (def_stmt
);
1732 op2
= gimple_assign_rhs2 (def_stmt
);
1734 if (TREE_CODE (op1
) != SSA_NAME
|| TREE_CODE (op2
) != SSA_NAME
)
1736 if (vect_print_dump_info (REPORT_DETAILS
))
1737 report_vect_op (def_stmt
, "reduction: uses not ssa_names: ");
1743 type
= TREE_TYPE (gimple_assign_lhs (def_stmt
));
1744 if ((TREE_CODE (op1
) == SSA_NAME
1745 && !types_compatible_p (type
,TREE_TYPE (op1
)))
1746 || (TREE_CODE (op2
) == SSA_NAME
1747 && !types_compatible_p (type
, TREE_TYPE (op2
)))
1748 || (op3
&& TREE_CODE (op3
) == SSA_NAME
1749 && !types_compatible_p (type
, TREE_TYPE (op3
)))
1750 || (op4
&& TREE_CODE (op4
) == SSA_NAME
1751 && !types_compatible_p (type
, TREE_TYPE (op4
))))
1753 if (vect_print_dump_info (REPORT_DETAILS
))
1755 fprintf (vect_dump
, "reduction: multiple types: operation type: ");
1756 print_generic_expr (vect_dump
, type
, TDF_SLIM
);
1757 fprintf (vect_dump
, ", operands types: ");
1758 print_generic_expr (vect_dump
, TREE_TYPE (op1
), TDF_SLIM
);
1759 fprintf (vect_dump
, ",");
1760 print_generic_expr (vect_dump
, TREE_TYPE (op2
), TDF_SLIM
);
1763 fprintf (vect_dump
, ",");
1764 print_generic_expr (vect_dump
, TREE_TYPE (op3
), TDF_SLIM
);
1769 fprintf (vect_dump
, ",");
1770 print_generic_expr (vect_dump
, TREE_TYPE (op4
), TDF_SLIM
);
1777 /* Check that it's ok to change the order of the computation.
1778 Generally, when vectorizing a reduction we change the order of the
1779 computation. This may change the behavior of the program in some
1780 cases, so we need to check that this is ok. One exception is when
1781 vectorizing an outer-loop: the inner-loop is executed sequentially,
1782 and therefore vectorizing reductions in the inner-loop during
1783 outer-loop vectorization is safe. */
1785 /* CHECKME: check for !flag_finite_math_only too? */
1786 if (SCALAR_FLOAT_TYPE_P (type
) && !flag_associative_math
1789 /* Changing the order of operations changes the semantics. */
1790 if (vect_print_dump_info (REPORT_DETAILS
))
1791 report_vect_op (def_stmt
, "reduction: unsafe fp math optimization: ");
1794 else if (INTEGRAL_TYPE_P (type
) && TYPE_OVERFLOW_TRAPS (type
)
1797 /* Changing the order of operations changes the semantics. */
1798 if (vect_print_dump_info (REPORT_DETAILS
))
1799 report_vect_op (def_stmt
, "reduction: unsafe int math optimization: ");
1802 else if (SAT_FIXED_POINT_TYPE_P (type
) && check_reduction
)
1804 /* Changing the order of operations changes the semantics. */
1805 if (vect_print_dump_info (REPORT_DETAILS
))
1806 report_vect_op (def_stmt
,
1807 "reduction: unsafe fixed-point math optimization: ");
1811 /* Reduction is safe. We're dealing with one of the following:
1812 1) integer arithmetic and no trapv
1813 2) floating point arithmetic, and special flags permit this optimization
1814 3) nested cycle (i.e., outer loop vectorization). */
1815 if (TREE_CODE (op1
) == SSA_NAME
)
1816 def1
= SSA_NAME_DEF_STMT (op1
);
1818 if (TREE_CODE (op2
) == SSA_NAME
)
1819 def2
= SSA_NAME_DEF_STMT (op2
);
1821 if (code
!= COND_EXPR
1822 && (!def1
|| !def2
|| gimple_nop_p (def1
) || gimple_nop_p (def2
)))
1824 if (vect_print_dump_info (REPORT_DETAILS
))
1825 report_vect_op (def_stmt
, "reduction: no defs for operands: ");
1829 /* Check that one def is the reduction def, defined by PHI,
1830 the other def is either defined in the loop ("vect_internal_def"),
1831 or it's an induction (defined by a loop-header phi-node). */
1833 if (def2
&& def2
== phi
1834 && (code
== COND_EXPR
1835 || (def1
&& flow_bb_inside_loop_p (loop
, gimple_bb (def1
))
1836 && (is_gimple_assign (def1
)
1837 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
1838 == vect_induction_def
1839 || (gimple_code (def1
) == GIMPLE_PHI
1840 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1
))
1841 == vect_internal_def
1842 && !is_loop_header_bb_p (gimple_bb (def1
)))))))
1844 if (vect_print_dump_info (REPORT_DETAILS
))
1845 report_vect_op (def_stmt
, "detected reduction: ");
1848 else if (def1
&& def1
== phi
1849 && (code
== COND_EXPR
1850 || (def2
&& flow_bb_inside_loop_p (loop
, gimple_bb (def2
))
1851 && (is_gimple_assign (def2
)
1852 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
1853 == vect_induction_def
1854 || (gimple_code (def2
) == GIMPLE_PHI
1855 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2
))
1856 == vect_internal_def
1857 && !is_loop_header_bb_p (gimple_bb (def2
)))))))
1859 if (check_reduction
)
1861 /* Swap operands (just for simplicity - so that the rest of the code
1862 can assume that the reduction variable is always the last (second)
1864 if (vect_print_dump_info (REPORT_DETAILS
))
1865 report_vect_op (def_stmt
,
1866 "detected reduction: need to swap operands: ");
1868 swap_tree_operands (def_stmt
, gimple_assign_rhs1_ptr (def_stmt
),
1869 gimple_assign_rhs2_ptr (def_stmt
));
1873 if (vect_print_dump_info (REPORT_DETAILS
))
1874 report_vect_op (def_stmt
, "detected reduction: ");
1881 if (vect_print_dump_info (REPORT_DETAILS
))
1882 report_vect_op (def_stmt
, "reduction: unknown pattern: ");
1889 /* Function vect_estimate_min_profitable_iters
1891 Return the number of iterations required for the vector version of the
1892 loop to be profitable relative to the cost of the scalar version of the
1895 TODO: Take profile info into account before making vectorization
1896 decisions, if available. */
1899 vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo
)
1902 int min_profitable_iters
;
1903 int peel_iters_prologue
;
1904 int peel_iters_epilogue
;
1905 int vec_inside_cost
= 0;
1906 int vec_outside_cost
= 0;
1907 int scalar_single_iter_cost
= 0;
1908 int scalar_outside_cost
= 0;
1909 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1910 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1911 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1912 int nbbs
= loop
->num_nodes
;
1913 int byte_misalign
= LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
);
1914 int peel_guard_costs
= 0;
1915 int innerloop_iters
= 0, factor
;
1916 VEC (slp_instance
, heap
) *slp_instances
;
1917 slp_instance instance
;
1919 /* Cost model disabled. */
1920 if (!flag_vect_cost_model
)
1922 if (vect_print_dump_info (REPORT_COST
))
1923 fprintf (vect_dump
, "cost model disabled.");
1927 /* Requires loop versioning tests to handle misalignment. */
1928 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
))
1930 /* FIXME: Make cost depend on complexity of individual check. */
1932 VEC_length (gimple
, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
));
1933 if (vect_print_dump_info (REPORT_COST
))
1934 fprintf (vect_dump
, "cost model: Adding cost of checks for loop "
1935 "versioning to treat misalignment.\n");
1938 /* Requires loop versioning with alias checks. */
1939 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
1941 /* FIXME: Make cost depend on complexity of individual check. */
1943 VEC_length (ddr_p
, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
));
1944 if (vect_print_dump_info (REPORT_COST
))
1945 fprintf (vect_dump
, "cost model: Adding cost of checks for loop "
1946 "versioning aliasing.\n");
1949 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
1950 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
1951 vec_outside_cost
+= TARG_COND_TAKEN_BRANCH_COST
;
1953 /* Count statements in scalar loop. Using this as scalar cost for a single
1956 TODO: Add outer loop support.
1958 TODO: Consider assigning different costs to different scalar
1963 innerloop_iters
= 50; /* FIXME */
1965 for (i
= 0; i
< nbbs
; i
++)
1967 gimple_stmt_iterator si
;
1968 basic_block bb
= bbs
[i
];
1970 if (bb
->loop_father
== loop
->inner
)
1971 factor
= innerloop_iters
;
1975 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1977 gimple stmt
= gsi_stmt (si
);
1978 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1979 /* Skip stmts that are not vectorized inside the loop. */
1980 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
1981 && (!STMT_VINFO_LIVE_P (stmt_info
)
1982 || STMT_VINFO_DEF_TYPE (stmt_info
) != vect_reduction_def
))
1984 scalar_single_iter_cost
+= cost_for_stmt (stmt
) * factor
;
1985 vec_inside_cost
+= STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info
) * factor
;
1986 /* FIXME: for stmts in the inner-loop in outer-loop vectorization,
1987 some of the "outside" costs are generated inside the outer-loop. */
1988 vec_outside_cost
+= STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info
);
1992 /* Add additional cost for the peeled instructions in prologue and epilogue
1995 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
1996 at compile-time - we assume it's vf/2 (the worst would be vf-1).
1998 TODO: Build an expression that represents peel_iters for prologue and
1999 epilogue to be used in a run-time test. */
2001 if (byte_misalign
< 0)
2003 peel_iters_prologue
= vf
/2;
2004 if (vect_print_dump_info (REPORT_COST
))
2005 fprintf (vect_dump
, "cost model: "
2006 "prologue peel iters set to vf/2.");
2008 /* If peeling for alignment is unknown, loop bound of main loop becomes
2010 peel_iters_epilogue
= vf
/2;
2011 if (vect_print_dump_info (REPORT_COST
))
2012 fprintf (vect_dump
, "cost model: "
2013 "epilogue peel iters set to vf/2 because "
2014 "peeling for alignment is unknown .");
2016 /* If peeled iterations are unknown, count a taken branch and a not taken
2017 branch per peeled loop. Even if scalar loop iterations are known,
2018 vector iterations are not known since peeled prologue iterations are
2019 not known. Hence guards remain the same. */
2020 peel_guard_costs
+= 2 * (TARG_COND_TAKEN_BRANCH_COST
2021 + TARG_COND_NOT_TAKEN_BRANCH_COST
);
2027 struct data_reference
*dr
= LOOP_VINFO_UNALIGNED_DR (loop_vinfo
);
2028 int element_size
= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr
))));
2029 tree vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr
)));
2030 int nelements
= TYPE_VECTOR_SUBPARTS (vectype
);
2032 peel_iters_prologue
= nelements
- (byte_misalign
/ element_size
);
2035 peel_iters_prologue
= 0;
2037 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
2039 peel_iters_epilogue
= vf
/2;
2040 if (vect_print_dump_info (REPORT_COST
))
2041 fprintf (vect_dump
, "cost model: "
2042 "epilogue peel iters set to vf/2 because "
2043 "loop iterations are unknown .");
2045 /* If peeled iterations are known but number of scalar loop
2046 iterations are unknown, count a taken branch per peeled loop. */
2047 peel_guard_costs
+= 2 * TARG_COND_TAKEN_BRANCH_COST
;
2052 int niters
= LOOP_VINFO_INT_NITERS (loop_vinfo
);
2053 peel_iters_prologue
= niters
< peel_iters_prologue
?
2054 niters
: peel_iters_prologue
;
2055 peel_iters_epilogue
= (niters
- peel_iters_prologue
) % vf
;
2059 vec_outside_cost
+= (peel_iters_prologue
* scalar_single_iter_cost
)
2060 + (peel_iters_epilogue
* scalar_single_iter_cost
)
2063 /* FORNOW: The scalar outside cost is incremented in one of the
2066 1. The vectorizer checks for alignment and aliasing and generates
2067 a condition that allows dynamic vectorization. A cost model
2068 check is ANDED with the versioning condition. Hence scalar code
2069 path now has the added cost of the versioning check.
2071 if (cost > th & versioning_check)
2074 Hence run-time scalar is incremented by not-taken branch cost.
2076 2. The vectorizer then checks if a prologue is required. If the
2077 cost model check was not done before during versioning, it has to
2078 be done before the prologue check.
2081 prologue = scalar_iters
2086 if (prologue == num_iters)
2089 Hence the run-time scalar cost is incremented by a taken branch,
2090 plus a not-taken branch, plus a taken branch cost.
2092 3. The vectorizer then checks if an epilogue is required. If the
2093 cost model check was not done before during prologue check, it
2094 has to be done with the epilogue check.
2100 if (prologue == num_iters)
2103 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
2106 Hence the run-time scalar cost should be incremented by 2 taken
2109 TODO: The back end may reorder the BBS's differently and reverse
2110 conditions/branch directions. Change the estimates below to
2111 something more reasonable. */
2113 /* If the number of iterations is known and we do not do versioning, we can
2114 decide whether to vectorize at compile time. Hence the scalar version
2115 do not carry cost model guard costs. */
2116 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
2117 || LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2118 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2120 /* Cost model check occurs at versioning. */
2121 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
2122 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2123 scalar_outside_cost
+= TARG_COND_NOT_TAKEN_BRANCH_COST
;
2126 /* Cost model check occurs at prologue generation. */
2127 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
) < 0)
2128 scalar_outside_cost
+= 2 * TARG_COND_TAKEN_BRANCH_COST
2129 + TARG_COND_NOT_TAKEN_BRANCH_COST
;
2130 /* Cost model check occurs at epilogue generation. */
2132 scalar_outside_cost
+= 2 * TARG_COND_TAKEN_BRANCH_COST
;
2136 /* Add SLP costs. */
2137 slp_instances
= LOOP_VINFO_SLP_INSTANCES (loop_vinfo
);
2138 for (i
= 0; VEC_iterate (slp_instance
, slp_instances
, i
, instance
); i
++)
2140 vec_outside_cost
+= SLP_INSTANCE_OUTSIDE_OF_LOOP_COST (instance
);
2141 vec_inside_cost
+= SLP_INSTANCE_INSIDE_OF_LOOP_COST (instance
);
2144 /* Calculate number of iterations required to make the vector version
2145 profitable, relative to the loop bodies only. The following condition
2147 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
2149 SIC = scalar iteration cost, VIC = vector iteration cost,
2150 VOC = vector outside cost, VF = vectorization factor,
2151 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
2152 SOC = scalar outside cost for run time cost model check. */
2154 if ((scalar_single_iter_cost
* vf
) > vec_inside_cost
)
2156 if (vec_outside_cost
<= 0)
2157 min_profitable_iters
= 1;
2160 min_profitable_iters
= ((vec_outside_cost
- scalar_outside_cost
) * vf
2161 - vec_inside_cost
* peel_iters_prologue
2162 - vec_inside_cost
* peel_iters_epilogue
)
2163 / ((scalar_single_iter_cost
* vf
)
2166 if ((scalar_single_iter_cost
* vf
* min_profitable_iters
)
2167 <= ((vec_inside_cost
* min_profitable_iters
)
2168 + ((vec_outside_cost
- scalar_outside_cost
) * vf
)))
2169 min_profitable_iters
++;
2172 /* vector version will never be profitable. */
2175 if (vect_print_dump_info (REPORT_COST
))
2176 fprintf (vect_dump
, "cost model: the vector iteration cost = %d "
2177 "divided by the scalar iteration cost = %d "
2178 "is greater or equal to the vectorization factor = %d.",
2179 vec_inside_cost
, scalar_single_iter_cost
, vf
);
2183 if (vect_print_dump_info (REPORT_COST
))
2185 fprintf (vect_dump
, "Cost model analysis: \n");
2186 fprintf (vect_dump
, " Vector inside of loop cost: %d\n",
2188 fprintf (vect_dump
, " Vector outside of loop cost: %d\n",
2190 fprintf (vect_dump
, " Scalar iteration cost: %d\n",
2191 scalar_single_iter_cost
);
2192 fprintf (vect_dump
, " Scalar outside cost: %d\n", scalar_outside_cost
);
2193 fprintf (vect_dump
, " prologue iterations: %d\n",
2194 peel_iters_prologue
);
2195 fprintf (vect_dump
, " epilogue iterations: %d\n",
2196 peel_iters_epilogue
);
2197 fprintf (vect_dump
, " Calculated minimum iters for profitability: %d\n",
2198 min_profitable_iters
);
2201 min_profitable_iters
=
2202 min_profitable_iters
< vf
? vf
: min_profitable_iters
;
2204 /* Because the condition we create is:
2205 if (niters <= min_profitable_iters)
2206 then skip the vectorized loop. */
2207 min_profitable_iters
--;
2209 if (vect_print_dump_info (REPORT_COST
))
2210 fprintf (vect_dump
, " Profitability threshold = %d\n",
2211 min_profitable_iters
);
2213 return min_profitable_iters
;
2217 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
2218 functions. Design better to avoid maintenance issues. */
2220 /* Function vect_model_reduction_cost.
2222 Models cost for a reduction operation, including the vector ops
2223 generated within the strip-mine loop, the initial definition before
2224 the loop, and the epilogue code that must be generated. */
2227 vect_model_reduction_cost (stmt_vec_info stmt_info
, enum tree_code reduc_code
,
2231 enum tree_code code
;
2234 gimple stmt
, orig_stmt
;
2236 enum machine_mode mode
;
2237 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
2238 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2241 /* Cost of reduction op inside loop. */
2242 STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info
) += ncopies
* TARG_VEC_STMT_COST
;
2244 stmt
= STMT_VINFO_STMT (stmt_info
);
2246 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
2248 case GIMPLE_SINGLE_RHS
:
2249 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
)) == ternary_op
);
2250 reduction_op
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 2);
2252 case GIMPLE_UNARY_RHS
:
2253 reduction_op
= gimple_assign_rhs1 (stmt
);
2255 case GIMPLE_BINARY_RHS
:
2256 reduction_op
= gimple_assign_rhs2 (stmt
);
2262 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
2265 if (vect_print_dump_info (REPORT_COST
))
2267 fprintf (vect_dump
, "unsupported data-type ");
2268 print_generic_expr (vect_dump
, TREE_TYPE (reduction_op
), TDF_SLIM
);
2273 mode
= TYPE_MODE (vectype
);
2274 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
2277 orig_stmt
= STMT_VINFO_STMT (stmt_info
);
2279 code
= gimple_assign_rhs_code (orig_stmt
);
2281 /* Add in cost for initial definition. */
2282 outer_cost
+= TARG_SCALAR_TO_VEC_COST
;
2284 /* Determine cost of epilogue code.
2286 We have a reduction operator that will reduce the vector in one statement.
2287 Also requires scalar extract. */
2289 if (!nested_in_vect_loop_p (loop
, orig_stmt
))
2291 if (reduc_code
!= ERROR_MARK
)
2292 outer_cost
+= TARG_VEC_STMT_COST
+ TARG_VEC_TO_SCALAR_COST
;
2295 int vec_size_in_bits
= tree_low_cst (TYPE_SIZE (vectype
), 1);
2297 TYPE_SIZE (TREE_TYPE (gimple_assign_lhs (orig_stmt
)));
2298 int element_bitsize
= tree_low_cst (bitsize
, 1);
2299 int nelements
= vec_size_in_bits
/ element_bitsize
;
2301 optab
= optab_for_tree_code (code
, vectype
, optab_default
);
2303 /* We have a whole vector shift available. */
2304 if (VECTOR_MODE_P (mode
)
2305 && optab_handler (optab
, mode
)->insn_code
!= CODE_FOR_nothing
2306 && optab_handler (vec_shr_optab
, mode
)->insn_code
!= CODE_FOR_nothing
)
2307 /* Final reduction via vector shifts and the reduction operator. Also
2308 requires scalar extract. */
2309 outer_cost
+= ((exact_log2(nelements
) * 2) * TARG_VEC_STMT_COST
2310 + TARG_VEC_TO_SCALAR_COST
);
2312 /* Use extracts and reduction op for final reduction. For N elements,
2313 we have N extracts and N-1 reduction ops. */
2314 outer_cost
+= ((nelements
+ nelements
- 1) * TARG_VEC_STMT_COST
);
2318 STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info
) = outer_cost
;
2320 if (vect_print_dump_info (REPORT_COST
))
2321 fprintf (vect_dump
, "vect_model_reduction_cost: inside_cost = %d, "
2322 "outside_cost = %d .", STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info
),
2323 STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info
));
2329 /* Function vect_model_induction_cost.
2331 Models cost for induction operations. */
2334 vect_model_induction_cost (stmt_vec_info stmt_info
, int ncopies
)
2336 /* loop cost for vec_loop. */
2337 STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info
) = ncopies
* TARG_VEC_STMT_COST
;
2338 /* prologue cost for vec_init and vec_step. */
2339 STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info
) = 2 * TARG_SCALAR_TO_VEC_COST
;
2341 if (vect_print_dump_info (REPORT_COST
))
2342 fprintf (vect_dump
, "vect_model_induction_cost: inside_cost = %d, "
2343 "outside_cost = %d .", STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info
),
2344 STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info
));
2348 /* Function get_initial_def_for_induction
2351 STMT - a stmt that performs an induction operation in the loop.
2352 IV_PHI - the initial value of the induction variable
2355 Return a vector variable, initialized with the first VF values of
2356 the induction variable. E.g., for an iv with IV_PHI='X' and
2357 evolution S, for a vector of 4 units, we want to return:
2358 [X, X + S, X + 2*S, X + 3*S]. */
2361 get_initial_def_for_induction (gimple iv_phi
)
2363 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (iv_phi
);
2364 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
2365 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2366 tree scalar_type
= TREE_TYPE (gimple_phi_result (iv_phi
));
2369 edge pe
= loop_preheader_edge (loop
);
2370 struct loop
*iv_loop
;
2372 tree vec
, vec_init
, vec_step
, t
;
2376 gimple init_stmt
, induction_phi
, new_stmt
;
2377 tree induc_def
, vec_def
, vec_dest
;
2378 tree init_expr
, step_expr
;
2379 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2384 stmt_vec_info phi_info
= vinfo_for_stmt (iv_phi
);
2385 bool nested_in_vect_loop
= false;
2386 gimple_seq stmts
= NULL
;
2387 imm_use_iterator imm_iter
;
2388 use_operand_p use_p
;
2392 gimple_stmt_iterator si
;
2393 basic_block bb
= gimple_bb (iv_phi
);
2396 vectype
= get_vectype_for_scalar_type (scalar_type
);
2397 gcc_assert (vectype
);
2398 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
2399 ncopies
= vf
/ nunits
;
2401 gcc_assert (phi_info
);
2402 gcc_assert (ncopies
>= 1);
2404 /* Find the first insertion point in the BB. */
2405 si
= gsi_after_labels (bb
);
2407 if (INTEGRAL_TYPE_P (scalar_type
))
2408 step_expr
= build_int_cst (scalar_type
, 0);
2409 else if (POINTER_TYPE_P (scalar_type
))
2410 step_expr
= build_int_cst (sizetype
, 0);
2412 step_expr
= build_real (scalar_type
, dconst0
);
2414 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
2415 if (nested_in_vect_loop_p (loop
, iv_phi
))
2417 nested_in_vect_loop
= true;
2418 iv_loop
= loop
->inner
;
2422 gcc_assert (iv_loop
== (gimple_bb (iv_phi
))->loop_father
);
2424 latch_e
= loop_latch_edge (iv_loop
);
2425 loop_arg
= PHI_ARG_DEF_FROM_EDGE (iv_phi
, latch_e
);
2427 access_fn
= analyze_scalar_evolution (iv_loop
, PHI_RESULT (iv_phi
));
2428 gcc_assert (access_fn
);
2429 ok
= vect_is_simple_iv_evolution (iv_loop
->num
, access_fn
,
2430 &init_expr
, &step_expr
);
2432 pe
= loop_preheader_edge (iv_loop
);
2434 /* Create the vector that holds the initial_value of the induction. */
2435 if (nested_in_vect_loop
)
2437 /* iv_loop is nested in the loop to be vectorized. init_expr had already
2438 been created during vectorization of previous stmts; We obtain it from
2439 the STMT_VINFO_VEC_STMT of the defining stmt. */
2440 tree iv_def
= PHI_ARG_DEF_FROM_EDGE (iv_phi
,
2441 loop_preheader_edge (iv_loop
));
2442 vec_init
= vect_get_vec_def_for_operand (iv_def
, iv_phi
, NULL
);
2446 /* iv_loop is the loop to be vectorized. Create:
2447 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
2448 new_var
= vect_get_new_vect_var (scalar_type
, vect_scalar_var
, "var_");
2449 add_referenced_var (new_var
);
2451 new_name
= force_gimple_operand (init_expr
, &stmts
, false, new_var
);
2454 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
2455 gcc_assert (!new_bb
);
2459 t
= tree_cons (NULL_TREE
, init_expr
, t
);
2460 for (i
= 1; i
< nunits
; i
++)
2462 /* Create: new_name_i = new_name + step_expr */
2463 enum tree_code code
= POINTER_TYPE_P (scalar_type
)
2464 ? POINTER_PLUS_EXPR
: PLUS_EXPR
;
2465 init_stmt
= gimple_build_assign_with_ops (code
, new_var
,
2466 new_name
, step_expr
);
2467 new_name
= make_ssa_name (new_var
, init_stmt
);
2468 gimple_assign_set_lhs (init_stmt
, new_name
);
2470 new_bb
= gsi_insert_on_edge_immediate (pe
, init_stmt
);
2471 gcc_assert (!new_bb
);
2473 if (vect_print_dump_info (REPORT_DETAILS
))
2475 fprintf (vect_dump
, "created new init_stmt: ");
2476 print_gimple_stmt (vect_dump
, init_stmt
, 0, TDF_SLIM
);
2478 t
= tree_cons (NULL_TREE
, new_name
, t
);
2480 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
2481 vec
= build_constructor_from_list (vectype
, nreverse (t
));
2482 vec_init
= vect_init_vector (iv_phi
, vec
, vectype
, NULL
);
2486 /* Create the vector that holds the step of the induction. */
2487 if (nested_in_vect_loop
)
2488 /* iv_loop is nested in the loop to be vectorized. Generate:
2489 vec_step = [S, S, S, S] */
2490 new_name
= step_expr
;
2493 /* iv_loop is the loop to be vectorized. Generate:
2494 vec_step = [VF*S, VF*S, VF*S, VF*S] */
2495 expr
= build_int_cst (TREE_TYPE (step_expr
), vf
);
2496 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
2501 for (i
= 0; i
< nunits
; i
++)
2502 t
= tree_cons (NULL_TREE
, unshare_expr (new_name
), t
);
2503 gcc_assert (CONSTANT_CLASS_P (new_name
));
2504 stepvectype
= get_vectype_for_scalar_type (TREE_TYPE (new_name
));
2505 gcc_assert (stepvectype
);
2506 vec
= build_vector (stepvectype
, t
);
2507 vec_step
= vect_init_vector (iv_phi
, vec
, stepvectype
, NULL
);
2510 /* Create the following def-use cycle:
2515 vec_iv = PHI <vec_init, vec_loop>
2519 vec_loop = vec_iv + vec_step; */
2521 /* Create the induction-phi that defines the induction-operand. */
2522 vec_dest
= vect_get_new_vect_var (vectype
, vect_simple_var
, "vec_iv_");
2523 add_referenced_var (vec_dest
);
2524 induction_phi
= create_phi_node (vec_dest
, iv_loop
->header
);
2525 set_vinfo_for_stmt (induction_phi
,
2526 new_stmt_vec_info (induction_phi
, loop_vinfo
, NULL
));
2527 induc_def
= PHI_RESULT (induction_phi
);
2529 /* Create the iv update inside the loop */
2530 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, vec_dest
,
2531 induc_def
, vec_step
);
2532 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
2533 gimple_assign_set_lhs (new_stmt
, vec_def
);
2534 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
2535 set_vinfo_for_stmt (new_stmt
, new_stmt_vec_info (new_stmt
, loop_vinfo
,
2538 /* Set the arguments of the phi node: */
2539 add_phi_arg (induction_phi
, vec_init
, pe
, UNKNOWN_LOCATION
);
2540 add_phi_arg (induction_phi
, vec_def
, loop_latch_edge (iv_loop
),
2544 /* In case that vectorization factor (VF) is bigger than the number
2545 of elements that we can fit in a vectype (nunits), we have to generate
2546 more than one vector stmt - i.e - we need to "unroll" the
2547 vector stmt by a factor VF/nunits. For more details see documentation
2548 in vectorizable_operation. */
2552 stmt_vec_info prev_stmt_vinfo
;
2553 /* FORNOW. This restriction should be relaxed. */
2554 gcc_assert (!nested_in_vect_loop
);
2556 /* Create the vector that holds the step of the induction. */
2557 expr
= build_int_cst (TREE_TYPE (step_expr
), nunits
);
2558 new_name
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
2561 for (i
= 0; i
< nunits
; i
++)
2562 t
= tree_cons (NULL_TREE
, unshare_expr (new_name
), t
);
2563 gcc_assert (CONSTANT_CLASS_P (new_name
));
2564 vec
= build_vector (stepvectype
, t
);
2565 vec_step
= vect_init_vector (iv_phi
, vec
, stepvectype
, NULL
);
2567 vec_def
= induc_def
;
2568 prev_stmt_vinfo
= vinfo_for_stmt (induction_phi
);
2569 for (i
= 1; i
< ncopies
; i
++)
2571 /* vec_i = vec_prev + vec_step */
2572 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, vec_dest
,
2574 vec_def
= make_ssa_name (vec_dest
, new_stmt
);
2575 gimple_assign_set_lhs (new_stmt
, vec_def
);
2577 gsi_insert_before (&si
, new_stmt
, GSI_SAME_STMT
);
2578 set_vinfo_for_stmt (new_stmt
,
2579 new_stmt_vec_info (new_stmt
, loop_vinfo
, NULL
));
2580 STMT_VINFO_RELATED_STMT (prev_stmt_vinfo
) = new_stmt
;
2581 prev_stmt_vinfo
= vinfo_for_stmt (new_stmt
);
2585 if (nested_in_vect_loop
)
2587 /* Find the loop-closed exit-phi of the induction, and record
2588 the final vector of induction results: */
2590 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, loop_arg
)
2592 if (!flow_bb_inside_loop_p (iv_loop
, gimple_bb (USE_STMT (use_p
))))
2594 exit_phi
= USE_STMT (use_p
);
2600 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (exit_phi
);
2601 /* FORNOW. Currently not supporting the case that an inner-loop induction
2602 is not used in the outer-loop (i.e. only outside the outer-loop). */
2603 gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo
)
2604 && !STMT_VINFO_LIVE_P (stmt_vinfo
));
2606 STMT_VINFO_VEC_STMT (stmt_vinfo
) = new_stmt
;
2607 if (vect_print_dump_info (REPORT_DETAILS
))
2609 fprintf (vect_dump
, "vector of inductions after inner-loop:");
2610 print_gimple_stmt (vect_dump
, new_stmt
, 0, TDF_SLIM
);
2616 if (vect_print_dump_info (REPORT_DETAILS
))
2618 fprintf (vect_dump
, "transform induction: created def-use cycle: ");
2619 print_gimple_stmt (vect_dump
, induction_phi
, 0, TDF_SLIM
);
2620 fprintf (vect_dump
, "\n");
2621 print_gimple_stmt (vect_dump
, SSA_NAME_DEF_STMT (vec_def
), 0, TDF_SLIM
);
2624 STMT_VINFO_VEC_STMT (phi_info
) = induction_phi
;
2629 /* Function get_initial_def_for_reduction
2632 STMT - a stmt that performs a reduction operation in the loop.
2633 INIT_VAL - the initial value of the reduction variable
2636 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
2637 of the reduction (used for adjusting the epilog - see below).
2638 Return a vector variable, initialized according to the operation that STMT
2639 performs. This vector will be used as the initial value of the
2640 vector of partial results.
2642 Option1 (adjust in epilog): Initialize the vector as follows:
2643 add/bit or/xor: [0,0,...,0,0]
2644 mult/bit and: [1,1,...,1,1]
2645 min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
2646 and when necessary (e.g. add/mult case) let the caller know
2647 that it needs to adjust the result by init_val.
2649 Option2: Initialize the vector as follows:
2650 add/bit or/xor: [init_val,0,0,...,0]
2651 mult/bit and: [init_val,1,1,...,1]
2652 min/max/cond_expr: [init_val,init_val,...,init_val]
2653 and no adjustments are needed.
2655 For example, for the following code:
2661 STMT is 's = s + a[i]', and the reduction variable is 's'.
2662 For a vector of 4 units, we want to return either [0,0,0,init_val],
2663 or [0,0,0,0] and let the caller know that it needs to adjust
2664 the result at the end by 'init_val'.
2666 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
2667 initialization vector is simpler (same element in all entries), if
2668 ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
2670 A cost model should help decide between these two schemes. */
2673 get_initial_def_for_reduction (gimple stmt
, tree init_val
,
2674 tree
*adjustment_def
)
2676 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (stmt
);
2677 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_vinfo
);
2678 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2679 tree scalar_type
= TREE_TYPE (init_val
);
2680 tree vectype
= get_vectype_for_scalar_type (scalar_type
);
2682 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2687 bool nested_in_vect_loop
= false;
2689 REAL_VALUE_TYPE real_init_val
= dconst0
;
2690 int int_init_val
= 0;
2691 gimple def_stmt
= NULL
;
2693 gcc_assert (vectype
);
2694 nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
2696 gcc_assert (POINTER_TYPE_P (scalar_type
) || INTEGRAL_TYPE_P (scalar_type
)
2697 || SCALAR_FLOAT_TYPE_P (scalar_type
));
2699 if (nested_in_vect_loop_p (loop
, stmt
))
2700 nested_in_vect_loop
= true;
2702 gcc_assert (loop
== (gimple_bb (stmt
))->loop_father
);
2704 /* In case of double reduction we only create a vector variable to be put
2705 in the reduction phi node. The actual statement creation is done in
2706 vect_create_epilog_for_reduction. */
2707 if (adjustment_def
&& nested_in_vect_loop
2708 && TREE_CODE (init_val
) == SSA_NAME
2709 && (def_stmt
= SSA_NAME_DEF_STMT (init_val
))
2710 && gimple_code (def_stmt
) == GIMPLE_PHI
2711 && flow_bb_inside_loop_p (loop
, gimple_bb (def_stmt
))
2712 && vinfo_for_stmt (def_stmt
)
2713 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt
))
2714 == vect_double_reduction_def
)
2716 *adjustment_def
= NULL
;
2717 return vect_create_destination_var (init_val
, vectype
);
2720 if (TREE_CONSTANT (init_val
))
2722 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
2723 init_value
= build_real (scalar_type
, TREE_REAL_CST (init_val
));
2725 init_value
= build_int_cst (scalar_type
, TREE_INT_CST_LOW (init_val
));
2728 init_value
= init_val
;
2732 case WIDEN_SUM_EXPR
:
2740 /* ADJUSMENT_DEF is NULL when called from
2741 vect_create_epilog_for_reduction to vectorize double reduction. */
2744 if (nested_in_vect_loop
)
2745 *adjustment_def
= vect_get_vec_def_for_operand (init_val
, stmt
,
2748 *adjustment_def
= init_val
;
2751 if (code
== MULT_EXPR
)
2753 real_init_val
= dconst1
;
2757 if (code
== BIT_AND_EXPR
)
2760 if (SCALAR_FLOAT_TYPE_P (scalar_type
))
2761 def_for_init
= build_real (scalar_type
, real_init_val
);
2763 def_for_init
= build_int_cst (scalar_type
, int_init_val
);
2765 /* Create a vector of '0' or '1' except the first element. */
2766 for (i
= nunits
- 2; i
>= 0; --i
)
2767 t
= tree_cons (NULL_TREE
, def_for_init
, t
);
2769 /* Option1: the first element is '0' or '1' as well. */
2772 t
= tree_cons (NULL_TREE
, def_for_init
, t
);
2773 init_def
= build_vector (vectype
, t
);
2777 /* Option2: the first element is INIT_VAL. */
2778 t
= tree_cons (NULL_TREE
, init_value
, t
);
2779 if (TREE_CONSTANT (init_val
))
2780 init_def
= build_vector (vectype
, t
);
2782 init_def
= build_constructor_from_list (vectype
, t
);
2791 *adjustment_def
= NULL_TREE
;
2792 init_def
= vect_get_vec_def_for_operand (init_val
, stmt
, NULL
);
2796 for (i
= nunits
- 1; i
>= 0; --i
)
2797 t
= tree_cons (NULL_TREE
, init_value
, t
);
2799 if (TREE_CONSTANT (init_val
))
2800 init_def
= build_vector (vectype
, t
);
2802 init_def
= build_constructor_from_list (vectype
, t
);
2814 /* Function vect_create_epilog_for_reduction
2816 Create code at the loop-epilog to finalize the result of a reduction
2819 VECT_DEF is a vector of partial results.
2820 REDUC_CODE is the tree-code for the epilog reduction.
2821 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
2822 number of elements that we can fit in a vectype (nunits). In this case
2823 we have to generate more than one vector stmt - i.e - we need to "unroll"
2824 the vector stmt by a factor VF/nunits. For more details see documentation
2825 in vectorizable_operation.
2826 STMT is the scalar reduction stmt that is being vectorized.
2827 REDUCTION_PHI is the phi-node that carries the reduction computation.
2828 REDUC_INDEX is the index of the operand in the right hand side of the
2829 statement that is defined by REDUCTION_PHI.
2830 DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
2833 1. Creates the reduction def-use cycle: sets the arguments for
2835 The loop-entry argument is the vectorized initial-value of the reduction.
2836 The loop-latch argument is VECT_DEF - the vector of partial sums.
2837 2. "Reduces" the vector of partial results VECT_DEF into a single result,
2838 by applying the operation specified by REDUC_CODE if available, or by
2839 other means (whole-vector shifts or a scalar loop).
2840 The function also creates a new phi node at the loop exit to preserve
2841 loop-closed form, as illustrated below.
2843 The flow at the entry to this function:
2846 vec_def = phi <null, null> # REDUCTION_PHI
2847 VECT_DEF = vector_stmt # vectorized form of STMT
2848 s_loop = scalar_stmt # (scalar) STMT
2850 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
2854 The above is transformed by this function into:
2857 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
2858 VECT_DEF = vector_stmt # vectorized form of STMT
2859 s_loop = scalar_stmt # (scalar) STMT
2861 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
2862 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
2863 v_out2 = reduce <v_out1>
2864 s_out3 = extract_field <v_out2, 0>
2865 s_out4 = adjust_result <s_out3>
2871 vect_create_epilog_for_reduction (tree vect_def
, gimple stmt
,
2873 enum tree_code reduc_code
,
2874 gimple reduction_phi
,
2878 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2879 stmt_vec_info prev_phi_info
;
2881 enum machine_mode mode
;
2882 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
2883 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
), *outer_loop
= NULL
;
2884 basic_block exit_bb
;
2887 gimple new_phi
= NULL
, phi
;
2888 gimple_stmt_iterator exit_gsi
;
2890 tree new_temp
= NULL_TREE
;
2892 gimple epilog_stmt
= NULL
;
2893 tree new_scalar_dest
, new_dest
;
2895 tree bitsize
, bitpos
;
2896 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2897 tree adjustment_def
;
2898 tree vec_initial_def
, def
;
2900 imm_use_iterator imm_iter
;
2901 use_operand_p use_p
;
2902 bool extract_scalar_result
= false;
2903 tree reduction_op
, expr
;
2906 bool nested_in_vect_loop
= false;
2907 VEC(gimple
,heap
) *phis
= NULL
;
2908 enum vect_def_type dt
= vect_unknown_def_type
;
2911 if (nested_in_vect_loop_p (loop
, stmt
))
2915 nested_in_vect_loop
= true;
2918 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
2920 case GIMPLE_SINGLE_RHS
:
2921 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
))
2923 reduction_op
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), reduc_index
);
2925 case GIMPLE_UNARY_RHS
:
2926 reduction_op
= gimple_assign_rhs1 (stmt
);
2928 case GIMPLE_BINARY_RHS
:
2929 reduction_op
= reduc_index
?
2930 gimple_assign_rhs2 (stmt
) : gimple_assign_rhs1 (stmt
);
2936 vectype
= get_vectype_for_scalar_type (TREE_TYPE (reduction_op
));
2937 gcc_assert (vectype
);
2938 mode
= TYPE_MODE (vectype
);
2940 /*** 1. Create the reduction def-use cycle ***/
2942 /* For the case of reduction, vect_get_vec_def_for_operand returns
2943 the scalar def before the loop, that defines the initial value
2944 of the reduction variable. */
2945 vec_initial_def
= vect_get_vec_def_for_operand (reduction_op
, stmt
,
2948 phi
= reduction_phi
;
2950 for (j
= 0; j
< ncopies
; j
++)
2952 /* 1.1 set the loop-entry arg of the reduction-phi: */
2953 add_phi_arg (phi
, vec_initial_def
, loop_preheader_edge (loop
),
2956 /* 1.2 set the loop-latch arg for the reduction-phi: */
2958 def
= vect_get_vec_def_for_stmt_copy (dt
, def
);
2959 add_phi_arg (phi
, def
, loop_latch_edge (loop
), UNKNOWN_LOCATION
);
2961 if (vect_print_dump_info (REPORT_DETAILS
))
2963 fprintf (vect_dump
, "transform reduction: created def-use cycle: ");
2964 print_gimple_stmt (vect_dump
, phi
, 0, TDF_SLIM
);
2965 fprintf (vect_dump
, "\n");
2966 print_gimple_stmt (vect_dump
, SSA_NAME_DEF_STMT (def
), 0, TDF_SLIM
);
2969 phi
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi
));
2972 /*** 2. Create epilog code
2973 The reduction epilog code operates across the elements of the vector
2974 of partial results computed by the vectorized loop.
2975 The reduction epilog code consists of:
2976 step 1: compute the scalar result in a vector (v_out2)
2977 step 2: extract the scalar result (s_out3) from the vector (v_out2)
2978 step 3: adjust the scalar result (s_out3) if needed.
2980 Step 1 can be accomplished using one the following three schemes:
2981 (scheme 1) using reduc_code, if available.
2982 (scheme 2) using whole-vector shifts, if available.
2983 (scheme 3) using a scalar loop. In this case steps 1+2 above are
2986 The overall epilog code looks like this:
2988 s_out0 = phi <s_loop> # original EXIT_PHI
2989 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
2990 v_out2 = reduce <v_out1> # step 1
2991 s_out3 = extract_field <v_out2, 0> # step 2
2992 s_out4 = adjust_result <s_out3> # step 3
2994 (step 3 is optional, and steps 1 and 2 may be combined).
2995 Lastly, the uses of s_out0 are replaced by s_out4.
2999 /* 2.1 Create new loop-exit-phi to preserve loop-closed form:
3000 v_out1 = phi <v_loop> */
3002 exit_bb
= single_exit (loop
)->dest
;
3004 prev_phi_info
= NULL
;
3005 for (j
= 0; j
< ncopies
; j
++)
3007 phi
= create_phi_node (SSA_NAME_VAR (vect_def
), exit_bb
);
3008 set_vinfo_for_stmt (phi
, new_stmt_vec_info (phi
, loop_vinfo
, NULL
));
3013 def
= vect_get_vec_def_for_stmt_copy (dt
, def
);
3014 STMT_VINFO_RELATED_STMT (prev_phi_info
) = phi
;
3016 SET_PHI_ARG_DEF (phi
, single_exit (loop
)->dest_idx
, def
);
3017 prev_phi_info
= vinfo_for_stmt (phi
);
3020 exit_gsi
= gsi_after_labels (exit_bb
);
3022 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
3023 (i.e. when reduc_code is not available) and in the final adjustment
3024 code (if needed). Also get the original scalar reduction variable as
3025 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
3026 represents a reduction pattern), the tree-code and scalar-def are
3027 taken from the original stmt that the pattern-stmt (STMT) replaces.
3028 Otherwise (it is a regular reduction) - the tree-code and scalar-def
3029 are taken from STMT. */
3031 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
3034 /* Regular reduction */
3039 /* Reduction pattern */
3040 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (orig_stmt
);
3041 gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo
));
3042 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo
) == stmt
);
3045 code
= gimple_assign_rhs_code (orig_stmt
);
3046 scalar_dest
= gimple_assign_lhs (orig_stmt
);
3047 scalar_type
= TREE_TYPE (scalar_dest
);
3048 new_scalar_dest
= vect_create_destination_var (scalar_dest
, NULL
);
3049 bitsize
= TYPE_SIZE (scalar_type
);
3051 /* For MINUS_EXPR the initial vector is [init_val,0,...,0], therefore,
3052 partial results are added and not subtracted. */
3053 if (code
== MINUS_EXPR
)
3056 /* In case this is a reduction in an inner-loop while vectorizing an outer
3057 loop - we don't need to extract a single scalar result at the end of the
3058 inner-loop (unless it is double reduction, i.e., the use of reduction is
3059 outside the outer-loop). The final vector of partial results will be used
3060 in the vectorized outer-loop, or reduced to a scalar result at the end of
3062 if (nested_in_vect_loop
&& !double_reduc
)
3063 goto vect_finalize_reduction
;
3065 /* The epilogue is created for the outer-loop, i.e., for the loop being
3071 gcc_assert (ncopies
== 1);
3073 /* 2.3 Create the reduction code, using one of the three schemes described
3076 if (reduc_code
!= ERROR_MARK
)
3080 /*** Case 1: Create:
3081 v_out2 = reduc_expr <v_out1> */
3083 if (vect_print_dump_info (REPORT_DETAILS
))
3084 fprintf (vect_dump
, "Reduce using direct vector reduction.");
3086 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
3087 tmp
= build1 (reduc_code
, vectype
, PHI_RESULT (new_phi
));
3088 epilog_stmt
= gimple_build_assign (vec_dest
, tmp
);
3089 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
3090 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
3091 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
3093 extract_scalar_result
= true;
3097 enum tree_code shift_code
= ERROR_MARK
;
3098 bool have_whole_vector_shift
= true;
3100 int element_bitsize
= tree_low_cst (bitsize
, 1);
3101 int vec_size_in_bits
= tree_low_cst (TYPE_SIZE (vectype
), 1);
3104 if (optab_handler (vec_shr_optab
, mode
)->insn_code
!= CODE_FOR_nothing
)
3105 shift_code
= VEC_RSHIFT_EXPR
;
3107 have_whole_vector_shift
= false;
3109 /* Regardless of whether we have a whole vector shift, if we're
3110 emulating the operation via tree-vect-generic, we don't want
3111 to use it. Only the first round of the reduction is likely
3112 to still be profitable via emulation. */
3113 /* ??? It might be better to emit a reduction tree code here, so that
3114 tree-vect-generic can expand the first round via bit tricks. */
3115 if (!VECTOR_MODE_P (mode
))
3116 have_whole_vector_shift
= false;
3119 optab optab
= optab_for_tree_code (code
, vectype
, optab_default
);
3120 if (optab_handler (optab
, mode
)->insn_code
== CODE_FOR_nothing
)
3121 have_whole_vector_shift
= false;
3124 if (have_whole_vector_shift
)
3126 /*** Case 2: Create:
3127 for (offset = VS/2; offset >= element_size; offset/=2)
3129 Create: va' = vec_shift <va, offset>
3130 Create: va = vop <va, va'>
3133 if (vect_print_dump_info (REPORT_DETAILS
))
3134 fprintf (vect_dump
, "Reduce using vector shifts");
3136 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
3137 new_temp
= PHI_RESULT (new_phi
);
3139 for (bit_offset
= vec_size_in_bits
/2;
3140 bit_offset
>= element_bitsize
;
3143 tree bitpos
= size_int (bit_offset
);
3145 epilog_stmt
= gimple_build_assign_with_ops (shift_code
, vec_dest
,
3147 new_name
= make_ssa_name (vec_dest
, epilog_stmt
);
3148 gimple_assign_set_lhs (epilog_stmt
, new_name
);
3149 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
3151 epilog_stmt
= gimple_build_assign_with_ops (code
, vec_dest
,
3152 new_name
, new_temp
);
3153 new_temp
= make_ssa_name (vec_dest
, epilog_stmt
);
3154 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
3155 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
3158 extract_scalar_result
= true;
3164 /*** Case 3: Create:
3165 s = extract_field <v_out2, 0>
3166 for (offset = element_size;
3167 offset < vector_size;
3168 offset += element_size;)
3170 Create: s' = extract_field <v_out2, offset>
3171 Create: s = op <s, s'>
3174 if (vect_print_dump_info (REPORT_DETAILS
))
3175 fprintf (vect_dump
, "Reduce using scalar code. ");
3177 vec_temp
= PHI_RESULT (new_phi
);
3178 vec_size_in_bits
= tree_low_cst (TYPE_SIZE (vectype
), 1);
3179 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
, bitsize
,
3181 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
3182 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
3183 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
3184 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
3186 for (bit_offset
= element_bitsize
;
3187 bit_offset
< vec_size_in_bits
;
3188 bit_offset
+= element_bitsize
)
3190 tree bitpos
= bitsize_int (bit_offset
);
3191 tree rhs
= build3 (BIT_FIELD_REF
, scalar_type
, vec_temp
, bitsize
,
3194 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
3195 new_name
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
3196 gimple_assign_set_lhs (epilog_stmt
, new_name
);
3197 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
3199 epilog_stmt
= gimple_build_assign_with_ops (code
,
3201 new_name
, new_temp
);
3202 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
3203 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
3204 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
3207 extract_scalar_result
= false;
3211 /* 2.4 Extract the final scalar result. Create:
3212 s_out3 = extract_field <v_out2, bitpos> */
3214 if (extract_scalar_result
)
3218 gcc_assert (!nested_in_vect_loop
|| double_reduc
);
3219 if (vect_print_dump_info (REPORT_DETAILS
))
3220 fprintf (vect_dump
, "extract scalar result");
3222 if (BYTES_BIG_ENDIAN
)
3223 bitpos
= size_binop (MULT_EXPR
,
3224 bitsize_int (TYPE_VECTOR_SUBPARTS (vectype
) - 1),
3225 TYPE_SIZE (scalar_type
));
3227 bitpos
= bitsize_zero_node
;
3229 rhs
= build3 (BIT_FIELD_REF
, scalar_type
, new_temp
, bitsize
, bitpos
);
3230 epilog_stmt
= gimple_build_assign (new_scalar_dest
, rhs
);
3231 new_temp
= make_ssa_name (new_scalar_dest
, epilog_stmt
);
3232 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
3233 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
3236 vect_finalize_reduction
:
3241 /* 2.5 Adjust the final result by the initial value of the reduction
3242 variable. (When such adjustment is not needed, then
3243 'adjustment_def' is zero). For example, if code is PLUS we create:
3244 new_temp = loop_exit_def + adjustment_def */
3248 if (nested_in_vect_loop
)
3250 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) == VECTOR_TYPE
);
3251 expr
= build2 (code
, vectype
, PHI_RESULT (new_phi
), adjustment_def
);
3252 new_dest
= vect_create_destination_var (scalar_dest
, vectype
);
3256 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def
)) != VECTOR_TYPE
);
3257 expr
= build2 (code
, scalar_type
, new_temp
, adjustment_def
);
3258 new_dest
= vect_create_destination_var (scalar_dest
, scalar_type
);
3261 epilog_stmt
= gimple_build_assign (new_dest
, expr
);
3262 new_temp
= make_ssa_name (new_dest
, epilog_stmt
);
3263 gimple_assign_set_lhs (epilog_stmt
, new_temp
);
3264 SSA_NAME_DEF_STMT (new_temp
) = epilog_stmt
;
3265 gsi_insert_before (&exit_gsi
, epilog_stmt
, GSI_SAME_STMT
);
3269 /* 2.6 Handle the loop-exit phi */
3271 /* Replace uses of s_out0 with uses of s_out3:
3272 Find the loop-closed-use at the loop exit of the original scalar result.
3273 (The reduction result is expected to have two immediate uses - one at the
3274 latch block, and one at the loop exit). */
3275 phis
= VEC_alloc (gimple
, heap
, 10);
3276 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, scalar_dest
)
3278 if (!flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
3280 exit_phi
= USE_STMT (use_p
);
3281 VEC_quick_push (gimple
, phis
, exit_phi
);
3285 /* We expect to have found an exit_phi because of loop-closed-ssa form. */
3286 gcc_assert (!VEC_empty (gimple
, phis
));
3288 for (i
= 0; VEC_iterate (gimple
, phis
, i
, exit_phi
); i
++)
3290 if (nested_in_vect_loop
)
3292 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (exit_phi
);
3295 /* FORNOW. Currently not supporting the case that an inner-loop
3296 reduction is not used in the outer-loop (but only outside the
3297 outer-loop), unless it is double reduction. */
3298 gcc_assert ((STMT_VINFO_RELEVANT_P (stmt_vinfo
)
3299 && !STMT_VINFO_LIVE_P (stmt_vinfo
)) || double_reduc
);
3301 epilog_stmt
= adjustment_def
? epilog_stmt
: new_phi
;
3302 STMT_VINFO_VEC_STMT (stmt_vinfo
) = epilog_stmt
;
3303 set_vinfo_for_stmt (epilog_stmt
,
3304 new_stmt_vec_info (epilog_stmt
, loop_vinfo
,
3307 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (epilog_stmt
)) =
3308 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_phi
));
3311 || STMT_VINFO_DEF_TYPE (stmt_vinfo
) != vect_double_reduction_def
)
3314 /* Handle double reduction:
3316 stmt1: s1 = phi <s0, s2> - double reduction phi (outer loop)
3317 stmt2: s3 = phi <s1, s4> - (regular) reduction phi (inner loop)
3318 stmt3: s4 = use (s3) - (regular) reduction stmt (inner loop)
3319 stmt4: s2 = phi <s4> - double reduction stmt (outer loop)
3321 At that point the regular reduction (stmt2 and stmt3) is already
3322 vectorized, as well as the exit phi node, stmt4.
3323 Here we vectorize the phi node of double reduction, stmt1, and
3324 update all relevant statements. */
3326 /* Go through all the uses of s2 to find double reduction phi node,
3327 i.e., stmt1 above. */
3328 orig_name
= PHI_RESULT (exit_phi
);
3329 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
3331 stmt_vec_info use_stmt_vinfo
= vinfo_for_stmt (use_stmt
);
3332 stmt_vec_info new_phi_vinfo
;
3333 tree vect_phi_init
, preheader_arg
, vect_phi_res
, init_def
;
3334 basic_block bb
= gimple_bb (use_stmt
);
3337 /* Check that USE_STMT is really double reduction phi node. */
3338 if (gimple_code (use_stmt
) != GIMPLE_PHI
3339 || gimple_phi_num_args (use_stmt
) != 2
3341 || STMT_VINFO_DEF_TYPE (use_stmt_vinfo
)
3342 != vect_double_reduction_def
3343 || bb
->loop_father
!= outer_loop
)
3346 /* Create vector phi node for double reduction:
3347 vs1 = phi <vs0, vs2>
3348 vs1 was created previously in this function by a call to
3349 vect_get_vec_def_for_operand and is stored in vec_initial_def;
3350 vs2 is defined by EPILOG_STMT, the vectorized EXIT_PHI;
3351 vs0 is created here. */
3353 /* Create vector phi node. */
3354 vect_phi
= create_phi_node (vec_initial_def
, bb
);
3355 new_phi_vinfo
= new_stmt_vec_info (vect_phi
,
3356 loop_vec_info_for_loop (outer_loop
), NULL
);
3357 set_vinfo_for_stmt (vect_phi
, new_phi_vinfo
);
3359 /* Create vs0 - initial def of the double reduction phi. */
3360 preheader_arg
= PHI_ARG_DEF_FROM_EDGE (use_stmt
,
3361 loop_preheader_edge (outer_loop
));
3362 init_def
= get_initial_def_for_reduction (stmt
, preheader_arg
,
3364 vect_phi_init
= vect_init_vector (use_stmt
, init_def
, vectype
,
3367 /* Update phi node arguments with vs0 and vs2. */
3368 add_phi_arg (vect_phi
, vect_phi_init
,
3369 loop_preheader_edge (outer_loop
), UNKNOWN_LOCATION
);
3370 add_phi_arg (vect_phi
, PHI_RESULT (epilog_stmt
),
3371 loop_latch_edge (outer_loop
), UNKNOWN_LOCATION
);
3372 if (vect_print_dump_info (REPORT_DETAILS
))
3374 fprintf (vect_dump
, "created double reduction phi node: ");
3375 print_gimple_stmt (vect_dump
, vect_phi
, 0, TDF_SLIM
);
3378 vect_phi_res
= PHI_RESULT (vect_phi
);
3380 /* Replace the use, i.e., set the correct vs1 in the regular
3381 reduction phi node. FORNOW, NCOPIES is always 1, so the loop
3383 use
= reduction_phi
;
3384 for (j
= 0; j
< ncopies
; j
++)
3386 edge pr_edge
= loop_preheader_edge (loop
);
3387 SET_PHI_ARG_DEF (use
, pr_edge
->dest_idx
, vect_phi_res
);
3388 use
= STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use
));
3393 /* Replace the uses: */
3394 orig_name
= PHI_RESULT (exit_phi
);
3395 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, orig_name
)
3396 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
3397 SET_USE (use_p
, new_temp
);
3400 VEC_free (gimple
, heap
, phis
);
3404 /* Function vectorizable_reduction.
3406 Check if STMT performs a reduction operation that can be vectorized.
3407 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3408 stmt to replace it, put it in VEC_STMT, and insert it at GSI.
3409 Return FALSE if not a vectorizable STMT, TRUE otherwise.
3411 This function also handles reduction idioms (patterns) that have been
3412 recognized in advance during vect_pattern_recog. In this case, STMT may be
3414 X = pattern_expr (arg0, arg1, ..., X)
3415 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
3416 sequence that had been detected and replaced by the pattern-stmt (STMT).
3418 In some cases of reduction patterns, the type of the reduction variable X is
3419 different than the type of the other arguments of STMT.
3420 In such cases, the vectype that is used when transforming STMT into a vector
3421 stmt is different than the vectype that is used to determine the
3422 vectorization factor, because it consists of a different number of elements
3423 than the actual number of elements that are being operated upon in parallel.
3425 For example, consider an accumulation of shorts into an int accumulator.
3426 On some targets it's possible to vectorize this pattern operating on 8
3427 shorts at a time (hence, the vectype for purposes of determining the
3428 vectorization factor should be V8HI); on the other hand, the vectype that
3429 is used to create the vector form is actually V4SI (the type of the result).
3431 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
3432 indicates what is the actual level of parallelism (V8HI in the example), so
3433 that the right vectorization factor would be derived. This vectype
3434 corresponds to the type of arguments to the reduction stmt, and should *NOT*
3435 be used to create the vectorized stmt. The right vectype for the vectorized
3436 stmt is obtained from the type of the result X:
3437 get_vectype_for_scalar_type (TREE_TYPE (X))
3439 This means that, contrary to "regular" reductions (or "regular" stmts in
3440 general), the following equation:
3441 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
3442 does *NOT* necessarily hold for reduction patterns. */
3445 vectorizable_reduction (gimple stmt
, gimple_stmt_iterator
*gsi
,
3450 tree loop_vec_def0
= NULL_TREE
, loop_vec_def1
= NULL_TREE
;
3451 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3452 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3453 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3454 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3455 enum tree_code code
, orig_code
, epilog_reduc_code
;
3456 enum machine_mode vec_mode
;
3458 optab optab
, reduc_optab
;
3459 tree new_temp
= NULL_TREE
;
3462 enum vect_def_type dt
;
3463 gimple new_phi
= NULL
;
3467 stmt_vec_info orig_stmt_info
;
3468 tree expr
= NULL_TREE
;
3470 int nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
3471 int ncopies
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) / nunits
;
3473 stmt_vec_info prev_stmt_info
, prev_phi_info
;
3474 gimple first_phi
= NULL
;
3475 bool single_defuse_cycle
= false;
3476 tree reduc_def
= NULL_TREE
;
3477 gimple new_stmt
= NULL
;
3480 bool nested_cycle
= false, found_nested_cycle_def
= false;
3481 gimple reduc_def_stmt
= NULL
;
3482 /* The default is that the reduction variable is the last in statement. */
3483 int reduc_index
= 2;
3484 bool double_reduc
= false, dummy
;
3486 struct loop
* def_stmt_loop
, *outer_loop
= NULL
;
3488 gimple def_arg_stmt
;
3490 if (nested_in_vect_loop_p (loop
, stmt
))
3494 nested_cycle
= true;
3497 gcc_assert (ncopies
>= 1);
3499 /* FORNOW: SLP not supported. */
3500 if (STMT_SLP_TYPE (stmt_info
))
3503 /* 1. Is vectorizable reduction? */
3504 /* Not supportable if the reduction variable is used in the loop. */
3505 if (STMT_VINFO_RELEVANT (stmt_info
) > vect_used_in_outer
)
3508 /* Reductions that are not used even in an enclosing outer-loop,
3509 are expected to be "live" (used out of the loop). */
3510 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
3511 && !STMT_VINFO_LIVE_P (stmt_info
))
3514 /* Make sure it was already recognized as a reduction computation. */
3515 if (STMT_VINFO_DEF_TYPE (stmt_info
) != vect_reduction_def
3516 && STMT_VINFO_DEF_TYPE (stmt_info
) != vect_nested_cycle
)
3519 /* 2. Has this been recognized as a reduction pattern?
3521 Check if STMT represents a pattern that has been recognized
3522 in earlier analysis stages. For stmts that represent a pattern,
3523 the STMT_VINFO_RELATED_STMT field records the last stmt in
3524 the original sequence that constitutes the pattern. */
3526 orig_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
3529 orig_stmt_info
= vinfo_for_stmt (orig_stmt
);
3530 gcc_assert (STMT_VINFO_RELATED_STMT (orig_stmt_info
) == stmt
);
3531 gcc_assert (STMT_VINFO_IN_PATTERN_P (orig_stmt_info
));
3532 gcc_assert (!STMT_VINFO_IN_PATTERN_P (stmt_info
));
3535 /* 3. Check the operands of the operation. The first operands are defined
3536 inside the loop body. The last operand is the reduction variable,
3537 which is defined by the loop-header-phi. */
3539 gcc_assert (is_gimple_assign (stmt
));
3542 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
)))
3544 case GIMPLE_SINGLE_RHS
:
3545 op_type
= TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt
));
3546 if (op_type
== ternary_op
)
3548 tree rhs
= gimple_assign_rhs1 (stmt
);
3549 ops
[0] = TREE_OPERAND (rhs
, 0);
3550 ops
[1] = TREE_OPERAND (rhs
, 1);
3551 ops
[2] = TREE_OPERAND (rhs
, 2);
3552 code
= TREE_CODE (rhs
);
3558 case GIMPLE_BINARY_RHS
:
3559 code
= gimple_assign_rhs_code (stmt
);
3560 op_type
= TREE_CODE_LENGTH (code
);
3561 gcc_assert (op_type
== binary_op
);
3562 ops
[0] = gimple_assign_rhs1 (stmt
);
3563 ops
[1] = gimple_assign_rhs2 (stmt
);
3566 case GIMPLE_UNARY_RHS
:
3573 scalar_dest
= gimple_assign_lhs (stmt
);
3574 scalar_type
= TREE_TYPE (scalar_dest
);
3575 if (!POINTER_TYPE_P (scalar_type
) && !INTEGRAL_TYPE_P (scalar_type
)
3576 && !SCALAR_FLOAT_TYPE_P (scalar_type
))
3579 /* All uses but the last are expected to be defined in the loop.
3580 The last use is the reduction variable. In case of nested cycle this
3581 assumption is not true: we use reduc_index to record the index of the
3582 reduction variable. */
3583 for (i
= 0; i
< op_type
-1; i
++)
3585 /* The condition of COND_EXPR is checked in vectorizable_condition(). */
3586 if (i
== 0 && code
== COND_EXPR
)
3589 is_simple_use
= vect_is_simple_use (ops
[i
], loop_vinfo
, NULL
, &def_stmt
,
3591 gcc_assert (is_simple_use
);
3592 if (dt
!= vect_internal_def
3593 && dt
!= vect_external_def
3594 && dt
!= vect_constant_def
3595 && dt
!= vect_induction_def
3596 && !(dt
== vect_nested_cycle
&& nested_cycle
))
3599 if (dt
== vect_nested_cycle
)
3601 found_nested_cycle_def
= true;
3602 reduc_def_stmt
= def_stmt
;
3607 is_simple_use
= vect_is_simple_use (ops
[i
], loop_vinfo
, NULL
, &def_stmt
,
3609 gcc_assert (is_simple_use
);
3610 gcc_assert (dt
== vect_reduction_def
3611 || dt
== vect_nested_cycle
3612 || ((dt
== vect_internal_def
|| dt
== vect_external_def
3613 || dt
== vect_constant_def
|| dt
== vect_induction_def
)
3614 && nested_cycle
&& found_nested_cycle_def
));
3615 if (!found_nested_cycle_def
)
3616 reduc_def_stmt
= def_stmt
;
3618 gcc_assert (gimple_code (reduc_def_stmt
) == GIMPLE_PHI
);
3620 gcc_assert (orig_stmt
== vect_is_simple_reduction (loop_vinfo
,
3625 gcc_assert (stmt
== vect_is_simple_reduction (loop_vinfo
, reduc_def_stmt
,
3626 !nested_cycle
, &dummy
));
3628 if (STMT_VINFO_LIVE_P (vinfo_for_stmt (reduc_def_stmt
)))
3631 vec_mode
= TYPE_MODE (vectype
);
3633 if (code
== COND_EXPR
)
3635 if (!vectorizable_condition (stmt
, gsi
, NULL
, ops
[reduc_index
], 0))
3637 if (vect_print_dump_info (REPORT_DETAILS
))
3638 fprintf (vect_dump
, "unsupported condition in reduction");
3645 /* 4. Supportable by target? */
3647 /* 4.1. check support for the operation in the loop */
3648 optab
= optab_for_tree_code (code
, vectype
, optab_default
);
3651 if (vect_print_dump_info (REPORT_DETAILS
))
3652 fprintf (vect_dump
, "no optab.");
3657 if (optab_handler (optab
, vec_mode
)->insn_code
== CODE_FOR_nothing
)
3659 if (vect_print_dump_info (REPORT_DETAILS
))
3660 fprintf (vect_dump
, "op not supported by target.");
3662 if (GET_MODE_SIZE (vec_mode
) != UNITS_PER_WORD
3663 || LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
3664 < vect_min_worthwhile_factor (code
))
3667 if (vect_print_dump_info (REPORT_DETAILS
))
3668 fprintf (vect_dump
, "proceeding using word mode.");
3671 /* Worthwhile without SIMD support? */
3672 if (!VECTOR_MODE_P (TYPE_MODE (vectype
))
3673 && LOOP_VINFO_VECT_FACTOR (loop_vinfo
)
3674 < vect_min_worthwhile_factor (code
))
3676 if (vect_print_dump_info (REPORT_DETAILS
))
3677 fprintf (vect_dump
, "not worthwhile without SIMD support.");
3683 /* 4.2. Check support for the epilog operation.
3685 If STMT represents a reduction pattern, then the type of the
3686 reduction variable may be different than the type of the rest
3687 of the arguments. For example, consider the case of accumulation
3688 of shorts into an int accumulator; The original code:
3689 S1: int_a = (int) short_a;
3690 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
3693 STMT: int_acc = widen_sum <short_a, int_acc>
3696 1. The tree-code that is used to create the vector operation in the
3697 epilog code (that reduces the partial results) is not the
3698 tree-code of STMT, but is rather the tree-code of the original
3699 stmt from the pattern that STMT is replacing. I.e, in the example
3700 above we want to use 'widen_sum' in the loop, but 'plus' in the
3702 2. The type (mode) we use to check available target support
3703 for the vector operation to be created in the *epilog*, is
3704 determined by the type of the reduction variable (in the example
3705 above we'd check this: plus_optab[vect_int_mode]).
3706 However the type (mode) we use to check available target support
3707 for the vector operation to be created *inside the loop*, is
3708 determined by the type of the other arguments to STMT (in the
3709 example we'd check this: widen_sum_optab[vect_short_mode]).
3711 This is contrary to "regular" reductions, in which the types of all
3712 the arguments are the same as the type of the reduction variable.
3713 For "regular" reductions we can therefore use the same vector type
3714 (and also the same tree-code) when generating the epilog code and
3715 when generating the code inside the loop. */
3719 /* This is a reduction pattern: get the vectype from the type of the
3720 reduction variable, and get the tree-code from orig_stmt. */
3721 orig_code
= gimple_assign_rhs_code (orig_stmt
);
3722 vectype
= get_vectype_for_scalar_type (TREE_TYPE (def
));
3725 if (vect_print_dump_info (REPORT_DETAILS
))
3727 fprintf (vect_dump
, "unsupported data-type ");
3728 print_generic_expr (vect_dump
, TREE_TYPE (def
), TDF_SLIM
);
3733 vec_mode
= TYPE_MODE (vectype
);
3737 /* Regular reduction: use the same vectype and tree-code as used for
3738 the vector code inside the loop can be used for the epilog code. */
3744 def_bb
= gimple_bb (reduc_def_stmt
);
3745 def_stmt_loop
= def_bb
->loop_father
;
3746 def_arg
= PHI_ARG_DEF_FROM_EDGE (reduc_def_stmt
,
3747 loop_preheader_edge (def_stmt_loop
));
3748 if (TREE_CODE (def_arg
) == SSA_NAME
3749 && (def_arg_stmt
= SSA_NAME_DEF_STMT (def_arg
))
3750 && gimple_code (def_arg_stmt
) == GIMPLE_PHI
3751 && flow_bb_inside_loop_p (outer_loop
, gimple_bb (def_arg_stmt
))
3752 && vinfo_for_stmt (def_arg_stmt
)
3753 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_arg_stmt
))
3754 == vect_double_reduction_def
)
3755 double_reduc
= true;
3758 epilog_reduc_code
= ERROR_MARK
;
3759 if (reduction_code_for_scalar_code (orig_code
, &epilog_reduc_code
))
3761 reduc_optab
= optab_for_tree_code (epilog_reduc_code
, vectype
,
3765 if (vect_print_dump_info (REPORT_DETAILS
))
3766 fprintf (vect_dump
, "no optab for reduction.");
3768 epilog_reduc_code
= ERROR_MARK
;
3772 && optab_handler (reduc_optab
, vec_mode
)->insn_code
3773 == CODE_FOR_nothing
)
3775 if (vect_print_dump_info (REPORT_DETAILS
))
3776 fprintf (vect_dump
, "reduc op not supported by target.");
3778 epilog_reduc_code
= ERROR_MARK
;
3783 if (!nested_cycle
|| double_reduc
)
3785 if (vect_print_dump_info (REPORT_DETAILS
))
3786 fprintf (vect_dump
, "no reduc code for scalar code.");
3792 if (double_reduc
&& ncopies
> 1)
3794 if (vect_print_dump_info (REPORT_DETAILS
))
3795 fprintf (vect_dump
, "multiple types in double reduction");
3800 if (!vec_stmt
) /* transformation not required. */
3802 STMT_VINFO_TYPE (stmt_info
) = reduc_vec_info_type
;
3803 if (!vect_model_reduction_cost (stmt_info
, epilog_reduc_code
, ncopies
))
3810 if (vect_print_dump_info (REPORT_DETAILS
))
3811 fprintf (vect_dump
, "transform reduction.");
3813 /* FORNOW: Multiple types are not supported for condition. */
3814 if (code
== COND_EXPR
)
3815 gcc_assert (ncopies
== 1);
3817 /* Create the destination vector */
3818 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
3820 /* In case the vectorization factor (VF) is bigger than the number
3821 of elements that we can fit in a vectype (nunits), we have to generate
3822 more than one vector stmt - i.e - we need to "unroll" the
3823 vector stmt by a factor VF/nunits. For more details see documentation
3824 in vectorizable_operation. */
3826 /* If the reduction is used in an outer loop we need to generate
3827 VF intermediate results, like so (e.g. for ncopies=2):
3832 (i.e. we generate VF results in 2 registers).
3833 In this case we have a separate def-use cycle for each copy, and therefore
3834 for each copy we get the vector def for the reduction variable from the
3835 respective phi node created for this copy.
3837 Otherwise (the reduction is unused in the loop nest), we can combine
3838 together intermediate results, like so (e.g. for ncopies=2):
3842 (i.e. we generate VF/2 results in a single register).
3843 In this case for each copy we get the vector def for the reduction variable
3844 from the vectorized reduction operation generated in the previous iteration.
3847 if (STMT_VINFO_RELEVANT (stmt_info
) == vect_unused_in_scope
)
3849 single_defuse_cycle
= true;
3853 epilog_copies
= ncopies
;
3855 prev_stmt_info
= NULL
;
3856 prev_phi_info
= NULL
;
3857 for (j
= 0; j
< ncopies
; j
++)
3859 if (j
== 0 || !single_defuse_cycle
)
3861 /* Create the reduction-phi that defines the reduction-operand. */
3862 new_phi
= create_phi_node (vec_dest
, loop
->header
);
3863 set_vinfo_for_stmt (new_phi
, new_stmt_vec_info (new_phi
, loop_vinfo
,
3865 /* Get the vector def for the reduction variable from the phi
3867 reduc_def
= PHI_RESULT (new_phi
);
3870 if (code
== COND_EXPR
)
3872 first_phi
= new_phi
;
3873 vectorizable_condition (stmt
, gsi
, vec_stmt
, reduc_def
, reduc_index
);
3874 /* Multiple types are not supported for condition. */
3881 loop_vec_def0
= vect_get_vec_def_for_operand (ops
[!reduc_index
],
3883 if (op_type
== ternary_op
)
3885 if (reduc_index
== 0)
3886 loop_vec_def1
= vect_get_vec_def_for_operand (ops
[2], stmt
,
3889 loop_vec_def1
= vect_get_vec_def_for_operand (ops
[1], stmt
,
3893 /* Get the vector def for the reduction variable from the phi
3895 first_phi
= new_phi
;
3899 enum vect_def_type dt
= vect_unknown_def_type
; /* Dummy */
3900 loop_vec_def0
= vect_get_vec_def_for_stmt_copy (dt
, loop_vec_def0
);
3901 if (op_type
== ternary_op
)
3902 loop_vec_def1
= vect_get_vec_def_for_stmt_copy (dt
, loop_vec_def1
);
3904 if (single_defuse_cycle
)
3905 reduc_def
= gimple_assign_lhs (new_stmt
);
3907 reduc_def
= PHI_RESULT (new_phi
);
3909 STMT_VINFO_RELATED_STMT (prev_phi_info
) = new_phi
;
3912 /* Arguments are ready. Create the new vector stmt. */
3913 if (op_type
== binary_op
)
3915 if (reduc_index
== 0)
3916 expr
= build2 (code
, vectype
, reduc_def
, loop_vec_def0
);
3918 expr
= build2 (code
, vectype
, loop_vec_def0
, reduc_def
);
3922 if (reduc_index
== 0)
3923 expr
= build3 (code
, vectype
, reduc_def
, loop_vec_def0
,
3927 if (reduc_index
== 1)
3928 expr
= build3 (code
, vectype
, loop_vec_def0
, reduc_def
,
3931 expr
= build3 (code
, vectype
, loop_vec_def0
, loop_vec_def1
,
3936 new_stmt
= gimple_build_assign (vec_dest
, expr
);
3937 new_temp
= make_ssa_name (vec_dest
, new_stmt
);
3938 gimple_assign_set_lhs (new_stmt
, new_temp
);
3939 vect_finish_stmt_generation (stmt
, new_stmt
, gsi
);
3942 STMT_VINFO_VEC_STMT (stmt_info
) = *vec_stmt
= new_stmt
;
3944 STMT_VINFO_RELATED_STMT (prev_stmt_info
) = new_stmt
;
3946 prev_stmt_info
= vinfo_for_stmt (new_stmt
);
3947 prev_phi_info
= vinfo_for_stmt (new_phi
);
3950 /* Finalize the reduction-phi (set its arguments) and create the
3951 epilog reduction code. */
3952 if (!single_defuse_cycle
|| code
== COND_EXPR
)
3953 new_temp
= gimple_assign_lhs (*vec_stmt
);
3955 vect_create_epilog_for_reduction (new_temp
, stmt
, epilog_copies
,
3956 epilog_reduc_code
, first_phi
, reduc_index
,
3961 /* Function vect_min_worthwhile_factor.
3963 For a loop where we could vectorize the operation indicated by CODE,
3964 return the minimum vectorization factor that makes it worthwhile
3965 to use generic vectors. */
3967 vect_min_worthwhile_factor (enum tree_code code
)
3988 /* Function vectorizable_induction
3990 Check if PHI performs an induction computation that can be vectorized.
3991 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
3992 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
3993 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
3996 vectorizable_induction (gimple phi
, gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
3999 stmt_vec_info stmt_info
= vinfo_for_stmt (phi
);
4000 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
4001 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
4002 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4003 int nunits
= TYPE_VECTOR_SUBPARTS (vectype
);
4004 int ncopies
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) / nunits
;
4007 gcc_assert (ncopies
>= 1);
4008 /* FORNOW. This restriction should be relaxed. */
4009 if (nested_in_vect_loop_p (loop
, phi
) && ncopies
> 1)
4011 if (vect_print_dump_info (REPORT_DETAILS
))
4012 fprintf (vect_dump
, "multiple types in nested loop.");
4016 if (!STMT_VINFO_RELEVANT_P (stmt_info
))
4019 /* FORNOW: SLP not supported. */
4020 if (STMT_SLP_TYPE (stmt_info
))
4023 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
);
4025 if (gimple_code (phi
) != GIMPLE_PHI
)
4028 if (!vec_stmt
) /* transformation not required. */
4030 STMT_VINFO_TYPE (stmt_info
) = induc_vec_info_type
;
4031 if (vect_print_dump_info (REPORT_DETAILS
))
4032 fprintf (vect_dump
, "=== vectorizable_induction ===");
4033 vect_model_induction_cost (stmt_info
, ncopies
);
4039 if (vect_print_dump_info (REPORT_DETAILS
))
4040 fprintf (vect_dump
, "transform induction phi.");
4042 vec_def
= get_initial_def_for_induction (phi
);
4043 *vec_stmt
= SSA_NAME_DEF_STMT (vec_def
);
4047 /* Function vectorizable_live_operation.
4049 STMT computes a value that is used outside the loop. Check if
4050 it can be supported. */
4053 vectorizable_live_operation (gimple stmt
,
4054 gimple_stmt_iterator
*gsi ATTRIBUTE_UNUSED
,
4055 gimple
*vec_stmt ATTRIBUTE_UNUSED
)
4057 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
4058 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
4059 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4065 enum vect_def_type dt
;
4066 enum tree_code code
;
4067 enum gimple_rhs_class rhs_class
;
4069 gcc_assert (STMT_VINFO_LIVE_P (stmt_info
));
4071 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_reduction_def
)
4074 if (!is_gimple_assign (stmt
))
4077 if (TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
4080 /* FORNOW. CHECKME. */
4081 if (nested_in_vect_loop_p (loop
, stmt
))
4084 code
= gimple_assign_rhs_code (stmt
);
4085 op_type
= TREE_CODE_LENGTH (code
);
4086 rhs_class
= get_gimple_rhs_class (code
);
4087 gcc_assert (rhs_class
!= GIMPLE_UNARY_RHS
|| op_type
== unary_op
);
4088 gcc_assert (rhs_class
!= GIMPLE_BINARY_RHS
|| op_type
== binary_op
);
4090 /* FORNOW: support only if all uses are invariant. This means
4091 that the scalar operations can remain in place, unvectorized.
4092 The original last scalar value that they compute will be used. */
4094 for (i
= 0; i
< op_type
; i
++)
4096 if (rhs_class
== GIMPLE_SINGLE_RHS
)
4097 op
= TREE_OPERAND (gimple_op (stmt
, 1), i
);
4099 op
= gimple_op (stmt
, i
+ 1);
4101 && !vect_is_simple_use (op
, loop_vinfo
, NULL
, &def_stmt
, &def
, &dt
))
4103 if (vect_print_dump_info (REPORT_DETAILS
))
4104 fprintf (vect_dump
, "use not simple.");
4108 if (dt
!= vect_external_def
&& dt
!= vect_constant_def
)
4112 /* No transformation is required for the cases we currently support. */
4116 /* Kill any debug uses outside LOOP of SSA names defined in STMT. */
4119 vect_loop_kill_debug_uses (struct loop
*loop
, gimple stmt
)
4121 ssa_op_iter op_iter
;
4122 imm_use_iterator imm_iter
;
4123 def_operand_p def_p
;
4126 FOR_EACH_PHI_OR_STMT_DEF (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
4128 FOR_EACH_IMM_USE_STMT (ustmt
, imm_iter
, DEF_FROM_PTR (def_p
))
4132 if (!is_gimple_debug (ustmt
))
4135 bb
= gimple_bb (ustmt
);
4137 if (!flow_bb_inside_loop_p (loop
, bb
))
4139 if (gimple_debug_bind_p (ustmt
))
4141 if (vect_print_dump_info (REPORT_DETAILS
))
4142 fprintf (vect_dump
, "killing debug use");
4144 gimple_debug_bind_reset_value (ustmt
);
4145 update_stmt (ustmt
);
4154 /* Function vect_transform_loop.
4156 The analysis phase has determined that the loop is vectorizable.
4157 Vectorize the loop - created vectorized stmts to replace the scalar
4158 stmts in the loop, and update the loop exit condition. */
4161 vect_transform_loop (loop_vec_info loop_vinfo
)
4163 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4164 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
4165 int nbbs
= loop
->num_nodes
;
4166 gimple_stmt_iterator si
;
4169 int vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
4171 bool slp_scheduled
= false;
4172 unsigned int nunits
;
4173 tree cond_expr
= NULL_TREE
;
4174 gimple_seq cond_expr_stmt_list
= NULL
;
4175 bool do_peeling_for_loop_bound
;
4177 if (vect_print_dump_info (REPORT_DETAILS
))
4178 fprintf (vect_dump
, "=== vec_transform_loop ===");
4180 /* Peel the loop if there are data refs with unknown alignment.
4181 Only one data ref with unknown store is allowed. */
4183 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
))
4184 vect_do_peeling_for_alignment (loop_vinfo
);
4186 do_peeling_for_loop_bound
4187 = (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
4188 || (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
4189 && LOOP_VINFO_INT_NITERS (loop_vinfo
) % vectorization_factor
!= 0));
4191 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
)
4192 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
4193 vect_loop_versioning (loop_vinfo
,
4194 !do_peeling_for_loop_bound
,
4195 &cond_expr
, &cond_expr_stmt_list
);
4197 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
4198 compile time constant), or it is a constant that doesn't divide by the
4199 vectorization factor, then an epilog loop needs to be created.
4200 We therefore duplicate the loop: the original loop will be vectorized,
4201 and will compute the first (n/VF) iterations. The second copy of the loop
4202 will remain scalar and will compute the remaining (n%VF) iterations.
4203 (VF is the vectorization factor). */
4205 if (do_peeling_for_loop_bound
)
4206 vect_do_peeling_for_loop_bound (loop_vinfo
, &ratio
,
4207 cond_expr
, cond_expr_stmt_list
);
4209 ratio
= build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo
)),
4210 LOOP_VINFO_INT_NITERS (loop_vinfo
) / vectorization_factor
);
4212 /* 1) Make sure the loop header has exactly two entries
4213 2) Make sure we have a preheader basic block. */
4215 gcc_assert (EDGE_COUNT (loop
->header
->preds
) == 2);
4217 split_edge (loop_preheader_edge (loop
));
4219 /* FORNOW: the vectorizer supports only loops which body consist
4220 of one basic block (header + empty latch). When the vectorizer will
4221 support more involved loop forms, the order by which the BBs are
4222 traversed need to be reconsidered. */
4224 for (i
= 0; i
< nbbs
; i
++)
4226 basic_block bb
= bbs
[i
];
4227 stmt_vec_info stmt_info
;
4230 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
4232 phi
= gsi_stmt (si
);
4233 if (vect_print_dump_info (REPORT_DETAILS
))
4235 fprintf (vect_dump
, "------>vectorizing phi: ");
4236 print_gimple_stmt (vect_dump
, phi
, 0, TDF_SLIM
);
4238 stmt_info
= vinfo_for_stmt (phi
);
4242 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
4243 vect_loop_kill_debug_uses (loop
, phi
);
4245 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
4246 && !STMT_VINFO_LIVE_P (stmt_info
))
4249 if ((TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
))
4250 != (unsigned HOST_WIDE_INT
) vectorization_factor
)
4251 && vect_print_dump_info (REPORT_DETAILS
))
4252 fprintf (vect_dump
, "multiple-types.");
4254 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_induction_def
)
4256 if (vect_print_dump_info (REPORT_DETAILS
))
4257 fprintf (vect_dump
, "transform phi.");
4258 vect_transform_stmt (phi
, NULL
, NULL
, NULL
, NULL
);
4262 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
);)
4264 gimple stmt
= gsi_stmt (si
);
4267 if (vect_print_dump_info (REPORT_DETAILS
))
4269 fprintf (vect_dump
, "------>vectorizing statement: ");
4270 print_gimple_stmt (vect_dump
, stmt
, 0, TDF_SLIM
);
4273 stmt_info
= vinfo_for_stmt (stmt
);
4275 /* vector stmts created in the outer-loop during vectorization of
4276 stmts in an inner-loop may not have a stmt_info, and do not
4277 need to be vectorized. */
4284 if (MAY_HAVE_DEBUG_STMTS
&& !STMT_VINFO_LIVE_P (stmt_info
))
4285 vect_loop_kill_debug_uses (loop
, stmt
);
4287 if (!STMT_VINFO_RELEVANT_P (stmt_info
)
4288 && !STMT_VINFO_LIVE_P (stmt_info
))
4294 gcc_assert (STMT_VINFO_VECTYPE (stmt_info
));
4296 (unsigned int) TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
4297 if (!STMT_SLP_TYPE (stmt_info
)
4298 && nunits
!= (unsigned int) vectorization_factor
4299 && vect_print_dump_info (REPORT_DETAILS
))
4300 /* For SLP VF is set according to unrolling factor, and not to
4301 vector size, hence for SLP this print is not valid. */
4302 fprintf (vect_dump
, "multiple-types.");
4304 /* SLP. Schedule all the SLP instances when the first SLP stmt is
4306 if (STMT_SLP_TYPE (stmt_info
))
4310 slp_scheduled
= true;
4312 if (vect_print_dump_info (REPORT_DETAILS
))
4313 fprintf (vect_dump
, "=== scheduling SLP instances ===");
4315 vect_schedule_slp (loop_vinfo
, NULL
);
4318 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
4319 if (!vinfo_for_stmt (stmt
) || PURE_SLP_STMT (stmt_info
))
4326 /* -------- vectorize statement ------------ */
4327 if (vect_print_dump_info (REPORT_DETAILS
))
4328 fprintf (vect_dump
, "transform statement.");
4330 strided_store
= false;
4331 is_store
= vect_transform_stmt (stmt
, &si
, &strided_store
, NULL
, NULL
);
4334 if (STMT_VINFO_STRIDED_ACCESS (stmt_info
))
4336 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
4337 interleaving chain was completed - free all the stores in
4339 vect_remove_stores (DR_GROUP_FIRST_DR (stmt_info
));
4340 gsi_remove (&si
, true);
4345 /* Free the attached stmt_vec_info and remove the stmt. */
4346 free_stmt_vec_info (stmt
);
4347 gsi_remove (&si
, true);
4355 slpeel_make_loop_iterate_ntimes (loop
, ratio
);
4357 /* The memory tags and pointers in vectorized statements need to
4358 have their SSA forms updated. FIXME, why can't this be delayed
4359 until all the loops have been transformed? */
4360 update_ssa (TODO_update_ssa
);
4362 if (vect_print_dump_info (REPORT_VECTORIZED_LOCATIONS
))
4363 fprintf (vect_dump
, "LOOP VECTORIZED.");
4364 if (loop
->inner
&& vect_print_dump_info (REPORT_VECTORIZED_LOCATIONS
))
4365 fprintf (vect_dump
, "OUTER LOOP VECTORIZED.");