|
0
|
1 /* Loop Vectorization
|
|
|
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 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 source_location LOC;
|
|
|
25 #define UNKNOWN_LOC UNKNOWN_LOCATION
|
|
|
26 #define EXPR_LOC(e) EXPR_LOCATION(e)
|
|
|
27 #define LOC_FILE(l) LOCATION_FILE (l)
|
|
|
28 #define LOC_LINE(l) LOCATION_LINE (l)
|
|
|
29
|
|
|
30 /* Used for naming of new temporaries. */
|
|
|
31 enum vect_var_kind {
|
|
|
32 vect_simple_var,
|
|
|
33 vect_pointer_var,
|
|
|
34 vect_scalar_var
|
|
|
35 };
|
|
|
36
|
|
|
37 /* Defines type of operation. */
|
|
|
38 enum operation_type {
|
|
|
39 unary_op = 1,
|
|
|
40 binary_op,
|
|
|
41 ternary_op
|
|
|
42 };
|
|
|
43
|
|
|
44 /* Define type of available alignment support. */
|
|
|
45 enum dr_alignment_support {
|
|
|
46 dr_unaligned_unsupported,
|
|
|
47 dr_unaligned_supported,
|
|
|
48 dr_explicit_realign,
|
|
|
49 dr_explicit_realign_optimized,
|
|
|
50 dr_aligned
|
|
|
51 };
|
|
|
52
|
|
|
53 /* Define type of def-use cross-iteration cycle. */
|
|
|
54 enum vect_def_type {
|
|
|
55 vect_constant_def = 1,
|
|
|
56 vect_invariant_def,
|
|
|
57 vect_loop_def,
|
|
|
58 vect_induction_def,
|
|
|
59 vect_reduction_def,
|
|
|
60 vect_unknown_def_type
|
|
|
61 };
|
|
|
62
|
|
|
63 /* Define verbosity levels. */
|
|
|
64 enum verbosity_levels {
|
|
|
65 REPORT_NONE,
|
|
|
66 REPORT_VECTORIZED_LOOPS,
|
|
|
67 REPORT_UNVECTORIZED_LOOPS,
|
|
|
68 REPORT_COST,
|
|
|
69 REPORT_ALIGNMENT,
|
|
|
70 REPORT_DR_DETAILS,
|
|
|
71 REPORT_BAD_FORM_LOOPS,
|
|
|
72 REPORT_OUTER_LOOPS,
|
|
|
73 REPORT_SLP,
|
|
|
74 REPORT_DETAILS,
|
|
|
75 /* New verbosity levels should be added before this one. */
|
|
|
76 MAX_VERBOSITY_LEVEL
|
|
|
77 };
|
|
|
78
|
|
|
79 /************************************************************************
|
|
|
80 SLP
|
|
|
81 ************************************************************************/
|
|
|
82
|
|
|
83 /* A computation tree of an SLP instance. Each node corresponds to a group of
|
|
|
84 stmts to be packed in a SIMD stmt. */
|
|
|
85 typedef struct _slp_tree {
|
|
|
86 /* Only binary and unary operations are supported. LEFT child corresponds to
|
|
|
87 the first operand and RIGHT child to the second if the operation is
|
|
|
88 binary. */
|
|
|
89 struct _slp_tree *left;
|
|
|
90 struct _slp_tree *right;
|
|
|
91 /* A group of scalar stmts to be vectorized together. */
|
|
|
92 VEC (gimple, heap) *stmts;
|
|
|
93 /* Vectorized stmt/s. */
|
|
|
94 VEC (gimple, heap) *vec_stmts;
|
|
|
95 /* Number of vector stmts that are created to replace the group of scalar
|
|
|
96 stmts. It is calculated during the transformation phase as the number of
|
|
|
97 scalar elements in one scalar iteration (GROUP_SIZE) multiplied by VF
|
|
|
98 divided by vector size. */
|
|
|
99 unsigned int vec_stmts_size;
|
|
|
100 /* Vectorization costs associated with SLP node. */
|
|
|
101 struct
|
|
|
102 {
|
|
|
103 int outside_of_loop; /* Statements generated outside loop. */
|
|
|
104 int inside_of_loop; /* Statements generated inside loop. */
|
|
|
105 } cost;
|
|
|
106 } *slp_tree;
|
|
|
107
|
|
|
108 DEF_VEC_P(slp_tree);
|
|
|
109 DEF_VEC_ALLOC_P(slp_tree, heap);
|
|
|
110
|
|
|
111 /* SLP instance is a sequence of stmts in a loop that can be packed into
|
|
|
112 SIMD stmts. */
|
|
|
113 typedef struct _slp_instance {
|
|
|
114 /* The root of SLP tree. */
|
|
|
115 slp_tree root;
|
|
|
116
|
|
|
117 /* Size of groups of scalar stmts that will be replaced by SIMD stmt/s. */
|
|
|
118 unsigned int group_size;
|
|
|
119
|
|
|
120 /* The unrolling factor required to vectorized this SLP instance. */
|
|
|
121 unsigned int unrolling_factor;
|
|
|
122
|
|
|
123 /* Vectorization costs associated with SLP instance. */
|
|
|
124 struct
|
|
|
125 {
|
|
|
126 int outside_of_loop; /* Statements generated outside loop. */
|
|
|
127 int inside_of_loop; /* Statements generated inside loop. */
|
|
|
128 } cost;
|
|
|
129
|
|
|
130 /* Loads permutation relatively to the stores, NULL if there is no
|
|
|
131 permutation. */
|
|
|
132 VEC (int, heap) *load_permutation;
|
|
|
133
|
|
|
134 /* The group of nodes that contain loads of this SLP instance. */
|
|
|
135 VEC (slp_tree, heap) *loads;
|
|
|
136
|
|
|
137 /* The first scalar load of the instance. The created vector loads will be
|
|
|
138 inserted before this statement. */
|
|
|
139 gimple first_load;
|
|
|
140 } *slp_instance;
|
|
|
141
|
|
|
142 DEF_VEC_P(slp_instance);
|
|
|
143 DEF_VEC_ALLOC_P(slp_instance, heap);
|
|
|
144
|
|
|
145 /* Access Functions. */
|
|
|
146 #define SLP_INSTANCE_TREE(S) (S)->root
|
|
|
147 #define SLP_INSTANCE_GROUP_SIZE(S) (S)->group_size
|
|
|
148 #define SLP_INSTANCE_UNROLLING_FACTOR(S) (S)->unrolling_factor
|
|
|
149 #define SLP_INSTANCE_OUTSIDE_OF_LOOP_COST(S) (S)->cost.outside_of_loop
|
|
|
150 #define SLP_INSTANCE_INSIDE_OF_LOOP_COST(S) (S)->cost.inside_of_loop
|
|
|
151 #define SLP_INSTANCE_LOAD_PERMUTATION(S) (S)->load_permutation
|
|
|
152 #define SLP_INSTANCE_LOADS(S) (S)->loads
|
|
|
153 #define SLP_INSTANCE_FIRST_LOAD_STMT(S) (S)->first_load
|
|
|
154
|
|
|
155 #define SLP_TREE_LEFT(S) (S)->left
|
|
|
156 #define SLP_TREE_RIGHT(S) (S)->right
|
|
|
157 #define SLP_TREE_SCALAR_STMTS(S) (S)->stmts
|
|
|
158 #define SLP_TREE_VEC_STMTS(S) (S)->vec_stmts
|
|
|
159 #define SLP_TREE_NUMBER_OF_VEC_STMTS(S) (S)->vec_stmts_size
|
|
|
160 #define SLP_TREE_OUTSIDE_OF_LOOP_COST(S) (S)->cost.outside_of_loop
|
|
|
161 #define SLP_TREE_INSIDE_OF_LOOP_COST(S) (S)->cost.inside_of_loop
|
|
|
162
|
|
|
163 /*-----------------------------------------------------------------*/
|
|
|
164 /* Info on vectorized loops. */
|
|
|
165 /*-----------------------------------------------------------------*/
|
|
|
166 typedef struct _loop_vec_info {
|
|
|
167
|
|
|
168 /* The loop to which this info struct refers to. */
|
|
|
169 struct loop *loop;
|
|
|
170
|
|
|
171 /* The loop basic blocks. */
|
|
|
172 basic_block *bbs;
|
|
|
173
|
|
|
174 /* Number of iterations. */
|
|
|
175 tree num_iters;
|
|
|
176 tree num_iters_unchanged;
|
|
|
177
|
|
|
178 /* Minimum number of iterations below which vectorization is expected to
|
|
|
179 not be profitable (as estimated by the cost model).
|
|
|
180 -1 indicates that vectorization will not be profitable.
|
|
|
181 FORNOW: This field is an int. Will be a tree in the future, to represent
|
|
|
182 values unknown at compile time. */
|
|
|
183 int min_profitable_iters;
|
|
|
184
|
|
|
185 /* Is the loop vectorizable? */
|
|
|
186 bool vectorizable;
|
|
|
187
|
|
|
188 /* Unrolling factor */
|
|
|
189 int vectorization_factor;
|
|
|
190
|
|
|
191 /* Unknown DRs according to which loop was peeled. */
|
|
|
192 struct data_reference *unaligned_dr;
|
|
|
193
|
|
|
194 /* peeling_for_alignment indicates whether peeling for alignment will take
|
|
|
195 place, and what the peeling factor should be:
|
|
|
196 peeling_for_alignment = X means:
|
|
|
197 If X=0: Peeling for alignment will not be applied.
|
|
|
198 If X>0: Peel first X iterations.
|
|
|
199 If X=-1: Generate a runtime test to calculate the number of iterations
|
|
|
200 to be peeled, using the dataref recorded in the field
|
|
|
201 unaligned_dr. */
|
|
|
202 int peeling_for_alignment;
|
|
|
203
|
|
|
204 /* The mask used to check the alignment of pointers or arrays. */
|
|
|
205 int ptr_mask;
|
|
|
206
|
|
|
207 /* All data references in the loop. */
|
|
|
208 VEC (data_reference_p, heap) *datarefs;
|
|
|
209
|
|
|
210 /* All data dependences in the loop. */
|
|
|
211 VEC (ddr_p, heap) *ddrs;
|
|
|
212
|
|
|
213 /* Data Dependence Relations defining address ranges that are candidates
|
|
|
214 for a run-time aliasing check. */
|
|
|
215 VEC (ddr_p, heap) *may_alias_ddrs;
|
|
|
216
|
|
|
217 /* Statements in the loop that have data references that are candidates for a
|
|
|
218 runtime (loop versioning) misalignment check. */
|
|
|
219 VEC(gimple,heap) *may_misalign_stmts;
|
|
|
220
|
|
|
221 /* The loop location in the source. */
|
|
|
222 LOC loop_line_number;
|
|
|
223
|
|
|
224 /* All interleaving chains of stores in the loop, represented by the first
|
|
|
225 stmt in the chain. */
|
|
|
226 VEC(gimple, heap) *strided_stores;
|
|
|
227
|
|
|
228 /* All SLP instances in the loop. This is a subset of the set of STRIDED_STORES
|
|
|
229 of the loop. */
|
|
|
230 VEC(slp_instance, heap) *slp_instances;
|
|
|
231
|
|
|
232 /* The unrolling factor needed to SLP the loop. In case of that pure SLP is
|
|
|
233 applied to the loop, i.e., no unrolling is needed, this is 1. */
|
|
|
234 unsigned slp_unrolling_factor;
|
|
|
235 } *loop_vec_info;
|
|
|
236
|
|
|
237 /* Access Functions. */
|
|
|
238 #define LOOP_VINFO_LOOP(L) (L)->loop
|
|
|
239 #define LOOP_VINFO_BBS(L) (L)->bbs
|
|
|
240 #define LOOP_VINFO_NITERS(L) (L)->num_iters
|
|
|
241 /* Since LOOP_VINFO_NITERS can change after prologue peeling
|
|
|
242 retain total unchanged scalar loop iterations for cost model. */
|
|
|
243 #define LOOP_VINFO_NITERS_UNCHANGED(L) (L)->num_iters_unchanged
|
|
|
244 #define LOOP_VINFO_COST_MODEL_MIN_ITERS(L) (L)->min_profitable_iters
|
|
|
245 #define LOOP_VINFO_VECTORIZABLE_P(L) (L)->vectorizable
|
|
|
246 #define LOOP_VINFO_VECT_FACTOR(L) (L)->vectorization_factor
|
|
|
247 #define LOOP_VINFO_PTR_MASK(L) (L)->ptr_mask
|
|
|
248 #define LOOP_VINFO_DATAREFS(L) (L)->datarefs
|
|
|
249 #define LOOP_VINFO_DDRS(L) (L)->ddrs
|
|
|
250 #define LOOP_VINFO_INT_NITERS(L) (TREE_INT_CST_LOW ((L)->num_iters))
|
|
|
251 #define LOOP_PEELING_FOR_ALIGNMENT(L) (L)->peeling_for_alignment
|
|
|
252 #define LOOP_VINFO_UNALIGNED_DR(L) (L)->unaligned_dr
|
|
|
253 #define LOOP_VINFO_MAY_MISALIGN_STMTS(L) (L)->may_misalign_stmts
|
|
|
254 #define LOOP_VINFO_LOC(L) (L)->loop_line_number
|
|
|
255 #define LOOP_VINFO_MAY_ALIAS_DDRS(L) (L)->may_alias_ddrs
|
|
|
256 #define LOOP_VINFO_STRIDED_STORES(L) (L)->strided_stores
|
|
|
257 #define LOOP_VINFO_SLP_INSTANCES(L) (L)->slp_instances
|
|
|
258 #define LOOP_VINFO_SLP_UNROLLING_FACTOR(L) (L)->slp_unrolling_factor
|
|
|
259
|
|
|
260 #define NITERS_KNOWN_P(n) \
|
|
|
261 (host_integerp ((n),0) \
|
|
|
262 && TREE_INT_CST_LOW ((n)) > 0)
|
|
|
263
|
|
|
264 #define LOOP_VINFO_NITERS_KNOWN_P(L) \
|
|
|
265 NITERS_KNOWN_P((L)->num_iters)
|
|
|
266
|
|
|
267 static inline loop_vec_info
|
|
|
268 loop_vec_info_for_loop (struct loop *loop)
|
|
|
269 {
|
|
|
270 return (loop_vec_info) loop->aux;
|
|
|
271 }
|
|
|
272
|
|
|
273 static inline bool
|
|
|
274 nested_in_vect_loop_p (struct loop *loop, gimple stmt)
|
|
|
275 {
|
|
|
276 return (loop->inner
|
|
|
277 && (loop->inner == (gimple_bb (stmt))->loop_father));
|
|
|
278 }
|
|
|
279
|
|
|
280 /*-----------------------------------------------------------------*/
|
|
|
281 /* Info on vectorized defs. */
|
|
|
282 /*-----------------------------------------------------------------*/
|
|
|
283 enum stmt_vec_info_type {
|
|
|
284 undef_vec_info_type = 0,
|
|
|
285 load_vec_info_type,
|
|
|
286 store_vec_info_type,
|
|
|
287 op_vec_info_type,
|
|
|
288 call_vec_info_type,
|
|
|
289 assignment_vec_info_type,
|
|
|
290 condition_vec_info_type,
|
|
|
291 reduc_vec_info_type,
|
|
|
292 induc_vec_info_type,
|
|
|
293 type_promotion_vec_info_type,
|
|
|
294 type_demotion_vec_info_type,
|
|
|
295 type_conversion_vec_info_type,
|
|
|
296 loop_exit_ctrl_vec_info_type
|
|
|
297 };
|
|
|
298
|
|
|
299 /* Indicates whether/how a variable is used in the loop. */
|
|
|
300 enum vect_relevant {
|
|
|
301 vect_unused_in_loop = 0,
|
|
|
302 vect_used_in_outer_by_reduction,
|
|
|
303 vect_used_in_outer,
|
|
|
304
|
|
|
305 /* defs that feed computations that end up (only) in a reduction. These
|
|
|
306 defs may be used by non-reduction stmts, but eventually, any
|
|
|
307 computations/values that are affected by these defs are used to compute
|
|
|
308 a reduction (i.e. don't get stored to memory, for example). We use this
|
|
|
309 to identify computations that we can change the order in which they are
|
|
|
310 computed. */
|
|
|
311 vect_used_by_reduction,
|
|
|
312
|
|
|
313 vect_used_in_loop
|
|
|
314 };
|
|
|
315
|
|
|
316 /* The type of vectorization that can be applied to the stmt: regular loop-based
|
|
|
317 vectorization; pure SLP - the stmt is a part of SLP instances and does not
|
|
|
318 have uses outside SLP instances; or hybrid SLP and loop-based - the stmt is
|
|
|
319 a part of SLP instance and also must be loop-based vectorized, since it has
|
|
|
320 uses outside SLP sequences.
|
|
|
321
|
|
|
322 In the loop context the meanings of pure and hybrid SLP are slightly
|
|
|
323 different. By saying that pure SLP is applied to the loop, we mean that we
|
|
|
324 exploit only intra-iteration parallelism in the loop; i.e., the loop can be
|
|
|
325 vectorized without doing any conceptual unrolling, cause we don't pack
|
|
|
326 together stmts from different iterations, only within a single iteration.
|
|
|
327 Loop hybrid SLP means that we exploit both intra-iteration and
|
|
|
328 inter-iteration parallelism (e.g., number of elements in the vector is 4
|
|
|
329 and the slp-group-size is 2, in which case we don't have enough parallelism
|
|
|
330 within an iteration, so we obtain the rest of the parallelism from subsequent
|
|
|
331 iterations by unrolling the loop by 2). */
|
|
|
332 enum slp_vect_type {
|
|
|
333 loop_vect = 0,
|
|
|
334 pure_slp,
|
|
|
335 hybrid
|
|
|
336 };
|
|
|
337
|
|
|
338
|
|
|
339 typedef struct data_reference *dr_p;
|
|
|
340 DEF_VEC_P(dr_p);
|
|
|
341 DEF_VEC_ALLOC_P(dr_p,heap);
|
|
|
342
|
|
|
343 typedef struct _stmt_vec_info {
|
|
|
344
|
|
|
345 enum stmt_vec_info_type type;
|
|
|
346
|
|
|
347 /* The stmt to which this info struct refers to. */
|
|
|
348 gimple stmt;
|
|
|
349
|
|
|
350 /* The loop_vec_info with respect to which STMT is vectorized. */
|
|
|
351 loop_vec_info loop_vinfo;
|
|
|
352
|
|
|
353 /* Not all stmts in the loop need to be vectorized. e.g, the increment
|
|
|
354 of the loop induction variable and computation of array indexes. relevant
|
|
|
355 indicates whether the stmt needs to be vectorized. */
|
|
|
356 enum vect_relevant relevant;
|
|
|
357
|
|
|
358 /* Indicates whether this stmts is part of a computation whose result is
|
|
|
359 used outside the loop. */
|
|
|
360 bool live;
|
|
|
361
|
|
|
362 /* The vector type to be used. */
|
|
|
363 tree vectype;
|
|
|
364
|
|
|
365 /* The vectorized version of the stmt. */
|
|
|
366 gimple vectorized_stmt;
|
|
|
367
|
|
|
368
|
|
|
369 /** The following is relevant only for stmts that contain a non-scalar
|
|
|
370 data-ref (array/pointer/struct access). A GIMPLE stmt is expected to have
|
|
|
371 at most one such data-ref. **/
|
|
|
372
|
|
|
373 /* Information about the data-ref (access function, etc),
|
|
|
374 relative to the inner-most containing loop. */
|
|
|
375 struct data_reference *data_ref_info;
|
|
|
376
|
|
|
377 /* Information about the data-ref relative to this loop
|
|
|
378 nest (the loop that is being considered for vectorization). */
|
|
|
379 tree dr_base_address;
|
|
|
380 tree dr_init;
|
|
|
381 tree dr_offset;
|
|
|
382 tree dr_step;
|
|
|
383 tree dr_aligned_to;
|
|
|
384
|
|
|
385 /* Stmt is part of some pattern (computation idiom) */
|
|
|
386 bool in_pattern_p;
|
|
|
387
|
|
|
388 /* Used for various bookkeeping purposes, generally holding a pointer to
|
|
|
389 some other stmt S that is in some way "related" to this stmt.
|
|
|
390 Current use of this field is:
|
|
|
391 If this stmt is part of a pattern (i.e. the field 'in_pattern_p' is
|
|
|
392 true): S is the "pattern stmt" that represents (and replaces) the
|
|
|
393 sequence of stmts that constitutes the pattern. Similarly, the
|
|
|
394 related_stmt of the "pattern stmt" points back to this stmt (which is
|
|
|
395 the last stmt in the original sequence of stmts that constitutes the
|
|
|
396 pattern). */
|
|
|
397 gimple related_stmt;
|
|
|
398
|
|
|
399 /* List of datarefs that are known to have the same alignment as the dataref
|
|
|
400 of this stmt. */
|
|
|
401 VEC(dr_p,heap) *same_align_refs;
|
|
|
402
|
|
|
403 /* Classify the def of this stmt. */
|
|
|
404 enum vect_def_type def_type;
|
|
|
405
|
|
|
406 /* Interleaving info. */
|
|
|
407 /* First data-ref in the interleaving group. */
|
|
|
408 gimple first_dr;
|
|
|
409 /* Pointer to the next data-ref in the group. */
|
|
|
410 gimple next_dr;
|
|
|
411 /* The size of the interleaving group. */
|
|
|
412 unsigned int size;
|
|
|
413 /* For stores, number of stores from this group seen. We vectorize the last
|
|
|
414 one. */
|
|
|
415 unsigned int store_count;
|
|
|
416 /* For loads only, the gap from the previous load. For consecutive loads, GAP
|
|
|
417 is 1. */
|
|
|
418 unsigned int gap;
|
|
|
419 /* In case that two or more stmts share data-ref, this is the pointer to the
|
|
|
420 previously detected stmt with the same dr. */
|
|
|
421 gimple same_dr_stmt;
|
|
|
422 /* For loads only, if there is a store with the same location, this field is
|
|
|
423 TRUE. */
|
|
|
424 bool read_write_dep;
|
|
|
425
|
|
|
426 /* Vectorization costs associated with statement. */
|
|
|
427 struct
|
|
|
428 {
|
|
|
429 int outside_of_loop; /* Statements generated outside loop. */
|
|
|
430 int inside_of_loop; /* Statements generated inside loop. */
|
|
|
431 } cost;
|
|
|
432
|
|
|
433 /* Whether the stmt is SLPed, loop-based vectorized, or both. */
|
|
|
434 enum slp_vect_type slp_type;
|
|
|
435 } *stmt_vec_info;
|
|
|
436
|
|
|
437 /* Access Functions. */
|
|
|
438 #define STMT_VINFO_TYPE(S) (S)->type
|
|
|
439 #define STMT_VINFO_STMT(S) (S)->stmt
|
|
|
440 #define STMT_VINFO_LOOP_VINFO(S) (S)->loop_vinfo
|
|
|
441 #define STMT_VINFO_RELEVANT(S) (S)->relevant
|
|
|
442 #define STMT_VINFO_LIVE_P(S) (S)->live
|
|
|
443 #define STMT_VINFO_VECTYPE(S) (S)->vectype
|
|
|
444 #define STMT_VINFO_VEC_STMT(S) (S)->vectorized_stmt
|
|
|
445 #define STMT_VINFO_DATA_REF(S) (S)->data_ref_info
|
|
|
446
|
|
|
447 #define STMT_VINFO_DR_BASE_ADDRESS(S) (S)->dr_base_address
|
|
|
448 #define STMT_VINFO_DR_INIT(S) (S)->dr_init
|
|
|
449 #define STMT_VINFO_DR_OFFSET(S) (S)->dr_offset
|
|
|
450 #define STMT_VINFO_DR_STEP(S) (S)->dr_step
|
|
|
451 #define STMT_VINFO_DR_ALIGNED_TO(S) (S)->dr_aligned_to
|
|
|
452
|
|
|
453 #define STMT_VINFO_IN_PATTERN_P(S) (S)->in_pattern_p
|
|
|
454 #define STMT_VINFO_RELATED_STMT(S) (S)->related_stmt
|
|
|
455 #define STMT_VINFO_SAME_ALIGN_REFS(S) (S)->same_align_refs
|
|
|
456 #define STMT_VINFO_DEF_TYPE(S) (S)->def_type
|
|
|
457 #define STMT_VINFO_DR_GROUP_FIRST_DR(S) (S)->first_dr
|
|
|
458 #define STMT_VINFO_DR_GROUP_NEXT_DR(S) (S)->next_dr
|
|
|
459 #define STMT_VINFO_DR_GROUP_SIZE(S) (S)->size
|
|
|
460 #define STMT_VINFO_DR_GROUP_STORE_COUNT(S) (S)->store_count
|
|
|
461 #define STMT_VINFO_DR_GROUP_GAP(S) (S)->gap
|
|
|
462 #define STMT_VINFO_DR_GROUP_SAME_DR_STMT(S)(S)->same_dr_stmt
|
|
|
463 #define STMT_VINFO_DR_GROUP_READ_WRITE_DEPENDENCE(S) (S)->read_write_dep
|
|
|
464 #define STMT_VINFO_STRIDED_ACCESS(S) ((S)->first_dr != NULL)
|
|
|
465
|
|
|
466 #define DR_GROUP_FIRST_DR(S) (S)->first_dr
|
|
|
467 #define DR_GROUP_NEXT_DR(S) (S)->next_dr
|
|
|
468 #define DR_GROUP_SIZE(S) (S)->size
|
|
|
469 #define DR_GROUP_STORE_COUNT(S) (S)->store_count
|
|
|
470 #define DR_GROUP_GAP(S) (S)->gap
|
|
|
471 #define DR_GROUP_SAME_DR_STMT(S) (S)->same_dr_stmt
|
|
|
472 #define DR_GROUP_READ_WRITE_DEPENDENCE(S) (S)->read_write_dep
|
|
|
473
|
|
|
474 #define STMT_VINFO_RELEVANT_P(S) ((S)->relevant != vect_unused_in_loop)
|
|
|
475 #define STMT_VINFO_OUTSIDE_OF_LOOP_COST(S) (S)->cost.outside_of_loop
|
|
|
476 #define STMT_VINFO_INSIDE_OF_LOOP_COST(S) (S)->cost.inside_of_loop
|
|
|
477
|
|
|
478 #define HYBRID_SLP_STMT(S) ((S)->slp_type == hybrid)
|
|
|
479 #define PURE_SLP_STMT(S) ((S)->slp_type == pure_slp)
|
|
|
480 #define STMT_SLP_TYPE(S) (S)->slp_type
|
|
|
481
|
|
|
482 /* These are some defines for the initial implementation of the vectorizer's
|
|
|
483 cost model. These will later be target specific hooks. */
|
|
|
484
|
|
|
485 /* Cost of conditional taken branch. */
|
|
|
486 #ifndef TARG_COND_TAKEN_BRANCH_COST
|
|
|
487 #define TARG_COND_TAKEN_BRANCH_COST 3
|
|
|
488 #endif
|
|
|
489
|
|
|
490 /* Cost of conditional not taken branch. */
|
|
|
491 #ifndef TARG_COND_NOT_TAKEN_BRANCH_COST
|
|
|
492 #define TARG_COND_NOT_TAKEN_BRANCH_COST 1
|
|
|
493 #endif
|
|
|
494
|
|
|
495 /* Cost of any scalar operation, excluding load and store. */
|
|
|
496 #ifndef TARG_SCALAR_STMT_COST
|
|
|
497 #define TARG_SCALAR_STMT_COST 1
|
|
|
498 #endif
|
|
|
499
|
|
|
500 /* Cost of scalar load. */
|
|
|
501 #ifndef TARG_SCALAR_LOAD_COST
|
|
|
502 #define TARG_SCALAR_LOAD_COST 1
|
|
|
503 #endif
|
|
|
504
|
|
|
505 /* Cost of scalar store. */
|
|
|
506 #ifndef TARG_SCALAR_STORE_COST
|
|
|
507 #define TARG_SCALAR_STORE_COST 1
|
|
|
508 #endif
|
|
|
509
|
|
|
510 /* Cost of any vector operation, excluding load, store or vector to scalar
|
|
|
511 operation. */
|
|
|
512 #ifndef TARG_VEC_STMT_COST
|
|
|
513 #define TARG_VEC_STMT_COST 1
|
|
|
514 #endif
|
|
|
515
|
|
|
516 /* Cost of vector to scalar operation. */
|
|
|
517 #ifndef TARG_VEC_TO_SCALAR_COST
|
|
|
518 #define TARG_VEC_TO_SCALAR_COST 1
|
|
|
519 #endif
|
|
|
520
|
|
|
521 /* Cost of scalar to vector operation. */
|
|
|
522 #ifndef TARG_SCALAR_TO_VEC_COST
|
|
|
523 #define TARG_SCALAR_TO_VEC_COST 1
|
|
|
524 #endif
|
|
|
525
|
|
|
526 /* Cost of aligned vector load. */
|
|
|
527 #ifndef TARG_VEC_LOAD_COST
|
|
|
528 #define TARG_VEC_LOAD_COST 1
|
|
|
529 #endif
|
|
|
530
|
|
|
531 /* Cost of misaligned vector load. */
|
|
|
532 #ifndef TARG_VEC_UNALIGNED_LOAD_COST
|
|
|
533 #define TARG_VEC_UNALIGNED_LOAD_COST 2
|
|
|
534 #endif
|
|
|
535
|
|
|
536 /* Cost of vector store. */
|
|
|
537 #ifndef TARG_VEC_STORE_COST
|
|
|
538 #define TARG_VEC_STORE_COST 1
|
|
|
539 #endif
|
|
|
540
|
|
|
541 /* Cost of vector permutation. */
|
|
|
542 #ifndef TARG_VEC_PERMUTE_COST
|
|
|
543 #define TARG_VEC_PERMUTE_COST 1
|
|
|
544 #endif
|
|
|
545
|
|
|
546 /* The maximum number of intermediate steps required in multi-step type
|
|
|
547 conversion. */
|
|
|
548 #define MAX_INTERM_CVT_STEPS 3
|
|
|
549
|
|
|
550 /* Avoid GTY(()) on stmt_vec_info. */
|
|
|
551 typedef void *vec_void_p;
|
|
|
552 DEF_VEC_P (vec_void_p);
|
|
|
553 DEF_VEC_ALLOC_P (vec_void_p, heap);
|
|
|
554
|
|
|
555 extern VEC(vec_void_p,heap) *stmt_vec_info_vec;
|
|
|
556
|
|
|
557 void init_stmt_vec_info_vec (void);
|
|
|
558 void free_stmt_vec_info_vec (void);
|
|
|
559
|
|
|
560 static inline stmt_vec_info
|
|
|
561 vinfo_for_stmt (gimple stmt)
|
|
|
562 {
|
|
|
563 unsigned int uid = gimple_uid (stmt);
|
|
|
564 if (uid == 0)
|
|
|
565 return NULL;
|
|
|
566
|
|
|
567 gcc_assert (uid <= VEC_length (vec_void_p, stmt_vec_info_vec));
|
|
|
568 return (stmt_vec_info) VEC_index (vec_void_p, stmt_vec_info_vec, uid - 1);
|
|
|
569 }
|
|
|
570
|
|
|
571 static inline void
|
|
|
572 set_vinfo_for_stmt (gimple stmt, stmt_vec_info info)
|
|
|
573 {
|
|
|
574 unsigned int uid = gimple_uid (stmt);
|
|
|
575 if (uid == 0)
|
|
|
576 {
|
|
|
577 gcc_assert (info);
|
|
|
578 uid = VEC_length (vec_void_p, stmt_vec_info_vec) + 1;
|
|
|
579 gimple_set_uid (stmt, uid);
|
|
|
580 VEC_safe_push (vec_void_p, heap, stmt_vec_info_vec, (vec_void_p) info);
|
|
|
581 }
|
|
|
582 else
|
|
|
583 VEC_replace (vec_void_p, stmt_vec_info_vec, uid - 1, (vec_void_p) info);
|
|
|
584 }
|
|
|
585
|
|
|
586 static inline gimple
|
|
|
587 get_earlier_stmt (gimple stmt1, gimple stmt2)
|
|
|
588 {
|
|
|
589 unsigned int uid1, uid2;
|
|
|
590
|
|
|
591 if (stmt1 == NULL)
|
|
|
592 return stmt2;
|
|
|
593
|
|
|
594 if (stmt2 == NULL)
|
|
|
595 return stmt1;
|
|
|
596
|
|
|
597 uid1 = gimple_uid (stmt1);
|
|
|
598 uid2 = gimple_uid (stmt2);
|
|
|
599
|
|
|
600 if (uid1 == 0 || uid2 == 0)
|
|
|
601 return NULL;
|
|
|
602
|
|
|
603 gcc_assert (uid1 <= VEC_length (vec_void_p, stmt_vec_info_vec));
|
|
|
604 gcc_assert (uid2 <= VEC_length (vec_void_p, stmt_vec_info_vec));
|
|
|
605
|
|
|
606 if (uid1 < uid2)
|
|
|
607 return stmt1;
|
|
|
608 else
|
|
|
609 return stmt2;
|
|
|
610 }
|
|
|
611
|
|
|
612 static inline bool
|
|
|
613 is_pattern_stmt_p (stmt_vec_info stmt_info)
|
|
|
614 {
|
|
|
615 gimple related_stmt;
|
|
|
616 stmt_vec_info related_stmt_info;
|
|
|
617
|
|
|
618 related_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
|
|
|
619 if (related_stmt
|
|
|
620 && (related_stmt_info = vinfo_for_stmt (related_stmt))
|
|
|
621 && STMT_VINFO_IN_PATTERN_P (related_stmt_info))
|
|
|
622 return true;
|
|
|
623
|
|
|
624 return false;
|
|
|
625 }
|
|
|
626
|
|
|
627 static inline bool
|
|
|
628 is_loop_header_bb_p (basic_block bb)
|
|
|
629 {
|
|
|
630 if (bb == (bb->loop_father)->header)
|
|
|
631 return true;
|
|
|
632 gcc_assert (EDGE_COUNT (bb->preds) == 1);
|
|
|
633 return false;
|
|
|
634 }
|
|
|
635
|
|
|
636 static inline void
|
|
|
637 stmt_vinfo_set_inside_of_loop_cost (stmt_vec_info stmt_info, slp_tree slp_node,
|
|
|
638 int cost)
|
|
|
639 {
|
|
|
640 if (slp_node)
|
|
|
641 SLP_TREE_INSIDE_OF_LOOP_COST (slp_node) = cost;
|
|
|
642 else
|
|
|
643 STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info) = cost;
|
|
|
644 }
|
|
|
645
|
|
|
646 static inline void
|
|
|
647 stmt_vinfo_set_outside_of_loop_cost (stmt_vec_info stmt_info, slp_tree slp_node,
|
|
|
648 int cost)
|
|
|
649 {
|
|
|
650 if (slp_node)
|
|
|
651 SLP_TREE_OUTSIDE_OF_LOOP_COST (slp_node) = cost;
|
|
|
652 else
|
|
|
653 STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info) = cost;
|
|
|
654 }
|
|
|
655
|
|
|
656 static inline int
|
|
|
657 vect_pow2 (int x)
|
|
|
658 {
|
|
|
659 int i, res = 1;
|
|
|
660
|
|
|
661 for (i = 0; i < x; i++)
|
|
|
662 res *= 2;
|
|
|
663
|
|
|
664 return res;
|
|
|
665 }
|
|
|
666
|
|
|
667 /*-----------------------------------------------------------------*/
|
|
|
668 /* Info on data references alignment. */
|
|
|
669 /*-----------------------------------------------------------------*/
|
|
|
670
|
|
|
671 /* Reflects actual alignment of first access in the vectorized loop,
|
|
|
672 taking into account peeling/versioning if applied. */
|
|
|
673 #define DR_MISALIGNMENT(DR) ((int) (size_t) (DR)->aux)
|
|
|
674 #define SET_DR_MISALIGNMENT(DR, VAL) ((DR)->aux = (void *) (size_t) (VAL))
|
|
|
675
|
|
|
676 static inline bool
|
|
|
677 aligned_access_p (struct data_reference *data_ref_info)
|
|
|
678 {
|
|
|
679 return (DR_MISALIGNMENT (data_ref_info) == 0);
|
|
|
680 }
|
|
|
681
|
|
|
682 static inline bool
|
|
|
683 known_alignment_for_access_p (struct data_reference *data_ref_info)
|
|
|
684 {
|
|
|
685 return (DR_MISALIGNMENT (data_ref_info) != -1);
|
|
|
686 }
|
|
|
687
|
|
|
688 /* vect_dump will be set to stderr or dump_file if exist. */
|
|
|
689 extern FILE *vect_dump;
|
|
|
690 extern enum verbosity_levels vect_verbosity_level;
|
|
|
691
|
|
|
692 /* Bitmap of virtual variables to be renamed. */
|
|
|
693 extern bitmap vect_memsyms_to_rename;
|
|
|
694
|
|
|
695 /*-----------------------------------------------------------------*/
|
|
|
696 /* Function prototypes. */
|
|
|
697 /*-----------------------------------------------------------------*/
|
|
|
698
|
|
|
699 /*************************************************************************
|
|
|
700 Simple Loop Peeling Utilities - in tree-vectorizer.c
|
|
|
701 *************************************************************************/
|
|
|
702 /* Entry point for peeling of simple loops.
|
|
|
703 Peel the first/last iterations of a loop.
|
|
|
704 It can be used outside of the vectorizer for loops that are simple enough
|
|
|
705 (see function documentation). In the vectorizer it is used to peel the
|
|
|
706 last few iterations when the loop bound is unknown or does not evenly
|
|
|
707 divide by the vectorization factor, and to peel the first few iterations
|
|
|
708 to force the alignment of data references in the loop. */
|
|
|
709 extern struct loop *slpeel_tree_peel_loop_to_edge
|
|
|
710 (struct loop *, edge, tree, tree, bool, unsigned int, bool);
|
|
|
711 extern void set_prologue_iterations (basic_block, tree,
|
|
|
712 struct loop *, unsigned int);
|
|
|
713 struct loop *tree_duplicate_loop_on_edge (struct loop *, edge);
|
|
|
714 extern void slpeel_make_loop_iterate_ntimes (struct loop *, tree);
|
|
|
715 extern bool slpeel_can_duplicate_loop_p (const struct loop *, const_edge);
|
|
|
716 #ifdef ENABLE_CHECKING
|
|
|
717 extern void slpeel_verify_cfg_after_peeling (struct loop *, struct loop *);
|
|
|
718 #endif
|
|
|
719
|
|
|
720
|
|
|
721 /*************************************************************************
|
|
|
722 General Vectorization Utilities
|
|
|
723 *************************************************************************/
|
|
|
724 /** In tree-vectorizer.c **/
|
|
|
725 extern tree get_vectype_for_scalar_type (tree);
|
|
|
726 extern bool vect_is_simple_use (tree, loop_vec_info, gimple *, tree *,
|
|
|
727 enum vect_def_type *);
|
|
|
728 extern bool vect_is_simple_iv_evolution (unsigned, tree, tree *, tree *);
|
|
|
729 extern gimple vect_is_simple_reduction (loop_vec_info, gimple);
|
|
|
730 extern bool vect_can_force_dr_alignment_p (const_tree, unsigned int);
|
|
|
731 extern enum dr_alignment_support vect_supportable_dr_alignment
|
|
|
732 (struct data_reference *);
|
|
|
733 extern bool reduction_code_for_scalar_code (enum tree_code, enum tree_code *);
|
|
|
734 extern bool supportable_widening_operation (enum tree_code, gimple, tree,
|
|
|
735 tree *, tree *, enum tree_code *, enum tree_code *,
|
|
|
736 int *, VEC (tree, heap) **);
|
|
|
737 extern bool supportable_narrowing_operation (enum tree_code, const_gimple,
|
|
|
738 tree, enum tree_code *, int *, VEC (tree, heap) **);
|
|
|
739
|
|
|
740 /* Creation and deletion of loop and stmt info structs. */
|
|
|
741 extern loop_vec_info new_loop_vec_info (struct loop *loop);
|
|
|
742 extern void destroy_loop_vec_info (loop_vec_info, bool);
|
|
|
743 extern stmt_vec_info new_stmt_vec_info (gimple stmt, loop_vec_info);
|
|
|
744 extern void free_stmt_vec_info (gimple stmt);
|
|
|
745
|
|
|
746
|
|
|
747 /** In tree-vect-analyze.c **/
|
|
|
748 /* Driver for analysis stage. */
|
|
|
749 extern loop_vec_info vect_analyze_loop (struct loop *);
|
|
|
750 extern void vect_free_slp_instance (slp_instance);
|
|
|
751 extern loop_vec_info vect_analyze_loop_form (struct loop *);
|
|
|
752 extern tree vect_get_smallest_scalar_type (gimple, HOST_WIDE_INT *,
|
|
|
753 HOST_WIDE_INT *);
|
|
|
754
|
|
|
755 /** In tree-vect-patterns.c **/
|
|
|
756 /* Pattern recognition functions.
|
|
|
757 Additional pattern recognition functions can (and will) be added
|
|
|
758 in the future. */
|
|
|
759 typedef gimple (* vect_recog_func_ptr) (gimple, tree *, tree *);
|
|
|
760 #define NUM_PATTERNS 4
|
|
|
761 void vect_pattern_recog (loop_vec_info);
|
|
|
762
|
|
|
763
|
|
|
764 /** In tree-vect-transform.c **/
|
|
|
765 extern bool vectorizable_load (gimple, gimple_stmt_iterator *, gimple *,
|
|
|
766 slp_tree, slp_instance);
|
|
|
767 extern bool vectorizable_store (gimple, gimple_stmt_iterator *, gimple *,
|
|
|
768 slp_tree);
|
|
|
769 extern bool vectorizable_operation (gimple, gimple_stmt_iterator *, gimple *,
|
|
|
770 slp_tree);
|
|
|
771 extern bool vectorizable_type_promotion (gimple, gimple_stmt_iterator *,
|
|
|
772 gimple *, slp_tree);
|
|
|
773 extern bool vectorizable_type_demotion (gimple, gimple_stmt_iterator *,
|
|
|
774 gimple *, slp_tree);
|
|
|
775 extern bool vectorizable_conversion (gimple, gimple_stmt_iterator *, gimple *,
|
|
|
776 slp_tree);
|
|
|
777 extern bool vectorizable_assignment (gimple, gimple_stmt_iterator *, gimple *,
|
|
|
778 slp_tree);
|
|
|
779 extern tree vectorizable_function (gimple, tree, tree);
|
|
|
780 extern bool vectorizable_call (gimple, gimple_stmt_iterator *, gimple *);
|
|
|
781 extern bool vectorizable_condition (gimple, gimple_stmt_iterator *, gimple *);
|
|
|
782 extern bool vectorizable_live_operation (gimple, gimple_stmt_iterator *,
|
|
|
783 gimple *);
|
|
|
784 extern bool vectorizable_reduction (gimple, gimple_stmt_iterator *, gimple *);
|
|
|
785 extern bool vectorizable_induction (gimple, gimple_stmt_iterator *, gimple *);
|
|
|
786 extern int vect_estimate_min_profitable_iters (loop_vec_info);
|
|
|
787 extern void vect_model_simple_cost (stmt_vec_info, int, enum vect_def_type *,
|
|
|
788 slp_tree);
|
|
|
789 extern void vect_model_store_cost (stmt_vec_info, int, enum vect_def_type,
|
|
|
790 slp_tree);
|
|
|
791 extern void vect_model_load_cost (stmt_vec_info, int, slp_tree);
|
|
|
792 extern bool vect_transform_slp_perm_load (gimple, VEC (tree, heap) *,
|
|
|
793 gimple_stmt_iterator *, int, slp_instance, bool);
|
|
|
794
|
|
|
795 /* Driver for transformation stage. */
|
|
|
796 extern void vect_transform_loop (loop_vec_info);
|
|
|
797
|
|
|
798 /*************************************************************************
|
|
|
799 Vectorization Debug Information - in tree-vectorizer.c
|
|
|
800 *************************************************************************/
|
|
|
801 extern bool vect_print_dump_info (enum verbosity_levels);
|
|
|
802 extern void vect_set_verbosity_level (const char *);
|
|
|
803 extern LOC find_loop_location (struct loop *);
|
|
|
804
|
|
|
805 #endif /* GCC_TREE_VECTORIZER_H */
|
