OSDN Git Service

2010-04-09 Richard Guenther <rguenther@suse.de>
[pf3gnuchains/gcc-fork.git] / gcc / tree-vect-loop.c
1 /* Loop Vectorization
2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3    Free Software Foundation, Inc.
4    Contributed by Dorit Naishlos <dorit@il.ibm.com> and
5    Ira Rosen <irar@il.ibm.com>
6
7 This file is part of GCC.
8
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
12 version.
13
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
17 for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3.  If not see
21 <http://www.gnu.org/licenses/>.  */
22
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "ggc.h"
28 #include "tree.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
33 #include "cfgloop.h"
34 #include "cfglayout.h"
35 #include "expr.h"
36 #include "recog.h"
37 #include "optabs.h"
38 #include "params.h"
39 #include "toplev.h"
40 #include "tree-chrec.h"
41 #include "tree-scalar-evolution.h"
42 #include "tree-vectorizer.h"
43
44 /* Loop Vectorization Pass.
45
46    This pass tries to vectorize loops.
47
48    For example, the vectorizer transforms the following simple loop:
49
50         short a[N]; short b[N]; short c[N]; int i;
51
52         for (i=0; i<N; i++){
53           a[i] = b[i] + c[i];
54         }
55
56    as if it was manually vectorized by rewriting the source code into:
57
58         typedef int __attribute__((mode(V8HI))) v8hi;
59         short a[N];  short b[N]; short c[N];   int i;
60         v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
61         v8hi va, vb, vc;
62
63         for (i=0; i<N/8; i++){
64           vb = pb[i];
65           vc = pc[i];
66           va = vb + vc;
67           pa[i] = va;
68         }
69
70         The main entry to this pass is vectorize_loops(), in which
71    the vectorizer applies a set of analyses on a given set of loops,
72    followed by the actual vectorization transformation for the loops that
73    had successfully passed the analysis phase.
74         Throughout this pass we make a distinction between two types of
75    data: scalars (which are represented by SSA_NAMES), and memory references
76    ("data-refs"). These two types of data require different handling both
77    during analysis and transformation. The types of data-refs that the
78    vectorizer currently supports are ARRAY_REFS which base is an array DECL
79    (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
80    accesses are required to have a simple (consecutive) access pattern.
81
82    Analysis phase:
83    ===============
84         The driver for the analysis phase is vect_analyze_loop().
85    It applies a set of analyses, some of which rely on the scalar evolution
86    analyzer (scev) developed by Sebastian Pop.
87
88         During the analysis phase the vectorizer records some information
89    per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
90    loop, as well as general information about the loop as a whole, which is
91    recorded in a "loop_vec_info" struct attached to each loop.
92
93    Transformation phase:
94    =====================
95         The loop transformation phase scans all the stmts in the loop, and
96    creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
97    the loop that needs to be vectorized. It inserts the vector code sequence
98    just before the scalar stmt S, and records a pointer to the vector code
99    in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
100    attached to S). This pointer will be used for the vectorization of following
101    stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
102    otherwise, we rely on dead code elimination for removing it.
103
104         For example, say stmt S1 was vectorized into stmt VS1:
105
106    VS1: vb = px[i];
107    S1:  b = x[i];    STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
108    S2:  a = b;
109
110    To vectorize stmt S2, the vectorizer first finds the stmt that defines
111    the operand 'b' (S1), and gets the relevant vector def 'vb' from the
112    vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
113    resulting sequence would be:
114
115    VS1: vb = px[i];
116    S1:  b = x[i];       STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
117    VS2: va = vb;
118    S2:  a = b;          STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
119
120         Operands that are not SSA_NAMEs, are data-refs that appear in
121    load/store operations (like 'x[i]' in S1), and are handled differently.
122
123    Target modeling:
124    =================
125         Currently the only target specific information that is used is the
126    size of the vector (in bytes) - "UNITS_PER_SIMD_WORD". Targets that can
127    support different sizes of vectors, for now will need to specify one value
128    for "UNITS_PER_SIMD_WORD". More flexibility will be added in the future.
129
130         Since we only vectorize operations which vector form can be
131    expressed using existing tree codes, to verify that an operation is
132    supported, the vectorizer checks the relevant optab at the relevant
133    machine_mode (e.g, optab_handler (add_optab, V8HImode)->insn_code). If
134    the value found is CODE_FOR_nothing, then there's no target support, and
135    we can't vectorize the stmt.
136
137    For additional information on this project see:
138    http://gcc.gnu.org/projects/tree-ssa/vectorization.html
139 */
140
141 /* Function vect_determine_vectorization_factor
142
143    Determine the vectorization factor (VF). VF is the number of data elements
144    that are operated upon in parallel in a single iteration of the vectorized
145    loop. For example, when vectorizing a loop that operates on 4byte elements,
146    on a target with vector size (VS) 16byte, the VF is set to 4, since 4
147    elements can fit in a single vector register.
148
149    We currently support vectorization of loops in which all types operated upon
150    are of the same size. Therefore this function currently sets VF according to
151    the size of the types operated upon, and fails if there are multiple sizes
152    in the loop.
153
154    VF is also the factor by which the loop iterations are strip-mined, e.g.:
155    original loop:
156         for (i=0; i<N; i++){
157           a[i] = b[i] + c[i];
158         }
159
160    vectorized loop:
161         for (i=0; i<N; i+=VF){
162           a[i:VF] = b[i:VF] + c[i:VF];
163         }
164 */
165
166 static bool
167 vect_determine_vectorization_factor (loop_vec_info loop_vinfo)
168 {
169   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
170   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
171   int nbbs = loop->num_nodes;
172   gimple_stmt_iterator si;
173   unsigned int vectorization_factor = 0;
174   tree scalar_type;
175   gimple phi;
176   tree vectype;
177   unsigned int nunits;
178   stmt_vec_info stmt_info;
179   int i;
180   HOST_WIDE_INT dummy;
181
182   if (vect_print_dump_info (REPORT_DETAILS))
183     fprintf (vect_dump, "=== vect_determine_vectorization_factor ===");
184
185   for (i = 0; i < nbbs; i++)
186     {
187       basic_block bb = bbs[i];
188
189       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
190         {
191           phi = gsi_stmt (si);
192           stmt_info = vinfo_for_stmt (phi);
193           if (vect_print_dump_info (REPORT_DETAILS))
194             {
195               fprintf (vect_dump, "==> examining phi: ");
196               print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
197             }
198
199           gcc_assert (stmt_info);
200
201           if (STMT_VINFO_RELEVANT_P (stmt_info))
202             {
203               gcc_assert (!STMT_VINFO_VECTYPE (stmt_info));
204               scalar_type = TREE_TYPE (PHI_RESULT (phi));
205
206               if (vect_print_dump_info (REPORT_DETAILS))
207                 {
208                   fprintf (vect_dump, "get vectype for scalar type:  ");
209                   print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
210                 }
211
212               vectype = get_vectype_for_scalar_type (scalar_type);
213               if (!vectype)
214                 {
215                   if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
216                     {
217                       fprintf (vect_dump,
218                                "not vectorized: unsupported data-type ");
219                       print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
220                     }
221                   return false;
222                 }
223               STMT_VINFO_VECTYPE (stmt_info) = vectype;
224
225               if (vect_print_dump_info (REPORT_DETAILS))
226                 {
227                   fprintf (vect_dump, "vectype: ");
228                   print_generic_expr (vect_dump, vectype, TDF_SLIM);
229                 }
230
231               nunits = TYPE_VECTOR_SUBPARTS (vectype);
232               if (vect_print_dump_info (REPORT_DETAILS))
233                 fprintf (vect_dump, "nunits = %d", nunits);
234
235               if (!vectorization_factor
236                   || (nunits > vectorization_factor))
237                 vectorization_factor = nunits;
238             }
239         }
240
241       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
242         {
243           tree vf_vectype;
244           gimple stmt = gsi_stmt (si);
245           stmt_info = vinfo_for_stmt (stmt);
246
247           if (vect_print_dump_info (REPORT_DETAILS))
248             {
249               fprintf (vect_dump, "==> examining statement: ");
250               print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
251             }
252
253           gcc_assert (stmt_info);
254
255           /* skip stmts which do not need to be vectorized.  */
256           if (!STMT_VINFO_RELEVANT_P (stmt_info)
257               && !STMT_VINFO_LIVE_P (stmt_info))
258             {
259               if (vect_print_dump_info (REPORT_DETAILS))
260                 fprintf (vect_dump, "skip.");
261               continue;
262             }
263
264           if (gimple_get_lhs (stmt) == NULL_TREE)
265             {
266               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
267                 {
268                   fprintf (vect_dump, "not vectorized: irregular stmt.");
269                   print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
270                 }
271               return false;
272             }
273
274           if (VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt))))
275             {
276               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
277                 {
278                   fprintf (vect_dump, "not vectorized: vector stmt in loop:");
279                   print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
280                 }
281               return false;
282             }
283
284           if (STMT_VINFO_VECTYPE (stmt_info))
285             {
286               /* The only case when a vectype had been already set is for stmts
287                  that contain a dataref, or for "pattern-stmts" (stmts generated
288                  by the vectorizer to represent/replace a certain idiom).  */
289               gcc_assert (STMT_VINFO_DATA_REF (stmt_info)
290                           || is_pattern_stmt_p (stmt_info));
291               vectype = STMT_VINFO_VECTYPE (stmt_info);
292             }
293           else
294             {
295               gcc_assert (!STMT_VINFO_DATA_REF (stmt_info)
296                           && !is_pattern_stmt_p (stmt_info));
297
298               scalar_type = TREE_TYPE (gimple_get_lhs (stmt));
299               if (vect_print_dump_info (REPORT_DETAILS))
300                 {
301                   fprintf (vect_dump, "get vectype for scalar type:  ");
302                   print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
303                 }
304               vectype = get_vectype_for_scalar_type (scalar_type);
305               if (!vectype)
306                 {
307                   if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
308                     {
309                       fprintf (vect_dump,
310                                "not vectorized: unsupported data-type ");
311                       print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
312                     }
313                   return false;
314                 }
315
316               STMT_VINFO_VECTYPE (stmt_info) = vectype;
317             }
318
319           /* The vectorization factor is according to the smallest
320              scalar type (or the largest vector size, but we only
321              support one vector size per loop).  */
322           scalar_type = vect_get_smallest_scalar_type (stmt, &dummy,
323                                                        &dummy);
324           if (vect_print_dump_info (REPORT_DETAILS))
325             {
326               fprintf (vect_dump, "get vectype for scalar type:  ");
327               print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
328             }
329           vf_vectype = get_vectype_for_scalar_type (scalar_type);
330           if (!vf_vectype)
331             {
332               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
333                 {
334                   fprintf (vect_dump,
335                            "not vectorized: unsupported data-type ");
336                   print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
337                 }
338               return false;
339             }
340
341           if ((GET_MODE_SIZE (TYPE_MODE (vectype))
342                != GET_MODE_SIZE (TYPE_MODE (vf_vectype))))
343             {
344               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
345                 {
346                   fprintf (vect_dump,
347                            "not vectorized: different sized vector "
348                            "types in statement, ");
349                   print_generic_expr (vect_dump, vectype, TDF_SLIM);
350                   fprintf (vect_dump, " and ");
351                   print_generic_expr (vect_dump, vf_vectype, TDF_SLIM);
352                 }
353               return false;
354             }
355
356           if (vect_print_dump_info (REPORT_DETAILS))
357             {
358               fprintf (vect_dump, "vectype: ");
359               print_generic_expr (vect_dump, vf_vectype, TDF_SLIM);
360             }
361
362           nunits = TYPE_VECTOR_SUBPARTS (vf_vectype);
363           if (vect_print_dump_info (REPORT_DETAILS))
364             fprintf (vect_dump, "nunits = %d", nunits);
365
366           if (!vectorization_factor
367               || (nunits > vectorization_factor))
368             vectorization_factor = nunits;
369         }
370     }
371
372   /* TODO: Analyze cost. Decide if worth while to vectorize.  */
373   if (vect_print_dump_info (REPORT_DETAILS))
374     fprintf (vect_dump, "vectorization factor = %d", vectorization_factor);
375   if (vectorization_factor <= 1)
376     {
377       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
378         fprintf (vect_dump, "not vectorized: unsupported data-type");
379       return false;
380     }
381   LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
382
383   return true;
384 }
385
386
387 /* Function vect_is_simple_iv_evolution.
388
389    FORNOW: A simple evolution of an induction variables in the loop is
390    considered a polynomial evolution with constant step.  */
391
392 static bool
393 vect_is_simple_iv_evolution (unsigned loop_nb, tree access_fn, tree * init,
394                              tree * step)
395 {
396   tree init_expr;
397   tree step_expr;
398   tree evolution_part = evolution_part_in_loop_num (access_fn, loop_nb);
399
400   /* When there is no evolution in this loop, the evolution function
401      is not "simple".  */
402   if (evolution_part == NULL_TREE)
403     return false;
404
405   /* When the evolution is a polynomial of degree >= 2
406      the evolution function is not "simple".  */
407   if (tree_is_chrec (evolution_part))
408     return false;
409
410   step_expr = evolution_part;
411   init_expr = unshare_expr (initial_condition_in_loop_num (access_fn, loop_nb));
412
413   if (vect_print_dump_info (REPORT_DETAILS))
414     {
415       fprintf (vect_dump, "step: ");
416       print_generic_expr (vect_dump, step_expr, TDF_SLIM);
417       fprintf (vect_dump, ",  init: ");
418       print_generic_expr (vect_dump, init_expr, TDF_SLIM);
419     }
420
421   *init = init_expr;
422   *step = step_expr;
423
424   if (TREE_CODE (step_expr) != INTEGER_CST)
425     {
426       if (vect_print_dump_info (REPORT_DETAILS))
427         fprintf (vect_dump, "step unknown.");
428       return false;
429     }
430
431   return true;
432 }
433
434 /* Function vect_analyze_scalar_cycles_1.
435
436    Examine the cross iteration def-use cycles of scalar variables
437    in LOOP. LOOP_VINFO represents the loop that is now being
438    considered for vectorization (can be LOOP, or an outer-loop
439    enclosing LOOP).  */
440
441 static void
442 vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo, struct loop *loop)
443 {
444   basic_block bb = loop->header;
445   tree dumy;
446   VEC(gimple,heap) *worklist = VEC_alloc (gimple, heap, 64);
447   gimple_stmt_iterator gsi;
448   bool double_reduc;
449
450   if (vect_print_dump_info (REPORT_DETAILS))
451     fprintf (vect_dump, "=== vect_analyze_scalar_cycles ===");
452
453   /* First - identify all inductions. Reduction detection assumes that all the
454      inductions have been identified, therefore, this order must not be
455      changed.  */
456   for (gsi = gsi_start_phis  (bb); !gsi_end_p (gsi); gsi_next (&gsi))
457     {
458       gimple phi = gsi_stmt (gsi);
459       tree access_fn = NULL;
460       tree def = PHI_RESULT (phi);
461       stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
462
463       if (vect_print_dump_info (REPORT_DETAILS))
464         {
465           fprintf (vect_dump, "Analyze phi: ");
466           print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
467         }
468
469       /* Skip virtual phi's. The data dependences that are associated with
470          virtual defs/uses (i.e., memory accesses) are analyzed elsewhere.  */
471       if (!is_gimple_reg (SSA_NAME_VAR (def)))
472         continue;
473
474       STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_unknown_def_type;
475
476       /* Analyze the evolution function.  */
477       access_fn = analyze_scalar_evolution (loop, def);
478       if (access_fn && vect_print_dump_info (REPORT_DETAILS))
479         {
480           fprintf (vect_dump, "Access function of PHI: ");
481           print_generic_expr (vect_dump, access_fn, TDF_SLIM);
482         }
483
484       if (!access_fn
485           || !vect_is_simple_iv_evolution (loop->num, access_fn, &dumy, &dumy))
486         {
487           VEC_safe_push (gimple, heap, worklist, phi);
488           continue;
489         }
490
491       if (vect_print_dump_info (REPORT_DETAILS))
492         fprintf (vect_dump, "Detected induction.");
493       STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def;
494     }
495
496
497   /* Second - identify all reductions and nested cycles.  */
498   while (VEC_length (gimple, worklist) > 0)
499     {
500       gimple phi = VEC_pop (gimple, worklist);
501       tree def = PHI_RESULT (phi);
502       stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
503       gimple reduc_stmt;
504       bool nested_cycle;
505
506       if (vect_print_dump_info (REPORT_DETAILS))
507         {
508           fprintf (vect_dump, "Analyze phi: ");
509           print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
510         }
511
512       gcc_assert (is_gimple_reg (SSA_NAME_VAR (def)));
513       gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_unknown_def_type);
514
515       nested_cycle = (loop != LOOP_VINFO_LOOP (loop_vinfo));
516       reduc_stmt = vect_is_simple_reduction (loop_vinfo, phi, !nested_cycle,
517                                              &double_reduc);
518       if (reduc_stmt)
519         {
520           if (double_reduc)
521             {
522               if (vect_print_dump_info (REPORT_DETAILS))
523                 fprintf (vect_dump, "Detected double reduction.");
524
525               STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_double_reduction_def;
526               STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
527                                                     vect_double_reduction_def;
528             }
529           else
530             {
531               if (nested_cycle)
532                 {
533                   if (vect_print_dump_info (REPORT_DETAILS))
534                     fprintf (vect_dump, "Detected vectorizable nested cycle.");
535
536                   STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_nested_cycle;
537                   STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
538                                                              vect_nested_cycle;
539                 }
540               else
541                 {
542                   if (vect_print_dump_info (REPORT_DETAILS))
543                     fprintf (vect_dump, "Detected reduction.");
544
545                   STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_reduction_def;
546                   STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
547                                                            vect_reduction_def;
548                 }
549             }
550         }
551       else
552         if (vect_print_dump_info (REPORT_DETAILS))
553           fprintf (vect_dump, "Unknown def-use cycle pattern.");
554     }
555
556   VEC_free (gimple, heap, worklist);
557 }
558
559
560 /* Function vect_analyze_scalar_cycles.
561
562    Examine the cross iteration def-use cycles of scalar variables, by
563    analyzing the loop-header PHIs of scalar variables; Classify each
564    cycle as one of the following: invariant, induction, reduction, unknown.
565    We do that for the loop represented by LOOP_VINFO, and also to its
566    inner-loop, if exists.
567    Examples for scalar cycles:
568
569    Example1: reduction:
570
571               loop1:
572               for (i=0; i<N; i++)
573                  sum += a[i];
574
575    Example2: induction:
576
577               loop2:
578               for (i=0; i<N; i++)
579                  a[i] = i;  */
580
581 static void
582 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
583 {
584   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
585
586   vect_analyze_scalar_cycles_1 (loop_vinfo, loop);
587
588   /* When vectorizing an outer-loop, the inner-loop is executed sequentially.
589      Reductions in such inner-loop therefore have different properties than
590      the reductions in the nest that gets vectorized:
591      1. When vectorized, they are executed in the same order as in the original
592         scalar loop, so we can't change the order of computation when
593         vectorizing them.
594      2. FIXME: Inner-loop reductions can be used in the inner-loop, so the
595         current checks are too strict.  */
596
597   if (loop->inner)
598     vect_analyze_scalar_cycles_1 (loop_vinfo, loop->inner);
599 }
600
601 /* Function vect_get_loop_niters.
602
603    Determine how many iterations the loop is executed.
604    If an expression that represents the number of iterations
605    can be constructed, place it in NUMBER_OF_ITERATIONS.
606    Return the loop exit condition.  */
607
608 static gimple
609 vect_get_loop_niters (struct loop *loop, tree *number_of_iterations)
610 {
611   tree niters;
612
613   if (vect_print_dump_info (REPORT_DETAILS))
614     fprintf (vect_dump, "=== get_loop_niters ===");
615
616   niters = number_of_exit_cond_executions (loop);
617
618   if (niters != NULL_TREE
619       && niters != chrec_dont_know)
620     {
621       *number_of_iterations = niters;
622
623       if (vect_print_dump_info (REPORT_DETAILS))
624         {
625           fprintf (vect_dump, "==> get_loop_niters:" );
626           print_generic_expr (vect_dump, *number_of_iterations, TDF_SLIM);
627         }
628     }
629
630   return get_loop_exit_condition (loop);
631 }
632
633
634 /* Function bb_in_loop_p
635
636    Used as predicate for dfs order traversal of the loop bbs.  */
637
638 static bool
639 bb_in_loop_p (const_basic_block bb, const void *data)
640 {
641   const struct loop *const loop = (const struct loop *)data;
642   if (flow_bb_inside_loop_p (loop, bb))
643     return true;
644   return false;
645 }
646
647
648 /* Function new_loop_vec_info.
649
650    Create and initialize a new loop_vec_info struct for LOOP, as well as
651    stmt_vec_info structs for all the stmts in LOOP.  */
652
653 static loop_vec_info
654 new_loop_vec_info (struct loop *loop)
655 {
656   loop_vec_info res;
657   basic_block *bbs;
658   gimple_stmt_iterator si;
659   unsigned int i, nbbs;
660
661   res = (loop_vec_info) xcalloc (1, sizeof (struct _loop_vec_info));
662   LOOP_VINFO_LOOP (res) = loop;
663
664   bbs = get_loop_body (loop);
665
666   /* Create/Update stmt_info for all stmts in the loop.  */
667   for (i = 0; i < loop->num_nodes; i++)
668     {
669       basic_block bb = bbs[i];
670
671       /* BBs in a nested inner-loop will have been already processed (because
672          we will have called vect_analyze_loop_form for any nested inner-loop).
673          Therefore, for stmts in an inner-loop we just want to update the
674          STMT_VINFO_LOOP_VINFO field of their stmt_info to point to the new
675          loop_info of the outer-loop we are currently considering to vectorize
676          (instead of the loop_info of the inner-loop).
677          For stmts in other BBs we need to create a stmt_info from scratch.  */
678       if (bb->loop_father != loop)
679         {
680           /* Inner-loop bb.  */
681           gcc_assert (loop->inner && bb->loop_father == loop->inner);
682           for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
683             {
684               gimple phi = gsi_stmt (si);
685               stmt_vec_info stmt_info = vinfo_for_stmt (phi);
686               loop_vec_info inner_loop_vinfo =
687                 STMT_VINFO_LOOP_VINFO (stmt_info);
688               gcc_assert (loop->inner == LOOP_VINFO_LOOP (inner_loop_vinfo));
689               STMT_VINFO_LOOP_VINFO (stmt_info) = res;
690             }
691           for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
692            {
693               gimple stmt = gsi_stmt (si);
694               stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
695               loop_vec_info inner_loop_vinfo =
696                  STMT_VINFO_LOOP_VINFO (stmt_info);
697               gcc_assert (loop->inner == LOOP_VINFO_LOOP (inner_loop_vinfo));
698               STMT_VINFO_LOOP_VINFO (stmt_info) = res;
699            }
700         }
701       else
702         {
703           /* bb in current nest.  */
704           for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
705             {
706               gimple phi = gsi_stmt (si);
707               gimple_set_uid (phi, 0);
708               set_vinfo_for_stmt (phi, new_stmt_vec_info (phi, res, NULL));
709             }
710
711           for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
712             {
713               gimple stmt = gsi_stmt (si);
714               gimple_set_uid (stmt, 0);
715               set_vinfo_for_stmt (stmt, new_stmt_vec_info (stmt, res, NULL));
716             }
717         }
718     }
719
720   /* CHECKME: We want to visit all BBs before their successors (except for
721      latch blocks, for which this assertion wouldn't hold).  In the simple
722      case of the loop forms we allow, a dfs order of the BBs would the same
723      as reversed postorder traversal, so we are safe.  */
724
725    free (bbs);
726    bbs = XCNEWVEC (basic_block, loop->num_nodes);
727    nbbs = dfs_enumerate_from (loop->header, 0, bb_in_loop_p,
728                               bbs, loop->num_nodes, loop);
729    gcc_assert (nbbs == loop->num_nodes);
730
731   LOOP_VINFO_BBS (res) = bbs;
732   LOOP_VINFO_NITERS (res) = NULL;
733   LOOP_VINFO_NITERS_UNCHANGED (res) = NULL;
734   LOOP_VINFO_COST_MODEL_MIN_ITERS (res) = 0;
735   LOOP_VINFO_VECTORIZABLE_P (res) = 0;
736   LOOP_PEELING_FOR_ALIGNMENT (res) = 0;
737   LOOP_VINFO_VECT_FACTOR (res) = 0;
738   LOOP_VINFO_DATAREFS (res) = VEC_alloc (data_reference_p, heap, 10);
739   LOOP_VINFO_DDRS (res) = VEC_alloc (ddr_p, heap, 10 * 10);
740   LOOP_VINFO_UNALIGNED_DR (res) = NULL;
741   LOOP_VINFO_MAY_MISALIGN_STMTS (res) =
742     VEC_alloc (gimple, heap,
743                PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS));
744   LOOP_VINFO_MAY_ALIAS_DDRS (res) =
745     VEC_alloc (ddr_p, heap,
746                PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS));
747   LOOP_VINFO_STRIDED_STORES (res) = VEC_alloc (gimple, heap, 10);
748   LOOP_VINFO_SLP_INSTANCES (res) = VEC_alloc (slp_instance, heap, 10);
749   LOOP_VINFO_SLP_UNROLLING_FACTOR (res) = 1;
750
751   return res;
752 }
753
754
755 /* Function destroy_loop_vec_info.
756
757    Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
758    stmts in the loop.  */
759
760 void
761 destroy_loop_vec_info (loop_vec_info loop_vinfo, bool clean_stmts)
762 {
763   struct loop *loop;
764   basic_block *bbs;
765   int nbbs;
766   gimple_stmt_iterator si;
767   int j;
768   VEC (slp_instance, heap) *slp_instances;
769   slp_instance instance;
770
771   if (!loop_vinfo)
772     return;
773
774   loop = LOOP_VINFO_LOOP (loop_vinfo);
775
776   bbs = LOOP_VINFO_BBS (loop_vinfo);
777   nbbs = loop->num_nodes;
778
779   if (!clean_stmts)
780     {
781       free (LOOP_VINFO_BBS (loop_vinfo));
782       free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo));
783       free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo));
784       VEC_free (gimple, heap, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
785
786       free (loop_vinfo);
787       loop->aux = NULL;
788       return;
789     }
790
791   for (j = 0; j < nbbs; j++)
792     {
793       basic_block bb = bbs[j];
794       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
795         free_stmt_vec_info (gsi_stmt (si));
796
797       for (si = gsi_start_bb (bb); !gsi_end_p (si); )
798         {
799           gimple stmt = gsi_stmt (si);
800           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
801
802           if (stmt_info)
803             {
804               /* Check if this is a "pattern stmt" (introduced by the
805                  vectorizer during the pattern recognition pass).  */
806               bool remove_stmt_p = false;
807               gimple orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
808               if (orig_stmt)
809                 {
810                   stmt_vec_info orig_stmt_info = vinfo_for_stmt (orig_stmt);
811                   if (orig_stmt_info
812                       && STMT_VINFO_IN_PATTERN_P (orig_stmt_info))
813                     remove_stmt_p = true;
814                 }
815
816               /* Free stmt_vec_info.  */
817               free_stmt_vec_info (stmt);
818
819               /* Remove dead "pattern stmts".  */
820               if (remove_stmt_p)
821                 gsi_remove (&si, true);
822             }
823           gsi_next (&si);
824         }
825     }
826
827   free (LOOP_VINFO_BBS (loop_vinfo));
828   free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo));
829   free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo));
830   VEC_free (gimple, heap, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
831   VEC_free (ddr_p, heap, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo));
832   slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
833   for (j = 0; VEC_iterate (slp_instance, slp_instances, j, instance); j++)
834     vect_free_slp_instance (instance);
835
836   VEC_free (slp_instance, heap, LOOP_VINFO_SLP_INSTANCES (loop_vinfo));
837   VEC_free (gimple, heap, LOOP_VINFO_STRIDED_STORES (loop_vinfo));
838
839   free (loop_vinfo);
840   loop->aux = NULL;
841 }
842
843
844 /* Function vect_analyze_loop_1.
845
846    Apply a set of analyses on LOOP, and create a loop_vec_info struct
847    for it. The different analyses will record information in the
848    loop_vec_info struct.  This is a subset of the analyses applied in
849    vect_analyze_loop, to be applied on an inner-loop nested in the loop
850    that is now considered for (outer-loop) vectorization.  */
851
852 static loop_vec_info
853 vect_analyze_loop_1 (struct loop *loop)
854 {
855   loop_vec_info loop_vinfo;
856
857   if (vect_print_dump_info (REPORT_DETAILS))
858     fprintf (vect_dump, "===== analyze_loop_nest_1 =====");
859
860   /* Check the CFG characteristics of the loop (nesting, entry/exit, etc.  */
861
862   loop_vinfo = vect_analyze_loop_form (loop);
863   if (!loop_vinfo)
864     {
865       if (vect_print_dump_info (REPORT_DETAILS))
866         fprintf (vect_dump, "bad inner-loop form.");
867       return NULL;
868     }
869
870   return loop_vinfo;
871 }
872
873
874 /* Function vect_analyze_loop_form.
875
876    Verify that certain CFG restrictions hold, including:
877    - the loop has a pre-header
878    - the loop has a single entry and exit
879    - the loop exit condition is simple enough, and the number of iterations
880      can be analyzed (a countable loop).  */
881
882 loop_vec_info
883 vect_analyze_loop_form (struct loop *loop)
884 {
885   loop_vec_info loop_vinfo;
886   gimple loop_cond;
887   tree number_of_iterations = NULL;
888   loop_vec_info inner_loop_vinfo = NULL;
889
890   if (vect_print_dump_info (REPORT_DETAILS))
891     fprintf (vect_dump, "=== vect_analyze_loop_form ===");
892
893   /* Different restrictions apply when we are considering an inner-most loop,
894      vs. an outer (nested) loop.
895      (FORNOW. May want to relax some of these restrictions in the future).  */
896
897   if (!loop->inner)
898     {
899       /* Inner-most loop.  We currently require that the number of BBs is
900          exactly 2 (the header and latch).  Vectorizable inner-most loops
901          look like this:
902
903                         (pre-header)
904                            |
905                           header <--------+
906                            | |            |
907                            | +--> latch --+
908                            |
909                         (exit-bb)  */
910
911       if (loop->num_nodes != 2)
912         {
913           if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
914             fprintf (vect_dump, "not vectorized: control flow in loop.");
915           return NULL;
916         }
917
918       if (empty_block_p (loop->header))
919     {
920           if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
921             fprintf (vect_dump, "not vectorized: empty loop.");
922       return NULL;
923     }
924     }
925   else
926     {
927       struct loop *innerloop = loop->inner;
928       edge entryedge;
929
930       /* Nested loop. We currently require that the loop is doubly-nested,
931          contains a single inner loop, and the number of BBs is exactly 5.
932          Vectorizable outer-loops look like this:
933
934                         (pre-header)
935                            |
936                           header <---+
937                            |         |
938                           inner-loop |
939                            |         |
940                           tail ------+
941                            |
942                         (exit-bb)
943
944          The inner-loop has the properties expected of inner-most loops
945          as described above.  */
946
947       if ((loop->inner)->inner || (loop->inner)->next)
948         {
949           if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
950             fprintf (vect_dump, "not vectorized: multiple nested loops.");
951           return NULL;
952         }
953
954       /* Analyze the inner-loop.  */
955       inner_loop_vinfo = vect_analyze_loop_1 (loop->inner);
956       if (!inner_loop_vinfo)
957         {
958           if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
959             fprintf (vect_dump, "not vectorized: Bad inner loop.");
960           return NULL;
961         }
962
963       if (!expr_invariant_in_loop_p (loop,
964                                         LOOP_VINFO_NITERS (inner_loop_vinfo)))
965         {
966           if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
967             fprintf (vect_dump,
968                      "not vectorized: inner-loop count not invariant.");
969           destroy_loop_vec_info (inner_loop_vinfo, true);
970           return NULL;
971         }
972
973       if (loop->num_nodes != 5)
974         {
975           if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
976             fprintf (vect_dump, "not vectorized: control flow in loop.");
977           destroy_loop_vec_info (inner_loop_vinfo, true);
978           return NULL;
979         }
980
981       gcc_assert (EDGE_COUNT (innerloop->header->preds) == 2);
982       entryedge = EDGE_PRED (innerloop->header, 0);
983       if (EDGE_PRED (innerloop->header, 0)->src == innerloop->latch)
984         entryedge = EDGE_PRED (innerloop->header, 1);
985
986       if (entryedge->src != loop->header
987           || !single_exit (innerloop)
988           || single_exit (innerloop)->dest !=  EDGE_PRED (loop->latch, 0)->src)
989         {
990           if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
991             fprintf (vect_dump, "not vectorized: unsupported outerloop form.");
992           destroy_loop_vec_info (inner_loop_vinfo, true);
993           return NULL;
994         }
995
996       if (vect_print_dump_info (REPORT_DETAILS))
997         fprintf (vect_dump, "Considering outer-loop vectorization.");
998     }
999
1000   if (!single_exit (loop)
1001       || EDGE_COUNT (loop->header->preds) != 2)
1002     {
1003       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1004         {
1005           if (!single_exit (loop))
1006             fprintf (vect_dump, "not vectorized: multiple exits.");
1007           else if (EDGE_COUNT (loop->header->preds) != 2)
1008             fprintf (vect_dump, "not vectorized: too many incoming edges.");
1009         }
1010       if (inner_loop_vinfo)
1011         destroy_loop_vec_info (inner_loop_vinfo, true);
1012       return NULL;
1013     }
1014
1015   /* We assume that the loop exit condition is at the end of the loop. i.e,
1016      that the loop is represented as a do-while (with a proper if-guard
1017      before the loop if needed), where the loop header contains all the
1018      executable statements, and the latch is empty.  */
1019   if (!empty_block_p (loop->latch)
1020         || !gimple_seq_empty_p (phi_nodes (loop->latch)))
1021     {
1022       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1023         fprintf (vect_dump, "not vectorized: unexpected loop form.");
1024       if (inner_loop_vinfo)
1025         destroy_loop_vec_info (inner_loop_vinfo, true);
1026       return NULL;
1027     }
1028
1029   /* Make sure there exists a single-predecessor exit bb:  */
1030   if (!single_pred_p (single_exit (loop)->dest))
1031     {
1032       edge e = single_exit (loop);
1033       if (!(e->flags & EDGE_ABNORMAL))
1034         {
1035           split_loop_exit_edge (e);
1036           if (vect_print_dump_info (REPORT_DETAILS))
1037             fprintf (vect_dump, "split exit edge.");
1038         }
1039       else
1040         {
1041           if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1042             fprintf (vect_dump, "not vectorized: abnormal loop exit edge.");
1043           if (inner_loop_vinfo)
1044             destroy_loop_vec_info (inner_loop_vinfo, true);
1045           return NULL;
1046         }
1047     }
1048
1049   loop_cond = vect_get_loop_niters (loop, &number_of_iterations);
1050   if (!loop_cond)
1051     {
1052       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1053         fprintf (vect_dump, "not vectorized: complicated exit condition.");
1054       if (inner_loop_vinfo)
1055         destroy_loop_vec_info (inner_loop_vinfo, true);
1056       return NULL;
1057     }
1058
1059   if (!number_of_iterations)
1060     {
1061       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1062         fprintf (vect_dump,
1063                  "not vectorized: number of iterations cannot be computed.");
1064       if (inner_loop_vinfo)
1065         destroy_loop_vec_info (inner_loop_vinfo, true);
1066       return NULL;
1067     }
1068
1069   if (chrec_contains_undetermined (number_of_iterations))
1070     {
1071       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1072         fprintf (vect_dump, "Infinite number of iterations.");
1073       if (inner_loop_vinfo)
1074         destroy_loop_vec_info (inner_loop_vinfo, true);
1075       return NULL;
1076     }
1077
1078   if (!NITERS_KNOWN_P (number_of_iterations))
1079     {
1080       if (vect_print_dump_info (REPORT_DETAILS))
1081         {
1082           fprintf (vect_dump, "Symbolic number of iterations is ");
1083           print_generic_expr (vect_dump, number_of_iterations, TDF_DETAILS);
1084         }
1085     }
1086   else if (TREE_INT_CST_LOW (number_of_iterations) == 0)
1087     {
1088       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1089         fprintf (vect_dump, "not vectorized: number of iterations = 0.");
1090       if (inner_loop_vinfo)
1091         destroy_loop_vec_info (inner_loop_vinfo, false);
1092       return NULL;
1093     }
1094
1095   loop_vinfo = new_loop_vec_info (loop);
1096   LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
1097   LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo) = number_of_iterations;
1098
1099   STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond)) = loop_exit_ctrl_vec_info_type;
1100
1101   /* CHECKME: May want to keep it around it in the future.  */
1102   if (inner_loop_vinfo)
1103     destroy_loop_vec_info (inner_loop_vinfo, false);
1104
1105   gcc_assert (!loop->aux);
1106   loop->aux = loop_vinfo;
1107   return loop_vinfo;
1108 }
1109
1110
1111 /* Function vect_analyze_loop_operations.
1112
1113    Scan the loop stmts and make sure they are all vectorizable.  */
1114
1115 static bool
1116 vect_analyze_loop_operations (loop_vec_info loop_vinfo)
1117 {
1118   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1119   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1120   int nbbs = loop->num_nodes;
1121   gimple_stmt_iterator si;
1122   unsigned int vectorization_factor = 0;
1123   int i;
1124   gimple phi;
1125   stmt_vec_info stmt_info;
1126   bool need_to_vectorize = false;
1127   int min_profitable_iters;
1128   int min_scalar_loop_bound;
1129   unsigned int th;
1130   bool only_slp_in_loop = true, ok;
1131
1132   if (vect_print_dump_info (REPORT_DETAILS))
1133     fprintf (vect_dump, "=== vect_analyze_loop_operations ===");
1134
1135   gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo));
1136   vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1137
1138   for (i = 0; i < nbbs; i++)
1139     {
1140       basic_block bb = bbs[i];
1141
1142       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
1143         {
1144           phi = gsi_stmt (si);
1145           ok = true;
1146
1147           stmt_info = vinfo_for_stmt (phi);
1148           if (vect_print_dump_info (REPORT_DETAILS))
1149             {
1150               fprintf (vect_dump, "examining phi: ");
1151               print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
1152             }
1153
1154           if (! is_loop_header_bb_p (bb))
1155             {
1156               /* inner-loop loop-closed exit phi in outer-loop vectorization
1157                  (i.e. a phi in the tail of the outer-loop).
1158                  FORNOW: we currently don't support the case that these phis
1159                  are not used in the outerloop (unless it is double reduction,
1160                  i.e., this phi is vect_reduction_def), cause this case
1161                  requires to actually do something here.  */
1162               if ((!STMT_VINFO_RELEVANT_P (stmt_info)
1163                    || STMT_VINFO_LIVE_P (stmt_info))
1164                   && STMT_VINFO_DEF_TYPE (stmt_info)
1165                      != vect_double_reduction_def)
1166                 {
1167                   if (vect_print_dump_info (REPORT_DETAILS))
1168                     fprintf (vect_dump,
1169                              "Unsupported loop-closed phi in outer-loop.");
1170                   return false;
1171                 }
1172               continue;
1173             }
1174
1175           gcc_assert (stmt_info);
1176
1177           if (STMT_VINFO_LIVE_P (stmt_info))
1178             {
1179               /* FORNOW: not yet supported.  */
1180               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1181                 fprintf (vect_dump, "not vectorized: value used after loop.");
1182               return false;
1183             }
1184
1185           if (STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_scope
1186               && STMT_VINFO_DEF_TYPE (stmt_info) != vect_induction_def)
1187             {
1188               /* A scalar-dependence cycle that we don't support.  */
1189               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1190                 fprintf (vect_dump, "not vectorized: scalar dependence cycle.");
1191               return false;
1192             }
1193
1194           if (STMT_VINFO_RELEVANT_P (stmt_info))
1195             {
1196               need_to_vectorize = true;
1197               if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def)
1198                 ok = vectorizable_induction (phi, NULL, NULL);
1199             }
1200
1201           if (!ok)
1202             {
1203               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1204                 {
1205                   fprintf (vect_dump,
1206                            "not vectorized: relevant phi not supported: ");
1207                   print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
1208                 }
1209               return false;
1210             }
1211         }
1212
1213       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1214         {
1215           gimple stmt = gsi_stmt (si);
1216           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1217
1218           gcc_assert (stmt_info);
1219
1220           if (!vect_analyze_stmt (stmt, &need_to_vectorize, NULL))
1221             return false;
1222
1223           if ((STMT_VINFO_RELEVANT_P (stmt_info)
1224                || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_info)))
1225               && !PURE_SLP_STMT (stmt_info))
1226
1227             /* STMT needs both SLP and loop-based vectorization.  */
1228             only_slp_in_loop = false;
1229         }
1230     } /* bbs */
1231
1232   /* All operations in the loop are either irrelevant (deal with loop
1233      control, or dead), or only used outside the loop and can be moved
1234      out of the loop (e.g. invariants, inductions).  The loop can be
1235      optimized away by scalar optimizations.  We're better off not
1236      touching this loop.  */
1237   if (!need_to_vectorize)
1238     {
1239       if (vect_print_dump_info (REPORT_DETAILS))
1240         fprintf (vect_dump,
1241                  "All the computation can be taken out of the loop.");
1242       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1243         fprintf (vect_dump,
1244                  "not vectorized: redundant loop. no profit to vectorize.");
1245       return false;
1246     }
1247
1248   /* If all the stmts in the loop can be SLPed, we perform only SLP, and
1249      vectorization factor of the loop is the unrolling factor required by the
1250      SLP instances.  If that unrolling factor is 1, we say, that we perform
1251      pure SLP on loop - cross iteration parallelism is not exploited.  */
1252   if (only_slp_in_loop)
1253     vectorization_factor = LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo);
1254   else
1255     vectorization_factor = least_common_multiple (vectorization_factor,
1256                                 LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo));
1257
1258   LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
1259
1260   if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1261       && vect_print_dump_info (REPORT_DETAILS))
1262     fprintf (vect_dump,
1263         "vectorization_factor = %d, niters = " HOST_WIDE_INT_PRINT_DEC,
1264         vectorization_factor, LOOP_VINFO_INT_NITERS (loop_vinfo));
1265
1266   if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1267       && (LOOP_VINFO_INT_NITERS (loop_vinfo) < vectorization_factor))
1268     {
1269       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1270         fprintf (vect_dump, "not vectorized: iteration count too small.");
1271       if (vect_print_dump_info (REPORT_DETAILS))
1272         fprintf (vect_dump,"not vectorized: iteration count smaller than "
1273                  "vectorization factor.");
1274       return false;
1275     }
1276
1277   /* Analyze cost. Decide if worth while to vectorize.  */
1278
1279   /* Once VF is set, SLP costs should be updated since the number of created
1280      vector stmts depends on VF.  */
1281   vect_update_slp_costs_according_to_vf (loop_vinfo);
1282
1283   min_profitable_iters = vect_estimate_min_profitable_iters (loop_vinfo);
1284   LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo) = min_profitable_iters;
1285
1286   if (min_profitable_iters < 0)
1287     {
1288       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1289         fprintf (vect_dump, "not vectorized: vectorization not profitable.");
1290       if (vect_print_dump_info (REPORT_DETAILS))
1291         fprintf (vect_dump, "not vectorized: vector version will never be "
1292                  "profitable.");
1293       return false;
1294     }
1295
1296   min_scalar_loop_bound = ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND)
1297                             * vectorization_factor) - 1);
1298
1299   /* Use the cost model only if it is more conservative than user specified
1300      threshold.  */
1301
1302   th = (unsigned) min_scalar_loop_bound;
1303   if (min_profitable_iters
1304       && (!min_scalar_loop_bound
1305           || min_profitable_iters > min_scalar_loop_bound))
1306     th = (unsigned) min_profitable_iters;
1307
1308   if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1309       && LOOP_VINFO_INT_NITERS (loop_vinfo) <= th)
1310     {
1311       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1312         fprintf (vect_dump, "not vectorized: vectorization not "
1313                  "profitable.");
1314       if (vect_print_dump_info (REPORT_DETAILS))
1315         fprintf (vect_dump, "not vectorized: iteration count smaller than "
1316                  "user specified loop bound parameter or minimum "
1317                  "profitable iterations (whichever is more conservative).");
1318       return false;
1319     }
1320
1321   if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1322       || LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0
1323       || LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo))
1324     {
1325       if (vect_print_dump_info (REPORT_DETAILS))
1326         fprintf (vect_dump, "epilog loop required.");
1327       if (!vect_can_advance_ivs_p (loop_vinfo))
1328         {
1329           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1330             fprintf (vect_dump,
1331                      "not vectorized: can't create epilog loop 1.");
1332           return false;
1333         }
1334       if (!slpeel_can_duplicate_loop_p (loop, single_exit (loop)))
1335         {
1336           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1337             fprintf (vect_dump,
1338                      "not vectorized: can't create epilog loop 2.");
1339           return false;
1340         }
1341     }
1342
1343   return true;
1344 }
1345
1346
1347 /* Function vect_analyze_loop.
1348
1349    Apply a set of analyses on LOOP, and create a loop_vec_info struct
1350    for it. The different analyses will record information in the
1351    loop_vec_info struct.  */
1352 loop_vec_info
1353 vect_analyze_loop (struct loop *loop)
1354 {
1355   bool ok;
1356   loop_vec_info loop_vinfo;
1357
1358   if (vect_print_dump_info (REPORT_DETAILS))
1359     fprintf (vect_dump, "===== analyze_loop_nest =====");
1360
1361   if (loop_outer (loop)
1362       && loop_vec_info_for_loop (loop_outer (loop))
1363       && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop))))
1364     {
1365       if (vect_print_dump_info (REPORT_DETAILS))
1366         fprintf (vect_dump, "outer-loop already vectorized.");
1367       return NULL;
1368     }
1369
1370   /* Check the CFG characteristics of the loop (nesting, entry/exit, etc.  */
1371
1372   loop_vinfo = vect_analyze_loop_form (loop);
1373   if (!loop_vinfo)
1374     {
1375       if (vect_print_dump_info (REPORT_DETAILS))
1376         fprintf (vect_dump, "bad loop form.");
1377       return NULL;
1378     }
1379
1380   /* Find all data references in the loop (which correspond to vdefs/vuses)
1381      and analyze their evolution in the loop.
1382
1383      FORNOW: Handle only simple, array references, which
1384      alignment can be forced, and aligned pointer-references.  */
1385
1386   ok = vect_analyze_data_refs (loop_vinfo, NULL);
1387   if (!ok)
1388     {
1389       if (vect_print_dump_info (REPORT_DETAILS))
1390         fprintf (vect_dump, "bad data references.");
1391       destroy_loop_vec_info (loop_vinfo, true);
1392       return NULL;
1393     }
1394
1395   /* Classify all cross-iteration scalar data-flow cycles.
1396      Cross-iteration cycles caused by virtual phis are analyzed separately.  */
1397
1398   vect_analyze_scalar_cycles (loop_vinfo);
1399
1400   vect_pattern_recog (loop_vinfo);
1401
1402   /* Data-flow analysis to detect stmts that do not need to be vectorized.  */
1403
1404   ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
1405   if (!ok)
1406     {
1407       if (vect_print_dump_info (REPORT_DETAILS))
1408         fprintf (vect_dump, "unexpected pattern.");
1409       destroy_loop_vec_info (loop_vinfo, true);
1410       return NULL;
1411     }
1412
1413   /* Analyze the alignment of the data-refs in the loop.
1414      Fail if a data reference is found that cannot be vectorized.  */
1415
1416   ok = vect_analyze_data_refs_alignment (loop_vinfo, NULL);
1417   if (!ok)
1418     {
1419       if (vect_print_dump_info (REPORT_DETAILS))
1420         fprintf (vect_dump, "bad data alignment.");
1421       destroy_loop_vec_info (loop_vinfo, true);
1422       return NULL;
1423     }
1424
1425   ok = vect_determine_vectorization_factor (loop_vinfo);
1426   if (!ok)
1427     {
1428       if (vect_print_dump_info (REPORT_DETAILS))
1429         fprintf (vect_dump, "can't determine vectorization factor.");
1430       destroy_loop_vec_info (loop_vinfo, true);
1431       return NULL;
1432     }
1433
1434   /* Analyze data dependences between the data-refs in the loop.
1435      FORNOW: fail at the first data dependence that we encounter.  */
1436
1437   ok = vect_analyze_data_ref_dependences (loop_vinfo, NULL);
1438   if (!ok)
1439     {
1440       if (vect_print_dump_info (REPORT_DETAILS))
1441         fprintf (vect_dump, "bad data dependence.");
1442       destroy_loop_vec_info (loop_vinfo, true);
1443       return NULL;
1444     }
1445
1446   /* Analyze the access patterns of the data-refs in the loop (consecutive,
1447      complex, etc.). FORNOW: Only handle consecutive access pattern.  */
1448
1449   ok = vect_analyze_data_ref_accesses (loop_vinfo, NULL);
1450   if (!ok)
1451     {
1452       if (vect_print_dump_info (REPORT_DETAILS))
1453         fprintf (vect_dump, "bad data access.");
1454       destroy_loop_vec_info (loop_vinfo, true);
1455       return NULL;
1456     }
1457
1458   /* Prune the list of ddrs to be tested at run-time by versioning for alias.
1459      It is important to call pruning after vect_analyze_data_ref_accesses,
1460      since we use grouping information gathered by interleaving analysis.  */
1461   ok = vect_prune_runtime_alias_test_list (loop_vinfo);
1462   if (!ok)
1463     {
1464       if (vect_print_dump_info (REPORT_DETAILS))
1465         fprintf (vect_dump, "too long list of versioning for alias "
1466                             "run-time tests.");
1467       destroy_loop_vec_info (loop_vinfo, true);
1468       return NULL;
1469     }
1470
1471   /* Check the SLP opportunities in the loop, analyze and build SLP trees.  */
1472   ok = vect_analyze_slp (loop_vinfo, NULL);
1473   if (ok)
1474     {
1475       /* Decide which possible SLP instances to SLP.  */
1476       vect_make_slp_decision (loop_vinfo);
1477
1478       /* Find stmts that need to be both vectorized and SLPed.  */
1479       vect_detect_hybrid_slp (loop_vinfo);
1480     }
1481
1482   /* This pass will decide on using loop versioning and/or loop peeling in
1483      order to enhance the alignment of data references in the loop.  */
1484
1485   ok = vect_enhance_data_refs_alignment (loop_vinfo);
1486   if (!ok)
1487     {
1488       if (vect_print_dump_info (REPORT_DETAILS))
1489         fprintf (vect_dump, "bad data alignment.");
1490       destroy_loop_vec_info (loop_vinfo, true);
1491       return NULL;
1492     }
1493
1494   /* Scan all the operations in the loop and make sure they are
1495      vectorizable.  */
1496
1497   ok = vect_analyze_loop_operations (loop_vinfo);
1498   if (!ok)
1499     {
1500       if (vect_print_dump_info (REPORT_DETAILS))
1501         fprintf (vect_dump, "bad operation or unsupported loop bound.");
1502       destroy_loop_vec_info (loop_vinfo, true);
1503       return NULL;
1504     }
1505
1506   LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1;
1507
1508   return loop_vinfo;
1509 }
1510
1511
1512 /* Function reduction_code_for_scalar_code
1513
1514    Input:
1515    CODE - tree_code of a reduction operations.
1516
1517    Output:
1518    REDUC_CODE - the corresponding tree-code to be used to reduce the
1519       vector of partial results into a single scalar result (which
1520       will also reside in a vector) or ERROR_MARK if the operation is
1521       a supported reduction operation, but does not have such tree-code.
1522
1523    Return FALSE if CODE currently cannot be vectorized as reduction.  */
1524
1525 static bool
1526 reduction_code_for_scalar_code (enum tree_code code,
1527                                 enum tree_code *reduc_code)
1528 {
1529   switch (code)
1530     {
1531       case MAX_EXPR:
1532         *reduc_code = REDUC_MAX_EXPR;
1533         return true;
1534
1535       case MIN_EXPR:
1536         *reduc_code = REDUC_MIN_EXPR;
1537         return true;
1538
1539       case PLUS_EXPR:
1540         *reduc_code = REDUC_PLUS_EXPR;
1541         return true;
1542
1543       case MULT_EXPR:
1544       case MINUS_EXPR:
1545       case BIT_IOR_EXPR:
1546       case BIT_XOR_EXPR:
1547       case BIT_AND_EXPR:
1548         *reduc_code = ERROR_MARK;
1549         return true;
1550
1551       default:
1552        return false;
1553     }
1554 }
1555
1556
1557 /* Error reporting helper for vect_is_simple_reduction below. GIMPLE statement
1558    STMT is printed with a message MSG. */
1559
1560 static void
1561 report_vect_op (gimple stmt, const char *msg)
1562 {
1563   fprintf (vect_dump, "%s", msg);
1564   print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
1565 }
1566
1567
1568 /* Function vect_is_simple_reduction
1569
1570    (1) Detect a cross-iteration def-use cycle that represents a simple
1571    reduction computation. We look for the following pattern:
1572
1573    loop_header:
1574      a1 = phi < a0, a2 >
1575      a3 = ...
1576      a2 = operation (a3, a1)
1577
1578    such that:
1579    1. operation is commutative and associative and it is safe to
1580       change the order of the computation (if CHECK_REDUCTION is true)
1581    2. no uses for a2 in the loop (a2 is used out of the loop)
1582    3. no uses of a1 in the loop besides the reduction operation.
1583
1584    Condition 1 is tested here.
1585    Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
1586
1587    (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
1588    nested cycles, if CHECK_REDUCTION is false.
1589
1590    (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
1591    reductions:
1592
1593      a1 = phi < a0, a2 >
1594      inner loop (def of a3)
1595      a2 = phi < a3 >
1596 */
1597
1598 gimple
1599 vect_is_simple_reduction (loop_vec_info loop_info, gimple phi,
1600                           bool check_reduction, bool *double_reduc)
1601 {
1602   struct loop *loop = (gimple_bb (phi))->loop_father;
1603   struct loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
1604   edge latch_e = loop_latch_edge (loop);
1605   tree loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
1606   gimple def_stmt, def1 = NULL, def2 = NULL;
1607   enum tree_code code;
1608   tree op1, op2, op3 = NULL_TREE, op4 = NULL_TREE;
1609   tree type;
1610   int nloop_uses;
1611   tree name;
1612   imm_use_iterator imm_iter;
1613   use_operand_p use_p;
1614   bool phi_def;
1615
1616   *double_reduc = false;
1617
1618   /* If CHECK_REDUCTION is true, we assume inner-most loop vectorization,
1619      otherwise, we assume outer loop vectorization.  */
1620   gcc_assert ((check_reduction && loop == vect_loop)
1621               || (!check_reduction && flow_loop_nested_p (vect_loop, loop)));
1622
1623   name = PHI_RESULT (phi);
1624   nloop_uses = 0;
1625   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
1626     {
1627       gimple use_stmt = USE_STMT (use_p);
1628       if (is_gimple_debug (use_stmt))
1629         continue;
1630       if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt))
1631           && vinfo_for_stmt (use_stmt)
1632           && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt)))
1633         nloop_uses++;
1634       if (nloop_uses > 1)
1635         {
1636           if (vect_print_dump_info (REPORT_DETAILS))
1637             fprintf (vect_dump, "reduction used in loop.");
1638           return NULL;
1639         }
1640     }
1641
1642   if (TREE_CODE (loop_arg) != SSA_NAME)
1643     {
1644       if (vect_print_dump_info (REPORT_DETAILS))
1645         {
1646           fprintf (vect_dump, "reduction: not ssa_name: ");
1647           print_generic_expr (vect_dump, loop_arg, TDF_SLIM);
1648         }
1649       return NULL;
1650     }
1651
1652   def_stmt = SSA_NAME_DEF_STMT (loop_arg);
1653   if (!def_stmt)
1654     {
1655       if (vect_print_dump_info (REPORT_DETAILS))
1656         fprintf (vect_dump, "reduction: no def_stmt.");
1657       return NULL;
1658     }
1659
1660   if (!is_gimple_assign (def_stmt) && gimple_code (def_stmt) != GIMPLE_PHI)
1661     {
1662       if (vect_print_dump_info (REPORT_DETAILS))
1663         print_gimple_stmt (vect_dump, def_stmt, 0, TDF_SLIM);
1664       return NULL;
1665     }
1666
1667   if (is_gimple_assign (def_stmt))
1668     {
1669       name = gimple_assign_lhs (def_stmt);
1670       phi_def = false;
1671     }
1672   else
1673     {
1674       name = PHI_RESULT (def_stmt);
1675       phi_def = true;
1676     }
1677
1678   nloop_uses = 0;
1679   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
1680     {
1681       gimple use_stmt = USE_STMT (use_p);
1682       if (is_gimple_debug (use_stmt))
1683         continue;
1684       if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt))
1685           && vinfo_for_stmt (use_stmt)
1686           && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt)))
1687         nloop_uses++;
1688       if (nloop_uses > 1)
1689         {
1690           if (vect_print_dump_info (REPORT_DETAILS))
1691             fprintf (vect_dump, "reduction used in loop.");
1692           return NULL;
1693         }
1694     }
1695
1696   /* If DEF_STMT is a phi node itself, we expect it to have a single argument
1697      defined in the inner loop.  */
1698   if (phi_def)
1699     {
1700       op1 = PHI_ARG_DEF (def_stmt, 0);
1701
1702       if (gimple_phi_num_args (def_stmt) != 1
1703           || TREE_CODE (op1) != SSA_NAME)
1704         {
1705           if (vect_print_dump_info (REPORT_DETAILS))
1706             fprintf (vect_dump, "unsupported phi node definition.");
1707
1708           return NULL;
1709         }
1710
1711       def1 = SSA_NAME_DEF_STMT (op1);
1712       if (flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
1713           && loop->inner
1714           && flow_bb_inside_loop_p (loop->inner, gimple_bb (def1))
1715           && is_gimple_assign (def1))
1716         {
1717           if (vect_print_dump_info (REPORT_DETAILS))
1718             report_vect_op (def_stmt, "detected double reduction: ");
1719
1720           *double_reduc = true;
1721           return def_stmt;
1722         }
1723
1724       return NULL;
1725     }
1726
1727   code = gimple_assign_rhs_code (def_stmt);
1728
1729   if (check_reduction
1730       && (!commutative_tree_code (code) || !associative_tree_code (code)))
1731     {
1732       if (vect_print_dump_info (REPORT_DETAILS))
1733         report_vect_op (def_stmt, "reduction: not commutative/associative: ");
1734       return NULL;
1735     }
1736
1737   if (get_gimple_rhs_class (code) != GIMPLE_BINARY_RHS)
1738     {
1739       if (code != COND_EXPR)
1740         {
1741           if (vect_print_dump_info (REPORT_DETAILS))
1742             report_vect_op (def_stmt, "reduction: not binary operation: ");
1743
1744           return NULL;
1745         }
1746
1747       op3 = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 0);
1748       if (COMPARISON_CLASS_P (op3))
1749         {
1750           op4 = TREE_OPERAND (op3, 1);
1751           op3 = TREE_OPERAND (op3, 0);
1752         }
1753
1754       op1 = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 1);
1755       op2 = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 2);
1756
1757       if (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op2) != SSA_NAME)
1758         {
1759           if (vect_print_dump_info (REPORT_DETAILS))
1760             report_vect_op (def_stmt, "reduction: uses not ssa_names: ");
1761
1762           return NULL;
1763         }
1764     }
1765   else
1766     {
1767       op1 = gimple_assign_rhs1 (def_stmt);
1768       op2 = gimple_assign_rhs2 (def_stmt);
1769
1770       if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
1771         {
1772           if (vect_print_dump_info (REPORT_DETAILS))
1773             report_vect_op (def_stmt, "reduction: uses not ssa_names: ");
1774
1775           return NULL;
1776         }
1777    }
1778
1779   type = TREE_TYPE (gimple_assign_lhs (def_stmt));
1780   if ((TREE_CODE (op1) == SSA_NAME
1781        && !types_compatible_p (type,TREE_TYPE (op1)))
1782       || (TREE_CODE (op2) == SSA_NAME
1783           && !types_compatible_p (type, TREE_TYPE (op2)))
1784       || (op3 && TREE_CODE (op3) == SSA_NAME
1785           && !types_compatible_p (type, TREE_TYPE (op3)))
1786       || (op4 && TREE_CODE (op4) == SSA_NAME
1787           && !types_compatible_p (type, TREE_TYPE (op4))))
1788     {
1789       if (vect_print_dump_info (REPORT_DETAILS))
1790         {
1791           fprintf (vect_dump, "reduction: multiple types: operation type: ");
1792           print_generic_expr (vect_dump, type, TDF_SLIM);
1793           fprintf (vect_dump, ", operands types: ");
1794           print_generic_expr (vect_dump, TREE_TYPE (op1), TDF_SLIM);
1795           fprintf (vect_dump, ",");
1796           print_generic_expr (vect_dump, TREE_TYPE (op2), TDF_SLIM);
1797           if (op3)
1798             {
1799               fprintf (vect_dump, ",");
1800               print_generic_expr (vect_dump, TREE_TYPE (op3), TDF_SLIM);
1801             }
1802
1803           if (op4)
1804             {
1805               fprintf (vect_dump, ",");
1806               print_generic_expr (vect_dump, TREE_TYPE (op4), TDF_SLIM);
1807             }
1808         }
1809
1810       return NULL;
1811     }
1812
1813   /* Check that it's ok to change the order of the computation.
1814      Generally, when vectorizing a reduction we change the order of the
1815      computation.  This may change the behavior of the program in some
1816      cases, so we need to check that this is ok.  One exception is when
1817      vectorizing an outer-loop: the inner-loop is executed sequentially,
1818      and therefore vectorizing reductions in the inner-loop during
1819      outer-loop vectorization is safe.  */
1820
1821   /* CHECKME: check for !flag_finite_math_only too?  */
1822   if (SCALAR_FLOAT_TYPE_P (type) && !flag_associative_math
1823       && check_reduction)
1824     {
1825       /* Changing the order of operations changes the semantics.  */
1826       if (vect_print_dump_info (REPORT_DETAILS))
1827         report_vect_op (def_stmt, "reduction: unsafe fp math optimization: ");
1828       return NULL;
1829     }
1830   else if (INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_TRAPS (type)
1831            && check_reduction)
1832     {
1833       /* Changing the order of operations changes the semantics.  */
1834       if (vect_print_dump_info (REPORT_DETAILS))
1835         report_vect_op (def_stmt, "reduction: unsafe int math optimization: ");
1836       return NULL;
1837     }
1838   else if (SAT_FIXED_POINT_TYPE_P (type) && check_reduction)
1839     {
1840       /* Changing the order of operations changes the semantics.  */
1841       if (vect_print_dump_info (REPORT_DETAILS))
1842         report_vect_op (def_stmt,
1843                         "reduction: unsafe fixed-point math optimization: ");
1844       return NULL;
1845     }
1846
1847   /* Reduction is safe. We're dealing with one of the following:
1848      1) integer arithmetic and no trapv
1849      2) floating point arithmetic, and special flags permit this optimization
1850      3) nested cycle (i.e., outer loop vectorization).  */
1851   if (TREE_CODE (op1) == SSA_NAME)
1852     def1 = SSA_NAME_DEF_STMT (op1);
1853
1854   if (TREE_CODE (op2) == SSA_NAME)
1855     def2 = SSA_NAME_DEF_STMT (op2);
1856
1857   if (code != COND_EXPR
1858       && (!def1 || !def2 || gimple_nop_p (def1) || gimple_nop_p (def2)))
1859     {
1860       if (vect_print_dump_info (REPORT_DETAILS))
1861         report_vect_op (def_stmt, "reduction: no defs for operands: ");
1862       return NULL;
1863     }
1864
1865   /* Check that one def is the reduction def, defined by PHI,
1866      the other def is either defined in the loop ("vect_internal_def"),
1867      or it's an induction (defined by a loop-header phi-node).  */
1868
1869   if (def2 && def2 == phi
1870       && (code == COND_EXPR
1871           || (def1 && flow_bb_inside_loop_p (loop, gimple_bb (def1))
1872               && (is_gimple_assign (def1)
1873                   || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1))
1874                       == vect_induction_def
1875                   || (gimple_code (def1) == GIMPLE_PHI
1876                       && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1))
1877                           == vect_internal_def
1878                       && !is_loop_header_bb_p (gimple_bb (def1)))))))
1879     {
1880       if (vect_print_dump_info (REPORT_DETAILS))
1881         report_vect_op (def_stmt, "detected reduction: ");
1882       return def_stmt;
1883     }
1884   else if (def1 && def1 == phi
1885            && (code == COND_EXPR
1886                || (def2 && flow_bb_inside_loop_p (loop, gimple_bb (def2))
1887                    && (is_gimple_assign (def2)
1888                        || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2))
1889                            == vect_induction_def
1890                        || (gimple_code (def2) == GIMPLE_PHI
1891                            && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2))
1892                                == vect_internal_def
1893                            && !is_loop_header_bb_p (gimple_bb (def2)))))))
1894     {
1895       if (check_reduction)
1896         {
1897           /* Swap operands (just for simplicity - so that the rest of the code
1898              can assume that the reduction variable is always the last (second)
1899              argument).  */
1900           if (vect_print_dump_info (REPORT_DETAILS))
1901             report_vect_op (def_stmt,
1902                             "detected reduction: need to swap operands: ");
1903
1904           swap_tree_operands (def_stmt, gimple_assign_rhs1_ptr (def_stmt),
1905                               gimple_assign_rhs2_ptr (def_stmt));
1906         }
1907       else
1908         {
1909           if (vect_print_dump_info (REPORT_DETAILS))
1910             report_vect_op (def_stmt, "detected reduction: ");
1911         }
1912
1913       return def_stmt;
1914     }
1915   else
1916     {
1917       if (vect_print_dump_info (REPORT_DETAILS))
1918         report_vect_op (def_stmt, "reduction: unknown pattern: ");
1919
1920       return NULL;
1921     }
1922 }
1923
1924
1925 /* Function vect_estimate_min_profitable_iters
1926
1927    Return the number of iterations required for the vector version of the
1928    loop to be profitable relative to the cost of the scalar version of the
1929    loop.
1930
1931    TODO: Take profile info into account before making vectorization
1932    decisions, if available.  */
1933
1934 int
1935 vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo)
1936 {
1937   int i;
1938   int min_profitable_iters;
1939   int peel_iters_prologue;
1940   int peel_iters_epilogue;
1941   int vec_inside_cost = 0;
1942   int vec_outside_cost = 0;
1943   int scalar_single_iter_cost = 0;
1944   int scalar_outside_cost = 0;
1945   int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1946   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1947   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1948   int nbbs = loop->num_nodes;
1949   int byte_misalign = LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo);
1950   int peel_guard_costs = 0;
1951   int innerloop_iters = 0, factor;
1952   VEC (slp_instance, heap) *slp_instances;
1953   slp_instance instance;
1954
1955   /* Cost model disabled.  */
1956   if (!flag_vect_cost_model)
1957     {
1958       if (vect_print_dump_info (REPORT_COST))
1959         fprintf (vect_dump, "cost model disabled.");
1960       return 0;
1961     }
1962
1963   /* Requires loop versioning tests to handle misalignment.  */
1964   if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo))
1965     {
1966       /*  FIXME: Make cost depend on complexity of individual check.  */
1967       vec_outside_cost +=
1968         VEC_length (gimple, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
1969       if (vect_print_dump_info (REPORT_COST))
1970         fprintf (vect_dump, "cost model: Adding cost of checks for loop "
1971                  "versioning to treat misalignment.\n");
1972     }
1973
1974   /* Requires loop versioning with alias checks.  */
1975   if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
1976     {
1977       /*  FIXME: Make cost depend on complexity of individual check.  */
1978       vec_outside_cost +=
1979         VEC_length (ddr_p, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo));
1980       if (vect_print_dump_info (REPORT_COST))
1981         fprintf (vect_dump, "cost model: Adding cost of checks for loop "
1982                  "versioning aliasing.\n");
1983     }
1984
1985   if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
1986       || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
1987     vec_outside_cost += TARG_COND_TAKEN_BRANCH_COST;
1988
1989   /* Count statements in scalar loop.  Using this as scalar cost for a single
1990      iteration for now.
1991
1992      TODO: Add outer loop support.
1993
1994      TODO: Consider assigning different costs to different scalar
1995      statements.  */
1996
1997   /* FORNOW.  */
1998   if (loop->inner)
1999     innerloop_iters = 50; /* FIXME */
2000
2001   for (i = 0; i < nbbs; i++)
2002     {
2003       gimple_stmt_iterator si;
2004       basic_block bb = bbs[i];
2005
2006       if (bb->loop_father == loop->inner)
2007         factor = innerloop_iters;
2008       else
2009         factor = 1;
2010
2011       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
2012         {
2013           gimple stmt = gsi_stmt (si);
2014           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2015           /* Skip stmts that are not vectorized inside the loop.  */
2016           if (!STMT_VINFO_RELEVANT_P (stmt_info)
2017               && (!STMT_VINFO_LIVE_P (stmt_info)
2018                   || STMT_VINFO_DEF_TYPE (stmt_info) != vect_reduction_def))
2019             continue;
2020           scalar_single_iter_cost += cost_for_stmt (stmt) * factor;
2021           vec_inside_cost += STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info) * factor;
2022           /* FIXME: for stmts in the inner-loop in outer-loop vectorization,
2023              some of the "outside" costs are generated inside the outer-loop.  */
2024           vec_outside_cost += STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info);
2025         }
2026     }
2027
2028   /* Add additional cost for the peeled instructions in prologue and epilogue
2029      loop.
2030
2031      FORNOW: If we don't know the value of peel_iters for prologue or epilogue
2032      at compile-time - we assume it's vf/2 (the worst would be vf-1).
2033
2034      TODO: Build an expression that represents peel_iters for prologue and
2035      epilogue to be used in a run-time test.  */
2036
2037   if (byte_misalign < 0)
2038     {
2039       peel_iters_prologue = vf/2;
2040       if (vect_print_dump_info (REPORT_COST))
2041         fprintf (vect_dump, "cost model: "
2042                  "prologue peel iters set to vf/2.");
2043
2044       /* If peeling for alignment is unknown, loop bound of main loop becomes
2045          unknown.  */
2046       peel_iters_epilogue = vf/2;
2047       if (vect_print_dump_info (REPORT_COST))
2048         fprintf (vect_dump, "cost model: "
2049                  "epilogue peel iters set to vf/2 because "
2050                  "peeling for alignment is unknown .");
2051
2052       /* If peeled iterations are unknown, count a taken branch and a not taken
2053          branch per peeled loop. Even if scalar loop iterations are known,
2054          vector iterations are not known since peeled prologue iterations are
2055          not known. Hence guards remain the same.  */
2056       peel_guard_costs +=  2 * (TARG_COND_TAKEN_BRANCH_COST
2057                               + TARG_COND_NOT_TAKEN_BRANCH_COST);
2058     }
2059   else
2060     {
2061       if (byte_misalign)
2062         {
2063           struct data_reference *dr = LOOP_VINFO_UNALIGNED_DR (loop_vinfo);
2064           int element_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr))));
2065           tree vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr)));
2066           int nelements = TYPE_VECTOR_SUBPARTS (vectype);
2067
2068           peel_iters_prologue = nelements - (byte_misalign / element_size);
2069         }
2070       else
2071         peel_iters_prologue = 0;
2072
2073       if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
2074         {
2075           peel_iters_epilogue = vf/2;
2076           if (vect_print_dump_info (REPORT_COST))
2077             fprintf (vect_dump, "cost model: "
2078                      "epilogue peel iters set to vf/2 because "
2079                      "loop iterations are unknown .");
2080
2081           /* If peeled iterations are known but number of scalar loop
2082              iterations are unknown, count a taken branch per peeled loop.  */
2083           peel_guard_costs +=  2 * TARG_COND_TAKEN_BRANCH_COST;
2084
2085         }
2086       else
2087         {
2088           int niters = LOOP_VINFO_INT_NITERS (loop_vinfo);
2089           peel_iters_prologue = niters < peel_iters_prologue ?
2090                                         niters : peel_iters_prologue;
2091           peel_iters_epilogue = (niters - peel_iters_prologue) % vf;
2092         }
2093     }
2094
2095   vec_outside_cost += (peel_iters_prologue * scalar_single_iter_cost)
2096                       + (peel_iters_epilogue * scalar_single_iter_cost)
2097                       + peel_guard_costs;
2098
2099   /* FORNOW: The scalar outside cost is incremented in one of the
2100      following ways:
2101
2102      1. The vectorizer checks for alignment and aliasing and generates
2103      a condition that allows dynamic vectorization.  A cost model
2104      check is ANDED with the versioning condition.  Hence scalar code
2105      path now has the added cost of the versioning check.
2106
2107        if (cost > th & versioning_check)
2108          jmp to vector code
2109
2110      Hence run-time scalar is incremented by not-taken branch cost.
2111
2112      2. The vectorizer then checks if a prologue is required.  If the
2113      cost model check was not done before during versioning, it has to
2114      be done before the prologue check.
2115
2116        if (cost <= th)
2117          prologue = scalar_iters
2118        if (prologue == 0)
2119          jmp to vector code
2120        else
2121          execute prologue
2122        if (prologue == num_iters)
2123          go to exit
2124
2125      Hence the run-time scalar cost is incremented by a taken branch,
2126      plus a not-taken branch, plus a taken branch cost.
2127
2128      3. The vectorizer then checks if an epilogue is required.  If the
2129      cost model check was not done before during prologue check, it
2130      has to be done with the epilogue check.
2131
2132        if (prologue == 0)
2133          jmp to vector code
2134        else
2135          execute prologue
2136        if (prologue == num_iters)
2137          go to exit
2138        vector code:
2139          if ((cost <= th) | (scalar_iters-prologue-epilogue == 0))
2140            jmp to epilogue
2141
2142      Hence the run-time scalar cost should be incremented by 2 taken
2143      branches.
2144
2145      TODO: The back end may reorder the BBS's differently and reverse
2146      conditions/branch directions.  Change the estimates below to
2147      something more reasonable.  */
2148
2149   /* If the number of iterations is known and we do not do versioning, we can
2150      decide whether to vectorize at compile time. Hence the scalar version
2151      do not carry cost model guard costs.  */
2152   if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
2153       || LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
2154       || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2155     {
2156       /* Cost model check occurs at versioning.  */
2157       if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
2158           || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2159         scalar_outside_cost += TARG_COND_NOT_TAKEN_BRANCH_COST;
2160       else
2161         {
2162           /* Cost model check occurs at prologue generation.  */
2163           if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0)
2164             scalar_outside_cost += 2 * TARG_COND_TAKEN_BRANCH_COST
2165               + TARG_COND_NOT_TAKEN_BRANCH_COST;
2166           /* Cost model check occurs at epilogue generation.  */
2167           else
2168             scalar_outside_cost += 2 * TARG_COND_TAKEN_BRANCH_COST;
2169         }
2170     }
2171
2172   /* Add SLP costs.  */
2173   slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
2174   for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
2175     {
2176       vec_outside_cost += SLP_INSTANCE_OUTSIDE_OF_LOOP_COST (instance);
2177       vec_inside_cost += SLP_INSTANCE_INSIDE_OF_LOOP_COST (instance);
2178     }
2179
2180   /* Calculate number of iterations required to make the vector version
2181      profitable, relative to the loop bodies only. The following condition
2182      must hold true:
2183      SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
2184      where
2185      SIC = scalar iteration cost, VIC = vector iteration cost,
2186      VOC = vector outside cost, VF = vectorization factor,
2187      PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
2188      SOC = scalar outside cost for run time cost model check.  */
2189
2190   if ((scalar_single_iter_cost * vf) > vec_inside_cost)
2191     {
2192       if (vec_outside_cost <= 0)
2193         min_profitable_iters = 1;
2194       else
2195         {
2196           min_profitable_iters = ((vec_outside_cost - scalar_outside_cost) * vf
2197                                   - vec_inside_cost * peel_iters_prologue
2198                                   - vec_inside_cost * peel_iters_epilogue)
2199                                  / ((scalar_single_iter_cost * vf)
2200                                     - vec_inside_cost);
2201
2202           if ((scalar_single_iter_cost * vf * min_profitable_iters)
2203               <= ((vec_inside_cost * min_profitable_iters)
2204                   + ((vec_outside_cost - scalar_outside_cost) * vf)))
2205             min_profitable_iters++;
2206         }
2207     }
2208   /* vector version will never be profitable.  */
2209   else
2210     {
2211       if (vect_print_dump_info (REPORT_COST))
2212         fprintf (vect_dump, "cost model: the vector iteration cost = %d "
2213                  "divided by the scalar iteration cost = %d "
2214                  "is greater or equal to the vectorization factor = %d.",
2215                  vec_inside_cost, scalar_single_iter_cost, vf);
2216       return -1;
2217     }
2218
2219   if (vect_print_dump_info (REPORT_COST))
2220     {
2221       fprintf (vect_dump, "Cost model analysis: \n");
2222       fprintf (vect_dump, "  Vector inside of loop cost: %d\n",
2223                vec_inside_cost);
2224       fprintf (vect_dump, "  Vector outside of loop cost: %d\n",
2225                vec_outside_cost);
2226       fprintf (vect_dump, "  Scalar iteration cost: %d\n",
2227                scalar_single_iter_cost);
2228       fprintf (vect_dump, "  Scalar outside cost: %d\n", scalar_outside_cost);
2229       fprintf (vect_dump, "  prologue iterations: %d\n",
2230                peel_iters_prologue);
2231       fprintf (vect_dump, "  epilogue iterations: %d\n",
2232                peel_iters_epilogue);
2233       fprintf (vect_dump, "  Calculated minimum iters for profitability: %d\n",
2234                min_profitable_iters);
2235     }
2236
2237   min_profitable_iters =
2238         min_profitable_iters < vf ? vf : min_profitable_iters;
2239
2240   /* Because the condition we create is:
2241      if (niters <= min_profitable_iters)
2242        then skip the vectorized loop.  */
2243   min_profitable_iters--;
2244
2245   if (vect_print_dump_info (REPORT_COST))
2246     fprintf (vect_dump, "  Profitability threshold = %d\n",
2247              min_profitable_iters);
2248
2249   return min_profitable_iters;
2250 }
2251
2252
2253 /* TODO: Close dependency between vect_model_*_cost and vectorizable_*
2254    functions. Design better to avoid maintenance issues.  */
2255
2256 /* Function vect_model_reduction_cost.
2257
2258    Models cost for a reduction operation, including the vector ops
2259    generated within the strip-mine loop, the initial definition before
2260    the loop, and the epilogue code that must be generated.  */
2261
2262 static bool
2263 vect_model_reduction_cost (stmt_vec_info stmt_info, enum tree_code reduc_code,
2264                            int ncopies)
2265 {
2266   int outer_cost = 0;
2267   enum tree_code code;
2268   optab optab;
2269   tree vectype;
2270   gimple stmt, orig_stmt;
2271   tree reduction_op;
2272   enum machine_mode mode;
2273   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2274   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2275
2276
2277   /* Cost of reduction op inside loop.  */
2278   STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info) += ncopies * TARG_VEC_STMT_COST;
2279
2280   stmt = STMT_VINFO_STMT (stmt_info);
2281
2282   switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2283     {
2284     case GIMPLE_SINGLE_RHS:
2285       gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt)) == ternary_op);
2286       reduction_op = TREE_OPERAND (gimple_assign_rhs1 (stmt), 2);
2287       break;
2288     case GIMPLE_UNARY_RHS:
2289       reduction_op = gimple_assign_rhs1 (stmt);
2290       break;
2291     case GIMPLE_BINARY_RHS:
2292       reduction_op = gimple_assign_rhs2 (stmt);
2293       break;
2294     default:
2295       gcc_unreachable ();
2296     }
2297
2298   vectype = get_vectype_for_scalar_type (TREE_TYPE (reduction_op));
2299   if (!vectype)
2300     {
2301       if (vect_print_dump_info (REPORT_COST))
2302         {
2303           fprintf (vect_dump, "unsupported data-type ");
2304           print_generic_expr (vect_dump, TREE_TYPE (reduction_op), TDF_SLIM);
2305         }
2306       return false;
2307    }
2308
2309   mode = TYPE_MODE (vectype);
2310   orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
2311
2312   if (!orig_stmt)
2313     orig_stmt = STMT_VINFO_STMT (stmt_info);
2314
2315   code = gimple_assign_rhs_code (orig_stmt);
2316
2317   /* Add in cost for initial definition.  */
2318   outer_cost += TARG_SCALAR_TO_VEC_COST;
2319
2320   /* Determine cost of epilogue code.
2321
2322      We have a reduction operator that will reduce the vector in one statement.
2323      Also requires scalar extract.  */
2324
2325   if (!nested_in_vect_loop_p (loop, orig_stmt))
2326     {
2327       if (reduc_code != ERROR_MARK)
2328         outer_cost += TARG_VEC_STMT_COST + TARG_VEC_TO_SCALAR_COST;
2329       else
2330         {
2331           int vec_size_in_bits = tree_low_cst (TYPE_SIZE (vectype), 1);
2332           tree bitsize =
2333             TYPE_SIZE (TREE_TYPE (gimple_assign_lhs (orig_stmt)));
2334           int element_bitsize = tree_low_cst (bitsize, 1);
2335           int nelements = vec_size_in_bits / element_bitsize;
2336
2337           optab = optab_for_tree_code (code, vectype, optab_default);
2338
2339           /* We have a whole vector shift available.  */
2340           if (VECTOR_MODE_P (mode)
2341               && optab_handler (optab, mode)->insn_code != CODE_FOR_nothing
2342               && optab_handler (vec_shr_optab, mode)->insn_code != CODE_FOR_nothing)
2343             /* Final reduction via vector shifts and the reduction operator. Also
2344                requires scalar extract.  */
2345             outer_cost += ((exact_log2(nelements) * 2) * TARG_VEC_STMT_COST
2346                                 + TARG_VEC_TO_SCALAR_COST);
2347           else
2348             /* Use extracts and reduction op for final reduction.  For N elements,
2349                we have N extracts and N-1 reduction ops.  */
2350             outer_cost += ((nelements + nelements - 1) * TARG_VEC_STMT_COST);
2351         }
2352     }
2353
2354   STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info) = outer_cost;
2355
2356   if (vect_print_dump_info (REPORT_COST))
2357     fprintf (vect_dump, "vect_model_reduction_cost: inside_cost = %d, "
2358              "outside_cost = %d .", STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info),
2359              STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info));
2360
2361   return true;
2362 }
2363
2364
2365 /* Function vect_model_induction_cost.
2366
2367    Models cost for induction operations.  */
2368
2369 static void
2370 vect_model_induction_cost (stmt_vec_info stmt_info, int ncopies)
2371 {
2372   /* loop cost for vec_loop.  */
2373   STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info) = ncopies * TARG_VEC_STMT_COST;
2374   /* prologue cost for vec_init and vec_step.  */
2375   STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info) = 2 * TARG_SCALAR_TO_VEC_COST;
2376
2377   if (vect_print_dump_info (REPORT_COST))
2378     fprintf (vect_dump, "vect_model_induction_cost: inside_cost = %d, "
2379              "outside_cost = %d .", STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info),
2380              STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info));
2381 }
2382
2383
2384 /* Function get_initial_def_for_induction
2385
2386    Input:
2387    STMT - a stmt that performs an induction operation in the loop.
2388    IV_PHI - the initial value of the induction variable
2389
2390    Output:
2391    Return a vector variable, initialized with the first VF values of
2392    the induction variable. E.g., for an iv with IV_PHI='X' and
2393    evolution S, for a vector of 4 units, we want to return:
2394    [X, X + S, X + 2*S, X + 3*S].  */
2395
2396 static tree
2397 get_initial_def_for_induction (gimple iv_phi)
2398 {
2399   stmt_vec_info stmt_vinfo = vinfo_for_stmt (iv_phi);
2400   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
2401   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2402   tree scalar_type = TREE_TYPE (gimple_phi_result (iv_phi));
2403   tree vectype;
2404   int nunits;
2405   edge pe = loop_preheader_edge (loop);
2406   struct loop *iv_loop;
2407   basic_block new_bb;
2408   tree vec, vec_init, vec_step, t;
2409   tree access_fn;
2410   tree new_var;
2411   tree new_name;
2412   gimple init_stmt, induction_phi, new_stmt;
2413   tree induc_def, vec_def, vec_dest;
2414   tree init_expr, step_expr;
2415   int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2416   int i;
2417   bool ok;
2418   int ncopies;
2419   tree expr;
2420   stmt_vec_info phi_info = vinfo_for_stmt (iv_phi);
2421   bool nested_in_vect_loop = false;
2422   gimple_seq stmts = NULL;
2423   imm_use_iterator imm_iter;
2424   use_operand_p use_p;
2425   gimple exit_phi;
2426   edge latch_e;
2427   tree loop_arg;
2428   gimple_stmt_iterator si;
2429   basic_block bb = gimple_bb (iv_phi);
2430   tree stepvectype;
2431
2432   vectype = get_vectype_for_scalar_type (scalar_type);
2433   gcc_assert (vectype);
2434   nunits = TYPE_VECTOR_SUBPARTS (vectype);
2435   ncopies = vf / nunits;
2436
2437   gcc_assert (phi_info);
2438   gcc_assert (ncopies >= 1);
2439
2440   /* Find the first insertion point in the BB.  */
2441   si = gsi_after_labels (bb);
2442
2443   if (INTEGRAL_TYPE_P (scalar_type))
2444     step_expr = build_int_cst (scalar_type, 0);
2445   else if (POINTER_TYPE_P (scalar_type))
2446     step_expr = build_int_cst (sizetype, 0);
2447   else
2448     step_expr = build_real (scalar_type, dconst0);
2449
2450   /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop?  */
2451   if (nested_in_vect_loop_p (loop, iv_phi))
2452     {
2453       nested_in_vect_loop = true;
2454       iv_loop = loop->inner;
2455     }
2456   else
2457     iv_loop = loop;
2458   gcc_assert (iv_loop == (gimple_bb (iv_phi))->loop_father);
2459
2460   latch_e = loop_latch_edge (iv_loop);
2461   loop_arg = PHI_ARG_DEF_FROM_EDGE (iv_phi, latch_e);
2462
2463   access_fn = analyze_scalar_evolution (iv_loop, PHI_RESULT (iv_phi));
2464   gcc_assert (access_fn);
2465   ok = vect_is_simple_iv_evolution (iv_loop->num, access_fn,
2466                                     &init_expr, &step_expr);
2467   gcc_assert (ok);
2468   pe = loop_preheader_edge (iv_loop);
2469
2470   /* Create the vector that holds the initial_value of the induction.  */
2471   if (nested_in_vect_loop)
2472     {
2473       /* iv_loop is nested in the loop to be vectorized.  init_expr had already
2474          been created during vectorization of previous stmts; We obtain it from
2475          the STMT_VINFO_VEC_STMT of the defining stmt. */
2476       tree iv_def = PHI_ARG_DEF_FROM_EDGE (iv_phi,
2477                                            loop_preheader_edge (iv_loop));
2478       vec_init = vect_get_vec_def_for_operand (iv_def, iv_phi, NULL);
2479     }
2480   else
2481     {
2482       /* iv_loop is the loop to be vectorized. Create:
2483          vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr)  */
2484       new_var = vect_get_new_vect_var (scalar_type, vect_scalar_var, "var_");
2485       add_referenced_var (new_var);
2486
2487       new_name = force_gimple_operand (init_expr, &stmts, false, new_var);
2488       if (stmts)
2489         {
2490           new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
2491           gcc_assert (!new_bb);
2492         }
2493
2494       t = NULL_TREE;
2495       t = tree_cons (NULL_TREE, init_expr, t);
2496       for (i = 1; i < nunits; i++)
2497         {
2498           /* Create: new_name_i = new_name + step_expr  */
2499           enum tree_code code = POINTER_TYPE_P (scalar_type)
2500                                 ? POINTER_PLUS_EXPR : PLUS_EXPR;
2501           init_stmt = gimple_build_assign_with_ops (code, new_var,
2502                                                     new_name, step_expr);
2503           new_name = make_ssa_name (new_var, init_stmt);
2504           gimple_assign_set_lhs (init_stmt, new_name);
2505
2506           new_bb = gsi_insert_on_edge_immediate (pe, init_stmt);
2507           gcc_assert (!new_bb);
2508
2509           if (vect_print_dump_info (REPORT_DETAILS))
2510             {
2511               fprintf (vect_dump, "created new init_stmt: ");
2512               print_gimple_stmt (vect_dump, init_stmt, 0, TDF_SLIM);
2513             }
2514           t = tree_cons (NULL_TREE, new_name, t);
2515         }
2516       /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1]  */
2517       vec = build_constructor_from_list (vectype, nreverse (t));
2518       vec_init = vect_init_vector (iv_phi, vec, vectype, NULL);
2519     }
2520
2521
2522   /* Create the vector that holds the step of the induction.  */
2523   if (nested_in_vect_loop)
2524     /* iv_loop is nested in the loop to be vectorized. Generate:
2525        vec_step = [S, S, S, S]  */
2526     new_name = step_expr;
2527   else
2528     {
2529       /* iv_loop is the loop to be vectorized. Generate:
2530           vec_step = [VF*S, VF*S, VF*S, VF*S]  */
2531       expr = build_int_cst (TREE_TYPE (step_expr), vf);
2532       new_name = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr),
2533                               expr, step_expr);
2534     }
2535
2536   t = NULL_TREE;
2537   for (i = 0; i < nunits; i++)
2538     t = tree_cons (NULL_TREE, unshare_expr (new_name), t);
2539   gcc_assert (CONSTANT_CLASS_P (new_name));
2540   stepvectype = get_vectype_for_scalar_type (TREE_TYPE (new_name));
2541   gcc_assert (stepvectype);
2542   vec = build_vector (stepvectype, t);
2543   vec_step = vect_init_vector (iv_phi, vec, stepvectype, NULL);
2544
2545
2546   /* Create the following def-use cycle:
2547      loop prolog:
2548          vec_init = ...
2549          vec_step = ...
2550      loop:
2551          vec_iv = PHI <vec_init, vec_loop>
2552          ...
2553          STMT
2554          ...
2555          vec_loop = vec_iv + vec_step;  */
2556
2557   /* Create the induction-phi that defines the induction-operand.  */
2558   vec_dest = vect_get_new_vect_var (vectype, vect_simple_var, "vec_iv_");
2559   add_referenced_var (vec_dest);
2560   induction_phi = create_phi_node (vec_dest, iv_loop->header);
2561   set_vinfo_for_stmt (induction_phi,
2562                       new_stmt_vec_info (induction_phi, loop_vinfo, NULL));
2563   induc_def = PHI_RESULT (induction_phi);
2564
2565   /* Create the iv update inside the loop  */
2566   new_stmt = gimple_build_assign_with_ops (PLUS_EXPR, vec_dest,
2567                                            induc_def, vec_step);
2568   vec_def = make_ssa_name (vec_dest, new_stmt);
2569   gimple_assign_set_lhs (new_stmt, vec_def);
2570   gsi_insert_before (&si, new_stmt, GSI_SAME_STMT);
2571   set_vinfo_for_stmt (new_stmt, new_stmt_vec_info (new_stmt, loop_vinfo,
2572                                                    NULL));
2573
2574   /* Set the arguments of the phi node:  */
2575   add_phi_arg (induction_phi, vec_init, pe, UNKNOWN_LOCATION);
2576   add_phi_arg (induction_phi, vec_def, loop_latch_edge (iv_loop),
2577                UNKNOWN_LOCATION);
2578
2579
2580   /* In case that vectorization factor (VF) is bigger than the number
2581      of elements that we can fit in a vectype (nunits), we have to generate
2582      more than one vector stmt - i.e - we need to "unroll" the
2583      vector stmt by a factor VF/nunits.  For more details see documentation
2584      in vectorizable_operation.  */
2585
2586   if (ncopies > 1)
2587     {
2588       stmt_vec_info prev_stmt_vinfo;
2589       /* FORNOW. This restriction should be relaxed.  */
2590       gcc_assert (!nested_in_vect_loop);
2591
2592       /* Create the vector that holds the step of the induction.  */
2593       expr = build_int_cst (TREE_TYPE (step_expr), nunits);
2594       new_name = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr),
2595                               expr, step_expr);
2596       t = NULL_TREE;
2597       for (i = 0; i < nunits; i++)
2598         t = tree_cons (NULL_TREE, unshare_expr (new_name), t);
2599       gcc_assert (CONSTANT_CLASS_P (new_name));
2600       vec = build_vector (stepvectype, t);
2601       vec_step = vect_init_vector (iv_phi, vec, stepvectype, NULL);
2602
2603       vec_def = induc_def;
2604       prev_stmt_vinfo = vinfo_for_stmt (induction_phi);
2605       for (i = 1; i < ncopies; i++)
2606         {
2607           /* vec_i = vec_prev + vec_step  */
2608           new_stmt = gimple_build_assign_with_ops (PLUS_EXPR, vec_dest,
2609                                                    vec_def, vec_step);
2610           vec_def = make_ssa_name (vec_dest, new_stmt);
2611           gimple_assign_set_lhs (new_stmt, vec_def);
2612
2613           gsi_insert_before (&si, new_stmt, GSI_SAME_STMT);
2614           set_vinfo_for_stmt (new_stmt,
2615                               new_stmt_vec_info (new_stmt, loop_vinfo, NULL));
2616           STMT_VINFO_RELATED_STMT (prev_stmt_vinfo) = new_stmt;
2617           prev_stmt_vinfo = vinfo_for_stmt (new_stmt);
2618         }
2619     }
2620
2621   if (nested_in_vect_loop)
2622     {
2623       /* Find the loop-closed exit-phi of the induction, and record
2624          the final vector of induction results:  */
2625       exit_phi = NULL;
2626       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, loop_arg)
2627         {
2628           if (!flow_bb_inside_loop_p (iv_loop, gimple_bb (USE_STMT (use_p))))
2629             {
2630               exit_phi = USE_STMT (use_p);
2631               break;
2632             }
2633         }
2634       if (exit_phi)
2635         {
2636           stmt_vec_info stmt_vinfo = vinfo_for_stmt (exit_phi);
2637           /* FORNOW. Currently not supporting the case that an inner-loop induction
2638              is not used in the outer-loop (i.e. only outside the outer-loop).  */
2639           gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo)
2640                       && !STMT_VINFO_LIVE_P (stmt_vinfo));
2641
2642           STMT_VINFO_VEC_STMT (stmt_vinfo) = new_stmt;
2643           if (vect_print_dump_info (REPORT_DETAILS))
2644             {
2645               fprintf (vect_dump, "vector of inductions after inner-loop:");
2646               print_gimple_stmt (vect_dump, new_stmt, 0, TDF_SLIM);
2647             }
2648         }
2649     }
2650
2651
2652   if (vect_print_dump_info (REPORT_DETAILS))
2653     {
2654       fprintf (vect_dump, "transform induction: created def-use cycle: ");
2655       print_gimple_stmt (vect_dump, induction_phi, 0, TDF_SLIM);
2656       fprintf (vect_dump, "\n");
2657       print_gimple_stmt (vect_dump, SSA_NAME_DEF_STMT (vec_def), 0, TDF_SLIM);
2658     }
2659
2660   STMT_VINFO_VEC_STMT (phi_info) = induction_phi;
2661   return induc_def;
2662 }
2663
2664
2665 /* Function get_initial_def_for_reduction
2666
2667    Input:
2668    STMT - a stmt that performs a reduction operation in the loop.
2669    INIT_VAL - the initial value of the reduction variable
2670
2671    Output:
2672    ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
2673         of the reduction (used for adjusting the epilog - see below).
2674    Return a vector variable, initialized according to the operation that STMT
2675         performs. This vector will be used as the initial value of the
2676         vector of partial results.
2677
2678    Option1 (adjust in epilog): Initialize the vector as follows:
2679      add/bit or/xor:    [0,0,...,0,0]
2680      mult/bit and:      [1,1,...,1,1]
2681      min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
2682    and when necessary (e.g. add/mult case) let the caller know
2683    that it needs to adjust the result by init_val.
2684
2685    Option2: Initialize the vector as follows:
2686      add/bit or/xor:    [init_val,0,0,...,0]
2687      mult/bit and:      [init_val,1,1,...,1]
2688      min/max/cond_expr: [init_val,init_val,...,init_val]
2689    and no adjustments are needed.
2690
2691    For example, for the following code:
2692
2693    s = init_val;
2694    for (i=0;i<n;i++)
2695      s = s + a[i];
2696
2697    STMT is 's = s + a[i]', and the reduction variable is 's'.
2698    For a vector of 4 units, we want to return either [0,0,0,init_val],
2699    or [0,0,0,0] and let the caller know that it needs to adjust
2700    the result at the end by 'init_val'.
2701
2702    FORNOW, we are using the 'adjust in epilog' scheme, because this way the
2703    initialization vector is simpler (same element in all entries), if
2704    ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
2705
2706    A cost model should help decide between these two schemes.  */
2707
2708 tree
2709 get_initial_def_for_reduction (gimple stmt, tree init_val,
2710                                tree *adjustment_def)
2711 {
2712   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
2713   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
2714   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2715   tree scalar_type = TREE_TYPE (init_val);
2716   tree vectype = get_vectype_for_scalar_type (scalar_type);
2717   int nunits;
2718   enum tree_code code = gimple_assign_rhs_code (stmt);
2719   tree def_for_init;
2720   tree init_def;
2721   tree t = NULL_TREE;
2722   int i;
2723   bool nested_in_vect_loop = false;
2724   tree init_value;
2725   REAL_VALUE_TYPE real_init_val = dconst0;
2726   int int_init_val = 0;
2727   gimple def_stmt = NULL;
2728
2729   gcc_assert (vectype);
2730   nunits = TYPE_VECTOR_SUBPARTS (vectype);
2731
2732   gcc_assert (POINTER_TYPE_P (scalar_type) || INTEGRAL_TYPE_P (scalar_type)
2733               || SCALAR_FLOAT_TYPE_P (scalar_type));
2734
2735   if (nested_in_vect_loop_p (loop, stmt))
2736     nested_in_vect_loop = true;
2737   else
2738     gcc_assert (loop == (gimple_bb (stmt))->loop_father);
2739
2740   /* In case of double reduction we only create a vector variable to be put
2741      in the reduction phi node. The actual statement creation is done in
2742      vect_create_epilog_for_reduction.  */
2743   if (adjustment_def && nested_in_vect_loop
2744       && TREE_CODE (init_val) == SSA_NAME
2745       && (def_stmt = SSA_NAME_DEF_STMT (init_val))
2746       && gimple_code (def_stmt) == GIMPLE_PHI
2747       && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
2748       && vinfo_for_stmt (def_stmt)
2749       && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt))
2750           == vect_double_reduction_def)
2751     {
2752       *adjustment_def = NULL;
2753       return vect_create_destination_var (init_val, vectype);
2754     }
2755
2756   if (TREE_CONSTANT (init_val))
2757     {
2758       if (SCALAR_FLOAT_TYPE_P (scalar_type))
2759         init_value = build_real (scalar_type, TREE_REAL_CST (init_val));
2760       else
2761         init_value = build_int_cst (scalar_type, TREE_INT_CST_LOW (init_val));
2762     }
2763   else
2764     init_value = init_val;
2765
2766   switch (code)
2767     {
2768       case WIDEN_SUM_EXPR:
2769       case DOT_PROD_EXPR:
2770       case PLUS_EXPR:
2771       case MINUS_EXPR:
2772       case BIT_IOR_EXPR:
2773       case BIT_XOR_EXPR:
2774       case MULT_EXPR:
2775       case BIT_AND_EXPR:
2776         /* ADJUSMENT_DEF is NULL when called from
2777            vect_create_epilog_for_reduction to vectorize double reduction.  */
2778         if (adjustment_def)
2779           {
2780             if (nested_in_vect_loop)
2781               *adjustment_def = vect_get_vec_def_for_operand (init_val, stmt,
2782                                                               NULL);
2783             else
2784               *adjustment_def = init_val;
2785           }
2786
2787         if (code == MULT_EXPR || code == BIT_AND_EXPR)
2788           {
2789             real_init_val = dconst1;
2790             int_init_val = 1;
2791           }
2792
2793         if (SCALAR_FLOAT_TYPE_P (scalar_type))
2794           def_for_init = build_real (scalar_type, real_init_val);
2795         else
2796           def_for_init = build_int_cst (scalar_type, int_init_val);
2797
2798         /* Create a vector of '0' or '1' except the first element.  */
2799         for (i = nunits - 2; i >= 0; --i)
2800           t = tree_cons (NULL_TREE, def_for_init, t);
2801
2802         /* Option1: the first element is '0' or '1' as well.  */
2803         if (adjustment_def)
2804           {
2805             t = tree_cons (NULL_TREE, def_for_init, t);
2806             init_def = build_vector (vectype, t);
2807             break;
2808           }
2809
2810         /* Option2: the first element is INIT_VAL.  */
2811         t = tree_cons (NULL_TREE, init_value, t);
2812         if (TREE_CONSTANT (init_val))
2813           init_def = build_vector (vectype, t);
2814         else
2815           init_def = build_constructor_from_list (vectype, t);
2816
2817         break;
2818
2819       case MIN_EXPR:
2820       case MAX_EXPR:
2821       case COND_EXPR:
2822         if (adjustment_def)
2823           {
2824             *adjustment_def = NULL_TREE;
2825             init_def = vect_get_vec_def_for_operand (init_val, stmt, NULL);
2826             break;
2827           }
2828
2829         for (i = nunits - 1; i >= 0; --i)
2830           t = tree_cons (NULL_TREE, init_value, t);
2831
2832         if (TREE_CONSTANT (init_val))
2833           init_def = build_vector (vectype, t);
2834         else
2835           init_def = build_constructor_from_list (vectype, t);
2836
2837         break;
2838
2839       default:
2840         gcc_unreachable ();
2841     }
2842
2843   return init_def;
2844 }
2845
2846
2847 /* Function vect_create_epilog_for_reduction
2848
2849    Create code at the loop-epilog to finalize the result of a reduction
2850    computation.
2851
2852    VECT_DEF is a vector of partial results.
2853    REDUC_CODE is the tree-code for the epilog reduction.
2854    NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
2855      number of elements that we can fit in a vectype (nunits). In this case
2856      we have to generate more than one vector stmt - i.e - we need to "unroll"
2857      the vector stmt by a factor VF/nunits.  For more details see documentation
2858      in vectorizable_operation.
2859    STMT is the scalar reduction stmt that is being vectorized.
2860    REDUCTION_PHI is the phi-node that carries the reduction computation.
2861    REDUC_INDEX is the index of the operand in the right hand side of the
2862      statement that is defined by REDUCTION_PHI.
2863    DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
2864
2865    This function:
2866    1. Creates the reduction def-use cycle: sets the arguments for
2867       REDUCTION_PHI:
2868       The loop-entry argument is the vectorized initial-value of the reduction.
2869       The loop-latch argument is VECT_DEF - the vector of partial sums.
2870    2. "Reduces" the vector of partial results VECT_DEF into a single result,
2871       by applying the operation specified by REDUC_CODE if available, or by
2872       other means (whole-vector shifts or a scalar loop).
2873       The function also creates a new phi node at the loop exit to preserve
2874       loop-closed form, as illustrated below.
2875
2876      The flow at the entry to this function:
2877
2878         loop:
2879           vec_def = phi <null, null>            # REDUCTION_PHI
2880           VECT_DEF = vector_stmt                # vectorized form of STMT
2881           s_loop = scalar_stmt                  # (scalar) STMT
2882         loop_exit:
2883           s_out0 = phi <s_loop>                 # (scalar) EXIT_PHI
2884           use <s_out0>
2885           use <s_out0>
2886
2887      The above is transformed by this function into:
2888
2889         loop:
2890           vec_def = phi <vec_init, VECT_DEF>    # REDUCTION_PHI
2891           VECT_DEF = vector_stmt                # vectorized form of STMT
2892           s_loop = scalar_stmt                  # (scalar) STMT
2893         loop_exit:
2894           s_out0 = phi <s_loop>                 # (scalar) EXIT_PHI
2895           v_out1 = phi <VECT_DEF>               # NEW_EXIT_PHI
2896           v_out2 = reduce <v_out1>
2897           s_out3 = extract_field <v_out2, 0>
2898           s_out4 = adjust_result <s_out3>
2899           use <s_out4>
2900           use <s_out4>
2901 */
2902
2903 static void
2904 vect_create_epilog_for_reduction (tree vect_def, gimple stmt,
2905                                   int ncopies,
2906                                   enum tree_code reduc_code,
2907                                   gimple reduction_phi,
2908                                   int reduc_index,
2909                                   bool double_reduc)
2910 {
2911   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2912   stmt_vec_info prev_phi_info;
2913   tree vectype;
2914   enum machine_mode mode;
2915   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2916   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo), *outer_loop = NULL;
2917   basic_block exit_bb;
2918   tree scalar_dest;
2919   tree scalar_type;
2920   gimple new_phi = NULL, phi;
2921   gimple_stmt_iterator exit_gsi;
2922   tree vec_dest;
2923   tree new_temp = NULL_TREE;
2924   tree new_name;
2925   gimple epilog_stmt = NULL;
2926   tree new_scalar_dest, new_dest;
2927   gimple exit_phi;
2928   tree bitsize, bitpos;
2929   enum tree_code code = gimple_assign_rhs_code (stmt);
2930   tree adjustment_def;
2931   tree vec_initial_def, def;
2932   tree orig_name;
2933   imm_use_iterator imm_iter;
2934   use_operand_p use_p;
2935   bool extract_scalar_result = false;
2936   tree reduction_op, expr;
2937   gimple orig_stmt;
2938   gimple use_stmt;
2939   bool nested_in_vect_loop = false;
2940   VEC(gimple,heap) *phis = NULL;
2941   enum vect_def_type dt = vect_unknown_def_type;
2942   int j, i;
2943
2944   if (nested_in_vect_loop_p (loop, stmt))
2945     {
2946       outer_loop = loop;
2947       loop = loop->inner;
2948       nested_in_vect_loop = true;
2949     }
2950
2951   switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
2952     {
2953     case GIMPLE_SINGLE_RHS:
2954       gcc_assert (TREE_OPERAND_LENGTH (gimple_assign_rhs1 (stmt))
2955                                        == ternary_op);
2956       reduction_op = TREE_OPERAND (gimple_assign_rhs1 (stmt), reduc_index);
2957       break;
2958     case GIMPLE_UNARY_RHS:
2959       reduction_op = gimple_assign_rhs1 (stmt);
2960       break;
2961     case GIMPLE_BINARY_RHS:
2962       reduction_op = reduc_index ?
2963                      gimple_assign_rhs2 (stmt) : gimple_assign_rhs1 (stmt);
2964       break;
2965     default:
2966       gcc_unreachable ();
2967     }
2968
2969   vectype = get_vectype_for_scalar_type (TREE_TYPE (reduction_op));
2970   gcc_assert (vectype);
2971   mode = TYPE_MODE (vectype);
2972
2973   /*** 1. Create the reduction def-use cycle  ***/
2974
2975   /* For the case of reduction, vect_get_vec_def_for_operand returns
2976      the scalar def before the loop, that defines the initial value
2977      of the reduction variable.  */
2978   vec_initial_def = vect_get_vec_def_for_operand (reduction_op, stmt,
2979                                                   &adjustment_def);
2980
2981   phi = reduction_phi;
2982   def = vect_def;
2983   for (j = 0; j < ncopies; j++)
2984     {
2985       /* 1.1 set the loop-entry arg of the reduction-phi:  */
2986       add_phi_arg (phi, vec_initial_def, loop_preheader_edge (loop),
2987                    UNKNOWN_LOCATION);
2988
2989       /* 1.2 set the loop-latch arg for the reduction-phi:  */
2990       if (j > 0)
2991         def = vect_get_vec_def_for_stmt_copy (dt, def);
2992       add_phi_arg (phi, def, loop_latch_edge (loop), UNKNOWN_LOCATION);
2993
2994       if (vect_print_dump_info (REPORT_DETAILS))
2995         {
2996           fprintf (vect_dump, "transform reduction: created def-use cycle: ");
2997           print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
2998           fprintf (vect_dump, "\n");
2999           print_gimple_stmt (vect_dump, SSA_NAME_DEF_STMT (def), 0, TDF_SLIM);
3000         }
3001
3002       phi = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (phi));
3003     }
3004
3005   /*** 2. Create epilog code
3006           The reduction epilog code operates across the elements of the vector
3007           of partial results computed by the vectorized loop.
3008           The reduction epilog code consists of:
3009           step 1: compute the scalar result in a vector (v_out2)
3010           step 2: extract the scalar result (s_out3) from the vector (v_out2)
3011           step 3: adjust the scalar result (s_out3) if needed.
3012
3013           Step 1 can be accomplished using one the following three schemes:
3014           (scheme 1) using reduc_code, if available.
3015           (scheme 2) using whole-vector shifts, if available.
3016           (scheme 3) using a scalar loop. In this case steps 1+2 above are
3017                      combined.
3018
3019           The overall epilog code looks like this:
3020
3021           s_out0 = phi <s_loop>         # original EXIT_PHI
3022           v_out1 = phi <VECT_DEF>       # NEW_EXIT_PHI
3023           v_out2 = reduce <v_out1>              # step 1
3024           s_out3 = extract_field <v_out2, 0>    # step 2
3025           s_out4 = adjust_result <s_out3>       # step 3
3026
3027           (step 3 is optional, and steps 1 and 2 may be combined).
3028           Lastly, the uses of s_out0 are replaced by s_out4.
3029
3030           ***/
3031
3032   /* 2.1 Create new loop-exit-phi to preserve loop-closed form:
3033         v_out1 = phi <v_loop>  */
3034
3035   exit_bb = single_exit (loop)->dest;
3036   def = vect_def;
3037   prev_phi_info = NULL;
3038   for (j = 0; j < ncopies; j++)
3039     {
3040       phi = create_phi_node (SSA_NAME_VAR (vect_def), exit_bb);
3041       set_vinfo_for_stmt (phi, new_stmt_vec_info (phi, loop_vinfo, NULL));
3042       if (j == 0)
3043         new_phi = phi;
3044       else
3045         {
3046           def = vect_get_vec_def_for_stmt_copy (dt, def);
3047           STMT_VINFO_RELATED_STMT (prev_phi_info) = phi;
3048         }
3049       SET_PHI_ARG_DEF (phi, single_exit (loop)->dest_idx, def);
3050       prev_phi_info = vinfo_for_stmt (phi);
3051     }
3052
3053   exit_gsi = gsi_after_labels (exit_bb);
3054
3055   /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
3056          (i.e. when reduc_code is not available) and in the final adjustment
3057          code (if needed).  Also get the original scalar reduction variable as
3058          defined in the loop.  In case STMT is a "pattern-stmt" (i.e. - it
3059          represents a reduction pattern), the tree-code and scalar-def are
3060          taken from the original stmt that the pattern-stmt (STMT) replaces.
3061          Otherwise (it is a regular reduction) - the tree-code and scalar-def
3062          are taken from STMT.  */
3063
3064   orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
3065   if (!orig_stmt)
3066     {
3067       /* Regular reduction  */
3068       orig_stmt = stmt;
3069     }
3070   else
3071     {
3072       /* Reduction pattern  */
3073       stmt_vec_info stmt_vinfo = vinfo_for_stmt (orig_stmt);
3074       gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo));
3075       gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo) == stmt);
3076     }
3077
3078   code = gimple_assign_rhs_code (orig_stmt);
3079   scalar_dest = gimple_assign_lhs (orig_stmt);
3080   scalar_type = TREE_TYPE (scalar_dest);
3081   new_scalar_dest = vect_create_destination_var (scalar_dest, NULL);
3082   bitsize = TYPE_SIZE (scalar_type);
3083
3084   /* For MINUS_EXPR the initial vector is [init_val,0,...,0], therefore,
3085      partial results are added and not subtracted.  */
3086   if (code == MINUS_EXPR)
3087     code = PLUS_EXPR;
3088
3089   /* In case this is a reduction in an inner-loop while vectorizing an outer
3090      loop - we don't need to extract a single scalar result at the end of the
3091      inner-loop (unless it is double reduction, i.e., the use of reduction is
3092      outside the outer-loop). The final vector of partial results will be used
3093      in the vectorized outer-loop, or reduced to a scalar result at the end of
3094      the outer-loop.  */
3095   if (nested_in_vect_loop && !double_reduc)
3096     goto vect_finalize_reduction;
3097
3098   /* The epilogue is created for the outer-loop, i.e., for the loop being
3099      vectorized.  */
3100   if (double_reduc)
3101     loop = outer_loop;
3102
3103   /* FORNOW */
3104   gcc_assert (ncopies == 1);
3105
3106   /* 2.3 Create the reduction code, using one of the three schemes described
3107          above.  */
3108
3109   if (reduc_code != ERROR_MARK)
3110     {
3111       tree tmp;
3112
3113       /*** Case 1:  Create:
3114            v_out2 = reduc_expr <v_out1>  */
3115
3116       if (vect_print_dump_info (REPORT_DETAILS))
3117         fprintf (vect_dump, "Reduce using direct vector reduction.");
3118
3119       vec_dest = vect_create_destination_var (scalar_dest, vectype);
3120       tmp = build1 (reduc_code, vectype,  PHI_RESULT (new_phi));
3121       epilog_stmt = gimple_build_assign (vec_dest, tmp);
3122       new_temp = make_ssa_name (vec_dest, epilog_stmt);
3123       gimple_assign_set_lhs (epilog_stmt, new_temp);
3124       gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3125
3126       extract_scalar_result = true;
3127     }
3128   else
3129     {
3130       enum tree_code shift_code = ERROR_MARK;
3131       bool have_whole_vector_shift = true;
3132       int bit_offset;
3133       int element_bitsize = tree_low_cst (bitsize, 1);
3134       int vec_size_in_bits = tree_low_cst (TYPE_SIZE (vectype), 1);
3135       tree vec_temp;
3136
3137       if (optab_handler (vec_shr_optab, mode)->insn_code != CODE_FOR_nothing)
3138         shift_code = VEC_RSHIFT_EXPR;
3139       else
3140         have_whole_vector_shift = false;
3141
3142       /* Regardless of whether we have a whole vector shift, if we're
3143          emulating the operation via tree-vect-generic, we don't want
3144          to use it.  Only the first round of the reduction is likely
3145          to still be profitable via emulation.  */
3146       /* ??? It might be better to emit a reduction tree code here, so that
3147          tree-vect-generic can expand the first round via bit tricks.  */
3148       if (!VECTOR_MODE_P (mode))
3149         have_whole_vector_shift = false;
3150       else
3151         {
3152           optab optab = optab_for_tree_code (code, vectype, optab_default);
3153           if (optab_handler (optab, mode)->insn_code == CODE_FOR_nothing)
3154             have_whole_vector_shift = false;
3155         }
3156
3157       if (have_whole_vector_shift)
3158         {
3159           /*** Case 2: Create:
3160              for (offset = VS/2; offset >= element_size; offset/=2)
3161                 {
3162                   Create:  va' = vec_shift <va, offset>
3163                   Create:  va = vop <va, va'>
3164                 }  */
3165
3166           if (vect_print_dump_info (REPORT_DETAILS))
3167             fprintf (vect_dump, "Reduce using vector shifts");
3168
3169           vec_dest = vect_create_destination_var (scalar_dest, vectype);
3170           new_temp = PHI_RESULT (new_phi);
3171
3172           for (bit_offset = vec_size_in_bits/2;
3173                bit_offset >= element_bitsize;
3174                bit_offset /= 2)
3175             {
3176               tree bitpos = size_int (bit_offset);
3177
3178               epilog_stmt = gimple_build_assign_with_ops (shift_code, vec_dest,
3179                                                           new_temp, bitpos);
3180               new_name = make_ssa_name (vec_dest, epilog_stmt);
3181               gimple_assign_set_lhs (epilog_stmt, new_name);
3182               gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3183
3184               epilog_stmt = gimple_build_assign_with_ops (code, vec_dest,
3185                                                           new_name, new_temp);
3186               new_temp = make_ssa_name (vec_dest, epilog_stmt);
3187               gimple_assign_set_lhs (epilog_stmt, new_temp);
3188               gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3189             }
3190
3191           extract_scalar_result = true;
3192         }
3193       else
3194         {
3195           tree rhs;
3196
3197           /*** Case 3: Create:
3198              s = extract_field <v_out2, 0>
3199              for (offset = element_size;
3200                   offset < vector_size;
3201                   offset += element_size;)
3202                {
3203                  Create:  s' = extract_field <v_out2, offset>
3204                  Create:  s = op <s, s'>
3205                }  */
3206
3207           if (vect_print_dump_info (REPORT_DETAILS))
3208             fprintf (vect_dump, "Reduce using scalar code. ");
3209
3210           vec_temp = PHI_RESULT (new_phi);
3211           vec_size_in_bits = tree_low_cst (TYPE_SIZE (vectype), 1);
3212           rhs = build3 (BIT_FIELD_REF, scalar_type, vec_temp, bitsize,
3213                          bitsize_zero_node);
3214           epilog_stmt = gimple_build_assign (new_scalar_dest, rhs);
3215           new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
3216           gimple_assign_set_lhs (epilog_stmt, new_temp);
3217           gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3218
3219           for (bit_offset = element_bitsize;
3220                bit_offset < vec_size_in_bits;
3221                bit_offset += element_bitsize)
3222             {
3223               tree bitpos = bitsize_int (bit_offset);
3224               tree rhs = build3 (BIT_FIELD_REF, scalar_type, vec_temp, bitsize,
3225                                  bitpos);
3226
3227               epilog_stmt = gimple_build_assign (new_scalar_dest, rhs);
3228               new_name = make_ssa_name (new_scalar_dest, epilog_stmt);
3229               gimple_assign_set_lhs (epilog_stmt, new_name);
3230               gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3231
3232               epilog_stmt = gimple_build_assign_with_ops (code,
3233                                                           new_scalar_dest,
3234                                                           new_name, new_temp);
3235               new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
3236               gimple_assign_set_lhs (epilog_stmt, new_temp);
3237               gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3238             }
3239
3240           extract_scalar_result = false;
3241         }
3242     }
3243
3244   /* 2.4  Extract the final scalar result.  Create:
3245          s_out3 = extract_field <v_out2, bitpos>  */
3246
3247   if (extract_scalar_result)
3248     {
3249       tree rhs;
3250
3251       gcc_assert (!nested_in_vect_loop || double_reduc);
3252       if (vect_print_dump_info (REPORT_DETAILS))
3253         fprintf (vect_dump, "extract scalar result");
3254
3255       if (BYTES_BIG_ENDIAN)
3256         bitpos = size_binop (MULT_EXPR,
3257                        bitsize_int (TYPE_VECTOR_SUBPARTS (vectype) - 1),
3258                        TYPE_SIZE (scalar_type));
3259       else
3260         bitpos = bitsize_zero_node;
3261
3262       rhs = build3 (BIT_FIELD_REF, scalar_type, new_temp, bitsize, bitpos);
3263       epilog_stmt = gimple_build_assign (new_scalar_dest, rhs);
3264       new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
3265       gimple_assign_set_lhs (epilog_stmt, new_temp);
3266       gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3267     }
3268
3269 vect_finalize_reduction:
3270
3271   if (double_reduc)
3272     loop = loop->inner;
3273
3274   /* 2.5 Adjust the final result by the initial value of the reduction
3275          variable. (When such adjustment is not needed, then
3276          'adjustment_def' is zero).  For example, if code is PLUS we create:
3277          new_temp = loop_exit_def + adjustment_def  */
3278
3279   if (adjustment_def)
3280     {
3281       if (nested_in_vect_loop)
3282         {
3283           gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def)) == VECTOR_TYPE);
3284           expr = build2 (code, vectype, PHI_RESULT (new_phi), adjustment_def);
3285           new_dest = vect_create_destination_var (scalar_dest, vectype);
3286         }
3287       else
3288         {
3289           gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def)) != VECTOR_TYPE);
3290           expr = build2 (code, scalar_type, new_temp, adjustment_def);
3291           new_dest = vect_create_destination_var (scalar_dest, scalar_type);
3292         }
3293
3294       epilog_stmt = gimple_build_assign (new_dest, expr);
3295       new_temp = make_ssa_name (new_dest, epilog_stmt);
3296       gimple_assign_set_lhs (epilog_stmt, new_temp);
3297       SSA_NAME_DEF_STMT (new_temp) = epilog_stmt;
3298       gsi_insert_before (&exit_gsi, epilog_stmt, GSI_SAME_STMT);
3299     }
3300
3301
3302   /* 2.6  Handle the loop-exit phi  */
3303
3304   /* Replace uses of s_out0 with uses of s_out3:
3305      Find the loop-closed-use at the loop exit of the original scalar result.
3306      (The reduction result is expected to have two immediate uses - one at the
3307      latch block, and one at the loop exit).  */
3308   phis = VEC_alloc (gimple, heap, 10);
3309   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, scalar_dest)
3310     {
3311       if (!flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
3312         {
3313           exit_phi = USE_STMT (use_p);
3314           VEC_quick_push (gimple, phis, exit_phi);
3315         }
3316     }
3317
3318   /* We expect to have found an exit_phi because of loop-closed-ssa form.  */
3319   gcc_assert (!VEC_empty (gimple, phis));
3320
3321   for (i = 0; VEC_iterate (gimple, phis, i, exit_phi); i++)
3322     {
3323       if (nested_in_vect_loop)
3324         {
3325           stmt_vec_info stmt_vinfo = vinfo_for_stmt (exit_phi);
3326           gimple vect_phi;
3327
3328           /* FORNOW. Currently not supporting the case that an inner-loop
3329              reduction is not used in the outer-loop (but only outside the
3330              outer-loop), unless it is double reduction.  */
3331           gcc_assert ((STMT_VINFO_RELEVANT_P (stmt_vinfo)
3332                       && !STMT_VINFO_LIVE_P (stmt_vinfo)) || double_reduc);
3333
3334           epilog_stmt = adjustment_def ? epilog_stmt : new_phi;
3335           STMT_VINFO_VEC_STMT (stmt_vinfo) = epilog_stmt;
3336           set_vinfo_for_stmt (epilog_stmt,
3337                               new_stmt_vec_info (epilog_stmt, loop_vinfo,
3338                                                  NULL));
3339           if (adjustment_def)
3340             STMT_VINFO_RELATED_STMT (vinfo_for_stmt (epilog_stmt)) =
3341                 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (new_phi));
3342
3343           if (!double_reduc
3344               || STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_double_reduction_def)
3345             continue;
3346
3347           /* Handle double reduction:
3348
3349              stmt1: s1 = phi <s0, s2>  - double reduction phi (outer loop)
3350              stmt2:   s3 = phi <s1, s4> - (regular) reduction phi (inner loop)
3351              stmt3:   s4 = use (s3)     - (regular) reduction stmt (inner loop)
3352              stmt4: s2 = phi <s4>      - double reduction stmt (outer loop)
3353
3354              At that point the regular reduction (stmt2 and stmt3) is already
3355              vectorized, as well as the exit phi node, stmt4.
3356              Here we vectorize the phi node of double reduction, stmt1, and
3357              update all relevant statements.  */
3358
3359           /* Go through all the uses of s2 to find double reduction phi node,
3360              i.e., stmt1 above.  */
3361           orig_name = PHI_RESULT (exit_phi);
3362           FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, orig_name)
3363             {
3364               stmt_vec_info use_stmt_vinfo = vinfo_for_stmt (use_stmt);
3365               stmt_vec_info new_phi_vinfo;
3366               tree vect_phi_init, preheader_arg, vect_phi_res, init_def;
3367               basic_block bb = gimple_bb (use_stmt);
3368               gimple use;
3369
3370               /* Check that USE_STMT is really double reduction phi node.  */
3371               if (gimple_code (use_stmt) != GIMPLE_PHI
3372                   || gimple_phi_num_args (use_stmt) != 2
3373                   || !use_stmt_vinfo
3374                   || STMT_VINFO_DEF_TYPE (use_stmt_vinfo)
3375                       != vect_double_reduction_def
3376                   || bb->loop_father != outer_loop)
3377                 continue;
3378
3379               /* Create vector phi node for double reduction:
3380                  vs1 = phi <vs0, vs2>
3381                  vs1 was created previously in this function by a call to
3382                  vect_get_vec_def_for_operand and is stored in vec_initial_def;
3383                  vs2 is defined by EPILOG_STMT, the vectorized EXIT_PHI;
3384                  vs0 is created here.  */
3385
3386               /* Create vector phi node.  */
3387               vect_phi = create_phi_node (vec_initial_def, bb);
3388               new_phi_vinfo = new_stmt_vec_info (vect_phi,
3389                                     loop_vec_info_for_loop (outer_loop), NULL);
3390               set_vinfo_for_stmt (vect_phi, new_phi_vinfo);
3391
3392               /* Create vs0 - initial def of the double reduction phi.  */
3393               preheader_arg = PHI_ARG_DEF_FROM_EDGE (use_stmt,
3394                                              loop_preheader_edge (outer_loop));
3395               init_def = get_initial_def_for_reduction (stmt, preheader_arg,
3396                                                         NULL);
3397               vect_phi_init = vect_init_vector (use_stmt, init_def, vectype,