1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 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
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 and the operands of INDIRECT_REFs.
64 For ARRAY_REFs, BASE_OBJECT is the reference with zeroed indices
65 (note that this reference does not have to be valid, if zero does not
66 belong to the range of the array; hence it is not recommended to use
67 BASE_OBJECT in any code generation). For INDIRECT_REFs, the address is
68 set to the loop-invariant part of the address of the object, except for
69 the constant offset. For the examples above,
71 base_object: a[0].b[0][0] *(p + x + 4B * j_0)
72 indices: {j_0, +, 1}_2 {16, +, 4}_2
82 /* A list of chrecs. Access functions of the indices. */
83 VEC(tree
,heap
) *access_fns
;
88 /* The alias information that should be used for new pointers to this
89 location. SYMBOL_TAG is either a DECL or a SYMBOL_MEMORY_TAG. */
91 struct ptr_info_def
*ptr_info
;
93 /* The set of virtual operands corresponding to this memory reference,
94 serving as a description of the alias information for the memory
95 reference. This could be eliminated if we had alias oracle. */
99 typedef struct scop
*scop_p
;
101 /* Each vector of the access matrix represents a linear access
102 function for a subscript. First elements correspond to the
103 leftmost indices, ie. for a[i][j] the first vector corresponds to
104 the subscript in "i". The elements of a vector are relative to
105 the loop nests in which the data reference is considered,
106 i.e. the vector is relative to the SCoP that provides the context
107 in which this data reference occurs.
115 if "i" varies in loop_1 and "j" varies in loop_2, the access
116 matrix with respect to the loop nest {loop_1, loop_2} is:
118 | loop_1 loop_2 param_n cst
122 whereas the access matrix with respect to loop_2 considers "i" as
125 | loop_2 param_i param_n cst
131 VEC (loop_p
, heap
) *loop_nest
;
132 int nb_induction_vars
;
133 VEC (tree
, heap
) *parameters
;
134 VEC (lambda_vector
, heap
) *matrix
;
137 #define AM_LOOP_NEST(M) (M)->loop_nest
138 #define AM_NB_INDUCTION_VARS(M) (M)->nb_induction_vars
139 #define AM_PARAMETERS(M) (M)->parameters
140 #define AM_MATRIX(M) (M)->matrix
141 #define AM_NB_PARAMETERS(M) (VEC_length (tree, AM_PARAMETERS(M)))
142 #define AM_CONST_COLUMN_INDEX(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M))
143 #define AM_NB_COLUMNS(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M) + 1)
144 #define AM_GET_SUBSCRIPT_ACCESS_VECTOR(M, I) VEC_index (lambda_vector, AM_MATRIX (M), I)
145 #define AM_GET_ACCESS_MATRIX_ELEMENT(M, I, J) AM_GET_SUBSCRIPT_ACCESS_VECTOR (M, I)[J]
147 /* Return the column in the access matrix of LOOP_NUM. */
150 am_vector_index_for_loop (struct access_matrix
*access_matrix
, int loop_num
)
155 for (i
= 0; VEC_iterate (loop_p
, AM_LOOP_NEST (access_matrix
), i
, l
); i
++)
156 if (l
->num
== loop_num
)
162 int access_matrix_get_index_for_parameter (tree
, struct access_matrix
*);
164 struct data_reference
166 /* A pointer to the statement that contains this DR. */
169 /* A pointer to the memory reference. */
172 /* Auxiliary info specific to a pass. */
175 /* True when the data reference is in RHS of a stmt. */
178 /* Behavior of the memory reference in the innermost loop. */
179 struct innermost_loop_behavior innermost
;
181 /* Subscripts of this data reference. */
182 struct indices indices
;
184 /* Alias information for the data reference. */
185 struct dr_alias alias
;
187 /* The SCoP in which the data reference was analyzed. */
190 /* Matrix representation for the data access functions. */
191 struct access_matrix
*access_matrix
;
194 #define DR_SCOP(DR) (DR)->scop
195 #define DR_STMT(DR) (DR)->stmt
196 #define DR_REF(DR) (DR)->ref
197 #define DR_BASE_OBJECT(DR) (DR)->indices.base_object
198 #define DR_ACCESS_FNS(DR) (DR)->indices.access_fns
199 #define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I)
200 #define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR))
201 #define DR_IS_READ(DR) (DR)->is_read
202 #define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address
203 #define DR_OFFSET(DR) (DR)->innermost.offset
204 #define DR_INIT(DR) (DR)->innermost.init
205 #define DR_STEP(DR) (DR)->innermost.step
206 #define DR_SYMBOL_TAG(DR) (DR)->alias.symbol_tag
207 #define DR_PTR_INFO(DR) (DR)->alias.ptr_info
208 #define DR_VOPS(DR) (DR)->alias.vops
209 #define DR_ALIGNED_TO(DR) (DR)->innermost.aligned_to
210 #define DR_ACCESS_MATRIX(DR) (DR)->access_matrix
212 typedef struct data_reference
*data_reference_p
;
213 DEF_VEC_P(data_reference_p
);
214 DEF_VEC_ALLOC_P (data_reference_p
, heap
);
216 enum data_dependence_direction
{
220 dir_positive_or_negative
,
221 dir_positive_or_equal
,
222 dir_negative_or_equal
,
227 /* The description of the grid of iterations that overlap. At most
228 two loops are considered at the same time just now, hence at most
229 two functions are needed. For each of the functions, we store
230 the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
231 where x, y, ... are variables. */
235 /* Special values of N. */
236 #define NO_DEPENDENCE 0
237 #define NOT_KNOWN (MAX_DIM + 1)
238 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
239 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
240 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
242 typedef VEC (tree
, heap
) *affine_fn
;
247 affine_fn fns
[MAX_DIM
];
250 /* What is a subscript? Given two array accesses a subscript is the
251 tuple composed of the access functions for a given dimension.
252 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
253 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts
254 are stored in the data_dependence_relation structure under the form
255 of an array of subscripts. */
259 /* A description of the iterations for which the elements are
261 conflict_function
*conflicting_iterations_in_a
;
262 conflict_function
*conflicting_iterations_in_b
;
264 /* This field stores the information about the iteration domain
265 validity of the dependence relation. */
268 /* Distance from the iteration that access a conflicting element in
269 A to the iteration that access this same conflicting element in
270 B. The distance is a tree scalar expression, i.e. a constant or a
271 symbolic expression, but certainly not a chrec function. */
275 typedef struct subscript
*subscript_p
;
276 DEF_VEC_P(subscript_p
);
277 DEF_VEC_ALLOC_P (subscript_p
, heap
);
279 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
280 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
281 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
282 #define SUB_DISTANCE(SUB) SUB->distance
284 /* A data_dependence_relation represents a relation between two
285 data_references A and B. */
287 struct data_dependence_relation
290 struct data_reference
*a
;
291 struct data_reference
*b
;
293 /* When the dependence relation is affine, it can be represented by
294 a distance vector. */
297 /* Set to true when the dependence relation is on the same data
299 bool self_reference_p
;
301 /* A "yes/no/maybe" field for the dependence relation:
303 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
304 relation between A and B, and the description of this relation
305 is given in the SUBSCRIPTS array,
307 - when "ARE_DEPENDENT == chrec_known", there is no dependence and
310 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
311 but the analyzer cannot be more specific. */
314 /* For each subscript in the dependence test, there is an element in
315 this array. This is the attribute that labels the edge A->B of
316 the data_dependence_relation. */
317 VEC (subscript_p
, heap
) *subscripts
;
319 /* The analyzed loop nest. */
320 VEC (loop_p
, heap
) *loop_nest
;
322 /* An index in loop_nest for the innermost loop that varies for
323 this data dependence relation. */
326 /* The classic direction vector. */
327 VEC (lambda_vector
, heap
) *dir_vects
;
329 /* The classic distance vector. */
330 VEC (lambda_vector
, heap
) *dist_vects
;
332 /* Is the dependence reversed with respect to the lexicographic order? */
336 typedef struct data_dependence_relation
*ddr_p
;
338 DEF_VEC_ALLOC_P(ddr_p
,heap
);
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) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
346 #define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
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) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
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 (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
359 #define DDR_NUM_DIR_VECTS(DDR) \
360 (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
361 #define DDR_DIR_VECT(DDR, I) \
362 VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
363 #define DDR_DIST_VECT(DDR, I) \
364 VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
365 #define DDR_REVERSED_P(DDR) DDR->reversed_p
369 /* Describes a location of a memory reference. */
371 typedef struct data_ref_loc_d
373 /* Position of the memory reference. */
376 /* True if the memory reference is read. */
380 DEF_VEC_O (data_ref_loc
);
381 DEF_VEC_ALLOC_O (data_ref_loc
, heap
);
383 bool get_references_in_stmt (gimple
, VEC (data_ref_loc
, heap
) **);
384 bool dr_analyze_innermost (struct data_reference
*);
385 extern bool compute_data_dependences_for_loop (struct loop
*, bool,
386 VEC (data_reference_p
, heap
) **,
387 VEC (ddr_p
, heap
) **);
388 extern tree
find_data_references_in_loop (struct loop
*,
389 VEC (data_reference_p
, heap
) **);
390 extern void print_direction_vector (FILE *, lambda_vector
, int);
391 extern void print_dir_vectors (FILE *, VEC (lambda_vector
, heap
) *, int);
392 extern void print_dist_vectors (FILE *, VEC (lambda_vector
, heap
) *, int);
393 extern void dump_subscript (FILE *, struct subscript
*);
394 extern void dump_ddrs (FILE *, VEC (ddr_p
, heap
) *);
395 extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p
, heap
) *);
396 extern void dump_data_reference (FILE *, struct data_reference
*);
397 extern void dump_data_references (FILE *, VEC (data_reference_p
, heap
) *);
398 extern void debug_data_dependence_relation (struct data_dependence_relation
*);
399 extern void dump_data_dependence_relation (FILE *,
400 struct data_dependence_relation
*);
401 extern void dump_data_dependence_relations (FILE *, VEC (ddr_p
, heap
) *);
402 extern void debug_data_dependence_relations (VEC (ddr_p
, heap
) *);
403 extern void dump_data_dependence_direction (FILE *,
404 enum data_dependence_direction
);
405 extern void free_dependence_relation (struct data_dependence_relation
*);
406 extern void free_dependence_relations (VEC (ddr_p
, heap
) *);
407 extern void free_data_ref (data_reference_p
);
408 extern void free_data_refs (VEC (data_reference_p
, heap
) *);
409 extern bool find_data_references_in_stmt (struct loop
*, gimple
,
410 VEC (data_reference_p
, heap
) **);
411 struct data_reference
*create_data_ref (struct loop
*, tree
, gimple
, bool);
412 extern bool find_loop_nest (struct loop
*, VEC (loop_p
, heap
) **);
413 extern void compute_all_dependences (VEC (data_reference_p
, heap
) *,
414 VEC (ddr_p
, heap
) **, VEC (loop_p
, heap
) *,
417 extern void create_rdg_vertices (struct graph
*, VEC (gimple
, heap
) *);
418 extern bool dr_may_alias_p (const struct data_reference
*,
419 const struct data_reference
*);
420 extern bool stmt_simple_memref_p (struct loop
*, gimple
, tree
);
422 /* Return true when the DDR contains two data references that have the
423 same access functions. */
426 same_access_functions (const struct data_dependence_relation
*ddr
)
430 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
431 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr
), i
),
432 DR_ACCESS_FN (DDR_B (ddr
), i
)))
438 /* Return true when DDR is an anti-dependence relation. */
441 ddr_is_anti_dependent (ddr_p ddr
)
443 return (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
444 && DR_IS_READ (DDR_A (ddr
))
445 && !DR_IS_READ (DDR_B (ddr
))
446 && !same_access_functions (ddr
));
449 /* Return true when DEPENDENCE_RELATIONS contains an anti-dependence. */
452 ddrs_have_anti_deps (VEC (ddr_p
, heap
) *dependence_relations
)
457 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
458 if (ddr_is_anti_dependent (ddr
))
464 /* Return the dependence level for the DDR relation. */
466 static inline unsigned
467 ddr_dependence_level (ddr_p ddr
)
472 if (DDR_DIST_VECTS (ddr
))
473 level
= dependence_level (DDR_DIST_VECT (ddr
, 0), DDR_NB_LOOPS (ddr
));
475 for (vector
= 1; vector
< DDR_NUM_DIST_VECTS (ddr
); vector
++)
476 level
= MIN (level
, dependence_level (DDR_DIST_VECT (ddr
, vector
),
477 DDR_NB_LOOPS (ddr
)));
483 /* A Reduced Dependence Graph (RDG) vertex representing a statement. */
484 typedef struct rdg_vertex
486 /* The statement represented by this vertex. */
489 /* True when the statement contains a write to memory. */
492 /* True when the statement contains a read from memory. */
496 #define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
497 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
498 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
499 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
500 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
501 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
503 void dump_rdg_vertex (FILE *, struct graph
*, int);
504 void debug_rdg_vertex (struct graph
*, int);
505 void dump_rdg_component (FILE *, struct graph
*, int, bitmap
);
506 void debug_rdg_component (struct graph
*, int);
507 void dump_rdg (FILE *, struct graph
*);
508 void debug_rdg (struct graph
*);
509 void dot_rdg (struct graph
*);
510 int rdg_vertex_for_stmt (struct graph
*, gimple
);
512 /* Data dependence type. */
516 /* Read After Write (RAW). */
519 /* Write After Read (WAR). */
522 /* Write After Write (WAW). */
525 /* Read After Read (RAR). */
529 /* Dependence information attached to an edge of the RDG. */
531 typedef struct rdg_edge
533 /* Type of the dependence. */
534 enum rdg_dep_type type
;
536 /* Levels of the dependence: the depth of the loops that carry the
540 /* Dependence relation between data dependences, NULL when one of
541 the vertices is a scalar. */
545 #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
546 #define RDGE_LEVEL(E) ((struct rdg_edge *) ((E)->data))->level
547 #define RDGE_RELATION(E) ((struct rdg_edge *) ((E)->data))->relation
549 struct graph
*build_rdg (struct loop
*);
550 struct graph
*build_empty_rdg (int);
551 void free_rdg (struct graph
*);
553 /* Return the index of the variable VAR in the LOOP_NEST array. */
556 index_in_loop_nest (int var
, VEC (loop_p
, heap
) *loop_nest
)
561 for (var_index
= 0; VEC_iterate (loop_p
, loop_nest
, var_index
, loopi
);
563 if (loopi
->num
== var
)
569 void stores_from_loop (struct loop
*, VEC (gimple
, heap
) **);
570 void remove_similar_memory_refs (VEC (gimple
, heap
) **);
571 bool rdg_defs_used_in_other_loops_p (struct graph
*, int);
572 bool have_similar_memory_accesses (gimple
, gimple
);
574 /* Determines whether RDG vertices V1 and V2 access to similar memory
575 locations, in which case they have to be in the same partition. */
578 rdg_has_similar_memory_accesses (struct graph
*rdg
, int v1
, int v2
)
580 return have_similar_memory_accesses (RDG_STMT (rdg
, v1
),
584 /* In lambda-code.c */
585 bool lambda_transform_legal_p (lambda_trans_matrix
, int,
586 VEC (ddr_p
, heap
) *);
587 void lambda_collect_parameters (VEC (data_reference_p
, heap
) *,
588 VEC (tree
, heap
) **);
589 bool lambda_compute_access_matrices (VEC (data_reference_p
, heap
) *,
590 VEC (tree
, heap
) *, VEC (loop_p
, heap
) *);
592 /* In tree-data-ref.c */
593 void split_constant_offset (tree
, tree
*, tree
*);
595 /* Strongly connected components of the reduced data dependence graph. */
597 typedef struct rdg_component
600 VEC (int, heap
) *vertices
;
604 DEF_VEC_ALLOC_P (rdgc
, heap
);
607 DEF_VEC_ALLOC_P (bitmap
, heap
);
609 #endif /* GCC_TREE_DATA_REF_H */