gcc/
[official-gcc.git] / gcc / tree-vectorizer.h
blob48c1f8d64b7eac20496b80f1720023ab2ad475d1
1 /* Vectorizer
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
10 version.
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
15 for more details.
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"
25 #include "target.h"
27 /* Used for naming of new temporaries. */
28 enum vect_var_kind {
29 vect_simple_var,
30 vect_pointer_var,
31 vect_scalar_var
34 /* Defines type of operation. */
35 enum operation_type {
36 unary_op = 1,
37 binary_op,
38 ternary_op
41 /* Define type of available alignment support. */
42 enum dr_alignment_support {
43 dr_unaligned_unsupported,
44 dr_unaligned_supported,
45 dr_explicit_realign,
46 dr_explicit_realign_optimized,
47 dr_aligned
50 /* Define type of def-use cross-iteration cycle. */
51 enum vect_def_type {
52 vect_uninitialized_def = 0,
53 vect_constant_def = 1,
54 vect_external_def,
55 vect_internal_def,
56 vect_induction_def,
57 vect_reduction_def,
58 vect_double_reduction_def,
59 vect_nested_cycle,
60 vect_unknown_def_type
63 #define VECTORIZABLE_CYCLE_DEF(D) (((D) == vect_reduction_def) \
64 || ((D) == vect_double_reduction_def) \
65 || ((D) == vect_nested_cycle))
67 /* Structure to encapsulate information about a group of like
68 instructions to be presented to the target cost model. */
69 typedef struct _stmt_info_for_cost {
70 int count;
71 enum vect_cost_for_stmt kind;
72 gimple stmt;
73 int misalign;
74 } stmt_info_for_cost;
77 typedef vec<stmt_info_for_cost> stmt_vector_for_cost;
79 static inline void
80 add_stmt_info_to_vec (stmt_vector_for_cost *stmt_cost_vec, int count,
81 enum vect_cost_for_stmt kind, gimple stmt, int misalign)
83 stmt_info_for_cost si;
84 si.count = count;
85 si.kind = kind;
86 si.stmt = stmt;
87 si.misalign = misalign;
88 stmt_cost_vec->safe_push (si);
91 /************************************************************************
92 SLP
93 ************************************************************************/
94 typedef struct _slp_tree *slp_tree;
96 /* A computation tree of an SLP instance. Each node corresponds to a group of
97 stmts to be packed in a SIMD stmt. */
98 struct _slp_tree {
99 /* Nodes that contain def-stmts of this node statements operands. */
100 vec<slp_tree> children;
101 /* A group of scalar stmts to be vectorized together. */
102 vec<gimple> stmts;
103 /* Load permutation relative to the stores, NULL if there is no
104 permutation. */
105 vec<unsigned> load_permutation;
106 /* Vectorized stmt/s. */
107 vec<gimple> vec_stmts;
108 /* Number of vector stmts that are created to replace the group of scalar
109 stmts. It is calculated during the transformation phase as the number of
110 scalar elements in one scalar iteration (GROUP_SIZE) multiplied by VF
111 divided by vector size. */
112 unsigned int vec_stmts_size;
113 /* Whether the scalar computations use two different operators. */
114 bool two_operators;
118 /* SLP instance is a sequence of stmts in a loop that can be packed into
119 SIMD stmts. */
120 typedef struct _slp_instance {
121 /* The root of SLP tree. */
122 slp_tree root;
124 /* Size of groups of scalar stmts that will be replaced by SIMD stmt/s. */
125 unsigned int group_size;
127 /* The unrolling factor required to vectorized this SLP instance. */
128 unsigned int unrolling_factor;
130 /* The group of nodes that contain loads of this SLP instance. */
131 vec<slp_tree> loads;
132 } *slp_instance;
135 /* Access Functions. */
136 #define SLP_INSTANCE_TREE(S) (S)->root
137 #define SLP_INSTANCE_GROUP_SIZE(S) (S)->group_size
138 #define SLP_INSTANCE_UNROLLING_FACTOR(S) (S)->unrolling_factor
139 #define SLP_INSTANCE_LOADS(S) (S)->loads
141 #define SLP_TREE_CHILDREN(S) (S)->children
142 #define SLP_TREE_SCALAR_STMTS(S) (S)->stmts
143 #define SLP_TREE_VEC_STMTS(S) (S)->vec_stmts
144 #define SLP_TREE_NUMBER_OF_VEC_STMTS(S) (S)->vec_stmts_size
145 #define SLP_TREE_LOAD_PERMUTATION(S) (S)->load_permutation
146 #define SLP_TREE_TWO_OPERATORS(S) (S)->two_operators
148 /* This structure is used in creation of an SLP tree. Each instance
149 corresponds to the same operand in a group of scalar stmts in an SLP
150 node. */
151 typedef struct _slp_oprnd_info
153 /* Def-stmts for the operands. */
154 vec<gimple> def_stmts;
155 /* Information about the first statement, its vector def-type, type, the
156 operand itself in case it's constant, and an indication if it's a pattern
157 stmt. */
158 enum vect_def_type first_dt;
159 tree first_op_type;
160 bool first_pattern;
161 bool second_pattern;
162 } *slp_oprnd_info;
166 /* This struct is used to store the information of a data reference,
167 including the data ref itself, the access offset (calculated by summing its
168 offset and init) and the segment length for aliasing checks.
169 This is used to merge alias checks. */
171 struct dr_with_seg_len
173 dr_with_seg_len (data_reference_p d, tree len)
174 : dr (d),
175 offset (size_binop (PLUS_EXPR, DR_OFFSET (d), DR_INIT (d))),
176 seg_len (len) {}
178 data_reference_p dr;
179 tree offset;
180 tree seg_len;
183 /* This struct contains two dr_with_seg_len objects with aliasing data
184 refs. Two comparisons are generated from them. */
186 struct dr_with_seg_len_pair_t
188 dr_with_seg_len_pair_t (const dr_with_seg_len& d1,
189 const dr_with_seg_len& d2)
190 : first (d1), second (d2) {}
192 dr_with_seg_len first;
193 dr_with_seg_len second;
197 typedef struct _vect_peel_info
199 int npeel;
200 struct data_reference *dr;
201 unsigned int count;
202 } *vect_peel_info;
204 typedef struct _vect_peel_extended_info
206 struct _vect_peel_info peel_info;
207 unsigned int inside_cost;
208 unsigned int outside_cost;
209 stmt_vector_for_cost body_cost_vec;
210 } *vect_peel_extended_info;
213 /* Peeling hashtable helpers. */
215 struct peel_info_hasher : free_ptr_hash <_vect_peel_info>
217 static inline hashval_t hash (const _vect_peel_info *);
218 static inline bool equal (const _vect_peel_info *, const _vect_peel_info *);
221 inline hashval_t
222 peel_info_hasher::hash (const _vect_peel_info *peel_info)
224 return (hashval_t) peel_info->npeel;
227 inline bool
228 peel_info_hasher::equal (const _vect_peel_info *a, const _vect_peel_info *b)
230 return (a->npeel == b->npeel);
234 /*-----------------------------------------------------------------*/
235 /* Info on vectorized loops. */
236 /*-----------------------------------------------------------------*/
237 typedef struct _loop_vec_info {
239 /* The loop to which this info struct refers to. */
240 struct loop *loop;
242 /* The loop basic blocks. */
243 basic_block *bbs;
245 /* Number of latch executions. */
246 tree num_itersm1;
247 /* Number of iterations. */
248 tree num_iters;
249 /* Number of iterations of the original loop. */
250 tree num_iters_unchanged;
252 /* Minimum number of iterations below which vectorization is expected to
253 not be profitable (as estimated by the cost model).
254 -1 indicates that vectorization will not be profitable.
255 FORNOW: This field is an int. Will be a tree in the future, to represent
256 values unknown at compile time. */
257 int min_profitable_iters;
259 /* Threshold of number of iterations below which vectorzation will not be
260 performed. It is calculated from MIN_PROFITABLE_ITERS and
261 PARAM_MIN_VECT_LOOP_BOUND. */
262 unsigned int th;
264 /* Is the loop vectorizable? */
265 bool vectorizable;
267 /* Unrolling factor */
268 int vectorization_factor;
270 /* Unknown DRs according to which loop was peeled. */
271 struct data_reference *unaligned_dr;
273 /* peeling_for_alignment indicates whether peeling for alignment will take
274 place, and what the peeling factor should be:
275 peeling_for_alignment = X means:
276 If X=0: Peeling for alignment will not be applied.
277 If X>0: Peel first X iterations.
278 If X=-1: Generate a runtime test to calculate the number of iterations
279 to be peeled, using the dataref recorded in the field
280 unaligned_dr. */
281 int peeling_for_alignment;
283 /* The mask used to check the alignment of pointers or arrays. */
284 int ptr_mask;
286 /* The loop nest in which the data dependences are computed. */
287 vec<loop_p> loop_nest;
289 /* All data references in the loop. */
290 vec<data_reference_p> datarefs;
292 /* All data dependences in the loop. */
293 vec<ddr_p> ddrs;
295 /* Data Dependence Relations defining address ranges that are candidates
296 for a run-time aliasing check. */
297 vec<ddr_p> may_alias_ddrs;
299 /* Data Dependence Relations defining address ranges together with segment
300 lengths from which the run-time aliasing check is built. */
301 vec<dr_with_seg_len_pair_t> comp_alias_ddrs;
303 /* Statements in the loop that have data references that are candidates for a
304 runtime (loop versioning) misalignment check. */
305 vec<gimple> may_misalign_stmts;
307 /* All interleaving chains of stores in the loop, represented by the first
308 stmt in the chain. */
309 vec<gimple> grouped_stores;
311 /* All SLP instances in the loop. This is a subset of the set of GROUP_STORES
312 of the loop. */
313 vec<slp_instance> slp_instances;
315 /* The unrolling factor needed to SLP the loop. In case of that pure SLP is
316 applied to the loop, i.e., no unrolling is needed, this is 1. */
317 unsigned slp_unrolling_factor;
319 /* Reduction cycles detected in the loop. Used in loop-aware SLP. */
320 vec<gimple> reductions;
322 /* All reduction chains in the loop, represented by the first
323 stmt in the chain. */
324 vec<gimple> reduction_chains;
326 /* Hash table used to choose the best peeling option. */
327 hash_table<peel_info_hasher> *peeling_htab;
329 /* Cost vector for a single scalar iteration. */
330 vec<stmt_info_for_cost> scalar_cost_vec;
332 /* Cost of a single scalar iteration. */
333 int single_scalar_iteration_cost;
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
340 this. */
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
350 fix it up. */
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:
364 #pragma omp simd
365 for (int i = 0; i < m; i++)
366 a[i] = a[i + k] * c;
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;
376 } *loop_vec_info;
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
385 cost model. */
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
413 #define LOOP_VINFO_SCALAR_ITERATION_COST(L) (L)->scalar_cost_vec
414 #define LOOP_VINFO_SINGLE_SCALAR_ITERATION_COST(L) (L)->single_scalar_iteration_cost
416 #define LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT(L) \
417 ((L)->may_misalign_stmts.length () > 0)
418 #define LOOP_REQUIRES_VERSIONING_FOR_ALIAS(L) \
419 ((L)->may_alias_ddrs.length () > 0)
421 #define LOOP_VINFO_NITERS_KNOWN_P(L) \
422 (tree_fits_shwi_p ((L)->num_iters) && tree_to_shwi ((L)->num_iters) > 0)
424 static inline loop_vec_info
425 loop_vec_info_for_loop (struct loop *loop)
427 return (loop_vec_info) loop->aux;
430 static inline bool
431 nested_in_vect_loop_p (struct loop *loop, gimple stmt)
433 return (loop->inner
434 && (loop->inner == (gimple_bb (stmt))->loop_father));
437 typedef struct _bb_vec_info {
439 basic_block bb;
440 /* All interleaving chains of stores in the basic block, represented by the
441 first stmt in the chain. */
442 vec<gimple> grouped_stores;
444 /* All SLP instances in the basic block. This is a subset of the set of
445 GROUP_STORES of the basic block. */
446 vec<slp_instance> slp_instances;
448 /* All data references in the basic block. */
449 vec<data_reference_p> datarefs;
451 /* All data dependences in the basic block. */
452 vec<ddr_p> ddrs;
454 /* Cost data used by the target cost model. */
455 void *target_cost_data;
457 } *bb_vec_info;
459 #define BB_VINFO_BB(B) (B)->bb
460 #define BB_VINFO_GROUPED_STORES(B) (B)->grouped_stores
461 #define BB_VINFO_SLP_INSTANCES(B) (B)->slp_instances
462 #define BB_VINFO_DATAREFS(B) (B)->datarefs
463 #define BB_VINFO_DDRS(B) (B)->ddrs
464 #define BB_VINFO_TARGET_COST_DATA(B) (B)->target_cost_data
466 static inline bb_vec_info
467 vec_info_for_bb (basic_block bb)
469 return (bb_vec_info) bb->aux;
472 /*-----------------------------------------------------------------*/
473 /* Info on vectorized defs. */
474 /*-----------------------------------------------------------------*/
475 enum stmt_vec_info_type {
476 undef_vec_info_type = 0,
477 load_vec_info_type,
478 store_vec_info_type,
479 shift_vec_info_type,
480 op_vec_info_type,
481 call_vec_info_type,
482 call_simd_clone_vec_info_type,
483 assignment_vec_info_type,
484 condition_vec_info_type,
485 reduc_vec_info_type,
486 induc_vec_info_type,
487 type_promotion_vec_info_type,
488 type_demotion_vec_info_type,
489 type_conversion_vec_info_type,
490 loop_exit_ctrl_vec_info_type
493 /* Indicates whether/how a variable is used in the scope of loop/basic
494 block. */
495 enum vect_relevant {
496 vect_unused_in_scope = 0,
497 /* The def is in the inner loop, and the use is in the outer loop, and the
498 use is a reduction stmt. */
499 vect_used_in_outer_by_reduction,
500 /* The def is in the inner loop, and the use is in the outer loop (and is
501 not part of reduction). */
502 vect_used_in_outer,
504 /* defs that feed computations that end up (only) in a reduction. These
505 defs may be used by non-reduction stmts, but eventually, any
506 computations/values that are affected by these defs are used to compute
507 a reduction (i.e. don't get stored to memory, for example). We use this
508 to identify computations that we can change the order in which they are
509 computed. */
510 vect_used_by_reduction,
512 vect_used_in_scope
515 /* The type of vectorization that can be applied to the stmt: regular loop-based
516 vectorization; pure SLP - the stmt is a part of SLP instances and does not
517 have uses outside SLP instances; or hybrid SLP and loop-based - the stmt is
518 a part of SLP instance and also must be loop-based vectorized, since it has
519 uses outside SLP sequences.
521 In the loop context the meanings of pure and hybrid SLP are slightly
522 different. By saying that pure SLP is applied to the loop, we mean that we
523 exploit only intra-iteration parallelism in the loop; i.e., the loop can be
524 vectorized without doing any conceptual unrolling, cause we don't pack
525 together stmts from different iterations, only within a single iteration.
526 Loop hybrid SLP means that we exploit both intra-iteration and
527 inter-iteration parallelism (e.g., number of elements in the vector is 4
528 and the slp-group-size is 2, in which case we don't have enough parallelism
529 within an iteration, so we obtain the rest of the parallelism from subsequent
530 iterations by unrolling the loop by 2). */
531 enum slp_vect_type {
532 loop_vect = 0,
533 pure_slp,
534 hybrid
538 typedef struct data_reference *dr_p;
540 typedef struct _stmt_vec_info {
542 enum stmt_vec_info_type type;
544 /* Indicates whether this stmts is part of a computation whose result is
545 used outside the loop. */
546 bool live;
548 /* Stmt is part of some pattern (computation idiom) */
549 bool in_pattern_p;
551 /* The stmt to which this info struct refers to. */
552 gimple stmt;
554 /* The loop_vec_info with respect to which STMT is vectorized. */
555 loop_vec_info loop_vinfo;
557 /* The vector type to be used for the LHS of this statement. */
558 tree vectype;
560 /* The vectorized version of the stmt. */
561 gimple vectorized_stmt;
564 /** The following is relevant only for stmts that contain a non-scalar
565 data-ref (array/pointer/struct access). A GIMPLE stmt is expected to have
566 at most one such data-ref. **/
568 /* Information about the data-ref (access function, etc),
569 relative to the inner-most containing loop. */
570 struct data_reference *data_ref_info;
572 /* Information about the data-ref relative to this loop
573 nest (the loop that is being considered for vectorization). */
574 tree dr_base_address;
575 tree dr_init;
576 tree dr_offset;
577 tree dr_step;
578 tree dr_aligned_to;
580 /* For loop PHI nodes, the evolution part of it. This makes sure
581 this information is still available in vect_update_ivs_after_vectorizer
582 where we may not be able to re-analyze the PHI nodes evolution as
583 peeling for the prologue loop can make it unanalyzable. The evolution
584 part is still correct though. */
585 tree loop_phi_evolution_part;
587 /* Used for various bookkeeping purposes, generally holding a pointer to
588 some other stmt S that is in some way "related" to this stmt.
589 Current use of this field is:
590 If this stmt is part of a pattern (i.e. the field 'in_pattern_p' is
591 true): S is the "pattern stmt" that represents (and replaces) the
592 sequence of stmts that constitutes the pattern. Similarly, the
593 related_stmt of the "pattern stmt" points back to this stmt (which is
594 the last stmt in the original sequence of stmts that constitutes the
595 pattern). */
596 gimple related_stmt;
598 /* Used to keep a sequence of def stmts of a pattern stmt if such exists. */
599 gimple_seq pattern_def_seq;
601 /* List of datarefs that are known to have the same alignment as the dataref
602 of this stmt. */
603 vec<dr_p> same_align_refs;
605 /* Selected SIMD clone's function info. First vector element
606 is SIMD clone's function decl, followed by a pair of trees (base + step)
607 for linear arguments (pair of NULLs for other arguments). */
608 vec<tree> simd_clone_info;
610 /* Classify the def of this stmt. */
611 enum vect_def_type def_type;
613 /* Whether the stmt is SLPed, loop-based vectorized, or both. */
614 enum slp_vect_type slp_type;
616 /* Interleaving and reduction chains info. */
617 /* First element in the group. */
618 gimple first_element;
619 /* Pointer to the next element in the group. */
620 gimple next_element;
621 /* For data-refs, in case that two or more stmts share data-ref, this is the
622 pointer to the previously detected stmt with the same dr. */
623 gimple same_dr_stmt;
624 /* The size of the group. */
625 unsigned int size;
626 /* For stores, number of stores from this group seen. We vectorize the last
627 one. */
628 unsigned int store_count;
629 /* For loads only, the gap from the previous load. For consecutive loads, GAP
630 is 1. */
631 unsigned int gap;
633 /* The minimum negative dependence distance this stmt participates in
634 or zero if none. */
635 unsigned int min_neg_dist;
637 /* Not all stmts in the loop need to be vectorized. e.g, the increment
638 of the loop induction variable and computation of array indexes. relevant
639 indicates whether the stmt needs to be vectorized. */
640 enum vect_relevant relevant;
642 /* The bb_vec_info with respect to which STMT is vectorized. */
643 bb_vec_info bb_vinfo;
645 /* Is this statement vectorizable or should it be skipped in (partial)
646 vectorization. */
647 bool vectorizable;
649 /* For loads only, true if this is a gather load. */
650 bool gather_p;
652 /* True if this is an access with loop-invariant stride. */
653 bool strided_p;
655 /* For both loads and stores. */
656 bool simd_lane_access_p;
657 } *stmt_vec_info;
659 /* Access Functions. */
660 #define STMT_VINFO_TYPE(S) (S)->type
661 #define STMT_VINFO_STMT(S) (S)->stmt
662 #define STMT_VINFO_LOOP_VINFO(S) (S)->loop_vinfo
663 #define STMT_VINFO_BB_VINFO(S) (S)->bb_vinfo
664 #define STMT_VINFO_RELEVANT(S) (S)->relevant
665 #define STMT_VINFO_LIVE_P(S) (S)->live
666 #define STMT_VINFO_VECTYPE(S) (S)->vectype
667 #define STMT_VINFO_VEC_STMT(S) (S)->vectorized_stmt
668 #define STMT_VINFO_VECTORIZABLE(S) (S)->vectorizable
669 #define STMT_VINFO_DATA_REF(S) (S)->data_ref_info
670 #define STMT_VINFO_GATHER_P(S) (S)->gather_p
671 #define STMT_VINFO_STRIDED_P(S) (S)->strided_p
672 #define STMT_VINFO_SIMD_LANE_ACCESS_P(S) (S)->simd_lane_access_p
674 #define STMT_VINFO_DR_BASE_ADDRESS(S) (S)->dr_base_address
675 #define STMT_VINFO_DR_INIT(S) (S)->dr_init
676 #define STMT_VINFO_DR_OFFSET(S) (S)->dr_offset
677 #define STMT_VINFO_DR_STEP(S) (S)->dr_step
678 #define STMT_VINFO_DR_ALIGNED_TO(S) (S)->dr_aligned_to
680 #define STMT_VINFO_IN_PATTERN_P(S) (S)->in_pattern_p
681 #define STMT_VINFO_RELATED_STMT(S) (S)->related_stmt
682 #define STMT_VINFO_PATTERN_DEF_SEQ(S) (S)->pattern_def_seq
683 #define STMT_VINFO_SAME_ALIGN_REFS(S) (S)->same_align_refs
684 #define STMT_VINFO_SIMD_CLONE_INFO(S) (S)->simd_clone_info
685 #define STMT_VINFO_DEF_TYPE(S) (S)->def_type
686 #define STMT_VINFO_GROUP_FIRST_ELEMENT(S) (S)->first_element
687 #define STMT_VINFO_GROUP_NEXT_ELEMENT(S) (S)->next_element
688 #define STMT_VINFO_GROUP_SIZE(S) (S)->size
689 #define STMT_VINFO_GROUP_STORE_COUNT(S) (S)->store_count
690 #define STMT_VINFO_GROUP_GAP(S) (S)->gap
691 #define STMT_VINFO_GROUP_SAME_DR_STMT(S) (S)->same_dr_stmt
692 #define STMT_VINFO_GROUPED_ACCESS(S) ((S)->first_element != NULL && (S)->data_ref_info)
693 #define STMT_VINFO_LOOP_PHI_EVOLUTION_PART(S) (S)->loop_phi_evolution_part
694 #define STMT_VINFO_MIN_NEG_DIST(S) (S)->min_neg_dist
696 #define GROUP_FIRST_ELEMENT(S) (S)->first_element
697 #define GROUP_NEXT_ELEMENT(S) (S)->next_element
698 #define GROUP_SIZE(S) (S)->size
699 #define GROUP_STORE_COUNT(S) (S)->store_count
700 #define GROUP_GAP(S) (S)->gap
701 #define GROUP_SAME_DR_STMT(S) (S)->same_dr_stmt
703 #define STMT_VINFO_RELEVANT_P(S) ((S)->relevant != vect_unused_in_scope)
705 #define HYBRID_SLP_STMT(S) ((S)->slp_type == hybrid)
706 #define PURE_SLP_STMT(S) ((S)->slp_type == pure_slp)
707 #define STMT_SLP_TYPE(S) (S)->slp_type
709 struct dataref_aux {
710 tree base_decl;
711 bool base_misaligned;
712 int misalignment;
715 #define VECT_MAX_COST 1000
717 /* The maximum number of intermediate steps required in multi-step type
718 conversion. */
719 #define MAX_INTERM_CVT_STEPS 3
721 /* The maximum vectorization factor supported by any target (V64QI). */
722 #define MAX_VECTORIZATION_FACTOR 64
724 /* Avoid GTY(()) on stmt_vec_info. */
725 typedef void *vec_void_p;
727 extern vec<vec_void_p> stmt_vec_info_vec;
729 void init_stmt_vec_info_vec (void);
730 void free_stmt_vec_info_vec (void);
732 /* Return a stmt_vec_info corresponding to STMT. */
734 static inline stmt_vec_info
735 vinfo_for_stmt (gimple stmt)
737 unsigned int uid = gimple_uid (stmt);
738 if (uid == 0)
739 return NULL;
741 return (stmt_vec_info) stmt_vec_info_vec[uid - 1];
744 /* Set vectorizer information INFO for STMT. */
746 static inline void
747 set_vinfo_for_stmt (gimple stmt, stmt_vec_info info)
749 unsigned int uid = gimple_uid (stmt);
750 if (uid == 0)
752 gcc_checking_assert (info);
753 uid = stmt_vec_info_vec.length () + 1;
754 gimple_set_uid (stmt, uid);
755 stmt_vec_info_vec.safe_push ((vec_void_p) info);
757 else
758 stmt_vec_info_vec[uid - 1] = (vec_void_p) info;
761 /* Return the earlier statement between STMT1 and STMT2. */
763 static inline gimple
764 get_earlier_stmt (gimple stmt1, gimple stmt2)
766 unsigned int uid1, uid2;
768 if (stmt1 == NULL)
769 return stmt2;
771 if (stmt2 == NULL)
772 return stmt1;
774 uid1 = gimple_uid (stmt1);
775 uid2 = gimple_uid (stmt2);
777 if (uid1 == 0 || uid2 == 0)
778 return NULL;
780 gcc_checking_assert (uid1 <= stmt_vec_info_vec.length ()
781 && uid2 <= stmt_vec_info_vec.length ());
783 if (uid1 < uid2)
784 return stmt1;
785 else
786 return stmt2;
789 /* Return the later statement between STMT1 and STMT2. */
791 static inline gimple
792 get_later_stmt (gimple stmt1, gimple stmt2)
794 unsigned int uid1, uid2;
796 if (stmt1 == NULL)
797 return stmt2;
799 if (stmt2 == NULL)
800 return stmt1;
802 uid1 = gimple_uid (stmt1);
803 uid2 = gimple_uid (stmt2);
805 if (uid1 == 0 || uid2 == 0)
806 return NULL;
808 gcc_assert (uid1 <= stmt_vec_info_vec.length ());
809 gcc_assert (uid2 <= stmt_vec_info_vec.length ());
811 if (uid1 > uid2)
812 return stmt1;
813 else
814 return stmt2;
817 /* Return TRUE if a statement represented by STMT_INFO is a part of a
818 pattern. */
820 static inline bool
821 is_pattern_stmt_p (stmt_vec_info stmt_info)
823 gimple related_stmt;
824 stmt_vec_info related_stmt_info;
826 related_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
827 if (related_stmt
828 && (related_stmt_info = vinfo_for_stmt (related_stmt))
829 && STMT_VINFO_IN_PATTERN_P (related_stmt_info))
830 return true;
832 return false;
835 /* Return true if BB is a loop header. */
837 static inline bool
838 is_loop_header_bb_p (basic_block bb)
840 if (bb == (bb->loop_father)->header)
841 return true;
842 gcc_checking_assert (EDGE_COUNT (bb->preds) == 1);
843 return false;
846 /* Return pow2 (X). */
848 static inline int
849 vect_pow2 (int x)
851 int i, res = 1;
853 for (i = 0; i < x; i++)
854 res *= 2;
856 return res;
859 /* Alias targetm.vectorize.builtin_vectorization_cost. */
861 static inline int
862 builtin_vectorization_cost (enum vect_cost_for_stmt type_of_cost,
863 tree vectype, int misalign)
865 return targetm.vectorize.builtin_vectorization_cost (type_of_cost,
866 vectype, misalign);
869 /* Get cost by calling cost target builtin. */
871 static inline
872 int vect_get_stmt_cost (enum vect_cost_for_stmt type_of_cost)
874 return builtin_vectorization_cost (type_of_cost, NULL, 0);
877 /* Alias targetm.vectorize.init_cost. */
879 static inline void *
880 init_cost (struct loop *loop_info)
882 return targetm.vectorize.init_cost (loop_info);
885 /* Alias targetm.vectorize.add_stmt_cost. */
887 static inline unsigned
888 add_stmt_cost (void *data, int count, enum vect_cost_for_stmt kind,
889 stmt_vec_info stmt_info, int misalign,
890 enum vect_cost_model_location where)
892 return targetm.vectorize.add_stmt_cost (data, count, kind,
893 stmt_info, misalign, where);
896 /* Alias targetm.vectorize.finish_cost. */
898 static inline void
899 finish_cost (void *data, unsigned *prologue_cost,
900 unsigned *body_cost, unsigned *epilogue_cost)
902 targetm.vectorize.finish_cost (data, prologue_cost, body_cost, epilogue_cost);
905 /* Alias targetm.vectorize.destroy_cost_data. */
907 static inline void
908 destroy_cost_data (void *data)
910 targetm.vectorize.destroy_cost_data (data);
914 /*-----------------------------------------------------------------*/
915 /* Info on data references alignment. */
916 /*-----------------------------------------------------------------*/
917 inline void
918 set_dr_misalignment (struct data_reference *dr, int val)
920 dataref_aux *data_aux = (dataref_aux *) dr->aux;
922 if (!data_aux)
924 data_aux = XCNEW (dataref_aux);
925 dr->aux = data_aux;
928 data_aux->misalignment = val;
931 inline int
932 dr_misalignment (struct data_reference *dr)
934 gcc_assert (dr->aux);
935 return ((dataref_aux *) dr->aux)->misalignment;
938 /* Reflects actual alignment of first access in the vectorized loop,
939 taking into account peeling/versioning if applied. */
940 #define DR_MISALIGNMENT(DR) dr_misalignment (DR)
941 #define SET_DR_MISALIGNMENT(DR, VAL) set_dr_misalignment (DR, VAL)
943 /* Return TRUE if the data access is aligned, and FALSE otherwise. */
945 static inline bool
946 aligned_access_p (struct data_reference *data_ref_info)
948 return (DR_MISALIGNMENT (data_ref_info) == 0);
951 /* Return TRUE if the alignment of the data access is known, and FALSE
952 otherwise. */
954 static inline bool
955 known_alignment_for_access_p (struct data_reference *data_ref_info)
957 return (DR_MISALIGNMENT (data_ref_info) != -1);
961 /* Return true if the vect cost model is unlimited. */
962 static inline bool
963 unlimited_cost_model (loop_p loop)
965 if (loop != NULL && loop->force_vectorize
966 && flag_simd_cost_model != VECT_COST_MODEL_DEFAULT)
967 return flag_simd_cost_model == VECT_COST_MODEL_UNLIMITED;
968 return (flag_vect_cost_model == VECT_COST_MODEL_UNLIMITED);
971 /* Source location */
972 extern source_location vect_location;
974 /*-----------------------------------------------------------------*/
975 /* Function prototypes. */
976 /*-----------------------------------------------------------------*/
978 /* Simple loop peeling and versioning utilities for vectorizer's purposes -
979 in tree-vect-loop-manip.c. */
980 extern void slpeel_make_loop_iterate_ntimes (struct loop *, tree);
981 extern bool slpeel_can_duplicate_loop_p (const struct loop *, const_edge);
982 struct loop *slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *,
983 struct loop *, edge);
984 extern void vect_loop_versioning (loop_vec_info, unsigned int, bool);
985 extern void vect_do_peeling_for_loop_bound (loop_vec_info, tree, tree,
986 unsigned int, bool);
987 extern void vect_do_peeling_for_alignment (loop_vec_info, tree,
988 unsigned int, bool);
989 extern source_location find_loop_location (struct loop *);
990 extern bool vect_can_advance_ivs_p (loop_vec_info);
992 /* In tree-vect-stmts.c. */
993 extern unsigned int current_vector_size;
994 extern tree get_vectype_for_scalar_type (tree);
995 extern tree get_same_sized_vectype (tree, tree);
996 extern bool vect_is_simple_use (tree, gimple, loop_vec_info,
997 bb_vec_info, gimple *,
998 tree *, enum vect_def_type *);
999 extern bool vect_is_simple_use_1 (tree, gimple, loop_vec_info,
1000 bb_vec_info, gimple *,
1001 tree *, enum vect_def_type *, tree *);
1002 extern bool supportable_widening_operation (enum tree_code, gimple, tree, tree,
1003 enum tree_code *, enum tree_code *,
1004 int *, vec<tree> *);
1005 extern bool supportable_narrowing_operation (enum tree_code, tree, tree,
1006 enum tree_code *,
1007 int *, vec<tree> *);
1008 extern stmt_vec_info new_stmt_vec_info (gimple stmt, loop_vec_info,
1009 bb_vec_info);
1010 extern void free_stmt_vec_info (gimple stmt);
1011 extern tree vectorizable_function (gcall *, tree, tree);
1012 extern void vect_model_simple_cost (stmt_vec_info, int, enum vect_def_type *,
1013 stmt_vector_for_cost *,
1014 stmt_vector_for_cost *);
1015 extern void vect_model_store_cost (stmt_vec_info, int, bool,
1016 enum vect_def_type, slp_tree,
1017 stmt_vector_for_cost *,
1018 stmt_vector_for_cost *);
1019 extern void vect_model_load_cost (stmt_vec_info, int, bool, slp_tree,
1020 stmt_vector_for_cost *,
1021 stmt_vector_for_cost *);
1022 extern unsigned record_stmt_cost (stmt_vector_for_cost *, int,
1023 enum vect_cost_for_stmt, stmt_vec_info,
1024 int, enum vect_cost_model_location);
1025 extern void vect_finish_stmt_generation (gimple, gimple,
1026 gimple_stmt_iterator *);
1027 extern bool vect_mark_stmts_to_be_vectorized (loop_vec_info);
1028 extern tree vect_get_vec_def_for_operand (tree, gimple, tree *);
1029 extern tree vect_init_vector (gimple, tree, tree,
1030 gimple_stmt_iterator *);
1031 extern tree vect_get_vec_def_for_stmt_copy (enum vect_def_type, tree);
1032 extern bool vect_transform_stmt (gimple, gimple_stmt_iterator *,
1033 bool *, slp_tree, slp_instance);
1034 extern void vect_remove_stores (gimple);
1035 extern bool vect_analyze_stmt (gimple, bool *, slp_tree);
1036 extern bool vectorizable_condition (gimple, gimple_stmt_iterator *, gimple *,
1037 tree, int, slp_tree);
1038 extern void vect_get_load_cost (struct data_reference *, int, bool,
1039 unsigned int *, unsigned int *,
1040 stmt_vector_for_cost *,
1041 stmt_vector_for_cost *, bool);
1042 extern void vect_get_store_cost (struct data_reference *, int,
1043 unsigned int *, stmt_vector_for_cost *);
1044 extern bool vect_supportable_shift (enum tree_code, tree);
1045 extern void vect_get_vec_defs (tree, tree, gimple, vec<tree> *,
1046 vec<tree> *, slp_tree, int);
1047 extern tree vect_gen_perm_mask_any (tree, const unsigned char *);
1048 extern tree vect_gen_perm_mask_checked (tree, const unsigned char *);
1050 /* In tree-vect-data-refs.c. */
1051 extern bool vect_can_force_dr_alignment_p (const_tree, unsigned int);
1052 extern enum dr_alignment_support vect_supportable_dr_alignment
1053 (struct data_reference *, bool);
1054 extern tree vect_get_smallest_scalar_type (gimple, HOST_WIDE_INT *,
1055 HOST_WIDE_INT *);
1056 extern bool vect_analyze_data_ref_dependences (loop_vec_info, int *);
1057 extern bool vect_slp_analyze_data_ref_dependences (bb_vec_info);
1058 extern bool vect_enhance_data_refs_alignment (loop_vec_info);
1059 extern bool vect_analyze_data_refs_alignment (loop_vec_info, bb_vec_info);
1060 extern bool vect_verify_datarefs_alignment (loop_vec_info, bb_vec_info);
1061 extern bool vect_analyze_data_ref_accesses (loop_vec_info, bb_vec_info);
1062 extern bool vect_prune_runtime_alias_test_list (loop_vec_info);
1063 extern tree vect_check_gather (gimple, loop_vec_info, tree *, tree *,
1064 int *);
1065 extern bool vect_analyze_data_refs (loop_vec_info, bb_vec_info, int *,
1066 unsigned *);
1067 extern tree vect_create_data_ref_ptr (gimple, tree, struct loop *, tree,
1068 tree *, gimple_stmt_iterator *,
1069 gimple *, bool, bool *,
1070 tree = NULL_TREE);
1071 extern tree bump_vector_ptr (tree, gimple, gimple_stmt_iterator *, gimple, tree);
1072 extern tree vect_create_destination_var (tree, tree);
1073 extern bool vect_grouped_store_supported (tree, unsigned HOST_WIDE_INT);
1074 extern bool vect_store_lanes_supported (tree, unsigned HOST_WIDE_INT);
1075 extern bool vect_grouped_load_supported (tree, unsigned HOST_WIDE_INT);
1076 extern bool vect_load_lanes_supported (tree, unsigned HOST_WIDE_INT);
1077 extern void vect_permute_store_chain (vec<tree> ,unsigned int, gimple,
1078 gimple_stmt_iterator *, vec<tree> *);
1079 extern tree vect_setup_realignment (gimple, gimple_stmt_iterator *, tree *,
1080 enum dr_alignment_support, tree,
1081 struct loop **);
1082 extern void vect_transform_grouped_load (gimple, vec<tree> , int,
1083 gimple_stmt_iterator *);
1084 extern void vect_record_grouped_load_vectors (gimple, vec<tree> );
1085 extern tree vect_get_new_vect_var (tree, enum vect_var_kind, const char *);
1086 extern tree vect_create_addr_base_for_vector_ref (gimple, gimple_seq *,
1087 tree, struct loop *,
1088 tree = NULL_TREE);
1090 /* In tree-vect-loop.c. */
1091 /* FORNOW: Used in tree-parloops.c. */
1092 extern void destroy_loop_vec_info (loop_vec_info, bool);
1093 extern gimple vect_force_simple_reduction (loop_vec_info, gimple, bool, bool *);
1094 /* Drive for loop analysis stage. */
1095 extern loop_vec_info vect_analyze_loop (struct loop *);
1096 /* Drive for loop transformation stage. */
1097 extern void vect_transform_loop (loop_vec_info);
1098 extern loop_vec_info vect_analyze_loop_form (struct loop *);
1099 extern bool vectorizable_live_operation (gimple, gimple_stmt_iterator *,
1100 gimple *);
1101 extern bool vectorizable_reduction (gimple, gimple_stmt_iterator *, gimple *,
1102 slp_tree);
1103 extern bool vectorizable_induction (gimple, gimple_stmt_iterator *, gimple *);
1104 extern tree get_initial_def_for_reduction (gimple, tree, tree *);
1105 extern int vect_min_worthwhile_factor (enum tree_code);
1106 extern int vect_get_known_peeling_cost (loop_vec_info, int, int *,
1107 stmt_vector_for_cost *,
1108 stmt_vector_for_cost *,
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_slp_analyze_operations (vec<slp_instance> slp_instances,
1117 void *);
1118 extern bool vect_schedule_slp (loop_vec_info, bb_vec_info);
1119 extern bool vect_analyze_slp (loop_vec_info, bb_vec_info, unsigned);
1120 extern bool vect_make_slp_decision (loop_vec_info);
1121 extern void vect_detect_hybrid_slp (loop_vec_info);
1122 extern void vect_get_slp_defs (vec<tree> , slp_tree,
1123 vec<vec<tree> > *, int);
1125 extern source_location find_bb_location (basic_block);
1126 extern bb_vec_info vect_slp_analyze_bb (basic_block);
1127 extern void vect_slp_transform_bb (basic_block);
1129 /* In tree-vect-patterns.c. */
1130 /* Pattern recognition functions.
1131 Additional pattern recognition functions can (and will) be added
1132 in the future. */
1133 typedef gimple (* vect_recog_func_ptr) (vec<gimple> *, tree *, tree *);
1134 #define NUM_PATTERNS 12
1135 void vect_pattern_recog (loop_vec_info, bb_vec_info);
1137 /* In tree-vectorizer.c. */
1138 unsigned vectorize_loops (void);
1139 void vect_destroy_datarefs (loop_vec_info, bb_vec_info);
1141 #endif /* GCC_TREE_VECTORIZER_H */