Core issue 2310 - conversion to base of incomplete type.
[official-gcc.git] / gcc / tree-data-ref.h
blob8739853336abbd899958373b8a6a3300dfb30d6d
1 /* Data references and dependences detectors.
2 Copyright (C) 2003-2018 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 "tree-chrec.h"
28 innermost_loop_behavior describes the evolution of the address of the memory
29 reference in the innermost enclosing loop. The address is expressed as
30 BASE + STEP * # of iteration, and base is further decomposed as the base
31 pointer (BASE_ADDRESS), loop invariant offset (OFFSET) and
32 constant offset (INIT). Examples, in loop nest
34 for (i = 0; i < 100; i++)
35 for (j = 3; j < 100; j++)
37 Example 1 Example 2
38 data-ref a[j].b[i][j] *(p + x + 16B + 4B * j)
41 innermost_loop_behavior
42 base_address &a p
43 offset i * D_i x
44 init 3 * D_j + offsetof (b) 28
45 step D_j 4
48 struct innermost_loop_behavior
50 tree base_address;
51 tree offset;
52 tree init;
53 tree step;
55 /* BASE_ADDRESS is known to be misaligned by BASE_MISALIGNMENT bytes
56 from an alignment boundary of BASE_ALIGNMENT bytes. For example,
57 if we had:
59 struct S __attribute__((aligned(16))) { ... };
61 char *ptr;
62 ... *(struct S *) (ptr - 4) ...;
64 the information would be:
66 base_address: ptr
67 base_aligment: 16
68 base_misalignment: 4
69 init: -4
71 where init cancels the base misalignment. If instead we had a
72 reference to a particular field:
74 struct S __attribute__((aligned(16))) { ... int f; ... };
76 char *ptr;
77 ... ((struct S *) (ptr - 4))->f ...;
79 the information would be:
81 base_address: ptr
82 base_aligment: 16
83 base_misalignment: 4
84 init: -4 + offsetof (S, f)
86 where base_address + init might also be misaligned, and by a different
87 amount from base_address. */
88 unsigned int base_alignment;
89 unsigned int base_misalignment;
91 /* The largest power of two that divides OFFSET, capped to a suitably
92 high value if the offset is zero. This is a byte rather than a bit
93 quantity. */
94 unsigned int offset_alignment;
96 /* Likewise for STEP. */
97 unsigned int step_alignment;
100 /* Describes the evolutions of indices of the memory reference. The indices
101 are indices of the ARRAY_REFs, indexes in artificial dimensions
102 added for member selection of records and the operands of MEM_REFs.
103 BASE_OBJECT is the part of the reference that is loop-invariant
104 (note that this reference does not have to cover the whole object
105 being accessed, in which case UNCONSTRAINED_BASE is set; hence it is
106 not recommended to use BASE_OBJECT in any code generation).
107 For the examples above,
109 base_object: a *(p + x + 4B * j_0)
110 indices: {j_0, +, 1}_2 {16, +, 4}_2
112 {i_0, +, 1}_1
113 {j_0, +, 1}_2
116 struct indices
118 /* The object. */
119 tree base_object;
121 /* A list of chrecs. Access functions of the indices. */
122 vec<tree> access_fns;
124 /* Whether BASE_OBJECT is an access representing the whole object
125 or whether the access could not be constrained. */
126 bool unconstrained_base;
129 struct dr_alias
131 /* The alias information that should be used for new pointers to this
132 location. */
133 struct ptr_info_def *ptr_info;
136 /* An integer vector. A vector formally consists of an element of a vector
137 space. A vector space is a set that is closed under vector addition
138 and scalar multiplication. In this vector space, an element is a list of
139 integers. */
140 typedef int *lambda_vector;
142 /* An integer matrix. A matrix consists of m vectors of length n (IE
143 all vectors are the same length). */
144 typedef lambda_vector *lambda_matrix;
148 struct data_reference
150 /* A pointer to the statement that contains this DR. */
151 gimple *stmt;
153 /* A pointer to the memory reference. */
154 tree ref;
156 /* Auxiliary info specific to a pass. */
157 void *aux;
159 /* True when the data reference is in RHS of a stmt. */
160 bool is_read;
162 /* True when the data reference is conditional within STMT,
163 i.e. if it might not occur even when the statement is executed
164 and runs to completion. */
165 bool is_conditional_in_stmt;
167 /* Behavior of the memory reference in the innermost loop. */
168 struct innermost_loop_behavior innermost;
170 /* Subscripts of this data reference. */
171 struct indices indices;
173 /* Alias information for the data reference. */
174 struct dr_alias alias;
177 #define DR_STMT(DR) (DR)->stmt
178 #define DR_REF(DR) (DR)->ref
179 #define DR_BASE_OBJECT(DR) (DR)->indices.base_object
180 #define DR_UNCONSTRAINED_BASE(DR) (DR)->indices.unconstrained_base
181 #define DR_ACCESS_FNS(DR) (DR)->indices.access_fns
182 #define DR_ACCESS_FN(DR, I) DR_ACCESS_FNS (DR)[I]
183 #define DR_NUM_DIMENSIONS(DR) DR_ACCESS_FNS (DR).length ()
184 #define DR_IS_READ(DR) (DR)->is_read
185 #define DR_IS_WRITE(DR) (!DR_IS_READ (DR))
186 #define DR_IS_CONDITIONAL_IN_STMT(DR) (DR)->is_conditional_in_stmt
187 #define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address
188 #define DR_OFFSET(DR) (DR)->innermost.offset
189 #define DR_INIT(DR) (DR)->innermost.init
190 #define DR_STEP(DR) (DR)->innermost.step
191 #define DR_PTR_INFO(DR) (DR)->alias.ptr_info
192 #define DR_BASE_ALIGNMENT(DR) (DR)->innermost.base_alignment
193 #define DR_BASE_MISALIGNMENT(DR) (DR)->innermost.base_misalignment
194 #define DR_OFFSET_ALIGNMENT(DR) (DR)->innermost.offset_alignment
195 #define DR_STEP_ALIGNMENT(DR) (DR)->innermost.step_alignment
196 #define DR_INNERMOST(DR) (DR)->innermost
198 typedef struct data_reference *data_reference_p;
200 /* This struct is used to store the information of a data reference,
201 including the data ref itself and the segment length for aliasing
202 checks. This is used to merge alias checks. */
204 struct dr_with_seg_len
206 dr_with_seg_len (data_reference_p d, tree len, unsigned HOST_WIDE_INT size,
207 unsigned int a)
208 : dr (d), seg_len (len), access_size (size), align (a) {}
210 data_reference_p dr;
211 /* The offset of the last access that needs to be checked minus
212 the offset of the first. */
213 tree seg_len;
214 /* A value that, when added to abs (SEG_LEN), gives the total number of
215 bytes in the segment. */
216 poly_uint64 access_size;
217 /* The minimum common alignment of DR's start address, SEG_LEN and
218 ACCESS_SIZE. */
219 unsigned int align;
222 /* This struct contains two dr_with_seg_len objects with aliasing data
223 refs. Two comparisons are generated from them. */
225 struct dr_with_seg_len_pair_t
227 dr_with_seg_len_pair_t (const dr_with_seg_len& d1,
228 const dr_with_seg_len& d2)
229 : first (d1), second (d2) {}
231 dr_with_seg_len first;
232 dr_with_seg_len second;
235 enum data_dependence_direction {
236 dir_positive,
237 dir_negative,
238 dir_equal,
239 dir_positive_or_negative,
240 dir_positive_or_equal,
241 dir_negative_or_equal,
242 dir_star,
243 dir_independent
246 /* The description of the grid of iterations that overlap. At most
247 two loops are considered at the same time just now, hence at most
248 two functions are needed. For each of the functions, we store
249 the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
250 where x, y, ... are variables. */
252 #define MAX_DIM 2
254 /* Special values of N. */
255 #define NO_DEPENDENCE 0
256 #define NOT_KNOWN (MAX_DIM + 1)
257 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
258 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
259 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
261 typedef vec<tree> affine_fn;
263 struct conflict_function
265 unsigned n;
266 affine_fn fns[MAX_DIM];
269 /* What is a subscript? Given two array accesses a subscript is the
270 tuple composed of the access functions for a given dimension.
271 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
272 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts
273 are stored in the data_dependence_relation structure under the form
274 of an array of subscripts. */
276 struct subscript
278 /* The access functions of the two references. */
279 tree access_fn[2];
281 /* A description of the iterations for which the elements are
282 accessed twice. */
283 conflict_function *conflicting_iterations_in_a;
284 conflict_function *conflicting_iterations_in_b;
286 /* This field stores the information about the iteration domain
287 validity of the dependence relation. */
288 tree last_conflict;
290 /* Distance from the iteration that access a conflicting element in
291 A to the iteration that access this same conflicting element in
292 B. The distance is a tree scalar expression, i.e. a constant or a
293 symbolic expression, but certainly not a chrec function. */
294 tree distance;
297 typedef struct subscript *subscript_p;
299 #define SUB_ACCESS_FN(SUB, I) (SUB)->access_fn[I]
300 #define SUB_CONFLICTS_IN_A(SUB) (SUB)->conflicting_iterations_in_a
301 #define SUB_CONFLICTS_IN_B(SUB) (SUB)->conflicting_iterations_in_b
302 #define SUB_LAST_CONFLICT(SUB) (SUB)->last_conflict
303 #define SUB_DISTANCE(SUB) (SUB)->distance
305 /* A data_dependence_relation represents a relation between two
306 data_references A and B. */
308 struct data_dependence_relation
311 struct data_reference *a;
312 struct data_reference *b;
314 /* A "yes/no/maybe" field for the dependence relation:
316 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
317 relation between A and B, and the description of this relation
318 is given in the SUBSCRIPTS array,
320 - when "ARE_DEPENDENT == chrec_known", there is no dependence and
321 SUBSCRIPTS is empty,
323 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
324 but the analyzer cannot be more specific. */
325 tree are_dependent;
327 /* If nonnull, COULD_BE_INDEPENDENT_P is true and the accesses are
328 independent when the runtime addresses of OBJECT_A and OBJECT_B
329 are different. The addresses of both objects are invariant in the
330 loop nest. */
331 tree object_a;
332 tree object_b;
334 /* For each subscript in the dependence test, there is an element in
335 this array. This is the attribute that labels the edge A->B of
336 the data_dependence_relation. */
337 vec<subscript_p> subscripts;
339 /* The analyzed loop nest. */
340 vec<loop_p> loop_nest;
342 /* The classic direction vector. */
343 vec<lambda_vector> dir_vects;
345 /* The classic distance vector. */
346 vec<lambda_vector> dist_vects;
348 /* An index in loop_nest for the innermost loop that varies for
349 this data dependence relation. */
350 unsigned inner_loop;
352 /* Is the dependence reversed with respect to the lexicographic order? */
353 bool reversed_p;
355 /* When the dependence relation is affine, it can be represented by
356 a distance vector. */
357 bool affine_p;
359 /* Set to true when the dependence relation is on the same data
360 access. */
361 bool self_reference_p;
363 /* True if the dependence described is conservatively correct rather
364 than exact, and if it is still possible for the accesses to be
365 conditionally independent. For example, the a and b references in:
367 struct s *a, *b;
368 for (int i = 0; i < n; ++i)
369 a->f[i] += b->f[i];
371 conservatively have a distance vector of (0), for the case in which
372 a == b, but the accesses are independent if a != b. Similarly,
373 the a and b references in:
375 struct s *a, *b;
376 for (int i = 0; i < n; ++i)
377 a[0].f[i] += b[i].f[i];
379 conservatively have a distance vector of (0), but they are indepenent
380 when a != b + i. In contrast, the references in:
382 struct s *a;
383 for (int i = 0; i < n; ++i)
384 a->f[i] += a->f[i];
386 have the same distance vector of (0), but the accesses can never be
387 independent. */
388 bool could_be_independent_p;
391 typedef struct data_dependence_relation *ddr_p;
393 #define DDR_A(DDR) (DDR)->a
394 #define DDR_B(DDR) (DDR)->b
395 #define DDR_AFFINE_P(DDR) (DDR)->affine_p
396 #define DDR_ARE_DEPENDENT(DDR) (DDR)->are_dependent
397 #define DDR_OBJECT_A(DDR) (DDR)->object_a
398 #define DDR_OBJECT_B(DDR) (DDR)->object_b
399 #define DDR_SUBSCRIPTS(DDR) (DDR)->subscripts
400 #define DDR_SUBSCRIPT(DDR, I) DDR_SUBSCRIPTS (DDR)[I]
401 #define DDR_NUM_SUBSCRIPTS(DDR) DDR_SUBSCRIPTS (DDR).length ()
403 #define DDR_LOOP_NEST(DDR) (DDR)->loop_nest
404 /* The size of the direction/distance vectors: the number of loops in
405 the loop nest. */
406 #define DDR_NB_LOOPS(DDR) (DDR_LOOP_NEST (DDR).length ())
407 #define DDR_INNER_LOOP(DDR) (DDR)->inner_loop
408 #define DDR_SELF_REFERENCE(DDR) (DDR)->self_reference_p
410 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
411 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
412 #define DDR_NUM_DIST_VECTS(DDR) \
413 (DDR_DIST_VECTS (DDR).length ())
414 #define DDR_NUM_DIR_VECTS(DDR) \
415 (DDR_DIR_VECTS (DDR).length ())
416 #define DDR_DIR_VECT(DDR, I) \
417 DDR_DIR_VECTS (DDR)[I]
418 #define DDR_DIST_VECT(DDR, I) \
419 DDR_DIST_VECTS (DDR)[I]
420 #define DDR_REVERSED_P(DDR) (DDR)->reversed_p
421 #define DDR_COULD_BE_INDEPENDENT_P(DDR) (DDR)->could_be_independent_p
424 bool dr_analyze_innermost (innermost_loop_behavior *, tree, struct loop *);
425 extern bool compute_data_dependences_for_loop (struct loop *, bool,
426 vec<loop_p> *,
427 vec<data_reference_p> *,
428 vec<ddr_p> *);
429 extern void debug_ddrs (vec<ddr_p> );
430 extern void dump_data_reference (FILE *, struct data_reference *);
431 extern void debug (data_reference &ref);
432 extern void debug (data_reference *ptr);
433 extern void debug_data_reference (struct data_reference *);
434 extern void debug_data_references (vec<data_reference_p> );
435 extern void debug (vec<data_reference_p> &ref);
436 extern void debug (vec<data_reference_p> *ptr);
437 extern void debug_data_dependence_relation (struct data_dependence_relation *);
438 extern void dump_data_dependence_relations (FILE *, vec<ddr_p> );
439 extern void debug (vec<ddr_p> &ref);
440 extern void debug (vec<ddr_p> *ptr);
441 extern void debug_data_dependence_relations (vec<ddr_p> );
442 extern void free_dependence_relation (struct data_dependence_relation *);
443 extern void free_dependence_relations (vec<ddr_p> );
444 extern void free_data_ref (data_reference_p);
445 extern void free_data_refs (vec<data_reference_p> );
446 extern bool find_data_references_in_stmt (struct loop *, gimple *,
447 vec<data_reference_p> *);
448 extern bool graphite_find_data_references_in_stmt (edge, loop_p, gimple *,
449 vec<data_reference_p> *);
450 tree find_data_references_in_loop (struct loop *, vec<data_reference_p> *);
451 bool loop_nest_has_data_refs (loop_p loop);
452 struct data_reference *create_data_ref (edge, loop_p, tree, gimple *, bool,
453 bool);
454 extern bool find_loop_nest (struct loop *, vec<loop_p> *);
455 extern struct data_dependence_relation *initialize_data_dependence_relation
456 (struct data_reference *, struct data_reference *, vec<loop_p>);
457 extern void compute_affine_dependence (struct data_dependence_relation *,
458 loop_p);
459 extern void compute_self_dependence (struct data_dependence_relation *);
460 extern bool compute_all_dependences (vec<data_reference_p> ,
461 vec<ddr_p> *,
462 vec<loop_p>, bool);
463 extern tree find_data_references_in_bb (struct loop *, basic_block,
464 vec<data_reference_p> *);
465 extern unsigned int dr_alignment (innermost_loop_behavior *);
466 extern tree get_base_for_alignment (tree, unsigned int *);
468 /* Return the alignment in bytes that DR is guaranteed to have at all
469 times. */
471 inline unsigned int
472 dr_alignment (data_reference *dr)
474 return dr_alignment (&DR_INNERMOST (dr));
477 extern bool dr_may_alias_p (const struct data_reference *,
478 const struct data_reference *, bool);
479 extern bool dr_equal_offsets_p (struct data_reference *,
480 struct data_reference *);
482 extern bool runtime_alias_check_p (ddr_p, struct loop *, bool);
483 extern int data_ref_compare_tree (tree, tree);
484 extern void prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *,
485 poly_uint64);
486 extern void create_runtime_alias_checks (struct loop *,
487 vec<dr_with_seg_len_pair_t> *, tree*);
488 extern tree dr_direction_indicator (struct data_reference *);
489 extern tree dr_zero_step_indicator (struct data_reference *);
490 extern bool dr_known_forward_stride_p (struct data_reference *);
492 /* Return true when the base objects of data references A and B are
493 the same memory object. */
495 static inline bool
496 same_data_refs_base_objects (data_reference_p a, data_reference_p b)
498 return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
499 && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
502 /* Return true when the data references A and B are accessing the same
503 memory object with the same access functions. */
505 static inline bool
506 same_data_refs (data_reference_p a, data_reference_p b)
508 unsigned int i;
510 /* The references are exactly the same. */
511 if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
512 return true;
514 if (!same_data_refs_base_objects (a, b))
515 return false;
517 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
518 if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
519 return false;
521 return true;
524 /* Returns true when all the dependences are computable. */
526 inline bool
527 known_dependences_p (vec<ddr_p> dependence_relations)
529 ddr_p ddr;
530 unsigned int i;
532 FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
533 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
534 return false;
536 return true;
539 /* Returns the dependence level for a vector DIST of size LENGTH.
540 LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
541 to the sequence of statements, not carried by any loop. */
543 static inline unsigned
544 dependence_level (lambda_vector dist_vect, int length)
546 int i;
548 for (i = 0; i < length; i++)
549 if (dist_vect[i] != 0)
550 return i + 1;
552 return 0;
555 /* Return the dependence level for the DDR relation. */
557 static inline unsigned
558 ddr_dependence_level (ddr_p ddr)
560 unsigned vector;
561 unsigned level = 0;
563 if (DDR_DIST_VECTS (ddr).exists ())
564 level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
566 for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
567 level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
568 DDR_NB_LOOPS (ddr)));
569 return level;
572 /* Return the index of the variable VAR in the LOOP_NEST array. */
574 static inline int
575 index_in_loop_nest (int var, vec<loop_p> loop_nest)
577 struct loop *loopi;
578 int var_index;
580 for (var_index = 0; loop_nest.iterate (var_index, &loopi);
581 var_index++)
582 if (loopi->num == var)
583 break;
585 return var_index;
588 /* Returns true when the data reference DR the form "A[i] = ..."
589 with a stride equal to its unit type size. */
591 static inline bool
592 adjacent_dr_p (struct data_reference *dr)
594 /* If this is a bitfield store bail out. */
595 if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
596 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
597 return false;
599 if (!DR_STEP (dr)
600 || TREE_CODE (DR_STEP (dr)) != INTEGER_CST)
601 return false;
603 return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (DR_STEP (dr)),
604 DR_STEP (dr)),
605 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
608 void split_constant_offset (tree , tree *, tree *);
610 /* Compute the greatest common divisor of a VECTOR of SIZE numbers. */
612 static inline int
613 lambda_vector_gcd (lambda_vector vector, int size)
615 int i;
616 int gcd1 = 0;
618 if (size > 0)
620 gcd1 = vector[0];
621 for (i = 1; i < size; i++)
622 gcd1 = gcd (gcd1, vector[i]);
624 return gcd1;
627 /* Allocate a new vector of given SIZE. */
629 static inline lambda_vector
630 lambda_vector_new (int size)
632 /* ??? We shouldn't abuse the GC allocator here. */
633 return ggc_cleared_vec_alloc<int> (size);
636 /* Clear out vector VEC1 of length SIZE. */
638 static inline void
639 lambda_vector_clear (lambda_vector vec1, int size)
641 memset (vec1, 0, size * sizeof (*vec1));
644 /* Returns true when the vector V is lexicographically positive, in
645 other words, when the first nonzero element is positive. */
647 static inline bool
648 lambda_vector_lexico_pos (lambda_vector v,
649 unsigned n)
651 unsigned i;
652 for (i = 0; i < n; i++)
654 if (v[i] == 0)
655 continue;
656 if (v[i] < 0)
657 return false;
658 if (v[i] > 0)
659 return true;
661 return true;
664 /* Return true if vector VEC1 of length SIZE is the zero vector. */
666 static inline bool
667 lambda_vector_zerop (lambda_vector vec1, int size)
669 int i;
670 for (i = 0; i < size; i++)
671 if (vec1[i] != 0)
672 return false;
673 return true;
676 /* Allocate a matrix of M rows x N cols. */
678 static inline lambda_matrix
679 lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
681 lambda_matrix mat;
682 int i;
684 mat = XOBNEWVEC (lambda_obstack, lambda_vector, m);
686 for (i = 0; i < m; i++)
687 mat[i] = XOBNEWVEC (lambda_obstack, int, n);
689 return mat;
692 #endif /* GCC_TREE_DATA_REF_H */