2 Copyright (C) 2003-2017 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"
27 /* 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 type of reduction. */
65 enum vect_reduction_type
{
68 INTEGER_INDUC_COND_REDUCTION
,
72 #define VECTORIZABLE_CYCLE_DEF(D) (((D) == vect_reduction_def) \
73 || ((D) == vect_double_reduction_def) \
74 || ((D) == vect_nested_cycle))
76 /* Structure to encapsulate information about a group of like
77 instructions to be presented to the target cost model. */
78 struct stmt_info_for_cost
{
80 enum vect_cost_for_stmt kind
;
85 typedef vec
<stmt_info_for_cost
> stmt_vector_for_cost
;
87 /************************************************************************
89 ************************************************************************/
90 typedef struct _slp_tree
*slp_tree
;
92 /* A computation tree of an SLP instance. Each node corresponds to a group of
93 stmts to be packed in a SIMD stmt. */
95 /* Nodes that contain def-stmts of this node statements operands. */
96 vec
<slp_tree
> children
;
97 /* A group of scalar stmts to be vectorized together. */
99 /* Load permutation relative to the stores, NULL if there is no
101 vec
<unsigned> load_permutation
;
102 /* Vectorized stmt/s. */
103 vec
<gimple
*> vec_stmts
;
104 /* Number of vector stmts that are created to replace the group of scalar
105 stmts. It is calculated during the transformation phase as the number of
106 scalar elements in one scalar iteration (GROUP_SIZE) multiplied by VF
107 divided by vector size. */
108 unsigned int vec_stmts_size
;
109 /* Whether the scalar computations use two different operators. */
111 /* The DEF type of this node. */
112 enum vect_def_type def_type
;
116 /* SLP instance is a sequence of stmts in a loop that can be packed into
118 typedef struct _slp_instance
{
119 /* The root of SLP tree. */
122 /* Size of groups of scalar stmts that will be replaced by SIMD stmt/s. */
123 unsigned int group_size
;
125 /* The unrolling factor required to vectorized this SLP instance. */
126 unsigned int unrolling_factor
;
128 /* The group of nodes that contain loads of this SLP instance. */
131 /* The SLP node containing the reduction PHIs. */
136 /* Access Functions. */
137 #define SLP_INSTANCE_TREE(S) (S)->root
138 #define SLP_INSTANCE_GROUP_SIZE(S) (S)->group_size
139 #define SLP_INSTANCE_UNROLLING_FACTOR(S) (S)->unrolling_factor
140 #define SLP_INSTANCE_LOADS(S) (S)->loads
142 #define SLP_TREE_CHILDREN(S) (S)->children
143 #define SLP_TREE_SCALAR_STMTS(S) (S)->stmts
144 #define SLP_TREE_VEC_STMTS(S) (S)->vec_stmts
145 #define SLP_TREE_NUMBER_OF_VEC_STMTS(S) (S)->vec_stmts_size
146 #define SLP_TREE_LOAD_PERMUTATION(S) (S)->load_permutation
147 #define SLP_TREE_TWO_OPERATORS(S) (S)->two_operators
148 #define SLP_TREE_DEF_TYPE(S) (S)->def_type
152 /* Vectorizer state common between loop and basic-block vectorization. */
154 enum { bb
, loop
} kind
;
156 /* All SLP instances. */
157 vec
<slp_instance
> slp_instances
;
159 /* All data references. */
160 vec
<data_reference_p
> datarefs
;
162 /* All data dependences. */
165 /* All interleaving chains of stores, represented by the first
166 stmt in the chain. */
167 vec
<gimple
*> grouped_stores
;
169 /* Cost data used by the target cost model. */
170 void *target_cost_data
;
173 struct _loop_vec_info
;
179 is_a_helper
<_loop_vec_info
*>::test (vec_info
*i
)
181 return i
->kind
== vec_info::loop
;
187 is_a_helper
<_bb_vec_info
*>::test (vec_info
*i
)
189 return i
->kind
== vec_info::bb
;
193 /*-----------------------------------------------------------------*/
194 /* Info on vectorized loops. */
195 /*-----------------------------------------------------------------*/
196 typedef struct _loop_vec_info
: public vec_info
{
198 /* The loop to which this info struct refers to. */
201 /* The loop basic blocks. */
204 /* Number of latch executions. */
206 /* Number of iterations. */
208 /* Number of iterations of the original loop. */
209 tree num_iters_unchanged
;
210 /* Condition under which this loop is analyzed and versioned. */
211 tree num_iters_assumptions
;
213 /* Threshold of number of iterations below which vectorzation will not be
214 performed. It is calculated from MIN_PROFITABLE_ITERS and
215 PARAM_MIN_VECT_LOOP_BOUND. */
218 /* Unrolling factor */
219 int vectorization_factor
;
221 /* Unknown DRs according to which loop was peeled. */
222 struct data_reference
*unaligned_dr
;
224 /* peeling_for_alignment indicates whether peeling for alignment will take
225 place, and what the peeling factor should be:
226 peeling_for_alignment = X means:
227 If X=0: Peeling for alignment will not be applied.
228 If X>0: Peel first X iterations.
229 If X=-1: Generate a runtime test to calculate the number of iterations
230 to be peeled, using the dataref recorded in the field
232 int peeling_for_alignment
;
234 /* The mask used to check the alignment of pointers or arrays. */
237 /* The loop nest in which the data dependences are computed. */
238 vec
<loop_p
> loop_nest
;
240 /* Data Dependence Relations defining address ranges that are candidates
241 for a run-time aliasing check. */
242 vec
<ddr_p
> may_alias_ddrs
;
244 /* Data Dependence Relations defining address ranges together with segment
245 lengths from which the run-time aliasing check is built. */
246 vec
<dr_with_seg_len_pair_t
> comp_alias_ddrs
;
248 /* Statements in the loop that have data references that are candidates for a
249 runtime (loop versioning) misalignment check. */
250 vec
<gimple
*> may_misalign_stmts
;
252 /* Reduction cycles detected in the loop. Used in loop-aware SLP. */
253 vec
<gimple
*> reductions
;
255 /* All reduction chains in the loop, represented by the first
256 stmt in the chain. */
257 vec
<gimple
*> reduction_chains
;
259 /* Cost vector for a single scalar iteration. */
260 vec
<stmt_info_for_cost
> scalar_cost_vec
;
262 /* The unrolling factor needed to SLP the loop. In case of that pure SLP is
263 applied to the loop, i.e., no unrolling is needed, this is 1. */
264 unsigned slp_unrolling_factor
;
266 /* Cost of a single scalar iteration. */
267 int single_scalar_iteration_cost
;
269 /* Is the loop vectorizable? */
272 /* When we have grouped data accesses with gaps, we may introduce invalid
273 memory accesses. We peel the last iteration of the loop to prevent
275 bool peeling_for_gaps
;
277 /* When the number of iterations is not a multiple of the vector size
278 we need to peel off iterations at the end to form an epilogue loop. */
279 bool peeling_for_niter
;
281 /* Reductions are canonicalized so that the last operand is the reduction
282 operand. If this places a constant into RHS1, this decanonicalizes
283 GIMPLE for other phases, so we must track when this has occurred and
285 bool operands_swapped
;
287 /* True if there are no loop carried data dependencies in the loop.
288 If loop->safelen <= 1, then this is always true, either the loop
289 didn't have any loop carried data dependencies, or the loop is being
290 vectorized guarded with some runtime alias checks, or couldn't
291 be vectorized at all, but then this field shouldn't be used.
292 For loop->safelen >= 2, the user has asserted that there are no
293 backward dependencies, but there still could be loop carried forward
294 dependencies in such loops. This flag will be false if normal
295 vectorizer data dependency analysis would fail or require versioning
296 for alias, but because of loop->safelen >= 2 it has been vectorized
297 even without versioning for alias. E.g. in:
299 for (int i = 0; i < m; i++)
301 (or #pragma simd or #pragma ivdep) we can vectorize this and it will
302 DTRT even for k > 0 && k < m, but without safelen we would not
303 vectorize this, so this field would be false. */
304 bool no_data_dependencies
;
306 /* Mark loops having masked stores. */
309 /* If if-conversion versioned this loop before conversion, this is the
310 loop version without if-conversion. */
311 struct loop
*scalar_loop
;
313 /* For loops being epilogues of already vectorized loops
314 this points to the original vectorized loop. Otherwise NULL. */
315 _loop_vec_info
*orig_loop_info
;
319 /* Access Functions. */
320 #define LOOP_VINFO_LOOP(L) (L)->loop
321 #define LOOP_VINFO_BBS(L) (L)->bbs
322 #define LOOP_VINFO_NITERSM1(L) (L)->num_itersm1
323 #define LOOP_VINFO_NITERS(L) (L)->num_iters
324 /* Since LOOP_VINFO_NITERS and LOOP_VINFO_NITERSM1 can change after
325 prologue peeling retain total unchanged scalar loop iterations for
327 #define LOOP_VINFO_NITERS_UNCHANGED(L) (L)->num_iters_unchanged
328 #define LOOP_VINFO_NITERS_ASSUMPTIONS(L) (L)->num_iters_assumptions
329 #define LOOP_VINFO_COST_MODEL_THRESHOLD(L) (L)->th
330 #define LOOP_VINFO_VECTORIZABLE_P(L) (L)->vectorizable
331 #define LOOP_VINFO_VECT_FACTOR(L) (L)->vectorization_factor
332 #define LOOP_VINFO_PTR_MASK(L) (L)->ptr_mask
333 #define LOOP_VINFO_LOOP_NEST(L) (L)->loop_nest
334 #define LOOP_VINFO_DATAREFS(L) (L)->datarefs
335 #define LOOP_VINFO_DDRS(L) (L)->ddrs
336 #define LOOP_VINFO_INT_NITERS(L) (TREE_INT_CST_LOW ((L)->num_iters))
337 #define LOOP_VINFO_PEELING_FOR_ALIGNMENT(L) (L)->peeling_for_alignment
338 #define LOOP_VINFO_UNALIGNED_DR(L) (L)->unaligned_dr
339 #define LOOP_VINFO_MAY_MISALIGN_STMTS(L) (L)->may_misalign_stmts
340 #define LOOP_VINFO_MAY_ALIAS_DDRS(L) (L)->may_alias_ddrs
341 #define LOOP_VINFO_COMP_ALIAS_DDRS(L) (L)->comp_alias_ddrs
342 #define LOOP_VINFO_GROUPED_STORES(L) (L)->grouped_stores
343 #define LOOP_VINFO_SLP_INSTANCES(L) (L)->slp_instances
344 #define LOOP_VINFO_SLP_UNROLLING_FACTOR(L) (L)->slp_unrolling_factor
345 #define LOOP_VINFO_REDUCTIONS(L) (L)->reductions
346 #define LOOP_VINFO_REDUCTION_CHAINS(L) (L)->reduction_chains
347 #define LOOP_VINFO_TARGET_COST_DATA(L) (L)->target_cost_data
348 #define LOOP_VINFO_PEELING_FOR_GAPS(L) (L)->peeling_for_gaps
349 #define LOOP_VINFO_OPERANDS_SWAPPED(L) (L)->operands_swapped
350 #define LOOP_VINFO_PEELING_FOR_NITER(L) (L)->peeling_for_niter
351 #define LOOP_VINFO_NO_DATA_DEPENDENCIES(L) (L)->no_data_dependencies
352 #define LOOP_VINFO_SCALAR_LOOP(L) (L)->scalar_loop
353 #define LOOP_VINFO_HAS_MASK_STORE(L) (L)->has_mask_store
354 #define LOOP_VINFO_SCALAR_ITERATION_COST(L) (L)->scalar_cost_vec
355 #define LOOP_VINFO_SINGLE_SCALAR_ITERATION_COST(L) (L)->single_scalar_iteration_cost
356 #define LOOP_VINFO_ORIG_LOOP_INFO(L) (L)->orig_loop_info
358 #define LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT(L) \
359 ((L)->may_misalign_stmts.length () > 0)
360 #define LOOP_REQUIRES_VERSIONING_FOR_ALIAS(L) \
361 ((L)->may_alias_ddrs.length () > 0)
362 #define LOOP_REQUIRES_VERSIONING_FOR_NITERS(L) \
363 (LOOP_VINFO_NITERS_ASSUMPTIONS (L))
364 #define LOOP_REQUIRES_VERSIONING(L) \
365 (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (L) \
366 || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (L) \
367 || LOOP_REQUIRES_VERSIONING_FOR_NITERS (L))
369 #define LOOP_VINFO_NITERS_KNOWN_P(L) \
370 (tree_fits_shwi_p ((L)->num_iters) && tree_to_shwi ((L)->num_iters) > 0)
372 #define LOOP_VINFO_EPILOGUE_P(L) \
373 (LOOP_VINFO_ORIG_LOOP_INFO (L) != NULL)
375 #define LOOP_VINFO_ORIG_VECT_FACTOR(L) \
376 (LOOP_VINFO_VECT_FACTOR (LOOP_VINFO_ORIG_LOOP_INFO (L)))
378 static inline loop_vec_info
379 loop_vec_info_for_loop (struct loop
*loop
)
381 return (loop_vec_info
) loop
->aux
;
385 nested_in_vect_loop_p (struct loop
*loop
, gimple
*stmt
)
388 && (loop
->inner
== (gimple_bb (stmt
))->loop_father
));
391 typedef struct _bb_vec_info
: public vec_info
394 gimple_stmt_iterator region_begin
;
395 gimple_stmt_iterator region_end
;
398 #define BB_VINFO_BB(B) (B)->bb
399 #define BB_VINFO_GROUPED_STORES(B) (B)->grouped_stores
400 #define BB_VINFO_SLP_INSTANCES(B) (B)->slp_instances
401 #define BB_VINFO_DATAREFS(B) (B)->datarefs
402 #define BB_VINFO_DDRS(B) (B)->ddrs
403 #define BB_VINFO_TARGET_COST_DATA(B) (B)->target_cost_data
405 static inline bb_vec_info
406 vec_info_for_bb (basic_block bb
)
408 return (bb_vec_info
) bb
->aux
;
411 /*-----------------------------------------------------------------*/
412 /* Info on vectorized defs. */
413 /*-----------------------------------------------------------------*/
414 enum stmt_vec_info_type
{
415 undef_vec_info_type
= 0,
421 call_simd_clone_vec_info_type
,
422 assignment_vec_info_type
,
423 condition_vec_info_type
,
424 comparison_vec_info_type
,
427 type_promotion_vec_info_type
,
428 type_demotion_vec_info_type
,
429 type_conversion_vec_info_type
,
430 loop_exit_ctrl_vec_info_type
433 /* Indicates whether/how a variable is used in the scope of loop/basic
436 vect_unused_in_scope
= 0,
438 /* The def is only used outside the loop. */
440 /* The def is in the inner loop, and the use is in the outer loop, and the
441 use is a reduction stmt. */
442 vect_used_in_outer_by_reduction
,
443 /* The def is in the inner loop, and the use is in the outer loop (and is
444 not part of reduction). */
447 /* defs that feed computations that end up (only) in a reduction. These
448 defs may be used by non-reduction stmts, but eventually, any
449 computations/values that are affected by these defs are used to compute
450 a reduction (i.e. don't get stored to memory, for example). We use this
451 to identify computations that we can change the order in which they are
453 vect_used_by_reduction
,
458 /* The type of vectorization that can be applied to the stmt: regular loop-based
459 vectorization; pure SLP - the stmt is a part of SLP instances and does not
460 have uses outside SLP instances; or hybrid SLP and loop-based - the stmt is
461 a part of SLP instance and also must be loop-based vectorized, since it has
462 uses outside SLP sequences.
464 In the loop context the meanings of pure and hybrid SLP are slightly
465 different. By saying that pure SLP is applied to the loop, we mean that we
466 exploit only intra-iteration parallelism in the loop; i.e., the loop can be
467 vectorized without doing any conceptual unrolling, cause we don't pack
468 together stmts from different iterations, only within a single iteration.
469 Loop hybrid SLP means that we exploit both intra-iteration and
470 inter-iteration parallelism (e.g., number of elements in the vector is 4
471 and the slp-group-size is 2, in which case we don't have enough parallelism
472 within an iteration, so we obtain the rest of the parallelism from subsequent
473 iterations by unrolling the loop by 2). */
480 /* Describes how we're going to vectorize an individual load or store,
481 or a group of loads or stores. */
482 enum vect_memory_access_type
{
483 /* An access to an invariant address. This is used only for loads. */
486 /* A simple contiguous access. */
489 /* A contiguous access that goes down in memory rather than up,
490 with no additional permutation. This is used only for stores
492 VMAT_CONTIGUOUS_DOWN
,
494 /* A simple contiguous access in which the elements need to be permuted
495 after loading or before storing. Only used for loop vectorization;
496 SLP uses separate permutes. */
497 VMAT_CONTIGUOUS_PERMUTE
,
499 /* A simple contiguous access in which the elements need to be reversed
500 after loading or before storing. */
501 VMAT_CONTIGUOUS_REVERSE
,
503 /* An access that uses IFN_LOAD_LANES or IFN_STORE_LANES. */
504 VMAT_LOAD_STORE_LANES
,
506 /* An access in which each scalar element is loaded or stored
510 /* A hybrid of VMAT_CONTIGUOUS and VMAT_ELEMENTWISE, used for grouped
511 SLP accesses. Each unrolled iteration uses a contiguous load
512 or store for the whole group, but the groups from separate iterations
513 are combined in the same way as for VMAT_ELEMENTWISE. */
516 /* The access uses gather loads or scatter stores. */
520 typedef struct data_reference
*dr_p
;
522 typedef struct _stmt_vec_info
{
524 enum stmt_vec_info_type type
;
526 /* Indicates whether this stmts is part of a computation whose result is
527 used outside the loop. */
530 /* Stmt is part of some pattern (computation idiom) */
533 /* Is this statement vectorizable or should it be skipped in (partial)
537 /* The stmt to which this info struct refers to. */
540 /* The vec_info with respect to which STMT is vectorized. */
543 /* The vector type to be used for the LHS of this statement. */
546 /* The vectorized version of the stmt. */
547 gimple
*vectorized_stmt
;
550 /* The following is relevant only for stmts that contain a non-scalar
551 data-ref (array/pointer/struct access). A GIMPLE stmt is expected to have
552 at most one such data-ref. */
554 /* Information about the data-ref (access function, etc),
555 relative to the inner-most containing loop. */
556 struct data_reference
*data_ref_info
;
558 /* Information about the data-ref relative to this loop
559 nest (the loop that is being considered for vectorization). */
560 innermost_loop_behavior dr_wrt_vec_loop
;
562 /* For loop PHI nodes, the base and evolution part of it. This makes sure
563 this information is still available in vect_update_ivs_after_vectorizer
564 where we may not be able to re-analyze the PHI nodes evolution as
565 peeling for the prologue loop can make it unanalyzable. The evolution
566 part is still correct after peeling, but the base may have changed from
568 tree loop_phi_evolution_base_unchanged
;
569 tree loop_phi_evolution_part
;
571 /* Used for various bookkeeping purposes, generally holding a pointer to
572 some other stmt S that is in some way "related" to this stmt.
573 Current use of this field is:
574 If this stmt is part of a pattern (i.e. the field 'in_pattern_p' is
575 true): S is the "pattern stmt" that represents (and replaces) the
576 sequence of stmts that constitutes the pattern. Similarly, the
577 related_stmt of the "pattern stmt" points back to this stmt (which is
578 the last stmt in the original sequence of stmts that constitutes the
580 gimple
*related_stmt
;
582 /* Used to keep a sequence of def stmts of a pattern stmt if such exists. */
583 gimple_seq pattern_def_seq
;
585 /* List of datarefs that are known to have the same alignment as the dataref
587 vec
<dr_p
> same_align_refs
;
589 /* Selected SIMD clone's function info. First vector element
590 is SIMD clone's function decl, followed by a pair of trees (base + step)
591 for linear arguments (pair of NULLs for other arguments). */
592 vec
<tree
> simd_clone_info
;
594 /* Classify the def of this stmt. */
595 enum vect_def_type def_type
;
597 /* Whether the stmt is SLPed, loop-based vectorized, or both. */
598 enum slp_vect_type slp_type
;
600 /* Interleaving and reduction chains info. */
601 /* First element in the group. */
602 gimple
*first_element
;
603 /* Pointer to the next element in the group. */
604 gimple
*next_element
;
605 /* For data-refs, in case that two or more stmts share data-ref, this is the
606 pointer to the previously detected stmt with the same dr. */
607 gimple
*same_dr_stmt
;
608 /* The size of the group. */
610 /* For stores, number of stores from this group seen. We vectorize the last
612 unsigned int store_count
;
613 /* For loads only, the gap from the previous load. For consecutive loads, GAP
617 /* The minimum negative dependence distance this stmt participates in
619 unsigned int min_neg_dist
;
621 /* Not all stmts in the loop need to be vectorized. e.g, the increment
622 of the loop induction variable and computation of array indexes. relevant
623 indicates whether the stmt needs to be vectorized. */
624 enum vect_relevant relevant
;
626 /* For loads if this is a gather, for stores if this is a scatter. */
627 bool gather_scatter_p
;
629 /* True if this is an access with loop-invariant stride. */
632 /* For both loads and stores. */
633 bool simd_lane_access_p
;
635 /* Classifies how the load or store is going to be implemented
636 for loop vectorization. */
637 vect_memory_access_type memory_access_type
;
639 /* For reduction loops, this is the type of reduction. */
640 enum vect_reduction_type v_reduc_type
;
642 /* For CONST_COND_REDUCTION, record the reduc code. */
643 enum tree_code const_cond_reduc_code
;
645 /* On a reduction PHI the reduction type as detected by
646 vect_force_simple_reduction. */
647 enum vect_reduction_type reduc_type
;
649 /* On a reduction PHI the def returned by vect_force_simple_reduction.
650 On the def returned by vect_force_simple_reduction the
651 corresponding PHI. */
654 /* The number of scalar stmt references from active SLP instances. */
655 unsigned int num_slp_uses
;
658 /* Information about a gather/scatter call. */
659 struct gather_scatter_info
{
660 /* The FUNCTION_DECL for the built-in gather/scatter function. */
663 /* The loop-invariant base value. */
666 /* The original scalar offset, which is a non-loop-invariant SSA_NAME. */
669 /* Each offset element should be multiplied by this amount before
670 being added to the base. */
673 /* The definition type for the vectorized offset. */
674 enum vect_def_type offset_dt
;
676 /* The type of the vectorized offset. */
680 /* Access Functions. */
681 #define STMT_VINFO_TYPE(S) (S)->type
682 #define STMT_VINFO_STMT(S) (S)->stmt
684 STMT_VINFO_LOOP_VINFO (stmt_vec_info stmt_vinfo
)
686 if (loop_vec_info loop_vinfo
= dyn_cast
<loop_vec_info
> (stmt_vinfo
->vinfo
))
691 STMT_VINFO_BB_VINFO (stmt_vec_info stmt_vinfo
)
693 if (bb_vec_info bb_vinfo
= dyn_cast
<bb_vec_info
> (stmt_vinfo
->vinfo
))
697 #define STMT_VINFO_RELEVANT(S) (S)->relevant
698 #define STMT_VINFO_LIVE_P(S) (S)->live
699 #define STMT_VINFO_VECTYPE(S) (S)->vectype
700 #define STMT_VINFO_VEC_STMT(S) (S)->vectorized_stmt
701 #define STMT_VINFO_VECTORIZABLE(S) (S)->vectorizable
702 #define STMT_VINFO_DATA_REF(S) (S)->data_ref_info
703 #define STMT_VINFO_GATHER_SCATTER_P(S) (S)->gather_scatter_p
704 #define STMT_VINFO_STRIDED_P(S) (S)->strided_p
705 #define STMT_VINFO_MEMORY_ACCESS_TYPE(S) (S)->memory_access_type
706 #define STMT_VINFO_SIMD_LANE_ACCESS_P(S) (S)->simd_lane_access_p
707 #define STMT_VINFO_VEC_REDUCTION_TYPE(S) (S)->v_reduc_type
708 #define STMT_VINFO_VEC_CONST_COND_REDUC_CODE(S) (S)->const_cond_reduc_code
710 #define STMT_VINFO_DR_WRT_VEC_LOOP(S) (S)->dr_wrt_vec_loop
711 #define STMT_VINFO_DR_BASE_ADDRESS(S) (S)->dr_wrt_vec_loop.base_address
712 #define STMT_VINFO_DR_INIT(S) (S)->dr_wrt_vec_loop.init
713 #define STMT_VINFO_DR_OFFSET(S) (S)->dr_wrt_vec_loop.offset
714 #define STMT_VINFO_DR_STEP(S) (S)->dr_wrt_vec_loop.step
715 #define STMT_VINFO_DR_BASE_ALIGNMENT(S) (S)->dr_wrt_vec_loop.base_alignment
716 #define STMT_VINFO_DR_BASE_MISALIGNMENT(S) \
717 (S)->dr_wrt_vec_loop.base_misalignment
718 #define STMT_VINFO_DR_OFFSET_ALIGNMENT(S) \
719 (S)->dr_wrt_vec_loop.offset_alignment
720 #define STMT_VINFO_DR_STEP_ALIGNMENT(S) \
721 (S)->dr_wrt_vec_loop.step_alignment
723 #define STMT_VINFO_IN_PATTERN_P(S) (S)->in_pattern_p
724 #define STMT_VINFO_RELATED_STMT(S) (S)->related_stmt
725 #define STMT_VINFO_PATTERN_DEF_SEQ(S) (S)->pattern_def_seq
726 #define STMT_VINFO_SAME_ALIGN_REFS(S) (S)->same_align_refs
727 #define STMT_VINFO_SIMD_CLONE_INFO(S) (S)->simd_clone_info
728 #define STMT_VINFO_DEF_TYPE(S) (S)->def_type
729 #define STMT_VINFO_GROUP_FIRST_ELEMENT(S) (S)->first_element
730 #define STMT_VINFO_GROUP_NEXT_ELEMENT(S) (S)->next_element
731 #define STMT_VINFO_GROUP_SIZE(S) (S)->size
732 #define STMT_VINFO_GROUP_STORE_COUNT(S) (S)->store_count
733 #define STMT_VINFO_GROUP_GAP(S) (S)->gap
734 #define STMT_VINFO_GROUP_SAME_DR_STMT(S) (S)->same_dr_stmt
735 #define STMT_VINFO_GROUPED_ACCESS(S) ((S)->first_element != NULL && (S)->data_ref_info)
736 #define STMT_VINFO_LOOP_PHI_EVOLUTION_BASE_UNCHANGED(S) (S)->loop_phi_evolution_base_unchanged
737 #define STMT_VINFO_LOOP_PHI_EVOLUTION_PART(S) (S)->loop_phi_evolution_part
738 #define STMT_VINFO_MIN_NEG_DIST(S) (S)->min_neg_dist
739 #define STMT_VINFO_NUM_SLP_USES(S) (S)->num_slp_uses
740 #define STMT_VINFO_REDUC_TYPE(S) (S)->reduc_type
741 #define STMT_VINFO_REDUC_DEF(S) (S)->reduc_def
743 #define GROUP_FIRST_ELEMENT(S) (S)->first_element
744 #define GROUP_NEXT_ELEMENT(S) (S)->next_element
745 #define GROUP_SIZE(S) (S)->size
746 #define GROUP_STORE_COUNT(S) (S)->store_count
747 #define GROUP_GAP(S) (S)->gap
748 #define GROUP_SAME_DR_STMT(S) (S)->same_dr_stmt
750 #define STMT_VINFO_RELEVANT_P(S) ((S)->relevant != vect_unused_in_scope)
752 #define HYBRID_SLP_STMT(S) ((S)->slp_type == hybrid)
753 #define PURE_SLP_STMT(S) ((S)->slp_type == pure_slp)
754 #define STMT_SLP_TYPE(S) (S)->slp_type
758 /* If true the alignment of base_decl needs to be increased. */
759 bool base_misaligned
;
763 #define DR_VECT_AUX(dr) ((dataref_aux *)(dr)->aux)
765 #define VECT_MAX_COST 1000
767 /* The maximum number of intermediate steps required in multi-step type
769 #define MAX_INTERM_CVT_STEPS 3
771 /* The maximum vectorization factor supported by any target (V64QI). */
772 #define MAX_VECTORIZATION_FACTOR 64
774 /* Nonzero if TYPE represents a (scalar) boolean type or type
775 in the middle-end compatible with it (unsigned precision 1 integral
776 types). Used to determine which types should be vectorized as
777 VECTOR_BOOLEAN_TYPE_P. */
779 #define VECT_SCALAR_BOOLEAN_TYPE_P(TYPE) \
780 (TREE_CODE (TYPE) == BOOLEAN_TYPE \
781 || ((TREE_CODE (TYPE) == INTEGER_TYPE \
782 || TREE_CODE (TYPE) == ENUMERAL_TYPE) \
783 && TYPE_PRECISION (TYPE) == 1 \
784 && TYPE_UNSIGNED (TYPE)))
786 extern vec
<stmt_vec_info
> stmt_vec_info_vec
;
788 void init_stmt_vec_info_vec (void);
789 void free_stmt_vec_info_vec (void);
791 /* Return a stmt_vec_info corresponding to STMT. */
793 static inline stmt_vec_info
794 vinfo_for_stmt (gimple
*stmt
)
796 unsigned int uid
= gimple_uid (stmt
);
800 return stmt_vec_info_vec
[uid
- 1];
803 /* Set vectorizer information INFO for STMT. */
806 set_vinfo_for_stmt (gimple
*stmt
, stmt_vec_info info
)
808 unsigned int uid
= gimple_uid (stmt
);
811 gcc_checking_assert (info
);
812 uid
= stmt_vec_info_vec
.length () + 1;
813 gimple_set_uid (stmt
, uid
);
814 stmt_vec_info_vec
.safe_push (info
);
818 gcc_checking_assert (info
== NULL
);
819 stmt_vec_info_vec
[uid
- 1] = info
;
823 /* Return the earlier statement between STMT1 and STMT2. */
825 static inline gimple
*
826 get_earlier_stmt (gimple
*stmt1
, gimple
*stmt2
)
828 unsigned int uid1
, uid2
;
836 uid1
= gimple_uid (stmt1
);
837 uid2
= gimple_uid (stmt2
);
839 if (uid1
== 0 || uid2
== 0)
842 gcc_checking_assert (uid1
<= stmt_vec_info_vec
.length ()
843 && uid2
<= stmt_vec_info_vec
.length ());
851 /* Return the later statement between STMT1 and STMT2. */
853 static inline gimple
*
854 get_later_stmt (gimple
*stmt1
, gimple
*stmt2
)
856 unsigned int uid1
, uid2
;
864 uid1
= gimple_uid (stmt1
);
865 uid2
= gimple_uid (stmt2
);
867 if (uid1
== 0 || uid2
== 0)
870 gcc_assert (uid1
<= stmt_vec_info_vec
.length ());
871 gcc_assert (uid2
<= stmt_vec_info_vec
.length ());
879 /* Return TRUE if a statement represented by STMT_INFO is a part of a
883 is_pattern_stmt_p (stmt_vec_info stmt_info
)
885 gimple
*related_stmt
;
886 stmt_vec_info related_stmt_info
;
888 related_stmt
= STMT_VINFO_RELATED_STMT (stmt_info
);
890 && (related_stmt_info
= vinfo_for_stmt (related_stmt
))
891 && STMT_VINFO_IN_PATTERN_P (related_stmt_info
))
897 /* Return true if BB is a loop header. */
900 is_loop_header_bb_p (basic_block bb
)
902 if (bb
== (bb
->loop_father
)->header
)
904 gcc_checking_assert (EDGE_COUNT (bb
->preds
) == 1);
908 /* Return pow2 (X). */
915 for (i
= 0; i
< x
; i
++)
921 /* Alias targetm.vectorize.builtin_vectorization_cost. */
924 builtin_vectorization_cost (enum vect_cost_for_stmt type_of_cost
,
925 tree vectype
, int misalign
)
927 return targetm
.vectorize
.builtin_vectorization_cost (type_of_cost
,
931 /* Get cost by calling cost target builtin. */
934 int vect_get_stmt_cost (enum vect_cost_for_stmt type_of_cost
)
936 return builtin_vectorization_cost (type_of_cost
, NULL
, 0);
939 /* Alias targetm.vectorize.init_cost. */
942 init_cost (struct loop
*loop_info
)
944 return targetm
.vectorize
.init_cost (loop_info
);
947 /* Alias targetm.vectorize.add_stmt_cost. */
949 static inline unsigned
950 add_stmt_cost (void *data
, int count
, enum vect_cost_for_stmt kind
,
951 stmt_vec_info stmt_info
, int misalign
,
952 enum vect_cost_model_location where
)
954 return targetm
.vectorize
.add_stmt_cost (data
, count
, kind
,
955 stmt_info
, misalign
, where
);
958 /* Alias targetm.vectorize.finish_cost. */
961 finish_cost (void *data
, unsigned *prologue_cost
,
962 unsigned *body_cost
, unsigned *epilogue_cost
)
964 targetm
.vectorize
.finish_cost (data
, prologue_cost
, body_cost
, epilogue_cost
);
967 /* Alias targetm.vectorize.destroy_cost_data. */
970 destroy_cost_data (void *data
)
972 targetm
.vectorize
.destroy_cost_data (data
);
975 /*-----------------------------------------------------------------*/
976 /* Info on data references alignment. */
977 /*-----------------------------------------------------------------*/
979 set_dr_misalignment (struct data_reference
*dr
, int val
)
981 dataref_aux
*data_aux
= DR_VECT_AUX (dr
);
985 data_aux
= XCNEW (dataref_aux
);
989 data_aux
->misalignment
= val
;
993 dr_misalignment (struct data_reference
*dr
)
995 return DR_VECT_AUX (dr
)->misalignment
;
998 /* Reflects actual alignment of first access in the vectorized loop,
999 taking into account peeling/versioning if applied. */
1000 #define DR_MISALIGNMENT(DR) dr_misalignment (DR)
1001 #define SET_DR_MISALIGNMENT(DR, VAL) set_dr_misalignment (DR, VAL)
1002 #define DR_MISALIGNMENT_UNKNOWN (-1)
1004 /* Return TRUE if the data access is aligned, and FALSE otherwise. */
1007 aligned_access_p (struct data_reference
*data_ref_info
)
1009 return (DR_MISALIGNMENT (data_ref_info
) == 0);
1012 /* Return TRUE if the alignment of the data access is known, and FALSE
1016 known_alignment_for_access_p (struct data_reference
*data_ref_info
)
1018 return (DR_MISALIGNMENT (data_ref_info
) != DR_MISALIGNMENT_UNKNOWN
);
1021 /* Return the behavior of DR with respect to the vectorization context
1022 (which for outer loop vectorization might not be the behavior recorded
1025 static inline innermost_loop_behavior
*
1026 vect_dr_behavior (data_reference
*dr
)
1028 gimple
*stmt
= DR_STMT (dr
);
1029 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1030 loop_vec_info loop_vinfo
= STMT_VINFO_LOOP_VINFO (stmt_info
);
1031 if (loop_vinfo
== NULL
1032 || !nested_in_vect_loop_p (LOOP_VINFO_LOOP (loop_vinfo
), stmt
))
1033 return &DR_INNERMOST (dr
);
1035 return &STMT_VINFO_DR_WRT_VEC_LOOP (stmt_info
);
1038 /* Return true if the vect cost model is unlimited. */
1040 unlimited_cost_model (loop_p loop
)
1042 if (loop
!= NULL
&& loop
->force_vectorize
1043 && flag_simd_cost_model
!= VECT_COST_MODEL_DEFAULT
)
1044 return flag_simd_cost_model
== VECT_COST_MODEL_UNLIMITED
;
1045 return (flag_vect_cost_model
== VECT_COST_MODEL_UNLIMITED
);
1048 /* Source location */
1049 extern source_location vect_location
;
1051 /*-----------------------------------------------------------------*/
1052 /* Function prototypes. */
1053 /*-----------------------------------------------------------------*/
1055 /* Simple loop peeling and versioning utilities for vectorizer's purposes -
1056 in tree-vect-loop-manip.c. */
1057 extern void slpeel_make_loop_iterate_ntimes (struct loop
*, tree
);
1058 extern bool slpeel_can_duplicate_loop_p (const struct loop
*, const_edge
);
1059 struct loop
*slpeel_tree_duplicate_loop_to_edge_cfg (struct loop
*,
1060 struct loop
*, edge
);
1061 extern void vect_loop_versioning (loop_vec_info
, unsigned int, bool);
1062 extern struct loop
*vect_do_peeling (loop_vec_info
, tree
, tree
,
1063 tree
*, int, bool, bool);
1064 extern source_location
find_loop_location (struct loop
*);
1065 extern bool vect_can_advance_ivs_p (loop_vec_info
);
1067 /* In tree-vect-stmts.c. */
1068 extern unsigned int current_vector_size
;
1069 extern tree
get_vectype_for_scalar_type (tree
);
1070 extern tree
get_mask_type_for_scalar_type (tree
);
1071 extern tree
get_same_sized_vectype (tree
, tree
);
1072 extern bool vect_is_simple_use (tree
, vec_info
*, gimple
**,
1073 enum vect_def_type
*);
1074 extern bool vect_is_simple_use (tree
, vec_info
*, gimple
**,
1075 enum vect_def_type
*, tree
*);
1076 extern bool supportable_widening_operation (enum tree_code
, gimple
*, tree
,
1077 tree
, enum tree_code
*,
1078 enum tree_code
*, int *,
1080 extern bool supportable_narrowing_operation (enum tree_code
, tree
, tree
,
1082 int *, vec
<tree
> *);
1083 extern stmt_vec_info
new_stmt_vec_info (gimple
*stmt
, vec_info
*);
1084 extern void free_stmt_vec_info (gimple
*stmt
);
1085 extern void vect_model_simple_cost (stmt_vec_info
, int, enum vect_def_type
*,
1086 int, stmt_vector_for_cost
*,
1087 stmt_vector_for_cost
*);
1088 extern void vect_model_store_cost (stmt_vec_info
, int, vect_memory_access_type
,
1089 enum vect_def_type
, slp_tree
,
1090 stmt_vector_for_cost
*,
1091 stmt_vector_for_cost
*);
1092 extern void vect_model_load_cost (stmt_vec_info
, int, vect_memory_access_type
,
1093 slp_tree
, stmt_vector_for_cost
*,
1094 stmt_vector_for_cost
*);
1095 extern unsigned record_stmt_cost (stmt_vector_for_cost
*, int,
1096 enum vect_cost_for_stmt
, stmt_vec_info
,
1097 int, enum vect_cost_model_location
);
1098 extern void vect_finish_stmt_generation (gimple
*, gimple
*,
1099 gimple_stmt_iterator
*);
1100 extern bool vect_mark_stmts_to_be_vectorized (loop_vec_info
);
1101 extern tree
vect_get_vec_def_for_operand_1 (gimple
*, enum vect_def_type
);
1102 extern tree
vect_get_vec_def_for_operand (tree
, gimple
*, tree
= NULL
);
1103 extern void vect_get_vec_defs (tree
, tree
, gimple
*, vec
<tree
> *,
1104 vec
<tree
> *, slp_tree
);
1105 extern void vect_get_vec_defs_for_stmt_copy (enum vect_def_type
*,
1106 vec
<tree
> *, vec
<tree
> *);
1107 extern tree
vect_init_vector (gimple
*, tree
, tree
,
1108 gimple_stmt_iterator
*);
1109 extern tree
vect_get_vec_def_for_stmt_copy (enum vect_def_type
, tree
);
1110 extern bool vect_transform_stmt (gimple
*, gimple_stmt_iterator
*,
1111 bool *, slp_tree
, slp_instance
);
1112 extern void vect_remove_stores (gimple
*);
1113 extern bool vect_analyze_stmt (gimple
*, bool *, slp_tree
, slp_instance
);
1114 extern bool vectorizable_condition (gimple
*, gimple_stmt_iterator
*,
1115 gimple
**, tree
, int, slp_tree
);
1116 extern void vect_get_load_cost (struct data_reference
*, int, bool,
1117 unsigned int *, unsigned int *,
1118 stmt_vector_for_cost
*,
1119 stmt_vector_for_cost
*, bool);
1120 extern void vect_get_store_cost (struct data_reference
*, int,
1121 unsigned int *, stmt_vector_for_cost
*);
1122 extern bool vect_supportable_shift (enum tree_code
, tree
);
1123 extern tree
vect_gen_perm_mask_any (tree
, const unsigned char *);
1124 extern tree
vect_gen_perm_mask_checked (tree
, const unsigned char *);
1125 extern void optimize_mask_stores (struct loop
*);
1127 /* In tree-vect-data-refs.c. */
1128 extern bool vect_can_force_dr_alignment_p (const_tree
, unsigned int);
1129 extern enum dr_alignment_support vect_supportable_dr_alignment
1130 (struct data_reference
*, bool);
1131 extern tree
vect_get_smallest_scalar_type (gimple
*, HOST_WIDE_INT
*,
1133 extern bool vect_analyze_data_ref_dependences (loop_vec_info
, int *);
1134 extern bool vect_slp_analyze_instance_dependence (slp_instance
);
1135 extern bool vect_enhance_data_refs_alignment (loop_vec_info
);
1136 extern bool vect_analyze_data_refs_alignment (loop_vec_info
);
1137 extern bool vect_verify_datarefs_alignment (loop_vec_info
);
1138 extern bool vect_slp_analyze_and_verify_instance_alignment (slp_instance
);
1139 extern bool vect_analyze_data_ref_accesses (vec_info
*);
1140 extern bool vect_prune_runtime_alias_test_list (loop_vec_info
);
1141 extern bool vect_check_gather_scatter (gimple
*, loop_vec_info
,
1142 gather_scatter_info
*);
1143 extern bool vect_analyze_data_refs (vec_info
*, int *);
1144 extern tree
vect_create_data_ref_ptr (gimple
*, tree
, struct loop
*, tree
,
1145 tree
*, gimple_stmt_iterator
*,
1146 gimple
**, bool, bool *,
1148 extern tree
bump_vector_ptr (tree
, gimple
*, gimple_stmt_iterator
*, gimple
*,
1150 extern tree
vect_create_destination_var (tree
, tree
);
1151 extern bool vect_grouped_store_supported (tree
, unsigned HOST_WIDE_INT
);
1152 extern bool vect_store_lanes_supported (tree
, unsigned HOST_WIDE_INT
);
1153 extern bool vect_grouped_load_supported (tree
, bool, unsigned HOST_WIDE_INT
);
1154 extern bool vect_load_lanes_supported (tree
, unsigned HOST_WIDE_INT
);
1155 extern void vect_permute_store_chain (vec
<tree
> ,unsigned int, gimple
*,
1156 gimple_stmt_iterator
*, vec
<tree
> *);
1157 extern tree
vect_setup_realignment (gimple
*, gimple_stmt_iterator
*, tree
*,
1158 enum dr_alignment_support
, tree
,
1160 extern void vect_transform_grouped_load (gimple
*, vec
<tree
> , int,
1161 gimple_stmt_iterator
*);
1162 extern void vect_record_grouped_load_vectors (gimple
*, vec
<tree
> );
1163 extern tree
vect_get_new_vect_var (tree
, enum vect_var_kind
, const char *);
1164 extern tree
vect_get_new_ssa_name (tree
, enum vect_var_kind
,
1165 const char * = NULL
);
1166 extern tree
vect_create_addr_base_for_vector_ref (gimple
*, gimple_seq
*,
1167 tree
, tree
= NULL_TREE
);
1169 /* In tree-vect-loop.c. */
1170 /* FORNOW: Used in tree-parloops.c. */
1171 extern void destroy_loop_vec_info (loop_vec_info
, bool);
1172 extern gimple
*vect_force_simple_reduction (loop_vec_info
, gimple
*,
1174 /* Drive for loop analysis stage. */
1175 extern loop_vec_info
vect_analyze_loop (struct loop
*, loop_vec_info
);
1176 extern tree
vect_build_loop_niters (loop_vec_info
, bool * = NULL
);
1177 extern void vect_gen_vector_loop_niters (loop_vec_info
, tree
, tree
*, bool);
1178 /* Drive for loop transformation stage. */
1179 extern struct loop
*vect_transform_loop (loop_vec_info
);
1180 extern loop_vec_info
vect_analyze_loop_form (struct loop
*);
1181 extern bool vectorizable_live_operation (gimple
*, gimple_stmt_iterator
*,
1182 slp_tree
, int, gimple
**);
1183 extern bool vectorizable_reduction (gimple
*, gimple_stmt_iterator
*,
1184 gimple
**, slp_tree
, slp_instance
);
1185 extern bool vectorizable_induction (gimple
*, gimple_stmt_iterator
*,
1186 gimple
**, slp_tree
);
1187 extern tree
get_initial_def_for_reduction (gimple
*, tree
, tree
*);
1188 extern int vect_min_worthwhile_factor (enum tree_code
);
1189 extern int vect_get_known_peeling_cost (loop_vec_info
, int, int *,
1190 stmt_vector_for_cost
*,
1191 stmt_vector_for_cost
*,
1192 stmt_vector_for_cost
*);
1194 /* In tree-vect-slp.c. */
1195 extern void vect_free_slp_instance (slp_instance
);
1196 extern bool vect_transform_slp_perm_load (slp_tree
, vec
<tree
> ,
1197 gimple_stmt_iterator
*, int,
1198 slp_instance
, bool, unsigned *);
1199 extern bool vect_slp_analyze_operations (vec
<slp_instance
> slp_instances
,
1201 extern bool vect_schedule_slp (vec_info
*);
1202 extern bool vect_analyze_slp (vec_info
*, unsigned);
1203 extern bool vect_make_slp_decision (loop_vec_info
);
1204 extern void vect_detect_hybrid_slp (loop_vec_info
);
1205 extern void vect_get_slp_defs (vec
<tree
> , slp_tree
, vec
<vec
<tree
> > *);
1206 extern bool vect_slp_bb (basic_block
);
1207 extern gimple
*vect_find_last_scalar_stmt_in_slp (slp_tree
);
1208 extern bool is_simple_and_all_uses_invariant (gimple
*, loop_vec_info
);
1210 /* In tree-vect-patterns.c. */
1211 /* Pattern recognition functions.
1212 Additional pattern recognition functions can (and will) be added
1214 typedef gimple
*(* vect_recog_func_ptr
) (vec
<gimple
*> *, tree
*, tree
*);
1215 #define NUM_PATTERNS 14
1216 void vect_pattern_recog (vec_info
*);
1218 /* In tree-vectorizer.c. */
1219 unsigned vectorize_loops (void);
1220 void vect_destroy_datarefs (vec_info
*);
1221 bool vect_stmt_in_region_p (vec_info
*, gimple
*);
1222 void vect_free_loop_info_assumptions (struct loop
*);
1224 #endif /* GCC_TREE_VECTORIZER_H */