gcc/
[official-gcc.git] / gcc / tree-data-ref.h
blob9d8e6992f800319f649e60e8298f043cf3d6066e
1 /* Data references and dependences detectors.
2 Copyright (C) 2003-2015 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #ifndef GCC_TREE_DATA_REF_H
22 #define GCC_TREE_DATA_REF_H
24 #include "graphds.h"
25 #include "omega.h"
26 #include "tree-chrec.h"
29 innermost_loop_behavior describes the evolution of the address of the memory
30 reference in the innermost enclosing loop. The address is expressed as
31 BASE + STEP * # of iteration, and base is further decomposed as the base
32 pointer (BASE_ADDRESS), loop invariant offset (OFFSET) and
33 constant offset (INIT). Examples, in loop nest
35 for (i = 0; i < 100; i++)
36 for (j = 3; j < 100; j++)
38 Example 1 Example 2
39 data-ref a[j].b[i][j] *(p + x + 16B + 4B * j)
42 innermost_loop_behavior
43 base_address &a p
44 offset i * D_i x
45 init 3 * D_j + offsetof (b) 28
46 step D_j 4
49 struct innermost_loop_behavior
51 tree base_address;
52 tree offset;
53 tree init;
54 tree step;
56 /* Alignment information. ALIGNED_TO is set to the largest power of two
57 that divides OFFSET. */
58 tree aligned_to;
61 /* Describes the evolutions of indices of the memory reference. The indices
62 are indices of the ARRAY_REFs, indexes in artificial dimensions
63 added for member selection of records and the operands of MEM_REFs.
64 BASE_OBJECT is the part of the reference that is loop-invariant
65 (note that this reference does not have to cover the whole object
66 being accessed, in which case UNCONSTRAINED_BASE is set; hence it is
67 not recommended to use BASE_OBJECT in any code generation).
68 For the examples above,
70 base_object: a *(p + x + 4B * j_0)
71 indices: {j_0, +, 1}_2 {16, +, 4}_2
73 {i_0, +, 1}_1
74 {j_0, +, 1}_2
77 struct indices
79 /* The object. */
80 tree base_object;
82 /* A list of chrecs. Access functions of the indices. */
83 vec<tree> access_fns;
85 /* Whether BASE_OBJECT is an access representing the whole object
86 or whether the access could not be constrained. */
87 bool unconstrained_base;
90 struct dr_alias
92 /* The alias information that should be used for new pointers to this
93 location. */
94 struct ptr_info_def *ptr_info;
97 /* An integer vector. A vector formally consists of an element of a vector
98 space. A vector space is a set that is closed under vector addition
99 and scalar multiplication. In this vector space, an element is a list of
100 integers. */
101 typedef int *lambda_vector;
103 /* An integer matrix. A matrix consists of m vectors of length n (IE
104 all vectors are the same length). */
105 typedef lambda_vector *lambda_matrix;
109 struct data_reference
111 /* A pointer to the statement that contains this DR. */
112 gimple stmt;
114 /* A pointer to the memory reference. */
115 tree ref;
117 /* Auxiliary info specific to a pass. */
118 void *aux;
120 /* True when the data reference is in RHS of a stmt. */
121 bool is_read;
123 /* Behavior of the memory reference in the innermost loop. */
124 struct innermost_loop_behavior innermost;
126 /* Subscripts of this data reference. */
127 struct indices indices;
129 /* Alias information for the data reference. */
130 struct dr_alias alias;
133 #define DR_STMT(DR) (DR)->stmt
134 #define DR_REF(DR) (DR)->ref
135 #define DR_BASE_OBJECT(DR) (DR)->indices.base_object
136 #define DR_UNCONSTRAINED_BASE(DR) (DR)->indices.unconstrained_base
137 #define DR_ACCESS_FNS(DR) (DR)->indices.access_fns
138 #define DR_ACCESS_FN(DR, I) DR_ACCESS_FNS (DR)[I]
139 #define DR_NUM_DIMENSIONS(DR) DR_ACCESS_FNS (DR).length ()
140 #define DR_IS_READ(DR) (DR)->is_read
141 #define DR_IS_WRITE(DR) (!DR_IS_READ (DR))
142 #define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address
143 #define DR_OFFSET(DR) (DR)->innermost.offset
144 #define DR_INIT(DR) (DR)->innermost.init
145 #define DR_STEP(DR) (DR)->innermost.step
146 #define DR_PTR_INFO(DR) (DR)->alias.ptr_info
147 #define DR_ALIGNED_TO(DR) (DR)->innermost.aligned_to
149 typedef struct data_reference *data_reference_p;
151 enum data_dependence_direction {
152 dir_positive,
153 dir_negative,
154 dir_equal,
155 dir_positive_or_negative,
156 dir_positive_or_equal,
157 dir_negative_or_equal,
158 dir_star,
159 dir_independent
162 /* The description of the grid of iterations that overlap. At most
163 two loops are considered at the same time just now, hence at most
164 two functions are needed. For each of the functions, we store
165 the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
166 where x, y, ... are variables. */
168 #define MAX_DIM 2
170 /* Special values of N. */
171 #define NO_DEPENDENCE 0
172 #define NOT_KNOWN (MAX_DIM + 1)
173 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
174 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
175 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
177 typedef vec<tree> affine_fn;
179 struct conflict_function
181 unsigned n;
182 affine_fn fns[MAX_DIM];
185 /* What is a subscript? Given two array accesses a subscript is the
186 tuple composed of the access functions for a given dimension.
187 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
188 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts
189 are stored in the data_dependence_relation structure under the form
190 of an array of subscripts. */
192 struct subscript
194 /* A description of the iterations for which the elements are
195 accessed twice. */
196 conflict_function *conflicting_iterations_in_a;
197 conflict_function *conflicting_iterations_in_b;
199 /* This field stores the information about the iteration domain
200 validity of the dependence relation. */
201 tree last_conflict;
203 /* Distance from the iteration that access a conflicting element in
204 A to the iteration that access this same conflicting element in
205 B. The distance is a tree scalar expression, i.e. a constant or a
206 symbolic expression, but certainly not a chrec function. */
207 tree distance;
210 typedef struct subscript *subscript_p;
212 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
213 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
214 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
215 #define SUB_DISTANCE(SUB) SUB->distance
217 /* A data_dependence_relation represents a relation between two
218 data_references A and B. */
220 struct data_dependence_relation
223 struct data_reference *a;
224 struct data_reference *b;
226 /* A "yes/no/maybe" field for the dependence relation:
228 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
229 relation between A and B, and the description of this relation
230 is given in the SUBSCRIPTS array,
232 - when "ARE_DEPENDENT == chrec_known", there is no dependence and
233 SUBSCRIPTS is empty,
235 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
236 but the analyzer cannot be more specific. */
237 tree are_dependent;
239 /* For each subscript in the dependence test, there is an element in
240 this array. This is the attribute that labels the edge A->B of
241 the data_dependence_relation. */
242 vec<subscript_p> subscripts;
244 /* The analyzed loop nest. */
245 vec<loop_p> loop_nest;
247 /* The classic direction vector. */
248 vec<lambda_vector> dir_vects;
250 /* The classic distance vector. */
251 vec<lambda_vector> dist_vects;
253 /* An index in loop_nest for the innermost loop that varies for
254 this data dependence relation. */
255 unsigned inner_loop;
257 /* Is the dependence reversed with respect to the lexicographic order? */
258 bool reversed_p;
260 /* When the dependence relation is affine, it can be represented by
261 a distance vector. */
262 bool affine_p;
264 /* Set to true when the dependence relation is on the same data
265 access. */
266 bool self_reference_p;
269 typedef struct data_dependence_relation *ddr_p;
271 #define DDR_A(DDR) DDR->a
272 #define DDR_B(DDR) DDR->b
273 #define DDR_AFFINE_P(DDR) DDR->affine_p
274 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
275 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
276 #define DDR_SUBSCRIPT(DDR, I) DDR_SUBSCRIPTS (DDR)[I]
277 #define DDR_NUM_SUBSCRIPTS(DDR) DDR_SUBSCRIPTS (DDR).length ()
279 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
280 /* The size of the direction/distance vectors: the number of loops in
281 the loop nest. */
282 #define DDR_NB_LOOPS(DDR) (DDR_LOOP_NEST (DDR).length ())
283 #define DDR_INNER_LOOP(DDR) DDR->inner_loop
284 #define DDR_SELF_REFERENCE(DDR) DDR->self_reference_p
286 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
287 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
288 #define DDR_NUM_DIST_VECTS(DDR) \
289 (DDR_DIST_VECTS (DDR).length ())
290 #define DDR_NUM_DIR_VECTS(DDR) \
291 (DDR_DIR_VECTS (DDR).length ())
292 #define DDR_DIR_VECT(DDR, I) \
293 DDR_DIR_VECTS (DDR)[I]
294 #define DDR_DIST_VECT(DDR, I) \
295 DDR_DIST_VECTS (DDR)[I]
296 #define DDR_REVERSED_P(DDR) DDR->reversed_p
299 bool dr_analyze_innermost (struct data_reference *, struct loop *);
300 extern bool compute_data_dependences_for_loop (struct loop *, bool,
301 vec<loop_p> *,
302 vec<data_reference_p> *,
303 vec<ddr_p> *);
304 extern bool compute_data_dependences_for_bb (basic_block, bool,
305 vec<data_reference_p> *,
306 vec<ddr_p> *);
307 extern void debug_ddrs (vec<ddr_p> );
308 extern void dump_data_reference (FILE *, struct data_reference *);
309 extern void debug (data_reference &ref);
310 extern void debug (data_reference *ptr);
311 extern void debug_data_reference (struct data_reference *);
312 extern void debug_data_references (vec<data_reference_p> );
313 extern void debug (vec<data_reference_p> &ref);
314 extern void debug (vec<data_reference_p> *ptr);
315 extern void debug_data_dependence_relation (struct data_dependence_relation *);
316 extern void dump_data_dependence_relations (FILE *, vec<ddr_p> );
317 extern void debug (vec<ddr_p> &ref);
318 extern void debug (vec<ddr_p> *ptr);
319 extern void debug_data_dependence_relations (vec<ddr_p> );
320 extern void free_dependence_relation (struct data_dependence_relation *);
321 extern void free_dependence_relations (vec<ddr_p> );
322 extern void free_data_ref (data_reference_p);
323 extern void free_data_refs (vec<data_reference_p> );
324 extern bool find_data_references_in_stmt (struct loop *, gimple,
325 vec<data_reference_p> *);
326 extern bool graphite_find_data_references_in_stmt (loop_p, loop_p, gimple,
327 vec<data_reference_p> *);
328 tree find_data_references_in_loop (struct loop *, vec<data_reference_p> *);
329 struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple, bool);
330 extern bool find_loop_nest (struct loop *, vec<loop_p> *);
331 extern struct data_dependence_relation *initialize_data_dependence_relation
332 (struct data_reference *, struct data_reference *, vec<loop_p>);
333 extern void compute_affine_dependence (struct data_dependence_relation *,
334 loop_p);
335 extern void compute_self_dependence (struct data_dependence_relation *);
336 extern bool compute_all_dependences (vec<data_reference_p> ,
337 vec<ddr_p> *,
338 vec<loop_p>, bool);
339 extern tree find_data_references_in_bb (struct loop *, basic_block,
340 vec<data_reference_p> *);
342 extern bool dr_may_alias_p (const struct data_reference *,
343 const struct data_reference *, bool);
344 extern bool dr_equal_offsets_p (struct data_reference *,
345 struct data_reference *);
346 extern void tree_check_data_deps (void);
349 /* Return true when the base objects of data references A and B are
350 the same memory object. */
352 static inline bool
353 same_data_refs_base_objects (data_reference_p a, data_reference_p b)
355 return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
356 && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
359 /* Return true when the data references A and B are accessing the same
360 memory object with the same access functions. */
362 static inline bool
363 same_data_refs (data_reference_p a, data_reference_p b)
365 unsigned int i;
367 /* The references are exactly the same. */
368 if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
369 return true;
371 if (!same_data_refs_base_objects (a, b))
372 return false;
374 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
375 if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
376 return false;
378 return true;
381 /* Return true when the DDR contains two data references that have the
382 same access functions. */
384 static inline bool
385 same_access_functions (const struct data_dependence_relation *ddr)
387 unsigned i;
389 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
390 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
391 DR_ACCESS_FN (DDR_B (ddr), i)))
392 return false;
394 return true;
397 /* Returns true when all the dependences are computable. */
399 inline bool
400 known_dependences_p (vec<ddr_p> dependence_relations)
402 ddr_p ddr;
403 unsigned int i;
405 FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
406 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
407 return false;
409 return true;
412 /* Returns the dependence level for a vector DIST of size LENGTH.
413 LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
414 to the sequence of statements, not carried by any loop. */
416 static inline unsigned
417 dependence_level (lambda_vector dist_vect, int length)
419 int i;
421 for (i = 0; i < length; i++)
422 if (dist_vect[i] != 0)
423 return i + 1;
425 return 0;
428 /* Return the dependence level for the DDR relation. */
430 static inline unsigned
431 ddr_dependence_level (ddr_p ddr)
433 unsigned vector;
434 unsigned level = 0;
436 if (DDR_DIST_VECTS (ddr).exists ())
437 level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
439 for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
440 level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
441 DDR_NB_LOOPS (ddr)));
442 return level;
445 /* Return the index of the variable VAR in the LOOP_NEST array. */
447 static inline int
448 index_in_loop_nest (int var, vec<loop_p> loop_nest)
450 struct loop *loopi;
451 int var_index;
453 for (var_index = 0; loop_nest.iterate (var_index, &loopi);
454 var_index++)
455 if (loopi->num == var)
456 break;
458 return var_index;
461 /* Returns true when the data reference DR the form "A[i] = ..."
462 with a stride equal to its unit type size. */
464 static inline bool
465 adjacent_dr_p (struct data_reference *dr)
467 /* If this is a bitfield store bail out. */
468 if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
469 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
470 return false;
472 if (!DR_STEP (dr)
473 || TREE_CODE (DR_STEP (dr)) != INTEGER_CST)
474 return false;
476 return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (DR_STEP (dr)),
477 DR_STEP (dr)),
478 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
481 void split_constant_offset (tree , tree *, tree *);
483 /* Compute the greatest common divisor of a VECTOR of SIZE numbers. */
485 static inline int
486 lambda_vector_gcd (lambda_vector vector, int size)
488 int i;
489 int gcd1 = 0;
491 if (size > 0)
493 gcd1 = vector[0];
494 for (i = 1; i < size; i++)
495 gcd1 = gcd (gcd1, vector[i]);
497 return gcd1;
500 /* Allocate a new vector of given SIZE. */
502 static inline lambda_vector
503 lambda_vector_new (int size)
505 /* ??? We shouldn't abuse the GC allocator here. */
506 return ggc_cleared_vec_alloc<int> (size);
509 /* Clear out vector VEC1 of length SIZE. */
511 static inline void
512 lambda_vector_clear (lambda_vector vec1, int size)
514 memset (vec1, 0, size * sizeof (*vec1));
517 /* Returns true when the vector V is lexicographically positive, in
518 other words, when the first nonzero element is positive. */
520 static inline bool
521 lambda_vector_lexico_pos (lambda_vector v,
522 unsigned n)
524 unsigned i;
525 for (i = 0; i < n; i++)
527 if (v[i] == 0)
528 continue;
529 if (v[i] < 0)
530 return false;
531 if (v[i] > 0)
532 return true;
534 return true;
537 /* Return true if vector VEC1 of length SIZE is the zero vector. */
539 static inline bool
540 lambda_vector_zerop (lambda_vector vec1, int size)
542 int i;
543 for (i = 0; i < size; i++)
544 if (vec1[i] != 0)
545 return false;
546 return true;
549 /* Allocate a matrix of M rows x N cols. */
551 static inline lambda_matrix
552 lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
554 lambda_matrix mat;
555 int i;
557 mat = XOBNEWVEC (lambda_obstack, lambda_vector, m);
559 for (i = 0; i < m; i++)
560 mat[i] = XOBNEWVEC (lambda_obstack, int, n);
562 return mat;
565 #endif /* GCC_TREE_DATA_REF_H */