|
0
|
1 /* Data references and dependences detectors.
|
|
|
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
|
|
|
3 Free Software Foundation, Inc.
|
|
|
4 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
|
|
|
5
|
|
|
6 This file is part of GCC.
|
|
|
7
|
|
|
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
|
|
|
11 version.
|
|
|
12
|
|
|
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
|
|
|
16 for more details.
|
|
|
17
|
|
|
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/>. */
|
|
|
21
|
|
|
22 #ifndef GCC_TREE_DATA_REF_H
|
|
|
23 #define GCC_TREE_DATA_REF_H
|
|
|
24
|
|
|
25 #include "graphds.h"
|
|
|
26 #include "lambda.h"
|
|
|
27 #include "omega.h"
|
|
|
28 #include "tree-chrec.h"
|
|
|
29
|
|
|
30 /*
|
|
|
31 innermost_loop_behavior describes the evolution of the address of the memory
|
|
|
32 reference in the innermost enclosing loop. The address is expressed as
|
|
|
33 BASE + STEP * # of iteration, and base is further decomposed as the base
|
|
|
34 pointer (BASE_ADDRESS), loop invariant offset (OFFSET) and
|
|
|
35 constant offset (INIT). Examples, in loop nest
|
|
|
36
|
|
|
37 for (i = 0; i < 100; i++)
|
|
|
38 for (j = 3; j < 100; j++)
|
|
|
39
|
|
|
40 Example 1 Example 2
|
|
|
41 data-ref a[j].b[i][j] *(p + x + 16B + 4B * j)
|
|
|
42
|
|
|
43
|
|
|
44 innermost_loop_behavior
|
|
|
45 base_address &a p
|
|
|
46 offset i * D_i x
|
|
|
47 init 3 * D_j + offsetof (b) 28
|
|
|
48 step D_j 4
|
|
|
49
|
|
|
50 */
|
|
|
51 struct innermost_loop_behavior
|
|
|
52 {
|
|
|
53 tree base_address;
|
|
|
54 tree offset;
|
|
|
55 tree init;
|
|
|
56 tree step;
|
|
|
57
|
|
|
58 /* Alignment information. ALIGNED_TO is set to the largest power of two
|
|
|
59 that divides OFFSET. */
|
|
|
60 tree aligned_to;
|
|
|
61 };
|
|
|
62
|
|
|
63 /* Describes the evolutions of indices of the memory reference. The indices
|
|
|
64 are indices of the ARRAY_REFs and the operands of INDIRECT_REFs.
|
|
|
65 For ARRAY_REFs, BASE_OBJECT is the reference with zeroed indices
|
|
|
66 (note that this reference does not have to be valid, if zero does not
|
|
|
67 belong to the range of the array; hence it is not recommended to use
|
|
|
68 BASE_OBJECT in any code generation). For INDIRECT_REFs, the address is
|
|
|
69 set to the loop-invariant part of the address of the object, except for
|
|
|
70 the constant offset. For the examples above,
|
|
|
71
|
|
|
72 base_object: a[0].b[0][0] *(p + x + 4B * j_0)
|
|
|
73 indices: {j_0, +, 1}_2 {16, +, 4}_2
|
|
|
74 {i_0, +, 1}_1
|
|
|
75 {j_0, +, 1}_2
|
|
|
76 */
|
|
|
77
|
|
|
78 struct indices
|
|
|
79 {
|
|
|
80 /* The object. */
|
|
|
81 tree base_object;
|
|
|
82
|
|
|
83 /* A list of chrecs. Access functions of the indices. */
|
|
|
84 VEC(tree,heap) *access_fns;
|
|
|
85 };
|
|
|
86
|
|
|
87 struct dr_alias
|
|
|
88 {
|
|
|
89 /* The alias information that should be used for new pointers to this
|
|
|
90 location. SYMBOL_TAG is either a DECL or a SYMBOL_MEMORY_TAG. */
|
|
|
91 tree symbol_tag;
|
|
|
92 struct ptr_info_def *ptr_info;
|
|
|
93
|
|
|
94 /* The set of virtual operands corresponding to this memory reference,
|
|
|
95 serving as a description of the alias information for the memory
|
|
|
96 reference. This could be eliminated if we had alias oracle. */
|
|
|
97 bitmap vops;
|
|
|
98 };
|
|
|
99
|
|
|
100 typedef struct scop *scop_p;
|
|
|
101
|
|
|
102 /* Each vector of the access matrix represents a linear access
|
|
|
103 function for a subscript. First elements correspond to the
|
|
|
104 leftmost indices, ie. for a[i][j] the first vector corresponds to
|
|
|
105 the subscript in "i". The elements of a vector are relative to
|
|
|
106 the loop nests in which the data reference is considered,
|
|
|
107 i.e. the vector is relative to the SCoP that provides the context
|
|
|
108 in which this data reference occurs.
|
|
|
109
|
|
|
110 For example, in
|
|
|
111
|
|
|
112 | loop_1
|
|
|
113 | loop_2
|
|
|
114 | a[i+3][2*j+n-1]
|
|
|
115
|
|
|
116 if "i" varies in loop_1 and "j" varies in loop_2, the access
|
|
|
117 matrix with respect to the loop nest {loop_1, loop_2} is:
|
|
|
118
|
|
|
119 | loop_1 loop_2 param_n cst
|
|
|
120 | 1 0 0 3
|
|
|
121 | 0 2 1 -1
|
|
|
122
|
|
|
123 whereas the access matrix with respect to loop_2 considers "i" as
|
|
|
124 a parameter:
|
|
|
125
|
|
|
126 | loop_2 param_i param_n cst
|
|
|
127 | 0 1 0 3
|
|
|
128 | 2 0 1 -1
|
|
|
129 */
|
|
|
130 struct access_matrix
|
|
|
131 {
|
|
|
132 VEC (loop_p, heap) *loop_nest;
|
|
|
133 int nb_induction_vars;
|
|
|
134 VEC (tree, heap) *parameters;
|
|
|
135 VEC (lambda_vector, gc) *matrix;
|
|
|
136 };
|
|
|
137
|
|
|
138 #define AM_LOOP_NEST(M) (M)->loop_nest
|
|
|
139 #define AM_NB_INDUCTION_VARS(M) (M)->nb_induction_vars
|
|
|
140 #define AM_PARAMETERS(M) (M)->parameters
|
|
|
141 #define AM_MATRIX(M) (M)->matrix
|
|
|
142 #define AM_NB_PARAMETERS(M) (VEC_length (tree, AM_PARAMETERS(M)))
|
|
|
143 #define AM_CONST_COLUMN_INDEX(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M))
|
|
|
144 #define AM_NB_COLUMNS(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M) + 1)
|
|
|
145 #define AM_GET_SUBSCRIPT_ACCESS_VECTOR(M, I) VEC_index (lambda_vector, AM_MATRIX (M), I)
|
|
|
146 #define AM_GET_ACCESS_MATRIX_ELEMENT(M, I, J) AM_GET_SUBSCRIPT_ACCESS_VECTOR (M, I)[J]
|
|
|
147
|
|
|
148 /* Return the column in the access matrix of LOOP_NUM. */
|
|
|
149
|
|
|
150 static inline int
|
|
|
151 am_vector_index_for_loop (struct access_matrix *access_matrix, int loop_num)
|
|
|
152 {
|
|
|
153 int i;
|
|
|
154 loop_p l;
|
|
|
155
|
|
|
156 for (i = 0; VEC_iterate (loop_p, AM_LOOP_NEST (access_matrix), i, l); i++)
|
|
|
157 if (l->num == loop_num)
|
|
|
158 return i;
|
|
|
159
|
|
|
160 gcc_unreachable();
|
|
|
161 }
|
|
|
162
|
|
|
163 int access_matrix_get_index_for_parameter (tree, struct access_matrix *);
|
|
|
164
|
|
|
165 struct data_reference
|
|
|
166 {
|
|
|
167 /* A pointer to the statement that contains this DR. */
|
|
|
168 gimple stmt;
|
|
|
169
|
|
|
170 /* A pointer to the memory reference. */
|
|
|
171 tree ref;
|
|
|
172
|
|
|
173 /* Auxiliary info specific to a pass. */
|
|
|
174 void *aux;
|
|
|
175
|
|
|
176 /* True when the data reference is in RHS of a stmt. */
|
|
|
177 bool is_read;
|
|
|
178
|
|
|
179 /* Behavior of the memory reference in the innermost loop. */
|
|
|
180 struct innermost_loop_behavior innermost;
|
|
|
181
|
|
|
182 /* Subscripts of this data reference. */
|
|
|
183 struct indices indices;
|
|
|
184
|
|
|
185 /* Alias information for the data reference. */
|
|
|
186 struct dr_alias alias;
|
|
|
187
|
|
|
188 /* The SCoP in which the data reference was analyzed. */
|
|
|
189 scop_p scop;
|
|
|
190
|
|
|
191 /* Matrix representation for the data access functions. */
|
|
|
192 struct access_matrix *access_matrix;
|
|
|
193 };
|
|
|
194
|
|
|
195 #define DR_SCOP(DR) (DR)->scop
|
|
|
196 #define DR_STMT(DR) (DR)->stmt
|
|
|
197 #define DR_REF(DR) (DR)->ref
|
|
|
198 #define DR_BASE_OBJECT(DR) (DR)->indices.base_object
|
|
|
199 #define DR_ACCESS_FNS(DR) (DR)->indices.access_fns
|
|
|
200 #define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I)
|
|
|
201 #define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR))
|
|
|
202 #define DR_IS_READ(DR) (DR)->is_read
|
|
|
203 #define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address
|
|
|
204 #define DR_OFFSET(DR) (DR)->innermost.offset
|
|
|
205 #define DR_INIT(DR) (DR)->innermost.init
|
|
|
206 #define DR_STEP(DR) (DR)->innermost.step
|
|
|
207 #define DR_SYMBOL_TAG(DR) (DR)->alias.symbol_tag
|
|
|
208 #define DR_PTR_INFO(DR) (DR)->alias.ptr_info
|
|
|
209 #define DR_VOPS(DR) (DR)->alias.vops
|
|
|
210 #define DR_ALIGNED_TO(DR) (DR)->innermost.aligned_to
|
|
|
211 #define DR_ACCESS_MATRIX(DR) (DR)->access_matrix
|
|
|
212
|
|
|
213 typedef struct data_reference *data_reference_p;
|
|
|
214 DEF_VEC_P(data_reference_p);
|
|
|
215 DEF_VEC_ALLOC_P (data_reference_p, heap);
|
|
|
216
|
|
|
217 enum data_dependence_direction {
|
|
|
218 dir_positive,
|
|
|
219 dir_negative,
|
|
|
220 dir_equal,
|
|
|
221 dir_positive_or_negative,
|
|
|
222 dir_positive_or_equal,
|
|
|
223 dir_negative_or_equal,
|
|
|
224 dir_star,
|
|
|
225 dir_independent
|
|
|
226 };
|
|
|
227
|
|
|
228 /* The description of the grid of iterations that overlap. At most
|
|
|
229 two loops are considered at the same time just now, hence at most
|
|
|
230 two functions are needed. For each of the functions, we store
|
|
|
231 the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
|
|
|
232 where x, y, ... are variables. */
|
|
|
233
|
|
|
234 #define MAX_DIM 2
|
|
|
235
|
|
|
236 /* Special values of N. */
|
|
|
237 #define NO_DEPENDENCE 0
|
|
|
238 #define NOT_KNOWN (MAX_DIM + 1)
|
|
|
239 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
|
|
|
240 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
|
|
|
241 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
|
|
|
242
|
|
|
243 typedef VEC (tree, heap) *affine_fn;
|
|
|
244
|
|
|
245 typedef struct
|
|
|
246 {
|
|
|
247 unsigned n;
|
|
|
248 affine_fn fns[MAX_DIM];
|
|
|
249 } conflict_function;
|
|
|
250
|
|
|
251 /* What is a subscript? Given two array accesses a subscript is the
|
|
|
252 tuple composed of the access functions for a given dimension.
|
|
|
253 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
|
|
|
254 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts
|
|
|
255 are stored in the data_dependence_relation structure under the form
|
|
|
256 of an array of subscripts. */
|
|
|
257
|
|
|
258 struct subscript
|
|
|
259 {
|
|
|
260 /* A description of the iterations for which the elements are
|
|
|
261 accessed twice. */
|
|
|
262 conflict_function *conflicting_iterations_in_a;
|
|
|
263 conflict_function *conflicting_iterations_in_b;
|
|
|
264
|
|
|
265 /* This field stores the information about the iteration domain
|
|
|
266 validity of the dependence relation. */
|
|
|
267 tree last_conflict;
|
|
|
268
|
|
|
269 /* Distance from the iteration that access a conflicting element in
|
|
|
270 A to the iteration that access this same conflicting element in
|
|
|
271 B. The distance is a tree scalar expression, i.e. a constant or a
|
|
|
272 symbolic expression, but certainly not a chrec function. */
|
|
|
273 tree distance;
|
|
|
274 };
|
|
|
275
|
|
|
276 typedef struct subscript *subscript_p;
|
|
|
277 DEF_VEC_P(subscript_p);
|
|
|
278 DEF_VEC_ALLOC_P (subscript_p, heap);
|
|
|
279
|
|
|
280 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
|
|
|
281 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
|
|
|
282 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
|
|
|
283 #define SUB_DISTANCE(SUB) SUB->distance
|
|
|
284
|
|
|
285 /* A data_dependence_relation represents a relation between two
|
|
|
286 data_references A and B. */
|
|
|
287
|
|
|
288 struct data_dependence_relation
|
|
|
289 {
|
|
|
290
|
|
|
291 struct data_reference *a;
|
|
|
292 struct data_reference *b;
|
|
|
293
|
|
|
294 /* A "yes/no/maybe" field for the dependence relation:
|
|
|
295
|
|
|
296 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
|
|
|
297 relation between A and B, and the description of this relation
|
|
|
298 is given in the SUBSCRIPTS array,
|
|
|
299
|
|
|
300 - when "ARE_DEPENDENT == chrec_known", there is no dependence and
|
|
|
301 SUBSCRIPTS is empty,
|
|
|
302
|
|
|
303 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
|
|
|
304 but the analyzer cannot be more specific. */
|
|
|
305 tree are_dependent;
|
|
|
306
|
|
|
307 /* For each subscript in the dependence test, there is an element in
|
|
|
308 this array. This is the attribute that labels the edge A->B of
|
|
|
309 the data_dependence_relation. */
|
|
|
310 VEC (subscript_p, heap) *subscripts;
|
|
|
311
|
|
|
312 /* The analyzed loop nest. */
|
|
|
313 VEC (loop_p, heap) *loop_nest;
|
|
|
314
|
|
|
315 /* The classic direction vector. */
|
|
|
316 VEC (lambda_vector, heap) *dir_vects;
|
|
|
317
|
|
|
318 /* The classic distance vector. */
|
|
|
319 VEC (lambda_vector, heap) *dist_vects;
|
|
|
320
|
|
|
321 /* An index in loop_nest for the innermost loop that varies for
|
|
|
322 this data dependence relation. */
|
|
|
323 unsigned inner_loop;
|
|
|
324
|
|
|
325 /* Is the dependence reversed with respect to the lexicographic order? */
|
|
|
326 bool reversed_p;
|
|
|
327
|
|
|
328 /* When the dependence relation is affine, it can be represented by
|
|
|
329 a distance vector. */
|
|
|
330 bool affine_p;
|
|
|
331
|
|
|
332 /* Set to true when the dependence relation is on the same data
|
|
|
333 access. */
|
|
|
334 bool self_reference_p;
|
|
|
335 };
|
|
|
336
|
|
|
337 typedef struct data_dependence_relation *ddr_p;
|
|
|
338 DEF_VEC_P(ddr_p);
|
|
|
339 DEF_VEC_ALLOC_P(ddr_p,heap);
|
|
|
340
|
|
|
341 #define DDR_A(DDR) DDR->a
|
|
|
342 #define DDR_B(DDR) DDR->b
|
|
|
343 #define DDR_AFFINE_P(DDR) DDR->affine_p
|
|
|
344 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
|
|
|
345 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
|
|
|
346 #define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
|
|
|
347 #define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
|
|
|
348
|
|
|
349 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
|
|
|
350 /* The size of the direction/distance vectors: the number of loops in
|
|
|
351 the loop nest. */
|
|
|
352 #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
|
|
|
353 #define DDR_INNER_LOOP(DDR) DDR->inner_loop
|
|
|
354 #define DDR_SELF_REFERENCE(DDR) DDR->self_reference_p
|
|
|
355
|
|
|
356 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
|
|
|
357 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
|
|
|
358 #define DDR_NUM_DIST_VECTS(DDR) \
|
|
|
359 (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
|
|
|
360 #define DDR_NUM_DIR_VECTS(DDR) \
|
|
|
361 (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
|
|
|
362 #define DDR_DIR_VECT(DDR, I) \
|
|
|
363 VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
|
|
|
364 #define DDR_DIST_VECT(DDR, I) \
|
|
|
365 VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
|
|
|
366 #define DDR_REVERSED_P(DDR) DDR->reversed_p
|
|
|
367
|
|
|
368
|
|
|
369
|
|
|
370 /* Describes a location of a memory reference. */
|
|
|
371
|
|
|
372 typedef struct data_ref_loc_d
|
|
|
373 {
|
|
|
374 /* Position of the memory reference. */
|
|
|
375 tree *pos;
|
|
|
376
|
|
|
377 /* True if the memory reference is read. */
|
|
|
378 bool is_read;
|
|
|
379 } data_ref_loc;
|
|
|
380
|
|
|
381 DEF_VEC_O (data_ref_loc);
|
|
|
382 DEF_VEC_ALLOC_O (data_ref_loc, heap);
|
|
|
383
|
|
|
384 bool get_references_in_stmt (gimple, VEC (data_ref_loc, heap) **);
|
|
|
385 bool dr_analyze_innermost (struct data_reference *);
|
|
|
386 extern bool compute_data_dependences_for_loop (struct loop *, bool,
|
|
|
387 VEC (data_reference_p, heap) **,
|
|
|
388 VEC (ddr_p, heap) **);
|
|
|
389 extern tree find_data_references_in_loop (struct loop *,
|
|
|
390 VEC (data_reference_p, heap) **);
|
|
|
391 extern void print_direction_vector (FILE *, lambda_vector, int);
|
|
|
392 extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int);
|
|
|
393 extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int);
|
|
|
394 extern void dump_subscript (FILE *, struct subscript *);
|
|
|
395 extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *);
|
|
|
396 extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *);
|
|
|
397 extern void dump_data_reference (FILE *, struct data_reference *);
|
|
|
398 extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *);
|
|
|
399 extern void debug_data_dependence_relation (struct data_dependence_relation *);
|
|
|
400 extern void dump_data_dependence_relation (FILE *,
|
|
|
401 struct data_dependence_relation *);
|
|
|
402 extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *);
|
|
|
403 extern void debug_data_dependence_relations (VEC (ddr_p, heap) *);
|
|
|
404 extern void dump_data_dependence_direction (FILE *,
|
|
|
405 enum data_dependence_direction);
|
|
|
406 extern void free_dependence_relation (struct data_dependence_relation *);
|
|
|
407 extern void free_dependence_relations (VEC (ddr_p, heap) *);
|
|
|
408 extern void free_data_ref (data_reference_p);
|
|
|
409 extern void free_data_refs (VEC (data_reference_p, heap) *);
|
|
|
410 extern bool find_data_references_in_stmt (struct loop *, gimple,
|
|
|
411 VEC (data_reference_p, heap) **);
|
|
|
412 struct data_reference *create_data_ref (struct loop *, tree, gimple, bool);
|
|
|
413 extern bool find_loop_nest (struct loop *, VEC (loop_p, heap) **);
|
|
|
414 extern void compute_all_dependences (VEC (data_reference_p, heap) *,
|
|
|
415 VEC (ddr_p, heap) **, VEC (loop_p, heap) *,
|
|
|
416 bool);
|
|
|
417
|
|
|
418 extern void create_rdg_vertices (struct graph *, VEC (gimple, heap) *);
|
|
|
419 extern bool dr_may_alias_p (const struct data_reference *,
|
|
|
420 const struct data_reference *);
|
|
|
421 extern bool stmt_simple_memref_p (struct loop *, gimple, tree);
|
|
|
422
|
|
|
423 /* Return true when the DDR contains two data references that have the
|
|
|
424 same access functions. */
|
|
|
425
|
|
|
426 static inline bool
|
|
|
427 same_access_functions (const struct data_dependence_relation *ddr)
|
|
|
428 {
|
|
|
429 unsigned i;
|
|
|
430
|
|
|
431 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
|
|
|
432 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
|
|
|
433 DR_ACCESS_FN (DDR_B (ddr), i)))
|
|
|
434 return false;
|
|
|
435
|
|
|
436 return true;
|
|
|
437 }
|
|
|
438
|
|
|
439 /* Return true when DDR is an anti-dependence relation. */
|
|
|
440
|
|
|
441 static inline bool
|
|
|
442 ddr_is_anti_dependent (ddr_p ddr)
|
|
|
443 {
|
|
|
444 return (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
|
|
|
445 && DR_IS_READ (DDR_A (ddr))
|
|
|
446 && !DR_IS_READ (DDR_B (ddr))
|
|
|
447 && !same_access_functions (ddr));
|
|
|
448 }
|
|
|
449
|
|
|
450 /* Return true when DEPENDENCE_RELATIONS contains an anti-dependence. */
|
|
|
451
|
|
|
452 static inline bool
|
|
|
453 ddrs_have_anti_deps (VEC (ddr_p, heap) *dependence_relations)
|
|
|
454 {
|
|
|
455 unsigned i;
|
|
|
456 ddr_p ddr;
|
|
|
457
|
|
|
458 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
|
|
|
459 if (ddr_is_anti_dependent (ddr))
|
|
|
460 return true;
|
|
|
461
|
|
|
462 return false;
|
|
|
463 }
|
|
|
464
|
|
|
465 /* Return the dependence level for the DDR relation. */
|
|
|
466
|
|
|
467 static inline unsigned
|
|
|
468 ddr_dependence_level (ddr_p ddr)
|
|
|
469 {
|
|
|
470 unsigned vector;
|
|
|
471 unsigned level = 0;
|
|
|
472
|
|
|
473 if (DDR_DIST_VECTS (ddr))
|
|
|
474 level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
|
|
|
475
|
|
|
476 for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
|
|
|
477 level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
|
|
|
478 DDR_NB_LOOPS (ddr)));
|
|
|
479 return level;
|
|
|
480 }
|
|
|
481
|
|
|
482
|
|
|
483
|
|
|
484 /* A Reduced Dependence Graph (RDG) vertex representing a statement. */
|
|
|
485 typedef struct rdg_vertex
|
|
|
486 {
|
|
|
487 /* The statement represented by this vertex. */
|
|
|
488 gimple stmt;
|
|
|
489
|
|
|
490 /* True when the statement contains a write to memory. */
|
|
|
491 bool has_mem_write;
|
|
|
492
|
|
|
493 /* True when the statement contains a read from memory. */
|
|
|
494 bool has_mem_reads;
|
|
|
495 } *rdg_vertex_p;
|
|
|
496
|
|
|
497 #define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
|
|
|
498 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
|
|
|
499 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
|
|
|
500 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
|
|
|
501 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
|
|
|
502 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
|
|
|
503
|
|
|
504 void dump_rdg_vertex (FILE *, struct graph *, int);
|
|
|
505 void debug_rdg_vertex (struct graph *, int);
|
|
|
506 void dump_rdg_component (FILE *, struct graph *, int, bitmap);
|
|
|
507 void debug_rdg_component (struct graph *, int);
|
|
|
508 void dump_rdg (FILE *, struct graph *);
|
|
|
509 void debug_rdg (struct graph *);
|
|
|
510 void dot_rdg (struct graph *);
|
|
|
511 int rdg_vertex_for_stmt (struct graph *, gimple);
|
|
|
512
|
|
|
513 /* Data dependence type. */
|
|
|
514
|
|
|
515 enum rdg_dep_type
|
|
|
516 {
|
|
|
517 /* Read After Write (RAW). */
|
|
|
518 flow_dd = 'f',
|
|
|
519
|
|
|
520 /* Write After Read (WAR). */
|
|
|
521 anti_dd = 'a',
|
|
|
522
|
|
|
523 /* Write After Write (WAW). */
|
|
|
524 output_dd = 'o',
|
|
|
525
|
|
|
526 /* Read After Read (RAR). */
|
|
|
527 input_dd = 'i'
|
|
|
528 };
|
|
|
529
|
|
|
530 /* Dependence information attached to an edge of the RDG. */
|
|
|
531
|
|
|
532 typedef struct rdg_edge
|
|
|
533 {
|
|
|
534 /* Type of the dependence. */
|
|
|
535 enum rdg_dep_type type;
|
|
|
536
|
|
|
537 /* Levels of the dependence: the depth of the loops that carry the
|
|
|
538 dependence. */
|
|
|
539 unsigned level;
|
|
|
540
|
|
|
541 /* Dependence relation between data dependences, NULL when one of
|
|
|
542 the vertices is a scalar. */
|
|
|
543 ddr_p relation;
|
|
|
544 } *rdg_edge_p;
|
|
|
545
|
|
|
546 #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
|
|
|
547 #define RDGE_LEVEL(E) ((struct rdg_edge *) ((E)->data))->level
|
|
|
548 #define RDGE_RELATION(E) ((struct rdg_edge *) ((E)->data))->relation
|
|
|
549
|
|
|
550 struct graph *build_rdg (struct loop *);
|
|
|
551 struct graph *build_empty_rdg (int);
|
|
|
552 void free_rdg (struct graph *);
|
|
|
553
|
|
|
554 /* Return the index of the variable VAR in the LOOP_NEST array. */
|
|
|
555
|
|
|
556 static inline int
|
|
|
557 index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
|
|
|
558 {
|
|
|
559 struct loop *loopi;
|
|
|
560 int var_index;
|
|
|
561
|
|
|
562 for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi);
|
|
|
563 var_index++)
|
|
|
564 if (loopi->num == var)
|
|
|
565 break;
|
|
|
566
|
|
|
567 return var_index;
|
|
|
568 }
|
|
|
569
|
|
|
570 void stores_from_loop (struct loop *, VEC (gimple, heap) **);
|
|
|
571 void remove_similar_memory_refs (VEC (gimple, heap) **);
|
|
|
572 bool rdg_defs_used_in_other_loops_p (struct graph *, int);
|
|
|
573 bool have_similar_memory_accesses (gimple, gimple);
|
|
|
574
|
|
|
575 /* Determines whether RDG vertices V1 and V2 access to similar memory
|
|
|
576 locations, in which case they have to be in the same partition. */
|
|
|
577
|
|
|
578 static inline bool
|
|
|
579 rdg_has_similar_memory_accesses (struct graph *rdg, int v1, int v2)
|
|
|
580 {
|
|
|
581 return have_similar_memory_accesses (RDG_STMT (rdg, v1),
|
|
|
582 RDG_STMT (rdg, v2));
|
|
|
583 }
|
|
|
584
|
|
|
585 /* In lambda-code.c */
|
|
|
586 bool lambda_transform_legal_p (lambda_trans_matrix, int,
|
|
|
587 VEC (ddr_p, heap) *);
|
|
|
588 void lambda_collect_parameters (VEC (data_reference_p, heap) *,
|
|
|
589 VEC (tree, heap) **);
|
|
|
590 bool lambda_compute_access_matrices (VEC (data_reference_p, heap) *,
|
|
|
591 VEC (tree, heap) *, VEC (loop_p, heap) *);
|
|
|
592
|
|
|
593 /* In tree-data-ref.c */
|
|
|
594 void split_constant_offset (tree , tree *, tree *);
|
|
|
595
|
|
|
596 /* Strongly connected components of the reduced data dependence graph. */
|
|
|
597
|
|
|
598 typedef struct rdg_component
|
|
|
599 {
|
|
|
600 int num;
|
|
|
601 VEC (int, heap) *vertices;
|
|
|
602 } *rdgc;
|
|
|
603
|
|
|
604 DEF_VEC_P (rdgc);
|
|
|
605 DEF_VEC_ALLOC_P (rdgc, heap);
|
|
|
606
|
|
|
607 DEF_VEC_P (bitmap);
|
|
|
608 DEF_VEC_ALLOC_P (bitmap, heap);
|
|
|
609
|
|
|
610 #endif /* GCC_TREE_DATA_REF_H */
|
