1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 #ifndef GCC_TREE_DATA_REF_H
23 #define GCC_TREE_DATA_REF_H
27 #include "tree-chrec.h"
30 innermost_loop_behavior describes the evolution of the address of the memory
31 reference in the innermost enclosing loop. The address is expressed as
32 BASE + STEP * # of iteration, and base is further decomposed as the base
33 pointer (BASE_ADDRESS), loop invariant offset (OFFSET) and
34 constant offset (INIT). Examples, in loop nest
36 for (i = 0; i < 100; i++)
37 for (j = 3; j < 100; j++)
40 data-ref a[j].b[i][j] *(p + x + 16B + 4B * j)
43 innermost_loop_behavior
46 init 3 * D_j + offsetof (b) 28
50 struct innermost_loop_behavior
57 /* Alignment information. ALIGNED_TO is set to the largest power of two
58 that divides OFFSET. */
62 /* Describes the evolutions of indices of the memory reference. The indices
63 are indices of the ARRAY_REFs, indexes in artificial dimensions
64 added for member selection of records and the operands of MEM_REFs.
65 BASE_OBJECT is the part of the reference that is loop-invariant
66 (note that this reference does not have to cover the whole object
67 being accessed, in which case UNCONSTRAINED_BASE is set; hence it is
68 not recommended to use BASE_OBJECT in any code generation).
69 For the examples above,
71 base_object: a *(p + x + 4B * j_0)
72 indices: {j_0, +, 1}_2 {16, +, 4}_2
83 /* A list of chrecs. Access functions of the indices. */
84 VEC(tree,heap) *access_fns;
86 /* Whether BASE_OBJECT is an access representing the whole object
87 or whether the access could not be constrained. */
88 bool unconstrained_base;
93 /* The alias information that should be used for new pointers to this
95 struct ptr_info_def *ptr_info;
98 /* An integer vector. A vector formally consists of an element of a vector
99 space. A vector space is a set that is closed under vector addition
100 and scalar multiplication. In this vector space, an element is a list of
102 typedef int *lambda_vector;
103 DEF_VEC_P(lambda_vector);
104 DEF_VEC_ALLOC_P(lambda_vector,heap);
105 DEF_VEC_ALLOC_P(lambda_vector,gc);
107 /* An integer matrix. A matrix consists of m vectors of length n (IE
108 all vectors are the same length). */
109 typedef lambda_vector *lambda_matrix;
111 /* Each vector of the access matrix represents a linear access
112 function for a subscript. First elements correspond to the
113 leftmost indices, ie. for a[i][j] the first vector corresponds to
114 the subscript in "i". The elements of a vector are relative to
115 the loop nests in which the data reference is considered,
116 i.e. the vector is relative to the SCoP that provides the context
117 in which this data reference occurs.
125 if "i" varies in loop_1 and "j" varies in loop_2, the access
126 matrix with respect to the loop nest {loop_1, loop_2} is:
128 | loop_1 loop_2 param_n cst
132 whereas the access matrix with respect to loop_2 considers "i" as
135 | loop_2 param_i param_n cst
141 VEC (loop_p, heap) *loop_nest;
142 int nb_induction_vars;
143 VEC (tree, heap) *parameters;
144 VEC (lambda_vector, gc) *matrix;
147 #define AM_LOOP_NEST(M) (M)->loop_nest
148 #define AM_NB_INDUCTION_VARS(M) (M)->nb_induction_vars
149 #define AM_PARAMETERS(M) (M)->parameters
150 #define AM_MATRIX(M) (M)->matrix
151 #define AM_NB_PARAMETERS(M) (VEC_length (tree, AM_PARAMETERS(M)))
152 #define AM_CONST_COLUMN_INDEX(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M))
153 #define AM_NB_COLUMNS(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M) + 1)
154 #define AM_GET_SUBSCRIPT_ACCESS_VECTOR(M, I) VEC_index (lambda_vector, AM_MATRIX (M), I)
155 #define AM_GET_ACCESS_MATRIX_ELEMENT(M, I, J) AM_GET_SUBSCRIPT_ACCESS_VECTOR (M, I)[J]
157 /* Return the column in the access matrix of LOOP_NUM. */
160 am_vector_index_for_loop (struct access_matrix *access_matrix, int loop_num)
165 for (i = 0; VEC_iterate (loop_p, AM_LOOP_NEST (access_matrix), i, l); i++)
166 if (l->num == loop_num)
172 struct data_reference
174 /* A pointer to the statement that contains this DR. */
177 /* A pointer to the memory reference. */
180 /* Auxiliary info specific to a pass. */
183 /* True when the data reference is in RHS of a stmt. */
186 /* Behavior of the memory reference in the innermost loop. */
187 struct innermost_loop_behavior innermost;
189 /* Subscripts of this data reference. */
190 struct indices indices;
192 /* Alias information for the data reference. */
193 struct dr_alias alias;
195 /* Matrix representation for the data access functions. */
196 struct access_matrix *access_matrix;
199 #define DR_STMT(DR) (DR)->stmt
200 #define DR_REF(DR) (DR)->ref
201 #define DR_BASE_OBJECT(DR) (DR)->indices.base_object
202 #define DR_UNCONSTRAINED_BASE(DR) (DR)->indices.unconstrained_base
203 #define DR_ACCESS_FNS(DR) (DR)->indices.access_fns
204 #define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I)
205 #define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR))
206 #define DR_IS_READ(DR) (DR)->is_read
207 #define DR_IS_WRITE(DR) (!DR_IS_READ (DR))
208 #define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address
209 #define DR_OFFSET(DR) (DR)->innermost.offset
210 #define DR_INIT(DR) (DR)->innermost.init
211 #define DR_STEP(DR) (DR)->innermost.step
212 #define DR_PTR_INFO(DR) (DR)->alias.ptr_info
213 #define DR_ALIGNED_TO(DR) (DR)->innermost.aligned_to
214 #define DR_ACCESS_MATRIX(DR) (DR)->access_matrix
216 typedef struct data_reference *data_reference_p;
217 DEF_VEC_P(data_reference_p);
218 DEF_VEC_ALLOC_P (data_reference_p, heap);
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, heap) *affine_fn;
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;
280 DEF_VEC_P(subscript_p);
281 DEF_VEC_ALLOC_P (subscript_p, heap);
283 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
284 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
285 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
286 #define SUB_DISTANCE(SUB) SUB->distance
288 /* A data_dependence_relation represents a relation between two
289 data_references A and B. */
291 struct data_dependence_relation
294 struct data_reference *a;
295 struct data_reference *b;
297 /* A "yes/no/maybe" field for the dependence relation:
299 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
300 relation between A and B, and the description of this relation
301 is given in the SUBSCRIPTS array,
303 - when "ARE_DEPENDENT == chrec_known", there is no dependence and
306 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
307 but the analyzer cannot be more specific. */
310 /* For each subscript in the dependence test, there is an element in
311 this array. This is the attribute that labels the edge A->B of
312 the data_dependence_relation. */
313 VEC (subscript_p, heap) *subscripts;
315 /* The analyzed loop nest. */
316 VEC (loop_p, heap) *loop_nest;
318 /* The classic direction vector. */
319 VEC (lambda_vector, heap) *dir_vects;
321 /* The classic distance vector. */
322 VEC (lambda_vector, heap) *dist_vects;
324 /* An index in loop_nest for the innermost loop that varies for
325 this data dependence relation. */
328 /* Is the dependence reversed with respect to the lexicographic order? */
331 /* When the dependence relation is affine, it can be represented by
332 a distance vector. */
335 /* Set to true when the dependence relation is on the same data
337 bool self_reference_p;
340 typedef struct data_dependence_relation *ddr_p;
342 DEF_VEC_ALLOC_P(ddr_p,heap);
344 #define DDR_A(DDR) DDR->a
345 #define DDR_B(DDR) DDR->b
346 #define DDR_AFFINE_P(DDR) DDR->affine_p
347 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
348 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
349 #define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
350 #define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
352 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
353 /* The size of the direction/distance vectors: the number of loops in
355 #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
356 #define DDR_INNER_LOOP(DDR) DDR->inner_loop
357 #define DDR_SELF_REFERENCE(DDR) DDR->self_reference_p
359 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
360 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
361 #define DDR_NUM_DIST_VECTS(DDR) \
362 (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
363 #define DDR_NUM_DIR_VECTS(DDR) \
364 (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
365 #define DDR_DIR_VECT(DDR, I) \
366 VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
367 #define DDR_DIST_VECT(DDR, I) \
368 VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
369 #define DDR_REVERSED_P(DDR) DDR->reversed_p
372 bool dr_analyze_innermost (struct data_reference *, struct loop *);
373 extern bool compute_data_dependences_for_loop (struct loop *, bool,
374 VEC (loop_p, heap) **,
375 VEC (data_reference_p, heap) **,
376 VEC (ddr_p, heap) **);
377 extern bool compute_data_dependences_for_bb (basic_block, bool,
378 VEC (data_reference_p, heap) **,
379 VEC (ddr_p, heap) **);
380 extern void debug_ddrs (VEC (ddr_p, heap) *);
381 extern void dump_data_reference (FILE *, struct data_reference *);
382 extern void debug_data_reference (struct data_reference *);
383 extern void debug_data_references (VEC (data_reference_p, heap) *);
384 extern void debug_data_dependence_relation (struct data_dependence_relation *);
385 extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *);
386 extern void debug_data_dependence_relations (VEC (ddr_p, heap) *);
387 extern void free_dependence_relation (struct data_dependence_relation *);
388 extern void free_dependence_relations (VEC (ddr_p, heap) *);
389 extern void free_data_ref (data_reference_p);
390 extern void free_data_refs (VEC (data_reference_p, heap) *);
391 extern bool find_data_references_in_stmt (struct loop *, gimple,
392 VEC (data_reference_p, heap) **);
393 extern bool graphite_find_data_references_in_stmt (loop_p, loop_p, gimple,
394 VEC (data_reference_p, heap) **);
395 struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple, bool);
396 extern bool find_loop_nest (struct loop *, VEC (loop_p, heap) **);
397 extern struct data_dependence_relation *initialize_data_dependence_relation
398 (struct data_reference *, struct data_reference *, VEC (loop_p, heap) *);
399 extern void compute_self_dependence (struct data_dependence_relation *);
400 extern bool compute_all_dependences (VEC (data_reference_p, heap) *,
401 VEC (ddr_p, heap) **, VEC (loop_p, heap) *,
403 extern tree find_data_references_in_bb (struct loop *, basic_block,
404 VEC (data_reference_p, heap) **);
406 extern void create_rdg_vertices (struct graph *, VEC (gimple, heap) *);
407 extern bool dr_may_alias_p (const struct data_reference *,
408 const struct data_reference *, bool);
409 extern bool dr_equal_offsets_p (struct data_reference *,
410 struct data_reference *);
413 /* Return true when the base objects of data references A and B are
414 the same memory object. */
417 same_data_refs_base_objects (data_reference_p a, data_reference_p b)
419 return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
420 && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
423 /* Return true when the data references A and B are accessing the same
424 memory object with the same access functions. */
427 same_data_refs (data_reference_p a, data_reference_p b)
431 /* The references are exactly the same. */
432 if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
435 if (!same_data_refs_base_objects (a, b))
438 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
439 if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
445 /* Return true when the DDR contains two data references that have the
446 same access functions. */
449 same_access_functions (const struct data_dependence_relation *ddr)
453 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
454 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
455 DR_ACCESS_FN (DDR_B (ddr), i)))
461 /* Return true when DDR is an anti-dependence relation. */
464 ddr_is_anti_dependent (ddr_p ddr)
466 return (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
467 && DR_IS_READ (DDR_A (ddr))
468 && DR_IS_WRITE (DDR_B (ddr))
469 && !same_access_functions (ddr));
472 /* Return true when DEPENDENCE_RELATIONS contains an anti-dependence. */
475 ddrs_have_anti_deps (VEC (ddr_p, heap) *dependence_relations)
480 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
481 if (ddr_is_anti_dependent (ddr))
487 /* Returns the dependence level for a vector DIST of size LENGTH.
488 LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
489 to the sequence of statements, not carried by any loop. */
491 static inline unsigned
492 dependence_level (lambda_vector dist_vect, int length)
496 for (i = 0; i < length; i++)
497 if (dist_vect[i] != 0)
503 /* Return the dependence level for the DDR relation. */
505 static inline unsigned
506 ddr_dependence_level (ddr_p ddr)
511 if (DDR_DIST_VECTS (ddr))
512 level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
514 for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
515 level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
516 DDR_NB_LOOPS (ddr)));
522 /* A Reduced Dependence Graph (RDG) vertex representing a statement. */
523 typedef struct rdg_vertex
525 /* The statement represented by this vertex. */
528 /* True when the statement contains a write to memory. */
531 /* True when the statement contains a read from memory. */
535 #define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
536 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
537 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
538 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
539 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
540 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
542 void debug_rdg_vertex (struct graph *, int);
543 void debug_rdg_component (struct graph *, int);
544 void dump_rdg (FILE *, struct graph *);
545 void debug_rdg (struct graph *);
546 int rdg_vertex_for_stmt (struct graph *, gimple);
548 /* Data dependence type. */
552 /* Read After Write (RAW). */
555 /* Write After Read (WAR). */
558 /* Write After Write (WAW). */
561 /* Read After Read (RAR). */
565 /* Dependence information attached to an edge of the RDG. */
567 typedef struct rdg_edge
569 /* Type of the dependence. */
570 enum rdg_dep_type type;
572 /* Levels of the dependence: the depth of the loops that carry the
576 /* Dependence relation between data dependences, NULL when one of
577 the vertices is a scalar. */
581 #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
582 #define RDGE_LEVEL(E) ((struct rdg_edge *) ((E)->data))->level
583 #define RDGE_RELATION(E) ((struct rdg_edge *) ((E)->data))->relation
585 struct graph *build_rdg (struct loop *,
586 VEC (loop_p, heap) **,
587 VEC (ddr_p, heap) **,
588 VEC (data_reference_p, heap) **);
589 struct graph *build_empty_rdg (int);
590 void free_rdg (struct graph *);
592 /* Return the index of the variable VAR in the LOOP_NEST array. */
595 index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
600 for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi);
602 if (loopi->num == var)
608 void stores_from_loop (struct loop *, VEC (gimple, heap) **);
609 void stores_zero_from_loop (struct loop *, VEC (gimple, heap) **);
610 bool rdg_defs_used_in_other_loops_p (struct graph *, int);
611 bool have_similar_memory_accesses (gimple, gimple);
612 bool stmt_with_adjacent_zero_store_dr_p (gimple);
614 /* Returns true when STRIDE is equal in absolute value to the size of
615 the unit type of TYPE. */
618 stride_of_unit_type_p (tree stride, tree type)
620 return (TREE_CODE (stride) == INTEGER_CST
621 && tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (stride),
623 TYPE_SIZE_UNIT (type)));
626 /* Determines whether RDG vertices V1 and V2 access to similar memory
627 locations, in which case they have to be in the same partition. */
630 rdg_has_similar_memory_accesses (struct graph *rdg, int v1, int v2)
632 return have_similar_memory_accesses (RDG_STMT (rdg, v1),
636 /* In tree-data-ref.c */
637 void split_constant_offset (tree , tree *, tree *);
639 /* Strongly connected components of the reduced data dependence graph. */
641 typedef struct rdg_component
644 VEC (int, heap) *vertices;
648 DEF_VEC_ALLOC_P (rdgc, heap);
651 DEF_VEC_ALLOC_P (bitmap, heap);
653 /* Compute the greatest common divisor of a VECTOR of SIZE numbers. */
656 lambda_vector_gcd (lambda_vector vector, int size)
664 for (i = 1; i < size; i++)
665 gcd1 = gcd (gcd1, vector[i]);
670 /* Allocate a new vector of given SIZE. */
672 static inline lambda_vector
673 lambda_vector_new (int size)
675 return (lambda_vector) ggc_alloc_cleared_atomic (sizeof (int) * size);
678 /* Clear out vector VEC1 of length SIZE. */
681 lambda_vector_clear (lambda_vector vec1, int size)
683 memset (vec1, 0, size * sizeof (*vec1));
686 /* Returns true when the vector V is lexicographically positive, in
687 other words, when the first nonzero element is positive. */
690 lambda_vector_lexico_pos (lambda_vector v,
694 for (i = 0; i < n; i++)
706 /* Return true if vector VEC1 of length SIZE is the zero vector. */
709 lambda_vector_zerop (lambda_vector vec1, int size)
712 for (i = 0; i < size; i++)
718 /* Allocate a matrix of M rows x N cols. */
720 static inline lambda_matrix
721 lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
726 mat = (lambda_matrix) obstack_alloc (lambda_obstack,
727 sizeof (lambda_vector *) * m);
729 for (i = 0; i < m; i++)
730 mat[i] = lambda_vector_new (n);
735 #endif /* GCC_TREE_DATA_REF_H */