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
26 /** {base_address + offset + init} is the first location accessed by data-ref
27 in the loop, and step is the stride of data-ref in the loop in bytes;
31 data-ref a[j].b[i][j] a + x + 16B (a is int*)
35 offset j_0*D_j + i_0*D_i + C_a x
38 access_fn NULL {16, +, 1}
42 access_fn <access_fns of indexes of b> NULL
45 struct first_location_in_loop
51 /* Access function related to first location in the loop. */
52 VEC(tree
,heap
) *access_fns
;
56 struct base_object_info
61 /* A list of chrecs. Access functions related to BASE_OBJECT. */
62 VEC(tree
,heap
) *access_fns
;
72 /* A pointer to the statement that contains this DR. */
75 /* A pointer to the ARRAY_REF node. */
78 /* Auxiliary info specific to a pass. */
81 /* True when the data reference is in RHS of a stmt. */
84 /* First location accessed by the data-ref in the loop. */
85 struct first_location_in_loop first_location
;
87 /* Base object related info. */
88 struct base_object_info object_info
;
90 /* Aliasing information. This field represents the symbol that
91 should be aliased by a pointer holding the address of this data
92 reference. If the original data reference was a pointer
93 dereference, then this field contains the memory tag that should
94 be used by the new vector-pointer. */
96 struct ptr_info_def
*ptr_info
;
99 /* Alignment information. */
100 /* The offset of the data-reference from its base in bytes. */
102 /* The maximum data-ref's alignment. */
105 /* The type of the data-ref. */
106 enum data_ref_type type
;
109 typedef struct data_reference
*data_reference_p
;
110 DEF_VEC_P(data_reference_p
);
111 DEF_VEC_ALLOC_P (data_reference_p
, heap
);
113 #define DR_STMT(DR) (DR)->stmt
114 #define DR_REF(DR) (DR)->ref
115 #define DR_BASE_OBJECT(DR) (DR)->object_info.base_object
116 #define DR_TYPE(DR) (DR)->type
117 #define DR_ACCESS_FNS(DR)\
118 (DR_TYPE(DR) == ARRAY_REF_TYPE ? \
119 (DR)->object_info.access_fns : (DR)->first_location.access_fns)
120 #define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I)
121 #define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR))
122 #define DR_IS_READ(DR) (DR)->is_read
123 #define DR_BASE_ADDRESS(DR) (DR)->first_location.base_address
124 #define DR_OFFSET(DR) (DR)->first_location.offset
125 #define DR_INIT(DR) (DR)->first_location.init
126 #define DR_STEP(DR) (DR)->first_location.step
127 #define DR_MEMTAG(DR) (DR)->memtag
128 #define DR_ALIGNED_TO(DR) (DR)->aligned_to
129 #define DR_OFFSET_MISALIGNMENT(DR) (DR)->misalignment
130 #define DR_PTR_INFO(DR) (DR)->ptr_info
131 #define DR_SUBVARS(DR) (DR)->subvars
133 #define DR_ACCESS_FNS_ADDR(DR) \
134 (DR_TYPE(DR) == ARRAY_REF_TYPE ? \
135 &((DR)->object_info.access_fns) : &((DR)->first_location.access_fns))
136 #define DR_SET_ACCESS_FNS(DR, ACC_FNS) \
138 if (DR_TYPE(DR) == ARRAY_REF_TYPE) \
139 (DR)->object_info.access_fns = ACC_FNS; \
141 (DR)->first_location.access_fns = ACC_FNS; \
143 #define DR_FREE_ACCESS_FNS(DR) \
145 if (DR_TYPE(DR) == ARRAY_REF_TYPE) \
146 VEC_free (tree, heap, (DR)->object_info.access_fns); \
148 VEC_free (tree, heap, (DR)->first_location.access_fns); \
151 enum data_dependence_direction
{
155 dir_positive_or_negative
,
156 dir_positive_or_equal
,
157 dir_negative_or_equal
,
162 /* What is a subscript? Given two array accesses a subscript is the
163 tuple composed of the access functions for a given dimension.
164 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
165 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts
166 are stored in the data_dependence_relation structure under the form
167 of an array of subscripts. */
171 /* A description of the iterations for which the elements are
173 tree conflicting_iterations_in_a
;
174 tree conflicting_iterations_in_b
;
176 /* This field stores the information about the iteration domain
177 validity of the dependence relation. */
180 /* Distance from the iteration that access a conflicting element in
181 A to the iteration that access this same conflicting element in
182 B. The distance is a tree scalar expression, i.e. a constant or a
183 symbolic expression, but certainly not a chrec function. */
187 typedef struct subscript
*subscript_p
;
188 DEF_VEC_P(subscript_p
);
189 DEF_VEC_ALLOC_P (subscript_p
, heap
);
191 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
192 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
193 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
194 #define SUB_DISTANCE(SUB) SUB->distance
196 typedef struct loop
*loop_p
;
198 DEF_VEC_ALLOC_P (loop_p
, heap
);
200 /* A data_dependence_relation represents a relation between two
201 data_references A and B. */
203 struct data_dependence_relation
206 struct data_reference
*a
;
207 struct data_reference
*b
;
209 /* When the dependence relation is affine, it can be represented by
210 a distance vector. */
213 /* A "yes/no/maybe" field for the dependence relation:
215 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
216 relation between A and B, and the description of this relation
217 is given in the SUBSCRIPTS array,
219 - when "ARE_DEPENDENT == chrec_known", there is no dependence and
222 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
223 but the analyzer cannot be more specific. */
226 /* For each subscript in the dependence test, there is an element in
227 this array. This is the attribute that labels the edge A->B of
228 the data_dependence_relation. */
229 VEC (subscript_p
, heap
) *subscripts
;
231 /* The analyzed loop nest. */
232 VEC (loop_p
, heap
) *loop_nest
;
234 /* The classic direction vector. */
235 VEC (lambda_vector
, heap
) *dir_vects
;
237 /* The classic distance vector. */
238 VEC (lambda_vector
, heap
) *dist_vects
;
241 typedef struct data_dependence_relation
*ddr_p
;
243 DEF_VEC_ALLOC_P(ddr_p
,heap
);
245 #define DDR_A(DDR) DDR->a
246 #define DDR_B(DDR) DDR->b
247 #define DDR_AFFINE_P(DDR) DDR->affine_p
248 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
249 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
250 #define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
251 #define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
253 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
254 /* The size of the direction/distance vectors: the number of loops in
256 #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
258 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
259 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
260 #define DDR_NUM_DIST_VECTS(DDR) \
261 (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
262 #define DDR_NUM_DIR_VECTS(DDR) \
263 (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
264 #define DDR_DIR_VECT(DDR, I) \
265 VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
266 #define DDR_DIST_VECT(DDR, I) \
267 VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
271 extern tree
find_data_references_in_loop (struct loop
*,
272 VEC (data_reference_p
, heap
) **);
273 extern void compute_data_dependences_for_loop (struct loop
*, bool,
274 VEC (data_reference_p
, heap
) **,
275 VEC (ddr_p
, heap
) **);
276 extern void print_direction_vector (FILE *, lambda_vector
, int);
277 extern void print_dir_vectors (FILE *, VEC (lambda_vector
, heap
) *, int);
278 extern void print_dist_vectors (FILE *, VEC (lambda_vector
, heap
) *, int);
279 extern void dump_subscript (FILE *, struct subscript
*);
280 extern void dump_ddrs (FILE *, VEC (ddr_p
, heap
) *);
281 extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p
, heap
) *);
282 extern void dump_data_reference (FILE *, struct data_reference
*);
283 extern void dump_data_references (FILE *, VEC (data_reference_p
, heap
) *);
284 extern void debug_data_dependence_relation (struct data_dependence_relation
*);
285 extern void dump_data_dependence_relation (FILE *,
286 struct data_dependence_relation
*);
287 extern void dump_data_dependence_relations (FILE *, VEC (ddr_p
, heap
) *);
288 extern void dump_data_dependence_direction (FILE *,
289 enum data_dependence_direction
);
290 extern void free_dependence_relation (struct data_dependence_relation
*);
291 extern void free_dependence_relations (VEC (ddr_p
, heap
) *);
292 extern void free_data_refs (VEC (data_reference_p
, heap
) *);
293 extern struct data_reference
*analyze_array (tree
, tree
, bool);
294 extern void estimate_iters_using_array (tree
, tree
);
297 /* Return the index of the variable VAR in the LOOP_NEST array. */
300 index_in_loop_nest (int var
, VEC (loop_p
, heap
) *loop_nest
)
305 for (var_index
= 0; VEC_iterate (loop_p
, loop_nest
, var_index
, loopi
);
307 if (loopi
->num
== var
)
313 /* In lambda-code.c */
314 bool lambda_transform_legal_p (lambda_trans_matrix
, int, VEC (ddr_p
, heap
) *);
316 #endif /* GCC_TREE_DATA_REF_H */