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>
4
5 This file is part of GCC.
6
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
10 version.
11
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
15 for more details.
16
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
20 02110-1301, USA. */
21
22 #ifndef GCC_TREE_DATA_REF_H
23 #define GCC_TREE_DATA_REF_H
24
25 #include "lambda.h"
26
27 /** {base_address + offset + init} is the first location accessed by data-ref
28 in the loop, and step is the stride of data-ref in the loop in bytes;
29 e.g.:
30
31 Example 1 Example 2
32 data-ref a[j].b[i][j] a + x + 16B (a is int*)
33
34 First location info:
35 base_address &a a
36 offset j_0*D_j + i_0*D_i + C_a x
37 init C_b 16
38 step D_j 4
39 access_fn NULL {16, +, 1}
40
41 Base object info:
42 base_object a NULL
43 access_fn <access_fns of indexes of b> NULL
44
45 **/
46 struct first_location_in_loop
47 {
48 tree base_address;
49 tree offset;
50 tree init;
51 tree step;
52 /* Access function related to first location in the loop. */
53 VEC(tree,heap) *access_fns;
54
55 };
56
57 struct base_object_info
58 {
59 /* The object. */
60 tree base_object;
61
62 /* A list of chrecs. Access functions related to BASE_OBJECT. */
63 VEC(tree,heap) *access_fns;
64 };
65
66 enum data_ref_type {
67 ARRAY_REF_TYPE,
68 POINTER_REF_TYPE
69 };
70
71 struct data_reference
72 {
73 /* A pointer to the statement that contains this DR. */
74 tree stmt;
75
76 /* A pointer to the ARRAY_REF node. */
77 tree ref;
78
79 /* Auxiliary info specific to a pass. */
80 int aux;
81
82 /* True when the data reference is in RHS of a stmt. */
83 bool is_read;
84
85 /* First location accessed by the data-ref in the loop. */
86 struct first_location_in_loop first_location;
87
88 /* Base object related info. */
89 struct base_object_info object_info;
90
91 /* Aliasing information. This field represents the symbol that
92 should be aliased by a pointer holding the address of this data
93 reference. If the original data reference was a pointer
94 dereference, then this field contains the memory tag that should
95 be used by the new vector-pointer. */
96 tree memtag;
97 struct ptr_info_def *ptr_info;
98 subvar_t subvars;
99
100 /* Alignment information. */
101 /* The offset of the data-reference from its base in bytes. */
102 tree misalignment;
103 /* The maximum data-ref's alignment. */
104 tree aligned_to;
105
106 /* The type of the data-ref. */
107 enum data_ref_type type;
108 };
109
110 typedef struct data_reference *data_reference_p;
111 DEF_VEC_P(data_reference_p);
112 DEF_VEC_ALLOC_P (data_reference_p, heap);
113
114 #define DR_STMT(DR) (DR)->stmt
115 #define DR_REF(DR) (DR)->ref
116 #define DR_BASE_OBJECT(DR) (DR)->object_info.base_object
117 #define DR_TYPE(DR) (DR)->type
118 #define DR_ACCESS_FNS(DR)\
119 (DR_TYPE(DR) == ARRAY_REF_TYPE ? \
120 (DR)->object_info.access_fns : (DR)->first_location.access_fns)
121 #define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I)
122 #define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR))
123 #define DR_IS_READ(DR) (DR)->is_read
124 #define DR_BASE_ADDRESS(DR) (DR)->first_location.base_address
125 #define DR_OFFSET(DR) (DR)->first_location.offset
126 #define DR_INIT(DR) (DR)->first_location.init
127 #define DR_STEP(DR) (DR)->first_location.step
128 #define DR_MEMTAG(DR) (DR)->memtag
129 #define DR_ALIGNED_TO(DR) (DR)->aligned_to
130 #define DR_OFFSET_MISALIGNMENT(DR) (DR)->misalignment
131 #define DR_PTR_INFO(DR) (DR)->ptr_info
132 #define DR_SUBVARS(DR) (DR)->subvars
133
134 #define DR_ACCESS_FNS_ADDR(DR) \
135 (DR_TYPE(DR) == ARRAY_REF_TYPE ? \
136 &((DR)->object_info.access_fns) : &((DR)->first_location.access_fns))
137 #define DR_SET_ACCESS_FNS(DR, ACC_FNS) \
138 { \
139 if (DR_TYPE(DR) == ARRAY_REF_TYPE) \
140 (DR)->object_info.access_fns = ACC_FNS; \
141 else \
142 (DR)->first_location.access_fns = ACC_FNS; \
143 }
144 #define DR_FREE_ACCESS_FNS(DR) \
145 { \
146 if (DR_TYPE(DR) == ARRAY_REF_TYPE) \
147 VEC_free (tree, heap, (DR)->object_info.access_fns); \
148 else \
149 VEC_free (tree, heap, (DR)->first_location.access_fns); \
150 }
151
152 enum data_dependence_direction {
153 dir_positive,
154 dir_negative,
155 dir_equal,
156 dir_positive_or_negative,
157 dir_positive_or_equal,
158 dir_negative_or_equal,
159 dir_star,
160 dir_independent
161 };
162
163 /* What is a subscript? Given two array accesses a subscript is the
164 tuple composed of the access functions for a given dimension.
165 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
166 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts
167 are stored in the data_dependence_relation structure under the form
168 of an array of subscripts. */
169
170 struct subscript
171 {
172 /* A description of the iterations for which the elements are
173 accessed twice. */
174 tree conflicting_iterations_in_a;
175 tree conflicting_iterations_in_b;
176
177 /* This field stores the information about the iteration domain
178 validity of the dependence relation. */
179 tree last_conflict;
180
181 /* Distance from the iteration that access a conflicting element in
182 A to the iteration that access this same conflicting element in
183 B. The distance is a tree scalar expression, i.e. a constant or a
184 symbolic expression, but certainly not a chrec function. */
185 tree distance;
186 };
187
188 typedef struct subscript *subscript_p;
189 DEF_VEC_P(subscript_p);
190 DEF_VEC_ALLOC_P (subscript_p, heap);
191
192 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
193 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
194 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
195 #define SUB_DISTANCE(SUB) SUB->distance
196
197 typedef struct loop *loop_p;
198 DEF_VEC_P(loop_p);
199 DEF_VEC_ALLOC_P (loop_p, heap);
200
201 /* A data_dependence_relation represents a relation between two
202 data_references A and B. */
203
204 struct data_dependence_relation
205 {
206
207 struct data_reference *a;
208 struct data_reference *b;
209
210 /* When the dependence relation is affine, it can be represented by
211 a distance vector. */
212 bool affine_p;
213
214 /* A "yes/no/maybe" field for the dependence relation:
215
216 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
217 relation between A and B, and the description of this relation
218 is given in the SUBSCRIPTS array,
219
220 - when "ARE_DEPENDENT == chrec_known", there is no dependence and
221 SUBSCRIPTS is empty,
222
223 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
224 but the analyzer cannot be more specific. */
225 tree are_dependent;
226
227 /* For each subscript in the dependence test, there is an element in
228 this array. This is the attribute that labels the edge A->B of
229 the data_dependence_relation. */
230 VEC (subscript_p, heap) *subscripts;
231
232 /* The analyzed loop nest. */
233 VEC (loop_p, heap) *loop_nest;
234
235 /* The classic direction vector. */
236 VEC (lambda_vector, heap) *dir_vects;
237
238 /* The classic distance vector. */
239 VEC (lambda_vector, heap) *dist_vects;
240 };
241
242 typedef struct data_dependence_relation *ddr_p;
243 DEF_VEC_P(ddr_p);
244 DEF_VEC_ALLOC_P(ddr_p,heap);
245
246 #define DDR_A(DDR) DDR->a
247 #define DDR_B(DDR) DDR->b
248 #define DDR_AFFINE_P(DDR) DDR->affine_p
249 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
250 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
251 #define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
252 #define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
253
254 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
255 /* The size of the direction/distance vectors: the number of loops in
256 the loop nest. */
257 #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
258
259 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
260 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
261 #define DDR_NUM_DIST_VECTS(DDR) \
262 (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
263 #define DDR_NUM_DIR_VECTS(DDR) \
264 (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
265 #define DDR_DIR_VECT(DDR, I) \
266 VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
267 #define DDR_DIST_VECT(DDR, I) \
268 VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
269
270
271
272 extern tree find_data_references_in_loop (struct loop *,
273 VEC (data_reference_p, heap) **);
274 extern void compute_data_dependences_for_loop (struct loop *, bool,
275 VEC (data_reference_p, heap) **,
276 VEC (ddr_p, heap) **);
277 extern void print_direction_vector (FILE *, lambda_vector, int);
278 extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int);
279 extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int);
280 extern void dump_subscript (FILE *, struct subscript *);
281 extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *);
282 extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *);
283 extern void dump_data_reference (FILE *, struct data_reference *);
284 extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *);
285 extern void debug_data_dependence_relation (struct data_dependence_relation *);
286 extern void dump_data_dependence_relation (FILE *,
287 struct data_dependence_relation *);
288 extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *);
289 extern void dump_data_dependence_direction (FILE *,
290 enum data_dependence_direction);
291 extern void free_dependence_relation (struct data_dependence_relation *);
292 extern void free_dependence_relations (VEC (ddr_p, heap) *);
293 extern void free_data_refs (VEC (data_reference_p, heap) *);
294 extern struct data_reference *analyze_array (tree, tree, bool);
295 extern void estimate_iters_using_array (tree, tree);
296
297
298 /* Return the index of the variable VAR in the LOOP_NEST array. */
299
300 static inline int
index_in_loop_nest(int var,VEC (loop_p,heap)* loop_nest)301 index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
302 {
303 struct loop *loopi;
304 int var_index;
305
306 for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi);
307 var_index++)
308 if (loopi->num == var)
309 break;
310
311 return var_index;
312 }
313
314 /* In lambda-code.c */
315 bool lambda_transform_legal_p (lambda_trans_matrix, int, VEC (ddr_p, heap) *);
316
317 #endif /* GCC_TREE_DATA_REF_H */
318