]>
Commit | Line | Data |
---|---|---|
b8698a0f | 1 | /* Data references and dependences detectors. |
d1e082c2 | 2 | Copyright (C) 2003-2013 Free Software Foundation, Inc. |
0ff4040e | 3 | Contributed by Sebastian Pop <pop@cri.ensmp.fr> |
56cf8686 SP |
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 | |
9dcd6f09 | 9 | Software Foundation; either version 3, or (at your option) any later |
56cf8686 SP |
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 | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
56cf8686 SP |
20 | |
21 | #ifndef GCC_TREE_DATA_REF_H | |
22 | #define GCC_TREE_DATA_REF_H | |
23 | ||
3a796c6f | 24 | #include "graphds.h" |
3d8864c0 | 25 | #include "omega.h" |
dea61d92 | 26 | #include "tree-chrec.h" |
36d59cf7 | 27 | |
98b44b0e | 28 | /* |
3cb960c7 ZD |
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 | |
b8698a0f L |
33 | constant offset (INIT). Examples, in loop nest |
34 | ||
3cb960c7 ZD |
35 | for (i = 0; i < 100; i++) |
36 | for (j = 3; j < 100; j++) | |
98b44b0e | 37 | |
86a07404 | 38 | Example 1 Example 2 |
3cb960c7 | 39 | data-ref a[j].b[i][j] *(p + x + 16B + 4B * j) |
b8698a0f | 40 | |
dea61d92 | 41 | |
3cb960c7 ZD |
42 | innermost_loop_behavior |
43 | base_address &a p | |
44 | offset i * D_i x | |
45 | init 3 * D_j + offsetof (b) 28 | |
86a07404 | 46 | step D_j 4 |
86a07404 | 47 | |
98b44b0e | 48 | */ |
3cb960c7 | 49 | struct innermost_loop_behavior |
86a07404 IR |
50 | { |
51 | tree base_address; | |
52 | tree offset; | |
53 | tree init; | |
54 | tree step; | |
3cb960c7 ZD |
55 | |
56 | /* Alignment information. ALIGNED_TO is set to the largest power of two | |
57 | that divides OFFSET. */ | |
58 | tree aligned_to; | |
86a07404 IR |
59 | }; |
60 | ||
3cb960c7 | 61 | /* Describes the evolutions of indices of the memory reference. The indices |
c4ddde1b RG |
62 | are indices of the ARRAY_REFs, indexes in artificial dimensions |
63 | added for member selection of records and the operands of MEM_REFs. | |
64 | BASE_OBJECT is the part of the reference that is loop-invariant | |
65 | (note that this reference does not have to cover the whole object | |
66 | being accessed, in which case UNCONSTRAINED_BASE is set; hence it is | |
67 | not recommended to use BASE_OBJECT in any code generation). | |
68 | For the examples above, | |
69 | ||
70 | base_object: a *(p + x + 4B * j_0) | |
3cb960c7 | 71 | indices: {j_0, +, 1}_2 {16, +, 4}_2 |
c4ddde1b | 72 | 4 |
3cb960c7 ZD |
73 | {i_0, +, 1}_1 |
74 | {j_0, +, 1}_2 | |
75 | */ | |
76 | ||
77 | struct indices | |
86a07404 IR |
78 | { |
79 | /* The object. */ | |
80 | tree base_object; | |
b8698a0f | 81 | |
3cb960c7 | 82 | /* A list of chrecs. Access functions of the indices. */ |
9771b263 | 83 | vec<tree> access_fns; |
c4ddde1b RG |
84 | |
85 | /* Whether BASE_OBJECT is an access representing the whole object | |
86 | or whether the access could not be constrained. */ | |
87 | bool unconstrained_base; | |
86a07404 IR |
88 | }; |
89 | ||
3cb960c7 ZD |
90 | struct dr_alias |
91 | { | |
92 | /* The alias information that should be used for new pointers to this | |
c4ddde1b | 93 | location. */ |
3cb960c7 | 94 | struct ptr_info_def *ptr_info; |
86a07404 IR |
95 | }; |
96 | ||
b305e3da SP |
97 | /* An integer vector. A vector formally consists of an element of a vector |
98 | space. A vector space is a set that is closed under vector addition | |
99 | and scalar multiplication. In this vector space, an element is a list of | |
100 | integers. */ | |
101 | typedef int *lambda_vector; | |
b305e3da SP |
102 | |
103 | /* An integer matrix. A matrix consists of m vectors of length n (IE | |
104 | all vectors are the same length). */ | |
105 | typedef lambda_vector *lambda_matrix; | |
106 | ||
9f275479 JS |
107 | /* Each vector of the access matrix represents a linear access |
108 | function for a subscript. First elements correspond to the | |
109 | leftmost indices, ie. for a[i][j] the first vector corresponds to | |
110 | the subscript in "i". The elements of a vector are relative to | |
111 | the loop nests in which the data reference is considered, | |
112 | i.e. the vector is relative to the SCoP that provides the context | |
113 | in which this data reference occurs. | |
114 | ||
115 | For example, in | |
116 | ||
117 | | loop_1 | |
118 | | loop_2 | |
119 | | a[i+3][2*j+n-1] | |
120 | ||
b8698a0f | 121 | if "i" varies in loop_1 and "j" varies in loop_2, the access |
9f275479 JS |
122 | matrix with respect to the loop nest {loop_1, loop_2} is: |
123 | ||
124 | | loop_1 loop_2 param_n cst | |
125 | | 1 0 0 3 | |
126 | | 0 2 1 -1 | |
127 | ||
128 | whereas the access matrix with respect to loop_2 considers "i" as | |
129 | a parameter: | |
130 | ||
131 | | loop_2 param_i param_n cst | |
132 | | 0 1 0 3 | |
133 | | 2 0 1 -1 | |
134 | */ | |
135 | struct access_matrix | |
136 | { | |
9771b263 | 137 | vec<loop_p> loop_nest; |
9f275479 | 138 | int nb_induction_vars; |
9771b263 DN |
139 | vec<tree> parameters; |
140 | vec<lambda_vector, va_gc> *matrix; | |
9f275479 JS |
141 | }; |
142 | ||
36174c82 | 143 | #define AM_LOOP_NEST(M) (M)->loop_nest |
9f275479 JS |
144 | #define AM_NB_INDUCTION_VARS(M) (M)->nb_induction_vars |
145 | #define AM_PARAMETERS(M) (M)->parameters | |
146 | #define AM_MATRIX(M) (M)->matrix | |
c3284718 | 147 | #define AM_NB_PARAMETERS(M) (AM_PARAMETERS (M)).length () |
9f275479 JS |
148 | #define AM_CONST_COLUMN_INDEX(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M)) |
149 | #define AM_NB_COLUMNS(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M) + 1) | |
9771b263 | 150 | #define AM_GET_SUBSCRIPT_ACCESS_VECTOR(M, I) AM_MATRIX (M)[I] |
9f275479 JS |
151 | #define AM_GET_ACCESS_MATRIX_ELEMENT(M, I, J) AM_GET_SUBSCRIPT_ACCESS_VECTOR (M, I)[J] |
152 | ||
153 | /* Return the column in the access matrix of LOOP_NUM. */ | |
154 | ||
155 | static inline int | |
156 | am_vector_index_for_loop (struct access_matrix *access_matrix, int loop_num) | |
157 | { | |
36174c82 SP |
158 | int i; |
159 | loop_p l; | |
160 | ||
9771b263 | 161 | for (i = 0; AM_LOOP_NEST (access_matrix).iterate (i, &l); i++) |
36174c82 SP |
162 | if (l->num == loop_num) |
163 | return i; | |
164 | ||
c3284718 | 165 | gcc_unreachable (); |
9f275479 JS |
166 | } |
167 | ||
36d59cf7 | 168 | struct data_reference |
56cf8686 | 169 | { |
56cf8686 | 170 | /* A pointer to the statement that contains this DR. */ |
726a989a | 171 | gimple stmt; |
b8698a0f | 172 | |
3cb960c7 | 173 | /* A pointer to the memory reference. */ |
56cf8686 SP |
174 | tree ref; |
175 | ||
56cf8686 | 176 | /* Auxiliary info specific to a pass. */ |
5417e022 | 177 | void *aux; |
56cf8686 SP |
178 | |
179 | /* True when the data reference is in RHS of a stmt. */ | |
180 | bool is_read; | |
181 | ||
3cb960c7 ZD |
182 | /* Behavior of the memory reference in the innermost loop. */ |
183 | struct innermost_loop_behavior innermost; | |
86a07404 | 184 | |
f8bf9252 | 185 | /* Subscripts of this data reference. */ |
3cb960c7 | 186 | struct indices indices; |
86a07404 | 187 | |
3cb960c7 ZD |
188 | /* Alias information for the data reference. */ |
189 | struct dr_alias alias; | |
56cf8686 | 190 | |
9f275479 JS |
191 | /* Matrix representation for the data access functions. */ |
192 | struct access_matrix *access_matrix; | |
193 | }; | |
ebf78a47 | 194 | |
86a07404 IR |
195 | #define DR_STMT(DR) (DR)->stmt |
196 | #define DR_REF(DR) (DR)->ref | |
3cb960c7 | 197 | #define DR_BASE_OBJECT(DR) (DR)->indices.base_object |
c4ddde1b | 198 | #define DR_UNCONSTRAINED_BASE(DR) (DR)->indices.unconstrained_base |
3cb960c7 | 199 | #define DR_ACCESS_FNS(DR) (DR)->indices.access_fns |
9771b263 DN |
200 | #define DR_ACCESS_FN(DR, I) DR_ACCESS_FNS (DR)[I] |
201 | #define DR_NUM_DIMENSIONS(DR) DR_ACCESS_FNS (DR).length () | |
86a07404 | 202 | #define DR_IS_READ(DR) (DR)->is_read |
b0af49c4 | 203 | #define DR_IS_WRITE(DR) (!DR_IS_READ (DR)) |
3cb960c7 ZD |
204 | #define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address |
205 | #define DR_OFFSET(DR) (DR)->innermost.offset | |
206 | #define DR_INIT(DR) (DR)->innermost.init | |
207 | #define DR_STEP(DR) (DR)->innermost.step | |
3cb960c7 | 208 | #define DR_PTR_INFO(DR) (DR)->alias.ptr_info |
3cb960c7 | 209 | #define DR_ALIGNED_TO(DR) (DR)->innermost.aligned_to |
9f275479 JS |
210 | #define DR_ACCESS_MATRIX(DR) (DR)->access_matrix |
211 | ||
212 | typedef struct data_reference *data_reference_p; | |
56cf8686 SP |
213 | |
214 | enum data_dependence_direction { | |
b8698a0f L |
215 | dir_positive, |
216 | dir_negative, | |
217 | dir_equal, | |
56cf8686 SP |
218 | dir_positive_or_negative, |
219 | dir_positive_or_equal, | |
220 | dir_negative_or_equal, | |
221 | dir_star, | |
222 | dir_independent | |
223 | }; | |
224 | ||
d93817c4 ZD |
225 | /* The description of the grid of iterations that overlap. At most |
226 | two loops are considered at the same time just now, hence at most | |
227 | two functions are needed. For each of the functions, we store | |
228 | the vector of coefficients, f[0] + x * f[1] + y * f[2] + ..., | |
229 | where x, y, ... are variables. */ | |
230 | ||
231 | #define MAX_DIM 2 | |
232 | ||
233 | /* Special values of N. */ | |
234 | #define NO_DEPENDENCE 0 | |
235 | #define NOT_KNOWN (MAX_DIM + 1) | |
236 | #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN) | |
237 | #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN) | |
238 | #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE) | |
239 | ||
9771b263 | 240 | typedef vec<tree> affine_fn; |
d93817c4 ZD |
241 | |
242 | typedef struct | |
243 | { | |
244 | unsigned n; | |
245 | affine_fn fns[MAX_DIM]; | |
246 | } conflict_function; | |
247 | ||
56cf8686 SP |
248 | /* What is a subscript? Given two array accesses a subscript is the |
249 | tuple composed of the access functions for a given dimension. | |
250 | Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three | |
251 | subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts | |
252 | are stored in the data_dependence_relation structure under the form | |
253 | of an array of subscripts. */ | |
254 | ||
36d59cf7 | 255 | struct subscript |
56cf8686 SP |
256 | { |
257 | /* A description of the iterations for which the elements are | |
258 | accessed twice. */ | |
d93817c4 ZD |
259 | conflict_function *conflicting_iterations_in_a; |
260 | conflict_function *conflicting_iterations_in_b; | |
b8698a0f | 261 | |
86df10e3 | 262 | /* This field stores the information about the iteration domain |
56cf8686 | 263 | validity of the dependence relation. */ |
86df10e3 | 264 | tree last_conflict; |
b8698a0f | 265 | |
56cf8686 SP |
266 | /* Distance from the iteration that access a conflicting element in |
267 | A to the iteration that access this same conflicting element in | |
89dbed81 | 268 | B. The distance is a tree scalar expression, i.e. a constant or a |
56cf8686 SP |
269 | symbolic expression, but certainly not a chrec function. */ |
270 | tree distance; | |
56cf8686 SP |
271 | }; |
272 | ||
ebf78a47 | 273 | typedef struct subscript *subscript_p; |
ebf78a47 | 274 | |
56cf8686 SP |
275 | #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a |
276 | #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b | |
86df10e3 | 277 | #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict |
56cf8686 | 278 | #define SUB_DISTANCE(SUB) SUB->distance |
56cf8686 SP |
279 | |
280 | /* A data_dependence_relation represents a relation between two | |
281 | data_references A and B. */ | |
282 | ||
36d59cf7 | 283 | struct data_dependence_relation |
56cf8686 | 284 | { |
b8698a0f | 285 | |
56cf8686 SP |
286 | struct data_reference *a; |
287 | struct data_reference *b; | |
288 | ||
289 | /* A "yes/no/maybe" field for the dependence relation: | |
b8698a0f | 290 | |
56cf8686 SP |
291 | - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence |
292 | relation between A and B, and the description of this relation | |
293 | is given in the SUBSCRIPTS array, | |
b8698a0f | 294 | |
56cf8686 SP |
295 | - when "ARE_DEPENDENT == chrec_known", there is no dependence and |
296 | SUBSCRIPTS is empty, | |
b8698a0f | 297 | |
56cf8686 SP |
298 | - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence, |
299 | but the analyzer cannot be more specific. */ | |
300 | tree are_dependent; | |
b8698a0f | 301 | |
56cf8686 SP |
302 | /* For each subscript in the dependence test, there is an element in |
303 | this array. This is the attribute that labels the edge A->B of | |
304 | the data_dependence_relation. */ | |
9771b263 | 305 | vec<subscript_p> subscripts; |
36d59cf7 | 306 | |
ba42e045 | 307 | /* The analyzed loop nest. */ |
9771b263 | 308 | vec<loop_p> loop_nest; |
86df10e3 | 309 | |
36d59cf7 | 310 | /* The classic direction vector. */ |
9771b263 | 311 | vec<lambda_vector> dir_vects; |
36d59cf7 DB |
312 | |
313 | /* The classic distance vector. */ | |
9771b263 | 314 | vec<lambda_vector> dist_vects; |
71d5b5e1 | 315 | |
8f5929e1 JJ |
316 | /* An index in loop_nest for the innermost loop that varies for |
317 | this data dependence relation. */ | |
318 | unsigned inner_loop; | |
319 | ||
71d5b5e1 SP |
320 | /* Is the dependence reversed with respect to the lexicographic order? */ |
321 | bool reversed_p; | |
8f5929e1 JJ |
322 | |
323 | /* When the dependence relation is affine, it can be represented by | |
324 | a distance vector. */ | |
325 | bool affine_p; | |
326 | ||
327 | /* Set to true when the dependence relation is on the same data | |
328 | access. */ | |
329 | bool self_reference_p; | |
56cf8686 SP |
330 | }; |
331 | ||
0ff4040e | 332 | typedef struct data_dependence_relation *ddr_p; |
0ff4040e | 333 | |
56cf8686 SP |
334 | #define DDR_A(DDR) DDR->a |
335 | #define DDR_B(DDR) DDR->b | |
86df10e3 | 336 | #define DDR_AFFINE_P(DDR) DDR->affine_p |
56cf8686 SP |
337 | #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent |
338 | #define DDR_SUBSCRIPTS(DDR) DDR->subscripts | |
9771b263 DN |
339 | #define DDR_SUBSCRIPT(DDR, I) DDR_SUBSCRIPTS (DDR)[I] |
340 | #define DDR_NUM_SUBSCRIPTS(DDR) DDR_SUBSCRIPTS (DDR).length () | |
ba42e045 SP |
341 | |
342 | #define DDR_LOOP_NEST(DDR) DDR->loop_nest | |
343 | /* The size of the direction/distance vectors: the number of loops in | |
344 | the loop nest. */ | |
9771b263 | 345 | #define DDR_NB_LOOPS(DDR) (DDR_LOOP_NEST (DDR).length ()) |
3d8864c0 | 346 | #define DDR_INNER_LOOP(DDR) DDR->inner_loop |
b3924be9 | 347 | #define DDR_SELF_REFERENCE(DDR) DDR->self_reference_p |
304afda6 SP |
348 | |
349 | #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects) | |
350 | #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects) | |
351 | #define DDR_NUM_DIST_VECTS(DDR) \ | |
9771b263 | 352 | (DDR_DIST_VECTS (DDR).length ()) |
304afda6 | 353 | #define DDR_NUM_DIR_VECTS(DDR) \ |
9771b263 | 354 | (DDR_DIR_VECTS (DDR).length ()) |
304afda6 | 355 | #define DDR_DIR_VECT(DDR, I) \ |
9771b263 | 356 | DDR_DIR_VECTS (DDR)[I] |
304afda6 | 357 | #define DDR_DIST_VECT(DDR, I) \ |
9771b263 | 358 | DDR_DIST_VECTS (DDR)[I] |
71d5b5e1 | 359 | #define DDR_REVERSED_P(DDR) DDR->reversed_p |
56cf8686 SP |
360 | |
361 | \f | |
4e4452b6 | 362 | bool dr_analyze_innermost (struct data_reference *, struct loop *); |
9f275479 | 363 | extern bool compute_data_dependences_for_loop (struct loop *, bool, |
9771b263 DN |
364 | vec<loop_p> *, |
365 | vec<data_reference_p> *, | |
366 | vec<ddr_p> *); | |
a70d6342 | 367 | extern bool compute_data_dependences_for_bb (basic_block, bool, |
9771b263 DN |
368 | vec<data_reference_p> *, |
369 | vec<ddr_p> *); | |
370 | extern void debug_ddrs (vec<ddr_p> ); | |
56cf8686 | 371 | extern void dump_data_reference (FILE *, struct data_reference *); |
7b3b6ae4 LC |
372 | extern void debug (data_reference &ref); |
373 | extern void debug (data_reference *ptr); | |
a37d995a | 374 | extern void debug_data_reference (struct data_reference *); |
9771b263 | 375 | extern void debug_data_references (vec<data_reference_p> ); |
7b3b6ae4 LC |
376 | extern void debug (vec<data_reference_p> &ref); |
377 | extern void debug (vec<data_reference_p> *ptr); | |
ba42e045 | 378 | extern void debug_data_dependence_relation (struct data_dependence_relation *); |
9771b263 | 379 | extern void dump_data_dependence_relations (FILE *, vec<ddr_p> ); |
7b3b6ae4 LC |
380 | extern void debug (vec<ddr_p> &ref); |
381 | extern void debug (vec<ddr_p> *ptr); | |
9771b263 | 382 | extern void debug_data_dependence_relations (vec<ddr_p> ); |
36d59cf7 | 383 | extern void free_dependence_relation (struct data_dependence_relation *); |
9771b263 | 384 | extern void free_dependence_relations (vec<ddr_p> ); |
dea61d92 | 385 | extern void free_data_ref (data_reference_p); |
9771b263 | 386 | extern void free_data_refs (vec<data_reference_p> ); |
f8bf9252 | 387 | extern bool find_data_references_in_stmt (struct loop *, gimple, |
9771b263 | 388 | vec<data_reference_p> *); |
5c640e29 | 389 | extern bool graphite_find_data_references_in_stmt (loop_p, loop_p, gimple, |
9771b263 | 390 | vec<data_reference_p> *); |
fcac74a1 | 391 | tree find_data_references_in_loop (struct loop *, vec<data_reference_p> *); |
5c640e29 | 392 | struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple, bool); |
9771b263 | 393 | extern bool find_loop_nest (struct loop *, vec<loop_p> *); |
aec7ae7d | 394 | extern struct data_dependence_relation *initialize_data_dependence_relation |
9771b263 | 395 | (struct data_reference *, struct data_reference *, vec<loop_p>); |
f20132e7 RG |
396 | extern void compute_affine_dependence (struct data_dependence_relation *, |
397 | loop_p); | |
aec7ae7d | 398 | extern void compute_self_dependence (struct data_dependence_relation *); |
9771b263 DN |
399 | extern bool compute_all_dependences (vec<data_reference_p> , |
400 | vec<ddr_p> *, | |
401 | vec<loop_p>, bool); | |
bfe068c3 | 402 | extern tree find_data_references_in_bb (struct loop *, basic_block, |
9771b263 | 403 | vec<data_reference_p> *); |
f8bf9252 | 404 | |
f8bf9252 | 405 | extern bool dr_may_alias_p (const struct data_reference *, |
02f5d6c5 | 406 | const struct data_reference *, bool); |
bfe068c3 IR |
407 | extern bool dr_equal_offsets_p (struct data_reference *, |
408 | struct data_reference *); | |
c1bf2a39 | 409 | extern void tree_check_data_deps (void); |
ebf78a47 | 410 | |
e1fd038a SP |
411 | |
412 | /* Return true when the base objects of data references A and B are | |
413 | the same memory object. */ | |
414 | ||
415 | static inline bool | |
416 | same_data_refs_base_objects (data_reference_p a, data_reference_p b) | |
417 | { | |
418 | return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b) | |
419 | && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0); | |
420 | } | |
421 | ||
422 | /* Return true when the data references A and B are accessing the same | |
423 | memory object with the same access functions. */ | |
424 | ||
425 | static inline bool | |
426 | same_data_refs (data_reference_p a, data_reference_p b) | |
427 | { | |
428 | unsigned int i; | |
429 | ||
430 | /* The references are exactly the same. */ | |
431 | if (operand_equal_p (DR_REF (a), DR_REF (b), 0)) | |
432 | return true; | |
433 | ||
434 | if (!same_data_refs_base_objects (a, b)) | |
435 | return false; | |
436 | ||
437 | for (i = 0; i < DR_NUM_DIMENSIONS (a); i++) | |
438 | if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i))) | |
439 | return false; | |
440 | ||
441 | return true; | |
442 | } | |
443 | ||
dea61d92 SP |
444 | /* Return true when the DDR contains two data references that have the |
445 | same access functions. */ | |
446 | ||
447 | static inline bool | |
448 | same_access_functions (const struct data_dependence_relation *ddr) | |
449 | { | |
450 | unsigned i; | |
451 | ||
452 | for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) | |
453 | if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i), | |
454 | DR_ACCESS_FN (DDR_B (ddr), i))) | |
455 | return false; | |
456 | ||
457 | return true; | |
458 | } | |
459 | ||
460 | /* Return true when DDR is an anti-dependence relation. */ | |
461 | ||
462 | static inline bool | |
463 | ddr_is_anti_dependent (ddr_p ddr) | |
464 | { | |
465 | return (DDR_ARE_DEPENDENT (ddr) == NULL_TREE | |
466 | && DR_IS_READ (DDR_A (ddr)) | |
b0af49c4 | 467 | && DR_IS_WRITE (DDR_B (ddr)) |
dea61d92 SP |
468 | && !same_access_functions (ddr)); |
469 | } | |
470 | ||
471 | /* Return true when DEPENDENCE_RELATIONS contains an anti-dependence. */ | |
472 | ||
473 | static inline bool | |
9771b263 | 474 | ddrs_have_anti_deps (vec<ddr_p> dependence_relations) |
dea61d92 SP |
475 | { |
476 | unsigned i; | |
477 | ddr_p ddr; | |
478 | ||
9771b263 | 479 | for (i = 0; dependence_relations.iterate (i, &ddr); i++) |
dea61d92 SP |
480 | if (ddr_is_anti_dependent (ddr)) |
481 | return true; | |
482 | ||
483 | return false; | |
484 | } | |
485 | ||
2fd5894f RB |
486 | /* Returns true when all the dependences are computable. */ |
487 | ||
488 | inline bool | |
489 | known_dependences_p (vec<ddr_p> dependence_relations) | |
490 | { | |
491 | ddr_p ddr; | |
492 | unsigned int i; | |
493 | ||
494 | FOR_EACH_VEC_ELT (dependence_relations, i, ddr) | |
495 | if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) | |
496 | return false; | |
497 | ||
498 | return true; | |
499 | } | |
500 | ||
b305e3da SP |
501 | /* Returns the dependence level for a vector DIST of size LENGTH. |
502 | LEVEL = 0 means a lexicographic dependence, i.e. a dependence due | |
503 | to the sequence of statements, not carried by any loop. */ | |
504 | ||
505 | static inline unsigned | |
506 | dependence_level (lambda_vector dist_vect, int length) | |
507 | { | |
508 | int i; | |
509 | ||
510 | for (i = 0; i < length; i++) | |
511 | if (dist_vect[i] != 0) | |
512 | return i + 1; | |
513 | ||
514 | return 0; | |
515 | } | |
516 | ||
dea61d92 SP |
517 | /* Return the dependence level for the DDR relation. */ |
518 | ||
519 | static inline unsigned | |
520 | ddr_dependence_level (ddr_p ddr) | |
521 | { | |
522 | unsigned vector; | |
523 | unsigned level = 0; | |
524 | ||
9771b263 | 525 | if (DDR_DIST_VECTS (ddr).exists ()) |
dea61d92 SP |
526 | level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr)); |
527 | ||
528 | for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++) | |
529 | level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector), | |
530 | DDR_NB_LOOPS (ddr))); | |
531 | return level; | |
532 | } | |
533 | ||
ba42e045 SP |
534 | /* Return the index of the variable VAR in the LOOP_NEST array. */ |
535 | ||
536 | static inline int | |
9771b263 | 537 | index_in_loop_nest (int var, vec<loop_p> loop_nest) |
ba42e045 SP |
538 | { |
539 | struct loop *loopi; | |
540 | int var_index; | |
541 | ||
9771b263 | 542 | for (var_index = 0; loop_nest.iterate (var_index, &loopi); |
ba42e045 SP |
543 | var_index++) |
544 | if (loopi->num == var) | |
545 | break; | |
546 | ||
547 | return var_index; | |
548 | } | |
549 | ||
be6b029b RG |
550 | /* Returns true when the data reference DR the form "A[i] = ..." |
551 | with a stride equal to its unit type size. */ | |
5e37ea0e SP |
552 | |
553 | static inline bool | |
d0582dc1 | 554 | adjacent_dr_p (struct data_reference *dr) |
5e37ea0e | 555 | { |
be6b029b RG |
556 | /* If this is a bitfield store bail out. */ |
557 | if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF | |
558 | && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1))) | |
559 | return false; | |
560 | ||
561 | if (!DR_STEP (dr) | |
562 | || TREE_CODE (DR_STEP (dr)) != INTEGER_CST) | |
563 | return false; | |
564 | ||
565 | return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (DR_STEP (dr)), | |
566 | DR_STEP (dr)), | |
567 | TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)))); | |
5e37ea0e SP |
568 | } |
569 | ||
468c2ac0 DN |
570 | void split_constant_offset (tree , tree *, tree *); |
571 | ||
b305e3da SP |
572 | /* Compute the greatest common divisor of a VECTOR of SIZE numbers. */ |
573 | ||
574 | static inline int | |
575 | lambda_vector_gcd (lambda_vector vector, int size) | |
576 | { | |
577 | int i; | |
578 | int gcd1 = 0; | |
579 | ||
580 | if (size > 0) | |
581 | { | |
582 | gcd1 = vector[0]; | |
583 | for (i = 1; i < size; i++) | |
584 | gcd1 = gcd (gcd1, vector[i]); | |
585 | } | |
586 | return gcd1; | |
587 | } | |
588 | ||
589 | /* Allocate a new vector of given SIZE. */ | |
590 | ||
591 | static inline lambda_vector | |
592 | lambda_vector_new (int size) | |
593 | { | |
594 | return (lambda_vector) ggc_alloc_cleared_atomic (sizeof (int) * size); | |
595 | } | |
596 | ||
597 | /* Clear out vector VEC1 of length SIZE. */ | |
598 | ||
599 | static inline void | |
600 | lambda_vector_clear (lambda_vector vec1, int size) | |
601 | { | |
602 | memset (vec1, 0, size * sizeof (*vec1)); | |
603 | } | |
604 | ||
605 | /* Returns true when the vector V is lexicographically positive, in | |
606 | other words, when the first nonzero element is positive. */ | |
607 | ||
608 | static inline bool | |
609 | lambda_vector_lexico_pos (lambda_vector v, | |
610 | unsigned n) | |
611 | { | |
612 | unsigned i; | |
613 | for (i = 0; i < n; i++) | |
614 | { | |
615 | if (v[i] == 0) | |
616 | continue; | |
617 | if (v[i] < 0) | |
618 | return false; | |
619 | if (v[i] > 0) | |
620 | return true; | |
621 | } | |
622 | return true; | |
623 | } | |
624 | ||
625 | /* Return true if vector VEC1 of length SIZE is the zero vector. */ | |
626 | ||
627 | static inline bool | |
628 | lambda_vector_zerop (lambda_vector vec1, int size) | |
629 | { | |
630 | int i; | |
631 | for (i = 0; i < size; i++) | |
632 | if (vec1[i] != 0) | |
633 | return false; | |
634 | return true; | |
635 | } | |
636 | ||
637 | /* Allocate a matrix of M rows x N cols. */ | |
638 | ||
639 | static inline lambda_matrix | |
640 | lambda_matrix_new (int m, int n, struct obstack *lambda_obstack) | |
641 | { | |
642 | lambda_matrix mat; | |
643 | int i; | |
644 | ||
645 | mat = (lambda_matrix) obstack_alloc (lambda_obstack, | |
646 | sizeof (lambda_vector *) * m); | |
647 | ||
648 | for (i = 0; i < m; i++) | |
649 | mat[i] = lambda_vector_new (n); | |
650 | ||
651 | return mat; | |
652 | } | |
653 | ||
56cf8686 | 654 | #endif /* GCC_TREE_DATA_REF_H */ |