OSDN Git Service

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