1 /* Analysis Utilities for Loop Vectorization.
2 Copyright (C) 2003,2004,2005 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com>
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, 59 Temple Place - Suite 330, Boston, MA
24 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-flow.h"
31 #include "tree-dump.h"
36 #include "tree-chrec.h"
37 #include "tree-data-ref.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-vectorizer.h"
41 /* Main analysis functions. */
42 static loop_vec_info vect_analyze_loop_form (struct loop *);
43 static bool vect_analyze_data_refs (loop_vec_info);
44 static bool vect_mark_stmts_to_be_vectorized (loop_vec_info);
45 static void vect_analyze_scalar_cycles (loop_vec_info);
46 static bool vect_analyze_data_ref_accesses (loop_vec_info);
47 static bool vect_analyze_data_ref_dependences (loop_vec_info);
48 static bool vect_analyze_data_refs_alignment (loop_vec_info);
49 static bool vect_compute_data_refs_alignment (loop_vec_info);
50 static void vect_enhance_data_refs_alignment (loop_vec_info);
51 static bool vect_analyze_operations (loop_vec_info);
52 static bool vect_determine_vectorization_factor (loop_vec_info);
54 /* Utility functions for the analyses. */
55 static bool exist_non_indexing_operands_for_use_p (tree, tree);
56 static void vect_mark_relevant (VEC(tree,heap) **, tree, bool, bool);
57 static bool vect_stmt_relevant_p (tree, loop_vec_info, bool *, bool *);
58 static tree vect_get_loop_niters (struct loop *, tree *);
59 static bool vect_analyze_data_ref_dependence
60 (struct data_reference *, struct data_reference *, loop_vec_info);
61 static bool vect_compute_data_ref_alignment (struct data_reference *);
62 static bool vect_analyze_data_ref_access (struct data_reference *);
63 static struct data_reference * vect_analyze_pointer_ref_access
64 (tree, tree, bool, tree, tree *, tree *);
65 static bool vect_can_advance_ivs_p (loop_vec_info);
66 static tree vect_get_ptr_offset (tree, tree, tree *);
67 static bool vect_analyze_offset_expr (tree, struct loop *, tree, tree *,
69 static bool vect_base_addr_differ_p (struct data_reference *,
70 struct data_reference *drb, bool *);
71 static tree vect_object_analysis (tree, tree, bool, tree,
72 struct data_reference **, tree *, tree *,
73 tree *, bool *, tree *, struct ptr_info_def **,
75 static tree vect_address_analysis (tree, tree, bool, tree,
76 struct data_reference *, tree *, tree *,
80 /* Function vect_get_ptr_offset
82 Compute the OFFSET modulo vector-type alignment of pointer REF in bits. */
85 vect_get_ptr_offset (tree ref ATTRIBUTE_UNUSED,
86 tree vectype ATTRIBUTE_UNUSED,
87 tree *offset ATTRIBUTE_UNUSED)
89 /* TODO: Use alignment information. */
94 /* Function vect_analyze_offset_expr
96 Given an offset expression EXPR received from get_inner_reference, analyze
97 it and create an expression for INITIAL_OFFSET by substituting the variables
98 of EXPR with initial_condition of the corresponding access_fn in the loop.
101 for (j = 3; j < N; j++)
104 For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be
105 substituted, since its access_fn in the inner loop is i. 'j' will be
106 substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
109 Compute MISALIGN (the misalignment of the data reference initial access from
110 its base) if possible. Misalignment can be calculated only if all the
111 variables can be substituted with constants, or if a variable is multiplied
112 by a multiple of VECTYPE_ALIGNMENT. In the above example, since 'i' cannot
113 be substituted, MISALIGN will be NULL_TREE in case that C_i is not a multiple
114 of VECTYPE_ALIGNMENT, and C` otherwise. (We perform MISALIGN modulo
115 VECTYPE_ALIGNMENT computation in the caller of this function).
117 STEP is an evolution of the data reference in this loop in bytes.
118 In the above example, STEP is C_j.
120 Return FALSE, if the analysis fails, e.g., there is no access_fn for a
121 variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN and STEP)
122 are NULL_TREEs. Otherwise, return TRUE.
127 vect_analyze_offset_expr (tree expr,
129 tree vectype_alignment,
130 tree *initial_offset,
136 tree left_offset = ssize_int (0);
137 tree right_offset = ssize_int (0);
138 tree left_misalign = ssize_int (0);
139 tree right_misalign = ssize_int (0);
140 tree left_step = ssize_int (0);
141 tree right_step = ssize_int (0);
143 tree init, evolution;
146 *misalign = NULL_TREE;
147 *initial_offset = NULL_TREE;
149 /* Strip conversions that don't narrow the mode. */
150 expr = vect_strip_conversion (expr);
156 if (TREE_CODE (expr) == INTEGER_CST)
158 *initial_offset = fold_convert (ssizetype, expr);
159 *misalign = fold_convert (ssizetype, expr);
160 *step = ssize_int (0);
164 /* 2. Variable. Try to substitute with initial_condition of the corresponding
165 access_fn in the current loop. */
166 if (SSA_VAR_P (expr))
168 tree access_fn = analyze_scalar_evolution (loop, expr);
170 if (access_fn == chrec_dont_know)
174 init = initial_condition_in_loop_num (access_fn, loop->num);
175 if (init == expr && !expr_invariant_in_loop_p (loop, init))
176 /* Not enough information: may be not loop invariant.
177 E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
178 initial_condition is D, but it depends on i - loop's induction
182 evolution = evolution_part_in_loop_num (access_fn, loop->num);
183 if (evolution && TREE_CODE (evolution) != INTEGER_CST)
184 /* Evolution is not constant. */
187 if (TREE_CODE (init) == INTEGER_CST)
188 *misalign = fold_convert (ssizetype, init);
190 /* Not constant, misalignment cannot be calculated. */
191 *misalign = NULL_TREE;
193 *initial_offset = fold_convert (ssizetype, init);
195 *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
199 /* Recursive computation. */
200 if (!BINARY_CLASS_P (expr))
202 /* We expect to get binary expressions (PLUS/MINUS and MULT). */
203 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
205 fprintf (vect_dump, "Not binary expression ");
206 print_generic_expr (vect_dump, expr, TDF_SLIM);
210 oprnd0 = TREE_OPERAND (expr, 0);
211 oprnd1 = TREE_OPERAND (expr, 1);
213 if (!vect_analyze_offset_expr (oprnd0, loop, vectype_alignment, &left_offset,
214 &left_misalign, &left_step)
215 || !vect_analyze_offset_expr (oprnd1, loop, vectype_alignment,
216 &right_offset, &right_misalign, &right_step))
219 /* The type of the operation: plus, minus or mult. */
220 code = TREE_CODE (expr);
224 if (TREE_CODE (right_offset) != INTEGER_CST)
225 /* RIGHT_OFFSET can be not constant. For example, for arrays of variable
227 FORNOW: We don't support such cases. */
230 /* Strip conversions that don't narrow the mode. */
231 left_offset = vect_strip_conversion (left_offset);
234 /* Misalignment computation. */
235 if (SSA_VAR_P (left_offset))
237 /* If the left side contains variables that can't be substituted with
238 constants, we check if the right side is a multiple of ALIGNMENT.
240 if (integer_zerop (size_binop (TRUNC_MOD_EXPR, right_offset,
241 fold_convert (ssizetype, vectype_alignment))))
242 *misalign = ssize_int (0);
244 /* If the remainder is not zero or the right side isn't constant,
245 we can't compute misalignment. */
246 *misalign = NULL_TREE;
250 /* The left operand was successfully substituted with constant. */
252 /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is
254 *misalign = size_binop (code, left_misalign, right_misalign);
256 *misalign = NULL_TREE;
259 /* Step calculation. */
260 /* Multiply the step by the right operand. */
261 *step = size_binop (MULT_EXPR, left_step, right_offset);
266 /* Combine the recursive calculations for step and misalignment. */
267 *step = size_binop (code, left_step, right_step);
269 if (left_misalign && right_misalign)
270 *misalign = size_binop (code, left_misalign, right_misalign);
272 *misalign = NULL_TREE;
280 /* Compute offset. */
281 *initial_offset = fold_convert (ssizetype,
282 fold (build2 (code, TREE_TYPE (left_offset),
289 /* Function vect_determine_vectorization_factor
291 Determine the vectorization factor (VF). VF is the number of data elements
292 that are operated upon in parallel in a single iteration of the vectorized
293 loop. For example, when vectorizing a loop that operates on 4byte elements,
294 on a target with vector size (VS) 16byte, the VF is set to 4, since 4
295 elements can fit in a single vector register.
297 We currently support vectorization of loops in which all types operated upon
298 are of the same size. Therefore this function currently sets VF according to
299 the size of the types operated upon, and fails if there are multiple sizes
302 VF is also the factor by which the loop iterations are strip-mined, e.g.:
309 for (i=0; i<N; i+=VF){
310 a[i:VF] = b[i:VF] + c[i:VF];
315 vect_determine_vectorization_factor (loop_vec_info loop_vinfo)
317 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
318 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
319 int nbbs = loop->num_nodes;
320 block_stmt_iterator si;
321 unsigned int vectorization_factor = 0;
325 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
326 fprintf (vect_dump, "=== vect_determine_vectorization_factor ===");
328 for (i = 0; i < nbbs; i++)
330 basic_block bb = bbs[i];
332 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
334 tree stmt = bsi_stmt (si);
336 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
339 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
341 fprintf (vect_dump, "==> examining statement: ");
342 print_generic_expr (vect_dump, stmt, TDF_SLIM);
345 gcc_assert (stmt_info);
346 /* skip stmts which do not need to be vectorized. */
347 if (!STMT_VINFO_RELEVANT_P (stmt_info)
348 && !STMT_VINFO_LIVE_P (stmt_info))
350 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
351 fprintf (vect_dump, "skip.");
355 if (VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))))
357 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
358 LOOP_LOC (loop_vinfo)))
360 fprintf (vect_dump, "not vectorized: vector stmt in loop:");
361 print_generic_expr (vect_dump, stmt, TDF_SLIM);
366 if (STMT_VINFO_DATA_REF (stmt_info))
367 scalar_type = TREE_TYPE (DR_REF (STMT_VINFO_DATA_REF (stmt_info)));
368 else if (TREE_CODE (stmt) == MODIFY_EXPR)
369 scalar_type = TREE_TYPE (TREE_OPERAND (stmt, 0));
371 scalar_type = TREE_TYPE (stmt);
373 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
375 fprintf (vect_dump, "get vectype for scalar type: ");
376 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
379 vectype = get_vectype_for_scalar_type (scalar_type);
382 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
383 LOOP_LOC (loop_vinfo)))
385 fprintf (vect_dump, "not vectorized: unsupported data-type ");
386 print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
390 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
392 fprintf (vect_dump, "vectype: ");
393 print_generic_expr (vect_dump, vectype, TDF_SLIM);
395 STMT_VINFO_VECTYPE (stmt_info) = vectype;
397 nunits = TYPE_VECTOR_SUBPARTS (vectype);
398 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
399 fprintf (vect_dump, "nunits = %d", nunits);
401 if (vectorization_factor)
403 /* FORNOW: don't allow mixed units.
404 This restriction will be relaxed in the future. */
405 if (nunits != vectorization_factor)
407 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
408 LOOP_LOC (loop_vinfo)))
409 fprintf (vect_dump, "not vectorized: mixed data-types");
414 vectorization_factor = nunits;
416 #ifdef ENABLE_CHECKING
417 gcc_assert (GET_MODE_SIZE (TYPE_MODE (scalar_type))
418 * vectorization_factor == UNITS_PER_SIMD_WORD);
423 /* TODO: Analyze cost. Decide if worth while to vectorize. */
425 if (vectorization_factor <= 1)
427 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
428 LOOP_LOC (loop_vinfo)))
429 fprintf (vect_dump, "not vectorized: unsupported data-type");
432 LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
438 /* Function vect_analyze_operations.
440 Scan the loop stmts and make sure they are all vectorizable. */
443 vect_analyze_operations (loop_vec_info loop_vinfo)
445 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
446 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
447 int nbbs = loop->num_nodes;
448 block_stmt_iterator si;
449 unsigned int vectorization_factor = 0;
453 stmt_vec_info stmt_info;
454 bool need_to_vectorize = false;
456 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
457 fprintf (vect_dump, "=== vect_analyze_operations ===");
459 gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo));
460 vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
462 for (i = 0; i < nbbs; i++)
464 basic_block bb = bbs[i];
466 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
468 stmt_info = vinfo_for_stmt (phi);
469 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
471 fprintf (vect_dump, "examining phi: ");
472 print_generic_expr (vect_dump, phi, TDF_SLIM);
475 gcc_assert (stmt_info);
477 if (STMT_VINFO_LIVE_P (stmt_info))
479 /* FORNOW: not yet supported. */
480 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
481 LOOP_LOC (loop_vinfo)))
482 fprintf (vect_dump, "not vectorized: value used after loop.");
486 gcc_assert (!STMT_VINFO_RELEVANT_P (stmt_info));
489 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
491 tree stmt = bsi_stmt (si);
492 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
494 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
496 fprintf (vect_dump, "==> examining statement: ");
497 print_generic_expr (vect_dump, stmt, TDF_SLIM);
500 gcc_assert (stmt_info);
502 /* skip stmts which do not need to be vectorized.
503 this is expected to include:
504 - the COND_EXPR which is the loop exit condition
505 - any LABEL_EXPRs in the loop
506 - computations that are used only for array indexing or loop
509 if (!STMT_VINFO_RELEVANT_P (stmt_info)
510 && !STMT_VINFO_LIVE_P (stmt_info))
512 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
513 fprintf (vect_dump, "irrelevant.");
517 if (STMT_VINFO_RELEVANT_P (stmt_info))
519 gcc_assert (!VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))));
520 gcc_assert (STMT_VINFO_VECTYPE (stmt_info));
522 ok = (vectorizable_operation (stmt, NULL, NULL)
523 || vectorizable_assignment (stmt, NULL, NULL)
524 || vectorizable_load (stmt, NULL, NULL)
525 || vectorizable_store (stmt, NULL, NULL)
526 || vectorizable_condition (stmt, NULL, NULL));
530 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
531 LOOP_LOC (loop_vinfo)))
534 "not vectorized: relevant stmt not supported: ");
535 print_generic_expr (vect_dump, stmt, TDF_SLIM);
539 need_to_vectorize = true;
542 if (STMT_VINFO_LIVE_P (stmt_info))
544 ok = vectorizable_live_operation (stmt, NULL, NULL);
548 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
549 LOOP_LOC (loop_vinfo)))
552 "not vectorized: live stmt not supported: ");
553 print_generic_expr (vect_dump, stmt, TDF_SLIM);
561 /* TODO: Analyze cost. Decide if worth while to vectorize. */
563 /* All operations in the loop are either irrelevant (deal with loop
564 control, or dead), or only used outside the loop and can be moved
565 out of the loop (e.g. invariants, inductions). The loop can be
566 optimized away by scalar optimizations. We're better off not
567 touching this loop. */
568 if (!need_to_vectorize)
570 if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
572 "All the computation can be taken out of the loop.");
573 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
574 LOOP_LOC (loop_vinfo)))
576 "not vectorized: redundant loop. no profit to vectorize.");
580 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
581 && vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
583 "vectorization_factor = %d, niters = " HOST_WIDE_INT_PRINT_DEC,
584 vectorization_factor, LOOP_VINFO_INT_NITERS (loop_vinfo));
586 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
587 && LOOP_VINFO_INT_NITERS (loop_vinfo) < vectorization_factor)
589 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
590 LOOP_LOC (loop_vinfo)))
591 fprintf (vect_dump, "not vectorized: iteration count too small.");
595 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
596 || LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0)
598 if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
599 fprintf (vect_dump, "epilog loop required.");
600 if (!vect_can_advance_ivs_p (loop_vinfo))
602 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
603 LOOP_LOC (loop_vinfo)))
605 "not vectorized: can't create epilog loop 1.");
608 if (!slpeel_can_duplicate_loop_p (loop, loop->single_exit))
610 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
611 LOOP_LOC (loop_vinfo)))
613 "not vectorized: can't create epilog loop 2.");
622 /* Function exist_non_indexing_operands_for_use_p
624 USE is one of the uses attached to STMT. Check if USE is
625 used in STMT for anything other than indexing an array. */
628 exist_non_indexing_operands_for_use_p (tree use, tree stmt)
631 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
633 /* USE corresponds to some operand in STMT. If there is no data
634 reference in STMT, then any operand that corresponds to USE
635 is not indexing an array. */
636 if (!STMT_VINFO_DATA_REF (stmt_info))
639 /* STMT has a data_ref. FORNOW this means that its of one of
643 (This should have been verified in analyze_data_refs).
645 'var' in the second case corresponds to a def, not a use,
646 so USE cannot correspond to any operands that are not used
649 Therefore, all we need to check is if STMT falls into the
650 first case, and whether var corresponds to USE. */
652 if (TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
655 operand = TREE_OPERAND (stmt, 1);
657 if (TREE_CODE (operand) != SSA_NAME)
667 /* Function vect_analyze_scalar_cycles.
669 Examine the cross iteration def-use cycles of scalar variables, by
670 analyzing the loop (scalar) PHIs; Classify each cycle as one of the
671 following: invariant, induction, reduction, unknown.
673 Some forms of scalar cycles are not yet supported.
675 Example1: reduction: (unsupported yet)
681 Example2: induction: (unsupported yet)
687 Note: the following loop *is* vectorizable:
693 even though it has a def-use cycle caused by the induction variable i:
695 loop: i_2 = PHI (i_0, i_1)
700 because the def-use cycle in loop3 is considered "not relevant" - i.e.,
701 it does not need to be vectorized because it is only used for array
702 indexing (see 'mark_stmts_to_be_vectorized'). The def-use cycle in
703 loop2 on the other hand is relevant (it is being written to memory).
707 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
710 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
711 basic_block bb = loop->header;
714 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
715 fprintf (vect_dump, "=== vect_analyze_scalar_cycles ===");
717 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
719 tree access_fn = NULL;
720 tree def = PHI_RESULT (phi);
721 stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
724 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
726 fprintf (vect_dump, "Analyze phi: ");
727 print_generic_expr (vect_dump, phi, TDF_SLIM);
730 /* Skip virtual phi's. The data dependences that are associated with
731 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
733 if (!is_gimple_reg (SSA_NAME_VAR (def)))
735 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
736 fprintf (vect_dump, "virtual phi. skip.");
740 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_unknown_def_type;
742 /* Analyze the evolution function. */
744 access_fn = analyze_scalar_evolution (loop, def);
749 if (vect_print_dump_info (REPORT_DETAILS,
750 LOOP_LOC (loop_vinfo)))
752 fprintf (vect_dump, "Access function of PHI: ");
753 print_generic_expr (vect_dump, access_fn, TDF_SLIM);
756 if (vect_is_simple_iv_evolution (loop->num, access_fn, &dummy, &dummy))
758 if (vect_print_dump_info (REPORT_DETAILS,LOOP_LOC (loop_vinfo)))
759 fprintf (vect_dump, "Detected induction.");
760 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def;
764 /* TODO: handle invariant phis */
766 reduc_stmt = vect_is_simple_reduction (loop, phi);
769 if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
770 fprintf (vect_dump, "Detected reduction.");
771 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_reduction_def;
772 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
776 if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
777 fprintf (vect_dump, "Unknown def-use cycle pattern.");
785 /* Function vect_base_addr_differ_p.
787 This is the simplest data dependence test: determines whether the
788 data references A and B access the same array/region. Returns
789 false when the property is not computable at compile time.
790 Otherwise return true, and DIFFER_P will record the result. This
791 utility will not be necessary when alias_sets_conflict_p will be
792 less conservative. */
795 vect_base_addr_differ_p (struct data_reference *dra,
796 struct data_reference *drb,
799 tree stmt_a = DR_STMT (dra);
800 stmt_vec_info stmt_info_a = vinfo_for_stmt (stmt_a);
801 tree stmt_b = DR_STMT (drb);
802 stmt_vec_info stmt_info_b = vinfo_for_stmt (stmt_b);
803 tree addr_a = STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info_a);
804 tree addr_b = STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info_b);
805 tree type_a = TREE_TYPE (addr_a);
806 tree type_b = TREE_TYPE (addr_b);
807 HOST_WIDE_INT alias_set_a, alias_set_b;
809 gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
811 /* Both references are ADDR_EXPR, i.e., we have the objects. */
812 if (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR)
813 return array_base_name_differ_p (dra, drb, differ_p);
815 alias_set_a = (TREE_CODE (addr_a) == ADDR_EXPR) ?
816 get_alias_set (TREE_OPERAND (addr_a, 0)) : get_alias_set (addr_a);
817 alias_set_b = (TREE_CODE (addr_b) == ADDR_EXPR) ?
818 get_alias_set (TREE_OPERAND (addr_b, 0)) : get_alias_set (addr_b);
820 if (!alias_sets_conflict_p (alias_set_a, alias_set_b))
826 /* An instruction writing through a restricted pointer is "independent" of any
827 instruction reading or writing through a different pointer, in the same
829 else if ((TYPE_RESTRICT (type_a) && !DR_IS_READ (dra))
830 || (TYPE_RESTRICT (type_b) && !DR_IS_READ (drb)))
839 /* Function vect_analyze_data_ref_dependence.
841 Return TRUE if there (might) exist a dependence between a memory-reference
842 DRA and a memory-reference DRB. */
845 vect_analyze_data_ref_dependence (struct data_reference *dra,
846 struct data_reference *drb,
847 loop_vec_info loop_vinfo)
850 struct data_dependence_relation *ddr;
851 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
852 int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
854 unsigned int loop_depth = 0;
855 struct loop *loop_nest = loop;
856 stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
857 stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
859 if (!vect_base_addr_differ_p (dra, drb, &differ_p))
861 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
862 LOOP_LOC (loop_vinfo)))
865 "not vectorized: can't determine dependence between: ");
866 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
867 fprintf (vect_dump, " and ");
868 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
876 ddr = initialize_data_dependence_relation (dra, drb);
877 compute_affine_dependence (ddr);
879 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
882 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
884 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
885 LOOP_LOC (loop_vinfo)))
888 "not vectorized: can't determine dependence between ");
889 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
890 fprintf (vect_dump, " and ");
891 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
896 /* Find loop depth. */
899 if (loop_nest->outer && loop_nest->outer->outer)
901 loop_nest = loop_nest->outer;
908 /* Compute distance vector. */
909 compute_subscript_distance (ddr);
910 build_classic_dist_vector (ddr, vect_loops_num, loop_nest->depth);
912 if (!DDR_DIST_VECT (ddr))
914 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
915 LOOP_LOC (loop_vinfo)))
917 fprintf (vect_dump, "not vectorized: bad dist vector for ");
918 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
919 fprintf (vect_dump, " and ");
920 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
925 dist = DDR_DIST_VECT (ddr)[loop_depth];
927 /* Same loop iteration. */
928 if (dist % vectorization_factor == 0)
930 /* Two references with distance zero have the same alignment. */
931 VEC_safe_push (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a), drb);
932 VEC_safe_push (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b), dra);
933 if (vect_print_dump_info (REPORT_ALIGNMENT, LOOP_LOC (loop_vinfo)))
934 fprintf (vect_dump, "accesses have the same alignment.");
938 if (dist >= vectorization_factor)
939 /* Dependence distance does not create dependence, as far as vectorization
940 is concerned, in this case. */
943 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
944 LOOP_LOC (loop_vinfo)))
947 "not vectorized: possible dependence between data-refs ");
948 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
949 fprintf (vect_dump, " and ");
950 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
957 /* Function vect_analyze_data_ref_dependences.
959 Examine all the data references in the loop, and make sure there do not
960 exist any data dependences between them. */
963 vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo)
966 varray_type loop_write_refs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
967 varray_type loop_read_refs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
969 /* Examine store-store (output) dependences. */
971 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
972 fprintf (vect_dump, "=== vect_analyze_dependences ===");
974 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
975 fprintf (vect_dump, "compare all store-store pairs.");
977 for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_refs); i++)
979 for (j = i + 1; j < VARRAY_ACTIVE_SIZE (loop_write_refs); j++)
981 struct data_reference *dra =
982 VARRAY_GENERIC_PTR (loop_write_refs, i);
983 struct data_reference *drb =
984 VARRAY_GENERIC_PTR (loop_write_refs, j);
985 if (vect_analyze_data_ref_dependence (dra, drb, loop_vinfo))
990 /* Examine load-store (true/anti) dependences. */
992 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
993 fprintf (vect_dump, "compare all load-store pairs.");
995 for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_refs); i++)
997 for (j = 0; j < VARRAY_ACTIVE_SIZE (loop_write_refs); j++)
999 struct data_reference *dra = VARRAY_GENERIC_PTR (loop_read_refs, i);
1000 struct data_reference *drb =
1001 VARRAY_GENERIC_PTR (loop_write_refs, j);
1002 if (vect_analyze_data_ref_dependence (dra, drb, loop_vinfo))
1011 /* Function vect_compute_data_ref_alignment
1013 Compute the misalignment of the data reference DR.
1016 1. If during the misalignment computation it is found that the data reference
1017 cannot be vectorized then false is returned.
1018 2. DR_MISALIGNMENT (DR) is defined.
1020 FOR NOW: No analysis is actually performed. Misalignment is calculated
1021 only for trivial cases. TODO. */
1024 vect_compute_data_ref_alignment (struct data_reference *dr)
1026 tree stmt = DR_STMT (dr);
1027 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1028 tree ref = DR_REF (dr);
1030 tree base, alignment;
1031 bool base_aligned_p;
1034 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1035 fprintf (vect_dump, "vect_compute_data_ref_alignment:");
1037 /* Initialize misalignment to unknown. */
1038 DR_MISALIGNMENT (dr) = -1;
1040 misalign = STMT_VINFO_VECT_MISALIGNMENT (stmt_info);
1041 base_aligned_p = STMT_VINFO_VECT_BASE_ALIGNED_P (stmt_info);
1042 base = build_fold_indirect_ref (STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info));
1043 vectype = STMT_VINFO_VECTYPE (stmt_info);
1047 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1049 fprintf (vect_dump, "Unknown alignment for access: ");
1050 print_generic_expr (vect_dump, base, TDF_SLIM);
1055 if (!base_aligned_p)
1057 if (!vect_can_force_dr_alignment_p (base, TYPE_ALIGN (vectype)))
1059 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1061 fprintf (vect_dump, "can't force alignment of ref: ");
1062 print_generic_expr (vect_dump, ref, TDF_SLIM);
1067 /* Force the alignment of the decl.
1068 NOTE: This is the only change to the code we make during
1069 the analysis phase, before deciding to vectorize the loop. */
1070 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1071 fprintf (vect_dump, "force alignment");
1072 DECL_ALIGN (base) = TYPE_ALIGN (vectype);
1073 DECL_USER_ALIGN (base) = 1;
1076 /* At this point we assume that the base is aligned. */
1077 gcc_assert (base_aligned_p
1078 || (TREE_CODE (base) == VAR_DECL
1079 && DECL_ALIGN (base) >= TYPE_ALIGN (vectype)));
1081 /* Alignment required, in bytes: */
1082 alignment = ssize_int (TYPE_ALIGN (vectype)/BITS_PER_UNIT);
1084 /* Modulo alignment. */
1085 misalign = size_binop (TRUNC_MOD_EXPR, misalign, alignment);
1086 if (tree_int_cst_sgn (misalign) < 0)
1088 /* Negative misalignment value. */
1089 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1090 fprintf (vect_dump, "unexpected misalign value");
1094 DR_MISALIGNMENT (dr) = tree_low_cst (misalign, 1);
1096 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1097 fprintf (vect_dump, "misalign = %d bytes", DR_MISALIGNMENT (dr));
1103 /* Function vect_compute_data_refs_alignment
1105 Compute the misalignment of data references in the loop.
1106 This pass may take place at function granularity instead of at loop
1109 FOR NOW: No analysis is actually performed. Misalignment is calculated
1110 only for trivial cases. TODO. */
1113 vect_compute_data_refs_alignment (loop_vec_info loop_vinfo)
1115 varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
1116 varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
1119 for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
1121 struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
1122 if (!vect_compute_data_ref_alignment (dr))
1126 for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
1128 struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
1129 if (!vect_compute_data_ref_alignment (dr))
1137 /* Function vect_enhance_data_refs_alignment
1139 This pass will use loop versioning and loop peeling in order to enhance
1140 the alignment of data references in the loop.
1142 FOR NOW: we assume that whatever versioning/peeling takes place, only the
1143 original loop is to be vectorized; Any other loops that are created by
1144 the transformations performed in this pass - are not supposed to be
1145 vectorized. This restriction will be relaxed. */
1148 vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo)
1150 varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
1151 varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
1152 varray_type datarefs;
1153 VEC(dr_p,heap) *same_align_drs;
1154 struct data_reference *dr0 = NULL;
1155 struct data_reference *dr;
1159 This pass will require a cost model to guide it whether to apply peeling
1160 or versioning or a combination of the two. For example, the scheme that
1161 intel uses when given a loop with several memory accesses, is as follows:
1162 choose one memory access ('p') which alignment you want to force by doing
1163 peeling. Then, either (1) generate a loop in which 'p' is aligned and all
1164 other accesses are not necessarily aligned, or (2) use loop versioning to
1165 generate one loop in which all accesses are aligned, and another loop in
1166 which only 'p' is necessarily aligned.
1168 ("Automatic Intra-Register Vectorization for the Intel Architecture",
1169 Aart J.C. Bik, Milind Girkar, Paul M. Grey and Ximmin Tian, International
1170 Journal of Parallel Programming, Vol. 30, No. 2, April 2002.)
1172 Devising a cost model is the most critical aspect of this work. It will
1173 guide us on which access to peel for, whether to use loop versioning, how
1174 many versions to create, etc. The cost model will probably consist of
1175 generic considerations as well as target specific considerations (on
1176 powerpc for example, misaligned stores are more painful than misaligned
1179 Here is the general steps involved in alignment enhancements:
1181 -- original loop, before alignment analysis:
1182 for (i=0; i<N; i++){
1183 x = q[i]; # DR_MISALIGNMENT(q) = unknown
1184 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1187 -- After vect_compute_data_refs_alignment:
1188 for (i=0; i<N; i++){
1189 x = q[i]; # DR_MISALIGNMENT(q) = 3
1190 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1193 -- Possibility 1: we do loop versioning:
1195 for (i=0; i<N; i++){ # loop 1A
1196 x = q[i]; # DR_MISALIGNMENT(q) = 3
1197 p[i] = y; # DR_MISALIGNMENT(p) = 0
1201 for (i=0; i<N; i++){ # loop 1B
1202 x = q[i]; # DR_MISALIGNMENT(q) = 3
1203 p[i] = y; # DR_MISALIGNMENT(p) = unaligned
1207 -- Possibility 2: we do loop peeling:
1208 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
1212 for (i = 3; i < N; i++){ # loop 2A
1213 x = q[i]; # DR_MISALIGNMENT(q) = 0
1214 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1217 -- Possibility 3: combination of loop peeling and versioning:
1218 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
1223 for (i = 3; i<N; i++){ # loop 3A
1224 x = q[i]; # DR_MISALIGNMENT(q) = 0
1225 p[i] = y; # DR_MISALIGNMENT(p) = 0
1229 for (i = 3; i<N; i++){ # loop 3B
1230 x = q[i]; # DR_MISALIGNMENT(q) = 0
1231 p[i] = y; # DR_MISALIGNMENT(p) = unaligned
1235 These loops are later passed to loop_transform to be vectorized. The
1236 vectorizer will use the alignment information to guide the transformation
1237 (whether to generate regular loads/stores, or with special handling for
1241 /* (1) Peeling to force alignment. */
1243 /* (1.1) Decide whether to perform peeling, and how many iterations to peel:
1245 + How many accesses will become aligned due to the peeling
1246 - How many accesses will become unaligned due to the peeling,
1247 and the cost of misaligned accesses.
1248 - The cost of peeling (the extra runtime checks, the increase
1251 The scheme we use FORNOW: peel to force the alignment of the first
1252 misaligned store in the loop.
1253 Rationale: misaligned stores are not yet supported.
1255 TODO: Use a better cost model. */
1257 for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
1259 dr0 = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
1260 if (!aligned_access_p (dr0))
1262 LOOP_VINFO_UNALIGNED_DR (loop_vinfo) = dr0;
1263 LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) = DR_MISALIGNMENT (dr0);
1268 /* (1.2) Update the alignment info according to the peeling factor.
1269 If the misalignment of the DR we peel for is M, then the
1270 peeling factor is VF - M, and the misalignment of each access DR_i
1271 in the loop is DR_MISALIGNMENT (DR_i) + VF - M.
1272 If the misalignment of the DR we peel for is unknown, then the
1273 misalignment of each access DR_i in the loop is also unknown.
1275 TODO: - consider accesses that are known to have the same
1276 alignment, even if that alignment is unknown. */
1278 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo))
1283 if (known_alignment_for_access_p (dr0))
1285 /* Since it's known at compile time, compute the number of iterations
1286 in the peeled loop (the peeling factor) for use in updating
1287 DR_MISALIGNMENT values. The peeling factor is the vectorization
1288 factor minus the misalignment as an element count. */
1289 mis = DR_MISALIGNMENT (dr0);
1290 mis /= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr0))));
1291 npeel = LOOP_VINFO_VECT_FACTOR (loop_vinfo) - mis;
1294 datarefs = loop_write_datarefs;
1295 for (j = 0; j < 2; j++)
1297 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
1299 struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
1303 if (known_alignment_for_access_p (dr)
1304 && DR_MISALIGNMENT (dr) == DR_MISALIGNMENT (dr0))
1305 DR_MISALIGNMENT (dr) = 0;
1306 else if (known_alignment_for_access_p (dr)
1307 && known_alignment_for_access_p (dr0))
1310 GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr))));
1312 DR_MISALIGNMENT (dr) += npeel * drsize;
1313 DR_MISALIGNMENT (dr) %= UNITS_PER_SIMD_WORD;
1316 DR_MISALIGNMENT (dr) = -1;
1318 datarefs = loop_read_datarefs;
1322 STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (DR_STMT (dr0)));
1323 for (i = 0; VEC_iterate (dr_p, same_align_drs, i, dr); i++)
1325 DR_MISALIGNMENT (dr) = 0;
1328 DR_MISALIGNMENT (dr0) = 0;
1333 /* Function vect_analyze_data_refs_alignment
1335 Analyze the alignment of the data-references in the loop.
1336 FOR NOW: Until support for misaligned accesses is in place, only if all
1337 accesses are aligned can the loop be vectorized. This restriction will be
1341 vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo)
1343 varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
1344 varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
1345 enum dr_alignment_support supportable_dr_alignment;
1348 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1349 fprintf (vect_dump, "=== vect_analyze_data_refs_alignment ===");
1352 /* This pass may take place at function granularity instead of at loop
1355 if (!vect_compute_data_refs_alignment (loop_vinfo))
1357 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1358 LOOP_LOC (loop_vinfo)))
1360 "not vectorized: can't calculate alignment for data ref.");
1365 /* This pass will decide on using loop versioning and/or loop peeling in
1366 order to enhance the alignment of data references in the loop. */
1368 vect_enhance_data_refs_alignment (loop_vinfo);
1371 /* Finally, check that all the data references in the loop can be
1372 handled with respect to their alignment. */
1374 for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
1376 struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
1377 supportable_dr_alignment = vect_supportable_dr_alignment (dr);
1378 if (!supportable_dr_alignment)
1380 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1381 LOOP_LOC (loop_vinfo)))
1382 fprintf (vect_dump, "not vectorized: unsupported unaligned load.");
1385 if (supportable_dr_alignment != dr_aligned
1386 && (vect_print_dump_info (REPORT_ALIGNMENT, LOOP_LOC (loop_vinfo))))
1387 fprintf (vect_dump, "Vectorizing an unaligned access.");
1389 for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
1391 struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
1392 supportable_dr_alignment = vect_supportable_dr_alignment (dr);
1393 if (!supportable_dr_alignment)
1395 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1396 LOOP_LOC (loop_vinfo)))
1397 fprintf (vect_dump, "not vectorized: unsupported unaligned store.");
1400 if (supportable_dr_alignment != dr_aligned
1401 && (vect_print_dump_info (REPORT_ALIGNMENT, LOOP_LOC (loop_vinfo))))
1402 fprintf (vect_dump, "Vectorizing an unaligned access.");
1404 if (LOOP_VINFO_UNALIGNED_DR (loop_vinfo)
1405 && vect_print_dump_info (REPORT_ALIGNMENT, LOOP_LOC (loop_vinfo)))
1406 fprintf (vect_dump, "Alignment of access forced using peeling.");
1412 /* Function vect_analyze_data_ref_access.
1414 Analyze the access pattern of the data-reference DR. For now, a data access
1415 has to consecutive to be considered vectorizable. */
1418 vect_analyze_data_ref_access (struct data_reference *dr)
1420 tree stmt = DR_STMT (dr);
1421 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1422 tree step = STMT_VINFO_VECT_STEP (stmt_info);
1423 tree scalar_type = TREE_TYPE (DR_REF (dr));
1425 if (!step || tree_int_cst_compare (step, TYPE_SIZE_UNIT (scalar_type)))
1427 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1428 fprintf (vect_dump, "not consecutive access");
1435 /* Function vect_analyze_data_ref_accesses.
1437 Analyze the access pattern of all the data references in the loop.
1439 FORNOW: the only access pattern that is considered vectorizable is a
1440 simple step 1 (consecutive) access.
1442 FORNOW: handle only arrays and pointer accesses. */
1445 vect_analyze_data_ref_accesses (loop_vec_info loop_vinfo)
1448 varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
1449 varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
1451 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1452 fprintf (vect_dump, "=== vect_analyze_data_ref_accesses ===");
1454 for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
1456 struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
1457 bool ok = vect_analyze_data_ref_access (dr);
1460 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1461 LOOP_LOC (loop_vinfo)))
1462 fprintf (vect_dump, "not vectorized: complicated access pattern.");
1467 for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
1469 struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
1470 bool ok = vect_analyze_data_ref_access (dr);
1473 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1474 LOOP_LOC (loop_vinfo)))
1475 fprintf (vect_dump, "not vectorized: complicated access pattern.");
1484 /* Function vect_analyze_pointer_ref_access.
1487 STMT - a stmt that contains a data-ref.
1488 MEMREF - a data-ref in STMT, which is an INDIRECT_REF.
1489 ACCESS_FN - the access function of MEMREF.
1492 If the data-ref access is vectorizable, return a data_reference structure
1493 that represents it (DR). Otherwise - return NULL.
1494 STEP - the stride of MEMREF in the loop.
1495 INIT - the initial condition of MEMREF in the loop.
1498 static struct data_reference *
1499 vect_analyze_pointer_ref_access (tree memref, tree stmt, bool is_read,
1500 tree access_fn, tree *ptr_init, tree *ptr_step)
1502 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1503 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1504 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1506 tree reftype, innertype;
1507 tree indx_access_fn;
1508 int loopnum = loop->num;
1509 struct data_reference *dr;
1511 if (!vect_is_simple_iv_evolution (loopnum, access_fn, &init, &step))
1513 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1514 LOOP_LOC (loop_vinfo)))
1515 fprintf (vect_dump, "not vectorized: pointer access is not simple.");
1521 if (!expr_invariant_in_loop_p (loop, init))
1523 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1524 LOOP_LOC (loop_vinfo)))
1526 "not vectorized: initial condition is not loop invariant.");
1530 if (TREE_CODE (step) != INTEGER_CST)
1532 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1533 LOOP_LOC (loop_vinfo)))
1535 "not vectorized: non constant step for pointer access.");
1539 reftype = TREE_TYPE (TREE_OPERAND (memref, 0));
1540 if (!POINTER_TYPE_P (reftype))
1542 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1543 LOOP_LOC (loop_vinfo)))
1544 fprintf (vect_dump, "not vectorized: unexpected pointer access form.");
1548 if (!POINTER_TYPE_P (TREE_TYPE (init)))
1550 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1551 LOOP_LOC (loop_vinfo)))
1552 fprintf (vect_dump, "not vectorized: unexpected pointer access form.");
1556 *ptr_step = fold_convert (ssizetype, step);
1557 innertype = TREE_TYPE (reftype);
1558 if (!COMPLETE_TYPE_P (innertype))
1560 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1561 LOOP_LOC (loop_vinfo)))
1562 fprintf (vect_dump, "not vectorized: pointer to incomplete type.");
1566 /* Check that STEP is a multiple of type size. */
1567 if (!integer_zerop (size_binop (TRUNC_MOD_EXPR, *ptr_step,
1568 fold_convert (ssizetype, TYPE_SIZE_UNIT (innertype)))))
1570 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1571 LOOP_LOC (loop_vinfo)))
1572 fprintf (vect_dump, "not vectorized: non consecutive access.");
1577 build_polynomial_chrec (loopnum, integer_zero_node, integer_one_node);
1578 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1580 fprintf (vect_dump, "Access function of ptr indx: ");
1581 print_generic_expr (vect_dump, indx_access_fn, TDF_SLIM);
1583 dr = init_data_ref (stmt, memref, NULL_TREE, indx_access_fn, is_read);
1589 /* Function vect_address_analysis
1591 Return the BASE of the address expression EXPR.
1592 Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1595 EXPR - the address expression that is being analyzed
1596 STMT - the statement that contains EXPR or its original memory reference
1597 IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
1598 VECTYPE - the type that defines the alignment (i.e, we compute
1599 alignment relative to TYPE_ALIGN(VECTYPE))
1600 DR - data_reference struct for the original memory reference
1603 BASE (returned value) - the base of the data reference EXPR.
1604 INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
1605 MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
1606 computation is impossible
1607 STEP - evolution of EXPR in the loop
1608 BASE_ALIGNED - indicates if BASE is aligned
1610 If something unexpected is encountered (an unsupported form of data-ref),
1611 then NULL_TREE is returned.
1615 vect_address_analysis (tree expr, tree stmt, bool is_read, tree vectype,
1616 struct data_reference *dr, tree *offset, tree *misalign,
1617 tree *step, bool *base_aligned)
1619 tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
1620 tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1622 struct ptr_info_def *dummy1;
1625 switch (TREE_CODE (expr))
1629 /* EXPR is of form {base +/- offset} (or {offset +/- base}). */
1630 oprnd0 = TREE_OPERAND (expr, 0);
1631 oprnd1 = TREE_OPERAND (expr, 1);
1633 STRIP_NOPS (oprnd0);
1634 STRIP_NOPS (oprnd1);
1636 /* Recursively try to find the base of the address contained in EXPR.
1637 For offset, the returned base will be NULL. */
1638 base_addr0 = vect_address_analysis (oprnd0, stmt, is_read, vectype, dr,
1639 &address_offset, &address_misalign, step,
1642 base_addr1 = vect_address_analysis (oprnd1, stmt, is_read, vectype, dr,
1643 &address_offset, &address_misalign, step,
1646 /* We support cases where only one of the operands contains an
1648 if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
1651 /* To revert STRIP_NOPS. */
1652 oprnd0 = TREE_OPERAND (expr, 0);
1653 oprnd1 = TREE_OPERAND (expr, 1);
1655 offset_expr = base_addr0 ?
1656 fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
1658 /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is
1659 a number, we can add it to the misalignment value calculated for base,
1660 otherwise, misalignment is NULL. */
1661 if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
1662 *misalign = size_binop (TREE_CODE (expr), address_misalign,
1665 *misalign = NULL_TREE;
1667 /* Combine offset (from EXPR {base + offset}) with the offset calculated
1669 *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
1670 return base_addr0 ? base_addr0 : base_addr1;
1673 base_address = vect_object_analysis (TREE_OPERAND (expr, 0), stmt,
1674 is_read, vectype, &dr, offset,
1675 misalign, step, base_aligned,
1676 &dummy, &dummy1, &dummy2);
1677 return base_address;
1680 if (!POINTER_TYPE_P (TREE_TYPE (expr)))
1683 if (TYPE_ALIGN (TREE_TYPE (TREE_TYPE (expr))) < TYPE_ALIGN (vectype))
1685 if (vect_get_ptr_offset (expr, vectype, misalign))
1686 *base_aligned = true;
1688 *base_aligned = false;
1692 *base_aligned = true;
1693 *misalign = ssize_int (0);
1695 *offset = ssize_int (0);
1696 *step = ssize_int (0);
1705 /* Function vect_object_analysis
1707 Return the BASE of the data reference MEMREF.
1708 Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1709 E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset
1710 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET
1711 instantiated with initial_conditions of access_functions of variables,
1712 modulo alignment, and STEP is the evolution of the DR_REF in this loop.
1714 Function get_inner_reference is used for the above in case of ARRAY_REF and
1717 The structure of the function is as follows:
1719 Case 1. For handled_component_p refs
1720 1.1 call get_inner_reference
1721 1.1.1 analyze offset expr received from get_inner_reference
1722 1.2. build data-reference structure for MEMREF
1723 (fall through with BASE)
1724 Case 2. For declarations
1726 2.2 update DR_BASE_NAME if necessary for alias
1727 Case 3. For INDIRECT_REFs
1728 3.1 get the access function
1729 3.2 analyze evolution of MEMREF
1730 3.3 set data-reference structure for MEMREF
1731 3.4 call vect_address_analysis to analyze INIT of the access function
1734 Combine the results of object and address analysis to calculate
1735 INITIAL_OFFSET, STEP and misalignment info.
1738 MEMREF - the memory reference that is being analyzed
1739 STMT - the statement that contains MEMREF
1740 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1741 VECTYPE - the type that defines the alignment (i.e, we compute
1742 alignment relative to TYPE_ALIGN(VECTYPE))
1745 BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
1746 E.g, if MEMREF is a.b[k].c[i][j] the returned
1748 DR - data_reference struct for MEMREF
1749 INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
1750 MISALIGN - offset of MEMREF from BASE in bytes (a constant) or NULL_TREE if
1751 the computation is impossible
1752 STEP - evolution of the DR_REF in the loop
1753 BASE_ALIGNED - indicates if BASE is aligned
1754 MEMTAG - memory tag for aliasing purposes
1755 PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
1756 SUBVAR - Sub-variables of the variable
1758 If something unexpected is encountered (an unsupported form of data-ref),
1759 then NULL_TREE is returned. */
1762 vect_object_analysis (tree memref, tree stmt, bool is_read,
1763 tree vectype, struct data_reference **dr,
1764 tree *offset, tree *misalign, tree *step,
1765 bool *base_aligned, tree *memtag,
1766 struct ptr_info_def **ptr_info, subvar_t *subvars)
1768 tree base = NULL_TREE, base_address = NULL_TREE;
1769 tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
1770 tree object_step = ssize_int (0), address_step = ssize_int (0);
1771 bool object_base_aligned = true, address_base_aligned = true;
1772 tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1773 HOST_WIDE_INT pbitsize, pbitpos;
1774 tree poffset, bit_pos_in_bytes;
1775 enum machine_mode pmode;
1776 int punsignedp, pvolatilep;
1777 tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
1778 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1779 loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1780 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1781 struct data_reference *ptr_dr = NULL;
1782 tree access_fn, evolution_part, address_to_analyze;
1787 /* Case 1. handled_component_p refs. */
1788 if (handled_component_p (memref))
1790 /* 1.1 call get_inner_reference. */
1791 /* Find the base and the offset from it. */
1792 base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
1793 &pmode, &punsignedp, &pvolatilep, false);
1797 /* 1.1.1 analyze offset expr received from get_inner_reference. */
1799 && !vect_analyze_offset_expr (poffset, loop, TYPE_SIZE_UNIT (vectype),
1800 &object_offset, &object_misalign, &object_step))
1802 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1804 fprintf (vect_dump, "failed to compute offset or step for ");
1805 print_generic_expr (vect_dump, memref, TDF_SLIM);
1810 /* Add bit position to OFFSET and MISALIGN. */
1812 bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
1813 /* Check that there is no remainder in bits. */
1814 if (pbitpos%BITS_PER_UNIT)
1816 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1817 fprintf (vect_dump, "bit offset alignment.");
1820 object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);
1821 if (object_misalign)
1822 object_misalign = size_binop (PLUS_EXPR, object_misalign,
1825 /* Create data-reference for MEMREF. TODO: handle COMPONENT_REFs. */
1828 if (TREE_CODE (memref) == ARRAY_REF)
1829 *dr = analyze_array (stmt, memref, is_read);
1834 memref = base; /* To continue analysis of BASE. */
1838 /* Part 1: Case 2. Declarations. */
1839 if (DECL_P (memref))
1841 /* We expect to get a decl only if we already have a DR. */
1844 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1846 fprintf (vect_dump, "unhandled decl ");
1847 print_generic_expr (vect_dump, memref, TDF_SLIM);
1852 /* 2.1 check the alignment. */
1853 if (DECL_ALIGN (memref) >= TYPE_ALIGN (vectype))
1854 object_base_aligned = true;
1856 object_base_aligned = false;
1858 /* 2.2 update DR_BASE_NAME if necessary. */
1859 if (!DR_BASE_NAME ((*dr)))
1860 /* For alias analysis. In case the analysis of INDIRECT_REF brought
1862 DR_BASE_NAME ((*dr)) = memref;
1864 if (SSA_VAR_P (memref) && var_can_have_subvars (memref))
1865 *subvars = get_subvars_for_var (memref);
1866 base_address = build_fold_addr_expr (memref);
1870 /* Part 1: Case 3. INDIRECT_REFs. */
1871 else if (TREE_CODE (memref) == INDIRECT_REF)
1873 tree ptr_ref = TREE_OPERAND (memref, 0);
1874 if (TREE_CODE (ptr_ref) == SSA_NAME)
1875 *ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
1877 /* 3.1 get the access function. */
1878 access_fn = analyze_scalar_evolution (loop, ptr_ref);
1881 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1882 LOOP_LOC (loop_vinfo)))
1883 fprintf (vect_dump, "not vectorized: complicated pointer access.");
1886 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1888 fprintf (vect_dump, "Access function of ptr: ");
1889 print_generic_expr (vect_dump, access_fn, TDF_SLIM);
1892 /* 3.2 analyze evolution of MEMREF. */
1893 evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
1896 ptr_dr = vect_analyze_pointer_ref_access (memref, stmt, is_read,
1897 access_fn, &ptr_init, &ptr_step);
1901 object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
1902 address_to_analyze = ptr_init;
1908 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1909 LOOP_LOC (loop_vinfo)))
1910 fprintf (vect_dump, "not vectorized: ptr is loop invariant.");
1913 /* Since there exists DR for MEMREF, we are analyzing the init of
1914 the access function, which not necessary has evolution in the
1916 address_to_analyze = initial_condition_in_loop_num (access_fn,
1920 /* 3.3 set data-reference structure for MEMREF. */
1921 *dr = (*dr) ? *dr : ptr_dr;
1923 /* 3.4 call vect_address_analysis to analyze INIT of the access
1925 base_address = vect_address_analysis (address_to_analyze, stmt, is_read,
1926 vectype, *dr, &address_offset, &address_misalign,
1927 &address_step, &address_base_aligned);
1931 switch (TREE_CODE (base_address))
1934 *memtag = get_var_ann (SSA_NAME_VAR (base_address))->type_mem_tag;
1935 if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
1936 *memtag = get_var_ann (
1937 SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->type_mem_tag;
1940 *memtag = TREE_OPERAND (base_address, 0);
1943 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
1944 LOOP_LOC (loop_vinfo)))
1946 fprintf (vect_dump, "not vectorized: no memtag ref: ");
1947 print_generic_expr (vect_dump, memref, TDF_SLIM);
1954 /* MEMREF cannot be analyzed. */
1957 if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag))
1958 *subvars = get_subvars_for_var (*memtag);
1960 /* Part 2: Combine the results of object and address analysis to calculate
1961 INITIAL_OFFSET, STEP and misalignment info. */
1962 *offset = size_binop (PLUS_EXPR, object_offset, address_offset);
1963 if (object_misalign && address_misalign)
1964 *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
1966 *misalign = NULL_TREE;
1967 *step = size_binop (PLUS_EXPR, object_step, address_step);
1968 *base_aligned = object_base_aligned && address_base_aligned;
1970 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1972 fprintf (vect_dump, "Results of object analysis for: ");
1973 print_generic_expr (vect_dump, memref, TDF_SLIM);
1974 fprintf (vect_dump, "\n\tbase_address: ");
1975 print_generic_expr (vect_dump, base_address, TDF_SLIM);
1976 fprintf (vect_dump, "\n\toffset: ");
1977 print_generic_expr (vect_dump, *offset, TDF_SLIM);
1978 fprintf (vect_dump, "\n\tstep: ");
1979 print_generic_expr (vect_dump, *step, TDF_SLIM);
1980 fprintf (vect_dump, "\n\tbase aligned %d\n\tmisalign: ", *base_aligned);
1981 print_generic_expr (vect_dump, *misalign, TDF_SLIM);
1983 return base_address;
1987 /* Function vect_analyze_data_refs.
1989 Find all the data references in the loop.
1991 The general structure of the analysis of data refs in the vectorizer is as
1993 1- vect_analyze_data_refs(loop):
1994 Find and analyze all data-refs in the loop:
1996 base_address = vect_object_analysis(ref)
1997 1.1- vect_object_analysis(ref):
1998 Analyze ref, and build a DR (data_reference struct) for it;
1999 compute base, initial_offset, step and alignment.
2000 Call get_inner_reference for refs handled in this function.
2001 Call vect_addr_analysis(addr) to analyze pointer type expressions.
2002 Set ref_stmt.base, ref_stmt.initial_offset, ref_stmt.alignment,
2003 ref_stmt.memtag, ref_stmt.ptr_info and ref_stmt.step accordingly.
2004 2- vect_analyze_dependences(): apply dependence testing using ref_stmt.DR
2005 3- vect_analyze_drs_alignment(): check that ref_stmt.alignment is ok.
2006 4- vect_analyze_drs_access(): check that ref_stmt.step is ok.
2008 FORNOW: Handle aligned INDIRECT_REFs and ARRAY_REFs
2009 which base is really an array (not a pointer) and which alignment
2010 can be forced. This restriction will be relaxed. */
2013 vect_analyze_data_refs (loop_vec_info loop_vinfo)
2015 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2016 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
2017 int nbbs = loop->num_nodes;
2018 block_stmt_iterator si;
2020 struct data_reference *dr;
2022 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2023 fprintf (vect_dump, "=== vect_analyze_data_refs ===");
2025 for (j = 0; j < nbbs; j++)
2027 basic_block bb = bbs[j];
2028 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2030 bool is_read = false;
2031 tree stmt = bsi_stmt (si);
2032 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2033 varray_type *datarefs = NULL;
2035 tree scalar_type, vectype;
2036 tree base, offset, misalign, step, tag;
2037 struct ptr_info_def *ptr_info;
2039 subvar_t subvars = NULL;
2040 bool no_vuse, no_vmaymust;
2042 /* Assumption: there exists a data-ref in stmt, if and only if
2043 it has vuses/vdefs. */
2045 no_vuse = ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE);
2046 no_vmaymust = ZERO_SSA_OPERANDS (stmt,
2047 SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF);
2048 if (no_vuse && no_vmaymust)
2051 if (!no_vuse && !no_vmaymust)
2053 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2055 fprintf (vect_dump, "unexpected vdefs and vuses in stmt: ");
2056 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2061 if (TREE_CODE (stmt) != MODIFY_EXPR)
2063 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2065 fprintf (vect_dump, "unexpected vops in stmt: ");
2066 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2073 memref = TREE_OPERAND (stmt, 1);
2074 datarefs = &(LOOP_VINFO_DATAREF_READS (loop_vinfo));
2079 memref = TREE_OPERAND (stmt, 0);
2080 datarefs = &(LOOP_VINFO_DATAREF_WRITES (loop_vinfo));
2084 scalar_type = TREE_TYPE (memref);
2085 vectype = get_vectype_for_scalar_type (scalar_type);
2088 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2090 fprintf (vect_dump, "no vectype for stmt: ");
2091 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2092 fprintf (vect_dump, " scalar_type: ");
2093 print_generic_expr (vect_dump, scalar_type, TDF_DETAILS);
2095 /* It is not possible to vectorize this data reference. */
2098 /* Analyze MEMREF. If it is of a supported form, build data_reference
2099 struct for it (DR). */
2101 base = vect_object_analysis (memref, stmt, is_read, vectype, &dr,
2102 &offset, &misalign, &step,
2103 &base_aligned, &tag, &ptr_info,
2107 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
2108 LOOP_LOC (loop_vinfo)))
2110 fprintf (vect_dump, "not vectorized: unhandled data ref: ");
2111 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2115 STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info) = base;
2116 STMT_VINFO_VECT_INIT_OFFSET (stmt_info) = offset;
2117 STMT_VINFO_VECT_STEP (stmt_info) = step;
2118 STMT_VINFO_VECT_MISALIGNMENT (stmt_info) = misalign;
2119 STMT_VINFO_VECT_BASE_ALIGNED_P (stmt_info) = base_aligned;
2120 STMT_VINFO_MEMTAG (stmt_info) = tag;
2121 STMT_VINFO_PTR_INFO (stmt_info) = ptr_info;
2122 STMT_VINFO_SUBVARS (stmt_info) = subvars;
2123 STMT_VINFO_VECTYPE (stmt_info) = vectype;
2124 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
2125 STMT_VINFO_DATA_REF (stmt_info) = dr;
2133 /* Utility functions used by vect_mark_stmts_to_be_vectorized. */
2135 /* Function vect_mark_relevant.
2137 Mark STMT as "relevant for vectorization" and add it to WORKLIST. */
2140 vect_mark_relevant (VEC(tree,heap) **worklist, tree stmt,
2141 bool relevant_p, bool live_p)
2143 stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2144 bool save_relevant_p = STMT_VINFO_RELEVANT_P (stmt_info);
2145 bool save_live_p = STMT_VINFO_LIVE_P (stmt_info);
2147 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2148 fprintf (vect_dump, "mark relevant %d, live %d.",relevant_p, live_p);
2150 STMT_VINFO_LIVE_P (stmt_info) |= live_p;
2152 if (TREE_CODE (stmt) == PHI_NODE)
2153 /* Don't mark as relevant because it's not going to vectorized. */
2156 STMT_VINFO_RELEVANT_P (stmt_info) |= relevant_p;
2158 if (STMT_VINFO_RELEVANT_P (stmt_info) == save_relevant_p
2159 && STMT_VINFO_LIVE_P (stmt_info) == save_live_p)
2161 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2162 fprintf (vect_dump, "already marked relevant/live.");
2166 VEC_safe_push (tree, heap, *worklist, stmt);
2170 /* Function vect_stmt_relevant_p.
2172 Return true if STMT in loop that is represented by LOOP_VINFO is
2173 "relevant for vectorization".
2175 A stmt is considered "relevant for vectorization" if:
2176 - it has uses outside the loop.
2177 - it has vdefs (it alters memory).
2178 - control stmts in the loop (except for the exit condition).
2180 CHECKME: what other side effects would the vectorizer allow? */
2183 vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo,
2184 bool *relevant_p, bool *live_p)
2186 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2187 ssa_op_iter op_iter;
2188 imm_use_iterator imm_iter;
2189 use_operand_p use_p;
2190 def_operand_p def_p;
2192 *relevant_p = false;
2195 /* cond stmt other than loop exit cond. */
2196 if (is_ctrl_stmt (stmt) && (stmt != LOOP_VINFO_EXIT_COND (loop_vinfo)))
2199 /* changing memory. */
2200 if (TREE_CODE (stmt) != PHI_NODE)
2201 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
2203 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2204 fprintf (vect_dump, "vec_stmt_relevant_p: stmt has vdefs.");
2208 /* uses outside the loop. */
2209 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_DEF)
2211 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
2213 basic_block bb = bb_for_stmt (USE_STMT (use_p));
2214 if (!flow_bb_inside_loop_p (loop, bb))
2216 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2217 fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop.");
2219 /* We expect all such uses to be in the loop exit phis
2220 (because of loop closed form) */
2221 gcc_assert (TREE_CODE (USE_STMT (use_p)) == PHI_NODE);
2222 gcc_assert (bb == loop->single_exit->dest);
2229 return (*live_p || *relevant_p);
2233 /* Function vect_mark_stmts_to_be_vectorized.
2235 Not all stmts in the loop need to be vectorized. For example:
2244 Stmt 1 and 3 do not need to be vectorized, because loop control and
2245 addressing of vectorized data-refs are handled differently.
2247 This pass detects such stmts. */
2250 vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo)
2252 VEC(tree,heap) *worklist;
2253 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2254 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
2255 unsigned int nbbs = loop->num_nodes;
2256 block_stmt_iterator si;
2261 stmt_vec_info stmt_vinfo;
2264 bool relevant_p, live_p;
2266 enum vect_def_type dt;
2268 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2269 fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ===");
2271 worklist = VEC_alloc (tree, heap, 64);
2273 /* 1. Init worklist. */
2276 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2278 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2280 fprintf (vect_dump, "init: phi relevant? ");
2281 print_generic_expr (vect_dump, phi, TDF_SLIM);
2284 if (vect_stmt_relevant_p (phi, loop_vinfo, &relevant_p, &live_p))
2285 vect_mark_relevant (&worklist, phi, relevant_p, live_p);
2288 for (i = 0; i < nbbs; i++)
2291 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2293 stmt = bsi_stmt (si);
2295 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2297 fprintf (vect_dump, "init: stmt relevant? ");
2298 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2301 if (vect_stmt_relevant_p (stmt, loop_vinfo, &relevant_p, &live_p))
2302 vect_mark_relevant (&worklist, stmt, relevant_p, live_p);
2307 /* 2. Process_worklist */
2309 while (VEC_length (tree, worklist) > 0)
2311 stmt = VEC_pop (tree, worklist);
2313 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2315 fprintf (vect_dump, "worklist: examine stmt: ");
2316 print_generic_expr (vect_dump, stmt, TDF_SLIM);
2319 /* Examine the USEs of STMT. For each ssa-name USE thta is defined
2320 in the loop, mark the stmt that defines it (DEF_STMT) as
2321 relevant/irrelevant and live/dead according to the liveness and
2322 relevance properties of STMT.
2325 gcc_assert (TREE_CODE (stmt) != PHI_NODE);
2327 ann = stmt_ann (stmt);
2328 stmt_vinfo = vinfo_for_stmt (stmt);
2330 relevant_p = STMT_VINFO_RELEVANT_P (stmt_vinfo);
2331 live_p = STMT_VINFO_LIVE_P (stmt_vinfo);
2333 /* Generally, the liveness and relevance properties of STMT are
2334 propagated to the DEF_STMTs of its USEs:
2335 STMT_VINFO_LIVE_P (DEF_STMT_info) <-- live_p
2336 STMT_VINFO_RELEVANT_P (DEF_STMT_info) <-- relevant_p
2340 - if USE is used only for address computations (e.g. array indexing),
2341 which does not need to be directly vectorized, then the
2342 liveness/relevance of the respective DEF_STMT is left unchanged.
2344 - if STMT has been identified as defining a reduction variable, then:
2345 STMT_VINFO_LIVE_P (DEF_STMT_info) <-- false
2346 STMT_VINFO_RELEVANT_P (DEF_STMT_info) <-- true
2347 because even though STMT is classified as live (since it defines a
2348 value that is used across loop iterations) and irrelevant (since it
2349 is not used inside the loop), it will be vectorized, and therefore
2350 the corresponding DEF_STMTs need to marked as relevant.
2353 if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def)
2355 gcc_assert (!relevant_p && live_p);
2360 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
2362 /* We are only interested in uses that need to be vectorized. Uses
2363 that are used for address computation are not considered relevant.
2365 if (exist_non_indexing_operands_for_use_p (use, stmt))
2367 if (!vect_is_simple_use (use, loop_vinfo, &def_stmt, &def, &dt))
2369 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
2370 LOOP_LOC (loop_vinfo)))
2372 "not vectorized: unsupported use in stmt.");
2373 VEC_free (tree, heap, worklist);
2377 if (!def_stmt || IS_EMPTY_STMT (def_stmt))
2380 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2382 fprintf (vect_dump, "worklist: examine use %d: ", i);
2383 print_generic_expr (vect_dump, use, TDF_SLIM);
2386 bb = bb_for_stmt (def_stmt);
2387 if (!flow_bb_inside_loop_p (loop, bb))
2390 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2392 fprintf (vect_dump, "def_stmt: ");
2393 print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
2396 vect_mark_relevant (&worklist, def_stmt, relevant_p, live_p);
2399 } /* while worklist */
2401 VEC_free (tree, heap, worklist);
2406 /* Function vect_can_advance_ivs_p
2408 In case the number of iterations that LOOP iterates in unknown at compile
2409 time, an epilog loop will be generated, and the loop induction variables
2410 (IVs) will be "advanced" to the value they are supposed to take just before
2411 the epilog loop. Here we check that the access function of the loop IVs
2412 and the expression that represents the loop bound are simple enough.
2413 These restrictions will be relaxed in the future. */
2416 vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
2418 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2419 basic_block bb = loop->header;
2422 /* Analyze phi functions of the loop header. */
2424 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2425 fprintf (vect_dump, "=== vect_can_advance_ivs_p ===");
2427 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2429 tree access_fn = NULL;
2430 tree evolution_part;
2432 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2434 fprintf (vect_dump, "Analyze phi: ");
2435 print_generic_expr (vect_dump, phi, TDF_SLIM);
2438 /* Skip virtual phi's. The data dependences that are associated with
2439 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
2441 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
2443 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2444 fprintf (vect_dump, "virtual phi. skip.");
2448 /* Analyze the evolution function. */
2450 access_fn = instantiate_parameters
2451 (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2455 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2456 fprintf (vect_dump, "No Access function.");
2460 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2462 fprintf (vect_dump, "Access function of PHI: ");
2463 print_generic_expr (vect_dump, access_fn, TDF_SLIM);
2466 evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
2468 if (evolution_part == NULL_TREE)
2470 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2471 fprintf (vect_dump, "No evolution.");
2475 /* FORNOW: We do not transform initial conditions of IVs
2476 which evolution functions are a polynomial of degree >= 2. */
2478 if (tree_is_chrec (evolution_part))
2486 /* Function vect_get_loop_niters.
2488 Determine how many iterations the loop is executed.
2489 If an expression that represents the number of iterations
2490 can be constructed, place it in NUMBER_OF_ITERATIONS.
2491 Return the loop exit condition. */
2494 vect_get_loop_niters (struct loop *loop, tree *number_of_iterations)
2498 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2499 fprintf (vect_dump, "=== get_loop_niters ===");
2501 niters = number_of_iterations_in_loop (loop);
2503 if (niters != NULL_TREE
2504 && niters != chrec_dont_know)
2506 *number_of_iterations = niters;
2508 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2510 fprintf (vect_dump, "==> get_loop_niters:" );
2511 print_generic_expr (vect_dump, *number_of_iterations, TDF_SLIM);
2515 return get_loop_exit_condition (loop);
2519 /* Function vect_analyze_loop_form.
2521 Verify the following restrictions (some may be relaxed in the future):
2522 - it's an inner-most loop
2523 - number of BBs = 2 (which are the loop header and the latch)
2524 - the loop has a pre-header
2525 - the loop has a single entry and exit
2526 - the loop exit condition is simple enough, and the number of iterations
2527 can be analyzed (a countable loop). */
2529 static loop_vec_info
2530 vect_analyze_loop_form (struct loop *loop)
2532 loop_vec_info loop_vinfo;
2534 tree number_of_iterations = NULL;
2537 loop_loc = find_loop_location (loop);
2539 if (vect_print_dump_info (REPORT_DETAILS, loop_loc))
2540 fprintf (vect_dump, "=== vect_analyze_loop_form ===");
2544 if (vect_print_dump_info (REPORT_OUTER_LOOPS, loop_loc))
2545 fprintf (vect_dump, "not vectorized: nested loop.");
2549 if (!loop->single_exit
2550 || loop->num_nodes != 2
2551 || EDGE_COUNT (loop->header->preds) != 2)
2553 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
2555 if (!loop->single_exit)
2556 fprintf (vect_dump, "not vectorized: multiple exits.");
2557 else if (loop->num_nodes != 2)
2558 fprintf (vect_dump, "not vectorized: too many BBs in loop.");
2559 else if (EDGE_COUNT (loop->header->preds) != 2)
2560 fprintf (vect_dump, "not vectorized: too many incoming edges.");
2566 /* We assume that the loop exit condition is at the end of the loop. i.e,
2567 that the loop is represented as a do-while (with a proper if-guard
2568 before the loop if needed), where the loop header contains all the
2569 executable statements, and the latch is empty. */
2570 if (!empty_block_p (loop->latch))
2572 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
2573 fprintf (vect_dump, "not vectorized: unexpected loop form.");
2577 /* Make sure there exists a single-predecessor exit bb: */
2578 if (!single_pred_p (loop->single_exit->dest))
2580 edge e = loop->single_exit;
2581 if (!(e->flags & EDGE_ABNORMAL))
2583 split_loop_exit_edge (e);
2584 if (vect_print_dump_info (REPORT_DETAILS, loop_loc))
2585 fprintf (vect_dump, "split exit edge.");
2589 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
2590 fprintf (vect_dump, "not vectorized: abnormal loop exit edge.");
2595 if (empty_block_p (loop->header))
2597 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
2598 fprintf (vect_dump, "not vectorized: empty loop.");
2602 loop_cond = vect_get_loop_niters (loop, &number_of_iterations);
2605 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
2606 fprintf (vect_dump, "not vectorized: complicated exit condition.");
2610 if (!number_of_iterations)
2612 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
2614 "not vectorized: number of iterations cannot be computed.");
2618 if (chrec_contains_undetermined (number_of_iterations))
2620 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
2621 fprintf (vect_dump, "Infinite number of iterations.");
2625 loop_vinfo = new_loop_vec_info (loop);
2626 LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
2628 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
2630 if (vect_print_dump_info (REPORT_DETAILS, loop_loc))
2632 fprintf (vect_dump, "Symbolic number of iterations is ");
2633 print_generic_expr (vect_dump, number_of_iterations, TDF_DETAILS);
2637 if (LOOP_VINFO_INT_NITERS (loop_vinfo) == 0)
2639 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS, loop_loc))
2640 fprintf (vect_dump, "not vectorized: number of iterations = 0.");
2644 LOOP_VINFO_EXIT_COND (loop_vinfo) = loop_cond;
2645 LOOP_VINFO_LOC (loop_vinfo) = loop_loc;
2651 /* Function vect_analyze_loop.
2653 Apply a set of analyses on LOOP, and create a loop_vec_info struct
2654 for it. The different analyses will record information in the
2655 loop_vec_info struct. */
2657 vect_analyze_loop (struct loop *loop)
2660 loop_vec_info loop_vinfo;
2662 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2663 fprintf (vect_dump, "===== analyze_loop_nest =====");
2665 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
2667 loop_vinfo = vect_analyze_loop_form (loop);
2670 if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2671 fprintf (vect_dump, "bad loop form.");
2675 /* Find all data references in the loop (which correspond to vdefs/vuses)
2676 and analyze their evolution in the loop.
2678 FORNOW: Handle only simple, array references, which
2679 alignment can be forced, and aligned pointer-references. */
2681 ok = vect_analyze_data_refs (loop_vinfo);
2684 if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
2685 fprintf (vect_dump, "bad data references.");
2686 destroy_loop_vec_info (loop_vinfo);
2690 /* Classify all cross-iteration scalar data-flow cycles.
2691 Cross-iteration cycles caused by virtual phis are analyzed separately. */
2693 vect_analyze_scalar_cycles (loop_vinfo);
2695 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
2697 ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
2700 if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
2701 fprintf (vect_dump, "unexpected pattern.");
2702 destroy_loop_vec_info (loop_vinfo);
2706 ok = vect_determine_vectorization_factor (loop_vinfo);
2709 if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
2710 fprintf (vect_dump, "can't determine vectorization factor.");
2711 destroy_loop_vec_info (loop_vinfo);
2715 /* Analyze data dependences between the data-refs in the loop.
2716 FORNOW: fail at the first data dependence that we encounter. */
2718 ok = vect_analyze_data_ref_dependences (loop_vinfo);
2721 if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
2722 fprintf (vect_dump, "bad data dependence.");
2723 destroy_loop_vec_info (loop_vinfo);
2727 /* Analyze the access patterns of the data-refs in the loop (consecutive,
2728 complex, etc.). FORNOW: Only handle consecutive access pattern. */
2730 ok = vect_analyze_data_ref_accesses (loop_vinfo);
2733 if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
2734 fprintf (vect_dump, "bad data access.");
2735 destroy_loop_vec_info (loop_vinfo);
2739 /* Analyze the alignment of the data-refs in the loop.
2740 FORNOW: Only aligned accesses are handled. */
2742 ok = vect_analyze_data_refs_alignment (loop_vinfo);
2745 if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
2746 fprintf (vect_dump, "bad data alignment.");
2747 destroy_loop_vec_info (loop_vinfo);
2751 /* Scan all the operations in the loop and make sure they are
2754 ok = vect_analyze_operations (loop_vinfo);
2757 if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
2758 fprintf (vect_dump, "bad operation or unsupported loop bound.");
2759 destroy_loop_vec_info (loop_vinfo);
2763 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1;