1 /* Data references and dependences detectors.
2 Copyright (C) 2003-2017 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
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
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
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++)
38 data-ref a[j].b[i][j] *(p + x + 16B + 4B * j)
41 innermost_loop_behavior
44 init 3 * D_j + offsetof (b) 28
48 struct innermost_loop_behavior
55 /* BASE_ADDRESS is known to be misaligned by BASE_MISALIGNMENT bytes
56 from an alignment boundary of BASE_ALIGNMENT bytes. For example,
59 struct S __attribute__((aligned(16))) { ... };
62 ... *(struct S *) (ptr - 4) ...;
64 the information would be:
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; ... };
77 ... ((struct S *) (ptr - 4))->f ...;
79 the information would be:
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
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
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
;
131 /* The alias information that should be used for new pointers to this
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
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. */
153 /* A pointer to the memory reference. */
156 /* Auxiliary info specific to a pass. */
159 /* True when the data reference is in RHS of a stmt. */
162 /* Behavior of the memory reference in the innermost loop. */
163 struct innermost_loop_behavior innermost
;
165 /* Subscripts of this data reference. */
166 struct indices indices
;
168 /* Alias information for the data reference. */
169 struct dr_alias alias
;
172 #define DR_STMT(DR) (DR)->stmt
173 #define DR_REF(DR) (DR)->ref
174 #define DR_BASE_OBJECT(DR) (DR)->indices.base_object
175 #define DR_UNCONSTRAINED_BASE(DR) (DR)->indices.unconstrained_base
176 #define DR_ACCESS_FNS(DR) (DR)->indices.access_fns
177 #define DR_ACCESS_FN(DR, I) DR_ACCESS_FNS (DR)[I]
178 #define DR_NUM_DIMENSIONS(DR) DR_ACCESS_FNS (DR).length ()
179 #define DR_IS_READ(DR) (DR)->is_read
180 #define DR_IS_WRITE(DR) (!DR_IS_READ (DR))
181 #define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address
182 #define DR_OFFSET(DR) (DR)->innermost.offset
183 #define DR_INIT(DR) (DR)->innermost.init
184 #define DR_STEP(DR) (DR)->innermost.step
185 #define DR_PTR_INFO(DR) (DR)->alias.ptr_info
186 #define DR_BASE_ALIGNMENT(DR) (DR)->innermost.base_alignment
187 #define DR_BASE_MISALIGNMENT(DR) (DR)->innermost.base_misalignment
188 #define DR_OFFSET_ALIGNMENT(DR) (DR)->innermost.offset_alignment
189 #define DR_STEP_ALIGNMENT(DR) (DR)->innermost.step_alignment
190 #define DR_INNERMOST(DR) (DR)->innermost
192 typedef struct data_reference
*data_reference_p
;
194 /* This struct is used to store the information of a data reference,
195 including the data ref itself and the segment length for aliasing
196 checks. This is used to merge alias checks. */
198 struct dr_with_seg_len
200 dr_with_seg_len (data_reference_p d
, tree len
)
201 : dr (d
), seg_len (len
) {}
207 /* This struct contains two dr_with_seg_len objects with aliasing data
208 refs. Two comparisons are generated from them. */
210 struct dr_with_seg_len_pair_t
212 dr_with_seg_len_pair_t (const dr_with_seg_len
& d1
,
213 const dr_with_seg_len
& d2
)
214 : first (d1
), second (d2
) {}
216 dr_with_seg_len first
;
217 dr_with_seg_len second
;
220 enum data_dependence_direction
{
224 dir_positive_or_negative
,
225 dir_positive_or_equal
,
226 dir_negative_or_equal
,
231 /* The description of the grid of iterations that overlap. At most
232 two loops are considered at the same time just now, hence at most
233 two functions are needed. For each of the functions, we store
234 the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
235 where x, y, ... are variables. */
239 /* Special values of N. */
240 #define NO_DEPENDENCE 0
241 #define NOT_KNOWN (MAX_DIM + 1)
242 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
243 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
244 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
246 typedef vec
<tree
> affine_fn
;
248 struct conflict_function
251 affine_fn fns
[MAX_DIM
];
254 /* What is a subscript? Given two array accesses a subscript is the
255 tuple composed of the access functions for a given dimension.
256 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
257 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts
258 are stored in the data_dependence_relation structure under the form
259 of an array of subscripts. */
263 /* A description of the iterations for which the elements are
265 conflict_function
*conflicting_iterations_in_a
;
266 conflict_function
*conflicting_iterations_in_b
;
268 /* This field stores the information about the iteration domain
269 validity of the dependence relation. */
272 /* Distance from the iteration that access a conflicting element in
273 A to the iteration that access this same conflicting element in
274 B. The distance is a tree scalar expression, i.e. a constant or a
275 symbolic expression, but certainly not a chrec function. */
279 typedef struct subscript
*subscript_p
;
281 #define SUB_CONFLICTS_IN_A(SUB) (SUB)->conflicting_iterations_in_a
282 #define SUB_CONFLICTS_IN_B(SUB) (SUB)->conflicting_iterations_in_b
283 #define SUB_LAST_CONFLICT(SUB) (SUB)->last_conflict
284 #define SUB_DISTANCE(SUB) (SUB)->distance
286 /* A data_dependence_relation represents a relation between two
287 data_references A and B. */
289 struct data_dependence_relation
292 struct data_reference
*a
;
293 struct data_reference
*b
;
295 /* A "yes/no/maybe" field for the dependence relation:
297 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
298 relation between A and B, and the description of this relation
299 is given in the SUBSCRIPTS array,
301 - when "ARE_DEPENDENT == chrec_known", there is no dependence and
304 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
305 but the analyzer cannot be more specific. */
308 /* For each subscript in the dependence test, there is an element in
309 this array. This is the attribute that labels the edge A->B of
310 the data_dependence_relation. */
311 vec
<subscript_p
> subscripts
;
313 /* The analyzed loop nest. */
314 vec
<loop_p
> loop_nest
;
316 /* The classic direction vector. */
317 vec
<lambda_vector
> dir_vects
;
319 /* The classic distance vector. */
320 vec
<lambda_vector
> dist_vects
;
322 /* An index in loop_nest for the innermost loop that varies for
323 this data dependence relation. */
326 /* Is the dependence reversed with respect to the lexicographic order? */
329 /* When the dependence relation is affine, it can be represented by
330 a distance vector. */
333 /* Set to true when the dependence relation is on the same data
335 bool self_reference_p
;
338 typedef struct data_dependence_relation
*ddr_p
;
340 #define DDR_A(DDR) (DDR)->a
341 #define DDR_B(DDR) (DDR)->b
342 #define DDR_AFFINE_P(DDR) (DDR)->affine_p
343 #define DDR_ARE_DEPENDENT(DDR) (DDR)->are_dependent
344 #define DDR_SUBSCRIPTS(DDR) (DDR)->subscripts
345 #define DDR_SUBSCRIPT(DDR, I) DDR_SUBSCRIPTS (DDR)[I]
346 #define DDR_NUM_SUBSCRIPTS(DDR) DDR_SUBSCRIPTS (DDR).length ()
348 #define DDR_LOOP_NEST(DDR) (DDR)->loop_nest
349 /* The size of the direction/distance vectors: the number of loops in
351 #define DDR_NB_LOOPS(DDR) (DDR_LOOP_NEST (DDR).length ())
352 #define DDR_INNER_LOOP(DDR) (DDR)->inner_loop
353 #define DDR_SELF_REFERENCE(DDR) (DDR)->self_reference_p
355 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
356 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
357 #define DDR_NUM_DIST_VECTS(DDR) \
358 (DDR_DIST_VECTS (DDR).length ())
359 #define DDR_NUM_DIR_VECTS(DDR) \
360 (DDR_DIR_VECTS (DDR).length ())
361 #define DDR_DIR_VECT(DDR, I) \
362 DDR_DIR_VECTS (DDR)[I]
363 #define DDR_DIST_VECT(DDR, I) \
364 DDR_DIST_VECTS (DDR)[I]
365 #define DDR_REVERSED_P(DDR) (DDR)->reversed_p
368 bool dr_analyze_innermost (innermost_loop_behavior
*, tree
, struct loop
*);
369 extern bool compute_data_dependences_for_loop (struct loop
*, bool,
371 vec
<data_reference_p
> *,
373 extern void debug_ddrs (vec
<ddr_p
> );
374 extern void dump_data_reference (FILE *, struct data_reference
*);
375 extern void debug (data_reference
&ref
);
376 extern void debug (data_reference
*ptr
);
377 extern void debug_data_reference (struct data_reference
*);
378 extern void debug_data_references (vec
<data_reference_p
> );
379 extern void debug (vec
<data_reference_p
> &ref
);
380 extern void debug (vec
<data_reference_p
> *ptr
);
381 extern void debug_data_dependence_relation (struct data_dependence_relation
*);
382 extern void dump_data_dependence_relations (FILE *, vec
<ddr_p
> );
383 extern void debug (vec
<ddr_p
> &ref
);
384 extern void debug (vec
<ddr_p
> *ptr
);
385 extern void debug_data_dependence_relations (vec
<ddr_p
> );
386 extern void free_dependence_relation (struct data_dependence_relation
*);
387 extern void free_dependence_relations (vec
<ddr_p
> );
388 extern void free_data_ref (data_reference_p
);
389 extern void free_data_refs (vec
<data_reference_p
> );
390 extern bool find_data_references_in_stmt (struct loop
*, gimple
*,
391 vec
<data_reference_p
> *);
392 extern bool graphite_find_data_references_in_stmt (loop_p
, loop_p
, gimple
*,
393 vec
<data_reference_p
> *);
394 tree
find_data_references_in_loop (struct loop
*, vec
<data_reference_p
> *);
395 bool loop_nest_has_data_refs (loop_p loop
);
396 struct data_reference
*create_data_ref (loop_p
, loop_p
, tree
, gimple
*, bool);
397 extern bool find_loop_nest (struct loop
*, vec
<loop_p
> *);
398 extern struct data_dependence_relation
*initialize_data_dependence_relation
399 (struct data_reference
*, struct data_reference
*, vec
<loop_p
>);
400 extern void compute_affine_dependence (struct data_dependence_relation
*,
402 extern void compute_self_dependence (struct data_dependence_relation
*);
403 extern bool compute_all_dependences (vec
<data_reference_p
> ,
406 extern tree
find_data_references_in_bb (struct loop
*, basic_block
,
407 vec
<data_reference_p
> *);
408 extern unsigned int dr_alignment (innermost_loop_behavior
*);
410 /* Return the alignment in bytes that DR is guaranteed to have at all
414 dr_alignment (data_reference
*dr
)
416 return dr_alignment (&DR_INNERMOST (dr
));
419 extern bool dr_may_alias_p (const struct data_reference
*,
420 const struct data_reference
*, bool);
421 extern bool dr_equal_offsets_p (struct data_reference
*,
422 struct data_reference
*);
424 extern bool runtime_alias_check_p (ddr_p
, struct loop
*, bool);
425 extern int data_ref_compare_tree (tree
, tree
);
426 extern void prune_runtime_alias_test_list (vec
<dr_with_seg_len_pair_t
> *,
427 unsigned HOST_WIDE_INT
);
428 extern void create_runtime_alias_checks (struct loop
*,
429 vec
<dr_with_seg_len_pair_t
> *, tree
*);
430 /* Return true when the base objects of data references A and B are
431 the same memory object. */
434 same_data_refs_base_objects (data_reference_p a
, data_reference_p b
)
436 return DR_NUM_DIMENSIONS (a
) == DR_NUM_DIMENSIONS (b
)
437 && operand_equal_p (DR_BASE_OBJECT (a
), DR_BASE_OBJECT (b
), 0);
440 /* Return true when the data references A and B are accessing the same
441 memory object with the same access functions. */
444 same_data_refs (data_reference_p a
, data_reference_p b
)
448 /* The references are exactly the same. */
449 if (operand_equal_p (DR_REF (a
), DR_REF (b
), 0))
452 if (!same_data_refs_base_objects (a
, b
))
455 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
456 if (!eq_evolutions_p (DR_ACCESS_FN (a
, i
), DR_ACCESS_FN (b
, i
)))
462 /* Return true when the DDR contains two data references that have the
463 same access functions. */
466 same_access_functions (const struct data_dependence_relation
*ddr
)
470 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
471 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr
), i
),
472 DR_ACCESS_FN (DDR_B (ddr
), i
)))
478 /* Returns true when all the dependences are computable. */
481 known_dependences_p (vec
<ddr_p
> dependence_relations
)
486 FOR_EACH_VEC_ELT (dependence_relations
, i
, ddr
)
487 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
493 /* Returns the dependence level for a vector DIST of size LENGTH.
494 LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
495 to the sequence of statements, not carried by any loop. */
497 static inline unsigned
498 dependence_level (lambda_vector dist_vect
, int length
)
502 for (i
= 0; i
< length
; i
++)
503 if (dist_vect
[i
] != 0)
509 /* Return the dependence level for the DDR relation. */
511 static inline unsigned
512 ddr_dependence_level (ddr_p ddr
)
517 if (DDR_DIST_VECTS (ddr
).exists ())
518 level
= dependence_level (DDR_DIST_VECT (ddr
, 0), DDR_NB_LOOPS (ddr
));
520 for (vector
= 1; vector
< DDR_NUM_DIST_VECTS (ddr
); vector
++)
521 level
= MIN (level
, dependence_level (DDR_DIST_VECT (ddr
, vector
),
522 DDR_NB_LOOPS (ddr
)));
526 /* Return the index of the variable VAR in the LOOP_NEST array. */
529 index_in_loop_nest (int var
, vec
<loop_p
> loop_nest
)
534 for (var_index
= 0; loop_nest
.iterate (var_index
, &loopi
);
536 if (loopi
->num
== var
)
542 /* Returns true when the data reference DR the form "A[i] = ..."
543 with a stride equal to its unit type size. */
546 adjacent_dr_p (struct data_reference
*dr
)
548 /* If this is a bitfield store bail out. */
549 if (TREE_CODE (DR_REF (dr
)) == COMPONENT_REF
550 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr
), 1)))
554 || TREE_CODE (DR_STEP (dr
)) != INTEGER_CST
)
557 return tree_int_cst_equal (fold_unary (ABS_EXPR
, TREE_TYPE (DR_STEP (dr
)),
559 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr
))));
562 void split_constant_offset (tree
, tree
*, tree
*);
564 /* Compute the greatest common divisor of a VECTOR of SIZE numbers. */
567 lambda_vector_gcd (lambda_vector vector
, int size
)
575 for (i
= 1; i
< size
; i
++)
576 gcd1
= gcd (gcd1
, vector
[i
]);
581 /* Allocate a new vector of given SIZE. */
583 static inline lambda_vector
584 lambda_vector_new (int size
)
586 /* ??? We shouldn't abuse the GC allocator here. */
587 return ggc_cleared_vec_alloc
<int> (size
);
590 /* Clear out vector VEC1 of length SIZE. */
593 lambda_vector_clear (lambda_vector vec1
, int size
)
595 memset (vec1
, 0, size
* sizeof (*vec1
));
598 /* Returns true when the vector V is lexicographically positive, in
599 other words, when the first nonzero element is positive. */
602 lambda_vector_lexico_pos (lambda_vector v
,
606 for (i
= 0; i
< n
; i
++)
618 /* Return true if vector VEC1 of length SIZE is the zero vector. */
621 lambda_vector_zerop (lambda_vector vec1
, int size
)
624 for (i
= 0; i
< size
; i
++)
630 /* Allocate a matrix of M rows x N cols. */
632 static inline lambda_matrix
633 lambda_matrix_new (int m
, int n
, struct obstack
*lambda_obstack
)
638 mat
= XOBNEWVEC (lambda_obstack
, lambda_vector
, m
);
640 for (i
= 0; i
< m
; i
++)
641 mat
[i
] = XOBNEWVEC (lambda_obstack
, int, n
);
646 #endif /* GCC_TREE_DATA_REF_H */