OSDN Git Service

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