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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
38 #include "tree-chrec.h"
39 #include "tree-data-ref.h"
40 #include "tree-scalar-evolution.h"
41 #include "tree-vectorizer.h"
44 /* Main analysis functions. */
45 static loop_vec_info vect_analyze_loop_form (struct loop *);
46 static bool vect_analyze_data_refs (loop_vec_info);
47 static bool vect_mark_stmts_to_be_vectorized (loop_vec_info);
48 static void vect_analyze_scalar_cycles (loop_vec_info);
49 static bool vect_analyze_data_ref_accesses (loop_vec_info);
50 static bool vect_analyze_data_ref_dependences (loop_vec_info);
51 static bool vect_analyze_data_refs_alignment (loop_vec_info);
52 static bool vect_compute_data_refs_alignment (loop_vec_info);
53 static bool vect_enhance_data_refs_alignment (loop_vec_info);
54 static bool vect_analyze_operations (loop_vec_info);
55 static bool vect_determine_vectorization_factor (loop_vec_info);
57 /* Utility functions for the analyses. */
58 static bool exist_non_indexing_operands_for_use_p (tree, tree);
59 static tree vect_get_loop_niters (struct loop *, tree *);
60 static bool vect_analyze_data_ref_dependence
61 (struct data_dependence_relation *, loop_vec_info);
62 static bool vect_compute_data_ref_alignment (struct data_reference *);
63 static bool vect_analyze_data_ref_access (struct data_reference *);
64 static bool vect_can_advance_ivs_p (loop_vec_info);
65 static void vect_update_misalignment_for_peel
66 (struct data_reference *, struct data_reference *, int npeel);
68 /* Function vect_determine_vectorization_factor
70 Determine the vectorization factor (VF). VF is the number of data elements
71 that are operated upon in parallel in a single iteration of the vectorized
72 loop. For example, when vectorizing a loop that operates on 4byte elements,
73 on a target with vector size (VS) 16byte, the VF is set to 4, since 4
74 elements can fit in a single vector register.
76 We currently support vectorization of loops in which all types operated upon
77 are of the same size. Therefore this function currently sets VF according to
78 the size of the types operated upon, and fails if there are multiple sizes
81 VF is also the factor by which the loop iterations are strip-mined, e.g.:
88 for (i=0; i<N; i+=VF){
89 a[i:VF] = b[i:VF] + c[i:VF];
94 vect_determine_vectorization_factor (loop_vec_info loop_vinfo)
96 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
97 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
98 int nbbs = loop->num_nodes;
99 block_stmt_iterator si;
100 unsigned int vectorization_factor = 0;
105 stmt_vec_info stmt_info;
108 if (vect_print_dump_info (REPORT_DETAILS))
109 fprintf (vect_dump, "=== vect_determine_vectorization_factor ===");
111 for (i = 0; i < nbbs; i++)
113 basic_block bb = bbs[i];
115 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
117 stmt_info = vinfo_for_stmt (phi);
118 if (vect_print_dump_info (REPORT_DETAILS))
120 fprintf (vect_dump, "==> examining phi: ");
121 print_generic_expr (vect_dump, phi, TDF_SLIM);
124 gcc_assert (stmt_info);
126 if (STMT_VINFO_RELEVANT_P (stmt_info))
128 gcc_assert (!STMT_VINFO_VECTYPE (stmt_info));
129 scalar_type = TREE_TYPE (PHI_RESULT (phi));
131 if (vect_print_dump_info (REPORT_DETAILS))
133 fprintf (vect_dump, "get vectype for scalar type: ");
134 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
137 vectype = get_vectype_for_scalar_type (scalar_type);
140 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
143 "not vectorized: unsupported data-type ");
144 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
148 STMT_VINFO_VECTYPE (stmt_info) = vectype;
150 if (vect_print_dump_info (REPORT_DETAILS))
152 fprintf (vect_dump, "vectype: ");
153 print_generic_expr (vect_dump, vectype, TDF_SLIM);
156 nunits = TYPE_VECTOR_SUBPARTS (vectype);
157 if (vect_print_dump_info (REPORT_DETAILS))
158 fprintf (vect_dump, "nunits = %d", nunits);
160 if (!vectorization_factor
161 || (nunits > vectorization_factor))
162 vectorization_factor = nunits;
166 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
168 tree stmt = bsi_stmt (si);
169 stmt_info = vinfo_for_stmt (stmt);
171 if (vect_print_dump_info (REPORT_DETAILS))
173 fprintf (vect_dump, "==> examining statement: ");
174 print_generic_expr (vect_dump, stmt, TDF_SLIM);
177 gcc_assert (stmt_info);
179 /* skip stmts which do not need to be vectorized. */
180 if (!STMT_VINFO_RELEVANT_P (stmt_info)
181 && !STMT_VINFO_LIVE_P (stmt_info))
183 if (vect_print_dump_info (REPORT_DETAILS))
184 fprintf (vect_dump, "skip.");
188 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
190 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
192 fprintf (vect_dump, "not vectorized: irregular stmt.");
193 print_generic_expr (vect_dump, stmt, TDF_SLIM);
198 if (!GIMPLE_STMT_P (stmt)
199 && VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))))
201 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
203 fprintf (vect_dump, "not vectorized: vector stmt in loop:");
204 print_generic_expr (vect_dump, stmt, TDF_SLIM);
209 if (STMT_VINFO_VECTYPE (stmt_info))
211 /* The only case when a vectype had been already set is for stmts
212 that contain a dataref, or for "pattern-stmts" (stmts generated
213 by the vectorizer to represent/replace a certain idiom). */
214 gcc_assert (STMT_VINFO_DATA_REF (stmt_info)
215 || is_pattern_stmt_p (stmt_info));
216 vectype = STMT_VINFO_VECTYPE (stmt_info);
220 gcc_assert (! STMT_VINFO_DATA_REF (stmt_info)
221 && !is_pattern_stmt_p (stmt_info));
223 /* We set the vectype according to the type of the result (lhs).
224 For stmts whose result-type is different than the type of the
225 arguments (e.g. demotion, promotion), vectype will be reset
226 appropriately (later). Note that we have to visit the smallest
227 datatype in this function, because that determines the VF.
228 If the smallest datatype in the loop is present only as the
229 rhs of a promotion operation - we'd miss it here.
230 However, in such a case, that a variable of this datatype
231 does not appear in the lhs anywhere in the loop, it shouldn't
232 affect the vectorization factor. */
233 scalar_type = TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 0));
235 if (vect_print_dump_info (REPORT_DETAILS))
237 fprintf (vect_dump, "get vectype for scalar type: ");
238 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
241 vectype = get_vectype_for_scalar_type (scalar_type);
244 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
247 "not vectorized: unsupported data-type ");
248 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
252 STMT_VINFO_VECTYPE (stmt_info) = vectype;
255 if (vect_print_dump_info (REPORT_DETAILS))
257 fprintf (vect_dump, "vectype: ");
258 print_generic_expr (vect_dump, vectype, TDF_SLIM);
261 nunits = TYPE_VECTOR_SUBPARTS (vectype);
262 if (vect_print_dump_info (REPORT_DETAILS))
263 fprintf (vect_dump, "nunits = %d", nunits);
265 if (!vectorization_factor
266 || (nunits > vectorization_factor))
267 vectorization_factor = nunits;
272 /* TODO: Analyze cost. Decide if worth while to vectorize. */
273 if (vect_print_dump_info (REPORT_DETAILS))
274 fprintf (vect_dump, "vectorization factor = %d", vectorization_factor);
275 if (vectorization_factor <= 1)
277 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
278 fprintf (vect_dump, "not vectorized: unsupported data-type");
281 LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
287 /* Function vect_analyze_operations.
289 Scan the loop stmts and make sure they are all vectorizable. */
292 vect_analyze_operations (loop_vec_info loop_vinfo)
294 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
295 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
296 int nbbs = loop->num_nodes;
297 block_stmt_iterator si;
298 unsigned int vectorization_factor = 0;
302 stmt_vec_info stmt_info;
303 bool need_to_vectorize = false;
304 int min_profitable_iters;
305 int min_scalar_loop_bound;
308 if (vect_print_dump_info (REPORT_DETAILS))
309 fprintf (vect_dump, "=== vect_analyze_operations ===");
311 gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo));
312 vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
314 for (i = 0; i < nbbs; i++)
316 basic_block bb = bbs[i];
318 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
322 stmt_info = vinfo_for_stmt (phi);
323 if (vect_print_dump_info (REPORT_DETAILS))
325 fprintf (vect_dump, "examining phi: ");
326 print_generic_expr (vect_dump, phi, TDF_SLIM);
329 gcc_assert (stmt_info);
331 if (STMT_VINFO_LIVE_P (stmt_info))
333 /* FORNOW: not yet supported. */
334 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
335 fprintf (vect_dump, "not vectorized: value used after loop.");
339 if (STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_loop
340 && STMT_VINFO_DEF_TYPE (stmt_info) != vect_induction_def)
342 /* A scalar-dependence cycle that we don't support. */
343 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
344 fprintf (vect_dump, "not vectorized: scalar dependence cycle.");
348 if (STMT_VINFO_RELEVANT_P (stmt_info))
350 need_to_vectorize = true;
351 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def)
352 ok = vectorizable_induction (phi, NULL, NULL);
357 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
360 "not vectorized: relevant phi not supported: ");
361 print_generic_expr (vect_dump, phi, TDF_SLIM);
367 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
369 tree stmt = bsi_stmt (si);
370 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
371 enum vect_def_type relevance = STMT_VINFO_RELEVANT (stmt_info);
373 if (vect_print_dump_info (REPORT_DETAILS))
375 fprintf (vect_dump, "==> examining statement: ");
376 print_generic_expr (vect_dump, stmt, TDF_SLIM);
379 gcc_assert (stmt_info);
381 /* skip stmts which do not need to be vectorized.
382 this is expected to include:
383 - the COND_EXPR which is the loop exit condition
384 - any LABEL_EXPRs in the loop
385 - computations that are used only for array indexing or loop
388 if (!STMT_VINFO_RELEVANT_P (stmt_info)
389 && !STMT_VINFO_LIVE_P (stmt_info))
391 if (vect_print_dump_info (REPORT_DETAILS))
392 fprintf (vect_dump, "irrelevant.");
396 switch (STMT_VINFO_DEF_TYPE (stmt_info))
401 case vect_reduction_def:
402 gcc_assert (relevance == vect_unused_in_loop);
405 case vect_induction_def:
406 case vect_constant_def:
407 case vect_invariant_def:
408 case vect_unknown_def_type:
413 if (STMT_VINFO_RELEVANT_P (stmt_info))
415 gcc_assert (GIMPLE_STMT_P (stmt)
416 || !VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))));
417 gcc_assert (STMT_VINFO_VECTYPE (stmt_info));
418 need_to_vectorize = true;
421 ok = (vectorizable_type_promotion (stmt, NULL, NULL)
422 || vectorizable_type_demotion (stmt, NULL, NULL)
423 || vectorizable_conversion (stmt, NULL, NULL)
424 || vectorizable_operation (stmt, NULL, NULL)
425 || vectorizable_assignment (stmt, NULL, NULL)
426 || vectorizable_load (stmt, NULL, NULL)
427 || vectorizable_call (stmt, NULL, NULL)
428 || vectorizable_store (stmt, NULL, NULL)
429 || vectorizable_condition (stmt, NULL, NULL)
430 || vectorizable_reduction (stmt, NULL, NULL));
432 /* Stmts that are (also) "live" (i.e. - that are used out of the loop)
433 need extra handling, except for vectorizable reductions. */
434 if (STMT_VINFO_LIVE_P (stmt_info)
435 && STMT_VINFO_TYPE (stmt_info) != reduc_vec_info_type)
436 ok |= vectorizable_live_operation (stmt, NULL, NULL);
440 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
442 fprintf (vect_dump, "not vectorized: stmt not supported: ");
443 print_generic_expr (vect_dump, stmt, TDF_SLIM);
450 /* All operations in the loop are either irrelevant (deal with loop
451 control, or dead), or only used outside the loop and can be moved
452 out of the loop (e.g. invariants, inductions). The loop can be
453 optimized away by scalar optimizations. We're better off not
454 touching this loop. */
455 if (!need_to_vectorize)
457 if (vect_print_dump_info (REPORT_DETAILS))
459 "All the computation can be taken out of the loop.");
460 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
462 "not vectorized: redundant loop. no profit to vectorize.");
466 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
467 && vect_print_dump_info (REPORT_DETAILS))
469 "vectorization_factor = %d, niters = " HOST_WIDE_INT_PRINT_DEC,
470 vectorization_factor, LOOP_VINFO_INT_NITERS (loop_vinfo));
472 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
473 && (LOOP_VINFO_INT_NITERS (loop_vinfo) < vectorization_factor))
475 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
476 fprintf (vect_dump, "not vectorized: iteration count too small.");
477 if (vect_print_dump_info (REPORT_DETAILS))
478 fprintf (vect_dump,"not vectorized: iteration count smaller than "
479 "vectorization factor.");
483 /* Analyze cost. Decide if worth while to vectorize. */
485 min_profitable_iters = vect_estimate_min_profitable_iters (loop_vinfo);
486 LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo) = min_profitable_iters;
487 if (min_profitable_iters < 0)
489 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
490 fprintf (vect_dump, "not vectorized: vectorization not profitable.");
491 if (vect_print_dump_info (REPORT_DETAILS))
492 fprintf (vect_dump, "not vectorized: vector version will never be "
497 min_scalar_loop_bound = (PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND))
498 * vectorization_factor;
500 /* Use the cost model only if it is more conservative than user specified
503 th = (unsigned) min_scalar_loop_bound;
504 if (min_profitable_iters
505 && (!min_scalar_loop_bound
506 || min_profitable_iters > min_scalar_loop_bound))
507 th = (unsigned) min_profitable_iters;
509 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
510 && LOOP_VINFO_INT_NITERS (loop_vinfo) < th)
512 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
513 fprintf (vect_dump, "not vectorized: vectorization not "
515 if (vect_print_dump_info (REPORT_DETAILS))
516 fprintf (vect_dump, "not vectorized: iteration count smaller than "
517 "user specified loop bound parameter or minimum "
518 "profitable iterations (whichever is more conservative).");
522 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
523 || LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0
524 || LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo))
526 if (vect_print_dump_info (REPORT_DETAILS))
527 fprintf (vect_dump, "epilog loop required.");
528 if (!vect_can_advance_ivs_p (loop_vinfo))
530 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
532 "not vectorized: can't create epilog loop 1.");
535 if (!slpeel_can_duplicate_loop_p (loop, single_exit (loop)))
537 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
539 "not vectorized: can't create epilog loop 2.");
548 /* Function exist_non_indexing_operands_for_use_p
550 USE is one of the uses attached to STMT. Check if USE is
551 used in STMT for anything other than indexing an array. */
554 exist_non_indexing_operands_for_use_p (tree use, tree stmt)
557 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
559 /* USE corresponds to some operand in STMT. If there is no data
560 reference in STMT, then any operand that corresponds to USE
561 is not indexing an array. */
562 if (!STMT_VINFO_DATA_REF (stmt_info))
565 /* STMT has a data_ref. FORNOW this means that its of one of
569 (This should have been verified in analyze_data_refs).
571 'var' in the second case corresponds to a def, not a use,
572 so USE cannot correspond to any operands that are not used
575 Therefore, all we need to check is if STMT falls into the
576 first case, and whether var corresponds to USE. */
578 if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME)
581 operand = GIMPLE_STMT_OPERAND (stmt, 1);
583 if (TREE_CODE (operand) != SSA_NAME)
593 /* Function vect_analyze_scalar_cycles.
595 Examine the cross iteration def-use cycles of scalar variables, by
596 analyzing the loop (scalar) PHIs; Classify each cycle as one of the
597 following: invariant, induction, reduction, unknown.
599 Some forms of scalar cycles are not yet supported.
601 Example1: reduction: (unsupported yet)
607 Example2: induction: (unsupported yet)
613 Note: the following loop *is* vectorizable:
619 even though it has a def-use cycle caused by the induction variable i:
621 loop: i_2 = PHI (i_0, i_1)
626 because the def-use cycle in loop3 is considered "not relevant" - i.e.,
627 it does not need to be vectorized because it is only used for array
628 indexing (see 'mark_stmts_to_be_vectorized'). The def-use cycle in
629 loop2 on the other hand is relevant (it is being written to memory).
633 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
636 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
637 basic_block bb = loop->header;
639 VEC(tree,heap) *worklist = VEC_alloc (tree, heap, 64);
641 if (vect_print_dump_info (REPORT_DETAILS))
642 fprintf (vect_dump, "=== vect_analyze_scalar_cycles ===");
644 /* First - identify all inductions. */
645 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
647 tree access_fn = NULL;
648 tree def = PHI_RESULT (phi);
649 stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
651 if (vect_print_dump_info (REPORT_DETAILS))
653 fprintf (vect_dump, "Analyze phi: ");
654 print_generic_expr (vect_dump, phi, TDF_SLIM);
657 /* Skip virtual phi's. The data dependences that are associated with
658 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
659 if (!is_gimple_reg (SSA_NAME_VAR (def)))
662 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_unknown_def_type;
664 /* Analyze the evolution function. */
665 access_fn = analyze_scalar_evolution (loop, def);
666 if (access_fn && vect_print_dump_info (REPORT_DETAILS))
668 fprintf (vect_dump, "Access function of PHI: ");
669 print_generic_expr (vect_dump, access_fn, TDF_SLIM);
673 || !vect_is_simple_iv_evolution (loop->num, access_fn, &dumy, &dumy))
675 VEC_safe_push (tree, heap, worklist, phi);
679 if (vect_print_dump_info (REPORT_DETAILS))
680 fprintf (vect_dump, "Detected induction.");
681 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def;
685 /* Second - identify all reductions. */
686 while (VEC_length (tree, worklist) > 0)
688 tree phi = VEC_pop (tree, worklist);
689 tree def = PHI_RESULT (phi);
690 stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
693 if (vect_print_dump_info (REPORT_DETAILS))
695 fprintf (vect_dump, "Analyze phi: ");
696 print_generic_expr (vect_dump, phi, TDF_SLIM);
699 gcc_assert (is_gimple_reg (SSA_NAME_VAR (def)));
700 gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_unknown_def_type);
702 reduc_stmt = vect_is_simple_reduction (loop, phi);
705 if (vect_print_dump_info (REPORT_DETAILS))
706 fprintf (vect_dump, "Detected reduction.");
707 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_reduction_def;
708 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
712 if (vect_print_dump_info (REPORT_DETAILS))
713 fprintf (vect_dump, "Unknown def-use cycle pattern.");
716 VEC_free (tree, heap, worklist);
721 /* Function vect_insert_into_interleaving_chain.
723 Insert DRA into the interleaving chain of DRB according to DRA's INIT. */
726 vect_insert_into_interleaving_chain (struct data_reference *dra,
727 struct data_reference *drb)
729 tree prev, next, next_init;
730 stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
731 stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
733 prev = DR_GROUP_FIRST_DR (stmtinfo_b);
734 next = DR_GROUP_NEXT_DR (vinfo_for_stmt (prev));
737 next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
738 if (tree_int_cst_compare (next_init, DR_INIT (dra)) > 0)
741 DR_GROUP_NEXT_DR (vinfo_for_stmt (prev)) = DR_STMT (dra);
742 DR_GROUP_NEXT_DR (stmtinfo_a) = next;
746 next = DR_GROUP_NEXT_DR (vinfo_for_stmt (prev));
749 /* We got to the end of the list. Insert here. */
750 DR_GROUP_NEXT_DR (vinfo_for_stmt (prev)) = DR_STMT (dra);
751 DR_GROUP_NEXT_DR (stmtinfo_a) = NULL_TREE;
755 /* Function vect_update_interleaving_chain.
757 For two data-refs DRA and DRB that are a part of a chain interleaved data
758 accesses, update the interleaving chain. DRB's INIT is smaller than DRA's.
760 There are four possible cases:
761 1. New stmts - both DRA and DRB are not a part of any chain:
764 2. DRB is a part of a chain and DRA is not:
765 no need to update FIRST_DR
766 no need to insert DRB
767 insert DRA according to init
768 3. DRA is a part of a chain and DRB is not:
769 if (init of FIRST_DR > init of DRB)
771 NEXT(FIRST_DR) = previous FIRST_DR
773 insert DRB according to its init
774 4. both DRA and DRB are in some interleaving chains:
775 choose the chain with the smallest init of FIRST_DR
776 insert the nodes of the second chain into the first one. */
779 vect_update_interleaving_chain (struct data_reference *drb,
780 struct data_reference *dra)
782 stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
783 stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
784 tree next_init, init_dra_chain, init_drb_chain, first_a, first_b;
785 tree node, prev, next, node_init, first_stmt;
787 /* 1. New stmts - both DRA and DRB are not a part of any chain. */
788 if (!DR_GROUP_FIRST_DR (stmtinfo_a) && !DR_GROUP_FIRST_DR (stmtinfo_b))
790 DR_GROUP_FIRST_DR (stmtinfo_a) = DR_STMT (drb);
791 DR_GROUP_FIRST_DR (stmtinfo_b) = DR_STMT (drb);
792 DR_GROUP_NEXT_DR (stmtinfo_b) = DR_STMT (dra);
796 /* 2. DRB is a part of a chain and DRA is not. */
797 if (!DR_GROUP_FIRST_DR (stmtinfo_a) && DR_GROUP_FIRST_DR (stmtinfo_b))
799 DR_GROUP_FIRST_DR (stmtinfo_a) = DR_GROUP_FIRST_DR (stmtinfo_b);
800 /* Insert DRA into the chain of DRB. */
801 vect_insert_into_interleaving_chain (dra, drb);
805 /* 3. DRA is a part of a chain and DRB is not. */
806 if (DR_GROUP_FIRST_DR (stmtinfo_a) && !DR_GROUP_FIRST_DR (stmtinfo_b))
808 tree old_first_stmt = DR_GROUP_FIRST_DR (stmtinfo_a);
809 tree init_old = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (
813 if (tree_int_cst_compare (init_old, DR_INIT (drb)) > 0)
815 /* DRB's init is smaller than the init of the stmt previously marked
816 as the first stmt of the interleaving chain of DRA. Therefore, we
817 update FIRST_STMT and put DRB in the head of the list. */
818 DR_GROUP_FIRST_DR (stmtinfo_b) = DR_STMT (drb);
819 DR_GROUP_NEXT_DR (stmtinfo_b) = old_first_stmt;
821 /* Update all the stmts in the list to point to the new FIRST_STMT. */
822 tmp = old_first_stmt;
825 DR_GROUP_FIRST_DR (vinfo_for_stmt (tmp)) = DR_STMT (drb);
826 tmp = DR_GROUP_NEXT_DR (vinfo_for_stmt (tmp));
831 /* Insert DRB in the list of DRA. */
832 vect_insert_into_interleaving_chain (drb, dra);
833 DR_GROUP_FIRST_DR (stmtinfo_b) = DR_GROUP_FIRST_DR (stmtinfo_a);
838 /* 4. both DRA and DRB are in some interleaving chains. */
839 first_a = DR_GROUP_FIRST_DR (stmtinfo_a);
840 first_b = DR_GROUP_FIRST_DR (stmtinfo_b);
841 if (first_a == first_b)
843 init_dra_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_a)));
844 init_drb_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_b)));
846 if (tree_int_cst_compare (init_dra_chain, init_drb_chain) > 0)
848 /* Insert the nodes of DRA chain into the DRB chain.
849 After inserting a node, continue from this node of the DRB chain (don't
850 start from the beginning. */
851 node = DR_GROUP_FIRST_DR (stmtinfo_a);
852 prev = DR_GROUP_FIRST_DR (stmtinfo_b);
853 first_stmt = first_b;
857 /* Insert the nodes of DRB chain into the DRA chain.
858 After inserting a node, continue from this node of the DRA chain (don't
859 start from the beginning. */
860 node = DR_GROUP_FIRST_DR (stmtinfo_b);
861 prev = DR_GROUP_FIRST_DR (stmtinfo_a);
862 first_stmt = first_a;
867 node_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (node)));
868 next = DR_GROUP_NEXT_DR (vinfo_for_stmt (prev));
871 next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
872 if (tree_int_cst_compare (next_init, node_init) > 0)
875 DR_GROUP_NEXT_DR (vinfo_for_stmt (prev)) = node;
876 DR_GROUP_NEXT_DR (vinfo_for_stmt (node)) = next;
881 next = DR_GROUP_NEXT_DR (vinfo_for_stmt (prev));
885 /* We got to the end of the list. Insert here. */
886 DR_GROUP_NEXT_DR (vinfo_for_stmt (prev)) = node;
887 DR_GROUP_NEXT_DR (vinfo_for_stmt (node)) = NULL_TREE;
890 DR_GROUP_FIRST_DR (vinfo_for_stmt (node)) = first_stmt;
891 node = DR_GROUP_NEXT_DR (vinfo_for_stmt (node));
896 /* Function vect_equal_offsets.
898 Check if OFFSET1 and OFFSET2 are identical expressions. */
901 vect_equal_offsets (tree offset1, tree offset2)
905 STRIP_NOPS (offset1);
906 STRIP_NOPS (offset2);
908 if (offset1 == offset2)
911 if (TREE_CODE (offset1) != TREE_CODE (offset2)
912 || !BINARY_CLASS_P (offset1)
913 || !BINARY_CLASS_P (offset2))
916 res0 = vect_equal_offsets (TREE_OPERAND (offset1, 0),
917 TREE_OPERAND (offset2, 0));
918 res1 = vect_equal_offsets (TREE_OPERAND (offset1, 1),
919 TREE_OPERAND (offset2, 1));
921 return (res0 && res1);
925 /* Function vect_check_interleaving.
927 Check if DRA and DRB are a part of interleaving. In case they are, insert
928 DRA and DRB in an interleaving chain. */
931 vect_check_interleaving (struct data_reference *dra,
932 struct data_reference *drb)
934 HOST_WIDE_INT type_size_a, type_size_b, diff_mod_size, step, init_a, init_b;
936 /* Check that the data-refs have same first location (except init) and they
937 are both either store or load (not load and store). */
938 if ((DR_BASE_ADDRESS (dra) != DR_BASE_ADDRESS (drb)
939 && (TREE_CODE (DR_BASE_ADDRESS (dra)) != ADDR_EXPR
940 || TREE_CODE (DR_BASE_ADDRESS (drb)) != ADDR_EXPR
941 || TREE_OPERAND (DR_BASE_ADDRESS (dra), 0)
942 != TREE_OPERAND (DR_BASE_ADDRESS (drb),0)))
943 || !vect_equal_offsets (DR_OFFSET (dra), DR_OFFSET (drb))
944 || !tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb))
945 || DR_IS_READ (dra) != DR_IS_READ (drb))
949 1. data-refs are of the same type
950 2. their steps are equal
951 3. the step is greater than the difference between data-refs' inits */
952 type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
953 type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
955 if (type_size_a != type_size_b
956 || tree_int_cst_compare (DR_STEP (dra), DR_STEP (drb)))
959 init_a = TREE_INT_CST_LOW (DR_INIT (dra));
960 init_b = TREE_INT_CST_LOW (DR_INIT (drb));
961 step = TREE_INT_CST_LOW (DR_STEP (dra));
965 /* If init_a == init_b + the size of the type * k, we have an interleaving,
966 and DRB is accessed before DRA. */
967 diff_mod_size = (init_a - init_b) % type_size_a;
969 if ((init_a - init_b) > step)
972 if (diff_mod_size == 0)
974 vect_update_interleaving_chain (drb, dra);
975 if (vect_print_dump_info (REPORT_DR_DETAILS))
977 fprintf (vect_dump, "Detected interleaving ");
978 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
979 fprintf (vect_dump, " and ");
980 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
987 /* If init_b == init_a + the size of the type * k, we have an
988 interleaving, and DRA is accessed before DRB. */
989 diff_mod_size = (init_b - init_a) % type_size_a;
991 if ((init_b - init_a) > step)
994 if (diff_mod_size == 0)
996 vect_update_interleaving_chain (dra, drb);
997 if (vect_print_dump_info (REPORT_DR_DETAILS))
999 fprintf (vect_dump, "Detected interleaving ");
1000 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
1001 fprintf (vect_dump, " and ");
1002 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
1010 /* Function vect_analyze_data_ref_dependence.
1012 Return TRUE if there (might) exist a dependence between a memory-reference
1013 DRA and a memory-reference DRB. */
1016 vect_analyze_data_ref_dependence (struct data_dependence_relation *ddr,
1017 loop_vec_info loop_vinfo)
1020 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1021 int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1022 struct data_reference *dra = DDR_A (ddr);
1023 struct data_reference *drb = DDR_B (ddr);
1024 stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
1025 stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
1026 int dra_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dra))));
1027 int drb_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (drb))));
1028 lambda_vector dist_v;
1029 unsigned int loop_depth;
1031 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
1033 /* Independent data accesses. */
1034 vect_check_interleaving (dra, drb);
1038 if ((DR_IS_READ (dra) && DR_IS_READ (drb)) || dra == drb)
1041 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
1043 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1046 "not vectorized: can't determine dependence between ");
1047 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
1048 fprintf (vect_dump, " and ");
1049 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
1054 if (DDR_NUM_DIST_VECTS (ddr) == 0)
1056 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1058 fprintf (vect_dump, "not vectorized: bad dist vector for ");
1059 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
1060 fprintf (vect_dump, " and ");
1061 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
1066 loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr));
1067 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
1069 int dist = dist_v[loop_depth];
1071 if (vect_print_dump_info (REPORT_DR_DETAILS))
1072 fprintf (vect_dump, "dependence distance = %d.", dist);
1074 /* Same loop iteration. */
1075 if (dist % vectorization_factor == 0 && dra_size == drb_size)
1077 /* Two references with distance zero have the same alignment. */
1078 VEC_safe_push (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a), drb);
1079 VEC_safe_push (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b), dra);
1080 if (vect_print_dump_info (REPORT_ALIGNMENT))
1081 fprintf (vect_dump, "accesses have the same alignment.");
1082 if (vect_print_dump_info (REPORT_DR_DETAILS))
1084 fprintf (vect_dump, "dependence distance modulo vf == 0 between ");
1085 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
1086 fprintf (vect_dump, " and ");
1087 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
1090 /* For interleaving, mark that there is a read-write dependency if
1091 necessary. We check before that one of the data-refs is store. */
1092 if (DR_IS_READ (dra))
1093 DR_GROUP_READ_WRITE_DEPENDENCE (stmtinfo_a) = true;
1096 if (DR_IS_READ (drb))
1097 DR_GROUP_READ_WRITE_DEPENDENCE (stmtinfo_b) = true;
1103 if (abs (dist) >= vectorization_factor)
1105 /* Dependence distance does not create dependence, as far as vectorization
1106 is concerned, in this case. */
1107 if (vect_print_dump_info (REPORT_DR_DETAILS))
1108 fprintf (vect_dump, "dependence distance >= VF.");
1112 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1115 "not vectorized: possible dependence between data-refs ");
1116 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
1117 fprintf (vect_dump, " and ");
1118 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
1128 /* Function vect_analyze_data_ref_dependences.
1130 Examine all the data references in the loop, and make sure there do not
1131 exist any data dependences between them. */
1134 vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo)
1137 VEC (ddr_p, heap) *ddrs = LOOP_VINFO_DDRS (loop_vinfo);
1138 struct data_dependence_relation *ddr;
1140 if (vect_print_dump_info (REPORT_DETAILS))
1141 fprintf (vect_dump, "=== vect_analyze_dependences ===");
1143 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
1144 if (vect_analyze_data_ref_dependence (ddr, loop_vinfo))
1151 /* Function vect_compute_data_ref_alignment
1153 Compute the misalignment of the data reference DR.
1156 1. If during the misalignment computation it is found that the data reference
1157 cannot be vectorized then false is returned.
1158 2. DR_MISALIGNMENT (DR) is defined.
1160 FOR NOW: No analysis is actually performed. Misalignment is calculated
1161 only for trivial cases. TODO. */
1164 vect_compute_data_ref_alignment (struct data_reference *dr)
1166 tree stmt = DR_STMT (dr);
1167 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1168 tree ref = DR_REF (dr);
1170 tree base, base_addr;
1173 tree aligned_to, alignment;
1175 if (vect_print_dump_info (REPORT_DETAILS))
1176 fprintf (vect_dump, "vect_compute_data_ref_alignment:");
1178 /* Initialize misalignment to unknown. */
1179 SET_DR_MISALIGNMENT (dr, -1);
1181 misalign = DR_INIT (dr);
1182 aligned_to = DR_ALIGNED_TO (dr);
1183 base_addr = DR_BASE_ADDRESS (dr);
1184 base = build_fold_indirect_ref (base_addr);
1185 vectype = STMT_VINFO_VECTYPE (stmt_info);
1186 alignment = ssize_int (TYPE_ALIGN (vectype)/BITS_PER_UNIT);
1188 if (tree_int_cst_compare (aligned_to, alignment) < 0)
1190 if (vect_print_dump_info (REPORT_DETAILS))
1192 fprintf (vect_dump, "Unknown alignment for access: ");
1193 print_generic_expr (vect_dump, base, TDF_SLIM);
1199 && tree_int_cst_compare (ssize_int (DECL_ALIGN_UNIT (base)),
1201 || (TREE_CODE (base_addr) == SSA_NAME
1202 && tree_int_cst_compare (ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (
1203 TREE_TYPE (base_addr)))),
1205 base_aligned = true;
1207 base_aligned = false;
1211 /* Do not change the alignment of global variables if
1212 flag_section_anchors is enabled. */
1213 if (!vect_can_force_dr_alignment_p (base, TYPE_ALIGN (vectype))
1214 || (TREE_STATIC (base) && flag_section_anchors))
1216 if (vect_print_dump_info (REPORT_DETAILS))
1218 fprintf (vect_dump, "can't force alignment of ref: ");
1219 print_generic_expr (vect_dump, ref, TDF_SLIM);
1224 /* Force the alignment of the decl.
1225 NOTE: This is the only change to the code we make during
1226 the analysis phase, before deciding to vectorize the loop. */
1227 if (vect_print_dump_info (REPORT_DETAILS))
1228 fprintf (vect_dump, "force alignment");
1229 DECL_ALIGN (base) = TYPE_ALIGN (vectype);
1230 DECL_USER_ALIGN (base) = 1;
1233 /* At this point we assume that the base is aligned. */
1234 gcc_assert (base_aligned
1235 || (TREE_CODE (base) == VAR_DECL
1236 && DECL_ALIGN (base) >= TYPE_ALIGN (vectype)));
1238 /* Modulo alignment. */
1239 misalign = size_binop (TRUNC_MOD_EXPR, misalign, alignment);
1241 if (!host_integerp (misalign, 1))
1243 /* Negative or overflowed misalignment value. */
1244 if (vect_print_dump_info (REPORT_DETAILS))
1245 fprintf (vect_dump, "unexpected misalign value");
1249 SET_DR_MISALIGNMENT (dr, TREE_INT_CST_LOW (misalign));
1251 if (vect_print_dump_info (REPORT_DETAILS))
1253 fprintf (vect_dump, "misalign = %d bytes of ref ", DR_MISALIGNMENT (dr));
1254 print_generic_expr (vect_dump, ref, TDF_SLIM);
1261 /* Function vect_compute_data_refs_alignment
1263 Compute the misalignment of data references in the loop.
1264 Return FALSE if a data reference is found that cannot be vectorized. */
1267 vect_compute_data_refs_alignment (loop_vec_info loop_vinfo)
1269 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1270 struct data_reference *dr;
1273 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1274 if (!vect_compute_data_ref_alignment (dr))
1281 /* Function vect_update_misalignment_for_peel
1283 DR - the data reference whose misalignment is to be adjusted.
1284 DR_PEEL - the data reference whose misalignment is being made
1285 zero in the vector loop by the peel.
1286 NPEEL - the number of iterations in the peel loop if the misalignment
1287 of DR_PEEL is known at compile time. */
1290 vect_update_misalignment_for_peel (struct data_reference *dr,
1291 struct data_reference *dr_peel, int npeel)
1294 VEC(dr_p,heap) *same_align_drs;
1295 struct data_reference *current_dr;
1296 int dr_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr))));
1297 int dr_peel_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr_peel))));
1298 stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));
1299 stmt_vec_info peel_stmt_info = vinfo_for_stmt (DR_STMT (dr_peel));
1301 /* For interleaved data accesses the step in the loop must be multiplied by
1302 the size of the interleaving group. */
1303 if (DR_GROUP_FIRST_DR (stmt_info))
1304 dr_size *= DR_GROUP_SIZE (vinfo_for_stmt (DR_GROUP_FIRST_DR (stmt_info)));
1305 if (DR_GROUP_FIRST_DR (peel_stmt_info))
1306 dr_peel_size *= DR_GROUP_SIZE (peel_stmt_info);
1308 /* It can be assumed that the data refs with the same alignment as dr_peel
1309 are aligned in the vector loop. */
1311 = STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (DR_STMT (dr_peel)));
1312 for (i = 0; VEC_iterate (dr_p, same_align_drs, i, current_dr); i++)
1314 if (current_dr != dr)
1316 gcc_assert (DR_MISALIGNMENT (dr) / dr_size ==
1317 DR_MISALIGNMENT (dr_peel) / dr_peel_size);
1318 SET_DR_MISALIGNMENT (dr, 0);
1322 if (known_alignment_for_access_p (dr)
1323 && known_alignment_for_access_p (dr_peel))
1325 int misal = DR_MISALIGNMENT (dr);
1326 misal += npeel * dr_size;
1327 misal %= UNITS_PER_SIMD_WORD;
1328 SET_DR_MISALIGNMENT (dr, misal);
1332 if (vect_print_dump_info (REPORT_DETAILS))
1333 fprintf (vect_dump, "Setting misalignment to -1.");
1334 SET_DR_MISALIGNMENT (dr, -1);
1338 /* Function vect_verify_datarefs_alignment
1340 Return TRUE if all data references in the loop can be
1341 handled with respect to alignment. */
1344 vect_verify_datarefs_alignment (loop_vec_info loop_vinfo)
1346 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1347 struct data_reference *dr;
1348 enum dr_alignment_support supportable_dr_alignment;
1351 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1353 tree stmt = DR_STMT (dr);
1354 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1356 /* For interleaving, only the alignment of the first access matters. */
1357 if (DR_GROUP_FIRST_DR (stmt_info)
1358 && DR_GROUP_FIRST_DR (stmt_info) != stmt)
1361 supportable_dr_alignment = vect_supportable_dr_alignment (dr);
1362 if (!supportable_dr_alignment)
1364 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1366 if (DR_IS_READ (dr))
1368 "not vectorized: unsupported unaligned load.");
1371 "not vectorized: unsupported unaligned store.");
1375 if (supportable_dr_alignment != dr_aligned
1376 && vect_print_dump_info (REPORT_ALIGNMENT))
1377 fprintf (vect_dump, "Vectorizing an unaligned access.");
1383 /* Function vector_alignment_reachable_p
1385 Return true if vector alignment for DR is reachable by peeling
1386 a few loop iterations. Return false otherwise. */
1389 vector_alignment_reachable_p (struct data_reference *dr)
1391 tree stmt = DR_STMT (dr);
1392 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1393 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1395 if (DR_GROUP_FIRST_DR (stmt_info))
1397 /* For interleaved access we peel only if number of iterations in
1398 the prolog loop ({VF - misalignment}), is a multiple of the
1399 number of the interleaved accesses. */
1400 int elem_size, mis_in_elements;
1401 int nelements = TYPE_VECTOR_SUBPARTS (vectype);
1403 /* FORNOW: handle only known alignment. */
1404 if (!known_alignment_for_access_p (dr))
1407 elem_size = UNITS_PER_SIMD_WORD / nelements;
1408 mis_in_elements = DR_MISALIGNMENT (dr) / elem_size;
1410 if ((nelements - mis_in_elements) % DR_GROUP_SIZE (stmt_info))
1414 /* If misalignment is known at the compile time then allow peeling
1415 only if natural alignment is reachable through peeling. */
1416 if (known_alignment_for_access_p (dr) && !aligned_access_p (dr))
1418 HOST_WIDE_INT elmsize =
1419 int_cst_value (TYPE_SIZE_UNIT (TREE_TYPE (vectype)));
1420 if (vect_print_dump_info (REPORT_DETAILS))
1422 fprintf (vect_dump, "data size =" HOST_WIDE_INT_PRINT_DEC, elmsize);
1423 fprintf (vect_dump, ". misalignment = %d. ", DR_MISALIGNMENT (dr));
1425 if (DR_MISALIGNMENT (dr) % elmsize)
1427 if (vect_print_dump_info (REPORT_DETAILS))
1428 fprintf (vect_dump, "data size does not divide the misalignment.\n");
1433 if (!known_alignment_for_access_p (dr))
1435 tree type = (TREE_TYPE (DR_REF (dr)));
1436 tree ba = DR_BASE_OBJECT (dr);
1437 bool is_packed = false;
1440 is_packed = contains_packed_reference (ba);
1442 if (vect_print_dump_info (REPORT_DETAILS))
1443 fprintf (vect_dump, "Unknown misalignment, is_packed = %d",is_packed);
1444 if (targetm.vectorize.vector_alignment_reachable (type, is_packed))
1453 /* Function vect_enhance_data_refs_alignment
1455 This pass will use loop versioning and loop peeling in order to enhance
1456 the alignment of data references in the loop.
1458 FOR NOW: we assume that whatever versioning/peeling takes place, only the
1459 original loop is to be vectorized; Any other loops that are created by
1460 the transformations performed in this pass - are not supposed to be
1461 vectorized. This restriction will be relaxed.
1463 This pass will require a cost model to guide it whether to apply peeling
1464 or versioning or a combination of the two. For example, the scheme that
1465 intel uses when given a loop with several memory accesses, is as follows:
1466 choose one memory access ('p') which alignment you want to force by doing
1467 peeling. Then, either (1) generate a loop in which 'p' is aligned and all
1468 other accesses are not necessarily aligned, or (2) use loop versioning to
1469 generate one loop in which all accesses are aligned, and another loop in
1470 which only 'p' is necessarily aligned.
1472 ("Automatic Intra-Register Vectorization for the Intel Architecture",
1473 Aart J.C. Bik, Milind Girkar, Paul M. Grey and Ximmin Tian, International
1474 Journal of Parallel Programming, Vol. 30, No. 2, April 2002.)
1476 Devising a cost model is the most critical aspect of this work. It will
1477 guide us on which access to peel for, whether to use loop versioning, how
1478 many versions to create, etc. The cost model will probably consist of
1479 generic considerations as well as target specific considerations (on
1480 powerpc for example, misaligned stores are more painful than misaligned
1483 Here are the general steps involved in alignment enhancements:
1485 -- original loop, before alignment analysis:
1486 for (i=0; i<N; i++){
1487 x = q[i]; # DR_MISALIGNMENT(q) = unknown
1488 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1491 -- After vect_compute_data_refs_alignment:
1492 for (i=0; i<N; i++){
1493 x = q[i]; # DR_MISALIGNMENT(q) = 3
1494 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1497 -- Possibility 1: we do loop versioning:
1499 for (i=0; i<N; i++){ # loop 1A
1500 x = q[i]; # DR_MISALIGNMENT(q) = 3
1501 p[i] = y; # DR_MISALIGNMENT(p) = 0
1505 for (i=0; i<N; i++){ # loop 1B
1506 x = q[i]; # DR_MISALIGNMENT(q) = 3
1507 p[i] = y; # DR_MISALIGNMENT(p) = unaligned
1511 -- Possibility 2: we do loop peeling:
1512 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
1516 for (i = 3; i < N; i++){ # loop 2A
1517 x = q[i]; # DR_MISALIGNMENT(q) = 0
1518 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1521 -- Possibility 3: combination of loop peeling and versioning:
1522 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
1527 for (i = 3; i<N; i++){ # loop 3A
1528 x = q[i]; # DR_MISALIGNMENT(q) = 0
1529 p[i] = y; # DR_MISALIGNMENT(p) = 0
1533 for (i = 3; i<N; i++){ # loop 3B
1534 x = q[i]; # DR_MISALIGNMENT(q) = 0
1535 p[i] = y; # DR_MISALIGNMENT(p) = unaligned
1539 These loops are later passed to loop_transform to be vectorized. The
1540 vectorizer will use the alignment information to guide the transformation
1541 (whether to generate regular loads/stores, or with special handling for
1545 vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo)
1547 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1548 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1549 enum dr_alignment_support supportable_dr_alignment;
1550 struct data_reference *dr0 = NULL;
1551 struct data_reference *dr;
1553 bool do_peeling = false;
1554 bool do_versioning = false;
1557 stmt_vec_info stmt_info;
1559 if (vect_print_dump_info (REPORT_DETAILS))
1560 fprintf (vect_dump, "=== vect_enhance_data_refs_alignment ===");
1562 /* While cost model enhancements are expected in the future, the high level
1563 view of the code at this time is as follows:
1565 A) If there is a misaligned write then see if peeling to align this write
1566 can make all data references satisfy vect_supportable_dr_alignment.
1567 If so, update data structures as needed and return true. Note that
1568 at this time vect_supportable_dr_alignment is known to return false
1569 for a misaligned write.
1571 B) If peeling wasn't possible and there is a data reference with an
1572 unknown misalignment that does not satisfy vect_supportable_dr_alignment
1573 then see if loop versioning checks can be used to make all data
1574 references satisfy vect_supportable_dr_alignment. If so, update
1575 data structures as needed and return true.
1577 C) If neither peeling nor versioning were successful then return false if
1578 any data reference does not satisfy vect_supportable_dr_alignment.
1580 D) Return true (all data references satisfy vect_supportable_dr_alignment).
1582 Note, Possibility 3 above (which is peeling and versioning together) is not
1583 being done at this time. */
1585 /* (1) Peeling to force alignment. */
1587 /* (1.1) Decide whether to perform peeling, and how many iterations to peel:
1589 + How many accesses will become aligned due to the peeling
1590 - How many accesses will become unaligned due to the peeling,
1591 and the cost of misaligned accesses.
1592 - The cost of peeling (the extra runtime checks, the increase
1595 The scheme we use FORNOW: peel to force the alignment of the first
1596 misaligned store in the loop.
1597 Rationale: misaligned stores are not yet supported.
1599 TODO: Use a cost model. */
1601 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1603 stmt = DR_STMT (dr);
1604 stmt_info = vinfo_for_stmt (stmt);
1606 /* For interleaving, only the alignment of the first access
1608 if (DR_GROUP_FIRST_DR (stmt_info)
1609 && DR_GROUP_FIRST_DR (stmt_info) != stmt)
1612 if (!DR_IS_READ (dr) && !aligned_access_p (dr))
1614 do_peeling = vector_alignment_reachable_p (dr);
1617 if (!do_peeling && vect_print_dump_info (REPORT_DETAILS))
1618 fprintf (vect_dump, "vector alignment may not be reachable");
1623 /* Often peeling for alignment will require peeling for loop-bound, which in
1624 turn requires that we know how to adjust the loop ivs after the loop. */
1625 if (!vect_can_advance_ivs_p (loop_vinfo)
1626 || !slpeel_can_duplicate_loop_p (loop, single_exit (loop)))
1633 tree stmt = DR_STMT (dr0);
1634 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1635 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1636 int nelements = TYPE_VECTOR_SUBPARTS (vectype);
1638 if (known_alignment_for_access_p (dr0))
1640 /* Since it's known at compile time, compute the number of iterations
1641 in the peeled loop (the peeling factor) for use in updating
1642 DR_MISALIGNMENT values. The peeling factor is the vectorization
1643 factor minus the misalignment as an element count. */
1644 mis = DR_MISALIGNMENT (dr0);
1645 mis /= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr0))));
1646 npeel = nelements - mis;
1648 /* For interleaved data access every iteration accesses all the
1649 members of the group, therefore we divide the number of iterations
1650 by the group size. */
1651 stmt_info = vinfo_for_stmt (DR_STMT (dr0));
1652 if (DR_GROUP_FIRST_DR (stmt_info))
1653 npeel /= DR_GROUP_SIZE (stmt_info);
1655 if (vect_print_dump_info (REPORT_DETAILS))
1656 fprintf (vect_dump, "Try peeling by %d", npeel);
1659 /* Ensure that all data refs can be vectorized after the peel. */
1660 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1662 int save_misalignment;
1667 stmt = DR_STMT (dr);
1668 stmt_info = vinfo_for_stmt (stmt);
1669 /* For interleaving, only the alignment of the first access
1671 if (DR_GROUP_FIRST_DR (stmt_info)
1672 && DR_GROUP_FIRST_DR (stmt_info) != stmt)
1675 save_misalignment = DR_MISALIGNMENT (dr);
1676 vect_update_misalignment_for_peel (dr, dr0, npeel);
1677 supportable_dr_alignment = vect_supportable_dr_alignment (dr);
1678 SET_DR_MISALIGNMENT (dr, save_misalignment);
1680 if (!supportable_dr_alignment)
1689 /* (1.2) Update the DR_MISALIGNMENT of each data reference DR_i.
1690 If the misalignment of DR_i is identical to that of dr0 then set
1691 DR_MISALIGNMENT (DR_i) to zero. If the misalignment of DR_i and
1692 dr0 are known at compile time then increment DR_MISALIGNMENT (DR_i)
1693 by the peeling factor times the element size of DR_i (MOD the
1694 vectorization factor times the size). Otherwise, the
1695 misalignment of DR_i must be set to unknown. */
1696 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1698 vect_update_misalignment_for_peel (dr, dr0, npeel);
1700 LOOP_VINFO_UNALIGNED_DR (loop_vinfo) = dr0;
1701 LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) = DR_MISALIGNMENT (dr0);
1702 SET_DR_MISALIGNMENT (dr0, 0);
1703 if (vect_print_dump_info (REPORT_ALIGNMENT))
1704 fprintf (vect_dump, "Alignment of access forced using peeling.");
1706 if (vect_print_dump_info (REPORT_DETAILS))
1707 fprintf (vect_dump, "Peeling for alignment will be applied.");
1709 stat = vect_verify_datarefs_alignment (loop_vinfo);
1716 /* (2) Versioning to force alignment. */
1718 /* Try versioning if:
1719 1) flag_tree_vect_loop_version is TRUE
1720 2) optimize_size is FALSE
1721 3) there is at least one unsupported misaligned data ref with an unknown
1723 4) all misaligned data refs with a known misalignment are supported, and
1724 5) the number of runtime alignment checks is within reason. */
1726 do_versioning = flag_tree_vect_loop_version && (!optimize_size);
1730 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1732 stmt = DR_STMT (dr);
1733 stmt_info = vinfo_for_stmt (stmt);
1735 /* For interleaving, only the alignment of the first access
1737 if (aligned_access_p (dr)
1738 || (DR_GROUP_FIRST_DR (stmt_info)
1739 && DR_GROUP_FIRST_DR (stmt_info) != stmt))
1742 supportable_dr_alignment = vect_supportable_dr_alignment (dr);
1744 if (!supportable_dr_alignment)
1750 if (known_alignment_for_access_p (dr)
1751 || VEC_length (tree,
1752 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo))
1753 >= (unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_CHECKS))
1755 do_versioning = false;
1759 stmt = DR_STMT (dr);
1760 vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
1761 gcc_assert (vectype);
1763 /* The rightmost bits of an aligned address must be zeros.
1764 Construct the mask needed for this test. For example,
1765 GET_MODE_SIZE for the vector mode V4SI is 16 bytes so the
1766 mask must be 15 = 0xf. */
1767 mask = GET_MODE_SIZE (TYPE_MODE (vectype)) - 1;
1769 /* FORNOW: use the same mask to test all potentially unaligned
1770 references in the loop. The vectorizer currently supports
1771 a single vector size, see the reference to
1772 GET_MODE_NUNITS (TYPE_MODE (vectype)) where the
1773 vectorization factor is computed. */
1774 gcc_assert (!LOOP_VINFO_PTR_MASK (loop_vinfo)
1775 || LOOP_VINFO_PTR_MASK (loop_vinfo) == mask);
1776 LOOP_VINFO_PTR_MASK (loop_vinfo) = mask;
1777 VEC_safe_push (tree, heap,
1778 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo),
1783 /* Versioning requires at least one misaligned data reference. */
1784 if (VEC_length (tree, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo)) == 0)
1785 do_versioning = false;
1786 else if (!do_versioning)
1787 VEC_truncate (tree, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo), 0);
1792 VEC(tree,heap) *may_misalign_stmts
1793 = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo);
1796 /* It can now be assumed that the data references in the statements
1797 in LOOP_VINFO_MAY_MISALIGN_STMTS will be aligned in the version
1798 of the loop being vectorized. */
1799 for (i = 0; VEC_iterate (tree, may_misalign_stmts, i, stmt); i++)
1801 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1802 dr = STMT_VINFO_DATA_REF (stmt_info);
1803 SET_DR_MISALIGNMENT (dr, 0);
1804 if (vect_print_dump_info (REPORT_ALIGNMENT))
1805 fprintf (vect_dump, "Alignment of access forced using versioning.");
1808 if (vect_print_dump_info (REPORT_DETAILS))
1809 fprintf (vect_dump, "Versioning for alignment will be applied.");
1811 /* Peeling and versioning can't be done together at this time. */
1812 gcc_assert (! (do_peeling && do_versioning));
1814 stat = vect_verify_datarefs_alignment (loop_vinfo);
1819 /* This point is reached if neither peeling nor versioning is being done. */
1820 gcc_assert (! (do_peeling || do_versioning));
1822 stat = vect_verify_datarefs_alignment (loop_vinfo);
1827 /* Function vect_analyze_data_refs_alignment
1829 Analyze the alignment of the data-references in the loop.
1830 Return FALSE if a data reference is found that cannot be vectorized. */
1833 vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo)
1835 if (vect_print_dump_info (REPORT_DETAILS))
1836 fprintf (vect_dump, "=== vect_analyze_data_refs_alignment ===");
1838 if (!vect_compute_data_refs_alignment (loop_vinfo))
1840 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1842 "not vectorized: can't calculate alignment for data ref.");
1850 /* Function vect_analyze_data_ref_access.
1852 Analyze the access pattern of the data-reference DR. For now, a data access
1853 has to be consecutive to be considered vectorizable. */
1856 vect_analyze_data_ref_access (struct data_reference *dr)
1858 tree step = DR_STEP (dr);
1859 HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
1860 tree scalar_type = TREE_TYPE (DR_REF (dr));
1861 HOST_WIDE_INT type_size = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type));
1862 tree stmt = DR_STMT (dr);
1863 /* For interleaving, STRIDE is STEP counted in elements, i.e., the size of the
1864 interleaving group (including gaps). */
1865 HOST_WIDE_INT stride = dr_step / type_size;
1869 if (vect_print_dump_info (REPORT_DETAILS))
1870 fprintf (vect_dump, "bad data-ref access");
1875 if (!tree_int_cst_compare (step, TYPE_SIZE_UNIT (scalar_type)))
1877 /* Mark that it is not interleaving. */
1878 DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) = NULL_TREE;
1882 /* Not consecutive access is possible only if it is a part of interleaving. */
1883 if (!DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)))
1885 /* Check if it this DR is a part of interleaving, and is a single
1886 element of the group that is accessed in the loop. */
1888 /* Gaps are supported only for loads. STEP must be a multiple of the type
1889 size. The size of the group must be a power of 2. */
1891 && (dr_step % type_size) == 0
1893 && exact_log2 (stride) != -1)
1895 DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) = stmt;
1896 DR_GROUP_SIZE (vinfo_for_stmt (stmt)) = stride;
1897 if (vect_print_dump_info (REPORT_DR_DETAILS))
1899 fprintf (vect_dump, "Detected single element interleaving %d ",
1900 DR_GROUP_SIZE (vinfo_for_stmt (stmt)));
1901 print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM);
1902 fprintf (vect_dump, " step ");
1903 print_generic_expr (vect_dump, step, TDF_SLIM);
1907 if (vect_print_dump_info (REPORT_DETAILS))
1908 fprintf (vect_dump, "not consecutive access");
1912 if (DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) == stmt)
1914 /* First stmt in the interleaving chain. Check the chain. */
1915 tree next = DR_GROUP_NEXT_DR (vinfo_for_stmt (stmt));
1916 struct data_reference *data_ref = dr;
1917 unsigned int count = 1;
1919 tree prev_init = DR_INIT (data_ref);
1921 HOST_WIDE_INT diff, count_in_bytes;
1925 /* Skip same data-refs. In case that two or more stmts share data-ref
1926 (supported only for loads), we vectorize only the first stmt, and
1927 the rest get their vectorized loads from the first one. */
1928 if (!tree_int_cst_compare (DR_INIT (data_ref),
1929 DR_INIT (STMT_VINFO_DATA_REF (
1930 vinfo_for_stmt (next)))))
1932 if (!DR_IS_READ (data_ref))
1934 if (vect_print_dump_info (REPORT_DETAILS))
1935 fprintf (vect_dump, "Two store stmts share the same dr.");
1939 /* Check that there is no load-store dependencies for this loads
1940 to prevent a case of load-store-load to the same location. */
1941 if (DR_GROUP_READ_WRITE_DEPENDENCE (vinfo_for_stmt (next))
1942 || DR_GROUP_READ_WRITE_DEPENDENCE (vinfo_for_stmt (prev)))
1944 if (vect_print_dump_info (REPORT_DETAILS))
1946 "READ_WRITE dependence in interleaving.");
1950 /* For load use the same data-ref load. */
1951 DR_GROUP_SAME_DR_STMT (vinfo_for_stmt (next)) = prev;
1954 next = DR_GROUP_NEXT_DR (vinfo_for_stmt (next));
1959 /* Check that all the accesses have the same STEP. */
1960 next_step = DR_STEP (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
1961 if (tree_int_cst_compare (step, next_step))
1963 if (vect_print_dump_info (REPORT_DETAILS))
1964 fprintf (vect_dump, "not consecutive access in interleaving");
1968 data_ref = STMT_VINFO_DATA_REF (vinfo_for_stmt (next));
1969 /* Check that the distance between two accesses is equal to the type
1970 size. Otherwise, we have gaps. */
1971 diff = (TREE_INT_CST_LOW (DR_INIT (data_ref))
1972 - TREE_INT_CST_LOW (prev_init)) / type_size;
1973 if (!DR_IS_READ (data_ref) && diff != 1)
1975 if (vect_print_dump_info (REPORT_DETAILS))
1976 fprintf (vect_dump, "interleaved store with gaps");
1979 /* Store the gap from the previous member of the group. If there is no
1980 gap in the access, DR_GROUP_GAP is always 1. */
1981 DR_GROUP_GAP (vinfo_for_stmt (next)) = diff;
1983 prev_init = DR_INIT (data_ref);
1984 next = DR_GROUP_NEXT_DR (vinfo_for_stmt (next));
1985 /* Count the number of data-refs in the chain. */
1989 /* COUNT is the number of accesses found, we multiply it by the size of
1990 the type to get COUNT_IN_BYTES. */
1991 count_in_bytes = type_size * count;
1993 /* Check that the size of the interleaving is not greater than STEP. */
1994 if (dr_step < count_in_bytes)
1996 if (vect_print_dump_info (REPORT_DETAILS))
1998 fprintf (vect_dump, "interleaving size is greater than step for ");
1999 print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM);
2004 /* Check that the size of the interleaving is equal to STEP for stores,
2005 i.e., that there are no gaps. */
2006 if (!DR_IS_READ (dr) && dr_step != count_in_bytes)
2008 if (vect_print_dump_info (REPORT_DETAILS))
2009 fprintf (vect_dump, "interleaved store with gaps");
2013 /* Check that STEP is a multiple of type size. */
2014 if ((dr_step % type_size) != 0)
2016 if (vect_print_dump_info (REPORT_DETAILS))
2018 fprintf (vect_dump, "step is not a multiple of type size: step ");
2019 print_generic_expr (vect_dump, step, TDF_SLIM);
2020 fprintf (vect_dump, " size ");
2021 print_generic_expr (vect_dump, TYPE_SIZE_UNIT (scalar_type),
2027 /* FORNOW: we handle only interleaving that is a power of 2. */
2028 if (exact_log2 (stride) == -1)
2030 if (vect_print_dump_info (REPORT_DETAILS))
2031 fprintf (vect_dump, "interleaving is not a power of 2");
2034 DR_GROUP_SIZE (vinfo_for_stmt (stmt)) = stride;
2040 /* Function vect_analyze_data_ref_accesses.
2042 Analyze the access pattern of all the data references in the loop.
2044 FORNOW: the only access pattern that is considered vectorizable is a
2045 simple step 1 (consecutive) access.
2047 FORNOW: handle only arrays and pointer accesses. */
2050 vect_analyze_data_ref_accesses (loop_vec_info loop_vinfo)
2053 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
2054 struct data_reference *dr;
2056 if (vect_print_dump_info (REPORT_DETAILS))
2057 fprintf (vect_dump, "=== vect_analyze_data_ref_accesses ===");
2059 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
2060 if (!vect_analyze_data_ref_access (dr))
2062 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2063 fprintf (vect_dump, "not vectorized: complicated access pattern.");
2071 /* Function vect_analyze_data_refs.
2073 Find all the data references in the loop.
2075 The general structure of the analysis of data refs in the vectorizer is as
2077 1- vect_analyze_data_refs(loop): call compute_data_dependences_for_loop to
2078 find and analyze all data-refs in the loop and their dependences.
2079 2- vect_analyze_dependences(): apply dependence testing using ddrs.
2080 3- vect_analyze_drs_alignment(): check that ref_stmt.alignment is ok.
2081 4- vect_analyze_drs_access(): check that ref_stmt.step is ok.
2086 vect_analyze_data_refs (loop_vec_info loop_vinfo)
2088 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2090 VEC (data_reference_p, heap) *datarefs;
2091 struct data_reference *dr;
2094 if (vect_print_dump_info (REPORT_DETAILS))
2095 fprintf (vect_dump, "=== vect_analyze_data_refs ===\n");
2097 compute_data_dependences_for_loop (loop, true,
2098 &LOOP_VINFO_DATAREFS (loop_vinfo),
2099 &LOOP_VINFO_DDRS (loop_vinfo));
2101 /* Go through the data-refs, check that the analysis succeeded. Update pointer
2102 from stmt_vec_info struct to DR and vectype. */
2103 datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
2105 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
2108 stmt_vec_info stmt_info;
2110 if (!dr || !DR_REF (dr))
2112 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2113 fprintf (vect_dump, "not vectorized: unhandled data-ref ");
2117 /* Update DR field in stmt_vec_info struct. */
2118 stmt = DR_STMT (dr);
2119 stmt_info = vinfo_for_stmt (stmt);
2121 if (STMT_VINFO_DATA_REF (stmt_info))
2123 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2126 "not vectorized: more than one data ref in stmt: ");
2127 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2131 STMT_VINFO_DATA_REF (stmt_info) = dr;
2133 /* Check that analysis of the data-ref succeeded. */
2134 if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr) || !DR_INIT (dr)
2137 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2139 fprintf (vect_dump, "not vectorized: data ref analysis failed ");
2140 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2145 if (TREE_CODE (DR_BASE_ADDRESS (dr)) == INTEGER_CST)
2147 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2148 fprintf (vect_dump, "not vectorized: base addr of dr is a "
2153 if (!DR_SYMBOL_TAG (dr))
2155 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2157 fprintf (vect_dump, "not vectorized: no memory tag for ");
2158 print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM);
2163 /* Set vectype for STMT. */
2164 scalar_type = TREE_TYPE (DR_REF (dr));
2165 STMT_VINFO_VECTYPE (stmt_info) =
2166 get_vectype_for_scalar_type (scalar_type);
2167 if (!STMT_VINFO_VECTYPE (stmt_info))
2169 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2172 "not vectorized: no vectype for stmt: ");
2173 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2174 fprintf (vect_dump, " scalar_type: ");
2175 print_generic_expr (vect_dump, scalar_type, TDF_DETAILS);
2185 /* Utility functions used by vect_mark_stmts_to_be_vectorized. */
2187 /* Function vect_mark_relevant.
2189 Mark STMT as "relevant for vectorization" and add it to WORKLIST. */
2192 vect_mark_relevant (VEC(tree,heap) **worklist, tree stmt,
2193 enum vect_relevant relevant, bool live_p)
2195 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2196 enum vect_relevant save_relevant = STMT_VINFO_RELEVANT (stmt_info);
2197 bool save_live_p = STMT_VINFO_LIVE_P (stmt_info);
2199 if (vect_print_dump_info (REPORT_DETAILS))
2200 fprintf (vect_dump, "mark relevant %d, live %d.", relevant, live_p);
2202 if (STMT_VINFO_IN_PATTERN_P (stmt_info))
2206 /* This is the last stmt in a sequence that was detected as a
2207 pattern that can potentially be vectorized. Don't mark the stmt
2208 as relevant/live because it's not going to vectorized.
2209 Instead mark the pattern-stmt that replaces it. */
2210 if (vect_print_dump_info (REPORT_DETAILS))
2211 fprintf (vect_dump, "last stmt in pattern. don't mark relevant/live.");
2212 pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
2213 stmt_info = vinfo_for_stmt (pattern_stmt);
2214 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_info) == stmt);
2215 save_relevant = STMT_VINFO_RELEVANT (stmt_info);
2216 save_live_p = STMT_VINFO_LIVE_P (stmt_info);
2217 stmt = pattern_stmt;
2220 STMT_VINFO_LIVE_P (stmt_info) |= live_p;
2221 if (relevant > STMT_VINFO_RELEVANT (stmt_info))
2222 STMT_VINFO_RELEVANT (stmt_info) = relevant;
2224 if (STMT_VINFO_RELEVANT (stmt_info) == save_relevant
2225 && STMT_VINFO_LIVE_P (stmt_info) == save_live_p)
2227 if (vect_print_dump_info (REPORT_DETAILS))
2228 fprintf (vect_dump, "already marked relevant/live.");
2232 VEC_safe_push (tree, heap, *worklist, stmt);
2236 /* Function vect_stmt_relevant_p.
2238 Return true if STMT in loop that is represented by LOOP_VINFO is
2239 "relevant for vectorization".
2241 A stmt is considered "relevant for vectorization" if:
2242 - it has uses outside the loop.
2243 - it has vdefs (it alters memory).
2244 - control stmts in the loop (except for the exit condition).
2246 CHECKME: what other side effects would the vectorizer allow? */
2249 vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo,
2250 enum vect_relevant *relevant, bool *live_p)
2252 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2253 ssa_op_iter op_iter;
2254 imm_use_iterator imm_iter;
2255 use_operand_p use_p;
2256 def_operand_p def_p;
2258 *relevant = vect_unused_in_loop;
2261 /* cond stmt other than loop exit cond. */
2262 if (is_ctrl_stmt (stmt) && (stmt != LOOP_VINFO_EXIT_COND (loop_vinfo)))
2263 *relevant = vect_used_in_loop;
2265 /* changing memory. */
2266 if (TREE_CODE (stmt) != PHI_NODE)
2267 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
2269 if (vect_print_dump_info (REPORT_DETAILS))
2270 fprintf (vect_dump, "vec_stmt_relevant_p: stmt has vdefs.");
2271 *relevant = vect_used_in_loop;
2274 /* uses outside the loop. */
2275 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_DEF)
2277 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
2279 basic_block bb = bb_for_stmt (USE_STMT (use_p));
2280 if (!flow_bb_inside_loop_p (loop, bb))
2282 if (vect_print_dump_info (REPORT_DETAILS))
2283 fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop.");
2285 /* We expect all such uses to be in the loop exit phis
2286 (because of loop closed form) */
2287 gcc_assert (TREE_CODE (USE_STMT (use_p)) == PHI_NODE);
2288 gcc_assert (bb == single_exit (loop)->dest);
2295 return (*live_p || *relevant);
2300 Function process_use.
2303 - a USE in STMT in a loop represented by LOOP_VINFO
2304 - LIVE_P, RELEVANT - enum values to be set in the STMT_VINFO of the stmt
2305 that defined USE. This is dont by calling mark_relevant and passing it
2306 the WORKLIST (to add DEF_STMT to the WORKlist in case itis relevant).
2309 Generally, LIVE_P and RELEVANT are used to define the liveness and
2310 relevance info of the DEF_STMT of this USE:
2311 STMT_VINFO_LIVE_P (DEF_STMT_info) <-- live_p
2312 STMT_VINFO_RELEVANT (DEF_STMT_info) <-- relevant
2314 - case 1: If USE is used only for address computations (e.g. array indexing),
2315 which does not need to be directly vectorized, then the liveness/relevance
2316 of the respective DEF_STMT is left unchanged.
2317 - case 2: If STMT is a reduction phi and DEF_STMT is a reduction stmt, we
2318 skip DEF_STMT cause it had already been processed.
2320 Return true if everything is as expected. Return false otherwise. */
2323 process_use (tree stmt, tree use, loop_vec_info loop_vinfo, bool live_p,
2324 enum vect_relevant relevant, VEC(tree,heap) **worklist)
2326 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2327 stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
2328 stmt_vec_info dstmt_vinfo;
2331 enum vect_def_type dt;
2333 /* case 1: we are only interested in uses that need to be vectorized. Uses
2334 that are used for address computation are not considered relevant. */
2335 if (!exist_non_indexing_operands_for_use_p (use, stmt))
2338 if (!vect_is_simple_use (use, loop_vinfo, &def_stmt, &def, &dt))
2340 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2341 fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
2345 if (!def_stmt || IS_EMPTY_STMT (def_stmt))
2348 def_bb = bb_for_stmt (def_stmt);
2349 if (!flow_bb_inside_loop_p (loop, def_bb))
2352 /* case 2: A reduction phi defining a reduction stmt (DEF_STMT). DEF_STMT
2353 must have already been processed, so we just check that everything is as
2354 expected, and we are done. */
2355 dstmt_vinfo = vinfo_for_stmt (def_stmt);
2356 if (TREE_CODE (stmt) == PHI_NODE
2357 && STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def
2358 && TREE_CODE (def_stmt) != PHI_NODE
2359 && STMT_VINFO_DEF_TYPE (dstmt_vinfo) == vect_reduction_def)
2361 if (STMT_VINFO_IN_PATTERN_P (dstmt_vinfo))
2362 dstmt_vinfo = vinfo_for_stmt (STMT_VINFO_RELATED_STMT (dstmt_vinfo));
2363 gcc_assert (STMT_VINFO_RELEVANT (dstmt_vinfo) < vect_used_by_reduction);
2364 gcc_assert (STMT_VINFO_LIVE_P (dstmt_vinfo)
2365 || STMT_VINFO_RELEVANT (dstmt_vinfo) > vect_unused_in_loop);
2369 vect_mark_relevant (worklist, def_stmt, relevant, live_p);
2374 /* Function vect_mark_stmts_to_be_vectorized.
2376 Not all stmts in the loop need to be vectorized. For example:
2385 Stmt 1 and 3 do not need to be vectorized, because loop control and
2386 addressing of vectorized data-refs are handled differently.
2388 This pass detects such stmts. */
2391 vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo)
2393 VEC(tree,heap) *worklist;
2394 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2395 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
2396 unsigned int nbbs = loop->num_nodes;
2397 block_stmt_iterator si;
2401 stmt_vec_info stmt_vinfo;
2405 enum vect_relevant relevant;
2407 if (vect_print_dump_info (REPORT_DETAILS))
2408 fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ===");
2410 worklist = VEC_alloc (tree, heap, 64);
2412 /* 1. Init worklist. */
2413 for (i = 0; i < nbbs; i++)
2416 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2418 if (vect_print_dump_info (REPORT_DETAILS))
2420 fprintf (vect_dump, "init: phi relevant? ");
2421 print_generic_expr (vect_dump, phi, TDF_SLIM);
2424 if (vect_stmt_relevant_p (phi, loop_vinfo, &relevant, &live_p))
2425 vect_mark_relevant (&worklist, phi, relevant, live_p);
2427 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2429 stmt = bsi_stmt (si);
2430 if (vect_print_dump_info (REPORT_DETAILS))
2432 fprintf (vect_dump, "init: stmt relevant? ");
2433 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2436 if (vect_stmt_relevant_p (stmt, loop_vinfo, &relevant, &live_p))
2437 vect_mark_relevant (&worklist, stmt, relevant, live_p);
2441 /* 2. Process_worklist */
2442 while (VEC_length (tree, worklist) > 0)
2444 use_operand_p use_p;
2447 stmt = VEC_pop (tree, worklist);
2448 if (vect_print_dump_info (REPORT_DETAILS))
2450 fprintf (vect_dump, "worklist: examine stmt: ");
2451 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2454 /* Examine the USEs of STMT. For each USE, mark the stmt that defines it
2455 (DEF_STMT) as relevant/irrelevant and live/dead according to the
2456 liveness and relevance properties of STMT. */
2457 ann = stmt_ann (stmt);
2458 stmt_vinfo = vinfo_for_stmt (stmt);
2459 relevant = STMT_VINFO_RELEVANT (stmt_vinfo);
2460 live_p = STMT_VINFO_LIVE_P (stmt_vinfo);
2462 /* Generally, the liveness and relevance properties of STMT are
2463 propagated as is to the DEF_STMTs of its USEs:
2464 live_p <-- STMT_VINFO_LIVE_P (STMT_VINFO)
2465 relevant <-- STMT_VINFO_RELEVANT (STMT_VINFO)
2467 One exception is when STMT has been identified as defining a reduction
2468 variable; in this case we set the liveness/relevance as follows:
2470 relevant = vect_used_by_reduction
2471 This is because we distinguish between two kinds of relevant stmts -
2472 those that are used by a reduction computation, and those that are
2473 (also) used by a regular computation. This allows us later on to
2474 identify stmts that are used solely by a reduction, and therefore the
2475 order of the results that they produce does not have to be kept.
2477 Reduction phis are expected to be used by a reduction stmt; Other
2478 reduction stmts are expected to be unused in the loop. These are the
2479 expected values of "relevant" for reduction phis/stmts in the loop:
2482 vect_unused_in_loop ok
2483 vect_used_by_reduction ok
2484 vect_used_in_loop */
2486 if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def)
2490 case vect_unused_in_loop:
2491 gcc_assert (TREE_CODE (stmt) != PHI_NODE);
2493 case vect_used_by_reduction:
2494 if (TREE_CODE (stmt) == PHI_NODE)
2496 case vect_used_in_loop:
2498 if (vect_print_dump_info (REPORT_DETAILS))
2499 fprintf (vect_dump, "unsupported use of reduction.");
2500 VEC_free (tree, heap, worklist);
2503 relevant = vect_used_by_reduction;
2507 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2509 tree op = USE_FROM_PTR (use_p);
2510 if (!process_use (stmt, op, loop_vinfo, live_p, relevant, &worklist))
2512 VEC_free (tree, heap, worklist);
2516 } /* while worklist */
2518 VEC_free (tree, heap, worklist);
2523 /* Function vect_can_advance_ivs_p
2525 In case the number of iterations that LOOP iterates is unknown at compile
2526 time, an epilog loop will be generated, and the loop induction variables
2527 (IVs) will be "advanced" to the value they are supposed to take just before
2528 the epilog loop. Here we check that the access function of the loop IVs
2529 and the expression that represents the loop bound are simple enough.
2530 These restrictions will be relaxed in the future. */
2533 vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
2535 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2536 basic_block bb = loop->header;
2539 /* Analyze phi functions of the loop header. */
2541 if (vect_print_dump_info (REPORT_DETAILS))
2542 fprintf (vect_dump, "vect_can_advance_ivs_p:");
2544 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2546 tree access_fn = NULL;
2547 tree evolution_part;
2549 if (vect_print_dump_info (REPORT_DETAILS))
2551 fprintf (vect_dump, "Analyze phi: ");
2552 print_generic_expr (vect_dump, phi, TDF_SLIM);
2555 /* Skip virtual phi's. The data dependences that are associated with
2556 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
2558 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
2560 if (vect_print_dump_info (REPORT_DETAILS))
2561 fprintf (vect_dump, "virtual phi. skip.");
2565 /* Skip reduction phis. */
2567 if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (phi)) == vect_reduction_def)
2569 if (vect_print_dump_info (REPORT_DETAILS))
2570 fprintf (vect_dump, "reduc phi. skip.");
2574 /* Analyze the evolution function. */
2576 access_fn = instantiate_parameters
2577 (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2581 if (vect_print_dump_info (REPORT_DETAILS))
2582 fprintf (vect_dump, "No Access function.");
2586 if (vect_print_dump_info (REPORT_DETAILS))
2588 fprintf (vect_dump, "Access function of PHI: ");
2589 print_generic_expr (vect_dump, access_fn, TDF_SLIM);
2592 evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
2594 if (evolution_part == NULL_TREE)
2596 if (vect_print_dump_info (REPORT_DETAILS))
2597 fprintf (vect_dump, "No evolution.");
2601 /* FORNOW: We do not transform initial conditions of IVs
2602 which evolution functions are a polynomial of degree >= 2. */
2604 if (tree_is_chrec (evolution_part))
2612 /* Function vect_get_loop_niters.
2614 Determine how many iterations the loop is executed.
2615 If an expression that represents the number of iterations
2616 can be constructed, place it in NUMBER_OF_ITERATIONS.
2617 Return the loop exit condition. */
2620 vect_get_loop_niters (struct loop *loop, tree *number_of_iterations)
2624 if (vect_print_dump_info (REPORT_DETAILS))
2625 fprintf (vect_dump, "=== get_loop_niters ===");
2627 niters = number_of_exit_cond_executions (loop);
2629 if (niters != NULL_TREE
2630 && niters != chrec_dont_know)
2632 *number_of_iterations = niters;
2634 if (vect_print_dump_info (REPORT_DETAILS))
2636 fprintf (vect_dump, "==> get_loop_niters:" );
2637 print_generic_expr (vect_dump, *number_of_iterations, TDF_SLIM);
2641 return get_loop_exit_condition (loop);
2645 /* Function vect_analyze_loop_form.
2647 Verify the following restrictions (some may be relaxed in the future):
2648 - it's an inner-most loop
2649 - number of BBs = 2 (which are the loop header and the latch)
2650 - the loop has a pre-header
2651 - the loop has a single entry and exit
2652 - the loop exit condition is simple enough, and the number of iterations
2653 can be analyzed (a countable loop). */
2655 static loop_vec_info
2656 vect_analyze_loop_form (struct loop *loop)
2658 loop_vec_info loop_vinfo;
2660 tree number_of_iterations = NULL;
2662 if (vect_print_dump_info (REPORT_DETAILS))
2663 fprintf (vect_dump, "=== vect_analyze_loop_form ===");
2667 if (vect_print_dump_info (REPORT_OUTER_LOOPS))
2668 fprintf (vect_dump, "not vectorized: nested loop.");
2672 if (!single_exit (loop)
2673 || loop->num_nodes != 2
2674 || EDGE_COUNT (loop->header->preds) != 2)
2676 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2678 if (!single_exit (loop))
2679 fprintf (vect_dump, "not vectorized: multiple exits.");
2680 else if (loop->num_nodes != 2)
2681 fprintf (vect_dump, "not vectorized: too many BBs in loop.");
2682 else if (EDGE_COUNT (loop->header->preds) != 2)
2683 fprintf (vect_dump, "not vectorized: too many incoming edges.");
2689 /* We assume that the loop exit condition is at the end of the loop. i.e,
2690 that the loop is represented as a do-while (with a proper if-guard
2691 before the loop if needed), where the loop header contains all the
2692 executable statements, and the latch is empty. */
2693 if (!empty_block_p (loop->latch)
2694 || phi_nodes (loop->latch))
2696 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2697 fprintf (vect_dump, "not vectorized: unexpected loop form.");
2701 /* Make sure there exists a single-predecessor exit bb: */
2702 if (!single_pred_p (single_exit (loop)->dest))
2704 edge e = single_exit (loop);
2705 if (!(e->flags & EDGE_ABNORMAL))
2707 split_loop_exit_edge (e);
2708 if (vect_print_dump_info (REPORT_DETAILS))
2709 fprintf (vect_dump, "split exit edge.");
2713 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2714 fprintf (vect_dump, "not vectorized: abnormal loop exit edge.");
2719 if (empty_block_p (loop->header))
2721 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2722 fprintf (vect_dump, "not vectorized: empty loop.");
2726 loop_cond = vect_get_loop_niters (loop, &number_of_iterations);
2729 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2730 fprintf (vect_dump, "not vectorized: complicated exit condition.");
2734 if (!number_of_iterations)
2736 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2738 "not vectorized: number of iterations cannot be computed.");
2742 if (chrec_contains_undetermined (number_of_iterations))
2744 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2745 fprintf (vect_dump, "Infinite number of iterations.");
2749 if (!NITERS_KNOWN_P (number_of_iterations))
2751 if (vect_print_dump_info (REPORT_DETAILS))
2753 fprintf (vect_dump, "Symbolic number of iterations is ");
2754 print_generic_expr (vect_dump, number_of_iterations, TDF_DETAILS);
2757 else if (TREE_INT_CST_LOW (number_of_iterations) == 0)
2759 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2760 fprintf (vect_dump, "not vectorized: number of iterations = 0.");
2764 loop_vinfo = new_loop_vec_info (loop);
2765 LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
2766 LOOP_VINFO_EXIT_COND (loop_vinfo) = loop_cond;
2768 gcc_assert (!loop->aux);
2769 loop->aux = loop_vinfo;
2774 /* Function vect_analyze_loop.
2776 Apply a set of analyses on LOOP, and create a loop_vec_info struct
2777 for it. The different analyses will record information in the
2778 loop_vec_info struct. */
2780 vect_analyze_loop (struct loop *loop)
2783 loop_vec_info loop_vinfo;
2785 if (vect_print_dump_info (REPORT_DETAILS))
2786 fprintf (vect_dump, "===== analyze_loop_nest =====");
2788 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
2790 loop_vinfo = vect_analyze_loop_form (loop);
2793 if (vect_print_dump_info (REPORT_DETAILS))
2794 fprintf (vect_dump, "bad loop form.");
2798 /* Find all data references in the loop (which correspond to vdefs/vuses)
2799 and analyze their evolution in the loop.
2801 FORNOW: Handle only simple, array references, which
2802 alignment can be forced, and aligned pointer-references. */
2804 ok = vect_analyze_data_refs (loop_vinfo);
2807 if (vect_print_dump_info (REPORT_DETAILS))
2808 fprintf (vect_dump, "bad data references.");
2809 destroy_loop_vec_info (loop_vinfo);
2813 /* Classify all cross-iteration scalar data-flow cycles.
2814 Cross-iteration cycles caused by virtual phis are analyzed separately. */
2816 vect_analyze_scalar_cycles (loop_vinfo);
2818 vect_pattern_recog (loop_vinfo);
2820 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
2822 ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
2825 if (vect_print_dump_info (REPORT_DETAILS))
2826 fprintf (vect_dump, "unexpected pattern.");
2827 destroy_loop_vec_info (loop_vinfo);
2831 /* Analyze the alignment of the data-refs in the loop.
2832 Fail if a data reference is found that cannot be vectorized. */
2834 ok = vect_analyze_data_refs_alignment (loop_vinfo);
2837 if (vect_print_dump_info (REPORT_DETAILS))
2838 fprintf (vect_dump, "bad data alignment.");
2839 destroy_loop_vec_info (loop_vinfo);
2843 ok = vect_determine_vectorization_factor (loop_vinfo);
2846 if (vect_print_dump_info (REPORT_DETAILS))
2847 fprintf (vect_dump, "can't determine vectorization factor.");
2848 destroy_loop_vec_info (loop_vinfo);
2852 /* Analyze data dependences between the data-refs in the loop.
2853 FORNOW: fail at the first data dependence that we encounter. */
2855 ok = vect_analyze_data_ref_dependences (loop_vinfo);
2858 if (vect_print_dump_info (REPORT_DETAILS))
2859 fprintf (vect_dump, "bad data dependence.");
2860 destroy_loop_vec_info (loop_vinfo);
2864 /* Analyze the access patterns of the data-refs in the loop (consecutive,
2865 complex, etc.). FORNOW: Only handle consecutive access pattern. */
2867 ok = vect_analyze_data_ref_accesses (loop_vinfo);
2870 if (vect_print_dump_info (REPORT_DETAILS))
2871 fprintf (vect_dump, "bad data access.");
2872 destroy_loop_vec_info (loop_vinfo);
2876 /* This pass will decide on using loop versioning and/or loop peeling in
2877 order to enhance the alignment of data references in the loop. */
2879 ok = vect_enhance_data_refs_alignment (loop_vinfo);
2882 if (vect_print_dump_info (REPORT_DETAILS))
2883 fprintf (vect_dump, "bad data alignment.");
2884 destroy_loop_vec_info (loop_vinfo);
2888 /* Scan all the operations in the loop and make sure they are
2891 ok = vect_analyze_operations (loop_vinfo);
2894 if (vect_print_dump_info (REPORT_DETAILS))
2895 fprintf (vect_dump, "bad operation or unsupported loop bound.");
2896 destroy_loop_vec_info (loop_vinfo);
2900 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1;