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 "tree-pretty-print.h"
31 #include "gimple-pretty-print.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
35 #include "cfglayout.h"
40 #include "diagnostic-core.h"
41 #include "tree-chrec.h"
42 #include "tree-scalar-evolution.h"
43 #include "tree-vectorizer.h"
46 /* Loop Vectorization Pass.
48 This pass tries to vectorize loops.
50 For example, the vectorizer transforms the following simple loop:
52 short a[N]; short b[N]; short c[N]; int i;
58 as if it was manually vectorized by rewriting the source code into:
60 typedef int __attribute__((mode(V8HI))) v8hi;
61 short a[N]; short b[N]; short c[N]; int i;
62 v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
65 for (i=0; i<N/8; i++){
72 The main entry to this pass is vectorize_loops(), in which
73 the vectorizer applies a set of analyses on a given set of loops,
74 followed by the actual vectorization transformation for the loops that
75 had successfully passed the analysis phase.
76 Throughout this pass we make a distinction between two types of
77 data: scalars (which are represented by SSA_NAMES), and memory references
78 ("data-refs"). These two types of data require different handling both
79 during analysis and transformation. The types of data-refs that the
80 vectorizer currently supports are ARRAY_REFS which base is an array DECL
81 (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
82 accesses are required to have a simple (consecutive) access pattern.
86 The driver for the analysis phase is vect_analyze_loop().
87 It applies a set of analyses, some of which rely on the scalar evolution
88 analyzer (scev) developed by Sebastian Pop.
90 During the analysis phase the vectorizer records some information
91 per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
92 loop, as well as general information about the loop as a whole, which is
93 recorded in a "loop_vec_info" struct attached to each loop.
97 The loop transformation phase scans all the stmts in the loop, and
98 creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
99 the loop that needs to be vectorized. It inserts the vector code sequence
100 just before the scalar stmt S, and records a pointer to the vector code
101 in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
102 attached to S). This pointer will be used for the vectorization of following
103 stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
104 otherwise, we rely on dead code elimination for removing it.
106 For example, say stmt S1 was vectorized into stmt VS1:
109 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
112 To vectorize stmt S2, the vectorizer first finds the stmt that defines
113 the operand 'b' (S1), and gets the relevant vector def 'vb' from the
114 vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
115 resulting sequence would be:
118 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
120 S2: a = b; STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
122 Operands that are not SSA_NAMEs, are data-refs that appear in
123 load/store operations (like 'x[i]' in S1), and are handled differently.
127 Currently the only target specific information that is used is the
128 size of the vector (in bytes) - "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD".
129 Targets that can support different sizes of vectors, for now will need
130 to specify one value for "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD". More
131 flexibility will be added in the future.
133 Since we only vectorize operations which vector form can be
134 expressed using existing tree codes, to verify that an operation is
135 supported, the vectorizer checks the relevant optab at the relevant
136 machine_mode (e.g, optab_handler (add_optab, V8HImode)). If
137 the value found is CODE_FOR_nothing, then there's no target support, and
138 we can't vectorize the stmt.
140 For additional information on this project see:
141 http://gcc.gnu.org/projects/tree-ssa/vectorization.html
144 /* Function vect_determine_vectorization_factor
146 Determine the vectorization factor (VF). VF is the number of data elements
147 that are operated upon in parallel in a single iteration of the vectorized
148 loop. For example, when vectorizing a loop that operates on 4byte elements,
149 on a target with vector size (VS) 16byte, the VF is set to 4, since 4
150 elements can fit in a single vector register.
152 We currently support vectorization of loops in which all types operated upon
153 are of the same size. Therefore this function currently sets VF according to
154 the size of the types operated upon, and fails if there are multiple sizes
157 VF is also the factor by which the loop iterations are strip-mined, e.g.:
164 for (i=0; i<N; i+=VF){
165 a[i:VF] = b[i:VF] + c[i:VF];
170 vect_determine_vectorization_factor (loop_vec_info loop_vinfo)
172 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
173 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
174 int nbbs = loop->num_nodes;
175 gimple_stmt_iterator si;
176 unsigned int vectorization_factor = 0;
181 stmt_vec_info stmt_info;
185 if (vect_print_dump_info (REPORT_DETAILS))
186 fprintf (vect_dump, "=== vect_determine_vectorization_factor ===");
188 for (i = 0; i < nbbs; i++)
190 basic_block bb = bbs[i];
192 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
195 stmt_info = vinfo_for_stmt (phi);
196 if (vect_print_dump_info (REPORT_DETAILS))
198 fprintf (vect_dump, "==> examining phi: ");
199 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
202 gcc_assert (stmt_info);
204 if (STMT_VINFO_RELEVANT_P (stmt_info))
206 gcc_assert (!STMT_VINFO_VECTYPE (stmt_info));
207 scalar_type = TREE_TYPE (PHI_RESULT (phi));
209 if (vect_print_dump_info (REPORT_DETAILS))
211 fprintf (vect_dump, "get vectype for scalar type: ");
212 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
215 vectype = get_vectype_for_scalar_type (scalar_type);
218 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
221 "not vectorized: unsupported data-type ");
222 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
226 STMT_VINFO_VECTYPE (stmt_info) = vectype;
228 if (vect_print_dump_info (REPORT_DETAILS))
230 fprintf (vect_dump, "vectype: ");
231 print_generic_expr (vect_dump, vectype, TDF_SLIM);
234 nunits = TYPE_VECTOR_SUBPARTS (vectype);
235 if (vect_print_dump_info (REPORT_DETAILS))
236 fprintf (vect_dump, "nunits = %d", nunits);
238 if (!vectorization_factor
239 || (nunits > vectorization_factor))
240 vectorization_factor = nunits;
244 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
247 gimple stmt = gsi_stmt (si), pattern_stmt;
248 stmt_info = vinfo_for_stmt (stmt);
250 if (vect_print_dump_info (REPORT_DETAILS))
252 fprintf (vect_dump, "==> examining statement: ");
253 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
256 gcc_assert (stmt_info);
258 /* Skip stmts which do not need to be vectorized. */
259 if (!STMT_VINFO_RELEVANT_P (stmt_info)
260 && !STMT_VINFO_LIVE_P (stmt_info))
262 if (STMT_VINFO_IN_PATTERN_P (stmt_info)
263 && (pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info))
264 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt))
265 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt))))
268 stmt_info = vinfo_for_stmt (pattern_stmt);
269 if (vect_print_dump_info (REPORT_DETAILS))
271 fprintf (vect_dump, "==> examining pattern statement: ");
272 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
277 if (vect_print_dump_info (REPORT_DETAILS))
278 fprintf (vect_dump, "skip.");
283 if (gimple_get_lhs (stmt) == NULL_TREE)
285 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
287 fprintf (vect_dump, "not vectorized: irregular stmt.");
288 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
293 if (VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt))))
295 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
297 fprintf (vect_dump, "not vectorized: vector stmt in loop:");
298 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
303 if (STMT_VINFO_VECTYPE (stmt_info))
305 /* The only case when a vectype had been already set is for stmts
306 that contain a dataref, or for "pattern-stmts" (stmts generated
307 by the vectorizer to represent/replace a certain idiom). */
308 gcc_assert (STMT_VINFO_DATA_REF (stmt_info)
309 || is_pattern_stmt_p (stmt_info));
310 vectype = STMT_VINFO_VECTYPE (stmt_info);
314 gcc_assert (!STMT_VINFO_DATA_REF (stmt_info)
315 && !is_pattern_stmt_p (stmt_info));
317 scalar_type = TREE_TYPE (gimple_get_lhs (stmt));
318 if (vect_print_dump_info (REPORT_DETAILS))
320 fprintf (vect_dump, "get vectype for scalar type: ");
321 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
323 vectype = get_vectype_for_scalar_type (scalar_type);
326 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
329 "not vectorized: unsupported data-type ");
330 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
335 STMT_VINFO_VECTYPE (stmt_info) = vectype;
338 /* The vectorization factor is according to the smallest
339 scalar type (or the largest vector size, but we only
340 support one vector size per loop). */
341 scalar_type = vect_get_smallest_scalar_type (stmt, &dummy,
343 if (vect_print_dump_info (REPORT_DETAILS))
345 fprintf (vect_dump, "get vectype for scalar type: ");
346 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
348 vf_vectype = get_vectype_for_scalar_type (scalar_type);
351 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
354 "not vectorized: unsupported data-type ");
355 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
360 if ((GET_MODE_SIZE (TYPE_MODE (vectype))
361 != GET_MODE_SIZE (TYPE_MODE (vf_vectype))))
363 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
366 "not vectorized: different sized vector "
367 "types in statement, ");
368 print_generic_expr (vect_dump, vectype, TDF_SLIM);
369 fprintf (vect_dump, " and ");
370 print_generic_expr (vect_dump, vf_vectype, TDF_SLIM);
375 if (vect_print_dump_info (REPORT_DETAILS))
377 fprintf (vect_dump, "vectype: ");
378 print_generic_expr (vect_dump, vf_vectype, TDF_SLIM);
381 nunits = TYPE_VECTOR_SUBPARTS (vf_vectype);
382 if (vect_print_dump_info (REPORT_DETAILS))
383 fprintf (vect_dump, "nunits = %d", nunits);
385 if (!vectorization_factor
386 || (nunits > vectorization_factor))
387 vectorization_factor = nunits;
391 /* TODO: Analyze cost. Decide if worth while to vectorize. */
392 if (vect_print_dump_info (REPORT_DETAILS))
393 fprintf (vect_dump, "vectorization factor = %d", vectorization_factor);
394 if (vectorization_factor <= 1)
396 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
397 fprintf (vect_dump, "not vectorized: unsupported data-type");
400 LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
406 /* Function vect_is_simple_iv_evolution.
408 FORNOW: A simple evolution of an induction variables in the loop is
409 considered a polynomial evolution with constant step. */
412 vect_is_simple_iv_evolution (unsigned loop_nb, tree access_fn, tree * init,
417 tree evolution_part = evolution_part_in_loop_num (access_fn, loop_nb);
419 /* When there is no evolution in this loop, the evolution function
421 if (evolution_part == NULL_TREE)
424 /* When the evolution is a polynomial of degree >= 2
425 the evolution function is not "simple". */
426 if (tree_is_chrec (evolution_part))
429 step_expr = evolution_part;
430 init_expr = unshare_expr (initial_condition_in_loop_num (access_fn, loop_nb));
432 if (vect_print_dump_info (REPORT_DETAILS))
434 fprintf (vect_dump, "step: ");
435 print_generic_expr (vect_dump, step_expr, TDF_SLIM);
436 fprintf (vect_dump, ", init: ");
437 print_generic_expr (vect_dump, init_expr, TDF_SLIM);
443 if (TREE_CODE (step_expr) != INTEGER_CST)
445 if (vect_print_dump_info (REPORT_DETAILS))
446 fprintf (vect_dump, "step unknown.");
453 /* Function vect_analyze_scalar_cycles_1.
455 Examine the cross iteration def-use cycles of scalar variables
456 in LOOP. LOOP_VINFO represents the loop that is now being
457 considered for vectorization (can be LOOP, or an outer-loop
461 vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo, struct loop *loop)
463 basic_block bb = loop->header;
465 VEC(gimple,heap) *worklist = VEC_alloc (gimple, heap, 64);
466 gimple_stmt_iterator gsi;
469 if (vect_print_dump_info (REPORT_DETAILS))
470 fprintf (vect_dump, "=== vect_analyze_scalar_cycles ===");
472 /* First - identify all inductions. Reduction detection assumes that all the
473 inductions have been identified, therefore, this order must not be
475 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
477 gimple phi = gsi_stmt (gsi);
478 tree access_fn = NULL;
479 tree def = PHI_RESULT (phi);
480 stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
482 if (vect_print_dump_info (REPORT_DETAILS))
484 fprintf (vect_dump, "Analyze phi: ");
485 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
488 /* Skip virtual phi's. The data dependences that are associated with
489 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
490 if (!is_gimple_reg (SSA_NAME_VAR (def)))
493 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_unknown_def_type;
495 /* Analyze the evolution function. */
496 access_fn = analyze_scalar_evolution (loop, def);
498 STRIP_NOPS (access_fn);
499 if (access_fn && vect_print_dump_info (REPORT_DETAILS))
501 fprintf (vect_dump, "Access function of PHI: ");
502 print_generic_expr (vect_dump, access_fn, TDF_SLIM);
506 || !vect_is_simple_iv_evolution (loop->num, access_fn, &dumy, &dumy))
508 VEC_safe_push (gimple, heap, worklist, phi);
512 if (vect_print_dump_info (REPORT_DETAILS))
513 fprintf (vect_dump, "Detected induction.");
514 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def;
518 /* Second - identify all reductions and nested cycles. */
519 while (VEC_length (gimple, worklist) > 0)
521 gimple phi = VEC_pop (gimple, worklist);
522 tree def = PHI_RESULT (phi);
523 stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
527 if (vect_print_dump_info (REPORT_DETAILS))
529 fprintf (vect_dump, "Analyze phi: ");
530 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
533 gcc_assert (is_gimple_reg (SSA_NAME_VAR (def)));
534 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_unknown_def_type);
536 nested_cycle = (loop != LOOP_VINFO_LOOP (loop_vinfo));
537 reduc_stmt = vect_force_simple_reduction (loop_vinfo, phi, !nested_cycle,
543 if (vect_print_dump_info (REPORT_DETAILS))
544 fprintf (vect_dump, "Detected double reduction.");
546 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_double_reduction_def;
547 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
548 vect_double_reduction_def;
554 if (vect_print_dump_info (REPORT_DETAILS))
555 fprintf (vect_dump, "Detected vectorizable nested cycle.");
557 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_nested_cycle;
558 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
563 if (vect_print_dump_info (REPORT_DETAILS))
564 fprintf (vect_dump, "Detected reduction.");
566 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_reduction_def;
567 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
569 /* Store the reduction cycles for possible vectorization in
571 VEC_safe_push (gimple, heap,
572 LOOP_VINFO_REDUCTIONS (loop_vinfo),
578 if (vect_print_dump_info (REPORT_DETAILS))
579 fprintf (vect_dump, "Unknown def-use cycle pattern.");
582 VEC_free (gimple, heap, worklist);
586 /* Function vect_analyze_scalar_cycles.
588 Examine the cross iteration def-use cycles of scalar variables, by
589 analyzing the loop-header PHIs of scalar variables. Classify each
590 cycle as one of the following: invariant, induction, reduction, unknown.
591 We do that for the loop represented by LOOP_VINFO, and also to its
592 inner-loop, if exists.
593 Examples for scalar cycles:
608 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
610 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
612 vect_analyze_scalar_cycles_1 (loop_vinfo, loop);
614 /* When vectorizing an outer-loop, the inner-loop is executed sequentially.
615 Reductions in such inner-loop therefore have different properties than
616 the reductions in the nest that gets vectorized:
617 1. When vectorized, they are executed in the same order as in the original
618 scalar loop, so we can't change the order of computation when
620 2. FIXME: Inner-loop reductions can be used in the inner-loop, so the
621 current checks are too strict. */
624 vect_analyze_scalar_cycles_1 (loop_vinfo, loop->inner);
627 /* Function vect_get_loop_niters.
629 Determine how many iterations the loop is executed.
630 If an expression that represents the number of iterations
631 can be constructed, place it in NUMBER_OF_ITERATIONS.
632 Return the loop exit condition. */
635 vect_get_loop_niters (struct loop *loop, tree *number_of_iterations)
639 if (vect_print_dump_info (REPORT_DETAILS))
640 fprintf (vect_dump, "=== get_loop_niters ===");
642 niters = number_of_exit_cond_executions (loop);
644 if (niters != NULL_TREE
645 && niters != chrec_dont_know)
647 *number_of_iterations = niters;
649 if (vect_print_dump_info (REPORT_DETAILS))
651 fprintf (vect_dump, "==> get_loop_niters:" );
652 print_generic_expr (vect_dump, *number_of_iterations, TDF_SLIM);
656 return get_loop_exit_condition (loop);
660 /* Function bb_in_loop_p
662 Used as predicate for dfs order traversal of the loop bbs. */
665 bb_in_loop_p (const_basic_block bb, const void *data)
667 const struct loop *const loop = (const struct loop *)data;
668 if (flow_bb_inside_loop_p (loop, bb))
674 /* Function new_loop_vec_info.
676 Create and initialize a new loop_vec_info struct for LOOP, as well as
677 stmt_vec_info structs for all the stmts in LOOP. */
680 new_loop_vec_info (struct loop *loop)
684 gimple_stmt_iterator si;
685 unsigned int i, nbbs;
687 res = (loop_vec_info) xcalloc (1, sizeof (struct _loop_vec_info));
688 LOOP_VINFO_LOOP (res) = loop;
690 bbs = get_loop_body (loop);
692 /* Create/Update stmt_info for all stmts in the loop. */
693 for (i = 0; i < loop->num_nodes; i++)
695 basic_block bb = bbs[i];
697 /* BBs in a nested inner-loop will have been already processed (because
698 we will have called vect_analyze_loop_form for any nested inner-loop).
699 Therefore, for stmts in an inner-loop we just want to update the
700 STMT_VINFO_LOOP_VINFO field of their stmt_info to point to the new
701 loop_info of the outer-loop we are currently considering to vectorize
702 (instead of the loop_info of the inner-loop).
703 For stmts in other BBs we need to create a stmt_info from scratch. */
704 if (bb->loop_father != loop)
707 gcc_assert (loop->inner && bb->loop_father == loop->inner);
708 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
710 gimple phi = gsi_stmt (si);
711 stmt_vec_info stmt_info = vinfo_for_stmt (phi);
712 loop_vec_info inner_loop_vinfo =
713 STMT_VINFO_LOOP_VINFO (stmt_info);
714 gcc_assert (loop->inner == LOOP_VINFO_LOOP (inner_loop_vinfo));
715 STMT_VINFO_LOOP_VINFO (stmt_info) = res;
717 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
719 gimple stmt = gsi_stmt (si);
720 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
721 loop_vec_info inner_loop_vinfo =
722 STMT_VINFO_LOOP_VINFO (stmt_info);
723 gcc_assert (loop->inner == LOOP_VINFO_LOOP (inner_loop_vinfo));
724 STMT_VINFO_LOOP_VINFO (stmt_info) = res;
729 /* bb in current nest. */
730 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
732 gimple phi = gsi_stmt (si);
733 gimple_set_uid (phi, 0);
734 set_vinfo_for_stmt (phi, new_stmt_vec_info (phi, res, NULL));
737 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
739 gimple stmt = gsi_stmt (si);
740 gimple_set_uid (stmt, 0);
741 set_vinfo_for_stmt (stmt, new_stmt_vec_info (stmt, res, NULL));
746 /* CHECKME: We want to visit all BBs before their successors (except for
747 latch blocks, for which this assertion wouldn't hold). In the simple
748 case of the loop forms we allow, a dfs order of the BBs would the same
749 as reversed postorder traversal, so we are safe. */
752 bbs = XCNEWVEC (basic_block, loop->num_nodes);
753 nbbs = dfs_enumerate_from (loop->header, 0, bb_in_loop_p,
754 bbs, loop->num_nodes, loop);
755 gcc_assert (nbbs == loop->num_nodes);
757 LOOP_VINFO_BBS (res) = bbs;
758 LOOP_VINFO_NITERS (res) = NULL;
759 LOOP_VINFO_NITERS_UNCHANGED (res) = NULL;
760 LOOP_VINFO_COST_MODEL_MIN_ITERS (res) = 0;
761 LOOP_VINFO_VECTORIZABLE_P (res) = 0;
762 LOOP_PEELING_FOR_ALIGNMENT (res) = 0;
763 LOOP_VINFO_VECT_FACTOR (res) = 0;
764 LOOP_VINFO_LOOP_NEST (res) = VEC_alloc (loop_p, heap, 3);
765 LOOP_VINFO_DATAREFS (res) = VEC_alloc (data_reference_p, heap, 10);
766 LOOP_VINFO_DDRS (res) = VEC_alloc (ddr_p, heap, 10 * 10);
767 LOOP_VINFO_UNALIGNED_DR (res) = NULL;
768 LOOP_VINFO_MAY_MISALIGN_STMTS (res) =
769 VEC_alloc (gimple, heap,
770 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS));
771 LOOP_VINFO_MAY_ALIAS_DDRS (res) =
772 VEC_alloc (ddr_p, heap,
773 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS));
774 LOOP_VINFO_STRIDED_STORES (res) = VEC_alloc (gimple, heap, 10);
775 LOOP_VINFO_REDUCTIONS (res) = VEC_alloc (gimple, heap, 10);
776 LOOP_VINFO_REDUCTION_CHAINS (res) = VEC_alloc (gimple, heap, 10);
777 LOOP_VINFO_SLP_INSTANCES (res) = VEC_alloc (slp_instance, heap, 10);
778 LOOP_VINFO_SLP_UNROLLING_FACTOR (res) = 1;
779 LOOP_VINFO_PEELING_HTAB (res) = NULL;
780 LOOP_VINFO_PEELING_FOR_GAPS (res) = false;
786 /* Function destroy_loop_vec_info.
788 Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
789 stmts in the loop. */
792 destroy_loop_vec_info (loop_vec_info loop_vinfo, bool clean_stmts)
797 gimple_stmt_iterator si;
799 VEC (slp_instance, heap) *slp_instances;
800 slp_instance instance;
805 loop = LOOP_VINFO_LOOP (loop_vinfo);
807 bbs = LOOP_VINFO_BBS (loop_vinfo);
808 nbbs = loop->num_nodes;
812 free (LOOP_VINFO_BBS (loop_vinfo));
813 free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo));
814 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo));
815 VEC_free (loop_p, heap, LOOP_VINFO_LOOP_NEST (loop_vinfo));
816 VEC_free (gimple, heap, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
817 VEC_free (ddr_p, heap, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo));
824 for (j = 0; j < nbbs; j++)
826 basic_block bb = bbs[j];
827 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
828 free_stmt_vec_info (gsi_stmt (si));
830 for (si = gsi_start_bb (bb); !gsi_end_p (si); )
832 gimple stmt = gsi_stmt (si);
833 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
837 /* Check if this statement has a related "pattern stmt"
838 (introduced by the vectorizer during the pattern recognition
839 pass). Free pattern's stmt_vec_info. */
840 if (STMT_VINFO_IN_PATTERN_P (stmt_info)
841 && vinfo_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info)))
842 free_stmt_vec_info (STMT_VINFO_RELATED_STMT (stmt_info));
844 /* Free stmt_vec_info. */
845 free_stmt_vec_info (stmt);
852 free (LOOP_VINFO_BBS (loop_vinfo));
853 free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo));
854 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo));
855 VEC_free (loop_p, heap, LOOP_VINFO_LOOP_NEST (loop_vinfo));
856 VEC_free (gimple, heap, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
857 VEC_free (ddr_p, heap, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo));
858 slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
859 FOR_EACH_VEC_ELT (slp_instance, slp_instances, j, instance)
860 vect_free_slp_instance (instance);
862 VEC_free (slp_instance, heap, LOOP_VINFO_SLP_INSTANCES (loop_vinfo));
863 VEC_free (gimple, heap, LOOP_VINFO_STRIDED_STORES (loop_vinfo));
864 VEC_free (gimple, heap, LOOP_VINFO_REDUCTIONS (loop_vinfo));
865 VEC_free (gimple, heap, LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo));
867 if (LOOP_VINFO_PEELING_HTAB (loop_vinfo))
868 htab_delete (LOOP_VINFO_PEELING_HTAB (loop_vinfo));
875 /* Function vect_analyze_loop_1.
877 Apply a set of analyses on LOOP, and create a loop_vec_info struct
878 for it. The different analyses will record information in the
879 loop_vec_info struct. This is a subset of the analyses applied in
880 vect_analyze_loop, to be applied on an inner-loop nested in the loop
881 that is now considered for (outer-loop) vectorization. */
884 vect_analyze_loop_1 (struct loop *loop)
886 loop_vec_info loop_vinfo;
888 if (vect_print_dump_info (REPORT_DETAILS))
889 fprintf (vect_dump, "===== analyze_loop_nest_1 =====");
891 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
893 loop_vinfo = vect_analyze_loop_form (loop);
896 if (vect_print_dump_info (REPORT_DETAILS))
897 fprintf (vect_dump, "bad inner-loop form.");
905 /* Function vect_analyze_loop_form.
907 Verify that certain CFG restrictions hold, including:
908 - the loop has a pre-header
909 - the loop has a single entry and exit
910 - the loop exit condition is simple enough, and the number of iterations
911 can be analyzed (a countable loop). */
914 vect_analyze_loop_form (struct loop *loop)
916 loop_vec_info loop_vinfo;
918 tree number_of_iterations = NULL;
919 loop_vec_info inner_loop_vinfo = NULL;
921 if (vect_print_dump_info (REPORT_DETAILS))
922 fprintf (vect_dump, "=== vect_analyze_loop_form ===");
924 /* Different restrictions apply when we are considering an inner-most loop,
925 vs. an outer (nested) loop.
926 (FORNOW. May want to relax some of these restrictions in the future). */
930 /* Inner-most loop. We currently require that the number of BBs is
931 exactly 2 (the header and latch). Vectorizable inner-most loops
942 if (loop->num_nodes != 2)
944 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
945 fprintf (vect_dump, "not vectorized: control flow in loop.");
949 if (empty_block_p (loop->header))
951 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
952 fprintf (vect_dump, "not vectorized: empty loop.");
958 struct loop *innerloop = loop->inner;
961 /* Nested loop. We currently require that the loop is doubly-nested,
962 contains a single inner loop, and the number of BBs is exactly 5.
963 Vectorizable outer-loops look like this:
975 The inner-loop has the properties expected of inner-most loops
976 as described above. */
978 if ((loop->inner)->inner || (loop->inner)->next)
980 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
981 fprintf (vect_dump, "not vectorized: multiple nested loops.");
985 /* Analyze the inner-loop. */
986 inner_loop_vinfo = vect_analyze_loop_1 (loop->inner);
987 if (!inner_loop_vinfo)
989 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
990 fprintf (vect_dump, "not vectorized: Bad inner loop.");
994 if (!expr_invariant_in_loop_p (loop,
995 LOOP_VINFO_NITERS (inner_loop_vinfo)))
997 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
999 "not vectorized: inner-loop count not invariant.");
1000 destroy_loop_vec_info (inner_loop_vinfo, true);
1004 if (loop->num_nodes != 5)
1006 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1007 fprintf (vect_dump, "not vectorized: control flow in loop.");
1008 destroy_loop_vec_info (inner_loop_vinfo, true);
1012 gcc_assert (EDGE_COUNT (innerloop->header->preds) == 2);
1013 entryedge = EDGE_PRED (innerloop->header, 0);
1014 if (EDGE_PRED (innerloop->header, 0)->src == innerloop->latch)
1015 entryedge = EDGE_PRED (innerloop->header, 1);
1017 if (entryedge->src != loop->header
1018 || !single_exit (innerloop)
1019 || single_exit (innerloop)->dest != EDGE_PRED (loop->latch, 0)->src)
1021 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1022 fprintf (vect_dump, "not vectorized: unsupported outerloop form.");
1023 destroy_loop_vec_info (inner_loop_vinfo, true);
1027 if (vect_print_dump_info (REPORT_DETAILS))
1028 fprintf (vect_dump, "Considering outer-loop vectorization.");
1031 if (!single_exit (loop)
1032 || EDGE_COUNT (loop->header->preds) != 2)
1034 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1036 if (!single_exit (loop))
1037 fprintf (vect_dump, "not vectorized: multiple exits.");
1038 else if (EDGE_COUNT (loop->header->preds) != 2)
1039 fprintf (vect_dump, "not vectorized: too many incoming edges.");
1041 if (inner_loop_vinfo)
1042 destroy_loop_vec_info (inner_loop_vinfo, true);
1046 /* We assume that the loop exit condition is at the end of the loop. i.e,
1047 that the loop is represented as a do-while (with a proper if-guard
1048 before the loop if needed), where the loop header contains all the
1049 executable statements, and the latch is empty. */
1050 if (!empty_block_p (loop->latch)
1051 || !gimple_seq_empty_p (phi_nodes (loop->latch)))
1053 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1054 fprintf (vect_dump, "not vectorized: unexpected loop form.");
1055 if (inner_loop_vinfo)
1056 destroy_loop_vec_info (inner_loop_vinfo, true);
1060 /* Make sure there exists a single-predecessor exit bb: */
1061 if (!single_pred_p (single_exit (loop)->dest))
1063 edge e = single_exit (loop);
1064 if (!(e->flags & EDGE_ABNORMAL))
1066 split_loop_exit_edge (e);
1067 if (vect_print_dump_info (REPORT_DETAILS))
1068 fprintf (vect_dump, "split exit edge.");
1072 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1073 fprintf (vect_dump, "not vectorized: abnormal loop exit edge.");
1074 if (inner_loop_vinfo)
1075 destroy_loop_vec_info (inner_loop_vinfo, true);
1080 loop_cond = vect_get_loop_niters (loop, &number_of_iterations);
1083 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1084 fprintf (vect_dump, "not vectorized: complicated exit condition.");
1085 if (inner_loop_vinfo)
1086 destroy_loop_vec_info (inner_loop_vinfo, true);
1090 if (!number_of_iterations)
1092 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1094 "not vectorized: number of iterations cannot be computed.");
1095 if (inner_loop_vinfo)
1096 destroy_loop_vec_info (inner_loop_vinfo, true);
1100 if (chrec_contains_undetermined (number_of_iterations))
1102 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1103 fprintf (vect_dump, "Infinite number of iterations.");
1104 if (inner_loop_vinfo)
1105 destroy_loop_vec_info (inner_loop_vinfo, true);
1109 if (!NITERS_KNOWN_P (number_of_iterations))
1111 if (vect_print_dump_info (REPORT_DETAILS))
1113 fprintf (vect_dump, "Symbolic number of iterations is ");
1114 print_generic_expr (vect_dump, number_of_iterations, TDF_DETAILS);
1117 else if (TREE_INT_CST_LOW (number_of_iterations) == 0)
1119 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1120 fprintf (vect_dump, "not vectorized: number of iterations = 0.");
1121 if (inner_loop_vinfo)
1122 destroy_loop_vec_info (inner_loop_vinfo, false);
1126 loop_vinfo = new_loop_vec_info (loop);
1127 LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
1128 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo) = number_of_iterations;
1130 STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond)) = loop_exit_ctrl_vec_info_type;
1132 /* CHECKME: May want to keep it around it in the future. */
1133 if (inner_loop_vinfo)
1134 destroy_loop_vec_info (inner_loop_vinfo, false);
1136 gcc_assert (!loop->aux);
1137 loop->aux = loop_vinfo;
1142 /* Get cost by calling cost target builtin. */
1145 vect_get_cost (enum vect_cost_for_stmt type_of_cost)
1147 tree dummy_type = NULL;
1150 return targetm.vectorize.builtin_vectorization_cost (type_of_cost,
1155 /* Function vect_analyze_loop_operations.
1157 Scan the loop stmts and make sure they are all vectorizable. */
1160 vect_analyze_loop_operations (loop_vec_info loop_vinfo, bool slp)
1162 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1163 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1164 int nbbs = loop->num_nodes;
1165 gimple_stmt_iterator si;
1166 unsigned int vectorization_factor = 0;
1169 stmt_vec_info stmt_info;
1170 bool need_to_vectorize = false;
1171 int min_profitable_iters;
1172 int min_scalar_loop_bound;
1174 bool only_slp_in_loop = true, ok;
1176 if (vect_print_dump_info (REPORT_DETAILS))
1177 fprintf (vect_dump, "=== vect_analyze_loop_operations ===");
1179 gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo));
1180 vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1183 /* If all the stmts in the loop can be SLPed, we perform only SLP, and
1184 vectorization factor of the loop is the unrolling factor required by
1185 the SLP instances. If that unrolling factor is 1, we say, that we
1186 perform pure SLP on loop - cross iteration parallelism is not
1188 for (i = 0; i < nbbs; i++)
1190 basic_block bb = bbs[i];
1191 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1193 gimple stmt = gsi_stmt (si);
1194 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1195 gcc_assert (stmt_info);
1196 if ((STMT_VINFO_RELEVANT_P (stmt_info)
1197 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info)))
1198 && !PURE_SLP_STMT (stmt_info))
1199 /* STMT needs both SLP and loop-based vectorization. */
1200 only_slp_in_loop = false;
1204 if (only_slp_in_loop)
1205 vectorization_factor = LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo);
1207 vectorization_factor = least_common_multiple (vectorization_factor,
1208 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo));
1210 LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
1211 if (vect_print_dump_info (REPORT_DETAILS))
1212 fprintf (vect_dump, "Updating vectorization factor to %d ",
1213 vectorization_factor);
1216 for (i = 0; i < nbbs; i++)
1218 basic_block bb = bbs[i];
1220 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
1222 phi = gsi_stmt (si);
1225 stmt_info = vinfo_for_stmt (phi);
1226 if (vect_print_dump_info (REPORT_DETAILS))
1228 fprintf (vect_dump, "examining phi: ");
1229 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
1232 /* Inner-loop loop-closed exit phi in outer-loop vectorization
1233 (i.e., a phi in the tail of the outer-loop). */
1234 if (! is_loop_header_bb_p (bb))
1236 /* FORNOW: we currently don't support the case that these phis
1237 are not used in the outerloop (unless it is double reduction,
1238 i.e., this phi is vect_reduction_def), cause this case
1239 requires to actually do something here. */
1240 if ((!STMT_VINFO_RELEVANT_P (stmt_info)
1241 || STMT_VINFO_LIVE_P (stmt_info))
1242 && STMT_VINFO_DEF_TYPE (stmt_info)
1243 != vect_double_reduction_def)
1245 if (vect_print_dump_info (REPORT_DETAILS))
1247 "Unsupported loop-closed phi in outer-loop.");
1251 /* If PHI is used in the outer loop, we check that its operand
1252 is defined in the inner loop. */
1253 if (STMT_VINFO_RELEVANT_P (stmt_info))
1258 if (gimple_phi_num_args (phi) != 1)
1261 phi_op = PHI_ARG_DEF (phi, 0);
1262 if (TREE_CODE (phi_op) != SSA_NAME)
1265 op_def_stmt = SSA_NAME_DEF_STMT (phi_op);
1266 if (!op_def_stmt || !vinfo_for_stmt (op_def_stmt))
1269 if (STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt))
1270 != vect_used_in_outer
1271 && STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt))
1272 != vect_used_in_outer_by_reduction)
1279 gcc_assert (stmt_info);
1281 if (STMT_VINFO_LIVE_P (stmt_info))
1283 /* FORNOW: not yet supported. */
1284 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1285 fprintf (vect_dump, "not vectorized: value used after loop.");
1289 if (STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_scope
1290 && STMT_VINFO_DEF_TYPE (stmt_info) != vect_induction_def)
1292 /* A scalar-dependence cycle that we don't support. */
1293 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1294 fprintf (vect_dump, "not vectorized: scalar dependence cycle.");
1298 if (STMT_VINFO_RELEVANT_P (stmt_info))
1300 need_to_vectorize = true;
1301 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def)
1302 ok = vectorizable_induction (phi, NULL, NULL);
1307 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1310 "not vectorized: relevant phi not supported: ");
1311 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
1317 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1319 gimple stmt = gsi_stmt (si);
1320 if (!vect_analyze_stmt (stmt, &need_to_vectorize, NULL))
1325 /* All operations in the loop are either irrelevant (deal with loop
1326 control, or dead), or only used outside the loop and can be moved
1327 out of the loop (e.g. invariants, inductions). The loop can be
1328 optimized away by scalar optimizations. We're better off not
1329 touching this loop. */
1330 if (!need_to_vectorize)
1332 if (vect_print_dump_info (REPORT_DETAILS))
1334 "All the computation can be taken out of the loop.");
1335 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1337 "not vectorized: redundant loop. no profit to vectorize.");
1341 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1342 && vect_print_dump_info (REPORT_DETAILS))
1344 "vectorization_factor = %d, niters = " HOST_WIDE_INT_PRINT_DEC,
1345 vectorization_factor, LOOP_VINFO_INT_NITERS (loop_vinfo));
1347 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1348 && (LOOP_VINFO_INT_NITERS (loop_vinfo) < vectorization_factor))
1350 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1351 fprintf (vect_dump, "not vectorized: iteration count too small.");
1352 if (vect_print_dump_info (REPORT_DETAILS))
1353 fprintf (vect_dump,"not vectorized: iteration count smaller than "
1354 "vectorization factor.");
1358 /* Analyze cost. Decide if worth while to vectorize. */
1360 /* Once VF is set, SLP costs should be updated since the number of created
1361 vector stmts depends on VF. */
1362 vect_update_slp_costs_according_to_vf (loop_vinfo);
1364 min_profitable_iters = vect_estimate_min_profitable_iters (loop_vinfo);
1365 LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo) = min_profitable_iters;
1367 if (min_profitable_iters < 0)
1369 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1370 fprintf (vect_dump, "not vectorized: vectorization not profitable.");
1371 if (vect_print_dump_info (REPORT_DETAILS))
1372 fprintf (vect_dump, "not vectorized: vector version will never be "
1377 min_scalar_loop_bound = ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND)
1378 * vectorization_factor) - 1);
1380 /* Use the cost model only if it is more conservative than user specified
1383 th = (unsigned) min_scalar_loop_bound;
1384 if (min_profitable_iters
1385 && (!min_scalar_loop_bound
1386 || min_profitable_iters > min_scalar_loop_bound))
1387 th = (unsigned) min_profitable_iters;
1389 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1390 && LOOP_VINFO_INT_NITERS (loop_vinfo) <= th)
1392 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1393 fprintf (vect_dump, "not vectorized: vectorization not "
1395 if (vect_print_dump_info (REPORT_DETAILS))
1396 fprintf (vect_dump, "not vectorized: iteration count smaller than "
1397 "user specified loop bound parameter or minimum "
1398 "profitable iterations (whichever is more conservative).");
1402 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1403 || LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0
1404 || LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo))
1406 if (vect_print_dump_info (REPORT_DETAILS))
1407 fprintf (vect_dump, "epilog loop required.");
1408 if (!vect_can_advance_ivs_p (loop_vinfo))
1410 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1412 "not vectorized: can't create epilog loop 1.");
1415 if (!slpeel_can_duplicate_loop_p (loop, single_exit (loop)))
1417 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1419 "not vectorized: can't create epilog loop 2.");
1428 /* Function vect_analyze_loop_2.
1430 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1431 for it. The different analyses will record information in the
1432 loop_vec_info struct. */
1434 vect_analyze_loop_2 (loop_vec_info loop_vinfo)
1436 bool ok, dummy, slp = false;
1437 int max_vf = MAX_VECTORIZATION_FACTOR;
1440 /* Find all data references in the loop (which correspond to vdefs/vuses)
1441 and analyze their evolution in the loop. Also adjust the minimal
1442 vectorization factor according to the loads and stores.
1444 FORNOW: Handle only simple, array references, which
1445 alignment can be forced, and aligned pointer-references. */
1447 ok = vect_analyze_data_refs (loop_vinfo, NULL, &min_vf);
1450 if (vect_print_dump_info (REPORT_DETAILS))
1451 fprintf (vect_dump, "bad data references.");
1455 /* Classify all cross-iteration scalar data-flow cycles.
1456 Cross-iteration cycles caused by virtual phis are analyzed separately. */
1458 vect_analyze_scalar_cycles (loop_vinfo);
1460 vect_pattern_recog (loop_vinfo);
1462 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
1464 ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
1467 if (vect_print_dump_info (REPORT_DETAILS))
1468 fprintf (vect_dump, "unexpected pattern.");
1472 /* Analyze data dependences between the data-refs in the loop
1473 and adjust the maximum vectorization factor according to
1475 FORNOW: fail at the first data dependence that we encounter. */
1477 ok = vect_analyze_data_ref_dependences (loop_vinfo, NULL, &max_vf, &dummy);
1481 if (vect_print_dump_info (REPORT_DETAILS))
1482 fprintf (vect_dump, "bad data dependence.");
1486 ok = vect_determine_vectorization_factor (loop_vinfo);
1489 if (vect_print_dump_info (REPORT_DETAILS))
1490 fprintf (vect_dump, "can't determine vectorization factor.");
1493 if (max_vf < LOOP_VINFO_VECT_FACTOR (loop_vinfo))
1495 if (vect_print_dump_info (REPORT_DETAILS))
1496 fprintf (vect_dump, "bad data dependence.");
1500 /* Analyze the alignment of the data-refs in the loop.
1501 Fail if a data reference is found that cannot be vectorized. */
1503 ok = vect_analyze_data_refs_alignment (loop_vinfo, NULL);
1506 if (vect_print_dump_info (REPORT_DETAILS))
1507 fprintf (vect_dump, "bad data alignment.");
1511 /* Analyze the access patterns of the data-refs in the loop (consecutive,
1512 complex, etc.). FORNOW: Only handle consecutive access pattern. */
1514 ok = vect_analyze_data_ref_accesses (loop_vinfo, NULL);
1517 if (vect_print_dump_info (REPORT_DETAILS))
1518 fprintf (vect_dump, "bad data access.");
1522 /* Prune the list of ddrs to be tested at run-time by versioning for alias.
1523 It is important to call pruning after vect_analyze_data_ref_accesses,
1524 since we use grouping information gathered by interleaving analysis. */
1525 ok = vect_prune_runtime_alias_test_list (loop_vinfo);
1528 if (vect_print_dump_info (REPORT_DETAILS))
1529 fprintf (vect_dump, "too long list of versioning for alias "
1534 /* This pass will decide on using loop versioning and/or loop peeling in
1535 order to enhance the alignment of data references in the loop. */
1537 ok = vect_enhance_data_refs_alignment (loop_vinfo);
1540 if (vect_print_dump_info (REPORT_DETAILS))
1541 fprintf (vect_dump, "bad data alignment.");
1545 /* Check the SLP opportunities in the loop, analyze and build SLP trees. */
1546 ok = vect_analyze_slp (loop_vinfo, NULL);
1549 /* Decide which possible SLP instances to SLP. */
1550 slp = vect_make_slp_decision (loop_vinfo);
1552 /* Find stmts that need to be both vectorized and SLPed. */
1553 vect_detect_hybrid_slp (loop_vinfo);
1558 /* Scan all the operations in the loop and make sure they are
1561 ok = vect_analyze_loop_operations (loop_vinfo, slp);
1564 if (vect_print_dump_info (REPORT_DETAILS))
1565 fprintf (vect_dump, "bad operation or unsupported loop bound.");
1572 /* Function vect_analyze_loop.
1574 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1575 for it. The different analyses will record information in the
1576 loop_vec_info struct. */
1578 vect_analyze_loop (struct loop *loop)
1580 loop_vec_info loop_vinfo;
1581 unsigned int vector_sizes;
1583 /* Autodetect first vector size we try. */
1584 current_vector_size = 0;
1585 vector_sizes = targetm.vectorize.autovectorize_vector_sizes ();
1587 if (vect_print_dump_info (REPORT_DETAILS))
1588 fprintf (vect_dump, "===== analyze_loop_nest =====");
1590 if (loop_outer (loop)
1591 && loop_vec_info_for_loop (loop_outer (loop))
1592 && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop))))
1594 if (vect_print_dump_info (REPORT_DETAILS))
1595 fprintf (vect_dump, "outer-loop already vectorized.");
1601 /* Check the CFG characteristics of the loop (nesting, entry/exit). */
1602 loop_vinfo = vect_analyze_loop_form (loop);
1605 if (vect_print_dump_info (REPORT_DETAILS))
1606 fprintf (vect_dump, "bad loop form.");
1610 if (vect_analyze_loop_2 (loop_vinfo))
1612 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1;
1617 destroy_loop_vec_info (loop_vinfo, true);
1619 vector_sizes &= ~current_vector_size;
1620 if (vector_sizes == 0
1621 || current_vector_size == 0)
1624 /* Try the next biggest vector size. */
1625 current_vector_size = 1 << floor_log2 (vector_sizes);
1626 if (vect_print_dump_info (REPORT_DETAILS))
1627 fprintf (vect_dump, "***** Re-trying analysis with "
1628 "vector size %d\n", current_vector_size);
1633 /* Function reduction_code_for_scalar_code
1636 CODE - tree_code of a reduction operations.
1639 REDUC_CODE - the corresponding tree-code to be used to reduce the
1640 vector of partial results into a single scalar result (which
1641 will also reside in a vector) or ERROR_MARK if the operation is
1642 a supported reduction operation, but does not have such tree-code.
1644 Return FALSE if CODE currently cannot be vectorized as reduction. */
1647 reduction_code_for_scalar_code (enum tree_code code,
1648 enum tree_code *reduc_code)
1653 *reduc_code = REDUC_MAX_EXPR;
1657 *reduc_code = REDUC_MIN_EXPR;
1661 *reduc_code = REDUC_PLUS_EXPR;
1669 *reduc_code = ERROR_MARK;
1678 /* Error reporting helper for vect_is_simple_reduction below. GIMPLE statement
1679 STMT is printed with a message MSG. */
1682 report_vect_op (gimple stmt, const char *msg)
1684 fprintf (vect_dump, "%s", msg);
1685 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
1689 /* Detect SLP reduction of the form:
1699 PHI is the reduction phi node (#a1 = phi <a5, a0> above)
1700 FIRST_STMT is the first reduction stmt in the chain
1701 (a2 = operation (a1)).
1703 Return TRUE if a reduction chain was detected. */
1706 vect_is_slp_reduction (loop_vec_info loop_info, gimple phi, gimple first_stmt)
1708 struct loop *loop = (gimple_bb (phi))->loop_father;
1709 struct loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
1710 enum tree_code code;
1711 gimple current_stmt = NULL, loop_use_stmt = NULL, first, next_stmt;
1712 stmt_vec_info use_stmt_info, current_stmt_info;
1714 imm_use_iterator imm_iter;
1715 use_operand_p use_p;
1716 int nloop_uses, size = 0;
1719 if (loop != vect_loop)
1722 lhs = PHI_RESULT (phi);
1723 code = gimple_assign_rhs_code (first_stmt);
1727 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
1729 gimple use_stmt = USE_STMT (use_p);
1730 if (is_gimple_debug (use_stmt))
1733 use_stmt = USE_STMT (use_p);
1735 /* Check if we got back to the reduction phi. */
1736 if (use_stmt == phi)
1738 loop_use_stmt = use_stmt;
1743 if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt))
1744 && vinfo_for_stmt (use_stmt)
1745 && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (use_stmt)))
1747 loop_use_stmt = use_stmt;
1758 /* We reached a statement with no loop uses. */
1759 if (nloop_uses == 0)
1762 /* This is a loop exit phi, and we haven't reached the reduction phi. */
1763 if (gimple_code (loop_use_stmt) == GIMPLE_PHI)
1766 if (!is_gimple_assign (loop_use_stmt)
1767 || code != gimple_assign_rhs_code (loop_use_stmt)
1768 || !flow_bb_inside_loop_p (loop, gimple_bb (loop_use_stmt)))
1771 /* Insert USE_STMT into reduction chain. */
1772 use_stmt_info = vinfo_for_stmt (loop_use_stmt);
1775 current_stmt_info = vinfo_for_stmt (current_stmt);
1776 GROUP_NEXT_ELEMENT (current_stmt_info) = loop_use_stmt;
1777 GROUP_FIRST_ELEMENT (use_stmt_info)
1778 = GROUP_FIRST_ELEMENT (current_stmt_info);
1781 GROUP_FIRST_ELEMENT (use_stmt_info) = loop_use_stmt;
1783 lhs = gimple_assign_lhs (loop_use_stmt);
1784 current_stmt = loop_use_stmt;
1788 if (!found || loop_use_stmt != phi || size < 2)
1791 /* Swap the operands, if needed, to make the reduction operand be the second
1793 lhs = PHI_RESULT (phi);
1794 next_stmt = GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt));
1797 if (gimple_assign_rhs2 (next_stmt) == lhs)
1799 tree op = gimple_assign_rhs1 (next_stmt);
1800 gimple def_stmt = NULL;
1802 if (TREE_CODE (op) == SSA_NAME)
1803 def_stmt = SSA_NAME_DEF_STMT (op);
1805 /* Check that the other def is either defined in the loop
1806 ("vect_internal_def"), or it's an induction (defined by a
1807 loop-header phi-node). */
1809 && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
1810 && (is_gimple_assign (def_stmt)
1811 || is_gimple_call (def_stmt)
1812 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
1813 == vect_induction_def
1814 || (gimple_code (def_stmt) == GIMPLE_PHI
1815 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
1816 == vect_internal_def
1817 && !is_loop_header_bb_p (gimple_bb (def_stmt)))))
1819 lhs = gimple_assign_lhs (next_stmt);
1820 next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
1828 tree op = gimple_assign_rhs2 (next_stmt);
1829 gimple def_stmt = NULL;
1831 if (TREE_CODE (op) == SSA_NAME)
1832 def_stmt = SSA_NAME_DEF_STMT (op);
1834 /* Check that the other def is either defined in the loop
1835 ("vect_internal_def"), or it's an induction (defined by a
1836 loop-header phi-node). */
1838 && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
1839 && (is_gimple_assign (def_stmt)
1840 || is_gimple_call (def_stmt)
1841 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
1842 == vect_induction_def
1843 || (gimple_code (def_stmt) == GIMPLE_PHI
1844 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
1845 == vect_internal_def
1846 && !is_loop_header_bb_p (gimple_bb (def_stmt)))))
1848 if (vect_print_dump_info (REPORT_DETAILS))
1850 fprintf (vect_dump, "swapping oprnds: ");
1851 print_gimple_stmt (vect_dump, next_stmt, 0, TDF_SLIM);
1854 swap_tree_operands (next_stmt,
1855 gimple_assign_rhs1_ptr (next_stmt),
1856 gimple_assign_rhs2_ptr (next_stmt));
1857 mark_symbols_for_renaming (next_stmt);
1863 lhs = gimple_assign_lhs (next_stmt);
1864 next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
1867 /* Save the chain for further analysis in SLP detection. */
1868 first = GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt));
1869 VEC_safe_push (gimple, heap, LOOP_VINFO_REDUCTION_CHAINS (loop_info), first);
1870 GROUP_SIZE (vinfo_for_stmt (first)) = size;
1876 /* Function vect_is_simple_reduction_1
1878 (1) Detect a cross-iteration def-use cycle that represents a simple
1879 reduction computation. We look for the following pattern:
1884 a2 = operation (a3, a1)
1887 1. operation is commutative and associative and it is safe to
1888 change the order of the computation (if CHECK_REDUCTION is true)
1889 2. no uses for a2 in the loop (a2 is used out of the loop)
1890 3. no uses of a1 in the loop besides the reduction operation
1891 4. no uses of a1 outside the loop.
1893 Conditions 1,4 are tested here.
1894 Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
1896 (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
1897 nested cycles, if CHECK_REDUCTION is false.
1899 (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
1903 inner loop (def of a3)
1906 If MODIFY is true it tries also to rework the code in-place to enable
1907 detection of more reduction patterns. For the time being we rewrite
1908 "res -= RHS" into "rhs += -RHS" when it seems worthwhile.
1912 vect_is_simple_reduction_1 (loop_vec_info loop_info, gimple phi,
1913 bool check_reduction, bool *double_reduc,
1916 struct loop *loop = (gimple_bb (phi))->loop_father;
1917 struct loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
1918 edge latch_e = loop_latch_edge (loop);
1919 tree loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
1920 gimple def_stmt, def1 = NULL, def2 = NULL;
1921 enum tree_code orig_code, code;
1922 tree op1, op2, op3 = NULL_TREE, op4 = NULL_TREE;
1926 imm_use_iterator imm_iter;
1927 use_operand_p use_p;
1930 *double_reduc = false;
1932 /* If CHECK_REDUCTION is true, we assume inner-most loop vectorization,
1933 otherwise, we assume outer loop vectorization. */
1934 gcc_assert ((check_reduction && loop == vect_loop)
1935 || (!check_reduction && flow_loop_nested_p (vect_loop, loop)));
1937 name = PHI_RESULT (phi);
1939 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
1941 gimple use_stmt = USE_STMT (use_p);
1942 if (is_gimple_debug (use_stmt))
1945 if (!flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
1947 if (vect_print_dump_info (REPORT_DETAILS))
1948 fprintf (vect_dump, "intermediate value used outside loop.");
1953 if (vinfo_for_stmt (use_stmt)
1954 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt)))
1958 if (vect_print_dump_info (REPORT_DETAILS))
1959 fprintf (vect_dump, "reduction used in loop.");
1964 if (TREE_CODE (loop_arg) != SSA_NAME)
1966 if (vect_print_dump_info (REPORT_DETAILS))
1968 fprintf (vect_dump, "reduction: not ssa_name: ");
1969 print_generic_expr (vect_dump, loop_arg, TDF_SLIM);
1974 def_stmt = SSA_NAME_DEF_STMT (loop_arg);
1977 if (vect_print_dump_info (REPORT_DETAILS))
1978 fprintf (vect_dump, "reduction: no def_stmt.");
1982 if (!is_gimple_assign (def_stmt) && gimple_code (def_stmt) != GIMPLE_PHI)
1984 if (vect_print_dump_info (REPORT_DETAILS))
1985 print_gimple_stmt (vect_dump, def_stmt, 0, TDF_SLIM);
1989 if (is_gimple_assign (def_stmt))
1991 name = gimple_assign_lhs (def_stmt);
1996 name = PHI_RESULT (def_stmt);
2001 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
2003 gimple use_stmt = USE_STMT (use_p);
2004 if (is_gimple_debug (use_stmt))
2006 if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt))
2007 && vinfo_for_stmt (use_stmt)
2008 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt)))
2012 if (vect_print_dump_info (REPORT_DETAILS))
2013 fprintf (vect_dump, "reduction used in loop.");
2018 /* If DEF_STMT is a phi node itself, we expect it to have a single argument
2019 defined in the inner loop. */
2022 op1 = PHI_ARG_DEF (def_stmt, 0);
2024 if (gimple_phi_num_args (def_stmt) != 1
2025 || TREE_CODE (op1) != SSA_NAME)
2027 if (vect_print_dump_info (REPORT_DETAILS))
2028 fprintf (vect_dump, "unsupported phi node definition.");
2033 def1 = SSA_NAME_DEF_STMT (op1);
2034 if (flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
2036 && flow_bb_inside_loop_p (loop->inner, gimple_bb (def1))
2037 && is_gimple_assign (def1))
2039 if (vect_print_dump_info (REPORT_DETAILS))
2040 report_vect_op (def_stmt, "detected double reduction: ");
2042 *double_reduc = true;
2049 code = orig_code = gimple_assign_rhs_code (def_stmt);
2051 /* We can handle "res -= x[i]", which is non-associative by
2052 simply rewriting this into "res += -x[i]". Avoid changing
2053 gimple instruction for the first simple tests and only do this
2054 if we're allowed to change code at all. */
2055 if (code == MINUS_EXPR
2057 && (op1 = gimple_assign_rhs1 (def_stmt))
2058 && TREE_CODE (op1) == SSA_NAME
2059 && SSA_NAME_DEF_STMT (op1) == phi)
2063 && (!commutative_tree_code (code) || !associative_tree_code (code)))
2065 if (vect_print_dump_info (REPORT_DETAILS))
2066 report_vect_op (def_stmt, "reduction: not commutative/associative: ");
2070 if (get_gimple_rhs_class (code) != GIMPLE_BINARY_RHS)
2072 if (code != COND_EXPR)
2074 if (vect_print_dump_info (REPORT_DETAILS))
2075 report_vect_op (def_stmt, "reduction: not binary operation: ");
2080 op3 = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 0);
2081 if (COMPARISON_CLASS_P (op3))
2083 op4 = TREE_OPERAND (op3, 1);
2084 op3 = TREE_OPERAND (op3, 0);
2087 op1 = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 1);
2088 op2 = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 2);
2090 if (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op2) != SSA_NAME)
2092 if (vect_print_dump_info (REPORT_DETAILS))
2093 report_vect_op (def_stmt, "reduction: uses not ssa_names: ");
2100 op1 = gimple_assign_rhs1 (def_stmt);
2101 op2 = gimple_assign_rhs2 (def_stmt);
2103 if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
2105 if (vect_print_dump_info (REPORT_DETAILS))
2106 report_vect_op (def_stmt, "reduction: uses not ssa_names: ");
2112 type = TREE_TYPE (gimple_assign_lhs (def_stmt));
2113 if ((TREE_CODE (op1) == SSA_NAME
2114 && !types_compatible_p (type,TREE_TYPE (op1)))
2115 || (TREE_CODE (op2) == SSA_NAME
2116 && !types_compatible_p (type, TREE_TYPE (op2)))
2117 || (op3 && TREE_CODE (op3) == SSA_NAME
2118 && !types_compatible_p (type, TREE_TYPE (op3)))
2119 || (op4 && TREE_CODE (op4) == SSA_NAME
2120 && !types_compatible_p (type, TREE_TYPE (op4))))
2122 if (vect_print_dump_info (REPORT_DETAILS))
2124 fprintf (vect_dump, "reduction: multiple types: operation type: ");
2125 print_generic_expr (vect_dump, type, TDF_SLIM);
2126 fprintf (vect_dump, ", operands types: ");
2127 print_generic_expr (vect_dump, TREE_TYPE (op1), TDF_SLIM);
2128 fprintf (vect_dump, ",");
2129 print_generic_expr (vect_dump, TREE_TYPE (op2), TDF_SLIM);
2132 fprintf (vect_dump, ",");
2133 print_generic_expr (vect_dump, TREE_TYPE (op3), TDF_SLIM);
2138 fprintf (vect_dump, ",");
2139 print_generic_expr (vect_dump, TREE_TYPE (op4), TDF_SLIM);
2146 /* Check that it's ok to change the order of the computation.
2147 Generally, when vectorizing a reduction we change the order of the
2148 computation. This may change the behavior of the program in some
2149 cases, so we need to check that this is ok. One exception is when
2150 vectorizing an outer-loop: the inner-loop is executed sequentially,
2151 and therefore vectorizing reductions in the inner-loop during
2152 outer-loop vectorization is safe. */
2154 /* CHECKME: check for !flag_finite_math_only too? */
2155 if (SCALAR_FLOAT_TYPE_P (type) && !flag_associative_math
2158 /* Changing the order of operations changes the semantics. */
2159 if (vect_print_dump_info (REPORT_DETAILS))
2160 report_vect_op (def_stmt, "reduction: unsafe fp math optimization: ");
2163 else if (INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_TRAPS (type)
2166 /* Changing the order of operations changes the semantics. */
2167 if (vect_print_dump_info (REPORT_DETAILS))
2168 report_vect_op (def_stmt, "reduction: unsafe int math optimization: ");
2171 else if (SAT_FIXED_POINT_TYPE_P (type) && check_reduction)
2173 /* Changing the order of operations changes the semantics. */
2174 if (vect_print_dump_info (REPORT_DETAILS))
2175 report_vect_op (def_stmt,
2176 "reduction: unsafe fixed-point math optimization: ");
2180 /* If we detected "res -= x[i]" earlier, rewrite it into
2181 "res += -x[i]" now. If this turns out to be useless reassoc
2182 will clean it up again. */
2183 if (orig_code == MINUS_EXPR)
2185 tree rhs = gimple_assign_rhs2 (def_stmt);
2186 tree negrhs = make_ssa_name (SSA_NAME_VAR (rhs), NULL);
2187 gimple negate_stmt = gimple_build_assign_with_ops (NEGATE_EXPR, negrhs,
2189 gimple_stmt_iterator gsi = gsi_for_stmt (def_stmt);
2190 set_vinfo_for_stmt (negate_stmt, new_stmt_vec_info (negate_stmt,
2192 gsi_insert_before (&gsi, negate_stmt, GSI_NEW_STMT);
2193 gimple_assign_set_rhs2 (def_stmt, negrhs);
2194 gimple_assign_set_rhs_code (def_stmt, PLUS_EXPR);
2195 update_stmt (def_stmt);
2198 /* Reduction is safe. We're dealing with one of the following:
2199 1) integer arithmetic and no trapv
2200 2) floating point arithmetic, and special flags permit this optimization
2201 3) nested cycle (i.e., outer loop vectorization). */
2202 if (TREE_CODE (op1) == SSA_NAME)
2203 def1 = SSA_NAME_DEF_STMT (op1);
2205 if (TREE_CODE (op2) == SSA_NAME)
2206 def2 = SSA_NAME_DEF_STMT (op2);
2208 if (code != COND_EXPR
2209 && (!def1 || !def2 || gimple_nop_p (def1) || gimple_nop_p (def2)))
2211 if (vect_print_dump_info (REPORT_DETAILS))
2212 report_vect_op (def_stmt, "reduction: no defs for operands: ");
2216 /* Check that one def is the reduction def, defined by PHI,
2217 the other def is either defined in the loop ("vect_internal_def"),
2218 or it's an induction (defined by a loop-header phi-node). */
2220 if (def2 && def2 == phi
2221 && (code == COND_EXPR
2222 || (def1 && flow_bb_inside_loop_p (loop, gimple_bb (def1))
2223 && (is_gimple_assign (def1)
2224 || is_gimple_call (def1)
2225 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1))
2226 == vect_induction_def
2227 || (gimple_code (def1) == GIMPLE_PHI
2228 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1))
2229 == vect_internal_def
2230 && !is_loop_header_bb_p (gimple_bb (def1)))))))
2232 if (vect_print_dump_info (REPORT_DETAILS))
2233 report_vect_op (def_stmt, "detected reduction: ");
2237 if (def1 && def1 == phi
2238 && (code == COND_EXPR
2239 || (def2 && flow_bb_inside_loop_p (loop, gimple_bb (def2))
2240 && (is_gimple_assign (def2)
2241 || is_gimple_call (def2)
2242 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2))
2243 == vect_induction_def
2244 || (gimple_code (def2) == GIMPLE_PHI
2245 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2))
2246 == vect_internal_def
2247 && !is_loop_header_bb_p (gimple_bb (def2)))))))
2249 if (check_reduction)
2251 /* Swap operands (just for simplicity - so that the rest of the code
2252 can assume that the reduction variable is always the last (second)
2254 if (vect_print_dump_info (REPORT_DETAILS))
2255 report_vect_op (def_stmt,
2256 "detected reduction: need to swap operands: ");
2258 swap_tree_operands (def_stmt, gimple_assign_rhs1_ptr (def_stmt),
2259 gimple_assign_rhs2_ptr (def_stmt));
2263 if (vect_print_dump_info (REPORT_DETAILS))
2264 report_vect_op (def_stmt, "detected reduction: ");
2270 /* Try to find SLP reduction chain. */
2271 if (check_reduction && vect_is_slp_reduction (loop_info, phi, def_stmt))
2273 if (vect_print_dump_info (REPORT_DETAILS))
2274 report_vect_op (def_stmt, "reduction: detected reduction chain: ");
2279 if (vect_print_dump_info (REPORT_DETAILS))
2280 report_vect_op (def_stmt, "reduction: unknown pattern: ");
2285 /* Wrapper around vect_is_simple_reduction_1, that won't modify code
2286 in-place. Arguments as there. */
2289 vect_is_simple_reduction (loop_vec_info loop_info, gimple phi,
2290 bool check_reduction, bool *double_reduc)
2292 return vect_is_simple_reduction_1 (loop_info, phi, check_reduction,
2293 double_reduc, false);
2296 /* Wrapper around vect_is_simple_reduction_1, which will modify code
2297 in-place if it enables detection of more reductions. Arguments
2301 vect_force_simple_reduction (loop_vec_info loop_info, gimple phi,
2302 bool check_reduction, bool *double_reduc)
2304 return vect_is_simple_reduction_1 (loop_info, phi, check_reduction,
2305 double_reduc, true);
2308 /* Calculate the cost of one scalar iteration of the loop. */
2310 vect_get_single_scalar_iteraion_cost (loop_vec_info loop_vinfo)
2312 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2313 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
2314 int nbbs = loop->num_nodes, factor, scalar_single_iter_cost = 0;
2315 int innerloop_iters, i, stmt_cost;
2317 /* Count statements in scalar loop. Using this as scalar cost for a single
2320 TODO: Add outer loop support.
2322 TODO: Consider assigning different costs to different scalar
2326 innerloop_iters = 1;
2328 innerloop_iters = 50; /* FIXME */
2330 for (i = 0; i < nbbs; i++)
2332 gimple_stmt_iterator si;
2333 basic_block bb = bbs[i];
2335 if (bb->loop_father == loop->inner)
2336 factor = innerloop_iters;
2340 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
2342 gimple stmt = gsi_stmt (si);
2343 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2345 if (!is_gimple_assign (stmt) && !is_gimple_call (stmt))
2348 /* Skip stmts that are not vectorized inside the loop. */
2350 && !STMT_VINFO_RELEVANT_P (stmt_info)
2351 && (!STMT_VINFO_LIVE_P (stmt_info)
2352 || STMT_VINFO_DEF_TYPE (stmt_info) != vect_reduction_def))
2355 if (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt)))
2357 if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt))))
2358 stmt_cost = vect_get_cost (scalar_load);
2360 stmt_cost = vect_get_cost (scalar_store);
2363 stmt_cost = vect_get_cost (scalar_stmt);
2365 scalar_single_iter_cost += stmt_cost * factor;
2368 return scalar_single_iter_cost;
2371 /* Calculate cost of peeling the loop PEEL_ITERS_PROLOGUE times. */
2373 vect_get_known_peeling_cost (loop_vec_info loop_vinfo, int peel_iters_prologue,
2374 int *peel_iters_epilogue,
2375 int scalar_single_iter_cost)
2377 int peel_guard_costs = 0;
2378 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2380 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
2382 *peel_iters_epilogue = vf/2;
2383 if (vect_print_dump_info (REPORT_COST))
2384 fprintf (vect_dump, "cost model: "
2385 "epilogue peel iters set to vf/2 because "
2386 "loop iterations are unknown .");
2388 /* If peeled iterations are known but number of scalar loop
2389 iterations are unknown, count a taken branch per peeled loop. */
2390 peel_guard_costs = 2 * vect_get_cost (cond_branch_taken);
2394 int niters = LOOP_VINFO_INT_NITERS (loop_vinfo);
2395 peel_iters_prologue = niters < peel_iters_prologue ?
2396 niters : peel_iters_prologue;
2397 *peel_iters_epilogue = (niters - peel_iters_prologue) % vf;
2398 /* If we need to peel for gaps, but no peeling is required, we have to
2399 peel VF iterations. */
2400 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo) && !*peel_iters_epilogue)
2401 *peel_iters_epilogue = vf;
2404 return (peel_iters_prologue * scalar_single_iter_cost)
2405 + (*peel_iters_epilogue * scalar_single_iter_cost)
2409 /* Function vect_estimate_min_profitable_iters
2411 Return the number of iterations required for the vector version of the
2412 loop to be profitable relative to the cost of the scalar version of the
2415 TODO: Take profile info into account before making vectorization
2416 decisions, if available. */
2419 vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo)
2422 int min_profitable_iters;
2423 int peel_iters_prologue;
2424 int peel_iters_epilogue;
2425 int vec_inside_cost = 0;
2426 int vec_outside_cost = 0;
2427 int scalar_single_iter_cost = 0;
2428 int scalar_outside_cost = 0;
2429 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2430 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2431 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
2432 int nbbs = loop->num_nodes;
2433 int npeel = LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo);
2434 int peel_guard_costs = 0;
2435 int innerloop_iters = 0, factor;
2436 VEC (slp_instance, heap) *slp_instances;
2437 slp_instance instance;
2439 /* Cost model disabled. */
2440 if (!flag_vect_cost_model)
2442 if (vect_print_dump_info (REPORT_COST))
2443 fprintf (vect_dump, "cost model disabled.");
2447 /* Requires loop versioning tests to handle misalignment. */
2448 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo))
2450 /* FIXME: Make cost depend on complexity of individual check. */
2452 VEC_length (gimple, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
2453 if (vect_print_dump_info (REPORT_COST))
2454 fprintf (vect_dump, "cost model: Adding cost of checks for loop "
2455 "versioning to treat misalignment.\n");
2458 /* Requires loop versioning with alias checks. */
2459 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2461 /* FIXME: Make cost depend on complexity of individual check. */
2463 VEC_length (ddr_p, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo));
2464 if (vect_print_dump_info (REPORT_COST))
2465 fprintf (vect_dump, "cost model: Adding cost of checks for loop "
2466 "versioning aliasing.\n");
2469 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
2470 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2471 vec_outside_cost += vect_get_cost (cond_branch_taken);
2473 /* Count statements in scalar loop. Using this as scalar cost for a single
2476 TODO: Add outer loop support.
2478 TODO: Consider assigning different costs to different scalar
2483 innerloop_iters = 50; /* FIXME */
2485 for (i = 0; i < nbbs; i++)
2487 gimple_stmt_iterator si;
2488 basic_block bb = bbs[i];
2490 if (bb->loop_father == loop->inner)
2491 factor = innerloop_iters;
2495 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
2497 gimple stmt = gsi_stmt (si);
2498 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2499 /* Skip stmts that are not vectorized inside the loop. */
2500 if (!STMT_VINFO_RELEVANT_P (stmt_info)
2501 && (!STMT_VINFO_LIVE_P (stmt_info)
2502 || STMT_VINFO_DEF_TYPE (stmt_info) != vect_reduction_def))
2504 vec_inside_cost += STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info) * factor;
2505 /* FIXME: for stmts in the inner-loop in outer-loop vectorization,
2506 some of the "outside" costs are generated inside the outer-loop. */
2507 vec_outside_cost += STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info);
2511 scalar_single_iter_cost = vect_get_single_scalar_iteraion_cost (loop_vinfo);
2513 /* Add additional cost for the peeled instructions in prologue and epilogue
2516 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
2517 at compile-time - we assume it's vf/2 (the worst would be vf-1).
2519 TODO: Build an expression that represents peel_iters for prologue and
2520 epilogue to be used in a run-time test. */
2524 peel_iters_prologue = vf/2;
2525 if (vect_print_dump_info (REPORT_COST))
2526 fprintf (vect_dump, "cost model: "
2527 "prologue peel iters set to vf/2.");
2529 /* If peeling for alignment is unknown, loop bound of main loop becomes
2531 peel_iters_epilogue = vf/2;
2532 if (vect_print_dump_info (REPORT_COST))
2533 fprintf (vect_dump, "cost model: "
2534 "epilogue peel iters set to vf/2 because "
2535 "peeling for alignment is unknown .");
2537 /* If peeled iterations are unknown, count a taken branch and a not taken
2538 branch per peeled loop. Even if scalar loop iterations are known,
2539 vector iterations are not known since peeled prologue iterations are
2540 not known. Hence guards remain the same. */
2541 peel_guard_costs += 2 * (vect_get_cost (cond_branch_taken)
2542 + vect_get_cost (cond_branch_not_taken));
2543 vec_outside_cost += (peel_iters_prologue * scalar_single_iter_cost)
2544 + (peel_iters_epilogue * scalar_single_iter_cost)
2549 peel_iters_prologue = npeel;
2550 vec_outside_cost += vect_get_known_peeling_cost (loop_vinfo,
2551 peel_iters_prologue, &peel_iters_epilogue,
2552 scalar_single_iter_cost);
2555 /* FORNOW: The scalar outside cost is incremented in one of the
2558 1. The vectorizer checks for alignment and aliasing and generates
2559 a condition that allows dynamic vectorization. A cost model
2560 check is ANDED with the versioning condition. Hence scalar code
2561 path now has the added cost of the versioning check.
2563 if (cost > th & versioning_check)
2566 Hence run-time scalar is incremented by not-taken branch cost.
2568 2. The vectorizer then checks if a prologue is required. If the
2569 cost model check was not done before during versioning, it has to
2570 be done before the prologue check.
2573 prologue = scalar_iters
2578 if (prologue == num_iters)
2581 Hence the run-time scalar cost is incremented by a taken branch,
2582 plus a not-taken branch, plus a taken branch cost.
2584 3. The vectorizer then checks if an epilogue is required. If the
2585 cost model check was not done before during prologue check, it
2586 has to be done with the epilogue check.
2592 if (prologue == num_iters)
2595 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
2598 Hence the run-time scalar cost should be incremented by 2 taken
2601 TODO: The back end may reorder the BBS's differently and reverse
2602 conditions/branch directions. Change the estimates below to
2603 something more reasonable. */
2605 /* If the number of iterations is known and we do not do versioning, we can
2606 decide whether to vectorize at compile time. Hence the scalar version
2607 do not carry cost model guard costs. */
2608 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
2609 || LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
2610 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2612 /* Cost model check occurs at versioning. */
2613 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
2614 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2615 scalar_outside_cost += vect_get_cost (cond_branch_not_taken);
2618 /* Cost model check occurs at prologue generation. */
2619 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0)
2620 scalar_outside_cost += 2 * vect_get_cost (cond_branch_taken)
2621 + vect_get_cost (cond_branch_not_taken);
2622 /* Cost model check occurs at epilogue generation. */
2624 scalar_outside_cost += 2 * vect_get_cost (cond_branch_taken);
2628 /* Add SLP costs. */
2629 slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
2630 FOR_EACH_VEC_ELT (slp_instance, slp_instances, i, instance)
2632 vec_outside_cost += SLP_INSTANCE_OUTSIDE_OF_LOOP_COST (instance);
2633 vec_inside_cost += SLP_INSTANCE_INSIDE_OF_LOOP_COST (instance);
2636 /* Calculate number of iterations required to make the vector version
2637 profitable, relative to the loop bodies only. The following condition
2639 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
2641 SIC = scalar iteration cost, VIC = vector iteration cost,
2642 VOC = vector outside cost, VF = vectorization factor,
2643 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
2644 SOC = scalar outside cost for run time cost model check. */
2646 if ((scalar_single_iter_cost * vf) > vec_inside_cost)
2648 if (vec_outside_cost <= 0)
2649 min_profitable_iters = 1;
2652 min_profitable_iters = ((vec_outside_cost - scalar_outside_cost) * vf
2653 - vec_inside_cost * peel_iters_prologue
2654 - vec_inside_cost * peel_iters_epilogue)
2655 / ((scalar_single_iter_cost * vf)
2658 if ((scalar_single_iter_cost * vf * min_profitable_iters)
2659 <= ((vec_inside_cost * min_profitable_iters)
2660 + ((vec_outside_cost - scalar_outside_cost) * vf)))
2661 min_profitable_iters++;
2664 /* vector version will never be profitable. */
2667 if (vect_print_dump_info (REPORT_COST))
2668 fprintf (vect_dump, "cost model: the vector iteration cost = %d "
2669 "divided by the scalar iteration cost = %d "
2670 "is greater or equal to the vectorization factor = %d.",
2671 vec_inside_cost, scalar_single_iter_cost, vf);
2675 if (vect_print_dump_info (REPORT_COST))
2677 fprintf (vect_dump, "Cost model analysis: \n");
2678 fprintf (vect_dump, " Vector inside of loop cost: %d\n",
2680 fprintf (vect_dump, " Vector outside of loop cost: %d\n",
2682 fprintf (vect_dump, " Scalar iteration cost: %d\n",
2683 scalar_single_iter_cost);
2684 fprintf (vect_dump, " Scalar outside cost: %d\n", scalar_outside_cost);
2685 fprintf (vect_dump, " prologue iterations: %d\n",
2686 peel_iters_prologue);
2687 fprintf (vect_dump, " epilogue iterations: %d\n",
2688 peel_iters_epilogue);
2689 fprintf (vect_dump, " Calculated minimum iters for profitability: %d\n",
2690 min_profitable_iters);
2693 min_profitable_iters =
2694 min_profitable_iters < vf ? vf : min_profitable_iters;
2696 /* Because the condition we create is:
2697 if (niters <= min_profitable_iters)
2698 then skip the vectorized loop. */
2699 min_profitable_iters--;
2701 if (vect_print_dump_info (REPORT_COST))
2702 fprintf (vect_dump, " Profitability threshold = %d\n",
2703 min_profitable_iters);
2705 return min_profitable_iters;
2709 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
2710 functions. Design better to avoid maintenance issues. */
2712 /* Function vect_model_reduction_cost.
2714 Models cost for a reduction operation, including the vector ops
2715 generated within the strip-mine loop, the initial definition before
2716 the loop, and the epilogue code that must be generated. */
2719 vect_model_reduction_cost (stmt_vec_info stmt_info, enum tree_code reduc_code,
2723 enum tree_code code;
2726 gimple stmt, orig_stmt;
2728 enum machine_mode mode;
2729 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2730 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2733 /* Cost of reduction op inside loop. */
2734 STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info)
2735 += ncopies * vect_get_cost (vector_stmt);
2737 stmt = STMT_VINFO_STMT (stmt_info);
2739 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2741 case GIMPLE_SINGLE_RHS:
2742 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt)) == ternary_op);
2743 reduction_op = TREE_OPERAND (gimple_assign_rhs1 (stmt), 2);
2745 case GIMPLE_UNARY_RHS:
2746 reduction_op = gimple_assign_rhs1 (stmt);
2748 case GIMPLE_BINARY_RHS:
2749 reduction_op = gimple_assign_rhs2 (stmt);
2751 case GIMPLE_TERNARY_RHS:
2752 reduction_op = gimple_assign_rhs3 (stmt);
2758 vectype = get_vectype_for_scalar_type (TREE_TYPE (reduction_op));
2761 if (vect_print_dump_info (REPORT_COST))
2763 fprintf (vect_dump, "unsupported data-type ");
2764 print_generic_expr (vect_dump, TREE_TYPE (reduction_op), TDF_SLIM);
2769 mode = TYPE_MODE (vectype);
2770 orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
2773 orig_stmt = STMT_VINFO_STMT (stmt_info);
2775 code = gimple_assign_rhs_code (orig_stmt);
2777 /* Add in cost for initial definition. */
2778 outer_cost += vect_get_cost (scalar_to_vec);
2780 /* Determine cost of epilogue code.
2782 We have a reduction operator that will reduce the vector in one statement.
2783 Also requires scalar extract. */
2785 if (!nested_in_vect_loop_p (loop, orig_stmt))
2787 if (reduc_code != ERROR_MARK)
2788 outer_cost += vect_get_cost (vector_stmt)
2789 + vect_get_cost (vec_to_scalar);
2792 int vec_size_in_bits = tree_low_cst (TYPE_SIZE (vectype), 1);
2794 TYPE_SIZE (TREE_TYPE (gimple_assign_lhs (orig_stmt)));
2795 int element_bitsize = tree_low_cst (bitsize, 1);
2796 int nelements = vec_size_in_bits / element_bitsize;
2798 optab = optab_for_tree_code (code, vectype, optab_default);
2800 /* We have a whole vector shift available. */
2801 if (VECTOR_MODE_P (mode)
2802 && optab_handler (optab, mode) != CODE_FOR_nothing
2803 && optab_handler (vec_shr_optab, mode) != CODE_FOR_nothing)
2804 /* Final reduction via vector shifts and the reduction operator. Also
2805 requires scalar extract. */
2806 outer_cost += ((exact_log2(nelements) * 2)
2807 * vect_get_cost (vector_stmt)
2808 + vect_get_cost (vec_to_scalar));
2810 /* Use extracts and reduction op for final reduction. For N elements,
2811 we have N extracts and N-1 reduction ops. */
2812 outer_cost += ((nelements + nelements - 1)
2813 * vect_get_cost (vector_stmt));
2817 STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info) = outer_cost;
2819 if (vect_print_dump_info (REPORT_COST))
2820 fprintf (vect_dump, "vect_model_reduction_cost: inside_cost = %d, "
2821 "outside_cost = %d .", STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info),
2822 STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info));
2828 /* Function vect_model_induction_cost.
2830 Models cost for induction operations. */
2833 vect_model_induction_cost (stmt_vec_info stmt_info, int ncopies)
2835 /* loop cost for vec_loop. */
2836 STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info)
2837 = ncopies * vect_get_cost (vector_stmt);
2838 /* prologue cost for vec_init and vec_step. */
2839 STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info)
2840 = 2 * vect_get_cost (scalar_to_vec);
2842 if (vect_print_dump_info (REPORT_COST))
2843 fprintf (vect_dump, "vect_model_induction_cost: inside_cost = %d, "
2844 "outside_cost = %d .", STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info),
2845 STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info));
2849 /* Function get_initial_def_for_induction
2852 STMT - a stmt that performs an induction operation in the loop.
2853 IV_PHI - the initial value of the induction variable
2856 Return a vector variable, initialized with the first VF values of
2857 the induction variable. E.g., for an iv with IV_PHI='X' and
2858 evolution S, for a vector of 4 units, we want to return:
2859 [X, X + S, X + 2*S, X + 3*S]. */
2862 get_initial_def_for_induction (gimple iv_phi)
2864 stmt_vec_info stmt_vinfo = vinfo_for_stmt (iv_phi);
2865 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
2866 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2870 edge pe = loop_preheader_edge (loop);
2871 struct loop *iv_loop;
2873 tree vec, vec_init, vec_step, t;
2877 gimple init_stmt, induction_phi, new_stmt;
2878 tree induc_def, vec_def, vec_dest;
2879 tree init_expr, step_expr;
2880 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2885 stmt_vec_info phi_info = vinfo_for_stmt (iv_phi);
2886 bool nested_in_vect_loop = false;
2887 gimple_seq stmts = NULL;
2888 imm_use_iterator imm_iter;
2889 use_operand_p use_p;
2893 gimple_stmt_iterator si;
2894 basic_block bb = gimple_bb (iv_phi);
2898 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
2899 if (nested_in_vect_loop_p (loop, iv_phi))
2901 nested_in_vect_loop = true;
2902 iv_loop = loop->inner;
2906 gcc_assert (iv_loop == (gimple_bb (iv_phi))->loop_father);
2908 latch_e = loop_latch_edge (iv_loop);
2909 loop_arg = PHI_ARG_DEF_FROM_EDGE (iv_phi, latch_e);
2911 access_fn = analyze_scalar_evolution (iv_loop, PHI_RESULT (iv_phi));
2912 gcc_assert (access_fn);
2913 STRIP_NOPS (access_fn);
2914 ok = vect_is_simple_iv_evolution (iv_loop->num, access_fn,
2915 &init_expr, &step_expr);
2917 pe = loop_preheader_edge (iv_loop);
2919 scalar_type = TREE_TYPE (init_expr);
2920 vectype = get_vectype_for_scalar_type (scalar_type);
2921 resvectype = get_vectype_for_scalar_type (TREE_TYPE (PHI_RESULT (iv_phi)));
2922 gcc_assert (vectype);
2923 nunits = TYPE_VECTOR_SUBPARTS (vectype);
2924 ncopies = vf / nunits;
2926 gcc_assert (phi_info);
2927 gcc_assert (ncopies >= 1);
2929 /* Find the first insertion point in the BB. */
2930 si = gsi_after_labels (bb);
2932 /* Create the vector that holds the initial_value of the induction. */
2933 if (nested_in_vect_loop)
2935 /* iv_loop is nested in the loop to be vectorized. init_expr had already
2936 been created during vectorization of previous stmts. We obtain it
2937 from the STMT_VINFO_VEC_STMT of the defining stmt. */
2938 tree iv_def = PHI_ARG_DEF_FROM_EDGE (iv_phi,
2939 loop_preheader_edge (iv_loop));
2940 vec_init = vect_get_vec_def_for_operand (iv_def, iv_phi, NULL);
2944 /* iv_loop is the loop to be vectorized. Create:
2945 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
2946 new_var = vect_get_new_vect_var (scalar_type, vect_scalar_var, "var_");
2947 add_referenced_var (new_var);
2949 new_name = force_gimple_operand (init_expr, &stmts, false, new_var);
2952 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
2953 gcc_assert (!new_bb);
2957 t = tree_cons (NULL_TREE, new_name, t);
2958 for (i = 1; i < nunits; i++)
2960 /* Create: new_name_i = new_name + step_expr */
2961 enum tree_code code = POINTER_TYPE_P (scalar_type)
2962 ? POINTER_PLUS_EXPR : PLUS_EXPR;
2963 init_stmt = gimple_build_assign_with_ops (code, new_var,
2964 new_name, step_expr);
2965 new_name = make_ssa_name (new_var, init_stmt);
2966 gimple_assign_set_lhs (init_stmt, new_name);
2968 new_bb = gsi_insert_on_edge_immediate (pe, init_stmt);
2969 gcc_assert (!new_bb);
2971 if (vect_print_dump_info (REPORT_DETAILS))
2973 fprintf (vect_dump, "created new init_stmt: ");
2974 print_gimple_stmt (vect_dump, init_stmt, 0, TDF_SLIM);
2976 t = tree_cons (NULL_TREE, new_name, t);
2978 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
2979 vec = build_constructor_from_list (vectype, nreverse (t));
2980 vec_init = vect_init_vector (iv_phi, vec, vectype, NULL);
2984 /* Create the vector that holds the step of the induction. */
2985 if (nested_in_vect_loop)
2986 /* iv_loop is nested in the loop to be vectorized. Generate:
2987 vec_step = [S, S, S, S] */
2988 new_name = step_expr;
2991 /* iv_loop is the loop to be vectorized. Generate:
2992 vec_step = [VF*S, VF*S, VF*S, VF*S] */
2993 expr = build_int_cst (TREE_TYPE (step_expr), vf);
2994 new_name = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr),
2998 t = unshare_expr (new_name);
2999 gcc_assert (CONSTANT_CLASS_P (new_name));
3000 stepvectype = get_vectype_for_scalar_type (TREE_TYPE (new_name));
3001 gcc_assert (stepvectype);
3002 vec = build_vector_from_val (stepvectype, t);
3003 vec_step = vect_init_vector (iv_phi, vec, stepvectype, NULL);
3006 /* Create the following def-use cycle:
3011 vec_iv = PHI <vec_init, vec_loop>
3015 vec_loop = vec_iv + vec_step; */
3017 /* Create the induction-phi that defines the induction-operand. */
3018 vec_dest = vect_get_new_vect_var (vectype, vect_simple_var, "vec_iv_");
3019 add_referenced_var (vec_dest);
3020 induction_phi = create_phi_node (vec_dest, iv_loop->header);
3021 set_vinfo_for_stmt (induction_phi,
3022 new_stmt_vec_info (induction_phi, loop_vinfo, NULL));
3023 induc_def = PHI_RESULT (induction_phi);
3025 /* Create the iv update inside the loop */
3026 new_stmt = gimple_build_assign_with_ops (PLUS_EXPR, vec_dest,
3027 induc_def, vec_step);
3028 vec_def = make_ssa_name (vec_dest, new_stmt);
3029 gimple_assign_set_lhs (new_stmt, vec_def);
3030 gsi_insert_before (&si, new_stmt, GSI_SAME_STMT);
3031 set_vinfo_for_stmt (new_stmt, new_stmt_vec_info (new_stmt, loop_vinfo,
3034 /* Set the arguments of the phi node: */
3035 add_phi_arg (induction_phi, vec_init, pe, UNKNOWN_LOCATION);
3036 add_phi_arg (induction_phi, vec_def, loop_latch_edge (iv_loop),
3040 /* In case that vectorization factor (VF) is bigger than the number
3041 of elements that we can fit in a vectype (nunits), we have to generate
3042 more than one vector stmt - i.e - we need to "unroll" the
3043 vector stmt by a factor VF/nunits. For more details see documentation
3044 in vectorizable_operation. */
3048 stmt_vec_info prev_stmt_vinfo;
3049 /* FORNOW. This restriction should be relaxed. */
3050 gcc_assert (!nested_in_vect_loop);
3052 /* Create the vector that holds the step of the induction. */
3053 expr = build_int_cst (TREE_TYPE (step_expr), nunits);
3054 new_name = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr),
3056 t = unshare_expr (new_name);
3057 gcc_assert (CONSTANT_CLASS_P (new_name));
3058 vec = build_vector_from_val (stepvectype, t);
3059 vec_step = vect_init_vector (iv_phi, vec, stepvectype, NULL);
3061 vec_def = induc_def;
3062 prev_stmt_vinfo = vinfo_for_stmt (induction_phi);
3063 for (i = 1; i < ncopies; i++)
3065 /* vec_i = vec_prev + vec_step */
3066 new_stmt = gimple_build_assign_with_ops (PLUS_EXPR, vec_dest,
3068 vec_def = make_ssa_name (vec_dest, new_stmt);
3069 gimple_assign_set_lhs (new_stmt, vec_def);
3071 gsi_insert_before (&si, new_stmt, GSI_SAME_STMT);
3072 if (!useless_type_conversion_p (resvectype, vectype))
3074 new_stmt = gimple_build_assign_with_ops
3076 vect_get_new_vect_var (resvectype, vect_simple_var,
3078 build1 (VIEW_CONVERT_EXPR, resvectype,
3079 gimple_assign_lhs (new_stmt)), NULL_TREE);
3080 gimple_assign_set_lhs (new_stmt,
3082 (gimple_assign_lhs (new_stmt), new_stmt));
3083 gsi_insert_before (&si, new_stmt, GSI_SAME_STMT);
3085 set_vinfo_for_stmt (new_stmt,
3086 new_stmt_vec_info (new_stmt, loop_vinfo, NULL));
3087 STMT_VINFO_RELATED_STMT (prev_stmt_vinfo) = new_stmt;
3088 prev_stmt_vinfo = vinfo_for_stmt (new_stmt);
3092 if (nested_in_vect_loop)
3094 /* Find the loop-closed exit-phi of the induction, and record
3095 the final vector of induction results: */
3097 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, loop_arg)
3099 if (!flow_bb_inside_loop_p (iv_loop, gimple_bb (USE_STMT (use_p))))
3101 exit_phi = USE_STMT (use_p);
3107 stmt_vec_info stmt_vinfo = vinfo_for_stmt (exit_phi);
3108 /* FORNOW. Currently not supporting the case that an inner-loop induction
3109 is not used in the outer-loop (i.e. only outside the outer-loop). */
3110 gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo)
3111 && !STMT_VINFO_LIVE_P (stmt_vinfo));
3113 STMT_VINFO_VEC_STMT (stmt_vinfo) = new_stmt;
3114 if (vect_print_dump_info (REPORT_DETAILS))
3116 fprintf (vect_dump, "vector of inductions after inner-loop:");
3117 print_gimple_stmt (vect_dump, new_stmt, 0, TDF_SLIM);
3123 if (vect_print_dump_info (REPORT_DETAILS))
3125 fprintf (vect_dump, "transform induction: created def-use cycle: ");
3126 print_gimple_stmt (vect_dump, induction_phi, 0, TDF_SLIM);
3127 fprintf (vect_dump, "\n");
3128 print_gimple_stmt (vect_dump, SSA_NAME_DEF_STMT (vec_def), 0, TDF_SLIM);
3131 STMT_VINFO_VEC_STMT (phi_info) = induction_phi;
3132 if (!useless_type_conversion_p (resvectype, vectype))
3134 new_stmt = gimple_build_assign_with_ops
3136 vect_get_new_vect_var (resvectype, vect_simple_var, "vec_iv_"),
3137 build1 (VIEW_CONVERT_EXPR, resvectype, induc_def), NULL_TREE);
3138 induc_def = make_ssa_name (gimple_assign_lhs (new_stmt), new_stmt);
3139 gimple_assign_set_lhs (new_stmt, induc_def);
3140 si = gsi_start_bb (bb);
3141 gsi_insert_before (&si, new_stmt, GSI_SAME_STMT);
3142 set_vinfo_for_stmt (new_stmt,
3143 new_stmt_vec_info (new_stmt, loop_vinfo, NULL));
3144 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_stmt))
3145 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (induction_phi));
3152 /* Function get_initial_def_for_reduction
3155 STMT - a stmt that performs a reduction operation in the loop.
3156 INIT_VAL - the initial value of the reduction variable
3159 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
3160 of the reduction (used for adjusting the epilog - see below).
3161 Return a vector variable, initialized according to the operation that STMT
3162 performs. This vector will be used as the initial value of the
3163 vector of partial results.
3165 Option1 (adjust in epilog): Initialize the vector as follows:
3166 add/bit or/xor: [0,0,...,0,0]
3167 mult/bit and: [1,1,...,1,1]
3168 min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
3169 and when necessary (e.g. add/mult case) let the caller know
3170 that it needs to adjust the result by init_val.
3172 Option2: Initialize the vector as follows:
3173 add/bit or/xor: [init_val,0,0,...,0]
3174 mult/bit and: [init_val,1,1,...,1]
3175 min/max/cond_expr: [init_val,init_val,...,init_val]
3176 and no adjustments are needed.
3178 For example, for the following code:
3184 STMT is 's = s + a[i]', and the reduction variable is 's'.
3185 For a vector of 4 units, we want to return either [0,0,0,init_val],
3186 or [0,0,0,0] and let the caller know that it needs to adjust
3187 the result at the end by 'init_val'.
3189 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
3190 initialization vector is simpler (same element in all entries), if
3191 ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
3193 A cost model should help decide between these two schemes. */
3196 get_initial_def_for_reduction (gimple stmt, tree init_val,
3197 tree *adjustment_def)
3199 stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
3200 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
3201 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
3202 tree scalar_type = TREE_TYPE (init_val);
3203 tree vectype = get_vectype_for_scalar_type (scalar_type);
3205 enum tree_code code = gimple_assign_rhs_code (stmt);
3210 bool nested_in_vect_loop = false;
3212 REAL_VALUE_TYPE real_init_val = dconst0;
3213 int int_init_val = 0;
3214 gimple def_stmt = NULL;
3216 gcc_assert (vectype);
3217 nunits = TYPE_VECTOR_SUBPARTS (vectype);
3219 gcc_assert (POINTER_TYPE_P (scalar_type) || INTEGRAL_TYPE_P (scalar_type)
3220 || SCALAR_FLOAT_TYPE_P (scalar_type));
3222 if (nested_in_vect_loop_p (loop, stmt))
3223 nested_in_vect_loop = true;
3225 gcc_assert (loop == (gimple_bb (stmt))->loop_father);
3227 /* In case of double reduction we only create a vector variable to be put
3228 in the reduction phi node. The actual statement creation is done in
3229 vect_create_epilog_for_reduction. */
3230 if (adjustment_def && nested_in_vect_loop
3231 && TREE_CODE (init_val) == SSA_NAME
3232 && (def_stmt = SSA_NAME_DEF_STMT (init_val))
3233 && gimple_code (def_stmt) == GIMPLE_PHI
3234 && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
3235 && vinfo_for_stmt (def_stmt)
3236 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
3237 == vect_double_reduction_def)
3239 *adjustment_def = NULL;
3240 return vect_create_destination_var (init_val, vectype);
3243 if (TREE_CONSTANT (init_val))
3245 if (SCALAR_FLOAT_TYPE_P (scalar_type))
3246 init_value = build_real (scalar_type, TREE_REAL_CST (init_val));
3248 init_value = build_int_cst (scalar_type, TREE_INT_CST_LOW (init_val));
3251 init_value = init_val;
3255 case WIDEN_SUM_EXPR:
3263 /* ADJUSMENT_DEF is NULL when called from
3264 vect_create_epilog_for_reduction to vectorize double reduction. */
3267 if (nested_in_vect_loop)
3268 *adjustment_def = vect_get_vec_def_for_operand (init_val, stmt,
3271 *adjustment_def = init_val;
3274 if (code == MULT_EXPR)
3276 real_init_val = dconst1;
3280 if (code == BIT_AND_EXPR)
3283 if (SCALAR_FLOAT_TYPE_P (scalar_type))
3284 def_for_init = build_real (scalar_type, real_init_val);
3286 def_for_init = build_int_cst (scalar_type, int_init_val);
3288 /* Create a vector of '0' or '1' except the first element. */
3289 for (i = nunits - 2; i >= 0; --i)
3290 t = tree_cons (NULL_TREE, def_for_init, t);
3292 /* Option1: the first element is '0' or '1' as well. */
3295 t = tree_cons (NULL_TREE, def_for_init, t);
3296 init_def = build_vector (vectype, t);
3300 /* Option2: the first element is INIT_VAL. */
3301 t = tree_cons (NULL_TREE, init_value, t);
3302 if (TREE_CONSTANT (init_val))
3303 init_def = build_vector (vectype, t);
3305 init_def = build_constructor_from_list (vectype, t);
3314 *adjustment_def = NULL_TREE;
3315 init_def = vect_get_vec_def_for_operand (init_val, stmt, NULL);
3319 init_def = build_vector_from_val (vectype, init_value);
3330 /* Function vect_create_epilog_for_reduction
3332 Create code at the loop-epilog to finalize the result of a reduction
3335 VECT_DEFS is list of vector of partial results, i.e., the lhs's of vector
3336 reduction statements.
3337 STMT is the scalar reduction stmt that is being vectorized.
3338 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
3339 number of elements that we can fit in a vectype (nunits). In this case
3340 we have to generate more than one vector stmt - i.e - we need to "unroll"
3341 the vector stmt by a factor VF/nunits. For more details see documentation
3342 in vectorizable_operation.
3343 REDUC_CODE is the tree-code for the epilog reduction.
3344 REDUCTION_PHIS is a list of the phi-nodes that carry the reduction
3346 REDUC_INDEX is the index of the operand in the right hand side of the
3347 statement that is defined by REDUCTION_PHI.
3348 DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
3349 SLP_NODE is an SLP node containing a group of reduction statements. The
3350 first one in this group is STMT.
3353 1. Creates the reduction def-use cycles: sets the arguments for
3355 The loop-entry argument is the vectorized initial-value of the reduction.
3356 The loop-latch argument is taken from VECT_DEFS - the vector of partial
3358 2. "Reduces" each vector of partial results VECT_DEFS into a single result,
3359 by applying the operation specified by REDUC_CODE if available, or by
3360 other means (whole-vector shifts or a scalar loop).
3361 The function also creates a new phi node at the loop exit to preserve
3362 loop-closed form, as illustrated below.
3364 The flow at the entry to this function:
3367 vec_def = phi <null, null> # REDUCTION_PHI
3368 VECT_DEF = vector_stmt # vectorized form of STMT
3369 s_loop = scalar_stmt # (scalar) STMT
3371 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3375 The above is transformed by this function into:
3378 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3379 VECT_DEF = vector_stmt # vectorized form of STMT
3380 s_loop = scalar_stmt # (scalar) STMT
3382 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3383 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3384 v_out2 = reduce <v_out1>
3385 s_out3 = extract_field <v_out2, 0>
3386 s_out4 = adjust_result <s_out3>
3392 vect_create_epilog_for_reduction (VEC (tree, heap) *vect_defs, gimple stmt,
3393 int ncopies, enum tree_code reduc_code,
3394 VEC (gimple, heap) *reduction_phis,
3395 int reduc_index, bool double_reduc,
3398 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3399 stmt_vec_info prev_phi_info;
3401 enum machine_mode mode;
3402 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3403 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo), *outer_loop = NULL;
3404 basic_block exit_bb;
3407 gimple new_phi = NULL, phi;
3408 gimple_stmt_iterator exit_gsi;
3410 tree new_temp = NULL_TREE, new_dest, new_name, new_scalar_dest;
3411 gimple epilog_stmt = NULL;
3412 enum tree_code code = gimple_assign_rhs_code (stmt);
3414 tree bitsize, bitpos;
3415 tree adjustment_def = NULL;
3416 tree vec_initial_def = NULL;
3417 tree reduction_op, expr, def;
3418 tree orig_name, scalar_result;
3419 imm_use_iterator imm_iter, phi_imm_iter;
3420 use_operand_p use_p, phi_use_p;
3421 bool extract_scalar_result = false;
3422 gimple use_stmt, orig_stmt, reduction_phi = NULL;
3423 bool nested_in_vect_loop = false;
3424 VEC (gimple, heap) *new_phis = NULL;
3425 enum vect_def_type dt = vect_unknown_def_type;
3427 VEC (tree, heap) *scalar_results = NULL;
3428 unsigned int group_size = 1, k, ratio;
3429 VEC (tree, heap) *vec_initial_defs = NULL;
3430 VEC (gimple, heap) *phis;
3431 bool slp_reduc = false;
3432 tree new_phi_result;
3435 group_size = VEC_length (gimple, SLP_TREE_SCALAR_STMTS (slp_node));
3437 if (nested_in_vect_loop_p (loop, stmt))
3441 nested_in_vect_loop = true;
3442 gcc_assert (!slp_node);
3445 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
3447 case GIMPLE_SINGLE_RHS:
3448 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt))
3450 reduction_op = TREE_OPERAND (gimple_assign_rhs1 (stmt), reduc_index);
3452 case GIMPLE_UNARY_RHS:
3453 reduction_op = gimple_assign_rhs1 (stmt);
3455 case GIMPLE_BINARY_RHS:
3456 reduction_op = reduc_index ?
3457 gimple_assign_rhs2 (stmt) : gimple_assign_rhs1 (stmt);
3459 case GIMPLE_TERNARY_RHS:
3460 reduction_op = gimple_op (stmt, reduc_index + 1);
3466 vectype = get_vectype_for_scalar_type (TREE_TYPE (reduction_op));
3467 gcc_assert (vectype);
3468 mode = TYPE_MODE (vectype);
3470 /* 1. Create the reduction def-use cycle:
3471 Set the arguments of REDUCTION_PHIS, i.e., transform
3474 vec_def = phi <null, null> # REDUCTION_PHI
3475 VECT_DEF = vector_stmt # vectorized form of STMT
3481 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3482 VECT_DEF = vector_stmt # vectorized form of STMT
3485 (in case of SLP, do it for all the phis). */
3487 /* Get the loop-entry arguments. */
3489 vect_get_slp_defs (reduction_op, NULL_TREE, slp_node, &vec_initial_defs,
3493 vec_initial_defs = VEC_alloc (tree, heap, 1);
3494 /* For the case of reduction, vect_get_vec_def_for_operand returns
3495 the scalar def before the loop, that defines the initial value
3496 of the reduction variable. */
3497 vec_initial_def = vect_get_vec_def_for_operand (reduction_op, stmt,
3499 VEC_quick_push (tree, vec_initial_defs, vec_initial_def);
3502 /* Set phi nodes arguments. */
3503 FOR_EACH_VEC_ELT (gimple, reduction_phis, i, phi)
3505 tree vec_init_def = VEC_index (tree, vec_initial_defs, i);
3506 tree def = VEC_index (tree, vect_defs, i);
3507 for (j = 0; j < ncopies; j++)
3509 /* Set the loop-entry arg of the reduction-phi. */
3510 add_phi_arg (phi, vec_init_def, loop_preheader_edge (loop),
3513 /* Set the loop-latch arg for the reduction-phi. */
3515 def = vect_get_vec_def_for_stmt_copy (vect_unknown_def_type, def);
3517 add_phi_arg (phi, def, loop_latch_edge (loop), UNKNOWN_LOCATION);
3519 if (vect_print_dump_info (REPORT_DETAILS))
3521 fprintf (vect_dump, "transform reduction: created def-use"
3523 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
3524 fprintf (vect_dump, "\n");
3525 print_gimple_stmt (vect_dump, SSA_NAME_DEF_STMT (def), 0,
3529 phi = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi));
3533 VEC_free (tree, heap, vec_initial_defs);
3535 /* 2. Create epilog code.
3536 The reduction epilog code operates across the elements of the vector
3537 of partial results computed by the vectorized loop.
3538 The reduction epilog code consists of:
3540 step 1: compute the scalar result in a vector (v_out2)
3541 step 2: extract the scalar result (s_out3) from the vector (v_out2)
3542 step 3: adjust the scalar result (s_out3) if needed.
3544 Step 1 can be accomplished using one the following three schemes:
3545 (scheme 1) using reduc_code, if available.
3546 (scheme 2) using whole-vector shifts, if available.
3547 (scheme 3) using a scalar loop. In this case steps 1+2 above are
3550 The overall epilog code looks like this:
3552 s_out0 = phi <s_loop> # original EXIT_PHI
3553 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3554 v_out2 = reduce <v_out1> # step 1
3555 s_out3 = extract_field <v_out2, 0> # step 2
3556 s_out4 = adjust_result <s_out3> # step 3
3558 (step 3 is optional, and steps 1 and 2 may be combined).
3559 Lastly, the uses of s_out0 are replaced by s_out4. */
3562 /* 2.1 Create new loop-exit-phis to preserve loop-closed form:
3563 v_out1 = phi <VECT_DEF>
3564 Store them in NEW_PHIS. */
3566 exit_bb = single_exit (loop)->dest;
3567 prev_phi_info = NULL;
3568 new_phis = VEC_alloc (gimple, heap, VEC_length (tree, vect_defs));
3569 FOR_EACH_VEC_ELT (tree, vect_defs, i, def)
3571 for (j = 0; j < ncopies; j++)
3573 phi = create_phi_node (SSA_NAME_VAR (def), exit_bb);
3574 set_vinfo_for_stmt (phi, new_stmt_vec_info (phi, loop_vinfo, NULL));
3576 VEC_quick_push (gimple, new_phis, phi);
3579 def = vect_get_vec_def_for_stmt_copy (dt, def);
3580 STMT_VINFO_RELATED_STMT (prev_phi_info) = phi;
3583 SET_PHI_ARG_DEF (phi, single_exit (loop)->dest_idx, def);
3584 prev_phi_info = vinfo_for_stmt (phi);
3588 /* The epilogue is created for the outer-loop, i.e., for the loop being
3593 exit_bb = single_exit (loop)->dest;
3596 exit_gsi = gsi_after_labels (exit_bb);
3598 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
3599 (i.e. when reduc_code is not available) and in the final adjustment
3600 code (if needed). Also get the original scalar reduction variable as
3601 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
3602 represents a reduction pattern), the tree-code and scalar-def are
3603 taken from the original stmt that the pattern-stmt (STMT) replaces.
3604 Otherwise (it is a regular reduction) - the tree-code and scalar-def
3605 are taken from STMT. */
3607 orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
3610 /* Regular reduction */
3615 /* Reduction pattern */
3616 stmt_vec_info stmt_vinfo = vinfo_for_stmt (orig_stmt);
3617 gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo));
3618 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo) == stmt);
3621 code = gimple_assign_rhs_code (orig_stmt);
3622 /* For MINUS_EXPR the initial vector is [init_val,0,...,0], therefore,
3623 partial results are added and not subtracted. */
3624 if (code == MINUS_EXPR)
3627 scalar_dest = gimple_assign_lhs (orig_stmt);
3628 scalar_type = TREE_TYPE (scalar_dest);
3629 scalar_results = VEC_alloc (tree, heap, group_size);
3630 new_scalar_dest = vect_create_destination_var (scalar_dest, NULL);
3631 bitsize = TYPE_SIZE (scalar_type);
3633 /* In case this is a reduction in an inner-loop while vectorizing an outer
3634 loop - we don't need to extract a single scalar result at the end of the
3635 inner-loop (unless it is double reduction, i.e., the use of reduction is
3636 outside the outer-loop). The final vector of partial results will be used
3637 in the vectorized outer-loop, or reduced to a scalar result at the end of
3639 if (nested_in_vect_loop && !double_reduc)
3640 goto vect_finalize_reduction;
3642 /* SLP reduction without reduction chain, e.g.,
3646 b2 = operation (b1) */
3647 slp_reduc = (slp_node && !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)));
3649 /* In case of reduction chain, e.g.,
3652 a3 = operation (a2),
3654 we may end up with more than one vector result. Here we reduce them to
3656 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
3658 tree first_vect = PHI_RESULT (VEC_index (gimple, new_phis, 0));
3661 vec_dest = vect_create_destination_var (scalar_dest, vectype);
3662 for (k = 1; k < VEC_length (gimple, new_phis); k++)
3664 gimple next_phi = VEC_index (gimple, new_phis, k);
3665 tree second_vect = PHI_RESULT (next_phi);
3666 gimple new_vec_stmt;
3668 tmp = build2 (code, vectype, first_vect, second_vect);
3669 new_vec_stmt = gimple_build_assign (vec_dest, tmp);
3670 first_vect = make_ssa_name (vec_dest, new_vec_stmt);
3671 gimple_assign_set_lhs (new_vec_stmt, first_vect);
3672 gsi_insert_before (&exit_gsi, new_vec_stmt, GSI_SAME_STMT);
3675 new_phi_result = first_vect;
3678 new_phi_result = PHI_RESULT (VEC_index (gimple, new_phis, 0));
3680 /* 2.3 Create the reduction code, using one of the three schemes described
3681 above. In SLP we simply need to extract all the elements from the
3682 vector (without reducing them), so we use scalar shifts. */
3683 if (reduc_code != ERROR_MARK && !slp_reduc)
3687 /*** Case 1: Create:
3688 v_out2 = reduc_expr <v_out1> */
3690 if (vect_print_dump_info (REPORT_DETAILS))
3691 fprintf (vect_dump, "Reduce using direct vector reduction.");
3693 vec_dest = vect_create_destination_var (scalar_dest, vectype);
3694 tmp = build1 (reduc_code, vectype, new_phi_result);
3695 epilog_stmt = gimple_build_assign (vec_dest, tmp);
3696 new_temp = make_ssa_name (vec_dest, epilog_stmt);
3697 gimple_assign_set_lhs (epilog_stmt, new_temp);
3698 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3700 extract_scalar_result = true;
3704 enum tree_code shift_code = ERROR_MARK;
3705 bool have_whole_vector_shift = true;
3707 int element_bitsize = tree_low_cst (bitsize, 1);
3708 int vec_size_in_bits = tree_low_cst (TYPE_SIZE (vectype), 1);
3711 if (optab_handler (vec_shr_optab, mode) != CODE_FOR_nothing)
3712 shift_code = VEC_RSHIFT_EXPR;
3714 have_whole_vector_shift = false;
3716 /* Regardless of whether we have a whole vector shift, if we're
3717 emulating the operation via tree-vect-generic, we don't want
3718 to use it. Only the first round of the reduction is likely
3719 to still be profitable via emulation. */
3720 /* ??? It might be better to emit a reduction tree code here, so that
3721 tree-vect-generic can expand the first round via bit tricks. */
3722 if (!VECTOR_MODE_P (mode))
3723 have_whole_vector_shift = false;
3726 optab optab = optab_for_tree_code (code, vectype, optab_default);
3727 if (optab_handler (optab, mode) == CODE_FOR_nothing)
3728 have_whole_vector_shift = false;
3731 if (have_whole_vector_shift && !slp_reduc)
3733 /*** Case 2: Create:
3734 for (offset = VS/2; offset >= element_size; offset/=2)
3736 Create: va' = vec_shift <va, offset>
3737 Create: va = vop <va, va'>
3740 if (vect_print_dump_info (REPORT_DETAILS))
3741 fprintf (vect_dump, "Reduce using vector shifts");
3743 vec_dest = vect_create_destination_var (scalar_dest, vectype);
3744 new_temp = new_phi_result;
3745 for (bit_offset = vec_size_in_bits/2;
3746 bit_offset >= element_bitsize;
3749 tree bitpos = size_int (bit_offset);
3751 epilog_stmt = gimple_build_assign_with_ops (shift_code,
3752 vec_dest, new_temp, bitpos);
3753 new_name = make_ssa_name (vec_dest, epilog_stmt);
3754 gimple_assign_set_lhs (epilog_stmt, new_name);
3755 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3757 epilog_stmt = gimple_build_assign_with_ops (code, vec_dest,
3758 new_name, new_temp);
3759 new_temp = make_ssa_name (vec_dest, epilog_stmt);
3760 gimple_assign_set_lhs (epilog_stmt, new_temp);
3761 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3764 extract_scalar_result = true;
3770 /*** Case 3: Create:
3771 s = extract_field <v_out2, 0>
3772 for (offset = element_size;
3773 offset < vector_size;
3774 offset += element_size;)
3776 Create: s' = extract_field <v_out2, offset>
3777 Create: s = op <s, s'> // For non SLP cases
3780 if (vect_print_dump_info (REPORT_DETAILS))
3781 fprintf (vect_dump, "Reduce using scalar code. ");
3783 vec_size_in_bits = tree_low_cst (TYPE_SIZE (vectype), 1);
3784 FOR_EACH_VEC_ELT (gimple, new_phis, i, new_phi)
3786 vec_temp = PHI_RESULT (new_phi);
3787 rhs = build3 (BIT_FIELD_REF, scalar_type, vec_temp, bitsize,
3789 epilog_stmt = gimple_build_assign (new_scalar_dest, rhs);
3790 new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
3791 gimple_assign_set_lhs (epilog_stmt, new_temp);
3792 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3794 /* In SLP we don't need to apply reduction operation, so we just
3795 collect s' values in SCALAR_RESULTS. */
3797 VEC_safe_push (tree, heap, scalar_results, new_temp);
3799 for (bit_offset = element_bitsize;
3800 bit_offset < vec_size_in_bits;
3801 bit_offset += element_bitsize)
3803 tree bitpos = bitsize_int (bit_offset);
3804 tree rhs = build3 (BIT_FIELD_REF, scalar_type, vec_temp,
3807 epilog_stmt = gimple_build_assign (new_scalar_dest, rhs);
3808 new_name = make_ssa_name (new_scalar_dest, epilog_stmt);
3809 gimple_assign_set_lhs (epilog_stmt, new_name);
3810 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3814 /* In SLP we don't need to apply reduction operation, so
3815 we just collect s' values in SCALAR_RESULTS. */
3816 new_temp = new_name;
3817 VEC_safe_push (tree, heap, scalar_results, new_name);
3821 epilog_stmt = gimple_build_assign_with_ops (code,
3822 new_scalar_dest, new_name, new_temp);
3823 new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
3824 gimple_assign_set_lhs (epilog_stmt, new_temp);
3825 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3830 /* The only case where we need to reduce scalar results in SLP, is
3831 unrolling. If the size of SCALAR_RESULTS is greater than
3832 GROUP_SIZE, we reduce them combining elements modulo
3836 tree res, first_res, new_res;
3839 /* Reduce multiple scalar results in case of SLP unrolling. */
3840 for (j = group_size; VEC_iterate (tree, scalar_results, j, res);
3843 first_res = VEC_index (tree, scalar_results, j % group_size);
3844 new_stmt = gimple_build_assign_with_ops (code,
3845 new_scalar_dest, first_res, res);
3846 new_res = make_ssa_name (new_scalar_dest, new_stmt);
3847 gimple_assign_set_lhs (new_stmt, new_res);
3848 gsi_insert_before (&exit_gsi, new_stmt, GSI_SAME_STMT);
3849 VEC_replace (tree, scalar_results, j % group_size, new_res);
3853 /* Not SLP - we have one scalar to keep in SCALAR_RESULTS. */
3854 VEC_safe_push (tree, heap, scalar_results, new_temp);
3856 extract_scalar_result = false;
3860 /* 2.4 Extract the final scalar result. Create:
3861 s_out3 = extract_field <v_out2, bitpos> */
3863 if (extract_scalar_result)
3867 if (vect_print_dump_info (REPORT_DETAILS))
3868 fprintf (vect_dump, "extract scalar result");
3870 if (BYTES_BIG_ENDIAN)
3871 bitpos = size_binop (MULT_EXPR,
3872 bitsize_int (TYPE_VECTOR_SUBPARTS (vectype) - 1),
3873 TYPE_SIZE (scalar_type));
3875 bitpos = bitsize_zero_node;
3877 rhs = build3 (BIT_FIELD_REF, scalar_type, new_temp, bitsize, bitpos);
3878 epilog_stmt = gimple_build_assign (new_scalar_dest, rhs);
3879 new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
3880 gimple_assign_set_lhs (epilog_stmt, new_temp);
3881 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3882 VEC_safe_push (tree, heap, scalar_results, new_temp);
3885 vect_finalize_reduction:
3890 /* 2.5 Adjust the final result by the initial value of the reduction
3891 variable. (When such adjustment is not needed, then
3892 'adjustment_def' is zero). For example, if code is PLUS we create:
3893 new_temp = loop_exit_def + adjustment_def */
3897 gcc_assert (!slp_reduc);
3898 if (nested_in_vect_loop)
3900 new_phi = VEC_index (gimple, new_phis, 0);
3901 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def)) == VECTOR_TYPE);
3902 expr = build2 (code, vectype, PHI_RESULT (new_phi), adjustment_def);
3903 new_dest = vect_create_destination_var (scalar_dest, vectype);
3907 new_temp = VEC_index (tree, scalar_results, 0);
3908 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def)) != VECTOR_TYPE);
3909 expr = build2 (code, scalar_type, new_temp, adjustment_def);
3910 new_dest = vect_create_destination_var (scalar_dest, scalar_type);
3913 epilog_stmt = gimple_build_assign (new_dest, expr);
3914 new_temp = make_ssa_name (new_dest, epilog_stmt);
3915 gimple_assign_set_lhs (epilog_stmt, new_temp);
3916 SSA_NAME_DEF_STMT (new_temp) = epilog_stmt;
3917 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3918 if (nested_in_vect_loop)
3920 set_vinfo_for_stmt (epilog_stmt,
3921 new_stmt_vec_info (epilog_stmt, loop_vinfo,
3923 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (epilog_stmt)) =
3924 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_phi));
3927 VEC_quick_push (tree, scalar_results, new_temp);
3929 VEC_replace (tree, scalar_results, 0, new_temp);
3932 VEC_replace (tree, scalar_results, 0, new_temp);
3934 VEC_replace (gimple, new_phis, 0, epilog_stmt);
3937 /* 2.6 Handle the loop-exit phis. Replace the uses of scalar loop-exit
3938 phis with new adjusted scalar results, i.e., replace use <s_out0>
3943 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3944 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3945 v_out2 = reduce <v_out1>
3946 s_out3 = extract_field <v_out2, 0>
3947 s_out4 = adjust_result <s_out3>
3954 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3955 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3956 v_out2 = reduce <v_out1>
3957 s_out3 = extract_field <v_out2, 0>
3958 s_out4 = adjust_result <s_out3>
3963 /* In SLP reduction chain we reduce vector results into one vector if
3964 necessary, hence we set here GROUP_SIZE to 1. SCALAR_DEST is the LHS of
3965 the last stmt in the reduction chain, since we are looking for the loop
3967 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
3969 scalar_dest = gimple_assign_lhs (VEC_index (gimple,
3970 SLP_TREE_SCALAR_STMTS (slp_node),
3975 /* In SLP we may have several statements in NEW_PHIS and REDUCTION_PHIS (in
3976 case that GROUP_SIZE is greater than vectorization factor). Therefore, we
3977 need to match SCALAR_RESULTS with corresponding statements. The first
3978 (GROUP_SIZE / number of new vector stmts) scalar results correspond to
3979 the first vector stmt, etc.
3980 (RATIO is equal to (GROUP_SIZE / number of new vector stmts)). */
3981 if (group_size > VEC_length (gimple, new_phis))
3983 ratio = group_size / VEC_length (gimple, new_phis);
3984 gcc_assert (!(group_size % VEC_length (gimple, new_phis)));
3989 for (k = 0; k < group_size; k++)
3993 epilog_stmt = VEC_index (gimple, new_phis, k / ratio);
3994 reduction_phi = VEC_index (gimple, reduction_phis, k / ratio);
3999 gimple current_stmt = VEC_index (gimple,
4000 SLP_TREE_SCALAR_STMTS (slp_node), k);
4002 orig_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (current_stmt));
4003 /* SLP statements can't participate in patterns. */
4004 gcc_assert (!orig_stmt);
4005 scalar_dest = gimple_assign_lhs (current_stmt);
4008 phis = VEC_alloc (gimple, heap, 3);
4009 /* Find the loop-closed-use at the loop exit of the original scalar
4010 result. (The reduction result is expected to have two immediate uses -
4011 one at the latch block, and one at the loop exit). */
4012 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, scalar_dest)
4013 if (!flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
4014 VEC_safe_push (gimple, heap, phis, USE_STMT (use_p));
4016 /* We expect to have found an exit_phi because of loop-closed-ssa
4018 gcc_assert (!VEC_empty (gimple, phis));
4020 FOR_EACH_VEC_ELT (gimple, phis, i, exit_phi)
4024 stmt_vec_info exit_phi_vinfo = vinfo_for_stmt (exit_phi);
4027 /* FORNOW. Currently not supporting the case that an inner-loop
4028 reduction is not used in the outer-loop (but only outside the
4029 outer-loop), unless it is double reduction. */
4030 gcc_assert ((STMT_VINFO_RELEVANT_P (exit_phi_vinfo)
4031 && !STMT_VINFO_LIVE_P (exit_phi_vinfo))
4034 STMT_VINFO_VEC_STMT (exit_phi_vinfo) = epilog_stmt;
4036 || STMT_VINFO_DEF_TYPE (exit_phi_vinfo)
4037 != vect_double_reduction_def)
4040 /* Handle double reduction:
4042 stmt1: s1 = phi <s0, s2> - double reduction phi (outer loop)
4043 stmt2: s3 = phi <s1, s4> - (regular) reduc phi (inner loop)
4044 stmt3: s4 = use (s3) - (regular) reduc stmt (inner loop)
4045 stmt4: s2 = phi <s4> - double reduction stmt (outer loop)
4047 At that point the regular reduction (stmt2 and stmt3) is
4048 already vectorized, as well as the exit phi node, stmt4.
4049 Here we vectorize the phi node of double reduction, stmt1, and
4050 update all relevant statements. */
4052 /* Go through all the uses of s2 to find double reduction phi
4053 node, i.e., stmt1 above. */
4054 orig_name = PHI_RESULT (exit_phi);
4055 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, orig_name)
4057 stmt_vec_info use_stmt_vinfo = vinfo_for_stmt (use_stmt);
4058 stmt_vec_info new_phi_vinfo;
4059 tree vect_phi_init, preheader_arg, vect_phi_res, init_def;
4060 basic_block bb = gimple_bb (use_stmt);
4063 /* Check that USE_STMT is really double reduction phi
4065 if (gimple_code (use_stmt) != GIMPLE_PHI
4066 || gimple_phi_num_args (use_stmt) != 2
4068 || STMT_VINFO_DEF_TYPE (use_stmt_vinfo)
4069 != vect_double_reduction_def
4070 || bb->loop_father != outer_loop)
4073 /* Create vector phi node for double reduction:
4074 vs1 = phi <vs0, vs2>
4075 vs1 was created previously in this function by a call to
4076 vect_get_vec_def_for_operand and is stored in
4078 vs2 is defined by EPILOG_STMT, the vectorized EXIT_PHI;
4079 vs0 is created here. */
4081 /* Create vector phi node. */
4082 vect_phi = create_phi_node (vec_initial_def, bb);
4083 new_phi_vinfo = new_stmt_vec_info (vect_phi,
4084 loop_vec_info_for_loop (outer_loop), NULL);
4085 set_vinfo_for_stmt (vect_phi, new_phi_vinfo);
4087 /* Create vs0 - initial def of the double reduction phi. */
4088 preheader_arg = PHI_ARG_DEF_FROM_EDGE (use_stmt,
4089 loop_preheader_edge (outer_loop));
4090 init_def = get_initial_def_for_reduction (stmt,
4091 preheader_arg, NULL);
4092 vect_phi_init = vect_init_vector (use_stmt, init_def,
4095 /* Update phi node arguments with vs0 and vs2. */
4096 add_phi_arg (vect_phi, vect_phi_init,
4097 loop_preheader_edge (outer_loop),
4099 add_phi_arg (vect_phi, PHI_RESULT (epilog_stmt),
4100 loop_latch_edge (outer_loop), UNKNOWN_LOCATION);
4101 if (vect_print_dump_info (REPORT_DETAILS))
4103 fprintf (vect_dump, "created double reduction phi "
4105 print_gimple_stmt (vect_dump, vect_phi, 0, TDF_SLIM);
4108 vect_phi_res = PHI_RESULT (vect_phi);
4110 /* Replace the use, i.e., set the correct vs1 in the regular
4111 reduction phi node. FORNOW, NCOPIES is always 1, so the
4112 loop is redundant. */
4113 use = reduction_phi;
4114 for (j = 0; j < ncopies; j++)
4116 edge pr_edge = loop_preheader_edge (loop);
4117 SET_PHI_ARG_DEF (use, pr_edge->dest_idx, vect_phi_res);
4118 use = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use));
4124 VEC_free (gimple, heap, phis);
4125 if (nested_in_vect_loop)
4133 phis = VEC_alloc (gimple, heap, 3);
4134 /* Find the loop-closed-use at the loop exit of the original scalar
4135 result. (The reduction result is expected to have two immediate uses,
4136 one at the latch block, and one at the loop exit). For double
4137 reductions we are looking for exit phis of the outer loop. */
4138 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, scalar_dest)
4140 if (!flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
4141 VEC_safe_push (gimple, heap, phis, USE_STMT (use_p));
4144 if (double_reduc && gimple_code (USE_STMT (use_p)) == GIMPLE_PHI)
4146 tree phi_res = PHI_RESULT (USE_STMT (use_p));
4148 FOR_EACH_IMM_USE_FAST (phi_use_p, phi_imm_iter, phi_res)
4150 if (!flow_bb_inside_loop_p (loop,
4151 gimple_bb (USE_STMT (phi_use_p))))
4152 VEC_safe_push (gimple, heap, phis,
4153 USE_STMT (phi_use_p));
4159 FOR_EACH_VEC_ELT (gimple, phis, i, exit_phi)
4161 /* Replace the uses: */
4162 orig_name = PHI_RESULT (exit_phi);
4163 scalar_result = VEC_index (tree, scalar_results, k);
4164 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, orig_name)
4165 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
4166 SET_USE (use_p, scalar_result);
4169 VEC_free (gimple, heap, phis);
4172 VEC_free (tree, heap, scalar_results);
4173 VEC_free (gimple, heap, new_phis);
4177 /* Function vectorizable_reduction.
4179 Check if STMT performs a reduction operation that can be vectorized.
4180 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4181 stmt to replace it, put it in VEC_STMT, and insert it at GSI.
4182 Return FALSE if not a vectorizable STMT, TRUE otherwise.
4184 This function also handles reduction idioms (patterns) that have been
4185 recognized in advance during vect_pattern_recog. In this case, STMT may be
4187 X = pattern_expr (arg0, arg1, ..., X)
4188 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
4189 sequence that had been detected and replaced by the pattern-stmt (STMT).
4191 In some cases of reduction patterns, the type of the reduction variable X is
4192 different than the type of the other arguments of STMT.
4193 In such cases, the vectype that is used when transforming STMT into a vector
4194 stmt is different than the vectype that is used to determine the
4195 vectorization factor, because it consists of a different number of elements
4196 than the actual number of elements that are being operated upon in parallel.
4198 For example, consider an accumulation of shorts into an int accumulator.
4199 On some targets it's possible to vectorize this pattern operating on 8
4200 shorts at a time (hence, the vectype for purposes of determining the
4201 vectorization factor should be V8HI); on the other hand, the vectype that
4202 is used to create the vector form is actually V4SI (the type of the result).
4204 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
4205 indicates what is the actual level of parallelism (V8HI in the example), so
4206 that the right vectorization factor would be derived. This vectype
4207 corresponds to the type of arguments to the reduction stmt, and should *NOT*
4208 be used to create the vectorized stmt. The right vectype for the vectorized
4209 stmt is obtained from the type of the result X:
4210 get_vectype_for_scalar_type (TREE_TYPE (X))
4212 This means that, contrary to "regular" reductions (or "regular" stmts in
4213 general), the following equation:
4214 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
4215 does *NOT* necessarily hold for reduction patterns. */
4218 vectorizable_reduction (gimple stmt, gimple_stmt_iterator *gsi,
4219 gimple *vec_stmt, slp_tree slp_node)
4223 tree loop_vec_def0 = NULL_TREE, loop_vec_def1 = NULL_TREE;
4224 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4225 tree vectype_out = STMT_VINFO_VECTYPE (stmt_info);
4226 tree vectype_in = NULL_TREE;
4227 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
4228 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
4229 enum tree_code code, orig_code, epilog_reduc_code;
4230 enum machine_mode vec_mode;
4232 optab optab, reduc_optab;
4233 tree new_temp = NULL_TREE;
4236 enum vect_def_type dt;
4237 gimple new_phi = NULL;
4241 stmt_vec_info orig_stmt_info;
4242 tree expr = NULL_TREE;
4246 stmt_vec_info prev_stmt_info, prev_phi_info;
4247 bool single_defuse_cycle = false;
4248 tree reduc_def = NULL_TREE;
4249 gimple new_stmt = NULL;
4252 bool nested_cycle = false, found_nested_cycle_def = false;
4253 gimple reduc_def_stmt = NULL;
4254 /* The default is that the reduction variable is the last in statement. */
4255 int reduc_index = 2;
4256 bool double_reduc = false, dummy;
4258 struct loop * def_stmt_loop, *outer_loop = NULL;
4260 gimple def_arg_stmt;
4261 VEC (tree, heap) *vec_oprnds0 = NULL, *vec_oprnds1 = NULL, *vect_defs = NULL;
4262 VEC (gimple, heap) *phis = NULL;
4264 tree def0, def1, tem;
4266 /* In case of reduction chain we switch to the first stmt in the chain, but
4267 we don't update STMT_INFO, since only the last stmt is marked as reduction
4268 and has reduction properties. */
4269 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
4270 stmt = GROUP_FIRST_ELEMENT (stmt_info);
4272 if (nested_in_vect_loop_p (loop, stmt))
4276 nested_cycle = true;
4279 /* 1. Is vectorizable reduction? */
4280 /* Not supportable if the reduction variable is used in the loop, unless
4281 it's a reduction chain. */
4282 if (STMT_VINFO_RELEVANT (stmt_info) > vect_used_in_outer
4283 && !GROUP_FIRST_ELEMENT (stmt_info))
4286 /* Reductions that are not used even in an enclosing outer-loop,
4287 are expected to be "live" (used out of the loop). */
4288 if (STMT_VINFO_RELEVANT (stmt_info) == vect_unused_in_scope
4289 && !STMT_VINFO_LIVE_P (stmt_info))
4292 /* Make sure it was already recognized as a reduction computation. */
4293 if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_reduction_def
4294 && STMT_VINFO_DEF_TYPE (stmt_info) != vect_nested_cycle)
4297 /* 2. Has this been recognized as a reduction pattern?
4299 Check if STMT represents a pattern that has been recognized
4300 in earlier analysis stages. For stmts that represent a pattern,
4301 the STMT_VINFO_RELATED_STMT field records the last stmt in
4302 the original sequence that constitutes the pattern. */
4304 orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
4307 orig_stmt_info = vinfo_for_stmt (orig_stmt);
4308 gcc_assert (STMT_VINFO_RELATED_STMT (orig_stmt_info) == stmt);
4309 gcc_assert (STMT_VINFO_IN_PATTERN_P (orig_stmt_info));
4310 gcc_assert (!STMT_VINFO_IN_PATTERN_P (stmt_info));
4313 /* 3. Check the operands of the operation. The first operands are defined
4314 inside the loop body. The last operand is the reduction variable,
4315 which is defined by the loop-header-phi. */
4317 gcc_assert (is_gimple_assign (stmt));
4320 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
4322 case GIMPLE_SINGLE_RHS:
4323 op_type = TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt));
4324 if (op_type == ternary_op)
4326 tree rhs = gimple_assign_rhs1 (stmt);
4327 ops[0] = TREE_OPERAND (rhs, 0);
4328 ops[1] = TREE_OPERAND (rhs, 1);
4329 ops[2] = TREE_OPERAND (rhs, 2);
4330 code = TREE_CODE (rhs);
4336 case GIMPLE_BINARY_RHS:
4337 code = gimple_assign_rhs_code (stmt);
4338 op_type = TREE_CODE_LENGTH (code);
4339 gcc_assert (op_type == binary_op);
4340 ops[0] = gimple_assign_rhs1 (stmt);
4341 ops[1] = gimple_assign_rhs2 (stmt);
4344 case GIMPLE_TERNARY_RHS:
4345 code = gimple_assign_rhs_code (stmt);
4346 op_type = TREE_CODE_LENGTH (code);
4347 gcc_assert (op_type == ternary_op);
4348 ops[0] = gimple_assign_rhs1 (stmt);
4349 ops[1] = gimple_assign_rhs2 (stmt);
4350 ops[2] = gimple_assign_rhs3 (stmt);
4353 case GIMPLE_UNARY_RHS:
4360 scalar_dest = gimple_assign_lhs (stmt);
4361 scalar_type = TREE_TYPE (scalar_dest);
4362 if (!POINTER_TYPE_P (scalar_type) && !INTEGRAL_TYPE_P (scalar_type)
4363 && !SCALAR_FLOAT_TYPE_P (scalar_type))
4366 /* All uses but the last are expected to be defined in the loop.
4367 The last use is the reduction variable. In case of nested cycle this
4368 assumption is not true: we use reduc_index to record the index of the
4369 reduction variable. */
4370 for (i = 0; i < op_type-1; i++)
4372 /* The condition of COND_EXPR is checked in vectorizable_condition(). */
4373 if (i == 0 && code == COND_EXPR)
4376 is_simple_use = vect_is_simple_use_1 (ops[i], loop_vinfo, NULL,
4377 &def_stmt, &def, &dt, &tem);
4380 gcc_assert (is_simple_use);
4382 if (dt != vect_internal_def
4383 && dt != vect_external_def
4384 && dt != vect_constant_def
4385 && dt != vect_induction_def
4386 && !(dt == vect_nested_cycle && nested_cycle))
4389 if (dt == vect_nested_cycle)
4391 found_nested_cycle_def = true;
4392 reduc_def_stmt = def_stmt;
4397 is_simple_use = vect_is_simple_use_1 (ops[i], loop_vinfo, NULL, &def_stmt,
4401 gcc_assert (is_simple_use);
4402 gcc_assert (dt == vect_reduction_def
4403 || dt == vect_nested_cycle
4404 || ((dt == vect_internal_def || dt == vect_external_def
4405 || dt == vect_constant_def || dt == vect_induction_def)
4406 && nested_cycle && found_nested_cycle_def));
4407 if (!found_nested_cycle_def)
4408 reduc_def_stmt = def_stmt;
4410 gcc_assert (gimple_code (reduc_def_stmt) == GIMPLE_PHI);
4412 gcc_assert (orig_stmt == vect_is_simple_reduction (loop_vinfo,
4418 gimple tmp = vect_is_simple_reduction (loop_vinfo, reduc_def_stmt,
4419 !nested_cycle, &dummy);
4420 /* We changed STMT to be the first stmt in reduction chain, hence we
4421 check that in this case the first element in the chain is STMT. */
4422 gcc_assert (stmt == tmp
4423 || GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp)) == stmt);
4426 if (STMT_VINFO_LIVE_P (vinfo_for_stmt (reduc_def_stmt)))
4429 if (slp_node || PURE_SLP_STMT (stmt_info))
4432 ncopies = (LOOP_VINFO_VECT_FACTOR (loop_vinfo)
4433 / TYPE_VECTOR_SUBPARTS (vectype_in));
4435 gcc_assert (ncopies >= 1);
4437 vec_mode = TYPE_MODE (vectype_in);
4439 if (code == COND_EXPR)
4441 if (!vectorizable_condition (stmt, gsi, NULL, ops[reduc_index], 0))
4443 if (vect_print_dump_info (REPORT_DETAILS))
4444 fprintf (vect_dump, "unsupported condition in reduction");
4451 /* 4. Supportable by target? */
4453 /* 4.1. check support for the operation in the loop */
4454 optab = optab_for_tree_code (code, vectype_in, optab_default);
4457 if (vect_print_dump_info (REPORT_DETAILS))
4458 fprintf (vect_dump, "no optab.");
4463 if (optab_handler (optab, vec_mode) == CODE_FOR_nothing)
4465 if (vect_print_dump_info (REPORT_DETAILS))
4466 fprintf (vect_dump, "op not supported by target.");
4468 if (GET_MODE_SIZE (vec_mode) != UNITS_PER_WORD
4469 || LOOP_VINFO_VECT_FACTOR (loop_vinfo)
4470 < vect_min_worthwhile_factor (code))
4473 if (vect_print_dump_info (REPORT_DETAILS))
4474 fprintf (vect_dump, "proceeding using word mode.");
4477 /* Worthwhile without SIMD support? */
4478 if (!VECTOR_MODE_P (TYPE_MODE (vectype_in))
4479 && LOOP_VINFO_VECT_FACTOR (loop_vinfo)
4480 < vect_min_worthwhile_factor (code))
4482 if (vect_print_dump_info (REPORT_DETAILS))
4483 fprintf (vect_dump, "not worthwhile without SIMD support.");
4489 /* 4.2. Check support for the epilog operation.
4491 If STMT represents a reduction pattern, then the type of the
4492 reduction variable may be different than the type of the rest
4493 of the arguments. For example, consider the case of accumulation
4494 of shorts into an int accumulator; The original code:
4495 S1: int_a = (int) short_a;
4496 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
4499 STMT: int_acc = widen_sum <short_a, int_acc>
4502 1. The tree-code that is used to create the vector operation in the
4503 epilog code (that reduces the partial results) is not the
4504 tree-code of STMT, but is rather the tree-code of the original
4505 stmt from the pattern that STMT is replacing. I.e, in the example
4506 above we want to use 'widen_sum' in the loop, but 'plus' in the
4508 2. The type (mode) we use to check available target support
4509 for the vector operation to be created in the *epilog*, is
4510 determined by the type of the reduction variable (in the example
4511 above we'd check this: optab_handler (plus_optab, vect_int_mode])).
4512 However the type (mode) we use to check available target support
4513 for the vector operation to be created *inside the loop*, is
4514 determined by the type of the other arguments to STMT (in the
4515 example we'd check this: optab_handler (widen_sum_optab,
4518 This is contrary to "regular" reductions, in which the types of all
4519 the arguments are the same as the type of the reduction variable.
4520 For "regular" reductions we can therefore use the same vector type
4521 (and also the same tree-code) when generating the epilog code and
4522 when generating the code inside the loop. */
4526 /* This is a reduction pattern: get the vectype from the type of the
4527 reduction variable, and get the tree-code from orig_stmt. */
4528 orig_code = gimple_assign_rhs_code (orig_stmt);
4529 gcc_assert (vectype_out);
4530 vec_mode = TYPE_MODE (vectype_out);
4534 /* Regular reduction: use the same vectype and tree-code as used for
4535 the vector code inside the loop can be used for the epilog code. */
4541 def_bb = gimple_bb (reduc_def_stmt);
4542 def_stmt_loop = def_bb->loop_father;
4543 def_arg = PHI_ARG_DEF_FROM_EDGE (reduc_def_stmt,
4544 loop_preheader_edge (def_stmt_loop));
4545 if (TREE_CODE (def_arg) == SSA_NAME
4546 && (def_arg_stmt = SSA_NAME_DEF_STMT (def_arg))
4547 && gimple_code (def_arg_stmt) == GIMPLE_PHI
4548 && flow_bb_inside_loop_p (outer_loop, gimple_bb (def_arg_stmt))
4549 && vinfo_for_stmt (def_arg_stmt)
4550 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_arg_stmt))
4551 == vect_double_reduction_def)
4552 double_reduc = true;
4555 epilog_reduc_code = ERROR_MARK;
4556 if (reduction_code_for_scalar_code (orig_code, &epilog_reduc_code))
4558 reduc_optab = optab_for_tree_code (epilog_reduc_code, vectype_out,
4562 if (vect_print_dump_info (REPORT_DETAILS))
4563 fprintf (vect_dump, "no optab for reduction.");
4565 epilog_reduc_code = ERROR_MARK;
4569 && optab_handler (reduc_optab, vec_mode) == CODE_FOR_nothing)
4571 if (vect_print_dump_info (REPORT_DETAILS))
4572 fprintf (vect_dump, "reduc op not supported by target.");
4574 epilog_reduc_code = ERROR_MARK;
4579 if (!nested_cycle || double_reduc)
4581 if (vect_print_dump_info (REPORT_DETAILS))
4582 fprintf (vect_dump, "no reduc code for scalar code.");
4588 if (double_reduc && ncopies > 1)
4590 if (vect_print_dump_info (REPORT_DETAILS))
4591 fprintf (vect_dump, "multiple types in double reduction");
4596 if (!vec_stmt) /* transformation not required. */
4598 if (!vect_model_reduction_cost (stmt_info, epilog_reduc_code, ncopies))
4600 STMT_VINFO_TYPE (stmt_info) = reduc_vec_info_type;
4606 if (vect_print_dump_info (REPORT_DETAILS))
4607 fprintf (vect_dump, "transform reduction.");
4609 /* FORNOW: Multiple types are not supported for condition. */
4610 if (code == COND_EXPR)
4611 gcc_assert (ncopies == 1);
4613 /* Create the destination vector */
4614 vec_dest = vect_create_destination_var (scalar_dest, vectype_out);
4616 /* In case the vectorization factor (VF) is bigger than the number
4617 of elements that we can fit in a vectype (nunits), we have to generate
4618 more than one vector stmt - i.e - we need to "unroll" the
4619 vector stmt by a factor VF/nunits. For more details see documentation
4620 in vectorizable_operation. */
4622 /* If the reduction is used in an outer loop we need to generate
4623 VF intermediate results, like so (e.g. for ncopies=2):
4628 (i.e. we generate VF results in 2 registers).
4629 In this case we have a separate def-use cycle for each copy, and therefore
4630 for each copy we get the vector def for the reduction variable from the
4631 respective phi node created for this copy.
4633 Otherwise (the reduction is unused in the loop nest), we can combine
4634 together intermediate results, like so (e.g. for ncopies=2):
4638 (i.e. we generate VF/2 results in a single register).
4639 In this case for each copy we get the vector def for the reduction variable
4640 from the vectorized reduction operation generated in the previous iteration.
4643 if (STMT_VINFO_RELEVANT (stmt_info) == vect_unused_in_scope)
4645 single_defuse_cycle = true;
4649 epilog_copies = ncopies;
4651 prev_stmt_info = NULL;
4652 prev_phi_info = NULL;
4655 vec_num = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
4656 gcc_assert (TYPE_VECTOR_SUBPARTS (vectype_out)
4657 == TYPE_VECTOR_SUBPARTS (vectype_in));
4662 vec_oprnds0 = VEC_alloc (tree, heap, 1);
4663 if (op_type == ternary_op)
4664 vec_oprnds1 = VEC_alloc (tree, heap, 1);
4667 phis = VEC_alloc (gimple, heap, vec_num);
4668 vect_defs = VEC_alloc (tree, heap, vec_num);
4670 VEC_quick_push (tree, vect_defs, NULL_TREE);
4672 for (j = 0; j < ncopies; j++)
4674 if (j == 0 || !single_defuse_cycle)
4676 for (i = 0; i < vec_num; i++)
4678 /* Create the reduction-phi that defines the reduction
4680 new_phi = create_phi_node (vec_dest, loop->header);
4681 set_vinfo_for_stmt (new_phi,
4682 new_stmt_vec_info (new_phi, loop_vinfo,
4684 if (j == 0 || slp_node)
4685 VEC_quick_push (gimple, phis, new_phi);
4689 if (code == COND_EXPR)
4691 gcc_assert (!slp_node);
4692 vectorizable_condition (stmt, gsi, vec_stmt,
4693 PHI_RESULT (VEC_index (gimple, phis, 0)),
4695 /* Multiple types are not supported for condition. */
4702 tree op0, op1 = NULL_TREE;
4704 op0 = ops[!reduc_index];
4705 if (op_type == ternary_op)
4707 if (reduc_index == 0)
4714 vect_get_slp_defs (op0, op1, slp_node, &vec_oprnds0, &vec_oprnds1,
4718 loop_vec_def0 = vect_get_vec_def_for_operand (ops[!reduc_index],
4720 VEC_quick_push (tree, vec_oprnds0, loop_vec_def0);
4721 if (op_type == ternary_op)
4723 loop_vec_def1 = vect_get_vec_def_for_operand (op1, stmt,
4725 VEC_quick_push (tree, vec_oprnds1, loop_vec_def1);
4733 enum vect_def_type dt = vect_unknown_def_type; /* Dummy */
4734 loop_vec_def0 = vect_get_vec_def_for_stmt_copy (dt, loop_vec_def0);
4735 VEC_replace (tree, vec_oprnds0, 0, loop_vec_def0);
4736 if (op_type == ternary_op)
4738 loop_vec_def1 = vect_get_vec_def_for_stmt_copy (dt,
4740 VEC_replace (tree, vec_oprnds1, 0, loop_vec_def1);
4744 if (single_defuse_cycle)
4745 reduc_def = gimple_assign_lhs (new_stmt);
4747 STMT_VINFO_RELATED_STMT (prev_phi_info) = new_phi;
4750 FOR_EACH_VEC_ELT (tree, vec_oprnds0, i, def0)
4753 reduc_def = PHI_RESULT (VEC_index (gimple, phis, i));
4756 if (!single_defuse_cycle || j == 0)
4757 reduc_def = PHI_RESULT (new_phi);
4760 def1 = ((op_type == ternary_op)
4761 ? VEC_index (tree, vec_oprnds1, i) : NULL);
4762 if (op_type == binary_op)
4764 if (reduc_index == 0)
4765 expr = build2 (code, vectype_out, reduc_def, def0);
4767 expr = build2 (code, vectype_out, def0, reduc_def);
4771 if (reduc_index == 0)
4772 expr = build3 (code, vectype_out, reduc_def, def0, def1);
4775 if (reduc_index == 1)
4776 expr = build3 (code, vectype_out, def0, reduc_def, def1);
4778 expr = build3 (code, vectype_out, def0, def1, reduc_def);
4782 new_stmt = gimple_build_assign (vec_dest, expr);
4783 new_temp = make_ssa_name (vec_dest, new_stmt);
4784 gimple_assign_set_lhs (new_stmt, new_temp);
4785 vect_finish_stmt_generation (stmt, new_stmt, gsi);
4789 VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
4790 VEC_quick_push (tree, vect_defs, new_temp);
4793 VEC_replace (tree, vect_defs, 0, new_temp);
4800 STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
4802 STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
4804 prev_stmt_info = vinfo_for_stmt (new_stmt);
4805 prev_phi_info = vinfo_for_stmt (new_phi);
4808 /* Finalize the reduction-phi (set its arguments) and create the
4809 epilog reduction code. */
4810 if ((!single_defuse_cycle || code == COND_EXPR) && !slp_node)
4812 new_temp = gimple_assign_lhs (*vec_stmt);
4813 VEC_replace (tree, vect_defs, 0, new_temp);
4816 vect_create_epilog_for_reduction (vect_defs, stmt, epilog_copies,
4817 epilog_reduc_code, phis, reduc_index,
4818 double_reduc, slp_node);
4820 VEC_free (gimple, heap, phis);
4821 VEC_free (tree, heap, vec_oprnds0);
4823 VEC_free (tree, heap, vec_oprnds1);
4828 /* Function vect_min_worthwhile_factor.
4830 For a loop where we could vectorize the operation indicated by CODE,
4831 return the minimum vectorization factor that makes it worthwhile
4832 to use generic vectors. */
4834 vect_min_worthwhile_factor (enum tree_code code)
4855 /* Function vectorizable_induction
4857 Check if PHI performs an induction computation that can be vectorized.
4858 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
4859 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
4860 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4863 vectorizable_induction (gimple phi, gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
4866 stmt_vec_info stmt_info = vinfo_for_stmt (phi);
4867 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
4868 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
4869 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
4870 int nunits = TYPE_VECTOR_SUBPARTS (vectype);
4871 int ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
4874 gcc_assert (ncopies >= 1);
4875 /* FORNOW. This restriction should be relaxed. */
4876 if (nested_in_vect_loop_p (loop, phi) && ncopies > 1)
4878 if (vect_print_dump_info (REPORT_DETAILS))
4879 fprintf (vect_dump, "multiple types in nested loop.");
4883 if (!STMT_VINFO_RELEVANT_P (stmt_info))
4886 /* FORNOW: SLP not supported. */
4887 if (STMT_SLP_TYPE (stmt_info))
4890 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def);
4892 if (gimple_code (phi) != GIMPLE_PHI)
4895 if (!vec_stmt) /* transformation not required. */
4897 STMT_VINFO_TYPE (stmt_info) = induc_vec_info_type;
4898 if (vect_print_dump_info (REPORT_DETAILS))
4899 fprintf (vect_dump, "=== vectorizable_induction ===");
4900 vect_model_induction_cost (stmt_info, ncopies);
4906 if (vect_print_dump_info (REPORT_DETAILS))
4907 fprintf (vect_dump, "transform induction phi.");
4909 vec_def = get_initial_def_for_induction (phi);
4910 *vec_stmt = SSA_NAME_DEF_STMT (vec_def);
4914 /* Function vectorizable_live_operation.
4916 STMT computes a value that is used outside the loop. Check if
4917 it can be supported. */
4920 vectorizable_live_operation (gimple stmt,
4921 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
4922 gimple *vec_stmt ATTRIBUTE_UNUSED)
4924 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4925 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
4926 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
4932 enum vect_def_type dt;
4933 enum tree_code code;
4934 enum gimple_rhs_class rhs_class;
4936 gcc_assert (STMT_VINFO_LIVE_P (stmt_info));
4938 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_reduction_def)
4941 if (!is_gimple_assign (stmt))
4944 if (TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
4947 /* FORNOW. CHECKME. */
4948 if (nested_in_vect_loop_p (loop, stmt))
4951 code = gimple_assign_rhs_code (stmt);
4952 op_type = TREE_CODE_LENGTH (code);
4953 rhs_class = get_gimple_rhs_class (code);
4954 gcc_assert (rhs_class != GIMPLE_UNARY_RHS || op_type == unary_op);
4955 gcc_assert (rhs_class != GIMPLE_BINARY_RHS || op_type == binary_op);
4957 /* FORNOW: support only if all uses are invariant. This means
4958 that the scalar operations can remain in place, unvectorized.
4959 The original last scalar value that they compute will be used. */
4961 for (i = 0; i < op_type; i++)
4963 if (rhs_class == GIMPLE_SINGLE_RHS)
4964 op = TREE_OPERAND (gimple_op (stmt, 1), i);
4966 op = gimple_op (stmt, i + 1);
4968 && !vect_is_simple_use (op, loop_vinfo, NULL, &def_stmt, &def, &dt))
4970 if (vect_print_dump_info (REPORT_DETAILS))
4971 fprintf (vect_dump, "use not simple.");
4975 if (dt != vect_external_def && dt != vect_constant_def)
4979 /* No transformation is required for the cases we currently support. */
4983 /* Kill any debug uses outside LOOP of SSA names defined in STMT. */
4986 vect_loop_kill_debug_uses (struct loop *loop, gimple stmt)
4988 ssa_op_iter op_iter;
4989 imm_use_iterator imm_iter;
4990 def_operand_p def_p;
4993 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_DEF)
4995 FOR_EACH_IMM_USE_STMT (ustmt, imm_iter, DEF_FROM_PTR (def_p))
4999 if (!is_gimple_debug (ustmt))
5002 bb = gimple_bb (ustmt);
5004 if (!flow_bb_inside_loop_p (loop, bb))
5006 if (gimple_debug_bind_p (ustmt))
5008 if (vect_print_dump_info (REPORT_DETAILS))
5009 fprintf (vect_dump, "killing debug use");
5011 gimple_debug_bind_reset_value (ustmt);
5012 update_stmt (ustmt);
5021 /* Function vect_transform_loop.
5023 The analysis phase has determined that the loop is vectorizable.
5024 Vectorize the loop - created vectorized stmts to replace the scalar
5025 stmts in the loop, and update the loop exit condition. */
5028 vect_transform_loop (loop_vec_info loop_vinfo)
5030 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
5031 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
5032 int nbbs = loop->num_nodes;
5033 gimple_stmt_iterator si;
5036 int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
5038 bool slp_scheduled = false;
5039 unsigned int nunits;
5040 tree cond_expr = NULL_TREE;
5041 gimple_seq cond_expr_stmt_list = NULL;
5042 bool do_peeling_for_loop_bound;
5044 if (vect_print_dump_info (REPORT_DETAILS))
5045 fprintf (vect_dump, "=== vec_transform_loop ===");
5047 /* Peel the loop if there are data refs with unknown alignment.
5048 Only one data ref with unknown store is allowed. */
5050 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo))
5051 vect_do_peeling_for_alignment (loop_vinfo);
5053 do_peeling_for_loop_bound
5054 = (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
5055 || (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
5056 && LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0)
5057 || LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo));
5059 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
5060 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
5061 vect_loop_versioning (loop_vinfo,
5062 !do_peeling_for_loop_bound,
5063 &cond_expr, &cond_expr_stmt_list);
5065 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
5066 compile time constant), or it is a constant that doesn't divide by the
5067 vectorization factor, then an epilog loop needs to be created.
5068 We therefore duplicate the loop: the original loop will be vectorized,
5069 and will compute the first (n/VF) iterations. The second copy of the loop
5070 will remain scalar and will compute the remaining (n%VF) iterations.
5071 (VF is the vectorization factor). */
5073 if (do_peeling_for_loop_bound)
5074 vect_do_peeling_for_loop_bound (loop_vinfo, &ratio,
5075 cond_expr, cond_expr_stmt_list);
5077 ratio = build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo)),
5078 LOOP_VINFO_INT_NITERS (loop_vinfo) / vectorization_factor);
5080 /* 1) Make sure the loop header has exactly two entries
5081 2) Make sure we have a preheader basic block. */
5083 gcc_assert (EDGE_COUNT (loop->header->preds) == 2);
5085 split_edge (loop_preheader_edge (loop));
5087 /* FORNOW: the vectorizer supports only loops which body consist
5088 of one basic block (header + empty latch). When the vectorizer will
5089 support more involved loop forms, the order by which the BBs are
5090 traversed need to be reconsidered. */
5092 for (i = 0; i < nbbs; i++)
5094 basic_block bb = bbs[i];
5095 stmt_vec_info stmt_info;
5098 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
5100 phi = gsi_stmt (si);
5101 if (vect_print_dump_info (REPORT_DETAILS))
5103 fprintf (vect_dump, "------>vectorizing phi: ");
5104 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
5106 stmt_info = vinfo_for_stmt (phi);
5110 if (MAY_HAVE_DEBUG_STMTS && !STMT_VINFO_LIVE_P (stmt_info))
5111 vect_loop_kill_debug_uses (loop, phi);
5113 if (!STMT_VINFO_RELEVANT_P (stmt_info)
5114 && !STMT_VINFO_LIVE_P (stmt_info))
5117 if ((TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info))
5118 != (unsigned HOST_WIDE_INT) vectorization_factor)
5119 && vect_print_dump_info (REPORT_DETAILS))
5120 fprintf (vect_dump, "multiple-types.");
5122 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def)
5124 if (vect_print_dump_info (REPORT_DETAILS))
5125 fprintf (vect_dump, "transform phi.");
5126 vect_transform_stmt (phi, NULL, NULL, NULL, NULL);
5130 for (si = gsi_start_bb (bb); !gsi_end_p (si);)
5132 gimple stmt = gsi_stmt (si), pattern_stmt;
5135 if (vect_print_dump_info (REPORT_DETAILS))
5137 fprintf (vect_dump, "------>vectorizing statement: ");
5138 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
5141 stmt_info = vinfo_for_stmt (stmt);
5143 /* vector stmts created in the outer-loop during vectorization of
5144 stmts in an inner-loop may not have a stmt_info, and do not
5145 need to be vectorized. */
5152 if (MAY_HAVE_DEBUG_STMTS && !STMT_VINFO_LIVE_P (stmt_info))
5153 vect_loop_kill_debug_uses (loop, stmt);
5155 if (!STMT_VINFO_RELEVANT_P (stmt_info)
5156 && !STMT_VINFO_LIVE_P (stmt_info))
5158 if (STMT_VINFO_IN_PATTERN_P (stmt_info)
5159 && (pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info))
5160 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt))
5161 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt))))
5163 stmt = pattern_stmt;
5164 stmt_info = vinfo_for_stmt (stmt);
5173 gcc_assert (STMT_VINFO_VECTYPE (stmt_info));
5174 nunits = (unsigned int) TYPE_VECTOR_SUBPARTS (
5175 STMT_VINFO_VECTYPE (stmt_info));
5176 if (!STMT_SLP_TYPE (stmt_info)
5177 && nunits != (unsigned int) vectorization_factor
5178 && vect_print_dump_info (REPORT_DETAILS))
5179 /* For SLP VF is set according to unrolling factor, and not to
5180 vector size, hence for SLP this print is not valid. */
5181 fprintf (vect_dump, "multiple-types.");
5183 /* SLP. Schedule all the SLP instances when the first SLP stmt is
5185 if (STMT_SLP_TYPE (stmt_info))
5189 slp_scheduled = true;
5191 if (vect_print_dump_info (REPORT_DETAILS))
5192 fprintf (vect_dump, "=== scheduling SLP instances ===");
5194 vect_schedule_slp (loop_vinfo, NULL);
5197 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
5198 if (!vinfo_for_stmt (stmt) || PURE_SLP_STMT (stmt_info))
5205 /* -------- vectorize statement ------------ */
5206 if (vect_print_dump_info (REPORT_DETAILS))
5207 fprintf (vect_dump, "transform statement.");
5209 strided_store = false;
5210 is_store = vect_transform_stmt (stmt, &si, &strided_store, NULL, NULL);
5213 if (STMT_VINFO_STRIDED_ACCESS (stmt_info))
5215 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
5216 interleaving chain was completed - free all the stores in
5218 vect_remove_stores (GROUP_FIRST_ELEMENT (stmt_info));
5219 gsi_remove (&si, true);
5224 /* Free the attached stmt_vec_info and remove the stmt. */
5225 free_stmt_vec_info (stmt);
5226 gsi_remove (&si, true);
5234 slpeel_make_loop_iterate_ntimes (loop, ratio);
5236 /* The memory tags and pointers in vectorized statements need to
5237 have their SSA forms updated. FIXME, why can't this be delayed
5238 until all the loops have been transformed? */
5239 update_ssa (TODO_update_ssa);
5241 if (vect_print_dump_info (REPORT_VECTORIZED_LOCATIONS))
5242 fprintf (vect_dump, "LOOP VECTORIZED.");
5243 if (loop->inner && vect_print_dump_info (REPORT_VECTORIZED_LOCATIONS))
5244 fprintf (vect_dump, "OUTER LOOP VECTORIZED.");