1/* Loop Vectorization
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com> and
4 Ira Rosen <irar@il.ibm.com>
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3. If not see
20<http://www.gnu.org/licenses/>. */
21
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "backend.h"
26#include "target.h"
27#include "rtl.h"
28#include "tree.h"
29#include "gimple.h"
30#include "cfghooks.h"
31#include "tree-pass.h"
32#include "ssa.h"
33#include "optabs-tree.h"
34#include "diagnostic-core.h"
35#include "fold-const.h"
36#include "stor-layout.h"
37#include "cfganal.h"
38#include "gimplify.h"
39#include "gimple-iterator.h"
40#include "gimplify-me.h"
41#include "tree-ssa-loop-ivopts.h"
42#include "tree-ssa-loop-manip.h"
43#include "tree-ssa-loop-niter.h"
44#include "tree-ssa-loop.h"
45#include "cfgloop.h"
46#include "params.h"
47#include "tree-scalar-evolution.h"
48#include "tree-vectorizer.h"
49#include "gimple-fold.h"
50#include "cgraph.h"
51#include "tree-cfg.h"
52#include "tree-if-conv.h"
53#include "internal-fn.h"
54#include "tree-vector-builder.h"
55
56/* Loop Vectorization Pass.
57
58 This pass tries to vectorize loops.
59
60 For example, the vectorizer transforms the following simple loop:
61
62 short a[N]; short b[N]; short c[N]; int i;
63
64 for (i=0; i<N; i++){
65 a[i] = b[i] + c[i];
66 }
67
68 as if it was manually vectorized by rewriting the source code into:
69
70 typedef int __attribute__((mode(V8HI))) v8hi;
71 short a[N]; short b[N]; short c[N]; int i;
72 v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
73 v8hi va, vb, vc;
74
75 for (i=0; i<N/8; i++){
76 vb = pb[i];
77 vc = pc[i];
78 va = vb + vc;
79 pa[i] = va;
80 }
81
82 The main entry to this pass is vectorize_loops(), in which
83 the vectorizer applies a set of analyses on a given set of loops,
84 followed by the actual vectorization transformation for the loops that
85 had successfully passed the analysis phase.
86 Throughout this pass we make a distinction between two types of
87 data: scalars (which are represented by SSA_NAMES), and memory references
88 ("data-refs"). These two types of data require different handling both
89 during analysis and transformation. The types of data-refs that the
90 vectorizer currently supports are ARRAY_REFS which base is an array DECL
91 (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
92 accesses are required to have a simple (consecutive) access pattern.
93
94 Analysis phase:
95 ===============
96 The driver for the analysis phase is vect_analyze_loop().
97 It applies a set of analyses, some of which rely on the scalar evolution
98 analyzer (scev) developed by Sebastian Pop.
99
100 During the analysis phase the vectorizer records some information
101 per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
102 loop, as well as general information about the loop as a whole, which is
103 recorded in a "loop_vec_info" struct attached to each loop.
104
105 Transformation phase:
106 =====================
107 The loop transformation phase scans all the stmts in the loop, and
108 creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
109 the loop that needs to be vectorized. It inserts the vector code sequence
110 just before the scalar stmt S, and records a pointer to the vector code
111 in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
112 attached to S). This pointer will be used for the vectorization of following
113 stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
114 otherwise, we rely on dead code elimination for removing it.
115
116 For example, say stmt S1 was vectorized into stmt VS1:
117
118 VS1: vb = px[i];
119 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
120 S2: a = b;
121
122 To vectorize stmt S2, the vectorizer first finds the stmt that defines
123 the operand 'b' (S1), and gets the relevant vector def 'vb' from the
124 vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
125 resulting sequence would be:
126
127 VS1: vb = px[i];
128 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
129 VS2: va = vb;
130 S2: a = b; STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
131
132 Operands that are not SSA_NAMEs, are data-refs that appear in
133 load/store operations (like 'x[i]' in S1), and are handled differently.
134
135 Target modeling:
136 =================
137 Currently the only target specific information that is used is the
138 size of the vector (in bytes) - "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD".
139 Targets that can support different sizes of vectors, for now will need
140 to specify one value for "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD". More
141 flexibility will be added in the future.
142
143 Since we only vectorize operations which vector form can be
144 expressed using existing tree codes, to verify that an operation is
145 supported, the vectorizer checks the relevant optab at the relevant
146 machine_mode (e.g, optab_handler (add_optab, V8HImode)). If
147 the value found is CODE_FOR_nothing, then there's no target support, and
148 we can't vectorize the stmt.
149
150 For additional information on this project see:
151 http://gcc.gnu.org/projects/tree-ssa/vectorization.html
152*/
153
154static void vect_estimate_min_profitable_iters (loop_vec_info, int *, int *);
155
156/* Function vect_determine_vectorization_factor
157
158 Determine the vectorization factor (VF). VF is the number of data elements
159 that are operated upon in parallel in a single iteration of the vectorized
160 loop. For example, when vectorizing a loop that operates on 4byte elements,
161 on a target with vector size (VS) 16byte, the VF is set to 4, since 4
162 elements can fit in a single vector register.
163
164 We currently support vectorization of loops in which all types operated upon
165 are of the same size. Therefore this function currently sets VF according to
166 the size of the types operated upon, and fails if there are multiple sizes
167 in the loop.
168
169 VF is also the factor by which the loop iterations are strip-mined, e.g.:
170 original loop:
171 for (i=0; i<N; i++){
172 a[i] = b[i] + c[i];
173 }
174
175 vectorized loop:
176 for (i=0; i<N; i+=VF){
177 a[i:VF] = b[i:VF] + c[i:VF];
178 }
179*/
180
181static bool
182vect_determine_vectorization_factor (loop_vec_info loop_vinfo)
183{
184 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
185 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
186 unsigned nbbs = loop->num_nodes;
187 unsigned int vectorization_factor = 0;
188 tree scalar_type = NULL_TREE;
189 gphi *phi;
190 tree vectype;
191 unsigned int nunits;
192 stmt_vec_info stmt_info;
193 unsigned i;
194 HOST_WIDE_INT dummy;
195 gimple *stmt, *pattern_stmt = NULL;
196 gimple_seq pattern_def_seq = NULL;
197 gimple_stmt_iterator pattern_def_si = gsi_none ();
198 bool analyze_pattern_stmt = false;
199 bool bool_result;
200 auto_vec<stmt_vec_info> mask_producers;
201
202 if (dump_enabled_p ())
203 dump_printf_loc (MSG_NOTE, vect_location,
204 "=== vect_determine_vectorization_factor ===\n");
205
206 for (i = 0; i < nbbs; i++)
207 {
208 basic_block bb = bbs[i];
209
210 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
211 gsi_next (&si))
212 {
213 phi = si.phi ();
214 stmt_info = vinfo_for_stmt (phi);
215 if (dump_enabled_p ())
216 {
217 dump_printf_loc (MSG_NOTE, vect_location, "==> examining phi: ");
218 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
219 }
220
221 gcc_assert (stmt_info);
222
223 if (STMT_VINFO_RELEVANT_P (stmt_info)
224 || STMT_VINFO_LIVE_P (stmt_info))
225 {
226 gcc_assert (!STMT_VINFO_VECTYPE (stmt_info));
227 scalar_type = TREE_TYPE (PHI_RESULT (phi));
228
229 if (dump_enabled_p ())
230 {
231 dump_printf_loc (MSG_NOTE, vect_location,
232 "get vectype for scalar type: ");
233 dump_generic_expr (MSG_NOTE, TDF_SLIM, scalar_type);
234 dump_printf (MSG_NOTE, "\n");
235 }
236
237 vectype = get_vectype_for_scalar_type (scalar_type);
238 if (!vectype)
239 {
240 if (dump_enabled_p ())
241 {
242 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
243 "not vectorized: unsupported "
244 "data-type ");
245 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
246 scalar_type);
247 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
248 }
249 return false;
250 }
251 STMT_VINFO_VECTYPE (stmt_info) = vectype;
252
253 if (dump_enabled_p ())
254 {
255 dump_printf_loc (MSG_NOTE, vect_location, "vectype: ");
256 dump_generic_expr (MSG_NOTE, TDF_SLIM, vectype);
257 dump_printf (MSG_NOTE, "\n");
258 }
259
260 nunits = TYPE_VECTOR_SUBPARTS (vectype);
261 if (dump_enabled_p ())
262 dump_printf_loc (MSG_NOTE, vect_location, "nunits = %d\n",
263 nunits);
264
265 if (!vectorization_factor
266 || (nunits > vectorization_factor))
267 vectorization_factor = nunits;
268 }
269 }
270
271 for (gimple_stmt_iterator si = gsi_start_bb (bb);
272 !gsi_end_p (si) || analyze_pattern_stmt;)
273 {
274 tree vf_vectype;
275
276 if (analyze_pattern_stmt)
277 stmt = pattern_stmt;
278 else
279 stmt = gsi_stmt (si);
280
281 stmt_info = vinfo_for_stmt (stmt);
282
283 if (dump_enabled_p ())
284 {
285 dump_printf_loc (MSG_NOTE, vect_location,
286 "==> examining statement: ");
287 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
288 }
289
290 gcc_assert (stmt_info);
291
292 /* Skip stmts which do not need to be vectorized. */
293 if ((!STMT_VINFO_RELEVANT_P (stmt_info)
294 && !STMT_VINFO_LIVE_P (stmt_info))
295 || gimple_clobber_p (stmt))
296 {
297 if (STMT_VINFO_IN_PATTERN_P (stmt_info)
298 && (pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info))
299 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt))
300 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt))))
301 {
302 stmt = pattern_stmt;
303 stmt_info = vinfo_for_stmt (pattern_stmt);
304 if (dump_enabled_p ())
305 {
306 dump_printf_loc (MSG_NOTE, vect_location,
307 "==> examining pattern statement: ");
308 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
309 }
310 }
311 else
312 {
313 if (dump_enabled_p ())
314 dump_printf_loc (MSG_NOTE, vect_location, "skip.\n");
315 gsi_next (&si);
316 continue;
317 }
318 }
319 else if (STMT_VINFO_IN_PATTERN_P (stmt_info)
320 && (pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info))
321 && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt))
322 || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt))))
323 analyze_pattern_stmt = true;
324
325 /* If a pattern statement has def stmts, analyze them too. */
326 if (is_pattern_stmt_p (stmt_info))
327 {
328 if (pattern_def_seq == NULL)
329 {
330 pattern_def_seq = STMT_VINFO_PATTERN_DEF_SEQ (stmt_info);
331 pattern_def_si = gsi_start (pattern_def_seq);
332 }
333 else if (!gsi_end_p (pattern_def_si))
334 gsi_next (&pattern_def_si);
335 if (pattern_def_seq != NULL)
336 {
337 gimple *pattern_def_stmt = NULL;
338 stmt_vec_info pattern_def_stmt_info = NULL;
339
340 while (!gsi_end_p (pattern_def_si))
341 {
342 pattern_def_stmt = gsi_stmt (pattern_def_si);
343 pattern_def_stmt_info
344 = vinfo_for_stmt (pattern_def_stmt);
345 if (STMT_VINFO_RELEVANT_P (pattern_def_stmt_info)
346 || STMT_VINFO_LIVE_P (pattern_def_stmt_info))
347 break;
348 gsi_next (&pattern_def_si);
349 }
350
351 if (!gsi_end_p (pattern_def_si))
352 {
353 if (dump_enabled_p ())
354 {
355 dump_printf_loc (MSG_NOTE, vect_location,
356 "==> examining pattern def stmt: ");
357 dump_gimple_stmt (MSG_NOTE, TDF_SLIM,
358 pattern_def_stmt, 0);
359 }
360
361 stmt = pattern_def_stmt;
362 stmt_info = pattern_def_stmt_info;
363 }
364 else
365 {
366 pattern_def_si = gsi_none ();
367 analyze_pattern_stmt = false;
368 }
369 }
370 else
371 analyze_pattern_stmt = false;
372 }
373
374 if (gimple_get_lhs (stmt) == NULL_TREE
375 /* MASK_STORE has no lhs, but is ok. */
376 && (!is_gimple_call (stmt)
377 || !gimple_call_internal_p (stmt)
378 || gimple_call_internal_fn (stmt) != IFN_MASK_STORE))
379 {
380 if (is_gimple_call (stmt))
381 {
382 /* Ignore calls with no lhs. These must be calls to
383 #pragma omp simd functions, and what vectorization factor
384 it really needs can't be determined until
385 vectorizable_simd_clone_call. */
386 if (!analyze_pattern_stmt && gsi_end_p (pattern_def_si))
387 {
388 pattern_def_seq = NULL;
389 gsi_next (&si);
390 }
391 continue;
392 }
393 if (dump_enabled_p ())
394 {
395 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
396 "not vectorized: irregular stmt.");
397 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt,
398 0);
399 }
400 return false;
401 }
402
403 if (VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt))))
404 {
405 if (dump_enabled_p ())
406 {
407 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
408 "not vectorized: vector stmt in loop:");
409 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
410 }
411 return false;
412 }
413
414 bool_result = false;
415
416 if (STMT_VINFO_VECTYPE (stmt_info))
417 {
418 /* The only case when a vectype had been already set is for stmts
419 that contain a dataref, or for "pattern-stmts" (stmts
420 generated by the vectorizer to represent/replace a certain
421 idiom). */
422 gcc_assert (STMT_VINFO_DATA_REF (stmt_info)
423 || is_pattern_stmt_p (stmt_info)
424 || !gsi_end_p (pattern_def_si));
425 vectype = STMT_VINFO_VECTYPE (stmt_info);
426 }
427 else
428 {
429 gcc_assert (!STMT_VINFO_DATA_REF (stmt_info));
430 if (gimple_call_internal_p (stmt, IFN_MASK_STORE))
431 scalar_type = TREE_TYPE (gimple_call_arg (stmt, 3));
432 else
433 scalar_type = TREE_TYPE (gimple_get_lhs (stmt));
434
435 /* Bool ops don't participate in vectorization factor
436 computation. For comparison use compared types to
437 compute a factor. */
438 if (VECT_SCALAR_BOOLEAN_TYPE_P (scalar_type)
439 && is_gimple_assign (stmt)
440 && gimple_assign_rhs_code (stmt) != COND_EXPR)
441 {
442 if (STMT_VINFO_RELEVANT_P (stmt_info)
443 || STMT_VINFO_LIVE_P (stmt_info))
444 mask_producers.safe_push (stmt_info);
445 bool_result = true;
446
447 if (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt))
448 == tcc_comparison
449 && !VECT_SCALAR_BOOLEAN_TYPE_P
450 (TREE_TYPE (gimple_assign_rhs1 (stmt))))
451 scalar_type = TREE_TYPE (gimple_assign_rhs1 (stmt));
452 else
453 {
454 if (!analyze_pattern_stmt && gsi_end_p (pattern_def_si))
455 {
456 pattern_def_seq = NULL;
457 gsi_next (&si);
458 }
459 continue;
460 }
461 }
462
463 if (dump_enabled_p ())
464 {
465 dump_printf_loc (MSG_NOTE, vect_location,
466 "get vectype for scalar type: ");
467 dump_generic_expr (MSG_NOTE, TDF_SLIM, scalar_type);
468 dump_printf (MSG_NOTE, "\n");
469 }
470 vectype = get_vectype_for_scalar_type (scalar_type);
471 if (!vectype)
472 {
473 if (dump_enabled_p ())
474 {
475 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
476 "not vectorized: unsupported "
477 "data-type ");
478 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
479 scalar_type);
480 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
481 }
482 return false;
483 }
484
485 if (!bool_result)
486 STMT_VINFO_VECTYPE (stmt_info) = vectype;
487
488 if (dump_enabled_p ())
489 {
490 dump_printf_loc (MSG_NOTE, vect_location, "vectype: ");
491 dump_generic_expr (MSG_NOTE, TDF_SLIM, vectype);
492 dump_printf (MSG_NOTE, "\n");
493 }
494 }
495
496 /* Don't try to compute VF out scalar types if we stmt
497 produces boolean vector. Use result vectype instead. */
498 if (VECTOR_BOOLEAN_TYPE_P (vectype))
499 vf_vectype = vectype;
500 else
501 {
502 /* The vectorization factor is according to the smallest
503 scalar type (or the largest vector size, but we only
504 support one vector size per loop). */
505 if (!bool_result)
506 scalar_type = vect_get_smallest_scalar_type (stmt, &dummy,
507 &dummy);
508 if (dump_enabled_p ())
509 {
510 dump_printf_loc (MSG_NOTE, vect_location,
511 "get vectype for scalar type: ");
512 dump_generic_expr (MSG_NOTE, TDF_SLIM, scalar_type);
513 dump_printf (MSG_NOTE, "\n");
514 }
515 vf_vectype = get_vectype_for_scalar_type (scalar_type);
516 }
517 if (!vf_vectype)
518 {
519 if (dump_enabled_p ())
520 {
521 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
522 "not vectorized: unsupported data-type ");
523 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
524 scalar_type);
525 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
526 }
527 return false;
528 }
529
530 if ((GET_MODE_SIZE (TYPE_MODE (vectype))
531 != GET_MODE_SIZE (TYPE_MODE (vf_vectype))))
532 {
533 if (dump_enabled_p ())
534 {
535 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
536 "not vectorized: different sized vector "
537 "types in statement, ");
538 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
539 vectype);
540 dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
541 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
542 vf_vectype);
543 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
544 }
545 return false;
546 }
547
548 if (dump_enabled_p ())
549 {
550 dump_printf_loc (MSG_NOTE, vect_location, "vectype: ");
551 dump_generic_expr (MSG_NOTE, TDF_SLIM, vf_vectype);
552 dump_printf (MSG_NOTE, "\n");
553 }
554
555 nunits = TYPE_VECTOR_SUBPARTS (vf_vectype);
556 if (dump_enabled_p ())
557 dump_printf_loc (MSG_NOTE, vect_location, "nunits = %d\n", nunits);
558 if (!vectorization_factor
559 || (nunits > vectorization_factor))
560 vectorization_factor = nunits;
561
562 if (!analyze_pattern_stmt && gsi_end_p (pattern_def_si))
563 {
564 pattern_def_seq = NULL;
565 gsi_next (&si);
566 }
567 }
568 }
569
570 /* TODO: Analyze cost. Decide if worth while to vectorize. */
571 if (dump_enabled_p ())
572 dump_printf_loc (MSG_NOTE, vect_location, "vectorization factor = %d\n",
573 vectorization_factor);
574 if (vectorization_factor <= 1)
575 {
576 if (dump_enabled_p ())
577 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
578 "not vectorized: unsupported data-type\n");
579 return false;
580 }
581 LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
582
583 for (i = 0; i < mask_producers.length (); i++)
584 {
585 tree mask_type = NULL;
586
587 stmt = STMT_VINFO_STMT (mask_producers[i]);
588
589 if (is_gimple_assign (stmt)
590 && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison
591 && !VECT_SCALAR_BOOLEAN_TYPE_P
592 (TREE_TYPE (gimple_assign_rhs1 (stmt))))
593 {
594 scalar_type = TREE_TYPE (gimple_assign_rhs1 (stmt));
595 mask_type = get_mask_type_for_scalar_type (scalar_type);
596
597 if (!mask_type)
598 {
599 if (dump_enabled_p ())
600 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
601 "not vectorized: unsupported mask\n");
602 return false;
603 }
604 }
605 else
606 {
607 tree rhs;
608 ssa_op_iter iter;
609 gimple *def_stmt;
610 enum vect_def_type dt;
611
612 FOR_EACH_SSA_TREE_OPERAND (rhs, stmt, iter, SSA_OP_USE)
613 {
614 if (!vect_is_simple_use (rhs, mask_producers[i]->vinfo,
615 &def_stmt, &dt, &vectype))
616 {
617 if (dump_enabled_p ())
618 {
619 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
620 "not vectorized: can't compute mask type "
621 "for statement, ");
622 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt,
623 0);
624 }
625 return false;
626 }
627
628 /* No vectype probably means external definition.
629 Allow it in case there is another operand which
630 allows to determine mask type. */
631 if (!vectype)
632 continue;
633
634 if (!mask_type)
635 mask_type = vectype;
636 else if (TYPE_VECTOR_SUBPARTS (mask_type)
637 != TYPE_VECTOR_SUBPARTS (vectype))
638 {
639 if (dump_enabled_p ())
640 {
641 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
642 "not vectorized: different sized masks "
643 "types in statement, ");
644 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
645 mask_type);
646 dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
647 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
648 vectype);
649 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
650 }
651 return false;
652 }
653 else if (VECTOR_BOOLEAN_TYPE_P (mask_type)
654 != VECTOR_BOOLEAN_TYPE_P (vectype))
655 {
656 if (dump_enabled_p ())
657 {
658 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
659 "not vectorized: mixed mask and "
660 "nonmask vector types in statement, ");
661 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
662 mask_type);
663 dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
664 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
665 vectype);
666 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
667 }
668 return false;
669 }
670 }
671
672 /* We may compare boolean value loaded as vector of integers.
673 Fix mask_type in such case. */
674 if (mask_type
675 && !VECTOR_BOOLEAN_TYPE_P (mask_type)
676 && gimple_code (stmt) == GIMPLE_ASSIGN
677 && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison)
678 mask_type = build_same_sized_truth_vector_type (mask_type);
679 }
680
681 /* No mask_type should mean loop invariant predicate.
682 This is probably a subject for optimization in
683 if-conversion. */
684 if (!mask_type)
685 {
686 if (dump_enabled_p ())
687 {
688 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
689 "not vectorized: can't compute mask type "
690 "for statement, ");
691 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt,
692 0);
693 }
694 return false;
695 }
696
697 STMT_VINFO_VECTYPE (mask_producers[i]) = mask_type;
698 }
699
700 return true;
701}
702
703
704/* Function vect_is_simple_iv_evolution.
705
706 FORNOW: A simple evolution of an induction variables in the loop is
707 considered a polynomial evolution. */
708
709static bool
710vect_is_simple_iv_evolution (unsigned loop_nb, tree access_fn, tree * init,
711 tree * step)
712{
713 tree init_expr;
714 tree step_expr;
715 tree evolution_part = evolution_part_in_loop_num (access_fn, loop_nb);
716 basic_block bb;
717
718 /* When there is no evolution in this loop, the evolution function
719 is not "simple". */
720 if (evolution_part == NULL_TREE)
721 return false;
722
723 /* When the evolution is a polynomial of degree >= 2
724 the evolution function is not "simple". */
725 if (tree_is_chrec (evolution_part))
726 return false;
727
728 step_expr = evolution_part;
729 init_expr = unshare_expr (initial_condition_in_loop_num (access_fn, loop_nb));
730
731 if (dump_enabled_p ())
732 {
733 dump_printf_loc (MSG_NOTE, vect_location, "step: ");
734 dump_generic_expr (MSG_NOTE, TDF_SLIM, step_expr);
735 dump_printf (MSG_NOTE, ", init: ");
736 dump_generic_expr (MSG_NOTE, TDF_SLIM, init_expr);
737 dump_printf (MSG_NOTE, "\n");
738 }
739
740 *init = init_expr;
741 *step = step_expr;
742
743 if (TREE_CODE (step_expr) != INTEGER_CST
744 && (TREE_CODE (step_expr) != SSA_NAME
745 || ((bb = gimple_bb (SSA_NAME_DEF_STMT (step_expr)))
746 && flow_bb_inside_loop_p (get_loop (cfun, loop_nb), bb))
747 || (!INTEGRAL_TYPE_P (TREE_TYPE (step_expr))
748 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (step_expr))
749 || !flag_associative_math)))
750 && (TREE_CODE (step_expr) != REAL_CST
751 || !flag_associative_math))
752 {
753 if (dump_enabled_p ())
754 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
755 "step unknown.\n");
756 return false;
757 }
758
759 return true;
760}
761
762/* Function vect_analyze_scalar_cycles_1.
763
764 Examine the cross iteration def-use cycles of scalar variables
765 in LOOP. LOOP_VINFO represents the loop that is now being
766 considered for vectorization (can be LOOP, or an outer-loop
767 enclosing LOOP). */
768
769static void
770vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo, struct loop *loop)
771{
772 basic_block bb = loop->header;
773 tree init, step;
774 auto_vec<gimple *, 64> worklist;
775 gphi_iterator gsi;
776 bool double_reduc;
777
778 if (dump_enabled_p ())
779 dump_printf_loc (MSG_NOTE, vect_location,
780 "=== vect_analyze_scalar_cycles ===\n");
781
782 /* First - identify all inductions. Reduction detection assumes that all the
783 inductions have been identified, therefore, this order must not be
784 changed. */
785 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
786 {
787 gphi *phi = gsi.phi ();
788 tree access_fn = NULL;
789 tree def = PHI_RESULT (phi);
790 stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
791
792 if (dump_enabled_p ())
793 {
794 dump_printf_loc (MSG_NOTE, vect_location, "Analyze phi: ");
795 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
796 }
797
798 /* Skip virtual phi's. The data dependences that are associated with
799 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
800 if (virtual_operand_p (def))
801 continue;
802
803 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_unknown_def_type;
804
805 /* Analyze the evolution function. */
806 access_fn = analyze_scalar_evolution (loop, def);
807 if (access_fn)
808 {
809 STRIP_NOPS (access_fn);
810 if (dump_enabled_p ())
811 {
812 dump_printf_loc (MSG_NOTE, vect_location,
813 "Access function of PHI: ");
814 dump_generic_expr (MSG_NOTE, TDF_SLIM, access_fn);
815 dump_printf (MSG_NOTE, "\n");
816 }
817 STMT_VINFO_LOOP_PHI_EVOLUTION_BASE_UNCHANGED (stmt_vinfo)
818 = initial_condition_in_loop_num (access_fn, loop->num);
819 STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo)
820 = evolution_part_in_loop_num (access_fn, loop->num);
821 }
822
823 if (!access_fn
824 || !vect_is_simple_iv_evolution (loop->num, access_fn, &init, &step)
825 || (LOOP_VINFO_LOOP (loop_vinfo) != loop
826 && TREE_CODE (step) != INTEGER_CST))
827 {
828 worklist.safe_push (phi);
829 continue;
830 }
831
832 gcc_assert (STMT_VINFO_LOOP_PHI_EVOLUTION_BASE_UNCHANGED (stmt_vinfo)
833 != NULL_TREE);
834 gcc_assert (STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_vinfo) != NULL_TREE);
835
836 if (dump_enabled_p ())
837 dump_printf_loc (MSG_NOTE, vect_location, "Detected induction.\n");
838 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def;
839 }
840
841
842 /* Second - identify all reductions and nested cycles. */
843 while (worklist.length () > 0)
844 {
845 gimple *phi = worklist.pop ();
846 tree def = PHI_RESULT (phi);
847 stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
848 gimple *reduc_stmt;
849
850 if (dump_enabled_p ())
851 {
852 dump_printf_loc (MSG_NOTE, vect_location, "Analyze phi: ");
853 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
854 }
855
856 gcc_assert (!virtual_operand_p (def)
857 && STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_unknown_def_type);
858
859 reduc_stmt = vect_force_simple_reduction (loop_vinfo, phi,
860 &double_reduc, false);
861 if (reduc_stmt)
862 {
863 if (double_reduc)
864 {
865 if (dump_enabled_p ())
866 dump_printf_loc (MSG_NOTE, vect_location,
867 "Detected double reduction.\n");
868
869 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_double_reduction_def;
870 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
871 vect_double_reduction_def;
872 }
873 else
874 {
875 if (loop != LOOP_VINFO_LOOP (loop_vinfo))
876 {
877 if (dump_enabled_p ())
878 dump_printf_loc (MSG_NOTE, vect_location,
879 "Detected vectorizable nested cycle.\n");
880
881 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_nested_cycle;
882 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
883 vect_nested_cycle;
884 }
885 else
886 {
887 if (dump_enabled_p ())
888 dump_printf_loc (MSG_NOTE, vect_location,
889 "Detected reduction.\n");
890
891 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_reduction_def;
892 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
893 vect_reduction_def;
894 /* Store the reduction cycles for possible vectorization in
895 loop-aware SLP if it was not detected as reduction
896 chain. */
897 if (! GROUP_FIRST_ELEMENT (vinfo_for_stmt (reduc_stmt)))
898 LOOP_VINFO_REDUCTIONS (loop_vinfo).safe_push (reduc_stmt);
899 }
900 }
901 }
902 else
903 if (dump_enabled_p ())
904 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
905 "Unknown def-use cycle pattern.\n");
906 }
907}
908
909
910/* Function vect_analyze_scalar_cycles.
911
912 Examine the cross iteration def-use cycles of scalar variables, by
913 analyzing the loop-header PHIs of scalar variables. Classify each
914 cycle as one of the following: invariant, induction, reduction, unknown.
915 We do that for the loop represented by LOOP_VINFO, and also to its
916 inner-loop, if exists.
917 Examples for scalar cycles:
918
919 Example1: reduction:
920
921 loop1:
922 for (i=0; i<N; i++)
923 sum += a[i];
924
925 Example2: induction:
926
927 loop2:
928 for (i=0; i<N; i++)
929 a[i] = i; */
930
931static void
932vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
933{
934 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
935
936 vect_analyze_scalar_cycles_1 (loop_vinfo, loop);
937
938 /* When vectorizing an outer-loop, the inner-loop is executed sequentially.
939 Reductions in such inner-loop therefore have different properties than
940 the reductions in the nest that gets vectorized:
941 1. When vectorized, they are executed in the same order as in the original
942 scalar loop, so we can't change the order of computation when
943 vectorizing them.
944 2. FIXME: Inner-loop reductions can be used in the inner-loop, so the
945 current checks are too strict. */
946
947 if (loop->inner)
948 vect_analyze_scalar_cycles_1 (loop_vinfo, loop->inner);
949}
950
951/* Transfer group and reduction information from STMT to its pattern stmt. */
952
953static void
954vect_fixup_reduc_chain (gimple *stmt)
955{
956 gimple *firstp = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt));
957 gimple *stmtp;
958 gcc_assert (!GROUP_FIRST_ELEMENT (vinfo_for_stmt (firstp))
959 && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)));
960 GROUP_SIZE (vinfo_for_stmt (firstp)) = GROUP_SIZE (vinfo_for_stmt (stmt));
961 do
962 {
963 stmtp = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt));
964 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmtp)) = firstp;
965 stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt));
966 if (stmt)
967 GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmtp))
968 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt));
969 }
970 while (stmt);
971 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (stmtp)) = vect_reduction_def;
972}
973
974/* Fixup scalar cycles that now have their stmts detected as patterns. */
975
976static void
977vect_fixup_scalar_cycles_with_patterns (loop_vec_info loop_vinfo)
978{
979 gimple *first;
980 unsigned i;
981
982 FOR_EACH_VEC_ELT (LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo), i, first)
983 if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (first)))
984 {
985 gimple *next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (first));
986 while (next)
987 {
988 if (! STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (next)))
989 break;
990 next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next));
991 }
992 /* If not all stmt in the chain are patterns try to handle
993 the chain without patterns. */
994 if (! next)
995 {
996 vect_fixup_reduc_chain (first);
997 LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo)[i]
998 = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first));
999 }
1000 }
1001}
1002
1003/* Function vect_get_loop_niters.
1004
1005 Determine how many iterations the loop is executed and place it
1006 in NUMBER_OF_ITERATIONS. Place the number of latch iterations
1007 in NUMBER_OF_ITERATIONSM1. Place the condition under which the
1008 niter information holds in ASSUMPTIONS.
1009
1010 Return the loop exit condition. */
1011
1012
1013static gcond *
1014vect_get_loop_niters (struct loop *loop, tree *assumptions,
1015 tree *number_of_iterations, tree *number_of_iterationsm1)
1016{
1017 edge exit = single_exit (loop);
1018 struct tree_niter_desc niter_desc;
1019 tree niter_assumptions, niter, may_be_zero;
1020 gcond *cond = get_loop_exit_condition (loop);
1021
1022 *assumptions = boolean_true_node;
1023 *number_of_iterationsm1 = chrec_dont_know;
1024 *number_of_iterations = chrec_dont_know;
1025 if (dump_enabled_p ())
1026 dump_printf_loc (MSG_NOTE, vect_location,
1027 "=== get_loop_niters ===\n");
1028
1029 if (!exit)
1030 return cond;
1031
1032 niter = chrec_dont_know;
1033 may_be_zero = NULL_TREE;
1034 niter_assumptions = boolean_true_node;
1035 if (!number_of_iterations_exit_assumptions (loop, exit, &niter_desc, NULL)
1036 || chrec_contains_undetermined (niter_desc.niter))
1037 return cond;
1038
1039 niter_assumptions = niter_desc.assumptions;
1040 may_be_zero = niter_desc.may_be_zero;
1041 niter = niter_desc.niter;
1042
1043 if (may_be_zero && integer_zerop (may_be_zero))
1044 may_be_zero = NULL_TREE;
1045
1046 if (may_be_zero)
1047 {
1048 if (COMPARISON_CLASS_P (may_be_zero))
1049 {
1050 /* Try to combine may_be_zero with assumptions, this can simplify
1051 computation of niter expression. */
1052 if (niter_assumptions && !integer_nonzerop (niter_assumptions))
1053 niter_assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1054 niter_assumptions,
1055 fold_build1 (TRUTH_NOT_EXPR,
1056 boolean_type_node,
1057 may_be_zero));
1058 else
1059 niter = fold_build3 (COND_EXPR, TREE_TYPE (niter), may_be_zero,
1060 build_int_cst (TREE_TYPE (niter), 0), niter);
1061
1062 may_be_zero = NULL_TREE;
1063 }
1064 else if (integer_nonzerop (may_be_zero))
1065 {
1066 *number_of_iterationsm1 = build_int_cst (TREE_TYPE (niter), 0);
1067 *number_of_iterations = build_int_cst (TREE_TYPE (niter), 1);
1068 return cond;
1069 }
1070 else
1071 return cond;
1072 }
1073
1074 *assumptions = niter_assumptions;
1075 *number_of_iterationsm1 = niter;
1076
1077 /* We want the number of loop header executions which is the number
1078 of latch executions plus one.
1079 ??? For UINT_MAX latch executions this number overflows to zero
1080 for loops like do { n++; } while (n != 0); */
1081 if (niter && !chrec_contains_undetermined (niter))
1082 niter = fold_build2 (PLUS_EXPR, TREE_TYPE (niter), unshare_expr (niter),
1083 build_int_cst (TREE_TYPE (niter), 1));
1084 *number_of_iterations = niter;
1085
1086 return cond;
1087}
1088
1089/* Function bb_in_loop_p
1090
1091 Used as predicate for dfs order traversal of the loop bbs. */
1092
1093static bool
1094bb_in_loop_p (const_basic_block bb, const void *data)
1095{
1096 const struct loop *const loop = (const struct loop *)data;
1097 if (flow_bb_inside_loop_p (loop, bb))
1098 return true;
1099 return false;
1100}
1101
1102
1103/* Create and initialize a new loop_vec_info struct for LOOP_IN, as well as
1104 stmt_vec_info structs for all the stmts in LOOP_IN. */
1105
1106_loop_vec_info::_loop_vec_info (struct loop *loop_in)
1107 : vec_info (vec_info::loop, init_cost (loop_in)),
1108 loop (loop_in),
1109 bbs (XCNEWVEC (basic_block, loop->num_nodes)),
1110 num_itersm1 (NULL_TREE),
1111 num_iters (NULL_TREE),
1112 num_iters_unchanged (NULL_TREE),
1113 num_iters_assumptions (NULL_TREE),
1114 th (0),
1115 vectorization_factor (0),
1116 max_vectorization_factor (0),
1117 unaligned_dr (NULL),
1118 peeling_for_alignment (0),
1119 ptr_mask (0),
1120 slp_unrolling_factor (1),
1121 single_scalar_iteration_cost (0),
1122 vectorizable (false),
1123 peeling_for_gaps (false),
1124 peeling_for_niter (false),
1125 operands_swapped (false),
1126 no_data_dependencies (false),
1127 has_mask_store (false),
1128 scalar_loop (NULL),
1129 orig_loop_info (NULL)
1130{
1131 /* Create/Update stmt_info for all stmts in the loop. */
1132 basic_block *body = get_loop_body (loop);
1133 for (unsigned int i = 0; i < loop->num_nodes; i++)
1134 {
1135 basic_block bb = body[i];
1136 gimple_stmt_iterator si;
1137
1138 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
1139 {
1140 gimple *phi = gsi_stmt (si);
1141 gimple_set_uid (phi, 0);
1142 set_vinfo_for_stmt (phi, new_stmt_vec_info (phi, this));
1143 }
1144
1145 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1146 {
1147 gimple *stmt = gsi_stmt (si);
1148 gimple_set_uid (stmt, 0);
1149 set_vinfo_for_stmt (stmt, new_stmt_vec_info (stmt, this));
1150 }
1151 }
1152 free (body);
1153
1154 /* CHECKME: We want to visit all BBs before their successors (except for
1155 latch blocks, for which this assertion wouldn't hold). In the simple
1156 case of the loop forms we allow, a dfs order of the BBs would the same
1157 as reversed postorder traversal, so we are safe. */
1158
1159 unsigned int nbbs = dfs_enumerate_from (loop->header, 0, bb_in_loop_p,
1160 bbs, loop->num_nodes, loop);
1161 gcc_assert (nbbs == loop->num_nodes);
1162}
1163
1164
1165/* Free all memory used by the _loop_vec_info, as well as all the
1166 stmt_vec_info structs of all the stmts in the loop. */
1167
1168_loop_vec_info::~_loop_vec_info ()
1169{
1170 int nbbs;
1171 gimple_stmt_iterator si;
1172 int j;
1173
1174 nbbs = loop->num_nodes;
1175 for (j = 0; j < nbbs; j++)
1176 {
1177 basic_block bb = bbs[j];
1178 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
1179 free_stmt_vec_info (gsi_stmt (si));
1180
1181 for (si = gsi_start_bb (bb); !gsi_end_p (si); )
1182 {
1183 gimple *stmt = gsi_stmt (si);
1184
1185 /* We may have broken canonical form by moving a constant
1186 into RHS1 of a commutative op. Fix such occurrences. */
1187 if (operands_swapped && is_gimple_assign (stmt))
1188 {
1189 enum tree_code code = gimple_assign_rhs_code (stmt);
1190
1191 if ((code == PLUS_EXPR
1192 || code == POINTER_PLUS_EXPR
1193 || code == MULT_EXPR)
1194 && CONSTANT_CLASS_P (gimple_assign_rhs1 (stmt)))
1195 swap_ssa_operands (stmt,
1196 gimple_assign_rhs1_ptr (stmt),
1197 gimple_assign_rhs2_ptr (stmt));
1198 else if (code == COND_EXPR
1199 && CONSTANT_CLASS_P (gimple_assign_rhs2 (stmt)))
1200 {
1201 tree cond_expr = gimple_assign_rhs1 (stmt);
1202 enum tree_code cond_code = TREE_CODE (cond_expr);
1203
1204 if (TREE_CODE_CLASS (cond_code) == tcc_comparison)
1205 {
1206 bool honor_nans = HONOR_NANS (TREE_OPERAND (cond_expr,
1207 0));
1208 cond_code = invert_tree_comparison (cond_code,
1209 honor_nans);
1210 if (cond_code != ERROR_MARK)
1211 {
1212 TREE_SET_CODE (cond_expr, cond_code);
1213 swap_ssa_operands (stmt,
1214 gimple_assign_rhs2_ptr (stmt),
1215 gimple_assign_rhs3_ptr (stmt));
1216 }
1217 }
1218 }
1219 }
1220
1221 /* Free stmt_vec_info. */
1222 free_stmt_vec_info (stmt);
1223 gsi_next (&si);
1224 }
1225 }
1226
1227 free (bbs);
1228
1229 loop->aux = NULL;
1230}
1231
1232
1233/* Calculate the cost of one scalar iteration of the loop. */
1234static void
1235vect_compute_single_scalar_iteration_cost (loop_vec_info loop_vinfo)
1236{
1237 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1238 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1239 int nbbs = loop->num_nodes, factor, scalar_single_iter_cost = 0;
1240 int innerloop_iters, i;
1241
1242 /* Count statements in scalar loop. Using this as scalar cost for a single
1243 iteration for now.
1244
1245 TODO: Add outer loop support.
1246
1247 TODO: Consider assigning different costs to different scalar
1248 statements. */
1249
1250 /* FORNOW. */
1251 innerloop_iters = 1;
1252 if (loop->inner)
1253 innerloop_iters = 50; /* FIXME */
1254
1255 for (i = 0; i < nbbs; i++)
1256 {
1257 gimple_stmt_iterator si;
1258 basic_block bb = bbs[i];
1259
1260 if (bb->loop_father == loop->inner)
1261 factor = innerloop_iters;
1262 else
1263 factor = 1;
1264
1265 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1266 {
1267 gimple *stmt = gsi_stmt (si);
1268 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1269
1270 if (!is_gimple_assign (stmt) && !is_gimple_call (stmt))
1271 continue;
1272
1273 /* Skip stmts that are not vectorized inside the loop. */
1274 if (stmt_info
1275 && !STMT_VINFO_RELEVANT_P (stmt_info)
1276 && (!STMT_VINFO_LIVE_P (stmt_info)
1277 || !VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info)))
1278 && !STMT_VINFO_IN_PATTERN_P (stmt_info))
1279 continue;
1280
1281 vect_cost_for_stmt kind;
1282 if (STMT_VINFO_DATA_REF (stmt_info))
1283 {
1284 if (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info)))
1285 kind = scalar_load;
1286 else
1287 kind = scalar_store;
1288 }
1289 else
1290 kind = scalar_stmt;
1291
1292 scalar_single_iter_cost
1293 += record_stmt_cost (&LOOP_VINFO_SCALAR_ITERATION_COST (loop_vinfo),
1294 factor, kind, stmt_info, 0, vect_prologue);
1295 }
1296 }
1297 LOOP_VINFO_SINGLE_SCALAR_ITERATION_COST (loop_vinfo)
1298 = scalar_single_iter_cost;
1299}
1300
1301
1302/* Function vect_analyze_loop_form_1.
1303
1304 Verify that certain CFG restrictions hold, including:
1305 - the loop has a pre-header
1306 - the loop has a single entry and exit
1307 - the loop exit condition is simple enough
1308 - the number of iterations can be analyzed, i.e, a countable loop. The
1309 niter could be analyzed under some assumptions. */
1310
1311bool
1312vect_analyze_loop_form_1 (struct loop *loop, gcond **loop_cond,
1313 tree *assumptions, tree *number_of_iterationsm1,
1314 tree *number_of_iterations, gcond **inner_loop_cond)
1315{
1316 if (dump_enabled_p ())
1317 dump_printf_loc (MSG_NOTE, vect_location,
1318 "=== vect_analyze_loop_form ===\n");
1319
1320 /* Different restrictions apply when we are considering an inner-most loop,
1321 vs. an outer (nested) loop.
1322 (FORNOW. May want to relax some of these restrictions in the future). */
1323
1324 if (!loop->inner)
1325 {
1326 /* Inner-most loop. We currently require that the number of BBs is
1327 exactly 2 (the header and latch). Vectorizable inner-most loops
1328 look like this:
1329
1330 (pre-header)
1331 |
1332 header <--------+
1333 | | |
1334 | +--> latch --+
1335 |
1336 (exit-bb) */
1337
1338 if (loop->num_nodes != 2)
1339 {
1340 if (dump_enabled_p ())
1341 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1342 "not vectorized: control flow in loop.\n");
1343 return false;
1344 }
1345
1346 if (empty_block_p (loop->header))
1347 {
1348 if (dump_enabled_p ())
1349 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1350 "not vectorized: empty loop.\n");
1351 return false;
1352 }
1353 }
1354 else
1355 {
1356 struct loop *innerloop = loop->inner;
1357 edge entryedge;
1358
1359 /* Nested loop. We currently require that the loop is doubly-nested,
1360 contains a single inner loop, and the number of BBs is exactly 5.
1361 Vectorizable outer-loops look like this:
1362
1363 (pre-header)
1364 |
1365 header <---+
1366 | |
1367 inner-loop |
1368 | |
1369 tail ------+
1370 |
1371 (exit-bb)
1372
1373 The inner-loop has the properties expected of inner-most loops
1374 as described above. */
1375
1376 if ((loop->inner)->inner || (loop->inner)->next)
1377 {
1378 if (dump_enabled_p ())
1379 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1380 "not vectorized: multiple nested loops.\n");
1381 return false;
1382 }
1383
1384 if (loop->num_nodes != 5)
1385 {
1386 if (dump_enabled_p ())
1387 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1388 "not vectorized: control flow in loop.\n");
1389 return false;
1390 }
1391
1392 entryedge = loop_preheader_edge (innerloop);
1393 if (entryedge->src != loop->header
1394 || !single_exit (innerloop)
1395 || single_exit (innerloop)->dest != EDGE_PRED (loop->latch, 0)->src)
1396 {
1397 if (dump_enabled_p ())
1398 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1399 "not vectorized: unsupported outerloop form.\n");
1400 return false;
1401 }
1402
1403 /* Analyze the inner-loop. */
1404 tree inner_niterm1, inner_niter, inner_assumptions;
1405 if (! vect_analyze_loop_form_1 (loop->inner, inner_loop_cond,
1406 &inner_assumptions, &inner_niterm1,
1407 &inner_niter, NULL)
1408 /* Don't support analyzing niter under assumptions for inner
1409 loop. */
1410 || !integer_onep (inner_assumptions))
1411 {
1412 if (dump_enabled_p ())
1413 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1414 "not vectorized: Bad inner loop.\n");
1415 return false;
1416 }
1417
1418 if (!expr_invariant_in_loop_p (loop, inner_niter))
1419 {
1420 if (dump_enabled_p ())
1421 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1422 "not vectorized: inner-loop count not"
1423 " invariant.\n");
1424 return false;
1425 }
1426
1427 if (dump_enabled_p ())
1428 dump_printf_loc (MSG_NOTE, vect_location,
1429 "Considering outer-loop vectorization.\n");
1430 }
1431
1432 if (!single_exit (loop)
1433 || EDGE_COUNT (loop->header->preds) != 2)
1434 {
1435 if (dump_enabled_p ())
1436 {
1437 if (!single_exit (loop))
1438 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1439 "not vectorized: multiple exits.\n");
1440 else if (EDGE_COUNT (loop->header->preds) != 2)
1441 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1442 "not vectorized: too many incoming edges.\n");
1443 }
1444 return false;
1445 }
1446
1447 /* We assume that the loop exit condition is at the end of the loop. i.e,
1448 that the loop is represented as a do-while (with a proper if-guard
1449 before the loop if needed), where the loop header contains all the
1450 executable statements, and the latch is empty. */
1451 if (!empty_block_p (loop->latch)
1452 || !gimple_seq_empty_p (phi_nodes (loop->latch)))
1453 {
1454 if (dump_enabled_p ())
1455 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1456 "not vectorized: latch block not empty.\n");
1457 return false;
1458 }
1459
1460 /* Make sure the exit is not abnormal. */
1461 edge e = single_exit (loop);
1462 if (e->flags & EDGE_ABNORMAL)
1463 {
1464 if (dump_enabled_p ())
1465 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1466 "not vectorized: abnormal loop exit edge.\n");
1467 return false;
1468 }
1469
1470 *loop_cond = vect_get_loop_niters (loop, assumptions, number_of_iterations,
1471 number_of_iterationsm1);
1472 if (!*loop_cond)
1473 {
1474 if (dump_enabled_p ())
1475 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1476 "not vectorized: complicated exit condition.\n");
1477 return false;
1478 }
1479
1480 if (integer_zerop (*assumptions)
1481 || !*number_of_iterations
1482 || chrec_contains_undetermined (*number_of_iterations))
1483 {
1484 if (dump_enabled_p ())
1485 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1486 "not vectorized: number of iterations cannot be "
1487 "computed.\n");
1488 return false;
1489 }
1490
1491 if (integer_zerop (*number_of_iterations))
1492 {
1493 if (dump_enabled_p ())
1494 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1495 "not vectorized: number of iterations = 0.\n");
1496 return false;
1497 }
1498
1499 return true;
1500}
1501
1502/* Analyze LOOP form and return a loop_vec_info if it is of suitable form. */
1503
1504loop_vec_info
1505vect_analyze_loop_form (struct loop *loop)
1506{
1507 tree assumptions, number_of_iterations, number_of_iterationsm1;
1508 gcond *loop_cond, *inner_loop_cond = NULL;
1509
1510 if (! vect_analyze_loop_form_1 (loop, &loop_cond,
1511 &assumptions, &number_of_iterationsm1,
1512 &number_of_iterations, &inner_loop_cond))
1513 return NULL;
1514
1515 loop_vec_info loop_vinfo = new _loop_vec_info (loop);
1516 LOOP_VINFO_NITERSM1 (loop_vinfo) = number_of_iterationsm1;
1517 LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
1518 LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo) = number_of_iterations;
1519 if (!integer_onep (assumptions))
1520 {
1521 /* We consider to vectorize this loop by versioning it under
1522 some assumptions. In order to do this, we need to clear
1523 existing information computed by scev and niter analyzer. */
1524 scev_reset_htab ();
1525 free_numbers_of_iterations_estimates (loop);
1526 /* Also set flag for this loop so that following scev and niter
1527 analysis are done under the assumptions. */
1528 loop_constraint_set (loop, LOOP_C_FINITE);
1529 /* Also record the assumptions for versioning. */
1530 LOOP_VINFO_NITERS_ASSUMPTIONS (loop_vinfo) = assumptions;
1531 }
1532
1533 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
1534 {
1535 if (dump_enabled_p ())
1536 {
1537 dump_printf_loc (MSG_NOTE, vect_location,
1538 "Symbolic number of iterations is ");
1539 dump_generic_expr (MSG_NOTE, TDF_DETAILS, number_of_iterations);
1540 dump_printf (MSG_NOTE, "\n");
1541 }
1542 }
1543
1544 STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond)) = loop_exit_ctrl_vec_info_type;
1545 if (inner_loop_cond)
1546 STMT_VINFO_TYPE (vinfo_for_stmt (inner_loop_cond))
1547 = loop_exit_ctrl_vec_info_type;
1548
1549 gcc_assert (!loop->aux);
1550 loop->aux = loop_vinfo;
1551 return loop_vinfo;
1552}
1553
1554
1555
1556/* Scan the loop stmts and dependent on whether there are any (non-)SLP
1557 statements update the vectorization factor. */
1558
1559static void
1560vect_update_vf_for_slp (loop_vec_info loop_vinfo)
1561{
1562 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1563 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1564 int nbbs = loop->num_nodes;
1565 unsigned int vectorization_factor;
1566 int i;
1567
1568 if (dump_enabled_p ())
1569 dump_printf_loc (MSG_NOTE, vect_location,
1570 "=== vect_update_vf_for_slp ===\n");
1571
1572 vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1573 gcc_assert (vectorization_factor != 0);
1574
1575 /* If all the stmts in the loop can be SLPed, we perform only SLP, and
1576 vectorization factor of the loop is the unrolling factor required by
1577 the SLP instances. If that unrolling factor is 1, we say, that we
1578 perform pure SLP on loop - cross iteration parallelism is not
1579 exploited. */
1580 bool only_slp_in_loop = true;
1581 for (i = 0; i < nbbs; i++)
1582 {
1583 basic_block bb = bbs[i];
1584 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
1585 gsi_next (&si))
1586 {
1587 gimple *stmt = gsi_stmt (si);
1588 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1589 if (STMT_VINFO_IN_PATTERN_P (stmt_info)
1590 && STMT_VINFO_RELATED_STMT (stmt_info))
1591 {
1592 stmt = STMT_VINFO_RELATED_STMT (stmt_info);
1593 stmt_info = vinfo_for_stmt (stmt);
1594 }
1595 if ((STMT_VINFO_RELEVANT_P (stmt_info)
1596 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info)))
1597 && !PURE_SLP_STMT (stmt_info))
1598 /* STMT needs both SLP and loop-based vectorization. */
1599 only_slp_in_loop = false;
1600 }
1601 }
1602
1603 if (only_slp_in_loop)
1604 {
1605 dump_printf_loc (MSG_NOTE, vect_location,
1606 "Loop contains only SLP stmts\n");
1607 vectorization_factor = LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo);
1608 }
1609 else
1610 {
1611 dump_printf_loc (MSG_NOTE, vect_location,
1612 "Loop contains SLP and non-SLP stmts\n");
1613 vectorization_factor
1614 = least_common_multiple (vectorization_factor,
1615 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo));
1616 }
1617
1618 LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
1619 if (dump_enabled_p ())
1620 dump_printf_loc (MSG_NOTE, vect_location,
1621 "Updating vectorization factor to %d\n",
1622 vectorization_factor);
1623}
1624
1625/* Function vect_analyze_loop_operations.
1626
1627 Scan the loop stmts and make sure they are all vectorizable. */
1628
1629static bool
1630vect_analyze_loop_operations (loop_vec_info loop_vinfo)
1631{
1632 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1633 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1634 int nbbs = loop->num_nodes;
1635 int i;
1636 stmt_vec_info stmt_info;
1637 bool need_to_vectorize = false;
1638 bool ok;
1639
1640 if (dump_enabled_p ())
1641 dump_printf_loc (MSG_NOTE, vect_location,
1642 "=== vect_analyze_loop_operations ===\n");
1643
1644 for (i = 0; i < nbbs; i++)
1645 {
1646 basic_block bb = bbs[i];
1647
1648 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
1649 gsi_next (&si))
1650 {
1651 gphi *phi = si.phi ();
1652 ok = true;
1653
1654 stmt_info = vinfo_for_stmt (phi);
1655 if (dump_enabled_p ())
1656 {
1657 dump_printf_loc (MSG_NOTE, vect_location, "examining phi: ");
1658 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
1659 }
1660 if (virtual_operand_p (gimple_phi_result (phi)))
1661 continue;
1662
1663 /* Inner-loop loop-closed exit phi in outer-loop vectorization
1664 (i.e., a phi in the tail of the outer-loop). */
1665 if (! is_loop_header_bb_p (bb))
1666 {
1667 /* FORNOW: we currently don't support the case that these phis
1668 are not used in the outerloop (unless it is double reduction,
1669 i.e., this phi is vect_reduction_def), cause this case
1670 requires to actually do something here. */
1671 if (STMT_VINFO_LIVE_P (stmt_info)
1672 && STMT_VINFO_DEF_TYPE (stmt_info)
1673 != vect_double_reduction_def)
1674 {
1675 if (dump_enabled_p ())
1676 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1677 "Unsupported loop-closed phi in "
1678 "outer-loop.\n");
1679 return false;
1680 }
1681
1682 /* If PHI is used in the outer loop, we check that its operand
1683 is defined in the inner loop. */
1684 if (STMT_VINFO_RELEVANT_P (stmt_info))
1685 {
1686 tree phi_op;
1687 gimple *op_def_stmt;
1688
1689 if (gimple_phi_num_args (phi) != 1)
1690 return false;
1691
1692 phi_op = PHI_ARG_DEF (phi, 0);
1693 if (TREE_CODE (phi_op) != SSA_NAME)
1694 return false;
1695
1696 op_def_stmt = SSA_NAME_DEF_STMT (phi_op);
1697 if (gimple_nop_p (op_def_stmt)
1698 || !flow_bb_inside_loop_p (loop, gimple_bb (op_def_stmt))
1699 || !vinfo_for_stmt (op_def_stmt))
1700 return false;
1701
1702 if (STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt))
1703 != vect_used_in_outer
1704 && STMT_VINFO_RELEVANT (vinfo_for_stmt (op_def_stmt))
1705 != vect_used_in_outer_by_reduction)
1706 return false;
1707 }
1708
1709 continue;
1710 }
1711
1712 gcc_assert (stmt_info);
1713
1714 if ((STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_scope
1715 || STMT_VINFO_LIVE_P (stmt_info))
1716 && STMT_VINFO_DEF_TYPE (stmt_info) != vect_induction_def)
1717 {
1718 /* A scalar-dependence cycle that we don't support. */
1719 if (dump_enabled_p ())
1720 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1721 "not vectorized: scalar dependence cycle.\n");
1722 return false;
1723 }
1724
1725 if (STMT_VINFO_RELEVANT_P (stmt_info))
1726 {
1727 need_to_vectorize = true;
1728 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def
1729 && ! PURE_SLP_STMT (stmt_info))
1730 ok = vectorizable_induction (phi, NULL, NULL, NULL);
1731 else if ((STMT_VINFO_DEF_TYPE (stmt_info) == vect_reduction_def
1732 || STMT_VINFO_DEF_TYPE (stmt_info) == vect_nested_cycle)
1733 && ! PURE_SLP_STMT (stmt_info))
1734 ok = vectorizable_reduction (phi, NULL, NULL, NULL, NULL);
1735 }
1736
1737 if (ok && STMT_VINFO_LIVE_P (stmt_info))
1738 ok = vectorizable_live_operation (phi, NULL, NULL, -1, NULL);
1739
1740 if (!ok)
1741 {
1742 if (dump_enabled_p ())
1743 {
1744 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1745 "not vectorized: relevant phi not "
1746 "supported: ");
1747 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, phi, 0);
1748 }
1749 return false;
1750 }
1751 }
1752
1753 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
1754 gsi_next (&si))
1755 {
1756 gimple *stmt = gsi_stmt (si);
1757 if (!gimple_clobber_p (stmt)
1758 && !vect_analyze_stmt (stmt, &need_to_vectorize, NULL, NULL))
1759 return false;
1760 }
1761 } /* bbs */
1762
1763 /* All operations in the loop are either irrelevant (deal with loop
1764 control, or dead), or only used outside the loop and can be moved
1765 out of the loop (e.g. invariants, inductions). The loop can be
1766 optimized away by scalar optimizations. We're better off not
1767 touching this loop. */
1768 if (!need_to_vectorize)
1769 {
1770 if (dump_enabled_p ())
1771 dump_printf_loc (MSG_NOTE, vect_location,
1772 "All the computation can be taken out of the loop.\n");
1773 if (dump_enabled_p ())
1774 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1775 "not vectorized: redundant loop. no profit to "
1776 "vectorize.\n");
1777 return false;
1778 }
1779
1780 return true;
1781}
1782
1783
1784/* Function vect_analyze_loop_2.
1785
1786 Apply a set of analyses on LOOP, and create a loop_vec_info struct
1787 for it. The different analyses will record information in the
1788 loop_vec_info struct. */
1789static bool
1790vect_analyze_loop_2 (loop_vec_info loop_vinfo, bool &fatal)
1791{
1792 bool ok;
1793 int max_vf = MAX_VECTORIZATION_FACTOR;
1794 int min_vf = 2;
1795 unsigned int n_stmts = 0;
1796
1797 /* The first group of checks is independent of the vector size. */
1798 fatal = true;
1799
1800 /* Find all data references in the loop (which correspond to vdefs/vuses)
1801 and analyze their evolution in the loop. */
1802
1803 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1804
1805 loop_p loop = LOOP_VINFO_LOOP (loop_vinfo);
1806 if (!find_loop_nest (loop, &LOOP_VINFO_LOOP_NEST (loop_vinfo)))
1807 {
1808 if (dump_enabled_p ())
1809 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1810 "not vectorized: loop nest containing two "
1811 "or more consecutive inner loops cannot be "
1812 "vectorized\n");
1813 return false;
1814 }
1815
1816 for (unsigned i = 0; i < loop->num_nodes; i++)
1817 for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]);
1818 !gsi_end_p (gsi); gsi_next (&gsi))
1819 {
1820 gimple *stmt = gsi_stmt (gsi);
1821 if (is_gimple_debug (stmt))
1822 continue;
1823 ++n_stmts;
1824 if (!find_data_references_in_stmt (loop, stmt,
1825 &LOOP_VINFO_DATAREFS (loop_vinfo)))
1826 {
1827 if (is_gimple_call (stmt) && loop->safelen)
1828 {
1829 tree fndecl = gimple_call_fndecl (stmt), op;
1830 if (fndecl != NULL_TREE)
1831 {
1832 cgraph_node *node = cgraph_node::get (fndecl);
1833 if (node != NULL && node->simd_clones != NULL)
1834 {
1835 unsigned int j, n = gimple_call_num_args (stmt);
1836 for (j = 0; j < n; j++)
1837 {
1838 op = gimple_call_arg (stmt, j);
1839 if (DECL_P (op)
1840 || (REFERENCE_CLASS_P (op)
1841 && get_base_address (op)))
1842 break;
1843 }
1844 op = gimple_call_lhs (stmt);
1845 /* Ignore #pragma omp declare simd functions
1846 if they don't have data references in the
1847 call stmt itself. */
1848 if (j == n
1849 && !(op
1850 && (DECL_P (op)
1851 || (REFERENCE_CLASS_P (op)
1852 && get_base_address (op)))))
1853 continue;
1854 }
1855 }
1856 }
1857 if (dump_enabled_p ())
1858 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1859 "not vectorized: loop contains function "
1860 "calls or data references that cannot "
1861 "be analyzed\n");
1862 return false;
1863 }
1864 }
1865
1866 /* Analyze the data references and also adjust the minimal
1867 vectorization factor according to the loads and stores. */
1868
1869 ok = vect_analyze_data_refs (loop_vinfo, &min_vf);
1870 if (!ok)
1871 {
1872 if (dump_enabled_p ())
1873 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1874 "bad data references.\n");
1875 return false;
1876 }
1877
1878 /* Classify all cross-iteration scalar data-flow cycles.
1879 Cross-iteration cycles caused by virtual phis are analyzed separately. */
1880 vect_analyze_scalar_cycles (loop_vinfo);
1881
1882 vect_pattern_recog (loop_vinfo);
1883
1884 vect_fixup_scalar_cycles_with_patterns (loop_vinfo);
1885
1886 /* Analyze the access patterns of the data-refs in the loop (consecutive,
1887 complex, etc.). FORNOW: Only handle consecutive access pattern. */
1888
1889 ok = vect_analyze_data_ref_accesses (loop_vinfo);
1890 if (!ok)
1891 {
1892 if (dump_enabled_p ())
1893 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1894 "bad data access.\n");
1895 return false;
1896 }
1897
1898 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
1899
1900 ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
1901 if (!ok)
1902 {
1903 if (dump_enabled_p ())
1904 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1905 "unexpected pattern.\n");
1906 return false;
1907 }
1908
1909 /* While the rest of the analysis below depends on it in some way. */
1910 fatal = false;
1911
1912 /* Analyze data dependences between the data-refs in the loop
1913 and adjust the maximum vectorization factor according to
1914 the dependences.
1915 FORNOW: fail at the first data dependence that we encounter. */
1916
1917 ok = vect_analyze_data_ref_dependences (loop_vinfo, &max_vf);
1918 if (!ok
1919 || max_vf < min_vf)
1920 {
1921 if (dump_enabled_p ())
1922 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1923 "bad data dependence.\n");
1924 return false;
1925 }
1926 LOOP_VINFO_MAX_VECT_FACTOR (loop_vinfo) = max_vf;
1927
1928 ok = vect_determine_vectorization_factor (loop_vinfo);
1929 if (!ok)
1930 {
1931 if (dump_enabled_p ())
1932 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1933 "can't determine vectorization factor.\n");
1934 return false;
1935 }
1936 if (max_vf < LOOP_VINFO_VECT_FACTOR (loop_vinfo))
1937 {
1938 if (dump_enabled_p ())
1939 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1940 "bad data dependence.\n");
1941 return false;
1942 }
1943
1944 /* Compute the scalar iteration cost. */
1945 vect_compute_single_scalar_iteration_cost (loop_vinfo);
1946
1947 int saved_vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1948 HOST_WIDE_INT estimated_niter;
1949 unsigned th;
1950 int min_scalar_loop_bound;
1951
1952 /* Check the SLP opportunities in the loop, analyze and build SLP trees. */
1953 ok = vect_analyze_slp (loop_vinfo, n_stmts);
1954 if (!ok)
1955 return false;
1956
1957 /* If there are any SLP instances mark them as pure_slp. */
1958 bool slp = vect_make_slp_decision (loop_vinfo);
1959 if (slp)
1960 {
1961 /* Find stmts that need to be both vectorized and SLPed. */
1962 vect_detect_hybrid_slp (loop_vinfo);
1963
1964 /* Update the vectorization factor based on the SLP decision. */
1965 vect_update_vf_for_slp (loop_vinfo);
1966 }
1967
1968 /* This is the point where we can re-start analysis with SLP forced off. */
1969start_over:
1970
1971 /* Now the vectorization factor is final. */
1972 unsigned vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1973 gcc_assert (vectorization_factor != 0);
1974
1975 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo) && dump_enabled_p ())
1976 dump_printf_loc (MSG_NOTE, vect_location,
1977 "vectorization_factor = %d, niters = "
1978 HOST_WIDE_INT_PRINT_DEC "\n", vectorization_factor,
1979 LOOP_VINFO_INT_NITERS (loop_vinfo));
1980
1981 HOST_WIDE_INT max_niter
1982 = likely_max_stmt_executions_int (LOOP_VINFO_LOOP (loop_vinfo));
1983 if ((LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1984 && (LOOP_VINFO_INT_NITERS (loop_vinfo) < vectorization_factor))
1985 || (max_niter != -1
1986 && (unsigned HOST_WIDE_INT) max_niter < vectorization_factor))
1987 {
1988 if (dump_enabled_p ())
1989 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1990 "not vectorized: iteration count smaller than "
1991 "vectorization factor.\n");
1992 return false;
1993 }
1994
1995 /* Analyze the alignment of the data-refs in the loop.
1996 Fail if a data reference is found that cannot be vectorized. */
1997
1998 ok = vect_analyze_data_refs_alignment (loop_vinfo);
1999 if (!ok)
2000 {
2001 if (dump_enabled_p ())
2002 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2003 "bad data alignment.\n");
2004 return false;
2005 }
2006
2007 /* Prune the list of ddrs to be tested at run-time by versioning for alias.
2008 It is important to call pruning after vect_analyze_data_ref_accesses,
2009 since we use grouping information gathered by interleaving analysis. */
2010 ok = vect_prune_runtime_alias_test_list (loop_vinfo);
2011 if (!ok)
2012 return false;
2013
2014 /* Do not invoke vect_enhance_data_refs_alignment for eplilogue
2015 vectorization. */
2016 if (!LOOP_VINFO_EPILOGUE_P (loop_vinfo))
2017 {
2018 /* This pass will decide on using loop versioning and/or loop peeling in
2019 order to enhance the alignment of data references in the loop. */
2020 ok = vect_enhance_data_refs_alignment (loop_vinfo);
2021 if (!ok)
2022 {
2023 if (dump_enabled_p ())
2024 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2025 "bad data alignment.\n");
2026 return false;
2027 }
2028 }
2029
2030 if (slp)
2031 {
2032 /* Analyze operations in the SLP instances. Note this may
2033 remove unsupported SLP instances which makes the above
2034 SLP kind detection invalid. */
2035 unsigned old_size = LOOP_VINFO_SLP_INSTANCES (loop_vinfo).length ();
2036 vect_slp_analyze_operations (loop_vinfo);
2037 if (LOOP_VINFO_SLP_INSTANCES (loop_vinfo).length () != old_size)
2038 goto again;
2039 }
2040
2041 /* Scan all the remaining operations in the loop that are not subject
2042 to SLP and make sure they are vectorizable. */
2043 ok = vect_analyze_loop_operations (loop_vinfo);
2044 if (!ok)
2045 {
2046 if (dump_enabled_p ())
2047 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2048 "bad operation or unsupported loop bound.\n");
2049 return false;
2050 }
2051
2052 /* If epilog loop is required because of data accesses with gaps,
2053 one additional iteration needs to be peeled. Check if there is
2054 enough iterations for vectorization. */
2055 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo)
2056 && LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
2057 {
2058 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2059 tree scalar_niters = LOOP_VINFO_NITERSM1 (loop_vinfo);
2060
2061 if (wi::to_widest (scalar_niters) < vf)
2062 {
2063 if (dump_enabled_p ())
2064 dump_printf_loc (MSG_NOTE, vect_location,
2065 "loop has no enough iterations to support"
2066 " peeling for gaps.\n");
2067 return false;
2068 }
2069 }
2070
2071 /* Analyze cost. Decide if worth while to vectorize. */
2072 int min_profitable_estimate, min_profitable_iters;
2073 vect_estimate_min_profitable_iters (loop_vinfo, &min_profitable_iters,
2074 &min_profitable_estimate);
2075
2076 if (min_profitable_iters < 0)
2077 {
2078 if (dump_enabled_p ())
2079 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2080 "not vectorized: vectorization not profitable.\n");
2081 if (dump_enabled_p ())
2082 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2083 "not vectorized: vector version will never be "
2084 "profitable.\n");
2085 goto again;
2086 }
2087
2088 min_scalar_loop_bound = (PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND)
2089 * vectorization_factor);
2090
2091 /* Use the cost model only if it is more conservative than user specified
2092 threshold. */
2093 th = (unsigned) MAX (min_scalar_loop_bound, min_profitable_iters);
2094
2095 LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo) = th;
2096
2097 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
2098 && LOOP_VINFO_INT_NITERS (loop_vinfo) < th)
2099 {
2100 if (dump_enabled_p ())
2101 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2102 "not vectorized: vectorization not profitable.\n");
2103 if (dump_enabled_p ())
2104 dump_printf_loc (MSG_NOTE, vect_location,
2105 "not vectorized: iteration count smaller than user "
2106 "specified loop bound parameter or minimum profitable "
2107 "iterations (whichever is more conservative).\n");
2108 goto again;
2109 }
2110
2111 estimated_niter
2112 = estimated_stmt_executions_int (LOOP_VINFO_LOOP (loop_vinfo));
2113 if (estimated_niter == -1)
2114 estimated_niter = max_niter;
2115 if (estimated_niter != -1
2116 && ((unsigned HOST_WIDE_INT) estimated_niter
2117 < MAX (th, (unsigned) min_profitable_estimate)))
2118 {
2119 if (dump_enabled_p ())
2120 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2121 "not vectorized: estimated iteration count too "
2122 "small.\n");
2123 if (dump_enabled_p ())
2124 dump_printf_loc (MSG_NOTE, vect_location,
2125 "not vectorized: estimated iteration count smaller "
2126 "than specified loop bound parameter or minimum "
2127 "profitable iterations (whichever is more "
2128 "conservative).\n");
2129 goto again;
2130 }
2131
2132 /* Decide whether we need to create an epilogue loop to handle
2133 remaining scalar iterations. */
2134 th = ((LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo)
2135 / LOOP_VINFO_VECT_FACTOR (loop_vinfo))
2136 * LOOP_VINFO_VECT_FACTOR (loop_vinfo));
2137
2138 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
2139 && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) > 0)
2140 {
2141 if (ctz_hwi (LOOP_VINFO_INT_NITERS (loop_vinfo)
2142 - LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo))
2143 < exact_log2 (LOOP_VINFO_VECT_FACTOR (loop_vinfo)))
2144 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo) = true;
2145 }
2146 else if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo)
2147 || (tree_ctz (LOOP_VINFO_NITERS (loop_vinfo))
2148 < (unsigned)exact_log2 (LOOP_VINFO_VECT_FACTOR (loop_vinfo))
2149 /* In case of versioning, check if the maximum number of
2150 iterations is greater than th. If they are identical,
2151 the epilogue is unnecessary. */
2152 && (!LOOP_REQUIRES_VERSIONING (loop_vinfo)
2153 || (unsigned HOST_WIDE_INT) max_niter > th)))
2154 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo) = true;
2155
2156 /* If an epilogue loop is required make sure we can create one. */
2157 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo)
2158 || LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo))
2159 {
2160 if (dump_enabled_p ())
2161 dump_printf_loc (MSG_NOTE, vect_location, "epilog loop required\n");
2162 if (!vect_can_advance_ivs_p (loop_vinfo)
2163 || !slpeel_can_duplicate_loop_p (LOOP_VINFO_LOOP (loop_vinfo),
2164 single_exit (LOOP_VINFO_LOOP
2165 (loop_vinfo))))
2166 {
2167 if (dump_enabled_p ())
2168 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2169 "not vectorized: can't create required "
2170 "epilog loop\n");
2171 goto again;
2172 }
2173 }
2174
2175 /* During peeling, we need to check if number of loop iterations is
2176 enough for both peeled prolog loop and vector loop. This check
2177 can be merged along with threshold check of loop versioning, so
2178 increase threshold for this case if necessary. */
2179 if (LOOP_REQUIRES_VERSIONING (loop_vinfo)
2180 && (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo)
2181 || LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo)))
2182 {
2183 unsigned niters_th;
2184
2185 /* Niters for peeled prolog loop. */
2186 if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0)
2187 {
2188 struct data_reference *dr = LOOP_VINFO_UNALIGNED_DR (loop_vinfo);
2189 tree vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr)));
2190
2191 niters_th = TYPE_VECTOR_SUBPARTS (vectype) - 1;
2192 }
2193 else
2194 niters_th = LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo);
2195
2196 /* Niters for at least one iteration of vectorized loop. */
2197 niters_th += LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2198 /* One additional iteration because of peeling for gap. */
2199 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo))
2200 niters_th++;
2201 if (LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo) < niters_th)
2202 LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo) = niters_th;
2203 }
2204
2205 gcc_assert (vectorization_factor
2206 == (unsigned)LOOP_VINFO_VECT_FACTOR (loop_vinfo));
2207
2208 /* Ok to vectorize! */
2209 return true;
2210
2211again:
2212 /* Try again with SLP forced off but if we didn't do any SLP there is
2213 no point in re-trying. */
2214 if (!slp)
2215 return false;
2216
2217 /* If there are reduction chains re-trying will fail anyway. */
2218 if (! LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo).is_empty ())
2219 return false;
2220
2221 /* Likewise if the grouped loads or stores in the SLP cannot be handled
2222 via interleaving or lane instructions. */
2223 slp_instance instance;
2224 slp_tree node;
2225 unsigned i, j;
2226 FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (loop_vinfo), i, instance)
2227 {
2228 stmt_vec_info vinfo;
2229 vinfo = vinfo_for_stmt
2230 (SLP_TREE_SCALAR_STMTS (SLP_INSTANCE_TREE (instance))[0]);
2231 if (! STMT_VINFO_GROUPED_ACCESS (vinfo))
2232 continue;
2233 vinfo = vinfo_for_stmt (STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo));
2234 unsigned int size = STMT_VINFO_GROUP_SIZE (vinfo);
2235 tree vectype = STMT_VINFO_VECTYPE (vinfo);
2236 if (! vect_store_lanes_supported (vectype, size)
2237 && ! vect_grouped_store_supported (vectype, size))
2238 return false;
2239 FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (instance), j, node)
2240 {
2241 vinfo = vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (node)[0]);
2242 vinfo = vinfo_for_stmt (STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo));
2243 bool single_element_p = !STMT_VINFO_GROUP_NEXT_ELEMENT (vinfo);
2244 size = STMT_VINFO_GROUP_SIZE (vinfo);
2245 vectype = STMT_VINFO_VECTYPE (vinfo);
2246 if (! vect_load_lanes_supported (vectype, size)
2247 && ! vect_grouped_load_supported (vectype, single_element_p,
2248 size))
2249 return false;
2250 }
2251 }
2252
2253 if (dump_enabled_p ())
2254 dump_printf_loc (MSG_NOTE, vect_location,
2255 "re-trying with SLP disabled\n");
2256
2257 /* Roll back state appropriately. No SLP this time. */
2258 slp = false;
2259 /* Restore vectorization factor as it were without SLP. */
2260 LOOP_VINFO_VECT_FACTOR (loop_vinfo) = saved_vectorization_factor;
2261 /* Free the SLP instances. */
2262 FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (loop_vinfo), j, instance)
2263 vect_free_slp_instance (instance);
2264 LOOP_VINFO_SLP_INSTANCES (loop_vinfo).release ();
2265 /* Reset SLP type to loop_vect on all stmts. */
2266 for (i = 0; i < LOOP_VINFO_LOOP (loop_vinfo)->num_nodes; ++i)
2267 {
2268 basic_block bb = LOOP_VINFO_BBS (loop_vinfo)[i];
2269 for (gimple_stmt_iterator si = gsi_start_phis (bb);
2270 !gsi_end_p (si); gsi_next (&si))
2271 {
2272 stmt_vec_info stmt_info = vinfo_for_stmt (gsi_stmt (si));
2273 STMT_SLP_TYPE (stmt_info) = loop_vect;
2274 }
2275 for (gimple_stmt_iterator si = gsi_start_bb (bb);
2276 !gsi_end_p (si); gsi_next (&si))
2277 {
2278 stmt_vec_info stmt_info = vinfo_for_stmt (gsi_stmt (si));
2279 STMT_SLP_TYPE (stmt_info) = loop_vect;
2280 if (STMT_VINFO_IN_PATTERN_P (stmt_info))
2281 {
2282 stmt_info = vinfo_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info));
2283 STMT_SLP_TYPE (stmt_info) = loop_vect;
2284 for (gimple_stmt_iterator pi
2285 = gsi_start (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info));
2286 !gsi_end_p (pi); gsi_next (&pi))
2287 {
2288 gimple *pstmt = gsi_stmt (pi);
2289 STMT_SLP_TYPE (vinfo_for_stmt (pstmt)) = loop_vect;
2290 }
2291 }
2292 }
2293 }
2294 /* Free optimized alias test DDRS. */
2295 LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo).release ();
2296 LOOP_VINFO_CHECK_UNEQUAL_ADDRS (loop_vinfo).release ();
2297 /* Reset target cost data. */
2298 destroy_cost_data (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo));
2299 LOOP_VINFO_TARGET_COST_DATA (loop_vinfo)
2300 = init_cost (LOOP_VINFO_LOOP (loop_vinfo));
2301 /* Reset assorted flags. */
2302 LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo) = false;
2303 LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo) = false;
2304 LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo) = 0;
2305
2306 goto start_over;
2307}
2308
2309/* Function vect_analyze_loop.
2310
2311 Apply a set of analyses on LOOP, and create a loop_vec_info struct
2312 for it. The different analyses will record information in the
2313 loop_vec_info struct. If ORIG_LOOP_VINFO is not NULL epilogue must
2314 be vectorized. */
2315loop_vec_info
2316vect_analyze_loop (struct loop *loop, loop_vec_info orig_loop_vinfo)
2317{
2318 loop_vec_info loop_vinfo;
2319 unsigned int vector_sizes;
2320
2321 /* Autodetect first vector size we try. */
2322 current_vector_size = 0;
2323 vector_sizes = targetm.vectorize.autovectorize_vector_sizes ();
2324
2325 if (dump_enabled_p ())
2326 dump_printf_loc (MSG_NOTE, vect_location,
2327 "===== analyze_loop_nest =====\n");
2328
2329 if (loop_outer (loop)
2330 && loop_vec_info_for_loop (loop_outer (loop))
2331 && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop))))
2332 {
2333 if (dump_enabled_p ())
2334 dump_printf_loc (MSG_NOTE, vect_location,
2335 "outer-loop already vectorized.\n");
2336 return NULL;
2337 }
2338
2339 while (1)
2340 {
2341 /* Check the CFG characteristics of the loop (nesting, entry/exit). */
2342 loop_vinfo = vect_analyze_loop_form (loop);
2343 if (!loop_vinfo)
2344 {
2345 if (dump_enabled_p ())
2346 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2347 "bad loop form.\n");
2348 return NULL;
2349 }
2350
2351 bool fatal = false;
2352
2353 if (orig_loop_vinfo)
2354 LOOP_VINFO_ORIG_LOOP_INFO (loop_vinfo) = orig_loop_vinfo;
2355
2356 if (vect_analyze_loop_2 (loop_vinfo, fatal))
2357 {
2358 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1;
2359
2360 return loop_vinfo;
2361 }
2362
2363 delete loop_vinfo;
2364
2365 vector_sizes &= ~current_vector_size;
2366 if (fatal
2367 || vector_sizes == 0
2368 || current_vector_size == 0)
2369 return NULL;
2370
2371 /* Try the next biggest vector size. */
2372 current_vector_size = 1 << floor_log2 (vector_sizes);
2373 if (dump_enabled_p ())
2374 dump_printf_loc (MSG_NOTE, vect_location,
2375 "***** Re-trying analysis with "
2376 "vector size %d\n", current_vector_size);
2377 }
2378}
2379
2380
2381/* Function reduction_fn_for_scalar_code
2382
2383 Input:
2384 CODE - tree_code of a reduction operations.
2385
2386 Output:
2387 REDUC_FN - the corresponding internal function to be used to reduce the
2388 vector of partial results into a single scalar result, or IFN_LAST
2389 if the operation is a supported reduction operation, but does not have
2390 such an internal function.
2391
2392 Return FALSE if CODE currently cannot be vectorized as reduction. */
2393
2394static bool
2395reduction_fn_for_scalar_code (enum tree_code code, internal_fn *reduc_fn)
2396{
2397 switch (code)
2398 {
2399 case MAX_EXPR:
2400 *reduc_fn = IFN_REDUC_MAX;
2401 return true;
2402
2403 case MIN_EXPR:
2404 *reduc_fn = IFN_REDUC_MIN;
2405 return true;
2406
2407 case PLUS_EXPR:
2408 *reduc_fn = IFN_REDUC_PLUS;
2409 return true;
2410
2411 case MULT_EXPR:
2412 case MINUS_EXPR:
2413 case BIT_IOR_EXPR:
2414 case BIT_XOR_EXPR:
2415 case BIT_AND_EXPR:
2416 *reduc_fn = IFN_LAST;
2417 return true;
2418
2419 default:
2420 return false;
2421 }
2422}
2423
2424
2425/* Error reporting helper for vect_is_simple_reduction below. GIMPLE statement
2426 STMT is printed with a message MSG. */
2427
2428static void
2429report_vect_op (dump_flags_t msg_type, gimple *stmt, const char *msg)
2430{
2431 dump_printf_loc (msg_type, vect_location, "%s", msg);
2432 dump_gimple_stmt (msg_type, TDF_SLIM, stmt, 0);
2433}
2434
2435
2436/* Detect SLP reduction of the form:
2437
2438 #a1 = phi <a5, a0>
2439 a2 = operation (a1)
2440 a3 = operation (a2)
2441 a4 = operation (a3)
2442 a5 = operation (a4)
2443
2444 #a = phi <a5>
2445
2446 PHI is the reduction phi node (#a1 = phi <a5, a0> above)
2447 FIRST_STMT is the first reduction stmt in the chain
2448 (a2 = operation (a1)).
2449
2450 Return TRUE if a reduction chain was detected. */
2451
2452static bool
2453vect_is_slp_reduction (loop_vec_info loop_info, gimple *phi,
2454 gimple *first_stmt)
2455{
2456 struct loop *loop = (gimple_bb (phi))->loop_father;
2457 struct loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
2458 enum tree_code code;
2459 gimple *current_stmt = NULL, *loop_use_stmt = NULL, *first, *next_stmt;
2460 stmt_vec_info use_stmt_info, current_stmt_info;
2461 tree lhs;
2462 imm_use_iterator imm_iter;
2463 use_operand_p use_p;
2464 int nloop_uses, size = 0, n_out_of_loop_uses;
2465 bool found = false;
2466
2467 if (loop != vect_loop)
2468 return false;
2469
2470 lhs = PHI_RESULT (phi);
2471 code = gimple_assign_rhs_code (first_stmt);
2472 while (1)
2473 {
2474 nloop_uses = 0;
2475 n_out_of_loop_uses = 0;
2476 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
2477 {
2478 gimple *use_stmt = USE_STMT (use_p);
2479 if (is_gimple_debug (use_stmt))
2480 continue;
2481
2482 /* Check if we got back to the reduction phi. */
2483 if (use_stmt == phi)
2484 {
2485 loop_use_stmt = use_stmt;
2486 found = true;
2487 break;
2488 }
2489
2490 if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
2491 {
2492 loop_use_stmt = use_stmt;
2493 nloop_uses++;
2494 }
2495 else
2496 n_out_of_loop_uses++;
2497
2498 /* There are can be either a single use in the loop or two uses in
2499 phi nodes. */
2500 if (nloop_uses > 1 || (n_out_of_loop_uses && nloop_uses))
2501 return false;
2502 }
2503
2504 if (found)
2505 break;
2506
2507 /* We reached a statement with no loop uses. */
2508 if (nloop_uses == 0)
2509 return false;
2510
2511 /* This is a loop exit phi, and we haven't reached the reduction phi. */
2512 if (gimple_code (loop_use_stmt) == GIMPLE_PHI)
2513 return false;
2514
2515 if (!is_gimple_assign (loop_use_stmt)
2516 || code != gimple_assign_rhs_code (loop_use_stmt)
2517 || !flow_bb_inside_loop_p (loop, gimple_bb (loop_use_stmt)))
2518 return false;
2519
2520 /* Insert USE_STMT into reduction chain. */
2521 use_stmt_info = vinfo_for_stmt (loop_use_stmt);
2522 if (current_stmt)
2523 {
2524 current_stmt_info = vinfo_for_stmt (current_stmt);
2525 GROUP_NEXT_ELEMENT (current_stmt_info) = loop_use_stmt;
2526 GROUP_FIRST_ELEMENT (use_stmt_info)
2527 = GROUP_FIRST_ELEMENT (current_stmt_info);
2528 }
2529 else
2530 GROUP_FIRST_ELEMENT (use_stmt_info) = loop_use_stmt;
2531
2532 lhs = gimple_assign_lhs (loop_use_stmt);
2533 current_stmt = loop_use_stmt;
2534 size++;
2535 }
2536
2537 if (!found || loop_use_stmt != phi || size < 2)
2538 return false;
2539
2540 /* Swap the operands, if needed, to make the reduction operand be the second
2541 operand. */
2542 lhs = PHI_RESULT (phi);
2543 next_stmt = GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt));
2544 while (next_stmt)
2545 {
2546 if (gimple_assign_rhs2 (next_stmt) == lhs)
2547 {
2548 tree op = gimple_assign_rhs1 (next_stmt);
2549 gimple *def_stmt = NULL;
2550
2551 if (TREE_CODE (op) == SSA_NAME)
2552 def_stmt = SSA_NAME_DEF_STMT (op);
2553
2554 /* Check that the other def is either defined in the loop
2555 ("vect_internal_def"), or it's an induction (defined by a
2556 loop-header phi-node). */
2557 if (def_stmt
2558 && gimple_bb (def_stmt)
2559 && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
2560 && (is_gimple_assign (def_stmt)
2561 || is_gimple_call (def_stmt)
2562 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
2563 == vect_induction_def
2564 || (gimple_code (def_stmt) == GIMPLE_PHI
2565 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
2566 == vect_internal_def
2567 && !is_loop_header_bb_p (gimple_bb (def_stmt)))))
2568 {
2569 lhs = gimple_assign_lhs (next_stmt);
2570 next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
2571 continue;
2572 }
2573
2574 return false;
2575 }
2576 else
2577 {
2578 tree op = gimple_assign_rhs2 (next_stmt);
2579 gimple *def_stmt = NULL;
2580
2581 if (TREE_CODE (op) == SSA_NAME)
2582 def_stmt = SSA_NAME_DEF_STMT (op);
2583
2584 /* Check that the other def is either defined in the loop
2585 ("vect_internal_def"), or it's an induction (defined by a
2586 loop-header phi-node). */
2587 if (def_stmt
2588 && gimple_bb (def_stmt)
2589 && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
2590 && (is_gimple_assign (def_stmt)
2591 || is_gimple_call (def_stmt)
2592 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
2593 == vect_induction_def
2594 || (gimple_code (def_stmt) == GIMPLE_PHI
2595 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
2596 == vect_internal_def
2597 && !is_loop_header_bb_p (gimple_bb (def_stmt)))))
2598 {
2599 if (dump_enabled_p ())
2600 {
2601 dump_printf_loc (MSG_NOTE, vect_location, "swapping oprnds: ");
2602 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, next_stmt, 0);
2603 }
2604
2605 swap_ssa_operands (next_stmt,
2606 gimple_assign_rhs1_ptr (next_stmt),
2607 gimple_assign_rhs2_ptr (next_stmt));
2608 update_stmt (next_stmt);
2609
2610 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (next_stmt)))
2611 LOOP_VINFO_OPERANDS_SWAPPED (loop_info) = true;
2612 }
2613 else
2614 return false;
2615 }
2616
2617 lhs = gimple_assign_lhs (next_stmt);
2618 next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
2619 }
2620
2621 /* Save the chain for further analysis in SLP detection. */
2622 first = GROUP_FIRST_ELEMENT (vinfo_for_stmt (current_stmt));
2623 LOOP_VINFO_REDUCTION_CHAINS (loop_info).safe_push (first);
2624 GROUP_SIZE (vinfo_for_stmt (first)) = size;
2625
2626 return true;
2627}
2628
2629
2630/* Return true if the reduction PHI in LOOP with latch arg LOOP_ARG and
2631 reduction operation CODE has a handled computation expression. */
2632
2633bool
2634check_reduction_path (location_t loc, loop_p loop, gphi *phi, tree loop_arg,
2635 enum tree_code code)
2636{
2637 auto_vec<std::pair<ssa_op_iter, use_operand_p> > path;
2638 auto_bitmap visited;
2639 tree lookfor = PHI_RESULT (phi);
2640 ssa_op_iter curri;
2641 use_operand_p curr = op_iter_init_phiuse (&curri, phi, SSA_OP_USE);
2642 while (USE_FROM_PTR (curr) != loop_arg)
2643 curr = op_iter_next_use (&curri);
2644 curri.i = curri.numops;
2645 do
2646 {
2647 path.safe_push (std::make_pair (curri, curr));
2648 tree use = USE_FROM_PTR (curr);
2649 if (use == lookfor)
2650 break;
2651 gimple *def = SSA_NAME_DEF_STMT (use);
2652 if (gimple_nop_p (def)
2653 || ! flow_bb_inside_loop_p (loop, gimple_bb (def)))
2654 {
2655pop:
2656 do
2657 {
2658 std::pair<ssa_op_iter, use_operand_p> x = path.pop ();
2659 curri = x.first;
2660 curr = x.second;
2661 do
2662 curr = op_iter_next_use (&curri);
2663 /* Skip already visited or non-SSA operands (from iterating
2664 over PHI args). */
2665 while (curr != NULL_USE_OPERAND_P
2666 && (TREE_CODE (USE_FROM_PTR (curr)) != SSA_NAME
2667 || ! bitmap_set_bit (visited,
2668 SSA_NAME_VERSION
2669 (USE_FROM_PTR (curr)))));
2670 }
2671 while (curr == NULL_USE_OPERAND_P && ! path.is_empty ());
2672 if (curr == NULL_USE_OPERAND_P)
2673 break;
2674 }
2675 else
2676 {
2677 if (gimple_code (def) == GIMPLE_PHI)
2678 curr = op_iter_init_phiuse (&curri, as_a <gphi *>(def), SSA_OP_USE);
2679 else
2680 curr = op_iter_init_use (&curri, def, SSA_OP_USE);
2681 while (curr != NULL_USE_OPERAND_P
2682 && (TREE_CODE (USE_FROM_PTR (curr)) != SSA_NAME
2683 || ! bitmap_set_bit (visited,
2684 SSA_NAME_VERSION
2685 (USE_FROM_PTR (curr)))))
2686 curr = op_iter_next_use (&curri);
2687 if (curr == NULL_USE_OPERAND_P)
2688 goto pop;
2689 }
2690 }
2691 while (1);
2692 if (dump_file && (dump_flags & TDF_DETAILS))
2693 {
2694 dump_printf_loc (MSG_NOTE, loc, "reduction path: ");
2695 unsigned i;
2696 std::pair<ssa_op_iter, use_operand_p> *x;
2697 FOR_EACH_VEC_ELT (path, i, x)
2698 {
2699 dump_generic_expr (MSG_NOTE, TDF_SLIM, USE_FROM_PTR (x->second));
2700 dump_printf (MSG_NOTE, " ");
2701 }
2702 dump_printf (MSG_NOTE, "\n");
2703 }
2704
2705 /* Check whether the reduction path detected is valid. */
2706 bool fail = path.length () == 0;
2707 bool neg = false;
2708 for (unsigned i = 1; i < path.length (); ++i)
2709 {
2710 gimple *use_stmt = USE_STMT (path[i].second);
2711 tree op = USE_FROM_PTR (path[i].second);
2712 if (! has_single_use (op)
2713 || ! is_gimple_assign (use_stmt))
2714 {
2715 fail = true;
2716 break;
2717 }
2718 if (gimple_assign_rhs_code (use_stmt) != code)
2719 {
2720 if (code == PLUS_EXPR
2721 && gimple_assign_rhs_code (use_stmt) == MINUS_EXPR)
2722 {
2723 /* Track whether we negate the reduction value each iteration. */
2724 if (gimple_assign_rhs2 (use_stmt) == op)
2725 neg = ! neg;
2726 }
2727 else
2728 {
2729 fail = true;
2730 break;
2731 }
2732 }
2733 }
2734 return ! fail && ! neg;
2735}
2736
2737
2738/* Function vect_is_simple_reduction
2739
2740 (1) Detect a cross-iteration def-use cycle that represents a simple
2741 reduction computation. We look for the following pattern:
2742
2743 loop_header:
2744 a1 = phi < a0, a2 >
2745 a3 = ...
2746 a2 = operation (a3, a1)
2747
2748 or
2749
2750 a3 = ...
2751 loop_header:
2752 a1 = phi < a0, a2 >
2753 a2 = operation (a3, a1)
2754
2755 such that:
2756 1. operation is commutative and associative and it is safe to
2757 change the order of the computation
2758 2. no uses for a2 in the loop (a2 is used out of the loop)
2759 3. no uses of a1 in the loop besides the reduction operation
2760 4. no uses of a1 outside the loop.
2761
2762 Conditions 1,4 are tested here.
2763 Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
2764
2765 (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
2766 nested cycles.
2767
2768 (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
2769 reductions:
2770
2771 a1 = phi < a0, a2 >
2772 inner loop (def of a3)
2773 a2 = phi < a3 >
2774
2775 (4) Detect condition expressions, ie:
2776 for (int i = 0; i < N; i++)
2777 if (a[i] < val)
2778 ret_val = a[i];
2779
2780*/
2781
2782static gimple *
2783vect_is_simple_reduction (loop_vec_info loop_info, gimple *phi,
2784 bool *double_reduc,
2785 bool need_wrapping_integral_overflow,
2786 enum vect_reduction_type *v_reduc_type)
2787{
2788 struct loop *loop = (gimple_bb (phi))->loop_father;
2789 struct loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
2790 gimple *def_stmt, *def1 = NULL, *def2 = NULL, *phi_use_stmt = NULL;
2791 enum tree_code orig_code, code;
2792 tree op1, op2, op3 = NULL_TREE, op4 = NULL_TREE;
2793 tree type;
2794 int nloop_uses;
2795 tree name;
2796 imm_use_iterator imm_iter;
2797 use_operand_p use_p;
2798 bool phi_def;
2799
2800 *double_reduc = false;
2801 *v_reduc_type = TREE_CODE_REDUCTION;
2802
2803 tree phi_name = PHI_RESULT (phi);
2804 /* ??? If there are no uses of the PHI result the inner loop reduction
2805 won't be detected as possibly double-reduction by vectorizable_reduction
2806 because that tries to walk the PHI arg from the preheader edge which
2807 can be constant. See PR60382. */
2808 if (has_zero_uses (phi_name))
2809 return NULL;
2810 nloop_uses = 0;
2811 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, phi_name)
2812 {
2813 gimple *use_stmt = USE_STMT (use_p);
2814 if (is_gimple_debug (use_stmt))
2815 continue;
2816
2817 if (!flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
2818 {
2819 if (dump_enabled_p ())
2820 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2821 "intermediate value used outside loop.\n");
2822
2823 return NULL;
2824 }
2825
2826 nloop_uses++;
2827 if (nloop_uses > 1)
2828 {
2829 if (dump_enabled_p ())
2830 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2831 "reduction value used in loop.\n");
2832 return NULL;
2833 }
2834
2835 phi_use_stmt = use_stmt;
2836 }
2837
2838 edge latch_e = loop_latch_edge (loop);
2839 tree loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
2840 if (TREE_CODE (loop_arg) != SSA_NAME)
2841 {
2842 if (dump_enabled_p ())
2843 {
2844 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2845 "reduction: not ssa_name: ");
2846 dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, loop_arg);
2847 dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
2848 }
2849 return NULL;
2850 }
2851
2852 def_stmt = SSA_NAME_DEF_STMT (loop_arg);
2853 if (is_gimple_assign (def_stmt))
2854 {
2855 name = gimple_assign_lhs (def_stmt);
2856 phi_def = false;
2857 }
2858 else if (gimple_code (def_stmt) == GIMPLE_PHI)
2859 {
2860 name = PHI_RESULT (def_stmt);
2861 phi_def = true;
2862 }
2863 else
2864 {
2865 if (dump_enabled_p ())
2866 {
2867 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2868 "reduction: unhandled reduction operation: ");
2869 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, def_stmt, 0);
2870 }
2871 return NULL;
2872 }
2873
2874 if (! flow_bb_inside_loop_p (loop, gimple_bb (def_stmt)))
2875 return NULL;
2876
2877 nloop_uses = 0;
2878 auto_vec<gphi *, 3> lcphis;
2879 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
2880 {
2881 gimple *use_stmt = USE_STMT (use_p);
2882 if (is_gimple_debug (use_stmt))
2883 continue;
2884 if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
2885 nloop_uses++;
2886 else
2887 /* We can have more than one loop-closed PHI. */
2888 lcphis.safe_push (as_a <gphi *> (use_stmt));
2889 if (nloop_uses > 1)
2890 {
2891 if (dump_enabled_p ())
2892 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2893 "reduction used in loop.\n");
2894 return NULL;
2895 }
2896 }
2897
2898 /* If DEF_STMT is a phi node itself, we expect it to have a single argument
2899 defined in the inner loop. */
2900 if (phi_def)
2901 {
2902 op1 = PHI_ARG_DEF (def_stmt, 0);
2903
2904 if (gimple_phi_num_args (def_stmt) != 1
2905 || TREE_CODE (op1) != SSA_NAME)
2906 {
2907 if (dump_enabled_p ())
2908 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2909 "unsupported phi node definition.\n");
2910
2911 return NULL;
2912 }
2913
2914 def1 = SSA_NAME_DEF_STMT (op1);
2915 if (gimple_bb (def1)
2916 && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
2917 && loop->inner
2918 && flow_bb_inside_loop_p (loop->inner, gimple_bb (def1))
2919 && is_gimple_assign (def1)
2920 && flow_bb_inside_loop_p (loop->inner, gimple_bb (phi_use_stmt)))
2921 {
2922 if (dump_enabled_p ())
2923 report_vect_op (MSG_NOTE, def_stmt,
2924 "detected double reduction: ");
2925
2926 *double_reduc = true;
2927 return def_stmt;
2928 }
2929
2930 return NULL;
2931 }
2932
2933 /* If we are vectorizing an inner reduction we are executing that
2934 in the original order only in case we are not dealing with a
2935 double reduction. */
2936 bool check_reduction = true;
2937 if (flow_loop_nested_p (vect_loop, loop))
2938 {
2939 gphi *lcphi;
2940 unsigned i;
2941 check_reduction = false;
2942 FOR_EACH_VEC_ELT (lcphis, i, lcphi)
2943 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (lcphi))
2944 {
2945 gimple *use_stmt = USE_STMT (use_p);
2946 if (is_gimple_debug (use_stmt))
2947 continue;
2948 if (! flow_bb_inside_loop_p (vect_loop, gimple_bb (use_stmt)))
2949 check_reduction = true;
2950 }
2951 }
2952
2953 bool nested_in_vect_loop = flow_loop_nested_p (vect_loop, loop);
2954 code = orig_code = gimple_assign_rhs_code (def_stmt);
2955
2956 /* We can handle "res -= x[i]", which is non-associative by
2957 simply rewriting this into "res += -x[i]". Avoid changing
2958 gimple instruction for the first simple tests and only do this
2959 if we're allowed to change code at all. */
2960 if (code == MINUS_EXPR && gimple_assign_rhs2 (def_stmt) != phi_name)
2961 code = PLUS_EXPR;
2962
2963 if (code == COND_EXPR)
2964 {
2965 if (! nested_in_vect_loop)
2966 *v_reduc_type = COND_REDUCTION;
2967
2968 op3 = gimple_assign_rhs1 (def_stmt);
2969 if (COMPARISON_CLASS_P (op3))
2970 {
2971 op4 = TREE_OPERAND (op3, 1);
2972 op3 = TREE_OPERAND (op3, 0);
2973 }
2974 if (op3 == phi_name || op4 == phi_name)
2975 {
2976 if (dump_enabled_p ())
2977 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
2978 "reduction: condition depends on previous"
2979 " iteration: ");
2980 return NULL;
2981 }
2982
2983 op1 = gimple_assign_rhs2 (def_stmt);
2984 op2 = gimple_assign_rhs3 (def_stmt);
2985 }
2986 else if (!commutative_tree_code (code) || !associative_tree_code (code))
2987 {
2988 if (dump_enabled_p ())
2989 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
2990 "reduction: not commutative/associative: ");
2991 return NULL;
2992 }
2993 else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
2994 {
2995 op1 = gimple_assign_rhs1 (def_stmt);
2996 op2 = gimple_assign_rhs2 (def_stmt);
2997 }
2998 else
2999 {
3000 if (dump_enabled_p ())
3001 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
3002 "reduction: not handled operation: ");
3003 return NULL;
3004 }
3005
3006 if (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op2) != SSA_NAME)
3007 {
3008 if (dump_enabled_p ())
3009 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
3010 "reduction: both uses not ssa_names: ");
3011
3012 return NULL;
3013 }
3014
3015 type = TREE_TYPE (gimple_assign_lhs (def_stmt));
3016 if ((TREE_CODE (op1) == SSA_NAME
3017 && !types_compatible_p (type,TREE_TYPE (op1)))
3018 || (TREE_CODE (op2) == SSA_NAME
3019 && !types_compatible_p (type, TREE_TYPE (op2)))
3020 || (op3 && TREE_CODE (op3) == SSA_NAME
3021 && !types_compatible_p (type, TREE_TYPE (op3)))
3022 || (op4 && TREE_CODE (op4) == SSA_NAME
3023 && !types_compatible_p (type, TREE_TYPE (op4))))
3024 {
3025 if (dump_enabled_p ())
3026 {
3027 dump_printf_loc (MSG_NOTE, vect_location,
3028 "reduction: multiple types: operation type: ");
3029 dump_generic_expr (MSG_NOTE, TDF_SLIM, type);
3030 dump_printf (MSG_NOTE, ", operands types: ");
3031 dump_generic_expr (MSG_NOTE, TDF_SLIM,
3032 TREE_TYPE (op1));
3033 dump_printf (MSG_NOTE, ",");
3034 dump_generic_expr (MSG_NOTE, TDF_SLIM,
3035 TREE_TYPE (op2));
3036 if (op3)
3037 {
3038 dump_printf (MSG_NOTE, ",");
3039 dump_generic_expr (MSG_NOTE, TDF_SLIM,
3040 TREE_TYPE (op3));
3041 }
3042
3043 if (op4)
3044 {
3045 dump_printf (MSG_NOTE, ",");
3046 dump_generic_expr (MSG_NOTE, TDF_SLIM,
3047 TREE_TYPE (op4));
3048 }
3049 dump_printf (MSG_NOTE, "\n");
3050 }
3051
3052 return NULL;
3053 }
3054
3055 /* Check that it's ok to change the order of the computation.
3056 Generally, when vectorizing a reduction we change the order of the
3057 computation. This may change the behavior of the program in some
3058 cases, so we need to check that this is ok. One exception is when
3059 vectorizing an outer-loop: the inner-loop is executed sequentially,
3060 and therefore vectorizing reductions in the inner-loop during
3061 outer-loop vectorization is safe. */
3062
3063 if (*v_reduc_type != COND_REDUCTION
3064 && check_reduction)
3065 {
3066 /* CHECKME: check for !flag_finite_math_only too? */
3067 if (SCALAR_FLOAT_TYPE_P (type) && !flag_associative_math)
3068 {
3069 /* Changing the order of operations changes the semantics. */
3070 if (dump_enabled_p ())
3071 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
3072 "reduction: unsafe fp math optimization: ");
3073 return NULL;
3074 }
3075 else if (INTEGRAL_TYPE_P (type))
3076 {
3077 if (!operation_no_trapping_overflow (type, code))
3078 {
3079 /* Changing the order of operations changes the semantics. */
3080 if (dump_enabled_p ())
3081 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
3082 "reduction: unsafe int math optimization"
3083 " (overflow traps): ");
3084 return NULL;
3085 }
3086 if (need_wrapping_integral_overflow
3087 && !TYPE_OVERFLOW_WRAPS (type)
3088 && operation_can_overflow (code))
3089 {
3090 /* Changing the order of operations changes the semantics. */
3091 if (dump_enabled_p ())
3092 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
3093 "reduction: unsafe int math optimization"
3094 " (overflow doesn't wrap): ");
3095 return NULL;
3096 }
3097 }
3098 else if (SAT_FIXED_POINT_TYPE_P (type))
3099 {
3100 /* Changing the order of operations changes the semantics. */
3101 if (dump_enabled_p ())
3102 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
3103 "reduction: unsafe fixed-point math optimization: ");
3104 return NULL;
3105 }
3106 }
3107
3108 /* Reduction is safe. We're dealing with one of the following:
3109 1) integer arithmetic and no trapv
3110 2) floating point arithmetic, and special flags permit this optimization
3111 3) nested cycle (i.e., outer loop vectorization). */
3112 if (TREE_CODE (op1) == SSA_NAME)
3113 def1 = SSA_NAME_DEF_STMT (op1);
3114
3115 if (TREE_CODE (op2) == SSA_NAME)
3116 def2 = SSA_NAME_DEF_STMT (op2);
3117
3118 if (code != COND_EXPR
3119 && ((!def1 || gimple_nop_p (def1)) && (!def2 || gimple_nop_p (def2))))
3120 {
3121 if (dump_enabled_p ())
3122 report_vect_op (MSG_NOTE, def_stmt, "reduction: no defs for operands: ");
3123 return NULL;
3124 }
3125
3126 /* Check that one def is the reduction def, defined by PHI,
3127 the other def is either defined in the loop ("vect_internal_def"),
3128 or it's an induction (defined by a loop-header phi-node). */
3129
3130 if (def2 && def2 == phi
3131 && (code == COND_EXPR
3132 || !def1 || gimple_nop_p (def1)
3133 || !flow_bb_inside_loop_p (loop, gimple_bb (def1))
3134 || (def1 && flow_bb_inside_loop_p (loop, gimple_bb (def1))
3135 && (is_gimple_assign (def1)
3136 || is_gimple_call (def1)
3137 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1))
3138 == vect_induction_def
3139 || (gimple_code (def1) == GIMPLE_PHI
3140 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1))
3141 == vect_internal_def
3142 && !is_loop_header_bb_p (gimple_bb (def1)))))))
3143 {
3144 if (dump_enabled_p ())
3145 report_vect_op (MSG_NOTE, def_stmt, "detected reduction: ");
3146 return def_stmt;
3147 }
3148
3149 if (def1 && def1 == phi
3150 && (code == COND_EXPR
3151 || !def2 || gimple_nop_p (def2)
3152 || !flow_bb_inside_loop_p (loop, gimple_bb (def2))
3153 || (def2 && flow_bb_inside_loop_p (loop, gimple_bb (def2))
3154 && (is_gimple_assign (def2)
3155 || is_gimple_call (def2)
3156 || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2))
3157 == vect_induction_def
3158 || (gimple_code (def2) == GIMPLE_PHI
3159 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2))
3160 == vect_internal_def
3161 && !is_loop_header_bb_p (gimple_bb (def2)))))))
3162 {
3163 if (! nested_in_vect_loop && orig_code != MINUS_EXPR)
3164 {
3165 /* Check if we can swap operands (just for simplicity - so that
3166 the rest of the code can assume that the reduction variable
3167 is always the last (second) argument). */
3168 if (code == COND_EXPR)
3169 {
3170 /* Swap cond_expr by inverting the condition. */
3171 tree cond_expr = gimple_assign_rhs1 (def_stmt);
3172 enum tree_code invert_code = ERROR_MARK;
3173 enum tree_code cond_code = TREE_CODE (cond_expr);
3174
3175 if (TREE_CODE_CLASS (cond_code) == tcc_comparison)
3176 {
3177 bool honor_nans = HONOR_NANS (TREE_OPERAND (cond_expr, 0));
3178 invert_code = invert_tree_comparison (cond_code, honor_nans);
3179 }
3180 if (invert_code != ERROR_MARK)
3181 {
3182 TREE_SET_CODE (cond_expr, invert_code);
3183 swap_ssa_operands (def_stmt,
3184 gimple_assign_rhs2_ptr (def_stmt),
3185 gimple_assign_rhs3_ptr (def_stmt));
3186 }
3187 else
3188 {
3189 if (dump_enabled_p ())
3190 report_vect_op (MSG_NOTE, def_stmt,
3191 "detected reduction: cannot swap operands "
3192 "for cond_expr");
3193 return NULL;
3194 }
3195 }
3196 else
3197 swap_ssa_operands (def_stmt, gimple_assign_rhs1_ptr (def_stmt),
3198 gimple_assign_rhs2_ptr (def_stmt));
3199
3200 if (dump_enabled_p ())
3201 report_vect_op (MSG_NOTE, def_stmt,
3202 "detected reduction: need to swap operands: ");
3203
3204 if (CONSTANT_CLASS_P (gimple_assign_rhs1 (def_stmt)))
3205 LOOP_VINFO_OPERANDS_SWAPPED (loop_info) = true;
3206 }
3207 else
3208 {
3209 if (dump_enabled_p ())
3210 report_vect_op (MSG_NOTE, def_stmt, "detected reduction: ");
3211 }
3212
3213 return def_stmt;
3214 }
3215
3216 /* Try to find SLP reduction chain. */
3217 if (! nested_in_vect_loop
3218 && code != COND_EXPR
3219 && orig_code != MINUS_EXPR
3220 && vect_is_slp_reduction (loop_info, phi, def_stmt))
3221 {
3222 if (dump_enabled_p ())
3223 report_vect_op (MSG_NOTE, def_stmt,
3224 "reduction: detected reduction chain: ");
3225
3226 return def_stmt;
3227 }
3228
3229 /* Dissolve group eventually half-built by vect_is_slp_reduction. */
3230 gimple *first = GROUP_FIRST_ELEMENT (vinfo_for_stmt (def_stmt));
3231 while (first)
3232 {
3233 gimple *next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (first));
3234 GROUP_FIRST_ELEMENT (vinfo_for_stmt (first)) = NULL;
3235 GROUP_NEXT_ELEMENT (vinfo_for_stmt (first)) = NULL;
3236 first = next;
3237 }
3238
3239 /* Look for the expression computing loop_arg from loop PHI result. */
3240 if (check_reduction_path (vect_location, loop, as_a <gphi *> (phi), loop_arg,
3241 code))
3242 return def_stmt;
3243
3244 if (dump_enabled_p ())
3245 {
3246 report_vect_op (MSG_MISSED_OPTIMIZATION, def_stmt,
3247 "reduction: unknown pattern: ");
3248 }
3249
3250 return NULL;
3251}
3252
3253/* Wrapper around vect_is_simple_reduction, which will modify code
3254 in-place if it enables detection of more reductions. Arguments
3255 as there. */
3256
3257gimple *
3258vect_force_simple_reduction (loop_vec_info loop_info, gimple *phi,
3259 bool *double_reduc,
3260 bool need_wrapping_integral_overflow)
3261{
3262 enum vect_reduction_type v_reduc_type;
3263 gimple *def = vect_is_simple_reduction (loop_info, phi, double_reduc,
3264 need_wrapping_integral_overflow,
3265 &v_reduc_type);
3266 if (def)
3267 {
3268 stmt_vec_info reduc_def_info = vinfo_for_stmt (phi);
3269 STMT_VINFO_REDUC_TYPE (reduc_def_info) = v_reduc_type;
3270 STMT_VINFO_REDUC_DEF (reduc_def_info) = def;
3271 reduc_def_info = vinfo_for_stmt (def);
3272 STMT_VINFO_REDUC_DEF (reduc_def_info) = phi;
3273 }
3274 return def;
3275}
3276
3277/* Calculate cost of peeling the loop PEEL_ITERS_PROLOGUE times. */
3278int
3279vect_get_known_peeling_cost (loop_vec_info loop_vinfo, int peel_iters_prologue,
3280 int *peel_iters_epilogue,
3281 stmt_vector_for_cost *scalar_cost_vec,
3282 stmt_vector_for_cost *prologue_cost_vec,
3283 stmt_vector_for_cost *epilogue_cost_vec)
3284{
3285 int retval = 0;
3286 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
3287
3288 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
3289 {
3290 *peel_iters_epilogue = vf/2;
3291 if (dump_enabled_p ())
3292 dump_printf_loc (MSG_NOTE, vect_location,
3293 "cost model: epilogue peel iters set to vf/2 "
3294 "because loop iterations are unknown .\n");
3295
3296 /* If peeled iterations are known but number of scalar loop
3297 iterations are unknown, count a taken branch per peeled loop. */
3298 retval = record_stmt_cost (prologue_cost_vec, 1, cond_branch_taken,
3299 NULL, 0, vect_prologue);
3300 retval = record_stmt_cost (prologue_cost_vec, 1, cond_branch_taken,
3301 NULL, 0, vect_epilogue);
3302 }
3303 else
3304 {
3305 int niters = LOOP_VINFO_INT_NITERS (loop_vinfo);
3306 peel_iters_prologue = niters < peel_iters_prologue ?
3307 niters : peel_iters_prologue;
3308 *peel_iters_epilogue = (niters - peel_iters_prologue) % vf;
3309 /* If we need to peel for gaps, but no peeling is required, we have to
3310 peel VF iterations. */
3311 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo) && !*peel_iters_epilogue)
3312 *peel_iters_epilogue = vf;
3313 }
3314
3315 stmt_info_for_cost *si;
3316 int j;
3317 if (peel_iters_prologue)
3318 FOR_EACH_VEC_ELT (*scalar_cost_vec, j, si)
3319 {
3320 stmt_vec_info stmt_info
3321 = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
3322 retval += record_stmt_cost (prologue_cost_vec,
3323 si->count * peel_iters_prologue,
3324 si->kind, stmt_info, si->misalign,
3325 vect_prologue);
3326 }
3327 if (*peel_iters_epilogue)
3328 FOR_EACH_VEC_ELT (*scalar_cost_vec, j, si)
3329 {
3330 stmt_vec_info stmt_info
3331 = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
3332 retval += record_stmt_cost (epilogue_cost_vec,
3333 si->count * *peel_iters_epilogue,
3334 si->kind, stmt_info, si->misalign,
3335 vect_epilogue);
3336 }
3337
3338 return retval;
3339}
3340
3341/* Function vect_estimate_min_profitable_iters
3342
3343 Return the number of iterations required for the vector version of the
3344 loop to be profitable relative to the cost of the scalar version of the
3345 loop.
3346
3347 *RET_MIN_PROFITABLE_NITERS is a cost model profitability threshold
3348 of iterations for vectorization. -1 value means loop vectorization
3349 is not profitable. This returned value may be used for dynamic
3350 profitability check.
3351
3352 *RET_MIN_PROFITABLE_ESTIMATE is a profitability threshold to be used
3353 for static check against estimated number of iterations. */
3354
3355static void
3356vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo,
3357 int *ret_min_profitable_niters,
3358 int *ret_min_profitable_estimate)
3359{
3360 int min_profitable_iters;
3361 int min_profitable_estimate;
3362 int peel_iters_prologue;
3363 int peel_iters_epilogue;
3364 unsigned vec_inside_cost = 0;
3365 int vec_outside_cost = 0;
3366 unsigned vec_prologue_cost = 0;
3367 unsigned vec_epilogue_cost = 0;
3368 int scalar_single_iter_cost = 0;
3369 int scalar_outside_cost = 0;
3370 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
3371 int npeel = LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo);
3372 void *target_cost_data = LOOP_VINFO_TARGET_COST_DATA (loop_vinfo);
3373
3374 /* Cost model disabled. */
3375 if (unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo)))
3376 {
3377 dump_printf_loc (MSG_NOTE, vect_location, "cost model disabled.\n");
3378 *ret_min_profitable_niters = 0;
3379 *ret_min_profitable_estimate = 0;
3380 return;
3381 }
3382
3383 /* Requires loop versioning tests to handle misalignment. */
3384 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo))
3385 {
3386 /* FIXME: Make cost depend on complexity of individual check. */
3387 unsigned len = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).length ();
3388 (void) add_stmt_cost (target_cost_data, len, vector_stmt, NULL, 0,
3389 vect_prologue);
3390 dump_printf (MSG_NOTE,
3391 "cost model: Adding cost of checks for loop "
3392 "versioning to treat misalignment.\n");
3393 }
3394
3395 /* Requires loop versioning with alias checks. */
3396 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
3397 {
3398 /* FIXME: Make cost depend on complexity of individual check. */
3399 unsigned len = LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo).length ();
3400 (void) add_stmt_cost (target_cost_data, len, vector_stmt, NULL, 0,
3401 vect_prologue);
3402 len = LOOP_VINFO_CHECK_UNEQUAL_ADDRS (loop_vinfo).length ();
3403 if (len)
3404 /* Count LEN - 1 ANDs and LEN comparisons. */
3405 (void) add_stmt_cost (target_cost_data, len * 2 - 1, scalar_stmt,
3406 NULL, 0, vect_prologue);
3407 dump_printf (MSG_NOTE,
3408 "cost model: Adding cost of checks for loop "
3409 "versioning aliasing.\n");
3410 }
3411
3412 /* Requires loop versioning with niter checks. */
3413 if (LOOP_REQUIRES_VERSIONING_FOR_NITERS (loop_vinfo))
3414 {
3415 /* FIXME: Make cost depend on complexity of individual check. */
3416 (void) add_stmt_cost (target_cost_data, 1, vector_stmt, NULL, 0,
3417 vect_prologue);
3418 dump_printf (MSG_NOTE,
3419 "cost model: Adding cost of checks for loop "
3420 "versioning niters.\n");
3421 }
3422
3423 if (LOOP_REQUIRES_VERSIONING (loop_vinfo))
3424 (void) add_stmt_cost (target_cost_data, 1, cond_branch_taken, NULL, 0,
3425 vect_prologue);
3426
3427 /* Count statements in scalar loop. Using this as scalar cost for a single
3428 iteration for now.
3429
3430 TODO: Add outer loop support.
3431
3432 TODO: Consider assigning different costs to different scalar
3433 statements. */
3434
3435 scalar_single_iter_cost
3436 = LOOP_VINFO_SINGLE_SCALAR_ITERATION_COST (loop_vinfo);
3437
3438 /* Add additional cost for the peeled instructions in prologue and epilogue
3439 loop.
3440
3441 FORNOW: If we don't know the value of peel_iters for prologue or epilogue
3442 at compile-time - we assume it's vf/2 (the worst would be vf-1).
3443
3444 TODO: Build an expression that represents peel_iters for prologue and
3445 epilogue to be used in a run-time test. */
3446
3447 if (npeel < 0)
3448 {
3449 peel_iters_prologue = vf/2;
3450 dump_printf (MSG_NOTE, "cost model: "
3451 "prologue peel iters set to vf/2.\n");
3452
3453 /* If peeling for alignment is unknown, loop bound of main loop becomes
3454 unknown. */
3455 peel_iters_epilogue = vf/2;
3456 dump_printf (MSG_NOTE, "cost model: "
3457 "epilogue peel iters set to vf/2 because "
3458 "peeling for alignment is unknown.\n");
3459
3460 /* If peeled iterations are unknown, count a taken branch and a not taken
3461 branch per peeled loop. Even if scalar loop iterations are known,
3462 vector iterations are not known since peeled prologue iterations are
3463 not known. Hence guards remain the same. */
3464 (void) add_stmt_cost (target_cost_data, 1, cond_branch_taken,
3465 NULL, 0, vect_prologue);
3466 (void) add_stmt_cost (target_cost_data, 1, cond_branch_not_taken,
3467 NULL, 0, vect_prologue);
3468 (void) add_stmt_cost (target_cost_data, 1, cond_branch_taken,
3469 NULL, 0, vect_epilogue);
3470 (void) add_stmt_cost (target_cost_data, 1, cond_branch_not_taken,
3471 NULL, 0, vect_epilogue);
3472 stmt_info_for_cost *si;
3473 int j;
3474 FOR_EACH_VEC_ELT (LOOP_VINFO_SCALAR_ITERATION_COST (loop_vinfo), j, si)
3475 {
3476 struct _stmt_vec_info *stmt_info
3477 = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
3478 (void) add_stmt_cost (target_cost_data,
3479 si->count * peel_iters_prologue,
3480 si->kind, stmt_info, si->misalign,
3481 vect_prologue);
3482 (void) add_stmt_cost (target_cost_data,
3483 si->count * peel_iters_epilogue,
3484 si->kind, stmt_info, si->misalign,
3485 vect_epilogue);
3486 }
3487 }
3488 else
3489 {
3490 stmt_vector_for_cost prologue_cost_vec, epilogue_cost_vec;
3491 stmt_info_for_cost *si;
3492 int j;
3493 void *data = LOOP_VINFO_TARGET_COST_DATA (loop_vinfo);
3494
3495 prologue_cost_vec.create (2);
3496 epilogue_cost_vec.create (2);
3497 peel_iters_prologue = npeel;
3498
3499 (void) vect_get_known_peeling_cost (loop_vinfo, peel_iters_prologue,
3500 &peel_iters_epilogue,
3501 &LOOP_VINFO_SCALAR_ITERATION_COST
3502 (loop_vinfo),
3503 &prologue_cost_vec,
3504 &epilogue_cost_vec);
3505
3506 FOR_EACH_VEC_ELT (prologue_cost_vec, j, si)
3507 {
3508 struct _stmt_vec_info *stmt_info
3509 = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
3510 (void) add_stmt_cost (data, si->count, si->kind, stmt_info,
3511 si->misalign, vect_prologue);
3512 }
3513
3514 FOR_EACH_VEC_ELT (epilogue_cost_vec, j, si)
3515 {
3516 struct _stmt_vec_info *stmt_info
3517 = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
3518 (void) add_stmt_cost (data, si->count, si->kind, stmt_info,
3519 si->misalign, vect_epilogue);
3520 }
3521
3522 prologue_cost_vec.release ();
3523 epilogue_cost_vec.release ();
3524 }
3525
3526 /* FORNOW: The scalar outside cost is incremented in one of the
3527 following ways:
3528
3529 1. The vectorizer checks for alignment and aliasing and generates
3530 a condition that allows dynamic vectorization. A cost model
3531 check is ANDED with the versioning condition. Hence scalar code
3532 path now has the added cost of the versioning check.
3533
3534 if (cost > th & versioning_check)
3535 jmp to vector code
3536
3537 Hence run-time scalar is incremented by not-taken branch cost.
3538
3539 2. The vectorizer then checks if a prologue is required. If the
3540 cost model check was not done before during versioning, it has to
3541 be done before the prologue check.
3542
3543 if (cost <= th)
3544 prologue = scalar_iters
3545 if (prologue == 0)
3546 jmp to vector code
3547 else
3548 execute prologue
3549 if (prologue == num_iters)
3550 go to exit
3551
3552 Hence the run-time scalar cost is incremented by a taken branch,
3553 plus a not-taken branch, plus a taken branch cost.
3554
3555 3. The vectorizer then checks if an epilogue is required. If the
3556 cost model check was not done before during prologue check, it
3557 has to be done with the epilogue check.
3558
3559 if (prologue == 0)
3560 jmp to vector code
3561 else
3562 execute prologue
3563 if (prologue == num_iters)
3564 go to exit
3565 vector code:
3566 if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
3567 jmp to epilogue
3568
3569 Hence the run-time scalar cost should be incremented by 2 taken
3570 branches.
3571
3572 TODO: The back end may reorder the BBS's differently and reverse
3573 conditions/branch directions. Change the estimates below to
3574 something more reasonable. */
3575
3576 /* If the number of iterations is known and we do not do versioning, we can
3577 decide whether to vectorize at compile time. Hence the scalar version
3578 do not carry cost model guard costs. */
3579 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
3580 || LOOP_REQUIRES_VERSIONING (loop_vinfo))
3581 {
3582 /* Cost model check occurs at versioning. */
3583 if (LOOP_REQUIRES_VERSIONING (loop_vinfo))
3584 scalar_outside_cost += vect_get_stmt_cost (cond_branch_not_taken);
3585 else
3586 {
3587 /* Cost model check occurs at prologue generation. */
3588 if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0)
3589 scalar_outside_cost += 2 * vect_get_stmt_cost (cond_branch_taken)
3590 + vect_get_stmt_cost (cond_branch_not_taken);
3591 /* Cost model check occurs at epilogue generation. */
3592 else
3593 scalar_outside_cost += 2 * vect_get_stmt_cost (cond_branch_taken);
3594 }
3595 }
3596
3597 /* Complete the target-specific cost calculations. */
3598 finish_cost (LOOP_VINFO_TARGET_COST_DATA (loop_vinfo), &vec_prologue_cost,
3599 &vec_inside_cost, &vec_epilogue_cost);
3600
3601 vec_outside_cost = (int)(vec_prologue_cost + vec_epilogue_cost);
3602
3603 if (dump_enabled_p ())
3604 {
3605 dump_printf_loc (MSG_NOTE, vect_location, "Cost model analysis: \n");
3606 dump_printf (MSG_NOTE, " Vector inside of loop cost: %d\n",
3607 vec_inside_cost);
3608 dump_printf (MSG_NOTE, " Vector prologue cost: %d\n",
3609 vec_prologue_cost);
3610 dump_printf (MSG_NOTE, " Vector epilogue cost: %d\n",
3611 vec_epilogue_cost);
3612 dump_printf (MSG_NOTE, " Scalar iteration cost: %d\n",
3613 scalar_single_iter_cost);
3614 dump_printf (MSG_NOTE, " Scalar outside cost: %d\n",
3615 scalar_outside_cost);
3616 dump_printf (MSG_NOTE, " Vector outside cost: %d\n",
3617 vec_outside_cost);
3618 dump_printf (MSG_NOTE, " prologue iterations: %d\n",
3619 peel_iters_prologue);
3620 dump_printf (MSG_NOTE, " epilogue iterations: %d\n",
3621 peel_iters_epilogue);
3622 }
3623
3624 /* Calculate number of iterations required to make the vector version
3625 profitable, relative to the loop bodies only. The following condition
3626 must hold true:
3627 SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
3628 where
3629 SIC = scalar iteration cost, VIC = vector iteration cost,
3630 VOC = vector outside cost, VF = vectorization factor,
3631 PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
3632 SOC = scalar outside cost for run time cost model check. */
3633
3634 if ((scalar_single_iter_cost * vf) > (int) vec_inside_cost)
3635 {
3636 if (vec_outside_cost <= 0)
3637 min_profitable_iters = 0;
3638 else
3639 {
3640 min_profitable_iters = ((vec_outside_cost - scalar_outside_cost) * vf
3641 - vec_inside_cost * peel_iters_prologue
3642 - vec_inside_cost * peel_iters_epilogue)
3643 / ((scalar_single_iter_cost * vf)
3644 - vec_inside_cost);
3645
3646 if ((scalar_single_iter_cost * vf * min_profitable_iters)
3647 <= (((int) vec_inside_cost * min_profitable_iters)
3648 + (((int) vec_outside_cost - scalar_outside_cost) * vf)))
3649 min_profitable_iters++;
3650 }
3651 }
3652 /* vector version will never be profitable. */
3653 else
3654 {
3655 if (LOOP_VINFO_LOOP (loop_vinfo)->force_vectorize)
3656 warning_at (vect_location, OPT_Wopenmp_simd, "vectorization "
3657 "did not happen for a simd loop");
3658
3659 if (dump_enabled_p ())
3660 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3661 "cost model: the vector iteration cost = %d "
3662 "divided by the scalar iteration cost = %d "
3663 "is greater or equal to the vectorization factor = %d"
3664 ".\n",
3665 vec_inside_cost, scalar_single_iter_cost, vf);
3666 *ret_min_profitable_niters = -1;
3667 *ret_min_profitable_estimate = -1;
3668 return;
3669 }
3670
3671 dump_printf (MSG_NOTE,
3672 " Calculated minimum iters for profitability: %d\n",
3673 min_profitable_iters);
3674
3675 /* We want the vectorized loop to execute at least once. */
3676 if (min_profitable_iters < (vf + peel_iters_prologue))
3677 min_profitable_iters = vf + peel_iters_prologue;
3678
3679 if (dump_enabled_p ())
3680 dump_printf_loc (MSG_NOTE, vect_location,
3681 " Runtime profitability threshold = %d\n",
3682 min_profitable_iters);
3683
3684 *ret_min_profitable_niters = min_profitable_iters;
3685
3686 /* Calculate number of iterations required to make the vector version
3687 profitable, relative to the loop bodies only.
3688
3689 Non-vectorized variant is SIC * niters and it must win over vector
3690 variant on the expected loop trip count. The following condition must hold true:
3691 SIC * niters > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC + SOC */
3692
3693 if (vec_outside_cost <= 0)
3694 min_profitable_estimate = 0;
3695 else
3696 {
3697 min_profitable_estimate = ((vec_outside_cost + scalar_outside_cost) * vf
3698 - vec_inside_cost * peel_iters_prologue
3699 - vec_inside_cost * peel_iters_epilogue)
3700 / ((scalar_single_iter_cost * vf)
3701 - vec_inside_cost);
3702 }
3703 min_profitable_estimate = MAX (min_profitable_estimate, min_profitable_iters);
3704 if (dump_enabled_p ())
3705 dump_printf_loc (MSG_NOTE, vect_location,
3706 " Static estimate profitability threshold = %d\n",
3707 min_profitable_estimate);
3708
3709 *ret_min_profitable_estimate = min_profitable_estimate;
3710}
3711
3712/* Writes into SEL a mask for a vec_perm, equivalent to a vec_shr by OFFSET
3713 vector elements (not bits) for a vector with NELT elements. */
3714static void
3715calc_vec_perm_mask_for_shift (unsigned int offset, unsigned int nelt,
3716 vec_perm_indices *sel)
3717{
3718 unsigned int i;
3719
3720 for (i = 0; i < nelt; i++)
3721 sel->quick_push ((i + offset) & (2 * nelt - 1));
3722}
3723
3724/* Checks whether the target supports whole-vector shifts for vectors of mode
3725 MODE. This is the case if _either_ the platform handles vec_shr_optab, _or_
3726 it supports vec_perm_const with masks for all necessary shift amounts. */
3727static bool
3728have_whole_vector_shift (machine_mode mode)
3729{
3730 if (optab_handler (vec_shr_optab, mode) != CODE_FOR_nothing)
3731 return true;
3732
3733 if (direct_optab_handler (vec_perm_const_optab, mode) == CODE_FOR_nothing)
3734 return false;
3735
3736 unsigned int i, nelt = GET_MODE_NUNITS (mode);
3737 auto_vec_perm_indices sel (nelt);
3738
3739 for (i = nelt/2; i >= 1; i/=2)
3740 {
3741 sel.truncate (0);
3742 calc_vec_perm_mask_for_shift (i, nelt, &sel);
3743 if (!can_vec_perm_p (mode, false, &sel))
3744 return false;
3745 }
3746 return true;
3747}
3748
3749/* TODO: Close dependency between vect_model_*_cost and vectorizable_*
3750 functions. Design better to avoid maintenance issues. */
3751
3752/* Function vect_model_reduction_cost.
3753
3754 Models cost for a reduction operation, including the vector ops
3755 generated within the strip-mine loop, the initial definition before
3756 the loop, and the epilogue code that must be generated. */
3757
3758static void
3759vect_model_reduction_cost (stmt_vec_info stmt_info, internal_fn reduc_fn,
3760 int ncopies)
3761{
3762 int prologue_cost = 0, epilogue_cost = 0;
3763 enum tree_code code;
3764 optab optab;
3765 tree vectype;
3766 gimple *orig_stmt;
3767 machine_mode mode;
3768 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3769 struct loop *loop = NULL;
3770 void *target_cost_data;
3771
3772 if (loop_vinfo)
3773 {
3774 loop = LOOP_VINFO_LOOP (loop_vinfo);
3775 target_cost_data = LOOP_VINFO_TARGET_COST_DATA (loop_vinfo);
3776 }
3777 else
3778 target_cost_data = BB_VINFO_TARGET_COST_DATA (STMT_VINFO_BB_VINFO (stmt_info));
3779
3780 /* Condition reductions generate two reductions in the loop. */
3781 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION)
3782 ncopies *= 2;
3783
3784 /* Cost of reduction op inside loop. */
3785 unsigned inside_cost = add_stmt_cost (target_cost_data, ncopies, vector_stmt,
3786 stmt_info, 0, vect_body);
3787
3788 vectype = STMT_VINFO_VECTYPE (stmt_info);
3789 mode = TYPE_MODE (vectype);
3790 orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
3791
3792 if (!orig_stmt)
3793 orig_stmt = STMT_VINFO_STMT (stmt_info);
3794
3795 code = gimple_assign_rhs_code (orig_stmt);
3796
3797 /* Add in cost for initial definition.
3798 For cond reduction we have four vectors: initial index, step, initial
3799 result of the data reduction, initial value of the index reduction. */
3800 int prologue_stmts = STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
3801 == COND_REDUCTION ? 4 : 1;
3802 prologue_cost += add_stmt_cost (target_cost_data, prologue_stmts,
3803 scalar_to_vec, stmt_info, 0,
3804 vect_prologue);
3805
3806 /* Determine cost of epilogue code.
3807
3808 We have a reduction operator that will reduce the vector in one statement.
3809 Also requires scalar extract. */
3810
3811 if (!loop || !nested_in_vect_loop_p (loop, orig_stmt))
3812 {
3813 if (reduc_fn != IFN_LAST)
3814 {
3815 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION)
3816 {
3817 /* An EQ stmt and an COND_EXPR stmt. */
3818 epilogue_cost += add_stmt_cost (target_cost_data, 2,
3819 vector_stmt, stmt_info, 0,
3820 vect_epilogue);
3821 /* Reduction of the max index and a reduction of the found
3822 values. */
3823 epilogue_cost += add_stmt_cost (target_cost_data, 2,
3824 vec_to_scalar, stmt_info, 0,
3825 vect_epilogue);
3826 /* A broadcast of the max value. */
3827 epilogue_cost += add_stmt_cost (target_cost_data, 1,
3828 scalar_to_vec, stmt_info, 0,
3829 vect_epilogue);
3830 }
3831 else
3832 {
3833 epilogue_cost += add_stmt_cost (target_cost_data, 1, vector_stmt,
3834 stmt_info, 0, vect_epilogue);
3835 epilogue_cost += add_stmt_cost (target_cost_data, 1,
3836 vec_to_scalar, stmt_info, 0,
3837 vect_epilogue);
3838 }
3839 }
3840 else if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION)
3841 {
3842 unsigned nunits = TYPE_VECTOR_SUBPARTS (vectype);
3843 /* Extraction of scalar elements. */
3844 epilogue_cost += add_stmt_cost (target_cost_data, 2 * nunits,
3845 vec_to_scalar, stmt_info, 0,
3846 vect_epilogue);
3847 /* Scalar max reductions via COND_EXPR / MAX_EXPR. */
3848 epilogue_cost += add_stmt_cost (target_cost_data, 2 * nunits - 3,
3849 scalar_stmt, stmt_info, 0,
3850 vect_epilogue);
3851 }
3852 else
3853 {
3854 int vec_size_in_bits = tree_to_uhwi (TYPE_SIZE (vectype));
3855 tree bitsize =
3856 TYPE_SIZE (TREE_TYPE (gimple_assign_lhs (orig_stmt)));
3857 int element_bitsize = tree_to_uhwi (bitsize);
3858 int nelements = vec_size_in_bits / element_bitsize;
3859
3860 if (code == COND_EXPR)
3861 code = MAX_EXPR;
3862
3863 optab = optab_for_tree_code (code, vectype, optab_default);
3864
3865 /* We have a whole vector shift available. */
3866 if (optab != unknown_optab
3867 && VECTOR_MODE_P (mode)
3868 && optab_handler (optab, mode) != CODE_FOR_nothing
3869 && have_whole_vector_shift (mode))
3870 {
3871 /* Final reduction via vector shifts and the reduction operator.
3872 Also requires scalar extract. */
3873 epilogue_cost += add_stmt_cost (target_cost_data,
3874 exact_log2 (nelements) * 2,
3875 vector_stmt, stmt_info, 0,
3876 vect_epilogue);
3877 epilogue_cost += add_stmt_cost (target_cost_data, 1,
3878 vec_to_scalar, stmt_info, 0,
3879 vect_epilogue);
3880 }
3881 else
3882 /* Use extracts and reduction op for final reduction. For N
3883 elements, we have N extracts and N-1 reduction ops. */
3884 epilogue_cost += add_stmt_cost (target_cost_data,
3885 nelements + nelements - 1,
3886 vector_stmt, stmt_info, 0,
3887 vect_epilogue);
3888 }
3889 }
3890
3891 if (dump_enabled_p ())
3892 dump_printf (MSG_NOTE,
3893 "vect_model_reduction_cost: inside_cost = %d, "
3894 "prologue_cost = %d, epilogue_cost = %d .\n", inside_cost,
3895 prologue_cost, epilogue_cost);
3896}
3897
3898
3899/* Function vect_model_induction_cost.
3900
3901 Models cost for induction operations. */
3902
3903static void
3904vect_model_induction_cost (stmt_vec_info stmt_info, int ncopies)
3905{
3906 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3907 void *target_cost_data = LOOP_VINFO_TARGET_COST_DATA (loop_vinfo);
3908 unsigned inside_cost, prologue_cost;
3909
3910 if (PURE_SLP_STMT (stmt_info))
3911 return;
3912
3913 /* loop cost for vec_loop. */
3914 inside_cost = add_stmt_cost (target_cost_data, ncopies, vector_stmt,
3915 stmt_info, 0, vect_body);
3916
3917 /* prologue cost for vec_init and vec_step. */
3918 prologue_cost = add_stmt_cost (target_cost_data, 2, scalar_to_vec,
3919 stmt_info, 0, vect_prologue);
3920
3921 if (dump_enabled_p ())
3922 dump_printf_loc (MSG_NOTE, vect_location,
3923 "vect_model_induction_cost: inside_cost = %d, "
3924 "prologue_cost = %d .\n", inside_cost, prologue_cost);
3925}
3926
3927
3928
3929/* Function get_initial_def_for_reduction
3930
3931 Input:
3932 STMT - a stmt that performs a reduction operation in the loop.
3933 INIT_VAL - the initial value of the reduction variable
3934
3935 Output:
3936 ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
3937 of the reduction (used for adjusting the epilog - see below).
3938 Return a vector variable, initialized according to the operation that STMT
3939 performs. This vector will be used as the initial value of the
3940 vector of partial results.
3941
3942 Option1 (adjust in epilog): Initialize the vector as follows:
3943 add/bit or/xor: [0,0,...,0,0]
3944 mult/bit and: [1,1,...,1,1]
3945 min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
3946 and when necessary (e.g. add/mult case) let the caller know
3947 that it needs to adjust the result by init_val.
3948
3949 Option2: Initialize the vector as follows:
3950 add/bit or/xor: [init_val,0,0,...,0]
3951 mult/bit and: [init_val,1,1,...,1]
3952 min/max/cond_expr: [init_val,init_val,...,init_val]
3953 and no adjustments are needed.
3954
3955 For example, for the following code:
3956
3957 s = init_val;
3958 for (i=0;i<n;i++)
3959 s = s + a[i];
3960
3961 STMT is 's = s + a[i]', and the reduction variable is 's'.
3962 For a vector of 4 units, we want to return either [0,0,0,init_val],
3963 or [0,0,0,0] and let the caller know that it needs to adjust
3964 the result at the end by 'init_val'.
3965
3966 FORNOW, we are using the 'adjust in epilog' scheme, because this way the
3967 initialization vector is simpler (same element in all entries), if
3968 ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
3969
3970 A cost model should help decide between these two schemes. */
3971
3972tree
3973get_initial_def_for_reduction (gimple *stmt, tree init_val,
3974 tree *adjustment_def)
3975{
3976 stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
3977 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
3978 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
3979 tree scalar_type = TREE_TYPE (init_val);
3980 tree vectype = get_vectype_for_scalar_type (scalar_type);
3981 enum tree_code code = gimple_assign_rhs_code (stmt);
3982 tree def_for_init;
3983 tree init_def;
3984 bool nested_in_vect_loop = false;
3985 REAL_VALUE_TYPE real_init_val = dconst0;
3986 int int_init_val = 0;
3987 gimple *def_stmt = NULL;
3988 gimple_seq stmts = NULL;
3989
3990 gcc_assert (vectype);
3991
3992 gcc_assert (POINTER_TYPE_P (scalar_type) || INTEGRAL_TYPE_P (scalar_type)
3993 || SCALAR_FLOAT_TYPE_P (scalar_type));
3994
3995 if (nested_in_vect_loop_p (loop, stmt))
3996 nested_in_vect_loop = true;
3997 else
3998 gcc_assert (loop == (gimple_bb (stmt))->loop_father);
3999
4000 /* In case of double reduction we only create a vector variable to be put
4001 in the reduction phi node. The actual statement creation is done in
4002 vect_create_epilog_for_reduction. */
4003 if (adjustment_def && nested_in_vect_loop
4004 && TREE_CODE (init_val) == SSA_NAME
4005 && (def_stmt = SSA_NAME_DEF_STMT (init_val))
4006 && gimple_code (def_stmt) == GIMPLE_PHI
4007 && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
4008 && vinfo_for_stmt (def_stmt)
4009 && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
4010 == vect_double_reduction_def)
4011 {
4012 *adjustment_def = NULL;
4013 return vect_create_destination_var (init_val, vectype);
4014 }
4015
4016 /* In case of a nested reduction do not use an adjustment def as
4017 that case is not supported by the epilogue generation correctly
4018 if ncopies is not one. */
4019 if (adjustment_def && nested_in_vect_loop)
4020 {
4021 *adjustment_def = NULL;
4022 return vect_get_vec_def_for_operand (init_val, stmt);
4023 }
4024
4025 switch (code)
4026 {
4027 case WIDEN_SUM_EXPR:
4028 case DOT_PROD_EXPR:
4029 case SAD_EXPR:
4030 case PLUS_EXPR:
4031 case MINUS_EXPR:
4032 case BIT_IOR_EXPR:
4033 case BIT_XOR_EXPR:
4034 case MULT_EXPR:
4035 case BIT_AND_EXPR:
4036 {
4037 /* ADJUSTMENT_DEF is NULL when called from
4038 vect_create_epilog_for_reduction to vectorize double reduction. */
4039 if (adjustment_def)
4040 *adjustment_def = init_val;
4041
4042 if (code == MULT_EXPR)
4043 {
4044 real_init_val = dconst1;
4045 int_init_val = 1;
4046 }
4047
4048 if (code == BIT_AND_EXPR)
4049 int_init_val = -1;
4050
4051 if (SCALAR_FLOAT_TYPE_P (scalar_type))
4052 def_for_init = build_real (scalar_type, real_init_val);
4053 else
4054 def_for_init = build_int_cst (scalar_type, int_init_val);
4055
4056 if (adjustment_def)
4057 /* Option1: the first element is '0' or '1' as well. */
4058 init_def = gimple_build_vector_from_val (&stmts, vectype,
4059 def_for_init);
4060 else
4061 {
4062 /* Option2: the first element is INIT_VAL. */
4063 tree_vector_builder elts (vectype, 1, 2);
4064 elts.quick_push (init_val);
4065 elts.quick_push (def_for_init);
4066 init_def = gimple_build_vector (&stmts, &elts);
4067 }
4068 }
4069 break;
4070
4071 case MIN_EXPR:
4072 case MAX_EXPR:
4073 case COND_EXPR:
4074 {
4075 if (adjustment_def)
4076 {
4077 *adjustment_def = NULL_TREE;
4078 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_vinfo) != COND_REDUCTION)
4079 {
4080 init_def = vect_get_vec_def_for_operand (init_val, stmt);
4081 break;
4082 }
4083 }
4084 init_val = gimple_convert (&stmts, TREE_TYPE (vectype), init_val);
4085 init_def = gimple_build_vector_from_val (&stmts, vectype, init_val);
4086 }
4087 break;
4088
4089 default:
4090 gcc_unreachable ();
4091 }
4092
4093 if (stmts)
4094 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
4095 return init_def;
4096}
4097
4098/* Get at the initial defs for the reduction PHIs in SLP_NODE.
4099 NUMBER_OF_VECTORS is the number of vector defs to create. */
4100
4101static void
4102get_initial_defs_for_reduction (slp_tree slp_node,
4103 vec<tree> *vec_oprnds,
4104 unsigned int number_of_vectors,
4105 enum tree_code code, bool reduc_chain)
4106{
4107 vec<gimple *> stmts = SLP_TREE_SCALAR_STMTS (slp_node);
4108 gimple *stmt = stmts[0];
4109 stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
4110 unsigned nunits;
4111 unsigned j, number_of_places_left_in_vector;
4112 tree vector_type, scalar_type;
4113 tree vop;
4114 int group_size = stmts.length ();
4115 unsigned int vec_num, i;
4116 unsigned number_of_copies = 1;
4117 vec<tree> voprnds;
4118 voprnds.create (number_of_vectors);
4119 tree neutral_op = NULL;
4120 struct loop *loop;
4121
4122 vector_type = STMT_VINFO_VECTYPE (stmt_vinfo);
4123 scalar_type = TREE_TYPE (vector_type);
4124 nunits = TYPE_VECTOR_SUBPARTS (vector_type);
4125
4126 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def);
4127
4128 loop = (gimple_bb (stmt))->loop_father;
4129 gcc_assert (loop);
4130 edge pe = loop_preheader_edge (loop);
4131
4132 /* op is the reduction operand of the first stmt already. */
4133 /* For additional copies (see the explanation of NUMBER_OF_COPIES below)
4134 we need either neutral operands or the original operands. See
4135 get_initial_def_for_reduction() for details. */
4136 switch (code)
4137 {
4138 case WIDEN_SUM_EXPR:
4139 case DOT_PROD_EXPR:
4140 case SAD_EXPR:
4141 case PLUS_EXPR:
4142 case MINUS_EXPR:
4143 case BIT_IOR_EXPR:
4144 case BIT_XOR_EXPR:
4145 neutral_op = build_zero_cst (scalar_type);
4146 break;
4147
4148 case MULT_EXPR:
4149 neutral_op = build_one_cst (scalar_type);
4150 break;
4151
4152 case BIT_AND_EXPR:
4153 neutral_op = build_all_ones_cst (scalar_type);
4154 break;
4155
4156 /* For MIN/MAX we don't have an easy neutral operand but
4157 the initial values can be used fine here. Only for
4158 a reduction chain we have to force a neutral element. */
4159 case MAX_EXPR:
4160 case MIN_EXPR:
4161 if (! reduc_chain)
4162 neutral_op = NULL;
4163 else
4164 neutral_op = PHI_ARG_DEF_FROM_EDGE (stmt, pe);
4165 break;
4166
4167 default:
4168 gcc_assert (! reduc_chain);
4169 neutral_op = NULL;
4170 }
4171
4172 /* NUMBER_OF_COPIES is the number of times we need to use the same values in
4173 created vectors. It is greater than 1 if unrolling is performed.
4174
4175 For example, we have two scalar operands, s1 and s2 (e.g., group of
4176 strided accesses of size two), while NUNITS is four (i.e., four scalars
4177 of this type can be packed in a vector). The output vector will contain
4178 two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
4179 will be 2).
4180
4181 If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
4182 containing the operands.
4183
4184 For example, NUNITS is four as before, and the group size is 8
4185 (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
4186 {s5, s6, s7, s8}. */
4187
4188 number_of_copies = nunits * number_of_vectors / group_size;
4189
4190 number_of_places_left_in_vector = nunits;
4191 tree_vector_builder elts (vector_type, nunits, 1);
4192 elts.quick_grow (nunits);
4193 for (j = 0; j < number_of_copies; j++)
4194 {
4195 for (i = group_size - 1; stmts.iterate (i, &stmt); i--)
4196 {
4197 tree op;
4198 /* Get the def before the loop. In reduction chain we have only
4199 one initial value. */
4200 if ((j != (number_of_copies - 1)
4201 || (reduc_chain && i != 0))
4202 && neutral_op)
4203 op = neutral_op;
4204 else
4205 op = PHI_ARG_DEF_FROM_EDGE (stmt, pe);
4206
4207 /* Create 'vect_ = {op0,op1,...,opn}'. */
4208 number_of_places_left_in_vector--;
4209 elts[number_of_places_left_in_vector] = op;
4210
4211 if (number_of_places_left_in_vector == 0)
4212 {
4213 gimple_seq ctor_seq = NULL;
4214 tree init = gimple_build_vector (&ctor_seq, &elts);
4215 if (ctor_seq != NULL)
4216 gsi_insert_seq_on_edge_immediate (pe, ctor_seq);
4217 voprnds.quick_push (init);
4218
4219 number_of_places_left_in_vector = nunits;
4220 elts.new_vector (vector_type, nunits, 1);
4221 elts.quick_grow (nunits);
4222 }
4223 }
4224 }
4225
4226 /* Since the vectors are created in the reverse order, we should invert
4227 them. */
4228 vec_num = voprnds.length ();
4229 for (j = vec_num; j != 0; j--)
4230 {
4231 vop = voprnds[j - 1];
4232 vec_oprnds->quick_push (vop);
4233 }
4234
4235 voprnds.release ();
4236
4237 /* In case that VF is greater than the unrolling factor needed for the SLP
4238 group of stmts, NUMBER_OF_VECTORS to be created is greater than
4239 NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
4240 to replicate the vectors. */
4241 tree neutral_vec = NULL;
4242 while (number_of_vectors > vec_oprnds->length ())
4243 {
4244 if (neutral_op)
4245 {
4246 if (!neutral_vec)
4247 {
4248 gimple_seq ctor_seq = NULL;
4249 neutral_vec = gimple_build_vector_from_val
4250 (&ctor_seq, vector_type, neutral_op);
4251 if (ctor_seq != NULL)
4252 gsi_insert_seq_on_edge_immediate (pe, ctor_seq);
4253 }
4254 vec_oprnds->quick_push (neutral_vec);
4255 }
4256 else
4257 {
4258 for (i = 0; vec_oprnds->iterate (i, &vop) && i < vec_num; i++)
4259 vec_oprnds->quick_push (vop);
4260 }
4261 }
4262}
4263
4264
4265/* Function vect_create_epilog_for_reduction
4266
4267 Create code at the loop-epilog to finalize the result of a reduction
4268 computation.
4269
4270 VECT_DEFS is list of vector of partial results, i.e., the lhs's of vector
4271 reduction statements.
4272 STMT is the scalar reduction stmt that is being vectorized.
4273 NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
4274 number of elements that we can fit in a vectype (nunits). In this case
4275 we have to generate more than one vector stmt - i.e - we need to "unroll"
4276 the vector stmt by a factor VF/nunits. For more details see documentation
4277 in vectorizable_operation.
4278 REDUC_FN is the internal function for the epilog reduction.
4279 REDUCTION_PHIS is a list of the phi-nodes that carry the reduction
4280 computation.
4281 REDUC_INDEX is the index of the operand in the right hand side of the
4282 statement that is defined by REDUCTION_PHI.
4283 DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
4284 SLP_NODE is an SLP node containing a group of reduction statements. The
4285 first one in this group is STMT.
4286 INDUC_VAL is for INTEGER_INDUC_COND_REDUCTION the value to use for the case
4287 when the COND_EXPR is never true in the loop. For MAX_EXPR, it needs to
4288 be smaller than any value of the IV in the loop, for MIN_EXPR larger than
4289 any value of the IV in the loop.
4290 INDUC_CODE is the code for epilog reduction if INTEGER_INDUC_COND_REDUCTION.
4291
4292 This function:
4293 1. Creates the reduction def-use cycles: sets the arguments for
4294 REDUCTION_PHIS:
4295 The loop-entry argument is the vectorized initial-value of the reduction.
4296 The loop-latch argument is taken from VECT_DEFS - the vector of partial
4297 sums.
4298 2. "Reduces" each vector of partial results VECT_DEFS into a single result,
4299 by calling the function specified by REDUC_FN if available, or by
4300 other means (whole-vector shifts or a scalar loop).
4301 The function also creates a new phi node at the loop exit to preserve
4302 loop-closed form, as illustrated below.
4303
4304 The flow at the entry to this function:
4305
4306 loop:
4307 vec_def = phi <null, null> # REDUCTION_PHI
4308 VECT_DEF = vector_stmt # vectorized form of STMT
4309 s_loop = scalar_stmt # (scalar) STMT
4310 loop_exit:
4311 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4312 use <s_out0>
4313 use <s_out0>
4314
4315 The above is transformed by this function into:
4316
4317 loop:
4318 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
4319 VECT_DEF = vector_stmt # vectorized form of STMT
4320 s_loop = scalar_stmt # (scalar) STMT
4321 loop_exit:
4322 s_out0 = phi <s_loop> # (scalar) EXIT_PHI
4323 v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
4324 v_out2 = reduce <v_out1>
4325 s_out3 = extract_field <v_out2, 0>
4326 s_out4 = adjust_result <s_out3>
4327 use <s_out4>
4328 use <s_out4>
4329*/
4330
4331static void
4332vect_create_epilog_for_reduction (vec<tree> vect_defs, gimple *stmt,
4333 gimple *reduc_def_stmt,
4334 int ncopies, internal_fn reduc_fn,
4335 vec<gimple *> reduction_phis,
4336 bool double_reduc,
4337 slp_tree slp_node,
4338 slp_instance slp_node_instance,
4339 tree induc_val, enum tree_code induc_code)
4340{
4341 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4342 stmt_vec_info prev_phi_info;
4343 tree vectype;
4344 machine_mode mode;
4345 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
4346 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo), *outer_loop = NULL;
4347 basic_block exit_bb;
4348 tree scalar_dest;
4349 tree scalar_type;
4350 gimple *new_phi = NULL, *phi;
4351 gimple_stmt_iterator exit_gsi;
4352 tree vec_dest;
4353 tree new_temp = NULL_TREE, new_dest, new_name, new_scalar_dest;
4354 gimple *epilog_stmt = NULL;
4355 enum tree_code code = gimple_assign_rhs_code (stmt);
4356 gimple *exit_phi;
4357 tree bitsize;
4358 tree adjustment_def = NULL;
4359 tree vec_initial_def = NULL;
4360 tree expr, def, initial_def = NULL;
4361 tree orig_name, scalar_result;
4362 imm_use_iterator imm_iter, phi_imm_iter;
4363 use_operand_p use_p, phi_use_p;
4364 gimple *use_stmt, *orig_stmt, *reduction_phi = NULL;
4365 bool nested_in_vect_loop = false;
4366 auto_vec<gimple *> new_phis;
4367 auto_vec<gimple *> inner_phis;
4368 enum vect_def_type dt = vect_unknown_def_type;
4369 int j, i;
4370 auto_vec<tree> scalar_results;
4371 unsigned int group_size = 1, k, ratio;
4372 auto_vec<tree> vec_initial_defs;
4373 auto_vec<gimple *> phis;
4374 bool slp_reduc = false;
4375 tree new_phi_result;
4376 gimple *inner_phi = NULL;
4377 tree induction_index = NULL_TREE;
4378
4379 if (slp_node)
4380 group_size = SLP_TREE_SCALAR_STMTS (slp_node).length ();
4381
4382 if (nested_in_vect_loop_p (loop, stmt))
4383 {
4384 outer_loop = loop;
4385 loop = loop->inner;
4386 nested_in_vect_loop = true;
4387 gcc_assert (!slp_node);
4388 }
4389
4390 vectype = STMT_VINFO_VECTYPE (stmt_info);
4391 gcc_assert (vectype);
4392 mode = TYPE_MODE (vectype);
4393
4394 /* 1. Create the reduction def-use cycle:
4395 Set the arguments of REDUCTION_PHIS, i.e., transform
4396
4397 loop:
4398 vec_def = phi <null, null> # REDUCTION_PHI
4399 VECT_DEF = vector_stmt # vectorized form of STMT
4400 ...
4401
4402 into:
4403
4404 loop:
4405 vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
4406 VECT_DEF = vector_stmt # vectorized form of STMT
4407 ...
4408
4409 (in case of SLP, do it for all the phis). */
4410
4411 /* Get the loop-entry arguments. */
4412 enum vect_def_type initial_def_dt = vect_unknown_def_type;
4413 if (slp_node)
4414 {
4415 unsigned vec_num = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
4416 vec_initial_defs.reserve (vec_num);
4417 get_initial_defs_for_reduction (slp_node_instance->reduc_phis,
4418 &vec_initial_defs, vec_num, code,
4419 GROUP_FIRST_ELEMENT (stmt_info));
4420 }
4421 else
4422 {
4423 /* Get at the scalar def before the loop, that defines the initial value
4424 of the reduction variable. */
4425 gimple *def_stmt;
4426 initial_def = PHI_ARG_DEF_FROM_EDGE (reduc_def_stmt,
4427 loop_preheader_edge (loop));
4428 /* Optimize: if initial_def is for REDUC_MAX smaller than the base
4429 and we can't use zero for induc_val, use initial_def. Similarly
4430 for REDUC_MIN and initial_def larger than the base. */
4431 if (TREE_CODE (initial_def) == INTEGER_CST
4432 && (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
4433 == INTEGER_INDUC_COND_REDUCTION)
4434 && !integer_zerop (induc_val)
4435 && ((reduc_fn == IFN_REDUC_MAX
4436 && tree_int_cst_lt (initial_def, induc_val))
4437 || (reduc_fn == IFN_REDUC_MIN
4438 && tree_int_cst_lt (induc_val, initial_def))))
4439 induc_val = initial_def;
4440 vect_is_simple_use (initial_def, loop_vinfo, &def_stmt, &initial_def_dt);
4441 vec_initial_def = get_initial_def_for_reduction (stmt, initial_def,
4442 &adjustment_def);
4443 vec_initial_defs.create (1);
4444 vec_initial_defs.quick_push (vec_initial_def);
4445 }
4446
4447 /* Set phi nodes arguments. */
4448 FOR_EACH_VEC_ELT (reduction_phis, i, phi)
4449 {
4450 tree vec_init_def = vec_initial_defs[i];
4451 tree def = vect_defs[i];
4452 for (j = 0; j < ncopies; j++)
4453 {
4454 if (j != 0)
4455 {
4456 phi = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi));
4457 if (nested_in_vect_loop)
4458 vec_init_def
4459 = vect_get_vec_def_for_stmt_copy (initial_def_dt,
4460 vec_init_def);
4461 }
4462
4463 /* Set the loop-entry arg of the reduction-phi. */
4464
4465 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info)
4466 == INTEGER_INDUC_COND_REDUCTION)
4467 {
4468 /* Initialise the reduction phi to zero. This prevents initial
4469 values of non-zero interferring with the reduction op. */
4470 gcc_assert (ncopies == 1);
4471 gcc_assert (i == 0);
4472
4473 tree vec_init_def_type = TREE_TYPE (vec_init_def);
4474 tree induc_val_vec
4475 = build_vector_from_val (vec_init_def_type, induc_val);
4476
4477 add_phi_arg (as_a <gphi *> (phi), induc_val_vec,
4478 loop_preheader_edge (loop), UNKNOWN_LOCATION);
4479 }
4480 else
4481 add_phi_arg (as_a <gphi *> (phi), vec_init_def,
4482 loop_preheader_edge (loop), UNKNOWN_LOCATION);
4483
4484 /* Set the loop-latch arg for the reduction-phi. */
4485 if (j > 0)
4486 def = vect_get_vec_def_for_stmt_copy (vect_unknown_def_type, def);
4487
4488 add_phi_arg (as_a <gphi *> (phi), def, loop_latch_edge (loop),
4489 UNKNOWN_LOCATION);
4490
4491 if (dump_enabled_p ())
4492 {
4493 dump_printf_loc (MSG_NOTE, vect_location,
4494 "transform reduction: created def-use cycle: ");
4495 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0);
4496 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, SSA_NAME_DEF_STMT (def), 0);
4497 }
4498 }
4499 }
4500
4501 /* For cond reductions we want to create a new vector (INDEX_COND_EXPR)
4502 which is updated with the current index of the loop for every match of
4503 the original loop's cond_expr (VEC_STMT). This results in a vector
4504 containing the last time the condition passed for that vector lane.
4505 The first match will be a 1 to allow 0 to be used for non-matching
4506 indexes. If there are no matches at all then the vector will be all
4507 zeroes. */
4508 if (STMT_VINFO_VEC_REDUCTION_TYPE (stmt_info) == COND_REDUCTION)
4509 {
4510 tree indx_before_incr, indx_after_incr;
4511 int nunits_out = TYPE_VECTOR_SUBPARTS (vectype);
4512 int k;
4513
4514 gimple *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
4515 gcc_assert (gimple_assign_rhs_code (vec_stmt) == VEC_COND_EXPR);
4516
4517 int scalar_precision
4518 = GET_MODE_PRECISION (SCALAR_TYPE_MODE (TREE_TYPE (vectype)));
4519 tree cr_index_scalar_type = make_unsigned_type (scalar_precision);
4520 tree cr_index_vector_type = build_vector_type
4521 (cr_index_scalar_type, TYPE_VECTOR_SUBPARTS (vectype));
4522
4523 /* First we create a simple vector induction variable which starts
4524 with the values {1,2,3,...} (SERIES_VECT) and increments by the
4525 vector size (STEP). */
4526
4527 /* Create a {1,2,3,...} vector. */
4528 tree_vector_builder vtemp (cr_index_vector_type, 1, 3);
4529 for (k = 0; k < 3; ++k)
4530 vtemp.quick_push (build_int_cst (cr_index_scalar_type, k + 1));
4531 tree series_vect = vtemp.build ();
4532
4533 /* Create a vector of the step value. */
4534 tree step = build_int_cst (cr_index_scalar_type, nunits_out);
4535 tree vec_step = build_vector_from_val (cr_index_vector_type, step);
4536
4537 /* Create an induction variable. */
4538 gimple_stmt_iterator incr_gsi;
4539 bool insert_after;
4540 standard_iv_increment_position (loop, &incr_gsi, &insert_after);
4541 create_iv (series_vect, vec_step, NULL_TREE, loop, &incr_gsi,
4542 insert_after, &indx_before_incr, &indx_after_incr);
4543
4544 /* Next create a new phi node vector (NEW_PHI_TREE) which