1 |
12 |
jlechner |
/* Data references and dependences detectors.
|
2 |
|
|
Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
|
3 |
|
|
Contributed by Sebastian Pop <s.pop@laposte.net>
|
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 |
|
|
#define DR_STMT(DR) (DR)->stmt
|
111 |
|
|
#define DR_REF(DR) (DR)->ref
|
112 |
|
|
#define DR_BASE_OBJECT(DR) (DR)->object_info.base_object
|
113 |
|
|
#define DR_TYPE(DR) (DR)->type
|
114 |
|
|
#define DR_ACCESS_FNS(DR)\
|
115 |
|
|
(DR_TYPE(DR) == ARRAY_REF_TYPE ? \
|
116 |
|
|
(DR)->object_info.access_fns : (DR)->first_location.access_fns)
|
117 |
|
|
#define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I)
|
118 |
|
|
#define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR))
|
119 |
|
|
#define DR_IS_READ(DR) (DR)->is_read
|
120 |
|
|
#define DR_BASE_ADDRESS(DR) (DR)->first_location.base_address
|
121 |
|
|
#define DR_OFFSET(DR) (DR)->first_location.offset
|
122 |
|
|
#define DR_INIT(DR) (DR)->first_location.init
|
123 |
|
|
#define DR_STEP(DR) (DR)->first_location.step
|
124 |
|
|
#define DR_MEMTAG(DR) (DR)->memtag
|
125 |
|
|
#define DR_ALIGNED_TO(DR) (DR)->aligned_to
|
126 |
|
|
#define DR_OFFSET_MISALIGNMENT(DR) (DR)->misalignment
|
127 |
|
|
#define DR_PTR_INFO(DR) (DR)->ptr_info
|
128 |
|
|
#define DR_SUBVARS(DR) (DR)->subvars
|
129 |
|
|
|
130 |
|
|
#define DR_ACCESS_FNS_ADDR(DR) \
|
131 |
|
|
(DR_TYPE(DR) == ARRAY_REF_TYPE ? \
|
132 |
|
|
&((DR)->object_info.access_fns) : &((DR)->first_location.access_fns))
|
133 |
|
|
#define DR_SET_ACCESS_FNS(DR, ACC_FNS) \
|
134 |
|
|
{ \
|
135 |
|
|
if (DR_TYPE(DR) == ARRAY_REF_TYPE) \
|
136 |
|
|
(DR)->object_info.access_fns = ACC_FNS; \
|
137 |
|
|
else \
|
138 |
|
|
(DR)->first_location.access_fns = ACC_FNS; \
|
139 |
|
|
}
|
140 |
|
|
#define DR_FREE_ACCESS_FNS(DR) \
|
141 |
|
|
{ \
|
142 |
|
|
if (DR_TYPE(DR) == ARRAY_REF_TYPE) \
|
143 |
|
|
VEC_free (tree, heap, (DR)->object_info.access_fns); \
|
144 |
|
|
else \
|
145 |
|
|
VEC_free (tree, heap, (DR)->first_location.access_fns); \
|
146 |
|
|
}
|
147 |
|
|
|
148 |
|
|
enum data_dependence_direction {
|
149 |
|
|
dir_positive,
|
150 |
|
|
dir_negative,
|
151 |
|
|
dir_equal,
|
152 |
|
|
dir_positive_or_negative,
|
153 |
|
|
dir_positive_or_equal,
|
154 |
|
|
dir_negative_or_equal,
|
155 |
|
|
dir_star,
|
156 |
|
|
dir_independent
|
157 |
|
|
};
|
158 |
|
|
|
159 |
|
|
/* What is a subscript? Given two array accesses a subscript is the
|
160 |
|
|
tuple composed of the access functions for a given dimension.
|
161 |
|
|
Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
|
162 |
|
|
subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts
|
163 |
|
|
are stored in the data_dependence_relation structure under the form
|
164 |
|
|
of an array of subscripts. */
|
165 |
|
|
|
166 |
|
|
struct subscript
|
167 |
|
|
{
|
168 |
|
|
/* A description of the iterations for which the elements are
|
169 |
|
|
accessed twice. */
|
170 |
|
|
tree conflicting_iterations_in_a;
|
171 |
|
|
tree conflicting_iterations_in_b;
|
172 |
|
|
|
173 |
|
|
/* This field stores the information about the iteration domain
|
174 |
|
|
validity of the dependence relation. */
|
175 |
|
|
tree last_conflict;
|
176 |
|
|
|
177 |
|
|
/* Distance from the iteration that access a conflicting element in
|
178 |
|
|
A to the iteration that access this same conflicting element in
|
179 |
|
|
B. The distance is a tree scalar expression, i.e. a constant or a
|
180 |
|
|
symbolic expression, but certainly not a chrec function. */
|
181 |
|
|
tree distance;
|
182 |
|
|
};
|
183 |
|
|
|
184 |
|
|
#define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
|
185 |
|
|
#define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
|
186 |
|
|
#define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
|
187 |
|
|
#define SUB_DISTANCE(SUB) SUB->distance
|
188 |
|
|
|
189 |
|
|
/* A data_dependence_relation represents a relation between two
|
190 |
|
|
data_references A and B. */
|
191 |
|
|
|
192 |
|
|
struct data_dependence_relation
|
193 |
|
|
{
|
194 |
|
|
|
195 |
|
|
struct data_reference *a;
|
196 |
|
|
struct data_reference *b;
|
197 |
|
|
|
198 |
|
|
/* When the dependence relation is affine, it can be represented by
|
199 |
|
|
a distance vector. */
|
200 |
|
|
bool affine_p;
|
201 |
|
|
|
202 |
|
|
/* A "yes/no/maybe" field for the dependence relation:
|
203 |
|
|
|
204 |
|
|
- when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
|
205 |
|
|
relation between A and B, and the description of this relation
|
206 |
|
|
is given in the SUBSCRIPTS array,
|
207 |
|
|
|
208 |
|
|
- when "ARE_DEPENDENT == chrec_known", there is no dependence and
|
209 |
|
|
SUBSCRIPTS is empty,
|
210 |
|
|
|
211 |
|
|
- when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
|
212 |
|
|
but the analyzer cannot be more specific. */
|
213 |
|
|
tree are_dependent;
|
214 |
|
|
|
215 |
|
|
/* For each subscript in the dependence test, there is an element in
|
216 |
|
|
this array. This is the attribute that labels the edge A->B of
|
217 |
|
|
the data_dependence_relation. */
|
218 |
|
|
varray_type subscripts;
|
219 |
|
|
|
220 |
|
|
/* The size of the direction/distance vectors: the depth of the
|
221 |
|
|
analyzed loop nest. */
|
222 |
|
|
int size_vect;
|
223 |
|
|
|
224 |
|
|
/* The classic direction vector. */
|
225 |
|
|
VEC(lambda_vector,heap) *dir_vects;
|
226 |
|
|
|
227 |
|
|
/* The classic distance vector. */
|
228 |
|
|
VEC(lambda_vector,heap) *dist_vects;
|
229 |
|
|
};
|
230 |
|
|
|
231 |
|
|
#define DDR_A(DDR) DDR->a
|
232 |
|
|
#define DDR_B(DDR) DDR->b
|
233 |
|
|
#define DDR_AFFINE_P(DDR) DDR->affine_p
|
234 |
|
|
#define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
|
235 |
|
|
#define DDR_SUBSCRIPTS(DDR) DDR->subscripts
|
236 |
|
|
#define DDR_SUBSCRIPTS_VECTOR_INIT(DDR, N) \
|
237 |
|
|
VARRAY_GENERIC_PTR_INIT (DDR_SUBSCRIPTS (DDR), N, "subscripts_vector");
|
238 |
|
|
#define DDR_SUBSCRIPT(DDR, I) VARRAY_GENERIC_PTR (DDR_SUBSCRIPTS (DDR), I)
|
239 |
|
|
#define DDR_NUM_SUBSCRIPTS(DDR) VARRAY_ACTIVE_SIZE (DDR_SUBSCRIPTS (DDR))
|
240 |
|
|
#define DDR_SIZE_VECT(DDR) DDR->size_vect
|
241 |
|
|
|
242 |
|
|
#define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
|
243 |
|
|
#define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
|
244 |
|
|
#define DDR_NUM_DIST_VECTS(DDR) \
|
245 |
|
|
(VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
|
246 |
|
|
#define DDR_NUM_DIR_VECTS(DDR) \
|
247 |
|
|
(VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
|
248 |
|
|
#define DDR_DIR_VECT(DDR, I) \
|
249 |
|
|
VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
|
250 |
|
|
#define DDR_DIST_VECT(DDR, I) \
|
251 |
|
|
VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
|
252 |
|
|
|
253 |
|
|
|
254 |
|
|
|
255 |
|
|
extern tree find_data_references_in_loop (struct loop *, varray_type *);
|
256 |
|
|
extern struct data_dependence_relation *initialize_data_dependence_relation
|
257 |
|
|
(struct data_reference *, struct data_reference *);
|
258 |
|
|
extern void compute_affine_dependence (struct data_dependence_relation *);
|
259 |
|
|
extern void analyze_all_data_dependences (struct loops *);
|
260 |
|
|
extern void compute_data_dependences_for_loop (struct loop *, bool,
|
261 |
|
|
varray_type *, varray_type *);
|
262 |
|
|
|
263 |
|
|
extern void dump_subscript (FILE *, struct subscript *);
|
264 |
|
|
extern void dump_ddrs (FILE *, varray_type);
|
265 |
|
|
extern void dump_dist_dir_vectors (FILE *, varray_type);
|
266 |
|
|
extern void dump_data_reference (FILE *, struct data_reference *);
|
267 |
|
|
extern void dump_data_references (FILE *, varray_type);
|
268 |
|
|
extern void dump_data_dependence_relation (FILE *,
|
269 |
|
|
struct data_dependence_relation *);
|
270 |
|
|
extern void dump_data_dependence_relations (FILE *, varray_type);
|
271 |
|
|
extern void dump_data_dependence_direction (FILE *,
|
272 |
|
|
enum data_dependence_direction);
|
273 |
|
|
extern void free_dependence_relation (struct data_dependence_relation *);
|
274 |
|
|
extern void free_dependence_relations (varray_type);
|
275 |
|
|
extern void free_data_refs (varray_type);
|
276 |
|
|
extern void compute_subscript_distance (struct data_dependence_relation *);
|
277 |
|
|
extern struct data_reference *analyze_array (tree, tree, bool);
|
278 |
|
|
extern void estimate_iters_using_array (tree, tree);
|
279 |
|
|
|
280 |
|
|
|
281 |
|
|
|
282 |
|
|
|
283 |
|
|
#endif /* GCC_TREE_DATA_REF_H */
|