Update gcc-50 to SVN version 221572
[dragonfly.git] / contrib / gcc-5.0 / gcc / tree-vect-data-refs.c
1 /* Data References Analysis and Manipulation Utilities for Vectorization.
2    Copyright (C) 2003-2015 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 "hash-set.h"
28 #include "machmode.h"
29 #include "vec.h"
30 #include "double-int.h"
31 #include "input.h"
32 #include "alias.h"
33 #include "symtab.h"
34 #include "wide-int.h"
35 #include "inchash.h"
36 #include "tree.h"
37 #include "fold-const.h"
38 #include "stor-layout.h"
39 #include "tm_p.h"
40 #include "target.h"
41 #include "predict.h"
42 #include "hard-reg-set.h"
43 #include "function.h"
44 #include "dominance.h"
45 #include "cfg.h"
46 #include "basic-block.h"
47 #include "gimple-pretty-print.h"
48 #include "tree-ssa-alias.h"
49 #include "internal-fn.h"
50 #include "tree-eh.h"
51 #include "gimple-expr.h"
52 #include "is-a.h"
53 #include "gimple.h"
54 #include "gimplify.h"
55 #include "gimple-iterator.h"
56 #include "gimplify-me.h"
57 #include "gimple-ssa.h"
58 #include "tree-phinodes.h"
59 #include "ssa-iterators.h"
60 #include "stringpool.h"
61 #include "tree-ssanames.h"
62 #include "tree-ssa-loop-ivopts.h"
63 #include "tree-ssa-loop-manip.h"
64 #include "tree-ssa-loop.h"
65 #include "cfgloop.h"
66 #include "tree-chrec.h"
67 #include "tree-scalar-evolution.h"
68 #include "tree-vectorizer.h"
69 #include "diagnostic-core.h"
70 #include "hash-map.h"
71 #include "plugin-api.h"
72 #include "ipa-ref.h"
73 #include "cgraph.h"
74 /* Need to include rtl.h, expr.h, etc. for optabs.  */
75 #include "hashtab.h"
76 #include "rtl.h"
77 #include "flags.h"
78 #include "statistics.h"
79 #include "real.h"
80 #include "fixed-value.h"
81 #include "insn-config.h"
82 #include "expmed.h"
83 #include "dojump.h"
84 #include "explow.h"
85 #include "calls.h"
86 #include "emit-rtl.h"
87 #include "varasm.h"
88 #include "stmt.h"
89 #include "expr.h"
90 #include "insn-codes.h"
91 #include "optabs.h"
92 #include "builtins.h"
93
94 /* Return true if load- or store-lanes optab OPTAB is implemented for
95    COUNT vectors of type VECTYPE.  NAME is the name of OPTAB.  */
96
97 static bool
98 vect_lanes_optab_supported_p (const char *name, convert_optab optab,
99                               tree vectype, unsigned HOST_WIDE_INT count)
100 {
101   machine_mode mode, array_mode;
102   bool limit_p;
103
104   mode = TYPE_MODE (vectype);
105   limit_p = !targetm.array_mode_supported_p (mode, count);
106   array_mode = mode_for_size (count * GET_MODE_BITSIZE (mode),
107                               MODE_INT, limit_p);
108
109   if (array_mode == BLKmode)
110     {
111       if (dump_enabled_p ())
112         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
113                          "no array mode for %s[" HOST_WIDE_INT_PRINT_DEC "]\n",
114                          GET_MODE_NAME (mode), count);
115       return false;
116     }
117
118   if (convert_optab_handler (optab, array_mode, mode) == CODE_FOR_nothing)
119     {
120       if (dump_enabled_p ())
121         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
122                          "cannot use %s<%s><%s>\n", name,
123                          GET_MODE_NAME (array_mode), GET_MODE_NAME (mode));
124       return false;
125     }
126
127   if (dump_enabled_p ())
128     dump_printf_loc (MSG_NOTE, vect_location,
129                      "can use %s<%s><%s>\n", name, GET_MODE_NAME (array_mode),
130                      GET_MODE_NAME (mode));
131
132   return true;
133 }
134
135
136 /* Return the smallest scalar part of STMT.
137    This is used to determine the vectype of the stmt.  We generally set the
138    vectype according to the type of the result (lhs).  For stmts whose
139    result-type is different than the type of the arguments (e.g., demotion,
140    promotion), vectype will be reset appropriately (later).  Note that we have
141    to visit the smallest datatype in this function, because that determines the
142    VF.  If the smallest datatype in the loop is present only as the rhs of a
143    promotion operation - we'd miss it.
144    Such a case, where a variable of this datatype does not appear in the lhs
145    anywhere in the loop, can only occur if it's an invariant: e.g.:
146    'int_x = (int) short_inv', which we'd expect to have been optimized away by
147    invariant motion.  However, we cannot rely on invariant motion to always
148    take invariants out of the loop, and so in the case of promotion we also
149    have to check the rhs.
150    LHS_SIZE_UNIT and RHS_SIZE_UNIT contain the sizes of the corresponding
151    types.  */
152
153 tree
154 vect_get_smallest_scalar_type (gimple stmt, HOST_WIDE_INT *lhs_size_unit,
155                                HOST_WIDE_INT *rhs_size_unit)
156 {
157   tree scalar_type = gimple_expr_type (stmt);
158   HOST_WIDE_INT lhs, rhs;
159
160   lhs = rhs = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type));
161
162   if (is_gimple_assign (stmt)
163       && (gimple_assign_cast_p (stmt)
164           || gimple_assign_rhs_code (stmt) == WIDEN_MULT_EXPR
165           || gimple_assign_rhs_code (stmt) == WIDEN_LSHIFT_EXPR
166           || gimple_assign_rhs_code (stmt) == FLOAT_EXPR))
167     {
168       tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (stmt));
169
170       rhs = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (rhs_type));
171       if (rhs < lhs)
172         scalar_type = rhs_type;
173     }
174
175   *lhs_size_unit = lhs;
176   *rhs_size_unit = rhs;
177   return scalar_type;
178 }
179
180
181 /* Insert DDR into LOOP_VINFO list of ddrs that may alias and need to be
182    tested at run-time.  Return TRUE if DDR was successfully inserted.
183    Return false if versioning is not supported.  */
184
185 static bool
186 vect_mark_for_runtime_alias_test (ddr_p ddr, loop_vec_info loop_vinfo)
187 {
188   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
189
190   if ((unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS) == 0)
191     return false;
192
193   if (dump_enabled_p ())
194     {
195       dump_printf_loc (MSG_NOTE, vect_location,
196                        "mark for run-time aliasing test between ");
197       dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_A (ddr)));
198       dump_printf (MSG_NOTE,  " and ");
199       dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_B (ddr)));
200       dump_printf (MSG_NOTE, "\n");
201     }
202
203   if (optimize_loop_nest_for_size_p (loop))
204     {
205       if (dump_enabled_p ())
206         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
207                          "versioning not supported when optimizing"
208                          " for size.\n");
209       return false;
210     }
211
212   /* FORNOW: We don't support versioning with outer-loop vectorization.  */
213   if (loop->inner)
214     {
215       if (dump_enabled_p ())
216         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
217                          "versioning not yet supported for outer-loops.\n");
218       return false;
219     }
220
221   /* FORNOW: We don't support creating runtime alias tests for non-constant
222      step.  */
223   if (TREE_CODE (DR_STEP (DDR_A (ddr))) != INTEGER_CST
224       || TREE_CODE (DR_STEP (DDR_B (ddr))) != INTEGER_CST)
225     {
226       if (dump_enabled_p ())
227         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
228                          "versioning not yet supported for non-constant "
229                          "step\n");
230       return false;
231     }
232
233   LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo).safe_push (ddr);
234   return true;
235 }
236
237
238 /* Function vect_analyze_data_ref_dependence.
239
240    Return TRUE if there (might) exist a dependence between a memory-reference
241    DRA and a memory-reference DRB.  When versioning for alias may check a
242    dependence at run-time, return FALSE.  Adjust *MAX_VF according to
243    the data dependence.  */
244
245 static bool
246 vect_analyze_data_ref_dependence (struct data_dependence_relation *ddr,
247                                   loop_vec_info loop_vinfo, int *max_vf)
248 {
249   unsigned int i;
250   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
251   struct data_reference *dra = DDR_A (ddr);
252   struct data_reference *drb = DDR_B (ddr);
253   stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
254   stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
255   lambda_vector dist_v;
256   unsigned int loop_depth;
257
258   /* In loop analysis all data references should be vectorizable.  */
259   if (!STMT_VINFO_VECTORIZABLE (stmtinfo_a)
260       || !STMT_VINFO_VECTORIZABLE (stmtinfo_b))
261     gcc_unreachable ();
262
263   /* Independent data accesses.  */
264   if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
265     return false;
266
267   if (dra == drb
268       || (DR_IS_READ (dra) && DR_IS_READ (drb)))
269     return false;
270
271   /* Even if we have an anti-dependence then, as the vectorized loop covers at
272      least two scalar iterations, there is always also a true dependence.
273      As the vectorizer does not re-order loads and stores we can ignore
274      the anti-dependence if TBAA can disambiguate both DRs similar to the
275      case with known negative distance anti-dependences (positive
276      distance anti-dependences would violate TBAA constraints).  */
277   if (((DR_IS_READ (dra) && DR_IS_WRITE (drb))
278        || (DR_IS_WRITE (dra) && DR_IS_READ (drb)))
279       && !alias_sets_conflict_p (get_alias_set (DR_REF (dra)),
280                                  get_alias_set (DR_REF (drb))))
281     return false;
282
283   /* Unknown data dependence.  */
284   if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
285     {
286       /* If user asserted safelen consecutive iterations can be
287          executed concurrently, assume independence.  */
288       if (loop->safelen >= 2)
289         {
290           if (loop->safelen < *max_vf)
291             *max_vf = loop->safelen;
292           LOOP_VINFO_NO_DATA_DEPENDENCIES (loop_vinfo) = false;
293           return false;
294         }
295
296       if (STMT_VINFO_GATHER_P (stmtinfo_a)
297           || STMT_VINFO_GATHER_P (stmtinfo_b))
298         {
299           if (dump_enabled_p ())
300             {
301               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
302                                "versioning for alias not supported for: "
303                                "can't determine dependence between ");
304               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
305                                  DR_REF (dra));
306               dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
307               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
308                                  DR_REF (drb));
309               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
310             }
311           return true;
312         }
313
314       if (dump_enabled_p ())
315         {
316           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
317                            "versioning for alias required: "
318                            "can't determine dependence between ");
319           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
320                              DR_REF (dra));
321           dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
322           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
323                              DR_REF (drb));
324           dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
325         }
326
327       /* Add to list of ddrs that need to be tested at run-time.  */
328       return !vect_mark_for_runtime_alias_test (ddr, loop_vinfo);
329     }
330
331   /* Known data dependence.  */
332   if (DDR_NUM_DIST_VECTS (ddr) == 0)
333     {
334       /* If user asserted safelen consecutive iterations can be
335          executed concurrently, assume independence.  */
336       if (loop->safelen >= 2)
337         {
338           if (loop->safelen < *max_vf)
339             *max_vf = loop->safelen;
340           LOOP_VINFO_NO_DATA_DEPENDENCIES (loop_vinfo) = false;
341           return false;
342         }
343
344       if (STMT_VINFO_GATHER_P (stmtinfo_a)
345           || STMT_VINFO_GATHER_P (stmtinfo_b))
346         {
347           if (dump_enabled_p ())
348             {
349               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
350                                "versioning for alias not supported for: "
351                                "bad dist vector for ");
352               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
353                                  DR_REF (dra));
354               dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
355               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
356                                  DR_REF (drb));
357               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
358             }
359           return true;
360         }
361
362       if (dump_enabled_p ())
363         {
364           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
365                            "versioning for alias required: "
366                            "bad dist vector for ");
367           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (dra));
368           dump_printf (MSG_MISSED_OPTIMIZATION,  " and ");
369           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (drb));
370           dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
371         }
372       /* Add to list of ddrs that need to be tested at run-time.  */
373       return !vect_mark_for_runtime_alias_test (ddr, loop_vinfo);
374     }
375
376   loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr));
377   FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
378     {
379       int dist = dist_v[loop_depth];
380
381       if (dump_enabled_p ())
382         dump_printf_loc (MSG_NOTE, vect_location,
383                          "dependence distance  = %d.\n", dist);
384
385       if (dist == 0)
386         {
387           if (dump_enabled_p ())
388             {
389               dump_printf_loc (MSG_NOTE, vect_location,
390                                "dependence distance == 0 between ");
391               dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
392               dump_printf (MSG_NOTE, " and ");
393               dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
394               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
395             }
396
397           /* When we perform grouped accesses and perform implicit CSE
398              by detecting equal accesses and doing disambiguation with
399              runtime alias tests like for
400                 .. = a[i];
401                 .. = a[i+1];
402                 a[i] = ..;
403                 a[i+1] = ..;
404                 *p = ..;
405                 .. = a[i];
406                 .. = a[i+1];
407              where we will end up loading { a[i], a[i+1] } once, make
408              sure that inserting group loads before the first load and
409              stores after the last store will do the right thing.
410              Similar for groups like
411                 a[i] = ...;
412                 ... = a[i];
413                 a[i+1] = ...;
414              where loads from the group interleave with the store.  */
415           if (STMT_VINFO_GROUPED_ACCESS (stmtinfo_a)
416               || STMT_VINFO_GROUPED_ACCESS (stmtinfo_b))
417             {
418               gimple earlier_stmt;
419               earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));
420               if (DR_IS_WRITE
421                     (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
422                 {
423                   if (dump_enabled_p ())
424                     dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
425                                      "READ_WRITE dependence in interleaving."
426                                      "\n");
427                   return true;
428                 }
429             }
430
431           continue;
432         }
433
434       if (dist > 0 && DDR_REVERSED_P (ddr))
435         {
436           /* If DDR_REVERSED_P the order of the data-refs in DDR was
437              reversed (to make distance vector positive), and the actual
438              distance is negative.  */
439           if (dump_enabled_p ())
440             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
441                              "dependence distance negative.\n");
442           /* Record a negative dependence distance to later limit the
443              amount of stmt copying / unrolling we can perform.
444              Only need to handle read-after-write dependence.  */
445           if (DR_IS_READ (drb)
446               && (STMT_VINFO_MIN_NEG_DIST (stmtinfo_b) == 0
447                   || STMT_VINFO_MIN_NEG_DIST (stmtinfo_b) > (unsigned)dist))
448             STMT_VINFO_MIN_NEG_DIST (stmtinfo_b) = dist;
449           continue;
450         }
451
452       if (abs (dist) >= 2
453           && abs (dist) < *max_vf)
454         {
455           /* The dependence distance requires reduction of the maximal
456              vectorization factor.  */
457           *max_vf = abs (dist);
458           if (dump_enabled_p ())
459             dump_printf_loc (MSG_NOTE, vect_location,
460                              "adjusting maximal vectorization factor to %i\n",
461                              *max_vf);
462         }
463
464       if (abs (dist) >= *max_vf)
465         {
466           /* Dependence distance does not create dependence, as far as
467              vectorization is concerned, in this case.  */
468           if (dump_enabled_p ())
469             dump_printf_loc (MSG_NOTE, vect_location,
470                              "dependence distance >= VF.\n");
471           continue;
472         }
473
474       if (dump_enabled_p ())
475         {
476           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
477                        "not vectorized, possible dependence "
478                        "between data-refs ");
479           dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
480           dump_printf (MSG_NOTE,  " and ");
481           dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
482           dump_printf (MSG_NOTE,  "\n");
483         }
484
485       return true;
486     }
487
488   return false;
489 }
490
491 /* Function vect_analyze_data_ref_dependences.
492
493    Examine all the data references in the loop, and make sure there do not
494    exist any data dependences between them.  Set *MAX_VF according to
495    the maximum vectorization factor the data dependences allow.  */
496
497 bool
498 vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo, int *max_vf)
499 {
500   unsigned int i;
501   struct data_dependence_relation *ddr;
502
503   if (dump_enabled_p ())
504     dump_printf_loc (MSG_NOTE, vect_location,
505                      "=== vect_analyze_data_ref_dependences ===\n");
506
507   LOOP_VINFO_NO_DATA_DEPENDENCIES (loop_vinfo) = true;
508   if (!compute_all_dependences (LOOP_VINFO_DATAREFS (loop_vinfo),
509                                 &LOOP_VINFO_DDRS (loop_vinfo),
510                                 LOOP_VINFO_LOOP_NEST (loop_vinfo), true))
511     return false;
512
513   FOR_EACH_VEC_ELT (LOOP_VINFO_DDRS (loop_vinfo), i, ddr)
514     if (vect_analyze_data_ref_dependence (ddr, loop_vinfo, max_vf))
515       return false;
516
517   return true;
518 }
519
520
521 /* Function vect_slp_analyze_data_ref_dependence.
522
523    Return TRUE if there (might) exist a dependence between a memory-reference
524    DRA and a memory-reference DRB.  When versioning for alias may check a
525    dependence at run-time, return FALSE.  Adjust *MAX_VF according to
526    the data dependence.  */
527
528 static bool
529 vect_slp_analyze_data_ref_dependence (struct data_dependence_relation *ddr)
530 {
531   struct data_reference *dra = DDR_A (ddr);
532   struct data_reference *drb = DDR_B (ddr);
533
534   /* We need to check dependences of statements marked as unvectorizable
535      as well, they still can prohibit vectorization.  */
536
537   /* Independent data accesses.  */
538   if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
539     return false;
540
541   if (dra == drb)
542     return false;
543
544   /* Read-read is OK.  */
545   if (DR_IS_READ (dra) && DR_IS_READ (drb))
546     return false;
547
548   /* If dra and drb are part of the same interleaving chain consider
549      them independent.  */
550   if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (DR_STMT (dra)))
551       && (GROUP_FIRST_ELEMENT (vinfo_for_stmt (DR_STMT (dra)))
552           == GROUP_FIRST_ELEMENT (vinfo_for_stmt (DR_STMT (drb)))))
553     return false;
554
555   /* Unknown data dependence.  */
556   if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
557     {
558       if  (dump_enabled_p ())
559         {
560           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
561                            "can't determine dependence between ");
562           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (dra));
563           dump_printf (MSG_MISSED_OPTIMIZATION,  " and ");
564           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (drb));
565           dump_printf (MSG_MISSED_OPTIMIZATION,  "\n");
566         }
567     }
568   else if (dump_enabled_p ())
569     {
570       dump_printf_loc (MSG_NOTE, vect_location,
571                        "determined dependence between ");
572       dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
573       dump_printf (MSG_NOTE, " and ");
574       dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
575       dump_printf (MSG_NOTE,  "\n");
576     }
577
578   /* We do not vectorize basic blocks with write-write dependencies.  */
579   if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
580     return true;
581
582   /* If we have a read-write dependence check that the load is before the store.
583      When we vectorize basic blocks, vector load can be only before
584      corresponding scalar load, and vector store can be only after its
585      corresponding scalar store.  So the order of the acceses is preserved in
586      case the load is before the store.  */
587   gimple earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));
588   if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
589     {
590       /* That only holds for load-store pairs taking part in vectorization.  */
591       if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dra)))
592           && STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (drb))))
593         return false;
594     }
595
596   return true;
597 }
598
599
600 /* Function vect_analyze_data_ref_dependences.
601
602    Examine all the data references in the basic-block, and make sure there
603    do not exist any data dependences between them.  Set *MAX_VF according to
604    the maximum vectorization factor the data dependences allow.  */
605
606 bool
607 vect_slp_analyze_data_ref_dependences (bb_vec_info bb_vinfo)
608 {
609   struct data_dependence_relation *ddr;
610   unsigned int i;
611
612   if (dump_enabled_p ())
613     dump_printf_loc (MSG_NOTE, vect_location,
614                      "=== vect_slp_analyze_data_ref_dependences ===\n");
615
616   if (!compute_all_dependences (BB_VINFO_DATAREFS (bb_vinfo),
617                                 &BB_VINFO_DDRS (bb_vinfo),
618                                 vNULL, true))
619     return false;
620
621   FOR_EACH_VEC_ELT (BB_VINFO_DDRS (bb_vinfo), i, ddr)
622     if (vect_slp_analyze_data_ref_dependence (ddr))
623       return false;
624
625   return true;
626 }
627
628
629 /* Function vect_compute_data_ref_alignment
630
631    Compute the misalignment of the data reference DR.
632
633    Output:
634    1. If during the misalignment computation it is found that the data reference
635       cannot be vectorized then false is returned.
636    2. DR_MISALIGNMENT (DR) is defined.
637
638    FOR NOW: No analysis is actually performed. Misalignment is calculated
639    only for trivial cases. TODO.  */
640
641 static bool
642 vect_compute_data_ref_alignment (struct data_reference *dr)
643 {
644   gimple stmt = DR_STMT (dr);
645   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
646   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
647   struct loop *loop = NULL;
648   tree ref = DR_REF (dr);
649   tree vectype;
650   tree base, base_addr;
651   bool base_aligned;
652   tree misalign;
653   tree aligned_to;
654   unsigned HOST_WIDE_INT alignment;
655
656   if (dump_enabled_p ())
657     dump_printf_loc (MSG_NOTE, vect_location,
658                      "vect_compute_data_ref_alignment:\n");
659
660   if (loop_vinfo)
661     loop = LOOP_VINFO_LOOP (loop_vinfo);
662
663   /* Initialize misalignment to unknown.  */
664   SET_DR_MISALIGNMENT (dr, -1);
665
666   /* Strided loads perform only component accesses, misalignment information
667      is irrelevant for them.  */
668   if (STMT_VINFO_STRIDE_LOAD_P (stmt_info))
669     return true;
670
671   misalign = DR_INIT (dr);
672   aligned_to = DR_ALIGNED_TO (dr);
673   base_addr = DR_BASE_ADDRESS (dr);
674   vectype = STMT_VINFO_VECTYPE (stmt_info);
675
676   /* In case the dataref is in an inner-loop of the loop that is being
677      vectorized (LOOP), we use the base and misalignment information
678      relative to the outer-loop (LOOP).  This is ok only if the misalignment
679      stays the same throughout the execution of the inner-loop, which is why
680      we have to check that the stride of the dataref in the inner-loop evenly
681      divides by the vector size.  */
682   if (loop && nested_in_vect_loop_p (loop, stmt))
683     {
684       tree step = DR_STEP (dr);
685       HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
686
687       if (dr_step % GET_MODE_SIZE (TYPE_MODE (vectype)) == 0)
688         {
689           if (dump_enabled_p ())
690             dump_printf_loc (MSG_NOTE, vect_location,
691                              "inner step divides the vector-size.\n");
692           misalign = STMT_VINFO_DR_INIT (stmt_info);
693           aligned_to = STMT_VINFO_DR_ALIGNED_TO (stmt_info);
694           base_addr = STMT_VINFO_DR_BASE_ADDRESS (stmt_info);
695         }
696       else
697         {
698           if (dump_enabled_p ())
699             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
700                              "inner step doesn't divide the vector-size.\n");
701           misalign = NULL_TREE;
702         }
703     }
704
705   /* Similarly, if we're doing basic-block vectorization, we can only use
706      base and misalignment information relative to an innermost loop if the
707      misalignment stays the same throughout the execution of the loop.
708      As above, this is the case if the stride of the dataref evenly divides
709      by the vector size.  */
710   if (!loop)
711     {
712       tree step = DR_STEP (dr);
713       HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
714
715       if (dr_step % GET_MODE_SIZE (TYPE_MODE (vectype)) != 0)
716         {
717           if (dump_enabled_p ())
718             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
719                              "SLP: step doesn't divide the vector-size.\n");
720           misalign = NULL_TREE;
721         }
722     }
723
724   alignment = TYPE_ALIGN_UNIT (vectype);
725
726   if ((compare_tree_int (aligned_to, alignment) < 0)
727       || !misalign)
728     {
729       if (dump_enabled_p ())
730         {
731           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
732                            "Unknown alignment for access: ");
733           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, ref);
734           dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
735         }
736       return true;
737     }
738
739   /* To look at alignment of the base we have to preserve an inner MEM_REF
740      as that carries alignment information of the actual access.  */
741   base = ref;
742   while (handled_component_p (base))
743     base = TREE_OPERAND (base, 0);
744   if (TREE_CODE (base) == MEM_REF)
745     base = build2 (MEM_REF, TREE_TYPE (base), base_addr,
746                    build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)), 0));
747
748   if (get_object_alignment (base) >= TYPE_ALIGN (vectype))
749     base_aligned = true;
750   else
751     base_aligned = false;
752
753   if (!base_aligned)
754     {
755       /* Strip an inner MEM_REF to a bare decl if possible.  */
756       if (TREE_CODE (base) == MEM_REF
757           && integer_zerop (TREE_OPERAND (base, 1))
758           && TREE_CODE (TREE_OPERAND (base, 0)) == ADDR_EXPR)
759         base = TREE_OPERAND (TREE_OPERAND (base, 0), 0);
760
761       if (!vect_can_force_dr_alignment_p (base, TYPE_ALIGN (vectype)))
762         {
763           if (dump_enabled_p ())
764             {
765               dump_printf_loc (MSG_NOTE, vect_location,
766                                "can't force alignment of ref: ");
767               dump_generic_expr (MSG_NOTE, TDF_SLIM, ref);
768               dump_printf (MSG_NOTE, "\n");
769             }
770           return true;
771         }
772
773       /* Force the alignment of the decl.
774          NOTE: This is the only change to the code we make during
775          the analysis phase, before deciding to vectorize the loop.  */
776       if (dump_enabled_p ())
777         {
778           dump_printf_loc (MSG_NOTE, vect_location, "force alignment of ");
779           dump_generic_expr (MSG_NOTE, TDF_SLIM, ref);
780           dump_printf (MSG_NOTE, "\n");
781         }
782
783       ((dataref_aux *)dr->aux)->base_decl = base;
784       ((dataref_aux *)dr->aux)->base_misaligned = true;
785     }
786
787   /* If this is a backward running DR then first access in the larger
788      vectype actually is N-1 elements before the address in the DR.
789      Adjust misalign accordingly.  */
790   if (tree_int_cst_sgn (DR_STEP (dr)) < 0)
791     {
792       tree offset = ssize_int (TYPE_VECTOR_SUBPARTS (vectype) - 1);
793       /* DR_STEP(dr) is the same as -TYPE_SIZE of the scalar type,
794          otherwise we wouldn't be here.  */
795       offset = fold_build2 (MULT_EXPR, ssizetype, offset, DR_STEP (dr));
796       /* PLUS because DR_STEP was negative.  */
797       misalign = size_binop (PLUS_EXPR, misalign, offset);
798     }
799
800   SET_DR_MISALIGNMENT (dr,
801                        wi::mod_floor (misalign, alignment, SIGNED).to_uhwi ());
802
803   if (dump_enabled_p ())
804     {
805       dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
806                        "misalign = %d bytes of ref ", DR_MISALIGNMENT (dr));
807       dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, ref);
808       dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
809     }
810
811   return true;
812 }
813
814
815 /* Function vect_compute_data_refs_alignment
816
817    Compute the misalignment of data references in the loop.
818    Return FALSE if a data reference is found that cannot be vectorized.  */
819
820 static bool
821 vect_compute_data_refs_alignment (loop_vec_info loop_vinfo,
822                                   bb_vec_info bb_vinfo)
823 {
824   vec<data_reference_p> datarefs;
825   struct data_reference *dr;
826   unsigned int i;
827
828   if (loop_vinfo)
829     datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
830   else
831     datarefs = BB_VINFO_DATAREFS (bb_vinfo);
832
833   FOR_EACH_VEC_ELT (datarefs, i, dr)
834     if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr)))
835         && !vect_compute_data_ref_alignment (dr))
836       {
837         if (bb_vinfo)
838           {
839             /* Mark unsupported statement as unvectorizable.  */
840             STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) = false;
841             continue;
842           }
843         else
844           return false;
845       }
846
847   return true;
848 }
849
850
851 /* Function vect_update_misalignment_for_peel
852
853    DR - the data reference whose misalignment is to be adjusted.
854    DR_PEEL - the data reference whose misalignment is being made
855              zero in the vector loop by the peel.
856    NPEEL - the number of iterations in the peel loop if the misalignment
857            of DR_PEEL is known at compile time.  */
858
859 static void
860 vect_update_misalignment_for_peel (struct data_reference *dr,
861                                    struct data_reference *dr_peel, int npeel)
862 {
863   unsigned int i;
864   vec<dr_p> same_align_drs;
865   struct data_reference *current_dr;
866   int dr_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr))));
867   int dr_peel_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr_peel))));
868   stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));
869   stmt_vec_info peel_stmt_info = vinfo_for_stmt (DR_STMT (dr_peel));
870
871  /* For interleaved data accesses the step in the loop must be multiplied by
872      the size of the interleaving group.  */
873   if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
874     dr_size *= GROUP_SIZE (vinfo_for_stmt (GROUP_FIRST_ELEMENT (stmt_info)));
875   if (STMT_VINFO_GROUPED_ACCESS (peel_stmt_info))
876     dr_peel_size *= GROUP_SIZE (peel_stmt_info);
877
878   /* It can be assumed that the data refs with the same alignment as dr_peel
879      are aligned in the vector loop.  */
880   same_align_drs
881     = STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (DR_STMT (dr_peel)));
882   FOR_EACH_VEC_ELT (same_align_drs, i, current_dr)
883     {
884       if (current_dr != dr)
885         continue;
886       gcc_assert (DR_MISALIGNMENT (dr) / dr_size ==
887                   DR_MISALIGNMENT (dr_peel) / dr_peel_size);
888       SET_DR_MISALIGNMENT (dr, 0);
889       return;
890     }
891
892   if (known_alignment_for_access_p (dr)
893       && known_alignment_for_access_p (dr_peel))
894     {
895       bool negative = tree_int_cst_compare (DR_STEP (dr), size_zero_node) < 0;
896       int misal = DR_MISALIGNMENT (dr);
897       tree vectype = STMT_VINFO_VECTYPE (stmt_info);
898       misal += negative ? -npeel * dr_size : npeel * dr_size;
899       misal &= (TYPE_ALIGN (vectype) / BITS_PER_UNIT) - 1;
900       SET_DR_MISALIGNMENT (dr, misal);
901       return;
902     }
903
904   if (dump_enabled_p ())
905     dump_printf_loc (MSG_NOTE, vect_location, "Setting misalignment to -1.\n");
906   SET_DR_MISALIGNMENT (dr, -1);
907 }
908
909
910 /* Function vect_verify_datarefs_alignment
911
912    Return TRUE if all data references in the loop can be
913    handled with respect to alignment.  */
914
915 bool
916 vect_verify_datarefs_alignment (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
917 {
918   vec<data_reference_p> datarefs;
919   struct data_reference *dr;
920   enum dr_alignment_support supportable_dr_alignment;
921   unsigned int i;
922
923   if (loop_vinfo)
924     datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
925   else
926     datarefs = BB_VINFO_DATAREFS (bb_vinfo);
927
928   FOR_EACH_VEC_ELT (datarefs, i, dr)
929     {
930       gimple stmt = DR_STMT (dr);
931       stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
932
933       if (!STMT_VINFO_RELEVANT_P (stmt_info))
934         continue;
935
936       /* For interleaving, only the alignment of the first access matters. 
937          Skip statements marked as not vectorizable.  */
938       if ((STMT_VINFO_GROUPED_ACCESS (stmt_info)
939            && GROUP_FIRST_ELEMENT (stmt_info) != stmt)
940           || !STMT_VINFO_VECTORIZABLE (stmt_info))
941         continue;
942
943       /* Strided loads perform only component accesses, alignment is
944          irrelevant for them.  */
945       if (STMT_VINFO_STRIDE_LOAD_P (stmt_info))
946         continue;
947
948       supportable_dr_alignment = vect_supportable_dr_alignment (dr, false);
949       if (!supportable_dr_alignment)
950         {
951           if (dump_enabled_p ())
952             {
953               if (DR_IS_READ (dr))
954                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
955                                  "not vectorized: unsupported unaligned load.");
956               else
957                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
958                                  "not vectorized: unsupported unaligned "
959                                  "store.");
960
961               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
962                                  DR_REF (dr));
963               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
964             }
965           return false;
966         }
967       if (supportable_dr_alignment != dr_aligned && dump_enabled_p ())
968         dump_printf_loc (MSG_NOTE, vect_location,
969                          "Vectorizing an unaligned access.\n");
970     }
971   return true;
972 }
973
974 /* Given an memory reference EXP return whether its alignment is less
975    than its size.  */
976
977 static bool
978 not_size_aligned (tree exp)
979 {
980   if (!tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (exp))))
981     return true;
982
983   return (tree_to_uhwi (TYPE_SIZE (TREE_TYPE (exp)))
984           > get_object_alignment (exp));
985 }
986
987 /* Function vector_alignment_reachable_p
988
989    Return true if vector alignment for DR is reachable by peeling
990    a few loop iterations.  Return false otherwise.  */
991
992 static bool
993 vector_alignment_reachable_p (struct data_reference *dr)
994 {
995   gimple stmt = DR_STMT (dr);
996   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
997   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
998
999   if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
1000     {
1001       /* For interleaved access we peel only if number of iterations in
1002          the prolog loop ({VF - misalignment}), is a multiple of the
1003          number of the interleaved accesses.  */
1004       int elem_size, mis_in_elements;
1005       int nelements = TYPE_VECTOR_SUBPARTS (vectype);
1006
1007       /* FORNOW: handle only known alignment.  */
1008       if (!known_alignment_for_access_p (dr))
1009         return false;
1010
1011       elem_size = GET_MODE_SIZE (TYPE_MODE (vectype)) / nelements;
1012       mis_in_elements = DR_MISALIGNMENT (dr) / elem_size;
1013
1014       if ((nelements - mis_in_elements) % GROUP_SIZE (stmt_info))
1015         return false;
1016     }
1017
1018   /* If misalignment is known at the compile time then allow peeling
1019      only if natural alignment is reachable through peeling.  */
1020   if (known_alignment_for_access_p (dr) && !aligned_access_p (dr))
1021     {
1022       HOST_WIDE_INT elmsize =
1023                 int_cst_value (TYPE_SIZE_UNIT (TREE_TYPE (vectype)));
1024       if (dump_enabled_p ())
1025         {
1026           dump_printf_loc (MSG_NOTE, vect_location,
1027                            "data size =" HOST_WIDE_INT_PRINT_DEC, elmsize);
1028           dump_printf (MSG_NOTE,
1029                        ". misalignment = %d.\n", DR_MISALIGNMENT (dr));
1030         }
1031       if (DR_MISALIGNMENT (dr) % elmsize)
1032         {
1033           if (dump_enabled_p ())
1034             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1035                              "data size does not divide the misalignment.\n");
1036           return false;
1037         }
1038     }
1039
1040   if (!known_alignment_for_access_p (dr))
1041     {
1042       tree type = TREE_TYPE (DR_REF (dr));
1043       bool is_packed = not_size_aligned (DR_REF (dr));
1044       if (dump_enabled_p ())
1045         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1046                          "Unknown misalignment, is_packed = %d\n",is_packed);
1047       if ((TYPE_USER_ALIGN (type) && !is_packed)
1048           || targetm.vectorize.vector_alignment_reachable (type, is_packed))
1049         return true;
1050       else
1051         return false;
1052     }
1053
1054   return true;
1055 }
1056
1057
1058 /* Calculate the cost of the memory access represented by DR.  */
1059
1060 static void
1061 vect_get_data_access_cost (struct data_reference *dr,
1062                            unsigned int *inside_cost,
1063                            unsigned int *outside_cost,
1064                            stmt_vector_for_cost *body_cost_vec)
1065 {
1066   gimple stmt = DR_STMT (dr);
1067   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1068   int nunits = TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info));
1069   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1070   int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1071   int ncopies = vf / nunits;
1072
1073   if (DR_IS_READ (dr))
1074     vect_get_load_cost (dr, ncopies, true, inside_cost, outside_cost,
1075                         NULL, body_cost_vec, false);
1076   else
1077     vect_get_store_cost (dr, ncopies, inside_cost, body_cost_vec);
1078
1079   if (dump_enabled_p ())
1080     dump_printf_loc (MSG_NOTE, vect_location,
1081                      "vect_get_data_access_cost: inside_cost = %d, "
1082                      "outside_cost = %d.\n", *inside_cost, *outside_cost);
1083 }
1084
1085
1086 /* Insert DR into peeling hash table with NPEEL as key.  */
1087
1088 static void
1089 vect_peeling_hash_insert (loop_vec_info loop_vinfo, struct data_reference *dr,
1090                           int npeel)
1091 {
1092   struct _vect_peel_info elem, *slot;
1093   _vect_peel_info **new_slot;
1094   bool supportable_dr_alignment = vect_supportable_dr_alignment (dr, true);
1095
1096   elem.npeel = npeel;
1097   slot = LOOP_VINFO_PEELING_HTAB (loop_vinfo)->find (&elem);
1098   if (slot)
1099     slot->count++;
1100   else
1101     {
1102       slot = XNEW (struct _vect_peel_info);
1103       slot->npeel = npeel;
1104       slot->dr = dr;
1105       slot->count = 1;
1106       new_slot
1107         = LOOP_VINFO_PEELING_HTAB (loop_vinfo)->find_slot (slot, INSERT);
1108       *new_slot = slot;
1109     }
1110
1111   if (!supportable_dr_alignment
1112       && unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo)))
1113     slot->count += VECT_MAX_COST;
1114 }
1115
1116
1117 /* Traverse peeling hash table to find peeling option that aligns maximum
1118    number of data accesses.  */
1119
1120 int
1121 vect_peeling_hash_get_most_frequent (_vect_peel_info **slot,
1122                                      _vect_peel_extended_info *max)
1123 {
1124   vect_peel_info elem = *slot;
1125
1126   if (elem->count > max->peel_info.count
1127       || (elem->count == max->peel_info.count
1128           && max->peel_info.npeel > elem->npeel))
1129     {
1130       max->peel_info.npeel = elem->npeel;
1131       max->peel_info.count = elem->count;
1132       max->peel_info.dr = elem->dr;
1133     }
1134
1135   return 1;
1136 }
1137
1138
1139 /* Traverse peeling hash table and calculate cost for each peeling option.
1140    Find the one with the lowest cost.  */
1141
1142 int
1143 vect_peeling_hash_get_lowest_cost (_vect_peel_info **slot,
1144                                    _vect_peel_extended_info *min)
1145 {
1146   vect_peel_info elem = *slot;
1147   int save_misalignment, dummy;
1148   unsigned int inside_cost = 0, outside_cost = 0, i;
1149   gimple stmt = DR_STMT (elem->dr);
1150   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1151   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1152   vec<data_reference_p> datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1153   struct data_reference *dr;
1154   stmt_vector_for_cost prologue_cost_vec, body_cost_vec, epilogue_cost_vec;
1155   int single_iter_cost;
1156
1157   prologue_cost_vec.create (2);
1158   body_cost_vec.create (2);
1159   epilogue_cost_vec.create (2);
1160
1161   FOR_EACH_VEC_ELT (datarefs, i, dr)
1162     {
1163       stmt = DR_STMT (dr);
1164       stmt_info = vinfo_for_stmt (stmt);
1165       /* For interleaving, only the alignment of the first access
1166          matters.  */
1167       if (STMT_VINFO_GROUPED_ACCESS (stmt_info)
1168           && GROUP_FIRST_ELEMENT (stmt_info) != stmt)
1169         continue;
1170
1171       save_misalignment = DR_MISALIGNMENT (dr);
1172       vect_update_misalignment_for_peel (dr, elem->dr, elem->npeel);
1173       vect_get_data_access_cost (dr, &inside_cost, &outside_cost,
1174                                  &body_cost_vec);
1175       SET_DR_MISALIGNMENT (dr, save_misalignment);
1176     }
1177
1178   single_iter_cost = vect_get_single_scalar_iteration_cost (loop_vinfo);
1179   outside_cost += vect_get_known_peeling_cost
1180     (loop_vinfo, elem->npeel, &dummy,
1181      /* ???  We use this cost as number of stmts with scalar_stmt cost,
1182         thus divide by that.  This introduces rounding errors, thus better 
1183         introduce a new cost kind (raw_cost?  scalar_iter_cost?). */
1184      single_iter_cost / vect_get_stmt_cost (scalar_stmt),
1185      &prologue_cost_vec, &epilogue_cost_vec);
1186
1187   /* Prologue and epilogue costs are added to the target model later.
1188      These costs depend only on the scalar iteration cost, the
1189      number of peeling iterations finally chosen, and the number of
1190      misaligned statements.  So discard the information found here.  */
1191   prologue_cost_vec.release ();
1192   epilogue_cost_vec.release ();
1193
1194   if (inside_cost < min->inside_cost
1195       || (inside_cost == min->inside_cost && outside_cost < min->outside_cost))
1196     {
1197       min->inside_cost = inside_cost;
1198       min->outside_cost = outside_cost;
1199       min->body_cost_vec.release ();
1200       min->body_cost_vec = body_cost_vec;
1201       min->peel_info.dr = elem->dr;
1202       min->peel_info.npeel = elem->npeel;
1203     }
1204   else
1205     body_cost_vec.release ();
1206
1207   return 1;
1208 }
1209
1210
1211 /* Choose best peeling option by traversing peeling hash table and either
1212    choosing an option with the lowest cost (if cost model is enabled) or the
1213    option that aligns as many accesses as possible.  */
1214
1215 static struct data_reference *
1216 vect_peeling_hash_choose_best_peeling (loop_vec_info loop_vinfo,
1217                                        unsigned int *npeel,
1218                                        stmt_vector_for_cost *body_cost_vec)
1219 {
1220    struct _vect_peel_extended_info res;
1221
1222    res.peel_info.dr = NULL;
1223    res.body_cost_vec = stmt_vector_for_cost ();
1224
1225    if (!unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo)))
1226      {
1227        res.inside_cost = INT_MAX;
1228        res.outside_cost = INT_MAX;
1229        LOOP_VINFO_PEELING_HTAB (loop_vinfo)
1230            ->traverse <_vect_peel_extended_info *,
1231                        vect_peeling_hash_get_lowest_cost> (&res);
1232      }
1233    else
1234      {
1235        res.peel_info.count = 0;
1236        LOOP_VINFO_PEELING_HTAB (loop_vinfo)
1237            ->traverse <_vect_peel_extended_info *,
1238                        vect_peeling_hash_get_most_frequent> (&res);
1239      }
1240
1241    *npeel = res.peel_info.npeel;
1242    *body_cost_vec = res.body_cost_vec;
1243    return res.peel_info.dr;
1244 }
1245
1246
1247 /* Function vect_enhance_data_refs_alignment
1248
1249    This pass will use loop versioning and loop peeling in order to enhance
1250    the alignment of data references in the loop.
1251
1252    FOR NOW: we assume that whatever versioning/peeling takes place, only the
1253    original loop is to be vectorized.  Any other loops that are created by
1254    the transformations performed in this pass - are not supposed to be
1255    vectorized.  This restriction will be relaxed.
1256
1257    This pass will require a cost model to guide it whether to apply peeling
1258    or versioning or a combination of the two.  For example, the scheme that
1259    intel uses when given a loop with several memory accesses, is as follows:
1260    choose one memory access ('p') which alignment you want to force by doing
1261    peeling.  Then, either (1) generate a loop in which 'p' is aligned and all
1262    other accesses are not necessarily aligned, or (2) use loop versioning to
1263    generate one loop in which all accesses are aligned, and another loop in
1264    which only 'p' is necessarily aligned.
1265
1266    ("Automatic Intra-Register Vectorization for the Intel Architecture",
1267    Aart J.C. Bik, Milind Girkar, Paul M. Grey and Ximmin Tian, International
1268    Journal of Parallel Programming, Vol. 30, No. 2, April 2002.)
1269
1270    Devising a cost model is the most critical aspect of this work.  It will
1271    guide us on which access to peel for, whether to use loop versioning, how
1272    many versions to create, etc.  The cost model will probably consist of
1273    generic considerations as well as target specific considerations (on
1274    powerpc for example, misaligned stores are more painful than misaligned
1275    loads).
1276
1277    Here are the general steps involved in alignment enhancements:
1278
1279      -- original loop, before alignment analysis:
1280         for (i=0; i<N; i++){
1281           x = q[i];                     # DR_MISALIGNMENT(q) = unknown
1282           p[i] = y;                     # DR_MISALIGNMENT(p) = unknown
1283         }
1284
1285      -- After vect_compute_data_refs_alignment:
1286         for (i=0; i<N; i++){
1287           x = q[i];                     # DR_MISALIGNMENT(q) = 3
1288           p[i] = y;                     # DR_MISALIGNMENT(p) = unknown
1289         }
1290
1291      -- Possibility 1: we do loop versioning:
1292      if (p is aligned) {
1293         for (i=0; i<N; i++){    # loop 1A
1294           x = q[i];                     # DR_MISALIGNMENT(q) = 3
1295           p[i] = y;                     # DR_MISALIGNMENT(p) = 0
1296         }
1297      }
1298      else {
1299         for (i=0; i<N; i++){    # loop 1B
1300           x = q[i];                     # DR_MISALIGNMENT(q) = 3
1301           p[i] = y;                     # DR_MISALIGNMENT(p) = unaligned
1302         }
1303      }
1304
1305      -- Possibility 2: we do loop peeling:
1306      for (i = 0; i < 3; i++){   # (scalar loop, not to be vectorized).
1307         x = q[i];
1308         p[i] = y;
1309      }
1310      for (i = 3; i < N; i++){   # loop 2A
1311         x = q[i];                       # DR_MISALIGNMENT(q) = 0
1312         p[i] = y;                       # DR_MISALIGNMENT(p) = unknown
1313      }
1314
1315      -- Possibility 3: combination of loop peeling and versioning:
1316      for (i = 0; i < 3; i++){   # (scalar loop, not to be vectorized).
1317         x = q[i];
1318         p[i] = y;
1319      }
1320      if (p is aligned) {
1321         for (i = 3; i<N; i++){  # loop 3A
1322           x = q[i];                     # DR_MISALIGNMENT(q) = 0
1323           p[i] = y;                     # DR_MISALIGNMENT(p) = 0
1324         }
1325      }
1326      else {
1327         for (i = 3; i<N; i++){  # loop 3B
1328           x = q[i];                     # DR_MISALIGNMENT(q) = 0
1329           p[i] = y;                     # DR_MISALIGNMENT(p) = unaligned
1330         }
1331      }
1332
1333      These loops are later passed to loop_transform to be vectorized.  The
1334      vectorizer will use the alignment information to guide the transformation
1335      (whether to generate regular loads/stores, or with special handling for
1336      misalignment).  */
1337
1338 bool
1339 vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo)
1340 {
1341   vec<data_reference_p> datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1342   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1343   enum dr_alignment_support supportable_dr_alignment;
1344   struct data_reference *dr0 = NULL, *first_store = NULL;
1345   struct data_reference *dr;
1346   unsigned int i, j;
1347   bool do_peeling = false;
1348   bool do_versioning = false;
1349   bool stat;
1350   gimple stmt;
1351   stmt_vec_info stmt_info;
1352   unsigned int npeel = 0;
1353   bool all_misalignments_unknown = true;
1354   unsigned int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1355   unsigned possible_npeel_number = 1;
1356   tree vectype;
1357   unsigned int nelements, mis, same_align_drs_max = 0;
1358   stmt_vector_for_cost body_cost_vec = stmt_vector_for_cost ();
1359
1360   if (dump_enabled_p ())
1361     dump_printf_loc (MSG_NOTE, vect_location,
1362                      "=== vect_enhance_data_refs_alignment ===\n");
1363
1364   /* While cost model enhancements are expected in the future, the high level
1365      view of the code at this time is as follows:
1366
1367      A) If there is a misaligned access then see if peeling to align
1368         this access can make all data references satisfy
1369         vect_supportable_dr_alignment.  If so, update data structures
1370         as needed and return true.
1371
1372      B) If peeling wasn't possible and there is a data reference with an
1373         unknown misalignment that does not satisfy vect_supportable_dr_alignment
1374         then see if loop versioning checks can be used to make all data
1375         references satisfy vect_supportable_dr_alignment.  If so, update
1376         data structures as needed and return true.
1377
1378      C) If neither peeling nor versioning were successful then return false if
1379         any data reference does not satisfy vect_supportable_dr_alignment.
1380
1381      D) Return true (all data references satisfy vect_supportable_dr_alignment).
1382
1383      Note, Possibility 3 above (which is peeling and versioning together) is not
1384      being done at this time.  */
1385
1386   /* (1) Peeling to force alignment.  */
1387
1388   /* (1.1) Decide whether to perform peeling, and how many iterations to peel:
1389      Considerations:
1390      + How many accesses will become aligned due to the peeling
1391      - How many accesses will become unaligned due to the peeling,
1392        and the cost of misaligned accesses.
1393      - The cost of peeling (the extra runtime checks, the increase
1394        in code size).  */
1395
1396   FOR_EACH_VEC_ELT (datarefs, i, dr)
1397     {
1398       stmt = DR_STMT (dr);
1399       stmt_info = vinfo_for_stmt (stmt);
1400
1401       if (!STMT_VINFO_RELEVANT_P (stmt_info))
1402         continue;
1403
1404       /* For interleaving, only the alignment of the first access
1405          matters.  */
1406       if (STMT_VINFO_GROUPED_ACCESS (stmt_info)
1407           && GROUP_FIRST_ELEMENT (stmt_info) != stmt)
1408         continue;
1409
1410       /* For invariant accesses there is nothing to enhance.  */
1411       if (integer_zerop (DR_STEP (dr)))
1412         continue;
1413
1414       /* Strided loads perform only component accesses, alignment is
1415          irrelevant for them.  */
1416       if (STMT_VINFO_STRIDE_LOAD_P (stmt_info))
1417         continue;
1418
1419       supportable_dr_alignment = vect_supportable_dr_alignment (dr, true);
1420       do_peeling = vector_alignment_reachable_p (dr);
1421       if (do_peeling)
1422         {
1423           if (known_alignment_for_access_p (dr))
1424             {
1425               unsigned int npeel_tmp;
1426               bool negative = tree_int_cst_compare (DR_STEP (dr),
1427                                                     size_zero_node) < 0;
1428
1429               /* Save info about DR in the hash table.  */
1430               if (!LOOP_VINFO_PEELING_HTAB (loop_vinfo))
1431                 LOOP_VINFO_PEELING_HTAB (loop_vinfo)
1432                   = new hash_table<peel_info_hasher> (1);
1433
1434               vectype = STMT_VINFO_VECTYPE (stmt_info);
1435               nelements = TYPE_VECTOR_SUBPARTS (vectype);
1436               mis = DR_MISALIGNMENT (dr) / GET_MODE_SIZE (TYPE_MODE (
1437                                                 TREE_TYPE (DR_REF (dr))));
1438               npeel_tmp = (negative
1439                            ? (mis - nelements) : (nelements - mis))
1440                   & (nelements - 1);
1441
1442               /* For multiple types, it is possible that the bigger type access
1443                  will have more than one peeling option.  E.g., a loop with two
1444                  types: one of size (vector size / 4), and the other one of
1445                  size (vector size / 8).  Vectorization factor will 8.  If both
1446                  access are misaligned by 3, the first one needs one scalar
1447                  iteration to be aligned, and the second one needs 5.  But the
1448                  the first one will be aligned also by peeling 5 scalar
1449                  iterations, and in that case both accesses will be aligned.
1450                  Hence, except for the immediate peeling amount, we also want
1451                  to try to add full vector size, while we don't exceed
1452                  vectorization factor.
1453                  We do this automtically for cost model, since we calculate cost
1454                  for every peeling option.  */
1455               if (unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo)))
1456                 possible_npeel_number = vf /nelements;
1457
1458               /* Handle the aligned case. We may decide to align some other
1459                  access, making DR unaligned.  */
1460               if (DR_MISALIGNMENT (dr) == 0)
1461                 {
1462                   npeel_tmp = 0;
1463                   if (unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo)))
1464                     possible_npeel_number++;
1465                 }
1466
1467               for (j = 0; j < possible_npeel_number; j++)
1468                 {
1469                   gcc_assert (npeel_tmp <= vf);
1470                   vect_peeling_hash_insert (loop_vinfo, dr, npeel_tmp);
1471                   npeel_tmp += nelements;
1472                 }
1473
1474               all_misalignments_unknown = false;
1475               /* Data-ref that was chosen for the case that all the
1476                  misalignments are unknown is not relevant anymore, since we
1477                  have a data-ref with known alignment.  */
1478               dr0 = NULL;
1479             }
1480           else
1481             {
1482               /* If we don't know any misalignment values, we prefer
1483                  peeling for data-ref that has the maximum number of data-refs
1484                  with the same alignment, unless the target prefers to align
1485                  stores over load.  */
1486               if (all_misalignments_unknown)
1487                 {
1488                   unsigned same_align_drs
1489                     = STMT_VINFO_SAME_ALIGN_REFS (stmt_info).length ();
1490                   if (!dr0
1491                       || same_align_drs_max < same_align_drs)
1492                     {
1493                       same_align_drs_max = same_align_drs;
1494                       dr0 = dr;
1495                     }
1496                   /* For data-refs with the same number of related
1497                      accesses prefer the one where the misalign
1498                      computation will be invariant in the outermost loop.  */
1499                   else if (same_align_drs_max == same_align_drs)
1500                     {
1501                       struct loop *ivloop0, *ivloop;
1502                       ivloop0 = outermost_invariant_loop_for_expr
1503                           (loop, DR_BASE_ADDRESS (dr0));
1504                       ivloop = outermost_invariant_loop_for_expr
1505                           (loop, DR_BASE_ADDRESS (dr));
1506                       if ((ivloop && !ivloop0)
1507                           || (ivloop && ivloop0
1508                               && flow_loop_nested_p (ivloop, ivloop0)))
1509                         dr0 = dr;
1510                     }
1511
1512                   if (!first_store && DR_IS_WRITE (dr))
1513                     first_store = dr;
1514                 }
1515
1516               /* If there are both known and unknown misaligned accesses in the
1517                  loop, we choose peeling amount according to the known
1518                  accesses.  */
1519               if (!supportable_dr_alignment)
1520                 {
1521                   dr0 = dr;
1522                   if (!first_store && DR_IS_WRITE (dr))
1523                     first_store = dr;
1524                 }
1525             }
1526         }
1527       else
1528         {
1529           if (!aligned_access_p (dr))
1530             {
1531               if (dump_enabled_p ())
1532                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1533                                  "vector alignment may not be reachable\n");
1534               break;
1535             }
1536         }
1537     }
1538
1539   /* Check if we can possibly peel the loop.  */
1540   if (!vect_can_advance_ivs_p (loop_vinfo)
1541       || !slpeel_can_duplicate_loop_p (loop, single_exit (loop)))
1542     do_peeling = false;
1543
1544   /* If we don't know how many times the peeling loop will run
1545      assume it will run VF-1 times and disable peeling if the remaining
1546      iters are less than the vectorization factor.  */
1547   if (do_peeling
1548       && all_misalignments_unknown
1549       && LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1550       && (LOOP_VINFO_INT_NITERS (loop_vinfo)
1551           < 2 * (unsigned) LOOP_VINFO_VECT_FACTOR (loop_vinfo) - 1))
1552     do_peeling = false;
1553
1554   if (do_peeling
1555       && all_misalignments_unknown
1556       && vect_supportable_dr_alignment (dr0, false))
1557     {
1558       /* Check if the target requires to prefer stores over loads, i.e., if
1559          misaligned stores are more expensive than misaligned loads (taking
1560          drs with same alignment into account).  */
1561       if (first_store && DR_IS_READ (dr0))
1562         {
1563           unsigned int load_inside_cost = 0, load_outside_cost = 0;
1564           unsigned int store_inside_cost = 0, store_outside_cost = 0;
1565           unsigned int load_inside_penalty = 0, load_outside_penalty = 0;
1566           unsigned int store_inside_penalty = 0, store_outside_penalty = 0;
1567           stmt_vector_for_cost dummy;
1568           dummy.create (2);
1569
1570           vect_get_data_access_cost (dr0, &load_inside_cost, &load_outside_cost,
1571                                      &dummy);
1572           vect_get_data_access_cost (first_store, &store_inside_cost,
1573                                      &store_outside_cost, &dummy);
1574
1575           dummy.release ();
1576
1577           /* Calculate the penalty for leaving FIRST_STORE unaligned (by
1578              aligning the load DR0).  */
1579           load_inside_penalty = store_inside_cost;
1580           load_outside_penalty = store_outside_cost;
1581           for (i = 0;
1582                STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (
1583                           DR_STMT (first_store))).iterate (i, &dr);
1584                i++)
1585             if (DR_IS_READ (dr))
1586               {
1587                 load_inside_penalty += load_inside_cost;
1588                 load_outside_penalty += load_outside_cost;
1589               }
1590             else
1591               {
1592                 load_inside_penalty += store_inside_cost;
1593                 load_outside_penalty += store_outside_cost;
1594               }
1595
1596           /* Calculate the penalty for leaving DR0 unaligned (by
1597              aligning the FIRST_STORE).  */
1598           store_inside_penalty = load_inside_cost;
1599           store_outside_penalty = load_outside_cost;
1600           for (i = 0;
1601                STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (
1602                       DR_STMT (dr0))).iterate (i, &dr);
1603                i++)
1604             if (DR_IS_READ (dr))
1605               {
1606                 store_inside_penalty += load_inside_cost;
1607                 store_outside_penalty += load_outside_cost;
1608               }
1609             else
1610               {
1611                 store_inside_penalty += store_inside_cost;
1612                 store_outside_penalty += store_outside_cost;
1613               }
1614
1615           if (load_inside_penalty > store_inside_penalty
1616               || (load_inside_penalty == store_inside_penalty
1617                   && load_outside_penalty > store_outside_penalty))
1618             dr0 = first_store;
1619         }
1620
1621       /* In case there are only loads with different unknown misalignments, use
1622          peeling only if it may help to align other accesses in the loop.  */
1623       if (!first_store
1624           && !STMT_VINFO_SAME_ALIGN_REFS (
1625                   vinfo_for_stmt (DR_STMT (dr0))).length ()
1626           && vect_supportable_dr_alignment (dr0, false)
1627               != dr_unaligned_supported)
1628         do_peeling = false;
1629     }
1630
1631   if (do_peeling && !dr0)
1632     {
1633       /* Peeling is possible, but there is no data access that is not supported
1634          unless aligned. So we try to choose the best possible peeling.  */
1635
1636       /* We should get here only if there are drs with known misalignment.  */
1637       gcc_assert (!all_misalignments_unknown);
1638
1639       /* Choose the best peeling from the hash table.  */
1640       dr0 = vect_peeling_hash_choose_best_peeling (loop_vinfo, &npeel,
1641                                                    &body_cost_vec);
1642       if (!dr0 || !npeel)
1643         do_peeling = false;
1644
1645       /* If peeling by npeel will result in a remaining loop not iterating
1646          enough to be vectorized then do not peel.  */
1647       if (do_peeling
1648           && LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1649           && (LOOP_VINFO_INT_NITERS (loop_vinfo)
1650               < LOOP_VINFO_VECT_FACTOR (loop_vinfo) + npeel))
1651         do_peeling = false;
1652     }
1653
1654   if (do_peeling)
1655     {
1656       stmt = DR_STMT (dr0);
1657       stmt_info = vinfo_for_stmt (stmt);
1658       vectype = STMT_VINFO_VECTYPE (stmt_info);
1659       nelements = TYPE_VECTOR_SUBPARTS (vectype);
1660
1661       if (known_alignment_for_access_p (dr0))
1662         {
1663           bool negative = tree_int_cst_compare (DR_STEP (dr0),
1664                                                 size_zero_node) < 0;
1665           if (!npeel)
1666             {
1667               /* Since it's known at compile time, compute the number of
1668                  iterations in the peeled loop (the peeling factor) for use in
1669                  updating DR_MISALIGNMENT values.  The peeling factor is the
1670                  vectorization factor minus the misalignment as an element
1671                  count.  */
1672               mis = DR_MISALIGNMENT (dr0);
1673               mis /= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr0))));
1674               npeel = ((negative ? mis - nelements : nelements - mis)
1675                        & (nelements - 1));
1676             }
1677
1678           /* For interleaved data access every iteration accesses all the
1679              members of the group, therefore we divide the number of iterations
1680              by the group size.  */
1681           stmt_info = vinfo_for_stmt (DR_STMT (dr0));
1682           if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
1683             npeel /= GROUP_SIZE (stmt_info);
1684
1685           if (dump_enabled_p ())
1686             dump_printf_loc (MSG_NOTE, vect_location,
1687                              "Try peeling by %d\n", npeel);
1688         }
1689
1690       /* Ensure that all data refs can be vectorized after the peel.  */
1691       FOR_EACH_VEC_ELT (datarefs, i, dr)
1692         {
1693           int save_misalignment;
1694
1695           if (dr == dr0)
1696             continue;
1697
1698           stmt = DR_STMT (dr);
1699           stmt_info = vinfo_for_stmt (stmt);
1700           /* For interleaving, only the alignment of the first access
1701             matters.  */
1702           if (STMT_VINFO_GROUPED_ACCESS (stmt_info)
1703               && GROUP_FIRST_ELEMENT (stmt_info) != stmt)
1704             continue;
1705
1706           /* Strided loads perform only component accesses, alignment is
1707              irrelevant for them.  */
1708           if (STMT_VINFO_STRIDE_LOAD_P (stmt_info))
1709             continue;
1710
1711           save_misalignment = DR_MISALIGNMENT (dr);
1712           vect_update_misalignment_for_peel (dr, dr0, npeel);
1713           supportable_dr_alignment = vect_supportable_dr_alignment (dr, false);
1714           SET_DR_MISALIGNMENT (dr, save_misalignment);
1715
1716           if (!supportable_dr_alignment)
1717             {
1718               do_peeling = false;
1719               break;
1720             }
1721         }
1722
1723       if (do_peeling && known_alignment_for_access_p (dr0) && npeel == 0)
1724         {
1725           stat = vect_verify_datarefs_alignment (loop_vinfo, NULL);
1726           if (!stat)
1727             do_peeling = false;
1728           else
1729             {
1730               body_cost_vec.release ();
1731               return stat;
1732             }
1733         }
1734
1735       if (do_peeling)
1736         {
1737           unsigned max_allowed_peel
1738             = PARAM_VALUE (PARAM_VECT_MAX_PEELING_FOR_ALIGNMENT);
1739           if (max_allowed_peel != (unsigned)-1)
1740             {
1741               unsigned max_peel = npeel;
1742               if (max_peel == 0)
1743                 {
1744                   gimple dr_stmt = DR_STMT (dr0);
1745                   stmt_vec_info vinfo = vinfo_for_stmt (dr_stmt);
1746                   tree vtype = STMT_VINFO_VECTYPE (vinfo);
1747                   max_peel = TYPE_VECTOR_SUBPARTS (vtype) - 1;
1748                 }
1749               if (max_peel > max_allowed_peel)
1750                 {
1751                   do_peeling = false;
1752                   if (dump_enabled_p ())
1753                     dump_printf_loc (MSG_NOTE, vect_location,
1754                         "Disable peeling, max peels reached: %d\n", max_peel);
1755                 }
1756             }
1757         }
1758
1759       if (do_peeling)
1760         {
1761           /* (1.2) Update the DR_MISALIGNMENT of each data reference DR_i.
1762              If the misalignment of DR_i is identical to that of dr0 then set
1763              DR_MISALIGNMENT (DR_i) to zero.  If the misalignment of DR_i and
1764              dr0 are known at compile time then increment DR_MISALIGNMENT (DR_i)
1765              by the peeling factor times the element size of DR_i (MOD the
1766              vectorization factor times the size).  Otherwise, the
1767              misalignment of DR_i must be set to unknown.  */
1768           FOR_EACH_VEC_ELT (datarefs, i, dr)
1769             if (dr != dr0)
1770               vect_update_misalignment_for_peel (dr, dr0, npeel);
1771
1772           LOOP_VINFO_UNALIGNED_DR (loop_vinfo) = dr0;
1773           if (npeel)
1774             LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) = npeel;
1775           else
1776             LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo)
1777               = DR_MISALIGNMENT (dr0);
1778           SET_DR_MISALIGNMENT (dr0, 0);
1779           if (dump_enabled_p ())
1780             {
1781               dump_printf_loc (MSG_NOTE, vect_location,
1782                                "Alignment of access forced using peeling.\n");
1783               dump_printf_loc (MSG_NOTE, vect_location,
1784                                "Peeling for alignment will be applied.\n");
1785             }
1786           /* The inside-loop cost will be accounted for in vectorizable_load
1787              and vectorizable_store correctly with adjusted alignments.
1788              Drop the body_cst_vec on the floor here.  */
1789           body_cost_vec.release ();
1790
1791           stat = vect_verify_datarefs_alignment (loop_vinfo, NULL);
1792           gcc_assert (stat);
1793           return stat;
1794         }
1795     }
1796
1797   body_cost_vec.release ();
1798
1799   /* (2) Versioning to force alignment.  */
1800
1801   /* Try versioning if:
1802      1) optimize loop for speed
1803      2) there is at least one unsupported misaligned data ref with an unknown
1804         misalignment, and
1805      3) all misaligned data refs with a known misalignment are supported, and
1806      4) the number of runtime alignment checks is within reason.  */
1807
1808   do_versioning =
1809         optimize_loop_nest_for_speed_p (loop)
1810         && (!loop->inner); /* FORNOW */
1811
1812   if (do_versioning)
1813     {
1814       FOR_EACH_VEC_ELT (datarefs, i, dr)
1815         {
1816           stmt = DR_STMT (dr);
1817           stmt_info = vinfo_for_stmt (stmt);
1818
1819           /* For interleaving, only the alignment of the first access
1820              matters.  */
1821           if (aligned_access_p (dr)
1822               || (STMT_VINFO_GROUPED_ACCESS (stmt_info)
1823                   && GROUP_FIRST_ELEMENT (stmt_info) != stmt))
1824             continue;
1825
1826           /* Strided loads perform only component accesses, alignment is
1827              irrelevant for them.  */
1828           if (STMT_VINFO_STRIDE_LOAD_P (stmt_info))
1829             continue;
1830
1831           supportable_dr_alignment = vect_supportable_dr_alignment (dr, false);
1832
1833           if (!supportable_dr_alignment)
1834             {
1835               gimple stmt;
1836               int mask;
1837               tree vectype;
1838
1839               if (known_alignment_for_access_p (dr)
1840                   || LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).length ()
1841                      >= (unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS))
1842                 {
1843                   do_versioning = false;
1844                   break;
1845                 }
1846
1847               stmt = DR_STMT (dr);
1848               vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
1849               gcc_assert (vectype);
1850
1851               /* The rightmost bits of an aligned address must be zeros.
1852                  Construct the mask needed for this test.  For example,
1853                  GET_MODE_SIZE for the vector mode V4SI is 16 bytes so the
1854                  mask must be 15 = 0xf. */
1855               mask = GET_MODE_SIZE (TYPE_MODE (vectype)) - 1;
1856
1857               /* FORNOW: use the same mask to test all potentially unaligned
1858                  references in the loop.  The vectorizer currently supports
1859                  a single vector size, see the reference to
1860                  GET_MODE_NUNITS (TYPE_MODE (vectype)) where the
1861                  vectorization factor is computed.  */
1862               gcc_assert (!LOOP_VINFO_PTR_MASK (loop_vinfo)
1863                           || LOOP_VINFO_PTR_MASK (loop_vinfo) == mask);
1864               LOOP_VINFO_PTR_MASK (loop_vinfo) = mask;
1865               LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).safe_push (
1866                       DR_STMT (dr));
1867             }
1868         }
1869
1870       /* Versioning requires at least one misaligned data reference.  */
1871       if (!LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo))
1872         do_versioning = false;
1873       else if (!do_versioning)
1874         LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).truncate (0);
1875     }
1876
1877   if (do_versioning)
1878     {
1879       vec<gimple> may_misalign_stmts
1880         = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo);
1881       gimple stmt;
1882
1883       /* It can now be assumed that the data references in the statements
1884          in LOOP_VINFO_MAY_MISALIGN_STMTS will be aligned in the version
1885          of the loop being vectorized.  */
1886       FOR_EACH_VEC_ELT (may_misalign_stmts, i, stmt)
1887         {
1888           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1889           dr = STMT_VINFO_DATA_REF (stmt_info);
1890           SET_DR_MISALIGNMENT (dr, 0);
1891           if (dump_enabled_p ())
1892             dump_printf_loc (MSG_NOTE, vect_location,
1893                              "Alignment of access forced using versioning.\n");
1894         }
1895
1896       if (dump_enabled_p ())
1897         dump_printf_loc (MSG_NOTE, vect_location,
1898                          "Versioning for alignment will be applied.\n");
1899
1900       /* Peeling and versioning can't be done together at this time.  */
1901       gcc_assert (! (do_peeling && do_versioning));
1902
1903       stat = vect_verify_datarefs_alignment (loop_vinfo, NULL);
1904       gcc_assert (stat);
1905       return stat;
1906     }
1907
1908   /* This point is reached if neither peeling nor versioning is being done.  */
1909   gcc_assert (! (do_peeling || do_versioning));
1910
1911   stat = vect_verify_datarefs_alignment (loop_vinfo, NULL);
1912   return stat;
1913 }
1914
1915
1916 /* Function vect_find_same_alignment_drs.
1917
1918    Update group and alignment relations according to the chosen
1919    vectorization factor.  */
1920
1921 static void
1922 vect_find_same_alignment_drs (struct data_dependence_relation *ddr,
1923                               loop_vec_info loop_vinfo)
1924 {
1925   unsigned int i;
1926   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1927   int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1928   struct data_reference *dra = DDR_A (ddr);
1929   struct data_reference *drb = DDR_B (ddr);
1930   stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
1931   stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
1932   int dra_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dra))));
1933   int drb_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (drb))));
1934   lambda_vector dist_v;
1935   unsigned int loop_depth;
1936
1937   if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
1938     return;
1939
1940   if (dra == drb)
1941     return;
1942
1943   if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
1944     return;
1945
1946   /* Loop-based vectorization and known data dependence.  */
1947   if (DDR_NUM_DIST_VECTS (ddr) == 0)
1948     return;
1949
1950   /* Data-dependence analysis reports a distance vector of zero
1951      for data-references that overlap only in the first iteration
1952      but have different sign step (see PR45764).
1953      So as a sanity check require equal DR_STEP.  */
1954   if (!operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))
1955     return;
1956
1957   loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr));
1958   FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
1959     {
1960       int dist = dist_v[loop_depth];
1961
1962       if (dump_enabled_p ())
1963         dump_printf_loc (MSG_NOTE, vect_location,
1964                          "dependence distance  = %d.\n", dist);
1965
1966       /* Same loop iteration.  */
1967       if (dist == 0
1968           || (dist % vectorization_factor == 0 && dra_size == drb_size))
1969         {
1970           /* Two references with distance zero have the same alignment.  */
1971           STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a).safe_push (drb);
1972           STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b).safe_push (dra);
1973           if (dump_enabled_p ())
1974             {
1975               dump_printf_loc (MSG_NOTE, vect_location,
1976                                "accesses have the same alignment.\n");
1977               dump_printf (MSG_NOTE,
1978                            "dependence distance modulo vf == 0 between ");
1979               dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
1980               dump_printf (MSG_NOTE,  " and ");
1981               dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
1982               dump_printf (MSG_NOTE, "\n");
1983             }
1984         }
1985     }
1986 }
1987
1988
1989 /* Function vect_analyze_data_refs_alignment
1990
1991    Analyze the alignment of the data-references in the loop.
1992    Return FALSE if a data reference is found that cannot be vectorized.  */
1993
1994 bool
1995 vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo,
1996                                   bb_vec_info bb_vinfo)
1997 {
1998   if (dump_enabled_p ())
1999     dump_printf_loc (MSG_NOTE, vect_location,
2000                      "=== vect_analyze_data_refs_alignment ===\n");
2001
2002   /* Mark groups of data references with same alignment using
2003      data dependence information.  */
2004   if (loop_vinfo)
2005     {
2006       vec<ddr_p> ddrs = LOOP_VINFO_DDRS (loop_vinfo);
2007       struct data_dependence_relation *ddr;
2008       unsigned int i;
2009
2010       FOR_EACH_VEC_ELT (ddrs, i, ddr)
2011         vect_find_same_alignment_drs (ddr, loop_vinfo);
2012     }
2013
2014   if (!vect_compute_data_refs_alignment (loop_vinfo, bb_vinfo))
2015     {
2016       if (dump_enabled_p ())
2017         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2018                          "not vectorized: can't calculate alignment "
2019                          "for data ref.\n");
2020       return false;
2021     }
2022
2023   return true;
2024 }
2025
2026
2027 /* Analyze groups of accesses: check that DR belongs to a group of
2028    accesses of legal size, step, etc.  Detect gaps, single element
2029    interleaving, and other special cases. Set grouped access info.
2030    Collect groups of strided stores for further use in SLP analysis.  */
2031
2032 static bool
2033 vect_analyze_group_access (struct data_reference *dr)
2034 {
2035   tree step = DR_STEP (dr);
2036   tree scalar_type = TREE_TYPE (DR_REF (dr));
2037   HOST_WIDE_INT type_size = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type));
2038   gimple stmt = DR_STMT (dr);
2039   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2040   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2041   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
2042   HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
2043   HOST_WIDE_INT groupsize, last_accessed_element = 1;
2044   bool slp_impossible = false;
2045   struct loop *loop = NULL;
2046
2047   if (loop_vinfo)
2048     loop = LOOP_VINFO_LOOP (loop_vinfo);
2049
2050   /* For interleaving, GROUPSIZE is STEP counted in elements, i.e., the
2051      size of the interleaving group (including gaps).  */
2052   groupsize = absu_hwi (dr_step) / type_size;
2053
2054   /* Not consecutive access is possible only if it is a part of interleaving.  */
2055   if (!GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
2056     {
2057       /* Check if it this DR is a part of interleaving, and is a single
2058          element of the group that is accessed in the loop.  */
2059
2060       /* Gaps are supported only for loads. STEP must be a multiple of the type
2061          size.  The size of the group must be a power of 2.  */
2062       if (DR_IS_READ (dr)
2063           && (dr_step % type_size) == 0
2064           && groupsize > 0
2065           && exact_log2 (groupsize) != -1)
2066         {
2067           GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) = stmt;
2068           GROUP_SIZE (vinfo_for_stmt (stmt)) = groupsize;
2069           if (dump_enabled_p ())
2070             {
2071               dump_printf_loc (MSG_NOTE, vect_location,
2072                                "Detected single element interleaving ");
2073               dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr));
2074               dump_printf (MSG_NOTE, " step ");
2075               dump_generic_expr (MSG_NOTE, TDF_SLIM, step);
2076               dump_printf (MSG_NOTE, "\n");
2077             }
2078
2079           if (loop_vinfo)
2080             {
2081               if (dump_enabled_p ())
2082                 dump_printf_loc (MSG_NOTE, vect_location,
2083                                  "Data access with gaps requires scalar "
2084                                  "epilogue loop\n");
2085               if (loop->inner)
2086                 {
2087                   if (dump_enabled_p ())
2088                     dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2089                                      "Peeling for outer loop is not"
2090                                      " supported\n");
2091                   return false;
2092                 }
2093
2094               LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo) = true;
2095             }
2096
2097           return true;
2098         }
2099
2100       if (dump_enabled_p ())
2101         {
2102           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2103                            "not consecutive access ");
2104           dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
2105           dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
2106         }
2107
2108       if (bb_vinfo)
2109         {
2110           /* Mark the statement as unvectorizable.  */
2111           STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) = false;
2112           return true;
2113         }
2114
2115       return false;
2116     }
2117
2118   if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) == stmt)
2119     {
2120       /* First stmt in the interleaving chain. Check the chain.  */
2121       gimple next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt));
2122       struct data_reference *data_ref = dr;
2123       unsigned int count = 1;
2124       tree prev_init = DR_INIT (data_ref);
2125       gimple prev = stmt;
2126       HOST_WIDE_INT diff, gaps = 0;
2127       unsigned HOST_WIDE_INT count_in_bytes;
2128
2129       while (next)
2130         {
2131           /* Skip same data-refs.  In case that two or more stmts share
2132              data-ref (supported only for loads), we vectorize only the first
2133              stmt, and the rest get their vectorized loads from the first
2134              one.  */
2135           if (!tree_int_cst_compare (DR_INIT (data_ref),
2136                                      DR_INIT (STMT_VINFO_DATA_REF (
2137                                                    vinfo_for_stmt (next)))))
2138             {
2139               if (DR_IS_WRITE (data_ref))
2140                 {
2141                   if (dump_enabled_p ())
2142                     dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2143                                      "Two store stmts share the same dr.\n");
2144                   return false;
2145                 }
2146
2147               /* For load use the same data-ref load.  */
2148               GROUP_SAME_DR_STMT (vinfo_for_stmt (next)) = prev;
2149
2150               prev = next;
2151               next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next));
2152               continue;
2153             }
2154
2155           prev = next;
2156           data_ref = STMT_VINFO_DATA_REF (vinfo_for_stmt (next));
2157
2158           /* All group members have the same STEP by construction.  */
2159           gcc_checking_assert (operand_equal_p (DR_STEP (data_ref), step, 0));
2160
2161           /* Check that the distance between two accesses is equal to the type
2162              size. Otherwise, we have gaps.  */
2163           diff = (TREE_INT_CST_LOW (DR_INIT (data_ref))
2164                   - TREE_INT_CST_LOW (prev_init)) / type_size;
2165           if (diff != 1)
2166             {
2167               /* FORNOW: SLP of accesses with gaps is not supported.  */
2168               slp_impossible = true;
2169               if (DR_IS_WRITE (data_ref))
2170                 {
2171                   if (dump_enabled_p ())
2172                     dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2173                                      "interleaved store with gaps\n");
2174                   return false;
2175                 }
2176
2177               gaps += diff - 1;
2178             }
2179
2180           last_accessed_element += diff;
2181
2182           /* Store the gap from the previous member of the group. If there is no
2183              gap in the access, GROUP_GAP is always 1.  */
2184           GROUP_GAP (vinfo_for_stmt (next)) = diff;
2185
2186           prev_init = DR_INIT (data_ref);
2187           next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next));
2188           /* Count the number of data-refs in the chain.  */
2189           count++;
2190         }
2191
2192       /* COUNT is the number of accesses found, we multiply it by the size of
2193          the type to get COUNT_IN_BYTES.  */
2194       count_in_bytes = type_size * count;
2195
2196       /* Check that the size of the interleaving (including gaps) is not
2197          greater than STEP.  */
2198       if (dr_step != 0
2199           && absu_hwi (dr_step) < count_in_bytes + gaps * type_size)
2200         {
2201           if (dump_enabled_p ())
2202             {
2203               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2204                                "interleaving size is greater than step for ");
2205               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
2206                                  DR_REF (dr));
2207               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
2208             }
2209           return false;
2210         }
2211
2212       /* Check that the size of the interleaving is equal to STEP for stores,
2213          i.e., that there are no gaps.  */
2214       if (dr_step != 0
2215           && absu_hwi (dr_step) != count_in_bytes)
2216         {
2217           if (DR_IS_READ (dr))
2218             {
2219               slp_impossible = true;
2220               /* There is a gap after the last load in the group. This gap is a
2221                  difference between the groupsize and the number of elements.
2222                  When there is no gap, this difference should be 0.  */
2223               GROUP_GAP (vinfo_for_stmt (stmt)) = groupsize - count;
2224             }
2225           else
2226             {
2227               if (dump_enabled_p ())
2228                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2229                                  "interleaved store with gaps\n");
2230               return false;
2231             }
2232         }
2233
2234       /* Check that STEP is a multiple of type size.  */
2235       if (dr_step != 0
2236           && (dr_step % type_size) != 0)
2237         {
2238           if (dump_enabled_p ())
2239             {
2240               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2241                                "step is not a multiple of type size: step ");
2242               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, step);
2243               dump_printf (MSG_MISSED_OPTIMIZATION, " size ");
2244               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
2245                                  TYPE_SIZE_UNIT (scalar_type));
2246               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
2247             }
2248           return false;
2249         }
2250
2251       if (groupsize == 0)
2252         groupsize = count;
2253
2254       GROUP_SIZE (vinfo_for_stmt (stmt)) = groupsize;
2255       if (dump_enabled_p ())
2256         dump_printf_loc (MSG_NOTE, vect_location,
2257                          "Detected interleaving of size %d\n", (int)groupsize);
2258
2259       /* SLP: create an SLP data structure for every interleaving group of
2260          stores for further analysis in vect_analyse_slp.  */
2261       if (DR_IS_WRITE (dr) && !slp_impossible)
2262         {
2263           if (loop_vinfo)
2264             LOOP_VINFO_GROUPED_STORES (loop_vinfo).safe_push (stmt);
2265           if (bb_vinfo)
2266             BB_VINFO_GROUPED_STORES (bb_vinfo).safe_push (stmt);
2267         }
2268
2269       /* There is a gap in the end of the group.  */
2270       if (groupsize - last_accessed_element > 0 && loop_vinfo)
2271         {
2272           if (dump_enabled_p ())
2273             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2274                              "Data access with gaps requires scalar "
2275                              "epilogue loop\n");
2276           if (loop->inner)
2277             {
2278               if (dump_enabled_p ())
2279                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2280                                  "Peeling for outer loop is not supported\n");
2281               return false;
2282             }
2283
2284           LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo) = true;
2285         }
2286     }
2287
2288   return true;
2289 }
2290
2291
2292 /* Analyze the access pattern of the data-reference DR.
2293    In case of non-consecutive accesses call vect_analyze_group_access() to
2294    analyze groups of accesses.  */
2295
2296 static bool
2297 vect_analyze_data_ref_access (struct data_reference *dr)
2298 {
2299   tree step = DR_STEP (dr);
2300   tree scalar_type = TREE_TYPE (DR_REF (dr));
2301   gimple stmt = DR_STMT (dr);
2302   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2303   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2304   struct loop *loop = NULL;
2305
2306   if (loop_vinfo)
2307     loop = LOOP_VINFO_LOOP (loop_vinfo);
2308
2309   if (loop_vinfo && !step)
2310     {
2311       if (dump_enabled_p ())
2312         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2313                          "bad data-ref access in loop\n");
2314       return false;
2315     }
2316
2317   /* Allow invariant loads in not nested loops.  */
2318   if (loop_vinfo && integer_zerop (step))
2319     {
2320       GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) = NULL;
2321       if (nested_in_vect_loop_p (loop, stmt))
2322         {
2323           if (dump_enabled_p ())
2324             dump_printf_loc (MSG_NOTE, vect_location,
2325                              "zero step in inner loop of nest\n");
2326           return false;
2327         }
2328       return DR_IS_READ (dr);
2329     }
2330
2331   if (loop && nested_in_vect_loop_p (loop, stmt))
2332     {
2333       /* Interleaved accesses are not yet supported within outer-loop
2334         vectorization for references in the inner-loop.  */
2335       GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) = NULL;
2336
2337       /* For the rest of the analysis we use the outer-loop step.  */
2338       step = STMT_VINFO_DR_STEP (stmt_info);
2339       if (integer_zerop (step))
2340         {
2341           if (dump_enabled_p ())
2342             dump_printf_loc (MSG_NOTE, vect_location,
2343                              "zero step in outer loop.\n");
2344           if (DR_IS_READ (dr))
2345             return true;
2346           else
2347             return false;
2348         }
2349     }
2350
2351   /* Consecutive?  */
2352   if (TREE_CODE (step) == INTEGER_CST)
2353     {
2354       HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
2355       if (!tree_int_cst_compare (step, TYPE_SIZE_UNIT (scalar_type))
2356           || (dr_step < 0
2357               && !compare_tree_int (TYPE_SIZE_UNIT (scalar_type), -dr_step)))
2358         {
2359           /* Mark that it is not interleaving.  */
2360           GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) = NULL;
2361           return true;
2362         }
2363     }
2364
2365   if (loop && nested_in_vect_loop_p (loop, stmt))
2366     {
2367       if (dump_enabled_p ())
2368         dump_printf_loc (MSG_NOTE, vect_location,
2369                          "grouped access in outer loop.\n");
2370       return false;
2371     }
2372
2373   /* Assume this is a DR handled by non-constant strided load case.  */
2374   if (TREE_CODE (step) != INTEGER_CST)
2375     return STMT_VINFO_STRIDE_LOAD_P (stmt_info);
2376
2377   /* Not consecutive access - check if it's a part of interleaving group.  */
2378   return vect_analyze_group_access (dr);
2379 }
2380
2381
2382
2383 /*  A helper function used in the comparator function to sort data
2384     references.  T1 and T2 are two data references to be compared.
2385     The function returns -1, 0, or 1.  */
2386
2387 static int
2388 compare_tree (tree t1, tree t2)
2389 {
2390   int i, cmp;
2391   enum tree_code code;
2392   char tclass;
2393
2394   if (t1 == t2)
2395     return 0;
2396   if (t1 == NULL)
2397     return -1;
2398   if (t2 == NULL)
2399     return 1;
2400
2401
2402   if (TREE_CODE (t1) != TREE_CODE (t2))
2403     return TREE_CODE (t1) < TREE_CODE (t2) ? -1 : 1;
2404
2405   code = TREE_CODE (t1);
2406   switch (code)
2407     {
2408     /* For const values, we can just use hash values for comparisons.  */
2409     case INTEGER_CST:
2410     case REAL_CST:
2411     case FIXED_CST:
2412     case STRING_CST:
2413     case COMPLEX_CST:
2414     case VECTOR_CST:
2415       {
2416         hashval_t h1 = iterative_hash_expr (t1, 0);
2417         hashval_t h2 = iterative_hash_expr (t2, 0);
2418         if (h1 != h2)
2419           return h1 < h2 ? -1 : 1;
2420         break;
2421       }
2422
2423     case SSA_NAME:
2424       cmp = compare_tree (SSA_NAME_VAR (t1), SSA_NAME_VAR (t2));
2425       if (cmp != 0)
2426         return cmp;
2427
2428       if (SSA_NAME_VERSION (t1) != SSA_NAME_VERSION (t2))
2429         return SSA_NAME_VERSION (t1) < SSA_NAME_VERSION (t2) ? -1 : 1;
2430       break;
2431
2432     default:
2433       tclass = TREE_CODE_CLASS (code);
2434
2435       /* For var-decl, we could compare their UIDs.  */
2436       if (tclass == tcc_declaration)
2437         {
2438           if (DECL_UID (t1) != DECL_UID (t2))
2439             return DECL_UID (t1) < DECL_UID (t2) ? -1 : 1;
2440           break;
2441         }
2442
2443       /* For expressions with operands, compare their operands recursively.  */
2444       for (i = TREE_OPERAND_LENGTH (t1) - 1; i >= 0; --i)
2445         {
2446           cmp = compare_tree (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
2447           if (cmp != 0)
2448             return cmp;
2449         }
2450     }
2451
2452   return 0;
2453 }
2454
2455
2456 /* Compare two data-references DRA and DRB to group them into chunks
2457    suitable for grouping.  */
2458
2459 static int
2460 dr_group_sort_cmp (const void *dra_, const void *drb_)
2461 {
2462   data_reference_p dra = *(data_reference_p *)const_cast<void *>(dra_);
2463   data_reference_p drb = *(data_reference_p *)const_cast<void *>(drb_);
2464   int cmp;
2465
2466   /* Stabilize sort.  */
2467   if (dra == drb)
2468     return 0;
2469
2470   /* Ordering of DRs according to base.  */
2471   if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0))
2472     {
2473       cmp = compare_tree (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb));
2474       if (cmp != 0)
2475         return cmp;
2476     }
2477
2478   /* And according to DR_OFFSET.  */
2479   if (!dr_equal_offsets_p (dra, drb))
2480     {
2481       cmp = compare_tree (DR_OFFSET (dra), DR_OFFSET (drb));
2482       if (cmp != 0)
2483         return cmp;
2484     }
2485
2486   /* Put reads before writes.  */
2487   if (DR_IS_READ (dra) != DR_IS_READ (drb))
2488     return DR_IS_READ (dra) ? -1 : 1;
2489
2490   /* Then sort after access size.  */
2491   if (!operand_equal_p (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
2492                         TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))), 0))
2493     {
2494       cmp = compare_tree (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
2495                           TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
2496       if (cmp != 0)
2497         return cmp;
2498     }
2499
2500   /* And after step.  */
2501   if (!operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))
2502     {
2503       cmp = compare_tree (DR_STEP (dra), DR_STEP (drb));
2504       if (cmp != 0)
2505         return cmp;
2506     }
2507
2508   /* Then sort after DR_INIT.  In case of identical DRs sort after stmt UID.  */
2509   cmp = tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb));
2510   if (cmp == 0)
2511     return gimple_uid (DR_STMT (dra)) < gimple_uid (DR_STMT (drb)) ? -1 : 1;
2512   return cmp;
2513 }
2514
2515 /* Function vect_analyze_data_ref_accesses.
2516
2517    Analyze the access pattern of all the data references in the loop.
2518
2519    FORNOW: the only access pattern that is considered vectorizable is a
2520            simple step 1 (consecutive) access.
2521
2522    FORNOW: handle only arrays and pointer accesses.  */
2523
2524 bool
2525 vect_analyze_data_ref_accesses (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
2526 {
2527   unsigned int i;
2528   vec<data_reference_p> datarefs;
2529   struct data_reference *dr;
2530
2531   if (dump_enabled_p ())
2532     dump_printf_loc (MSG_NOTE, vect_location,
2533                      "=== vect_analyze_data_ref_accesses ===\n");
2534
2535   if (loop_vinfo)
2536     datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
2537   else
2538     datarefs = BB_VINFO_DATAREFS (bb_vinfo);
2539
2540   if (datarefs.is_empty ())
2541     return true;
2542
2543   /* Sort the array of datarefs to make building the interleaving chains
2544      linear.  Don't modify the original vector's order, it is needed for
2545      determining what dependencies are reversed.  */
2546   vec<data_reference_p> datarefs_copy = datarefs.copy ();
2547   datarefs_copy.qsort (dr_group_sort_cmp);
2548
2549   /* Build the interleaving chains.  */
2550   for (i = 0; i < datarefs_copy.length () - 1;)
2551     {
2552       data_reference_p dra = datarefs_copy[i];
2553       stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
2554       stmt_vec_info lastinfo = NULL;
2555       for (i = i + 1; i < datarefs_copy.length (); ++i)
2556         {
2557           data_reference_p drb = datarefs_copy[i];
2558           stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
2559
2560           /* ???  Imperfect sorting (non-compatible types, non-modulo
2561              accesses, same accesses) can lead to a group to be artificially
2562              split here as we don't just skip over those.  If it really
2563              matters we can push those to a worklist and re-iterate
2564              over them.  The we can just skip ahead to the next DR here.  */
2565
2566           /* Check that the data-refs have same first location (except init)
2567              and they are both either store or load (not load and store,
2568              not masked loads or stores).  */
2569           if (DR_IS_READ (dra) != DR_IS_READ (drb)
2570               || !operand_equal_p (DR_BASE_ADDRESS (dra),
2571                                    DR_BASE_ADDRESS (drb), 0)
2572               || !dr_equal_offsets_p (dra, drb)
2573               || !gimple_assign_single_p (DR_STMT (dra))
2574               || !gimple_assign_single_p (DR_STMT (drb)))
2575             break;
2576
2577           /* Check that the data-refs have the same constant size and step.  */
2578           tree sza = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra)));
2579           tree szb = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb)));
2580           if (!tree_fits_uhwi_p (sza)
2581               || !tree_fits_uhwi_p (szb)
2582               || !tree_int_cst_equal (sza, szb)
2583               || !tree_fits_shwi_p (DR_STEP (dra))
2584               || !tree_fits_shwi_p (DR_STEP (drb))
2585               || !tree_int_cst_equal (DR_STEP (dra), DR_STEP (drb)))
2586             break;
2587
2588           /* Do not place the same access in the interleaving chain twice.  */
2589           if (tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb)) == 0)
2590             break;
2591
2592           /* Check the types are compatible.
2593              ???  We don't distinguish this during sorting.  */
2594           if (!types_compatible_p (TREE_TYPE (DR_REF (dra)),
2595                                    TREE_TYPE (DR_REF (drb))))
2596             break;
2597
2598           /* Sorting has ensured that DR_INIT (dra) <= DR_INIT (drb).  */
2599           HOST_WIDE_INT init_a = TREE_INT_CST_LOW (DR_INIT (dra));
2600           HOST_WIDE_INT init_b = TREE_INT_CST_LOW (DR_INIT (drb));
2601           gcc_assert (init_a < init_b);
2602
2603           /* If init_b == init_a + the size of the type * k, we have an
2604              interleaving, and DRA is accessed before DRB.  */
2605           HOST_WIDE_INT type_size_a = tree_to_uhwi (sza);
2606           if ((init_b - init_a) % type_size_a != 0)
2607             break;
2608
2609           /* The step (if not zero) is greater than the difference between
2610              data-refs' inits.  This splits groups into suitable sizes.  */
2611           HOST_WIDE_INT step = tree_to_shwi (DR_STEP (dra));
2612           if (step != 0 && step <= (init_b - init_a))
2613             break;
2614
2615           if (dump_enabled_p ())
2616             {
2617               dump_printf_loc (MSG_NOTE, vect_location,
2618                                "Detected interleaving ");
2619               dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
2620               dump_printf (MSG_NOTE,  " and ");
2621               dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
2622               dump_printf (MSG_NOTE, "\n");
2623             }
2624
2625           /* Link the found element into the group list.  */
2626           if (!GROUP_FIRST_ELEMENT (stmtinfo_a))
2627             {
2628               GROUP_FIRST_ELEMENT (stmtinfo_a) = DR_STMT (dra);
2629               lastinfo = stmtinfo_a;
2630             }
2631           GROUP_FIRST_ELEMENT (stmtinfo_b) = DR_STMT (dra);
2632           GROUP_NEXT_ELEMENT (lastinfo) = DR_STMT (drb);
2633           lastinfo = stmtinfo_b;
2634         }
2635     }
2636
2637   FOR_EACH_VEC_ELT (datarefs_copy, i, dr)
2638     if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) 
2639         && !vect_analyze_data_ref_access (dr))
2640       {
2641         if (dump_enabled_p ())
2642           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2643                            "not vectorized: complicated access pattern.\n");
2644
2645         if (bb_vinfo)
2646           {
2647             /* Mark the statement as not vectorizable.  */
2648             STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) = false;
2649             continue;
2650           }
2651         else
2652           {
2653             datarefs_copy.release ();
2654             return false;
2655           }
2656       }
2657
2658   datarefs_copy.release ();
2659   return true;
2660 }
2661
2662
2663 /* Operator == between two dr_with_seg_len objects.
2664
2665    This equality operator is used to make sure two data refs
2666    are the same one so that we will consider to combine the
2667    aliasing checks of those two pairs of data dependent data
2668    refs.  */
2669
2670 static bool
2671 operator == (const dr_with_seg_len& d1,
2672              const dr_with_seg_len& d2)
2673 {
2674   return operand_equal_p (DR_BASE_ADDRESS (d1.dr),
2675                           DR_BASE_ADDRESS (d2.dr), 0)
2676            && compare_tree (d1.offset, d2.offset) == 0
2677            && compare_tree (d1.seg_len, d2.seg_len) == 0;
2678 }
2679
2680 /* Function comp_dr_with_seg_len_pair.
2681
2682    Comparison function for sorting objects of dr_with_seg_len_pair_t
2683    so that we can combine aliasing checks in one scan.  */
2684
2685 static int
2686 comp_dr_with_seg_len_pair (const void *p1_, const void *p2_)
2687 {
2688   const dr_with_seg_len_pair_t* p1 = (const dr_with_seg_len_pair_t *) p1_;
2689   const dr_with_seg_len_pair_t* p2 = (const dr_with_seg_len_pair_t *) p2_;
2690
2691   const dr_with_seg_len &p11 = p1->first,
2692                         &p12 = p1->second,
2693                         &p21 = p2->first,
2694                         &p22 = p2->second;
2695
2696   /* For DR pairs (a, b) and (c, d), we only consider to merge the alias checks
2697      if a and c have the same basic address snd step, and b and d have the same
2698      address and step.  Therefore, if any a&c or b&d don't have the same address
2699      and step, we don't care the order of those two pairs after sorting.  */
2700   int comp_res;
2701
2702   if ((comp_res = compare_tree (DR_BASE_ADDRESS (p11.dr),
2703                                 DR_BASE_ADDRESS (p21.dr))) != 0)
2704     return comp_res;
2705   if ((comp_res = compare_tree (DR_BASE_ADDRESS (p12.dr),
2706                                 DR_BASE_ADDRESS (p22.dr))) != 0)
2707     return comp_res;
2708   if ((comp_res = compare_tree (DR_STEP (p11.dr), DR_STEP (p21.dr))) != 0)
2709     return comp_res;
2710   if ((comp_res = compare_tree (DR_STEP (p12.dr), DR_STEP (p22.dr))) != 0)
2711     return comp_res;
2712   if ((comp_res = compare_tree (p11.offset, p21.offset)) != 0)
2713     return comp_res;
2714   if ((comp_res = compare_tree (p12.offset, p22.offset)) != 0)
2715     return comp_res;
2716
2717   return 0;
2718 }
2719
2720 /* Function vect_vfa_segment_size.
2721
2722    Create an expression that computes the size of segment
2723    that will be accessed for a data reference.  The functions takes into
2724    account that realignment loads may access one more vector.
2725
2726    Input:
2727      DR: The data reference.
2728      LENGTH_FACTOR: segment length to consider.
2729
2730    Return an expression whose value is the size of segment which will be
2731    accessed by DR.  */
2732
2733 static tree
2734 vect_vfa_segment_size (struct data_reference *dr, tree length_factor)
2735 {
2736   tree segment_length;
2737
2738   if (integer_zerop (DR_STEP (dr)))
2739     segment_length = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)));
2740   else
2741     segment_length = size_binop (MULT_EXPR,
2742                                  fold_convert (sizetype, DR_STEP (dr)),
2743                                  fold_convert (sizetype, length_factor));
2744
2745   if (vect_supportable_dr_alignment (dr, false)
2746         == dr_explicit_realign_optimized)
2747     {
2748       tree vector_size = TYPE_SIZE_UNIT
2749                           (STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr))));
2750
2751       segment_length = size_binop (PLUS_EXPR, segment_length, vector_size);
2752     }
2753   return segment_length;
2754 }
2755
2756 /* Function vect_prune_runtime_alias_test_list.
2757
2758    Prune a list of ddrs to be tested at run-time by versioning for alias.
2759    Merge several alias checks into one if possible.
2760    Return FALSE if resulting list of ddrs is longer then allowed by
2761    PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS, otherwise return TRUE.  */
2762
2763 bool
2764 vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo)
2765 {
2766   vec<ddr_p> may_alias_ddrs =
2767     LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo);
2768   vec<dr_with_seg_len_pair_t>& comp_alias_ddrs =
2769     LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo);
2770   int vect_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2771   tree scalar_loop_iters = LOOP_VINFO_NITERS (loop_vinfo);
2772
2773   ddr_p ddr;
2774   unsigned int i;
2775   tree length_factor;
2776
2777   if (dump_enabled_p ())
2778     dump_printf_loc (MSG_NOTE, vect_location,
2779                      "=== vect_prune_runtime_alias_test_list ===\n");
2780
2781   if (may_alias_ddrs.is_empty ())
2782     return true;
2783
2784   /* Basically, for each pair of dependent data refs store_ptr_0
2785      and load_ptr_0, we create an expression:
2786
2787      ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
2788      || (load_ptr_0 + load_segment_length_0) <= store_ptr_0))
2789
2790      for aliasing checks.  However, in some cases we can decrease
2791      the number of checks by combining two checks into one.  For
2792      example, suppose we have another pair of data refs store_ptr_0
2793      and load_ptr_1, and if the following condition is satisfied:
2794
2795      load_ptr_0 < load_ptr_1  &&
2796      load_ptr_1 - load_ptr_0 - load_segment_length_0 < store_segment_length_0
2797
2798      (this condition means, in each iteration of vectorized loop,
2799      the accessed memory of store_ptr_0 cannot be between the memory
2800      of load_ptr_0 and load_ptr_1.)
2801
2802      we then can use only the following expression to finish the
2803      alising checks between store_ptr_0 & load_ptr_0 and
2804      store_ptr_0 & load_ptr_1:
2805
2806      ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
2807      || (load_ptr_1 + load_segment_length_1 <= store_ptr_0))
2808
2809      Note that we only consider that load_ptr_0 and load_ptr_1 have the
2810      same basic address.  */
2811
2812   comp_alias_ddrs.create (may_alias_ddrs.length ());
2813
2814   /* First, we collect all data ref pairs for aliasing checks.  */
2815   FOR_EACH_VEC_ELT (may_alias_ddrs, i, ddr)
2816     {
2817       struct data_reference *dr_a, *dr_b;
2818       gimple dr_group_first_a, dr_group_first_b;
2819       tree segment_length_a, segment_length_b;
2820       gimple stmt_a, stmt_b;
2821
2822       dr_a = DDR_A (ddr);
2823       stmt_a = DR_STMT (DDR_A (ddr));
2824       dr_group_first_a = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_a));
2825       if (dr_group_first_a)
2826         {
2827           stmt_a = dr_group_first_a;
2828           dr_a = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt_a));
2829         }
2830
2831       dr_b = DDR_B (ddr);
2832       stmt_b = DR_STMT (DDR_B (ddr));
2833       dr_group_first_b = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_b));
2834       if (dr_group_first_b)
2835         {
2836           stmt_b = dr_group_first_b;
2837           dr_b = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt_b));
2838         }
2839
2840       if (!operand_equal_p (DR_STEP (dr_a), DR_STEP (dr_b), 0))
2841         length_factor = scalar_loop_iters;
2842       else
2843         length_factor = size_int (vect_factor);
2844       segment_length_a = vect_vfa_segment_size (dr_a, length_factor);
2845       segment_length_b = vect_vfa_segment_size (dr_b, length_factor);
2846
2847       dr_with_seg_len_pair_t dr_with_seg_len_pair
2848           (dr_with_seg_len (dr_a, segment_length_a),
2849            dr_with_seg_len (dr_b, segment_length_b));
2850
2851       if (compare_tree (DR_BASE_ADDRESS (dr_a), DR_BASE_ADDRESS (dr_b)) > 0)
2852         std::swap (dr_with_seg_len_pair.first, dr_with_seg_len_pair.second);
2853
2854       comp_alias_ddrs.safe_push (dr_with_seg_len_pair);
2855     }
2856
2857   /* Second, we sort the collected data ref pairs so that we can scan
2858      them once to combine all possible aliasing checks.  */
2859   comp_alias_ddrs.qsort (comp_dr_with_seg_len_pair);
2860
2861   /* Third, we scan the sorted dr pairs and check if we can combine
2862      alias checks of two neighbouring dr pairs.  */
2863   for (size_t i = 1; i < comp_alias_ddrs.length (); ++i)
2864     {
2865       /* Deal with two ddrs (dr_a1, dr_b1) and (dr_a2, dr_b2).  */
2866       dr_with_seg_len *dr_a1 = &comp_alias_ddrs[i-1].first,
2867                       *dr_b1 = &comp_alias_ddrs[i-1].second,
2868                       *dr_a2 = &comp_alias_ddrs[i].first,
2869                       *dr_b2 = &comp_alias_ddrs[i].second;
2870
2871       /* Remove duplicate data ref pairs.  */
2872       if (*dr_a1 == *dr_a2 && *dr_b1 == *dr_b2)
2873         {
2874           if (dump_enabled_p ())
2875             {
2876               dump_printf_loc (MSG_NOTE, vect_location,
2877                                "found equal ranges ");
2878               dump_generic_expr (MSG_NOTE, TDF_SLIM,
2879                                  DR_REF (dr_a1->dr));
2880               dump_printf (MSG_NOTE,  ", ");
2881               dump_generic_expr (MSG_NOTE, TDF_SLIM,
2882                                  DR_REF (dr_b1->dr));
2883               dump_printf (MSG_NOTE,  " and ");
2884               dump_generic_expr (MSG_NOTE, TDF_SLIM,
2885                                  DR_REF (dr_a2->dr));
2886               dump_printf (MSG_NOTE,  ", ");
2887               dump_generic_expr (MSG_NOTE, TDF_SLIM,
2888                                  DR_REF (dr_b2->dr));
2889               dump_printf (MSG_NOTE, "\n");
2890             }
2891
2892           comp_alias_ddrs.ordered_remove (i--);
2893           continue;
2894         }
2895
2896       if (*dr_a1 == *dr_a2 || *dr_b1 == *dr_b2)
2897         {
2898           /* We consider the case that DR_B1 and DR_B2 are same memrefs,
2899              and DR_A1 and DR_A2 are two consecutive memrefs.  */
2900           if (*dr_a1 == *dr_a2)
2901             {
2902               std::swap (dr_a1, dr_b1);
2903               std::swap (dr_a2, dr_b2);
2904             }
2905
2906           if (!operand_equal_p (DR_BASE_ADDRESS (dr_a1->dr),
2907                                 DR_BASE_ADDRESS (dr_a2->dr),
2908                                 0)
2909               || !tree_fits_shwi_p (dr_a1->offset)
2910               || !tree_fits_shwi_p (dr_a2->offset))
2911             continue;
2912
2913           HOST_WIDE_INT diff = (tree_to_shwi (dr_a2->offset)
2914                                 - tree_to_shwi (dr_a1->offset));
2915
2916
2917           /* Now we check if the following condition is satisfied:
2918
2919              DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
2920
2921              where DIFF = DR_A2->OFFSET - DR_A1->OFFSET.  However,
2922              SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we
2923              have to make a best estimation.  We can get the minimum value
2924              of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B,
2925              then either of the following two conditions can guarantee the
2926              one above:
2927
2928              1: DIFF <= MIN_SEG_LEN_B
2929              2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B
2930
2931              */
2932
2933           HOST_WIDE_INT  min_seg_len_b = (tree_fits_shwi_p (dr_b1->seg_len)
2934                                           ? tree_to_shwi (dr_b1->seg_len)
2935                                           : vect_factor);
2936
2937           if (diff <= min_seg_len_b
2938               || (tree_fits_shwi_p (dr_a1->seg_len)
2939                   && diff - tree_to_shwi (dr_a1->seg_len) < min_seg_len_b))
2940             {
2941               if (dump_enabled_p ())
2942                 {
2943                   dump_printf_loc (MSG_NOTE, vect_location,
2944                                    "merging ranges for ");
2945                   dump_generic_expr (MSG_NOTE, TDF_SLIM,
2946                                      DR_REF (dr_a1->dr));
2947                   dump_printf (MSG_NOTE,  ", ");
2948                   dump_generic_expr (MSG_NOTE, TDF_SLIM,
2949                                      DR_REF (dr_b1->dr));
2950                   dump_printf (MSG_NOTE,  " and ");
2951                   dump_generic_expr (MSG_NOTE, TDF_SLIM,
2952                                      DR_REF (dr_a2->dr));
2953                   dump_printf (MSG_NOTE,  ", ");
2954                   dump_generic_expr (MSG_NOTE, TDF_SLIM,
2955                                      DR_REF (dr_b2->dr));
2956                   dump_printf (MSG_NOTE, "\n");
2957                 }
2958
2959               dr_a1->seg_len = size_binop (PLUS_EXPR,
2960                                            dr_a2->seg_len, size_int (diff));
2961               comp_alias_ddrs.ordered_remove (i--);
2962             }
2963         }
2964     }
2965
2966   dump_printf_loc (MSG_NOTE, vect_location,
2967                    "improved number of alias checks from %d to %d\n",
2968                    may_alias_ddrs.length (), comp_alias_ddrs.length ());
2969   if ((int) comp_alias_ddrs.length () >
2970       PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS))
2971     return false;
2972
2973   return true;
2974 }
2975
2976 /* Check whether a non-affine read in stmt is suitable for gather load
2977    and if so, return a builtin decl for that operation.  */
2978
2979 tree
2980 vect_check_gather (gimple stmt, loop_vec_info loop_vinfo, tree *basep,
2981                    tree *offp, int *scalep)
2982 {
2983   HOST_WIDE_INT scale = 1, pbitpos, pbitsize;
2984   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2985   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2986   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
2987   tree offtype = NULL_TREE;
2988   tree decl, base, off;
2989   machine_mode pmode;
2990   int punsignedp, pvolatilep;
2991
2992   base = DR_REF (dr);
2993   /* For masked loads/stores, DR_REF (dr) is an artificial MEM_REF,
2994      see if we can use the def stmt of the address.  */
2995   if (is_gimple_call (stmt)
2996       && gimple_call_internal_p (stmt)
2997       && (gimple_call_internal_fn (stmt) == IFN_MASK_LOAD
2998           || gimple_call_internal_fn (stmt) == IFN_MASK_STORE)
2999       && TREE_CODE (base) == MEM_REF
3000       && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME
3001       && integer_zerop (TREE_OPERAND (base, 1))
3002       && !expr_invariant_in_loop_p (loop, TREE_OPERAND (base, 0)))
3003     {
3004       gimple def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (base, 0));
3005       if (is_gimple_assign (def_stmt)
3006           && gimple_assign_rhs_code (def_stmt) == ADDR_EXPR)
3007         base = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 0);
3008     }
3009
3010   /* The gather builtins need address of the form
3011      loop_invariant + vector * {1, 2, 4, 8}
3012      or
3013      loop_invariant + sign_extend (vector) * { 1, 2, 4, 8 }.
3014      Unfortunately DR_BASE_ADDRESS/DR_OFFSET can be a mixture
3015      of loop invariants/SSA_NAMEs defined in the loop, with casts,
3016      multiplications and additions in it.  To get a vector, we need
3017      a single SSA_NAME that will be defined in the loop and will
3018      contain everything that is not loop invariant and that can be
3019      vectorized.  The following code attempts to find such a preexistng
3020      SSA_NAME OFF and put the loop invariants into a tree BASE
3021      that can be gimplified before the loop.  */
3022   base = get_inner_reference (base, &pbitsize, &pbitpos, &off,
3023                               &pmode, &punsignedp, &pvolatilep, false);
3024   gcc_assert (base != NULL_TREE && (pbitpos % BITS_PER_UNIT) == 0);
3025
3026   if (TREE_CODE (base) == MEM_REF)
3027     {
3028       if (!integer_zerop (TREE_OPERAND (base, 1)))
3029         {
3030           if (off == NULL_TREE)
3031             {
3032               offset_int moff = mem_ref_offset (base);
3033               off = wide_int_to_tree (sizetype, moff);
3034             }
3035           else
3036             off = size_binop (PLUS_EXPR, off,
3037                               fold_convert (sizetype, TREE_OPERAND (base, 1)));
3038         }
3039       base = TREE_OPERAND (base, 0);
3040     }
3041   else
3042     base = build_fold_addr_expr (base);
3043
3044   if (off == NULL_TREE)
3045     off = size_zero_node;
3046
3047   /* If base is not loop invariant, either off is 0, then we start with just
3048      the constant offset in the loop invariant BASE and continue with base
3049      as OFF, otherwise give up.
3050      We could handle that case by gimplifying the addition of base + off
3051      into some SSA_NAME and use that as off, but for now punt.  */
3052   if (!expr_invariant_in_loop_p (loop, base))
3053     {
3054       if (!integer_zerop (off))
3055         return NULL_TREE;
3056       off = base;
3057       base = size_int (pbitpos / BITS_PER_UNIT);
3058     }
3059   /* Otherwise put base + constant offset into the loop invariant BASE
3060      and continue with OFF.  */
3061   else
3062     {
3063       base = fold_convert (sizetype, base);
3064       base = size_binop (PLUS_EXPR, base, size_int (pbitpos / BITS_PER_UNIT));
3065     }
3066
3067   /* OFF at this point may be either a SSA_NAME or some tree expression
3068      from get_inner_reference.  Try to peel off loop invariants from it
3069      into BASE as long as possible.  */
3070   STRIP_NOPS (off);
3071   while (offtype == NULL_TREE)
3072     {
3073       enum tree_code code;
3074       tree op0, op1, add = NULL_TREE;
3075
3076       if (TREE_CODE (off) == SSA_NAME)
3077         {
3078           gimple def_stmt = SSA_NAME_DEF_STMT (off);
3079
3080           if (expr_invariant_in_loop_p (loop, off))
3081             return NULL_TREE;
3082
3083           if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
3084             break;
3085
3086           op0 = gimple_assign_rhs1 (def_stmt);
3087           code = gimple_assign_rhs_code (def_stmt);
3088           op1 = gimple_assign_rhs2 (def_stmt);
3089         }
3090       else
3091         {
3092           if (get_gimple_rhs_class (TREE_CODE (off)) == GIMPLE_TERNARY_RHS)
3093             return NULL_TREE;
3094           code = TREE_CODE (off);
3095           extract_ops_from_tree (off, &code, &op0, &op1);
3096         }
3097       switch (code)
3098         {
3099         case POINTER_PLUS_EXPR:
3100         case PLUS_EXPR:
3101           if (expr_invariant_in_loop_p (loop, op0))
3102             {
3103               add = op0;
3104               off = op1;
3105             do_add:
3106               add = fold_convert (sizetype, add);
3107               if (scale != 1)
3108                 add = size_binop (MULT_EXPR, add, size_int (scale));
3109               base = size_binop (PLUS_EXPR, base, add);
3110               continue;
3111             }
3112           if (expr_invariant_in_loop_p (loop, op1))
3113             {
3114               add = op1;
3115               off = op0;
3116               goto do_add;
3117             }
3118           break;
3119         case MINUS_EXPR:
3120           if (expr_invariant_in_loop_p (loop, op1))
3121             {
3122               add = fold_convert (sizetype, op1);
3123               add = size_binop (MINUS_EXPR, size_zero_node, add);
3124               off = op0;
3125               goto do_add;
3126             }
3127           break;
3128         case MULT_EXPR:
3129           if (scale == 1 && tree_fits_shwi_p (op1))
3130             {
3131               scale = tree_to_shwi (op1);
3132               off = op0;
3133               continue;
3134             }
3135           break;
3136         case SSA_NAME:
3137           off = op0;
3138           continue;
3139         CASE_CONVERT:
3140           if (!POINTER_TYPE_P (TREE_TYPE (op0))
3141               && !INTEGRAL_TYPE_P (TREE_TYPE (op0)))
3142             break;
3143           if (TYPE_PRECISION (TREE_TYPE (op0))
3144               == TYPE_PRECISION (TREE_TYPE (off)))
3145             {
3146               off = op0;
3147               continue;
3148             }
3149           if (TYPE_PRECISION (TREE_TYPE (op0))
3150               < TYPE_PRECISION (TREE_TYPE (off)))
3151             {
3152               off = op0;
3153               offtype = TREE_TYPE (off);
3154               STRIP_NOPS (off);
3155               continue;
3156             }
3157           break;
3158         default:
3159           break;
3160         }
3161       break;
3162     }
3163
3164   /* If at the end OFF still isn't a SSA_NAME or isn't
3165      defined in the loop, punt.  */
3166   if (TREE_CODE (off) != SSA_NAME
3167       || expr_invariant_in_loop_p (loop, off))
3168     return NULL_TREE;
3169
3170   if (offtype == NULL_TREE)
3171     offtype = TREE_TYPE (off);
3172
3173   decl = targetm.vectorize.builtin_gather (STMT_VINFO_VECTYPE (stmt_info),
3174                                            offtype, scale);
3175   if (decl == NULL_TREE)
3176     return NULL_TREE;
3177
3178   if (basep)
3179     *basep = base;
3180   if (offp)
3181     *offp = off;
3182   if (scalep)
3183     *scalep = scale;
3184   return decl;
3185 }
3186
3187 /* Function vect_analyze_data_refs.
3188
3189   Find all the data references in the loop or basic block.
3190
3191    The general structure of the analysis of data refs in the vectorizer is as
3192    follows:
3193    1- vect_analyze_data_refs(loop/bb): call
3194       compute_data_dependences_for_loop/bb to find and analyze all data-refs
3195       in the loop/bb and their dependences.
3196    2- vect_analyze_dependences(): apply dependence testing using ddrs.
3197    3- vect_analyze_drs_alignment(): check that ref_stmt.alignment is ok.
3198    4- vect_analyze_drs_access(): check that ref_stmt.step is ok.
3199
3200 */
3201
3202 bool
3203 vect_analyze_data_refs (loop_vec_info loop_vinfo,
3204                         bb_vec_info bb_vinfo,
3205                         int *min_vf, unsigned *n_stmts)
3206 {
3207   struct loop *loop = NULL;
3208   basic_block bb = NULL;
3209   unsigned int i;
3210   vec<data_reference_p> datarefs;
3211   struct data_reference *dr;
3212   tree scalar_type;
3213
3214   if (dump_enabled_p ())
3215     dump_printf_loc (MSG_NOTE, vect_location,
3216                      "=== vect_analyze_data_refs ===\n");
3217
3218   if (loop_vinfo)
3219     {
3220       basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
3221
3222       loop = LOOP_VINFO_LOOP (loop_vinfo);
3223       datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
3224       if (!find_loop_nest (loop, &LOOP_VINFO_LOOP_NEST (loop_vinfo)))
3225         {
3226           if (dump_enabled_p ())
3227             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3228                              "not vectorized: loop contains function calls"
3229                              " or data references that cannot be analyzed\n");
3230           return false;
3231         }
3232
3233       for (i = 0; i < loop->num_nodes; i++)
3234         {
3235           gimple_stmt_iterator gsi;
3236
3237           for (gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
3238             {
3239               gimple stmt = gsi_stmt (gsi);
3240               if (is_gimple_debug (stmt))
3241                 continue;
3242               ++*n_stmts;
3243               if (!find_data_references_in_stmt (loop, stmt, &datarefs))
3244                 {
3245                   if (is_gimple_call (stmt) && loop->safelen)
3246                     {
3247                       tree fndecl = gimple_call_fndecl (stmt), op;
3248                       if (fndecl != NULL_TREE)
3249                         {
3250                           struct cgraph_node *node = cgraph_node::get (fndecl);
3251                           if (node != NULL && node->simd_clones != NULL)
3252                             {
3253                               unsigned int j, n = gimple_call_num_args (stmt);
3254                               for (j = 0; j < n; j++)
3255                                 {
3256                                   op = gimple_call_arg (stmt, j);
3257                                   if (DECL_P (op)
3258                                       || (REFERENCE_CLASS_P (op)
3259                                           && get_base_address (op)))
3260                                     break;
3261                                 }
3262                               op = gimple_call_lhs (stmt);
3263                               /* Ignore #pragma omp declare simd functions
3264                                  if they don't have data references in the
3265                                  call stmt itself.  */
3266                               if (j == n
3267                                   && !(op
3268                                        && (DECL_P (op)
3269                                            || (REFERENCE_CLASS_P (op)
3270                                                && get_base_address (op)))))
3271                                 continue;
3272                             }
3273                         }
3274                     }
3275                   LOOP_VINFO_DATAREFS (loop_vinfo) = datarefs;
3276                   if (dump_enabled_p ())
3277                     dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3278                                      "not vectorized: loop contains function "
3279                                      "calls or data references that cannot "
3280                                      "be analyzed\n");
3281                   return false;
3282                 }
3283             }
3284         }
3285
3286       LOOP_VINFO_DATAREFS (loop_vinfo) = datarefs;
3287     }
3288   else
3289     {
3290       gimple_stmt_iterator gsi;
3291
3292       bb = BB_VINFO_BB (bb_vinfo);
3293       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3294         {
3295           gimple stmt = gsi_stmt (gsi);
3296           if (is_gimple_debug (stmt))
3297             continue;
3298           ++*n_stmts;
3299           if (!find_data_references_in_stmt (NULL, stmt,
3300                                              &BB_VINFO_DATAREFS (bb_vinfo)))
3301             {
3302               /* Mark the rest of the basic-block as unvectorizable.  */
3303               for (; !gsi_end_p (gsi); gsi_next (&gsi))
3304                 {
3305                   stmt = gsi_stmt (gsi);
3306                   STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt)) = false;
3307                 }
3308               break;
3309             }
3310         }
3311
3312       datarefs = BB_VINFO_DATAREFS (bb_vinfo);
3313     }
3314
3315   /* Go through the data-refs, check that the analysis succeeded.  Update
3316      pointer from stmt_vec_info struct to DR and vectype.  */
3317
3318   FOR_EACH_VEC_ELT (datarefs, i, dr)
3319     {
3320       gimple stmt;
3321       stmt_vec_info stmt_info;
3322       tree base, offset, init;
3323       bool gather = false;
3324       bool simd_lane_access = false;
3325       int vf;
3326
3327 again:
3328       if (!dr || !DR_REF (dr))
3329         {
3330           if (dump_enabled_p ())
3331             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3332                              "not vectorized: unhandled data-ref\n");
3333           return false;
3334         }
3335
3336       stmt = DR_STMT (dr);
3337       stmt_info = vinfo_for_stmt (stmt);
3338
3339       /* Discard clobbers from the dataref vector.  We will remove
3340          clobber stmts during vectorization.  */
3341       if (gimple_clobber_p (stmt))
3342         {
3343           free_data_ref (dr);
3344           if (i == datarefs.length () - 1)
3345             {
3346               datarefs.pop ();
3347               break;
3348             }
3349           datarefs.ordered_remove (i);
3350           dr = datarefs[i];
3351           goto again;
3352         }
3353
3354       /* Check that analysis of the data-ref succeeded.  */
3355       if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr) || !DR_INIT (dr)
3356           || !DR_STEP (dr))
3357         {
3358           bool maybe_gather
3359             = DR_IS_READ (dr)
3360               && !TREE_THIS_VOLATILE (DR_REF (dr))
3361               && targetm.vectorize.builtin_gather != NULL;
3362           bool maybe_simd_lane_access
3363             = loop_vinfo && loop->simduid;
3364
3365           /* If target supports vector gather loads, or if this might be
3366              a SIMD lane access, see if they can't be used.  */
3367           if (loop_vinfo
3368               && (maybe_gather || maybe_simd_lane_access)
3369               && !nested_in_vect_loop_p (loop, stmt))
3370             {
3371               struct data_reference *newdr
3372                 = create_data_ref (NULL, loop_containing_stmt (stmt),
3373                                    DR_REF (dr), stmt, true);
3374               gcc_assert (newdr != NULL && DR_REF (newdr));
3375               if (DR_BASE_ADDRESS (newdr)
3376                   && DR_OFFSET (newdr)
3377                   && DR_INIT (newdr)
3378                   && DR_STEP (newdr)
3379                   && integer_zerop (DR_STEP (newdr)))
3380                 {
3381                   if (maybe_simd_lane_access)
3382                     {
3383                       tree off = DR_OFFSET (newdr);
3384                       STRIP_NOPS (off);
3385                       if (TREE_CODE (DR_INIT (newdr)) == INTEGER_CST
3386                           && TREE_CODE (off) == MULT_EXPR
3387                           && tree_fits_uhwi_p (TREE_OPERAND (off, 1)))
3388                         {
3389                           tree step = TREE_OPERAND (off, 1);
3390                           off = TREE_OPERAND (off, 0);
3391                           STRIP_NOPS (off);
3392                           if (CONVERT_EXPR_P (off)
3393                               && TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (off,
3394                                                                           0)))
3395                                  < TYPE_PRECISION (TREE_TYPE (off)))
3396                             off = TREE_OPERAND (off, 0);
3397                           if (TREE_CODE (off) == SSA_NAME)
3398                             {
3399                               gimple def = SSA_NAME_DEF_STMT (off);
3400                               tree reft = TREE_TYPE (DR_REF (newdr));
3401                               if (is_gimple_call (def)
3402                                   && gimple_call_internal_p (def)
3403                                   && (gimple_call_internal_fn (def)
3404                                       == IFN_GOMP_SIMD_LANE))
3405                                 {
3406                                   tree arg = gimple_call_arg (def, 0);
3407                                   gcc_assert (TREE_CODE (arg) == SSA_NAME);
3408                                   arg = SSA_NAME_VAR (arg);
3409                                   if (arg == loop->simduid
3410                                       /* For now.  */
3411                                       && tree_int_cst_equal
3412                                            (TYPE_SIZE_UNIT (reft),
3413                                             step))
3414                                     {
3415                                       DR_OFFSET (newdr) = ssize_int (0);
3416                                       DR_STEP (newdr) = step;
3417                                       DR_ALIGNED_TO (newdr)
3418                                         = size_int (BIGGEST_ALIGNMENT);
3419                                       dr = newdr;
3420                                       simd_lane_access = true;
3421                                     }
3422                                 }
3423                             }
3424                         }
3425                     }
3426                   if (!simd_lane_access && maybe_gather)
3427                     {
3428                       dr = newdr;
3429                       gather = true;
3430                     }
3431                 }
3432               if (!gather && !simd_lane_access)
3433                 free_data_ref (newdr);
3434             }
3435
3436           if (!gather && !simd_lane_access)
3437             {
3438               if (dump_enabled_p ())
3439                 {
3440                   dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3441                                    "not vectorized: data ref analysis "
3442                                    "failed ");
3443                   dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3444                   dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
3445                 }
3446
3447               if (bb_vinfo)
3448                 break;
3449
3450               return false;
3451             }
3452         }
3453
3454       if (TREE_CODE (DR_BASE_ADDRESS (dr)) == INTEGER_CST)
3455         {
3456           if (dump_enabled_p ())
3457             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3458                              "not vectorized: base addr of dr is a "
3459                              "constant\n");
3460
3461           if (bb_vinfo)
3462             break;
3463
3464           if (gather || simd_lane_access)
3465             free_data_ref (dr);
3466           return false;
3467         }
3468
3469       if (TREE_THIS_VOLATILE (DR_REF (dr)))
3470         {
3471           if (dump_enabled_p ())
3472             {
3473               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3474                                "not vectorized: volatile type ");
3475               dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3476               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
3477             }
3478
3479           if (bb_vinfo)
3480             break;
3481
3482           return false;
3483         }
3484
3485       if (stmt_can_throw_internal (stmt))
3486         {
3487           if (dump_enabled_p ())
3488             {
3489               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3490                                "not vectorized: statement can throw an "
3491                                "exception ");
3492               dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3493               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
3494             }
3495
3496           if (bb_vinfo)
3497             break;
3498
3499           if (gather || simd_lane_access)
3500             free_data_ref (dr);
3501           return false;
3502         }
3503
3504       if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
3505           && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
3506         {
3507           if (dump_enabled_p ())
3508             {
3509               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3510                                "not vectorized: statement is bitfield "
3511                                "access ");
3512               dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3513               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
3514             }
3515
3516           if (bb_vinfo)
3517             break;
3518
3519           if (gather || simd_lane_access)
3520             free_data_ref (dr);
3521           return false;
3522         }
3523
3524       base = unshare_expr (DR_BASE_ADDRESS (dr));
3525       offset = unshare_expr (DR_OFFSET (dr));
3526       init = unshare_expr (DR_INIT (dr));
3527
3528       if (is_gimple_call (stmt)
3529           && (!gimple_call_internal_p (stmt)
3530               || (gimple_call_internal_fn (stmt) != IFN_MASK_LOAD
3531                   && gimple_call_internal_fn (stmt) != IFN_MASK_STORE)))
3532         {
3533           if (dump_enabled_p ())
3534             {
3535               dump_printf_loc (MSG_MISSED_OPTIMIZATION,  vect_location,
3536                                "not vectorized: dr in a call ");
3537               dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3538               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
3539             }
3540
3541           if (bb_vinfo)
3542             break;
3543
3544           if (gather || simd_lane_access)
3545             free_data_ref (dr);
3546           return false;
3547         }
3548
3549       /* Update DR field in stmt_vec_info struct.  */
3550
3551       /* If the dataref is in an inner-loop of the loop that is considered for
3552          for vectorization, we also want to analyze the access relative to
3553          the outer-loop (DR contains information only relative to the
3554          inner-most enclosing loop).  We do that by building a reference to the
3555          first location accessed by the inner-loop, and analyze it relative to
3556          the outer-loop.  */
3557       if (loop && nested_in_vect_loop_p (loop, stmt))
3558         {
3559           tree outer_step, outer_base, outer_init;
3560           HOST_WIDE_INT pbitsize, pbitpos;
3561           tree poffset;
3562           machine_mode pmode;
3563           int punsignedp, pvolatilep;
3564           affine_iv base_iv, offset_iv;
3565           tree dinit;
3566
3567           /* Build a reference to the first location accessed by the
3568              inner-loop: *(BASE+INIT).  (The first location is actually
3569              BASE+INIT+OFFSET, but we add OFFSET separately later).  */
3570           tree inner_base = build_fold_indirect_ref
3571                                 (fold_build_pointer_plus (base, init));
3572
3573           if (dump_enabled_p ())
3574             {
3575               dump_printf_loc (MSG_NOTE, vect_location,
3576                                "analyze in outer-loop: ");
3577               dump_generic_expr (MSG_NOTE, TDF_SLIM, inner_base);
3578               dump_printf (MSG_NOTE, "\n");
3579             }
3580
3581           outer_base = get_inner_reference (inner_base, &pbitsize, &pbitpos,
3582                           &poffset, &pmode, &punsignedp, &pvolatilep, false);
3583           gcc_assert (outer_base != NULL_TREE);
3584
3585           if (pbitpos % BITS_PER_UNIT != 0)
3586             {
3587               if (dump_enabled_p ())
3588                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3589                                  "failed: bit offset alignment.\n");
3590               return false;
3591             }
3592
3593           outer_base = build_fold_addr_expr (outer_base);
3594           if (!simple_iv (loop, loop_containing_stmt (stmt), outer_base,
3595                           &base_iv, false))
3596             {
3597               if (dump_enabled_p ())
3598                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3599                                  "failed: evolution of base is not affine.\n");
3600               return false;
3601             }
3602
3603           if (offset)
3604             {
3605               if (poffset)
3606                 poffset = fold_build2 (PLUS_EXPR, TREE_TYPE (offset), offset,
3607                                        poffset);
3608               else
3609                 poffset = offset;
3610             }
3611
3612           if (!poffset)
3613             {
3614               offset_iv.base = ssize_int (0);
3615               offset_iv.step = ssize_int (0);
3616             }
3617           else if (!simple_iv (loop, loop_containing_stmt (stmt), poffset,
3618                                &offset_iv, false))
3619             {
3620               if (dump_enabled_p ())
3621                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3622                                  "evolution of offset is not affine.\n");
3623               return false;
3624             }
3625
3626           outer_init = ssize_int (pbitpos / BITS_PER_UNIT);
3627           split_constant_offset (base_iv.base, &base_iv.base, &dinit);
3628           outer_init =  size_binop (PLUS_EXPR, outer_init, dinit);
3629           split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
3630           outer_init =  size_binop (PLUS_EXPR, outer_init, dinit);
3631
3632           outer_step = size_binop (PLUS_EXPR,
3633                                 fold_convert (ssizetype, base_iv.step),
3634                                 fold_convert (ssizetype, offset_iv.step));
3635
3636           STMT_VINFO_DR_STEP (stmt_info) = outer_step;
3637           /* FIXME: Use canonicalize_base_object_address (base_iv.base); */
3638           STMT_VINFO_DR_BASE_ADDRESS (stmt_info) = base_iv.base;
3639           STMT_VINFO_DR_INIT (stmt_info) = outer_init;
3640           STMT_VINFO_DR_OFFSET (stmt_info) =
3641                                 fold_convert (ssizetype, offset_iv.base);
3642           STMT_VINFO_DR_ALIGNED_TO (stmt_info) =
3643                                 size_int (highest_pow2_factor (offset_iv.base));
3644
3645           if (dump_enabled_p ())
3646             {
3647               dump_printf_loc (MSG_NOTE, vect_location,
3648                                "\touter base_address: ");
3649               dump_generic_expr (MSG_NOTE, TDF_SLIM,
3650                                  STMT_VINFO_DR_BASE_ADDRESS (stmt_info));
3651               dump_printf (MSG_NOTE, "\n\touter offset from base address: ");
3652               dump_generic_expr (MSG_NOTE, TDF_SLIM,
3653                                  STMT_VINFO_DR_OFFSET (stmt_info));
3654               dump_printf (MSG_NOTE,
3655                            "\n\touter constant offset from base address: ");
3656               dump_generic_expr (MSG_NOTE, TDF_SLIM,
3657                                  STMT_VINFO_DR_INIT (stmt_info));
3658               dump_printf (MSG_NOTE, "\n\touter step: ");
3659               dump_generic_expr (MSG_NOTE, TDF_SLIM,
3660                                  STMT_VINFO_DR_STEP (stmt_info));
3661               dump_printf (MSG_NOTE, "\n\touter aligned to: ");
3662               dump_generic_expr (MSG_NOTE, TDF_SLIM,
3663                                  STMT_VINFO_DR_ALIGNED_TO (stmt_info));
3664               dump_printf (MSG_NOTE, "\n");
3665             }
3666         }
3667
3668       if (STMT_VINFO_DATA_REF (stmt_info))
3669         {
3670           if (dump_enabled_p ())
3671             {
3672               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3673                                "not vectorized: more than one data ref "
3674                                "in stmt: ");
3675               dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3676               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
3677             }
3678
3679           if (bb_vinfo)
3680             break;
3681
3682           if (gather || simd_lane_access)
3683             free_data_ref (dr);
3684           return false;
3685         }
3686
3687       STMT_VINFO_DATA_REF (stmt_info) = dr;
3688       if (simd_lane_access)
3689         {
3690           STMT_VINFO_SIMD_LANE_ACCESS_P (stmt_info) = true;
3691           free_data_ref (datarefs[i]);
3692           datarefs[i] = dr;
3693         }
3694
3695       /* Set vectype for STMT.  */
3696       scalar_type = TREE_TYPE (DR_REF (dr));
3697       STMT_VINFO_VECTYPE (stmt_info)
3698         = get_vectype_for_scalar_type (scalar_type);
3699       if (!STMT_VINFO_VECTYPE (stmt_info))
3700         {
3701           if (dump_enabled_p ())
3702             {
3703               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3704                                "not vectorized: no vectype for stmt: ");
3705               dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3706               dump_printf (MSG_MISSED_OPTIMIZATION, " scalar_type: ");
3707               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_DETAILS,
3708                                  scalar_type);
3709               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
3710             }
3711
3712           if (bb_vinfo)
3713             break;
3714
3715           if (gather || simd_lane_access)
3716             {
3717               STMT_VINFO_DATA_REF (stmt_info) = NULL;
3718               if (gather)
3719                 free_data_ref (dr);
3720             }
3721           return false;
3722         }
3723       else
3724         {
3725           if (dump_enabled_p ())
3726             {
3727               dump_printf_loc (MSG_NOTE, vect_location,
3728                                "got vectype for stmt: ");
3729               dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
3730               dump_generic_expr (MSG_NOTE, TDF_SLIM,
3731                                  STMT_VINFO_VECTYPE (stmt_info));
3732               dump_printf (MSG_NOTE, "\n");
3733             }
3734         }
3735
3736       /* Adjust the minimal vectorization factor according to the