1/* Data references and dependences detectors.
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
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 3, 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 COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#ifndef GCC_TREE_DATA_REF_H
22#define GCC_TREE_DATA_REF_H
23
24#include "graphds.h"
25#include "tree-chrec.h"
26
27/*
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
33
34 for (i = 0; i < 100; i++)
35 for (j = 3; j < 100; j++)
36
37 Example 1 Example 2
38 data-ref a[j].b[i][j] *(p + x + 16B + 4B * j)
39
40
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
46
47 */
48struct innermost_loop_behavior
49{
50 tree base_address;
51 tree offset;
52 tree init;
53 tree step;
54
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:
58
59 struct S __attribute__((aligned(16))) { ... };
60
61 char *ptr;
62 ... *(struct S *) (ptr - 4) ...;
63
64 the information would be:
65
66 base_address: ptr
67 base_aligment: 16
68 base_misalignment: 4
69 init: -4
70
71 where init cancels the base misalignment. If instead we had a
72 reference to a particular field:
73
74 struct S __attribute__((aligned(16))) { ... int f; ... };
75
76 char *ptr;
77 ... ((struct S *) (ptr - 4))->f ...;
78
79 the information would be:
80
81 base_address: ptr
82 base_aligment: 16
83 base_misalignment: 4
84 init: -4 + offsetof (S, f)
85
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;
90
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;
95
96 /* Likewise for STEP. */
97 unsigned int step_alignment;
98};
99
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,
108
109 base_object: a *(p + x + 4B * j_0)
110 indices: {j_0, +, 1}_2 {16, +, 4}_2
111 4
112 {i_0, +, 1}_1
113 {j_0, +, 1}_2
114*/
115
116struct indices
117{
118 /* The object. */
119 tree base_object;
120
121 /* A list of chrecs. Access functions of the indices. */
122 vec<tree> access_fns;
123
124 /* Whether BASE_OBJECT is an access representing the whole object
125 or whether the access could not be constrained. */
126 bool unconstrained_base;
127};
128
129struct dr_alias
130{
131 /* The alias information that should be used for new pointers to this
132 location. */
133 struct ptr_info_def *ptr_info;
134};
135
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. */
140typedef int *lambda_vector;
141
142/* An integer matrix. A matrix consists of m vectors of length n (IE
143 all vectors are the same length). */
144typedef lambda_vector *lambda_matrix;
145
146
147
148struct data_reference
149{
150 /* A pointer to the statement that contains this DR. */
151 gimple *stmt;
152
153 /* A pointer to the memory reference. */
154 tree ref;
155
156 /* Auxiliary info specific to a pass. */
157 void *aux;
158
159 /* True when the data reference is in RHS of a stmt. */
160 bool is_read;
161
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;
166
167 /* Behavior of the memory reference in the innermost loop. */
168 struct innermost_loop_behavior innermost;
169
170 /* Subscripts of this data reference. */
171 struct indices indices;
172
173 /* Alias information for the data reference. */
174 struct dr_alias alias;
175};
176
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
197
198typedef struct data_reference *data_reference_p;
199
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. */
203
204struct dr_with_seg_len
205{
206 dr_with_seg_len (data_reference_p d, tree len)
207 : dr (d), seg_len (len) {}
208
209 data_reference_p dr;
210 tree seg_len;
211};
212
213/* This struct contains two dr_with_seg_len objects with aliasing data
214 refs. Two comparisons are generated from them. */
215
216struct dr_with_seg_len_pair_t
217{
218 dr_with_seg_len_pair_t (const dr_with_seg_len& d1,
219 const dr_with_seg_len& d2)
220 : first (d1), second (d2) {}
221
222 dr_with_seg_len first;
223 dr_with_seg_len second;
224};
225
226enum data_dependence_direction {
227 dir_positive,
228 dir_negative,
229 dir_equal,
230 dir_positive_or_negative,
231 dir_positive_or_equal,
232 dir_negative_or_equal,
233 dir_star,
234 dir_independent
235};
236
237/* The description of the grid of iterations that overlap. At most
238 two loops are considered at the same time just now, hence at most
239 two functions are needed. For each of the functions, we store
240 the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
241 where x, y, ... are variables. */
242
243#define MAX_DIM 2
244
245/* Special values of N. */
246#define NO_DEPENDENCE 0
247#define NOT_KNOWN (MAX_DIM + 1)
248#define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
249#define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
250#define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
251
252typedef vec<tree> affine_fn;
253
254struct conflict_function
255{
256 unsigned n;
257 affine_fn fns[MAX_DIM];
258};
259
260/* What is a subscript? Given two array accesses a subscript is the
261 tuple composed of the access functions for a given dimension.
262 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
263 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts
264 are stored in the data_dependence_relation structure under the form
265 of an array of subscripts. */
266
267struct subscript
268{
269 /* The access functions of the two references. */
270 tree access_fn[2];
271
272 /* A description of the iterations for which the elements are
273 accessed twice. */
274 conflict_function *conflicting_iterations_in_a;
275 conflict_function *conflicting_iterations_in_b;
276
277 /* This field stores the information about the iteration domain
278 validity of the dependence relation. */
279 tree last_conflict;
280
281 /* Distance from the iteration that access a conflicting element in
282 A to the iteration that access this same conflicting element in
283 B. The distance is a tree scalar expression, i.e. a constant or a
284 symbolic expression, but certainly not a chrec function. */
285 tree distance;
286};
287
288typedef struct subscript *subscript_p;
289
290#define SUB_ACCESS_FN(SUB, I) (SUB)->access_fn[I]
291#define SUB_CONFLICTS_IN_A(SUB) (SUB)->conflicting_iterations_in_a
292#define SUB_CONFLICTS_IN_B(SUB) (SUB)->conflicting_iterations_in_b
293#define SUB_LAST_CONFLICT(SUB) (SUB)->last_conflict
294#define SUB_DISTANCE(SUB) (SUB)->distance
295
296/* A data_dependence_relation represents a relation between two
297 data_references A and B. */
298
299struct data_dependence_relation
300{
301
302 struct data_reference *a;
303 struct data_reference *b;
304
305 /* A "yes/no/maybe" field for the dependence relation:
306
307 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
308 relation between A and B, and the description of this relation
309 is given in the SUBSCRIPTS array,
310
311 - when "ARE_DEPENDENT == chrec_known", there is no dependence and
312 SUBSCRIPTS is empty,
313
314 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
315 but the analyzer cannot be more specific. */
316 tree are_dependent;
317
318 /* If nonnull, COULD_BE_INDEPENDENT_P is true and the accesses are
319 independent when the runtime addresses of OBJECT_A and OBJECT_B
320 are different. The addresses of both objects are invariant in the
321 loop nest. */
322 tree object_a;
323 tree object_b;
324
325 /* For each subscript in the dependence test, there is an element in
326 this array. This is the attribute that labels the edge A->B of
327 the data_dependence_relation. */
328 vec<subscript_p> subscripts;
329
330 /* The analyzed loop nest. */
331 vec<loop_p> loop_nest;
332
333 /* The classic direction vector. */
334 vec<lambda_vector> dir_vects;
335
336 /* The classic distance vector. */
337 vec<lambda_vector> dist_vects;
338
339 /* An index in loop_nest for the innermost loop that varies for
340 this data dependence relation. */
341 unsigned inner_loop;
342
343 /* Is the dependence reversed with respect to the lexicographic order? */
344 bool reversed_p;
345
346 /* When the dependence relation is affine, it can be represented by
347 a distance vector. */
348 bool affine_p;
349
350 /* Set to true when the dependence relation is on the same data
351 access. */
352 bool self_reference_p;
353
354 /* True if the dependence described is conservatively correct rather
355 than exact, and if it is still possible for the accesses to be
356 conditionally independent. For example, the a and b references in:
357
358 struct s *a, *b;
359 for (int i = 0; i < n; ++i)
360 a->f[i] += b->f[i];
361
362 conservatively have a distance vector of (0), for the case in which
363 a == b, but the accesses are independent if a != b. Similarly,
364 the a and b references in:
365
366 struct s *a, *b;
367 for (int i = 0; i < n; ++i)
368 a[0].f[i] += b[i].f[i];
369
370 conservatively have a distance vector of (0), but they are indepenent
371 when a != b + i. In contrast, the references in:
372
373 struct s *a;
374 for (int i = 0; i < n; ++i)
375 a->f[i] += a->f[i];
376
377 have the same distance vector of (0), but the accesses can never be
378 independent. */
379 bool could_be_independent_p;
380};
381
382typedef struct data_dependence_relation *ddr_p;
383
384#define DDR_A(DDR) (DDR)->a
385#define DDR_B(DDR) (DDR)->b
386#define DDR_AFFINE_P(DDR) (DDR)->affine_p
387#define DDR_ARE_DEPENDENT(DDR) (DDR)->are_dependent
388#define DDR_OBJECT_A(DDR) (DDR)->object_a
389#define DDR_OBJECT_B(DDR) (DDR)->object_b
390#define DDR_SUBSCRIPTS(DDR) (DDR)->subscripts
391#define DDR_SUBSCRIPT(DDR, I) DDR_SUBSCRIPTS (DDR)[I]
392#define DDR_NUM_SUBSCRIPTS(DDR) DDR_SUBSCRIPTS (DDR).length ()
393
394#define DDR_LOOP_NEST(DDR) (DDR)->loop_nest
395/* The size of the direction/distance vectors: the number of loops in
396 the loop nest. */
397#define DDR_NB_LOOPS(DDR) (DDR_LOOP_NEST (DDR).length ())
398#define DDR_INNER_LOOP(DDR) (DDR)->inner_loop
399#define DDR_SELF_REFERENCE(DDR) (DDR)->self_reference_p
400
401#define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
402#define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
403#define DDR_NUM_DIST_VECTS(DDR) \
404 (DDR_DIST_VECTS (DDR).length ())
405#define DDR_NUM_DIR_VECTS(DDR) \
406 (DDR_DIR_VECTS (DDR).length ())
407#define DDR_DIR_VECT(DDR, I) \
408 DDR_DIR_VECTS (DDR)[I]
409#define DDR_DIST_VECT(DDR, I) \
410 DDR_DIST_VECTS (DDR)[I]
411#define DDR_REVERSED_P(DDR) (DDR)->reversed_p
412#define DDR_COULD_BE_INDEPENDENT_P(DDR) (DDR)->could_be_independent_p
413
414
415bool dr_analyze_innermost (innermost_loop_behavior *, tree, struct loop *);
416extern bool compute_data_dependences_for_loop (struct loop *, bool,
417 vec<loop_p> *,
418 vec<data_reference_p> *,
419 vec<ddr_p> *);
420extern void debug_ddrs (vec<ddr_p> );
421extern void dump_data_reference (FILE *, struct data_reference *);
422extern void debug (data_reference &ref);
423extern void debug (data_reference *ptr);
424extern void debug_data_reference (struct data_reference *);
425extern void debug_data_references (vec<data_reference_p> );
426extern void debug (vec<data_reference_p> &ref);
427extern void debug (vec<data_reference_p> *ptr);
428extern void debug_data_dependence_relation (struct data_dependence_relation *);
429extern void dump_data_dependence_relations (FILE *, vec<ddr_p> );
430extern void debug (vec<ddr_p> &ref);
431extern void debug (vec<ddr_p> *ptr);
432extern void debug_data_dependence_relations (vec<ddr_p> );
433extern void free_dependence_relation (struct data_dependence_relation *);
434extern void free_dependence_relations (vec<ddr_p> );
435extern void free_data_ref (data_reference_p);
436extern void free_data_refs (vec<data_reference_p> );
437extern bool find_data_references_in_stmt (struct loop *, gimple *,
438 vec<data_reference_p> *);
439extern bool graphite_find_data_references_in_stmt (edge, loop_p, gimple *,
440 vec<data_reference_p> *);
441tree find_data_references_in_loop (struct loop *, vec<data_reference_p> *);
442bool loop_nest_has_data_refs (loop_p loop);
443struct data_reference *create_data_ref (edge, loop_p, tree, gimple *, bool,
444 bool);
445extern bool find_loop_nest (struct loop *, vec<loop_p> *);
446extern struct data_dependence_relation *initialize_data_dependence_relation
447 (struct data_reference *, struct data_reference *, vec<loop_p>);
448extern void compute_affine_dependence (struct data_dependence_relation *,
449 loop_p);
450extern void compute_self_dependence (struct data_dependence_relation *);
451extern bool compute_all_dependences (vec<data_reference_p> ,
452 vec<ddr_p> *,
453 vec<loop_p>, bool);
454extern tree find_data_references_in_bb (struct loop *, basic_block,
455 vec<data_reference_p> *);
456extern unsigned int dr_alignment (innermost_loop_behavior *);
457
458/* Return the alignment in bytes that DR is guaranteed to have at all
459 times. */
460
461inline unsigned int
462dr_alignment (data_reference *dr)
463{
464 return dr_alignment (&DR_INNERMOST (dr));
465}
466
467extern bool dr_may_alias_p (const struct data_reference *,
468 const struct data_reference *, bool);
469extern bool dr_equal_offsets_p (struct data_reference *,
470 struct data_reference *);
471
472extern bool runtime_alias_check_p (ddr_p, struct loop *, bool);
473extern int data_ref_compare_tree (tree, tree);
474extern void prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *,
475 unsigned HOST_WIDE_INT);
476extern void create_runtime_alias_checks (struct loop *,
477 vec<dr_with_seg_len_pair_t> *, tree*);
478/* Return true when the base objects of data references A and B are
479 the same memory object. */
480
481static inline bool
482same_data_refs_base_objects (data_reference_p a, data_reference_p b)
483{
484 return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
485 && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
486}
487
488/* Return true when the data references A and B are accessing the same
489 memory object with the same access functions. */
490
491static inline bool
492same_data_refs (data_reference_p a, data_reference_p b)
493{
494 unsigned int i;
495
496 /* The references are exactly the same. */
497 if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
498 return true;
499
500 if (!same_data_refs_base_objects (a, b))
501 return false;
502
503 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
504 if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
505 return false;
506
507 return true;
508}
509
510/* Returns true when all the dependences are computable. */
511
512inline bool
513known_dependences_p (vec<ddr_p> dependence_relations)
514{
515 ddr_p ddr;
516 unsigned int i;
517
518 FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
519 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
520 return false;
521
522 return true;
523}
524
525/* Returns the dependence level for a vector DIST of size LENGTH.
526 LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
527 to the sequence of statements, not carried by any loop. */
528
529static inline unsigned
530dependence_level (lambda_vector dist_vect, int length)
531{
532 int i;
533
534 for (i = 0; i < length; i++)
535 if (dist_vect[i] != 0)
536 return i + 1;
537
538 return 0;
539}
540
541/* Return the dependence level for the DDR relation. */
542
543static inline unsigned
544ddr_dependence_level (ddr_p ddr)
545{
546 unsigned vector;
547 unsigned level = 0;
548
549 if (DDR_DIST_VECTS (ddr).exists ())
550 level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
551
552 for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
553 level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
554 DDR_NB_LOOPS (ddr)));
555 return level;
556}
557
558/* Return the index of the variable VAR in the LOOP_NEST array. */
559
560static inline int
561index_in_loop_nest (int var, vec<loop_p> loop_nest)
562{
563 struct loop *loopi;
564 int var_index;
565
566 for (var_index = 0; loop_nest.iterate (var_index, &loopi);
567 var_index++)
568 if (loopi->num == var)
569 break;
570
571 return var_index;
572}
573
574/* Returns true when the data reference DR the form "A[i] = ..."
575 with a stride equal to its unit type size. */
576
577static inline bool
578adjacent_dr_p (struct data_reference *dr)
579{
580 /* If this is a bitfield store bail out. */
581 if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
582 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
583 return false;
584
585 if (!DR_STEP (dr)
586 || TREE_CODE (DR_STEP (dr)) != INTEGER_CST)
587 return false;
588
589 return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (DR_STEP (dr)),
590 DR_STEP (dr)),
591 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
592}
593
594void split_constant_offset (tree , tree *, tree *);
595
596/* Compute the greatest common divisor of a VECTOR of SIZE numbers. */
597
598static inline int
599lambda_vector_gcd (lambda_vector vector, int size)
600{
601 int i;
602 int gcd1 = 0;
603
604 if (size > 0)
605 {
606 gcd1 = vector[0];
607 for (i = 1; i < size; i++)
608 gcd1 = gcd (gcd1, vector[i]);
609 }
610 return gcd1;
611}
612
613/* Allocate a new vector of given SIZE. */
614
615static inline lambda_vector
616lambda_vector_new (int size)
617{
618 /* ??? We shouldn't abuse the GC allocator here. */
619 return ggc_cleared_vec_alloc<int> (size);
620}
621
622/* Clear out vector VEC1 of length SIZE. */
623
624static inline void
625lambda_vector_clear (lambda_vector vec1, int size)
626{
627 memset (vec1, 0, size * sizeof (*vec1));
628}
629
630/* Returns true when the vector V is lexicographically positive, in
631 other words, when the first nonzero element is positive. */
632
633static inline bool
634lambda_vector_lexico_pos (lambda_vector v,
635 unsigned n)
636{
637 unsigned i;
638 for (i = 0; i < n; i++)
639 {
640 if (v[i] == 0)
641 continue;
642 if (v[i] < 0)
643 return false;
644 if (v[i] > 0)
645 return true;
646 }
647 return true;
648}
649
650/* Return true if vector VEC1 of length SIZE is the zero vector. */
651
652static inline bool
653lambda_vector_zerop (lambda_vector vec1, int size)
654{
655 int i;
656 for (i = 0; i < size; i++)
657 if (vec1[i] != 0)
658 return false;
659 return true;
660}
661
662/* Allocate a matrix of M rows x N cols. */
663
664static inline lambda_matrix
665lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
666{
667 lambda_matrix mat;
668 int i;
669
670 mat = XOBNEWVEC (lambda_obstack, lambda_vector, m);
671
672 for (i = 0; i < m; i++)
673 mat[i] = XOBNEWVEC (lambda_obstack, int, n);
674
675 return mat;
676}
677
678#endif /* GCC_TREE_DATA_REF_H */
679