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_DR_DETAILS))
1045 "versioning for alias required: 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_DR_DETAILS))
1057 fprintf (vect_dump, "versioning for alias required: 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_DR_DETAILS))
1114 "versioning for alias required: possible dependence "
1115 "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);
1127 /* Return TRUE if DDR_NEW is already found in MAY_ALIAS_DDRS list. */
1130 vect_is_duplicate_ddr (VEC (ddr_p, heap) * may_alias_ddrs, ddr_p ddr_new)
1135 for (i = 0; VEC_iterate (ddr_p, may_alias_ddrs, i, ddr); i++)
1137 tree dref_A_i, dref_B_i, dref_A_j, dref_B_j;
1139 dref_A_i = DR_REF (DDR_A (ddr));
1140 dref_B_i = DR_REF (DDR_B (ddr));
1141 dref_A_j = DR_REF (DDR_A (ddr_new));
1142 dref_B_j = DR_REF (DDR_B (ddr_new));
1144 if ((operand_equal_p (dref_A_i, dref_A_j, 0)
1145 && operand_equal_p (dref_B_i, dref_B_j, 0))
1146 || (operand_equal_p (dref_A_i, dref_B_j, 0)
1147 && operand_equal_p (dref_B_i, dref_A_j, 0)))
1149 if (vect_print_dump_info (REPORT_DR_DETAILS))
1151 fprintf (vect_dump, "found same pair of data references ");
1152 print_generic_expr (vect_dump, dref_A_i, TDF_SLIM);
1153 fprintf (vect_dump, " and ");
1154 print_generic_expr (vect_dump, dref_B_i, TDF_SLIM);
1162 /* Save DDR in LOOP_VINFO list of ddrs that may alias and need to be
1163 tested at run-time. Returns false if number of run-time checks
1164 inserted by vectorizer is greater than maximum defined by
1165 PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS. */
1167 vect_mark_for_runtime_alias_test (ddr_p ddr, loop_vec_info loop_vinfo)
1169 if (vect_print_dump_info (REPORT_DR_DETAILS))
1171 fprintf (vect_dump, "mark for run-time aliasing test between ");
1172 print_generic_expr (vect_dump, DR_REF (DDR_A (ddr)), TDF_SLIM);
1173 fprintf (vect_dump, " and ");
1174 print_generic_expr (vect_dump, DR_REF (DDR_B (ddr)), TDF_SLIM);
1177 /* Do not add to the list duplicate ddrs. */
1178 if (vect_is_duplicate_ddr (LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo), ddr))
1181 if (VEC_length (ddr_p, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo))
1182 >= (unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS))
1184 if (vect_print_dump_info (REPORT_DR_DETAILS))
1187 "disable versioning for alias - max number of generated "
1188 "checks exceeded.");
1191 VEC_truncate (ddr_p, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo), 0);
1195 VEC_safe_push (ddr_p, heap, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo), ddr);
1199 /* Function vect_analyze_data_ref_dependences.
1201 Examine all the data references in the loop, and make sure there do not
1202 exist any data dependences between them. */
1205 vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo)
1208 VEC (ddr_p, heap) * ddrs = LOOP_VINFO_DDRS (loop_vinfo);
1209 struct data_dependence_relation *ddr;
1211 if (vect_print_dump_info (REPORT_DETAILS))
1212 fprintf (vect_dump, "=== vect_analyze_dependences ===");
1214 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
1215 if (vect_analyze_data_ref_dependence (ddr, loop_vinfo))
1217 /* Add to list of ddrs that need to be tested at run-time. */
1218 if (!vect_mark_for_runtime_alias_test (ddr, loop_vinfo))
1226 /* Function vect_compute_data_ref_alignment
1228 Compute the misalignment of the data reference DR.
1231 1. If during the misalignment computation it is found that the data reference
1232 cannot be vectorized then false is returned.
1233 2. DR_MISALIGNMENT (DR) is defined.
1235 FOR NOW: No analysis is actually performed. Misalignment is calculated
1236 only for trivial cases. TODO. */
1239 vect_compute_data_ref_alignment (struct data_reference *dr)
1241 tree stmt = DR_STMT (dr);
1242 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1243 tree ref = DR_REF (dr);
1245 tree base, base_addr;
1248 tree aligned_to, alignment;
1250 if (vect_print_dump_info (REPORT_DETAILS))
1251 fprintf (vect_dump, "vect_compute_data_ref_alignment:");
1253 /* Initialize misalignment to unknown. */
1254 SET_DR_MISALIGNMENT (dr, -1);
1256 misalign = DR_INIT (dr);
1257 aligned_to = DR_ALIGNED_TO (dr);
1258 base_addr = DR_BASE_ADDRESS (dr);
1259 base = build_fold_indirect_ref (base_addr);
1260 vectype = STMT_VINFO_VECTYPE (stmt_info);
1261 alignment = ssize_int (TYPE_ALIGN (vectype)/BITS_PER_UNIT);
1263 if (tree_int_cst_compare (aligned_to, alignment) < 0)
1265 if (vect_print_dump_info (REPORT_DETAILS))
1267 fprintf (vect_dump, "Unknown alignment for access: ");
1268 print_generic_expr (vect_dump, base, TDF_SLIM);
1274 && tree_int_cst_compare (ssize_int (DECL_ALIGN_UNIT (base)),
1276 || (TREE_CODE (base_addr) == SSA_NAME
1277 && tree_int_cst_compare (ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (
1278 TREE_TYPE (base_addr)))),
1280 base_aligned = true;
1282 base_aligned = false;
1286 /* Do not change the alignment of global variables if
1287 flag_section_anchors is enabled. */
1288 if (!vect_can_force_dr_alignment_p (base, TYPE_ALIGN (vectype))
1289 || (TREE_STATIC (base) && flag_section_anchors))
1291 if (vect_print_dump_info (REPORT_DETAILS))
1293 fprintf (vect_dump, "can't force alignment of ref: ");
1294 print_generic_expr (vect_dump, ref, TDF_SLIM);
1299 /* Force the alignment of the decl.
1300 NOTE: This is the only change to the code we make during
1301 the analysis phase, before deciding to vectorize the loop. */
1302 if (vect_print_dump_info (REPORT_DETAILS))
1303 fprintf (vect_dump, "force alignment");
1304 DECL_ALIGN (base) = TYPE_ALIGN (vectype);
1305 DECL_USER_ALIGN (base) = 1;
1308 /* At this point we assume that the base is aligned. */
1309 gcc_assert (base_aligned
1310 || (TREE_CODE (base) == VAR_DECL
1311 && DECL_ALIGN (base) >= TYPE_ALIGN (vectype)));
1313 /* Modulo alignment. */
1314 misalign = size_binop (TRUNC_MOD_EXPR, misalign, alignment);
1316 if (!host_integerp (misalign, 1))
1318 /* Negative or overflowed misalignment value. */
1319 if (vect_print_dump_info (REPORT_DETAILS))
1320 fprintf (vect_dump, "unexpected misalign value");
1324 SET_DR_MISALIGNMENT (dr, TREE_INT_CST_LOW (misalign));
1326 if (vect_print_dump_info (REPORT_DETAILS))
1328 fprintf (vect_dump, "misalign = %d bytes of ref ", DR_MISALIGNMENT (dr));
1329 print_generic_expr (vect_dump, ref, TDF_SLIM);
1336 /* Function vect_compute_data_refs_alignment
1338 Compute the misalignment of data references in the loop.
1339 Return FALSE if a data reference is found that cannot be vectorized. */
1342 vect_compute_data_refs_alignment (loop_vec_info loop_vinfo)
1344 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1345 struct data_reference *dr;
1348 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1349 if (!vect_compute_data_ref_alignment (dr))
1356 /* Function vect_update_misalignment_for_peel
1358 DR - the data reference whose misalignment is to be adjusted.
1359 DR_PEEL - the data reference whose misalignment is being made
1360 zero in the vector loop by the peel.
1361 NPEEL - the number of iterations in the peel loop if the misalignment
1362 of DR_PEEL is known at compile time. */
1365 vect_update_misalignment_for_peel (struct data_reference *dr,
1366 struct data_reference *dr_peel, int npeel)
1369 VEC(dr_p,heap) *same_align_drs;
1370 struct data_reference *current_dr;
1371 int dr_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr))));
1372 int dr_peel_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr_peel))));
1373 stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));
1374 stmt_vec_info peel_stmt_info = vinfo_for_stmt (DR_STMT (dr_peel));
1376 /* For interleaved data accesses the step in the loop must be multiplied by
1377 the size of the interleaving group. */
1378 if (DR_GROUP_FIRST_DR (stmt_info))
1379 dr_size *= DR_GROUP_SIZE (vinfo_for_stmt (DR_GROUP_FIRST_DR (stmt_info)));
1380 if (DR_GROUP_FIRST_DR (peel_stmt_info))
1381 dr_peel_size *= DR_GROUP_SIZE (peel_stmt_info);
1383 /* It can be assumed that the data refs with the same alignment as dr_peel
1384 are aligned in the vector loop. */
1386 = STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (DR_STMT (dr_peel)));
1387 for (i = 0; VEC_iterate (dr_p, same_align_drs, i, current_dr); i++)
1389 if (current_dr != dr)
1391 gcc_assert (DR_MISALIGNMENT (dr) / dr_size ==
1392 DR_MISALIGNMENT (dr_peel) / dr_peel_size);
1393 SET_DR_MISALIGNMENT (dr, 0);
1397 if (known_alignment_for_access_p (dr)
1398 && known_alignment_for_access_p (dr_peel))
1400 int misal = DR_MISALIGNMENT (dr);
1401 misal += npeel * dr_size;
1402 misal %= UNITS_PER_SIMD_WORD;
1403 SET_DR_MISALIGNMENT (dr, misal);
1407 if (vect_print_dump_info (REPORT_DETAILS))
1408 fprintf (vect_dump, "Setting misalignment to -1.");
1409 SET_DR_MISALIGNMENT (dr, -1);
1413 /* Function vect_verify_datarefs_alignment
1415 Return TRUE if all data references in the loop can be
1416 handled with respect to alignment. */
1419 vect_verify_datarefs_alignment (loop_vec_info loop_vinfo)
1421 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1422 struct data_reference *dr;
1423 enum dr_alignment_support supportable_dr_alignment;
1426 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1428 tree stmt = DR_STMT (dr);
1429 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1431 /* For interleaving, only the alignment of the first access matters. */
1432 if (DR_GROUP_FIRST_DR (stmt_info)
1433 && DR_GROUP_FIRST_DR (stmt_info) != stmt)
1436 supportable_dr_alignment = vect_supportable_dr_alignment (dr);
1437 if (!supportable_dr_alignment)
1439 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1441 if (DR_IS_READ (dr))
1443 "not vectorized: unsupported unaligned load.");
1446 "not vectorized: unsupported unaligned store.");
1450 if (supportable_dr_alignment != dr_aligned
1451 && vect_print_dump_info (REPORT_ALIGNMENT))
1452 fprintf (vect_dump, "Vectorizing an unaligned access.");
1458 /* Function vector_alignment_reachable_p
1460 Return true if vector alignment for DR is reachable by peeling
1461 a few loop iterations. Return false otherwise. */
1464 vector_alignment_reachable_p (struct data_reference *dr)
1466 tree stmt = DR_STMT (dr);
1467 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1468 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1470 if (DR_GROUP_FIRST_DR (stmt_info))
1472 /* For interleaved access we peel only if number of iterations in
1473 the prolog loop ({VF - misalignment}), is a multiple of the
1474 number of the interleaved accesses. */
1475 int elem_size, mis_in_elements;
1476 int nelements = TYPE_VECTOR_SUBPARTS (vectype);
1478 /* FORNOW: handle only known alignment. */
1479 if (!known_alignment_for_access_p (dr))
1482 elem_size = UNITS_PER_SIMD_WORD / nelements;
1483 mis_in_elements = DR_MISALIGNMENT (dr) / elem_size;
1485 if ((nelements - mis_in_elements) % DR_GROUP_SIZE (stmt_info))
1489 /* If misalignment is known at the compile time then allow peeling
1490 only if natural alignment is reachable through peeling. */
1491 if (known_alignment_for_access_p (dr) && !aligned_access_p (dr))
1493 HOST_WIDE_INT elmsize =
1494 int_cst_value (TYPE_SIZE_UNIT (TREE_TYPE (vectype)));
1495 if (vect_print_dump_info (REPORT_DETAILS))
1497 fprintf (vect_dump, "data size =" HOST_WIDE_INT_PRINT_DEC, elmsize);
1498 fprintf (vect_dump, ". misalignment = %d. ", DR_MISALIGNMENT (dr));
1500 if (DR_MISALIGNMENT (dr) % elmsize)
1502 if (vect_print_dump_info (REPORT_DETAILS))
1503 fprintf (vect_dump, "data size does not divide the misalignment.\n");
1508 if (!known_alignment_for_access_p (dr))
1510 tree type = (TREE_TYPE (DR_REF (dr)));
1511 tree ba = DR_BASE_OBJECT (dr);
1512 bool is_packed = false;
1515 is_packed = contains_packed_reference (ba);
1517 if (vect_print_dump_info (REPORT_DETAILS))
1518 fprintf (vect_dump, "Unknown misalignment, is_packed = %d",is_packed);
1519 if (targetm.vectorize.vector_alignment_reachable (type, is_packed))
1528 /* Function vect_enhance_data_refs_alignment
1530 This pass will use loop versioning and loop peeling in order to enhance
1531 the alignment of data references in the loop.
1533 FOR NOW: we assume that whatever versioning/peeling takes place, only the
1534 original loop is to be vectorized; Any other loops that are created by
1535 the transformations performed in this pass - are not supposed to be
1536 vectorized. This restriction will be relaxed.
1538 This pass will require a cost model to guide it whether to apply peeling
1539 or versioning or a combination of the two. For example, the scheme that
1540 intel uses when given a loop with several memory accesses, is as follows:
1541 choose one memory access ('p') which alignment you want to force by doing
1542 peeling. Then, either (1) generate a loop in which 'p' is aligned and all
1543 other accesses are not necessarily aligned, or (2) use loop versioning to
1544 generate one loop in which all accesses are aligned, and another loop in
1545 which only 'p' is necessarily aligned.
1547 ("Automatic Intra-Register Vectorization for the Intel Architecture",
1548 Aart J.C. Bik, Milind Girkar, Paul M. Grey and Ximmin Tian, International
1549 Journal of Parallel Programming, Vol. 30, No. 2, April 2002.)
1551 Devising a cost model is the most critical aspect of this work. It will
1552 guide us on which access to peel for, whether to use loop versioning, how
1553 many versions to create, etc. The cost model will probably consist of
1554 generic considerations as well as target specific considerations (on
1555 powerpc for example, misaligned stores are more painful than misaligned
1558 Here are the general steps involved in alignment enhancements:
1560 -- original loop, before alignment analysis:
1561 for (i=0; i<N; i++){
1562 x = q[i]; # DR_MISALIGNMENT(q) = unknown
1563 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1566 -- After vect_compute_data_refs_alignment:
1567 for (i=0; i<N; i++){
1568 x = q[i]; # DR_MISALIGNMENT(q) = 3
1569 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1572 -- Possibility 1: we do loop versioning:
1574 for (i=0; i<N; i++){ # loop 1A
1575 x = q[i]; # DR_MISALIGNMENT(q) = 3
1576 p[i] = y; # DR_MISALIGNMENT(p) = 0
1580 for (i=0; i<N; i++){ # loop 1B
1581 x = q[i]; # DR_MISALIGNMENT(q) = 3
1582 p[i] = y; # DR_MISALIGNMENT(p) = unaligned
1586 -- Possibility 2: we do loop peeling:
1587 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
1591 for (i = 3; i < N; i++){ # loop 2A
1592 x = q[i]; # DR_MISALIGNMENT(q) = 0
1593 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1596 -- Possibility 3: combination of loop peeling and versioning:
1597 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
1602 for (i = 3; i<N; i++){ # loop 3A
1603 x = q[i]; # DR_MISALIGNMENT(q) = 0
1604 p[i] = y; # DR_MISALIGNMENT(p) = 0
1608 for (i = 3; i<N; i++){ # loop 3B
1609 x = q[i]; # DR_MISALIGNMENT(q) = 0
1610 p[i] = y; # DR_MISALIGNMENT(p) = unaligned
1614 These loops are later passed to loop_transform to be vectorized. The
1615 vectorizer will use the alignment information to guide the transformation
1616 (whether to generate regular loads/stores, or with special handling for
1620 vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo)
1622 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1623 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1624 enum dr_alignment_support supportable_dr_alignment;
1625 struct data_reference *dr0 = NULL;
1626 struct data_reference *dr;
1628 bool do_peeling = false;
1629 bool do_versioning = false;
1632 stmt_vec_info stmt_info;
1633 int vect_versioning_for_alias_required;
1635 if (vect_print_dump_info (REPORT_DETAILS))
1636 fprintf (vect_dump, "=== vect_enhance_data_refs_alignment ===");
1638 /* While cost model enhancements are expected in the future, the high level
1639 view of the code at this time is as follows:
1641 A) If there is a misaligned write then see if peeling to align this write
1642 can make all data references satisfy vect_supportable_dr_alignment.
1643 If so, update data structures as needed and return true. Note that
1644 at this time vect_supportable_dr_alignment is known to return false
1645 for a misaligned write.
1647 B) If peeling wasn't possible and there is a data reference with an
1648 unknown misalignment that does not satisfy vect_supportable_dr_alignment
1649 then see if loop versioning checks can be used to make all data
1650 references satisfy vect_supportable_dr_alignment. If so, update
1651 data structures as needed and return true.
1653 C) If neither peeling nor versioning were successful then return false if
1654 any data reference does not satisfy vect_supportable_dr_alignment.
1656 D) Return true (all data references satisfy vect_supportable_dr_alignment).
1658 Note, Possibility 3 above (which is peeling and versioning together) is not
1659 being done at this time. */
1661 /* (1) Peeling to force alignment. */
1663 /* (1.1) Decide whether to perform peeling, and how many iterations to peel:
1665 + How many accesses will become aligned due to the peeling
1666 - How many accesses will become unaligned due to the peeling,
1667 and the cost of misaligned accesses.
1668 - The cost of peeling (the extra runtime checks, the increase
1671 The scheme we use FORNOW: peel to force the alignment of the first
1672 misaligned store in the loop.
1673 Rationale: misaligned stores are not yet supported.
1675 TODO: Use a cost model. */
1677 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1679 stmt = DR_STMT (dr);
1680 stmt_info = vinfo_for_stmt (stmt);
1682 /* For interleaving, only the alignment of the first access
1684 if (DR_GROUP_FIRST_DR (stmt_info)
1685 && DR_GROUP_FIRST_DR (stmt_info) != stmt)
1688 if (!DR_IS_READ (dr) && !aligned_access_p (dr))
1690 do_peeling = vector_alignment_reachable_p (dr);
1693 if (!do_peeling && vect_print_dump_info (REPORT_DETAILS))
1694 fprintf (vect_dump, "vector alignment may not be reachable");
1699 vect_versioning_for_alias_required =
1700 (VEC_length (ddr_p, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo)) > 0);
1702 /* Temporarily, if versioning for alias is required, we disable peeling
1703 until we support peeling and versioning. Often peeling for alignment
1704 will require peeling for loop-bound, which in turn requires that we
1705 know how to adjust the loop ivs after the loop. */
1706 if (vect_versioning_for_alias_required
1707 || !vect_can_advance_ivs_p (loop_vinfo)
1708 || !slpeel_can_duplicate_loop_p (loop, single_exit (loop)))
1715 tree stmt = DR_STMT (dr0);
1716 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1717 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1718 int nelements = TYPE_VECTOR_SUBPARTS (vectype);
1720 if (known_alignment_for_access_p (dr0))
1722 /* Since it's known at compile time, compute the number of iterations
1723 in the peeled loop (the peeling factor) for use in updating
1724 DR_MISALIGNMENT values. The peeling factor is the vectorization
1725 factor minus the misalignment as an element count. */
1726 mis = DR_MISALIGNMENT (dr0);
1727 mis /= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr0))));
1728 npeel = nelements - mis;
1730 /* For interleaved data access every iteration accesses all the
1731 members of the group, therefore we divide the number of iterations
1732 by the group size. */
1733 stmt_info = vinfo_for_stmt (DR_STMT (dr0));
1734 if (DR_GROUP_FIRST_DR (stmt_info))
1735 npeel /= DR_GROUP_SIZE (stmt_info);
1737 if (vect_print_dump_info (REPORT_DETAILS))
1738 fprintf (vect_dump, "Try peeling by %d", npeel);
1741 /* Ensure that all data refs can be vectorized after the peel. */
1742 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1744 int save_misalignment;
1749 stmt = DR_STMT (dr);
1750 stmt_info = vinfo_for_stmt (stmt);
1751 /* For interleaving, only the alignment of the first access
1753 if (DR_GROUP_FIRST_DR (stmt_info)
1754 && DR_GROUP_FIRST_DR (stmt_info) != stmt)
1757 save_misalignment = DR_MISALIGNMENT (dr);
1758 vect_update_misalignment_for_peel (dr, dr0, npeel);
1759 supportable_dr_alignment = vect_supportable_dr_alignment (dr);
1760 SET_DR_MISALIGNMENT (dr, save_misalignment);
1762 if (!supportable_dr_alignment)
1771 /* (1.2) Update the DR_MISALIGNMENT of each data reference DR_i.
1772 If the misalignment of DR_i is identical to that of dr0 then set
1773 DR_MISALIGNMENT (DR_i) to zero. If the misalignment of DR_i and
1774 dr0 are known at compile time then increment DR_MISALIGNMENT (DR_i)
1775 by the peeling factor times the element size of DR_i (MOD the
1776 vectorization factor times the size). Otherwise, the
1777 misalignment of DR_i must be set to unknown. */
1778 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1780 vect_update_misalignment_for_peel (dr, dr0, npeel);
1782 LOOP_VINFO_UNALIGNED_DR (loop_vinfo) = dr0;
1783 LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) = DR_MISALIGNMENT (dr0);
1784 SET_DR_MISALIGNMENT (dr0, 0);
1785 if (vect_print_dump_info (REPORT_ALIGNMENT))
1786 fprintf (vect_dump, "Alignment of access forced using peeling.");
1788 if (vect_print_dump_info (REPORT_DETAILS))
1789 fprintf (vect_dump, "Peeling for alignment will be applied.");
1791 stat = vect_verify_datarefs_alignment (loop_vinfo);
1798 /* (2) Versioning to force alignment. */
1800 /* Try versioning if:
1801 1) flag_tree_vect_loop_version is TRUE
1802 2) optimize_size is FALSE
1803 3) there is at least one unsupported misaligned data ref with an unknown
1805 4) all misaligned data refs with a known misalignment are supported, and
1806 5) the number of runtime alignment checks is within reason. */
1808 do_versioning = flag_tree_vect_loop_version && (!optimize_size);
1812 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1814 stmt = DR_STMT (dr);
1815 stmt_info = vinfo_for_stmt (stmt);
1817 /* For interleaving, only the alignment of the first access
1819 if (aligned_access_p (dr)
1820 || (DR_GROUP_FIRST_DR (stmt_info)
1821 && DR_GROUP_FIRST_DR (stmt_info) != stmt))
1824 supportable_dr_alignment = vect_supportable_dr_alignment (dr);
1826 if (!supportable_dr_alignment)
1832 if (known_alignment_for_access_p (dr)
1833 || VEC_length (tree,
1834 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo))
1835 >= (unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS))
1837 do_versioning = false;
1841 stmt = DR_STMT (dr);
1842 vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
1843 gcc_assert (vectype);
1845 /* The rightmost bits of an aligned address must be zeros.
1846 Construct the mask needed for this test. For example,
1847 GET_MODE_SIZE for the vector mode V4SI is 16 bytes so the
1848 mask must be 15 = 0xf. */
1849 mask = GET_MODE_SIZE (TYPE_MODE (vectype)) - 1;
1851 /* FORNOW: use the same mask to test all potentially unaligned
1852 references in the loop. The vectorizer currently supports
1853 a single vector size, see the reference to
1854 GET_MODE_NUNITS (TYPE_MODE (vectype)) where the
1855 vectorization factor is computed. */
1856 gcc_assert (!LOOP_VINFO_PTR_MASK (loop_vinfo)
1857 || LOOP_VINFO_PTR_MASK (loop_vinfo) == mask);
1858 LOOP_VINFO_PTR_MASK (loop_vinfo) = mask;
1859 VEC_safe_push (tree, heap,
1860 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo),
1865 /* Versioning requires at least one misaligned data reference. */
1866 if (VEC_length (tree, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo)) == 0)
1867 do_versioning = false;
1868 else if (!do_versioning)
1869 VEC_truncate (tree, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo), 0);
1874 VEC(tree,heap) *may_misalign_stmts
1875 = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo);
1878 /* It can now be assumed that the data references in the statements
1879 in LOOP_VINFO_MAY_MISALIGN_STMTS will be aligned in the version
1880 of the loop being vectorized. */
1881 for (i = 0; VEC_iterate (tree, may_misalign_stmts, i, stmt); i++)
1883 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1884 dr = STMT_VINFO_DATA_REF (stmt_info);
1885 SET_DR_MISALIGNMENT (dr, 0);
1886 if (vect_print_dump_info (REPORT_ALIGNMENT))
1887 fprintf (vect_dump, "Alignment of access forced using versioning.");
1890 if (vect_print_dump_info (REPORT_DETAILS))
1891 fprintf (vect_dump, "Versioning for alignment will be applied.");
1893 /* Peeling and versioning can't be done together at this time. */
1894 gcc_assert (! (do_peeling && do_versioning));
1896 stat = vect_verify_datarefs_alignment (loop_vinfo);
1901 /* This point is reached if neither peeling nor versioning is being done. */
1902 gcc_assert (! (do_peeling || do_versioning));
1904 stat = vect_verify_datarefs_alignment (loop_vinfo);
1909 /* Function vect_analyze_data_refs_alignment
1911 Analyze the alignment of the data-references in the loop.
1912 Return FALSE if a data reference is found that cannot be vectorized. */
1915 vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo)
1917 if (vect_print_dump_info (REPORT_DETAILS))
1918 fprintf (vect_dump, "=== vect_analyze_data_refs_alignment ===");
1920 if (!vect_compute_data_refs_alignment (loop_vinfo))
1922 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1924 "not vectorized: can't calculate alignment for data ref.");
1932 /* Function vect_analyze_data_ref_access.
1934 Analyze the access pattern of the data-reference DR. For now, a data access
1935 has to be consecutive to be considered vectorizable. */
1938 vect_analyze_data_ref_access (struct data_reference *dr)
1940 tree step = DR_STEP (dr);
1941 HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
1942 tree scalar_type = TREE_TYPE (DR_REF (dr));
1943 HOST_WIDE_INT type_size = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type));
1944 tree stmt = DR_STMT (dr);
1945 /* For interleaving, STRIDE is STEP counted in elements, i.e., the size of the
1946 interleaving group (including gaps). */
1947 HOST_WIDE_INT stride = dr_step / type_size;
1951 if (vect_print_dump_info (REPORT_DETAILS))
1952 fprintf (vect_dump, "bad data-ref access");
1957 if (!tree_int_cst_compare (step, TYPE_SIZE_UNIT (scalar_type)))
1959 /* Mark that it is not interleaving. */
1960 DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) = NULL_TREE;
1964 /* Not consecutive access is possible only if it is a part of interleaving. */
1965 if (!DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)))
1967 /* Check if it this DR is a part of interleaving, and is a single
1968 element of the group that is accessed in the loop. */
1970 /* Gaps are supported only for loads. STEP must be a multiple of the type
1971 size. The size of the group must be a power of 2. */
1973 && (dr_step % type_size) == 0
1975 && exact_log2 (stride) != -1)
1977 DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) = stmt;
1978 DR_GROUP_SIZE (vinfo_for_stmt (stmt)) = stride;
1979 if (vect_print_dump_info (REPORT_DR_DETAILS))
1981 fprintf (vect_dump, "Detected single element interleaving %d ",
1982 DR_GROUP_SIZE (vinfo_for_stmt (stmt)));
1983 print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM);
1984 fprintf (vect_dump, " step ");
1985 print_generic_expr (vect_dump, step, TDF_SLIM);
1989 if (vect_print_dump_info (REPORT_DETAILS))
1990 fprintf (vect_dump, "not consecutive access");
1994 if (DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) == stmt)
1996 /* First stmt in the interleaving chain. Check the chain. */
1997 tree next = DR_GROUP_NEXT_DR (vinfo_for_stmt (stmt));
1998 struct data_reference *data_ref = dr;
1999 unsigned int count = 1;
2001 tree prev_init = DR_INIT (data_ref);
2003 HOST_WIDE_INT diff, count_in_bytes;
2007 /* Skip same data-refs. In case that two or more stmts share data-ref
2008 (supported only for loads), we vectorize only the first stmt, and
2009 the rest get their vectorized loads from the first one. */
2010 if (!tree_int_cst_compare (DR_INIT (data_ref),
2011 DR_INIT (STMT_VINFO_DATA_REF (
2012 vinfo_for_stmt (next)))))
2014 if (!DR_IS_READ (data_ref))
2016 if (vect_print_dump_info (REPORT_DETAILS))
2017 fprintf (vect_dump, "Two store stmts share the same dr.");
2021 /* Check that there is no load-store dependencies for this loads
2022 to prevent a case of load-store-load to the same location. */
2023 if (DR_GROUP_READ_WRITE_DEPENDENCE (vinfo_for_stmt (next))
2024 || DR_GROUP_READ_WRITE_DEPENDENCE (vinfo_for_stmt (prev)))
2026 if (vect_print_dump_info (REPORT_DETAILS))
2028 "READ_WRITE dependence in interleaving.");
2032 /* For load use the same data-ref load. */
2033 DR_GROUP_SAME_DR_STMT (vinfo_for_stmt (next)) = prev;
2036 next = DR_GROUP_NEXT_DR (vinfo_for_stmt (next));
2041 /* Check that all the accesses have the same STEP. */
2042 next_step = DR_STEP (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
2043 if (tree_int_cst_compare (step, next_step))
2045 if (vect_print_dump_info (REPORT_DETAILS))
2046 fprintf (vect_dump, "not consecutive access in interleaving");
2050 data_ref = STMT_VINFO_DATA_REF (vinfo_for_stmt (next));
2051 /* Check that the distance between two accesses is equal to the type
2052 size. Otherwise, we have gaps. */
2053 diff = (TREE_INT_CST_LOW (DR_INIT (data_ref))
2054 - TREE_INT_CST_LOW (prev_init)) / type_size;
2055 if (!DR_IS_READ (data_ref) && diff != 1)
2057 if (vect_print_dump_info (REPORT_DETAILS))
2058 fprintf (vect_dump, "interleaved store with gaps");
2061 /* Store the gap from the previous member of the group. If there is no
2062 gap in the access, DR_GROUP_GAP is always 1. */
2063 DR_GROUP_GAP (vinfo_for_stmt (next)) = diff;
2065 prev_init = DR_INIT (data_ref);
2066 next = DR_GROUP_NEXT_DR (vinfo_for_stmt (next));
2067 /* Count the number of data-refs in the chain. */
2071 /* COUNT is the number of accesses found, we multiply it by the size of
2072 the type to get COUNT_IN_BYTES. */
2073 count_in_bytes = type_size * count;
2075 /* Check that the size of the interleaving is not greater than STEP. */
2076 if (dr_step < count_in_bytes)
2078 if (vect_print_dump_info (REPORT_DETAILS))
2080 fprintf (vect_dump, "interleaving size is greater than step for ");
2081 print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM);
2086 /* Check that the size of the interleaving is equal to STEP for stores,
2087 i.e., that there are no gaps. */
2088 if (!DR_IS_READ (dr) && dr_step != count_in_bytes)
2090 if (vect_print_dump_info (REPORT_DETAILS))
2091 fprintf (vect_dump, "interleaved store with gaps");
2095 /* Check that STEP is a multiple of type size. */
2096 if ((dr_step % type_size) != 0)
2098 if (vect_print_dump_info (REPORT_DETAILS))
2100 fprintf (vect_dump, "step is not a multiple of type size: step ");
2101 print_generic_expr (vect_dump, step, TDF_SLIM);
2102 fprintf (vect_dump, " size ");
2103 print_generic_expr (vect_dump, TYPE_SIZE_UNIT (scalar_type),
2109 /* FORNOW: we handle only interleaving that is a power of 2. */
2110 if (exact_log2 (stride) == -1)
2112 if (vect_print_dump_info (REPORT_DETAILS))
2113 fprintf (vect_dump, "interleaving is not a power of 2");
2116 DR_GROUP_SIZE (vinfo_for_stmt (stmt)) = stride;
2122 /* Function vect_analyze_data_ref_accesses.
2124 Analyze the access pattern of all the data references in the loop.
2126 FORNOW: the only access pattern that is considered vectorizable is a
2127 simple step 1 (consecutive) access.
2129 FORNOW: handle only arrays and pointer accesses. */
2132 vect_analyze_data_ref_accesses (loop_vec_info loop_vinfo)
2135 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
2136 struct data_reference *dr;
2138 if (vect_print_dump_info (REPORT_DETAILS))
2139 fprintf (vect_dump, "=== vect_analyze_data_ref_accesses ===");
2141 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
2142 if (!vect_analyze_data_ref_access (dr))
2144 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2145 fprintf (vect_dump, "not vectorized: complicated access pattern.");
2153 /* Function vect_analyze_data_refs.
2155 Find all the data references in the loop.
2157 The general structure of the analysis of data refs in the vectorizer is as
2159 1- vect_analyze_data_refs(loop): call compute_data_dependences_for_loop to
2160 find and analyze all data-refs in the loop and their dependences.
2161 2- vect_analyze_dependences(): apply dependence testing using ddrs.
2162 3- vect_analyze_drs_alignment(): check that ref_stmt.alignment is ok.
2163 4- vect_analyze_drs_access(): check that ref_stmt.step is ok.
2168 vect_analyze_data_refs (loop_vec_info loop_vinfo)
2170 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2172 VEC (data_reference_p, heap) *datarefs;
2173 struct data_reference *dr;
2176 if (vect_print_dump_info (REPORT_DETAILS))
2177 fprintf (vect_dump, "=== vect_analyze_data_refs ===\n");
2179 compute_data_dependences_for_loop (loop, true,
2180 &LOOP_VINFO_DATAREFS (loop_vinfo),
2181 &LOOP_VINFO_DDRS (loop_vinfo));
2183 /* Go through the data-refs, check that the analysis succeeded. Update pointer
2184 from stmt_vec_info struct to DR and vectype. */
2185 datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
2187 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
2190 stmt_vec_info stmt_info;
2192 if (!dr || !DR_REF (dr))
2194 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2195 fprintf (vect_dump, "not vectorized: unhandled data-ref ");
2199 /* Update DR field in stmt_vec_info struct. */
2200 stmt = DR_STMT (dr);
2201 stmt_info = vinfo_for_stmt (stmt);
2203 if (STMT_VINFO_DATA_REF (stmt_info))
2205 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2208 "not vectorized: more than one data ref in stmt: ");
2209 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2213 STMT_VINFO_DATA_REF (stmt_info) = dr;
2215 /* Check that analysis of the data-ref succeeded. */
2216 if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr) || !DR_INIT (dr)
2219 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2221 fprintf (vect_dump, "not vectorized: data ref analysis failed ");
2222 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2227 if (TREE_CODE (DR_BASE_ADDRESS (dr)) == INTEGER_CST)
2229 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2230 fprintf (vect_dump, "not vectorized: base addr of dr is a "
2235 if (!DR_SYMBOL_TAG (dr))
2237 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2239 fprintf (vect_dump, "not vectorized: no memory tag for ");
2240 print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM);
2245 /* Set vectype for STMT. */
2246 scalar_type = TREE_TYPE (DR_REF (dr));
2247 STMT_VINFO_VECTYPE (stmt_info) =
2248 get_vectype_for_scalar_type (scalar_type);
2249 if (!STMT_VINFO_VECTYPE (stmt_info))
2251 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2254 "not vectorized: no vectype for stmt: ");
2255 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2256 fprintf (vect_dump, " scalar_type: ");
2257 print_generic_expr (vect_dump, scalar_type, TDF_DETAILS);
2267 /* Utility functions used by vect_mark_stmts_to_be_vectorized. */
2269 /* Function vect_mark_relevant.
2271 Mark STMT as "relevant for vectorization" and add it to WORKLIST. */
2274 vect_mark_relevant (VEC(tree,heap) **worklist, tree stmt,
2275 enum vect_relevant relevant, bool live_p)
2277 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2278 enum vect_relevant save_relevant = STMT_VINFO_RELEVANT (stmt_info);
2279 bool save_live_p = STMT_VINFO_LIVE_P (stmt_info);
2281 if (vect_print_dump_info (REPORT_DETAILS))
2282 fprintf (vect_dump, "mark relevant %d, live %d.", relevant, live_p);
2284 if (STMT_VINFO_IN_PATTERN_P (stmt_info))
2288 /* This is the last stmt in a sequence that was detected as a
2289 pattern that can potentially be vectorized. Don't mark the stmt
2290 as relevant/live because it's not going to vectorized.
2291 Instead mark the pattern-stmt that replaces it. */
2292 if (vect_print_dump_info (REPORT_DETAILS))
2293 fprintf (vect_dump, "last stmt in pattern. don't mark relevant/live.");
2294 pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
2295 stmt_info = vinfo_for_stmt (pattern_stmt);
2296 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_info) == stmt);
2297 save_relevant = STMT_VINFO_RELEVANT (stmt_info);
2298 save_live_p = STMT_VINFO_LIVE_P (stmt_info);
2299 stmt = pattern_stmt;
2302 STMT_VINFO_LIVE_P (stmt_info) |= live_p;
2303 if (relevant > STMT_VINFO_RELEVANT (stmt_info))
2304 STMT_VINFO_RELEVANT (stmt_info) = relevant;
2306 if (STMT_VINFO_RELEVANT (stmt_info) == save_relevant
2307 && STMT_VINFO_LIVE_P (stmt_info) == save_live_p)
2309 if (vect_print_dump_info (REPORT_DETAILS))
2310 fprintf (vect_dump, "already marked relevant/live.");
2314 VEC_safe_push (tree, heap, *worklist, stmt);
2318 /* Function vect_stmt_relevant_p.
2320 Return true if STMT in loop that is represented by LOOP_VINFO is
2321 "relevant for vectorization".
2323 A stmt is considered "relevant for vectorization" if:
2324 - it has uses outside the loop.
2325 - it has vdefs (it alters memory).
2326 - control stmts in the loop (except for the exit condition).
2328 CHECKME: what other side effects would the vectorizer allow? */
2331 vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo,
2332 enum vect_relevant *relevant, bool *live_p)
2334 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2335 ssa_op_iter op_iter;
2336 imm_use_iterator imm_iter;
2337 use_operand_p use_p;
2338 def_operand_p def_p;
2340 *relevant = vect_unused_in_loop;
2343 /* cond stmt other than loop exit cond. */
2344 if (is_ctrl_stmt (stmt) && (stmt != LOOP_VINFO_EXIT_COND (loop_vinfo)))
2345 *relevant = vect_used_in_loop;
2347 /* changing memory. */
2348 if (TREE_CODE (stmt) != PHI_NODE)
2349 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
2351 if (vect_print_dump_info (REPORT_DETAILS))
2352 fprintf (vect_dump, "vec_stmt_relevant_p: stmt has vdefs.");
2353 *relevant = vect_used_in_loop;
2356 /* uses outside the loop. */
2357 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_DEF)
2359 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
2361 basic_block bb = bb_for_stmt (USE_STMT (use_p));
2362 if (!flow_bb_inside_loop_p (loop, bb))
2364 if (vect_print_dump_info (REPORT_DETAILS))
2365 fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop.");
2367 /* We expect all such uses to be in the loop exit phis
2368 (because of loop closed form) */
2369 gcc_assert (TREE_CODE (USE_STMT (use_p)) == PHI_NODE);
2370 gcc_assert (bb == single_exit (loop)->dest);
2377 return (*live_p || *relevant);
2382 Function process_use.
2385 - a USE in STMT in a loop represented by LOOP_VINFO
2386 - LIVE_P, RELEVANT - enum values to be set in the STMT_VINFO of the stmt
2387 that defined USE. This is dont by calling mark_relevant and passing it
2388 the WORKLIST (to add DEF_STMT to the WORKlist in case itis relevant).
2391 Generally, LIVE_P and RELEVANT are used to define the liveness and
2392 relevance info of the DEF_STMT of this USE:
2393 STMT_VINFO_LIVE_P (DEF_STMT_info) <-- live_p
2394 STMT_VINFO_RELEVANT (DEF_STMT_info) <-- relevant
2396 - case 1: If USE is used only for address computations (e.g. array indexing),
2397 which does not need to be directly vectorized, then the liveness/relevance
2398 of the respective DEF_STMT is left unchanged.
2399 - case 2: If STMT is a reduction phi and DEF_STMT is a reduction stmt, we
2400 skip DEF_STMT cause it had already been processed.
2402 Return true if everything is as expected. Return false otherwise. */
2405 process_use (tree stmt, tree use, loop_vec_info loop_vinfo, bool live_p,
2406 enum vect_relevant relevant, VEC(tree,heap) **worklist)
2408 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2409 stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
2410 stmt_vec_info dstmt_vinfo;
2413 enum vect_def_type dt;
2415 /* case 1: we are only interested in uses that need to be vectorized. Uses
2416 that are used for address computation are not considered relevant. */
2417 if (!exist_non_indexing_operands_for_use_p (use, stmt))
2420 if (!vect_is_simple_use (use, loop_vinfo, &def_stmt, &def, &dt))
2422 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2423 fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
2427 if (!def_stmt || IS_EMPTY_STMT (def_stmt))
2430 def_bb = bb_for_stmt (def_stmt);
2431 if (!flow_bb_inside_loop_p (loop, def_bb))
2434 /* case 2: A reduction phi defining a reduction stmt (DEF_STMT). DEF_STMT
2435 must have already been processed, so we just check that everything is as
2436 expected, and we are done. */
2437 dstmt_vinfo = vinfo_for_stmt (def_stmt);
2438 if (TREE_CODE (stmt) == PHI_NODE
2439 && STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def
2440 && TREE_CODE (def_stmt) != PHI_NODE
2441 && STMT_VINFO_DEF_TYPE (dstmt_vinfo) == vect_reduction_def)
2443 if (STMT_VINFO_IN_PATTERN_P (dstmt_vinfo))
2444 dstmt_vinfo = vinfo_for_stmt (STMT_VINFO_RELATED_STMT (dstmt_vinfo));
2445 gcc_assert (STMT_VINFO_RELEVANT (dstmt_vinfo) < vect_used_by_reduction);
2446 gcc_assert (STMT_VINFO_LIVE_P (dstmt_vinfo)
2447 || STMT_VINFO_RELEVANT (dstmt_vinfo) > vect_unused_in_loop);
2451 vect_mark_relevant (worklist, def_stmt, relevant, live_p);
2456 /* Function vect_mark_stmts_to_be_vectorized.
2458 Not all stmts in the loop need to be vectorized. For example:
2467 Stmt 1 and 3 do not need to be vectorized, because loop control and
2468 addressing of vectorized data-refs are handled differently.
2470 This pass detects such stmts. */
2473 vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo)
2475 VEC(tree,heap) *worklist;
2476 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2477 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
2478 unsigned int nbbs = loop->num_nodes;
2479 block_stmt_iterator si;
2483 stmt_vec_info stmt_vinfo;
2487 enum vect_relevant relevant;
2489 if (vect_print_dump_info (REPORT_DETAILS))
2490 fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ===");
2492 worklist = VEC_alloc (tree, heap, 64);
2494 /* 1. Init worklist. */
2495 for (i = 0; i < nbbs; i++)
2498 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2500 if (vect_print_dump_info (REPORT_DETAILS))
2502 fprintf (vect_dump, "init: phi relevant? ");
2503 print_generic_expr (vect_dump, phi, TDF_SLIM);
2506 if (vect_stmt_relevant_p (phi, loop_vinfo, &relevant, &live_p))
2507 vect_mark_relevant (&worklist, phi, relevant, live_p);
2509 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2511 stmt = bsi_stmt (si);
2512 if (vect_print_dump_info (REPORT_DETAILS))
2514 fprintf (vect_dump, "init: stmt relevant? ");
2515 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2518 if (vect_stmt_relevant_p (stmt, loop_vinfo, &relevant, &live_p))
2519 vect_mark_relevant (&worklist, stmt, relevant, live_p);
2523 /* 2. Process_worklist */
2524 while (VEC_length (tree, worklist) > 0)
2526 use_operand_p use_p;
2529 stmt = VEC_pop (tree, worklist);
2530 if (vect_print_dump_info (REPORT_DETAILS))
2532 fprintf (vect_dump, "worklist: examine stmt: ");
2533 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2536 /* Examine the USEs of STMT. For each USE, mark the stmt that defines it
2537 (DEF_STMT) as relevant/irrelevant and live/dead according to the
2538 liveness and relevance properties of STMT. */
2539 ann = stmt_ann (stmt);
2540 stmt_vinfo = vinfo_for_stmt (stmt);
2541 relevant = STMT_VINFO_RELEVANT (stmt_vinfo);
2542 live_p = STMT_VINFO_LIVE_P (stmt_vinfo);
2544 /* Generally, the liveness and relevance properties of STMT are
2545 propagated as is to the DEF_STMTs of its USEs:
2546 live_p <-- STMT_VINFO_LIVE_P (STMT_VINFO)
2547 relevant <-- STMT_VINFO_RELEVANT (STMT_VINFO)
2549 One exception is when STMT has been identified as defining a reduction
2550 variable; in this case we set the liveness/relevance as follows:
2552 relevant = vect_used_by_reduction
2553 This is because we distinguish between two kinds of relevant stmts -
2554 those that are used by a reduction computation, and those that are
2555 (also) used by a regular computation. This allows us later on to
2556 identify stmts that are used solely by a reduction, and therefore the
2557 order of the results that they produce does not have to be kept.
2559 Reduction phis are expected to be used by a reduction stmt; Other
2560 reduction stmts are expected to be unused in the loop. These are the
2561 expected values of "relevant" for reduction phis/stmts in the loop:
2564 vect_unused_in_loop ok
2565 vect_used_by_reduction ok
2566 vect_used_in_loop */
2568 if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def)
2572 case vect_unused_in_loop:
2573 gcc_assert (TREE_CODE (stmt) != PHI_NODE);
2575 case vect_used_by_reduction:
2576 if (TREE_CODE (stmt) == PHI_NODE)
2578 case vect_used_in_loop:
2580 if (vect_print_dump_info (REPORT_DETAILS))
2581 fprintf (vect_dump, "unsupported use of reduction.");
2582 VEC_free (tree, heap, worklist);
2585 relevant = vect_used_by_reduction;
2589 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2591 tree op = USE_FROM_PTR (use_p);
2592 if (!process_use (stmt, op, loop_vinfo, live_p, relevant, &worklist))
2594 VEC_free (tree, heap, worklist);
2598 } /* while worklist */
2600 VEC_free (tree, heap, worklist);
2605 /* Function vect_can_advance_ivs_p
2607 In case the number of iterations that LOOP iterates is unknown at compile
2608 time, an epilog loop will be generated, and the loop induction variables
2609 (IVs) will be "advanced" to the value they are supposed to take just before
2610 the epilog loop. Here we check that the access function of the loop IVs
2611 and the expression that represents the loop bound are simple enough.
2612 These restrictions will be relaxed in the future. */
2615 vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
2617 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2618 basic_block bb = loop->header;
2621 /* Analyze phi functions of the loop header. */
2623 if (vect_print_dump_info (REPORT_DETAILS))
2624 fprintf (vect_dump, "vect_can_advance_ivs_p:");
2626 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2628 tree access_fn = NULL;
2629 tree evolution_part;
2631 if (vect_print_dump_info (REPORT_DETAILS))
2633 fprintf (vect_dump, "Analyze phi: ");
2634 print_generic_expr (vect_dump, phi, TDF_SLIM);
2637 /* Skip virtual phi's. The data dependences that are associated with
2638 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
2640 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
2642 if (vect_print_dump_info (REPORT_DETAILS))
2643 fprintf (vect_dump, "virtual phi. skip.");
2647 /* Skip reduction phis. */
2649 if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (phi)) == vect_reduction_def)
2651 if (vect_print_dump_info (REPORT_DETAILS))
2652 fprintf (vect_dump, "reduc phi. skip.");
2656 /* Analyze the evolution function. */
2658 access_fn = instantiate_parameters
2659 (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2663 if (vect_print_dump_info (REPORT_DETAILS))
2664 fprintf (vect_dump, "No Access function.");
2668 if (vect_print_dump_info (REPORT_DETAILS))
2670 fprintf (vect_dump, "Access function of PHI: ");
2671 print_generic_expr (vect_dump, access_fn, TDF_SLIM);
2674 evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
2676 if (evolution_part == NULL_TREE)
2678 if (vect_print_dump_info (REPORT_DETAILS))
2679 fprintf (vect_dump, "No evolution.");
2683 /* FORNOW: We do not transform initial conditions of IVs
2684 which evolution functions are a polynomial of degree >= 2. */
2686 if (tree_is_chrec (evolution_part))
2694 /* Function vect_get_loop_niters.
2696 Determine how many iterations the loop is executed.
2697 If an expression that represents the number of iterations
2698 can be constructed, place it in NUMBER_OF_ITERATIONS.
2699 Return the loop exit condition. */
2702 vect_get_loop_niters (struct loop *loop, tree *number_of_iterations)
2706 if (vect_print_dump_info (REPORT_DETAILS))
2707 fprintf (vect_dump, "=== get_loop_niters ===");
2709 niters = number_of_exit_cond_executions (loop);
2711 if (niters != NULL_TREE
2712 && niters != chrec_dont_know)
2714 *number_of_iterations = niters;
2716 if (vect_print_dump_info (REPORT_DETAILS))
2718 fprintf (vect_dump, "==> get_loop_niters:" );
2719 print_generic_expr (vect_dump, *number_of_iterations, TDF_SLIM);
2723 return get_loop_exit_condition (loop);
2727 /* Function vect_analyze_loop_form.
2729 Verify the following restrictions (some may be relaxed in the future):
2730 - it's an inner-most loop
2731 - number of BBs = 2 (which are the loop header and the latch)
2732 - the loop has a pre-header
2733 - the loop has a single entry and exit
2734 - the loop exit condition is simple enough, and the number of iterations
2735 can be analyzed (a countable loop). */
2737 static loop_vec_info
2738 vect_analyze_loop_form (struct loop *loop)
2740 loop_vec_info loop_vinfo;
2742 tree number_of_iterations = NULL;
2744 if (vect_print_dump_info (REPORT_DETAILS))
2745 fprintf (vect_dump, "=== vect_analyze_loop_form ===");
2749 if (vect_print_dump_info (REPORT_OUTER_LOOPS))
2750 fprintf (vect_dump, "not vectorized: nested loop.");
2754 if (!single_exit (loop)
2755 || loop->num_nodes != 2
2756 || EDGE_COUNT (loop->header->preds) != 2)
2758 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2760 if (!single_exit (loop))
2761 fprintf (vect_dump, "not vectorized: multiple exits.");
2762 else if (loop->num_nodes != 2)
2763 fprintf (vect_dump, "not vectorized: too many BBs in loop.");
2764 else if (EDGE_COUNT (loop->header->preds) != 2)
2765 fprintf (vect_dump, "not vectorized: too many incoming edges.");
2771 /* We assume that the loop exit condition is at the end of the loop. i.e,
2772 that the loop is represented as a do-while (with a proper if-guard
2773 before the loop if needed), where the loop header contains all the
2774 executable statements, and the latch is empty. */
2775 if (!empty_block_p (loop->latch)
2776 || phi_nodes (loop->latch))
2778 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2779 fprintf (vect_dump, "not vectorized: unexpected loop form.");
2783 /* Make sure there exists a single-predecessor exit bb: */
2784 if (!single_pred_p (single_exit (loop)->dest))
2786 edge e = single_exit (loop);
2787 if (!(e->flags & EDGE_ABNORMAL))
2789 split_loop_exit_edge (e);
2790 if (vect_print_dump_info (REPORT_DETAILS))
2791 fprintf (vect_dump, "split exit edge.");
2795 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2796 fprintf (vect_dump, "not vectorized: abnormal loop exit edge.");
2801 if (empty_block_p (loop->header))
2803 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2804 fprintf (vect_dump, "not vectorized: empty loop.");
2808 loop_cond = vect_get_loop_niters (loop, &number_of_iterations);
2811 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2812 fprintf (vect_dump, "not vectorized: complicated exit condition.");
2816 if (!number_of_iterations)
2818 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2820 "not vectorized: number of iterations cannot be computed.");
2824 if (chrec_contains_undetermined (number_of_iterations))
2826 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
2827 fprintf (vect_dump, "Infinite number of iterations.");
2831 if (!NITERS_KNOWN_P (number_of_iterations))
2833 if (vect_print_dump_info (REPORT_DETAILS))
2835 fprintf (vect_dump, "Symbolic number of iterations is ");
2836 print_generic_expr (vect_dump, number_of_iterations, TDF_DETAILS);
2839 else if (TREE_INT_CST_LOW (number_of_iterations) == 0)
2841 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
2842 fprintf (vect_dump, "not vectorized: number of iterations = 0.");
2846 loop_vinfo = new_loop_vec_info (loop);
2847 LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
2848 LOOP_VINFO_EXIT_COND (loop_vinfo) = loop_cond;
2850 gcc_assert (!loop->aux);
2851 loop->aux = loop_vinfo;
2856 /* Function vect_analyze_loop.
2858 Apply a set of analyses on LOOP, and create a loop_vec_info struct
2859 for it. The different analyses will record information in the
2860 loop_vec_info struct. */
2862 vect_analyze_loop (struct loop *loop)
2865 loop_vec_info loop_vinfo;
2867 if (vect_print_dump_info (REPORT_DETAILS))
2868 fprintf (vect_dump, "===== analyze_loop_nest =====");
2870 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
2872 loop_vinfo = vect_analyze_loop_form (loop);
2875 if (vect_print_dump_info (REPORT_DETAILS))
2876 fprintf (vect_dump, "bad loop form.");
2880 /* Find all data references in the loop (which correspond to vdefs/vuses)
2881 and analyze their evolution in the loop.
2883 FORNOW: Handle only simple, array references, which
2884 alignment can be forced, and aligned pointer-references. */
2886 ok = vect_analyze_data_refs (loop_vinfo);
2889 if (vect_print_dump_info (REPORT_DETAILS))
2890 fprintf (vect_dump, "bad data references.");
2891 destroy_loop_vec_info (loop_vinfo);
2895 /* Classify all cross-iteration scalar data-flow cycles.
2896 Cross-iteration cycles caused by virtual phis are analyzed separately. */
2898 vect_analyze_scalar_cycles (loop_vinfo);
2900 vect_pattern_recog (loop_vinfo);
2902 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
2904 ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
2907 if (vect_print_dump_info (REPORT_DETAILS))
2908 fprintf (vect_dump, "unexpected pattern.");
2909 destroy_loop_vec_info (loop_vinfo);
2913 /* Analyze the alignment of the data-refs in the loop.
2914 Fail if a data reference is found that cannot be vectorized. */
2916 ok = vect_analyze_data_refs_alignment (loop_vinfo);
2919 if (vect_print_dump_info (REPORT_DETAILS))
2920 fprintf (vect_dump, "bad data alignment.");
2921 destroy_loop_vec_info (loop_vinfo);
2925 ok = vect_determine_vectorization_factor (loop_vinfo);
2928 if (vect_print_dump_info (REPORT_DETAILS))
2929 fprintf (vect_dump, "can't determine vectorization factor.");
2930 destroy_loop_vec_info (loop_vinfo);
2934 /* Analyze data dependences between the data-refs in the loop.
2935 FORNOW: fail at the first data dependence that we encounter. */
2937 ok = vect_analyze_data_ref_dependences (loop_vinfo);
2940 if (vect_print_dump_info (REPORT_DETAILS))
2941 fprintf (vect_dump, "bad data dependence.");
2942 destroy_loop_vec_info (loop_vinfo);
2946 /* Analyze the access patterns of the data-refs in the loop (consecutive,
2947 complex, etc.). FORNOW: Only handle consecutive access pattern. */
2949 ok = vect_analyze_data_ref_accesses (loop_vinfo);
2952 if (vect_print_dump_info (REPORT_DETAILS))
2953 fprintf (vect_dump, "bad data access.");
2954 destroy_loop_vec_info (loop_vinfo);
2958 /* This pass will decide on using loop versioning and/or loop peeling in
2959 order to enhance the alignment of data references in the loop. */
2961 ok = vect_enhance_data_refs_alignment (loop_vinfo);
2964 if (vect_print_dump_info (REPORT_DETAILS))
2965 fprintf (vect_dump, "bad data alignment.");
2966 destroy_loop_vec_info (loop_vinfo);
2970 /* Scan all the operations in the loop and make sure they are
2973 ok = vect_analyze_operations (loop_vinfo);
2976 if (vect_print_dump_info (REPORT_DETAILS))
2977 fprintf (vect_dump, "bad operation or unsupported loop bound.");
2978 destroy_loop_vec_info (loop_vinfo);
2982 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1;