OSDN Git Service

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