OSDN Git Service

f0b3dae719cd7ecfe0dbb392f193aec92d930b97
[pf3gnuchains/gcc-fork.git] / gcc / tree-vect-stmts.c
1 /* Statement Analysis and Transformation for 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>
5    and 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 "target.h"
30 #include "basic-block.h"
31 #include "tree-pretty-print.h"
32 #include "gimple-pretty-print.h"
33 #include "tree-flow.h"
34 #include "tree-dump.h"
35 #include "cfgloop.h"
36 #include "cfglayout.h"
37 #include "expr.h"
38 #include "recog.h"
39 #include "optabs.h"
40 #include "diagnostic-core.h"
41 #include "tree-vectorizer.h"
42 #include "langhooks.h"
43
44
45 /* Return a variable of type ELEM_TYPE[NELEMS].  */
46
47 static tree
48 create_vector_array (tree elem_type, unsigned HOST_WIDE_INT nelems)
49 {
50   return create_tmp_var (build_array_type_nelts (elem_type, nelems),
51                          "vect_array");
52 }
53
54 /* ARRAY is an array of vectors created by create_vector_array.
55    Return an SSA_NAME for the vector in index N.  The reference
56    is part of the vectorization of STMT and the vector is associated
57    with scalar destination SCALAR_DEST.  */
58
59 static tree
60 read_vector_array (gimple stmt, gimple_stmt_iterator *gsi, tree scalar_dest,
61                    tree array, unsigned HOST_WIDE_INT n)
62 {
63   tree vect_type, vect, vect_name, array_ref;
64   gimple new_stmt;
65
66   gcc_assert (TREE_CODE (TREE_TYPE (array)) == ARRAY_TYPE);
67   vect_type = TREE_TYPE (TREE_TYPE (array));
68   vect = vect_create_destination_var (scalar_dest, vect_type);
69   array_ref = build4 (ARRAY_REF, vect_type, array,
70                       build_int_cst (size_type_node, n),
71                       NULL_TREE, NULL_TREE);
72
73   new_stmt = gimple_build_assign (vect, array_ref);
74   vect_name = make_ssa_name (vect, new_stmt);
75   gimple_assign_set_lhs (new_stmt, vect_name);
76   vect_finish_stmt_generation (stmt, new_stmt, gsi);
77   mark_symbols_for_renaming (new_stmt);
78
79   return vect_name;
80 }
81
82 /* ARRAY is an array of vectors created by create_vector_array.
83    Emit code to store SSA_NAME VECT in index N of the array.
84    The store is part of the vectorization of STMT.  */
85
86 static void
87 write_vector_array (gimple stmt, gimple_stmt_iterator *gsi, tree vect,
88                     tree array, unsigned HOST_WIDE_INT n)
89 {
90   tree array_ref;
91   gimple new_stmt;
92
93   array_ref = build4 (ARRAY_REF, TREE_TYPE (vect), array,
94                       build_int_cst (size_type_node, n),
95                       NULL_TREE, NULL_TREE);
96
97   new_stmt = gimple_build_assign (array_ref, vect);
98   vect_finish_stmt_generation (stmt, new_stmt, gsi);
99   mark_symbols_for_renaming (new_stmt);
100 }
101
102 /* PTR is a pointer to an array of type TYPE.  Return a representation
103    of *PTR.  The memory reference replaces those in FIRST_DR
104    (and its group).  */
105
106 static tree
107 create_array_ref (tree type, tree ptr, struct data_reference *first_dr)
108 {
109   struct ptr_info_def *pi;
110   tree mem_ref, alias_ptr_type;
111
112   alias_ptr_type = reference_alias_ptr_type (DR_REF (first_dr));
113   mem_ref = build2 (MEM_REF, type, ptr, build_int_cst (alias_ptr_type, 0));
114   /* Arrays have the same alignment as their type.  */
115   pi = get_ptr_info (ptr);
116   pi->align = TYPE_ALIGN_UNIT (type);
117   pi->misalign = 0;
118   return mem_ref;
119 }
120
121 /* Utility functions used by vect_mark_stmts_to_be_vectorized.  */
122
123 /* Function vect_mark_relevant.
124
125    Mark STMT as "relevant for vectorization" and add it to WORKLIST.  */
126
127 static void
128 vect_mark_relevant (VEC(gimple,heap) **worklist, gimple stmt,
129                     enum vect_relevant relevant, bool live_p,
130                     bool used_in_pattern)
131 {
132   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
133   enum vect_relevant save_relevant = STMT_VINFO_RELEVANT (stmt_info);
134   bool save_live_p = STMT_VINFO_LIVE_P (stmt_info);
135   gimple pattern_stmt;
136
137   if (vect_print_dump_info (REPORT_DETAILS))
138     fprintf (vect_dump, "mark relevant %d, live %d.", relevant, live_p);
139
140   /* If this stmt is an original stmt in a pattern, we might need to mark its
141      related pattern stmt instead of the original stmt.  However, such stmts
142      may have their own uses that are not in any pattern, in such cases the
143      stmt itself should be marked.  */
144   if (STMT_VINFO_IN_PATTERN_P (stmt_info))
145     {
146       bool found = false;
147       if (!used_in_pattern)
148         {
149           imm_use_iterator imm_iter;
150           use_operand_p use_p;
151           gimple use_stmt;
152           tree lhs;
153           loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
154           struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
155
156           if (is_gimple_assign (stmt))
157             lhs = gimple_assign_lhs (stmt);
158           else
159             lhs = gimple_call_lhs (stmt);
160
161           /* This use is out of pattern use, if LHS has other uses that are
162              pattern uses, we should mark the stmt itself, and not the pattern
163              stmt.  */
164           if (TREE_CODE (lhs) == SSA_NAME)
165             FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
166               {
167                 if (is_gimple_debug (USE_STMT (use_p)))
168                   continue;
169                 use_stmt = USE_STMT (use_p);
170
171                 if (!flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
172                   continue;
173
174                 if (vinfo_for_stmt (use_stmt)
175                     && STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (use_stmt)))
176                   {
177                     found = true;
178                     break;
179                   }
180               }
181         }
182
183       if (!found)
184         {
185           /* This is the last stmt in a sequence that was detected as a
186              pattern that can potentially be vectorized.  Don't mark the stmt
187              as relevant/live because it's not going to be vectorized.
188              Instead mark the pattern-stmt that replaces it.  */
189
190           pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
191
192           if (vect_print_dump_info (REPORT_DETAILS))
193             fprintf (vect_dump, "last stmt in pattern. don't mark"
194                                 " relevant/live.");
195           stmt_info = vinfo_for_stmt (pattern_stmt);
196           gcc_assert (STMT_VINFO_RELATED_STMT (stmt_info) == stmt);
197           save_relevant = STMT_VINFO_RELEVANT (stmt_info);
198           save_live_p = STMT_VINFO_LIVE_P (stmt_info);
199           stmt = pattern_stmt;
200         }
201     }
202
203   STMT_VINFO_LIVE_P (stmt_info) |= live_p;
204   if (relevant > STMT_VINFO_RELEVANT (stmt_info))
205     STMT_VINFO_RELEVANT (stmt_info) = relevant;
206
207   if (STMT_VINFO_RELEVANT (stmt_info) == save_relevant
208       && STMT_VINFO_LIVE_P (stmt_info) == save_live_p)
209     {
210       if (vect_print_dump_info (REPORT_DETAILS))
211         fprintf (vect_dump, "already marked relevant/live.");
212       return;
213     }
214
215   VEC_safe_push (gimple, heap, *worklist, stmt);
216 }
217
218
219 /* Function vect_stmt_relevant_p.
220
221    Return true if STMT in loop that is represented by LOOP_VINFO is
222    "relevant for vectorization".
223
224    A stmt is considered "relevant for vectorization" if:
225    - it has uses outside the loop.
226    - it has vdefs (it alters memory).
227    - control stmts in the loop (except for the exit condition).
228
229    CHECKME: what other side effects would the vectorizer allow?  */
230
231 static bool
232 vect_stmt_relevant_p (gimple stmt, loop_vec_info loop_vinfo,
233                       enum vect_relevant *relevant, bool *live_p)
234 {
235   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
236   ssa_op_iter op_iter;
237   imm_use_iterator imm_iter;
238   use_operand_p use_p;
239   def_operand_p def_p;
240
241   *relevant = vect_unused_in_scope;
242   *live_p = false;
243
244   /* cond stmt other than loop exit cond.  */
245   if (is_ctrl_stmt (stmt)
246       && STMT_VINFO_TYPE (vinfo_for_stmt (stmt))
247          != loop_exit_ctrl_vec_info_type)
248     *relevant = vect_used_in_scope;
249
250   /* changing memory.  */
251   if (gimple_code (stmt) != GIMPLE_PHI)
252     if (gimple_vdef (stmt))
253       {
254         if (vect_print_dump_info (REPORT_DETAILS))
255           fprintf (vect_dump, "vec_stmt_relevant_p: stmt has vdefs.");
256         *relevant = vect_used_in_scope;
257       }
258
259   /* uses outside the loop.  */
260   FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_DEF)
261     {
262       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
263         {
264           basic_block bb = gimple_bb (USE_STMT (use_p));
265           if (!flow_bb_inside_loop_p (loop, bb))
266             {
267               if (vect_print_dump_info (REPORT_DETAILS))
268                 fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop.");
269
270               if (is_gimple_debug (USE_STMT (use_p)))
271                 continue;
272
273               /* We expect all such uses to be in the loop exit phis
274                  (because of loop closed form)   */
275               gcc_assert (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI);
276               gcc_assert (bb == single_exit (loop)->dest);
277
278               *live_p = true;
279             }
280         }
281     }
282
283   return (*live_p || *relevant);
284 }
285
286
287 /* Function exist_non_indexing_operands_for_use_p
288
289    USE is one of the uses attached to STMT.  Check if USE is
290    used in STMT for anything other than indexing an array.  */
291
292 static bool
293 exist_non_indexing_operands_for_use_p (tree use, gimple stmt)
294 {
295   tree operand;
296   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
297
298   /* USE corresponds to some operand in STMT.  If there is no data
299      reference in STMT, then any operand that corresponds to USE
300      is not indexing an array.  */
301   if (!STMT_VINFO_DATA_REF (stmt_info))
302     return true;
303
304   /* STMT has a data_ref. FORNOW this means that its of one of
305      the following forms:
306      -1- ARRAY_REF = var
307      -2- var = ARRAY_REF
308      (This should have been verified in analyze_data_refs).
309
310      'var' in the second case corresponds to a def, not a use,
311      so USE cannot correspond to any operands that are not used
312      for array indexing.
313
314      Therefore, all we need to check is if STMT falls into the
315      first case, and whether var corresponds to USE.  */
316
317   if (!gimple_assign_copy_p (stmt))
318     return false;
319   if (TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
320     return false;
321   operand = gimple_assign_rhs1 (stmt);
322   if (TREE_CODE (operand) != SSA_NAME)
323     return false;
324
325   if (operand == use)
326     return true;
327
328   return false;
329 }
330
331
332 /*
333    Function process_use.
334
335    Inputs:
336    - a USE in STMT in a loop represented by LOOP_VINFO
337    - LIVE_P, RELEVANT - enum values to be set in the STMT_VINFO of the stmt
338      that defined USE.  This is done by calling mark_relevant and passing it
339      the WORKLIST (to add DEF_STMT to the WORKLIST in case it is relevant).
340    - FORCE is true if exist_non_indexing_operands_for_use_p check shouldn't
341      be performed.
342
343    Outputs:
344    Generally, LIVE_P and RELEVANT are used to define the liveness and
345    relevance info of the DEF_STMT of this USE:
346        STMT_VINFO_LIVE_P (DEF_STMT_info) <-- live_p
347        STMT_VINFO_RELEVANT (DEF_STMT_info) <-- relevant
348    Exceptions:
349    - case 1: If USE is used only for address computations (e.g. array indexing),
350    which does not need to be directly vectorized, then the liveness/relevance
351    of the respective DEF_STMT is left unchanged.
352    - case 2: If STMT is a reduction phi and DEF_STMT is a reduction stmt, we
353    skip DEF_STMT cause it had already been processed.
354    - case 3: If DEF_STMT and STMT are in different nests, then  "relevant" will
355    be modified accordingly.
356
357    Return true if everything is as expected. Return false otherwise.  */
358
359 static bool
360 process_use (gimple stmt, tree use, loop_vec_info loop_vinfo, bool live_p,
361              enum vect_relevant relevant, VEC(gimple,heap) **worklist,
362              bool force)
363 {
364   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
365   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
366   stmt_vec_info dstmt_vinfo;
367   basic_block bb, def_bb;
368   tree def;
369   gimple def_stmt;
370   enum vect_def_type dt;
371
372   /* case 1: we are only interested in uses that need to be vectorized.  Uses
373      that are used for address computation are not considered relevant.  */
374   if (!force && !exist_non_indexing_operands_for_use_p (use, stmt))
375      return true;
376
377   if (!vect_is_simple_use (use, stmt, loop_vinfo, NULL, &def_stmt, &def, &dt))
378     {
379       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
380         fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
381       return false;
382     }
383
384   if (!def_stmt || gimple_nop_p (def_stmt))
385     return true;
386
387   def_bb = gimple_bb (def_stmt);
388   if (!flow_bb_inside_loop_p (loop, def_bb))
389     {
390       if (vect_print_dump_info (REPORT_DETAILS))
391         fprintf (vect_dump, "def_stmt is out of loop.");
392       return true;
393     }
394
395   /* case 2: A reduction phi (STMT) defined by a reduction stmt (DEF_STMT).
396      DEF_STMT must have already been processed, because this should be the
397      only way that STMT, which is a reduction-phi, was put in the worklist,
398      as there should be no other uses for DEF_STMT in the loop.  So we just
399      check that everything is as expected, and we are done.  */
400   dstmt_vinfo = vinfo_for_stmt (def_stmt);
401   bb = gimple_bb (stmt);
402   if (gimple_code (stmt) == GIMPLE_PHI
403       && STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def
404       && gimple_code (def_stmt) != GIMPLE_PHI
405       && STMT_VINFO_DEF_TYPE (dstmt_vinfo) == vect_reduction_def
406       && bb->loop_father == def_bb->loop_father)
407     {
408       if (vect_print_dump_info (REPORT_DETAILS))
409         fprintf (vect_dump, "reduc-stmt defining reduc-phi in the same nest.");
410       if (STMT_VINFO_IN_PATTERN_P (dstmt_vinfo))
411         dstmt_vinfo = vinfo_for_stmt (STMT_VINFO_RELATED_STMT (dstmt_vinfo));
412       gcc_assert (STMT_VINFO_RELEVANT (dstmt_vinfo) < vect_used_by_reduction);
413       gcc_assert (STMT_VINFO_LIVE_P (dstmt_vinfo)
414                   || STMT_VINFO_RELEVANT (dstmt_vinfo) > vect_unused_in_scope);
415       return true;
416     }
417
418   /* case 3a: outer-loop stmt defining an inner-loop stmt:
419         outer-loop-header-bb:
420                 d = def_stmt
421         inner-loop:
422                 stmt # use (d)
423         outer-loop-tail-bb:
424                 ...               */
425   if (flow_loop_nested_p (def_bb->loop_father, bb->loop_father))
426     {
427       if (vect_print_dump_info (REPORT_DETAILS))
428         fprintf (vect_dump, "outer-loop def-stmt defining inner-loop stmt.");
429
430       switch (relevant)
431         {
432         case vect_unused_in_scope:
433           relevant = (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_nested_cycle) ?
434                       vect_used_in_scope : vect_unused_in_scope;
435           break;
436
437         case vect_used_in_outer_by_reduction:
438           gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def);
439           relevant = vect_used_by_reduction;
440           break;
441
442         case vect_used_in_outer:
443           gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def);
444           relevant = vect_used_in_scope;
445           break;
446
447         case vect_used_in_scope:
448           break;
449
450         default:
451           gcc_unreachable ();
452         }
453     }
454
455   /* case 3b: inner-loop stmt defining an outer-loop stmt:
456         outer-loop-header-bb:
457                 ...
458         inner-loop:
459                 d = def_stmt
460         outer-loop-tail-bb (or outer-loop-exit-bb in double reduction):
461                 stmt # use (d)          */
462   else if (flow_loop_nested_p (bb->loop_father, def_bb->loop_father))
463     {
464       if (vect_print_dump_info (REPORT_DETAILS))
465         fprintf (vect_dump, "inner-loop def-stmt defining outer-loop stmt.");
466
467       switch (relevant)
468         {
469         case vect_unused_in_scope:
470           relevant = (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def
471             || STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_double_reduction_def) ?
472                       vect_used_in_outer_by_reduction : vect_unused_in_scope;
473           break;
474
475         case vect_used_by_reduction:
476           relevant = vect_used_in_outer_by_reduction;
477           break;
478
479         case vect_used_in_scope:
480           relevant = vect_used_in_outer;
481           break;
482
483         default:
484           gcc_unreachable ();
485         }
486     }
487
488   vect_mark_relevant (worklist, def_stmt, relevant, live_p,
489                       is_pattern_stmt_p (stmt_vinfo));
490   return true;
491 }
492
493
494 /* Function vect_mark_stmts_to_be_vectorized.
495
496    Not all stmts in the loop need to be vectorized. For example:
497
498      for i...
499        for j...
500    1.    T0 = i + j
501    2.    T1 = a[T0]
502
503    3.    j = j + 1
504
505    Stmt 1 and 3 do not need to be vectorized, because loop control and
506    addressing of vectorized data-refs are handled differently.
507
508    This pass detects such stmts.  */
509
510 bool
511 vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo)
512 {
513   VEC(gimple,heap) *worklist;
514   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
515   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
516   unsigned int nbbs = loop->num_nodes;
517   gimple_stmt_iterator si;
518   gimple stmt;
519   unsigned int i;
520   stmt_vec_info stmt_vinfo;
521   basic_block bb;
522   gimple phi;
523   bool live_p;
524   enum vect_relevant relevant, tmp_relevant;
525   enum vect_def_type def_type;
526
527   if (vect_print_dump_info (REPORT_DETAILS))
528     fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ===");
529
530   worklist = VEC_alloc (gimple, heap, 64);
531
532   /* 1. Init worklist.  */
533   for (i = 0; i < nbbs; i++)
534     {
535       bb = bbs[i];
536       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
537         {
538           phi = gsi_stmt (si);
539           if (vect_print_dump_info (REPORT_DETAILS))
540             {
541               fprintf (vect_dump, "init: phi relevant? ");
542               print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
543             }
544
545           if (vect_stmt_relevant_p (phi, loop_vinfo, &relevant, &live_p))
546             vect_mark_relevant (&worklist, phi, relevant, live_p, false);
547         }
548       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
549         {
550           stmt = gsi_stmt (si);
551           if (vect_print_dump_info (REPORT_DETAILS))
552             {
553               fprintf (vect_dump, "init: stmt relevant? ");
554               print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
555             }
556
557           if (vect_stmt_relevant_p (stmt, loop_vinfo, &relevant, &live_p))
558             vect_mark_relevant (&worklist, stmt, relevant, live_p, false);
559         }
560     }
561
562   /* 2. Process_worklist */
563   while (VEC_length (gimple, worklist) > 0)
564     {
565       use_operand_p use_p;
566       ssa_op_iter iter;
567
568       stmt = VEC_pop (gimple, worklist);
569       if (vect_print_dump_info (REPORT_DETAILS))
570         {
571           fprintf (vect_dump, "worklist: examine stmt: ");
572           print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
573         }
574
575       /* Examine the USEs of STMT. For each USE, mark the stmt that defines it
576          (DEF_STMT) as relevant/irrelevant and live/dead according to the
577          liveness and relevance properties of STMT.  */
578       stmt_vinfo = vinfo_for_stmt (stmt);
579       relevant = STMT_VINFO_RELEVANT (stmt_vinfo);
580       live_p = STMT_VINFO_LIVE_P (stmt_vinfo);
581
582       /* Generally, the liveness and relevance properties of STMT are
583          propagated as is to the DEF_STMTs of its USEs:
584           live_p <-- STMT_VINFO_LIVE_P (STMT_VINFO)
585           relevant <-- STMT_VINFO_RELEVANT (STMT_VINFO)
586
587          One exception is when STMT has been identified as defining a reduction
588          variable; in this case we set the liveness/relevance as follows:
589            live_p = false
590            relevant = vect_used_by_reduction
591          This is because we distinguish between two kinds of relevant stmts -
592          those that are used by a reduction computation, and those that are
593          (also) used by a regular computation.  This allows us later on to
594          identify stmts that are used solely by a reduction, and therefore the
595          order of the results that they produce does not have to be kept.  */
596
597       def_type = STMT_VINFO_DEF_TYPE (stmt_vinfo);
598       tmp_relevant = relevant;
599       switch (def_type)
600         {
601           case vect_reduction_def:
602             switch (tmp_relevant)
603               {
604                 case vect_unused_in_scope:
605                   relevant = vect_used_by_reduction;
606                   break;
607
608                 case vect_used_by_reduction:
609                   if (gimple_code (stmt) == GIMPLE_PHI)
610                     break;
611                   /* fall through */
612
613                 default:
614                   if (vect_print_dump_info (REPORT_DETAILS))
615                     fprintf (vect_dump, "unsupported use of reduction.");
616
617                   VEC_free (gimple, heap, worklist);
618                   return false;
619               }
620
621             live_p = false;
622             break;
623
624           case vect_nested_cycle:
625             if (tmp_relevant != vect_unused_in_scope
626                 && tmp_relevant != vect_used_in_outer_by_reduction
627                 && tmp_relevant != vect_used_in_outer)
628               {
629                 if (vect_print_dump_info (REPORT_DETAILS))
630                   fprintf (vect_dump, "unsupported use of nested cycle.");
631
632                 VEC_free (gimple, heap, worklist);
633                 return false;
634               }
635
636             live_p = false;
637             break;
638
639           case vect_double_reduction_def:
640             if (tmp_relevant != vect_unused_in_scope
641                 && tmp_relevant != vect_used_by_reduction)
642               {
643                 if (vect_print_dump_info (REPORT_DETAILS))
644                   fprintf (vect_dump, "unsupported use of double reduction.");
645
646                 VEC_free (gimple, heap, worklist);
647                 return false;
648               }
649
650             live_p = false;
651             break;
652
653           default:
654             break;
655         }
656
657       if (is_pattern_stmt_p (stmt_vinfo))
658         {
659           /* Pattern statements are not inserted into the code, so
660              FOR_EACH_PHI_OR_STMT_USE optimizes their operands out, and we
661              have to scan the RHS or function arguments instead.  */
662           if (is_gimple_assign (stmt))
663             {
664               enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
665               tree op = gimple_assign_rhs1 (stmt);
666
667               i = 1;
668               if (rhs_code == COND_EXPR && COMPARISON_CLASS_P (op))
669                 {
670                   if (!process_use (stmt, TREE_OPERAND (op, 0), loop_vinfo,
671                                     live_p, relevant, &worklist, false)
672                       || !process_use (stmt, TREE_OPERAND (op, 1), loop_vinfo,
673                                        live_p, relevant, &worklist, false))
674                     {
675                       VEC_free (gimple, heap, worklist);
676                       return false;
677                     }
678                   i = 2;
679                 }
680               for (; i < gimple_num_ops (stmt); i++)
681                 {
682                   op = gimple_op (stmt, i);
683                   if (!process_use (stmt, op, loop_vinfo, live_p, relevant,
684                                     &worklist, false))
685                     {
686                       VEC_free (gimple, heap, worklist);
687                       return false;
688                     }
689                  }
690             }
691           else if (is_gimple_call (stmt))
692             {
693               for (i = 0; i < gimple_call_num_args (stmt); i++)
694                 {
695                   tree arg = gimple_call_arg (stmt, i);
696                   if (!process_use (stmt, arg, loop_vinfo, live_p, relevant,
697                                     &worklist, false))
698                     {
699                       VEC_free (gimple, heap, worklist);
700                       return false;
701                     }
702                 }
703             }
704         }
705       else
706         FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
707           {
708             tree op = USE_FROM_PTR (use_p);
709             if (!process_use (stmt, op, loop_vinfo, live_p, relevant,
710                               &worklist, false))
711               {
712                 VEC_free (gimple, heap, worklist);
713                 return false;
714               }
715           }
716
717       if (STMT_VINFO_GATHER_P (stmt_vinfo))
718         {
719           tree off;
720           tree decl = vect_check_gather (stmt, loop_vinfo, NULL, &off, NULL);
721           gcc_assert (decl);
722           if (!process_use (stmt, off, loop_vinfo, live_p, relevant,
723                             &worklist, true))
724             {
725               VEC_free (gimple, heap, worklist);
726               return false;
727             }
728         }
729     } /* while worklist */
730
731   VEC_free (gimple, heap, worklist);
732   return true;
733 }
734
735
736 /* Get cost by calling cost target builtin.  */
737
738 static inline
739 int vect_get_stmt_cost (enum vect_cost_for_stmt type_of_cost)
740 {
741   tree dummy_type = NULL;
742   int dummy = 0;
743
744   return targetm.vectorize.builtin_vectorization_cost (type_of_cost,
745                                                        dummy_type, dummy);
746 }
747
748
749 /* Get cost for STMT.  */
750
751 int
752 cost_for_stmt (gimple stmt)
753 {
754   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
755
756   switch (STMT_VINFO_TYPE (stmt_info))
757   {
758   case load_vec_info_type:
759     return vect_get_stmt_cost (scalar_load);
760   case store_vec_info_type:
761     return vect_get_stmt_cost (scalar_store);
762   case op_vec_info_type:
763   case condition_vec_info_type:
764   case assignment_vec_info_type:
765   case reduc_vec_info_type:
766   case induc_vec_info_type:
767   case type_promotion_vec_info_type:
768   case type_demotion_vec_info_type:
769   case type_conversion_vec_info_type:
770   case call_vec_info_type:
771     return vect_get_stmt_cost (scalar_stmt);
772   case undef_vec_info_type:
773   default:
774     gcc_unreachable ();
775   }
776 }
777
778 /* Function vect_model_simple_cost.
779
780    Models cost for simple operations, i.e. those that only emit ncopies of a
781    single op.  Right now, this does not account for multiple insns that could
782    be generated for the single vector op.  We will handle that shortly.  */
783
784 void
785 vect_model_simple_cost (stmt_vec_info stmt_info, int ncopies,
786                         enum vect_def_type *dt, slp_tree slp_node)
787 {
788   int i;
789   int inside_cost = 0, outside_cost = 0;
790
791   /* The SLP costs were already calculated during SLP tree build.  */
792   if (PURE_SLP_STMT (stmt_info))
793     return;
794
795   inside_cost = ncopies * vect_get_stmt_cost (vector_stmt); 
796
797   /* FORNOW: Assuming maximum 2 args per stmts.  */
798   for (i = 0; i < 2; i++)
799     {
800       if (dt[i] == vect_constant_def || dt[i] == vect_external_def)
801         outside_cost += vect_get_stmt_cost (vector_stmt); 
802     }
803
804   if (vect_print_dump_info (REPORT_COST))
805     fprintf (vect_dump, "vect_model_simple_cost: inside_cost = %d, "
806              "outside_cost = %d .", inside_cost, outside_cost);
807
808   /* Set the costs either in STMT_INFO or SLP_NODE (if exists).  */
809   stmt_vinfo_set_inside_of_loop_cost (stmt_info, slp_node, inside_cost);
810   stmt_vinfo_set_outside_of_loop_cost (stmt_info, slp_node, outside_cost);
811 }
812
813
814 /* Model cost for type demotion and promotion operations.  PWR is normally
815    zero for single-step promotions and demotions.  It will be one if 
816    two-step promotion/demotion is required, and so on.  Each additional
817    step doubles the number of instructions required.  */
818
819 static void
820 vect_model_promotion_demotion_cost (stmt_vec_info stmt_info,
821                                     enum vect_def_type *dt, int pwr)
822 {
823   int i, tmp;
824   int inside_cost = 0, outside_cost = 0, single_stmt_cost;
825
826   /* The SLP costs were already calculated during SLP tree build.  */
827   if (PURE_SLP_STMT (stmt_info))
828     return;
829
830   single_stmt_cost = vect_get_stmt_cost (vec_promote_demote);
831   for (i = 0; i < pwr + 1; i++)
832     {
833       tmp = (STMT_VINFO_TYPE (stmt_info) == type_promotion_vec_info_type) ?
834         (i + 1) : i;
835       inside_cost += vect_pow2 (tmp) * single_stmt_cost;
836     }
837
838   /* FORNOW: Assuming maximum 2 args per stmts.  */
839   for (i = 0; i < 2; i++)
840     {
841       if (dt[i] == vect_constant_def || dt[i] == vect_external_def)
842         outside_cost += vect_get_stmt_cost (vector_stmt);
843     }
844
845   if (vect_print_dump_info (REPORT_COST))
846     fprintf (vect_dump, "vect_model_promotion_demotion_cost: inside_cost = %d, "
847              "outside_cost = %d .", inside_cost, outside_cost);
848
849   /* Set the costs in STMT_INFO.  */
850   stmt_vinfo_set_inside_of_loop_cost (stmt_info, NULL, inside_cost);
851   stmt_vinfo_set_outside_of_loop_cost (stmt_info, NULL, outside_cost);
852 }
853
854 /* Function vect_cost_strided_group_size
855
856    For strided load or store, return the group_size only if it is the first
857    load or store of a group, else return 1.  This ensures that group size is
858    only returned once per group.  */
859
860 static int
861 vect_cost_strided_group_size (stmt_vec_info stmt_info)
862 {
863   gimple first_stmt = GROUP_FIRST_ELEMENT (stmt_info);
864
865   if (first_stmt == STMT_VINFO_STMT (stmt_info))
866     return GROUP_SIZE (stmt_info);
867
868   return 1;
869 }
870
871
872 /* Function vect_model_store_cost
873
874    Models cost for stores.  In the case of strided accesses, one access
875    has the overhead of the strided access attributed to it.  */
876
877 void
878 vect_model_store_cost (stmt_vec_info stmt_info, int ncopies,
879                        bool store_lanes_p, enum vect_def_type dt,
880                        slp_tree slp_node)
881 {
882   int group_size;
883   unsigned int inside_cost = 0, outside_cost = 0;
884   struct data_reference *first_dr;
885   gimple first_stmt;
886
887   /* The SLP costs were already calculated during SLP tree build.  */
888   if (PURE_SLP_STMT (stmt_info))
889     return;
890
891   if (dt == vect_constant_def || dt == vect_external_def)
892     outside_cost = vect_get_stmt_cost (scalar_to_vec); 
893
894   /* Strided access?  */
895   if (STMT_VINFO_STRIDED_ACCESS (stmt_info))
896     {
897       if (slp_node)
898         {
899           first_stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (slp_node), 0);
900           group_size = 1;
901         }
902       else
903         {
904           first_stmt = GROUP_FIRST_ELEMENT (stmt_info);
905           group_size = vect_cost_strided_group_size (stmt_info);
906         }
907
908       first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt));
909     }
910   /* Not a strided access.  */
911   else
912     {
913       group_size = 1;
914       first_dr = STMT_VINFO_DATA_REF (stmt_info);
915     }
916
917   /* We assume that the cost of a single store-lanes instruction is
918      equivalent to the cost of GROUP_SIZE separate stores.  If a strided
919      access is instead being provided by a permute-and-store operation,
920      include the cost of the permutes.  */
921   if (!store_lanes_p && group_size > 1)
922     {
923       /* Uses a high and low interleave operation for each needed permute.  */
924       inside_cost = ncopies * exact_log2(group_size) * group_size
925         * vect_get_stmt_cost (vec_perm);
926
927       if (vect_print_dump_info (REPORT_COST))
928         fprintf (vect_dump, "vect_model_store_cost: strided group_size = %d .",
929                  group_size);
930     }
931
932   /* Costs of the stores.  */
933   vect_get_store_cost (first_dr, ncopies, &inside_cost);
934
935   if (vect_print_dump_info (REPORT_COST))
936     fprintf (vect_dump, "vect_model_store_cost: inside_cost = %d, "
937              "outside_cost = %d .", inside_cost, outside_cost);
938
939   /* Set the costs either in STMT_INFO or SLP_NODE (if exists).  */
940   stmt_vinfo_set_inside_of_loop_cost (stmt_info, slp_node, inside_cost);
941   stmt_vinfo_set_outside_of_loop_cost (stmt_info, slp_node, outside_cost);
942 }
943
944
945 /* Calculate cost of DR's memory access.  */
946 void
947 vect_get_store_cost (struct data_reference *dr, int ncopies,
948                      unsigned int *inside_cost)
949 {
950   int alignment_support_scheme = vect_supportable_dr_alignment (dr, false);
951
952   switch (alignment_support_scheme)
953     {
954     case dr_aligned:
955       {
956         *inside_cost += ncopies * vect_get_stmt_cost (vector_store);
957
958         if (vect_print_dump_info (REPORT_COST))
959           fprintf (vect_dump, "vect_model_store_cost: aligned.");
960
961         break;
962       }
963
964     case dr_unaligned_supported:
965       {
966         gimple stmt = DR_STMT (dr);
967         stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
968         tree vectype = STMT_VINFO_VECTYPE (stmt_info);
969
970         /* Here, we assign an additional cost for the unaligned store.  */
971         *inside_cost += ncopies
972           * targetm.vectorize.builtin_vectorization_cost (unaligned_store,
973                                  vectype, DR_MISALIGNMENT (dr));
974
975         if (vect_print_dump_info (REPORT_COST))
976           fprintf (vect_dump, "vect_model_store_cost: unaligned supported by "
977                    "hardware.");
978
979         break;
980       }
981
982     default:
983       gcc_unreachable ();
984     }
985 }
986
987
988 /* Function vect_model_load_cost
989
990    Models cost for loads.  In the case of strided accesses, the last access
991    has the overhead of the strided access attributed to it.  Since unaligned
992    accesses are supported for loads, we also account for the costs of the
993    access scheme chosen.  */
994
995 void
996 vect_model_load_cost (stmt_vec_info stmt_info, int ncopies, bool load_lanes_p,
997                       slp_tree slp_node)
998 {
999   int group_size;
1000   gimple first_stmt;
1001   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info), *first_dr;
1002   unsigned int inside_cost = 0, outside_cost = 0;
1003
1004   /* The SLP costs were already calculated during SLP tree build.  */
1005   if (PURE_SLP_STMT (stmt_info))
1006     return;
1007
1008   /* Strided accesses?  */
1009   first_stmt = GROUP_FIRST_ELEMENT (stmt_info);
1010   if (STMT_VINFO_STRIDED_ACCESS (stmt_info) && first_stmt && !slp_node)
1011     {
1012       group_size = vect_cost_strided_group_size (stmt_info);
1013       first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt));
1014     }
1015   /* Not a strided access.  */
1016   else
1017     {
1018       group_size = 1;
1019       first_dr = dr;
1020     }
1021
1022   /* We assume that the cost of a single load-lanes instruction is
1023      equivalent to the cost of GROUP_SIZE separate loads.  If a strided
1024      access is instead being provided by a load-and-permute operation,
1025      include the cost of the permutes.  */
1026   if (!load_lanes_p && group_size > 1)
1027     {
1028       /* Uses an even and odd extract operations for each needed permute.  */
1029       inside_cost = ncopies * exact_log2(group_size) * group_size
1030         * vect_get_stmt_cost (vec_perm);
1031
1032       if (vect_print_dump_info (REPORT_COST))
1033         fprintf (vect_dump, "vect_model_load_cost: strided group_size = %d .",
1034                  group_size);
1035     }
1036
1037   /* The loads themselves.  */
1038   vect_get_load_cost (first_dr, ncopies,
1039          ((!STMT_VINFO_STRIDED_ACCESS (stmt_info)) || group_size > 1
1040           || slp_node),
1041          &inside_cost, &outside_cost);
1042
1043   if (vect_print_dump_info (REPORT_COST))
1044     fprintf (vect_dump, "vect_model_load_cost: inside_cost = %d, "
1045              "outside_cost = %d .", inside_cost, outside_cost);
1046
1047   /* Set the costs either in STMT_INFO or SLP_NODE (if exists).  */
1048   stmt_vinfo_set_inside_of_loop_cost (stmt_info, slp_node, inside_cost);
1049   stmt_vinfo_set_outside_of_loop_cost (stmt_info, slp_node, outside_cost);
1050 }
1051
1052
1053 /* Calculate cost of DR's memory access.  */
1054 void
1055 vect_get_load_cost (struct data_reference *dr, int ncopies,
1056                     bool add_realign_cost, unsigned int *inside_cost,
1057                     unsigned int *outside_cost)
1058 {
1059   int alignment_support_scheme = vect_supportable_dr_alignment (dr, false);
1060
1061   switch (alignment_support_scheme)
1062     {
1063     case dr_aligned:
1064       {
1065         *inside_cost += ncopies * vect_get_stmt_cost (vector_load); 
1066
1067         if (vect_print_dump_info (REPORT_COST))
1068           fprintf (vect_dump, "vect_model_load_cost: aligned.");
1069
1070         break;
1071       }
1072     case dr_unaligned_supported:
1073       {
1074         gimple stmt = DR_STMT (dr);
1075         stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1076         tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1077
1078         /* Here, we assign an additional cost for the unaligned load.  */
1079         *inside_cost += ncopies
1080           * targetm.vectorize.builtin_vectorization_cost (unaligned_load,
1081                                            vectype, DR_MISALIGNMENT (dr));
1082         if (vect_print_dump_info (REPORT_COST))
1083           fprintf (vect_dump, "vect_model_load_cost: unaligned supported by "
1084                    "hardware.");
1085
1086         break;
1087       }
1088     case dr_explicit_realign:
1089       {
1090         *inside_cost += ncopies * (2 * vect_get_stmt_cost (vector_load)
1091                                    + vect_get_stmt_cost (vec_perm));
1092
1093         /* FIXME: If the misalignment remains fixed across the iterations of
1094            the containing loop, the following cost should be added to the
1095            outside costs.  */
1096         if (targetm.vectorize.builtin_mask_for_load)
1097           *inside_cost += vect_get_stmt_cost (vector_stmt);
1098
1099         if (vect_print_dump_info (REPORT_COST))
1100           fprintf (vect_dump, "vect_model_load_cost: explicit realign");
1101
1102         break;
1103       }
1104     case dr_explicit_realign_optimized:
1105       {
1106         if (vect_print_dump_info (REPORT_COST))
1107           fprintf (vect_dump, "vect_model_load_cost: unaligned software "
1108                    "pipelined.");
1109
1110         /* Unaligned software pipeline has a load of an address, an initial
1111            load, and possibly a mask operation to "prime" the loop.  However,
1112            if this is an access in a group of loads, which provide strided
1113            access, then the above cost should only be considered for one
1114            access in the group.  Inside the loop, there is a load op
1115            and a realignment op.  */
1116
1117         if (add_realign_cost)
1118           {
1119             *outside_cost = 2 * vect_get_stmt_cost (vector_stmt);
1120             if (targetm.vectorize.builtin_mask_for_load)
1121               *outside_cost += vect_get_stmt_cost (vector_stmt);
1122           }
1123
1124         *inside_cost += ncopies * (vect_get_stmt_cost (vector_load)
1125                                    + vect_get_stmt_cost (vec_perm));
1126
1127         if (vect_print_dump_info (REPORT_COST))
1128           fprintf (vect_dump,
1129                    "vect_model_load_cost: explicit realign optimized");
1130
1131         break;
1132       }
1133
1134     default:
1135       gcc_unreachable ();
1136     }
1137 }
1138
1139
1140 /* Function vect_init_vector.
1141
1142    Insert a new stmt (INIT_STMT) that initializes a new vector variable with
1143    the vector elements of VECTOR_VAR.  Place the initialization at BSI if it
1144    is not NULL.  Otherwise, place the initialization at the loop preheader.
1145    Return the DEF of INIT_STMT.
1146    It will be used in the vectorization of STMT.  */
1147
1148 tree
1149 vect_init_vector (gimple stmt, tree vector_var, tree vector_type,
1150                   gimple_stmt_iterator *gsi)
1151 {
1152   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
1153   tree new_var;
1154   gimple init_stmt;
1155   tree vec_oprnd;
1156   edge pe;
1157   tree new_temp;
1158   basic_block new_bb;
1159
1160   new_var = vect_get_new_vect_var (vector_type, vect_simple_var, "cst_");
1161   add_referenced_var (new_var);
1162   init_stmt = gimple_build_assign  (new_var, vector_var);
1163   new_temp = make_ssa_name (new_var, init_stmt);
1164   gimple_assign_set_lhs (init_stmt, new_temp);
1165
1166   if (gsi)
1167     vect_finish_stmt_generation (stmt, init_stmt, gsi);
1168   else
1169     {
1170       loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
1171
1172       if (loop_vinfo)
1173         {
1174           struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1175
1176           if (nested_in_vect_loop_p (loop, stmt))
1177             loop = loop->inner;
1178
1179           pe = loop_preheader_edge (loop);
1180           new_bb = gsi_insert_on_edge_immediate (pe, init_stmt);
1181           gcc_assert (!new_bb);
1182         }
1183       else
1184        {
1185           bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_vinfo);
1186           basic_block bb;
1187           gimple_stmt_iterator gsi_bb_start;
1188
1189           gcc_assert (bb_vinfo);
1190           bb = BB_VINFO_BB (bb_vinfo);
1191           gsi_bb_start = gsi_after_labels (bb);
1192           gsi_insert_before (&gsi_bb_start, init_stmt, GSI_SAME_STMT);
1193        }
1194     }
1195
1196   if (vect_print_dump_info (REPORT_DETAILS))
1197     {
1198       fprintf (vect_dump, "created new init_stmt: ");
1199       print_gimple_stmt (vect_dump, init_stmt, 0, TDF_SLIM);
1200     }
1201
1202   vec_oprnd = gimple_assign_lhs (init_stmt);
1203   return vec_oprnd;
1204 }
1205
1206
1207 /* Function vect_get_vec_def_for_operand.
1208
1209    OP is an operand in STMT.  This function returns a (vector) def that will be
1210    used in the vectorized stmt for STMT.
1211
1212    In the case that OP is an SSA_NAME which is defined in the loop, then
1213    STMT_VINFO_VEC_STMT of the defining stmt holds the relevant def.
1214
1215    In case OP is an invariant or constant, a new stmt that creates a vector def
1216    needs to be introduced.  */
1217
1218 tree
1219 vect_get_vec_def_for_operand (tree op, gimple stmt, tree *scalar_def)
1220 {
1221   tree vec_oprnd;
1222   gimple vec_stmt;
1223   gimple def_stmt;
1224   stmt_vec_info def_stmt_info = NULL;
1225   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
1226   unsigned int nunits;
1227   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
1228   tree vec_inv;
1229   tree vec_cst;
1230   tree t = NULL_TREE;
1231   tree def;
1232   int i;
1233   enum vect_def_type dt;
1234   bool is_simple_use;
1235   tree vector_type;
1236
1237   if (vect_print_dump_info (REPORT_DETAILS))
1238     {
1239       fprintf (vect_dump, "vect_get_vec_def_for_operand: ");
1240       print_generic_expr (vect_dump, op, TDF_SLIM);
1241     }
1242
1243   is_simple_use = vect_is_simple_use (op, stmt, loop_vinfo, NULL,
1244                                       &def_stmt, &def, &dt);
1245   gcc_assert (is_simple_use);
1246   if (vect_print_dump_info (REPORT_DETAILS))
1247     {
1248       if (def)
1249         {
1250           fprintf (vect_dump, "def =  ");
1251           print_generic_expr (vect_dump, def, TDF_SLIM);
1252         }
1253       if (def_stmt)
1254         {
1255           fprintf (vect_dump, "  def_stmt =  ");
1256           print_gimple_stmt (vect_dump, def_stmt, 0, TDF_SLIM);
1257         }
1258     }
1259
1260   switch (dt)
1261     {
1262     /* Case 1: operand is a constant.  */
1263     case vect_constant_def:
1264       {
1265         vector_type = get_vectype_for_scalar_type (TREE_TYPE (op));
1266         gcc_assert (vector_type);
1267         nunits = TYPE_VECTOR_SUBPARTS (vector_type);
1268
1269         if (scalar_def)
1270           *scalar_def = op;
1271
1272         /* Create 'vect_cst_ = {cst,cst,...,cst}'  */
1273         if (vect_print_dump_info (REPORT_DETAILS))
1274           fprintf (vect_dump, "Create vector_cst. nunits = %d", nunits);
1275
1276         vec_cst = build_vector_from_val (vector_type,
1277                                          fold_convert (TREE_TYPE (vector_type),
1278                                                        op));
1279         return vect_init_vector (stmt, vec_cst, vector_type, NULL);
1280       }
1281
1282     /* Case 2: operand is defined outside the loop - loop invariant.  */
1283     case vect_external_def:
1284       {
1285         vector_type = get_vectype_for_scalar_type (TREE_TYPE (def));
1286         gcc_assert (vector_type);
1287         nunits = TYPE_VECTOR_SUBPARTS (vector_type);
1288
1289         if (scalar_def)
1290           *scalar_def = def;
1291
1292         /* Create 'vec_inv = {inv,inv,..,inv}'  */
1293         if (vect_print_dump_info (REPORT_DETAILS))
1294           fprintf (vect_dump, "Create vector_inv.");
1295
1296         for (i = nunits - 1; i >= 0; --i)
1297           {
1298             t = tree_cons (NULL_TREE, def, t);
1299           }
1300
1301         /* FIXME: use build_constructor directly.  */
1302         vec_inv = build_constructor_from_list (vector_type, t);
1303         return vect_init_vector (stmt, vec_inv, vector_type, NULL);
1304       }
1305
1306     /* Case 3: operand is defined inside the loop.  */
1307     case vect_internal_def:
1308       {
1309         if (scalar_def)
1310           *scalar_def = NULL/* FIXME tuples: def_stmt*/;
1311
1312         /* Get the def from the vectorized stmt.  */
1313         def_stmt_info = vinfo_for_stmt (def_stmt);
1314
1315         vec_stmt = STMT_VINFO_VEC_STMT (def_stmt_info);
1316         /* Get vectorized pattern statement.  */
1317         if (!vec_stmt
1318             && STMT_VINFO_IN_PATTERN_P (def_stmt_info)
1319             && !STMT_VINFO_RELEVANT (def_stmt_info))
1320           vec_stmt = STMT_VINFO_VEC_STMT (vinfo_for_stmt (
1321                        STMT_VINFO_RELATED_STMT (def_stmt_info)));
1322         gcc_assert (vec_stmt);
1323         if (gimple_code (vec_stmt) == GIMPLE_PHI)
1324           vec_oprnd = PHI_RESULT (vec_stmt);
1325         else if (is_gimple_call (vec_stmt))
1326           vec_oprnd = gimple_call_lhs (vec_stmt);
1327         else
1328           vec_oprnd = gimple_assign_lhs (vec_stmt);
1329         return vec_oprnd;
1330       }
1331
1332     /* Case 4: operand is defined by a loop header phi - reduction  */
1333     case vect_reduction_def:
1334     case vect_double_reduction_def:
1335     case vect_nested_cycle:
1336       {
1337         struct loop *loop;
1338
1339         gcc_assert (gimple_code (def_stmt) == GIMPLE_PHI);
1340         loop = (gimple_bb (def_stmt))->loop_father;
1341
1342         /* Get the def before the loop  */
1343         op = PHI_ARG_DEF_FROM_EDGE (def_stmt, loop_preheader_edge (loop));
1344         return get_initial_def_for_reduction (stmt, op, scalar_def);
1345      }
1346
1347     /* Case 5: operand is defined by loop-header phi - induction.  */
1348     case vect_induction_def:
1349       {
1350         gcc_assert (gimple_code (def_stmt) == GIMPLE_PHI);
1351
1352         /* Get the def from the vectorized stmt.  */
1353         def_stmt_info = vinfo_for_stmt (def_stmt);
1354         vec_stmt = STMT_VINFO_VEC_STMT (def_stmt_info);
1355         if (gimple_code (vec_stmt) == GIMPLE_PHI)
1356           vec_oprnd = PHI_RESULT (vec_stmt);
1357         else
1358           vec_oprnd = gimple_get_lhs (vec_stmt);
1359         return vec_oprnd;
1360       }
1361
1362     default:
1363       gcc_unreachable ();
1364     }
1365 }
1366
1367
1368 /* Function vect_get_vec_def_for_stmt_copy
1369
1370    Return a vector-def for an operand.  This function is used when the
1371    vectorized stmt to be created (by the caller to this function) is a "copy"
1372    created in case the vectorized result cannot fit in one vector, and several
1373    copies of the vector-stmt are required.  In this case the vector-def is
1374    retrieved from the vector stmt recorded in the STMT_VINFO_RELATED_STMT field
1375    of the stmt that defines VEC_OPRND.
1376    DT is the type of the vector def VEC_OPRND.
1377
1378    Context:
1379         In case the vectorization factor (VF) is bigger than the number
1380    of elements that can fit in a vectype (nunits), we have to generate
1381    more than one vector stmt to vectorize the scalar stmt.  This situation
1382    arises when there are multiple data-types operated upon in the loop; the
1383    smallest data-type determines the VF, and as a result, when vectorizing
1384    stmts operating on wider types we need to create 'VF/nunits' "copies" of the
1385    vector stmt (each computing a vector of 'nunits' results, and together
1386    computing 'VF' results in each iteration).  This function is called when
1387    vectorizing such a stmt (e.g. vectorizing S2 in the illustration below, in
1388    which VF=16 and nunits=4, so the number of copies required is 4):
1389
1390    scalar stmt:         vectorized into:        STMT_VINFO_RELATED_STMT
1391
1392    S1: x = load         VS1.0:  vx.0 = memref0      VS1.1
1393                         VS1.1:  vx.1 = memref1      VS1.2
1394                         VS1.2:  vx.2 = memref2      VS1.3
1395                         VS1.3:  vx.3 = memref3
1396
1397    S2: z = x + ...      VSnew.0:  vz0 = vx.0 + ...  VSnew.1
1398                         VSnew.1:  vz1 = vx.1 + ...  VSnew.2
1399                         VSnew.2:  vz2 = vx.2 + ...  VSnew.3
1400                         VSnew.3:  vz3 = vx.3 + ...
1401
1402    The vectorization of S1 is explained in vectorizable_load.
1403    The vectorization of S2:
1404         To create the first vector-stmt out of the 4 copies - VSnew.0 -
1405    the function 'vect_get_vec_def_for_operand' is called to
1406    get the relevant vector-def for each operand of S2.  For operand x it
1407    returns  the vector-def 'vx.0'.
1408
1409         To create the remaining copies of the vector-stmt (VSnew.j), this
1410    function is called to get the relevant vector-def for each operand.  It is
1411    obtained from the respective VS1.j stmt, which is recorded in the
1412    STMT_VINFO_RELATED_STMT field of the stmt that defines VEC_OPRND.
1413
1414         For example, to obtain the vector-def 'vx.1' in order to create the
1415    vector stmt 'VSnew.1', this function is called with VEC_OPRND='vx.0'.
1416    Given 'vx0' we obtain the stmt that defines it ('VS1.0'); from the
1417    STMT_VINFO_RELATED_STMT field of 'VS1.0' we obtain the next copy - 'VS1.1',
1418    and return its def ('vx.1').
1419    Overall, to create the above sequence this function will be called 3 times:
1420         vx.1 = vect_get_vec_def_for_stmt_copy (dt, vx.0);
1421         vx.2 = vect_get_vec_def_for_stmt_copy (dt, vx.1);
1422         vx.3 = vect_get_vec_def_for_stmt_copy (dt, vx.2);  */
1423
1424 tree
1425 vect_get_vec_def_for_stmt_copy (enum vect_def_type dt, tree vec_oprnd)
1426 {
1427   gimple vec_stmt_for_operand;
1428   stmt_vec_info def_stmt_info;
1429
1430   /* Do nothing; can reuse same def.  */
1431   if (dt == vect_external_def || dt == vect_constant_def )
1432     return vec_oprnd;
1433
1434   vec_stmt_for_operand = SSA_NAME_DEF_STMT (vec_oprnd);
1435   def_stmt_info = vinfo_for_stmt (vec_stmt_for_operand);
1436   gcc_assert (def_stmt_info);
1437   vec_stmt_for_operand = STMT_VINFO_RELATED_STMT (def_stmt_info);
1438   gcc_assert (vec_stmt_for_operand);
1439   vec_oprnd = gimple_get_lhs (vec_stmt_for_operand);
1440   if (gimple_code (vec_stmt_for_operand) == GIMPLE_PHI)
1441     vec_oprnd = PHI_RESULT (vec_stmt_for_operand);
1442   else
1443     vec_oprnd = gimple_get_lhs (vec_stmt_for_operand);
1444   return vec_oprnd;
1445 }
1446
1447
1448 /* Get vectorized definitions for the operands to create a copy of an original
1449    stmt.  See vect_get_vec_def_for_stmt_copy () for details.  */
1450
1451 static void
1452 vect_get_vec_defs_for_stmt_copy (enum vect_def_type *dt,
1453                                  VEC(tree,heap) **vec_oprnds0,
1454                                  VEC(tree,heap) **vec_oprnds1)
1455 {
1456   tree vec_oprnd = VEC_pop (tree, *vec_oprnds0);
1457
1458   vec_oprnd = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd);
1459   VEC_quick_push (tree, *vec_oprnds0, vec_oprnd);
1460
1461   if (vec_oprnds1 && *vec_oprnds1)
1462     {
1463       vec_oprnd = VEC_pop (tree, *vec_oprnds1);
1464       vec_oprnd = vect_get_vec_def_for_stmt_copy (dt[1], vec_oprnd);
1465       VEC_quick_push (tree, *vec_oprnds1, vec_oprnd);
1466     }
1467 }
1468
1469
1470 /* Get vectorized definitions for OP0 and OP1.
1471    REDUC_INDEX is the index of reduction operand in case of reduction,
1472    and -1 otherwise.  */
1473
1474 void
1475 vect_get_vec_defs (tree op0, tree op1, gimple stmt,
1476                    VEC (tree, heap) **vec_oprnds0,
1477                    VEC (tree, heap) **vec_oprnds1,
1478                    slp_tree slp_node, int reduc_index)
1479 {
1480   if (slp_node)
1481     {
1482       int nops = (op1 == NULL_TREE) ? 1 : 2;
1483       VEC (tree, heap) *ops = VEC_alloc (tree, heap, nops);
1484       VEC (slp_void_p, heap) *vec_defs = VEC_alloc (slp_void_p, heap, nops);
1485
1486       VEC_quick_push (tree, ops, op0);
1487       if (op1)
1488         VEC_quick_push (tree, ops, op1);
1489
1490       vect_get_slp_defs (ops, slp_node, &vec_defs, reduc_index);
1491
1492       *vec_oprnds0 = (VEC (tree, heap) *) VEC_index (slp_void_p, vec_defs, 0);
1493       if (op1)
1494         *vec_oprnds1 = (VEC (tree, heap) *) VEC_index (slp_void_p, vec_defs, 1);
1495
1496       VEC_free (tree, heap, ops);
1497       VEC_free (slp_void_p, heap, vec_defs);
1498     }
1499   else
1500     {
1501       tree vec_oprnd;
1502
1503       *vec_oprnds0 = VEC_alloc (tree, heap, 1);
1504       vec_oprnd = vect_get_vec_def_for_operand (op0, stmt, NULL);
1505       VEC_quick_push (tree, *vec_oprnds0, vec_oprnd);
1506
1507       if (op1)
1508         {
1509           *vec_oprnds1 = VEC_alloc (tree, heap, 1);
1510           vec_oprnd = vect_get_vec_def_for_operand (op1, stmt, NULL);
1511           VEC_quick_push (tree, *vec_oprnds1, vec_oprnd);
1512         }
1513     }
1514 }
1515
1516
1517 /* Function vect_finish_stmt_generation.
1518
1519    Insert a new stmt.  */
1520
1521 void
1522 vect_finish_stmt_generation (gimple stmt, gimple vec_stmt,
1523                              gimple_stmt_iterator *gsi)
1524 {
1525   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1526   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1527   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
1528
1529   gcc_assert (gimple_code (stmt) != GIMPLE_LABEL);
1530
1531   gsi_insert_before (gsi, vec_stmt, GSI_SAME_STMT);
1532
1533   set_vinfo_for_stmt (vec_stmt, new_stmt_vec_info (vec_stmt, loop_vinfo,
1534                                                    bb_vinfo));
1535
1536   if (vect_print_dump_info (REPORT_DETAILS))
1537     {
1538       fprintf (vect_dump, "add new stmt: ");
1539       print_gimple_stmt (vect_dump, vec_stmt, 0, TDF_SLIM);
1540     }
1541
1542   gimple_set_location (vec_stmt, gimple_location (stmt));
1543 }
1544
1545 /* Checks if CALL can be vectorized in type VECTYPE.  Returns
1546    a function declaration if the target has a vectorized version
1547    of the function, or NULL_TREE if the function cannot be vectorized.  */
1548
1549 tree
1550 vectorizable_function (gimple call, tree vectype_out, tree vectype_in)
1551 {
1552   tree fndecl = gimple_call_fndecl (call);
1553
1554   /* We only handle functions that do not read or clobber memory -- i.e.
1555      const or novops ones.  */
1556   if (!(gimple_call_flags (call) & (ECF_CONST | ECF_NOVOPS)))
1557     return NULL_TREE;
1558
1559   if (!fndecl
1560       || TREE_CODE (fndecl) != FUNCTION_DECL
1561       || !DECL_BUILT_IN (fndecl))
1562     return NULL_TREE;
1563
1564   return targetm.vectorize.builtin_vectorized_function (fndecl, vectype_out,
1565                                                         vectype_in);
1566 }
1567
1568 /* Function vectorizable_call.
1569
1570    Check if STMT performs a function call that can be vectorized.
1571    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1572    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1573    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
1574
1575 static bool
1576 vectorizable_call (gimple stmt, gimple_stmt_iterator *gsi, gimple *vec_stmt,
1577                    slp_tree slp_node)
1578 {
1579   tree vec_dest;
1580   tree scalar_dest;
1581   tree op, type;
1582   tree vec_oprnd0 = NULL_TREE, vec_oprnd1 = NULL_TREE;
1583   stmt_vec_info stmt_info = vinfo_for_stmt (stmt), prev_stmt_info;
1584   tree vectype_out, vectype_in;
1585   int nunits_in;
1586   int nunits_out;
1587   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1588   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
1589   tree fndecl, new_temp, def, rhs_type;
1590   gimple def_stmt;
1591   enum vect_def_type dt[3]
1592     = {vect_unknown_def_type, vect_unknown_def_type, vect_unknown_def_type};
1593   gimple new_stmt = NULL;
1594   int ncopies, j;
1595   VEC(tree, heap) *vargs = NULL;
1596   enum { NARROW, NONE, WIDEN } modifier;
1597   size_t i, nargs;
1598   tree lhs;
1599
1600   if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
1601     return false;
1602
1603   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
1604     return false;
1605
1606   /* Is STMT a vectorizable call?   */
1607   if (!is_gimple_call (stmt))
1608     return false;
1609
1610   if (TREE_CODE (gimple_call_lhs (stmt)) != SSA_NAME)
1611     return false;
1612
1613   if (stmt_can_throw_internal (stmt))
1614     return false;
1615
1616   vectype_out = STMT_VINFO_VECTYPE (stmt_info);
1617
1618   /* Process function arguments.  */
1619   rhs_type = NULL_TREE;
1620   vectype_in = NULL_TREE;
1621   nargs = gimple_call_num_args (stmt);
1622
1623   /* Bail out if the function has more than three arguments, we do not have
1624      interesting builtin functions to vectorize with more than two arguments
1625      except for fma.  No arguments is also not good.  */
1626   if (nargs == 0 || nargs > 3)
1627     return false;
1628
1629   for (i = 0; i < nargs; i++)
1630     {
1631       tree opvectype;
1632
1633       op = gimple_call_arg (stmt, i);
1634
1635       /* We can only handle calls with arguments of the same type.  */
1636       if (rhs_type
1637           && !types_compatible_p (rhs_type, TREE_TYPE (op)))
1638         {
1639           if (vect_print_dump_info (REPORT_DETAILS))
1640             fprintf (vect_dump, "argument types differ.");
1641           return false;
1642         }
1643       if (!rhs_type)
1644         rhs_type = TREE_TYPE (op);
1645
1646       if (!vect_is_simple_use_1 (op, stmt, loop_vinfo, bb_vinfo,
1647                                  &def_stmt, &def, &dt[i], &opvectype))
1648         {
1649           if (vect_print_dump_info (REPORT_DETAILS))
1650             fprintf (vect_dump, "use not simple.");
1651           return false;
1652         }
1653
1654       if (!vectype_in)
1655         vectype_in = opvectype;
1656       else if (opvectype
1657                && opvectype != vectype_in)
1658         {
1659           if (vect_print_dump_info (REPORT_DETAILS))
1660             fprintf (vect_dump, "argument vector types differ.");
1661           return false;
1662         }
1663     }
1664   /* If all arguments are external or constant defs use a vector type with
1665      the same size as the output vector type.  */
1666   if (!vectype_in)
1667     vectype_in = get_same_sized_vectype (rhs_type, vectype_out);
1668   if (vec_stmt)
1669     gcc_assert (vectype_in);
1670   if (!vectype_in)
1671     {
1672       if (vect_print_dump_info (REPORT_DETAILS))
1673         {
1674           fprintf (vect_dump, "no vectype for scalar type ");
1675           print_generic_expr (vect_dump, rhs_type, TDF_SLIM);
1676         }
1677
1678       return false;
1679     }
1680
1681   /* FORNOW */
1682   nunits_in = TYPE_VECTOR_SUBPARTS (vectype_in);
1683   nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
1684   if (nunits_in == nunits_out / 2)
1685     modifier = NARROW;
1686   else if (nunits_out == nunits_in)
1687     modifier = NONE;
1688   else if (nunits_out == nunits_in / 2)
1689     modifier = WIDEN;
1690   else
1691     return false;
1692
1693   /* For now, we only vectorize functions if a target specific builtin
1694      is available.  TODO -- in some cases, it might be profitable to
1695      insert the calls for pieces of the vector, in order to be able
1696      to vectorize other operations in the loop.  */
1697   fndecl = vectorizable_function (stmt, vectype_out, vectype_in);
1698   if (fndecl == NULL_TREE)
1699     {
1700       if (vect_print_dump_info (REPORT_DETAILS))
1701         fprintf (vect_dump, "function is not vectorizable.");
1702
1703       return false;
1704     }
1705
1706   gcc_assert (!gimple_vuse (stmt));
1707
1708   if (slp_node || PURE_SLP_STMT (stmt_info))
1709     ncopies = 1;
1710   else if (modifier == NARROW)
1711     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_out;
1712   else
1713     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_in;
1714
1715   /* Sanity check: make sure that at least one copy of the vectorized stmt
1716      needs to be generated.  */
1717   gcc_assert (ncopies >= 1);
1718
1719   if (!vec_stmt) /* transformation not required.  */
1720     {
1721       STMT_VINFO_TYPE (stmt_info) = call_vec_info_type;
1722       if (vect_print_dump_info (REPORT_DETAILS))
1723         fprintf (vect_dump, "=== vectorizable_call ===");
1724       vect_model_simple_cost (stmt_info, ncopies, dt, NULL);
1725       return true;
1726     }
1727
1728   /** Transform.  **/
1729
1730   if (vect_print_dump_info (REPORT_DETAILS))
1731     fprintf (vect_dump, "transform call.");
1732
1733   /* Handle def.  */
1734   scalar_dest = gimple_call_lhs (stmt);
1735   vec_dest = vect_create_destination_var (scalar_dest, vectype_out);
1736
1737   prev_stmt_info = NULL;
1738   switch (modifier)
1739     {
1740     case NONE:
1741       for (j = 0; j < ncopies; ++j)
1742         {
1743           /* Build argument list for the vectorized call.  */
1744           if (j == 0)
1745             vargs = VEC_alloc (tree, heap, nargs);
1746           else
1747             VEC_truncate (tree, vargs, 0);
1748
1749           if (slp_node)
1750             {
1751               VEC (slp_void_p, heap) *vec_defs
1752                 = VEC_alloc (slp_void_p, heap, nargs);
1753               VEC (tree, heap) *vec_oprnds0;
1754
1755               for (i = 0; i < nargs; i++)
1756                 VEC_quick_push (tree, vargs, gimple_call_arg (stmt, i));
1757               vect_get_slp_defs (vargs, slp_node, &vec_defs, -1);
1758               vec_oprnds0
1759                 = (VEC (tree, heap) *) VEC_index (slp_void_p, vec_defs, 0);
1760
1761               /* Arguments are ready.  Create the new vector stmt.  */
1762               FOR_EACH_VEC_ELT (tree, vec_oprnds0, i, vec_oprnd0)
1763                 {
1764                   size_t k;
1765                   for (k = 0; k < nargs; k++)
1766                     {
1767                       VEC (tree, heap) *vec_oprndsk
1768                         = (VEC (tree, heap) *)
1769                           VEC_index (slp_void_p, vec_defs, k);
1770                       VEC_replace (tree, vargs, k,
1771                                    VEC_index (tree, vec_oprndsk, i));
1772                     }
1773                   new_stmt = gimple_build_call_vec (fndecl, vargs);
1774                   new_temp = make_ssa_name (vec_dest, new_stmt);
1775                   gimple_call_set_lhs (new_stmt, new_temp);
1776                   vect_finish_stmt_generation (stmt, new_stmt, gsi);
1777                   mark_symbols_for_renaming (new_stmt);
1778                   VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node),
1779                                   new_stmt);
1780                 }
1781
1782               for (i = 0; i < nargs; i++)
1783                 {
1784                   VEC (tree, heap) *vec_oprndsi
1785                     = (VEC (tree, heap) *)
1786                       VEC_index (slp_void_p, vec_defs, i);
1787                   VEC_free (tree, heap, vec_oprndsi);
1788                 }
1789               VEC_free (slp_void_p, heap, vec_defs);
1790               continue;
1791             }
1792
1793           for (i = 0; i < nargs; i++)
1794             {
1795               op = gimple_call_arg (stmt, i);
1796               if (j == 0)
1797                 vec_oprnd0
1798                   = vect_get_vec_def_for_operand (op, stmt, NULL);
1799               else
1800                 {
1801                   vec_oprnd0 = gimple_call_arg (new_stmt, i);
1802                   vec_oprnd0
1803                     = vect_get_vec_def_for_stmt_copy (dt[i], vec_oprnd0);
1804                 }
1805
1806               VEC_quick_push (tree, vargs, vec_oprnd0);
1807             }
1808
1809           new_stmt = gimple_build_call_vec (fndecl, vargs);
1810           new_temp = make_ssa_name (vec_dest, new_stmt);
1811           gimple_call_set_lhs (new_stmt, new_temp);
1812
1813           vect_finish_stmt_generation (stmt, new_stmt, gsi);
1814           mark_symbols_for_renaming (new_stmt);
1815
1816           if (j == 0)
1817             STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
1818           else
1819             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
1820
1821           prev_stmt_info = vinfo_for_stmt (new_stmt);
1822         }
1823
1824       break;
1825
1826     case NARROW:
1827       for (j = 0; j < ncopies; ++j)
1828         {
1829           /* Build argument list for the vectorized call.  */
1830           if (j == 0)
1831             vargs = VEC_alloc (tree, heap, nargs * 2);
1832           else
1833             VEC_truncate (tree, vargs, 0);
1834
1835           if (slp_node)
1836             {
1837               VEC (slp_void_p, heap) *vec_defs
1838                 = VEC_alloc (slp_void_p, heap, nargs);
1839               VEC (tree, heap) *vec_oprnds0;
1840
1841               for (i = 0; i < nargs; i++)
1842                 VEC_quick_push (tree, vargs, gimple_call_arg (stmt, i));
1843               vect_get_slp_defs (vargs, slp_node, &vec_defs, -1);
1844               vec_oprnds0
1845                 = (VEC (tree, heap) *) VEC_index (slp_void_p, vec_defs, 0);
1846
1847               /* Arguments are ready.  Create the new vector stmt.  */
1848               for (i = 0; VEC_iterate (tree, vec_oprnds0, i, vec_oprnd0);
1849                    i += 2)
1850                 {
1851                   size_t k;
1852                   VEC_truncate (tree, vargs, 0);
1853                   for (k = 0; k < nargs; k++)
1854                     {
1855                       VEC (tree, heap) *vec_oprndsk
1856                         = (VEC (tree, heap) *)
1857                           VEC_index (slp_void_p, vec_defs, k);
1858                       VEC_quick_push (tree, vargs,
1859                                       VEC_index (tree, vec_oprndsk, i));
1860                       VEC_quick_push (tree, vargs,
1861                                       VEC_index (tree, vec_oprndsk, i + 1));
1862                     }
1863                   new_stmt = gimple_build_call_vec (fndecl, vargs);
1864                   new_temp = make_ssa_name (vec_dest, new_stmt);
1865                   gimple_call_set_lhs (new_stmt, new_temp);
1866                   vect_finish_stmt_generation (stmt, new_stmt, gsi);
1867                   mark_symbols_for_renaming (new_stmt);
1868                   VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node),
1869                                   new_stmt);
1870                 }
1871
1872               for (i = 0; i < nargs; i++)
1873                 {
1874                   VEC (tree, heap) *vec_oprndsi
1875                     = (VEC (tree, heap) *)
1876                       VEC_index (slp_void_p, vec_defs, i);
1877                   VEC_free (tree, heap, vec_oprndsi);
1878                 }
1879               VEC_free (slp_void_p, heap, vec_defs);
1880               continue;
1881             }
1882
1883           for (i = 0; i < nargs; i++)
1884             {
1885               op = gimple_call_arg (stmt, i);
1886               if (j == 0)
1887                 {
1888                   vec_oprnd0
1889                     = vect_get_vec_def_for_operand (op, stmt, NULL);
1890                   vec_oprnd1
1891                     = vect_get_vec_def_for_stmt_copy (dt[i], vec_oprnd0);
1892                 }
1893               else
1894                 {
1895                   vec_oprnd1 = gimple_call_arg (new_stmt, 2*i + 1);
1896                   vec_oprnd0
1897                     = vect_get_vec_def_for_stmt_copy (dt[i], vec_oprnd1);
1898                   vec_oprnd1
1899                     = vect_get_vec_def_for_stmt_copy (dt[i], vec_oprnd0);
1900                 }
1901
1902               VEC_quick_push (tree, vargs, vec_oprnd0);
1903               VEC_quick_push (tree, vargs, vec_oprnd1);
1904             }
1905
1906           new_stmt = gimple_build_call_vec (fndecl, vargs);
1907           new_temp = make_ssa_name (vec_dest, new_stmt);
1908           gimple_call_set_lhs (new_stmt, new_temp);
1909
1910           vect_finish_stmt_generation (stmt, new_stmt, gsi);
1911           mark_symbols_for_renaming (new_stmt);
1912
1913           if (j == 0)
1914             STMT_VINFO_VEC_STMT (stmt_info) = new_stmt;
1915           else
1916             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
1917
1918           prev_stmt_info = vinfo_for_stmt (new_stmt);
1919         }
1920
1921       *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
1922
1923       break;
1924
1925     case WIDEN:
1926       /* No current target implements this case.  */
1927       return false;
1928     }
1929
1930   VEC_free (tree, heap, vargs);
1931
1932   /* Update the exception handling table with the vector stmt if necessary.  */
1933   if (maybe_clean_or_replace_eh_stmt (stmt, *vec_stmt))
1934     gimple_purge_dead_eh_edges (gimple_bb (stmt));
1935
1936   /* The call in STMT might prevent it from being removed in dce.
1937      We however cannot remove it here, due to the way the ssa name
1938      it defines is mapped to the new definition.  So just replace
1939      rhs of the statement with something harmless.  */
1940
1941   if (slp_node)
1942     return true;
1943
1944   type = TREE_TYPE (scalar_dest);
1945   if (is_pattern_stmt_p (stmt_info))
1946     lhs = gimple_call_lhs (STMT_VINFO_RELATED_STMT (stmt_info));
1947   else
1948     lhs = gimple_call_lhs (stmt);
1949   new_stmt = gimple_build_assign (lhs, build_zero_cst (type));
1950   set_vinfo_for_stmt (new_stmt, stmt_info);
1951   set_vinfo_for_stmt (stmt, NULL);
1952   STMT_VINFO_STMT (stmt_info) = new_stmt;
1953   gsi_replace (gsi, new_stmt, false);
1954   SSA_NAME_DEF_STMT (gimple_assign_lhs (new_stmt)) = new_stmt;
1955
1956   return true;
1957 }
1958
1959
1960 /* Function vect_gen_widened_results_half
1961
1962    Create a vector stmt whose code, type, number of arguments, and result
1963    variable are CODE, OP_TYPE, and VEC_DEST, and its arguments are
1964    VEC_OPRND0 and VEC_OPRND1.  The new vector stmt is to be inserted at BSI.
1965    In the case that CODE is a CALL_EXPR, this means that a call to DECL
1966    needs to be created (DECL is a function-decl of a target-builtin).
1967    STMT is the original scalar stmt that we are vectorizing.  */
1968
1969 static gimple
1970 vect_gen_widened_results_half (enum tree_code code,
1971                                tree decl,
1972                                tree vec_oprnd0, tree vec_oprnd1, int op_type,
1973                                tree vec_dest, gimple_stmt_iterator *gsi,
1974                                gimple stmt)
1975 {
1976   gimple new_stmt;
1977   tree new_temp;
1978
1979   /* Generate half of the widened result:  */
1980   if (code == CALL_EXPR)
1981     {
1982       /* Target specific support  */
1983       if (op_type == binary_op)
1984         new_stmt = gimple_build_call (decl, 2, vec_oprnd0, vec_oprnd1);
1985       else
1986         new_stmt = gimple_build_call (decl, 1, vec_oprnd0);
1987       new_temp = make_ssa_name (vec_dest, new_stmt);
1988       gimple_call_set_lhs (new_stmt, new_temp);
1989     }
1990   else
1991     {
1992       /* Generic support */
1993       gcc_assert (op_type == TREE_CODE_LENGTH (code));
1994       if (op_type != binary_op)
1995         vec_oprnd1 = NULL;
1996       new_stmt = gimple_build_assign_with_ops (code, vec_dest, vec_oprnd0,
1997                                                vec_oprnd1);
1998       new_temp = make_ssa_name (vec_dest, new_stmt);
1999       gimple_assign_set_lhs (new_stmt, new_temp);
2000     }
2001   vect_finish_stmt_generation (stmt, new_stmt, gsi);
2002
2003   return new_stmt;
2004 }
2005
2006
2007 /* Get vectorized definitions for loop-based vectorization.  For the first
2008    operand we call vect_get_vec_def_for_operand() (with OPRND containing
2009    scalar operand), and for the rest we get a copy with
2010    vect_get_vec_def_for_stmt_copy() using the previous vector definition
2011    (stored in OPRND). See vect_get_vec_def_for_stmt_copy() for details.
2012    The vectors are collected into VEC_OPRNDS.  */
2013
2014 static void
2015 vect_get_loop_based_defs (tree *oprnd, gimple stmt, enum vect_def_type dt,
2016                           VEC (tree, heap) **vec_oprnds, int multi_step_cvt)
2017 {
2018   tree vec_oprnd;
2019
2020   /* Get first vector operand.  */
2021   /* All the vector operands except the very first one (that is scalar oprnd)
2022      are stmt copies.  */
2023   if (TREE_CODE (TREE_TYPE (*oprnd)) != VECTOR_TYPE)
2024     vec_oprnd = vect_get_vec_def_for_operand (*oprnd, stmt, NULL);
2025   else
2026     vec_oprnd = vect_get_vec_def_for_stmt_copy (dt, *oprnd);
2027
2028   VEC_quick_push (tree, *vec_oprnds, vec_oprnd);
2029
2030   /* Get second vector operand.  */
2031   vec_oprnd = vect_get_vec_def_for_stmt_copy (dt, vec_oprnd);
2032   VEC_quick_push (tree, *vec_oprnds, vec_oprnd);
2033
2034   *oprnd = vec_oprnd;
2035
2036   /* For conversion in multiple steps, continue to get operands
2037      recursively.  */
2038   if (multi_step_cvt)
2039     vect_get_loop_based_defs (oprnd, stmt, dt, vec_oprnds,  multi_step_cvt - 1);
2040 }
2041
2042
2043 /* Create vectorized demotion statements for vector operands from VEC_OPRNDS.
2044    For multi-step conversions store the resulting vectors and call the function
2045    recursively.  */
2046
2047 static void
2048 vect_create_vectorized_demotion_stmts (VEC (tree, heap) **vec_oprnds,
2049                                        int multi_step_cvt, gimple stmt,
2050                                        VEC (tree, heap) *vec_dsts,
2051                                        gimple_stmt_iterator *gsi,
2052                                        slp_tree slp_node, enum tree_code code,
2053                                        stmt_vec_info *prev_stmt_info)
2054 {
2055   unsigned int i;
2056   tree vop0, vop1, new_tmp, vec_dest;
2057   gimple new_stmt;
2058   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2059
2060   vec_dest = VEC_pop (tree, vec_dsts);
2061
2062   for (i = 0; i < VEC_length (tree, *vec_oprnds); i += 2)
2063     {
2064       /* Create demotion operation.  */
2065       vop0 = VEC_index (tree, *vec_oprnds, i);
2066       vop1 = VEC_index (tree, *vec_oprnds, i + 1);
2067       new_stmt = gimple_build_assign_with_ops (code, vec_dest, vop0, vop1);
2068       new_tmp = make_ssa_name (vec_dest, new_stmt);
2069       gimple_assign_set_lhs (new_stmt, new_tmp);
2070       vect_finish_stmt_generation (stmt, new_stmt, gsi);
2071
2072       if (multi_step_cvt)
2073         /* Store the resulting vector for next recursive call.  */
2074         VEC_replace (tree, *vec_oprnds, i/2, new_tmp);
2075       else
2076         {
2077           /* This is the last step of the conversion sequence. Store the
2078              vectors in SLP_NODE or in vector info of the scalar statement
2079              (or in STMT_VINFO_RELATED_STMT chain).  */
2080           if (slp_node)
2081             VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
2082           else
2083             {
2084               if (!*prev_stmt_info)
2085                 STMT_VINFO_VEC_STMT (stmt_info) = new_stmt;
2086               else
2087                 STMT_VINFO_RELATED_STMT (*prev_stmt_info) = new_stmt;
2088
2089               *prev_stmt_info = vinfo_for_stmt (new_stmt);
2090             }
2091         }
2092     }
2093
2094   /* For multi-step demotion operations we first generate demotion operations
2095      from the source type to the intermediate types, and then combine the
2096      results (stored in VEC_OPRNDS) in demotion operation to the destination
2097      type.  */
2098   if (multi_step_cvt)
2099     {
2100       /* At each level of recursion we have half of the operands we had at the
2101          previous level.  */
2102       VEC_truncate (tree, *vec_oprnds, (i+1)/2);
2103       vect_create_vectorized_demotion_stmts (vec_oprnds, multi_step_cvt - 1,
2104                                              stmt, vec_dsts, gsi, slp_node,
2105                                              VEC_PACK_TRUNC_EXPR,
2106                                              prev_stmt_info);
2107     }
2108
2109   VEC_quick_push (tree, vec_dsts, vec_dest);
2110 }
2111
2112
2113 /* Create vectorized promotion statements for vector operands from VEC_OPRNDS0
2114    and VEC_OPRNDS1 (for binary operations).  For multi-step conversions store
2115    the resulting vectors and call the function recursively.  */
2116
2117 static void
2118 vect_create_vectorized_promotion_stmts (VEC (tree, heap) **vec_oprnds0,
2119                                         VEC (tree, heap) **vec_oprnds1,
2120                                         gimple stmt, tree vec_dest,
2121                                         gimple_stmt_iterator *gsi,
2122                                         enum tree_code code1,
2123                                         enum tree_code code2, tree decl1,
2124                                         tree decl2, int op_type)
2125 {
2126   int i;
2127   tree vop0, vop1, new_tmp1, new_tmp2;
2128   gimple new_stmt1, new_stmt2;
2129   VEC (tree, heap) *vec_tmp = NULL;
2130
2131   vec_tmp = VEC_alloc (tree, heap, VEC_length (tree, *vec_oprnds0) * 2);
2132   FOR_EACH_VEC_ELT (tree, *vec_oprnds0, i, vop0)
2133     {
2134       if (op_type == binary_op)
2135         vop1 = VEC_index (tree, *vec_oprnds1, i);
2136       else
2137         vop1 = NULL_TREE;
2138
2139       /* Generate the two halves of promotion operation.  */
2140       new_stmt1 = vect_gen_widened_results_half (code1, decl1, vop0, vop1,
2141                                                  op_type, vec_dest, gsi, stmt);
2142       new_stmt2 = vect_gen_widened_results_half (code2, decl2, vop0, vop1,
2143                                                  op_type, vec_dest, gsi, stmt);
2144       if (is_gimple_call (new_stmt1))
2145         {
2146           new_tmp1 = gimple_call_lhs (new_stmt1);
2147           new_tmp2 = gimple_call_lhs (new_stmt2);
2148         }
2149       else
2150         {
2151           new_tmp1 = gimple_assign_lhs (new_stmt1);
2152           new_tmp2 = gimple_assign_lhs (new_stmt2);
2153         }
2154
2155       /* Store the results for the next step.  */
2156       VEC_quick_push (tree, vec_tmp, new_tmp1);
2157       VEC_quick_push (tree, vec_tmp, new_tmp2);
2158     }
2159
2160   VEC_free (tree, heap, *vec_oprnds0);
2161   *vec_oprnds0 = vec_tmp;
2162 }
2163
2164
2165 /* Check if STMT performs a conversion operation, that can be vectorized.
2166    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2167    stmt to replace it, put it in VEC_STMT, and insert it at GSI.
2168    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
2169
2170 static bool
2171 vectorizable_conversion (gimple stmt, gimple_stmt_iterator *gsi,
2172                          gimple *vec_stmt, slp_tree slp_node)
2173 {
2174   tree vec_dest;
2175   tree scalar_dest;
2176   tree op0, op1 = NULL_TREE;
2177   tree vec_oprnd0 = NULL_TREE, vec_oprnd1 = NULL_TREE;
2178   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2179   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2180   enum tree_code code, code1 = ERROR_MARK, code2 = ERROR_MARK;
2181   enum tree_code codecvt1 = ERROR_MARK, codecvt2 = ERROR_MARK;
2182   tree decl1 = NULL_TREE, decl2 = NULL_TREE;
2183   tree new_temp;
2184   tree def;
2185   gimple def_stmt;
2186   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
2187   gimple new_stmt = NULL;
2188   stmt_vec_info prev_stmt_info;
2189   int nunits_in;
2190   int nunits_out;
2191   tree vectype_out, vectype_in;
2192   int ncopies, i, j;
2193   tree lhs_type, rhs_type;
2194   enum { NARROW, NONE, WIDEN } modifier;
2195   VEC (tree,heap) *vec_oprnds0 = NULL, *vec_oprnds1 = NULL;
2196   tree vop0;
2197   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
2198   int multi_step_cvt = 0;
2199   VEC (tree, heap) *vec_dsts = NULL, *interm_types = NULL;
2200   tree last_oprnd, intermediate_type, cvt_type = NULL_TREE;
2201   int op_type;
2202   enum machine_mode rhs_mode;
2203   unsigned short fltsz;
2204
2205   /* Is STMT a vectorizable conversion?   */
2206
2207   if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
2208     return false;
2209
2210   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
2211     return false;
2212
2213   if (!is_gimple_assign (stmt))
2214     return false;
2215
2216   if (TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
2217     return false;
2218
2219   code = gimple_assign_rhs_code (stmt);
2220   if (!CONVERT_EXPR_CODE_P (code)
2221       && code != FIX_TRUNC_EXPR
2222       && code != FLOAT_EXPR
2223       && code != WIDEN_MULT_EXPR
2224       && code != WIDEN_LSHIFT_EXPR)
2225     return false;
2226
2227   op_type = TREE_CODE_LENGTH (code);
2228
2229   /* Check types of lhs and rhs.  */
2230   scalar_dest = gimple_assign_lhs (stmt);
2231   lhs_type = TREE_TYPE (scalar_dest);
2232   vectype_out = STMT_VINFO_VECTYPE (stmt_info);
2233
2234   op0 = gimple_assign_rhs1 (stmt);
2235   rhs_type = TREE_TYPE (op0);
2236
2237   if ((code != FIX_TRUNC_EXPR && code != FLOAT_EXPR)
2238       && !((INTEGRAL_TYPE_P (lhs_type)
2239             && INTEGRAL_TYPE_P (rhs_type))
2240            || (SCALAR_FLOAT_TYPE_P (lhs_type)
2241                && SCALAR_FLOAT_TYPE_P (rhs_type))))
2242     return false;
2243
2244   if ((INTEGRAL_TYPE_P (lhs_type)
2245        && (TYPE_PRECISION (lhs_type)
2246            != GET_MODE_PRECISION (TYPE_MODE (lhs_type))))
2247       || (INTEGRAL_TYPE_P (rhs_type)
2248           && (TYPE_PRECISION (rhs_type)
2249               != GET_MODE_PRECISION (TYPE_MODE (rhs_type)))))
2250     {
2251       if (vect_print_dump_info (REPORT_DETAILS))
2252         fprintf (vect_dump,
2253                  "type conversion to/from bit-precision unsupported.");
2254       return false;
2255     }
2256
2257   /* Check the operands of the operation.  */
2258   if (!vect_is_simple_use_1 (op0, stmt, loop_vinfo, bb_vinfo,
2259                              &def_stmt, &def, &dt[0], &vectype_in))
2260     {
2261       if (vect_print_dump_info (REPORT_DETAILS))
2262         fprintf (vect_dump, "use not simple.");
2263       return false;
2264     }
2265   if (op_type == binary_op)
2266     {
2267       bool ok;
2268
2269       op1 = gimple_assign_rhs2 (stmt);
2270       gcc_assert (code == WIDEN_MULT_EXPR || code == WIDEN_LSHIFT_EXPR);
2271       /* For WIDEN_MULT_EXPR, if OP0 is a constant, use the type of
2272          OP1.  */
2273       if (CONSTANT_CLASS_P (op0))
2274         ok = vect_is_simple_use_1 (op1, stmt, loop_vinfo, NULL,
2275                                    &def_stmt, &def, &dt[1], &vectype_in);
2276       else
2277         ok = vect_is_simple_use (op1, stmt, loop_vinfo, NULL, &def_stmt,
2278                                  &def, &dt[1]);
2279
2280       if (!ok)
2281         {
2282           if (vect_print_dump_info (REPORT_DETAILS))
2283             fprintf (vect_dump, "use not simple.");
2284           return false;
2285         }
2286     }
2287
2288   /* If op0 is an external or constant defs use a vector type of
2289      the same size as the output vector type.  */
2290   if (!vectype_in)
2291     vectype_in = get_same_sized_vectype (rhs_type, vectype_out);
2292   if (vec_stmt)
2293     gcc_assert (vectype_in);
2294   if (!vectype_in)
2295     {
2296       if (vect_print_dump_info (REPORT_DETAILS))
2297         {
2298           fprintf (vect_dump, "no vectype for scalar type ");
2299           print_generic_expr (vect_dump, rhs_type, TDF_SLIM);
2300         }
2301
2302       return false;
2303     }
2304
2305   nunits_in = TYPE_VECTOR_SUBPARTS (vectype_in);
2306   nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
2307   if (nunits_in < nunits_out)
2308     modifier = NARROW;
2309   else if (nunits_out == nunits_in)
2310     modifier = NONE;
2311   else
2312     modifier = WIDEN;
2313
2314   /* Multiple types in SLP are handled by creating the appropriate number of
2315      vectorized stmts for each SLP node.  Hence, NCOPIES is always 1 in
2316      case of SLP.  */
2317   if (slp_node || PURE_SLP_STMT (stmt_info))
2318     ncopies = 1;
2319   else if (modifier == NARROW)
2320     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_out;
2321   else
2322     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_in;
2323
2324   /* Sanity check: make sure that at least one copy of the vectorized stmt
2325      needs to be generated.  */
2326   gcc_assert (ncopies >= 1);
2327
2328   /* Supportable by target?  */
2329   switch (modifier)
2330     {
2331     case NONE:
2332       if (code != FIX_TRUNC_EXPR && code != FLOAT_EXPR)
2333         return false;
2334       if (supportable_convert_operation (code, vectype_out, vectype_in,
2335                                          &decl1, &code1))
2336         break;
2337       /* FALLTHRU */
2338     unsupported:
2339       if (vect_print_dump_info (REPORT_DETAILS))
2340         fprintf (vect_dump, "conversion not supported by target.");
2341       return false;
2342
2343     case WIDEN:
2344       if (supportable_widening_operation (code, stmt, vectype_out, vectype_in,
2345                                           &decl1, &decl2, &code1, &code2,
2346                                           &multi_step_cvt, &interm_types))
2347         {
2348           /* Binary widening operation can only be supported directly by the
2349              architecture.  */
2350           gcc_assert (!(multi_step_cvt && op_type == binary_op));
2351           break;
2352         }
2353
2354       if (code != FLOAT_EXPR
2355           || (GET_MODE_SIZE (TYPE_MODE (lhs_type))
2356               <= GET_MODE_SIZE (TYPE_MODE (rhs_type))))
2357         goto unsupported;
2358
2359       rhs_mode = TYPE_MODE (rhs_type);
2360       fltsz = GET_MODE_SIZE (TYPE_MODE (lhs_type));
2361       for (rhs_mode = GET_MODE_2XWIDER_MODE (TYPE_MODE (rhs_type));
2362            rhs_mode != VOIDmode && GET_MODE_SIZE (rhs_mode) <= fltsz;
2363            rhs_mode = GET_MODE_2XWIDER_MODE (rhs_mode))
2364         {
2365           cvt_type
2366             = build_nonstandard_integer_type (GET_MODE_BITSIZE (rhs_mode), 0);
2367           cvt_type = get_same_sized_vectype (cvt_type, vectype_in);
2368           if (cvt_type == NULL_TREE)
2369             goto unsupported;
2370
2371           if (GET_MODE_SIZE (rhs_mode) == fltsz)
2372             {
2373               if (!supportable_convert_operation (code, vectype_out,
2374                                                   cvt_type, &decl1, &codecvt1))
2375                 goto unsupported;
2376             }
2377           else if (!supportable_widening_operation (code, stmt, vectype_out,
2378                                                     cvt_type, &decl1, &decl2,
2379                                                     &codecvt1, &codecvt2,
2380                                                     &multi_step_cvt,
2381                                                     &interm_types))
2382             continue;
2383           else
2384             gcc_assert (multi_step_cvt == 0);
2385
2386           if (supportable_widening_operation (NOP_EXPR, stmt, cvt_type,
2387                                               vectype_in, NULL, NULL, &code1,
2388                                               &code2, &multi_step_cvt,
2389                                               &interm_types))
2390             break;
2391         }
2392
2393       if (rhs_mode == VOIDmode || GET_MODE_SIZE (rhs_mode) > fltsz)
2394         goto unsupported;
2395
2396       if (GET_MODE_SIZE (rhs_mode) == fltsz)
2397         codecvt2 = ERROR_MARK;
2398       else
2399         {
2400           multi_step_cvt++;
2401           VEC_safe_push (tree, heap, interm_types, cvt_type);
2402           cvt_type = NULL_TREE;
2403         }
2404       break;
2405
2406     case NARROW:
2407       gcc_assert (op_type == unary_op);
2408       if (supportable_narrowing_operation (code, vectype_out, vectype_in,
2409                                            &code1, &multi_step_cvt,
2410                                            &interm_types))
2411         break;
2412
2413       if (code != FIX_TRUNC_EXPR
2414           || (GET_MODE_SIZE (TYPE_MODE (lhs_type))
2415               >= GET_MODE_SIZE (TYPE_MODE (rhs_type))))
2416         goto unsupported;
2417
2418       rhs_mode = TYPE_MODE (rhs_type);
2419       cvt_type
2420         = build_nonstandard_integer_type (GET_MODE_BITSIZE (rhs_mode), 0);
2421       cvt_type = get_same_sized_vectype (cvt_type, vectype_in);
2422       if (cvt_type == NULL_TREE)
2423         goto unsupported;
2424       if (!supportable_convert_operation (code, cvt_type, vectype_in,
2425                                           &decl1, &codecvt1))
2426         goto unsupported;
2427       if (supportable_narrowing_operation (NOP_EXPR, vectype_out, cvt_type,
2428                                            &code1, &multi_step_cvt,
2429                                            &interm_types))
2430         break;
2431       goto unsupported;
2432
2433     default:
2434       gcc_unreachable ();
2435     }
2436
2437   if (!vec_stmt)                /* transformation not required.  */
2438     {
2439       if (vect_print_dump_info (REPORT_DETAILS))
2440         fprintf (vect_dump, "=== vectorizable_conversion ===");
2441       if (code == FIX_TRUNC_EXPR || code == FLOAT_EXPR)
2442         {
2443           STMT_VINFO_TYPE (stmt_info) = type_conversion_vec_info_type;
2444           vect_model_simple_cost (stmt_info, ncopies, dt, NULL);
2445         }
2446       else if (modifier == NARROW)
2447         {
2448           STMT_VINFO_TYPE (stmt_info) = type_demotion_vec_info_type;
2449           vect_model_promotion_demotion_cost (stmt_info, dt, multi_step_cvt);
2450         }
2451       else
2452         {
2453           STMT_VINFO_TYPE (stmt_info) = type_promotion_vec_info_type;
2454           vect_model_promotion_demotion_cost (stmt_info, dt, multi_step_cvt);
2455         }
2456       VEC_free (tree, heap, interm_types);
2457       return true;
2458     }
2459
2460   /** Transform.  **/
2461   if (vect_print_dump_info (REPORT_DETAILS))
2462     fprintf (vect_dump, "transform conversion. ncopies = %d.", ncopies);
2463
2464   if (op_type == binary_op)
2465     {
2466       if (CONSTANT_CLASS_P (op0))
2467         op0 = fold_convert (TREE_TYPE (op1), op0);
2468       else if (CONSTANT_CLASS_P (op1))
2469         op1 = fold_convert (TREE_TYPE (op0), op1);
2470     }
2471
2472   /* In case of multi-step conversion, we first generate conversion operations
2473      to the intermediate types, and then from that types to the final one.
2474      We create vector destinations for the intermediate type (TYPES) received
2475      from supportable_*_operation, and store them in the correct order
2476      for future use in vect_create_vectorized_*_stmts ().  */
2477   vec_dsts = VEC_alloc (tree, heap, multi_step_cvt + 1);
2478   vec_dest = vect_create_destination_var (scalar_dest,
2479                                           (cvt_type && modifier == WIDEN)
2480                                           ? cvt_type : vectype_out);
2481   VEC_quick_push (tree, vec_dsts, vec_dest);
2482
2483   if (multi_step_cvt)
2484     {
2485       for (i = VEC_length (tree, interm_types) - 1;
2486            VEC_iterate (tree, interm_types, i, intermediate_type); i--)
2487         {
2488           vec_dest = vect_create_destination_var (scalar_dest,
2489                                                   intermediate_type);
2490           VEC_quick_push (tree, vec_dsts, vec_dest);
2491         }
2492     }
2493
2494   if (cvt_type)
2495     vec_dest = vect_create_destination_var (scalar_dest,
2496                                             modifier == WIDEN
2497                                             ? vectype_out : cvt_type);
2498
2499   if (!slp_node)
2500     {
2501       if (modifier == NONE)
2502         vec_oprnds0 = VEC_alloc (tree, heap, 1);
2503       else if (modifier == WIDEN)
2504         {
2505           vec_oprnds0 = VEC_alloc (tree, heap,
2506                                    (multi_step_cvt
2507                                     ? vect_pow2 (multi_step_cvt) : 1));
2508           if (op_type == binary_op)
2509             vec_oprnds1 = VEC_alloc (tree, heap, 1);
2510         }
2511       else
2512         vec_oprnds0 = VEC_alloc (tree, heap,
2513                                  2 * (multi_step_cvt
2514                                       ? vect_pow2 (multi_step_cvt) : 1));
2515     }
2516   else if (code == WIDEN_LSHIFT_EXPR)
2517     vec_oprnds1 = VEC_alloc (tree, heap, slp_node->vec_stmts_size);
2518
2519   last_oprnd = op0;
2520   prev_stmt_info = NULL;
2521   switch (modifier)
2522     {
2523     case NONE:
2524       for (j = 0; j < ncopies; j++)
2525         {
2526           if (j == 0)
2527             vect_get_vec_defs (op0, NULL, stmt, &vec_oprnds0, NULL, slp_node,
2528                                -1);
2529           else
2530             vect_get_vec_defs_for_stmt_copy (dt, &vec_oprnds0, NULL);
2531
2532           FOR_EACH_VEC_ELT (tree, vec_oprnds0, i, vop0)
2533             {
2534               /* Arguments are ready, create the new vector stmt.  */
2535               if (code1 == CALL_EXPR)
2536                 {
2537                   new_stmt = gimple_build_call (decl1, 1, vop0);
2538                   new_temp = make_ssa_name (vec_dest, new_stmt);
2539                   gimple_call_set_lhs (new_stmt, new_temp);
2540                 }
2541               else
2542                 {
2543                   gcc_assert (TREE_CODE_LENGTH (code1) == unary_op);
2544                   new_stmt = gimple_build_assign_with_ops (code1, vec_dest,
2545                                                            vop0, NULL);
2546                   new_temp = make_ssa_name (vec_dest, new_stmt);
2547                   gimple_assign_set_lhs (new_stmt, new_temp);
2548                 }
2549
2550               vect_finish_stmt_generation (stmt, new_stmt, gsi);
2551               if (slp_node)
2552                 VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node),
2553                                 new_stmt);
2554             }
2555
2556           if (j == 0)
2557             STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
2558           else
2559             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
2560           prev_stmt_info = vinfo_for_stmt (new_stmt);
2561         }
2562       break;
2563
2564     case WIDEN:
2565       /* In case the vectorization factor (VF) is bigger than the number
2566          of elements that we can fit in a vectype (nunits), we have to
2567          generate more than one vector stmt - i.e - we need to "unroll"
2568          the vector stmt by a factor VF/nunits.  */
2569       for (j = 0; j < ncopies; j++)
2570         {
2571           /* Handle uses.  */
2572           if (j == 0)
2573             {
2574               if (slp_node)
2575                 {
2576                   if (code == WIDEN_LSHIFT_EXPR)
2577                     {
2578                       unsigned int k;
2579
2580                       vec_oprnd1 = op1;
2581                       /* Store vec_oprnd1 for every vector stmt to be created
2582                          for SLP_NODE.  We check during the analysis that all
2583                          the shift arguments are the same.  */
2584                       for (k = 0; k < slp_node->vec_stmts_size - 1; k++)
2585                         VEC_quick_push (tree, vec_oprnds1, vec_oprnd1);
2586
2587                       vect_get_vec_defs (op0, NULL_TREE, stmt, &vec_oprnds0, NULL,
2588                                          slp_node, -1);
2589                     }
2590                   else
2591                     vect_get_vec_defs (op0, op1, stmt, &vec_oprnds0,
2592                                        &vec_oprnds1, slp_node, -1);
2593                 }
2594               else
2595                 {
2596                   vec_oprnd0 = vect_get_vec_def_for_operand (op0, stmt, NULL);
2597                   VEC_quick_push (tree, vec_oprnds0, vec_oprnd0);
2598                   if (op_type == binary_op)
2599                     {
2600                       if (code == WIDEN_LSHIFT_EXPR)
2601                         vec_oprnd1 = op1;
2602                       else
2603                         vec_oprnd1 = vect_get_vec_def_for_operand (op1, stmt,
2604                                                                    NULL);
2605                       VEC_quick_push (tree, vec_oprnds1, vec_oprnd1);
2606                     }
2607                 }
2608             }
2609           else
2610             {
2611               vec_oprnd0 = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd0);
2612               VEC_truncate (tree, vec_oprnds0, 0);
2613               VEC_quick_push (tree, vec_oprnds0, vec_oprnd0);
2614               if (op_type == binary_op)
2615                 {
2616                   if (code == WIDEN_LSHIFT_EXPR)
2617                     vec_oprnd1 = op1;
2618                   else
2619                     vec_oprnd1 = vect_get_vec_def_for_stmt_copy (dt[1],
2620                                                                  vec_oprnd1);
2621                   VEC_truncate (tree, vec_oprnds1, 0);
2622                   VEC_quick_push (tree, vec_oprnds1, vec_oprnd1);
2623                 }
2624             }
2625
2626           /* Arguments are ready.  Create the new vector stmts.  */
2627           for (i = multi_step_cvt; i >= 0; i--)
2628             {
2629               tree this_dest = VEC_index (tree, vec_dsts, i);
2630               enum tree_code c1 = code1, c2 = code2;
2631               if (i == 0 && codecvt2 != ERROR_MARK)
2632                 {
2633                   c1 = codecvt1;
2634                   c2 = codecvt2;
2635                 }
2636               vect_create_vectorized_promotion_stmts (&vec_oprnds0,
2637                                                       &vec_oprnds1,
2638                                                       stmt, this_dest, gsi,
2639                                                       c1, c2, decl1, decl2,
2640                                                       op_type);
2641             }
2642
2643           FOR_EACH_VEC_ELT (tree, vec_oprnds0, i, vop0)
2644             {
2645               if (cvt_type)
2646                 {
2647                   if (codecvt1 == CALL_EXPR)
2648                     {
2649                       new_stmt = gimple_build_call (decl1, 1, vop0);
2650                       new_temp = make_ssa_name (vec_dest, new_stmt);
2651                       gimple_call_set_lhs (new_stmt, new_temp);
2652                     }
2653                   else
2654                     {
2655                       gcc_assert (TREE_CODE_LENGTH (codecvt1) == unary_op);
2656                       new_temp = make_ssa_name (vec_dest, NULL);
2657                       new_stmt = gimple_build_assign_with_ops (codecvt1,
2658                                                                new_temp,
2659                                                                vop0, NULL);
2660                     }
2661
2662                   vect_finish_stmt_generation (stmt, new_stmt, gsi);
2663                 }
2664               else
2665                 new_stmt = SSA_NAME_DEF_STMT (vop0);
2666
2667               if (slp_node)
2668                 VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node),
2669                                 new_stmt);
2670               else
2671                 {
2672                   if (!prev_stmt_info)
2673                     STMT_VINFO_VEC_STMT (stmt_info) = new_stmt;
2674                   else
2675                     STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
2676                   prev_stmt_info = vinfo_for_stmt (new_stmt);
2677                 }
2678             }
2679         }
2680
2681       *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
2682       break;
2683
2684     case NARROW:
2685       /* In case the vectorization factor (VF) is bigger than the number
2686          of elements that we can fit in a vectype (nunits), we have to
2687          generate more than one vector stmt - i.e - we need to "unroll"
2688          the vector stmt by a factor VF/nunits.  */
2689       for (j = 0; j < ncopies; j++)
2690         {
2691           /* Handle uses.  */
2692           if (slp_node)
2693             vect_get_vec_defs (op0, NULL_TREE, stmt, &vec_oprnds0, NULL,
2694                                slp_node, -1);
2695           else
2696             {
2697               VEC_truncate (tree, vec_oprnds0, 0);
2698               vect_get_loop_based_defs (&last_oprnd, stmt, dt[0], &vec_oprnds0,
2699                                         vect_pow2 (multi_step_cvt) - 1);
2700             }
2701
2702           /* Arguments are ready.  Create the new vector stmts.  */
2703           if (cvt_type)
2704             FOR_EACH_VEC_ELT (tree, vec_oprnds0, i, vop0)
2705               {
2706                 if (codecvt1 == CALL_EXPR)
2707                   {
2708                     new_stmt = gimple_build_call (decl1, 1, vop0);
2709                     new_temp = make_ssa_name (vec_dest, new_stmt);
2710                     gimple_call_set_lhs (new_stmt, new_temp);
2711                   }
2712                 else
2713                   {
2714                     gcc_assert (TREE_CODE_LENGTH (codecvt1) == unary_op);
2715                     new_temp = make_ssa_name (vec_dest, NULL);
2716                     new_stmt = gimple_build_assign_with_ops (codecvt1, new_temp,
2717                                                              vop0, NULL);
2718                   }
2719
2720                 vect_finish_stmt_generation (stmt, new_stmt, gsi);
2721                 VEC_replace (tree, vec_oprnds0, i, new_temp);
2722               }
2723
2724           vect_create_vectorized_demotion_stmts (&vec_oprnds0, multi_step_cvt,
2725                                                  stmt, vec_dsts, gsi,
2726                                                  slp_node, code1,
2727                                                  &prev_stmt_info);
2728         }
2729
2730       *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
2731       break;
2732     }
2733
2734   VEC_free (tree, heap, vec_oprnds0);
2735   VEC_free (tree, heap, vec_oprnds1);
2736   VEC_free (tree, heap, vec_dsts);
2737   VEC_free (tree, heap, interm_types);
2738
2739   return true;
2740 }
2741
2742
2743 /* Function vectorizable_assignment.
2744
2745    Check if STMT performs an assignment (copy) that can be vectorized.
2746    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2747    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2748    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
2749
2750 static bool
2751 vectorizable_assignment (gimple stmt, gimple_stmt_iterator *gsi,
2752                          gimple *vec_stmt, slp_tree slp_node)
2753 {
2754   tree vec_dest;
2755   tree scalar_dest;
2756   tree op;
2757   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2758   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
2759   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2760   tree new_temp;
2761   tree def;
2762   gimple def_stmt;
2763   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
2764   unsigned int nunits = TYPE_VECTOR_SUBPARTS (vectype);
2765   int ncopies;
2766   int i, j;
2767   VEC(tree,heap) *vec_oprnds = NULL;
2768   tree vop;
2769   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
2770   gimple new_stmt = NULL;
2771   stmt_vec_info prev_stmt_info = NULL;
2772   enum tree_code code;
2773   tree vectype_in;
2774
2775   /* Multiple types in SLP are handled by creating the appropriate number of
2776      vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
2777      case of SLP.  */
2778   if (slp_node || PURE_SLP_STMT (stmt_info))
2779     ncopies = 1;
2780   else
2781     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
2782
2783   gcc_assert (ncopies >= 1);
2784
2785   if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
2786     return false;
2787
2788   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
2789     return false;
2790
2791   /* Is vectorizable assignment?  */
2792   if (!is_gimple_assign (stmt))
2793     return false;
2794
2795   scalar_dest = gimple_assign_lhs (stmt);
2796   if (TREE_CODE (scalar_dest) != SSA_NAME)
2797     return false;
2798
2799   code = gimple_assign_rhs_code (stmt);
2800   if (gimple_assign_single_p (stmt)
2801       || code == PAREN_EXPR
2802       || CONVERT_EXPR_CODE_P (code))
2803     op = gimple_assign_rhs1 (stmt);
2804   else
2805     return false;
2806
2807   if (code == VIEW_CONVERT_EXPR)
2808     op = TREE_OPERAND (op, 0);
2809
2810   if (!vect_is_simple_use_1 (op, stmt, loop_vinfo, bb_vinfo,
2811                              &def_stmt, &def, &dt[0], &vectype_in))
2812     {
2813       if (vect_print_dump_info (REPORT_DETAILS))
2814         fprintf (vect_dump, "use not simple.");
2815       return false;
2816     }
2817
2818   /* We can handle NOP_EXPR conversions that do not change the number
2819      of elements or the vector size.  */
2820   if ((CONVERT_EXPR_CODE_P (code)
2821        || code == VIEW_CONVERT_EXPR)
2822       && (!vectype_in
2823           || TYPE_VECTOR_SUBPARTS (vectype_in) != nunits
2824           || (GET_MODE_SIZE (TYPE_MODE (vectype))
2825               != GET_MODE_SIZE (TYPE_MODE (vectype_in)))))
2826     return false;
2827
2828   /* We do not handle bit-precision changes.  */
2829   if ((CONVERT_EXPR_CODE_P (code)
2830        || code == VIEW_CONVERT_EXPR)
2831       && INTEGRAL_TYPE_P (TREE_TYPE (scalar_dest))
2832       && ((TYPE_PRECISION (TREE_TYPE (scalar_dest))
2833            != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (scalar_dest))))
2834           || ((TYPE_PRECISION (TREE_TYPE (op))
2835                != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (op))))))
2836       /* But a conversion that does not change the bit-pattern is ok.  */
2837       && !((TYPE_PRECISION (TREE_TYPE (scalar_dest))
2838             > TYPE_PRECISION (TREE_TYPE (op)))
2839            && TYPE_UNSIGNED (TREE_TYPE (op))))
2840     {
2841       if (vect_print_dump_info (REPORT_DETAILS))
2842         fprintf (vect_dump, "type conversion to/from bit-precision "
2843                  "unsupported.");
2844       return false;
2845     }
2846
2847   if (!vec_stmt) /* transformation not required.  */
2848     {
2849       STMT_VINFO_TYPE (stmt_info) = assignment_vec_info_type;
2850       if (vect_print_dump_info (REPORT_DETAILS))
2851         fprintf (vect_dump, "=== vectorizable_assignment ===");
2852       vect_model_simple_cost (stmt_info, ncopies, dt, NULL);
2853       return true;
2854     }
2855
2856   /** Transform.  **/
2857   if (vect_print_dump_info (REPORT_DETAILS))
2858     fprintf (vect_dump, "transform assignment.");
2859
2860   /* Handle def.  */
2861   vec_dest = vect_create_destination_var (scalar_dest, vectype);
2862
2863   /* Handle use.  */
2864   for (j = 0; j < ncopies; j++)
2865     {
2866       /* Handle uses.  */
2867       if (j == 0)
2868         vect_get_vec_defs (op, NULL, stmt, &vec_oprnds, NULL, slp_node, -1);
2869       else
2870         vect_get_vec_defs_for_stmt_copy (dt, &vec_oprnds, NULL);
2871
2872       /* Arguments are ready. create the new vector stmt.  */
2873       FOR_EACH_VEC_ELT (tree, vec_oprnds, i, vop)
2874        {
2875          if (CONVERT_EXPR_CODE_P (code)
2876              || code == VIEW_CONVERT_EXPR)
2877            vop = build1 (VIEW_CONVERT_EXPR, vectype, vop);
2878          new_stmt = gimple_build_assign (vec_dest, vop);
2879          new_temp = make_ssa_name (vec_dest, new_stmt);
2880          gimple_assign_set_lhs (new_stmt, new_temp);
2881          vect_finish_stmt_generation (stmt, new_stmt, gsi);
2882          if (slp_node)
2883            VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
2884        }
2885
2886       if (slp_node)
2887         continue;
2888
2889       if (j == 0)
2890         STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
2891       else
2892         STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
2893
2894       prev_stmt_info = vinfo_for_stmt (new_stmt);
2895     }
2896
2897   VEC_free (tree, heap, vec_oprnds);
2898   return true;
2899 }
2900
2901
2902 /* Return TRUE if CODE (a shift operation) is supported for SCALAR_TYPE
2903    either as shift by a scalar or by a vector.  */
2904
2905 bool
2906 vect_supportable_shift (enum tree_code code, tree scalar_type)
2907 {
2908
2909   enum machine_mode vec_mode;
2910   optab optab;
2911   int icode;
2912   tree vectype;
2913
2914   vectype = get_vectype_for_scalar_type (scalar_type);
2915   if (!vectype)
2916     return false;
2917
2918   optab = optab_for_tree_code (code, vectype, optab_scalar);
2919   if (!optab
2920       || optab_handler (optab, TYPE_MODE (vectype)) == CODE_FOR_nothing)
2921     {
2922       optab = optab_for_tree_code (code, vectype, optab_vector);
2923       if (!optab
2924           || (optab_handler (optab, TYPE_MODE (vectype))
2925                       == CODE_FOR_nothing))
2926         return false;
2927     }
2928
2929   vec_mode = TYPE_MODE (vectype);
2930   icode = (int) optab_handler (optab, vec_mode);
2931   if (icode == CODE_FOR_nothing)
2932     return false;
2933
2934   return true;
2935 }
2936
2937
2938 /* Function vectorizable_shift.
2939
2940    Check if STMT performs a shift operation that can be vectorized.
2941    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2942    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2943    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
2944
2945 static bool
2946 vectorizable_shift (gimple stmt, gimple_stmt_iterator *gsi,
2947                     gimple *vec_stmt, slp_tree slp_node)
2948 {
2949   tree vec_dest;
2950   tree scalar_dest;
2951   tree op0, op1 = NULL;
2952   tree vec_oprnd1 = NULL_TREE;
2953   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2954   tree vectype;
2955   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2956   enum tree_code code;
2957   enum machine_mode vec_mode;
2958   tree new_temp;
2959   optab optab;
2960   int icode;
2961   enum machine_mode optab_op2_mode;
2962   tree def;
2963   gimple def_stmt;
2964   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
2965   gimple new_stmt = NULL;
2966   stmt_vec_info prev_stmt_info;
2967   int nunits_in;
2968   int nunits_out;
2969   tree vectype_out;
2970   tree op1_vectype;
2971   int ncopies;
2972   int j, i;
2973   VEC (tree, heap) *vec_oprnds0 = NULL, *vec_oprnds1 = NULL;
2974   tree vop0, vop1;
2975   unsigned int k;
2976   bool scalar_shift_arg = true;
2977   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
2978   int vf;
2979
2980   if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
2981     return false;
2982
2983   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
2984     return false;
2985
2986   /* Is STMT a vectorizable binary/unary operation?   */
2987   if (!is_gimple_assign (stmt))
2988     return false;
2989
2990   if (TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
2991     return false;
2992
2993   code = gimple_assign_rhs_code (stmt);
2994
2995   if (!(code == LSHIFT_EXPR || code == RSHIFT_EXPR || code == LROTATE_EXPR
2996       || code == RROTATE_EXPR))
2997     return false;
2998
2999   scalar_dest = gimple_assign_lhs (stmt);
3000   vectype_out = STMT_VINFO_VECTYPE (stmt_info);
3001   if (TYPE_PRECISION (TREE_TYPE (scalar_dest))
3002       != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (scalar_dest))))
3003     {
3004       if (vect_print_dump_info (REPORT_DETAILS))
3005         fprintf (vect_dump, "bit-precision shifts not supported.");
3006       return false;
3007     }
3008
3009   op0 = gimple_assign_rhs1 (stmt);
3010   if (!vect_is_simple_use_1 (op0, stmt, loop_vinfo, bb_vinfo,
3011                              &def_stmt, &def, &dt[0], &vectype))
3012     {
3013       if (vect_print_dump_info (REPORT_DETAILS))
3014         fprintf (vect_dump, "use not simple.");
3015       return false;
3016     }
3017   /* If op0 is an external or constant def use a vector type with
3018      the same size as the output vector type.  */
3019   if (!vectype)
3020     vectype = get_same_sized_vectype (TREE_TYPE (op0), vectype_out);
3021   if (vec_stmt)
3022     gcc_assert (vectype);
3023   if (!vectype)
3024     {
3025       if (vect_print_dump_info (REPORT_DETAILS))
3026         {
3027           fprintf (vect_dump, "no vectype for scalar type ");
3028           print_generic_expr (vect_dump, TREE_TYPE (op0), TDF_SLIM);
3029         }
3030
3031       return false;
3032     }
3033
3034   nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
3035   nunits_in = TYPE_VECTOR_SUBPARTS (vectype);
3036   if (nunits_out != nunits_in)
3037     return false;
3038
3039   op1 = gimple_assign_rhs2 (stmt);
3040   if (!vect_is_simple_use_1 (op1, stmt, loop_vinfo, bb_vinfo, &def_stmt,
3041                              &def, &dt[1], &op1_vectype))
3042     {
3043       if (vect_print_dump_info (REPORT_DETAILS))
3044         fprintf (vect_dump, "use not simple.");
3045       return false;
3046     }
3047
3048   if (loop_vinfo)
3049     vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
3050   else
3051     vf = 1;
3052
3053   /* Multiple types in SLP are handled by creating the appropriate number of
3054      vectorized stmts for each SLP node.  Hence, NCOPIES is always 1 in
3055      case of SLP.  */
3056   if (slp_node || PURE_SLP_STMT (stmt_info))
3057     ncopies = 1;
3058   else
3059     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_in;
3060
3061   gcc_assert (ncopies >= 1);
3062
3063   /* Determine whether the shift amount is a vector, or scalar.  If the
3064      shift/rotate amount is a vector, use the vector/vector shift optabs.  */
3065
3066   if (dt[1] == vect_internal_def && !slp_node)
3067     scalar_shift_arg = false;
3068   else if (dt[1] == vect_constant_def
3069            || dt[1] == vect_external_def
3070            || dt[1] == vect_internal_def)
3071     {
3072       /* In SLP, need to check whether the shift count is the same,
3073          in loops if it is a constant or invariant, it is always
3074          a scalar shift.  */
3075       if (slp_node)
3076         {
3077           VEC (gimple, heap) *stmts = SLP_TREE_SCALAR_STMTS (slp_node);
3078           gimple slpstmt;
3079
3080           FOR_EACH_VEC_ELT (gimple, stmts, k, slpstmt)
3081             if (!operand_equal_p (gimple_assign_rhs2 (slpstmt), op1, 0))
3082               scalar_shift_arg = false;
3083         }
3084     }
3085   else
3086     {
3087       if (vect_print_dump_info (REPORT_DETAILS))
3088         fprintf (vect_dump, "operand mode requires invariant argument.");
3089       return false;
3090     }
3091
3092   /* Vector shifted by vector.  */
3093   if (!scalar_shift_arg)
3094     {
3095       optab = optab_for_tree_code (code, vectype, optab_vector);
3096       if (vect_print_dump_info (REPORT_DETAILS))
3097         fprintf (vect_dump, "vector/vector shift/rotate found.");
3098       if (!op1_vectype)
3099         op1_vectype = get_same_sized_vectype (TREE_TYPE (op1), vectype_out);
3100       if (op1_vectype == NULL_TREE
3101           || TYPE_MODE (op1_vectype) != TYPE_MODE (vectype))
3102         {
3103           if (vect_print_dump_info (REPORT_DETAILS))
3104             fprintf (vect_dump, "unusable type for last operand in"
3105                                 " vector/vector shift/rotate.");
3106           return false;
3107         }
3108     }
3109   /* See if the machine has a vector shifted by scalar insn and if not
3110      then see if it has a vector shifted by vector insn.  */
3111   else
3112     {
3113       optab = optab_for_tree_code (code, vectype, optab_scalar);
3114       if (optab
3115           && optab_handler (optab, TYPE_MODE (vectype)) != CODE_FOR_nothing)
3116         {
3117           if (vect_print_dump_info (REPORT_DETAILS))
3118             fprintf (vect_dump, "vector/scalar shift/rotate found.");
3119         }
3120       else
3121         {
3122           optab = optab_for_tree_code (code, vectype, optab_vector);
3123           if (optab
3124                && (optab_handler (optab, TYPE_MODE (vectype))
3125                       != CODE_FOR_nothing))
3126             {
3127               scalar_shift_arg = false;
3128
3129               if (vect_print_dump_info (REPORT_DETAILS))
3130                 fprintf (vect_dump, "vector/vector shift/rotate found.");
3131
3132               /* Unlike the other binary operators, shifts/rotates have
3133                  the rhs being int, instead of the same type as the lhs,
3134                  so make sure the scalar is the right type if we are
3135                  dealing with vectors of long long/long/short/char.  */
3136               if (dt[1] == vect_constant_def)
3137                 op1 = fold_convert (TREE_TYPE (vectype), op1);
3138               else if (!useless_type_conversion_p (TREE_TYPE (vectype),
3139                                                    TREE_TYPE (op1)))
3140                 {
3141                   if (slp_node
3142                       && TYPE_MODE (TREE_TYPE (vectype))
3143                          != TYPE_MODE (TREE_TYPE (op1)))
3144                     {
3145                       if (vect_print_dump_info (REPORT_DETAILS))
3146                       fprintf (vect_dump, "unusable type for last operand in"
3147                                           " vector/vector shift/rotate.");
3148                         return false;
3149                     }
3150                   if (vec_stmt && !slp_node)
3151                     {
3152                       op1 = fold_convert (TREE_TYPE (vectype), op1);
3153                       op1 = vect_init_vector (stmt, op1,
3154                                               TREE_TYPE (vectype), NULL);
3155                     }
3156                 }
3157             }
3158         }
3159     }
3160
3161   /* Supportable by target?  */
3162   if (!optab)
3163     {
3164       if (vect_print_dump_info (REPORT_DETAILS))
3165         fprintf (vect_dump, "no optab.");
3166       return false;
3167     }
3168   vec_mode = TYPE_MODE (vectype);
3169   icode = (int) optab_handler (optab, vec_mode);
3170   if (icode == CODE_FOR_nothing)
3171     {
3172       if (vect_print_dump_info (REPORT_DETAILS))
3173         fprintf (vect_dump, "op not supported by target.");
3174       /* Check only during analysis.  */
3175       if (GET_MODE_SIZE (vec_mode) != UNITS_PER_WORD
3176           || (vf < vect_min_worthwhile_factor (code)
3177               && !vec_stmt))
3178         return false;
3179       if (vect_print_dump_info (REPORT_DETAILS))
3180         fprintf (vect_dump, "proceeding using word mode.");
3181     }
3182
3183   /* Worthwhile without SIMD support?  Check only during analysis.  */
3184   if (!VECTOR_MODE_P (TYPE_MODE (vectype))
3185       && vf < vect_min_worthwhile_factor (code)
3186       && !vec_stmt)
3187     {
3188       if (vect_print_dump_info (REPORT_DETAILS))
3189         fprintf (vect_dump, "not worthwhile without SIMD support.");
3190       return false;
3191     }
3192
3193   if (!vec_stmt) /* transformation not required.  */
3194     {
3195       STMT_VINFO_TYPE (stmt_info) = shift_vec_info_type;
3196       if (vect_print_dump_info (REPORT_DETAILS))
3197         fprintf (vect_dump, "=== vectorizable_shift ===");
3198       vect_model_simple_cost (stmt_info, ncopies, dt, NULL);
3199       return true;
3200     }
3201
3202   /** Transform.  **/
3203
3204   if (vect_print_dump_info (REPORT_DETAILS))
3205     fprintf (vect_dump, "transform binary/unary operation.");
3206
3207   /* Handle def.  */
3208   vec_dest = vect_create_destination_var (scalar_dest, vectype);
3209
3210   /* Allocate VECs for vector operands.  In case of SLP, vector operands are
3211      created in the previous stages of the recursion, so no allocation is
3212      needed, except for the case of shift with scalar shift argument.  In that
3213      case we store the scalar operand in VEC_OPRNDS1 for every vector stmt to
3214      be created to vectorize the SLP group, i.e., SLP_NODE->VEC_STMTS_SIZE.
3215      In case of loop-based vectorization we allocate VECs of size 1.  We
3216      allocate VEC_OPRNDS1 only in case of binary operation.  */
3217   if (!slp_node)
3218     {
3219       vec_oprnds0 = VEC_alloc (tree, heap, 1);
3220       vec_oprnds1 = VEC_alloc (tree, heap, 1);
3221     }
3222   else if (scalar_shift_arg)
3223     vec_oprnds1 = VEC_alloc (tree, heap, slp_node->vec_stmts_size);
3224
3225   prev_stmt_info = NULL;
3226   for (j = 0; j < ncopies; j++)
3227     {
3228       /* Handle uses.  */
3229       if (j == 0)
3230         {
3231           if (scalar_shift_arg)
3232             {
3233               /* Vector shl and shr insn patterns can be defined with scalar
3234                  operand 2 (shift operand).  In this case, use constant or loop
3235                  invariant op1 directly, without extending it to vector mode
3236                  first.  */
3237               optab_op2_mode = insn_data[icode].operand[2].mode;
3238               if (!VECTOR_MODE_P (optab_op2_mode))
3239                 {
3240                   if (vect_print_dump_info (REPORT_DETAILS))
3241                     fprintf (vect_dump, "operand 1 using scalar mode.");
3242                   vec_oprnd1 = op1;
3243                   VEC_quick_push (tree, vec_oprnds1, vec_oprnd1);
3244                   if (slp_node)
3245                     {
3246                       /* Store vec_oprnd1 for every vector stmt to be created
3247                          for SLP_NODE.  We check during the analysis that all
3248                          the shift arguments are the same.
3249                          TODO: Allow different constants for different vector
3250                          stmts generated for an SLP instance.  */
3251                       for (k = 0; k < slp_node->vec_stmts_size - 1; k++)
3252                         VEC_quick_push (tree, vec_oprnds1, vec_oprnd1);
3253                     }
3254                 }
3255             }
3256
3257           /* vec_oprnd1 is available if operand 1 should be of a scalar-type
3258              (a special case for certain kind of vector shifts); otherwise,
3259              operand 1 should be of a vector type (the usual case).  */
3260           if (vec_oprnd1)
3261             vect_get_vec_defs (op0, NULL_TREE, stmt, &vec_oprnds0, NULL,
3262                                slp_node, -1);
3263           else
3264             vect_get_vec_defs (op0, op1, stmt, &vec_oprnds0, &vec_oprnds1,
3265                                slp_node, -1);
3266         }
3267       else
3268         vect_get_vec_defs_for_stmt_copy (dt, &vec_oprnds0, &vec_oprnds1);
3269
3270       /* Arguments are ready.  Create the new vector stmt.  */
3271       FOR_EACH_VEC_ELT (tree, vec_oprnds0, i, vop0)
3272         {
3273           vop1 = VEC_index (tree, vec_oprnds1, i);
3274           new_stmt = gimple_build_assign_with_ops (code, vec_dest, vop0, vop1);
3275           new_temp = make_ssa_name (vec_dest, new_stmt);
3276           gimple_assign_set_lhs (new_stmt, new_temp);
3277           vect_finish_stmt_generation (stmt, new_stmt, gsi);
3278           if (slp_node)
3279             VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
3280         }
3281
3282       if (slp_node)
3283         continue;
3284
3285       if (j == 0)
3286         STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
3287       else
3288         STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
3289       prev_stmt_info = vinfo_for_stmt (new_stmt);
3290     }
3291
3292   VEC_free (tree, heap, vec_oprnds0);
3293   VEC_free (tree, heap, vec_oprnds1);
3294
3295   return true;
3296 }
3297
3298
3299 /* Function vectorizable_operation.
3300
3301    Check if STMT performs a binary, unary or ternary operation that can
3302    be vectorized.
3303    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3304    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3305    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
3306
3307 static bool
3308 vectorizable_operation (gimple stmt, gimple_stmt_iterator *gsi,
3309                         gimple *vec_stmt, slp_tree slp_node)
3310 {
3311   tree vec_dest;
3312   tree scalar_dest;
3313   tree op0, op1 = NULL_TREE, op2 = NULL_TREE;
3314   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3315   tree vectype;
3316   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3317   enum tree_code code;
3318   enum machine_mode vec_mode;
3319   tree new_temp;
3320   int op_type;
3321   optab optab;
3322   int icode;
3323   tree def;
3324   gimple def_stmt;
3325   enum vect_def_type dt[3]
3326     = {vect_unknown_def_type, vect_unknown_def_type, vect_unknown_def_type};
3327   gimple new_stmt = NULL;
3328   stmt_vec_info prev_stmt_info;
3329   int nunits_in;
3330   int nunits_out;
3331   tree vectype_out;
3332   int ncopies;
3333   int j, i;
3334   VEC(tree,heap) *vec_oprnds0 = NULL, *vec_oprnds1 = NULL, *vec_oprnds2 = NULL;
3335   tree vop0, vop1, vop2;
3336   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
3337   int vf;
3338
3339   if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
3340     return false;
3341
3342   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
3343     return false;
3344
3345   /* Is STMT a vectorizable binary/unary operation?   */
3346   if (!is_gimple_assign (stmt))
3347     return false;
3348
3349   if (TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
3350     return false;
3351
3352   code = gimple_assign_rhs_code (stmt);
3353
3354   /* For pointer addition, we should use the normal plus for
3355      the vector addition.  */
3356   if (code == POINTER_PLUS_EXPR)
3357     code = PLUS_EXPR;
3358
3359   /* Support only unary or binary operations.  */
3360   op_type = TREE_CODE_LENGTH (code);
3361   if (op_type != unary_op && op_type != binary_op && op_type != ternary_op)
3362     {
3363       if (vect_print_dump_info (REPORT_DETAILS))
3364         fprintf (vect_dump, "num. args = %d (not unary/binary/ternary op).",
3365                  op_type);
3366       return false;
3367     }
3368
3369   scalar_dest = gimple_assign_lhs (stmt);
3370   vectype_out = STMT_VINFO_VECTYPE (stmt_info);
3371
3372   /* Most operations cannot handle bit-precision types without extra
3373      truncations.  */
3374   if ((TYPE_PRECISION (TREE_TYPE (scalar_dest))
3375        != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (scalar_dest))))
3376       /* Exception are bitwise binary operations.  */
3377       && code != BIT_IOR_EXPR
3378       && code != BIT_XOR_EXPR
3379       && code != BIT_AND_EXPR)
3380     {
3381       if (vect_print_dump_info (REPORT_DETAILS))
3382         fprintf (vect_dump, "bit-precision arithmetic not supported.");
3383       return false;
3384     }
3385
3386   op0 = gimple_assign_rhs1 (stmt);
3387   if (!vect_is_simple_use_1 (op0, stmt, loop_vinfo, bb_vinfo,
3388                              &def_stmt, &def, &dt[0], &vectype))
3389     {
3390       if (vect_print_dump_info (REPORT_DETAILS))
3391         fprintf (vect_dump, "use not simple.");
3392       return false;
3393     }
3394   /* If op0 is an external or constant def use a vector type with
3395      the same size as the output vector type.  */
3396   if (!vectype)
3397     vectype = get_same_sized_vectype (TREE_TYPE (op0), vectype_out);
3398   if (vec_stmt)
3399     gcc_assert (vectype);
3400   if (!vectype)
3401     {
3402       if (vect_print_dump_info (REPORT_DETAILS))
3403         {
3404           fprintf (vect_dump, "no vectype for scalar type ");
3405           print_generic_expr (vect_dump, TREE_TYPE (op0), TDF_SLIM);
3406         }
3407
3408       return false;
3409     }
3410
3411   nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
3412   nunits_in = TYPE_VECTOR_SUBPARTS (vectype);
3413   if (nunits_out != nunits_in)
3414     return false;
3415
3416   if (op_type == binary_op || op_type == ternary_op)
3417     {
3418       op1 = gimple_assign_rhs2 (stmt);
3419       if (!vect_is_simple_use (op1, stmt, loop_vinfo, bb_vinfo, &def_stmt,
3420                                &def, &dt[1]))
3421         {
3422           if (vect_print_dump_info (REPORT_DETAILS))
3423             fprintf (vect_dump, "use not simple.");
3424           return false;
3425         }
3426     }
3427   if (op_type == ternary_op)
3428     {
3429       op2 = gimple_assign_rhs3 (stmt);
3430       if (!vect_is_simple_use (op2, stmt, loop_vinfo, bb_vinfo, &def_stmt,
3431                                &def, &dt[2]))
3432         {
3433           if (vect_print_dump_info (REPORT_DETAILS))
3434             fprintf (vect_dump, "use not simple.");
3435           return false;
3436         }
3437     }
3438
3439   if (loop_vinfo)
3440     vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
3441   else
3442     vf = 1;
3443
3444   /* Multiple types in SLP are handled by creating the appropriate number of
3445      vectorized stmts for each SLP node.  Hence, NCOPIES is always 1 in
3446      case of SLP.  */
3447   if (slp_node || PURE_SLP_STMT (stmt_info))
3448     ncopies = 1;
3449   else
3450     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_in;
3451
3452   gcc_assert (ncopies >= 1);
3453
3454   /* Shifts are handled in vectorizable_shift ().  */
3455   if (code == LSHIFT_EXPR || code == RSHIFT_EXPR || code == LROTATE_EXPR
3456       || code == RROTATE_EXPR)
3457    return false;
3458
3459   optab = optab_for_tree_code (code, vectype, optab_default);
3460
3461   /* Supportable by target?  */
3462   if (!optab)
3463     {
3464       if (vect_print_dump_info (REPORT_DETAILS))
3465         fprintf (vect_dump, "no optab.");
3466       return false;
3467     }
3468   vec_mode = TYPE_MODE (vectype);
3469   icode = (int) optab_handler (optab, vec_mode);
3470   if (icode == CODE_FOR_nothing)
3471     {
3472       if (vect_print_dump_info (REPORT_DETAILS))
3473         fprintf (vect_dump, "op not supported by target.");
3474       /* Check only during analysis.  */
3475       if (GET_MODE_SIZE (vec_mode) != UNITS_PER_WORD
3476           || (vf < vect_min_worthwhile_factor (code)
3477               && !vec_stmt))
3478         return false;
3479       if (vect_print_dump_info (REPORT_DETAILS))
3480         fprintf (vect_dump, "proceeding using word mode.");
3481     }
3482
3483   /* Worthwhile without SIMD support?  Check only during analysis.  */
3484   if (!VECTOR_MODE_P (TYPE_MODE (vectype))
3485       && vf < vect_min_worthwhile_factor (code)
3486       && !vec_stmt)
3487     {
3488       if (vect_print_dump_info (REPORT_DETAILS))
3489         fprintf (vect_dump, "not worthwhile without SIMD support.");
3490       return false;
3491     }
3492
3493   if (!vec_stmt) /* transformation not required.  */
3494     {
3495       STMT_VINFO_TYPE (stmt_info) = op_vec_info_type;
3496       if (vect_print_dump_info (REPORT_DETAILS))
3497         fprintf (vect_dump, "=== vectorizable_operation ===");
3498       vect_model_simple_cost (stmt_info, ncopies, dt, NULL);
3499       return true;
3500     }
3501
3502   /** Transform.  **/
3503
3504   if (vect_print_dump_info (REPORT_DETAILS))
3505     fprintf (vect_dump, "transform binary/unary operation.");
3506
3507   /* Handle def.  */
3508   vec_dest = vect_create_destination_var (scalar_dest, vectype);
3509
3510   /* Allocate VECs for vector operands.  In case of SLP, vector operands are
3511      created in the previous stages of the recursion, so no allocation is
3512      needed, except for the case of shift with scalar shift argument.  In that
3513      case we store the scalar operand in VEC_OPRNDS1 for every vector stmt to
3514      be created to vectorize the SLP group, i.e., SLP_NODE->VEC_STMTS_SIZE.
3515      In case of loop-based vectorization we allocate VECs of size 1.  We
3516      allocate VEC_OPRNDS1 only in case of binary operation.  */
3517   if (!slp_node)
3518     {
3519       vec_oprnds0 = VEC_alloc (tree, heap, 1);
3520       if (op_type == binary_op || op_type == ternary_op)
3521         vec_oprnds1 = VEC_alloc (tree, heap, 1);
3522       if (op_type == ternary_op)
3523         vec_oprnds2 = VEC_alloc (tree, heap, 1);
3524     }
3525
3526   /* In case the vectorization factor (VF) is bigger than the number
3527      of elements that we can fit in a vectype (nunits), we have to generate
3528      more than one vector stmt - i.e - we need to "unroll" the
3529      vector stmt by a factor VF/nunits.  In doing so, we record a pointer
3530      from one copy of the vector stmt to the next, in the field
3531      STMT_VINFO_RELATED_STMT.  This is necessary in order to allow following
3532      stages to find the correct vector defs to be used when vectorizing
3533      stmts that use the defs of the current stmt.  The example below
3534      illustrates the vectorization process when VF=16 and nunits=4 (i.e.,
3535      we need to create 4 vectorized stmts):
3536
3537      before vectorization:
3538                                 RELATED_STMT    VEC_STMT
3539         S1:     x = memref      -               -
3540         S2:     z = x + 1       -               -
3541
3542      step 1: vectorize stmt S1 (done in vectorizable_load. See more details
3543              there):
3544                                 RELATED_STMT    VEC_STMT
3545         VS1_0:  vx0 = memref0   VS1_1           -
3546         VS1_1:  vx1 = memref1   VS1_2           -
3547         VS1_2:  vx2 = memref2   VS1_3           -
3548         VS1_3:  vx3 = memref3   -               -
3549         S1:     x = load        -               VS1_0
3550         S2:     z = x + 1       -               -
3551
3552      step2: vectorize stmt S2 (done here):
3553         To vectorize stmt S2 we first need to find the relevant vector
3554         def for the first operand 'x'.  This is, as usual, obtained from
3555         the vector stmt recorded in the STMT_VINFO_VEC_STMT of the stmt
3556         that defines 'x' (S1).  This way we find the stmt VS1_0, and the
3557         relevant vector def 'vx0'.  Having found 'vx0' we can generate
3558         the vector stmt VS2_0, and as usual, record it in the
3559         STMT_VINFO_VEC_STMT of stmt S2.
3560         When creating the second copy (VS2_1), we obtain the relevant vector
3561         def from the vector stmt recorded in the STMT_VINFO_RELATED_STMT of
3562         stmt VS1_0.  This way we find the stmt VS1_1 and the relevant
3563         vector def 'vx1'.  Using 'vx1' we create stmt VS2_1 and record a
3564         pointer to it in the STMT_VINFO_RELATED_STMT of the vector stmt VS2_0.
3565         Similarly when creating stmts VS2_2 and VS2_3.  This is the resulting
3566         chain of stmts and pointers:
3567                                 RELATED_STMT    VEC_STMT
3568         VS1_0:  vx0 = memref0   VS1_1           -
3569         VS1_1:  vx1 = memref1   VS1_2           -
3570         VS1_2:  vx2 = memref2   VS1_3           -
3571         VS1_3:  vx3 = memref3   -               -
3572         S1:     x = load        -               VS1_0
3573         VS2_0:  vz0 = vx0 + v1  VS2_1           -
3574         VS2_1:  vz1 = vx1 + v1  VS2_2           -
3575         VS2_2:  vz2 = vx2 + v1  VS2_3           -
3576         VS2_3:  vz3 = vx3 + v1  -               -
3577         S2:     z = x + 1       -               VS2_0  */
3578
3579   prev_stmt_info = NULL;
3580   for (j = 0; j < ncopies; j++)
3581     {
3582       /* Handle uses.  */
3583       if (j == 0)
3584         {
3585           if (op_type == binary_op || op_type == ternary_op)
3586             vect_get_vec_defs (op0, op1, stmt, &vec_oprnds0, &vec_oprnds1,
3587                                slp_node, -1);
3588           else
3589             vect_get_vec_defs (op0, NULL_TREE, stmt, &vec_oprnds0, NULL,
3590                                slp_node, -1);
3591           if (op_type == ternary_op)
3592             {
3593               vec_oprnds2 = VEC_alloc (tree, heap, 1);
3594               VEC_quick_push (tree, vec_oprnds2,
3595                               vect_get_vec_def_for_operand (op2, stmt, NULL));
3596             }
3597         }
3598       else
3599         {
3600           vect_get_vec_defs_for_stmt_copy (dt, &vec_oprnds0, &vec_oprnds1);
3601           if (op_type == ternary_op)
3602             {
3603               tree vec_oprnd = VEC_pop (tree, vec_oprnds2);
3604               VEC_quick_push (tree, vec_oprnds2,
3605                               vect_get_vec_def_for_stmt_copy (dt[2],
3606                                                               vec_oprnd));
3607             }
3608         }
3609
3610       /* Arguments are ready.  Create the new vector stmt.  */
3611       FOR_EACH_VEC_ELT (tree, vec_oprnds0, i, vop0)
3612         {
3613           vop1 = ((op_type == binary_op || op_type == ternary_op)
3614                   ? VEC_index (tree, vec_oprnds1, i) : NULL_TREE);
3615           vop2 = ((op_type == ternary_op)
3616                   ? VEC_index (tree, vec_oprnds2, i) : NULL_TREE);
3617           new_stmt = gimple_build_assign_with_ops3 (code, vec_dest,
3618                                                     vop0, vop1, vop2);
3619           new_temp = make_ssa_name (vec_dest, new_stmt);
3620           gimple_assign_set_lhs (new_stmt, new_temp);
3621           vect_finish_stmt_generation (stmt, new_stmt, gsi);
3622           if (slp_node)
3623             VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
3624         }
3625
3626       if (slp_node)
3627         continue;
3628
3629       if (j == 0)
3630         STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
3631       else
3632         STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
3633       prev_stmt_info = vinfo_for_stmt (new_stmt);
3634     }
3635
3636   VEC_free (tree, heap, vec_oprnds0);
3637   if (vec_oprnds1)
3638     VEC_free (tree, heap, vec_oprnds1);
3639   if (vec_oprnds2)
3640     VEC_free (tree, heap, vec_oprnds2);
3641
3642   return true;
3643 }
3644
3645
3646 /* Function vectorizable_store.
3647
3648    Check if STMT defines a non scalar data-ref (array/pointer/structure) that
3649    can be vectorized.
3650    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3651    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3652    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
3653
3654 static bool
3655 vectorizable_store (gimple stmt, gimple_stmt_iterator *gsi, gimple *vec_stmt,
3656                     slp_tree slp_node)
3657 {
3658   tree scalar_dest;
3659   tree data_ref;
3660   tree op;
3661   tree vec_oprnd = NULL_TREE;
3662   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3663   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info), *first_dr = NULL;
3664   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
3665   tree elem_type;
3666   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3667   struct loop *loop = NULL;
3668   enum machine_mode vec_mode;
3669   tree dummy;
3670   enum dr_alignment_support alignment_support_scheme;
3671   tree def;
3672   gimple def_stmt;
3673   enum vect_def_type dt;
3674   stmt_vec_info prev_stmt_info = NULL;
3675   tree dataref_ptr = NULL_TREE;
3676   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
3677   int ncopies;
3678   int j;
3679   gimple next_stmt, first_stmt = NULL;
3680   bool strided_store = false;
3681   bool store_lanes_p = false;
3682   unsigned int group_size, i;
3683   VEC(tree,heap) *dr_chain = NULL, *oprnds = NULL, *result_chain = NULL;
3684   bool inv_p;
3685   VEC(tree,heap) *vec_oprnds = NULL;
3686   bool slp = (slp_node != NULL);
3687   unsigned int vec_num;
3688   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
3689   tree aggr_type;
3690
3691   if (loop_vinfo)
3692     loop = LOOP_VINFO_LOOP (loop_vinfo);
3693
3694   /* Multiple types in SLP are handled by creating the appropriate number of
3695      vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
3696      case of SLP.  */
3697   if (slp || PURE_SLP_STMT (stmt_info))
3698     ncopies = 1;
3699   else
3700     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
3701
3702   gcc_assert (ncopies >= 1);
3703
3704   /* FORNOW. This restriction should be relaxed.  */
3705   if (loop && nested_in_vect_loop_p (loop, stmt) && ncopies > 1)
3706     {
3707       if (vect_print_dump_info (REPORT_DETAILS))
3708         fprintf (vect_dump, "multiple types in nested loop.");
3709       return false;
3710     }
3711
3712   if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
3713     return false;
3714
3715   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
3716     return false;
3717
3718   /* Is vectorizable store? */
3719
3720   if (!is_gimple_assign (stmt))
3721     return false;
3722
3723   scalar_dest = gimple_assign_lhs (stmt);
3724   if (TREE_CODE (scalar_dest) == VIEW_CONVERT_EXPR
3725       && is_pattern_stmt_p (stmt_info))
3726     scalar_dest = TREE_OPERAND (scalar_dest, 0);
3727   if (TREE_CODE (scalar_dest) != ARRAY_REF
3728       && TREE_CODE (scalar_dest) != INDIRECT_REF
3729       && TREE_CODE (scalar_dest) != COMPONENT_REF
3730       && TREE_CODE (scalar_dest) != IMAGPART_EXPR
3731       && TREE_CODE (scalar_dest) != REALPART_EXPR
3732       && TREE_CODE (scalar_dest) != MEM_REF)
3733     return false;
3734
3735   gcc_assert (gimple_assign_single_p (stmt));
3736   op = gimple_assign_rhs1 (stmt);
3737   if (!vect_is_simple_use (op, stmt, loop_vinfo, bb_vinfo, &def_stmt,
3738                            &def, &dt))
3739     {
3740       if (vect_print_dump_info (REPORT_DETAILS))
3741         fprintf (vect_dump, "use not simple.");
3742       return false;
3743     }
3744
3745   elem_type = TREE_TYPE (vectype);
3746   vec_mode = TYPE_MODE (vectype);
3747
3748   /* FORNOW. In some cases can vectorize even if data-type not supported
3749      (e.g. - array initialization with 0).  */
3750   if (optab_handler (mov_optab, vec_mode) == CODE_FOR_nothing)
3751     return false;
3752
3753   if (!STMT_VINFO_DATA_REF (stmt_info))
3754     return false;
3755
3756   if (tree_int_cst_compare (loop && nested_in_vect_loop_p (loop, stmt)
3757                             ? STMT_VINFO_DR_STEP (stmt_info) : DR_STEP (dr),
3758                             size_zero_node) < 0)
3759     {
3760       if (vect_print_dump_info (REPORT_DETAILS))
3761         fprintf (vect_dump, "negative step for store.");
3762       return false;
3763     }
3764
3765   if (STMT_VINFO_STRIDED_ACCESS (stmt_info))
3766     {
3767       strided_store = true;
3768       first_stmt = GROUP_FIRST_ELEMENT (stmt_info);
3769       if (!slp && !PURE_SLP_STMT (stmt_info))
3770         {
3771           group_size = GROUP_SIZE (vinfo_for_stmt (first_stmt));
3772           if (vect_store_lanes_supported (vectype, group_size))
3773             store_lanes_p = true;
3774           else if (!vect_strided_store_supported (vectype, group_size))
3775             return false;
3776         }
3777
3778       if (first_stmt == stmt)
3779         {
3780           /* STMT is the leader of the group. Check the operands of all the
3781              stmts of the group.  */
3782           next_stmt = GROUP_NEXT_ELEMENT (stmt_info);
3783           while (next_stmt)
3784             {
3785               gcc_assert (gimple_assign_single_p (next_stmt));
3786               op = gimple_assign_rhs1 (next_stmt);
3787               if (!vect_is_simple_use (op, next_stmt, loop_vinfo, bb_vinfo,
3788                                        &def_stmt, &def, &dt))
3789                 {
3790                   if (vect_print_dump_info (REPORT_DETAILS))
3791                     fprintf (vect_dump, "use not simple.");
3792                   return false;
3793                 }
3794               next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
3795             }
3796         }
3797     }
3798
3799   if (!vec_stmt) /* transformation not required.  */
3800     {
3801       STMT_VINFO_TYPE (stmt_info) = store_vec_info_type;
3802       vect_model_store_cost (stmt_info, ncopies, store_lanes_p, dt, NULL);
3803       return true;
3804     }
3805
3806   /** Transform.  **/
3807
3808   if (strided_store)
3809     {
3810       first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt));
3811       group_size = GROUP_SIZE (vinfo_for_stmt (first_stmt));
3812
3813       GROUP_STORE_COUNT (vinfo_for_stmt (first_stmt))++;
3814
3815       /* FORNOW */
3816       gcc_assert (!loop || !nested_in_vect_loop_p (loop, stmt));
3817
3818       /* We vectorize all the stmts of the interleaving group when we
3819          reach the last stmt in the group.  */
3820       if (GROUP_STORE_COUNT (vinfo_for_stmt (first_stmt))
3821           < GROUP_SIZE (vinfo_for_stmt (first_stmt))
3822           && !slp)
3823         {
3824           *vec_stmt = NULL;
3825           return true;
3826         }
3827
3828       if (slp)
3829         {
3830           strided_store = false;
3831           /* VEC_NUM is the number of vect stmts to be created for this 
3832              group.  */
3833           vec_num = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
3834           first_stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (slp_node), 0); 
3835           first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt));
3836           op = gimple_assign_rhs1 (first_stmt);
3837         } 
3838       else
3839         /* VEC_NUM is the number of vect stmts to be created for this 
3840            group.  */
3841         vec_num = group_size;
3842     }
3843   else
3844     {
3845       first_stmt = stmt;
3846       first_dr = dr;
3847       group_size = vec_num = 1;
3848     }
3849
3850   if (vect_print_dump_info (REPORT_DETAILS))
3851     fprintf (vect_dump, "transform store. ncopies = %d",ncopies);
3852
3853   dr_chain = VEC_alloc (tree, heap, group_size);
3854   oprnds = VEC_alloc (tree, heap, group_size);
3855
3856   alignment_support_scheme = vect_supportable_dr_alignment (first_dr, false);
3857   gcc_assert (alignment_support_scheme);
3858   /* Targets with store-lane instructions must not require explicit
3859      realignment.  */
3860   gcc_assert (!store_lanes_p
3861               || alignment_support_scheme == dr_aligned
3862               || alignment_support_scheme == dr_unaligned_supported);
3863
3864   if (store_lanes_p)
3865     aggr_type = build_array_type_nelts (elem_type, vec_num * nunits);
3866   else
3867     aggr_type = vectype;
3868
3869   /* In case the vectorization factor (VF) is bigger than the number
3870      of elements that we can fit in a vectype (nunits), we have to generate
3871      more than one vector stmt - i.e - we need to "unroll" the
3872      vector stmt by a factor VF/nunits.  For more details see documentation in
3873      vect_get_vec_def_for_copy_stmt.  */
3874
3875   /* In case of interleaving (non-unit strided access):
3876
3877         S1:  &base + 2 = x2
3878         S2:  &base = x0
3879         S3:  &base + 1 = x1
3880         S4:  &base + 3 = x3
3881
3882      We create vectorized stores starting from base address (the access of the
3883      first stmt in the chain (S2 in the above example), when the last store stmt
3884      of the chain (S4) is reached:
3885
3886         VS1: &base = vx2
3887         VS2: &base + vec_size*1 = vx0
3888         VS3: &base + vec_size*2 = vx1
3889         VS4: &base + vec_size*3 = vx3
3890
3891      Then permutation statements are generated:
3892
3893         VS5: vx5 = VEC_PERM_EXPR < vx0, vx3, {0, 8, 1, 9, 2, 10, 3, 11} >
3894         VS6: vx6 = VEC_PERM_EXPR < vx0, vx3, {4, 12, 5, 13, 6, 14, 7, 15} >
3895         ...
3896
3897      And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
3898      (the order of the data-refs in the output of vect_permute_store_chain
3899      corresponds to the order of scalar stmts in the interleaving chain - see
3900      the documentation of vect_permute_store_chain()).
3901
3902      In case of both multiple types and interleaving, above vector stores and
3903      permutation stmts are created for every copy.  The result vector stmts are
3904      put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
3905      STMT_VINFO_RELATED_STMT for the next copies.
3906   */
3907
3908   prev_stmt_info = NULL;
3909   for (j = 0; j < ncopies; j++)
3910     {
3911       gimple new_stmt;
3912       gimple ptr_incr;
3913
3914       if (j == 0)
3915         {
3916           if (slp)
3917             {
3918               /* Get vectorized arguments for SLP_NODE.  */
3919               vect_get_vec_defs (op, NULL_TREE, stmt, &vec_oprnds,
3920                                  NULL, slp_node, -1);
3921
3922               vec_oprnd = VEC_index (tree, vec_oprnds, 0);
3923             }
3924           else
3925             {
3926               /* For interleaved stores we collect vectorized defs for all the
3927                  stores in the group in DR_CHAIN and OPRNDS. DR_CHAIN is then
3928                  used as an input to vect_permute_store_chain(), and OPRNDS as
3929                  an input to vect_get_vec_def_for_stmt_copy() for the next copy.
3930
3931                  If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
3932                  OPRNDS are of size 1.  */