OSDN Git Service

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