remove unused files
[platform/upstream/gcc48.git] / gcc / tree-vect-data-refs.c
1 /* Data References Analysis and Manipulation Utilities for Vectorization.
2    Copyright (C) 2003-2013 Free Software Foundation, Inc.
3    Contributed by Dorit Naishlos <dorit@il.ibm.com>
4    and Ira Rosen <irar@il.ibm.com>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "dumpfile.h"
26 #include "tm.h"
27 #include "ggc.h"
28 #include "tree.h"
29 #include "tm_p.h"
30 #include "target.h"
31 #include "basic-block.h"
32 #include "gimple-pretty-print.h"
33 #include "tree-flow.h"
34 #include "dumpfile.h"
35 #include "cfgloop.h"
36 #include "tree-chrec.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-vectorizer.h"
39 #include "diagnostic-core.h"
40
41 /* Need to include rtl.h, expr.h, etc. for optabs.  */
42 #include "expr.h"
43 #include "optabs.h"
44
45 /* Return true if load- or store-lanes optab OPTAB is implemented for
46    COUNT vectors of type VECTYPE.  NAME is the name of OPTAB.  */
47
48 static bool
49 vect_lanes_optab_supported_p (const char *name, convert_optab optab,
50                               tree vectype, unsigned HOST_WIDE_INT count)
51 {
52   enum machine_mode mode, array_mode;
53   bool limit_p;
54
55   mode = TYPE_MODE (vectype);
56   limit_p = !targetm.array_mode_supported_p (mode, count);
57   array_mode = mode_for_size (count * GET_MODE_BITSIZE (mode),
58                               MODE_INT, limit_p);
59
60   if (array_mode == BLKmode)
61     {
62       if (dump_enabled_p ())
63         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
64                          "no array mode for %s[" HOST_WIDE_INT_PRINT_DEC "]",
65                          GET_MODE_NAME (mode), count);
66       return false;
67     }
68
69   if (convert_optab_handler (optab, array_mode, mode) == CODE_FOR_nothing)
70     {
71       if (dump_enabled_p ())
72         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
73                          "cannot use %s<%s><%s>", name,
74                          GET_MODE_NAME (array_mode), GET_MODE_NAME (mode));
75       return false;
76     }
77
78   if (dump_enabled_p ())
79     dump_printf_loc (MSG_NOTE, vect_location,
80                      "can use %s<%s><%s>", name, GET_MODE_NAME (array_mode),
81                      GET_MODE_NAME (mode));
82
83   return true;
84 }
85
86
87 /* Return the smallest scalar part of STMT.
88    This is used to determine the vectype of the stmt.  We generally set the
89    vectype according to the type of the result (lhs).  For stmts whose
90    result-type is different than the type of the arguments (e.g., demotion,
91    promotion), vectype will be reset appropriately (later).  Note that we have
92    to visit the smallest datatype in this function, because that determines the
93    VF.  If the smallest datatype in the loop is present only as the rhs of a
94    promotion operation - we'd miss it.
95    Such a case, where a variable of this datatype does not appear in the lhs
96    anywhere in the loop, can only occur if it's an invariant: e.g.:
97    'int_x = (int) short_inv', which we'd expect to have been optimized away by
98    invariant motion.  However, we cannot rely on invariant motion to always
99    take invariants out of the loop, and so in the case of promotion we also
100    have to check the rhs.
101    LHS_SIZE_UNIT and RHS_SIZE_UNIT contain the sizes of the corresponding
102    types.  */
103
104 tree
105 vect_get_smallest_scalar_type (gimple stmt, HOST_WIDE_INT *lhs_size_unit,
106                                HOST_WIDE_INT *rhs_size_unit)
107 {
108   tree scalar_type = gimple_expr_type (stmt);
109   HOST_WIDE_INT lhs, rhs;
110
111   lhs = rhs = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type));
112
113   if (is_gimple_assign (stmt)
114       && (gimple_assign_cast_p (stmt)
115           || gimple_assign_rhs_code (stmt) == WIDEN_MULT_EXPR
116           || gimple_assign_rhs_code (stmt) == WIDEN_LSHIFT_EXPR
117           || gimple_assign_rhs_code (stmt) == FLOAT_EXPR))
118     {
119       tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (stmt));
120
121       rhs = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (rhs_type));
122       if (rhs < lhs)
123         scalar_type = rhs_type;
124     }
125
126   *lhs_size_unit = lhs;
127   *rhs_size_unit = rhs;
128   return scalar_type;
129 }
130
131
132 /* Find the place of the data-ref in STMT in the interleaving chain that starts
133    from FIRST_STMT.  Return -1 if the data-ref is not a part of the chain.  */
134
135 int
136 vect_get_place_in_interleaving_chain (gimple stmt, gimple first_stmt)
137 {
138   gimple next_stmt = first_stmt;
139   int result = 0;
140
141   if (first_stmt != GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
142     return -1;
143
144   while (next_stmt && next_stmt != stmt)
145     {
146       result++;
147       next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
148     }
149
150   if (next_stmt)
151     return result;
152   else
153     return -1;
154 }
155
156
157 /* Function vect_insert_into_interleaving_chain.
158
159    Insert DRA into the interleaving chain of DRB according to DRA's INIT.  */
160
161 static void
162 vect_insert_into_interleaving_chain (struct data_reference *dra,
163                                      struct data_reference *drb)
164 {
165   gimple prev, next;
166   tree next_init;
167   stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
168   stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
169
170   prev = GROUP_FIRST_ELEMENT (stmtinfo_b);
171   next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
172   while (next)
173     {
174       next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
175       if (tree_int_cst_compare (next_init, DR_INIT (dra)) > 0)
176         {
177           /* Insert here.  */
178           GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = DR_STMT (dra);
179           GROUP_NEXT_ELEMENT (stmtinfo_a) = next;
180           return;
181         }
182       prev = next;
183       next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
184     }
185
186   /* We got to the end of the list. Insert here.  */
187   GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = DR_STMT (dra);
188   GROUP_NEXT_ELEMENT (stmtinfo_a) = NULL;
189 }
190
191
192 /* Function vect_update_interleaving_chain.
193
194    For two data-refs DRA and DRB that are a part of a chain interleaved data
195    accesses, update the interleaving chain.  DRB's INIT is smaller than DRA's.
196
197    There are four possible cases:
198    1. New stmts - both DRA and DRB are not a part of any chain:
199       FIRST_DR = DRB
200       NEXT_DR (DRB) = DRA
201    2. DRB is a part of a chain and DRA is not:
202       no need to update FIRST_DR
203       no need to insert DRB
204       insert DRA according to init
205    3. DRA is a part of a chain and DRB is not:
206       if (init of FIRST_DR > init of DRB)
207           FIRST_DR = DRB
208           NEXT(FIRST_DR) = previous FIRST_DR
209       else
210           insert DRB according to its init
211    4. both DRA and DRB are in some interleaving chains:
212       choose the chain with the smallest init of FIRST_DR
213       insert the nodes of the second chain into the first one.  */
214
215 static void
216 vect_update_interleaving_chain (struct data_reference *drb,
217                                 struct data_reference *dra)
218 {
219   stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
220   stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
221   tree next_init, init_dra_chain, init_drb_chain;
222   gimple first_a, first_b;
223   tree node_init;
224   gimple node, prev, next, first_stmt;
225
226   /* 1. New stmts - both DRA and DRB are not a part of any chain.   */
227   if (!GROUP_FIRST_ELEMENT (stmtinfo_a) && !GROUP_FIRST_ELEMENT (stmtinfo_b))
228     {
229       GROUP_FIRST_ELEMENT (stmtinfo_a) = DR_STMT (drb);
230       GROUP_FIRST_ELEMENT (stmtinfo_b) = DR_STMT (drb);
231       GROUP_NEXT_ELEMENT (stmtinfo_b) = DR_STMT (dra);
232       return;
233     }
234
235   /* 2. DRB is a part of a chain and DRA is not.  */
236   if (!GROUP_FIRST_ELEMENT (stmtinfo_a) && GROUP_FIRST_ELEMENT (stmtinfo_b))
237     {
238       GROUP_FIRST_ELEMENT (stmtinfo_a) = GROUP_FIRST_ELEMENT (stmtinfo_b);
239       /* Insert DRA into the chain of DRB.  */
240       vect_insert_into_interleaving_chain (dra, drb);
241       return;
242     }
243
244   /* 3. DRA is a part of a chain and DRB is not.  */
245   if (GROUP_FIRST_ELEMENT (stmtinfo_a) && !GROUP_FIRST_ELEMENT (stmtinfo_b))
246     {
247       gimple old_first_stmt = GROUP_FIRST_ELEMENT (stmtinfo_a);
248       tree init_old = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (
249                                                               old_first_stmt)));
250       gimple tmp;
251
252       if (tree_int_cst_compare (init_old, DR_INIT (drb)) > 0)
253         {
254           /* DRB's init is smaller than the init of the stmt previously marked
255              as the first stmt of the interleaving chain of DRA.  Therefore, we
256              update FIRST_STMT and put DRB in the head of the list.  */
257           GROUP_FIRST_ELEMENT (stmtinfo_b) = DR_STMT (drb);
258           GROUP_NEXT_ELEMENT (stmtinfo_b) = old_first_stmt;
259
260           /* Update all the stmts in the list to point to the new FIRST_STMT.  */
261           tmp = old_first_stmt;
262           while (tmp)
263             {
264               GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp)) = DR_STMT (drb);
265               tmp = GROUP_NEXT_ELEMENT (vinfo_for_stmt (tmp));
266             }
267         }
268       else
269         {
270           /* Insert DRB in the list of DRA.  */
271           vect_insert_into_interleaving_chain (drb, dra);
272           GROUP_FIRST_ELEMENT (stmtinfo_b) = GROUP_FIRST_ELEMENT (stmtinfo_a);
273         }
274       return;
275     }
276
277   /* 4. both DRA and DRB are in some interleaving chains.  */
278   first_a = GROUP_FIRST_ELEMENT (stmtinfo_a);
279   first_b = GROUP_FIRST_ELEMENT (stmtinfo_b);
280   if (first_a == first_b)
281     return;
282   init_dra_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_a)));
283   init_drb_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_b)));
284
285   if (tree_int_cst_compare (init_dra_chain, init_drb_chain) > 0)
286     {
287       /* Insert the nodes of DRA chain into the DRB chain.
288          After inserting a node, continue from this node of the DRB chain (don't
289          start from the beginning.  */
290       node = GROUP_FIRST_ELEMENT (stmtinfo_a);
291       prev = GROUP_FIRST_ELEMENT (stmtinfo_b);
292       first_stmt = first_b;
293     }
294   else
295     {
296       /* Insert the nodes of DRB chain into the DRA chain.
297          After inserting a node, continue from this node of the DRA chain (don't
298          start from the beginning.  */
299       node = GROUP_FIRST_ELEMENT (stmtinfo_b);
300       prev = GROUP_FIRST_ELEMENT (stmtinfo_a);
301       first_stmt = first_a;
302     }
303
304   while (node)
305     {
306       node_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (node)));
307       next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
308       while (next)
309         {
310           next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
311           if (tree_int_cst_compare (next_init, node_init) > 0)
312             {
313               /* Insert here.  */
314               GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = node;
315               GROUP_NEXT_ELEMENT (vinfo_for_stmt (node)) = next;
316               prev = node;
317               break;
318             }
319           prev = next;
320           next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
321         }
322       if (!next)
323         {
324           /* We got to the end of the list. Insert here.  */
325           GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = node;
326           GROUP_NEXT_ELEMENT (vinfo_for_stmt (node)) = NULL;
327           prev = node;
328         }
329       GROUP_FIRST_ELEMENT (vinfo_for_stmt (node)) = first_stmt;
330       node = GROUP_NEXT_ELEMENT (vinfo_for_stmt (node));
331     }
332 }
333
334 /* Check dependence between DRA and DRB for basic block vectorization.
335    If the accesses share same bases and offsets, we can compare their initial
336    constant offsets to decide whether they differ or not.  In case of a read-
337    write dependence we check that the load is before the store to ensure that
338    vectorization will not change the order of the accesses.  */
339
340 static bool
341 vect_drs_dependent_in_basic_block (struct data_reference *dra,
342                                    struct data_reference *drb)
343 {
344   HOST_WIDE_INT type_size_a, type_size_b, init_a, init_b;
345   gimple earlier_stmt;
346
347   /* We only call this function for pairs of loads and stores, but we verify
348      it here.  */
349   if (DR_IS_READ (dra) == DR_IS_READ (drb))
350     {
351       if (DR_IS_READ (dra))
352         return false;
353       else
354         return true;
355     }
356
357   /* Check that the data-refs have same bases and offsets.  If not, we can't
358      determine if they are dependent.  */
359   if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
360       || !dr_equal_offsets_p (dra, drb))
361     return true;
362
363   /* Check the types.  */
364   type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
365   type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
366
367   if (type_size_a != type_size_b
368       || !types_compatible_p (TREE_TYPE (DR_REF (dra)),
369                               TREE_TYPE (DR_REF (drb))))
370     return true;
371
372   init_a = TREE_INT_CST_LOW (DR_INIT (dra));
373   init_b = TREE_INT_CST_LOW (DR_INIT (drb));
374
375   /* Two different locations - no dependence.  */
376   if (init_a != init_b)
377     return false;
378
379   /* We have a read-write dependence.  Check that the load is before the store.
380      When we vectorize basic blocks, vector load can be only before 
381      corresponding scalar load, and vector store can be only after its
382      corresponding scalar store.  So the order of the acceses is preserved in
383      case the load is before the store.  */
384   earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));   
385   if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
386     return false;
387
388   return true;
389 }
390
391
392 /* Function vect_check_interleaving.
393
394    Check if DRA and DRB are a part of interleaving.  In case they are, insert
395    DRA and DRB in an interleaving chain.  */
396
397 static bool
398 vect_check_interleaving (struct data_reference *dra,
399                          struct data_reference *drb)
400 {
401   HOST_WIDE_INT type_size_a, type_size_b, diff_mod_size, step, init_a, init_b;
402
403   /* Check that the data-refs have same first location (except init) and they
404      are both either store or load (not load and store).  */
405   if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
406       || !dr_equal_offsets_p (dra, drb)
407       || !tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb))
408       || DR_IS_READ (dra) != DR_IS_READ (drb))
409     return false;
410
411   /* Check:
412      1. data-refs are of the same type
413      2. their steps are equal
414      3. the step (if greater than zero) is greater than the difference between
415         data-refs' inits.  */
416   type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
417   type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
418
419   if (type_size_a != type_size_b
420       || tree_int_cst_compare (DR_STEP (dra), DR_STEP (drb))
421       || !types_compatible_p (TREE_TYPE (DR_REF (dra)),
422                               TREE_TYPE (DR_REF (drb))))
423     return false;
424
425   init_a = TREE_INT_CST_LOW (DR_INIT (dra));
426   init_b = TREE_INT_CST_LOW (DR_INIT (drb));
427   step = TREE_INT_CST_LOW (DR_STEP (dra));
428
429   if (init_a > init_b)
430     {
431       /* If init_a == init_b + the size of the type * k, we have an interleaving,
432          and DRB is accessed before DRA.  */
433       diff_mod_size = (init_a - init_b) % type_size_a;
434
435       if (step && (init_a - init_b) > step)
436          return false;
437
438       if (diff_mod_size == 0)
439         {
440           vect_update_interleaving_chain (drb, dra);
441           if (dump_enabled_p ())
442             {
443               dump_printf_loc (MSG_NOTE, vect_location,
444                                "Detected interleaving ");
445               dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
446               dump_printf (MSG_NOTE,  " and ");
447               dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
448             }
449           return true;
450         }
451     }
452   else
453     {
454       /* If init_b == init_a + the size of the type * k, we have an
455          interleaving, and DRA is accessed before DRB.  */
456       diff_mod_size = (init_b - init_a) % type_size_a;
457
458       if (step && (init_b - init_a) > step)
459          return false;
460
461       if (diff_mod_size == 0)
462         {
463           vect_update_interleaving_chain (dra, drb);
464           if (dump_enabled_p ())
465             {
466               dump_printf_loc (MSG_NOTE, vect_location,
467                                "Detected interleaving ");
468               dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
469               dump_printf (MSG_NOTE,  " and ");
470               dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
471             }
472           return true;
473         }
474     }
475
476   return false;
477 }
478
479 /* Check if data references pointed by DR_I and DR_J are same or
480    belong to same interleaving group.  Return FALSE if drs are
481    different, otherwise return TRUE.  */
482
483 static bool
484 vect_same_range_drs (data_reference_p dr_i, data_reference_p dr_j)
485 {
486   gimple stmt_i = DR_STMT (dr_i);
487   gimple stmt_j = DR_STMT (dr_j);
488
489   if (operand_equal_p (DR_REF (dr_i), DR_REF (dr_j), 0)
490       || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_i))
491             && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_j))
492             && (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_i))
493                 == GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_j)))))
494     return true;
495   else
496     return false;
497 }
498
499 /* If address ranges represented by DDR_I and DDR_J are equal,
500    return TRUE, otherwise return FALSE.  */
501
502 static bool
503 vect_vfa_range_equal (ddr_p ddr_i, ddr_p ddr_j)
504 {
505   if ((vect_same_range_drs (DDR_A (ddr_i), DDR_A (ddr_j))
506        && vect_same_range_drs (DDR_B (ddr_i), DDR_B (ddr_j)))
507       || (vect_same_range_drs (DDR_A (ddr_i), DDR_B (ddr_j))
508           && vect_same_range_drs (DDR_B (ddr_i), DDR_A (ddr_j))))
509     return true;
510   else
511     return false;
512 }
513
514 /* Insert DDR into LOOP_VINFO list of ddrs that may alias and need to be
515    tested at run-time.  Return TRUE if DDR was successfully inserted.
516    Return false if versioning is not supported.  */
517
518 static bool
519 vect_mark_for_runtime_alias_test (ddr_p ddr, loop_vec_info loop_vinfo)
520 {
521   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
522
523   if ((unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS) == 0)
524     return false;
525
526   if (dump_enabled_p ())
527     {
528       dump_printf_loc (MSG_NOTE, vect_location,
529                        "mark for run-time aliasing test between ");
530       dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_A (ddr)));
531       dump_printf (MSG_NOTE,  " and ");
532       dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_B (ddr)));
533     }
534
535   if (optimize_loop_nest_for_size_p (loop))
536     {
537       if (dump_enabled_p ())
538         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
539                          "versioning not supported when optimizing for size.");
540       return false;
541     }
542
543   /* FORNOW: We don't support versioning with outer-loop vectorization.  */
544   if (loop->inner)
545     {
546       if (dump_enabled_p ())
547         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
548                          "versioning not yet supported for outer-loops.");
549       return false;
550     }
551
552   /* FORNOW: We don't support creating runtime alias tests for non-constant
553      step.  */
554   if (TREE_CODE (DR_STEP (DDR_A (ddr))) != INTEGER_CST
555       || TREE_CODE (DR_STEP (DDR_B (ddr))) != INTEGER_CST)
556     {
557       if (dump_enabled_p ())
558         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
559                          "versioning not yet supported for non-constant "
560                          "step");
561       return false;
562     }
563
564   LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo).safe_push (ddr);
565   return true;
566 }
567
568
569 /* Function vect_analyze_data_ref_dependence.
570
571    Return TRUE if there (might) exist a dependence between a memory-reference
572    DRA and a memory-reference DRB.  When versioning for alias may check a
573    dependence at run-time, return FALSE.  Adjust *MAX_VF according to
574    the data dependence.  */
575
576 static bool
577 vect_analyze_data_ref_dependence (struct data_dependence_relation *ddr,
578                                   loop_vec_info loop_vinfo, int *max_vf)
579 {
580   unsigned int i;
581   struct loop *loop = NULL;
582   struct data_reference *dra = DDR_A (ddr);
583   struct data_reference *drb = DDR_B (ddr);
584   stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
585   stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
586   lambda_vector dist_v;
587   unsigned int loop_depth;
588
589   /* Don't bother to analyze statements marked as unvectorizable.  */
590   if (!STMT_VINFO_VECTORIZABLE (stmtinfo_a)
591       || !STMT_VINFO_VECTORIZABLE (stmtinfo_b))
592     return false;
593
594   if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
595     {
596       /* Independent data accesses.  */
597       vect_check_interleaving (dra, drb);
598       return false;
599     }
600
601   if (loop_vinfo)
602     loop = LOOP_VINFO_LOOP (loop_vinfo);
603
604   if ((DR_IS_READ (dra) && DR_IS_READ (drb) && loop_vinfo) || dra == drb)
605     return false;
606
607   if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
608     {
609       gimple earlier_stmt;
610
611       if (loop_vinfo)
612         {
613           if (dump_enabled_p ())
614             {
615               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
616                                "versioning for alias required: "
617                                "can't determine dependence between ");
618               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
619                                  DR_REF (dra));
620               dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
621               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
622                                  DR_REF (drb));
623             }
624
625           /* Add to list of ddrs that need to be tested at run-time.  */
626           return !vect_mark_for_runtime_alias_test (ddr, loop_vinfo);
627         }
628
629       /* When vectorizing a basic block unknown depnedence can still mean
630          grouped access.  */
631       if (vect_check_interleaving (dra, drb))
632          return false;
633
634       /* Read-read is OK (we need this check here, after checking for
635          interleaving).  */
636       if (DR_IS_READ (dra) && DR_IS_READ (drb))
637         return false;
638
639       if (dump_enabled_p ())
640         {
641           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
642                            "can't determine dependence between ");
643           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (dra));
644           dump_printf (MSG_MISSED_OPTIMIZATION,  " and ");
645           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (drb));
646         }
647
648       /* We do not vectorize basic blocks with write-write dependencies.  */
649       if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
650         return true;
651
652       /* Check that it's not a load-after-store dependence.  */
653       earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));
654       if (DR_IS_WRITE (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
655         return true;
656
657       return false;
658     }
659
660   /* Versioning for alias is not yet supported for basic block SLP, and
661      dependence distance is unapplicable, hence, in case of known data
662      dependence, basic block vectorization is impossible for now.  */
663   if (!loop_vinfo)
664     {
665       if (dra != drb && vect_check_interleaving (dra, drb))
666         return false;
667
668       if (dump_enabled_p ())
669         {
670           dump_printf_loc (MSG_NOTE, vect_location,
671                            "determined dependence between ");
672           dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
673           dump_printf (MSG_NOTE, " and ");
674           dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
675         }
676
677       /* Do not vectorize basic blcoks with write-write dependences.  */
678       if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
679         return true;
680
681       /* Check if this dependence is allowed in basic block vectorization.  */
682       return vect_drs_dependent_in_basic_block (dra, drb);
683     }
684
685   /* Loop-based vectorization and known data dependence.  */
686   if (DDR_NUM_DIST_VECTS (ddr) == 0)
687     {
688       if (dump_enabled_p ())
689         {
690           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
691                            "versioning for alias required: "
692                            "bad dist vector for ");
693           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (dra));
694           dump_printf (MSG_MISSED_OPTIMIZATION,  " and ");
695           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (drb));
696         }
697       /* Add to list of ddrs that need to be tested at run-time.  */
698       return !vect_mark_for_runtime_alias_test (ddr, loop_vinfo);
699     }
700
701   loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr));
702   FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
703     {
704       int dist = dist_v[loop_depth];
705
706       if (dump_enabled_p ())
707         dump_printf_loc (MSG_NOTE, vect_location,
708                          "dependence distance  = %d.", dist);
709
710       if (dist == 0)
711         {
712           if (dump_enabled_p ())
713             {
714               dump_printf_loc (MSG_NOTE, vect_location, 
715                                "dependence distance == 0 between ");
716               dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
717               dump_printf (MSG_NOTE, " and ");
718               dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
719             }
720
721           /* For interleaving, mark that there is a read-write dependency if
722              necessary. We check before that one of the data-refs is store.  */
723           if (DR_IS_READ (dra))
724             GROUP_READ_WRITE_DEPENDENCE (stmtinfo_a) = true;
725           else
726             {
727               if (DR_IS_READ (drb))
728                 GROUP_READ_WRITE_DEPENDENCE (stmtinfo_b) = true;
729             }
730
731           continue;
732         }
733
734       if (dist > 0 && DDR_REVERSED_P (ddr))
735         {
736           /* If DDR_REVERSED_P the order of the data-refs in DDR was
737              reversed (to make distance vector positive), and the actual
738              distance is negative.  */
739           if (dump_enabled_p ())
740             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
741                              "dependence distance negative.");
742           continue;
743         }
744
745       if (abs (dist) >= 2
746           && abs (dist) < *max_vf)
747         {
748           /* The dependence distance requires reduction of the maximal
749              vectorization factor.  */
750           *max_vf = abs (dist);
751           if (dump_enabled_p ())
752             dump_printf_loc (MSG_NOTE, vect_location,
753                              "adjusting maximal vectorization factor to %i",
754                              *max_vf);
755         }
756
757       if (abs (dist) >= *max_vf)
758         {
759           /* Dependence distance does not create dependence, as far as
760              vectorization is concerned, in this case.  */
761           if (dump_enabled_p ())
762             dump_printf_loc (MSG_NOTE, vect_location,
763                              "dependence distance >= VF.");
764           continue;
765         }
766
767       if (dump_enabled_p ())
768         {
769           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
770                        "not vectorized, possible dependence "
771                        "between data-refs ");
772           dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
773           dump_printf (MSG_NOTE,  " and ");
774           dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
775         }
776
777       return true;
778     }
779
780   return false;
781 }
782
783 /* Function vect_analyze_data_ref_dependences.
784
785    Examine all the data references in the loop, and make sure there do not
786    exist any data dependences between them.  Set *MAX_VF according to
787    the maximum vectorization factor the data dependences allow.  */
788
789 bool
790 vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo,
791                                    bb_vec_info bb_vinfo, int *max_vf)
792 {
793   unsigned int i;
794   vec<ddr_p> ddrs = vNULL;
795   struct data_dependence_relation *ddr;
796
797   if (dump_enabled_p ())
798     dump_printf_loc (MSG_NOTE, vect_location,
799                      "=== vect_analyze_dependences ===");
800   if (loop_vinfo)
801     ddrs = LOOP_VINFO_DDRS (loop_vinfo);
802   else
803     ddrs = BB_VINFO_DDRS (bb_vinfo);
804
805   FOR_EACH_VEC_ELT (ddrs, i, ddr)
806     if (vect_analyze_data_ref_dependence (ddr, loop_vinfo, max_vf))
807       return false;
808
809   return true;
810 }
811
812
813 /* Function vect_compute_data_ref_alignment
814
815    Compute the misalignment of the data reference DR.
816
817    Output:
818    1. If during the misalignment computation it is found that the data reference
819       cannot be vectorized then false is returned.
820    2. DR_MISALIGNMENT (DR) is defined.
821
822    FOR NOW: No analysis is actually performed. Misalignment is calculated
823    only for trivial cases. TODO.  */
824
825 static bool
826 vect_compute_data_ref_alignment (struct data_reference *dr)
827 {
828   gimple stmt = DR_STMT (dr);
829   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
830   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
831   struct loop *loop = NULL;
832   tree ref = DR_REF (dr);
833   tree vectype;
834   tree base, base_addr;
835   bool base_aligned;
836   tree misalign;
837   tree aligned_to, alignment;
838
839   if (dump_enabled_p ())
840     dump_printf_loc (MSG_NOTE, vect_location,
841                      "vect_compute_data_ref_alignment:");
842
843   if (loop_vinfo)
844     loop = LOOP_VINFO_LOOP (loop_vinfo);
845
846   /* Initialize misalignment to unknown.  */
847   SET_DR_MISALIGNMENT (dr, -1);
848
849   /* Strided loads perform only component accesses, misalignment information
850      is irrelevant for them.  */
851   if (STMT_VINFO_STRIDE_LOAD_P (stmt_info))
852     return true;
853
854   misalign = DR_INIT (dr);
855   aligned_to = DR_ALIGNED_TO (dr);
856   base_addr = DR_BASE_ADDRESS (dr);
857   vectype = STMT_VINFO_VECTYPE (stmt_info);
858
859   /* In case the dataref is in an inner-loop of the loop that is being
860      vectorized (LOOP), we use the base and misalignment information
861      relative to the outer-loop (LOOP).  This is ok only if the misalignment
862      stays the same throughout the execution of the inner-loop, which is why
863      we have to check that the stride of the dataref in the inner-loop evenly
864      divides by the vector size.  */
865   if (loop && nested_in_vect_loop_p (loop, stmt))
866     {
867       tree step = DR_STEP (dr);
868       HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
869
870       if (dr_step % GET_MODE_SIZE (TYPE_MODE (vectype)) == 0)
871         {
872           if (dump_enabled_p ())
873             dump_printf_loc (MSG_NOTE, vect_location,
874                              "inner step divides the vector-size.");
875           misalign = STMT_VINFO_DR_INIT (stmt_info);
876           aligned_to = STMT_VINFO_DR_ALIGNED_TO (stmt_info);
877           base_addr = STMT_VINFO_DR_BASE_ADDRESS (stmt_info);
878         }
879       else
880         {
881           if (dump_enabled_p ())
882             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
883                              "inner step doesn't divide the vector-size.");
884           misalign = NULL_TREE;
885         }
886     }
887
888   /* Similarly, if we're doing basic-block vectorization, we can only use
889      base and misalignment information relative to an innermost loop if the
890      misalignment stays the same throughout the execution of the loop.
891      As above, this is the case if the stride of the dataref evenly divides
892      by the vector size.  */
893   if (!loop)
894     {
895       tree step = DR_STEP (dr);
896       HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
897
898       if (dr_step % GET_MODE_SIZE (TYPE_MODE (vectype)) != 0)
899         {
900           if (dump_enabled_p ())
901             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
902                              "SLP: step doesn't divide the vector-size.");
903           misalign = NULL_TREE;
904         }
905     }
906
907   base = build_fold_indirect_ref (base_addr);
908   alignment = ssize_int (TYPE_ALIGN (vectype)/BITS_PER_UNIT);
909
910   if ((aligned_to && tree_int_cst_compare (aligned_to, alignment) < 0)
911       || !misalign)
912     {
913       if (dump_enabled_p ())
914         {
915           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
916                            "Unknown alignment for access: ");
917           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, base);
918         }
919       return true;
920     }
921
922   if ((DECL_P (base)
923        && tree_int_cst_compare (ssize_int (DECL_ALIGN_UNIT (base)),
924                                 alignment) >= 0)
925       || (TREE_CODE (base_addr) == SSA_NAME
926           && tree_int_cst_compare (ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (
927                                                       TREE_TYPE (base_addr)))),
928                                    alignment) >= 0)
929       || (get_pointer_alignment (base_addr) >= TYPE_ALIGN (vectype)))
930     base_aligned = true;
931   else
932     base_aligned = false;
933
934   if (!base_aligned)
935     {
936       /* Do not change the alignment of global variables here if
937          flag_section_anchors is enabled as we already generated
938          RTL for other functions.  Most global variables should
939          have been aligned during the IPA increase_alignment pass.  */
940       if (!vect_can_force_dr_alignment_p (base, TYPE_ALIGN (vectype))
941           || (TREE_STATIC (base) && flag_section_anchors))
942         {
943           if (dump_enabled_p ())
944             {
945               dump_printf_loc (MSG_NOTE, vect_location,
946                                "can't force alignment of ref: ");
947               dump_generic_expr (MSG_NOTE, TDF_SLIM, ref);
948             }
949           return true;
950         }
951
952       /* Force the alignment of the decl.
953          NOTE: This is the only change to the code we make during
954          the analysis phase, before deciding to vectorize the loop.  */
955       if (dump_enabled_p ())
956         {
957           dump_printf_loc (MSG_NOTE, vect_location, "force alignment of ");
958           dump_generic_expr (MSG_NOTE, TDF_SLIM, ref);
959         }
960
961       DECL_ALIGN (base) = TYPE_ALIGN (vectype);
962       DECL_USER_ALIGN (base) = 1;
963     }
964
965   /* At this point we assume that the base is aligned.  */
966   gcc_assert (base_aligned
967               || (TREE_CODE (base) == VAR_DECL
968                   && DECL_ALIGN (base) >= TYPE_ALIGN (vectype)));
969
970   /* If this is a backward running DR then first access in the larger
971      vectype actually is N-1 elements before the address in the DR.
972      Adjust misalign accordingly.  */
973   if (tree_int_cst_compare (DR_STEP (dr), size_zero_node) < 0)
974     {
975       tree offset = ssize_int (TYPE_VECTOR_SUBPARTS (vectype) - 1);
976       /* DR_STEP(dr) is the same as -TYPE_SIZE of the scalar type,
977          otherwise we wouldn't be here.  */
978       offset = fold_build2 (MULT_EXPR, ssizetype, offset, DR_STEP (dr));
979       /* PLUS because DR_STEP was negative.  */
980       misalign = size_binop (PLUS_EXPR, misalign, offset);
981     }
982
983   /* Modulo alignment.  */
984   misalign = size_binop (FLOOR_MOD_EXPR, misalign, alignment);
985
986   if (!host_integerp (misalign, 1))
987     {
988       /* Negative or overflowed misalignment value.  */
989       if (dump_enabled_p ())
990         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
991                          "unexpected misalign value");
992       return false;
993     }
994
995   SET_DR_MISALIGNMENT (dr, TREE_INT_CST_LOW (misalign));
996
997   if (dump_enabled_p ())
998     {
999       dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1000                        "misalign = %d bytes of ref ", DR_MISALIGNMENT (dr));
1001       dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, ref);
1002     }
1003
1004   return true;
1005 }
1006
1007
1008 /* Function vect_compute_data_refs_alignment
1009
1010    Compute the misalignment of data references in the loop.
1011    Return FALSE if a data reference is found that cannot be vectorized.  */
1012
1013 static bool
1014 vect_compute_data_refs_alignment (loop_vec_info loop_vinfo,
1015                                   bb_vec_info bb_vinfo)
1016 {
1017   vec<data_reference_p> datarefs;
1018   struct data_reference *dr;
1019   unsigned int i;
1020
1021   if (loop_vinfo)
1022     datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1023   else
1024     datarefs = BB_VINFO_DATAREFS (bb_vinfo);
1025
1026   FOR_EACH_VEC_ELT (datarefs, i, dr)
1027     if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr)))
1028         && !vect_compute_data_ref_alignment (dr))
1029       {
1030         if (bb_vinfo)
1031           {
1032             /* Mark unsupported statement as unvectorizable.  */
1033             STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) = false;
1034             continue;
1035           }
1036         else
1037           return false;
1038       }
1039
1040   return true;
1041 }
1042
1043
1044 /* Function vect_update_misalignment_for_peel
1045
1046    DR - the data reference whose misalignment is to be adjusted.
1047    DR_PEEL - the data reference whose misalignment is being made
1048              zero in the vector loop by the peel.
1049    NPEEL - the number of iterations in the peel loop if the misalignment
1050            of DR_PEEL is known at compile time.  */
1051
1052 static void
1053 vect_update_misalignment_for_peel (struct data_reference *dr,
1054                                    struct data_reference *dr_peel, int npeel)
1055 {
1056   unsigned int i;
1057   vec<dr_p> same_align_drs;
1058   struct data_reference *current_dr;
1059   int dr_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr))));
1060   int dr_peel_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr_peel))));
1061   stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));
1062   stmt_vec_info peel_stmt_info = vinfo_for_stmt (DR_STMT (dr_peel));
1063
1064  /* For interleaved data accesses the step in the loop must be multiplied by
1065      the size of the interleaving group.  */
1066   if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
1067     dr_size *= GROUP_SIZE (vinfo_for_stmt (GROUP_FIRST_ELEMENT (stmt_info)));
1068   if (STMT_VINFO_GROUPED_ACCESS (peel_stmt_info))
1069     dr_peel_size *= GROUP_SIZE (peel_stmt_info);
1070
1071   /* It can be assumed that the data refs with the same alignment as dr_peel
1072      are aligned in the vector loop.  */
1073   same_align_drs
1074     = STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (DR_STMT (dr_peel)));
1075   FOR_EACH_VEC_ELT (same_align_drs, i, current_dr)
1076     {
1077       if (current_dr != dr)
1078         continue;
1079       gcc_assert (DR_MISALIGNMENT (dr) / dr_size ==
1080                   DR_MISALIGNMENT (dr_peel) / dr_peel_size);
1081       SET_DR_MISALIGNMENT (dr, 0);
1082       return;
1083     }
1084
1085   if (known_alignment_for_access_p (dr)
1086       && known_alignment_for_access_p (dr_peel))
1087     {
1088       bool negative = tree_int_cst_compare (DR_STEP (dr), size_zero_node) < 0;
1089       int misal = DR_MISALIGNMENT (dr);
1090       tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1091       misal += negative ? -npeel * dr_size : npeel * dr_size;
1092       misal &= (TYPE_ALIGN (vectype) / BITS_PER_UNIT) - 1;
1093       SET_DR_MISALIGNMENT (dr, misal);
1094       return;
1095     }
1096
1097   if (dump_enabled_p ())
1098     dump_printf_loc (MSG_NOTE, vect_location, "Setting misalignment to -1.");
1099   SET_DR_MISALIGNMENT (dr, -1);
1100 }
1101
1102
1103 /* Function vect_verify_datarefs_alignment
1104
1105    Return TRUE if all data references in the loop can be
1106    handled with respect to alignment.  */
1107
1108 bool
1109 vect_verify_datarefs_alignment (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
1110 {
1111   vec<data_reference_p> datarefs;
1112   struct data_reference *dr;
1113   enum dr_alignment_support supportable_dr_alignment;
1114   unsigned int i;
1115
1116   if (loop_vinfo)
1117     datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1118   else
1119     datarefs = BB_VINFO_DATAREFS (bb_vinfo);
1120
1121   FOR_EACH_VEC_ELT (datarefs, i, dr)
1122     {
1123       gimple stmt = DR_STMT (dr);
1124       stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1125
1126       if (!STMT_VINFO_RELEVANT_P (stmt_info))
1127         continue;
1128
1129       /* For interleaving, only the alignment of the first access matters. 
1130          Skip statements marked as not vectorizable.  */
1131       if ((STMT_VINFO_GROUPED_ACCESS (stmt_info)
1132            && GROUP_FIRST_ELEMENT (stmt_info) != stmt)
1133           || !STMT_VINFO_VECTORIZABLE (stmt_info))
1134         continue;
1135
1136       /* Strided loads perform only component accesses, alignment is
1137          irrelevant for them.  */
1138       if (STMT_VINFO_STRIDE_LOAD_P (stmt_info))
1139         continue;
1140
1141       supportable_dr_alignment = vect_supportable_dr_alignment (dr, false);
1142       if (!supportable_dr_alignment)
1143         {
1144           if (dump_enabled_p ())
1145             {
1146               if (DR_IS_READ (dr))
1147                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1148                                  "not vectorized: unsupported unaligned load.");
1149               else
1150                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1151                                  "not vectorized: unsupported unaligned "
1152                                  "store.");
1153
1154               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
1155                                  DR_REF (dr));
1156             }
1157           return false;
1158         }
1159       if (supportable_dr_alignment != dr_aligned && dump_enabled_p ())
1160         dump_printf_loc (MSG_NOTE, vect_location,
1161                          "Vectorizing an unaligned access.");
1162     }
1163   return true;
1164 }
1165
1166 /* Given an memory reference EXP return whether its alignment is less
1167    than its size.  */
1168
1169 static bool
1170 not_size_aligned (tree exp)
1171 {
1172   if (!host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1))
1173     return true;
1174
1175   return (TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp)))
1176           > get_object_alignment (exp));
1177 }
1178
1179 /* Function vector_alignment_reachable_p
1180
1181    Return true if vector alignment for DR is reachable by peeling
1182    a few loop iterations.  Return false otherwise.  */
1183
1184 static bool
1185 vector_alignment_reachable_p (struct data_reference *dr)
1186 {
1187   gimple stmt = DR_STMT (dr);
1188   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1189   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1190
1191   if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
1192     {
1193       /* For interleaved access we peel only if number of iterations in
1194          the prolog loop ({VF - misalignment}), is a multiple of the
1195          number of the interleaved accesses.  */
1196       int elem_size, mis_in_elements;
1197       int nelements = TYPE_VECTOR_SUBPARTS (vectype);
1198
1199       /* FORNOW: handle only known alignment.  */
1200       if (!known_alignment_for_access_p (dr))
1201         return false;
1202
1203       elem_size = GET_MODE_SIZE (TYPE_MODE (vectype)) / nelements;
1204       mis_in_elements = DR_MISALIGNMENT (dr) / elem_size;
1205
1206       if ((nelements - mis_in_elements) % GROUP_SIZE (stmt_info))
1207         return false;
1208     }
1209
1210   /* If misalignment is known at the compile time then allow peeling
1211      only if natural alignment is reachable through peeling.  */
1212   if (known_alignment_for_access_p (dr) && !aligned_access_p (dr))
1213     {
1214       HOST_WIDE_INT elmsize =
1215                 int_cst_value (TYPE_SIZE_UNIT (TREE_TYPE (vectype)));
1216       if (dump_enabled_p ())
1217         {
1218           dump_printf_loc (MSG_NOTE, vect_location, 
1219                            "data size =" HOST_WIDE_INT_PRINT_DEC, elmsize);
1220           dump_printf (MSG_NOTE, 
1221                        ". misalignment = %d. ", DR_MISALIGNMENT (dr));
1222         }
1223       if (DR_MISALIGNMENT (dr) % elmsize)
1224         {
1225           if (dump_enabled_p ())
1226             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
1227                              "data size does not divide the misalignment.\n");
1228           return false;
1229         }
1230     }
1231
1232   if (!known_alignment_for_access_p (dr))
1233     {
1234       tree type = TREE_TYPE (DR_REF (dr));
1235       bool is_packed = not_size_aligned (DR_REF (dr));
1236       if (dump_enabled_p ())
1237         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
1238                          "Unknown misalignment, is_packed = %d",is_packed);
1239       if (targetm.vectorize.vector_alignment_reachable (type, is_packed))
1240         return true;
1241       else
1242         return false;
1243     }
1244
1245   return true;
1246 }
1247
1248
1249 /* Calculate the cost of the memory access represented by DR.  */
1250
1251 static void
1252 vect_get_data_access_cost (struct data_reference *dr,
1253                            unsigned int *inside_cost,
1254                            unsigned int *outside_cost,
1255                            stmt_vector_for_cost *body_cost_vec)
1256 {
1257   gimple stmt = DR_STMT (dr);
1258   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1259   int nunits = TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info));
1260   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1261   int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1262   int ncopies = vf / nunits;
1263
1264   if (DR_IS_READ (dr))
1265     vect_get_load_cost (dr, ncopies, true, inside_cost, outside_cost,
1266                         NULL, body_cost_vec, false);
1267   else
1268     vect_get_store_cost (dr, ncopies, inside_cost, body_cost_vec);
1269
1270   if (dump_enabled_p ())
1271     dump_printf_loc (MSG_NOTE, vect_location,
1272                      "vect_get_data_access_cost: inside_cost = %d, "
1273                      "outside_cost = %d.", *inside_cost, *outside_cost);
1274 }
1275
1276
1277 static hashval_t
1278 vect_peeling_hash (const void *elem)
1279 {
1280   const struct _vect_peel_info *peel_info;
1281
1282   peel_info = (const struct _vect_peel_info *) elem;
1283   return (hashval_t) peel_info->npeel;
1284 }
1285
1286
1287 static int
1288 vect_peeling_hash_eq (const void *elem1, const void *elem2)
1289 {
1290   const struct _vect_peel_info *a, *b;
1291
1292   a = (const struct _vect_peel_info *) elem1;
1293   b = (const struct _vect_peel_info *) elem2;
1294   return (a->npeel == b->npeel);
1295 }
1296
1297
1298 /* Insert DR into peeling hash table with NPEEL as key.  */
1299
1300 static void
1301 vect_peeling_hash_insert (loop_vec_info loop_vinfo, struct data_reference *dr,
1302                           int npeel)
1303 {
1304   struct _vect_peel_info elem, *slot;
1305   void **new_slot;
1306   bool supportable_dr_alignment = vect_supportable_dr_alignment (dr, true);
1307
1308   elem.npeel = npeel;
1309   slot = (vect_peel_info) htab_find (LOOP_VINFO_PEELING_HTAB (loop_vinfo),
1310                                      &elem);
1311   if (slot)
1312     slot->count++;
1313   else
1314     {
1315       slot = XNEW (struct _vect_peel_info);
1316       slot->npeel = npeel;
1317       slot->dr = dr;
1318       slot->count = 1;
1319       new_slot = htab_find_slot (LOOP_VINFO_PEELING_HTAB (loop_vinfo), slot,
1320                                  INSERT);
1321       *new_slot = slot;
1322     }
1323
1324   if (!supportable_dr_alignment && !flag_vect_cost_model)
1325     slot->count += VECT_MAX_COST;
1326 }
1327
1328
1329 /* Traverse peeling hash table to find peeling option that aligns maximum
1330    number of data accesses.  */
1331
1332 static int
1333 vect_peeling_hash_get_most_frequent (void **slot, void *data)
1334 {
1335   vect_peel_info elem = (vect_peel_info) *slot;
1336   vect_peel_extended_info max = (vect_peel_extended_info) data;
1337
1338   if (elem->count > max->peel_info.count
1339       || (elem->count == max->peel_info.count
1340           && max->peel_info.npeel > elem->npeel))
1341     {
1342       max->peel_info.npeel = elem->npeel;
1343       max->peel_info.count = elem->count;
1344       max->peel_info.dr = elem->dr;
1345     }
1346
1347   return 1;
1348 }
1349
1350
1351 /* Traverse peeling hash table and calculate cost for each peeling option.
1352    Find the one with the lowest cost.  */
1353
1354 static int
1355 vect_peeling_hash_get_lowest_cost (void **slot, void *data)
1356 {
1357   vect_peel_info elem = (vect_peel_info) *slot;
1358   vect_peel_extended_info min = (vect_peel_extended_info) data;
1359   int save_misalignment, dummy;
1360   unsigned int inside_cost = 0, outside_cost = 0, i;
1361   gimple stmt = DR_STMT (elem->dr);
1362   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1363   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1364   vec<data_reference_p> datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1365   struct data_reference *dr;
1366   stmt_vector_for_cost prologue_cost_vec, body_cost_vec, epilogue_cost_vec;
1367   int single_iter_cost;
1368
1369   prologue_cost_vec.create (2);
1370   body_cost_vec.create (2);
1371   epilogue_cost_vec.create (2);
1372
1373   FOR_EACH_VEC_ELT (datarefs, i, dr)
1374     {
1375       stmt = DR_STMT (dr);
1376       stmt_info = vinfo_for_stmt (stmt);
1377       /* For interleaving, only the alignment of the first access
1378          matters.  */
1379       if (STMT_VINFO_GROUPED_ACCESS (stmt_info)
1380           && GROUP_FIRST_ELEMENT (stmt_info) != stmt)
1381         continue;
1382
1383       save_misalignment = DR_MISALIGNMENT (dr);
1384       vect_update_misalignment_for_peel (dr, elem->dr, elem->npeel);
1385       vect_get_data_access_cost (dr, &inside_cost, &outside_cost,
1386                                  &body_cost_vec);
1387       SET_DR_MISALIGNMENT (dr, save_misalignment);
1388     }
1389
1390   single_iter_cost = vect_get_single_scalar_iteration_cost (loop_vinfo);
1391   outside_cost += vect_get_known_peeling_cost (loop_vinfo, elem->npeel,
1392                                                &dummy, single_iter_cost,
1393                                                &prologue_cost_vec,
1394                                                &epilogue_cost_vec);
1395
1396   /* Prologue and epilogue costs are added to the target model later.
1397      These costs depend only on the scalar iteration cost, the
1398      number of peeling iterations finally chosen, and the number of
1399      misaligned statements.  So discard the information found here.  */
1400   prologue_cost_vec.release ();
1401   epilogue_cost_vec.release ();
1402
1403   if (inside_cost < min->inside_cost
1404       || (inside_cost == min->inside_cost && outside_cost < min->outside_cost))
1405     {
1406       min->inside_cost = inside_cost;
1407       min->outside_cost = outside_cost;
1408       min->body_cost_vec.release ();
1409       min->body_cost_vec = body_cost_vec;
1410       min->peel_info.dr = elem->dr;
1411       min->peel_info.npeel = elem->npeel;
1412     }
1413   else
1414     body_cost_vec.release ();
1415
1416   return 1;
1417 }
1418
1419
1420 /* Choose best peeling option by traversing peeling hash table and either
1421    choosing an option with the lowest cost (if cost model is enabled) or the
1422    option that aligns as many accesses as possible.  */
1423
1424 static struct data_reference *
1425 vect_peeling_hash_choose_best_peeling (loop_vec_info loop_vinfo,
1426                                        unsigned int *npeel,
1427                                        stmt_vector_for_cost *body_cost_vec)
1428 {
1429    struct _vect_peel_extended_info res;
1430
1431    res.peel_info.dr = NULL;
1432    res.body_cost_vec = stmt_vector_for_cost();
1433
1434    if (flag_vect_cost_model)
1435      {
1436        res.inside_cost = INT_MAX;
1437        res.outside_cost = INT_MAX;
1438        htab_traverse (LOOP_VINFO_PEELING_HTAB (loop_vinfo),
1439                       vect_peeling_hash_get_lowest_cost, &res);
1440      }
1441    else
1442      {
1443        res.peel_info.count = 0;
1444        htab_traverse (LOOP_VINFO_PEELING_HTAB (loop_vinfo),
1445                       vect_peeling_hash_get_most_frequent, &res);
1446      }
1447
1448    *npeel = res.peel_info.npeel;
1449    *body_cost_vec = res.body_cost_vec;
1450    return res.peel_info.dr;
1451 }
1452
1453
1454 /* Function vect_enhance_data_refs_alignment
1455
1456    This pass will use loop versioning and loop peeling in order to enhance
1457    the alignment of data references in the loop.
1458
1459    FOR NOW: we assume that whatever versioning/peeling takes place, only the
1460    original loop is to be vectorized.  Any other loops that are created by
1461    the transformations performed in this pass - are not supposed to be
1462    vectorized.  This restriction will be relaxed.
1463
1464    This pass will require a cost model to guide it whether to apply peeling
1465    or versioning or a combination of the two.  For example, the scheme that
1466    intel uses when given a loop with several memory accesses, is as follows:
1467    choose one memory access ('p') which alignment you want to force by doing
1468    peeling.  Then, either (1) generate a loop in which 'p' is aligned and all
1469    other accesses are not necessarily aligned, or (2) use loop versioning to
1470    generate one loop in which all accesses are aligned, and another loop in
1471    which only 'p' is necessarily aligned.
1472
1473    ("Automatic Intra-Register Vectorization for the Intel Architecture",
1474    Aart J.C. Bik, Milind Girkar, Paul M. Grey and Ximmin Tian, International
1475    Journal of Parallel Programming, Vol. 30, No. 2, April 2002.)
1476
1477    Devising a cost model is the most critical aspect of this work.  It will
1478    guide us on which access to peel for, whether to use loop versioning, how
1479    many versions to create, etc.  The cost model will probably consist of
1480    generic considerations as well as target specific considerations (on
1481    powerpc for example, misaligned stores are more painful than misaligned
1482    loads).
1483
1484    Here are the general steps involved in alignment enhancements:
1485
1486      -- original loop, before alignment analysis:
1487         for (i=0; i<N; i++){
1488           x = q[i];                     # DR_MISALIGNMENT(q) = unknown
1489           p[i] = y;                     # DR_MISALIGNMENT(p) = unknown
1490         }
1491
1492      -- After vect_compute_data_refs_alignment:
1493         for (i=0; i<N; i++){
1494           x = q[i];                     # DR_MISALIGNMENT(q) = 3
1495           p[i] = y;                     # DR_MISALIGNMENT(p) = unknown
1496         }
1497
1498      -- Possibility 1: we do loop versioning:
1499      if (p is aligned) {
1500         for (i=0; i<N; i++){    # loop 1A
1501           x = q[i];                     # DR_MISALIGNMENT(q) = 3
1502           p[i] = y;                     # DR_MISALIGNMENT(p) = 0
1503         }
1504      }
1505      else {
1506         for (i=0; i<N; i++){    # loop 1B
1507           x = q[i];                     # DR_MISALIGNMENT(q) = 3
1508           p[i] = y;                     # DR_MISALIGNMENT(p) = unaligned
1509         }
1510      }
1511
1512      -- Possibility 2: we do loop peeling:
1513      for (i = 0; i < 3; i++){   # (scalar loop, not to be vectorized).
1514         x = q[i];
1515         p[i] = y;
1516      }
1517      for (i = 3; i < N; i++){   # loop 2A
1518         x = q[i];                       # DR_MISALIGNMENT(q) = 0
1519         p[i] = y;                       # DR_MISALIGNMENT(p) = unknown
1520      }
1521
1522      -- Possibility 3: combination of loop peeling and versioning:
1523      for (i = 0; i < 3; i++){   # (scalar loop, not to be vectorized).
1524         x = q[i];
1525         p[i] = y;
1526      }
1527      if (p is aligned) {
1528         for (i = 3; i<N; i++){  # loop 3A
1529           x = q[i];                     # DR_MISALIGNMENT(q) = 0
1530           p[i] = y;                     # DR_MISALIGNMENT(p) = 0
1531         }
1532      }
1533      else {
1534         for (i = 3; i<N; i++){  # loop 3B
1535           x = q[i];                     # DR_MISALIGNMENT(q) = 0
1536           p[i] = y;                     # DR_MISALIGNMENT(p) = unaligned
1537         }
1538      }
1539
1540      These loops are later passed to loop_transform to be vectorized.  The
1541      vectorizer will use the alignment information to guide the transformation
1542      (whether to generate regular loads/stores, or with special handling for
1543      misalignment).  */
1544
1545 bool
1546 vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo)
1547 {
1548   vec<data_reference_p> datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1549   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1550   enum dr_alignment_support supportable_dr_alignment;
1551   struct data_reference *dr0 = NULL, *first_store = NULL;
1552   struct data_reference *dr;
1553   unsigned int i, j;
1554   bool do_peeling = false;
1555   bool do_versioning = false;
1556   bool stat;
1557   gimple stmt;
1558   stmt_vec_info stmt_info;
1559   int vect_versioning_for_alias_required;
1560   unsigned int npeel = 0;
1561   bool all_misalignments_unknown = true;
1562   unsigned int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1563   unsigned possible_npeel_number = 1;
1564   tree vectype;
1565   unsigned int nelements, mis, same_align_drs_max = 0;
1566   stmt_vector_for_cost body_cost_vec = stmt_vector_for_cost();
1567
1568   if (dump_enabled_p ())
1569     dump_printf_loc (MSG_NOTE, vect_location,
1570                      "=== vect_enhance_data_refs_alignment ===");
1571
1572   /* While cost model enhancements are expected in the future, the high level
1573      view of the code at this time is as follows:
1574
1575      A) If there is a misaligned access then see if peeling to align
1576         this access can make all data references satisfy
1577         vect_supportable_dr_alignment.  If so, update data structures
1578         as needed and return true.
1579
1580      B) If peeling wasn't possible and there is a data reference with an
1581         unknown misalignment that does not satisfy vect_supportable_dr_alignment
1582         then see if loop versioning checks can be used to make all data
1583         references satisfy vect_supportable_dr_alignment.  If so, update
1584         data structures as needed and return true.
1585
1586      C) If neither peeling nor versioning were successful then return false if
1587         any data reference does not satisfy vect_supportable_dr_alignment.
1588
1589      D) Return true (all data references satisfy vect_supportable_dr_alignment).
1590
1591      Note, Possibility 3 above (which is peeling and versioning together) is not
1592      being done at this time.  */
1593
1594   /* (1) Peeling to force alignment.  */
1595
1596   /* (1.1) Decide whether to perform peeling, and how many iterations to peel:
1597      Considerations:
1598      + How many accesses will become aligned due to the peeling
1599      - How many accesses will become unaligned due to the peeling,
1600        and the cost of misaligned accesses.
1601      - The cost of peeling (the extra runtime checks, the increase
1602        in code size).  */
1603
1604   FOR_EACH_VEC_ELT (datarefs, i, dr)
1605     {
1606       stmt = DR_STMT (dr);
1607       stmt_info = vinfo_for_stmt (stmt);
1608
1609       if (!STMT_VINFO_RELEVANT_P (stmt_info))
1610         continue;
1611
1612       /* For interleaving, only the alignment of the first access
1613          matters.  */
1614       if (STMT_VINFO_GROUPED_ACCESS (stmt_info)
1615           && GROUP_FIRST_ELEMENT (stmt_info) != stmt)
1616         continue;
1617
1618       /* For invariant accesses there is nothing to enhance.  */
1619       if (integer_zerop (DR_STEP (dr)))
1620         continue;
1621
1622       /* Strided loads perform only component accesses, alignment is
1623          irrelevant for them.  */
1624       if (STMT_VINFO_STRIDE_LOAD_P (stmt_info))
1625         continue;
1626
1627       supportable_dr_alignment = vect_supportable_dr_alignment (dr, true);
1628       do_peeling = vector_alignment_reachable_p (dr);
1629       if (do_peeling)
1630         {
1631           if (known_alignment_for_access_p (dr))
1632             {
1633               unsigned int npeel_tmp;
1634               bool negative = tree_int_cst_compare (DR_STEP (dr),
1635                                                     size_zero_node) < 0;
1636
1637               /* Save info about DR in the hash table.  */
1638               if (!LOOP_VINFO_PEELING_HTAB (loop_vinfo))
1639                 LOOP_VINFO_PEELING_HTAB (loop_vinfo) =
1640                            htab_create (1, vect_peeling_hash,
1641                                         vect_peeling_hash_eq, free);
1642
1643               vectype = STMT_VINFO_VECTYPE (stmt_info);
1644               nelements = TYPE_VECTOR_SUBPARTS (vectype);
1645               mis = DR_MISALIGNMENT (dr) / GET_MODE_SIZE (TYPE_MODE (
1646                                                 TREE_TYPE (DR_REF (dr))));
1647               npeel_tmp = (negative
1648                            ? (mis - nelements) : (nelements - mis))
1649                   & (nelements - 1);
1650
1651               /* For multiple types, it is possible that the bigger type access
1652                  will have more than one peeling option.  E.g., a loop with two
1653                  types: one of size (vector size / 4), and the other one of
1654                  size (vector size / 8).  Vectorization factor will 8.  If both
1655                  access are misaligned by 3, the first one needs one scalar
1656                  iteration to be aligned, and the second one needs 5.  But the
1657                  the first one will be aligned also by peeling 5 scalar
1658                  iterations, and in that case both accesses will be aligned.
1659                  Hence, except for the immediate peeling amount, we also want
1660                  to try to add full vector size, while we don't exceed
1661                  vectorization factor.
1662                  We do this automtically for cost model, since we calculate cost
1663                  for every peeling option.  */
1664               if (!flag_vect_cost_model)
1665                 possible_npeel_number = vf /nelements;
1666
1667               /* Handle the aligned case. We may decide to align some other
1668                  access, making DR unaligned.  */
1669               if (DR_MISALIGNMENT (dr) == 0)
1670                 {
1671                   npeel_tmp = 0;
1672                   if (!flag_vect_cost_model)
1673                     possible_npeel_number++;
1674                 }
1675
1676               for (j = 0; j < possible_npeel_number; j++)
1677                 {
1678                   gcc_assert (npeel_tmp <= vf);
1679                   vect_peeling_hash_insert (loop_vinfo, dr, npeel_tmp);
1680                   npeel_tmp += nelements;
1681                 }
1682
1683               all_misalignments_unknown = false;
1684               /* Data-ref that was chosen for the case that all the
1685                  misalignments are unknown is not relevant anymore, since we
1686                  have a data-ref with known alignment.  */
1687               dr0 = NULL;
1688             }
1689           else
1690             {
1691               /* If we don't know all the misalignment values, we prefer
1692                  peeling for data-ref that has maximum number of data-refs
1693                  with the same alignment, unless the target prefers to align
1694                  stores over load.  */
1695               if (all_misalignments_unknown)
1696                 {
1697                   if (same_align_drs_max 
1698                         < STMT_VINFO_SAME_ALIGN_REFS (stmt_info).length ()
1699                       || !dr0)
1700                     {
1701                       same_align_drs_max
1702                           = STMT_VINFO_SAME_ALIGN_REFS (stmt_info).length ();
1703                       dr0 = dr;
1704                     }
1705
1706                   if (!first_store && DR_IS_WRITE (dr))
1707                     first_store = dr;
1708                 }
1709
1710               /* If there are both known and unknown misaligned accesses in the
1711                  loop, we choose peeling amount according to the known
1712                  accesses.  */
1713
1714
1715               if (!supportable_dr_alignment)
1716                 {
1717                   dr0 = dr;
1718                   if (!first_store && DR_IS_WRITE (dr))
1719                     first_store = dr;
1720                 }
1721             }
1722         }
1723       else
1724         {
1725           if (!aligned_access_p (dr))
1726             {
1727               if (dump_enabled_p ())
1728                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
1729                                  "vector alignment may not be reachable");
1730               break;
1731             }
1732         }
1733     }
1734
1735   vect_versioning_for_alias_required
1736     = LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo);
1737
1738   /* Temporarily, if versioning for alias is required, we disable peeling
1739      until we support peeling and versioning.  Often peeling for alignment
1740      will require peeling for loop-bound, which in turn requires that we
1741      know how to adjust the loop ivs after the loop.  */
1742   if (vect_versioning_for_alias_required
1743       || !vect_can_advance_ivs_p (loop_vinfo)
1744       || !slpeel_can_duplicate_loop_p (loop, single_exit (loop)))
1745     do_peeling = false;
1746
1747   if (do_peeling && all_misalignments_unknown
1748       && vect_supportable_dr_alignment (dr0, false))
1749     {
1750
1751       /* Check if the target requires to prefer stores over loads, i.e., if
1752          misaligned stores are more expensive than misaligned loads (taking
1753          drs with same alignment into account).  */
1754       if (first_store && DR_IS_READ (dr0))
1755         {
1756           unsigned int load_inside_cost = 0, load_outside_cost = 0;
1757           unsigned int store_inside_cost = 0, store_outside_cost = 0;
1758           unsigned int load_inside_penalty = 0, load_outside_penalty = 0;
1759           unsigned int store_inside_penalty = 0, store_outside_penalty = 0;
1760           stmt_vector_for_cost dummy;
1761           dummy.create (2);
1762
1763           vect_get_data_access_cost (dr0, &load_inside_cost, &load_outside_cost,
1764                                      &dummy);
1765           vect_get_data_access_cost (first_store, &store_inside_cost,
1766                                      &store_outside_cost, &dummy);
1767
1768           dummy.release ();
1769
1770           /* Calculate the penalty for leaving FIRST_STORE unaligned (by
1771              aligning the load DR0).  */
1772           load_inside_penalty = store_inside_cost;
1773           load_outside_penalty = store_outside_cost;
1774           for (i = 0;
1775                STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (
1776                           DR_STMT (first_store))).iterate (i, &dr);
1777                i++)
1778             if (DR_IS_READ (dr))
1779               {
1780                 load_inside_penalty += load_inside_cost;
1781                 load_outside_penalty += load_outside_cost;
1782               }
1783             else
1784               {
1785                 load_inside_penalty += store_inside_cost;
1786                 load_outside_penalty += store_outside_cost;
1787               }
1788
1789           /* Calculate the penalty for leaving DR0 unaligned (by
1790              aligning the FIRST_STORE).  */
1791           store_inside_penalty = load_inside_cost;
1792           store_outside_penalty = load_outside_cost;
1793           for (i = 0;
1794                STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (
1795                       DR_STMT (dr0))).iterate (i, &dr);
1796                i++)
1797             if (DR_IS_READ (dr))
1798               {
1799                 store_inside_penalty += load_inside_cost;
1800                 store_outside_penalty += load_outside_cost;
1801               }
1802             else
1803               {
1804                 store_inside_penalty += store_inside_cost;
1805                 store_outside_penalty += store_outside_cost;
1806               }
1807
1808           if (load_inside_penalty > store_inside_penalty
1809               || (load_inside_penalty == store_inside_penalty
1810                   && load_outside_penalty > store_outside_penalty))
1811             dr0 = first_store;
1812         }
1813
1814       /* In case there are only loads with different unknown misalignments, use
1815          peeling only if it may help to align other accesses in the loop.  */
1816       if (!first_store
1817           && !STMT_VINFO_SAME_ALIGN_REFS (
1818                   vinfo_for_stmt (DR_STMT (dr0))).length ()
1819           && vect_supportable_dr_alignment (dr0, false)
1820               != dr_unaligned_supported)
1821         do_peeling = false;
1822     }
1823
1824   if (do_peeling && !dr0)
1825     {
1826       /* Peeling is possible, but there is no data access that is not supported
1827          unless aligned. So we try to choose the best possible peeling.  */
1828
1829       /* We should get here only if there are drs with known misalignment.  */
1830       gcc_assert (!all_misalignments_unknown);
1831
1832       /* Choose the best peeling from the hash table.  */
1833       dr0 = vect_peeling_hash_choose_best_peeling (loop_vinfo, &npeel,
1834                                                    &body_cost_vec);
1835       if (!dr0 || !npeel)
1836         do_peeling = false;
1837     }
1838
1839   if (do_peeling)
1840     {
1841       stmt = DR_STMT (dr0);
1842       stmt_info = vinfo_for_stmt (stmt);
1843       vectype = STMT_VINFO_VECTYPE (stmt_info);
1844       nelements = TYPE_VECTOR_SUBPARTS (vectype);
1845
1846       if (known_alignment_for_access_p (dr0))
1847         {
1848           bool negative = tree_int_cst_compare (DR_STEP (dr0),
1849                                                 size_zero_node) < 0;
1850           if (!npeel)
1851             {
1852               /* Since it's known at compile time, compute the number of
1853                  iterations in the peeled loop (the peeling factor) for use in
1854                  updating DR_MISALIGNMENT values.  The peeling factor is the
1855                  vectorization factor minus the misalignment as an element
1856                  count.  */
1857               mis = DR_MISALIGNMENT (dr0);
1858               mis /= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr0))));
1859               npeel = ((negative ? mis - nelements : nelements - mis)
1860                        & (nelements - 1));
1861             }
1862
1863           /* For interleaved data access every iteration accesses all the
1864              members of the group, therefore we divide the number of iterations
1865              by the group size.  */
1866           stmt_info = vinfo_for_stmt (DR_STMT (dr0));
1867           if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
1868             npeel /= GROUP_SIZE (stmt_info);
1869
1870           if (dump_enabled_p ())
1871             dump_printf_loc (MSG_NOTE, vect_location,
1872                              "Try peeling by %d", npeel);
1873         }
1874
1875       /* Ensure that all data refs can be vectorized after the peel.  */
1876       FOR_EACH_VEC_ELT (datarefs, i, dr)
1877         {
1878           int save_misalignment;
1879
1880           if (dr == dr0)
1881             continue;
1882
1883           stmt = DR_STMT (dr);
1884           stmt_info = vinfo_for_stmt (stmt);
1885           /* For interleaving, only the alignment of the first access
1886             matters.  */
1887           if (STMT_VINFO_GROUPED_ACCESS (stmt_info)
1888               && GROUP_FIRST_ELEMENT (stmt_info) != stmt)
1889             continue;
1890
1891           /* Strided loads perform only component accesses, alignment is
1892              irrelevant for them.  */
1893           if (STMT_VINFO_STRIDE_LOAD_P (stmt_info))
1894             continue;
1895
1896           save_misalignment = DR_MISALIGNMENT (dr);
1897           vect_update_misalignment_for_peel (dr, dr0, npeel);
1898           supportable_dr_alignment = vect_supportable_dr_alignment (dr, false);
1899           SET_DR_MISALIGNMENT (dr, save_misalignment);
1900
1901           if (!supportable_dr_alignment)
1902             {
1903               do_peeling = false;
1904               break;
1905             }
1906         }
1907
1908       if (do_peeling && known_alignment_for_access_p (dr0) && npeel == 0)
1909         {
1910           stat = vect_verify_datarefs_alignment (loop_vinfo, NULL);
1911           if (!stat)
1912             do_peeling = false;
1913           else
1914             {
1915               body_cost_vec.release ();
1916               return stat;
1917             }
1918         }
1919
1920       if (do_peeling)
1921         {
1922           stmt_info_for_cost *si;
1923           void *data = LOOP_VINFO_TARGET_COST_DATA (loop_vinfo);
1924
1925           /* (1.2) Update the DR_MISALIGNMENT of each data reference DR_i.
1926              If the misalignment of DR_i is identical to that of dr0 then set
1927              DR_MISALIGNMENT (DR_i) to zero.  If the misalignment of DR_i and
1928              dr0 are known at compile time then increment DR_MISALIGNMENT (DR_i)
1929              by the peeling factor times the element size of DR_i (MOD the
1930              vectorization factor times the size).  Otherwise, the
1931              misalignment of DR_i must be set to unknown.  */
1932           FOR_EACH_VEC_ELT (datarefs, i, dr)
1933             if (dr != dr0)
1934               vect_update_misalignment_for_peel (dr, dr0, npeel);
1935
1936           LOOP_VINFO_UNALIGNED_DR (loop_vinfo) = dr0;
1937           if (npeel)
1938             LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) = npeel;
1939           else
1940             LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) = DR_MISALIGNMENT (dr0);
1941           SET_DR_MISALIGNMENT (dr0, 0);
1942           if (dump_enabled_p ())
1943             {
1944               dump_printf_loc (MSG_NOTE, vect_location,
1945                                "Alignment of access forced using peeling.");
1946               dump_printf_loc (MSG_NOTE, vect_location,
1947                                "Peeling for alignment will be applied.");
1948             }
1949           /* We've delayed passing the inside-loop peeling costs to the
1950              target cost model until we were sure peeling would happen.
1951              Do so now.  */
1952           if (body_cost_vec.exists ())
1953             {
1954               FOR_EACH_VEC_ELT (body_cost_vec, i, si)
1955                 {
1956                   struct _stmt_vec_info *stmt_info
1957                     = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
1958                   (void) add_stmt_cost (data, si->count, si->kind, stmt_info,
1959                                         si->misalign, vect_body);
1960                 }
1961               body_cost_vec.release ();
1962             }
1963
1964           stat = vect_verify_datarefs_alignment (loop_vinfo, NULL);
1965           gcc_assert (stat);
1966           return stat;
1967         }
1968     }
1969
1970   body_cost_vec.release ();
1971
1972   /* (2) Versioning to force alignment.  */
1973
1974   /* Try versioning if:
1975      1) flag_tree_vect_loop_version is TRUE
1976      2) optimize loop for speed
1977      3) there is at least one unsupported misaligned data ref with an unknown
1978         misalignment, and
1979      4) all misaligned data refs with a known misalignment are supported, and
1980      5) the number of runtime alignment checks is within reason.  */
1981
1982   do_versioning =
1983         flag_tree_vect_loop_version
1984         && optimize_loop_nest_for_speed_p (loop)
1985         && (!loop->inner); /* FORNOW */
1986
1987   if (do_versioning)
1988     {
1989       FOR_EACH_VEC_ELT (datarefs, i, dr)
1990         {
1991           stmt = DR_STMT (dr);
1992           stmt_info = vinfo_for_stmt (stmt);
1993
1994           /* For interleaving, only the alignment of the first access
1995              matters.  */
1996           if (aligned_access_p (dr)
1997               || (STMT_VINFO_GROUPED_ACCESS (stmt_info)
1998                   && GROUP_FIRST_ELEMENT (stmt_info) != stmt))
1999             continue;
2000
2001           /* Strided loads perform only component accesses, alignment is
2002              irrelevant for them.  */
2003           if (STMT_VINFO_STRIDE_LOAD_P (stmt_info))
2004             continue;
2005
2006           supportable_dr_alignment = vect_supportable_dr_alignment (dr, false);
2007
2008           if (!supportable_dr_alignment)
2009             {
2010               gimple stmt;
2011               int mask;
2012               tree vectype;
2013
2014               if (known_alignment_for_access_p (dr)
2015                   || LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).length ()
2016                      >= (unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS))
2017                 {
2018                   do_versioning = false;
2019                   break;
2020                 }
2021
2022               stmt = DR_STMT (dr);
2023               vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
2024               gcc_assert (vectype);
2025
2026               /* The rightmost bits of an aligned address must be zeros.
2027                  Construct the mask needed for this test.  For example,
2028                  GET_MODE_SIZE for the vector mode V4SI is 16 bytes so the
2029                  mask must be 15 = 0xf. */
2030               mask = GET_MODE_SIZE (TYPE_MODE (vectype)) - 1;
2031
2032               /* FORNOW: use the same mask to test all potentially unaligned
2033                  references in the loop.  The vectorizer currently supports
2034                  a single vector size, see the reference to
2035                  GET_MODE_NUNITS (TYPE_MODE (vectype)) where the
2036                  vectorization factor is computed.  */
2037               gcc_assert (!LOOP_VINFO_PTR_MASK (loop_vinfo)
2038                           || LOOP_VINFO_PTR_MASK (loop_vinfo) == mask);
2039               LOOP_VINFO_PTR_MASK (loop_vinfo) = mask;
2040               LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).safe_push (
2041                       DR_STMT (dr));
2042             }
2043         }
2044
2045       /* Versioning requires at least one misaligned data reference.  */
2046       if (!LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo))
2047         do_versioning = false;
2048       else if (!do_versioning)
2049         LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).truncate (0);
2050     }
2051
2052   if (do_versioning)
2053     {
2054       vec<gimple> may_misalign_stmts
2055         = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo);
2056       gimple stmt;
2057
2058       /* It can now be assumed that the data references in the statements
2059          in LOOP_VINFO_MAY_MISALIGN_STMTS will be aligned in the version
2060          of the loop being vectorized.  */
2061       FOR_EACH_VEC_ELT (may_misalign_stmts, i, stmt)
2062         {
2063           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2064           dr = STMT_VINFO_DATA_REF (stmt_info);
2065           SET_DR_MISALIGNMENT (dr, 0);
2066           if (dump_enabled_p ())
2067             dump_printf_loc (MSG_NOTE, vect_location, 
2068                              "Alignment of access forced using versioning.");
2069         }
2070
2071       if (dump_enabled_p ())
2072         dump_printf_loc (MSG_NOTE, vect_location, 
2073                          "Versioning for alignment will be applied.");
2074
2075       /* Peeling and versioning can't be done together at this time.  */
2076       gcc_assert (! (do_peeling && do_versioning));
2077
2078       stat = vect_verify_datarefs_alignment (loop_vinfo, NULL);
2079       gcc_assert (stat);
2080       return stat;
2081     }
2082
2083   /* This point is reached if neither peeling nor versioning is being done.  */
2084   gcc_assert (! (do_peeling || do_versioning));
2085
2086   stat = vect_verify_datarefs_alignment (loop_vinfo, NULL);
2087   return stat;
2088 }
2089
2090
2091 /* Function vect_find_same_alignment_drs.
2092
2093    Update group and alignment relations according to the chosen
2094    vectorization factor.  */
2095
2096 static void
2097 vect_find_same_alignment_drs (struct data_dependence_relation *ddr,
2098                               loop_vec_info loop_vinfo)
2099 {
2100   unsigned int i;
2101   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2102   int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2103   struct data_reference *dra = DDR_A (ddr);
2104   struct data_reference *drb = DDR_B (ddr);
2105   stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
2106   stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
2107   int dra_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dra))));
2108   int drb_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (drb))));
2109   lambda_vector dist_v;
2110   unsigned int loop_depth;
2111
2112   if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
2113     return;
2114
2115   if (dra == drb)
2116     return;
2117
2118   if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
2119     return;
2120
2121   /* Loop-based vectorization and known data dependence.  */
2122   if (DDR_NUM_DIST_VECTS (ddr) == 0)
2123     return;
2124
2125   /* Data-dependence analysis reports a distance vector of zero
2126      for data-references that overlap only in the first iteration
2127      but have different sign step (see PR45764).
2128      So as a sanity check require equal DR_STEP.  */
2129   if (!operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))
2130     return;
2131
2132   loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr));
2133   FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
2134     {
2135       int dist = dist_v[loop_depth];
2136
2137       if (dump_enabled_p ())
2138         dump_printf_loc (MSG_NOTE, vect_location,
2139                          "dependence distance  = %d.", dist);
2140
2141       /* Same loop iteration.  */
2142       if (dist == 0
2143           || (dist % vectorization_factor == 0 && dra_size == drb_size))
2144         {
2145           /* Two references with distance zero have the same alignment.  */
2146           STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a).safe_push (drb);
2147           STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b).safe_push (dra);
2148           if (dump_enabled_p ())
2149             {
2150               dump_printf_loc (MSG_NOTE, vect_location,
2151                                "accesses have the same alignment.");
2152               dump_printf (MSG_NOTE,
2153                            "dependence distance modulo vf == 0 between ");
2154               dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
2155               dump_printf (MSG_NOTE,  " and ");
2156               dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
2157             }
2158         }
2159     }
2160 }
2161
2162
2163 /* Function vect_analyze_data_refs_alignment
2164
2165    Analyze the alignment of the data-references in the loop.
2166    Return FALSE if a data reference is found that cannot be vectorized.  */
2167
2168 bool
2169 vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo,
2170                                   bb_vec_info bb_vinfo)
2171 {
2172   if (dump_enabled_p ())
2173     dump_printf_loc (MSG_NOTE, vect_location,
2174                      "=== vect_analyze_data_refs_alignment ===");
2175
2176   /* Mark groups of data references with same alignment using
2177      data dependence information.  */
2178   if (loop_vinfo)
2179     {
2180       vec<ddr_p> ddrs = LOOP_VINFO_DDRS (loop_vinfo);
2181       struct data_dependence_relation *ddr;
2182       unsigned int i;
2183
2184       FOR_EACH_VEC_ELT (ddrs, i, ddr)
2185         vect_find_same_alignment_drs (ddr, loop_vinfo);
2186     }
2187
2188   if (!vect_compute_data_refs_alignment (loop_vinfo, bb_vinfo))
2189     {
2190       if (dump_enabled_p ())
2191         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
2192                          "not vectorized: can't calculate alignment "
2193                          "for data ref.");
2194       return false;
2195     }
2196
2197   return true;
2198 }
2199
2200
2201 /* Analyze groups of accesses: check that DR belongs to a group of
2202    accesses of legal size, step, etc.  Detect gaps, single element
2203    interleaving, and other special cases. Set grouped access info.
2204    Collect groups of strided stores for further use in SLP analysis.  */
2205
2206 static bool
2207 vect_analyze_group_access (struct data_reference *dr)
2208 {
2209   tree step = DR_STEP (dr);
2210   tree scalar_type = TREE_TYPE (DR_REF (dr));
2211   HOST_WIDE_INT type_size = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type));
2212   gimple stmt = DR_STMT (dr);
2213   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2214   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2215   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
2216   HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
2217   HOST_WIDE_INT groupsize, last_accessed_element = 1;
2218   bool slp_impossible = false;
2219   struct loop *loop = NULL;
2220
2221   if (loop_vinfo)
2222     loop = LOOP_VINFO_LOOP (loop_vinfo);
2223
2224   /* For interleaving, GROUPSIZE is STEP counted in elements, i.e., the
2225      size of the interleaving group (including gaps).  */
2226   groupsize = dr_step / type_size;
2227
2228   /* Not consecutive access is possible only if it is a part of interleaving.  */
2229   if (!GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
2230     {
2231       /* Check if it this DR is a part of interleaving, and is a single
2232          element of the group that is accessed in the loop.  */
2233
2234       /* Gaps are supported only for loads. STEP must be a multiple of the type
2235          size.  The size of the group must be a power of 2.  */
2236       if (DR_IS_READ (dr)
2237           && (dr_step % type_size) == 0
2238           && groupsize > 0
2239           && exact_log2 (groupsize) != -1)
2240         {
2241           GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) = stmt;
2242           GROUP_SIZE (vinfo_for_stmt (stmt)) = groupsize;
2243           if (dump_enabled_p ())
2244             {
2245               dump_printf_loc (MSG_NOTE, vect_location, 
2246                                "Detected single element interleaving ");
2247               dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr));
2248               dump_printf (MSG_NOTE, " step ");
2249               dump_generic_expr (MSG_NOTE, TDF_SLIM, step);
2250             }
2251
2252           if (loop_vinfo)
2253             {
2254               if (dump_enabled_p ())
2255                 dump_printf_loc (MSG_NOTE, vect_location,
2256                                  "Data access with gaps requires scalar "
2257                                  "epilogue loop");
2258               if (loop->inner)
2259                 {
2260                   if (dump_enabled_p ())
2261                     dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2262                                      "Peeling for outer loop is not"
2263                                      " supported");
2264                   return false;
2265                 }
2266
2267               LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo) = true;
2268             }
2269
2270           return true;
2271         }
2272
2273       if (dump_enabled_p ())
2274         {
2275           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2276                            "not consecutive access ");
2277           dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
2278         }
2279
2280       if (bb_vinfo)
2281         {
2282           /* Mark the statement as unvectorizable.  */
2283           STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) = false;
2284           return true;
2285         }
2286
2287       return false;
2288     }
2289
2290   if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) == stmt)
2291     {
2292       /* First stmt in the interleaving chain. Check the chain.  */
2293       gimple next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt));
2294       struct data_reference *data_ref = dr;
2295       unsigned int count = 1;
2296       tree next_step;
2297       tree prev_init = DR_INIT (data_ref);
2298       gimple prev = stmt;
2299       HOST_WIDE_INT diff, count_in_bytes, gaps = 0;
2300
2301       while (next)
2302         {
2303           /* Skip same data-refs.  In case that two or more stmts share
2304              data-ref (supported only for loads), we vectorize only the first
2305              stmt, and the rest get their vectorized loads from the first
2306              one.  */
2307           if (!tree_int_cst_compare (DR_INIT (data_ref),
2308                                      DR_INIT (STMT_VINFO_DATA_REF (
2309                                                    vinfo_for_stmt (next)))))
2310             {
2311               if (DR_IS_WRITE (data_ref))
2312                 {
2313                   if (dump_enabled_p ())
2314                     dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
2315                                      "Two store stmts share the same dr.");
2316                   return false;
2317                 }
2318
2319               /* Check that there is no load-store dependencies for this loads
2320                  to prevent a case of load-store-load to the same location.  */
2321               if (GROUP_READ_WRITE_DEPENDENCE (vinfo_for_stmt (next))
2322                   || GROUP_READ_WRITE_DEPENDENCE (vinfo_for_stmt (prev)))
2323                 {
2324                   if (dump_enabled_p ())
2325                     dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
2326                                      "READ_WRITE dependence in interleaving.");
2327                   return false;
2328                 }
2329
2330               /* For load use the same data-ref load.  */
2331               GROUP_SAME_DR_STMT (vinfo_for_stmt (next)) = prev;
2332
2333               prev = next;
2334               next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next));
2335               continue;
2336             }
2337
2338           prev = next;
2339
2340           /* Check that all the accesses have the same STEP.  */
2341           next_step = DR_STEP (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
2342           if (tree_int_cst_compare (step, next_step))
2343             {
2344               if (dump_enabled_p ())
2345                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
2346                                  "not consecutive access in interleaving");
2347               return false;
2348             }
2349
2350           data_ref = STMT_VINFO_DATA_REF (vinfo_for_stmt (next));
2351           /* Check that the distance between two accesses is equal to the type
2352              size. Otherwise, we have gaps.  */
2353           diff = (TREE_INT_CST_LOW (DR_INIT (data_ref))
2354                   - TREE_INT_CST_LOW (prev_init)) / type_size;
2355           if (diff != 1)
2356             {
2357               /* FORNOW: SLP of accesses with gaps is not supported.  */
2358               slp_impossible = true;
2359               if (DR_IS_WRITE (data_ref))
2360                 {
2361                   if (dump_enabled_p ())
2362                     dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
2363                                      "interleaved store with gaps");
2364                   return false;
2365                 }
2366
2367               gaps += diff - 1;
2368             }
2369
2370           last_accessed_element += diff;
2371
2372           /* Store the gap from the previous member of the group. If there is no
2373              gap in the access, GROUP_GAP is always 1.  */
2374           GROUP_GAP (vinfo_for_stmt (next)) = diff;
2375
2376           prev_init = DR_INIT (data_ref);
2377           next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next));
2378           /* Count the number of data-refs in the chain.  */
2379           count++;
2380         }
2381
2382       /* COUNT is the number of accesses found, we multiply it by the size of
2383          the type to get COUNT_IN_BYTES.  */
2384       count_in_bytes = type_size * count;
2385
2386       /* Check that the size of the interleaving (including gaps) is not
2387          greater than STEP.  */
2388       if (dr_step && dr_step < count_in_bytes + gaps * type_size)
2389         {
2390           if (dump_enabled_p ())
2391             {
2392               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
2393                                "interleaving size is greater than step for ");
2394               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (dr));
2395             }
2396           return false;
2397         }
2398
2399       /* Check that the size of the interleaving is equal to STEP for stores,
2400          i.e., that there are no gaps.  */
2401       if (dr_step && dr_step != count_in_bytes)
2402         {
2403           if (DR_IS_READ (dr))
2404             {
2405               slp_impossible = true;
2406               /* There is a gap after the last load in the group. This gap is a
2407                  difference between the groupsize and the number of elements.
2408                  When there is no gap, this difference should be 0.  */
2409               GROUP_GAP (vinfo_for_stmt (stmt)) = groupsize - count;
2410             }
2411           else
2412             {
2413               if (dump_enabled_p ())
2414                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
2415                                  "interleaved store with gaps");
2416               return false;
2417             }
2418         }
2419
2420       /* Check that STEP is a multiple of type size.  */
2421       if (dr_step && (dr_step % type_size) != 0)
2422         {
2423           if (dump_enabled_p ())
2424             {
2425               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2426                                "step is not a multiple of type size: step ");
2427               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, step);
2428               dump_printf (MSG_MISSED_OPTIMIZATION, " size ");
2429               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
2430                                  TYPE_SIZE_UNIT (scalar_type));
2431             }
2432           return false;
2433         }
2434
2435       if (groupsize == 0)
2436         groupsize = count;
2437
2438       GROUP_SIZE (vinfo_for_stmt (stmt)) = groupsize;
2439       if (dump_enabled_p ())
2440         dump_printf_loc (MSG_NOTE, vect_location, 
2441                          "Detected interleaving of size %d", (int)groupsize);
2442
2443       /* SLP: create an SLP data structure for every interleaving group of
2444          stores for further analysis in vect_analyse_slp.  */
2445       if (DR_IS_WRITE (dr) && !slp_impossible)
2446         {
2447           if (loop_vinfo)
2448             LOOP_VINFO_GROUPED_STORES (loop_vinfo).safe_push (stmt);
2449           if (bb_vinfo)
2450             BB_VINFO_GROUPED_STORES (bb_vinfo).safe_push (stmt);
2451         }
2452
2453       /* There is a gap in the end of the group.  */
2454       if (groupsize - last_accessed_element > 0 && loop_vinfo)
2455         {
2456           if (dump_enabled_p ())
2457             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2458                              "Data access with gaps requires scalar "
2459                              "epilogue loop");
2460           if (loop->inner)
2461             {
2462               if (dump_enabled_p ())
2463                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
2464                                  "Peeling for outer loop is not supported");
2465               return false;
2466             }
2467
2468           LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo) = true;
2469         }
2470     }
2471
2472   return true;
2473 }
2474
2475
2476 /* Analyze the access pattern of the data-reference DR.
2477    In case of non-consecutive accesses call vect_analyze_group_access() to
2478    analyze groups of accesses.  */
2479
2480 static bool
2481 vect_analyze_data_ref_access (struct data_reference *dr)
2482 {
2483   tree step = DR_STEP (dr);
2484   tree scalar_type = TREE_TYPE (DR_REF (dr));
2485   gimple stmt = DR_STMT (dr);
2486   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2487   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2488   struct loop *loop = NULL;
2489
2490   if (loop_vinfo)
2491     loop = LOOP_VINFO_LOOP (loop_vinfo);
2492
2493   if (loop_vinfo && !step)
2494     {
2495       if (dump_enabled_p ())
2496         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
2497                          "bad data-ref access in loop");
2498       return false;
2499     }
2500
2501   /* Allow invariant loads in not nested loops.  */
2502   if (loop_vinfo && integer_zerop (step))
2503     {
2504       GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) = NULL;
2505       if (nested_in_vect_loop_p (loop, stmt))
2506         {
2507           if (dump_enabled_p ())
2508             dump_printf_loc (MSG_NOTE, vect_location,
2509                              "zero step in inner loop of nest");
2510           return false;
2511         }
2512       return DR_IS_READ (dr);
2513     }
2514
2515   if (loop && nested_in_vect_loop_p (loop, stmt))
2516     {
2517       /* Interleaved accesses are not yet supported within outer-loop
2518         vectorization for references in the inner-loop.  */
2519       GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) = NULL;
2520
2521       /* For the rest of the analysis we use the outer-loop step.  */
2522       step = STMT_VINFO_DR_STEP (stmt_info);
2523       if (integer_zerop (step))
2524         {
2525           if (dump_enabled_p ())
2526             dump_printf_loc (MSG_NOTE, vect_location,
2527                              "zero step in outer loop.");
2528           if (DR_IS_READ (dr))
2529             return true;
2530           else
2531             return false;
2532         }
2533     }
2534
2535   /* Consecutive?  */
2536   if (TREE_CODE (step) == INTEGER_CST)
2537     {
2538       HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
2539       if (!tree_int_cst_compare (step, TYPE_SIZE_UNIT (scalar_type))
2540           || (dr_step < 0
2541               && !compare_tree_int (TYPE_SIZE_UNIT (scalar_type), -dr_step)))
2542         {
2543           /* Mark that it is not interleaving.  */
2544           GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) = NULL;
2545           return true;
2546         }
2547     }
2548
2549   if (loop && nested_in_vect_loop_p (loop, stmt))
2550     {
2551       if (dump_enabled_p ())
2552         dump_printf_loc (MSG_NOTE, vect_location,
2553                          "grouped access in outer loop.");
2554       return false;
2555     }
2556
2557   /* Assume this is a DR handled by non-constant strided load case.  */
2558   if (TREE_CODE (step) != INTEGER_CST)
2559     return STMT_VINFO_STRIDE_LOAD_P (stmt_info);
2560
2561   /* Not consecutive access - check if it's a part of interleaving group.  */
2562   return vect_analyze_group_access (dr);
2563 }
2564
2565
2566 /* Function vect_analyze_data_ref_accesses.
2567
2568    Analyze the access pattern of all the data references in the loop.
2569
2570    FORNOW: the only access pattern that is considered vectorizable is a
2571            simple step 1 (consecutive) access.
2572
2573    FORNOW: handle only arrays and pointer accesses.  */
2574
2575 bool
2576 vect_analyze_data_ref_accesses (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
2577 {
2578   unsigned int i;
2579   vec<data_reference_p> datarefs;
2580   struct data_reference *dr;
2581
2582   if (dump_enabled_p ())
2583     dump_printf_loc (MSG_NOTE, vect_location,
2584                      "=== vect_analyze_data_ref_accesses ===");
2585
2586   if (loop_vinfo)
2587     datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
2588   else
2589     datarefs = BB_VINFO_DATAREFS (bb_vinfo);
2590
2591   FOR_EACH_VEC_ELT (datarefs, i, dr)
2592     if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) 
2593         && !vect_analyze_data_ref_access (dr))
2594       {
2595         if (dump_enabled_p ())
2596           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
2597                            "not vectorized: complicated access pattern.");
2598
2599         if (bb_vinfo)
2600           {
2601             /* Mark the statement as not vectorizable.  */
2602             STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) = false;
2603             continue;
2604           }
2605         else
2606           return false;
2607       }
2608
2609   return true;
2610 }
2611
2612 /* Function vect_prune_runtime_alias_test_list.
2613
2614    Prune a list of ddrs to be tested at run-time by versioning for alias.
2615    Return FALSE if resulting list of ddrs is longer then allowed by
2616    PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS, otherwise return TRUE.  */
2617
2618 bool
2619 vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo)
2620 {
2621   vec<ddr_p>  ddrs =
2622     LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo);
2623   unsigned i, j;
2624
2625   if (dump_enabled_p ())
2626     dump_printf_loc (MSG_NOTE, vect_location,
2627                      "=== vect_prune_runtime_alias_test_list ===");
2628
2629   for (i = 0; i < ddrs.length (); )
2630     {
2631       bool found;
2632       ddr_p ddr_i;
2633
2634       ddr_i = ddrs[i];
2635       found = false;
2636
2637       for (j = 0; j < i; j++)
2638         {
2639           ddr_p ddr_j = ddrs[j];
2640
2641           if (vect_vfa_range_equal (ddr_i, ddr_j))
2642             {
2643               if (dump_enabled_p ())
2644                 {
2645                   dump_printf_loc (MSG_NOTE, vect_location,
2646                                    "found equal ranges ");
2647                   dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_A (ddr_i)));
2648                   dump_printf (MSG_NOTE,  ", ");
2649                   dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_B (ddr_i)));
2650                   dump_printf (MSG_NOTE,  " and ");
2651                   dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_A (ddr_j)));
2652                   dump_printf (MSG_NOTE,  ", ");
2653                   dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_B (ddr_j)));
2654                 }
2655               found = true;
2656               break;
2657             }
2658         }
2659
2660       if (found)
2661       {
2662         ddrs.ordered_remove (i);
2663         continue;
2664       }
2665       i++;
2666     }
2667
2668   if (ddrs.length () >
2669        (unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS))
2670     {
2671       if (dump_enabled_p ())
2672         {
2673           dump_printf_loc (MSG_MISSED_OPTIMIZATION,  vect_location, 
2674                            "disable versioning for alias - max number of "
2675                            "generated checks exceeded.");
2676         }
2677
2678       LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo).truncate (0);
2679
2680       return false;
2681     }
2682
2683   return true;
2684 }
2685
2686 /* Check whether a non-affine read in stmt is suitable for gather load
2687    and if so, return a builtin decl for that operation.  */
2688
2689 tree
2690 vect_check_gather (gimple stmt, loop_vec_info loop_vinfo, tree *basep,
2691                    tree *offp, int *scalep)
2692 {
2693   HOST_WIDE_INT scale = 1, pbitpos, pbitsize;
2694   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2695   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2696   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
2697   tree offtype = NULL_TREE;
2698   tree decl, base, off;
2699   enum machine_mode pmode;
2700   int punsignedp, pvolatilep;
2701
2702   /* The gather builtins need address of the form
2703      loop_invariant + vector * {1, 2, 4, 8}
2704      or
2705      loop_invariant + sign_extend (vector) * { 1, 2, 4, 8 }.
2706      Unfortunately DR_BASE_ADDRESS/DR_OFFSET can be a mixture
2707      of loop invariants/SSA_NAMEs defined in the loop, with casts,
2708      multiplications and additions in it.  To get a vector, we need
2709      a single SSA_NAME that will be defined in the loop and will
2710      contain everything that is not loop invariant and that can be
2711      vectorized.  The following code attempts to find such a preexistng
2712      SSA_NAME OFF and put the loop invariants into a tree BASE
2713      that can be gimplified before the loop.  */
2714   base = get_inner_reference (DR_REF (dr), &pbitsize, &pbitpos, &off,
2715                               &pmode, &punsignedp, &pvolatilep, false);
2716   gcc_assert (base != NULL_TREE && (pbitpos % BITS_PER_UNIT) == 0);
2717
2718   if (TREE_CODE (base) == MEM_REF)
2719     {
2720       if (!integer_zerop (TREE_OPERAND (base, 1)))
2721         {
2722           if (off == NULL_TREE)
2723             {
2724               double_int moff = mem_ref_offset (base);
2725               off = double_int_to_tree (sizetype, moff);
2726             }
2727           else
2728             off = size_binop (PLUS_EXPR, off,
2729                               fold_convert (sizetype, TREE_OPERAND (base, 1)));
2730         }
2731       base = TREE_OPERAND (base, 0);
2732     }
2733   else
2734     base = build_fold_addr_expr (base);
2735
2736   if (off == NULL_TREE)
2737     off = size_zero_node;
2738
2739   /* If base is not loop invariant, either off is 0, then we start with just
2740      the constant offset in the loop invariant BASE and continue with base
2741      as OFF, otherwise give up.
2742      We could handle that case by gimplifying the addition of base + off
2743      into some SSA_NAME and use that as off, but for now punt.  */
2744   if (!expr_invariant_in_loop_p (loop, base))
2745     {
2746       if (!integer_zerop (off))
2747         return NULL_TREE;
2748       off = base;
2749       base = size_int (pbitpos / BITS_PER_UNIT);
2750     }
2751   /* Otherwise put base + constant offset into the loop invariant BASE
2752      and continue with OFF.  */
2753   else
2754     {
2755       base = fold_convert (sizetype, base);
2756       base = size_binop (PLUS_EXPR, base, size_int (pbitpos / BITS_PER_UNIT));
2757     }
2758
2759   /* OFF at this point may be either a SSA_NAME or some tree expression
2760      from get_inner_reference.  Try to peel off loop invariants from it
2761      into BASE as long as possible.  */
2762   STRIP_NOPS (off);
2763   while (offtype == NULL_TREE)
2764     {
2765       enum tree_code code;
2766       tree op0, op1, add = NULL_TREE;
2767
2768       if (TREE_CODE (off) == SSA_NAME)
2769         {
2770           gimple def_stmt = SSA_NAME_DEF_STMT (off);
2771
2772           if (expr_invariant_in_loop_p (loop, off))
2773             return NULL_TREE;
2774
2775           if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
2776             break;
2777
2778           op0 = gimple_assign_rhs1 (def_stmt);
2779           code = gimple_assign_rhs_code (def_stmt);
2780           op1 = gimple_assign_rhs2 (def_stmt);
2781         }
2782       else
2783         {
2784           if (get_gimple_rhs_class (TREE_CODE (off)) == GIMPLE_TERNARY_RHS)
2785             return NULL_TREE;
2786           code = TREE_CODE (off);
2787           extract_ops_from_tree (off, &code, &op0, &op1);
2788         }
2789       switch (code)
2790         {
2791         case POINTER_PLUS_EXPR:
2792         case PLUS_EXPR:
2793           if (expr_invariant_in_loop_p (loop, op0))
2794             {
2795               add = op0;
2796               off = op1;
2797             do_add:
2798               add = fold_convert (sizetype, add);
2799               if (scale != 1)
2800                 add = size_binop (MULT_EXPR, add, size_int (scale));
2801               base = size_binop (PLUS_EXPR, base, add);
2802               continue;
2803             }
2804           if (expr_invariant_in_loop_p (loop, op1))
2805             {
2806               add = op1;
2807               off = op0;
2808               goto do_add;
2809             }
2810           break;
2811         case MINUS_EXPR:
2812           if (expr_invariant_in_loop_p (loop, op1))
2813             {
2814               add = fold_convert (sizetype, op1);
2815               add = size_binop (MINUS_EXPR, size_zero_node, add);
2816               off = op0;
2817               goto do_add;
2818             }
2819           break;
2820         case MULT_EXPR:
2821           if (scale == 1 && host_integerp (op1, 0))
2822             {
2823               scale = tree_low_cst (op1, 0);
2824               off = op0;
2825               continue;
2826             }
2827           break;
2828         case SSA_NAME:
2829           off = op0;
2830           continue;
2831         CASE_CONVERT:
2832           if (!POINTER_TYPE_P (TREE_TYPE (op0))
2833               && !INTEGRAL_TYPE_P (TREE_TYPE (op0)))
2834             break;
2835           if (TYPE_PRECISION (TREE_TYPE (op0))
2836               == TYPE_PRECISION (TREE_TYPE (off)))
2837             {
2838               off = op0;
2839               continue;
2840             }
2841           if (TYPE_PRECISION (TREE_TYPE (op0))
2842               < TYPE_PRECISION (TREE_TYPE (off)))
2843             {
2844               off = op0;
2845               offtype = TREE_TYPE (off);
2846               STRIP_NOPS (off);
2847               continue;
2848             }
2849           break;
2850         default:
2851           break;
2852         }
2853       break;
2854     }
2855
2856   /* If at the end OFF still isn't a SSA_NAME or isn't
2857      defined in the loop, punt.  */
2858   if (TREE_CODE (off) != SSA_NAME
2859       || expr_invariant_in_loop_p (loop, off))
2860     return NULL_TREE;
2861
2862   if (offtype == NULL_TREE)
2863     offtype = TREE_TYPE (off);
2864
2865   decl = targetm.vectorize.builtin_gather (STMT_VINFO_VECTYPE (stmt_info),
2866                                            offtype, scale);
2867   if (decl == NULL_TREE)
2868     return NULL_TREE;
2869
2870   if (basep)
2871     *basep = base;
2872   if (offp)
2873     *offp = off;
2874   if (scalep)
2875     *scalep = scale;
2876   return decl;
2877 }
2878
2879 /* Check wether a non-affine load in STMT (being in the loop referred to
2880    in LOOP_VINFO) is suitable for handling as strided load.  That is the case
2881    if its address is a simple induction variable.  If so return the base
2882    of that induction variable in *BASEP and the (loop-invariant) step
2883    in *STEPP, both only when that pointer is non-zero.
2884
2885    This handles ARRAY_REFs (with variant index) and MEM_REFs (with variant
2886    base pointer) only.  */
2887
2888 static bool
2889 vect_check_strided_load (gimple stmt, loop_vec_info loop_vinfo)
2890 {
2891   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2892   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2893   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
2894   tree base, off;
2895   affine_iv iv;
2896
2897   if (!DR_IS_READ (dr))
2898     return false;
2899
2900   base = DR_REF (dr);
2901
2902   if (TREE_CODE (base) == ARRAY_REF)
2903     {
2904       off = TREE_OPERAND (base, 1);
2905       base = TREE_OPERAND (base, 0);
2906     }
2907   else if (TREE_CODE (base) == MEM_REF)
2908     {
2909       off = TREE_OPERAND (base, 0);
2910       base = TREE_OPERAND (base, 1);
2911     }
2912   else
2913     return false;
2914
2915   if (TREE_CODE (off) != SSA_NAME)
2916     return false;
2917
2918   if (!expr_invariant_in_loop_p (loop, base)
2919       || !simple_iv (loop, loop_containing_stmt (stmt), off, &iv, true))
2920     return false;
2921
2922   return true;
2923 }
2924
2925 /* Function vect_analyze_data_refs.
2926
2927   Find all the data references in the loop or basic block.
2928
2929    The general structure of the analysis of data refs in the vectorizer is as
2930    follows:
2931    1- vect_analyze_data_refs(loop/bb): call
2932       compute_data_dependences_for_loop/bb to find and analyze all data-refs
2933       in the loop/bb and their dependences.
2934    2- vect_analyze_dependences(): apply dependence testing using ddrs.
2935    3- vect_analyze_drs_alignment(): check that ref_stmt.alignment is ok.
2936    4- vect_analyze_drs_access(): check that ref_stmt.step is ok.
2937
2938 */
2939
2940 bool
2941 vect_analyze_data_refs (loop_vec_info loop_vinfo,
2942                         bb_vec_info bb_vinfo,
2943                         int *min_vf)
2944 {
2945   struct loop *loop = NULL;
2946   basic_block bb = NULL;
2947   unsigned int i;
2948   vec<data_reference_p> datarefs;
2949   struct data_reference *dr;
2950   tree scalar_type;
2951   bool res, stop_bb_analysis = false;
2952
2953   if (dump_enabled_p ())
2954     dump_printf_loc (MSG_NOTE, vect_location,
2955                      "=== vect_analyze_data_refs ===\n");
2956
2957   if (loop_vinfo)
2958     {
2959       loop = LOOP_VINFO_LOOP (loop_vinfo);
2960       res = compute_data_dependences_for_loop
2961         (loop, true,
2962          &LOOP_VINFO_LOOP_NEST (loop_vinfo),
2963          &LOOP_VINFO_DATAREFS (loop_vinfo),
2964          &LOOP_VINFO_DDRS (loop_vinfo));
2965
2966       if (!res)
2967         {
2968           if (dump_enabled_p ())
2969             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
2970                              "not vectorized: loop contains function calls"
2971                              " or data references that cannot be analyzed");
2972           return false;
2973         }
2974
2975       datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
2976     }
2977   else
2978     {
2979       gimple_stmt_iterator gsi;
2980
2981       bb = BB_VINFO_BB (bb_vinfo);
2982       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2983         {
2984           gimple stmt = gsi_stmt (gsi);
2985           if (!find_data_references_in_stmt (NULL, stmt,
2986                                              &BB_VINFO_DATAREFS (bb_vinfo)))
2987             {
2988               /* Mark the rest of the basic-block as unvectorizable.  */
2989               for (; !gsi_end_p (gsi); gsi_next (&gsi))
2990                 {
2991                   stmt = gsi_stmt (gsi);
2992                   STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt)) = false;
2993                 }
2994               break;
2995             }
2996         }
2997       if (!compute_all_dependences (BB_VINFO_DATAREFS (bb_vinfo),
2998                                     &BB_VINFO_DDRS (bb_vinfo),
2999                                     vNULL, true))
3000         {
3001           if (dump_enabled_p ())
3002             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
3003                              "not vectorized: basic block contains function"
3004                              " calls or data references that cannot be"
3005                              " analyzed");
3006           return false;
3007         }
3008
3009       datarefs = BB_VINFO_DATAREFS (bb_vinfo);
3010     }
3011
3012   /* Go through the data-refs, check that the analysis succeeded.  Update
3013      pointer from stmt_vec_info struct to DR and vectype.  */
3014
3015   FOR_EACH_VEC_ELT (datarefs, i, dr)
3016     {
3017       gimple stmt;
3018       stmt_vec_info stmt_info;
3019       tree base, offset, init;
3020       bool gather = false;
3021       int vf;
3022
3023       if (!dr || !DR_REF (dr))
3024         {
3025           if (dump_enabled_p ())
3026             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3027                              "not vectorized: unhandled data-ref ");
3028           return false;
3029         }
3030
3031       stmt = DR_STMT (dr);
3032       stmt_info = vinfo_for_stmt (stmt);
3033
3034       if (stop_bb_analysis)
3035         {
3036           STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3037           continue;
3038         }
3039
3040       /* Check that analysis of the data-ref succeeded.  */
3041       if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr) || !DR_INIT (dr)
3042           || !DR_STEP (dr))
3043         {
3044           /* If target supports vector gather loads, see if they can't
3045              be used.  */
3046           if (loop_vinfo
3047               && DR_IS_READ (dr)
3048               && !TREE_THIS_VOLATILE (DR_REF (dr))
3049               && targetm.vectorize.builtin_gather != NULL
3050               && !nested_in_vect_loop_p (loop, stmt))
3051             {
3052               struct data_reference *newdr
3053                 = create_data_ref (NULL, loop_containing_stmt (stmt),
3054                                    DR_REF (dr), stmt, true);
3055               gcc_assert (newdr != NULL && DR_REF (newdr));
3056               if (DR_BASE_ADDRESS (newdr)
3057                   && DR_OFFSET (newdr)
3058                   && DR_INIT (newdr)
3059                   && DR_STEP (newdr)
3060                   && integer_zerop (DR_STEP (newdr)))
3061                 {
3062                   dr = newdr;
3063                   gather = true;
3064                 }
3065               else
3066                 free_data_ref (newdr);
3067             }
3068
3069           if (!gather)
3070             {
3071               if (dump_enabled_p ())
3072                 {
3073                   dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
3074                                    "not vectorized: data ref analysis "
3075                                    "failed ");
3076                   dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3077                 }
3078
3079               if (bb_vinfo)
3080                 {
3081                   STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3082                   stop_bb_analysis = true;
3083                   continue;
3084                 }
3085
3086               return false;
3087             }
3088         }
3089
3090       if (TREE_CODE (DR_BASE_ADDRESS (dr)) == INTEGER_CST)
3091         {
3092           if (dump_enabled_p ())
3093             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3094                              "not vectorized: base addr of dr is a "
3095                              "constant");
3096
3097           if (bb_vinfo)
3098             {
3099               STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3100               stop_bb_analysis = true;
3101               continue;
3102             }
3103
3104           if (gather)
3105             free_data_ref (dr);
3106           return false;
3107         }
3108
3109       if (TREE_THIS_VOLATILE (DR_REF (dr)))
3110         {
3111           if (dump_enabled_p ())
3112             {
3113               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3114                                "not vectorized: volatile type ");
3115               dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3116             }
3117
3118           if (bb_vinfo)
3119             {
3120               STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3121               stop_bb_analysis = true;
3122               continue;
3123             }
3124
3125           return false;
3126         }
3127
3128       if (stmt_can_throw_internal (stmt))
3129         {
3130           if (dump_enabled_p ())
3131             {
3132               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3133                                "not vectorized: statement can throw an "
3134                                "exception ");
3135               dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3136             }
3137
3138           if (bb_vinfo)
3139             {
3140               STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3141               stop_bb_analysis = true;
3142               continue;
3143             }
3144
3145           if (gather)
3146             free_data_ref (dr);
3147           return false;
3148         }
3149
3150       if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
3151           && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
3152         {
3153           if (dump_enabled_p ())
3154             {
3155               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3156                                "not vectorized: statement is bitfield "
3157                                "access ");
3158               dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3159             }
3160
3161           if (bb_vinfo)
3162             {
3163               STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3164               stop_bb_analysis = true;
3165               continue;
3166             }
3167
3168           if (gather)
3169             free_data_ref (dr);
3170           return false;
3171         }
3172
3173       base = unshare_expr (DR_BASE_ADDRESS (dr));
3174       offset = unshare_expr (DR_OFFSET (dr));
3175       init = unshare_expr (DR_INIT (dr));
3176
3177       if (is_gimple_call (stmt))
3178         {
3179           if (dump_enabled_p ())
3180             {
3181               dump_printf_loc (MSG_MISSED_OPTIMIZATION,  vect_location,
3182                                "not vectorized: dr in a call ");
3183               dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3184             }
3185
3186           if (bb_vinfo)
3187             {
3188               STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3189               stop_bb_analysis = true;
3190               continue;
3191             }
3192
3193           if (gather)
3194             free_data_ref (dr);
3195           return false;
3196         }
3197
3198       /* Update DR field in stmt_vec_info struct.  */
3199
3200       /* If the dataref is in an inner-loop of the loop that is considered for
3201          for vectorization, we also want to analyze the access relative to
3202          the outer-loop (DR contains information only relative to the
3203          inner-most enclosing loop).  We do that by building a reference to the
3204          first location accessed by the inner-loop, and analyze it relative to
3205          the outer-loop.  */
3206       if (loop && nested_in_vect_loop_p (loop, stmt))
3207         {
3208           tree outer_step, outer_base, outer_init;
3209           HOST_WIDE_INT pbitsize, pbitpos;
3210           tree poffset;
3211           enum machine_mode pmode;
3212           int punsignedp, pvolatilep;
3213           affine_iv base_iv, offset_iv;
3214           tree dinit;
3215
3216           /* Build a reference to the first location accessed by the
3217              inner-loop: *(BASE+INIT).  (The first location is actually
3218              BASE+INIT+OFFSET, but we add OFFSET separately later).  */
3219           tree inner_base = build_fold_indirect_ref
3220                                 (fold_build_pointer_plus (base, init));
3221
3222           if (dump_enabled_p ())
3223             {
3224               dump_printf_loc (MSG_NOTE, vect_location,
3225                                "analyze in outer-loop: ");
3226               dump_generic_expr (MSG_NOTE, TDF_SLIM, inner_base);
3227             }
3228
3229           outer_base = get_inner_reference (inner_base, &pbitsize, &pbitpos,
3230                           &poffset, &pmode, &punsignedp, &pvolatilep, false);
3231           gcc_assert (outer_base != NULL_TREE);
3232
3233           if (pbitpos % BITS_PER_UNIT != 0)
3234             {
3235               if (dump_enabled_p ())
3236                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3237                                  "failed: bit offset alignment.\n");
3238               return false;
3239             }
3240
3241           outer_base = build_fold_addr_expr (outer_base);
3242           if (!simple_iv (loop, loop_containing_stmt (stmt), outer_base,
3243                           &base_iv, false))
3244             {
3245               if (dump_enabled_p ())
3246                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
3247                                  "failed: evolution of base is not affine.\n");
3248               return false;
3249             }
3250
3251           if (offset)
3252             {
3253               if (poffset)
3254                 poffset = fold_build2 (PLUS_EXPR, TREE_TYPE (offset), offset,
3255                                        poffset);
3256               else
3257                 poffset = offset;
3258             }
3259
3260           if (!poffset)
3261             {
3262               offset_iv.base = ssize_int (0);
3263               offset_iv.step = ssize_int (0);
3264             }
3265           else if (!simple_iv (loop, loop_containing_stmt (stmt), poffset,
3266                                &offset_iv, false))
3267             {
3268               if (dump_enabled_p ())
3269                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
3270                                  "evolution of offset is not affine.\n");
3271               return false;
3272             }
3273
3274           outer_init = ssize_int (pbitpos / BITS_PER_UNIT);
3275           split_constant_offset (base_iv.base, &base_iv.base, &dinit);
3276           outer_init =  size_binop (PLUS_EXPR, outer_init, dinit);
3277           split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
3278           outer_init =  size_binop (PLUS_EXPR, outer_init, dinit);
3279
3280           outer_step = size_binop (PLUS_EXPR,
3281                                 fold_convert (ssizetype, base_iv.step),
3282                                 fold_convert (ssizetype, offset_iv.step));
3283
3284           STMT_VINFO_DR_STEP (stmt_info) = outer_step;
3285           /* FIXME: Use canonicalize_base_object_address (base_iv.base); */
3286           STMT_VINFO_DR_BASE_ADDRESS (stmt_info) = base_iv.base;
3287           STMT_VINFO_DR_INIT (stmt_info) = outer_init;
3288           STMT_VINFO_DR_OFFSET (stmt_info) =
3289                                 fold_convert (ssizetype, offset_iv.base);
3290           STMT_VINFO_DR_ALIGNED_TO (stmt_info) =
3291                                 size_int (highest_pow2_factor (offset_iv.base));
3292
3293           if (dump_enabled_p ())
3294             {
3295               dump_printf_loc (MSG_NOTE, vect_location,
3296                                "\touter base_address: ");
3297               dump_generic_expr (MSG_NOTE, TDF_SLIM,
3298                                  STMT_VINFO_DR_BASE_ADDRESS (stmt_info));
3299               dump_printf (MSG_NOTE, "\n\touter offset from base address: ");
3300               dump_generic_expr (MSG_NOTE, TDF_SLIM,
3301                                  STMT_VINFO_DR_OFFSET (stmt_info));
3302               dump_printf (MSG_NOTE,
3303                            "\n\touter constant offset from base address: ");
3304               dump_generic_expr (MSG_NOTE, TDF_SLIM,
3305                                  STMT_VINFO_DR_INIT (stmt_info));
3306               dump_printf (MSG_NOTE, "\n\touter step: ");
3307               dump_generic_expr (MSG_NOTE, TDF_SLIM,
3308                                  STMT_VINFO_DR_STEP (stmt_info));
3309               dump_printf (MSG_NOTE, "\n\touter aligned to: ");
3310               dump_generic_expr (MSG_NOTE, TDF_SLIM,
3311                                  STMT_VINFO_DR_ALIGNED_TO (stmt_info));
3312             }
3313         }
3314
3315       if (STMT_VINFO_DATA_REF (stmt_info))
3316         {
3317           if (dump_enabled_p ())
3318             {
3319               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3320                                "not vectorized: more than one data ref "
3321                                "in stmt: ");
3322               dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3323             }
3324
3325           if (bb_vinfo)
3326             {
3327               STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3328               stop_bb_analysis = true;
3329               continue;
3330             }
3331
3332           if (gather)
3333             free_data_ref (dr);
3334           return false;
3335         }
3336
3337       STMT_VINFO_DATA_REF (stmt_info) = dr;
3338
3339       /* Set vectype for STMT.  */
3340       scalar_type = TREE_TYPE (DR_REF (dr));
3341       STMT_VINFO_VECTYPE (stmt_info) =
3342                 get_vectype_for_scalar_type (scalar_type);
3343       if (!STMT_VINFO_VECTYPE (stmt_info))
3344         {
3345           if (dump_enabled_p ())
3346             {
3347               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
3348                                "not vectorized: no vectype for stmt: ");
3349               dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3350               dump_printf (MSG_MISSED_OPTIMIZATION, " scalar_type: ");
3351               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_DETAILS,
3352                                  scalar_type);
3353             }
3354
3355           if (bb_vinfo)
3356             {
3357               /* Mark the statement as not vectorizable.  */
3358               STMT_VINFO_VECTORIZABLE (stmt_info) = false;
3359               stop_bb_analysis = true;
3360               continue;
3361             }
3362
3363           if (gather)
3364             {
3365               STMT_VINFO_DATA_REF (stmt_info) = NULL;
3366               free_data_ref (dr);
3367             }
3368           return false;
3369         }
3370
3371       /* Adjust the minimal vectorization factor according to the
3372          vector type.  */
3373       vf = TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info));
3374       if (vf > *min_vf)
3375         *min_vf = vf;
3376
3377       if (gather)
3378         {
3379           unsigned int j, k, n;
3380           struct data_reference *olddr
3381             = datarefs[i];
3382           vec<ddr_p> ddrs = LOOP_VINFO_DDRS (loop_vinfo);
3383           struct data_dependence_relation *ddr, *newddr;
3384           bool bad = false;
3385           tree off;
3386           vec<loop_p> nest = LOOP_VINFO_LOOP_NEST (loop_vinfo);
3387
3388           gather = 0 != vect_check_gather (stmt, loop_vinfo, NULL, &off, NULL);
3389           if (gather
3390               && get_vectype_for_scalar_type (TREE_TYPE (off)) == NULL_TREE)
3391             gather = false;
3392           if (!gather)
3393             {
3394               STMT_VINFO_DATA_REF (stmt_info) = NULL;
3395               free_data_ref (dr);
3396               if (dump_enabled_p ())
3397                 {
3398                   dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
3399                                    "not vectorized: not suitable for gather "
3400                                    "load ");
3401                   dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3402                 }
3403               return false;
3404             }
3405
3406           n = datarefs.length () - 1;
3407           for (j = 0, k = i - 1; j < i; j++)
3408             {
3409               ddr = ddrs[k];
3410               gcc_assert (DDR_B (ddr) == olddr);
3411               newddr = initialize_data_dependence_relation (DDR_A (ddr), dr,
3412                                                             nest);
3413               ddrs[k] = newddr;
3414               free_dependence_relation (ddr);
3415               if (!bad
3416                   && DR_IS_WRITE (DDR_A (newddr))
3417                   && DDR_ARE_DEPENDENT (newddr) != chrec_known)
3418                 bad = true;
3419               k += --n;
3420             }
3421
3422           k++;
3423           n = k + datarefs.length () - i - 1;
3424           for (; k < n; k++)
3425             {
3426               ddr = ddrs[k];
3427               gcc_assert (DDR_A (ddr) == olddr);
3428               newddr = initialize_data_dependence_relation (dr, DDR_B (ddr),
3429                                                             nest);
3430               ddrs[k] = newddr;
3431               free_dependence_relation (ddr);
3432               if (!bad
3433                   && DR_IS_WRITE (DDR_B (newddr))
3434                   && DDR_ARE_DEPENDENT (newddr) != chrec_known)
3435                 bad = true;
3436             }
3437
3438           k = ddrs.length ()
3439               - datarefs.length () + i;
3440           ddr = ddrs[k];
3441           gcc_assert (DDR_A (ddr) == olddr && DDR_B (ddr) == olddr);
3442           newddr = initialize_data_dependence_relation (dr, dr, nest);
3443           ddrs[k] = newddr;
3444           free_dependence_relation (ddr);
3445           datarefs[i] = dr;
3446
3447           if (bad)
3448             {
3449               if (dump_enabled_p ())
3450                 {
3451                   dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
3452                                    "not vectorized: data dependence conflict"
3453                                    " prevents gather load");
3454                   dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3455                 }
3456               return false;
3457             }
3458
3459           STMT_VINFO_GATHER_P (stmt_info) = true;
3460         }
3461       else if (loop_vinfo
3462                && TREE_CODE (DR_STEP (dr)) != INTEGER_CST)
3463         {
3464           bool strided_load = false;
3465           if (!nested_in_vect_loop_p (loop, stmt))
3466             strided_load = vect_check_strided_load (stmt, loop_vinfo);
3467           if (!strided_load)
3468             {
3469               if (dump_enabled_p ())
3470                 {
3471                   dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
3472                                    "not vectorized: not suitable for strided "
3473                                    "load ");
3474                   dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3475                 }
3476               return false;
3477             }
3478           STMT_VINFO_STRIDE_LOAD_P (stmt_info) = true;
3479         }
3480     }
3481
3482   return true;
3483 }
3484
3485
3486 /* Function vect_get_new_vect_var.
3487
3488    Returns a name for a new variable.  The current naming scheme appends the
3489    prefix "vect_" or "vect_p" (depending on the value of VAR_KIND) to
3490    the name of vectorizer generated variables, and appends that to NAME if
3491    provided.  */
3492
3493 tree
3494 vect_get_new_vect_var (tree type, enum vect_var_kind var_kind, const char *name)
3495 {
3496   const char *prefix;
3497   tree new_vect_var;
3498
3499   switch (var_kind)
3500   {
3501   case vect_simple_var:
3502     prefix = "vect_";
3503     break;
3504   case vect_scalar_var:
3505     prefix = "stmp_";
3506     break;
3507   case vect_pointer_var:
3508     prefix = "vect_p";
3509     break;
3510   default:
3511     gcc_unreachable ();
3512   }
3513
3514   if (name)
3515     {
3516       char* tmp = concat (prefix, name, NULL);
3517       new_vect_var = create_tmp_reg (type, tmp);
3518       free (tmp);
3519     }
3520   else
3521     new_vect_var = create_tmp_reg (type, prefix);
3522
3523   return new_vect_var;
3524 }
3525
3526
3527 /* Function vect_create_addr_base_for_vector_ref.
3528
3529    Create an expression that computes the address of the first memory location
3530    that will be accessed for a data reference.
3531
3532    Input:
3533    STMT: The statement containing the data reference.
3534    NEW_STMT_LIST: Must be initialized to NULL_TREE or a statement list.
3535    OFFSET: Optional. If supplied, it is be added to the initial address.
3536    LOOP:    Specify relative to which loop-nest should the address be computed.
3537             For example, when the dataref is in an inner-loop nested in an
3538             outer-loop that is now being vectorized, LOOP can be either the
3539             outer-loop, or the inner-loop.  The first memory location accessed
3540             by the following dataref ('in' points to short):
3541
3542                 for (i=0; i<N; i++)
3543                    for (j=0; j<M; j++)
3544                      s += in[i+j]
3545
3546             is as follows:
3547             if LOOP=i_loop:     &in             (relative to i_loop)
3548             if LOOP=j_loop:     &in+i*2B        (relative to j_loop)
3549
3550    Output:
3551    1. Return an SSA_NAME whose value is the address of the memory location of
3552       the first vector of the data reference.
3553    2. If new_stmt_list is not NULL_TREE after return then the caller must insert
3554       these statement(s) which define the returned SSA_NAME.
3555
3556    FORNOW: We are only handling array accesses with step 1.  */
3557
3558 tree
3559 vect_create_addr_base_for_vector_ref (gimple stmt,
3560                                       gimple_seq *new_stmt_list,
3561                                       tree offset,
3562                                       struct loop *loop)
3563 {
3564   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3565   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
3566   tree data_ref_base = unshare_expr (DR_BASE_ADDRESS (dr));
3567   const char *base_name;
3568   tree data_ref_base_var;
3569   tree vec_stmt;
3570   tree addr_base, addr_expr;
3571   tree dest;
3572   gimple_seq seq = NULL;
3573   tree base_offset = unshare_expr (DR_OFFSET (dr));
3574   tree init = unshare_expr (DR_INIT (dr));
3575   tree vect_ptr_type;
3576   tree step = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)));
3577   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3578   tree base;
3579
3580   if (loop_vinfo && loop && loop != (gimple_bb (stmt))->loop_father)
3581     {
3582       struct loop *outer_loop = LOOP_VINFO_LOOP (loop_vinfo);
3583
3584       gcc_assert (nested_in_vect_loop_p (outer_loop, stmt));
3585
3586       data_ref_base = unshare_expr (STMT_VINFO_DR_BASE_ADDRESS (stmt_info));
3587       base_offset = unshare_expr (STMT_VINFO_DR_OFFSET (stmt_info));
3588       init = unshare_expr (STMT_VINFO_DR_INIT (stmt_info));
3589     }
3590
3591   if (loop_vinfo)
3592     base_name = get_name (data_ref_base);
3593   else
3594     {
3595       base_offset = ssize_int (0);
3596       init = ssize_int (0);
3597       base_name = get_name (DR_REF (dr));
3598     }
3599
3600   data_ref_base_var = create_tmp_var (TREE_TYPE (data_ref_base), "batmp");
3601   data_ref_base = force_gimple_operand (data_ref_base, &seq, true,
3602                                         data_ref_base_var);
3603   gimple_seq_add_seq (new_stmt_list, seq);
3604
3605   /* Create base_offset */
3606   base_offset = size_binop (PLUS_EXPR,
3607                             fold_convert (sizetype, base_offset),
3608                             fold_convert (sizetype, init));
3609   dest = create_tmp_var (sizetype, "base_off");
3610   base_offset = force_gimple_operand (base_offset, &seq, true, dest);
3611   gimple_seq_add_seq (new_stmt_list, seq);
3612
3613   if (offset)
3614     {
3615       tree tmp = create_tmp_var (sizetype, "offset");
3616
3617       offset = fold_build2 (MULT_EXPR, sizetype,
3618                             fold_convert (sizetype, offset), step);
3619       base_offset = fold_build2 (PLUS_EXPR, sizetype,
3620                                  base_offset, offset);
3621       base_offset = force_gimple_operand (base_offset, &seq, false, tmp);
3622       gimple_seq_add_seq (new_stmt_list, seq);
3623     }
3624
3625   /* base + base_offset */
3626   if (loop_vinfo)
3627     addr_base = fold_build_pointer_plus (data_ref_base, base_offset);
3628   else
3629     {
3630       addr_base = build1 (ADDR_EXPR,
3631                           build_pointer_type (TREE_TYPE (DR_REF (dr))),
3632                           unshare_expr (DR_REF (dr)));
3633     }
3634
3635   vect_ptr_type = build_pointer_type (STMT_VINFO_VECTYPE (stmt_info));
3636   base = get_base_address (DR_REF (dr));
3637   if (base
3638       && TREE_CODE (base) == MEM_REF)
3639     vect_ptr_type
3640       = build_qualified_type (vect_ptr_type,
3641                               TYPE_QUALS (TREE_TYPE (TREE_OPERAND (base, 0))));
3642
3643   vec_stmt = fold_convert (vect_ptr_type, addr_base);
3644   addr_expr = vect_get_new_vect_var (vect_ptr_type, vect_pointer_var,
3645                                      base_name);
3646   vec_stmt = force_gimple_operand (vec_stmt, &seq, false, addr_expr);
3647   gimple_seq_add_seq (new_stmt_list, seq);
3648
3649   if (DR_PTR_INFO (dr)
3650       && TREE_CODE (vec_stmt) == SSA_NAME)
3651     {
3652       duplicate_ssa_name_ptr_info (vec_stmt, DR_PTR_INFO (dr));
3653       if (offset)
3654         mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (vec_stmt));
3655     }
3656
3657   if (dump_enabled_p ())
3658     {
3659       dump_printf_loc (MSG_NOTE, vect_location, "created ");
3660       dump_generic_expr (MSG_NOTE, TDF_SLIM, vec_stmt);
3661     }
3662
3663   return vec_stmt;
3664 }
3665
3666
3667 /* Function vect_create_data_ref_ptr.
3668
3669    Create a new pointer-to-AGGR_TYPE variable (ap), that points to the first
3670    location accessed in the loop by STMT, along with the def-use update
3671    chain to appropriately advance the pointer through the loop iterations.
3672    Also set aliasing information for the pointer.  This pointer is used by
3673    the callers to this function to create a memory reference expression for
3674    vector load/store access.
3675
3676    Input:
3677    1. STMT: a stmt that references memory. Expected to be of the form
3678          GIMPLE_ASSIGN <name, data-ref> or
3679          GIMPLE_ASSIGN <data-ref, name>.
3680    2. AGGR_TYPE: the type of the reference, which should be either a vector
3681         or an array.
3682    3. AT_LOOP: the loop where the vector memref is to be created.
3683    4. OFFSET (optional): an offset to be added to the initial address accessed
3684         by the data-ref in STMT.
3685    5. BSI: location where the new stmts are to be placed if there is no loop
3686    6. ONLY_INIT: indicate if ap is to be updated in the loop, or remain
3687         pointing to the initial address.
3688
3689    Output:
3690    1. Declare a new ptr to vector_type, and have it point to the base of the
3691       data reference (initial addressed accessed by the data reference).
3692       For example, for vector of type V8HI, the following code is generated:
3693
3694       v8hi *ap;
3695       ap = (v8hi *)initial_address;
3696
3697       if OFFSET is not supplied:
3698          initial_address = &a[init];
3699       if OFFSET is supplied:
3700          initial_address = &a[init + OFFSET];
3701
3702       Return the initial_address in INITIAL_ADDRESS.
3703
3704    2. If ONLY_INIT is true, just return the initial pointer.  Otherwise, also
3705       update the pointer in each iteration of the loop.
3706
3707       Return the increment stmt that updates the pointer in PTR_INCR.
3708
3709    3. Set INV_P to true if the access pattern of the data reference in the
3710       vectorized loop is invariant.  Set it to false otherwise.
3711
3712    4. Return the pointer.  */
3713
3714 tree
3715 vect_create_data_ref_ptr (gimple stmt, tree aggr_type, struct loop *at_loop,
3716                           tree offset, tree *initial_address,
3717                           gimple_stmt_iterator *gsi, gimple *ptr_incr,
3718                           bool only_init, bool *inv_p)
3719 {
3720   const char *base_name;
3721   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3722   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3723   struct loop *loop = NULL;
3724   bool nested_in_vect_loop = false;
3725   struct loop *containing_loop = NULL;
3726   tree aggr_ptr_type;
3727   tree aggr_ptr;
3728   tree new_temp;
3729   gimple vec_stmt;
3730   gimple_seq new_stmt_list = NULL;
3731   edge pe = NULL;
3732   basic_block new_bb;
3733   tree aggr_ptr_init;
3734   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
3735   tree aptr;
3736   gimple_stmt_iterator incr_gsi;
3737   bool insert_after;
3738   bool negative;
3739   tree indx_before_incr, indx_after_incr;
3740   gimple incr;
3741   tree step;
3742   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
3743   tree base;
3744
3745   gcc_assert (TREE_CODE (aggr_type) == ARRAY_TYPE
3746               || TREE_CODE (aggr_type) == VECTOR_TYPE);
3747
3748   if (loop_vinfo)
3749     {
3750       loop = LOOP_VINFO_LOOP (loop_vinfo);
3751       nested_in_vect_loop = nested_in_vect_loop_p (loop, stmt);
3752       containing_loop = (gimple_bb (stmt))->loop_father;
3753       pe = loop_preheader_edge (loop);
3754     }
3755   else
3756     {
3757       gcc_assert (bb_vinfo);
3758       only_init = true;
3759       *ptr_incr = NULL;
3760     }
3761
3762   /* Check the step (evolution) of the load in LOOP, and record
3763      whether it's invariant.  */
3764   if (nested_in_vect_loop)
3765     step = STMT_VINFO_DR_STEP (stmt_info);
3766   else
3767     step = DR_STEP (STMT_VINFO_DATA_REF (stmt_info));
3768
3769   if (tree_int_cst_compare (step, size_zero_node) == 0)
3770     *inv_p = true;
3771   else
3772     *inv_p = false;
3773   negative = tree_int_cst_compare (step, size_zero_node) < 0;
3774
3775   /* Create an expression for the first address accessed by this load
3776      in LOOP.  */
3777   base_name = get_name (DR_BASE_ADDRESS (dr));
3778
3779   if (dump_enabled_p ())
3780     {
3781       tree dr_base_type = TREE_TYPE (DR_BASE_OBJECT (dr));
3782       dump_printf_loc (MSG_NOTE, vect_location,
3783                        "create %s-pointer variable to type: ",
3784                        tree_code_name[(int) TREE_CODE (aggr_type)]);
3785       dump_generic_expr (MSG_NOTE, TDF_SLIM, aggr_type);
3786       if (TREE_CODE (dr_base_type) == ARRAY_TYPE)
3787         dump_printf (MSG_NOTE, "  vectorizing an array ref: ");
3788       else if (TREE_CODE (dr_base_type) == RECORD_TYPE)
3789         dump_printf (MSG_NOTE, "  vectorizing a record based array ref: ");
3790       else
3791         dump_printf (MSG_NOTE, "  vectorizing a pointer ref: ");
3792       dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_BASE_OBJECT (dr));
3793     }
3794
3795   /* (1) Create the new aggregate-pointer variable.  */
3796   aggr_ptr_type = build_pointer_type (aggr_type);
3797   base = get_base_address (DR_REF (dr));
3798   if (base
3799       && TREE_CODE (base) == MEM_REF)
3800     aggr_ptr_type
3801       = build_qualified_type (aggr_ptr_type,
3802                               TYPE_QUALS (TREE_TYPE (TREE_OPERAND (base, 0))));
3803   aggr_ptr = vect_get_new_vect_var (aggr_ptr_type, vect_pointer_var, base_name);
3804
3805   /* Vector and array types inherit the alias set of their component
3806      type by default so we need to use a ref-all pointer if the data
3807      reference does not conflict with the created aggregated data
3808      reference because it is not addressable.  */
3809   if (!alias_sets_conflict_p (get_deref_alias_set (aggr_ptr),
3810                               get_alias_set (DR_REF (dr))))
3811     {
3812       aggr_ptr_type
3813         = build_pointer_type_for_mode (aggr_type,
3814                                        TYPE_MODE (aggr_ptr_type), true);
3815       aggr_ptr = vect_get_new_vect_var (aggr_ptr_type, vect_pointer_var,
3816                                         base_name);
3817     }
3818
3819   /* Likewise for any of the data references in the stmt group.  */
3820   else if (STMT_VINFO_GROUP_SIZE (stmt_info) > 1)
3821     {
3822       gimple orig_stmt = STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info);
3823       do
3824         {
3825           tree lhs = gimple_assign_lhs (orig_stmt);
3826           if (!alias_sets_conflict_p (get_deref_alias_set (aggr_ptr),
3827                                       get_alias_set (lhs)))
3828             {
3829               aggr_ptr_type
3830                 = build_pointer_type_for_mode (aggr_type,
3831                                                TYPE_MODE (aggr_ptr_type), true);
3832               aggr_ptr
3833                 = vect_get_new_vect_var (aggr_ptr_type, vect_pointer_var,
3834                                          base_name);
3835               break;
3836             }
3837
3838           orig_stmt = STMT_VINFO_GROUP_NEXT_ELEMENT (vinfo_for_stmt (orig_stmt));
3839         }
3840       while (orig_stmt);
3841     }
3842
3843   /* Note: If the dataref is in an inner-loop nested in LOOP, and we are
3844      vectorizing LOOP (i.e., outer-loop vectorization), we need to create two
3845      def-use update cycles for the pointer: one relative to the outer-loop
3846      (LOOP), which is what steps (3) and (4) below do.  The other is relative
3847      to the inner-loop (which is the inner-most loop containing the dataref),
3848      and this is done be step (5) below.
3849
3850      When vectorizing inner-most loops, the vectorized loop (LOOP) is also the
3851      inner-most loop, and so steps (3),(4) work the same, and step (5) is
3852      redundant.  Steps (3),(4) create the following:
3853
3854         vp0 = &base_addr;
3855         LOOP:   vp1 = phi(vp0,vp2)
3856                 ...
3857                 ...
3858                 vp2 = vp1 + step
3859                 goto LOOP
3860
3861      If there is an inner-loop nested in loop, then step (5) will also be
3862      applied, and an additional update in the inner-loop will be created:
3863
3864         vp0 = &base_addr;
3865         LOOP:   vp1 = phi(vp0,vp2)
3866                 ...
3867         inner:     vp3 = phi(vp1,vp4)
3868                    vp4 = vp3 + inner_step
3869                    if () goto inner
3870                 ...
3871                 vp2 = vp1 + step
3872                 if () goto LOOP   */
3873
3874   /* (2) Calculate the initial address of the aggregate-pointer, and set
3875      the aggregate-pointer to point to it before the loop.  */
3876
3877   /* Create: (&(base[init_val+offset]) in the loop preheader.  */
3878
3879   new_temp = vect_create_addr_base_for_vector_ref (stmt, &new_stmt_list,
3880                                                    offset, loop);
3881   if (new_stmt_list)
3882     {
3883       if (pe)
3884         {
3885           new_bb = gsi_insert_seq_on_edge_immediate (pe, new_stmt_list);
3886           gcc_assert (!new_bb);
3887         }
3888       else
3889         gsi_insert_seq_before (gsi, new_stmt_list, GSI_SAME_STMT);
3890     }
3891
3892   *initial_address = new_temp;
3893
3894   /* Create: p = (aggr_type *) initial_base  */
3895   if (TREE_CODE (new_temp) != SSA_NAME
3896       || !useless_type_conversion_p (aggr_ptr_type, TREE_TYPE (new_temp)))
3897     {
3898       vec_stmt = gimple_build_assign (aggr_ptr,
3899                                       fold_convert (aggr_ptr_type, new_temp));
3900       aggr_ptr_init = make_ssa_name (aggr_ptr, vec_stmt);
3901       /* Copy the points-to information if it exists. */
3902       if (DR_PTR_INFO (dr))
3903         duplicate_ssa_name_ptr_info (aggr_ptr_init, DR_PTR_INFO (dr));
3904       gimple_assign_set_lhs (vec_stmt, aggr_ptr_init);
3905       if (pe)
3906         {
3907           new_bb = gsi_insert_on_edge_immediate (pe, vec_stmt);
3908           gcc_assert (!new_bb);
3909         }
3910       else
3911         gsi_insert_before (gsi, vec_stmt, GSI_SAME_STMT);
3912     }
3913   else
3914     aggr_ptr_init = new_temp;
3915
3916   /* (3) Handle the updating of the aggregate-pointer inside the loop.
3917      This is needed when ONLY_INIT is false, and also when AT_LOOP is the
3918      inner-loop nested in LOOP (during outer-loop vectorization).  */
3919
3920   /* No update in loop is required.  */
3921   if (only_init && (!loop_vinfo || at_loop == loop))
3922     aptr = aggr_ptr_init;
3923   else
3924     {
3925       /* The step of the aggregate pointer is the type size.  */
3926       tree step = TYPE_SIZE_UNIT (aggr_type);
3927       /* One exception to the above is when the scalar step of the load in
3928          LOOP is zero. In this case the step here is also zero.  */
3929       if (*inv_p)
3930         step = size_zero_node;
3931       else if (negative)
3932         step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
3933
3934       standard_iv_increment_position (loop, &incr_gsi, &insert_after);
3935
3936       create_iv (aggr_ptr_init,
3937                  fold_convert (aggr_ptr_type, step),
3938                  aggr_ptr, loop, &incr_gsi, insert_after,
3939                  &indx_before_incr, &indx_after_incr);
3940       incr = gsi_stmt (incr_gsi);
3941       set_vinfo_for_stmt (incr, new_stmt_vec_info (incr, loop_vinfo, NULL));
3942
3943       /* Copy the points-to information if it exists. */
3944       if (DR_PTR_INFO (dr))
3945         {
3946           duplicate_ssa_name_ptr_info (indx_before_incr, DR_PTR_INFO (dr));
3947           duplicate_ssa_name_ptr_info (indx_after_incr, DR_PTR_INFO (dr));
3948         }
3949       if (ptr_incr)
3950         *ptr_incr = incr;
3951
3952       aptr = indx_before_incr;
3953     }
3954
3955   if (!nested_in_vect_loop || only_init)
3956     return aptr;
3957
3958
3959   /* (4) Handle the updating of the aggregate-pointer inside the inner-loop
3960      nested in LOOP, if exists.  */
3961
3962   gcc_assert (nested_in_vect_loop);
3963   if (!only_init)
3964     {
3965       standard_iv_increment_position (containing_loop, &incr_gsi,
3966                                       &insert_after);
3967       create_iv (aptr, fold_convert (aggr_ptr_type, DR_STEP (dr)), aggr_ptr,
3968                  containing_loop, &incr_gsi, insert_after, &indx_before_incr,
3969                  &indx_after_incr);
3970       incr = gsi_stmt (incr_gsi);
3971       set_vinfo_for_stmt (incr, new_stmt_vec_info (incr, loop_vinfo, NULL));
3972
3973       /* Copy the points-to information if it exists. */
3974       if (DR_PTR_INFO (dr))
3975         {
3976           duplicate_ssa_name_ptr_info (indx_before_incr, DR_PTR_INFO (dr));
3977           duplicate_ssa_name_ptr_info (indx_after_incr, DR_PTR_INFO (dr));
3978         }
3979       if (ptr_incr)
3980         *ptr_incr = incr;
3981
3982       return indx_before_incr;
3983     }
3984   else
3985     gcc_unreachable ();
3986 }
3987
3988
3989 /* Function bump_vector_ptr
3990
3991    Increment a pointer (to a vector type) by vector-size. If requested,
3992    i.e. if PTR-INCR is given, then also connect the new increment stmt
3993    to the existing def-use update-chain of the pointer, by modifying
3994    the PTR_INCR as illustrated below:
3995
3996    The pointer def-use update-chain before this function:
3997                         DATAREF_PTR = phi (p_0, p_2)
3998                         ....
3999         PTR_INCR:       p_2 = DATAREF_PTR + step
4000
4001    The pointer def-use update-chain after this function:
4002                         DATAREF_PTR = phi (p_0, p_2)
4003                         ....
4004                         NEW_DATAREF_PTR = DATAREF_PTR + BUMP
4005                         ....
4006         PTR_INCR:       p_2 = NEW_DATAREF_PTR + step
4007
4008    Input:
4009    DATAREF_PTR - ssa_name of a pointer (to vector type) that is being updated
4010                  in the loop.
4011    PTR_INCR - optional. The stmt that updates the pointer in each iteration of
4012               the loop.  The increment amount across iterations is expected
4013               to be vector_size.
4014    BSI - location where the new update stmt is to be placed.
4015    STMT - the original scalar memory-access stmt that is being vectorized.
4016    BUMP - optional. The offset by which to bump the pointer. If not given,
4017           the offset is assumed to be vector_size.
4018
4019    Output: Return NEW_DATAREF_PTR as illustrated above.
4020
4021 */
4022
4023 tree
4024 bump_vector_ptr (tree dataref_ptr, gimple ptr_incr, gimple_stmt_iterator *gsi,
4025                  gimple stmt, tree bump)
4026 {
4027   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4028   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
4029   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
4030   tree update = TYPE_SIZE_UNIT (vectype);
4031   gimple incr_stmt;
4032   ssa_op_iter iter;
4033   use_operand_p use_p;
4034   tree new_dataref_ptr;
4035
4036   if (bump)
4037     update = bump;
4038
4039   new_dataref_ptr = copy_ssa_name (dataref_ptr, NULL);
4040   incr_stmt = gimple_build_assign_with_ops (POINTER_PLUS_EXPR, new_dataref_ptr,
4041                                             dataref_ptr, update);
4042   vect_finish_stmt_generation (stmt, incr_stmt, gsi);
4043
4044   /* Copy the points-to information if it exists. */
4045   if (DR_PTR_INFO (dr))
4046     {
4047       duplicate_ssa_name_ptr_info (new_dataref_ptr, DR_PTR_INFO (dr));
4048       mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (new_dataref_ptr));
4049     }
4050
4051   if (!ptr_incr)
4052     return new_dataref_ptr;
4053
4054   /* Update the vector-pointer's cross-iteration increment.  */
4055   FOR_EACH_SSA_USE_OPERAND (use_p, ptr_incr, iter, SSA_OP_USE)
4056     {
4057       tree use = USE_FROM_PTR (use_p);
4058
4059       if (use == dataref_ptr)
4060         SET_USE (use_p, new_dataref_ptr);
4061       else
4062         gcc_assert (tree_int_cst_compare (use, update) == 0);
4063     }
4064
4065   return new_dataref_ptr;
4066 }
4067
4068
4069 /* Function vect_create_destination_var.
4070
4071    Create a new temporary of type VECTYPE.  */
4072
4073 tree
4074 vect_create_destination_var (tree scalar_dest, tree vectype)
4075 {
4076   tree vec_dest;
4077   const char *new_name;
4078   tree type;
4079   enum vect_var_kind kind;
4080
4081   kind = vectype ? vect_simple_var : vect_scalar_var;
4082   type = vectype ? vectype : TREE_TYPE (scalar_dest);
4083
4084   gcc_assert (TREE_CODE (scalar_dest) == SSA_NAME);
4085
4086   new_name = get_name (scalar_dest);
4087   if (!new_name)
4088     new_name = "var_";
4089   vec_dest = vect_get_new_vect_var (type, kind, new_name);
4090
4091   return vec_dest;
4092 }
4093
4094 /* Function vect_grouped_store_supported.
4095
4096    Returns TRUE if interleave high and interleave low permutations
4097    are supported, and FALSE otherwise.  */
4098
4099 bool
4100 vect_grouped_store_supported (tree vectype, unsigned HOST_WIDE_INT count)
4101 {
4102   enum machine_mode mode = TYPE_MODE (vectype);
4103
4104   /* vect_permute_store_chain requires the group size to be a power of two.  */
4105   if (exact_log2 (count) == -1)
4106     {
4107       if (dump_enabled_p ())
4108         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
4109                          "the size of the group of accesses"
4110                          " is not a power of 2");
4111       return false;
4112     }
4113
4114   /* Check that the permutation is supported.  */
4115   if (VECTOR_MODE_P (mode))
4116     {
4117       unsigned int i, nelt = GET_MODE_NUNITS (mode);
4118       unsigned char *sel = XALLOCAVEC (unsigned char, nelt);
4119       for (i = 0; i < nelt / 2; i++)
4120         {
4121           sel[i * 2] = i;
4122           sel[i * 2 + 1] = i + nelt;
4123         }
4124       if (can_vec_perm_p (mode, false, sel))
4125         {
4126           for (i = 0; i < nelt; i++)
4127             sel[i] += nelt / 2;
4128           if (can_vec_perm_p (mode, false, sel))
4129             return true;
4130         }
4131     }
4132
4133   if (dump_enabled_p ())
4134     dump_printf (MSG_MISSED_OPTIMIZATION,
4135                  "interleave op not supported by target.");
4136   return false;
4137 }
4138
4139
4140 /* Return TRUE if vec_store_lanes is available for COUNT vectors of
4141    type VECTYPE.  */
4142
4143 bool
4144 vect_store_lanes_supported (tree vectype, unsigned HOST_WIDE_INT count)
4145 {
4146   return vect_lanes_optab_supported_p ("vec_store_lanes",
4147                                        vec_store_lanes_optab,
4148                                        vectype, count);
4149 }
4150
4151
4152 /* Function vect_permute_store_chain.
4153
4154    Given a chain of interleaved stores in DR_CHAIN of LENGTH that must be
4155    a power of 2, generate interleave_high/low stmts to reorder the data
4156    correctly for the stores.  Return the final references for stores in
4157    RESULT_CHAIN.
4158
4159    E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
4160    The input is 4 vectors each containing 8 elements.  We assign a number to
4161    each element, the input sequence is:
4162
4163    1st vec:   0  1  2  3  4  5  6  7
4164    2nd vec:   8  9 10 11 12 13 14 15
4165    3rd vec:  16 17 18 19 20 21 22 23
4166    4th vec:  24 25 26 27 28 29 30 31
4167
4168    The output sequence should be:
4169
4170    1st vec:  0  8 16 24  1  9 17 25
4171    2nd vec:  2 10 18 26  3 11 19 27
4172    3rd vec:  4 12 20 28  5 13 21 30
4173    4th vec:  6 14 22 30  7 15 23 31
4174
4175    i.e., we interleave the contents of the four vectors in their order.
4176
4177    We use interleave_high/low instructions to create such output.  The input of
4178    each interleave_high/low operation is two vectors:
4179    1st vec    2nd vec
4180    0 1 2 3    4 5 6 7
4181    the even elements of the result vector are obtained left-to-right from the
4182    high/low elements of the first vector.  The odd elements of the result are
4183    obtained left-to-right from the high/low elements of the second vector.
4184    The output of interleave_high will be:   0 4 1 5
4185    and of interleave_low:                   2 6 3 7
4186
4187
4188    The permutation is done in log LENGTH stages.  In each stage interleave_high
4189    and interleave_low stmts are created for each pair of vectors in DR_CHAIN,
4190    where the first argument is taken from the first half of DR_CHAIN and the
4191    second argument from it's second half.
4192    In our example,
4193
4194    I1: interleave_high (1st vec, 3rd vec)
4195    I2: interleave_low (1st vec, 3rd vec)
4196    I3: interleave_high (2nd vec, 4th vec)
4197    I4: interleave_low (2nd vec, 4th vec)
4198
4199    The output for the first stage is:
4200
4201    I1:  0 16  1 17  2 18  3 19
4202    I2:  4 20  5 21  6 22  7 23
4203    I3:  8 24  9 25 10 26 11 27
4204    I4: 12 28 13 29 14 30 15 31
4205
4206    The output of the second stage, i.e. the final result is:
4207
4208    I1:  0  8 16 24  1  9 17 25
4209    I2:  2 10 18 26  3 11 19 27
4210    I3:  4 12 20 28  5 13 21 30
4211    I4:  6 14 22 30  7 15 23 31.  */
4212
4213 void
4214 vect_permute_store_chain (vec<tree> dr_chain,
4215                           unsigned int length,
4216                           gimple stmt,
4217                           gimple_stmt_iterator *gsi,
4218                           vec<tree> *result_chain)
4219 {
4220   tree vect1, vect2, high, low;
4221   gimple perm_stmt;
4222   tree vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
4223   tree perm_mask_low, perm_mask_high;
4224   unsigned int i, n;
4225   unsigned int j, nelt = TYPE_VECTOR_SUBPARTS (vectype);
4226   unsigned char *sel = XALLOCAVEC (unsigned char, nelt);
4227
4228   result_chain->quick_grow (length);
4229   memcpy (result_chain->address (), dr_chain.address (),
4230           length * sizeof (tree));
4231
4232   for (i = 0, n = nelt / 2; i < n; i++)
4233     {
4234       sel[i * 2] = i;
4235       sel[i * 2 + 1] = i + nelt;
4236     }
4237   perm_mask_high = vect_gen_perm_mask (vectype, sel);
4238   gcc_assert (perm_mask_high != NULL);
4239
4240   for (i = 0; i < nelt; i++)
4241     sel[i] += nelt / 2;
4242   perm_mask_low = vect_gen_perm_mask (vectype, sel);
4243   gcc_assert (perm_mask_low != NULL);
4244
4245   for (i = 0, n = exact_log2 (length); i < n; i++)
4246     {
4247       for (j = 0; j < length/2; j++)
4248         {
4249           vect1 = dr_chain[j];
4250           vect2 = dr_chain[j+length/2];
4251
4252           /* Create interleaving stmt:
4253              high = VEC_PERM_EXPR <vect1, vect2, {0, nelt, 1, nelt+1, ...}>  */
4254           high = make_temp_ssa_name (vectype, NULL, "vect_inter_high");
4255           perm_stmt
4256             = gimple_build_assign_with_ops (VEC_PERM_EXPR, high,
4257                                             vect1, vect2, perm_mask_high);
4258           vect_finish_stmt_generation (stmt, perm_stmt, gsi);
4259           (*result_chain)[2*j] = high;
4260
4261           /* Create interleaving stmt:
4262              low = VEC_PERM_EXPR <vect1, vect2, {nelt/2, nelt*3/2, nelt/2+1,
4263                                                  nelt*3/2+1, ...}>  */
4264           low = make_temp_ssa_name (vectype, NULL, "vect_inter_low");
4265           perm_stmt
4266             = gimple_build_assign_with_ops (VEC_PERM_EXPR, low,
4267                                             vect1, vect2, perm_mask_low);
4268           vect_finish_stmt_generation (stmt, perm_stmt, gsi);
4269           (*result_chain)[2*j+1] = low;
4270         }
4271       memcpy (dr_chain.address (), result_chain->address (),
4272               length * sizeof (tree));
4273     }
4274 }
4275
4276 /* Function vect_setup_realignment
4277
4278    This function is called when vectorizing an unaligned load using
4279    the dr_explicit_realign[_optimized] scheme.
4280    This function generates the following code at the loop prolog:
4281
4282       p = initial_addr;
4283    x  msq_init = *(floor(p));   # prolog load
4284       realignment_token = call target_builtin;
4285     loop:
4286    x  msq = phi (msq_init, ---)
4287
4288    The stmts marked with x are generated only for the case of
4289    dr_explicit_realign_optimized.
4290
4291    The code above sets up a new (vector) pointer, pointing to the first
4292    location accessed by STMT, and a "floor-aligned" load using that pointer.
4293    It also generates code to compute the "realignment-token" (if the relevant
4294    target hook was defined), and creates a phi-node at the loop-header bb
4295    whose arguments are the result of the prolog-load (created by this
4296    function) and the result of a load that takes place in the loop (to be
4297    created by the caller to this function).
4298
4299    For the case of dr_explicit_realign_optimized:
4300    The caller to this function uses the phi-result (msq) to create the
4301    realignment code inside the loop, and sets up the missing phi argument,
4302    as follows:
4303     loop:
4304       msq = phi (msq_init, lsq)
4305       lsq = *(floor(p'));        # load in loop
4306       result = realign_load (msq, lsq, realignment_token);
4307
4308    For the case of dr_explicit_realign:
4309     loop:
4310       msq = *(floor(p));        # load in loop
4311       p' = p + (VS-1);
4312       lsq = *(floor(p'));       # load in loop
4313       result = realign_load (msq, lsq, realignment_token);
4314
4315    Input:
4316    STMT - (scalar) load stmt to be vectorized. This load accesses
4317           a memory location that may be unaligned.
4318    BSI - place where new code is to be inserted.
4319    ALIGNMENT_SUPPORT_SCHEME - which of the two misalignment handling schemes
4320                               is used.
4321
4322    Output:
4323    REALIGNMENT_TOKEN - the result of a call to the builtin_mask_for_load
4324                        target hook, if defined.
4325    Return value - the result of the loop-header phi node.  */
4326
4327 tree
4328 vect_setup_realignment (gimple stmt, gimple_stmt_iterator *gsi,
4329                         tree *realignment_token,
4330                         enum dr_alignment_support alignment_support_scheme,
4331                         tree init_addr,
4332                         struct loop **at_loop)
4333 {
4334   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4335   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
4336   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
4337   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
4338   struct loop *loop = NULL;
4339   edge pe = NULL;
4340   tree scalar_dest = gimple_assign_lhs (stmt);
4341   tree vec_dest;
4342   gimple inc;
4343   tree ptr;
4344   tree data_ref;
4345   gimple new_stmt;
4346   basic_block new_bb;
4347   tree msq_init = NULL_TREE;
4348   tree new_temp;
4349   gimple phi_stmt;
4350   tree msq = NULL_TREE;
4351   gimple_seq stmts = NULL;
4352   bool inv_p;
4353   bool compute_in_loop = false;
4354   bool nested_in_vect_loop = false;
4355   struct loop *containing_loop = (gimple_bb (stmt))->loop_father;
4356   struct loop *loop_for_initial_load = NULL;
4357
4358   if (loop_vinfo)
4359     {
4360       loop = LOOP_VINFO_LOOP (loop_vinfo);
4361       nested_in_vect_loop = nested_in_vect_loop_p (loop, stmt);
4362     }
4363
4364   gcc_assert (alignment_support_scheme == dr_explicit_realign
4365               || alignment_support_scheme == dr_explicit_realign_optimized);
4366
4367   /* We need to generate three things:
4368      1. the misalignment computation
4369      2. the extra vector load (for the optimized realignment scheme).
4370      3. the phi node for the two vectors from which the realignment is
4371       done (for the optimized realignment scheme).  */
4372
4373   /* 1. Determine where to generate the misalignment computation.
4374
4375      If INIT_ADDR is NULL_TREE, this indicates that the misalignment
4376      calculation will be generated by this function, outside the loop (in the
4377      preheader).  Otherwise, INIT_ADDR had already been computed for us by the
4378      caller, inside the loop.
4379
4380      Background: If the misalignment remains fixed throughout the iterations of
4381      the loop, then both realignment schemes are applicable, and also the
4382      misalignment computation can be done outside LOOP.  This is because we are
4383      vectorizing LOOP, and so the memory accesses in LOOP advance in steps that
4384      are a multiple of VS (the Vector Size), and therefore the misalignment in
4385      different vectorized LOOP iterations is always the same.
4386      The problem arises only if the memory access is in an inner-loop nested
4387      inside LOOP, which is now being vectorized using outer-loop vectorization.
4388      This is the only case when the misalignment of the memory access may not
4389      remain fixed throughout the iterations of the inner-loop (as explained in
4390      detail in vect_supportable_dr_alignment).  In this case, not only is the
4391      optimized realignment scheme not applicable, but also the misalignment
4392      computation (and generation of the realignment token that is passed to
4393      REALIGN_LOAD) have to be done inside the loop.
4394
4395      In short, INIT_ADDR indicates whether we are in a COMPUTE_IN_LOOP mode
4396      or not, which in turn determines if the misalignment is computed inside
4397      the inner-loop, or outside LOOP.  */
4398
4399   if (init_addr != NULL_TREE || !loop_vinfo)
4400     {
4401       compute_in_loop = true;
4402       gcc_assert (alignment_support_scheme == dr_explicit_realign);
4403     }
4404
4405
4406   /* 2. Determine where to generate the extra vector load.
4407
4408      For the optimized realignment scheme, instead of generating two vector
4409      loads in each iteration, we generate a single extra vector load in the
4410      preheader of the loop, and in each iteration reuse the result of the
4411      vector load from the previous iteration.  In case the memory access is in
4412      an inner-loop nested inside LOOP, which is now being vectorized using
4413      outer-loop vectorization, we need to determine whether this initial vector
4414      load should be generated at the preheader of the inner-loop, or can be
4415      generated at the preheader of LOOP.  If the memory access has no evolution
4416      in LOOP, it can be generated in the preheader of LOOP. Otherwise, it has
4417      to be generated inside LOOP (in the preheader of the inner-loop).  */
4418
4419   if (nested_in_vect_loop)
4420     {
4421       tree outerloop_step = STMT_VINFO_DR_STEP (stmt_info);
4422       bool invariant_in_outerloop =
4423             (tree_int_cst_compare (outerloop_step, size_zero_node) == 0);
4424       loop_for_initial_load = (invariant_in_outerloop ? loop : loop->inner);
4425     }
4426   else
4427     loop_for_initial_load = loop;
4428   if (at_loop)
4429     *at_loop = loop_for_initial_load;
4430
4431   if (loop_for_initial_load)
4432     pe = loop_preheader_edge (loop_for_initial_load);
4433
4434   /* 3. For the case of the optimized realignment, create the first vector
4435       load at the loop preheader.  */
4436
4437   if (alignment_support_scheme == dr_explicit_realign_optimized)
4438     {
4439       /* Create msq_init = *(floor(p1)) in the loop preheader  */
4440
4441       gcc_assert (!compute_in_loop);
4442       vec_dest = vect_create_destination_var (scalar_dest, vectype);
4443       ptr = vect_create_data_ref_ptr (stmt, vectype, loop_for_initial_load,
4444                                       NULL_TREE, &init_addr, NULL, &inc,
4445                                       true, &inv_p);
4446       new_temp = copy_ssa_name (ptr, NULL);
4447       new_stmt = gimple_build_assign_with_ops
4448                    (BIT_AND_EXPR, new_temp, ptr,
4449                     build_int_cst (TREE_TYPE (ptr),
4450                                    -(HOST_WIDE_INT)TYPE_ALIGN_UNIT (vectype)));
4451       new_bb = gsi_insert_on_edge_immediate (pe, new_stmt);
4452       gcc_assert (!new_bb);
4453       data_ref
4454         = build2 (MEM_REF, TREE_TYPE (vec_dest), new_temp,
4455                   build_int_cst (reference_alias_ptr_type (DR_REF (dr)), 0));
4456       new_stmt = gimple_build_assign (vec_dest, data_ref);
4457       new_temp = make_ssa_name (vec_dest, new_stmt);
4458       gimple_assign_set_lhs (new_stmt, new_temp);
4459       if (pe)
4460         {
4461           new_bb = gsi_insert_on_edge_immediate (pe, new_stmt);
4462           gcc_assert (!new_bb);
4463         }
4464       else
4465          gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
4466
4467       msq_init = gimple_assign_lhs (new_stmt);
4468     }
4469
4470   /* 4. Create realignment token using a target builtin, if available.
4471       It is done either inside the containing loop, or before LOOP (as
4472       determined above).  */
4473
4474   if (targetm.vectorize.builtin_mask_for_load)
4475     {
4476       tree builtin_decl;
4477
4478       /* Compute INIT_ADDR - the initial addressed accessed by this memref.  */
4479       if (!init_addr)
4480         {
4481           /* Generate the INIT_ADDR computation outside LOOP.  */
4482           init_addr = vect_create_addr_base_for_vector_ref (stmt, &stmts,
4483                                                         NULL_TREE, loop);
4484           if (loop)
4485             {
4486               pe = loop_preheader_edge (loop);
4487               new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
4488               gcc_assert (!new_bb);
4489             }
4490           else
4491              gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
4492         }
4493
4494       builtin_decl = targetm.vectorize.builtin_mask_for_load ();
4495       new_stmt = gimple_build_call (builtin_decl, 1, init_addr);
4496       vec_dest =
4497         vect_create_destination_var (scalar_dest,
4498                                      gimple_call_return_type (new_stmt));
4499       new_temp = make_ssa_name (vec_dest, new_stmt);
4500       gimple_call_set_lhs (new_stmt, new_temp);
4501
4502       if (compute_in_loop)
4503         gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
4504       else
4505         {
4506           /* Generate the misalignment computation outside LOOP.  */
4507           pe = loop_preheader_edge (loop);
4508           new_bb = gsi_insert_on_edge_immediate (pe, new_stmt);
4509           gcc_assert (!new_bb);
4510         }
4511
4512       *realignment_token = gimple_call_lhs (new_stmt);
4513
4514       /* The result of the CALL_EXPR to this builtin is determined from
4515          the value of the parameter and no global variables are touched
4516          which makes the builtin a "const" function.  Requiring the
4517          builtin to have the "const" attribute makes it unnecessary
4518          to call mark_call_clobbered.  */
4519       gcc_assert (TREE_READONLY (builtin_decl));
4520     }
4521
4522   if (alignment_support_scheme == dr_explicit_realign)
4523     return msq;
4524
4525   gcc_assert (!compute_in_loop);
4526   gcc_assert (alignment_support_scheme == dr_explicit_realign_optimized);
4527
4528
4529   /* 5. Create msq = phi <msq_init, lsq> in loop  */
4530
4531   pe = loop_preheader_edge (containing_loop);
4532   vec_dest = vect_create_destination_var (scalar_dest, vectype);
4533   msq = make_ssa_name (vec_dest, NULL);
4534   phi_stmt = create_phi_node (msq, containing_loop->header);
4535   add_phi_arg (phi_stmt, msq_init, pe, UNKNOWN_LOCATION);
4536
4537   return msq;
4538 }
4539
4540
4541 /* Function vect_grouped_load_supported.
4542
4543    Returns TRUE if even and odd permutations are supported,
4544    and FALSE otherwise.  */
4545
4546 bool
4547 vect_grouped_load_supported (tree vectype, unsigned HOST_WIDE_INT count)
4548 {
4549   enum machine_mode mode = TYPE_MODE (vectype);
4550
4551   /* vect_permute_load_chain requires the group size to be a power of two.  */
4552   if (exact_log2 (count) == -1)
4553     {
4554       if (dump_enabled_p ())
4555         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
4556                          "the size of the group of accesses"
4557                          " is not a power of 2");
4558       return false;
4559     }
4560
4561   /* Check that the permutation is supported.  */
4562   if (VECTOR_MODE_P (mode))
4563     {
4564       unsigned int i, nelt = GET_MODE_NUNITS (mode);
4565       unsigned char *sel = XALLOCAVEC (unsigned char, nelt);
4566
4567       for (i = 0; i < nelt; i++)
4568         sel[i] = i * 2;
4569       if (can_vec_perm_p (mode, false, sel))
4570         {
4571           for (i = 0; i < nelt; i++)
4572             sel[i] = i * 2 + 1;
4573           if (can_vec_perm_p (mode, false, sel))
4574             return true;
4575         }
4576     }
4577
4578   if (dump_enabled_p ())
4579     dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
4580                      "extract even/odd not supported by target");
4581   return false;
4582 }
4583
4584 /* Return TRUE if vec_load_lanes is available for COUNT vectors of
4585    type VECTYPE.  */
4586
4587 bool
4588 vect_load_lanes_supported (tree vectype, unsigned HOST_WIDE_INT count)
4589 {
4590   return vect_lanes_optab_supported_p ("vec_load_lanes",
4591                                        vec_load_lanes_optab,
4592                                        vectype, count);
4593 }
4594
4595 /* Function vect_permute_load_chain.
4596
4597    Given a chain of interleaved loads in DR_CHAIN of LENGTH that must be
4598    a power of 2, generate extract_even/odd stmts to reorder the input data
4599    correctly.  Return the final references for loads in RESULT_CHAIN.
4600
4601    E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
4602    The input is 4 vectors each containing 8 elements. We assign a number to each
4603    element, the input sequence is:
4604
4605    1st vec:   0  1  2  3  4  5  6  7
4606    2nd vec:   8  9 10 11 12 13 14 15
4607    3rd vec:  16 17 18 19 20 21 22 23
4608    4th vec:  24 25 26 27 28 29 30 31
4609
4610    The output sequence should be:
4611
4612    1st vec:  0 4  8 12 16 20 24 28
4613    2nd vec:  1 5  9 13 17 21 25 29
4614    3rd vec:  2 6 10 14 18 22 26 30
4615    4th vec:  3 7 11 15 19 23 27 31
4616
4617    i.e., the first output vector should contain the first elements of each
4618    interleaving group, etc.
4619
4620    We use extract_even/odd instructions to create such output.  The input of
4621    each extract_even/odd operation is two vectors
4622    1st vec    2nd vec
4623    0 1 2 3    4 5 6 7
4624
4625    and the output is the vector of extracted even/odd elements.  The output of
4626    extract_even will be:   0 2 4 6
4627    and of extract_odd:     1 3 5 7
4628
4629
4630    The permutation is done in log LENGTH stages.  In each stage extract_even
4631    and extract_odd stmts are created for each pair of vectors in DR_CHAIN in
4632    their order.  In our example,
4633
4634    E1: extract_even (1st vec, 2nd vec)
4635    E2: extract_odd (1st vec, 2nd vec)
4636    E3: extract_even (3rd vec, 4th vec)
4637    E4: extract_odd (3rd vec, 4th vec)
4638
4639    The output for the first stage will be:
4640
4641    E1:  0  2  4  6  8 10 12 14
4642    E2:  1  3  5  7  9 11 13 15
4643    E3: 16 18 20 22 24 26 28 30
4644    E4: 17 19 21 23 25 27 29 31
4645
4646    In order to proceed and create the correct sequence for the next stage (or
4647    for the correct output, if the second stage is the last one, as in our
4648    example), we first put the output of extract_even operation and then the
4649    output of extract_odd in RESULT_CHAIN (which is then copied to DR_CHAIN).
4650    The input for the second stage is:
4651
4652    1st vec (E1):  0  2  4  6  8 10 12 14
4653    2nd vec (E3): 16 18 20 22 24 26 28 30
4654    3rd vec (E2):  1  3  5  7  9 11 13 15
4655    4th vec (E4): 17 19 21 23 25 27 29 31
4656
4657    The output of the second stage:
4658
4659    E1: 0 4  8 12 16 20 24 28
4660    E2: 2 6 10 14 18 22 26 30
4661    E3: 1 5  9 13 17 21 25 29
4662    E4: 3 7 11 15 19 23 27 31
4663
4664    And RESULT_CHAIN after reordering:
4665
4666    1st vec (E1):  0 4  8 12 16 20 24 28
4667    2nd vec (E3):  1 5  9 13 17 21 25 29
4668    3rd vec (E2):  2 6 10 14 18 22 26 30
4669    4th vec (E4):  3 7 11 15 19 23 27 31.  */
4670
4671 static void
4672 vect_permute_load_chain (vec<tree> dr_chain,
4673                          unsigned int length,
4674                          gimple stmt,
4675                          gimple_stmt_iterator *gsi,
4676                          vec<tree> *result_chain)
4677 {
4678   tree data_ref, first_vect, second_vect;
4679   tree perm_mask_even, perm_mask_odd;
4680   gimple perm_stmt;
4681   tree vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
4682   unsigned int i, j, log_length = exact_log2 (length);
4683   unsigned nelt = TYPE_VECTOR_SUBPARTS (vectype);
4684   unsigned char *sel = XALLOCAVEC (unsigned char, nelt);
4685
4686   result_chain->quick_grow (length);
4687   memcpy (result_chain->address (), dr_chain.address (),
4688           length * sizeof (tree));
4689
4690   for (i = 0; i < nelt; ++i)
4691     sel[i] = i * 2;
4692   perm_mask_even = vect_gen_perm_mask (vectype, sel);
4693   gcc_assert (perm_mask_even != NULL);
4694
4695   for (i = 0; i < nelt; ++i)
4696     sel[i] = i * 2 + 1;
4697   perm_mask_odd = vect_gen_perm_mask (vectype, sel);
4698   gcc_assert (perm_mask_odd != NULL);
4699
4700   for (i = 0; i < log_length; i++)
4701     {
4702       for (j = 0; j < length; j += 2)
4703         {
4704           first_vect = dr_chain[j];
4705           second_vect = dr_chain[j+1];
4706
4707           /* data_ref = permute_even (first_data_ref, second_data_ref);  */
4708           data_ref = make_temp_ssa_name (vectype, NULL, "vect_perm_even");
4709           perm_stmt = gimple_build_assign_with_ops (VEC_PERM_EXPR, data_ref,
4710                                                     first_vect, second_vect,
4711                                                     perm_mask_even);
4712           vect_finish_stmt_generation (stmt, perm_stmt, gsi);
4713           (*result_chain)[j/2] = data_ref;
4714
4715           /* data_ref = permute_odd (first_data_ref, second_data_ref);  */
4716           data_ref = make_temp_ssa_name (vectype, NULL, "vect_perm_odd");
4717           perm_stmt = gimple_build_assign_with_ops (VEC_PERM_EXPR, data_ref,
4718                                                     first_vect, second_vect,
4719                                                     perm_mask_odd);
4720           vect_finish_stmt_generation (stmt, perm_stmt, gsi);
4721           (*result_chain)[j/2+length/2] = data_ref;
4722         }
4723       memcpy (dr_chain.address (), result_chain->address (),
4724               length * sizeof (tree));
4725     }
4726 }
4727
4728
4729 /* Function vect_transform_grouped_load.
4730
4731    Given a chain of input interleaved data-refs (in DR_CHAIN), build statements
4732    to perform their permutation and ascribe the result vectorized statements to
4733    the scalar statements.
4734 */
4735
4736 void
4737 vect_transform_grouped_load (gimple stmt, vec<tree> dr_chain, int size,
4738                              gimple_stmt_iterator *gsi)
4739 {
4740   vec<tree> result_chain = vNULL;
4741
4742   /* DR_CHAIN contains input data-refs that are a part of the interleaving.
4743      RESULT_CHAIN is the output of vect_permute_load_chain, it contains permuted
4744      vectors, that are ready for vector computation.  */
4745   result_chain.create (size);
4746   vect_permute_load_chain (dr_chain, size, stmt, gsi, &result_chain);
4747   vect_record_grouped_load_vectors (stmt, result_chain);
4748   result_chain.release ();
4749 }
4750
4751 /* RESULT_CHAIN contains the output of a group of grouped loads that were
4752    generated as part of the vectorization of STMT.  Assign the statement
4753    for each vector to the associated scalar statement.  */
4754
4755 void
4756 vect_record_grouped_load_vectors (gimple stmt, vec<tree> result_chain)
4757 {
4758   gimple first_stmt = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt));
4759   gimple next_stmt, new_stmt;
4760   unsigned int i, gap_count;
4761   tree tmp_data_ref;
4762
4763   /* Put a permuted data-ref in the VECTORIZED_STMT field.
4764      Since we scan the chain starting from it's first node, their order
4765      corresponds the order of data-refs in RESULT_CHAIN.  */
4766   next_stmt = first_stmt;
4767   gap_count = 1;
4768   FOR_EACH_VEC_ELT (result_chain, i, tmp_data_ref)
4769     {
4770       if (!next_stmt)
4771         break;
4772
4773       /* Skip the gaps.  Loads created for the gaps will be removed by dead
4774        code elimination pass later.  No need to check for the first stmt in
4775        the group, since it always exists.
4776        GROUP_GAP is the number of steps in elements from the previous
4777        access (if there is no gap GROUP_GAP is 1).  We skip loads that
4778        correspond to the gaps.  */
4779       if (next_stmt != first_stmt
4780           && gap_count < GROUP_GAP (vinfo_for_stmt (next_stmt)))
4781       {
4782         gap_count++;
4783         continue;
4784       }
4785
4786       while (next_stmt)
4787         {
4788           new_stmt = SSA_NAME_DEF_STMT (tmp_data_ref);
4789           /* We assume that if VEC_STMT is not NULL, this is a case of multiple
4790              copies, and we put the new vector statement in the first available
4791              RELATED_STMT.  */
4792           if (!STMT_VINFO_VEC_STMT (vinfo_for_stmt (next_stmt)))
4793             STMT_VINFO_VEC_STMT (vinfo_for_stmt (next_stmt)) = new_stmt;
4794           else
4795             {
4796               if (!GROUP_SAME_DR_STMT (vinfo_for_stmt (next_stmt)))
4797                 {
4798                   gimple prev_stmt =
4799                     STMT_VINFO_VEC_STMT (vinfo_for_stmt (next_stmt));
4800                   gimple rel_stmt =
4801                     STMT_VINFO_RELATED_STMT (vinfo_for_stmt (prev_stmt));
4802                   while (rel_stmt)
4803                     {
4804                       prev_stmt = rel_stmt;
4805                       rel_stmt =
4806                         STMT_VINFO_RELATED_STMT (vinfo_for_stmt (rel_stmt));
4807                     }
4808
4809                   STMT_VINFO_RELATED_STMT (vinfo_for_stmt (prev_stmt)) =
4810                     new_stmt;
4811                 }
4812             }
4813
4814           next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
4815           gap_count = 1;
4816           /* If NEXT_STMT accesses the same DR as the previous statement,
4817              put the same TMP_DATA_REF as its vectorized statement; otherwise
4818              get the next data-ref from RESULT_CHAIN.  */
4819           if (!next_stmt || !GROUP_SAME_DR_STMT (vinfo_for_stmt (next_stmt)))
4820             break;
4821         }
4822     }
4823 }
4824
4825 /* Function vect_force_dr_alignment_p.
4826
4827    Returns whether the alignment of a DECL can be forced to be aligned
4828    on ALIGNMENT bit boundary.  */
4829
4830 bool
4831 vect_can_force_dr_alignment_p (const_tree decl, unsigned int alignment)
4832 {
4833   if (TREE_CODE (decl) != VAR_DECL)
4834     return false;
4835
4836   /* We cannot change alignment of common or external symbols as another
4837      translation unit may contain a definition with lower alignment.  
4838      The rules of common symbol linking mean that the definition
4839      will override the common symbol.  The same is true for constant
4840      pool entries which may be shared and are not properly merged
4841      by LTO.  */
4842   if (DECL_EXTERNAL (decl)
4843       || DECL_COMMON (decl)
4844       || DECL_IN_CONSTANT_POOL (decl))
4845     return false;
4846
4847   if (TREE_ASM_WRITTEN (decl))
4848     return false;
4849
4850   /* Do not override the alignment as specified by the ABI when the used
4851      attribute is set.  */
4852   if (DECL_PRESERVE_P (decl))
4853     return false;
4854
4855   /* Do not override explicit alignment set by the user when an explicit
4856      section name is also used.  This is a common idiom used by many
4857      software projects.  */
4858   if (DECL_SECTION_NAME (decl) != NULL_TREE
4859       && !DECL_HAS_IMPLICIT_SECTION_NAME_P (decl))
4860     return false;
4861
4862   if (TREE_STATIC (decl))
4863     return (alignment <= MAX_OFILE_ALIGNMENT);
4864   else
4865     return (alignment <= MAX_STACK_ALIGNMENT);
4866 }
4867
4868
4869 /* Return whether the data reference DR is supported with respect to its
4870    alignment.
4871    If CHECK_ALIGNED_ACCESSES is TRUE, check if the access is supported even
4872    it is aligned, i.e., check if it is possible to vectorize it with different
4873    alignment.  */
4874
4875 enum dr_alignment_support
4876 vect_supportable_dr_alignment (struct data_reference *dr,
4877                                bool check_aligned_accesses)
4878 {
4879   gimple stmt = DR_STMT (dr);
4880   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4881   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
4882   enum machine_mode mode = TYPE_MODE (vectype);
4883   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
4884   struct loop *vect_loop = NULL;
4885   bool nested_in_vect_loop = false;
4886
4887   if (aligned_access_p (dr) && !check_aligned_accesses)
4888     return dr_aligned;
4889
4890   if (loop_vinfo)
4891     {
4892       vect_loop = LOOP_VINFO_LOOP (loop_vinfo);
4893       nested_in_vect_loop = nested_in_vect_loop_p (vect_loop, stmt);
4894     }
4895
4896   /* Possibly unaligned access.  */
4897
4898   /* We can choose between using the implicit realignment scheme (generating
4899      a misaligned_move stmt) and the explicit realignment scheme (generating
4900      aligned loads with a REALIGN_LOAD).  There are two variants to the
4901      explicit realignment scheme: optimized, and unoptimized.
4902      We can optimize the realignment only if the step between consecutive
4903      vector loads is equal to the vector size.  Since the vector memory
4904      accesses advance in steps of VS (Vector Size) in the vectorized loop, it
4905      is guaranteed that the misalignment amount remains the same throughout the
4906      execution of the vectorized loop.  Therefore, we can create the
4907      "realignment token" (the permutation mask that is passed to REALIGN_LOAD)
4908      at the loop preheader.
4909
4910      However, in the case of outer-loop vectorization, when vectorizing a
4911      memory access in the inner-loop nested within the LOOP that is now being
4912      vectorized, while it is guaranteed that the misalignment of the
4913      vectorized memory access will remain the same in different outer-loop
4914      iterations, it is *not* guaranteed that is will remain the same throughout
4915      the execution of the inner-loop.  This is because the inner-loop advances
4916      with the original scalar step (and not in steps of VS).  If the inner-loop
4917      step happens to be a multiple of VS, then the misalignment remains fixed
4918      and we can use the optimized realignment scheme.  For example:
4919
4920       for (i=0; i<N; i++)
4921         for (j=0; j<M; j++)
4922           s += a[i+j];
4923
4924      When vectorizing the i-loop in the above example, the step between
4925      consecutive vector loads is 1, and so the misalignment does not remain
4926      fixed across the execution of the inner-loop, and the realignment cannot
4927      be optimized (as illustrated in the following pseudo vectorized loop):
4928
4929       for (i=0; i<N; i+=4)
4930         for (j=0; j<M; j++){
4931           vs += vp[i+j]; // misalignment of &vp[i+j] is {0,1,2,3,0,1,2,3,...}
4932                          // when j is {0,1,2,3,4,5,6,7,...} respectively.
4933                          // (assuming that we start from an aligned address).
4934           }
4935
4936      We therefore have to use the unoptimized realignment scheme:
4937
4938       for (i=0; i<N; i+=4)
4939           for (j=k; j<M; j+=4)
4940           vs += vp[i+j]; // misalignment of &vp[i+j] is always k (assuming
4941                            // that the misalignment of the initial address is
4942                            // 0).
4943
4944      The loop can then be vectorized as follows:
4945
4946       for (k=0; k<4; k++){
4947         rt = get_realignment_token (&vp[k]);
4948         for (i=0; i<N; i+=4){
4949           v1 = vp[i+k];
4950           for (j=k; j<M; j+=4){
4951             v2 = vp[i+j+VS-1];
4952             va = REALIGN_LOAD <v1,v2,rt>;
4953             vs += va;
4954             v1 = v2;
4955           }
4956         }
4957     } */
4958
4959   if (DR_IS_READ (dr))
4960     {
4961       bool is_packed = false;
4962       tree type = (TREE_TYPE (DR_REF (dr)));
4963
4964       if (optab_handler (vec_realign_load_optab, mode) != CODE_FOR_nothing
4965           && (!targetm.vectorize.builtin_mask_for_load
4966               || targetm.vectorize.builtin_mask_for_load ()))
4967         {
4968           tree vectype = STMT_VINFO_VECTYPE (stmt_info);
4969           if ((nested_in_vect_loop
4970                && (TREE_INT_CST_LOW (DR_STEP (dr))
4971                    != GET_MODE_SIZE (TYPE_MODE (vectype))))
4972               || !loop_vinfo)
4973             return dr_explicit_realign;
4974           else
4975             return dr_explicit_realign_optimized;
4976         }
4977       if (!known_alignment_for_access_p (dr))
4978         is_packed = not_size_aligned (DR_REF (dr));
4979
4980       if (targetm.vectorize.
4981           support_vector_misalignment (mode, type,
4982                                        DR_MISALIGNMENT (dr), is_packed))
4983         /* Can't software pipeline the loads, but can at least do them.  */
4984         return dr_unaligned_supported;
4985     }
4986   else
4987     {
4988       bool is_packed = false;
4989       tree type = (TREE_TYPE (DR_REF (dr)));
4990
4991       if (!known_alignment_for_access_p (dr))
4992         is_packed = not_size_aligned (DR_REF (dr));
4993
4994      if (targetm.vectorize.
4995          support_vector_misalignment (mode, type,
4996                                       DR_MISALIGNMENT (dr), is_packed))
4997        return dr_unaligned_supported;
4998     }
4999
5000   /* Unsupported.  */
5001   return dr_unaligned_unsupported;
5002 }