1 /* Analysis Utilities for Loop Vectorization.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
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
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-flow.h"
31 #include "tree-dump.h"
37 #include "tree-chrec.h"
38 #include "tree-data-ref.h"
39 #include "tree-scalar-evolution.h"
40 #include "tree-vectorizer.h"
43 /* Main analysis functions. */
44 static loop_vec_info vect_analyze_loop_form (struct loop *);
45 static bool vect_analyze_data_refs (loop_vec_info);
46 static bool vect_mark_stmts_to_be_vectorized (loop_vec_info);
47 static void vect_analyze_scalar_cycles (loop_vec_info);
48 static bool vect_analyze_data_ref_accesses (loop_vec_info);
49 static bool vect_analyze_data_ref_dependences (loop_vec_info);
50 static bool vect_analyze_data_refs_alignment (loop_vec_info);
51 static bool vect_compute_data_refs_alignment (loop_vec_info);
52 static bool vect_enhance_data_refs_alignment (loop_vec_info);
53 static bool vect_analyze_operations (loop_vec_info);
54 static bool vect_determine_vectorization_factor (loop_vec_info);
56 /* Utility functions for the analyses. */
57 static bool exist_non_indexing_operands_for_use_p (tree, tree);
58 static tree vect_get_loop_niters (struct loop *, tree *);
59 static bool vect_analyze_data_ref_dependence
60 (struct data_dependence_relation *, 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 bool vect_can_advance_ivs_p (loop_vec_info);
64 static void vect_update_misalignment_for_peel
65 (struct data_reference *, struct data_reference *, int npeel);
67 /* Function vect_determine_vectorization_factor
69 Determine the vectorization factor (VF). VF is the number of data elements
70 that are operated upon in parallel in a single iteration of the vectorized
71 loop. For example, when vectorizing a loop that operates on 4byte elements,
72 on a target with vector size (VS) 16byte, the VF is set to 4, since 4
73 elements can fit in a single vector register.
75 We currently support vectorization of loops in which all types operated upon
76 are of the same size. Therefore this function currently sets VF according to
77 the size of the types operated upon, and fails if there are multiple sizes
80 VF is also the factor by which the loop iterations are strip-mined, e.g.:
87 for (i=0; i<N; i+=VF){
88 a[i:VF] = b[i:VF] + c[i:VF];
93 vect_determine_vectorization_factor (loop_vec_info loop_vinfo)
95 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
96 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
97 int nbbs = loop->num_nodes;
98 block_stmt_iterator si;
99 unsigned int vectorization_factor = 0;
104 stmt_vec_info stmt_info;
107 if (vect_print_dump_info (REPORT_DETAILS))
108 fprintf (vect_dump, "=== vect_determine_vectorization_factor ===");
110 for (i = 0; i < nbbs; i++)
112 basic_block bb = bbs[i];
114 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
116 stmt_info = vinfo_for_stmt (phi);
117 if (vect_print_dump_info (REPORT_DETAILS))
119 fprintf (vect_dump, "==> examining phi: ");
120 print_generic_expr (vect_dump, phi, TDF_SLIM);
123 gcc_assert (stmt_info);
125 if (STMT_VINFO_RELEVANT_P (stmt_info))
127 gcc_assert (!STMT_VINFO_VECTYPE (stmt_info));
128 scalar_type = TREE_TYPE (PHI_RESULT (phi));
130 if (vect_print_dump_info (REPORT_DETAILS))
132 fprintf (vect_dump, "get vectype for scalar type: ");
133 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
136 vectype = get_vectype_for_scalar_type (scalar_type);
139 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
142 "not vectorized: unsupported data-type ");
143 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
147 STMT_VINFO_VECTYPE (stmt_info) = vectype;
149 if (vect_print_dump_info (REPORT_DETAILS))
151 fprintf (vect_dump, "vectype: ");
152 print_generic_expr (vect_dump, vectype, TDF_SLIM);
155 nunits = TYPE_VECTOR_SUBPARTS (vectype);
156 if (vect_print_dump_info (REPORT_DETAILS))
157 fprintf (vect_dump, "nunits = %d", nunits);
159 if (!vectorization_factor
160 || (nunits > vectorization_factor))
161 vectorization_factor = nunits;
165 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
167 tree stmt = bsi_stmt (si);
168 stmt_info = vinfo_for_stmt (stmt);
170 if (vect_print_dump_info (REPORT_DETAILS))
172 fprintf (vect_dump, "==> examining statement: ");
173 print_generic_expr (vect_dump, stmt, TDF_SLIM);
176 gcc_assert (stmt_info);
178 /* skip stmts which do not need to be vectorized. */
179 if (!STMT_VINFO_RELEVANT_P (stmt_info)
180 && !STMT_VINFO_LIVE_P (stmt_info))
182 if (vect_print_dump_info (REPORT_DETAILS))
183 fprintf (vect_dump, "skip.");
187 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
189 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
191 fprintf (vect_dump, "not vectorized: irregular stmt.");
192 print_generic_expr (vect_dump, stmt, TDF_SLIM);
197 if (!GIMPLE_STMT_P (stmt)
198 && VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))))
200 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
202 fprintf (vect_dump, "not vectorized: vector stmt in loop:");
203 print_generic_expr (vect_dump, stmt, TDF_SLIM);
208 if (STMT_VINFO_VECTYPE (stmt_info))
210 /* The only case when a vectype had been already set is for stmts
211 that contain a dataref, or for "pattern-stmts" (stmts generated
212 by the vectorizer to represent/replace a certain idiom). */
213 gcc_assert (STMT_VINFO_DATA_REF (stmt_info)
214 || is_pattern_stmt_p (stmt_info));
215 vectype = STMT_VINFO_VECTYPE (stmt_info);
219 gcc_assert (! STMT_VINFO_DATA_REF (stmt_info)
220 && !is_pattern_stmt_p (stmt_info));
222 /* We set the vectype according to the type of the result (lhs).
223 For stmts whose result-type is different than the type of the
224 arguments (e.g. demotion, promotion), vectype will be reset
225 appropriately (later). Note that we have to visit the smallest
226 datatype in this function, because that determines the VF.
227 If the smallest datatype in the loop is present only as the
228 rhs of a promotion operation - we'd miss it here.
229 However, in such a case, that a variable of this datatype
230 does not appear in the lhs anywhere in the loop, it shouldn't
231 affect the vectorization factor. */
232 scalar_type = TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 0));
234 if (vect_print_dump_info (REPORT_DETAILS))
236 fprintf (vect_dump, "get vectype for scalar type: ");
237 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
240 vectype = get_vectype_for_scalar_type (scalar_type);
243 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
246 "not vectorized: unsupported data-type ");
247 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
251 STMT_VINFO_VECTYPE (stmt_info) = vectype;
254 if (vect_print_dump_info (REPORT_DETAILS))
256 fprintf (vect_dump, "vectype: ");
257 print_generic_expr (vect_dump, vectype, TDF_SLIM);
260 nunits = TYPE_VECTOR_SUBPARTS (vectype);
261 if (vect_print_dump_info (REPORT_DETAILS))
262 fprintf (vect_dump, "nunits = %d", nunits);
264 if (!vectorization_factor
265 || (nunits > vectorization_factor))
266 vectorization_factor = nunits;
271 /* TODO: Analyze cost. Decide if worth while to vectorize. */
272 if (vect_print_dump_info (REPORT_DETAILS))
273 fprintf (vect_dump, "vectorization factor = %d", vectorization_factor);
274 if (vectorization_factor <= 1)
276 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
277 fprintf (vect_dump, "not vectorized: unsupported data-type");
280 LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
286 /* Function vect_analyze_operations.
288 Scan the loop stmts and make sure they are all vectorizable. */
291 vect_analyze_operations (loop_vec_info loop_vinfo)
293 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
294 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
295 int nbbs = loop->num_nodes;
296 block_stmt_iterator si;
297 unsigned int vectorization_factor = 0;
301 stmt_vec_info stmt_info;
302 bool need_to_vectorize = false;
303 int min_profitable_iters;
304 int min_scalar_loop_bound;
307 if (vect_print_dump_info (REPORT_DETAILS))
308 fprintf (vect_dump, "=== vect_analyze_operations ===");
310 gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo));
311 vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
313 for (i = 0; i < nbbs; i++)
315 basic_block bb = bbs[i];
317 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
321 stmt_info = vinfo_for_stmt (phi);
322 if (vect_print_dump_info (REPORT_DETAILS))
324 fprintf (vect_dump, "examining phi: ");
325 print_generic_expr (vect_dump, phi, TDF_SLIM);
328 gcc_assert (stmt_info);
330 if (STMT_VINFO_LIVE_P (stmt_info))
332 /* FORNOW: not yet supported. */
333 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
334 fprintf (vect_dump, "not vectorized: value used after loop.");
338 if (STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_loop
339 && STMT_VINFO_DEF_TYPE (stmt_info) != vect_induction_def)
341 /* A scalar-dependence cycle that we don't support. */
342 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
343 fprintf (vect_dump, "not vectorized: scalar dependence cycle.");
347 if (STMT_VINFO_RELEVANT_P (stmt_info))
349 need_to_vectorize = true;
350 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def)
351 ok = vectorizable_induction (phi, NULL, NULL);
356 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
359 "not vectorized: relevant phi not supported: ");
360 print_generic_expr (vect_dump, phi, TDF_SLIM);
366 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
368 tree stmt = bsi_stmt (si);
369 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
370 enum vect_def_type relevance = STMT_VINFO_RELEVANT (stmt_info);
372 if (vect_print_dump_info (REPORT_DETAILS))
374 fprintf (vect_dump, "==> examining statement: ");
375 print_generic_expr (vect_dump, stmt, TDF_SLIM);
378 gcc_assert (stmt_info);
380 /* skip stmts which do not need to be vectorized.
381 this is expected to include:
382 - the COND_EXPR which is the loop exit condition
383 - any LABEL_EXPRs in the loop
384 - computations that are used only for array indexing or loop
387 if (!STMT_VINFO_RELEVANT_P (stmt_info)
388 && !STMT_VINFO_LIVE_P (stmt_info))
390 if (vect_print_dump_info (REPORT_DETAILS))
391 fprintf (vect_dump, "irrelevant.");
395 switch (STMT_VINFO_DEF_TYPE (stmt_info))
400 case vect_reduction_def:
401 gcc_assert (relevance == vect_unused_in_loop);
404 case vect_induction_def:
405 case vect_constant_def:
406 case vect_invariant_def:
407 case vect_unknown_def_type:
412 if (STMT_VINFO_RELEVANT_P (stmt_info))
414 gcc_assert (GIMPLE_STMT_P (stmt)
415 || !VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))));
416 gcc_assert (STMT_VINFO_VECTYPE (stmt_info));
417 need_to_vectorize = true;
420 ok = (vectorizable_type_promotion (stmt, NULL, NULL)
421 || vectorizable_type_demotion (stmt, NULL, NULL)
422 || vectorizable_conversion (stmt, NULL, NULL)
423 || vectorizable_operation (stmt, NULL, NULL)
424 || vectorizable_assignment (stmt, NULL, NULL)
425 || vectorizable_load (stmt, NULL, NULL)
426 || vectorizable_call (stmt, NULL, NULL)
427 || vectorizable_store (stmt, NULL, NULL)
428 || vectorizable_condition (stmt, NULL, NULL)
429 || vectorizable_reduction (stmt, NULL, NULL));
431 /* Stmts that are (also) "live" (i.e. - that are used out of the loop)
432 need extra handling, except for vectorizable reductions. */
433 if (STMT_VINFO_LIVE_P (stmt_info)
434 && STMT_VINFO_TYPE (stmt_info) != reduc_vec_info_type)
435 ok |= vectorizable_live_operation (stmt, NULL, NULL);
439 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
441 fprintf (vect_dump, "not vectorized: stmt not supported: ");
442 print_generic_expr (vect_dump, stmt, TDF_SLIM);
449 /* All operations in the loop are either irrelevant (deal with loop
450 control, or dead), or only used outside the loop and can be moved
451 out of the loop (e.g. invariants, inductions). The loop can be
452 optimized away by scalar optimizations. We're better off not
453 touching this loop. */
454 if (!need_to_vectorize)
456 if (vect_print_dump_info (REPORT_DETAILS))
458 "All the computation can be taken out of the loop.");
459 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
461 "not vectorized: redundant loop. no profit to vectorize.");
465 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
466 && vect_print_dump_info (REPORT_DETAILS))
468 "vectorization_factor = %d, niters = " HOST_WIDE_INT_PRINT_DEC,
469 vectorization_factor, LOOP_VINFO_INT_NITERS (loop_vinfo));
471 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
472 && (LOOP_VINFO_INT_NITERS (loop_vinfo) < vectorization_factor))
474 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
475 fprintf (vect_dump, "not vectorized: iteration count too small.");
476 if (vect_print_dump_info (REPORT_DETAILS))
477 fprintf (vect_dump,"not vectorized: iteration count smaller than "
478 "vectorization factor.");
482 /* Analyze cost. Decide if worth while to vectorize. */
484 min_profitable_iters = vect_estimate_min_profitable_iters (loop_vinfo);
485 LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo) = min_profitable_iters;
486 if (min_profitable_iters < 0)
488 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
489 fprintf (vect_dump, "not vectorized: vectorization not profitable.");
490 if (vect_print_dump_info (REPORT_DETAILS))
491 fprintf (vect_dump, "not vectorized: vector version will never be "
496 min_scalar_loop_bound = (PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND))
497 * vectorization_factor;
499 /* Use the cost model only if it is more conservative than user specified
502 th = (unsigned) min_scalar_loop_bound;
503 if (min_profitable_iters
504 && (!min_scalar_loop_bound
505 || min_profitable_iters > min_scalar_loop_bound))
506 th = (unsigned) min_profitable_iters;
508 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
509 && LOOP_VINFO_INT_NITERS (loop_vinfo) < th)
511 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
512 fprintf (vect_dump, "not vectorized: vectorization not "
514 if (vect_print_dump_info (REPORT_DETAILS))
515 fprintf (vect_dump, "not vectorized: iteration count smaller than "
516 "user specified loop bound parameter or minimum "
517 "profitable iterations (whichever is more conservative).");
521 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
522 || LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0
523 || LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo))
525 if (vect_print_dump_info (REPORT_DETAILS))
526 fprintf (vect_dump, "epilog loop required.");
527 if (!vect_can_advance_ivs_p (loop_vinfo))
529 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
531 "not vectorized: can't create epilog loop 1.");
534 if (!slpeel_can_duplicate_loop_p (loop, single_exit (loop)))
536 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
538 "not vectorized: can't create epilog loop 2.");
547 /* Function exist_non_indexing_operands_for_use_p
549 USE is one of the uses attached to STMT. Check if USE is
550 used in STMT for anything other than indexing an array. */
553 exist_non_indexing_operands_for_use_p (tree use, tree stmt)
556 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
558 /* USE corresponds to some operand in STMT. If there is no data
559 reference in STMT, then any operand that corresponds to USE
560 is not indexing an array. */
561 if (!STMT_VINFO_DATA_REF (stmt_info))
564 /* STMT has a data_ref. FORNOW this means that its of one of
568 (This should have been verified in analyze_data_refs).
570 'var' in the second case corresponds to a def, not a use,
571 so USE cannot correspond to any operands that are not used
574 Therefore, all we need to check is if STMT falls into the
575 first case, and whether var corresponds to USE. */
577 if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME)
580 operand = GIMPLE_STMT_OPERAND (stmt, 1);
582 if (TREE_CODE (operand) != SSA_NAME)
592 /* Function vect_analyze_scalar_cycles.
594 Examine the cross iteration def-use cycles of scalar variables, by
595 analyzing the loop (scalar) PHIs; Classify each cycle as one of the
596 following: invariant, induction, reduction, unknown.
598 Some forms of scalar cycles are not yet supported.
600 Example1: reduction: (unsupported yet)
606 Example2: induction: (unsupported yet)
612 Note: the following loop *is* vectorizable:
618 even though it has a def-use cycle caused by the induction variable i:
620 loop: i_2 = PHI (i_0, i_1)
625 because the def-use cycle in loop3 is considered "not relevant" - i.e.,
626 it does not need to be vectorized because it is only used for array
627 indexing (see 'mark_stmts_to_be_vectorized'). The def-use cycle in
628 loop2 on the other hand is relevant (it is being written to memory).
632 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
635 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
636 basic_block bb = loop->header;
638 VEC(tree,heap) *worklist = VEC_alloc (tree, heap, 64);
640 if (vect_print_dump_info (REPORT_DETAILS))
641 fprintf (vect_dump, "=== vect_analyze_scalar_cycles ===");
643 /* First - identify all inductions. */
644 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
646 tree access_fn = NULL;
647 tree def = PHI_RESULT (phi);
648 stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
650 if (vect_print_dump_info (REPORT_DETAILS))
652 fprintf (vect_dump, "Analyze phi: ");
653 print_generic_expr (vect_dump, phi, TDF_SLIM);
656 /* Skip virtual phi's. The data dependences that are associated with
657 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
658 if (!is_gimple_reg (SSA_NAME_VAR (def)))
661 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_unknown_def_type;
663 /* Analyze the evolution function. */
664 access_fn = analyze_scalar_evolution (loop, def);
665 if (access_fn && vect_print_dump_info (REPORT_DETAILS))
667 fprintf (vect_dump, "Access function of PHI: ");
668 print_generic_expr (vect_dump, access_fn, TDF_SLIM);
672 || !vect_is_simple_iv_evolution (loop->num, access_fn, &dumy, &dumy))
674 VEC_safe_push (tree, heap, worklist, phi);
678 if (vect_print_dump_info (REPORT_DETAILS))
679 fprintf (vect_dump, "Detected induction.");
680 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def;
684 /* Second - identify all reductions. */
685 while (VEC_length (tree, worklist) > 0)
687 tree phi = VEC_pop (tree, worklist);
688 tree def = PHI_RESULT (phi);
689 stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
692 if (vect_print_dump_info (REPORT_DETAILS))
694 fprintf (vect_dump, "Analyze phi: ");
695 print_generic_expr (vect_dump, phi, TDF_SLIM);
698 gcc_assert (is_gimple_reg (SSA_NAME_VAR (def)));
699 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_unknown_def_type);
701 reduc_stmt = vect_is_simple_reduction (loop, phi);
704 if (vect_print_dump_info (REPORT_DETAILS))
705 fprintf (vect_dump, "Detected reduction.");
706 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_reduction_def;
707 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
711 if (vect_print_dump_info (REPORT_DETAILS))
712 fprintf (vect_dump, "Unknown def-use cycle pattern.");
715 VEC_free (tree, heap, worklist);
720 /* Function vect_insert_into_interleaving_chain.
722 Insert DRA into the interleaving chain of DRB according to DRA's INIT. */
725 vect_insert_into_interleaving_chain (struct data_reference *dra,
726 struct data_reference *drb)
728 tree prev, next, next_init;
729 stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
730 stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
732 prev = DR_GROUP_FIRST_DR (stmtinfo_b);
733 next = DR_GROUP_NEXT_DR (vinfo_for_stmt (prev));
736 next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
737 if (tree_int_cst_compare (next_init, DR_INIT (dra)) > 0)
740 DR_GROUP_NEXT_DR (vinfo_for_stmt (prev)) = DR_STMT (dra);
741 DR_GROUP_NEXT_DR (stmtinfo_a) = next;
745 next = DR_GROUP_NEXT_DR (vinfo_for_stmt (prev));
748 /* We got to the end of the list. Insert here. */
749 DR_GROUP_NEXT_DR (vinfo_for_stmt (prev)) = DR_STMT (dra);
750 DR_GROUP_NEXT_DR (stmtinfo_a) = NULL_TREE;
754 /* Function vect_update_interleaving_chain.
756 For two data-refs DRA and DRB that are a part of a chain interleaved data
757 accesses, update the interleaving chain. DRB's INIT is smaller than DRA's.
759 There are four possible cases:
760 1. New stmts - both DRA and DRB are not a part of any chain:
763 2. DRB is a part of a chain and DRA is not:
764 no need to update FIRST_DR
765 no need to insert DRB
766 insert DRA according to init
767 3. DRA is a part of a chain and DRB is not:
768 if (init of FIRST_DR > init of DRB)
770 NEXT(FIRST_DR) = previous FIRST_DR
772 insert DRB according to its init
773 4. both DRA and DRB are in some interleaving chains:
774 choose the chain with the smallest init of FIRST_DR
775 insert the nodes of the second chain into the first one. */
778 vect_update_interleaving_chain (struct data_reference *drb,
779 struct data_reference *dra)
781 stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
782 stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
783 tree next_init, init_dra_chain, init_drb_chain, first_a, first_b;
784 tree node, prev, next, node_init, first_stmt;
786 /* 1. New stmts - both DRA and DRB are not a part of any chain. */
787 if (!DR_GROUP_FIRST_DR (stmtinfo_a) && !DR_GROUP_FIRST_DR (stmtinfo_b))
789 DR_GROUP_FIRST_DR (stmtinfo_a) = DR_STMT (drb);
790 DR_GROUP_FIRST_DR (stmtinfo_b) = DR_STMT (drb);
791 DR_GROUP_NEXT_DR (stmtinfo_b) = DR_STMT (dra);
795 /* 2. DRB is a part of a chain and DRA is not. */
796 if (!DR_GROUP_FIRST_DR (stmtinfo_a) && DR_GROUP_FIRST_DR (stmtinfo_b))
798 DR_GROUP_FIRST_DR (stmtinfo_a) = DR_GROUP_FIRST_DR (stmtinfo_b);
799 /* Insert DRA into the chain of DRB. */
800 vect_insert_into_interleaving_chain (dra, drb);
804 /* 3. DRA is a part of a chain and DRB is not. */
805 if (DR_GROUP_FIRST_DR (stmtinfo_a) && !DR_GROUP_FIRST_DR (stmtinfo_b))
807 tree old_first_stmt = DR_GROUP_FIRST_DR (stmtinfo_a);
808 tree init_old = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (
812 if (tree_int_cst_compare (init_old, DR_INIT (drb)) > 0)
814 /* DRB's init is smaller than the init of the stmt previously marked
815 as the first stmt of the interleaving chain of DRA. Therefore, we
816 update FIRST_STMT and put DRB in the head of the list. */
817 DR_GROUP_FIRST_DR (stmtinfo_b) = DR_STMT (drb);
818 DR_GROUP_NEXT_DR (stmtinfo_b) = old_first_stmt;
820 /* Update all the stmts in the list to point to the new FIRST_STMT. */
821 tmp = old_first_stmt;
824 DR_GROUP_FIRST_DR (vinfo_for_stmt (tmp)) = DR_STMT (drb);
825 tmp = DR_GROUP_NEXT_DR (vinfo_for_stmt (tmp));
830 /* Insert DRB in the list of DRA. */
831 vect_insert_into_interleaving_chain (drb, dra);
832 DR_GROUP_FIRST_DR (stmtinfo_b) = DR_GROUP_FIRST_DR (stmtinfo_a);
837 /* 4. both DRA and DRB are in some interleaving chains. */
838 first_a = DR_GROUP_FIRST_DR (stmtinfo_a);
839 first_b = DR_GROUP_FIRST_DR (stmtinfo_b);
840 if (first_a == first_b)
842 init_dra_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_a)));
843 init_drb_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_b)));
845 if (tree_int_cst_compare (init_dra_chain, init_drb_chain) > 0)
847 /* Insert the nodes of DRA chain into the DRB chain.
848 After inserting a node, continue from this node of the DRB chain (don't
849 start from the beginning. */
850 node = DR_GROUP_FIRST_DR (stmtinfo_a);
851 prev = DR_GROUP_FIRST_DR (stmtinfo_b);
852 first_stmt = first_b;
856 /* Insert the nodes of DRB chain into the DRA chain.
857 After inserting a node, continue from this node of the DRA chain (don't
858 start from the beginning. */
859 node = DR_GROUP_FIRST_DR (stmtinfo_b);
860 prev = DR_GROUP_FIRST_DR (stmtinfo_a);
861 first_stmt = first_a;
866 node_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (node)));
867 next = DR_GROUP_NEXT_DR (vinfo_for_stmt (prev));
870 next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
871 if (tree_int_cst_compare (next_init, node_init) > 0)
874 DR_GROUP_NEXT_DR (vinfo_for_stmt (prev)) = node;
875 DR_GROUP_NEXT_DR (vinfo_for_stmt (node)) = next;
880 next = DR_GROUP_NEXT_DR (vinfo_for_stmt (prev));
884 /* We got to the end of the list. Insert here. */
885 DR_GROUP_NEXT_DR (vinfo_for_stmt (prev)) = node;
886 DR_GROUP_NEXT_DR (vinfo_for_stmt (node)) = NULL_TREE;
889 DR_GROUP_FIRST_DR (vinfo_for_stmt (node)) = first_stmt;
890 node = DR_GROUP_NEXT_DR (vinfo_for_stmt (node));
895 /* Function vect_equal_offsets.
897 Check if OFFSET1 and OFFSET2 are identical expressions. */
900 vect_equal_offsets (tree offset1, tree offset2)
904 STRIP_NOPS (offset1);
905 STRIP_NOPS (offset2);
907 if (offset1 == offset2)
910 if (TREE_CODE (offset1) != TREE_CODE (offset2)
911 || !BINARY_CLASS_P (offset1)
912 || !BINARY_CLASS_P (offset2))
915 res0 = vect_equal_offsets (TREE_OPERAND (offset1, 0),
916 TREE_OPERAND (offset2, 0));
917 res1 = vect_equal_offsets (TREE_OPERAND (offset1, 1),
918 TREE_OPERAND (offset2, 1));
920 return (res0 && res1);
924 /* Function vect_check_interleaving.
926 Check if DRA and DRB are a part of interleaving. In case they are, insert
927 DRA and DRB in an interleaving chain. */
930 vect_check_interleaving (struct data_reference *dra,
931 struct data_reference *drb)
933 HOST_WIDE_INT type_size_a, type_size_b, diff_mod_size, step, init_a, init_b;
935 /* Check that the data-refs have same first location (except init) and they
936 are both either store or load (not load and store). */
937 if ((DR_BASE_ADDRESS (dra) != DR_BASE_ADDRESS (drb)
938 && (TREE_CODE (DR_BASE_ADDRESS (dra)) != ADDR_EXPR
939 || TREE_CODE (DR_BASE_ADDRESS (drb)) != ADDR_EXPR
940 || TREE_OPERAND (DR_BASE_ADDRESS (dra), 0)
941 != TREE_OPERAND (DR_BASE_ADDRESS (drb),0)))
942 || !vect_equal_offsets (DR_OFFSET (dra), DR_OFFSET (drb))
943 || !tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb))
944 || DR_IS_READ (dra) != DR_IS_READ (drb))
948 1. data-refs are of the same type
949 2. their steps are equal
950 3. the step is greater than the difference between data-refs' inits */
951 type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
952 type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
954 if (type_size_a != type_size_b
955 || tree_int_cst_compare (DR_STEP (dra), DR_STEP (drb)))
958 init_a = TREE_INT_CST_LOW (DR_INIT (dra));
959 init_b = TREE_INT_CST_LOW (DR_INIT (drb));
960 step = TREE_INT_CST_LOW (DR_STEP (dra));
964 /* If init_a == init_b + the size of the type * k, we have an interleaving,
965 and DRB is accessed before DRA. */
966 diff_mod_size = (init_a - init_b) % type_size_a;
968 if ((init_a - init_b) > step)
971 if (diff_mod_size == 0)
973 vect_update_interleaving_chain (drb, dra);
974 if (vect_print_dump_info (REPORT_DR_DETAILS))
976 fprintf (vect_dump, "Detected interleaving ");
977 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
978 fprintf (vect_dump, " and ");
979 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
986 /* If init_b == init_a + the size of the type * k, we have an
987 interleaving, and DRA is accessed before DRB. */
988 diff_mod_size = (init_b - init_a) % type_size_a;
990 if ((init_b - init_a) > step)
993 if (diff_mod_size == 0)
995 vect_update_interleaving_chain (dra, drb);
996 if (vect_print_dump_info (REPORT_DR_DETAILS))
998 fprintf (vect_dump, "Detected interleaving ");
999 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
1000 fprintf (vect_dump, " and ");
1001 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
1009 /* Function vect_analyze_data_ref_dependence.
1011 Return TRUE if there (might) exist a dependence between a memory-reference
1012 DRA and a memory-reference DRB. */
1015 vect_analyze_data_ref_dependence (struct data_dependence_relation *ddr,
1016 loop_vec_info loop_vinfo)
1019 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1020 int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1021 struct data_reference *dra = DDR_A (ddr);
1022 struct data_reference *drb = DDR_B (ddr);
1023 stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
1024 stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
1025 int dra_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dra))));
1026 int drb_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (drb))));
1027 lambda_vector dist_v;
1028 unsigned int loop_depth;
1030 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
1032 /* Independent data accesses. */
1033 vect_check_interleaving (dra, drb);
1037 if ((DR_IS_READ (dra) && DR_IS_READ (drb)) || dra == drb)
1040 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
1042 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1045 "not vectorized: can't determine dependence between ");
1046 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
1047 fprintf (vect_dump, " and ");
1048 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
1053 if (DDR_NUM_DIST_VECTS (ddr) == 0)
1055 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1057 fprintf (vect_dump, "not vectorized: bad dist vector for ");
1058 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
1059 fprintf (vect_dump, " and ");
1060 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
1065 loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr));
1066 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
1068 int dist = dist_v[loop_depth];
1070 if (vect_print_dump_info (REPORT_DR_DETAILS))
1071 fprintf (vect_dump, "dependence distance = %d.", dist);
1073 /* Same loop iteration. */
1074 if (dist % vectorization_factor == 0 && dra_size == drb_size)
1076 /* Two references with distance zero have the same alignment. */
1077 VEC_safe_push (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a), drb);
1078 VEC_safe_push (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b), dra);
1079 if (vect_print_dump_info (REPORT_ALIGNMENT))
1080 fprintf (vect_dump, "accesses have the same alignment.");
1081 if (vect_print_dump_info (REPORT_DR_DETAILS))
1083 fprintf (vect_dump, "dependence distance modulo vf == 0 between ");
1084 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
1085 fprintf (vect_dump, " and ");
1086 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
1089 /* For interleaving, mark that there is a read-write dependency if
1090 necessary. We check before that one of the data-refs is store. */
1091 if (DR_IS_READ (dra))
1092 DR_GROUP_READ_WRITE_DEPENDENCE (stmtinfo_a) = true;
1095 if (DR_IS_READ (drb))
1096 DR_GROUP_READ_WRITE_DEPENDENCE (stmtinfo_b) = true;
1102 if (abs (dist) >= vectorization_factor)
1104 /* Dependence distance does not create dependence, as far as vectorization
1105 is concerned, in this case. */
1106 if (vect_print_dump_info (REPORT_DR_DETAILS))
1107 fprintf (vect_dump, "dependence distance >= VF.");
1111 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1114 "not vectorized: possible dependence between data-refs ");
1115 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
1116 fprintf (vect_dump, " and ");
1117 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
1127 /* Function vect_analyze_data_ref_dependences.
1129 Examine all the data references in the loop, and make sure there do not
1130 exist any data dependences between them. */
1133 vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo)
1136 VEC (ddr_p, heap) *ddrs = LOOP_VINFO_DDRS (loop_vinfo);
1137 struct data_dependence_relation *ddr;
1139 if (vect_print_dump_info (REPORT_DETAILS))
1140 fprintf (vect_dump, "=== vect_analyze_dependences ===");
1142 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
1143 if (vect_analyze_data_ref_dependence (ddr, loop_vinfo))
1150 /* Function vect_compute_data_ref_alignment
1152 Compute the misalignment of the data reference DR.
1155 1. If during the misalignment computation it is found that the data reference
1156 cannot be vectorized then false is returned.
1157 2. DR_MISALIGNMENT (DR) is defined.
1159 FOR NOW: No analysis is actually performed. Misalignment is calculated
1160 only for trivial cases. TODO. */
1163 vect_compute_data_ref_alignment (struct data_reference *dr)
1165 tree stmt = DR_STMT (dr);
1166 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1167 tree ref = DR_REF (dr);
1169 tree base, base_addr;
1172 tree aligned_to, alignment;
1174 if (vect_print_dump_info (REPORT_DETAILS))
1175 fprintf (vect_dump, "vect_compute_data_ref_alignment:");
1177 /* Initialize misalignment to unknown. */
1178 SET_DR_MISALIGNMENT (dr, -1);
1180 misalign = DR_INIT (dr);
1181 aligned_to = DR_ALIGNED_TO (dr);
1182 base_addr = DR_BASE_ADDRESS (dr);
1183 base = build_fold_indirect_ref (base_addr);
1184 vectype = STMT_VINFO_VECTYPE (stmt_info);
1185 alignment = ssize_int (TYPE_ALIGN (vectype)/BITS_PER_UNIT);
1187 if (tree_int_cst_compare (aligned_to, alignment) < 0)
1189 if (vect_print_dump_info (REPORT_DETAILS))
1191 fprintf (vect_dump, "Unknown alignment for access: ");
1192 print_generic_expr (vect_dump, base, TDF_SLIM);
1198 && tree_int_cst_compare (ssize_int (DECL_ALIGN_UNIT (base)),
1200 || (TREE_CODE (base_addr) == SSA_NAME
1201 && tree_int_cst_compare (ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (
1202 TREE_TYPE (base_addr)))),
1204 base_aligned = true;
1206 base_aligned = false;
1210 /* Do not change the alignment of global variables if
1211 flag_section_anchors is enabled. */
1212 if (!vect_can_force_dr_alignment_p (base, TYPE_ALIGN (vectype))
1213 || (TREE_STATIC (base) && flag_section_anchors))
1215 if (vect_print_dump_info (REPORT_DETAILS))
1217 fprintf (vect_dump, "can't force alignment of ref: ");
1218 print_generic_expr (vect_dump, ref, TDF_SLIM);
1223 /* Force the alignment of the decl.
1224 NOTE: This is the only change to the code we make during
1225 the analysis phase, before deciding to vectorize the loop. */
1226 if (vect_print_dump_info (REPORT_DETAILS))
1227 fprintf (vect_dump, "force alignment");
1228 DECL_ALIGN (base) = TYPE_ALIGN (vectype);
1229 DECL_USER_ALIGN (base) = 1;
1232 /* At this point we assume that the base is aligned. */
1233 gcc_assert (base_aligned
1234 || (TREE_CODE (base) == VAR_DECL
1235 && DECL_ALIGN (base) >= TYPE_ALIGN (vectype)));
1237 /* Modulo alignment. */
1238 misalign = size_binop (TRUNC_MOD_EXPR, misalign, alignment);
1240 if (!host_integerp (misalign, 1))
1242 /* Negative or overflowed misalignment value. */
1243 if (vect_print_dump_info (REPORT_DETAILS))
1244 fprintf (vect_dump, "unexpected misalign value");
1248 SET_DR_MISALIGNMENT (dr, TREE_INT_CST_LOW (misalign));
1250 if (vect_print_dump_info (REPORT_DETAILS))
1252 fprintf (vect_dump, "misalign = %d bytes of ref ", DR_MISALIGNMENT (dr));
1253 print_generic_expr (vect_dump, ref, TDF_SLIM);
1260 /* Function vect_compute_data_refs_alignment
1262 Compute the misalignment of data references in the loop.
1263 Return FALSE if a data reference is found that cannot be vectorized. */
1266 vect_compute_data_refs_alignment (loop_vec_info loop_vinfo)
1268 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1269 struct data_reference *dr;
1272 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1273 if (!vect_compute_data_ref_alignment (dr))
1280 /* Function vect_update_misalignment_for_peel
1282 DR - the data reference whose misalignment is to be adjusted.
1283 DR_PEEL - the data reference whose misalignment is being made
1284 zero in the vector loop by the peel.
1285 NPEEL - the number of iterations in the peel loop if the misalignment
1286 of DR_PEEL is known at compile time. */
1289 vect_update_misalignment_for_peel (struct data_reference *dr,
1290 struct data_reference *dr_peel, int npeel)
1293 VEC(dr_p,heap) *same_align_drs;
1294 struct data_reference *current_dr;
1295 int dr_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr))));
1296 int dr_peel_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr_peel))));
1297 stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));
1298 stmt_vec_info peel_stmt_info = vinfo_for_stmt (DR_STMT (dr_peel));
1300 /* For interleaved data accesses the step in the loop must be multiplied by
1301 the size of the interleaving group. */
1302 if (DR_GROUP_FIRST_DR (stmt_info))
1303 dr_size *= DR_GROUP_SIZE (vinfo_for_stmt (DR_GROUP_FIRST_DR (stmt_info)));
1304 if (DR_GROUP_FIRST_DR (peel_stmt_info))
1305 dr_peel_size *= DR_GROUP_SIZE (peel_stmt_info);
1307 /* It can be assumed that the data refs with the same alignment as dr_peel
1308 are aligned in the vector loop. */
1310 = STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (DR_STMT (dr_peel)));
1311 for (i = 0; VEC_iterate (dr_p, same_align_drs, i, current_dr); i++)
1313 if (current_dr != dr)
1315 gcc_assert (DR_MISALIGNMENT (dr) / dr_size ==
1316 DR_MISALIGNMENT (dr_peel) / dr_peel_size);
1317 SET_DR_MISALIGNMENT (dr, 0);
1321 if (known_alignment_for_access_p (dr)
1322 && known_alignment_for_access_p (dr_peel))
1324 int misal = DR_MISALIGNMENT (dr);
1325 misal += npeel * dr_size;
1326 misal %= UNITS_PER_SIMD_WORD;
1327 SET_DR_MISALIGNMENT (dr, misal);
1331 if (vect_print_dump_info (REPORT_DETAILS))
1332 fprintf (vect_dump, "Setting misalignment to -1.");
1333 SET_DR_MISALIGNMENT (dr, -1);
1337 /* Function vect_verify_datarefs_alignment
1339 Return TRUE if all data references in the loop can be
1340 handled with respect to alignment. */
1343 vect_verify_datarefs_alignment (loop_vec_info loop_vinfo)
1345 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1346 struct data_reference *dr;
1347 enum dr_alignment_support supportable_dr_alignment;
1350 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1352 tree stmt = DR_STMT (dr);
1353 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1355 /* For interleaving, only the alignment of the first access matters. */
1356 if (DR_GROUP_FIRST_DR (stmt_info)
1357 && DR_GROUP_FIRST_DR (stmt_info) != stmt)
1360 supportable_dr_alignment = vect_supportable_dr_alignment (dr);
1361 if (!supportable_dr_alignment)
1363 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1365 if (DR_IS_READ (dr))
1367 "not vectorized: unsupported unaligned load.");
1370 "not vectorized: unsupported unaligned store.");
1374 if (supportable_dr_alignment != dr_aligned
1375 && vect_print_dump_info (REPORT_ALIGNMENT))
1376 fprintf (vect_dump, "Vectorizing an unaligned access.");
1382 /* Function vector_alignment_reachable_p
1384 Return true if vector alignment for DR is reachable by peeling
1385 a few loop iterations. Return false otherwise. */
1388 vector_alignment_reachable_p (struct data_reference *dr)
1390 tree stmt = DR_STMT (dr);
1391 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1392 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1394 if (DR_GROUP_FIRST_DR (stmt_info))
1396 /* For interleaved access we peel only if number of iterations in
1397 the prolog loop ({VF - misalignment}), is a multiple of the
1398 number of the interleaved accesses. */
1399 int elem_size, mis_in_elements;
1400 int nelements = TYPE_VECTOR_SUBPARTS (vectype);
1402 /* FORNOW: handle only known alignment. */
1403 if (!known_alignment_for_access_p (dr))
1406 elem_size = UNITS_PER_SIMD_WORD / nelements;
1407 mis_in_elements = DR_MISALIGNMENT (dr) / elem_size;
1409 if ((nelements - mis_in_elements) % DR_GROUP_SIZE (stmt_info))
1413 /* If misalignment is known at the compile time then allow peeling
1414 only if natural alignment is reachable through peeling. */
1415 if (known_alignment_for_access_p (dr) && !aligned_access_p (dr))
1417 HOST_WIDE_INT elmsize =
1418 int_cst_value (TYPE_SIZE_UNIT (TREE_TYPE (vectype)));
1419 if (vect_print_dump_info (REPORT_DETAILS))
1421 fprintf (vect_dump, "data size =" HOST_WIDE_INT_PRINT_DEC, elmsize);
1422 fprintf (vect_dump, ". misalignment = %d. ", DR_MISALIGNMENT (dr));
1424 if (DR_MISALIGNMENT (dr) % elmsize)
1426 if (vect_print_dump_info (REPORT_DETAILS))
1427 fprintf (vect_dump, "data size does not divide the misalignment.\n");
1432 if (!known_alignment_for_access_p (dr))
1434 tree type = (TREE_TYPE (DR_REF (dr)));
1435 tree ba = DR_BASE_OBJECT (dr);
1436 bool is_packed = false;
1439 is_packed = contains_packed_reference (ba);
1441 if (vect_print_dump_info (REPORT_DETAILS))
1442 fprintf (vect_dump, "Unknown misalignment, is_packed = %d",is_packed);
1443 if (targetm.vectorize.vector_alignment_reachable (type, is_packed))
1452 /* Function vect_enhance_data_refs_alignment
1454 This pass will use loop versioning and loop peeling in order to enhance
1455 the alignment of data references in the loop.
1457 FOR NOW: we assume that whatever versioning/peeling takes place, only the
1458 original loop is to be vectorized; Any other loops that are created by
1459 the transformations performed in this pass - are not supposed to be
1460 vectorized. This restriction will be relaxed.
1462 This pass will require a cost model to guide it whether to apply peeling
1463 or versioning or a combination of the two. For example, the scheme that
1464 intel uses when given a loop with several memory accesses, is as follows:
1465 choose one memory access ('p') which alignment you want to force by doing
1466 peeling. Then, either (1) generate a loop in which 'p' is aligned and all
1467 other accesses are not necessarily aligned, or (2) use loop versioning to
1468 generate one loop in which all accesses are aligned, and another loop in
1469 which only 'p' is necessarily aligned.
1471 ("Automatic Intra-Register Vectorization for the Intel Architecture",
1472 Aart J.C. Bik, Milind Girkar, Paul M. Grey and Ximmin Tian, International
1473 Journal of Parallel Programming, Vol. 30, No. 2, April 2002.)
1475 Devising a cost model is the most critical aspect of this work. It will
1476 guide us on which access to peel for, whether to use loop versioning, how
1477 many versions to create, etc. The cost model will probably consist of
1478 generic considerations as well as target specific considerations (on
1479 powerpc for example, misaligned stores are more painful than misaligned
1482 Here are the general steps involved in alignment enhancements:
1484 -- original loop, before alignment analysis:
1485 for (i=0; i<N; i++){
1486 x = q[i]; # DR_MISALIGNMENT(q) = unknown
1487 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1490 -- After vect_compute_data_refs_alignment:
1491 for (i=0; i<N; i++){
1492 x = q[i]; # DR_MISALIGNMENT(q) = 3
1493 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1496 -- Possibility 1: we do loop versioning:
1498 for (i=0; i<N; i++){ # loop 1A
1499 x = q[i]; # DR_MISALIGNMENT(q) = 3
1500 p[i] = y; # DR_MISALIGNMENT(p) = 0
1504 for (i=0; i<N; i++){ # loop 1B
1505 x = q[i]; # DR_MISALIGNMENT(q) = 3
1506 p[i] = y; # DR_MISALIGNMENT(p) = unaligned
1510 -- Possibility 2: we do loop peeling:
1511 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
1515 for (i = 3; i < N; i++){ # loop 2A
1516 x = q[i]; # DR_MISALIGNMENT(q) = 0
1517 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1520 -- Possibility 3: combination of loop peeling and versioning:
1521 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
1526 for (i = 3; i<N; i++){ # loop 3A
1527 x = q[i]; # DR_MISALIGNMENT(q) = 0
1528 p[i] = y; # DR_MISALIGNMENT(p) = 0
1532 for (i = 3; i<N; i++){ # loop 3B
1533 x = q[i]; # DR_MISALIGNMENT(q) = 0
1534 p[i] = y; # DR_MISALIGNMENT(p) = unaligned
1538 These loops are later passed to loop_transform to be vectorized. The
1539 vectorizer will use the alignment information to guide the transformation
1540 (whether to generate regular loads/stores, or with special handling for
1544 vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo)
1546 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1547 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1548 enum dr_alignment_support supportable_dr_alignment;
1549 struct data_reference *dr0 = NULL;
1550 struct data_reference *dr;
1552 bool do_peeling = false;
1553 bool do_versioning = false;
1556 stmt_vec_info stmt_info;
1558 if (vect_print_dump_info (REPORT_DETAILS))
1559 fprintf (vect_dump, "=== vect_enhance_data_refs_alignment ===");
1561 /* While cost model enhancements are expected in the future, the high level
1562 view of the code at this time is as follows:
1564 A) If there is a misaligned write then see if peeling to align this write
1565 can make all data references satisfy vect_supportable_dr_alignment.
1566 If so, update data structures as needed and return true. Note that
1567 at this time vect_supportable_dr_alignment is known to return false
1568 for a misaligned write.
1570 B) If peeling wasn't possible and there is a data reference with an
1571 unknown misalignment that does not satisfy vect_supportable_dr_alignment
1572 then see if loop versioning checks can be used to make all data
1573 references satisfy vect_supportable_dr_alignment. If so, update
1574 data structures as needed and return true.
1576 C) If neither peeling nor versioning were successful then return false if
1577 any data reference does not satisfy vect_supportable_dr_alignment.
1579 D) Return true (all data references satisfy vect_supportable_dr_alignment).
1581 Note, Possibility 3 above (which is peeling and versioning together) is not
1582 being done at this time. */
1584 /* (1) Peeling to force alignment. */
1586 /* (1.1) Decide whether to perform peeling, and how many iterations to peel:
1588 + How many accesses will become aligned due to the peeling
1589 - How many accesses will become unaligned due to the peeling,
1590 and the cost of misaligned accesses.
1591 - The cost of peeling (the extra runtime checks, the increase
1594 The scheme we use FORNOW: peel to force the alignment of the first
1595 misaligned store in the loop.
1596 Rationale: misaligned stores are not yet supported.
1598 TODO: Use a cost model. */
1600 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1602 stmt = DR_STMT (dr);
1603 stmt_info = vinfo_for_stmt (stmt);
1605 /* For interleaving, only the alignment of the first access
1607 if (DR_GROUP_FIRST_DR (stmt_info)
1608 && DR_GROUP_FIRST_DR (stmt_info) != stmt)
1611 if (!DR_IS_READ (dr) && !aligned_access_p (dr))
1613 do_peeling = vector_alignment_reachable_p (dr);
1616 if (!do_peeling && vect_print_dump_info (REPORT_DETAILS))
1617 fprintf (vect_dump, "vector alignment may not be reachable");
1622 /* Often peeling for alignment will require peeling for loop-bound, which in
1623 turn requires that we know how to adjust the loop ivs after the loop. */
1624 if (!vect_can_advance_ivs_p (loop_vinfo)
1625 || !slpeel_can_duplicate_loop_p (loop, single_exit (loop)))
1632 tree stmt = DR_STMT (dr0);
1633 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1634 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1635 int nelements = TYPE_VECTOR_SUBPARTS (vectype);
1637 if (known_alignment_for_access_p (dr0))
1639 /* Since it's known at compile time, compute the number of iterations
1640 in the peeled loop (the peeling factor) for use in updating
1641 DR_MISALIGNMENT values. The peeling factor is the vectorization
1642 factor minus the misalignment as an element count. */
1643 mis = DR_MISALIGNMENT (dr0);
1644 mis /= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr0))));
1645 npeel = nelements - mis;
1647 /* For interleaved data access every iteration accesses all the
1648 members of the group, therefore we divide the number of iterations
1649 by the group size. */
1650 stmt_info = vinfo_for_stmt (DR_STMT (dr0));
1651 if (DR_GROUP_FIRST_DR (stmt_info))
1652 npeel /= DR_GROUP_SIZE (stmt_info);
1654 if (vect_print_dump_info (REPORT_DETAILS))
1655 fprintf (vect_dump, "Try peeling by %d", npeel);
1658 /* Ensure that all data refs can be vectorized after the peel. */
1659 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1661 int save_misalignment;
1666 stmt = DR_STMT (dr);
1667 stmt_info = vinfo_for_stmt (stmt);
1668 /* For interleaving, only the alignment of the first access
1670 if (DR_GROUP_FIRST_DR (stmt_info)
1671 && DR_GROUP_FIRST_DR (stmt_info) != stmt)
1674 save_misalignment = DR_MISALIGNMENT (dr);
1675 vect_update_misalignment_for_peel (dr, dr0, npeel);
1676 supportable_dr_alignment = vect_supportable_dr_alignment (dr);
1677 SET_DR_MISALIGNMENT (dr, save_misalignment);
1679 if (!supportable_dr_alignment)
1688 /* (1.2) Update the DR_MISALIGNMENT of each data reference DR_i.
1689 If the misalignment of DR_i is identical to that of dr0 then set
1690 DR_MISALIGNMENT (DR_i) to zero. If the misalignment of DR_i and
1691 dr0 are known at compile time then increment DR_MISALIGNMENT (DR_i)
1692 by the peeling factor times the element size of DR_i (MOD the
1693 vectorization factor times the size). Otherwise, the
1694 misalignment of DR_i must be set to unknown. */
1695 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1697 vect_update_misalignment_for_peel (dr, dr0, npeel);
1699 LOOP_VINFO_UNALIGNED_DR (loop_vinfo) = dr0;
1700 LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) = DR_MISALIGNMENT (dr0);
1701 SET_DR_MISALIGNMENT (dr0, 0);
1702 if (vect_print_dump_info (REPORT_ALIGNMENT))
1703 fprintf (vect_dump, "Alignment of access forced using peeling.");
1705 if (vect_print_dump_info (REPORT_DETAILS))
1706 fprintf (vect_dump, "Peeling for alignment will be applied.");
1708 stat = vect_verify_datarefs_alignment (loop_vinfo);
1715 /* (2) Versioning to force alignment. */
1717 /* Try versioning if:
1718 1) flag_tree_vect_loop_version is TRUE
1719 2) optimize_size is FALSE
1720 3) there is at least one unsupported misaligned data ref with an unknown
1722 4) all misaligned data refs with a known misalignment are supported, and
1723 5) the number of runtime alignment checks is within reason. */
1725 do_versioning = flag_tree_vect_loop_version && (!optimize_size);
1729 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1731 stmt = DR_STMT (dr);
1732 stmt_info = vinfo_for_stmt (stmt);
1734 /* For interleaving, only the alignment of the first access
1736 if (aligned_access_p (dr)
1737 || (DR_GROUP_FIRST_DR (stmt_info)
1738 && DR_GROUP_FIRST_DR (stmt_info) != stmt))
1741 supportable_dr_alignment = vect_supportable_dr_alignment (dr);
1743 if (!supportable_dr_alignment)
1749 if (known_alignment_for_access_p (dr)
1750 || VEC_length (tree,
1751 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo))
1752 >= (unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_CHECKS))
1754 do_versioning = false;
1758 stmt = DR_STMT (dr);
1759 vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
1760 gcc_assert (vectype);
1762 /* The rightmost bits of an aligned address must be zeros.
1763 Construct the mask needed for this test. For example,
1764 GET_MODE_SIZE for the vector mode V4SI is 16 bytes so the
1765 mask must be 15 = 0xf. */
1766 mask = GET_MODE_SIZE (TYPE_MODE (vectype)) - 1;
1768 /* FORNOW: use the same mask to test all potentially unaligned
1769 references in the loop. The vectorizer currently supports
1770 a single vector size, see the reference to
1771 GET_MODE_NUNITS (TYPE_MODE (vectype)) where the
1772 vectorization factor is computed. */
1773 gcc_assert (!LOOP_VINFO_PTR_MASK (loop_vinfo)
1774 || LOOP_VINFO_PTR_MASK (loop_vinfo) == mask);
1775 LOOP_VINFO_PTR_MASK (loop_vinfo) = mask;
1776 VEC_safe_push (tree, heap,
1777 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo),
1782 /* Versioning requires at least one misaligned data reference. */
1783 if (VEC_length (tree, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo)) == 0)
1784 do_versioning = false;
1785 else if (!do_versioning)
1786 VEC_truncate (tree, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo), 0);
1791 VEC(tree,heap) *may_misalign_stmts
1792 = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo);
1795 /* It can now be assumed that the data references in the statements
1796 in LOOP_VINFO_MAY_MISALIGN_STMTS will be aligned in the version
1797 of the loop being vectorized. */
1798 for (i = 0; VEC_iterate (tree, may_misalign_stmts, i, stmt); i++)
1800 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1801 dr = STMT_VINFO_DATA_REF (stmt_info);
1802 SET_DR_MISALIGNMENT (dr, 0);
1803 if (vect_print_dump_info (REPORT_ALIGNMENT))
1804 fprintf (vect_dump, "Alignment of access forced using versioning.");
1807 if (vect_print_dump_info (REPORT_DETAILS))
1808 fprintf (vect_dump, "Versioning for alignment will be applied.");
1810 /* Peeling and versioning can't be done together at this time. */
1811 gcc_assert (! (do_peeling && do_versioning));
1813 stat = vect_verify_datarefs_alignment (loop_vinfo);
1818 /* This point is reached if neither peeling nor versioning is being done. */
1819 gcc_assert (! (do_peeling || do_versioning));
1821 stat = vect_verify_datarefs_alignment (loop_vinfo);
1826 /* Function vect_analyze_data_refs_alignment
1828 Analyze the alignment of the data-references in the loop.
1829 Return FALSE if a data reference is found that cannot be vectorized. */
1832 vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo)
1834 if (vect_print_dump_info (REPORT_DETAILS))
1835 fprintf (vect_dump, "=== vect_analyze_data_refs_alignment ===");
1837 if (!vect_compute_data_refs_alignment (loop_vinfo))
1839 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1841 "not vectorized: can't calculate alignment for data ref.");
1849 /* Function vect_analyze_data_ref_access.
1851 Analyze the access pattern of the data-reference DR. For now, a data access
1852 has to be consecutive to be considered vectorizable. */
1855 vect_analyze_data_ref_access (struct data_reference *dr)
1857 tree step = DR_STEP (dr);
1858 HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
1859 tree scalar_type = TREE_TYPE (DR_REF (dr));
1860 HOST_WIDE_INT type_size = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type));
1861 tree stmt = DR_STMT (dr);
1862 /* For interleaving, STRIDE is STEP counted in elements, i.e., the size of the
1863 interleaving group (including gaps). */
1864 HOST_WIDE_INT stride = dr_step / type_size;
1868 if (vect_print_dump_info (REPORT_DETAILS))
1869 fprintf (vect_dump, "bad data-ref access");
1874 if (!tree_int_cst_compare (step, TYPE_SIZE_UNIT (scalar_type)))
1876 /* Mark that it is not interleaving. */
1877 DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) = NULL_TREE;
1881 /* Not consecutive access is possible only if it is a part of interleaving. */
1882 if (!DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)))
1884 /* Check if it this DR is a part of interleaving, and is a single
1885 element of the group that is accessed in the loop. */
1887 /* Gaps are supported only for loads. STEP must be a multiple of the type
1888 size. The size of the group must be a power of 2. */
1890 && (dr_step % type_size) == 0
1892 && exact_log2 (stride) != -1)
1894 DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) = stmt;
1895 DR_GROUP_SIZE (vinfo_for_stmt (stmt)) = stride;
1896 if (vect_print_dump_info (REPORT_DR_DETAILS))
1898 fprintf (vect_dump, "Detected single element interleaving %d ",
1899 DR_GROUP_SIZE (vinfo_for_stmt (stmt)));
1900 print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM);
1901 fprintf (vect_dump, " step ");
1902 print_generic_expr (vect_dump, step, TDF_SLIM);
1906 if (vect_print_dump_info (REPORT_DETAILS))
1907 fprintf (vect_dump, "not consecutive access");
1911 if (DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) == stmt)
1913 /* First stmt in the interleaving chain. Check the chain. */
1914 tree next = DR_GROUP_NEXT_DR (vinfo_for_stmt (stmt));
1915 struct data_reference *data_ref = dr;
1916 unsigned int count = 1;
1918 tree prev_init = DR_INIT (data_ref);
1920 HOST_WIDE_INT diff, count_in_bytes;
1924 /* Skip same data-refs. In case that two or more stmts share data-ref
1925 (supported only for loads), we vectorize only the first stmt, and
1926 the rest get their vectorized loads from the first one. */
1927 if (!tree_int_cst_compare (DR_INIT (data_ref),
1928 DR_INIT (STMT_VINFO_DATA_REF (
1929 vinfo_for_stmt (next)))))
1931 if (!DR_IS_READ (data_ref))
1933 if (vect_print_dump_info (REPORT_DETAILS))
1934 fprintf (vect_dump, "Two store stmts share the same dr.");
1938 /* Check that there is no load-store dependencies for this loads
1939 to prevent a case of load-store-load to the same location. */
1940 if (DR_GROUP_READ_WRITE_DEPENDENCE (vinfo_for_stmt (next))
1941 || DR_GROUP_READ_WRITE_DEPENDENCE (vinfo_for_stmt (prev)))
1943 if (vect_print_dump_info (REPORT_DETAILS))
1945 "READ_WRITE dependence in interleaving.");
1949 /* For load use the same data-ref load. */
1950 DR_GROUP_SAME_DR_STMT (vinfo_for_stmt (next)) = prev;
1953 next = DR_GROUP_NEXT_DR (vinfo_for_stmt (next));
1958 /* Check that all the accesses have the same STEP. */
1959 next_step = DR_STEP (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
1960 if (tree_int_cst_compare (step, next_step))
1962 if (vect_print_dump_info (REPORT_DETAILS))
1963 fprintf (vect_dump, "not consecutive access in interleaving");
1967 data_ref = STMT_VINFO_DATA_REF (vinfo_for_stmt (next));
1968 /* Check that the distance between two accesses is equal to the type
1969 size. Otherwise, we have gaps. */
1970 diff = (TREE_INT_CST_LOW (DR_INIT (data_ref))
1971 - TREE_INT_CST_LOW (prev_init)) / type_size;
1972 if (!DR_IS_READ (data_ref) && diff != 1)
1974 if (vect_print_dump_info (REPORT_DETAILS))
1975 fprintf (vect_dump, "interleaved store with gaps");
1978 /* Store the gap from the previous member of the group. If there is no
1979 gap in the access, DR_GROUP_GAP is always 1. */
1980 DR_GROUP_GAP (vinfo_for_stmt (next)) = diff;
1982 prev_init = DR_INIT (data_ref);
1983 next = DR_GROUP_NEXT_DR (vinfo_for_stmt (next));
1984 /* Count the number of data-refs in the chain. */
1988 /* COUNT is the number of accesses found, we multiply it by the size of
1989 the type to get COUNT_IN_BYTES. */
1990 count_in_bytes = type_size * count;
1992 /* Check that the size of the interleaving is not greater than STEP. */
1993 if (dr_step < count_in_bytes)
1995 if (vect_print_dump_info (REPORT_DETAILS))
1997 fprintf (vect_dump, "interleaving size is greater than step for ");
1998 print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM);
2003 /* Check that the size of the interleaving is equal to STEP for stores,
2004 i.e., that there are no gaps. */
2005 if (!DR_IS_READ (dr) && dr_step != count_in_bytes)
2007 if (vect_print_dump_info (REPORT_DETAILS))
2008 fprintf (vect_dump, "interleaved store with gaps");
2012 /* Check that STEP is a multiple of type size. */
2013 if ((dr_step % type_size) != 0)
2015 if (vect_print_dump_info (REPORT_DETAILS))
2017 fprintf (vect_dump, "step is not a multiple of type size: step ");
2018 print_generic_expr (vect_dump, step, TDF_SLIM);
2019 fprintf (vect_dump, " size ");
2020 print_generic_expr (vect_dump, TYPE_SIZE_UNIT (scalar_type),
2026 /* FORNOW: we handle only interleaving that is a power of 2. */
2027 if (exact_log2 (stride) == -1)
2029 if (vect_print_dump_info (REPORT_DETAILS))
2030 fprintf (vect_dump, "interleaving is not a power of 2");
2033 DR_GROUP_SIZE (vinfo_for_stmt (stmt)) = stride;
2039 /* Function vect_analyze_data_ref_accesses.
2041 Analyze the access pattern of all the data references in the loop.
2043 FORNOW: the only access pattern that is considered vectorizable is a
2044 simple step 1 (consecutive) access.
2046 FORNOW: handle only arrays and pointer accesses. */
2049 vect_analyze_data_ref_accesses (loop_vec_info loop_vinfo)
2052 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
2053 struct data_reference *dr;
2055 if (vect_print_dump_info (REPORT_DETAILS))
2056 fprintf (vect_dump, "=== vect_analyze_data_ref_accesses ===");
2058 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
2059 if (!vect_analyze_data_ref_access (dr))
2061 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2062 fprintf (vect_dump, "not vectorized: complicated access pattern.");
2070 /* Function vect_analyze_data_refs.
2072 Find all the data references in the loop.
2074 The general structure of the analysis of data refs in the vectorizer is as
2076 1- vect_analyze_data_refs(loop): call compute_data_dependences_for_loop to
2077 find and analyze all data-refs in the loop and their dependences.
2078 2- vect_analyze_dependences(): apply dependence testing using ddrs.
2079 3- vect_analyze_drs_alignment(): check that ref_stmt.alignment is ok.
2080 4- vect_analyze_drs_access(): check that ref_stmt.step is ok.
2085 vect_analyze_data_refs (loop_vec_info loop_vinfo)
2087 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2089 VEC (data_reference_p, heap) *datarefs;
2090 struct data_reference *dr;
2093 if (vect_print_dump_info (REPORT_DETAILS))
2094 fprintf (vect_dump, "=== vect_analyze_data_refs ===\n");
2096 compute_data_dependences_for_loop (loop, true,
2097 &LOOP_VINFO_DATAREFS (loop_vinfo),
2098 &LOOP_VINFO_DDRS (loop_vinfo));
2100 /* Go through the data-refs, check that the analysis succeeded. Update pointer
2101 from stmt_vec_info struct to DR and vectype. */
2102 datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
2104 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
2107 stmt_vec_info stmt_info;
2109 if (!dr || !DR_REF (dr))
2111 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2112 fprintf (vect_dump, "not vectorized: unhandled data-ref ");
2116 /* Update DR field in stmt_vec_info struct. */
2117 stmt = DR_STMT (dr);
2118 stmt_info = vinfo_for_stmt (stmt);
2120 if (STMT_VINFO_DATA_REF (stmt_info))
2122 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2125 "not vectorized: more than one data ref in stmt: ");
2126 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2130 STMT_VINFO_DATA_REF (stmt_info) = dr;
2132 /* Check that analysis of the data-ref succeeded. */
2133 if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr) || !DR_INIT (dr)
2136 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2138 fprintf (vect_dump, "not vectorized: data ref analysis failed ");
2139 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2144 if (TREE_CODE (DR_BASE_ADDRESS (dr)) == INTEGER_CST)
2146 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2147 fprintf (vect_dump, "not vectorized: base addr of dr is a "
2152 if (!DR_SYMBOL_TAG (dr))
2154 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2156 fprintf (vect_dump, "not vectorized: no memory tag for ");
2157 print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM);
2162 /* Set vectype for STMT. */
2163 scalar_type = TREE_TYPE (DR_REF (dr));
2164 STMT_VINFO_VECTYPE (stmt_info) =
2165 get_vectype_for_scalar_type (scalar_type);
2166 if (!STMT_VINFO_VECTYPE (stmt_info))
2168 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2171 "not vectorized: no vectype for stmt: ");
2172 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2173 fprintf (vect_dump, " scalar_type: ");
2174 print_generic_expr (vect_dump, scalar_type, TDF_DETAILS);
2184 /* Utility functions used by vect_mark_stmts_to_be_vectorized. */
2186 /* Function vect_mark_relevant.
2188 Mark STMT as "relevant for vectorization" and add it to WORKLIST. */
2191 vect_mark_relevant (VEC(tree,heap) **worklist, tree stmt,
2192 enum vect_relevant relevant, bool live_p)
2194 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2195 enum vect_relevant save_relevant = STMT_VINFO_RELEVANT (stmt_info);
2196 bool save_live_p = STMT_VINFO_LIVE_P (stmt_info);
2198 if (vect_print_dump_info (REPORT_DETAILS))
2199 fprintf (vect_dump, "mark relevant %d, live %d.", relevant, live_p);
2201 if (STMT_VINFO_IN_PATTERN_P (stmt_info))
2205 /* This is the last stmt in a sequence that was detected as a
2206 pattern that can potentially be vectorized. Don't mark the stmt
2207 as relevant/live because it's not going to vectorized.
2208 Instead mark the pattern-stmt that replaces it. */
2209 if (vect_print_dump_info (REPORT_DETAILS))
2210 fprintf (vect_dump, "last stmt in pattern. don't mark relevant/live.");
2211 pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
2212 stmt_info = vinfo_for_stmt (pattern_stmt);
2213 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_info) == stmt);
2214 save_relevant = STMT_VINFO_RELEVANT (stmt_info);
2215 save_live_p = STMT_VINFO_LIVE_P (stmt_info);
2216 stmt = pattern_stmt;
2219 STMT_VINFO_LIVE_P (stmt_info) |= live_p;
2220 if (relevant > STMT_VINFO_RELEVANT (stmt_info))
2221 STMT_VINFO_RELEVANT (stmt_info) = relevant;
2223 if (STMT_VINFO_RELEVANT (stmt_info) == save_relevant
2224 && STMT_VINFO_LIVE_P (stmt_info) == save_live_p)
2226 if (vect_print_dump_info (REPORT_DETAILS))
2227 fprintf (vect_dump, "already marked relevant/live.");
2231 VEC_safe_push (tree, heap, *worklist, stmt);
2235 /* Function vect_stmt_relevant_p.
2237 Return true if STMT in loop that is represented by LOOP_VINFO is
2238 "relevant for vectorization".
2240 A stmt is considered "relevant for vectorization" if:
2241 - it has uses outside the loop.
2242 - it has vdefs (it alters memory).
2243 - control stmts in the loop (except for the exit condition).
2245 CHECKME: what other side effects would the vectorizer allow? */
2248 vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo,
2249 enum vect_relevant *relevant, bool *live_p)
2251 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2252 ssa_op_iter op_iter;
2253 imm_use_iterator imm_iter;
2254 use_operand_p use_p;
2255 def_operand_p def_p;
2257 *relevant = vect_unused_in_loop;
2260 /* cond stmt other than loop exit cond. */
2261 if (is_ctrl_stmt (stmt) && (stmt != LOOP_VINFO_EXIT_COND (loop_vinfo)))
2262 *relevant = vect_used_in_loop;
2264 /* changing memory. */
2265 if (TREE_CODE (stmt) != PHI_NODE)
2266 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
2268 if (vect_print_dump_info (REPORT_DETAILS))
2269 fprintf (vect_dump, "vec_stmt_relevant_p: stmt has vdefs.");
2270 *relevant = vect_used_in_loop;
2273 /* uses outside the loop. */
2274 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_DEF)
2276 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
2278 basic_block bb = bb_for_stmt (USE_STMT (use_p));
2279 if (!flow_bb_inside_loop_p (loop, bb))
2281 if (vect_print_dump_info (REPORT_DETAILS))
2282 fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop.");
2284 /* We expect all such uses to be in the loop exit phis
2285 (because of loop closed form) */
2286 gcc_assert (TREE_CODE (USE_STMT (use_p)) == PHI_NODE);
2287 gcc_assert (bb == single_exit (loop)->dest);
2294 return (*live_p || *relevant);
2299 Function process_use.
2302 - a USE in STMT in a loop represented by LOOP_VINFO
2303 - LIVE_P, RELEVANT - enum values to be set in the STMT_VINFO of the stmt
2304 that defined USE. This is dont by calling mark_relevant and passing it
2305 the WORKLIST (to add DEF_STMT to the WORKlist in case itis relevant).
2308 Generally, LIVE_P and RELEVANT are used to define the liveness and
2309 relevance info of the DEF_STMT of this USE:
2310 STMT_VINFO_LIVE_P (DEF_STMT_info) <-- live_p
2311 STMT_VINFO_RELEVANT (DEF_STMT_info) <-- relevant
2313 - case 1: If USE is used only for address computations (e.g. array indexing),
2314 which does not need to be directly vectorized, then the liveness/relevance
2315 of the respective DEF_STMT is left unchanged.
2316 - case 2: If STMT is a reduction phi and DEF_STMT is a reduction stmt, we
2317 skip DEF_STMT cause it had already been processed.
2319 Return true if everything is as expected. Return false otherwise. */
2322 process_use (tree stmt, tree use, loop_vec_info loop_vinfo, bool live_p,
2323 enum vect_relevant relevant, VEC(tree,heap) **worklist)
2325 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2326 stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
2327 stmt_vec_info dstmt_vinfo;
2330 enum vect_def_type dt;
2332 /* case 1: we are only interested in uses that need to be vectorized. Uses
2333 that are used for address computation are not considered relevant. */
2334 if (!exist_non_indexing_operands_for_use_p (use, stmt))
2337 if (!vect_is_simple_use (use, loop_vinfo, &def_stmt, &def, &dt))
2339 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2340 fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
2344 if (!def_stmt || IS_EMPTY_STMT (def_stmt))
2347 def_bb = bb_for_stmt (def_stmt);
2348 if (!flow_bb_inside_loop_p (loop, def_bb))
2351 /* case 2: A reduction phi defining a reduction stmt (DEF_STMT). DEF_STMT
2352 must have already been processed, so we just check that everything is as
2353 expected, and we are done. */
2354 dstmt_vinfo = vinfo_for_stmt (def_stmt);
2355 if (TREE_CODE (stmt) == PHI_NODE
2356 && STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def
2357 && TREE_CODE (def_stmt) != PHI_NODE
2358 && STMT_VINFO_DEF_TYPE (dstmt_vinfo) == vect_reduction_def)
2360 if (STMT_VINFO_IN_PATTERN_P (dstmt_vinfo))
2361 dstmt_vinfo = vinfo_for_stmt (STMT_VINFO_RELATED_STMT (dstmt_vinfo));
2362 gcc_assert (STMT_VINFO_RELEVANT (dstmt_vinfo) < vect_used_by_reduction);
2363 gcc_assert (STMT_VINFO_LIVE_P (dstmt_vinfo)
2364 || STMT_VINFO_RELEVANT (dstmt_vinfo) > vect_unused_in_loop);
2368 vect_mark_relevant (worklist, def_stmt, relevant, live_p);
2373 /* Function vect_mark_stmts_to_be_vectorized.
2375 Not all stmts in the loop need to be vectorized. For example:
2384 Stmt 1 and 3 do not need to be vectorized, because loop control and
2385 addressing of vectorized data-refs are handled differently.
2387 This pass detects such stmts. */
2390 vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo)
2392 VEC(tree,heap) *worklist;
2393 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2394 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
2395 unsigned int nbbs = loop->num_nodes;
2396 block_stmt_iterator si;
2400 stmt_vec_info stmt_vinfo;
2404 enum vect_relevant relevant;
2406 if (vect_print_dump_info (REPORT_DETAILS))
2407 fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ===");
2409 worklist = VEC_alloc (tree, heap, 64);
2411 /* 1. Init worklist. */
2412 for (i = 0; i < nbbs; i++)
2415 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2417 if (vect_print_dump_info (REPORT_DETAILS))
2419 fprintf (vect_dump, "init: phi relevant? ");
2420 print_generic_expr (vect_dump, phi, TDF_SLIM);
2423 if (vect_stmt_relevant_p (phi, loop_vinfo, &relevant, &live_p))
2424 vect_mark_relevant (&worklist, phi, relevant, live_p);
2426 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2428 stmt = bsi_stmt (si);
2429 if (vect_print_dump_info (REPORT_DETAILS))
2431 fprintf (vect_dump, "init: stmt relevant? ");
2432 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2435 if (vect_stmt_relevant_p (stmt, loop_vinfo, &relevant, &live_p))
2436 vect_mark_relevant (&worklist, stmt, relevant, live_p);
2440 /* 2. Process_worklist */
2441 while (VEC_length (tree, worklist) > 0)
2443 use_operand_p use_p;
2446 stmt = VEC_pop (tree, worklist);
2447 if (vect_print_dump_info (REPORT_DETAILS))
2449 fprintf (vect_dump, "worklist: examine stmt: ");
2450 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2453 /* Examine the USEs of STMT. For each USE, mark the stmt that defines it
2454 (DEF_STMT) as relevant/irrelevant and live/dead according to the
2455 liveness and relevance properties of STMT. */
2456 ann = stmt_ann (stmt);
2457 stmt_vinfo = vinfo_for_stmt (stmt);
2458 relevant = STMT_VINFO_RELEVANT (stmt_vinfo);
2459 live_p = STMT_VINFO_LIVE_P (stmt_vinfo);
2461 /* Generally, the liveness and relevance properties of STMT are
2462 propagated as is to the DEF_STMTs of its USEs:
2463 live_p <-- STMT_VINFO_LIVE_P (STMT_VINFO)
2464 relevant <-- STMT_VINFO_RELEVANT (STMT_VINFO)
2466 One exception is when STMT has been identified as defining a reduction
2467 variable; in this case we set the liveness/relevance as follows:
2469 relevant = vect_used_by_reduction
2470 This is because we distinguish between two kinds of relevant stmts -
2471 those that are used by a reduction computation, and those that are
2472 (also) used by a regular computation. This allows us later on to
2473 identify stmts that are used solely by a reduction, and therefore the
2474 order of the results that they produce does not have to be kept.
2476 Reduction phis are expected to be used by a reduction stmt; Other
2477 reduction stmts are expected to be unused in the loop. These are the
2478 expected values of "relevant" for reduction phis/stmts in the loop:
2481 vect_unused_in_loop ok
2482 vect_used_by_reduction ok
2483 vect_used_in_loop */
2485 if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def)
2489 case vect_unused_in_loop:
2490 gcc_assert (TREE_CODE (stmt) != PHI_NODE);
2492 case vect_used_by_reduction:
2493 if (TREE_CODE (stmt) == PHI_NODE)
2495 case vect_used_in_loop:
2497 if (vect_print_dump_info (REPORT_DETAILS))
2498 fprintf (vect_dump, "unsupported use of reduction.");
2499 VEC_free (tree, heap, worklist);
2502 relevant = vect_used_by_reduction;
2506 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2508 tree op = USE_FROM_PTR (use_p);
2509 if (!process_use (stmt, op, loop_vinfo, live_p, relevant, &worklist))
2511 VEC_free (tree, heap, worklist);
2515 } /* while worklist */
2517 VEC_free (tree, heap, worklist);
2522 /* Function vect_can_advance_ivs_p
2524 In case the number of iterations that LOOP iterates is unknown at compile
2525 time, an epilog loop will be generated, and the loop induction variables
2526 (IVs) will be "advanced" to the value they are supposed to take just before
2527 the epilog loop. Here we check that the access function of the loop IVs
2528 and the expression that represents the loop bound are simple enough.
2529 These restrictions will be relaxed in the future. */
2532 vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
2534 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2535 basic_block bb = loop->header;
2538 /* Analyze phi functions of the loop header. */
2540 if (vect_print_dump_info (REPORT_DETAILS))
2541 fprintf (vect_dump, "vect_can_advance_ivs_p:");
2543 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2545 tree access_fn = NULL;
2546 tree evolution_part;
2548 if (vect_print_dump_info (REPORT_DETAILS))
2550 fprintf (vect_dump, "Analyze phi: ");
2551 print_generic_expr (vect_dump, phi, TDF_SLIM);
2554 /* Skip virtual phi's. The data dependences that are associated with
2555 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
2557 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
2559 if (vect_print_dump_info (REPORT_DETAILS))
2560 fprintf (vect_dump, "virtual phi. skip.");
2564 /* Skip reduction phis. */
2566 if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (phi)) == vect_reduction_def)
2568 if (vect_print_dump_info (REPORT_DETAILS))
2569 fprintf (vect_dump, "reduc phi. skip.");
2573 /* Analyze the evolution function. */
2575 access_fn = instantiate_parameters
2576 (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2580 if (vect_print_dump_info (REPORT_DETAILS))
2581 fprintf (vect_dump, "No Access function.");
2585 if (vect_print_dump_info (REPORT_DETAILS))
2587 fprintf (vect_dump, "Access function of PHI: ");
2588 print_generic_expr (vect_dump, access_fn, TDF_SLIM);
2591 evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
2593 if (evolution_part == NULL_TREE)
2595 if (vect_print_dump_info (REPORT_DETAILS))
2596 fprintf (vect_dump, "No evolution.");
2600 /* FORNOW: We do not transform initial conditions of IVs
2601 which evolution functions are a polynomial of degree >= 2. */
2603 if (tree_is_chrec (evolution_part))
2611 /* Function vect_get_loop_niters.
2613 Determine how many iterations the loop is executed.
2614 If an expression that represents the number of iterations
2615 can be constructed, place it in NUMBER_OF_ITERATIONS.
2616 Return the loop exit condition. */
2619 vect_get_loop_niters (struct loop *loop, tree *number_of_iterations)
2623 if (vect_print_dump_info (REPORT_DETAILS))
2624 fprintf (vect_dump, "=== get_loop_niters ===");
2626 niters = number_of_exit_cond_executions (loop);
2628 if (niters != NULL_TREE
2629 && niters != chrec_dont_know)
2631 *number_of_iterations = niters;
2633 if (vect_print_dump_info (REPORT_DETAILS))
2635 fprintf (vect_dump, "==> get_loop_niters:" );
2636 print_generic_expr (vect_dump, *number_of_iterations, TDF_SLIM);
2640 return get_loop_exit_condition (loop);
2644 /* Function vect_analyze_loop_form.
2646 Verify the following restrictions (some may be relaxed in the future):
2647 - it's an inner-most loop
2648 - number of BBs = 2 (which are the loop header and the latch)
2649 - the loop has a pre-header
2650 - the loop has a single entry and exit
2651 - the loop exit condition is simple enough, and the number of iterations
2652 can be analyzed (a countable loop). */
2654 static loop_vec_info
2655 vect_analyze_loop_form (struct loop *loop)
2657 loop_vec_info loop_vinfo;
2659 tree number_of_iterations = NULL;
2661 if (vect_print_dump_info (REPORT_DETAILS))
2662 fprintf (vect_dump, "=== vect_analyze_loop_form ===");
2666 if (vect_print_dump_info (REPORT_OUTER_LOOPS))
2667 fprintf (vect_dump, "not vectorized: nested loop.");
2671 if (!single_exit (loop)
2672 || loop->num_nodes != 2
2673 || EDGE_COUNT (loop->header->preds) != 2)
2675 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2677 if (!single_exit (loop))
2678 fprintf (vect_dump, "not vectorized: multiple exits.");
2679 else if (loop->num_nodes != 2)
2680 fprintf (vect_dump, "not vectorized: too many BBs in loop.");
2681 else if (EDGE_COUNT (loop->header->preds) != 2)
2682 fprintf (vect_dump, "not vectorized: too many incoming edges.");
2688 /* We assume that the loop exit condition is at the end of the loop. i.e,
2689 that the loop is represented as a do-while (with a proper if-guard
2690 before the loop if needed), where the loop header contains all the
2691 executable statements, and the latch is empty. */
2692 if (!empty_block_p (loop->latch)
2693 || phi_nodes (loop->latch))
2695 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2696 fprintf (vect_dump, "not vectorized: unexpected loop form.");
2700 /* Make sure there exists a single-predecessor exit bb: */
2701 if (!single_pred_p (single_exit (loop)->dest))
2703 edge e = single_exit (loop);
2704 if (!(e->flags & EDGE_ABNORMAL))
2706 split_loop_exit_edge (e);
2707 if (vect_print_dump_info (REPORT_DETAILS))
2708 fprintf (vect_dump, "split exit edge.");
2712 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2713 fprintf (vect_dump, "not vectorized: abnormal loop exit edge.");
2718 if (empty_block_p (loop->header))
2720 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2721 fprintf (vect_dump, "not vectorized: empty loop.");
2725 loop_cond = vect_get_loop_niters (loop, &number_of_iterations);
2728 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2729 fprintf (vect_dump, "not vectorized: complicated exit condition.");
2733 if (!number_of_iterations)
2735 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2737 "not vectorized: number of iterations cannot be computed.");
2741 if (chrec_contains_undetermined (number_of_iterations))
2743 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2744 fprintf (vect_dump, "Infinite number of iterations.");
2748 if (!NITERS_KNOWN_P (number_of_iterations))
2750 if (vect_print_dump_info (REPORT_DETAILS))
2752 fprintf (vect_dump, "Symbolic number of iterations is ");
2753 print_generic_expr (vect_dump, number_of_iterations, TDF_DETAILS);
2756 else if (TREE_INT_CST_LOW (number_of_iterations) == 0)
2758 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2759 fprintf (vect_dump, "not vectorized: number of iterations = 0.");
2763 loop_vinfo = new_loop_vec_info (loop);
2764 LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
2765 LOOP_VINFO_EXIT_COND (loop_vinfo) = loop_cond;
2767 gcc_assert (!loop->aux);
2768 loop->aux = loop_vinfo;
2773 /* Function vect_analyze_loop.
2775 Apply a set of analyses on LOOP, and create a loop_vec_info struct
2776 for it. The different analyses will record information in the
2777 loop_vec_info struct. */
2779 vect_analyze_loop (struct loop *loop)
2782 loop_vec_info loop_vinfo;
2784 if (vect_print_dump_info (REPORT_DETAILS))
2785 fprintf (vect_dump, "===== analyze_loop_nest =====");
2787 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
2789 loop_vinfo = vect_analyze_loop_form (loop);
2792 if (vect_print_dump_info (REPORT_DETAILS))
2793 fprintf (vect_dump, "bad loop form.");
2797 /* Find all data references in the loop (which correspond to vdefs/vuses)
2798 and analyze their evolution in the loop.
2800 FORNOW: Handle only simple, array references, which
2801 alignment can be forced, and aligned pointer-references. */
2803 ok = vect_analyze_data_refs (loop_vinfo);
2806 if (vect_print_dump_info (REPORT_DETAILS))
2807 fprintf (vect_dump, "bad data references.");
2808 destroy_loop_vec_info (loop_vinfo);
2812 /* Classify all cross-iteration scalar data-flow cycles.
2813 Cross-iteration cycles caused by virtual phis are analyzed separately. */
2815 vect_analyze_scalar_cycles (loop_vinfo);
2817 vect_pattern_recog (loop_vinfo);
2819 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
2821 ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
2824 if (vect_print_dump_info (REPORT_DETAILS))
2825 fprintf (vect_dump, "unexpected pattern.");
2826 destroy_loop_vec_info (loop_vinfo);
2830 /* Analyze the alignment of the data-refs in the loop.
2831 Fail if a data reference is found that cannot be vectorized. */
2833 ok = vect_analyze_data_refs_alignment (loop_vinfo);
2836 if (vect_print_dump_info (REPORT_DETAILS))
2837 fprintf (vect_dump, "bad data alignment.");
2838 destroy_loop_vec_info (loop_vinfo);
2842 ok = vect_determine_vectorization_factor (loop_vinfo);
2845 if (vect_print_dump_info (REPORT_DETAILS))
2846 fprintf (vect_dump, "can't determine vectorization factor.");
2847 destroy_loop_vec_info (loop_vinfo);
2851 /* Analyze data dependences between the data-refs in the loop.
2852 FORNOW: fail at the first data dependence that we encounter. */
2854 ok = vect_analyze_data_ref_dependences (loop_vinfo);
2857 if (vect_print_dump_info (REPORT_DETAILS))
2858 fprintf (vect_dump, "bad data dependence.");
2859 destroy_loop_vec_info (loop_vinfo);
2863 /* Analyze the access patterns of the data-refs in the loop (consecutive,
2864 complex, etc.). FORNOW: Only handle consecutive access pattern. */
2866 ok = vect_analyze_data_ref_accesses (loop_vinfo);
2869 if (vect_print_dump_info (REPORT_DETAILS))
2870 fprintf (vect_dump, "bad data access.");
2871 destroy_loop_vec_info (loop_vinfo);
2875 /* This pass will decide on using loop versioning and/or loop peeling in
2876 order to enhance the alignment of data references in the loop. */
2878 ok = vect_enhance_data_refs_alignment (loop_vinfo);
2881 if (vect_print_dump_info (REPORT_DETAILS))
2882 fprintf (vect_dump, "bad data alignment.");
2883 destroy_loop_vec_info (loop_vinfo);
2887 /* Scan all the operations in the loop and make sure they are
2890 ok = vect_analyze_operations (loop_vinfo);
2893 if (vect_print_dump_info (REPORT_DETAILS))
2894 fprintf (vect_dump, "bad operation or unsupported loop bound.");
2895 destroy_loop_vec_info (loop_vinfo);
2899 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1;