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"
41 #include "tree-chrec.h"
42 #include "tree-scalar-evolution.h"
43 #include "tree-vectorizer.h"
45 /* Loop Vectorization Pass.
47 This pass tries to vectorize loops.
49 For example, the vectorizer transforms the following simple loop:
51 short a[N]; short b[N]; short c[N]; int i;
57 as if it was manually vectorized by rewriting the source code into:
59 typedef int __attribute__((mode(V8HI))) v8hi;
60 short a[N]; short b[N]; short c[N]; int i;
61 v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
64 for (i=0; i<N/8; i++){
71 The main entry to this pass is vectorize_loops(), in which
72 the vectorizer applies a set of analyses on a given set of loops,
73 followed by the actual vectorization transformation for the loops that
74 had successfully passed the analysis phase.
75 Throughout this pass we make a distinction between two types of
76 data: scalars (which are represented by SSA_NAMES), and memory references
77 ("data-refs"). These two types of data require different handling both
78 during analysis and transformation. The types of data-refs that the
79 vectorizer currently supports are ARRAY_REFS which base is an array DECL
80 (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
81 accesses are required to have a simple (consecutive) access pattern.
85 The driver for the analysis phase is vect_analyze_loop().
86 It applies a set of analyses, some of which rely on the scalar evolution
87 analyzer (scev) developed by Sebastian Pop.
89 During the analysis phase the vectorizer records some information
90 per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
91 loop, as well as general information about the loop as a whole, which is
92 recorded in a "loop_vec_info" struct attached to each loop.
96 The loop transformation phase scans all the stmts in the loop, and
97 creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
98 the loop that needs to be vectorized. It inserts the vector code sequence
99 just before the scalar stmt S, and records a pointer to the vector code
100 in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
101 attached to S). This pointer will be used for the vectorization of following
102 stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
103 otherwise, we rely on dead code elimination for removing it.
105 For example, say stmt S1 was vectorized into stmt VS1:
108 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
111 To vectorize stmt S2, the vectorizer first finds the stmt that defines
112 the operand 'b' (S1), and gets the relevant vector def 'vb' from the
113 vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
114 resulting sequence would be:
117 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
119 S2: a = b; STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
121 Operands that are not SSA_NAMEs, are data-refs that appear in
122 load/store operations (like 'x[i]' in S1), and are handled differently.
126 Currently the only target specific information that is used is the
127 size of the vector (in bytes) - "UNITS_PER_SIMD_WORD". Targets that can
128 support different sizes of vectors, for now will need to specify one value
129 for "UNITS_PER_SIMD_WORD". More flexibility will be added in the future.
131 Since we only vectorize operations which vector form can be
132 expressed using existing tree codes, to verify that an operation is
133 supported, the vectorizer checks the relevant optab at the relevant
134 machine_mode (e.g, optab_handler (add_optab, V8HImode)->insn_code). If
135 the value found is CODE_FOR_nothing, then there's no target support, and
136 we can't vectorize the stmt.
138 For additional information on this project see:
139 http://gcc.gnu.org/projects/tree-ssa/vectorization.html
142 /* Function vect_determine_vectorization_factor
144 Determine the vectorization factor (VF). VF is the number of data elements
145 that are operated upon in parallel in a single iteration of the vectorized
146 loop. For example, when vectorizing a loop that operates on 4byte elements,
147 on a target with vector size (VS) 16byte, the VF is set to 4, since 4
148 elements can fit in a single vector register.
150 We currently support vectorization of loops in which all types operated upon
151 are of the same size. Therefore this function currently sets VF according to
152 the size of the types operated upon, and fails if there are multiple sizes
155 VF is also the factor by which the loop iterations are strip-mined, e.g.:
162 for (i=0; i<N; i+=VF){
163 a[i:VF] = b[i:VF] + c[i:VF];
168 vect_determine_vectorization_factor (loop_vec_info loop_vinfo)
170 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
171 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
172 int nbbs = loop->num_nodes;
173 gimple_stmt_iterator si;
174 unsigned int vectorization_factor = 0;
179 stmt_vec_info stmt_info;
183 if (vect_print_dump_info (REPORT_DETAILS))
184 fprintf (vect_dump, "=== vect_determine_vectorization_factor ===");
186 for (i = 0; i < nbbs; i++)
188 basic_block bb = bbs[i];
190 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
193 stmt_info = vinfo_for_stmt (phi);
194 if (vect_print_dump_info (REPORT_DETAILS))
196 fprintf (vect_dump, "==> examining phi: ");
197 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
200 gcc_assert (stmt_info);
202 if (STMT_VINFO_RELEVANT_P (stmt_info))
204 gcc_assert (!STMT_VINFO_VECTYPE (stmt_info));
205 scalar_type = TREE_TYPE (PHI_RESULT (phi));
207 if (vect_print_dump_info (REPORT_DETAILS))
209 fprintf (vect_dump, "get vectype for scalar type: ");
210 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
213 vectype = get_vectype_for_scalar_type (scalar_type);
216 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
219 "not vectorized: unsupported data-type ");
220 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
224 STMT_VINFO_VECTYPE (stmt_info) = vectype;
226 if (vect_print_dump_info (REPORT_DETAILS))
228 fprintf (vect_dump, "vectype: ");
229 print_generic_expr (vect_dump, vectype, TDF_SLIM);
232 nunits = TYPE_VECTOR_SUBPARTS (vectype);
233 if (vect_print_dump_info (REPORT_DETAILS))
234 fprintf (vect_dump, "nunits = %d", nunits);
236 if (!vectorization_factor
237 || (nunits > vectorization_factor))
238 vectorization_factor = nunits;
242 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
245 gimple stmt = gsi_stmt (si);
246 stmt_info = vinfo_for_stmt (stmt);
248 if (vect_print_dump_info (REPORT_DETAILS))
250 fprintf (vect_dump, "==> examining statement: ");
251 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
254 gcc_assert (stmt_info);
256 /* skip stmts which do not need to be vectorized. */
257 if (!STMT_VINFO_RELEVANT_P (stmt_info)
258 && !STMT_VINFO_LIVE_P (stmt_info))
260 if (vect_print_dump_info (REPORT_DETAILS))
261 fprintf (vect_dump, "skip.");
265 if (gimple_get_lhs (stmt) == NULL_TREE)
267 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
269 fprintf (vect_dump, "not vectorized: irregular stmt.");
270 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
275 if (VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt))))
277 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
279 fprintf (vect_dump, "not vectorized: vector stmt in loop:");
280 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
285 if (STMT_VINFO_VECTYPE (stmt_info))
287 /* The only case when a vectype had been already set is for stmts
288 that contain a dataref, or for "pattern-stmts" (stmts generated
289 by the vectorizer to represent/replace a certain idiom). */
290 gcc_assert (STMT_VINFO_DATA_REF (stmt_info)
291 || is_pattern_stmt_p (stmt_info));
292 vectype = STMT_VINFO_VECTYPE (stmt_info);
296 gcc_assert (!STMT_VINFO_DATA_REF (stmt_info)
297 && !is_pattern_stmt_p (stmt_info));
299 scalar_type = TREE_TYPE (gimple_get_lhs (stmt));
300 if (vect_print_dump_info (REPORT_DETAILS))
302 fprintf (vect_dump, "get vectype for scalar type: ");
303 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
305 vectype = get_vectype_for_scalar_type (scalar_type);
308 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
311 "not vectorized: unsupported data-type ");
312 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
317 STMT_VINFO_VECTYPE (stmt_info) = vectype;
320 /* The vectorization factor is according to the smallest
321 scalar type (or the largest vector size, but we only
322 support one vector size per loop). */
323 scalar_type = vect_get_smallest_scalar_type (stmt, &dummy,
325 if (vect_print_dump_info (REPORT_DETAILS))
327 fprintf (vect_dump, "get vectype for scalar type: ");
328 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
330 vf_vectype = get_vectype_for_scalar_type (scalar_type);
333 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
336 "not vectorized: unsupported data-type ");
337 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
342 if ((GET_MODE_SIZE (TYPE_MODE (vectype))
343 != GET_MODE_SIZE (TYPE_MODE (vf_vectype))))
345 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
348 "not vectorized: different sized vector "
349 "types in statement, ");
350 print_generic_expr (vect_dump, vectype, TDF_SLIM);
351 fprintf (vect_dump, " and ");
352 print_generic_expr (vect_dump, vf_vectype, TDF_SLIM);
357 if (vect_print_dump_info (REPORT_DETAILS))
359 fprintf (vect_dump, "vectype: ");
360 print_generic_expr (vect_dump, vf_vectype, TDF_SLIM);
363 nunits = TYPE_VECTOR_SUBPARTS (vf_vectype);
364 if (vect_print_dump_info (REPORT_DETAILS))
365 fprintf (vect_dump, "nunits = %d", nunits);
367 if (!vectorization_factor
368 || (nunits > vectorization_factor))
369 vectorization_factor = nunits;
373 /* TODO: Analyze cost. Decide if worth while to vectorize. */
374 if (vect_print_dump_info (REPORT_DETAILS))
375 fprintf (vect_dump, "vectorization factor = %d", vectorization_factor);
376 if (vectorization_factor <= 1)
378 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
379 fprintf (vect_dump, "not vectorized: unsupported data-type");
382 LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
388 /* Function vect_is_simple_iv_evolution.
390 FORNOW: A simple evolution of an induction variables in the loop is
391 considered a polynomial evolution with constant step. */
394 vect_is_simple_iv_evolution (unsigned loop_nb, tree access_fn, tree * init,
399 tree evolution_part = evolution_part_in_loop_num (access_fn, loop_nb);
401 /* When there is no evolution in this loop, the evolution function
403 if (evolution_part == NULL_TREE)
406 /* When the evolution is a polynomial of degree >= 2
407 the evolution function is not "simple". */
408 if (tree_is_chrec (evolution_part))
411 step_expr = evolution_part;
412 init_expr = unshare_expr (initial_condition_in_loop_num (access_fn, loop_nb));
414 if (vect_print_dump_info (REPORT_DETAILS))
416 fprintf (vect_dump, "step: ");
417 print_generic_expr (vect_dump, step_expr, TDF_SLIM);
418 fprintf (vect_dump, ", init: ");
419 print_generic_expr (vect_dump, init_expr, TDF_SLIM);
425 if (TREE_CODE (step_expr) != INTEGER_CST)
427 if (vect_print_dump_info (REPORT_DETAILS))
428 fprintf (vect_dump, "step unknown.");
435 /* Function vect_analyze_scalar_cycles_1.
437 Examine the cross iteration def-use cycles of scalar variables
438 in LOOP. LOOP_VINFO represents the loop that is now being
439 considered for vectorization (can be LOOP, or an outer-loop
443 vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo, struct loop *loop)
445 basic_block bb = loop->header;
447 VEC(gimple,heap) *worklist = VEC_alloc (gimple, heap, 64);
448 gimple_stmt_iterator gsi;
451 if (vect_print_dump_info (REPORT_DETAILS))
452 fprintf (vect_dump, "=== vect_analyze_scalar_cycles ===");
454 /* First - identify all inductions. Reduction detection assumes that all the
455 inductions have been identified, therefore, this order must not be
457 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
459 gimple phi = gsi_stmt (gsi);
460 tree access_fn = NULL;
461 tree def = PHI_RESULT (phi);
462 stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
464 if (vect_print_dump_info (REPORT_DETAILS))
466 fprintf (vect_dump, "Analyze phi: ");
467 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
470 /* Skip virtual phi's. The data dependences that are associated with
471 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
472 if (!is_gimple_reg (SSA_NAME_VAR (def)))
475 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_unknown_def_type;
477 /* Analyze the evolution function. */
478 access_fn = analyze_scalar_evolution (loop, def);
479 if (access_fn && vect_print_dump_info (REPORT_DETAILS))
481 fprintf (vect_dump, "Access function of PHI: ");
482 print_generic_expr (vect_dump, access_fn, TDF_SLIM);
486 || !vect_is_simple_iv_evolution (loop->num, access_fn, &dumy, &dumy))
488 VEC_safe_push (gimple, heap, worklist, phi);
492 if (vect_print_dump_info (REPORT_DETAILS))
493 fprintf (vect_dump, "Detected induction.");
494 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def;
498 /* Second - identify all reductions and nested cycles. */
499 while (VEC_length (gimple, worklist) > 0)
501 gimple phi = VEC_pop (gimple, worklist);
502 tree def = PHI_RESULT (phi);
503 stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
507 if (vect_print_dump_info (REPORT_DETAILS))
509 fprintf (vect_dump, "Analyze phi: ");
510 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
513 gcc_assert (is_gimple_reg (SSA_NAME_VAR (def)));
514 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_unknown_def_type);
516 nested_cycle = (loop != LOOP_VINFO_LOOP (loop_vinfo));
517 reduc_stmt = vect_force_simple_reduction (loop_vinfo, phi, !nested_cycle,
523 if (vect_print_dump_info (REPORT_DETAILS))
524 fprintf (vect_dump, "Detected double reduction.");
526 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_double_reduction_def;
527 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
528 vect_double_reduction_def;
534 if (vect_print_dump_info (REPORT_DETAILS))
535 fprintf (vect_dump, "Detected vectorizable nested cycle.");
537 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_nested_cycle;
538 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
543 if (vect_print_dump_info (REPORT_DETAILS))
544 fprintf (vect_dump, "Detected reduction.");
546 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_reduction_def;
547 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
549 /* Store the reduction cycles for possible vectorization in
551 VEC_safe_push (gimple, heap,
552 LOOP_VINFO_REDUCTIONS (loop_vinfo),
558 if (vect_print_dump_info (REPORT_DETAILS))
559 fprintf (vect_dump, "Unknown def-use cycle pattern.");
562 VEC_free (gimple, heap, worklist);
566 /* Function vect_analyze_scalar_cycles.
568 Examine the cross iteration def-use cycles of scalar variables, by
569 analyzing the loop-header PHIs of scalar variables; Classify each
570 cycle as one of the following: invariant, induction, reduction, unknown.
571 We do that for the loop represented by LOOP_VINFO, and also to its
572 inner-loop, if exists.
573 Examples for scalar cycles:
588 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
590 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
592 vect_analyze_scalar_cycles_1 (loop_vinfo, loop);
594 /* When vectorizing an outer-loop, the inner-loop is executed sequentially.
595 Reductions in such inner-loop therefore have different properties than
596 the reductions in the nest that gets vectorized:
597 1. When vectorized, they are executed in the same order as in the original
598 scalar loop, so we can't change the order of computation when
600 2. FIXME: Inner-loop reductions can be used in the inner-loop, so the
601 current checks are too strict. */
604 vect_analyze_scalar_cycles_1 (loop_vinfo, loop->inner);
607 /* Function vect_get_loop_niters.
609 Determine how many iterations the loop is executed.
610 If an expression that represents the number of iterations
611 can be constructed, place it in NUMBER_OF_ITERATIONS.
612 Return the loop exit condition. */
615 vect_get_loop_niters (struct loop *loop, tree *number_of_iterations)
619 if (vect_print_dump_info (REPORT_DETAILS))
620 fprintf (vect_dump, "=== get_loop_niters ===");
622 niters = number_of_exit_cond_executions (loop);
624 if (niters != NULL_TREE
625 && niters != chrec_dont_know)
627 *number_of_iterations = niters;
629 if (vect_print_dump_info (REPORT_DETAILS))
631 fprintf (vect_dump, "==> get_loop_niters:" );
632 print_generic_expr (vect_dump, *number_of_iterations, TDF_SLIM);
636 return get_loop_exit_condition (loop);
640 /* Function bb_in_loop_p
642 Used as predicate for dfs order traversal of the loop bbs. */
645 bb_in_loop_p (const_basic_block bb, const void *data)
647 const struct loop *const loop = (const struct loop *)data;
648 if (flow_bb_inside_loop_p (loop, bb))
654 /* Function new_loop_vec_info.
656 Create and initialize a new loop_vec_info struct for LOOP, as well as
657 stmt_vec_info structs for all the stmts in LOOP. */
660 new_loop_vec_info (struct loop *loop)
664 gimple_stmt_iterator si;
665 unsigned int i, nbbs;
667 res = (loop_vec_info) xcalloc (1, sizeof (struct _loop_vec_info));
668 LOOP_VINFO_LOOP (res) = loop;
670 bbs = get_loop_body (loop);
672 /* Create/Update stmt_info for all stmts in the loop. */
673 for (i = 0; i < loop->num_nodes; i++)
675 basic_block bb = bbs[i];
677 /* BBs in a nested inner-loop will have been already processed (because
678 we will have called vect_analyze_loop_form for any nested inner-loop).
679 Therefore, for stmts in an inner-loop we just want to update the
680 STMT_VINFO_LOOP_VINFO field of their stmt_info to point to the new
681 loop_info of the outer-loop we are currently considering to vectorize
682 (instead of the loop_info of the inner-loop).
683 For stmts in other BBs we need to create a stmt_info from scratch. */
684 if (bb->loop_father != loop)
687 gcc_assert (loop->inner && bb->loop_father == loop->inner);
688 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
690 gimple phi = gsi_stmt (si);
691 stmt_vec_info stmt_info = vinfo_for_stmt (phi);
692 loop_vec_info inner_loop_vinfo =
693 STMT_VINFO_LOOP_VINFO (stmt_info);
694 gcc_assert (loop->inner == LOOP_VINFO_LOOP (inner_loop_vinfo));
695 STMT_VINFO_LOOP_VINFO (stmt_info) = res;
697 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
699 gimple stmt = gsi_stmt (si);
700 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
701 loop_vec_info inner_loop_vinfo =
702 STMT_VINFO_LOOP_VINFO (stmt_info);
703 gcc_assert (loop->inner == LOOP_VINFO_LOOP (inner_loop_vinfo));
704 STMT_VINFO_LOOP_VINFO (stmt_info) = res;
709 /* bb in current nest. */
710 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
712 gimple phi = gsi_stmt (si);
713 gimple_set_uid (phi, 0);
714 set_vinfo_for_stmt (phi, new_stmt_vec_info (phi, res, NULL));
717 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
719 gimple stmt = gsi_stmt (si);
720 gimple_set_uid (stmt, 0);
721 set_vinfo_for_stmt (stmt, new_stmt_vec_info (stmt, res, NULL));
726 /* CHECKME: We want to visit all BBs before their successors (except for
727 latch blocks, for which this assertion wouldn't hold). In the simple
728 case of the loop forms we allow, a dfs order of the BBs would the same
729 as reversed postorder traversal, so we are safe. */
732 bbs = XCNEWVEC (basic_block, loop->num_nodes);
733 nbbs = dfs_enumerate_from (loop->header, 0, bb_in_loop_p,
734 bbs, loop->num_nodes, loop);
735 gcc_assert (nbbs == loop->num_nodes);
737 LOOP_VINFO_BBS (res) = bbs;
738 LOOP_VINFO_NITERS (res) = NULL;
739 LOOP_VINFO_NITERS_UNCHANGED (res) = NULL;
740 LOOP_VINFO_COST_MODEL_MIN_ITERS (res) = 0;
741 LOOP_VINFO_VECTORIZABLE_P (res) = 0;
742 LOOP_PEELING_FOR_ALIGNMENT (res) = 0;
743 LOOP_VINFO_VECT_FACTOR (res) = 0;
744 LOOP_VINFO_DATAREFS (res) = VEC_alloc (data_reference_p, heap, 10);
745 LOOP_VINFO_DDRS (res) = VEC_alloc (ddr_p, heap, 10 * 10);
746 LOOP_VINFO_UNALIGNED_DR (res) = NULL;
747 LOOP_VINFO_MAY_MISALIGN_STMTS (res) =
748 VEC_alloc (gimple, heap,
749 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS));
750 LOOP_VINFO_MAY_ALIAS_DDRS (res) =
751 VEC_alloc (ddr_p, heap,
752 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS));
753 LOOP_VINFO_STRIDED_STORES (res) = VEC_alloc (gimple, heap, 10);
754 LOOP_VINFO_REDUCTIONS (res) = VEC_alloc (gimple, heap, 10);
755 LOOP_VINFO_SLP_INSTANCES (res) = VEC_alloc (slp_instance, heap, 10);
756 LOOP_VINFO_SLP_UNROLLING_FACTOR (res) = 1;
762 /* Function destroy_loop_vec_info.
764 Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
765 stmts in the loop. */
768 destroy_loop_vec_info (loop_vec_info loop_vinfo, bool clean_stmts)
773 gimple_stmt_iterator si;
775 VEC (slp_instance, heap) *slp_instances;
776 slp_instance instance;
781 loop = LOOP_VINFO_LOOP (loop_vinfo);
783 bbs = LOOP_VINFO_BBS (loop_vinfo);
784 nbbs = loop->num_nodes;
788 free (LOOP_VINFO_BBS (loop_vinfo));
789 free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo));
790 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo));
791 VEC_free (gimple, heap, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
798 for (j = 0; j < nbbs; j++)
800 basic_block bb = bbs[j];
801 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
802 free_stmt_vec_info (gsi_stmt (si));
804 for (si = gsi_start_bb (bb); !gsi_end_p (si); )
806 gimple stmt = gsi_stmt (si);
807 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
811 /* Check if this is a "pattern stmt" (introduced by the
812 vectorizer during the pattern recognition pass). */
813 bool remove_stmt_p = false;
814 gimple orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
817 stmt_vec_info orig_stmt_info = vinfo_for_stmt (orig_stmt);
819 && STMT_VINFO_IN_PATTERN_P (orig_stmt_info))
820 remove_stmt_p = true;
823 /* Free stmt_vec_info. */
824 free_stmt_vec_info (stmt);
826 /* Remove dead "pattern stmts". */
828 gsi_remove (&si, true);
834 free (LOOP_VINFO_BBS (loop_vinfo));
835 free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo));
836 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo));
837 VEC_free (gimple, heap, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
838 VEC_free (ddr_p, heap, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo));
839 slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
840 for (j = 0; VEC_iterate (slp_instance, slp_instances, j, instance); j++)
841 vect_free_slp_instance (instance);
843 VEC_free (slp_instance, heap, LOOP_VINFO_SLP_INSTANCES (loop_vinfo));
844 VEC_free (gimple, heap, LOOP_VINFO_STRIDED_STORES (loop_vinfo));
845 VEC_free (gimple, heap, LOOP_VINFO_REDUCTIONS (loop_vinfo));
852 /* Function vect_analyze_loop_1.
854 Apply a set of analyses on LOOP, and create a loop_vec_info struct
855 for it. The different analyses will record information in the
856 loop_vec_info struct. This is a subset of the analyses applied in
857 vect_analyze_loop, to be applied on an inner-loop nested in the loop
858 that is now considered for (outer-loop) vectorization. */
861 vect_analyze_loop_1 (struct loop *loop)
863 loop_vec_info loop_vinfo;
865 if (vect_print_dump_info (REPORT_DETAILS))
866 fprintf (vect_dump, "===== analyze_loop_nest_1 =====");
868 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
870 loop_vinfo = vect_analyze_loop_form (loop);
873 if (vect_print_dump_info (REPORT_DETAILS))
874 fprintf (vect_dump, "bad inner-loop form.");
882 /* Function vect_analyze_loop_form.
884 Verify that certain CFG restrictions hold, including:
885 - the loop has a pre-header
886 - the loop has a single entry and exit
887 - the loop exit condition is simple enough, and the number of iterations
888 can be analyzed (a countable loop). */
891 vect_analyze_loop_form (struct loop *loop)
893 loop_vec_info loop_vinfo;
895 tree number_of_iterations = NULL;
896 loop_vec_info inner_loop_vinfo = NULL;
898 if (vect_print_dump_info (REPORT_DETAILS))
899 fprintf (vect_dump, "=== vect_analyze_loop_form ===");
901 /* Different restrictions apply when we are considering an inner-most loop,
902 vs. an outer (nested) loop.
903 (FORNOW. May want to relax some of these restrictions in the future). */
907 /* Inner-most loop. We currently require that the number of BBs is
908 exactly 2 (the header and latch). Vectorizable inner-most loops
919 if (loop->num_nodes != 2)
921 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
922 fprintf (vect_dump, "not vectorized: control flow in loop.");
926 if (empty_block_p (loop->header))
928 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
929 fprintf (vect_dump, "not vectorized: empty loop.");
935 struct loop *innerloop = loop->inner;
938 /* Nested loop. We currently require that the loop is doubly-nested,
939 contains a single inner loop, and the number of BBs is exactly 5.
940 Vectorizable outer-loops look like this:
952 The inner-loop has the properties expected of inner-most loops
953 as described above. */
955 if ((loop->inner)->inner || (loop->inner)->next)
957 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
958 fprintf (vect_dump, "not vectorized: multiple nested loops.");
962 /* Analyze the inner-loop. */
963 inner_loop_vinfo = vect_analyze_loop_1 (loop->inner);
964 if (!inner_loop_vinfo)
966 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
967 fprintf (vect_dump, "not vectorized: Bad inner loop.");
971 if (!expr_invariant_in_loop_p (loop,
972 LOOP_VINFO_NITERS (inner_loop_vinfo)))
974 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
976 "not vectorized: inner-loop count not invariant.");
977 destroy_loop_vec_info (inner_loop_vinfo, true);
981 if (loop->num_nodes != 5)
983 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
984 fprintf (vect_dump, "not vectorized: control flow in loop.");
985 destroy_loop_vec_info (inner_loop_vinfo, true);
989 gcc_assert (EDGE_COUNT (innerloop->header->preds) == 2);
990 entryedge = EDGE_PRED (innerloop->header, 0);
991 if (EDGE_PRED (innerloop->header, 0)->src == innerloop->latch)
992 entryedge = EDGE_PRED (innerloop->header, 1);
994 if (entryedge->src != loop->header
995 || !single_exit (innerloop)
996 || single_exit (innerloop)->dest != EDGE_PRED (loop->latch, 0)->src)
998 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
999 fprintf (vect_dump, "not vectorized: unsupported outerloop form.");
1000 destroy_loop_vec_info (inner_loop_vinfo, true);
1004 if (vect_print_dump_info (REPORT_DETAILS))
1005 fprintf (vect_dump, "Considering outer-loop vectorization.");
1008 if (!single_exit (loop)
1009 || EDGE_COUNT (loop->header->preds) != 2)
1011 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1013 if (!single_exit (loop))
1014 fprintf (vect_dump, "not vectorized: multiple exits.");
1015 else if (EDGE_COUNT (loop->header->preds) != 2)
1016 fprintf (vect_dump, "not vectorized: too many incoming edges.");
1018 if (inner_loop_vinfo)
1019 destroy_loop_vec_info (inner_loop_vinfo, true);
1023 /* We assume that the loop exit condition is at the end of the loop. i.e,
1024 that the loop is represented as a do-while (with a proper if-guard
1025 before the loop if needed), where the loop header contains all the
1026 executable statements, and the latch is empty. */
1027 if (!empty_block_p (loop->latch)
1028 || !gimple_seq_empty_p (phi_nodes (loop->latch)))
1030 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1031 fprintf (vect_dump, "not vectorized: unexpected loop form.");
1032 if (inner_loop_vinfo)
1033 destroy_loop_vec_info (inner_loop_vinfo, true);
1037 /* Make sure there exists a single-predecessor exit bb: */
1038 if (!single_pred_p (single_exit (loop)->dest))
1040 edge e = single_exit (loop);
1041 if (!(e->flags & EDGE_ABNORMAL))
1043 split_loop_exit_edge (e);
1044 if (vect_print_dump_info (REPORT_DETAILS))
1045 fprintf (vect_dump, "split exit edge.");
1049 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1050 fprintf (vect_dump, "not vectorized: abnormal loop exit edge.");
1051 if (inner_loop_vinfo)
1052 destroy_loop_vec_info (inner_loop_vinfo, true);
1057 loop_cond = vect_get_loop_niters (loop, &number_of_iterations);
1060 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1061 fprintf (vect_dump, "not vectorized: complicated exit condition.");
1062 if (inner_loop_vinfo)
1063 destroy_loop_vec_info (inner_loop_vinfo, true);
1067 if (!number_of_iterations)
1069 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1071 "not vectorized: number of iterations cannot be computed.");
1072 if (inner_loop_vinfo)
1073 destroy_loop_vec_info (inner_loop_vinfo, true);
1077 if (chrec_contains_undetermined (number_of_iterations))
1079 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1080 fprintf (vect_dump, "Infinite number of iterations.");
1081 if (inner_loop_vinfo)
1082 destroy_loop_vec_info (inner_loop_vinfo, true);
1086 if (!NITERS_KNOWN_P (number_of_iterations))
1088 if (vect_print_dump_info (REPORT_DETAILS))
1090 fprintf (vect_dump, "Symbolic number of iterations is ");
1091 print_generic_expr (vect_dump, number_of_iterations, TDF_DETAILS);
1094 else if (TREE_INT_CST_LOW (number_of_iterations) == 0)
1096 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1097 fprintf (vect_dump, "not vectorized: number of iterations = 0.");
1098 if (inner_loop_vinfo)
1099 destroy_loop_vec_info (inner_loop_vinfo, false);
1103 loop_vinfo = new_loop_vec_info (loop);
1104 LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
1105 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo) = number_of_iterations;
1107 STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond)) = loop_exit_ctrl_vec_info_type;
1109 /* CHECKME: May want to keep it around it in the future. */
1110 if (inner_loop_vinfo)
1111 destroy_loop_vec_info (inner_loop_vinfo, false);
1113 gcc_assert (!loop->aux);
1114 loop->aux = loop_vinfo;
1119 /* Function vect_analyze_loop_operations.
1121 Scan the loop stmts and make sure they are all vectorizable. */
1124 vect_analyze_loop_operations (loop_vec_info loop_vinfo)
1126 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1127 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1128 int nbbs = loop->num_nodes;
1129 gimple_stmt_iterator si;
1130 unsigned int vectorization_factor = 0;
1133 stmt_vec_info stmt_info;
1134 bool need_to_vectorize = false;
1135 int min_profitable_iters;
1136 int min_scalar_loop_bound;
1138 bool only_slp_in_loop = true, ok;
1140 if (vect_print_dump_info (REPORT_DETAILS))
1141 fprintf (vect_dump, "=== vect_analyze_loop_operations ===");
1143 gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo));
1144 vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1146 for (i = 0; i < nbbs; i++)
1148 basic_block bb = bbs[i];
1150 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
1152 phi = gsi_stmt (si);
1155 stmt_info = vinfo_for_stmt (phi);
1156 if (vect_print_dump_info (REPORT_DETAILS))
1158 fprintf (vect_dump, "examining phi: ");
1159 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
1162 if (! is_loop_header_bb_p (bb))
1164 /* inner-loop loop-closed exit phi in outer-loop vectorization
1165 (i.e. a phi in the tail of the outer-loop).
1166 FORNOW: we currently don't support the case that these phis
1167 are not used in the outerloop (unless it is double reduction,
1168 i.e., this phi is vect_reduction_def), cause this case
1169 requires to actually do something here. */
1170 if ((!STMT_VINFO_RELEVANT_P (stmt_info)
1171 || STMT_VINFO_LIVE_P (stmt_info))
1172 && STMT_VINFO_DEF_TYPE (stmt_info)
1173 != vect_double_reduction_def)
1175 if (vect_print_dump_info (REPORT_DETAILS))
1177 "Unsupported loop-closed phi in outer-loop.");
1183 gcc_assert (stmt_info);
1185 if (STMT_VINFO_LIVE_P (stmt_info))
1187 /* FORNOW: not yet supported. */
1188 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1189 fprintf (vect_dump, "not vectorized: value used after loop.");
1193 if (STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_scope
1194 && STMT_VINFO_DEF_TYPE (stmt_info) != vect_induction_def)
1196 /* A scalar-dependence cycle that we don't support. */
1197 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1198 fprintf (vect_dump, "not vectorized: scalar dependence cycle.");
1202 if (STMT_VINFO_RELEVANT_P (stmt_info))
1204 need_to_vectorize = true;
1205 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def)
1206 ok = vectorizable_induction (phi, NULL, NULL);
1211 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1214 "not vectorized: relevant phi not supported: ");
1215 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
1221 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1223 gimple stmt = gsi_stmt (si);
1224 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1226 gcc_assert (stmt_info);
1228 if (!vect_analyze_stmt (stmt, &need_to_vectorize, NULL))
1231 if ((STMT_VINFO_RELEVANT_P (stmt_info)
1232 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info)))
1233 && !PURE_SLP_STMT (stmt_info))
1234 /* STMT needs both SLP and loop-based vectorization. */
1235 only_slp_in_loop = false;
1239 /* All operations in the loop are either irrelevant (deal with loop
1240 control, or dead), or only used outside the loop and can be moved
1241 out of the loop (e.g. invariants, inductions). The loop can be
1242 optimized away by scalar optimizations. We're better off not
1243 touching this loop. */
1244 if (!need_to_vectorize)
1246 if (vect_print_dump_info (REPORT_DETAILS))
1248 "All the computation can be taken out of the loop.");
1249 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1251 "not vectorized: redundant loop. no profit to vectorize.");
1255 /* If all the stmts in the loop can be SLPed, we perform only SLP, and
1256 vectorization factor of the loop is the unrolling factor required by the
1257 SLP instances. If that unrolling factor is 1, we say, that we perform
1258 pure SLP on loop - cross iteration parallelism is not exploited. */
1259 if (only_slp_in_loop)
1260 vectorization_factor = LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo);
1262 vectorization_factor = least_common_multiple (vectorization_factor,
1263 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo));
1265 LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
1267 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1268 && vect_print_dump_info (REPORT_DETAILS))
1270 "vectorization_factor = %d, niters = " HOST_WIDE_INT_PRINT_DEC,
1271 vectorization_factor, LOOP_VINFO_INT_NITERS (loop_vinfo));
1273 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1274 && (LOOP_VINFO_INT_NITERS (loop_vinfo) < vectorization_factor))
1276 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1277 fprintf (vect_dump, "not vectorized: iteration count too small.");
1278 if (vect_print_dump_info (REPORT_DETAILS))
1279 fprintf (vect_dump,"not vectorized: iteration count smaller than "
1280 "vectorization factor.");
1284 /* Analyze cost. Decide if worth while to vectorize. */
1286 /* Once VF is set, SLP costs should be updated since the number of created
1287 vector stmts depends on VF. */
1288 vect_update_slp_costs_according_to_vf (loop_vinfo);
1290 min_profitable_iters = vect_estimate_min_profitable_iters (loop_vinfo);
1291 LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo) = min_profitable_iters;
1293 if (min_profitable_iters < 0)
1295 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1296 fprintf (vect_dump, "not vectorized: vectorization not profitable.");
1297 if (vect_print_dump_info (REPORT_DETAILS))
1298 fprintf (vect_dump, "not vectorized: vector version will never be "
1303 min_scalar_loop_bound = ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND)
1304 * vectorization_factor) - 1);
1306 /* Use the cost model only if it is more conservative than user specified
1309 th = (unsigned) min_scalar_loop_bound;
1310 if (min_profitable_iters
1311 && (!min_scalar_loop_bound
1312 || min_profitable_iters > min_scalar_loop_bound))
1313 th = (unsigned) min_profitable_iters;
1315 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1316 && LOOP_VINFO_INT_NITERS (loop_vinfo) <= th)
1318 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1319 fprintf (vect_dump, "not vectorized: vectorization not "
1321 if (vect_print_dump_info (REPORT_DETAILS))
1322 fprintf (vect_dump, "not vectorized: iteration count smaller than "
1323 "user specified loop bound parameter or minimum "
1324 "profitable iterations (whichever is more conservative).");
1328 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1329 || LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0
1330 || LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo))
1332 if (vect_print_dump_info (REPORT_DETAILS))
1333 fprintf (vect_dump, "epilog loop required.");
1334 if (!vect_can_advance_ivs_p (loop_vinfo))
1336 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1338 "not vectorized: can't create epilog loop 1.");
1341 if (!slpeel_can_duplicate_loop_p (loop, single_exit (loop)))
1343 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1345 "not vectorized: can't create epilog loop 2.");
1354 /* Function vect_analyze_loop.
1356 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1357 for it. The different analyses will record information in the
1358 loop_vec_info struct. */
1360 vect_analyze_loop (struct loop *loop)
1363 loop_vec_info loop_vinfo;
1364 int max_vf = MAX_VECTORIZATION_FACTOR;
1367 if (vect_print_dump_info (REPORT_DETAILS))
1368 fprintf (vect_dump, "===== analyze_loop_nest =====");
1370 if (loop_outer (loop)
1371 && loop_vec_info_for_loop (loop_outer (loop))
1372 && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop))))
1374 if (vect_print_dump_info (REPORT_DETAILS))
1375 fprintf (vect_dump, "outer-loop already vectorized.");
1379 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
1381 loop_vinfo = vect_analyze_loop_form (loop);
1384 if (vect_print_dump_info (REPORT_DETAILS))
1385 fprintf (vect_dump, "bad loop form.");
1389 /* Find all data references in the loop (which correspond to vdefs/vuses)
1390 and analyze their evolution in the loop. Also adjust the minimal
1391 vectorization factor according to the loads and stores.
1393 FORNOW: Handle only simple, array references, which
1394 alignment can be forced, and aligned pointer-references. */
1396 ok = vect_analyze_data_refs (loop_vinfo, NULL, &min_vf);
1399 if (vect_print_dump_info (REPORT_DETAILS))
1400 fprintf (vect_dump, "bad data references.");
1401 destroy_loop_vec_info (loop_vinfo, true);
1405 /* Classify all cross-iteration scalar data-flow cycles.
1406 Cross-iteration cycles caused by virtual phis are analyzed separately. */
1408 vect_analyze_scalar_cycles (loop_vinfo);
1410 vect_pattern_recog (loop_vinfo);
1412 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
1414 ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
1417 if (vect_print_dump_info (REPORT_DETAILS))
1418 fprintf (vect_dump, "unexpected pattern.");
1419 destroy_loop_vec_info (loop_vinfo, true);
1423 /* Analyze data dependences between the data-refs in the loop
1424 and adjust the maximum vectorization factor according to
1426 FORNOW: fail at the first data dependence that we encounter. */
1428 ok = vect_analyze_data_ref_dependences (loop_vinfo, NULL, &max_vf);
1432 if (vect_print_dump_info (REPORT_DETAILS))
1433 fprintf (vect_dump, "bad data dependence.");
1434 destroy_loop_vec_info (loop_vinfo, true);
1438 ok = vect_determine_vectorization_factor (loop_vinfo);
1441 if (vect_print_dump_info (REPORT_DETAILS))
1442 fprintf (vect_dump, "can't determine vectorization factor.");
1443 destroy_loop_vec_info (loop_vinfo, true);
1446 if (max_vf < LOOP_VINFO_VECT_FACTOR (loop_vinfo))
1448 if (vect_print_dump_info (REPORT_DETAILS))
1449 fprintf (vect_dump, "bad data dependence.");
1450 destroy_loop_vec_info (loop_vinfo, true);
1454 /* Analyze the alignment of the data-refs in the loop.
1455 Fail if a data reference is found that cannot be vectorized. */
1457 ok = vect_analyze_data_refs_alignment (loop_vinfo, NULL);
1460 if (vect_print_dump_info (REPORT_DETAILS))
1461 fprintf (vect_dump, "bad data alignment.");
1462 destroy_loop_vec_info (loop_vinfo, true);
1466 /* Analyze the access patterns of the data-refs in the loop (consecutive,
1467 complex, etc.). FORNOW: Only handle consecutive access pattern. */
1469 ok = vect_analyze_data_ref_accesses (loop_vinfo, NULL);
1472 if (vect_print_dump_info (REPORT_DETAILS))
1473 fprintf (vect_dump, "bad data access.");
1474 destroy_loop_vec_info (loop_vinfo, true);
1478 /* Prune the list of ddrs to be tested at run-time by versioning for alias.
1479 It is important to call pruning after vect_analyze_data_ref_accesses,
1480 since we use grouping information gathered by interleaving analysis. */
1481 ok = vect_prune_runtime_alias_test_list (loop_vinfo);
1484 if (vect_print_dump_info (REPORT_DETAILS))
1485 fprintf (vect_dump, "too long list of versioning for alias "
1487 destroy_loop_vec_info (loop_vinfo, true);
1491 /* Check the SLP opportunities in the loop, analyze and build SLP trees. */
1492 ok = vect_analyze_slp (loop_vinfo, NULL);
1495 /* Decide which possible SLP instances to SLP. */
1496 vect_make_slp_decision (loop_vinfo);
1498 /* Find stmts that need to be both vectorized and SLPed. */
1499 vect_detect_hybrid_slp (loop_vinfo);
1502 /* This pass will decide on using loop versioning and/or loop peeling in
1503 order to enhance the alignment of data references in the loop. */
1505 ok = vect_enhance_data_refs_alignment (loop_vinfo);
1508 if (vect_print_dump_info (REPORT_DETAILS))
1509 fprintf (vect_dump, "bad data alignment.");
1510 destroy_loop_vec_info (loop_vinfo, true);
1514 /* Scan all the operations in the loop and make sure they are
1517 ok = vect_analyze_loop_operations (loop_vinfo);
1520 if (vect_print_dump_info (REPORT_DETAILS))
1521 fprintf (vect_dump, "bad operation or unsupported loop bound.");
1522 destroy_loop_vec_info (loop_vinfo, true);
1526 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1;
1532 /* Function reduction_code_for_scalar_code
1535 CODE - tree_code of a reduction operations.
1538 REDUC_CODE - the corresponding tree-code to be used to reduce the
1539 vector of partial results into a single scalar result (which
1540 will also reside in a vector) or ERROR_MARK if the operation is
1541 a supported reduction operation, but does not have such tree-code.
1543 Return FALSE if CODE currently cannot be vectorized as reduction. */
1546 reduction_code_for_scalar_code (enum tree_code code,
1547 enum tree_code *reduc_code)
1552 *reduc_code = REDUC_MAX_EXPR;
1556 *reduc_code = REDUC_MIN_EXPR;
1560 *reduc_code = REDUC_PLUS_EXPR;
1568 *reduc_code = ERROR_MARK;
1577 /* Error reporting helper for vect_is_simple_reduction below. GIMPLE statement
1578 STMT is printed with a message MSG. */
1581 report_vect_op (gimple stmt, const char *msg)
1583 fprintf (vect_dump, "%s", msg);
1584 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
1588 /* Function vect_is_simple_reduction_1
1590 (1) Detect a cross-iteration def-use cycle that represents a simple
1591 reduction computation. We look for the following pattern:
1596 a2 = operation (a3, a1)
1599 1. operation is commutative and associative and it is safe to
1600 change the order of the computation (if CHECK_REDUCTION is true)
1601 2. no uses for a2 in the loop (a2 is used out of the loop)
1602 3. no uses of a1 in the loop besides the reduction operation.
1604 Condition 1 is tested here.
1605 Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
1607 (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
1608 nested cycles, if CHECK_REDUCTION is false.
1610 (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
1614 inner loop (def of a3)
1617 If MODIFY is true it tries also to rework the code in-place to enable
1618 detection of more reduction patterns. For the time being we rewrite
1619 "res -= RHS" into "rhs += -RHS" when it seems worthwhile.
1623 vect_is_simple_reduction_1 (loop_vec_info loop_info, gimple phi,
1624 bool check_reduction, bool *double_reduc,
1627 struct loop *loop = (gimple_bb (phi))->loop_father;
1628 struct loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
1629 edge latch_e = loop_latch_edge (loop);
1630 tree loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
1631 gimple def_stmt, def1 = NULL, def2 = NULL;
1632 enum tree_code orig_code, code;
1633 tree op1, op2, op3 = NULL_TREE, op4 = NULL_TREE;
1637 imm_use_iterator imm_iter;
1638 use_operand_p use_p;
1641 *double_reduc = false;
1643 /* If CHECK_REDUCTION is true, we assume inner-most loop vectorization,
1644 otherwise, we assume outer loop vectorization. */
1645 gcc_assert ((check_reduction && loop == vect_loop)
1646 || (!check_reduction && flow_loop_nested_p (vect_loop, loop)));
1648 name = PHI_RESULT (phi);
1650 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
1652 gimple use_stmt = USE_STMT (use_p);
1653 if (is_gimple_debug (use_stmt))
1655 if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt))
1656 && vinfo_for_stmt (use_stmt)
1657 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt)))
1661 if (vect_print_dump_info (REPORT_DETAILS))
1662 fprintf (vect_dump, "reduction used in loop.");
1667 if (TREE_CODE (loop_arg) != SSA_NAME)
1669 if (vect_print_dump_info (REPORT_DETAILS))
1671 fprintf (vect_dump, "reduction: not ssa_name: ");
1672 print_generic_expr (vect_dump, loop_arg, TDF_SLIM);
1677 def_stmt = SSA_NAME_DEF_STMT (loop_arg);
1680 if (vect_print_dump_info (REPORT_DETAILS))
1681 fprintf (vect_dump, "reduction: no def_stmt.");
1685 if (!is_gimple_assign (def_stmt) && gimple_code (def_stmt) != GIMPLE_PHI)
1687 if (vect_print_dump_info (REPORT_DETAILS))
1688 print_gimple_stmt (vect_dump, def_stmt, 0, TDF_SLIM);
1692 if (is_gimple_assign (def_stmt))
1694 name = gimple_assign_lhs (def_stmt);
1699 name = PHI_RESULT (def_stmt);
1704 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
1706 gimple use_stmt = USE_STMT (use_p);
1707 if (is_gimple_debug (use_stmt))
1709 if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt))
1710 && vinfo_for_stmt (use_stmt)
1711 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt)))
1715 if (vect_print_dump_info (REPORT_DETAILS))
1716 fprintf (vect_dump, "reduction used in loop.");
1721 /* If DEF_STMT is a phi node itself, we expect it to have a single argument
1722 defined in the inner loop. */
1725 op1 = PHI_ARG_DEF (def_stmt, 0);
1727 if (gimple_phi_num_args (def_stmt) != 1
1728 || TREE_CODE (op1) != SSA_NAME)
1730 if (vect_print_dump_info (REPORT_DETAILS))
1731 fprintf (vect_dump, "unsupported phi node definition.");
1736 def1 = SSA_NAME_DEF_STMT (op1);
1737 if (flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
1739 && flow_bb_inside_loop_p (loop->inner, gimple_bb (def1))
1740 && is_gimple_assign (def1))
1742 if (vect_print_dump_info (REPORT_DETAILS))
1743 report_vect_op (def_stmt, "detected double reduction: ");
1745 *double_reduc = true;
1752 code = orig_code = gimple_assign_rhs_code (def_stmt);
1754 /* We can handle "res -= x[i]", which is non-associative by
1755 simply rewriting this into "res += -x[i]". Avoid changing
1756 gimple instruction for the first simple tests and only do this
1757 if we're allowed to change code at all. */
1758 if (code == MINUS_EXPR && modify)
1762 && (!commutative_tree_code (code) || !associative_tree_code (code)))
1764 if (vect_print_dump_info (REPORT_DETAILS))
1765 report_vect_op (def_stmt, "reduction: not commutative/associative: ");
1769 if (get_gimple_rhs_class (code) != GIMPLE_BINARY_RHS)
1771 if (code != COND_EXPR)
1773 if (vect_print_dump_info (REPORT_DETAILS))
1774 report_vect_op (def_stmt, "reduction: not binary operation: ");
1779 op3 = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 0);
1780 if (COMPARISON_CLASS_P (op3))
1782 op4 = TREE_OPERAND (op3, 1);
1783 op3 = TREE_OPERAND (op3, 0);
1786 op1 = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 1);
1787 op2 = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 2);
1789 if (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op2) != SSA_NAME)
1791 if (vect_print_dump_info (REPORT_DETAILS))
1792 report_vect_op (def_stmt, "reduction: uses not ssa_names: ");
1799 op1 = gimple_assign_rhs1 (def_stmt);
1800 op2 = gimple_assign_rhs2 (def_stmt);
1802 if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
1804 if (vect_print_dump_info (REPORT_DETAILS))
1805 report_vect_op (def_stmt, "reduction: uses not ssa_names: ");
1811 type = TREE_TYPE (gimple_assign_lhs (def_stmt));
1812 if ((TREE_CODE (op1) == SSA_NAME
1813 && !types_compatible_p (type,TREE_TYPE (op1)))
1814 || (TREE_CODE (op2) == SSA_NAME
1815 && !types_compatible_p (type, TREE_TYPE (op2)))
1816 || (op3 && TREE_CODE (op3) == SSA_NAME
1817 && !types_compatible_p (type, TREE_TYPE (op3)))
1818 || (op4 && TREE_CODE (op4) == SSA_NAME
1819 && !types_compatible_p (type, TREE_TYPE (op4))))
1821 if (vect_print_dump_info (REPORT_DETAILS))
1823 fprintf (vect_dump, "reduction: multiple types: operation type: ");
1824 print_generic_expr (vect_dump, type, TDF_SLIM);
1825 fprintf (vect_dump, ", operands types: ");
1826 print_generic_expr (vect_dump, TREE_TYPE (op1), TDF_SLIM);
1827 fprintf (vect_dump, ",");
1828 print_generic_expr (vect_dump, TREE_TYPE (op2), TDF_SLIM);
1831 fprintf (vect_dump, ",");
1832 print_generic_expr (vect_dump, TREE_TYPE (op3), TDF_SLIM);
1837 fprintf (vect_dump, ",");
1838 print_generic_expr (vect_dump, TREE_TYPE (op4), TDF_SLIM);
1845 /* Check that it's ok to change the order of the computation.
1846 Generally, when vectorizing a reduction we change the order of the
1847 computation. This may change the behavior of the program in some
1848 cases, so we need to check that this is ok. One exception is when
1849 vectorizing an outer-loop: the inner-loop is executed sequentially,
1850 and therefore vectorizing reductions in the inner-loop during
1851 outer-loop vectorization is safe. */
1853 /* CHECKME: check for !flag_finite_math_only too? */
1854 if (SCALAR_FLOAT_TYPE_P (type) && !flag_associative_math
1857 /* Changing the order of operations changes the semantics. */
1858 if (vect_print_dump_info (REPORT_DETAILS))
1859 report_vect_op (def_stmt, "reduction: unsafe fp math optimization: ");
1862 else if (INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_TRAPS (type)
1865 /* Changing the order of operations changes the semantics. */
1866 if (vect_print_dump_info (REPORT_DETAILS))
1867 report_vect_op (def_stmt, "reduction: unsafe int math optimization: ");
1870 else if (SAT_FIXED_POINT_TYPE_P (type) && check_reduction)
1872 /* Changing the order of operations changes the semantics. */
1873 if (vect_print_dump_info (REPORT_DETAILS))
1874 report_vect_op (def_stmt,
1875 "reduction: unsafe fixed-point math optimization: ");
1879 /* If we detected "res -= x[i]" earlier, rewrite it into
1880 "res += -x[i]" now. If this turns out to be useless reassoc
1881 will clean it up again. */
1882 if (orig_code == MINUS_EXPR)
1884 tree rhs = gimple_assign_rhs2 (def_stmt);
1885 tree negrhs = make_ssa_name (SSA_NAME_VAR (rhs), NULL);
1886 gimple negate_stmt = gimple_build_assign_with_ops (NEGATE_EXPR, negrhs,
1888 gimple_stmt_iterator gsi = gsi_for_stmt (def_stmt);
1889 set_vinfo_for_stmt (negate_stmt, new_stmt_vec_info (negate_stmt,
1891 gsi_insert_before (&gsi, negate_stmt, GSI_NEW_STMT);
1892 gimple_assign_set_rhs2 (def_stmt, negrhs);
1893 gimple_assign_set_rhs_code (def_stmt, PLUS_EXPR);
1894 update_stmt (def_stmt);
1897 /* Reduction is safe. We're dealing with one of the following:
1898 1) integer arithmetic and no trapv
1899 2) floating point arithmetic, and special flags permit this optimization
1900 3) nested cycle (i.e., outer loop vectorization). */
1901 if (TREE_CODE (op1) == SSA_NAME)
1902 def1 = SSA_NAME_DEF_STMT (op1);
1904 if (TREE_CODE (op2) == SSA_NAME)
1905 def2 = SSA_NAME_DEF_STMT (op2);
1907 if (code != COND_EXPR
1908 && (!def1 || !def2 || gimple_nop_p (def1) || gimple_nop_p (def2)))
1910 if (vect_print_dump_info (REPORT_DETAILS))
1911 report_vect_op (def_stmt, "reduction: no defs for operands: ");
1915 /* Check that one def is the reduction def, defined by PHI,
1916 the other def is either defined in the loop ("vect_internal_def"),
1917 or it's an induction (defined by a loop-header phi-node). */
1919 if (def2 && def2 == phi
1920 && (code == COND_EXPR
1921 || (def1 && flow_bb_inside_loop_p (loop, gimple_bb (def1))
1922 && (is_gimple_assign (def1)
1923 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1))
1924 == vect_induction_def
1925 || (gimple_code (def1) == GIMPLE_PHI
1926 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1))
1927 == vect_internal_def
1928 && !is_loop_header_bb_p (gimple_bb (def1)))))))
1930 if (vect_print_dump_info (REPORT_DETAILS))
1931 report_vect_op (def_stmt, "detected reduction: ");
1934 else if (def1 && def1 == phi
1935 && (code == COND_EXPR
1936 || (def2 && flow_bb_inside_loop_p (loop, gimple_bb (def2))
1937 && (is_gimple_assign (def2)
1938 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2))
1939 == vect_induction_def
1940 || (gimple_code (def2) == GIMPLE_PHI
1941 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2))
1942 == vect_internal_def
1943 && !is_loop_header_bb_p (gimple_bb (def2)))))))
1945 if (check_reduction)
1947 /* Swap operands (just for simplicity - so that the rest of the code
1948 can assume that the reduction variable is always the last (second)
1950 if (vect_print_dump_info (REPORT_DETAILS))
1951 report_vect_op (def_stmt,
1952 "detected reduction: need to swap operands: ");
1954 swap_tree_operands (def_stmt, gimple_assign_rhs1_ptr (def_stmt),
1955 gimple_assign_rhs2_ptr (def_stmt));
1959 if (vect_print_dump_info (REPORT_DETAILS))
1960 report_vect_op (def_stmt, "detected reduction: ");
1967 if (vect_print_dump_info (REPORT_DETAILS))
1968 report_vect_op (def_stmt, "reduction: unknown pattern: ");
1974 /* Wrapper around vect_is_simple_reduction_1, that won't modify code
1975 in-place. Arguments as there. */
1978 vect_is_simple_reduction (loop_vec_info loop_info, gimple phi,
1979 bool check_reduction, bool *double_reduc)
1981 return vect_is_simple_reduction_1 (loop_info, phi, check_reduction,
1982 double_reduc, false);
1985 /* Wrapper around vect_is_simple_reduction_1, which will modify code
1986 in-place if it enables detection of more reductions. Arguments
1990 vect_force_simple_reduction (loop_vec_info loop_info, gimple phi,
1991 bool check_reduction, bool *double_reduc)
1993 return vect_is_simple_reduction_1 (loop_info, phi, check_reduction,
1994 double_reduc, true);
1997 /* Function vect_estimate_min_profitable_iters
1999 Return the number of iterations required for the vector version of the
2000 loop to be profitable relative to the cost of the scalar version of the
2003 TODO: Take profile info into account before making vectorization
2004 decisions, if available. */
2007 vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo)
2010 int min_profitable_iters;
2011 int peel_iters_prologue;
2012 int peel_iters_epilogue;
2013 int vec_inside_cost = 0;
2014 int vec_outside_cost = 0;
2015 int scalar_single_iter_cost = 0;
2016 int scalar_outside_cost = 0;
2017 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2018 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2019 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
2020 int nbbs = loop->num_nodes;
2021 int byte_misalign = LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo);
2022 int peel_guard_costs = 0;
2023 int innerloop_iters = 0, factor;
2024 VEC (slp_instance, heap) *slp_instances;
2025 slp_instance instance;
2027 /* Cost model disabled. */
2028 if (!flag_vect_cost_model)
2030 if (vect_print_dump_info (REPORT_COST))
2031 fprintf (vect_dump, "cost model disabled.");
2035 /* Requires loop versioning tests to handle misalignment. */
2036 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo))
2038 /* FIXME: Make cost depend on complexity of individual check. */
2040 VEC_length (gimple, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
2041 if (vect_print_dump_info (REPORT_COST))
2042 fprintf (vect_dump, "cost model: Adding cost of checks for loop "
2043 "versioning to treat misalignment.\n");
2046 /* Requires loop versioning with alias checks. */
2047 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2049 /* FIXME: Make cost depend on complexity of individual check. */
2051 VEC_length (ddr_p, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo));
2052 if (vect_print_dump_info (REPORT_COST))
2053 fprintf (vect_dump, "cost model: Adding cost of checks for loop "
2054 "versioning aliasing.\n");
2057 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
2058 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2059 vec_outside_cost += TARG_COND_TAKEN_BRANCH_COST;
2061 /* Count statements in scalar loop. Using this as scalar cost for a single
2064 TODO: Add outer loop support.
2066 TODO: Consider assigning different costs to different scalar
2071 innerloop_iters = 50; /* FIXME */
2073 for (i = 0; i < nbbs; i++)
2075 gimple_stmt_iterator si;
2076 basic_block bb = bbs[i];
2078 if (bb->loop_father == loop->inner)
2079 factor = innerloop_iters;
2083 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
2085 gimple stmt = gsi_stmt (si);
2086 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2087 /* Skip stmts that are not vectorized inside the loop. */
2088 if (!STMT_VINFO_RELEVANT_P (stmt_info)
2089 && (!STMT_VINFO_LIVE_P (stmt_info)
2090 || STMT_VINFO_DEF_TYPE (stmt_info) != vect_reduction_def))
2092 scalar_single_iter_cost += cost_for_stmt (stmt) * factor;
2093 vec_inside_cost += STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info) * factor;
2094 /* FIXME: for stmts in the inner-loop in outer-loop vectorization,
2095 some of the "outside" costs are generated inside the outer-loop. */
2096 vec_outside_cost += STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info);
2100 /* Add additional cost for the peeled instructions in prologue and epilogue
2103 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
2104 at compile-time - we assume it's vf/2 (the worst would be vf-1).
2106 TODO: Build an expression that represents peel_iters for prologue and
2107 epilogue to be used in a run-time test. */
2109 if (byte_misalign < 0)
2111 peel_iters_prologue = vf/2;
2112 if (vect_print_dump_info (REPORT_COST))
2113 fprintf (vect_dump, "cost model: "
2114 "prologue peel iters set to vf/2.");
2116 /* If peeling for alignment is unknown, loop bound of main loop becomes
2118 peel_iters_epilogue = vf/2;
2119 if (vect_print_dump_info (REPORT_COST))
2120 fprintf (vect_dump, "cost model: "
2121 "epilogue peel iters set to vf/2 because "
2122 "peeling for alignment is unknown .");
2124 /* If peeled iterations are unknown, count a taken branch and a not taken
2125 branch per peeled loop. Even if scalar loop iterations are known,
2126 vector iterations are not known since peeled prologue iterations are
2127 not known. Hence guards remain the same. */
2128 peel_guard_costs += 2 * (TARG_COND_TAKEN_BRANCH_COST
2129 + TARG_COND_NOT_TAKEN_BRANCH_COST);
2135 struct data_reference *dr = LOOP_VINFO_UNALIGNED_DR (loop_vinfo);
2136 int element_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr))));
2137 tree vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr)));
2138 int nelements = TYPE_VECTOR_SUBPARTS (vectype);
2140 peel_iters_prologue = nelements - (byte_misalign / element_size);
2143 peel_iters_prologue = 0;
2145 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
2147 peel_iters_epilogue = vf/2;
2148 if (vect_print_dump_info (REPORT_COST))
2149 fprintf (vect_dump, "cost model: "
2150 "epilogue peel iters set to vf/2 because "
2151 "loop iterations are unknown .");
2153 /* If peeled iterations are known but number of scalar loop
2154 iterations are unknown, count a taken branch per peeled loop. */
2155 peel_guard_costs += 2 * TARG_COND_TAKEN_BRANCH_COST;
2160 int niters = LOOP_VINFO_INT_NITERS (loop_vinfo);
2161 peel_iters_prologue = niters < peel_iters_prologue ?
2162 niters : peel_iters_prologue;
2163 peel_iters_epilogue = (niters - peel_iters_prologue) % vf;
2167 vec_outside_cost += (peel_iters_prologue * scalar_single_iter_cost)
2168 + (peel_iters_epilogue * scalar_single_iter_cost)
2171 /* FORNOW: The scalar outside cost is incremented in one of the
2174 1. The vectorizer checks for alignment and aliasing and generates
2175 a condition that allows dynamic vectorization. A cost model
2176 check is ANDED with the versioning condition. Hence scalar code
2177 path now has the added cost of the versioning check.
2179 if (cost > th & versioning_check)
2182 Hence run-time scalar is incremented by not-taken branch cost.
2184 2. The vectorizer then checks if a prologue is required. If the
2185 cost model check was not done before during versioning, it has to
2186 be done before the prologue check.
2189 prologue = scalar_iters
2194 if (prologue == num_iters)
2197 Hence the run-time scalar cost is incremented by a taken branch,
2198 plus a not-taken branch, plus a taken branch cost.
2200 3. The vectorizer then checks if an epilogue is required. If the
2201 cost model check was not done before during prologue check, it
2202 has to be done with the epilogue check.
2208 if (prologue == num_iters)
2211 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
2214 Hence the run-time scalar cost should be incremented by 2 taken
2217 TODO: The back end may reorder the BBS's differently and reverse
2218 conditions/branch directions. Change the estimates below to
2219 something more reasonable. */
2221 /* If the number of iterations is known and we do not do versioning, we can
2222 decide whether to vectorize at compile time. Hence the scalar version
2223 do not carry cost model guard costs. */
2224 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
2225 || LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
2226 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2228 /* Cost model check occurs at versioning. */
2229 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
2230 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2231 scalar_outside_cost += TARG_COND_NOT_TAKEN_BRANCH_COST;
2234 /* Cost model check occurs at prologue generation. */
2235 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0)
2236 scalar_outside_cost += 2 * TARG_COND_TAKEN_BRANCH_COST
2237 + TARG_COND_NOT_TAKEN_BRANCH_COST;
2238 /* Cost model check occurs at epilogue generation. */
2240 scalar_outside_cost += 2 * TARG_COND_TAKEN_BRANCH_COST;
2244 /* Add SLP costs. */
2245 slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
2246 for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
2248 vec_outside_cost += SLP_INSTANCE_OUTSIDE_OF_LOOP_COST (instance);
2249 vec_inside_cost += SLP_INSTANCE_INSIDE_OF_LOOP_COST (instance);
2252 /* Calculate number of iterations required to make the vector version
2253 profitable, relative to the loop bodies only. The following condition
2255 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
2257 SIC = scalar iteration cost, VIC = vector iteration cost,
2258 VOC = vector outside cost, VF = vectorization factor,
2259 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
2260 SOC = scalar outside cost for run time cost model check. */
2262 if ((scalar_single_iter_cost * vf) > vec_inside_cost)
2264 if (vec_outside_cost <= 0)
2265 min_profitable_iters = 1;
2268 min_profitable_iters = ((vec_outside_cost - scalar_outside_cost) * vf
2269 - vec_inside_cost * peel_iters_prologue
2270 - vec_inside_cost * peel_iters_epilogue)
2271 / ((scalar_single_iter_cost * vf)
2274 if ((scalar_single_iter_cost * vf * min_profitable_iters)
2275 <= ((vec_inside_cost * min_profitable_iters)
2276 + ((vec_outside_cost - scalar_outside_cost) * vf)))
2277 min_profitable_iters++;
2280 /* vector version will never be profitable. */
2283 if (vect_print_dump_info (REPORT_COST))
2284 fprintf (vect_dump, "cost model: the vector iteration cost = %d "
2285 "divided by the scalar iteration cost = %d "
2286 "is greater or equal to the vectorization factor = %d.",
2287 vec_inside_cost, scalar_single_iter_cost, vf);
2291 if (vect_print_dump_info (REPORT_COST))
2293 fprintf (vect_dump, "Cost model analysis: \n");
2294 fprintf (vect_dump, " Vector inside of loop cost: %d\n",
2296 fprintf (vect_dump, " Vector outside of loop cost: %d\n",
2298 fprintf (vect_dump, " Scalar iteration cost: %d\n",
2299 scalar_single_iter_cost);
2300 fprintf (vect_dump, " Scalar outside cost: %d\n", scalar_outside_cost);
2301 fprintf (vect_dump, " prologue iterations: %d\n",
2302 peel_iters_prologue);
2303 fprintf (vect_dump, " epilogue iterations: %d\n",
2304 peel_iters_epilogue);
2305 fprintf (vect_dump, " Calculated minimum iters for profitability: %d\n",
2306 min_profitable_iters);
2309 min_profitable_iters =
2310 min_profitable_iters < vf ? vf : min_profitable_iters;
2312 /* Because the condition we create is:
2313 if (niters <= min_profitable_iters)
2314 then skip the vectorized loop. */
2315 min_profitable_iters--;
2317 if (vect_print_dump_info (REPORT_COST))
2318 fprintf (vect_dump, " Profitability threshold = %d\n",
2319 min_profitable_iters);
2321 return min_profitable_iters;
2325 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
2326 functions. Design better to avoid maintenance issues. */
2328 /* Function vect_model_reduction_cost.
2330 Models cost for a reduction operation, including the vector ops
2331 generated within the strip-mine loop, the initial definition before
2332 the loop, and the epilogue code that must be generated. */
2335 vect_model_reduction_cost (stmt_vec_info stmt_info, enum tree_code reduc_code,
2339 enum tree_code code;
2342 gimple stmt, orig_stmt;
2344 enum machine_mode mode;
2345 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2346 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2349 /* Cost of reduction op inside loop. */
2350 STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info) += ncopies * TARG_VEC_STMT_COST;
2352 stmt = STMT_VINFO_STMT (stmt_info);
2354 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2356 case GIMPLE_SINGLE_RHS:
2357 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt)) == ternary_op);
2358 reduction_op = TREE_OPERAND (gimple_assign_rhs1 (stmt), 2);
2360 case GIMPLE_UNARY_RHS:
2361 reduction_op = gimple_assign_rhs1 (stmt);
2363 case GIMPLE_BINARY_RHS:
2364 reduction_op = gimple_assign_rhs2 (stmt);
2370 vectype = get_vectype_for_scalar_type (TREE_TYPE (reduction_op));
2373 if (vect_print_dump_info (REPORT_COST))
2375 fprintf (vect_dump, "unsupported data-type ");
2376 print_generic_expr (vect_dump, TREE_TYPE (reduction_op), TDF_SLIM);
2381 mode = TYPE_MODE (vectype);
2382 orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
2385 orig_stmt = STMT_VINFO_STMT (stmt_info);
2387 code = gimple_assign_rhs_code (orig_stmt);
2389 /* Add in cost for initial definition. */
2390 outer_cost += TARG_SCALAR_TO_VEC_COST;
2392 /* Determine cost of epilogue code.
2394 We have a reduction operator that will reduce the vector in one statement.
2395 Also requires scalar extract. */
2397 if (!nested_in_vect_loop_p (loop, orig_stmt))
2399 if (reduc_code != ERROR_MARK)
2400 outer_cost += TARG_VEC_STMT_COST + TARG_VEC_TO_SCALAR_COST;
2403 int vec_size_in_bits = tree_low_cst (TYPE_SIZE (vectype), 1);
2405 TYPE_SIZE (TREE_TYPE (gimple_assign_lhs (orig_stmt)));
2406 int element_bitsize = tree_low_cst (bitsize, 1);
2407 int nelements = vec_size_in_bits / element_bitsize;
2409 optab = optab_for_tree_code (code, vectype, optab_default);
2411 /* We have a whole vector shift available. */
2412 if (VECTOR_MODE_P (mode)
2413 && optab_handler (optab, mode)->insn_code != CODE_FOR_nothing
2414 && optab_handler (vec_shr_optab, mode)->insn_code != CODE_FOR_nothing)
2415 /* Final reduction via vector shifts and the reduction operator. Also
2416 requires scalar extract. */
2417 outer_cost += ((exact_log2(nelements) * 2) * TARG_VEC_STMT_COST
2418 + TARG_VEC_TO_SCALAR_COST);
2420 /* Use extracts and reduction op for final reduction. For N elements,
2421 we have N extracts and N-1 reduction ops. */
2422 outer_cost += ((nelements + nelements - 1) * TARG_VEC_STMT_COST);
2426 STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info) = outer_cost;
2428 if (vect_print_dump_info (REPORT_COST))
2429 fprintf (vect_dump, "vect_model_reduction_cost: inside_cost = %d, "
2430 "outside_cost = %d .", STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info),
2431 STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info));
2437 /* Function vect_model_induction_cost.
2439 Models cost for induction operations. */
2442 vect_model_induction_cost (stmt_vec_info stmt_info, int ncopies)
2444 /* loop cost for vec_loop. */
2445 STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info) = ncopies * TARG_VEC_STMT_COST;
2446 /* prologue cost for vec_init and vec_step. */
2447 STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info) = 2 * TARG_SCALAR_TO_VEC_COST;
2449 if (vect_print_dump_info (REPORT_COST))
2450 fprintf (vect_dump, "vect_model_induction_cost: inside_cost = %d, "
2451 "outside_cost = %d .", STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info),
2452 STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info));
2456 /* Function get_initial_def_for_induction
2459 STMT - a stmt that performs an induction operation in the loop.
2460 IV_PHI - the initial value of the induction variable
2463 Return a vector variable, initialized with the first VF values of
2464 the induction variable. E.g., for an iv with IV_PHI='X' and
2465 evolution S, for a vector of 4 units, we want to return:
2466 [X, X + S, X + 2*S, X + 3*S]. */
2469 get_initial_def_for_induction (gimple iv_phi)
2471 stmt_vec_info stmt_vinfo = vinfo_for_stmt (iv_phi);
2472 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
2473 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2474 tree scalar_type = TREE_TYPE (gimple_phi_result (iv_phi));
2477 edge pe = loop_preheader_edge (loop);
2478 struct loop *iv_loop;
2480 tree vec, vec_init, vec_step, t;
2484 gimple init_stmt, induction_phi, new_stmt;
2485 tree induc_def, vec_def, vec_dest;
2486 tree init_expr, step_expr;
2487 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2492 stmt_vec_info phi_info = vinfo_for_stmt (iv_phi);
2493 bool nested_in_vect_loop = false;
2494 gimple_seq stmts = NULL;
2495 imm_use_iterator imm_iter;
2496 use_operand_p use_p;
2500 gimple_stmt_iterator si;
2501 basic_block bb = gimple_bb (iv_phi);
2504 vectype = get_vectype_for_scalar_type (scalar_type);
2505 gcc_assert (vectype);
2506 nunits = TYPE_VECTOR_SUBPARTS (vectype);
2507 ncopies = vf / nunits;
2509 gcc_assert (phi_info);
2510 gcc_assert (ncopies >= 1);
2512 /* Find the first insertion point in the BB. */
2513 si = gsi_after_labels (bb);
2515 if (INTEGRAL_TYPE_P (scalar_type))
2516 step_expr = build_int_cst (scalar_type, 0);
2517 else if (POINTER_TYPE_P (scalar_type))
2518 step_expr = build_int_cst (sizetype, 0);
2520 step_expr = build_real (scalar_type, dconst0);
2522 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
2523 if (nested_in_vect_loop_p (loop, iv_phi))
2525 nested_in_vect_loop = true;
2526 iv_loop = loop->inner;
2530 gcc_assert (iv_loop == (gimple_bb (iv_phi))->loop_father);
2532 latch_e = loop_latch_edge (iv_loop);
2533 loop_arg = PHI_ARG_DEF_FROM_EDGE (iv_phi, latch_e);
2535 access_fn = analyze_scalar_evolution (iv_loop, PHI_RESULT (iv_phi));
2536 gcc_assert (access_fn);
2537 ok = vect_is_simple_iv_evolution (iv_loop->num, access_fn,
2538 &init_expr, &step_expr);
2540 pe = loop_preheader_edge (iv_loop);
2542 /* Create the vector that holds the initial_value of the induction. */
2543 if (nested_in_vect_loop)
2545 /* iv_loop is nested in the loop to be vectorized. init_expr had already
2546 been created during vectorization of previous stmts; We obtain it from
2547 the STMT_VINFO_VEC_STMT of the defining stmt. */
2548 tree iv_def = PHI_ARG_DEF_FROM_EDGE (iv_phi,
2549 loop_preheader_edge (iv_loop));
2550 vec_init = vect_get_vec_def_for_operand (iv_def, iv_phi, NULL);
2554 /* iv_loop is the loop to be vectorized. Create:
2555 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
2556 new_var = vect_get_new_vect_var (scalar_type, vect_scalar_var, "var_");
2557 add_referenced_var (new_var);
2559 new_name = force_gimple_operand (init_expr, &stmts, false, new_var);
2562 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
2563 gcc_assert (!new_bb);
2567 t = tree_cons (NULL_TREE, init_expr, t);
2568 for (i = 1; i < nunits; i++)
2570 /* Create: new_name_i = new_name + step_expr */
2571 enum tree_code code = POINTER_TYPE_P (scalar_type)
2572 ? POINTER_PLUS_EXPR : PLUS_EXPR;
2573 init_stmt = gimple_build_assign_with_ops (code, new_var,
2574 new_name, step_expr);
2575 new_name = make_ssa_name (new_var, init_stmt);
2576 gimple_assign_set_lhs (init_stmt, new_name);
2578 new_bb = gsi_insert_on_edge_immediate (pe, init_stmt);
2579 gcc_assert (!new_bb);
2581 if (vect_print_dump_info (REPORT_DETAILS))
2583 fprintf (vect_dump, "created new init_stmt: ");
2584 print_gimple_stmt (vect_dump, init_stmt, 0, TDF_SLIM);
2586 t = tree_cons (NULL_TREE, new_name, t);
2588 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
2589 vec = build_constructor_from_list (vectype, nreverse (t));
2590 vec_init = vect_init_vector (iv_phi, vec, vectype, NULL);
2594 /* Create the vector that holds the step of the induction. */
2595 if (nested_in_vect_loop)
2596 /* iv_loop is nested in the loop to be vectorized. Generate:
2597 vec_step = [S, S, S, S] */
2598 new_name = step_expr;
2601 /* iv_loop is the loop to be vectorized. Generate:
2602 vec_step = [VF*S, VF*S, VF*S, VF*S] */
2603 expr = build_int_cst (TREE_TYPE (step_expr), vf);
2604 new_name = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr),
2609 for (i = 0; i < nunits; i++)
2610 t = tree_cons (NULL_TREE, unshare_expr (new_name), t);
2611 gcc_assert (CONSTANT_CLASS_P (new_name));
2612 stepvectype = get_vectype_for_scalar_type (TREE_TYPE (new_name));
2613 gcc_assert (stepvectype);
2614 vec = build_vector (stepvectype, t);
2615 vec_step = vect_init_vector (iv_phi, vec, stepvectype, NULL);
2618 /* Create the following def-use cycle:
2623 vec_iv = PHI <vec_init, vec_loop>
2627 vec_loop = vec_iv + vec_step; */
2629 /* Create the induction-phi that defines the induction-operand. */
2630 vec_dest = vect_get_new_vect_var (vectype, vect_simple_var, "vec_iv_");
2631 add_referenced_var (vec_dest);
2632 induction_phi = create_phi_node (vec_dest, iv_loop->header);
2633 set_vinfo_for_stmt (induction_phi,
2634 new_stmt_vec_info (induction_phi, loop_vinfo, NULL));
2635 induc_def = PHI_RESULT (induction_phi);
2637 /* Create the iv update inside the loop */
2638 new_stmt = gimple_build_assign_with_ops (PLUS_EXPR, vec_dest,
2639 induc_def, vec_step);
2640 vec_def = make_ssa_name (vec_dest, new_stmt);
2641 gimple_assign_set_lhs (new_stmt, vec_def);
2642 gsi_insert_before (&si, new_stmt, GSI_SAME_STMT);
2643 set_vinfo_for_stmt (new_stmt, new_stmt_vec_info (new_stmt, loop_vinfo,
2646 /* Set the arguments of the phi node: */
2647 add_phi_arg (induction_phi, vec_init, pe, UNKNOWN_LOCATION);
2648 add_phi_arg (induction_phi, vec_def, loop_latch_edge (iv_loop),
2652 /* In case that vectorization factor (VF) is bigger than the number
2653 of elements that we can fit in a vectype (nunits), we have to generate
2654 more than one vector stmt - i.e - we need to "unroll" the
2655 vector stmt by a factor VF/nunits. For more details see documentation
2656 in vectorizable_operation. */
2660 stmt_vec_info prev_stmt_vinfo;
2661 /* FORNOW. This restriction should be relaxed. */
2662 gcc_assert (!nested_in_vect_loop);
2664 /* Create the vector that holds the step of the induction. */
2665 expr = build_int_cst (TREE_TYPE (step_expr), nunits);
2666 new_name = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr),
2669 for (i = 0; i < nunits; i++)
2670 t = tree_cons (NULL_TREE, unshare_expr (new_name), t);
2671 gcc_assert (CONSTANT_CLASS_P (new_name));
2672 vec = build_vector (stepvectype, t);
2673 vec_step = vect_init_vector (iv_phi, vec, stepvectype, NULL);
2675 vec_def = induc_def;
2676 prev_stmt_vinfo = vinfo_for_stmt (induction_phi);
2677 for (i = 1; i < ncopies; i++)
2679 /* vec_i = vec_prev + vec_step */
2680 new_stmt = gimple_build_assign_with_ops (PLUS_EXPR, vec_dest,
2682 vec_def = make_ssa_name (vec_dest, new_stmt);
2683 gimple_assign_set_lhs (new_stmt, vec_def);
2685 gsi_insert_before (&si, new_stmt, GSI_SAME_STMT);
2686 set_vinfo_for_stmt (new_stmt,
2687 new_stmt_vec_info (new_stmt, loop_vinfo, NULL));
2688 STMT_VINFO_RELATED_STMT (prev_stmt_vinfo) = new_stmt;
2689 prev_stmt_vinfo = vinfo_for_stmt (new_stmt);
2693 if (nested_in_vect_loop)
2695 /* Find the loop-closed exit-phi of the induction, and record
2696 the final vector of induction results: */
2698 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, loop_arg)
2700 if (!flow_bb_inside_loop_p (iv_loop, gimple_bb (USE_STMT (use_p))))
2702 exit_phi = USE_STMT (use_p);
2708 stmt_vec_info stmt_vinfo = vinfo_for_stmt (exit_phi);
2709 /* FORNOW. Currently not supporting the case that an inner-loop induction
2710 is not used in the outer-loop (i.e. only outside the outer-loop). */
2711 gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo)
2712 && !STMT_VINFO_LIVE_P (stmt_vinfo));
2714 STMT_VINFO_VEC_STMT (stmt_vinfo) = new_stmt;
2715 if (vect_print_dump_info (REPORT_DETAILS))
2717 fprintf (vect_dump, "vector of inductions after inner-loop:");
2718 print_gimple_stmt (vect_dump, new_stmt, 0, TDF_SLIM);
2724 if (vect_print_dump_info (REPORT_DETAILS))
2726 fprintf (vect_dump, "transform induction: created def-use cycle: ");
2727 print_gimple_stmt (vect_dump, induction_phi, 0, TDF_SLIM);
2728 fprintf (vect_dump, "\n");
2729 print_gimple_stmt (vect_dump, SSA_NAME_DEF_STMT (vec_def), 0, TDF_SLIM);
2732 STMT_VINFO_VEC_STMT (phi_info) = induction_phi;
2737 /* Function get_initial_def_for_reduction
2740 STMT - a stmt that performs a reduction operation in the loop.
2741 INIT_VAL - the initial value of the reduction variable
2744 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
2745 of the reduction (used for adjusting the epilog - see below).
2746 Return a vector variable, initialized according to the operation that STMT
2747 performs. This vector will be used as the initial value of the
2748 vector of partial results.
2750 Option1 (adjust in epilog): Initialize the vector as follows:
2751 add/bit or/xor: [0,0,...,0,0]
2752 mult/bit and: [1,1,...,1,1]
2753 min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
2754 and when necessary (e.g. add/mult case) let the caller know
2755 that it needs to adjust the result by init_val.
2757 Option2: Initialize the vector as follows:
2758 add/bit or/xor: [init_val,0,0,...,0]
2759 mult/bit and: [init_val,1,1,...,1]
2760 min/max/cond_expr: [init_val,init_val,...,init_val]
2761 and no adjustments are needed.
2763 For example, for the following code:
2769 STMT is 's = s + a[i]', and the reduction variable is 's'.
2770 For a vector of 4 units, we want to return either [0,0,0,init_val],
2771 or [0,0,0,0] and let the caller know that it needs to adjust
2772 the result at the end by 'init_val'.
2774 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
2775 initialization vector is simpler (same element in all entries), if
2776 ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
2778 A cost model should help decide between these two schemes. */
2781 get_initial_def_for_reduction (gimple stmt, tree init_val,
2782 tree *adjustment_def)
2784 stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
2785 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
2786 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2787 tree scalar_type = TREE_TYPE (init_val);
2788 tree vectype = get_vectype_for_scalar_type (scalar_type);
2790 enum tree_code code = gimple_assign_rhs_code (stmt);
2795 bool nested_in_vect_loop = false;
2797 REAL_VALUE_TYPE real_init_val = dconst0;
2798 int int_init_val = 0;
2799 gimple def_stmt = NULL;
2801 gcc_assert (vectype);
2802 nunits = TYPE_VECTOR_SUBPARTS (vectype);
2804 gcc_assert (POINTER_TYPE_P (scalar_type) || INTEGRAL_TYPE_P (scalar_type)
2805 || SCALAR_FLOAT_TYPE_P (scalar_type));
2807 if (nested_in_vect_loop_p (loop, stmt))
2808 nested_in_vect_loop = true;
2810 gcc_assert (loop == (gimple_bb (stmt))->loop_father);
2812 /* In case of double reduction we only create a vector variable to be put
2813 in the reduction phi node. The actual statement creation is done in
2814 vect_create_epilog_for_reduction. */
2815 if (adjustment_def && nested_in_vect_loop
2816 && TREE_CODE (init_val) == SSA_NAME
2817 && (def_stmt = SSA_NAME_DEF_STMT (init_val))
2818 && gimple_code (def_stmt) == GIMPLE_PHI
2819 && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
2820 && vinfo_for_stmt (def_stmt)
2821 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
2822 == vect_double_reduction_def)
2824 *adjustment_def = NULL;
2825 return vect_create_destination_var (init_val, vectype);
2828 if (TREE_CONSTANT (init_val))
2830 if (SCALAR_FLOAT_TYPE_P (scalar_type))
2831 init_value = build_real (scalar_type, TREE_REAL_CST (init_val));
2833 init_value = build_int_cst (scalar_type, TREE_INT_CST_LOW (init_val));
2836 init_value = init_val;
2840 case WIDEN_SUM_EXPR:
2848 /* ADJUSMENT_DEF is NULL when called from
2849 vect_create_epilog_for_reduction to vectorize double reduction. */
2852 if (nested_in_vect_loop)
2853 *adjustment_def = vect_get_vec_def_for_operand (init_val, stmt,
2856 *adjustment_def = init_val;
2859 if (code == MULT_EXPR || code == BIT_AND_EXPR)
2861 real_init_val = dconst1;
2865 if (SCALAR_FLOAT_TYPE_P (scalar_type))
2866 def_for_init = build_real (scalar_type, real_init_val);
2868 def_for_init = build_int_cst (scalar_type, int_init_val);
2870 /* Create a vector of '0' or '1' except the first element. */
2871 for (i = nunits - 2; i >= 0; --i)
2872 t = tree_cons (NULL_TREE, def_for_init, t);
2874 /* Option1: the first element is '0' or '1' as well. */
2877 t = tree_cons (NULL_TREE, def_for_init, t);
2878 init_def = build_vector (vectype, t);
2882 /* Option2: the first element is INIT_VAL. */
2883 t = tree_cons (NULL_TREE, init_value, t);
2884 if (TREE_CONSTANT (init_val))
2885 init_def = build_vector (vectype, t);
2887 init_def = build_constructor_from_list (vectype, t);
2896 *adjustment_def = NULL_TREE;
2897 init_def = vect_get_vec_def_for_operand (init_val, stmt, NULL);
2901 for (i = nunits - 1; i >= 0; --i)
2902 t = tree_cons (NULL_TREE, init_value, t);
2904 if (TREE_CONSTANT (init_val))
2905 init_def = build_vector (vectype, t);
2907 init_def = build_constructor_from_list (vectype, t);
2919 /* Function vect_create_epilog_for_reduction
2921 Create code at the loop-epilog to finalize the result of a reduction
2924 VECT_DEFS is list of vector of partial results, i.e., the lhs's of vector
2925 reduction statements.
2926 STMT is the scalar reduction stmt that is being vectorized.
2927 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
2928 number of elements that we can fit in a vectype (nunits). In this case
2929 we have to generate more than one vector stmt - i.e - we need to "unroll"
2930 the vector stmt by a factor VF/nunits. For more details see documentation
2931 in vectorizable_operation.
2932 REDUC_CODE is the tree-code for the epilog reduction.
2933 REDUCTION_PHIS is a list of the phi-nodes that carry the reduction
2935 REDUC_INDEX is the index of the operand in the right hand side of the
2936 statement that is defined by REDUCTION_PHI.
2937 DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
2938 SLP_NODE is an SLP node containing a group of reduction statements. The
2939 first one in this group is STMT.
2942 1. Creates the reduction def-use cycles: sets the arguments for
2944 The loop-entry argument is the vectorized initial-value of the reduction.
2945 The loop-latch argument is taken from VECT_DEFS - the vector of partial
2947 2. "Reduces" each vector of partial results VECT_DEFS into a single result,
2948 by applying the operation specified by REDUC_CODE if available, or by
2949 other means (whole-vector shifts or a scalar loop).
2950 The function also creates a new phi node at the loop exit to preserve
2951 loop-closed form, as illustrated below.
2953 The flow at the entry to this function:
2956 vec_def = phi <null, null> # REDUCTION_PHI
2957 VECT_DEF = vector_stmt # vectorized form of STMT
2958 s_loop = scalar_stmt # (scalar) STMT
2960 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
2964 The above is transformed by this function into:
2967 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
2968 VECT_DEF = vector_stmt # vectorized form of STMT
2969 s_loop = scalar_stmt # (scalar) STMT
2971 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
2972 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
2973 v_out2 = reduce <v_out1>
2974 s_out3 = extract_field <v_out2, 0>
2975 s_out4 = adjust_result <s_out3>
2981 vect_create_epilog_for_reduction (VEC (tree, heap) *vect_defs, gimple stmt,
2982 int ncopies, enum tree_code reduc_code,
2983 VEC (gimple, heap) *reduction_phis,
2984 int reduc_index, bool double_reduc,
2987 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2988 stmt_vec_info prev_phi_info;
2990 enum machine_mode mode;
2991 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2992 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo), *outer_loop = NULL;
2993 basic_block exit_bb;
2996 gimple new_phi = NULL, phi;
2997 gimple_stmt_iterator exit_gsi;
2999 tree new_temp = NULL_TREE, new_dest, new_name, new_scalar_dest;
3000 gimple epilog_stmt = NULL;
3001 enum tree_code code = gimple_assign_rhs_code (stmt);
3003 tree bitsize, bitpos;
3004 tree adjustment_def = NULL;
3005 tree vec_initial_def = NULL;
3006 tree reduction_op, expr, def;
3007 tree orig_name, scalar_result;
3008 imm_use_iterator imm_iter;
3009 use_operand_p use_p;
3010 bool extract_scalar_result = false;
3011 gimple use_stmt, orig_stmt, reduction_phi = NULL;
3012 bool nested_in_vect_loop = false;
3013 VEC (gimple, heap) *new_phis = NULL;
3014 enum vect_def_type dt = vect_unknown_def_type;
3016 VEC (tree, heap) *scalar_results = NULL;
3017 unsigned int group_size = 1, k, ratio;
3018 VEC (tree, heap) *vec_initial_defs = NULL;
3019 VEC (gimple, heap) *phis;
3022 group_size = VEC_length (gimple, SLP_TREE_SCALAR_STMTS (slp_node));
3024 if (nested_in_vect_loop_p (loop, stmt))
3028 nested_in_vect_loop = true;
3029 gcc_assert (!slp_node);
3032 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
3034 case GIMPLE_SINGLE_RHS:
3035 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt))
3037 reduction_op = TREE_OPERAND (gimple_assign_rhs1 (stmt), reduc_index);
3039 case GIMPLE_UNARY_RHS:
3040 reduction_op = gimple_assign_rhs1 (stmt);
3042 case GIMPLE_BINARY_RHS:
3043 reduction_op = reduc_index ?
3044 gimple_assign_rhs2 (stmt) : gimple_assign_rhs1 (stmt);
3050 vectype = get_vectype_for_scalar_type (TREE_TYPE (reduction_op));
3051 gcc_assert (vectype);
3052 mode = TYPE_MODE (vectype);
3054 /* 1. Create the reduction def-use cycle:
3055 Set the arguments of REDUCTION_PHIS, i.e., transform
3058 vec_def = phi <null, null> # REDUCTION_PHI
3059 VECT_DEF = vector_stmt # vectorized form of STMT
3065 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3066 VECT_DEF = vector_stmt # vectorized form of STMT
3069 (in case of SLP, do it for all the phis). */
3071 /* Get the loop-entry arguments. */
3073 vect_get_slp_defs (slp_node, &vec_initial_defs, NULL, reduc_index);
3076 vec_initial_defs = VEC_alloc (tree, heap, 1);
3077 /* For the case of reduction, vect_get_vec_def_for_operand returns
3078 the scalar def before the loop, that defines the initial value
3079 of the reduction variable. */
3080 vec_initial_def = vect_get_vec_def_for_operand (reduction_op, stmt,
3082 VEC_quick_push (tree, vec_initial_defs, vec_initial_def);
3085 /* Set phi nodes arguments. */
3086 for (i = 0; VEC_iterate (gimple, reduction_phis, i, phi); i++)
3088 tree vec_init_def = VEC_index (tree, vec_initial_defs, i);
3089 tree def = VEC_index (tree, vect_defs, i);
3090 for (j = 0; j < ncopies; j++)
3092 /* Set the loop-entry arg of the reduction-phi. */
3093 add_phi_arg (phi, vec_init_def, loop_preheader_edge (loop),
3096 /* Set the loop-latch arg for the reduction-phi. */
3098 def = vect_get_vec_def_for_stmt_copy (vect_unknown_def_type, def);
3100 add_phi_arg (phi, def, loop_latch_edge (loop), UNKNOWN_LOCATION);
3102 if (vect_print_dump_info (REPORT_DETAILS))
3104 fprintf (vect_dump, "transform reduction: created def-use"
3106 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
3107 fprintf (vect_dump, "\n");
3108 print_gimple_stmt (vect_dump, SSA_NAME_DEF_STMT (def), 0,
3112 phi = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi));
3116 VEC_free (tree, heap, vec_initial_defs);
3118 /* 2. Create epilog code.
3119 The reduction epilog code operates across the elements of the vector
3120 of partial results computed by the vectorized loop.
3121 The reduction epilog code consists of:
3123 step 1: compute the scalar result in a vector (v_out2)
3124 step 2: extract the scalar result (s_out3) from the vector (v_out2)
3125 step 3: adjust the scalar result (s_out3) if needed.
3127 Step 1 can be accomplished using one the following three schemes:
3128 (scheme 1) using reduc_code, if available.
3129 (scheme 2) using whole-vector shifts, if available.
3130 (scheme 3) using a scalar loop. In this case steps 1+2 above are
3133 The overall epilog code looks like this:
3135 s_out0 = phi <s_loop> # original EXIT_PHI
3136 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3137 v_out2 = reduce <v_out1> # step 1
3138 s_out3 = extract_field <v_out2, 0> # step 2
3139 s_out4 = adjust_result <s_out3> # step 3
3141 (step 3 is optional, and steps 1 and 2 may be combined).
3142 Lastly, the uses of s_out0 are replaced by s_out4. */
3145 /* 2.1 Create new loop-exit-phis to preserve loop-closed form:
3146 v_out1 = phi <VECT_DEF>
3147 Store them in NEW_PHIS. */
3149 exit_bb = single_exit (loop)->dest;
3150 prev_phi_info = NULL;
3151 new_phis = VEC_alloc (gimple, heap, VEC_length (tree, vect_defs));
3152 for (i = 0; VEC_iterate (tree, vect_defs, i, def); i++)
3154 for (j = 0; j < ncopies; j++)
3156 phi = create_phi_node (SSA_NAME_VAR (def), exit_bb);
3157 set_vinfo_for_stmt (phi, new_stmt_vec_info (phi, loop_vinfo, NULL));
3159 VEC_quick_push (gimple, new_phis, phi);
3162 def = vect_get_vec_def_for_stmt_copy (dt, def);
3163 STMT_VINFO_RELATED_STMT (prev_phi_info) = phi;
3166 SET_PHI_ARG_DEF (phi, single_exit (loop)->dest_idx, def);
3167 prev_phi_info = vinfo_for_stmt (phi);
3171 exit_gsi = gsi_after_labels (exit_bb);
3173 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
3174 (i.e. when reduc_code is not available) and in the final adjustment
3175 code (if needed). Also get the original scalar reduction variable as
3176 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
3177 represents a reduction pattern), the tree-code and scalar-def are
3178 taken from the original stmt that the pattern-stmt (STMT) replaces.
3179 Otherwise (it is a regular reduction) - the tree-code and scalar-def
3180 are taken from STMT. */
3182 orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
3185 /* Regular reduction */
3190 /* Reduction pattern */
3191 stmt_vec_info stmt_vinfo = vinfo_for_stmt (orig_stmt);
3192 gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo));
3193 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo) == stmt);
3196 code = gimple_assign_rhs_code (orig_stmt);
3197 /* For MINUS_EXPR the initial vector is [init_val,0,...,0], therefore,
3198 partial results are added and not subtracted. */
3199 if (code == MINUS_EXPR)
3202 scalar_dest = gimple_assign_lhs (orig_stmt);
3203 scalar_type = TREE_TYPE (scalar_dest);
3204 scalar_results = VEC_alloc (tree, heap, group_size);
3205 new_scalar_dest = vect_create_destination_var (scalar_dest, NULL);
3206 bitsize = TYPE_SIZE (scalar_type);
3208 /* In case this is a reduction in an inner-loop while vectorizing an outer
3209 loop - we don't need to extract a single scalar result at the end of the
3210 inner-loop (unless it is double reduction, i.e., the use of reduction is
3211 outside the outer-loop). The final vector of partial results will be used
3212 in the vectorized outer-loop, or reduced to a scalar result at the end of
3214 if (nested_in_vect_loop && !double_reduc)
3215 goto vect_finalize_reduction;
3217 /* 2.3 Create the reduction code, using one of the three schemes described
3218 above. In SLP we simply need to extract all the elements from the
3219 vector (without reducing them), so we use scalar shifts. */
3220 if (reduc_code != ERROR_MARK && !slp_node)
3224 /*** Case 1: Create:
3225 v_out2 = reduc_expr <v_out1> */
3227 if (vect_print_dump_info (REPORT_DETAILS))
3228 fprintf (vect_dump, "Reduce using direct vector reduction.");
3230 vec_dest = vect_create_destination_var (scalar_dest, vectype);
3231 new_phi = VEC_index (gimple, new_phis, 0);
3232 tmp = build1 (reduc_code, vectype, PHI_RESULT (new_phi));
3233 epilog_stmt = gimple_build_assign (vec_dest, tmp);
3234 new_temp = make_ssa_name (vec_dest, epilog_stmt);
3235 gimple_assign_set_lhs (epilog_stmt, new_temp);
3236 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3238 extract_scalar_result = true;
3242 enum tree_code shift_code = ERROR_MARK;
3243 bool have_whole_vector_shift = true;
3245 int element_bitsize = tree_low_cst (bitsize, 1);
3246 int vec_size_in_bits = tree_low_cst (TYPE_SIZE (vectype), 1);
3249 if (optab_handler (vec_shr_optab, mode)->insn_code != CODE_FOR_nothing)
3250 shift_code = VEC_RSHIFT_EXPR;
3252 have_whole_vector_shift = false;
3254 /* Regardless of whether we have a whole vector shift, if we're
3255 emulating the operation via tree-vect-generic, we don't want
3256 to use it. Only the first round of the reduction is likely
3257 to still be profitable via emulation. */
3258 /* ??? It might be better to emit a reduction tree code here, so that
3259 tree-vect-generic can expand the first round via bit tricks. */
3260 if (!VECTOR_MODE_P (mode))
3261 have_whole_vector_shift = false;
3264 optab optab = optab_for_tree_code (code, vectype, optab_default);
3265 if (optab_handler (optab, mode)->insn_code == CODE_FOR_nothing)
3266 have_whole_vector_shift = false;
3269 if (have_whole_vector_shift && !slp_node)
3271 /*** Case 2: Create:
3272 for (offset = VS/2; offset >= element_size; offset/=2)
3274 Create: va' = vec_shift <va, offset>
3275 Create: va = vop <va, va'>
3278 if (vect_print_dump_info (REPORT_DETAILS))
3279 fprintf (vect_dump, "Reduce using vector shifts");
3281 vec_dest = vect_create_destination_var (scalar_dest, vectype);
3282 new_phi = VEC_index (gimple, new_phis, 0);
3283 new_temp = PHI_RESULT (new_phi);
3284 for (bit_offset = vec_size_in_bits/2;
3285 bit_offset >= element_bitsize;
3288 tree bitpos = size_int (bit_offset);
3290 epilog_stmt = gimple_build_assign_with_ops (shift_code,
3291 vec_dest, new_temp, bitpos);
3292 new_name = make_ssa_name (vec_dest, epilog_stmt);
3293 gimple_assign_set_lhs (epilog_stmt, new_name);
3294 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3296 epilog_stmt = gimple_build_assign_with_ops (code, vec_dest,
3297 new_name, new_temp);
3298 new_temp = make_ssa_name (vec_dest, epilog_stmt);
3299 gimple_assign_set_lhs (epilog_stmt, new_temp);
3300 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3303 extract_scalar_result = true;
3309 /*** Case 3: Create:
3310 s = extract_field <v_out2, 0>
3311 for (offset = element_size;
3312 offset < vector_size;
3313 offset += element_size;)
3315 Create: s' = extract_field <v_out2, offset>
3316 Create: s = op <s, s'> // For non SLP cases
3319 if (vect_print_dump_info (REPORT_DETAILS))
3320 fprintf (vect_dump, "Reduce using scalar code. ");
3322 vec_size_in_bits = tree_low_cst (TYPE_SIZE (vectype), 1);
3323 for (i = 0; VEC_iterate (gimple, new_phis, i, new_phi); i++)
3325 vec_temp = PHI_RESULT (new_phi);
3326 rhs = build3 (BIT_FIELD_REF, scalar_type, vec_temp, bitsize,
3328 epilog_stmt = gimple_build_assign (new_scalar_dest, rhs);
3329 new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
3330 gimple_assign_set_lhs (epilog_stmt, new_temp);
3331 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3333 /* In SLP we don't need to apply reduction operation, so we just
3334 collect s' values in SCALAR_RESULTS. */
3336 VEC_safe_push (tree, heap, scalar_results, new_temp);
3338 for (bit_offset = element_bitsize;
3339 bit_offset < vec_size_in_bits;
3340 bit_offset += element_bitsize)
3342 tree bitpos = bitsize_int (bit_offset);
3343 tree rhs = build3 (BIT_FIELD_REF, scalar_type, vec_temp,
3346 epilog_stmt = gimple_build_assign (new_scalar_dest, rhs);
3347 new_name = make_ssa_name (new_scalar_dest, epilog_stmt);
3348 gimple_assign_set_lhs (epilog_stmt, new_name);
3349 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3353 /* In SLP we don't need to apply reduction operation, so
3354 we just collect s' values in SCALAR_RESULTS. */
3355 new_temp = new_name;
3356 VEC_safe_push (tree, heap, scalar_results, new_name);
3360 epilog_stmt = gimple_build_assign_with_ops (code,
3361 new_scalar_dest, new_name, new_temp);
3362 new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
3363 gimple_assign_set_lhs (epilog_stmt, new_temp);
3364 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3369 /* The only case where we need to reduce scalar results in SLP, is
3370 unrolling. If the size of SCALAR_RESULTS is greater than
3371 GROUP_SIZE, we reduce them combining elements modulo
3375 tree res, first_res, new_res;
3378 /* Reduce multiple scalar results in case of SLP unrolling. */
3379 for (j = group_size; VEC_iterate (tree, scalar_results, j, res);
3382 first_res = VEC_index (tree, scalar_results, j % group_size);
3383 new_stmt = gimple_build_assign_with_ops (code,
3384 new_scalar_dest, first_res, res);
3385 new_res = make_ssa_name (new_scalar_dest, new_stmt);
3386 gimple_assign_set_lhs (new_stmt, new_res);
3387 gsi_insert_before (&exit_gsi, new_stmt, GSI_SAME_STMT);
3388 VEC_replace (tree, scalar_results, j % group_size, new_res);
3392 /* Not SLP - we have one scalar to keep in SCALAR_RESULTS. */
3393 VEC_safe_push (tree, heap, scalar_results, new_temp);
3395 extract_scalar_result = false;
3399 /* 2.4 Extract the final scalar result. Create:
3400 s_out3 = extract_field <v_out2, bitpos> */
3402 if (extract_scalar_result)
3406 if (vect_print_dump_info (REPORT_DETAILS))
3407 fprintf (vect_dump, "extract scalar result");
3409 if (BYTES_BIG_ENDIAN)
3410 bitpos = size_binop (MULT_EXPR,
3411 bitsize_int (TYPE_VECTOR_SUBPARTS (vectype) - 1),
3412 TYPE_SIZE (scalar_type));
3414 bitpos = bitsize_zero_node;
3416 rhs = build3 (BIT_FIELD_REF, scalar_type, new_temp, bitsize, bitpos);
3417 epilog_stmt = gimple_build_assign (new_scalar_dest, rhs);
3418 new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
3419 gimple_assign_set_lhs (epilog_stmt, new_temp);
3420 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3421 VEC_safe_push (tree, heap, scalar_results, new_temp);
3424 vect_finalize_reduction:
3426 /* 2.5 Adjust the final result by the initial value of the reduction
3427 variable. (When such adjustment is not needed, then
3428 'adjustment_def' is zero). For example, if code is PLUS we create:
3429 new_temp = loop_exit_def + adjustment_def */
3433 gcc_assert (!slp_node);
3434 if (nested_in_vect_loop)
3436 new_phi = VEC_index (gimple, new_phis, 0);
3437 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def)) == VECTOR_TYPE);
3438 expr = build2 (code, vectype, PHI_RESULT (new_phi), adjustment_def);
3439 new_dest = vect_create_destination_var (scalar_dest, vectype);
3443 new_temp = VEC_index (tree, scalar_results, 0);
3444 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def)) != VECTOR_TYPE);
3445 expr = build2 (code, scalar_type, new_temp, adjustment_def);
3446 new_dest = vect_create_destination_var (scalar_dest, scalar_type);
3449 epilog_stmt = gimple_build_assign (new_dest, expr);
3450 new_temp = make_ssa_name (new_dest, epilog_stmt);
3451 gimple_assign_set_lhs (epilog_stmt, new_temp);
3452 SSA_NAME_DEF_STMT (new_temp) = epilog_stmt;
3453 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3454 if (nested_in_vect_loop)
3456 set_vinfo_for_stmt (epilog_stmt,
3457 new_stmt_vec_info (epilog_stmt, loop_vinfo,
3459 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (epilog_stmt)) =
3460 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_phi));
3463 VEC_quick_push (tree, scalar_results, new_temp);
3465 VEC_replace (tree, scalar_results, 0, new_temp);
3468 VEC_replace (tree, scalar_results, 0, new_temp);
3470 VEC_replace (gimple, new_phis, 0, epilog_stmt);
3473 /* 2.6 Handle the loop-exit phis. Replace the uses of scalar loop-exit
3474 phis with new adjusted scalar results, i.e., replace use <s_out0>
3479 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3480 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3481 v_out2 = reduce <v_out1>
3482 s_out3 = extract_field <v_out2, 0>
3483 s_out4 = adjust_result <s_out3>
3490 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3491 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3492 v_out2 = reduce <v_out1>
3493 s_out3 = extract_field <v_out2, 0>
3494 s_out4 = adjust_result <s_out3>
3498 /* In SLP we may have several statements in NEW_PHIS and REDUCTION_PHIS (in
3499 case that GROUP_SIZE is greater than vectorization factor). Therefore, we
3500 need to match SCALAR_RESULTS with corresponding statements. The first
3501 (GROUP_SIZE / number of new vector stmts) scalar results correspond to
3502 the first vector stmt, etc.
3503 (RATIO is equal to (GROUP_SIZE / number of new vector stmts)). */
3504 if (group_size > VEC_length (gimple, new_phis))
3506 ratio = group_size / VEC_length (gimple, new_phis);
3507 gcc_assert (!(group_size % VEC_length (gimple, new_phis)));
3512 for (k = 0; k < group_size; k++)
3516 epilog_stmt = VEC_index (gimple, new_phis, k / ratio);
3517 reduction_phi = VEC_index (gimple, reduction_phis, k / ratio);
3522 gimple current_stmt = VEC_index (gimple,
3523 SLP_TREE_SCALAR_STMTS (slp_node), k);
3525 orig_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (current_stmt));
3526 /* SLP statements can't participate in patterns. */
3527 gcc_assert (!orig_stmt);
3528 scalar_dest = gimple_assign_lhs (current_stmt);
3531 phis = VEC_alloc (gimple, heap, 3);
3532 /* Find the loop-closed-use at the loop exit of the original scalar
3533 result. (The reduction result is expected to have two immediate uses -
3534 one at the latch block, and one at the loop exit). */
3535 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, scalar_dest)
3536 if (!flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
3537 VEC_safe_push (gimple, heap, phis, USE_STMT (use_p));
3539 /* We expect to have found an exit_phi because of loop-closed-ssa
3541 gcc_assert (!VEC_empty (gimple, phis));
3543 for (i = 0; VEC_iterate (gimple, phis, i, exit_phi); i++)
3547 stmt_vec_info exit_phi_vinfo = vinfo_for_stmt (exit_phi);
3550 /* FORNOW. Currently not supporting the case that an inner-loop
3551 reduction is not used in the outer-loop (but only outside the
3552 outer-loop), unless it is double reduction. */
3553 gcc_assert ((STMT_VINFO_RELEVANT_P (exit_phi_vinfo)
3554 && !STMT_VINFO_LIVE_P (exit_phi_vinfo))
3557 STMT_VINFO_VEC_STMT (exit_phi_vinfo) = epilog_stmt;
3559 || STMT_VINFO_DEF_TYPE (exit_phi_vinfo)
3560 != vect_double_reduction_def)
3563 /* Handle double reduction:
3565 stmt1: s1 = phi <s0, s2> - double reduction phi (outer loop)
3566 stmt2: s3 = phi <s1, s4> - (regular) reduc phi (inner loop)
3567 stmt3: s4 = use (s3) - (regular) reduc stmt (inner loop)
3568 stmt4: s2 = phi <s4> - double reduction stmt (outer loop)
3570 At that point the regular reduction (stmt2 and stmt3) is
3571 already vectorized, as well as the exit phi node, stmt4.
3572 Here we vectorize the phi node of double reduction, stmt1, and
3573 update all relevant statements. */
3575 /* Go through all the uses of s2 to find double reduction phi
3576 node, i.e., stmt1 above. */
3577 orig_name = PHI_RESULT (exit_phi);
3578 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, orig_name)
3580 stmt_vec_info use_stmt_vinfo = vinfo_for_stmt (use_stmt);
3581 stmt_vec_info new_phi_vinfo;
3582 tree vect_phi_init, preheader_arg, vect_phi_res, init_def;
3583 basic_block bb = gimple_bb (use_stmt);
3586 /* Check that USE_STMT is really double reduction phi
3588 if (gimple_code (use_stmt) != GIMPLE_PHI
3589 || gimple_phi_num_args (use_stmt) != 2
3591 || STMT_VINFO_DEF_TYPE (use_stmt_vinfo)
3592 != vect_double_reduction_def
3593 || bb->loop_father != outer_loop)
3596 /* Create vector phi node for double reduction:
3597 vs1 = phi <vs0, vs2>
3598 vs1 was created previously in this function by a call to
3599 vect_get_vec_def_for_operand and is stored in
3601 vs2 is defined by EPILOG_STMT, the vectorized EXIT_PHI;
3602 vs0 is created here. */
3604 /* Create vector phi node. */
3605 vect_phi = create_phi_node (vec_initial_def, bb);
3606 new_phi_vinfo = new_stmt_vec_info (vect_phi,
3607 loop_vec_info_for_loop (outer_loop), NULL);
3608 set_vinfo_for_stmt (vect_phi, new_phi_vinfo);
3610 /* Create vs0 - initial def of the double reduction phi. */
3611 preheader_arg = PHI_ARG_DEF_FROM_EDGE (use_stmt,
3612 loop_preheader_edge (outer_loop));
3613 init_def = get_initial_def_for_reduction (stmt,
3614 preheader_arg, NULL);
3615 vect_phi_init = vect_init_vector (use_stmt, init_def,
3618 /* Update phi node arguments with vs0 and vs2. */
3619 add_phi_arg (vect_phi, vect_phi_init,
3620 loop_preheader_edge (outer_loop),
3622 add_phi_arg (vect_phi, PHI_RESULT (epilog_stmt),
3623 loop_latch_edge (outer_loop), UNKNOWN_LOCATION);
3624 if (vect_print_dump_info (REPORT_DETAILS))
3626 fprintf (vect_dump, "created double reduction phi "
3628 print_gimple_stmt (vect_dump, vect_phi, 0, TDF_SLIM);
3631 vect_phi_res = PHI_RESULT (vect_phi);
3633 /* Replace the use, i.e., set the correct vs1 in the regular
3634 reduction phi node. FORNOW, NCOPIES is always 1, so the
3635 loop is redundant. */
3636 use = reduction_phi;
3637 for (j = 0; j < ncopies; j++)
3639 edge pr_edge = loop_preheader_edge (loop);
3640 SET_PHI_ARG_DEF (use, pr_edge->dest_idx, vect_phi_res);
3641 use = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use));
3646 /* Replace the uses: */
3647 orig_name = PHI_RESULT (exit_phi);
3648 scalar_result = VEC_index (tree, scalar_results, k);
3649 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, orig_name)
3650 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
3651 SET_USE (use_p, scalar_result);
3654 VEC_free (gimple, heap, phis);
3657 VEC_free (tree, heap, scalar_results);
3658 VEC_free (gimple, heap, new_phis);
3662 /* Function vectorizable_reduction.
3664 Check if STMT performs a reduction operation that can be vectorized.
3665 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3666 stmt to replace it, put it in VEC_STMT, and insert it at GSI.
3667 Return FALSE if not a vectorizable STMT, TRUE otherwise.
3669 This function also handles reduction idioms (patterns) that have been
3670 recognized in advance during vect_pattern_recog. In this case, STMT may be
3672 X = pattern_expr (arg0, arg1, ..., X)
3673 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
3674 sequence that had been detected and replaced by the pattern-stmt (STMT).
3676 In some cases of reduction patterns, the type of the reduction variable X is
3677 different than the type of the other arguments of STMT.
3678 In such cases, the vectype that is used when transforming STMT into a vector
3679 stmt is different than the vectype that is used to determine the
3680 vectorization factor, because it consists of a different number of elements
3681 than the actual number of elements that are being operated upon in parallel.
3683 For example, consider an accumulation of shorts into an int accumulator.
3684 On some targets it's possible to vectorize this pattern operating on 8
3685 shorts at a time (hence, the vectype for purposes of determining the
3686 vectorization factor should be V8HI); on the other hand, the vectype that
3687 is used to create the vector form is actually V4SI (the type of the result).
3689 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
3690 indicates what is the actual level of parallelism (V8HI in the example), so
3691 that the right vectorization factor would be derived. This vectype
3692 corresponds to the type of arguments to the reduction stmt, and should *NOT*
3693 be used to create the vectorized stmt. The right vectype for the vectorized
3694 stmt is obtained from the type of the result X:
3695 get_vectype_for_scalar_type (TREE_TYPE (X))
3697 This means that, contrary to "regular" reductions (or "regular" stmts in
3698 general), the following equation:
3699 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
3700 does *NOT* necessarily hold for reduction patterns. */
3703 vectorizable_reduction (gimple stmt, gimple_stmt_iterator *gsi,
3704 gimple *vec_stmt, slp_tree slp_node)
3708 tree loop_vec_def0 = NULL_TREE, loop_vec_def1 = NULL_TREE;
3709 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3710 tree vectype_out = STMT_VINFO_VECTYPE (stmt_info);
3711 tree vectype_in = NULL_TREE;
3712 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3713 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
3714 enum tree_code code, orig_code, epilog_reduc_code;
3715 enum machine_mode vec_mode;
3717 optab optab, reduc_optab;
3718 tree new_temp = NULL_TREE;
3721 enum vect_def_type dt;
3722 gimple new_phi = NULL;
3726 stmt_vec_info orig_stmt_info;
3727 tree expr = NULL_TREE;
3731 stmt_vec_info prev_stmt_info, prev_phi_info;
3732 bool single_defuse_cycle = false;
3733 tree reduc_def = NULL_TREE;
3734 gimple new_stmt = NULL;
3737 bool nested_cycle = false, found_nested_cycle_def = false;
3738 gimple reduc_def_stmt = NULL;
3739 /* The default is that the reduction variable is the last in statement. */
3740 int reduc_index = 2;
3741 bool double_reduc = false, dummy;
3743 struct loop * def_stmt_loop, *outer_loop = NULL;
3745 gimple def_arg_stmt;
3746 VEC (tree, heap) *vec_oprnds0 = NULL, *vec_oprnds1 = NULL, *vect_defs = NULL;
3747 VEC (gimple, heap) *phis = NULL;
3751 if (nested_in_vect_loop_p (loop, stmt))
3755 nested_cycle = true;
3758 /* 1. Is vectorizable reduction? */
3759 /* Not supportable if the reduction variable is used in the loop. */
3760 if (STMT_VINFO_RELEVANT (stmt_info) > vect_used_in_outer)
3763 /* Reductions that are not used even in an enclosing outer-loop,
3764 are expected to be "live" (used out of the loop). */
3765 if (STMT_VINFO_RELEVANT (stmt_info) == vect_unused_in_scope
3766 && !STMT_VINFO_LIVE_P (stmt_info))
3769 /* Make sure it was already recognized as a reduction computation. */
3770 if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_reduction_def
3771 && STMT_VINFO_DEF_TYPE (stmt_info) != vect_nested_cycle)
3774 /* 2. Has this been recognized as a reduction pattern?
3776 Check if STMT represents a pattern that has been recognized
3777 in earlier analysis stages. For stmts that represent a pattern,
3778 the STMT_VINFO_RELATED_STMT field records the last stmt in
3779 the original sequence that constitutes the pattern. */
3781 orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
3784 orig_stmt_info = vinfo_for_stmt (orig_stmt);
3785 gcc_assert (STMT_VINFO_RELATED_STMT (orig_stmt_info) == stmt);
3786 gcc_assert (STMT_VINFO_IN_PATTERN_P (orig_stmt_info));
3787 gcc_assert (!STMT_VINFO_IN_PATTERN_P (stmt_info));
3790 /* 3. Check the operands of the operation. The first operands are defined
3791 inside the loop body. The last operand is the reduction variable,
3792 which is defined by the loop-header-phi. */
3794 gcc_assert (is_gimple_assign (stmt));
3797 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
3799 case GIMPLE_SINGLE_RHS:
3800 op_type = TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt));
3801 if (op_type == ternary_op)
3803 tree rhs = gimple_assign_rhs1 (stmt);
3804 ops[0] = TREE_OPERAND (rhs, 0);
3805 ops[1] = TREE_OPERAND (rhs, 1);
3806 ops[2] = TREE_OPERAND (rhs, 2);
3807 code = TREE_CODE (rhs);
3813 case GIMPLE_BINARY_RHS:
3814 code = gimple_assign_rhs_code (stmt);
3815 op_type = TREE_CODE_LENGTH (code);
3816 gcc_assert (op_type == binary_op);
3817 ops[0] = gimple_assign_rhs1 (stmt);
3818 ops[1] = gimple_assign_rhs2 (stmt);
3821 case GIMPLE_UNARY_RHS:
3828 scalar_dest = gimple_assign_lhs (stmt);
3829 scalar_type = TREE_TYPE (scalar_dest);
3830 if (!POINTER_TYPE_P (scalar_type) && !INTEGRAL_TYPE_P (scalar_type)
3831 && !SCALAR_FLOAT_TYPE_P (scalar_type))
3834 /* All uses but the last are expected to be defined in the loop.
3835 The last use is the reduction variable. In case of nested cycle this
3836 assumption is not true: we use reduc_index to record the index of the
3837 reduction variable. */
3838 for (i = 0; i < op_type-1; i++)
3842 /* The condition of COND_EXPR is checked in vectorizable_condition(). */
3843 if (i == 0 && code == COND_EXPR)
3846 is_simple_use = vect_is_simple_use_1 (ops[i], loop_vinfo, NULL,
3847 &def_stmt, &def, &dt, &tem);
3850 gcc_assert (is_simple_use);
3851 if (dt != vect_internal_def
3852 && dt != vect_external_def
3853 && dt != vect_constant_def
3854 && dt != vect_induction_def
3855 && !(dt == vect_nested_cycle && nested_cycle))
3858 if (dt == vect_nested_cycle)
3860 found_nested_cycle_def = true;
3861 reduc_def_stmt = def_stmt;
3866 is_simple_use = vect_is_simple_use (ops[i], loop_vinfo, NULL, &def_stmt,
3868 gcc_assert (is_simple_use);
3869 gcc_assert (dt == vect_reduction_def
3870 || dt == vect_nested_cycle
3871 || ((dt == vect_internal_def || dt == vect_external_def
3872 || dt == vect_constant_def || dt == vect_induction_def)
3873 && nested_cycle && found_nested_cycle_def));
3874 if (!found_nested_cycle_def)
3875 reduc_def_stmt = def_stmt;
3877 gcc_assert (gimple_code (reduc_def_stmt) == GIMPLE_PHI);
3879 gcc_assert (orig_stmt == vect_is_simple_reduction (loop_vinfo,
3884 gcc_assert (stmt == vect_is_simple_reduction (loop_vinfo, reduc_def_stmt,
3885 !nested_cycle, &dummy));
3887 if (STMT_VINFO_LIVE_P (vinfo_for_stmt (reduc_def_stmt)))
3893 ncopies = (LOOP_VINFO_VECT_FACTOR (loop_vinfo)
3894 / TYPE_VECTOR_SUBPARTS (vectype_in));
3896 gcc_assert (ncopies >= 1);
3898 vec_mode = TYPE_MODE (vectype_in);
3900 if (code == COND_EXPR)
3902 if (!vectorizable_condition (stmt, gsi, NULL, ops[reduc_index], 0))
3904 if (vect_print_dump_info (REPORT_DETAILS))
3905 fprintf (vect_dump, "unsupported condition in reduction");
3912 /* 4. Supportable by target? */
3914 /* 4.1. check support for the operation in the loop */
3915 optab = optab_for_tree_code (code, vectype_in, optab_default);
3918 if (vect_print_dump_info (REPORT_DETAILS))
3919 fprintf (vect_dump, "no optab.");
3924 if (optab_handler (optab, vec_mode)->insn_code == CODE_FOR_nothing)
3926 if (vect_print_dump_info (REPORT_DETAILS))
3927 fprintf (vect_dump, "op not supported by target.");
3929 if (GET_MODE_SIZE (vec_mode) != UNITS_PER_WORD
3930 || LOOP_VINFO_VECT_FACTOR (loop_vinfo)
3931 < vect_min_worthwhile_factor (code))
3934 if (vect_print_dump_info (REPORT_DETAILS))
3935 fprintf (vect_dump, "proceeding using word mode.");
3938 /* Worthwhile without SIMD support? */
3939 if (!VECTOR_MODE_P (TYPE_MODE (vectype_in))
3940 && LOOP_VINFO_VECT_FACTOR (loop_vinfo)
3941 < vect_min_worthwhile_factor (code))
3943 if (vect_print_dump_info (REPORT_DETAILS))
3944 fprintf (vect_dump, "not worthwhile without SIMD support.");
3950 /* 4.2. Check support for the epilog operation.
3952 If STMT represents a reduction pattern, then the type of the
3953 reduction variable may be different than the type of the rest
3954 of the arguments. For example, consider the case of accumulation
3955 of shorts into an int accumulator; The original code:
3956 S1: int_a = (int) short_a;
3957 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
3960 STMT: int_acc = widen_sum <short_a, int_acc>
3963 1. The tree-code that is used to create the vector operation in the
3964 epilog code (that reduces the partial results) is not the
3965 tree-code of STMT, but is rather the tree-code of the original
3966 stmt from the pattern that STMT is replacing. I.e, in the example
3967 above we want to use 'widen_sum' in the loop, but 'plus' in the
3969 2. The type (mode) we use to check available target support
3970 for the vector operation to be created in the *epilog*, is
3971 determined by the type of the reduction variable (in the example
3972 above we'd check this: plus_optab[vect_int_mode]).
3973 However the type (mode) we use to check available target support
3974 for the vector operation to be created *inside the loop*, is
3975 determined by the type of the other arguments to STMT (in the
3976 example we'd check this: widen_sum_optab[vect_short_mode]).
3978 This is contrary to "regular" reductions, in which the types of all
3979 the arguments are the same as the type of the reduction variable.
3980 For "regular" reductions we can therefore use the same vector type
3981 (and also the same tree-code) when generating the epilog code and
3982 when generating the code inside the loop. */
3986 /* This is a reduction pattern: get the vectype from the type of the
3987 reduction variable, and get the tree-code from orig_stmt. */
3988 orig_code = gimple_assign_rhs_code (orig_stmt);
3989 gcc_assert (vectype_out);
3990 vec_mode = TYPE_MODE (vectype_out);
3994 /* Regular reduction: use the same vectype and tree-code as used for
3995 the vector code inside the loop can be used for the epilog code. */
4001 def_bb = gimple_bb (reduc_def_stmt);
4002 def_stmt_loop = def_bb->loop_father;
4003 def_arg = PHI_ARG_DEF_FROM_EDGE (reduc_def_stmt,
4004 loop_preheader_edge (def_stmt_loop));
4005 if (TREE_CODE (def_arg) == SSA_NAME
4006 && (def_arg_stmt = SSA_NAME_DEF_STMT (def_arg))
4007 && gimple_code (def_arg_stmt) == GIMPLE_PHI
4008 && flow_bb_inside_loop_p (outer_loop, gimple_bb (def_arg_stmt))
4009 && vinfo_for_stmt (def_arg_stmt)
4010 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_arg_stmt))
4011 == vect_double_reduction_def)
4012 double_reduc = true;
4015 epilog_reduc_code = ERROR_MARK;
4016 if (reduction_code_for_scalar_code (orig_code, &epilog_reduc_code))
4018 reduc_optab = optab_for_tree_code (epilog_reduc_code, vectype_out,
4022 if (vect_print_dump_info (REPORT_DETAILS))
4023 fprintf (vect_dump, "no optab for reduction.");
4025 epilog_reduc_code = ERROR_MARK;
4029 && optab_handler (reduc_optab, vec_mode)->insn_code
4030 == CODE_FOR_nothing)
4032 if (vect_print_dump_info (REPORT_DETAILS))
4033 fprintf (vect_dump, "reduc op not supported by target.");
4035 epilog_reduc_code = ERROR_MARK;
4040 if (!nested_cycle || double_reduc)
4042 if (vect_print_dump_info (REPORT_DETAILS))
4043 fprintf (vect_dump, "no reduc code for scalar code.");
4049 if (double_reduc && ncopies > 1)
4051 if (vect_print_dump_info (REPORT_DETAILS))
4052 fprintf (vect_dump, "multiple types in double reduction");
4057 if (!vec_stmt) /* transformation not required. */
4059 STMT_VINFO_TYPE (stmt_info) = reduc_vec_info_type;
4060 if (!vect_model_reduction_cost (stmt_info, epilog_reduc_code, ncopies))
4067 if (vect_print_dump_info (REPORT_DETAILS))
4068 fprintf (vect_dump, "transform reduction.");
4070 /* FORNOW: Multiple types are not supported for condition. */
4071 if (code == COND_EXPR)
4072 gcc_assert (ncopies == 1);
4074 /* Create the destination vector */
4075 vec_dest = vect_create_destination_var (scalar_dest, vectype_out);
4077 /* In case the vectorization factor (VF) is bigger than the number
4078 of elements that we can fit in a vectype (nunits), we have to generate
4079 more than one vector stmt - i.e - we need to "unroll" the
4080 vector stmt by a factor VF/nunits. For more details see documentation
4081 in vectorizable_operation. */
4083 /* If the reduction is used in an outer loop we need to generate
4084 VF intermediate results, like so (e.g. for ncopies=2):
4089 (i.e. we generate VF results in 2 registers).
4090 In this case we have a separate def-use cycle for each copy, and therefore
4091 for each copy we get the vector def for the reduction variable from the
4092 respective phi node created for this copy.
4094 Otherwise (the reduction is unused in the loop nest), we can combine
4095 together intermediate results, like so (e.g. for ncopies=2):
4099 (i.e. we generate VF/2 results in a single register).
4100 In this case for each copy we get the vector def for the reduction variable
4101 from the vectorized reduction operation generated in the previous iteration.
4104 if (STMT_VINFO_RELEVANT (stmt_info) == vect_unused_in_scope)
4106 single_defuse_cycle = true;
4110 epilog_copies = ncopies;
4112 prev_stmt_info = NULL;
4113 prev_phi_info = NULL;
4116 vec_num = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
4117 gcc_assert (TYPE_VECTOR_SUBPARTS (vectype_out)
4118 == TYPE_VECTOR_SUBPARTS (vectype_in));
4123 vec_oprnds0 = VEC_alloc (tree, heap, 1);
4124 if (op_type == ternary_op)
4125 vec_oprnds1 = VEC_alloc (tree, heap, 1);
4128 phis = VEC_alloc (gimple, heap, vec_num);
4129 vect_defs = VEC_alloc (tree, heap, vec_num);
4131 VEC_quick_push (tree, vect_defs, NULL_TREE);
4133 for (j = 0; j < ncopies; j++)
4135 if (j == 0 || !single_defuse_cycle)
4137 for (i = 0; i < vec_num; i++)
4139 /* Create the reduction-phi that defines the reduction
4141 new_phi = create_phi_node (vec_dest, loop->header);
4142 set_vinfo_for_stmt (new_phi,
4143 new_stmt_vec_info (new_phi, loop_vinfo,
4145 if (j == 0 || slp_node)
4146 VEC_quick_push (gimple, phis, new_phi);
4150 if (code == COND_EXPR)
4152 gcc_assert (!slp_node);
4153 vectorizable_condition (stmt, gsi, vec_stmt,
4154 PHI_RESULT (VEC_index (gimple, phis, 0)),
4156 /* Multiple types are not supported for condition. */
4164 vect_get_slp_defs (slp_node, &vec_oprnds0, &vec_oprnds1, -1);
4167 loop_vec_def0 = vect_get_vec_def_for_operand (ops[!reduc_index],
4169 VEC_quick_push (tree, vec_oprnds0, loop_vec_def0);
4170 if (op_type == ternary_op)
4172 if (reduc_index == 0)
4173 loop_vec_def1 = vect_get_vec_def_for_operand (ops[2], stmt,
4176 loop_vec_def1 = vect_get_vec_def_for_operand (ops[1], stmt,
4179 VEC_quick_push (tree, vec_oprnds1, loop_vec_def1);
4187 enum vect_def_type dt = vect_unknown_def_type; /* Dummy */
4188 loop_vec_def0 = vect_get_vec_def_for_stmt_copy (dt, loop_vec_def0);
4189 VEC_replace (tree, vec_oprnds0, 0, loop_vec_def0);
4190 if (op_type == ternary_op)
4192 loop_vec_def1 = vect_get_vec_def_for_stmt_copy (dt,
4194 VEC_replace (tree, vec_oprnds1, 0, loop_vec_def1);
4198 if (single_defuse_cycle)
4199 reduc_def = gimple_assign_lhs (new_stmt);
4201 STMT_VINFO_RELATED_STMT (prev_phi_info) = new_phi;
4204 for (i = 0; VEC_iterate (tree, vec_oprnds0, i, def0); i++)
4207 reduc_def = PHI_RESULT (VEC_index (gimple, phis, i));
4210 if (!single_defuse_cycle || j == 0)
4211 reduc_def = PHI_RESULT (new_phi);
4214 def1 = ((op_type == ternary_op)
4215 ? VEC_index (tree, vec_oprnds1, i) : NULL);
4216 if (op_type == binary_op)
4218 if (reduc_index == 0)
4219 expr = build2 (code, vectype_out, reduc_def, def0);
4221 expr = build2 (code, vectype_out, def0, reduc_def);
4225 if (reduc_index == 0)
4226 expr = build3 (code, vectype_out, reduc_def, def0, def1);
4229 if (reduc_index == 1)
4230 expr = build3 (code, vectype_out, def0, reduc_def, def1);
4232 expr = build3 (code, vectype_out, def0, def1, reduc_def);
4236 new_stmt = gimple_build_assign (vec_dest, expr);
4237 new_temp = make_ssa_name (vec_dest, new_stmt);
4238 gimple_assign_set_lhs (new_stmt, new_temp);
4239 vect_finish_stmt_generation (stmt, new_stmt, gsi);
4242 VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
4243 VEC_quick_push (tree, vect_defs, new_temp);
4246 VEC_replace (tree, vect_defs, 0, new_temp);
4253 STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
4255 STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
4257 prev_stmt_info = vinfo_for_stmt (new_stmt);
4258 prev_phi_info = vinfo_for_stmt (new_phi);
4261 /* Finalize the reduction-phi (set its arguments) and create the
4262 epilog reduction code. */
4263 if ((!single_defuse_cycle || code == COND_EXPR) && !slp_node)
4265 new_temp = gimple_assign_lhs (*vec_stmt);
4266 VEC_replace (tree, vect_defs, 0, new_temp);
4269 vect_create_epilog_for_reduction (vect_defs, stmt, epilog_copies,
4270 epilog_reduc_code, phis, reduc_index,
4271 double_reduc, slp_node);
4273 VEC_free (gimple, heap, phis);
4274 VEC_free (tree, heap, vec_oprnds0);
4276 VEC_free (tree, heap, vec_oprnds1);
4281 /* Function vect_min_worthwhile_factor.
4283 For a loop where we could vectorize the operation indicated by CODE,
4284 return the minimum vectorization factor that makes it worthwhile
4285 to use generic vectors. */
4287 vect_min_worthwhile_factor (enum tree_code code)
4308 /* Function vectorizable_induction
4310 Check if PHI performs an induction computation that can be vectorized.
4311 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
4312 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
4313 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
4316 vectorizable_induction (gimple phi, gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
4319 stmt_vec_info stmt_info = vinfo_for_stmt (phi);
4320 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
4321 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
4322 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
4323 int nunits = TYPE_VECTOR_SUBPARTS (vectype);
4324 int ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
4327 gcc_assert (ncopies >= 1);
4328 /* FORNOW. This restriction should be relaxed. */
4329 if (nested_in_vect_loop_p (loop, phi) && ncopies > 1)
4331 if (vect_print_dump_info (REPORT_DETAILS))
4332 fprintf (vect_dump, "multiple types in nested loop.");
4336 if (!STMT_VINFO_RELEVANT_P (stmt_info))
4339 /* FORNOW: SLP not supported. */
4340 if (STMT_SLP_TYPE (stmt_info))
4343 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def);
4345 if (gimple_code (phi) != GIMPLE_PHI)
4348 if (!vec_stmt) /* transformation not required. */
4350 STMT_VINFO_TYPE (stmt_info) = induc_vec_info_type;
4351 if (vect_print_dump_info (REPORT_DETAILS))
4352 fprintf (vect_dump, "=== vectorizable_induction ===");
4353 vect_model_induction_cost (stmt_info, ncopies);
4359 if (vect_print_dump_info (REPORT_DETAILS))
4360 fprintf (vect_dump, "transform induction phi.");
4362 vec_def = get_initial_def_for_induction (phi);
4363 *vec_stmt = SSA_NAME_DEF_STMT (vec_def);
4367 /* Function vectorizable_live_operation.
4369 STMT computes a value that is used outside the loop. Check if
4370 it can be supported. */
4373 vectorizable_live_operation (gimple stmt,
4374 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
4375 gimple *vec_stmt ATTRIBUTE_UNUSED)
4377 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4378 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
4379 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
4385 enum vect_def_type dt;
4386 enum tree_code code;
4387 enum gimple_rhs_class rhs_class;
4389 gcc_assert (STMT_VINFO_LIVE_P (stmt_info));
4391 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_reduction_def)
4394 if (!is_gimple_assign (stmt))
4397 if (TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
4400 /* FORNOW. CHECKME. */
4401 if (nested_in_vect_loop_p (loop, stmt))
4404 code = gimple_assign_rhs_code (stmt);
4405 op_type = TREE_CODE_LENGTH (code);
4406 rhs_class = get_gimple_rhs_class (code);
4407 gcc_assert (rhs_class != GIMPLE_UNARY_RHS || op_type == unary_op);
4408 gcc_assert (rhs_class != GIMPLE_BINARY_RHS || op_type == binary_op);
4410 /* FORNOW: support only if all uses are invariant. This means
4411 that the scalar operations can remain in place, unvectorized.
4412 The original last scalar value that they compute will be used. */
4414 for (i = 0; i < op_type; i++)
4416 if (rhs_class == GIMPLE_SINGLE_RHS)
4417 op = TREE_OPERAND (gimple_op (stmt, 1), i);
4419 op = gimple_op (stmt, i + 1);
4421 && !vect_is_simple_use (op, loop_vinfo, NULL, &def_stmt, &def, &dt))
4423 if (vect_print_dump_info (REPORT_DETAILS))
4424 fprintf (vect_dump, "use not simple.");
4428 if (dt != vect_external_def && dt != vect_constant_def)
4432 /* No transformation is required for the cases we currently support. */
4436 /* Kill any debug uses outside LOOP of SSA names defined in STMT. */
4439 vect_loop_kill_debug_uses (struct loop *loop, gimple stmt)
4441 ssa_op_iter op_iter;
4442 imm_use_iterator imm_iter;
4443 def_operand_p def_p;
4446 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_DEF)
4448 FOR_EACH_IMM_USE_STMT (ustmt, imm_iter, DEF_FROM_PTR (def_p))
4452 if (!is_gimple_debug (ustmt))
4455 bb = gimple_bb (ustmt);
4457 if (!flow_bb_inside_loop_p (loop, bb))
4459 if (gimple_debug_bind_p (ustmt))
4461 if (vect_print_dump_info (REPORT_DETAILS))
4462 fprintf (vect_dump, "killing debug use");
4464 gimple_debug_bind_reset_value (ustmt);
4465 update_stmt (ustmt);
4474 /* Function vect_transform_loop.
4476 The analysis phase has determined that the loop is vectorizable.
4477 Vectorize the loop - created vectorized stmts to replace the scalar
4478 stmts in the loop, and update the loop exit condition. */
4481 vect_transform_loop (loop_vec_info loop_vinfo)
4483 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
4484 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
4485 int nbbs = loop->num_nodes;
4486 gimple_stmt_iterator si;
4489 int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
4491 bool slp_scheduled = false;
4492 unsigned int nunits;
4493 tree cond_expr = NULL_TREE;
4494 gimple_seq cond_expr_stmt_list = NULL;
4495 bool do_peeling_for_loop_bound;
4497 if (vect_print_dump_info (REPORT_DETAILS))
4498 fprintf (vect_dump, "=== vec_transform_loop ===");
4500 /* Peel the loop if there are data refs with unknown alignment.
4501 Only one data ref with unknown store is allowed. */
4503 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo))
4504 vect_do_peeling_for_alignment (loop_vinfo);
4506 do_peeling_for_loop_bound
4507 = (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
4508 || (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
4509 && LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0));
4511 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
4512 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
4513 vect_loop_versioning (loop_vinfo,
4514 !do_peeling_for_loop_bound,
4515 &cond_expr, &cond_expr_stmt_list);
4517 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
4518 compile time constant), or it is a constant that doesn't divide by the
4519 vectorization factor, then an epilog loop needs to be created.
4520 We therefore duplicate the loop: the original loop will be vectorized,
4521 and will compute the first (n/VF) iterations. The second copy of the loop
4522 will remain scalar and will compute the remaining (n%VF) iterations.
4523 (VF is the vectorization factor). */
4525 if (do_peeling_for_loop_bound)
4526 vect_do_peeling_for_loop_bound (loop_vinfo, &ratio,
4527 cond_expr, cond_expr_stmt_list);
4529 ratio = build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo)),
4530 LOOP_VINFO_INT_NITERS (loop_vinfo) / vectorization_factor);
4532 /* 1) Make sure the loop header has exactly two entries
4533 2) Make sure we have a preheader basic block. */
4535 gcc_assert (EDGE_COUNT (loop->header->preds) == 2);
4537 split_edge (loop_preheader_edge (loop));
4539 /* FORNOW: the vectorizer supports only loops which body consist
4540 of one basic block (header + empty latch). When the vectorizer will
4541 support more involved loop forms, the order by which the BBs are
4542 traversed need to be reconsidered. */
4544 for (i = 0; i < nbbs; i++)
4546 basic_block bb = bbs[i];
4547 stmt_vec_info stmt_info;
4550 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
4552 phi = gsi_stmt (si);
4553 if (vect_print_dump_info (REPORT_DETAILS))
4555 fprintf (vect_dump, "------>vectorizing phi: ");
4556 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
4558 stmt_info = vinfo_for_stmt (phi);
4562 if (MAY_HAVE_DEBUG_STMTS && !STMT_VINFO_LIVE_P (stmt_info))
4563 vect_loop_kill_debug_uses (loop, phi);
4565 if (!STMT_VINFO_RELEVANT_P (stmt_info)
4566 && !STMT_VINFO_LIVE_P (stmt_info))
4569 if ((TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info))
4570 != (unsigned HOST_WIDE_INT) vectorization_factor)
4571 && vect_print_dump_info (REPORT_DETAILS))
4572 fprintf (vect_dump, "multiple-types.");
4574 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def)
4576 if (vect_print_dump_info (REPORT_DETAILS))
4577 fprintf (vect_dump, "transform phi.");
4578 vect_transform_stmt (phi, NULL, NULL, NULL, NULL);
4582 for (si = gsi_start_bb (bb); !gsi_end_p (si);)
4584 gimple stmt = gsi_stmt (si);
4587 if (vect_print_dump_info (REPORT_DETAILS))
4589 fprintf (vect_dump, "------>vectorizing statement: ");
4590 print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
4593 stmt_info = vinfo_for_stmt (stmt);
4595 /* vector stmts created in the outer-loop during vectorization of
4596 stmts in an inner-loop may not have a stmt_info, and do not
4597 need to be vectorized. */
4604 if (MAY_HAVE_DEBUG_STMTS && !STMT_VINFO_LIVE_P (stmt_info))
4605 vect_loop_kill_debug_uses (loop, stmt);
4607 if (!STMT_VINFO_RELEVANT_P (stmt_info)
4608 && !STMT_VINFO_LIVE_P (stmt_info))
4614 gcc_assert (STMT_VINFO_VECTYPE (stmt_info));
4616 (unsigned int) TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info));
4617 if (!STMT_SLP_TYPE (stmt_info)
4618 && nunits != (unsigned int) vectorization_factor
4619 && vect_print_dump_info (REPORT_DETAILS))
4620 /* For SLP VF is set according to unrolling factor, and not to
4621 vector size, hence for SLP this print is not valid. */
4622 fprintf (vect_dump, "multiple-types.");
4624 /* SLP. Schedule all the SLP instances when the first SLP stmt is
4626 if (STMT_SLP_TYPE (stmt_info))
4630 slp_scheduled = true;
4632 if (vect_print_dump_info (REPORT_DETAILS))
4633 fprintf (vect_dump, "=== scheduling SLP instances ===");
4635 vect_schedule_slp (loop_vinfo, NULL);
4638 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
4639 if (!vinfo_for_stmt (stmt) || PURE_SLP_STMT (stmt_info))
4646 /* -------- vectorize statement ------------ */
4647 if (vect_print_dump_info (REPORT_DETAILS))
4648 fprintf (vect_dump, "transform statement.");
4650 strided_store = false;
4651 is_store = vect_transform_stmt (stmt, &si, &strided_store, NULL, NULL);
4654 if (STMT_VINFO_STRIDED_ACCESS (stmt_info))
4656 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
4657 interleaving chain was completed - free all the stores in
4659 vect_remove_stores (DR_GROUP_FIRST_DR (stmt_info));
4660 gsi_remove (&si, true);
4665 /* Free the attached stmt_vec_info and remove the stmt. */
4666 free_stmt_vec_info (stmt);
4667 gsi_remove (&si, true);
4675 slpeel_make_loop_iterate_ntimes (loop, ratio);
4677 /* The memory tags and pointers in vectorized statements need to
4678 have their SSA forms updated. FIXME, why can't this be delayed
4679 until all the loops have been transformed? */
4680 update_ssa (TODO_update_ssa);
4682 if (vect_print_dump_info (REPORT_VECTORIZED_LOCATIONS))
4683 fprintf (vect_dump, "LOOP VECTORIZED.");
4684 if (loop->inner && vect_print_dump_info (REPORT_VECTORIZED_LOCATIONS))
4685 fprintf (vect_dump, "OUTER LOOP VECTORIZED.");