1/* Loop Vectorization
2   Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3   Contributed by Dorit Naishlos <dorit@il.ibm.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 2, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING.  If not, write to the Free
19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
2002110-1301, USA.  */
21
22#ifndef GCC_TREE_VECTORIZER_H
23#define GCC_TREE_VECTORIZER_H
24
25#ifdef USE_MAPPED_LOCATION
26  typedef source_location LOC;
27  #define UNKNOWN_LOC UNKNOWN_LOCATION
28  #define EXPR_LOC(e) EXPR_LOCATION(e)
29  #define LOC_FILE(l) LOCATION_FILE (l)
30  #define LOC_LINE(l) LOCATION_LINE (l)
31#else
32  typedef source_locus LOC;
33  #define UNKNOWN_LOC NULL
34  #define EXPR_LOC(e) EXPR_LOCUS(e)
35  #define LOC_FILE(l) (l)->file
36  #define LOC_LINE(l) (l)->line
37#endif
38
39/* Used for naming of new temporaries.  */
40enum vect_var_kind {
41  vect_simple_var,
42  vect_pointer_var,
43  vect_scalar_var
44};
45
46/* Defines type of operation: unary or binary.  */
47enum operation_type {
48  unary_op = 1,
49  binary_op
50};
51
52/* Define type of available alignment support.  */
53enum dr_alignment_support {
54  dr_unaligned_unsupported,
55  dr_unaligned_supported,
56  dr_unaligned_software_pipeline,
57  dr_aligned
58};
59
60/* Define type of def-use cross-iteration cycle.  */
61enum vect_def_type {
62  vect_constant_def,
63  vect_invariant_def,
64  vect_loop_def,
65  vect_induction_def,
66  vect_reduction_def,
67  vect_unknown_def_type
68};
69
70/* Define verbosity levels.  */
71enum verbosity_levels {
72  REPORT_NONE,
73  REPORT_VECTORIZED_LOOPS,
74  REPORT_UNVECTORIZED_LOOPS,
75  REPORT_ALIGNMENT,
76  REPORT_DR_DETAILS,
77  REPORT_BAD_FORM_LOOPS,
78  REPORT_OUTER_LOOPS,
79  REPORT_DETAILS,
80  /* New verbosity levels should be added before this one.  */
81  MAX_VERBOSITY_LEVEL
82};
83
84/*-----------------------------------------------------------------*/
85/* Info on vectorized loops.                                       */
86/*-----------------------------------------------------------------*/
87typedef struct _loop_vec_info {
88
89  /* The loop to which this info struct refers to.  */
90  struct loop *loop;
91
92  /* The loop basic blocks.  */
93  basic_block *bbs;
94
95  /* The loop exit_condition.  */
96  tree exit_cond;
97
98  /* Number of iterations.  */
99  tree num_iters;
100
101  /* Is the loop vectorizable? */
102  bool vectorizable;
103
104  /* Unrolling factor  */
105  int vectorization_factor;
106
107  /* Unknown DRs according to which loop was peeled.  */
108  struct data_reference *unaligned_dr;
109
110  /* peeling_for_alignment indicates whether peeling for alignment will take
111     place, and what the peeling factor should be:
112     peeling_for_alignment = X means:
113        If X=0: Peeling for alignment will not be applied.
114        If X>0: Peel first X iterations.
115        If X=-1: Generate a runtime test to calculate the number of iterations
116                 to be peeled, using the dataref recorded in the field
117                 unaligned_dr.  */
118  int peeling_for_alignment;
119
120  /* The mask used to check the alignment of pointers or arrays.  */
121  int ptr_mask;
122
123  /* All data references in the loop.  */
124  varray_type datarefs;
125
126  /* All data dependences in the loop.  */
127  varray_type ddrs;
128
129  /* Statements in the loop that have data references that are candidates for a
130     runtime (loop versioning) misalignment check.  */
131  VEC(tree,heap) *may_misalign_stmts;
132
133  /* The loop location in the source.  */
134  LOC loop_line_number;
135} *loop_vec_info;
136
137/* Access Functions.  */
138#define LOOP_VINFO_LOOP(L)            (L)->loop
139#define LOOP_VINFO_BBS(L)             (L)->bbs
140#define LOOP_VINFO_EXIT_COND(L)       (L)->exit_cond
141#define LOOP_VINFO_NITERS(L)          (L)->num_iters
142#define LOOP_VINFO_VECTORIZABLE_P(L)  (L)->vectorizable
143#define LOOP_VINFO_VECT_FACTOR(L)     (L)->vectorization_factor
144#define LOOP_VINFO_PTR_MASK(L)        (L)->ptr_mask
145#define LOOP_VINFO_DATAREFS(L)        (L)->datarefs
146#define LOOP_VINFO_DDRS(L)            (L)->ddrs
147#define LOOP_VINFO_INT_NITERS(L)      (TREE_INT_CST_LOW ((L)->num_iters))
148#define LOOP_PEELING_FOR_ALIGNMENT(L) (L)->peeling_for_alignment
149#define LOOP_VINFO_UNALIGNED_DR(L)    (L)->unaligned_dr
150#define LOOP_VINFO_MAY_MISALIGN_STMTS(L) (L)->may_misalign_stmts
151#define LOOP_VINFO_LOC(L)             (L)->loop_line_number
152
153#define LOOP_VINFO_NITERS_KNOWN_P(L)                     \
154(host_integerp ((L)->num_iters,0)                        \
155&& TREE_INT_CST_LOW ((L)->num_iters) > 0)
156
157/*-----------------------------------------------------------------*/
158/* Info on vectorized defs.                                        */
159/*-----------------------------------------------------------------*/
160enum stmt_vec_info_type {
161  undef_vec_info_type = 0,
162  load_vec_info_type,
163  store_vec_info_type,
164  op_vec_info_type,
165  assignment_vec_info_type,
166  condition_vec_info_type,
167  reduc_vec_info_type
168};
169
170typedef struct data_reference *dr_p;
171DEF_VEC_P(dr_p);
172DEF_VEC_ALLOC_P(dr_p,heap);
173
174typedef struct _stmt_vec_info {
175
176  enum stmt_vec_info_type type;
177
178  /* The stmt to which this info struct refers to.  */
179  tree stmt;
180
181  /* The loop_vec_info with respect to which STMT is vectorized.  */
182  loop_vec_info loop_vinfo;
183
184  /* Not all stmts in the loop need to be vectorized. e.g, the incrementation
185     of the loop induction variable and computation of array indexes. relevant
186     indicates whether the stmt needs to be vectorized.  */
187  bool relevant;
188
189  /* Indicates whether this stmts is part of a computation whose result is
190     used outside the loop.  */
191  bool live;
192
193  /* The vector type to be used.  */
194  tree vectype;
195
196  /* The vectorized version of the stmt.  */
197  tree vectorized_stmt;
198
199
200  /** The following is relevant only for stmts that contain a non-scalar
201     data-ref (array/pointer/struct access). A GIMPLE stmt is expected to have
202     at most one such data-ref.  **/
203
204  /* Information about the data-ref (access function, etc).  */
205  struct data_reference *data_ref_info;
206
207  /* List of datarefs that are known to have the same alignment as the dataref
208     of this stmt.  */
209  VEC(dr_p,heap) *same_align_refs;
210
211  /* Classify the def of this stmt.  */
212  enum vect_def_type def_type;
213
214} *stmt_vec_info;
215
216/* Access Functions.  */
217#define STMT_VINFO_TYPE(S)                (S)->type
218#define STMT_VINFO_STMT(S)                (S)->stmt
219#define STMT_VINFO_LOOP_VINFO(S)          (S)->loop_vinfo
220#define STMT_VINFO_RELEVANT_P(S)          (S)->relevant
221#define STMT_VINFO_LIVE_P(S)              (S)->live
222#define STMT_VINFO_VECTYPE(S)             (S)->vectype
223#define STMT_VINFO_VEC_STMT(S)            (S)->vectorized_stmt
224#define STMT_VINFO_DATA_REF(S)            (S)->data_ref_info
225#define STMT_VINFO_SAME_ALIGN_REFS(S)     (S)->same_align_refs
226#define STMT_VINFO_DEF_TYPE(S)            (S)->def_type
227
228static inline void set_stmt_info (tree_ann_t ann, stmt_vec_info stmt_info);
229static inline stmt_vec_info vinfo_for_stmt (tree stmt);
230
231static inline void
232set_stmt_info (tree_ann_t ann, stmt_vec_info stmt_info)
233{
234  if (ann)
235    ann->common.aux = (char *) stmt_info;
236}
237
238static inline stmt_vec_info
239vinfo_for_stmt (tree stmt)
240{
241  tree_ann_t ann = tree_ann (stmt);
242  return ann ? (stmt_vec_info) ann->common.aux : NULL;
243}
244
245/*-----------------------------------------------------------------*/
246/* Info on data references alignment.                              */
247/*-----------------------------------------------------------------*/
248
249/* Reflects actual alignment of first access in the vectorized loop,
250   taking into account peeling/versioning if applied.  */
251#define DR_MISALIGNMENT(DR)   (DR)->aux
252
253static inline bool
254aligned_access_p (struct data_reference *data_ref_info)
255{
256  return (DR_MISALIGNMENT (data_ref_info) == 0);
257}
258
259static inline bool
260known_alignment_for_access_p (struct data_reference *data_ref_info)
261{
262  return (DR_MISALIGNMENT (data_ref_info) != -1);
263}
264
265/* Perform signed modulo, always returning a non-negative value.  */
266#define VECT_SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))
267
268/* vect_dump will be set to stderr or dump_file if exist.  */
269extern FILE *vect_dump;
270extern enum verbosity_levels vect_verbosity_level;
271
272/* Number of loops, at the beginning of vectorization.  */
273extern unsigned int vect_loops_num;
274
275/* Bitmap of virtual variables to be renamed.  */
276extern bitmap vect_vnames_to_rename;
277
278/*-----------------------------------------------------------------*/
279/* Function prototypes.                                            */
280/*-----------------------------------------------------------------*/
281
282/*************************************************************************
283  Simple Loop Peeling Utilities - in tree-vectorizer.c
284 *************************************************************************/
285/* Entry point for peeling of simple loops.
286   Peel the first/last iterations of a loop.
287   It can be used outside of the vectorizer for loops that are simple enough
288   (see function documentation).  In the vectorizer it is used to peel the
289   last few iterations when the loop bound is unknown or does not evenly
290   divide by the vectorization factor, and to peel the first few iterations
291   to force the alignment of data references in the loop.  */
292extern struct loop *slpeel_tree_peel_loop_to_edge
293  (struct loop *, struct loops *, edge, tree, tree, bool);
294extern void slpeel_make_loop_iterate_ntimes (struct loop *, tree);
295extern bool slpeel_can_duplicate_loop_p (struct loop *, edge);
296#ifdef ENABLE_CHECKING
297extern void slpeel_verify_cfg_after_peeling (struct loop *, struct loop *);
298#endif
299
300
301/*************************************************************************
302  General Vectorization Utilities
303 *************************************************************************/
304/** In tree-vectorizer.c **/
305extern tree vect_strip_conversion (tree);
306extern tree get_vectype_for_scalar_type (tree);
307extern bool vect_is_simple_use (tree, loop_vec_info, tree *, tree *,
308				enum vect_def_type *);
309extern bool vect_is_simple_iv_evolution (unsigned, tree, tree *, tree *);
310extern tree vect_is_simple_reduction (struct loop *, tree);
311extern bool vect_can_force_dr_alignment_p (tree, unsigned int);
312extern enum dr_alignment_support vect_supportable_dr_alignment
313  (struct data_reference *);
314extern bool reduction_code_for_scalar_code (enum tree_code, enum tree_code *);
315
316/* Creation and deletion of loop and stmt info structs.  */
317extern loop_vec_info new_loop_vec_info (struct loop *loop);
318extern void destroy_loop_vec_info (loop_vec_info);
319extern stmt_vec_info new_stmt_vec_info (tree stmt, loop_vec_info);
320/* Main driver.  */
321extern void vectorize_loops (struct loops *);
322
323/** In tree-vect-analyze.c  **/
324/* Driver for analysis stage.  */
325extern loop_vec_info vect_analyze_loop (struct loop *);
326
327/** In tree-vect-transform.c  **/
328extern bool vectorizable_load (tree, block_stmt_iterator *, tree *);
329extern bool vectorizable_store (tree, block_stmt_iterator *, tree *);
330extern bool vectorizable_operation (tree, block_stmt_iterator *, tree *);
331extern bool vectorizable_assignment (tree, block_stmt_iterator *, tree *);
332extern bool vectorizable_condition (tree, block_stmt_iterator *, tree *);
333extern bool vectorizable_live_operation (tree, block_stmt_iterator *, tree *);
334extern bool vectorizable_reduction (tree, block_stmt_iterator *, tree *);
335/* Driver for transformation stage.  */
336extern void vect_transform_loop (loop_vec_info, struct loops *);
337
338/*************************************************************************
339  Vectorization Debug Information - in tree-vectorizer.c
340 *************************************************************************/
341extern bool vect_print_dump_info (enum verbosity_levels);
342extern void vect_set_verbosity_level (const char *);
343extern LOC find_loop_location (struct loop *);
344
345#endif  /* GCC_TREE_VECTORIZER_H  */
346