tree-vectorizer.h source code [gcc/tree-vectorizer.h]

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

source code of gcc/tree-vectorizer.h