1 /* Data References Analysis and Manipulation Utilities for Vectorization.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com>
4 and Ira Rosen <irar@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
31 #include "basic-block.h"
32 #include "gimple-pretty-print.h"
36 #include "tree-chrec.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-vectorizer.h"
39 #include "diagnostic-core.h"
40 /* Need to include rtl.h, expr.h, etc. for optabs. */
44 /* Return true if load- or store-lanes optab OPTAB is implemented for
45 COUNT vectors of type VECTYPE. NAME is the name of OPTAB. */
48 vect_lanes_optab_supported_p (const char *name
, convert_optab optab
,
49 tree vectype
, unsigned HOST_WIDE_INT count
)
51 enum machine_mode mode
, array_mode
;
54 mode
= TYPE_MODE (vectype
);
55 limit_p
= !targetm
.array_mode_supported_p (mode
, count
);
56 array_mode
= mode_for_size (count
* GET_MODE_BITSIZE (mode
),
59 if (array_mode
== BLKmode
)
61 if (dump_enabled_p ())
62 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
63 "no array mode for %s[" HOST_WIDE_INT_PRINT_DEC
"]\n",
64 GET_MODE_NAME (mode
), count
);
68 if (convert_optab_handler (optab
, array_mode
, mode
) == CODE_FOR_nothing
)
70 if (dump_enabled_p ())
71 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
72 "cannot use %s<%s><%s>\n", name
,
73 GET_MODE_NAME (array_mode
), GET_MODE_NAME (mode
));
77 if (dump_enabled_p ())
78 dump_printf_loc (MSG_NOTE
, vect_location
,
79 "can use %s<%s><%s>\n", name
, GET_MODE_NAME (array_mode
),
80 GET_MODE_NAME (mode
));
86 /* Return the smallest scalar part of STMT.
87 This is used to determine the vectype of the stmt. We generally set the
88 vectype according to the type of the result (lhs). For stmts whose
89 result-type is different than the type of the arguments (e.g., demotion,
90 promotion), vectype will be reset appropriately (later). Note that we have
91 to visit the smallest datatype in this function, because that determines the
92 VF. If the smallest datatype in the loop is present only as the rhs of a
93 promotion operation - we'd miss it.
94 Such a case, where a variable of this datatype does not appear in the lhs
95 anywhere in the loop, can only occur if it's an invariant: e.g.:
96 'int_x = (int) short_inv', which we'd expect to have been optimized away by
97 invariant motion. However, we cannot rely on invariant motion to always
98 take invariants out of the loop, and so in the case of promotion we also
99 have to check the rhs.
100 LHS_SIZE_UNIT and RHS_SIZE_UNIT contain the sizes of the corresponding
104 vect_get_smallest_scalar_type (gimple stmt
, HOST_WIDE_INT
*lhs_size_unit
,
105 HOST_WIDE_INT
*rhs_size_unit
)
107 tree scalar_type
= gimple_expr_type (stmt
);
108 HOST_WIDE_INT lhs
, rhs
;
110 lhs
= rhs
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type
));
112 if (is_gimple_assign (stmt
)
113 && (gimple_assign_cast_p (stmt
)
114 || gimple_assign_rhs_code (stmt
) == WIDEN_MULT_EXPR
115 || gimple_assign_rhs_code (stmt
) == WIDEN_LSHIFT_EXPR
116 || gimple_assign_rhs_code (stmt
) == FLOAT_EXPR
))
118 tree rhs_type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
120 rhs
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (rhs_type
));
122 scalar_type
= rhs_type
;
125 *lhs_size_unit
= lhs
;
126 *rhs_size_unit
= rhs
;
131 /* Check if data references pointed by DR_I and DR_J are same or
132 belong to same interleaving group. Return FALSE if drs are
133 different, otherwise return TRUE. */
136 vect_same_range_drs (data_reference_p dr_i
, data_reference_p dr_j
)
138 gimple stmt_i
= DR_STMT (dr_i
);
139 gimple stmt_j
= DR_STMT (dr_j
);
141 if (operand_equal_p (DR_REF (dr_i
), DR_REF (dr_j
), 0)
142 || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_i
))
143 && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_j
))
144 && (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_i
))
145 == GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_j
)))))
151 /* If address ranges represented by DDR_I and DDR_J are equal,
152 return TRUE, otherwise return FALSE. */
155 vect_vfa_range_equal (ddr_p ddr_i
, ddr_p ddr_j
)
157 if ((vect_same_range_drs (DDR_A (ddr_i
), DDR_A (ddr_j
))
158 && vect_same_range_drs (DDR_B (ddr_i
), DDR_B (ddr_j
)))
159 || (vect_same_range_drs (DDR_A (ddr_i
), DDR_B (ddr_j
))
160 && vect_same_range_drs (DDR_B (ddr_i
), DDR_A (ddr_j
))))
166 /* Insert DDR into LOOP_VINFO list of ddrs that may alias and need to be
167 tested at run-time. Return TRUE if DDR was successfully inserted.
168 Return false if versioning is not supported. */
171 vect_mark_for_runtime_alias_test (ddr_p ddr
, loop_vec_info loop_vinfo
)
173 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
175 if ((unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS
) == 0)
178 if (dump_enabled_p ())
180 dump_printf_loc (MSG_NOTE
, vect_location
,
181 "mark for run-time aliasing test between ");
182 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (DDR_A (ddr
)));
183 dump_printf (MSG_NOTE
, " and ");
184 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (DDR_B (ddr
)));
185 dump_printf (MSG_NOTE
, "\n");
188 if (optimize_loop_nest_for_size_p (loop
))
190 if (dump_enabled_p ())
191 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
192 "versioning not supported when optimizing"
197 /* FORNOW: We don't support versioning with outer-loop vectorization. */
200 if (dump_enabled_p ())
201 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
202 "versioning not yet supported for outer-loops.\n");
206 /* FORNOW: We don't support creating runtime alias tests for non-constant
208 if (TREE_CODE (DR_STEP (DDR_A (ddr
))) != INTEGER_CST
209 || TREE_CODE (DR_STEP (DDR_B (ddr
))) != INTEGER_CST
)
211 if (dump_enabled_p ())
212 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
213 "versioning not yet supported for non-constant "
218 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
).safe_push (ddr
);
223 /* Function vect_analyze_data_ref_dependence.
225 Return TRUE if there (might) exist a dependence between a memory-reference
226 DRA and a memory-reference DRB. When versioning for alias may check a
227 dependence at run-time, return FALSE. Adjust *MAX_VF according to
228 the data dependence. */
231 vect_analyze_data_ref_dependence (struct data_dependence_relation
*ddr
,
232 loop_vec_info loop_vinfo
, int *max_vf
)
235 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
236 struct data_reference
*dra
= DDR_A (ddr
);
237 struct data_reference
*drb
= DDR_B (ddr
);
238 stmt_vec_info stmtinfo_a
= vinfo_for_stmt (DR_STMT (dra
));
239 stmt_vec_info stmtinfo_b
= vinfo_for_stmt (DR_STMT (drb
));
240 lambda_vector dist_v
;
241 unsigned int loop_depth
;
243 /* In loop analysis all data references should be vectorizable. */
244 if (!STMT_VINFO_VECTORIZABLE (stmtinfo_a
)
245 || !STMT_VINFO_VECTORIZABLE (stmtinfo_b
))
248 /* Independent data accesses. */
249 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
253 || (DR_IS_READ (dra
) && DR_IS_READ (drb
)))
256 /* Unknown data dependence. */
257 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
259 /* If user asserted safelen consecutive iterations can be
260 executed concurrently, assume independence. */
261 if (loop
->safelen
>= 2)
263 if (loop
->safelen
< *max_vf
)
264 *max_vf
= loop
->safelen
;
268 if (STMT_VINFO_GATHER_P (stmtinfo_a
)
269 || STMT_VINFO_GATHER_P (stmtinfo_b
))
271 if (dump_enabled_p ())
273 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
274 "versioning for alias not supported for: "
275 "can't determine dependence between ");
276 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
278 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
279 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
281 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
286 if (dump_enabled_p ())
288 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
289 "versioning for alias required: "
290 "can't determine dependence between ");
291 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
293 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
294 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
296 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
299 /* Add to list of ddrs that need to be tested at run-time. */
300 return !vect_mark_for_runtime_alias_test (ddr
, loop_vinfo
);
303 /* Known data dependence. */
304 if (DDR_NUM_DIST_VECTS (ddr
) == 0)
306 /* If user asserted safelen consecutive iterations can be
307 executed concurrently, assume independence. */
308 if (loop
->safelen
>= 2)
310 if (loop
->safelen
< *max_vf
)
311 *max_vf
= loop
->safelen
;
315 if (STMT_VINFO_GATHER_P (stmtinfo_a
)
316 || STMT_VINFO_GATHER_P (stmtinfo_b
))
318 if (dump_enabled_p ())
320 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
321 "versioning for alias not supported for: "
322 "bad dist vector for ");
323 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
325 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
326 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
328 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
333 if (dump_enabled_p ())
335 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
336 "versioning for alias required: "
337 "bad dist vector for ");
338 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, DR_REF (dra
));
339 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
340 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, DR_REF (drb
));
341 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
343 /* Add to list of ddrs that need to be tested at run-time. */
344 return !vect_mark_for_runtime_alias_test (ddr
, loop_vinfo
);
347 loop_depth
= index_in_loop_nest (loop
->num
, DDR_LOOP_NEST (ddr
));
348 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, dist_v
)
350 int dist
= dist_v
[loop_depth
];
352 if (dump_enabled_p ())
353 dump_printf_loc (MSG_NOTE
, vect_location
,
354 "dependence distance = %d.\n", dist
);
358 if (dump_enabled_p ())
360 dump_printf_loc (MSG_NOTE
, vect_location
,
361 "dependence distance == 0 between ");
362 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dra
));
363 dump_printf (MSG_NOTE
, " and ");
364 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (drb
));
365 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
368 /* When we perform grouped accesses and perform implicit CSE
369 by detecting equal accesses and doing disambiguation with
370 runtime alias tests like for
378 where we will end up loading { a[i], a[i+1] } once, make
379 sure that inserting group loads before the first load and
380 stores after the last store will do the right thing. */
381 if ((STMT_VINFO_GROUPED_ACCESS (stmtinfo_a
)
382 && GROUP_SAME_DR_STMT (stmtinfo_a
))
383 || (STMT_VINFO_GROUPED_ACCESS (stmtinfo_b
)
384 && GROUP_SAME_DR_STMT (stmtinfo_b
)))
387 earlier_stmt
= get_earlier_stmt (DR_STMT (dra
), DR_STMT (drb
));
389 (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt
))))
391 if (dump_enabled_p ())
392 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
393 "READ_WRITE dependence in interleaving."
402 if (dist
> 0 && DDR_REVERSED_P (ddr
))
404 /* If DDR_REVERSED_P the order of the data-refs in DDR was
405 reversed (to make distance vector positive), and the actual
406 distance is negative. */
407 if (dump_enabled_p ())
408 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
409 "dependence distance negative.\n");
414 && abs (dist
) < *max_vf
)
416 /* The dependence distance requires reduction of the maximal
417 vectorization factor. */
418 *max_vf
= abs (dist
);
419 if (dump_enabled_p ())
420 dump_printf_loc (MSG_NOTE
, vect_location
,
421 "adjusting maximal vectorization factor to %i\n",
425 if (abs (dist
) >= *max_vf
)
427 /* Dependence distance does not create dependence, as far as
428 vectorization is concerned, in this case. */
429 if (dump_enabled_p ())
430 dump_printf_loc (MSG_NOTE
, vect_location
,
431 "dependence distance >= VF.\n");
435 if (dump_enabled_p ())
437 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
438 "not vectorized, possible dependence "
439 "between data-refs ");
440 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dra
));
441 dump_printf (MSG_NOTE
, " and ");
442 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (drb
));
443 dump_printf (MSG_NOTE
, "\n");
452 /* Function vect_analyze_data_ref_dependences.
454 Examine all the data references in the loop, and make sure there do not
455 exist any data dependences between them. Set *MAX_VF according to
456 the maximum vectorization factor the data dependences allow. */
459 vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo
, int *max_vf
)
462 struct data_dependence_relation
*ddr
;
464 if (dump_enabled_p ())
465 dump_printf_loc (MSG_NOTE
, vect_location
,
466 "=== vect_analyze_data_ref_dependences ===\n");
468 if (!compute_all_dependences (LOOP_VINFO_DATAREFS (loop_vinfo
),
469 &LOOP_VINFO_DDRS (loop_vinfo
),
470 LOOP_VINFO_LOOP_NEST (loop_vinfo
), true))
473 FOR_EACH_VEC_ELT (LOOP_VINFO_DDRS (loop_vinfo
), i
, ddr
)
474 if (vect_analyze_data_ref_dependence (ddr
, loop_vinfo
, max_vf
))
481 /* Function vect_slp_analyze_data_ref_dependence.
483 Return TRUE if there (might) exist a dependence between a memory-reference
484 DRA and a memory-reference DRB. When versioning for alias may check a
485 dependence at run-time, return FALSE. Adjust *MAX_VF according to
486 the data dependence. */
489 vect_slp_analyze_data_ref_dependence (struct data_dependence_relation
*ddr
)
491 struct data_reference
*dra
= DDR_A (ddr
);
492 struct data_reference
*drb
= DDR_B (ddr
);
494 /* We need to check dependences of statements marked as unvectorizable
495 as well, they still can prohibit vectorization. */
497 /* Independent data accesses. */
498 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
504 /* Read-read is OK. */
505 if (DR_IS_READ (dra
) && DR_IS_READ (drb
))
508 /* If dra and drb are part of the same interleaving chain consider
510 if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (DR_STMT (dra
)))
511 && (GROUP_FIRST_ELEMENT (vinfo_for_stmt (DR_STMT (dra
)))
512 == GROUP_FIRST_ELEMENT (vinfo_for_stmt (DR_STMT (drb
)))))
515 /* Unknown data dependence. */
516 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
520 if (dump_enabled_p ())
522 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
523 "can't determine dependence between ");
524 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, DR_REF (dra
));
525 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
526 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, DR_REF (drb
));
527 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
530 /* We do not vectorize basic blocks with write-write dependencies. */
531 if (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))
534 /* Check that it's not a load-after-store dependence. */
535 earlier_stmt
= get_earlier_stmt (DR_STMT (dra
), DR_STMT (drb
));
536 if (DR_IS_WRITE (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt
))))
542 if (dump_enabled_p ())
544 dump_printf_loc (MSG_NOTE
, vect_location
,
545 "determined dependence between ");
546 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dra
));
547 dump_printf (MSG_NOTE
, " and ");
548 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (drb
));
549 dump_printf (MSG_NOTE
, "\n");
552 /* Do not vectorize basic blocks with write-write dependences. */
553 if (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))
556 /* Check dependence between DRA and DRB for basic block vectorization.
557 If the accesses share same bases and offsets, we can compare their initial
558 constant offsets to decide whether they differ or not. In case of a read-
559 write dependence we check that the load is before the store to ensure that
560 vectorization will not change the order of the accesses. */
562 HOST_WIDE_INT type_size_a
, type_size_b
, init_a
, init_b
;
565 /* Check that the data-refs have same bases and offsets. If not, we can't
566 determine if they are dependent. */
567 if (!operand_equal_p (DR_BASE_ADDRESS (dra
), DR_BASE_ADDRESS (drb
), 0)
568 || !dr_equal_offsets_p (dra
, drb
))
571 /* Check the types. */
572 type_size_a
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra
))));
573 type_size_b
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb
))));
575 if (type_size_a
!= type_size_b
576 || !types_compatible_p (TREE_TYPE (DR_REF (dra
)),
577 TREE_TYPE (DR_REF (drb
))))
580 init_a
= TREE_INT_CST_LOW (DR_INIT (dra
));
581 init_b
= TREE_INT_CST_LOW (DR_INIT (drb
));
583 /* Two different locations - no dependence. */
584 if (init_a
!= init_b
)
587 /* We have a read-write dependence. Check that the load is before the store.
588 When we vectorize basic blocks, vector load can be only before
589 corresponding scalar load, and vector store can be only after its
590 corresponding scalar store. So the order of the acceses is preserved in
591 case the load is before the store. */
592 earlier_stmt
= get_earlier_stmt (DR_STMT (dra
), DR_STMT (drb
));
593 if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt
))))
600 /* Function vect_analyze_data_ref_dependences.
602 Examine all the data references in the basic-block, and make sure there
603 do not exist any data dependences between them. Set *MAX_VF according to
604 the maximum vectorization factor the data dependences allow. */
607 vect_slp_analyze_data_ref_dependences (bb_vec_info bb_vinfo
)
609 struct data_dependence_relation
*ddr
;
612 if (dump_enabled_p ())
613 dump_printf_loc (MSG_NOTE
, vect_location
,
614 "=== vect_slp_analyze_data_ref_dependences ===\n");
616 if (!compute_all_dependences (BB_VINFO_DATAREFS (bb_vinfo
),
617 &BB_VINFO_DDRS (bb_vinfo
),
621 FOR_EACH_VEC_ELT (BB_VINFO_DDRS (bb_vinfo
), i
, ddr
)
622 if (vect_slp_analyze_data_ref_dependence (ddr
))
629 /* Function vect_compute_data_ref_alignment
631 Compute the misalignment of the data reference DR.
634 1. If during the misalignment computation it is found that the data reference
635 cannot be vectorized then false is returned.
636 2. DR_MISALIGNMENT (DR) is defined.
638 FOR NOW: No analysis is actually performed. Misalignment is calculated
639 only for trivial cases. TODO. */
642 vect_compute_data_ref_alignment (struct data_reference
*dr
)
644 gimple stmt
= DR_STMT (dr
);
645 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
646 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
647 struct loop
*loop
= NULL
;
648 tree ref
= DR_REF (dr
);
650 tree base
, base_addr
;
653 tree aligned_to
, alignment
;
655 if (dump_enabled_p ())
656 dump_printf_loc (MSG_NOTE
, vect_location
,
657 "vect_compute_data_ref_alignment:\n");
660 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
662 /* Initialize misalignment to unknown. */
663 SET_DR_MISALIGNMENT (dr
, -1);
665 /* Strided loads perform only component accesses, misalignment information
666 is irrelevant for them. */
667 if (STMT_VINFO_STRIDE_LOAD_P (stmt_info
))
670 misalign
= DR_INIT (dr
);
671 aligned_to
= DR_ALIGNED_TO (dr
);
672 base_addr
= DR_BASE_ADDRESS (dr
);
673 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
675 /* In case the dataref is in an inner-loop of the loop that is being
676 vectorized (LOOP), we use the base and misalignment information
677 relative to the outer-loop (LOOP). This is ok only if the misalignment
678 stays the same throughout the execution of the inner-loop, which is why
679 we have to check that the stride of the dataref in the inner-loop evenly
680 divides by the vector size. */
681 if (loop
&& nested_in_vect_loop_p (loop
, stmt
))
683 tree step
= DR_STEP (dr
);
684 HOST_WIDE_INT dr_step
= TREE_INT_CST_LOW (step
);
686 if (dr_step
% GET_MODE_SIZE (TYPE_MODE (vectype
)) == 0)
688 if (dump_enabled_p ())
689 dump_printf_loc (MSG_NOTE
, vect_location
,
690 "inner step divides the vector-size.\n");
691 misalign
= STMT_VINFO_DR_INIT (stmt_info
);
692 aligned_to
= STMT_VINFO_DR_ALIGNED_TO (stmt_info
);
693 base_addr
= STMT_VINFO_DR_BASE_ADDRESS (stmt_info
);
697 if (dump_enabled_p ())
698 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
699 "inner step doesn't divide the vector-size.\n");
700 misalign
= NULL_TREE
;
704 /* Similarly, if we're doing basic-block vectorization, we can only use
705 base and misalignment information relative to an innermost loop if the
706 misalignment stays the same throughout the execution of the loop.
707 As above, this is the case if the stride of the dataref evenly divides
708 by the vector size. */
711 tree step
= DR_STEP (dr
);
712 HOST_WIDE_INT dr_step
= TREE_INT_CST_LOW (step
);
714 if (dr_step
% GET_MODE_SIZE (TYPE_MODE (vectype
)) != 0)
716 if (dump_enabled_p ())
717 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
718 "SLP: step doesn't divide the vector-size.\n");
719 misalign
= NULL_TREE
;
723 base
= build_fold_indirect_ref (base_addr
);
724 alignment
= ssize_int (TYPE_ALIGN (vectype
)/BITS_PER_UNIT
);
726 if ((aligned_to
&& tree_int_cst_compare (aligned_to
, alignment
) < 0)
729 if (dump_enabled_p ())
731 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
732 "Unknown alignment for access: ");
733 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, base
);
734 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
740 && tree_int_cst_compare (ssize_int (DECL_ALIGN_UNIT (base
)),
742 || (TREE_CODE (base_addr
) == SSA_NAME
743 && tree_int_cst_compare (ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (
744 TREE_TYPE (base_addr
)))),
746 || (get_pointer_alignment (base_addr
) >= TYPE_ALIGN (vectype
)))
749 base_aligned
= false;
753 /* Do not change the alignment of global variables here if
754 flag_section_anchors is enabled as we already generated
755 RTL for other functions. Most global variables should
756 have been aligned during the IPA increase_alignment pass. */
757 if (!vect_can_force_dr_alignment_p (base
, TYPE_ALIGN (vectype
))
758 || (TREE_STATIC (base
) && flag_section_anchors
))
760 if (dump_enabled_p ())
762 dump_printf_loc (MSG_NOTE
, vect_location
,
763 "can't force alignment of ref: ");
764 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, ref
);
765 dump_printf (MSG_NOTE
, "\n");
770 /* Force the alignment of the decl.
771 NOTE: This is the only change to the code we make during
772 the analysis phase, before deciding to vectorize the loop. */
773 if (dump_enabled_p ())
775 dump_printf_loc (MSG_NOTE
, vect_location
, "force alignment of ");
776 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, ref
);
777 dump_printf (MSG_NOTE
, "\n");
780 ((dataref_aux
*)dr
->aux
)->base_decl
= base
;
781 ((dataref_aux
*)dr
->aux
)->base_misaligned
= true;
784 /* If this is a backward running DR then first access in the larger
785 vectype actually is N-1 elements before the address in the DR.
786 Adjust misalign accordingly. */
787 if (tree_int_cst_compare (DR_STEP (dr
), size_zero_node
) < 0)
789 tree offset
= ssize_int (TYPE_VECTOR_SUBPARTS (vectype
) - 1);
790 /* DR_STEP(dr) is the same as -TYPE_SIZE of the scalar type,
791 otherwise we wouldn't be here. */
792 offset
= fold_build2 (MULT_EXPR
, ssizetype
, offset
, DR_STEP (dr
));
793 /* PLUS because DR_STEP was negative. */
794 misalign
= size_binop (PLUS_EXPR
, misalign
, offset
);
797 /* Modulo alignment. */
798 misalign
= size_binop (FLOOR_MOD_EXPR
, misalign
, alignment
);
800 if (!host_integerp (misalign
, 1))
802 /* Negative or overflowed misalignment value. */
803 if (dump_enabled_p ())
804 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
805 "unexpected misalign value\n");
809 SET_DR_MISALIGNMENT (dr
, TREE_INT_CST_LOW (misalign
));
811 if (dump_enabled_p ())
813 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
814 "misalign = %d bytes of ref ", DR_MISALIGNMENT (dr
));
815 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, ref
);
816 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
823 /* Function vect_compute_data_refs_alignment
825 Compute the misalignment of data references in the loop.
826 Return FALSE if a data reference is found that cannot be vectorized. */
829 vect_compute_data_refs_alignment (loop_vec_info loop_vinfo
,
830 bb_vec_info bb_vinfo
)
832 vec
<data_reference_p
> datarefs
;
833 struct data_reference
*dr
;
837 datarefs
= LOOP_VINFO_DATAREFS (loop_vinfo
);
839 datarefs
= BB_VINFO_DATAREFS (bb_vinfo
);
841 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
842 if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr
)))
843 && !vect_compute_data_ref_alignment (dr
))
847 /* Mark unsupported statement as unvectorizable. */
848 STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr
))) = false;
859 /* Function vect_update_misalignment_for_peel
861 DR - the data reference whose misalignment is to be adjusted.
862 DR_PEEL - the data reference whose misalignment is being made
863 zero in the vector loop by the peel.
864 NPEEL - the number of iterations in the peel loop if the misalignment
865 of DR_PEEL is known at compile time. */
868 vect_update_misalignment_for_peel (struct data_reference
*dr
,
869 struct data_reference
*dr_peel
, int npeel
)
872 vec
<dr_p
> same_align_drs
;
873 struct data_reference
*current_dr
;
874 int dr_size
= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr
))));
875 int dr_peel_size
= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr_peel
))));
876 stmt_vec_info stmt_info
= vinfo_for_stmt (DR_STMT (dr
));
877 stmt_vec_info peel_stmt_info
= vinfo_for_stmt (DR_STMT (dr_peel
));
879 /* For interleaved data accesses the step in the loop must be multiplied by
880 the size of the interleaving group. */
881 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
882 dr_size
*= GROUP_SIZE (vinfo_for_stmt (GROUP_FIRST_ELEMENT (stmt_info
)));
883 if (STMT_VINFO_GROUPED_ACCESS (peel_stmt_info
))
884 dr_peel_size
*= GROUP_SIZE (peel_stmt_info
);
886 /* It can be assumed that the data refs with the same alignment as dr_peel
887 are aligned in the vector loop. */
889 = STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (DR_STMT (dr_peel
)));
890 FOR_EACH_VEC_ELT (same_align_drs
, i
, current_dr
)
892 if (current_dr
!= dr
)
894 gcc_assert (DR_MISALIGNMENT (dr
) / dr_size
==
895 DR_MISALIGNMENT (dr_peel
) / dr_peel_size
);
896 SET_DR_MISALIGNMENT (dr
, 0);
900 if (known_alignment_for_access_p (dr
)
901 && known_alignment_for_access_p (dr_peel
))
903 bool negative
= tree_int_cst_compare (DR_STEP (dr
), size_zero_node
) < 0;
904 int misal
= DR_MISALIGNMENT (dr
);
905 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
906 misal
+= negative
? -npeel
* dr_size
: npeel
* dr_size
;
907 misal
&= (TYPE_ALIGN (vectype
) / BITS_PER_UNIT
) - 1;
908 SET_DR_MISALIGNMENT (dr
, misal
);
912 if (dump_enabled_p ())
913 dump_printf_loc (MSG_NOTE
, vect_location
, "Setting misalignment to -1.\n");
914 SET_DR_MISALIGNMENT (dr
, -1);
918 /* Function vect_verify_datarefs_alignment
920 Return TRUE if all data references in the loop can be
921 handled with respect to alignment. */
924 vect_verify_datarefs_alignment (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
)
926 vec
<data_reference_p
> datarefs
;
927 struct data_reference
*dr
;
928 enum dr_alignment_support supportable_dr_alignment
;
932 datarefs
= LOOP_VINFO_DATAREFS (loop_vinfo
);
934 datarefs
= BB_VINFO_DATAREFS (bb_vinfo
);
936 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
938 gimple stmt
= DR_STMT (dr
);
939 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
941 if (!STMT_VINFO_RELEVANT_P (stmt_info
))
944 /* For interleaving, only the alignment of the first access matters.
945 Skip statements marked as not vectorizable. */
946 if ((STMT_VINFO_GROUPED_ACCESS (stmt_info
)
947 && GROUP_FIRST_ELEMENT (stmt_info
) != stmt
)
948 || !STMT_VINFO_VECTORIZABLE (stmt_info
))
951 /* Strided loads perform only component accesses, alignment is
952 irrelevant for them. */
953 if (STMT_VINFO_STRIDE_LOAD_P (stmt_info
))
956 supportable_dr_alignment
= vect_supportable_dr_alignment (dr
, false);
957 if (!supportable_dr_alignment
)
959 if (dump_enabled_p ())
962 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
963 "not vectorized: unsupported unaligned load.");
965 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
966 "not vectorized: unsupported unaligned "
969 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
971 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
975 if (supportable_dr_alignment
!= dr_aligned
&& dump_enabled_p ())
976 dump_printf_loc (MSG_NOTE
, vect_location
,
977 "Vectorizing an unaligned access.\n");
982 /* Given an memory reference EXP return whether its alignment is less
986 not_size_aligned (tree exp
)
988 if (!host_integerp (TYPE_SIZE (TREE_TYPE (exp
)), 1))
991 return (TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp
)))
992 > get_object_alignment (exp
));
995 /* Function vector_alignment_reachable_p
997 Return true if vector alignment for DR is reachable by peeling
998 a few loop iterations. Return false otherwise. */
1001 vector_alignment_reachable_p (struct data_reference
*dr
)
1003 gimple stmt
= DR_STMT (dr
);
1004 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1005 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
1007 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1009 /* For interleaved access we peel only if number of iterations in
1010 the prolog loop ({VF - misalignment}), is a multiple of the
1011 number of the interleaved accesses. */
1012 int elem_size
, mis_in_elements
;
1013 int nelements
= TYPE_VECTOR_SUBPARTS (vectype
);
1015 /* FORNOW: handle only known alignment. */
1016 if (!known_alignment_for_access_p (dr
))
1019 elem_size
= GET_MODE_SIZE (TYPE_MODE (vectype
)) / nelements
;
1020 mis_in_elements
= DR_MISALIGNMENT (dr
) / elem_size
;
1022 if ((nelements
- mis_in_elements
) % GROUP_SIZE (stmt_info
))
1026 /* If misalignment is known at the compile time then allow peeling
1027 only if natural alignment is reachable through peeling. */
1028 if (known_alignment_for_access_p (dr
) && !aligned_access_p (dr
))
1030 HOST_WIDE_INT elmsize
=
1031 int_cst_value (TYPE_SIZE_UNIT (TREE_TYPE (vectype
)));
1032 if (dump_enabled_p ())
1034 dump_printf_loc (MSG_NOTE
, vect_location
,
1035 "data size =" HOST_WIDE_INT_PRINT_DEC
, elmsize
);
1036 dump_printf (MSG_NOTE
,
1037 ". misalignment = %d.\n", DR_MISALIGNMENT (dr
));
1039 if (DR_MISALIGNMENT (dr
) % elmsize
)
1041 if (dump_enabled_p ())
1042 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1043 "data size does not divide the misalignment.\n");
1048 if (!known_alignment_for_access_p (dr
))
1050 tree type
= TREE_TYPE (DR_REF (dr
));
1051 bool is_packed
= not_size_aligned (DR_REF (dr
));
1052 if (dump_enabled_p ())
1053 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1054 "Unknown misalignment, is_packed = %d\n",is_packed
);
1055 if ((TYPE_USER_ALIGN (type
) && !is_packed
)
1056 || targetm
.vectorize
.vector_alignment_reachable (type
, is_packed
))
1066 /* Calculate the cost of the memory access represented by DR. */
1069 vect_get_data_access_cost (struct data_reference
*dr
,
1070 unsigned int *inside_cost
,
1071 unsigned int *outside_cost
,
1072 stmt_vector_for_cost
*body_cost_vec
)
1074 gimple stmt
= DR_STMT (dr
);
1075 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1076 int nunits
= TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
1077 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
1078 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1079 int ncopies
= vf
/ nunits
;
1081 if (DR_IS_READ (dr
))
1082 vect_get_load_cost (dr
, ncopies
, true, inside_cost
, outside_cost
,
1083 NULL
, body_cost_vec
, false);
1085 vect_get_store_cost (dr
, ncopies
, inside_cost
, body_cost_vec
);
1087 if (dump_enabled_p ())
1088 dump_printf_loc (MSG_NOTE
, vect_location
,
1089 "vect_get_data_access_cost: inside_cost = %d, "
1090 "outside_cost = %d.\n", *inside_cost
, *outside_cost
);
1094 /* Insert DR into peeling hash table with NPEEL as key. */
1097 vect_peeling_hash_insert (loop_vec_info loop_vinfo
, struct data_reference
*dr
,
1100 struct _vect_peel_info elem
, *slot
;
1101 _vect_peel_info
**new_slot
;
1102 bool supportable_dr_alignment
= vect_supportable_dr_alignment (dr
, true);
1105 slot
= LOOP_VINFO_PEELING_HTAB (loop_vinfo
).find (&elem
);
1110 slot
= XNEW (struct _vect_peel_info
);
1111 slot
->npeel
= npeel
;
1114 new_slot
= LOOP_VINFO_PEELING_HTAB (loop_vinfo
).find_slot (slot
, INSERT
);
1118 if (!supportable_dr_alignment
&& !flag_vect_cost_model
)
1119 slot
->count
+= VECT_MAX_COST
;
1123 /* Traverse peeling hash table to find peeling option that aligns maximum
1124 number of data accesses. */
1127 vect_peeling_hash_get_most_frequent (_vect_peel_info
**slot
,
1128 _vect_peel_extended_info
*max
)
1130 vect_peel_info elem
= *slot
;
1132 if (elem
->count
> max
->peel_info
.count
1133 || (elem
->count
== max
->peel_info
.count
1134 && max
->peel_info
.npeel
> elem
->npeel
))
1136 max
->peel_info
.npeel
= elem
->npeel
;
1137 max
->peel_info
.count
= elem
->count
;
1138 max
->peel_info
.dr
= elem
->dr
;
1145 /* Traverse peeling hash table and calculate cost for each peeling option.
1146 Find the one with the lowest cost. */
1149 vect_peeling_hash_get_lowest_cost (_vect_peel_info
**slot
,
1150 _vect_peel_extended_info
*min
)
1152 vect_peel_info elem
= *slot
;
1153 int save_misalignment
, dummy
;
1154 unsigned int inside_cost
= 0, outside_cost
= 0, i
;
1155 gimple stmt
= DR_STMT (elem
->dr
);
1156 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1157 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
1158 vec
<data_reference_p
> datarefs
= LOOP_VINFO_DATAREFS (loop_vinfo
);
1159 struct data_reference
*dr
;
1160 stmt_vector_for_cost prologue_cost_vec
, body_cost_vec
, epilogue_cost_vec
;
1161 int single_iter_cost
;
1163 prologue_cost_vec
.create (2);
1164 body_cost_vec
.create (2);
1165 epilogue_cost_vec
.create (2);
1167 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
1169 stmt
= DR_STMT (dr
);
1170 stmt_info
= vinfo_for_stmt (stmt
);
1171 /* For interleaving, only the alignment of the first access
1173 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
)
1174 && GROUP_FIRST_ELEMENT (stmt_info
) != stmt
)
1177 save_misalignment
= DR_MISALIGNMENT (dr
);
1178 vect_update_misalignment_for_peel (dr
, elem
->dr
, elem
->npeel
);
1179 vect_get_data_access_cost (dr
, &inside_cost
, &outside_cost
,
1181 SET_DR_MISALIGNMENT (dr
, save_misalignment
);
1184 single_iter_cost
= vect_get_single_scalar_iteration_cost (loop_vinfo
);
1185 outside_cost
+= vect_get_known_peeling_cost (loop_vinfo
, elem
->npeel
,
1186 &dummy
, single_iter_cost
,
1188 &epilogue_cost_vec
);
1190 /* Prologue and epilogue costs are added to the target model later.
1191 These costs depend only on the scalar iteration cost, the
1192 number of peeling iterations finally chosen, and the number of
1193 misaligned statements. So discard the information found here. */
1194 prologue_cost_vec
.release ();
1195 epilogue_cost_vec
.release ();
1197 if (inside_cost
< min
->inside_cost
1198 || (inside_cost
== min
->inside_cost
&& outside_cost
< min
->outside_cost
))
1200 min
->inside_cost
= inside_cost
;
1201 min
->outside_cost
= outside_cost
;
1202 min
->body_cost_vec
.release ();
1203 min
->body_cost_vec
= body_cost_vec
;
1204 min
->peel_info
.dr
= elem
->dr
;
1205 min
->peel_info
.npeel
= elem
->npeel
;
1208 body_cost_vec
.release ();
1214 /* Choose best peeling option by traversing peeling hash table and either
1215 choosing an option with the lowest cost (if cost model is enabled) or the
1216 option that aligns as many accesses as possible. */
1218 static struct data_reference
*
1219 vect_peeling_hash_choose_best_peeling (loop_vec_info loop_vinfo
,
1220 unsigned int *npeel
,
1221 stmt_vector_for_cost
*body_cost_vec
)
1223 struct _vect_peel_extended_info res
;
1225 res
.peel_info
.dr
= NULL
;
1226 res
.body_cost_vec
= stmt_vector_for_cost();
1228 if (flag_vect_cost_model
)
1230 res
.inside_cost
= INT_MAX
;
1231 res
.outside_cost
= INT_MAX
;
1232 LOOP_VINFO_PEELING_HTAB (loop_vinfo
)
1233 .traverse
<_vect_peel_extended_info
*,
1234 vect_peeling_hash_get_lowest_cost
> (&res
);
1238 res
.peel_info
.count
= 0;
1239 LOOP_VINFO_PEELING_HTAB (loop_vinfo
)
1240 .traverse
<_vect_peel_extended_info
*,
1241 vect_peeling_hash_get_most_frequent
> (&res
);
1244 *npeel
= res
.peel_info
.npeel
;
1245 *body_cost_vec
= res
.body_cost_vec
;
1246 return res
.peel_info
.dr
;
1250 /* Function vect_enhance_data_refs_alignment
1252 This pass will use loop versioning and loop peeling in order to enhance
1253 the alignment of data references in the loop.
1255 FOR NOW: we assume that whatever versioning/peeling takes place, only the
1256 original loop is to be vectorized. Any other loops that are created by
1257 the transformations performed in this pass - are not supposed to be
1258 vectorized. This restriction will be relaxed.
1260 This pass will require a cost model to guide it whether to apply peeling
1261 or versioning or a combination of the two. For example, the scheme that
1262 intel uses when given a loop with several memory accesses, is as follows:
1263 choose one memory access ('p') which alignment you want to force by doing
1264 peeling. Then, either (1) generate a loop in which 'p' is aligned and all
1265 other accesses are not necessarily aligned, or (2) use loop versioning to
1266 generate one loop in which all accesses are aligned, and another loop in
1267 which only 'p' is necessarily aligned.
1269 ("Automatic Intra-Register Vectorization for the Intel Architecture",
1270 Aart J.C. Bik, Milind Girkar, Paul M. Grey and Ximmin Tian, International
1271 Journal of Parallel Programming, Vol. 30, No. 2, April 2002.)
1273 Devising a cost model is the most critical aspect of this work. It will
1274 guide us on which access to peel for, whether to use loop versioning, how
1275 many versions to create, etc. The cost model will probably consist of
1276 generic considerations as well as target specific considerations (on
1277 powerpc for example, misaligned stores are more painful than misaligned
1280 Here are the general steps involved in alignment enhancements:
1282 -- original loop, before alignment analysis:
1283 for (i=0; i<N; i++){
1284 x = q[i]; # DR_MISALIGNMENT(q) = unknown
1285 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1288 -- After vect_compute_data_refs_alignment:
1289 for (i=0; i<N; i++){
1290 x = q[i]; # DR_MISALIGNMENT(q) = 3
1291 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1294 -- Possibility 1: we do loop versioning:
1296 for (i=0; i<N; i++){ # loop 1A
1297 x = q[i]; # DR_MISALIGNMENT(q) = 3
1298 p[i] = y; # DR_MISALIGNMENT(p) = 0
1302 for (i=0; i<N; i++){ # loop 1B
1303 x = q[i]; # DR_MISALIGNMENT(q) = 3
1304 p[i] = y; # DR_MISALIGNMENT(p) = unaligned
1308 -- Possibility 2: we do loop peeling:
1309 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
1313 for (i = 3; i < N; i++){ # loop 2A
1314 x = q[i]; # DR_MISALIGNMENT(q) = 0
1315 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1318 -- Possibility 3: combination of loop peeling and versioning:
1319 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
1324 for (i = 3; i<N; i++){ # loop 3A
1325 x = q[i]; # DR_MISALIGNMENT(q) = 0
1326 p[i] = y; # DR_MISALIGNMENT(p) = 0
1330 for (i = 3; i<N; i++){ # loop 3B
1331 x = q[i]; # DR_MISALIGNMENT(q) = 0
1332 p[i] = y; # DR_MISALIGNMENT(p) = unaligned
1336 These loops are later passed to loop_transform to be vectorized. The
1337 vectorizer will use the alignment information to guide the transformation
1338 (whether to generate regular loads/stores, or with special handling for
1342 vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo
)
1344 vec
<data_reference_p
> datarefs
= LOOP_VINFO_DATAREFS (loop_vinfo
);
1345 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1346 enum dr_alignment_support supportable_dr_alignment
;
1347 struct data_reference
*dr0
= NULL
, *first_store
= NULL
;
1348 struct data_reference
*dr
;
1350 bool do_peeling
= false;
1351 bool do_versioning
= false;
1354 stmt_vec_info stmt_info
;
1355 unsigned int npeel
= 0;
1356 bool all_misalignments_unknown
= true;
1357 unsigned int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1358 unsigned possible_npeel_number
= 1;
1360 unsigned int nelements
, mis
, same_align_drs_max
= 0;
1361 stmt_vector_for_cost body_cost_vec
= stmt_vector_for_cost();
1363 if (dump_enabled_p ())
1364 dump_printf_loc (MSG_NOTE
, vect_location
,
1365 "=== vect_enhance_data_refs_alignment ===\n");
1367 /* While cost model enhancements are expected in the future, the high level
1368 view of the code at this time is as follows:
1370 A) If there is a misaligned access then see if peeling to align
1371 this access can make all data references satisfy
1372 vect_supportable_dr_alignment. If so, update data structures
1373 as needed and return true.
1375 B) If peeling wasn't possible and there is a data reference with an
1376 unknown misalignment that does not satisfy vect_supportable_dr_alignment
1377 then see if loop versioning checks can be used to make all data
1378 references satisfy vect_supportable_dr_alignment. If so, update
1379 data structures as needed and return true.
1381 C) If neither peeling nor versioning were successful then return false if
1382 any data reference does not satisfy vect_supportable_dr_alignment.
1384 D) Return true (all data references satisfy vect_supportable_dr_alignment).
1386 Note, Possibility 3 above (which is peeling and versioning together) is not
1387 being done at this time. */
1389 /* (1) Peeling to force alignment. */
1391 /* (1.1) Decide whether to perform peeling, and how many iterations to peel:
1393 + How many accesses will become aligned due to the peeling
1394 - How many accesses will become unaligned due to the peeling,
1395 and the cost of misaligned accesses.
1396 - The cost of peeling (the extra runtime checks, the increase
1399 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
1401 stmt
= DR_STMT (dr
);
1402 stmt_info
= vinfo_for_stmt (stmt
);
1404 if (!STMT_VINFO_RELEVANT_P (stmt_info
))
1407 /* For interleaving, only the alignment of the first access
1409 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
)
1410 && GROUP_FIRST_ELEMENT (stmt_info
) != stmt
)
1413 /* For invariant accesses there is nothing to enhance. */
1414 if (integer_zerop (DR_STEP (dr
)))
1417 /* Strided loads perform only component accesses, alignment is
1418 irrelevant for them. */
1419 if (STMT_VINFO_STRIDE_LOAD_P (stmt_info
))
1422 supportable_dr_alignment
= vect_supportable_dr_alignment (dr
, true);
1423 do_peeling
= vector_alignment_reachable_p (dr
);
1426 if (known_alignment_for_access_p (dr
))
1428 unsigned int npeel_tmp
;
1429 bool negative
= tree_int_cst_compare (DR_STEP (dr
),
1430 size_zero_node
) < 0;
1432 /* Save info about DR in the hash table. */
1433 if (!LOOP_VINFO_PEELING_HTAB (loop_vinfo
).is_created ())
1434 LOOP_VINFO_PEELING_HTAB (loop_vinfo
).create (1);
1436 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
1437 nelements
= TYPE_VECTOR_SUBPARTS (vectype
);
1438 mis
= DR_MISALIGNMENT (dr
) / GET_MODE_SIZE (TYPE_MODE (
1439 TREE_TYPE (DR_REF (dr
))));
1440 npeel_tmp
= (negative
1441 ? (mis
- nelements
) : (nelements
- mis
))
1444 /* For multiple types, it is possible that the bigger type access
1445 will have more than one peeling option. E.g., a loop with two
1446 types: one of size (vector size / 4), and the other one of
1447 size (vector size / 8). Vectorization factor will 8. If both
1448 access are misaligned by 3, the first one needs one scalar
1449 iteration to be aligned, and the second one needs 5. But the
1450 the first one will be aligned also by peeling 5 scalar
1451 iterations, and in that case both accesses will be aligned.
1452 Hence, except for the immediate peeling amount, we also want
1453 to try to add full vector size, while we don't exceed
1454 vectorization factor.
1455 We do this automtically for cost model, since we calculate cost
1456 for every peeling option. */
1457 if (!flag_vect_cost_model
)
1458 possible_npeel_number
= vf
/nelements
;
1460 /* Handle the aligned case. We may decide to align some other
1461 access, making DR unaligned. */
1462 if (DR_MISALIGNMENT (dr
) == 0)
1465 if (!flag_vect_cost_model
)
1466 possible_npeel_number
++;
1469 for (j
= 0; j
< possible_npeel_number
; j
++)
1471 gcc_assert (npeel_tmp
<= vf
);
1472 vect_peeling_hash_insert (loop_vinfo
, dr
, npeel_tmp
);
1473 npeel_tmp
+= nelements
;
1476 all_misalignments_unknown
= false;
1477 /* Data-ref that was chosen for the case that all the
1478 misalignments are unknown is not relevant anymore, since we
1479 have a data-ref with known alignment. */
1484 /* If we don't know any misalignment values, we prefer
1485 peeling for data-ref that has the maximum number of data-refs
1486 with the same alignment, unless the target prefers to align
1487 stores over load. */
1488 if (all_misalignments_unknown
)
1490 unsigned same_align_drs
1491 = STMT_VINFO_SAME_ALIGN_REFS (stmt_info
).length ();
1493 || same_align_drs_max
< same_align_drs
)
1495 same_align_drs_max
= same_align_drs
;
1498 /* For data-refs with the same number of related
1499 accesses prefer the one where the misalign
1500 computation will be invariant in the outermost loop. */
1501 else if (same_align_drs_max
== same_align_drs
)
1503 struct loop
*ivloop0
, *ivloop
;
1504 ivloop0
= outermost_invariant_loop_for_expr
1505 (loop
, DR_BASE_ADDRESS (dr0
));
1506 ivloop
= outermost_invariant_loop_for_expr
1507 (loop
, DR_BASE_ADDRESS (dr
));
1508 if ((ivloop
&& !ivloop0
)
1509 || (ivloop
&& ivloop0
1510 && flow_loop_nested_p (ivloop
, ivloop0
)))
1514 if (!first_store
&& DR_IS_WRITE (dr
))
1518 /* If there are both known and unknown misaligned accesses in the
1519 loop, we choose peeling amount according to the known
1521 if (!supportable_dr_alignment
)
1524 if (!first_store
&& DR_IS_WRITE (dr
))
1531 if (!aligned_access_p (dr
))
1533 if (dump_enabled_p ())
1534 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1535 "vector alignment may not be reachable\n");
1541 /* Check if we can possibly peel the loop. */
1542 if (!vect_can_advance_ivs_p (loop_vinfo
)
1543 || !slpeel_can_duplicate_loop_p (loop
, single_exit (loop
)))
1546 if (do_peeling
&& all_misalignments_unknown
1547 && vect_supportable_dr_alignment (dr0
, false))
1550 /* Check if the target requires to prefer stores over loads, i.e., if
1551 misaligned stores are more expensive than misaligned loads (taking
1552 drs with same alignment into account). */
1553 if (first_store
&& DR_IS_READ (dr0
))
1555 unsigned int load_inside_cost
= 0, load_outside_cost
= 0;
1556 unsigned int store_inside_cost
= 0, store_outside_cost
= 0;
1557 unsigned int load_inside_penalty
= 0, load_outside_penalty
= 0;
1558 unsigned int store_inside_penalty
= 0, store_outside_penalty
= 0;
1559 stmt_vector_for_cost dummy
;
1562 vect_get_data_access_cost (dr0
, &load_inside_cost
, &load_outside_cost
,
1564 vect_get_data_access_cost (first_store
, &store_inside_cost
,
1565 &store_outside_cost
, &dummy
);
1569 /* Calculate the penalty for leaving FIRST_STORE unaligned (by
1570 aligning the load DR0). */
1571 load_inside_penalty
= store_inside_cost
;
1572 load_outside_penalty
= store_outside_cost
;
1574 STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (
1575 DR_STMT (first_store
))).iterate (i
, &dr
);
1577 if (DR_IS_READ (dr
))
1579 load_inside_penalty
+= load_inside_cost
;
1580 load_outside_penalty
+= load_outside_cost
;
1584 load_inside_penalty
+= store_inside_cost
;
1585 load_outside_penalty
+= store_outside_cost
;
1588 /* Calculate the penalty for leaving DR0 unaligned (by
1589 aligning the FIRST_STORE). */
1590 store_inside_penalty
= load_inside_cost
;
1591 store_outside_penalty
= load_outside_cost
;
1593 STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (
1594 DR_STMT (dr0
))).iterate (i
, &dr
);
1596 if (DR_IS_READ (dr
))
1598 store_inside_penalty
+= load_inside_cost
;
1599 store_outside_penalty
+= load_outside_cost
;
1603 store_inside_penalty
+= store_inside_cost
;
1604 store_outside_penalty
+= store_outside_cost
;
1607 if (load_inside_penalty
> store_inside_penalty
1608 || (load_inside_penalty
== store_inside_penalty
1609 && load_outside_penalty
> store_outside_penalty
))
1613 /* In case there are only loads with different unknown misalignments, use
1614 peeling only if it may help to align other accesses in the loop. */
1616 && !STMT_VINFO_SAME_ALIGN_REFS (
1617 vinfo_for_stmt (DR_STMT (dr0
))).length ()
1618 && vect_supportable_dr_alignment (dr0
, false)
1619 != dr_unaligned_supported
)
1623 if (do_peeling
&& !dr0
)
1625 /* Peeling is possible, but there is no data access that is not supported
1626 unless aligned. So we try to choose the best possible peeling. */
1628 /* We should get here only if there are drs with known misalignment. */
1629 gcc_assert (!all_misalignments_unknown
);
1631 /* Choose the best peeling from the hash table. */
1632 dr0
= vect_peeling_hash_choose_best_peeling (loop_vinfo
, &npeel
,
1640 stmt
= DR_STMT (dr0
);
1641 stmt_info
= vinfo_for_stmt (stmt
);
1642 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
1643 nelements
= TYPE_VECTOR_SUBPARTS (vectype
);
1645 if (known_alignment_for_access_p (dr0
))
1647 bool negative
= tree_int_cst_compare (DR_STEP (dr0
),
1648 size_zero_node
) < 0;
1651 /* Since it's known at compile time, compute the number of
1652 iterations in the peeled loop (the peeling factor) for use in
1653 updating DR_MISALIGNMENT values. The peeling factor is the
1654 vectorization factor minus the misalignment as an element
1656 mis
= DR_MISALIGNMENT (dr0
);
1657 mis
/= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr0
))));
1658 npeel
= ((negative
? mis
- nelements
: nelements
- mis
)
1662 /* For interleaved data access every iteration accesses all the
1663 members of the group, therefore we divide the number of iterations
1664 by the group size. */
1665 stmt_info
= vinfo_for_stmt (DR_STMT (dr0
));
1666 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1667 npeel
/= GROUP_SIZE (stmt_info
);
1669 if (dump_enabled_p ())
1670 dump_printf_loc (MSG_NOTE
, vect_location
,
1671 "Try peeling by %d\n", npeel
);
1674 /* Ensure that all data refs can be vectorized after the peel. */
1675 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
1677 int save_misalignment
;
1682 stmt
= DR_STMT (dr
);
1683 stmt_info
= vinfo_for_stmt (stmt
);
1684 /* For interleaving, only the alignment of the first access
1686 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
)
1687 && GROUP_FIRST_ELEMENT (stmt_info
) != stmt
)
1690 /* Strided loads perform only component accesses, alignment is
1691 irrelevant for them. */
1692 if (STMT_VINFO_STRIDE_LOAD_P (stmt_info
))
1695 save_misalignment
= DR_MISALIGNMENT (dr
);
1696 vect_update_misalignment_for_peel (dr
, dr0
, npeel
);
1697 supportable_dr_alignment
= vect_supportable_dr_alignment (dr
, false);
1698 SET_DR_MISALIGNMENT (dr
, save_misalignment
);
1700 if (!supportable_dr_alignment
)
1707 if (do_peeling
&& known_alignment_for_access_p (dr0
) && npeel
== 0)
1709 stat
= vect_verify_datarefs_alignment (loop_vinfo
, NULL
);
1714 body_cost_vec
.release ();
1721 unsigned max_allowed_peel
1722 = PARAM_VALUE (PARAM_VECT_MAX_PEELING_FOR_ALIGNMENT
);
1723 if (max_allowed_peel
!= (unsigned)-1)
1725 unsigned max_peel
= npeel
;
1728 gimple dr_stmt
= DR_STMT (dr0
);
1729 stmt_vec_info vinfo
= vinfo_for_stmt (dr_stmt
);
1730 tree vtype
= STMT_VINFO_VECTYPE (vinfo
);
1731 max_peel
= TYPE_VECTOR_SUBPARTS (vtype
) - 1;
1733 if (max_peel
> max_allowed_peel
)
1736 if (dump_enabled_p ())
1737 dump_printf_loc (MSG_NOTE
, vect_location
,
1738 "Disable peeling, max peels reached: %d\n", max_peel
);
1745 stmt_info_for_cost
*si
;
1746 void *data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
1748 /* (1.2) Update the DR_MISALIGNMENT of each data reference DR_i.
1749 If the misalignment of DR_i is identical to that of dr0 then set
1750 DR_MISALIGNMENT (DR_i) to zero. If the misalignment of DR_i and
1751 dr0 are known at compile time then increment DR_MISALIGNMENT (DR_i)
1752 by the peeling factor times the element size of DR_i (MOD the
1753 vectorization factor times the size). Otherwise, the
1754 misalignment of DR_i must be set to unknown. */
1755 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
1757 vect_update_misalignment_for_peel (dr
, dr0
, npeel
);
1759 LOOP_VINFO_UNALIGNED_DR (loop_vinfo
) = dr0
;
1761 LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
) = npeel
;
1763 LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
) = DR_MISALIGNMENT (dr0
);
1764 SET_DR_MISALIGNMENT (dr0
, 0);
1765 if (dump_enabled_p ())
1767 dump_printf_loc (MSG_NOTE
, vect_location
,
1768 "Alignment of access forced using peeling.\n");
1769 dump_printf_loc (MSG_NOTE
, vect_location
,
1770 "Peeling for alignment will be applied.\n");
1772 /* We've delayed passing the inside-loop peeling costs to the
1773 target cost model until we were sure peeling would happen.
1775 if (body_cost_vec
.exists ())
1777 FOR_EACH_VEC_ELT (body_cost_vec
, i
, si
)
1779 struct _stmt_vec_info
*stmt_info
1780 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
1781 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
1782 si
->misalign
, vect_body
);
1784 body_cost_vec
.release ();
1787 stat
= vect_verify_datarefs_alignment (loop_vinfo
, NULL
);
1793 body_cost_vec
.release ();
1795 /* (2) Versioning to force alignment. */
1797 /* Try versioning if:
1798 1) flag_tree_vect_loop_version is TRUE
1799 2) optimize loop for speed
1800 3) there is at least one unsupported misaligned data ref with an unknown
1802 4) all misaligned data refs with a known misalignment are supported, and
1803 5) the number of runtime alignment checks is within reason. */
1806 flag_tree_vect_loop_version
1807 && optimize_loop_nest_for_speed_p (loop
)
1808 && (!loop
->inner
); /* FORNOW */
1812 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
1814 stmt
= DR_STMT (dr
);
1815 stmt_info
= vinfo_for_stmt (stmt
);
1817 /* For interleaving, only the alignment of the first access
1819 if (aligned_access_p (dr
)
1820 || (STMT_VINFO_GROUPED_ACCESS (stmt_info
)
1821 && GROUP_FIRST_ELEMENT (stmt_info
) != stmt
))
1824 /* Strided loads perform only component accesses, alignment is
1825 irrelevant for them. */
1826 if (STMT_VINFO_STRIDE_LOAD_P (stmt_info
))
1829 supportable_dr_alignment
= vect_supportable_dr_alignment (dr
, false);
1831 if (!supportable_dr_alignment
)
1837 if (known_alignment_for_access_p (dr
)
1838 || LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).length ()
1839 >= (unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS
))
1841 do_versioning
= false;
1845 stmt
= DR_STMT (dr
);
1846 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1847 gcc_assert (vectype
);
1849 /* The rightmost bits of an aligned address must be zeros.
1850 Construct the mask needed for this test. For example,
1851 GET_MODE_SIZE for the vector mode V4SI is 16 bytes so the
1852 mask must be 15 = 0xf. */
1853 mask
= GET_MODE_SIZE (TYPE_MODE (vectype
)) - 1;
1855 /* FORNOW: use the same mask to test all potentially unaligned
1856 references in the loop. The vectorizer currently supports
1857 a single vector size, see the reference to
1858 GET_MODE_NUNITS (TYPE_MODE (vectype)) where the
1859 vectorization factor is computed. */
1860 gcc_assert (!LOOP_VINFO_PTR_MASK (loop_vinfo
)
1861 || LOOP_VINFO_PTR_MASK (loop_vinfo
) == mask
);
1862 LOOP_VINFO_PTR_MASK (loop_vinfo
) = mask
;
1863 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).safe_push (
1868 /* Versioning requires at least one misaligned data reference. */
1869 if (!LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
))
1870 do_versioning
= false;
1871 else if (!do_versioning
)
1872 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).truncate (0);
1877 vec
<gimple
> may_misalign_stmts
1878 = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
);
1881 /* It can now be assumed that the data references in the statements
1882 in LOOP_VINFO_MAY_MISALIGN_STMTS will be aligned in the version
1883 of the loop being vectorized. */
1884 FOR_EACH_VEC_ELT (may_misalign_stmts
, i
, stmt
)
1886 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1887 dr
= STMT_VINFO_DATA_REF (stmt_info
);
1888 SET_DR_MISALIGNMENT (dr
, 0);
1889 if (dump_enabled_p ())
1890 dump_printf_loc (MSG_NOTE
, vect_location
,
1891 "Alignment of access forced using versioning.\n");
1894 if (dump_enabled_p ())
1895 dump_printf_loc (MSG_NOTE
, vect_location
,
1896 "Versioning for alignment will be applied.\n");
1898 /* Peeling and versioning can't be done together at this time. */
1899 gcc_assert (! (do_peeling
&& do_versioning
));
1901 stat
= vect_verify_datarefs_alignment (loop_vinfo
, NULL
);
1906 /* This point is reached if neither peeling nor versioning is being done. */
1907 gcc_assert (! (do_peeling
|| do_versioning
));
1909 stat
= vect_verify_datarefs_alignment (loop_vinfo
, NULL
);
1914 /* Function vect_find_same_alignment_drs.
1916 Update group and alignment relations according to the chosen
1917 vectorization factor. */
1920 vect_find_same_alignment_drs (struct data_dependence_relation
*ddr
,
1921 loop_vec_info loop_vinfo
)
1924 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1925 int vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1926 struct data_reference
*dra
= DDR_A (ddr
);
1927 struct data_reference
*drb
= DDR_B (ddr
);
1928 stmt_vec_info stmtinfo_a
= vinfo_for_stmt (DR_STMT (dra
));
1929 stmt_vec_info stmtinfo_b
= vinfo_for_stmt (DR_STMT (drb
));
1930 int dra_size
= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dra
))));
1931 int drb_size
= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (drb
))));
1932 lambda_vector dist_v
;
1933 unsigned int loop_depth
;
1935 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
1941 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
1944 /* Loop-based vectorization and known data dependence. */
1945 if (DDR_NUM_DIST_VECTS (ddr
) == 0)
1948 /* Data-dependence analysis reports a distance vector of zero
1949 for data-references that overlap only in the first iteration
1950 but have different sign step (see PR45764).
1951 So as a sanity check require equal DR_STEP. */
1952 if (!operand_equal_p (DR_STEP (dra
), DR_STEP (drb
), 0))
1955 loop_depth
= index_in_loop_nest (loop
->num
, DDR_LOOP_NEST (ddr
));
1956 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, dist_v
)
1958 int dist
= dist_v
[loop_depth
];
1960 if (dump_enabled_p ())
1961 dump_printf_loc (MSG_NOTE
, vect_location
,
1962 "dependence distance = %d.\n", dist
);
1964 /* Same loop iteration. */
1966 || (dist
% vectorization_factor
== 0 && dra_size
== drb_size
))
1968 /* Two references with distance zero have the same alignment. */
1969 STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a
).safe_push (drb
);
1970 STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b
).safe_push (dra
);
1971 if (dump_enabled_p ())
1973 dump_printf_loc (MSG_NOTE
, vect_location
,
1974 "accesses have the same alignment.\n");
1975 dump_printf (MSG_NOTE
,
1976 "dependence distance modulo vf == 0 between ");
1977 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dra
));
1978 dump_printf (MSG_NOTE
, " and ");
1979 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (drb
));
1980 dump_printf (MSG_NOTE
, "\n");
1987 /* Function vect_analyze_data_refs_alignment
1989 Analyze the alignment of the data-references in the loop.
1990 Return FALSE if a data reference is found that cannot be vectorized. */
1993 vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo
,
1994 bb_vec_info bb_vinfo
)
1996 if (dump_enabled_p ())
1997 dump_printf_loc (MSG_NOTE
, vect_location
,
1998 "=== vect_analyze_data_refs_alignment ===\n");
2000 /* Mark groups of data references with same alignment using
2001 data dependence information. */
2004 vec
<ddr_p
> ddrs
= LOOP_VINFO_DDRS (loop_vinfo
);
2005 struct data_dependence_relation
*ddr
;
2008 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
2009 vect_find_same_alignment_drs (ddr
, loop_vinfo
);
2012 if (!vect_compute_data_refs_alignment (loop_vinfo
, bb_vinfo
))
2014 if (dump_enabled_p ())
2015 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2016 "not vectorized: can't calculate alignment "
2025 /* Analyze groups of accesses: check that DR belongs to a group of
2026 accesses of legal size, step, etc. Detect gaps, single element
2027 interleaving, and other special cases. Set grouped access info.
2028 Collect groups of strided stores for further use in SLP analysis. */
2031 vect_analyze_group_access (struct data_reference
*dr
)
2033 tree step
= DR_STEP (dr
);
2034 tree scalar_type
= TREE_TYPE (DR_REF (dr
));
2035 HOST_WIDE_INT type_size
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type
));
2036 gimple stmt
= DR_STMT (dr
);
2037 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2038 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
2039 bb_vec_info bb_vinfo
= STMT_VINFO_BB_VINFO (stmt_info
);
2040 HOST_WIDE_INT dr_step
= TREE_INT_CST_LOW (step
);
2041 HOST_WIDE_INT groupsize
, last_accessed_element
= 1;
2042 bool slp_impossible
= false;
2043 struct loop
*loop
= NULL
;
2046 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2048 /* For interleaving, GROUPSIZE is STEP counted in elements, i.e., the
2049 size of the interleaving group (including gaps). */
2050 groupsize
= absu_hwi (dr_step
) / type_size
;
2052 /* Not consecutive access is possible only if it is a part of interleaving. */
2053 if (!GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
2055 /* Check if it this DR is a part of interleaving, and is a single
2056 element of the group that is accessed in the loop. */
2058 /* Gaps are supported only for loads. STEP must be a multiple of the type
2059 size. The size of the group must be a power of 2. */
2061 && (dr_step
% type_size
) == 0
2063 && exact_log2 (groupsize
) != -1)
2065 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) = stmt
;
2066 GROUP_SIZE (vinfo_for_stmt (stmt
)) = groupsize
;
2067 if (dump_enabled_p ())
2069 dump_printf_loc (MSG_NOTE
, vect_location
,
2070 "Detected single element interleaving ");
2071 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dr
));
2072 dump_printf (MSG_NOTE
, " step ");
2073 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, step
);
2074 dump_printf (MSG_NOTE
, "\n");
2079 if (dump_enabled_p ())
2080 dump_printf_loc (MSG_NOTE
, vect_location
,
2081 "Data access with gaps requires scalar "
2085 if (dump_enabled_p ())
2086 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2087 "Peeling for outer loop is not"
2092 LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) = true;
2098 if (dump_enabled_p ())
2100 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2101 "not consecutive access ");
2102 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
2103 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
2108 /* Mark the statement as unvectorizable. */
2109 STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr
))) = false;
2116 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) == stmt
)
2118 /* First stmt in the interleaving chain. Check the chain. */
2119 gimple next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
));
2120 struct data_reference
*data_ref
= dr
;
2121 unsigned int count
= 1;
2122 tree prev_init
= DR_INIT (data_ref
);
2124 HOST_WIDE_INT diff
, gaps
= 0;
2125 unsigned HOST_WIDE_INT count_in_bytes
;
2129 /* Skip same data-refs. In case that two or more stmts share
2130 data-ref (supported only for loads), we vectorize only the first
2131 stmt, and the rest get their vectorized loads from the first
2133 if (!tree_int_cst_compare (DR_INIT (data_ref
),
2134 DR_INIT (STMT_VINFO_DATA_REF (
2135 vinfo_for_stmt (next
)))))
2137 if (DR_IS_WRITE (data_ref
))
2139 if (dump_enabled_p ())
2140 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2141 "Two store stmts share the same dr.\n");
2145 /* For load use the same data-ref load. */
2146 GROUP_SAME_DR_STMT (vinfo_for_stmt (next
)) = prev
;
2149 next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next
));
2154 data_ref
= STMT_VINFO_DATA_REF (vinfo_for_stmt (next
));
2156 /* All group members have the same STEP by construction. */
2157 gcc_checking_assert (operand_equal_p (DR_STEP (data_ref
), step
, 0));
2159 /* Check that the distance between two accesses is equal to the type
2160 size. Otherwise, we have gaps. */
2161 diff
= (TREE_INT_CST_LOW (DR_INIT (data_ref
))
2162 - TREE_INT_CST_LOW (prev_init
)) / type_size
;
2165 /* FORNOW: SLP of accesses with gaps is not supported. */
2166 slp_impossible
= true;
2167 if (DR_IS_WRITE (data_ref
))
2169 if (dump_enabled_p ())
2170 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2171 "interleaved store with gaps\n");
2178 last_accessed_element
+= diff
;
2180 /* Store the gap from the previous member of the group. If there is no
2181 gap in the access, GROUP_GAP is always 1. */
2182 GROUP_GAP (vinfo_for_stmt (next
)) = diff
;
2184 prev_init
= DR_INIT (data_ref
);
2185 next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next
));
2186 /* Count the number of data-refs in the chain. */
2190 /* COUNT is the number of accesses found, we multiply it by the size of
2191 the type to get COUNT_IN_BYTES. */
2192 count_in_bytes
= type_size
* count
;
2194 /* Check that the size of the interleaving (including gaps) is not
2195 greater than STEP. */
2197 && absu_hwi (dr_step
) < count_in_bytes
+ gaps
* type_size
)
2199 if (dump_enabled_p ())
2201 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2202 "interleaving size is greater than step for ");
2203 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
2205 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
2210 /* Check that the size of the interleaving is equal to STEP for stores,
2211 i.e., that there are no gaps. */
2213 && absu_hwi (dr_step
) != count_in_bytes
)
2215 if (DR_IS_READ (dr
))
2217 slp_impossible
= true;
2218 /* There is a gap after the last load in the group. This gap is a
2219 difference between the groupsize and the number of elements.
2220 When there is no gap, this difference should be 0. */
2221 GROUP_GAP (vinfo_for_stmt (stmt
)) = groupsize
- count
;
2225 if (dump_enabled_p ())
2226 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2227 "interleaved store with gaps\n");
2232 /* Check that STEP is a multiple of type size. */
2234 && (dr_step
% type_size
) != 0)
2236 if (dump_enabled_p ())
2238 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2239 "step is not a multiple of type size: step ");
2240 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, step
);
2241 dump_printf (MSG_MISSED_OPTIMIZATION
, " size ");
2242 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
2243 TYPE_SIZE_UNIT (scalar_type
));
2244 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
2252 GROUP_SIZE (vinfo_for_stmt (stmt
)) = groupsize
;
2253 if (dump_enabled_p ())
2254 dump_printf_loc (MSG_NOTE
, vect_location
,
2255 "Detected interleaving of size %d\n", (int)groupsize
);
2257 /* SLP: create an SLP data structure for every interleaving group of
2258 stores for further analysis in vect_analyse_slp. */
2259 if (DR_IS_WRITE (dr
) && !slp_impossible
)
2262 LOOP_VINFO_GROUPED_STORES (loop_vinfo
).safe_push (stmt
);
2264 BB_VINFO_GROUPED_STORES (bb_vinfo
).safe_push (stmt
);
2267 /* There is a gap in the end of the group. */
2268 if (groupsize
- last_accessed_element
> 0 && loop_vinfo
)
2270 if (dump_enabled_p ())
2271 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2272 "Data access with gaps requires scalar "
2276 if (dump_enabled_p ())
2277 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2278 "Peeling for outer loop is not supported\n");
2282 LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) = true;
2290 /* Analyze the access pattern of the data-reference DR.
2291 In case of non-consecutive accesses call vect_analyze_group_access() to
2292 analyze groups of accesses. */
2295 vect_analyze_data_ref_access (struct data_reference
*dr
)
2297 tree step
= DR_STEP (dr
);
2298 tree scalar_type
= TREE_TYPE (DR_REF (dr
));
2299 gimple stmt
= DR_STMT (dr
);
2300 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2301 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
2302 struct loop
*loop
= NULL
;
2305 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2307 if (loop_vinfo
&& !step
)
2309 if (dump_enabled_p ())
2310 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2311 "bad data-ref access in loop\n");
2315 /* Allow invariant loads in not nested loops. */
2316 if (loop_vinfo
&& integer_zerop (step
))
2318 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) = NULL
;
2319 if (nested_in_vect_loop_p (loop
, stmt
))
2321 if (dump_enabled_p ())
2322 dump_printf_loc (MSG_NOTE
, vect_location
,
2323 "zero step in inner loop of nest\n");
2326 return DR_IS_READ (dr
);
2329 if (loop
&& nested_in_vect_loop_p (loop
, stmt
))
2331 /* Interleaved accesses are not yet supported within outer-loop
2332 vectorization for references in the inner-loop. */
2333 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) = NULL
;
2335 /* For the rest of the analysis we use the outer-loop step. */
2336 step
= STMT_VINFO_DR_STEP (stmt_info
);
2337 if (integer_zerop (step
))
2339 if (dump_enabled_p ())
2340 dump_printf_loc (MSG_NOTE
, vect_location
,
2341 "zero step in outer loop.\n");
2342 if (DR_IS_READ (dr
))
2350 if (TREE_CODE (step
) == INTEGER_CST
)
2352 HOST_WIDE_INT dr_step
= TREE_INT_CST_LOW (step
);
2353 if (!tree_int_cst_compare (step
, TYPE_SIZE_UNIT (scalar_type
))
2355 && !compare_tree_int (TYPE_SIZE_UNIT (scalar_type
), -dr_step
)))
2357 /* Mark that it is not interleaving. */
2358 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) = NULL
;
2363 if (loop
&& nested_in_vect_loop_p (loop
, stmt
))
2365 if (dump_enabled_p ())
2366 dump_printf_loc (MSG_NOTE
, vect_location
,
2367 "grouped access in outer loop.\n");
2371 /* Assume this is a DR handled by non-constant strided load case. */
2372 if (TREE_CODE (step
) != INTEGER_CST
)
2373 return STMT_VINFO_STRIDE_LOAD_P (stmt_info
);
2375 /* Not consecutive access - check if it's a part of interleaving group. */
2376 return vect_analyze_group_access (dr
);
2381 /* A helper function used in the comparator function to sort data
2382 references. T1 and T2 are two data references to be compared.
2383 The function returns -1, 0, or 1. */
2386 compare_tree (tree t1
, tree t2
)
2389 enum tree_code code
;
2400 if (TREE_CODE (t1
) != TREE_CODE (t2
))
2401 return TREE_CODE (t1
) < TREE_CODE (t2
) ? -1 : 1;
2403 code
= TREE_CODE (t1
);
2406 /* For const values, we can just use hash values for comparisons. */
2414 hashval_t h1
= iterative_hash_expr (t1
, 0);
2415 hashval_t h2
= iterative_hash_expr (t2
, 0);
2417 return h1
< h2
? -1 : 1;
2422 cmp
= compare_tree (SSA_NAME_VAR (t1
), SSA_NAME_VAR (t2
));
2426 if (SSA_NAME_VERSION (t1
) != SSA_NAME_VERSION (t2
))
2427 return SSA_NAME_VERSION (t1
) < SSA_NAME_VERSION (t2
) ? -1 : 1;
2431 tclass
= TREE_CODE_CLASS (code
);
2433 /* For var-decl, we could compare their UIDs. */
2434 if (tclass
== tcc_declaration
)
2436 if (DECL_UID (t1
) != DECL_UID (t2
))
2437 return DECL_UID (t1
) < DECL_UID (t2
) ? -1 : 1;
2441 /* For expressions with operands, compare their operands recursively. */
2442 for (i
= TREE_OPERAND_LENGTH (t1
) - 1; i
>= 0; --i
)
2444 cmp
= compare_tree (TREE_OPERAND (t1
, i
), TREE_OPERAND (t2
, i
));
2454 /* Compare two data-references DRA and DRB to group them into chunks
2455 suitable for grouping. */
2458 dr_group_sort_cmp (const void *dra_
, const void *drb_
)
2460 data_reference_p dra
= *(data_reference_p
*)const_cast<void *>(dra_
);
2461 data_reference_p drb
= *(data_reference_p
*)const_cast<void *>(drb_
);
2464 /* Stabilize sort. */
2468 /* Ordering of DRs according to base. */
2469 if (!operand_equal_p (DR_BASE_ADDRESS (dra
), DR_BASE_ADDRESS (drb
), 0))
2471 cmp
= compare_tree (DR_BASE_ADDRESS (dra
), DR_BASE_ADDRESS (drb
));
2476 /* And according to DR_OFFSET. */
2477 if (!dr_equal_offsets_p (dra
, drb
))
2479 cmp
= compare_tree (DR_OFFSET (dra
), DR_OFFSET (drb
));
2484 /* Put reads before writes. */
2485 if (DR_IS_READ (dra
) != DR_IS_READ (drb
))
2486 return DR_IS_READ (dra
) ? -1 : 1;
2488 /* Then sort after access size. */
2489 if (!operand_equal_p (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra
))),
2490 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb
))), 0))
2492 cmp
= compare_tree (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra
))),
2493 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb
))));
2498 /* And after step. */
2499 if (!operand_equal_p (DR_STEP (dra
), DR_STEP (drb
), 0))
2501 cmp
= compare_tree (DR_STEP (dra
), DR_STEP (drb
));
2506 /* Then sort after DR_INIT. In case of identical DRs sort after stmt UID. */
2507 cmp
= tree_int_cst_compare (DR_INIT (dra
), DR_INIT (drb
));
2509 return gimple_uid (DR_STMT (dra
)) < gimple_uid (DR_STMT (drb
)) ? -1 : 1;
2513 /* Function vect_analyze_data_ref_accesses.
2515 Analyze the access pattern of all the data references in the loop.
2517 FORNOW: the only access pattern that is considered vectorizable is a
2518 simple step 1 (consecutive) access.
2520 FORNOW: handle only arrays and pointer accesses. */
2523 vect_analyze_data_ref_accesses (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
)
2526 vec
<data_reference_p
> datarefs
;
2527 struct data_reference
*dr
;
2529 if (dump_enabled_p ())
2530 dump_printf_loc (MSG_NOTE
, vect_location
,
2531 "=== vect_analyze_data_ref_accesses ===\n");
2534 datarefs
= LOOP_VINFO_DATAREFS (loop_vinfo
);
2536 datarefs
= BB_VINFO_DATAREFS (bb_vinfo
);
2538 if (datarefs
.is_empty ())
2541 /* Sort the array of datarefs to make building the interleaving chains
2543 qsort (datarefs
.address(), datarefs
.length (),
2544 sizeof (data_reference_p
), dr_group_sort_cmp
);
2546 /* Build the interleaving chains. */
2547 for (i
= 0; i
< datarefs
.length () - 1;)
2549 data_reference_p dra
= datarefs
[i
];
2550 stmt_vec_info stmtinfo_a
= vinfo_for_stmt (DR_STMT (dra
));
2551 stmt_vec_info lastinfo
= NULL
;
2552 for (i
= i
+ 1; i
< datarefs
.length (); ++i
)
2554 data_reference_p drb
= datarefs
[i
];
2555 stmt_vec_info stmtinfo_b
= vinfo_for_stmt (DR_STMT (drb
));
2557 /* ??? Imperfect sorting (non-compatible types, non-modulo
2558 accesses, same accesses) can lead to a group to be artificially
2559 split here as we don't just skip over those. If it really
2560 matters we can push those to a worklist and re-iterate
2561 over them. The we can just skip ahead to the next DR here. */
2563 /* Check that the data-refs have same first location (except init)
2564 and they are both either store or load (not load and store). */
2565 if (DR_IS_READ (dra
) != DR_IS_READ (drb
)
2566 || !operand_equal_p (DR_BASE_ADDRESS (dra
),
2567 DR_BASE_ADDRESS (drb
), 0)
2568 || !dr_equal_offsets_p (dra
, drb
))
2571 /* Check that the data-refs have the same constant size and step. */
2572 tree sza
= TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra
)));
2573 tree szb
= TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb
)));
2574 if (!host_integerp (sza
, 1)
2575 || !host_integerp (szb
, 1)
2576 || !tree_int_cst_equal (sza
, szb
)
2577 || !host_integerp (DR_STEP (dra
), 0)
2578 || !host_integerp (DR_STEP (drb
), 0)
2579 || !tree_int_cst_equal (DR_STEP (dra
), DR_STEP (drb
)))
2582 /* Do not place the same access in the interleaving chain twice. */
2583 if (tree_int_cst_compare (DR_INIT (dra
), DR_INIT (drb
)) == 0)
2586 /* Check the types are compatible.
2587 ??? We don't distinguish this during sorting. */
2588 if (!types_compatible_p (TREE_TYPE (DR_REF (dra
)),
2589 TREE_TYPE (DR_REF (drb
))))
2592 /* Sorting has ensured that DR_INIT (dra) <= DR_INIT (drb). */
2593 HOST_WIDE_INT init_a
= TREE_INT_CST_LOW (DR_INIT (dra
));
2594 HOST_WIDE_INT init_b
= TREE_INT_CST_LOW (DR_INIT (drb
));
2595 gcc_assert (init_a
< init_b
);
2597 /* If init_b == init_a + the size of the type * k, we have an
2598 interleaving, and DRA is accessed before DRB. */
2599 HOST_WIDE_INT type_size_a
= TREE_INT_CST_LOW (sza
);
2600 if ((init_b
- init_a
) % type_size_a
!= 0)
2603 /* The step (if not zero) is greater than the difference between
2604 data-refs' inits. This splits groups into suitable sizes. */
2605 HOST_WIDE_INT step
= TREE_INT_CST_LOW (DR_STEP (dra
));
2606 if (step
!= 0 && step
<= (init_b
- init_a
))
2609 if (dump_enabled_p ())
2611 dump_printf_loc (MSG_NOTE
, vect_location
,
2612 "Detected interleaving ");
2613 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dra
));
2614 dump_printf (MSG_NOTE
, " and ");
2615 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (drb
));
2616 dump_printf (MSG_NOTE
, "\n");
2619 /* Link the found element into the group list. */
2620 if (!GROUP_FIRST_ELEMENT (stmtinfo_a
))
2622 GROUP_FIRST_ELEMENT (stmtinfo_a
) = DR_STMT (dra
);
2623 lastinfo
= stmtinfo_a
;
2625 GROUP_FIRST_ELEMENT (stmtinfo_b
) = DR_STMT (dra
);
2626 GROUP_NEXT_ELEMENT (lastinfo
) = DR_STMT (drb
);
2627 lastinfo
= stmtinfo_b
;
2631 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
2632 if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr
)))
2633 && !vect_analyze_data_ref_access (dr
))
2635 if (dump_enabled_p ())
2636 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2637 "not vectorized: complicated access pattern.\n");
2641 /* Mark the statement as not vectorizable. */
2642 STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr
))) = false;
2652 /* Function vect_prune_runtime_alias_test_list.
2654 Prune a list of ddrs to be tested at run-time by versioning for alias.
2655 Return FALSE if resulting list of ddrs is longer then allowed by
2656 PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS, otherwise return TRUE. */
2659 vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo
)
2662 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
);
2665 if (dump_enabled_p ())
2666 dump_printf_loc (MSG_NOTE
, vect_location
,
2667 "=== vect_prune_runtime_alias_test_list ===\n");
2669 for (i
= 0; i
< ddrs
.length (); )
2677 for (j
= 0; j
< i
; j
++)
2679 ddr_p ddr_j
= ddrs
[j
];
2681 if (vect_vfa_range_equal (ddr_i
, ddr_j
))
2683 if (dump_enabled_p ())
2685 dump_printf_loc (MSG_NOTE
, vect_location
,
2686 "found equal ranges ");
2687 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2688 DR_REF (DDR_A (ddr_i
)));
2689 dump_printf (MSG_NOTE
, ", ");
2690 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2691 DR_REF (DDR_B (ddr_i
)));
2692 dump_printf (MSG_NOTE
, " and ");
2693 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2694 DR_REF (DDR_A (ddr_j
)));
2695 dump_printf (MSG_NOTE
, ", ");
2696 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2697 DR_REF (DDR_B (ddr_j
)));
2698 dump_printf (MSG_NOTE
, "\n");
2707 ddrs
.ordered_remove (i
);
2713 if (ddrs
.length () >
2714 (unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS
))
2716 if (dump_enabled_p ())
2718 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2719 "disable versioning for alias - max number of "
2720 "generated checks exceeded.\n");
2723 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
).truncate (0);
2731 /* Check whether a non-affine read in stmt is suitable for gather load
2732 and if so, return a builtin decl for that operation. */
2735 vect_check_gather (gimple stmt
, loop_vec_info loop_vinfo
, tree
*basep
,
2736 tree
*offp
, int *scalep
)
2738 HOST_WIDE_INT scale
= 1, pbitpos
, pbitsize
;
2739 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2740 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2741 struct data_reference
*dr
= STMT_VINFO_DATA_REF (stmt_info
);
2742 tree offtype
= NULL_TREE
;
2743 tree decl
, base
, off
;
2744 enum machine_mode pmode
;
2745 int punsignedp
, pvolatilep
;
2747 /* The gather builtins need address of the form
2748 loop_invariant + vector * {1, 2, 4, 8}
2750 loop_invariant + sign_extend (vector) * { 1, 2, 4, 8 }.
2751 Unfortunately DR_BASE_ADDRESS/DR_OFFSET can be a mixture
2752 of loop invariants/SSA_NAMEs defined in the loop, with casts,
2753 multiplications and additions in it. To get a vector, we need
2754 a single SSA_NAME that will be defined in the loop and will
2755 contain everything that is not loop invariant and that can be
2756 vectorized. The following code attempts to find such a preexistng
2757 SSA_NAME OFF and put the loop invariants into a tree BASE
2758 that can be gimplified before the loop. */
2759 base
= get_inner_reference (DR_REF (dr
), &pbitsize
, &pbitpos
, &off
,
2760 &pmode
, &punsignedp
, &pvolatilep
, false);
2761 gcc_assert (base
!= NULL_TREE
&& (pbitpos
% BITS_PER_UNIT
) == 0);
2763 if (TREE_CODE (base
) == MEM_REF
)
2765 if (!integer_zerop (TREE_OPERAND (base
, 1)))
2767 if (off
== NULL_TREE
)
2769 double_int moff
= mem_ref_offset (base
);
2770 off
= double_int_to_tree (sizetype
, moff
);
2773 off
= size_binop (PLUS_EXPR
, off
,
2774 fold_convert (sizetype
, TREE_OPERAND (base
, 1)));
2776 base
= TREE_OPERAND (base
, 0);
2779 base
= build_fold_addr_expr (base
);
2781 if (off
== NULL_TREE
)
2782 off
= size_zero_node
;
2784 /* If base is not loop invariant, either off is 0, then we start with just
2785 the constant offset in the loop invariant BASE and continue with base
2786 as OFF, otherwise give up.
2787 We could handle that case by gimplifying the addition of base + off
2788 into some SSA_NAME and use that as off, but for now punt. */
2789 if (!expr_invariant_in_loop_p (loop
, base
))
2791 if (!integer_zerop (off
))
2794 base
= size_int (pbitpos
/ BITS_PER_UNIT
);
2796 /* Otherwise put base + constant offset into the loop invariant BASE
2797 and continue with OFF. */
2800 base
= fold_convert (sizetype
, base
);
2801 base
= size_binop (PLUS_EXPR
, base
, size_int (pbitpos
/ BITS_PER_UNIT
));
2804 /* OFF at this point may be either a SSA_NAME or some tree expression
2805 from get_inner_reference. Try to peel off loop invariants from it
2806 into BASE as long as possible. */
2808 while (offtype
== NULL_TREE
)
2810 enum tree_code code
;
2811 tree op0
, op1
, add
= NULL_TREE
;
2813 if (TREE_CODE (off
) == SSA_NAME
)
2815 gimple def_stmt
= SSA_NAME_DEF_STMT (off
);
2817 if (expr_invariant_in_loop_p (loop
, off
))
2820 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2823 op0
= gimple_assign_rhs1 (def_stmt
);
2824 code
= gimple_assign_rhs_code (def_stmt
);
2825 op1
= gimple_assign_rhs2 (def_stmt
);
2829 if (get_gimple_rhs_class (TREE_CODE (off
)) == GIMPLE_TERNARY_RHS
)
2831 code
= TREE_CODE (off
);
2832 extract_ops_from_tree (off
, &code
, &op0
, &op1
);
2836 case POINTER_PLUS_EXPR
:
2838 if (expr_invariant_in_loop_p (loop
, op0
))
2843 add
= fold_convert (sizetype
, add
);
2845 add
= size_binop (MULT_EXPR
, add
, size_int (scale
));
2846 base
= size_binop (PLUS_EXPR
, base
, add
);
2849 if (expr_invariant_in_loop_p (loop
, op1
))
2857 if (expr_invariant_in_loop_p (loop
, op1
))
2859 add
= fold_convert (sizetype
, op1
);
2860 add
= size_binop (MINUS_EXPR
, size_zero_node
, add
);
2866 if (scale
== 1 && host_integerp (op1
, 0))
2868 scale
= tree_low_cst (op1
, 0);
2877 if (!POINTER_TYPE_P (TREE_TYPE (op0
))
2878 && !INTEGRAL_TYPE_P (TREE_TYPE (op0
)))
2880 if (TYPE_PRECISION (TREE_TYPE (op0
))
2881 == TYPE_PRECISION (TREE_TYPE (off
)))
2886 if (TYPE_PRECISION (TREE_TYPE (op0
))
2887 < TYPE_PRECISION (TREE_TYPE (off
)))
2890 offtype
= TREE_TYPE (off
);
2901 /* If at the end OFF still isn't a SSA_NAME or isn't
2902 defined in the loop, punt. */
2903 if (TREE_CODE (off
) != SSA_NAME
2904 || expr_invariant_in_loop_p (loop
, off
))
2907 if (offtype
== NULL_TREE
)
2908 offtype
= TREE_TYPE (off
);
2910 decl
= targetm
.vectorize
.builtin_gather (STMT_VINFO_VECTYPE (stmt_info
),
2912 if (decl
== NULL_TREE
)
2924 /* Function vect_analyze_data_refs.
2926 Find all the data references in the loop or basic block.
2928 The general structure of the analysis of data refs in the vectorizer is as
2930 1- vect_analyze_data_refs(loop/bb): call
2931 compute_data_dependences_for_loop/bb to find and analyze all data-refs
2932 in the loop/bb and their dependences.
2933 2- vect_analyze_dependences(): apply dependence testing using ddrs.
2934 3- vect_analyze_drs_alignment(): check that ref_stmt.alignment is ok.
2935 4- vect_analyze_drs_access(): check that ref_stmt.step is ok.
2940 vect_analyze_data_refs (loop_vec_info loop_vinfo
,
2941 bb_vec_info bb_vinfo
,
2944 struct loop
*loop
= NULL
;
2945 basic_block bb
= NULL
;
2947 vec
<data_reference_p
> datarefs
;
2948 struct data_reference
*dr
;
2951 if (dump_enabled_p ())
2952 dump_printf_loc (MSG_NOTE
, vect_location
,
2953 "=== vect_analyze_data_refs ===\n");
2957 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2958 if (!find_loop_nest (loop
, &LOOP_VINFO_LOOP_NEST (loop_vinfo
))
2959 || find_data_references_in_loop
2960 (loop
, &LOOP_VINFO_DATAREFS (loop_vinfo
)))
2962 if (dump_enabled_p ())
2963 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2964 "not vectorized: loop contains function calls"
2965 " or data references that cannot be analyzed\n");
2969 datarefs
= LOOP_VINFO_DATAREFS (loop_vinfo
);
2973 gimple_stmt_iterator gsi
;
2975 bb
= BB_VINFO_BB (bb_vinfo
);
2976 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2978 gimple stmt
= gsi_stmt (gsi
);
2979 if (!find_data_references_in_stmt (NULL
, stmt
,
2980 &BB_VINFO_DATAREFS (bb_vinfo
)))
2982 /* Mark the rest of the basic-block as unvectorizable. */
2983 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
2985 stmt
= gsi_stmt (gsi
);
2986 STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt
)) = false;
2992 datarefs
= BB_VINFO_DATAREFS (bb_vinfo
);
2995 /* Go through the data-refs, check that the analysis succeeded. Update
2996 pointer from stmt_vec_info struct to DR and vectype. */
2998 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
3001 stmt_vec_info stmt_info
;
3002 tree base
, offset
, init
;
3003 bool gather
= false;
3004 bool simd_lane_access
= false;
3008 if (!dr
|| !DR_REF (dr
))
3010 if (dump_enabled_p ())
3011 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3012 "not vectorized: unhandled data-ref\n");
3016 stmt
= DR_STMT (dr
);
3017 stmt_info
= vinfo_for_stmt (stmt
);
3019 /* Discard clobbers from the dataref vector. We will remove
3020 clobber stmts during vectorization. */
3021 if (gimple_clobber_p (stmt
))
3023 if (i
== datarefs
.length () - 1)
3028 datarefs
[i
] = datarefs
.pop ();
3032 /* Check that analysis of the data-ref succeeded. */
3033 if (!DR_BASE_ADDRESS (dr
) || !DR_OFFSET (dr
) || !DR_INIT (dr
)
3038 && !TREE_THIS_VOLATILE (DR_REF (dr
))
3039 && targetm
.vectorize
.builtin_gather
!= NULL
;
3040 bool maybe_simd_lane_access
3041 = loop_vinfo
&& loop
->simduid
;
3043 /* If target supports vector gather loads, or if this might be
3044 a SIMD lane access, see if they can't be used. */
3046 && (maybe_gather
|| maybe_simd_lane_access
)
3047 && !nested_in_vect_loop_p (loop
, stmt
))
3049 struct data_reference
*newdr
3050 = create_data_ref (NULL
, loop_containing_stmt (stmt
),
3051 DR_REF (dr
), stmt
, true);
3052 gcc_assert (newdr
!= NULL
&& DR_REF (newdr
));
3053 if (DR_BASE_ADDRESS (newdr
)
3054 && DR_OFFSET (newdr
)
3057 && integer_zerop (DR_STEP (newdr
)))
3059 if (maybe_simd_lane_access
)
3061 tree off
= DR_OFFSET (newdr
);
3063 if (TREE_CODE (DR_INIT (newdr
)) == INTEGER_CST
3064 && TREE_CODE (off
) == MULT_EXPR
3065 && host_integerp (TREE_OPERAND (off
, 1), 1))
3067 tree step
= TREE_OPERAND (off
, 1);
3068 off
= TREE_OPERAND (off
, 0);
3070 if (CONVERT_EXPR_P (off
)
3071 && TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (off
,
3073 < TYPE_PRECISION (TREE_TYPE (off
)))
3074 off
= TREE_OPERAND (off
, 0);
3075 if (TREE_CODE (off
) == SSA_NAME
)
3077 gimple def
= SSA_NAME_DEF_STMT (off
);
3078 tree reft
= TREE_TYPE (DR_REF (newdr
));
3079 if (gimple_call_internal_p (def
)
3080 && gimple_call_internal_fn (def
)
3081 == IFN_GOMP_SIMD_LANE
)
3083 tree arg
= gimple_call_arg (def
, 0);
3084 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
3085 arg
= SSA_NAME_VAR (arg
);
3086 if (arg
== loop
->simduid
3088 && tree_int_cst_equal
3089 (TYPE_SIZE_UNIT (reft
),
3092 DR_OFFSET (newdr
) = ssize_int (0);
3093 DR_STEP (newdr
) = step
;
3094 DR_ALIGNED_TO (newdr
)
3095 = size_int (BIGGEST_ALIGNMENT
);
3097 simd_lane_access
= true;
3103 if (!simd_lane_access
&& maybe_gather
)
3109 if (!gather
&& !simd_lane_access
)
3110 free_data_ref (newdr
);
3113 if (!gather
&& !simd_lane_access
)
3115 if (dump_enabled_p ())
3117 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3118 "not vectorized: data ref analysis "
3120 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3121 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3131 if (TREE_CODE (DR_BASE_ADDRESS (dr
)) == INTEGER_CST
)
3133 if (dump_enabled_p ())
3134 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3135 "not vectorized: base addr of dr is a "
3141 if (gather
|| simd_lane_access
)
3146 if (TREE_THIS_VOLATILE (DR_REF (dr
)))
3148 if (dump_enabled_p ())
3150 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3151 "not vectorized: volatile type ");
3152 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3153 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3162 if (stmt_can_throw_internal (stmt
))
3164 if (dump_enabled_p ())
3166 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3167 "not vectorized: statement can throw an "
3169 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3170 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3176 if (gather
|| simd_lane_access
)
3181 if (TREE_CODE (DR_REF (dr
)) == COMPONENT_REF
3182 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr
), 1)))
3184 if (dump_enabled_p ())
3186 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3187 "not vectorized: statement is bitfield "
3189 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3190 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3196 if (gather
|| simd_lane_access
)
3201 base
= unshare_expr (DR_BASE_ADDRESS (dr
));
3202 offset
= unshare_expr (DR_OFFSET (dr
));
3203 init
= unshare_expr (DR_INIT (dr
));
3205 if (is_gimple_call (stmt
))
3207 if (dump_enabled_p ())
3209 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3210 "not vectorized: dr in a call ");
3211 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3212 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3218 if (gather
|| simd_lane_access
)
3223 /* Update DR field in stmt_vec_info struct. */
3225 /* If the dataref is in an inner-loop of the loop that is considered for
3226 for vectorization, we also want to analyze the access relative to
3227 the outer-loop (DR contains information only relative to the
3228 inner-most enclosing loop). We do that by building a reference to the
3229 first location accessed by the inner-loop, and analyze it relative to
3231 if (loop
&& nested_in_vect_loop_p (loop
, stmt
))
3233 tree outer_step
, outer_base
, outer_init
;
3234 HOST_WIDE_INT pbitsize
, pbitpos
;
3236 enum machine_mode pmode
;
3237 int punsignedp
, pvolatilep
;
3238 affine_iv base_iv
, offset_iv
;
3241 /* Build a reference to the first location accessed by the
3242 inner-loop: *(BASE+INIT). (The first location is actually
3243 BASE+INIT+OFFSET, but we add OFFSET separately later). */
3244 tree inner_base
= build_fold_indirect_ref
3245 (fold_build_pointer_plus (base
, init
));
3247 if (dump_enabled_p ())
3249 dump_printf_loc (MSG_NOTE
, vect_location
,
3250 "analyze in outer-loop: ");
3251 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, inner_base
);
3252 dump_printf (MSG_NOTE
, "\n");
3255 outer_base
= get_inner_reference (inner_base
, &pbitsize
, &pbitpos
,
3256 &poffset
, &pmode
, &punsignedp
, &pvolatilep
, false);
3257 gcc_assert (outer_base
!= NULL_TREE
);
3259 if (pbitpos
% BITS_PER_UNIT
!= 0)
3261 if (dump_enabled_p ())
3262 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3263 "failed: bit offset alignment.\n");
3267 outer_base
= build_fold_addr_expr (outer_base
);
3268 if (!simple_iv (loop
, loop_containing_stmt (stmt
), outer_base
,
3271 if (dump_enabled_p ())
3272 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3273 "failed: evolution of base is not affine.\n");
3280 poffset
= fold_build2 (PLUS_EXPR
, TREE_TYPE (offset
), offset
,
3288 offset_iv
.base
= ssize_int (0);
3289 offset_iv
.step
= ssize_int (0);
3291 else if (!simple_iv (loop
, loop_containing_stmt (stmt
), poffset
,
3294 if (dump_enabled_p ())
3295 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3296 "evolution of offset is not affine.\n");
3300 outer_init
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
3301 split_constant_offset (base_iv
.base
, &base_iv
.base
, &dinit
);
3302 outer_init
= size_binop (PLUS_EXPR
, outer_init
, dinit
);
3303 split_constant_offset (offset_iv
.base
, &offset_iv
.base
, &dinit
);
3304 outer_init
= size_binop (PLUS_EXPR
, outer_init
, dinit
);
3306 outer_step
= size_binop (PLUS_EXPR
,
3307 fold_convert (ssizetype
, base_iv
.step
),
3308 fold_convert (ssizetype
, offset_iv
.step
));
3310 STMT_VINFO_DR_STEP (stmt_info
) = outer_step
;
3311 /* FIXME: Use canonicalize_base_object_address (base_iv.base); */
3312 STMT_VINFO_DR_BASE_ADDRESS (stmt_info
) = base_iv
.base
;
3313 STMT_VINFO_DR_INIT (stmt_info
) = outer_init
;
3314 STMT_VINFO_DR_OFFSET (stmt_info
) =
3315 fold_convert (ssizetype
, offset_iv
.base
);
3316 STMT_VINFO_DR_ALIGNED_TO (stmt_info
) =
3317 size_int (highest_pow2_factor (offset_iv
.base
));
3319 if (dump_enabled_p ())
3321 dump_printf_loc (MSG_NOTE
, vect_location
,
3322 "\touter base_address: ");
3323 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
3324 STMT_VINFO_DR_BASE_ADDRESS (stmt_info
));
3325 dump_printf (MSG_NOTE
, "\n\touter offset from base address: ");
3326 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
3327 STMT_VINFO_DR_OFFSET (stmt_info
));
3328 dump_printf (MSG_NOTE
,
3329 "\n\touter constant offset from base address: ");
3330 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
3331 STMT_VINFO_DR_INIT (stmt_info
));
3332 dump_printf (MSG_NOTE
, "\n\touter step: ");
3333 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
3334 STMT_VINFO_DR_STEP (stmt_info
));
3335 dump_printf (MSG_NOTE
, "\n\touter aligned to: ");
3336 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
3337 STMT_VINFO_DR_ALIGNED_TO (stmt_info
));
3338 dump_printf (MSG_NOTE
, "\n");
3342 if (STMT_VINFO_DATA_REF (stmt_info
))
3344 if (dump_enabled_p ())
3346 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3347 "not vectorized: more than one data ref "
3349 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3350 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3356 if (gather
|| simd_lane_access
)
3361 STMT_VINFO_DATA_REF (stmt_info
) = dr
;
3362 if (simd_lane_access
)
3364 STMT_VINFO_SIMD_LANE_ACCESS_P (stmt_info
) = true;
3368 /* Set vectype for STMT. */
3369 scalar_type
= TREE_TYPE (DR_REF (dr
));
3370 STMT_VINFO_VECTYPE (stmt_info
) =
3371 get_vectype_for_scalar_type (scalar_type
);
3372 if (!STMT_VINFO_VECTYPE (stmt_info
))
3374 if (dump_enabled_p ())
3376 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3377 "not vectorized: no vectype for stmt: ");
3378 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3379 dump_printf (MSG_MISSED_OPTIMIZATION
, " scalar_type: ");
3380 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_DETAILS
,
3382 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3388 if (gather
|| simd_lane_access
)
3390 STMT_VINFO_DATA_REF (stmt_info
) = NULL
;
3397 if (dump_enabled_p ())
3399 dump_printf_loc (MSG_NOTE
, vect_location
,
3400 "got vectype for stmt: ");
3401 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
3402 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
3403 STMT_VINFO_VECTYPE (stmt_info
));
3404 dump_printf (MSG_NOTE
, "\n");
3408 /* Adjust the minimal vectorization factor according to the
3410 vf
= TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
3418 gather
= 0 != vect_check_gather (stmt
, loop_vinfo
, NULL
, &off
, NULL
);
3420 && get_vectype_for_scalar_type (TREE_TYPE (off
)) == NULL_TREE
)
3424 STMT_VINFO_DATA_REF (stmt_info
) = NULL
;
3426 if (dump_enabled_p ())
3428 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3429 "not vectorized: not suitable for gather "
3431 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3432 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3438 STMT_VINFO_GATHER_P (stmt_info
) = true;
3441 && TREE_CODE (DR_STEP (dr
)) != INTEGER_CST
)
3443 if (nested_in_vect_loop_p (loop
, stmt
)
3444 || !DR_IS_READ (dr
))
3446 if (dump_enabled_p ())
3448 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3449 "not vectorized: not suitable for strided "
3451 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3452 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3456 STMT_VINFO_STRIDE_LOAD_P (stmt_info
) = true;
3460 /* If we stopped analysis at the first dataref we could not analyze
3461 when trying to vectorize a basic-block mark the rest of the datarefs
3462 as not vectorizable and truncate the vector of datarefs. That
3463 avoids spending useless time in analyzing their dependence. */
3464 if (i
!= datarefs
.length ())
3466 gcc_assert (bb_vinfo
!= NULL
);
3467 for (unsigned j
= i
; j
< datarefs
.length (); ++j
)
3469 data_reference_p dr
= datarefs
[j
];
3470 STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr
))) = false;
3473 datarefs
.truncate (i
);
3480 /* Function vect_get_new_vect_var.
3482 Returns a name for a new variable. The current naming scheme appends the
3483 prefix "vect_" or "vect_p" (depending on the value of VAR_KIND) to
3484 the name of vectorizer generated variables, and appends that to NAME if
3488 vect_get_new_vect_var (tree type
, enum vect_var_kind var_kind
, const char *name
)
3495 case vect_simple_var
:
3498 case vect_scalar_var
:
3501 case vect_pointer_var
:
3510 char* tmp
= concat (prefix
, "_", name
, NULL
);
3511 new_vect_var
= create_tmp_reg (type
, tmp
);
3515 new_vect_var
= create_tmp_reg (type
, prefix
);
3517 return new_vect_var
;
3521 /* Function vect_create_addr_base_for_vector_ref.
3523 Create an expression that computes the address of the first memory location
3524 that will be accessed for a data reference.
3527 STMT: The statement containing the data reference.
3528 NEW_STMT_LIST: Must be initialized to NULL_TREE or a statement list.
3529 OFFSET: Optional. If supplied, it is be added to the initial address.
3530 LOOP: Specify relative to which loop-nest should the address be computed.
3531 For example, when the dataref is in an inner-loop nested in an
3532 outer-loop that is now being vectorized, LOOP can be either the
3533 outer-loop, or the inner-loop. The first memory location accessed
3534 by the following dataref ('in' points to short):
3541 if LOOP=i_loop: &in (relative to i_loop)
3542 if LOOP=j_loop: &in+i*2B (relative to j_loop)
3545 1. Return an SSA_NAME whose value is the address of the memory location of
3546 the first vector of the data reference.
3547 2. If new_stmt_list is not NULL_TREE after return then the caller must insert
3548 these statement(s) which define the returned SSA_NAME.
3550 FORNOW: We are only handling array accesses with step 1. */
3553 vect_create_addr_base_for_vector_ref (gimple stmt
,
3554 gimple_seq
*new_stmt_list
,
3558 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3559 struct data_reference
*dr
= STMT_VINFO_DATA_REF (stmt_info
);
3561 const char *base_name
;
3564 gimple_seq seq
= NULL
;
3568 tree step
= TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr
)));
3569 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3571 if (loop_vinfo
&& loop
&& loop
!= (gimple_bb (stmt
))->loop_father
)
3573 struct loop
*outer_loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3575 gcc_assert (nested_in_vect_loop_p (outer_loop
, stmt
));
3577 data_ref_base
= unshare_expr (STMT_VINFO_DR_BASE_ADDRESS (stmt_info
));
3578 base_offset
= unshare_expr (STMT_VINFO_DR_OFFSET (stmt_info
));
3579 init
= unshare_expr (STMT_VINFO_DR_INIT (stmt_info
));
3583 data_ref_base
= unshare_expr (DR_BASE_ADDRESS (dr
));
3584 base_offset
= unshare_expr (DR_OFFSET (dr
));
3585 init
= unshare_expr (DR_INIT (dr
));
3589 base_name
= get_name (data_ref_base
);
3592 base_offset
= ssize_int (0);
3593 init
= ssize_int (0);
3594 base_name
= get_name (DR_REF (dr
));
3597 /* Create base_offset */
3598 base_offset
= size_binop (PLUS_EXPR
,
3599 fold_convert (sizetype
, base_offset
),
3600 fold_convert (sizetype
, init
));
3604 offset
= fold_build2 (MULT_EXPR
, sizetype
,
3605 fold_convert (sizetype
, offset
), step
);
3606 base_offset
= fold_build2 (PLUS_EXPR
, sizetype
,
3607 base_offset
, offset
);
3610 /* base + base_offset */
3612 addr_base
= fold_build_pointer_plus (data_ref_base
, base_offset
);
3615 addr_base
= build1 (ADDR_EXPR
,
3616 build_pointer_type (TREE_TYPE (DR_REF (dr
))),
3617 unshare_expr (DR_REF (dr
)));
3620 vect_ptr_type
= build_pointer_type (STMT_VINFO_VECTYPE (stmt_info
));
3621 addr_base
= fold_convert (vect_ptr_type
, addr_base
);
3622 dest
= vect_get_new_vect_var (vect_ptr_type
, vect_pointer_var
, base_name
);
3623 addr_base
= force_gimple_operand (addr_base
, &seq
, false, dest
);
3624 gimple_seq_add_seq (new_stmt_list
, seq
);
3626 if (DR_PTR_INFO (dr
)
3627 && TREE_CODE (addr_base
) == SSA_NAME
)
3629 duplicate_ssa_name_ptr_info (addr_base
, DR_PTR_INFO (dr
));
3631 mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (addr_base
));
3634 if (dump_enabled_p ())
3636 dump_printf_loc (MSG_NOTE
, vect_location
, "created ");
3637 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, addr_base
);
3638 dump_printf (MSG_NOTE
, "\n");
3645 /* Function vect_create_data_ref_ptr.
3647 Create a new pointer-to-AGGR_TYPE variable (ap), that points to the first
3648 location accessed in the loop by STMT, along with the def-use update
3649 chain to appropriately advance the pointer through the loop iterations.
3650 Also set aliasing information for the pointer. This pointer is used by
3651 the callers to this function to create a memory reference expression for
3652 vector load/store access.
3655 1. STMT: a stmt that references memory. Expected to be of the form
3656 GIMPLE_ASSIGN <name, data-ref> or
3657 GIMPLE_ASSIGN <data-ref, name>.
3658 2. AGGR_TYPE: the type of the reference, which should be either a vector
3660 3. AT_LOOP: the loop where the vector memref is to be created.
3661 4. OFFSET (optional): an offset to be added to the initial address accessed
3662 by the data-ref in STMT.
3663 5. BSI: location where the new stmts are to be placed if there is no loop
3664 6. ONLY_INIT: indicate if ap is to be updated in the loop, or remain
3665 pointing to the initial address.
3668 1. Declare a new ptr to vector_type, and have it point to the base of the
3669 data reference (initial addressed accessed by the data reference).
3670 For example, for vector of type V8HI, the following code is generated:
3673 ap = (v8hi *)initial_address;
3675 if OFFSET is not supplied:
3676 initial_address = &a[init];
3677 if OFFSET is supplied:
3678 initial_address = &a[init + OFFSET];
3680 Return the initial_address in INITIAL_ADDRESS.
3682 2. If ONLY_INIT is true, just return the initial pointer. Otherwise, also
3683 update the pointer in each iteration of the loop.
3685 Return the increment stmt that updates the pointer in PTR_INCR.
3687 3. Set INV_P to true if the access pattern of the data reference in the
3688 vectorized loop is invariant. Set it to false otherwise.
3690 4. Return the pointer. */
3693 vect_create_data_ref_ptr (gimple stmt
, tree aggr_type
, struct loop
*at_loop
,
3694 tree offset
, tree
*initial_address
,
3695 gimple_stmt_iterator
*gsi
, gimple
*ptr_incr
,
3696 bool only_init
, bool *inv_p
)
3698 const char *base_name
;
3699 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3700 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3701 struct loop
*loop
= NULL
;
3702 bool nested_in_vect_loop
= false;
3703 struct loop
*containing_loop
= NULL
;
3708 gimple_seq new_stmt_list
= NULL
;
3712 struct data_reference
*dr
= STMT_VINFO_DATA_REF (stmt_info
);
3714 gimple_stmt_iterator incr_gsi
;
3716 tree indx_before_incr
, indx_after_incr
;
3719 bb_vec_info bb_vinfo
= STMT_VINFO_BB_VINFO (stmt_info
);
3721 gcc_assert (TREE_CODE (aggr_type
) == ARRAY_TYPE
3722 || TREE_CODE (aggr_type
) == VECTOR_TYPE
);
3726 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3727 nested_in_vect_loop
= nested_in_vect_loop_p (loop
, stmt
);
3728 containing_loop
= (gimple_bb (stmt
))->loop_father
;
3729 pe
= loop_preheader_edge (loop
);
3733 gcc_assert (bb_vinfo
);
3738 /* Check the step (evolution) of the load in LOOP, and record
3739 whether it's invariant. */
3740 if (nested_in_vect_loop
)
3741 step
= STMT_VINFO_DR_STEP (stmt_info
);
3743 step
= DR_STEP (STMT_VINFO_DATA_REF (stmt_info
));
3745 if (integer_zerop (step
))
3750 /* Create an expression for the first address accessed by this load
3752 base_name
= get_name (DR_BASE_ADDRESS (dr
));
3754 if (dump_enabled_p ())
3756 tree dr_base_type
= TREE_TYPE (DR_BASE_OBJECT (dr
));
3757 dump_printf_loc (MSG_NOTE
, vect_location
,
3758 "create %s-pointer variable to type: ",
3759 tree_code_name
[(int) TREE_CODE (aggr_type
)]);
3760 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, aggr_type
);
3761 if (TREE_CODE (dr_base_type
) == ARRAY_TYPE
)
3762 dump_printf (MSG_NOTE
, " vectorizing an array ref: ");
3763 else if (TREE_CODE (dr_base_type
) == VECTOR_TYPE
)
3764 dump_printf (MSG_NOTE
, " vectorizing a vector ref: ");
3765 else if (TREE_CODE (dr_base_type
) == RECORD_TYPE
)
3766 dump_printf (MSG_NOTE
, " vectorizing a record based array ref: ");
3768 dump_printf (MSG_NOTE
, " vectorizing a pointer ref: ");
3769 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_BASE_OBJECT (dr
));
3770 dump_printf (MSG_NOTE
, "\n");
3773 /* (1) Create the new aggregate-pointer variable.
3774 Vector and array types inherit the alias set of their component
3775 type by default so we need to use a ref-all pointer if the data
3776 reference does not conflict with the created aggregated data
3777 reference because it is not addressable. */
3778 bool need_ref_all
= false;
3779 if (!alias_sets_conflict_p (get_alias_set (aggr_type
),
3780 get_alias_set (DR_REF (dr
))))
3781 need_ref_all
= true;
3782 /* Likewise for any of the data references in the stmt group. */
3783 else if (STMT_VINFO_GROUP_SIZE (stmt_info
) > 1)
3785 gimple orig_stmt
= STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info
);
3788 stmt_vec_info sinfo
= vinfo_for_stmt (orig_stmt
);
3789 struct data_reference
*sdr
= STMT_VINFO_DATA_REF (sinfo
);
3790 if (!alias_sets_conflict_p (get_alias_set (aggr_type
),
3791 get_alias_set (DR_REF (sdr
))))
3793 need_ref_all
= true;
3796 orig_stmt
= STMT_VINFO_GROUP_NEXT_ELEMENT (sinfo
);
3800 aggr_ptr_type
= build_pointer_type_for_mode (aggr_type
, ptr_mode
,
3802 aggr_ptr
= vect_get_new_vect_var (aggr_ptr_type
, vect_pointer_var
, base_name
);
3805 /* Note: If the dataref is in an inner-loop nested in LOOP, and we are
3806 vectorizing LOOP (i.e., outer-loop vectorization), we need to create two
3807 def-use update cycles for the pointer: one relative to the outer-loop
3808 (LOOP), which is what steps (3) and (4) below do. The other is relative
3809 to the inner-loop (which is the inner-most loop containing the dataref),
3810 and this is done be step (5) below.
3812 When vectorizing inner-most loops, the vectorized loop (LOOP) is also the
3813 inner-most loop, and so steps (3),(4) work the same, and step (5) is
3814 redundant. Steps (3),(4) create the following:
3817 LOOP: vp1 = phi(vp0,vp2)
3823 If there is an inner-loop nested in loop, then step (5) will also be
3824 applied, and an additional update in the inner-loop will be created:
3827 LOOP: vp1 = phi(vp0,vp2)
3829 inner: vp3 = phi(vp1,vp4)
3830 vp4 = vp3 + inner_step
3836 /* (2) Calculate the initial address of the aggregate-pointer, and set
3837 the aggregate-pointer to point to it before the loop. */
3839 /* Create: (&(base[init_val+offset]) in the loop preheader. */
3841 new_temp
= vect_create_addr_base_for_vector_ref (stmt
, &new_stmt_list
,
3847 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, new_stmt_list
);
3848 gcc_assert (!new_bb
);
3851 gsi_insert_seq_before (gsi
, new_stmt_list
, GSI_SAME_STMT
);
3854 *initial_address
= new_temp
;
3856 /* Create: p = (aggr_type *) initial_base */
3857 if (TREE_CODE (new_temp
) != SSA_NAME
3858 || !useless_type_conversion_p (aggr_ptr_type
, TREE_TYPE (new_temp
)))
3860 vec_stmt
= gimple_build_assign (aggr_ptr
,
3861 fold_convert (aggr_ptr_type
, new_temp
));
3862 aggr_ptr_init
= make_ssa_name (aggr_ptr
, vec_stmt
);
3863 /* Copy the points-to information if it exists. */
3864 if (DR_PTR_INFO (dr
))
3865 duplicate_ssa_name_ptr_info (aggr_ptr_init
, DR_PTR_INFO (dr
));
3866 gimple_assign_set_lhs (vec_stmt
, aggr_ptr_init
);
3869 new_bb
= gsi_insert_on_edge_immediate (pe
, vec_stmt
);
3870 gcc_assert (!new_bb
);
3873 gsi_insert_before (gsi
, vec_stmt
, GSI_SAME_STMT
);
3876 aggr_ptr_init
= new_temp
;
3878 /* (3) Handle the updating of the aggregate-pointer inside the loop.
3879 This is needed when ONLY_INIT is false, and also when AT_LOOP is the
3880 inner-loop nested in LOOP (during outer-loop vectorization). */
3882 /* No update in loop is required. */
3883 if (only_init
&& (!loop_vinfo
|| at_loop
== loop
))
3884 aptr
= aggr_ptr_init
;
3887 /* The step of the aggregate pointer is the type size. */
3888 tree iv_step
= TYPE_SIZE_UNIT (aggr_type
);
3889 /* One exception to the above is when the scalar step of the load in
3890 LOOP is zero. In this case the step here is also zero. */
3892 iv_step
= size_zero_node
;
3893 else if (tree_int_cst_sgn (step
) == -1)
3894 iv_step
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (iv_step
), iv_step
);
3896 standard_iv_increment_position (loop
, &incr_gsi
, &insert_after
);
3898 create_iv (aggr_ptr_init
,
3899 fold_convert (aggr_ptr_type
, iv_step
),
3900 aggr_ptr
, loop
, &incr_gsi
, insert_after
,
3901 &indx_before_incr
, &indx_after_incr
);
3902 incr
= gsi_stmt (incr_gsi
);
3903 set_vinfo_for_stmt (incr
, new_stmt_vec_info (incr
, loop_vinfo
, NULL
));
3905 /* Copy the points-to information if it exists. */
3906 if (DR_PTR_INFO (dr
))
3908 duplicate_ssa_name_ptr_info (indx_before_incr
, DR_PTR_INFO (dr
));
3909 duplicate_ssa_name_ptr_info (indx_after_incr
, DR_PTR_INFO (dr
));
3914 aptr
= indx_before_incr
;
3917 if (!nested_in_vect_loop
|| only_init
)
3921 /* (4) Handle the updating of the aggregate-pointer inside the inner-loop
3922 nested in LOOP, if exists. */
3924 gcc_assert (nested_in_vect_loop
);
3927 standard_iv_increment_position (containing_loop
, &incr_gsi
,
3929 create_iv (aptr
, fold_convert (aggr_ptr_type
, DR_STEP (dr
)), aggr_ptr
,
3930 containing_loop
, &incr_gsi
, insert_after
, &indx_before_incr
,
3932 incr
= gsi_stmt (incr_gsi
);
3933 set_vinfo_for_stmt (incr
, new_stmt_vec_info (incr
, loop_vinfo
, NULL
));
3935 /* Copy the points-to information if it exists. */
3936 if (DR_PTR_INFO (dr
))
3938 duplicate_ssa_name_ptr_info (indx_before_incr
, DR_PTR_INFO (dr
));
3939 duplicate_ssa_name_ptr_info (indx_after_incr
, DR_PTR_INFO (dr
));
3944 return indx_before_incr
;
3951 /* Function bump_vector_ptr
3953 Increment a pointer (to a vector type) by vector-size. If requested,
3954 i.e. if PTR-INCR is given, then also connect the new increment stmt
3955 to the existing def-use update-chain of the pointer, by modifying
3956 the PTR_INCR as illustrated below:
3958 The pointer def-use update-chain before this function:
3959 DATAREF_PTR = phi (p_0, p_2)
3961 PTR_INCR: p_2 = DATAREF_PTR + step
3963 The pointer def-use update-chain after this function:
3964 DATAREF_PTR = phi (p_0, p_2)
3966 NEW_DATAREF_PTR = DATAREF_PTR + BUMP
3968 PTR_INCR: p_2 = NEW_DATAREF_PTR + step
3971 DATAREF_PTR - ssa_name of a pointer (to vector type) that is being updated
3973 PTR_INCR - optional. The stmt that updates the pointer in each iteration of
3974 the loop. The increment amount across iterations is expected
3976 BSI - location where the new update stmt is to be placed.
3977 STMT - the original scalar memory-access stmt that is being vectorized.
3978 BUMP - optional. The offset by which to bump the pointer. If not given,
3979 the offset is assumed to be vector_size.
3981 Output: Return NEW_DATAREF_PTR as illustrated above.
3986 bump_vector_ptr (tree dataref_ptr
, gimple ptr_incr
, gimple_stmt_iterator
*gsi
,
3987 gimple stmt
, tree bump
)
3989 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3990 struct data_reference
*dr
= STMT_VINFO_DATA_REF (stmt_info
);
3991 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
3992 tree update
= TYPE_SIZE_UNIT (vectype
);
3995 use_operand_p use_p
;
3996 tree new_dataref_ptr
;
4001 new_dataref_ptr
= copy_ssa_name (dataref_ptr
, NULL
);
4002 incr_stmt
= gimple_build_assign_with_ops (POINTER_PLUS_EXPR
, new_dataref_ptr
,
4003 dataref_ptr
, update
);
4004 vect_finish_stmt_generation (stmt
, incr_stmt
, gsi
);
4006 /* Copy the points-to information if it exists. */
4007 if (DR_PTR_INFO (dr
))
4009 duplicate_ssa_name_ptr_info (new_dataref_ptr
, DR_PTR_INFO (dr
));
4010 mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (new_dataref_ptr
));
4014 return new_dataref_ptr
;
4016 /* Update the vector-pointer's cross-iteration increment. */
4017 FOR_EACH_SSA_USE_OPERAND (use_p
, ptr_incr
, iter
, SSA_OP_USE
)
4019 tree use
= USE_FROM_PTR (use_p
);
4021 if (use
== dataref_ptr
)
4022 SET_USE (use_p
, new_dataref_ptr
);
4024 gcc_assert (tree_int_cst_compare (use
, update
) == 0);
4027 return new_dataref_ptr
;
4031 /* Function vect_create_destination_var.
4033 Create a new temporary of type VECTYPE. */
4036 vect_create_destination_var (tree scalar_dest
, tree vectype
)
4042 enum vect_var_kind kind
;
4044 kind
= vectype
? vect_simple_var
: vect_scalar_var
;
4045 type
= vectype
? vectype
: TREE_TYPE (scalar_dest
);
4047 gcc_assert (TREE_CODE (scalar_dest
) == SSA_NAME
);
4049 name
= get_name (scalar_dest
);
4051 asprintf (&new_name
, "%s_%u", name
, SSA_NAME_VERSION (scalar_dest
));
4053 asprintf (&new_name
, "_%u", SSA_NAME_VERSION (scalar_dest
));
4054 vec_dest
= vect_get_new_vect_var (type
, kind
, new_name
);
4060 /* Function vect_grouped_store_supported.
4062 Returns TRUE if interleave high and interleave low permutations
4063 are supported, and FALSE otherwise. */
4066 vect_grouped_store_supported (tree vectype
, unsigned HOST_WIDE_INT count
)
4068 enum machine_mode mode
= TYPE_MODE (vectype
);
4070 /* vect_permute_store_chain requires the group size to be a power of two. */
4071 if (exact_log2 (count
) == -1)
4073 if (dump_enabled_p ())
4074 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4075 "the size of the group of accesses"
4076 " is not a power of 2\n");
4080 /* Check that the permutation is supported. */
4081 if (VECTOR_MODE_P (mode
))
4083 unsigned int i
, nelt
= GET_MODE_NUNITS (mode
);
4084 unsigned char *sel
= XALLOCAVEC (unsigned char, nelt
);
4085 for (i
= 0; i
< nelt
/ 2; i
++)
4088 sel
[i
* 2 + 1] = i
+ nelt
;
4090 if (can_vec_perm_p (mode
, false, sel
))
4092 for (i
= 0; i
< nelt
; i
++)
4094 if (can_vec_perm_p (mode
, false, sel
))
4099 if (dump_enabled_p ())
4100 dump_printf (MSG_MISSED_OPTIMIZATION
,
4101 "interleave op not supported by target.\n");
4106 /* Return TRUE if vec_store_lanes is available for COUNT vectors of
4110 vect_store_lanes_supported (tree vectype
, unsigned HOST_WIDE_INT count
)
4112 return vect_lanes_optab_supported_p ("vec_store_lanes",
4113 vec_store_lanes_optab
,
4118 /* Function vect_permute_store_chain.
4120 Given a chain of interleaved stores in DR_CHAIN of LENGTH that must be
4121 a power of 2, generate interleave_high/low stmts to reorder the data
4122 correctly for the stores. Return the final references for stores in
4125 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
4126 The input is 4 vectors each containing 8 elements. We assign a number to
4127 each element, the input sequence is:
4129 1st vec: 0 1 2 3 4 5 6 7
4130 2nd vec: 8 9 10 11 12 13 14 15
4131 3rd vec: 16 17 18 19 20 21 22 23
4132 4th vec: 24 25 26 27 28 29 30 31
4134 The output sequence should be:
4136 1st vec: 0 8 16 24 1 9 17 25
4137 2nd vec: 2 10 18 26 3 11 19 27
4138 3rd vec: 4 12 20 28 5 13 21 30
4139 4th vec: 6 14 22 30 7 15 23 31
4141 i.e., we interleave the contents of the four vectors in their order.
4143 We use interleave_high/low instructions to create such output. The input of
4144 each interleave_high/low operation is two vectors:
4147 the even elements of the result vector are obtained left-to-right from the
4148 high/low elements of the first vector. The odd elements of the result are
4149 obtained left-to-right from the high/low elements of the second vector.
4150 The output of interleave_high will be: 0 4 1 5
4151 and of interleave_low: 2 6 3 7
4154 The permutation is done in log LENGTH stages. In each stage interleave_high
4155 and interleave_low stmts are created for each pair of vectors in DR_CHAIN,
4156 where the first argument is taken from the first half of DR_CHAIN and the
4157 second argument from it's second half.
4160 I1: interleave_high (1st vec, 3rd vec)
4161 I2: interleave_low (1st vec, 3rd vec)
4162 I3: interleave_high (2nd vec, 4th vec)
4163 I4: interleave_low (2nd vec, 4th vec)
4165 The output for the first stage is:
4167 I1: 0 16 1 17 2 18 3 19
4168 I2: 4 20 5 21 6 22 7 23
4169 I3: 8 24 9 25 10 26 11 27
4170 I4: 12 28 13 29 14 30 15 31
4172 The output of the second stage, i.e. the final result is:
4174 I1: 0 8 16 24 1 9 17 25
4175 I2: 2 10 18 26 3 11 19 27
4176 I3: 4 12 20 28 5 13 21 30
4177 I4: 6 14 22 30 7 15 23 31. */
4180 vect_permute_store_chain (vec
<tree
> dr_chain
,
4181 unsigned int length
,
4183 gimple_stmt_iterator
*gsi
,
4184 vec
<tree
> *result_chain
)
4186 tree vect1
, vect2
, high
, low
;
4188 tree vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
4189 tree perm_mask_low
, perm_mask_high
;
4191 unsigned int j
, nelt
= TYPE_VECTOR_SUBPARTS (vectype
);
4192 unsigned char *sel
= XALLOCAVEC (unsigned char, nelt
);
4194 result_chain
->quick_grow (length
);
4195 memcpy (result_chain
->address (), dr_chain
.address (),
4196 length
* sizeof (tree
));
4198 for (i
= 0, n
= nelt
/ 2; i
< n
; i
++)
4201 sel
[i
* 2 + 1] = i
+ nelt
;
4203 perm_mask_high
= vect_gen_perm_mask (vectype
, sel
);
4204 gcc_assert (perm_mask_high
!= NULL
);
4206 for (i
= 0; i
< nelt
; i
++)
4208 perm_mask_low
= vect_gen_perm_mask (vectype
, sel
);
4209 gcc_assert (perm_mask_low
!= NULL
);
4211 for (i
= 0, n
= exact_log2 (length
); i
< n
; i
++)
4213 for (j
= 0; j
< length
/2; j
++)
4215 vect1
= dr_chain
[j
];
4216 vect2
= dr_chain
[j
+length
/2];
4218 /* Create interleaving stmt:
4219 high = VEC_PERM_EXPR <vect1, vect2, {0, nelt, 1, nelt+1, ...}> */
4220 high
= make_temp_ssa_name (vectype
, NULL
, "vect_inter_high");
4222 = gimple_build_assign_with_ops (VEC_PERM_EXPR
, high
,
4223 vect1
, vect2
, perm_mask_high
);
4224 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
4225 (*result_chain
)[2*j
] = high
;
4227 /* Create interleaving stmt:
4228 low = VEC_PERM_EXPR <vect1, vect2, {nelt/2, nelt*3/2, nelt/2+1,
4229 nelt*3/2+1, ...}> */
4230 low
= make_temp_ssa_name (vectype
, NULL
, "vect_inter_low");
4232 = gimple_build_assign_with_ops (VEC_PERM_EXPR
, low
,
4233 vect1
, vect2
, perm_mask_low
);
4234 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
4235 (*result_chain
)[2*j
+1] = low
;
4237 memcpy (dr_chain
.address (), result_chain
->address (),
4238 length
* sizeof (tree
));
4242 /* Function vect_setup_realignment
4244 This function is called when vectorizing an unaligned load using
4245 the dr_explicit_realign[_optimized] scheme.
4246 This function generates the following code at the loop prolog:
4249 x msq_init = *(floor(p)); # prolog load
4250 realignment_token = call target_builtin;
4252 x msq = phi (msq_init, ---)
4254 The stmts marked with x are generated only for the case of
4255 dr_explicit_realign_optimized.
4257 The code above sets up a new (vector) pointer, pointing to the first
4258 location accessed by STMT, and a "floor-aligned" load using that pointer.
4259 It also generates code to compute the "realignment-token" (if the relevant
4260 target hook was defined), and creates a phi-node at the loop-header bb
4261 whose arguments are the result of the prolog-load (created by this
4262 function) and the result of a load that takes place in the loop (to be
4263 created by the caller to this function).
4265 For the case of dr_explicit_realign_optimized:
4266 The caller to this function uses the phi-result (msq) to create the
4267 realignment code inside the loop, and sets up the missing phi argument,
4270 msq = phi (msq_init, lsq)
4271 lsq = *(floor(p')); # load in loop
4272 result = realign_load (msq, lsq, realignment_token);
4274 For the case of dr_explicit_realign:
4276 msq = *(floor(p)); # load in loop
4278 lsq = *(floor(p')); # load in loop
4279 result = realign_load (msq, lsq, realignment_token);
4282 STMT - (scalar) load stmt to be vectorized. This load accesses
4283 a memory location that may be unaligned.
4284 BSI - place where new code is to be inserted.
4285 ALIGNMENT_SUPPORT_SCHEME - which of the two misalignment handling schemes
4289 REALIGNMENT_TOKEN - the result of a call to the builtin_mask_for_load
4290 target hook, if defined.
4291 Return value - the result of the loop-header phi node. */
4294 vect_setup_realignment (gimple stmt
, gimple_stmt_iterator
*gsi
,
4295 tree
*realignment_token
,
4296 enum dr_alignment_support alignment_support_scheme
,
4298 struct loop
**at_loop
)
4300 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
4301 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
4302 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
4303 struct data_reference
*dr
= STMT_VINFO_DATA_REF (stmt_info
);
4304 struct loop
*loop
= NULL
;
4306 tree scalar_dest
= gimple_assign_lhs (stmt
);
4313 tree msq_init
= NULL_TREE
;
4316 tree msq
= NULL_TREE
;
4317 gimple_seq stmts
= NULL
;
4319 bool compute_in_loop
= false;
4320 bool nested_in_vect_loop
= false;
4321 struct loop
*containing_loop
= (gimple_bb (stmt
))->loop_father
;
4322 struct loop
*loop_for_initial_load
= NULL
;
4326 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4327 nested_in_vect_loop
= nested_in_vect_loop_p (loop
, stmt
);
4330 gcc_assert (alignment_support_scheme
== dr_explicit_realign
4331 || alignment_support_scheme
== dr_explicit_realign_optimized
);
4333 /* We need to generate three things:
4334 1. the misalignment computation
4335 2. the extra vector load (for the optimized realignment scheme).
4336 3. the phi node for the two vectors from which the realignment is
4337 done (for the optimized realignment scheme). */
4339 /* 1. Determine where to generate the misalignment computation.
4341 If INIT_ADDR is NULL_TREE, this indicates that the misalignment
4342 calculation will be generated by this function, outside the loop (in the
4343 preheader). Otherwise, INIT_ADDR had already been computed for us by the
4344 caller, inside the loop.
4346 Background: If the misalignment remains fixed throughout the iterations of
4347 the loop, then both realignment schemes are applicable, and also the
4348 misalignment computation can be done outside LOOP. This is because we are
4349 vectorizing LOOP, and so the memory accesses in LOOP advance in steps that
4350 are a multiple of VS (the Vector Size), and therefore the misalignment in
4351 different vectorized LOOP iterations is always the same.
4352 The problem arises only if the memory access is in an inner-loop nested
4353 inside LOOP, which is now being vectorized using outer-loop vectorization.
4354 This is the only case when the misalignment of the memory access may not
4355 remain fixed throughout the iterations of the inner-loop (as explained in
4356 detail in vect_supportable_dr_alignment). In this case, not only is the
4357 optimized realignment scheme not applicable, but also the misalignment
4358 computation (and generation of the realignment token that is passed to
4359 REALIGN_LOAD) have to be done inside the loop.
4361 In short, INIT_ADDR indicates whether we are in a COMPUTE_IN_LOOP mode
4362 or not, which in turn determines if the misalignment is computed inside
4363 the inner-loop, or outside LOOP. */
4365 if (init_addr
!= NULL_TREE
|| !loop_vinfo
)
4367 compute_in_loop
= true;
4368 gcc_assert (alignment_support_scheme
== dr_explicit_realign
);
4372 /* 2. Determine where to generate the extra vector load.
4374 For the optimized realignment scheme, instead of generating two vector
4375 loads in each iteration, we generate a single extra vector load in the
4376 preheader of the loop, and in each iteration reuse the result of the
4377 vector load from the previous iteration. In case the memory access is in
4378 an inner-loop nested inside LOOP, which is now being vectorized using
4379 outer-loop vectorization, we need to determine whether this initial vector
4380 load should be generated at the preheader of the inner-loop, or can be
4381 generated at the preheader of LOOP. If the memory access has no evolution
4382 in LOOP, it can be generated in the preheader of LOOP. Otherwise, it has
4383 to be generated inside LOOP (in the preheader of the inner-loop). */
4385 if (nested_in_vect_loop
)
4387 tree outerloop_step
= STMT_VINFO_DR_STEP (stmt_info
);
4388 bool invariant_in_outerloop
=
4389 (tree_int_cst_compare (outerloop_step
, size_zero_node
) == 0);
4390 loop_for_initial_load
= (invariant_in_outerloop
? loop
: loop
->inner
);
4393 loop_for_initial_load
= loop
;
4395 *at_loop
= loop_for_initial_load
;
4397 if (loop_for_initial_load
)
4398 pe
= loop_preheader_edge (loop_for_initial_load
);
4400 /* 3. For the case of the optimized realignment, create the first vector
4401 load at the loop preheader. */
4403 if (alignment_support_scheme
== dr_explicit_realign_optimized
)
4405 /* Create msq_init = *(floor(p1)) in the loop preheader */
4407 gcc_assert (!compute_in_loop
);
4408 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4409 ptr
= vect_create_data_ref_ptr (stmt
, vectype
, loop_for_initial_load
,
4410 NULL_TREE
, &init_addr
, NULL
, &inc
,
4412 new_temp
= copy_ssa_name (ptr
, NULL
);
4413 new_stmt
= gimple_build_assign_with_ops
4414 (BIT_AND_EXPR
, new_temp
, ptr
,
4415 build_int_cst (TREE_TYPE (ptr
),
4416 -(HOST_WIDE_INT
)TYPE_ALIGN_UNIT (vectype
)));
4417 new_bb
= gsi_insert_on_edge_immediate (pe
, new_stmt
);
4418 gcc_assert (!new_bb
);
4420 = build2 (MEM_REF
, TREE_TYPE (vec_dest
), new_temp
,
4421 build_int_cst (reference_alias_ptr_type (DR_REF (dr
)), 0));
4422 new_stmt
= gimple_build_assign (vec_dest
, data_ref
);
4423 new_temp
= make_ssa_name (vec_dest
, new_stmt
);
4424 gimple_assign_set_lhs (new_stmt
, new_temp
);
4427 new_bb
= gsi_insert_on_edge_immediate (pe
, new_stmt
);
4428 gcc_assert (!new_bb
);
4431 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
4433 msq_init
= gimple_assign_lhs (new_stmt
);
4436 /* 4. Create realignment token using a target builtin, if available.
4437 It is done either inside the containing loop, or before LOOP (as
4438 determined above). */
4440 if (targetm
.vectorize
.builtin_mask_for_load
)
4444 /* Compute INIT_ADDR - the initial addressed accessed by this memref. */
4447 /* Generate the INIT_ADDR computation outside LOOP. */
4448 init_addr
= vect_create_addr_base_for_vector_ref (stmt
, &stmts
,
4452 pe
= loop_preheader_edge (loop
);
4453 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
4454 gcc_assert (!new_bb
);
4457 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
4460 builtin_decl
= targetm
.vectorize
.builtin_mask_for_load ();
4461 new_stmt
= gimple_build_call (builtin_decl
, 1, init_addr
);
4463 vect_create_destination_var (scalar_dest
,
4464 gimple_call_return_type (new_stmt
));
4465 new_temp
= make_ssa_name (vec_dest
, new_stmt
);
4466 gimple_call_set_lhs (new_stmt
, new_temp
);
4468 if (compute_in_loop
)
4469 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
4472 /* Generate the misalignment computation outside LOOP. */
4473 pe
= loop_preheader_edge (loop
);
4474 new_bb
= gsi_insert_on_edge_immediate (pe
, new_stmt
);
4475 gcc_assert (!new_bb
);
4478 *realignment_token
= gimple_call_lhs (new_stmt
);
4480 /* The result of the CALL_EXPR to this builtin is determined from
4481 the value of the parameter and no global variables are touched
4482 which makes the builtin a "const" function. Requiring the
4483 builtin to have the "const" attribute makes it unnecessary
4484 to call mark_call_clobbered. */
4485 gcc_assert (TREE_READONLY (builtin_decl
));
4488 if (alignment_support_scheme
== dr_explicit_realign
)
4491 gcc_assert (!compute_in_loop
);
4492 gcc_assert (alignment_support_scheme
== dr_explicit_realign_optimized
);
4495 /* 5. Create msq = phi <msq_init, lsq> in loop */
4497 pe
= loop_preheader_edge (containing_loop
);
4498 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4499 msq
= make_ssa_name (vec_dest
, NULL
);
4500 phi_stmt
= create_phi_node (msq
, containing_loop
->header
);
4501 add_phi_arg (phi_stmt
, msq_init
, pe
, UNKNOWN_LOCATION
);
4507 /* Function vect_grouped_load_supported.
4509 Returns TRUE if even and odd permutations are supported,
4510 and FALSE otherwise. */
4513 vect_grouped_load_supported (tree vectype
, unsigned HOST_WIDE_INT count
)
4515 enum machine_mode mode
= TYPE_MODE (vectype
);
4517 /* vect_permute_load_chain requires the group size to be a power of two. */
4518 if (exact_log2 (count
) == -1)
4520 if (dump_enabled_p ())
4521 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4522 "the size of the group of accesses"
4523 " is not a power of 2\n");
4527 /* Check that the permutation is supported. */
4528 if (VECTOR_MODE_P (mode
))
4530 unsigned int i
, nelt
= GET_MODE_NUNITS (mode
);
4531 unsigned char *sel
= XALLOCAVEC (unsigned char, nelt
);
4533 for (i
= 0; i
< nelt
; i
++)
4535 if (can_vec_perm_p (mode
, false, sel
))
4537 for (i
= 0; i
< nelt
; i
++)
4539 if (can_vec_perm_p (mode
, false, sel
))
4544 if (dump_enabled_p ())
4545 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4546 "extract even/odd not supported by target\n");
4550 /* Return TRUE if vec_load_lanes is available for COUNT vectors of
4554 vect_load_lanes_supported (tree vectype
, unsigned HOST_WIDE_INT count
)
4556 return vect_lanes_optab_supported_p ("vec_load_lanes",
4557 vec_load_lanes_optab
,
4561 /* Function vect_permute_load_chain.
4563 Given a chain of interleaved loads in DR_CHAIN of LENGTH that must be
4564 a power of 2, generate extract_even/odd stmts to reorder the input data
4565 correctly. Return the final references for loads in RESULT_CHAIN.
4567 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
4568 The input is 4 vectors each containing 8 elements. We assign a number to each
4569 element, the input sequence is:
4571 1st vec: 0 1 2 3 4 5 6 7
4572 2nd vec: 8 9 10 11 12 13 14 15
4573 3rd vec: 16 17 18 19 20 21 22 23
4574 4th vec: 24 25 26 27 28 29 30 31
4576 The output sequence should be:
4578 1st vec: 0 4 8 12 16 20 24 28
4579 2nd vec: 1 5 9 13 17 21 25 29
4580 3rd vec: 2 6 10 14 18 22 26 30
4581 4th vec: 3 7 11 15 19 23 27 31
4583 i.e., the first output vector should contain the first elements of each
4584 interleaving group, etc.
4586 We use extract_even/odd instructions to create such output. The input of
4587 each extract_even/odd operation is two vectors
4591 and the output is the vector of extracted even/odd elements. The output of
4592 extract_even will be: 0 2 4 6
4593 and of extract_odd: 1 3 5 7
4596 The permutation is done in log LENGTH stages. In each stage extract_even
4597 and extract_odd stmts are created for each pair of vectors in DR_CHAIN in
4598 their order. In our example,
4600 E1: extract_even (1st vec, 2nd vec)
4601 E2: extract_odd (1st vec, 2nd vec)
4602 E3: extract_even (3rd vec, 4th vec)
4603 E4: extract_odd (3rd vec, 4th vec)
4605 The output for the first stage will be:
4607 E1: 0 2 4 6 8 10 12 14
4608 E2: 1 3 5 7 9 11 13 15
4609 E3: 16 18 20 22 24 26 28 30
4610 E4: 17 19 21 23 25 27 29 31
4612 In order to proceed and create the correct sequence for the next stage (or
4613 for the correct output, if the second stage is the last one, as in our
4614 example), we first put the output of extract_even operation and then the
4615 output of extract_odd in RESULT_CHAIN (which is then copied to DR_CHAIN).
4616 The input for the second stage is:
4618 1st vec (E1): 0 2 4 6 8 10 12 14
4619 2nd vec (E3): 16 18 20 22 24 26 28 30
4620 3rd vec (E2): 1 3 5 7 9 11 13 15
4621 4th vec (E4): 17 19 21 23 25 27 29 31
4623 The output of the second stage:
4625 E1: 0 4 8 12 16 20 24 28
4626 E2: 2 6 10 14 18 22 26 30
4627 E3: 1 5 9 13 17 21 25 29
4628 E4: 3 7 11 15 19 23 27 31
4630 And RESULT_CHAIN after reordering:
4632 1st vec (E1): 0 4 8 12 16 20 24 28
4633 2nd vec (E3): 1 5 9 13 17 21 25 29
4634 3rd vec (E2): 2 6 10 14 18 22 26 30
4635 4th vec (E4): 3 7 11 15 19 23 27 31. */
4638 vect_permute_load_chain (vec
<tree
> dr_chain
,
4639 unsigned int length
,
4641 gimple_stmt_iterator
*gsi
,
4642 vec
<tree
> *result_chain
)
4644 tree data_ref
, first_vect
, second_vect
;
4645 tree perm_mask_even
, perm_mask_odd
;
4647 tree vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
4648 unsigned int i
, j
, log_length
= exact_log2 (length
);
4649 unsigned nelt
= TYPE_VECTOR_SUBPARTS (vectype
);
4650 unsigned char *sel
= XALLOCAVEC (unsigned char, nelt
);
4652 result_chain
->quick_grow (length
);
4653 memcpy (result_chain
->address (), dr_chain
.address (),
4654 length
* sizeof (tree
));
4656 for (i
= 0; i
< nelt
; ++i
)
4658 perm_mask_even
= vect_gen_perm_mask (vectype
, sel
);
4659 gcc_assert (perm_mask_even
!= NULL
);
4661 for (i
= 0; i
< nelt
; ++i
)
4663 perm_mask_odd
= vect_gen_perm_mask (vectype
, sel
);
4664 gcc_assert (perm_mask_odd
!= NULL
);
4666 for (i
= 0; i
< log_length
; i
++)
4668 for (j
= 0; j
< length
; j
+= 2)
4670 first_vect
= dr_chain
[j
];
4671 second_vect
= dr_chain
[j
+1];
4673 /* data_ref = permute_even (first_data_ref, second_data_ref); */
4674 data_ref
= make_temp_ssa_name (vectype
, NULL
, "vect_perm_even");
4675 perm_stmt
= gimple_build_assign_with_ops (VEC_PERM_EXPR
, data_ref
,
4676 first_vect
, second_vect
,
4678 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
4679 (*result_chain
)[j
/2] = data_ref
;
4681 /* data_ref = permute_odd (first_data_ref, second_data_ref); */
4682 data_ref
= make_temp_ssa_name (vectype
, NULL
, "vect_perm_odd");
4683 perm_stmt
= gimple_build_assign_with_ops (VEC_PERM_EXPR
, data_ref
,
4684 first_vect
, second_vect
,
4686 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
4687 (*result_chain
)[j
/2+length
/2] = data_ref
;
4689 memcpy (dr_chain
.address (), result_chain
->address (),
4690 length
* sizeof (tree
));
4695 /* Function vect_transform_grouped_load.
4697 Given a chain of input interleaved data-refs (in DR_CHAIN), build statements
4698 to perform their permutation and ascribe the result vectorized statements to
4699 the scalar statements.
4703 vect_transform_grouped_load (gimple stmt
, vec
<tree
> dr_chain
, int size
,
4704 gimple_stmt_iterator
*gsi
)
4706 vec
<tree
> result_chain
= vNULL
;
4708 /* DR_CHAIN contains input data-refs that are a part of the interleaving.
4709 RESULT_CHAIN is the output of vect_permute_load_chain, it contains permuted
4710 vectors, that are ready for vector computation. */
4711 result_chain
.create (size
);
4712 vect_permute_load_chain (dr_chain
, size
, stmt
, gsi
, &result_chain
);
4713 vect_record_grouped_load_vectors (stmt
, result_chain
);
4714 result_chain
.release ();
4717 /* RESULT_CHAIN contains the output of a group of grouped loads that were
4718 generated as part of the vectorization of STMT. Assign the statement
4719 for each vector to the associated scalar statement. */
4722 vect_record_grouped_load_vectors (gimple stmt
, vec
<tree
> result_chain
)
4724 gimple first_stmt
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
));
4725 gimple next_stmt
, new_stmt
;
4726 unsigned int i
, gap_count
;
4729 /* Put a permuted data-ref in the VECTORIZED_STMT field.
4730 Since we scan the chain starting from it's first node, their order
4731 corresponds the order of data-refs in RESULT_CHAIN. */
4732 next_stmt
= first_stmt
;
4734 FOR_EACH_VEC_ELT (result_chain
, i
, tmp_data_ref
)
4739 /* Skip the gaps. Loads created for the gaps will be removed by dead
4740 code elimination pass later. No need to check for the first stmt in
4741 the group, since it always exists.
4742 GROUP_GAP is the number of steps in elements from the previous
4743 access (if there is no gap GROUP_GAP is 1). We skip loads that
4744 correspond to the gaps. */
4745 if (next_stmt
!= first_stmt
4746 && gap_count
< GROUP_GAP (vinfo_for_stmt (next_stmt
)))
4754 new_stmt
= SSA_NAME_DEF_STMT (tmp_data_ref
);
4755 /* We assume that if VEC_STMT is not NULL, this is a case of multiple
4756 copies, and we put the new vector statement in the first available
4758 if (!STMT_VINFO_VEC_STMT (vinfo_for_stmt (next_stmt
)))
4759 STMT_VINFO_VEC_STMT (vinfo_for_stmt (next_stmt
)) = new_stmt
;
4762 if (!GROUP_SAME_DR_STMT (vinfo_for_stmt (next_stmt
)))
4765 STMT_VINFO_VEC_STMT (vinfo_for_stmt (next_stmt
));
4767 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (prev_stmt
));
4770 prev_stmt
= rel_stmt
;
4772 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (rel_stmt
));
4775 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (prev_stmt
)) =
4780 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
4782 /* If NEXT_STMT accesses the same DR as the previous statement,
4783 put the same TMP_DATA_REF as its vectorized statement; otherwise
4784 get the next data-ref from RESULT_CHAIN. */
4785 if (!next_stmt
|| !GROUP_SAME_DR_STMT (vinfo_for_stmt (next_stmt
)))
4791 /* Function vect_force_dr_alignment_p.
4793 Returns whether the alignment of a DECL can be forced to be aligned
4794 on ALIGNMENT bit boundary. */
4797 vect_can_force_dr_alignment_p (const_tree decl
, unsigned int alignment
)
4799 if (TREE_CODE (decl
) != VAR_DECL
)
4802 /* We cannot change alignment of common or external symbols as another
4803 translation unit may contain a definition with lower alignment.
4804 The rules of common symbol linking mean that the definition
4805 will override the common symbol. The same is true for constant
4806 pool entries which may be shared and are not properly merged
4808 if (DECL_EXTERNAL (decl
)
4809 || DECL_COMMON (decl
)
4810 || DECL_IN_CONSTANT_POOL (decl
))
4813 if (TREE_ASM_WRITTEN (decl
))
4816 /* Do not override the alignment as specified by the ABI when the used
4817 attribute is set. */
4818 if (DECL_PRESERVE_P (decl
))
4821 /* Do not override explicit alignment set by the user when an explicit
4822 section name is also used. This is a common idiom used by many
4823 software projects. */
4824 if (DECL_SECTION_NAME (decl
) != NULL_TREE
4825 && !DECL_HAS_IMPLICIT_SECTION_NAME_P (decl
))
4828 if (TREE_STATIC (decl
))
4829 return (alignment
<= MAX_OFILE_ALIGNMENT
);
4831 return (alignment
<= MAX_STACK_ALIGNMENT
);
4835 /* Return whether the data reference DR is supported with respect to its
4837 If CHECK_ALIGNED_ACCESSES is TRUE, check if the access is supported even
4838 it is aligned, i.e., check if it is possible to vectorize it with different
4841 enum dr_alignment_support
4842 vect_supportable_dr_alignment (struct data_reference
*dr
,
4843 bool check_aligned_accesses
)
4845 gimple stmt
= DR_STMT (dr
);
4846 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
4847 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
4848 enum machine_mode mode
= TYPE_MODE (vectype
);
4849 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
4850 struct loop
*vect_loop
= NULL
;
4851 bool nested_in_vect_loop
= false;
4853 if (aligned_access_p (dr
) && !check_aligned_accesses
)
4858 vect_loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4859 nested_in_vect_loop
= nested_in_vect_loop_p (vect_loop
, stmt
);
4862 /* Possibly unaligned access. */
4864 /* We can choose between using the implicit realignment scheme (generating
4865 a misaligned_move stmt) and the explicit realignment scheme (generating
4866 aligned loads with a REALIGN_LOAD). There are two variants to the
4867 explicit realignment scheme: optimized, and unoptimized.
4868 We can optimize the realignment only if the step between consecutive
4869 vector loads is equal to the vector size. Since the vector memory
4870 accesses advance in steps of VS (Vector Size) in the vectorized loop, it
4871 is guaranteed that the misalignment amount remains the same throughout the
4872 execution of the vectorized loop. Therefore, we can create the
4873 "realignment token" (the permutation mask that is passed to REALIGN_LOAD)
4874 at the loop preheader.
4876 However, in the case of outer-loop vectorization, when vectorizing a
4877 memory access in the inner-loop nested within the LOOP that is now being
4878 vectorized, while it is guaranteed that the misalignment of the
4879 vectorized memory access will remain the same in different outer-loop
4880 iterations, it is *not* guaranteed that is will remain the same throughout
4881 the execution of the inner-loop. This is because the inner-loop advances
4882 with the original scalar step (and not in steps of VS). If the inner-loop
4883 step happens to be a multiple of VS, then the misalignment remains fixed
4884 and we can use the optimized realignment scheme. For example:
4890 When vectorizing the i-loop in the above example, the step between
4891 consecutive vector loads is 1, and so the misalignment does not remain
4892 fixed across the execution of the inner-loop, and the realignment cannot
4893 be optimized (as illustrated in the following pseudo vectorized loop):
4895 for (i=0; i<N; i+=4)
4896 for (j=0; j<M; j++){
4897 vs += vp[i+j]; // misalignment of &vp[i+j] is {0,1,2,3,0,1,2,3,...}
4898 // when j is {0,1,2,3,4,5,6,7,...} respectively.
4899 // (assuming that we start from an aligned address).
4902 We therefore have to use the unoptimized realignment scheme:
4904 for (i=0; i<N; i+=4)
4905 for (j=k; j<M; j+=4)
4906 vs += vp[i+j]; // misalignment of &vp[i+j] is always k (assuming
4907 // that the misalignment of the initial address is
4910 The loop can then be vectorized as follows:
4912 for (k=0; k<4; k++){
4913 rt = get_realignment_token (&vp[k]);
4914 for (i=0; i<N; i+=4){
4916 for (j=k; j<M; j+=4){
4918 va = REALIGN_LOAD <v1,v2,rt>;
4925 if (DR_IS_READ (dr
))
4927 bool is_packed
= false;
4928 tree type
= (TREE_TYPE (DR_REF (dr
)));
4930 if (optab_handler (vec_realign_load_optab
, mode
) != CODE_FOR_nothing
4931 && (!targetm
.vectorize
.builtin_mask_for_load
4932 || targetm
.vectorize
.builtin_mask_for_load ()))
4934 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
4935 if ((nested_in_vect_loop
4936 && (TREE_INT_CST_LOW (DR_STEP (dr
))
4937 != GET_MODE_SIZE (TYPE_MODE (vectype
))))
4939 return dr_explicit_realign
;
4941 return dr_explicit_realign_optimized
;
4943 if (!known_alignment_for_access_p (dr
))
4944 is_packed
= not_size_aligned (DR_REF (dr
));
4946 if ((TYPE_USER_ALIGN (type
) && !is_packed
)
4947 || targetm
.vectorize
.
4948 support_vector_misalignment (mode
, type
,
4949 DR_MISALIGNMENT (dr
), is_packed
))
4950 /* Can't software pipeline the loads, but can at least do them. */
4951 return dr_unaligned_supported
;
4955 bool is_packed
= false;
4956 tree type
= (TREE_TYPE (DR_REF (dr
)));
4958 if (!known_alignment_for_access_p (dr
))
4959 is_packed
= not_size_aligned (DR_REF (dr
));
4961 if ((TYPE_USER_ALIGN (type
) && !is_packed
)
4962 || targetm
.vectorize
.
4963 support_vector_misalignment (mode
, type
,
4964 DR_MISALIGNMENT (dr
), is_packed
))
4965 return dr_unaligned_supported
;
4969 return dr_unaligned_unsupported
;