2 Copyright (C) 2003-2015 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 #include "tree-data-ref.h"
26 #include "hash-table.h"
28 /* Used for naming of new temporaries. */
35 /* Defines type of operation. */
42 /* Define type of available alignment support. */
43 enum dr_alignment_support
{
44 dr_unaligned_unsupported
,
45 dr_unaligned_supported
,
47 dr_explicit_realign_optimized
,
51 /* Define type of def-use cross-iteration cycle. */
53 vect_uninitialized_def
= 0,
54 vect_constant_def
= 1,
59 vect_double_reduction_def
,
64 #define VECTORIZABLE_CYCLE_DEF(D) (((D) == vect_reduction_def) \
65 || ((D) == vect_double_reduction_def) \
66 || ((D) == vect_nested_cycle))
68 /* Structure to encapsulate information about a group of like
69 instructions to be presented to the target cost model. */
70 typedef struct _stmt_info_for_cost
{
72 enum vect_cost_for_stmt kind
;
78 typedef vec
<stmt_info_for_cost
> stmt_vector_for_cost
;
81 add_stmt_info_to_vec (stmt_vector_for_cost
*stmt_cost_vec
, int count
,
82 enum vect_cost_for_stmt kind
, gimple stmt
, int misalign
)
84 stmt_info_for_cost si
;
88 si
.misalign
= misalign
;
89 stmt_cost_vec
->safe_push (si
);
92 /************************************************************************
94 ************************************************************************/
95 typedef struct _slp_tree
*slp_tree
;
97 /* A computation tree of an SLP instance. Each node corresponds to a group of
98 stmts to be packed in a SIMD stmt. */
100 /* Nodes that contain def-stmts of this node statements operands. */
101 vec
<slp_tree
> children
;
102 /* A group of scalar stmts to be vectorized together. */
104 /* Load permutation relative to the stores, NULL if there is no
106 vec
<unsigned> load_permutation
;
107 /* Vectorized stmt/s. */
108 vec
<gimple
> vec_stmts
;
109 /* Number of vector stmts that are created to replace the group of scalar
110 stmts. It is calculated during the transformation phase as the number of
111 scalar elements in one scalar iteration (GROUP_SIZE) multiplied by VF
112 divided by vector size. */
113 unsigned int vec_stmts_size
;
114 /* Whether the scalar computations use two different operators. */
119 /* SLP instance is a sequence of stmts in a loop that can be packed into
121 typedef struct _slp_instance
{
122 /* The root of SLP tree. */
125 /* Size of groups of scalar stmts that will be replaced by SIMD stmt/s. */
126 unsigned int group_size
;
128 /* The unrolling factor required to vectorized this SLP instance. */
129 unsigned int unrolling_factor
;
131 /* Vectorization costs associated with SLP instance. */
132 stmt_vector_for_cost body_cost_vec
;
134 /* The group of nodes that contain loads of this SLP instance. */
139 /* Access Functions. */
140 #define SLP_INSTANCE_TREE(S) (S)->root
141 #define SLP_INSTANCE_GROUP_SIZE(S) (S)->group_size
142 #define SLP_INSTANCE_UNROLLING_FACTOR(S) (S)->unrolling_factor
143 #define SLP_INSTANCE_BODY_COST_VEC(S) (S)->body_cost_vec
144 #define SLP_INSTANCE_LOADS(S) (S)->loads
146 #define SLP_TREE_CHILDREN(S) (S)->children
147 #define SLP_TREE_SCALAR_STMTS(S) (S)->stmts
148 #define SLP_TREE_VEC_STMTS(S) (S)->vec_stmts
149 #define SLP_TREE_NUMBER_OF_VEC_STMTS(S) (S)->vec_stmts_size
150 #define SLP_TREE_LOAD_PERMUTATION(S) (S)->load_permutation
151 #define SLP_TREE_TWO_OPERATORS(S) (S)->two_operators
153 /* This structure is used in creation of an SLP tree. Each instance
154 corresponds to the same operand in a group of scalar stmts in an SLP
156 typedef struct _slp_oprnd_info
158 /* Def-stmts for the operands. */
159 vec
<gimple
> def_stmts
;
160 /* Information about the first statement, its vector def-type, type, the
161 operand itself in case it's constant, and an indication if it's a pattern
163 enum vect_def_type first_dt
;
170 /* This struct is used to store the information of a data reference,
171 including the data ref itself, the access offset (calculated by summing its
172 offset and init) and the segment length for aliasing checks.
173 This is used to merge alias checks. */
175 struct dr_with_seg_len
177 dr_with_seg_len (data_reference_p d
, tree len
)
179 offset (size_binop (PLUS_EXPR
, DR_OFFSET (d
), DR_INIT (d
))),
187 /* This struct contains two dr_with_seg_len objects with aliasing data
188 refs. Two comparisons are generated from them. */
190 struct dr_with_seg_len_pair_t
192 dr_with_seg_len_pair_t (const dr_with_seg_len
& d1
,
193 const dr_with_seg_len
& d2
)
194 : first (d1
), second (d2
) {}
196 dr_with_seg_len first
;
197 dr_with_seg_len second
;
201 typedef struct _vect_peel_info
204 struct data_reference
*dr
;
208 typedef struct _vect_peel_extended_info
210 struct _vect_peel_info peel_info
;
211 unsigned int inside_cost
;
212 unsigned int outside_cost
;
213 stmt_vector_for_cost body_cost_vec
;
214 } *vect_peel_extended_info
;
217 /* Peeling hashtable helpers. */
219 struct peel_info_hasher
: typed_free_remove
<_vect_peel_info
>
221 typedef _vect_peel_info
*value_type
;
222 typedef _vect_peel_info
*compare_type
;
223 static inline hashval_t
hash (const _vect_peel_info
*);
224 static inline bool equal (const _vect_peel_info
*, const _vect_peel_info
*);
228 peel_info_hasher::hash (const _vect_peel_info
*peel_info
)
230 return (hashval_t
) peel_info
->npeel
;
234 peel_info_hasher::equal (const _vect_peel_info
*a
, const _vect_peel_info
*b
)
236 return (a
->npeel
== b
->npeel
);
240 /*-----------------------------------------------------------------*/
241 /* Info on vectorized loops. */
242 /*-----------------------------------------------------------------*/
243 typedef struct _loop_vec_info
{
245 /* The loop to which this info struct refers to. */
248 /* The loop basic blocks. */
251 /* Number of latch executions. */
253 /* Number of iterations. */
255 /* Number of iterations of the original loop. */
256 tree num_iters_unchanged
;
258 /* Minimum number of iterations below which vectorization is expected to
259 not be profitable (as estimated by the cost model).
260 -1 indicates that vectorization will not be profitable.
261 FORNOW: This field is an int. Will be a tree in the future, to represent
262 values unknown at compile time. */
263 int min_profitable_iters
;
265 /* Threshold of number of iterations below which vectorzation will not be
266 performed. It is calculated from MIN_PROFITABLE_ITERS and
267 PARAM_MIN_VECT_LOOP_BOUND. */
270 /* Is the loop vectorizable? */
273 /* Unrolling factor */
274 int vectorization_factor
;
276 /* Unknown DRs according to which loop was peeled. */
277 struct data_reference
*unaligned_dr
;
279 /* peeling_for_alignment indicates whether peeling for alignment will take
280 place, and what the peeling factor should be:
281 peeling_for_alignment = X means:
282 If X=0: Peeling for alignment will not be applied.
283 If X>0: Peel first X iterations.
284 If X=-1: Generate a runtime test to calculate the number of iterations
285 to be peeled, using the dataref recorded in the field
287 int peeling_for_alignment
;
289 /* The mask used to check the alignment of pointers or arrays. */
292 /* The loop nest in which the data dependences are computed. */
293 vec
<loop_p
> loop_nest
;
295 /* All data references in the loop. */
296 vec
<data_reference_p
> datarefs
;
298 /* All data dependences in the loop. */
301 /* Data Dependence Relations defining address ranges that are candidates
302 for a run-time aliasing check. */
303 vec
<ddr_p
> may_alias_ddrs
;
305 /* Data Dependence Relations defining address ranges together with segment
306 lengths from which the run-time aliasing check is built. */
307 vec
<dr_with_seg_len_pair_t
> comp_alias_ddrs
;
309 /* Statements in the loop that have data references that are candidates for a
310 runtime (loop versioning) misalignment check. */
311 vec
<gimple
> may_misalign_stmts
;
313 /* All interleaving chains of stores in the loop, represented by the first
314 stmt in the chain. */
315 vec
<gimple
> grouped_stores
;
317 /* All SLP instances in the loop. This is a subset of the set of GROUP_STORES
319 vec
<slp_instance
> slp_instances
;
321 /* The unrolling factor needed to SLP the loop. In case of that pure SLP is
322 applied to the loop, i.e., no unrolling is needed, this is 1. */
323 unsigned slp_unrolling_factor
;
325 /* Reduction cycles detected in the loop. Used in loop-aware SLP. */
326 vec
<gimple
> reductions
;
328 /* All reduction chains in the loop, represented by the first
329 stmt in the chain. */
330 vec
<gimple
> reduction_chains
;
332 /* Hash table used to choose the best peeling option. */
333 hash_table
<peel_info_hasher
> *peeling_htab
;
335 /* Cost data used by the target cost model. */
336 void *target_cost_data
;
338 /* When we have grouped data accesses with gaps, we may introduce invalid
339 memory accesses. We peel the last iteration of the loop to prevent
341 bool peeling_for_gaps
;
343 /* When the number of iterations is not a multiple of the vector size
344 we need to peel off iterations at the end to form an epilogue loop. */
345 bool peeling_for_niter
;
347 /* Reductions are canonicalized so that the last operand is the reduction
348 operand. If this places a constant into RHS1, this decanonicalizes
349 GIMPLE for other phases, so we must track when this has occurred and
351 bool operands_swapped
;
353 /* True if there are no loop carried data dependencies in the loop.
354 If loop->safelen <= 1, then this is always true, either the loop
355 didn't have any loop carried data dependencies, or the loop is being
356 vectorized guarded with some runtime alias checks, or couldn't
357 be vectorized at all, but then this field shouldn't be used.
358 For loop->safelen >= 2, the user has asserted that there are no
359 backward dependencies, but there still could be loop carried forward
360 dependencies in such loops. This flag will be false if normal
361 vectorizer data dependency analysis would fail or require versioning
362 for alias, but because of loop->safelen >= 2 it has been vectorized
363 even without versioning for alias. E.g. in:
365 for (int i = 0; i < m; i++)
367 (or #pragma simd or #pragma ivdep) we can vectorize this and it will
368 DTRT even for k > 0 && k < m, but without safelen we would not
369 vectorize this, so this field would be false. */
370 bool no_data_dependencies
;
372 /* If if-conversion versioned this loop before conversion, this is the
373 loop version without if-conversion. */
374 struct loop
*scalar_loop
;
378 /* Access Functions. */
379 #define LOOP_VINFO_LOOP(L) (L)->loop
380 #define LOOP_VINFO_BBS(L) (L)->bbs
381 #define LOOP_VINFO_NITERSM1(L) (L)->num_itersm1
382 #define LOOP_VINFO_NITERS(L) (L)->num_iters
383 /* Since LOOP_VINFO_NITERS and LOOP_VINFO_NITERSM1 can change after
384 prologue peeling retain total unchanged scalar loop iterations for
386 #define LOOP_VINFO_NITERS_UNCHANGED(L) (L)->num_iters_unchanged
387 #define LOOP_VINFO_COST_MODEL_MIN_ITERS(L) (L)->min_profitable_iters
388 #define LOOP_VINFO_COST_MODEL_THRESHOLD(L) (L)->th
389 #define LOOP_VINFO_VECTORIZABLE_P(L) (L)->vectorizable
390 #define LOOP_VINFO_VECT_FACTOR(L) (L)->vectorization_factor
391 #define LOOP_VINFO_PTR_MASK(L) (L)->ptr_mask
392 #define LOOP_VINFO_LOOP_NEST(L) (L)->loop_nest
393 #define LOOP_VINFO_DATAREFS(L) (L)->datarefs
394 #define LOOP_VINFO_DDRS(L) (L)->ddrs
395 #define LOOP_VINFO_INT_NITERS(L) (TREE_INT_CST_LOW ((L)->num_iters))
396 #define LOOP_VINFO_PEELING_FOR_ALIGNMENT(L) (L)->peeling_for_alignment
397 #define LOOP_VINFO_UNALIGNED_DR(L) (L)->unaligned_dr
398 #define LOOP_VINFO_MAY_MISALIGN_STMTS(L) (L)->may_misalign_stmts
399 #define LOOP_VINFO_MAY_ALIAS_DDRS(L) (L)->may_alias_ddrs
400 #define LOOP_VINFO_COMP_ALIAS_DDRS(L) (L)->comp_alias_ddrs
401 #define LOOP_VINFO_GROUPED_STORES(L) (L)->grouped_stores
402 #define LOOP_VINFO_SLP_INSTANCES(L) (L)->slp_instances
403 #define LOOP_VINFO_SLP_UNROLLING_FACTOR(L) (L)->slp_unrolling_factor
404 #define LOOP_VINFO_REDUCTIONS(L) (L)->reductions
405 #define LOOP_VINFO_REDUCTION_CHAINS(L) (L)->reduction_chains
406 #define LOOP_VINFO_PEELING_HTAB(L) (L)->peeling_htab
407 #define LOOP_VINFO_TARGET_COST_DATA(L) (L)->target_cost_data
408 #define LOOP_VINFO_PEELING_FOR_GAPS(L) (L)->peeling_for_gaps
409 #define LOOP_VINFO_OPERANDS_SWAPPED(L) (L)->operands_swapped
410 #define LOOP_VINFO_PEELING_FOR_NITER(L) (L)->peeling_for_niter
411 #define LOOP_VINFO_NO_DATA_DEPENDENCIES(L) (L)->no_data_dependencies
412 #define LOOP_VINFO_SCALAR_LOOP(L) (L)->scalar_loop
414 #define LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT(L) \
415 ((L)->may_misalign_stmts.length () > 0)
416 #define LOOP_REQUIRES_VERSIONING_FOR_ALIAS(L) \
417 ((L)->may_alias_ddrs.length () > 0)
419 #define LOOP_VINFO_NITERS_KNOWN_P(L) \
420 (tree_fits_shwi_p ((L)->num_iters) && tree_to_shwi ((L)->num_iters) > 0)
422 static inline loop_vec_info
423 loop_vec_info_for_loop (struct loop
*loop
)
425 return (loop_vec_info
) loop
->aux
;
429 nested_in_vect_loop_p (struct loop
*loop
, gimple stmt
)
432 && (loop
->inner
== (gimple_bb (stmt
))->loop_father
));
435 typedef struct _bb_vec_info
{
438 /* All interleaving chains of stores in the basic block, represented by the
439 first stmt in the chain. */
440 vec
<gimple
> grouped_stores
;
442 /* All SLP instances in the basic block. This is a subset of the set of
443 GROUP_STORES of the basic block. */
444 vec
<slp_instance
> slp_instances
;
446 /* All data references in the basic block. */
447 vec
<data_reference_p
> datarefs
;
449 /* All data dependences in the basic block. */
452 /* Cost data used by the target cost model. */
453 void *target_cost_data
;
457 #define BB_VINFO_BB(B) (B)->bb
458 #define BB_VINFO_GROUPED_STORES(B) (B)->grouped_stores
459 #define BB_VINFO_SLP_INSTANCES(B) (B)->slp_instances
460 #define BB_VINFO_DATAREFS(B) (B)->datarefs
461 #define BB_VINFO_DDRS(B) (B)->ddrs
462 #define BB_VINFO_TARGET_COST_DATA(B) (B)->target_cost_data
464 static inline bb_vec_info
465 vec_info_for_bb (basic_block bb
)
467 return (bb_vec_info
) bb
->aux
;
470 /*-----------------------------------------------------------------*/
471 /* Info on vectorized defs. */
472 /*-----------------------------------------------------------------*/
473 enum stmt_vec_info_type
{
474 undef_vec_info_type
= 0,
480 call_simd_clone_vec_info_type
,
481 assignment_vec_info_type
,
482 condition_vec_info_type
,
485 type_promotion_vec_info_type
,
486 type_demotion_vec_info_type
,
487 type_conversion_vec_info_type
,
488 loop_exit_ctrl_vec_info_type
491 /* Indicates whether/how a variable is used in the scope of loop/basic
494 vect_unused_in_scope
= 0,
495 /* The def is in the inner loop, and the use is in the outer loop, and the
496 use is a reduction stmt. */
497 vect_used_in_outer_by_reduction
,
498 /* The def is in the inner loop, and the use is in the outer loop (and is
499 not part of reduction). */
502 /* defs that feed computations that end up (only) in a reduction. These
503 defs may be used by non-reduction stmts, but eventually, any
504 computations/values that are affected by these defs are used to compute
505 a reduction (i.e. don't get stored to memory, for example). We use this
506 to identify computations that we can change the order in which they are
508 vect_used_by_reduction
,
513 /* The type of vectorization that can be applied to the stmt: regular loop-based
514 vectorization; pure SLP - the stmt is a part of SLP instances and does not
515 have uses outside SLP instances; or hybrid SLP and loop-based - the stmt is
516 a part of SLP instance and also must be loop-based vectorized, since it has
517 uses outside SLP sequences.
519 In the loop context the meanings of pure and hybrid SLP are slightly
520 different. By saying that pure SLP is applied to the loop, we mean that we
521 exploit only intra-iteration parallelism in the loop; i.e., the loop can be
522 vectorized without doing any conceptual unrolling, cause we don't pack
523 together stmts from different iterations, only within a single iteration.
524 Loop hybrid SLP means that we exploit both intra-iteration and
525 inter-iteration parallelism (e.g., number of elements in the vector is 4
526 and the slp-group-size is 2, in which case we don't have enough parallelism
527 within an iteration, so we obtain the rest of the parallelism from subsequent
528 iterations by unrolling the loop by 2). */
536 typedef struct data_reference
*dr_p
;
538 typedef struct _stmt_vec_info
{
540 enum stmt_vec_info_type type
;
542 /* Indicates whether this stmts is part of a computation whose result is
543 used outside the loop. */
546 /* Stmt is part of some pattern (computation idiom) */
549 /* The stmt to which this info struct refers to. */
552 /* The loop_vec_info with respect to which STMT is vectorized. */
553 loop_vec_info loop_vinfo
;
555 /* The vector type to be used for the LHS of this statement. */
558 /* The vectorized version of the stmt. */
559 gimple vectorized_stmt
;
562 /** The following is relevant only for stmts that contain a non-scalar
563 data-ref (array/pointer/struct access). A GIMPLE stmt is expected to have
564 at most one such data-ref. **/
566 /* Information about the data-ref (access function, etc),
567 relative to the inner-most containing loop. */
568 struct data_reference
*data_ref_info
;
570 /* Information about the data-ref relative to this loop
571 nest (the loop that is being considered for vectorization). */
572 tree dr_base_address
;
578 /* For loop PHI nodes, the evolution part of it. This makes sure
579 this information is still available in vect_update_ivs_after_vectorizer
580 where we may not be able to re-analyze the PHI nodes evolution as
581 peeling for the prologue loop can make it unanalyzable. The evolution
582 part is still correct though. */
583 tree loop_phi_evolution_part
;
585 /* Used for various bookkeeping purposes, generally holding a pointer to
586 some other stmt S that is in some way "related" to this stmt.
587 Current use of this field is:
588 If this stmt is part of a pattern (i.e. the field 'in_pattern_p' is
589 true): S is the "pattern stmt" that represents (and replaces) the
590 sequence of stmts that constitutes the pattern. Similarly, the
591 related_stmt of the "pattern stmt" points back to this stmt (which is
592 the last stmt in the original sequence of stmts that constitutes the
596 /* Used to keep a sequence of def stmts of a pattern stmt if such exists. */
597 gimple_seq pattern_def_seq
;
599 /* List of datarefs that are known to have the same alignment as the dataref
601 vec
<dr_p
> same_align_refs
;
603 /* Selected SIMD clone's function info. First vector element
604 is SIMD clone's function decl, followed by a pair of trees (base + step)
605 for linear arguments (pair of NULLs for other arguments). */
606 vec
<tree
> simd_clone_info
;
608 /* Classify the def of this stmt. */
609 enum vect_def_type def_type
;
611 /* Whether the stmt is SLPed, loop-based vectorized, or both. */
612 enum slp_vect_type slp_type
;
614 /* Interleaving and reduction chains info. */
615 /* First element in the group. */
616 gimple first_element
;
617 /* Pointer to the next element in the group. */
619 /* For data-refs, in case that two or more stmts share data-ref, this is the
620 pointer to the previously detected stmt with the same dr. */
622 /* The size of the group. */
624 /* For stores, number of stores from this group seen. We vectorize the last
626 unsigned int store_count
;
627 /* For loads only, the gap from the previous load. For consecutive loads, GAP
631 /* The minimum negative dependence distance this stmt participates in
633 unsigned int min_neg_dist
;
635 /* Not all stmts in the loop need to be vectorized. e.g, the increment
636 of the loop induction variable and computation of array indexes. relevant
637 indicates whether the stmt needs to be vectorized. */
638 enum vect_relevant relevant
;
640 /* The bb_vec_info with respect to which STMT is vectorized. */
641 bb_vec_info bb_vinfo
;
643 /* Is this statement vectorizable or should it be skipped in (partial)
647 /* For loads only, true if this is a gather load. */
650 /* True if this is an access with loop-invariant stride. */
653 /* For both loads and stores. */
654 bool simd_lane_access_p
;
657 /* Access Functions. */
658 #define STMT_VINFO_TYPE(S) (S)->type
659 #define STMT_VINFO_STMT(S) (S)->stmt
660 #define STMT_VINFO_LOOP_VINFO(S) (S)->loop_vinfo
661 #define STMT_VINFO_BB_VINFO(S) (S)->bb_vinfo
662 #define STMT_VINFO_RELEVANT(S) (S)->relevant
663 #define STMT_VINFO_LIVE_P(S) (S)->live
664 #define STMT_VINFO_VECTYPE(S) (S)->vectype
665 #define STMT_VINFO_VEC_STMT(S) (S)->vectorized_stmt
666 #define STMT_VINFO_VECTORIZABLE(S) (S)->vectorizable
667 #define STMT_VINFO_DATA_REF(S) (S)->data_ref_info
668 #define STMT_VINFO_GATHER_P(S) (S)->gather_p
669 #define STMT_VINFO_STRIDED_P(S) (S)->strided_p
670 #define STMT_VINFO_SIMD_LANE_ACCESS_P(S) (S)->simd_lane_access_p
672 #define STMT_VINFO_DR_BASE_ADDRESS(S) (S)->dr_base_address
673 #define STMT_VINFO_DR_INIT(S) (S)->dr_init
674 #define STMT_VINFO_DR_OFFSET(S) (S)->dr_offset
675 #define STMT_VINFO_DR_STEP(S) (S)->dr_step
676 #define STMT_VINFO_DR_ALIGNED_TO(S) (S)->dr_aligned_to
678 #define STMT_VINFO_IN_PATTERN_P(S) (S)->in_pattern_p
679 #define STMT_VINFO_RELATED_STMT(S) (S)->related_stmt
680 #define STMT_VINFO_PATTERN_DEF_SEQ(S) (S)->pattern_def_seq
681 #define STMT_VINFO_SAME_ALIGN_REFS(S) (S)->same_align_refs
682 #define STMT_VINFO_SIMD_CLONE_INFO(S) (S)->simd_clone_info
683 #define STMT_VINFO_DEF_TYPE(S) (S)->def_type
684 #define STMT_VINFO_GROUP_FIRST_ELEMENT(S) (S)->first_element
685 #define STMT_VINFO_GROUP_NEXT_ELEMENT(S) (S)->next_element
686 #define STMT_VINFO_GROUP_SIZE(S) (S)->size
687 #define STMT_VINFO_GROUP_STORE_COUNT(S) (S)->store_count
688 #define STMT_VINFO_GROUP_GAP(S) (S)->gap
689 #define STMT_VINFO_GROUP_SAME_DR_STMT(S) (S)->same_dr_stmt
690 #define STMT_VINFO_GROUPED_ACCESS(S) ((S)->first_element != NULL && (S)->data_ref_info)
691 #define STMT_VINFO_LOOP_PHI_EVOLUTION_PART(S) (S)->loop_phi_evolution_part
692 #define STMT_VINFO_MIN_NEG_DIST(S) (S)->min_neg_dist
694 #define GROUP_FIRST_ELEMENT(S) (S)->first_element
695 #define GROUP_NEXT_ELEMENT(S) (S)->next_element
696 #define GROUP_SIZE(S) (S)->size
697 #define GROUP_STORE_COUNT(S) (S)->store_count
698 #define GROUP_GAP(S) (S)->gap
699 #define GROUP_SAME_DR_STMT(S) (S)->same_dr_stmt
701 #define STMT_VINFO_RELEVANT_P(S) ((S)->relevant != vect_unused_in_scope)
703 #define HYBRID_SLP_STMT(S) ((S)->slp_type == hybrid)
704 #define PURE_SLP_STMT(S) ((S)->slp_type == pure_slp)
705 #define STMT_SLP_TYPE(S) (S)->slp_type
709 bool base_misaligned
;
713 #define VECT_MAX_COST 1000
715 /* The maximum number of intermediate steps required in multi-step type
717 #define MAX_INTERM_CVT_STEPS 3
719 /* The maximum vectorization factor supported by any target (V64QI). */
720 #define MAX_VECTORIZATION_FACTOR 64
722 /* Avoid GTY(()) on stmt_vec_info. */
723 typedef void *vec_void_p
;
725 extern vec
<vec_void_p
> stmt_vec_info_vec
;
727 void init_stmt_vec_info_vec (void);
728 void free_stmt_vec_info_vec (void);
730 /* Return a stmt_vec_info corresponding to STMT. */
732 static inline stmt_vec_info
733 vinfo_for_stmt (gimple stmt
)
735 unsigned int uid
= gimple_uid (stmt
);
739 return (stmt_vec_info
) stmt_vec_info_vec
[uid
- 1];
742 /* Set vectorizer information INFO for STMT. */
745 set_vinfo_for_stmt (gimple stmt
, stmt_vec_info info
)
747 unsigned int uid
= gimple_uid (stmt
);
750 gcc_checking_assert (info
);
751 uid
= stmt_vec_info_vec
.length () + 1;
752 gimple_set_uid (stmt
, uid
);
753 stmt_vec_info_vec
.safe_push ((vec_void_p
) info
);
756 stmt_vec_info_vec
[uid
- 1] = (vec_void_p
) info
;
759 /* Return the earlier statement between STMT1 and STMT2. */
762 get_earlier_stmt (gimple stmt1
, gimple stmt2
)
764 unsigned int uid1
, uid2
;
772 uid1
= gimple_uid (stmt1
);
773 uid2
= gimple_uid (stmt2
);
775 if (uid1
== 0 || uid2
== 0)
778 gcc_checking_assert (uid1
<= stmt_vec_info_vec
.length ()
779 && uid2
<= stmt_vec_info_vec
.length ());
787 /* Return the later statement between STMT1 and STMT2. */
790 get_later_stmt (gimple stmt1
, gimple stmt2
)
792 unsigned int uid1
, uid2
;
800 uid1
= gimple_uid (stmt1
);
801 uid2
= gimple_uid (stmt2
);
803 if (uid1
== 0 || uid2
== 0)
806 gcc_assert (uid1
<= stmt_vec_info_vec
.length ());
807 gcc_assert (uid2
<= stmt_vec_info_vec
.length ());
815 /* Return TRUE if a statement represented by STMT_INFO is a part of a
819 is_pattern_stmt_p (stmt_vec_info stmt_info
)
822 stmt_vec_info related_stmt_info
;
824 related_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
826 && (related_stmt_info
= vinfo_for_stmt (related_stmt
))
827 && STMT_VINFO_IN_PATTERN_P (related_stmt_info
))
833 /* Return true if BB is a loop header. */
836 is_loop_header_bb_p (basic_block bb
)
838 if (bb
== (bb
->loop_father
)->header
)
840 gcc_checking_assert (EDGE_COUNT (bb
->preds
) == 1);
844 /* Return pow2 (X). */
851 for (i
= 0; i
< x
; i
++)
857 /* Alias targetm.vectorize.builtin_vectorization_cost. */
860 builtin_vectorization_cost (enum vect_cost_for_stmt type_of_cost
,
861 tree vectype
, int misalign
)
863 return targetm
.vectorize
.builtin_vectorization_cost (type_of_cost
,
867 /* Get cost by calling cost target builtin. */
870 int vect_get_stmt_cost (enum vect_cost_for_stmt type_of_cost
)
872 return builtin_vectorization_cost (type_of_cost
, NULL
, 0);
875 /* Alias targetm.vectorize.init_cost. */
878 init_cost (struct loop
*loop_info
)
880 return targetm
.vectorize
.init_cost (loop_info
);
883 /* Alias targetm.vectorize.add_stmt_cost. */
885 static inline unsigned
886 add_stmt_cost (void *data
, int count
, enum vect_cost_for_stmt kind
,
887 stmt_vec_info stmt_info
, int misalign
,
888 enum vect_cost_model_location where
)
890 return targetm
.vectorize
.add_stmt_cost (data
, count
, kind
,
891 stmt_info
, misalign
, where
);
894 /* Alias targetm.vectorize.finish_cost. */
897 finish_cost (void *data
, unsigned *prologue_cost
,
898 unsigned *body_cost
, unsigned *epilogue_cost
)
900 targetm
.vectorize
.finish_cost (data
, prologue_cost
, body_cost
, epilogue_cost
);
903 /* Alias targetm.vectorize.destroy_cost_data. */
906 destroy_cost_data (void *data
)
908 targetm
.vectorize
.destroy_cost_data (data
);
912 /*-----------------------------------------------------------------*/
913 /* Info on data references alignment. */
914 /*-----------------------------------------------------------------*/
916 set_dr_misalignment (struct data_reference
*dr
, int val
)
918 dataref_aux
*data_aux
= (dataref_aux
*) dr
->aux
;
922 data_aux
= XCNEW (dataref_aux
);
926 data_aux
->misalignment
= val
;
930 dr_misalignment (struct data_reference
*dr
)
932 gcc_assert (dr
->aux
);
933 return ((dataref_aux
*) dr
->aux
)->misalignment
;
936 /* Reflects actual alignment of first access in the vectorized loop,
937 taking into account peeling/versioning if applied. */
938 #define DR_MISALIGNMENT(DR) dr_misalignment (DR)
939 #define SET_DR_MISALIGNMENT(DR, VAL) set_dr_misalignment (DR, VAL)
941 /* Return TRUE if the data access is aligned, and FALSE otherwise. */
944 aligned_access_p (struct data_reference
*data_ref_info
)
946 return (DR_MISALIGNMENT (data_ref_info
) == 0);
949 /* Return TRUE if the alignment of the data access is known, and FALSE
953 known_alignment_for_access_p (struct data_reference
*data_ref_info
)
955 return (DR_MISALIGNMENT (data_ref_info
) != -1);
959 /* Return true if the vect cost model is unlimited. */
961 unlimited_cost_model (loop_p loop
)
963 if (loop
!= NULL
&& loop
->force_vectorize
964 && flag_simd_cost_model
!= VECT_COST_MODEL_DEFAULT
)
965 return flag_simd_cost_model
== VECT_COST_MODEL_UNLIMITED
;
966 return (flag_vect_cost_model
== VECT_COST_MODEL_UNLIMITED
);
969 /* Source location */
970 extern source_location vect_location
;
972 /*-----------------------------------------------------------------*/
973 /* Function prototypes. */
974 /*-----------------------------------------------------------------*/
976 /* Simple loop peeling and versioning utilities for vectorizer's purposes -
977 in tree-vect-loop-manip.c. */
978 extern void slpeel_make_loop_iterate_ntimes (struct loop
*, tree
);
979 extern bool slpeel_can_duplicate_loop_p (const struct loop
*, const_edge
);
980 struct loop
*slpeel_tree_duplicate_loop_to_edge_cfg (struct loop
*,
981 struct loop
*, edge
);
982 extern void vect_loop_versioning (loop_vec_info
, unsigned int, bool);
983 extern void vect_do_peeling_for_loop_bound (loop_vec_info
, tree
, tree
,
985 extern void vect_do_peeling_for_alignment (loop_vec_info
, tree
,
987 extern source_location
find_loop_location (struct loop
*);
988 extern bool vect_can_advance_ivs_p (loop_vec_info
);
990 /* In tree-vect-stmts.c. */
991 extern unsigned int current_vector_size
;
992 extern tree
get_vectype_for_scalar_type (tree
);
993 extern tree
get_same_sized_vectype (tree
, tree
);
994 extern bool vect_is_simple_use (tree
, gimple
, loop_vec_info
,
995 bb_vec_info
, gimple
*,
996 tree
*, enum vect_def_type
*);
997 extern bool vect_is_simple_use_1 (tree
, gimple
, loop_vec_info
,
998 bb_vec_info
, gimple
*,
999 tree
*, enum vect_def_type
*, tree
*);
1000 extern bool supportable_widening_operation (enum tree_code
, gimple
, tree
, tree
,
1001 enum tree_code
*, enum tree_code
*,
1002 int *, vec
<tree
> *);
1003 extern bool supportable_narrowing_operation (enum tree_code
, tree
, tree
,
1005 int *, vec
<tree
> *);
1006 extern stmt_vec_info
new_stmt_vec_info (gimple stmt
, loop_vec_info
,
1008 extern void free_stmt_vec_info (gimple stmt
);
1009 extern tree
vectorizable_function (gcall
*, tree
, tree
);
1010 extern void vect_model_simple_cost (stmt_vec_info
, int, enum vect_def_type
*,
1011 stmt_vector_for_cost
*,
1012 stmt_vector_for_cost
*);
1013 extern void vect_model_store_cost (stmt_vec_info
, int, bool,
1014 enum vect_def_type
, slp_tree
,
1015 stmt_vector_for_cost
*,
1016 stmt_vector_for_cost
*);
1017 extern void vect_model_load_cost (stmt_vec_info
, int, bool, slp_tree
,
1018 stmt_vector_for_cost
*,
1019 stmt_vector_for_cost
*);
1020 extern unsigned record_stmt_cost (stmt_vector_for_cost
*, int,
1021 enum vect_cost_for_stmt
, stmt_vec_info
,
1022 int, enum vect_cost_model_location
);
1023 extern void vect_finish_stmt_generation (gimple
, gimple
,
1024 gimple_stmt_iterator
*);
1025 extern bool vect_mark_stmts_to_be_vectorized (loop_vec_info
);
1026 extern tree
vect_get_vec_def_for_operand (tree
, gimple
, tree
*);
1027 extern tree
vect_init_vector (gimple
, tree
, tree
,
1028 gimple_stmt_iterator
*);
1029 extern tree
vect_get_vec_def_for_stmt_copy (enum vect_def_type
, tree
);
1030 extern bool vect_transform_stmt (gimple
, gimple_stmt_iterator
*,
1031 bool *, slp_tree
, slp_instance
);
1032 extern void vect_remove_stores (gimple
);
1033 extern bool vect_analyze_stmt (gimple
, bool *, slp_tree
);
1034 extern bool vectorizable_condition (gimple
, gimple_stmt_iterator
*, gimple
*,
1035 tree
, int, slp_tree
);
1036 extern void vect_get_load_cost (struct data_reference
*, int, bool,
1037 unsigned int *, unsigned int *,
1038 stmt_vector_for_cost
*,
1039 stmt_vector_for_cost
*, bool);
1040 extern void vect_get_store_cost (struct data_reference
*, int,
1041 unsigned int *, stmt_vector_for_cost
*);
1042 extern bool vect_supportable_shift (enum tree_code
, tree
);
1043 extern void vect_get_vec_defs (tree
, tree
, gimple
, vec
<tree
> *,
1044 vec
<tree
> *, slp_tree
, int);
1045 extern tree
vect_gen_perm_mask_any (tree
, const unsigned char *);
1046 extern tree
vect_gen_perm_mask_checked (tree
, const unsigned char *);
1048 /* In tree-vect-data-refs.c. */
1049 extern bool vect_can_force_dr_alignment_p (const_tree
, unsigned int);
1050 extern enum dr_alignment_support vect_supportable_dr_alignment
1051 (struct data_reference
*, bool);
1052 extern tree
vect_get_smallest_scalar_type (gimple
, HOST_WIDE_INT
*,
1054 extern bool vect_analyze_data_ref_dependences (loop_vec_info
, int *);
1055 extern bool vect_slp_analyze_data_ref_dependences (bb_vec_info
);
1056 extern bool vect_enhance_data_refs_alignment (loop_vec_info
);
1057 extern bool vect_analyze_data_refs_alignment (loop_vec_info
, bb_vec_info
);
1058 extern bool vect_verify_datarefs_alignment (loop_vec_info
, bb_vec_info
);
1059 extern bool vect_analyze_data_ref_accesses (loop_vec_info
, bb_vec_info
);
1060 extern bool vect_prune_runtime_alias_test_list (loop_vec_info
);
1061 extern tree
vect_check_gather (gimple
, loop_vec_info
, tree
*, tree
*,
1063 extern bool vect_analyze_data_refs (loop_vec_info
, bb_vec_info
, int *,
1065 extern tree
vect_create_data_ref_ptr (gimple
, tree
, struct loop
*, tree
,
1066 tree
*, gimple_stmt_iterator
*,
1067 gimple
*, bool, bool *,
1069 extern tree
bump_vector_ptr (tree
, gimple
, gimple_stmt_iterator
*, gimple
, tree
);
1070 extern tree
vect_create_destination_var (tree
, tree
);
1071 extern bool vect_grouped_store_supported (tree
, unsigned HOST_WIDE_INT
);
1072 extern bool vect_store_lanes_supported (tree
, unsigned HOST_WIDE_INT
);
1073 extern bool vect_grouped_load_supported (tree
, unsigned HOST_WIDE_INT
);
1074 extern bool vect_load_lanes_supported (tree
, unsigned HOST_WIDE_INT
);
1075 extern void vect_permute_store_chain (vec
<tree
> ,unsigned int, gimple
,
1076 gimple_stmt_iterator
*, vec
<tree
> *);
1077 extern tree
vect_setup_realignment (gimple
, gimple_stmt_iterator
*, tree
*,
1078 enum dr_alignment_support
, tree
,
1080 extern void vect_transform_grouped_load (gimple
, vec
<tree
> , int,
1081 gimple_stmt_iterator
*);
1082 extern void vect_record_grouped_load_vectors (gimple
, vec
<tree
> );
1083 extern tree
vect_get_new_vect_var (tree
, enum vect_var_kind
, const char *);
1084 extern tree
vect_create_addr_base_for_vector_ref (gimple
, gimple_seq
*,
1085 tree
, struct loop
*,
1088 /* In tree-vect-loop.c. */
1089 /* FORNOW: Used in tree-parloops.c. */
1090 extern void destroy_loop_vec_info (loop_vec_info
, bool);
1091 extern gimple
vect_force_simple_reduction (loop_vec_info
, gimple
, bool, bool *);
1092 /* Drive for loop analysis stage. */
1093 extern loop_vec_info
vect_analyze_loop (struct loop
*);
1094 /* Drive for loop transformation stage. */
1095 extern void vect_transform_loop (loop_vec_info
);
1096 extern loop_vec_info
vect_analyze_loop_form (struct loop
*);
1097 extern bool vectorizable_live_operation (gimple
, gimple_stmt_iterator
*,
1099 extern bool vectorizable_reduction (gimple
, gimple_stmt_iterator
*, gimple
*,
1101 extern bool vectorizable_induction (gimple
, gimple_stmt_iterator
*, gimple
*);
1102 extern tree
get_initial_def_for_reduction (gimple
, tree
, tree
*);
1103 extern int vect_min_worthwhile_factor (enum tree_code
);
1104 extern int vect_get_known_peeling_cost (loop_vec_info
, int, int *,
1105 stmt_vector_for_cost
*,
1106 stmt_vector_for_cost
*,
1107 stmt_vector_for_cost
*);
1108 extern int vect_get_single_scalar_iteration_cost (loop_vec_info
,
1109 stmt_vector_for_cost
*);
1111 /* In tree-vect-slp.c. */
1112 extern void vect_free_slp_instance (slp_instance
);
1113 extern bool vect_transform_slp_perm_load (slp_tree
, vec
<tree
> ,
1114 gimple_stmt_iterator
*, int,
1115 slp_instance
, bool);
1116 extern bool vect_schedule_slp (loop_vec_info
, bb_vec_info
);
1117 extern void vect_update_slp_costs_according_to_vf (loop_vec_info
);
1118 extern bool vect_analyze_slp (loop_vec_info
, bb_vec_info
, unsigned);
1119 extern bool vect_make_slp_decision (loop_vec_info
);
1120 extern void vect_detect_hybrid_slp (loop_vec_info
);
1121 extern void vect_get_slp_defs (vec
<tree
> , slp_tree
,
1122 vec
<vec
<tree
> > *, int);
1124 extern source_location
find_bb_location (basic_block
);
1125 extern bb_vec_info
vect_slp_analyze_bb (basic_block
);
1126 extern void vect_slp_transform_bb (basic_block
);
1128 /* In tree-vect-patterns.c. */
1129 /* Pattern recognition functions.
1130 Additional pattern recognition functions can (and will) be added
1132 typedef gimple (* vect_recog_func_ptr
) (vec
<gimple
> *, tree
*, tree
*);
1133 #define NUM_PATTERNS 12
1134 void vect_pattern_recog (loop_vec_info
, bb_vec_info
);
1136 /* In tree-vectorizer.c. */
1137 unsigned vectorize_loops (void);
1138 void vect_destroy_datarefs (loop_vec_info
, bb_vec_info
);
1140 #endif /* GCC_TREE_VECTORIZER_H */