1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006 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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 #ifndef GCC_TREE_DATA_REF_H
23 #define GCC_TREE_DATA_REF_H
28 The first location accessed by data-ref in the loop is the address of data-ref's
29 base (BASE_ADDRESS) plus the initial offset from the base. We divide the initial offset
30 into two parts: loop invariant offset (OFFSET) and constant offset (INIT).
31 STEP is the stride of data-ref in the loop in bytes.
34 data-ref a[j].b[i][j] a + x + 16B (a is int*)
38 offset j_0*D_j + i_0*D_i x
41 access_fn NULL {16, +, 1}
45 access_fn <access_fns of indexes of b> NULL
48 struct first_location_in_loop
54 /* Access function related to first location in the loop. */
55 VEC(tree
,heap
) *access_fns
;
58 struct base_object_info
63 /* A list of chrecs. Access functions related to BASE_OBJECT. */
64 VEC(tree
,heap
) *access_fns
;
74 /* A pointer to the statement that contains this DR. */
77 /* A pointer to the ARRAY_REF node. */
80 /* Auxiliary info specific to a pass. */
83 /* True when the data reference is in RHS of a stmt. */
86 /* First location accessed by the data-ref in the loop. */
87 struct first_location_in_loop first_location
;
89 /* Base object related info. */
90 struct base_object_info object_info
;
92 /* Aliasing information. This field represents the symbol that
93 should be aliased by a pointer holding the address of this data
94 reference. If the original data reference was a pointer
95 dereference, then this field contains the memory tag that should
96 be used by the new vector-pointer. */
98 struct ptr_info_def
*ptr_info
;
101 /* Alignment information.
102 MISALIGNMENT is the offset of the data-reference from its base in bytes.
103 ALIGNED_TO is the maximum data-ref's alignment.
107 for (j = 3; j < N; j++)
110 For a[j].b[i][j], the offset from base (calculated in get_inner_reference()
111 will be 'i * C_i + j * C_j + C'.
112 We try to substitute the variables of the offset expression
113 with initial_condition of the corresponding access_fn in the loop.
114 'i' cannot be substituted, since its access_fn in the inner loop is i. 'j'
115 will be substituted with 3.
118 for (j = 3; j < N; j++)
121 Here the offset expression (j * C_j + C) will not contain variables after
122 subsitution of j=3 (3*C_j + C).
124 Misalignment can be calculated only if all the variables can be
125 substituted with constants, otherwise, we record maximum possible alignment
126 in ALIGNED_TO. In Example 1, since 'i' cannot be substituted,
127 MISALIGNMENT will be NULL_TREE, and the biggest divider of C_i (a power of
128 2) will be recorded in ALIGNED_TO.
130 In Example 2, MISALIGNMENT will be the value of 3*C_j + C in bytes, and
131 ALIGNED_TO will be NULL_TREE.
136 /* The type of the data-ref. */
137 enum data_ref_type type
;
140 typedef struct data_reference
*data_reference_p
;
141 DEF_VEC_P(data_reference_p
);
142 DEF_VEC_ALLOC_P (data_reference_p
, heap
);
144 #define DR_STMT(DR) (DR)->stmt
145 #define DR_REF(DR) (DR)->ref
146 #define DR_BASE_OBJECT(DR) (DR)->object_info.base_object
147 #define DR_TYPE(DR) (DR)->type
148 #define DR_ACCESS_FNS(DR)\
149 (DR_TYPE(DR) == ARRAY_REF_TYPE ? \
150 (DR)->object_info.access_fns : (DR)->first_location.access_fns)
151 #define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I)
152 #define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR))
153 #define DR_IS_READ(DR) (DR)->is_read
154 #define DR_BASE_ADDRESS(DR) (DR)->first_location.base_address
155 #define DR_OFFSET(DR) (DR)->first_location.offset
156 #define DR_INIT(DR) (DR)->first_location.init
157 #define DR_STEP(DR) (DR)->first_location.step
158 #define DR_MEMTAG(DR) (DR)->memtag
159 #define DR_ALIGNED_TO(DR) (DR)->aligned_to
160 #define DR_OFFSET_MISALIGNMENT(DR) (DR)->misalignment
161 #define DR_PTR_INFO(DR) (DR)->ptr_info
162 #define DR_SUBVARS(DR) (DR)->subvars
164 #define DR_ACCESS_FNS_ADDR(DR) \
165 (DR_TYPE(DR) == ARRAY_REF_TYPE ? \
166 &((DR)->object_info.access_fns) : &((DR)->first_location.access_fns))
167 #define DR_SET_ACCESS_FNS(DR, ACC_FNS) \
169 if (DR_TYPE(DR) == ARRAY_REF_TYPE) \
170 (DR)->object_info.access_fns = ACC_FNS; \
172 (DR)->first_location.access_fns = ACC_FNS; \
174 #define DR_FREE_ACCESS_FNS(DR) \
176 if (DR_TYPE(DR) == ARRAY_REF_TYPE) \
177 VEC_free (tree, heap, (DR)->object_info.access_fns); \
179 VEC_free (tree, heap, (DR)->first_location.access_fns); \
182 enum data_dependence_direction
{
186 dir_positive_or_negative
,
187 dir_positive_or_equal
,
188 dir_negative_or_equal
,
193 /* What is a subscript? Given two array accesses a subscript is the
194 tuple composed of the access functions for a given dimension.
195 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
196 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts
197 are stored in the data_dependence_relation structure under the form
198 of an array of subscripts. */
202 /* A description of the iterations for which the elements are
204 tree conflicting_iterations_in_a
;
205 tree conflicting_iterations_in_b
;
207 /* This field stores the information about the iteration domain
208 validity of the dependence relation. */
211 /* Distance from the iteration that access a conflicting element in
212 A to the iteration that access this same conflicting element in
213 B. The distance is a tree scalar expression, i.e. a constant or a
214 symbolic expression, but certainly not a chrec function. */
218 typedef struct subscript
*subscript_p
;
219 DEF_VEC_P(subscript_p
);
220 DEF_VEC_ALLOC_P (subscript_p
, heap
);
222 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
223 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
224 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
225 #define SUB_DISTANCE(SUB) SUB->distance
227 typedef struct loop
*loop_p
;
229 DEF_VEC_ALLOC_P (loop_p
, heap
);
231 /* A data_dependence_relation represents a relation between two
232 data_references A and B. */
234 struct data_dependence_relation
237 struct data_reference
*a
;
238 struct data_reference
*b
;
240 /* When the dependence relation is affine, it can be represented by
241 a distance vector. */
244 /* A "yes/no/maybe" field for the dependence relation:
246 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
247 relation between A and B, and the description of this relation
248 is given in the SUBSCRIPTS array,
250 - when "ARE_DEPENDENT == chrec_known", there is no dependence and
253 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
254 but the analyzer cannot be more specific. */
257 /* For each subscript in the dependence test, there is an element in
258 this array. This is the attribute that labels the edge A->B of
259 the data_dependence_relation. */
260 VEC (subscript_p
, heap
) *subscripts
;
262 /* The analyzed loop nest. */
263 VEC (loop_p
, heap
) *loop_nest
;
265 /* The classic direction vector. */
266 VEC (lambda_vector
, heap
) *dir_vects
;
268 /* The classic distance vector. */
269 VEC (lambda_vector
, heap
) *dist_vects
;
272 typedef struct data_dependence_relation
*ddr_p
;
274 DEF_VEC_ALLOC_P(ddr_p
,heap
);
276 #define DDR_A(DDR) DDR->a
277 #define DDR_B(DDR) DDR->b
278 #define DDR_AFFINE_P(DDR) DDR->affine_p
279 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
280 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
281 #define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
282 #define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
284 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
285 /* The size of the direction/distance vectors: the number of loops in
287 #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
289 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
290 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
291 #define DDR_NUM_DIST_VECTS(DDR) \
292 (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
293 #define DDR_NUM_DIR_VECTS(DDR) \
294 (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
295 #define DDR_DIR_VECT(DDR, I) \
296 VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
297 #define DDR_DIST_VECT(DDR, I) \
298 VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
302 /* Describes a location of a memory reference. */
304 typedef struct data_ref_loc_d
306 /* Position of the memory reference. */
309 /* True if the memory reference is read. */
313 DEF_VEC_O (data_ref_loc
);
314 DEF_VEC_ALLOC_O (data_ref_loc
, heap
);
316 bool get_references_in_stmt (tree
, VEC (data_ref_loc
, heap
) **);
317 extern tree
find_data_references_in_loop (struct loop
*,
318 VEC (data_reference_p
, heap
) **);
319 extern void compute_data_dependences_for_loop (struct loop
*, bool,
320 VEC (data_reference_p
, heap
) **,
321 VEC (ddr_p
, heap
) **);
322 extern void print_direction_vector (FILE *, lambda_vector
, int);
323 extern void print_dir_vectors (FILE *, VEC (lambda_vector
, heap
) *, int);
324 extern void print_dist_vectors (FILE *, VEC (lambda_vector
, heap
) *, int);
325 extern void dump_subscript (FILE *, struct subscript
*);
326 extern void dump_ddrs (FILE *, VEC (ddr_p
, heap
) *);
327 extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p
, heap
) *);
328 extern void dump_data_reference (FILE *, struct data_reference
*);
329 extern void dump_data_references (FILE *, VEC (data_reference_p
, heap
) *);
330 extern void debug_data_dependence_relation (struct data_dependence_relation
*);
331 extern void dump_data_dependence_relation (FILE *,
332 struct data_dependence_relation
*);
333 extern void dump_data_dependence_relations (FILE *, VEC (ddr_p
, heap
) *);
334 extern void dump_data_dependence_direction (FILE *,
335 enum data_dependence_direction
);
336 extern void free_dependence_relation (struct data_dependence_relation
*);
337 extern void free_dependence_relations (VEC (ddr_p
, heap
) *);
338 extern void free_data_refs (VEC (data_reference_p
, heap
) *);
339 extern struct data_reference
*analyze_array (tree
, tree
, bool);
342 /* Return the index of the variable VAR in the LOOP_NEST array. */
345 index_in_loop_nest (int var
, VEC (loop_p
, heap
) *loop_nest
)
350 for (var_index
= 0; VEC_iterate (loop_p
, loop_nest
, var_index
, loopi
);
352 if (loopi
->num
== var
)
358 /* In lambda-code.c */
359 bool lambda_transform_legal_p (lambda_trans_matrix
, int, VEC (ddr_p
, heap
) *);
361 #endif /* GCC_TREE_DATA_REF_H */