OSDN Git Service

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