2014-01-24 Ed Smith-Rowland <3dw4rd@verizon.net>
[official-gcc.git] / gcc / tree-vectorizer.h
blob51367ea2500b01e26872e357c9c670b65b91604b
1 /* Vectorizer
2 Copyright (C) 2003-2014 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"
26 #include "hash-table.h"
28 /* Used for naming of new temporaries. */
29 enum vect_var_kind {
30 vect_simple_var,
31 vect_pointer_var,
32 vect_scalar_var
35 /* Defines type of operation. */
36 enum operation_type {
37 unary_op = 1,
38 binary_op,
39 ternary_op
42 /* Define type of available alignment support. */
43 enum dr_alignment_support {
44 dr_unaligned_unsupported,
45 dr_unaligned_supported,
46 dr_explicit_realign,
47 dr_explicit_realign_optimized,
48 dr_aligned
51 /* Define type of def-use cross-iteration cycle. */
52 enum vect_def_type {
53 vect_uninitialized_def = 0,
54 vect_constant_def = 1,
55 vect_external_def,
56 vect_internal_def,
57 vect_induction_def,
58 vect_reduction_def,
59 vect_double_reduction_def,
60 vect_nested_cycle,
61 vect_unknown_def_type
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 {
71 int count;
72 enum vect_cost_for_stmt kind;
73 gimple stmt;
74 int misalign;
75 } stmt_info_for_cost;
78 typedef vec<stmt_info_for_cost> stmt_vector_for_cost;
80 static inline void
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;
85 si.count = count;
86 si.kind = kind;
87 si.stmt = stmt;
88 si.misalign = misalign;
89 stmt_cost_vec->safe_push (si);
92 /************************************************************************
93 SLP
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. */
99 struct _slp_tree {
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. */
103 vec<gimple> stmts;
104 /* Load permutation relative to the stores, NULL if there is no
105 permutation. */
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;
117 /* SLP instance is a sequence of stmts in a loop that can be packed into
118 SIMD stmts. */
119 typedef struct _slp_instance {
120 /* The root of SLP tree. */
121 slp_tree root;
123 /* Size of groups of scalar stmts that will be replaced by SIMD stmt/s. */
124 unsigned int group_size;
126 /* The unrolling factor required to vectorized this SLP instance. */
127 unsigned int unrolling_factor;
129 /* Vectorization costs associated with SLP instance. */
130 stmt_vector_for_cost body_cost_vec;
132 /* The group of nodes that contain loads of this SLP instance. */
133 vec<slp_tree> loads;
135 /* The first scalar load of the instance. The created vector loads will be
136 inserted before this statement. */
137 gimple first_load;
138 } *slp_instance;
141 /* Access Functions. */
142 #define SLP_INSTANCE_TREE(S) (S)->root
143 #define SLP_INSTANCE_GROUP_SIZE(S) (S)->group_size
144 #define SLP_INSTANCE_UNROLLING_FACTOR(S) (S)->unrolling_factor
145 #define SLP_INSTANCE_BODY_COST_VEC(S) (S)->body_cost_vec
146 #define SLP_INSTANCE_LOADS(S) (S)->loads
147 #define SLP_INSTANCE_FIRST_LOAD_STMT(S) (S)->first_load
149 #define SLP_TREE_CHILDREN(S) (S)->children
150 #define SLP_TREE_SCALAR_STMTS(S) (S)->stmts
151 #define SLP_TREE_VEC_STMTS(S) (S)->vec_stmts
152 #define SLP_TREE_NUMBER_OF_VEC_STMTS(S) (S)->vec_stmts_size
153 #define SLP_TREE_LOAD_PERMUTATION(S) (S)->load_permutation
155 /* This structure is used in creation of an SLP tree. Each instance
156 corresponds to the same operand in a group of scalar stmts in an SLP
157 node. */
158 typedef struct _slp_oprnd_info
160 /* Def-stmts for the operands. */
161 vec<gimple> def_stmts;
162 /* Information about the first statement, its vector def-type, type, the
163 operand itself in case it's constant, and an indication if it's a pattern
164 stmt. */
165 enum vect_def_type first_dt;
166 tree first_op_type;
167 bool first_pattern;
168 } *slp_oprnd_info;
172 /* This struct is used to store the information of a data reference,
173 including the data ref itself, the access offset (calculated by summing its
174 offset and init) and the segment length for aliasing checks.
175 This is used to merge alias checks. */
177 struct dr_with_seg_len
179 dr_with_seg_len (data_reference_p d, tree len)
180 : dr (d),
181 offset (size_binop (PLUS_EXPR, DR_OFFSET (d), DR_INIT (d))),
182 seg_len (len) {}
184 data_reference_p dr;
185 tree offset;
186 tree seg_len;
189 /* This struct contains two dr_with_seg_len objects with aliasing data
190 refs. Two comparisons are generated from them. */
192 struct dr_with_seg_len_pair_t
194 dr_with_seg_len_pair_t (const dr_with_seg_len& d1,
195 const dr_with_seg_len& d2)
196 : first (d1), second (d2) {}
198 dr_with_seg_len first;
199 dr_with_seg_len second;
203 typedef struct _vect_peel_info
205 int npeel;
206 struct data_reference *dr;
207 unsigned int count;
208 } *vect_peel_info;
210 typedef struct _vect_peel_extended_info
212 struct _vect_peel_info peel_info;
213 unsigned int inside_cost;
214 unsigned int outside_cost;
215 stmt_vector_for_cost body_cost_vec;
216 } *vect_peel_extended_info;
219 /* Peeling hashtable helpers. */
221 struct peel_info_hasher : typed_free_remove <_vect_peel_info>
223 typedef _vect_peel_info value_type;
224 typedef _vect_peel_info compare_type;
225 static inline hashval_t hash (const value_type *);
226 static inline bool equal (const value_type *, const compare_type *);
229 inline hashval_t
230 peel_info_hasher::hash (const value_type *peel_info)
232 return (hashval_t) peel_info->npeel;
235 inline bool
236 peel_info_hasher::equal (const value_type *a, const compare_type *b)
238 return (a->npeel == b->npeel);
242 /*-----------------------------------------------------------------*/
243 /* Info on vectorized loops. */
244 /*-----------------------------------------------------------------*/
245 typedef struct _loop_vec_info {
247 /* The loop to which this info struct refers to. */
248 struct loop *loop;
250 /* The loop basic blocks. */
251 basic_block *bbs;
253 /* Number of latch executions. */
254 tree num_itersm1;
255 /* Number of iterations. */
256 tree num_iters;
257 /* Number of iterations of the original loop. */
258 tree num_iters_unchanged;
260 /* Minimum number of iterations below which vectorization is expected to
261 not be profitable (as estimated by the cost model).
262 -1 indicates that vectorization will not be profitable.
263 FORNOW: This field is an int. Will be a tree in the future, to represent
264 values unknown at compile time. */
265 int min_profitable_iters;
267 /* Is the loop vectorizable? */
268 bool vectorizable;
270 /* Unrolling factor */
271 int vectorization_factor;
273 /* Unknown DRs according to which loop was peeled. */
274 struct data_reference *unaligned_dr;
276 /* peeling_for_alignment indicates whether peeling for alignment will take
277 place, and what the peeling factor should be:
278 peeling_for_alignment = X means:
279 If X=0: Peeling for alignment will not be applied.
280 If X>0: Peel first X iterations.
281 If X=-1: Generate a runtime test to calculate the number of iterations
282 to be peeled, using the dataref recorded in the field
283 unaligned_dr. */
284 int peeling_for_alignment;
286 /* The mask used to check the alignment of pointers or arrays. */
287 int ptr_mask;
289 /* The loop nest in which the data dependences are computed. */
290 vec<loop_p> loop_nest;
292 /* All data references in the loop. */
293 vec<data_reference_p> datarefs;
295 /* All data dependences in the loop. */
296 vec<ddr_p> ddrs;
298 /* Data Dependence Relations defining address ranges that are candidates
299 for a run-time aliasing check. */
300 vec<ddr_p> may_alias_ddrs;
302 /* Data Dependence Relations defining address ranges together with segment
303 lengths from which the run-time aliasing check is built. */
304 vec<dr_with_seg_len_pair_t> comp_alias_ddrs;
306 /* Statements in the loop that have data references that are candidates for a
307 runtime (loop versioning) misalignment check. */
308 vec<gimple> may_misalign_stmts;
310 /* All interleaving chains of stores in the loop, represented by the first
311 stmt in the chain. */
312 vec<gimple> grouped_stores;
314 /* All SLP instances in the loop. This is a subset of the set of GROUP_STORES
315 of the loop. */
316 vec<slp_instance> slp_instances;
318 /* The unrolling factor needed to SLP the loop. In case of that pure SLP is
319 applied to the loop, i.e., no unrolling is needed, this is 1. */
320 unsigned slp_unrolling_factor;
322 /* Reduction cycles detected in the loop. Used in loop-aware SLP. */
323 vec<gimple> reductions;
325 /* All reduction chains in the loop, represented by the first
326 stmt in the chain. */
327 vec<gimple> reduction_chains;
329 /* Hash table used to choose the best peeling option. */
330 hash_table <peel_info_hasher> peeling_htab;
332 /* Cost data used by the target cost model. */
333 void *target_cost_data;
335 /* When we have grouped data accesses with gaps, we may introduce invalid
336 memory accesses. We peel the last iteration of the loop to prevent
337 this. */
338 bool peeling_for_gaps;
340 /* When the number of iterations is not a multiple of the vector size
341 we need to peel off iterations at the end to form an epilogue loop. */
342 bool peeling_for_niter;
344 /* Reductions are canonicalized so that the last operand is the reduction
345 operand. If this places a constant into RHS1, this decanonicalizes
346 GIMPLE for other phases, so we must track when this has occurred and
347 fix it up. */
348 bool operands_swapped;
350 /* True if there are no loop carried data dependencies in the loop.
351 If loop->safelen <= 1, then this is always true, either the loop
352 didn't have any loop carried data dependencies, or the loop is being
353 vectorized guarded with some runtime alias checks, or couldn't
354 be vectorized at all, but then this field shouldn't be used.
355 For loop->safelen >= 2, the user has asserted that there are no
356 backward dependencies, but there still could be loop carried forward
357 dependencies in such loops. This flag will be false if normal
358 vectorizer data dependency analysis would fail or require versioning
359 for alias, but because of loop->safelen >= 2 it has been vectorized
360 even without versioning for alias. E.g. in:
361 #pragma omp simd
362 for (int i = 0; i < m; i++)
363 a[i] = a[i + k] * c;
364 (or #pragma simd or #pragma ivdep) we can vectorize this and it will
365 DTRT even for k > 0 && k < m, but without safelen we would not
366 vectorize this, so this field would be false. */
367 bool no_data_dependencies;
369 /* If if-conversion versioned this loop before conversion, this is the
370 loop version without if-conversion. */
371 struct loop *scalar_loop;
373 } *loop_vec_info;
375 /* Access Functions. */
376 #define LOOP_VINFO_LOOP(L) (L)->loop
377 #define LOOP_VINFO_BBS(L) (L)->bbs
378 #define LOOP_VINFO_NITERSM1(L) (L)->num_itersm1
379 #define LOOP_VINFO_NITERS(L) (L)->num_iters
380 /* Since LOOP_VINFO_NITERS and LOOP_VINFO_NITERSM1 can change after
381 prologue peeling retain total unchanged scalar loop iterations for
382 cost model. */
383 #define LOOP_VINFO_NITERS_UNCHANGED(L) (L)->num_iters_unchanged
384 #define LOOP_VINFO_COST_MODEL_MIN_ITERS(L) (L)->min_profitable_iters
385 #define LOOP_VINFO_VECTORIZABLE_P(L) (L)->vectorizable
386 #define LOOP_VINFO_VECT_FACTOR(L) (L)->vectorization_factor
387 #define LOOP_VINFO_PTR_MASK(L) (L)->ptr_mask
388 #define LOOP_VINFO_LOOP_NEST(L) (L)->loop_nest
389 #define LOOP_VINFO_DATAREFS(L) (L)->datarefs
390 #define LOOP_VINFO_DDRS(L) (L)->ddrs
391 #define LOOP_VINFO_INT_NITERS(L) (TREE_INT_CST_LOW ((L)->num_iters))
392 #define LOOP_VINFO_PEELING_FOR_ALIGNMENT(L) (L)->peeling_for_alignment
393 #define LOOP_VINFO_UNALIGNED_DR(L) (L)->unaligned_dr
394 #define LOOP_VINFO_MAY_MISALIGN_STMTS(L) (L)->may_misalign_stmts
395 #define LOOP_VINFO_MAY_ALIAS_DDRS(L) (L)->may_alias_ddrs
396 #define LOOP_VINFO_COMP_ALIAS_DDRS(L) (L)->comp_alias_ddrs
397 #define LOOP_VINFO_GROUPED_STORES(L) (L)->grouped_stores
398 #define LOOP_VINFO_SLP_INSTANCES(L) (L)->slp_instances
399 #define LOOP_VINFO_SLP_UNROLLING_FACTOR(L) (L)->slp_unrolling_factor
400 #define LOOP_VINFO_REDUCTIONS(L) (L)->reductions
401 #define LOOP_VINFO_REDUCTION_CHAINS(L) (L)->reduction_chains
402 #define LOOP_VINFO_PEELING_HTAB(L) (L)->peeling_htab
403 #define LOOP_VINFO_TARGET_COST_DATA(L) (L)->target_cost_data
404 #define LOOP_VINFO_PEELING_FOR_GAPS(L) (L)->peeling_for_gaps
405 #define LOOP_VINFO_OPERANDS_SWAPPED(L) (L)->operands_swapped
406 #define LOOP_VINFO_PEELING_FOR_NITER(L) (L)->peeling_for_niter
407 #define LOOP_VINFO_NO_DATA_DEPENDENCIES(L) (L)->no_data_dependencies
408 #define LOOP_VINFO_SCALAR_LOOP(L) (L)->scalar_loop
410 #define LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT(L) \
411 (L)->may_misalign_stmts.length () > 0
412 #define LOOP_REQUIRES_VERSIONING_FOR_ALIAS(L) \
413 (L)->may_alias_ddrs.length () > 0
415 #define LOOP_VINFO_NITERS_KNOWN_P(L) \
416 (tree_fits_shwi_p ((L)->num_iters) && tree_to_shwi ((L)->num_iters) > 0)
418 static inline loop_vec_info
419 loop_vec_info_for_loop (struct loop *loop)
421 return (loop_vec_info) loop->aux;
424 static inline bool
425 nested_in_vect_loop_p (struct loop *loop, gimple stmt)
427 return (loop->inner
428 && (loop->inner == (gimple_bb (stmt))->loop_father));
431 typedef struct _bb_vec_info {
433 basic_block bb;
434 /* All interleaving chains of stores in the basic block, represented by the
435 first stmt in the chain. */
436 vec<gimple> grouped_stores;
438 /* All SLP instances in the basic block. This is a subset of the set of
439 GROUP_STORES of the basic block. */
440 vec<slp_instance> slp_instances;
442 /* All data references in the basic block. */
443 vec<data_reference_p> datarefs;
445 /* All data dependences in the basic block. */
446 vec<ddr_p> ddrs;
448 /* Cost data used by the target cost model. */
449 void *target_cost_data;
451 } *bb_vec_info;
453 #define BB_VINFO_BB(B) (B)->bb
454 #define BB_VINFO_GROUPED_STORES(B) (B)->grouped_stores
455 #define BB_VINFO_SLP_INSTANCES(B) (B)->slp_instances
456 #define BB_VINFO_DATAREFS(B) (B)->datarefs
457 #define BB_VINFO_DDRS(B) (B)->ddrs
458 #define BB_VINFO_TARGET_COST_DATA(B) (B)->target_cost_data
460 static inline bb_vec_info
461 vec_info_for_bb (basic_block bb)
463 return (bb_vec_info) bb->aux;
466 /*-----------------------------------------------------------------*/
467 /* Info on vectorized defs. */
468 /*-----------------------------------------------------------------*/
469 enum stmt_vec_info_type {
470 undef_vec_info_type = 0,
471 load_vec_info_type,
472 store_vec_info_type,
473 shift_vec_info_type,
474 op_vec_info_type,
475 call_vec_info_type,
476 call_simd_clone_vec_info_type,
477 assignment_vec_info_type,
478 condition_vec_info_type,
479 reduc_vec_info_type,
480 induc_vec_info_type,
481 type_promotion_vec_info_type,
482 type_demotion_vec_info_type,
483 type_conversion_vec_info_type,
484 loop_exit_ctrl_vec_info_type
487 /* Indicates whether/how a variable is used in the scope of loop/basic
488 block. */
489 enum vect_relevant {
490 vect_unused_in_scope = 0,
491 /* The def is in the inner loop, and the use is in the outer loop, and the
492 use is a reduction stmt. */
493 vect_used_in_outer_by_reduction,
494 /* The def is in the inner loop, and the use is in the outer loop (and is
495 not part of reduction). */
496 vect_used_in_outer,
498 /* defs that feed computations that end up (only) in a reduction. These
499 defs may be used by non-reduction stmts, but eventually, any
500 computations/values that are affected by these defs are used to compute
501 a reduction (i.e. don't get stored to memory, for example). We use this
502 to identify computations that we can change the order in which they are
503 computed. */
504 vect_used_by_reduction,
506 vect_used_in_scope
509 /* The type of vectorization that can be applied to the stmt: regular loop-based
510 vectorization; pure SLP - the stmt is a part of SLP instances and does not
511 have uses outside SLP instances; or hybrid SLP and loop-based - the stmt is
512 a part of SLP instance and also must be loop-based vectorized, since it has
513 uses outside SLP sequences.
515 In the loop context the meanings of pure and hybrid SLP are slightly
516 different. By saying that pure SLP is applied to the loop, we mean that we
517 exploit only intra-iteration parallelism in the loop; i.e., the loop can be
518 vectorized without doing any conceptual unrolling, cause we don't pack
519 together stmts from different iterations, only within a single iteration.
520 Loop hybrid SLP means that we exploit both intra-iteration and
521 inter-iteration parallelism (e.g., number of elements in the vector is 4
522 and the slp-group-size is 2, in which case we don't have enough parallelism
523 within an iteration, so we obtain the rest of the parallelism from subsequent
524 iterations by unrolling the loop by 2). */
525 enum slp_vect_type {
526 loop_vect = 0,
527 pure_slp,
528 hybrid
532 typedef struct data_reference *dr_p;
534 typedef struct _stmt_vec_info {
536 enum stmt_vec_info_type type;
538 /* Indicates whether this stmts is part of a computation whose result is
539 used outside the loop. */
540 bool live;
542 /* Stmt is part of some pattern (computation idiom) */
543 bool in_pattern_p;
545 /* The stmt to which this info struct refers to. */
546 gimple stmt;
548 /* The loop_vec_info with respect to which STMT is vectorized. */
549 loop_vec_info loop_vinfo;
551 /* The vector type to be used for the LHS of this statement. */
552 tree vectype;
554 /* The vectorized version of the stmt. */
555 gimple vectorized_stmt;
558 /** The following is relevant only for stmts that contain a non-scalar
559 data-ref (array/pointer/struct access). A GIMPLE stmt is expected to have
560 at most one such data-ref. **/
562 /* Information about the data-ref (access function, etc),
563 relative to the inner-most containing loop. */
564 struct data_reference *data_ref_info;
566 /* Information about the data-ref relative to this loop
567 nest (the loop that is being considered for vectorization). */
568 tree dr_base_address;
569 tree dr_init;
570 tree dr_offset;
571 tree dr_step;
572 tree dr_aligned_to;
574 /* For loop PHI nodes, the evolution part of it. This makes sure
575 this information is still available in vect_update_ivs_after_vectorizer
576 where we may not be able to re-analyze the PHI nodes evolution as
577 peeling for the prologue loop can make it unanalyzable. The evolution
578 part is still correct though. */
579 tree loop_phi_evolution_part;
581 /* Used for various bookkeeping purposes, generally holding a pointer to
582 some other stmt S that is in some way "related" to this stmt.
583 Current use of this field is:
584 If this stmt is part of a pattern (i.e. the field 'in_pattern_p' is
585 true): S is the "pattern stmt" that represents (and replaces) the
586 sequence of stmts that constitutes the pattern. Similarly, the
587 related_stmt of the "pattern stmt" points back to this stmt (which is
588 the last stmt in the original sequence of stmts that constitutes the
589 pattern). */
590 gimple related_stmt;
592 /* Used to keep a sequence of def stmts of a pattern stmt if such exists. */
593 gimple_seq pattern_def_seq;
595 /* List of datarefs that are known to have the same alignment as the dataref
596 of this stmt. */
597 vec<dr_p> same_align_refs;
599 /* Selected SIMD clone's function decl. */
600 tree simd_clone_fndecl;
602 /* Classify the def of this stmt. */
603 enum vect_def_type def_type;
605 /* Whether the stmt is SLPed, loop-based vectorized, or both. */
606 enum slp_vect_type slp_type;
608 /* Interleaving and reduction chains info. */
609 /* First element in the group. */
610 gimple first_element;
611 /* Pointer to the next element in the group. */
612 gimple next_element;
613 /* For data-refs, in case that two or more stmts share data-ref, this is the
614 pointer to the previously detected stmt with the same dr. */
615 gimple same_dr_stmt;
616 /* The size of the group. */
617 unsigned int size;
618 /* For stores, number of stores from this group seen. We vectorize the last
619 one. */
620 unsigned int store_count;
621 /* For loads only, the gap from the previous load. For consecutive loads, GAP
622 is 1. */
623 unsigned int gap;
625 /* Not all stmts in the loop need to be vectorized. e.g, the increment
626 of the loop induction variable and computation of array indexes. relevant
627 indicates whether the stmt needs to be vectorized. */
628 enum vect_relevant relevant;
630 /* The bb_vec_info with respect to which STMT is vectorized. */
631 bb_vec_info bb_vinfo;
633 /* Is this statement vectorizable or should it be skipped in (partial)
634 vectorization. */
635 bool vectorizable;
637 /* For loads only, true if this is a gather load. */
638 bool gather_p;
639 bool stride_load_p;
641 /* For both loads and stores. */
642 bool simd_lane_access_p;
643 } *stmt_vec_info;
645 /* Access Functions. */
646 #define STMT_VINFO_TYPE(S) (S)->type
647 #define STMT_VINFO_STMT(S) (S)->stmt
648 #define STMT_VINFO_LOOP_VINFO(S) (S)->loop_vinfo
649 #define STMT_VINFO_BB_VINFO(S) (S)->bb_vinfo
650 #define STMT_VINFO_RELEVANT(S) (S)->relevant
651 #define STMT_VINFO_LIVE_P(S) (S)->live
652 #define STMT_VINFO_VECTYPE(S) (S)->vectype
653 #define STMT_VINFO_VEC_STMT(S) (S)->vectorized_stmt
654 #define STMT_VINFO_VECTORIZABLE(S) (S)->vectorizable
655 #define STMT_VINFO_DATA_REF(S) (S)->data_ref_info
656 #define STMT_VINFO_GATHER_P(S) (S)->gather_p
657 #define STMT_VINFO_STRIDE_LOAD_P(S) (S)->stride_load_p
658 #define STMT_VINFO_SIMD_LANE_ACCESS_P(S) (S)->simd_lane_access_p
660 #define STMT_VINFO_DR_BASE_ADDRESS(S) (S)->dr_base_address
661 #define STMT_VINFO_DR_INIT(S) (S)->dr_init
662 #define STMT_VINFO_DR_OFFSET(S) (S)->dr_offset
663 #define STMT_VINFO_DR_STEP(S) (S)->dr_step
664 #define STMT_VINFO_DR_ALIGNED_TO(S) (S)->dr_aligned_to
666 #define STMT_VINFO_IN_PATTERN_P(S) (S)->in_pattern_p
667 #define STMT_VINFO_RELATED_STMT(S) (S)->related_stmt
668 #define STMT_VINFO_PATTERN_DEF_SEQ(S) (S)->pattern_def_seq
669 #define STMT_VINFO_SAME_ALIGN_REFS(S) (S)->same_align_refs
670 #define STMT_VINFO_SIMD_CLONE_FNDECL(S) (S)->simd_clone_fndecl
671 #define STMT_VINFO_DEF_TYPE(S) (S)->def_type
672 #define STMT_VINFO_GROUP_FIRST_ELEMENT(S) (S)->first_element
673 #define STMT_VINFO_GROUP_NEXT_ELEMENT(S) (S)->next_element
674 #define STMT_VINFO_GROUP_SIZE(S) (S)->size
675 #define STMT_VINFO_GROUP_STORE_COUNT(S) (S)->store_count
676 #define STMT_VINFO_GROUP_GAP(S) (S)->gap
677 #define STMT_VINFO_GROUP_SAME_DR_STMT(S) (S)->same_dr_stmt
678 #define STMT_VINFO_GROUPED_ACCESS(S) ((S)->first_element != NULL && (S)->data_ref_info)
679 #define STMT_VINFO_LOOP_PHI_EVOLUTION_PART(S) (S)->loop_phi_evolution_part
681 #define GROUP_FIRST_ELEMENT(S) (S)->first_element
682 #define GROUP_NEXT_ELEMENT(S) (S)->next_element
683 #define GROUP_SIZE(S) (S)->size
684 #define GROUP_STORE_COUNT(S) (S)->store_count
685 #define GROUP_GAP(S) (S)->gap
686 #define GROUP_SAME_DR_STMT(S) (S)->same_dr_stmt
688 #define STMT_VINFO_RELEVANT_P(S) ((S)->relevant != vect_unused_in_scope)
690 #define HYBRID_SLP_STMT(S) ((S)->slp_type == hybrid)
691 #define PURE_SLP_STMT(S) ((S)->slp_type == pure_slp)
692 #define STMT_SLP_TYPE(S) (S)->slp_type
694 struct dataref_aux {
695 tree base_decl;
696 bool base_misaligned;
697 int misalignment;
700 #define VECT_MAX_COST 1000
702 /* The maximum number of intermediate steps required in multi-step type
703 conversion. */
704 #define MAX_INTERM_CVT_STEPS 3
706 /* The maximum vectorization factor supported by any target (V64QI). */
707 #define MAX_VECTORIZATION_FACTOR 64
709 /* Avoid GTY(()) on stmt_vec_info. */
710 typedef void *vec_void_p;
712 extern vec<vec_void_p> stmt_vec_info_vec;
714 void init_stmt_vec_info_vec (void);
715 void free_stmt_vec_info_vec (void);
717 /* Return a stmt_vec_info corresponding to STMT. */
719 static inline stmt_vec_info
720 vinfo_for_stmt (gimple stmt)
722 unsigned int uid = gimple_uid (stmt);
723 if (uid == 0)
724 return NULL;
726 return (stmt_vec_info) stmt_vec_info_vec[uid - 1];
729 /* Set vectorizer information INFO for STMT. */
731 static inline void
732 set_vinfo_for_stmt (gimple stmt, stmt_vec_info info)
734 unsigned int uid = gimple_uid (stmt);
735 if (uid == 0)
737 gcc_checking_assert (info);
738 uid = stmt_vec_info_vec.length () + 1;
739 gimple_set_uid (stmt, uid);
740 stmt_vec_info_vec.safe_push ((vec_void_p) info);
742 else
743 stmt_vec_info_vec[uid - 1] = (vec_void_p) info;
746 /* Return the earlier statement between STMT1 and STMT2. */
748 static inline gimple
749 get_earlier_stmt (gimple stmt1, gimple stmt2)
751 unsigned int uid1, uid2;
753 if (stmt1 == NULL)
754 return stmt2;
756 if (stmt2 == NULL)
757 return stmt1;
759 uid1 = gimple_uid (stmt1);
760 uid2 = gimple_uid (stmt2);
762 if (uid1 == 0 || uid2 == 0)
763 return NULL;
765 gcc_checking_assert (uid1 <= stmt_vec_info_vec.length ()
766 && uid2 <= stmt_vec_info_vec.length ());
768 if (uid1 < uid2)
769 return stmt1;
770 else
771 return stmt2;
774 /* Return the later statement between STMT1 and STMT2. */
776 static inline gimple
777 get_later_stmt (gimple stmt1, gimple stmt2)
779 unsigned int uid1, uid2;
781 if (stmt1 == NULL)
782 return stmt2;
784 if (stmt2 == NULL)
785 return stmt1;
787 uid1 = gimple_uid (stmt1);
788 uid2 = gimple_uid (stmt2);
790 if (uid1 == 0 || uid2 == 0)
791 return NULL;
793 gcc_assert (uid1 <= stmt_vec_info_vec.length ());
794 gcc_assert (uid2 <= stmt_vec_info_vec.length ());
796 if (uid1 > uid2)
797 return stmt1;
798 else
799 return stmt2;
802 /* Return TRUE if a statement represented by STMT_INFO is a part of a
803 pattern. */
805 static inline bool
806 is_pattern_stmt_p (stmt_vec_info stmt_info)
808 gimple related_stmt;
809 stmt_vec_info related_stmt_info;
811 related_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
812 if (related_stmt
813 && (related_stmt_info = vinfo_for_stmt (related_stmt))
814 && STMT_VINFO_IN_PATTERN_P (related_stmt_info))
815 return true;
817 return false;
820 /* Return true if BB is a loop header. */
822 static inline bool
823 is_loop_header_bb_p (basic_block bb)
825 if (bb == (bb->loop_father)->header)
826 return true;
827 gcc_checking_assert (EDGE_COUNT (bb->preds) == 1);
828 return false;
831 /* Return pow2 (X). */
833 static inline int
834 vect_pow2 (int x)
836 int i, res = 1;
838 for (i = 0; i < x; i++)
839 res *= 2;
841 return res;
844 /* Alias targetm.vectorize.builtin_vectorization_cost. */
846 static inline int
847 builtin_vectorization_cost (enum vect_cost_for_stmt type_of_cost,
848 tree vectype, int misalign)
850 return targetm.vectorize.builtin_vectorization_cost (type_of_cost,
851 vectype, misalign);
854 /* Get cost by calling cost target builtin. */
856 static inline
857 int vect_get_stmt_cost (enum vect_cost_for_stmt type_of_cost)
859 return builtin_vectorization_cost (type_of_cost, NULL, 0);
862 /* Alias targetm.vectorize.init_cost. */
864 static inline void *
865 init_cost (struct loop *loop_info)
867 return targetm.vectorize.init_cost (loop_info);
870 /* Alias targetm.vectorize.add_stmt_cost. */
872 static inline unsigned
873 add_stmt_cost (void *data, int count, enum vect_cost_for_stmt kind,
874 stmt_vec_info stmt_info, int misalign,
875 enum vect_cost_model_location where)
877 return targetm.vectorize.add_stmt_cost (data, count, kind,
878 stmt_info, misalign, where);
881 /* Alias targetm.vectorize.finish_cost. */
883 static inline void
884 finish_cost (void *data, unsigned *prologue_cost,
885 unsigned *body_cost, unsigned *epilogue_cost)
887 targetm.vectorize.finish_cost (data, prologue_cost, body_cost, epilogue_cost);
890 /* Alias targetm.vectorize.destroy_cost_data. */
892 static inline void
893 destroy_cost_data (void *data)
895 targetm.vectorize.destroy_cost_data (data);
899 /*-----------------------------------------------------------------*/
900 /* Info on data references alignment. */
901 /*-----------------------------------------------------------------*/
902 inline void
903 set_dr_misalignment (struct data_reference *dr, int val)
905 dataref_aux *data_aux = (dataref_aux *) dr->aux;
907 if (!data_aux)
909 data_aux = XCNEW (dataref_aux);
910 dr->aux = data_aux;
913 data_aux->misalignment = val;
916 inline int
917 dr_misalignment (struct data_reference *dr)
919 gcc_assert (dr->aux);
920 return ((dataref_aux *) dr->aux)->misalignment;
923 /* Reflects actual alignment of first access in the vectorized loop,
924 taking into account peeling/versioning if applied. */
925 #define DR_MISALIGNMENT(DR) dr_misalignment (DR)
926 #define SET_DR_MISALIGNMENT(DR, VAL) set_dr_misalignment (DR, VAL)
928 /* Return TRUE if the data access is aligned, and FALSE otherwise. */
930 static inline bool
931 aligned_access_p (struct data_reference *data_ref_info)
933 return (DR_MISALIGNMENT (data_ref_info) == 0);
936 /* Return TRUE if the alignment of the data access is known, and FALSE
937 otherwise. */
939 static inline bool
940 known_alignment_for_access_p (struct data_reference *data_ref_info)
942 return (DR_MISALIGNMENT (data_ref_info) != -1);
946 /* Return true if the vect cost model is unlimited. */
947 static inline bool
948 unlimited_cost_model (loop_p loop)
950 if (loop != NULL && loop->force_vect
951 && flag_simd_cost_model != VECT_COST_MODEL_DEFAULT)
952 return flag_simd_cost_model == VECT_COST_MODEL_UNLIMITED;
953 return (flag_vect_cost_model == VECT_COST_MODEL_UNLIMITED);
956 /* Source location */
957 extern source_location vect_location;
959 /*-----------------------------------------------------------------*/
960 /* Function prototypes. */
961 /*-----------------------------------------------------------------*/
963 /* Simple loop peeling and versioning utilities for vectorizer's purposes -
964 in tree-vect-loop-manip.c. */
965 extern void slpeel_make_loop_iterate_ntimes (struct loop *, tree);
966 extern bool slpeel_can_duplicate_loop_p (const struct loop *, const_edge);
967 struct loop *slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *,
968 struct loop *, edge);
969 extern void vect_loop_versioning (loop_vec_info, unsigned int, bool);
970 extern void vect_do_peeling_for_loop_bound (loop_vec_info, tree, tree,
971 unsigned int, bool);
972 extern void vect_do_peeling_for_alignment (loop_vec_info, tree,
973 unsigned int, bool);
974 extern source_location find_loop_location (struct loop *);
975 extern bool vect_can_advance_ivs_p (loop_vec_info);
977 /* In tree-vect-stmts.c. */
978 extern unsigned int current_vector_size;
979 extern tree get_vectype_for_scalar_type (tree);
980 extern tree get_same_sized_vectype (tree, tree);
981 extern bool vect_is_simple_use (tree, gimple, loop_vec_info,
982 bb_vec_info, gimple *,
983 tree *, enum vect_def_type *);
984 extern bool vect_is_simple_use_1 (tree, gimple, loop_vec_info,
985 bb_vec_info, gimple *,
986 tree *, enum vect_def_type *, tree *);
987 extern bool supportable_widening_operation (enum tree_code, gimple, tree, tree,
988 enum tree_code *, enum tree_code *,
989 int *, vec<tree> *);
990 extern bool supportable_narrowing_operation (enum tree_code, tree, tree,
991 enum tree_code *,
992 int *, vec<tree> *);
993 extern stmt_vec_info new_stmt_vec_info (gimple stmt, loop_vec_info,
994 bb_vec_info);
995 extern void free_stmt_vec_info (gimple stmt);
996 extern tree vectorizable_function (gimple, tree, tree);
997 extern void vect_model_simple_cost (stmt_vec_info, int, enum vect_def_type *,
998 stmt_vector_for_cost *,
999 stmt_vector_for_cost *);
1000 extern void vect_model_store_cost (stmt_vec_info, int, bool,
1001 enum vect_def_type, slp_tree,
1002 stmt_vector_for_cost *,
1003 stmt_vector_for_cost *);
1004 extern void vect_model_load_cost (stmt_vec_info, int, bool, slp_tree,
1005 stmt_vector_for_cost *,
1006 stmt_vector_for_cost *);
1007 extern unsigned record_stmt_cost (stmt_vector_for_cost *, int,
1008 enum vect_cost_for_stmt, stmt_vec_info,
1009 int, enum vect_cost_model_location);
1010 extern void vect_finish_stmt_generation (gimple, gimple,
1011 gimple_stmt_iterator *);
1012 extern bool vect_mark_stmts_to_be_vectorized (loop_vec_info);
1013 extern tree vect_get_vec_def_for_operand (tree, gimple, tree *);
1014 extern tree vect_init_vector (gimple, tree, tree,
1015 gimple_stmt_iterator *);
1016 extern tree vect_get_vec_def_for_stmt_copy (enum vect_def_type, tree);
1017 extern bool vect_transform_stmt (gimple, gimple_stmt_iterator *,
1018 bool *, slp_tree, slp_instance);
1019 extern void vect_remove_stores (gimple);
1020 extern bool vect_analyze_stmt (gimple, bool *, slp_tree);
1021 extern bool vectorizable_condition (gimple, gimple_stmt_iterator *, gimple *,
1022 tree, int, slp_tree);
1023 extern void vect_get_load_cost (struct data_reference *, int, bool,
1024 unsigned int *, unsigned int *,
1025 stmt_vector_for_cost *,
1026 stmt_vector_for_cost *, bool);
1027 extern void vect_get_store_cost (struct data_reference *, int,
1028 unsigned int *, stmt_vector_for_cost *);
1029 extern bool vect_supportable_shift (enum tree_code, tree);
1030 extern void vect_get_vec_defs (tree, tree, gimple, vec<tree> *,
1031 vec<tree> *, slp_tree, int);
1032 extern tree vect_gen_perm_mask (tree, unsigned char *);
1034 /* In tree-vect-data-refs.c. */
1035 extern bool vect_can_force_dr_alignment_p (const_tree, unsigned int);
1036 extern enum dr_alignment_support vect_supportable_dr_alignment
1037 (struct data_reference *, bool);
1038 extern tree vect_get_smallest_scalar_type (gimple, HOST_WIDE_INT *,
1039 HOST_WIDE_INT *);
1040 extern bool vect_analyze_data_ref_dependences (loop_vec_info, int *);
1041 extern bool vect_slp_analyze_data_ref_dependences (bb_vec_info);
1042 extern bool vect_enhance_data_refs_alignment (loop_vec_info);
1043 extern bool vect_analyze_data_refs_alignment (loop_vec_info, bb_vec_info);
1044 extern bool vect_verify_datarefs_alignment (loop_vec_info, bb_vec_info);
1045 extern bool vect_analyze_data_ref_accesses (loop_vec_info, bb_vec_info);
1046 extern bool vect_prune_runtime_alias_test_list (loop_vec_info);
1047 extern tree vect_check_gather (gimple, loop_vec_info, tree *, tree *,
1048 int *);
1049 extern bool vect_analyze_data_refs (loop_vec_info, bb_vec_info, int *);
1050 extern tree vect_create_data_ref_ptr (gimple, tree, struct loop *, tree,
1051 tree *, gimple_stmt_iterator *,
1052 gimple *, bool, bool *);
1053 extern tree bump_vector_ptr (tree, gimple, gimple_stmt_iterator *, gimple, tree);
1054 extern tree vect_create_destination_var (tree, tree);
1055 extern bool vect_grouped_store_supported (tree, unsigned HOST_WIDE_INT);
1056 extern bool vect_store_lanes_supported (tree, unsigned HOST_WIDE_INT);
1057 extern bool vect_grouped_load_supported (tree, unsigned HOST_WIDE_INT);
1058 extern bool vect_load_lanes_supported (tree, unsigned HOST_WIDE_INT);
1059 extern void vect_permute_store_chain (vec<tree> ,unsigned int, gimple,
1060 gimple_stmt_iterator *, vec<tree> *);
1061 extern tree vect_setup_realignment (gimple, gimple_stmt_iterator *, tree *,
1062 enum dr_alignment_support, tree,
1063 struct loop **);
1064 extern void vect_transform_grouped_load (gimple, vec<tree> , int,
1065 gimple_stmt_iterator *);
1066 extern void vect_record_grouped_load_vectors (gimple, vec<tree> );
1067 extern tree vect_get_new_vect_var (tree, enum vect_var_kind, const char *);
1068 extern tree vect_create_addr_base_for_vector_ref (gimple, gimple_seq *,
1069 tree, struct loop *);
1071 /* In tree-vect-loop.c. */
1072 /* FORNOW: Used in tree-parloops.c. */
1073 extern void destroy_loop_vec_info (loop_vec_info, bool);
1074 extern gimple vect_force_simple_reduction (loop_vec_info, gimple, bool, bool *);
1075 /* Drive for loop analysis stage. */
1076 extern loop_vec_info vect_analyze_loop (struct loop *);
1077 /* Drive for loop transformation stage. */
1078 extern void vect_transform_loop (loop_vec_info);
1079 extern loop_vec_info vect_analyze_loop_form (struct loop *);
1080 extern bool vectorizable_live_operation (gimple, gimple_stmt_iterator *,
1081 gimple *);
1082 extern bool vectorizable_reduction (gimple, gimple_stmt_iterator *, gimple *,
1083 slp_tree);
1084 extern bool vectorizable_induction (gimple, gimple_stmt_iterator *, gimple *);
1085 extern tree get_initial_def_for_reduction (gimple, tree, tree *);
1086 extern int vect_min_worthwhile_factor (enum tree_code);
1087 extern int vect_get_known_peeling_cost (loop_vec_info, int, int *, int,
1088 stmt_vector_for_cost *,
1089 stmt_vector_for_cost *);
1090 extern int vect_get_single_scalar_iteration_cost (loop_vec_info);
1092 /* In tree-vect-slp.c. */
1093 extern void vect_free_slp_instance (slp_instance);
1094 extern bool vect_transform_slp_perm_load (slp_tree, vec<tree> ,
1095 gimple_stmt_iterator *, int,
1096 slp_instance, bool);
1097 extern bool vect_schedule_slp (loop_vec_info, bb_vec_info);
1098 extern void vect_update_slp_costs_according_to_vf (loop_vec_info);
1099 extern bool vect_analyze_slp (loop_vec_info, bb_vec_info);
1100 extern bool vect_make_slp_decision (loop_vec_info);
1101 extern void vect_detect_hybrid_slp (loop_vec_info);
1102 extern void vect_get_slp_defs (vec<tree> , slp_tree,
1103 vec<vec<tree> > *, int);
1105 extern source_location find_bb_location (basic_block);
1106 extern bb_vec_info vect_slp_analyze_bb (basic_block);
1107 extern void vect_slp_transform_bb (basic_block);
1109 /* In tree-vect-patterns.c. */
1110 /* Pattern recognition functions.
1111 Additional pattern recognition functions can (and will) be added
1112 in the future. */
1113 typedef gimple (* vect_recog_func_ptr) (vec<gimple> *, tree *, tree *);
1114 #define NUM_PATTERNS 11
1115 void vect_pattern_recog (loop_vec_info, bb_vec_info);
1117 /* In tree-vectorizer.c. */
1118 unsigned vectorize_loops (void);
1119 void vect_destroy_datarefs (loop_vec_info, bb_vec_info);
1121 #endif /* GCC_TREE_VECTORIZER_H */