OSDN Git Service

* cfgloop.c (flow_loop_entry_edges_find, flow_loop_exit_edges_find,
[pf3gnuchains/gcc-fork.git] / gcc / tree-vect-analyze.c
1 /* Analysis Utilities for Loop Vectorization.
2    Copyright (C) 2003,2004,2005 Free Software Foundation, Inc.
3    Contributed by Dorit Naishlos <dorit@il.ibm.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "errors.h"
27 #include "ggc.h"
28 #include "tree.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
33 #include "timevar.h"
34 #include "cfgloop.h"
35 #include "expr.h"
36 #include "optabs.h"
37 #include "tree-chrec.h"
38 #include "tree-data-ref.h"
39 #include "tree-scalar-evolution.h"
40 #include "tree-vectorizer.h"
41
42 /* Main analysis functions.  */
43 static loop_vec_info vect_analyze_loop_form (struct loop *);
44 static bool vect_analyze_data_refs (loop_vec_info);
45 static bool vect_mark_stmts_to_be_vectorized (loop_vec_info);
46 static bool vect_analyze_scalar_cycles (loop_vec_info);
47 static bool vect_analyze_data_ref_accesses (loop_vec_info);
48 static bool vect_analyze_data_ref_dependences (loop_vec_info);
49 static bool vect_analyze_data_refs_alignment (loop_vec_info);
50 static bool vect_compute_data_refs_alignment (loop_vec_info);
51 static void vect_enhance_data_refs_alignment (loop_vec_info);
52 static bool vect_analyze_operations (loop_vec_info);
53
54 /* Utility functions for the analyses.  */
55 static bool exist_non_indexing_operands_for_use_p (tree, tree);
56 static void vect_mark_relevant (varray_type *, tree);
57 static bool vect_stmt_relevant_p (tree, loop_vec_info);
58 static tree vect_get_loop_niters (struct loop *, tree *);
59 static bool vect_analyze_data_ref_dependence
60   (struct data_reference *, struct data_reference *, loop_vec_info);
61 static bool vect_compute_data_ref_alignment (struct data_reference *);
62 static bool vect_analyze_data_ref_access (struct data_reference *);
63 static struct data_reference * vect_analyze_pointer_ref_access 
64   (tree, tree, bool, tree, tree *, tree *);
65 static bool vect_can_advance_ivs_p (loop_vec_info);
66 static tree vect_get_ptr_offset (tree, tree, tree *);
67 static bool vect_analyze_offset_expr (tree, struct loop *, tree, tree *, 
68                                       tree *, tree *);
69 static bool vect_base_addr_differ_p (struct data_reference *,
70                                      struct data_reference *drb, bool *);
71 static tree vect_object_analysis (tree, tree, bool, tree, 
72                                   struct data_reference **, tree *, tree *, 
73                                   tree *, bool *, tree *);
74 static tree vect_address_analysis (tree, tree, bool, tree, 
75                                    struct data_reference *, tree *, tree *, 
76                                    tree *, bool *);
77
78
79 /* Function vect_get_ptr_offset
80
81    Compute the OFFSET modulo vector-type alignment of pointer REF in bits.  */
82
83 static tree 
84 vect_get_ptr_offset (tree ref ATTRIBUTE_UNUSED, 
85                      tree vectype ATTRIBUTE_UNUSED, 
86                      tree *offset ATTRIBUTE_UNUSED)
87 {
88   /* TODO: Use alignment information.  */
89   return NULL_TREE; 
90 }
91
92
93 /* Function vect_analyze_offset_expr
94
95    Given an offset expression EXPR received from get_inner_reference, analyze
96    it and create an expression for INITIAL_OFFSET by substituting the variables 
97    of EXPR with initial_condition of the corresponding access_fn in the loop. 
98    E.g., 
99       for i
100          for (j = 3; j < N; j++)
101             a[j].b[i][j] = 0;
102          
103    For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be 
104    substituted, since its access_fn in the inner loop is i. 'j' will be 
105    substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
106    C` =  3 * C_j + C.
107
108    Compute MISALIGN (the misalignment of the data reference initial access from
109    its base) if possible. Misalignment can be calculated only if all the
110    variables can be substituted with constants, or if a variable is multiplied
111    by a multiple of VECTYPE_ALIGNMENT. In the above example, since 'i' cannot
112    be substituted, MISALIGN will be NULL_TREE in case that C_i is not a multiple
113    of VECTYPE_ALIGNMENT, and C` otherwise. (We perform MISALIGN modulo 
114    VECTYPE_ALIGNMENT computation in the caller of this function).
115
116    STEP is an evolution of the data reference in this loop in bytes.
117    In the above example, STEP is C_j.
118
119    Return FALSE, if the analysis fails, e.g., there is no access_fn for a 
120    variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN and STEP) 
121    are NULL_TREEs. Otherwise, return TRUE.
122
123 */
124
125 static bool
126 vect_analyze_offset_expr (tree expr, 
127                           struct loop *loop, 
128                           tree vectype_alignment,
129                           tree *initial_offset,
130                           tree *misalign,
131                           tree *step)
132 {
133   tree oprnd0;
134   tree oprnd1;
135   tree left_offset = ssize_int (0);
136   tree right_offset = ssize_int (0);
137   tree left_misalign = ssize_int (0);
138   tree right_misalign = ssize_int (0);
139   tree left_step = ssize_int (0);
140   tree right_step = ssize_int (0);
141   enum tree_code code;
142   tree init, evolution;
143
144   *step = NULL_TREE;
145   *misalign = NULL_TREE;
146   *initial_offset = NULL_TREE;
147
148   /* Strip conversions that don't narrow the mode.  */
149   expr = vect_strip_conversion (expr);
150   if (!expr)
151     return false;
152
153   /* Stop conditions:
154      1. Constant.  */
155   if (TREE_CODE (expr) == INTEGER_CST)
156     {
157       *initial_offset = fold_convert (ssizetype, expr);
158       *misalign = fold_convert (ssizetype, expr);      
159       *step = ssize_int (0);
160       return true;
161     }
162
163   /* 2. Variable. Try to substitute with initial_condition of the corresponding
164      access_fn in the current loop.  */
165   if (SSA_VAR_P (expr))
166     {
167       tree access_fn = analyze_scalar_evolution (loop, expr);
168
169       if (access_fn == chrec_dont_know)
170         /* No access_fn.  */
171         return false;
172
173       init = initial_condition_in_loop_num (access_fn, loop->num);
174       if (init == expr && !expr_invariant_in_loop_p (loop, init))
175         /* Not enough information: may be not loop invariant.  
176            E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its 
177            initial_condition is D, but it depends on i - loop's induction
178            variable.  */          
179         return false;
180
181       evolution = evolution_part_in_loop_num (access_fn, loop->num);
182       if (evolution && TREE_CODE (evolution) != INTEGER_CST)
183         /* Evolution is not constant.  */
184         return false;
185
186       if (TREE_CODE (init) == INTEGER_CST)
187         *misalign = fold_convert (ssizetype, init);
188       else
189         /* Not constant, misalignment cannot be calculated.  */
190         *misalign = NULL_TREE;
191
192       *initial_offset = fold_convert (ssizetype, init); 
193
194       *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
195       return true;      
196     }
197
198   /* Recursive computation.  */
199   if (!BINARY_CLASS_P (expr))
200     {
201       /* We expect to get binary expressions (PLUS/MINUS and MULT).  */
202       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
203         {
204           fprintf (vect_dump, "Not binary expression ");
205           print_generic_expr (vect_dump, expr, TDF_SLIM);
206         }
207       return false;
208     }
209   oprnd0 = TREE_OPERAND (expr, 0);
210   oprnd1 = TREE_OPERAND (expr, 1);
211
212   if (!vect_analyze_offset_expr (oprnd0, loop, vectype_alignment, &left_offset, 
213                                 &left_misalign, &left_step)
214       || !vect_analyze_offset_expr (oprnd1, loop, vectype_alignment, 
215                                    &right_offset, &right_misalign, &right_step))
216     return false;
217
218   /* The type of the operation: plus, minus or mult.  */
219   code = TREE_CODE (expr);
220   switch (code)
221     {
222     case MULT_EXPR:
223       if (TREE_CODE (right_offset) != INTEGER_CST)
224         /* RIGHT_OFFSET can be not constant. For example, for arrays of variable 
225            sized types. 
226            FORNOW: We don't support such cases.  */
227         return false;
228
229       /* Strip conversions that don't narrow the mode.  */
230       left_offset = vect_strip_conversion (left_offset);      
231       if (!left_offset)
232         return false;      
233       /* Misalignment computation.  */
234       if (SSA_VAR_P (left_offset))
235         {
236           /* If the left side contains variables that can't be substituted with 
237              constants, we check if the right side is a multiple of ALIGNMENT.
238            */
239           if (integer_zerop (size_binop (TRUNC_MOD_EXPR, right_offset, 
240                                   fold_convert (ssizetype, vectype_alignment))))
241             *misalign = ssize_int (0);
242           else
243             /* If the remainder is not zero or the right side isn't constant,
244                we can't compute  misalignment.  */
245             *misalign = NULL_TREE;
246         }
247       else 
248         {
249           /* The left operand was successfully substituted with constant.  */     
250           if (left_misalign)
251             /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is 
252                NULL_TREE.  */
253             *misalign  = size_binop (code, left_misalign, right_misalign);
254           else
255             *misalign = NULL_TREE; 
256         }
257
258       /* Step calculation.  */
259       /* Multiply the step by the right operand.  */
260       *step  = size_binop (MULT_EXPR, left_step, right_offset);
261       break;
262    
263     case PLUS_EXPR:
264     case MINUS_EXPR:
265       /* Combine the recursive calculations for step and misalignment.  */
266       *step = size_binop (code, left_step, right_step);
267    
268       if (left_misalign && right_misalign)
269         *misalign  = size_binop (code, left_misalign, right_misalign);
270       else
271         *misalign = NULL_TREE;
272     
273       break;
274
275     default:
276       gcc_unreachable ();
277     }
278
279   /* Compute offset.  */
280   *initial_offset = fold_convert (ssizetype, 
281                                   fold (build2 (code, TREE_TYPE (left_offset), 
282                                                 left_offset, 
283                                                 right_offset)));
284   return true;
285 }
286
287
288 /* Function vect_analyze_operations.
289
290    Scan the loop stmts and make sure they are all vectorizable.  */
291
292 static bool
293 vect_analyze_operations (loop_vec_info loop_vinfo)
294 {
295   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
296   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
297   int nbbs = loop->num_nodes;
298   block_stmt_iterator si;
299   unsigned int vectorization_factor = 0;
300   int i;
301   bool ok;
302   tree scalar_type;
303
304   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
305     fprintf (vect_dump, "=== vect_analyze_operations ===");
306
307   for (i = 0; i < nbbs; i++)
308     {
309       basic_block bb = bbs[i];
310
311       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
312         {
313           tree stmt = bsi_stmt (si);
314           unsigned int nunits;
315           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
316           tree vectype;
317
318           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
319             {
320               fprintf (vect_dump, "==> examining statement: ");
321               print_generic_expr (vect_dump, stmt, TDF_SLIM);
322             }
323
324           gcc_assert (stmt_info);
325
326           /* skip stmts which do not need to be vectorized.
327              this is expected to include:
328              - the COND_EXPR which is the loop exit condition
329              - any LABEL_EXPRs in the loop
330              - computations that are used only for array indexing or loop
331              control  */
332
333           if (!STMT_VINFO_RELEVANT_P (stmt_info))
334             {
335               if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
336                 fprintf (vect_dump, "irrelevant.");
337               continue;
338             }
339
340           if (VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))))
341             {
342               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
343                                          LOOP_LOC (loop_vinfo)))
344                 {
345                   fprintf (vect_dump, "not vectorized: vector stmt in loop:");
346                   print_generic_expr (vect_dump, stmt, TDF_SLIM);
347                 }
348               return false;
349             }
350
351           if (STMT_VINFO_DATA_REF (stmt_info))
352             scalar_type = TREE_TYPE (DR_REF (STMT_VINFO_DATA_REF (stmt_info)));    
353           else if (TREE_CODE (stmt) == MODIFY_EXPR)
354             scalar_type = TREE_TYPE (TREE_OPERAND (stmt, 0));
355           else
356             scalar_type = TREE_TYPE (stmt);
357
358           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
359             {
360               fprintf (vect_dump, "get vectype for scalar type:  ");
361               print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
362             }
363
364           vectype = get_vectype_for_scalar_type (scalar_type);
365           if (!vectype)
366             {
367               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
368                                          LOOP_LOC (loop_vinfo)))
369                 {
370                   fprintf (vect_dump,
371                            "not vectorized: unsupported data-type ");
372                   print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
373                 }
374               return false;
375             }
376
377           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
378             {
379               fprintf (vect_dump, "vectype: ");
380               print_generic_expr (vect_dump, vectype, TDF_SLIM);
381             }
382           STMT_VINFO_VECTYPE (stmt_info) = vectype;
383
384           ok = (vectorizable_operation (stmt, NULL, NULL)
385                 || vectorizable_assignment (stmt, NULL, NULL)
386                 || vectorizable_load (stmt, NULL, NULL)
387                 || vectorizable_store (stmt, NULL, NULL));
388
389           if (!ok)
390             {
391               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
392                                          LOOP_LOC (loop_vinfo)))
393                 {
394                   fprintf (vect_dump, "not vectorized: stmt not supported: ");
395                   print_generic_expr (vect_dump, stmt, TDF_SLIM);
396                 }
397               return false;
398             }
399
400           nunits = GET_MODE_NUNITS (TYPE_MODE (vectype));
401           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
402             fprintf (vect_dump, "nunits = %d", nunits);
403
404           if (vectorization_factor)
405             {
406               /* FORNOW: don't allow mixed units.
407                  This restriction will be relaxed in the future.  */
408               if (nunits != vectorization_factor)
409                 {
410                   if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
411                                              LOOP_LOC (loop_vinfo)))
412                     fprintf (vect_dump, "not vectorized: mixed data-types");
413                   return false;
414                 }
415             }
416           else
417             vectorization_factor = nunits;
418
419 #ifdef ENABLE_CHECKING
420           gcc_assert (GET_MODE_SIZE (TYPE_MODE (scalar_type))
421                         * vectorization_factor == UNITS_PER_SIMD_WORD);
422 #endif
423         }
424     }
425
426   /* TODO: Analyze cost. Decide if worth while to vectorize.  */
427
428   if (vectorization_factor <= 1)
429     {
430       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
431                                  LOOP_LOC (loop_vinfo)))
432         fprintf (vect_dump, "not vectorized: unsupported data-type");
433       return false;
434     }
435   LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
436
437   if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
438       && vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
439     fprintf (vect_dump,
440         "vectorization_factor = %d, niters = " HOST_WIDE_INT_PRINT_DEC,
441         vectorization_factor, LOOP_VINFO_INT_NITERS (loop_vinfo));
442
443   if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
444       && LOOP_VINFO_INT_NITERS (loop_vinfo) < vectorization_factor)
445     {
446       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
447                                  LOOP_LOC (loop_vinfo)))
448         fprintf (vect_dump, "not vectorized: iteration count too small.");
449       return false;
450     }
451
452   if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
453       || LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0)
454     {
455       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
456         fprintf (vect_dump, "epilog loop required.");
457       if (!vect_can_advance_ivs_p (loop_vinfo))
458         {
459           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
460                                      LOOP_LOC (loop_vinfo)))
461             fprintf (vect_dump,
462                      "not vectorized: can't create epilog loop 1.");
463           return false;
464         }
465       if (!slpeel_can_duplicate_loop_p (loop, loop->single_exit))
466         {
467           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
468                                      LOOP_LOC (loop_vinfo)))
469             fprintf (vect_dump,
470                      "not vectorized: can't create epilog loop 2.");
471           return false;
472         }
473     }
474
475   return true;
476 }
477
478
479 /* Function exist_non_indexing_operands_for_use_p 
480
481    USE is one of the uses attached to STMT. Check if USE is 
482    used in STMT for anything other than indexing an array.  */
483
484 static bool
485 exist_non_indexing_operands_for_use_p (tree use, tree stmt)
486 {
487   tree operand;
488   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
489  
490   /* USE corresponds to some operand in STMT. If there is no data
491      reference in STMT, then any operand that corresponds to USE
492      is not indexing an array.  */
493   if (!STMT_VINFO_DATA_REF (stmt_info))
494     return true;
495  
496   /* STMT has a data_ref. FORNOW this means that its of one of
497      the following forms:
498      -1- ARRAY_REF = var
499      -2- var = ARRAY_REF
500      (This should have been verified in analyze_data_refs).
501
502      'var' in the second case corresponds to a def, not a use,
503      so USE cannot correspond to any operands that are not used 
504      for array indexing.
505
506      Therefore, all we need to check is if STMT falls into the
507      first case, and whether var corresponds to USE.  */
508  
509   if (TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
510     return false;
511
512   operand = TREE_OPERAND (stmt, 1);
513
514   if (TREE_CODE (operand) != SSA_NAME)
515     return false;
516
517   if (operand == use)
518     return true;
519
520   return false;
521 }
522
523
524 /* Function vect_analyze_scalar_cycles.
525
526    Examine the cross iteration def-use cycles of scalar variables, by
527    analyzing the loop (scalar) PHIs; verify that the cross iteration def-use
528    cycles that they represent do not impede vectorization.
529
530    FORNOW: Reduction as in the following loop, is not supported yet:
531               loop1:
532               for (i=0; i<N; i++)
533                  sum += a[i];
534            The cross-iteration cycle corresponding to variable 'sum' will be
535            considered too complicated and will impede vectorization.
536
537    FORNOW: Induction as in the following loop, is not supported yet:
538               loop2:
539               for (i=0; i<N; i++)
540                  a[i] = i;
541
542            However, the following loop *is* vectorizable:
543               loop3:
544               for (i=0; i<N; i++)
545                  a[i] = b[i];
546
547            In both loops there exists a def-use cycle for the variable i:
548               loop: i_2 = PHI (i_0, i_1)
549                     a[i_2] = ...;
550                     i_1 = i_2 + 1;
551                     GOTO loop;
552
553            The evolution of the above cycle is considered simple enough,
554            however, we also check that the cycle does not need to be
555            vectorized, i.e - we check that the variable that this cycle
556            defines is only used for array indexing or in stmts that do not
557            need to be vectorized. This is not the case in loop2, but it
558            *is* the case in loop3.  */
559
560 static bool
561 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
562 {
563   tree phi;
564   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
565   basic_block bb = loop->header;
566   tree dummy;
567
568   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
569     fprintf (vect_dump, "=== vect_analyze_scalar_cycles ===");
570
571   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
572     {
573       tree access_fn = NULL;
574
575       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
576         {
577           fprintf (vect_dump, "Analyze phi: ");
578           print_generic_expr (vect_dump, phi, TDF_SLIM);
579         }
580
581       /* Skip virtual phi's. The data dependences that are associated with
582          virtual defs/uses (i.e., memory accesses) are analyzed elsewhere.  */
583
584       if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
585         {
586           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
587             fprintf (vect_dump, "virtual phi. skip.");
588           continue;
589         }
590
591       /* Analyze the evolution function.  */
592
593       /* FORNOW: The only scalar cross-iteration cycles that we allow are
594          those of loop induction variables; This property is verified here.
595
596          Furthermore, if that induction variable is used in an operation
597          that needs to be vectorized (i.e, is not solely used to index
598          arrays and check the exit condition) - we do not support its
599          vectorization yet. This property is verified in vect_is_simple_use,
600          during vect_analyze_operations.  */
601
602       access_fn = /* instantiate_parameters
603                      (loop,*/
604          analyze_scalar_evolution (loop, PHI_RESULT (phi));
605
606       if (!access_fn)
607         {
608           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
609                                     LOOP_LOC (loop_vinfo)))
610             fprintf (vect_dump, "not vectorized: unsupported scalar cycle.");
611           return false;
612         }
613
614       if (vect_print_dump_info (REPORT_DETAILS,
615                                 LOOP_LOC (loop_vinfo)))
616         {
617            fprintf (vect_dump, "Access function of PHI: ");
618            print_generic_expr (vect_dump, access_fn, TDF_SLIM);
619         }
620
621       if (!vect_is_simple_iv_evolution (loop->num, access_fn, &dummy, &dummy))
622         {
623           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
624                                     LOOP_LOC (loop_vinfo)))
625             fprintf (vect_dump, "not vectorized: unsupported scalar cycle.");
626           return false;
627         }
628     }
629
630   return true;
631 }
632
633
634 /* Function vect_base_addr_differ_p.
635
636    This is the simplest data dependence test: determines whether the
637    data references A and B access the same array/region.  Returns
638    false when the property is not computable at compile time.
639    Otherwise return true, and DIFFER_P will record the result. This
640    utility will not be necessary when alias_sets_conflict_p will be
641    less conservative.  */
642
643 static bool
644 vect_base_addr_differ_p (struct data_reference *dra,
645                          struct data_reference *drb,
646                          bool *differ_p)
647 {
648   tree stmt_a = DR_STMT (dra);
649   stmt_vec_info stmt_info_a = vinfo_for_stmt (stmt_a);   
650   tree stmt_b = DR_STMT (drb);
651   stmt_vec_info stmt_info_b = vinfo_for_stmt (stmt_b);   
652   tree addr_a = STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info_a);
653   tree addr_b = STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info_b);
654   tree type_a = TREE_TYPE (addr_a);
655   tree type_b = TREE_TYPE (addr_b);
656   HOST_WIDE_INT alias_set_a, alias_set_b;
657
658   gcc_assert (POINTER_TYPE_P (type_a) &&  POINTER_TYPE_P (type_b));
659   
660   /* Both references are ADDR_EXPR, i.e., we have the objects.  */
661   if (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR)
662     return array_base_name_differ_p (dra, drb, differ_p);  
663
664   alias_set_a = (TREE_CODE (addr_a) == ADDR_EXPR) ? 
665     get_alias_set (TREE_OPERAND (addr_a, 0)) : get_alias_set (addr_a);
666   alias_set_b = (TREE_CODE (addr_b) == ADDR_EXPR) ? 
667     get_alias_set (TREE_OPERAND (addr_b, 0)) : get_alias_set (addr_b);
668
669   if (!alias_sets_conflict_p (alias_set_a, alias_set_b))
670     {
671       *differ_p = true;
672       return true;
673     }
674   
675   /* An instruction writing through a restricted pointer is "independent" of any 
676      instruction reading or writing through a different pointer, in the same 
677      block/scope.  */
678   else if ((TYPE_RESTRICT (type_a) && !DR_IS_READ (dra))
679       || (TYPE_RESTRICT (type_b) && !DR_IS_READ (drb)))
680     {
681       *differ_p = true;
682       return true;
683     }
684   return false;
685 }
686
687
688 /* Function vect_analyze_data_ref_dependence.
689
690    Return TRUE if there (might) exist a dependence between a memory-reference
691    DRA and a memory-reference DRB.  */
692
693 static bool
694 vect_analyze_data_ref_dependence (struct data_reference *dra,
695                                   struct data_reference *drb, 
696                                   loop_vec_info loop_vinfo)
697 {
698   bool differ_p; 
699   struct data_dependence_relation *ddr;
700   
701   if (!vect_base_addr_differ_p (dra, drb, &differ_p))
702     {
703       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
704                                 LOOP_LOC (loop_vinfo)))
705         {
706           fprintf (vect_dump,
707                 "not vectorized: can't determine dependence between: ");
708           print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
709           fprintf (vect_dump, " and ");
710           print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
711         }
712       return true;
713     }
714
715   if (differ_p)
716     return false;
717
718   ddr = initialize_data_dependence_relation (dra, drb);
719   compute_affine_dependence (ddr);
720
721   if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
722     return false;
723   
724   if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
725                             LOOP_LOC (loop_vinfo)))
726     {
727       fprintf (vect_dump,
728         "not vectorized: possible dependence between data-refs ");
729       print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
730       fprintf (vect_dump, " and ");
731       print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
732     }
733
734   return true;
735 }
736
737
738 /* Function vect_analyze_data_ref_dependences.
739
740    Examine all the data references in the loop, and make sure there do not
741    exist any data dependences between them.
742
743    TODO: dependences which distance is greater than the vectorization factor
744          can be ignored.  */
745
746 static bool
747 vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo)
748 {
749   unsigned int i, j;
750   varray_type loop_write_refs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
751   varray_type loop_read_refs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
752
753   /* Examine store-store (output) dependences.  */
754
755   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
756     fprintf (vect_dump, "=== vect_analyze_dependences ===");
757
758   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
759     fprintf (vect_dump, "compare all store-store pairs.");
760
761   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_refs); i++)
762     {
763       for (j = i + 1; j < VARRAY_ACTIVE_SIZE (loop_write_refs); j++)
764         {
765           struct data_reference *dra =
766             VARRAY_GENERIC_PTR (loop_write_refs, i);
767           struct data_reference *drb =
768             VARRAY_GENERIC_PTR (loop_write_refs, j);
769           if (vect_analyze_data_ref_dependence (dra, drb, loop_vinfo))
770             return false;
771         }
772     }
773
774   /* Examine load-store (true/anti) dependences.  */
775
776   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
777     fprintf (vect_dump, "compare all load-store pairs.");
778
779   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_refs); i++)
780     {
781       for (j = 0; j < VARRAY_ACTIVE_SIZE (loop_write_refs); j++)
782         {
783           struct data_reference *dra = VARRAY_GENERIC_PTR (loop_read_refs, i);
784           struct data_reference *drb =
785             VARRAY_GENERIC_PTR (loop_write_refs, j);
786           if (vect_analyze_data_ref_dependence (dra, drb, loop_vinfo))
787             return false;
788         }
789     }
790
791   return true;
792 }
793
794
795 /* Function vect_compute_data_ref_alignment
796
797    Compute the misalignment of the data reference DR.
798
799    Output:
800    1. If during the misalignment computation it is found that the data reference
801       cannot be vectorized then false is returned.
802    2. DR_MISALIGNMENT (DR) is defined.
803
804    FOR NOW: No analysis is actually performed. Misalignment is calculated
805    only for trivial cases. TODO.  */
806
807 static bool
808 vect_compute_data_ref_alignment (struct data_reference *dr)
809 {
810   tree stmt = DR_STMT (dr);
811   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);  
812   tree ref = DR_REF (dr);
813   tree vectype;
814   tree base, alignment;
815   bool base_aligned_p;
816   tree misalign;
817    
818   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
819     fprintf (vect_dump, "vect_compute_data_ref_alignment:");
820
821   /* Initialize misalignment to unknown.  */
822   DR_MISALIGNMENT (dr) = -1;
823
824   misalign = STMT_VINFO_VECT_MISALIGNMENT (stmt_info);
825   base_aligned_p = STMT_VINFO_VECT_BASE_ALIGNED_P (stmt_info);
826   base = build_fold_indirect_ref (STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info));
827   vectype = STMT_VINFO_VECTYPE (stmt_info);
828
829   if (!misalign)
830     {
831       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC)) 
832         {
833           fprintf (vect_dump, "Unknown alignment for access: ");
834           print_generic_expr (vect_dump, base, TDF_SLIM);
835         }
836       return true;
837     }
838
839   if (!base_aligned_p) 
840     {
841       if (!vect_can_force_dr_alignment_p (base, TYPE_ALIGN (vectype)))
842         {
843           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
844             {
845               fprintf (vect_dump, "can't force alignment of ref: ");
846               print_generic_expr (vect_dump, ref, TDF_SLIM);
847             }
848           return true;
849         }
850       
851       /* Force the alignment of the decl.
852          NOTE: This is the only change to the code we make during
853          the analysis phase, before deciding to vectorize the loop.  */
854       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
855         fprintf (vect_dump, "force alignment");
856       DECL_ALIGN (base) = TYPE_ALIGN (vectype);
857       DECL_USER_ALIGN (base) = 1;
858     }
859
860   /* At this point we assume that the base is aligned.  */
861   gcc_assert (base_aligned_p 
862               || (TREE_CODE (base) == VAR_DECL 
863                   && DECL_ALIGN (base) >= TYPE_ALIGN (vectype)));
864
865   /* Alignment required, in bytes:  */
866   alignment = ssize_int (TYPE_ALIGN (vectype)/BITS_PER_UNIT);
867
868   /* Modulo alignment.  */
869   misalign = size_binop (TRUNC_MOD_EXPR, misalign, alignment);
870   if (tree_int_cst_sgn (misalign) < 0)
871     {
872       /* Negative misalignment value.  */
873       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
874         fprintf (vect_dump, "unexpected misalign value");
875       return false;
876     }
877
878   DR_MISALIGNMENT (dr) = tree_low_cst (misalign, 1);
879
880   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
881     fprintf (vect_dump, "misalign = %d bytes", DR_MISALIGNMENT (dr));
882
883   return true;
884 }
885
886
887 /* Function vect_compute_data_refs_alignment
888
889    Compute the misalignment of data references in the loop.
890    This pass may take place at function granularity instead of at loop
891    granularity.
892
893    FOR NOW: No analysis is actually performed. Misalignment is calculated
894    only for trivial cases. TODO.  */
895
896 static bool
897 vect_compute_data_refs_alignment (loop_vec_info loop_vinfo)
898 {
899   varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
900   varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
901   unsigned int i;
902
903   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
904     {
905       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
906       if (!vect_compute_data_ref_alignment (dr))
907         return false;
908     }
909
910   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
911     {
912       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
913       if (!vect_compute_data_ref_alignment (dr))
914         return false;
915     }
916
917   return true;
918 }
919
920
921 /* Function vect_enhance_data_refs_alignment
922
923    This pass will use loop versioning and loop peeling in order to enhance
924    the alignment of data references in the loop.
925
926    FOR NOW: we assume that whatever versioning/peeling takes place, only the
927    original loop is to be vectorized; Any other loops that are created by
928    the transformations performed in this pass - are not supposed to be
929    vectorized. This restriction will be relaxed.  */
930
931 static void
932 vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo)
933 {
934   varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
935   varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
936   unsigned int i;
937
938   /*
939      This pass will require a cost model to guide it whether to apply peeling 
940      or versioning or a combination of the two. For example, the scheme that
941      intel uses when given a loop with several memory accesses, is as follows:
942      choose one memory access ('p') which alignment you want to force by doing 
943      peeling. Then, either (1) generate a loop in which 'p' is aligned and all 
944      other accesses are not necessarily aligned, or (2) use loop versioning to 
945      generate one loop in which all accesses are aligned, and another loop in 
946      which only 'p' is necessarily aligned. 
947
948      ("Automatic Intra-Register Vectorization for the Intel Architecture",
949       Aart J.C. Bik, Milind Girkar, Paul M. Grey and Ximmin Tian, International
950       Journal of Parallel Programming, Vol. 30, No. 2, April 2002.)     
951
952      Devising a cost model is the most critical aspect of this work. It will 
953      guide us on which access to peel for, whether to use loop versioning, how 
954      many versions to create, etc. The cost model will probably consist of 
955      generic considerations as well as target specific considerations (on 
956      powerpc for example, misaligned stores are more painful than misaligned 
957      loads). 
958
959      Here is the general steps involved in alignment enhancements:
960     
961      -- original loop, before alignment analysis:
962         for (i=0; i<N; i++){
963           x = q[i];                     # DR_MISALIGNMENT(q) = unknown
964           p[i] = y;                     # DR_MISALIGNMENT(p) = unknown
965         }
966
967      -- After vect_compute_data_refs_alignment:
968         for (i=0; i<N; i++){
969           x = q[i];                     # DR_MISALIGNMENT(q) = 3
970           p[i] = y;                     # DR_MISALIGNMENT(p) = unknown
971         }
972
973      -- Possibility 1: we do loop versioning:
974      if (p is aligned) {
975         for (i=0; i<N; i++){    # loop 1A
976           x = q[i];                     # DR_MISALIGNMENT(q) = 3
977           p[i] = y;                     # DR_MISALIGNMENT(p) = 0
978         }
979      } 
980      else {
981         for (i=0; i<N; i++){    # loop 1B
982           x = q[i];                     # DR_MISALIGNMENT(q) = 3
983           p[i] = y;                     # DR_MISALIGNMENT(p) = unaligned
984         }
985      }
986    
987      -- Possibility 2: we do loop peeling:
988      for (i = 0; i < 3; i++){   # (scalar loop, not to be vectorized).
989         x = q[i];
990         p[i] = y;
991      }
992      for (i = 3; i < N; i++){   # loop 2A
993         x = q[i];                       # DR_MISALIGNMENT(q) = 0
994         p[i] = y;                       # DR_MISALIGNMENT(p) = unknown
995      }
996
997      -- Possibility 3: combination of loop peeling and versioning:
998      for (i = 0; i < 3; i++){   # (scalar loop, not to be vectorized).
999         x = q[i];
1000         p[i] = y;
1001      }
1002      if (p is aligned) {
1003         for (i = 3; i<N; i++){  # loop 3A
1004           x = q[i];                     # DR_MISALIGNMENT(q) = 0
1005           p[i] = y;                     # DR_MISALIGNMENT(p) = 0
1006         }
1007      } 
1008      else {
1009         for (i = 3; i<N; i++){  # loop 3B
1010           x = q[i];                     # DR_MISALIGNMENT(q) = 0
1011           p[i] = y;                     # DR_MISALIGNMENT(p) = unaligned
1012         }
1013      }
1014
1015      These loops are later passed to loop_transform to be vectorized. The 
1016      vectorizer will use the alignment information to guide the transformation 
1017      (whether to generate regular loads/stores, or with special handling for 
1018      misalignment). 
1019    */
1020
1021   /* (1) Peeling to force alignment.  */
1022
1023   /* (1.1) Decide whether to perform peeling, and how many iterations to peel:
1024      Considerations:
1025      + How many accesses will become aligned due to the peeling
1026      - How many accesses will become unaligned due to the peeling,
1027        and the cost of misaligned accesses.
1028      - The cost of peeling (the extra runtime checks, the increase 
1029        in code size).
1030
1031      The scheme we use FORNOW: peel to force the alignment of the first
1032      misaligned store in the loop.
1033      Rationale: misaligned stores are not yet supported.
1034
1035      TODO: Use a better cost model.  */
1036
1037   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
1038     {
1039       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
1040       if (!aligned_access_p (dr))
1041         {
1042           LOOP_VINFO_UNALIGNED_DR (loop_vinfo) = dr;
1043           LOOP_DO_PEELING_FOR_ALIGNMENT (loop_vinfo) = true;
1044           break;
1045         }
1046     }
1047
1048   if (!LOOP_VINFO_UNALIGNED_DR (loop_vinfo))
1049     {
1050       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
1051         fprintf (vect_dump, "Peeling for alignment will not be applied.");
1052       return;
1053     }
1054   else
1055     if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
1056       fprintf (vect_dump, "Peeling for alignment will be applied.");
1057
1058
1059   /* (1.2) Update the alignment info according to the peeling factor.
1060            If the misalignment of the DR we peel for is M, then the
1061            peeling factor is VF - M, and the misalignment of each access DR_i
1062            in the loop is DR_MISALIGNMENT (DR_i) + VF - M.
1063            If the misalignment of the DR we peel for is unknown, then the 
1064            misalignment of each access DR_i in the loop is also unknown.
1065
1066            FORNOW: set the misalignment of the accesses to unknown even
1067                    if the peeling factor is known at compile time.
1068
1069            TODO: - if the peeling factor is known at compile time, use that
1070                    when updating the misalignment info of the loop DRs.
1071                  - consider accesses that are known to have the same 
1072                    alignment, even if that alignment is unknown.  */
1073    
1074   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
1075     {
1076       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
1077       if (dr == LOOP_VINFO_UNALIGNED_DR (loop_vinfo))
1078         {
1079           DR_MISALIGNMENT (dr) = 0;
1080           if (vect_print_dump_info (REPORT_ALIGNMENT, LOOP_LOC (loop_vinfo)))
1081             fprintf (vect_dump, "Alignment of access forced using peeling.");
1082         }
1083       else
1084         DR_MISALIGNMENT (dr) = -1;
1085     }
1086   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
1087     {
1088       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
1089       if (dr == LOOP_VINFO_UNALIGNED_DR (loop_vinfo))
1090         {
1091           DR_MISALIGNMENT (dr) = 0;
1092           if (vect_print_dump_info (REPORT_ALIGNMENT, LOOP_LOC (loop_vinfo)))
1093             fprintf (vect_dump, "Alignment of access forced using peeling.");
1094         }
1095       else
1096         DR_MISALIGNMENT (dr) = -1;
1097     }
1098 }
1099
1100
1101 /* Function vect_analyze_data_refs_alignment
1102
1103    Analyze the alignment of the data-references in the loop.
1104    FOR NOW: Until support for misliagned accesses is in place, only if all
1105    accesses are aligned can the loop be vectorized. This restriction will be 
1106    relaxed.  */ 
1107
1108 static bool
1109 vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo)
1110 {
1111   varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
1112   varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
1113   enum dr_alignment_support supportable_dr_alignment;
1114   unsigned int i;
1115
1116   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1117     fprintf (vect_dump, "=== vect_analyze_data_refs_alignment ===");
1118
1119
1120   /* This pass may take place at function granularity instead of at loop
1121      granularity.  */
1122
1123   if (!vect_compute_data_refs_alignment (loop_vinfo))
1124     {
1125       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1126                                 LOOP_LOC (loop_vinfo)))
1127         fprintf (vect_dump, 
1128                  "not vectorized: can't calculate alignment for data ref.");
1129       return false;
1130     }
1131
1132
1133   /* This pass will decide on using loop versioning and/or loop peeling in 
1134      order to enhance the alignment of data references in the loop.  */
1135
1136   vect_enhance_data_refs_alignment (loop_vinfo);
1137
1138
1139   /* Finally, check that all the data references in the loop can be
1140      handled with respect to their alignment.  */
1141
1142   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
1143     {
1144       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
1145       supportable_dr_alignment = vect_supportable_dr_alignment (dr);
1146       if (!supportable_dr_alignment)
1147         {
1148           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1149                                     LOOP_LOC (loop_vinfo)))
1150             fprintf (vect_dump, "not vectorized: unsupported unaligned load.");
1151           return false;
1152         }
1153       if (supportable_dr_alignment != dr_aligned 
1154           && (vect_print_dump_info (REPORT_ALIGNMENT, LOOP_LOC (loop_vinfo))))
1155         fprintf (vect_dump, "Vectorizing an unaligned access.");
1156     }
1157   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
1158     {
1159       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
1160       supportable_dr_alignment = vect_supportable_dr_alignment (dr);
1161       if (!supportable_dr_alignment)
1162         {
1163           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1164                                     LOOP_LOC (loop_vinfo)))
1165             fprintf (vect_dump, "not vectorized: unsupported unaligned store.");
1166           return false;
1167         }
1168       if (supportable_dr_alignment != dr_aligned 
1169           && (vect_print_dump_info (REPORT_ALIGNMENT, LOOP_LOC (loop_vinfo))))
1170         fprintf (vect_dump, "Vectorizing an unaligned access.");
1171     }
1172
1173   return true;
1174 }
1175
1176
1177 /* Function vect_analyze_data_ref_access.
1178
1179    Analyze the access pattern of the data-reference DR. For now, a data access
1180    has to consecutive to be considered vectorizable.  */
1181
1182 static bool
1183 vect_analyze_data_ref_access (struct data_reference *dr)
1184 {
1185   tree stmt = DR_STMT (dr);
1186   stmt_vec_info stmt_info = vinfo_for_stmt (stmt); 
1187   tree step = STMT_VINFO_VECT_STEP (stmt_info);
1188   tree scalar_type = TREE_TYPE (DR_REF (dr));
1189
1190   if (!step || tree_int_cst_compare (step, TYPE_SIZE_UNIT (scalar_type)))
1191     {
1192       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1193         fprintf (vect_dump, "not consecutive access");
1194       return false;
1195     }
1196   return true;
1197 }
1198
1199
1200 /* Function vect_analyze_data_ref_accesses.
1201
1202    Analyze the access pattern of all the data references in the loop.
1203
1204    FORNOW: the only access pattern that is considered vectorizable is a
1205            simple step 1 (consecutive) access.
1206
1207    FORNOW: handle only arrays and pointer accesses.  */
1208
1209 static bool
1210 vect_analyze_data_ref_accesses (loop_vec_info loop_vinfo)
1211 {
1212   unsigned int i;
1213   varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
1214   varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
1215
1216   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1217     fprintf (vect_dump, "=== vect_analyze_data_ref_accesses ===");
1218
1219   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
1220     {
1221       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
1222       bool ok = vect_analyze_data_ref_access (dr);
1223       if (!ok)
1224         {
1225           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1226                                       LOOP_LOC (loop_vinfo)))
1227             fprintf (vect_dump, "not vectorized: complicated access pattern.");
1228           return false;
1229         }
1230     }
1231
1232   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
1233     {
1234       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
1235       bool ok = vect_analyze_data_ref_access (dr);
1236       if (!ok)
1237         {
1238           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1239                                     LOOP_LOC (loop_vinfo)))
1240             fprintf (vect_dump, "not vectorized: complicated access pattern.");
1241           return false;
1242         }
1243     }
1244
1245   return true;
1246 }
1247
1248
1249 /* Function vect_analyze_pointer_ref_access.
1250
1251    Input:
1252    STMT - a stmt that contains a data-ref.
1253    MEMREF - a data-ref in STMT, which is an INDIRECT_REF.
1254    ACCESS_FN - the access function of MEMREF.
1255
1256    Output:
1257    If the data-ref access is vectorizable, return a data_reference structure
1258    that represents it (DR). Otherwise - return NULL.  
1259    STEP - the stride of MEMREF in the loop.
1260    INIT - the initial condition of MEMREF in the loop.
1261 */
1262
1263 static struct data_reference *
1264 vect_analyze_pointer_ref_access (tree memref, tree stmt, bool is_read, 
1265                                  tree access_fn, tree *ptr_init, tree *ptr_step)
1266 {
1267   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1268   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1269   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1270   tree step, init;      
1271   tree reftype, innertype;
1272   tree indx_access_fn; 
1273   int loopnum = loop->num;
1274   struct data_reference *dr;
1275
1276   if (!vect_is_simple_iv_evolution (loopnum, access_fn, &init, &step))
1277     {
1278       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS, 
1279                                 LOOP_LOC (loop_vinfo))) 
1280         fprintf (vect_dump, "not vectorized: pointer access is not simple.");   
1281       return NULL;
1282     }
1283
1284   STRIP_NOPS (init);
1285
1286   if (!expr_invariant_in_loop_p (loop, init))
1287     {
1288       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1289                                 LOOP_LOC (loop_vinfo))) 
1290         fprintf (vect_dump, 
1291                  "not vectorized: initial condition is not loop invariant.");   
1292       return NULL;
1293     }
1294
1295   if (TREE_CODE (step) != INTEGER_CST)
1296     {
1297       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1298                                 LOOP_LOC (loop_vinfo))) 
1299         fprintf (vect_dump, 
1300                 "not vectorized: non constant step for pointer access.");       
1301       return NULL;
1302     }
1303
1304   reftype = TREE_TYPE (TREE_OPERAND (memref, 0));
1305   if (!POINTER_TYPE_P (reftype)) 
1306     {
1307       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1308                                 LOOP_LOC (loop_vinfo)))
1309         fprintf (vect_dump, "not vectorized: unexpected pointer access form."); 
1310       return NULL;
1311     }
1312
1313   reftype = TREE_TYPE (init);
1314   if (!POINTER_TYPE_P (reftype)) 
1315     {
1316       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1317                                 LOOP_LOC (loop_vinfo))) 
1318         fprintf (vect_dump, "not vectorized: unexpected pointer access form.");
1319       return NULL;
1320     }
1321
1322   *ptr_step = fold_convert (ssizetype, step);
1323   innertype = TREE_TYPE (reftype);
1324   /* Check that STEP is a multiple of type size.  */
1325   if (!integer_zerop (size_binop (TRUNC_MOD_EXPR, *ptr_step, 
1326                         fold_convert (ssizetype, TYPE_SIZE_UNIT (innertype)))))
1327     {
1328       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1329                                 LOOP_LOC (loop_vinfo))) 
1330         fprintf (vect_dump, "not vectorized: non consecutive access."); 
1331       return NULL;
1332     }
1333    
1334   indx_access_fn = 
1335         build_polynomial_chrec (loopnum, integer_zero_node, integer_one_node);
1336   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1337     {
1338       fprintf (vect_dump, "Access function of ptr indx: ");
1339       print_generic_expr (vect_dump, indx_access_fn, TDF_SLIM);
1340     }
1341   dr = init_data_ref (stmt, memref, NULL_TREE, indx_access_fn, is_read);
1342   *ptr_init = init;
1343   return dr;
1344 }
1345
1346
1347 /* Function vect_address_analysis
1348
1349    Return the BASE of the address expression EXPR.
1350    Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1351
1352    Input:
1353    EXPR - the address expression that is being analyzed
1354    STMT - the statement that contains EXPR or its original memory reference
1355    IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
1356    VECTYPE - the type that defines the alignment (i.e, we compute
1357              alignment relative to TYPE_ALIGN(VECTYPE))
1358    DR - data_reference struct for the original memory reference
1359
1360    Output:
1361    BASE (returned value) - the base of the data reference EXPR.
1362    INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
1363    MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
1364               computation is impossible
1365    STEP - evolution of EXPR in the loop
1366    BASE_ALIGNED - indicates if BASE is aligned
1367  
1368    If something unexpected is encountered (an unsupported form of data-ref),
1369    then NULL_TREE is returned.  
1370  */
1371
1372 static tree
1373 vect_address_analysis (tree expr, tree stmt, bool is_read, tree vectype, 
1374                        struct data_reference *dr, tree *offset, tree *misalign,
1375                        tree *step, bool *base_aligned)
1376 {
1377   tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
1378   tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1379   tree dummy;
1380
1381   switch (TREE_CODE (expr))
1382     {
1383     case PLUS_EXPR:
1384     case MINUS_EXPR:
1385       /* EXPR is of form {base +/- offset} (or {offset +/- base}).  */
1386       oprnd0 = TREE_OPERAND (expr, 0);
1387       oprnd1 = TREE_OPERAND (expr, 1);
1388
1389       STRIP_NOPS (oprnd0);
1390       STRIP_NOPS (oprnd1);
1391       
1392       /* Recursively try to find the base of the address contained in EXPR.
1393          For offset, the returned base will be NULL.  */
1394       base_addr0 = vect_address_analysis (oprnd0, stmt, is_read, vectype, dr, 
1395                                      &address_offset, &address_misalign, step, 
1396                                      base_aligned);
1397
1398       base_addr1 = vect_address_analysis (oprnd1, stmt, is_read, vectype, dr, 
1399                                      &address_offset, &address_misalign, step, 
1400                                      base_aligned);
1401
1402       /* We support cases where only one of the operands contains an 
1403          address.  */
1404       if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
1405         return NULL_TREE;
1406
1407       /* To revert STRIP_NOPS.  */
1408       oprnd0 = TREE_OPERAND (expr, 0);
1409       oprnd1 = TREE_OPERAND (expr, 1);
1410       
1411       offset_expr = base_addr0 ? 
1412         fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
1413
1414       /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is 
1415          a number, we can add it to the misalignment value calculated for base,
1416          otherwise, misalignment is NULL.  */
1417       if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
1418         *misalign = size_binop (TREE_CODE (expr), address_misalign, 
1419                                 offset_expr);
1420       else
1421         *misalign = NULL_TREE;
1422
1423       /* Combine offset (from EXPR {base + offset}) with the offset calculated
1424          for base.  */
1425       *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
1426       return base_addr0 ? base_addr0 : base_addr1;
1427
1428     case ADDR_EXPR:
1429       base_address = vect_object_analysis (TREE_OPERAND (expr, 0), stmt, is_read, 
1430                                    vectype, &dr, offset, misalign, step, 
1431                                    base_aligned, &dummy);
1432       return base_address;
1433
1434     case SSA_NAME:
1435       if (!POINTER_TYPE_P (TREE_TYPE (expr)))
1436         return NULL_TREE;
1437
1438       if (TYPE_ALIGN (TREE_TYPE (TREE_TYPE (expr))) < TYPE_ALIGN (vectype)) 
1439         {
1440           if (vect_get_ptr_offset (expr, vectype, misalign))
1441             *base_aligned = true;         
1442           else
1443             *base_aligned = false;
1444         }
1445       else
1446         {         
1447           *base_aligned = true;
1448           *misalign = ssize_int (0);
1449         }
1450       *offset = ssize_int (0);
1451       *step = ssize_int (0);
1452       return expr;
1453       
1454     default:
1455       return NULL_TREE;
1456     }
1457 }
1458
1459
1460 /* Function vect_object_analysis
1461
1462    Return the BASE of the data reference MEMREF.
1463    Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1464    E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset  
1465    'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET 
1466    instantiated with initial_conditions of access_functions of variables, 
1467    modulo alignment, and STEP is the evolution of the DR_REF in this loop.
1468
1469    Function get_inner_reference is used for the above in case of ARRAY_REF and
1470    COMPONENT_REF.
1471
1472    The structure of the function is as follows:
1473    Part 1:
1474    Case 1. For handled_component_p refs 
1475           1.1 call get_inner_reference
1476             1.1.1 analyze offset expr received from get_inner_reference
1477           1.2. build data-reference structure for MEMREF
1478         (fall through with BASE)
1479    Case 2. For declarations 
1480           2.1 check alignment
1481           2.2 update DR_BASE_NAME if necessary for alias
1482    Case 3. For INDIRECT_REFs 
1483           3.1 get the access function
1484           3.2 analyze evolution of MEMREF
1485           3.3 set data-reference structure for MEMREF
1486           3.4 call vect_address_analysis to analyze INIT of the access function
1487
1488    Part 2:
1489    Combine the results of object and address analysis to calculate 
1490    INITIAL_OFFSET, STEP and misalignment info.   
1491
1492    Input:
1493    MEMREF - the memory reference that is being analyzed
1494    STMT - the statement that contains MEMREF
1495    IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1496    VECTYPE - the type that defines the alignment (i.e, we compute
1497              alignment relative to TYPE_ALIGN(VECTYPE))
1498    
1499    Output:
1500    BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
1501                                    E.g, if MEMREF is a.b[k].c[i][j] the returned
1502                                    base is &a.
1503    DR - data_reference struct for MEMREF
1504    INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
1505    MISALIGN - offset of MEMREF from BASE in bytes (a constant) or NULL_TREE if 
1506               the computation is impossible
1507    STEP - evolution of the DR_REF in the loop
1508    BASE_ALIGNED - indicates if BASE is aligned
1509    MEMTAG - memory tag for aliasing purposes
1510  
1511    If something unexpected is encountered (an unsupported form of data-ref),
1512    then NULL_TREE is returned.  */
1513
1514 static tree
1515 vect_object_analysis (tree memref, tree stmt, bool is_read,
1516                       tree vectype, struct data_reference **dr,
1517                       tree *offset, tree *misalign, tree *step,
1518                       bool *base_aligned, tree *memtag)
1519 {
1520   tree base = NULL_TREE, base_address = NULL_TREE;
1521   tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
1522   tree object_step = ssize_int (0), address_step = ssize_int (0);
1523   bool object_base_aligned = true, address_base_aligned = true;
1524   tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1525   HOST_WIDE_INT pbitsize, pbitpos;
1526   tree poffset, bit_pos_in_bytes;
1527   enum machine_mode pmode;
1528   int punsignedp, pvolatilep;
1529   tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
1530   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1531   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1532   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1533   struct data_reference *ptr_dr = NULL;
1534   tree access_fn, evolution_part, address_to_analyze;
1535    
1536   /* Part 1: */
1537   /* Case 1. handled_component_p refs.  */
1538   if (handled_component_p (memref))
1539     {
1540       /* 1.1 call get_inner_reference.  */
1541       /* Find the base and the offset from it.  */
1542       base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
1543                                   &pmode, &punsignedp, &pvolatilep, false);
1544       if (!base)
1545         return NULL_TREE;
1546
1547       /* 1.1.1 analyze offset expr received from get_inner_reference.  */
1548       if (poffset 
1549           && !vect_analyze_offset_expr (poffset, loop, TYPE_SIZE_UNIT (vectype), 
1550                                 &object_offset, &object_misalign, &object_step))
1551         {
1552           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1553             {
1554               fprintf (vect_dump, "failed to compute offset or step for ");
1555               print_generic_expr (vect_dump, memref, TDF_SLIM);
1556             }
1557           return NULL_TREE;
1558         }
1559
1560       /* Add bit position to OFFSET and MISALIGN.  */
1561
1562       bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
1563       /* Check that there is no remainder in bits.  */
1564       if (pbitpos%BITS_PER_UNIT)
1565         {
1566           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1567             fprintf (vect_dump, "bit offset alignment.");
1568           return NULL_TREE;
1569         }
1570       object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);     
1571       if (object_misalign) 
1572         object_misalign = size_binop (PLUS_EXPR, object_misalign, 
1573                                       bit_pos_in_bytes); 
1574
1575       /* Create data-reference for MEMREF. TODO: handle COMPONENT_REFs.  */
1576       if (!(*dr))
1577         { 
1578           if (TREE_CODE (memref) == ARRAY_REF)
1579             *dr = analyze_array (stmt, memref, is_read);
1580           else
1581             /* FORNOW.  */
1582             return NULL_TREE;
1583         }
1584       memref = base; /* To continue analysis of BASE.  */
1585       /* fall through  */
1586     }
1587   
1588   /*  Part 1: Case 2. Declarations.  */ 
1589   if (DECL_P (memref))
1590     {
1591       /* We expect to get a decl only if we already have a DR.  */
1592       if (!(*dr))
1593         {
1594           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1595             {
1596               fprintf (vect_dump, "unhandled decl ");
1597               print_generic_expr (vect_dump, memref, TDF_SLIM);
1598             }
1599           return NULL_TREE;
1600         }
1601
1602       /* 2.1 check the alignment.  */
1603       if (DECL_ALIGN (memref) >= TYPE_ALIGN (vectype))
1604         object_base_aligned = true;
1605       else
1606         object_base_aligned = false;
1607
1608       /* 2.2 update DR_BASE_NAME if necessary.  */
1609       if (!DR_BASE_NAME ((*dr)))
1610         /* For alias analysis.  In case the analysis of INDIRECT_REF brought 
1611            us to object.  */
1612         DR_BASE_NAME ((*dr)) = memref;
1613
1614       base_address = build_fold_addr_expr (memref);
1615       *memtag = memref;
1616     }
1617
1618   /* Part 1:  Case 3. INDIRECT_REFs.  */
1619   else if (TREE_CODE (memref) == INDIRECT_REF)
1620     {      
1621       /* 3.1 get the access function.  */
1622       access_fn = analyze_scalar_evolution (loop, TREE_OPERAND (memref, 0));
1623       if (!access_fn)
1624         {
1625           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1626                                     LOOP_LOC (loop_vinfo)))
1627             fprintf (vect_dump, "not vectorized: complicated pointer access."); 
1628           return NULL_TREE;
1629         }
1630       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1631         {
1632           fprintf (vect_dump, "Access function of ptr: ");
1633           print_generic_expr (vect_dump, access_fn, TDF_SLIM);
1634         }
1635
1636       /* 3.2 analyze evolution of MEMREF.  */
1637       evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
1638       if (evolution_part)
1639         {
1640           ptr_dr = vect_analyze_pointer_ref_access (memref, stmt, is_read, 
1641                                          access_fn, &ptr_init, &ptr_step);
1642           if (!(ptr_dr))
1643             return NULL_TREE; 
1644           
1645           object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
1646           address_to_analyze = ptr_init;
1647         }
1648       else
1649         {
1650           if (!(*dr))
1651             {
1652               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1653                                         LOOP_LOC (loop_vinfo))) 
1654                 fprintf (vect_dump, "not vectorized: ptr is loop invariant.");  
1655               return NULL_TREE;
1656             }
1657           /* Since there exists DR for MEMREF, we are analyzing the base of
1658              handled component, which not necessary has evolution in the 
1659              loop.  */
1660           address_to_analyze = TREE_OPERAND (base, 0);
1661         }
1662       
1663       /* 3.3 set data-reference structure for MEMREF.  */
1664       *dr = (*dr) ? *dr : ptr_dr;
1665
1666       /* 3.4 call vect_address_analysis to analyze INIT of the access 
1667          function.  */
1668       base_address = vect_address_analysis (address_to_analyze, stmt, is_read, 
1669                                vectype, *dr, &address_offset, &address_misalign, 
1670                                &address_step, &address_base_aligned);
1671       if (!base_address)
1672         return NULL_TREE;
1673
1674       switch (TREE_CODE (base_address))
1675         {
1676         case SSA_NAME:
1677           *memtag = get_var_ann (SSA_NAME_VAR (base_address))->type_mem_tag;
1678           if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
1679             *memtag = get_var_ann (
1680                       SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->type_mem_tag;
1681           break;
1682         case ADDR_EXPR:
1683           *memtag = TREE_OPERAND (base_address, 0);
1684           break;
1685         default:
1686           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1687                                     LOOP_LOC (loop_vinfo)))
1688             {
1689               fprintf (vect_dump, "not vectorized: no memtag ref: "); 
1690               print_generic_expr (vect_dump, memref, TDF_SLIM);
1691             }
1692           return NULL_TREE;
1693         }
1694     }
1695             
1696   if (!base_address)
1697     /* MEMREF cannot be analyzed.  */
1698     return NULL_TREE;
1699
1700   /* Part 2: Combine the results of object and address analysis to calculate 
1701      INITIAL_OFFSET, STEP and misalignment info. */
1702   *offset = size_binop (PLUS_EXPR, object_offset, address_offset);
1703   if (object_misalign && address_misalign)
1704     *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
1705   else
1706     *misalign = NULL_TREE;
1707   *step = size_binop (PLUS_EXPR, object_step, address_step); 
1708   *base_aligned = object_base_aligned && address_base_aligned;
1709
1710   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1711     {
1712       fprintf (vect_dump, "Results of object analysis for: ");
1713       print_generic_expr (vect_dump, memref, TDF_SLIM);
1714       fprintf (vect_dump, "\n\tbase_address: ");
1715       print_generic_expr (vect_dump, base_address, TDF_SLIM);
1716       fprintf (vect_dump, "\n\toffset: ");
1717       print_generic_expr (vect_dump, *offset, TDF_SLIM);
1718       fprintf (vect_dump, "\n\tstep: ");
1719       print_generic_expr (vect_dump, *step, TDF_SLIM);
1720       fprintf (vect_dump, "\n\tbase aligned %d\n\tmisalign: ", *base_aligned);
1721       print_generic_expr (vect_dump, *misalign, TDF_SLIM);
1722     }
1723   return base_address;
1724 }
1725
1726
1727 /* Function vect_analyze_data_refs.
1728
1729    Find all the data references in the loop.
1730
1731    The general structure of the analysis of data refs in the vectorizer is as 
1732    follows:
1733    1- vect_analyze_data_refs(loop): 
1734       Find and analyze all data-refs in the loop:
1735           foreach ref
1736              base_address = vect_object_analysis(ref)
1737       1.1- vect_object_analysis(ref): 
1738            Analyze ref, and build a DR (data_referece struct) for it;
1739            compute base, initial_offset, step and alignment. 
1740            Call get_inner_reference for refs handled in this function.
1741            Call vect_addr_analysis(addr) to analyze pointer type expressions.
1742       Set ref_stmt.base, ref_stmt.initial_offset, ref_stmt.alignment,  
1743       ref_stmt.memtag and ref_stmt.step accordingly. 
1744    2- vect_analyze_dependences(): apply dependence testing using ref_stmt.DR
1745    3- vect_analyze_drs_alignment(): check that ref_stmt.alignment is ok.
1746    4- vect_analyze_drs_access(): check that ref_stmt.step is ok.
1747
1748    FORNOW: Handle aligned INDIRECT_REFs and ARRAY_REFs 
1749            which base is really an array (not a pointer) and which alignment 
1750            can be forced. This restriction will be relaxed.  */
1751
1752 static bool
1753 vect_analyze_data_refs (loop_vec_info loop_vinfo)
1754 {
1755   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1756   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1757   int nbbs = loop->num_nodes;
1758   block_stmt_iterator si;
1759   int j;
1760   struct data_reference *dr;
1761
1762   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1763     fprintf (vect_dump, "=== vect_analyze_data_refs ===");
1764
1765   for (j = 0; j < nbbs; j++)
1766     {
1767       basic_block bb = bbs[j];
1768       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1769         {
1770           bool is_read = false;
1771           tree stmt = bsi_stmt (si);
1772           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1773           v_may_def_optype v_may_defs = STMT_V_MAY_DEF_OPS (stmt);
1774           v_must_def_optype v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
1775           vuse_optype vuses = STMT_VUSE_OPS (stmt);
1776           varray_type *datarefs = NULL;
1777           int nvuses, nv_may_defs, nv_must_defs;
1778           tree memref = NULL;
1779           tree scalar_type, vectype;      
1780           tree base, offset, misalign, step, tag;
1781           bool base_aligned;
1782
1783           /* Assumption: there exists a data-ref in stmt, if and only if 
1784              it has vuses/vdefs.  */
1785
1786           if (!vuses && !v_may_defs && !v_must_defs)
1787             continue;
1788
1789           nvuses = NUM_VUSES (vuses);
1790           nv_may_defs = NUM_V_MAY_DEFS (v_may_defs);
1791           nv_must_defs = NUM_V_MUST_DEFS (v_must_defs);
1792
1793           if (nvuses && (nv_may_defs || nv_must_defs))
1794             {
1795               if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1796                 {
1797                   fprintf (vect_dump, "unexpected vdefs and vuses in stmt: ");
1798                   print_generic_expr (vect_dump, stmt, TDF_SLIM);
1799                 }
1800               return false;
1801             }
1802
1803           if (TREE_CODE (stmt) != MODIFY_EXPR)
1804             {
1805               if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1806                 {
1807                   fprintf (vect_dump, "unexpected vops in stmt: ");
1808                   print_generic_expr (vect_dump, stmt, TDF_SLIM);
1809                 }
1810               return false;
1811             }
1812
1813           if (vuses)
1814             {
1815               memref = TREE_OPERAND (stmt, 1);
1816               datarefs = &(LOOP_VINFO_DATAREF_READS (loop_vinfo));
1817               is_read = true;
1818             } 
1819           else /* vdefs */
1820             {
1821               memref = TREE_OPERAND (stmt, 0);
1822               datarefs = &(LOOP_VINFO_DATAREF_WRITES (loop_vinfo));
1823               is_read = false;
1824             }
1825           
1826           scalar_type = TREE_TYPE (memref);
1827           vectype = get_vectype_for_scalar_type (scalar_type);
1828           if (!vectype)
1829             {
1830               if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1831                 {
1832                   fprintf (vect_dump, "no vectype for stmt: ");
1833                   print_generic_expr (vect_dump, stmt, TDF_SLIM);
1834                   fprintf (vect_dump, " scalar_type: ");
1835                   print_generic_expr (vect_dump, scalar_type, TDF_DETAILS);
1836                 }
1837               /* It is not possible to vectorize this data reference.  */
1838               return false;
1839             }
1840          /* Analyze MEMREF. If it is of a supported form, build data_reference
1841              struct for it (DR).  */
1842           dr = NULL; 
1843           base = vect_object_analysis (memref, stmt, is_read, vectype, &dr, 
1844                                        &offset, &misalign, &step, 
1845                                        &base_aligned, &tag);
1846           if (!base)
1847             {
1848               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1849                                         LOOP_LOC (loop_vinfo)))
1850                 {
1851                   fprintf (vect_dump, "not vectorized: unhandled data ref: "); 
1852                   print_generic_expr (vect_dump, stmt, TDF_SLIM);
1853                 }
1854               return false;
1855             }
1856           STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info) = base;
1857           STMT_VINFO_VECT_INIT_OFFSET (stmt_info) = offset;
1858           STMT_VINFO_VECT_STEP (stmt_info) = step;
1859           STMT_VINFO_VECT_MISALIGNMENT (stmt_info) = misalign;
1860           STMT_VINFO_VECT_BASE_ALIGNED_P (stmt_info) = base_aligned;
1861           STMT_VINFO_MEMTAG (stmt_info) = tag;
1862           STMT_VINFO_VECTYPE (stmt_info) = vectype;
1863           VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
1864           STMT_VINFO_DATA_REF (stmt_info) = dr;
1865         }
1866     }
1867
1868   return true;
1869 }
1870
1871
1872 /* Utility functions used by vect_mark_stmts_to_be_vectorized.  */
1873
1874 /* Function vect_mark_relevant.
1875
1876    Mark STMT as "relevant for vectorization" and add it to WORKLIST.  */
1877
1878 static void
1879 vect_mark_relevant (varray_type *worklist, tree stmt)
1880 {
1881   stmt_vec_info stmt_info;
1882
1883   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1884     fprintf (vect_dump, "mark relevant.");
1885
1886   if (TREE_CODE (stmt) == PHI_NODE)
1887     {
1888       VARRAY_PUSH_TREE (*worklist, stmt);
1889       return;
1890     }
1891
1892   stmt_info = vinfo_for_stmt (stmt);
1893
1894   if (!stmt_info)
1895     {
1896       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1897         {
1898           fprintf (vect_dump, "mark relevant: no stmt info!!.");
1899           print_generic_expr (vect_dump, stmt, TDF_SLIM);
1900         }
1901       return;
1902     }
1903
1904   if (STMT_VINFO_RELEVANT_P (stmt_info))
1905     {
1906       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1907         fprintf (vect_dump, "already marked relevant.");
1908       return;
1909     }
1910
1911   STMT_VINFO_RELEVANT_P (stmt_info) = 1;
1912   VARRAY_PUSH_TREE (*worklist, stmt);
1913 }
1914
1915
1916 /* Function vect_stmt_relevant_p.
1917
1918    Return true if STMT in loop that is represented by LOOP_VINFO is
1919    "relevant for vectorization".
1920
1921    A stmt is considered "relevant for vectorization" if:
1922    - it has uses outside the loop.
1923    - it has vdefs (it alters memory).
1924    - control stmts in the loop (except for the exit condition).
1925
1926    CHECKME: what other side effects would the vectorizer allow?  */
1927
1928 static bool
1929 vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo)
1930 {
1931   v_may_def_optype v_may_defs;
1932   v_must_def_optype v_must_defs;
1933   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1934   int i;
1935   dataflow_t df;
1936   int num_uses;
1937
1938   /* cond stmt other than loop exit cond.  */
1939   if (is_ctrl_stmt (stmt) && (stmt != LOOP_VINFO_EXIT_COND (loop_vinfo)))
1940     return true;
1941
1942   /* changing memory.  */
1943   if (TREE_CODE (stmt) != PHI_NODE)
1944     {
1945       v_may_defs = STMT_V_MAY_DEF_OPS (stmt);
1946       v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
1947       if (v_may_defs || v_must_defs)
1948         {
1949           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1950             fprintf (vect_dump, "vec_stmt_relevant_p: stmt has vdefs.");
1951           return true;
1952         }
1953     }
1954
1955   /* uses outside the loop.  */
1956   df = get_immediate_uses (stmt);
1957   num_uses = num_immediate_uses (df);
1958   for (i = 0; i < num_uses; i++)
1959     {
1960       tree use = immediate_use (df, i);
1961       basic_block bb = bb_for_stmt (use);
1962       if (!flow_bb_inside_loop_p (loop, bb))
1963         {
1964           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1965             fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop.");
1966           return true;
1967         }
1968     }
1969
1970   return false;
1971 }
1972
1973
1974 /* Function vect_mark_stmts_to_be_vectorized.
1975
1976    Not all stmts in the loop need to be vectorized. For example:
1977
1978      for i...
1979        for j...
1980    1.    T0 = i + j
1981    2.    T1 = a[T0]
1982
1983    3.    j = j + 1
1984
1985    Stmt 1 and 3 do not need to be vectorized, because loop control and
1986    addressing of vectorized data-refs are handled differently.
1987
1988    This pass detects such stmts.  */
1989
1990 static bool
1991 vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo)
1992 {
1993   varray_type worklist;
1994   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1995   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1996   unsigned int nbbs = loop->num_nodes;
1997   block_stmt_iterator si;
1998   tree stmt;
1999   stmt_ann_t ann;
2000   unsigned int i;
2001   int j;
2002   use_optype use_ops;
2003   stmt_vec_info stmt_info;
2004   basic_block bb;
2005   tree phi;
2006
2007   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2008     fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ===");
2009
2010   bb = loop->header;
2011   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2012     {
2013       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2014         {
2015           fprintf (vect_dump, "init: phi relevant? ");
2016           print_generic_expr (vect_dump, phi, TDF_SLIM);
2017         }
2018
2019       if (vect_stmt_relevant_p (phi, loop_vinfo))
2020         {
2021           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
2022                                     LOOP_LOC (loop_vinfo)))
2023             fprintf (vect_dump, "unsupported reduction/induction.");
2024           return false;
2025         }
2026     }
2027
2028   VARRAY_TREE_INIT (worklist, 64, "work list");
2029
2030   /* 1. Init worklist.  */
2031
2032   for (i = 0; i < nbbs; i++)
2033     {
2034       bb = bbs[i];
2035       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2036         {
2037           stmt = bsi_stmt (si);
2038
2039           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2040             {
2041               fprintf (vect_dump, "init: stmt relevant? ");
2042               print_generic_expr (vect_dump, stmt, TDF_SLIM);
2043             } 
2044
2045           stmt_info = vinfo_for_stmt (stmt);
2046           STMT_VINFO_RELEVANT_P (stmt_info) = 0;
2047
2048           if (vect_stmt_relevant_p (stmt, loop_vinfo))
2049             vect_mark_relevant (&worklist, stmt);
2050         }
2051     }
2052
2053
2054   /* 2. Process_worklist */
2055
2056   while (VARRAY_ACTIVE_SIZE (worklist) > 0)
2057     {
2058       stmt = VARRAY_TOP_TREE (worklist);
2059       VARRAY_POP (worklist);
2060
2061       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2062         {
2063           fprintf (vect_dump, "worklist: examine stmt: ");
2064           print_generic_expr (vect_dump, stmt, TDF_SLIM);
2065         }
2066
2067       /* Examine the USES in this statement. Mark all the statements which
2068          feed this statement's uses as "relevant", unless the USE is used as
2069          an array index.  */
2070
2071       if (TREE_CODE (stmt) == PHI_NODE)
2072         {
2073           /* follow the def-use chain inside the loop.  */
2074           for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
2075             {
2076               tree arg = PHI_ARG_DEF (stmt, j);
2077               tree def_stmt = NULL_TREE;
2078               basic_block bb;
2079               if (!vect_is_simple_use (arg, loop_vinfo, &def_stmt))
2080                 {
2081                   if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
2082                                             LOOP_LOC (loop_vinfo)))
2083                     fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
2084                   varray_clear (worklist);
2085                   return false;
2086                 }
2087               if (!def_stmt)
2088                 continue;
2089
2090               if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2091                 {
2092                   fprintf (vect_dump, "worklist: def_stmt: ");
2093                   print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
2094                 }
2095
2096               bb = bb_for_stmt (def_stmt);
2097               if (flow_bb_inside_loop_p (loop, bb))
2098                 vect_mark_relevant (&worklist, def_stmt);
2099             }
2100         } 
2101
2102       ann = stmt_ann (stmt);
2103       use_ops = USE_OPS (ann);
2104
2105       for (i = 0; i < NUM_USES (use_ops); i++)
2106         {
2107           tree use = USE_OP (use_ops, i);
2108
2109           /* We are only interested in uses that need to be vectorized. Uses 
2110              that are used for address computation are not considered relevant.
2111            */
2112           if (exist_non_indexing_operands_for_use_p (use, stmt))
2113             {
2114               tree def_stmt = NULL_TREE;
2115               basic_block bb;
2116               if (!vect_is_simple_use (use, loop_vinfo, &def_stmt))
2117                 {
2118                   if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
2119                                             LOOP_LOC (loop_vinfo)))
2120                     fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
2121                   varray_clear (worklist);
2122                   return false;
2123                 }
2124
2125               if (!def_stmt)
2126                 continue;
2127
2128               if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2129                 {
2130                   fprintf (vect_dump, "worklist: examine use %d: ", i);
2131                   print_generic_expr (vect_dump, use, TDF_SLIM);
2132                 }
2133
2134               bb = bb_for_stmt (def_stmt);
2135               if (flow_bb_inside_loop_p (loop, bb))
2136                 vect_mark_relevant (&worklist, def_stmt);
2137             }
2138         }
2139     }                           /* while worklist */
2140
2141   varray_clear (worklist);
2142   return true;
2143 }
2144
2145
2146 /* Function vect_can_advance_ivs_p
2147
2148    In case the number of iterations that LOOP iterates in unknown at compile 
2149    time, an epilog loop will be generated, and the loop induction variables 
2150    (IVs) will be "advanced" to the value they are supposed to take just before 
2151    the epilog loop.  Here we check that the access function of the loop IVs
2152    and the expression that represents the loop bound are simple enough.
2153    These restrictions will be relaxed in the future.  */
2154
2155 static bool 
2156 vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
2157 {
2158   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2159   basic_block bb = loop->header;
2160   tree phi;
2161
2162   /* Analyze phi functions of the loop header.  */
2163
2164   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2165     {
2166       tree access_fn = NULL;
2167       tree evolution_part;
2168
2169       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2170         {
2171           fprintf (vect_dump, "Analyze phi: ");
2172           print_generic_expr (vect_dump, phi, TDF_SLIM);
2173         }
2174
2175       /* Skip virtual phi's. The data dependences that are associated with
2176          virtual defs/uses (i.e., memory accesses) are analyzed elsewhere.  */
2177
2178       if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
2179         {
2180           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2181             fprintf (vect_dump, "virtual phi. skip.");
2182           continue;
2183         }
2184
2185       /* Analyze the evolution function.  */
2186
2187       access_fn = instantiate_parameters
2188         (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2189
2190       if (!access_fn)
2191         {
2192           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2193             fprintf (vect_dump, "No Access function.");
2194           return false;
2195         }
2196
2197       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2198         {
2199           fprintf (vect_dump, "Access function of PHI: ");
2200           print_generic_expr (vect_dump, access_fn, TDF_SLIM);
2201         }
2202
2203       evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
2204       
2205       if (evolution_part == NULL_TREE)
2206         return false;
2207   
2208       /* FORNOW: We do not transform initial conditions of IVs 
2209          which evolution functions are a polynomial of degree >= 2.  */
2210
2211       if (tree_is_chrec (evolution_part))
2212         return false;  
2213     }
2214
2215   return true;
2216 }
2217
2218
2219 /* Function vect_get_loop_niters.
2220
2221    Determine how many iterations the loop is executed.
2222    If an expression that represents the number of iterations
2223    can be constructed, place it in NUMBER_OF_ITERATIONS.
2224    Return the loop exit condition.  */
2225
2226 static tree
2227 vect_get_loop_niters (struct loop *loop, tree *number_of_iterations)
2228 {
2229   tree niters;
2230
2231   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2232     fprintf (vect_dump, "=== get_loop_niters ===");
2233
2234   niters = number_of_iterations_in_loop (loop);
2235
2236   if (niters != NULL_TREE
2237       && niters != chrec_dont_know)
2238     {
2239       *number_of_iterations = niters;
2240
2241       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2242         {
2243           fprintf (vect_dump, "==> get_loop_niters:" );
2244           print_generic_expr (vect_dump, *number_of_iterations, TDF_SLIM);
2245         }
2246     }
2247
2248   return get_loop_exit_condition (loop);
2249 }
2250
2251
2252 /* Function vect_analyze_loop_form.
2253
2254    Verify the following restrictions (some may be relaxed in the future):
2255    - it's an inner-most loop
2256    - number of BBs = 2 (which are the loop header and the latch)
2257    - the loop has a pre-header
2258    - the loop has a single entry and exit
2259    - the loop exit condition is simple enough, and the number of iterations
2260      can be analyzed (a countable loop).  */
2261
2262 static loop_vec_info
2263 vect_analyze_loop_form (struct loop *loop)
2264 {
2265   loop_vec_info loop_vinfo;
2266   tree loop_cond;
2267   tree number_of_iterations = NULL;
2268   LOC loop_loc;
2269
2270   loop_loc = find_loop_location (loop);
2271
2272   if (vect_print_dump_info (REPORT_DETAILS, loop_loc))
2273     fprintf (vect_dump, "=== vect_analyze_loop_form ===");
2274
2275   if (loop->inner)
2276     {
2277       if (vect_print_dump_info (REPORT_OUTER_LOOPS, loop_loc))
2278         fprintf (vect_dump, "not vectorized: nested loop.");
2279       return NULL;
2280     }
2281   
2282   if (!loop->single_exit 
2283       || loop->num_nodes != 2
2284       || EDGE_COUNT (loop->header->preds) != 2)
2285     {
2286       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
2287         {
2288           if (!loop->single_exit)
2289             fprintf (vect_dump, "not vectorized: multiple exits.");
2290           else if (loop->num_nodes != 2)
2291             fprintf (vect_dump, "not vectorized: too many BBs in loop.");
2292           else if (EDGE_COUNT (loop->header->preds) != 2)
2293             fprintf (vect_dump, "not vectorized: too many incoming edges.");
2294         }
2295
2296       return NULL;
2297     }
2298
2299   /* We assume that the loop exit condition is at the end of the loop. i.e,
2300      that the loop is represented as a do-while (with a proper if-guard
2301      before the loop if needed), where the loop header contains all the
2302      executable statements, and the latch is empty.  */
2303   if (!empty_block_p (loop->latch))
2304     {
2305       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
2306         fprintf (vect_dump, "not vectorized: unexpectd loop form.");
2307       return NULL;
2308     }
2309
2310   /* Make sure there exists a single-predecessor exit bb:  */
2311   if (EDGE_COUNT (loop->single_exit->dest->preds) != 1)
2312     {
2313       edge e = loop->single_exit;
2314       if (!(e->flags & EDGE_ABNORMAL))
2315         {
2316           loop_split_edge_with (e, NULL);
2317           if (vect_print_dump_info (REPORT_DETAILS, loop_loc))
2318             fprintf (vect_dump, "split exit edge.");
2319         }
2320       else
2321         {
2322           if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
2323             fprintf (vect_dump, "not vectorized: abnormal loop exit edge.");
2324           return NULL;
2325         }
2326     }
2327
2328   if (empty_block_p (loop->header))
2329     {
2330       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
2331         fprintf (vect_dump, "not vectorized: empty loop.");
2332       return NULL;
2333     }
2334
2335   loop_cond = vect_get_loop_niters (loop, &number_of_iterations);
2336   if (!loop_cond)
2337     {
2338       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
2339         fprintf (vect_dump, "not vectorized: complicated exit condition.");
2340       return NULL;
2341     }
2342   
2343   if (!number_of_iterations) 
2344     {
2345       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
2346         fprintf (vect_dump, 
2347                  "not vectorized: number of iterations cannot be computed.");
2348       return NULL;
2349     }
2350
2351   if (chrec_contains_undetermined (number_of_iterations))
2352     {
2353       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
2354         fprintf (vect_dump, "Infinite number of iterations.");
2355       return false;
2356     }
2357
2358   loop_vinfo = new_loop_vec_info (loop);
2359   LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
2360
2361   if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
2362     {
2363       if (vect_print_dump_info (REPORT_DETAILS, loop_loc))
2364         {
2365           fprintf (vect_dump, "Symbolic number of iterations is ");
2366           print_generic_expr (vect_dump, number_of_iterations, TDF_DETAILS);
2367         }
2368     }
2369   else
2370   if (LOOP_VINFO_INT_NITERS (loop_vinfo) == 0)
2371     {
2372       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS, loop_loc))
2373         fprintf (vect_dump, "not vectorized: number of iterations = 0.");
2374       return NULL;
2375     }
2376
2377   LOOP_VINFO_EXIT_COND (loop_vinfo) = loop_cond;
2378   LOOP_VINFO_LOC (loop_vinfo) = loop_loc;
2379
2380   return loop_vinfo;
2381 }
2382
2383
2384 /* Function vect_analyze_loop.
2385
2386    Apply a set of analyses on LOOP, and create a loop_vec_info struct
2387    for it. The different analyses will record information in the
2388    loop_vec_info struct.  */
2389 loop_vec_info
2390 vect_analyze_loop (struct loop *loop)
2391 {
2392   bool ok;
2393   loop_vec_info loop_vinfo;
2394
2395   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2396     fprintf (vect_dump, "===== analyze_loop_nest =====");
2397
2398   /* Check the CFG characteristics of the loop (nesting, entry/exit, etc.  */
2399
2400   loop_vinfo = vect_analyze_loop_form (loop);
2401   if (!loop_vinfo)
2402     {
2403       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2404         fprintf (vect_dump, "bad loop form.");
2405       return NULL;
2406     }
2407
2408   /* Find all data references in the loop (which correspond to vdefs/vuses)
2409      and analyze their evolution in the loop.
2410
2411      FORNOW: Handle only simple, array references, which
2412      alignment can be forced, and aligned pointer-references.  */
2413
2414   ok = vect_analyze_data_refs (loop_vinfo);
2415   if (!ok)
2416     {
2417       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
2418         fprintf (vect_dump, "bad data references.");
2419       destroy_loop_vec_info (loop_vinfo);
2420       return NULL;
2421     }
2422
2423   /* Data-flow analysis to detect stmts that do not need to be vectorized.  */
2424
2425   ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
2426   if (!ok)
2427     {
2428       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
2429         fprintf (vect_dump, "unexpected pattern.");
2430       destroy_loop_vec_info (loop_vinfo);
2431       return NULL;
2432     }
2433
2434   /* Check that all cross-iteration scalar data-flow cycles are OK.
2435      Cross-iteration cycles caused by virtual phis are analyzed separately.  */
2436
2437   ok = vect_analyze_scalar_cycles (loop_vinfo);
2438   if (!ok)
2439     {
2440       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
2441         fprintf (vect_dump, "bad scalar cycle.");
2442       destroy_loop_vec_info (loop_vinfo);
2443       return NULL;
2444     }
2445
2446   /* Analyze data dependences between the data-refs in the loop. 
2447      FORNOW: fail at the first data dependence that we encounter.  */
2448
2449   ok = vect_analyze_data_ref_dependences (loop_vinfo);
2450   if (!ok)
2451     {
2452       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
2453         fprintf (vect_dump, "bad data dependence.");
2454       destroy_loop_vec_info (loop_vinfo);
2455       return NULL;
2456     }
2457
2458   /* Analyze the access patterns of the data-refs in the loop (consecutive,
2459      complex, etc.). FORNOW: Only handle consecutive access pattern.  */
2460
2461   ok = vect_analyze_data_ref_accesses (loop_vinfo);
2462   if (!ok)
2463     {
2464       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
2465         fprintf (vect_dump, "bad data access.");
2466       destroy_loop_vec_info (loop_vinfo);
2467       return NULL;
2468     }
2469
2470   /* Analyze the alignment of the data-refs in the loop.
2471      FORNOW: Only aligned accesses are handled.  */
2472
2473   ok = vect_analyze_data_refs_alignment (loop_vinfo);
2474   if (!ok)
2475     {
2476       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
2477         fprintf (vect_dump, "bad data alignment.");
2478       destroy_loop_vec_info (loop_vinfo);
2479       return NULL;
2480     }
2481
2482   /* Scan all the operations in the loop and make sure they are
2483      vectorizable.  */
2484
2485   ok = vect_analyze_operations (loop_vinfo);
2486   if (!ok)
2487     {
2488       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
2489         fprintf (vect_dump, "bad operation or unsupported loop bound.");
2490       destroy_loop_vec_info (loop_vinfo);
2491       return NULL;
2492     }
2493
2494   LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1;
2495
2496   return loop_vinfo;
2497 }