OSDN Git Service

faf3b3ade221fc6f5539846aac105007c792ad61
[pf3gnuchains/gcc-fork.git] / gcc / tree-vect-transform.c
1 /* Transformation Utilities for Loop Vectorization.
2    Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3    Contributed by Dorit Naishlos <dorit@il.ibm.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "ggc.h"
26 #include "tree.h"
27 #include "target.h"
28 #include "rtl.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
33 #include "timevar.h"
34 #include "cfgloop.h"
35 #include "expr.h"
36 #include "optabs.h"
37 #include "params.h"
38 #include "recog.h"
39 #include "tree-data-ref.h"
40 #include "tree-chrec.h"
41 #include "tree-scalar-evolution.h"
42 #include "tree-vectorizer.h"
43 #include "langhooks.h"
44 #include "tree-pass.h"
45 #include "toplev.h"
46 #include "real.h"
47
48 /* Utility functions for the code transformation.  */
49 static bool vect_transform_stmt (tree, block_stmt_iterator *, bool *, slp_tree);
50 static tree vect_create_destination_var (tree, tree);
51 static tree vect_create_data_ref_ptr 
52   (tree, struct loop*, tree, tree *, tree *, bool, tree, bool *); 
53 static tree vect_create_addr_base_for_vector_ref 
54   (tree, tree *, tree, struct loop *);
55 static tree vect_get_new_vect_var (tree, enum vect_var_kind, const char *);
56 static tree vect_get_vec_def_for_operand (tree, tree, tree *);
57 static tree vect_init_vector (tree, tree, tree, block_stmt_iterator *);
58 static void vect_finish_stmt_generation 
59   (tree stmt, tree vec_stmt, block_stmt_iterator *);
60 static bool vect_is_simple_cond (tree, loop_vec_info); 
61 static void vect_create_epilog_for_reduction (tree, tree, enum tree_code, tree);
62 static tree get_initial_def_for_reduction (tree, tree, tree *);
63
64 /* Utility function dealing with loop peeling (not peeling itself).  */
65 static void vect_generate_tmps_on_preheader 
66   (loop_vec_info, tree *, tree *, tree *);
67 static tree vect_build_loop_niters (loop_vec_info);
68 static void vect_update_ivs_after_vectorizer (loop_vec_info, tree, edge); 
69 static tree vect_gen_niters_for_prolog_loop (loop_vec_info, tree);
70 static void vect_update_init_of_dr (struct data_reference *, tree niters);
71 static void vect_update_inits_of_drs (loop_vec_info, tree);
72 static int vect_min_worthwhile_factor (enum tree_code);
73
74
75 static int
76 cost_for_stmt (tree stmt)
77 {
78   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
79
80   switch (STMT_VINFO_TYPE (stmt_info))
81   {
82   case load_vec_info_type:
83     return TARG_SCALAR_LOAD_COST;
84   case store_vec_info_type:
85     return TARG_SCALAR_STORE_COST;
86   case op_vec_info_type:
87   case condition_vec_info_type:
88   case assignment_vec_info_type:
89   case reduc_vec_info_type:
90   case induc_vec_info_type:
91   case type_promotion_vec_info_type:
92   case type_demotion_vec_info_type:
93   case type_conversion_vec_info_type:
94   case call_vec_info_type:
95     return TARG_SCALAR_STMT_COST;
96   case undef_vec_info_type:
97   default:
98     gcc_unreachable ();
99   }
100 }
101
102
103 /* Function vect_estimate_min_profitable_iters
104
105    Return the number of iterations required for the vector version of the
106    loop to be profitable relative to the cost of the scalar version of the
107    loop.
108
109    TODO: Take profile info into account before making vectorization
110    decisions, if available.  */
111
112 int
113 vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo)
114 {
115   int i;
116   int min_profitable_iters;
117   int peel_iters_prologue;
118   int peel_iters_epilogue;
119   int vec_inside_cost = 0;
120   int vec_outside_cost = 0;
121   int scalar_single_iter_cost = 0;
122   int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
123   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
124   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
125   int nbbs = loop->num_nodes;
126   int byte_misalign;
127   int peel_guard_costs = 0;
128   int innerloop_iters = 0, factor;
129   VEC (slp_instance, heap) *slp_instances;
130   slp_instance instance;
131
132   /* Cost model disabled.  */
133   if (!flag_vect_cost_model)
134     {
135       if (vect_print_dump_info (REPORT_DETAILS))
136         fprintf (vect_dump, "cost model disabled.");      
137       return 0;
138     }
139
140   /* Requires loop versioning tests to handle misalignment.  */
141
142   if (VEC_length (tree, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo)))
143     {
144       /*  FIXME: Make cost depend on complexity of individual check.  */
145       vec_outside_cost +=
146         VEC_length (tree, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
147       if (vect_print_dump_info (REPORT_DETAILS))
148         fprintf (vect_dump, "cost model: Adding cost of checks for loop "
149                  "versioning to treat misalignment.\n");
150     }
151
152   if (VEC_length (ddr_p, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo)))
153     {
154       /*  FIXME: Make cost depend on complexity of individual check.  */
155       vec_outside_cost +=
156         VEC_length (ddr_p, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo));
157       if (vect_print_dump_info (REPORT_DETAILS))
158         fprintf (vect_dump, "cost model: Adding cost of checks for loop "
159                  "versioning aliasing.\n");
160     }
161
162   if (VEC_length (tree, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo))
163       || VEC_length (ddr_p, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo)))
164     {
165       vec_outside_cost += TARG_COND_TAKEN_BRANCH_COST;
166     }
167
168   /* Count statements in scalar loop.  Using this as scalar cost for a single
169      iteration for now.
170
171      TODO: Add outer loop support.
172
173      TODO: Consider assigning different costs to different scalar
174      statements.  */
175
176   /* FORNOW.  */
177   if (loop->inner)
178     innerloop_iters = 50; /* FIXME */
179
180   for (i = 0; i < nbbs; i++)
181     {
182       block_stmt_iterator si;
183       basic_block bb = bbs[i];
184
185       if (bb->loop_father == loop->inner)
186         factor = innerloop_iters;
187       else
188         factor = 1;
189
190       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
191         {
192           tree stmt = bsi_stmt (si);
193           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
194           if (!STMT_VINFO_RELEVANT_P (stmt_info)
195               && !STMT_VINFO_LIVE_P (stmt_info))
196             continue;
197           scalar_single_iter_cost += cost_for_stmt (stmt) * factor;
198           vec_inside_cost += STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info) * factor;
199           /* FIXME: for stmts in the inner-loop in outer-loop vectorization,
200              some of the "outside" costs are generated inside the outer-loop.  */
201           vec_outside_cost += STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info);
202         }
203     }
204
205   /* Add additional cost for the peeled instructions in prologue and epilogue
206      loop.
207
208      FORNOW: If we dont know the value of peel_iters for prologue or epilogue
209      at compile-time - we assume it's vf/2 (the worst would be vf-1).
210
211      TODO: Build an expression that represents peel_iters for prologue and
212      epilogue to be used in a run-time test.  */
213
214   byte_misalign = LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo);
215
216   if (byte_misalign < 0)
217     {
218       peel_iters_prologue = vf/2;
219       if (vect_print_dump_info (REPORT_DETAILS))
220         fprintf (vect_dump, "cost model: "
221                  "prologue peel iters set to vf/2.");
222
223       /* If peeling for alignment is unknown, loop bound of main loop becomes
224          unknown.  */
225       peel_iters_epilogue = vf/2;
226       if (vect_print_dump_info (REPORT_DETAILS))
227         fprintf (vect_dump, "cost model: "
228                  "epilogue peel iters set to vf/2 because "
229                  "peeling for alignment is unknown .");
230
231       /* If peeled iterations are unknown, count a taken branch and a not taken
232          branch per peeled loop. Even if scalar loop iterations are known, 
233          vector iterations are not known since peeled prologue iterations are
234          not known. Hence guards remain the same.  */
235       peel_guard_costs +=  2 * (TARG_COND_TAKEN_BRANCH_COST
236                                + TARG_COND_NOT_TAKEN_BRANCH_COST);
237
238     }
239   else 
240     {
241       if (byte_misalign)
242         {
243           struct data_reference *dr = LOOP_VINFO_UNALIGNED_DR (loop_vinfo);
244           int element_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr))));
245           tree vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr)));
246           int nelements = TYPE_VECTOR_SUBPARTS (vectype);
247
248           peel_iters_prologue = nelements - (byte_misalign / element_size);
249         }
250       else
251         peel_iters_prologue = 0;
252
253       if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
254         {
255           peel_iters_epilogue = vf/2;
256           if (vect_print_dump_info (REPORT_DETAILS))
257             fprintf (vect_dump, "cost model: "
258                      "epilogue peel iters set to vf/2 because "
259                      "loop iterations are unknown .");
260
261           /* If peeled iterations are known but number of scalar loop
262              iterations are unknown, count a taken branch per peeled loop.  */
263           peel_guard_costs +=  2 * TARG_COND_TAKEN_BRANCH_COST;
264
265         }
266       else      
267         {
268           int niters = LOOP_VINFO_INT_NITERS (loop_vinfo);
269           peel_iters_prologue = niters < peel_iters_prologue ? 
270                                         niters : peel_iters_prologue;
271           peel_iters_epilogue = (niters - peel_iters_prologue) % vf;
272         }
273     }
274
275   vec_outside_cost += (peel_iters_prologue * scalar_single_iter_cost)
276                       + (peel_iters_epilogue * scalar_single_iter_cost)
277                       + peel_guard_costs;
278
279   /* Allow targets add additional (outside-of-loop) costs. FORNOW, the only
280      information we provide for the target is whether testing against the
281      threshold involves a runtime test.  */
282   if (targetm.vectorize.builtin_vectorization_cost)
283     {
284       bool runtime_test = false;
285
286       /* If the number of iterations is unknown, or the
287          peeling-for-misalignment amount is unknown, we eill have to generate
288          a runtime test to test the loop count against the threshold.  */
289       if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
290           || (byte_misalign < 0))
291         runtime_test = true;
292       vec_outside_cost +=
293         targetm.vectorize.builtin_vectorization_cost (runtime_test);
294       if (vect_print_dump_info (REPORT_DETAILS))
295         fprintf (vect_dump, "cost model : Adding target out-of-loop cost = %d",
296                   targetm.vectorize.builtin_vectorization_cost (runtime_test));
297     }
298
299   /* Add SLP costs.  */
300   slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
301   for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
302     {
303       vec_outside_cost += SLP_INSTANCE_OUTSIDE_OF_LOOP_COST (instance);
304       vec_inside_cost += SLP_INSTANCE_INSIDE_OF_LOOP_COST (instance);
305     }
306
307   /* Calculate number of iterations required to make the vector version 
308      profitable, relative to the loop bodies only. The following condition
309      must hold true: ((SIC*VF)-VIC)*niters > VOC*VF, where
310      SIC = scalar iteration cost, VIC = vector iteration cost,
311      VOC = vector outside cost and VF = vectorization factor.  */
312
313   if ((scalar_single_iter_cost * vf) > vec_inside_cost)
314     {
315       if (vec_outside_cost <= 0)
316         min_profitable_iters = 1;
317       else
318         {
319           min_profitable_iters = (vec_outside_cost * vf 
320                                   - vec_inside_cost * peel_iters_prologue
321                                   - vec_inside_cost * peel_iters_epilogue)
322                                  / ((scalar_single_iter_cost * vf)
323                                     - vec_inside_cost);
324
325           if ((scalar_single_iter_cost * vf * min_profitable_iters)
326               <= ((vec_inside_cost * min_profitable_iters)
327                   + (vec_outside_cost * vf)))
328             min_profitable_iters++;
329         }
330     }
331   /* vector version will never be profitable.  */
332   else
333     {
334       if (vect_print_dump_info (REPORT_DETAILS))
335         fprintf (vect_dump, "cost model: vector iteration cost = %d "
336                  "is divisible by scalar iteration cost = %d by a factor "
337                  "greater than or equal to the vectorization factor = %d .",
338                  vec_inside_cost, scalar_single_iter_cost, vf);
339       return -1;
340     }
341
342   if (vect_print_dump_info (REPORT_DETAILS))
343     {
344       fprintf (vect_dump, "Cost model analysis: \n");
345       fprintf (vect_dump, "  Vector inside of loop cost: %d\n",
346                vec_inside_cost);
347       fprintf (vect_dump, "  Vector outside of loop cost: %d\n",
348                vec_outside_cost);
349       fprintf (vect_dump, "  Scalar cost: %d\n", scalar_single_iter_cost);
350       fprintf (vect_dump, "  prologue iterations: %d\n",
351                peel_iters_prologue);
352       fprintf (vect_dump, "  epilogue iterations: %d\n",
353                peel_iters_epilogue);
354       fprintf (vect_dump, "  Calculated minimum iters for profitability: %d\n",
355                min_profitable_iters);
356     }
357
358   min_profitable_iters = 
359         min_profitable_iters < vf ? vf : min_profitable_iters;
360
361   /* Because the condition we create is:
362      if (niters <= min_profitable_iters)
363        then skip the vectorized loop.  */
364   min_profitable_iters--;
365
366   if (vect_print_dump_info (REPORT_DETAILS))
367     fprintf (vect_dump, "  Profitability threshold = %d\n",
368              min_profitable_iters);
369     
370   return min_profitable_iters;
371 }
372
373
374 /* TODO: Close dependency between vect_model_*_cost and vectorizable_* 
375    functions. Design better to avoid maintenance issues.  */
376     
377 /* Function vect_model_reduction_cost.  
378
379    Models cost for a reduction operation, including the vector ops 
380    generated within the strip-mine loop, the initial definition before
381    the loop, and the epilogue code that must be generated.  */
382
383 static bool 
384 vect_model_reduction_cost (stmt_vec_info stmt_info, enum tree_code reduc_code,
385                            int ncopies)
386 {
387   int outer_cost = 0;
388   enum tree_code code;
389   optab optab;
390   tree vectype;
391   tree orig_stmt;
392   tree reduction_op;
393   enum machine_mode mode;
394   tree operation = GIMPLE_STMT_OPERAND (STMT_VINFO_STMT (stmt_info), 1);
395   int op_type = TREE_CODE_LENGTH (TREE_CODE (operation));
396   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
397   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
398
399   /* Cost of reduction op inside loop.  */
400   STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info) += ncopies * TARG_VEC_STMT_COST;
401
402   reduction_op = TREE_OPERAND (operation, op_type-1);
403   vectype = get_vectype_for_scalar_type (TREE_TYPE (reduction_op));
404   if (!vectype)
405     {
406       if (vect_print_dump_info (REPORT_DETAILS))
407         {
408           fprintf (vect_dump, "unsupported data-type ");
409           print_generic_expr (vect_dump, TREE_TYPE (reduction_op), TDF_SLIM);
410         }
411       return false;
412    }
413   
414   mode = TYPE_MODE (vectype);
415   orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
416
417   if (!orig_stmt) 
418     orig_stmt = STMT_VINFO_STMT (stmt_info);
419
420   code = TREE_CODE (GIMPLE_STMT_OPERAND (orig_stmt, 1));
421
422   /* Add in cost for initial definition.  */
423   outer_cost += TARG_SCALAR_TO_VEC_COST;
424
425   /* Determine cost of epilogue code.
426
427      We have a reduction operator that will reduce the vector in one statement.
428      Also requires scalar extract.  */
429
430   if (!nested_in_vect_loop_p (loop, orig_stmt))
431     {
432       if (reduc_code < NUM_TREE_CODES) 
433         outer_cost += TARG_VEC_STMT_COST + TARG_VEC_TO_SCALAR_COST;
434       else 
435         {
436           int vec_size_in_bits = tree_low_cst (TYPE_SIZE (vectype), 1);
437           tree bitsize =
438             TYPE_SIZE (TREE_TYPE ( GIMPLE_STMT_OPERAND (orig_stmt, 0)));
439           int element_bitsize = tree_low_cst (bitsize, 1);
440           int nelements = vec_size_in_bits / element_bitsize;
441
442           optab = optab_for_tree_code (code, vectype);
443
444           /* We have a whole vector shift available.  */
445           if (VECTOR_MODE_P (mode)
446               && optab_handler (optab, mode)->insn_code != CODE_FOR_nothing
447               && optab_handler (vec_shr_optab, mode)->insn_code != CODE_FOR_nothing)
448             /* Final reduction via vector shifts and the reduction operator. Also
449                requires scalar extract.  */
450             outer_cost += ((exact_log2(nelements) * 2) * TARG_VEC_STMT_COST
451                                 + TARG_VEC_TO_SCALAR_COST); 
452           else
453             /* Use extracts and reduction op for final reduction.  For N elements,
454                we have N extracts and N-1 reduction ops.  */
455             outer_cost += ((nelements + nelements - 1) * TARG_VEC_STMT_COST);
456         }
457     }
458
459   STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info) = outer_cost;
460
461   if (vect_print_dump_info (REPORT_DETAILS))
462     fprintf (vect_dump, "vect_model_reduction_cost: inside_cost = %d, "
463              "outside_cost = %d .", STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info),
464              STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info));
465
466   return true;
467 }
468
469
470 /* Function vect_model_induction_cost.
471
472    Models cost for induction operations.  */
473
474 static void
475 vect_model_induction_cost (stmt_vec_info stmt_info, int ncopies)
476 {
477   /* loop cost for vec_loop.  */
478   STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info) = ncopies * TARG_VEC_STMT_COST;
479   /* prologue cost for vec_init and vec_step.  */
480   STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info) = 2 * TARG_SCALAR_TO_VEC_COST;
481   
482   if (vect_print_dump_info (REPORT_DETAILS))
483     fprintf (vect_dump, "vect_model_induction_cost: inside_cost = %d, "
484              "outside_cost = %d .", STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info),
485              STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info));
486 }
487
488
489 /* Function vect_model_simple_cost.  
490
491    Models cost for simple operations, i.e. those that only emit ncopies of a 
492    single op.  Right now, this does not account for multiple insns that could
493    be generated for the single vector op.  We will handle that shortly.  */
494
495 void
496 vect_model_simple_cost (stmt_vec_info stmt_info, int ncopies, 
497                         enum vect_def_type *dt, slp_tree slp_node)
498 {
499   int i;
500   int inside_cost = 0, outside_cost = 0;
501
502   inside_cost = ncopies * TARG_VEC_STMT_COST;
503
504   /* FORNOW: Assuming maximum 2 args per stmts.  */
505   for (i = 0; i < 2; i++)
506     {
507       if (dt[i] == vect_constant_def || dt[i] == vect_invariant_def)
508         outside_cost += TARG_SCALAR_TO_VEC_COST; 
509     }
510   
511   if (vect_print_dump_info (REPORT_DETAILS))
512     fprintf (vect_dump, "vect_model_simple_cost: inside_cost = %d, "
513              "outside_cost = %d .", inside_cost, outside_cost);
514
515   /* Set the costs either in STMT_INFO or SLP_NODE (if exists).  */
516   stmt_vinfo_set_inside_of_loop_cost (stmt_info, slp_node, inside_cost);
517   stmt_vinfo_set_outside_of_loop_cost (stmt_info, slp_node, outside_cost);
518 }
519
520
521 /* Function vect_cost_strided_group_size 
522  
523    For strided load or store, return the group_size only if it is the first
524    load or store of a group, else return 1.  This ensures that group size is
525    only returned once per group.  */
526
527 static int
528 vect_cost_strided_group_size (stmt_vec_info stmt_info)
529 {
530   tree first_stmt = DR_GROUP_FIRST_DR (stmt_info);
531
532   if (first_stmt == STMT_VINFO_STMT (stmt_info))
533     return DR_GROUP_SIZE (stmt_info);
534
535   return 1;
536 }
537
538
539 /* Function vect_model_store_cost
540
541    Models cost for stores.  In the case of strided accesses, one access
542    has the overhead of the strided access attributed to it.  */
543
544 void
545 vect_model_store_cost (stmt_vec_info stmt_info, int ncopies, 
546                        enum vect_def_type dt, slp_tree slp_node)
547 {
548   int group_size;
549   int inside_cost = 0, outside_cost = 0;
550
551   if (dt == vect_constant_def || dt == vect_invariant_def)
552     outside_cost = TARG_SCALAR_TO_VEC_COST;
553
554   /* Strided access?  */
555   if (DR_GROUP_FIRST_DR (stmt_info)) 
556     group_size = vect_cost_strided_group_size (stmt_info);
557   /* Not a strided access.  */
558   else
559     group_size = 1;
560
561   /* Is this an access in a group of stores, which provide strided access?  
562      If so, add in the cost of the permutes.  */
563   if (group_size > 1) 
564     {
565       /* Uses a high and low interleave operation for each needed permute.  */
566       inside_cost = ncopies * exact_log2(group_size) * group_size 
567              * TARG_VEC_STMT_COST;
568
569       if (vect_print_dump_info (REPORT_DETAILS))
570         fprintf (vect_dump, "vect_model_store_cost: strided group_size = %d .",
571                  group_size);
572
573     }
574
575   /* Costs of the stores.  */
576   inside_cost += ncopies * TARG_VEC_STORE_COST;
577
578   if (vect_print_dump_info (REPORT_DETAILS))
579     fprintf (vect_dump, "vect_model_store_cost: inside_cost = %d, "
580              "outside_cost = %d .", inside_cost, outside_cost);
581
582   /* Set the costs either in STMT_INFO or SLP_NODE (if exists).  */
583   stmt_vinfo_set_inside_of_loop_cost (stmt_info, slp_node, inside_cost);
584   stmt_vinfo_set_outside_of_loop_cost (stmt_info, slp_node, outside_cost);
585 }
586
587
588 /* Function vect_model_load_cost
589
590    Models cost for loads.  In the case of strided accesses, the last access
591    has the overhead of the strided access attributed to it.  Since unaligned
592    accesses are supported for loads, we also account for the costs of the 
593    access scheme chosen.  */
594
595 void
596 vect_model_load_cost (stmt_vec_info stmt_info, int ncopies, slp_tree slp_node)
597                  
598 {
599   int group_size;
600   int alignment_support_cheme;
601   tree first_stmt;
602   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info), *first_dr;
603   int inside_cost = 0, outside_cost = 0;
604
605   /* Strided accesses?  */
606   first_stmt = DR_GROUP_FIRST_DR (stmt_info);
607   if (first_stmt && !slp_node)
608     {
609       group_size = vect_cost_strided_group_size (stmt_info);
610       first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt));
611     }
612   /* Not a strided access.  */
613   else
614     {
615       group_size = 1;
616       first_dr = dr;
617     }
618
619   alignment_support_cheme = vect_supportable_dr_alignment (first_dr);
620
621   /* Is this an access in a group of loads providing strided access?  
622      If so, add in the cost of the permutes.  */
623   if (group_size > 1) 
624     {
625       /* Uses an even and odd extract operations for each needed permute.  */
626       inside_cost = ncopies * exact_log2(group_size) * group_size
627         * TARG_VEC_STMT_COST;
628
629       if (vect_print_dump_info (REPORT_DETAILS))
630         fprintf (vect_dump, "vect_model_load_cost: strided group_size = %d .",
631                  group_size);
632
633     }
634
635   /* The loads themselves.  */
636   switch (alignment_support_cheme)
637     {
638     case dr_aligned:
639       {
640         inside_cost += ncopies * TARG_VEC_LOAD_COST;
641
642         if (vect_print_dump_info (REPORT_DETAILS))
643           fprintf (vect_dump, "vect_model_load_cost: aligned.");
644
645         break;
646       }
647     case dr_unaligned_supported:
648       {
649         /* Here, we assign an additional cost for the unaligned load.  */
650         inside_cost += ncopies * TARG_VEC_UNALIGNED_LOAD_COST;
651
652         if (vect_print_dump_info (REPORT_DETAILS))
653           fprintf (vect_dump, "vect_model_load_cost: unaligned supported by "
654                    "hardware.");
655
656         break;
657       }
658     case dr_explicit_realign:
659       {
660         inside_cost += ncopies * (2*TARG_VEC_LOAD_COST + TARG_VEC_STMT_COST);
661
662         /* FIXME: If the misalignment remains fixed across the iterations of
663            the containing loop, the following cost should be added to the
664            outside costs.  */
665         if (targetm.vectorize.builtin_mask_for_load)
666           inside_cost += TARG_VEC_STMT_COST;
667
668         break;
669       }
670     case dr_explicit_realign_optimized:
671       {
672         if (vect_print_dump_info (REPORT_DETAILS))
673           fprintf (vect_dump, "vect_model_load_cost: unaligned software "
674                    "pipelined.");
675
676         /* Unaligned software pipeline has a load of an address, an initial
677            load, and possibly a mask operation to "prime" the loop. However,
678            if this is an access in a group of loads, which provide strided
679            access, then the above cost should only be considered for one
680            access in the group. Inside the loop, there is a load op
681            and a realignment op.  */
682
683         if ((!DR_GROUP_FIRST_DR (stmt_info)) || group_size > 1 || slp_node)
684           {
685             outside_cost = 2*TARG_VEC_STMT_COST;
686             if (targetm.vectorize.builtin_mask_for_load)
687               outside_cost += TARG_VEC_STMT_COST;
688           }
689
690         inside_cost += ncopies * (TARG_VEC_LOAD_COST + TARG_VEC_STMT_COST);
691
692         break;
693       }
694
695     default:
696       gcc_unreachable ();
697     }
698   
699   if (vect_print_dump_info (REPORT_DETAILS))
700     fprintf (vect_dump, "vect_model_load_cost: inside_cost = %d, "
701              "outside_cost = %d .", inside_cost, outside_cost);
702
703   /* Set the costs either in STMT_INFO or SLP_NODE (if exists).  */
704   stmt_vinfo_set_inside_of_loop_cost (stmt_info, slp_node, inside_cost);
705   stmt_vinfo_set_outside_of_loop_cost (stmt_info, slp_node, outside_cost);
706 }
707
708
709 /* Function vect_get_new_vect_var.
710
711    Returns a name for a new variable. The current naming scheme appends the 
712    prefix "vect_" or "vect_p" (depending on the value of VAR_KIND) to 
713    the name of vectorizer generated variables, and appends that to NAME if 
714    provided.  */
715
716 static tree
717 vect_get_new_vect_var (tree type, enum vect_var_kind var_kind, const char *name)
718 {
719   const char *prefix;
720   tree new_vect_var;
721
722   switch (var_kind)
723   {
724   case vect_simple_var:
725     prefix = "vect_";
726     break;
727   case vect_scalar_var:
728     prefix = "stmp_";
729     break;
730   case vect_pointer_var:
731     prefix = "vect_p";
732     break;
733   default:
734     gcc_unreachable ();
735   }
736
737   if (name)
738     {
739       char* tmp = concat (prefix, name, NULL);
740       new_vect_var = create_tmp_var (type, tmp);
741       free (tmp);
742     }
743   else
744     new_vect_var = create_tmp_var (type, prefix);
745
746   /* Mark vector typed variable as a gimple register variable.  */
747   if (TREE_CODE (type) == VECTOR_TYPE)
748     DECL_GIMPLE_REG_P (new_vect_var) = true;
749
750   return new_vect_var;
751 }
752
753
754 /* Function vect_create_addr_base_for_vector_ref.
755
756    Create an expression that computes the address of the first memory location
757    that will be accessed for a data reference.
758
759    Input:
760    STMT: The statement containing the data reference.
761    NEW_STMT_LIST: Must be initialized to NULL_TREE or a statement list.
762    OFFSET: Optional. If supplied, it is be added to the initial address.
763    LOOP:    Specify relative to which loop-nest should the address be computed.
764             For example, when the dataref is in an inner-loop nested in an
765             outer-loop that is now being vectorized, LOOP can be either the
766             outer-loop, or the inner-loop. The first memory location accessed
767             by the following dataref ('in' points to short):
768
769                 for (i=0; i<N; i++)
770                    for (j=0; j<M; j++)
771                      s += in[i+j]
772
773             is as follows:
774             if LOOP=i_loop:     &in             (relative to i_loop)
775             if LOOP=j_loop:     &in+i*2B        (relative to j_loop)
776
777    Output:
778    1. Return an SSA_NAME whose value is the address of the memory location of 
779       the first vector of the data reference.
780    2. If new_stmt_list is not NULL_TREE after return then the caller must insert
781       these statement(s) which define the returned SSA_NAME.
782
783    FORNOW: We are only handling array accesses with step 1.  */
784
785 static tree
786 vect_create_addr_base_for_vector_ref (tree stmt,
787                                       tree *new_stmt_list,
788                                       tree offset,
789                                       struct loop *loop)
790 {
791   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
792   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
793   struct loop *containing_loop = (bb_for_stmt (stmt))->loop_father;
794   tree data_ref_base = unshare_expr (DR_BASE_ADDRESS (dr));
795   tree base_name;
796   tree data_ref_base_var;
797   tree new_base_stmt;
798   tree vec_stmt;
799   tree addr_base, addr_expr;
800   tree dest, new_stmt;
801   tree base_offset = unshare_expr (DR_OFFSET (dr));
802   tree init = unshare_expr (DR_INIT (dr));
803   tree vect_ptr_type, addr_expr2;
804   tree step = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)));
805
806   gcc_assert (loop);
807   if (loop != containing_loop)
808     {
809       loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
810       struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
811
812       gcc_assert (nested_in_vect_loop_p (loop, stmt));
813
814       data_ref_base = unshare_expr (STMT_VINFO_DR_BASE_ADDRESS (stmt_info));
815       base_offset = unshare_expr (STMT_VINFO_DR_OFFSET (stmt_info));
816       init = unshare_expr (STMT_VINFO_DR_INIT (stmt_info));
817     }
818
819   /* Create data_ref_base */
820   base_name = build_fold_indirect_ref (data_ref_base);
821   data_ref_base_var = create_tmp_var (TREE_TYPE (data_ref_base), "batmp");
822   add_referenced_var (data_ref_base_var);
823   data_ref_base = force_gimple_operand (data_ref_base, &new_base_stmt,
824                                         true, data_ref_base_var);
825   append_to_statement_list_force(new_base_stmt, new_stmt_list);
826
827   /* Create base_offset */
828   base_offset = size_binop (PLUS_EXPR, base_offset, init);
829   base_offset = fold_convert (sizetype, base_offset);
830   dest = create_tmp_var (TREE_TYPE (base_offset), "base_off");
831   add_referenced_var (dest);
832   base_offset = force_gimple_operand (base_offset, &new_stmt, true, dest); 
833   append_to_statement_list_force (new_stmt, new_stmt_list);
834
835   if (offset)
836     {
837       tree tmp = create_tmp_var (sizetype, "offset");
838
839       add_referenced_var (tmp);
840       offset = fold_build2 (MULT_EXPR, TREE_TYPE (offset), offset, step);
841       base_offset = fold_build2 (PLUS_EXPR, TREE_TYPE (base_offset),
842                                  base_offset, offset);
843       base_offset = force_gimple_operand (base_offset, &new_stmt, false, tmp);
844       append_to_statement_list_force (new_stmt, new_stmt_list);
845     }
846   
847   /* base + base_offset */
848   addr_base = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (data_ref_base), 
849                            data_ref_base, base_offset);
850
851   vect_ptr_type = build_pointer_type (STMT_VINFO_VECTYPE (stmt_info));
852
853   /* addr_expr = addr_base */
854   addr_expr = vect_get_new_vect_var (vect_ptr_type, vect_pointer_var,
855                                      get_name (base_name));
856   add_referenced_var (addr_expr);
857   vec_stmt = fold_convert (vect_ptr_type, addr_base);
858   addr_expr2 = vect_get_new_vect_var (vect_ptr_type, vect_pointer_var,
859                                      get_name (base_name));
860   add_referenced_var (addr_expr2);
861   vec_stmt = force_gimple_operand (vec_stmt, &new_stmt, false, addr_expr2);
862   append_to_statement_list_force (new_stmt, new_stmt_list);
863
864   if (vect_print_dump_info (REPORT_DETAILS))
865     {
866       fprintf (vect_dump, "created ");
867       print_generic_expr (vect_dump, vec_stmt, TDF_SLIM);
868     }
869   return vec_stmt;
870 }
871
872
873 /* Function vect_create_data_ref_ptr.
874
875    Create a new pointer to vector type (vp), that points to the first location
876    accessed in the loop by STMT, along with the def-use update chain to 
877    appropriately advance the pointer through the loop iterations. Also set
878    aliasing information for the pointer.  This vector pointer is used by the
879    callers to this function to create a memory reference expression for vector
880    load/store access.
881
882    Input:
883    1. STMT: a stmt that references memory. Expected to be of the form
884          GIMPLE_MODIFY_STMT <name, data-ref> or
885          GIMPLE_MODIFY_STMT <data-ref, name>.
886    2. AT_LOOP: the loop where the vector memref is to be created.
887    3. OFFSET (optional): an offset to be added to the initial address accessed
888         by the data-ref in STMT.
889    4. ONLY_INIT: indicate if vp is to be updated in the loop, or remain
890         pointing to the initial address.
891    5. TYPE: if not NULL indicates the required type of the data-ref
892
893    Output:
894    1. Declare a new ptr to vector_type, and have it point to the base of the
895       data reference (initial addressed accessed by the data reference).
896       For example, for vector of type V8HI, the following code is generated:
897
898       v8hi *vp;
899       vp = (v8hi *)initial_address;
900
901       if OFFSET is not supplied:
902          initial_address = &a[init];
903       if OFFSET is supplied:
904          initial_address = &a[init + OFFSET];
905
906       Return the initial_address in INITIAL_ADDRESS.
907
908    2. If ONLY_INIT is true, just return the initial pointer.  Otherwise, also
909       update the pointer in each iteration of the loop.  
910
911       Return the increment stmt that updates the pointer in PTR_INCR.
912
913    3. Set INV_P to true if the access pattern of the data reference in the 
914       vectorized loop is invariant. Set it to false otherwise.
915
916    4. Return the pointer.  */
917
918 static tree
919 vect_create_data_ref_ptr (tree stmt, struct loop *at_loop,
920                           tree offset, tree *initial_address, tree *ptr_incr,
921                           bool only_init, tree type, bool *inv_p)
922 {
923   tree base_name;
924   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
925   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
926   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
927   bool nested_in_vect_loop = nested_in_vect_loop_p (loop, stmt);
928   struct loop *containing_loop = (bb_for_stmt (stmt))->loop_father;
929   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
930   tree vect_ptr_type;
931   tree vect_ptr;
932   tree tag;
933   tree new_temp;
934   tree vec_stmt;
935   tree new_stmt_list = NULL_TREE;
936   edge pe;
937   basic_block new_bb;
938   tree vect_ptr_init;
939   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
940   tree vptr;
941   block_stmt_iterator incr_bsi;
942   bool insert_after;
943   tree indx_before_incr, indx_after_incr;
944   tree incr;
945   tree step;
946
947   /* Check the step (evolution) of the load in LOOP, and record
948      whether it's invariant.  */
949   if (nested_in_vect_loop)
950     step = STMT_VINFO_DR_STEP (stmt_info);
951   else
952     step = DR_STEP (STMT_VINFO_DATA_REF (stmt_info));
953     
954   if (tree_int_cst_compare (step, size_zero_node) == 0)
955     *inv_p = true;
956   else
957     *inv_p = false;
958
959   /* Create an expression for the first address accessed by this load
960      in LOOP.  */ 
961   base_name =  build_fold_indirect_ref (unshare_expr (DR_BASE_ADDRESS (dr)));
962
963   if (vect_print_dump_info (REPORT_DETAILS))
964     {
965       tree data_ref_base = base_name;
966       fprintf (vect_dump, "create vector-pointer variable to type: ");
967       print_generic_expr (vect_dump, vectype, TDF_SLIM);
968       if (TREE_CODE (data_ref_base) == VAR_DECL)
969         fprintf (vect_dump, "  vectorizing a one dimensional array ref: ");
970       else if (TREE_CODE (data_ref_base) == ARRAY_REF)
971         fprintf (vect_dump, "  vectorizing a multidimensional array ref: ");
972       else if (TREE_CODE (data_ref_base) == COMPONENT_REF)
973         fprintf (vect_dump, "  vectorizing a record based array ref: ");
974       else if (TREE_CODE (data_ref_base) == SSA_NAME)
975         fprintf (vect_dump, "  vectorizing a pointer ref: ");
976       print_generic_expr (vect_dump, base_name, TDF_SLIM);
977     }
978
979   /** (1) Create the new vector-pointer variable:  **/
980   if (type)  
981     vect_ptr_type = build_pointer_type (type);
982   else
983     vect_ptr_type = build_pointer_type (vectype);
984   vect_ptr = vect_get_new_vect_var (vect_ptr_type, vect_pointer_var,
985                                     get_name (base_name));
986   add_referenced_var (vect_ptr);
987
988   /** (2) Add aliasing information to the new vector-pointer:
989           (The points-to info (DR_PTR_INFO) may be defined later.)  **/
990   
991   tag = DR_SYMBOL_TAG (dr);
992   gcc_assert (tag);
993
994   /* If tag is a variable (and NOT_A_TAG) than a new symbol memory
995      tag must be created with tag added to its may alias list.  */
996   if (!MTAG_P (tag))
997     new_type_alias (vect_ptr, tag, DR_REF (dr));
998   else
999     set_symbol_mem_tag (vect_ptr, tag);
1000
1001   var_ann (vect_ptr)->subvars = DR_SUBVARS (dr);
1002
1003   /** Note: If the dataref is in an inner-loop nested in LOOP, and we are
1004       vectorizing LOOP (i.e. outer-loop vectorization), we need to create two
1005       def-use update cycles for the pointer: One relative to the outer-loop
1006       (LOOP), which is what steps (3) and (4) below do. The other is relative
1007       to the inner-loop (which is the inner-most loop containing the dataref),
1008       and this is done be step (5) below. 
1009
1010       When vectorizing inner-most loops, the vectorized loop (LOOP) is also the
1011       inner-most loop, and so steps (3),(4) work the same, and step (5) is
1012       redundant.  Steps (3),(4) create the following:
1013
1014         vp0 = &base_addr;
1015         LOOP:   vp1 = phi(vp0,vp2)
1016                 ...  
1017                 ...
1018                 vp2 = vp1 + step
1019                 goto LOOP
1020                         
1021       If there is an inner-loop nested in loop, then step (5) will also be
1022       applied, and an additional update in the inner-loop will be created:
1023
1024         vp0 = &base_addr;
1025         LOOP:   vp1 = phi(vp0,vp2)
1026                 ...
1027         inner:     vp3 = phi(vp1,vp4)
1028                    vp4 = vp3 + inner_step
1029                    if () goto inner
1030                 ...
1031                 vp2 = vp1 + step
1032                 if () goto LOOP   */
1033
1034   /** (3) Calculate the initial address the vector-pointer, and set
1035           the vector-pointer to point to it before the loop:  **/
1036
1037   /* Create: (&(base[init_val+offset]) in the loop preheader.  */
1038
1039   new_temp = vect_create_addr_base_for_vector_ref (stmt, &new_stmt_list,
1040                                                    offset, loop);
1041   pe = loop_preheader_edge (loop);
1042   new_bb = bsi_insert_on_edge_immediate (pe, new_stmt_list);
1043   gcc_assert (!new_bb);
1044   *initial_address = new_temp;
1045
1046   /* Create: p = (vectype *) initial_base  */
1047   vec_stmt = fold_convert (vect_ptr_type, new_temp);
1048   vec_stmt = build_gimple_modify_stmt (vect_ptr, vec_stmt);
1049   vect_ptr_init = make_ssa_name (vect_ptr, vec_stmt);
1050   GIMPLE_STMT_OPERAND (vec_stmt, 0) = vect_ptr_init;
1051   new_bb = bsi_insert_on_edge_immediate (pe, vec_stmt);
1052   gcc_assert (!new_bb);
1053
1054
1055   /** (4) Handle the updating of the vector-pointer inside the loop.
1056           This is needed when ONLY_INIT is false, and also when AT_LOOP
1057           is the inner-loop nested in LOOP (during outer-loop vectorization).
1058    **/
1059
1060   if (only_init && at_loop == loop) /* No update in loop is required.  */
1061     {
1062       /* Copy the points-to information if it exists. */
1063       if (DR_PTR_INFO (dr))
1064         duplicate_ssa_name_ptr_info (vect_ptr_init, DR_PTR_INFO (dr));
1065       vptr = vect_ptr_init;
1066     }
1067   else
1068     {
1069       /* The step of the vector pointer is the Vector Size.  */
1070       tree step = TYPE_SIZE_UNIT (vectype);
1071       /* One exception to the above is when the scalar step of the load in 
1072          LOOP is zero. In this case the step here is also zero.  */
1073       if (*inv_p)
1074         step = size_zero_node;
1075
1076       standard_iv_increment_position (loop, &incr_bsi, &insert_after);
1077
1078       create_iv (vect_ptr_init,
1079                  fold_convert (vect_ptr_type, step),
1080                  NULL_TREE, loop, &incr_bsi, insert_after,
1081                  &indx_before_incr, &indx_after_incr);
1082       incr = bsi_stmt (incr_bsi);
1083       set_stmt_info (stmt_ann (incr),
1084                      new_stmt_vec_info (incr, loop_vinfo));
1085
1086       /* Copy the points-to information if it exists. */
1087       if (DR_PTR_INFO (dr))
1088         {
1089           duplicate_ssa_name_ptr_info (indx_before_incr, DR_PTR_INFO (dr));
1090           duplicate_ssa_name_ptr_info (indx_after_incr, DR_PTR_INFO (dr));
1091         }
1092       merge_alias_info (vect_ptr_init, indx_before_incr);
1093       merge_alias_info (vect_ptr_init, indx_after_incr);
1094       if (ptr_incr)
1095         *ptr_incr = incr;
1096
1097       vptr = indx_before_incr;
1098     }
1099
1100   if (!nested_in_vect_loop || only_init)
1101     return vptr;
1102
1103
1104   /** (5) Handle the updating of the vector-pointer inside the inner-loop
1105           nested in LOOP, if exists: **/
1106
1107   gcc_assert (nested_in_vect_loop);
1108   if (!only_init)
1109     {
1110       standard_iv_increment_position (containing_loop, &incr_bsi, 
1111                                       &insert_after);
1112       create_iv (vptr, fold_convert (vect_ptr_type, DR_STEP (dr)), NULL_TREE, 
1113                  containing_loop, &incr_bsi, insert_after, &indx_before_incr, 
1114                  &indx_after_incr);
1115       incr = bsi_stmt (incr_bsi);
1116       set_stmt_info (stmt_ann (incr), new_stmt_vec_info (incr, loop_vinfo));
1117
1118       /* Copy the points-to information if it exists. */
1119       if (DR_PTR_INFO (dr))
1120         {
1121           duplicate_ssa_name_ptr_info (indx_before_incr, DR_PTR_INFO (dr));
1122           duplicate_ssa_name_ptr_info (indx_after_incr, DR_PTR_INFO (dr));
1123         }
1124       merge_alias_info (vect_ptr_init, indx_before_incr);
1125       merge_alias_info (vect_ptr_init, indx_after_incr);
1126       if (ptr_incr)
1127         *ptr_incr = incr;
1128
1129       return indx_before_incr; 
1130     }
1131   else
1132     gcc_unreachable ();
1133 }
1134
1135
1136 /* Function bump_vector_ptr
1137
1138    Increment a pointer (to a vector type) by vector-size. If requested,
1139    i.e. if PTR-INCR is given, then also connect the new increment stmt 
1140    to the existing def-use update-chain of the pointer, by modifying
1141    the PTR_INCR as illustrated below:
1142
1143    The pointer def-use update-chain before this function:
1144                         DATAREF_PTR = phi (p_0, p_2)
1145                         ....
1146         PTR_INCR:       p_2 = DATAREF_PTR + step 
1147
1148    The pointer def-use update-chain after this function:
1149                         DATAREF_PTR = phi (p_0, p_2)
1150                         ....
1151                         NEW_DATAREF_PTR = DATAREF_PTR + BUMP
1152                         ....
1153         PTR_INCR:       p_2 = NEW_DATAREF_PTR + step
1154
1155    Input:
1156    DATAREF_PTR - ssa_name of a pointer (to vector type) that is being updated 
1157                  in the loop.
1158    PTR_INCR - optional. The stmt that updates the pointer in each iteration of 
1159               the loop.  The increment amount across iterations is expected
1160               to be vector_size.      
1161    BSI - location where the new update stmt is to be placed.
1162    STMT - the original scalar memory-access stmt that is being vectorized.
1163    BUMP - optional. The offset by which to bump the pointer. If not given,
1164           the offset is assumed to be vector_size.
1165
1166    Output: Return NEW_DATAREF_PTR as illustrated above.
1167    
1168 */
1169
1170 static tree
1171 bump_vector_ptr (tree dataref_ptr, tree ptr_incr, block_stmt_iterator *bsi,
1172                  tree stmt, tree bump)
1173 {
1174   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1175   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
1176   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1177   tree vptr_type = TREE_TYPE (dataref_ptr);
1178   tree ptr_var = SSA_NAME_VAR (dataref_ptr);
1179   tree update = TYPE_SIZE_UNIT (vectype);
1180   tree incr_stmt;
1181   ssa_op_iter iter;
1182   use_operand_p use_p;
1183   tree new_dataref_ptr;
1184
1185   if (bump)
1186     update = bump;
1187     
1188   incr_stmt = build_gimple_modify_stmt (ptr_var,
1189                                         build2 (POINTER_PLUS_EXPR, vptr_type,
1190                                                 dataref_ptr, update));
1191   new_dataref_ptr = make_ssa_name (ptr_var, incr_stmt);
1192   GIMPLE_STMT_OPERAND (incr_stmt, 0) = new_dataref_ptr;
1193   vect_finish_stmt_generation (stmt, incr_stmt, bsi);
1194
1195   /* Copy the points-to information if it exists. */
1196   if (DR_PTR_INFO (dr))
1197     duplicate_ssa_name_ptr_info (new_dataref_ptr, DR_PTR_INFO (dr));
1198   merge_alias_info (new_dataref_ptr, dataref_ptr);
1199
1200   if (!ptr_incr)
1201     return new_dataref_ptr;
1202
1203   /* Update the vector-pointer's cross-iteration increment.  */
1204   FOR_EACH_SSA_USE_OPERAND (use_p, ptr_incr, iter, SSA_OP_USE)
1205     {
1206       tree use = USE_FROM_PTR (use_p);
1207
1208       if (use == dataref_ptr)
1209         SET_USE (use_p, new_dataref_ptr);
1210       else
1211         gcc_assert (tree_int_cst_compare (use, update) == 0);
1212     }
1213
1214   return new_dataref_ptr;
1215 }
1216
1217
1218 /* Function vect_create_destination_var.
1219
1220    Create a new temporary of type VECTYPE.  */
1221
1222 static tree
1223 vect_create_destination_var (tree scalar_dest, tree vectype)
1224 {
1225   tree vec_dest;
1226   const char *new_name;
1227   tree type;
1228   enum vect_var_kind kind;
1229
1230   kind = vectype ? vect_simple_var : vect_scalar_var;
1231   type = vectype ? vectype : TREE_TYPE (scalar_dest);
1232
1233   gcc_assert (TREE_CODE (scalar_dest) == SSA_NAME);
1234
1235   new_name = get_name (scalar_dest);
1236   if (!new_name)
1237     new_name = "var_";
1238   vec_dest = vect_get_new_vect_var (type, kind, new_name);
1239   add_referenced_var (vec_dest);
1240
1241   return vec_dest;
1242 }
1243
1244
1245 /* Function vect_init_vector.
1246
1247    Insert a new stmt (INIT_STMT) that initializes a new vector variable with
1248    the vector elements of VECTOR_VAR. Place the initialization at BSI if it
1249    is not NULL. Otherwise, place the initialization at the loop preheader.
1250    Return the DEF of INIT_STMT. 
1251    It will be used in the vectorization of STMT.  */
1252
1253 static tree
1254 vect_init_vector (tree stmt, tree vector_var, tree vector_type,
1255                   block_stmt_iterator *bsi)
1256 {
1257   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
1258   tree new_var;
1259   tree init_stmt;
1260   tree vec_oprnd;
1261   edge pe;
1262   tree new_temp;
1263   basic_block new_bb;
1264  
1265   new_var = vect_get_new_vect_var (vector_type, vect_simple_var, "cst_");
1266   add_referenced_var (new_var); 
1267   init_stmt = build_gimple_modify_stmt (new_var, vector_var);
1268   new_temp = make_ssa_name (new_var, init_stmt);
1269   GIMPLE_STMT_OPERAND (init_stmt, 0) = new_temp;
1270
1271   if (bsi)
1272     vect_finish_stmt_generation (stmt, init_stmt, bsi);
1273   else
1274     {
1275       loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
1276       struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1277
1278       if (nested_in_vect_loop_p (loop, stmt))
1279         loop = loop->inner;
1280       pe = loop_preheader_edge (loop);
1281       new_bb = bsi_insert_on_edge_immediate (pe, init_stmt);
1282       gcc_assert (!new_bb);
1283     }
1284
1285   if (vect_print_dump_info (REPORT_DETAILS))
1286     {
1287       fprintf (vect_dump, "created new init_stmt: ");
1288       print_generic_expr (vect_dump, init_stmt, TDF_SLIM);
1289     }
1290
1291   vec_oprnd = GIMPLE_STMT_OPERAND (init_stmt, 0);
1292   return vec_oprnd;
1293 }
1294
1295
1296 /* For constant and loop invariant defs of SLP_NODE this function returns 
1297    (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.  
1298    OP_NUM determines if we gather defs for operand 0 or operand 1 of the scalar
1299    stmts.  */
1300
1301 static void
1302 vect_get_constant_vectors (slp_tree slp_node, VEC(tree,heap) **vec_oprnds,
1303                            unsigned int op_num)
1304 {
1305   VEC (tree, heap) *stmts = SLP_TREE_SCALAR_STMTS (slp_node);
1306   tree stmt = VEC_index (tree, stmts, 0);
1307   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
1308   tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
1309   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
1310   tree vec_cst;
1311   tree t = NULL_TREE;
1312   int j, number_of_places_left_in_vector;
1313   tree vector_type;
1314   tree op, vop, operation;
1315   int group_size = VEC_length (tree, stmts);
1316   unsigned int vec_num, i;
1317   int number_of_copies = 1;
1318   bool is_store = false;
1319   unsigned int number_of_vectors = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
1320   VEC (tree, heap) *voprnds = VEC_alloc (tree, heap, number_of_vectors);
1321   bool constant_p;
1322
1323   if (STMT_VINFO_DATA_REF (stmt_vinfo))
1324     is_store = true;
1325
1326   /* NUMBER_OF_COPIES is the number of times we need to use the same values in
1327      created vectors. It is greater than 1 if unrolling is performed. 
1328
1329      For example, we have two scalar operands, s1 and s2 (e.g., group of
1330      strided accesses of size two), while NUINTS is four (i.e., four scalars
1331      of this type can be packed in a vector). The output vector will contain
1332      two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
1333      will be 2).
1334
1335      If GROUP_SIZE > NUNITS, the scalars will be split into several vectors 
1336      containing the operands.
1337
1338      For example, NUINTS is four as before, and the group size is 8 
1339      (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
1340      {s5, s6, s7, s8}.  */
1341     
1342   number_of_copies = least_common_multiple (nunits, group_size) / group_size;
1343
1344   number_of_places_left_in_vector = nunits;
1345   constant_p = true;
1346   for (j = 0; j < number_of_copies; j++)
1347     {
1348       for (i = group_size - 1; VEC_iterate (tree, stmts, i, stmt); i--)
1349         {
1350           operation = GIMPLE_STMT_OPERAND (stmt, 1);
1351           if (is_store)
1352             op = operation;
1353           else
1354             op = TREE_OPERAND (operation, op_num);
1355           if (!CONSTANT_CLASS_P (op))
1356             constant_p = false;
1357
1358           /* Create 'vect_ = {op0,op1,...,opn}'.  */
1359           t = tree_cons (NULL_TREE, op, t);
1360
1361           number_of_places_left_in_vector--;
1362
1363           if (number_of_places_left_in_vector == 0)
1364             {
1365               number_of_places_left_in_vector = nunits;
1366
1367               vector_type = get_vectype_for_scalar_type (TREE_TYPE (op));
1368               gcc_assert (vector_type);
1369               if (constant_p)
1370                 vec_cst = build_vector (vector_type, t);
1371               else
1372                 vec_cst = build_constructor_from_list (vector_type, t);
1373               constant_p = true;
1374               VEC_quick_push (tree, voprnds,
1375                               vect_init_vector (stmt, vec_cst, vector_type,
1376                                                 NULL));
1377               t = NULL_TREE;
1378             }
1379         }
1380     }
1381
1382   /* Since the vectors are created in the reverse order, we should invert 
1383      them.  */
1384   vec_num = VEC_length (tree, voprnds);
1385   for (j = vec_num - 1; j >= 0; j--)
1386     {
1387       vop = VEC_index (tree, voprnds, j);
1388       VEC_quick_push (tree, *vec_oprnds, vop);
1389     }
1390
1391   VEC_free (tree, heap, voprnds);
1392
1393   /* In case that VF is greater than the unrolling factor needed for the SLP
1394      group of stmts, NUMBER_OF_VECTORS to be created is greater than 
1395      NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have 
1396      to replicate the vectors.  */
1397   while (number_of_vectors > VEC_length (tree, *vec_oprnds))
1398     {
1399       for (i = 0; VEC_iterate (tree, *vec_oprnds, i, vop) && i < vec_num; i++)
1400         VEC_quick_push (tree, *vec_oprnds, vop);
1401     }
1402 }
1403
1404
1405 /* Get vectorized definitions from SLP_NODE that contains corresponding
1406    vectorized def-stmts.  */
1407  
1408 static void
1409 vect_get_slp_vect_defs (slp_tree slp_node, VEC (tree,heap) **vec_oprnds)
1410 {
1411   tree vec_oprnd;
1412   tree vec_def_stmt;
1413   unsigned int i;
1414
1415   gcc_assert (SLP_TREE_VEC_STMTS (slp_node));
1416
1417   for (i = 0; 
1418        VEC_iterate (tree, SLP_TREE_VEC_STMTS (slp_node), i, vec_def_stmt); 
1419        i++)
1420     {
1421       gcc_assert (vec_def_stmt);
1422       vec_oprnd = GIMPLE_STMT_OPERAND (vec_def_stmt, 0);
1423       VEC_quick_push (tree, *vec_oprnds, vec_oprnd);
1424     }
1425 }
1426
1427
1428 /* Get vectorized definitions for SLP_NODE. 
1429    If the scalar definitions are loop invariants or constants, collect them and 
1430    call vect_get_constant_vectors() to create vector stmts.
1431    Otherwise, the def-stmts must be already vectorized and the vectorized stmts
1432    must be stored in the LEFT/RIGHT node of SLP_NODE, and we call
1433    vect_get_slp_vect_defs() to retrieve them.  
1434    If VEC_OPRNDS1 is NULL, don't get vector defs for the second operand (from
1435    the right node. This is used when the second operand must remain scalar.  */
1436  
1437 static void
1438 vect_get_slp_defs (slp_tree slp_node, VEC (tree,heap) **vec_oprnds0,
1439                    VEC (tree,heap) **vec_oprnds1)
1440 {
1441   tree operation, first_stmt;
1442
1443   /* Allocate memory for vectorized defs.  */
1444   *vec_oprnds0 = VEC_alloc (tree, heap, 
1445                             SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node));
1446
1447   /* SLP_NODE corresponds either to a group of stores or to a group of 
1448      unary/binary operations. We don't call this function for loads.  */
1449   if (SLP_TREE_LEFT (slp_node)) 
1450     /* The defs are already vectorized.  */ 
1451     vect_get_slp_vect_defs (SLP_TREE_LEFT (slp_node), vec_oprnds0);
1452   else
1453     /* Build vectors from scalar defs.  */
1454     vect_get_constant_vectors (slp_node, vec_oprnds0, 0);
1455
1456   first_stmt = VEC_index (tree, SLP_TREE_SCALAR_STMTS (slp_node), 0);
1457   if (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt)))
1458     /* Since we don't call this function with loads, this is a group of 
1459        stores.  */
1460     return;
1461
1462   operation = GIMPLE_STMT_OPERAND (first_stmt, 1);
1463   if (TREE_OPERAND_LENGTH (operation) == unary_op || !vec_oprnds1)
1464     return;
1465
1466   *vec_oprnds1 = VEC_alloc (tree, heap, 
1467                             SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node));
1468
1469   if (SLP_TREE_RIGHT (slp_node))
1470     /* The defs are already vectorized.  */ 
1471     vect_get_slp_vect_defs (SLP_TREE_RIGHT (slp_node), vec_oprnds1);
1472   else
1473     /* Build vectors from scalar defs.  */
1474     vect_get_constant_vectors (slp_node, vec_oprnds1, 1);
1475 }
1476
1477
1478 /* Function get_initial_def_for_induction
1479
1480    Input:
1481    STMT - a stmt that performs an induction operation in the loop.
1482    IV_PHI - the initial value of the induction variable
1483
1484    Output:
1485    Return a vector variable, initialized with the first VF values of
1486    the induction variable. E.g., for an iv with IV_PHI='X' and
1487    evolution S, for a vector of 4 units, we want to return: 
1488    [X, X + S, X + 2*S, X + 3*S].  */
1489
1490 static tree
1491 get_initial_def_for_induction (tree iv_phi)
1492 {
1493   stmt_vec_info stmt_vinfo = vinfo_for_stmt (iv_phi);
1494   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
1495   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1496   tree scalar_type = TREE_TYPE (PHI_RESULT_TREE (iv_phi));
1497   tree vectype; 
1498   int nunits;
1499   edge pe = loop_preheader_edge (loop);
1500   struct loop *iv_loop;
1501   basic_block new_bb;
1502   tree vec, vec_init, vec_step, t;
1503   tree access_fn;
1504   tree new_var;
1505   tree new_name;
1506   tree init_stmt;
1507   tree induction_phi, induc_def, new_stmt, vec_def, vec_dest;
1508   tree init_expr, step_expr;
1509   int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1510   int i;
1511   bool ok;
1512   int ncopies;
1513   tree expr;
1514   stmt_vec_info phi_info = vinfo_for_stmt (iv_phi);
1515   bool nested_in_vect_loop = false;
1516   tree stmts;
1517   imm_use_iterator imm_iter;
1518   use_operand_p use_p;
1519   tree exit_phi;
1520   edge latch_e;
1521   tree loop_arg;
1522   block_stmt_iterator si;
1523   basic_block bb = bb_for_stmt (iv_phi);
1524
1525   vectype = get_vectype_for_scalar_type (scalar_type);
1526   gcc_assert (vectype);
1527   nunits = TYPE_VECTOR_SUBPARTS (vectype);
1528   ncopies = vf / nunits;
1529
1530   gcc_assert (phi_info);
1531   gcc_assert (ncopies >= 1);
1532
1533   /* Find the first insertion point in the BB.  */
1534   si = bsi_after_labels (bb);
1535
1536   if (INTEGRAL_TYPE_P (scalar_type))
1537     step_expr = build_int_cst (scalar_type, 0);
1538   else
1539     step_expr = build_real (scalar_type, dconst0);
1540
1541   /* Is phi in an inner-loop, while vectorizing an enclosing outer-loop?  */
1542   if (nested_in_vect_loop_p (loop, iv_phi))
1543     {
1544       nested_in_vect_loop = true;
1545       iv_loop = loop->inner;
1546     }
1547   else
1548     iv_loop = loop;
1549   gcc_assert (iv_loop == (bb_for_stmt (iv_phi))->loop_father);
1550
1551   latch_e = loop_latch_edge (iv_loop);
1552   loop_arg = PHI_ARG_DEF_FROM_EDGE (iv_phi, latch_e);
1553
1554   access_fn = analyze_scalar_evolution (iv_loop, PHI_RESULT (iv_phi));
1555   gcc_assert (access_fn);
1556   ok = vect_is_simple_iv_evolution (iv_loop->num, access_fn,
1557                                   &init_expr, &step_expr);
1558   gcc_assert (ok);
1559   pe = loop_preheader_edge (iv_loop);
1560
1561   /* Create the vector that holds the initial_value of the induction.  */
1562   if (nested_in_vect_loop)
1563     {
1564       /* iv_loop is nested in the loop to be vectorized.  init_expr had already
1565          been created during vectorization of previous stmts; We obtain it from
1566          the STMT_VINFO_VEC_STMT of the defining stmt. */
1567       tree iv_def = PHI_ARG_DEF_FROM_EDGE (iv_phi, loop_preheader_edge (iv_loop));
1568       vec_init = vect_get_vec_def_for_operand (iv_def, iv_phi, NULL);
1569     }
1570   else
1571     {
1572       /* iv_loop is the loop to be vectorized. Create:
1573          vec_init = [X, X+S, X+2*S, X+3*S] (S = step_expr, X = init_expr)  */
1574       new_var = vect_get_new_vect_var (scalar_type, vect_scalar_var, "var_");
1575       add_referenced_var (new_var);
1576
1577       new_name = force_gimple_operand (init_expr, &stmts, false, new_var);
1578       if (stmts)
1579         {
1580           new_bb = bsi_insert_on_edge_immediate (pe, stmts);
1581           gcc_assert (!new_bb);
1582         }
1583
1584       t = NULL_TREE;
1585       t = tree_cons (NULL_TREE, init_expr, t);
1586       for (i = 1; i < nunits; i++)
1587         {
1588           tree tmp;
1589
1590           /* Create: new_name_i = new_name + step_expr  */
1591           tmp = fold_build2 (PLUS_EXPR, scalar_type, new_name, step_expr);
1592           init_stmt = build_gimple_modify_stmt (new_var, tmp);
1593           new_name = make_ssa_name (new_var, init_stmt);
1594           GIMPLE_STMT_OPERAND (init_stmt, 0) = new_name;
1595
1596           new_bb = bsi_insert_on_edge_immediate (pe, init_stmt);
1597           gcc_assert (!new_bb);
1598
1599           if (vect_print_dump_info (REPORT_DETAILS))
1600             {
1601               fprintf (vect_dump, "created new init_stmt: ");
1602               print_generic_expr (vect_dump, init_stmt, TDF_SLIM);
1603             }
1604           t = tree_cons (NULL_TREE, new_name, t);
1605         }
1606       /* Create a vector from [new_name_0, new_name_1, ..., new_name_nunits-1]  */
1607       vec = build_constructor_from_list (vectype, nreverse (t));
1608       vec_init = vect_init_vector (iv_phi, vec, vectype, NULL);
1609     }
1610
1611
1612   /* Create the vector that holds the step of the induction.  */
1613   if (nested_in_vect_loop)
1614     /* iv_loop is nested in the loop to be vectorized. Generate:
1615        vec_step = [S, S, S, S]  */
1616     new_name = step_expr;
1617   else
1618     {
1619       /* iv_loop is the loop to be vectorized. Generate:
1620           vec_step = [VF*S, VF*S, VF*S, VF*S]  */
1621       expr = build_int_cst (scalar_type, vf);
1622       new_name = fold_build2 (MULT_EXPR, scalar_type, expr, step_expr);
1623     }
1624
1625   t = NULL_TREE;
1626   for (i = 0; i < nunits; i++)
1627     t = tree_cons (NULL_TREE, unshare_expr (new_name), t);
1628   gcc_assert (CONSTANT_CLASS_P (new_name));
1629   vec = build_vector (vectype, t);
1630   vec_step = vect_init_vector (iv_phi, vec, vectype, NULL);
1631
1632
1633   /* Create the following def-use cycle:
1634      loop prolog:
1635          vec_init = ...
1636          vec_step = ...
1637      loop:
1638          vec_iv = PHI <vec_init, vec_loop>
1639          ...
1640          STMT
1641          ...
1642          vec_loop = vec_iv + vec_step;  */
1643
1644   /* Create the induction-phi that defines the induction-operand.  */
1645   vec_dest = vect_get_new_vect_var (vectype, vect_simple_var, "vec_iv_");
1646   add_referenced_var (vec_dest);
1647   induction_phi = create_phi_node (vec_dest, iv_loop->header);
1648   set_stmt_info (get_stmt_ann (induction_phi),
1649                  new_stmt_vec_info (induction_phi, loop_vinfo));
1650   induc_def = PHI_RESULT (induction_phi);
1651
1652   /* Create the iv update inside the loop  */
1653   new_stmt = build_gimple_modify_stmt (NULL_TREE,
1654                                        build2 (PLUS_EXPR, vectype,
1655                                                induc_def, vec_step));
1656   vec_def = make_ssa_name (vec_dest, new_stmt);
1657   GIMPLE_STMT_OPERAND (new_stmt, 0) = vec_def;
1658   bsi_insert_before (&si, new_stmt, BSI_SAME_STMT);
1659   set_stmt_info (get_stmt_ann (new_stmt),
1660                  new_stmt_vec_info (new_stmt, loop_vinfo));
1661
1662   /* Set the arguments of the phi node:  */
1663   add_phi_arg (induction_phi, vec_init, pe);
1664   add_phi_arg (induction_phi, vec_def, loop_latch_edge (iv_loop));
1665
1666
1667   /* In case that vectorization factor (VF) is bigger than the number
1668      of elements that we can fit in a vectype (nunits), we have to generate
1669      more than one vector stmt - i.e - we need to "unroll" the
1670      vector stmt by a factor VF/nunits.  For more details see documentation
1671      in vectorizable_operation.  */
1672   
1673   if (ncopies > 1)
1674     {
1675       stmt_vec_info prev_stmt_vinfo;
1676       /* FORNOW. This restriction should be relaxed.  */
1677       gcc_assert (!nested_in_vect_loop);
1678
1679       /* Create the vector that holds the step of the induction.  */
1680       expr = build_int_cst (scalar_type, nunits);
1681       new_name = fold_build2 (MULT_EXPR, scalar_type, expr, step_expr);
1682       t = NULL_TREE;
1683       for (i = 0; i < nunits; i++)
1684         t = tree_cons (NULL_TREE, unshare_expr (new_name), t);
1685       gcc_assert (CONSTANT_CLASS_P (new_name));
1686       vec = build_vector (vectype, t);
1687       vec_step = vect_init_vector (iv_phi, vec, vectype, NULL);
1688
1689       vec_def = induc_def;
1690       prev_stmt_vinfo = vinfo_for_stmt (induction_phi);
1691       for (i = 1; i < ncopies; i++)
1692         {
1693           tree tmp;
1694
1695           /* vec_i = vec_prev + vec_step  */
1696           tmp = build2 (PLUS_EXPR, vectype, vec_def, vec_step);
1697           new_stmt = build_gimple_modify_stmt (NULL_TREE, tmp);
1698           vec_def = make_ssa_name (vec_dest, new_stmt);
1699           GIMPLE_STMT_OPERAND (new_stmt, 0) = vec_def;
1700           bsi_insert_before (&si, new_stmt, BSI_SAME_STMT);
1701           set_stmt_info (get_stmt_ann (new_stmt),
1702                          new_stmt_vec_info (new_stmt, loop_vinfo));
1703           STMT_VINFO_RELATED_STMT (prev_stmt_vinfo) = new_stmt;
1704           prev_stmt_vinfo = vinfo_for_stmt (new_stmt); 
1705         }
1706     }
1707
1708   if (nested_in_vect_loop)
1709     {
1710       /* Find the loop-closed exit-phi of the induction, and record
1711          the final vector of induction results:  */
1712       exit_phi = NULL;
1713       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, loop_arg)
1714         {
1715           if (!flow_bb_inside_loop_p (iv_loop, bb_for_stmt (USE_STMT (use_p))))
1716             {
1717               exit_phi = USE_STMT (use_p);
1718               break;
1719             }
1720         }
1721       if (exit_phi) 
1722         {
1723           stmt_vec_info stmt_vinfo = vinfo_for_stmt (exit_phi);
1724           /* FORNOW. Currently not supporting the case that an inner-loop induction
1725              is not used in the outer-loop (i.e. only outside the outer-loop).  */
1726           gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo)
1727                       && !STMT_VINFO_LIVE_P (stmt_vinfo));
1728
1729           STMT_VINFO_VEC_STMT (stmt_vinfo) = new_stmt;
1730           if (vect_print_dump_info (REPORT_DETAILS))
1731             {
1732               fprintf (vect_dump, "vector of inductions after inner-loop:");
1733               print_generic_expr (vect_dump, new_stmt, TDF_SLIM);
1734             }
1735         }
1736     }
1737
1738
1739   if (vect_print_dump_info (REPORT_DETAILS))
1740     {
1741       fprintf (vect_dump, "transform induction: created def-use cycle:");
1742       print_generic_expr (vect_dump, induction_phi, TDF_SLIM);
1743       fprintf (vect_dump, "\n");
1744       print_generic_expr (vect_dump, SSA_NAME_DEF_STMT (vec_def), TDF_SLIM);
1745     }
1746
1747   STMT_VINFO_VEC_STMT (phi_info) = induction_phi;
1748   return induc_def;
1749 }
1750
1751
1752 /* Function vect_get_vec_def_for_operand.
1753
1754    OP is an operand in STMT. This function returns a (vector) def that will be
1755    used in the vectorized stmt for STMT.
1756
1757    In the case that OP is an SSA_NAME which is defined in the loop, then
1758    STMT_VINFO_VEC_STMT of the defining stmt holds the relevant def.
1759
1760    In case OP is an invariant or constant, a new stmt that creates a vector def
1761    needs to be introduced.  */
1762
1763 static tree
1764 vect_get_vec_def_for_operand (tree op, tree stmt, tree *scalar_def)
1765 {
1766   tree vec_oprnd;
1767   tree vec_stmt;
1768   tree def_stmt;
1769   stmt_vec_info def_stmt_info = NULL;
1770   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
1771   tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
1772   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
1773   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
1774   tree vec_inv;
1775   tree vec_cst;
1776   tree t = NULL_TREE;
1777   tree def;
1778   int i;
1779   enum vect_def_type dt;
1780   bool is_simple_use;
1781   tree vector_type;
1782
1783   if (vect_print_dump_info (REPORT_DETAILS))
1784     {
1785       fprintf (vect_dump, "vect_get_vec_def_for_operand: ");
1786       print_generic_expr (vect_dump, op, TDF_SLIM);
1787     }
1788
1789   is_simple_use = vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt);
1790   gcc_assert (is_simple_use);
1791   if (vect_print_dump_info (REPORT_DETAILS))
1792     {
1793       if (def)
1794         {
1795           fprintf (vect_dump, "def =  ");
1796           print_generic_expr (vect_dump, def, TDF_SLIM);
1797         }
1798       if (def_stmt)
1799         {
1800           fprintf (vect_dump, "  def_stmt =  ");
1801           print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
1802         }
1803     }
1804
1805   switch (dt)
1806     {
1807     /* Case 1: operand is a constant.  */
1808     case vect_constant_def:
1809       {
1810         if (scalar_def) 
1811           *scalar_def = op;
1812
1813         /* Create 'vect_cst_ = {cst,cst,...,cst}'  */
1814         if (vect_print_dump_info (REPORT_DETAILS))
1815           fprintf (vect_dump, "Create vector_cst. nunits = %d", nunits);
1816
1817         for (i = nunits - 1; i >= 0; --i)
1818           {
1819             t = tree_cons (NULL_TREE, op, t);
1820           }
1821         vector_type = get_vectype_for_scalar_type (TREE_TYPE (op));
1822         gcc_assert (vector_type);
1823         vec_cst = build_vector (vector_type, t);
1824
1825         return vect_init_vector (stmt, vec_cst, vector_type, NULL);
1826       }
1827
1828     /* Case 2: operand is defined outside the loop - loop invariant.  */
1829     case vect_invariant_def:
1830       {
1831         if (scalar_def) 
1832           *scalar_def = def;
1833
1834         /* Create 'vec_inv = {inv,inv,..,inv}'  */
1835         if (vect_print_dump_info (REPORT_DETAILS))
1836           fprintf (vect_dump, "Create vector_inv.");
1837
1838         for (i = nunits - 1; i >= 0; --i)
1839           {
1840             t = tree_cons (NULL_TREE, def, t);
1841           }
1842
1843         /* FIXME: use build_constructor directly.  */
1844         vector_type = get_vectype_for_scalar_type (TREE_TYPE (def));
1845         gcc_assert (vector_type);
1846         vec_inv = build_constructor_from_list (vector_type, t);
1847         return vect_init_vector (stmt, vec_inv, vector_type, NULL);
1848       }
1849
1850     /* Case 3: operand is defined inside the loop.  */
1851     case vect_loop_def:
1852       {
1853         if (scalar_def) 
1854           *scalar_def = def_stmt;
1855
1856         /* Get the def from the vectorized stmt.  */
1857         def_stmt_info = vinfo_for_stmt (def_stmt);
1858         vec_stmt = STMT_VINFO_VEC_STMT (def_stmt_info);
1859         gcc_assert (vec_stmt);
1860         if (TREE_CODE (vec_stmt) == PHI_NODE)
1861           vec_oprnd = PHI_RESULT (vec_stmt);
1862         else
1863           vec_oprnd = GIMPLE_STMT_OPERAND (vec_stmt, 0);
1864         return vec_oprnd;
1865       }
1866
1867     /* Case 4: operand is defined by a loop header phi - reduction  */
1868     case vect_reduction_def:
1869       {
1870         struct loop *loop;
1871
1872         gcc_assert (TREE_CODE (def_stmt) == PHI_NODE);
1873         loop = (bb_for_stmt (def_stmt))->loop_father; 
1874
1875         /* Get the def before the loop  */
1876         op = PHI_ARG_DEF_FROM_EDGE (def_stmt, loop_preheader_edge (loop));
1877         return get_initial_def_for_reduction (stmt, op, scalar_def);
1878      }
1879
1880     /* Case 5: operand is defined by loop-header phi - induction.  */
1881     case vect_induction_def:
1882       {
1883         gcc_assert (TREE_CODE (def_stmt) == PHI_NODE);
1884
1885         /* Get the def from the vectorized stmt.  */
1886         def_stmt_info = vinfo_for_stmt (def_stmt);
1887         vec_stmt = STMT_VINFO_VEC_STMT (def_stmt_info);
1888         gcc_assert (vec_stmt && (TREE_CODE (vec_stmt) == PHI_NODE));
1889         vec_oprnd = PHI_RESULT (vec_stmt);
1890         return vec_oprnd;
1891       }
1892
1893     default:
1894       gcc_unreachable ();
1895     }
1896 }
1897
1898
1899 /* Function vect_get_vec_def_for_stmt_copy
1900
1901    Return a vector-def for an operand. This function is used when the 
1902    vectorized stmt to be created (by the caller to this function) is a "copy" 
1903    created in case the vectorized result cannot fit in one vector, and several 
1904    copies of the vector-stmt are required. In this case the vector-def is 
1905    retrieved from the vector stmt recorded in the STMT_VINFO_RELATED_STMT field
1906    of the stmt that defines VEC_OPRND. 
1907    DT is the type of the vector def VEC_OPRND.
1908
1909    Context:
1910         In case the vectorization factor (VF) is bigger than the number
1911    of elements that can fit in a vectype (nunits), we have to generate
1912    more than one vector stmt to vectorize the scalar stmt. This situation
1913    arises when there are multiple data-types operated upon in the loop; the 
1914    smallest data-type determines the VF, and as a result, when vectorizing
1915    stmts operating on wider types we need to create 'VF/nunits' "copies" of the
1916    vector stmt (each computing a vector of 'nunits' results, and together
1917    computing 'VF' results in each iteration).  This function is called when 
1918    vectorizing such a stmt (e.g. vectorizing S2 in the illustration below, in
1919    which VF=16 and nunits=4, so the number of copies required is 4):
1920
1921    scalar stmt:         vectorized into:        STMT_VINFO_RELATED_STMT
1922  
1923    S1: x = load         VS1.0:  vx.0 = memref0      VS1.1
1924                         VS1.1:  vx.1 = memref1      VS1.2
1925                         VS1.2:  vx.2 = memref2      VS1.3
1926                         VS1.3:  vx.3 = memref3 
1927
1928    S2: z = x + ...      VSnew.0:  vz0 = vx.0 + ...  VSnew.1
1929                         VSnew.1:  vz1 = vx.1 + ...  VSnew.2
1930                         VSnew.2:  vz2 = vx.2 + ...  VSnew.3
1931                         VSnew.3:  vz3 = vx.3 + ...
1932
1933    The vectorization of S1 is explained in vectorizable_load.
1934    The vectorization of S2:
1935         To create the first vector-stmt out of the 4 copies - VSnew.0 - 
1936    the function 'vect_get_vec_def_for_operand' is called to 
1937    get the relevant vector-def for each operand of S2. For operand x it
1938    returns  the vector-def 'vx.0'.
1939
1940         To create the remaining copies of the vector-stmt (VSnew.j), this 
1941    function is called to get the relevant vector-def for each operand.  It is 
1942    obtained from the respective VS1.j stmt, which is recorded in the 
1943    STMT_VINFO_RELATED_STMT field of the stmt that defines VEC_OPRND.
1944
1945         For example, to obtain the vector-def 'vx.1' in order to create the 
1946    vector stmt 'VSnew.1', this function is called with VEC_OPRND='vx.0'. 
1947    Given 'vx0' we obtain the stmt that defines it ('VS1.0'); from the 
1948    STMT_VINFO_RELATED_STMT field of 'VS1.0' we obtain the next copy - 'VS1.1',
1949    and return its def ('vx.1').
1950    Overall, to create the above sequence this function will be called 3 times:
1951         vx.1 = vect_get_vec_def_for_stmt_copy (dt, vx.0);
1952         vx.2 = vect_get_vec_def_for_stmt_copy (dt, vx.1);
1953         vx.3 = vect_get_vec_def_for_stmt_copy (dt, vx.2);  */
1954
1955 static tree
1956 vect_get_vec_def_for_stmt_copy (enum vect_def_type dt, tree vec_oprnd)
1957 {
1958   tree vec_stmt_for_operand;
1959   stmt_vec_info def_stmt_info;
1960
1961   /* Do nothing; can reuse same def.  */
1962   if (dt == vect_invariant_def || dt == vect_constant_def )
1963     return vec_oprnd;
1964
1965   vec_stmt_for_operand = SSA_NAME_DEF_STMT (vec_oprnd);
1966   def_stmt_info = vinfo_for_stmt (vec_stmt_for_operand);
1967   gcc_assert (def_stmt_info);
1968   vec_stmt_for_operand = STMT_VINFO_RELATED_STMT (def_stmt_info);
1969   gcc_assert (vec_stmt_for_operand);
1970   vec_oprnd = GIMPLE_STMT_OPERAND (vec_stmt_for_operand, 0);
1971   return vec_oprnd;
1972 }
1973
1974
1975 /* Get vectorized definitions for the operands to create a copy of an original
1976    stmt. See vect_get_vec_def_for_stmt_copy() for details.  */
1977
1978 static void
1979 vect_get_vec_defs_for_stmt_copy (enum vect_def_type *dt, 
1980                                  VEC(tree,heap) **vec_oprnds0, 
1981                                  VEC(tree,heap) **vec_oprnds1)
1982 {
1983   tree vec_oprnd = VEC_pop (tree, *vec_oprnds0);
1984
1985   vec_oprnd = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd);
1986   VEC_quick_push (tree, *vec_oprnds0, vec_oprnd);
1987
1988   if (vec_oprnds1 && *vec_oprnds1)
1989     {
1990       vec_oprnd = VEC_pop (tree, *vec_oprnds1);
1991       vec_oprnd = vect_get_vec_def_for_stmt_copy (dt[1], vec_oprnd);
1992       VEC_quick_push (tree, *vec_oprnds1, vec_oprnd);
1993     }
1994 }
1995
1996
1997 /* Get vectorized definitions for OP0 and OP1, or SLP_NODE if it is not NULL.  */
1998
1999 static void
2000 vect_get_vec_defs (tree op0, tree op1, tree stmt, VEC(tree,heap) **vec_oprnds0, 
2001                    VEC(tree,heap) **vec_oprnds1, slp_tree slp_node)
2002 {
2003   if (slp_node)
2004     vect_get_slp_defs (slp_node, vec_oprnds0, vec_oprnds1);
2005   else
2006     {
2007       tree vec_oprnd;
2008
2009       *vec_oprnds0 = VEC_alloc (tree, heap, 1); 
2010       vec_oprnd = vect_get_vec_def_for_operand (op0, stmt, NULL);      
2011       VEC_quick_push (tree, *vec_oprnds0, vec_oprnd);
2012
2013       if (op1)
2014         {
2015           *vec_oprnds1 = VEC_alloc (tree, heap, 1);     
2016           vec_oprnd = vect_get_vec_def_for_operand (op1, stmt, NULL);      
2017           VEC_quick_push (tree, *vec_oprnds1, vec_oprnd);
2018         }
2019     }
2020 }
2021
2022
2023 /* Function vect_finish_stmt_generation.
2024
2025    Insert a new stmt.  */
2026
2027 static void
2028 vect_finish_stmt_generation (tree stmt, tree vec_stmt, 
2029                              block_stmt_iterator *bsi)
2030 {
2031   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2032   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2033
2034   gcc_assert (stmt == bsi_stmt (*bsi));
2035   gcc_assert (TREE_CODE (stmt) != LABEL_EXPR);
2036
2037   bsi_insert_before (bsi, vec_stmt, BSI_SAME_STMT);
2038
2039   set_stmt_info (get_stmt_ann (vec_stmt), 
2040                  new_stmt_vec_info (vec_stmt, loop_vinfo)); 
2041
2042   if (vect_print_dump_info (REPORT_DETAILS))
2043     {
2044       fprintf (vect_dump, "add new stmt: ");
2045       print_generic_expr (vect_dump, vec_stmt, TDF_SLIM);
2046     }
2047
2048   /* Make sure bsi points to the stmt that is being vectorized.  */
2049   gcc_assert (stmt == bsi_stmt (*bsi));
2050
2051 #ifdef USE_MAPPED_LOCATION
2052   SET_EXPR_LOCATION (vec_stmt, EXPR_LOCATION (stmt));
2053 #else
2054   SET_EXPR_LOCUS (vec_stmt, EXPR_LOCUS (stmt));
2055 #endif
2056 }
2057
2058
2059 /* Function get_initial_def_for_reduction
2060
2061    Input:
2062    STMT - a stmt that performs a reduction operation in the loop.
2063    INIT_VAL - the initial value of the reduction variable
2064
2065    Output:
2066    ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
2067         of the reduction (used for adjusting the epilog - see below).
2068    Return a vector variable, initialized according to the operation that STMT
2069         performs. This vector will be used as the initial value of the
2070         vector of partial results.
2071
2072    Option1 (adjust in epilog): Initialize the vector as follows:
2073      add:         [0,0,...,0,0]
2074      mult:        [1,1,...,1,1]
2075      min/max:     [init_val,init_val,..,init_val,init_val]
2076      bit and/or:  [init_val,init_val,..,init_val,init_val]
2077    and when necessary (e.g. add/mult case) let the caller know
2078    that it needs to adjust the result by init_val.
2079
2080    Option2: Initialize the vector as follows:
2081      add:         [0,0,...,0,init_val]
2082      mult:        [1,1,...,1,init_val]
2083      min/max:     [init_val,init_val,...,init_val]
2084      bit and/or:  [init_val,init_val,...,init_val]
2085    and no adjustments are needed.
2086
2087    For example, for the following code:
2088
2089    s = init_val;
2090    for (i=0;i<n;i++)
2091      s = s + a[i];
2092
2093    STMT is 's = s + a[i]', and the reduction variable is 's'.
2094    For a vector of 4 units, we want to return either [0,0,0,init_val],
2095    or [0,0,0,0] and let the caller know that it needs to adjust
2096    the result at the end by 'init_val'.
2097
2098    FORNOW, we are using the 'adjust in epilog' scheme, because this way the
2099    initialization vector is simpler (same element in all entries).
2100    A cost model should help decide between these two schemes.  */
2101
2102 static tree
2103 get_initial_def_for_reduction (tree stmt, tree init_val, tree *adjustment_def)
2104 {
2105   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
2106   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
2107   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2108   tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
2109   int nunits =  TYPE_VECTOR_SUBPARTS (vectype);
2110   enum tree_code code = TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1));
2111   tree type = TREE_TYPE (init_val);
2112   tree vecdef;
2113   tree def_for_init;
2114   tree init_def;
2115   tree t = NULL_TREE;
2116   int i;
2117   tree vector_type;
2118   bool nested_in_vect_loop = false; 
2119
2120   gcc_assert (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type) || SCALAR_FLOAT_TYPE_P (type));
2121   if (nested_in_vect_loop_p (loop, stmt))
2122     nested_in_vect_loop = true;
2123   else
2124     gcc_assert (loop == (bb_for_stmt (stmt))->loop_father);
2125
2126   vecdef = vect_get_vec_def_for_operand (init_val, stmt, NULL);
2127
2128   switch (code)
2129   {
2130   case WIDEN_SUM_EXPR:
2131   case DOT_PROD_EXPR:
2132   case PLUS_EXPR:
2133     if (nested_in_vect_loop)
2134       *adjustment_def = vecdef;
2135     else
2136       *adjustment_def = init_val;
2137     /* Create a vector of zeros for init_def.  */
2138     if (SCALAR_FLOAT_TYPE_P (type))
2139       def_for_init = build_real (type, dconst0);
2140     else
2141       def_for_init = build_int_cst (type, 0);
2142     for (i = nunits - 1; i >= 0; --i)
2143       t = tree_cons (NULL_TREE, def_for_init, t);
2144     vector_type = get_vectype_for_scalar_type (TREE_TYPE (def_for_init));
2145     gcc_assert (vector_type);
2146     init_def = build_vector (vector_type, t);
2147     break;
2148
2149   case MIN_EXPR:
2150   case MAX_EXPR:
2151     *adjustment_def = NULL_TREE;
2152     init_def = vecdef;
2153     break;
2154
2155   default:
2156     gcc_unreachable ();
2157   }
2158
2159   return init_def;
2160 }
2161
2162
2163 /* Function vect_create_epilog_for_reduction
2164     
2165    Create code at the loop-epilog to finalize the result of a reduction
2166    computation. 
2167   
2168    VECT_DEF is a vector of partial results. 
2169    REDUC_CODE is the tree-code for the epilog reduction.
2170    STMT is the scalar reduction stmt that is being vectorized.
2171    REDUCTION_PHI is the phi-node that carries the reduction computation.
2172
2173    This function:
2174    1. Creates the reduction def-use cycle: sets the arguments for 
2175       REDUCTION_PHI:
2176       The loop-entry argument is the vectorized initial-value of the reduction.
2177       The loop-latch argument is VECT_DEF - the vector of partial sums.
2178    2. "Reduces" the vector of partial results VECT_DEF into a single result,
2179       by applying the operation specified by REDUC_CODE if available, or by 
2180       other means (whole-vector shifts or a scalar loop).
2181       The function also creates a new phi node at the loop exit to preserve 
2182       loop-closed form, as illustrated below.
2183   
2184      The flow at the entry to this function:
2185     
2186         loop:
2187           vec_def = phi <null, null>            # REDUCTION_PHI
2188           VECT_DEF = vector_stmt                # vectorized form of STMT
2189           s_loop = scalar_stmt                  # (scalar) STMT
2190         loop_exit:
2191           s_out0 = phi <s_loop>                 # (scalar) EXIT_PHI
2192           use <s_out0>
2193           use <s_out0>
2194
2195      The above is transformed by this function into:
2196
2197         loop:
2198           vec_def = phi <vec_init, VECT_DEF>    # REDUCTION_PHI
2199           VECT_DEF = vector_stmt                # vectorized form of STMT
2200           s_loop = scalar_stmt                  # (scalar) STMT 
2201         loop_exit:
2202           s_out0 = phi <s_loop>                 # (scalar) EXIT_PHI
2203           v_out1 = phi <VECT_DEF>               # NEW_EXIT_PHI
2204           v_out2 = reduce <v_out1>
2205           s_out3 = extract_field <v_out2, 0>
2206           s_out4 = adjust_result <s_out3>
2207           use <s_out4>
2208           use <s_out4>
2209 */
2210
2211 static void
2212 vect_create_epilog_for_reduction (tree vect_def, tree stmt,
2213                                   enum tree_code reduc_code, tree reduction_phi)
2214 {
2215   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2216   tree vectype;
2217   enum machine_mode mode;
2218   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2219   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2220   basic_block exit_bb;
2221   tree scalar_dest;
2222   tree scalar_type;
2223   tree new_phi;
2224   block_stmt_iterator exit_bsi;
2225   tree vec_dest;
2226   tree new_temp = NULL_TREE;
2227   tree new_name;
2228   tree epilog_stmt = NULL_TREE;
2229   tree new_scalar_dest, exit_phi, new_dest;
2230   tree bitsize, bitpos, bytesize; 
2231   enum tree_code code = TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1));
2232   tree adjustment_def;
2233   tree vec_initial_def;
2234   tree orig_name;
2235   imm_use_iterator imm_iter;
2236   use_operand_p use_p;
2237   bool extract_scalar_result = false;
2238   tree reduction_op, expr;
2239   tree orig_stmt;
2240   tree use_stmt;
2241   tree operation = GIMPLE_STMT_OPERAND (stmt, 1);
2242   bool nested_in_vect_loop = false;
2243   int op_type;
2244   VEC(tree,heap) *phis = NULL;
2245   int i;
2246   
2247   if (nested_in_vect_loop_p (loop, stmt))
2248     {
2249       loop = loop->inner;
2250       nested_in_vect_loop = true;
2251     }
2252   
2253   op_type = TREE_OPERAND_LENGTH (operation);
2254   reduction_op = TREE_OPERAND (operation, op_type-1);
2255   vectype = get_vectype_for_scalar_type (TREE_TYPE (reduction_op));
2256   gcc_assert (vectype);
2257   mode = TYPE_MODE (vectype);
2258
2259   /*** 1. Create the reduction def-use cycle  ***/
2260   
2261   /* 1.1 set the loop-entry arg of the reduction-phi:  */
2262   /* For the case of reduction, vect_get_vec_def_for_operand returns
2263      the scalar def before the loop, that defines the initial value
2264      of the reduction variable.  */
2265   vec_initial_def = vect_get_vec_def_for_operand (reduction_op, stmt,
2266                                                   &adjustment_def);
2267   add_phi_arg (reduction_phi, vec_initial_def, loop_preheader_edge (loop));
2268
2269   /* 1.2 set the loop-latch arg for the reduction-phi:  */
2270   add_phi_arg (reduction_phi, vect_def, loop_latch_edge (loop));
2271
2272   if (vect_print_dump_info (REPORT_DETAILS))
2273     {
2274       fprintf (vect_dump, "transform reduction: created def-use cycle:");
2275       print_generic_expr (vect_dump, reduction_phi, TDF_SLIM);
2276       fprintf (vect_dump, "\n");
2277       print_generic_expr (vect_dump, SSA_NAME_DEF_STMT (vect_def), TDF_SLIM);
2278     }
2279
2280
2281   /*** 2. Create epilog code
2282           The reduction epilog code operates across the elements of the vector
2283           of partial results computed by the vectorized loop.
2284           The reduction epilog code consists of:
2285           step 1: compute the scalar result in a vector (v_out2)
2286           step 2: extract the scalar result (s_out3) from the vector (v_out2)
2287           step 3: adjust the scalar result (s_out3) if needed.
2288
2289           Step 1 can be accomplished using one the following three schemes:
2290           (scheme 1) using reduc_code, if available.
2291           (scheme 2) using whole-vector shifts, if available.
2292           (scheme 3) using a scalar loop. In this case steps 1+2 above are 
2293                      combined.
2294                 
2295           The overall epilog code looks like this:
2296
2297           s_out0 = phi <s_loop>         # original EXIT_PHI
2298           v_out1 = phi <VECT_DEF>       # NEW_EXIT_PHI
2299           v_out2 = reduce <v_out1>              # step 1
2300           s_out3 = extract_field <v_out2, 0>    # step 2
2301           s_out4 = adjust_result <s_out3>       # step 3
2302
2303           (step 3 is optional, and step2 1 and 2 may be combined).
2304           Lastly, the uses of s_out0 are replaced by s_out4.
2305
2306           ***/
2307
2308   /* 2.1 Create new loop-exit-phi to preserve loop-closed form:
2309         v_out1 = phi <v_loop>  */
2310
2311   exit_bb = single_exit (loop)->dest;
2312   new_phi = create_phi_node (SSA_NAME_VAR (vect_def), exit_bb);
2313   SET_PHI_ARG_DEF (new_phi, single_exit (loop)->dest_idx, vect_def);
2314   exit_bsi = bsi_after_labels (exit_bb);
2315
2316   /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3 
2317          (i.e. when reduc_code is not available) and in the final adjustment
2318          code (if needed).  Also get the original scalar reduction variable as
2319          defined in the loop.  In case STMT is a "pattern-stmt" (i.e. - it 
2320          represents a reduction pattern), the tree-code and scalar-def are 
2321          taken from the original stmt that the pattern-stmt (STMT) replaces.  
2322          Otherwise (it is a regular reduction) - the tree-code and scalar-def
2323          are taken from STMT.  */ 
2324
2325   orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
2326   if (!orig_stmt)
2327     {
2328       /* Regular reduction  */
2329       orig_stmt = stmt;
2330     }
2331   else
2332     {
2333       /* Reduction pattern  */
2334       stmt_vec_info stmt_vinfo = vinfo_for_stmt (orig_stmt);
2335       gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo));
2336       gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo) == stmt);
2337     }
2338   code = TREE_CODE (GIMPLE_STMT_OPERAND (orig_stmt, 1));
2339   scalar_dest = GIMPLE_STMT_OPERAND (orig_stmt, 0);
2340   scalar_type = TREE_TYPE (scalar_dest);
2341   new_scalar_dest = vect_create_destination_var (scalar_dest, NULL);
2342   bitsize = TYPE_SIZE (scalar_type);
2343   bytesize = TYPE_SIZE_UNIT (scalar_type);
2344
2345
2346   /* In case this is a reduction in an inner-loop while vectorizing an outer
2347      loop - we don't need to extract a single scalar result at the end of the
2348      inner-loop.  The final vector of partial results will be used in the
2349      vectorized outer-loop, or reduced to a scalar result at the end of the
2350      outer-loop.  */
2351   if (nested_in_vect_loop)
2352     goto vect_finalize_reduction;
2353
2354   /* 2.3 Create the reduction code, using one of the three schemes described
2355          above.  */
2356
2357   if (reduc_code < NUM_TREE_CODES)
2358     {
2359       tree tmp;
2360
2361       /*** Case 1:  Create:
2362            v_out2 = reduc_expr <v_out1>  */
2363
2364       if (vect_print_dump_info (REPORT_DETAILS))
2365         fprintf (vect_dump, "Reduce using direct vector reduction.");
2366
2367       vec_dest = vect_create_destination_var (scalar_dest, vectype);
2368       tmp = build1 (reduc_code, vectype,  PHI_RESULT (new_phi));
2369       epilog_stmt = build_gimple_modify_stmt (vec_dest, tmp);
2370       new_temp = make_ssa_name (vec_dest, epilog_stmt);
2371       GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
2372       bsi_insert_before (&exit_bsi, epilog_stmt, BSI_SAME_STMT);
2373
2374       extract_scalar_result = true;
2375     }
2376   else
2377     {
2378       enum tree_code shift_code = 0;
2379       bool have_whole_vector_shift = true;
2380       int bit_offset;
2381       int element_bitsize = tree_low_cst (bitsize, 1);
2382       int vec_size_in_bits = tree_low_cst (TYPE_SIZE (vectype), 1);
2383       tree vec_temp;
2384
2385       if (optab_handler (vec_shr_optab, mode)->insn_code != CODE_FOR_nothing)
2386         shift_code = VEC_RSHIFT_EXPR;
2387       else
2388         have_whole_vector_shift = false;
2389
2390       /* Regardless of whether we have a whole vector shift, if we're
2391          emulating the operation via tree-vect-generic, we don't want
2392          to use it.  Only the first round of the reduction is likely
2393          to still be profitable via emulation.  */
2394       /* ??? It might be better to emit a reduction tree code here, so that
2395          tree-vect-generic can expand the first round via bit tricks.  */
2396       if (!VECTOR_MODE_P (mode))
2397         have_whole_vector_shift = false;
2398       else
2399         {
2400           optab optab = optab_for_tree_code (code, vectype);
2401           if (optab_handler (optab, mode)->insn_code == CODE_FOR_nothing)
2402             have_whole_vector_shift = false;
2403         }
2404
2405       if (have_whole_vector_shift)
2406         {
2407           /*** Case 2: Create:
2408              for (offset = VS/2; offset >= element_size; offset/=2)
2409                 {
2410                   Create:  va' = vec_shift <va, offset>
2411                   Create:  va = vop <va, va'>
2412                 }  */
2413
2414           if (vect_print_dump_info (REPORT_DETAILS))
2415             fprintf (vect_dump, "Reduce using vector shifts");
2416
2417           vec_dest = vect_create_destination_var (scalar_dest, vectype);
2418           new_temp = PHI_RESULT (new_phi);
2419
2420           for (bit_offset = vec_size_in_bits/2;
2421                bit_offset >= element_bitsize;
2422                bit_offset /= 2)
2423             {
2424               tree bitpos = size_int (bit_offset);
2425               tree tmp = build2 (shift_code, vectype, new_temp, bitpos);
2426               epilog_stmt = build_gimple_modify_stmt (vec_dest, tmp);
2427               new_name = make_ssa_name (vec_dest, epilog_stmt);
2428               GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_name;
2429               bsi_insert_before (&exit_bsi, epilog_stmt, BSI_SAME_STMT);
2430
2431               tmp = build2 (code, vectype, new_name, new_temp);
2432               epilog_stmt = build_gimple_modify_stmt (vec_dest, tmp);
2433               new_temp = make_ssa_name (vec_dest, epilog_stmt);
2434               GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
2435               bsi_insert_before (&exit_bsi, epilog_stmt, BSI_SAME_STMT);
2436             }
2437
2438           extract_scalar_result = true;
2439         }
2440       else
2441         {
2442           tree rhs;
2443
2444           /*** Case 3: Create:  
2445              s = extract_field <v_out2, 0>
2446              for (offset = element_size; 
2447                   offset < vector_size; 
2448                   offset += element_size;)
2449                {
2450                  Create:  s' = extract_field <v_out2, offset>
2451                  Create:  s = op <s, s'>
2452                }  */
2453
2454           if (vect_print_dump_info (REPORT_DETAILS))
2455             fprintf (vect_dump, "Reduce using scalar code. ");
2456
2457           vec_temp = PHI_RESULT (new_phi);
2458           vec_size_in_bits = tree_low_cst (TYPE_SIZE (vectype), 1);
2459           rhs = build3 (BIT_FIELD_REF, scalar_type, vec_temp, bitsize,
2460                          bitsize_zero_node);
2461           BIT_FIELD_REF_UNSIGNED (rhs) = TYPE_UNSIGNED (scalar_type);
2462           epilog_stmt = build_gimple_modify_stmt (new_scalar_dest, rhs);
2463           new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
2464           GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
2465           bsi_insert_before (&exit_bsi, epilog_stmt, BSI_SAME_STMT);
2466               
2467           for (bit_offset = element_bitsize;
2468                bit_offset < vec_size_in_bits;
2469                bit_offset += element_bitsize)
2470             { 
2471               tree tmp;
2472               tree bitpos = bitsize_int (bit_offset);
2473               tree rhs = build3 (BIT_FIELD_REF, scalar_type, vec_temp, bitsize,
2474                                  bitpos);
2475                 
2476               BIT_FIELD_REF_UNSIGNED (rhs) = TYPE_UNSIGNED (scalar_type);
2477               epilog_stmt = build_gimple_modify_stmt (new_scalar_dest, rhs);
2478               new_name = make_ssa_name (new_scalar_dest, epilog_stmt);
2479               GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_name;
2480               bsi_insert_before (&exit_bsi, epilog_stmt, BSI_SAME_STMT);
2481
2482               tmp = build2 (code, scalar_type, new_name, new_temp);
2483               epilog_stmt = build_gimple_modify_stmt (new_scalar_dest, tmp);
2484               new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
2485               GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
2486               bsi_insert_before (&exit_bsi, epilog_stmt, BSI_SAME_STMT);
2487             }
2488
2489           extract_scalar_result = false;
2490         }
2491     }
2492
2493   /* 2.4  Extract the final scalar result.  Create:
2494          s_out3 = extract_field <v_out2, bitpos>  */
2495   
2496   if (extract_scalar_result)
2497     {
2498       tree rhs;
2499
2500       gcc_assert (!nested_in_vect_loop);
2501       if (vect_print_dump_info (REPORT_DETAILS))
2502         fprintf (vect_dump, "extract scalar result");
2503
2504       if (BYTES_BIG_ENDIAN)
2505         bitpos = size_binop (MULT_EXPR,
2506                        bitsize_int (TYPE_VECTOR_SUBPARTS (vectype) - 1),
2507                        TYPE_SIZE (scalar_type));
2508       else
2509         bitpos = bitsize_zero_node;
2510
2511       rhs = build3 (BIT_FIELD_REF, scalar_type, new_temp, bitsize, bitpos);
2512       BIT_FIELD_REF_UNSIGNED (rhs) = TYPE_UNSIGNED (scalar_type);
2513       epilog_stmt = build_gimple_modify_stmt (new_scalar_dest, rhs);
2514       new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
2515       GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp; 
2516       bsi_insert_before (&exit_bsi, epilog_stmt, BSI_SAME_STMT);
2517     }
2518
2519 vect_finalize_reduction:
2520
2521   /* 2.5 Adjust the final result by the initial value of the reduction
2522          variable. (When such adjustment is not needed, then
2523          'adjustment_def' is zero).  For example, if code is PLUS we create:
2524          new_temp = loop_exit_def + adjustment_def  */
2525
2526   if (adjustment_def)
2527     {
2528       if (nested_in_vect_loop)
2529         {
2530           gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def)) == VECTOR_TYPE);
2531           expr = build2 (code, vectype, PHI_RESULT (new_phi), adjustment_def);
2532           new_dest = vect_create_destination_var (scalar_dest, vectype);
2533         }
2534       else
2535         {
2536           gcc_assert (TREE_CODE (TREE_TYPE (adjustment_def)) != VECTOR_TYPE);
2537           expr = build2 (code, scalar_type, new_temp, adjustment_def);
2538           new_dest = vect_create_destination_var (scalar_dest, scalar_type);
2539         }
2540       epilog_stmt = build_gimple_modify_stmt (new_dest, expr);
2541       new_temp = make_ssa_name (new_dest, epilog_stmt);
2542       GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
2543       bsi_insert_before (&exit_bsi, epilog_stmt, BSI_SAME_STMT);
2544     }
2545
2546
2547   /* 2.6  Handle the loop-exit phi  */
2548
2549   /* Replace uses of s_out0 with uses of s_out3:
2550      Find the loop-closed-use at the loop exit of the original scalar result.
2551      (The reduction result is expected to have two immediate uses - one at the 
2552      latch block, and one at the loop exit).  */
2553   phis = VEC_alloc (tree, heap, 10);
2554   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, scalar_dest)
2555     {
2556       if (!flow_bb_inside_loop_p (loop, bb_for_stmt (USE_STMT (use_p))))
2557         {
2558           exit_phi = USE_STMT (use_p);
2559           VEC_quick_push (tree, phis, exit_phi);
2560         }
2561     }
2562   /* We expect to have found an exit_phi because of loop-closed-ssa form.  */
2563   gcc_assert (!VEC_empty (tree, phis));
2564
2565   for (i = 0; VEC_iterate (tree, phis, i, exit_phi); i++)
2566     {
2567       if (nested_in_vect_loop)
2568         {
2569           stmt_vec_info stmt_vinfo = vinfo_for_stmt (exit_phi);
2570
2571           /* FORNOW. Currently not supporting the case that an inner-loop reduction
2572              is not used in the outer-loop (but only outside the outer-loop).  */
2573           gcc_assert (STMT_VINFO_RELEVANT_P (stmt_vinfo) 
2574                       && !STMT_VINFO_LIVE_P (stmt_vinfo));
2575
2576           epilog_stmt = adjustment_def ? epilog_stmt :  new_phi;
2577           STMT_VINFO_VEC_STMT (stmt_vinfo) = epilog_stmt;
2578           set_stmt_info (get_stmt_ann (epilog_stmt),
2579           new_stmt_vec_info (epilog_stmt, loop_vinfo));
2580           continue;
2581         }
2582
2583       /* Replace the uses:  */
2584       orig_name = PHI_RESULT (exit_phi);
2585       FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, orig_name)
2586         FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
2587           SET_USE (use_p, new_temp);
2588     }
2589   VEC_free (tree, heap, phis);
2590
2591
2592
2593 /* Function vectorizable_reduction.
2594
2595    Check if STMT performs a reduction operation that can be vectorized.
2596    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2597    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2598    Return FALSE if not a vectorizable STMT, TRUE otherwise.
2599
2600    This function also handles reduction idioms (patterns) that have been 
2601    recognized in advance during vect_pattern_recog. In this case, STMT may be
2602    of this form:
2603      X = pattern_expr (arg0, arg1, ..., X)
2604    and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
2605    sequence that had been detected and replaced by the pattern-stmt (STMT).
2606   
2607    In some cases of reduction patterns, the type of the reduction variable X is
2608    different than the type of the other arguments of STMT.
2609    In such cases, the vectype that is used when transforming STMT into a vector
2610    stmt is different than the vectype that is used to determine the
2611    vectorization factor, because it consists of a different number of elements 
2612    than the actual number of elements that are being operated upon in parallel.
2613
2614    For example, consider an accumulation of shorts into an int accumulator.
2615    On some targets it's possible to vectorize this pattern operating on 8
2616    shorts at a time (hence, the vectype for purposes of determining the
2617    vectorization factor should be V8HI); on the other hand, the vectype that
2618    is used to create the vector form is actually V4SI (the type of the result).
2619
2620    Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
2621    indicates what is the actual level of parallelism (V8HI in the example), so
2622    that the right vectorization factor would be derived. This vectype
2623    corresponds to the type of arguments to the reduction stmt, and should *NOT*
2624    be used to create the vectorized stmt. The right vectype for the vectorized
2625    stmt is obtained from the type of the result X:
2626         get_vectype_for_scalar_type (TREE_TYPE (X))
2627
2628    This means that, contrary to "regular" reductions (or "regular" stmts in
2629    general), the following equation:
2630       STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
2631    does *NOT* necessarily hold for reduction patterns.  */
2632
2633 bool
2634 vectorizable_reduction (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
2635 {
2636   tree vec_dest;
2637   tree scalar_dest;
2638   tree op;
2639   tree loop_vec_def0 = NULL_TREE, loop_vec_def1 = NULL_TREE;
2640   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2641   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
2642   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2643   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2644   tree operation;
2645   enum tree_code code, orig_code, epilog_reduc_code = 0;
2646   enum machine_mode vec_mode;
2647   int op_type;
2648   optab optab, reduc_optab;
2649   tree new_temp = NULL_TREE;
2650   tree def, def_stmt;
2651   enum vect_def_type dt;
2652   tree new_phi;
2653   tree scalar_type;
2654   bool is_simple_use;
2655   tree orig_stmt;
2656   stmt_vec_info orig_stmt_info;
2657   tree expr = NULL_TREE;
2658   int i;
2659   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
2660   int ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
2661   stmt_vec_info prev_stmt_info;
2662   tree reduc_def;
2663   tree new_stmt = NULL_TREE;
2664   int j;
2665
2666   if (nested_in_vect_loop_p (loop, stmt))
2667     {
2668       loop = loop->inner;
2669       /* FORNOW. This restriction should be relaxed.  */
2670       if (ncopies > 1)
2671         {
2672           if (vect_print_dump_info (REPORT_DETAILS))
2673             fprintf (vect_dump, "multiple types in nested loop.");
2674           return false;
2675         }
2676     }
2677
2678   gcc_assert (ncopies >= 1);
2679
2680   /* FORNOW: SLP not supported.  */
2681   if (STMT_SLP_TYPE (stmt_info))
2682     return false;
2683
2684   /* 1. Is vectorizable reduction?  */
2685
2686   /* Not supportable if the reduction variable is used in the loop.  */
2687   if (STMT_VINFO_RELEVANT (stmt_info) > vect_used_in_outer)
2688     return false;
2689
2690   /* Reductions that are not used even in an enclosing outer-loop,
2691      are expected to be "live" (used out of the loop).  */
2692   if (STMT_VINFO_RELEVANT (stmt_info) == vect_unused_in_loop
2693       && !STMT_VINFO_LIVE_P (stmt_info))
2694     return false;
2695
2696   /* Make sure it was already recognized as a reduction computation.  */
2697   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_reduction_def)
2698     return false;
2699
2700   /* 2. Has this been recognized as a reduction pattern? 
2701
2702      Check if STMT represents a pattern that has been recognized
2703      in earlier analysis stages.  For stmts that represent a pattern,
2704      the STMT_VINFO_RELATED_STMT field records the last stmt in
2705      the original sequence that constitutes the pattern.  */
2706
2707   orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
2708   if (orig_stmt)
2709     {
2710       orig_stmt_info = vinfo_for_stmt (orig_stmt);
2711       gcc_assert (STMT_VINFO_RELATED_STMT (orig_stmt_info) == stmt);
2712       gcc_assert (STMT_VINFO_IN_PATTERN_P (orig_stmt_info));
2713       gcc_assert (!STMT_VINFO_IN_PATTERN_P (stmt_info));
2714     }
2715  
2716   /* 3. Check the operands of the operation. The first operands are defined
2717         inside the loop body. The last operand is the reduction variable,
2718         which is defined by the loop-header-phi.  */
2719
2720   gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
2721
2722   operation = GIMPLE_STMT_OPERAND (stmt, 1);
2723   code = TREE_CODE (operation);
2724   op_type = TREE_OPERAND_LENGTH (operation);
2725   if (op_type != binary_op && op_type != ternary_op)
2726     return false;
2727   scalar_dest = GIMPLE_STMT_OPERAND (stmt, 0);
2728   scalar_type = TREE_TYPE (scalar_dest);
2729   if (!POINTER_TYPE_P (scalar_type) && !INTEGRAL_TYPE_P (scalar_type) 
2730       && !SCALAR_FLOAT_TYPE_P (scalar_type))
2731     return false;
2732
2733   /* All uses but the last are expected to be defined in the loop.
2734      The last use is the reduction variable.  */
2735   for (i = 0; i < op_type-1; i++)
2736     {
2737       op = TREE_OPERAND (operation, i);
2738       is_simple_use = vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt);
2739       gcc_assert (is_simple_use);
2740       if (dt != vect_loop_def
2741           && dt != vect_invariant_def
2742           && dt != vect_constant_def
2743           && dt != vect_induction_def)
2744         return false;
2745     }
2746
2747   op = TREE_OPERAND (operation, i);
2748   is_simple_use = vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt);
2749   gcc_assert (is_simple_use);
2750   gcc_assert (dt == vect_reduction_def);
2751   gcc_assert (TREE_CODE (def_stmt) == PHI_NODE);
2752   if (orig_stmt) 
2753     gcc_assert (orig_stmt == vect_is_simple_reduction (loop_vinfo, def_stmt));
2754   else
2755     gcc_assert (stmt == vect_is_simple_reduction (loop_vinfo, def_stmt));
2756   
2757   if (STMT_VINFO_LIVE_P (vinfo_for_stmt (def_stmt)))
2758     return false;
2759
2760   /* 4. Supportable by target?  */
2761
2762   /* 4.1. check support for the operation in the loop  */
2763   optab = optab_for_tree_code (code, vectype);
2764   if (!optab)
2765     {
2766       if (vect_print_dump_info (REPORT_DETAILS))
2767         fprintf (vect_dump, "no optab.");
2768       return false;
2769     }
2770   vec_mode = TYPE_MODE (vectype);
2771   if (optab_handler (optab, vec_mode)->insn_code == CODE_FOR_nothing)
2772     {
2773       if (vect_print_dump_info (REPORT_DETAILS))
2774         fprintf (vect_dump, "op not supported by target.");
2775       if (GET_MODE_SIZE (vec_mode) != UNITS_PER_WORD
2776           || LOOP_VINFO_VECT_FACTOR (loop_vinfo)
2777              < vect_min_worthwhile_factor (code))
2778         return false;
2779       if (vect_print_dump_info (REPORT_DETAILS))
2780         fprintf (vect_dump, "proceeding using word mode.");
2781     }
2782
2783   /* Worthwhile without SIMD support?  */
2784   if (!VECTOR_MODE_P (TYPE_MODE (vectype))
2785       && LOOP_VINFO_VECT_FACTOR (loop_vinfo)
2786          < vect_min_worthwhile_factor (code))
2787     {
2788       if (vect_print_dump_info (REPORT_DETAILS))
2789         fprintf (vect_dump, "not worthwhile without SIMD support.");
2790       return false;
2791     }
2792
2793   /* 4.2. Check support for the epilog operation.
2794
2795           If STMT represents a reduction pattern, then the type of the
2796           reduction variable may be different than the type of the rest
2797           of the arguments.  For example, consider the case of accumulation
2798           of shorts into an int accumulator; The original code:
2799                         S1: int_a = (int) short_a;
2800           orig_stmt->   S2: int_acc = plus <int_a ,int_acc>;
2801
2802           was replaced with:
2803                         STMT: int_acc = widen_sum <short_a, int_acc>
2804
2805           This means that:
2806           1. The tree-code that is used to create the vector operation in the 
2807              epilog code (that reduces the partial results) is not the 
2808              tree-code of STMT, but is rather the tree-code of the original 
2809              stmt from the pattern that STMT is replacing. I.e, in the example 
2810              above we want to use 'widen_sum' in the loop, but 'plus' in the 
2811              epilog.
2812           2. The type (mode) we use to check available target support
2813              for the vector operation to be created in the *epilog*, is 
2814              determined by the type of the reduction variable (in the example 
2815              above we'd check this: plus_optab[vect_int_mode]).
2816              However the type (mode) we use to check available target support
2817              for the vector operation to be created *inside the loop*, is
2818              determined by the type of the other arguments to STMT (in the
2819              example we'd check this: widen_sum_optab[vect_short_mode]).
2820   
2821           This is contrary to "regular" reductions, in which the types of all 
2822           the arguments are the same as the type of the reduction variable. 
2823           For "regular" reductions we can therefore use the same vector type 
2824           (and also the same tree-code) when generating the epilog code and
2825           when generating the code inside the loop.  */
2826
2827   if (orig_stmt)
2828     {
2829       /* This is a reduction pattern: get the vectype from the type of the
2830          reduction variable, and get the tree-code from orig_stmt.  */
2831       orig_code = TREE_CODE (GIMPLE_STMT_OPERAND (orig_stmt, 1));
2832       vectype = get_vectype_for_scalar_type (TREE_TYPE (def));
2833       if (!vectype)
2834         {
2835           if (vect_print_dump_info (REPORT_DETAILS))
2836             {
2837               fprintf (vect_dump, "unsupported data-type ");
2838               print_generic_expr (vect_dump, TREE_TYPE (def), TDF_SLIM);
2839             }
2840           return false;
2841         }
2842
2843       vec_mode = TYPE_MODE (vectype);
2844     }
2845   else
2846     {
2847       /* Regular reduction: use the same vectype and tree-code as used for
2848          the vector code inside the loop can be used for the epilog code. */
2849       orig_code = code;
2850     }
2851
2852   if (!reduction_code_for_scalar_code (orig_code, &epilog_reduc_code))
2853     return false;
2854   reduc_optab = optab_for_tree_code (epilog_reduc_code, vectype);
2855   if (!reduc_optab)
2856     {
2857       if (vect_print_dump_info (REPORT_DETAILS))
2858         fprintf (vect_dump, "no optab for reduction.");
2859       epilog_reduc_code = NUM_TREE_CODES;
2860     }
2861   if (optab_handler (reduc_optab, vec_mode)->insn_code == CODE_FOR_nothing)
2862     {
2863       if (vect_print_dump_info (REPORT_DETAILS))
2864         fprintf (vect_dump, "reduc op not supported by target.");
2865       epilog_reduc_code = NUM_TREE_CODES;
2866     }
2867  
2868   if (!vec_stmt) /* transformation not required.  */
2869     {
2870       STMT_VINFO_TYPE (stmt_info) = reduc_vec_info_type;
2871       if (!vect_model_reduction_cost (stmt_info, epilog_reduc_code, ncopies))
2872         return false;
2873       return true;
2874     }
2875
2876   /** Transform.  **/
2877
2878   if (vect_print_dump_info (REPORT_DETAILS))
2879     fprintf (vect_dump, "transform reduction.");
2880
2881   /* Create the destination vector  */
2882   vec_dest = vect_create_destination_var (scalar_dest, vectype);
2883
2884   /* Create the reduction-phi that defines the reduction-operand.  */
2885   new_phi = create_phi_node (vec_dest, loop->header);
2886
2887   /* In case the vectorization factor (VF) is bigger than the number
2888      of elements that we can fit in a vectype (nunits), we have to generate
2889      more than one vector stmt - i.e - we need to "unroll" the
2890      vector stmt by a factor VF/nunits.  For more details see documentation
2891      in vectorizable_operation.  */
2892
2893   prev_stmt_info = NULL;
2894   for (j = 0; j < ncopies; j++)
2895     {
2896       /* Handle uses.  */
2897       if (j == 0)
2898         {
2899           op = TREE_OPERAND (operation, 0);
2900           loop_vec_def0 = vect_get_vec_def_for_operand (op, stmt, NULL);
2901           if (op_type == ternary_op)
2902             {
2903               op = TREE_OPERAND (operation, 1);
2904               loop_vec_def1 = vect_get_vec_def_for_operand (op, stmt, NULL);
2905             }
2906
2907           /* Get the vector def for the reduction variable from the phi node */
2908           reduc_def = PHI_RESULT (new_phi);
2909         }
2910       else
2911         {
2912           enum vect_def_type dt = vect_unknown_def_type; /* Dummy */
2913           loop_vec_def0 = vect_get_vec_def_for_stmt_copy (dt, loop_vec_def0);
2914           if (op_type == ternary_op)
2915             loop_vec_def1 = vect_get_vec_def_for_stmt_copy (dt, loop_vec_def1);
2916
2917           /* Get the vector def for the reduction variable from the vectorized
2918              reduction operation generated in the previous iteration (j-1)  */
2919           reduc_def = GIMPLE_STMT_OPERAND (new_stmt ,0);
2920         }
2921
2922       /* Arguments are ready. create the new vector stmt.  */
2923       if (op_type == binary_op)
2924         expr = build2 (code, vectype, loop_vec_def0, reduc_def);
2925       else
2926         expr = build3 (code, vectype, loop_vec_def0, loop_vec_def1, 
2927                        reduc_def);
2928       new_stmt = build_gimple_modify_stmt (vec_dest, expr);
2929       new_temp = make_ssa_name (vec_dest, new_stmt);
2930       GIMPLE_STMT_OPERAND (new_stmt, 0) = new_temp;
2931       vect_finish_stmt_generation (stmt, new_stmt, bsi);
2932
2933       if (j == 0)
2934         STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
2935       else
2936         STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
2937       prev_stmt_info = vinfo_for_stmt (new_stmt);
2938     }
2939
2940   /* Finalize the reduction-phi (set it's arguments) and create the
2941      epilog reduction code.  */
2942   vect_create_epilog_for_reduction (new_temp, stmt, epilog_reduc_code, new_phi);
2943   return true;
2944 }
2945
2946 /* Checks if CALL can be vectorized in type VECTYPE.  Returns
2947    a function declaration if the target has a vectorized version
2948    of the function, or NULL_TREE if the function cannot be vectorized.  */
2949
2950 tree
2951 vectorizable_function (tree call, tree vectype_out, tree vectype_in)
2952 {
2953   tree fndecl = get_callee_fndecl (call);
2954   enum built_in_function code;
2955
2956   /* We only handle functions that do not read or clobber memory -- i.e.
2957      const or novops ones.  */
2958   if (!(call_expr_flags (call) & (ECF_CONST | ECF_NOVOPS)))
2959     return NULL_TREE;
2960
2961   if (!fndecl
2962       || TREE_CODE (fndecl) != FUNCTION_DECL
2963       || !DECL_BUILT_IN (fndecl))
2964     return NULL_TREE;
2965
2966   code = DECL_FUNCTION_CODE (fndecl);
2967   return targetm.vectorize.builtin_vectorized_function (code, vectype_out,
2968                                                         vectype_in);
2969 }
2970
2971 /* Function vectorizable_call.
2972
2973    Check if STMT performs a function call that can be vectorized. 
2974    If VEC_STMT is also passed, vectorize the STMT: create a vectorized 
2975    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2976    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
2977
2978 bool
2979 vectorizable_call (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
2980 {
2981   tree vec_dest;
2982   tree scalar_dest;
2983   tree operation;
2984   tree op, type;
2985   tree vec_oprnd0 = NULL_TREE, vec_oprnd1 = NULL_TREE;
2986   stmt_vec_info stmt_info = vinfo_for_stmt (stmt), prev_stmt_info;
2987   tree vectype_out, vectype_in;
2988   int nunits_in;
2989   int nunits_out;
2990   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2991   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2992   tree fndecl, rhs, new_temp, def, def_stmt, rhs_type, lhs_type;
2993   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
2994   tree new_stmt;
2995   int ncopies, j, nargs;
2996   call_expr_arg_iterator iter;
2997   tree vargs;
2998   enum { NARROW, NONE, WIDEN } modifier;
2999
3000   if (!STMT_VINFO_RELEVANT_P (stmt_info))
3001     return false;
3002
3003   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_loop_def)
3004     return false;
3005
3006   /* FORNOW: SLP not supported.  */
3007   if (STMT_SLP_TYPE (stmt_info))
3008     return false;
3009
3010   /* Is STMT a vectorizable call?   */
3011   if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
3012     return false;
3013
3014   if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) != SSA_NAME)
3015     return false;
3016
3017   operation = GIMPLE_STMT_OPERAND (stmt, 1);
3018   if (TREE_CODE (operation) != CALL_EXPR)
3019     return false;
3020
3021   /* Process function arguments.  */
3022   rhs_type = NULL_TREE;
3023   nargs = 0;
3024   FOR_EACH_CALL_EXPR_ARG (op, iter, operation)
3025     {
3026       /* Bail out if the function has more than two arguments, we
3027          do not have interesting builtin functions to vectorize with
3028          more than two arguments.  */
3029       if (nargs >= 2)
3030         return false;
3031
3032       /* We can only handle calls with arguments of the same type.  */
3033       if (rhs_type
3034           && rhs_type != TREE_TYPE (op))
3035         {
3036           if (vect_print_dump_info (REPORT_DETAILS))
3037             fprintf (vect_dump, "argument types differ.");
3038           return false;
3039         }
3040       rhs_type = TREE_TYPE (op);
3041
3042       if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt[nargs]))
3043         {
3044           if (vect_print_dump_info (REPORT_DETAILS))
3045             fprintf (vect_dump, "use not simple.");
3046           return false;
3047         }
3048
3049       ++nargs;
3050     }
3051
3052   /* No arguments is also not good.  */
3053   if (nargs == 0)
3054     return false;
3055
3056   vectype_in = get_vectype_for_scalar_type (rhs_type);
3057   if (!vectype_in)
3058     return false;
3059   nunits_in = TYPE_VECTOR_SUBPARTS (vectype_in);
3060
3061   lhs_type = TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 0));
3062   vectype_out = get_vectype_for_scalar_type (lhs_type);
3063   if (!vectype_out)
3064     return false;
3065   nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
3066
3067   /* FORNOW */
3068   if (nunits_in == nunits_out / 2)
3069     modifier = NARROW;
3070   else if (nunits_out == nunits_in)
3071     modifier = NONE;
3072   else if (nunits_out == nunits_in / 2)
3073     modifier = WIDEN;
3074   else
3075     return false;
3076
3077   /* For now, we only vectorize functions if a target specific builtin
3078      is available.  TODO -- in some cases, it might be profitable to
3079      insert the calls for pieces of the vector, in order to be able
3080      to vectorize other operations in the loop.  */
3081   fndecl = vectorizable_function (operation, vectype_out, vectype_in);
3082   if (fndecl == NULL_TREE)
3083     {
3084       if (vect_print_dump_info (REPORT_DETAILS))
3085         fprintf (vect_dump, "function is not vectorizable.");
3086
3087       return false;
3088     }
3089
3090   gcc_assert (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS));
3091
3092   if (modifier == NARROW)
3093     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_out;
3094   else
3095     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_in;
3096
3097   /* Sanity check: make sure that at least one copy of the vectorized stmt
3098      needs to be generated.  */
3099   gcc_assert (ncopies >= 1);
3100
3101   /* FORNOW. This restriction should be relaxed.  */
3102   if (nested_in_vect_loop_p (loop, stmt) && ncopies > 1)
3103     {
3104       if (vect_print_dump_info (REPORT_DETAILS))
3105       fprintf (vect_dump, "multiple types in nested loop.");
3106       return false;
3107     }
3108
3109   if (!vec_stmt) /* transformation not required.  */
3110     {
3111       STMT_VINFO_TYPE (stmt_info) = call_vec_info_type;
3112       if (vect_print_dump_info (REPORT_DETAILS))
3113         fprintf (vect_dump, "=== vectorizable_call ===");
3114       vect_model_simple_cost (stmt_info, ncopies, dt, NULL);
3115       return true;
3116     }
3117
3118   /** Transform.  **/
3119
3120   if (vect_print_dump_info (REPORT_DETAILS))
3121     fprintf (vect_dump, "transform operation.");
3122
3123   /* FORNOW. This restriction should be relaxed.  */
3124   if (nested_in_vect_loop_p (loop, stmt) && ncopies > 1)
3125     {
3126       if (vect_print_dump_info (REPORT_DETAILS))
3127         fprintf (vect_dump, "multiple types in nested loop.");
3128       return false;
3129     }
3130
3131   /* Handle def.  */
3132   scalar_dest = GIMPLE_STMT_OPERAND (stmt, 0);
3133   vec_dest = vect_create_destination_var (scalar_dest, vectype_out);
3134
3135   prev_stmt_info = NULL;
3136   switch (modifier)
3137     {
3138     case NONE:
3139       for (j = 0; j < ncopies; ++j)
3140         {
3141           /* Build argument list for the vectorized call.  */
3142           /* FIXME: Rewrite this so that it doesn't
3143              construct a temporary list.  */
3144           vargs = NULL_TREE;
3145           nargs = 0;
3146           FOR_EACH_CALL_EXPR_ARG (op, iter, operation)
3147             {
3148               if (j == 0)
3149                 vec_oprnd0
3150                   = vect_get_vec_def_for_operand (op, stmt, NULL);
3151               else
3152                 vec_oprnd0
3153                   = vect_get_vec_def_for_stmt_copy (dt[nargs], vec_oprnd0);
3154
3155               vargs = tree_cons (NULL_TREE, vec_oprnd0, vargs);
3156
3157               ++nargs;
3158             }
3159           vargs = nreverse (vargs);
3160
3161           rhs = build_function_call_expr (fndecl, vargs);
3162           new_stmt = build_gimple_modify_stmt (vec_dest, rhs);
3163           new_temp = make_ssa_name (vec_dest, new_stmt);
3164           GIMPLE_STMT_OPERAND (new_stmt, 0) = new_temp;
3165
3166           vect_finish_stmt_generation (stmt, new_stmt, bsi);
3167
3168           if (j == 0)
3169             STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
3170           else
3171             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
3172
3173           prev_stmt_info = vinfo_for_stmt (new_stmt);
3174         }
3175
3176       break;
3177
3178     case NARROW:
3179       for (j = 0; j < ncopies; ++j)
3180         {
3181           /* Build argument list for the vectorized call.  */
3182           /* FIXME: Rewrite this so that it doesn't
3183              construct a temporary list.  */
3184           vargs = NULL_TREE;
3185           nargs = 0;
3186           FOR_EACH_CALL_EXPR_ARG (op, iter, operation)
3187             {
3188               if (j == 0)
3189                 {
3190                   vec_oprnd0
3191                     = vect_get_vec_def_for_operand (op, stmt, NULL);
3192                   vec_oprnd1
3193                     = vect_get_vec_def_for_stmt_copy (dt[nargs], vec_oprnd0);
3194                 }
3195               else
3196                 {
3197                   vec_oprnd0
3198                     = vect_get_vec_def_for_stmt_copy (dt[nargs], vec_oprnd1);
3199                   vec_oprnd1
3200                     = vect_get_vec_def_for_stmt_copy (dt[nargs], vec_oprnd0);
3201                 }
3202
3203               vargs = tree_cons (NULL_TREE, vec_oprnd0, vargs);
3204               vargs = tree_cons (NULL_TREE, vec_oprnd1, vargs);
3205
3206               ++nargs;
3207             }
3208           vargs = nreverse (vargs);
3209
3210           rhs = build_function_call_expr (fndecl, vargs);
3211           new_stmt = build_gimple_modify_stmt (vec_dest, rhs);
3212           new_temp = make_ssa_name (vec_dest, new_stmt);
3213           GIMPLE_STMT_OPERAND (new_stmt, 0) = new_temp;
3214
3215           vect_finish_stmt_generation (stmt, new_stmt, bsi);
3216
3217           if (j == 0)
3218             STMT_VINFO_VEC_STMT (stmt_info) = new_stmt;
3219           else
3220             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
3221
3222           prev_stmt_info = vinfo_for_stmt (new_stmt);
3223         }
3224
3225       *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
3226
3227       break;
3228
3229     case WIDEN:
3230       /* No current target implements this case.  */
3231       return false;
3232     }
3233
3234   /* The call in STMT might prevent it from being removed in dce.
3235      We however cannot remove it here, due to the way the ssa name
3236      it defines is mapped to the new definition.  So just replace
3237      rhs of the statement with something harmless.  */
3238   type = TREE_TYPE (scalar_dest);
3239   GIMPLE_STMT_OPERAND (stmt, 1) = fold_convert (type, integer_zero_node);
3240   update_stmt (stmt);
3241
3242   return true;
3243 }
3244
3245
3246 /* Function vect_gen_widened_results_half
3247
3248    Create a vector stmt whose code, type, number of arguments, and result
3249    variable are CODE, VECTYPE, OP_TYPE, and VEC_DEST, and its arguments are 
3250    VEC_OPRND0 and VEC_OPRND1. The new vector stmt is to be inserted at BSI.
3251    In the case that CODE is a CALL_EXPR, this means that a call to DECL
3252    needs to be created (DECL is a function-decl of a target-builtin).
3253    STMT is the original scalar stmt that we are vectorizing.  */
3254
3255 static tree
3256 vect_gen_widened_results_half (enum tree_code code, tree vectype, tree decl,
3257                                tree vec_oprnd0, tree vec_oprnd1, int op_type,
3258                                tree vec_dest, block_stmt_iterator *bsi,
3259                                tree stmt)
3260
3261   tree expr; 
3262   tree new_stmt; 
3263   tree new_temp; 
3264   tree sym; 
3265   ssa_op_iter iter;
3266  
3267   /* Generate half of the widened result:  */ 
3268   if (code == CALL_EXPR) 
3269     {  
3270       /* Target specific support  */ 
3271       if (op_type == binary_op)
3272         expr = build_call_expr (decl, 2, vec_oprnd0, vec_oprnd1);
3273       else
3274         expr = build_call_expr (decl, 1, vec_oprnd0);
3275     } 
3276   else 
3277     { 
3278       /* Generic support */ 
3279       gcc_assert (op_type == TREE_CODE_LENGTH (code)); 
3280       if (op_type == binary_op) 
3281         expr = build2 (code, vectype, vec_oprnd0, vec_oprnd1); 
3282       else  
3283         expr = build1 (code, vectype, vec_oprnd0); 
3284     } 
3285   new_stmt = build_gimple_modify_stmt (vec_dest, expr);
3286   new_temp = make_ssa_name (vec_dest, new_stmt); 
3287   GIMPLE_STMT_OPERAND (new_stmt, 0) = new_temp; 
3288   vect_finish_stmt_generation (stmt, new_stmt, bsi); 
3289
3290   if (code == CALL_EXPR)
3291     {
3292       FOR_EACH_SSA_TREE_OPERAND (sym, new_stmt, iter, SSA_OP_ALL_VIRTUALS)
3293         {
3294           if (TREE_CODE (sym) == SSA_NAME)
3295             sym = SSA_NAME_VAR (sym);
3296           mark_sym_for_renaming (sym);
3297         }
3298     }
3299
3300   return new_stmt;
3301 }
3302
3303
3304 /* Check if STMT performs a conversion operation, that can be vectorized. 
3305    If VEC_STMT is also passed, vectorize the STMT: create a vectorized 
3306    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3307    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
3308
3309 bool
3310 vectorizable_conversion (tree stmt, block_stmt_iterator *bsi,
3311                          tree *vec_stmt, slp_tree slp_node)
3312 {
3313   tree vec_dest;
3314   tree scalar_dest;
3315   tree operation;
3316   tree op0;
3317   tree vec_oprnd0 = NULL_TREE, vec_oprnd1 = NULL_TREE;
3318   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3319   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3320   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
3321   enum tree_code code, code1 = ERROR_MARK, code2 = ERROR_MARK;
3322   tree decl1 = NULL_TREE, decl2 = NULL_TREE;
3323   tree new_temp;
3324   tree def, def_stmt;
3325   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
3326   tree new_stmt = NULL_TREE;
3327   stmt_vec_info prev_stmt_info;
3328   int nunits_in;
3329   int nunits_out;
3330   tree vectype_out, vectype_in;
3331   int ncopies, j;
3332   tree expr;
3333   tree rhs_type, lhs_type;
3334   tree builtin_decl;
3335   enum { NARROW, NONE, WIDEN } modifier;
3336   int i;
3337   VEC(tree,heap) *vec_oprnds0 = NULL;
3338   tree vop0;
3339
3340   /* Is STMT a vectorizable conversion?   */
3341
3342   if (!STMT_VINFO_RELEVANT_P (stmt_info))
3343     return false;
3344
3345   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_loop_def)
3346     return false;
3347
3348   if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
3349     return false;
3350
3351   if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) != SSA_NAME)
3352     return false;
3353
3354   operation = GIMPLE_STMT_OPERAND (stmt, 1);
3355   code = TREE_CODE (operation);
3356   if (code != FIX_TRUNC_EXPR && code != FLOAT_EXPR)
3357     return false;
3358
3359   /* Check types of lhs and rhs.  */
3360   op0 = TREE_OPERAND (operation, 0);
3361   rhs_type = TREE_TYPE (op0);
3362   vectype_in = get_vectype_for_scalar_type (rhs_type);
3363   if (!vectype_in)
3364     return false;
3365   nunits_in = TYPE_VECTOR_SUBPARTS (vectype_in);
3366
3367   scalar_dest = GIMPLE_STMT_OPERAND (stmt, 0);
3368   lhs_type = TREE_TYPE (scalar_dest);
3369   vectype_out = get_vectype_for_scalar_type (lhs_type);
3370   if (!vectype_out)
3371     return false;
3372   nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
3373
3374   /* FORNOW */
3375   if (nunits_in == nunits_out / 2)
3376     modifier = NARROW;
3377   else if (nunits_out == nunits_in)
3378     modifier = NONE;
3379   else if (nunits_out == nunits_in / 2)
3380     modifier = WIDEN;
3381   else
3382     return false;
3383
3384   if (modifier == NONE)
3385     gcc_assert (STMT_VINFO_VECTYPE (stmt_info) == vectype_out);
3386
3387   /* Bail out if the types are both integral or non-integral.  */
3388   if ((INTEGRAL_TYPE_P (rhs_type) && INTEGRAL_TYPE_P (lhs_type))
3389       || (!INTEGRAL_TYPE_P (rhs_type) && !INTEGRAL_TYPE_P (lhs_type)))
3390     return false;
3391
3392   if (modifier == NARROW)
3393     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_out;
3394   else
3395     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_in;
3396
3397   /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
3398      this, so we can safely override NCOPIES with 1 here.  */
3399   if (slp_node)
3400     ncopies = 1;
3401   
3402   /* Sanity check: make sure that at least one copy of the vectorized stmt
3403      needs to be generated.  */
3404   gcc_assert (ncopies >= 1);
3405
3406   /* FORNOW. This restriction should be relaxed.  */
3407   if (nested_in_vect_loop_p (loop, stmt) && ncopies > 1)
3408     {
3409       if (vect_print_dump_info (REPORT_DETAILS))
3410       fprintf (vect_dump, "multiple types in nested loop.");
3411       return false;
3412     }
3413
3414   /* Check the operands of the operation.  */
3415   if (!vect_is_simple_use (op0, loop_vinfo, &def_stmt, &def, &dt[0]))
3416     {
3417       if (vect_print_dump_info (REPORT_DETAILS))
3418         fprintf (vect_dump, "use not simple.");
3419       return false;
3420     }
3421
3422   /* Supportable by target?  */
3423   if ((modifier == NONE
3424        && !targetm.vectorize.builtin_conversion (code, vectype_in))
3425       || (modifier == WIDEN
3426           && !supportable_widening_operation (code, stmt, vectype_in,
3427                                               &decl1, &decl2,
3428                                               &code1, &code2))
3429       || (modifier == NARROW
3430           && !supportable_narrowing_operation (code, stmt, vectype_in,
3431                                                &code1)))
3432     {
3433       if (vect_print_dump_info (REPORT_DETAILS))
3434         fprintf (vect_dump, "op not supported by target.");
3435       return false;
3436     }
3437
3438   if (modifier != NONE)
3439     {
3440       STMT_VINFO_VECTYPE (stmt_info) = vectype_in;
3441       /* FORNOW: SLP not supported.  */
3442       if (STMT_SLP_TYPE (stmt_info))
3443         return false;      
3444     }
3445
3446   if (!vec_stmt)                /* transformation not required.  */
3447     {
3448       STMT_VINFO_TYPE (stmt_info) = type_conversion_vec_info_type;
3449       return true;
3450     }
3451
3452   /** Transform.  **/
3453   if (vect_print_dump_info (REPORT_DETAILS))
3454     fprintf (vect_dump, "transform conversion.");
3455
3456   /* Handle def.  */
3457   vec_dest = vect_create_destination_var (scalar_dest, vectype_out);
3458
3459   if (modifier == NONE && !slp_node)
3460     vec_oprnds0 = VEC_alloc (tree, heap, 1);
3461
3462   prev_stmt_info = NULL;
3463   switch (modifier)
3464     {
3465     case NONE:
3466       for (j = 0; j < ncopies; j++)
3467         {
3468           tree sym;
3469           ssa_op_iter iter;
3470
3471           if (j == 0)
3472             vect_get_vec_defs (op0, NULL, stmt, &vec_oprnds0, NULL, slp_node);
3473           else
3474             vect_get_vec_defs_for_stmt_copy (dt, &vec_oprnds0, NULL);
3475
3476           builtin_decl =
3477             targetm.vectorize.builtin_conversion (code, vectype_in);
3478           for (i = 0; VEC_iterate (tree, vec_oprnds0, i, vop0); i++)
3479             { 
3480               new_stmt = build_call_expr (builtin_decl, 1, vop0);
3481
3482               /* Arguments are ready. create the new vector stmt.  */
3483               new_stmt = build_gimple_modify_stmt (vec_dest, new_stmt);
3484               new_temp = make_ssa_name (vec_dest, new_stmt);
3485               GIMPLE_STMT_OPERAND (new_stmt, 0) = new_temp;
3486               vect_finish_stmt_generation (stmt, new_stmt, bsi);
3487               FOR_EACH_SSA_TREE_OPERAND (sym, new_stmt, iter, 
3488                                          SSA_OP_ALL_VIRTUALS)
3489                 {
3490                   if (TREE_CODE (sym) == SSA_NAME)
3491                     sym = SSA_NAME_VAR (sym);
3492                   mark_sym_for_renaming (sym);
3493                 }
3494               if (slp_node)
3495                 VEC_quick_push (tree, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
3496             }
3497
3498           if (j == 0)
3499             STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
3500           else
3501             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
3502           prev_stmt_info = vinfo_for_stmt (new_stmt);
3503         }
3504       break;
3505
3506     case WIDEN:
3507       /* In case the vectorization factor (VF) is bigger than the number
3508          of elements that we can fit in a vectype (nunits), we have to
3509          generate more than one vector stmt - i.e - we need to "unroll"
3510          the vector stmt by a factor VF/nunits.  */
3511       for (j = 0; j < ncopies; j++)
3512         {
3513           if (j == 0)
3514             vec_oprnd0 = vect_get_vec_def_for_operand (op0, stmt, NULL);
3515           else
3516             vec_oprnd0 = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd0);
3517
3518           STMT_VINFO_VECTYPE (stmt_info) = vectype_in;
3519
3520           /* Generate first half of the widened result:  */
3521           new_stmt
3522             = vect_gen_widened_results_half (code1, vectype_out, decl1, 
3523                                              vec_oprnd0, vec_oprnd1,
3524                                              unary_op, vec_dest, bsi, stmt);
3525           if (j == 0)
3526             STMT_VINFO_VEC_STMT (stmt_info) = new_stmt;
3527           else
3528             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
3529           prev_stmt_info = vinfo_for_stmt (new_stmt);
3530
3531           /* Generate second half of the widened result:  */
3532           new_stmt
3533             = vect_gen_widened_results_half (code2, vectype_out, decl2,
3534                                              vec_oprnd0, vec_oprnd1,
3535                                              unary_op, vec_dest, bsi, stmt);
3536           STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
3537           prev_stmt_info = vinfo_for_stmt (new_stmt);
3538         }
3539       break;
3540
3541     case NARROW:
3542       /* In case the vectorization factor (VF) is bigger than the number
3543          of elements that we can fit in a vectype (nunits), we have to
3544          generate more than one vector stmt - i.e - we need to "unroll"
3545          the vector stmt by a factor VF/nunits.  */
3546       for (j = 0; j < ncopies; j++)
3547         {
3548           /* Handle uses.  */
3549           if (j == 0)
3550             {
3551               vec_oprnd0 = vect_get_vec_def_for_operand (op0, stmt, NULL);
3552               vec_oprnd1 = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd0);
3553             }
3554           else
3555             {
3556               vec_oprnd0 = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd1);
3557               vec_oprnd1 = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd0);
3558             }
3559
3560           /* Arguments are ready. Create the new vector stmt.  */
3561           expr = build2 (code1, vectype_out, vec_oprnd0, vec_oprnd1);
3562           new_stmt = build_gimple_modify_stmt (vec_dest, expr);
3563           new_temp = make_ssa_name (vec_dest, new_stmt);
3564           GIMPLE_STMT_OPERAND (new_stmt, 0) = new_temp;
3565           vect_finish_stmt_generation (stmt, new_stmt, bsi);
3566
3567           if (j == 0)
3568             STMT_VINFO_VEC_STMT (stmt_info) = new_stmt;
3569           else
3570             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
3571
3572           prev_stmt_info = vinfo_for_stmt (new_stmt);
3573         }
3574
3575       *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
3576     }
3577
3578   return true;
3579 }
3580
3581
3582 /* Function vectorizable_assignment.
3583
3584    Check if STMT performs an assignment (copy) that can be vectorized. 
3585    If VEC_STMT is also passed, vectorize the STMT: create a vectorized 
3586    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3587    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
3588
3589 bool
3590 vectorizable_assignment (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt, 
3591                          slp_tree slp_node)
3592 {
3593   tree vec_dest;
3594   tree scalar_dest;
3595   tree op;
3596   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3597   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
3598   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3599   tree new_temp;
3600   tree def, def_stmt;
3601   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
3602   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
3603   int ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
3604   int i;
3605   VEC(tree,heap) *vec_oprnds = NULL;
3606   tree vop;
3607
3608   gcc_assert (ncopies >= 1);
3609   if (ncopies > 1)
3610     return false; /* FORNOW */
3611
3612   if (!STMT_VINFO_RELEVANT_P (stmt_info))
3613     return false;
3614
3615   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_loop_def)
3616     return false;
3617
3618   /* Is vectorizable assignment?  */
3619   if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
3620     return false;
3621
3622   scalar_dest = GIMPLE_STMT_OPERAND (stmt, 0);
3623   if (TREE_CODE (scalar_dest) != SSA_NAME)
3624     return false;
3625
3626   op = GIMPLE_STMT_OPERAND (stmt, 1);
3627   if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt[0]))
3628     {
3629       if (vect_print_dump_info (REPORT_DETAILS))
3630         fprintf (vect_dump, "use not simple.");
3631       return false;
3632     }
3633
3634   if (!vec_stmt) /* transformation not required.  */
3635     {
3636       STMT_VINFO_TYPE (stmt_info) = assignment_vec_info_type;
3637       if (vect_print_dump_info (REPORT_DETAILS))
3638         fprintf (vect_dump, "=== vectorizable_assignment ===");
3639       vect_model_simple_cost (stmt_info, ncopies, dt, NULL);
3640       return true;
3641     }
3642
3643   /** Transform.  **/
3644   if (vect_print_dump_info (REPORT_DETAILS))
3645     fprintf (vect_dump, "transform assignment.");
3646
3647   /* Handle def.  */
3648   vec_dest = vect_create_destination_var (scalar_dest, vectype);
3649
3650   /* Handle use.  */
3651   vect_get_vec_defs (op, NULL, stmt, &vec_oprnds, NULL, slp_node);
3652
3653   /* Arguments are ready. create the new vector stmt.  */
3654   for (i = 0; VEC_iterate (tree, vec_oprnds, i, vop); i++)
3655     {
3656       *vec_stmt = build_gimple_modify_stmt (vec_dest, vop);
3657       new_temp = make_ssa_name (vec_dest, *vec_stmt);
3658       GIMPLE_STMT_OPERAND (*vec_stmt, 0) = new_temp;
3659       vect_finish_stmt_generation (stmt, *vec_stmt, bsi);
3660       STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt;
3661
3662       if (slp_node)
3663         VEC_quick_push (tree, SLP_TREE_VEC_STMTS (slp_node), *vec_stmt);
3664    }
3665   
3666   VEC_free (tree, heap, vec_oprnds);       
3667   return true;
3668 }
3669
3670
3671 /* Function vect_min_worthwhile_factor.
3672
3673    For a loop where we could vectorize the operation indicated by CODE,
3674    return the minimum vectorization factor that makes it worthwhile
3675    to use generic vectors.  */
3676 static int
3677 vect_min_worthwhile_factor (enum tree_code code)
3678 {
3679   switch (code)
3680     {
3681     case PLUS_EXPR:
3682     case MINUS_EXPR:
3683     case NEGATE_EXPR:
3684       return 4;
3685
3686     case BIT_AND_EXPR:
3687     case BIT_IOR_EXPR:
3688     case BIT_XOR_EXPR:
3689     case BIT_NOT_EXPR:
3690       return 2;
3691
3692     default:
3693       return INT_MAX;
3694     }
3695 }
3696
3697
3698 /* Function vectorizable_induction
3699
3700    Check if PHI performs an induction computation that can be vectorized.
3701    If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
3702    phi to replace it, put it in VEC_STMT, and add it to the same basic block.
3703    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
3704
3705 bool
3706 vectorizable_induction (tree phi, block_stmt_iterator *bsi ATTRIBUTE_UNUSED,
3707                         tree *vec_stmt)
3708 {
3709   stmt_vec_info stmt_info = vinfo_for_stmt (phi);
3710   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
3711   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3712   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
3713   int ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
3714   tree vec_def;
3715
3716   gcc_assert (ncopies >= 1);
3717
3718   if (!STMT_VINFO_RELEVANT_P (stmt_info))
3719     return false;
3720
3721   /* FORNOW: SLP not supported.  */
3722   if (STMT_SLP_TYPE (stmt_info))
3723     return false;
3724
3725   gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def);
3726
3727   if (TREE_CODE (phi) != PHI_NODE)
3728     return false;
3729
3730   if (!vec_stmt) /* transformation not required.  */
3731     {
3732       STMT_VINFO_TYPE (stmt_info) = induc_vec_info_type;
3733       if (vect_print_dump_info (REPORT_DETAILS))
3734         fprintf (vect_dump, "=== vectorizable_induction ===");
3735       vect_model_induction_cost (stmt_info, ncopies);
3736       return true;
3737     }
3738
3739   /** Transform.  **/
3740
3741   if (vect_print_dump_info (REPORT_DETAILS))
3742     fprintf (vect_dump, "transform induction phi.");
3743
3744   vec_def = get_initial_def_for_induction (phi);
3745   *vec_stmt = SSA_NAME_DEF_STMT (vec_def);
3746   return true;
3747 }
3748
3749
3750 /* Function vectorizable_operation.
3751
3752    Check if STMT performs a binary or unary operation that can be vectorized. 
3753    If VEC_STMT is also passed, vectorize the STMT: create a vectorized 
3754    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3755    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
3756
3757 bool
3758 vectorizable_operation (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt, 
3759                         slp_tree slp_node)
3760 {
3761   tree vec_dest;
3762   tree scalar_dest;
3763   tree operation;
3764   tree op0, op1 = NULL;
3765   tree vec_oprnd1 = NULL_TREE;
3766   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3767   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
3768   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3769   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
3770   enum tree_code code;
3771   enum machine_mode vec_mode;
3772   tree new_temp;
3773   int op_type;
3774   optab optab;
3775   int icode;
3776   enum machine_mode optab_op2_mode;
3777   tree def, def_stmt;
3778   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
3779   tree new_stmt = NULL_TREE;
3780   stmt_vec_info prev_stmt_info;
3781   int nunits_in = TYPE_VECTOR_SUBPARTS (vectype);
3782   int nunits_out;
3783   tree vectype_out;
3784   int ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_in;
3785   int j, i;
3786   VEC(tree,heap) *vec_oprnds0 = NULL, *vec_oprnds1 = NULL;
3787   tree vop0, vop1;
3788   unsigned int k;
3789   bool scalar_shift_arg = false;
3790
3791   /* FORNOW: SLP with multiple types is not supported. The SLP analysis verifies
3792      this, so we can safely override NCOPIES with 1 here.  */
3793   if (slp_node)
3794     ncopies = 1;
3795   gcc_assert (ncopies >= 1);
3796   /* FORNOW. This restriction should be relaxed.  */
3797   if (nested_in_vect_loop_p (loop, stmt) && ncopies > 1)
3798     {
3799       if (vect_print_dump_info (REPORT_DETAILS))
3800         fprintf (vect_dump, "multiple types in nested loop.");
3801       return false;
3802     }
3803
3804   if (!STMT_VINFO_RELEVANT_P (stmt_info))
3805     return false;
3806
3807   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_loop_def)
3808     return false;
3809
3810   /* Is STMT a vectorizable binary/unary operation?   */
3811   if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
3812     return false;
3813
3814   if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) != SSA_NAME)
3815     return false;
3816
3817   scalar_dest = GIMPLE_STMT_OPERAND (stmt, 0);
3818   vectype_out = get_vectype_for_scalar_type (TREE_TYPE (scalar_dest));
3819   if (!vectype_out)
3820     return false;
3821   nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
3822   if (nunits_out != nunits_in)
3823     return false;
3824
3825   operation = GIMPLE_STMT_OPERAND (stmt, 1);
3826   code = TREE_CODE (operation);
3827
3828   /* For pointer addition, we should use the normal plus for
3829      the vector addition.  */
3830   if (code == POINTER_PLUS_EXPR)
3831     code = PLUS_EXPR;
3832
3833   optab = optab_for_tree_code (code, vectype);
3834
3835   /* Support only unary or binary operations.  */
3836   op_type = TREE_OPERAND_LENGTH (operation);
3837   if (op_type != unary_op && op_type != binary_op)
3838     {
3839       if (vect_print_dump_info (REPORT_DETAILS))
3840         fprintf (vect_dump, "num. args = %d (not unary/binary op).", op_type);
3841       return false;
3842     }
3843
3844   op0 = TREE_OPERAND (operation, 0);
3845   if (!vect_is_simple_use (op0, loop_vinfo, &def_stmt, &def, &dt[0]))
3846     {
3847       if (vect_print_dump_info (REPORT_DETAILS))
3848         fprintf (vect_dump, "use not simple.");
3849       return false;
3850     }
3851
3852   if (op_type == binary_op)
3853     {
3854       op1 = TREE_OPERAND (operation, 1);
3855       if (!vect_is_simple_use (op1, loop_vinfo, &def_stmt, &def, &dt[1]))
3856         {
3857           if (vect_print_dump_info (REPORT_DETAILS))
3858             fprintf (vect_dump, "use not simple.");
3859           return false;
3860         }
3861     }
3862
3863   /* Supportable by target?  */
3864   if (!optab)
3865     {
3866       if (vect_print_dump_info (REPORT_DETAILS))
3867         fprintf (vect_dump, "no optab.");
3868       return false;
3869     }
3870   vec_mode = TYPE_MODE (vectype);
3871   icode = (int) optab_handler (optab, vec_mode)->insn_code;
3872   if (icode == CODE_FOR_nothing)
3873     {
3874       if (vect_print_dump_info (REPORT_DETAILS))
3875         fprintf (vect_dump, "op not supported by target.");
3876       /* Check only during analysis.  */
3877       if (GET_MODE_SIZE (vec_mode) != UNITS_PER_WORD
3878           || (LOOP_VINFO_VECT_FACTOR (loop_vinfo)
3879               < vect_min_worthwhile_factor (code)
3880               && !vec_stmt))
3881         return false;
3882       if (vect_print_dump_info (REPORT_DETAILS))
3883         fprintf (vect_dump, "proceeding using word mode.");
3884     }
3885
3886   /* Worthwhile without SIMD support? Check only during analysis.  */
3887   if (!VECTOR_MODE_P (TYPE_MODE (vectype))
3888       && LOOP_VINFO_VECT_FACTOR (loop_vinfo)
3889          < vect_min_worthwhile_factor (code)
3890       && !vec_stmt)
3891     {
3892       if (vect_print_dump_info (REPORT_DETAILS))
3893         fprintf (vect_dump, "not worthwhile without SIMD support.");
3894       return false;
3895     }
3896
3897   if (code == LSHIFT_EXPR || code == RSHIFT_EXPR)
3898     {
3899       /* FORNOW: not yet supported.  */
3900       if (!VECTOR_MODE_P (vec_mode))
3901         return false;
3902
3903       /* Invariant argument is needed for a vector shift
3904          by a scalar shift operand.  */
3905       optab_op2_mode = insn_data[icode].operand[2].mode;
3906       if (!VECTOR_MODE_P (optab_op2_mode))
3907         {
3908           if (dt[1] != vect_constant_def && dt[1] != vect_invariant_def)
3909             {
3910               if (vect_print_dump_info (REPORT_DETAILS))
3911                 fprintf (vect_dump, "operand mode requires invariant"
3912                                     " argument.");
3913               return false;
3914             }
3915
3916           scalar_shift_arg = true;
3917         }
3918     }
3919
3920   if (!vec_stmt) /* transformation not required.  */
3921     {
3922       STMT_VINFO_TYPE (stmt_info) = op_vec_info_type;
3923       if (vect_print_dump_info (REPORT_DETAILS))
3924         fprintf (vect_dump, "=== vectorizable_operation ===");
3925       vect_model_simple_cost (stmt_info, ncopies, dt, NULL);
3926       return true;
3927     }
3928
3929   /** Transform.  **/
3930
3931   if (vect_print_dump_info (REPORT_DETAILS))
3932     fprintf (vect_dump, "transform binary/unary operation.");
3933
3934   /* Handle def.  */
3935   vec_dest = vect_create_destination_var (scalar_dest, vectype);
3936
3937   /* Allocate VECs for vector operands. In case of SLP, vector operands are 
3938      created in the previous stages of the recursion, so no allocation is
3939      needed, except for the case of shift with scalar shift argument. In that
3940      case we store the scalar operand in VEC_OPRNDS1 for every vector stmt to
3941      be created to vectorize the SLP group, i.e., SLP_NODE->VEC_STMTS_SIZE.
3942      In case of loop-based vectorization we allocate VECs of size 1. We 
3943      allocate VEC_OPRNDS1 only in case of binary operation.  */ 
3944   if (!slp_node)
3945     {
3946       vec_oprnds0 = VEC_alloc (tree, heap, 1);
3947       if (op_type == binary_op)
3948         vec_oprnds1 = VEC_alloc (tree, heap, 1);
3949     }
3950   else if (scalar_shift_arg)
3951     vec_oprnds1 = VEC_alloc (tree, heap, slp_node->vec_stmts_size);  
3952
3953   /* In case the vectorization factor (VF) is bigger than the number
3954      of elements that we can fit in a vectype (nunits), we have to generate
3955      more than one vector stmt - i.e - we need to "unroll" the
3956      vector stmt by a factor VF/nunits. In doing so, we record a pointer
3957      from one copy of the vector stmt to the next, in the field
3958      STMT_VINFO_RELATED_STMT. This is necessary in order to allow following
3959      stages to find the correct vector defs to be used when vectorizing
3960      stmts that use the defs of the current stmt. The example below illustrates
3961      the vectorization process when VF=16 and nunits=4 (i.e - we need to create
3962      4 vectorized stmts):
3963
3964      before vectorization:
3965                                 RELATED_STMT    VEC_STMT
3966         S1:     x = memref      -               -
3967         S2:     z = x + 1       -               -
3968
3969      step 1: vectorize stmt S1 (done in vectorizable_load. See more details
3970              there):
3971                                 RELATED_STMT    VEC_STMT
3972         VS1_0:  vx0 = memref0   VS1_1           -
3973         VS1_1:  vx1 = memref1   VS1_2           -
3974         VS1_2:  vx2 = memref2   VS1_3           -
3975         VS1_3:  vx3 = memref3   -               -
3976         S1:     x = load        -               VS1_0
3977         S2:     z = x + 1       -               -
3978
3979      step2: vectorize stmt S2 (done here):