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 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
29 innermost_loop_behavior describes the evolution of the address of the memory
30 reference in the innermost enclosing loop. The address is expressed as
31 BASE + STEP * # of iteration, and base is further decomposed as the base
32 pointer (BASE_ADDRESS), loop invariant offset (OFFSET) and
33 constant offset (INIT). Examples, in loop nest
35 for (i = 0; i < 100; i++)
36 for (j = 3; j < 100; j++)
39 data-ref a[j].b[i][j] *(p + x + 16B + 4B * j)
41 innermost_loop_behavior
44 init 3 * D_j + offsetof (b) 28
48 struct innermost_loop_behavior
55 /* Alignment information. ALIGNED_TO is set to the largest power of two
56 that divides OFFSET. */
60 /* Describes the evolutions of indices of the memory reference. The indices
61 are indices of the ARRAY_REFs and the operands of INDIRECT_REFs.
62 For ARRAY_REFs, BASE_OBJECT is the reference with zeroed indices
63 (note that this reference does not have to be valid, if zero does not
64 belong to the range of the array; hence it is not recommended to use
65 BASE_OBJECT in any code generation). For INDIRECT_REFs, the address is
66 set to the loop-invariant part of the address of the object, except for
67 the constant offset. For the examples above,
69 base_object: a[0].b[0][0] *(p + x + 4B * j_0)
70 indices: {j_0, +, 1}_2 {16, +, 4}_2
80 /* A list of chrecs. Access functions of the indices. */
81 VEC(tree
,heap
) *access_fns
;
86 /* The alias information that should be used for new pointers to this
87 location. SYMBOL_TAG is either a DECL or a SYMBOL_MEMORY_TAG. */
90 struct ptr_info_def
*ptr_info
;
92 /* The set of virtual operands corresponding to this memory reference,
93 serving as a description of the alias information for the memory
94 reference. This could be eliminated if we had alias oracle. */
100 /* A pointer to the statement that contains this DR. */
103 /* A pointer to the memory reference. */
106 /* Auxiliary info specific to a pass. */
109 /* True when the data reference is in RHS of a stmt. */
112 /* Behavior of the memory reference in the innermost loop. */
113 struct innermost_loop_behavior innermost
;
115 /* Decomposition to indices for alias analysis. */
116 struct indices indices
;
118 /* Alias information for the data reference. */
119 struct dr_alias alias
;
122 typedef struct data_reference
*data_reference_p
;
123 DEF_VEC_P(data_reference_p
);
124 DEF_VEC_ALLOC_P (data_reference_p
, heap
);
126 #define DR_STMT(DR) (DR)->stmt
127 #define DR_REF(DR) (DR)->ref
128 #define DR_BASE_OBJECT(DR) (DR)->indices.base_object
129 #define DR_ACCESS_FNS(DR) (DR)->indices.access_fns
130 #define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I)
131 #define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR))
132 #define DR_IS_READ(DR) (DR)->is_read
133 #define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address
134 #define DR_OFFSET(DR) (DR)->innermost.offset
135 #define DR_INIT(DR) (DR)->innermost.init
136 #define DR_STEP(DR) (DR)->innermost.step
137 #define DR_SYMBOL_TAG(DR) (DR)->alias.symbol_tag
138 #define DR_PTR_INFO(DR) (DR)->alias.ptr_info
139 #define DR_SUBVARS(DR) (DR)->alias.subvars
140 #define DR_VOPS(DR) (DR)->alias.vops
141 #define DR_ALIGNED_TO(DR) (DR)->innermost.aligned_to
143 enum data_dependence_direction
{
147 dir_positive_or_negative
,
148 dir_positive_or_equal
,
149 dir_negative_or_equal
,
154 /* The description of the grid of iterations that overlap. At most
155 two loops are considered at the same time just now, hence at most
156 two functions are needed. For each of the functions, we store
157 the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
158 where x, y, ... are variables. */
162 /* Special values of N. */
163 #define NO_DEPENDENCE 0
164 #define NOT_KNOWN (MAX_DIM + 1)
165 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
166 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
167 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
169 typedef VEC (tree
, heap
) *affine_fn
;
174 affine_fn fns
[MAX_DIM
];
177 /* What is a subscript? Given two array accesses a subscript is the
178 tuple composed of the access functions for a given dimension.
179 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
180 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts
181 are stored in the data_dependence_relation structure under the form
182 of an array of subscripts. */
186 /* A description of the iterations for which the elements are
188 conflict_function
*conflicting_iterations_in_a
;
189 conflict_function
*conflicting_iterations_in_b
;
191 /* This field stores the information about the iteration domain
192 validity of the dependence relation. */
195 /* Distance from the iteration that access a conflicting element in
196 A to the iteration that access this same conflicting element in
197 B. The distance is a tree scalar expression, i.e. a constant or a
198 symbolic expression, but certainly not a chrec function. */
202 typedef struct subscript
*subscript_p
;
203 DEF_VEC_P(subscript_p
);
204 DEF_VEC_ALLOC_P (subscript_p
, heap
);
206 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
207 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
208 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
209 #define SUB_DISTANCE(SUB) SUB->distance
211 /* A data_dependence_relation represents a relation between two
212 data_references A and B. */
214 struct data_dependence_relation
217 struct data_reference
*a
;
218 struct data_reference
*b
;
220 /* When the dependence relation is affine, it can be represented by
221 a distance vector. */
224 /* A "yes/no/maybe" field for the dependence relation:
226 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
227 relation between A and B, and the description of this relation
228 is given in the SUBSCRIPTS array,
230 - when "ARE_DEPENDENT == chrec_known", there is no dependence and
233 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
234 but the analyzer cannot be more specific. */
237 /* For each subscript in the dependence test, there is an element in
238 this array. This is the attribute that labels the edge A->B of
239 the data_dependence_relation. */
240 VEC (subscript_p
, heap
) *subscripts
;
242 /* The analyzed loop nest. */
243 VEC (loop_p
, heap
) *loop_nest
;
245 /* An index in loop_nest for the innermost loop that varies for
246 this data dependence relation. */
249 /* The classic direction vector. */
250 VEC (lambda_vector
, heap
) *dir_vects
;
252 /* The classic distance vector. */
253 VEC (lambda_vector
, heap
) *dist_vects
;
256 typedef struct data_dependence_relation
*ddr_p
;
258 DEF_VEC_ALLOC_P(ddr_p
,heap
);
260 #define DDR_A(DDR) DDR->a
261 #define DDR_B(DDR) DDR->b
262 #define DDR_AFFINE_P(DDR) DDR->affine_p
263 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
264 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
265 #define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
266 #define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
268 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
269 /* The size of the direction/distance vectors: the number of loops in
271 #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
272 #define DDR_INNER_LOOP(DDR) DDR->inner_loop
274 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
275 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
276 #define DDR_NUM_DIST_VECTS(DDR) \
277 (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
278 #define DDR_NUM_DIR_VECTS(DDR) \
279 (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
280 #define DDR_DIR_VECT(DDR, I) \
281 VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
282 #define DDR_DIST_VECT(DDR, I) \
283 VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
287 /* Describes a location of a memory reference. */
289 typedef struct data_ref_loc_d
291 /* Position of the memory reference. */
294 /* True if the memory reference is read. */
298 DEF_VEC_O (data_ref_loc
);
299 DEF_VEC_ALLOC_O (data_ref_loc
, heap
);
301 bool get_references_in_stmt (tree
, VEC (data_ref_loc
, heap
) **);
302 void dr_analyze_innermost (struct data_reference
*);
303 extern void compute_data_dependences_for_loop (struct loop
*, bool,
304 VEC (data_reference_p
, heap
) **,
305 VEC (ddr_p
, heap
) **);
306 extern void print_direction_vector (FILE *, lambda_vector
, int);
307 extern void print_dir_vectors (FILE *, VEC (lambda_vector
, heap
) *, int);
308 extern void print_dist_vectors (FILE *, VEC (lambda_vector
, heap
) *, int);
309 extern void dump_subscript (FILE *, struct subscript
*);
310 extern void dump_ddrs (FILE *, VEC (ddr_p
, heap
) *);
311 extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p
, heap
) *);
312 extern void dump_data_reference (FILE *, struct data_reference
*);
313 extern void dump_data_references (FILE *, VEC (data_reference_p
, heap
) *);
314 extern void debug_data_dependence_relation (struct data_dependence_relation
*);
315 extern void dump_data_dependence_relation (FILE *,
316 struct data_dependence_relation
*);
317 extern void dump_data_dependence_relations (FILE *, VEC (ddr_p
, heap
) *);
318 extern void dump_data_dependence_direction (FILE *,
319 enum data_dependence_direction
);
320 extern void free_dependence_relation (struct data_dependence_relation
*);
321 extern void free_dependence_relations (VEC (ddr_p
, heap
) *);
322 extern void free_data_refs (VEC (data_reference_p
, heap
) *);
323 struct data_reference
*create_data_ref (struct loop
*, tree
, tree
, bool);
324 bool find_loop_nest (struct loop
*, VEC (loop_p
, heap
) **);
325 void compute_all_dependences (VEC (data_reference_p
, heap
) *,
326 VEC (ddr_p
, heap
) **, VEC (loop_p
, heap
) *, bool);
328 /* Return the index of the variable VAR in the LOOP_NEST array. */
331 index_in_loop_nest (int var
, VEC (loop_p
, heap
) *loop_nest
)
336 for (var_index
= 0; VEC_iterate (loop_p
, loop_nest
, var_index
, loopi
);
338 if (loopi
->num
== var
)
344 /* In lambda-code.c */
345 bool lambda_transform_legal_p (lambda_trans_matrix
, int, VEC (ddr_p
, heap
) *);
347 #endif /* GCC_TREE_DATA_REF_H */