OSDN Git Service

b91f8d1a55653e76b24d01d0b958b0d29736879c
[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   integral_type = INTEGRAL_TYPE_P (rhs_type) ? vectype_in : vectype_out;
1623
1624   if (modifier == NARROW)
1625     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_out;
1626   else
1627     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_in;
1628
1629   /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
1630      this, so we can safely override NCOPIES with 1 here.  */
1631   if (slp_node)
1632     ncopies = 1;
1633
1634   /* Sanity check: make sure that at least one copy of the vectorized stmt
1635      needs to be generated.  */
1636   gcc_assert (ncopies >= 1);
1637
1638   /* Supportable by target?  */
1639   if ((modifier == NONE
1640        && !targetm.vectorize.builtin_conversion (code, vectype_out, vectype_in))
1641       || (modifier == WIDEN
1642           && !supportable_widening_operation (code, stmt,
1643                                               vectype_out, vectype_in,
1644                                               &decl1, &decl2,
1645                                               &code1, &code2,
1646                                               &dummy_int, &dummy))
1647       || (modifier == NARROW
1648           && !supportable_narrowing_operation (code, vectype_out, vectype_in,
1649                                                &code1, &dummy_int, &dummy)))
1650     {
1651       if (vect_print_dump_info (REPORT_DETAILS))
1652         fprintf (vect_dump, "conversion not supported by target.");
1653       return false;
1654     }
1655
1656   if (modifier != NONE)
1657     {
1658       /* FORNOW: SLP not supported.  */
1659       if (STMT_SLP_TYPE (stmt_info))
1660         return false;
1661     }
1662
1663   if (!vec_stmt)                /* transformation not required.  */
1664     {
1665       STMT_VINFO_TYPE (stmt_info) = type_conversion_vec_info_type;
1666       return true;
1667     }
1668
1669   /** Transform.  **/
1670   if (vect_print_dump_info (REPORT_DETAILS))
1671     fprintf (vect_dump, "transform conversion.");
1672
1673   /* Handle def.  */
1674   vec_dest = vect_create_destination_var (scalar_dest, vectype_out);
1675
1676   if (modifier == NONE && !slp_node)
1677     vec_oprnds0 = VEC_alloc (tree, heap, 1);
1678
1679   prev_stmt_info = NULL;
1680   switch (modifier)
1681     {
1682     case NONE:
1683       for (j = 0; j < ncopies; j++)
1684         {
1685           if (j == 0)
1686             vect_get_vec_defs (op0, NULL, stmt, &vec_oprnds0, NULL, slp_node);
1687           else
1688             vect_get_vec_defs_for_stmt_copy (dt, &vec_oprnds0, NULL);
1689
1690           builtin_decl =
1691             targetm.vectorize.builtin_conversion (code,
1692                                                   vectype_out, vectype_in);
1693           for (i = 0; VEC_iterate (tree, vec_oprnds0, i, vop0); i++)
1694             {
1695               /* Arguments are ready. create the new vector stmt.  */
1696               new_stmt = gimple_build_call (builtin_decl, 1, vop0);
1697               new_temp = make_ssa_name (vec_dest, new_stmt);
1698               gimple_call_set_lhs (new_stmt, new_temp);
1699               vect_finish_stmt_generation (stmt, new_stmt, gsi);
1700               if (slp_node)
1701                 VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
1702             }
1703
1704           if (j == 0)
1705             STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
1706           else
1707             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
1708           prev_stmt_info = vinfo_for_stmt (new_stmt);
1709         }
1710       break;
1711
1712     case WIDEN:
1713       /* In case the vectorization factor (VF) is bigger than the number
1714          of elements that we can fit in a vectype (nunits), we have to
1715          generate more than one vector stmt - i.e - we need to "unroll"
1716          the vector stmt by a factor VF/nunits.  */
1717       for (j = 0; j < ncopies; j++)
1718         {
1719           if (j == 0)
1720             vec_oprnd0 = vect_get_vec_def_for_operand (op0, stmt, NULL);
1721           else
1722             vec_oprnd0 = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd0);
1723
1724           /* Generate first half of the widened result:  */
1725           new_stmt
1726             = vect_gen_widened_results_half (code1, decl1,
1727                                              vec_oprnd0, vec_oprnd1,
1728                                              unary_op, vec_dest, gsi, stmt);
1729           if (j == 0)
1730             STMT_VINFO_VEC_STMT (stmt_info) = new_stmt;
1731           else
1732             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
1733           prev_stmt_info = vinfo_for_stmt (new_stmt);
1734
1735           /* Generate second half of the widened result:  */
1736           new_stmt
1737             = vect_gen_widened_results_half (code2, decl2,
1738                                              vec_oprnd0, vec_oprnd1,
1739                                              unary_op, vec_dest, gsi, stmt);
1740           STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
1741           prev_stmt_info = vinfo_for_stmt (new_stmt);
1742         }
1743       break;
1744
1745     case NARROW:
1746       /* In case the vectorization factor (VF) is bigger than the number
1747          of elements that we can fit in a vectype (nunits), we have to
1748          generate more than one vector stmt - i.e - we need to "unroll"
1749          the vector stmt by a factor VF/nunits.  */
1750       for (j = 0; j < ncopies; j++)
1751         {
1752           /* Handle uses.  */
1753           if (j == 0)
1754             {
1755               vec_oprnd0 = vect_get_vec_def_for_operand (op0, stmt, NULL);
1756               vec_oprnd1 = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd0);
1757             }
1758           else
1759             {
1760               vec_oprnd0 = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd1);
1761               vec_oprnd1 = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd0);
1762             }
1763
1764           /* Arguments are ready. Create the new vector stmt.  */
1765           new_stmt = gimple_build_assign_with_ops (code1, vec_dest, vec_oprnd0,
1766                                                    vec_oprnd1);
1767           new_temp = make_ssa_name (vec_dest, new_stmt);
1768           gimple_assign_set_lhs (new_stmt, new_temp);
1769           vect_finish_stmt_generation (stmt, new_stmt, gsi);
1770
1771           if (j == 0)
1772             STMT_VINFO_VEC_STMT (stmt_info) = new_stmt;
1773           else
1774             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
1775
1776           prev_stmt_info = vinfo_for_stmt (new_stmt);
1777         }
1778
1779       *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
1780     }
1781
1782   if (vec_oprnds0)
1783     VEC_free (tree, heap, vec_oprnds0);
1784
1785   return true;
1786 }
1787 /* Function vectorizable_assignment.
1788
1789    Check if STMT performs an assignment (copy) that can be vectorized.
1790    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1791    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1792    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
1793
1794 static bool
1795 vectorizable_assignment (gimple stmt, gimple_stmt_iterator *gsi,
1796                          gimple *vec_stmt, slp_tree slp_node)
1797 {
1798   tree vec_dest;
1799   tree scalar_dest;
1800   tree op;
1801   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1802   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1803   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1804   tree new_temp;
1805   tree def;
1806   gimple def_stmt;
1807   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
1808   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
1809   int ncopies;
1810   int i, j;
1811   VEC(tree,heap) *vec_oprnds = NULL;
1812   tree vop;
1813   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
1814   gimple new_stmt = NULL;
1815   stmt_vec_info prev_stmt_info = NULL;
1816
1817   /* Multiple types in SLP are handled by creating the appropriate number of
1818      vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
1819      case of SLP.  */
1820   if (slp_node)
1821     ncopies = 1;
1822   else
1823     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
1824
1825   gcc_assert (ncopies >= 1);
1826
1827   if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
1828     return false;
1829
1830   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
1831     return false;
1832
1833   /* Is vectorizable assignment?  */
1834   if (!is_gimple_assign (stmt))
1835     return false;
1836
1837   scalar_dest = gimple_assign_lhs (stmt);
1838   if (TREE_CODE (scalar_dest) != SSA_NAME)
1839     return false;
1840
1841   if (gimple_assign_single_p (stmt)
1842       || gimple_assign_rhs_code (stmt) == PAREN_EXPR)
1843     op = gimple_assign_rhs1 (stmt);
1844   else
1845     return false;
1846
1847   if (!vect_is_simple_use (op, loop_vinfo, bb_vinfo, &def_stmt, &def, &dt[0]))
1848     {
1849       if (vect_print_dump_info (REPORT_DETAILS))
1850         fprintf (vect_dump, "use not simple.");
1851       return false;
1852     }
1853
1854   if (!vec_stmt) /* transformation not required.  */
1855     {
1856       STMT_VINFO_TYPE (stmt_info) = assignment_vec_info_type;
1857       if (vect_print_dump_info (REPORT_DETAILS))
1858         fprintf (vect_dump, "=== vectorizable_assignment ===");
1859       vect_model_simple_cost (stmt_info, ncopies, dt, NULL);
1860       return true;
1861     }
1862
1863   /** Transform.  **/
1864   if (vect_print_dump_info (REPORT_DETAILS))
1865     fprintf (vect_dump, "transform assignment.");
1866
1867   /* Handle def.  */
1868   vec_dest = vect_create_destination_var (scalar_dest, vectype);
1869
1870   /* Handle use.  */
1871   for (j = 0; j < ncopies; j++)
1872     {
1873       /* Handle uses.  */
1874       if (j == 0)
1875         vect_get_vec_defs (op, NULL, stmt, &vec_oprnds, NULL, slp_node);
1876       else
1877         vect_get_vec_defs_for_stmt_copy (dt, &vec_oprnds, NULL);
1878
1879       /* Arguments are ready. create the new vector stmt.  */
1880       for (i = 0; VEC_iterate (tree, vec_oprnds, i, vop); i++)
1881        {
1882          new_stmt = gimple_build_assign (vec_dest, vop);
1883          new_temp = make_ssa_name (vec_dest, new_stmt);
1884          gimple_assign_set_lhs (new_stmt, new_temp);
1885          vect_finish_stmt_generation (stmt, new_stmt, gsi);
1886          if (slp_node)
1887            VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
1888        }
1889
1890       if (slp_node)
1891         continue;
1892
1893       if (j == 0)
1894         STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
1895       else
1896         STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
1897
1898       prev_stmt_info = vinfo_for_stmt (new_stmt);
1899     }
1900
1901   VEC_free (tree, heap, vec_oprnds);
1902   return true;
1903 }
1904
1905 /* Function vectorizable_operation.
1906
1907    Check if STMT performs a binary or unary operation that can be vectorized.
1908    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1909    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1910    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
1911
1912 static bool
1913 vectorizable_operation (gimple stmt, gimple_stmt_iterator *gsi,
1914                         gimple *vec_stmt, slp_tree slp_node)
1915 {
1916   tree vec_dest;
1917   tree scalar_dest;
1918   tree op0, op1 = NULL;
1919   tree vec_oprnd1 = NULL_TREE;
1920   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1921   tree vectype;
1922   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1923   enum tree_code code;
1924   enum machine_mode vec_mode;
1925   tree new_temp;
1926   int op_type;
1927   optab optab;
1928   int icode;
1929   enum machine_mode optab_op2_mode;
1930   tree def;
1931   gimple def_stmt;
1932   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
1933   gimple new_stmt = NULL;
1934   stmt_vec_info prev_stmt_info;
1935   int nunits_in;
1936   int nunits_out;
1937   tree vectype_out;
1938   int ncopies;
1939   int j, i;
1940   VEC(tree,heap) *vec_oprnds0 = NULL, *vec_oprnds1 = NULL;
1941   tree vop0, vop1;
1942   unsigned int k;
1943   bool scalar_shift_arg = false;
1944   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
1945   int vf;
1946
1947   if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
1948     return false;
1949
1950   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
1951     return false;
1952
1953   /* Is STMT a vectorizable binary/unary operation?   */
1954   if (!is_gimple_assign (stmt))
1955     return false;
1956
1957   if (TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
1958     return false;
1959
1960   code = gimple_assign_rhs_code (stmt);
1961
1962   /* For pointer addition, we should use the normal plus for
1963      the vector addition.  */
1964   if (code == POINTER_PLUS_EXPR)
1965     code = PLUS_EXPR;
1966
1967   /* Support only unary or binary operations.  */
1968   op_type = TREE_CODE_LENGTH (code);
1969   if (op_type != unary_op && op_type != binary_op)
1970     {
1971       if (vect_print_dump_info (REPORT_DETAILS))
1972         fprintf (vect_dump, "num. args = %d (not unary/binary op).", op_type);
1973       return false;
1974     }
1975
1976   scalar_dest = gimple_assign_lhs (stmt);
1977   vectype_out = STMT_VINFO_VECTYPE (stmt_info);
1978
1979   op0 = gimple_assign_rhs1 (stmt);
1980   if (!vect_is_simple_use_1 (op0, loop_vinfo, bb_vinfo,
1981                              &def_stmt, &def, &dt[0], &vectype))
1982     {
1983       if (vect_print_dump_info (REPORT_DETAILS))
1984         fprintf (vect_dump, "use not simple.");
1985       return false;
1986     }
1987   /* If op0 is an external or constant def use a vector type with
1988      the same size as the output vector type.  */
1989   if (!vectype)
1990     vectype = get_same_sized_vectype (TREE_TYPE (op0), vectype_out);
1991   gcc_assert (vectype);
1992
1993   nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
1994   nunits_in = TYPE_VECTOR_SUBPARTS (vectype);
1995   if (nunits_out != nunits_in)
1996     return false;
1997
1998   if (op_type == binary_op)
1999     {
2000       op1 = gimple_assign_rhs2 (stmt);
2001       if (!vect_is_simple_use (op1, loop_vinfo, bb_vinfo, &def_stmt, &def,
2002                                &dt[1]))
2003         {
2004           if (vect_print_dump_info (REPORT_DETAILS))
2005             fprintf (vect_dump, "use not simple.");
2006           return false;
2007         }
2008     }
2009
2010   if (loop_vinfo)
2011     vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2012   else
2013     vf = 1;
2014
2015   /* Multiple types in SLP are handled by creating the appropriate number of
2016      vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
2017      case of SLP.  */
2018   if (slp_node)
2019     ncopies = 1;
2020   else
2021     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_in;
2022
2023   gcc_assert (ncopies >= 1);
2024
2025   /* If this is a shift/rotate, determine whether the shift amount is a vector,
2026      or scalar.  If the shift/rotate amount is a vector, use the vector/vector
2027      shift optabs.  */
2028   if (code == LSHIFT_EXPR || code == RSHIFT_EXPR || code == LROTATE_EXPR
2029       || code == RROTATE_EXPR)
2030     {
2031       /* vector shifted by vector */
2032       if (dt[1] == vect_internal_def)
2033         {
2034           optab = optab_for_tree_code (code, vectype, optab_vector);
2035           if (vect_print_dump_info (REPORT_DETAILS))
2036             fprintf (vect_dump, "vector/vector shift/rotate found.");
2037         }
2038
2039       /* See if the machine has a vector shifted by scalar insn and if not
2040          then see if it has a vector shifted by vector insn */
2041       else if (dt[1] == vect_constant_def || dt[1] == vect_external_def)
2042         {
2043           optab = optab_for_tree_code (code, vectype, optab_scalar);
2044           if (optab
2045               && (optab_handler (optab, TYPE_MODE (vectype))->insn_code
2046                   != CODE_FOR_nothing))
2047             {
2048               scalar_shift_arg = true;
2049               if (vect_print_dump_info (REPORT_DETAILS))
2050                 fprintf (vect_dump, "vector/scalar shift/rotate found.");
2051             }
2052           else
2053             {
2054               optab = optab_for_tree_code (code, vectype, optab_vector);
2055               if (optab
2056                   && (optab_handler (optab, TYPE_MODE (vectype))->insn_code
2057                       != CODE_FOR_nothing))
2058                 {
2059                   if (vect_print_dump_info (REPORT_DETAILS))
2060                     fprintf (vect_dump, "vector/vector shift/rotate found.");
2061
2062                   /* Unlike the other binary operators, shifts/rotates have
2063                      the rhs being int, instead of the same type as the lhs,
2064                      so make sure the scalar is the right type if we are
2065                      dealing with vectors of short/char.  */
2066                   if (dt[1] == vect_constant_def)
2067                     op1 = fold_convert (TREE_TYPE (vectype), op1);
2068                 }
2069             }
2070         }
2071
2072       else
2073         {
2074           if (vect_print_dump_info (REPORT_DETAILS))
2075             fprintf (vect_dump, "operand mode requires invariant argument.");
2076           return false;
2077         }
2078     }
2079   else
2080     optab = optab_for_tree_code (code, vectype, optab_default);
2081
2082   /* Supportable by target?  */
2083   if (!optab)
2084     {
2085       if (vect_print_dump_info (REPORT_DETAILS))
2086         fprintf (vect_dump, "no optab.");
2087       return false;
2088     }
2089   vec_mode = TYPE_MODE (vectype);
2090   icode = (int) optab_handler (optab, vec_mode)->insn_code;
2091   if (icode == CODE_FOR_nothing)
2092     {
2093       if (vect_print_dump_info (REPORT_DETAILS))
2094         fprintf (vect_dump, "op not supported by target.");
2095       /* Check only during analysis.  */
2096       if (GET_MODE_SIZE (vec_mode) != UNITS_PER_WORD
2097           || (vf < vect_min_worthwhile_factor (code)
2098               && !vec_stmt))
2099         return false;
2100       if (vect_print_dump_info (REPORT_DETAILS))
2101         fprintf (vect_dump, "proceeding using word mode.");
2102     }
2103
2104   /* Worthwhile without SIMD support? Check only during analysis.  */
2105   if (!VECTOR_MODE_P (TYPE_MODE (vectype))
2106       && vf < vect_min_worthwhile_factor (code)
2107       && !vec_stmt)
2108     {
2109       if (vect_print_dump_info (REPORT_DETAILS))
2110         fprintf (vect_dump, "not worthwhile without SIMD support.");
2111       return false;
2112     }
2113
2114   if (!vec_stmt) /* transformation not required.  */
2115     {
2116       STMT_VINFO_TYPE (stmt_info) = op_vec_info_type;
2117       if (vect_print_dump_info (REPORT_DETAILS))
2118         fprintf (vect_dump, "=== vectorizable_operation ===");
2119       vect_model_simple_cost (stmt_info, ncopies, dt, NULL);
2120       return true;
2121     }
2122
2123   /** Transform.  **/
2124
2125   if (vect_print_dump_info (REPORT_DETAILS))
2126     fprintf (vect_dump, "transform binary/unary operation.");
2127
2128   /* Handle def.  */
2129   vec_dest = vect_create_destination_var (scalar_dest, vectype);
2130
2131   /* Allocate VECs for vector operands. In case of SLP, vector operands are
2132      created in the previous stages of the recursion, so no allocation is
2133      needed, except for the case of shift with scalar shift argument. In that
2134      case we store the scalar operand in VEC_OPRNDS1 for every vector stmt to
2135      be created to vectorize the SLP group, i.e., SLP_NODE->VEC_STMTS_SIZE.
2136      In case of loop-based vectorization we allocate VECs of size 1. We
2137      allocate VEC_OPRNDS1 only in case of binary operation.  */
2138   if (!slp_node)
2139     {
2140       vec_oprnds0 = VEC_alloc (tree, heap, 1);
2141       if (op_type == binary_op)
2142         vec_oprnds1 = VEC_alloc (tree, heap, 1);
2143     }
2144   else if (scalar_shift_arg)
2145     vec_oprnds1 = VEC_alloc (tree, heap, slp_node->vec_stmts_size);
2146
2147   /* In case the vectorization factor (VF) is bigger than the number
2148      of elements that we can fit in a vectype (nunits), we have to generate
2149      more than one vector stmt - i.e - we need to "unroll" the
2150      vector stmt by a factor VF/nunits. In doing so, we record a pointer
2151      from one copy of the vector stmt to the next, in the field
2152      STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
2153      stages to find the correct vector defs to be used when vectorizing
2154      stmts that use the defs of the current stmt. The example below illustrates
2155      the vectorization process when VF=16 and nunits=4 (i.e - we need to create
2156      4 vectorized stmts):
2157
2158      before vectorization:
2159                                 RELATED_STMT    VEC_STMT
2160         S1:     x = memref      -               -
2161         S2:     z = x + 1       -               -
2162
2163      step 1: vectorize stmt S1 (done in vectorizable_load. See more details
2164              there):
2165                                 RELATED_STMT    VEC_STMT
2166         VS1_0:  vx0 = memref0   VS1_1           -
2167         VS1_1:  vx1 = memref1   VS1_2           -
2168         VS1_2:  vx2 = memref2   VS1_3           -
2169         VS1_3:  vx3 = memref3   -               -
2170         S1:     x = load        -               VS1_0
2171         S2:     z = x + 1       -               -
2172
2173      step2: vectorize stmt S2 (done here):
2174         To vectorize stmt S2 we first need to find the relevant vector
2175         def for the first operand 'x'. This is, as usual, obtained from
2176         the vector stmt recorded in the STMT_VINFO_VEC_STMT of the stmt
2177         that defines 'x' (S1). This way we find the stmt VS1_0, and the
2178         relevant vector def 'vx0'. Having found 'vx0' we can generate
2179         the vector stmt VS2_0, and as usual, record it in the
2180         STMT_VINFO_VEC_STMT of stmt S2.
2181         When creating the second copy (VS2_1), we obtain the relevant vector
2182         def from the vector stmt recorded in the STMT_VINFO_RELATED_STMT of
2183         stmt VS1_0. This way we find the stmt VS1_1 and the relevant
2184         vector def 'vx1'. Using 'vx1' we create stmt VS2_1 and record a
2185         pointer to it in the STMT_VINFO_RELATED_STMT of the vector stmt VS2_0.
2186         Similarly when creating stmts VS2_2 and VS2_3. This is the resulting
2187         chain of stmts and pointers:
2188                                 RELATED_STMT    VEC_STMT
2189         VS1_0:  vx0 = memref0   VS1_1           -
2190         VS1_1:  vx1 = memref1   VS1_2           -
2191         VS1_2:  vx2 = memref2   VS1_3           -
2192         VS1_3:  vx3 = memref3   -               -
2193         S1:     x = load        -               VS1_0
2194         VS2_0:  vz0 = vx0 + v1  VS2_1           -
2195         VS2_1:  vz1 = vx1 + v1  VS2_2           -
2196         VS2_2:  vz2 = vx2 + v1  VS2_3           -
2197         VS2_3:  vz3 = vx3 + v1  -               -
2198         S2:     z = x + 1       -               VS2_0  */
2199
2200   prev_stmt_info = NULL;
2201   for (j = 0; j < ncopies; j++)
2202     {
2203       /* Handle uses.  */
2204       if (j == 0)
2205         {
2206           if (op_type == binary_op && scalar_shift_arg)
2207             {
2208               /* Vector shl and shr insn patterns can be defined with scalar
2209                  operand 2 (shift operand). In this case, use constant or loop
2210                  invariant op1 directly, without extending it to vector mode
2211                  first.  */
2212               optab_op2_mode = insn_data[icode].operand[2].mode;
2213               if (!VECTOR_MODE_P (optab_op2_mode))
2214                 {
2215                   if (vect_print_dump_info (REPORT_DETAILS))
2216                     fprintf (vect_dump, "operand 1 using scalar mode.");
2217                   vec_oprnd1 = op1;
2218                   VEC_quick_push (tree, vec_oprnds1, vec_oprnd1);
2219                   if (slp_node)
2220                     {
2221                       /* Store vec_oprnd1 for every vector stmt to be created
2222                          for SLP_NODE. We check during the analysis that all the
2223                          shift arguments are the same.
2224                          TODO: Allow different constants for different vector
2225                          stmts generated for an SLP instance.  */
2226                       for (k = 0; k < slp_node->vec_stmts_size - 1; k++)
2227                         VEC_quick_push (tree, vec_oprnds1, vec_oprnd1);
2228                     }
2229                 }
2230             }
2231
2232           /* vec_oprnd1 is available if operand 1 should be of a scalar-type
2233              (a special case for certain kind of vector shifts); otherwise,
2234              operand 1 should be of a vector type (the usual case).  */
2235           if (op_type == binary_op && !vec_oprnd1)
2236             vect_get_vec_defs (op0, op1, stmt, &vec_oprnds0, &vec_oprnds1,
2237                                slp_node);
2238           else
2239             vect_get_vec_defs (op0, NULL_TREE, stmt, &vec_oprnds0, NULL,
2240                                slp_node);
2241         }
2242       else
2243         vect_get_vec_defs_for_stmt_copy (dt, &vec_oprnds0, &vec_oprnds1);
2244
2245       /* Arguments are ready. Create the new vector stmt.  */
2246       for (i = 0; VEC_iterate (tree, vec_oprnds0, i, vop0); i++)
2247         {
2248           vop1 = ((op_type == binary_op)
2249                   ? VEC_index (tree, vec_oprnds1, i) : NULL);
2250           new_stmt = gimple_build_assign_with_ops (code, vec_dest, vop0, vop1);
2251           new_temp = make_ssa_name (vec_dest, new_stmt);
2252           gimple_assign_set_lhs (new_stmt, new_temp);
2253           vect_finish_stmt_generation (stmt, new_stmt, gsi);
2254           if (slp_node)
2255             VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
2256         }
2257
2258       if (slp_node)
2259         continue;
2260
2261       if (j == 0)
2262         STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
2263       else
2264         STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
2265       prev_stmt_info = vinfo_for_stmt (new_stmt);
2266     }
2267
2268   VEC_free (tree, heap, vec_oprnds0);
2269   if (vec_oprnds1)
2270     VEC_free (tree, heap, vec_oprnds1);
2271
2272   return true;
2273 }
2274
2275
2276 /* Get vectorized definitions for loop-based vectorization. For the first
2277    operand we call vect_get_vec_def_for_operand() (with OPRND containing
2278    scalar operand), and for the rest we get a copy with
2279    vect_get_vec_def_for_stmt_copy() using the previous vector definition
2280    (stored in OPRND). See vect_get_vec_def_for_stmt_copy() for details.
2281    The vectors are collected into VEC_OPRNDS.  */
2282
2283 static void
2284 vect_get_loop_based_defs (tree *oprnd, gimple stmt, enum vect_def_type dt,
2285                           VEC (tree, heap) **vec_oprnds, int multi_step_cvt)
2286 {
2287   tree vec_oprnd;
2288
2289   /* Get first vector operand.  */
2290   /* All the vector operands except the very first one (that is scalar oprnd)
2291      are stmt copies.  */
2292   if (TREE_CODE (TREE_TYPE (*oprnd)) != VECTOR_TYPE)
2293     vec_oprnd = vect_get_vec_def_for_operand (*oprnd, stmt, NULL);
2294   else
2295     vec_oprnd = vect_get_vec_def_for_stmt_copy (dt, *oprnd);
2296
2297   VEC_quick_push (tree, *vec_oprnds, vec_oprnd);
2298
2299   /* Get second vector operand.  */
2300   vec_oprnd = vect_get_vec_def_for_stmt_copy (dt, vec_oprnd);
2301   VEC_quick_push (tree, *vec_oprnds, vec_oprnd);
2302
2303   *oprnd = vec_oprnd;
2304
2305   /* For conversion in multiple steps, continue to get operands
2306      recursively.  */
2307   if (multi_step_cvt)
2308     vect_get_loop_based_defs (oprnd, stmt, dt, vec_oprnds,  multi_step_cvt - 1);
2309 }
2310
2311
2312 /* Create vectorized demotion statements for vector operands from VEC_OPRNDS.
2313    For multi-step conversions store the resulting vectors and call the function
2314    recursively.  */
2315
2316 static void
2317 vect_create_vectorized_demotion_stmts (VEC (tree, heap) **vec_oprnds,
2318                                        int multi_step_cvt, gimple stmt,
2319                                        VEC (tree, heap) *vec_dsts,
2320                                        gimple_stmt_iterator *gsi,
2321                                        slp_tree slp_node, enum tree_code code,
2322                                        stmt_vec_info *prev_stmt_info)
2323 {
2324   unsigned int i;
2325   tree vop0, vop1, new_tmp, vec_dest;
2326   gimple new_stmt;
2327   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2328
2329   vec_dest = VEC_pop (tree, vec_dsts);
2330
2331   for (i = 0; i < VEC_length (tree, *vec_oprnds); i += 2)
2332     {
2333       /* Create demotion operation.  */
2334       vop0 = VEC_index (tree, *vec_oprnds, i);
2335       vop1 = VEC_index (tree, *vec_oprnds, i + 1);
2336       new_stmt = gimple_build_assign_with_ops (code, vec_dest, vop0, vop1);
2337       new_tmp = make_ssa_name (vec_dest, new_stmt);
2338       gimple_assign_set_lhs (new_stmt, new_tmp);
2339       vect_finish_stmt_generation (stmt, new_stmt, gsi);
2340
2341       if (multi_step_cvt)
2342         /* Store the resulting vector for next recursive call.  */
2343         VEC_replace (tree, *vec_oprnds, i/2, new_tmp);
2344       else
2345         {
2346           /* This is the last step of the conversion sequence. Store the
2347              vectors in SLP_NODE or in vector info of the scalar statement
2348              (or in STMT_VINFO_RELATED_STMT chain).  */
2349           if (slp_node)
2350             VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
2351           else
2352             {
2353               if (!*prev_stmt_info)
2354                 STMT_VINFO_VEC_STMT (stmt_info) = new_stmt;
2355               else
2356                 STMT_VINFO_RELATED_STMT (*prev_stmt_info) = new_stmt;
2357
2358               *prev_stmt_info = vinfo_for_stmt (new_stmt);
2359             }
2360         }
2361     }
2362
2363   /* For multi-step demotion operations we first generate demotion operations
2364      from the source type to the intermediate types, and then combine the
2365      results (stored in VEC_OPRNDS) in demotion operation to the destination
2366      type.  */
2367   if (multi_step_cvt)
2368     {
2369       /* At each level of recursion we have have of the operands we had at the
2370          previous level.  */
2371       VEC_truncate (tree, *vec_oprnds, (i+1)/2);
2372       vect_create_vectorized_demotion_stmts (vec_oprnds, multi_step_cvt - 1,
2373                                              stmt, vec_dsts, gsi, slp_node,
2374                                              code, prev_stmt_info);
2375     }
2376 }
2377
2378
2379 /* Function vectorizable_type_demotion
2380
2381    Check if STMT performs a binary or unary operation that involves
2382    type demotion, and if it can be vectorized.
2383    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2384    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2385    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
2386
2387 static bool
2388 vectorizable_type_demotion (gimple stmt, gimple_stmt_iterator *gsi,
2389                             gimple *vec_stmt, slp_tree slp_node)
2390 {
2391   tree vec_dest;
2392   tree scalar_dest;
2393   tree op0;
2394   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2395   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2396   enum tree_code code, code1 = ERROR_MARK;
2397   tree def;
2398   gimple def_stmt;
2399   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
2400   stmt_vec_info prev_stmt_info;
2401   int nunits_in;
2402   int nunits_out;
2403   tree vectype_out;
2404   int ncopies;
2405   int j, i;
2406   tree vectype_in;
2407   int multi_step_cvt = 0;
2408   VEC (tree, heap) *vec_oprnds0 = NULL;
2409   VEC (tree, heap) *vec_dsts = NULL, *interm_types = NULL, *tmp_vec_dsts = NULL;
2410   tree last_oprnd, intermediate_type;
2411
2412   /* FORNOW: not supported by basic block SLP vectorization.  */
2413   gcc_assert (loop_vinfo);
2414
2415   if (!STMT_VINFO_RELEVANT_P (stmt_info))
2416     return false;
2417
2418   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
2419     return false;
2420
2421   /* Is STMT a vectorizable type-demotion operation?  */
2422   if (!is_gimple_assign (stmt))
2423     return false;
2424
2425   if (TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
2426     return false;
2427
2428   code = gimple_assign_rhs_code (stmt);
2429   if (!CONVERT_EXPR_CODE_P (code))
2430     return false;
2431
2432   scalar_dest = gimple_assign_lhs (stmt);
2433   vectype_out = STMT_VINFO_VECTYPE (stmt_info);
2434
2435   /* Check the operands of the operation.  */
2436   op0 = gimple_assign_rhs1 (stmt);
2437   if (! ((INTEGRAL_TYPE_P (TREE_TYPE (scalar_dest))
2438           && INTEGRAL_TYPE_P (TREE_TYPE (op0)))
2439          || (SCALAR_FLOAT_TYPE_P (TREE_TYPE (scalar_dest))
2440              && SCALAR_FLOAT_TYPE_P (TREE_TYPE (op0))
2441              && CONVERT_EXPR_CODE_P (code))))
2442     return false;
2443   if (!vect_is_simple_use_1 (op0, loop_vinfo, NULL,
2444                              &def_stmt, &def, &dt[0], &vectype_in))
2445     {
2446       if (vect_print_dump_info (REPORT_DETAILS))
2447         fprintf (vect_dump, "use not simple.");
2448       return false;
2449     }
2450   /* If op0 is an external def use a vector type with the
2451      same size as the output vector type if possible.  */
2452   if (!vectype_in)
2453     vectype_in = get_same_sized_vectype (TREE_TYPE (op0), vectype_out);
2454   if (!vectype_in)
2455     return false;
2456
2457   nunits_in = TYPE_VECTOR_SUBPARTS (vectype_in);
2458   nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
2459   if (nunits_in >= nunits_out)
2460     return false;
2461
2462   /* Multiple types in SLP are handled by creating the appropriate number of
2463      vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
2464      case of SLP.  */
2465   if (slp_node)
2466     ncopies = 1;
2467   else
2468     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_out;
2469   gcc_assert (ncopies >= 1);
2470
2471   /* Supportable by target?  */
2472   if (!supportable_narrowing_operation (code, vectype_out, vectype_in,
2473                                         &code1, &multi_step_cvt, &interm_types))
2474     return false;
2475
2476   if (!vec_stmt) /* transformation not required.  */
2477     {
2478       STMT_VINFO_TYPE (stmt_info) = type_demotion_vec_info_type;
2479       if (vect_print_dump_info (REPORT_DETAILS))
2480         fprintf (vect_dump, "=== vectorizable_demotion ===");
2481       vect_model_simple_cost (stmt_info, ncopies, dt, NULL);
2482       return true;
2483     }
2484
2485   /** Transform.  **/
2486   if (vect_print_dump_info (REPORT_DETAILS))
2487     fprintf (vect_dump, "transform type demotion operation. ncopies = %d.",
2488              ncopies);
2489
2490   /* In case of multi-step demotion, we first generate demotion operations to
2491      the intermediate types, and then from that types to the final one.
2492      We create vector destinations for the intermediate type (TYPES) received
2493      from supportable_narrowing_operation, and store them in the correct order
2494      for future use in vect_create_vectorized_demotion_stmts().  */
2495   if (multi_step_cvt)
2496     vec_dsts = VEC_alloc (tree, heap, multi_step_cvt + 1);
2497   else
2498     vec_dsts = VEC_alloc (tree, heap, 1);
2499
2500   vec_dest = vect_create_destination_var (scalar_dest, vectype_out);
2501   VEC_quick_push (tree, vec_dsts, vec_dest);
2502
2503   if (multi_step_cvt)
2504     {
2505       for (i = VEC_length (tree, interm_types) - 1;
2506            VEC_iterate (tree, interm_types, i, intermediate_type); i--)
2507         {
2508           vec_dest = vect_create_destination_var (scalar_dest,
2509                                                   intermediate_type);
2510           VEC_quick_push (tree, vec_dsts, vec_dest);
2511         }
2512     }
2513
2514   /* In case the vectorization factor (VF) is bigger than the number
2515      of elements that we can fit in a vectype (nunits), we have to generate
2516      more than one vector stmt - i.e - we need to "unroll" the
2517      vector stmt by a factor VF/nunits.   */
2518   last_oprnd = op0;
2519   prev_stmt_info = NULL;
2520   for (j = 0; j < ncopies; j++)
2521     {
2522       /* Handle uses.  */
2523       if (slp_node)
2524         vect_get_slp_defs (slp_node, &vec_oprnds0, NULL, -1);
2525       else
2526         {
2527           VEC_free (tree, heap, vec_oprnds0);
2528           vec_oprnds0 = VEC_alloc (tree, heap,
2529                         (multi_step_cvt ? vect_pow2 (multi_step_cvt) * 2 : 2));
2530           vect_get_loop_based_defs (&last_oprnd, stmt, dt[0], &vec_oprnds0,
2531                                     vect_pow2 (multi_step_cvt) - 1);
2532         }
2533
2534       /* Arguments are ready. Create the new vector stmts.  */
2535       tmp_vec_dsts = VEC_copy (tree, heap, vec_dsts);
2536       vect_create_vectorized_demotion_stmts (&vec_oprnds0,
2537                                              multi_step_cvt, stmt, tmp_vec_dsts,
2538                                              gsi, slp_node, code1,
2539                                              &prev_stmt_info);
2540     }
2541
2542   VEC_free (tree, heap, vec_oprnds0);
2543   VEC_free (tree, heap, vec_dsts);
2544   VEC_free (tree, heap, tmp_vec_dsts);
2545   VEC_free (tree, heap, interm_types);
2546
2547   *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
2548   return true;
2549 }
2550
2551
2552 /* Create vectorized promotion statements for vector operands from VEC_OPRNDS0
2553    and VEC_OPRNDS1 (for binary operations). For multi-step conversions store
2554    the resulting vectors and call the function recursively.  */
2555
2556 static void
2557 vect_create_vectorized_promotion_stmts (VEC (tree, heap) **vec_oprnds0,
2558                                         VEC (tree, heap) **vec_oprnds1,
2559                                         int multi_step_cvt, gimple stmt,
2560                                         VEC (tree, heap) *vec_dsts,
2561                                         gimple_stmt_iterator *gsi,
2562                                         slp_tree slp_node, enum tree_code code1,
2563                                         enum tree_code code2, tree decl1,
2564                                         tree decl2, int op_type,
2565                                         stmt_vec_info *prev_stmt_info)
2566 {
2567   int i;
2568   tree vop0, vop1, new_tmp1, new_tmp2, vec_dest;
2569   gimple new_stmt1, new_stmt2;
2570   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2571   VEC (tree, heap) *vec_tmp;
2572
2573   vec_dest = VEC_pop (tree, vec_dsts);
2574   vec_tmp = VEC_alloc (tree, heap, VEC_length (tree, *vec_oprnds0) * 2);
2575
2576   for (i = 0; VEC_iterate (tree, *vec_oprnds0, i, vop0); i++)
2577     {
2578       if (op_type == binary_op)
2579         vop1 = VEC_index (tree, *vec_oprnds1, i);
2580       else
2581         vop1 = NULL_TREE;
2582
2583       /* Generate the two halves of promotion operation.  */
2584       new_stmt1 = vect_gen_widened_results_half (code1, decl1, vop0, vop1,
2585                                                  op_type, vec_dest, gsi, stmt);
2586       new_stmt2 = vect_gen_widened_results_half (code2, decl2, vop0, vop1,
2587                                                  op_type, vec_dest, gsi, stmt);
2588       if (is_gimple_call (new_stmt1))
2589         {
2590           new_tmp1 = gimple_call_lhs (new_stmt1);
2591           new_tmp2 = gimple_call_lhs (new_stmt2);
2592         }
2593       else
2594         {
2595           new_tmp1 = gimple_assign_lhs (new_stmt1);
2596           new_tmp2 = gimple_assign_lhs (new_stmt2);
2597         }
2598
2599       if (multi_step_cvt)
2600         {
2601           /* Store the results for the recursive call.  */
2602           VEC_quick_push (tree, vec_tmp, new_tmp1);
2603           VEC_quick_push (tree, vec_tmp, new_tmp2);
2604         }
2605       else
2606         {
2607           /* Last step of promotion sequience - store the results.  */
2608           if (slp_node)
2609             {
2610               VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt1);
2611               VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt2);
2612             }
2613           else
2614             {
2615               if (!*prev_stmt_info)
2616                 STMT_VINFO_VEC_STMT (stmt_info) = new_stmt1;
2617               else
2618                 STMT_VINFO_RELATED_STMT (*prev_stmt_info) = new_stmt1;
2619
2620               *prev_stmt_info = vinfo_for_stmt (new_stmt1);
2621               STMT_VINFO_RELATED_STMT (*prev_stmt_info) = new_stmt2;
2622               *prev_stmt_info = vinfo_for_stmt (new_stmt2);
2623             }
2624         }
2625     }
2626
2627   if (multi_step_cvt)
2628     {
2629       /* For multi-step promotion operation we first generate we call the
2630          function recurcively for every stage. We start from the input type,
2631          create promotion operations to the intermediate types, and then
2632          create promotions to the output type.  */
2633       *vec_oprnds0 = VEC_copy (tree, heap, vec_tmp);
2634       VEC_free (tree, heap, vec_tmp);
2635       vect_create_vectorized_promotion_stmts (vec_oprnds0, vec_oprnds1,
2636                                               multi_step_cvt - 1, stmt,
2637                                               vec_dsts, gsi, slp_node, code1,
2638                                               code2, decl2, decl2, op_type,
2639                                               prev_stmt_info);
2640     }
2641 }
2642
2643
2644 /* Function vectorizable_type_promotion
2645
2646    Check if STMT performs a binary or unary operation that involves
2647    type promotion, and if it can be vectorized.
2648    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2649    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2650    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
2651
2652 static bool
2653 vectorizable_type_promotion (gimple stmt, gimple_stmt_iterator *gsi,
2654                              gimple *vec_stmt, slp_tree slp_node)
2655 {
2656   tree vec_dest;
2657   tree scalar_dest;
2658   tree op0, op1 = NULL;
2659   tree vec_oprnd0=NULL, vec_oprnd1=NULL;
2660   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2661   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2662   enum tree_code code, code1 = ERROR_MARK, code2 = ERROR_MARK;
2663   tree decl1 = NULL_TREE, decl2 = NULL_TREE;
2664   int op_type;
2665   tree def;
2666   gimple def_stmt;
2667   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
2668   stmt_vec_info prev_stmt_info;
2669   int nunits_in;
2670   int nunits_out;
2671   tree vectype_out;
2672   int ncopies;
2673   int j, i;
2674   tree vectype_in;
2675   tree intermediate_type = NULL_TREE;
2676   int multi_step_cvt = 0;
2677   VEC (tree, heap) *vec_oprnds0 = NULL, *vec_oprnds1 = NULL;
2678   VEC (tree, heap) *vec_dsts = NULL, *interm_types = NULL, *tmp_vec_dsts = NULL;
2679
2680   /* FORNOW: not supported by basic block SLP vectorization.  */
2681   gcc_assert (loop_vinfo);
2682
2683   if (!STMT_VINFO_RELEVANT_P (stmt_info))
2684     return false;
2685
2686   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
2687     return false;
2688
2689   /* Is STMT a vectorizable type-promotion operation?  */
2690   if (!is_gimple_assign (stmt))
2691     return false;
2692
2693   if (TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
2694     return false;
2695
2696   code = gimple_assign_rhs_code (stmt);
2697   if (!CONVERT_EXPR_CODE_P (code)
2698       && code != WIDEN_MULT_EXPR)
2699     return false;
2700
2701   scalar_dest = gimple_assign_lhs (stmt);
2702   vectype_out = STMT_VINFO_VECTYPE (stmt_info);
2703
2704   /* Check the operands of the operation.  */
2705   op0 = gimple_assign_rhs1 (stmt);
2706   if (! ((INTEGRAL_TYPE_P (TREE_TYPE (scalar_dest))
2707           && INTEGRAL_TYPE_P (TREE_TYPE (op0)))
2708          || (SCALAR_FLOAT_TYPE_P (TREE_TYPE (scalar_dest))
2709              && SCALAR_FLOAT_TYPE_P (TREE_TYPE (op0))
2710              && CONVERT_EXPR_CODE_P (code))))
2711     return false;
2712   if (!vect_is_simple_use_1 (op0, loop_vinfo, NULL,
2713                              &def_stmt, &def, &dt[0], &vectype_in))
2714     {
2715       if (vect_print_dump_info (REPORT_DETAILS))
2716         fprintf (vect_dump, "use not simple.");
2717       return false;
2718     }
2719   /* If op0 is an external or constant def use a vector type with
2720      the same size as the output vector type.  */
2721   if (!vectype_in)
2722     vectype_in = get_same_sized_vectype (TREE_TYPE (op0), vectype_out);
2723   if (!vectype_in)
2724     return false;
2725
2726   nunits_in = TYPE_VECTOR_SUBPARTS (vectype_in);
2727   nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
2728   if (nunits_in <= nunits_out)
2729     return false;
2730
2731   /* Multiple types in SLP are handled by creating the appropriate number of
2732      vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
2733      case of SLP.  */
2734   if (slp_node)
2735     ncopies = 1;
2736   else
2737     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_in;
2738
2739   gcc_assert (ncopies >= 1);
2740
2741   op_type = TREE_CODE_LENGTH (code);
2742   if (op_type == binary_op)
2743     {
2744       op1 = gimple_assign_rhs2 (stmt);
2745       if (!vect_is_simple_use (op1, loop_vinfo, NULL, &def_stmt, &def, &dt[1]))
2746         {
2747           if (vect_print_dump_info (REPORT_DETAILS))
2748             fprintf (vect_dump, "use not simple.");
2749           return false;
2750         }
2751     }
2752
2753   /* Supportable by target?  */
2754   if (!supportable_widening_operation (code, stmt, vectype_out, vectype_in,
2755                                        &decl1, &decl2, &code1, &code2,
2756                                        &multi_step_cvt, &interm_types))
2757     return false;
2758
2759   /* Binary widening operation can only be supported directly by the
2760      architecture.  */
2761   gcc_assert (!(multi_step_cvt && op_type == binary_op));
2762
2763   if (!vec_stmt) /* transformation not required.  */
2764     {
2765       STMT_VINFO_TYPE (stmt_info) = type_promotion_vec_info_type;
2766       if (vect_print_dump_info (REPORT_DETAILS))
2767         fprintf (vect_dump, "=== vectorizable_promotion ===");
2768       vect_model_simple_cost (stmt_info, 2*ncopies, dt, NULL);
2769       return true;
2770     }
2771
2772   /** Transform.  **/
2773
2774   if (vect_print_dump_info (REPORT_DETAILS))
2775     fprintf (vect_dump, "transform type promotion operation. ncopies = %d.",
2776                         ncopies);
2777
2778   /* Handle def.  */
2779   /* In case of multi-step promotion, we first generate promotion operations
2780      to the intermediate types, and then from that types to the final one.
2781      We store vector destination in VEC_DSTS in the correct order for
2782      recursive creation of promotion operations in
2783      vect_create_vectorized_promotion_stmts(). Vector destinations are created
2784      according to TYPES recieved from supportable_widening_operation().   */
2785   if (multi_step_cvt)
2786     vec_dsts = VEC_alloc (tree, heap, multi_step_cvt + 1);
2787   else
2788     vec_dsts = VEC_alloc (tree, heap, 1);
2789
2790   vec_dest = vect_create_destination_var (scalar_dest, vectype_out);
2791   VEC_quick_push (tree, vec_dsts, vec_dest);
2792
2793   if (multi_step_cvt)
2794     {
2795       for (i = VEC_length (tree, interm_types) - 1;
2796            VEC_iterate (tree, interm_types, i, intermediate_type); i--)
2797         {
2798           vec_dest = vect_create_destination_var (scalar_dest,
2799                                                   intermediate_type);
2800           VEC_quick_push (tree, vec_dsts, vec_dest);
2801         }
2802     }
2803
2804   if (!slp_node)
2805     {
2806       vec_oprnds0 = VEC_alloc (tree, heap,
2807                             (multi_step_cvt ? vect_pow2 (multi_step_cvt) : 1));
2808       if (op_type == binary_op)
2809         vec_oprnds1 = VEC_alloc (tree, heap, 1);
2810     }
2811
2812   /* In case the vectorization factor (VF) is bigger than the number
2813      of elements that we can fit in a vectype (nunits), we have to generate
2814      more than one vector stmt - i.e - we need to "unroll" the
2815      vector stmt by a factor VF/nunits.   */
2816
2817   prev_stmt_info = NULL;
2818   for (j = 0; j < ncopies; j++)
2819     {
2820       /* Handle uses.  */
2821       if (j == 0)
2822         {
2823           if (slp_node)
2824               vect_get_slp_defs (slp_node, &vec_oprnds0, &vec_oprnds1, -1);
2825           else
2826             {
2827               vec_oprnd0 = vect_get_vec_def_for_operand (op0, stmt, NULL);
2828               VEC_quick_push (tree, vec_oprnds0, vec_oprnd0);
2829               if (op_type == binary_op)
2830                 {
2831                   vec_oprnd1 = vect_get_vec_def_for_operand (op1, stmt, NULL);
2832                   VEC_quick_push (tree, vec_oprnds1, vec_oprnd1);
2833                 }
2834             }
2835         }
2836       else
2837         {
2838           vec_oprnd0 = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd0);
2839           VEC_replace (tree, vec_oprnds0, 0, vec_oprnd0);
2840           if (op_type == binary_op)
2841             {
2842               vec_oprnd1 = vect_get_vec_def_for_stmt_copy (dt[1], vec_oprnd1);
2843               VEC_replace (tree, vec_oprnds1, 0, vec_oprnd1);
2844             }
2845         }
2846
2847       /* Arguments are ready. Create the new vector stmts.  */
2848       tmp_vec_dsts = VEC_copy (tree, heap, vec_dsts);
2849       vect_create_vectorized_promotion_stmts (&vec_oprnds0, &vec_oprnds1,
2850                                               multi_step_cvt, stmt,
2851                                               tmp_vec_dsts,
2852                                               gsi, slp_node, code1, code2,
2853                                               decl1, decl2, op_type,
2854                                               &prev_stmt_info);
2855     }
2856
2857   VEC_free (tree, heap, vec_dsts);
2858   VEC_free (tree, heap, tmp_vec_dsts);
2859   VEC_free (tree, heap, interm_types);
2860   VEC_free (tree, heap, vec_oprnds0);
2861   VEC_free (tree, heap, vec_oprnds1);
2862
2863   *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
2864   return true;
2865 }
2866
2867
2868 /* Function vectorizable_store.
2869
2870    Check if STMT defines a non scalar data-ref (array/pointer/structure) that
2871    can be vectorized.
2872    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2873    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2874    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
2875
2876 static bool
2877 vectorizable_store (gimple stmt, gimple_stmt_iterator *gsi, gimple *vec_stmt,
2878                     slp_tree slp_node)
2879 {
2880   tree scalar_dest;
2881   tree data_ref;
2882   tree op;
2883   tree vec_oprnd = NULL_TREE;
2884   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2885   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info), *first_dr = NULL;
2886   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
2887   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2888   struct loop *loop = NULL;
2889   enum machine_mode vec_mode;
2890   tree dummy;
2891   enum dr_alignment_support alignment_support_scheme;
2892   tree def;
2893   gimple def_stmt;
2894   enum vect_def_type dt;
2895   stmt_vec_info prev_stmt_info = NULL;
2896   tree dataref_ptr = NULL_TREE;
2897   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
2898   int ncopies;
2899   int j;
2900   gimple next_stmt, first_stmt = NULL;
2901   bool strided_store = false;
2902   unsigned int group_size, i;
2903   VEC(tree,heap) *dr_chain = NULL, *oprnds = NULL, *result_chain = NULL;
2904   bool inv_p;
2905   VEC(tree,heap) *vec_oprnds = NULL;
2906   bool slp = (slp_node != NULL);
2907   unsigned int vec_num;
2908   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
2909
2910   if (loop_vinfo)
2911     loop = LOOP_VINFO_LOOP (loop_vinfo);
2912
2913   /* Multiple types in SLP are handled by creating the appropriate number of
2914      vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
2915      case of SLP.  */
2916   if (slp)
2917     ncopies = 1;
2918   else
2919     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
2920
2921   gcc_assert (ncopies >= 1);
2922
2923   /* FORNOW. This restriction should be relaxed.  */
2924   if (loop && nested_in_vect_loop_p (loop, stmt) && ncopies > 1)
2925     {
2926       if (vect_print_dump_info (REPORT_DETAILS))
2927         fprintf (vect_dump, "multiple types in nested loop.");
2928       return false;
2929     }
2930
2931   if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
2932     return false;
2933
2934   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
2935     return false;
2936
2937   /* Is vectorizable store? */
2938
2939   if (!is_gimple_assign (stmt))
2940     return false;
2941
2942   scalar_dest = gimple_assign_lhs (stmt);
2943   if (TREE_CODE (scalar_dest) != ARRAY_REF
2944       && TREE_CODE (scalar_dest) != INDIRECT_REF
2945       && TREE_CODE (scalar_dest) != COMPONENT_REF
2946       && TREE_CODE (scalar_dest) != IMAGPART_EXPR
2947       && TREE_CODE (scalar_dest) != REALPART_EXPR)
2948     return false;
2949
2950   gcc_assert (gimple_assign_single_p (stmt));
2951   op = gimple_assign_rhs1 (stmt);
2952   if (!vect_is_simple_use (op, loop_vinfo, bb_vinfo, &def_stmt, &def, &dt))
2953     {
2954       if (vect_print_dump_info (REPORT_DETAILS))
2955         fprintf (vect_dump, "use not simple.");
2956       return false;
2957     }
2958
2959   /* The scalar rhs type needs to be trivially convertible to the vector
2960      component type.  This should always be the case.  */
2961   if (!useless_type_conversion_p (TREE_TYPE (vectype), TREE_TYPE (op)))
2962     {
2963       if (vect_print_dump_info (REPORT_DETAILS))
2964         fprintf (vect_dump, "???  operands of different types");
2965       return false;
2966     }
2967
2968   vec_mode = TYPE_MODE (vectype);
2969   /* FORNOW. In some cases can vectorize even if data-type not supported
2970      (e.g. - array initialization with 0).  */
2971   if (optab_handler (mov_optab, (int)vec_mode)->insn_code == CODE_FOR_nothing)
2972     return false;
2973
2974   if (!STMT_VINFO_DATA_REF (stmt_info))
2975     return false;
2976
2977   if (STMT_VINFO_STRIDED_ACCESS (stmt_info))
2978     {
2979       strided_store = true;
2980       first_stmt = DR_GROUP_FIRST_DR (stmt_info);
2981       if (!vect_strided_store_supported (vectype)
2982           && !PURE_SLP_STMT (stmt_info) && !slp)
2983         return false;
2984
2985       if (first_stmt == stmt)
2986         {
2987           /* STMT is the leader of the group. Check the operands of all the
2988              stmts of the group.  */
2989           next_stmt = DR_GROUP_NEXT_DR (stmt_info);
2990           while (next_stmt)
2991             {
2992               gcc_assert (gimple_assign_single_p (next_stmt));
2993               op = gimple_assign_rhs1 (next_stmt);
2994               if (!vect_is_simple_use (op, loop_vinfo, bb_vinfo, &def_stmt,
2995                                        &def, &dt))
2996                 {
2997                   if (vect_print_dump_info (REPORT_DETAILS))
2998                     fprintf (vect_dump, "use not simple.");
2999                   return false;
3000                 }
3001               next_stmt = DR_GROUP_NEXT_DR (vinfo_for_stmt (next_stmt));
3002             }
3003         }
3004     }
3005
3006   if (!vec_stmt) /* transformation not required.  */
3007     {
3008       STMT_VINFO_TYPE (stmt_info) = store_vec_info_type;
3009       vect_model_store_cost (stmt_info, ncopies, dt, NULL);
3010       return true;
3011     }
3012
3013   /** Transform.  **/
3014
3015   if (strided_store)
3016     {
3017       first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt));
3018       group_size = DR_GROUP_SIZE (vinfo_for_stmt (first_stmt));
3019
3020       DR_GROUP_STORE_COUNT (vinfo_for_stmt (first_stmt))++;
3021
3022       /* FORNOW */
3023       gcc_assert (!loop || !nested_in_vect_loop_p (loop, stmt));
3024
3025       /* We vectorize all the stmts of the interleaving group when we
3026          reach the last stmt in the group.  */
3027       if (DR_GROUP_STORE_COUNT (vinfo_for_stmt (first_stmt))
3028           < DR_GROUP_SIZE (vinfo_for_stmt (first_stmt))
3029           && !slp)
3030         {
3031           *vec_stmt = NULL;
3032           return true;
3033         }
3034
3035       if (slp)
3036         {
3037           strided_store = false;
3038           /* VEC_NUM is the number of vect stmts to be created for this 
3039              group.  */
3040           vec_num = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
3041           first_stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (slp_node), 0); 
3042           first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt));
3043         } 
3044       else
3045         /* VEC_NUM is the number of vect stmts to be created for this 
3046            group.  */
3047         vec_num = group_size;
3048     }
3049   else
3050     {
3051       first_stmt = stmt;
3052       first_dr = dr;
3053       group_size = vec_num = 1;
3054     }
3055
3056   if (vect_print_dump_info (REPORT_DETAILS))
3057     fprintf (vect_dump, "transform store. ncopies = %d",ncopies);
3058
3059   dr_chain = VEC_alloc (tree, heap, group_size);
3060   oprnds = VEC_alloc (tree, heap, group_size);
3061
3062   alignment_support_scheme = vect_supportable_dr_alignment (first_dr);
3063   gcc_assert (alignment_support_scheme);
3064
3065   /* In case the vectorization factor (VF) is bigger than the number
3066      of elements that we can fit in a vectype (nunits), we have to generate
3067      more than one vector stmt - i.e - we need to "unroll" the
3068      vector stmt by a factor VF/nunits.  For more details see documentation in
3069      vect_get_vec_def_for_copy_stmt.  */
3070
3071   /* In case of interleaving (non-unit strided access):
3072
3073         S1:  &base + 2 = x2
3074         S2:  &base = x0
3075         S3:  &base + 1 = x1
3076         S4:  &base + 3 = x3
3077
3078      We create vectorized stores starting from base address (the access of the
3079      first stmt in the chain (S2 in the above example), when the last store stmt
3080      of the chain (S4) is reached:
3081
3082         VS1: &base = vx2
3083         VS2: &base + vec_size*1 = vx0
3084         VS3: &base + vec_size*2 = vx1
3085         VS4: &base + vec_size*3 = vx3
3086
3087      Then permutation statements are generated:
3088
3089         VS5: vx5 = VEC_INTERLEAVE_HIGH_EXPR < vx0, vx3 >
3090         VS6: vx6 = VEC_INTERLEAVE_LOW_EXPR < vx0, vx3 >
3091         ...
3092
3093      And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
3094      (the order of the data-refs in the output of vect_permute_store_chain
3095      corresponds to the order of scalar stmts in the interleaving chain - see
3096      the documentation of vect_permute_store_chain()).
3097
3098      In case of both multiple types and interleaving, above vector stores and
3099      permutation stmts are created for every copy. The result vector stmts are
3100      put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
3101      STMT_VINFO_RELATED_STMT for the next copies.
3102   */
3103
3104   prev_stmt_info = NULL;
3105   for (j = 0; j < ncopies; j++)
3106     {
3107       gimple new_stmt;
3108       gimple ptr_incr;
3109
3110       if (j == 0)
3111         {
3112           if (slp)
3113             {
3114               /* Get vectorized arguments for SLP_NODE.  */
3115               vect_get_slp_defs (slp_node, &vec_oprnds, NULL, -1);
3116
3117               vec_oprnd = VEC_index (tree, vec_oprnds, 0);
3118             }
3119           else
3120             {
3121               /* For interleaved stores we collect vectorized defs for all the
3122                  stores in the group in DR_CHAIN and OPRNDS. DR_CHAIN is then
3123                  used as an input to vect_permute_store_chain(), and OPRNDS as
3124                  an input to vect_get_vec_def_for_stmt_copy() for the next copy.
3125
3126                  If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
3127                  OPRNDS are of size 1.  */
3128               next_stmt = first_stmt;
3129               for (i = 0; i < group_size; i++)
3130                 {
3131                   /* Since gaps are not supported for interleaved stores,
3132                      GROUP_SIZE is the exact number of stmts in the chain.
3133                      Therefore, NEXT_STMT can't be NULL_TREE.  In case that
3134                      there is no interleaving, GROUP_SIZE is 1, and only one
3135                      iteration of the loop will be executed.  */
3136                   gcc_assert (next_stmt
3137                               && gimple_assign_single_p (next_stmt));
3138                   op = gimple_assign_rhs1 (next_stmt);
3139
3140                   vec_oprnd = vect_get_vec_def_for_operand (op, next_stmt,
3141                                                             NULL);
3142                   VEC_quick_push(tree, dr_chain, vec_oprnd);
3143                   VEC_quick_push(tree, oprnds, vec_oprnd);
3144                   next_stmt = DR_GROUP_NEXT_DR (vinfo_for_stmt (next_stmt));
3145                 }
3146             }
3147
3148           /* We should have catched mismatched types earlier.  */
3149           gcc_assert (useless_type_conversion_p (vectype,
3150                                                  TREE_TYPE (vec_oprnd)));
3151           dataref_ptr = vect_create_data_ref_ptr (first_stmt, NULL, NULL_TREE,
3152                                                   &dummy, &ptr_incr, false,
3153                                                   &inv_p);
3154           gcc_assert (bb_vinfo || !inv_p);
3155         }
3156       else
3157         {
3158           /* For interleaved stores we created vectorized defs for all the
3159              defs stored in OPRNDS in the previous iteration (previous copy).
3160              DR_CHAIN is then used as an input to vect_permute_store_chain(),
3161              and OPRNDS as an input to vect_get_vec_def_for_stmt_copy() for the
3162              next copy.
3163              If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
3164              OPRNDS are of size 1.  */
3165           for (i = 0; i < group_size; i++)
3166             {
3167               op = VEC_index (tree, oprnds, i);
3168               vect_is_simple_use (op, loop_vinfo, bb_vinfo, &def_stmt, &def,
3169                                   &dt);
3170               vec_oprnd = vect_get_vec_def_for_stmt_copy (dt, op);
3171               VEC_replace(tree, dr_chain, i, vec_oprnd);
3172               VEC_replace(tree, oprnds, i, vec_oprnd);
3173             }
3174           dataref_ptr =
3175                 bump_vector_ptr (dataref_ptr, ptr_incr, gsi, stmt, NULL_TREE);
3176         }
3177
3178       if (strided_store)
3179         {
3180           result_chain = VEC_alloc (tree, heap, group_size);
3181           /* Permute.  */
3182           if (!vect_permute_store_chain (dr_chain, group_size, stmt, gsi,
3183                                          &result_chain))
3184             return false;
3185         }
3186
3187       next_stmt = first_stmt;
3188       for (i = 0; i < vec_num; i++)
3189         {
3190           if (i > 0)
3191             /* Bump the vector pointer.  */
3192             dataref_ptr = bump_vector_ptr (dataref_ptr, ptr_incr, gsi, stmt,
3193                                            NULL_TREE);
3194
3195           if (slp)
3196             vec_oprnd = VEC_index (tree, vec_oprnds, i);
3197           else if (strided_store)
3198             /* For strided stores vectorized defs are interleaved in
3199                vect_permute_store_chain().  */
3200             vec_oprnd = VEC_index (tree, result_chain, i);
3201
3202           if (aligned_access_p (first_dr))
3203             data_ref = build_fold_indirect_ref (dataref_ptr);
3204           else
3205           {
3206             int mis = DR_MISALIGNMENT (first_dr);
3207             tree tmis = (mis == -1 ? size_zero_node : size_int (mis));
3208             tmis = size_binop (MULT_EXPR, tmis, size_int (BITS_PER_UNIT));
3209             data_ref = build2 (MISALIGNED_INDIRECT_REF, vectype, dataref_ptr, tmis);
3210            }
3211
3212           /* If accesses through a pointer to vectype do not alias the original
3213              memory reference we have a problem.  This should never happen.  */
3214           gcc_assert (alias_sets_conflict_p (get_alias_set (data_ref),
3215                       get_alias_set (gimple_assign_lhs (stmt))));
3216
3217           /* Arguments are ready. Create the new vector stmt.  */
3218           new_stmt = gimple_build_assign (data_ref, vec_oprnd);
3219           vect_finish_stmt_generation (stmt, new_stmt, gsi);
3220           mark_symbols_for_renaming (new_stmt);
3221
3222           if (slp)
3223             continue;
3224
3225           if (j == 0)
3226             STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt =  new_stmt;
3227           else
3228             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
3229
3230           prev_stmt_info = vinfo_for_stmt (new_stmt);
3231           next_stmt = DR_GROUP_NEXT_DR (vinfo_for_stmt (next_stmt));
3232           if (!next_stmt)
3233             break;
3234         }
3235     }
3236
3237   VEC_free (tree, heap, dr_chain);
3238   VEC_free (tree, heap, oprnds);
3239   if (result_chain)
3240     VEC_free (tree, heap, result_chain);
3241
3242   return true;
3243 }
3244
3245 /* vectorizable_load.
3246
3247    Check if STMT reads a non scalar data-ref (array/pointer/structure) that
3248    can be vectorized.
3249    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3250    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3251    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
3252
3253 static bool
3254 vectorizable_load (gimple stmt, gimple_stmt_iterator *gsi, gimple *vec_stmt,
3255                    slp_tree slp_node, slp_instance slp_node_instance)
3256 {
3257   tree scalar_dest;
3258   tree vec_dest = NULL;
3259   tree data_ref = NULL;
3260   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3261   stmt_vec_info prev_stmt_info;
3262   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3263   struct loop *loop = NULL;
3264   struct loop *containing_loop = (gimple_bb (stmt))->loop_father;
3265   bool nested_in_vect_loop = false;
3266   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info), *first_dr;
3267   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
3268   tree new_temp;
3269   int mode;
3270   gimple new_stmt = NULL;
3271   tree dummy;
3272   enum dr_alignment_support alignment_support_scheme;
3273   tree dataref_ptr = NULL_TREE;
3274   gimple ptr_incr;
3275   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
3276   int ncopies;
3277   int i, j, group_size;
3278   tree msq = NULL_TREE, lsq;
3279   tree offset = NULL_TREE;
3280   tree realignment_token = NULL_TREE;
3281   gimple phi = NULL;
3282   VEC(tree,heap) *dr_chain = NULL;
3283   bool strided_load = false;
3284   gimple first_stmt;
3285   tree scalar_type;
3286   bool inv_p;
3287   bool compute_in_loop = false;
3288   struct loop *at_loop;
3289   int vec_num;
3290   bool slp = (slp_node != NULL);
3291   bool slp_perm = false;
3292   enum tree_code code;
3293   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
3294   int vf;
3295
3296   if (loop_vinfo)
3297     {
3298       loop = LOOP_VINFO_LOOP (loop_vinfo);
3299       nested_in_vect_loop = nested_in_vect_loop_p (loop, stmt);
3300       vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
3301     }
3302   else
3303     vf = 1;
3304
3305   /* Multiple types in SLP are handled by creating the appropriate number of
3306      vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
3307      case of SLP.  */
3308   if (slp)
3309     ncopies = 1;
3310   else
3311     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
3312
3313   gcc_assert (ncopies >= 1);
3314
3315   /* FORNOW. This restriction should be relaxed.  */
3316   if (nested_in_vect_loop && ncopies > 1)
3317     {
3318       if (vect_print_dump_info (REPORT_DETAILS))
3319         fprintf (vect_dump, "multiple types in nested loop.");
3320       return false;
3321     }
3322
3323   if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
3324     return false;
3325
3326   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
3327     return false;
3328
3329   /* Is vectorizable load? */
3330   if (!is_gimple_assign (stmt))
3331     return false;
3332
3333   scalar_dest = gimple_assign_lhs (stmt);
3334   if (TREE_CODE (scalar_dest) != SSA_NAME)
3335     return false;
3336
3337   code = gimple_assign_rhs_code (stmt);
3338   if (code != ARRAY_REF
3339       && code != INDIRECT_REF
3340       && code != COMPONENT_REF
3341       && code != IMAGPART_EXPR
3342       && code != REALPART_EXPR)
3343     return false;
3344
3345   if (!STMT_VINFO_DATA_REF (stmt_info))
3346     return false;
3347
3348   scalar_type = TREE_TYPE (DR_REF (dr));
3349   mode = (int) TYPE_MODE (vectype);
3350
3351   /* FORNOW. In some cases can vectorize even if data-type not supported
3352     (e.g. - data copies).  */
3353   if (optab_handler (mov_optab, mode)->insn_code == CODE_FOR_nothing)
3354     {
3355       if (vect_print_dump_info (REPORT_DETAILS))
3356         fprintf (vect_dump, "Aligned load, but unsupported type.");
3357       return false;
3358     }
3359
3360   /* The vector component type needs to be trivially convertible to the
3361      scalar lhs.  This should always be the case.  */
3362   if (!useless_type_conversion_p (TREE_TYPE (scalar_dest), TREE_TYPE (vectype)))
3363     {
3364       if (vect_print_dump_info (REPORT_DETAILS))
3365         fprintf (vect_dump, "???  operands of different types");
3366       return false;
3367     }
3368
3369   /* Check if the load is a part of an interleaving chain.  */
3370   if (STMT_VINFO_STRIDED_ACCESS (stmt_info))
3371     {
3372       strided_load = true;
3373       /* FORNOW */
3374       gcc_assert (! nested_in_vect_loop);
3375
3376       /* Check if interleaving is supported.  */
3377       if (!vect_strided_load_supported (vectype)
3378           && !PURE_SLP_STMT (stmt_info) && !slp)
3379         return false;
3380     }
3381
3382   if (!vec_stmt) /* transformation not required.  */
3383     {
3384       STMT_VINFO_TYPE (stmt_info) = load_vec_info_type;
3385       vect_model_load_cost (stmt_info, ncopies, NULL);
3386       return true;
3387     }
3388
3389   if (vect_print_dump_info (REPORT_DETAILS))
3390     fprintf (vect_dump, "transform load.");
3391
3392   /** Transform.  **/
3393
3394   if (strided_load)
3395     {
3396       first_stmt = DR_GROUP_FIRST_DR (stmt_info);
3397       /* Check if the chain of loads is already vectorized.  */
3398       if (STMT_VINFO_VEC_STMT (vinfo_for_stmt (first_stmt)))
3399         {
3400           *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
3401           return true;
3402         }
3403       first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt));
3404       group_size = DR_GROUP_SIZE (vinfo_for_stmt (first_stmt));
3405
3406       /* VEC_NUM is the number of vect stmts to be created for this group.  */
3407       if (slp)
3408         {
3409           strided_load = false;
3410           vec_num = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
3411           if (SLP_INSTANCE_LOAD_PERMUTATION (slp_node_instance))
3412             slp_perm = true;
3413         }
3414       else
3415         vec_num = group_size;
3416
3417       dr_chain = VEC_alloc (tree, heap, vec_num);
3418     }
3419   else
3420     {
3421       first_stmt = stmt;
3422       first_dr = dr;
3423       group_size = vec_num = 1;
3424     }
3425
3426   alignment_support_scheme = vect_supportable_dr_alignment (first_dr);
3427   gcc_assert (alignment_support_scheme);
3428
3429   /* In case the vectorization factor (VF) is bigger than the number
3430      of elements that we can fit in a vectype (nunits), we have to generate
3431      more than one vector stmt - i.e - we need to "unroll" the
3432      vector stmt by a factor VF/nunits. In doing so, we record a pointer
3433      from one copy of the vector stmt to the next, in the field
3434      STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
3435      stages to find the correct vector defs to be used when vectorizing
3436      stmts that use the defs of the current stmt. The example below illustrates
3437      the vectorization process when VF=16 and nunits=4 (i.e - we need to create
3438      4 vectorized stmts):
3439
3440      before vectorization:
3441                                 RELATED_STMT    VEC_STMT
3442         S1:     x = memref      -               -
3443         S2:     z = x + 1       -               -
3444
3445      step 1: vectorize stmt S1:
3446         We first create the vector stmt VS1_0, and, as usual, record a
3447         pointer to it in the STMT_VINFO_VEC_STMT of the scalar stmt S1.
3448         Next, we create the vector stmt VS1_1, and record a pointer to
3449         it in the STMT_VINFO_RELATED_STMT of the vector stmt VS1_0.
3450         Similarly, for VS1_2 and VS1_3. This is the resulting chain of
3451         stmts and pointers:
3452                                 RELATED_STMT    VEC_STMT
3453         VS1_0:  vx0 = memref0   VS1_1           -
3454         VS1_1:  vx1 = memref1   VS1_2           -
3455         VS1_2:  vx2 = memref2   VS1_3           -
3456         VS1_3:  vx3 = memref3   -               -
3457         S1:     x = load        -               VS1_0
3458         S2:     z = x + 1       -               -
3459
3460      See in documentation in vect_get_vec_def_for_stmt_copy for how the
3461      information we recorded in RELATED_STMT field is used to vectorize
3462      stmt S2.  */
3463
3464   /* In case of interleaving (non-unit strided access):
3465
3466      S1:  x2 = &base + 2
3467      S2:  x0 = &base
3468      S3:  x1 = &base + 1
3469      S4:  x3 = &base + 3
3470
3471      Vectorized loads are created in the order of memory accesses
3472      starting from the access of the first stmt of the chain:
3473
3474      VS1: vx0 = &base
3475      VS2: vx1 = &base + vec_size*1
3476      VS3: vx3 = &base + vec_size*2
3477      VS4: vx4 = &base + vec_size*3
3478
3479      Then permutation statements are generated:
3480
3481      VS5: vx5 = VEC_EXTRACT_EVEN_EXPR < vx0, vx1 >
3482      VS6: vx6 = VEC_EXTRACT_ODD_EXPR < vx0, vx1 >
3483        ...
3484
3485      And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
3486      (the order of the data-refs in the output of vect_permute_load_chain
3487      corresponds to the order of scalar stmts in the interleaving chain - see
3488      the documentation of vect_permute_load_chain()).
3489      The generation of permutation stmts and recording them in
3490      STMT_VINFO_VEC_STMT is done in vect_transform_strided_load().
3491
3492      In case of both multiple types and interleaving, the vector loads and
3493      permutation stmts above are created for every copy. The result vector stmts
3494      are put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
3495      STMT_VINFO_RELATED_STMT for the next copies.  */
3496
3497   /* If the data reference is aligned (dr_aligned) or potentially unaligned
3498      on a target that supports unaligned accesses (dr_unaligned_supported)
3499      we generate the following code:
3500          p = initial_addr;
3501          indx = 0;
3502          loop {
3503            p = p + indx * vectype_size;
3504            vec_dest = *(p);
3505            indx = indx + 1;
3506          }
3507
3508      Otherwise, the data reference is potentially unaligned on a target that
3509      does not support unaligned accesses (dr_explicit_realign_optimized) -
3510      then generate the following code, in which the data in each iteration is
3511      obtained by two vector loads, one from the previous iteration, and one
3512      from the current iteration:
3513          p1 = initial_addr;
3514          msq_init = *(floor(p1))
3515          p2 = initial_addr + VS - 1;
3516          realignment_token = call target_builtin;
3517          indx = 0;
3518          loop {
3519            p2 = p2 + indx * vectype_size
3520            lsq = *(floor(p2))
3521            vec_dest = realign_load (msq, lsq, realignment_token)
3522            indx = indx + 1;
3523            msq = lsq;
3524          }   */
3525
3526   /* If the misalignment remains the same throughout the execution of the
3527      loop, we can create the init_addr and permutation mask at the loop
3528      preheader. Otherwise, it needs to be created inside the loop.
3529      This can only occur when vectorizing memory accesses in the inner-loop
3530      nested within an outer-loop that is being vectorized.  */
3531
3532   if (loop && nested_in_vect_loop_p (loop, stmt)
3533       && (TREE_INT_CST_LOW (DR_STEP (dr))
3534           % GET_MODE_SIZE (TYPE_MODE (vectype)) != 0))
3535     {
3536       gcc_assert (alignment_support_scheme != dr_explicit_realign_optimized);
3537       compute_in_loop = true;
3538     }
3539
3540   if ((alignment_support_scheme == dr_explicit_realign_optimized
3541        || alignment_support_scheme == dr_explicit_realign)
3542       && !compute_in_loop)
3543     {
3544       msq = vect_setup_realignment (first_stmt, gsi, &realignment_token,
3545                                     alignment_support_scheme, NULL_TREE,
3546                                     &at_loop);
3547       if (alignment_support_scheme == dr_explicit_realign_optimized)
3548         {
3549           phi = SSA_NAME_DEF_STMT (msq);
3550           offset = size_int (TYPE_VECTOR_SUBPARTS (vectype) - 1);
3551         }
3552     }
3553   else
3554     at_loop = loop;
3555
3556   prev_stmt_info = NULL;
3557   for (j = 0; j < ncopies; j++)
3558     {
3559       /* 1. Create the vector pointer update chain.  */
3560       if (j == 0)
3561         dataref_ptr = vect_create_data_ref_ptr (first_stmt,
3562                                                 at_loop, offset,
3563                                                 &dummy, &ptr_incr, false,
3564                                                 &inv_p);
3565       else
3566         dataref_ptr =
3567                 bump_vector_ptr (dataref_ptr, ptr_incr, gsi, stmt, NULL_TREE);
3568
3569       for (i = 0; i < vec_num; i++)
3570         {
3571           if (i > 0)
3572             dataref_ptr = bump_vector_ptr (dataref_ptr, ptr_incr, gsi, stmt,
3573                                            NULL_TREE);
3574
3575           /* 2. Create the vector-load in the loop.  */
3576           switch (alignment_support_scheme)
3577             {
3578             case dr_aligned:
3579               gcc_assert (aligned_access_p (first_dr));
3580               data_ref = build_fold_indirect_ref (dataref_ptr);
3581               break;
3582             case dr_unaligned_supported:
3583               {
3584                 int mis = DR_MISALIGNMENT (first_dr);
3585                 tree tmis = (mis == -1 ? size_zero_node : size_int (mis));
3586
3587                 tmis = size_binop (MULT_EXPR, tmis, size_int(BITS_PER_UNIT));
3588                 data_ref =
3589                   build2 (MISALIGNED_INDIRECT_REF, vectype, dataref_ptr, tmis);
3590                 break;
3591               }
3592             case dr_explicit_realign:
3593               {
3594                 tree ptr, bump;
3595                 tree vs_minus_1 = size_int (TYPE_VECTOR_SUBPARTS (vectype) - 1);
3596
3597                 if (compute_in_loop)
3598                   msq = vect_setup_realignment (first_stmt, gsi,
3599                                                 &realignment_token,
3600                                                 dr_explicit_realign,
3601                                                 dataref_ptr, NULL);
3602
3603                 data_ref = build1 (ALIGN_INDIRECT_REF, vectype, dataref_ptr);
3604                 vec_dest = vect_create_destination_var (scalar_dest, vectype);
3605                 new_stmt = gimple_build_assign (vec_dest, data_ref);
3606                 new_temp = make_ssa_name (vec_dest, new_stmt);
3607                 gimple_assign_set_lhs (new_stmt, new_temp);
3608                 gimple_set_vdef (new_stmt, gimple_vdef (stmt));
3609                 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
3610                 vect_finish_stmt_generation (stmt, new_stmt, gsi);
3611                 msq = new_temp;
3612
3613                 bump = size_binop (MULT_EXPR, vs_minus_1,
3614                                    TYPE_SIZE_UNIT (scalar_type));
3615                 ptr = bump_vector_ptr (dataref_ptr, NULL, gsi, stmt, bump);
3616                 data_ref = build1 (ALIGN_INDIRECT_REF, vectype, ptr);
3617                 break;
3618               }
3619             case dr_explicit_realign_optimized:
3620               data_ref = build1 (ALIGN_INDIRECT_REF, vectype, dataref_ptr);
3621               break;
3622             default:
3623               gcc_unreachable ();
3624             }
3625           /* If accesses through a pointer to vectype do not alias the original
3626              memory reference we have a problem.  This should never happen. */
3627           gcc_assert (alias_sets_conflict_p (get_alias_set (data_ref),
3628                       get_alias_set (gimple_assign_rhs1 (stmt))));
3629           vec_dest = vect_create_destination_var (scalar_dest, vectype);
3630           new_stmt = gimple_build_assign (vec_dest, data_ref);
3631           new_temp = make_ssa_name (vec_dest, new_stmt);
3632           gimple_assign_set_lhs (new_stmt, new_temp);
3633           vect_finish_stmt_generation (stmt, new_stmt, gsi);
3634           mark_symbols_for_renaming (new_stmt);
3635
3636           /* 3. Handle explicit realignment if necessary/supported. Create in
3637                 loop: vec_dest = realign_load (msq, lsq, realignment_token)  */
3638           if (alignment_support_scheme == dr_explicit_realign_optimized
3639               || alignment_support_scheme == dr_explicit_realign)
3640             {
3641               tree tmp;
3642
3643               lsq = gimple_assign_lhs (new_stmt);
3644               if (!realignment_token)
3645                 realignment_token = dataref_ptr;
3646               vec_dest = vect_create_destination_var (scalar_dest, vectype);
3647               tmp = build3 (REALIGN_LOAD_EXPR, vectype, msq, lsq,
3648                             realignment_token);
3649               new_stmt = gimple_build_assign (vec_dest, tmp);
3650               new_temp = make_ssa_name (vec_dest, new_stmt);
3651               gimple_assign_set_lhs (new_stmt, new_temp);
3652               vect_finish_stmt_generation (stmt, new_stmt, gsi);
3653
3654               if (alignment_support_scheme == dr_explicit_realign_optimized)
3655                 {
3656                   gcc_assert (phi);
3657                   if (i == vec_num - 1 && j == ncopies - 1)
3658                     add_phi_arg (phi, lsq, loop_latch_edge (containing_loop),
3659                                  UNKNOWN_LOCATION);
3660                   msq = lsq;
3661                 }
3662             }
3663
3664           /* 4. Handle invariant-load.  */
3665           if (inv_p && !bb_vinfo)
3666             {
3667               gcc_assert (!strided_load);
3668               gcc_assert (nested_in_vect_loop_p (loop, stmt));
3669               if (j == 0)
3670                 {
3671                   int k;
3672                   tree t = NULL_TREE;
3673                   tree vec_inv, bitpos, bitsize = TYPE_SIZE (scalar_type);
3674
3675                   /* CHECKME: bitpos depends on endianess?  */
3676                   bitpos = bitsize_zero_node;
3677                   vec_inv = build3 (BIT_FIELD_REF, scalar_type, new_temp,
3678                                     bitsize, bitpos);
3679                   vec_dest =
3680                         vect_create_destination_var (scalar_dest, NULL_TREE);
3681                   new_stmt = gimple_build_assign (vec_dest, vec_inv);
3682                   new_temp = make_ssa_name (vec_dest, new_stmt);
3683                   gimple_assign_set_lhs (new_stmt, new_temp);
3684                   vect_finish_stmt_generation (stmt, new_stmt, gsi);
3685
3686                   for (k = nunits - 1; k >= 0; --k)
3687                     t = tree_cons (NULL_TREE, new_temp, t);
3688                   /* FIXME: use build_constructor directly.  */
3689                   vec_inv = build_constructor_from_list (vectype, t);
3690                   new_temp = vect_init_vector (stmt, vec_inv, vectype, gsi);
3691                   new_stmt = SSA_NAME_DEF_STMT (new_temp);
3692                 }
3693               else
3694                 gcc_unreachable (); /* FORNOW. */
3695             }
3696
3697           /* Collect vector loads and later create their permutation in
3698              vect_transform_strided_load ().  */
3699           if (strided_load || slp_perm)
3700             VEC_quick_push (tree, dr_chain, new_temp);
3701
3702          /* Store vector loads in the corresponding SLP_NODE.  */
3703           if (slp && !slp_perm)
3704             VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
3705         }
3706
3707       if (slp && !slp_perm)
3708         continue;
3709
3710       if (slp_perm)
3711         {
3712           if (!vect_transform_slp_perm_load (stmt, dr_chain, gsi, vf,
3713                                              slp_node_instance, false))
3714             {
3715               VEC_free (tree, heap, dr_chain);
3716               return false;
3717             }
3718         }
3719       else
3720         {
3721           if (strided_load)
3722             {
3723               if (!vect_transform_strided_load (stmt, dr_chain, group_size, gsi))
3724                 return false;
3725
3726               *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
3727               VEC_free (tree, heap, dr_chain);
3728               dr_chain = VEC_alloc (tree, heap, group_size);
3729             }
3730           else
3731             {
3732               if (j == 0)
3733                 STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
3734               else
3735                 STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
3736               prev_stmt_info = vinfo_for_stmt (new_stmt);
3737             }
3738         }
3739     }
3740
3741   if (dr_chain)
3742     VEC_free (tree, heap, dr_chain);
3743
3744   return true;
3745 }
3746
3747 /* Function vect_is_simple_cond.
3748
3749    Input:
3750    LOOP - the loop that is being vectorized.
3751    COND - Condition that is checked for simple use.
3752
3753    Returns whether a COND can be vectorized.  Checks whether
3754    condition operands are supportable using vec_is_simple_use.  */
3755
3756 static bool
3757 vect_is_simple_cond (tree cond, loop_vec_info loop_vinfo)
3758 {
3759   tree lhs, rhs;
3760   tree def;
3761   enum vect_def_type dt;
3762
3763   if (!COMPARISON_CLASS_P (cond))
3764     return false;
3765
3766   lhs = TREE_OPERAND (cond, 0);
3767   rhs = TREE_OPERAND (cond, 1);
3768
3769   if (TREE_CODE (lhs) == SSA_NAME)
3770     {
3771       gimple lhs_def_stmt = SSA_NAME_DEF_STMT (lhs);
3772       if (!vect_is_simple_use (lhs, loop_vinfo, NULL, &lhs_def_stmt, &def,
3773                                &dt))
3774         return false;
3775     }
3776   else if (TREE_CODE (lhs) != INTEGER_CST && TREE_CODE (lhs) != REAL_CST
3777            && TREE_CODE (lhs) != FIXED_CST)
3778     return false;
3779
3780   if (TREE_CODE (rhs) == SSA_NAME)
3781     {
3782       gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
3783       if (!vect_is_simple_use (rhs, loop_vinfo, NULL, &rhs_def_stmt, &def,
3784                                &dt))
3785         return false;
3786     }
3787   else if (TREE_CODE (rhs) != INTEGER_CST  && TREE_CODE (rhs) != REAL_CST
3788            && TREE_CODE (rhs) != FIXED_CST)
3789     return false;
3790
3791   return true;
3792 }
3793
3794 /* vectorizable_condition.
3795
3796    Check if STMT is conditional modify expression that can be vectorized.
3797    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3798    stmt using VEC_COND_EXPR  to replace it, put it in VEC_STMT, and insert it
3799    at GSI.
3800
3801    When STMT is vectorized as nested cycle, REDUC_DEF is the vector variable
3802    to be used at REDUC_INDEX (in then clause if REDUC_INDEX is 1, and in
3803    else caluse if it is 2).
3804
3805    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
3806
3807 bool
3808 vectorizable_condition (gimple stmt, gimple_stmt_iterator *gsi,
3809                         gimple *vec_stmt, tree reduc_def, int reduc_index)
3810 {
3811   tree scalar_dest = NULL_TREE;
3812   tree vec_dest = NULL_TREE;
3813   tree op = NULL_TREE;
3814   tree cond_expr, then_clause, else_clause;
3815   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3816   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
3817   tree vec_cond_lhs, vec_cond_rhs, vec_then_clause, vec_else_clause;
3818   tree vec_compare, vec_cond_expr;
3819   tree new_temp;
3820   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3821   enum machine_mode vec_mode;
3822   tree def;
3823   enum vect_def_type dt;
3824   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
3825   int ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
3826   enum tree_code code;
3827
3828   /* FORNOW: unsupported in basic block SLP.  */
3829   gcc_assert (loop_vinfo);
3830
3831   gcc_assert (ncopies >= 1);
3832   if (ncopies > 1)
3833     return false; /* FORNOW */
3834
3835   if (!STMT_VINFO_RELEVANT_P (stmt_info))
3836     return false;
3837
3838   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def
3839       && !(STMT_VINFO_DEF_TYPE (stmt_info) == vect_nested_cycle
3840            && reduc_def))
3841     return false;
3842
3843   /* FORNOW: SLP not supported.  */
3844   if (STMT_SLP_TYPE (stmt_info))
3845     return false;
3846
3847   /* FORNOW: not yet supported.  */
3848   if (STMT_VINFO_LIVE_P (stmt_info))
3849     {
3850       if (vect_print_dump_info (REPORT_DETAILS))
3851         fprintf (vect_dump, "value used after loop.");
3852       return false;
3853     }
3854
3855   /* Is vectorizable conditional operation?  */
3856   if (!is_gimple_assign (stmt))
3857     return false;
3858
3859   code = gimple_assign_rhs_code (stmt);
3860
3861   if (code != COND_EXPR)
3862     return false;
3863
3864   gcc_assert (gimple_assign_single_p (stmt));
3865   op = gimple_assign_rhs1 (stmt);
3866   cond_expr = TREE_OPERAND (op, 0);
3867   then_clause = TREE_OPERAND (op, 1);
3868   else_clause = TREE_OPERAND (op, 2);
3869
3870   if (!vect_is_simple_cond (cond_expr, loop_vinfo))
3871     return false;
3872
3873   /* We do not handle two different vector types for the condition
3874      and the values.  */
3875   if (!types_compatible_p (TREE_TYPE (TREE_OPERAND (cond_expr, 0)),
3876                            TREE_TYPE (vectype)))
3877     return false;
3878
3879   if (TREE_CODE (then_clause) == SSA_NAME)
3880     {
3881       gimple then_def_stmt = SSA_NAME_DEF_STMT (then_clause);
3882       if (!vect_is_simple_use (then_clause, loop_vinfo, NULL,
3883                                &then_def_stmt, &def, &dt))
3884         return false;
3885     }
3886   else if (TREE_CODE (then_clause) != INTEGER_CST
3887            && TREE_CODE (then_clause) != REAL_CST
3888            && TREE_CODE (then_clause) != FIXED_CST)
3889     return false;
3890
3891   if (TREE_CODE (else_clause) == SSA_NAME)
3892     {
3893       gimple else_def_stmt = SSA_NAME_DEF_STMT (else_clause);
3894       if (!vect_is_simple_use (else_clause, loop_vinfo, NULL,
3895                                &else_def_stmt, &def, &dt))
3896         return false;
3897     }
3898   else if (TREE_CODE (else_clause) != INTEGER_CST
3899            && TREE_CODE (else_clause) != REAL_CST
3900            && TREE_CODE (else_clause) != FIXED_CST)
3901     return false;
3902
3903
3904   vec_mode = TYPE_MODE (vectype);
3905
3906   if (!vec_stmt)
3907     {
3908       STMT_VINFO_TYPE (stmt_info) = condition_vec_info_type;
3909       return expand_vec_cond_expr_p (TREE_TYPE (op), vec_mode);
3910     }
3911
3912   /* Transform */
3913
3914   /* Handle def.  */
3915   scalar_dest = gimple_assign_lhs (stmt);
3916   vec_dest = vect_create_destination_var (scalar_dest, vectype);
3917
3918   /* Handle cond expr.  */
3919   vec_cond_lhs =
3920     vect_get_vec_def_for_operand (TREE_OPERAND (cond_expr, 0), stmt, NULL);
3921   vec_cond_rhs =
3922     vect_get_vec_def_for_operand (TREE_OPERAND (cond_expr, 1), stmt, NULL);
3923   if (reduc_index == 1)
3924     vec_then_clause = reduc_def;
3925   else
3926     vec_then_clause = vect_get_vec_def_for_operand (then_clause, stmt, NULL);
3927   if (reduc_index == 2)
3928     vec_else_clause = reduc_def;
3929   else
3930     vec_else_clause = vect_get_vec_def_for_operand (else_clause, stmt, NULL);
3931
3932   /* Arguments are ready. Create the new vector stmt.  */
3933   vec_compare = build2 (TREE_CODE (cond_expr), vectype,
3934                         vec_cond_lhs, vec_cond_rhs);
3935   vec_cond_expr = build3 (VEC_COND_EXPR, vectype,
3936                           vec_compare, vec_then_clause, vec_else_clause);
3937
3938   *vec_stmt = gimple_build_assign (vec_dest, vec_cond_expr);
3939   new_temp = make_ssa_name (vec_dest, *vec_stmt);
3940   gimple_assign_set_lhs (*vec_stmt, new_temp);
3941   vect_finish_stmt_generation (stmt, *vec_stmt, gsi);
3942
3943   return true;
3944 }
3945
3946
3947 /* Make sure the statement is vectorizable.  */
3948
3949 bool
3950 vect_analyze_stmt (gimple stmt, bool *need_to_vectorize, slp_tree node)
3951 {
3952   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3953   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
3954   enum vect_relevant relevance = STMT_VINFO_RELEVANT (stmt_info);
3955   bool ok;
3956   tree scalar_type, vectype;
3957
3958   if (vect_print_dump_info (REPORT_DETAILS))
3959     {
3960       fprintf (vect_dump, "==> examining statement: ");
3961       print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
3962     }
3963
3964   if (gimple_has_volatile_ops (stmt))
3965     {
3966       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
3967         fprintf (vect_dump, "not vectorized: stmt has volatile operands");
3968
3969       return false;
3970     }
3971
3972   /* Skip stmts that do not need to be vectorized. In loops this is expected
3973      to include:
3974      - the COND_EXPR which is the loop exit condition
3975      - any LABEL_EXPRs in the loop
3976      - computations that are used only for array indexing or loop control.
3977      In basic blocks we only analyze statements that are a part of some SLP
3978      instance, therefore, all the statements are relevant.  */
3979
3980   if (!STMT_VINFO_RELEVANT_P (stmt_info)