PR target/47230
[official-gcc.git] / gcc / tree-vect-loop.c
blob7e013f3b549a07bd44789bd4d3e3701eec7c51dc
1 /* Loop Vectorization
2 Copyright (C) 2003-2014 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com> and
4 Ira Rosen <irar@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "dumpfile.h"
26 #include "tm.h"
27 #include "tree.h"
28 #include "stor-layout.h"
29 #include "basic-block.h"
30 #include "gimple-pretty-print.h"
31 #include "tree-ssa-alias.h"
32 #include "internal-fn.h"
33 #include "gimple-expr.h"
34 #include "is-a.h"
35 #include "gimple.h"
36 #include "gimplify.h"
37 #include "gimple-iterator.h"
38 #include "gimplify-me.h"
39 #include "gimple-ssa.h"
40 #include "tree-phinodes.h"
41 #include "ssa-iterators.h"
42 #include "stringpool.h"
43 #include "tree-ssanames.h"
44 #include "tree-ssa-loop-ivopts.h"
45 #include "tree-ssa-loop-manip.h"
46 #include "tree-ssa-loop-niter.h"
47 #include "tree-pass.h"
48 #include "cfgloop.h"
49 #include "expr.h"
50 #include "recog.h"
51 #include "optabs.h"
52 #include "params.h"
53 #include "diagnostic-core.h"
54 #include "tree-chrec.h"
55 #include "tree-scalar-evolution.h"
56 #include "tree-vectorizer.h"
57 #include "target.h"
59 /* Loop Vectorization Pass.
61 This pass tries to vectorize loops.
63 For example, the vectorizer transforms the following simple loop:
65 short a[N]; short b[N]; short c[N]; int i;
67 for (i=0; i<N; i++){
68 a[i] = b[i] + c[i];
71 as if it was manually vectorized by rewriting the source code into:
73 typedef int __attribute__((mode(V8HI))) v8hi;
74 short a[N]; short b[N]; short c[N]; int i;
75 v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
76 v8hi va, vb, vc;
78 for (i=0; i<N/8; i++){
79 vb = pb[i];
80 vc = pc[i];
81 va = vb + vc;
82 pa[i] = va;
85 The main entry to this pass is vectorize_loops(), in which
86 the vectorizer applies a set of analyses on a given set of loops,
87 followed by the actual vectorization transformation for the loops that
88 had successfully passed the analysis phase.
89 Throughout this pass we make a distinction between two types of
90 data: scalars (which are represented by SSA_NAMES), and memory references
91 ("data-refs"). These two types of data require different handling both
92 during analysis and transformation. The types of data-refs that the
93 vectorizer currently supports are ARRAY_REFS which base is an array DECL
94 (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
95 accesses are required to have a simple (consecutive) access pattern.
97 Analysis phase:
98 ===============
99 The driver for the analysis phase is vect_analyze_loop().
100 It applies a set of analyses, some of which rely on the scalar evolution
101 analyzer (scev) developed by Sebastian Pop.
103 During the analysis phase the vectorizer records some information
104 per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
105 loop, as well as general information about the loop as a whole, which is
106 recorded in a "loop_vec_info" struct attached to each loop.
108 Transformation phase:
109 =====================
110 The loop transformation phase scans all the stmts in the loop, and
111 creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
112 the loop that needs to be vectorized. It inserts the vector code sequence
113 just before the scalar stmt S, and records a pointer to the vector code
114 in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
115 attached to S). This pointer will be used for the vectorization of following
116 stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
117 otherwise, we rely on dead code elimination for removing it.
119 For example, say stmt S1 was vectorized into stmt VS1:
121 VS1: vb = px[i];
122 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
123 S2: a = b;
125 To vectorize stmt S2, the vectorizer first finds the stmt that defines
126 the operand 'b' (S1), and gets the relevant vector def 'vb' from the
127 vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
128 resulting sequence would be:
130 VS1: vb = px[i];
131 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
132 VS2: va = vb;
133 S2: a = b; STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
135 Operands that are not SSA_NAMEs, are data-refs that appear in
136 load/store operations (like 'x[i]' in S1), and are handled differently.
138 Target modeling:
139 =================
140 Currently the only target specific information that is used is the
141 size of the vector (in bytes) - "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD".
142 Targets that can support different sizes of vectors, for now will need
143 to specify one value for "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD". More
144 flexibility will be added in the future.
146 Since we only vectorize operations which vector form can be
147 expressed using existing tree codes, to verify that an operation is
148 supported, the vectorizer checks the relevant optab at the relevant
149 machine_mode (e.g, optab_handler (add_optab, V8HImode)). If
150 the value found is CODE_FOR_nothing, then there's no target support, and
151 we can't vectorize the stmt.
153 For additional information on this project see:
154 http://gcc.gnu.org/projects/tree-ssa/vectorization.html
157 static void vect_estimate_min_profitable_iters (loop_vec_info, int *, int *);
159 /* Function vect_determine_vectorization_factor
161 Determine the vectorization factor (VF). VF is the number of data elements
162 that are operated upon in parallel in a single iteration of the vectorized
163 loop. For example, when vectorizing a loop that operates on 4byte elements,
164 on a target with vector size (VS) 16byte, the VF is set to 4, since 4
165 elements can fit in a single vector register.
167 We currently support vectorization of loops in which all types operated upon
168 are of the same size. Therefore this function currently sets VF according to
169 the size of the types operated upon, and fails if there are multiple sizes
170 in the loop.
172 VF is also the factor by which the loop iterations are strip-mined, e.g.:
173 original loop:
174 for (i=0; i<N; i++){
175 a[i] = b[i] + c[i];
178 vectorized loop:
179 for (i=0; i<N; i+=VF){
180 a[i:VF] = b[i:VF] + c[i:VF];
184 static bool
185 vect_determine_vectorization_factor (loop_vec_info loop_vinfo)
187 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
188 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
189 int nbbs = loop->num_nodes;
190 gimple_stmt_iterator si;
191 unsigned int vectorization_factor = 0;
192 tree scalar_type;
193 gimple phi;
194 tree vectype;
195 unsigned int nunits;
196 stmt_vec_info stmt_info;
197 int i;
198 HOST_WIDE_INT dummy;
199 gimple stmt, pattern_stmt = NULL;
200 gimple_seq pattern_def_seq = NULL;
201 gimple_stmt_iterator pattern_def_si = gsi_none ();
202 bool analyze_pattern_stmt = false;
204 if (dump_enabled_p ())
205 dump_printf_loc (MSG_NOTE, vect_location,
206 "=== vect_determine_vectorization_factor ===\n");
208 for (i = 0; i < nbbs; i++)
210 basic_block bb = bbs[i];
212 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
214 phi = gsi_stmt (si);
215 stmt_info = vinfo_for_stmt (phi);
216 if (dump_enabled_p ())
218 dump_printf_loc (MSG_NOTE, vect_location, "==> examining phi: ");
219 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
220 dump_printf (MSG_NOTE, "\n");
223 gcc_assert (stmt_info);
225 if (STMT_VINFO_RELEVANT_P (stmt_info))
227 gcc_assert (!STMT_VINFO_VECTYPE (stmt_info));
228 scalar_type = TREE_TYPE (PHI_RESULT (phi));
230 if (dump_enabled_p ())
232 dump_printf_loc (MSG_NOTE, vect_location,
233 "get vectype for scalar type: ");
234 dump_generic_expr (MSG_NOTE, TDF_SLIM, scalar_type);
235 dump_printf (MSG_NOTE, "\n");
238 vectype = get_vectype_for_scalar_type (scalar_type);
239 if (!vectype)
241 if (dump_enabled_p ())
243 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
244 "not vectorized: unsupported "
245 "data-type ");
246 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
247 scalar_type);
248 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
250 return false;
252 STMT_VINFO_VECTYPE (stmt_info) = vectype;
254 if (dump_enabled_p ())
256 dump_printf_loc (MSG_NOTE, vect_location, "vectype: ");
257 dump_generic_expr (MSG_NOTE, TDF_SLIM, vectype);
258 dump_printf (MSG_NOTE, "\n");
261 nunits = TYPE_VECTOR_SUBPARTS (vectype);
262 if (dump_enabled_p ())
263 dump_printf_loc (MSG_NOTE, vect_location, "nunits = %d\n",
264 nunits);
266 if (!vectorization_factor
267 || (nunits > vectorization_factor))
268 vectorization_factor = nunits;
272 for (si = gsi_start_bb (bb); !gsi_end_p (si) || analyze_pattern_stmt;)
274 tree vf_vectype;
276 if (analyze_pattern_stmt)
277 stmt = pattern_stmt;
278 else
279 stmt = gsi_stmt (si);
281 stmt_info = vinfo_for_stmt (stmt);
283 if (dump_enabled_p ())
285 dump_printf_loc (MSG_NOTE, vect_location,
286 "==> examining statement: ");
287 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
288 dump_printf (MSG_NOTE, "\n");
291 gcc_assert (stmt_info);
293 /* Skip stmts which do not need to be vectorized. */
294 if ((!STMT_VINFO_RELEVANT_P (stmt_info)
295 && !STMT_VINFO_LIVE_P (stmt_info))
296 || gimple_clobber_p (stmt))
298 if (STMT_VINFO_IN_PATTERN_P (stmt_info)
299 && (pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info))
300 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt))
301 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt))))
303 stmt = pattern_stmt;
304 stmt_info = vinfo_for_stmt (pattern_stmt);
305 if (dump_enabled_p ())
307 dump_printf_loc (MSG_NOTE, vect_location,
308 "==> examining pattern statement: ");
309 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
310 dump_printf (MSG_NOTE, "\n");
313 else
315 if (dump_enabled_p ())
316 dump_printf_loc (MSG_NOTE, vect_location, "skip.\n");
317 gsi_next (&si);
318 continue;
321 else if (STMT_VINFO_IN_PATTERN_P (stmt_info)
322 && (pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info))
323 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt))
324 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt))))
325 analyze_pattern_stmt = true;
327 /* If a pattern statement has def stmts, analyze them too. */
328 if (is_pattern_stmt_p (stmt_info))
330 if (pattern_def_seq == NULL)
332 pattern_def_seq = STMT_VINFO_PATTERN_DEF_SEQ (stmt_info);
333 pattern_def_si = gsi_start (pattern_def_seq);
335 else if (!gsi_end_p (pattern_def_si))
336 gsi_next (&pattern_def_si);
337 if (pattern_def_seq != NULL)
339 gimple pattern_def_stmt = NULL;
340 stmt_vec_info pattern_def_stmt_info = NULL;
342 while (!gsi_end_p (pattern_def_si))
344 pattern_def_stmt = gsi_stmt (pattern_def_si);
345 pattern_def_stmt_info
346 = vinfo_for_stmt (pattern_def_stmt);
347 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info)
348 || STMT_VINFO_LIVE_P (pattern_def_stmt_info))
349 break;
350 gsi_next (&pattern_def_si);
353 if (!gsi_end_p (pattern_def_si))
355 if (dump_enabled_p ())
357 dump_printf_loc (MSG_NOTE, vect_location,
358 "==> examining pattern def stmt: ");
359 dump_gimple_stmt (MSG_NOTE, TDF_SLIM,
360 pattern_def_stmt, 0);
361 dump_printf (MSG_NOTE, "\n");
364 stmt = pattern_def_stmt;
365 stmt_info = pattern_def_stmt_info;
367 else
369 pattern_def_si = gsi_none ();
370 analyze_pattern_stmt = false;
373 else
374 analyze_pattern_stmt = false;
377 if (gimple_get_lhs (stmt) == NULL_TREE
378 /* MASK_STORE has no lhs, but is ok. */
379 && (!is_gimple_call (stmt)
380 || !gimple_call_internal_p (stmt)
381 || gimple_call_internal_fn (stmt) != IFN_MASK_STORE))
383 if (is_gimple_call (stmt))
385 /* Ignore calls with no lhs. These must be calls to
386 #pragma omp simd functions, and what vectorization factor
387 it really needs can't be determined until
388 vectorizable_simd_clone_call. */
389 if (!analyze_pattern_stmt && gsi_end_p (pattern_def_si))
391 pattern_def_seq = NULL;
392 gsi_next (&si);
394 continue;
396 if (dump_enabled_p ())
398 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
399 "not vectorized: irregular stmt.");
400 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt,
402 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
404 return false;
407 if (VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt))))
409 if (dump_enabled_p ())
411 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
412 "not vectorized: vector stmt in loop:");
413 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
414 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
416 return false;
419 if (STMT_VINFO_VECTYPE (stmt_info))
421 /* The only case when a vectype had been already set is for stmts
422 that contain a dataref, or for "pattern-stmts" (stmts
423 generated by the vectorizer to represent/replace a certain
424 idiom). */
425 gcc_assert (STMT_VINFO_DATA_REF (stmt_info)
426 || is_pattern_stmt_p (stmt_info)
427 || !gsi_end_p (pattern_def_si));
428 vectype = STMT_VINFO_VECTYPE (stmt_info);
430 else
432 gcc_assert (!STMT_VINFO_DATA_REF (stmt_info));
433 if (is_gimple_call (stmt)
434 && gimple_call_internal_p (stmt)
435 && gimple_call_internal_fn (stmt) == IFN_MASK_STORE)
436 scalar_type = TREE_TYPE (gimple_call_arg (stmt, 3));
437 else
438 scalar_type = TREE_TYPE (gimple_get_lhs (stmt));
439 if (dump_enabled_p ())
441 dump_printf_loc (MSG_NOTE, vect_location,
442 "get vectype for scalar type: ");
443 dump_generic_expr (MSG_NOTE, TDF_SLIM, scalar_type);
444 dump_printf (MSG_NOTE, "\n");
446 vectype = get_vectype_for_scalar_type (scalar_type);
447 if (!vectype)
449 if (dump_enabled_p ())
451 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
452 "not vectorized: unsupported "
453 "data-type ");
454 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
455 scalar_type);
456 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
458 return false;
461 STMT_VINFO_VECTYPE (stmt_info) = vectype;
463 if (dump_enabled_p ())
465 dump_printf_loc (MSG_NOTE, vect_location, "vectype: ");
466 dump_generic_expr (MSG_NOTE, TDF_SLIM, vectype);
467 dump_printf (MSG_NOTE, "\n");
471 /* The vectorization factor is according to the smallest
472 scalar type (or the largest vector size, but we only
473 support one vector size per loop). */
474 scalar_type = vect_get_smallest_scalar_type (stmt, &dummy,
475 &dummy);
476 if (dump_enabled_p ())
478 dump_printf_loc (MSG_NOTE, vect_location,
479 "get vectype for scalar type: ");
480 dump_generic_expr (MSG_NOTE, TDF_SLIM, scalar_type);
481 dump_printf (MSG_NOTE, "\n");
483 vf_vectype = get_vectype_for_scalar_type (scalar_type);
484 if (!vf_vectype)
486 if (dump_enabled_p ())
488 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
489 "not vectorized: unsupported data-type ");
490 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
491 scalar_type);
492 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
494 return false;
497 if ((GET_MODE_SIZE (TYPE_MODE (vectype))
498 != GET_MODE_SIZE (TYPE_MODE (vf_vectype))))
500 if (dump_enabled_p ())
502 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
503 "not vectorized: different sized vector "
504 "types in statement, ");
505 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
506 vectype);
507 dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
508 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
509 vf_vectype);
510 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
512 return false;
515 if (dump_enabled_p ())
517 dump_printf_loc (MSG_NOTE, vect_location, "vectype: ");
518 dump_generic_expr (MSG_NOTE, TDF_SLIM, vf_vectype);
519 dump_printf (MSG_NOTE, "\n");
522 nunits = TYPE_VECTOR_SUBPARTS (vf_vectype);
523 if (dump_enabled_p ())
524 dump_printf_loc (MSG_NOTE, vect_location, "nunits = %d\n", nunits);
525 if (!vectorization_factor
526 || (nunits > vectorization_factor))
527 vectorization_factor = nunits;
529 if (!analyze_pattern_stmt && gsi_end_p (pattern_def_si))
531 pattern_def_seq = NULL;
532 gsi_next (&si);
537 /* TODO: Analyze cost. Decide if worth while to vectorize. */
538 if (dump_enabled_p ())
539 dump_printf_loc (MSG_NOTE, vect_location, "vectorization factor = %d\n",
540 vectorization_factor);
541 if (vectorization_factor <= 1)
543 if (dump_enabled_p ())
544 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
545 "not vectorized: unsupported data-type\n");
546 return false;
548 LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
550 return true;
554 /* Function vect_is_simple_iv_evolution.
556 FORNOW: A simple evolution of an induction variables in the loop is
557 considered a polynomial evolution. */
559 static bool
560 vect_is_simple_iv_evolution (unsigned loop_nb, tree access_fn, tree * init,
561 tree * step)
563 tree init_expr;
564 tree step_expr;
565 tree evolution_part = evolution_part_in_loop_num (access_fn, loop_nb);
566 basic_block bb;
568 /* When there is no evolution in this loop, the evolution function
569 is not "simple". */
570 if (evolution_part == NULL_TREE)
571 return false;
573 /* When the evolution is a polynomial of degree >= 2
574 the evolution function is not "simple". */
575 if (tree_is_chrec (evolution_part))
576 return false;
578 step_expr = evolution_part;
579 init_expr = unshare_expr (initial_condition_in_loop_num (access_fn, loop_nb));
581 if (dump_enabled_p ())
583 dump_printf_loc (MSG_NOTE, vect_location, "step: ");
584 dump_generic_expr (MSG_NOTE, TDF_SLIM, step_expr);
585 dump_printf (MSG_NOTE, ", init: ");
586 dump_generic_expr (MSG_NOTE, TDF_SLIM, init_expr);
587 dump_printf (MSG_NOTE, "\n");
590 *init = init_expr;
591 *step = step_expr;
593 if (TREE_CODE (step_expr) != INTEGER_CST
594 && (TREE_CODE (step_expr) != SSA_NAME
595 || ((bb = gimple_bb (SSA_NAME_DEF_STMT (step_expr)))
596 && flow_bb_inside_loop_p (get_loop (cfun, loop_nb), bb))
597 || (!INTEGRAL_TYPE_P (TREE_TYPE (step_expr))
598 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr))
599 || !flag_associative_math)))
600 && (TREE_CODE (step_expr) != REAL_CST
601 || !flag_associative_math))
603 if (dump_enabled_p ())
604 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
605 "step unknown.\n");
606 return false;
609 return true;
612 /* Function vect_analyze_scalar_cycles_1.
614 Examine the cross iteration def-use cycles of scalar variables
615 in LOOP. LOOP_VINFO represents the loop that is now being
616 considered for vectorization (can be LOOP, or an outer-loop
617 enclosing LOOP). */
619 static void
620 vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo, struct loop *loop)
622 basic_block bb = loop->header;
623 tree init, step;
624 auto_vec<gimple, 64> worklist;
625 gimple_stmt_iterator gsi;
626 bool double_reduc;
628 if (dump_enabled_p ())
629 dump_printf_loc (MSG_NOTE, vect_location,
630 "=== vect_analyze_scalar_cycles ===\n");
632 /* First - identify all inductions. Reduction detection assumes that all the
633 inductions have been identified, therefore, this order must not be
634 changed. */
635 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
637 gimple phi = gsi_stmt (gsi);
638 tree access_fn = NULL;
639 tree def = PHI_RESULT (phi);
640 stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
642 if (dump_enabled_p ())
644 dump_printf_loc (MSG_NOTE, vect_location, "Analyze phi: ");
645 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
646 dump_printf (MSG_NOTE, "\n");
649 /* Skip virtual phi's. The data dependences that are associated with
650 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
651 if (virtual_operand_p (def))
652 continue;
654 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_unknown_def_type;
656 /* Analyze the evolution function. */
657 access_fn = analyze_scalar_evolution (loop, def);
658 if (access_fn)
660 STRIP_NOPS (access_fn);
661 if (dump_enabled_p ())
663 dump_printf_loc (MSG_NOTE, vect_location,
664 "Access function of PHI: ");
665 dump_generic_expr (MSG_NOTE, TDF_SLIM, access_fn);
666 dump_printf (MSG_NOTE, "\n");
668 STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo)
669 = evolution_part_in_loop_num (access_fn, loop->num);
672 if (!access_fn
673 || !vect_is_simple_iv_evolution (loop->num, access_fn, &init, &step)
674 || (LOOP_VINFO_LOOP (loop_vinfo) != loop
675 && TREE_CODE (step) != INTEGER_CST))
677 worklist.safe_push (phi);
678 continue;
681 gcc_assert (STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo) != NULL_TREE);
683 if (dump_enabled_p ())
684 dump_printf_loc (MSG_NOTE, vect_location, "Detected induction.\n");
685 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def;
689 /* Second - identify all reductions and nested cycles. */
690 while (worklist.length () > 0)
692 gimple phi = worklist.pop ();
693 tree def = PHI_RESULT (phi);
694 stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
695 gimple reduc_stmt;
696 bool nested_cycle;
698 if (dump_enabled_p ())
700 dump_printf_loc (MSG_NOTE, vect_location, "Analyze phi: ");
701 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
702 dump_printf (MSG_NOTE, "\n");
705 gcc_assert (!virtual_operand_p (def)
706 && STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_unknown_def_type);
708 nested_cycle = (loop != LOOP_VINFO_LOOP (loop_vinfo));
709 reduc_stmt = vect_force_simple_reduction (loop_vinfo, phi, !nested_cycle,
710 &double_reduc);
711 if (reduc_stmt)
713 if (double_reduc)
715 if (dump_enabled_p ())
716 dump_printf_loc (MSG_NOTE, vect_location,
717 "Detected double reduction.\n");
719 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_double_reduction_def;
720 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
721 vect_double_reduction_def;
723 else
725 if (nested_cycle)
727 if (dump_enabled_p ())
728 dump_printf_loc (MSG_NOTE, vect_location,
729 "Detected vectorizable nested cycle.\n");
731 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_nested_cycle;
732 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
733 vect_nested_cycle;
735 else
737 if (dump_enabled_p ())
738 dump_printf_loc (MSG_NOTE, vect_location,
739 "Detected reduction.\n");
741 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_reduction_def;
742 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
743 vect_reduction_def;
744 /* Store the reduction cycles for possible vectorization in
745 loop-aware SLP. */
746 LOOP_VINFO_REDUCTIONS (loop_vinfo).safe_push (reduc_stmt);
750 else
751 if (dump_enabled_p ())
752 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
753 "Unknown def-use cycle pattern.\n");
758 /* Function vect_analyze_scalar_cycles.
760 Examine the cross iteration def-use cycles of scalar variables, by
761 analyzing the loop-header PHIs of scalar variables. Classify each
762 cycle as one of the following: invariant, induction, reduction, unknown.
763 We do that for the loop represented by LOOP_VINFO, and also to its
764 inner-loop, if exists.
765 Examples for scalar cycles:
767 Example1: reduction:
769 loop1:
770 for (i=0; i<N; i++)
771 sum += a[i];
773 Example2: induction:
775 loop2:
776 for (i=0; i<N; i++)
777 a[i] = i; */
779 static void
780 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
782 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
784 vect_analyze_scalar_cycles_1 (loop_vinfo, loop);
786 /* When vectorizing an outer-loop, the inner-loop is executed sequentially.
787 Reductions in such inner-loop therefore have different properties than
788 the reductions in the nest that gets vectorized:
789 1. When vectorized, they are executed in the same order as in the original
790 scalar loop, so we can't change the order of computation when
791 vectorizing them.
792 2. FIXME: Inner-loop reductions can be used in the inner-loop, so the
793 current checks are too strict. */
795 if (loop->inner)
796 vect_analyze_scalar_cycles_1 (loop_vinfo, loop->inner);
800 /* Function vect_get_loop_niters.
802 Determine how many iterations the loop is executed and place it
803 in NUMBER_OF_ITERATIONS. Place the number of latch iterations
804 in NUMBER_OF_ITERATIONSM1.
806 Return the loop exit condition. */
808 static gimple
809 vect_get_loop_niters (struct loop *loop, tree *number_of_iterations,
810 tree *number_of_iterationsm1)
812 tree niters;
814 if (dump_enabled_p ())
815 dump_printf_loc (MSG_NOTE, vect_location,
816 "=== get_loop_niters ===\n");
818 niters = number_of_latch_executions (loop);
819 *number_of_iterationsm1 = niters;
821 /* We want the number of loop header executions which is the number
822 of latch executions plus one.
823 ??? For UINT_MAX latch executions this number overflows to zero
824 for loops like do { n++; } while (n != 0); */
825 if (niters && !chrec_contains_undetermined (niters))
826 niters = fold_build2 (PLUS_EXPR, TREE_TYPE (niters), unshare_expr (niters),
827 build_int_cst (TREE_TYPE (niters), 1));
828 *number_of_iterations = niters;
830 return get_loop_exit_condition (loop);
834 /* Function bb_in_loop_p
836 Used as predicate for dfs order traversal of the loop bbs. */
838 static bool
839 bb_in_loop_p (const_basic_block bb, const void *data)
841 const struct loop *const loop = (const struct loop *)data;
842 if (flow_bb_inside_loop_p (loop, bb))
843 return true;
844 return false;
848 /* Function new_loop_vec_info.
850 Create and initialize a new loop_vec_info struct for LOOP, as well as
851 stmt_vec_info structs for all the stmts in LOOP. */
853 static loop_vec_info
854 new_loop_vec_info (struct loop *loop)
856 loop_vec_info res;
857 basic_block *bbs;
858 gimple_stmt_iterator si;
859 unsigned int i, nbbs;
861 res = (loop_vec_info) xcalloc (1, sizeof (struct _loop_vec_info));
862 LOOP_VINFO_LOOP (res) = loop;
864 bbs = get_loop_body (loop);
866 /* Create/Update stmt_info for all stmts in the loop. */
867 for (i = 0; i < loop->num_nodes; i++)
869 basic_block bb = bbs[i];
871 /* BBs in a nested inner-loop will have been already processed (because
872 we will have called vect_analyze_loop_form for any nested inner-loop).
873 Therefore, for stmts in an inner-loop we just want to update the
874 STMT_VINFO_LOOP_VINFO field of their stmt_info to point to the new
875 loop_info of the outer-loop we are currently considering to vectorize
876 (instead of the loop_info of the inner-loop).
877 For stmts in other BBs we need to create a stmt_info from scratch. */
878 if (bb->loop_father != loop)
880 /* Inner-loop bb. */
881 gcc_assert (loop->inner && bb->loop_father == loop->inner);
882 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
884 gimple phi = gsi_stmt (si);
885 stmt_vec_info stmt_info = vinfo_for_stmt (phi);
886 loop_vec_info inner_loop_vinfo =
887 STMT_VINFO_LOOP_VINFO (stmt_info);
888 gcc_assert (loop->inner == LOOP_VINFO_LOOP (inner_loop_vinfo));
889 STMT_VINFO_LOOP_VINFO (stmt_info) = res;
891 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
893 gimple stmt = gsi_stmt (si);
894 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
895 loop_vec_info inner_loop_vinfo =
896 STMT_VINFO_LOOP_VINFO (stmt_info);
897 gcc_assert (loop->inner == LOOP_VINFO_LOOP (inner_loop_vinfo));
898 STMT_VINFO_LOOP_VINFO (stmt_info) = res;
901 else
903 /* bb in current nest. */
904 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
906 gimple phi = gsi_stmt (si);
907 gimple_set_uid (phi, 0);
908 set_vinfo_for_stmt (phi, new_stmt_vec_info (phi, res, NULL));
911 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
913 gimple stmt = gsi_stmt (si);
914 gimple_set_uid (stmt, 0);
915 set_vinfo_for_stmt (stmt, new_stmt_vec_info (stmt, res, NULL));
920 /* CHECKME: We want to visit all BBs before their successors (except for
921 latch blocks, for which this assertion wouldn't hold). In the simple
922 case of the loop forms we allow, a dfs order of the BBs would the same
923 as reversed postorder traversal, so we are safe. */
925 free (bbs);
926 bbs = XCNEWVEC (basic_block, loop->num_nodes);
927 nbbs = dfs_enumerate_from (loop->header, 0, bb_in_loop_p,
928 bbs, loop->num_nodes, loop);
929 gcc_assert (nbbs == loop->num_nodes);
931 LOOP_VINFO_BBS (res) = bbs;
932 LOOP_VINFO_NITERSM1 (res) = NULL;
933 LOOP_VINFO_NITERS (res) = NULL;
934 LOOP_VINFO_NITERS_UNCHANGED (res) = NULL;
935 LOOP_VINFO_COST_MODEL_MIN_ITERS (res) = 0;
936 LOOP_VINFO_COST_MODEL_THRESHOLD (res) = 0;
937 LOOP_VINFO_VECTORIZABLE_P (res) = 0;
938 LOOP_VINFO_PEELING_FOR_ALIGNMENT (res) = 0;
939 LOOP_VINFO_VECT_FACTOR (res) = 0;
940 LOOP_VINFO_LOOP_NEST (res).create (3);
941 LOOP_VINFO_DATAREFS (res).create (10);
942 LOOP_VINFO_DDRS (res).create (10 * 10);
943 LOOP_VINFO_UNALIGNED_DR (res) = NULL;
944 LOOP_VINFO_MAY_MISALIGN_STMTS (res).create (
945 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS));
946 LOOP_VINFO_MAY_ALIAS_DDRS (res).create (
947 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS));
948 LOOP_VINFO_GROUPED_STORES (res).create (10);
949 LOOP_VINFO_REDUCTIONS (res).create (10);
950 LOOP_VINFO_REDUCTION_CHAINS (res).create (10);
951 LOOP_VINFO_SLP_INSTANCES (res).create (10);
952 LOOP_VINFO_SLP_UNROLLING_FACTOR (res) = 1;
953 LOOP_VINFO_TARGET_COST_DATA (res) = init_cost (loop);
954 LOOP_VINFO_PEELING_FOR_GAPS (res) = false;
955 LOOP_VINFO_PEELING_FOR_NITER (res) = false;
956 LOOP_VINFO_OPERANDS_SWAPPED (res) = false;
958 return res;
962 /* Function destroy_loop_vec_info.
964 Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
965 stmts in the loop. */
967 void
968 destroy_loop_vec_info (loop_vec_info loop_vinfo, bool clean_stmts)
970 struct loop *loop;
971 basic_block *bbs;
972 int nbbs;
973 gimple_stmt_iterator si;
974 int j;
975 vec<slp_instance> slp_instances;
976 slp_instance instance;
977 bool swapped;
979 if (!loop_vinfo)
980 return;
982 loop = LOOP_VINFO_LOOP (loop_vinfo);
984 bbs = LOOP_VINFO_BBS (loop_vinfo);
985 nbbs = clean_stmts ? loop->num_nodes : 0;
986 swapped = LOOP_VINFO_OPERANDS_SWAPPED (loop_vinfo);
988 for (j = 0; j < nbbs; j++)
990 basic_block bb = bbs[j];
991 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
992 free_stmt_vec_info (gsi_stmt (si));
994 for (si = gsi_start_bb (bb); !gsi_end_p (si); )
996 gimple stmt = gsi_stmt (si);
998 /* We may have broken canonical form by moving a constant
999 into RHS1 of a commutative op. Fix such occurrences. */
1000 if (swapped && is_gimple_assign (stmt))
1002 enum tree_code code = gimple_assign_rhs_code (stmt);
1004 if ((code == PLUS_EXPR
1005 || code == POINTER_PLUS_EXPR
1006 || code == MULT_EXPR)
1007 && CONSTANT_CLASS_P (gimple_assign_rhs1 (stmt)))
1008 swap_ssa_operands (stmt,
1009 gimple_assign_rhs1_ptr (stmt),
1010 gimple_assign_rhs2_ptr (stmt));
1013 /* Free stmt_vec_info. */
1014 free_stmt_vec_info (stmt);
1015 gsi_next (&si);
1019 free (LOOP_VINFO_BBS (loop_vinfo));
1020 vect_destroy_datarefs (loop_vinfo, NULL);
1021 free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo));
1022 LOOP_VINFO_LOOP_NEST (loop_vinfo).release ();
1023 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).release ();
1024 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo).release ();
1025 slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
1026 FOR_EACH_VEC_ELT (slp_instances, j, instance)
1027 vect_free_slp_instance (instance);
1029 LOOP_VINFO_SLP_INSTANCES (loop_vinfo).release ();
1030 LOOP_VINFO_GROUPED_STORES (loop_vinfo).release ();
1031 LOOP_VINFO_REDUCTIONS (loop_vinfo).release ();
1032 LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo).release ();
1034 delete LOOP_VINFO_PEELING_HTAB (loop_vinfo);
1035 LOOP_VINFO_PEELING_HTAB (loop_vinfo) = NULL;
1037 destroy_cost_data (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo));
1039 free (loop_vinfo);
1040 loop->aux = NULL;
1044 /* Function vect_analyze_loop_1.
1046 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1047 for it. The different analyses will record information in the
1048 loop_vec_info struct. This is a subset of the analyses applied in
1049 vect_analyze_loop, to be applied on an inner-loop nested in the loop
1050 that is now considered for (outer-loop) vectorization. */
1052 static loop_vec_info
1053 vect_analyze_loop_1 (struct loop *loop)
1055 loop_vec_info loop_vinfo;
1057 if (dump_enabled_p ())
1058 dump_printf_loc (MSG_NOTE, vect_location,
1059 "===== analyze_loop_nest_1 =====\n");
1061 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
1063 loop_vinfo = vect_analyze_loop_form (loop);
1064 if (!loop_vinfo)
1066 if (dump_enabled_p ())
1067 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1068 "bad inner-loop form.\n");
1069 return NULL;
1072 return loop_vinfo;
1076 /* Function vect_analyze_loop_form.
1078 Verify that certain CFG restrictions hold, including:
1079 - the loop has a pre-header
1080 - the loop has a single entry and exit
1081 - the loop exit condition is simple enough, and the number of iterations
1082 can be analyzed (a countable loop). */
1084 loop_vec_info
1085 vect_analyze_loop_form (struct loop *loop)
1087 loop_vec_info loop_vinfo;
1088 gimple loop_cond;
1089 tree number_of_iterations = NULL, number_of_iterationsm1 = NULL;
1090 loop_vec_info inner_loop_vinfo = NULL;
1092 if (dump_enabled_p ())
1093 dump_printf_loc (MSG_NOTE, vect_location,
1094 "=== vect_analyze_loop_form ===\n");
1096 /* Different restrictions apply when we are considering an inner-most loop,
1097 vs. an outer (nested) loop.
1098 (FORNOW. May want to relax some of these restrictions in the future). */
1100 if (!loop->inner)
1102 /* Inner-most loop. We currently require that the number of BBs is
1103 exactly 2 (the header and latch). Vectorizable inner-most loops
1104 look like this:
1106 (pre-header)
1108 header <--------+
1109 | | |
1110 | +--> latch --+
1112 (exit-bb) */
1114 if (loop->num_nodes != 2)
1116 if (dump_enabled_p ())
1117 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1118 "not vectorized: control flow in loop.\n");
1119 return NULL;
1122 if (empty_block_p (loop->header))
1124 if (dump_enabled_p ())
1125 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1126 "not vectorized: empty loop.\n");
1127 return NULL;
1130 else
1132 struct loop *innerloop = loop->inner;
1133 edge entryedge;
1135 /* Nested loop. We currently require that the loop is doubly-nested,
1136 contains a single inner loop, and the number of BBs is exactly 5.
1137 Vectorizable outer-loops look like this:
1139 (pre-header)
1141 header <---+
1143 inner-loop |
1145 tail ------+
1147 (exit-bb)
1149 The inner-loop has the properties expected of inner-most loops
1150 as described above. */
1152 if ((loop->inner)->inner || (loop->inner)->next)
1154 if (dump_enabled_p ())
1155 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1156 "not vectorized: multiple nested loops.\n");
1157 return NULL;
1160 /* Analyze the inner-loop. */
1161 inner_loop_vinfo = vect_analyze_loop_1 (loop->inner);
1162 if (!inner_loop_vinfo)
1164 if (dump_enabled_p ())
1165 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1166 "not vectorized: Bad inner loop.\n");
1167 return NULL;
1170 if (!expr_invariant_in_loop_p (loop,
1171 LOOP_VINFO_NITERS (inner_loop_vinfo)))
1173 if (dump_enabled_p ())
1174 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1175 "not vectorized: inner-loop count not"
1176 " invariant.\n");
1177 destroy_loop_vec_info (inner_loop_vinfo, true);
1178 return NULL;
1181 if (loop->num_nodes != 5)
1183 if (dump_enabled_p ())
1184 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1185 "not vectorized: control flow in loop.\n");
1186 destroy_loop_vec_info (inner_loop_vinfo, true);
1187 return NULL;
1190 gcc_assert (EDGE_COUNT (innerloop->header->preds) == 2);
1191 entryedge = EDGE_PRED (innerloop->header, 0);
1192 if (EDGE_PRED (innerloop->header, 0)->src == innerloop->latch)
1193 entryedge = EDGE_PRED (innerloop->header, 1);
1195 if (entryedge->src != loop->header
1196 || !single_exit (innerloop)
1197 || single_exit (innerloop)->dest != EDGE_PRED (loop->latch, 0)->src)
1199 if (dump_enabled_p ())
1200 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1201 "not vectorized: unsupported outerloop form.\n");
1202 destroy_loop_vec_info (inner_loop_vinfo, true);
1203 return NULL;
1206 if (dump_enabled_p ())
1207 dump_printf_loc (MSG_NOTE, vect_location,
1208 "Considering outer-loop vectorization.\n");
1211 if (!single_exit (loop)
1212 || EDGE_COUNT (loop->header->preds) != 2)
1214 if (dump_enabled_p ())
1216 if (!single_exit (loop))
1217 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1218 "not vectorized: multiple exits.\n");
1219 else if (EDGE_COUNT (loop->header->preds) != 2)
1220 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1221 "not vectorized: too many incoming edges.\n");
1223 if (inner_loop_vinfo)
1224 destroy_loop_vec_info (inner_loop_vinfo, true);
1225 return NULL;
1228 /* We assume that the loop exit condition is at the end of the loop. i.e,
1229 that the loop is represented as a do-while (with a proper if-guard
1230 before the loop if needed), where the loop header contains all the
1231 executable statements, and the latch is empty. */
1232 if (!empty_block_p (loop->latch)
1233 || !gimple_seq_empty_p (phi_nodes (loop->latch)))
1235 if (dump_enabled_p ())
1236 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1237 "not vectorized: latch block not empty.\n");
1238 if (inner_loop_vinfo)
1239 destroy_loop_vec_info (inner_loop_vinfo, true);
1240 return NULL;
1243 /* Make sure there exists a single-predecessor exit bb: */
1244 if (!single_pred_p (single_exit (loop)->dest))
1246 edge e = single_exit (loop);
1247 if (!(e->flags & EDGE_ABNORMAL))
1249 split_loop_exit_edge (e);
1250 if (dump_enabled_p ())
1251 dump_printf (MSG_NOTE, "split exit edge.\n");
1253 else
1255 if (dump_enabled_p ())
1256 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1257 "not vectorized: abnormal loop exit edge.\n");
1258 if (inner_loop_vinfo)
1259 destroy_loop_vec_info (inner_loop_vinfo, true);
1260 return NULL;
1264 loop_cond = vect_get_loop_niters (loop, &number_of_iterations,
1265 &number_of_iterationsm1);
1266 if (!loop_cond)
1268 if (dump_enabled_p ())
1269 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1270 "not vectorized: complicated exit condition.\n");
1271 if (inner_loop_vinfo)
1272 destroy_loop_vec_info (inner_loop_vinfo, true);
1273 return NULL;
1276 if (!number_of_iterations
1277 || chrec_contains_undetermined (number_of_iterations))
1279 if (dump_enabled_p ())
1280 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1281 "not vectorized: number of iterations cannot be "
1282 "computed.\n");
1283 if (inner_loop_vinfo)
1284 destroy_loop_vec_info (inner_loop_vinfo, true);
1285 return NULL;
1288 if (integer_zerop (number_of_iterations))
1290 if (dump_enabled_p ())
1291 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1292 "not vectorized: number of iterations = 0.\n");
1293 if (inner_loop_vinfo)
1294 destroy_loop_vec_info (inner_loop_vinfo, true);
1295 return NULL;
1298 loop_vinfo = new_loop_vec_info (loop);
1299 LOOP_VINFO_NITERSM1 (loop_vinfo) = number_of_iterationsm1;
1300 LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
1301 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo) = number_of_iterations;
1303 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
1305 if (dump_enabled_p ())
1307 dump_printf_loc (MSG_NOTE, vect_location,
1308 "Symbolic number of iterations is ");
1309 dump_generic_expr (MSG_NOTE, TDF_DETAILS, number_of_iterations);
1310 dump_printf (MSG_NOTE, "\n");
1314 STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond)) = loop_exit_ctrl_vec_info_type;
1316 /* CHECKME: May want to keep it around it in the future. */
1317 if (inner_loop_vinfo)
1318 destroy_loop_vec_info (inner_loop_vinfo, false);
1320 gcc_assert (!loop->aux);
1321 loop->aux = loop_vinfo;
1322 return loop_vinfo;
1326 /* Function vect_analyze_loop_operations.
1328 Scan the loop stmts and make sure they are all vectorizable. */
1330 static bool
1331 vect_analyze_loop_operations (loop_vec_info loop_vinfo, bool slp)
1333 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1334 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1335 int nbbs = loop->num_nodes;
1336 gimple_stmt_iterator si;
1337 unsigned int vectorization_factor = 0;
1338 int i;
1339 gimple phi;
1340 stmt_vec_info stmt_info;
1341 bool need_to_vectorize = false;
1342 int min_profitable_iters;
1343 int min_scalar_loop_bound;
1344 unsigned int th;
1345 bool only_slp_in_loop = true, ok;
1346 HOST_WIDE_INT max_niter;
1347 HOST_WIDE_INT estimated_niter;
1348 int min_profitable_estimate;
1350 if (dump_enabled_p ())
1351 dump_printf_loc (MSG_NOTE, vect_location,
1352 "=== vect_analyze_loop_operations ===\n");
1354 gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo));
1355 vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1356 if (slp)
1358 /* If all the stmts in the loop can be SLPed, we perform only SLP, and
1359 vectorization factor of the loop is the unrolling factor required by
1360 the SLP instances. If that unrolling factor is 1, we say, that we
1361 perform pure SLP on loop - cross iteration parallelism is not
1362 exploited. */
1363 for (i = 0; i < nbbs; i++)
1365 basic_block bb = bbs[i];
1366 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1368 gimple stmt = gsi_stmt (si);
1369 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1370 gcc_assert (stmt_info);
1371 if ((STMT_VINFO_RELEVANT_P (stmt_info)
1372 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info)))
1373 && !PURE_SLP_STMT (stmt_info))
1374 /* STMT needs both SLP and loop-based vectorization. */
1375 only_slp_in_loop = false;
1379 if (only_slp_in_loop)
1380 vectorization_factor = LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo);
1381 else
1382 vectorization_factor = least_common_multiple (vectorization_factor,
1383 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo));
1385 LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
1386 if (dump_enabled_p ())
1387 dump_printf_loc (MSG_NOTE, vect_location,
1388 "Updating vectorization factor to %d\n",
1389 vectorization_factor);
1392 for (i = 0; i < nbbs; i++)
1394 basic_block bb = bbs[i];
1396 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
1398 phi = gsi_stmt (si);
1399 ok = true;
1401 stmt_info = vinfo_for_stmt (phi);
1402 if (dump_enabled_p ())
1404 dump_printf_loc (MSG_NOTE, vect_location, "examining phi: ");
1405 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
1406 dump_printf (MSG_NOTE, "\n");
1409 /* Inner-loop loop-closed exit phi in outer-loop vectorization
1410 (i.e., a phi in the tail of the outer-loop). */
1411 if (! is_loop_header_bb_p (bb))
1413 /* FORNOW: we currently don't support the case that these phis
1414 are not used in the outerloop (unless it is double reduction,
1415 i.e., this phi is vect_reduction_def), cause this case
1416 requires to actually do something here. */
1417 if ((!STMT_VINFO_RELEVANT_P (stmt_info)
1418 || STMT_VINFO_LIVE_P (stmt_info))
1419 && STMT_VINFO_DEF_TYPE (stmt_info)
1420 != vect_double_reduction_def)
1422 if (dump_enabled_p ())
1423 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1424 "Unsupported loop-closed phi in "
1425 "outer-loop.\n");
1426 return false;
1429 /* If PHI is used in the outer loop, we check that its operand
1430 is defined in the inner loop. */
1431 if (STMT_VINFO_RELEVANT_P (stmt_info))
1433 tree phi_op;
1434 gimple op_def_stmt;
1436 if (gimple_phi_num_args (phi) != 1)
1437 return false;
1439 phi_op = PHI_ARG_DEF (phi, 0);
1440 if (TREE_CODE (phi_op) != SSA_NAME)
1441 return false;
1443 op_def_stmt = SSA_NAME_DEF_STMT (phi_op);
1444 if (gimple_nop_p (op_def_stmt)
1445 || !flow_bb_inside_loop_p (loop, gimple_bb (op_def_stmt))
1446 || !vinfo_for_stmt (op_def_stmt))
1447 return false;
1449 if (STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt))
1450 != vect_used_in_outer
1451 && STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt))
1452 != vect_used_in_outer_by_reduction)
1453 return false;
1456 continue;
1459 gcc_assert (stmt_info);
1461 if (STMT_VINFO_LIVE_P (stmt_info))
1463 /* FORNOW: not yet supported. */
1464 if (dump_enabled_p ())
1465 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1466 "not vectorized: value used after loop.\n");
1467 return false;
1470 if (STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_scope
1471 && STMT_VINFO_DEF_TYPE (stmt_info) != vect_induction_def)
1473 /* A scalar-dependence cycle that we don't support. */
1474 if (dump_enabled_p ())
1475 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1476 "not vectorized: scalar dependence cycle.\n");
1477 return false;
1480 if (STMT_VINFO_RELEVANT_P (stmt_info))
1482 need_to_vectorize = true;
1483 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def)
1484 ok = vectorizable_induction (phi, NULL, NULL);
1487 if (!ok)
1489 if (dump_enabled_p ())
1491 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1492 "not vectorized: relevant phi not "
1493 "supported: ");
1494 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, phi, 0);
1495 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
1497 return false;
1501 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1503 gimple stmt = gsi_stmt (si);
1504 if (!gimple_clobber_p (stmt)
1505 && !vect_analyze_stmt (stmt, &need_to_vectorize, NULL))
1506 return false;
1508 } /* bbs */
1510 /* All operations in the loop are either irrelevant (deal with loop
1511 control, or dead), or only used outside the loop and can be moved
1512 out of the loop (e.g. invariants, inductions). The loop can be
1513 optimized away by scalar optimizations. We're better off not
1514 touching this loop. */
1515 if (!need_to_vectorize)
1517 if (dump_enabled_p ())
1518 dump_printf_loc (MSG_NOTE, vect_location,
1519 "All the computation can be taken out of the loop.\n");
1520 if (dump_enabled_p ())
1521 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1522 "not vectorized: redundant loop. no profit to "
1523 "vectorize.\n");
1524 return false;
1527 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo) && dump_enabled_p ())
1528 dump_printf_loc (MSG_NOTE, vect_location,
1529 "vectorization_factor = %d, niters = "
1530 HOST_WIDE_INT_PRINT_DEC "\n", vectorization_factor,
1531 LOOP_VINFO_INT_NITERS (loop_vinfo));
1533 if ((LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1534 && (LOOP_VINFO_INT_NITERS (loop_vinfo) < vectorization_factor))
1535 || ((max_niter = max_stmt_executions_int (loop)) != -1
1536 && (unsigned HOST_WIDE_INT) max_niter < vectorization_factor))
1538 if (dump_enabled_p ())
1539 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1540 "not vectorized: iteration count too small.\n");
1541 if (dump_enabled_p ())
1542 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1543 "not vectorized: iteration count smaller than "
1544 "vectorization factor.\n");
1545 return false;
1548 /* Analyze cost. Decide if worth while to vectorize. */
1550 /* Once VF is set, SLP costs should be updated since the number of created
1551 vector stmts depends on VF. */
1552 vect_update_slp_costs_according_to_vf (loop_vinfo);
1554 vect_estimate_min_profitable_iters (loop_vinfo, &min_profitable_iters,
1555 &min_profitable_estimate);
1556 LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo) = min_profitable_iters;
1558 if (min_profitable_iters < 0)
1560 if (dump_enabled_p ())
1561 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1562 "not vectorized: vectorization not profitable.\n");
1563 if (dump_enabled_p ())
1564 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1565 "not vectorized: vector version will never be "
1566 "profitable.\n");
1567 return false;
1570 min_scalar_loop_bound = ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND)
1571 * vectorization_factor) - 1);
1574 /* Use the cost model only if it is more conservative than user specified
1575 threshold. */
1577 th = (unsigned) min_scalar_loop_bound;
1578 if (min_profitable_iters
1579 && (!min_scalar_loop_bound
1580 || min_profitable_iters > min_scalar_loop_bound))
1581 th = (unsigned) min_profitable_iters;
1583 LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo) = th;
1585 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1586 && LOOP_VINFO_INT_NITERS (loop_vinfo) <= th)
1588 if (dump_enabled_p ())
1589 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1590 "not vectorized: vectorization not profitable.\n");
1591 if (dump_enabled_p ())
1592 dump_printf_loc (MSG_NOTE, vect_location,
1593 "not vectorized: iteration count smaller than user "
1594 "specified loop bound parameter or minimum profitable "
1595 "iterations (whichever is more conservative).\n");
1596 return false;
1599 if ((estimated_niter = estimated_stmt_executions_int (loop)) != -1
1600 && ((unsigned HOST_WIDE_INT) estimated_niter
1601 <= MAX (th, (unsigned)min_profitable_estimate)))
1603 if (dump_enabled_p ())
1604 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1605 "not vectorized: estimated iteration count too "
1606 "small.\n");
1607 if (dump_enabled_p ())
1608 dump_printf_loc (MSG_NOTE, vect_location,
1609 "not vectorized: estimated iteration count smaller "
1610 "than specified loop bound parameter or minimum "
1611 "profitable iterations (whichever is more "
1612 "conservative).\n");
1613 return false;
1616 return true;
1620 /* Function vect_analyze_loop_2.
1622 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1623 for it. The different analyses will record information in the
1624 loop_vec_info struct. */
1625 static bool
1626 vect_analyze_loop_2 (loop_vec_info loop_vinfo)
1628 bool ok, slp = false;
1629 int max_vf = MAX_VECTORIZATION_FACTOR;
1630 int min_vf = 2;
1631 unsigned int th;
1632 unsigned int n_stmts = 0;
1634 /* Find all data references in the loop (which correspond to vdefs/vuses)
1635 and analyze their evolution in the loop. Also adjust the minimal
1636 vectorization factor according to the loads and stores.
1638 FORNOW: Handle only simple, array references, which
1639 alignment can be forced, and aligned pointer-references. */
1641 ok = vect_analyze_data_refs (loop_vinfo, NULL, &min_vf, &n_stmts);
1642 if (!ok)
1644 if (dump_enabled_p ())
1645 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1646 "bad data references.\n");
1647 return false;
1650 /* Analyze the access patterns of the data-refs in the loop (consecutive,
1651 complex, etc.). FORNOW: Only handle consecutive access pattern. */
1653 ok = vect_analyze_data_ref_accesses (loop_vinfo, NULL);
1654 if (!ok)
1656 if (dump_enabled_p ())
1657 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1658 "bad data access.\n");
1659 return false;
1662 /* Classify all cross-iteration scalar data-flow cycles.
1663 Cross-iteration cycles caused by virtual phis are analyzed separately. */
1665 vect_analyze_scalar_cycles (loop_vinfo);
1667 vect_pattern_recog (loop_vinfo, NULL);
1669 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
1671 ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
1672 if (!ok)
1674 if (dump_enabled_p ())
1675 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1676 "unexpected pattern.\n");
1677 return false;
1680 /* Analyze data dependences between the data-refs in the loop
1681 and adjust the maximum vectorization factor according to
1682 the dependences.
1683 FORNOW: fail at the first data dependence that we encounter. */
1685 ok = vect_analyze_data_ref_dependences (loop_vinfo, &max_vf);
1686 if (!ok
1687 || max_vf < min_vf)
1689 if (dump_enabled_p ())
1690 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1691 "bad data dependence.\n");
1692 return false;
1695 ok = vect_determine_vectorization_factor (loop_vinfo);
1696 if (!ok)
1698 if (dump_enabled_p ())
1699 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1700 "can't determine vectorization factor.\n");
1701 return false;
1703 if (max_vf < LOOP_VINFO_VECT_FACTOR (loop_vinfo))
1705 if (dump_enabled_p ())
1706 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1707 "bad data dependence.\n");
1708 return false;
1711 /* Analyze the alignment of the data-refs in the loop.
1712 Fail if a data reference is found that cannot be vectorized. */
1714 ok = vect_analyze_data_refs_alignment (loop_vinfo, NULL);
1715 if (!ok)
1717 if (dump_enabled_p ())
1718 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1719 "bad data alignment.\n");
1720 return false;
1723 /* Prune the list of ddrs to be tested at run-time by versioning for alias.
1724 It is important to call pruning after vect_analyze_data_ref_accesses,
1725 since we use grouping information gathered by interleaving analysis. */
1726 ok = vect_prune_runtime_alias_test_list (loop_vinfo);
1727 if (!ok)
1729 if (dump_enabled_p ())
1730 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1731 "number of versioning for alias "
1732 "run-time tests exceeds %d "
1733 "(--param vect-max-version-for-alias-checks)\n",
1734 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS));
1735 return false;
1738 /* This pass will decide on using loop versioning and/or loop peeling in
1739 order to enhance the alignment of data references in the loop. */
1741 ok = vect_enhance_data_refs_alignment (loop_vinfo);
1742 if (!ok)
1744 if (dump_enabled_p ())
1745 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1746 "bad data alignment.\n");
1747 return false;
1750 /* Check the SLP opportunities in the loop, analyze and build SLP trees. */
1751 ok = vect_analyze_slp (loop_vinfo, NULL, n_stmts);
1752 if (ok)
1754 /* Decide which possible SLP instances to SLP. */
1755 slp = vect_make_slp_decision (loop_vinfo);
1757 /* Find stmts that need to be both vectorized and SLPed. */
1758 vect_detect_hybrid_slp (loop_vinfo);
1760 else
1761 return false;
1763 /* Scan all the operations in the loop and make sure they are
1764 vectorizable. */
1766 ok = vect_analyze_loop_operations (loop_vinfo, slp);
1767 if (!ok)
1769 if (dump_enabled_p ())
1770 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1771 "bad operation or unsupported loop bound.\n");
1772 return false;
1775 /* Decide whether we need to create an epilogue loop to handle
1776 remaining scalar iterations. */
1777 th = ((LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo) + 1)
1778 / LOOP_VINFO_VECT_FACTOR (loop_vinfo))
1779 * LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1781 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1782 && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) > 0)
1784 if (ctz_hwi (LOOP_VINFO_INT_NITERS (loop_vinfo)
1785 - LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo))
1786 < exact_log2 (LOOP_VINFO_VECT_FACTOR (loop_vinfo)))
1787 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo) = true;
1789 else if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo)
1790 || (tree_ctz (LOOP_VINFO_NITERS (loop_vinfo))
1791 < (unsigned)exact_log2 (LOOP_VINFO_VECT_FACTOR (loop_vinfo))
1792 /* In case of versioning, check if the maximum number of
1793 iterations is greater than th. If they are identical,
1794 the epilogue is unnecessary. */
1795 && ((!LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo)
1796 && !LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo))
1797 || (unsigned HOST_WIDE_INT)max_stmt_executions_int
1798 (LOOP_VINFO_LOOP (loop_vinfo)) > th)))
1799 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo) = true;
1801 /* If an epilogue loop is required make sure we can create one. */
1802 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo)
1803 || LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo))
1805 if (dump_enabled_p ())
1806 dump_printf_loc (MSG_NOTE, vect_location, "epilog loop required\n");
1807 if (!vect_can_advance_ivs_p (loop_vinfo)
1808 || !slpeel_can_duplicate_loop_p (LOOP_VINFO_LOOP (loop_vinfo),
1809 single_exit (LOOP_VINFO_LOOP
1810 (loop_vinfo))))
1812 if (dump_enabled_p ())
1813 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1814 "not vectorized: can't create required "
1815 "epilog loop\n");
1816 return false;
1820 return true;
1823 /* Function vect_analyze_loop.
1825 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1826 for it. The different analyses will record information in the
1827 loop_vec_info struct. */
1828 loop_vec_info
1829 vect_analyze_loop (struct loop *loop)
1831 loop_vec_info loop_vinfo;
1832 unsigned int vector_sizes;
1834 /* Autodetect first vector size we try. */
1835 current_vector_size = 0;
1836 vector_sizes = targetm.vectorize.autovectorize_vector_sizes ();
1838 if (dump_enabled_p ())
1839 dump_printf_loc (MSG_NOTE, vect_location,
1840 "===== analyze_loop_nest =====\n");
1842 if (loop_outer (loop)
1843 && loop_vec_info_for_loop (loop_outer (loop))
1844 && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop))))
1846 if (dump_enabled_p ())
1847 dump_printf_loc (MSG_NOTE, vect_location,
1848 "outer-loop already vectorized.\n");
1849 return NULL;
1852 while (1)
1854 /* Check the CFG characteristics of the loop (nesting, entry/exit). */
1855 loop_vinfo = vect_analyze_loop_form (loop);
1856 if (!loop_vinfo)
1858 if (dump_enabled_p ())
1859 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1860 "bad loop form.\n");
1861 return NULL;
1864 if (vect_analyze_loop_2 (loop_vinfo))
1866 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1;
1868 return loop_vinfo;
1871 destroy_loop_vec_info (loop_vinfo, true);
1873 vector_sizes &= ~current_vector_size;
1874 if (vector_sizes == 0
1875 || current_vector_size == 0)
1876 return NULL;
1878 /* Try the next biggest vector size. */
1879 current_vector_size = 1 << floor_log2 (vector_sizes);
1880 if (dump_enabled_p ())
1881 dump_printf_loc (MSG_NOTE, vect_location,
1882 "***** Re-trying analysis with "
1883 "vector size %d\n", current_vector_size);
1888 /* Function reduction_code_for_scalar_code
1890 Input:
1891 CODE - tree_code of a reduction operations.
1893 Output:
1894 REDUC_CODE - the corresponding tree-code to be used to reduce the
1895 vector of partial results into a single scalar result (which
1896 will also reside in a vector) or ERROR_MARK if the operation is
1897 a supported reduction operation, but does not have such tree-code.
1899 Return FALSE if CODE currently cannot be vectorized as reduction. */
1901 static bool
1902 reduction_code_for_scalar_code (enum tree_code code,
1903 enum tree_code *reduc_code)
1905 switch (code)
1907 case MAX_EXPR:
1908 *reduc_code = REDUC_MAX_EXPR;
1909 return true;
1911 case MIN_EXPR:
1912 *reduc_code = REDUC_MIN_EXPR;
1913 return true;
1915 case PLUS_EXPR:
1916 *reduc_code = REDUC_PLUS_EXPR;
1917 return true;
1919 case MULT_EXPR:
1920 case MINUS_EXPR:
1921 case BIT_IOR_EXPR:
1922 case BIT_XOR_EXPR:
1923 case BIT_AND_EXPR:
1924 *reduc_code = ERROR_MARK;
1925 return true;
1927 default:
1928 return false;
1933 /* Error reporting helper for vect_is_simple_reduction below. GIMPLE statement
1934 STMT is printed with a message MSG. */
1936 static void
1937 report_vect_op (int msg_type, gimple stmt, const char *msg)
1939 dump_printf_loc (msg_type, vect_location, "%s", msg);
1940 dump_gimple_stmt (msg_type, TDF_SLIM, stmt, 0);
1941 dump_printf (msg_type, "\n");
1945 /* Detect SLP reduction of the form:
1947 #a1 = phi <a5, a0>
1948 a2 = operation (a1)
1949 a3 = operation (a2)
1950 a4 = operation (a3)
1951 a5 = operation (a4)
1953 #a = phi <a5>
1955 PHI is the reduction phi node (#a1 = phi <a5, a0> above)
1956 FIRST_STMT is the first reduction stmt in the chain
1957 (a2 = operation (a1)).
1959 Return TRUE if a reduction chain was detected. */
1961 static bool
1962 vect_is_slp_reduction (loop_vec_info loop_info, gimple phi, gimple first_stmt)
1964 struct loop *loop = (gimple_bb (phi))->loop_father;
1965 struct loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
1966 enum tree_code code;
1967 gimple current_stmt = NULL, loop_use_stmt = NULL, first, next_stmt;
1968 stmt_vec_info use_stmt_info, current_stmt_info;
1969 tree lhs;
1970 imm_use_iterator imm_iter;
1971 use_operand_p use_p;
1972 int nloop_uses, size = 0, n_out_of_loop_uses;
1973 bool found = false;
1975 if (loop != vect_loop)
1976 return false;
1978 lhs = PHI_RESULT (phi);
1979 code = gimple_assign_rhs_code (first_stmt);
1980 while (1)
1982 nloop_uses = 0;
1983 n_out_of_loop_uses = 0;
1984 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
1986 gimple use_stmt = USE_STMT (use_p);
1987 if (is_gimple_debug (use_stmt))
1988 continue;
1990 /* Check if we got back to the reduction phi. */
1991 if (use_stmt == phi)
1993 loop_use_stmt = use_stmt;
1994 found = true;
1995 break;
1998 if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
2000 if (vinfo_for_stmt (use_stmt)
2001 && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (use_stmt)))
2003 loop_use_stmt = use_stmt;
2004 nloop_uses++;
2007 else
2008 n_out_of_loop_uses++;
2010 /* There are can be either a single use in the loop or two uses in
2011 phi nodes. */
2012 if (nloop_uses > 1 || (n_out_of_loop_uses && nloop_uses))
2013 return false;
2016 if (found)
2017 break;
2019 /* We reached a statement with no loop uses. */
2020 if (nloop_uses == 0)
2021 return false;
2023 /* This is a loop exit phi, and we haven't reached the reduction phi. */
2024 if (gimple_code (loop_use_stmt) == GIMPLE_PHI)
2025 return false;
2027 if (!is_gimple_assign (loop_use_stmt)
2028 || code != gimple_assign_rhs_code (loop_use_stmt)
2029 || !flow_bb_inside_loop_p (loop, gimple_bb (loop_use_stmt)))
2030 return false;
2032 /* Insert USE_STMT into reduction chain. */
2033 use_stmt_info = vinfo_for_stmt (loop_use_stmt);
2034 if (current_stmt)
2036 current_stmt_info = vinfo_for_stmt (current_stmt);
2037 GROUP_NEXT_ELEMENT (current_stmt_info) = loop_use_stmt;
2038 GROUP_FIRST_ELEMENT (use_stmt_info)
2039 = GROUP_FIRST_ELEMENT (current_stmt_info);
2041 else
2042 GROUP_FIRST_ELEMENT (use_stmt_info) = loop_use_stmt;
2044 lhs = gimple_assign_lhs (loop_use_stmt);
2045 current_stmt = loop_use_stmt;
2046 size++;
2049 if (!found || loop_use_stmt != phi || size < 2)
2050 return false;
2052 /* Swap the operands, if needed, to make the reduction operand be the second
2053 operand. */
2054 lhs = PHI_RESULT (phi);
2055 next_stmt = GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt));
2056 while (next_stmt)
2058 if (gimple_assign_rhs2 (next_stmt) == lhs)
2060 tree op = gimple_assign_rhs1 (next_stmt);
2061 gimple def_stmt = NULL;
2063 if (TREE_CODE (op) == SSA_NAME)
2064 def_stmt = SSA_NAME_DEF_STMT (op);
2066 /* Check that the other def is either defined in the loop
2067 ("vect_internal_def"), or it's an induction (defined by a
2068 loop-header phi-node). */
2069 if (def_stmt
2070 && gimple_bb (def_stmt)
2071 && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
2072 && (is_gimple_assign (def_stmt)
2073 || is_gimple_call (def_stmt)
2074 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
2075 == vect_induction_def
2076 || (gimple_code (def_stmt) == GIMPLE_PHI
2077 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
2078 == vect_internal_def
2079 && !is_loop_header_bb_p (gimple_bb (def_stmt)))))
2081 lhs = gimple_assign_lhs (next_stmt);
2082 next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
2083 continue;
2086 return false;
2088 else
2090 tree op = gimple_assign_rhs2 (next_stmt);
2091 gimple def_stmt = NULL;
2093 if (TREE_CODE (op) == SSA_NAME)
2094 def_stmt = SSA_NAME_DEF_STMT (op);
2096 /* Check that the other def is either defined in the loop
2097 ("vect_internal_def"), or it's an induction (defined by a
2098 loop-header phi-node). */
2099 if (def_stmt
2100 && gimple_bb (def_stmt)
2101 && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
2102 && (is_gimple_assign (def_stmt)
2103 || is_gimple_call (def_stmt)
2104 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
2105 == vect_induction_def
2106 || (gimple_code (def_stmt) == GIMPLE_PHI
2107 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
2108 == vect_internal_def
2109 && !is_loop_header_bb_p (gimple_bb (def_stmt)))))
2111 if (dump_enabled_p ())
2113 dump_printf_loc (MSG_NOTE, vect_location, "swapping oprnds: ");
2114 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, next_stmt, 0);
2115 dump_printf (MSG_NOTE, "\n");
2118 swap_ssa_operands (next_stmt,
2119 gimple_assign_rhs1_ptr (next_stmt),
2120 gimple_assign_rhs2_ptr (next_stmt));
2121 update_stmt (next_stmt);
2123 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (next_stmt)))
2124 LOOP_VINFO_OPERANDS_SWAPPED (loop_info) = true;
2126 else
2127 return false;
2130 lhs = gimple_assign_lhs (next_stmt);
2131 next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
2134 /* Save the chain for further analysis in SLP detection. */
2135 first = GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt));
2136 LOOP_VINFO_REDUCTION_CHAINS (loop_info).safe_push (first);
2137 GROUP_SIZE (vinfo_for_stmt (first)) = size;
2139 return true;
2143 /* Function vect_is_simple_reduction_1
2145 (1) Detect a cross-iteration def-use cycle that represents a simple
2146 reduction computation. We look for the following pattern:
2148 loop_header:
2149 a1 = phi < a0, a2 >
2150 a3 = ...
2151 a2 = operation (a3, a1)
2155 a3 = ...
2156 loop_header:
2157 a1 = phi < a0, a2 >
2158 a2 = operation (a3, a1)
2160 such that:
2161 1. operation is commutative and associative and it is safe to
2162 change the order of the computation (if CHECK_REDUCTION is true)
2163 2. no uses for a2 in the loop (a2 is used out of the loop)
2164 3. no uses of a1 in the loop besides the reduction operation
2165 4. no uses of a1 outside the loop.
2167 Conditions 1,4 are tested here.
2168 Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
2170 (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
2171 nested cycles, if CHECK_REDUCTION is false.
2173 (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
2174 reductions:
2176 a1 = phi < a0, a2 >
2177 inner loop (def of a3)
2178 a2 = phi < a3 >
2180 If MODIFY is true it tries also to rework the code in-place to enable
2181 detection of more reduction patterns. For the time being we rewrite
2182 "res -= RHS" into "rhs += -RHS" when it seems worthwhile.
2185 static gimple
2186 vect_is_simple_reduction_1 (loop_vec_info loop_info, gimple phi,
2187 bool check_reduction, bool *double_reduc,
2188 bool modify)
2190 struct loop *loop = (gimple_bb (phi))->loop_father;
2191 struct loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
2192 edge latch_e = loop_latch_edge (loop);
2193 tree loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
2194 gimple def_stmt, def1 = NULL, def2 = NULL;
2195 enum tree_code orig_code, code;
2196 tree op1, op2, op3 = NULL_TREE, op4 = NULL_TREE;
2197 tree type;
2198 int nloop_uses;
2199 tree name;
2200 imm_use_iterator imm_iter;
2201 use_operand_p use_p;
2202 bool phi_def;
2204 *double_reduc = false;
2206 /* If CHECK_REDUCTION is true, we assume inner-most loop vectorization,
2207 otherwise, we assume outer loop vectorization. */
2208 gcc_assert ((check_reduction && loop == vect_loop)
2209 || (!check_reduction && flow_loop_nested_p (vect_loop, loop)));
2211 name = PHI_RESULT (phi);
2212 /* ??? If there are no uses of the PHI result the inner loop reduction
2213 won't be detected as possibly double-reduction by vectorizable_reduction
2214 because that tries to walk the PHI arg from the preheader edge which
2215 can be constant. See PR60382. */
2216 if (has_zero_uses (name))
2217 return NULL;
2218 nloop_uses = 0;
2219 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
2221 gimple use_stmt = USE_STMT (use_p);
2222 if (is_gimple_debug (use_stmt))
2223 continue;
2225 if (!flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
2227 if (dump_enabled_p ())
2228 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2229 "intermediate value used outside loop.\n");
2231 return NULL;
2234 if (vinfo_for_stmt (use_stmt)
2235 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt)))
2236 nloop_uses++;
2237 if (nloop_uses > 1)
2239 if (dump_enabled_p ())
2240 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2241 "reduction used in loop.\n");
2242 return NULL;
2246 if (TREE_CODE (loop_arg) != SSA_NAME)
2248 if (dump_enabled_p ())
2250 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2251 "reduction: not ssa_name: ");
2252 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, loop_arg);
2253 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
2255 return NULL;
2258 def_stmt = SSA_NAME_DEF_STMT (loop_arg);
2259 if (!def_stmt)
2261 if (dump_enabled_p ())
2262 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2263 "reduction: no def_stmt.\n");
2264 return NULL;
2267 if (!is_gimple_assign (def_stmt) && gimple_code (def_stmt) != GIMPLE_PHI)
2269 if (dump_enabled_p ())
2271 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, def_stmt, 0);
2272 dump_printf (MSG_NOTE, "\n");
2274 return NULL;
2277 if (is_gimple_assign (def_stmt))
2279 name = gimple_assign_lhs (def_stmt);
2280 phi_def = false;
2282 else
2284 name = PHI_RESULT (def_stmt);
2285 phi_def = true;
2288 nloop_uses = 0;
2289 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
2291 gimple use_stmt = USE_STMT (use_p);
2292 if (is_gimple_debug (use_stmt))
2293 continue;
2294 if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt))
2295 && vinfo_for_stmt (use_stmt)
2296 && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt)))
2297 nloop_uses++;
2298 if (nloop_uses > 1)
2300 if (dump_enabled_p ())
2301 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2302 "reduction used in loop.\n");
2303 return NULL;
2307 /* If DEF_STMT is a phi node itself, we expect it to have a single argument
2308 defined in the inner loop. */
2309 if (phi_def)
2311 op1 = PHI_ARG_DEF (def_stmt, 0);
2313 if (gimple_phi_num_args (def_stmt) != 1
2314 || TREE_CODE (op1) != SSA_NAME)
2316 if (dump_enabled_p ())
2317 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2318 "unsupported phi node definition.\n");
2320 return NULL;
2323 def1 = SSA_NAME_DEF_STMT (op1);
2324 if (flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
2325 && loop->inner
2326 && flow_bb_inside_loop_p (loop->inner, gimple_bb (def1))
2327 && is_gimple_assign (def1))
2329 if (dump_enabled_p ())
2330 report_vect_op (MSG_NOTE, def_stmt,
2331 "detected double reduction: ");
2333 *double_reduc = true;
2334 return def_stmt;
2337 return NULL;
2340 code = orig_code = gimple_assign_rhs_code (def_stmt);
2342 /* We can handle "res -= x[i]", which is non-associative by
2343 simply rewriting this into "res += -x[i]". Avoid changing
2344 gimple instruction for the first simple tests and only do this
2345 if we're allowed to change code at all. */
2346 if (code == MINUS_EXPR
2347 && modify
2348 && (op1 = gimple_assign_rhs1 (def_stmt))
2349 && TREE_CODE (op1) == SSA_NAME
2350 && SSA_NAME_DEF_STMT (op1) == phi)
2351 code = PLUS_EXPR;
2353 if (check_reduction
2354 && (!commutative_tree_code (code) || !associative_tree_code (code)))
2356 if (dump_enabled_p ())
2357 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
2358 "reduction: not commutative/associative: ");
2359 return NULL;
2362 if (get_gimple_rhs_class (code) != GIMPLE_BINARY_RHS)
2364 if (code != COND_EXPR)
2366 if (dump_enabled_p ())
2367 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
2368 "reduction: not binary operation: ");
2370 return NULL;
2373 op3 = gimple_assign_rhs1 (def_stmt);
2374 if (COMPARISON_CLASS_P (op3))
2376 op4 = TREE_OPERAND (op3, 1);
2377 op3 = TREE_OPERAND (op3, 0);
2380 op1 = gimple_assign_rhs2 (def_stmt);
2381 op2 = gimple_assign_rhs3 (def_stmt);
2383 if (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op2) != SSA_NAME)
2385 if (dump_enabled_p ())
2386 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
2387 "reduction: uses not ssa_names: ");
2389 return NULL;
2392 else
2394 op1 = gimple_assign_rhs1 (def_stmt);
2395 op2 = gimple_assign_rhs2 (def_stmt);
2397 if (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op2) != SSA_NAME)
2399 if (dump_enabled_p ())
2400 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
2401 "reduction: uses not ssa_names: ");
2403 return NULL;
2407 type = TREE_TYPE (gimple_assign_lhs (def_stmt));
2408 if ((TREE_CODE (op1) == SSA_NAME
2409 && !types_compatible_p (type,TREE_TYPE (op1)))
2410 || (TREE_CODE (op2) == SSA_NAME
2411 && !types_compatible_p (type, TREE_TYPE (op2)))
2412 || (op3 && TREE_CODE (op3) == SSA_NAME
2413 && !types_compatible_p (type, TREE_TYPE (op3)))
2414 || (op4 && TREE_CODE (op4) == SSA_NAME
2415 && !types_compatible_p (type, TREE_TYPE (op4))))
2417 if (dump_enabled_p ())
2419 dump_printf_loc (MSG_NOTE, vect_location,
2420 "reduction: multiple types: operation type: ");
2421 dump_generic_expr (MSG_NOTE, TDF_SLIM, type);
2422 dump_printf (MSG_NOTE, ", operands types: ");
2423 dump_generic_expr (MSG_NOTE, TDF_SLIM,
2424 TREE_TYPE (op1));
2425 dump_printf (MSG_NOTE, ",");
2426 dump_generic_expr (MSG_NOTE, TDF_SLIM,
2427 TREE_TYPE (op2));
2428 if (op3)
2430 dump_printf (MSG_NOTE, ",");
2431 dump_generic_expr (MSG_NOTE, TDF_SLIM,
2432 TREE_TYPE (op3));
2435 if (op4)
2437 dump_printf (MSG_NOTE, ",");
2438 dump_generic_expr (MSG_NOTE, TDF_SLIM,
2439 TREE_TYPE (op4));
2441 dump_printf (MSG_NOTE, "\n");
2444 return NULL;
2447 /* Check that it's ok to change the order of the computation.
2448 Generally, when vectorizing a reduction we change the order of the
2449 computation. This may change the behavior of the program in some
2450 cases, so we need to check that this is ok. One exception is when
2451 vectorizing an outer-loop: the inner-loop is executed sequentially,
2452 and therefore vectorizing reductions in the inner-loop during
2453 outer-loop vectorization is safe. */
2455 /* CHECKME: check for !flag_finite_math_only too? */
2456 if (SCALAR_FLOAT_TYPE_P (type) && !flag_associative_math
2457 && check_reduction)
2459 /* Changing the order of operations changes the semantics. */
2460 if (dump_enabled_p ())
2461 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
2462 "reduction: unsafe fp math optimization: ");
2463 return NULL;
2465 else if (INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_TRAPS (type)
2466 && check_reduction)
2468 /* Changing the order of operations changes the semantics. */
2469 if (dump_enabled_p ())
2470 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
2471 "reduction: unsafe int math optimization: ");
2472 return NULL;
2474 else if (SAT_FIXED_POINT_TYPE_P (type) && check_reduction)
2476 /* Changing the order of operations changes the semantics. */
2477 if (dump_enabled_p ())
2478 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
2479 "reduction: unsafe fixed-point math optimization: ");
2480 return NULL;
2483 /* If we detected "res -= x[i]" earlier, rewrite it into
2484 "res += -x[i]" now. If this turns out to be useless reassoc
2485 will clean it up again. */
2486 if (orig_code == MINUS_EXPR)
2488 tree rhs = gimple_assign_rhs2 (def_stmt);
2489 tree negrhs = make_ssa_name (TREE_TYPE (rhs), NULL);
2490 gimple negate_stmt = gimple_build_assign_with_ops (NEGATE_EXPR, negrhs,
2491 rhs, NULL);
2492 gimple_stmt_iterator gsi = gsi_for_stmt (def_stmt);
2493 set_vinfo_for_stmt (negate_stmt, new_stmt_vec_info (negate_stmt,
2494 loop_info, NULL));
2495 gsi_insert_before (&gsi, negate_stmt, GSI_NEW_STMT);
2496 gimple_assign_set_rhs2 (def_stmt, negrhs);
2497 gimple_assign_set_rhs_code (def_stmt, PLUS_EXPR);
2498 update_stmt (def_stmt);
2501 /* Reduction is safe. We're dealing with one of the following:
2502 1) integer arithmetic and no trapv
2503 2) floating point arithmetic, and special flags permit this optimization
2504 3) nested cycle (i.e., outer loop vectorization). */
2505 if (TREE_CODE (op1) == SSA_NAME)
2506 def1 = SSA_NAME_DEF_STMT (op1);
2508 if (TREE_CODE (op2) == SSA_NAME)
2509 def2 = SSA_NAME_DEF_STMT (op2);
2511 if (code != COND_EXPR
2512 && ((!def1 || gimple_nop_p (def1)) && (!def2 || gimple_nop_p (def2))))
2514 if (dump_enabled_p ())
2515 report_vect_op (MSG_NOTE, def_stmt, "reduction: no defs for operands: ");
2516 return NULL;
2519 /* Check that one def is the reduction def, defined by PHI,
2520 the other def is either defined in the loop ("vect_internal_def"),
2521 or it's an induction (defined by a loop-header phi-node). */
2523 if (def2 && def2 == phi
2524 && (code == COND_EXPR
2525 || !def1 || gimple_nop_p (def1)
2526 || !flow_bb_inside_loop_p (loop, gimple_bb (def1))
2527 || (def1 && flow_bb_inside_loop_p (loop, gimple_bb (def1))
2528 && (is_gimple_assign (def1)
2529 || is_gimple_call (def1)
2530 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1))
2531 == vect_induction_def
2532 || (gimple_code (def1) == GIMPLE_PHI
2533 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1))
2534 == vect_internal_def
2535 && !is_loop_header_bb_p (gimple_bb (def1)))))))
2537 if (dump_enabled_p ())
2538 report_vect_op (MSG_NOTE, def_stmt, "detected reduction: ");
2539 return def_stmt;
2542 if (def1 && def1 == phi
2543 && (code == COND_EXPR
2544 || !def2 || gimple_nop_p (def2)
2545 || !flow_bb_inside_loop_p (loop, gimple_bb (def2))
2546 || (def2 && flow_bb_inside_loop_p (loop, gimple_bb (def2))
2547 && (is_gimple_assign (def2)
2548 || is_gimple_call (def2)
2549 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2))
2550 == vect_induction_def
2551 || (gimple_code (def2) == GIMPLE_PHI
2552 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2))
2553 == vect_internal_def
2554 && !is_loop_header_bb_p (gimple_bb (def2)))))))
2556 if (check_reduction)
2558 /* Swap operands (just for simplicity - so that the rest of the code
2559 can assume that the reduction variable is always the last (second)
2560 argument). */
2561 if (dump_enabled_p ())
2562 report_vect_op (MSG_NOTE, def_stmt,
2563 "detected reduction: need to swap operands: ");
2565 swap_ssa_operands (def_stmt, gimple_assign_rhs1_ptr (def_stmt),
2566 gimple_assign_rhs2_ptr (def_stmt));
2568 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (def_stmt)))
2569 LOOP_VINFO_OPERANDS_SWAPPED (loop_info) = true;
2571 else
2573 if (dump_enabled_p ())
2574 report_vect_op (MSG_NOTE, def_stmt, "detected reduction: ");
2577 return def_stmt;
2580 /* Try to find SLP reduction chain. */
2581 if (check_reduction && vect_is_slp_reduction (loop_info, phi, def_stmt))
2583 if (dump_enabled_p ())
2584 report_vect_op (MSG_NOTE, def_stmt,
2585 "reduction: detected reduction chain: ");
2587 return def_stmt;
2590 if (dump_enabled_p ())
2591 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
2592 "reduction: unknown pattern: ");
2594 return NULL;
2597 /* Wrapper around vect_is_simple_reduction_1, that won't modify code
2598 in-place. Arguments as there. */
2600 static gimple
2601 vect_is_simple_reduction (loop_vec_info loop_info, gimple phi,
2602 bool check_reduction, bool *double_reduc)
2604 return vect_is_simple_reduction_1 (loop_info, phi, check_reduction,
2605 double_reduc, false);
2608 /* Wrapper around vect_is_simple_reduction_1, which will modify code
2609 in-place if it enables detection of more reductions. Arguments
2610 as there. */
2612 gimple
2613 vect_force_simple_reduction (loop_vec_info loop_info, gimple phi,
2614 bool check_reduction, bool *double_reduc)
2616 return vect_is_simple_reduction_1 (loop_info, phi, check_reduction,
2617 double_reduc, true);
2620 /* Calculate the cost of one scalar iteration of the loop. */
2622 vect_get_single_scalar_iteration_cost (loop_vec_info loop_vinfo)
2624 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2625 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
2626 int nbbs = loop->num_nodes, factor, scalar_single_iter_cost = 0;
2627 int innerloop_iters, i, stmt_cost;
2629 /* Count statements in scalar loop. Using this as scalar cost for a single
2630 iteration for now.
2632 TODO: Add outer loop support.
2634 TODO: Consider assigning different costs to different scalar
2635 statements. */
2637 /* FORNOW. */
2638 innerloop_iters = 1;
2639 if (loop->inner)
2640 innerloop_iters = 50; /* FIXME */
2642 for (i = 0; i < nbbs; i++)
2644 gimple_stmt_iterator si;
2645 basic_block bb = bbs[i];
2647 if (bb->loop_father == loop->inner)
2648 factor = innerloop_iters;
2649 else
2650 factor = 1;
2652 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
2654 gimple stmt = gsi_stmt (si);
2655 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2657 if (!is_gimple_assign (stmt) && !is_gimple_call (stmt))
2658 continue;
2660 /* Skip stmts that are not vectorized inside the loop. */
2661 if (stmt_info
2662 && !STMT_VINFO_RELEVANT_P (stmt_info)
2663 && (!STMT_VINFO_LIVE_P (stmt_info)
2664 || !VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info)))
2665 && !STMT_VINFO_IN_PATTERN_P (stmt_info))
2666 continue;
2668 if (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt)))
2670 if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt))))
2671 stmt_cost = vect_get_stmt_cost (scalar_load);
2672 else
2673 stmt_cost = vect_get_stmt_cost (scalar_store);
2675 else
2676 stmt_cost = vect_get_stmt_cost (scalar_stmt);
2678 scalar_single_iter_cost += stmt_cost * factor;
2681 return scalar_single_iter_cost;
2684 /* Calculate cost of peeling the loop PEEL_ITERS_PROLOGUE times. */
2686 vect_get_known_peeling_cost (loop_vec_info loop_vinfo, int peel_iters_prologue,
2687 int *peel_iters_epilogue,
2688 int scalar_single_iter_cost,
2689 stmt_vector_for_cost *prologue_cost_vec,
2690 stmt_vector_for_cost *epilogue_cost_vec)
2692 int retval = 0;
2693 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2695 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
2697 *peel_iters_epilogue = vf/2;
2698 if (dump_enabled_p ())
2699 dump_printf_loc (MSG_NOTE, vect_location,
2700 "cost model: epilogue peel iters set to vf/2 "
2701 "because loop iterations are unknown .\n");
2703 /* If peeled iterations are known but number of scalar loop
2704 iterations are unknown, count a taken branch per peeled loop. */
2705 retval = record_stmt_cost (prologue_cost_vec, 2, cond_branch_taken,
2706 NULL, 0, vect_prologue);
2708 else
2710 int niters = LOOP_VINFO_INT_NITERS (loop_vinfo);
2711 peel_iters_prologue = niters < peel_iters_prologue ?
2712 niters : peel_iters_prologue;
2713 *peel_iters_epilogue = (niters - peel_iters_prologue) % vf;
2714 /* If we need to peel for gaps, but no peeling is required, we have to
2715 peel VF iterations. */
2716 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo) && !*peel_iters_epilogue)
2717 *peel_iters_epilogue = vf;
2720 if (peel_iters_prologue)
2721 retval += record_stmt_cost (prologue_cost_vec,
2722 peel_iters_prologue * scalar_single_iter_cost,
2723 scalar_stmt, NULL, 0, vect_prologue);
2724 if (*peel_iters_epilogue)
2725 retval += record_stmt_cost (epilogue_cost_vec,
2726 *peel_iters_epilogue * scalar_single_iter_cost,
2727 scalar_stmt, NULL, 0, vect_epilogue);
2728 return retval;
2731 /* Function vect_estimate_min_profitable_iters
2733 Return the number of iterations required for the vector version of the
2734 loop to be profitable relative to the cost of the scalar version of the
2735 loop. */
2737 static void
2738 vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo,
2739 int *ret_min_profitable_niters,
2740 int *ret_min_profitable_estimate)
2742 int min_profitable_iters;
2743 int min_profitable_estimate;
2744 int peel_iters_prologue;
2745 int peel_iters_epilogue;
2746 unsigned vec_inside_cost = 0;
2747 int vec_outside_cost = 0;
2748 unsigned vec_prologue_cost = 0;
2749 unsigned vec_epilogue_cost = 0;
2750 int scalar_single_iter_cost = 0;
2751 int scalar_outside_cost = 0;
2752 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2753 int npeel = LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo);
2754 void *target_cost_data = LOOP_VINFO_TARGET_COST_DATA (loop_vinfo);
2756 /* Cost model disabled. */
2757 if (unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo)))
2759 dump_printf_loc (MSG_NOTE, vect_location, "cost model disabled.\n");
2760 *ret_min_profitable_niters = 0;
2761 *ret_min_profitable_estimate = 0;
2762 return;
2765 /* Requires loop versioning tests to handle misalignment. */
2766 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo))
2768 /* FIXME: Make cost depend on complexity of individual check. */
2769 unsigned len = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).length ();
2770 (void) add_stmt_cost (target_cost_data, len, vector_stmt, NULL, 0,
2771 vect_prologue);
2772 dump_printf (MSG_NOTE,
2773 "cost model: Adding cost of checks for loop "
2774 "versioning to treat misalignment.\n");
2777 /* Requires loop versioning with alias checks. */
2778 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2780 /* FIXME: Make cost depend on complexity of individual check. */
2781 unsigned len = LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo).length ();
2782 (void) add_stmt_cost (target_cost_data, len, vector_stmt, NULL, 0,
2783 vect_prologue);
2784 dump_printf (MSG_NOTE,
2785 "cost model: Adding cost of checks for loop "
2786 "versioning aliasing.\n");
2789 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
2790 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2791 (void) add_stmt_cost (target_cost_data, 1, cond_branch_taken, NULL, 0,
2792 vect_prologue);
2794 /* Count statements in scalar loop. Using this as scalar cost for a single
2795 iteration for now.
2797 TODO: Add outer loop support.
2799 TODO: Consider assigning different costs to different scalar
2800 statements. */
2802 scalar_single_iter_cost = vect_get_single_scalar_iteration_cost (loop_vinfo);
2804 /* Add additional cost for the peeled instructions in prologue and epilogue
2805 loop.
2807 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
2808 at compile-time - we assume it's vf/2 (the worst would be vf-1).
2810 TODO: Build an expression that represents peel_iters for prologue and
2811 epilogue to be used in a run-time test. */
2813 if (npeel < 0)
2815 peel_iters_prologue = vf/2;
2816 dump_printf (MSG_NOTE, "cost model: "
2817 "prologue peel iters set to vf/2.\n");
2819 /* If peeling for alignment is unknown, loop bound of main loop becomes
2820 unknown. */
2821 peel_iters_epilogue = vf/2;
2822 dump_printf (MSG_NOTE, "cost model: "
2823 "epilogue peel iters set to vf/2 because "
2824 "peeling for alignment is unknown.\n");
2826 /* If peeled iterations are unknown, count a taken branch and a not taken
2827 branch per peeled loop. Even if scalar loop iterations are known,
2828 vector iterations are not known since peeled prologue iterations are
2829 not known. Hence guards remain the same. */
2830 (void) add_stmt_cost (target_cost_data, 2, cond_branch_taken,
2831 NULL, 0, vect_prologue);
2832 (void) add_stmt_cost (target_cost_data, 2, cond_branch_not_taken,
2833 NULL, 0, vect_prologue);
2834 /* FORNOW: Don't attempt to pass individual scalar instructions to
2835 the model; just assume linear cost for scalar iterations. */
2836 (void) add_stmt_cost (target_cost_data,
2837 peel_iters_prologue * scalar_single_iter_cost,
2838 scalar_stmt, NULL, 0, vect_prologue);
2839 (void) add_stmt_cost (target_cost_data,
2840 peel_iters_epilogue * scalar_single_iter_cost,
2841 scalar_stmt, NULL, 0, vect_epilogue);
2843 else
2845 stmt_vector_for_cost prologue_cost_vec, epilogue_cost_vec;
2846 stmt_info_for_cost *si;
2847 int j;
2848 void *data = LOOP_VINFO_TARGET_COST_DATA (loop_vinfo);
2850 prologue_cost_vec.create (2);
2851 epilogue_cost_vec.create (2);
2852 peel_iters_prologue = npeel;
2854 (void) vect_get_known_peeling_cost (loop_vinfo, peel_iters_prologue,
2855 &peel_iters_epilogue,
2856 scalar_single_iter_cost,
2857 &prologue_cost_vec,
2858 &epilogue_cost_vec);
2860 FOR_EACH_VEC_ELT (prologue_cost_vec, j, si)
2862 struct _stmt_vec_info *stmt_info
2863 = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
2864 (void) add_stmt_cost (data, si->count, si->kind, stmt_info,
2865 si->misalign, vect_prologue);
2868 FOR_EACH_VEC_ELT (epilogue_cost_vec, j, si)
2870 struct _stmt_vec_info *stmt_info
2871 = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
2872 (void) add_stmt_cost (data, si->count, si->kind, stmt_info,
2873 si->misalign, vect_epilogue);
2876 prologue_cost_vec.release ();
2877 epilogue_cost_vec.release ();
2880 /* FORNOW: The scalar outside cost is incremented in one of the
2881 following ways:
2883 1. The vectorizer checks for alignment and aliasing and generates
2884 a condition that allows dynamic vectorization. A cost model
2885 check is ANDED with the versioning condition. Hence scalar code
2886 path now has the added cost of the versioning check.
2888 if (cost > th & versioning_check)
2889 jmp to vector code
2891 Hence run-time scalar is incremented by not-taken branch cost.
2893 2. The vectorizer then checks if a prologue is required. If the
2894 cost model check was not done before during versioning, it has to
2895 be done before the prologue check.
2897 if (cost <= th)
2898 prologue = scalar_iters
2899 if (prologue == 0)
2900 jmp to vector code
2901 else
2902 execute prologue
2903 if (prologue == num_iters)
2904 go to exit
2906 Hence the run-time scalar cost is incremented by a taken branch,
2907 plus a not-taken branch, plus a taken branch cost.
2909 3. The vectorizer then checks if an epilogue is required. If the
2910 cost model check was not done before during prologue check, it
2911 has to be done with the epilogue check.
2913 if (prologue == 0)
2914 jmp to vector code
2915 else
2916 execute prologue
2917 if (prologue == num_iters)
2918 go to exit
2919 vector code:
2920 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
2921 jmp to epilogue
2923 Hence the run-time scalar cost should be incremented by 2 taken
2924 branches.
2926 TODO: The back end may reorder the BBS's differently and reverse
2927 conditions/branch directions. Change the estimates below to
2928 something more reasonable. */
2930 /* If the number of iterations is known and we do not do versioning, we can
2931 decide whether to vectorize at compile time. Hence the scalar version
2932 do not carry cost model guard costs. */
2933 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
2934 || LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
2935 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2937 /* Cost model check occurs at versioning. */
2938 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
2939 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2940 scalar_outside_cost += vect_get_stmt_cost (cond_branch_not_taken);
2941 else
2943 /* Cost model check occurs at prologue generation. */
2944 if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0)
2945 scalar_outside_cost += 2 * vect_get_stmt_cost (cond_branch_taken)
2946 + vect_get_stmt_cost (cond_branch_not_taken);
2947 /* Cost model check occurs at epilogue generation. */
2948 else
2949 scalar_outside_cost += 2 * vect_get_stmt_cost (cond_branch_taken);
2953 /* Complete the target-specific cost calculations. */
2954 finish_cost (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo), &vec_prologue_cost,
2955 &vec_inside_cost, &vec_epilogue_cost);
2957 vec_outside_cost = (int)(vec_prologue_cost + vec_epilogue_cost);
2959 /* Calculate number of iterations required to make the vector version
2960 profitable, relative to the loop bodies only. The following condition
2961 must hold true:
2962 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
2963 where
2964 SIC = scalar iteration cost, VIC = vector iteration cost,
2965 VOC = vector outside cost, VF = vectorization factor,
2966 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
2967 SOC = scalar outside cost for run time cost model check. */
2969 if ((scalar_single_iter_cost * vf) > (int) vec_inside_cost)
2971 if (vec_outside_cost <= 0)
2972 min_profitable_iters = 1;
2973 else
2975 min_profitable_iters = ((vec_outside_cost - scalar_outside_cost) * vf
2976 - vec_inside_cost * peel_iters_prologue
2977 - vec_inside_cost * peel_iters_epilogue)
2978 / ((scalar_single_iter_cost * vf)
2979 - vec_inside_cost);
2981 if ((scalar_single_iter_cost * vf * min_profitable_iters)
2982 <= (((int) vec_inside_cost * min_profitable_iters)
2983 + (((int) vec_outside_cost - scalar_outside_cost) * vf)))
2984 min_profitable_iters++;
2987 /* vector version will never be profitable. */
2988 else
2990 if (LOOP_VINFO_LOOP (loop_vinfo)->force_vectorize)
2991 warning_at (vect_location, OPT_Wopenmp_simd, "vectorization "
2992 "did not happen for a simd loop");
2994 if (dump_enabled_p ())
2995 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2996 "cost model: the vector iteration cost = %d "
2997 "divided by the scalar iteration cost = %d "
2998 "is greater or equal to the vectorization factor = %d"
2999 ".\n",
3000 vec_inside_cost, scalar_single_iter_cost, vf);
3001 *ret_min_profitable_niters = -1;
3002 *ret_min_profitable_estimate = -1;
3003 return;
3006 if (dump_enabled_p ())
3008 dump_printf_loc (MSG_NOTE, vect_location, "Cost model analysis: \n");
3009 dump_printf (MSG_NOTE, " Vector inside of loop cost: %d\n",
3010 vec_inside_cost);
3011 dump_printf (MSG_NOTE, " Vector prologue cost: %d\n",
3012 vec_prologue_cost);
3013 dump_printf (MSG_NOTE, " Vector epilogue cost: %d\n",
3014 vec_epilogue_cost);
3015 dump_printf (MSG_NOTE, " Scalar iteration cost: %d\n",
3016 scalar_single_iter_cost);
3017 dump_printf (MSG_NOTE, " Scalar outside cost: %d\n",
3018 scalar_outside_cost);
3019 dump_printf (MSG_NOTE, " Vector outside cost: %d\n",
3020 vec_outside_cost);
3021 dump_printf (MSG_NOTE, " prologue iterations: %d\n",
3022 peel_iters_prologue);
3023 dump_printf (MSG_NOTE, " epilogue iterations: %d\n",
3024 peel_iters_epilogue);
3025 dump_printf (MSG_NOTE,
3026 " Calculated minimum iters for profitability: %d\n",
3027 min_profitable_iters);
3028 dump_printf (MSG_NOTE, "\n");
3031 min_profitable_iters =
3032 min_profitable_iters < vf ? vf : min_profitable_iters;
3034 /* Because the condition we create is:
3035 if (niters <= min_profitable_iters)
3036 then skip the vectorized loop. */
3037 min_profitable_iters--;
3039 if (dump_enabled_p ())
3040 dump_printf_loc (MSG_NOTE, vect_location,
3041 " Runtime profitability threshold = %d\n",
3042 min_profitable_iters);
3044 *ret_min_profitable_niters = min_profitable_iters;
3046 /* Calculate number of iterations required to make the vector version
3047 profitable, relative to the loop bodies only.
3049 Non-vectorized variant is SIC * niters and it must win over vector
3050 variant on the expected loop trip count. The following condition must hold true:
3051 SIC * niters > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC + SOC */
3053 if (vec_outside_cost <= 0)
3054 min_profitable_estimate = 1;
3055 else
3057 min_profitable_estimate = ((vec_outside_cost + scalar_outside_cost) * vf
3058 - vec_inside_cost * peel_iters_prologue
3059 - vec_inside_cost * peel_iters_epilogue)
3060 / ((scalar_single_iter_cost * vf)
3061 - vec_inside_cost);
3063 min_profitable_estimate --;
3064 min_profitable_estimate = MAX (min_profitable_estimate, min_profitable_iters);
3065 if (dump_enabled_p ())
3066 dump_printf_loc (MSG_NOTE, vect_location,
3067 " Static estimate profitability threshold = %d\n",
3068 min_profitable_iters);
3070 *ret_min_profitable_estimate = min_profitable_estimate;
3074 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
3075 functions. Design better to avoid maintenance issues. */
3077 /* Function vect_model_reduction_cost.
3079 Models cost for a reduction operation, including the vector ops
3080 generated within the strip-mine loop, the initial definition before
3081 the loop, and the epilogue code that must be generated. */
3083 static bool
3084 vect_model_reduction_cost (stmt_vec_info stmt_info, enum tree_code reduc_code,
3085 int ncopies)
3087 int prologue_cost = 0, epilogue_cost = 0;
3088 enum tree_code code;
3089 optab optab;
3090 tree vectype;
3091 gimple stmt, orig_stmt;
3092 tree reduction_op;
3093 enum machine_mode mode;
3094 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3095 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
3096 void *target_cost_data = LOOP_VINFO_TARGET_COST_DATA (loop_vinfo);
3098 /* Cost of reduction op inside loop. */
3099 unsigned inside_cost = add_stmt_cost (target_cost_data, ncopies, vector_stmt,
3100 stmt_info, 0, vect_body);
3101 stmt = STMT_VINFO_STMT (stmt_info);
3103 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
3105 case GIMPLE_SINGLE_RHS:
3106 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt)) == ternary_op);
3107 reduction_op = TREE_OPERAND (gimple_assign_rhs1 (stmt), 2);
3108 break;
3109 case GIMPLE_UNARY_RHS:
3110 reduction_op = gimple_assign_rhs1 (stmt);
3111 break;
3112 case GIMPLE_BINARY_RHS:
3113 reduction_op = gimple_assign_rhs2 (stmt);
3114 break;
3115 case GIMPLE_TERNARY_RHS:
3116 reduction_op = gimple_assign_rhs3 (stmt);
3117 break;
3118 default:
3119 gcc_unreachable ();
3122 vectype = get_vectype_for_scalar_type (TREE_TYPE (reduction_op));
3123 if (!vectype)
3125 if (dump_enabled_p ())
3127 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3128 "unsupported data-type ");
3129 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
3130 TREE_TYPE (reduction_op));
3131 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
3133 return false;
3136 mode = TYPE_MODE (vectype);
3137 orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
3139 if (!orig_stmt)
3140 orig_stmt = STMT_VINFO_STMT (stmt_info);
3142 code = gimple_assign_rhs_code (orig_stmt);
3144 /* Add in cost for initial definition. */
3145 prologue_cost += add_stmt_cost (target_cost_data, 1, scalar_to_vec,
3146 stmt_info, 0, vect_prologue);
3148 /* Determine cost of epilogue code.
3150 We have a reduction operator that will reduce the vector in one statement.
3151 Also requires scalar extract. */
3153 if (!nested_in_vect_loop_p (loop, orig_stmt))
3155 if (reduc_code != ERROR_MARK)
3157 epilogue_cost += add_stmt_cost (target_cost_data, 1, vector_stmt,
3158 stmt_info, 0, vect_epilogue);
3159 epilogue_cost += add_stmt_cost (target_cost_data, 1, vec_to_scalar,
3160 stmt_info, 0, vect_epilogue);
3162 else
3164 int vec_size_in_bits = tree_to_uhwi (TYPE_SIZE (vectype));
3165 tree bitsize =
3166 TYPE_SIZE (TREE_TYPE (gimple_assign_lhs (orig_stmt)));
3167 int element_bitsize = tree_to_uhwi (bitsize);
3168 int nelements = vec_size_in_bits / element_bitsize;
3170 optab = optab_for_tree_code (code, vectype, optab_default);
3172 /* We have a whole vector shift available. */
3173 if (VECTOR_MODE_P (mode)
3174 && optab_handler (optab, mode) != CODE_FOR_nothing
3175 && optab_handler (vec_shr_optab, mode) != CODE_FOR_nothing)
3177 /* Final reduction via vector shifts and the reduction operator.
3178 Also requires scalar extract. */
3179 epilogue_cost += add_stmt_cost (target_cost_data,
3180 exact_log2 (nelements) * 2,
3181 vector_stmt, stmt_info, 0,
3182 vect_epilogue);
3183 epilogue_cost += add_stmt_cost (target_cost_data, 1,
3184 vec_to_scalar, stmt_info, 0,
3185 vect_epilogue);
3187 else
3188 /* Use extracts and reduction op for final reduction. For N
3189 elements, we have N extracts and N-1 reduction ops. */
3190 epilogue_cost += add_stmt_cost (target_cost_data,
3191 nelements + nelements - 1,
3192 vector_stmt, stmt_info, 0,
3193 vect_epilogue);
3197 if (dump_enabled_p ())
3198 dump_printf (MSG_NOTE,
3199 "vect_model_reduction_cost: inside_cost = %d, "
3200 "prologue_cost = %d, epilogue_cost = %d .\n", inside_cost,
3201 prologue_cost, epilogue_cost);
3203 return true;
3207 /* Function vect_model_induction_cost.
3209 Models cost for induction operations. */
3211 static void
3212 vect_model_induction_cost (stmt_vec_info stmt_info, int ncopies)
3214 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3215 void *target_cost_data = LOOP_VINFO_TARGET_COST_DATA (loop_vinfo);
3216 unsigned inside_cost, prologue_cost;
3218 /* loop cost for vec_loop. */
3219 inside_cost = add_stmt_cost (target_cost_data, ncopies, vector_stmt,
3220 stmt_info, 0, vect_body);
3222 /* prologue cost for vec_init and vec_step. */
3223 prologue_cost = add_stmt_cost (target_cost_data, 2, scalar_to_vec,
3224 stmt_info, 0, vect_prologue);
3226 if (dump_enabled_p ())
3227 dump_printf_loc (MSG_NOTE, vect_location,
3228 "vect_model_induction_cost: inside_cost = %d, "
3229 "prologue_cost = %d .\n", inside_cost, prologue_cost);
3233 /* Function get_initial_def_for_induction
3235 Input:
3236 STMT - a stmt that performs an induction operation in the loop.
3237 IV_PHI - the initial value of the induction variable
3239 Output:
3240 Return a vector variable, initialized with the first VF values of
3241 the induction variable. E.g., for an iv with IV_PHI='X' and
3242 evolution S, for a vector of 4 units, we want to return:
3243 [X, X + S, X + 2*S, X + 3*S]. */
3245 static tree
3246 get_initial_def_for_induction (gimple iv_phi)
3248 stmt_vec_info stmt_vinfo = vinfo_for_stmt (iv_phi);
3249 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
3250 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
3251 tree vectype;
3252 int nunits;
3253 edge pe = loop_preheader_edge (loop);
3254 struct loop *iv_loop;
3255 basic_block new_bb;
3256 tree new_vec, vec_init, vec_step, t;
3257 tree new_var;
3258 tree new_name;
3259 gimple init_stmt, induction_phi, new_stmt;
3260 tree induc_def, vec_def, vec_dest;
3261 tree init_expr, step_expr;
3262 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
3263 int i;
3264 int ncopies;
3265 tree expr;
3266 stmt_vec_info phi_info = vinfo_for_stmt (iv_phi);
3267 bool nested_in_vect_loop = false;
3268 gimple_seq stmts = NULL;
3269 imm_use_iterator imm_iter;
3270 use_operand_p use_p;
3271 gimple exit_phi;
3272 edge latch_e;
3273 tree loop_arg;
3274 gimple_stmt_iterator si;
3275 basic_block bb = gimple_bb (iv_phi);
3276 tree stepvectype;
3277 tree resvectype;
3279 /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop? */
3280 if (nested_in_vect_loop_p (loop, iv_phi))
3282 nested_in_vect_loop = true;
3283 iv_loop = loop->inner;
3285 else
3286 iv_loop = loop;
3287 gcc_assert (iv_loop == (gimple_bb (iv_phi))->loop_father);
3289 latch_e = loop_latch_edge (iv_loop);
3290 loop_arg = PHI_ARG_DEF_FROM_EDGE (iv_phi, latch_e);
3292 step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (phi_info);
3293 gcc_assert (step_expr != NULL_TREE);
3295 pe = loop_preheader_edge (iv_loop);
3296 init_expr = PHI_ARG_DEF_FROM_EDGE (iv_phi,
3297 loop_preheader_edge (iv_loop));
3299 vectype = get_vectype_for_scalar_type (TREE_TYPE (init_expr));
3300 resvectype = get_vectype_for_scalar_type (TREE_TYPE (PHI_RESULT (iv_phi)));
3301 gcc_assert (vectype);
3302 nunits = TYPE_VECTOR_SUBPARTS (vectype);
3303 ncopies = vf / nunits;
3305 gcc_assert (phi_info);
3306 gcc_assert (ncopies >= 1);
3308 /* Convert the step to the desired type. */
3309 step_expr = force_gimple_operand (fold_convert (TREE_TYPE (vectype),
3310 step_expr),
3311 &stmts, true, NULL_TREE);
3312 if (stmts)
3314 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
3315 gcc_assert (!new_bb);
3318 /* Find the first insertion point in the BB. */
3319 si = gsi_after_labels (bb);
3321 /* Create the vector that holds the initial_value of the induction. */
3322 if (nested_in_vect_loop)
3324 /* iv_loop is nested in the loop to be vectorized. init_expr had already
3325 been created during vectorization of previous stmts. We obtain it
3326 from the STMT_VINFO_VEC_STMT of the defining stmt. */
3327 vec_init = vect_get_vec_def_for_operand (init_expr, iv_phi, NULL);
3328 /* If the initial value is not of proper type, convert it. */
3329 if (!useless_type_conversion_p (vectype, TREE_TYPE (vec_init)))
3331 new_stmt = gimple_build_assign_with_ops
3332 (VIEW_CONVERT_EXPR,
3333 vect_get_new_vect_var (vectype, vect_simple_var, "vec_iv_"),
3334 build1 (VIEW_CONVERT_EXPR, vectype, vec_init), NULL_TREE);
3335 vec_init = make_ssa_name (gimple_assign_lhs (new_stmt), new_stmt);
3336 gimple_assign_set_lhs (new_stmt, vec_init);
3337 new_bb = gsi_insert_on_edge_immediate (loop_preheader_edge (iv_loop),
3338 new_stmt);
3339 gcc_assert (!new_bb);
3340 set_vinfo_for_stmt (new_stmt,
3341 new_stmt_vec_info (new_stmt, loop_vinfo, NULL));
3344 else
3346 vec<constructor_elt, va_gc> *v;
3348 /* iv_loop is the loop to be vectorized. Create:
3349 vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr) */
3350 new_var = vect_get_new_vect_var (TREE_TYPE (vectype),
3351 vect_scalar_var, "var_");
3352 new_name = force_gimple_operand (fold_convert (TREE_TYPE (vectype),
3353 init_expr),
3354 &stmts, false, new_var);
3355 if (stmts)
3357 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
3358 gcc_assert (!new_bb);
3361 vec_alloc (v, nunits);
3362 bool constant_p = is_gimple_min_invariant (new_name);
3363 CONSTRUCTOR_APPEND_ELT (v, NULL_TREE, new_name);
3364 for (i = 1; i < nunits; i++)
3366 /* Create: new_name_i = new_name + step_expr */
3367 new_name = fold_build2 (PLUS_EXPR, TREE_TYPE (new_name),
3368 new_name, step_expr);
3369 if (!is_gimple_min_invariant (new_name))
3371 init_stmt = gimple_build_assign (new_var, new_name);
3372 new_name = make_ssa_name (new_var, init_stmt);
3373 gimple_assign_set_lhs (init_stmt, new_name);
3374 new_bb = gsi_insert_on_edge_immediate (pe, init_stmt);
3375 gcc_assert (!new_bb);
3376 if (dump_enabled_p ())
3378 dump_printf_loc (MSG_NOTE, vect_location,
3379 "created new init_stmt: ");
3380 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, init_stmt, 0);
3381 dump_printf (MSG_NOTE, "\n");
3383 constant_p = false;
3385 CONSTRUCTOR_APPEND_ELT (v, NULL_TREE, new_name);
3387 /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1] */
3388 if (constant_p)
3389 new_vec = build_vector_from_ctor (vectype, v);
3390 else
3391 new_vec = build_constructor (vectype, v);
3392 vec_init = vect_init_vector (iv_phi, new_vec, vectype, NULL);
3396 /* Create the vector that holds the step of the induction. */
3397 if (nested_in_vect_loop)
3398 /* iv_loop is nested in the loop to be vectorized. Generate:
3399 vec_step = [S, S, S, S] */
3400 new_name = step_expr;
3401 else
3403 /* iv_loop is the loop to be vectorized. Generate:
3404 vec_step = [VF*S, VF*S, VF*S, VF*S] */
3405 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr)))
3407 expr = build_int_cst (integer_type_node, vf);
3408 expr = fold_convert (TREE_TYPE (step_expr), expr);
3410 else
3411 expr = build_int_cst (TREE_TYPE (step_expr), vf);
3412 new_name = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr),
3413 expr, step_expr);
3414 if (TREE_CODE (step_expr) == SSA_NAME)
3415 new_name = vect_init_vector (iv_phi, new_name,
3416 TREE_TYPE (step_expr), NULL);
3419 t = unshare_expr (new_name);
3420 gcc_assert (CONSTANT_CLASS_P (new_name)
3421 || TREE_CODE (new_name) == SSA_NAME);
3422 stepvectype = get_vectype_for_scalar_type (TREE_TYPE (new_name));
3423 gcc_assert (stepvectype);
3424 new_vec = build_vector_from_val (stepvectype, t);
3425 vec_step = vect_init_vector (iv_phi, new_vec, stepvectype, NULL);
3428 /* Create the following def-use cycle:
3429 loop prolog:
3430 vec_init = ...
3431 vec_step = ...
3432 loop:
3433 vec_iv = PHI <vec_init, vec_loop>
3435 STMT
3437 vec_loop = vec_iv + vec_step; */
3439 /* Create the induction-phi that defines the induction-operand. */
3440 vec_dest = vect_get_new_vect_var (vectype, vect_simple_var, "vec_iv_");
3441 induction_phi = create_phi_node (vec_dest, iv_loop->header);
3442 set_vinfo_for_stmt (induction_phi,
3443 new_stmt_vec_info (induction_phi, loop_vinfo, NULL));
3444 induc_def = PHI_RESULT (induction_phi);
3446 /* Create the iv update inside the loop */
3447 new_stmt = gimple_build_assign_with_ops (PLUS_EXPR, vec_dest,
3448 induc_def, vec_step);
3449 vec_def = make_ssa_name (vec_dest, new_stmt);
3450 gimple_assign_set_lhs (new_stmt, vec_def);
3451 gsi_insert_before (&si, new_stmt, GSI_SAME_STMT);
3452 set_vinfo_for_stmt (new_stmt, new_stmt_vec_info (new_stmt, loop_vinfo,
3453 NULL));
3455 /* Set the arguments of the phi node: */
3456 add_phi_arg (induction_phi, vec_init, pe, UNKNOWN_LOCATION);
3457 add_phi_arg (induction_phi, vec_def, loop_latch_edge (iv_loop),
3458 UNKNOWN_LOCATION);
3461 /* In case that vectorization factor (VF) is bigger than the number
3462 of elements that we can fit in a vectype (nunits), we have to generate
3463 more than one vector stmt - i.e - we need to "unroll" the
3464 vector stmt by a factor VF/nunits. For more details see documentation
3465 in vectorizable_operation. */
3467 if (ncopies > 1)
3469 stmt_vec_info prev_stmt_vinfo;
3470 /* FORNOW. This restriction should be relaxed. */
3471 gcc_assert (!nested_in_vect_loop);
3473 /* Create the vector that holds the step of the induction. */
3474 if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr)))
3476 expr = build_int_cst (integer_type_node, nunits);
3477 expr = fold_convert (TREE_TYPE (step_expr), expr);
3479 else
3480 expr = build_int_cst (TREE_TYPE (step_expr), nunits);
3481 new_name = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr),
3482 expr, step_expr);
3483 if (TREE_CODE (step_expr) == SSA_NAME)
3484 new_name = vect_init_vector (iv_phi, new_name,
3485 TREE_TYPE (step_expr), NULL);
3486 t = unshare_expr (new_name);
3487 gcc_assert (CONSTANT_CLASS_P (new_name)
3488 || TREE_CODE (new_name) == SSA_NAME);
3489 new_vec = build_vector_from_val (stepvectype, t);
3490 vec_step = vect_init_vector (iv_phi, new_vec, stepvectype, NULL);
3492 vec_def = induc_def;
3493 prev_stmt_vinfo = vinfo_for_stmt (induction_phi);
3494 for (i = 1; i < ncopies; i++)
3496 /* vec_i = vec_prev + vec_step */
3497 new_stmt = gimple_build_assign_with_ops (PLUS_EXPR, vec_dest,
3498 vec_def, vec_step);
3499 vec_def = make_ssa_name (vec_dest, new_stmt);
3500 gimple_assign_set_lhs (new_stmt, vec_def);
3502 gsi_insert_before (&si, new_stmt, GSI_SAME_STMT);
3503 if (!useless_type_conversion_p (resvectype, vectype))
3505 new_stmt = gimple_build_assign_with_ops
3506 (VIEW_CONVERT_EXPR,
3507 vect_get_new_vect_var (resvectype, vect_simple_var,
3508 "vec_iv_"),
3509 build1 (VIEW_CONVERT_EXPR, resvectype,
3510 gimple_assign_lhs (new_stmt)), NULL_TREE);
3511 gimple_assign_set_lhs (new_stmt,
3512 make_ssa_name
3513 (gimple_assign_lhs (new_stmt), new_stmt));
3514 gsi_insert_before (&si, new_stmt, GSI_SAME_STMT);
3516 set_vinfo_for_stmt (new_stmt,
3517 new_stmt_vec_info (new_stmt, loop_vinfo, NULL));
3518 STMT_VINFO_RELATED_STMT (prev_stmt_vinfo) = new_stmt;
3519 prev_stmt_vinfo = vinfo_for_stmt (new_stmt);
3523 if (nested_in_vect_loop)
3525 /* Find the loop-closed exit-phi of the induction, and record
3526 the final vector of induction results: */
3527 exit_phi = NULL;
3528 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, loop_arg)
3530 gimple use_stmt = USE_STMT (use_p);
3531 if (is_gimple_debug (use_stmt))
3532 continue;
3534 if (!flow_bb_inside_loop_p (iv_loop, gimple_bb (use_stmt)))
3536 exit_phi = use_stmt;
3537 break;
3540 if (exit_phi)
3542 stmt_vec_info stmt_vinfo = vinfo_for_stmt (exit_phi);
3543 /* FORNOW. Currently not supporting the case that an inner-loop induction
3544 is not used in the outer-loop (i.e. only outside the outer-loop). */
3545 gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo)
3546 && !STMT_VINFO_LIVE_P (stmt_vinfo));
3548 STMT_VINFO_VEC_STMT (stmt_vinfo) = new_stmt;
3549 if (dump_enabled_p ())
3551 dump_printf_loc (MSG_NOTE, vect_location,
3552 "vector of inductions after inner-loop:");
3553 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, new_stmt, 0);
3554 dump_printf (MSG_NOTE, "\n");
3560 if (dump_enabled_p ())
3562 dump_printf_loc (MSG_NOTE, vect_location,
3563 "transform induction: created def-use cycle: ");
3564 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, induction_phi, 0);
3565 dump_printf (MSG_NOTE, "\n");
3566 dump_gimple_stmt (MSG_NOTE, TDF_SLIM,
3567 SSA_NAME_DEF_STMT (vec_def), 0);
3568 dump_printf (MSG_NOTE, "\n");
3571 STMT_VINFO_VEC_STMT (phi_info) = induction_phi;
3572 if (!useless_type_conversion_p (resvectype, vectype))
3574 new_stmt = gimple_build_assign_with_ops
3575 (VIEW_CONVERT_EXPR,
3576 vect_get_new_vect_var (resvectype, vect_simple_var, "vec_iv_"),
3577 build1 (VIEW_CONVERT_EXPR, resvectype, induc_def), NULL_TREE);
3578 induc_def = make_ssa_name (gimple_assign_lhs (new_stmt), new_stmt);
3579 gimple_assign_set_lhs (new_stmt, induc_def);
3580 si = gsi_after_labels (bb);
3581 gsi_insert_before (&si, new_stmt, GSI_SAME_STMT);
3582 set_vinfo_for_stmt (new_stmt,
3583 new_stmt_vec_info (new_stmt, loop_vinfo, NULL));
3584 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_stmt))
3585 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (induction_phi));
3588 return induc_def;
3592 /* Function get_initial_def_for_reduction
3594 Input:
3595 STMT - a stmt that performs a reduction operation in the loop.
3596 INIT_VAL - the initial value of the reduction variable
3598 Output:
3599 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
3600 of the reduction (used for adjusting the epilog - see below).
3601 Return a vector variable, initialized according to the operation that STMT
3602 performs. This vector will be used as the initial value of the
3603 vector of partial results.
3605 Option1 (adjust in epilog): Initialize the vector as follows:
3606 add/bit or/xor: [0,0,...,0,0]
3607 mult/bit and: [1,1,...,1,1]
3608 min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
3609 and when necessary (e.g. add/mult case) let the caller know
3610 that it needs to adjust the result by init_val.
3612 Option2: Initialize the vector as follows:
3613 add/bit or/xor: [init_val,0,0,...,0]
3614 mult/bit and: [init_val,1,1,...,1]
3615 min/max/cond_expr: [init_val,init_val,...,init_val]
3616 and no adjustments are needed.
3618 For example, for the following code:
3620 s = init_val;
3621 for (i=0;i<n;i++)
3622 s = s + a[i];
3624 STMT is 's = s + a[i]', and the reduction variable is 's'.
3625 For a vector of 4 units, we want to return either [0,0,0,init_val],
3626 or [0,0,0,0] and let the caller know that it needs to adjust
3627 the result at the end by 'init_val'.
3629 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
3630 initialization vector is simpler (same element in all entries), if
3631 ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
3633 A cost model should help decide between these two schemes. */
3635 tree
3636 get_initial_def_for_reduction (gimple stmt, tree init_val,
3637 tree *adjustment_def)
3639 stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
3640 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
3641 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
3642 tree scalar_type = TREE_TYPE (init_val);
3643 tree vectype = get_vectype_for_scalar_type (scalar_type);
3644 int nunits;
3645 enum tree_code code = gimple_assign_rhs_code (stmt);
3646 tree def_for_init;
3647 tree init_def;
3648 tree *elts;
3649 int i;
3650 bool nested_in_vect_loop = false;
3651 tree init_value;
3652 REAL_VALUE_TYPE real_init_val = dconst0;
3653 int int_init_val = 0;
3654 gimple def_stmt = NULL;
3656 gcc_assert (vectype);
3657 nunits = TYPE_VECTOR_SUBPARTS (vectype);
3659 gcc_assert (POINTER_TYPE_P (scalar_type) || INTEGRAL_TYPE_P (scalar_type)
3660 || SCALAR_FLOAT_TYPE_P (scalar_type));
3662 if (nested_in_vect_loop_p (loop, stmt))
3663 nested_in_vect_loop = true;
3664 else
3665 gcc_assert (loop == (gimple_bb (stmt))->loop_father);
3667 /* In case of double reduction we only create a vector variable to be put
3668 in the reduction phi node. The actual statement creation is done in
3669 vect_create_epilog_for_reduction. */
3670 if (adjustment_def && nested_in_vect_loop
3671 && TREE_CODE (init_val) == SSA_NAME
3672 && (def_stmt = SSA_NAME_DEF_STMT (init_val))
3673 && gimple_code (def_stmt) == GIMPLE_PHI
3674 && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
3675 && vinfo_for_stmt (def_stmt)
3676 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
3677 == vect_double_reduction_def)
3679 *adjustment_def = NULL;
3680 return vect_create_destination_var (init_val, vectype);
3683 if (TREE_CONSTANT (init_val))
3685 if (SCALAR_FLOAT_TYPE_P (scalar_type))
3686 init_value = build_real (scalar_type, TREE_REAL_CST (init_val));
3687 else
3688 init_value = build_int_cst (scalar_type, TREE_INT_CST_LOW (init_val));
3690 else
3691 init_value = init_val;
3693 switch (code)
3695 case WIDEN_SUM_EXPR:
3696 case DOT_PROD_EXPR:
3697 case SAD_EXPR:
3698 case PLUS_EXPR:
3699 case MINUS_EXPR:
3700 case BIT_IOR_EXPR:
3701 case BIT_XOR_EXPR:
3702 case MULT_EXPR:
3703 case BIT_AND_EXPR:
3704 /* ADJUSMENT_DEF is NULL when called from
3705 vect_create_epilog_for_reduction to vectorize double reduction. */
3706 if (adjustment_def)
3708 if (nested_in_vect_loop)
3709 *adjustment_def = vect_get_vec_def_for_operand (init_val, stmt,
3710 NULL);
3711 else
3712 *adjustment_def = init_val;
3715 if (code == MULT_EXPR)
3717 real_init_val = dconst1;
3718 int_init_val = 1;
3721 if (code == BIT_AND_EXPR)
3722 int_init_val = -1;
3724 if (SCALAR_FLOAT_TYPE_P (scalar_type))
3725 def_for_init = build_real (scalar_type, real_init_val);
3726 else
3727 def_for_init = build_int_cst (scalar_type, int_init_val);
3729 /* Create a vector of '0' or '1' except the first element. */
3730 elts = XALLOCAVEC (tree, nunits);
3731 for (i = nunits - 2; i >= 0; --i)
3732 elts[i + 1] = def_for_init;
3734 /* Option1: the first element is '0' or '1' as well. */
3735 if (adjustment_def)
3737 elts[0] = def_for_init;
3738 init_def = build_vector (vectype, elts);
3739 break;
3742 /* Option2: the first element is INIT_VAL. */
3743 elts[0] = init_val;
3744 if (TREE_CONSTANT (init_val))
3745 init_def = build_vector (vectype, elts);
3746 else
3748 vec<constructor_elt, va_gc> *v;
3749 vec_alloc (v, nunits);
3750 CONSTRUCTOR_APPEND_ELT (v, NULL_TREE, init_val);
3751 for (i = 1; i < nunits; ++i)
3752 CONSTRUCTOR_APPEND_ELT (v, NULL_TREE, elts[i]);
3753 init_def = build_constructor (vectype, v);
3756 break;
3758 case MIN_EXPR:
3759 case MAX_EXPR:
3760 case COND_EXPR:
3761 if (adjustment_def)
3763 *adjustment_def = NULL_TREE;
3764 init_def = vect_get_vec_def_for_operand (init_val, stmt, NULL);
3765 break;
3768 init_def = build_vector_from_val (vectype, init_value);
3769 break;
3771 default:
3772 gcc_unreachable ();
3775 return init_def;
3779 /* Function vect_create_epilog_for_reduction
3781 Create code at the loop-epilog to finalize the result of a reduction
3782 computation.
3784 VECT_DEFS is list of vector of partial results, i.e., the lhs's of vector
3785 reduction statements.
3786 STMT is the scalar reduction stmt that is being vectorized.
3787 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
3788 number of elements that we can fit in a vectype (nunits). In this case
3789 we have to generate more than one vector stmt - i.e - we need to "unroll"
3790 the vector stmt by a factor VF/nunits. For more details see documentation
3791 in vectorizable_operation.
3792 REDUC_CODE is the tree-code for the epilog reduction.
3793 REDUCTION_PHIS is a list of the phi-nodes that carry the reduction
3794 computation.
3795 REDUC_INDEX is the index of the operand in the right hand side of the
3796 statement that is defined by REDUCTION_PHI.
3797 DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
3798 SLP_NODE is an SLP node containing a group of reduction statements. The
3799 first one in this group is STMT.
3801 This function:
3802 1. Creates the reduction def-use cycles: sets the arguments for
3803 REDUCTION_PHIS:
3804 The loop-entry argument is the vectorized initial-value of the reduction.
3805 The loop-latch argument is taken from VECT_DEFS - the vector of partial
3806 sums.
3807 2. "Reduces" each vector of partial results VECT_DEFS into a single result,
3808 by applying the operation specified by REDUC_CODE if available, or by
3809 other means (whole-vector shifts or a scalar loop).
3810 The function also creates a new phi node at the loop exit to preserve
3811 loop-closed form, as illustrated below.
3813 The flow at the entry to this function:
3815 loop:
3816 vec_def = phi <null, null> # REDUCTION_PHI
3817 VECT_DEF = vector_stmt # vectorized form of STMT
3818 s_loop = scalar_stmt # (scalar) STMT
3819 loop_exit:
3820 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3821 use <s_out0>
3822 use <s_out0>
3824 The above is transformed by this function into:
3826 loop:
3827 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3828 VECT_DEF = vector_stmt # vectorized form of STMT
3829 s_loop = scalar_stmt # (scalar) STMT
3830 loop_exit:
3831 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
3832 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
3833 v_out2 = reduce <v_out1>
3834 s_out3 = extract_field <v_out2, 0>
3835 s_out4 = adjust_result <s_out3>
3836 use <s_out4>
3837 use <s_out4>
3840 static void
3841 vect_create_epilog_for_reduction (vec<tree> vect_defs, gimple stmt,
3842 int ncopies, enum tree_code reduc_code,
3843 vec<gimple> reduction_phis,
3844 int reduc_index, bool double_reduc,
3845 slp_tree slp_node)
3847 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3848 stmt_vec_info prev_phi_info;
3849 tree vectype;
3850 enum machine_mode mode;
3851 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3852 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo), *outer_loop = NULL;
3853 basic_block exit_bb;
3854 tree scalar_dest;
3855 tree scalar_type;
3856 gimple new_phi = NULL, phi;
3857 gimple_stmt_iterator exit_gsi;
3858 tree vec_dest;
3859 tree new_temp = NULL_TREE, new_dest, new_name, new_scalar_dest;
3860 gimple epilog_stmt = NULL;
3861 enum tree_code code = gimple_assign_rhs_code (stmt);
3862 gimple exit_phi;
3863 tree bitsize, bitpos;
3864 tree adjustment_def = NULL;
3865 tree vec_initial_def = NULL;
3866 tree reduction_op, expr, def;
3867 tree orig_name, scalar_result;
3868 imm_use_iterator imm_iter, phi_imm_iter;
3869 use_operand_p use_p, phi_use_p;
3870 bool extract_scalar_result = false;
3871 gimple use_stmt, orig_stmt, reduction_phi = NULL;
3872 bool nested_in_vect_loop = false;
3873 auto_vec<gimple> new_phis;
3874 auto_vec<gimple> inner_phis;
3875 enum vect_def_type dt = vect_unknown_def_type;
3876 int j, i;
3877 auto_vec<tree> scalar_results;
3878 unsigned int group_size = 1, k, ratio;
3879 auto_vec<tree> vec_initial_defs;
3880 auto_vec<gimple> phis;
3881 bool slp_reduc = false;
3882 tree new_phi_result;
3883 gimple inner_phi = NULL;
3885 if (slp_node)
3886 group_size = SLP_TREE_SCALAR_STMTS (slp_node).length ();
3888 if (nested_in_vect_loop_p (loop, stmt))
3890 outer_loop = loop;
3891 loop = loop->inner;
3892 nested_in_vect_loop = true;
3893 gcc_assert (!slp_node);
3896 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
3898 case GIMPLE_SINGLE_RHS:
3899 gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt))
3900 == ternary_op);
3901 reduction_op = TREE_OPERAND (gimple_assign_rhs1 (stmt), reduc_index);
3902 break;
3903 case GIMPLE_UNARY_RHS:
3904 reduction_op = gimple_assign_rhs1 (stmt);
3905 break;
3906 case GIMPLE_BINARY_RHS:
3907 reduction_op = reduc_index ?
3908 gimple_assign_rhs2 (stmt) : gimple_assign_rhs1 (stmt);
3909 break;
3910 case GIMPLE_TERNARY_RHS:
3911 reduction_op = gimple_op (stmt, reduc_index + 1);
3912 break;
3913 default:
3914 gcc_unreachable ();
3917 vectype = get_vectype_for_scalar_type (TREE_TYPE (reduction_op));
3918 gcc_assert (vectype);
3919 mode = TYPE_MODE (vectype);
3921 /* 1. Create the reduction def-use cycle:
3922 Set the arguments of REDUCTION_PHIS, i.e., transform
3924 loop:
3925 vec_def = phi <null, null> # REDUCTION_PHI
3926 VECT_DEF = vector_stmt # vectorized form of STMT
3929 into:
3931 loop:
3932 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
3933 VECT_DEF = vector_stmt # vectorized form of STMT
3936 (in case of SLP, do it for all the phis). */
3938 /* Get the loop-entry arguments. */
3939 if (slp_node)
3940 vect_get_vec_defs (reduction_op, NULL_TREE, stmt, &vec_initial_defs,
3941 NULL, slp_node, reduc_index);
3942 else
3944 vec_initial_defs.create (1);
3945 /* For the case of reduction, vect_get_vec_def_for_operand returns
3946 the scalar def before the loop, that defines the initial value
3947 of the reduction variable. */
3948 vec_initial_def = vect_get_vec_def_for_operand (reduction_op, stmt,
3949 &adjustment_def);
3950 vec_initial_defs.quick_push (vec_initial_def);
3953 /* Set phi nodes arguments. */
3954 FOR_EACH_VEC_ELT (reduction_phis, i, phi)
3956 tree vec_init_def, def;
3957 gimple_seq stmts;
3958 vec_init_def = force_gimple_operand (vec_initial_defs[i], &stmts,
3959 true, NULL_TREE);
3960 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
3961 def = vect_defs[i];
3962 for (j = 0; j < ncopies; j++)
3964 /* Set the loop-entry arg of the reduction-phi. */
3965 add_phi_arg (phi, vec_init_def, loop_preheader_edge (loop),
3966 UNKNOWN_LOCATION);
3968 /* Set the loop-latch arg for the reduction-phi. */
3969 if (j > 0)
3970 def = vect_get_vec_def_for_stmt_copy (vect_unknown_def_type, def);
3972 add_phi_arg (phi, def, loop_latch_edge (loop), UNKNOWN_LOCATION);
3974 if (dump_enabled_p ())
3976 dump_printf_loc (MSG_NOTE, vect_location,
3977 "transform reduction: created def-use cycle: ");
3978 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
3979 dump_printf (MSG_NOTE, "\n");
3980 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, SSA_NAME_DEF_STMT (def), 0);
3981 dump_printf (MSG_NOTE, "\n");
3984 phi = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi));
3988 /* 2. Create epilog code.
3989 The reduction epilog code operates across the elements of the vector
3990 of partial results computed by the vectorized loop.
3991 The reduction epilog code consists of:
3993 step 1: compute the scalar result in a vector (v_out2)
3994 step 2: extract the scalar result (s_out3) from the vector (v_out2)
3995 step 3: adjust the scalar result (s_out3) if needed.
3997 Step 1 can be accomplished using one the following three schemes:
3998 (scheme 1) using reduc_code, if available.
3999 (scheme 2) using whole-vector shifts, if available.
4000 (scheme 3) using a scalar loop. In this case steps 1+2 above are
4001 combined.
4003 The overall epilog code looks like this:
4005 s_out0 = phi <s_loop> # original EXIT_PHI
4006 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4007 v_out2 = reduce <v_out1> # step 1
4008 s_out3 = extract_field <v_out2, 0> # step 2
4009 s_out4 = adjust_result <s_out3> # step 3
4011 (step 3 is optional, and steps 1 and 2 may be combined).
4012 Lastly, the uses of s_out0 are replaced by s_out4. */
4015 /* 2.1 Create new loop-exit-phis to preserve loop-closed form:
4016 v_out1 = phi <VECT_DEF>
4017 Store them in NEW_PHIS. */
4019 exit_bb = single_exit (loop)->dest;
4020 prev_phi_info = NULL;
4021 new_phis.create (vect_defs.length ());
4022 FOR_EACH_VEC_ELT (vect_defs, i, def)
4024 for (j = 0; j < ncopies; j++)
4026 tree new_def = copy_ssa_name (def, NULL);
4027 phi = create_phi_node (new_def, exit_bb);
4028 set_vinfo_for_stmt (phi, new_stmt_vec_info (phi, loop_vinfo, NULL));
4029 if (j == 0)
4030 new_phis.quick_push (phi);
4031 else
4033 def = vect_get_vec_def_for_stmt_copy (dt, def);
4034 STMT_VINFO_RELATED_STMT (prev_phi_info) = phi;
4037 SET_PHI_ARG_DEF (phi, single_exit (loop)->dest_idx, def);
4038 prev_phi_info = vinfo_for_stmt (phi);
4042 /* The epilogue is created for the outer-loop, i.e., for the loop being
4043 vectorized. Create exit phis for the outer loop. */
4044 if (double_reduc)
4046 loop = outer_loop;
4047 exit_bb = single_exit (loop)->dest;
4048 inner_phis.create (vect_defs.length ());
4049 FOR_EACH_VEC_ELT (new_phis, i, phi)
4051 tree new_result = copy_ssa_name (PHI_RESULT (phi), NULL);
4052 gimple outer_phi = create_phi_node (new_result, exit_bb);
4053 SET_PHI_ARG_DEF (outer_phi, single_exit (loop)->dest_idx,
4054 PHI_RESULT (phi));
4055 set_vinfo_for_stmt (outer_phi, new_stmt_vec_info (outer_phi,
4056 loop_vinfo, NULL));
4057 inner_phis.quick_push (phi);
4058 new_phis[i] = outer_phi;
4059 prev_phi_info = vinfo_for_stmt (outer_phi);
4060 while (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi)))
4062 phi = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi));
4063 new_result = copy_ssa_name (PHI_RESULT (phi), NULL);
4064 outer_phi = create_phi_node (new_result, exit_bb);
4065 SET_PHI_ARG_DEF (outer_phi, single_exit (loop)->dest_idx,
4066 PHI_RESULT (phi));
4067 set_vinfo_for_stmt (outer_phi, new_stmt_vec_info (outer_phi,
4068 loop_vinfo, NULL));
4069 STMT_VINFO_RELATED_STMT (prev_phi_info) = outer_phi;
4070 prev_phi_info = vinfo_for_stmt (outer_phi);
4075 exit_gsi = gsi_after_labels (exit_bb);
4077 /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
4078 (i.e. when reduc_code is not available) and in the final adjustment
4079 code (if needed). Also get the original scalar reduction variable as
4080 defined in the loop. In case STMT is a "pattern-stmt" (i.e. - it
4081 represents a reduction pattern), the tree-code and scalar-def are
4082 taken from the original stmt that the pattern-stmt (STMT) replaces.
4083 Otherwise (it is a regular reduction) - the tree-code and scalar-def
4084 are taken from STMT. */
4086 orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
4087 if (!orig_stmt)
4089 /* Regular reduction */
4090 orig_stmt = stmt;
4092 else
4094 /* Reduction pattern */
4095 stmt_vec_info stmt_vinfo = vinfo_for_stmt (orig_stmt);
4096 gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo));
4097 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo) == stmt);
4100 code = gimple_assign_rhs_code (orig_stmt);
4101 /* For MINUS_EXPR the initial vector is [init_val,0,...,0], therefore,
4102 partial results are added and not subtracted. */
4103 if (code == MINUS_EXPR)
4104 code = PLUS_EXPR;
4106 scalar_dest = gimple_assign_lhs (orig_stmt);
4107 scalar_type = TREE_TYPE (scalar_dest);
4108 scalar_results.create (group_size);
4109 new_scalar_dest = vect_create_destination_var (scalar_dest, NULL);
4110 bitsize = TYPE_SIZE (scalar_type);
4112 /* In case this is a reduction in an inner-loop while vectorizing an outer
4113 loop - we don't need to extract a single scalar result at the end of the
4114 inner-loop (unless it is double reduction, i.e., the use of reduction is
4115 outside the outer-loop). The final vector of partial results will be used
4116 in the vectorized outer-loop, or reduced to a scalar result at the end of
4117 the outer-loop. */
4118 if (nested_in_vect_loop && !double_reduc)
4119 goto vect_finalize_reduction;
4121 /* SLP reduction without reduction chain, e.g.,
4122 # a1 = phi <a2, a0>
4123 # b1 = phi <b2, b0>
4124 a2 = operation (a1)
4125 b2 = operation (b1) */
4126 slp_reduc = (slp_node && !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)));
4128 /* In case of reduction chain, e.g.,
4129 # a1 = phi <a3, a0>
4130 a2 = operation (a1)
4131 a3 = operation (a2),
4133 we may end up with more than one vector result. Here we reduce them to
4134 one vector. */
4135 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
4137 tree first_vect = PHI_RESULT (new_phis[0]);
4138 tree tmp;
4139 gimple new_vec_stmt = NULL;
4141 vec_dest = vect_create_destination_var (scalar_dest, vectype);
4142 for (k = 1; k < new_phis.length (); k++)
4144 gimple next_phi = new_phis[k];
4145 tree second_vect = PHI_RESULT (next_phi);
4147 tmp = build2 (code, vectype, first_vect, second_vect);
4148 new_vec_stmt = gimple_build_assign (vec_dest, tmp);
4149 first_vect = make_ssa_name (vec_dest, new_vec_stmt);
4150 gimple_assign_set_lhs (new_vec_stmt, first_vect);
4151 gsi_insert_before (&exit_gsi, new_vec_stmt, GSI_SAME_STMT);
4154 new_phi_result = first_vect;
4155 if (new_vec_stmt)
4157 new_phis.truncate (0);
4158 new_phis.safe_push (new_vec_stmt);
4161 else
4162 new_phi_result = PHI_RESULT (new_phis[0]);
4164 /* 2.3 Create the reduction code, using one of the three schemes described
4165 above. In SLP we simply need to extract all the elements from the
4166 vector (without reducing them), so we use scalar shifts. */
4167 if (reduc_code != ERROR_MARK && !slp_reduc)
4169 tree tmp;
4171 /*** Case 1: Create:
4172 v_out2 = reduc_expr <v_out1> */
4174 if (dump_enabled_p ())
4175 dump_printf_loc (MSG_NOTE, vect_location,
4176 "Reduce using direct vector reduction.\n");
4178 vec_dest = vect_create_destination_var (scalar_dest, vectype);
4179 tmp = build1 (reduc_code, vectype, new_phi_result);
4180 epilog_stmt = gimple_build_assign (vec_dest, tmp);
4181 new_temp = make_ssa_name (vec_dest, epilog_stmt);
4182 gimple_assign_set_lhs (epilog_stmt, new_temp);
4183 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4185 extract_scalar_result = true;
4187 else
4189 enum tree_code shift_code = ERROR_MARK;
4190 bool have_whole_vector_shift = true;
4191 int bit_offset;
4192 int element_bitsize = tree_to_uhwi (bitsize);
4193 int vec_size_in_bits = tree_to_uhwi (TYPE_SIZE (vectype));
4194 tree vec_temp;
4196 if (optab_handler (vec_shr_optab, mode) != CODE_FOR_nothing)
4197 shift_code = VEC_RSHIFT_EXPR;
4198 else
4199 have_whole_vector_shift = false;
4201 /* Regardless of whether we have a whole vector shift, if we're
4202 emulating the operation via tree-vect-generic, we don't want
4203 to use it. Only the first round of the reduction is likely
4204 to still be profitable via emulation. */
4205 /* ??? It might be better to emit a reduction tree code here, so that
4206 tree-vect-generic can expand the first round via bit tricks. */
4207 if (!VECTOR_MODE_P (mode))
4208 have_whole_vector_shift = false;
4209 else
4211 optab optab = optab_for_tree_code (code, vectype, optab_default);
4212 if (optab_handler (optab, mode) == CODE_FOR_nothing)
4213 have_whole_vector_shift = false;
4216 if (have_whole_vector_shift && !slp_reduc)
4218 /*** Case 2: Create:
4219 for (offset = VS/2; offset >= element_size; offset/=2)
4221 Create: va' = vec_shift <va, offset>
4222 Create: va = vop <va, va'>
4223 } */
4225 if (dump_enabled_p ())
4226 dump_printf_loc (MSG_NOTE, vect_location,
4227 "Reduce using vector shifts\n");
4229 vec_dest = vect_create_destination_var (scalar_dest, vectype);
4230 new_temp = new_phi_result;
4231 for (bit_offset = vec_size_in_bits/2;
4232 bit_offset >= element_bitsize;
4233 bit_offset /= 2)
4235 tree bitpos = size_int (bit_offset);
4237 epilog_stmt = gimple_build_assign_with_ops (shift_code,
4238 vec_dest, new_temp, bitpos);
4239 new_name = make_ssa_name (vec_dest, epilog_stmt);
4240 gimple_assign_set_lhs (epilog_stmt, new_name);
4241 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4243 epilog_stmt = gimple_build_assign_with_ops (code, vec_dest,
4244 new_name, new_temp);
4245 new_temp = make_ssa_name (vec_dest, epilog_stmt);
4246 gimple_assign_set_lhs (epilog_stmt, new_temp);
4247 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4250 extract_scalar_result = true;
4252 else
4254 tree rhs;
4256 /*** Case 3: Create:
4257 s = extract_field <v_out2, 0>
4258 for (offset = element_size;
4259 offset < vector_size;
4260 offset += element_size;)
4262 Create: s' = extract_field <v_out2, offset>
4263 Create: s = op <s, s'> // For non SLP cases
4264 } */
4266 if (dump_enabled_p ())
4267 dump_printf_loc (MSG_NOTE, vect_location,
4268 "Reduce using scalar code.\n");
4270 vec_size_in_bits = tree_to_uhwi (TYPE_SIZE (vectype));
4271 FOR_EACH_VEC_ELT (new_phis, i, new_phi)
4273 if (gimple_code (new_phi) == GIMPLE_PHI)
4274 vec_temp = PHI_RESULT (new_phi);
4275 else
4276 vec_temp = gimple_assign_lhs (new_phi);
4277 rhs = build3 (BIT_FIELD_REF, scalar_type, vec_temp, bitsize,
4278 bitsize_zero_node);
4279 epilog_stmt = gimple_build_assign (new_scalar_dest, rhs);
4280 new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
4281 gimple_assign_set_lhs (epilog_stmt, new_temp);
4282 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4284 /* In SLP we don't need to apply reduction operation, so we just
4285 collect s' values in SCALAR_RESULTS. */
4286 if (slp_reduc)
4287 scalar_results.safe_push (new_temp);
4289 for (bit_offset = element_bitsize;
4290 bit_offset < vec_size_in_bits;
4291 bit_offset += element_bitsize)
4293 tree bitpos = bitsize_int (bit_offset);
4294 tree rhs = build3 (BIT_FIELD_REF, scalar_type, vec_temp,
4295 bitsize, bitpos);
4297 epilog_stmt = gimple_build_assign (new_scalar_dest, rhs);
4298 new_name = make_ssa_name (new_scalar_dest, epilog_stmt);
4299 gimple_assign_set_lhs (epilog_stmt, new_name);
4300 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4302 if (slp_reduc)
4304 /* In SLP we don't need to apply reduction operation, so
4305 we just collect s' values in SCALAR_RESULTS. */
4306 new_temp = new_name;
4307 scalar_results.safe_push (new_name);
4309 else
4311 epilog_stmt = gimple_build_assign_with_ops (code,
4312 new_scalar_dest, new_name, new_temp);
4313 new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
4314 gimple_assign_set_lhs (epilog_stmt, new_temp);
4315 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4320 /* The only case where we need to reduce scalar results in SLP, is
4321 unrolling. If the size of SCALAR_RESULTS is greater than
4322 GROUP_SIZE, we reduce them combining elements modulo
4323 GROUP_SIZE. */
4324 if (slp_reduc)
4326 tree res, first_res, new_res;
4327 gimple new_stmt;
4329 /* Reduce multiple scalar results in case of SLP unrolling. */
4330 for (j = group_size; scalar_results.iterate (j, &res);
4331 j++)
4333 first_res = scalar_results[j % group_size];
4334 new_stmt = gimple_build_assign_with_ops (code,
4335 new_scalar_dest, first_res, res);
4336 new_res = make_ssa_name (new_scalar_dest, new_stmt);
4337 gimple_assign_set_lhs (new_stmt, new_res);
4338 gsi_insert_before (&exit_gsi, new_stmt, GSI_SAME_STMT);
4339 scalar_results[j % group_size] = new_res;
4342 else
4343 /* Not SLP - we have one scalar to keep in SCALAR_RESULTS. */
4344 scalar_results.safe_push (new_temp);
4346 extract_scalar_result = false;
4350 /* 2.4 Extract the final scalar result. Create:
4351 s_out3 = extract_field <v_out2, bitpos> */
4353 if (extract_scalar_result)
4355 tree rhs;
4357 if (dump_enabled_p ())
4358 dump_printf_loc (MSG_NOTE, vect_location,
4359 "extract scalar result\n");
4361 if (BYTES_BIG_ENDIAN)
4362 bitpos = size_binop (MULT_EXPR,
4363 bitsize_int (TYPE_VECTOR_SUBPARTS (vectype) - 1),
4364 TYPE_SIZE (scalar_type));
4365 else
4366 bitpos = bitsize_zero_node;
4368 rhs = build3 (BIT_FIELD_REF, scalar_type, new_temp, bitsize, bitpos);
4369 epilog_stmt = gimple_build_assign (new_scalar_dest, rhs);
4370 new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
4371 gimple_assign_set_lhs (epilog_stmt, new_temp);
4372 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4373 scalar_results.safe_push (new_temp);
4376 vect_finalize_reduction:
4378 if (double_reduc)
4379 loop = loop->inner;
4381 /* 2.5 Adjust the final result by the initial value of the reduction
4382 variable. (When such adjustment is not needed, then
4383 'adjustment_def' is zero). For example, if code is PLUS we create:
4384 new_temp = loop_exit_def + adjustment_def */
4386 if (adjustment_def)
4388 gcc_assert (!slp_reduc);
4389 if (nested_in_vect_loop)
4391 new_phi = new_phis[0];
4392 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def)) == VECTOR_TYPE);
4393 expr = build2 (code, vectype, PHI_RESULT (new_phi), adjustment_def);
4394 new_dest = vect_create_destination_var (scalar_dest, vectype);
4396 else
4398 new_temp = scalar_results[0];
4399 gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def)) != VECTOR_TYPE);
4400 expr = build2 (code, scalar_type, new_temp, adjustment_def);
4401 new_dest = vect_create_destination_var (scalar_dest, scalar_type);
4404 epilog_stmt = gimple_build_assign (new_dest, expr);
4405 new_temp = make_ssa_name (new_dest, epilog_stmt);
4406 gimple_assign_set_lhs (epilog_stmt, new_temp);
4407 gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
4408 if (nested_in_vect_loop)
4410 set_vinfo_for_stmt (epilog_stmt,
4411 new_stmt_vec_info (epilog_stmt, loop_vinfo,
4412 NULL));
4413 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (epilog_stmt)) =
4414 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_phi));
4416 if (!double_reduc)
4417 scalar_results.quick_push (new_temp);
4418 else
4419 scalar_results[0] = new_temp;
4421 else
4422 scalar_results[0] = new_temp;
4424 new_phis[0] = epilog_stmt;
4427 /* 2.6 Handle the loop-exit phis. Replace the uses of scalar loop-exit
4428 phis with new adjusted scalar results, i.e., replace use <s_out0>
4429 with use <s_out4>.
4431 Transform:
4432 loop_exit:
4433 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4434 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4435 v_out2 = reduce <v_out1>
4436 s_out3 = extract_field <v_out2, 0>
4437 s_out4 = adjust_result <s_out3>
4438 use <s_out0>
4439 use <s_out0>
4441 into:
4443 loop_exit:
4444 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4445 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4446 v_out2 = reduce <v_out1>
4447 s_out3 = extract_field <v_out2, 0>
4448 s_out4 = adjust_result <s_out3>
4449 use <s_out4>
4450 use <s_out4> */
4453 /* In SLP reduction chain we reduce vector results into one vector if
4454 necessary, hence we set here GROUP_SIZE to 1. SCALAR_DEST is the LHS of
4455 the last stmt in the reduction chain, since we are looking for the loop
4456 exit phi node. */
4457 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
4459 scalar_dest = gimple_assign_lhs (
4460 SLP_TREE_SCALAR_STMTS (slp_node)[group_size - 1]);
4461 group_size = 1;
4464 /* In SLP we may have several statements in NEW_PHIS and REDUCTION_PHIS (in
4465 case that GROUP_SIZE is greater than vectorization factor). Therefore, we
4466 need to match SCALAR_RESULTS with corresponding statements. The first
4467 (GROUP_SIZE / number of new vector stmts) scalar results correspond to
4468 the first vector stmt, etc.
4469 (RATIO is equal to (GROUP_SIZE / number of new vector stmts)). */
4470 if (group_size > new_phis.length ())
4472 ratio = group_size / new_phis.length ();
4473 gcc_assert (!(group_size % new_phis.length ()));
4475 else
4476 ratio = 1;
4478 for (k = 0; k < group_size; k++)
4480 if (k % ratio == 0)
4482 epilog_stmt = new_phis[k / ratio];
4483 reduction_phi = reduction_phis[k / ratio];
4484 if (double_reduc)
4485 inner_phi = inner_phis[k / ratio];
4488 if (slp_reduc)
4490 gimple current_stmt = SLP_TREE_SCALAR_STMTS (slp_node)[k];
4492 orig_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (current_stmt));
4493 /* SLP statements can't participate in patterns. */
4494 gcc_assert (!orig_stmt);
4495 scalar_dest = gimple_assign_lhs (current_stmt);
4498 phis.create (3);
4499 /* Find the loop-closed-use at the loop exit of the original scalar
4500 result. (The reduction result is expected to have two immediate uses -
4501 one at the latch block, and one at the loop exit). */
4502 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, scalar_dest)
4503 if (!flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p)))
4504 && !is_gimple_debug (USE_STMT (use_p)))
4505 phis.safe_push (USE_STMT (use_p));
4507 /* While we expect to have found an exit_phi because of loop-closed-ssa
4508 form we can end up without one if the scalar cycle is dead. */
4510 FOR_EACH_VEC_ELT (phis, i, exit_phi)
4512 if (outer_loop)
4514 stmt_vec_info exit_phi_vinfo = vinfo_for_stmt (exit_phi);
4515 gimple vect_phi;
4517 /* FORNOW. Currently not supporting the case that an inner-loop
4518 reduction is not used in the outer-loop (but only outside the
4519 outer-loop), unless it is double reduction. */
4520 gcc_assert ((STMT_VINFO_RELEVANT_P (exit_phi_vinfo)
4521 && !STMT_VINFO_LIVE_P (exit_phi_vinfo))
4522 || double_reduc);
4524 STMT_VINFO_VEC_STMT (exit_phi_vinfo) = epilog_stmt;
4525 if (!double_reduc
4526 || STMT_VINFO_DEF_TYPE (exit_phi_vinfo)
4527 != vect_double_reduction_def)
4528 continue;
4530 /* Handle double reduction:
4532 stmt1: s1 = phi <s0, s2> - double reduction phi (outer loop)
4533 stmt2: s3 = phi <s1, s4> - (regular) reduc phi (inner loop)
4534 stmt3: s4 = use (s3) - (regular) reduc stmt (inner loop)
4535 stmt4: s2 = phi <s4> - double reduction stmt (outer loop)
4537 At that point the regular reduction (stmt2 and stmt3) is
4538 already vectorized, as well as the exit phi node, stmt4.
4539 Here we vectorize the phi node of double reduction, stmt1, and
4540 update all relevant statements. */
4542 /* Go through all the uses of s2 to find double reduction phi
4543 node, i.e., stmt1 above. */
4544 orig_name = PHI_RESULT (exit_phi);
4545 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, orig_name)
4547 stmt_vec_info use_stmt_vinfo;
4548 stmt_vec_info new_phi_vinfo;
4549 tree vect_phi_init, preheader_arg, vect_phi_res, init_def;
4550 basic_block bb = gimple_bb (use_stmt);
4551 gimple use;
4553 /* Check that USE_STMT is really double reduction phi
4554 node. */
4555 if (gimple_code (use_stmt) != GIMPLE_PHI
4556 || gimple_phi_num_args (use_stmt) != 2
4557 || bb->loop_father != outer_loop)
4558 continue;
4559 use_stmt_vinfo = vinfo_for_stmt (use_stmt);
4560 if (!use_stmt_vinfo
4561 || STMT_VINFO_DEF_TYPE (use_stmt_vinfo)
4562 != vect_double_reduction_def)
4563 continue;
4565 /* Create vector phi node for double reduction:
4566 vs1 = phi <vs0, vs2>
4567 vs1 was created previously in this function by a call to
4568 vect_get_vec_def_for_operand and is stored in
4569 vec_initial_def;
4570 vs2 is defined by INNER_PHI, the vectorized EXIT_PHI;
4571 vs0 is created here. */
4573 /* Create vector phi node. */
4574 vect_phi = create_phi_node (vec_initial_def, bb);
4575 new_phi_vinfo = new_stmt_vec_info (vect_phi,
4576 loop_vec_info_for_loop (outer_loop), NULL);
4577 set_vinfo_for_stmt (vect_phi, new_phi_vinfo);
4579 /* Create vs0 - initial def of the double reduction phi. */
4580 preheader_arg = PHI_ARG_DEF_FROM_EDGE (use_stmt,
4581 loop_preheader_edge (outer_loop));
4582 init_def = get_initial_def_for_reduction (stmt,
4583 preheader_arg, NULL);
4584 vect_phi_init = vect_init_vector (use_stmt, init_def,
4585 vectype, NULL);
4587 /* Update phi node arguments with vs0 and vs2. */
4588 add_phi_arg (vect_phi, vect_phi_init,
4589 loop_preheader_edge (outer_loop),
4590 UNKNOWN_LOCATION);
4591 add_phi_arg (vect_phi, PHI_RESULT (inner_phi),
4592 loop_latch_edge (outer_loop), UNKNOWN_LOCATION);
4593 if (dump_enabled_p ())
4595 dump_printf_loc (MSG_NOTE, vect_location,
4596 "created double reduction phi node: ");
4597 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, vect_phi, 0);
4598 dump_printf (MSG_NOTE, "\n");
4601 vect_phi_res = PHI_RESULT (vect_phi);
4603 /* Replace the use, i.e., set the correct vs1 in the regular
4604 reduction phi node. FORNOW, NCOPIES is always 1, so the
4605 loop is redundant. */
4606 use = reduction_phi;
4607 for (j = 0; j < ncopies; j++)
4609 edge pr_edge = loop_preheader_edge (loop);
4610 SET_PHI_ARG_DEF (use, pr_edge->dest_idx, vect_phi_res);
4611 use = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use));
4617 phis.release ();
4618 if (nested_in_vect_loop)
4620 if (double_reduc)
4621 loop = outer_loop;
4622 else
4623 continue;
4626 phis.create (3);
4627 /* Find the loop-closed-use at the loop exit of the original scalar
4628 result. (The reduction result is expected to have two immediate uses,
4629 one at the latch block, and one at the loop exit). For double
4630 reductions we are looking for exit phis of the outer loop. */
4631 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, scalar_dest)
4633 if (!flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
4635 if (!is_gimple_debug (USE_STMT (use_p)))
4636 phis.safe_push (USE_STMT (use_p));
4638 else
4640 if (double_reduc && gimple_code (USE_STMT (use_p)) == GIMPLE_PHI)
4642 tree phi_res = PHI_RESULT (USE_STMT (use_p));
4644 FOR_EACH_IMM_USE_FAST (phi_use_p, phi_imm_iter, phi_res)
4646 if (!flow_bb_inside_loop_p (loop,
4647 gimple_bb (USE_STMT (phi_use_p)))
4648 && !is_gimple_debug (USE_STMT (phi_use_p)))
4649 phis.safe_push (USE_STMT (phi_use_p));
4655 FOR_EACH_VEC_ELT (phis, i, exit_phi)
4657 /* Replace the uses: */
4658 orig_name = PHI_RESULT (exit_phi);
4659 scalar_result = scalar_results[k];
4660 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, orig_name)
4661 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
4662 SET_USE (use_p, scalar_result);
4665 phis.release ();
4670 /* Function vectorizable_reduction.
4672 Check if STMT performs a reduction operation that can be vectorized.
4673 If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4674 stmt to replace it, put it in VEC_STMT, and insert it at GSI.
4675 Return FALSE if not a vectorizable STMT, TRUE otherwise.
4677 This function also handles reduction idioms (patterns) that have been
4678 recognized in advance during vect_pattern_recog. In this case, STMT may be
4679 of this form:
4680 X = pattern_expr (arg0, arg1, ..., X)
4681 and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
4682 sequence that had been detected and replaced by the pattern-stmt (STMT).
4684 In some cases of reduction patterns, the type of the reduction variable X is
4685 different than the type of the other arguments of STMT.
4686 In such cases, the vectype that is used when transforming STMT into a vector
4687 stmt is different than the vectype that is used to determine the
4688 vectorization factor, because it consists of a different number of elements
4689 than the actual number of elements that are being operated upon in parallel.
4691 For example, consider an accumulation of shorts into an int accumulator.
4692 On some targets it's possible to vectorize this pattern operating on 8
4693 shorts at a time (hence, the vectype for purposes of determining the
4694 vectorization factor should be V8HI); on the other hand, the vectype that
4695 is used to create the vector form is actually V4SI (the type of the result).
4697 Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
4698 indicates what is the actual level of parallelism (V8HI in the example), so
4699 that the right vectorization factor would be derived. This vectype
4700 corresponds to the type of arguments to the reduction stmt, and should *NOT*
4701 be used to create the vectorized stmt. The right vectype for the vectorized
4702 stmt is obtained from the type of the result X:
4703 get_vectype_for_scalar_type (TREE_TYPE (X))
4705 This means that, contrary to "regular" reductions (or "regular" stmts in
4706 general), the following equation:
4707 STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
4708 does *NOT* necessarily hold for reduction patterns. */
4710 bool
4711 vectorizable_reduction (gimple stmt, gimple_stmt_iterator *gsi,
4712 gimple *vec_stmt, slp_tree slp_node)
4714 tree vec_dest;
4715 tree scalar_dest;
4716 tree loop_vec_def0 = NULL_TREE, loop_vec_def1 = NULL_TREE;
4717 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4718 tree vectype_out = STMT_VINFO_VECTYPE (stmt_info);
4719 tree vectype_in = NULL_TREE;
4720 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
4721 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
4722 enum tree_code code, orig_code, epilog_reduc_code;
4723 enum machine_mode vec_mode;
4724 int op_type;
4725 optab optab, reduc_optab;
4726 tree new_temp = NULL_TREE;
4727 tree def;
4728 gimple def_stmt;
4729 enum vect_def_type dt;
4730 gimple new_phi = NULL;
4731 tree scalar_type;
4732 bool is_simple_use;
4733 gimple orig_stmt;
4734 stmt_vec_info orig_stmt_info;
4735 tree expr = NULL_TREE;
4736 int i;
4737 int ncopies;
4738 int epilog_copies;
4739 stmt_vec_info prev_stmt_info, prev_phi_info;
4740 bool single_defuse_cycle = false;
4741 tree reduc_def = NULL_TREE;
4742 gimple new_stmt = NULL;
4743 int j;
4744 tree ops[3];
4745 bool nested_cycle = false, found_nested_cycle_def = false;
4746 gimple reduc_def_stmt = NULL;
4747 /* The default is that the reduction variable is the last in statement. */
4748 int reduc_index = 2;
4749 bool double_reduc = false, dummy;
4750 basic_block def_bb;
4751 struct loop * def_stmt_loop, *outer_loop = NULL;
4752 tree def_arg;
4753 gimple def_arg_stmt;
4754 auto_vec<tree> vec_oprnds0;
4755 auto_vec<tree> vec_oprnds1;
4756 auto_vec<tree> vect_defs;
4757 auto_vec<gimple> phis;
4758 int vec_num;
4759 tree def0, def1, tem, op0, op1 = NULL_TREE;
4761 /* In case of reduction chain we switch to the first stmt in the chain, but
4762 we don't update STMT_INFO, since only the last stmt is marked as reduction
4763 and has reduction properties. */
4764 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
4765 stmt = GROUP_FIRST_ELEMENT (stmt_info);
4767 if (nested_in_vect_loop_p (loop, stmt))
4769 outer_loop = loop;
4770 loop = loop->inner;
4771 nested_cycle = true;
4774 /* 1. Is vectorizable reduction? */
4775 /* Not supportable if the reduction variable is used in the loop, unless
4776 it's a reduction chain. */
4777 if (STMT_VINFO_RELEVANT (stmt_info) > vect_used_in_outer
4778 && !GROUP_FIRST_ELEMENT (stmt_info))
4779 return false;
4781 /* Reductions that are not used even in an enclosing outer-loop,
4782 are expected to be "live" (used out of the loop). */
4783 if (STMT_VINFO_RELEVANT (stmt_info) == vect_unused_in_scope
4784 && !STMT_VINFO_LIVE_P (stmt_info))
4785 return false;
4787 /* Make sure it was already recognized as a reduction computation. */
4788 if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_reduction_def
4789 && STMT_VINFO_DEF_TYPE (stmt_info) != vect_nested_cycle)
4790 return false;
4792 /* 2. Has this been recognized as a reduction pattern?
4794 Check if STMT represents a pattern that has been recognized
4795 in earlier analysis stages. For stmts that represent a pattern,
4796 the STMT_VINFO_RELATED_STMT field records the last stmt in
4797 the original sequence that constitutes the pattern. */
4799 orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
4800 if (orig_stmt)
4802 orig_stmt_info = vinfo_for_stmt (orig_stmt);
4803 gcc_assert (STMT_VINFO_IN_PATTERN_P (orig_stmt_info));
4804 gcc_assert (!STMT_VINFO_IN_PATTERN_P (stmt_info));
4807 /* 3. Check the operands of the operation. The first operands are defined
4808 inside the loop body. The last operand is the reduction variable,
4809 which is defined by the loop-header-phi. */
4811 gcc_assert (is_gimple_assign (stmt));
4813 /* Flatten RHS. */
4814 switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
4816 case GIMPLE_SINGLE_RHS:
4817 op_type = TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt));
4818 if (op_type == ternary_op)
4820 tree rhs = gimple_assign_rhs1 (stmt);
4821 ops[0] = TREE_OPERAND (rhs, 0);
4822 ops[1] = TREE_OPERAND (rhs, 1);
4823 ops[2] = TREE_OPERAND (rhs, 2);
4824 code = TREE_CODE (rhs);
4826 else
4827 return false;
4828 break;
4830 case GIMPLE_BINARY_RHS:
4831 code = gimple_assign_rhs_code (stmt);
4832 op_type = TREE_CODE_LENGTH (code);
4833 gcc_assert (op_type == binary_op);
4834 ops[0] = gimple_assign_rhs1 (stmt);
4835 ops[1] = gimple_assign_rhs2 (stmt);
4836 break;
4838 case GIMPLE_TERNARY_RHS:
4839 code = gimple_assign_rhs_code (stmt);
4840 op_type = TREE_CODE_LENGTH (code);
4841 gcc_assert (op_type == ternary_op);
4842 ops[0] = gimple_assign_rhs1 (stmt);
4843 ops[1] = gimple_assign_rhs2 (stmt);
4844 ops[2] = gimple_assign_rhs3 (stmt);
4845 break;
4847 case GIMPLE_UNARY_RHS:
4848 return false;
4850 default:
4851 gcc_unreachable ();
4854 if (code == COND_EXPR && slp_node)
4855 return false;
4857 scalar_dest = gimple_assign_lhs (stmt);
4858 scalar_type = TREE_TYPE (scalar_dest);
4859 if (!POINTER_TYPE_P (scalar_type) && !INTEGRAL_TYPE_P (scalar_type)
4860 && !SCALAR_FLOAT_TYPE_P (scalar_type))
4861 return false;
4863 /* Do not try to vectorize bit-precision reductions. */
4864 if ((TYPE_PRECISION (scalar_type)
4865 != GET_MODE_PRECISION (TYPE_MODE (scalar_type))))
4866 return false;
4868 /* All uses but the last are expected to be defined in the loop.
4869 The last use is the reduction variable. In case of nested cycle this
4870 assumption is not true: we use reduc_index to record the index of the
4871 reduction variable. */
4872 for (i = 0; i < op_type - 1; i++)
4874 /* The condition of COND_EXPR is checked in vectorizable_condition(). */
4875 if (i == 0 && code == COND_EXPR)
4876 continue;
4878 is_simple_use = vect_is_simple_use_1 (ops[i], stmt, loop_vinfo, NULL,
4879 &def_stmt, &def, &dt, &tem);
4880 if (!vectype_in)
4881 vectype_in = tem;
4882 gcc_assert (is_simple_use);
4884 if (dt != vect_internal_def
4885 && dt != vect_external_def
4886 && dt != vect_constant_def
4887 && dt != vect_induction_def
4888 && !(dt == vect_nested_cycle && nested_cycle))
4889 return false;
4891 if (dt == vect_nested_cycle)
4893 found_nested_cycle_def = true;
4894 reduc_def_stmt = def_stmt;
4895 reduc_index = i;
4899 is_simple_use = vect_is_simple_use_1 (ops[i], stmt, loop_vinfo, NULL,
4900 &def_stmt, &def, &dt, &tem);
4901 if (!vectype_in)
4902 vectype_in = tem;
4903 gcc_assert (is_simple_use);
4904 if (!(dt == vect_reduction_def
4905 || dt == vect_nested_cycle
4906 || ((dt == vect_internal_def || dt == vect_external_def
4907 || dt == vect_constant_def || dt == vect_induction_def)
4908 && nested_cycle && found_nested_cycle_def)))
4910 /* For pattern recognized stmts, orig_stmt might be a reduction,
4911 but some helper statements for the pattern might not, or
4912 might be COND_EXPRs with reduction uses in the condition. */
4913 gcc_assert (orig_stmt);
4914 return false;
4916 if (!found_nested_cycle_def)
4917 reduc_def_stmt = def_stmt;
4919 gcc_assert (gimple_code (reduc_def_stmt) == GIMPLE_PHI);
4920 if (orig_stmt)
4921 gcc_assert (orig_stmt == vect_is_simple_reduction (loop_vinfo,
4922 reduc_def_stmt,
4923 !nested_cycle,
4924 &dummy));
4925 else
4927 gimple tmp = vect_is_simple_reduction (loop_vinfo, reduc_def_stmt,
4928 !nested_cycle, &dummy);
4929 /* We changed STMT to be the first stmt in reduction chain, hence we
4930 check that in this case the first element in the chain is STMT. */
4931 gcc_assert (stmt == tmp
4932 || GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp)) == stmt);
4935 if (STMT_VINFO_LIVE_P (vinfo_for_stmt (reduc_def_stmt)))
4936 return false;
4938 if (slp_node || PURE_SLP_STMT (stmt_info))
4939 ncopies = 1;
4940 else
4941 ncopies = (LOOP_VINFO_VECT_FACTOR (loop_vinfo)
4942 / TYPE_VECTOR_SUBPARTS (vectype_in));
4944 gcc_assert (ncopies >= 1);
4946 vec_mode = TYPE_MODE (vectype_in);
4948 if (code == COND_EXPR)
4950 if (!vectorizable_condition (stmt, gsi, NULL, ops[reduc_index], 0, NULL))
4952 if (dump_enabled_p ())
4953 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
4954 "unsupported condition in reduction\n");
4956 return false;
4959 else
4961 /* 4. Supportable by target? */
4963 if (code == LSHIFT_EXPR || code == RSHIFT_EXPR
4964 || code == LROTATE_EXPR || code == RROTATE_EXPR)
4966 /* Shifts and rotates are only supported by vectorizable_shifts,
4967 not vectorizable_reduction. */
4968 if (dump_enabled_p ())
4969 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
4970 "unsupported shift or rotation.\n");
4971 return false;
4974 /* 4.1. check support for the operation in the loop */
4975 optab = optab_for_tree_code (code, vectype_in, optab_default);
4976 if (!optab)
4978 if (dump_enabled_p ())
4979 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
4980 "no optab.\n");
4982 return false;
4985 if (optab_handler (optab, vec_mode) == CODE_FOR_nothing)
4987 if (dump_enabled_p ())
4988 dump_printf (MSG_NOTE, "op not supported by target.\n");
4990 if (GET_MODE_SIZE (vec_mode) != UNITS_PER_WORD
4991 || LOOP_VINFO_VECT_FACTOR (loop_vinfo)
4992 < vect_min_worthwhile_factor (code))
4993 return false;
4995 if (dump_enabled_p ())
4996 dump_printf (MSG_NOTE, "proceeding using word mode.\n");
4999 /* Worthwhile without SIMD support? */
5000 if (!VECTOR_MODE_P (TYPE_MODE (vectype_in))
5001 && LOOP_VINFO_VECT_FACTOR (loop_vinfo)
5002 < vect_min_worthwhile_factor (code))
5004 if (dump_enabled_p ())
5005 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5006 "not worthwhile without SIMD support.\n");
5008 return false;
5012 /* 4.2. Check support for the epilog operation.
5014 If STMT represents a reduction pattern, then the type of the
5015 reduction variable may be different than the type of the rest
5016 of the arguments. For example, consider the case of accumulation
5017 of shorts into an int accumulator; The original code:
5018 S1: int_a = (int) short_a;
5019 orig_stmt-> S2: int_acc = plus <int_a ,int_acc>;
5021 was replaced with:
5022 STMT: int_acc = widen_sum <short_a, int_acc>
5024 This means that:
5025 1. The tree-code that is used to create the vector operation in the
5026 epilog code (that reduces the partial results) is not the
5027 tree-code of STMT, but is rather the tree-code of the original
5028 stmt from the pattern that STMT is replacing. I.e, in the example
5029 above we want to use 'widen_sum' in the loop, but 'plus' in the
5030 epilog.
5031 2. The type (mode) we use to check available target support
5032 for the vector operation to be created in the *epilog*, is
5033 determined by the type of the reduction variable (in the example
5034 above we'd check this: optab_handler (plus_optab, vect_int_mode])).
5035 However the type (mode) we use to check available target support
5036 for the vector operation to be created *inside the loop*, is
5037 determined by the type of the other arguments to STMT (in the
5038 example we'd check this: optab_handler (widen_sum_optab,
5039 vect_short_mode)).
5041 This is contrary to "regular" reductions, in which the types of all
5042 the arguments are the same as the type of the reduction variable.
5043 For "regular" reductions we can therefore use the same vector type
5044 (and also the same tree-code) when generating the epilog code and
5045 when generating the code inside the loop. */
5047 if (orig_stmt)
5049 /* This is a reduction pattern: get the vectype from the type of the
5050 reduction variable, and get the tree-code from orig_stmt. */
5051 orig_code = gimple_assign_rhs_code (orig_stmt);
5052 gcc_assert (vectype_out);
5053 vec_mode = TYPE_MODE (vectype_out);
5055 else
5057 /* Regular reduction: use the same vectype and tree-code as used for
5058 the vector code inside the loop can be used for the epilog code. */
5059 orig_code = code;
5062 if (nested_cycle)
5064 def_bb = gimple_bb (reduc_def_stmt);
5065 def_stmt_loop = def_bb->loop_father;
5066 def_arg = PHI_ARG_DEF_FROM_EDGE (reduc_def_stmt,
5067 loop_preheader_edge (def_stmt_loop));
5068 if (TREE_CODE (def_arg) == SSA_NAME
5069 && (def_arg_stmt = SSA_NAME_DEF_STMT (def_arg))
5070 && gimple_code (def_arg_stmt) == GIMPLE_PHI
5071 && flow_bb_inside_loop_p (outer_loop, gimple_bb (def_arg_stmt))
5072 && vinfo_for_stmt (def_arg_stmt)
5073 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_arg_stmt))
5074 == vect_double_reduction_def)
5075 double_reduc = true;
5078 epilog_reduc_code = ERROR_MARK;
5079 if (reduction_code_for_scalar_code (orig_code, &epilog_reduc_code))
5081 reduc_optab = optab_for_tree_code (epilog_reduc_code, vectype_out,
5082 optab_default);
5083 if (!reduc_optab)
5085 if (dump_enabled_p ())
5086 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5087 "no optab for reduction.\n");
5089 epilog_reduc_code = ERROR_MARK;
5092 if (reduc_optab
5093 && optab_handler (reduc_optab, vec_mode) == CODE_FOR_nothing)
5095 if (dump_enabled_p ())
5096 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5097 "reduc op not supported by target.\n");
5099 epilog_reduc_code = ERROR_MARK;
5102 else
5104 if (!nested_cycle || double_reduc)
5106 if (dump_enabled_p ())
5107 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5108 "no reduc code for scalar code.\n");
5110 return false;
5114 if (double_reduc && ncopies > 1)
5116 if (dump_enabled_p ())
5117 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5118 "multiple types in double reduction\n");
5120 return false;
5123 /* In case of widenning multiplication by a constant, we update the type
5124 of the constant to be the type of the other operand. We check that the
5125 constant fits the type in the pattern recognition pass. */
5126 if (code == DOT_PROD_EXPR
5127 && !types_compatible_p (TREE_TYPE (ops[0]), TREE_TYPE (ops[1])))
5129 if (TREE_CODE (ops[0]) == INTEGER_CST)
5130 ops[0] = fold_convert (TREE_TYPE (ops[1]), ops[0]);
5131 else if (TREE_CODE (ops[1]) == INTEGER_CST)
5132 ops[1] = fold_convert (TREE_TYPE (ops[0]), ops[1]);
5133 else
5135 if (dump_enabled_p ())
5136 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5137 "invalid types in dot-prod\n");
5139 return false;
5143 if (!vec_stmt) /* transformation not required. */
5145 if (!vect_model_reduction_cost (stmt_info, epilog_reduc_code, ncopies))
5146 return false;
5147 STMT_VINFO_TYPE (stmt_info) = reduc_vec_info_type;
5148 return true;
5151 /** Transform. **/
5153 if (dump_enabled_p ())
5154 dump_printf_loc (MSG_NOTE, vect_location, "transform reduction.\n");
5156 /* FORNOW: Multiple types are not supported for condition. */
5157 if (code == COND_EXPR)
5158 gcc_assert (ncopies == 1);
5160 /* Create the destination vector */
5161 vec_dest = vect_create_destination_var (scalar_dest, vectype_out);
5163 /* In case the vectorization factor (VF) is bigger than the number
5164 of elements that we can fit in a vectype (nunits), we have to generate
5165 more than one vector stmt - i.e - we need to "unroll" the
5166 vector stmt by a factor VF/nunits. For more details see documentation
5167 in vectorizable_operation. */
5169 /* If the reduction is used in an outer loop we need to generate
5170 VF intermediate results, like so (e.g. for ncopies=2):
5171 r0 = phi (init, r0)
5172 r1 = phi (init, r1)
5173 r0 = x0 + r0;
5174 r1 = x1 + r1;
5175 (i.e. we generate VF results in 2 registers).
5176 In this case we have a separate def-use cycle for each copy, and therefore
5177 for each copy we get the vector def for the reduction variable from the
5178 respective phi node created for this copy.
5180 Otherwise (the reduction is unused in the loop nest), we can combine
5181 together intermediate results, like so (e.g. for ncopies=2):
5182 r = phi (init, r)
5183 r = x0 + r;
5184 r = x1 + r;
5185 (i.e. we generate VF/2 results in a single register).
5186 In this case for each copy we get the vector def for the reduction variable
5187 from the vectorized reduction operation generated in the previous iteration.
5190 if (STMT_VINFO_RELEVANT (stmt_info) == vect_unused_in_scope)
5192 single_defuse_cycle = true;
5193 epilog_copies = 1;
5195 else
5196 epilog_copies = ncopies;
5198 prev_stmt_info = NULL;
5199 prev_phi_info = NULL;
5200 if (slp_node)
5202 vec_num = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
5203 gcc_assert (TYPE_VECTOR_SUBPARTS (vectype_out)
5204 == TYPE_VECTOR_SUBPARTS (vectype_in));
5206 else
5208 vec_num = 1;
5209 vec_oprnds0.create (1);
5210 if (op_type == ternary_op)
5211 vec_oprnds1.create (1);
5214 phis.create (vec_num);
5215 vect_defs.create (vec_num);
5216 if (!slp_node)
5217 vect_defs.quick_push (NULL_TREE);
5219 for (j = 0; j < ncopies; j++)
5221 if (j == 0 || !single_defuse_cycle)
5223 for (i = 0; i < vec_num; i++)
5225 /* Create the reduction-phi that defines the reduction
5226 operand. */
5227 new_phi = create_phi_node (vec_dest, loop->header);
5228 set_vinfo_for_stmt (new_phi,
5229 new_stmt_vec_info (new_phi, loop_vinfo,
5230 NULL));
5231 if (j == 0 || slp_node)
5232 phis.quick_push (new_phi);
5236 if (code == COND_EXPR)
5238 gcc_assert (!slp_node);
5239 vectorizable_condition (stmt, gsi, vec_stmt,
5240 PHI_RESULT (phis[0]),
5241 reduc_index, NULL);
5242 /* Multiple types are not supported for condition. */
5243 break;
5246 /* Handle uses. */
5247 if (j == 0)
5249 op0 = ops[!reduc_index];
5250 if (op_type == ternary_op)
5252 if (reduc_index == 0)
5253 op1 = ops[2];
5254 else
5255 op1 = ops[1];
5258 if (slp_node)
5259 vect_get_vec_defs (op0, op1, stmt, &vec_oprnds0, &vec_oprnds1,
5260 slp_node, -1);
5261 else
5263 loop_vec_def0 = vect_get_vec_def_for_operand (ops[!reduc_index],
5264 stmt, NULL);
5265 vec_oprnds0.quick_push (loop_vec_def0);
5266 if (op_type == ternary_op)
5268 loop_vec_def1 = vect_get_vec_def_for_operand (op1, stmt,
5269 NULL);
5270 vec_oprnds1.quick_push (loop_vec_def1);
5274 else
5276 if (!slp_node)
5278 enum vect_def_type dt;
5279 gimple dummy_stmt;
5280 tree dummy;
5282 vect_is_simple_use (ops[!reduc_index], stmt, loop_vinfo, NULL,
5283 &dummy_stmt, &dummy, &dt);
5284 loop_vec_def0 = vect_get_vec_def_for_stmt_copy (dt,
5285 loop_vec_def0);
5286 vec_oprnds0[0] = loop_vec_def0;
5287 if (op_type == ternary_op)
5289 vect_is_simple_use (op1, stmt, loop_vinfo, NULL, &dummy_stmt,
5290 &dummy, &dt);
5291 loop_vec_def1 = vect_get_vec_def_for_stmt_copy (dt,
5292 loop_vec_def1);
5293 vec_oprnds1[0] = loop_vec_def1;
5297 if (single_defuse_cycle)
5298 reduc_def = gimple_assign_lhs (new_stmt);
5300 STMT_VINFO_RELATED_STMT (prev_phi_info) = new_phi;
5303 FOR_EACH_VEC_ELT (vec_oprnds0, i, def0)
5305 if (slp_node)
5306 reduc_def = PHI_RESULT (phis[i]);
5307 else
5309 if (!single_defuse_cycle || j == 0)
5310 reduc_def = PHI_RESULT (new_phi);
5313 def1 = ((op_type == ternary_op)
5314 ? vec_oprnds1[i] : NULL);
5315 if (op_type == binary_op)
5317 if (reduc_index == 0)
5318 expr = build2 (code, vectype_out, reduc_def, def0);
5319 else
5320 expr = build2 (code, vectype_out, def0, reduc_def);
5322 else
5324 if (reduc_index == 0)
5325 expr = build3 (code, vectype_out, reduc_def, def0, def1);
5326 else
5328 if (reduc_index == 1)
5329 expr = build3 (code, vectype_out, def0, reduc_def, def1);
5330 else
5331 expr = build3 (code, vectype_out, def0, def1, reduc_def);
5335 new_stmt = gimple_build_assign (vec_dest, expr);
5336 new_temp = make_ssa_name (vec_dest, new_stmt);
5337 gimple_assign_set_lhs (new_stmt, new_temp);
5338 vect_finish_stmt_generation (stmt, new_stmt, gsi);
5340 if (slp_node)
5342 SLP_TREE_VEC_STMTS (slp_node).quick_push (new_stmt);
5343 vect_defs.quick_push (new_temp);
5345 else
5346 vect_defs[0] = new_temp;
5349 if (slp_node)
5350 continue;
5352 if (j == 0)
5353 STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
5354 else
5355 STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
5357 prev_stmt_info = vinfo_for_stmt (new_stmt);
5358 prev_phi_info = vinfo_for_stmt (new_phi);
5361 /* Finalize the reduction-phi (set its arguments) and create the
5362 epilog reduction code. */
5363 if ((!single_defuse_cycle || code == COND_EXPR) && !slp_node)
5365 new_temp = gimple_assign_lhs (*vec_stmt);
5366 vect_defs[0] = new_temp;
5369 vect_create_epilog_for_reduction (vect_defs, stmt, epilog_copies,
5370 epilog_reduc_code, phis, reduc_index,
5371 double_reduc, slp_node);
5373 return true;
5376 /* Function vect_min_worthwhile_factor.
5378 For a loop where we could vectorize the operation indicated by CODE,
5379 return the minimum vectorization factor that makes it worthwhile
5380 to use generic vectors. */
5382 vect_min_worthwhile_factor (enum tree_code code)
5384 switch (code)
5386 case PLUS_EXPR:
5387 case MINUS_EXPR:
5388 case NEGATE_EXPR:
5389 return 4;
5391 case BIT_AND_EXPR:
5392 case BIT_IOR_EXPR:
5393 case BIT_XOR_EXPR:
5394 case BIT_NOT_EXPR:
5395 return 2;
5397 default:
5398 return INT_MAX;
5403 /* Function vectorizable_induction
5405 Check if PHI performs an induction computation that can be vectorized.
5406 If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
5407 phi to replace it, put it in VEC_STMT, and add it to the same basic block.
5408 Return FALSE if not a vectorizable STMT, TRUE otherwise. */
5410 bool
5411 vectorizable_induction (gimple phi, gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
5412 gimple *vec_stmt)
5414 stmt_vec_info stmt_info = vinfo_for_stmt (phi);
5415 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
5416 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
5417 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
5418 int nunits = TYPE_VECTOR_SUBPARTS (vectype);
5419 int ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
5420 tree vec_def;
5422 gcc_assert (ncopies >= 1);
5423 /* FORNOW. These restrictions should be relaxed. */
5424 if (nested_in_vect_loop_p (loop, phi))
5426 imm_use_iterator imm_iter;
5427 use_operand_p use_p;
5428 gimple exit_phi;
5429 edge latch_e;
5430 tree loop_arg;
5432 if (ncopies > 1)
5434 if (dump_enabled_p ())
5435 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5436 "multiple types in nested loop.\n");
5437 return false;
5440 exit_phi = NULL;
5441 latch_e = loop_latch_edge (loop->inner);
5442 loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
5443 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, loop_arg)
5445 gimple use_stmt = USE_STMT (use_p);
5446 if (is_gimple_debug (use_stmt))
5447 continue;
5449 if (!flow_bb_inside_loop_p (loop->inner, gimple_bb (use_stmt)))
5451 exit_phi = use_stmt;
5452 break;
5455 if (exit_phi)
5457 stmt_vec_info exit_phi_vinfo = vinfo_for_stmt (exit_phi);
5458 if (!(STMT_VINFO_RELEVANT_P (exit_phi_vinfo)
5459 && !STMT_VINFO_LIVE_P (exit_phi_vinfo)))
5461 if (dump_enabled_p ())
5462 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5463 "inner-loop induction only used outside "
5464 "of the outer vectorized loop.\n");
5465 return false;
5470 if (!STMT_VINFO_RELEVANT_P (stmt_info))
5471 return false;
5473 /* FORNOW: SLP not supported. */
5474 if (STMT_SLP_TYPE (stmt_info))
5475 return false;
5477 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def);
5479 if (gimple_code (phi) != GIMPLE_PHI)
5480 return false;
5482 if (!vec_stmt) /* transformation not required. */
5484 STMT_VINFO_TYPE (stmt_info) = induc_vec_info_type;
5485 if (dump_enabled_p ())
5486 dump_printf_loc (MSG_NOTE, vect_location,
5487 "=== vectorizable_induction ===\n");
5488 vect_model_induction_cost (stmt_info, ncopies);
5489 return true;
5492 /** Transform. **/
5494 if (dump_enabled_p ())
5495 dump_printf_loc (MSG_NOTE, vect_location, "transform induction phi.\n");
5497 vec_def = get_initial_def_for_induction (phi);
5498 *vec_stmt = SSA_NAME_DEF_STMT (vec_def);
5499 return true;
5502 /* Function vectorizable_live_operation.
5504 STMT computes a value that is used outside the loop. Check if
5505 it can be supported. */
5507 bool
5508 vectorizable_live_operation (gimple stmt,
5509 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
5510 gimple *vec_stmt)
5512 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
5513 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
5514 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
5515 int i;
5516 int op_type;
5517 tree op;
5518 tree def;
5519 gimple def_stmt;
5520 enum vect_def_type dt;
5521 enum tree_code code;
5522 enum gimple_rhs_class rhs_class;
5524 gcc_assert (STMT_VINFO_LIVE_P (stmt_info));
5526 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_reduction_def)
5527 return false;
5529 if (!is_gimple_assign (stmt))
5531 if (gimple_call_internal_p (stmt)
5532 && gimple_call_internal_fn (stmt) == IFN_GOMP_SIMD_LANE
5533 && gimple_call_lhs (stmt)
5534 && loop->simduid
5535 && TREE_CODE (gimple_call_arg (stmt, 0)) == SSA_NAME
5536 && loop->simduid
5537 == SSA_NAME_VAR (gimple_call_arg (stmt, 0)))
5539 edge e = single_exit (loop);
5540 basic_block merge_bb = e->dest;
5541 imm_use_iterator imm_iter;
5542 use_operand_p use_p;
5543 tree lhs = gimple_call_lhs (stmt);
5545 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
5547 gimple use_stmt = USE_STMT (use_p);
5548 if (gimple_code (use_stmt) == GIMPLE_PHI
5549 && gimple_bb (use_stmt) == merge_bb)
5551 if (vec_stmt)
5553 tree vfm1
5554 = build_int_cst (unsigned_type_node,
5555 loop_vinfo->vectorization_factor - 1);
5556 SET_PHI_ARG_DEF (use_stmt, e->dest_idx, vfm1);
5558 return true;
5563 return false;
5566 if (TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
5567 return false;
5569 /* FORNOW. CHECKME. */
5570 if (nested_in_vect_loop_p (loop, stmt))
5571 return false;
5573 code = gimple_assign_rhs_code (stmt);
5574 op_type = TREE_CODE_LENGTH (code);
5575 rhs_class = get_gimple_rhs_class (code);
5576 gcc_assert (rhs_class != GIMPLE_UNARY_RHS || op_type == unary_op);
5577 gcc_assert (rhs_class != GIMPLE_BINARY_RHS || op_type == binary_op);
5579 /* FORNOW: support only if all uses are invariant. This means
5580 that the scalar operations can remain in place, unvectorized.
5581 The original last scalar value that they compute will be used. */
5583 for (i = 0; i < op_type; i++)
5585 if (rhs_class == GIMPLE_SINGLE_RHS)
5586 op = TREE_OPERAND (gimple_op (stmt, 1), i);
5587 else
5588 op = gimple_op (stmt, i + 1);
5589 if (op
5590 && !vect_is_simple_use (op, stmt, loop_vinfo, NULL, &def_stmt, &def,
5591 &dt))
5593 if (dump_enabled_p ())
5594 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
5595 "use not simple.\n");
5596 return false;
5599 if (dt != vect_external_def && dt != vect_constant_def)
5600 return false;
5603 /* No transformation is required for the cases we currently support. */
5604 return true;
5607 /* Kill any debug uses outside LOOP of SSA names defined in STMT. */
5609 static void
5610 vect_loop_kill_debug_uses (struct loop *loop, gimple stmt)
5612 ssa_op_iter op_iter;
5613 imm_use_iterator imm_iter;
5614 def_operand_p def_p;
5615 gimple ustmt;
5617 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_DEF)
5619 FOR_EACH_IMM_USE_STMT (ustmt, imm_iter, DEF_FROM_PTR (def_p))
5621 basic_block bb;
5623 if (!is_gimple_debug (ustmt))
5624 continue;
5626 bb = gimple_bb (ustmt);
5628 if (!flow_bb_inside_loop_p (loop, bb))
5630 if (gimple_debug_bind_p (ustmt))
5632 if (dump_enabled_p ())
5633 dump_printf_loc (MSG_NOTE, vect_location,
5634 "killing debug use\n");
5636 gimple_debug_bind_reset_value (ustmt);
5637 update_stmt (ustmt);
5639 else
5640 gcc_unreachable ();
5647 /* This function builds ni_name = number of iterations. Statements
5648 are emitted on the loop preheader edge. */
5650 static tree
5651 vect_build_loop_niters (loop_vec_info loop_vinfo)
5653 tree ni = unshare_expr (LOOP_VINFO_NITERS (loop_vinfo));
5654 if (TREE_CODE (ni) == INTEGER_CST)
5655 return ni;
5656 else
5658 tree ni_name, var;
5659 gimple_seq stmts = NULL;
5660 edge pe = loop_preheader_edge (LOOP_VINFO_LOOP (loop_vinfo));
5662 var = create_tmp_var (TREE_TYPE (ni), "niters");
5663 ni_name = force_gimple_operand (ni, &stmts, false, var);
5664 if (stmts)
5665 gsi_insert_seq_on_edge_immediate (pe, stmts);
5667 return ni_name;
5672 /* This function generates the following statements:
5674 ni_name = number of iterations loop executes
5675 ratio = ni_name / vf
5676 ratio_mult_vf_name = ratio * vf
5678 and places them on the loop preheader edge. */
5680 static void
5681 vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo,
5682 tree ni_name,
5683 tree *ratio_mult_vf_name_ptr,
5684 tree *ratio_name_ptr)
5686 tree ni_minus_gap_name;
5687 tree var;
5688 tree ratio_name;
5689 tree ratio_mult_vf_name;
5690 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
5691 edge pe = loop_preheader_edge (LOOP_VINFO_LOOP (loop_vinfo));
5692 tree log_vf;
5694 log_vf = build_int_cst (TREE_TYPE (ni_name), exact_log2 (vf));
5696 /* If epilogue loop is required because of data accesses with gaps, we
5697 subtract one iteration from the total number of iterations here for
5698 correct calculation of RATIO. */
5699 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo))
5701 ni_minus_gap_name = fold_build2 (MINUS_EXPR, TREE_TYPE (ni_name),
5702 ni_name,
5703 build_one_cst (TREE_TYPE (ni_name)));
5704 if (!is_gimple_val (ni_minus_gap_name))
5706 var = create_tmp_var (TREE_TYPE (ni_name), "ni_gap");
5707 gimple stmts = NULL;
5708 ni_minus_gap_name = force_gimple_operand (ni_minus_gap_name, &stmts,
5709 true, var);
5710 gsi_insert_seq_on_edge_immediate (pe, stmts);
5713 else
5714 ni_minus_gap_name = ni_name;
5716 /* Create: ratio = ni >> log2(vf) */
5717 /* ??? As we have ni == number of latch executions + 1, ni could
5718 have overflown to zero. So avoid computing ratio based on ni
5719 but compute it using the fact that we know ratio will be at least
5720 one, thus via (ni - vf) >> log2(vf) + 1. */
5721 ratio_name
5722 = fold_build2 (PLUS_EXPR, TREE_TYPE (ni_name),
5723 fold_build2 (RSHIFT_EXPR, TREE_TYPE (ni_name),
5724 fold_build2 (MINUS_EXPR, TREE_TYPE (ni_name),
5725 ni_minus_gap_name,
5726 build_int_cst
5727 (TREE_TYPE (ni_name), vf)),
5728 log_vf),
5729 build_int_cst (TREE_TYPE (ni_name), 1));
5730 if (!is_gimple_val (ratio_name))
5732 var = create_tmp_var (TREE_TYPE (ni_name), "bnd");
5733 gimple stmts = NULL;
5734 ratio_name = force_gimple_operand (ratio_name, &stmts, true, var);
5735 gsi_insert_seq_on_edge_immediate (pe, stmts);
5737 *ratio_name_ptr = ratio_name;
5739 /* Create: ratio_mult_vf = ratio << log2 (vf). */
5741 if (ratio_mult_vf_name_ptr)
5743 ratio_mult_vf_name = fold_build2 (LSHIFT_EXPR, TREE_TYPE (ratio_name),
5744 ratio_name, log_vf);
5745 if (!is_gimple_val (ratio_mult_vf_name))
5747 var = create_tmp_var (TREE_TYPE (ni_name), "ratio_mult_vf");
5748 gimple stmts = NULL;
5749 ratio_mult_vf_name = force_gimple_operand (ratio_mult_vf_name, &stmts,
5750 true, var);
5751 gsi_insert_seq_on_edge_immediate (pe, stmts);
5753 *ratio_mult_vf_name_ptr = ratio_mult_vf_name;
5756 return;
5760 /* Function vect_transform_loop.
5762 The analysis phase has determined that the loop is vectorizable.
5763 Vectorize the loop - created vectorized stmts to replace the scalar
5764 stmts in the loop, and update the loop exit condition. */
5766 void
5767 vect_transform_loop (loop_vec_info loop_vinfo)
5769 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
5770 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
5771 int nbbs = loop->num_nodes;
5772 gimple_stmt_iterator si;
5773 int i;
5774 tree ratio = NULL;
5775 int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
5776 bool grouped_store;
5777 bool slp_scheduled = false;
5778 gimple stmt, pattern_stmt;
5779 gimple_seq pattern_def_seq = NULL;
5780 gimple_stmt_iterator pattern_def_si = gsi_none ();
5781 bool transform_pattern_stmt = false;
5782 bool check_profitability = false;
5783 int th;
5784 /* Record number of iterations before we started tampering with the profile. */
5785 gcov_type expected_iterations = expected_loop_iterations_unbounded (loop);
5787 if (dump_enabled_p ())
5788 dump_printf_loc (MSG_NOTE, vect_location, "=== vec_transform_loop ===\n");
5790 /* If profile is inprecise, we have chance to fix it up. */
5791 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
5792 expected_iterations = LOOP_VINFO_INT_NITERS (loop_vinfo);
5794 /* Use the more conservative vectorization threshold. If the number
5795 of iterations is constant assume the cost check has been performed
5796 by our caller. If the threshold makes all loops profitable that
5797 run at least the vectorization factor number of times checking
5798 is pointless, too. */
5799 th = LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo);
5800 if (th >= LOOP_VINFO_VECT_FACTOR (loop_vinfo) - 1
5801 && !LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
5803 if (dump_enabled_p ())
5804 dump_printf_loc (MSG_NOTE, vect_location,
5805 "Profitability threshold is %d loop iterations.\n",
5806 th);
5807 check_profitability = true;
5810 /* Version the loop first, if required, so the profitability check
5811 comes first. */
5813 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
5814 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
5816 vect_loop_versioning (loop_vinfo, th, check_profitability);
5817 check_profitability = false;
5820 tree ni_name = vect_build_loop_niters (loop_vinfo);
5821 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo) = ni_name;
5823 /* Peel the loop if there are data refs with unknown alignment.
5824 Only one data ref with unknown store is allowed. */
5826 if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo))
5828 vect_do_peeling_for_alignment (loop_vinfo, ni_name,
5829 th, check_profitability);
5830 check_profitability = false;
5831 /* The above adjusts LOOP_VINFO_NITERS, so cause ni_name to
5832 be re-computed. */
5833 ni_name = NULL_TREE;
5836 /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
5837 compile time constant), or it is a constant that doesn't divide by the
5838 vectorization factor, then an epilog loop needs to be created.
5839 We therefore duplicate the loop: the original loop will be vectorized,
5840 and will compute the first (n/VF) iterations. The second copy of the loop
5841 will remain scalar and will compute the remaining (n%VF) iterations.
5842 (VF is the vectorization factor). */
5844 if (LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo)
5845 || LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo))
5847 tree ratio_mult_vf;
5848 if (!ni_name)
5849 ni_name = vect_build_loop_niters (loop_vinfo);
5850 vect_generate_tmps_on_preheader (loop_vinfo, ni_name, &ratio_mult_vf,
5851 &ratio);
5852 vect_do_peeling_for_loop_bound (loop_vinfo, ni_name, ratio_mult_vf,
5853 th, check_profitability);
5855 else if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
5856 ratio = build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo)),
5857 LOOP_VINFO_INT_NITERS (loop_vinfo) / vectorization_factor);
5858 else
5860 if (!ni_name)
5861 ni_name = vect_build_loop_niters (loop_vinfo);
5862 vect_generate_tmps_on_preheader (loop_vinfo, ni_name, NULL, &ratio);
5865 /* 1) Make sure the loop header has exactly two entries
5866 2) Make sure we have a preheader basic block. */
5868 gcc_assert (EDGE_COUNT (loop->header->preds) == 2);
5870 split_edge (loop_preheader_edge (loop));
5872 /* FORNOW: the vectorizer supports only loops which body consist
5873 of one basic block (header + empty latch). When the vectorizer will
5874 support more involved loop forms, the order by which the BBs are
5875 traversed need to be reconsidered. */
5877 for (i = 0; i < nbbs; i++)
5879 basic_block bb = bbs[i];
5880 stmt_vec_info stmt_info;
5881 gimple phi;
5883 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
5885 phi = gsi_stmt (si);
5886 if (dump_enabled_p ())
5888 dump_printf_loc (MSG_NOTE, vect_location,
5889 "------>vectorizing phi: ");
5890 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
5891 dump_printf (MSG_NOTE, "\n");
5893 stmt_info = vinfo_for_stmt (phi);
5894 if (!stmt_info)
5895 continue;
5897 if (MAY_HAVE_DEBUG_STMTS && !STMT_VINFO_LIVE_P (stmt_info))
5898 vect_loop_kill_debug_uses (loop, phi);
5900 if (!STMT_VINFO_RELEVANT_P (stmt_info)
5901 && !STMT_VINFO_LIVE_P (stmt_info))
5902 continue;
5904 if (STMT_VINFO_VECTYPE (stmt_info)
5905 && (TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info))
5906 != (unsigned HOST_WIDE_INT) vectorization_factor)
5907 && dump_enabled_p ())
5908 dump_printf_loc (MSG_NOTE, vect_location, "multiple-types.\n");
5910 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def)
5912 if (dump_enabled_p ())
5913 dump_printf_loc (MSG_NOTE, vect_location, "transform phi.\n");
5914 vect_transform_stmt (phi, NULL, NULL, NULL, NULL);
5918 pattern_stmt = NULL;
5919 for (si = gsi_start_bb (bb); !gsi_end_p (si) || transform_pattern_stmt;)
5921 bool is_store;
5923 if (transform_pattern_stmt)
5924 stmt = pattern_stmt;
5925 else
5927 stmt = gsi_stmt (si);
5928 /* During vectorization remove existing clobber stmts. */
5929 if (gimple_clobber_p (stmt))
5931 unlink_stmt_vdef (stmt);
5932 gsi_remove (&si, true);
5933 release_defs (stmt);
5934 continue;
5938 if (dump_enabled_p ())
5940 dump_printf_loc (MSG_NOTE, vect_location,
5941 "------>vectorizing statement: ");
5942 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
5943 dump_printf (MSG_NOTE, "\n");
5946 stmt_info = vinfo_for_stmt (stmt);
5948 /* vector stmts created in the outer-loop during vectorization of
5949 stmts in an inner-loop may not have a stmt_info, and do not
5950 need to be vectorized. */
5951 if (!stmt_info)
5953 gsi_next (&si);
5954 continue;
5957 if (MAY_HAVE_DEBUG_STMTS && !STMT_VINFO_LIVE_P (stmt_info))
5958 vect_loop_kill_debug_uses (loop, stmt);
5960 if (!STMT_VINFO_RELEVANT_P (stmt_info)
5961 && !STMT_VINFO_LIVE_P (stmt_info))
5963 if (STMT_VINFO_IN_PATTERN_P (stmt_info)
5964 && (pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info))
5965 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt))
5966 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt))))
5968 stmt = pattern_stmt;
5969 stmt_info = vinfo_for_stmt (stmt);
5971 else
5973 gsi_next (&si);
5974 continue;
5977 else if (STMT_VINFO_IN_PATTERN_P (stmt_info)
5978 && (pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info))
5979 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt))
5980 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt))))
5981 transform_pattern_stmt = true;
5983 /* If pattern statement has def stmts, vectorize them too. */
5984 if (is_pattern_stmt_p (stmt_info))
5986 if (pattern_def_seq == NULL)
5988 pattern_def_seq = STMT_VINFO_PATTERN_DEF_SEQ (stmt_info);
5989 pattern_def_si = gsi_start (pattern_def_seq);
5991 else if (!gsi_end_p (pattern_def_si))
5992 gsi_next (&pattern_def_si);
5993 if (pattern_def_seq != NULL)
5995 gimple pattern_def_stmt = NULL;
5996 stmt_vec_info pattern_def_stmt_info = NULL;
5998 while (!gsi_end_p (pattern_def_si))
6000 pattern_def_stmt = gsi_stmt (pattern_def_si);
6001 pattern_def_stmt_info
6002 = vinfo_for_stmt (pattern_def_stmt);
6003 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info)
6004 || STMT_VINFO_LIVE_P (pattern_def_stmt_info))
6005 break;
6006 gsi_next (&pattern_def_si);
6009 if (!gsi_end_p (pattern_def_si))
6011 if (dump_enabled_p ())
6013 dump_printf_loc (MSG_NOTE, vect_location,
6014 "==> vectorizing pattern def "
6015 "stmt: ");
6016 dump_gimple_stmt (MSG_NOTE, TDF_SLIM,
6017 pattern_def_stmt, 0);
6018 dump_printf (MSG_NOTE, "\n");
6021 stmt = pattern_def_stmt;
6022 stmt_info = pattern_def_stmt_info;
6024 else
6026 pattern_def_si = gsi_none ();
6027 transform_pattern_stmt = false;
6030 else
6031 transform_pattern_stmt = false;
6034 if (STMT_VINFO_VECTYPE (stmt_info))
6036 unsigned int nunits
6037 = (unsigned int)
6038 TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info));
6039 if (!STMT_SLP_TYPE (stmt_info)
6040 && nunits != (unsigned int) vectorization_factor
6041 && dump_enabled_p ())
6042 /* For SLP VF is set according to unrolling factor, and not
6043 to vector size, hence for SLP this print is not valid. */
6044 dump_printf_loc (MSG_NOTE, vect_location, "multiple-types.\n");
6047 /* SLP. Schedule all the SLP instances when the first SLP stmt is
6048 reached. */
6049 if (STMT_SLP_TYPE (stmt_info))
6051 if (!slp_scheduled)
6053 slp_scheduled = true;
6055 if (dump_enabled_p ())
6056 dump_printf_loc (MSG_NOTE, vect_location,
6057 "=== scheduling SLP instances ===\n");
6059 vect_schedule_slp (loop_vinfo, NULL);
6062 /* Hybrid SLP stmts must be vectorized in addition to SLP. */
6063 if (!vinfo_for_stmt (stmt) || PURE_SLP_STMT (stmt_info))
6065 if (!transform_pattern_stmt && gsi_end_p (pattern_def_si))
6067 pattern_def_seq = NULL;
6068 gsi_next (&si);
6070 continue;
6074 /* -------- vectorize statement ------------ */
6075 if (dump_enabled_p ())
6076 dump_printf_loc (MSG_NOTE, vect_location, "transform statement.\n");
6078 grouped_store = false;
6079 is_store = vect_transform_stmt (stmt, &si, &grouped_store, NULL, NULL);
6080 if (is_store)
6082 if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
6084 /* Interleaving. If IS_STORE is TRUE, the vectorization of the
6085 interleaving chain was completed - free all the stores in
6086 the chain. */
6087 gsi_next (&si);
6088 vect_remove_stores (GROUP_FIRST_ELEMENT (stmt_info));
6090 else
6092 /* Free the attached stmt_vec_info and remove the stmt. */
6093 gimple store = gsi_stmt (si);
6094 free_stmt_vec_info (store);
6095 unlink_stmt_vdef (store);
6096 gsi_remove (&si, true);
6097 release_defs (store);
6100 /* Stores can only appear at the end of pattern statements. */
6101 gcc_assert (!transform_pattern_stmt);
6102 pattern_def_seq = NULL;
6104 else if (!transform_pattern_stmt && gsi_end_p (pattern_def_si))
6106 pattern_def_seq = NULL;
6107 gsi_next (&si);
6109 } /* stmts in BB */
6110 } /* BBs in loop */
6112 slpeel_make_loop_iterate_ntimes (loop, ratio);
6114 /* Reduce loop iterations by the vectorization factor. */
6115 scale_loop_profile (loop, GCOV_COMPUTE_SCALE (1, vectorization_factor),
6116 expected_iterations / vectorization_factor);
6117 loop->nb_iterations_upper_bound
6118 = wi::udiv_floor (loop->nb_iterations_upper_bound, vectorization_factor);
6119 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo)
6120 && loop->nb_iterations_upper_bound != 0)
6121 loop->nb_iterations_upper_bound = loop->nb_iterations_upper_bound - 1;
6122 if (loop->any_estimate)
6124 loop->nb_iterations_estimate
6125 = wi::udiv_floor (loop->nb_iterations_estimate, vectorization_factor);
6126 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo)
6127 && loop->nb_iterations_estimate != 0)
6128 loop->nb_iterations_estimate = loop->nb_iterations_estimate - 1;
6131 if (dump_enabled_p ())
6133 dump_printf_loc (MSG_NOTE, vect_location,
6134 "LOOP VECTORIZED\n");
6135 if (loop->inner)
6136 dump_printf_loc (MSG_NOTE, vect_location,
6137 "OUTER LOOP VECTORIZED\n");
6138 dump_printf (MSG_NOTE, "\n");