2 Copyright (C) 2003-2019 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #ifndef GCC_TREE_VECTORIZER_H
22 #define GCC_TREE_VECTORIZER_H
24 typedef class _stmt_vec_info
*stmt_vec_info
;
26 #include "tree-data-ref.h"
27 #include "tree-hash-traits.h"
30 /* Used for naming of new temporaries. */
38 /* Defines type of operation. */
45 /* Define type of available alignment support. */
46 enum dr_alignment_support
{
47 dr_unaligned_unsupported
,
48 dr_unaligned_supported
,
50 dr_explicit_realign_optimized
,
54 /* Define type of def-use cross-iteration cycle. */
56 vect_uninitialized_def
= 0,
57 vect_constant_def
= 1,
62 vect_double_reduction_def
,
67 /* Define type of reduction. */
68 enum vect_reduction_type
{
71 INTEGER_INDUC_COND_REDUCTION
,
74 /* Retain a scalar phi and use a FOLD_EXTRACT_LAST within the loop
77 for (int i = 0; i < VF; ++i)
78 res = cond[i] ? val[i] : res; */
79 EXTRACT_LAST_REDUCTION
,
81 /* Use a folding reduction within the loop to implement:
83 for (int i = 0; i < VF; ++i)
86 (with no reassocation). */
90 #define VECTORIZABLE_CYCLE_DEF(D) (((D) == vect_reduction_def) \
91 || ((D) == vect_double_reduction_def) \
92 || ((D) == vect_nested_cycle))
94 /* Structure to encapsulate information about a group of like
95 instructions to be presented to the target cost model. */
96 struct stmt_info_for_cost
{
98 enum vect_cost_for_stmt kind
;
99 enum vect_cost_model_location where
;
100 stmt_vec_info stmt_info
;
104 typedef vec
<stmt_info_for_cost
> stmt_vector_for_cost
;
106 /* Maps base addresses to an innermost_loop_behavior that gives the maximum
107 known alignment for that base. */
108 typedef hash_map
<tree_operand_hash
,
109 innermost_loop_behavior
*> vec_base_alignments
;
111 /************************************************************************
113 ************************************************************************/
114 typedef struct _slp_tree
*slp_tree
;
116 /* A computation tree of an SLP instance. Each node corresponds to a group of
117 stmts to be packed in a SIMD stmt. */
119 /* Nodes that contain def-stmts of this node statements operands. */
120 vec
<slp_tree
> children
;
121 /* A group of scalar stmts to be vectorized together. */
122 vec
<stmt_vec_info
> stmts
;
123 /* Load permutation relative to the stores, NULL if there is no
125 vec
<unsigned> load_permutation
;
126 /* Vectorized stmt/s. */
127 vec
<stmt_vec_info
> vec_stmts
;
128 /* Number of vector stmts that are created to replace the group of scalar
129 stmts. It is calculated during the transformation phase as the number of
130 scalar elements in one scalar iteration (GROUP_SIZE) multiplied by VF
131 divided by vector size. */
132 unsigned int vec_stmts_size
;
133 /* Reference count in the SLP graph. */
135 /* The maximum number of vector elements for the subtree rooted
137 poly_uint64 max_nunits
;
138 /* Whether the scalar computations use two different operators. */
140 /* The DEF type of this node. */
141 enum vect_def_type def_type
;
145 /* SLP instance is a sequence of stmts in a loop that can be packed into
147 typedef class _slp_instance
{
149 /* The root of SLP tree. */
152 /* Size of groups of scalar stmts that will be replaced by SIMD stmt/s. */
153 unsigned int group_size
;
155 /* The unrolling factor required to vectorized this SLP instance. */
156 poly_uint64 unrolling_factor
;
158 /* The group of nodes that contain loads of this SLP instance. */
161 /* The SLP node containing the reduction PHIs. */
166 /* Access Functions. */
167 #define SLP_INSTANCE_TREE(S) (S)->root
168 #define SLP_INSTANCE_GROUP_SIZE(S) (S)->group_size
169 #define SLP_INSTANCE_UNROLLING_FACTOR(S) (S)->unrolling_factor
170 #define SLP_INSTANCE_LOADS(S) (S)->loads
172 #define SLP_TREE_CHILDREN(S) (S)->children
173 #define SLP_TREE_SCALAR_STMTS(S) (S)->stmts
174 #define SLP_TREE_VEC_STMTS(S) (S)->vec_stmts
175 #define SLP_TREE_NUMBER_OF_VEC_STMTS(S) (S)->vec_stmts_size
176 #define SLP_TREE_LOAD_PERMUTATION(S) (S)->load_permutation
177 #define SLP_TREE_TWO_OPERATORS(S) (S)->two_operators
178 #define SLP_TREE_DEF_TYPE(S) (S)->def_type
180 /* Key for map that records association between
181 scalar conditions and corresponding loop mask, and
182 is populated by vect_record_loop_mask. */
184 struct scalar_cond_masked_key
186 scalar_cond_masked_key (tree t
, unsigned ncopies_
)
189 get_cond_ops_from_tree (t
);
192 void get_cond_ops_from_tree (tree
);
201 struct default_hash_traits
<scalar_cond_masked_key
>
203 typedef scalar_cond_masked_key compare_type
;
204 typedef scalar_cond_masked_key value_type
;
206 static inline hashval_t
211 inchash::add_expr (v
.op0
, h
, 0);
212 inchash::add_expr (v
.op1
, h
, 0);
213 h
.add_int (v
.ncopies
);
218 equal (value_type existing
, value_type candidate
)
220 return (existing
.ncopies
== candidate
.ncopies
221 && existing
.code
== candidate
.code
222 && operand_equal_p (existing
.op0
, candidate
.op0
, 0)
223 && operand_equal_p (existing
.op1
, candidate
.op1
, 0));
227 mark_empty (value_type
&v
)
233 is_empty (value_type v
)
235 return v
.ncopies
== 0;
238 static inline void mark_deleted (value_type
&) {}
240 static inline bool is_deleted (const value_type
&)
245 static inline void remove (value_type
&) {}
248 typedef hash_set
<scalar_cond_masked_key
> scalar_cond_masked_set_type
;
250 /* Describes two objects whose addresses must be unequal for the vectorized
252 typedef std::pair
<tree
, tree
> vec_object_pair
;
254 /* Records that vectorization is only possible if abs (EXPR) >= MIN_VALUE.
255 UNSIGNED_P is true if we can assume that abs (EXPR) == EXPR. */
256 class vec_lower_bound
{
258 vec_lower_bound () {}
259 vec_lower_bound (tree e
, bool u
, poly_uint64 m
)
260 : expr (e
), unsigned_p (u
), min_value (m
) {}
264 poly_uint64 min_value
;
267 /* Vectorizer state shared between different analyses like vector sizes
268 of the same CFG region. */
269 class vec_info_shared
{
274 void save_datarefs();
275 void check_datarefs();
277 /* All data references. Freed by free_data_refs, so not an auto_vec. */
278 vec
<data_reference_p
> datarefs
;
279 vec
<data_reference
> datarefs_copy
;
281 /* The loop nest in which the data dependences are computed. */
282 auto_vec
<loop_p
> loop_nest
;
284 /* All data dependences. Freed by free_dependence_relations, so not
289 /* Vectorizer state common between loop and basic-block vectorization. */
292 enum vec_kind
{ bb
, loop
};
294 vec_info (vec_kind
, void *, vec_info_shared
*);
297 stmt_vec_info
add_stmt (gimple
*);
298 stmt_vec_info
lookup_stmt (gimple
*);
299 stmt_vec_info
lookup_def (tree
);
300 stmt_vec_info
lookup_single_use (tree
);
301 class dr_vec_info
*lookup_dr (data_reference
*);
302 void move_dr (stmt_vec_info
, stmt_vec_info
);
303 void remove_stmt (stmt_vec_info
);
304 void replace_stmt (gimple_stmt_iterator
*, stmt_vec_info
, gimple
*);
306 /* The type of vectorization. */
309 /* Shared vectorizer state. */
310 vec_info_shared
*shared
;
312 /* The mapping of GIMPLE UID to stmt_vec_info. */
313 vec
<stmt_vec_info
> stmt_vec_infos
;
315 /* All SLP instances. */
316 auto_vec
<slp_instance
> slp_instances
;
318 /* Maps base addresses to an innermost_loop_behavior that gives the maximum
319 known alignment for that base. */
320 vec_base_alignments base_alignments
;
322 /* All interleaving chains of stores, represented by the first
323 stmt in the chain. */
324 auto_vec
<stmt_vec_info
> grouped_stores
;
326 /* Cost data used by the target cost model. */
327 void *target_cost_data
;
329 /* The vector size for this loop in bytes, or 0 if we haven't picked
331 poly_uint64 vector_size
;
334 stmt_vec_info
new_stmt_vec_info (gimple
*stmt
);
335 void set_vinfo_for_stmt (gimple
*, stmt_vec_info
);
336 void free_stmt_vec_infos ();
337 void free_stmt_vec_info (stmt_vec_info
);
340 class _loop_vec_info
;
346 is_a_helper
<_loop_vec_info
*>::test (vec_info
*i
)
348 return i
->kind
== vec_info::loop
;
354 is_a_helper
<_bb_vec_info
*>::test (vec_info
*i
)
356 return i
->kind
== vec_info::bb
;
360 /* In general, we can divide the vector statements in a vectorized loop
361 into related groups ("rgroups") and say that for each rgroup there is
362 some nS such that the rgroup operates on nS values from one scalar
363 iteration followed by nS values from the next. That is, if VF is the
364 vectorization factor of the loop, the rgroup operates on a sequence:
366 (1,1) (1,2) ... (1,nS) (2,1) ... (2,nS) ... (VF,1) ... (VF,nS)
368 where (i,j) represents a scalar value with index j in a scalar
369 iteration with index i.
371 [ We use the term "rgroup" to emphasise that this grouping isn't
372 necessarily the same as the grouping of statements used elsewhere.
373 For example, if we implement a group of scalar loads using gather
374 loads, we'll use a separate gather load for each scalar load, and
375 thus each gather load will belong to its own rgroup. ]
377 In general this sequence will occupy nV vectors concatenated
378 together. If these vectors have nL lanes each, the total number
379 of scalar values N is given by:
381 N = nS * VF = nV * nL
383 None of nS, VF, nV and nL are required to be a power of 2. nS and nV
384 are compile-time constants but VF and nL can be variable (if the target
385 supports variable-length vectors).
387 In classical vectorization, each iteration of the vector loop would
388 handle exactly VF iterations of the original scalar loop. However,
389 in a fully-masked loop, a particular iteration of the vector loop
390 might handle fewer than VF iterations of the scalar loop. The vector
391 lanes that correspond to iterations of the scalar loop are said to be
392 "active" and the other lanes are said to be "inactive".
394 In a fully-masked loop, many rgroups need to be masked to ensure that
395 they have no effect for the inactive lanes. Each such rgroup needs a
396 sequence of booleans in the same order as above, but with each (i,j)
397 replaced by a boolean that indicates whether iteration i is active.
398 This sequence occupies nV vector masks that again have nL lanes each.
399 Thus the mask sequence as a whole consists of VF independent booleans
400 that are each repeated nS times.
402 We make the simplifying assumption that if a sequence of nV masks is
403 suitable for one (nS,nL) pair, we can reuse it for (nS/2,nL/2) by
404 VIEW_CONVERTing it. This holds for all current targets that support
405 fully-masked loops. For example, suppose the scalar loop is:
409 for (int i = 0; i < n; ++i)
411 f[i * 2 + 0] += 1.0f;
412 f[i * 2 + 1] += 2.0f;
416 and suppose that vectors have 256 bits. The vectorized f accesses
417 will belong to one rgroup and the vectorized d access to another:
419 f rgroup: nS = 2, nV = 1, nL = 8
420 d rgroup: nS = 1, nV = 1, nL = 4
423 [ In this simple example the rgroups do correspond to the normal
424 SLP grouping scheme. ]
426 If only the first three lanes are active, the masks we need are:
428 f rgroup: 1 1 | 1 1 | 1 1 | 0 0
429 d rgroup: 1 | 1 | 1 | 0
431 Here we can use a mask calculated for f's rgroup for d's, but not
434 Thus for each value of nV, it is enough to provide nV masks, with the
435 mask being calculated based on the highest nL (or, equivalently, based
436 on the highest nS) required by any rgroup with that nV. We therefore
437 represent the entire collection of masks as a two-level table, with the
438 first level being indexed by nV - 1 (since nV == 0 doesn't exist) and
439 the second being indexed by the mask index 0 <= i < nV. */
441 /* The masks needed by rgroups with nV vectors, according to the
442 description above. */
443 struct rgroup_masks
{
444 /* The largest nS for all rgroups that use these masks. */
445 unsigned int max_nscalars_per_iter
;
447 /* The type of mask to use, based on the highest nS recorded above. */
450 /* A vector of nV masks, in iteration order. */
454 typedef auto_vec
<rgroup_masks
> vec_loop_masks
;
456 /*-----------------------------------------------------------------*/
457 /* Info on vectorized loops. */
458 /*-----------------------------------------------------------------*/
459 typedef class _loop_vec_info
: public vec_info
{
461 _loop_vec_info (class loop
*, vec_info_shared
*);
464 /* The loop to which this info struct refers to. */
467 /* The loop basic blocks. */
470 /* Number of latch executions. */
472 /* Number of iterations. */
474 /* Number of iterations of the original loop. */
475 tree num_iters_unchanged
;
476 /* Condition under which this loop is analyzed and versioned. */
477 tree num_iters_assumptions
;
479 /* Threshold of number of iterations below which vectorization will not be
480 performed. It is calculated from MIN_PROFITABLE_ITERS and
481 PARAM_MIN_VECT_LOOP_BOUND. */
484 /* When applying loop versioning, the vector form should only be used
485 if the number of scalar iterations is >= this value, on top of all
486 the other requirements. Ignored when loop versioning is not being
488 poly_uint64 versioning_threshold
;
490 /* Unrolling factor */
491 poly_uint64 vectorization_factor
;
493 /* Maximum runtime vectorization factor, or MAX_VECTORIZATION_FACTOR
494 if there is no particular limit. */
495 unsigned HOST_WIDE_INT max_vectorization_factor
;
497 /* The masks that a fully-masked loop should use to avoid operating
498 on inactive scalars. */
499 vec_loop_masks masks
;
501 /* Set of scalar conditions that have loop mask applied. */
502 scalar_cond_masked_set_type scalar_cond_masked_set
;
504 /* If we are using a loop mask to align memory addresses, this variable
505 contains the number of vector elements that we should skip in the
506 first iteration of the vector loop (i.e. the number of leading
507 elements that should be false in the first mask). */
508 tree mask_skip_niters
;
510 /* Type of the variables to use in the WHILE_ULT call for fully-masked
512 tree mask_compare_type
;
514 /* For #pragma omp simd if (x) loops the x expression. If constant 0,
515 the loop should not be vectorized, if constant non-zero, simd_if_cond
516 shouldn't be set and loop vectorized normally, if SSA_NAME, the loop
517 should be versioned on that condition, using scalar loop if the condition
518 is false and vectorized loop otherwise. */
521 /* Type of the IV to use in the WHILE_ULT call for fully-masked
525 /* Unknown DRs according to which loop was peeled. */
526 class dr_vec_info
*unaligned_dr
;
528 /* peeling_for_alignment indicates whether peeling for alignment will take
529 place, and what the peeling factor should be:
530 peeling_for_alignment = X means:
531 If X=0: Peeling for alignment will not be applied.
532 If X>0: Peel first X iterations.
533 If X=-1: Generate a runtime test to calculate the number of iterations
534 to be peeled, using the dataref recorded in the field
536 int peeling_for_alignment
;
538 /* The mask used to check the alignment of pointers or arrays. */
541 /* Data Dependence Relations defining address ranges that are candidates
542 for a run-time aliasing check. */
543 auto_vec
<ddr_p
> may_alias_ddrs
;
545 /* Data Dependence Relations defining address ranges together with segment
546 lengths from which the run-time aliasing check is built. */
547 auto_vec
<dr_with_seg_len_pair_t
> comp_alias_ddrs
;
549 /* Check that the addresses of each pair of objects is unequal. */
550 auto_vec
<vec_object_pair
> check_unequal_addrs
;
552 /* List of values that are required to be nonzero. This is used to check
553 whether things like "x[i * n] += 1;" are safe and eventually gets added
554 to the checks for lower bounds below. */
555 auto_vec
<tree
> check_nonzero
;
557 /* List of values that need to be checked for a minimum value. */
558 auto_vec
<vec_lower_bound
> lower_bounds
;
560 /* Statements in the loop that have data references that are candidates for a
561 runtime (loop versioning) misalignment check. */
562 auto_vec
<stmt_vec_info
> may_misalign_stmts
;
564 /* Reduction cycles detected in the loop. Used in loop-aware SLP. */
565 auto_vec
<stmt_vec_info
> reductions
;
567 /* All reduction chains in the loop, represented by the first
568 stmt in the chain. */
569 auto_vec
<stmt_vec_info
> reduction_chains
;
571 /* Cost vector for a single scalar iteration. */
572 auto_vec
<stmt_info_for_cost
> scalar_cost_vec
;
574 /* Map of IV base/step expressions to inserted name in the preheader. */
575 hash_map
<tree_operand_hash
, tree
> *ivexpr_map
;
577 /* Map of OpenMP "omp simd array" scan variables to corresponding
578 rhs of the store of the initializer. */
579 hash_map
<tree
, tree
> *scan_map
;
581 /* The unrolling factor needed to SLP the loop. In case of that pure SLP is
582 applied to the loop, i.e., no unrolling is needed, this is 1. */
583 poly_uint64 slp_unrolling_factor
;
585 /* Cost of a single scalar iteration. */
586 int single_scalar_iteration_cost
;
588 /* Is the loop vectorizable? */
591 /* Records whether we still have the option of using a fully-masked loop. */
592 bool can_fully_mask_p
;
594 /* True if have decided to use a fully-masked loop. */
597 /* When we have grouped data accesses with gaps, we may introduce invalid
598 memory accesses. We peel the last iteration of the loop to prevent
600 bool peeling_for_gaps
;
602 /* When the number of iterations is not a multiple of the vector size
603 we need to peel off iterations at the end to form an epilogue loop. */
604 bool peeling_for_niter
;
606 /* True if there are no loop carried data dependencies in the loop.
607 If loop->safelen <= 1, then this is always true, either the loop
608 didn't have any loop carried data dependencies, or the loop is being
609 vectorized guarded with some runtime alias checks, or couldn't
610 be vectorized at all, but then this field shouldn't be used.
611 For loop->safelen >= 2, the user has asserted that there are no
612 backward dependencies, but there still could be loop carried forward
613 dependencies in such loops. This flag will be false if normal
614 vectorizer data dependency analysis would fail or require versioning
615 for alias, but because of loop->safelen >= 2 it has been vectorized
616 even without versioning for alias. E.g. in:
618 for (int i = 0; i < m; i++)
620 (or #pragma simd or #pragma ivdep) we can vectorize this and it will
621 DTRT even for k > 0 && k < m, but without safelen we would not
622 vectorize this, so this field would be false. */
623 bool no_data_dependencies
;
625 /* Mark loops having masked stores. */
628 /* Queued scaling factor for the scalar loop. */
629 profile_probability scalar_loop_scaling
;
631 /* If if-conversion versioned this loop before conversion, this is the
632 loop version without if-conversion. */
633 class loop
*scalar_loop
;
635 /* For loops being epilogues of already vectorized loops
636 this points to the original vectorized loop. Otherwise NULL. */
637 _loop_vec_info
*orig_loop_info
;
641 /* Access Functions. */
642 #define LOOP_VINFO_LOOP(L) (L)->loop
643 #define LOOP_VINFO_BBS(L) (L)->bbs
644 #define LOOP_VINFO_NITERSM1(L) (L)->num_itersm1
645 #define LOOP_VINFO_NITERS(L) (L)->num_iters
646 /* Since LOOP_VINFO_NITERS and LOOP_VINFO_NITERSM1 can change after
647 prologue peeling retain total unchanged scalar loop iterations for
649 #define LOOP_VINFO_NITERS_UNCHANGED(L) (L)->num_iters_unchanged
650 #define LOOP_VINFO_NITERS_ASSUMPTIONS(L) (L)->num_iters_assumptions
651 #define LOOP_VINFO_COST_MODEL_THRESHOLD(L) (L)->th
652 #define LOOP_VINFO_VERSIONING_THRESHOLD(L) (L)->versioning_threshold
653 #define LOOP_VINFO_VECTORIZABLE_P(L) (L)->vectorizable
654 #define LOOP_VINFO_CAN_FULLY_MASK_P(L) (L)->can_fully_mask_p
655 #define LOOP_VINFO_FULLY_MASKED_P(L) (L)->fully_masked_p
656 #define LOOP_VINFO_VECT_FACTOR(L) (L)->vectorization_factor
657 #define LOOP_VINFO_MAX_VECT_FACTOR(L) (L)->max_vectorization_factor
658 #define LOOP_VINFO_MASKS(L) (L)->masks
659 #define LOOP_VINFO_MASK_SKIP_NITERS(L) (L)->mask_skip_niters
660 #define LOOP_VINFO_MASK_COMPARE_TYPE(L) (L)->mask_compare_type
661 #define LOOP_VINFO_MASK_IV_TYPE(L) (L)->iv_type
662 #define LOOP_VINFO_PTR_MASK(L) (L)->ptr_mask
663 #define LOOP_VINFO_LOOP_NEST(L) (L)->shared->loop_nest
664 #define LOOP_VINFO_DATAREFS(L) (L)->shared->datarefs
665 #define LOOP_VINFO_DDRS(L) (L)->shared->ddrs
666 #define LOOP_VINFO_INT_NITERS(L) (TREE_INT_CST_LOW ((L)->num_iters))
667 #define LOOP_VINFO_PEELING_FOR_ALIGNMENT(L) (L)->peeling_for_alignment
668 #define LOOP_VINFO_UNALIGNED_DR(L) (L)->unaligned_dr
669 #define LOOP_VINFO_MAY_MISALIGN_STMTS(L) (L)->may_misalign_stmts
670 #define LOOP_VINFO_MAY_ALIAS_DDRS(L) (L)->may_alias_ddrs
671 #define LOOP_VINFO_COMP_ALIAS_DDRS(L) (L)->comp_alias_ddrs
672 #define LOOP_VINFO_CHECK_UNEQUAL_ADDRS(L) (L)->check_unequal_addrs
673 #define LOOP_VINFO_CHECK_NONZERO(L) (L)->check_nonzero
674 #define LOOP_VINFO_LOWER_BOUNDS(L) (L)->lower_bounds
675 #define LOOP_VINFO_GROUPED_STORES(L) (L)->grouped_stores
676 #define LOOP_VINFO_SLP_INSTANCES(L) (L)->slp_instances
677 #define LOOP_VINFO_SLP_UNROLLING_FACTOR(L) (L)->slp_unrolling_factor
678 #define LOOP_VINFO_REDUCTIONS(L) (L)->reductions
679 #define LOOP_VINFO_REDUCTION_CHAINS(L) (L)->reduction_chains
680 #define LOOP_VINFO_TARGET_COST_DATA(L) (L)->target_cost_data
681 #define LOOP_VINFO_PEELING_FOR_GAPS(L) (L)->peeling_for_gaps
682 #define LOOP_VINFO_PEELING_FOR_NITER(L) (L)->peeling_for_niter
683 #define LOOP_VINFO_NO_DATA_DEPENDENCIES(L) (L)->no_data_dependencies
684 #define LOOP_VINFO_SCALAR_LOOP(L) (L)->scalar_loop
685 #define LOOP_VINFO_SCALAR_LOOP_SCALING(L) (L)->scalar_loop_scaling
686 #define LOOP_VINFO_HAS_MASK_STORE(L) (L)->has_mask_store
687 #define LOOP_VINFO_SCALAR_ITERATION_COST(L) (L)->scalar_cost_vec
688 #define LOOP_VINFO_SINGLE_SCALAR_ITERATION_COST(L) (L)->single_scalar_iteration_cost
689 #define LOOP_VINFO_ORIG_LOOP_INFO(L) (L)->orig_loop_info
690 #define LOOP_VINFO_SIMD_IF_COND(L) (L)->simd_if_cond
692 #define LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT(L) \
693 ((L)->may_misalign_stmts.length () > 0)
694 #define LOOP_REQUIRES_VERSIONING_FOR_ALIAS(L) \
695 ((L)->comp_alias_ddrs.length () > 0 \
696 || (L)->check_unequal_addrs.length () > 0 \
697 || (L)->lower_bounds.length () > 0)
698 #define LOOP_REQUIRES_VERSIONING_FOR_NITERS(L) \
699 (LOOP_VINFO_NITERS_ASSUMPTIONS (L))
700 #define LOOP_REQUIRES_VERSIONING_FOR_SIMD_IF_COND(L) \
701 (LOOP_VINFO_SIMD_IF_COND (L))
702 #define LOOP_REQUIRES_VERSIONING(L) \
703 (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (L) \
704 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (L) \
705 || LOOP_REQUIRES_VERSIONING_FOR_NITERS (L) \
706 || LOOP_REQUIRES_VERSIONING_FOR_SIMD_IF_COND (L))
708 #define LOOP_VINFO_NITERS_KNOWN_P(L) \
709 (tree_fits_shwi_p ((L)->num_iters) && tree_to_shwi ((L)->num_iters) > 0)
711 #define LOOP_VINFO_EPILOGUE_P(L) \
712 (LOOP_VINFO_ORIG_LOOP_INFO (L) != NULL)
714 #define LOOP_VINFO_ORIG_MAX_VECT_FACTOR(L) \
715 (LOOP_VINFO_MAX_VECT_FACTOR (LOOP_VINFO_ORIG_LOOP_INFO (L)))
717 /* Wrapper for loop_vec_info, for tracking success/failure, where a non-NULL
718 value signifies success, and a NULL value signifies failure, supporting
719 propagating an opt_problem * describing the failure back up the call
721 typedef opt_pointer_wrapper
<loop_vec_info
> opt_loop_vec_info
;
723 static inline loop_vec_info
724 loop_vec_info_for_loop (class loop
*loop
)
726 return (loop_vec_info
) loop
->aux
;
729 typedef class _bb_vec_info
: public vec_info
732 _bb_vec_info (gimple_stmt_iterator
, gimple_stmt_iterator
, vec_info_shared
*);
736 gimple_stmt_iterator region_begin
;
737 gimple_stmt_iterator region_end
;
740 #define BB_VINFO_BB(B) (B)->bb
741 #define BB_VINFO_GROUPED_STORES(B) (B)->grouped_stores
742 #define BB_VINFO_SLP_INSTANCES(B) (B)->slp_instances
743 #define BB_VINFO_DATAREFS(B) (B)->shared->datarefs
744 #define BB_VINFO_DDRS(B) (B)->shared->ddrs
745 #define BB_VINFO_TARGET_COST_DATA(B) (B)->target_cost_data
747 static inline bb_vec_info
748 vec_info_for_bb (basic_block bb
)
750 return (bb_vec_info
) bb
->aux
;
753 /*-----------------------------------------------------------------*/
754 /* Info on vectorized defs. */
755 /*-----------------------------------------------------------------*/
756 enum stmt_vec_info_type
{
757 undef_vec_info_type
= 0,
763 call_simd_clone_vec_info_type
,
764 assignment_vec_info_type
,
765 condition_vec_info_type
,
766 comparison_vec_info_type
,
769 type_promotion_vec_info_type
,
770 type_demotion_vec_info_type
,
771 type_conversion_vec_info_type
,
774 loop_exit_ctrl_vec_info_type
777 /* Indicates whether/how a variable is used in the scope of loop/basic
780 vect_unused_in_scope
= 0,
782 /* The def is only used outside the loop. */
784 /* The def is in the inner loop, and the use is in the outer loop, and the
785 use is a reduction stmt. */
786 vect_used_in_outer_by_reduction
,
787 /* The def is in the inner loop, and the use is in the outer loop (and is
788 not part of reduction). */
791 /* defs that feed computations that end up (only) in a reduction. These
792 defs may be used by non-reduction stmts, but eventually, any
793 computations/values that are affected by these defs are used to compute
794 a reduction (i.e. don't get stored to memory, for example). We use this
795 to identify computations that we can change the order in which they are
797 vect_used_by_reduction
,
802 /* The type of vectorization that can be applied to the stmt: regular loop-based
803 vectorization; pure SLP - the stmt is a part of SLP instances and does not
804 have uses outside SLP instances; or hybrid SLP and loop-based - the stmt is
805 a part of SLP instance and also must be loop-based vectorized, since it has
806 uses outside SLP sequences.
808 In the loop context the meanings of pure and hybrid SLP are slightly
809 different. By saying that pure SLP is applied to the loop, we mean that we
810 exploit only intra-iteration parallelism in the loop; i.e., the loop can be
811 vectorized without doing any conceptual unrolling, cause we don't pack
812 together stmts from different iterations, only within a single iteration.
813 Loop hybrid SLP means that we exploit both intra-iteration and
814 inter-iteration parallelism (e.g., number of elements in the vector is 4
815 and the slp-group-size is 2, in which case we don't have enough parallelism
816 within an iteration, so we obtain the rest of the parallelism from subsequent
817 iterations by unrolling the loop by 2). */
824 /* Says whether a statement is a load, a store of a vectorized statement
825 result, or a store of an invariant value. */
826 enum vec_load_store_type
{
832 /* Describes how we're going to vectorize an individual load or store,
833 or a group of loads or stores. */
834 enum vect_memory_access_type
{
835 /* An access to an invariant address. This is used only for loads. */
838 /* A simple contiguous access. */
841 /* A contiguous access that goes down in memory rather than up,
842 with no additional permutation. This is used only for stores
844 VMAT_CONTIGUOUS_DOWN
,
846 /* A simple contiguous access in which the elements need to be permuted
847 after loading or before storing. Only used for loop vectorization;
848 SLP uses separate permutes. */
849 VMAT_CONTIGUOUS_PERMUTE
,
851 /* A simple contiguous access in which the elements need to be reversed
852 after loading or before storing. */
853 VMAT_CONTIGUOUS_REVERSE
,
855 /* An access that uses IFN_LOAD_LANES or IFN_STORE_LANES. */
856 VMAT_LOAD_STORE_LANES
,
858 /* An access in which each scalar element is loaded or stored
862 /* A hybrid of VMAT_CONTIGUOUS and VMAT_ELEMENTWISE, used for grouped
863 SLP accesses. Each unrolled iteration uses a contiguous load
864 or store for the whole group, but the groups from separate iterations
865 are combined in the same way as for VMAT_ELEMENTWISE. */
868 /* The access uses gather loads or scatter stores. */
874 /* The data reference itself. */
876 /* The statement that contains the data reference. */
878 /* The misalignment in bytes of the reference, or -1 if not known. */
880 /* The byte alignment that we'd ideally like the reference to have,
881 and the value that misalignment is measured against. */
882 poly_uint64 target_alignment
;
883 /* If true the alignment of base_decl needs to be increased. */
884 bool base_misaligned
;
888 typedef struct data_reference
*dr_p
;
890 class _stmt_vec_info
{
893 enum stmt_vec_info_type type
;
895 /* Indicates whether this stmts is part of a computation whose result is
896 used outside the loop. */
899 /* Stmt is part of some pattern (computation idiom) */
902 /* True if the statement was created during pattern recognition as
903 part of the replacement for RELATED_STMT. This implies that the
904 statement isn't part of any basic block, although for convenience
905 its gimple_bb is the same as for RELATED_STMT. */
908 /* Is this statement vectorizable or should it be skipped in (partial)
912 /* The stmt to which this info struct refers to. */
915 /* The vec_info with respect to which STMT is vectorized. */
918 /* The vector type to be used for the LHS of this statement. */
921 /* The vectorized version of the stmt. */
922 stmt_vec_info vectorized_stmt
;
925 /* The following is relevant only for stmts that contain a non-scalar
926 data-ref (array/pointer/struct access). A GIMPLE stmt is expected to have
927 at most one such data-ref. */
931 /* Information about the data-ref relative to this loop
932 nest (the loop that is being considered for vectorization). */
933 innermost_loop_behavior dr_wrt_vec_loop
;
935 /* For loop PHI nodes, the base and evolution part of it. This makes sure
936 this information is still available in vect_update_ivs_after_vectorizer
937 where we may not be able to re-analyze the PHI nodes evolution as
938 peeling for the prologue loop can make it unanalyzable. The evolution
939 part is still correct after peeling, but the base may have changed from
941 tree loop_phi_evolution_base_unchanged
;
942 tree loop_phi_evolution_part
;
944 /* Used for various bookkeeping purposes, generally holding a pointer to
945 some other stmt S that is in some way "related" to this stmt.
946 Current use of this field is:
947 If this stmt is part of a pattern (i.e. the field 'in_pattern_p' is
948 true): S is the "pattern stmt" that represents (and replaces) the
949 sequence of stmts that constitutes the pattern. Similarly, the
950 related_stmt of the "pattern stmt" points back to this stmt (which is
951 the last stmt in the original sequence of stmts that constitutes the
953 stmt_vec_info related_stmt
;
955 /* Used to keep a sequence of def stmts of a pattern stmt if such exists.
956 The sequence is attached to the original statement rather than the
957 pattern statement. */
958 gimple_seq pattern_def_seq
;
960 /* List of datarefs that are known to have the same alignment as the dataref
962 vec
<dr_p
> same_align_refs
;
964 /* Selected SIMD clone's function info. First vector element
965 is SIMD clone's function decl, followed by a pair of trees (base + step)
966 for linear arguments (pair of NULLs for other arguments). */
967 vec
<tree
> simd_clone_info
;
969 /* Classify the def of this stmt. */
970 enum vect_def_type def_type
;
972 /* Whether the stmt is SLPed, loop-based vectorized, or both. */
973 enum slp_vect_type slp_type
;
975 /* Interleaving and reduction chains info. */
976 /* First element in the group. */
977 stmt_vec_info first_element
;
978 /* Pointer to the next element in the group. */
979 stmt_vec_info next_element
;
980 /* The size of the group. */
982 /* For stores, number of stores from this group seen. We vectorize the last
984 unsigned int store_count
;
985 /* For loads only, the gap from the previous load. For consecutive loads, GAP
989 /* The minimum negative dependence distance this stmt participates in
991 unsigned int min_neg_dist
;
993 /* Not all stmts in the loop need to be vectorized. e.g, the increment
994 of the loop induction variable and computation of array indexes. relevant
995 indicates whether the stmt needs to be vectorized. */
996 enum vect_relevant relevant
;
998 /* For loads if this is a gather, for stores if this is a scatter. */
999 bool gather_scatter_p
;
1001 /* True if this is an access with loop-invariant stride. */
1004 /* For both loads and stores. */
1005 unsigned simd_lane_access_p
: 3;
1007 /* Classifies how the load or store is going to be implemented
1008 for loop vectorization. */
1009 vect_memory_access_type memory_access_type
;
1011 /* For INTEGER_INDUC_COND_REDUCTION, the initial value to be used. */
1012 tree induc_cond_initial_val
;
1014 /* If not NULL the value to be added to compute final reduction value. */
1015 tree reduc_epilogue_adjustment
;
1017 /* On a reduction PHI the reduction type as detected by
1018 vect_is_simple_reduction and vectorizable_reduction. */
1019 enum vect_reduction_type reduc_type
;
1021 /* The original reduction code, to be used in the epilogue. */
1022 enum tree_code reduc_code
;
1023 /* An internal function we should use in the epilogue. */
1024 internal_fn reduc_fn
;
1026 /* On a stmt participating in the reduction the index of the operand
1027 on the reduction SSA cycle. */
1030 /* On a reduction PHI the def returned by vect_force_simple_reduction.
1031 On the def returned by vect_force_simple_reduction the
1032 corresponding PHI. */
1033 stmt_vec_info reduc_def
;
1035 /* The vector input type relevant for reduction vectorization. */
1036 tree reduc_vectype_in
;
1038 /* Whether we force a single cycle PHI during reduction vectorization. */
1039 bool force_single_cycle
;
1041 /* Whether on this stmt reduction meta is recorded. */
1044 /* The number of scalar stmt references from active SLP instances. */
1045 unsigned int num_slp_uses
;
1047 /* If nonzero, the lhs of the statement could be truncated to this
1048 many bits without affecting any users of the result. */
1049 unsigned int min_output_precision
;
1051 /* If nonzero, all non-boolean input operands have the same precision,
1052 and they could each be truncated to this many bits without changing
1054 unsigned int min_input_precision
;
1056 /* If OPERATION_BITS is nonzero, the statement could be performed on
1057 an integer with the sign and number of bits given by OPERATION_SIGN
1058 and OPERATION_BITS without changing the result. */
1059 unsigned int operation_precision
;
1060 signop operation_sign
;
1062 /* True if this is only suitable for SLP vectorization. */
1063 bool slp_vect_only_p
;
1066 /* Information about a gather/scatter call. */
1067 struct gather_scatter_info
{
1068 /* The internal function to use for the gather/scatter operation,
1069 or IFN_LAST if a built-in function should be used instead. */
1072 /* The FUNCTION_DECL for the built-in gather/scatter function,
1073 or null if an internal function should be used instead. */
1076 /* The loop-invariant base value. */
1079 /* The original scalar offset, which is a non-loop-invariant SSA_NAME. */
1082 /* Each offset element should be multiplied by this amount before
1083 being added to the base. */
1086 /* The definition type for the vectorized offset. */
1087 enum vect_def_type offset_dt
;
1089 /* The type of the vectorized offset. */
1090 tree offset_vectype
;
1092 /* The type of the scalar elements after loading or before storing. */
1095 /* The type of the scalar elements being loaded or stored. */
1099 /* Access Functions. */
1100 #define STMT_VINFO_TYPE(S) (S)->type
1101 #define STMT_VINFO_STMT(S) (S)->stmt
1102 inline loop_vec_info
1103 STMT_VINFO_LOOP_VINFO (stmt_vec_info stmt_vinfo
)
1105 if (loop_vec_info loop_vinfo
= dyn_cast
<loop_vec_info
> (stmt_vinfo
->vinfo
))
1110 STMT_VINFO_BB_VINFO (stmt_vec_info stmt_vinfo
)
1112 if (bb_vec_info bb_vinfo
= dyn_cast
<bb_vec_info
> (stmt_vinfo
->vinfo
))
1116 #define STMT_VINFO_RELEVANT(S) (S)->relevant
1117 #define STMT_VINFO_LIVE_P(S) (S)->live
1118 #define STMT_VINFO_VECTYPE(S) (S)->vectype
1119 #define STMT_VINFO_VEC_STMT(S) (S)->vectorized_stmt
1120 #define STMT_VINFO_VECTORIZABLE(S) (S)->vectorizable
1121 #define STMT_VINFO_DATA_REF(S) ((S)->dr_aux.dr + 0)
1122 #define STMT_VINFO_GATHER_SCATTER_P(S) (S)->gather_scatter_p
1123 #define STMT_VINFO_STRIDED_P(S) (S)->strided_p
1124 #define STMT_VINFO_MEMORY_ACCESS_TYPE(S) (S)->memory_access_type
1125 #define STMT_VINFO_SIMD_LANE_ACCESS_P(S) (S)->simd_lane_access_p
1126 #define STMT_VINFO_VEC_INDUC_COND_INITIAL_VAL(S) (S)->induc_cond_initial_val
1127 #define STMT_VINFO_REDUC_EPILOGUE_ADJUSTMENT(S) (S)->reduc_epilogue_adjustment
1128 #define STMT_VINFO_REDUC_IDX(S) (S)->reduc_idx
1129 #define STMT_VINFO_FORCE_SINGLE_CYCLE(S) (S)->force_single_cycle
1131 #define STMT_VINFO_DR_WRT_VEC_LOOP(S) (S)->dr_wrt_vec_loop
1132 #define STMT_VINFO_DR_BASE_ADDRESS(S) (S)->dr_wrt_vec_loop.base_address
1133 #define STMT_VINFO_DR_INIT(S) (S)->dr_wrt_vec_loop.init
1134 #define STMT_VINFO_DR_OFFSET(S) (S)->dr_wrt_vec_loop.offset
1135 #define STMT_VINFO_DR_STEP(S) (S)->dr_wrt_vec_loop.step
1136 #define STMT_VINFO_DR_BASE_ALIGNMENT(S) (S)->dr_wrt_vec_loop.base_alignment
1137 #define STMT_VINFO_DR_BASE_MISALIGNMENT(S) \
1138 (S)->dr_wrt_vec_loop.base_misalignment
1139 #define STMT_VINFO_DR_OFFSET_ALIGNMENT(S) \
1140 (S)->dr_wrt_vec_loop.offset_alignment
1141 #define STMT_VINFO_DR_STEP_ALIGNMENT(S) \
1142 (S)->dr_wrt_vec_loop.step_alignment
1144 #define STMT_VINFO_DR_INFO(S) \
1145 (gcc_checking_assert ((S)->dr_aux.stmt == (S)), &(S)->dr_aux)
1147 #define STMT_VINFO_IN_PATTERN_P(S) (S)->in_pattern_p
1148 #define STMT_VINFO_RELATED_STMT(S) (S)->related_stmt
1149 #define STMT_VINFO_PATTERN_DEF_SEQ(S) (S)->pattern_def_seq
1150 #define STMT_VINFO_SAME_ALIGN_REFS(S) (S)->same_align_refs
1151 #define STMT_VINFO_SIMD_CLONE_INFO(S) (S)->simd_clone_info
1152 #define STMT_VINFO_DEF_TYPE(S) (S)->def_type
1153 #define STMT_VINFO_GROUPED_ACCESS(S) \
1154 ((S)->dr_aux.dr && DR_GROUP_FIRST_ELEMENT(S))
1155 #define STMT_VINFO_LOOP_PHI_EVOLUTION_BASE_UNCHANGED(S) (S)->loop_phi_evolution_base_unchanged
1156 #define STMT_VINFO_LOOP_PHI_EVOLUTION_PART(S) (S)->loop_phi_evolution_part
1157 #define STMT_VINFO_MIN_NEG_DIST(S) (S)->min_neg_dist
1158 #define STMT_VINFO_NUM_SLP_USES(S) (S)->num_slp_uses
1159 #define STMT_VINFO_REDUC_TYPE(S) (S)->reduc_type
1160 #define STMT_VINFO_REDUC_CODE(S) (S)->reduc_code
1161 #define STMT_VINFO_REDUC_FN(S) (S)->reduc_fn
1162 #define STMT_VINFO_REDUC_DEF(S) (S)->reduc_def
1163 #define STMT_VINFO_REDUC_VECTYPE_IN(S) (S)->reduc_vectype_in
1164 #define STMT_VINFO_SLP_VECT_ONLY(S) (S)->slp_vect_only_p
1166 #define DR_GROUP_FIRST_ELEMENT(S) \
1167 (gcc_checking_assert ((S)->dr_aux.dr), (S)->first_element)
1168 #define DR_GROUP_NEXT_ELEMENT(S) \
1169 (gcc_checking_assert ((S)->dr_aux.dr), (S)->next_element)
1170 #define DR_GROUP_SIZE(S) \
1171 (gcc_checking_assert ((S)->dr_aux.dr), (S)->size)
1172 #define DR_GROUP_STORE_COUNT(S) \
1173 (gcc_checking_assert ((S)->dr_aux.dr), (S)->store_count)
1174 #define DR_GROUP_GAP(S) \
1175 (gcc_checking_assert ((S)->dr_aux.dr), (S)->gap)
1177 #define REDUC_GROUP_FIRST_ELEMENT(S) \
1178 (gcc_checking_assert (!(S)->dr_aux.dr), (S)->first_element)
1179 #define REDUC_GROUP_NEXT_ELEMENT(S) \
1180 (gcc_checking_assert (!(S)->dr_aux.dr), (S)->next_element)
1181 #define REDUC_GROUP_SIZE(S) \
1182 (gcc_checking_assert (!(S)->dr_aux.dr), (S)->size)
1184 #define STMT_VINFO_RELEVANT_P(S) ((S)->relevant != vect_unused_in_scope)
1186 #define HYBRID_SLP_STMT(S) ((S)->slp_type == hybrid)
1187 #define PURE_SLP_STMT(S) ((S)->slp_type == pure_slp)
1188 #define STMT_SLP_TYPE(S) (S)->slp_type
1190 #define VECT_MAX_COST 1000
1192 /* The maximum number of intermediate steps required in multi-step type
1194 #define MAX_INTERM_CVT_STEPS 3
1196 #define MAX_VECTORIZATION_FACTOR INT_MAX
1198 /* Nonzero if TYPE represents a (scalar) boolean type or type
1199 in the middle-end compatible with it (unsigned precision 1 integral
1200 types). Used to determine which types should be vectorized as
1201 VECTOR_BOOLEAN_TYPE_P. */
1203 #define VECT_SCALAR_BOOLEAN_TYPE_P(TYPE) \
1204 (TREE_CODE (TYPE) == BOOLEAN_TYPE \
1205 || ((TREE_CODE (TYPE) == INTEGER_TYPE \
1206 || TREE_CODE (TYPE) == ENUMERAL_TYPE) \
1207 && TYPE_PRECISION (TYPE) == 1 \
1208 && TYPE_UNSIGNED (TYPE)))
1211 nested_in_vect_loop_p (class loop
*loop
, stmt_vec_info stmt_info
)
1214 && (loop
->inner
== (gimple_bb (stmt_info
->stmt
))->loop_father
));
1217 /* Return TRUE if a statement represented by STMT_INFO is a part of a
1221 is_pattern_stmt_p (stmt_vec_info stmt_info
)
1223 return stmt_info
->pattern_stmt_p
;
1226 /* If STMT_INFO is a pattern statement, return the statement that it
1227 replaces, otherwise return STMT_INFO itself. */
1229 inline stmt_vec_info
1230 vect_orig_stmt (stmt_vec_info stmt_info
)
1232 if (is_pattern_stmt_p (stmt_info
))
1233 return STMT_VINFO_RELATED_STMT (stmt_info
);
1237 /* Return the later statement between STMT1_INFO and STMT2_INFO. */
1239 static inline stmt_vec_info
1240 get_later_stmt (stmt_vec_info stmt1_info
, stmt_vec_info stmt2_info
)
1242 if (gimple_uid (vect_orig_stmt (stmt1_info
)->stmt
)
1243 > gimple_uid (vect_orig_stmt (stmt2_info
)->stmt
))
1249 /* If STMT_INFO has been replaced by a pattern statement, return the
1250 replacement statement, otherwise return STMT_INFO itself. */
1252 inline stmt_vec_info
1253 vect_stmt_to_vectorize (stmt_vec_info stmt_info
)
1255 if (STMT_VINFO_IN_PATTERN_P (stmt_info
))
1256 return STMT_VINFO_RELATED_STMT (stmt_info
);
1260 /* Return true if BB is a loop header. */
1263 is_loop_header_bb_p (basic_block bb
)
1265 if (bb
== (bb
->loop_father
)->header
)
1267 gcc_checking_assert (EDGE_COUNT (bb
->preds
) == 1);
1271 /* Return pow2 (X). */
1278 for (i
= 0; i
< x
; i
++)
1284 /* Alias targetm.vectorize.builtin_vectorization_cost. */
1287 builtin_vectorization_cost (enum vect_cost_for_stmt type_of_cost
,
1288 tree vectype
, int misalign
)
1290 return targetm
.vectorize
.builtin_vectorization_cost (type_of_cost
,
1294 /* Get cost by calling cost target builtin. */
1297 int vect_get_stmt_cost (enum vect_cost_for_stmt type_of_cost
)
1299 return builtin_vectorization_cost (type_of_cost
, NULL
, 0);
1302 /* Alias targetm.vectorize.init_cost. */
1304 static inline void *
1305 init_cost (class loop
*loop_info
)
1307 return targetm
.vectorize
.init_cost (loop_info
);
1310 extern void dump_stmt_cost (FILE *, void *, int, enum vect_cost_for_stmt
,
1311 stmt_vec_info
, int, unsigned,
1312 enum vect_cost_model_location
);
1314 /* Alias targetm.vectorize.add_stmt_cost. */
1316 static inline unsigned
1317 add_stmt_cost (void *data
, int count
, enum vect_cost_for_stmt kind
,
1318 stmt_vec_info stmt_info
, int misalign
,
1319 enum vect_cost_model_location where
)
1321 unsigned cost
= targetm
.vectorize
.add_stmt_cost (data
, count
, kind
,
1322 stmt_info
, misalign
, where
);
1323 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1324 dump_stmt_cost (dump_file
, data
, count
, kind
, stmt_info
, misalign
,
1329 /* Alias targetm.vectorize.finish_cost. */
1332 finish_cost (void *data
, unsigned *prologue_cost
,
1333 unsigned *body_cost
, unsigned *epilogue_cost
)
1335 targetm
.vectorize
.finish_cost (data
, prologue_cost
, body_cost
, epilogue_cost
);
1338 /* Alias targetm.vectorize.destroy_cost_data. */
1341 destroy_cost_data (void *data
)
1343 targetm
.vectorize
.destroy_cost_data (data
);
1347 add_stmt_costs (void *data
, stmt_vector_for_cost
*cost_vec
)
1349 stmt_info_for_cost
*cost
;
1351 FOR_EACH_VEC_ELT (*cost_vec
, i
, cost
)
1352 add_stmt_cost (data
, cost
->count
, cost
->kind
, cost
->stmt_info
,
1353 cost
->misalign
, cost
->where
);
1356 /*-----------------------------------------------------------------*/
1357 /* Info on data references alignment. */
1358 /*-----------------------------------------------------------------*/
1359 #define DR_MISALIGNMENT_UNKNOWN (-1)
1360 #define DR_MISALIGNMENT_UNINITIALIZED (-2)
1363 set_dr_misalignment (dr_vec_info
*dr_info
, int val
)
1365 dr_info
->misalignment
= val
;
1369 dr_misalignment (dr_vec_info
*dr_info
)
1371 int misalign
= dr_info
->misalignment
;
1372 gcc_assert (misalign
!= DR_MISALIGNMENT_UNINITIALIZED
);
1376 /* Reflects actual alignment of first access in the vectorized loop,
1377 taking into account peeling/versioning if applied. */
1378 #define DR_MISALIGNMENT(DR) dr_misalignment (DR)
1379 #define SET_DR_MISALIGNMENT(DR, VAL) set_dr_misalignment (DR, VAL)
1381 /* Only defined once DR_MISALIGNMENT is defined. */
1382 #define DR_TARGET_ALIGNMENT(DR) ((DR)->target_alignment)
1384 /* Return true if data access DR_INFO is aligned to its target alignment
1385 (which may be less than a full vector). */
1388 aligned_access_p (dr_vec_info
*dr_info
)
1390 return (DR_MISALIGNMENT (dr_info
) == 0);
1393 /* Return TRUE if the alignment of the data access is known, and FALSE
1397 known_alignment_for_access_p (dr_vec_info
*dr_info
)
1399 return (DR_MISALIGNMENT (dr_info
) != DR_MISALIGNMENT_UNKNOWN
);
1402 /* Return the minimum alignment in bytes that the vectorized version
1403 of DR_INFO is guaranteed to have. */
1405 static inline unsigned int
1406 vect_known_alignment_in_bytes (dr_vec_info
*dr_info
)
1408 if (DR_MISALIGNMENT (dr_info
) == DR_MISALIGNMENT_UNKNOWN
)
1409 return TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_info
->dr
)));
1410 if (DR_MISALIGNMENT (dr_info
) == 0)
1411 return known_alignment (DR_TARGET_ALIGNMENT (dr_info
));
1412 return DR_MISALIGNMENT (dr_info
) & -DR_MISALIGNMENT (dr_info
);
1415 /* Return the behavior of DR_INFO with respect to the vectorization context
1416 (which for outer loop vectorization might not be the behavior recorded
1417 in DR_INFO itself). */
1419 static inline innermost_loop_behavior
*
1420 vect_dr_behavior (dr_vec_info
*dr_info
)
1422 stmt_vec_info stmt_info
= dr_info
->stmt
;
1423 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
1424 if (loop_vinfo
== NULL
1425 || !nested_in_vect_loop_p (LOOP_VINFO_LOOP (loop_vinfo
), stmt_info
))
1426 return &DR_INNERMOST (dr_info
->dr
);
1428 return &STMT_VINFO_DR_WRT_VEC_LOOP (stmt_info
);
1431 /* Return true if the vect cost model is unlimited. */
1433 unlimited_cost_model (loop_p loop
)
1435 if (loop
!= NULL
&& loop
->force_vectorize
1436 && flag_simd_cost_model
!= VECT_COST_MODEL_DEFAULT
)
1437 return flag_simd_cost_model
== VECT_COST_MODEL_UNLIMITED
;
1438 return (flag_vect_cost_model
== VECT_COST_MODEL_UNLIMITED
);
1441 /* Return true if the loop described by LOOP_VINFO is fully-masked and
1442 if the first iteration should use a partial mask in order to achieve
1446 vect_use_loop_mask_for_alignment_p (loop_vec_info loop_vinfo
)
1448 return (LOOP_VINFO_FULLY_MASKED_P (loop_vinfo
)
1449 && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo
));
1452 /* Return the number of vectors of type VECTYPE that are needed to get
1453 NUNITS elements. NUNITS should be based on the vectorization factor,
1454 so it is always a known multiple of the number of elements in VECTYPE. */
1456 static inline unsigned int
1457 vect_get_num_vectors (poly_uint64 nunits
, tree vectype
)
1459 return exact_div (nunits
, TYPE_VECTOR_SUBPARTS (vectype
)).to_constant ();
1462 /* Return the number of copies needed for loop vectorization when
1463 a statement operates on vectors of type VECTYPE. This is the
1464 vectorization factor divided by the number of elements in
1465 VECTYPE and is always known at compile time. */
1467 static inline unsigned int
1468 vect_get_num_copies (loop_vec_info loop_vinfo
, tree vectype
)
1470 return vect_get_num_vectors (LOOP_VINFO_VECT_FACTOR (loop_vinfo
), vectype
);
1473 /* Update maximum unit count *MAX_NUNITS so that it accounts for
1474 NUNITS. *MAX_NUNITS can be 1 if we haven't yet recorded anything. */
1477 vect_update_max_nunits (poly_uint64
*max_nunits
, poly_uint64 nunits
)
1479 /* All unit counts have the form vec_info::vector_size * X for some
1480 rational X, so two unit sizes must have a common multiple.
1481 Everything is a multiple of the initial value of 1. */
1482 *max_nunits
= force_common_multiple (*max_nunits
, nunits
);
1485 /* Update maximum unit count *MAX_NUNITS so that it accounts for
1486 the number of units in vector type VECTYPE. *MAX_NUNITS can be 1
1487 if we haven't yet recorded any vector types. */
1490 vect_update_max_nunits (poly_uint64
*max_nunits
, tree vectype
)
1492 vect_update_max_nunits (max_nunits
, TYPE_VECTOR_SUBPARTS (vectype
));
1495 /* Return the vectorization factor that should be used for costing
1496 purposes while vectorizing the loop described by LOOP_VINFO.
1497 Pick a reasonable estimate if the vectorization factor isn't
1498 known at compile time. */
1500 static inline unsigned int
1501 vect_vf_for_cost (loop_vec_info loop_vinfo
)
1503 return estimated_poly_value (LOOP_VINFO_VECT_FACTOR (loop_vinfo
));
1506 /* Estimate the number of elements in VEC_TYPE for costing purposes.
1507 Pick a reasonable estimate if the exact number isn't known at
1510 static inline unsigned int
1511 vect_nunits_for_cost (tree vec_type
)
1513 return estimated_poly_value (TYPE_VECTOR_SUBPARTS (vec_type
));
1516 /* Return the maximum possible vectorization factor for LOOP_VINFO. */
1518 static inline unsigned HOST_WIDE_INT
1519 vect_max_vf (loop_vec_info loop_vinfo
)
1521 unsigned HOST_WIDE_INT vf
;
1522 if (LOOP_VINFO_VECT_FACTOR (loop_vinfo
).is_constant (&vf
))
1524 return MAX_VECTORIZATION_FACTOR
;
1527 /* Return the size of the value accessed by unvectorized data reference
1528 DR_INFO. This is only valid once STMT_VINFO_VECTYPE has been calculated
1529 for the associated gimple statement, since that guarantees that DR_INFO
1530 accesses either a scalar or a scalar equivalent. ("Scalar equivalent"
1531 here includes things like V1SI, which can be vectorized in the same way
1535 vect_get_scalar_dr_size (dr_vec_info
*dr_info
)
1537 return tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_info
->dr
))));
1540 /* Source location + hotness information. */
1541 extern dump_user_location_t vect_location
;
1543 /* A macro for calling:
1544 dump_begin_scope (MSG, vect_location);
1545 via an RAII object, thus printing "=== MSG ===\n" to the dumpfile etc,
1548 once the object goes out of scope, thus capturing the nesting of
1551 These scopes affect dump messages within them: dump messages at the
1552 top level implicitly default to MSG_PRIORITY_USER_FACING, whereas those
1553 in a nested scope implicitly default to MSG_PRIORITY_INTERNALS. */
1555 #define DUMP_VECT_SCOPE(MSG) \
1556 AUTO_DUMP_SCOPE (MSG, vect_location)
1558 /* A sentinel class for ensuring that the "vect_location" global gets
1559 reset at the end of a scope.
1561 The "vect_location" global is used during dumping and contains a
1562 location_t, which could contain references to a tree block via the
1563 ad-hoc data. This data is used for tracking inlining information,
1564 but it's not a GC root; it's simply assumed that such locations never
1565 get accessed if the blocks are optimized away.
1567 Hence we need to ensure that such locations are purged at the end
1568 of any operations using them (e.g. via this class). */
1570 class auto_purge_vect_location
1573 ~auto_purge_vect_location ();
1576 /*-----------------------------------------------------------------*/
1577 /* Function prototypes. */
1578 /*-----------------------------------------------------------------*/
1580 /* Simple loop peeling and versioning utilities for vectorizer's purposes -
1581 in tree-vect-loop-manip.c. */
1582 extern void vect_set_loop_condition (class loop
*, loop_vec_info
,
1583 tree
, tree
, tree
, bool);
1584 extern bool slpeel_can_duplicate_loop_p (const class loop
*, const_edge
);
1585 class loop
*slpeel_tree_duplicate_loop_to_edge_cfg (class loop
*,
1586 class loop
*, edge
);
1587 class loop
*vect_loop_versioning (loop_vec_info
);
1588 extern class loop
*vect_do_peeling (loop_vec_info
, tree
, tree
,
1589 tree
*, tree
*, tree
*, int, bool, bool);
1590 extern void vect_prepare_for_masked_peels (loop_vec_info
);
1591 extern dump_user_location_t
find_loop_location (class loop
*);
1592 extern bool vect_can_advance_ivs_p (loop_vec_info
);
1594 /* In tree-vect-stmts.c. */
1595 extern tree
get_vectype_for_scalar_type (vec_info
*, tree
);
1596 extern tree
get_vectype_for_scalar_type_and_size (tree
, poly_uint64
);
1597 extern tree
get_mask_type_for_scalar_type (vec_info
*, tree
);
1598 extern tree
get_same_sized_vectype (tree
, tree
);
1599 extern bool vect_get_loop_mask_type (loop_vec_info
);
1600 extern bool vect_is_simple_use (tree
, vec_info
*, enum vect_def_type
*,
1601 stmt_vec_info
* = NULL
, gimple
** = NULL
);
1602 extern bool vect_is_simple_use (tree
, vec_info
*, enum vect_def_type
*,
1603 tree
*, stmt_vec_info
* = NULL
,
1605 extern bool supportable_widening_operation (enum tree_code
, stmt_vec_info
,
1606 tree
, tree
, enum tree_code
*,
1607 enum tree_code
*, int *,
1609 extern bool supportable_narrowing_operation (vec_info
*, enum tree_code
, tree
,
1610 tree
, enum tree_code
*,
1611 int *, vec
<tree
> *);
1612 extern unsigned record_stmt_cost (stmt_vector_for_cost
*, int,
1613 enum vect_cost_for_stmt
, stmt_vec_info
,
1614 int, enum vect_cost_model_location
);
1615 extern stmt_vec_info
vect_finish_replace_stmt (stmt_vec_info
, gimple
*);
1616 extern stmt_vec_info
vect_finish_stmt_generation (stmt_vec_info
, gimple
*,
1617 gimple_stmt_iterator
*);
1618 extern opt_result
vect_mark_stmts_to_be_vectorized (loop_vec_info
, bool *);
1619 extern tree
vect_get_store_rhs (stmt_vec_info
);
1620 extern tree
vect_get_vec_def_for_operand_1 (stmt_vec_info
, enum vect_def_type
);
1621 extern tree
vect_get_vec_def_for_operand (tree
, stmt_vec_info
, tree
= NULL
);
1622 extern void vect_get_vec_defs (tree
, tree
, stmt_vec_info
, vec
<tree
> *,
1623 vec
<tree
> *, slp_tree
);
1624 extern void vect_get_vec_defs_for_stmt_copy (vec_info
*,
1625 vec
<tree
> *, vec
<tree
> *);
1626 extern tree
vect_init_vector (stmt_vec_info
, tree
, tree
,
1627 gimple_stmt_iterator
*);
1628 extern tree
vect_get_vec_def_for_stmt_copy (vec_info
*, tree
);
1629 extern bool vect_transform_stmt (stmt_vec_info
, gimple_stmt_iterator
*,
1630 slp_tree
, slp_instance
);
1631 extern void vect_remove_stores (stmt_vec_info
);
1632 extern opt_result
vect_analyze_stmt (stmt_vec_info
, bool *, slp_tree
,
1633 slp_instance
, stmt_vector_for_cost
*);
1634 extern void vect_get_load_cost (stmt_vec_info
, int, bool,
1635 unsigned int *, unsigned int *,
1636 stmt_vector_for_cost
*,
1637 stmt_vector_for_cost
*, bool);
1638 extern void vect_get_store_cost (stmt_vec_info
, int,
1639 unsigned int *, stmt_vector_for_cost
*);
1640 extern bool vect_supportable_shift (vec_info
*, enum tree_code
, tree
);
1641 extern tree
vect_gen_perm_mask_any (tree
, const vec_perm_indices
&);
1642 extern tree
vect_gen_perm_mask_checked (tree
, const vec_perm_indices
&);
1643 extern void optimize_mask_stores (class loop
*);
1644 extern gcall
*vect_gen_while (tree
, tree
, tree
);
1645 extern tree
vect_gen_while_not (gimple_seq
*, tree
, tree
, tree
);
1646 extern opt_result
vect_get_vector_types_for_stmt (stmt_vec_info
, tree
*,
1648 extern opt_tree
vect_get_mask_type_for_stmt (stmt_vec_info
);
1650 /* In tree-vect-data-refs.c. */
1651 extern bool vect_can_force_dr_alignment_p (const_tree
, poly_uint64
);
1652 extern enum dr_alignment_support vect_supportable_dr_alignment
1653 (dr_vec_info
*, bool);
1654 extern tree
vect_get_smallest_scalar_type (stmt_vec_info
, HOST_WIDE_INT
*,
1656 extern opt_result
vect_analyze_data_ref_dependences (loop_vec_info
, unsigned int *);
1657 extern bool vect_slp_analyze_instance_dependence (slp_instance
);
1658 extern opt_result
vect_enhance_data_refs_alignment (loop_vec_info
);
1659 extern opt_result
vect_analyze_data_refs_alignment (loop_vec_info
);
1660 extern opt_result
vect_verify_datarefs_alignment (loop_vec_info
);
1661 extern bool vect_slp_analyze_and_verify_instance_alignment (slp_instance
);
1662 extern opt_result
vect_analyze_data_ref_accesses (vec_info
*);
1663 extern opt_result
vect_prune_runtime_alias_test_list (loop_vec_info
);
1664 extern bool vect_gather_scatter_fn_p (bool, bool, tree
, tree
, unsigned int,
1665 signop
, int, internal_fn
*, tree
*);
1666 extern bool vect_check_gather_scatter (stmt_vec_info
, loop_vec_info
,
1667 gather_scatter_info
*);
1668 extern opt_result
vect_find_stmt_data_reference (loop_p
, gimple
*,
1669 vec
<data_reference_p
> *);
1670 extern opt_result
vect_analyze_data_refs (vec_info
*, poly_uint64
*, bool *);
1671 extern void vect_record_base_alignments (vec_info
*);
1672 extern tree
vect_create_data_ref_ptr (stmt_vec_info
, tree
, class loop
*, tree
,
1673 tree
*, gimple_stmt_iterator
*,
1675 tree
= NULL_TREE
, tree
= NULL_TREE
);
1676 extern tree
bump_vector_ptr (tree
, gimple
*, gimple_stmt_iterator
*,
1677 stmt_vec_info
, tree
);
1678 extern void vect_copy_ref_info (tree
, tree
);
1679 extern tree
vect_create_destination_var (tree
, tree
);
1680 extern bool vect_grouped_store_supported (tree
, unsigned HOST_WIDE_INT
);
1681 extern bool vect_store_lanes_supported (tree
, unsigned HOST_WIDE_INT
, bool);
1682 extern bool vect_grouped_load_supported (tree
, bool, unsigned HOST_WIDE_INT
);
1683 extern bool vect_load_lanes_supported (tree
, unsigned HOST_WIDE_INT
, bool);
1684 extern void vect_permute_store_chain (vec
<tree
> ,unsigned int, stmt_vec_info
,
1685 gimple_stmt_iterator
*, vec
<tree
> *);
1686 extern tree
vect_setup_realignment (stmt_vec_info
, gimple_stmt_iterator
*,
1687 tree
*, enum dr_alignment_support
, tree
,
1689 extern void vect_transform_grouped_load (stmt_vec_info
, vec
<tree
> , int,
1690 gimple_stmt_iterator
*);
1691 extern void vect_record_grouped_load_vectors (stmt_vec_info
, vec
<tree
>);
1692 extern tree
vect_get_new_vect_var (tree
, enum vect_var_kind
, const char *);
1693 extern tree
vect_get_new_ssa_name (tree
, enum vect_var_kind
,
1694 const char * = NULL
);
1695 extern tree
vect_create_addr_base_for_vector_ref (stmt_vec_info
, gimple_seq
*,
1696 tree
, tree
= NULL_TREE
);
1698 /* In tree-vect-loop.c. */
1699 extern widest_int
vect_iv_limit_for_full_masking (loop_vec_info loop_vinfo
);
1700 /* Used in gimple-loop-interchange.c and tree-parloops.c. */
1701 extern bool check_reduction_path (dump_user_location_t
, loop_p
, gphi
*, tree
,
1703 extern bool needs_fold_left_reduction_p (tree
, tree_code
);
1704 /* Drive for loop analysis stage. */
1705 extern opt_loop_vec_info
vect_analyze_loop (class loop
*,
1708 extern tree
vect_build_loop_niters (loop_vec_info
, bool * = NULL
);
1709 extern void vect_gen_vector_loop_niters (loop_vec_info
, tree
, tree
*,
1711 extern tree
vect_halve_mask_nunits (vec_info
*, tree
);
1712 extern tree
vect_double_mask_nunits (vec_info
*, tree
);
1713 extern void vect_record_loop_mask (loop_vec_info
, vec_loop_masks
*,
1714 unsigned int, tree
, tree
);
1715 extern tree
vect_get_loop_mask (gimple_stmt_iterator
*, vec_loop_masks
*,
1716 unsigned int, tree
, unsigned int);
1717 extern stmt_vec_info
info_for_reduction (stmt_vec_info
);
1719 /* Drive for loop transformation stage. */
1720 extern class loop
*vect_transform_loop (loop_vec_info
);
1721 extern opt_loop_vec_info
vect_analyze_loop_form (class loop
*,
1723 extern bool vectorizable_live_operation (stmt_vec_info
, gimple_stmt_iterator
*,
1724 slp_tree
, slp_instance
, int,
1725 bool, stmt_vector_for_cost
*);
1726 extern bool vectorizable_reduction (stmt_vec_info
, slp_tree
, slp_instance
,
1727 stmt_vector_for_cost
*);
1728 extern bool vectorizable_induction (stmt_vec_info
, gimple_stmt_iterator
*,
1729 stmt_vec_info
*, slp_tree
,
1730 stmt_vector_for_cost
*);
1731 extern bool vect_transform_reduction (stmt_vec_info
, gimple_stmt_iterator
*,
1732 stmt_vec_info
*, slp_tree
);
1733 extern bool vect_transform_cycle_phi (stmt_vec_info
, stmt_vec_info
*,
1734 slp_tree
, slp_instance
);
1735 extern bool vectorizable_lc_phi (stmt_vec_info
, stmt_vec_info
*, slp_tree
);
1736 extern bool vect_worthwhile_without_simd_p (vec_info
*, tree_code
);
1737 extern int vect_get_known_peeling_cost (loop_vec_info
, int, int *,
1738 stmt_vector_for_cost
*,
1739 stmt_vector_for_cost
*,
1740 stmt_vector_for_cost
*);
1741 extern tree
cse_and_gimplify_to_preheader (loop_vec_info
, tree
);
1743 /* In tree-vect-slp.c. */
1744 extern void vect_free_slp_instance (slp_instance
, bool);
1745 extern bool vect_transform_slp_perm_load (slp_tree
, vec
<tree
> ,
1746 gimple_stmt_iterator
*, poly_uint64
,
1747 slp_instance
, bool, unsigned *);
1748 extern bool vect_slp_analyze_operations (vec_info
*);
1749 extern void vect_schedule_slp (vec_info
*);
1750 extern opt_result
vect_analyze_slp (vec_info
*, unsigned);
1751 extern bool vect_make_slp_decision (loop_vec_info
);
1752 extern void vect_detect_hybrid_slp (loop_vec_info
);
1753 extern void vect_get_slp_defs (vec
<tree
> , slp_tree
, vec
<vec
<tree
> > *);
1754 extern bool vect_slp_bb (basic_block
);
1755 extern stmt_vec_info
vect_find_last_scalar_stmt_in_slp (slp_tree
);
1756 extern bool is_simple_and_all_uses_invariant (stmt_vec_info
, loop_vec_info
);
1757 extern bool can_duplicate_and_interleave_p (vec_info
*, unsigned int,
1759 unsigned int * = NULL
,
1760 tree
* = NULL
, tree
* = NULL
);
1761 extern void duplicate_and_interleave (vec_info
*, gimple_seq
*, tree
,
1762 vec
<tree
>, unsigned int, vec
<tree
> &);
1763 extern int vect_get_place_in_interleaving_chain (stmt_vec_info
, stmt_vec_info
);
1765 /* In tree-vect-patterns.c. */
1766 /* Pattern recognition functions.
1767 Additional pattern recognition functions can (and will) be added
1769 void vect_pattern_recog (vec_info
*);
1771 /* In tree-vectorizer.c. */
1772 unsigned vectorize_loops (void);
1773 void vect_free_loop_info_assumptions (class loop
*);
1774 gimple
*vect_loop_vectorized_call (class loop
*, gcond
**cond
= NULL
);
1777 #endif /* GCC_TREE_VECTORIZER_H */