1 /* Data References Analysis and Manipulation Utilities for Vectorization.
2 Copyright (C) 2003-2014 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"
28 #include "stor-layout.h"
31 #include "basic-block.h"
32 #include "gimple-pretty-print.h"
33 #include "tree-ssa-alias.h"
34 #include "internal-fn.h"
36 #include "gimple-expr.h"
40 #include "gimple-iterator.h"
41 #include "gimplify-me.h"
42 #include "gimple-ssa.h"
43 #include "tree-phinodes.h"
44 #include "ssa-iterators.h"
45 #include "stringpool.h"
46 #include "tree-ssanames.h"
47 #include "tree-ssa-loop-ivopts.h"
48 #include "tree-ssa-loop-manip.h"
49 #include "tree-ssa-loop.h"
52 #include "tree-chrec.h"
53 #include "tree-scalar-evolution.h"
54 #include "tree-vectorizer.h"
55 #include "diagnostic-core.h"
57 /* Need to include rtl.h, expr.h, etc. for optabs. */
63 /* Return true if load- or store-lanes optab OPTAB is implemented for
64 COUNT vectors of type VECTYPE. NAME is the name of OPTAB. */
67 vect_lanes_optab_supported_p (const char *name
, convert_optab optab
,
68 tree vectype
, unsigned HOST_WIDE_INT count
)
70 enum machine_mode mode
, array_mode
;
73 mode
= TYPE_MODE (vectype
);
74 limit_p
= !targetm
.array_mode_supported_p (mode
, count
);
75 array_mode
= mode_for_size (count
* GET_MODE_BITSIZE (mode
),
78 if (array_mode
== BLKmode
)
80 if (dump_enabled_p ())
81 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
82 "no array mode for %s[" HOST_WIDE_INT_PRINT_DEC
"]\n",
83 GET_MODE_NAME (mode
), count
);
87 if (convert_optab_handler (optab
, array_mode
, mode
) == CODE_FOR_nothing
)
89 if (dump_enabled_p ())
90 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
91 "cannot use %s<%s><%s>\n", name
,
92 GET_MODE_NAME (array_mode
), GET_MODE_NAME (mode
));
96 if (dump_enabled_p ())
97 dump_printf_loc (MSG_NOTE
, vect_location
,
98 "can use %s<%s><%s>\n", name
, GET_MODE_NAME (array_mode
),
99 GET_MODE_NAME (mode
));
105 /* Return the smallest scalar part of STMT.
106 This is used to determine the vectype of the stmt. We generally set the
107 vectype according to the type of the result (lhs). For stmts whose
108 result-type is different than the type of the arguments (e.g., demotion,
109 promotion), vectype will be reset appropriately (later). Note that we have
110 to visit the smallest datatype in this function, because that determines the
111 VF. If the smallest datatype in the loop is present only as the rhs of a
112 promotion operation - we'd miss it.
113 Such a case, where a variable of this datatype does not appear in the lhs
114 anywhere in the loop, can only occur if it's an invariant: e.g.:
115 'int_x = (int) short_inv', which we'd expect to have been optimized away by
116 invariant motion. However, we cannot rely on invariant motion to always
117 take invariants out of the loop, and so in the case of promotion we also
118 have to check the rhs.
119 LHS_SIZE_UNIT and RHS_SIZE_UNIT contain the sizes of the corresponding
123 vect_get_smallest_scalar_type (gimple stmt
, HOST_WIDE_INT
*lhs_size_unit
,
124 HOST_WIDE_INT
*rhs_size_unit
)
126 tree scalar_type
= gimple_expr_type (stmt
);
127 HOST_WIDE_INT lhs
, rhs
;
129 lhs
= rhs
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type
));
131 if (is_gimple_assign (stmt
)
132 && (gimple_assign_cast_p (stmt
)
133 || gimple_assign_rhs_code (stmt
) == WIDEN_MULT_EXPR
134 || gimple_assign_rhs_code (stmt
) == WIDEN_LSHIFT_EXPR
135 || gimple_assign_rhs_code (stmt
) == FLOAT_EXPR
))
137 tree rhs_type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
139 rhs
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (rhs_type
));
141 scalar_type
= rhs_type
;
144 *lhs_size_unit
= lhs
;
145 *rhs_size_unit
= rhs
;
150 /* Insert DDR into LOOP_VINFO list of ddrs that may alias and need to be
151 tested at run-time. Return TRUE if DDR was successfully inserted.
152 Return false if versioning is not supported. */
155 vect_mark_for_runtime_alias_test (ddr_p ddr
, loop_vec_info loop_vinfo
)
157 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
159 if ((unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS
) == 0)
162 if (dump_enabled_p ())
164 dump_printf_loc (MSG_NOTE
, vect_location
,
165 "mark for run-time aliasing test between ");
166 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (DDR_A (ddr
)));
167 dump_printf (MSG_NOTE
, " and ");
168 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (DDR_B (ddr
)));
169 dump_printf (MSG_NOTE
, "\n");
172 if (optimize_loop_nest_for_size_p (loop
))
174 if (dump_enabled_p ())
175 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
176 "versioning not supported when optimizing"
181 /* FORNOW: We don't support versioning with outer-loop vectorization. */
184 if (dump_enabled_p ())
185 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
186 "versioning not yet supported for outer-loops.\n");
190 /* FORNOW: We don't support creating runtime alias tests for non-constant
192 if (TREE_CODE (DR_STEP (DDR_A (ddr
))) != INTEGER_CST
193 || TREE_CODE (DR_STEP (DDR_B (ddr
))) != INTEGER_CST
)
195 if (dump_enabled_p ())
196 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
197 "versioning not yet supported for non-constant "
202 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
).safe_push (ddr
);
207 /* Function vect_analyze_data_ref_dependence.
209 Return TRUE if there (might) exist a dependence between a memory-reference
210 DRA and a memory-reference DRB. When versioning for alias may check a
211 dependence at run-time, return FALSE. Adjust *MAX_VF according to
212 the data dependence. */
215 vect_analyze_data_ref_dependence (struct data_dependence_relation
*ddr
,
216 loop_vec_info loop_vinfo
, int *max_vf
)
219 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
220 struct data_reference
*dra
= DDR_A (ddr
);
221 struct data_reference
*drb
= DDR_B (ddr
);
222 stmt_vec_info stmtinfo_a
= vinfo_for_stmt (DR_STMT (dra
));
223 stmt_vec_info stmtinfo_b
= vinfo_for_stmt (DR_STMT (drb
));
224 lambda_vector dist_v
;
225 unsigned int loop_depth
;
227 /* In loop analysis all data references should be vectorizable. */
228 if (!STMT_VINFO_VECTORIZABLE (stmtinfo_a
)
229 || !STMT_VINFO_VECTORIZABLE (stmtinfo_b
))
232 /* Independent data accesses. */
233 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
237 || (DR_IS_READ (dra
) && DR_IS_READ (drb
)))
240 /* Even if we have an anti-dependence then, as the vectorized loop covers at
241 least two scalar iterations, there is always also a true dependence.
242 As the vectorizer does not re-order loads and stores we can ignore
243 the anti-dependence if TBAA can disambiguate both DRs similar to the
244 case with known negative distance anti-dependences (positive
245 distance anti-dependences would violate TBAA constraints). */
246 if (((DR_IS_READ (dra
) && DR_IS_WRITE (drb
))
247 || (DR_IS_WRITE (dra
) && DR_IS_READ (drb
)))
248 && !alias_sets_conflict_p (get_alias_set (DR_REF (dra
)),
249 get_alias_set (DR_REF (drb
))))
252 /* Unknown data dependence. */
253 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
255 /* If user asserted safelen consecutive iterations can be
256 executed concurrently, assume independence. */
257 if (loop
->safelen
>= 2)
259 if (loop
->safelen
< *max_vf
)
260 *max_vf
= loop
->safelen
;
261 LOOP_VINFO_NO_DATA_DEPENDENCIES (loop_vinfo
) = false;
265 if (STMT_VINFO_GATHER_P (stmtinfo_a
)
266 || STMT_VINFO_GATHER_P (stmtinfo_b
))
268 if (dump_enabled_p ())
270 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
271 "versioning for alias not supported for: "
272 "can't determine dependence between ");
273 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
275 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
276 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
278 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
283 if (dump_enabled_p ())
285 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
286 "versioning for alias required: "
287 "can't determine dependence between ");
288 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
290 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
291 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
293 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
296 /* Add to list of ddrs that need to be tested at run-time. */
297 return !vect_mark_for_runtime_alias_test (ddr
, loop_vinfo
);
300 /* Known data dependence. */
301 if (DDR_NUM_DIST_VECTS (ddr
) == 0)
303 /* If user asserted safelen consecutive iterations can be
304 executed concurrently, assume independence. */
305 if (loop
->safelen
>= 2)
307 if (loop
->safelen
< *max_vf
)
308 *max_vf
= loop
->safelen
;
309 LOOP_VINFO_NO_DATA_DEPENDENCIES (loop_vinfo
) = false;
313 if (STMT_VINFO_GATHER_P (stmtinfo_a
)
314 || STMT_VINFO_GATHER_P (stmtinfo_b
))
316 if (dump_enabled_p ())
318 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
319 "versioning for alias not supported for: "
320 "bad dist vector for ");
321 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
323 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
324 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
326 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
331 if (dump_enabled_p ())
333 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
334 "versioning for alias required: "
335 "bad dist vector for ");
336 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, DR_REF (dra
));
337 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
338 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, DR_REF (drb
));
339 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
341 /* Add to list of ddrs that need to be tested at run-time. */
342 return !vect_mark_for_runtime_alias_test (ddr
, loop_vinfo
);
345 loop_depth
= index_in_loop_nest (loop
->num
, DDR_LOOP_NEST (ddr
));
346 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, dist_v
)
348 int dist
= dist_v
[loop_depth
];
350 if (dump_enabled_p ())
351 dump_printf_loc (MSG_NOTE
, vect_location
,
352 "dependence distance = %d.\n", dist
);
356 if (dump_enabled_p ())
358 dump_printf_loc (MSG_NOTE
, vect_location
,
359 "dependence distance == 0 between ");
360 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dra
));
361 dump_printf (MSG_NOTE
, " and ");
362 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (drb
));
363 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
366 /* When we perform grouped accesses and perform implicit CSE
367 by detecting equal accesses and doing disambiguation with
368 runtime alias tests like for
376 where we will end up loading { a[i], a[i+1] } once, make
377 sure that inserting group loads before the first load and
378 stores after the last store will do the right thing. */
379 if ((STMT_VINFO_GROUPED_ACCESS (stmtinfo_a
)
380 && GROUP_SAME_DR_STMT (stmtinfo_a
))
381 || (STMT_VINFO_GROUPED_ACCESS (stmtinfo_b
)
382 && GROUP_SAME_DR_STMT (stmtinfo_b
)))
385 earlier_stmt
= get_earlier_stmt (DR_STMT (dra
), DR_STMT (drb
));
387 (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt
))))
389 if (dump_enabled_p ())
390 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
391 "READ_WRITE dependence in interleaving."
400 if (dist
> 0 && DDR_REVERSED_P (ddr
))
402 /* If DDR_REVERSED_P the order of the data-refs in DDR was
403 reversed (to make distance vector positive), and the actual
404 distance is negative. */
405 if (dump_enabled_p ())
406 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
407 "dependence distance negative.\n");
408 /* Record a negative dependence distance to later limit the
409 amount of stmt copying / unrolling we can perform.
410 Only need to handle read-after-write dependence. */
412 && (STMT_VINFO_MIN_NEG_DIST (stmtinfo_b
) == 0
413 || STMT_VINFO_MIN_NEG_DIST (stmtinfo_b
) > (unsigned)dist
))
414 STMT_VINFO_MIN_NEG_DIST (stmtinfo_b
) = dist
;
419 && abs (dist
) < *max_vf
)
421 /* The dependence distance requires reduction of the maximal
422 vectorization factor. */
423 *max_vf
= abs (dist
);
424 if (dump_enabled_p ())
425 dump_printf_loc (MSG_NOTE
, vect_location
,
426 "adjusting maximal vectorization factor to %i\n",
430 if (abs (dist
) >= *max_vf
)
432 /* Dependence distance does not create dependence, as far as
433 vectorization is concerned, in this case. */
434 if (dump_enabled_p ())
435 dump_printf_loc (MSG_NOTE
, vect_location
,
436 "dependence distance >= VF.\n");
440 if (dump_enabled_p ())
442 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
443 "not vectorized, possible dependence "
444 "between data-refs ");
445 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dra
));
446 dump_printf (MSG_NOTE
, " and ");
447 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (drb
));
448 dump_printf (MSG_NOTE
, "\n");
457 /* Function vect_analyze_data_ref_dependences.
459 Examine all the data references in the loop, and make sure there do not
460 exist any data dependences between them. Set *MAX_VF according to
461 the maximum vectorization factor the data dependences allow. */
464 vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo
, int *max_vf
)
467 struct data_dependence_relation
*ddr
;
469 if (dump_enabled_p ())
470 dump_printf_loc (MSG_NOTE
, vect_location
,
471 "=== vect_analyze_data_ref_dependences ===\n");
473 LOOP_VINFO_NO_DATA_DEPENDENCIES (loop_vinfo
) = true;
474 if (!compute_all_dependences (LOOP_VINFO_DATAREFS (loop_vinfo
),
475 &LOOP_VINFO_DDRS (loop_vinfo
),
476 LOOP_VINFO_LOOP_NEST (loop_vinfo
), true))
479 FOR_EACH_VEC_ELT (LOOP_VINFO_DDRS (loop_vinfo
), i
, ddr
)
480 if (vect_analyze_data_ref_dependence (ddr
, loop_vinfo
, max_vf
))
487 /* Function vect_slp_analyze_data_ref_dependence.
489 Return TRUE if there (might) exist a dependence between a memory-reference
490 DRA and a memory-reference DRB. When versioning for alias may check a
491 dependence at run-time, return FALSE. Adjust *MAX_VF according to
492 the data dependence. */
495 vect_slp_analyze_data_ref_dependence (struct data_dependence_relation
*ddr
)
497 struct data_reference
*dra
= DDR_A (ddr
);
498 struct data_reference
*drb
= DDR_B (ddr
);
500 /* We need to check dependences of statements marked as unvectorizable
501 as well, they still can prohibit vectorization. */
503 /* Independent data accesses. */
504 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
510 /* Read-read is OK. */
511 if (DR_IS_READ (dra
) && DR_IS_READ (drb
))
514 /* If dra and drb are part of the same interleaving chain consider
516 if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (DR_STMT (dra
)))
517 && (GROUP_FIRST_ELEMENT (vinfo_for_stmt (DR_STMT (dra
)))
518 == GROUP_FIRST_ELEMENT (vinfo_for_stmt (DR_STMT (drb
)))))
521 /* Unknown data dependence. */
522 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
524 if (dump_enabled_p ())
526 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
527 "can't determine dependence between ");
528 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, DR_REF (dra
));
529 dump_printf (MSG_MISSED_OPTIMIZATION
, " and ");
530 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, DR_REF (drb
));
531 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
534 else if (dump_enabled_p ())
536 dump_printf_loc (MSG_NOTE
, vect_location
,
537 "determined dependence between ");
538 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dra
));
539 dump_printf (MSG_NOTE
, " and ");
540 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (drb
));
541 dump_printf (MSG_NOTE
, "\n");
544 /* We do not vectorize basic blocks with write-write dependencies. */
545 if (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))
548 /* If we have a read-write dependence check that the load is before the store.
549 When we vectorize basic blocks, vector load can be only before
550 corresponding scalar load, and vector store can be only after its
551 corresponding scalar store. So the order of the acceses is preserved in
552 case the load is before the store. */
553 gimple earlier_stmt
= get_earlier_stmt (DR_STMT (dra
), DR_STMT (drb
));
554 if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt
))))
556 /* That only holds for load-store pairs taking part in vectorization. */
557 if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dra
)))
558 && STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (drb
))))
566 /* Function vect_analyze_data_ref_dependences.
568 Examine all the data references in the basic-block, and make sure there
569 do not exist any data dependences between them. Set *MAX_VF according to
570 the maximum vectorization factor the data dependences allow. */
573 vect_slp_analyze_data_ref_dependences (bb_vec_info bb_vinfo
)
575 struct data_dependence_relation
*ddr
;
578 if (dump_enabled_p ())
579 dump_printf_loc (MSG_NOTE
, vect_location
,
580 "=== vect_slp_analyze_data_ref_dependences ===\n");
582 if (!compute_all_dependences (BB_VINFO_DATAREFS (bb_vinfo
),
583 &BB_VINFO_DDRS (bb_vinfo
),
587 FOR_EACH_VEC_ELT (BB_VINFO_DDRS (bb_vinfo
), i
, ddr
)
588 if (vect_slp_analyze_data_ref_dependence (ddr
))
595 /* Function vect_compute_data_ref_alignment
597 Compute the misalignment of the data reference DR.
600 1. If during the misalignment computation it is found that the data reference
601 cannot be vectorized then false is returned.
602 2. DR_MISALIGNMENT (DR) is defined.
604 FOR NOW: No analysis is actually performed. Misalignment is calculated
605 only for trivial cases. TODO. */
608 vect_compute_data_ref_alignment (struct data_reference
*dr
)
610 gimple stmt
= DR_STMT (dr
);
611 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
612 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
613 struct loop
*loop
= NULL
;
614 tree ref
= DR_REF (dr
);
616 tree base
, base_addr
;
619 tree aligned_to
, alignment
;
621 if (dump_enabled_p ())
622 dump_printf_loc (MSG_NOTE
, vect_location
,
623 "vect_compute_data_ref_alignment:\n");
626 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
628 /* Initialize misalignment to unknown. */
629 SET_DR_MISALIGNMENT (dr
, -1);
631 /* Strided loads perform only component accesses, misalignment information
632 is irrelevant for them. */
633 if (STMT_VINFO_STRIDE_LOAD_P (stmt_info
))
636 misalign
= DR_INIT (dr
);
637 aligned_to
= DR_ALIGNED_TO (dr
);
638 base_addr
= DR_BASE_ADDRESS (dr
);
639 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
641 /* In case the dataref is in an inner-loop of the loop that is being
642 vectorized (LOOP), we use the base and misalignment information
643 relative to the outer-loop (LOOP). This is ok only if the misalignment
644 stays the same throughout the execution of the inner-loop, which is why
645 we have to check that the stride of the dataref in the inner-loop evenly
646 divides by the vector size. */
647 if (loop
&& nested_in_vect_loop_p (loop
, stmt
))
649 tree step
= DR_STEP (dr
);
650 HOST_WIDE_INT dr_step
= TREE_INT_CST_LOW (step
);
652 if (dr_step
% GET_MODE_SIZE (TYPE_MODE (vectype
)) == 0)
654 if (dump_enabled_p ())
655 dump_printf_loc (MSG_NOTE
, vect_location
,
656 "inner step divides the vector-size.\n");
657 misalign
= STMT_VINFO_DR_INIT (stmt_info
);
658 aligned_to
= STMT_VINFO_DR_ALIGNED_TO (stmt_info
);
659 base_addr
= STMT_VINFO_DR_BASE_ADDRESS (stmt_info
);
663 if (dump_enabled_p ())
664 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
665 "inner step doesn't divide the vector-size.\n");
666 misalign
= NULL_TREE
;
670 /* Similarly, if we're doing basic-block vectorization, we can only use
671 base and misalignment information relative to an innermost loop if the
672 misalignment stays the same throughout the execution of the loop.
673 As above, this is the case if the stride of the dataref evenly divides
674 by the vector size. */
677 tree step
= DR_STEP (dr
);
678 HOST_WIDE_INT dr_step
= TREE_INT_CST_LOW (step
);
680 if (dr_step
% GET_MODE_SIZE (TYPE_MODE (vectype
)) != 0)
682 if (dump_enabled_p ())
683 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
684 "SLP: step doesn't divide the vector-size.\n");
685 misalign
= NULL_TREE
;
689 base
= build_fold_indirect_ref (base_addr
);
690 alignment
= ssize_int (TYPE_ALIGN (vectype
)/BITS_PER_UNIT
);
692 if ((aligned_to
&& tree_int_cst_compare (aligned_to
, alignment
) < 0)
695 if (dump_enabled_p ())
697 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
698 "Unknown alignment for access: ");
699 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, base
);
700 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
706 && tree_int_cst_compare (ssize_int (DECL_ALIGN_UNIT (base
)),
708 || (TREE_CODE (base_addr
) == SSA_NAME
709 && tree_int_cst_compare (ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (
710 TREE_TYPE (base_addr
)))),
712 || (get_pointer_alignment (base_addr
) >= TYPE_ALIGN (vectype
)))
715 base_aligned
= false;
719 /* Do not change the alignment of global variables here if
720 flag_section_anchors is enabled as we already generated
721 RTL for other functions. Most global variables should
722 have been aligned during the IPA increase_alignment pass. */
723 if (!vect_can_force_dr_alignment_p (base
, TYPE_ALIGN (vectype
))
724 || (TREE_STATIC (base
) && flag_section_anchors
))
726 if (dump_enabled_p ())
728 dump_printf_loc (MSG_NOTE
, vect_location
,
729 "can't force alignment of ref: ");
730 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, ref
);
731 dump_printf (MSG_NOTE
, "\n");
736 /* Force the alignment of the decl.
737 NOTE: This is the only change to the code we make during
738 the analysis phase, before deciding to vectorize the loop. */
739 if (dump_enabled_p ())
741 dump_printf_loc (MSG_NOTE
, vect_location
, "force alignment of ");
742 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, ref
);
743 dump_printf (MSG_NOTE
, "\n");
746 ((dataref_aux
*)dr
->aux
)->base_decl
= base
;
747 ((dataref_aux
*)dr
->aux
)->base_misaligned
= true;
750 /* If this is a backward running DR then first access in the larger
751 vectype actually is N-1 elements before the address in the DR.
752 Adjust misalign accordingly. */
753 if (tree_int_cst_compare (DR_STEP (dr
), size_zero_node
) < 0)
755 tree offset
= ssize_int (TYPE_VECTOR_SUBPARTS (vectype
) - 1);
756 /* DR_STEP(dr) is the same as -TYPE_SIZE of the scalar type,
757 otherwise we wouldn't be here. */
758 offset
= fold_build2 (MULT_EXPR
, ssizetype
, offset
, DR_STEP (dr
));
759 /* PLUS because DR_STEP was negative. */
760 misalign
= size_binop (PLUS_EXPR
, misalign
, offset
);
763 /* Modulo alignment. */
764 misalign
= size_binop (FLOOR_MOD_EXPR
, misalign
, alignment
);
766 if (!tree_fits_uhwi_p (misalign
))
768 /* Negative or overflowed misalignment value. */
769 if (dump_enabled_p ())
770 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
771 "unexpected misalign value\n");
775 SET_DR_MISALIGNMENT (dr
, tree_to_uhwi (misalign
));
777 if (dump_enabled_p ())
779 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
780 "misalign = %d bytes of ref ", DR_MISALIGNMENT (dr
));
781 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, ref
);
782 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
789 /* Function vect_compute_data_refs_alignment
791 Compute the misalignment of data references in the loop.
792 Return FALSE if a data reference is found that cannot be vectorized. */
795 vect_compute_data_refs_alignment (loop_vec_info loop_vinfo
,
796 bb_vec_info bb_vinfo
)
798 vec
<data_reference_p
> datarefs
;
799 struct data_reference
*dr
;
803 datarefs
= LOOP_VINFO_DATAREFS (loop_vinfo
);
805 datarefs
= BB_VINFO_DATAREFS (bb_vinfo
);
807 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
808 if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr
)))
809 && !vect_compute_data_ref_alignment (dr
))
813 /* Mark unsupported statement as unvectorizable. */
814 STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr
))) = false;
825 /* Function vect_update_misalignment_for_peel
827 DR - the data reference whose misalignment is to be adjusted.
828 DR_PEEL - the data reference whose misalignment is being made
829 zero in the vector loop by the peel.
830 NPEEL - the number of iterations in the peel loop if the misalignment
831 of DR_PEEL is known at compile time. */
834 vect_update_misalignment_for_peel (struct data_reference
*dr
,
835 struct data_reference
*dr_peel
, int npeel
)
838 vec
<dr_p
> same_align_drs
;
839 struct data_reference
*current_dr
;
840 int dr_size
= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr
))));
841 int dr_peel_size
= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr_peel
))));
842 stmt_vec_info stmt_info
= vinfo_for_stmt (DR_STMT (dr
));
843 stmt_vec_info peel_stmt_info
= vinfo_for_stmt (DR_STMT (dr_peel
));
845 /* For interleaved data accesses the step in the loop must be multiplied by
846 the size of the interleaving group. */
847 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
848 dr_size
*= GROUP_SIZE (vinfo_for_stmt (GROUP_FIRST_ELEMENT (stmt_info
)));
849 if (STMT_VINFO_GROUPED_ACCESS (peel_stmt_info
))
850 dr_peel_size
*= GROUP_SIZE (peel_stmt_info
);
852 /* It can be assumed that the data refs with the same alignment as dr_peel
853 are aligned in the vector loop. */
855 = STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (DR_STMT (dr_peel
)));
856 FOR_EACH_VEC_ELT (same_align_drs
, i
, current_dr
)
858 if (current_dr
!= dr
)
860 gcc_assert (DR_MISALIGNMENT (dr
) / dr_size
==
861 DR_MISALIGNMENT (dr_peel
) / dr_peel_size
);
862 SET_DR_MISALIGNMENT (dr
, 0);
866 if (known_alignment_for_access_p (dr
)
867 && known_alignment_for_access_p (dr_peel
))
869 bool negative
= tree_int_cst_compare (DR_STEP (dr
), size_zero_node
) < 0;
870 int misal
= DR_MISALIGNMENT (dr
);
871 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
872 misal
+= negative
? -npeel
* dr_size
: npeel
* dr_size
;
873 misal
&= (TYPE_ALIGN (vectype
) / BITS_PER_UNIT
) - 1;
874 SET_DR_MISALIGNMENT (dr
, misal
);
878 if (dump_enabled_p ())
879 dump_printf_loc (MSG_NOTE
, vect_location
, "Setting misalignment to -1.\n");
880 SET_DR_MISALIGNMENT (dr
, -1);
884 /* Function vect_verify_datarefs_alignment
886 Return TRUE if all data references in the loop can be
887 handled with respect to alignment. */
890 vect_verify_datarefs_alignment (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
)
892 vec
<data_reference_p
> datarefs
;
893 struct data_reference
*dr
;
894 enum dr_alignment_support supportable_dr_alignment
;
898 datarefs
= LOOP_VINFO_DATAREFS (loop_vinfo
);
900 datarefs
= BB_VINFO_DATAREFS (bb_vinfo
);
902 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
904 gimple stmt
= DR_STMT (dr
);
905 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
907 if (!STMT_VINFO_RELEVANT_P (stmt_info
))
910 /* For interleaving, only the alignment of the first access matters.
911 Skip statements marked as not vectorizable. */
912 if ((STMT_VINFO_GROUPED_ACCESS (stmt_info
)
913 && GROUP_FIRST_ELEMENT (stmt_info
) != stmt
)
914 || !STMT_VINFO_VECTORIZABLE (stmt_info
))
917 /* Strided loads perform only component accesses, alignment is
918 irrelevant for them. */
919 if (STMT_VINFO_STRIDE_LOAD_P (stmt_info
))
922 supportable_dr_alignment
= vect_supportable_dr_alignment (dr
, false);
923 if (!supportable_dr_alignment
)
925 if (dump_enabled_p ())
928 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
929 "not vectorized: unsupported unaligned load.");
931 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
932 "not vectorized: unsupported unaligned "
935 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
937 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
941 if (supportable_dr_alignment
!= dr_aligned
&& dump_enabled_p ())
942 dump_printf_loc (MSG_NOTE
, vect_location
,
943 "Vectorizing an unaligned access.\n");
948 /* Given an memory reference EXP return whether its alignment is less
952 not_size_aligned (tree exp
)
954 if (!tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (exp
))))
957 return (tree_to_uhwi (TYPE_SIZE (TREE_TYPE (exp
)))
958 > get_object_alignment (exp
));
961 /* Function vector_alignment_reachable_p
963 Return true if vector alignment for DR is reachable by peeling
964 a few loop iterations. Return false otherwise. */
967 vector_alignment_reachable_p (struct data_reference
*dr
)
969 gimple stmt
= DR_STMT (dr
);
970 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
971 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
973 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
975 /* For interleaved access we peel only if number of iterations in
976 the prolog loop ({VF - misalignment}), is a multiple of the
977 number of the interleaved accesses. */
978 int elem_size
, mis_in_elements
;
979 int nelements
= TYPE_VECTOR_SUBPARTS (vectype
);
981 /* FORNOW: handle only known alignment. */
982 if (!known_alignment_for_access_p (dr
))
985 elem_size
= GET_MODE_SIZE (TYPE_MODE (vectype
)) / nelements
;
986 mis_in_elements
= DR_MISALIGNMENT (dr
) / elem_size
;
988 if ((nelements
- mis_in_elements
) % GROUP_SIZE (stmt_info
))
992 /* If misalignment is known at the compile time then allow peeling
993 only if natural alignment is reachable through peeling. */
994 if (known_alignment_for_access_p (dr
) && !aligned_access_p (dr
))
996 HOST_WIDE_INT elmsize
=
997 int_cst_value (TYPE_SIZE_UNIT (TREE_TYPE (vectype
)));
998 if (dump_enabled_p ())
1000 dump_printf_loc (MSG_NOTE
, vect_location
,
1001 "data size =" HOST_WIDE_INT_PRINT_DEC
, elmsize
);
1002 dump_printf (MSG_NOTE
,
1003 ". misalignment = %d.\n", DR_MISALIGNMENT (dr
));
1005 if (DR_MISALIGNMENT (dr
) % elmsize
)
1007 if (dump_enabled_p ())
1008 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1009 "data size does not divide the misalignment.\n");
1014 if (!known_alignment_for_access_p (dr
))
1016 tree type
= TREE_TYPE (DR_REF (dr
));
1017 bool is_packed
= not_size_aligned (DR_REF (dr
));
1018 if (dump_enabled_p ())
1019 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1020 "Unknown misalignment, is_packed = %d\n",is_packed
);
1021 if ((TYPE_USER_ALIGN (type
) && !is_packed
)
1022 || targetm
.vectorize
.vector_alignment_reachable (type
, is_packed
))
1032 /* Calculate the cost of the memory access represented by DR. */
1035 vect_get_data_access_cost (struct data_reference
*dr
,
1036 unsigned int *inside_cost
,
1037 unsigned int *outside_cost
,
1038 stmt_vector_for_cost
*body_cost_vec
)
1040 gimple stmt
= DR_STMT (dr
);
1041 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1042 int nunits
= TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
1043 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
1044 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1045 int ncopies
= vf
/ nunits
;
1047 if (DR_IS_READ (dr
))
1048 vect_get_load_cost (dr
, ncopies
, true, inside_cost
, outside_cost
,
1049 NULL
, body_cost_vec
, false);
1051 vect_get_store_cost (dr
, ncopies
, inside_cost
, body_cost_vec
);
1053 if (dump_enabled_p ())
1054 dump_printf_loc (MSG_NOTE
, vect_location
,
1055 "vect_get_data_access_cost: inside_cost = %d, "
1056 "outside_cost = %d.\n", *inside_cost
, *outside_cost
);
1060 /* Insert DR into peeling hash table with NPEEL as key. */
1063 vect_peeling_hash_insert (loop_vec_info loop_vinfo
, struct data_reference
*dr
,
1066 struct _vect_peel_info elem
, *slot
;
1067 _vect_peel_info
**new_slot
;
1068 bool supportable_dr_alignment
= vect_supportable_dr_alignment (dr
, true);
1071 slot
= LOOP_VINFO_PEELING_HTAB (loop_vinfo
).find (&elem
);
1076 slot
= XNEW (struct _vect_peel_info
);
1077 slot
->npeel
= npeel
;
1080 new_slot
= LOOP_VINFO_PEELING_HTAB (loop_vinfo
).find_slot (slot
, INSERT
);
1084 if (!supportable_dr_alignment
1085 && unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo
)))
1086 slot
->count
+= VECT_MAX_COST
;
1090 /* Traverse peeling hash table to find peeling option that aligns maximum
1091 number of data accesses. */
1094 vect_peeling_hash_get_most_frequent (_vect_peel_info
**slot
,
1095 _vect_peel_extended_info
*max
)
1097 vect_peel_info elem
= *slot
;
1099 if (elem
->count
> max
->peel_info
.count
1100 || (elem
->count
== max
->peel_info
.count
1101 && max
->peel_info
.npeel
> elem
->npeel
))
1103 max
->peel_info
.npeel
= elem
->npeel
;
1104 max
->peel_info
.count
= elem
->count
;
1105 max
->peel_info
.dr
= elem
->dr
;
1112 /* Traverse peeling hash table and calculate cost for each peeling option.
1113 Find the one with the lowest cost. */
1116 vect_peeling_hash_get_lowest_cost (_vect_peel_info
**slot
,
1117 _vect_peel_extended_info
*min
)
1119 vect_peel_info elem
= *slot
;
1120 int save_misalignment
, dummy
;
1121 unsigned int inside_cost
= 0, outside_cost
= 0, i
;
1122 gimple stmt
= DR_STMT (elem
->dr
);
1123 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1124 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
1125 vec
<data_reference_p
> datarefs
= LOOP_VINFO_DATAREFS (loop_vinfo
);
1126 struct data_reference
*dr
;
1127 stmt_vector_for_cost prologue_cost_vec
, body_cost_vec
, epilogue_cost_vec
;
1128 int single_iter_cost
;
1130 prologue_cost_vec
.create (2);
1131 body_cost_vec
.create (2);
1132 epilogue_cost_vec
.create (2);
1134 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
1136 stmt
= DR_STMT (dr
);
1137 stmt_info
= vinfo_for_stmt (stmt
);
1138 /* For interleaving, only the alignment of the first access
1140 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
)
1141 && GROUP_FIRST_ELEMENT (stmt_info
) != stmt
)
1144 save_misalignment
= DR_MISALIGNMENT (dr
);
1145 vect_update_misalignment_for_peel (dr
, elem
->dr
, elem
->npeel
);
1146 vect_get_data_access_cost (dr
, &inside_cost
, &outside_cost
,
1148 SET_DR_MISALIGNMENT (dr
, save_misalignment
);
1151 single_iter_cost
= vect_get_single_scalar_iteration_cost (loop_vinfo
);
1152 outside_cost
+= vect_get_known_peeling_cost (loop_vinfo
, elem
->npeel
,
1153 &dummy
, single_iter_cost
,
1155 &epilogue_cost_vec
);
1157 /* Prologue and epilogue costs are added to the target model later.
1158 These costs depend only on the scalar iteration cost, the
1159 number of peeling iterations finally chosen, and the number of
1160 misaligned statements. So discard the information found here. */
1161 prologue_cost_vec
.release ();
1162 epilogue_cost_vec
.release ();
1164 if (inside_cost
< min
->inside_cost
1165 || (inside_cost
== min
->inside_cost
&& outside_cost
< min
->outside_cost
))
1167 min
->inside_cost
= inside_cost
;
1168 min
->outside_cost
= outside_cost
;
1169 min
->body_cost_vec
.release ();
1170 min
->body_cost_vec
= body_cost_vec
;
1171 min
->peel_info
.dr
= elem
->dr
;
1172 min
->peel_info
.npeel
= elem
->npeel
;
1175 body_cost_vec
.release ();
1181 /* Choose best peeling option by traversing peeling hash table and either
1182 choosing an option with the lowest cost (if cost model is enabled) or the
1183 option that aligns as many accesses as possible. */
1185 static struct data_reference
*
1186 vect_peeling_hash_choose_best_peeling (loop_vec_info loop_vinfo
,
1187 unsigned int *npeel
,
1188 stmt_vector_for_cost
*body_cost_vec
)
1190 struct _vect_peel_extended_info res
;
1192 res
.peel_info
.dr
= NULL
;
1193 res
.body_cost_vec
= stmt_vector_for_cost ();
1195 if (!unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo
)))
1197 res
.inside_cost
= INT_MAX
;
1198 res
.outside_cost
= INT_MAX
;
1199 LOOP_VINFO_PEELING_HTAB (loop_vinfo
)
1200 .traverse
<_vect_peel_extended_info
*,
1201 vect_peeling_hash_get_lowest_cost
> (&res
);
1205 res
.peel_info
.count
= 0;
1206 LOOP_VINFO_PEELING_HTAB (loop_vinfo
)
1207 .traverse
<_vect_peel_extended_info
*,
1208 vect_peeling_hash_get_most_frequent
> (&res
);
1211 *npeel
= res
.peel_info
.npeel
;
1212 *body_cost_vec
= res
.body_cost_vec
;
1213 return res
.peel_info
.dr
;
1217 /* Function vect_enhance_data_refs_alignment
1219 This pass will use loop versioning and loop peeling in order to enhance
1220 the alignment of data references in the loop.
1222 FOR NOW: we assume that whatever versioning/peeling takes place, only the
1223 original loop is to be vectorized. Any other loops that are created by
1224 the transformations performed in this pass - are not supposed to be
1225 vectorized. This restriction will be relaxed.
1227 This pass will require a cost model to guide it whether to apply peeling
1228 or versioning or a combination of the two. For example, the scheme that
1229 intel uses when given a loop with several memory accesses, is as follows:
1230 choose one memory access ('p') which alignment you want to force by doing
1231 peeling. Then, either (1) generate a loop in which 'p' is aligned and all
1232 other accesses are not necessarily aligned, or (2) use loop versioning to
1233 generate one loop in which all accesses are aligned, and another loop in
1234 which only 'p' is necessarily aligned.
1236 ("Automatic Intra-Register Vectorization for the Intel Architecture",
1237 Aart J.C. Bik, Milind Girkar, Paul M. Grey and Ximmin Tian, International
1238 Journal of Parallel Programming, Vol. 30, No. 2, April 2002.)
1240 Devising a cost model is the most critical aspect of this work. It will
1241 guide us on which access to peel for, whether to use loop versioning, how
1242 many versions to create, etc. The cost model will probably consist of
1243 generic considerations as well as target specific considerations (on
1244 powerpc for example, misaligned stores are more painful than misaligned
1247 Here are the general steps involved in alignment enhancements:
1249 -- original loop, before alignment analysis:
1250 for (i=0; i<N; i++){
1251 x = q[i]; # DR_MISALIGNMENT(q) = unknown
1252 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1255 -- After vect_compute_data_refs_alignment:
1256 for (i=0; i<N; i++){
1257 x = q[i]; # DR_MISALIGNMENT(q) = 3
1258 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1261 -- Possibility 1: we do loop versioning:
1263 for (i=0; i<N; i++){ # loop 1A
1264 x = q[i]; # DR_MISALIGNMENT(q) = 3
1265 p[i] = y; # DR_MISALIGNMENT(p) = 0
1269 for (i=0; i<N; i++){ # loop 1B
1270 x = q[i]; # DR_MISALIGNMENT(q) = 3
1271 p[i] = y; # DR_MISALIGNMENT(p) = unaligned
1275 -- Possibility 2: we do loop peeling:
1276 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
1280 for (i = 3; i < N; i++){ # loop 2A
1281 x = q[i]; # DR_MISALIGNMENT(q) = 0
1282 p[i] = y; # DR_MISALIGNMENT(p) = unknown
1285 -- Possibility 3: combination of loop peeling and versioning:
1286 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
1291 for (i = 3; i<N; i++){ # loop 3A
1292 x = q[i]; # DR_MISALIGNMENT(q) = 0
1293 p[i] = y; # DR_MISALIGNMENT(p) = 0
1297 for (i = 3; i<N; i++){ # loop 3B
1298 x = q[i]; # DR_MISALIGNMENT(q) = 0
1299 p[i] = y; # DR_MISALIGNMENT(p) = unaligned
1303 These loops are later passed to loop_transform to be vectorized. The
1304 vectorizer will use the alignment information to guide the transformation
1305 (whether to generate regular loads/stores, or with special handling for
1309 vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo
)
1311 vec
<data_reference_p
> datarefs
= LOOP_VINFO_DATAREFS (loop_vinfo
);
1312 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1313 enum dr_alignment_support supportable_dr_alignment
;
1314 struct data_reference
*dr0
= NULL
, *first_store
= NULL
;
1315 struct data_reference
*dr
;
1317 bool do_peeling
= false;
1318 bool do_versioning
= false;
1321 stmt_vec_info stmt_info
;
1322 unsigned int npeel
= 0;
1323 bool all_misalignments_unknown
= true;
1324 unsigned int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1325 unsigned possible_npeel_number
= 1;
1327 unsigned int nelements
, mis
, same_align_drs_max
= 0;
1328 stmt_vector_for_cost body_cost_vec
= stmt_vector_for_cost ();
1330 if (dump_enabled_p ())
1331 dump_printf_loc (MSG_NOTE
, vect_location
,
1332 "=== vect_enhance_data_refs_alignment ===\n");
1334 /* While cost model enhancements are expected in the future, the high level
1335 view of the code at this time is as follows:
1337 A) If there is a misaligned access then see if peeling to align
1338 this access can make all data references satisfy
1339 vect_supportable_dr_alignment. If so, update data structures
1340 as needed and return true.
1342 B) If peeling wasn't possible and there is a data reference with an
1343 unknown misalignment that does not satisfy vect_supportable_dr_alignment
1344 then see if loop versioning checks can be used to make all data
1345 references satisfy vect_supportable_dr_alignment. If so, update
1346 data structures as needed and return true.
1348 C) If neither peeling nor versioning were successful then return false if
1349 any data reference does not satisfy vect_supportable_dr_alignment.
1351 D) Return true (all data references satisfy vect_supportable_dr_alignment).
1353 Note, Possibility 3 above (which is peeling and versioning together) is not
1354 being done at this time. */
1356 /* (1) Peeling to force alignment. */
1358 /* (1.1) Decide whether to perform peeling, and how many iterations to peel:
1360 + How many accesses will become aligned due to the peeling
1361 - How many accesses will become unaligned due to the peeling,
1362 and the cost of misaligned accesses.
1363 - The cost of peeling (the extra runtime checks, the increase
1366 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
1368 stmt
= DR_STMT (dr
);
1369 stmt_info
= vinfo_for_stmt (stmt
);
1371 if (!STMT_VINFO_RELEVANT_P (stmt_info
))
1374 /* For interleaving, only the alignment of the first access
1376 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
)
1377 && GROUP_FIRST_ELEMENT (stmt_info
) != stmt
)
1380 /* For invariant accesses there is nothing to enhance. */
1381 if (integer_zerop (DR_STEP (dr
)))
1384 /* Strided loads perform only component accesses, alignment is
1385 irrelevant for them. */
1386 if (STMT_VINFO_STRIDE_LOAD_P (stmt_info
))
1389 supportable_dr_alignment
= vect_supportable_dr_alignment (dr
, true);
1390 do_peeling
= vector_alignment_reachable_p (dr
);
1393 if (known_alignment_for_access_p (dr
))
1395 unsigned int npeel_tmp
;
1396 bool negative
= tree_int_cst_compare (DR_STEP (dr
),
1397 size_zero_node
) < 0;
1399 /* Save info about DR in the hash table. */
1400 if (!LOOP_VINFO_PEELING_HTAB (loop_vinfo
).is_created ())
1401 LOOP_VINFO_PEELING_HTAB (loop_vinfo
).create (1);
1403 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
1404 nelements
= TYPE_VECTOR_SUBPARTS (vectype
);
1405 mis
= DR_MISALIGNMENT (dr
) / GET_MODE_SIZE (TYPE_MODE (
1406 TREE_TYPE (DR_REF (dr
))));
1407 npeel_tmp
= (negative
1408 ? (mis
- nelements
) : (nelements
- mis
))
1411 /* For multiple types, it is possible that the bigger type access
1412 will have more than one peeling option. E.g., a loop with two
1413 types: one of size (vector size / 4), and the other one of
1414 size (vector size / 8). Vectorization factor will 8. If both
1415 access are misaligned by 3, the first one needs one scalar
1416 iteration to be aligned, and the second one needs 5. But the
1417 the first one will be aligned also by peeling 5 scalar
1418 iterations, and in that case both accesses will be aligned.
1419 Hence, except for the immediate peeling amount, we also want
1420 to try to add full vector size, while we don't exceed
1421 vectorization factor.
1422 We do this automtically for cost model, since we calculate cost
1423 for every peeling option. */
1424 if (unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo
)))
1425 possible_npeel_number
= vf
/nelements
;
1427 /* Handle the aligned case. We may decide to align some other
1428 access, making DR unaligned. */
1429 if (DR_MISALIGNMENT (dr
) == 0)
1432 if (unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo
)))
1433 possible_npeel_number
++;
1436 for (j
= 0; j
< possible_npeel_number
; j
++)
1438 gcc_assert (npeel_tmp
<= vf
);
1439 vect_peeling_hash_insert (loop_vinfo
, dr
, npeel_tmp
);
1440 npeel_tmp
+= nelements
;
1443 all_misalignments_unknown
= false;
1444 /* Data-ref that was chosen for the case that all the
1445 misalignments are unknown is not relevant anymore, since we
1446 have a data-ref with known alignment. */
1451 /* If we don't know any misalignment values, we prefer
1452 peeling for data-ref that has the maximum number of data-refs
1453 with the same alignment, unless the target prefers to align
1454 stores over load. */
1455 if (all_misalignments_unknown
)
1457 unsigned same_align_drs
1458 = STMT_VINFO_SAME_ALIGN_REFS (stmt_info
).length ();
1460 || same_align_drs_max
< same_align_drs
)
1462 same_align_drs_max
= same_align_drs
;
1465 /* For data-refs with the same number of related
1466 accesses prefer the one where the misalign
1467 computation will be invariant in the outermost loop. */
1468 else if (same_align_drs_max
== same_align_drs
)
1470 struct loop
*ivloop0
, *ivloop
;
1471 ivloop0
= outermost_invariant_loop_for_expr
1472 (loop
, DR_BASE_ADDRESS (dr0
));
1473 ivloop
= outermost_invariant_loop_for_expr
1474 (loop
, DR_BASE_ADDRESS (dr
));
1475 if ((ivloop
&& !ivloop0
)
1476 || (ivloop
&& ivloop0
1477 && flow_loop_nested_p (ivloop
, ivloop0
)))
1481 if (!first_store
&& DR_IS_WRITE (dr
))
1485 /* If there are both known and unknown misaligned accesses in the
1486 loop, we choose peeling amount according to the known
1488 if (!supportable_dr_alignment
)
1491 if (!first_store
&& DR_IS_WRITE (dr
))
1498 if (!aligned_access_p (dr
))
1500 if (dump_enabled_p ())
1501 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1502 "vector alignment may not be reachable\n");
1508 /* Check if we can possibly peel the loop. */
1509 if (!vect_can_advance_ivs_p (loop_vinfo
)
1510 || !slpeel_can_duplicate_loop_p (loop
, single_exit (loop
)))
1513 if (do_peeling
&& all_misalignments_unknown
1514 && vect_supportable_dr_alignment (dr0
, false))
1517 /* Check if the target requires to prefer stores over loads, i.e., if
1518 misaligned stores are more expensive than misaligned loads (taking
1519 drs with same alignment into account). */
1520 if (first_store
&& DR_IS_READ (dr0
))
1522 unsigned int load_inside_cost
= 0, load_outside_cost
= 0;
1523 unsigned int store_inside_cost
= 0, store_outside_cost
= 0;
1524 unsigned int load_inside_penalty
= 0, load_outside_penalty
= 0;
1525 unsigned int store_inside_penalty
= 0, store_outside_penalty
= 0;
1526 stmt_vector_for_cost dummy
;
1529 vect_get_data_access_cost (dr0
, &load_inside_cost
, &load_outside_cost
,
1531 vect_get_data_access_cost (first_store
, &store_inside_cost
,
1532 &store_outside_cost
, &dummy
);
1536 /* Calculate the penalty for leaving FIRST_STORE unaligned (by
1537 aligning the load DR0). */
1538 load_inside_penalty
= store_inside_cost
;
1539 load_outside_penalty
= store_outside_cost
;
1541 STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (
1542 DR_STMT (first_store
))).iterate (i
, &dr
);
1544 if (DR_IS_READ (dr
))
1546 load_inside_penalty
+= load_inside_cost
;
1547 load_outside_penalty
+= load_outside_cost
;
1551 load_inside_penalty
+= store_inside_cost
;
1552 load_outside_penalty
+= store_outside_cost
;
1555 /* Calculate the penalty for leaving DR0 unaligned (by
1556 aligning the FIRST_STORE). */
1557 store_inside_penalty
= load_inside_cost
;
1558 store_outside_penalty
= load_outside_cost
;
1560 STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (
1561 DR_STMT (dr0
))).iterate (i
, &dr
);
1563 if (DR_IS_READ (dr
))
1565 store_inside_penalty
+= load_inside_cost
;
1566 store_outside_penalty
+= load_outside_cost
;
1570 store_inside_penalty
+= store_inside_cost
;
1571 store_outside_penalty
+= store_outside_cost
;
1574 if (load_inside_penalty
> store_inside_penalty
1575 || (load_inside_penalty
== store_inside_penalty
1576 && load_outside_penalty
> store_outside_penalty
))
1580 /* In case there are only loads with different unknown misalignments, use
1581 peeling only if it may help to align other accesses in the loop. */
1583 && !STMT_VINFO_SAME_ALIGN_REFS (
1584 vinfo_for_stmt (DR_STMT (dr0
))).length ()
1585 && vect_supportable_dr_alignment (dr0
, false)
1586 != dr_unaligned_supported
)
1590 if (do_peeling
&& !dr0
)
1592 /* Peeling is possible, but there is no data access that is not supported
1593 unless aligned. So we try to choose the best possible peeling. */
1595 /* We should get here only if there are drs with known misalignment. */
1596 gcc_assert (!all_misalignments_unknown
);
1598 /* Choose the best peeling from the hash table. */
1599 dr0
= vect_peeling_hash_choose_best_peeling (loop_vinfo
, &npeel
,
1607 stmt
= DR_STMT (dr0
);
1608 stmt_info
= vinfo_for_stmt (stmt
);
1609 vectype
= STMT_VINFO_VECTYPE (stmt_info
);
1610 nelements
= TYPE_VECTOR_SUBPARTS (vectype
);
1612 if (known_alignment_for_access_p (dr0
))
1614 bool negative
= tree_int_cst_compare (DR_STEP (dr0
),
1615 size_zero_node
) < 0;
1618 /* Since it's known at compile time, compute the number of
1619 iterations in the peeled loop (the peeling factor) for use in
1620 updating DR_MISALIGNMENT values. The peeling factor is the
1621 vectorization factor minus the misalignment as an element
1623 mis
= DR_MISALIGNMENT (dr0
);
1624 mis
/= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr0
))));
1625 npeel
= ((negative
? mis
- nelements
: nelements
- mis
)
1629 /* For interleaved data access every iteration accesses all the
1630 members of the group, therefore we divide the number of iterations
1631 by the group size. */
1632 stmt_info
= vinfo_for_stmt (DR_STMT (dr0
));
1633 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
))
1634 npeel
/= GROUP_SIZE (stmt_info
);
1636 if (dump_enabled_p ())
1637 dump_printf_loc (MSG_NOTE
, vect_location
,
1638 "Try peeling by %d\n", npeel
);
1641 /* Ensure that all data refs can be vectorized after the peel. */
1642 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
1644 int save_misalignment
;
1649 stmt
= DR_STMT (dr
);
1650 stmt_info
= vinfo_for_stmt (stmt
);
1651 /* For interleaving, only the alignment of the first access
1653 if (STMT_VINFO_GROUPED_ACCESS (stmt_info
)
1654 && GROUP_FIRST_ELEMENT (stmt_info
) != stmt
)
1657 /* Strided loads perform only component accesses, alignment is
1658 irrelevant for them. */
1659 if (STMT_VINFO_STRIDE_LOAD_P (stmt_info
))
1662 save_misalignment
= DR_MISALIGNMENT (dr
);
1663 vect_update_misalignment_for_peel (dr
, dr0
, npeel
);
1664 supportable_dr_alignment
= vect_supportable_dr_alignment (dr
, false);
1665 SET_DR_MISALIGNMENT (dr
, save_misalignment
);
1667 if (!supportable_dr_alignment
)
1674 if (do_peeling
&& known_alignment_for_access_p (dr0
) && npeel
== 0)
1676 stat
= vect_verify_datarefs_alignment (loop_vinfo
, NULL
);
1681 body_cost_vec
.release ();
1688 unsigned max_allowed_peel
1689 = PARAM_VALUE (PARAM_VECT_MAX_PEELING_FOR_ALIGNMENT
);
1690 if (max_allowed_peel
!= (unsigned)-1)
1692 unsigned max_peel
= npeel
;
1695 gimple dr_stmt
= DR_STMT (dr0
);
1696 stmt_vec_info vinfo
= vinfo_for_stmt (dr_stmt
);
1697 tree vtype
= STMT_VINFO_VECTYPE (vinfo
);
1698 max_peel
= TYPE_VECTOR_SUBPARTS (vtype
) - 1;
1700 if (max_peel
> max_allowed_peel
)
1703 if (dump_enabled_p ())
1704 dump_printf_loc (MSG_NOTE
, vect_location
,
1705 "Disable peeling, max peels reached: %d\n", max_peel
);
1712 stmt_info_for_cost
*si
;
1713 void *data
= LOOP_VINFO_TARGET_COST_DATA (loop_vinfo
);
1715 /* (1.2) Update the DR_MISALIGNMENT of each data reference DR_i.
1716 If the misalignment of DR_i is identical to that of dr0 then set
1717 DR_MISALIGNMENT (DR_i) to zero. If the misalignment of DR_i and
1718 dr0 are known at compile time then increment DR_MISALIGNMENT (DR_i)
1719 by the peeling factor times the element size of DR_i (MOD the
1720 vectorization factor times the size). Otherwise, the
1721 misalignment of DR_i must be set to unknown. */
1722 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
1724 vect_update_misalignment_for_peel (dr
, dr0
, npeel
);
1726 LOOP_VINFO_UNALIGNED_DR (loop_vinfo
) = dr0
;
1728 LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
) = npeel
;
1730 LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
)
1731 = DR_MISALIGNMENT (dr0
);
1732 SET_DR_MISALIGNMENT (dr0
, 0);
1733 if (dump_enabled_p ())
1735 dump_printf_loc (MSG_NOTE
, vect_location
,
1736 "Alignment of access forced using peeling.\n");
1737 dump_printf_loc (MSG_NOTE
, vect_location
,
1738 "Peeling for alignment will be applied.\n");
1740 /* We've delayed passing the inside-loop peeling costs to the
1741 target cost model until we were sure peeling would happen.
1743 if (body_cost_vec
.exists ())
1745 FOR_EACH_VEC_ELT (body_cost_vec
, i
, si
)
1747 struct _stmt_vec_info
*stmt_info
1748 = si
->stmt
? vinfo_for_stmt (si
->stmt
) : NULL
;
1749 (void) add_stmt_cost (data
, si
->count
, si
->kind
, stmt_info
,
1750 si
->misalign
, vect_body
);
1752 body_cost_vec
.release ();
1755 stat
= vect_verify_datarefs_alignment (loop_vinfo
, NULL
);
1761 body_cost_vec
.release ();
1763 /* (2) Versioning to force alignment. */
1765 /* Try versioning if:
1766 1) optimize loop for speed
1767 2) there is at least one unsupported misaligned data ref with an unknown
1769 3) all misaligned data refs with a known misalignment are supported, and
1770 4) the number of runtime alignment checks is within reason. */
1773 optimize_loop_nest_for_speed_p (loop
)
1774 && (!loop
->inner
); /* FORNOW */
1778 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
1780 stmt
= DR_STMT (dr
);
1781 stmt_info
= vinfo_for_stmt (stmt
);
1783 /* For interleaving, only the alignment of the first access
1785 if (aligned_access_p (dr
)
1786 || (STMT_VINFO_GROUPED_ACCESS (stmt_info
)
1787 && GROUP_FIRST_ELEMENT (stmt_info
) != stmt
))
1790 /* Strided loads perform only component accesses, alignment is
1791 irrelevant for them. */
1792 if (STMT_VINFO_STRIDE_LOAD_P (stmt_info
))
1795 supportable_dr_alignment
= vect_supportable_dr_alignment (dr
, false);
1797 if (!supportable_dr_alignment
)
1803 if (known_alignment_for_access_p (dr
)
1804 || LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).length ()
1805 >= (unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS
))
1807 do_versioning
= false;
1811 stmt
= DR_STMT (dr
);
1812 vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
1813 gcc_assert (vectype
);
1815 /* The rightmost bits of an aligned address must be zeros.
1816 Construct the mask needed for this test. For example,
1817 GET_MODE_SIZE for the vector mode V4SI is 16 bytes so the
1818 mask must be 15 = 0xf. */
1819 mask
= GET_MODE_SIZE (TYPE_MODE (vectype
)) - 1;
1821 /* FORNOW: use the same mask to test all potentially unaligned
1822 references in the loop. The vectorizer currently supports
1823 a single vector size, see the reference to
1824 GET_MODE_NUNITS (TYPE_MODE (vectype)) where the
1825 vectorization factor is computed. */
1826 gcc_assert (!LOOP_VINFO_PTR_MASK (loop_vinfo
)
1827 || LOOP_VINFO_PTR_MASK (loop_vinfo
) == mask
);
1828 LOOP_VINFO_PTR_MASK (loop_vinfo
) = mask
;
1829 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).safe_push (
1834 /* Versioning requires at least one misaligned data reference. */
1835 if (!LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
))
1836 do_versioning
= false;
1837 else if (!do_versioning
)
1838 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
).truncate (0);
1843 vec
<gimple
> may_misalign_stmts
1844 = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
);
1847 /* It can now be assumed that the data references in the statements
1848 in LOOP_VINFO_MAY_MISALIGN_STMTS will be aligned in the version
1849 of the loop being vectorized. */
1850 FOR_EACH_VEC_ELT (may_misalign_stmts
, i
, stmt
)
1852 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1853 dr
= STMT_VINFO_DATA_REF (stmt_info
);
1854 SET_DR_MISALIGNMENT (dr
, 0);
1855 if (dump_enabled_p ())
1856 dump_printf_loc (MSG_NOTE
, vect_location
,
1857 "Alignment of access forced using versioning.\n");
1860 if (dump_enabled_p ())
1861 dump_printf_loc (MSG_NOTE
, vect_location
,
1862 "Versioning for alignment will be applied.\n");
1864 /* Peeling and versioning can't be done together at this time. */
1865 gcc_assert (! (do_peeling
&& do_versioning
));
1867 stat
= vect_verify_datarefs_alignment (loop_vinfo
, NULL
);
1872 /* This point is reached if neither peeling nor versioning is being done. */
1873 gcc_assert (! (do_peeling
|| do_versioning
));
1875 stat
= vect_verify_datarefs_alignment (loop_vinfo
, NULL
);
1880 /* Function vect_find_same_alignment_drs.
1882 Update group and alignment relations according to the chosen
1883 vectorization factor. */
1886 vect_find_same_alignment_drs (struct data_dependence_relation
*ddr
,
1887 loop_vec_info loop_vinfo
)
1890 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1891 int vectorization_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1892 struct data_reference
*dra
= DDR_A (ddr
);
1893 struct data_reference
*drb
= DDR_B (ddr
);
1894 stmt_vec_info stmtinfo_a
= vinfo_for_stmt (DR_STMT (dra
));
1895 stmt_vec_info stmtinfo_b
= vinfo_for_stmt (DR_STMT (drb
));
1896 int dra_size
= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dra
))));
1897 int drb_size
= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (drb
))));
1898 lambda_vector dist_v
;
1899 unsigned int loop_depth
;
1901 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
1907 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
1910 /* Loop-based vectorization and known data dependence. */
1911 if (DDR_NUM_DIST_VECTS (ddr
) == 0)
1914 /* Data-dependence analysis reports a distance vector of zero
1915 for data-references that overlap only in the first iteration
1916 but have different sign step (see PR45764).
1917 So as a sanity check require equal DR_STEP. */
1918 if (!operand_equal_p (DR_STEP (dra
), DR_STEP (drb
), 0))
1921 loop_depth
= index_in_loop_nest (loop
->num
, DDR_LOOP_NEST (ddr
));
1922 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, dist_v
)
1924 int dist
= dist_v
[loop_depth
];
1926 if (dump_enabled_p ())
1927 dump_printf_loc (MSG_NOTE
, vect_location
,
1928 "dependence distance = %d.\n", dist
);
1930 /* Same loop iteration. */
1932 || (dist
% vectorization_factor
== 0 && dra_size
== drb_size
))
1934 /* Two references with distance zero have the same alignment. */
1935 STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a
).safe_push (drb
);
1936 STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b
).safe_push (dra
);
1937 if (dump_enabled_p ())
1939 dump_printf_loc (MSG_NOTE
, vect_location
,
1940 "accesses have the same alignment.\n");
1941 dump_printf (MSG_NOTE
,
1942 "dependence distance modulo vf == 0 between ");
1943 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dra
));
1944 dump_printf (MSG_NOTE
, " and ");
1945 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (drb
));
1946 dump_printf (MSG_NOTE
, "\n");
1953 /* Function vect_analyze_data_refs_alignment
1955 Analyze the alignment of the data-references in the loop.
1956 Return FALSE if a data reference is found that cannot be vectorized. */
1959 vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo
,
1960 bb_vec_info bb_vinfo
)
1962 if (dump_enabled_p ())
1963 dump_printf_loc (MSG_NOTE
, vect_location
,
1964 "=== vect_analyze_data_refs_alignment ===\n");
1966 /* Mark groups of data references with same alignment using
1967 data dependence information. */
1970 vec
<ddr_p
> ddrs
= LOOP_VINFO_DDRS (loop_vinfo
);
1971 struct data_dependence_relation
*ddr
;
1974 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
1975 vect_find_same_alignment_drs (ddr
, loop_vinfo
);
1978 if (!vect_compute_data_refs_alignment (loop_vinfo
, bb_vinfo
))
1980 if (dump_enabled_p ())
1981 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
1982 "not vectorized: can't calculate alignment "
1991 /* Analyze groups of accesses: check that DR belongs to a group of
1992 accesses of legal size, step, etc. Detect gaps, single element
1993 interleaving, and other special cases. Set grouped access info.
1994 Collect groups of strided stores for further use in SLP analysis. */
1997 vect_analyze_group_access (struct data_reference
*dr
)
1999 tree step
= DR_STEP (dr
);
2000 tree scalar_type
= TREE_TYPE (DR_REF (dr
));
2001 HOST_WIDE_INT type_size
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type
));
2002 gimple stmt
= DR_STMT (dr
);
2003 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2004 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
2005 bb_vec_info bb_vinfo
= STMT_VINFO_BB_VINFO (stmt_info
);
2006 HOST_WIDE_INT dr_step
= TREE_INT_CST_LOW (step
);
2007 HOST_WIDE_INT groupsize
, last_accessed_element
= 1;
2008 bool slp_impossible
= false;
2009 struct loop
*loop
= NULL
;
2012 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2014 /* For interleaving, GROUPSIZE is STEP counted in elements, i.e., the
2015 size of the interleaving group (including gaps). */
2016 groupsize
= absu_hwi (dr_step
) / type_size
;
2018 /* Not consecutive access is possible only if it is a part of interleaving. */
2019 if (!GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)))
2021 /* Check if it this DR is a part of interleaving, and is a single
2022 element of the group that is accessed in the loop. */
2024 /* Gaps are supported only for loads. STEP must be a multiple of the type
2025 size. The size of the group must be a power of 2. */
2027 && (dr_step
% type_size
) == 0
2029 && exact_log2 (groupsize
) != -1)
2031 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) = stmt
;
2032 GROUP_SIZE (vinfo_for_stmt (stmt
)) = groupsize
;
2033 if (dump_enabled_p ())
2035 dump_printf_loc (MSG_NOTE
, vect_location
,
2036 "Detected single element interleaving ");
2037 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dr
));
2038 dump_printf (MSG_NOTE
, " step ");
2039 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, step
);
2040 dump_printf (MSG_NOTE
, "\n");
2045 if (dump_enabled_p ())
2046 dump_printf_loc (MSG_NOTE
, vect_location
,
2047 "Data access with gaps requires scalar "
2051 if (dump_enabled_p ())
2052 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2053 "Peeling for outer loop is not"
2058 LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) = true;
2064 if (dump_enabled_p ())
2066 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2067 "not consecutive access ");
2068 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
2069 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
2074 /* Mark the statement as unvectorizable. */
2075 STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr
))) = false;
2082 if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) == stmt
)
2084 /* First stmt in the interleaving chain. Check the chain. */
2085 gimple next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (stmt
));
2086 struct data_reference
*data_ref
= dr
;
2087 unsigned int count
= 1;
2088 tree prev_init
= DR_INIT (data_ref
);
2090 HOST_WIDE_INT diff
, gaps
= 0;
2091 unsigned HOST_WIDE_INT count_in_bytes
;
2095 /* Skip same data-refs. In case that two or more stmts share
2096 data-ref (supported only for loads), we vectorize only the first
2097 stmt, and the rest get their vectorized loads from the first
2099 if (!tree_int_cst_compare (DR_INIT (data_ref
),
2100 DR_INIT (STMT_VINFO_DATA_REF (
2101 vinfo_for_stmt (next
)))))
2103 if (DR_IS_WRITE (data_ref
))
2105 if (dump_enabled_p ())
2106 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2107 "Two store stmts share the same dr.\n");
2111 /* For load use the same data-ref load. */
2112 GROUP_SAME_DR_STMT (vinfo_for_stmt (next
)) = prev
;
2115 next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next
));
2120 data_ref
= STMT_VINFO_DATA_REF (vinfo_for_stmt (next
));
2122 /* All group members have the same STEP by construction. */
2123 gcc_checking_assert (operand_equal_p (DR_STEP (data_ref
), step
, 0));
2125 /* Check that the distance between two accesses is equal to the type
2126 size. Otherwise, we have gaps. */
2127 diff
= (TREE_INT_CST_LOW (DR_INIT (data_ref
))
2128 - TREE_INT_CST_LOW (prev_init
)) / type_size
;
2131 /* FORNOW: SLP of accesses with gaps is not supported. */
2132 slp_impossible
= true;
2133 if (DR_IS_WRITE (data_ref
))
2135 if (dump_enabled_p ())
2136 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2137 "interleaved store with gaps\n");
2144 last_accessed_element
+= diff
;
2146 /* Store the gap from the previous member of the group. If there is no
2147 gap in the access, GROUP_GAP is always 1. */
2148 GROUP_GAP (vinfo_for_stmt (next
)) = diff
;
2150 prev_init
= DR_INIT (data_ref
);
2151 next
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next
));
2152 /* Count the number of data-refs in the chain. */
2156 /* COUNT is the number of accesses found, we multiply it by the size of
2157 the type to get COUNT_IN_BYTES. */
2158 count_in_bytes
= type_size
* count
;
2160 /* Check that the size of the interleaving (including gaps) is not
2161 greater than STEP. */
2163 && absu_hwi (dr_step
) < count_in_bytes
+ gaps
* type_size
)
2165 if (dump_enabled_p ())
2167 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2168 "interleaving size is greater than step for ");
2169 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
2171 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
2176 /* Check that the size of the interleaving is equal to STEP for stores,
2177 i.e., that there are no gaps. */
2179 && absu_hwi (dr_step
) != count_in_bytes
)
2181 if (DR_IS_READ (dr
))
2183 slp_impossible
= true;
2184 /* There is a gap after the last load in the group. This gap is a
2185 difference between the groupsize and the number of elements.
2186 When there is no gap, this difference should be 0. */
2187 GROUP_GAP (vinfo_for_stmt (stmt
)) = groupsize
- count
;
2191 if (dump_enabled_p ())
2192 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2193 "interleaved store with gaps\n");
2198 /* Check that STEP is a multiple of type size. */
2200 && (dr_step
% type_size
) != 0)
2202 if (dump_enabled_p ())
2204 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2205 "step is not a multiple of type size: step ");
2206 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, step
);
2207 dump_printf (MSG_MISSED_OPTIMIZATION
, " size ");
2208 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
,
2209 TYPE_SIZE_UNIT (scalar_type
));
2210 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
2218 GROUP_SIZE (vinfo_for_stmt (stmt
)) = groupsize
;
2219 if (dump_enabled_p ())
2220 dump_printf_loc (MSG_NOTE
, vect_location
,
2221 "Detected interleaving of size %d\n", (int)groupsize
);
2223 /* SLP: create an SLP data structure for every interleaving group of
2224 stores for further analysis in vect_analyse_slp. */
2225 if (DR_IS_WRITE (dr
) && !slp_impossible
)
2228 LOOP_VINFO_GROUPED_STORES (loop_vinfo
).safe_push (stmt
);
2230 BB_VINFO_GROUPED_STORES (bb_vinfo
).safe_push (stmt
);
2233 /* There is a gap in the end of the group. */
2234 if (groupsize
- last_accessed_element
> 0 && loop_vinfo
)
2236 if (dump_enabled_p ())
2237 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2238 "Data access with gaps requires scalar "
2242 if (dump_enabled_p ())
2243 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2244 "Peeling for outer loop is not supported\n");
2248 LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
) = true;
2256 /* Analyze the access pattern of the data-reference DR.
2257 In case of non-consecutive accesses call vect_analyze_group_access() to
2258 analyze groups of accesses. */
2261 vect_analyze_data_ref_access (struct data_reference
*dr
)
2263 tree step
= DR_STEP (dr
);
2264 tree scalar_type
= TREE_TYPE (DR_REF (dr
));
2265 gimple stmt
= DR_STMT (dr
);
2266 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2267 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
2268 struct loop
*loop
= NULL
;
2271 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2273 if (loop_vinfo
&& !step
)
2275 if (dump_enabled_p ())
2276 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2277 "bad data-ref access in loop\n");
2281 /* Allow invariant loads in not nested loops. */
2282 if (loop_vinfo
&& integer_zerop (step
))
2284 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) = NULL
;
2285 if (nested_in_vect_loop_p (loop
, stmt
))
2287 if (dump_enabled_p ())
2288 dump_printf_loc (MSG_NOTE
, vect_location
,
2289 "zero step in inner loop of nest\n");
2292 return DR_IS_READ (dr
);
2295 if (loop
&& nested_in_vect_loop_p (loop
, stmt
))
2297 /* Interleaved accesses are not yet supported within outer-loop
2298 vectorization for references in the inner-loop. */
2299 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) = NULL
;
2301 /* For the rest of the analysis we use the outer-loop step. */
2302 step
= STMT_VINFO_DR_STEP (stmt_info
);
2303 if (integer_zerop (step
))
2305 if (dump_enabled_p ())
2306 dump_printf_loc (MSG_NOTE
, vect_location
,
2307 "zero step in outer loop.\n");
2308 if (DR_IS_READ (dr
))
2316 if (TREE_CODE (step
) == INTEGER_CST
)
2318 HOST_WIDE_INT dr_step
= TREE_INT_CST_LOW (step
);
2319 if (!tree_int_cst_compare (step
, TYPE_SIZE_UNIT (scalar_type
))
2321 && !compare_tree_int (TYPE_SIZE_UNIT (scalar_type
), -dr_step
)))
2323 /* Mark that it is not interleaving. */
2324 GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
)) = NULL
;
2329 if (loop
&& nested_in_vect_loop_p (loop
, stmt
))
2331 if (dump_enabled_p ())
2332 dump_printf_loc (MSG_NOTE
, vect_location
,
2333 "grouped access in outer loop.\n");
2337 /* Assume this is a DR handled by non-constant strided load case. */
2338 if (TREE_CODE (step
) != INTEGER_CST
)
2339 return STMT_VINFO_STRIDE_LOAD_P (stmt_info
);
2341 /* Not consecutive access - check if it's a part of interleaving group. */
2342 return vect_analyze_group_access (dr
);
2347 /* A helper function used in the comparator function to sort data
2348 references. T1 and T2 are two data references to be compared.
2349 The function returns -1, 0, or 1. */
2352 compare_tree (tree t1
, tree t2
)
2355 enum tree_code code
;
2366 if (TREE_CODE (t1
) != TREE_CODE (t2
))
2367 return TREE_CODE (t1
) < TREE_CODE (t2
) ? -1 : 1;
2369 code
= TREE_CODE (t1
);
2372 /* For const values, we can just use hash values for comparisons. */
2380 hashval_t h1
= iterative_hash_expr (t1
, 0);
2381 hashval_t h2
= iterative_hash_expr (t2
, 0);
2383 return h1
< h2
? -1 : 1;
2388 cmp
= compare_tree (SSA_NAME_VAR (t1
), SSA_NAME_VAR (t2
));
2392 if (SSA_NAME_VERSION (t1
) != SSA_NAME_VERSION (t2
))
2393 return SSA_NAME_VERSION (t1
) < SSA_NAME_VERSION (t2
) ? -1 : 1;
2397 tclass
= TREE_CODE_CLASS (code
);
2399 /* For var-decl, we could compare their UIDs. */
2400 if (tclass
== tcc_declaration
)
2402 if (DECL_UID (t1
) != DECL_UID (t2
))
2403 return DECL_UID (t1
) < DECL_UID (t2
) ? -1 : 1;
2407 /* For expressions with operands, compare their operands recursively. */
2408 for (i
= TREE_OPERAND_LENGTH (t1
) - 1; i
>= 0; --i
)
2410 cmp
= compare_tree (TREE_OPERAND (t1
, i
), TREE_OPERAND (t2
, i
));
2420 /* Compare two data-references DRA and DRB to group them into chunks
2421 suitable for grouping. */
2424 dr_group_sort_cmp (const void *dra_
, const void *drb_
)
2426 data_reference_p dra
= *(data_reference_p
*)const_cast<void *>(dra_
);
2427 data_reference_p drb
= *(data_reference_p
*)const_cast<void *>(drb_
);
2430 /* Stabilize sort. */
2434 /* Ordering of DRs according to base. */
2435 if (!operand_equal_p (DR_BASE_ADDRESS (dra
), DR_BASE_ADDRESS (drb
), 0))
2437 cmp
= compare_tree (DR_BASE_ADDRESS (dra
), DR_BASE_ADDRESS (drb
));
2442 /* And according to DR_OFFSET. */
2443 if (!dr_equal_offsets_p (dra
, drb
))
2445 cmp
= compare_tree (DR_OFFSET (dra
), DR_OFFSET (drb
));
2450 /* Put reads before writes. */
2451 if (DR_IS_READ (dra
) != DR_IS_READ (drb
))
2452 return DR_IS_READ (dra
) ? -1 : 1;
2454 /* Then sort after access size. */
2455 if (!operand_equal_p (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra
))),
2456 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb
))), 0))
2458 cmp
= compare_tree (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra
))),
2459 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb
))));
2464 /* And after step. */
2465 if (!operand_equal_p (DR_STEP (dra
), DR_STEP (drb
), 0))
2467 cmp
= compare_tree (DR_STEP (dra
), DR_STEP (drb
));
2472 /* Then sort after DR_INIT. In case of identical DRs sort after stmt UID. */
2473 cmp
= tree_int_cst_compare (DR_INIT (dra
), DR_INIT (drb
));
2475 return gimple_uid (DR_STMT (dra
)) < gimple_uid (DR_STMT (drb
)) ? -1 : 1;
2479 /* Function vect_analyze_data_ref_accesses.
2481 Analyze the access pattern of all the data references in the loop.
2483 FORNOW: the only access pattern that is considered vectorizable is a
2484 simple step 1 (consecutive) access.
2486 FORNOW: handle only arrays and pointer accesses. */
2489 vect_analyze_data_ref_accesses (loop_vec_info loop_vinfo
, bb_vec_info bb_vinfo
)
2492 vec
<data_reference_p
> datarefs
;
2493 struct data_reference
*dr
;
2495 if (dump_enabled_p ())
2496 dump_printf_loc (MSG_NOTE
, vect_location
,
2497 "=== vect_analyze_data_ref_accesses ===\n");
2500 datarefs
= LOOP_VINFO_DATAREFS (loop_vinfo
);
2502 datarefs
= BB_VINFO_DATAREFS (bb_vinfo
);
2504 if (datarefs
.is_empty ())
2507 /* Sort the array of datarefs to make building the interleaving chains
2508 linear. Don't modify the original vector's order, it is needed for
2509 determining what dependencies are reversed. */
2510 vec
<data_reference_p
> datarefs_copy
= datarefs
.copy ();
2511 qsort (datarefs_copy
.address (), datarefs_copy
.length (),
2512 sizeof (data_reference_p
), dr_group_sort_cmp
);
2514 /* Build the interleaving chains. */
2515 for (i
= 0; i
< datarefs_copy
.length () - 1;)
2517 data_reference_p dra
= datarefs_copy
[i
];
2518 stmt_vec_info stmtinfo_a
= vinfo_for_stmt (DR_STMT (dra
));
2519 stmt_vec_info lastinfo
= NULL
;
2520 for (i
= i
+ 1; i
< datarefs_copy
.length (); ++i
)
2522 data_reference_p drb
= datarefs_copy
[i
];
2523 stmt_vec_info stmtinfo_b
= vinfo_for_stmt (DR_STMT (drb
));
2525 /* ??? Imperfect sorting (non-compatible types, non-modulo
2526 accesses, same accesses) can lead to a group to be artificially
2527 split here as we don't just skip over those. If it really
2528 matters we can push those to a worklist and re-iterate
2529 over them. The we can just skip ahead to the next DR here. */
2531 /* Check that the data-refs have same first location (except init)
2532 and they are both either store or load (not load and store). */
2533 if (DR_IS_READ (dra
) != DR_IS_READ (drb
)
2534 || !operand_equal_p (DR_BASE_ADDRESS (dra
),
2535 DR_BASE_ADDRESS (drb
), 0)
2536 || !dr_equal_offsets_p (dra
, drb
))
2539 /* Check that the data-refs have the same constant size and step. */
2540 tree sza
= TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra
)));
2541 tree szb
= TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb
)));
2542 if (!tree_fits_uhwi_p (sza
)
2543 || !tree_fits_uhwi_p (szb
)
2544 || !tree_int_cst_equal (sza
, szb
)
2545 || !tree_fits_shwi_p (DR_STEP (dra
))
2546 || !tree_fits_shwi_p (DR_STEP (drb
))
2547 || !tree_int_cst_equal (DR_STEP (dra
), DR_STEP (drb
)))
2550 /* Do not place the same access in the interleaving chain twice. */
2551 if (tree_int_cst_compare (DR_INIT (dra
), DR_INIT (drb
)) == 0)
2554 /* Check the types are compatible.
2555 ??? We don't distinguish this during sorting. */
2556 if (!types_compatible_p (TREE_TYPE (DR_REF (dra
)),
2557 TREE_TYPE (DR_REF (drb
))))
2560 /* Sorting has ensured that DR_INIT (dra) <= DR_INIT (drb). */
2561 HOST_WIDE_INT init_a
= TREE_INT_CST_LOW (DR_INIT (dra
));
2562 HOST_WIDE_INT init_b
= TREE_INT_CST_LOW (DR_INIT (drb
));
2563 gcc_assert (init_a
< init_b
);
2565 /* If init_b == init_a + the size of the type * k, we have an
2566 interleaving, and DRA is accessed before DRB. */
2567 HOST_WIDE_INT type_size_a
= tree_to_uhwi (sza
);
2568 if ((init_b
- init_a
) % type_size_a
!= 0)
2571 /* The step (if not zero) is greater than the difference between
2572 data-refs' inits. This splits groups into suitable sizes. */
2573 HOST_WIDE_INT step
= tree_to_shwi (DR_STEP (dra
));
2574 if (step
!= 0 && step
<= (init_b
- init_a
))
2577 if (dump_enabled_p ())
2579 dump_printf_loc (MSG_NOTE
, vect_location
,
2580 "Detected interleaving ");
2581 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (dra
));
2582 dump_printf (MSG_NOTE
, " and ");
2583 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_REF (drb
));
2584 dump_printf (MSG_NOTE
, "\n");
2587 /* Link the found element into the group list. */
2588 if (!GROUP_FIRST_ELEMENT (stmtinfo_a
))
2590 GROUP_FIRST_ELEMENT (stmtinfo_a
) = DR_STMT (dra
);
2591 lastinfo
= stmtinfo_a
;
2593 GROUP_FIRST_ELEMENT (stmtinfo_b
) = DR_STMT (dra
);
2594 GROUP_NEXT_ELEMENT (lastinfo
) = DR_STMT (drb
);
2595 lastinfo
= stmtinfo_b
;
2599 FOR_EACH_VEC_ELT (datarefs_copy
, i
, dr
)
2600 if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr
)))
2601 && !vect_analyze_data_ref_access (dr
))
2603 if (dump_enabled_p ())
2604 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
2605 "not vectorized: complicated access pattern.\n");
2609 /* Mark the statement as not vectorizable. */
2610 STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr
))) = false;
2615 datarefs_copy
.release ();
2620 datarefs_copy
.release ();
2625 /* Operator == between two dr_with_seg_len objects.
2627 This equality operator is used to make sure two data refs
2628 are the same one so that we will consider to combine the
2629 aliasing checks of those two pairs of data dependent data
2633 operator == (const dr_with_seg_len
& d1
,
2634 const dr_with_seg_len
& d2
)
2636 return operand_equal_p (DR_BASE_ADDRESS (d1
.dr
),
2637 DR_BASE_ADDRESS (d2
.dr
), 0)
2638 && compare_tree (d1
.offset
, d2
.offset
) == 0
2639 && compare_tree (d1
.seg_len
, d2
.seg_len
) == 0;
2642 /* Function comp_dr_with_seg_len_pair.
2644 Comparison function for sorting objects of dr_with_seg_len_pair_t
2645 so that we can combine aliasing checks in one scan. */
2648 comp_dr_with_seg_len_pair (const void *p1_
, const void *p2_
)
2650 const dr_with_seg_len_pair_t
* p1
= (const dr_with_seg_len_pair_t
*) p1_
;
2651 const dr_with_seg_len_pair_t
* p2
= (const dr_with_seg_len_pair_t
*) p2_
;
2653 const dr_with_seg_len
&p11
= p1
->first
,
2658 /* For DR pairs (a, b) and (c, d), we only consider to merge the alias checks
2659 if a and c have the same basic address snd step, and b and d have the same
2660 address and step. Therefore, if any a&c or b&d don't have the same address
2661 and step, we don't care the order of those two pairs after sorting. */
2664 if ((comp_res
= compare_tree (DR_BASE_ADDRESS (p11
.dr
),
2665 DR_BASE_ADDRESS (p21
.dr
))) != 0)
2667 if ((comp_res
= compare_tree (DR_BASE_ADDRESS (p12
.dr
),
2668 DR_BASE_ADDRESS (p22
.dr
))) != 0)
2670 if ((comp_res
= compare_tree (DR_STEP (p11
.dr
), DR_STEP (p21
.dr
))) != 0)
2672 if ((comp_res
= compare_tree (DR_STEP (p12
.dr
), DR_STEP (p22
.dr
))) != 0)
2674 if ((comp_res
= compare_tree (p11
.offset
, p21
.offset
)) != 0)
2676 if ((comp_res
= compare_tree (p12
.offset
, p22
.offset
)) != 0)
2682 template <class T
> static void
2690 /* Function vect_vfa_segment_size.
2692 Create an expression that computes the size of segment
2693 that will be accessed for a data reference. The functions takes into
2694 account that realignment loads may access one more vector.
2697 DR: The data reference.
2698 LENGTH_FACTOR: segment length to consider.
2700 Return an expression whose value is the size of segment which will be
2704 vect_vfa_segment_size (struct data_reference
*dr
, tree length_factor
)
2706 tree segment_length
;
2708 if (integer_zerop (DR_STEP (dr
)))
2709 segment_length
= TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr
)));
2711 segment_length
= size_binop (MULT_EXPR
,
2712 fold_convert (sizetype
, DR_STEP (dr
)),
2713 fold_convert (sizetype
, length_factor
));
2715 if (vect_supportable_dr_alignment (dr
, false)
2716 == dr_explicit_realign_optimized
)
2718 tree vector_size
= TYPE_SIZE_UNIT
2719 (STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr
))));
2721 segment_length
= size_binop (PLUS_EXPR
, segment_length
, vector_size
);
2723 return segment_length
;
2726 /* Function vect_prune_runtime_alias_test_list.
2728 Prune a list of ddrs to be tested at run-time by versioning for alias.
2729 Merge several alias checks into one if possible.
2730 Return FALSE if resulting list of ddrs is longer then allowed by
2731 PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS, otherwise return TRUE. */
2734 vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo
)
2736 vec
<ddr_p
> may_alias_ddrs
=
2737 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
);
2738 vec
<dr_with_seg_len_pair_t
>& comp_alias_ddrs
=
2739 LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo
);
2740 int vect_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2741 tree scalar_loop_iters
= LOOP_VINFO_NITERS (loop_vinfo
);
2747 if (dump_enabled_p ())
2748 dump_printf_loc (MSG_NOTE
, vect_location
,
2749 "=== vect_prune_runtime_alias_test_list ===\n");
2751 if (may_alias_ddrs
.is_empty ())
2754 /* Basically, for each pair of dependent data refs store_ptr_0
2755 and load_ptr_0, we create an expression:
2757 ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
2758 || (load_ptr_0 + load_segment_length_0) <= store_ptr_0))
2760 for aliasing checks. However, in some cases we can decrease
2761 the number of checks by combining two checks into one. For
2762 example, suppose we have another pair of data refs store_ptr_0
2763 and load_ptr_1, and if the following condition is satisfied:
2765 load_ptr_0 < load_ptr_1 &&
2766 load_ptr_1 - load_ptr_0 - load_segment_length_0 < store_segment_length_0
2768 (this condition means, in each iteration of vectorized loop,
2769 the accessed memory of store_ptr_0 cannot be between the memory
2770 of load_ptr_0 and load_ptr_1.)
2772 we then can use only the following expression to finish the
2773 alising checks between store_ptr_0 & load_ptr_0 and
2774 store_ptr_0 & load_ptr_1:
2776 ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
2777 || (load_ptr_1 + load_segment_length_1 <= store_ptr_0))
2779 Note that we only consider that load_ptr_0 and load_ptr_1 have the
2780 same basic address. */
2782 comp_alias_ddrs
.create (may_alias_ddrs
.length ());
2784 /* First, we collect all data ref pairs for aliasing checks. */
2785 FOR_EACH_VEC_ELT (may_alias_ddrs
, i
, ddr
)
2787 struct data_reference
*dr_a
, *dr_b
;
2788 gimple dr_group_first_a
, dr_group_first_b
;
2789 tree segment_length_a
, segment_length_b
;
2790 gimple stmt_a
, stmt_b
;
2793 stmt_a
= DR_STMT (DDR_A (ddr
));
2794 dr_group_first_a
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_a
));
2795 if (dr_group_first_a
)
2797 stmt_a
= dr_group_first_a
;
2798 dr_a
= STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt_a
));
2802 stmt_b
= DR_STMT (DDR_B (ddr
));
2803 dr_group_first_b
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_b
));
2804 if (dr_group_first_b
)
2806 stmt_b
= dr_group_first_b
;
2807 dr_b
= STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt_b
));
2810 if (!operand_equal_p (DR_STEP (dr_a
), DR_STEP (dr_b
), 0))
2811 length_factor
= scalar_loop_iters
;
2813 length_factor
= size_int (vect_factor
);
2814 segment_length_a
= vect_vfa_segment_size (dr_a
, length_factor
);
2815 segment_length_b
= vect_vfa_segment_size (dr_b
, length_factor
);
2817 dr_with_seg_len_pair_t dr_with_seg_len_pair
2818 (dr_with_seg_len (dr_a
, segment_length_a
),
2819 dr_with_seg_len (dr_b
, segment_length_b
));
2821 if (compare_tree (DR_BASE_ADDRESS (dr_a
), DR_BASE_ADDRESS (dr_b
)) > 0)
2822 swap (dr_with_seg_len_pair
.first
, dr_with_seg_len_pair
.second
);
2824 comp_alias_ddrs
.safe_push (dr_with_seg_len_pair
);
2827 /* Second, we sort the collected data ref pairs so that we can scan
2828 them once to combine all possible aliasing checks. */
2829 comp_alias_ddrs
.qsort (comp_dr_with_seg_len_pair
);
2831 /* Third, we scan the sorted dr pairs and check if we can combine
2832 alias checks of two neighbouring dr pairs. */
2833 for (size_t i
= 1; i
< comp_alias_ddrs
.length (); ++i
)
2835 /* Deal with two ddrs (dr_a1, dr_b1) and (dr_a2, dr_b2). */
2836 dr_with_seg_len
*dr_a1
= &comp_alias_ddrs
[i
-1].first
,
2837 *dr_b1
= &comp_alias_ddrs
[i
-1].second
,
2838 *dr_a2
= &comp_alias_ddrs
[i
].first
,
2839 *dr_b2
= &comp_alias_ddrs
[i
].second
;
2841 /* Remove duplicate data ref pairs. */
2842 if (*dr_a1
== *dr_a2
&& *dr_b1
== *dr_b2
)
2844 if (dump_enabled_p ())
2846 dump_printf_loc (MSG_NOTE
, vect_location
,
2847 "found equal ranges ");
2848 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2849 DR_REF (dr_a1
->dr
));
2850 dump_printf (MSG_NOTE
, ", ");
2851 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2852 DR_REF (dr_b1
->dr
));
2853 dump_printf (MSG_NOTE
, " and ");
2854 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2855 DR_REF (dr_a2
->dr
));
2856 dump_printf (MSG_NOTE
, ", ");
2857 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2858 DR_REF (dr_b2
->dr
));
2859 dump_printf (MSG_NOTE
, "\n");
2862 comp_alias_ddrs
.ordered_remove (i
--);
2866 if (*dr_a1
== *dr_a2
|| *dr_b1
== *dr_b2
)
2868 /* We consider the case that DR_B1 and DR_B2 are same memrefs,
2869 and DR_A1 and DR_A2 are two consecutive memrefs. */
2870 if (*dr_a1
== *dr_a2
)
2872 swap (dr_a1
, dr_b1
);
2873 swap (dr_a2
, dr_b2
);
2876 if (!operand_equal_p (DR_BASE_ADDRESS (dr_a1
->dr
),
2877 DR_BASE_ADDRESS (dr_a2
->dr
),
2879 || !tree_fits_shwi_p (dr_a1
->offset
)
2880 || !tree_fits_shwi_p (dr_a2
->offset
))
2883 HOST_WIDE_INT diff
= (tree_to_shwi (dr_a2
->offset
)
2884 - tree_to_shwi (dr_a1
->offset
));
2887 /* Now we check if the following condition is satisfied:
2889 DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
2891 where DIFF = DR_A2->OFFSET - DR_A1->OFFSET. However,
2892 SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we
2893 have to make a best estimation. We can get the minimum value
2894 of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B,
2895 then either of the following two conditions can guarantee the
2898 1: DIFF <= MIN_SEG_LEN_B
2899 2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B
2903 HOST_WIDE_INT min_seg_len_b
= (tree_fits_shwi_p (dr_b1
->seg_len
)
2904 ? tree_to_shwi (dr_b1
->seg_len
)
2907 if (diff
<= min_seg_len_b
2908 || (tree_fits_shwi_p (dr_a1
->seg_len
)
2909 && diff
- tree_to_shwi (dr_a1
->seg_len
) < min_seg_len_b
))
2911 if (dump_enabled_p ())
2913 dump_printf_loc (MSG_NOTE
, vect_location
,
2914 "merging ranges for ");
2915 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2916 DR_REF (dr_a1
->dr
));
2917 dump_printf (MSG_NOTE
, ", ");
2918 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2919 DR_REF (dr_b1
->dr
));
2920 dump_printf (MSG_NOTE
, " and ");
2921 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2922 DR_REF (dr_a2
->dr
));
2923 dump_printf (MSG_NOTE
, ", ");
2924 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
2925 DR_REF (dr_b2
->dr
));
2926 dump_printf (MSG_NOTE
, "\n");
2929 dr_a1
->seg_len
= size_binop (PLUS_EXPR
,
2930 dr_a2
->seg_len
, size_int (diff
));
2931 comp_alias_ddrs
.ordered_remove (i
--);
2936 dump_printf_loc (MSG_NOTE
, vect_location
,
2937 "improved number of alias checks from %d to %d\n",
2938 may_alias_ddrs
.length (), comp_alias_ddrs
.length ());
2939 if ((int) comp_alias_ddrs
.length () >
2940 PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS
))
2946 /* Check whether a non-affine read in stmt is suitable for gather load
2947 and if so, return a builtin decl for that operation. */
2950 vect_check_gather (gimple stmt
, loop_vec_info loop_vinfo
, tree
*basep
,
2951 tree
*offp
, int *scalep
)
2953 HOST_WIDE_INT scale
= 1, pbitpos
, pbitsize
;
2954 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2955 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
2956 struct data_reference
*dr
= STMT_VINFO_DATA_REF (stmt_info
);
2957 tree offtype
= NULL_TREE
;
2958 tree decl
, base
, off
;
2959 enum machine_mode pmode
;
2960 int punsignedp
, pvolatilep
;
2963 /* For masked loads/stores, DR_REF (dr) is an artificial MEM_REF,
2964 see if we can use the def stmt of the address. */
2965 if (is_gimple_call (stmt
)
2966 && gimple_call_internal_p (stmt
)
2967 && (gimple_call_internal_fn (stmt
) == IFN_MASK_LOAD
2968 || gimple_call_internal_fn (stmt
) == IFN_MASK_STORE
)
2969 && TREE_CODE (base
) == MEM_REF
2970 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
2971 && integer_zerop (TREE_OPERAND (base
, 1))
2972 && !expr_invariant_in_loop_p (loop
, TREE_OPERAND (base
, 0)))
2974 gimple def_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (base
, 0));
2975 if (is_gimple_assign (def_stmt
)
2976 && gimple_assign_rhs_code (def_stmt
) == ADDR_EXPR
)
2977 base
= TREE_OPERAND (gimple_assign_rhs1 (def_stmt
), 0);
2980 /* The gather builtins need address of the form
2981 loop_invariant + vector * {1, 2, 4, 8}
2983 loop_invariant + sign_extend (vector) * { 1, 2, 4, 8 }.
2984 Unfortunately DR_BASE_ADDRESS/DR_OFFSET can be a mixture
2985 of loop invariants/SSA_NAMEs defined in the loop, with casts,
2986 multiplications and additions in it. To get a vector, we need
2987 a single SSA_NAME that will be defined in the loop and will
2988 contain everything that is not loop invariant and that can be
2989 vectorized. The following code attempts to find such a preexistng
2990 SSA_NAME OFF and put the loop invariants into a tree BASE
2991 that can be gimplified before the loop. */
2992 base
= get_inner_reference (base
, &pbitsize
, &pbitpos
, &off
,
2993 &pmode
, &punsignedp
, &pvolatilep
, false);
2994 gcc_assert (base
!= NULL_TREE
&& (pbitpos
% BITS_PER_UNIT
) == 0);
2996 if (TREE_CODE (base
) == MEM_REF
)
2998 if (!integer_zerop (TREE_OPERAND (base
, 1)))
3000 if (off
== NULL_TREE
)
3002 offset_int moff
= mem_ref_offset (base
);
3003 off
= wide_int_to_tree (sizetype
, moff
);
3006 off
= size_binop (PLUS_EXPR
, off
,
3007 fold_convert (sizetype
, TREE_OPERAND (base
, 1)));
3009 base
= TREE_OPERAND (base
, 0);
3012 base
= build_fold_addr_expr (base
);
3014 if (off
== NULL_TREE
)
3015 off
= size_zero_node
;
3017 /* If base is not loop invariant, either off is 0, then we start with just
3018 the constant offset in the loop invariant BASE and continue with base
3019 as OFF, otherwise give up.
3020 We could handle that case by gimplifying the addition of base + off
3021 into some SSA_NAME and use that as off, but for now punt. */
3022 if (!expr_invariant_in_loop_p (loop
, base
))
3024 if (!integer_zerop (off
))
3027 base
= size_int (pbitpos
/ BITS_PER_UNIT
);
3029 /* Otherwise put base + constant offset into the loop invariant BASE
3030 and continue with OFF. */
3033 base
= fold_convert (sizetype
, base
);
3034 base
= size_binop (PLUS_EXPR
, base
, size_int (pbitpos
/ BITS_PER_UNIT
));
3037 /* OFF at this point may be either a SSA_NAME or some tree expression
3038 from get_inner_reference. Try to peel off loop invariants from it
3039 into BASE as long as possible. */
3041 while (offtype
== NULL_TREE
)
3043 enum tree_code code
;
3044 tree op0
, op1
, add
= NULL_TREE
;
3046 if (TREE_CODE (off
) == SSA_NAME
)
3048 gimple def_stmt
= SSA_NAME_DEF_STMT (off
);
3050 if (expr_invariant_in_loop_p (loop
, off
))
3053 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
3056 op0
= gimple_assign_rhs1 (def_stmt
);
3057 code
= gimple_assign_rhs_code (def_stmt
);
3058 op1
= gimple_assign_rhs2 (def_stmt
);
3062 if (get_gimple_rhs_class (TREE_CODE (off
)) == GIMPLE_TERNARY_RHS
)
3064 code
= TREE_CODE (off
);
3065 extract_ops_from_tree (off
, &code
, &op0
, &op1
);
3069 case POINTER_PLUS_EXPR
:
3071 if (expr_invariant_in_loop_p (loop
, op0
))
3076 add
= fold_convert (sizetype
, add
);
3078 add
= size_binop (MULT_EXPR
, add
, size_int (scale
));
3079 base
= size_binop (PLUS_EXPR
, base
, add
);
3082 if (expr_invariant_in_loop_p (loop
, op1
))
3090 if (expr_invariant_in_loop_p (loop
, op1
))
3092 add
= fold_convert (sizetype
, op1
);
3093 add
= size_binop (MINUS_EXPR
, size_zero_node
, add
);
3099 if (scale
== 1 && tree_fits_shwi_p (op1
))
3101 scale
= tree_to_shwi (op1
);
3110 if (!POINTER_TYPE_P (TREE_TYPE (op0
))
3111 && !INTEGRAL_TYPE_P (TREE_TYPE (op0
)))
3113 if (TYPE_PRECISION (TREE_TYPE (op0
))
3114 == TYPE_PRECISION (TREE_TYPE (off
)))
3119 if (TYPE_PRECISION (TREE_TYPE (op0
))
3120 < TYPE_PRECISION (TREE_TYPE (off
)))
3123 offtype
= TREE_TYPE (off
);
3134 /* If at the end OFF still isn't a SSA_NAME or isn't
3135 defined in the loop, punt. */
3136 if (TREE_CODE (off
) != SSA_NAME
3137 || expr_invariant_in_loop_p (loop
, off
))
3140 if (offtype
== NULL_TREE
)
3141 offtype
= TREE_TYPE (off
);
3143 decl
= targetm
.vectorize
.builtin_gather (STMT_VINFO_VECTYPE (stmt_info
),
3145 if (decl
== NULL_TREE
)
3157 /* Function vect_analyze_data_refs.
3159 Find all the data references in the loop or basic block.
3161 The general structure of the analysis of data refs in the vectorizer is as
3163 1- vect_analyze_data_refs(loop/bb): call
3164 compute_data_dependences_for_loop/bb to find and analyze all data-refs
3165 in the loop/bb and their dependences.
3166 2- vect_analyze_dependences(): apply dependence testing using ddrs.
3167 3- vect_analyze_drs_alignment(): check that ref_stmt.alignment is ok.
3168 4- vect_analyze_drs_access(): check that ref_stmt.step is ok.
3173 vect_analyze_data_refs (loop_vec_info loop_vinfo
,
3174 bb_vec_info bb_vinfo
,
3175 int *min_vf
, unsigned *n_stmts
)
3177 struct loop
*loop
= NULL
;
3178 basic_block bb
= NULL
;
3180 vec
<data_reference_p
> datarefs
;
3181 struct data_reference
*dr
;
3184 if (dump_enabled_p ())
3185 dump_printf_loc (MSG_NOTE
, vect_location
,
3186 "=== vect_analyze_data_refs ===\n");
3190 basic_block
*bbs
= LOOP_VINFO_BBS (loop_vinfo
);
3192 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3193 datarefs
= LOOP_VINFO_DATAREFS (loop_vinfo
);
3194 if (!find_loop_nest (loop
, &LOOP_VINFO_LOOP_NEST (loop_vinfo
)))
3196 if (dump_enabled_p ())
3197 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3198 "not vectorized: loop contains function calls"
3199 " or data references that cannot be analyzed\n");
3203 for (i
= 0; i
< loop
->num_nodes
; i
++)
3205 gimple_stmt_iterator gsi
;
3207 for (gsi
= gsi_start_bb (bbs
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
3209 gimple stmt
= gsi_stmt (gsi
);
3210 if (is_gimple_debug (stmt
))
3213 if (!find_data_references_in_stmt (loop
, stmt
, &datarefs
))
3215 if (is_gimple_call (stmt
) && loop
->safelen
)
3217 tree fndecl
= gimple_call_fndecl (stmt
), op
;
3218 if (fndecl
!= NULL_TREE
)
3220 struct cgraph_node
*node
= cgraph_get_node (fndecl
);
3221 if (node
!= NULL
&& node
->simd_clones
!= NULL
)
3223 unsigned int j
, n
= gimple_call_num_args (stmt
);
3224 for (j
= 0; j
< n
; j
++)
3226 op
= gimple_call_arg (stmt
, j
);
3228 || (REFERENCE_CLASS_P (op
)
3229 && get_base_address (op
)))
3232 op
= gimple_call_lhs (stmt
);
3233 /* Ignore #pragma omp declare simd functions
3234 if they don't have data references in the
3235 call stmt itself. */
3239 || (REFERENCE_CLASS_P (op
)
3240 && get_base_address (op
)))))
3245 LOOP_VINFO_DATAREFS (loop_vinfo
) = datarefs
;
3246 if (dump_enabled_p ())
3247 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3248 "not vectorized: loop contains function "
3249 "calls or data references that cannot "
3256 LOOP_VINFO_DATAREFS (loop_vinfo
) = datarefs
;
3260 gimple_stmt_iterator gsi
;
3262 bb
= BB_VINFO_BB (bb_vinfo
);
3263 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3265 gimple stmt
= gsi_stmt (gsi
);
3266 if (is_gimple_debug (stmt
))
3269 if (!find_data_references_in_stmt (NULL
, stmt
,
3270 &BB_VINFO_DATAREFS (bb_vinfo
)))
3272 /* Mark the rest of the basic-block as unvectorizable. */
3273 for (; !gsi_end_p (gsi
); gsi_next (&gsi
))
3275 stmt
= gsi_stmt (gsi
);
3276 STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt
)) = false;
3282 datarefs
= BB_VINFO_DATAREFS (bb_vinfo
);
3285 /* Go through the data-refs, check that the analysis succeeded. Update
3286 pointer from stmt_vec_info struct to DR and vectype. */
3288 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
3291 stmt_vec_info stmt_info
;
3292 tree base
, offset
, init
;
3293 bool gather
= false;
3294 bool simd_lane_access
= false;
3298 if (!dr
|| !DR_REF (dr
))
3300 if (dump_enabled_p ())
3301 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3302 "not vectorized: unhandled data-ref\n");
3306 stmt
= DR_STMT (dr
);
3307 stmt_info
= vinfo_for_stmt (stmt
);
3309 /* Discard clobbers from the dataref vector. We will remove
3310 clobber stmts during vectorization. */
3311 if (gimple_clobber_p (stmt
))
3314 if (i
== datarefs
.length () - 1)
3319 datarefs
.ordered_remove (i
);
3324 /* Check that analysis of the data-ref succeeded. */
3325 if (!DR_BASE_ADDRESS (dr
) || !DR_OFFSET (dr
) || !DR_INIT (dr
)
3330 && !TREE_THIS_VOLATILE (DR_REF (dr
))
3331 && targetm
.vectorize
.builtin_gather
!= NULL
;
3332 bool maybe_simd_lane_access
3333 = loop_vinfo
&& loop
->simduid
;
3335 /* If target supports vector gather loads, or if this might be
3336 a SIMD lane access, see if they can't be used. */
3338 && (maybe_gather
|| maybe_simd_lane_access
)
3339 && !nested_in_vect_loop_p (loop
, stmt
))
3341 struct data_reference
*newdr
3342 = create_data_ref (NULL
, loop_containing_stmt (stmt
),
3343 DR_REF (dr
), stmt
, true);
3344 gcc_assert (newdr
!= NULL
&& DR_REF (newdr
));
3345 if (DR_BASE_ADDRESS (newdr
)
3346 && DR_OFFSET (newdr
)
3349 && integer_zerop (DR_STEP (newdr
)))
3351 if (maybe_simd_lane_access
)
3353 tree off
= DR_OFFSET (newdr
);
3355 if (TREE_CODE (DR_INIT (newdr
)) == INTEGER_CST
3356 && TREE_CODE (off
) == MULT_EXPR
3357 && tree_fits_uhwi_p (TREE_OPERAND (off
, 1)))
3359 tree step
= TREE_OPERAND (off
, 1);
3360 off
= TREE_OPERAND (off
, 0);
3362 if (CONVERT_EXPR_P (off
)
3363 && TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (off
,
3365 < TYPE_PRECISION (TREE_TYPE (off
)))
3366 off
= TREE_OPERAND (off
, 0);
3367 if (TREE_CODE (off
) == SSA_NAME
)
3369 gimple def
= SSA_NAME_DEF_STMT (off
);
3370 tree reft
= TREE_TYPE (DR_REF (newdr
));
3371 if (is_gimple_call (def
)
3372 && gimple_call_internal_p (def
)
3373 && (gimple_call_internal_fn (def
)
3374 == IFN_GOMP_SIMD_LANE
))
3376 tree arg
= gimple_call_arg (def
, 0);
3377 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
3378 arg
= SSA_NAME_VAR (arg
);
3379 if (arg
== loop
->simduid
3381 && tree_int_cst_equal
3382 (TYPE_SIZE_UNIT (reft
),
3385 DR_OFFSET (newdr
) = ssize_int (0);
3386 DR_STEP (newdr
) = step
;
3387 DR_ALIGNED_TO (newdr
)
3388 = size_int (BIGGEST_ALIGNMENT
);
3390 simd_lane_access
= true;
3396 if (!simd_lane_access
&& maybe_gather
)
3402 if (!gather
&& !simd_lane_access
)
3403 free_data_ref (newdr
);
3406 if (!gather
&& !simd_lane_access
)
3408 if (dump_enabled_p ())
3410 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3411 "not vectorized: data ref analysis "
3413 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3414 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3424 if (TREE_CODE (DR_BASE_ADDRESS (dr
)) == INTEGER_CST
)
3426 if (dump_enabled_p ())
3427 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3428 "not vectorized: base addr of dr is a "
3434 if (gather
|| simd_lane_access
)
3439 if (TREE_THIS_VOLATILE (DR_REF (dr
)))
3441 if (dump_enabled_p ())
3443 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3444 "not vectorized: volatile type ");
3445 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3446 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3455 if (stmt_can_throw_internal (stmt
))
3457 if (dump_enabled_p ())
3459 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3460 "not vectorized: statement can throw an "
3462 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3463 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3469 if (gather
|| simd_lane_access
)
3474 if (TREE_CODE (DR_REF (dr
)) == COMPONENT_REF
3475 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr
), 1)))
3477 if (dump_enabled_p ())
3479 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3480 "not vectorized: statement is bitfield "
3482 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3483 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3489 if (gather
|| simd_lane_access
)
3494 base
= unshare_expr (DR_BASE_ADDRESS (dr
));
3495 offset
= unshare_expr (DR_OFFSET (dr
));
3496 init
= unshare_expr (DR_INIT (dr
));
3498 if (is_gimple_call (stmt
)
3499 && (!gimple_call_internal_p (stmt
)
3500 || (gimple_call_internal_fn (stmt
) != IFN_MASK_LOAD
3501 && gimple_call_internal_fn (stmt
) != IFN_MASK_STORE
)))
3503 if (dump_enabled_p ())
3505 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3506 "not vectorized: dr in a call ");
3507 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3508 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3514 if (gather
|| simd_lane_access
)
3519 /* Update DR field in stmt_vec_info struct. */
3521 /* If the dataref is in an inner-loop of the loop that is considered for
3522 for vectorization, we also want to analyze the access relative to
3523 the outer-loop (DR contains information only relative to the
3524 inner-most enclosing loop). We do that by building a reference to the
3525 first location accessed by the inner-loop, and analyze it relative to
3527 if (loop
&& nested_in_vect_loop_p (loop
, stmt
))
3529 tree outer_step
, outer_base
, outer_init
;
3530 HOST_WIDE_INT pbitsize
, pbitpos
;
3532 enum machine_mode pmode
;
3533 int punsignedp
, pvolatilep
;
3534 affine_iv base_iv
, offset_iv
;
3537 /* Build a reference to the first location accessed by the
3538 inner-loop: *(BASE+INIT). (The first location is actually
3539 BASE+INIT+OFFSET, but we add OFFSET separately later). */
3540 tree inner_base
= build_fold_indirect_ref
3541 (fold_build_pointer_plus (base
, init
));
3543 if (dump_enabled_p ())
3545 dump_printf_loc (MSG_NOTE
, vect_location
,
3546 "analyze in outer-loop: ");
3547 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, inner_base
);
3548 dump_printf (MSG_NOTE
, "\n");
3551 outer_base
= get_inner_reference (inner_base
, &pbitsize
, &pbitpos
,
3552 &poffset
, &pmode
, &punsignedp
, &pvolatilep
, false);
3553 gcc_assert (outer_base
!= NULL_TREE
);
3555 if (pbitpos
% BITS_PER_UNIT
!= 0)
3557 if (dump_enabled_p ())
3558 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3559 "failed: bit offset alignment.\n");
3563 outer_base
= build_fold_addr_expr (outer_base
);
3564 if (!simple_iv (loop
, loop_containing_stmt (stmt
), outer_base
,
3567 if (dump_enabled_p ())
3568 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3569 "failed: evolution of base is not affine.\n");
3576 poffset
= fold_build2 (PLUS_EXPR
, TREE_TYPE (offset
), offset
,
3584 offset_iv
.base
= ssize_int (0);
3585 offset_iv
.step
= ssize_int (0);
3587 else if (!simple_iv (loop
, loop_containing_stmt (stmt
), poffset
,
3590 if (dump_enabled_p ())
3591 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3592 "evolution of offset is not affine.\n");
3596 outer_init
= ssize_int (pbitpos
/ BITS_PER_UNIT
);
3597 split_constant_offset (base_iv
.base
, &base_iv
.base
, &dinit
);
3598 outer_init
= size_binop (PLUS_EXPR
, outer_init
, dinit
);
3599 split_constant_offset (offset_iv
.base
, &offset_iv
.base
, &dinit
);
3600 outer_init
= size_binop (PLUS_EXPR
, outer_init
, dinit
);
3602 outer_step
= size_binop (PLUS_EXPR
,
3603 fold_convert (ssizetype
, base_iv
.step
),
3604 fold_convert (ssizetype
, offset_iv
.step
));
3606 STMT_VINFO_DR_STEP (stmt_info
) = outer_step
;
3607 /* FIXME: Use canonicalize_base_object_address (base_iv.base); */
3608 STMT_VINFO_DR_BASE_ADDRESS (stmt_info
) = base_iv
.base
;
3609 STMT_VINFO_DR_INIT (stmt_info
) = outer_init
;
3610 STMT_VINFO_DR_OFFSET (stmt_info
) =
3611 fold_convert (ssizetype
, offset_iv
.base
);
3612 STMT_VINFO_DR_ALIGNED_TO (stmt_info
) =
3613 size_int (highest_pow2_factor (offset_iv
.base
));
3615 if (dump_enabled_p ())
3617 dump_printf_loc (MSG_NOTE
, vect_location
,
3618 "\touter base_address: ");
3619 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
3620 STMT_VINFO_DR_BASE_ADDRESS (stmt_info
));
3621 dump_printf (MSG_NOTE
, "\n\touter offset from base address: ");
3622 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
3623 STMT_VINFO_DR_OFFSET (stmt_info
));
3624 dump_printf (MSG_NOTE
,
3625 "\n\touter constant offset from base address: ");
3626 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
3627 STMT_VINFO_DR_INIT (stmt_info
));
3628 dump_printf (MSG_NOTE
, "\n\touter step: ");
3629 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
3630 STMT_VINFO_DR_STEP (stmt_info
));
3631 dump_printf (MSG_NOTE
, "\n\touter aligned to: ");
3632 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
3633 STMT_VINFO_DR_ALIGNED_TO (stmt_info
));
3634 dump_printf (MSG_NOTE
, "\n");
3638 if (STMT_VINFO_DATA_REF (stmt_info
))
3640 if (dump_enabled_p ())
3642 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3643 "not vectorized: more than one data ref "
3645 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3646 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3652 if (gather
|| simd_lane_access
)
3657 STMT_VINFO_DATA_REF (stmt_info
) = dr
;
3658 if (simd_lane_access
)
3660 STMT_VINFO_SIMD_LANE_ACCESS_P (stmt_info
) = true;
3661 free_data_ref (datarefs
[i
]);
3665 /* Set vectype for STMT. */
3666 scalar_type
= TREE_TYPE (DR_REF (dr
));
3667 STMT_VINFO_VECTYPE (stmt_info
)
3668 = get_vectype_for_scalar_type (scalar_type
);
3669 if (!STMT_VINFO_VECTYPE (stmt_info
))
3671 if (dump_enabled_p ())
3673 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3674 "not vectorized: no vectype for stmt: ");
3675 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3676 dump_printf (MSG_MISSED_OPTIMIZATION
, " scalar_type: ");
3677 dump_generic_expr (MSG_MISSED_OPTIMIZATION
, TDF_DETAILS
,
3679 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3685 if (gather
|| simd_lane_access
)
3687 STMT_VINFO_DATA_REF (stmt_info
) = NULL
;
3695 if (dump_enabled_p ())
3697 dump_printf_loc (MSG_NOTE
, vect_location
,
3698 "got vectype for stmt: ");
3699 dump_gimple_stmt (MSG_NOTE
, TDF_SLIM
, stmt
, 0);
3700 dump_generic_expr (MSG_NOTE
, TDF_SLIM
,
3701 STMT_VINFO_VECTYPE (stmt_info
));
3702 dump_printf (MSG_NOTE
, "\n");
3706 /* Adjust the minimal vectorization factor according to the
3708 vf
= TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info
));
3716 gather
= 0 != vect_check_gather (stmt
, loop_vinfo
, NULL
, &off
, NULL
);
3718 && get_vectype_for_scalar_type (TREE_TYPE (off
)) == NULL_TREE
)
3722 STMT_VINFO_DATA_REF (stmt_info
) = NULL
;
3724 if (dump_enabled_p ())
3726 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3727 "not vectorized: not suitable for gather "
3729 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3730 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3736 STMT_VINFO_GATHER_P (stmt_info
) = true;
3739 && TREE_CODE (DR_STEP (dr
)) != INTEGER_CST
)
3741 if (nested_in_vect_loop_p (loop
, stmt
)
3742 || !DR_IS_READ (dr
))
3744 if (dump_enabled_p ())
3746 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
3747 "not vectorized: not suitable for strided "
3749 dump_gimple_stmt (MSG_MISSED_OPTIMIZATION
, TDF_SLIM
, stmt
, 0);
3750 dump_printf (MSG_MISSED_OPTIMIZATION
, "\n");
3754 STMT_VINFO_STRIDE_LOAD_P (stmt_info
) = true;
3758 /* If we stopped analysis at the first dataref we could not analyze
3759 when trying to vectorize a basic-block mark the rest of the datarefs
3760 as not vectorizable and truncate the vector of datarefs. That
3761 avoids spending useless time in analyzing their dependence. */
3762 if (i
!= datarefs
.length ())
3764 gcc_assert (bb_vinfo
!= NULL
);
3765 for (unsigned j
= i
; j
< datarefs
.length (); ++j
)
3767 data_reference_p dr
= datarefs
[j
];
3768 STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr
))) = false;
3771 datarefs
.truncate (i
);
3778 /* Function vect_get_new_vect_var.
3780 Returns a name for a new variable. The current naming scheme appends the
3781 prefix "vect_" or "vect_p" (depending on the value of VAR_KIND) to
3782 the name of vectorizer generated variables, and appends that to NAME if
3786 vect_get_new_vect_var (tree type
, enum vect_var_kind var_kind
, const char *name
)
3793 case vect_simple_var
:
3796 case vect_scalar_var
:
3799 case vect_pointer_var
:
3808 char* tmp
= concat (prefix
, "_", name
, NULL
);
3809 new_vect_var
= create_tmp_reg (type
, tmp
);
3813 new_vect_var
= create_tmp_reg (type
, prefix
);
3815 return new_vect_var
;
3819 /* Function vect_create_addr_base_for_vector_ref.
3821 Create an expression that computes the address of the first memory location
3822 that will be accessed for a data reference.
3825 STMT: The statement containing the data reference.
3826 NEW_STMT_LIST: Must be initialized to NULL_TREE or a statement list.
3827 OFFSET: Optional. If supplied, it is be added to the initial address.
3828 LOOP: Specify relative to which loop-nest should the address be computed.
3829 For example, when the dataref is in an inner-loop nested in an
3830 outer-loop that is now being vectorized, LOOP can be either the
3831 outer-loop, or the inner-loop. The first memory location accessed
3832 by the following dataref ('in' points to short):
3839 if LOOP=i_loop: &in (relative to i_loop)
3840 if LOOP=j_loop: &in+i*2B (relative to j_loop)
3843 1. Return an SSA_NAME whose value is the address of the memory location of
3844 the first vector of the data reference.
3845 2. If new_stmt_list is not NULL_TREE after return then the caller must insert
3846 these statement(s) which define the returned SSA_NAME.
3848 FORNOW: We are only handling array accesses with step 1. */
3851 vect_create_addr_base_for_vector_ref (gimple stmt
,
3852 gimple_seq
*new_stmt_list
,
3856 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3857 struct data_reference
*dr
= STMT_VINFO_DATA_REF (stmt_info
);
3859 const char *base_name
;
3862 gimple_seq seq
= NULL
;
3866 tree step
= TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr
)));
3867 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3869 if (loop_vinfo
&& loop
&& loop
!= (gimple_bb (stmt
))->loop_father
)
3871 struct loop
*outer_loop
= LOOP_VINFO_LOOP (loop_vinfo
);
3873 gcc_assert (nested_in_vect_loop_p (outer_loop
, stmt
));
3875 data_ref_base
= unshare_expr (STMT_VINFO_DR_BASE_ADDRESS (stmt_info
));
3876 base_offset
= unshare_expr (STMT_VINFO_DR_OFFSET (stmt_info
));
3877 init
= unshare_expr (STMT_VINFO_DR_INIT (stmt_info
));
3881 data_ref_base
= unshare_expr (DR_BASE_ADDRESS (dr
));
3882 base_offset
= unshare_expr (DR_OFFSET (dr
));
3883 init
= unshare_expr (DR_INIT (dr
));
3887 base_name
= get_name (data_ref_base
);
3890 base_offset
= ssize_int (0);
3891 init
= ssize_int (0);
3892 base_name
= get_name (DR_REF (dr
));
3895 /* Create base_offset */
3896 base_offset
= size_binop (PLUS_EXPR
,
3897 fold_convert (sizetype
, base_offset
),
3898 fold_convert (sizetype
, init
));
3902 offset
= fold_build2 (MULT_EXPR
, sizetype
,
3903 fold_convert (sizetype
, offset
), step
);
3904 base_offset
= fold_build2 (PLUS_EXPR
, sizetype
,
3905 base_offset
, offset
);
3908 /* base + base_offset */
3910 addr_base
= fold_build_pointer_plus (data_ref_base
, base_offset
);
3913 addr_base
= build1 (ADDR_EXPR
,
3914 build_pointer_type (TREE_TYPE (DR_REF (dr
))),
3915 unshare_expr (DR_REF (dr
)));
3918 vect_ptr_type
= build_pointer_type (STMT_VINFO_VECTYPE (stmt_info
));
3919 addr_base
= fold_convert (vect_ptr_type
, addr_base
);
3920 dest
= vect_get_new_vect_var (vect_ptr_type
, vect_pointer_var
, base_name
);
3921 addr_base
= force_gimple_operand (addr_base
, &seq
, false, dest
);
3922 gimple_seq_add_seq (new_stmt_list
, seq
);
3924 if (DR_PTR_INFO (dr
)
3925 && TREE_CODE (addr_base
) == SSA_NAME
)
3927 duplicate_ssa_name_ptr_info (addr_base
, DR_PTR_INFO (dr
));
3929 mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (addr_base
));
3932 if (dump_enabled_p ())
3934 dump_printf_loc (MSG_NOTE
, vect_location
, "created ");
3935 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, addr_base
);
3936 dump_printf (MSG_NOTE
, "\n");
3943 /* Function vect_create_data_ref_ptr.
3945 Create a new pointer-to-AGGR_TYPE variable (ap), that points to the first
3946 location accessed in the loop by STMT, along with the def-use update
3947 chain to appropriately advance the pointer through the loop iterations.
3948 Also set aliasing information for the pointer. This pointer is used by
3949 the callers to this function to create a memory reference expression for
3950 vector load/store access.
3953 1. STMT: a stmt that references memory. Expected to be of the form
3954 GIMPLE_ASSIGN <name, data-ref> or
3955 GIMPLE_ASSIGN <data-ref, name>.
3956 2. AGGR_TYPE: the type of the reference, which should be either a vector
3958 3. AT_LOOP: the loop where the vector memref is to be created.
3959 4. OFFSET (optional): an offset to be added to the initial address accessed
3960 by the data-ref in STMT.
3961 5. BSI: location where the new stmts are to be placed if there is no loop
3962 6. ONLY_INIT: indicate if ap is to be updated in the loop, or remain
3963 pointing to the initial address.
3966 1. Declare a new ptr to vector_type, and have it point to the base of the
3967 data reference (initial addressed accessed by the data reference).
3968 For example, for vector of type V8HI, the following code is generated:
3971 ap = (v8hi *)initial_address;
3973 if OFFSET is not supplied:
3974 initial_address = &a[init];
3975 if OFFSET is supplied:
3976 initial_address = &a[init + OFFSET];
3978 Return the initial_address in INITIAL_ADDRESS.
3980 2. If ONLY_INIT is true, just return the initial pointer. Otherwise, also
3981 update the pointer in each iteration of the loop.
3983 Return the increment stmt that updates the pointer in PTR_INCR.
3985 3. Set INV_P to true if the access pattern of the data reference in the
3986 vectorized loop is invariant. Set it to false otherwise.
3988 4. Return the pointer. */
3991 vect_create_data_ref_ptr (gimple stmt
, tree aggr_type
, struct loop
*at_loop
,
3992 tree offset
, tree
*initial_address
,
3993 gimple_stmt_iterator
*gsi
, gimple
*ptr_incr
,
3994 bool only_init
, bool *inv_p
)
3996 const char *base_name
;
3997 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
3998 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
3999 struct loop
*loop
= NULL
;
4000 bool nested_in_vect_loop
= false;
4001 struct loop
*containing_loop
= NULL
;
4006 gimple_seq new_stmt_list
= NULL
;
4010 struct data_reference
*dr
= STMT_VINFO_DATA_REF (stmt_info
);
4012 gimple_stmt_iterator incr_gsi
;
4014 tree indx_before_incr
, indx_after_incr
;
4017 bb_vec_info bb_vinfo
= STMT_VINFO_BB_VINFO (stmt_info
);
4019 gcc_assert (TREE_CODE (aggr_type
) == ARRAY_TYPE
4020 || TREE_CODE (aggr_type
) == VECTOR_TYPE
);
4024 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4025 nested_in_vect_loop
= nested_in_vect_loop_p (loop
, stmt
);
4026 containing_loop
= (gimple_bb (stmt
))->loop_father
;
4027 pe
= loop_preheader_edge (loop
);
4031 gcc_assert (bb_vinfo
);
4036 /* Check the step (evolution) of the load in LOOP, and record
4037 whether it's invariant. */
4038 if (nested_in_vect_loop
)
4039 step
= STMT_VINFO_DR_STEP (stmt_info
);
4041 step
= DR_STEP (STMT_VINFO_DATA_REF (stmt_info
));
4043 if (integer_zerop (step
))
4048 /* Create an expression for the first address accessed by this load
4050 base_name
= get_name (DR_BASE_ADDRESS (dr
));
4052 if (dump_enabled_p ())
4054 tree dr_base_type
= TREE_TYPE (DR_BASE_OBJECT (dr
));
4055 dump_printf_loc (MSG_NOTE
, vect_location
,
4056 "create %s-pointer variable to type: ",
4057 get_tree_code_name (TREE_CODE (aggr_type
)));
4058 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, aggr_type
);
4059 if (TREE_CODE (dr_base_type
) == ARRAY_TYPE
)
4060 dump_printf (MSG_NOTE
, " vectorizing an array ref: ");
4061 else if (TREE_CODE (dr_base_type
) == VECTOR_TYPE
)
4062 dump_printf (MSG_NOTE
, " vectorizing a vector ref: ");
4063 else if (TREE_CODE (dr_base_type
) == RECORD_TYPE
)
4064 dump_printf (MSG_NOTE
, " vectorizing a record based array ref: ");
4066 dump_printf (MSG_NOTE
, " vectorizing a pointer ref: ");
4067 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, DR_BASE_OBJECT (dr
));
4068 dump_printf (MSG_NOTE
, "\n");
4071 /* (1) Create the new aggregate-pointer variable.
4072 Vector and array types inherit the alias set of their component
4073 type by default so we need to use a ref-all pointer if the data
4074 reference does not conflict with the created aggregated data
4075 reference because it is not addressable. */
4076 bool need_ref_all
= false;
4077 if (!alias_sets_conflict_p (get_alias_set (aggr_type
),
4078 get_alias_set (DR_REF (dr
))))
4079 need_ref_all
= true;
4080 /* Likewise for any of the data references in the stmt group. */
4081 else if (STMT_VINFO_GROUP_SIZE (stmt_info
) > 1)
4083 gimple orig_stmt
= STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info
);
4086 stmt_vec_info sinfo
= vinfo_for_stmt (orig_stmt
);
4087 struct data_reference
*sdr
= STMT_VINFO_DATA_REF (sinfo
);
4088 if (!alias_sets_conflict_p (get_alias_set (aggr_type
),
4089 get_alias_set (DR_REF (sdr
))))
4091 need_ref_all
= true;
4094 orig_stmt
= STMT_VINFO_GROUP_NEXT_ELEMENT (sinfo
);
4098 aggr_ptr_type
= build_pointer_type_for_mode (aggr_type
, ptr_mode
,
4100 aggr_ptr
= vect_get_new_vect_var (aggr_ptr_type
, vect_pointer_var
, base_name
);
4103 /* Note: If the dataref is in an inner-loop nested in LOOP, and we are
4104 vectorizing LOOP (i.e., outer-loop vectorization), we need to create two
4105 def-use update cycles for the pointer: one relative to the outer-loop
4106 (LOOP), which is what steps (3) and (4) below do. The other is relative
4107 to the inner-loop (which is the inner-most loop containing the dataref),
4108 and this is done be step (5) below.
4110 When vectorizing inner-most loops, the vectorized loop (LOOP) is also the
4111 inner-most loop, and so steps (3),(4) work the same, and step (5) is
4112 redundant. Steps (3),(4) create the following:
4115 LOOP: vp1 = phi(vp0,vp2)
4121 If there is an inner-loop nested in loop, then step (5) will also be
4122 applied, and an additional update in the inner-loop will be created:
4125 LOOP: vp1 = phi(vp0,vp2)
4127 inner: vp3 = phi(vp1,vp4)
4128 vp4 = vp3 + inner_step
4134 /* (2) Calculate the initial address of the aggregate-pointer, and set
4135 the aggregate-pointer to point to it before the loop. */
4137 /* Create: (&(base[init_val+offset]) in the loop preheader. */
4139 new_temp
= vect_create_addr_base_for_vector_ref (stmt
, &new_stmt_list
,
4145 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, new_stmt_list
);
4146 gcc_assert (!new_bb
);
4149 gsi_insert_seq_before (gsi
, new_stmt_list
, GSI_SAME_STMT
);
4152 *initial_address
= new_temp
;
4154 /* Create: p = (aggr_type *) initial_base */
4155 if (TREE_CODE (new_temp
) != SSA_NAME
4156 || !useless_type_conversion_p (aggr_ptr_type
, TREE_TYPE (new_temp
)))
4158 vec_stmt
= gimple_build_assign (aggr_ptr
,
4159 fold_convert (aggr_ptr_type
, new_temp
));
4160 aggr_ptr_init
= make_ssa_name (aggr_ptr
, vec_stmt
);
4161 /* Copy the points-to information if it exists. */
4162 if (DR_PTR_INFO (dr
))
4163 duplicate_ssa_name_ptr_info (aggr_ptr_init
, DR_PTR_INFO (dr
));
4164 gimple_assign_set_lhs (vec_stmt
, aggr_ptr_init
);
4167 new_bb
= gsi_insert_on_edge_immediate (pe
, vec_stmt
);
4168 gcc_assert (!new_bb
);
4171 gsi_insert_before (gsi
, vec_stmt
, GSI_SAME_STMT
);
4174 aggr_ptr_init
= new_temp
;
4176 /* (3) Handle the updating of the aggregate-pointer inside the loop.
4177 This is needed when ONLY_INIT is false, and also when AT_LOOP is the
4178 inner-loop nested in LOOP (during outer-loop vectorization). */
4180 /* No update in loop is required. */
4181 if (only_init
&& (!loop_vinfo
|| at_loop
== loop
))
4182 aptr
= aggr_ptr_init
;
4185 /* The step of the aggregate pointer is the type size. */
4186 tree iv_step
= TYPE_SIZE_UNIT (aggr_type
);
4187 /* One exception to the above is when the scalar step of the load in
4188 LOOP is zero. In this case the step here is also zero. */
4190 iv_step
= size_zero_node
;
4191 else if (tree_int_cst_sgn (step
) == -1)
4192 iv_step
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (iv_step
), iv_step
);
4194 standard_iv_increment_position (loop
, &incr_gsi
, &insert_after
);
4196 create_iv (aggr_ptr_init
,
4197 fold_convert (aggr_ptr_type
, iv_step
),
4198 aggr_ptr
, loop
, &incr_gsi
, insert_after
,
4199 &indx_before_incr
, &indx_after_incr
);
4200 incr
= gsi_stmt (incr_gsi
);
4201 set_vinfo_for_stmt (incr
, new_stmt_vec_info (incr
, loop_vinfo
, NULL
));
4203 /* Copy the points-to information if it exists. */
4204 if (DR_PTR_INFO (dr
))
4206 duplicate_ssa_name_ptr_info (indx_before_incr
, DR_PTR_INFO (dr
));
4207 duplicate_ssa_name_ptr_info (indx_after_incr
, DR_PTR_INFO (dr
));
4212 aptr
= indx_before_incr
;
4215 if (!nested_in_vect_loop
|| only_init
)
4219 /* (4) Handle the updating of the aggregate-pointer inside the inner-loop
4220 nested in LOOP, if exists. */
4222 gcc_assert (nested_in_vect_loop
);
4225 standard_iv_increment_position (containing_loop
, &incr_gsi
,
4227 create_iv (aptr
, fold_convert (aggr_ptr_type
, DR_STEP (dr
)), aggr_ptr
,
4228 containing_loop
, &incr_gsi
, insert_after
, &indx_before_incr
,
4230 incr
= gsi_stmt (incr_gsi
);
4231 set_vinfo_for_stmt (incr
, new_stmt_vec_info (incr
, loop_vinfo
, NULL
));
4233 /* Copy the points-to information if it exists. */
4234 if (DR_PTR_INFO (dr
))
4236 duplicate_ssa_name_ptr_info (indx_before_incr
, DR_PTR_INFO (dr
));
4237 duplicate_ssa_name_ptr_info (indx_after_incr
, DR_PTR_INFO (dr
));
4242 return indx_before_incr
;
4249 /* Function bump_vector_ptr
4251 Increment a pointer (to a vector type) by vector-size. If requested,
4252 i.e. if PTR-INCR is given, then also connect the new increment stmt
4253 to the existing def-use update-chain of the pointer, by modifying
4254 the PTR_INCR as illustrated below:
4256 The pointer def-use update-chain before this function:
4257 DATAREF_PTR = phi (p_0, p_2)
4259 PTR_INCR: p_2 = DATAREF_PTR + step
4261 The pointer def-use update-chain after this function:
4262 DATAREF_PTR = phi (p_0, p_2)
4264 NEW_DATAREF_PTR = DATAREF_PTR + BUMP
4266 PTR_INCR: p_2 = NEW_DATAREF_PTR + step
4269 DATAREF_PTR - ssa_name of a pointer (to vector type) that is being updated
4271 PTR_INCR - optional. The stmt that updates the pointer in each iteration of
4272 the loop. The increment amount across iterations is expected
4274 BSI - location where the new update stmt is to be placed.
4275 STMT - the original scalar memory-access stmt that is being vectorized.
4276 BUMP - optional. The offset by which to bump the pointer. If not given,
4277 the offset is assumed to be vector_size.
4279 Output: Return NEW_DATAREF_PTR as illustrated above.
4284 bump_vector_ptr (tree dataref_ptr
, gimple ptr_incr
, gimple_stmt_iterator
*gsi
,
4285 gimple stmt
, tree bump
)
4287 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
4288 struct data_reference
*dr
= STMT_VINFO_DATA_REF (stmt_info
);
4289 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
4290 tree update
= TYPE_SIZE_UNIT (vectype
);
4293 use_operand_p use_p
;
4294 tree new_dataref_ptr
;
4299 new_dataref_ptr
= copy_ssa_name (dataref_ptr
, NULL
);
4300 incr_stmt
= gimple_build_assign_with_ops (POINTER_PLUS_EXPR
, new_dataref_ptr
,
4301 dataref_ptr
, update
);
4302 vect_finish_stmt_generation (stmt
, incr_stmt
, gsi
);
4304 /* Copy the points-to information if it exists. */
4305 if (DR_PTR_INFO (dr
))
4307 duplicate_ssa_name_ptr_info (new_dataref_ptr
, DR_PTR_INFO (dr
));
4308 mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (new_dataref_ptr
));
4312 return new_dataref_ptr
;
4314 /* Update the vector-pointer's cross-iteration increment. */
4315 FOR_EACH_SSA_USE_OPERAND (use_p
, ptr_incr
, iter
, SSA_OP_USE
)
4317 tree use
= USE_FROM_PTR (use_p
);
4319 if (use
== dataref_ptr
)
4320 SET_USE (use_p
, new_dataref_ptr
);
4322 gcc_assert (tree_int_cst_compare (use
, update
) == 0);
4325 return new_dataref_ptr
;
4329 /* Function vect_create_destination_var.
4331 Create a new temporary of type VECTYPE. */
4334 vect_create_destination_var (tree scalar_dest
, tree vectype
)
4340 enum vect_var_kind kind
;
4342 kind
= vectype
? vect_simple_var
: vect_scalar_var
;
4343 type
= vectype
? vectype
: TREE_TYPE (scalar_dest
);
4345 gcc_assert (TREE_CODE (scalar_dest
) == SSA_NAME
);
4347 name
= get_name (scalar_dest
);
4349 asprintf (&new_name
, "%s_%u", name
, SSA_NAME_VERSION (scalar_dest
));
4351 asprintf (&new_name
, "_%u", SSA_NAME_VERSION (scalar_dest
));
4352 vec_dest
= vect_get_new_vect_var (type
, kind
, new_name
);
4358 /* Function vect_grouped_store_supported.
4360 Returns TRUE if interleave high and interleave low permutations
4361 are supported, and FALSE otherwise. */
4364 vect_grouped_store_supported (tree vectype
, unsigned HOST_WIDE_INT count
)
4366 enum machine_mode mode
= TYPE_MODE (vectype
);
4368 /* vect_permute_store_chain requires the group size to be equal to 3 or
4369 be a power of two. */
4370 if (count
!= 3 && exact_log2 (count
) == -1)
4372 if (dump_enabled_p ())
4373 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4374 "the size of the group of accesses"
4375 " is not a power of 2 or not eqaul to 3\n");
4379 /* Check that the permutation is supported. */
4380 if (VECTOR_MODE_P (mode
))
4382 unsigned int i
, nelt
= GET_MODE_NUNITS (mode
);
4383 unsigned char *sel
= XALLOCAVEC (unsigned char, nelt
);
4387 unsigned int j0
= 0, j1
= 0, j2
= 0;
4390 for (j
= 0; j
< 3; j
++)
4392 int nelt0
= ((3 - j
) * nelt
) % 3;
4393 int nelt1
= ((3 - j
) * nelt
+ 1) % 3;
4394 int nelt2
= ((3 - j
) * nelt
+ 2) % 3;
4395 for (i
= 0; i
< nelt
; i
++)
4397 if (3 * i
+ nelt0
< nelt
)
4398 sel
[3 * i
+ nelt0
] = j0
++;
4399 if (3 * i
+ nelt1
< nelt
)
4400 sel
[3 * i
+ nelt1
] = nelt
+ j1
++;
4401 if (3 * i
+ nelt2
< nelt
)
4402 sel
[3 * i
+ nelt2
] = 0;
4404 if (!can_vec_perm_p (mode
, false, sel
))
4406 if (dump_enabled_p ())
4407 dump_printf (MSG_MISSED_OPTIMIZATION
,
4408 "permutaion op not supported by target.\n");
4412 for (i
= 0; i
< nelt
; i
++)
4414 if (3 * i
+ nelt0
< nelt
)
4415 sel
[3 * i
+ nelt0
] = 3 * i
+ nelt0
;
4416 if (3 * i
+ nelt1
< nelt
)
4417 sel
[3 * i
+ nelt1
] = 3 * i
+ nelt1
;
4418 if (3 * i
+ nelt2
< nelt
)
4419 sel
[3 * i
+ nelt2
] = nelt
+ j2
++;
4421 if (!can_vec_perm_p (mode
, false, sel
))
4423 if (dump_enabled_p ())
4424 dump_printf (MSG_MISSED_OPTIMIZATION
,
4425 "permutaion op not supported by target.\n");
4433 /* If length is not equal to 3 then only power of 2 is supported. */
4434 gcc_assert (exact_log2 (count
) != -1);
4436 for (i
= 0; i
< nelt
/ 2; i
++)
4439 sel
[i
* 2 + 1] = i
+ nelt
;
4441 if (can_vec_perm_p (mode
, false, sel
))
4443 for (i
= 0; i
< nelt
; i
++)
4445 if (can_vec_perm_p (mode
, false, sel
))
4451 if (dump_enabled_p ())
4452 dump_printf (MSG_MISSED_OPTIMIZATION
,
4453 "permutaion op not supported by target.\n");
4458 /* Return TRUE if vec_store_lanes is available for COUNT vectors of
4462 vect_store_lanes_supported (tree vectype
, unsigned HOST_WIDE_INT count
)
4464 return vect_lanes_optab_supported_p ("vec_store_lanes",
4465 vec_store_lanes_optab
,
4470 /* Function vect_permute_store_chain.
4472 Given a chain of interleaved stores in DR_CHAIN of LENGTH that must be
4473 a power of 2 or equal to 3, generate interleave_high/low stmts to reorder
4474 the data correctly for the stores. Return the final references for stores
4477 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
4478 The input is 4 vectors each containing 8 elements. We assign a number to
4479 each element, the input sequence is:
4481 1st vec: 0 1 2 3 4 5 6 7
4482 2nd vec: 8 9 10 11 12 13 14 15
4483 3rd vec: 16 17 18 19 20 21 22 23
4484 4th vec: 24 25 26 27 28 29 30 31
4486 The output sequence should be:
4488 1st vec: 0 8 16 24 1 9 17 25
4489 2nd vec: 2 10 18 26 3 11 19 27
4490 3rd vec: 4 12 20 28 5 13 21 30
4491 4th vec: 6 14 22 30 7 15 23 31
4493 i.e., we interleave the contents of the four vectors in their order.
4495 We use interleave_high/low instructions to create such output. The input of
4496 each interleave_high/low operation is two vectors:
4499 the even elements of the result vector are obtained left-to-right from the
4500 high/low elements of the first vector. The odd elements of the result are
4501 obtained left-to-right from the high/low elements of the second vector.
4502 The output of interleave_high will be: 0 4 1 5
4503 and of interleave_low: 2 6 3 7
4506 The permutation is done in log LENGTH stages. In each stage interleave_high
4507 and interleave_low stmts are created for each pair of vectors in DR_CHAIN,
4508 where the first argument is taken from the first half of DR_CHAIN and the
4509 second argument from it's second half.
4512 I1: interleave_high (1st vec, 3rd vec)
4513 I2: interleave_low (1st vec, 3rd vec)
4514 I3: interleave_high (2nd vec, 4th vec)
4515 I4: interleave_low (2nd vec, 4th vec)
4517 The output for the first stage is:
4519 I1: 0 16 1 17 2 18 3 19
4520 I2: 4 20 5 21 6 22 7 23
4521 I3: 8 24 9 25 10 26 11 27
4522 I4: 12 28 13 29 14 30 15 31
4524 The output of the second stage, i.e. the final result is:
4526 I1: 0 8 16 24 1 9 17 25
4527 I2: 2 10 18 26 3 11 19 27
4528 I3: 4 12 20 28 5 13 21 30
4529 I4: 6 14 22 30 7 15 23 31. */
4532 vect_permute_store_chain (vec
<tree
> dr_chain
,
4533 unsigned int length
,
4535 gimple_stmt_iterator
*gsi
,
4536 vec
<tree
> *result_chain
)
4538 tree vect1
, vect2
, high
, low
;
4540 tree vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
4541 tree perm_mask_low
, perm_mask_high
;
4543 tree perm3_mask_low
, perm3_mask_high
;
4544 unsigned int i
, n
, log_length
= exact_log2 (length
);
4545 unsigned int j
, nelt
= TYPE_VECTOR_SUBPARTS (vectype
);
4546 unsigned char *sel
= XALLOCAVEC (unsigned char, nelt
);
4548 result_chain
->quick_grow (length
);
4549 memcpy (result_chain
->address (), dr_chain
.address (),
4550 length
* sizeof (tree
));
4554 unsigned int j0
= 0, j1
= 0, j2
= 0;
4556 for (j
= 0; j
< 3; j
++)
4558 int nelt0
= ((3 - j
) * nelt
) % 3;
4559 int nelt1
= ((3 - j
) * nelt
+ 1) % 3;
4560 int nelt2
= ((3 - j
) * nelt
+ 2) % 3;
4562 for (i
= 0; i
< nelt
; i
++)
4564 if (3 * i
+ nelt0
< nelt
)
4565 sel
[3 * i
+ nelt0
] = j0
++;
4566 if (3 * i
+ nelt1
< nelt
)
4567 sel
[3 * i
+ nelt1
] = nelt
+ j1
++;
4568 if (3 * i
+ nelt2
< nelt
)
4569 sel
[3 * i
+ nelt2
] = 0;
4571 perm3_mask_low
= vect_gen_perm_mask (vectype
, sel
);
4572 gcc_assert (perm3_mask_low
!= NULL
);
4574 for (i
= 0; i
< nelt
; i
++)
4576 if (3 * i
+ nelt0
< nelt
)
4577 sel
[3 * i
+ nelt0
] = 3 * i
+ nelt0
;
4578 if (3 * i
+ nelt1
< nelt
)
4579 sel
[3 * i
+ nelt1
] = 3 * i
+ nelt1
;
4580 if (3 * i
+ nelt2
< nelt
)
4581 sel
[3 * i
+ nelt2
] = nelt
+ j2
++;
4583 perm3_mask_high
= vect_gen_perm_mask (vectype
, sel
);
4584 gcc_assert (perm3_mask_high
!= NULL
);
4586 vect1
= dr_chain
[0];
4587 vect2
= dr_chain
[1];
4589 /* Create interleaving stmt:
4590 low = VEC_PERM_EXPR <vect1, vect2,
4591 {j, nelt, *, j + 1, nelt + j + 1, *,
4592 j + 2, nelt + j + 2, *, ...}> */
4593 data_ref
= make_temp_ssa_name (vectype
, NULL
, "vect_shuffle3_low");
4594 perm_stmt
= gimple_build_assign_with_ops (VEC_PERM_EXPR
, data_ref
,
4597 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
4600 vect2
= dr_chain
[2];
4601 /* Create interleaving stmt:
4602 low = VEC_PERM_EXPR <vect1, vect2,
4603 {0, 1, nelt + j, 3, 4, nelt + j + 1,
4604 6, 7, nelt + j + 2, ...}> */
4605 data_ref
= make_temp_ssa_name (vectype
, NULL
, "vect_shuffle3_high");
4606 perm_stmt
= gimple_build_assign_with_ops (VEC_PERM_EXPR
, data_ref
,
4609 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
4610 (*result_chain
)[j
] = data_ref
;
4615 /* If length is not equal to 3 then only power of 2 is supported. */
4616 gcc_assert (exact_log2 (length
) != -1);
4618 for (i
= 0, n
= nelt
/ 2; i
< n
; i
++)
4621 sel
[i
* 2 + 1] = i
+ nelt
;
4623 perm_mask_high
= vect_gen_perm_mask (vectype
, sel
);
4624 gcc_assert (perm_mask_high
!= NULL
);
4626 for (i
= 0; i
< nelt
; i
++)
4628 perm_mask_low
= vect_gen_perm_mask (vectype
, sel
);
4629 gcc_assert (perm_mask_low
!= NULL
);
4631 for (i
= 0, n
= log_length
; i
< n
; i
++)
4633 for (j
= 0; j
< length
/2; j
++)
4635 vect1
= dr_chain
[j
];
4636 vect2
= dr_chain
[j
+length
/2];
4638 /* Create interleaving stmt:
4639 high = VEC_PERM_EXPR <vect1, vect2, {0, nelt, 1, nelt+1,
4641 high
= make_temp_ssa_name (vectype
, NULL
, "vect_inter_high");
4643 = gimple_build_assign_with_ops (VEC_PERM_EXPR
, high
,
4644 vect1
, vect2
, perm_mask_high
);
4645 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
4646 (*result_chain
)[2*j
] = high
;
4648 /* Create interleaving stmt:
4649 low = VEC_PERM_EXPR <vect1, vect2,
4650 {nelt/2, nelt*3/2, nelt/2+1, nelt*3/2+1,
4652 low
= make_temp_ssa_name (vectype
, NULL
, "vect_inter_low");
4654 = gimple_build_assign_with_ops (VEC_PERM_EXPR
, low
,
4655 vect1
, vect2
, perm_mask_low
);
4656 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
4657 (*result_chain
)[2*j
+1] = low
;
4659 memcpy (dr_chain
.address (), result_chain
->address (),
4660 length
* sizeof (tree
));
4665 /* Function vect_setup_realignment
4667 This function is called when vectorizing an unaligned load using
4668 the dr_explicit_realign[_optimized] scheme.
4669 This function generates the following code at the loop prolog:
4672 x msq_init = *(floor(p)); # prolog load
4673 realignment_token = call target_builtin;
4675 x msq = phi (msq_init, ---)
4677 The stmts marked with x are generated only for the case of
4678 dr_explicit_realign_optimized.
4680 The code above sets up a new (vector) pointer, pointing to the first
4681 location accessed by STMT, and a "floor-aligned" load using that pointer.
4682 It also generates code to compute the "realignment-token" (if the relevant
4683 target hook was defined), and creates a phi-node at the loop-header bb
4684 whose arguments are the result of the prolog-load (created by this
4685 function) and the result of a load that takes place in the loop (to be
4686 created by the caller to this function).
4688 For the case of dr_explicit_realign_optimized:
4689 The caller to this function uses the phi-result (msq) to create the
4690 realignment code inside the loop, and sets up the missing phi argument,
4693 msq = phi (msq_init, lsq)
4694 lsq = *(floor(p')); # load in loop
4695 result = realign_load (msq, lsq, realignment_token);
4697 For the case of dr_explicit_realign:
4699 msq = *(floor(p)); # load in loop
4701 lsq = *(floor(p')); # load in loop
4702 result = realign_load (msq, lsq, realignment_token);
4705 STMT - (scalar) load stmt to be vectorized. This load accesses
4706 a memory location that may be unaligned.
4707 BSI - place where new code is to be inserted.
4708 ALIGNMENT_SUPPORT_SCHEME - which of the two misalignment handling schemes
4712 REALIGNMENT_TOKEN - the result of a call to the builtin_mask_for_load
4713 target hook, if defined.
4714 Return value - the result of the loop-header phi node. */
4717 vect_setup_realignment (gimple stmt
, gimple_stmt_iterator
*gsi
,
4718 tree
*realignment_token
,
4719 enum dr_alignment_support alignment_support_scheme
,
4721 struct loop
**at_loop
)
4723 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
4724 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
4725 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
4726 struct data_reference
*dr
= STMT_VINFO_DATA_REF (stmt_info
);
4727 struct loop
*loop
= NULL
;
4729 tree scalar_dest
= gimple_assign_lhs (stmt
);
4736 tree msq_init
= NULL_TREE
;
4739 tree msq
= NULL_TREE
;
4740 gimple_seq stmts
= NULL
;
4742 bool compute_in_loop
= false;
4743 bool nested_in_vect_loop
= false;
4744 struct loop
*containing_loop
= (gimple_bb (stmt
))->loop_father
;
4745 struct loop
*loop_for_initial_load
= NULL
;
4749 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
4750 nested_in_vect_loop
= nested_in_vect_loop_p (loop
, stmt
);
4753 gcc_assert (alignment_support_scheme
== dr_explicit_realign
4754 || alignment_support_scheme
== dr_explicit_realign_optimized
);
4756 /* We need to generate three things:
4757 1. the misalignment computation
4758 2. the extra vector load (for the optimized realignment scheme).
4759 3. the phi node for the two vectors from which the realignment is
4760 done (for the optimized realignment scheme). */
4762 /* 1. Determine where to generate the misalignment computation.
4764 If INIT_ADDR is NULL_TREE, this indicates that the misalignment
4765 calculation will be generated by this function, outside the loop (in the
4766 preheader). Otherwise, INIT_ADDR had already been computed for us by the
4767 caller, inside the loop.
4769 Background: If the misalignment remains fixed throughout the iterations of
4770 the loop, then both realignment schemes are applicable, and also the
4771 misalignment computation can be done outside LOOP. This is because we are
4772 vectorizing LOOP, and so the memory accesses in LOOP advance in steps that
4773 are a multiple of VS (the Vector Size), and therefore the misalignment in
4774 different vectorized LOOP iterations is always the same.
4775 The problem arises only if the memory access is in an inner-loop nested
4776 inside LOOP, which is now being vectorized using outer-loop vectorization.
4777 This is the only case when the misalignment of the memory access may not
4778 remain fixed throughout the iterations of the inner-loop (as explained in
4779 detail in vect_supportable_dr_alignment). In this case, not only is the
4780 optimized realignment scheme not applicable, but also the misalignment
4781 computation (and generation of the realignment token that is passed to
4782 REALIGN_LOAD) have to be done inside the loop.
4784 In short, INIT_ADDR indicates whether we are in a COMPUTE_IN_LOOP mode
4785 or not, which in turn determines if the misalignment is computed inside
4786 the inner-loop, or outside LOOP. */
4788 if (init_addr
!= NULL_TREE
|| !loop_vinfo
)
4790 compute_in_loop
= true;
4791 gcc_assert (alignment_support_scheme
== dr_explicit_realign
);
4795 /* 2. Determine where to generate the extra vector load.
4797 For the optimized realignment scheme, instead of generating two vector
4798 loads in each iteration, we generate a single extra vector load in the
4799 preheader of the loop, and in each iteration reuse the result of the
4800 vector load from the previous iteration. In case the memory access is in
4801 an inner-loop nested inside LOOP, which is now being vectorized using
4802 outer-loop vectorization, we need to determine whether this initial vector
4803 load should be generated at the preheader of the inner-loop, or can be
4804 generated at the preheader of LOOP. If the memory access has no evolution
4805 in LOOP, it can be generated in the preheader of LOOP. Otherwise, it has
4806 to be generated inside LOOP (in the preheader of the inner-loop). */
4808 if (nested_in_vect_loop
)
4810 tree outerloop_step
= STMT_VINFO_DR_STEP (stmt_info
);
4811 bool invariant_in_outerloop
=
4812 (tree_int_cst_compare (outerloop_step
, size_zero_node
) == 0);
4813 loop_for_initial_load
= (invariant_in_outerloop
? loop
: loop
->inner
);
4816 loop_for_initial_load
= loop
;
4818 *at_loop
= loop_for_initial_load
;
4820 if (loop_for_initial_load
)
4821 pe
= loop_preheader_edge (loop_for_initial_load
);
4823 /* 3. For the case of the optimized realignment, create the first vector
4824 load at the loop preheader. */
4826 if (alignment_support_scheme
== dr_explicit_realign_optimized
)
4828 /* Create msq_init = *(floor(p1)) in the loop preheader */
4830 gcc_assert (!compute_in_loop
);
4831 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4832 ptr
= vect_create_data_ref_ptr (stmt
, vectype
, loop_for_initial_load
,
4833 NULL_TREE
, &init_addr
, NULL
, &inc
,
4835 new_temp
= copy_ssa_name (ptr
, NULL
);
4836 new_stmt
= gimple_build_assign_with_ops
4837 (BIT_AND_EXPR
, new_temp
, ptr
,
4838 build_int_cst (TREE_TYPE (ptr
),
4839 -(HOST_WIDE_INT
)TYPE_ALIGN_UNIT (vectype
)));
4840 new_bb
= gsi_insert_on_edge_immediate (pe
, new_stmt
);
4841 gcc_assert (!new_bb
);
4843 = build2 (MEM_REF
, TREE_TYPE (vec_dest
), new_temp
,
4844 build_int_cst (reference_alias_ptr_type (DR_REF (dr
)), 0));
4845 new_stmt
= gimple_build_assign (vec_dest
, data_ref
);
4846 new_temp
= make_ssa_name (vec_dest
, new_stmt
);
4847 gimple_assign_set_lhs (new_stmt
, new_temp
);
4850 new_bb
= gsi_insert_on_edge_immediate (pe
, new_stmt
);
4851 gcc_assert (!new_bb
);
4854 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
4856 msq_init
= gimple_assign_lhs (new_stmt
);
4859 /* 4. Create realignment token using a target builtin, if available.
4860 It is done either inside the containing loop, or before LOOP (as
4861 determined above). */
4863 if (targetm
.vectorize
.builtin_mask_for_load
)
4867 /* Compute INIT_ADDR - the initial addressed accessed by this memref. */
4870 /* Generate the INIT_ADDR computation outside LOOP. */
4871 init_addr
= vect_create_addr_base_for_vector_ref (stmt
, &stmts
,
4875 pe
= loop_preheader_edge (loop
);
4876 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
4877 gcc_assert (!new_bb
);
4880 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
4883 builtin_decl
= targetm
.vectorize
.builtin_mask_for_load ();
4884 new_stmt
= gimple_build_call (builtin_decl
, 1, init_addr
);
4886 vect_create_destination_var (scalar_dest
,
4887 gimple_call_return_type (new_stmt
));
4888 new_temp
= make_ssa_name (vec_dest
, new_stmt
);
4889 gimple_call_set_lhs (new_stmt
, new_temp
);
4891 if (compute_in_loop
)
4892 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
4895 /* Generate the misalignment computation outside LOOP. */
4896 pe
= loop_preheader_edge (loop
);
4897 new_bb
= gsi_insert_on_edge_immediate (pe
, new_stmt
);
4898 gcc_assert (!new_bb
);
4901 *realignment_token
= gimple_call_lhs (new_stmt
);
4903 /* The result of the CALL_EXPR to this builtin is determined from
4904 the value of the parameter and no global variables are touched
4905 which makes the builtin a "const" function. Requiring the
4906 builtin to have the "const" attribute makes it unnecessary
4907 to call mark_call_clobbered. */
4908 gcc_assert (TREE_READONLY (builtin_decl
));
4911 if (alignment_support_scheme
== dr_explicit_realign
)
4914 gcc_assert (!compute_in_loop
);
4915 gcc_assert (alignment_support_scheme
== dr_explicit_realign_optimized
);
4918 /* 5. Create msq = phi <msq_init, lsq> in loop */
4920 pe
= loop_preheader_edge (containing_loop
);
4921 vec_dest
= vect_create_destination_var (scalar_dest
, vectype
);
4922 msq
= make_ssa_name (vec_dest
, NULL
);
4923 phi_stmt
= create_phi_node (msq
, containing_loop
->header
);
4924 add_phi_arg (phi_stmt
, msq_init
, pe
, UNKNOWN_LOCATION
);
4930 /* Function vect_grouped_load_supported.
4932 Returns TRUE if even and odd permutations are supported,
4933 and FALSE otherwise. */
4936 vect_grouped_load_supported (tree vectype
, unsigned HOST_WIDE_INT count
)
4938 enum machine_mode mode
= TYPE_MODE (vectype
);
4940 /* vect_permute_load_chain requires the group size to be equal to 3 or
4941 be a power of two. */
4942 if (count
!= 3 && exact_log2 (count
) == -1)
4944 if (dump_enabled_p ())
4945 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4946 "the size of the group of accesses"
4947 " is not a power of 2 or not equal to 3\n");
4951 /* Check that the permutation is supported. */
4952 if (VECTOR_MODE_P (mode
))
4954 unsigned int i
, j
, nelt
= GET_MODE_NUNITS (mode
);
4955 unsigned char *sel
= XALLOCAVEC (unsigned char, nelt
);
4960 for (k
= 0; k
< 3; k
++)
4962 for (i
= 0; i
< nelt
; i
++)
4963 if (3 * i
+ k
< 2 * nelt
)
4967 if (!can_vec_perm_p (mode
, false, sel
))
4969 if (dump_enabled_p ())
4970 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4971 "shuffle of 3 loads is not supported by"
4975 for (i
= 0, j
= 0; i
< nelt
; i
++)
4976 if (3 * i
+ k
< 2 * nelt
)
4979 sel
[i
] = nelt
+ ((nelt
+ k
) % 3) + 3 * (j
++);
4980 if (!can_vec_perm_p (mode
, false, sel
))
4982 if (dump_enabled_p ())
4983 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
4984 "shuffle of 3 loads is not supported by"
4993 /* If length is not equal to 3 then only power of 2 is supported. */
4994 gcc_assert (exact_log2 (count
) != -1);
4995 for (i
= 0; i
< nelt
; i
++)
4997 if (can_vec_perm_p (mode
, false, sel
))
4999 for (i
= 0; i
< nelt
; i
++)
5001 if (can_vec_perm_p (mode
, false, sel
))
5007 if (dump_enabled_p ())
5008 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, vect_location
,
5009 "extract even/odd not supported by target\n");
5013 /* Return TRUE if vec_load_lanes is available for COUNT vectors of
5017 vect_load_lanes_supported (tree vectype
, unsigned HOST_WIDE_INT count
)
5019 return vect_lanes_optab_supported_p ("vec_load_lanes",
5020 vec_load_lanes_optab
,
5024 /* Function vect_permute_load_chain.
5026 Given a chain of interleaved loads in DR_CHAIN of LENGTH that must be
5027 a power of 2 or equal to 3, generate extract_even/odd stmts to reorder
5028 the input data correctly. Return the final references for loads in
5031 E.g., LENGTH is 4 and the scalar type is short, i.e., VF is 8.
5032 The input is 4 vectors each containing 8 elements. We assign a number to each
5033 element, the input sequence is:
5035 1st vec: 0 1 2 3 4 5 6 7
5036 2nd vec: 8 9 10 11 12 13 14 15
5037 3rd vec: 16 17 18 19 20 21 22 23
5038 4th vec: 24 25 26 27 28 29 30 31
5040 The output sequence should be:
5042 1st vec: 0 4 8 12 16 20 24 28
5043 2nd vec: 1 5 9 13 17 21 25 29
5044 3rd vec: 2 6 10 14 18 22 26 30
5045 4th vec: 3 7 11 15 19 23 27 31
5047 i.e., the first output vector should contain the first elements of each
5048 interleaving group, etc.
5050 We use extract_even/odd instructions to create such output. The input of
5051 each extract_even/odd operation is two vectors
5055 and the output is the vector of extracted even/odd elements. The output of
5056 extract_even will be: 0 2 4 6
5057 and of extract_odd: 1 3 5 7
5060 The permutation is done in log LENGTH stages. In each stage extract_even
5061 and extract_odd stmts are created for each pair of vectors in DR_CHAIN in
5062 their order. In our example,
5064 E1: extract_even (1st vec, 2nd vec)
5065 E2: extract_odd (1st vec, 2nd vec)
5066 E3: extract_even (3rd vec, 4th vec)
5067 E4: extract_odd (3rd vec, 4th vec)
5069 The output for the first stage will be:
5071 E1: 0 2 4 6 8 10 12 14
5072 E2: 1 3 5 7 9 11 13 15
5073 E3: 16 18 20 22 24 26 28 30
5074 E4: 17 19 21 23 25 27 29 31
5076 In order to proceed and create the correct sequence for the next stage (or
5077 for the correct output, if the second stage is the last one, as in our
5078 example), we first put the output of extract_even operation and then the
5079 output of extract_odd in RESULT_CHAIN (which is then copied to DR_CHAIN).
5080 The input for the second stage is:
5082 1st vec (E1): 0 2 4 6 8 10 12 14
5083 2nd vec (E3): 16 18 20 22 24 26 28 30
5084 3rd vec (E2): 1 3 5 7 9 11 13 15
5085 4th vec (E4): 17 19 21 23 25 27 29 31
5087 The output of the second stage:
5089 E1: 0 4 8 12 16 20 24 28
5090 E2: 2 6 10 14 18 22 26 30
5091 E3: 1 5 9 13 17 21 25 29
5092 E4: 3 7 11 15 19 23 27 31
5094 And RESULT_CHAIN after reordering:
5096 1st vec (E1): 0 4 8 12 16 20 24 28
5097 2nd vec (E3): 1 5 9 13 17 21 25 29
5098 3rd vec (E2): 2 6 10 14 18 22 26 30
5099 4th vec (E4): 3 7 11 15 19 23 27 31. */
5102 vect_permute_load_chain (vec
<tree
> dr_chain
,
5103 unsigned int length
,
5105 gimple_stmt_iterator
*gsi
,
5106 vec
<tree
> *result_chain
)
5108 tree data_ref
, first_vect
, second_vect
;
5109 tree perm_mask_even
, perm_mask_odd
;
5110 tree perm3_mask_low
, perm3_mask_high
;
5112 tree vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt
));
5113 unsigned int i
, j
, log_length
= exact_log2 (length
);
5114 unsigned nelt
= TYPE_VECTOR_SUBPARTS (vectype
);
5115 unsigned char *sel
= XALLOCAVEC (unsigned char, nelt
);
5117 result_chain
->quick_grow (length
);
5118 memcpy (result_chain
->address (), dr_chain
.address (),
5119 length
* sizeof (tree
));
5125 for (k
= 0; k
< 3; k
++)
5127 for (i
= 0; i
< nelt
; i
++)
5128 if (3 * i
+ k
< 2 * nelt
)
5132 perm3_mask_low
= vect_gen_perm_mask (vectype
, sel
);
5133 gcc_assert (perm3_mask_low
!= NULL
);
5135 for (i
= 0, j
= 0; i
< nelt
; i
++)
5136 if (3 * i
+ k
< 2 * nelt
)
5139 sel
[i
] = nelt
+ ((nelt
+ k
) % 3) + 3 * (j
++);
5141 perm3_mask_high
= vect_gen_perm_mask (vectype
, sel
);
5142 gcc_assert (perm3_mask_high
!= NULL
);
5144 first_vect
= dr_chain
[0];
5145 second_vect
= dr_chain
[1];
5147 /* Create interleaving stmt (low part of):
5148 low = VEC_PERM_EXPR <first_vect, second_vect2, {k, 3 + k, 6 + k,
5150 data_ref
= make_temp_ssa_name (vectype
, NULL
, "vect_suffle3_low");
5151 perm_stmt
= gimple_build_assign_with_ops (VEC_PERM_EXPR
, data_ref
,
5152 first_vect
, second_vect
,
5154 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
5156 /* Create interleaving stmt (high part of):
5157 high = VEC_PERM_EXPR <first_vect, second_vect2, {k, 3 + k, 6 + k,
5159 first_vect
= data_ref
;
5160 second_vect
= dr_chain
[2];
5161 data_ref
= make_temp_ssa_name (vectype
, NULL
, "vect_suffle3_high");
5162 perm_stmt
= gimple_build_assign_with_ops (VEC_PERM_EXPR
, data_ref
,
5163 first_vect
, second_vect
,
5165 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
5166 (*result_chain
)[k
] = data_ref
;
5171 /* If length is not equal to 3 then only power of 2 is supported. */
5172 gcc_assert (exact_log2 (length
) != -1);
5174 for (i
= 0; i
< nelt
; ++i
)
5176 perm_mask_even
= vect_gen_perm_mask (vectype
, sel
);
5177 gcc_assert (perm_mask_even
!= NULL
);
5179 for (i
= 0; i
< nelt
; ++i
)
5181 perm_mask_odd
= vect_gen_perm_mask (vectype
, sel
);
5182 gcc_assert (perm_mask_odd
!= NULL
);
5184 for (i
= 0; i
< log_length
; i
++)
5186 for (j
= 0; j
< length
; j
+= 2)
5188 first_vect
= dr_chain
[j
];
5189 second_vect
= dr_chain
[j
+1];
5191 /* data_ref = permute_even (first_data_ref, second_data_ref); */
5192 data_ref
= make_temp_ssa_name (vectype
, NULL
, "vect_perm_even");
5193 perm_stmt
= gimple_build_assign_with_ops (VEC_PERM_EXPR
, data_ref
,
5194 first_vect
, second_vect
,
5196 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
5197 (*result_chain
)[j
/2] = data_ref
;
5199 /* data_ref = permute_odd (first_data_ref, second_data_ref); */
5200 data_ref
= make_temp_ssa_name (vectype
, NULL
, "vect_perm_odd");
5201 perm_stmt
= gimple_build_assign_with_ops (VEC_PERM_EXPR
, data_ref
,
5202 first_vect
, second_vect
,
5204 vect_finish_stmt_generation (stmt
, perm_stmt
, gsi
);
5205 (*result_chain
)[j
/2+length
/2] = data_ref
;
5207 memcpy (dr_chain
.address (), result_chain
->address (),
5208 length
* sizeof (tree
));
5213 /* Function vect_transform_grouped_load.
5215 Given a chain of input interleaved data-refs (in DR_CHAIN), build statements
5216 to perform their permutation and ascribe the result vectorized statements to
5217 the scalar statements.
5221 vect_transform_grouped_load (gimple stmt
, vec
<tree
> dr_chain
, int size
,
5222 gimple_stmt_iterator
*gsi
)
5224 vec
<tree
> result_chain
= vNULL
;
5226 /* DR_CHAIN contains input data-refs that are a part of the interleaving.
5227 RESULT_CHAIN is the output of vect_permute_load_chain, it contains permuted
5228 vectors, that are ready for vector computation. */
5229 result_chain
.create (size
);
5230 vect_permute_load_chain (dr_chain
, size
, stmt
, gsi
, &result_chain
);
5231 vect_record_grouped_load_vectors (stmt
, result_chain
);
5232 result_chain
.release ();
5235 /* RESULT_CHAIN contains the output of a group of grouped loads that were
5236 generated as part of the vectorization of STMT. Assign the statement
5237 for each vector to the associated scalar statement. */
5240 vect_record_grouped_load_vectors (gimple stmt
, vec
<tree
> result_chain
)
5242 gimple first_stmt
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt
));
5243 gimple next_stmt
, new_stmt
;
5244 unsigned int i
, gap_count
;
5247 /* Put a permuted data-ref in the VECTORIZED_STMT field.
5248 Since we scan the chain starting from it's first node, their order
5249 corresponds the order of data-refs in RESULT_CHAIN. */
5250 next_stmt
= first_stmt
;
5252 FOR_EACH_VEC_ELT (result_chain
, i
, tmp_data_ref
)
5257 /* Skip the gaps. Loads created for the gaps will be removed by dead
5258 code elimination pass later. No need to check for the first stmt in
5259 the group, since it always exists.
5260 GROUP_GAP is the number of steps in elements from the previous
5261 access (if there is no gap GROUP_GAP is 1). We skip loads that
5262 correspond to the gaps. */
5263 if (next_stmt
!= first_stmt
5264 && gap_count
< GROUP_GAP (vinfo_for_stmt (next_stmt
)))
5272 new_stmt
= SSA_NAME_DEF_STMT (tmp_data_ref
);
5273 /* We assume that if VEC_STMT is not NULL, this is a case of multiple
5274 copies, and we put the new vector statement in the first available
5276 if (!STMT_VINFO_VEC_STMT (vinfo_for_stmt (next_stmt
)))
5277 STMT_VINFO_VEC_STMT (vinfo_for_stmt (next_stmt
)) = new_stmt
;
5280 if (!GROUP_SAME_DR_STMT (vinfo_for_stmt (next_stmt
)))
5283 STMT_VINFO_VEC_STMT (vinfo_for_stmt (next_stmt
));
5285 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (prev_stmt
));
5288 prev_stmt
= rel_stmt
;
5290 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (rel_stmt
));
5293 STMT_VINFO_RELATED_STMT (vinfo_for_stmt (prev_stmt
)) =
5298 next_stmt
= GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt
));
5300 /* If NEXT_STMT accesses the same DR as the previous statement,
5301 put the same TMP_DATA_REF as its vectorized statement; otherwise
5302 get the next data-ref from RESULT_CHAIN. */
5303 if (!next_stmt
|| !GROUP_SAME_DR_STMT (vinfo_for_stmt (next_stmt
)))
5309 /* Function vect_force_dr_alignment_p.
5311 Returns whether the alignment of a DECL can be forced to be aligned
5312 on ALIGNMENT bit boundary. */
5315 vect_can_force_dr_alignment_p (const_tree decl
, unsigned int alignment
)
5317 if (TREE_CODE (decl
) != VAR_DECL
)
5320 /* With -fno-toplevel-reorder we may have already output the constant. */
5321 if (TREE_ASM_WRITTEN (decl
))
5324 /* Constant pool entries may be shared and not properly merged by LTO. */
5325 if (DECL_IN_CONSTANT_POOL (decl
))
5328 if (TREE_PUBLIC (decl
) || DECL_EXTERNAL (decl
))
5332 /* We cannot change alignment of symbols that may bind to symbols
5333 in other translation unit that may contain a definition with lower
5335 if (!decl_binds_to_current_def_p (decl
))
5338 /* When compiling partition, be sure the symbol is not output by other
5340 snode
= symtab_get_node (decl
);
5342 && (snode
->in_other_partition
5343 || symtab_get_symbol_partitioning_class (snode
) == SYMBOL_DUPLICATE
))
5347 /* Do not override the alignment as specified by the ABI when the used
5348 attribute is set. */
5349 if (DECL_PRESERVE_P (decl
))
5352 /* Do not override explicit alignment set by the user when an explicit
5353 section name is also used. This is a common idiom used by many
5354 software projects. */
5355 if (TREE_STATIC (decl
)
5356 && DECL_SECTION_NAME (decl
) != NULL
5357 && !symtab_get_node (decl
)->implicit_section
)
5360 /* If symbol is an alias, we need to check that target is OK. */
5361 if (TREE_STATIC (decl
))
5363 tree target
= symtab_alias_ultimate_target (symtab_get_node (decl
))->decl
;
5366 if (DECL_PRESERVE_P (target
))
5372 if (TREE_STATIC (decl
))
5373 return (alignment
<= MAX_OFILE_ALIGNMENT
);
5375 return (alignment
<= MAX_STACK_ALIGNMENT
);
5379 /* Return whether the data reference DR is supported with respect to its
5381 If CHECK_ALIGNED_ACCESSES is TRUE, check if the access is supported even
5382 it is aligned, i.e., check if it is possible to vectorize it with different
5385 enum dr_alignment_support
5386 vect_supportable_dr_alignment (struct data_reference
*dr
,
5387 bool check_aligned_accesses
)
5389 gimple stmt
= DR_STMT (dr
);
5390 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
5391 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
5392 enum machine_mode mode
= TYPE_MODE (vectype
);
5393 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
5394 struct loop
*vect_loop
= NULL
;
5395 bool nested_in_vect_loop
= false;
5397 if (aligned_access_p (dr
) && !check_aligned_accesses
)
5400 /* For now assume all conditional loads/stores support unaligned
5401 access without any special code. */
5402 if (is_gimple_call (stmt
)
5403 && gimple_call_internal_p (stmt
)
5404 && (gimple_call_internal_fn (stmt
) == IFN_MASK_LOAD
5405 || gimple_call_internal_fn (stmt
) == IFN_MASK_STORE
))
5406 return dr_unaligned_supported
;
5410 vect_loop
= LOOP_VINFO_LOOP (loop_vinfo
);
5411 nested_in_vect_loop
= nested_in_vect_loop_p (vect_loop
, stmt
);
5414 /* Possibly unaligned access. */
5416 /* We can choose between using the implicit realignment scheme (generating
5417 a misaligned_move stmt) and the explicit realignment scheme (generating
5418 aligned loads with a REALIGN_LOAD). There are two variants to the
5419 explicit realignment scheme: optimized, and unoptimized.
5420 We can optimize the realignment only if the step between consecutive
5421 vector loads is equal to the vector size. Since the vector memory
5422 accesses advance in steps of VS (Vector Size) in the vectorized loop, it
5423 is guaranteed that the misalignment amount remains the same throughout the
5424 execution of the vectorized loop. Therefore, we can create the
5425 "realignment token" (the permutation mask that is passed to REALIGN_LOAD)
5426 at the loop preheader.
5428 However, in the case of outer-loop vectorization, when vectorizing a
5429 memory access in the inner-loop nested within the LOOP that is now being
5430 vectorized, while it is guaranteed that the misalignment of the
5431 vectorized memory access will remain the same in different outer-loop
5432 iterations, it is *not* guaranteed that is will remain the same throughout
5433 the execution of the inner-loop. This is because the inner-loop advances
5434 with the original scalar step (and not in steps of VS). If the inner-loop
5435 step happens to be a multiple of VS, then the misalignment remains fixed
5436 and we can use the optimized realignment scheme. For example:
5442 When vectorizing the i-loop in the above example, the step between
5443 consecutive vector loads is 1, and so the misalignment does not remain
5444 fixed across the execution of the inner-loop, and the realignment cannot
5445 be optimized (as illustrated in the following pseudo vectorized loop):
5447 for (i=0; i<N; i+=4)
5448 for (j=0; j<M; j++){
5449 vs += vp[i+j]; // misalignment of &vp[i+j] is {0,1,2,3,0,1,2,3,...}
5450 // when j is {0,1,2,3,4,5,6,7,...} respectively.
5451 // (assuming that we start from an aligned address).
5454 We therefore have to use the unoptimized realignment scheme:
5456 for (i=0; i<N; i+=4)
5457 for (j=k; j<M; j+=4)
5458 vs += vp[i+j]; // misalignment of &vp[i+j] is always k (assuming
5459 // that the misalignment of the initial address is
5462 The loop can then be vectorized as follows:
5464 for (k=0; k<4; k++){
5465 rt = get_realignment_token (&vp[k]);
5466 for (i=0; i<N; i+=4){
5468 for (j=k; j<M; j+=4){
5470 va = REALIGN_LOAD <v1,v2,rt>;
5477 if (DR_IS_READ (dr
))
5479 bool is_packed
= false;
5480 tree type
= (TREE_TYPE (DR_REF (dr
)));
5482 if (optab_handler (vec_realign_load_optab
, mode
) != CODE_FOR_nothing
5483 && (!targetm
.vectorize
.builtin_mask_for_load
5484 || targetm
.vectorize
.builtin_mask_for_load ()))
5486 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
5487 if ((nested_in_vect_loop
5488 && (TREE_INT_CST_LOW (DR_STEP (dr
))
5489 != GET_MODE_SIZE (TYPE_MODE (vectype
))))
5491 return dr_explicit_realign
;
5493 return dr_explicit_realign_optimized
;
5495 if (!known_alignment_for_access_p (dr
))
5496 is_packed
= not_size_aligned (DR_REF (dr
));
5498 if ((TYPE_USER_ALIGN (type
) && !is_packed
)
5499 || targetm
.vectorize
.
5500 support_vector_misalignment (mode
, type
,
5501 DR_MISALIGNMENT (dr
), is_packed
))
5502 /* Can't software pipeline the loads, but can at least do them. */
5503 return dr_unaligned_supported
;
5507 bool is_packed
= false;
5508 tree type
= (TREE_TYPE (DR_REF (dr
)));
5510 if (!known_alignment_for_access_p (dr
))
5511 is_packed
= not_size_aligned (DR_REF (dr
));
5513 if ((TYPE_USER_ALIGN (type
) && !is_packed
)
5514 || targetm
.vectorize
.
5515 support_vector_misalignment (mode
, type
,
5516 DR_MISALIGNMENT (dr
), is_packed
))
5517 return dr_unaligned_supported
;
5521 return dr_unaligned_unsupported
;