Line data Source code
1 : /* Vectorizer
2 : Copyright (C) 2003-2026 Free Software Foundation, Inc.
3 : Contributed by Dorit Naishlos <dorit@il.ibm.com>
4 :
5 : This file is part of GCC.
6 :
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.
11 :
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.
16 :
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/>. */
20 :
21 : #ifndef GCC_TREE_VECTORIZER_H
22 : #define GCC_TREE_VECTORIZER_H
23 :
24 : typedef class _stmt_vec_info *stmt_vec_info;
25 : typedef struct _slp_tree *slp_tree;
26 :
27 : #include "tree-data-ref.h"
28 : #include "tree-hash-traits.h"
29 : #include "target.h"
30 : #include "internal-fn.h"
31 : #include "tree-ssa-operands.h"
32 : #include "gimple-match.h"
33 : #include "dominance.h"
34 : #include "ssa.h"
35 :
36 : /* Used for naming of new temporaries. */
37 : enum vect_var_kind {
38 : vect_simple_var,
39 : vect_pointer_var,
40 : vect_scalar_var,
41 : vect_mask_var
42 : };
43 :
44 : /* Defines type of operation. */
45 : enum operation_type {
46 : unary_op = 1,
47 : binary_op,
48 : ternary_op
49 : };
50 :
51 : /* Define type of available alignment support. */
52 : enum dr_alignment_support {
53 : dr_unaligned_unsupported,
54 : dr_unaligned_supported,
55 : dr_explicit_realign,
56 : dr_explicit_realign_optimized,
57 : dr_aligned
58 : };
59 :
60 : /* Define type of peeling support to indicate how peeling for alignment can help
61 : make vectorization supported. */
62 : enum peeling_support {
63 : peeling_known_supported,
64 : peeling_maybe_supported,
65 : peeling_unsupported
66 : };
67 :
68 : /* Define type of def-use cross-iteration cycle. */
69 : enum vect_def_type {
70 : vect_uninitialized_def = 0,
71 : vect_constant_def = 1,
72 : vect_external_def,
73 : vect_internal_def,
74 : vect_induction_def,
75 : vect_reduction_def,
76 : vect_double_reduction_def,
77 : vect_nested_cycle,
78 : vect_first_order_recurrence,
79 : vect_condition_def,
80 : vect_unknown_def_type
81 : };
82 :
83 : /* Define operation type of linear/non-linear induction variable. */
84 : enum vect_induction_op_type {
85 : vect_step_op_add = 0,
86 : vect_step_op_neg,
87 : vect_step_op_mul,
88 : vect_step_op_shl,
89 : vect_step_op_shr
90 : };
91 :
92 : /* Define type of reduction. */
93 : enum vect_reduction_type {
94 : TREE_CODE_REDUCTION,
95 : COND_REDUCTION,
96 : INTEGER_INDUC_COND_REDUCTION,
97 : CONST_COND_REDUCTION,
98 :
99 : /* Retain a scalar phi and use a FOLD_EXTRACT_LAST within the loop
100 : to implement:
101 :
102 : for (int i = 0; i < VF; ++i)
103 : res = cond[i] ? val[i] : res; */
104 : EXTRACT_LAST_REDUCTION,
105 :
106 : /* Use a folding reduction within the loop to implement:
107 :
108 : for (int i = 0; i < VF; ++i)
109 : res = res OP val[i];
110 :
111 : (with no reassociation). */
112 : FOLD_LEFT_REDUCTION
113 : };
114 :
115 : #define VECTORIZABLE_CYCLE_DEF(D) (((D) == vect_reduction_def) \
116 : || ((D) == vect_double_reduction_def) \
117 : || ((D) == vect_nested_cycle))
118 :
119 : /* Structure to encapsulate information about a group of like
120 : instructions to be presented to the target cost model. */
121 : struct stmt_info_for_cost {
122 : int count;
123 : enum vect_cost_for_stmt kind;
124 : enum vect_cost_model_location where;
125 : stmt_vec_info stmt_info;
126 : slp_tree node;
127 : tree vectype;
128 : int misalign;
129 : };
130 :
131 : typedef vec<stmt_info_for_cost> stmt_vector_for_cost;
132 :
133 : /* Maps base addresses to an innermost_loop_behavior and the stmt it was
134 : derived from that gives the maximum known alignment for that base. */
135 : typedef hash_map<tree_operand_hash,
136 : std::pair<stmt_vec_info, innermost_loop_behavior *> >
137 : vec_base_alignments;
138 :
139 : /* Represents elements [START, START + LENGTH) of cyclical array OPS*
140 : (i.e. OPS repeated to give at least START + LENGTH elements) */
141 : struct vect_scalar_ops_slice
142 : {
143 : tree op (unsigned int i) const;
144 : bool all_same_p () const;
145 :
146 : vec<tree> *ops;
147 : unsigned int start;
148 : unsigned int length;
149 : };
150 :
151 : /* Return element I of the slice. */
152 : inline tree
153 2737239 : vect_scalar_ops_slice::op (unsigned int i) const
154 : {
155 5474478 : return (*ops)[(i + start) % ops->length ()];
156 : }
157 :
158 : /* Hash traits for vect_scalar_ops_slice. */
159 : struct vect_scalar_ops_slice_hash : typed_noop_remove<vect_scalar_ops_slice>
160 : {
161 : typedef vect_scalar_ops_slice value_type;
162 : typedef vect_scalar_ops_slice compare_type;
163 :
164 : static const bool empty_zero_p = true;
165 :
166 : static void mark_deleted (value_type &s) { s.length = ~0U; }
167 0 : static void mark_empty (value_type &s) { s.length = 0; }
168 449529 : static bool is_deleted (const value_type &s) { return s.length == ~0U; }
169 4241414 : static bool is_empty (const value_type &s) { return s.length == 0; }
170 : static hashval_t hash (const value_type &);
171 : static bool equal (const value_type &, const compare_type &);
172 : };
173 :
174 : /* Describes how we're going to vectorize an individual load or store,
175 : or a group of loads or stores. */
176 : enum vect_memory_access_type {
177 : VMAT_UNINITIALIZED,
178 :
179 : /* An access to an invariant address. This is used only for loads. */
180 : VMAT_INVARIANT,
181 :
182 : /* A simple contiguous access. */
183 : VMAT_CONTIGUOUS,
184 :
185 : /* A contiguous access that goes down in memory rather than up,
186 : with no additional permutation. This is used only for stores
187 : of invariants. */
188 : VMAT_CONTIGUOUS_DOWN,
189 :
190 : /* A simple contiguous access in which the elements need to be reversed
191 : after loading or before storing. */
192 : VMAT_CONTIGUOUS_REVERSE,
193 :
194 : /* An access that uses IFN_LOAD_LANES or IFN_STORE_LANES. */
195 : VMAT_LOAD_STORE_LANES,
196 :
197 : /* An access in which each scalar element is loaded or stored
198 : individually. */
199 : VMAT_ELEMENTWISE,
200 :
201 : /* A hybrid of VMAT_CONTIGUOUS and VMAT_ELEMENTWISE, used for grouped
202 : SLP accesses. Each unrolled iteration uses a contiguous load
203 : or store for the whole group, but the groups from separate iterations
204 : are combined in the same way as for VMAT_ELEMENTWISE. */
205 : VMAT_STRIDED_SLP,
206 :
207 : /* The access uses gather loads or scatter stores. */
208 : VMAT_GATHER_SCATTER_LEGACY,
209 : VMAT_GATHER_SCATTER_IFN,
210 : VMAT_GATHER_SCATTER_EMULATED
211 : };
212 :
213 : /* Returns whether MAT is any of the VMAT_GATHER_SCATTER_* kinds. */
214 :
215 : inline bool
216 6674176 : mat_gather_scatter_p (vect_memory_access_type mat)
217 : {
218 6674176 : return (mat == VMAT_GATHER_SCATTER_LEGACY
219 : || mat == VMAT_GATHER_SCATTER_IFN
220 6674176 : || mat == VMAT_GATHER_SCATTER_EMULATED);
221 : }
222 :
223 : /*-----------------------------------------------------------------*/
224 : /* Info on vectorized defs. */
225 : /*-----------------------------------------------------------------*/
226 : enum stmt_vec_info_type {
227 : undef_vec_info_type = 0,
228 : load_vec_info_type,
229 : store_vec_info_type,
230 : shift_vec_info_type,
231 : op_vec_info_type,
232 : call_vec_info_type,
233 : call_simd_clone_vec_info_type,
234 : assignment_vec_info_type,
235 : condition_vec_info_type,
236 : comparison_vec_info_type,
237 : reduc_vec_info_type,
238 : induc_vec_info_type,
239 : type_promotion_vec_info_type,
240 : type_demotion_vec_info_type,
241 : type_conversion_vec_info_type,
242 : cycle_phi_info_type,
243 : lc_phi_info_type,
244 : phi_info_type,
245 : recurr_info_type,
246 : loop_exit_ctrl_vec_info_type,
247 : permute_info_type
248 : };
249 :
250 : /************************************************************************
251 : SLP
252 : ************************************************************************/
253 : typedef vec<std::pair<unsigned, unsigned> > lane_permutation_t;
254 : typedef auto_vec<std::pair<unsigned, unsigned>, 16> auto_lane_permutation_t;
255 : typedef vec<unsigned> load_permutation_t;
256 : typedef auto_vec<unsigned, 16> auto_load_permutation_t;
257 :
258 3433941 : struct vect_data {
259 2129892 : virtual ~vect_data () = default;
260 : };
261 :
262 : /* Analysis data from vectorizable_simd_clone_call for
263 : call_simd_clone_vec_info_type. */
264 : struct vect_simd_clone_data : vect_data {
265 1993 : virtual ~vect_simd_clone_data () = default;
266 1492 : vect_simd_clone_data () = default;
267 501 : vect_simd_clone_data (vect_simd_clone_data &&other) = default;
268 :
269 : /* Selected SIMD clone and clone for in-branch. */
270 : cgraph_node *clone;
271 : cgraph_node *clone_inbranch;
272 :
273 : /* Selected SIMD clone's function info. First vector element
274 : is NULL_TREE, followed by a pair of trees (base + step)
275 : for linear arguments (pair of NULLs for other arguments). */
276 : auto_vec<tree> simd_clone_info;
277 : };
278 :
279 : /* Analysis data from vectorizable_load and vectorizable_store for
280 : load_vec_info_type and store_vec_info_type. */
281 : struct vect_load_store_data : vect_data {
282 1302056 : vect_load_store_data (vect_load_store_data &&other) = default;
283 2129892 : vect_load_store_data () = default;
284 3431222 : virtual ~vect_load_store_data () = default;
285 :
286 : vect_memory_access_type memory_access_type;
287 : dr_alignment_support alignment_support_scheme;
288 : int misalignment;
289 : internal_fn lanes_ifn; // VMAT_LOAD_STORE_LANES
290 : poly_int64 poffset;
291 : union {
292 : internal_fn ifn; // VMAT_GATHER_SCATTER_IFN
293 : tree decl; // VMAT_GATHER_SCATTER_DECL
294 : } gs;
295 : tree strided_offset_vectype; // VMAT_GATHER_SCATTER_IFN, originally strided
296 : /* Load/store type with larger element mode used for punning the vectype. */
297 : tree ls_type; // VMAT_GATHER_SCATTER_IFN, VMAT_STRIDED_SLP
298 : /* Load/store element type used for punning the vectype. Relevant when
299 : that is a vector type. */
300 : tree ls_eltype; // VMAT_STRIDED_SLP
301 : /* This is set to a supported offset vector type if we don't support the
302 : originally requested offset type, otherwise NULL.
303 : If nonzero there will be an additional offset conversion before
304 : the gather/scatter. */
305 : tree supported_offset_vectype; // VMAT_GATHER_SCATTER_IFN
306 : /* Similar for scale. Only nonzero if we don't support the requested
307 : scale. Then we need to multiply the offset vector before the
308 : gather/scatter. */
309 : int supported_scale; // VMAT_GATHER_SCATTER_IFN
310 : auto_vec<int> elsvals;
311 : /* True if the load requires a load permutation. */
312 : bool slp_perm; // SLP_TREE_LOAD_PERMUTATION
313 : unsigned n_perms; // SLP_TREE_LOAD_PERMUTATION
314 : unsigned n_loads; // SLP_TREE_LOAD_PERMUTATION
315 : /* Whether the load permutation is consecutive and simple. */
316 : bool subchain_p; // VMAT_STRIDED_SLP and VMAT_GATHER_SCATTER
317 : };
318 :
319 : struct match_elt_t {
320 : int v;
321 : operator bool () const = delete;
322 : match_elt_t& operator= (bool) = delete;
323 43547542 : match_elt_t& operator= (int v_) { v = v_; return *this; }
324 : };
325 :
326 : inline bool operator!= (const match_elt_t &m, const match_elt_t &m2) { return m.v != m2.v; }
327 : inline bool operator== (const match_elt_t &m, const match_elt_t &m2) { return m.v == m2.v; }
328 46924983 : inline bool operator== (const match_elt_t &m, int v) { return m.v == v; }
329 41339507 : inline bool operator!= (const match_elt_t &m, int v) { return m.v != v; }
330 : inline bool operator< (const match_elt_t &m, int v) { return m.v < v; }
331 : inline bool operator> (const match_elt_t &m, int v) { return m.v > v; }
332 :
333 : /* A computation tree of an SLP instance. Each node corresponds to a group of
334 : stmts to be packed in a SIMD stmt. */
335 : struct _slp_tree {
336 : _slp_tree ();
337 : ~_slp_tree ();
338 :
339 : void push_vec_def (gimple *def);
340 12456 : void push_vec_def (tree def) { vec_defs.quick_push (def); }
341 :
342 : /* Nodes that contain def-stmts of this node statements operands. */
343 : vec<slp_tree> children;
344 :
345 : /* A group of scalar stmts to be vectorized together. Unused when
346 : def_type is vect_external_def or vect_costant_def. */
347 : vec<stmt_vec_info> stmts;
348 : /* A group of scalar operands to be vectorized together. Unused
349 : unless def_type is vect_external_def or vect_constant_def. */
350 : vec<tree> ops;
351 : /* A set of lane indices that are live and to be code-generated from
352 : this SLP node. */
353 : vec<unsigned> live_lanes;
354 :
355 : /* The representative that should be used for analysis and
356 : code generation. NULL when code is VEC_PERM_EXPR. */
357 : stmt_vec_info representative;
358 :
359 : struct {
360 : /* SLP cycle the node resides in, or -1. */
361 : int id;
362 : /* The SLP operand index with the edge on the SLP cycle, or -1. */
363 : int reduc_idx;
364 : } cycle_info;
365 :
366 : /* Load permutation mapping outgoing vector lanes to lanes of
367 : the single DR group the load accesses. NULL if there is no
368 : permutation. Unused when this is not a load. */
369 : load_permutation_t load_permutation;
370 : /* Lane permutation of the operands scalar lanes encoded as pairs
371 : of { operand number, lane number }. The number of elements
372 : denotes the number of output lanes. Unused unless code is
373 : VEC_PERM_EXPR. */
374 : lane_permutation_t lane_permutation;
375 :
376 : tree vectype;
377 : /* Vectorized defs. */
378 : vec<tree> vec_defs;
379 : /* Insertion place for verification purposes. Only set for
380 : BB vectorization. NULL denotes region entry. */
381 : gimple *si;
382 :
383 : /* Reference count in the SLP graph. */
384 : unsigned int refcnt;
385 : /* The DEF type of this node. */
386 : enum vect_def_type def_type;
387 : /* The number of scalar lanes produced by this node. */
388 : unsigned int lanes;
389 : /* The operation of this node. Either VEC_PERM_EXPR or ERROR_MARK. */
390 : enum tree_code code;
391 : /* For gather/scatter memory operations the scale each offset element
392 : should be multiplied by before being added to the base. */
393 : int gs_scale;
394 : /* For gather/scatter memory operations the loop-invariant base value. */
395 : tree gs_base;
396 : /* Whether uses of this load or feeders of this store are suitable
397 : for load/store-lanes. */
398 : bool ldst_lanes;
399 : /* For BB vect, flag to indicate this load node should be vectorized
400 : as to avoid STLF fails because of related stores. */
401 : bool avoid_stlf_fail;
402 :
403 : /* The vertex index of this node when a full graph is built. */
404 : int vertex;
405 :
406 : /* The kind of operation as determined by analysis and optional
407 : kind specific data. */
408 : enum stmt_vec_info_type type;
409 : vect_data *data;
410 :
411 : template <class T>
412 2131384 : T& get_data (T& else_) { return data ? *static_cast <T *> (data) : else_; }
413 :
414 : /* If not NULL this is a cached failed SLP discovery attempt with
415 : the lanes that failed during SLP discovery as 'false'. This is
416 : a copy of the matches array. */
417 : match_elt_t *failed;
418 :
419 : /* Allocate from slp_tree_pool. */
420 : static void *operator new (size_t);
421 :
422 : /* Return memory to slp_tree_pool. */
423 : static void operator delete (void *, size_t);
424 :
425 : /* Linked list of nodes to release when we free the slp_tree_pool. */
426 : slp_tree next_node;
427 : slp_tree prev_node;
428 : };
429 :
430 : /* The enum describes the type of operations that an SLP instance
431 : can perform. */
432 :
433 : enum slp_instance_kind {
434 : slp_inst_kind_store,
435 : slp_inst_kind_reduc_group,
436 : slp_inst_kind_reduc_chain,
437 : slp_inst_kind_bb_reduc,
438 : slp_inst_kind_ctor,
439 : slp_inst_kind_gcond
440 : };
441 :
442 : /* SLP instance is a sequence of stmts in a loop that can be packed into
443 : SIMD stmts. */
444 : typedef class _slp_instance {
445 : public:
446 : /* The root of SLP tree. */
447 : slp_tree root;
448 :
449 : /* For vector constructors, the constructor stmt that the SLP tree is built
450 : from, NULL otherwise. */
451 : vec<stmt_vec_info> root_stmts;
452 :
453 : /* For slp_inst_kind_bb_reduc the defs that were not vectorized, NULL
454 : otherwise. */
455 : vec<tree> remain_defs;
456 :
457 : /* The group of nodes that contain loads of this SLP instance. */
458 : vec<slp_tree> loads;
459 :
460 : /* The SLP node containing the reduction PHIs. */
461 : slp_tree reduc_phis;
462 :
463 : /* Vector cost of this entry to the SLP graph. */
464 : stmt_vector_for_cost cost_vec;
465 :
466 : /* If this instance is the main entry of a subgraph the set of
467 : entries into the same subgraph, including itself. */
468 : vec<_slp_instance *> subgraph_entries;
469 :
470 : /* The type of operation the SLP instance is performing. */
471 : slp_instance_kind kind;
472 :
473 : dump_user_location_t location () const;
474 : } *slp_instance;
475 :
476 :
477 : /* Access Functions. */
478 : #define SLP_INSTANCE_TREE(S) (S)->root
479 : #define SLP_INSTANCE_LOADS(S) (S)->loads
480 : #define SLP_INSTANCE_ROOT_STMTS(S) (S)->root_stmts
481 : #define SLP_INSTANCE_REMAIN_DEFS(S) (S)->remain_defs
482 : #define SLP_INSTANCE_KIND(S) (S)->kind
483 :
484 : #define SLP_TREE_CHILDREN(S) (S)->children
485 : #define SLP_TREE_SCALAR_STMTS(S) (S)->stmts
486 : #define SLP_TREE_SCALAR_OPS(S) (S)->ops
487 : #define SLP_TREE_LIVE_LANES(S) (S)->live_lanes
488 : #define SLP_TREE_REF_COUNT(S) (S)->refcnt
489 : #define SLP_TREE_VEC_DEFS(S) (S)->vec_defs
490 : #define SLP_TREE_LOAD_PERMUTATION(S) (S)->load_permutation
491 : #define SLP_TREE_LANE_PERMUTATION(S) (S)->lane_permutation
492 : #define SLP_TREE_DEF_TYPE(S) (S)->def_type
493 : #define SLP_TREE_VECTYPE(S) (S)->vectype
494 : #define SLP_TREE_REPRESENTATIVE(S) (S)->representative
495 : #define SLP_TREE_LANES(S) (S)->lanes
496 : #define SLP_TREE_CODE(S) (S)->code
497 : #define SLP_TREE_TYPE(S) (S)->type
498 : #define SLP_TREE_GS_SCALE(S) (S)->gs_scale
499 : #define SLP_TREE_GS_BASE(S) (S)->gs_base
500 : #define SLP_TREE_REDUC_IDX(S) (S)->cycle_info.reduc_idx
501 : #define SLP_TREE_PERMUTE_P(S) ((S)->code == VEC_PERM_EXPR)
502 :
503 : inline vect_memory_access_type
504 1072406 : SLP_TREE_MEMORY_ACCESS_TYPE (slp_tree node)
505 : {
506 385763 : if (SLP_TREE_TYPE (node) == load_vec_info_type
507 368253 : || SLP_TREE_TYPE (node) == store_vec_info_type)
508 117236 : return static_cast<vect_load_store_data *> (node->data)->memory_access_type;
509 : return VMAT_UNINITIALIZED;
510 : }
511 :
512 : enum vect_partial_vector_style {
513 : vect_partial_vectors_none,
514 : vect_partial_vectors_while_ult,
515 : vect_partial_vectors_avx512,
516 : vect_partial_vectors_len
517 : };
518 :
519 : /* Key for map that records association between
520 : scalar conditions and corresponding loop mask, and
521 : is populated by vect_record_loop_mask. */
522 :
523 : struct scalar_cond_masked_key
524 : {
525 60843 : scalar_cond_masked_key (tree t, unsigned ncopies_)
526 60843 : : ncopies (ncopies_)
527 : {
528 60843 : get_cond_ops_from_tree (t);
529 : }
530 :
531 : void get_cond_ops_from_tree (tree);
532 :
533 : unsigned ncopies;
534 : bool inverted_p;
535 : tree_code code;
536 : tree op0;
537 : tree op1;
538 : };
539 :
540 : template<>
541 : struct default_hash_traits<scalar_cond_masked_key>
542 : {
543 : typedef scalar_cond_masked_key compare_type;
544 : typedef scalar_cond_masked_key value_type;
545 :
546 : static inline hashval_t
547 69439 : hash (value_type v)
548 : {
549 69439 : inchash::hash h;
550 69439 : h.add_int (v.code);
551 69439 : inchash::add_expr (v.op0, h, 0);
552 69439 : inchash::add_expr (v.op1, h, 0);
553 69439 : h.add_int (v.ncopies);
554 69439 : h.add_flag (v.inverted_p);
555 69439 : return h.end ();
556 : }
557 :
558 : static inline bool
559 10440 : equal (value_type existing, value_type candidate)
560 : {
561 10440 : return (existing.ncopies == candidate.ncopies
562 10224 : && existing.code == candidate.code
563 6362 : && existing.inverted_p == candidate.inverted_p
564 4957 : && operand_equal_p (existing.op0, candidate.op0, 0)
565 13589 : && operand_equal_p (existing.op1, candidate.op1, 0));
566 : }
567 :
568 : static const bool empty_zero_p = true;
569 :
570 : static inline void
571 0 : mark_empty (value_type &v)
572 : {
573 0 : v.ncopies = 0;
574 0 : v.inverted_p = false;
575 : }
576 :
577 : static inline bool
578 8637654 : is_empty (value_type v)
579 : {
580 8577985 : return v.ncopies == 0;
581 : }
582 :
583 : static inline void mark_deleted (value_type &) {}
584 :
585 : static inline bool is_deleted (const value_type &)
586 : {
587 : return false;
588 : }
589 :
590 52501 : static inline void remove (value_type &) {}
591 : };
592 :
593 : typedef hash_set<scalar_cond_masked_key> scalar_cond_masked_set_type;
594 :
595 : /* Key and map that records association between vector conditions and
596 : corresponding loop mask, and is populated by prepare_vec_mask. */
597 :
598 : typedef pair_hash<tree_operand_hash, tree_operand_hash> tree_cond_mask_hash;
599 : typedef hash_set<tree_cond_mask_hash> vec_cond_masked_set_type;
600 :
601 : /* Describes two objects whose addresses must be unequal for the vectorized
602 : loop to be valid. */
603 : typedef std::pair<tree, tree> vec_object_pair;
604 :
605 : /* Records that vectorization is only possible if abs (EXPR) >= MIN_VALUE.
606 : UNSIGNED_P is true if we can assume that abs (EXPR) == EXPR. */
607 : class vec_lower_bound {
608 : public:
609 : vec_lower_bound () {}
610 1769 : vec_lower_bound (tree e, bool u, poly_uint64 m)
611 1769 : : expr (e), unsigned_p (u), min_value (m) {}
612 :
613 : tree expr;
614 : bool unsigned_p;
615 : poly_uint64 min_value;
616 : };
617 :
618 : /* Vectorizer state shared between different analyses like vector sizes
619 : of the same CFG region. */
620 : class vec_info_shared {
621 : public:
622 : vec_info_shared();
623 : ~vec_info_shared();
624 :
625 : void save_datarefs();
626 : void check_datarefs();
627 :
628 : /* All data references. Freed by free_data_refs, so not an auto_vec. */
629 : vec<data_reference_p> datarefs;
630 : vec<data_reference> datarefs_copy;
631 :
632 : /* The loop nest in which the data dependences are computed. */
633 : auto_vec<loop_p> loop_nest;
634 :
635 : /* All data dependences. Freed by free_dependence_relations, so not
636 : an auto_vec. */
637 : vec<ddr_p> ddrs;
638 : };
639 :
640 : /* Vectorizer state common between loop and basic-block vectorization. */
641 : class vec_info {
642 : public:
643 : typedef hash_set<int_hash<machine_mode, E_VOIDmode, E_BLKmode> > mode_set;
644 : enum vec_kind { bb, loop };
645 :
646 : vec_info (vec_kind, vec_info_shared *);
647 : ~vec_info ();
648 :
649 : stmt_vec_info add_stmt (gimple *);
650 : stmt_vec_info add_pattern_stmt (gimple *, stmt_vec_info);
651 : stmt_vec_info resync_stmt_addr (gimple *);
652 : stmt_vec_info lookup_stmt (gimple *);
653 : stmt_vec_info lookup_def (tree);
654 : stmt_vec_info lookup_single_use (tree);
655 : class dr_vec_info *lookup_dr (data_reference *);
656 : void move_dr (stmt_vec_info, stmt_vec_info);
657 : void remove_stmt (stmt_vec_info);
658 : void replace_stmt (gimple_stmt_iterator *, stmt_vec_info, gimple *);
659 : void insert_on_entry (stmt_vec_info, gimple *);
660 : void insert_seq_on_entry (stmt_vec_info, gimple_seq);
661 :
662 : /* The type of vectorization. */
663 : vec_kind kind;
664 :
665 : /* Shared vectorizer state. */
666 : vec_info_shared *shared;
667 :
668 : /* The mapping of GIMPLE UID to stmt_vec_info. */
669 : vec<stmt_vec_info> stmt_vec_infos;
670 : /* Whether the above mapping is complete. */
671 : bool stmt_vec_info_ro;
672 :
673 : /* Whether we've done a transform we think OK to not update virtual
674 : SSA form. */
675 : bool any_known_not_updated_vssa;
676 :
677 : /* The SLP graph. */
678 : auto_vec<slp_instance> slp_instances;
679 :
680 : /* Maps base addresses to an innermost_loop_behavior that gives the maximum
681 : known alignment for that base. */
682 : vec_base_alignments base_alignments;
683 :
684 : /* All interleaving chains of stores, represented by the first
685 : stmt in the chain. */
686 : auto_vec<stmt_vec_info> grouped_stores;
687 :
688 : /* The set of vector modes used in the vectorized region. */
689 : mode_set used_vector_modes;
690 :
691 : /* The argument we should pass to related_vector_mode when looking up
692 : the vector mode for a scalar mode, or VOIDmode if we haven't yet
693 : made any decisions about which vector modes to use. */
694 : machine_mode vector_mode;
695 :
696 : /* The basic blocks in the vectorization region. For _loop_vec_info,
697 : the memory is internally managed, while for _bb_vec_info, it points
698 : to element space of an external auto_vec<>. This inconsistency is
699 : not a good class design pattern. TODO: improve it with an unified
700 : auto_vec<> whose lifetime is confined to vec_info object. */
701 : basic_block *bbs;
702 :
703 : /* The count of the basic blocks in the vectorization region. */
704 : unsigned int nbbs;
705 :
706 : /* Used to keep a sequence of def stmts of a pattern stmt that are loop
707 : invariant if they exists.
708 : The sequence is emitted in the loop preheader should the loop be vectorized
709 : and are reset when undoing patterns. */
710 : gimple_seq inv_pattern_def_seq;
711 :
712 : private:
713 : stmt_vec_info new_stmt_vec_info (gimple *stmt);
714 : void set_vinfo_for_stmt (gimple *, stmt_vec_info, bool = true);
715 : void free_stmt_vec_infos ();
716 : void free_stmt_vec_info (stmt_vec_info);
717 : };
718 :
719 : class _loop_vec_info;
720 : class _bb_vec_info;
721 :
722 : template<>
723 : template<>
724 : inline bool
725 387375630 : is_a_helper <_loop_vec_info *>::test (vec_info *i)
726 : {
727 386698263 : return i->kind == vec_info::loop;
728 : }
729 :
730 : template<>
731 : template<>
732 : inline bool
733 78703858 : is_a_helper <_bb_vec_info *>::test (vec_info *i)
734 : {
735 78703858 : return i->kind == vec_info::bb;
736 : }
737 :
738 : /* In general, we can divide the vector statements in a vectorized loop
739 : into related groups ("rgroups") and say that for each rgroup there is
740 : some nS such that the rgroup operates on nS values from one scalar
741 : iteration followed by nS values from the next. That is, if VF is the
742 : vectorization factor of the loop, the rgroup operates on a sequence:
743 :
744 : (1,1) (1,2) ... (1,nS) (2,1) ... (2,nS) ... (VF,1) ... (VF,nS)
745 :
746 : where (i,j) represents a scalar value with index j in a scalar
747 : iteration with index i.
748 :
749 : [ We use the term "rgroup" to emphasise that this grouping isn't
750 : necessarily the same as the grouping of statements used elsewhere.
751 : For example, if we implement a group of scalar loads using gather
752 : loads, we'll use a separate gather load for each scalar load, and
753 : thus each gather load will belong to its own rgroup. ]
754 :
755 : In general this sequence will occupy nV vectors concatenated
756 : together. If these vectors have nL lanes each, the total number
757 : of scalar values N is given by:
758 :
759 : N = nS * VF = nV * nL
760 :
761 : None of nS, VF, nV and nL are required to be a power of 2. nS and nV
762 : are compile-time constants but VF and nL can be variable (if the target
763 : supports variable-length vectors).
764 :
765 : In classical vectorization, each iteration of the vector loop would
766 : handle exactly VF iterations of the original scalar loop. However,
767 : in vector loops that are able to operate on partial vectors, a
768 : particular iteration of the vector loop might handle fewer than VF
769 : iterations of the scalar loop. The vector lanes that correspond to
770 : iterations of the scalar loop are said to be "active" and the other
771 : lanes are said to be "inactive".
772 :
773 : In such vector loops, many rgroups need to be controlled to ensure
774 : that they have no effect for the inactive lanes. Conceptually, each
775 : such rgroup needs a sequence of booleans in the same order as above,
776 : but with each (i,j) replaced by a boolean that indicates whether
777 : iteration i is active. This sequence occupies nV vector controls
778 : that again have nL lanes each. Thus the control sequence as a whole
779 : consists of VF independent booleans that are each repeated nS times.
780 :
781 : Taking mask-based approach as a partially-populated vectors example.
782 : We make the simplifying assumption that if a sequence of nV masks is
783 : suitable for one (nS,nL) pair, we can reuse it for (nS/2,nL/2) by
784 : VIEW_CONVERTing it. This holds for all current targets that support
785 : fully-masked loops. For example, suppose the scalar loop is:
786 :
787 : float *f;
788 : double *d;
789 : for (int i = 0; i < n; ++i)
790 : {
791 : f[i * 2 + 0] += 1.0f;
792 : f[i * 2 + 1] += 2.0f;
793 : d[i] += 3.0;
794 : }
795 :
796 : and suppose that vectors have 256 bits. The vectorized f accesses
797 : will belong to one rgroup and the vectorized d access to another:
798 :
799 : f rgroup: nS = 2, nV = 1, nL = 8
800 : d rgroup: nS = 1, nV = 1, nL = 4
801 : VF = 4
802 :
803 : [ In this simple example the rgroups do correspond to the normal
804 : SLP grouping scheme. ]
805 :
806 : If only the first three lanes are active, the masks we need are:
807 :
808 : f rgroup: 1 1 | 1 1 | 1 1 | 0 0
809 : d rgroup: 1 | 1 | 1 | 0
810 :
811 : Here we can use a mask calculated for f's rgroup for d's, but not
812 : vice versa.
813 :
814 : Thus for each value of nV, it is enough to provide nV masks, with the
815 : mask being calculated based on the highest nL (or, equivalently, based
816 : on the highest nS) required by any rgroup with that nV. We therefore
817 : represent the entire collection of masks as a two-level table, with the
818 : first level being indexed by nV - 1 (since nV == 0 doesn't exist) and
819 : the second being indexed by the mask index 0 <= i < nV. */
820 :
821 : /* The controls (like masks or lengths) needed by rgroups with nV vectors,
822 : according to the description above. */
823 : struct rgroup_controls {
824 : /* The largest nS for all rgroups that use these controls.
825 : For vect_partial_vectors_avx512 this is the constant nscalars_per_iter
826 : for all members of the group. */
827 : unsigned int max_nscalars_per_iter;
828 :
829 : /* For the largest nS recorded above, the loop controls divide each scalar
830 : into FACTOR equal-sized pieces. This is useful if we need to split
831 : element-based accesses into byte-based accesses.
832 : For vect_partial_vectors_avx512 this records nV instead. */
833 : unsigned int factor;
834 :
835 : /* This is a vector type with MAX_NSCALARS_PER_ITER * VF / nV elements.
836 : For mask-based controls, it is the type of the masks in CONTROLS.
837 : For length-based controls, it can be any vector type that has the
838 : specified number of elements; the type of the elements doesn't matter. */
839 : tree type;
840 :
841 : /* When there is no uniformly used LOOP_VINFO_RGROUP_COMPARE_TYPE this
842 : is the rgroup specific type used. */
843 : tree compare_type;
844 :
845 : /* A vector of nV controls, in iteration order. */
846 : vec<tree> controls;
847 :
848 : /* In case of len_load and len_store with a bias there is only one
849 : rgroup. This holds the adjusted loop length for the this rgroup. */
850 : tree bias_adjusted_ctrl;
851 : };
852 :
853 541421 : struct vec_loop_masks
854 : {
855 546437 : bool is_empty () const { return mask_set.is_empty (); }
856 :
857 : /* Set to record vectype, nvector pairs. */
858 : hash_set<pair_hash <nofree_ptr_hash <tree_node>,
859 : int_hash<unsigned, 0>>> mask_set;
860 :
861 : /* rgroup_controls used for the partial vector scheme. */
862 : auto_vec<rgroup_controls> rgc_vec;
863 : };
864 :
865 : typedef auto_vec<rgroup_controls> vec_loop_lens;
866 :
867 : typedef auto_vec<std::pair<data_reference*, tree> > drs_init_vec;
868 :
869 : /* Abstraction around info on reductions which is still in stmt_vec_info
870 : but will be duplicated or moved elsewhere. */
871 204364 : class vect_reduc_info_s
872 : {
873 : public:
874 : /* The def type of the main reduction PHI, vect_reduction_def or
875 : vect_double_reduction_def. */
876 : enum vect_def_type def_type;
877 :
878 : /* The reduction type as detected by
879 : vect_is_simple_reduction and vectorizable_reduction. */
880 : enum vect_reduction_type reduc_type;
881 :
882 : /* The original scalar reduction code, to be used in the epilogue. */
883 : code_helper reduc_code;
884 :
885 : /* A vector internal function we should use in the epilogue. */
886 : internal_fn reduc_fn;
887 :
888 : /* For loop reduction with multiple vectorized results (ncopies > 1), a
889 : lane-reducing operation participating in it may not use all of those
890 : results, this field specifies result index starting from which any
891 : following land-reducing operation would be assigned to. */
892 : unsigned int reduc_result_pos;
893 :
894 : /* Whether this represents a reduction chain. */
895 : bool is_reduc_chain;
896 :
897 : /* Whether we force a single cycle PHI during reduction vectorization. */
898 : bool force_single_cycle;
899 :
900 : /* The vector type for performing the actual reduction operation. */
901 : tree reduc_vectype;
902 :
903 : /* The vector type we should use for the final reduction in the epilogue
904 : when we reduce a mask. */
905 : tree reduc_vectype_for_mask;
906 :
907 : /* The neutral operand to use, if any. */
908 : tree neutral_op;
909 :
910 : /* For INTEGER_INDUC_COND_REDUCTION, the initial value to be used. */
911 : tree induc_cond_initial_val;
912 :
913 : /* If not NULL the value to be added to compute final reduction value. */
914 : tree reduc_epilogue_adjustment;
915 :
916 : /* If non-null, the reduction is being performed by an epilogue loop
917 : and we have decided to reuse this accumulator from the main loop. */
918 : struct vect_reusable_accumulator *reused_accumulator;
919 :
920 : /* If the vector code is performing N scalar reductions in parallel,
921 : this variable gives the initial scalar values of those N reductions. */
922 : auto_vec<tree> reduc_initial_values;
923 :
924 : /* If the vector code is performing N scalar reductions in parallel, this
925 : variable gives the vectorized code's final (scalar) result for each of
926 : those N reductions. In other words, REDUC_SCALAR_RESULTS[I] replaces
927 : the original scalar code's loop-closed SSA PHI for reduction number I. */
928 : auto_vec<tree> reduc_scalar_results;
929 : };
930 :
931 : typedef class vect_reduc_info_s *vect_reduc_info;
932 :
933 : #define VECT_REDUC_INFO_DEF_TYPE(I) ((I)->def_type)
934 : #define VECT_REDUC_INFO_TYPE(I) ((I)->reduc_type)
935 : #define VECT_REDUC_INFO_CODE(I) ((I)->reduc_code)
936 : #define VECT_REDUC_INFO_FN(I) ((I)->reduc_fn)
937 : #define VECT_REDUC_INFO_SCALAR_RESULTS(I) ((I)->reduc_scalar_results)
938 : #define VECT_REDUC_INFO_INITIAL_VALUES(I) ((I)->reduc_initial_values)
939 : #define VECT_REDUC_INFO_REUSED_ACCUMULATOR(I) ((I)->reused_accumulator)
940 : #define VECT_REDUC_INFO_INDUC_COND_INITIAL_VAL(I) ((I)->induc_cond_initial_val)
941 : #define VECT_REDUC_INFO_EPILOGUE_ADJUSTMENT(I) ((I)->reduc_epilogue_adjustment)
942 : #define VECT_REDUC_INFO_VECTYPE(I) ((I)->reduc_vectype)
943 : #define VECT_REDUC_INFO_VECTYPE_FOR_MASK(I) ((I)->reduc_vectype_for_mask)
944 : #define VECT_REDUC_INFO_FORCE_SINGLE_CYCLE(I) ((I)->force_single_cycle)
945 : #define VECT_REDUC_INFO_RESULT_POS(I) ((I)->reduc_result_pos)
946 : #define VECT_REDUC_INFO_NEUTRAL_OP(I) ((I)->neutral_op)
947 :
948 : /* Information about a reduction accumulator from the main loop that could
949 : conceivably be reused as the input to a reduction in an epilogue loop. */
950 : struct vect_reusable_accumulator {
951 : /* The final value of the accumulator, which forms the input to the
952 : reduction operation. */
953 : tree reduc_input;
954 :
955 : /* The stmt_vec_info that describes the reduction (i.e. the one for
956 : which is_reduc_info is true). */
957 : vect_reduc_info reduc_info;
958 : };
959 :
960 : /*-----------------------------------------------------------------*/
961 : /* Info on vectorized loops. */
962 : /*-----------------------------------------------------------------*/
963 : typedef class _loop_vec_info : public vec_info {
964 : public:
965 : _loop_vec_info (class loop *, vec_info_shared *, basic_block *);
966 : ~_loop_vec_info ();
967 :
968 : /* The loop to which this info struct refers to. */
969 : class loop *loop;
970 :
971 : /* Number of latch executions. */
972 : tree num_itersm1;
973 : /* Number of iterations. */
974 : tree num_iters;
975 : /* Number of iterations of the original loop. */
976 : tree num_iters_unchanged;
977 : /* Condition under which this loop is analyzed and versioned. */
978 : tree num_iters_assumptions;
979 :
980 : /* The cost of the vector code. */
981 : class vector_costs *vector_costs;
982 :
983 : /* The cost of the scalar code. */
984 : class vector_costs *scalar_costs;
985 :
986 : /* Threshold of number of iterations below which vectorization will not be
987 : performed. It is calculated from MIN_PROFITABLE_ITERS and
988 : param_min_vect_loop_bound. */
989 : unsigned int th;
990 :
991 : /* When applying loop versioning, the vector form should only be used
992 : if the number of scalar iterations is >= this value, on top of all
993 : the other requirements. Ignored when loop versioning is not being
994 : used. */
995 : poly_uint64 versioning_threshold;
996 :
997 : /* Unrolling factor. In case of suitable super-word parallelism
998 : it can be that no unrolling is needed, and thus this is 1. */
999 : poly_uint64 vectorization_factor;
1000 :
1001 : /* Gimple operand for the number of scalar iteration handed per loop
1002 : iteration, and therefore how much to increment each IV by. */
1003 : tree iv_increment;
1004 :
1005 : /* If this loop is an epilogue loop whose main loop can be skipped,
1006 : MAIN_LOOP_EDGE is the edge from the main loop to this loop's
1007 : preheader. SKIP_MAIN_LOOP_EDGE is then the edge that skips the
1008 : main loop and goes straight to this loop's preheader.
1009 :
1010 : Both fields are null otherwise. */
1011 : edge main_loop_edge;
1012 : edge skip_main_loop_edge;
1013 :
1014 : /* If this loop is an epilogue loop that might be skipped after executing
1015 : the main loop, this edge is the one that skips the epilogue. */
1016 : edge skip_this_loop_edge;
1017 :
1018 : /* Reduction descriptors of this loop. Referenced to from SLP nodes
1019 : by index. */
1020 : auto_vec<vect_reduc_info> reduc_infos;
1021 :
1022 : /* The vectorized form of a standard reduction replaces the original
1023 : scalar code's final result (a loop-closed SSA PHI) with the result
1024 : of a vector-to-scalar reduction operation. After vectorization,
1025 : this variable maps these vector-to-scalar results to information
1026 : about the reductions that generated them. */
1027 : hash_map<tree, vect_reusable_accumulator> reusable_accumulators;
1028 :
1029 : /* The number of times that the target suggested we unroll the vector loop
1030 : in order to promote more ILP. This value will be used to re-analyze the
1031 : loop for vectorization and if successful the value will be folded into
1032 : vectorization_factor (and therefore exactly divides
1033 : vectorization_factor). */
1034 : unsigned int suggested_unroll_factor;
1035 :
1036 : /* Maximum runtime vectorization factor, or MAX_VECTORIZATION_FACTOR
1037 : if there is no particular limit. */
1038 : unsigned HOST_WIDE_INT max_vectorization_factor;
1039 :
1040 : /* The masks that a fully-masked loop should use to avoid operating
1041 : on inactive scalars. */
1042 : vec_loop_masks masks;
1043 :
1044 : /* The lengths that a loop with length should use to avoid operating
1045 : on inactive scalars. */
1046 : vec_loop_lens lens;
1047 :
1048 : /* Set of scalar conditions that have loop mask applied. */
1049 : scalar_cond_masked_set_type scalar_cond_masked_set;
1050 :
1051 : /* Set of vector conditions that have loop mask applied. */
1052 : vec_cond_masked_set_type vec_cond_masked_set;
1053 :
1054 : /* If we are using a loop mask to align memory addresses, this variable
1055 : contains the number of vector elements that we should skip in the
1056 : first iteration of the vector loop (i.e. the number of leading
1057 : elements that should be false in the first mask). */
1058 : tree mask_skip_niters;
1059 :
1060 : /* If we are using a loop mask to align memory addresses and we're in an
1061 : early break loop then this variable contains the number of elements that
1062 : were skipped during the initial iteration of the loop. */
1063 : tree mask_skip_niters_pfa_offset;
1064 :
1065 : /* The type that the loop control IV should be converted to before
1066 : testing which of the VF scalars are active and inactive.
1067 : Only meaningful if LOOP_VINFO_USING_PARTIAL_VECTORS_P. */
1068 : tree rgroup_compare_type;
1069 :
1070 : /* For #pragma omp simd if (x) loops the x expression. If constant 0,
1071 : the loop should not be vectorized, if constant non-zero, simd_if_cond
1072 : shouldn't be set and loop vectorized normally, if SSA_NAME, the loop
1073 : should be versioned on that condition, using scalar loop if the condition
1074 : is false and vectorized loop otherwise. */
1075 : tree simd_if_cond;
1076 :
1077 : /* The type that the vector loop control IV should have when
1078 : LOOP_VINFO_USING_PARTIAL_VECTORS_P is true. */
1079 : tree rgroup_iv_type;
1080 :
1081 : /* The style used for implementing partial vectors when
1082 : LOOP_VINFO_USING_PARTIAL_VECTORS_P is true. */
1083 : vect_partial_vector_style partial_vector_style;
1084 :
1085 : /* Unknown DRs according to which loop was peeled. */
1086 : class dr_vec_info *unaligned_dr;
1087 :
1088 : /* peeling_for_alignment indicates whether peeling for alignment will take
1089 : place, and what the peeling factor should be:
1090 : peeling_for_alignment = X means:
1091 : If X=0: Peeling for alignment will not be applied.
1092 : If X>0: Peel first X iterations.
1093 : If X=-1: Generate a runtime test to calculate the number of iterations
1094 : to be peeled, using the dataref recorded in the field
1095 : unaligned_dr. */
1096 : int peeling_for_alignment;
1097 :
1098 : /* The mask used to check the alignment of pointers or arrays. */
1099 : poly_uint64 ptr_mask;
1100 :
1101 : /* The maximum speculative read amount in VLA modes for runtime check. */
1102 : poly_uint64 max_spec_read_amount;
1103 :
1104 : /* Indicates whether the loop has any non-linear IV. */
1105 : bool nonlinear_iv;
1106 :
1107 : /* Data Dependence Relations defining address ranges that are candidates
1108 : for a run-time aliasing check. */
1109 : auto_vec<ddr_p> may_alias_ddrs;
1110 :
1111 : /* Data Dependence Relations defining address ranges together with segment
1112 : lengths from which the run-time aliasing check is built. */
1113 : auto_vec<dr_with_seg_len_pair_t> comp_alias_ddrs;
1114 :
1115 : /* Check that the addresses of each pair of objects is unequal. */
1116 : auto_vec<vec_object_pair> check_unequal_addrs;
1117 :
1118 : /* List of values that are required to be nonzero. This is used to check
1119 : whether things like "x[i * n] += 1;" are safe and eventually gets added
1120 : to the checks for lower bounds below. */
1121 : auto_vec<tree> check_nonzero;
1122 :
1123 : /* List of values that need to be checked for a minimum value. */
1124 : auto_vec<vec_lower_bound> lower_bounds;
1125 :
1126 : /* Statements in the loop that have data references that are candidates for a
1127 : runtime (loop versioning) misalignment check. */
1128 : auto_vec<stmt_vec_info> may_misalign_stmts;
1129 :
1130 : /* Reduction cycles detected in the loop. Used in loop-aware SLP. */
1131 : auto_vec<stmt_vec_info> reductions;
1132 :
1133 : /* Defs that could not be analyzed such as OMP SIMD calls without
1134 : a LHS. */
1135 : auto_vec<stmt_vec_info> alternate_defs;
1136 :
1137 : /* Cost vector for a single scalar iteration. */
1138 : auto_vec<stmt_info_for_cost> scalar_cost_vec;
1139 :
1140 : /* Map of IV base/step expressions to inserted name in the preheader. */
1141 : hash_map<tree_operand_hash, tree> *ivexpr_map;
1142 :
1143 : /* Map of OpenMP "omp simd array" scan variables to corresponding
1144 : rhs of the store of the initializer. */
1145 : hash_map<tree, tree> *scan_map;
1146 :
1147 : /* The factor used to over weight those statements in an inner loop
1148 : relative to the loop being vectorized. */
1149 : unsigned int inner_loop_cost_factor;
1150 :
1151 : /* Is the loop vectorizable? */
1152 : bool vectorizable;
1153 :
1154 : /* Records whether we still have the option of vectorizing this loop
1155 : using partially-populated vectors; in other words, whether it is
1156 : still possible for one iteration of the vector loop to handle
1157 : fewer than VF scalars. */
1158 : bool can_use_partial_vectors_p;
1159 :
1160 : /* Records whether we must use niter masking for correctness reasons. */
1161 : bool must_use_partial_vectors_p;
1162 :
1163 : /* True if we've decided to use partially-populated vectors, so that
1164 : the vector loop can handle fewer than VF scalars. */
1165 : bool using_partial_vectors_p;
1166 :
1167 : /* True if we've decided to use a decrementing loop control IV that counts
1168 : scalars. This can be done for any loop that:
1169 :
1170 : (a) uses length "controls"; and
1171 : (b) can iterate more than once. */
1172 : bool using_decrementing_iv_p;
1173 :
1174 : /* True if we've decided to use output of select_vl to adjust IV of
1175 : both loop control and data reference pointer. This is only true
1176 : for single-rgroup control. */
1177 : bool using_select_vl_p;
1178 :
1179 : /* True if we've decided to use peeling with versioning together, which allows
1180 : unaligned unsupported data refs to be uniformly aligned after a certain
1181 : amount of peeling (mutual alignment). Otherwise, we use versioning alone
1182 : so these data refs must be already aligned to a power-of-two boundary
1183 : without peeling. */
1184 : bool allow_mutual_alignment;
1185 :
1186 : /* The bias for len_load and len_store. For now, only 0 and -1 are
1187 : supported. -1 must be used when a backend does not support
1188 : len_load/len_store with a length of zero. */
1189 : signed char partial_load_store_bias;
1190 :
1191 : /* When we have grouped data accesses with gaps, we may introduce invalid
1192 : memory accesses. We peel the last iteration of the loop to prevent
1193 : this. */
1194 : bool peeling_for_gaps;
1195 :
1196 : /* When the number of iterations is not a multiple of the vector size
1197 : we need to peel off iterations at the end to form an epilogue loop. */
1198 : bool peeling_for_niter;
1199 :
1200 : /* When the loop has early breaks that we can vectorize we need to peel
1201 : the loop for the break finding loop. */
1202 : bool early_breaks;
1203 :
1204 : /* List of loop additional IV conditionals found in the loop. */
1205 : auto_vec<gcond *> conds;
1206 :
1207 : /* Main loop IV cond. */
1208 : gcond* loop_iv_cond;
1209 :
1210 : /* True if we have an unroll factor requested by the user through pragma GCC
1211 : unroll. */
1212 : bool user_unroll;
1213 :
1214 : /* True if there are no loop carried data dependencies in the loop.
1215 : If loop->safelen <= 1, then this is always true, either the loop
1216 : didn't have any loop carried data dependencies, or the loop is being
1217 : vectorized guarded with some runtime alias checks, or couldn't
1218 : be vectorized at all, but then this field shouldn't be used.
1219 : For loop->safelen >= 2, the user has asserted that there are no
1220 : backward dependencies, but there still could be loop carried forward
1221 : dependencies in such loops. This flag will be false if normal
1222 : vectorizer data dependency analysis would fail or require versioning
1223 : for alias, but because of loop->safelen >= 2 it has been vectorized
1224 : even without versioning for alias. E.g. in:
1225 : #pragma omp simd
1226 : for (int i = 0; i < m; i++)
1227 : a[i] = a[i + k] * c;
1228 : (or #pragma simd or #pragma ivdep) we can vectorize this and it will
1229 : DTRT even for k > 0 && k < m, but without safelen we would not
1230 : vectorize this, so this field would be false. */
1231 : bool no_data_dependencies;
1232 :
1233 : /* Mark loops having masked stores. */
1234 : bool has_mask_store;
1235 :
1236 : /* Queued scaling factor for the scalar loop. */
1237 : profile_probability scalar_loop_scaling;
1238 :
1239 : /* If if-conversion versioned this loop before conversion, this is the
1240 : loop version without if-conversion. */
1241 : class loop *scalar_loop;
1242 :
1243 : /* For loops being epilogues of already vectorized loops
1244 : this points to the main vectorized loop. Otherwise NULL. */
1245 : _loop_vec_info *main_loop_info;
1246 :
1247 : /* For loops being epilogues of already vectorized loops
1248 : this points to the preceding vectorized (possibly epilogue) loop.
1249 : Otherwise NULL. */
1250 : _loop_vec_info *orig_loop_info;
1251 :
1252 : /* Used to store loop_vec_infos of the epilogue of this loop during
1253 : analysis. */
1254 : _loop_vec_info *epilogue_vinfo;
1255 :
1256 : /* If this is an epilogue loop the DR advancement applied. */
1257 : tree drs_advanced_by;
1258 :
1259 : /* The controlling loop exit for the current loop when vectorizing.
1260 : For counted loops, this IV controls the natural exits of the loop. */
1261 : edge vec_loop_main_exit;
1262 :
1263 : /* The controlling loop exit for the epilogue loop when vectorizing.
1264 : For counted loops, this IV controls the natural exits of the loop. */
1265 : edge vec_epilogue_loop_main_exit;
1266 :
1267 : /* The controlling loop exit for the scalar loop being vectorized.
1268 : For counted loops, this IV controls the natural exits of the loop. */
1269 : edge scalar_loop_main_exit;
1270 :
1271 : /* Indicate if the multiple exit loop has any side-effects that require it to
1272 : have a scalar epilogue. */
1273 : bool early_break_needs_epilogue;
1274 :
1275 : /* Used to store the list of stores needing to be moved if doing early
1276 : break vectorization as they would violate the scalar loop semantics if
1277 : vectorized in their current location. These are stored in order that they
1278 : need to be moved. */
1279 : auto_vec<gimple *> early_break_stores;
1280 :
1281 : /* The final basic block where to move statements to. In the case of
1282 : multiple exits this could be pretty far away. */
1283 : basic_block early_break_dest_bb;
1284 :
1285 : /* Statements whose VUSES need updating if early break vectorization is to
1286 : happen. */
1287 : auto_vec<gimple*> early_break_vuses;
1288 :
1289 : /* The IV adjustment value for inductions that needs to be materialized
1290 : inside the relevant exit blocks in order to adjust for early break. */
1291 : tree early_break_niters_var;
1292 :
1293 : /* The type of the variable to be used to create the scalar IV for early break
1294 : loops. */
1295 : tree early_break_iv_type;
1296 :
1297 : /* Record statements that are needed to be live for early break vectorization
1298 : but may not have an LC PHI node materialized yet in the exits. */
1299 : auto_vec<stmt_vec_info> early_break_live_ivs;
1300 : } *loop_vec_info;
1301 :
1302 : /* Access Functions. */
1303 : #define LOOP_VINFO_LOOP(L) (L)->loop
1304 : #define LOOP_VINFO_MAIN_EXIT(L) (L)->vec_loop_main_exit
1305 : #define LOOP_VINFO_EPILOGUE_MAIN_EXIT(L) (L)->vec_epilogue_loop_main_exit
1306 : #define LOOP_VINFO_SCALAR_MAIN_EXIT(L) (L)->scalar_loop_main_exit
1307 : #define LOOP_VINFO_BBS(L) (L)->bbs
1308 : #define LOOP_VINFO_NBBS(L) (L)->nbbs
1309 : #define LOOP_VINFO_NITERSM1(L) (L)->num_itersm1
1310 : #define LOOP_VINFO_NITERS(L) (L)->num_iters
1311 : #define LOOP_VINFO_NITERS_UNCOUNTED_P(L) (LOOP_VINFO_NITERS (L) \
1312 : == chrec_dont_know)
1313 : /* Since LOOP_VINFO_NITERS and LOOP_VINFO_NITERSM1 can change after
1314 : prologue peeling retain total unchanged scalar loop iterations for
1315 : cost model. */
1316 : #define LOOP_VINFO_NITERS_UNCHANGED(L) (L)->num_iters_unchanged
1317 : #define LOOP_VINFO_NITERS_ASSUMPTIONS(L) (L)->num_iters_assumptions
1318 : #define LOOP_VINFO_COST_MODEL_THRESHOLD(L) (L)->th
1319 : #define LOOP_VINFO_VERSIONING_THRESHOLD(L) (L)->versioning_threshold
1320 : #define LOOP_VINFO_VECTORIZABLE_P(L) (L)->vectorizable
1321 : #define LOOP_VINFO_CAN_USE_PARTIAL_VECTORS_P(L) (L)->can_use_partial_vectors_p
1322 : #define LOOP_VINFO_MUST_USE_PARTIAL_VECTORS_P(L) (L)->must_use_partial_vectors_p
1323 : #define LOOP_VINFO_USING_PARTIAL_VECTORS_P(L) (L)->using_partial_vectors_p
1324 : #define LOOP_VINFO_USING_DECREMENTING_IV_P(L) (L)->using_decrementing_iv_p
1325 : #define LOOP_VINFO_USING_SELECT_VL_P(L) (L)->using_select_vl_p
1326 : #define LOOP_VINFO_ALLOW_MUTUAL_ALIGNMENT(L) (L)->allow_mutual_alignment
1327 : #define LOOP_VINFO_PARTIAL_LOAD_STORE_BIAS(L) (L)->partial_load_store_bias
1328 : #define LOOP_VINFO_VECT_FACTOR(L) (L)->vectorization_factor
1329 : #define LOOP_VINFO_IV_INCREMENT(L) (L)->iv_increment
1330 : #define LOOP_VINFO_IV_INCREMENT_INVARIANT_P(L) \
1331 : (!LOOP_VINFO_USING_SELECT_VL_P (L))
1332 : #define LOOP_VINFO_MAX_VECT_FACTOR(L) (L)->max_vectorization_factor
1333 : #define LOOP_VINFO_MASKS(L) (L)->masks
1334 : #define LOOP_VINFO_LENS(L) (L)->lens
1335 : #define LOOP_VINFO_MASK_SKIP_NITERS(L) (L)->mask_skip_niters
1336 : #define LOOP_VINFO_MASK_NITERS_PFA_OFFSET(L) (L)->mask_skip_niters_pfa_offset
1337 : #define LOOP_VINFO_RGROUP_COMPARE_TYPE(L) (L)->rgroup_compare_type
1338 : #define LOOP_VINFO_RGROUP_IV_TYPE(L) (L)->rgroup_iv_type
1339 : #define LOOP_VINFO_PARTIAL_VECTORS_STYLE(L) (L)->partial_vector_style
1340 : #define LOOP_VINFO_PTR_MASK(L) (L)->ptr_mask
1341 : #define LOOP_VINFO_MAX_SPEC_READ_AMOUNT(L) (L)->max_spec_read_amount
1342 : #define LOOP_VINFO_LOOP_NEST(L) (L)->shared->loop_nest
1343 : #define LOOP_VINFO_DATAREFS(L) (L)->shared->datarefs
1344 : #define LOOP_VINFO_DDRS(L) (L)->shared->ddrs
1345 : #define LOOP_VINFO_INT_NITERS(L) (TREE_INT_CST_LOW ((L)->num_iters))
1346 : #define LOOP_VINFO_PEELING_FOR_ALIGNMENT(L) (L)->peeling_for_alignment
1347 : #define LOOP_VINFO_NON_LINEAR_IV(L) (L)->nonlinear_iv
1348 : #define LOOP_VINFO_UNALIGNED_DR(L) (L)->unaligned_dr
1349 : #define LOOP_VINFO_MAY_MISALIGN_STMTS(L) (L)->may_misalign_stmts
1350 : #define LOOP_VINFO_MAY_ALIAS_DDRS(L) (L)->may_alias_ddrs
1351 : #define LOOP_VINFO_COMP_ALIAS_DDRS(L) (L)->comp_alias_ddrs
1352 : #define LOOP_VINFO_CHECK_UNEQUAL_ADDRS(L) (L)->check_unequal_addrs
1353 : #define LOOP_VINFO_CHECK_NONZERO(L) (L)->check_nonzero
1354 : #define LOOP_VINFO_LOWER_BOUNDS(L) (L)->lower_bounds
1355 : #define LOOP_VINFO_USER_UNROLL(L) (L)->user_unroll
1356 : #define LOOP_VINFO_GROUPED_STORES(L) (L)->grouped_stores
1357 : #define LOOP_VINFO_SLP_INSTANCES(L) (L)->slp_instances
1358 : #define LOOP_VINFO_REDUCTIONS(L) (L)->reductions
1359 : #define LOOP_VINFO_PEELING_FOR_GAPS(L) (L)->peeling_for_gaps
1360 : #define LOOP_VINFO_PEELING_FOR_NITER(L) (L)->peeling_for_niter
1361 : #define LOOP_VINFO_EARLY_BREAKS(L) (L)->early_breaks
1362 : #define LOOP_VINFO_EARLY_BRK_NEEDS_EPILOG(L) (L)->early_break_needs_epilogue
1363 : #define LOOP_VINFO_EARLY_BRK_STORES(L) (L)->early_break_stores
1364 : #define LOOP_VINFO_EARLY_BREAKS_VECT_PEELED(L) \
1365 : ((single_pred ((L)->loop->latch) != (L)->vec_loop_main_exit->src) \
1366 : || LOOP_VINFO_NITERS_UNCOUNTED_P (L))
1367 : #define LOOP_VINFO_EARLY_BREAKS_LIVE_IVS(L) \
1368 : (L)->early_break_live_ivs
1369 : #define LOOP_VINFO_EARLY_BRK_DEST_BB(L) (L)->early_break_dest_bb
1370 : #define LOOP_VINFO_EARLY_BRK_VUSES(L) (L)->early_break_vuses
1371 : #define LOOP_VINFO_EARLY_BRK_NITERS_VAR(L) (L)->early_break_niters_var
1372 : #define LOOP_VINFO_EARLY_BRK_IV_TYPE(L) (L)->early_break_iv_type
1373 : #define LOOP_VINFO_LOOP_CONDS(L) (L)->conds
1374 : #define LOOP_VINFO_LOOP_IV_COND(L) (L)->loop_iv_cond
1375 : #define LOOP_VINFO_NO_DATA_DEPENDENCIES(L) (L)->no_data_dependencies
1376 : #define LOOP_VINFO_SCALAR_LOOP(L) (L)->scalar_loop
1377 : #define LOOP_VINFO_SCALAR_LOOP_SCALING(L) (L)->scalar_loop_scaling
1378 : #define LOOP_VINFO_HAS_MASK_STORE(L) (L)->has_mask_store
1379 : #define LOOP_VINFO_SCALAR_ITERATION_COST(L) (L)->scalar_cost_vec
1380 : #define LOOP_VINFO_MAIN_LOOP_INFO(L) (L)->main_loop_info
1381 : #define LOOP_VINFO_ORIG_LOOP_INFO(L) (L)->orig_loop_info
1382 : #define LOOP_VINFO_SIMD_IF_COND(L) (L)->simd_if_cond
1383 : #define LOOP_VINFO_INNER_LOOP_COST_FACTOR(L) (L)->inner_loop_cost_factor
1384 : #define LOOP_VINFO_INV_PATTERN_DEF_SEQ(L) (L)->inv_pattern_def_seq
1385 : #define LOOP_VINFO_DRS_ADVANCED_BY(L) (L)->drs_advanced_by
1386 : #define LOOP_VINFO_ALTERNATE_DEFS(L) (L)->alternate_defs
1387 :
1388 : #define LOOP_VINFO_FULLY_MASKED_P(L) \
1389 : (LOOP_VINFO_USING_PARTIAL_VECTORS_P (L) \
1390 : && !LOOP_VINFO_MASKS (L).is_empty ())
1391 :
1392 : #define LOOP_VINFO_FULLY_WITH_LENGTH_P(L) \
1393 : (LOOP_VINFO_USING_PARTIAL_VECTORS_P (L) \
1394 : && !LOOP_VINFO_LENS (L).is_empty ())
1395 :
1396 : #define LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT(L) \
1397 : ((L)->may_misalign_stmts.length () > 0)
1398 : #define LOOP_REQUIRES_VERSIONING_FOR_SPEC_READ(L) \
1399 : (maybe_gt ((L)->max_spec_read_amount, 0U))
1400 : #define LOOP_REQUIRES_VERSIONING_FOR_ALIAS(L) \
1401 : ((L)->comp_alias_ddrs.length () > 0 \
1402 : || (L)->check_unequal_addrs.length () > 0 \
1403 : || (L)->lower_bounds.length () > 0)
1404 : #define LOOP_REQUIRES_VERSIONING_FOR_NITERS(L) \
1405 : (LOOP_VINFO_NITERS_ASSUMPTIONS (L))
1406 : #define LOOP_REQUIRES_VERSIONING_FOR_SIMD_IF_COND(L) \
1407 : (LOOP_VINFO_SIMD_IF_COND (L))
1408 : #define LOOP_REQUIRES_VERSIONING(L) \
1409 : (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (L) \
1410 : || LOOP_REQUIRES_VERSIONING_FOR_SPEC_READ (L) \
1411 : || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (L) \
1412 : || LOOP_REQUIRES_VERSIONING_FOR_NITERS (L) \
1413 : || LOOP_REQUIRES_VERSIONING_FOR_SIMD_IF_COND (L))
1414 :
1415 : #define LOOP_VINFO_USE_VERSIONING_WITHOUT_PEELING(L) \
1416 : ((L)->may_misalign_stmts.length () > 0 \
1417 : && !LOOP_VINFO_ALLOW_MUTUAL_ALIGNMENT (L))
1418 :
1419 : #define LOOP_VINFO_NITERS_KNOWN_P(L) \
1420 : (tree_fits_shwi_p ((L)->num_iters) && tree_to_shwi ((L)->num_iters) > 0)
1421 :
1422 : #define LOOP_VINFO_EPILOGUE_P(L) \
1423 : (LOOP_VINFO_ORIG_LOOP_INFO (L) != NULL)
1424 :
1425 : #define LOOP_VINFO_ORIG_MAX_VECT_FACTOR(L) \
1426 : (LOOP_VINFO_MAX_VECT_FACTOR (LOOP_VINFO_ORIG_LOOP_INFO (L)))
1427 :
1428 : /* Wrapper for loop_vec_info, for tracking success/failure, where a non-NULL
1429 : value signifies success, and a NULL value signifies failure, supporting
1430 : propagating an opt_problem * describing the failure back up the call
1431 : stack. */
1432 : typedef opt_pointer_wrapper <loop_vec_info> opt_loop_vec_info;
1433 :
1434 : inline loop_vec_info
1435 553257 : loop_vec_info_for_loop (class loop *loop)
1436 : {
1437 553257 : return (loop_vec_info) loop->aux;
1438 : }
1439 :
1440 : struct slp_root
1441 : {
1442 1381583 : slp_root (slp_instance_kind kind_, vec<stmt_vec_info> stmts_,
1443 15570 : vec<stmt_vec_info> roots_, vec<tree> remain_ = vNULL)
1444 1381583 : : kind(kind_), stmts(stmts_), roots(roots_), remain(remain_) {}
1445 : slp_instance_kind kind;
1446 : vec<stmt_vec_info> stmts;
1447 : vec<stmt_vec_info> roots;
1448 : vec<tree> remain;
1449 : };
1450 :
1451 : typedef class _bb_vec_info : public vec_info
1452 : {
1453 : public:
1454 : _bb_vec_info (vec<basic_block> bbs, vec_info_shared *);
1455 : ~_bb_vec_info ();
1456 :
1457 : vec<slp_root> roots;
1458 : } *bb_vec_info;
1459 :
1460 : #define BB_VINFO_BBS(B) (B)->bbs
1461 : #define BB_VINFO_NBBS(B) (B)->nbbs
1462 : #define BB_VINFO_GROUPED_STORES(B) (B)->grouped_stores
1463 : #define BB_VINFO_SLP_INSTANCES(B) (B)->slp_instances
1464 : #define BB_VINFO_DATAREFS(B) (B)->shared->datarefs
1465 : #define BB_VINFO_DDRS(B) (B)->shared->ddrs
1466 :
1467 : /* Indicates whether/how a variable is used in the scope of loop/basic
1468 : block. */
1469 : enum vect_relevant {
1470 : vect_unused_in_scope = 0,
1471 :
1472 : /* The def is only used outside the loop. */
1473 : vect_used_only_live,
1474 : /* The def is in the inner loop, and the use is in the outer loop, and the
1475 : use is a reduction stmt. */
1476 : vect_used_in_outer_by_reduction,
1477 : /* The def is in the inner loop, and the use is in the outer loop (and is
1478 : not part of reduction). */
1479 : vect_used_in_outer,
1480 :
1481 : /* defs that feed computations that end up (only) in a reduction. These
1482 : defs may be used by non-reduction stmts, but eventually, any
1483 : computations/values that are affected by these defs are used to compute
1484 : a reduction (i.e. don't get stored to memory, for example). We use this
1485 : to identify computations that we can change the order in which they are
1486 : computed. */
1487 : vect_used_by_reduction,
1488 :
1489 : vect_used_in_scope
1490 : };
1491 :
1492 : /* The type of vectorization. pure_slp means the stmt is covered by the
1493 : SLP graph, not_vect means it is not. This is mostly used by BB
1494 : vectorization. */
1495 : enum slp_vect_type {
1496 : not_vect = 0,
1497 : pure_slp,
1498 : };
1499 :
1500 : /* Says whether a statement is a load, a store of a vectorized statement
1501 : result, or a store of an invariant value. */
1502 : enum vec_load_store_type {
1503 : VLS_LOAD,
1504 : VLS_STORE,
1505 : VLS_STORE_INVARIANT
1506 : };
1507 :
1508 : class dr_vec_info {
1509 : public:
1510 : /* The data reference itself. */
1511 : data_reference *dr;
1512 : /* The statement that contains the data reference. */
1513 : stmt_vec_info stmt;
1514 : /* The analysis group this DR belongs to when doing BB vectorization.
1515 : DRs of the same group belong to the same conditional execution context. */
1516 : unsigned group;
1517 : /* The misalignment in bytes of the reference, or -1 if not known. */
1518 : int misalignment;
1519 : /* The byte alignment that we'd ideally like the reference to have,
1520 : and the value that misalignment is measured against. */
1521 : poly_uint64 target_alignment;
1522 : /* If true the alignment of base_decl needs to be increased. */
1523 : bool base_misaligned;
1524 :
1525 : /* Set by early break vectorization when this DR needs peeling for alignment
1526 : for correctness. */
1527 : bool safe_speculative_read_required;
1528 :
1529 : /* Set by early break vectorization when this DR's scalar accesses are known
1530 : to be inbounds of a known bounds loop. */
1531 : bool scalar_access_known_in_bounds;
1532 :
1533 : tree base_decl;
1534 :
1535 : /* Stores current vectorized loop's offset. To be added to the DR's
1536 : offset to calculate current offset of data reference. */
1537 : tree offset;
1538 : };
1539 :
1540 : typedef struct data_reference *dr_p;
1541 :
1542 : class _stmt_vec_info {
1543 : public:
1544 :
1545 : /* Indicates whether this stmts is part of a computation whose result is
1546 : used outside the loop. */
1547 : bool live;
1548 :
1549 : /* Stmt is part of some pattern (computation idiom) */
1550 : bool in_pattern_p;
1551 :
1552 : /* True if the statement was created during pattern recognition as
1553 : part of the replacement for RELATED_STMT. This implies that the
1554 : statement isn't part of any basic block, although for convenience
1555 : its gimple_bb is the same as for RELATED_STMT. */
1556 : bool pattern_stmt_p;
1557 :
1558 : /* Is this statement vectorizable or should it be skipped in (partial)
1559 : vectorization. */
1560 : bool vectorizable;
1561 :
1562 : /* The stmt to which this info struct refers to. */
1563 : gimple *stmt;
1564 :
1565 : /* The vector type to be used for the LHS of this statement. */
1566 : tree vectype;
1567 :
1568 : /* The following is relevant only for stmts that contain a non-scalar
1569 : data-ref (array/pointer/struct access). A GIMPLE stmt is expected to have
1570 : at most one such data-ref. */
1571 :
1572 : dr_vec_info dr_aux;
1573 :
1574 : /* Information about the data-ref relative to this loop
1575 : nest (the loop that is being considered for vectorization). */
1576 : innermost_loop_behavior dr_wrt_vec_loop;
1577 :
1578 : /* For loop PHI nodes, the base and evolution part of it. This makes sure
1579 : this information is still available in vect_update_ivs_after_vectorizer
1580 : where we may not be able to re-analyze the PHI nodes evolution as
1581 : peeling for the prologue loop can make it unanalyzable. The evolution
1582 : part is still correct after peeling, but the base may have changed from
1583 : the version here. */
1584 : tree loop_phi_evolution_base_unchanged;
1585 : tree loop_phi_evolution_part;
1586 : enum vect_induction_op_type loop_phi_evolution_type;
1587 :
1588 : /* Used for various bookkeeping purposes, generally holding a pointer to
1589 : some other stmt S that is in some way "related" to this stmt.
1590 : Current use of this field is:
1591 : If this stmt is part of a pattern (i.e. the field 'in_pattern_p' is
1592 : true): S is the "pattern stmt" that represents (and replaces) the
1593 : sequence of stmts that constitutes the pattern. Similarly, the
1594 : related_stmt of the "pattern stmt" points back to this stmt (which is
1595 : the last stmt in the original sequence of stmts that constitutes the
1596 : pattern). */
1597 : stmt_vec_info related_stmt;
1598 :
1599 : /* Used to keep a sequence of def stmts of a pattern stmt if such exists.
1600 : The sequence is attached to the original statement rather than the
1601 : pattern statement. */
1602 : gimple_seq pattern_def_seq;
1603 :
1604 : /* Classify the def of this stmt. */
1605 : enum vect_def_type def_type;
1606 :
1607 : /* Whether the stmt is SLPed, loop-based vectorized, or both. */
1608 : enum slp_vect_type slp_type;
1609 :
1610 : /* Interleaving chains info. */
1611 : /* First element in the group. */
1612 : stmt_vec_info first_element;
1613 : /* Pointer to the next element in the group. */
1614 : stmt_vec_info next_element;
1615 : /* The size of the group. */
1616 : unsigned int size;
1617 : /* For loads only, the gap from the previous load. For consecutive loads, GAP
1618 : is 1. */
1619 : unsigned int gap;
1620 :
1621 : /* The minimum negative dependence distance this stmt participates in
1622 : or zero if none. */
1623 : unsigned int min_neg_dist;
1624 :
1625 : /* Not all stmts in the loop need to be vectorized. e.g, the increment
1626 : of the loop induction variable and computation of array indexes. relevant
1627 : indicates whether the stmt needs to be vectorized. */
1628 : enum vect_relevant relevant;
1629 :
1630 : /* For loads if this is a gather, for stores if this is a scatter. */
1631 : bool gather_scatter_p;
1632 :
1633 : /* True if this is an access with loop-invariant stride. */
1634 : bool strided_p;
1635 :
1636 : /* For both loads and stores. */
1637 : unsigned simd_lane_access_p : 3;
1638 :
1639 : /* On a reduction PHI the reduction type as detected by
1640 : vect_is_simple_reduction. */
1641 : enum vect_reduction_type reduc_type;
1642 :
1643 : /* On a reduction PHI, the original reduction code as detected by
1644 : vect_is_simple_reduction. */
1645 : code_helper reduc_code;
1646 :
1647 : /* On a stmt participating in a reduction the index of the operand
1648 : on the reduction SSA cycle. */
1649 : int reduc_idx;
1650 :
1651 : /* On a reduction PHI the def returned by vect_is_simple_reduction.
1652 : On the def returned by vect_is_simple_reduction the corresponding PHI. */
1653 : stmt_vec_info reduc_def;
1654 :
1655 : /* If nonzero, the lhs of the statement could be truncated to this
1656 : many bits without affecting any users of the result. */
1657 : unsigned int min_output_precision;
1658 :
1659 : /* If nonzero, all non-boolean input operands have the same precision,
1660 : and they could each be truncated to this many bits without changing
1661 : the result. */
1662 : unsigned int min_input_precision;
1663 :
1664 : /* If OPERATION_BITS is nonzero, the statement could be performed on
1665 : an integer with the sign and number of bits given by OPERATION_SIGN
1666 : and OPERATION_BITS without changing the result. */
1667 : unsigned int operation_precision;
1668 : signop operation_sign;
1669 :
1670 : /* If the statement produces a boolean result, this value describes
1671 : how we should choose the associated vector type. The possible
1672 : values are:
1673 :
1674 : - an integer precision N if we should use the vector mask type
1675 : associated with N-bit integers. This is only used if all relevant
1676 : input booleans also want the vector mask type for N-bit integers,
1677 : or if we can convert them into that form by pattern-matching.
1678 :
1679 : - ~0U if we considered choosing a vector mask type but decided
1680 : to treat the boolean as a normal integer type instead.
1681 :
1682 : - 0 otherwise. This means either that the operation isn't one that
1683 : could have a vector mask type (and so should have a normal vector
1684 : type instead) or that we simply haven't made a choice either way. */
1685 : unsigned int mask_precision;
1686 :
1687 : /* True if this is only suitable for SLP vectorization. */
1688 : bool slp_vect_only_p;
1689 : };
1690 :
1691 : /* Information about a gather/scatter call. */
1692 : struct gather_scatter_info {
1693 : /* The internal function to use for the gather/scatter operation,
1694 : or IFN_LAST if a built-in function should be used instead. */
1695 : internal_fn ifn;
1696 :
1697 : /* The FUNCTION_DECL for the built-in gather/scatter function,
1698 : or null if an internal function should be used instead. */
1699 : tree decl;
1700 :
1701 : /* The loop-invariant base value. */
1702 : tree base;
1703 :
1704 : /* The TBBA alias pointer the value of which determines the alignment
1705 : of the scalar accesses. */
1706 : tree alias_ptr;
1707 :
1708 : /* The original scalar offset, which is a non-loop-invariant SSA_NAME. */
1709 : tree offset;
1710 :
1711 : /* Each offset element should be multiplied by this amount before
1712 : being added to the base. */
1713 : int scale;
1714 :
1715 : /* The type of the vectorized offset. */
1716 : tree offset_vectype;
1717 :
1718 : /* The type of the scalar elements after loading or before storing. */
1719 : tree element_type;
1720 :
1721 : /* The type of the scalar elements being loaded or stored. */
1722 : tree memory_type;
1723 : };
1724 :
1725 : /* Access Functions. */
1726 : #define STMT_VINFO_STMT(S) (S)->stmt
1727 : #define STMT_VINFO_RELEVANT(S) (S)->relevant
1728 : #define STMT_VINFO_LIVE_P(S) (S)->live
1729 : #define STMT_VINFO_VECTYPE(S) (S)->vectype
1730 : #define STMT_VINFO_VECTORIZABLE(S) (S)->vectorizable
1731 : #define STMT_VINFO_DATA_REF(S) ((S)->dr_aux.dr + 0)
1732 : #define STMT_VINFO_GATHER_SCATTER_P(S) (S)->gather_scatter_p
1733 : #define STMT_VINFO_STRIDED_P(S) (S)->strided_p
1734 : #define STMT_VINFO_SIMD_LANE_ACCESS_P(S) (S)->simd_lane_access_p
1735 : #define STMT_VINFO_REDUC_IDX(S) (S)->reduc_idx
1736 :
1737 : #define STMT_VINFO_DR_WRT_VEC_LOOP(S) (S)->dr_wrt_vec_loop
1738 : #define STMT_VINFO_DR_BASE_ADDRESS(S) (S)->dr_wrt_vec_loop.base_address
1739 : #define STMT_VINFO_DR_INIT(S) (S)->dr_wrt_vec_loop.init
1740 : #define STMT_VINFO_DR_OFFSET(S) (S)->dr_wrt_vec_loop.offset
1741 : #define STMT_VINFO_DR_STEP(S) (S)->dr_wrt_vec_loop.step
1742 : #define STMT_VINFO_DR_BASE_ALIGNMENT(S) (S)->dr_wrt_vec_loop.base_alignment
1743 : #define STMT_VINFO_DR_BASE_MISALIGNMENT(S) \
1744 : (S)->dr_wrt_vec_loop.base_misalignment
1745 : #define STMT_VINFO_DR_OFFSET_ALIGNMENT(S) \
1746 : (S)->dr_wrt_vec_loop.offset_alignment
1747 : #define STMT_VINFO_DR_STEP_ALIGNMENT(S) \
1748 : (S)->dr_wrt_vec_loop.step_alignment
1749 :
1750 : #define STMT_VINFO_DR_INFO(S) \
1751 : (gcc_checking_assert ((S)->dr_aux.stmt == (S)), &(S)->dr_aux)
1752 :
1753 : #define STMT_VINFO_IN_PATTERN_P(S) (S)->in_pattern_p
1754 : #define STMT_VINFO_RELATED_STMT(S) (S)->related_stmt
1755 : #define STMT_VINFO_PATTERN_DEF_SEQ(S) (S)->pattern_def_seq
1756 : #define STMT_VINFO_DEF_TYPE(S) (S)->def_type
1757 : #define STMT_VINFO_GROUPED_ACCESS(S) \
1758 : ((S)->dr_aux.dr && DR_GROUP_FIRST_ELEMENT(S))
1759 : #define STMT_VINFO_LOOP_PHI_EVOLUTION_BASE_UNCHANGED(S) (S)->loop_phi_evolution_base_unchanged
1760 : #define STMT_VINFO_LOOP_PHI_EVOLUTION_PART(S) (S)->loop_phi_evolution_part
1761 : #define STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE(S) (S)->loop_phi_evolution_type
1762 : #define STMT_VINFO_MIN_NEG_DIST(S) (S)->min_neg_dist
1763 : #define STMT_VINFO_REDUC_TYPE(S) (S)->reduc_type
1764 : #define STMT_VINFO_REDUC_CODE(S) (S)->reduc_code
1765 : #define STMT_VINFO_REDUC_DEF(S) (S)->reduc_def
1766 : #define STMT_VINFO_SLP_VECT_ONLY(S) (S)->slp_vect_only_p
1767 : #define STMT_VINFO_REDUC_VECTYPE_IN(S) (S)->reduc_vectype_in
1768 :
1769 : #define DR_GROUP_FIRST_ELEMENT(S) \
1770 : (gcc_checking_assert ((S)->dr_aux.dr), (S)->first_element)
1771 : #define DR_GROUP_NEXT_ELEMENT(S) \
1772 : (gcc_checking_assert ((S)->dr_aux.dr), (S)->next_element)
1773 : #define DR_GROUP_SIZE(S) \
1774 : (gcc_checking_assert ((S)->dr_aux.dr), (S)->size)
1775 : #define DR_GROUP_GAP(S) \
1776 : (gcc_checking_assert ((S)->dr_aux.dr), (S)->gap)
1777 :
1778 : #define STMT_VINFO_RELEVANT_P(S) ((S)->relevant != vect_unused_in_scope)
1779 :
1780 : #define PURE_SLP_STMT(S) ((S)->slp_type == pure_slp)
1781 : #define STMT_SLP_TYPE(S) (S)->slp_type
1782 :
1783 :
1784 : /* Contains the scalar or vector costs for a vec_info. */
1785 : class vector_costs
1786 : {
1787 : public:
1788 : vector_costs (vec_info *, bool);
1789 0 : virtual ~vector_costs () {}
1790 :
1791 : /* Update the costs in response to adding COUNT copies of a statement.
1792 :
1793 : - WHERE specifies whether the cost occurs in the loop prologue,
1794 : the loop body, or the loop epilogue.
1795 : - KIND is the kind of statement, which is always meaningful.
1796 : - STMT_INFO or NODE, if nonnull, describe the statement that will be
1797 : vectorized.
1798 : - VECTYPE, if nonnull, is the vector type that the vectorized
1799 : statement will operate on. Note that this should be used in
1800 : preference to STMT_VINFO_VECTYPE (STMT_INFO) since the latter
1801 : is not correct for SLP.
1802 : - for unaligned_load and unaligned_store statements, MISALIGN is
1803 : the byte misalignment of the load or store relative to the target's
1804 : preferred alignment for VECTYPE, or DR_MISALIGNMENT_UNKNOWN
1805 : if the misalignment is not known.
1806 :
1807 : Return the calculated cost as well as recording it. The return
1808 : value is used for dumping purposes. */
1809 : virtual unsigned int add_stmt_cost (int count, vect_cost_for_stmt kind,
1810 : stmt_vec_info stmt_info,
1811 : slp_tree node,
1812 : tree vectype, int misalign,
1813 : vect_cost_model_location where);
1814 :
1815 : /* Update the costs in response to adding costs in V which are all from
1816 : vectorizing NODE to the respective part. */
1817 : virtual unsigned int add_slp_cost (slp_tree node,
1818 : const array_slice<stmt_info_for_cost> &v);
1819 :
1820 : /* Finish calculating the cost of the code. The results can be
1821 : read back using the functions below.
1822 :
1823 : If the costs describe vector code, SCALAR_COSTS gives the costs
1824 : of the corresponding scalar code, otherwise it is null. */
1825 : virtual void finish_cost (const vector_costs *scalar_costs);
1826 :
1827 : /* The costs in THIS and OTHER both describe ways of vectorizing
1828 : a main loop. Return true if the costs described by THIS are
1829 : cheaper than the costs described by OTHER. Return false if any
1830 : of the following are true:
1831 :
1832 : - THIS and OTHER are of equal cost
1833 : - OTHER is better than THIS
1834 : - we can't be sure about the relative costs of THIS and OTHER. */
1835 : virtual bool better_main_loop_than_p (const vector_costs *other) const;
1836 :
1837 : /* Likewise, but the costs in THIS and OTHER both describe ways of
1838 : vectorizing an epilogue loop of MAIN_LOOP. */
1839 : virtual bool better_epilogue_loop_than_p (const vector_costs *other,
1840 : loop_vec_info main_loop) const;
1841 :
1842 : unsigned int prologue_cost () const;
1843 : unsigned int body_cost () const;
1844 : unsigned int epilogue_cost () const;
1845 : unsigned int outside_cost () const;
1846 : unsigned int total_cost () const;
1847 :
1848 : unsigned int suggested_unroll_factor () const;
1849 : machine_mode suggested_epilogue_mode (int &masked) const;
1850 :
1851 36217 : vec_info *vinfo () const { return m_vinfo; }
1852 8120880 : bool costing_for_scalar () const { return m_costing_for_scalar; }
1853 :
1854 : protected:
1855 : unsigned int record_stmt_cost (stmt_vec_info, vect_cost_model_location,
1856 : unsigned int);
1857 : unsigned int adjust_cost_for_freq (stmt_vec_info, vect_cost_model_location,
1858 : unsigned int);
1859 : int compare_inside_loop_cost (const vector_costs *) const;
1860 : int compare_outside_loop_cost (const vector_costs *) const;
1861 :
1862 : /* The region of code that we're considering vectorizing. */
1863 : vec_info *m_vinfo;
1864 :
1865 : /* True if we're costing the scalar code, false if we're costing
1866 : the vector code. */
1867 : bool m_costing_for_scalar;
1868 :
1869 : /* The costs of the three regions, indexed by vect_cost_model_location. */
1870 : unsigned int m_costs[3];
1871 :
1872 : /* The suggested unrolling factor determined at finish_cost. */
1873 : unsigned int m_suggested_unroll_factor;
1874 :
1875 : /* The suggested mode to be used for a vectorized epilogue or VOIDmode,
1876 : determined at finish_cost. m_masked_epilogue specifies whether the
1877 : epilogue should use masked vectorization, regardless of the
1878 : --param vect-partial-vector-usage default. If -1 then the
1879 : --param setting takes precedence. If the user explicitly specified
1880 : --param vect-partial-vector-usage then that takes precedence. */
1881 : machine_mode m_suggested_epilogue_mode;
1882 : int m_masked_epilogue;
1883 :
1884 : /* True if finish_cost has been called. */
1885 : bool m_finished;
1886 : };
1887 :
1888 : /* Create costs for VINFO. COSTING_FOR_SCALAR is true if the costs
1889 : are for scalar code, false if they are for vector code. */
1890 :
1891 : inline
1892 2291866 : vector_costs::vector_costs (vec_info *vinfo, bool costing_for_scalar)
1893 2291866 : : m_vinfo (vinfo),
1894 2291866 : m_costing_for_scalar (costing_for_scalar),
1895 2291866 : m_costs (),
1896 2291866 : m_suggested_unroll_factor(1),
1897 2291866 : m_suggested_epilogue_mode(VOIDmode),
1898 2291866 : m_masked_epilogue (-1),
1899 2291866 : m_finished (false)
1900 : {
1901 : }
1902 :
1903 : /* Return the cost of the prologue code (in abstract units). */
1904 :
1905 : inline unsigned int
1906 1399474 : vector_costs::prologue_cost () const
1907 : {
1908 1399474 : gcc_checking_assert (m_finished);
1909 1399474 : return m_costs[vect_prologue];
1910 : }
1911 :
1912 : /* Return the cost of the body code (in abstract units). */
1913 :
1914 : inline unsigned int
1915 2174433 : vector_costs::body_cost () const
1916 : {
1917 2174433 : gcc_checking_assert (m_finished);
1918 2174433 : return m_costs[vect_body];
1919 : }
1920 :
1921 : /* Return the cost of the epilogue code (in abstract units). */
1922 :
1923 : inline unsigned int
1924 1399474 : vector_costs::epilogue_cost () const
1925 : {
1926 1399474 : gcc_checking_assert (m_finished);
1927 1399474 : return m_costs[vect_epilogue];
1928 : }
1929 :
1930 : /* Return the cost of the prologue and epilogue code (in abstract units). */
1931 :
1932 : inline unsigned int
1933 521009 : vector_costs::outside_cost () const
1934 : {
1935 521009 : return prologue_cost () + epilogue_cost ();
1936 : }
1937 :
1938 : /* Return the cost of the prologue, body and epilogue code
1939 : (in abstract units). */
1940 :
1941 : inline unsigned int
1942 129036 : vector_costs::total_cost () const
1943 : {
1944 129036 : return body_cost () + outside_cost ();
1945 : }
1946 :
1947 : /* Return the suggested unroll factor. */
1948 :
1949 : inline unsigned int
1950 128646 : vector_costs::suggested_unroll_factor () const
1951 : {
1952 128646 : gcc_checking_assert (m_finished);
1953 128646 : return m_suggested_unroll_factor;
1954 : }
1955 :
1956 : /* Return the suggested epilogue mode. */
1957 :
1958 : inline machine_mode
1959 14783 : vector_costs::suggested_epilogue_mode (int &masked_p) const
1960 : {
1961 14783 : gcc_checking_assert (m_finished);
1962 14783 : masked_p = m_masked_epilogue;
1963 14783 : return m_suggested_epilogue_mode;
1964 : }
1965 :
1966 : #define VECT_MAX_COST 1000
1967 :
1968 : /* The maximum number of intermediate steps required in multi-step type
1969 : conversion. */
1970 : #define MAX_INTERM_CVT_STEPS 3
1971 :
1972 : #define MAX_VECTORIZATION_FACTOR INT_MAX
1973 :
1974 : /* Nonzero if TYPE represents a (scalar) boolean type or type
1975 : in the middle-end compatible with it (unsigned precision 1 integral
1976 : types). Used to determine which types should be vectorized as
1977 : VECTOR_BOOLEAN_TYPE_P. */
1978 :
1979 : #define VECT_SCALAR_BOOLEAN_TYPE_P(TYPE) \
1980 : (TREE_CODE (TYPE) == BOOLEAN_TYPE \
1981 : || ((TREE_CODE (TYPE) == INTEGER_TYPE \
1982 : || TREE_CODE (TYPE) == ENUMERAL_TYPE) \
1983 : && TYPE_PRECISION (TYPE) == 1 \
1984 : && TYPE_UNSIGNED (TYPE)))
1985 :
1986 : inline bool
1987 12195948 : nested_in_vect_loop_p (class loop *loop, stmt_vec_info stmt_info)
1988 : {
1989 12195948 : return (loop->inner
1990 9798361 : && (loop->inner == (gimple_bb (stmt_info->stmt))->loop_father));
1991 : }
1992 :
1993 : /* PHI is either a scalar reduction phi or a scalar induction phi.
1994 : Return the initial value of the variable on entry to the containing
1995 : loop. */
1996 :
1997 : inline tree
1998 36628 : vect_phi_initial_value (gphi *phi)
1999 : {
2000 36628 : basic_block bb = gimple_bb (phi);
2001 36628 : edge pe = loop_preheader_edge (bb->loop_father);
2002 36628 : gcc_assert (pe->dest == bb);
2003 36628 : return PHI_ARG_DEF_FROM_EDGE (phi, pe);
2004 : }
2005 :
2006 : /* Return true if STMT_INFO should produce a vector mask type rather than
2007 : a normal nonmask type. */
2008 :
2009 : inline bool
2010 7387590 : vect_use_mask_type_p (stmt_vec_info stmt_info)
2011 : {
2012 7387590 : return stmt_info->mask_precision && stmt_info->mask_precision != ~0U;
2013 : }
2014 :
2015 : /* Return TRUE if a statement represented by STMT_INFO is a part of a
2016 : pattern. */
2017 :
2018 : inline bool
2019 133758638 : is_pattern_stmt_p (stmt_vec_info stmt_info)
2020 : {
2021 86051788 : return stmt_info->pattern_stmt_p;
2022 : }
2023 :
2024 : /* If STMT_INFO is a pattern statement, return the statement that it
2025 : replaces, otherwise return STMT_INFO itself. */
2026 :
2027 : inline stmt_vec_info
2028 52208972 : vect_orig_stmt (stmt_vec_info stmt_info)
2029 : {
2030 39763861 : if (is_pattern_stmt_p (stmt_info))
2031 4064303 : return STMT_VINFO_RELATED_STMT (stmt_info);
2032 : return stmt_info;
2033 : }
2034 :
2035 : /* Return the later statement between STMT1_INFO and STMT2_INFO. */
2036 :
2037 : inline stmt_vec_info
2038 6059319 : get_later_stmt (stmt_vec_info stmt1_info, stmt_vec_info stmt2_info)
2039 : {
2040 6059319 : gimple *stmt1 = vect_orig_stmt (stmt1_info)->stmt;
2041 6059319 : gimple *stmt2 = vect_orig_stmt (stmt2_info)->stmt;
2042 6059319 : if (gimple_bb (stmt1) == gimple_bb (stmt2))
2043 : {
2044 6041353 : if (gimple_uid (stmt1) > gimple_uid (stmt2))
2045 : return stmt1_info;
2046 : else
2047 1263128 : return stmt2_info;
2048 : }
2049 : /* ??? We should be really calling this function only with stmts
2050 : in the same BB but we can recover if there's a domination
2051 : relationship between them. */
2052 17966 : else if (dominated_by_p (CDI_DOMINATORS,
2053 17966 : gimple_bb (stmt1), gimple_bb (stmt2)))
2054 : return stmt1_info;
2055 7432 : else if (dominated_by_p (CDI_DOMINATORS,
2056 7432 : gimple_bb (stmt2), gimple_bb (stmt1)))
2057 : return stmt2_info;
2058 0 : gcc_unreachable ();
2059 : }
2060 :
2061 : /* If STMT_INFO has been replaced by a pattern statement, return the
2062 : replacement statement, otherwise return STMT_INFO itself. */
2063 :
2064 : inline stmt_vec_info
2065 54842800 : vect_stmt_to_vectorize (stmt_vec_info stmt_info)
2066 : {
2067 54842800 : if (STMT_VINFO_IN_PATTERN_P (stmt_info))
2068 1771045 : return STMT_VINFO_RELATED_STMT (stmt_info);
2069 : return stmt_info;
2070 : }
2071 :
2072 : /* Return true if BB is a loop header. */
2073 :
2074 : inline bool
2075 1425354 : is_loop_header_bb_p (basic_block bb)
2076 : {
2077 1425354 : if (bb == (bb->loop_father)->header)
2078 1416623 : return true;
2079 :
2080 : return false;
2081 : }
2082 :
2083 : /* Return pow2 (X). */
2084 :
2085 : inline int
2086 : vect_pow2 (int x)
2087 : {
2088 : int i, res = 1;
2089 :
2090 : for (i = 0; i < x; i++)
2091 : res *= 2;
2092 :
2093 : return res;
2094 : }
2095 :
2096 : /* Alias targetm.vectorize.builtin_vectorization_cost. */
2097 :
2098 : inline int
2099 9622654 : builtin_vectorization_cost (enum vect_cost_for_stmt type_of_cost,
2100 : tree vectype, int misalign)
2101 : {
2102 9553093 : return targetm.vectorize.builtin_vectorization_cost (type_of_cost,
2103 : vectype, misalign);
2104 : }
2105 :
2106 : /* Get cost by calling cost target builtin. */
2107 :
2108 : inline
2109 155 : int vect_get_stmt_cost (enum vect_cost_for_stmt type_of_cost)
2110 : {
2111 69406 : return builtin_vectorization_cost (type_of_cost, NULL, 0);
2112 : }
2113 :
2114 : /* Alias targetm.vectorize.init_cost. */
2115 :
2116 : inline vector_costs *
2117 2291866 : init_cost (vec_info *vinfo, bool costing_for_scalar)
2118 : {
2119 2291866 : return targetm.vectorize.create_costs (vinfo, costing_for_scalar);
2120 : }
2121 :
2122 : extern void dump_stmt_cost (FILE *, int, enum vect_cost_for_stmt,
2123 : stmt_vec_info, slp_tree, tree, int, unsigned,
2124 : enum vect_cost_model_location);
2125 :
2126 : /* Dump and add costs. */
2127 :
2128 : inline unsigned
2129 8120880 : add_stmt_cost (vector_costs *costs, int count,
2130 : enum vect_cost_for_stmt kind,
2131 : stmt_vec_info stmt_info, slp_tree node,
2132 : tree vectype, int misalign,
2133 : enum vect_cost_model_location where)
2134 : {
2135 : /* Even though a vector type might be set on stmt do not pass that on when
2136 : costing the scalar IL. A SLP node shouldn't have been recorded. */
2137 8120880 : if (costs->costing_for_scalar ())
2138 : {
2139 4150537 : vectype = NULL_TREE;
2140 4150537 : gcc_checking_assert (node == NULL);
2141 : }
2142 8120880 : unsigned cost = costs->add_stmt_cost (count, kind, stmt_info, node, vectype,
2143 : misalign, where);
2144 8120880 : if (dump_file && (dump_flags & TDF_DETAILS))
2145 232638 : dump_stmt_cost (dump_file, count, kind, stmt_info, node, vectype, misalign,
2146 : cost, where);
2147 8120880 : return cost;
2148 : }
2149 :
2150 : inline unsigned
2151 84967 : add_stmt_cost (vector_costs *costs, int count, enum vect_cost_for_stmt kind,
2152 : enum vect_cost_model_location where)
2153 : {
2154 84967 : gcc_assert (kind == cond_branch_taken || kind == cond_branch_not_taken
2155 : || kind == scalar_stmt);
2156 84967 : return add_stmt_cost (costs, count, kind, NULL, NULL, NULL_TREE, 0, where);
2157 : }
2158 :
2159 : inline unsigned
2160 2318112 : add_stmt_cost (vector_costs *costs, stmt_info_for_cost *i)
2161 : {
2162 2318112 : return add_stmt_cost (costs, i->count, i->kind, i->stmt_info, i->node,
2163 2318112 : i->vectype, i->misalign, i->where);
2164 : }
2165 :
2166 : inline void
2167 386642 : add_stmt_costs (vector_costs *costs, stmt_vector_for_cost *cost_vec)
2168 : {
2169 386642 : stmt_info_for_cost *cost;
2170 386642 : unsigned i;
2171 2219067 : FOR_EACH_VEC_ELT (*cost_vec, i, cost)
2172 1832425 : add_stmt_cost (costs, cost->count, cost->kind, cost->stmt_info,
2173 : cost->node, cost->vectype, cost->misalign, cost->where);
2174 386642 : }
2175 :
2176 : /*-----------------------------------------------------------------*/
2177 : /* Info on data references alignment. */
2178 : /*-----------------------------------------------------------------*/
2179 : #define DR_MISALIGNMENT_UNKNOWN (-1)
2180 : #define DR_MISALIGNMENT_UNINITIALIZED (-2)
2181 :
2182 : inline void
2183 2706120 : set_dr_misalignment (dr_vec_info *dr_info, int val)
2184 : {
2185 2706120 : dr_info->misalignment = val;
2186 : }
2187 :
2188 : extern int dr_misalignment (dr_vec_info *dr_info, tree vectype,
2189 : poly_int64 offset = 0);
2190 :
2191 : #define SET_DR_MISALIGNMENT(DR, VAL) set_dr_misalignment (DR, VAL)
2192 :
2193 : /* Only defined once DR_MISALIGNMENT is defined. */
2194 : inline const poly_uint64
2195 8244125 : dr_target_alignment (dr_vec_info *dr_info)
2196 : {
2197 8244125 : if (STMT_VINFO_GROUPED_ACCESS (dr_info->stmt))
2198 6048076 : dr_info = STMT_VINFO_DR_INFO (DR_GROUP_FIRST_ELEMENT (dr_info->stmt));
2199 8244125 : return dr_info->target_alignment;
2200 : }
2201 : #define DR_TARGET_ALIGNMENT(DR) dr_target_alignment (DR)
2202 : #define DR_SCALAR_KNOWN_BOUNDS(DR) (DR)->scalar_access_known_in_bounds
2203 :
2204 : /* Return if the stmt_vec_info requires peeling for alignment. */
2205 : inline bool
2206 4736703 : dr_safe_speculative_read_required (stmt_vec_info stmt_info)
2207 : {
2208 4736703 : dr_vec_info *dr_info;
2209 4736703 : if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
2210 1715609 : dr_info = STMT_VINFO_DR_INFO (DR_GROUP_FIRST_ELEMENT (stmt_info));
2211 : else
2212 3021094 : dr_info = STMT_VINFO_DR_INFO (stmt_info);
2213 :
2214 4736703 : return dr_info->safe_speculative_read_required;
2215 : }
2216 :
2217 : /* Set the safe_speculative_read_required for the stmt_vec_info, if group
2218 : access then set on the fist element otherwise set on DR directly. */
2219 : inline void
2220 246856 : dr_set_safe_speculative_read_required (stmt_vec_info stmt_info,
2221 : bool requires_alignment)
2222 : {
2223 246856 : dr_vec_info *dr_info;
2224 246856 : if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
2225 68435 : dr_info = STMT_VINFO_DR_INFO (DR_GROUP_FIRST_ELEMENT (stmt_info));
2226 : else
2227 178421 : dr_info = STMT_VINFO_DR_INFO (stmt_info);
2228 :
2229 246856 : dr_info->safe_speculative_read_required = requires_alignment;
2230 246856 : }
2231 :
2232 : inline void
2233 1670764 : set_dr_target_alignment (dr_vec_info *dr_info, poly_uint64 val)
2234 : {
2235 1670764 : dr_info->target_alignment = val;
2236 : }
2237 : #define SET_DR_TARGET_ALIGNMENT(DR, VAL) set_dr_target_alignment (DR, VAL)
2238 :
2239 : /* Return true if data access DR_INFO is aligned to the targets
2240 : preferred alignment for VECTYPE (which may be less than a full vector). */
2241 :
2242 : inline bool
2243 404480 : aligned_access_p (dr_vec_info *dr_info, tree vectype)
2244 : {
2245 404480 : return (dr_misalignment (dr_info, vectype) == 0);
2246 : }
2247 :
2248 : /* Return TRUE if the (mis-)alignment of the data access is known with
2249 : respect to the targets preferred alignment for VECTYPE, and FALSE
2250 : otherwise. */
2251 :
2252 : inline bool
2253 2449221 : known_alignment_for_access_p (dr_vec_info *dr_info, tree vectype)
2254 : {
2255 2189214 : return (dr_misalignment (dr_info, vectype) != DR_MISALIGNMENT_UNKNOWN);
2256 : }
2257 :
2258 : /* Return the minimum alignment in bytes that the vectorized version
2259 : of DR_INFO is guaranteed to have. */
2260 :
2261 : inline unsigned int
2262 263490 : vect_known_alignment_in_bytes (dr_vec_info *dr_info, tree vectype,
2263 : poly_int64 offset = 0)
2264 : {
2265 263490 : int misalignment = dr_misalignment (dr_info, vectype, offset);
2266 263490 : if (misalignment == DR_MISALIGNMENT_UNKNOWN)
2267 129704 : return TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_info->dr)));
2268 133786 : else if (misalignment == 0)
2269 92478 : return known_alignment (DR_TARGET_ALIGNMENT (dr_info));
2270 41308 : return misalignment & -misalignment;
2271 : }
2272 :
2273 : /* Return the behavior of DR_INFO with respect to the vectorization context
2274 : (which for outer loop vectorization might not be the behavior recorded
2275 : in DR_INFO itself). */
2276 :
2277 : inline innermost_loop_behavior *
2278 5895228 : vect_dr_behavior (vec_info *vinfo, dr_vec_info *dr_info)
2279 : {
2280 5895228 : stmt_vec_info stmt_info = dr_info->stmt;
2281 5895228 : loop_vec_info loop_vinfo = dyn_cast<loop_vec_info> (vinfo);
2282 2405872 : if (loop_vinfo == NULL
2283 2405872 : || !nested_in_vect_loop_p (LOOP_VINFO_LOOP (loop_vinfo), stmt_info))
2284 5890878 : return &DR_INNERMOST (dr_info->dr);
2285 : else
2286 4350 : return &STMT_VINFO_DR_WRT_VEC_LOOP (stmt_info);
2287 : }
2288 :
2289 : /* Return the offset calculated by adding the offset of this DR_INFO to the
2290 : corresponding data_reference's offset. If CHECK_OUTER then use
2291 : vect_dr_behavior to select the appropriate data_reference to use. */
2292 :
2293 : inline tree
2294 715165 : get_dr_vinfo_offset (vec_info *vinfo,
2295 : dr_vec_info *dr_info, bool check_outer = false)
2296 : {
2297 715165 : innermost_loop_behavior *base;
2298 715165 : if (check_outer)
2299 674743 : base = vect_dr_behavior (vinfo, dr_info);
2300 : else
2301 40422 : base = &dr_info->dr->innermost;
2302 :
2303 715165 : tree offset = base->offset;
2304 :
2305 715165 : if (!dr_info->offset)
2306 : return offset;
2307 :
2308 1160 : offset = fold_convert (sizetype, offset);
2309 1160 : return fold_build2 (PLUS_EXPR, TREE_TYPE (dr_info->offset), offset,
2310 : dr_info->offset);
2311 : }
2312 :
2313 :
2314 : /* Return the vect cost model for LOOP. */
2315 : inline enum vect_cost_model
2316 2476068 : loop_cost_model (loop_p loop)
2317 : {
2318 2476068 : if (loop != NULL
2319 1781192 : && loop->force_vectorize
2320 79669 : && flag_simd_cost_model != VECT_COST_MODEL_DEFAULT)
2321 : return flag_simd_cost_model;
2322 2396399 : return flag_vect_cost_model;
2323 : }
2324 :
2325 : /* Return true if the vect cost model is unlimited. */
2326 : inline bool
2327 1694697 : unlimited_cost_model (loop_p loop)
2328 : {
2329 1694697 : return loop_cost_model (loop) == VECT_COST_MODEL_UNLIMITED;
2330 : }
2331 :
2332 : /* Return true if the loop described by LOOP_VINFO is fully-masked and
2333 : if the first iteration should use a partial mask in order to achieve
2334 : alignment. */
2335 :
2336 : inline bool
2337 275473 : vect_use_loop_mask_for_alignment_p (loop_vec_info loop_vinfo)
2338 : {
2339 : /* With early break vectorization we don't know whether the accesses will stay
2340 : inside the loop or not. TODO: The early break adjustment code can be
2341 : implemented the same way as vectorizable_linear_induction. However we
2342 : can't test this today so reject it. */
2343 106 : return (LOOP_VINFO_FULLY_MASKED_P (loop_vinfo)
2344 106 : && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo)
2345 275481 : && !(LOOP_VINFO_NON_LINEAR_IV (loop_vinfo)
2346 0 : && LOOP_VINFO_EARLY_BREAKS (loop_vinfo)));
2347 : }
2348 :
2349 : /* Return the number of vectors of type VECTYPE that are needed to get
2350 : NUNITS elements. NUNITS should be based on the vectorization factor,
2351 : so it is always a known multiple of the number of elements in VECTYPE. */
2352 :
2353 : inline unsigned int
2354 5612688 : vect_get_num_vectors (poly_uint64 nunits, tree vectype)
2355 : {
2356 5612688 : return exact_div (nunits, TYPE_VECTOR_SUBPARTS (vectype)).to_constant ();
2357 : }
2358 :
2359 : /* Return the number of vectors in the context of vectorization region VINFO,
2360 : needed for a group of statements and a vector type as specified by NODE. */
2361 :
2362 : inline unsigned int
2363 5611805 : vect_get_num_copies (vec_info *vinfo, slp_tree node)
2364 : {
2365 5611805 : poly_uint64 vf;
2366 :
2367 5611805 : if (loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo))
2368 3085108 : vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2369 : else
2370 : vf = 1;
2371 :
2372 5611805 : vf *= SLP_TREE_LANES (node);
2373 5611805 : tree vectype = SLP_TREE_VECTYPE (node);
2374 :
2375 5611805 : return vect_get_num_vectors (vf, vectype);
2376 : }
2377 :
2378 : /* Return the vectorization factor that should be used for costing
2379 : purposes while vectorizing the loop described by LOOP_VINFO.
2380 : Pick a reasonable estimate if the vectorization factor isn't
2381 : known at compile time. */
2382 :
2383 : inline unsigned int
2384 1442272 : vect_vf_for_cost (loop_vec_info loop_vinfo)
2385 : {
2386 1442272 : return estimated_poly_value (LOOP_VINFO_VECT_FACTOR (loop_vinfo));
2387 : }
2388 :
2389 : /* Estimate the number of elements in VEC_TYPE for costing purposes.
2390 : Pick a reasonable estimate if the exact number isn't known at
2391 : compile time. */
2392 :
2393 : inline unsigned int
2394 60779 : vect_nunits_for_cost (tree vec_type)
2395 : {
2396 60779 : return estimated_poly_value (TYPE_VECTOR_SUBPARTS (vec_type));
2397 : }
2398 :
2399 : /* Return the maximum possible vectorization factor for LOOP_VINFO. */
2400 :
2401 : inline unsigned HOST_WIDE_INT
2402 102269 : vect_max_vf (loop_vec_info loop_vinfo)
2403 : {
2404 102269 : unsigned HOST_WIDE_INT vf;
2405 102269 : if (LOOP_VINFO_VECT_FACTOR (loop_vinfo).is_constant (&vf))
2406 102269 : return vf;
2407 : return MAX_VECTORIZATION_FACTOR;
2408 : }
2409 :
2410 : /* Return the size of the value accessed by unvectorized data reference
2411 : DR_INFO. This is only valid once STMT_VINFO_VECTYPE has been calculated
2412 : for the associated gimple statement, since that guarantees that DR_INFO
2413 : accesses either a scalar or a scalar equivalent. ("Scalar equivalent"
2414 : here includes things like V1SI, which can be vectorized in the same way
2415 : as a plain SI.) */
2416 :
2417 : inline unsigned int
2418 2034940 : vect_get_scalar_dr_size (dr_vec_info *dr_info)
2419 : {
2420 2034940 : return tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_info->dr))));
2421 : }
2422 :
2423 : /* Return true if LOOP_VINFO requires a runtime check for whether the
2424 : vector loop is profitable. */
2425 :
2426 : inline bool
2427 74368 : vect_apply_runtime_profitability_check_p (loop_vec_info loop_vinfo)
2428 : {
2429 74368 : unsigned int th = LOOP_VINFO_COST_MODEL_THRESHOLD (loop_vinfo);
2430 39610 : return (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
2431 74368 : && th >= vect_vf_for_cost (loop_vinfo));
2432 : }
2433 :
2434 : /* Return true if CODE is a lane-reducing opcode. */
2435 :
2436 : inline bool
2437 393794 : lane_reducing_op_p (code_helper code)
2438 : {
2439 393794 : return code == DOT_PROD_EXPR || code == WIDEN_SUM_EXPR || code == SAD_EXPR;
2440 : }
2441 :
2442 : /* Return true if STMT is a lane-reducing statement. */
2443 :
2444 : inline bool
2445 496092 : lane_reducing_stmt_p (gimple *stmt)
2446 : {
2447 496092 : if (auto *assign = dyn_cast <gassign *> (stmt))
2448 347222 : return lane_reducing_op_p (gimple_assign_rhs_code (assign));
2449 : return false;
2450 : }
2451 :
2452 : /* Source location + hotness information. */
2453 : extern dump_user_location_t vect_location;
2454 :
2455 : /* A macro for calling:
2456 : dump_begin_scope (MSG, vect_location);
2457 : via an RAII object, thus printing "=== MSG ===\n" to the dumpfile etc,
2458 : and then calling
2459 : dump_end_scope ();
2460 : once the object goes out of scope, thus capturing the nesting of
2461 : the scopes.
2462 :
2463 : These scopes affect dump messages within them: dump messages at the
2464 : top level implicitly default to MSG_PRIORITY_USER_FACING, whereas those
2465 : in a nested scope implicitly default to MSG_PRIORITY_INTERNALS. */
2466 :
2467 : #define DUMP_VECT_SCOPE(MSG) \
2468 : AUTO_DUMP_SCOPE (MSG, vect_location)
2469 :
2470 : /* A sentinel class for ensuring that the "vect_location" global gets
2471 : reset at the end of a scope.
2472 :
2473 : The "vect_location" global is used during dumping and contains a
2474 : location_t, which could contain references to a tree block via the
2475 : ad-hoc data. This data is used for tracking inlining information,
2476 : but it's not a GC root; it's simply assumed that such locations never
2477 : get accessed if the blocks are optimized away.
2478 :
2479 : Hence we need to ensure that such locations are purged at the end
2480 : of any operations using them (e.g. via this class). */
2481 :
2482 : class auto_purge_vect_location
2483 : {
2484 : public:
2485 : ~auto_purge_vect_location ();
2486 : };
2487 :
2488 : /*-----------------------------------------------------------------*/
2489 : /* Function prototypes. */
2490 : /*-----------------------------------------------------------------*/
2491 :
2492 : /* Simple loop peeling and versioning utilities for vectorizer's purposes -
2493 : in tree-vect-loop-manip.cc. */
2494 : extern void vect_set_loop_condition (class loop *, edge, loop_vec_info,
2495 : tree, tree, tree, bool);
2496 : extern bool slpeel_can_duplicate_loop_p (const class loop *, const_edge,
2497 : const_edge);
2498 : class loop *slpeel_tree_duplicate_loop_to_edge_cfg (class loop *, edge,
2499 : class loop *, edge,
2500 : edge, edge *, bool = true,
2501 : vec<basic_block> * = NULL,
2502 : bool = false, bool = false,
2503 : bool = true);
2504 : class loop *vect_loop_versioning (loop_vec_info, gimple *);
2505 : extern class loop *vect_do_peeling (loop_vec_info, tree, tree,
2506 : tree *, tree *, tree *, int, bool, bool,
2507 : tree *);
2508 : extern tree vect_get_main_loop_result (loop_vec_info, tree, tree);
2509 : extern void vect_prepare_for_masked_peels (loop_vec_info);
2510 : extern dump_user_location_t find_loop_location (class loop *);
2511 : extern bool vect_can_advance_ivs_p (loop_vec_info);
2512 : extern void vect_update_inits_of_drs (loop_vec_info, tree, tree_code);
2513 : extern edge vec_init_loop_exit_info (class loop *);
2514 : extern void vect_iv_increment_position (edge, gimple_stmt_iterator *, bool *);
2515 :
2516 : /* In tree-vect-stmts.cc. */
2517 : extern tree get_related_vectype_for_scalar_type (machine_mode, tree,
2518 : poly_uint64 = 0);
2519 : extern tree get_vectype_for_scalar_type (vec_info *, tree, unsigned int = 0);
2520 : extern tree get_vectype_for_scalar_type (vec_info *, tree, slp_tree);
2521 : extern tree get_mask_type_for_scalar_type (vec_info *, tree, unsigned int = 0);
2522 : extern tree get_mask_type_for_scalar_type (vec_info *, tree, slp_tree);
2523 : extern tree get_same_sized_vectype (tree, tree);
2524 : extern bool vect_chooses_same_modes_p (vec_info *, machine_mode);
2525 : extern bool vect_chooses_same_modes_p (machine_mode, machine_mode);
2526 : extern bool vect_get_loop_mask_type (loop_vec_info);
2527 : extern bool vect_is_simple_use (tree, vec_info *, enum vect_def_type *,
2528 : stmt_vec_info * = NULL, gimple ** = NULL);
2529 : extern bool vect_is_simple_use (vec_info *, slp_tree,
2530 : unsigned, tree *, slp_tree *,
2531 : enum vect_def_type *,
2532 : tree *, stmt_vec_info * = NULL);
2533 : extern bool vect_is_simple_use (vec_info *, slp_tree,
2534 : unsigned, slp_tree *,
2535 : enum vect_def_type *, tree *);
2536 : extern bool vect_maybe_update_slp_op_vectype (slp_tree, tree);
2537 : extern tree perm_mask_for_reverse (tree);
2538 : extern bool supportable_widening_operation (code_helper, tree, tree, bool,
2539 : code_helper*, code_helper*,
2540 : int*, vec<tree> *);
2541 : extern bool supportable_narrowing_operation (code_helper, tree, tree,
2542 : code_helper *, int *,
2543 : vec<tree> *);
2544 : extern bool supportable_indirect_convert_operation (code_helper,
2545 : tree, tree,
2546 : vec<std::pair<tree, tree_code> > &,
2547 : slp_tree = NULL);
2548 : extern int compare_step_with_zero (vec_info *, stmt_vec_info);
2549 :
2550 : extern unsigned record_stmt_cost (stmt_vector_for_cost *, int,
2551 : enum vect_cost_for_stmt, stmt_vec_info,
2552 : tree, int, enum vect_cost_model_location);
2553 : extern unsigned record_stmt_cost (stmt_vector_for_cost *, int,
2554 : enum vect_cost_for_stmt, slp_tree,
2555 : tree, int, enum vect_cost_model_location);
2556 : extern unsigned record_stmt_cost (stmt_vector_for_cost *, int,
2557 : enum vect_cost_for_stmt,
2558 : enum vect_cost_model_location);
2559 : extern unsigned record_stmt_cost (stmt_vector_for_cost *, int,
2560 : enum vect_cost_for_stmt, stmt_vec_info,
2561 : slp_tree, tree, int,
2562 : enum vect_cost_model_location);
2563 :
2564 : /* Overload of record_stmt_cost with VECTYPE derived from STMT_INFO. */
2565 :
2566 : inline unsigned
2567 1905184 : record_stmt_cost (stmt_vector_for_cost *body_cost_vec, int count,
2568 : enum vect_cost_for_stmt kind, stmt_vec_info stmt_info,
2569 : int misalign, enum vect_cost_model_location where)
2570 : {
2571 1905184 : return record_stmt_cost (body_cost_vec, count, kind, stmt_info,
2572 : STMT_VINFO_VECTYPE (stmt_info), misalign, where);
2573 : }
2574 :
2575 : /* Overload of record_stmt_cost with VECTYPE derived from SLP node. */
2576 :
2577 : inline unsigned
2578 1673275 : record_stmt_cost (stmt_vector_for_cost *body_cost_vec, int count,
2579 : enum vect_cost_for_stmt kind, slp_tree node,
2580 : int misalign, enum vect_cost_model_location where)
2581 : {
2582 1465496 : return record_stmt_cost (body_cost_vec, count, kind, node,
2583 : SLP_TREE_VECTYPE (node), misalign, where);
2584 : }
2585 :
2586 : extern void vect_finish_replace_stmt (vec_info *, stmt_vec_info, gimple *);
2587 : extern void vect_finish_stmt_generation (vec_info *, stmt_vec_info, gimple *,
2588 : gimple_stmt_iterator *);
2589 : extern opt_result vect_mark_stmts_to_be_vectorized (loop_vec_info, bool *);
2590 : extern tree vect_get_store_rhs (stmt_vec_info);
2591 : void vect_get_vec_defs (vec_info *, slp_tree,
2592 : bool, vec<tree> *,
2593 : bool = false, vec<tree> * = NULL,
2594 : bool = false, vec<tree> * = NULL,
2595 : bool = false, vec<tree> * = NULL);
2596 : extern tree vect_init_vector (vec_info *, stmt_vec_info, tree, tree,
2597 : gimple_stmt_iterator *);
2598 : extern tree vect_get_slp_vect_def (slp_tree, unsigned);
2599 : extern void vect_transform_stmt (vec_info *, stmt_vec_info,
2600 : gimple_stmt_iterator *,
2601 : slp_tree, slp_instance);
2602 : extern void vect_remove_stores (vec_info *, stmt_vec_info);
2603 : extern bool vect_nop_conversion_p (stmt_vec_info);
2604 : extern opt_result vect_analyze_stmt (vec_info *, slp_tree,
2605 : slp_instance, stmt_vector_for_cost *);
2606 : extern void vect_get_load_cost (vec_info *, stmt_vec_info, slp_tree, int,
2607 : dr_alignment_support, int, bool,
2608 : unsigned int *, unsigned int *,
2609 : stmt_vector_for_cost *,
2610 : stmt_vector_for_cost *, bool);
2611 : extern void vect_get_store_cost (vec_info *, stmt_vec_info, slp_tree, int,
2612 : dr_alignment_support, int,
2613 : unsigned int *, stmt_vector_for_cost *);
2614 : extern bool vect_supportable_shift (vec_info *, enum tree_code, tree);
2615 : extern tree vect_gen_perm_mask_any (tree, const vec_perm_indices &);
2616 : extern tree vect_gen_perm_mask_checked (tree, const vec_perm_indices &);
2617 : extern void optimize_mask_stores (class loop*);
2618 : extern tree vect_gen_while (gimple_seq *, tree, tree, tree,
2619 : const char * = nullptr);
2620 : extern tree vect_gen_while_not (gimple_seq *, tree, tree, tree);
2621 : extern opt_result vect_get_vector_types_for_stmt (vec_info *,
2622 : stmt_vec_info, tree *,
2623 : unsigned int = 0);
2624 : extern opt_tree vect_get_mask_type_for_stmt (stmt_vec_info, unsigned int = 0);
2625 :
2626 : /* In tree-if-conv.cc. */
2627 : extern bool ref_within_array_bound (gimple *, tree);
2628 :
2629 : /* In tree-vect-data-refs.cc. */
2630 : extern bool vect_can_force_dr_alignment_p (const_tree, poly_uint64);
2631 : extern enum dr_alignment_support vect_supportable_dr_alignment
2632 : (vec_info *, dr_vec_info *, tree, int,
2633 : bool = false);
2634 : extern opt_result vect_analyze_data_ref_dependences (loop_vec_info, unsigned int *);
2635 : extern bool vect_slp_analyze_instance_dependence (vec_info *, slp_instance);
2636 : extern opt_result vect_enhance_data_refs_alignment (loop_vec_info);
2637 : extern void vect_analyze_data_refs_alignment (loop_vec_info);
2638 : extern bool vect_slp_analyze_instance_alignment (vec_info *, slp_instance);
2639 : extern opt_result vect_analyze_data_ref_accesses (vec_info *, vec<int> *);
2640 : extern opt_result vect_prune_runtime_alias_test_list (loop_vec_info);
2641 : extern bool vect_gather_scatter_fn_p (vec_info *, bool, bool, tree, tree,
2642 : tree, int, int *, internal_fn *, tree *,
2643 : tree *, vec<int> * = nullptr);
2644 : extern bool vect_check_gather_scatter (stmt_vec_info, tree,
2645 : loop_vec_info, gather_scatter_info *,
2646 : vec<int> * = nullptr);
2647 : extern void vect_describe_gather_scatter_call (stmt_vec_info,
2648 : gather_scatter_info *);
2649 : extern opt_result vect_find_stmt_data_reference (loop_p, gimple *,
2650 : vec<data_reference_p> *,
2651 : vec<int> *, int);
2652 : extern opt_result vect_analyze_data_refs (vec_info *, bool *);
2653 : extern void vect_record_base_alignments (vec_info *);
2654 : extern tree vect_create_data_ref_ptr (vec_info *,
2655 : stmt_vec_info, tree, class loop *, tree,
2656 : tree *, gimple_stmt_iterator *,
2657 : gimple **, bool,
2658 : tree = NULL_TREE);
2659 : extern tree bump_vector_ptr (vec_info *, tree, gimple_stmt_iterator *,
2660 : stmt_vec_info, tree);
2661 : extern void vect_copy_ref_info (tree, tree);
2662 : extern tree vect_create_destination_var (tree, tree);
2663 : extern bool vect_grouped_store_supported (tree, unsigned HOST_WIDE_INT);
2664 : extern internal_fn vect_store_lanes_supported (tree, unsigned HOST_WIDE_INT, bool);
2665 : extern bool vect_grouped_load_supported (tree, bool, unsigned HOST_WIDE_INT);
2666 : extern internal_fn vect_load_lanes_supported (tree, unsigned HOST_WIDE_INT,
2667 : bool, vec<int> * = nullptr);
2668 : extern tree vect_setup_realignment (vec_info *,
2669 : stmt_vec_info, tree, gimple_stmt_iterator *,
2670 : tree *, enum dr_alignment_support, tree,
2671 : class loop **);
2672 : extern tree vect_get_new_vect_var (tree, enum vect_var_kind, const char *);
2673 : extern tree vect_get_new_ssa_name (tree, enum vect_var_kind,
2674 : const char * = NULL);
2675 : extern tree vect_create_addr_base_for_vector_ref (vec_info *,
2676 : stmt_vec_info, gimple_seq *,
2677 : tree);
2678 :
2679 : /* In tree-vect-loop.cc. */
2680 : extern tree neutral_op_for_reduction (tree, code_helper, tree, bool = true);
2681 : extern widest_int vect_iv_limit_for_partial_vectors (loop_vec_info loop_vinfo);
2682 : bool vect_rgroup_iv_might_wrap_p (loop_vec_info, rgroup_controls *);
2683 : /* Used in gimple-loop-interchange.c and tree-parloops.cc. */
2684 : extern bool check_reduction_path (dump_user_location_t, loop_p, gphi *, tree,
2685 : enum tree_code);
2686 : extern bool needs_fold_left_reduction_p (tree, code_helper);
2687 : /* Drive for loop analysis stage. */
2688 : extern opt_loop_vec_info vect_analyze_loop (class loop *, gimple *,
2689 : vec_info_shared *);
2690 : extern tree vect_build_loop_niters (loop_vec_info, bool * = NULL);
2691 : extern void vect_gen_vector_loop_niters (loop_vec_info, tree, tree *,
2692 : tree *, bool);
2693 : extern tree vect_get_loop_iv_increment (loop_vec_info);
2694 : extern tree vect_halve_mask_nunits (tree, machine_mode);
2695 : extern tree vect_double_mask_nunits (tree, machine_mode);
2696 : extern void vect_record_loop_mask (loop_vec_info, vec_loop_masks *,
2697 : unsigned int, tree, tree);
2698 : extern tree vect_get_loop_mask (loop_vec_info, gimple_stmt_iterator *,
2699 : vec_loop_masks *,
2700 : unsigned int, tree, unsigned int);
2701 : extern void vect_record_loop_len (loop_vec_info, vec_loop_lens *, unsigned int,
2702 : tree, unsigned int);
2703 : extern tree vect_get_loop_len (loop_vec_info, gimple_stmt_iterator *,
2704 : vec_loop_lens *, unsigned int, tree,
2705 : unsigned int, unsigned int, bool);
2706 : extern tree vect_gen_loop_len_mask (loop_vec_info, gimple_stmt_iterator *,
2707 : gimple_stmt_iterator *, vec_loop_lens *,
2708 : unsigned int, tree, tree, unsigned int,
2709 : unsigned int);
2710 : extern gimple_seq vect_gen_len (tree, tree, tree, tree);
2711 : extern vect_reduc_info info_for_reduction (loop_vec_info, slp_tree);
2712 : extern bool reduction_fn_for_scalar_code (code_helper, internal_fn *);
2713 : extern unsigned vect_min_prec_for_max_niters (loop_vec_info, unsigned int);
2714 : /* Drive for loop transformation stage. */
2715 : extern class loop *vect_transform_loop (loop_vec_info, gimple *);
2716 470810 : struct vect_loop_form_info
2717 : {
2718 : tree number_of_iterations;
2719 : tree number_of_iterationsm1;
2720 : tree assumptions;
2721 : auto_vec<gcond *> conds;
2722 : gcond *inner_loop_cond;
2723 : edge loop_exit;
2724 : basic_block *bbs = nullptr;
2725 470810 : ~vect_loop_form_info () { free (bbs); }
2726 : };
2727 : extern opt_result vect_analyze_loop_form (class loop *, gimple *,
2728 : vect_loop_form_info *);
2729 : extern loop_vec_info vect_create_loop_vinfo (class loop *, vec_info_shared *,
2730 : const vect_loop_form_info *,
2731 : loop_vec_info = nullptr);
2732 : extern bool vectorizable_live_operation (vec_info *, stmt_vec_info,
2733 : slp_tree, slp_instance, int,
2734 : bool, stmt_vector_for_cost *);
2735 : extern bool vectorizable_lane_reducing (loop_vec_info, stmt_vec_info,
2736 : slp_tree, stmt_vector_for_cost *);
2737 : extern bool vectorizable_reduction (loop_vec_info, stmt_vec_info,
2738 : slp_tree, slp_instance,
2739 : stmt_vector_for_cost *);
2740 : extern bool vectorizable_induction (loop_vec_info, stmt_vec_info,
2741 : slp_tree, stmt_vector_for_cost *);
2742 : extern bool vect_transform_reduction (loop_vec_info, stmt_vec_info,
2743 : gimple_stmt_iterator *,
2744 : slp_tree);
2745 : extern bool vect_transform_cycle_phi (loop_vec_info, stmt_vec_info,
2746 : slp_tree, slp_instance);
2747 : extern bool vectorizable_lc_phi (loop_vec_info, stmt_vec_info, slp_tree);
2748 : extern bool vect_transform_lc_phi (loop_vec_info, stmt_vec_info, slp_tree);
2749 : extern bool vectorizable_phi (bb_vec_info, stmt_vec_info, slp_tree,
2750 : stmt_vector_for_cost *);
2751 : extern bool vectorizable_recurr (loop_vec_info, stmt_vec_info,
2752 : slp_tree, stmt_vector_for_cost *);
2753 : extern bool vectorizable_early_exit (loop_vec_info, stmt_vec_info,
2754 : gimple_stmt_iterator *,
2755 : slp_tree, stmt_vector_for_cost *);
2756 : extern bool vect_emulated_vector_p (tree);
2757 : extern bool vect_can_vectorize_without_simd_p (tree_code);
2758 : extern bool vect_can_vectorize_without_simd_p (code_helper);
2759 : extern int vect_get_known_peeling_cost (loop_vec_info, int);
2760 : extern tree cse_and_gimplify_to_preheader (loop_vec_info, tree);
2761 :
2762 : /* Nonlinear induction. */
2763 : extern tree vect_peel_nonlinear_iv_init (gimple_seq*, tree, tree,
2764 : tree, enum vect_induction_op_type,
2765 : bool);
2766 :
2767 : /* In tree-vect-slp.cc. */
2768 : extern void vect_slp_init (void);
2769 : extern void vect_slp_fini (void);
2770 : extern void vect_free_slp_instance (slp_instance);
2771 : extern bool vect_transform_slp_perm_load (vec_info *, slp_tree, const vec<tree> &,
2772 : gimple_stmt_iterator *, poly_uint64,
2773 : bool, unsigned *,
2774 : unsigned * = nullptr, bool = false);
2775 : extern bool vectorizable_slp_permutation (vec_info *, gimple_stmt_iterator *,
2776 : slp_tree, stmt_vector_for_cost *);
2777 : extern bool vect_slp_analyze_operations (vec_info *);
2778 : extern bool vect_schedule_slp (vec_info *, vec<slp_instance> &, bool);
2779 : extern opt_result vect_analyze_slp (vec_info *, unsigned, bool);
2780 : extern bool vect_make_slp_decision (loop_vec_info);
2781 : extern void vect_optimize_slp (vec_info *);
2782 : extern void vect_gather_slp_loads (vec_info *);
2783 : extern tree vect_get_slp_scalar_def (slp_tree, unsigned);
2784 : extern void vect_get_slp_defs (slp_tree, vec<tree> *);
2785 : extern void vect_get_slp_defs (vec_info *, slp_tree, vec<vec<tree> > *,
2786 : unsigned n = -1U);
2787 : extern bool vect_slp_if_converted_bb (basic_block bb, loop_p orig_loop);
2788 : extern bool vect_slp_function (function *);
2789 : extern stmt_vec_info vect_find_last_scalar_stmt_in_slp (slp_tree);
2790 : extern stmt_vec_info vect_find_first_scalar_stmt_in_slp (slp_tree);
2791 : extern bool is_simple_and_all_uses_invariant (stmt_vec_info, loop_vec_info);
2792 : extern bool can_duplicate_and_interleave_p (vec_info *, unsigned int, tree,
2793 : unsigned int * = NULL,
2794 : tree * = NULL, tree * = NULL);
2795 : extern void duplicate_and_interleave (vec_info *, gimple_seq *, tree,
2796 : const vec<tree> &, unsigned int, vec<tree> &);
2797 : extern int vect_get_place_in_interleaving_chain (stmt_vec_info, stmt_vec_info);
2798 : extern slp_tree vect_create_new_slp_node (unsigned, tree_code);
2799 : extern void vect_free_slp_tree (slp_tree);
2800 : extern bool compatible_calls_p (gcall *, gcall *, bool);
2801 : extern int vect_slp_child_index_for_operand (const stmt_vec_info, int op);
2802 :
2803 : extern tree prepare_vec_mask (loop_vec_info, tree, tree, tree,
2804 : gimple_stmt_iterator *);
2805 : extern tree vect_get_mask_load_else (int, tree);
2806 : extern bool vect_load_perm_consecutive_p (slp_tree, unsigned = UINT_MAX);
2807 : extern bool vect_get_num_copies_for_invariant (vec_info *, slp_tree,
2808 : unsigned *, unsigned *);
2809 :
2810 : /* In tree-vect-patterns.cc. */
2811 : extern void
2812 : vect_mark_pattern_stmts (vec_info *, stmt_vec_info, gimple *, tree);
2813 : extern bool vect_get_range_info (tree, wide_int*, wide_int*);
2814 :
2815 : /* Pattern recognition functions.
2816 : Additional pattern recognition functions can (and will) be added
2817 : in the future. */
2818 : void vect_pattern_recog (vec_info *);
2819 :
2820 : /* In tree-vectorizer.cc. */
2821 : unsigned vectorize_loops (void);
2822 : void vect_free_loop_info_assumptions (class loop *);
2823 : gimple *vect_loop_vectorized_call (class loop *, gcond **cond = NULL);
2824 : bool vect_stmt_dominates_stmt_p (gimple *, gimple *);
2825 :
2826 : /* SLP Pattern matcher types, tree-vect-slp-patterns.cc. */
2827 :
2828 : /* Forward declaration of possible two operands operation that can be matched
2829 : by the complex numbers pattern matchers. */
2830 : enum _complex_operation : unsigned;
2831 :
2832 : /* All possible load permute values that could result from the partial data-flow
2833 : analysis. */
2834 : typedef enum _complex_perm_kinds {
2835 : PERM_UNKNOWN,
2836 : PERM_EVENODD,
2837 : PERM_ODDEVEN,
2838 : PERM_ODDODD,
2839 : PERM_EVENEVEN,
2840 : /* Can be combined with any other PERM values. */
2841 : PERM_TOP
2842 : } complex_perm_kinds_t;
2843 :
2844 : /* Cache from nodes to the load permutation they represent. */
2845 : typedef hash_map <slp_tree, complex_perm_kinds_t>
2846 : slp_tree_to_load_perm_map_t;
2847 :
2848 : /* Cache from nodes pair to being compatible or not. */
2849 : typedef pair_hash <nofree_ptr_hash <_slp_tree>,
2850 : nofree_ptr_hash <_slp_tree>> slp_node_hash;
2851 : typedef hash_map <slp_node_hash, bool> slp_compat_nodes_map_t;
2852 :
2853 :
2854 : /* Vector pattern matcher base class. All SLP pattern matchers must inherit
2855 : from this type. */
2856 :
2857 : class vect_pattern
2858 : {
2859 : protected:
2860 : /* The number of arguments that the IFN requires. */
2861 : unsigned m_num_args;
2862 :
2863 : /* The internal function that will be used when a pattern is created. */
2864 : internal_fn m_ifn;
2865 :
2866 : /* The current node being inspected. */
2867 : slp_tree *m_node;
2868 :
2869 : /* The list of operands to be the children for the node produced when the
2870 : internal function is created. */
2871 : vec<slp_tree> m_ops;
2872 :
2873 : /* Default constructor where NODE is the root of the tree to inspect. */
2874 1114 : vect_pattern (slp_tree *node, vec<slp_tree> *m_ops, internal_fn ifn)
2875 32 : {
2876 1114 : this->m_ifn = ifn;
2877 1114 : this->m_node = node;
2878 1114 : this->m_ops.create (0);
2879 1114 : if (m_ops)
2880 32 : this->m_ops.safe_splice (*m_ops);
2881 : }
2882 :
2883 : public:
2884 :
2885 : /* Create a new instance of the pattern matcher class of the given type. */
2886 : static vect_pattern* recognize (slp_tree_to_load_perm_map_t *,
2887 : slp_compat_nodes_map_t *, slp_tree *);
2888 :
2889 : /* Build the pattern from the data collected so far. */
2890 : virtual void build (vec_info *) = 0;
2891 :
2892 : /* Default destructor. */
2893 : virtual ~vect_pattern ()
2894 : {
2895 : this->m_ops.release ();
2896 : }
2897 : };
2898 :
2899 : /* Function pointer to create a new pattern matcher from a generic type. */
2900 : typedef vect_pattern* (*vect_pattern_decl_t) (slp_tree_to_load_perm_map_t *,
2901 : slp_compat_nodes_map_t *,
2902 : slp_tree *);
2903 :
2904 : /* List of supported pattern matchers. */
2905 : extern vect_pattern_decl_t slp_patterns[];
2906 :
2907 : /* Number of supported pattern matchers. */
2908 : extern size_t num__slp_patterns;
2909 :
2910 : /* ----------------------------------------------------------------------
2911 : Target support routines
2912 : -----------------------------------------------------------------------
2913 : The following routines are provided to simplify costing decisions in
2914 : target code. Please add more as needed. */
2915 :
2916 : /* Return true if an operation of kind KIND for STMT_INFO represents
2917 : the extraction of an element from a vector in preparation for
2918 : storing the element to memory. */
2919 : inline bool
2920 : vect_is_store_elt_extraction (vect_cost_for_stmt kind, stmt_vec_info stmt_info)
2921 : {
2922 : return (kind == vec_to_scalar
2923 : && STMT_VINFO_DATA_REF (stmt_info)
2924 : && DR_IS_WRITE (STMT_VINFO_DATA_REF (stmt_info)));
2925 : }
2926 :
2927 : /* Return true if STMT_INFO represents part of a reduction. */
2928 : inline bool
2929 51849210 : vect_is_reduction (stmt_vec_info stmt_info)
2930 : {
2931 51849210 : return STMT_VINFO_REDUC_IDX (stmt_info) != -1;
2932 : }
2933 :
2934 : /* Return true if SLP_NODE represents part of a reduction. */
2935 : inline bool
2936 287949 : vect_is_reduction (slp_tree slp_node)
2937 : {
2938 287949 : return SLP_TREE_REDUC_IDX (slp_node) != -1;
2939 : }
2940 :
2941 : /* If STMT_INFO describes a reduction, return the vect_reduction_type
2942 : of the reduction it describes, otherwise return -1. */
2943 : inline int
2944 56690 : vect_reduc_type (vec_info *vinfo, slp_tree node)
2945 : {
2946 56690 : if (loop_vec_info loop_vinfo = dyn_cast<loop_vec_info> (vinfo))
2947 : {
2948 56690 : vect_reduc_info reduc_info = info_for_reduction (loop_vinfo, node);
2949 56690 : if (reduc_info)
2950 53689 : return int (VECT_REDUC_INFO_TYPE (reduc_info));
2951 : }
2952 : return -1;
2953 : }
2954 :
2955 : /* If STMT_INFO is a COND_EXPR that includes an embedded comparison, return the
2956 : scalar type of the values being compared. Return null otherwise. */
2957 : inline tree
2958 0 : vect_embedded_comparison_type (stmt_vec_info stmt_info)
2959 : {
2960 0 : if (auto *assign = dyn_cast<gassign *> (stmt_info->stmt))
2961 0 : if (gimple_assign_rhs_code (assign) == COND_EXPR)
2962 : {
2963 0 : tree cond = gimple_assign_rhs1 (assign);
2964 0 : if (COMPARISON_CLASS_P (cond))
2965 0 : return TREE_TYPE (TREE_OPERAND (cond, 0));
2966 : }
2967 : return NULL_TREE;
2968 : }
2969 :
2970 : /* If STMT_INFO is a comparison or contains an embedded comparison, return the
2971 : scalar type of the values being compared. Return null otherwise. */
2972 : inline tree
2973 68141 : vect_comparison_type (stmt_vec_info stmt_info)
2974 : {
2975 68141 : if (auto *assign = dyn_cast<gassign *> (stmt_info->stmt))
2976 68141 : if (TREE_CODE_CLASS (gimple_assign_rhs_code (assign)) == tcc_comparison)
2977 68141 : return TREE_TYPE (gimple_assign_rhs1 (assign));
2978 0 : return vect_embedded_comparison_type (stmt_info);
2979 : }
2980 :
2981 : /* Return true if STMT_INFO extends the result of a load. */
2982 : inline bool
2983 : vect_is_extending_load (class vec_info *vinfo, stmt_vec_info stmt_info)
2984 : {
2985 : /* Although this is quite large for an inline function, this part
2986 : at least should be inline. */
2987 : gassign *assign = dyn_cast <gassign *> (stmt_info->stmt);
2988 : if (!assign || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (assign)))
2989 : return false;
2990 :
2991 : tree rhs = gimple_assign_rhs1 (stmt_info->stmt);
2992 : tree lhs_type = TREE_TYPE (gimple_assign_lhs (assign));
2993 : tree rhs_type = TREE_TYPE (rhs);
2994 : if (!INTEGRAL_TYPE_P (lhs_type)
2995 : || !INTEGRAL_TYPE_P (rhs_type)
2996 : || TYPE_PRECISION (lhs_type) <= TYPE_PRECISION (rhs_type))
2997 : return false;
2998 :
2999 : stmt_vec_info def_stmt_info = vinfo->lookup_def (rhs);
3000 : return (def_stmt_info
3001 : && STMT_VINFO_DATA_REF (def_stmt_info)
3002 : && DR_IS_READ (STMT_VINFO_DATA_REF (def_stmt_info)));
3003 : }
3004 :
3005 : /* Return true if STMT_INFO truncates the input of a store. */
3006 : inline bool
3007 : vect_is_truncating_store (class vec_info *vinfo, stmt_vec_info stmt_info)
3008 : {
3009 : /* Although this is quite large for an inline function, this part
3010 : at least should be inline. */
3011 : gassign *assign = dyn_cast<gassign *> (stmt_info->stmt);
3012 : if (!assign || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (assign)))
3013 : return false;
3014 :
3015 : tree rhs = gimple_assign_rhs1 (stmt_info->stmt);
3016 : tree lhs = gimple_assign_lhs (assign);
3017 : tree lhs_type = TREE_TYPE (lhs);
3018 : tree rhs_type = TREE_TYPE (rhs);
3019 : if (!INTEGRAL_TYPE_P (lhs_type) || !INTEGRAL_TYPE_P (rhs_type)
3020 : || TYPE_PRECISION (lhs_type) >= TYPE_PRECISION (rhs_type))
3021 : return false;
3022 :
3023 : gimple *use_stmt;
3024 : use_operand_p use_p;
3025 : if (!single_imm_use (lhs, &use_p, &use_stmt))
3026 : return false;
3027 :
3028 : stmt_vec_info use_stmt_info = vinfo->lookup_stmt (use_stmt);
3029 : return (use_stmt_info && STMT_VINFO_DATA_REF (use_stmt_info)
3030 : && DR_IS_WRITE (STMT_VINFO_DATA_REF (use_stmt_info)));
3031 : }
3032 :
3033 : /* Return true if STMT_INFO is an integer truncation. */
3034 : inline bool
3035 : vect_is_integer_truncation (stmt_vec_info stmt_info)
3036 : {
3037 : gassign *assign = dyn_cast <gassign *> (stmt_info->stmt);
3038 : if (!assign || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (assign)))
3039 : return false;
3040 :
3041 : tree lhs_type = TREE_TYPE (gimple_assign_lhs (assign));
3042 : tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (assign));
3043 : return (INTEGRAL_TYPE_P (lhs_type)
3044 : && INTEGRAL_TYPE_P (rhs_type)
3045 : && TYPE_PRECISION (lhs_type) < TYPE_PRECISION (rhs_type));
3046 : }
3047 :
3048 : /* Build a GIMPLE_ASSIGN or GIMPLE_CALL with the tree_code,
3049 : or internal_fn contained in ch, respectively. */
3050 : gimple * vect_gimple_build (tree, code_helper, tree, tree = NULL_TREE);
3051 : #endif /* GCC_TREE_VECTORIZER_H */
|