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"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #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"
42 /* Main analysis functions. */
43 static loop_vec_info
vect_analyze_loop_form (struct loop
*);
44 static bool vect_analyze_data_refs (loop_vec_info
);
45 static bool vect_mark_stmts_to_be_vectorized (loop_vec_info
);
46 static bool vect_analyze_scalar_cycles (loop_vec_info
);
47 static bool vect_analyze_data_ref_accesses (loop_vec_info
);
48 static bool vect_analyze_data_ref_dependences (loop_vec_info
);
49 static bool vect_analyze_data_refs_alignment (loop_vec_info
);
50 static bool vect_compute_data_refs_alignment (loop_vec_info
);
51 static void vect_enhance_data_refs_alignment (loop_vec_info
);
52 static bool vect_analyze_operations (loop_vec_info
);
54 /* Utility functions for the analyses. */
55 static bool exist_non_indexing_operands_for_use_p (tree
, tree
);
56 static void vect_mark_relevant (varray_type
*, tree
);
57 static bool vect_stmt_relevant_p (tree
, loop_vec_info
);
58 static tree
vect_get_loop_niters (struct loop
*, tree
*);
59 static bool vect_analyze_data_ref_dependence
60 (struct data_reference
*, struct data_reference
*, loop_vec_info
);
61 static bool vect_compute_data_ref_alignment (struct data_reference
*);
62 static bool vect_analyze_data_ref_access (struct data_reference
*);
63 static struct data_reference
* vect_analyze_pointer_ref_access
64 (tree
, tree
, bool, tree
, tree
*, tree
*);
65 static bool vect_can_advance_ivs_p (loop_vec_info
);
66 static tree
vect_get_ptr_offset (tree
, tree
, tree
*);
67 static bool vect_analyze_offset_expr (tree
, struct loop
*, tree
, tree
*,
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
*, subvar_t
*);
74 static tree
vect_address_analysis (tree
, tree
, bool, tree
,
75 struct data_reference
*, tree
*, tree
*,
79 /* Function vect_get_ptr_offset
81 Compute the OFFSET modulo vector-type alignment of pointer REF in bits. */
84 vect_get_ptr_offset (tree ref ATTRIBUTE_UNUSED
,
85 tree vectype ATTRIBUTE_UNUSED
,
86 tree
*offset ATTRIBUTE_UNUSED
)
88 /* TODO: Use alignment information. */
93 /* Function vect_analyze_offset_expr
95 Given an offset expression EXPR received from get_inner_reference, analyze
96 it and create an expression for INITIAL_OFFSET by substituting the variables
97 of EXPR with initial_condition of the corresponding access_fn in the loop.
100 for (j = 3; j < N; j++)
103 For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be
104 substituted, since its access_fn in the inner loop is i. 'j' will be
105 substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
108 Compute MISALIGN (the misalignment of the data reference initial access from
109 its base) if possible. Misalignment can be calculated only if all the
110 variables can be substituted with constants, or if a variable is multiplied
111 by a multiple of VECTYPE_ALIGNMENT. In the above example, since 'i' cannot
112 be substituted, MISALIGN will be NULL_TREE in case that C_i is not a multiple
113 of VECTYPE_ALIGNMENT, and C` otherwise. (We perform MISALIGN modulo
114 VECTYPE_ALIGNMENT computation in the caller of this function).
116 STEP is an evolution of the data reference in this loop in bytes.
117 In the above example, STEP is C_j.
119 Return FALSE, if the analysis fails, e.g., there is no access_fn for a
120 variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN and STEP)
121 are NULL_TREEs. Otherwise, return TRUE.
126 vect_analyze_offset_expr (tree expr
,
128 tree vectype_alignment
,
129 tree
*initial_offset
,
135 tree left_offset
= ssize_int (0);
136 tree right_offset
= ssize_int (0);
137 tree left_misalign
= ssize_int (0);
138 tree right_misalign
= ssize_int (0);
139 tree left_step
= ssize_int (0);
140 tree right_step
= ssize_int (0);
142 tree init
, evolution
;
145 *misalign
= NULL_TREE
;
146 *initial_offset
= NULL_TREE
;
148 /* Strip conversions that don't narrow the mode. */
149 expr
= vect_strip_conversion (expr
);
155 if (TREE_CODE (expr
) == INTEGER_CST
)
157 *initial_offset
= fold_convert (ssizetype
, expr
);
158 *misalign
= fold_convert (ssizetype
, expr
);
159 *step
= ssize_int (0);
163 /* 2. Variable. Try to substitute with initial_condition of the corresponding
164 access_fn in the current loop. */
165 if (SSA_VAR_P (expr
))
167 tree access_fn
= analyze_scalar_evolution (loop
, expr
);
169 if (access_fn
== chrec_dont_know
)
173 init
= initial_condition_in_loop_num (access_fn
, loop
->num
);
174 if (init
== expr
&& !expr_invariant_in_loop_p (loop
, init
))
175 /* Not enough information: may be not loop invariant.
176 E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
177 initial_condition is D, but it depends on i - loop's induction
181 evolution
= evolution_part_in_loop_num (access_fn
, loop
->num
);
182 if (evolution
&& TREE_CODE (evolution
) != INTEGER_CST
)
183 /* Evolution is not constant. */
186 if (TREE_CODE (init
) == INTEGER_CST
)
187 *misalign
= fold_convert (ssizetype
, init
);
189 /* Not constant, misalignment cannot be calculated. */
190 *misalign
= NULL_TREE
;
192 *initial_offset
= fold_convert (ssizetype
, init
);
194 *step
= evolution
? fold_convert (ssizetype
, evolution
) : ssize_int (0);
198 /* Recursive computation. */
199 if (!BINARY_CLASS_P (expr
))
201 /* We expect to get binary expressions (PLUS/MINUS and MULT). */
202 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
204 fprintf (vect_dump
, "Not binary expression ");
205 print_generic_expr (vect_dump
, expr
, TDF_SLIM
);
209 oprnd0
= TREE_OPERAND (expr
, 0);
210 oprnd1
= TREE_OPERAND (expr
, 1);
212 if (!vect_analyze_offset_expr (oprnd0
, loop
, vectype_alignment
, &left_offset
,
213 &left_misalign
, &left_step
)
214 || !vect_analyze_offset_expr (oprnd1
, loop
, vectype_alignment
,
215 &right_offset
, &right_misalign
, &right_step
))
218 /* The type of the operation: plus, minus or mult. */
219 code
= TREE_CODE (expr
);
223 if (TREE_CODE (right_offset
) != INTEGER_CST
)
224 /* RIGHT_OFFSET can be not constant. For example, for arrays of variable
226 FORNOW: We don't support such cases. */
229 /* Strip conversions that don't narrow the mode. */
230 left_offset
= vect_strip_conversion (left_offset
);
233 /* Misalignment computation. */
234 if (SSA_VAR_P (left_offset
))
236 /* If the left side contains variables that can't be substituted with
237 constants, we check if the right side is a multiple of ALIGNMENT.
239 if (integer_zerop (size_binop (TRUNC_MOD_EXPR
, right_offset
,
240 fold_convert (ssizetype
, vectype_alignment
))))
241 *misalign
= ssize_int (0);
243 /* If the remainder is not zero or the right side isn't constant,
244 we can't compute misalignment. */
245 *misalign
= NULL_TREE
;
249 /* The left operand was successfully substituted with constant. */
251 /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is
253 *misalign
= size_binop (code
, left_misalign
, right_misalign
);
255 *misalign
= NULL_TREE
;
258 /* Step calculation. */
259 /* Multiply the step by the right operand. */
260 *step
= size_binop (MULT_EXPR
, left_step
, right_offset
);
265 /* Combine the recursive calculations for step and misalignment. */
266 *step
= size_binop (code
, left_step
, right_step
);
268 if (left_misalign
&& right_misalign
)
269 *misalign
= size_binop (code
, left_misalign
, right_misalign
);
271 *misalign
= NULL_TREE
;
279 /* Compute offset. */
280 *initial_offset
= fold_convert (ssizetype
,
281 fold (build2 (code
, TREE_TYPE (left_offset
),
288 /* Function vect_analyze_operations.
290 Scan the loop stmts and make sure they are all vectorizable. */
293 vect_analyze_operations (loop_vec_info loop_vinfo
)
295 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
296 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
297 int nbbs
= loop
->num_nodes
;
298 block_stmt_iterator si
;
299 unsigned int vectorization_factor
= 0;
304 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
305 fprintf (vect_dump
, "=== vect_analyze_operations ===");
307 for (i
= 0; i
< nbbs
; i
++)
309 basic_block bb
= bbs
[i
];
311 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
313 tree stmt
= bsi_stmt (si
);
315 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
318 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
320 fprintf (vect_dump
, "==> examining statement: ");
321 print_generic_expr (vect_dump
, stmt
, TDF_SLIM
);
324 gcc_assert (stmt_info
);
326 /* skip stmts which do not need to be vectorized.
327 this is expected to include:
328 - the COND_EXPR which is the loop exit condition
329 - any LABEL_EXPRs in the loop
330 - computations that are used only for array indexing or loop
333 if (!STMT_VINFO_RELEVANT_P (stmt_info
))
335 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
336 fprintf (vect_dump
, "irrelevant.");
340 if (VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt
))))
342 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
343 LOOP_LOC (loop_vinfo
)))
345 fprintf (vect_dump
, "not vectorized: vector stmt in loop:");
346 print_generic_expr (vect_dump
, stmt
, TDF_SLIM
);
351 if (STMT_VINFO_DATA_REF (stmt_info
))
352 scalar_type
= TREE_TYPE (DR_REF (STMT_VINFO_DATA_REF (stmt_info
)));
353 else if (TREE_CODE (stmt
) == MODIFY_EXPR
)
354 scalar_type
= TREE_TYPE (TREE_OPERAND (stmt
, 0));
356 scalar_type
= TREE_TYPE (stmt
);
358 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
360 fprintf (vect_dump
, "get vectype for scalar type: ");
361 print_generic_expr (vect_dump
, scalar_type
, TDF_SLIM
);
364 vectype
= get_vectype_for_scalar_type (scalar_type
);
367 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
368 LOOP_LOC (loop_vinfo
)))
371 "not vectorized: unsupported data-type ");
372 print_generic_expr (vect_dump
, scalar_type
, TDF_SLIM
);
377 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
379 fprintf (vect_dump
, "vectype: ");
380 print_generic_expr (vect_dump
, vectype
, TDF_SLIM
);
382 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
384 ok
= (vectorizable_operation (stmt
, NULL
, NULL
)
385 || vectorizable_assignment (stmt
, NULL
, NULL
)
386 || vectorizable_load (stmt
, NULL
, NULL
)
387 || vectorizable_store (stmt
, NULL
, NULL
));
391 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
392 LOOP_LOC (loop_vinfo
)))
394 fprintf (vect_dump
, "not vectorized: stmt not supported: ");
395 print_generic_expr (vect_dump
, stmt
, TDF_SLIM
);
400 nunits
= GET_MODE_NUNITS (TYPE_MODE (vectype
));
401 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
402 fprintf (vect_dump
, "nunits = %d", nunits
);
404 if (vectorization_factor
)
406 /* FORNOW: don't allow mixed units.
407 This restriction will be relaxed in the future. */
408 if (nunits
!= vectorization_factor
)
410 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
411 LOOP_LOC (loop_vinfo
)))
412 fprintf (vect_dump
, "not vectorized: mixed data-types");
417 vectorization_factor
= nunits
;
419 #ifdef ENABLE_CHECKING
420 gcc_assert (GET_MODE_SIZE (TYPE_MODE (scalar_type
))
421 * vectorization_factor
== UNITS_PER_SIMD_WORD
);
426 /* TODO: Analyze cost. Decide if worth while to vectorize. */
428 if (vectorization_factor
<= 1)
430 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
431 LOOP_LOC (loop_vinfo
)))
432 fprintf (vect_dump
, "not vectorized: unsupported data-type");
435 LOOP_VINFO_VECT_FACTOR (loop_vinfo
) = vectorization_factor
;
437 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
438 && vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
440 "vectorization_factor = %d, niters = " HOST_WIDE_INT_PRINT_DEC
,
441 vectorization_factor
, LOOP_VINFO_INT_NITERS (loop_vinfo
));
443 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
444 && LOOP_VINFO_INT_NITERS (loop_vinfo
) < vectorization_factor
)
446 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
447 LOOP_LOC (loop_vinfo
)))
448 fprintf (vect_dump
, "not vectorized: iteration count too small.");
452 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
)
453 || LOOP_VINFO_INT_NITERS (loop_vinfo
) % vectorization_factor
!= 0)
455 if (vect_print_dump_info (REPORT_DETAILS
, LOOP_LOC (loop_vinfo
)))
456 fprintf (vect_dump
, "epilog loop required.");
457 if (!vect_can_advance_ivs_p (loop_vinfo
))
459 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
460 LOOP_LOC (loop_vinfo
)))
462 "not vectorized: can't create epilog loop 1.");
465 if (!slpeel_can_duplicate_loop_p (loop
, loop
->single_exit
))
467 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
468 LOOP_LOC (loop_vinfo
)))
470 "not vectorized: can't create epilog loop 2.");
479 /* Function exist_non_indexing_operands_for_use_p
481 USE is one of the uses attached to STMT. Check if USE is
482 used in STMT for anything other than indexing an array. */
485 exist_non_indexing_operands_for_use_p (tree use
, tree stmt
)
488 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
490 /* USE corresponds to some operand in STMT. If there is no data
491 reference in STMT, then any operand that corresponds to USE
492 is not indexing an array. */
493 if (!STMT_VINFO_DATA_REF (stmt_info
))
496 /* STMT has a data_ref. FORNOW this means that its of one of
500 (This should have been verified in analyze_data_refs).
502 'var' in the second case corresponds to a def, not a use,
503 so USE cannot correspond to any operands that are not used
506 Therefore, all we need to check is if STMT falls into the
507 first case, and whether var corresponds to USE. */
509 if (TREE_CODE (TREE_OPERAND (stmt
, 0)) == SSA_NAME
)
512 operand
= TREE_OPERAND (stmt
, 1);
514 if (TREE_CODE (operand
) != SSA_NAME
)
524 /* Function vect_analyze_scalar_cycles.
526 Examine the cross iteration def-use cycles of scalar variables, by
527 analyzing the loop (scalar) PHIs; verify that the cross iteration def-use
528 cycles that they represent do not impede vectorization.
530 FORNOW: Reduction as in the following loop, is not supported yet:
534 The cross-iteration cycle corresponding to variable 'sum' will be
535 considered too complicated and will impede vectorization.
537 FORNOW: Induction as in the following loop, is not supported yet:
542 However, the following loop *is* vectorizable:
547 In both loops there exists a def-use cycle for the variable i:
548 loop: i_2 = PHI (i_0, i_1)
553 The evolution of the above cycle is considered simple enough,
554 however, we also check that the cycle does not need to be
555 vectorized, i.e - we check that the variable that this cycle
556 defines is only used for array indexing or in stmts that do not
557 need to be vectorized. This is not the case in loop2, but it
558 *is* the case in loop3. */
561 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo
)
564 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
565 basic_block bb
= loop
->header
;
568 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
569 fprintf (vect_dump
, "=== vect_analyze_scalar_cycles ===");
571 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
573 tree access_fn
= NULL
;
575 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
577 fprintf (vect_dump
, "Analyze phi: ");
578 print_generic_expr (vect_dump
, phi
, TDF_SLIM
);
581 /* Skip virtual phi's. The data dependences that are associated with
582 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
584 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi
))))
586 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
587 fprintf (vect_dump
, "virtual phi. skip.");
591 /* Analyze the evolution function. */
593 /* FORNOW: The only scalar cross-iteration cycles that we allow are
594 those of loop induction variables; This property is verified here.
596 Furthermore, if that induction variable is used in an operation
597 that needs to be vectorized (i.e, is not solely used to index
598 arrays and check the exit condition) - we do not support its
599 vectorization yet. This property is verified in vect_is_simple_use,
600 during vect_analyze_operations. */
602 access_fn
= /* instantiate_parameters
604 analyze_scalar_evolution (loop
, PHI_RESULT (phi
));
608 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
609 LOOP_LOC (loop_vinfo
)))
610 fprintf (vect_dump
, "not vectorized: unsupported scalar cycle.");
614 if (vect_print_dump_info (REPORT_DETAILS
,
615 LOOP_LOC (loop_vinfo
)))
617 fprintf (vect_dump
, "Access function of PHI: ");
618 print_generic_expr (vect_dump
, access_fn
, TDF_SLIM
);
621 if (!vect_is_simple_iv_evolution (loop
->num
, access_fn
, &dummy
, &dummy
))
623 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
624 LOOP_LOC (loop_vinfo
)))
625 fprintf (vect_dump
, "not vectorized: unsupported scalar cycle.");
634 /* Function vect_base_addr_differ_p.
636 This is the simplest data dependence test: determines whether the
637 data references A and B access the same array/region. Returns
638 false when the property is not computable at compile time.
639 Otherwise return true, and DIFFER_P will record the result. This
640 utility will not be necessary when alias_sets_conflict_p will be
641 less conservative. */
644 vect_base_addr_differ_p (struct data_reference
*dra
,
645 struct data_reference
*drb
,
648 tree stmt_a
= DR_STMT (dra
);
649 stmt_vec_info stmt_info_a
= vinfo_for_stmt (stmt_a
);
650 tree stmt_b
= DR_STMT (drb
);
651 stmt_vec_info stmt_info_b
= vinfo_for_stmt (stmt_b
);
652 tree addr_a
= STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info_a
);
653 tree addr_b
= STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info_b
);
654 tree type_a
= TREE_TYPE (addr_a
);
655 tree type_b
= TREE_TYPE (addr_b
);
656 HOST_WIDE_INT alias_set_a
, alias_set_b
;
658 gcc_assert (POINTER_TYPE_P (type_a
) && POINTER_TYPE_P (type_b
));
660 /* Both references are ADDR_EXPR, i.e., we have the objects. */
661 if (TREE_CODE (addr_a
) == ADDR_EXPR
&& TREE_CODE (addr_b
) == ADDR_EXPR
)
662 return array_base_name_differ_p (dra
, drb
, differ_p
);
664 alias_set_a
= (TREE_CODE (addr_a
) == ADDR_EXPR
) ?
665 get_alias_set (TREE_OPERAND (addr_a
, 0)) : get_alias_set (addr_a
);
666 alias_set_b
= (TREE_CODE (addr_b
) == ADDR_EXPR
) ?
667 get_alias_set (TREE_OPERAND (addr_b
, 0)) : get_alias_set (addr_b
);
669 if (!alias_sets_conflict_p (alias_set_a
, alias_set_b
))
675 /* An instruction writing through a restricted pointer is "independent" of any
676 instruction reading or writing through a different pointer, in the same
678 else if ((TYPE_RESTRICT (type_a
) && !DR_IS_READ (dra
))
679 || (TYPE_RESTRICT (type_b
) && !DR_IS_READ (drb
)))
688 /* Function vect_analyze_data_ref_dependence.
690 Return TRUE if there (might) exist a dependence between a memory-reference
691 DRA and a memory-reference DRB. */
694 vect_analyze_data_ref_dependence (struct data_reference
*dra
,
695 struct data_reference
*drb
,
696 loop_vec_info loop_vinfo
)
699 struct data_dependence_relation
*ddr
;
701 if (!vect_base_addr_differ_p (dra
, drb
, &differ_p
))
703 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
704 LOOP_LOC (loop_vinfo
)))
707 "not vectorized: can't determine dependence between: ");
708 print_generic_expr (vect_dump
, DR_REF (dra
), TDF_SLIM
);
709 fprintf (vect_dump
, " and ");
710 print_generic_expr (vect_dump
, DR_REF (drb
), TDF_SLIM
);
718 ddr
= initialize_data_dependence_relation (dra
, drb
);
719 compute_affine_dependence (ddr
);
721 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
724 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
725 LOOP_LOC (loop_vinfo
)))
728 "not vectorized: possible dependence between data-refs ");
729 print_generic_expr (vect_dump
, DR_REF (dra
), TDF_SLIM
);
730 fprintf (vect_dump
, " and ");
731 print_generic_expr (vect_dump
, DR_REF (drb
), TDF_SLIM
);
738 /* Function vect_analyze_data_ref_dependences.
740 Examine all the data references in the loop, and make sure there do not
741 exist any data dependences between them.
743 TODO: dependences which distance is greater than the vectorization factor
747 vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo
)
750 varray_type loop_write_refs
= LOOP_VINFO_DATAREF_WRITES (loop_vinfo
);
751 varray_type loop_read_refs
= LOOP_VINFO_DATAREF_READS (loop_vinfo
);
753 /* Examine store-store (output) dependences. */
755 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
756 fprintf (vect_dump
, "=== vect_analyze_dependences ===");
758 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
759 fprintf (vect_dump
, "compare all store-store pairs.");
761 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (loop_write_refs
); i
++)
763 for (j
= i
+ 1; j
< VARRAY_ACTIVE_SIZE (loop_write_refs
); j
++)
765 struct data_reference
*dra
=
766 VARRAY_GENERIC_PTR (loop_write_refs
, i
);
767 struct data_reference
*drb
=
768 VARRAY_GENERIC_PTR (loop_write_refs
, j
);
769 if (vect_analyze_data_ref_dependence (dra
, drb
, loop_vinfo
))
774 /* Examine load-store (true/anti) dependences. */
776 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
777 fprintf (vect_dump
, "compare all load-store pairs.");
779 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (loop_read_refs
); i
++)
781 for (j
= 0; j
< VARRAY_ACTIVE_SIZE (loop_write_refs
); j
++)
783 struct data_reference
*dra
= VARRAY_GENERIC_PTR (loop_read_refs
, i
);
784 struct data_reference
*drb
=
785 VARRAY_GENERIC_PTR (loop_write_refs
, j
);
786 if (vect_analyze_data_ref_dependence (dra
, drb
, loop_vinfo
))
795 /* Function vect_compute_data_ref_alignment
797 Compute the misalignment of the data reference DR.
800 1. If during the misalignment computation it is found that the data reference
801 cannot be vectorized then false is returned.
802 2. DR_MISALIGNMENT (DR) is defined.
804 FOR NOW: No analysis is actually performed. Misalignment is calculated
805 only for trivial cases. TODO. */
808 vect_compute_data_ref_alignment (struct data_reference
*dr
)
810 tree stmt
= DR_STMT (dr
);
811 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
812 tree ref
= DR_REF (dr
);
814 tree base
, alignment
;
818 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
819 fprintf (vect_dump
, "vect_compute_data_ref_alignment:");
821 /* Initialize misalignment to unknown. */
822 DR_MISALIGNMENT (dr
) = -1;
824 misalign
= STMT_VINFO_VECT_MISALIGNMENT (stmt_info
);
825 base_aligned_p
= STMT_VINFO_VECT_BASE_ALIGNED_P (stmt_info
);
826 base
= build_fold_indirect_ref (STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info
));
827 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
831 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
833 fprintf (vect_dump
, "Unknown alignment for access: ");
834 print_generic_expr (vect_dump
, base
, TDF_SLIM
);
841 if (!vect_can_force_dr_alignment_p (base
, TYPE_ALIGN (vectype
)))
843 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
845 fprintf (vect_dump
, "can't force alignment of ref: ");
846 print_generic_expr (vect_dump
, ref
, TDF_SLIM
);
851 /* Force the alignment of the decl.
852 NOTE: This is the only change to the code we make during
853 the analysis phase, before deciding to vectorize the loop. */
854 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
855 fprintf (vect_dump
, "force alignment");
856 DECL_ALIGN (base
) = TYPE_ALIGN (vectype
);
857 DECL_USER_ALIGN (base
) = 1;
860 /* At this point we assume that the base is aligned. */
861 gcc_assert (base_aligned_p
862 || (TREE_CODE (base
) == VAR_DECL
863 && DECL_ALIGN (base
) >= TYPE_ALIGN (vectype
)));
865 /* Alignment required, in bytes: */
866 alignment
= ssize_int (TYPE_ALIGN (vectype
)/BITS_PER_UNIT
);
868 /* Modulo alignment. */
869 misalign
= size_binop (TRUNC_MOD_EXPR
, misalign
, alignment
);
870 if (tree_int_cst_sgn (misalign
) < 0)
872 /* Negative misalignment value. */
873 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
874 fprintf (vect_dump
, "unexpected misalign value");
878 DR_MISALIGNMENT (dr
) = tree_low_cst (misalign
, 1);
880 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
881 fprintf (vect_dump
, "misalign = %d bytes", DR_MISALIGNMENT (dr
));
887 /* Function vect_compute_data_refs_alignment
889 Compute the misalignment of data references in the loop.
890 This pass may take place at function granularity instead of at loop
893 FOR NOW: No analysis is actually performed. Misalignment is calculated
894 only for trivial cases. TODO. */
897 vect_compute_data_refs_alignment (loop_vec_info loop_vinfo
)
899 varray_type loop_write_datarefs
= LOOP_VINFO_DATAREF_WRITES (loop_vinfo
);
900 varray_type loop_read_datarefs
= LOOP_VINFO_DATAREF_READS (loop_vinfo
);
903 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (loop_write_datarefs
); i
++)
905 struct data_reference
*dr
= VARRAY_GENERIC_PTR (loop_write_datarefs
, i
);
906 if (!vect_compute_data_ref_alignment (dr
))
910 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (loop_read_datarefs
); i
++)
912 struct data_reference
*dr
= VARRAY_GENERIC_PTR (loop_read_datarefs
, i
);
913 if (!vect_compute_data_ref_alignment (dr
))
921 /* Function vect_enhance_data_refs_alignment
923 This pass will use loop versioning and loop peeling in order to enhance
924 the alignment of data references in the loop.
926 FOR NOW: we assume that whatever versioning/peeling takes place, only the
927 original loop is to be vectorized; Any other loops that are created by
928 the transformations performed in this pass - are not supposed to be
929 vectorized. This restriction will be relaxed. */
932 vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo
)
934 varray_type loop_read_datarefs
= LOOP_VINFO_DATAREF_READS (loop_vinfo
);
935 varray_type loop_write_datarefs
= LOOP_VINFO_DATAREF_WRITES (loop_vinfo
);
939 This pass will require a cost model to guide it whether to apply peeling
940 or versioning or a combination of the two. For example, the scheme that
941 intel uses when given a loop with several memory accesses, is as follows:
942 choose one memory access ('p') which alignment you want to force by doing
943 peeling. Then, either (1) generate a loop in which 'p' is aligned and all
944 other accesses are not necessarily aligned, or (2) use loop versioning to
945 generate one loop in which all accesses are aligned, and another loop in
946 which only 'p' is necessarily aligned.
948 ("Automatic Intra-Register Vectorization for the Intel Architecture",
949 Aart J.C. Bik, Milind Girkar, Paul M. Grey and Ximmin Tian, International
950 Journal of Parallel Programming, Vol. 30, No. 2, April 2002.)
952 Devising a cost model is the most critical aspect of this work. It will
953 guide us on which access to peel for, whether to use loop versioning, how
954 many versions to create, etc. The cost model will probably consist of
955 generic considerations as well as target specific considerations (on
956 powerpc for example, misaligned stores are more painful than misaligned
959 Here is the general steps involved in alignment enhancements:
961 -- original loop, before alignment analysis:
963 x = q[i]; # DR_MISALIGNMENT(q) = unknown
964 p[i] = y; # DR_MISALIGNMENT(p) = unknown
967 -- After vect_compute_data_refs_alignment:
969 x = q[i]; # DR_MISALIGNMENT(q) = 3
970 p[i] = y; # DR_MISALIGNMENT(p) = unknown
973 -- Possibility 1: we do loop versioning:
975 for (i=0; i<N; i++){ # loop 1A
976 x = q[i]; # DR_MISALIGNMENT(q) = 3
977 p[i] = y; # DR_MISALIGNMENT(p) = 0
981 for (i=0; i<N; i++){ # loop 1B
982 x = q[i]; # DR_MISALIGNMENT(q) = 3
983 p[i] = y; # DR_MISALIGNMENT(p) = unaligned
987 -- Possibility 2: we do loop peeling:
988 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
992 for (i = 3; i < N; i++){ # loop 2A
993 x = q[i]; # DR_MISALIGNMENT(q) = 0
994 p[i] = y; # DR_MISALIGNMENT(p) = unknown
997 -- Possibility 3: combination of loop peeling and versioning:
998 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
1003 for (i = 3; i<N; i++){ # loop 3A
1004 x = q[i]; # DR_MISALIGNMENT(q) = 0
1005 p[i] = y; # DR_MISALIGNMENT(p) = 0
1009 for (i = 3; i<N; i++){ # loop 3B
1010 x = q[i]; # DR_MISALIGNMENT(q) = 0
1011 p[i] = y; # DR_MISALIGNMENT(p) = unaligned
1015 These loops are later passed to loop_transform to be vectorized. The
1016 vectorizer will use the alignment information to guide the transformation
1017 (whether to generate regular loads/stores, or with special handling for
1021 /* (1) Peeling to force alignment. */
1023 /* (1.1) Decide whether to perform peeling, and how many iterations to peel:
1025 + How many accesses will become aligned due to the peeling
1026 - How many accesses will become unaligned due to the peeling,
1027 and the cost of misaligned accesses.
1028 - The cost of peeling (the extra runtime checks, the increase
1031 The scheme we use FORNOW: peel to force the alignment of the first
1032 misaligned store in the loop.
1033 Rationale: misaligned stores are not yet supported.
1035 TODO: Use a better cost model. */
1037 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (loop_write_datarefs
); i
++)
1039 struct data_reference
*dr
= VARRAY_GENERIC_PTR (loop_write_datarefs
, i
);
1040 if (!aligned_access_p (dr
))
1042 LOOP_VINFO_UNALIGNED_DR (loop_vinfo
) = dr
;
1043 LOOP_DO_PEELING_FOR_ALIGNMENT (loop_vinfo
) = true;
1048 if (!LOOP_VINFO_UNALIGNED_DR (loop_vinfo
))
1050 if (vect_print_dump_info (REPORT_DETAILS
, LOOP_LOC (loop_vinfo
)))
1051 fprintf (vect_dump
, "Peeling for alignment will not be applied.");
1055 if (vect_print_dump_info (REPORT_DETAILS
, LOOP_LOC (loop_vinfo
)))
1056 fprintf (vect_dump
, "Peeling for alignment will be applied.");
1059 /* (1.2) Update the alignment info according to the peeling factor.
1060 If the misalignment of the DR we peel for is M, then the
1061 peeling factor is VF - M, and the misalignment of each access DR_i
1062 in the loop is DR_MISALIGNMENT (DR_i) + VF - M.
1063 If the misalignment of the DR we peel for is unknown, then the
1064 misalignment of each access DR_i in the loop is also unknown.
1066 FORNOW: set the misalignment of the accesses to unknown even
1067 if the peeling factor is known at compile time.
1069 TODO: - if the peeling factor is known at compile time, use that
1070 when updating the misalignment info of the loop DRs.
1071 - consider accesses that are known to have the same
1072 alignment, even if that alignment is unknown. */
1074 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (loop_write_datarefs
); i
++)
1076 struct data_reference
*dr
= VARRAY_GENERIC_PTR (loop_write_datarefs
, i
);
1077 if (dr
== LOOP_VINFO_UNALIGNED_DR (loop_vinfo
))
1079 DR_MISALIGNMENT (dr
) = 0;
1080 if (vect_print_dump_info (REPORT_ALIGNMENT
, LOOP_LOC (loop_vinfo
)))
1081 fprintf (vect_dump
, "Alignment of access forced using peeling.");
1084 DR_MISALIGNMENT (dr
) = -1;
1086 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (loop_read_datarefs
); i
++)
1088 struct data_reference
*dr
= VARRAY_GENERIC_PTR (loop_read_datarefs
, i
);
1089 if (dr
== LOOP_VINFO_UNALIGNED_DR (loop_vinfo
))
1091 DR_MISALIGNMENT (dr
) = 0;
1092 if (vect_print_dump_info (REPORT_ALIGNMENT
, LOOP_LOC (loop_vinfo
)))
1093 fprintf (vect_dump
, "Alignment of access forced using peeling.");
1096 DR_MISALIGNMENT (dr
) = -1;
1101 /* Function vect_analyze_data_refs_alignment
1103 Analyze the alignment of the data-references in the loop.
1104 FOR NOW: Until support for misliagned accesses is in place, only if all
1105 accesses are aligned can the loop be vectorized. This restriction will be
1109 vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo
)
1111 varray_type loop_read_datarefs
= LOOP_VINFO_DATAREF_READS (loop_vinfo
);
1112 varray_type loop_write_datarefs
= LOOP_VINFO_DATAREF_WRITES (loop_vinfo
);
1113 enum dr_alignment_support supportable_dr_alignment
;
1116 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1117 fprintf (vect_dump
, "=== vect_analyze_data_refs_alignment ===");
1120 /* This pass may take place at function granularity instead of at loop
1123 if (!vect_compute_data_refs_alignment (loop_vinfo
))
1125 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
1126 LOOP_LOC (loop_vinfo
)))
1128 "not vectorized: can't calculate alignment for data ref.");
1133 /* This pass will decide on using loop versioning and/or loop peeling in
1134 order to enhance the alignment of data references in the loop. */
1136 vect_enhance_data_refs_alignment (loop_vinfo
);
1139 /* Finally, check that all the data references in the loop can be
1140 handled with respect to their alignment. */
1142 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (loop_read_datarefs
); i
++)
1144 struct data_reference
*dr
= VARRAY_GENERIC_PTR (loop_read_datarefs
, i
);
1145 supportable_dr_alignment
= vect_supportable_dr_alignment (dr
);
1146 if (!supportable_dr_alignment
)
1148 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
1149 LOOP_LOC (loop_vinfo
)))
1150 fprintf (vect_dump
, "not vectorized: unsupported unaligned load.");
1153 if (supportable_dr_alignment
!= dr_aligned
1154 && (vect_print_dump_info (REPORT_ALIGNMENT
, LOOP_LOC (loop_vinfo
))))
1155 fprintf (vect_dump
, "Vectorizing an unaligned access.");
1157 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (loop_write_datarefs
); i
++)
1159 struct data_reference
*dr
= VARRAY_GENERIC_PTR (loop_write_datarefs
, i
);
1160 supportable_dr_alignment
= vect_supportable_dr_alignment (dr
);
1161 if (!supportable_dr_alignment
)
1163 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
1164 LOOP_LOC (loop_vinfo
)))
1165 fprintf (vect_dump
, "not vectorized: unsupported unaligned store.");
1168 if (supportable_dr_alignment
!= dr_aligned
1169 && (vect_print_dump_info (REPORT_ALIGNMENT
, LOOP_LOC (loop_vinfo
))))
1170 fprintf (vect_dump
, "Vectorizing an unaligned access.");
1177 /* Function vect_analyze_data_ref_access.
1179 Analyze the access pattern of the data-reference DR. For now, a data access
1180 has to consecutive to be considered vectorizable. */
1183 vect_analyze_data_ref_access (struct data_reference
*dr
)
1185 tree stmt
= DR_STMT (dr
);
1186 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1187 tree step
= STMT_VINFO_VECT_STEP (stmt_info
);
1188 tree scalar_type
= TREE_TYPE (DR_REF (dr
));
1190 if (!step
|| tree_int_cst_compare (step
, TYPE_SIZE_UNIT (scalar_type
)))
1192 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1193 fprintf (vect_dump
, "not consecutive access");
1200 /* Function vect_analyze_data_ref_accesses.
1202 Analyze the access pattern of all the data references in the loop.
1204 FORNOW: the only access pattern that is considered vectorizable is a
1205 simple step 1 (consecutive) access.
1207 FORNOW: handle only arrays and pointer accesses. */
1210 vect_analyze_data_ref_accesses (loop_vec_info loop_vinfo
)
1213 varray_type loop_write_datarefs
= LOOP_VINFO_DATAREF_WRITES (loop_vinfo
);
1214 varray_type loop_read_datarefs
= LOOP_VINFO_DATAREF_READS (loop_vinfo
);
1216 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1217 fprintf (vect_dump
, "=== vect_analyze_data_ref_accesses ===");
1219 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (loop_write_datarefs
); i
++)
1221 struct data_reference
*dr
= VARRAY_GENERIC_PTR (loop_write_datarefs
, i
);
1222 bool ok
= vect_analyze_data_ref_access (dr
);
1225 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
1226 LOOP_LOC (loop_vinfo
)))
1227 fprintf (vect_dump
, "not vectorized: complicated access pattern.");
1232 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (loop_read_datarefs
); i
++)
1234 struct data_reference
*dr
= VARRAY_GENERIC_PTR (loop_read_datarefs
, i
);
1235 bool ok
= vect_analyze_data_ref_access (dr
);
1238 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
1239 LOOP_LOC (loop_vinfo
)))
1240 fprintf (vect_dump
, "not vectorized: complicated access pattern.");
1249 /* Function vect_analyze_pointer_ref_access.
1252 STMT - a stmt that contains a data-ref.
1253 MEMREF - a data-ref in STMT, which is an INDIRECT_REF.
1254 ACCESS_FN - the access function of MEMREF.
1257 If the data-ref access is vectorizable, return a data_reference structure
1258 that represents it (DR). Otherwise - return NULL.
1259 STEP - the stride of MEMREF in the loop.
1260 INIT - the initial condition of MEMREF in the loop.
1263 static struct data_reference
*
1264 vect_analyze_pointer_ref_access (tree memref
, tree stmt
, bool is_read
,
1265 tree access_fn
, tree
*ptr_init
, tree
*ptr_step
)
1267 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1268 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
1269 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1271 tree reftype
, innertype
;
1272 tree indx_access_fn
;
1273 int loopnum
= loop
->num
;
1274 struct data_reference
*dr
;
1276 if (!vect_is_simple_iv_evolution (loopnum
, access_fn
, &init
, &step
))
1278 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
1279 LOOP_LOC (loop_vinfo
)))
1280 fprintf (vect_dump
, "not vectorized: pointer access is not simple.");
1286 if (!expr_invariant_in_loop_p (loop
, init
))
1288 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
1289 LOOP_LOC (loop_vinfo
)))
1291 "not vectorized: initial condition is not loop invariant.");
1295 if (TREE_CODE (step
) != INTEGER_CST
)
1297 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
1298 LOOP_LOC (loop_vinfo
)))
1300 "not vectorized: non constant step for pointer access.");
1304 reftype
= TREE_TYPE (TREE_OPERAND (memref
, 0));
1305 if (!POINTER_TYPE_P (reftype
))
1307 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
1308 LOOP_LOC (loop_vinfo
)))
1309 fprintf (vect_dump
, "not vectorized: unexpected pointer access form.");
1313 reftype
= TREE_TYPE (init
);
1314 if (!POINTER_TYPE_P (reftype
))
1316 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
1317 LOOP_LOC (loop_vinfo
)))
1318 fprintf (vect_dump
, "not vectorized: unexpected pointer access form.");
1322 *ptr_step
= fold_convert (ssizetype
, step
);
1323 innertype
= TREE_TYPE (reftype
);
1324 /* Check that STEP is a multiple of type size. */
1325 if (!integer_zerop (size_binop (TRUNC_MOD_EXPR
, *ptr_step
,
1326 fold_convert (ssizetype
, TYPE_SIZE_UNIT (innertype
)))))
1328 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
1329 LOOP_LOC (loop_vinfo
)))
1330 fprintf (vect_dump
, "not vectorized: non consecutive access.");
1335 build_polynomial_chrec (loopnum
, integer_zero_node
, integer_one_node
);
1336 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1338 fprintf (vect_dump
, "Access function of ptr indx: ");
1339 print_generic_expr (vect_dump
, indx_access_fn
, TDF_SLIM
);
1341 dr
= init_data_ref (stmt
, memref
, NULL_TREE
, indx_access_fn
, is_read
);
1347 /* Function vect_address_analysis
1349 Return the BASE of the address expression EXPR.
1350 Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1353 EXPR - the address expression that is being analyzed
1354 STMT - the statement that contains EXPR or its original memory reference
1355 IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
1356 VECTYPE - the type that defines the alignment (i.e, we compute
1357 alignment relative to TYPE_ALIGN(VECTYPE))
1358 DR - data_reference struct for the original memory reference
1361 BASE (returned value) - the base of the data reference EXPR.
1362 INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
1363 MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
1364 computation is impossible
1365 STEP - evolution of EXPR in the loop
1366 BASE_ALIGNED - indicates if BASE is aligned
1368 If something unexpected is encountered (an unsupported form of data-ref),
1369 then NULL_TREE is returned.
1373 vect_address_analysis (tree expr
, tree stmt
, bool is_read
, tree vectype
,
1374 struct data_reference
*dr
, tree
*offset
, tree
*misalign
,
1375 tree
*step
, bool *base_aligned
)
1377 tree oprnd0
, oprnd1
, base_address
, offset_expr
, base_addr0
, base_addr1
;
1378 tree address_offset
= ssize_int (0), address_misalign
= ssize_int (0);
1382 switch (TREE_CODE (expr
))
1386 /* EXPR is of form {base +/- offset} (or {offset +/- base}). */
1387 oprnd0
= TREE_OPERAND (expr
, 0);
1388 oprnd1
= TREE_OPERAND (expr
, 1);
1390 STRIP_NOPS (oprnd0
);
1391 STRIP_NOPS (oprnd1
);
1393 /* Recursively try to find the base of the address contained in EXPR.
1394 For offset, the returned base will be NULL. */
1395 base_addr0
= vect_address_analysis (oprnd0
, stmt
, is_read
, vectype
, dr
,
1396 &address_offset
, &address_misalign
, step
,
1399 base_addr1
= vect_address_analysis (oprnd1
, stmt
, is_read
, vectype
, dr
,
1400 &address_offset
, &address_misalign
, step
,
1403 /* We support cases where only one of the operands contains an
1405 if ((base_addr0
&& base_addr1
) || (!base_addr0
&& !base_addr1
))
1408 /* To revert STRIP_NOPS. */
1409 oprnd0
= TREE_OPERAND (expr
, 0);
1410 oprnd1
= TREE_OPERAND (expr
, 1);
1412 offset_expr
= base_addr0
?
1413 fold_convert (ssizetype
, oprnd1
) : fold_convert (ssizetype
, oprnd0
);
1415 /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is
1416 a number, we can add it to the misalignment value calculated for base,
1417 otherwise, misalignment is NULL. */
1418 if (TREE_CODE (offset_expr
) == INTEGER_CST
&& address_misalign
)
1419 *misalign
= size_binop (TREE_CODE (expr
), address_misalign
,
1422 *misalign
= NULL_TREE
;
1424 /* Combine offset (from EXPR {base + offset}) with the offset calculated
1426 *offset
= size_binop (TREE_CODE (expr
), address_offset
, offset_expr
);
1427 return base_addr0
? base_addr0
: base_addr1
;
1430 base_address
= vect_object_analysis (TREE_OPERAND (expr
, 0), stmt
,
1431 is_read
, vectype
, &dr
, offset
,
1432 misalign
, step
, base_aligned
,
1434 return base_address
;
1437 if (!POINTER_TYPE_P (TREE_TYPE (expr
)))
1440 if (TYPE_ALIGN (TREE_TYPE (TREE_TYPE (expr
))) < TYPE_ALIGN (vectype
))
1442 if (vect_get_ptr_offset (expr
, vectype
, misalign
))
1443 *base_aligned
= true;
1445 *base_aligned
= false;
1449 *base_aligned
= true;
1450 *misalign
= ssize_int (0);
1452 *offset
= ssize_int (0);
1453 *step
= ssize_int (0);
1462 /* Function vect_object_analysis
1464 Return the BASE of the data reference MEMREF.
1465 Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1466 E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset
1467 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET
1468 instantiated with initial_conditions of access_functions of variables,
1469 modulo alignment, and STEP is the evolution of the DR_REF in this loop.
1471 Function get_inner_reference is used for the above in case of ARRAY_REF and
1474 The structure of the function is as follows:
1476 Case 1. For handled_component_p refs
1477 1.1 call get_inner_reference
1478 1.1.1 analyze offset expr received from get_inner_reference
1479 1.2. build data-reference structure for MEMREF
1480 (fall through with BASE)
1481 Case 2. For declarations
1483 2.2 update DR_BASE_NAME if necessary for alias
1484 Case 3. For INDIRECT_REFs
1485 3.1 get the access function
1486 3.2 analyze evolution of MEMREF
1487 3.3 set data-reference structure for MEMREF
1488 3.4 call vect_address_analysis to analyze INIT of the access function
1491 Combine the results of object and address analysis to calculate
1492 INITIAL_OFFSET, STEP and misalignment info.
1495 MEMREF - the memory reference that is being analyzed
1496 STMT - the statement that contains MEMREF
1497 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1498 VECTYPE - the type that defines the alignment (i.e, we compute
1499 alignment relative to TYPE_ALIGN(VECTYPE))
1502 BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
1503 E.g, if MEMREF is a.b[k].c[i][j] the returned
1505 DR - data_reference struct for MEMREF
1506 INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
1507 MISALIGN - offset of MEMREF from BASE in bytes (a constant) or NULL_TREE if
1508 the computation is impossible
1509 STEP - evolution of the DR_REF in the loop
1510 BASE_ALIGNED - indicates if BASE is aligned
1511 MEMTAG - memory tag for aliasing purposes
1512 SUBVAR - Sub-variables of the variable
1514 If something unexpected is encountered (an unsupported form of data-ref),
1515 then NULL_TREE is returned. */
1518 vect_object_analysis (tree memref
, tree stmt
, bool is_read
,
1519 tree vectype
, struct data_reference
**dr
,
1520 tree
*offset
, tree
*misalign
, tree
*step
,
1521 bool *base_aligned
, tree
*memtag
,
1524 tree base
= NULL_TREE
, base_address
= NULL_TREE
;
1525 tree object_offset
= ssize_int (0), object_misalign
= ssize_int (0);
1526 tree object_step
= ssize_int (0), address_step
= ssize_int (0);
1527 bool object_base_aligned
= true, address_base_aligned
= true;
1528 tree address_offset
= ssize_int (0), address_misalign
= ssize_int (0);
1529 HOST_WIDE_INT pbitsize
, pbitpos
;
1530 tree poffset
, bit_pos_in_bytes
;
1531 enum machine_mode pmode
;
1532 int punsignedp
, pvolatilep
;
1533 tree ptr_step
= ssize_int (0), ptr_init
= NULL_TREE
;
1534 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1535 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
1536 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1537 struct data_reference
*ptr_dr
= NULL
;
1538 tree access_fn
, evolution_part
, address_to_analyze
;
1541 /* Case 1. handled_component_p refs. */
1542 if (handled_component_p (memref
))
1544 /* 1.1 call get_inner_reference. */
1545 /* Find the base and the offset from it. */
1546 base
= get_inner_reference (memref
, &pbitsize
, &pbitpos
, &poffset
,
1547 &pmode
, &punsignedp
, &pvolatilep
, false);
1551 /* 1.1.1 analyze offset expr received from get_inner_reference. */
1553 && !vect_analyze_offset_expr (poffset
, loop
, TYPE_SIZE_UNIT (vectype
),
1554 &object_offset
, &object_misalign
, &object_step
))
1556 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1558 fprintf (vect_dump
, "failed to compute offset or step for ");
1559 print_generic_expr (vect_dump
, memref
, TDF_SLIM
);
1564 /* Add bit position to OFFSET and MISALIGN. */
1566 bit_pos_in_bytes
= ssize_int (pbitpos
/BITS_PER_UNIT
);
1567 /* Check that there is no remainder in bits. */
1568 if (pbitpos
%BITS_PER_UNIT
)
1570 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1571 fprintf (vect_dump
, "bit offset alignment.");
1574 object_offset
= size_binop (PLUS_EXPR
, bit_pos_in_bytes
, object_offset
);
1575 if (object_misalign
)
1576 object_misalign
= size_binop (PLUS_EXPR
, object_misalign
,
1579 /* Create data-reference for MEMREF. TODO: handle COMPONENT_REFs. */
1582 if (TREE_CODE (memref
) == ARRAY_REF
)
1583 *dr
= analyze_array (stmt
, memref
, is_read
);
1588 memref
= base
; /* To continue analysis of BASE. */
1592 /* Part 1: Case 2. Declarations. */
1593 if (DECL_P (memref
))
1595 /* We expect to get a decl only if we already have a DR. */
1598 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1600 fprintf (vect_dump
, "unhandled decl ");
1601 print_generic_expr (vect_dump
, memref
, TDF_SLIM
);
1606 /* 2.1 check the alignment. */
1607 if (DECL_ALIGN (memref
) >= TYPE_ALIGN (vectype
))
1608 object_base_aligned
= true;
1610 object_base_aligned
= false;
1612 /* 2.2 update DR_BASE_NAME if necessary. */
1613 if (!DR_BASE_NAME ((*dr
)))
1614 /* For alias analysis. In case the analysis of INDIRECT_REF brought
1616 DR_BASE_NAME ((*dr
)) = memref
;
1618 if (SSA_VAR_P (memref
) && var_can_have_subvars (memref
))
1619 *subvars
= get_subvars_for_var (memref
);
1620 base_address
= build_fold_addr_expr (memref
);
1624 /* Part 1: Case 3. INDIRECT_REFs. */
1625 else if (TREE_CODE (memref
) == INDIRECT_REF
)
1627 /* 3.1 get the access function. */
1628 access_fn
= analyze_scalar_evolution (loop
, TREE_OPERAND (memref
, 0));
1631 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
1632 LOOP_LOC (loop_vinfo
)))
1633 fprintf (vect_dump
, "not vectorized: complicated pointer access.");
1636 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1638 fprintf (vect_dump
, "Access function of ptr: ");
1639 print_generic_expr (vect_dump
, access_fn
, TDF_SLIM
);
1642 /* 3.2 analyze evolution of MEMREF. */
1643 evolution_part
= evolution_part_in_loop_num (access_fn
, loop
->num
);
1646 ptr_dr
= vect_analyze_pointer_ref_access (memref
, stmt
, is_read
,
1647 access_fn
, &ptr_init
, &ptr_step
);
1651 object_step
= size_binop (PLUS_EXPR
, object_step
, ptr_step
);
1652 address_to_analyze
= ptr_init
;
1658 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
1659 LOOP_LOC (loop_vinfo
)))
1660 fprintf (vect_dump
, "not vectorized: ptr is loop invariant.");
1663 /* Since there exists DR for MEMREF, we are analyzing the init of
1664 the access function, which not necessary has evolution in the
1666 address_to_analyze
= initial_condition_in_loop_num (access_fn
,
1670 /* 3.3 set data-reference structure for MEMREF. */
1671 *dr
= (*dr
) ? *dr
: ptr_dr
;
1673 /* 3.4 call vect_address_analysis to analyze INIT of the access
1675 base_address
= vect_address_analysis (address_to_analyze
, stmt
, is_read
,
1676 vectype
, *dr
, &address_offset
, &address_misalign
,
1677 &address_step
, &address_base_aligned
);
1681 switch (TREE_CODE (base_address
))
1684 *memtag
= get_var_ann (SSA_NAME_VAR (base_address
))->type_mem_tag
;
1685 if (!(*memtag
) && TREE_CODE (TREE_OPERAND (memref
, 0)) == SSA_NAME
)
1686 *memtag
= get_var_ann (
1687 SSA_NAME_VAR (TREE_OPERAND (memref
, 0)))->type_mem_tag
;
1690 *memtag
= TREE_OPERAND (base_address
, 0);
1693 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
1694 LOOP_LOC (loop_vinfo
)))
1696 fprintf (vect_dump
, "not vectorized: no memtag ref: ");
1697 print_generic_expr (vect_dump
, memref
, TDF_SLIM
);
1704 /* MEMREF cannot be analyzed. */
1707 if (SSA_VAR_P (*memtag
) && var_can_have_subvars (*memtag
))
1708 *subvars
= get_subvars_for_var (*memtag
);
1710 /* Part 2: Combine the results of object and address analysis to calculate
1711 INITIAL_OFFSET, STEP and misalignment info. */
1712 *offset
= size_binop (PLUS_EXPR
, object_offset
, address_offset
);
1713 if (object_misalign
&& address_misalign
)
1714 *misalign
= size_binop (PLUS_EXPR
, object_misalign
, address_misalign
);
1716 *misalign
= NULL_TREE
;
1717 *step
= size_binop (PLUS_EXPR
, object_step
, address_step
);
1718 *base_aligned
= object_base_aligned
&& address_base_aligned
;
1720 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1722 fprintf (vect_dump
, "Results of object analysis for: ");
1723 print_generic_expr (vect_dump
, memref
, TDF_SLIM
);
1724 fprintf (vect_dump
, "\n\tbase_address: ");
1725 print_generic_expr (vect_dump
, base_address
, TDF_SLIM
);
1726 fprintf (vect_dump
, "\n\toffset: ");
1727 print_generic_expr (vect_dump
, *offset
, TDF_SLIM
);
1728 fprintf (vect_dump
, "\n\tstep: ");
1729 print_generic_expr (vect_dump
, *step
, TDF_SLIM
);
1730 fprintf (vect_dump
, "\n\tbase aligned %d\n\tmisalign: ", *base_aligned
);
1731 print_generic_expr (vect_dump
, *misalign
, TDF_SLIM
);
1733 return base_address
;
1737 /* Function vect_analyze_data_refs.
1739 Find all the data references in the loop.
1741 The general structure of the analysis of data refs in the vectorizer is as
1743 1- vect_analyze_data_refs(loop):
1744 Find and analyze all data-refs in the loop:
1746 base_address = vect_object_analysis(ref)
1747 1.1- vect_object_analysis(ref):
1748 Analyze ref, and build a DR (data_referece struct) for it;
1749 compute base, initial_offset, step and alignment.
1750 Call get_inner_reference for refs handled in this function.
1751 Call vect_addr_analysis(addr) to analyze pointer type expressions.
1752 Set ref_stmt.base, ref_stmt.initial_offset, ref_stmt.alignment,
1753 ref_stmt.memtag and ref_stmt.step accordingly.
1754 2- vect_analyze_dependences(): apply dependence testing using ref_stmt.DR
1755 3- vect_analyze_drs_alignment(): check that ref_stmt.alignment is ok.
1756 4- vect_analyze_drs_access(): check that ref_stmt.step is ok.
1758 FORNOW: Handle aligned INDIRECT_REFs and ARRAY_REFs
1759 which base is really an array (not a pointer) and which alignment
1760 can be forced. This restriction will be relaxed. */
1763 vect_analyze_data_refs (loop_vec_info loop_vinfo
)
1765 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1766 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1767 int nbbs
= loop
->num_nodes
;
1768 block_stmt_iterator si
;
1770 struct data_reference
*dr
;
1772 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1773 fprintf (vect_dump
, "=== vect_analyze_data_refs ===");
1775 for (j
= 0; j
< nbbs
; j
++)
1777 basic_block bb
= bbs
[j
];
1778 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
1780 bool is_read
= false;
1781 tree stmt
= bsi_stmt (si
);
1782 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1783 v_may_def_optype v_may_defs
= STMT_V_MAY_DEF_OPS (stmt
);
1784 v_must_def_optype v_must_defs
= STMT_V_MUST_DEF_OPS (stmt
);
1785 vuse_optype vuses
= STMT_VUSE_OPS (stmt
);
1786 varray_type
*datarefs
= NULL
;
1787 int nvuses
, nv_may_defs
, nv_must_defs
;
1789 tree scalar_type
, vectype
;
1790 tree base
, offset
, misalign
, step
, tag
;
1794 /* Assumption: there exists a data-ref in stmt, if and only if
1795 it has vuses/vdefs. */
1797 if (!vuses
&& !v_may_defs
&& !v_must_defs
)
1800 nvuses
= NUM_VUSES (vuses
);
1801 nv_may_defs
= NUM_V_MAY_DEFS (v_may_defs
);
1802 nv_must_defs
= NUM_V_MUST_DEFS (v_must_defs
);
1804 if (nvuses
&& (nv_may_defs
|| nv_must_defs
))
1806 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1808 fprintf (vect_dump
, "unexpected vdefs and vuses in stmt: ");
1809 print_generic_expr (vect_dump
, stmt
, TDF_SLIM
);
1814 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
1816 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1818 fprintf (vect_dump
, "unexpected vops in stmt: ");
1819 print_generic_expr (vect_dump
, stmt
, TDF_SLIM
);
1826 memref
= TREE_OPERAND (stmt
, 1);
1827 datarefs
= &(LOOP_VINFO_DATAREF_READS (loop_vinfo
));
1832 memref
= TREE_OPERAND (stmt
, 0);
1833 datarefs
= &(LOOP_VINFO_DATAREF_WRITES (loop_vinfo
));
1837 scalar_type
= TREE_TYPE (memref
);
1838 vectype
= get_vectype_for_scalar_type (scalar_type
);
1841 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1843 fprintf (vect_dump
, "no vectype for stmt: ");
1844 print_generic_expr (vect_dump
, stmt
, TDF_SLIM
);
1845 fprintf (vect_dump
, " scalar_type: ");
1846 print_generic_expr (vect_dump
, scalar_type
, TDF_DETAILS
);
1848 /* It is not possible to vectorize this data reference. */
1851 /* Analyze MEMREF. If it is of a supported form, build data_reference
1852 struct for it (DR). */
1854 base
= vect_object_analysis (memref
, stmt
, is_read
, vectype
, &dr
,
1855 &offset
, &misalign
, &step
,
1856 &base_aligned
, &tag
, &subvars
);
1859 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
1860 LOOP_LOC (loop_vinfo
)))
1862 fprintf (vect_dump
, "not vectorized: unhandled data ref: ");
1863 print_generic_expr (vect_dump
, stmt
, TDF_SLIM
);
1867 STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info
) = base
;
1868 STMT_VINFO_VECT_INIT_OFFSET (stmt_info
) = offset
;
1869 STMT_VINFO_VECT_STEP (stmt_info
) = step
;
1870 STMT_VINFO_VECT_MISALIGNMENT (stmt_info
) = misalign
;
1871 STMT_VINFO_VECT_BASE_ALIGNED_P (stmt_info
) = base_aligned
;
1872 STMT_VINFO_MEMTAG (stmt_info
) = tag
;
1873 STMT_VINFO_SUBVARS (stmt_info
) = subvars
;
1874 STMT_VINFO_VECTYPE (stmt_info
) = vectype
;
1875 VARRAY_PUSH_GENERIC_PTR (*datarefs
, dr
);
1876 STMT_VINFO_DATA_REF (stmt_info
) = dr
;
1884 /* Utility functions used by vect_mark_stmts_to_be_vectorized. */
1886 /* Function vect_mark_relevant.
1888 Mark STMT as "relevant for vectorization" and add it to WORKLIST. */
1891 vect_mark_relevant (varray_type
*worklist
, tree stmt
)
1893 stmt_vec_info stmt_info
;
1895 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1896 fprintf (vect_dump
, "mark relevant.");
1898 if (TREE_CODE (stmt
) == PHI_NODE
)
1900 VARRAY_PUSH_TREE (*worklist
, stmt
);
1904 stmt_info
= vinfo_for_stmt (stmt
);
1908 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1910 fprintf (vect_dump
, "mark relevant: no stmt info!!.");
1911 print_generic_expr (vect_dump
, stmt
, TDF_SLIM
);
1916 if (STMT_VINFO_RELEVANT_P (stmt_info
))
1918 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1919 fprintf (vect_dump
, "already marked relevant.");
1923 STMT_VINFO_RELEVANT_P (stmt_info
) = 1;
1924 VARRAY_PUSH_TREE (*worklist
, stmt
);
1928 /* Function vect_stmt_relevant_p.
1930 Return true if STMT in loop that is represented by LOOP_VINFO is
1931 "relevant for vectorization".
1933 A stmt is considered "relevant for vectorization" if:
1934 - it has uses outside the loop.
1935 - it has vdefs (it alters memory).
1936 - control stmts in the loop (except for the exit condition).
1938 CHECKME: what other side effects would the vectorizer allow? */
1941 vect_stmt_relevant_p (tree stmt
, loop_vec_info loop_vinfo
)
1943 v_may_def_optype v_may_defs
;
1944 v_must_def_optype v_must_defs
;
1945 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1950 /* cond stmt other than loop exit cond. */
1951 if (is_ctrl_stmt (stmt
) && (stmt
!= LOOP_VINFO_EXIT_COND (loop_vinfo
)))
1954 /* changing memory. */
1955 if (TREE_CODE (stmt
) != PHI_NODE
)
1957 v_may_defs
= STMT_V_MAY_DEF_OPS (stmt
);
1958 v_must_defs
= STMT_V_MUST_DEF_OPS (stmt
);
1959 if (v_may_defs
|| v_must_defs
)
1961 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1962 fprintf (vect_dump
, "vec_stmt_relevant_p: stmt has vdefs.");
1967 /* uses outside the loop. */
1968 df
= get_immediate_uses (stmt
);
1969 num_uses
= num_immediate_uses (df
);
1970 for (i
= 0; i
< num_uses
; i
++)
1972 tree use
= immediate_use (df
, i
);
1973 basic_block bb
= bb_for_stmt (use
);
1974 if (!flow_bb_inside_loop_p (loop
, bb
))
1976 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
1977 fprintf (vect_dump
, "vec_stmt_relevant_p: used out of loop.");
1986 /* Function vect_mark_stmts_to_be_vectorized.
1988 Not all stmts in the loop need to be vectorized. For example:
1997 Stmt 1 and 3 do not need to be vectorized, because loop control and
1998 addressing of vectorized data-refs are handled differently.
2000 This pass detects such stmts. */
2003 vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo
)
2005 varray_type worklist
;
2006 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2007 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
2008 unsigned int nbbs
= loop
->num_nodes
;
2009 block_stmt_iterator si
;
2015 stmt_vec_info stmt_info
;
2019 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
2020 fprintf (vect_dump
, "=== vect_mark_stmts_to_be_vectorized ===");
2023 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2025 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
2027 fprintf (vect_dump
, "init: phi relevant? ");
2028 print_generic_expr (vect_dump
, phi
, TDF_SLIM
);
2031 if (vect_stmt_relevant_p (phi
, loop_vinfo
))
2033 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
2034 LOOP_LOC (loop_vinfo
)))
2035 fprintf (vect_dump
, "unsupported reduction/induction.");
2040 VARRAY_TREE_INIT (worklist
, 64, "work list");
2042 /* 1. Init worklist. */
2044 for (i
= 0; i
< nbbs
; i
++)
2047 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
2049 stmt
= bsi_stmt (si
);
2051 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
2053 fprintf (vect_dump
, "init: stmt relevant? ");
2054 print_generic_expr (vect_dump
, stmt
, TDF_SLIM
);
2057 stmt_info
= vinfo_for_stmt (stmt
);
2058 STMT_VINFO_RELEVANT_P (stmt_info
) = 0;
2060 if (vect_stmt_relevant_p (stmt
, loop_vinfo
))
2061 vect_mark_relevant (&worklist
, stmt
);
2066 /* 2. Process_worklist */
2068 while (VARRAY_ACTIVE_SIZE (worklist
) > 0)
2070 stmt
= VARRAY_TOP_TREE (worklist
);
2071 VARRAY_POP (worklist
);
2073 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
2075 fprintf (vect_dump
, "worklist: examine stmt: ");
2076 print_generic_expr (vect_dump
, stmt
, TDF_SLIM
);
2079 /* Examine the USES in this statement. Mark all the statements which
2080 feed this statement's uses as "relevant", unless the USE is used as
2083 if (TREE_CODE (stmt
) == PHI_NODE
)
2085 /* follow the def-use chain inside the loop. */
2086 for (j
= 0; j
< PHI_NUM_ARGS (stmt
); j
++)
2088 tree arg
= PHI_ARG_DEF (stmt
, j
);
2089 tree def_stmt
= NULL_TREE
;
2091 if (!vect_is_simple_use (arg
, loop_vinfo
, &def_stmt
))
2093 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
2094 LOOP_LOC (loop_vinfo
)))
2095 fprintf (vect_dump
, "not vectorized: unsupported use in stmt.");
2096 varray_clear (worklist
);
2102 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
2104 fprintf (vect_dump
, "worklist: def_stmt: ");
2105 print_generic_expr (vect_dump
, def_stmt
, TDF_SLIM
);
2108 bb
= bb_for_stmt (def_stmt
);
2109 if (flow_bb_inside_loop_p (loop
, bb
))
2110 vect_mark_relevant (&worklist
, def_stmt
);
2114 ann
= stmt_ann (stmt
);
2115 use_ops
= USE_OPS (ann
);
2117 for (i
= 0; i
< NUM_USES (use_ops
); i
++)
2119 tree use
= USE_OP (use_ops
, i
);
2121 /* We are only interested in uses that need to be vectorized. Uses
2122 that are used for address computation are not considered relevant.
2124 if (exist_non_indexing_operands_for_use_p (use
, stmt
))
2126 tree def_stmt
= NULL_TREE
;
2128 if (!vect_is_simple_use (use
, loop_vinfo
, &def_stmt
))
2130 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
,
2131 LOOP_LOC (loop_vinfo
)))
2132 fprintf (vect_dump
, "not vectorized: unsupported use in stmt.");
2133 varray_clear (worklist
);
2140 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
2142 fprintf (vect_dump
, "worklist: examine use %d: ", i
);
2143 print_generic_expr (vect_dump
, use
, TDF_SLIM
);
2146 bb
= bb_for_stmt (def_stmt
);
2147 if (flow_bb_inside_loop_p (loop
, bb
))
2148 vect_mark_relevant (&worklist
, def_stmt
);
2151 } /* while worklist */
2153 varray_clear (worklist
);
2158 /* Function vect_can_advance_ivs_p
2160 In case the number of iterations that LOOP iterates in unknown at compile
2161 time, an epilog loop will be generated, and the loop induction variables
2162 (IVs) will be "advanced" to the value they are supposed to take just before
2163 the epilog loop. Here we check that the access function of the loop IVs
2164 and the expression that represents the loop bound are simple enough.
2165 These restrictions will be relaxed in the future. */
2168 vect_can_advance_ivs_p (loop_vec_info loop_vinfo
)
2170 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2171 basic_block bb
= loop
->header
;
2174 /* Analyze phi functions of the loop header. */
2176 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2178 tree access_fn
= NULL
;
2179 tree evolution_part
;
2181 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
2183 fprintf (vect_dump
, "Analyze phi: ");
2184 print_generic_expr (vect_dump
, phi
, TDF_SLIM
);
2187 /* Skip virtual phi's. The data dependences that are associated with
2188 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
2190 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi
))))
2192 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
2193 fprintf (vect_dump
, "virtual phi. skip.");
2197 /* Analyze the evolution function. */
2199 access_fn
= instantiate_parameters
2200 (loop
, analyze_scalar_evolution (loop
, PHI_RESULT (phi
)));
2204 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
2205 fprintf (vect_dump
, "No Access function.");
2209 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
2211 fprintf (vect_dump
, "Access function of PHI: ");
2212 print_generic_expr (vect_dump
, access_fn
, TDF_SLIM
);
2215 evolution_part
= evolution_part_in_loop_num (access_fn
, loop
->num
);
2217 if (evolution_part
== NULL_TREE
)
2220 /* FORNOW: We do not transform initial conditions of IVs
2221 which evolution functions are a polynomial of degree >= 2. */
2223 if (tree_is_chrec (evolution_part
))
2231 /* Function vect_get_loop_niters.
2233 Determine how many iterations the loop is executed.
2234 If an expression that represents the number of iterations
2235 can be constructed, place it in NUMBER_OF_ITERATIONS.
2236 Return the loop exit condition. */
2239 vect_get_loop_niters (struct loop
*loop
, tree
*number_of_iterations
)
2243 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
2244 fprintf (vect_dump
, "=== get_loop_niters ===");
2246 niters
= number_of_iterations_in_loop (loop
);
2248 if (niters
!= NULL_TREE
2249 && niters
!= chrec_dont_know
)
2251 *number_of_iterations
= niters
;
2253 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
2255 fprintf (vect_dump
, "==> get_loop_niters:" );
2256 print_generic_expr (vect_dump
, *number_of_iterations
, TDF_SLIM
);
2260 return get_loop_exit_condition (loop
);
2264 /* Function vect_analyze_loop_form.
2266 Verify the following restrictions (some may be relaxed in the future):
2267 - it's an inner-most loop
2268 - number of BBs = 2 (which are the loop header and the latch)
2269 - the loop has a pre-header
2270 - the loop has a single entry and exit
2271 - the loop exit condition is simple enough, and the number of iterations
2272 can be analyzed (a countable loop). */
2274 static loop_vec_info
2275 vect_analyze_loop_form (struct loop
*loop
)
2277 loop_vec_info loop_vinfo
;
2279 tree number_of_iterations
= NULL
;
2282 loop_loc
= find_loop_location (loop
);
2284 if (vect_print_dump_info (REPORT_DETAILS
, loop_loc
))
2285 fprintf (vect_dump
, "=== vect_analyze_loop_form ===");
2289 if (vect_print_dump_info (REPORT_OUTER_LOOPS
, loop_loc
))
2290 fprintf (vect_dump
, "not vectorized: nested loop.");
2294 if (!loop
->single_exit
2295 || loop
->num_nodes
!= 2
2296 || EDGE_COUNT (loop
->header
->preds
) != 2)
2298 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
, loop_loc
))
2300 if (!loop
->single_exit
)
2301 fprintf (vect_dump
, "not vectorized: multiple exits.");
2302 else if (loop
->num_nodes
!= 2)
2303 fprintf (vect_dump
, "not vectorized: too many BBs in loop.");
2304 else if (EDGE_COUNT (loop
->header
->preds
) != 2)
2305 fprintf (vect_dump
, "not vectorized: too many incoming edges.");
2311 /* We assume that the loop exit condition is at the end of the loop. i.e,
2312 that the loop is represented as a do-while (with a proper if-guard
2313 before the loop if needed), where the loop header contains all the
2314 executable statements, and the latch is empty. */
2315 if (!empty_block_p (loop
->latch
))
2317 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
, loop_loc
))
2318 fprintf (vect_dump
, "not vectorized: unexpectd loop form.");
2322 /* Make sure there exists a single-predecessor exit bb: */
2323 if (!single_pred_p (loop
->single_exit
->dest
))
2325 edge e
= loop
->single_exit
;
2326 if (!(e
->flags
& EDGE_ABNORMAL
))
2328 loop_split_edge_with (e
, NULL
);
2329 if (vect_print_dump_info (REPORT_DETAILS
, loop_loc
))
2330 fprintf (vect_dump
, "split exit edge.");
2334 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
, loop_loc
))
2335 fprintf (vect_dump
, "not vectorized: abnormal loop exit edge.");
2340 if (empty_block_p (loop
->header
))
2342 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
, loop_loc
))
2343 fprintf (vect_dump
, "not vectorized: empty loop.");
2347 loop_cond
= vect_get_loop_niters (loop
, &number_of_iterations
);
2350 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
, loop_loc
))
2351 fprintf (vect_dump
, "not vectorized: complicated exit condition.");
2355 if (!number_of_iterations
)
2357 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
, loop_loc
))
2359 "not vectorized: number of iterations cannot be computed.");
2363 if (chrec_contains_undetermined (number_of_iterations
))
2365 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS
, loop_loc
))
2366 fprintf (vect_dump
, "Infinite number of iterations.");
2370 loop_vinfo
= new_loop_vec_info (loop
);
2371 LOOP_VINFO_NITERS (loop_vinfo
) = number_of_iterations
;
2373 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo
))
2375 if (vect_print_dump_info (REPORT_DETAILS
, loop_loc
))
2377 fprintf (vect_dump
, "Symbolic number of iterations is ");
2378 print_generic_expr (vect_dump
, number_of_iterations
, TDF_DETAILS
);
2382 if (LOOP_VINFO_INT_NITERS (loop_vinfo
) == 0)
2384 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS
, loop_loc
))
2385 fprintf (vect_dump
, "not vectorized: number of iterations = 0.");
2389 LOOP_VINFO_EXIT_COND (loop_vinfo
) = loop_cond
;
2390 LOOP_VINFO_LOC (loop_vinfo
) = loop_loc
;
2396 /* Function vect_analyze_loop.
2398 Apply a set of analyses on LOOP, and create a loop_vec_info struct
2399 for it. The different analyses will record information in the
2400 loop_vec_info struct. */
2402 vect_analyze_loop (struct loop
*loop
)
2405 loop_vec_info loop_vinfo
;
2407 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
2408 fprintf (vect_dump
, "===== analyze_loop_nest =====");
2410 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
2412 loop_vinfo
= vect_analyze_loop_form (loop
);
2415 if (vect_print_dump_info (REPORT_DETAILS
, UNKNOWN_LOC
))
2416 fprintf (vect_dump
, "bad loop form.");
2420 /* Find all data references in the loop (which correspond to vdefs/vuses)
2421 and analyze their evolution in the loop.
2423 FORNOW: Handle only simple, array references, which
2424 alignment can be forced, and aligned pointer-references. */
2426 ok
= vect_analyze_data_refs (loop_vinfo
);
2429 if (vect_print_dump_info (REPORT_DETAILS
, LOOP_LOC (loop_vinfo
)))
2430 fprintf (vect_dump
, "bad data references.");
2431 destroy_loop_vec_info (loop_vinfo
);
2435 /* Data-flow analysis to detect stmts that do not need to be vectorized. */
2437 ok
= vect_mark_stmts_to_be_vectorized (loop_vinfo
);
2440 if (vect_print_dump_info (REPORT_DETAILS
, LOOP_LOC (loop_vinfo
)))
2441 fprintf (vect_dump
, "unexpected pattern.");
2442 destroy_loop_vec_info (loop_vinfo
);
2446 /* Check that all cross-iteration scalar data-flow cycles are OK.
2447 Cross-iteration cycles caused by virtual phis are analyzed separately. */
2449 ok
= vect_analyze_scalar_cycles (loop_vinfo
);
2452 if (vect_print_dump_info (REPORT_DETAILS
, LOOP_LOC (loop_vinfo
)))
2453 fprintf (vect_dump
, "bad scalar cycle.");
2454 destroy_loop_vec_info (loop_vinfo
);
2458 /* Analyze data dependences between the data-refs in the loop.
2459 FORNOW: fail at the first data dependence that we encounter. */
2461 ok
= vect_analyze_data_ref_dependences (loop_vinfo
);
2464 if (vect_print_dump_info (REPORT_DETAILS
, LOOP_LOC (loop_vinfo
)))
2465 fprintf (vect_dump
, "bad data dependence.");
2466 destroy_loop_vec_info (loop_vinfo
);
2470 /* Analyze the access patterns of the data-refs in the loop (consecutive,
2471 complex, etc.). FORNOW: Only handle consecutive access pattern. */
2473 ok
= vect_analyze_data_ref_accesses (loop_vinfo
);
2476 if (vect_print_dump_info (REPORT_DETAILS
, LOOP_LOC (loop_vinfo
)))
2477 fprintf (vect_dump
, "bad data access.");
2478 destroy_loop_vec_info (loop_vinfo
);
2482 /* Analyze the alignment of the data-refs in the loop.
2483 FORNOW: Only aligned accesses are handled. */
2485 ok
= vect_analyze_data_refs_alignment (loop_vinfo
);
2488 if (vect_print_dump_info (REPORT_DETAILS
, LOOP_LOC (loop_vinfo
)))
2489 fprintf (vect_dump
, "bad data alignment.");
2490 destroy_loop_vec_info (loop_vinfo
);
2494 /* Scan all the operations in the loop and make sure they are
2497 ok
= vect_analyze_operations (loop_vinfo
);
2500 if (vect_print_dump_info (REPORT_DETAILS
, LOOP_LOC (loop_vinfo
)))
2501 fprintf (vect_dump
, "bad operation or unsupported loop bound.");
2502 destroy_loop_vec_info (loop_vinfo
);
2506 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
) = 1;