]>
Commit | Line | Data |
---|---|---|
56cf8686 | 1 | /* Data references and dependences detectors. |
ad616de1 | 2 | Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. |
56cf8686 SP |
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 | |
366ccddb KC |
19 | Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA |
20 | 02110-1301, USA. */ | |
56cf8686 SP |
21 | |
22 | /* This pass walks a given loop structure searching for array | |
23 | references. The information about the array accesses is recorded | |
24 | in DATA_REFERENCE structures. | |
25 | ||
26 | The basic test for determining the dependences is: | |
27 | given two access functions chrec1 and chrec2 to a same array, and | |
28 | x and y two vectors from the iteration domain, the same element of | |
29 | the array is accessed twice at iterations x and y if and only if: | |
30 | | chrec1 (x) == chrec2 (y). | |
31 | ||
32 | The goals of this analysis are: | |
33 | ||
34 | - to determine the independence: the relation between two | |
35 | independent accesses is qualified with the chrec_known (this | |
36 | information allows a loop parallelization), | |
37 | ||
38 | - when two data references access the same data, to qualify the | |
39 | dependence relation with classic dependence representations: | |
40 | ||
41 | - distance vectors | |
42 | - direction vectors | |
43 | - loop carried level dependence | |
44 | - polyhedron dependence | |
45 | or with the chains of recurrences based representation, | |
46 | ||
50300b4c | 47 | - to define a knowledge base for storing the data dependence |
56cf8686 SP |
48 | information, |
49 | ||
50 | - to define an interface to access this data. | |
51 | ||
52 | ||
53 | Definitions: | |
54 | ||
55 | - subscript: given two array accesses a subscript is the tuple | |
56 | composed of the access functions for a given dimension. Example: | |
57 | Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts: | |
58 | (f1, g1), (f2, g2), (f3, g3). | |
59 | ||
60 | - Diophantine equation: an equation whose coefficients and | |
61 | solutions are integer constants, for example the equation | |
62 | | 3*x + 2*y = 1 | |
63 | has an integer solution x = 1 and y = -1. | |
64 | ||
65 | References: | |
66 | ||
67 | - "Advanced Compilation for High Performance Computing" by Randy | |
68 | Allen and Ken Kennedy. | |
69 | http://citeseer.ist.psu.edu/goff91practical.html | |
70 | ||
71 | - "Loop Transformations for Restructuring Compilers - The Foundations" | |
72 | by Utpal Banerjee. | |
73 | ||
74 | ||
75 | */ | |
76 | ||
77 | #include "config.h" | |
78 | #include "system.h" | |
79 | #include "coretypes.h" | |
80 | #include "tm.h" | |
56cf8686 SP |
81 | #include "ggc.h" |
82 | #include "tree.h" | |
83 | ||
84 | /* These RTL headers are needed for basic-block.h. */ | |
85 | #include "rtl.h" | |
86 | #include "basic-block.h" | |
87 | #include "diagnostic.h" | |
88 | #include "tree-flow.h" | |
89 | #include "tree-dump.h" | |
90 | #include "timevar.h" | |
91 | #include "cfgloop.h" | |
92 | #include "tree-chrec.h" | |
93 | #include "tree-data-ref.h" | |
94 | #include "tree-scalar-evolution.h" | |
95 | #include "tree-pass.h" | |
56cf8686 | 96 | |
86a07404 IR |
97 | static tree object_analysis (tree, tree, bool, struct data_reference **, |
98 | tree *, tree *, tree *, tree *, tree *, | |
99 | struct ptr_info_def **, subvar_t *); | |
100 | static struct data_reference * init_data_ref (tree, tree, tree, tree, bool, | |
101 | tree, tree, tree, tree, tree, | |
102 | struct ptr_info_def *, | |
103 | enum data_ref_type); | |
104 | ||
105 | /* Determine if PTR and DECL may alias, the result is put in ALIASED. | |
106 | Return FALSE if there is no type memory tag for PTR. | |
107 | */ | |
108 | static bool | |
109 | ptr_decl_may_alias_p (tree ptr, tree decl, | |
110 | struct data_reference *ptr_dr, | |
111 | bool *aliased) | |
112 | { | |
113 | tree tag; | |
114 | ||
115 | gcc_assert (TREE_CODE (ptr) == SSA_NAME && DECL_P (decl)); | |
116 | ||
117 | tag = get_var_ann (SSA_NAME_VAR (ptr))->type_mem_tag; | |
118 | if (!tag) | |
119 | tag = DR_MEMTAG (ptr_dr); | |
120 | if (!tag) | |
121 | return false; | |
122 | ||
123 | *aliased = is_aliased_with (tag, decl); | |
124 | return true; | |
125 | } | |
126 | ||
127 | ||
128 | /* Determine if two pointers may alias, the result is put in ALIASED. | |
129 | Return FALSE if there is no type memory tag for one of the pointers. | |
130 | */ | |
131 | static bool | |
132 | ptr_ptr_may_alias_p (tree ptr_a, tree ptr_b, | |
133 | struct data_reference *dra, | |
134 | struct data_reference *drb, | |
135 | bool *aliased) | |
136 | { | |
137 | tree tag_a, tag_b; | |
138 | ||
139 | tag_a = get_var_ann (SSA_NAME_VAR (ptr_a))->type_mem_tag; | |
140 | if (!tag_a) | |
141 | tag_a = DR_MEMTAG (dra); | |
142 | if (!tag_a) | |
143 | return false; | |
144 | tag_b = get_var_ann (SSA_NAME_VAR (ptr_b))->type_mem_tag; | |
145 | if (!tag_b) | |
146 | tag_b = DR_MEMTAG (drb); | |
147 | if (!tag_b) | |
148 | return false; | |
149 | *aliased = (tag_a == tag_b); | |
150 | return true; | |
151 | } | |
152 | ||
153 | ||
154 | /* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED. | |
155 | Return FALSE if there is no type memory tag for one of the symbols. | |
156 | */ | |
157 | static bool | |
158 | may_alias_p (tree base_a, tree base_b, | |
159 | struct data_reference *dra, | |
160 | struct data_reference *drb, | |
161 | bool *aliased) | |
162 | { | |
163 | if (TREE_CODE (base_a) == ADDR_EXPR || TREE_CODE (base_b) == ADDR_EXPR) | |
164 | { | |
165 | if (TREE_CODE (base_a) == ADDR_EXPR && TREE_CODE (base_b) == ADDR_EXPR) | |
166 | { | |
167 | *aliased = (TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)); | |
168 | return true; | |
169 | } | |
170 | if (TREE_CODE (base_a) == ADDR_EXPR) | |
171 | return ptr_decl_may_alias_p (base_b, TREE_OPERAND (base_a, 0), drb, | |
172 | aliased); | |
173 | else | |
174 | return ptr_decl_may_alias_p (base_a, TREE_OPERAND (base_b, 0), dra, | |
175 | aliased); | |
176 | } | |
177 | ||
178 | return ptr_ptr_may_alias_p (base_a, base_b, dra, drb, aliased); | |
179 | } | |
180 | ||
181 | ||
182 | /* Determine if a pointer (BASE_A) and a record/union access (BASE_B) | |
183 | are not aliased. Return TRUE if they differ. */ | |
184 | static bool | |
185 | record_ptr_differ_p (struct data_reference *dra, | |
186 | struct data_reference *drb) | |
187 | { | |
188 | bool aliased; | |
189 | tree base_a = DR_BASE_OBJECT (dra); | |
190 | tree base_b = DR_BASE_OBJECT (drb); | |
191 | ||
192 | if (TREE_CODE (base_b) != COMPONENT_REF) | |
193 | return false; | |
194 | ||
195 | /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs. | |
196 | For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b. | |
197 | Probably will be unnecessary with struct alias analysis. */ | |
198 | while (TREE_CODE (base_b) == COMPONENT_REF) | |
199 | base_b = TREE_OPERAND (base_b, 0); | |
200 | /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer | |
201 | ((*q)[i]). */ | |
202 | if (TREE_CODE (base_a) == INDIRECT_REF | |
203 | && ((TREE_CODE (base_b) == VAR_DECL | |
204 | && (ptr_decl_may_alias_p (TREE_OPERAND (base_a, 0), base_b, dra, | |
205 | &aliased) | |
206 | && !aliased)) | |
207 | || (TREE_CODE (base_b) == INDIRECT_REF | |
208 | && (ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0), | |
209 | TREE_OPERAND (base_b, 0), dra, drb, | |
210 | &aliased) | |
211 | && !aliased)))) | |
212 | return true; | |
213 | else | |
214 | return false; | |
215 | } | |
216 | ||
217 | ||
218 | /* Determine if an array access (BASE_A) and a record/union access (BASE_B) | |
219 | are not aliased. Return TRUE if they differ. */ | |
220 | static bool | |
221 | record_array_differ_p (struct data_reference *dra, | |
222 | struct data_reference *drb) | |
223 | { | |
224 | bool aliased; | |
225 | tree base_a = DR_BASE_OBJECT (dra); | |
226 | tree base_b = DR_BASE_OBJECT (drb); | |
227 | ||
228 | if (TREE_CODE (base_b) != COMPONENT_REF) | |
229 | return false; | |
230 | ||
231 | /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs. | |
232 | For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b. | |
233 | Probably will be unnecessary with struct alias analysis. */ | |
234 | while (TREE_CODE (base_b) == COMPONENT_REF) | |
235 | base_b = TREE_OPERAND (base_b, 0); | |
236 | ||
237 | /* Compare a record/union access (b.c[i] or p->c[i]) and an array access | |
238 | (a[i]). In case of p->c[i] use alias analysis to verify that p is not | |
239 | pointing to a. */ | |
240 | if (TREE_CODE (base_a) == VAR_DECL | |
241 | && (TREE_CODE (base_b) == VAR_DECL | |
242 | || (TREE_CODE (base_b) == INDIRECT_REF | |
243 | && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, | |
244 | &aliased) | |
245 | && !aliased)))) | |
246 | return true; | |
247 | else | |
248 | return false; | |
249 | } | |
250 | ||
251 | ||
252 | /* Determine if an array access (BASE_A) and a pointer (BASE_B) | |
253 | are not aliased. Return TRUE if they differ. */ | |
254 | static bool | |
255 | array_ptr_differ_p (tree base_a, tree base_b, | |
256 | struct data_reference *drb) | |
257 | { | |
258 | bool aliased; | |
259 | ||
260 | /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the | |
261 | help of alias analysis that p is not pointing to a. */ | |
262 | if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == INDIRECT_REF | |
263 | && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, &aliased) | |
264 | && !aliased)) | |
265 | return true; | |
266 | else | |
267 | return false; | |
268 | } | |
269 | ||
270 | ||
79fe1b3b | 271 | /* This is the simplest data dependence test: determines whether the |
68b26d5c SP |
272 | data references A and B access the same array/region. Returns |
273 | false when the property is not computable at compile time. | |
274 | Otherwise return true, and DIFFER_P will record the result. This | |
275 | utility will not be necessary when alias_sets_conflict_p will be | |
276 | less conservative. */ | |
79fe1b3b | 277 | |
86a07404 IR |
278 | static bool |
279 | base_object_differ_p (struct data_reference *a, | |
280 | struct data_reference *b, | |
281 | bool *differ_p) | |
79fe1b3b | 282 | { |
86a07404 IR |
283 | tree base_a = DR_BASE_OBJECT (a); |
284 | tree base_b = DR_BASE_OBJECT (b); | |
285 | bool aliased; | |
79fe1b3b | 286 | |
e3a8a4ed IR |
287 | if (!base_a || !base_b) |
288 | return false; | |
289 | ||
68b26d5c SP |
290 | /* Determine if same base. Example: for the array accesses |
291 | a[i], b[i] or pointer accesses *a, *b, bases are a, b. */ | |
79fe1b3b DN |
292 | if (base_a == base_b) |
293 | { | |
294 | *differ_p = false; | |
295 | return true; | |
296 | } | |
297 | ||
68b26d5c SP |
298 | /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p) |
299 | and (*q) */ | |
79fe1b3b DN |
300 | if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF |
301 | && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)) | |
302 | { | |
303 | *differ_p = false; | |
304 | return true; | |
305 | } | |
306 | ||
86df10e3 | 307 | /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */ |
79fe1b3b DN |
308 | if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF |
309 | && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0) | |
310 | && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1)) | |
311 | { | |
312 | *differ_p = false; | |
313 | return true; | |
314 | } | |
315 | ||
86df10e3 | 316 | |
68b26d5c | 317 | /* Determine if different bases. */ |
79fe1b3b | 318 | |
68b26d5c | 319 | /* At this point we know that base_a != base_b. However, pointer |
59c4456e KH |
320 | accesses of the form x=(*p) and y=(*q), whose bases are p and q, |
321 | may still be pointing to the same base. In SSAed GIMPLE p and q will | |
322 | be SSA_NAMES in this case. Therefore, here we check if they are | |
323 | really two different declarations. */ | |
79fe1b3b DN |
324 | if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL) |
325 | { | |
326 | *differ_p = true; | |
327 | return true; | |
328 | } | |
329 | ||
86a07404 IR |
330 | /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the |
331 | help of alias analysis that p is not pointing to a. */ | |
332 | if (array_ptr_differ_p (base_a, base_b, b) | |
333 | || array_ptr_differ_p (base_b, base_a, a)) | |
334 | { | |
335 | *differ_p = true; | |
336 | return true; | |
337 | } | |
338 | ||
339 | /* If the bases are pointers ((*q)[i] and (*p)[i]), we check with the | |
340 | help of alias analysis they don't point to the same bases. */ | |
341 | if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF | |
342 | && (may_alias_p (TREE_OPERAND (base_a, 0), TREE_OPERAND (base_b, 0), a, b, | |
343 | &aliased) | |
344 | && !aliased)) | |
345 | { | |
346 | *differ_p = true; | |
347 | return true; | |
348 | } | |
349 | ||
68b26d5c SP |
350 | /* Compare two record/union bases s.a and t.b: s != t or (a != b and |
351 | s and t are not unions). */ | |
79fe1b3b DN |
352 | if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF |
353 | && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL | |
354 | && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL | |
355 | && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0)) | |
356 | || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE | |
357 | && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE | |
358 | && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1)))) | |
359 | { | |
360 | *differ_p = true; | |
361 | return true; | |
362 | } | |
363 | ||
86a07404 IR |
364 | /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer |
365 | ((*q)[i]). */ | |
366 | if (record_ptr_differ_p (a, b) || record_ptr_differ_p (b, a)) | |
367 | { | |
368 | *differ_p = true; | |
369 | return true; | |
370 | } | |
371 | ||
372 | /* Compare a record/union access (b.c[i] or p->c[i]) and an array access | |
373 | (a[i]). In case of p->c[i] use alias analysis to verify that p is not | |
374 | pointing to a. */ | |
375 | if (record_array_differ_p (a, b) || record_array_differ_p (b, a)) | |
79fe1b3b DN |
376 | { |
377 | *differ_p = true; | |
378 | return true; | |
379 | } | |
380 | ||
79fe1b3b DN |
381 | return false; |
382 | } | |
56cf8686 | 383 | |
86a07404 IR |
384 | /* Function base_addr_differ_p. |
385 | ||
386 | This is the simplest data dependence test: determines whether the | |
1f400bbb | 387 | data references DRA and DRB access the same array/region. Returns |
86a07404 | 388 | false when the property is not computable at compile time. |
1f400bbb IR |
389 | Otherwise return true, and DIFFER_P will record the result. |
390 | ||
391 | The algorithm: | |
392 | 1. if (both DRA and DRB are represented as arrays) | |
393 | compare DRA.BASE_OBJECT and DRB.BASE_OBJECT | |
394 | 2. else if (both DRA and DRB are represented as pointers) | |
395 | try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION | |
396 | 3. else if (DRA and DRB are represented differently or 2. fails) | |
397 | only try to prove that the bases are surely different | |
398 | */ | |
86a07404 IR |
399 | |
400 | ||
401 | static bool | |
402 | base_addr_differ_p (struct data_reference *dra, | |
403 | struct data_reference *drb, | |
404 | bool *differ_p) | |
405 | { | |
406 | tree addr_a = DR_BASE_ADDRESS (dra); | |
407 | tree addr_b = DR_BASE_ADDRESS (drb); | |
408 | tree type_a, type_b; | |
409 | bool aliased; | |
410 | ||
411 | if (!addr_a || !addr_b) | |
412 | return false; | |
413 | ||
414 | type_a = TREE_TYPE (addr_a); | |
415 | type_b = TREE_TYPE (addr_b); | |
416 | ||
417 | gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b)); | |
418 | ||
1f400bbb IR |
419 | /* 1. if (both DRA and DRB are represented as arrays) |
420 | compare DRA.BASE_OBJECT and DRB.BASE_OBJECT. */ | |
421 | if (DR_TYPE (dra) == ARRAY_REF_TYPE && DR_TYPE (drb) == ARRAY_REF_TYPE) | |
86a07404 IR |
422 | return base_object_differ_p (dra, drb, differ_p); |
423 | ||
1f400bbb IR |
424 | |
425 | /* 2. else if (both DRA and DRB are represented as pointers) | |
426 | try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION. */ | |
86a07404 IR |
427 | /* If base addresses are the same, we check the offsets, since the access of |
428 | the data-ref is described by {base addr + offset} and its access function, | |
429 | i.e., in order to decide whether the bases of data-refs are the same we | |
430 | compare both base addresses and offsets. */ | |
1f400bbb IR |
431 | if (DR_TYPE (dra) == POINTER_REF_TYPE && DR_TYPE (drb) == POINTER_REF_TYPE |
432 | && (addr_a == addr_b | |
433 | || (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR | |
434 | && TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0)))) | |
86a07404 IR |
435 | { |
436 | /* Compare offsets. */ | |
437 | tree offset_a = DR_OFFSET (dra); | |
438 | tree offset_b = DR_OFFSET (drb); | |
439 | ||
86a07404 IR |
440 | STRIP_NOPS (offset_a); |
441 | STRIP_NOPS (offset_b); | |
442 | ||
443 | /* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle | |
444 | PLUS_EXPR. */ | |
445 | if ((offset_a == offset_b) | |
446 | || (TREE_CODE (offset_a) == MULT_EXPR | |
447 | && TREE_CODE (offset_b) == MULT_EXPR | |
448 | && TREE_OPERAND (offset_a, 0) == TREE_OPERAND (offset_b, 0) | |
449 | && TREE_OPERAND (offset_a, 1) == TREE_OPERAND (offset_b, 1))) | |
450 | { | |
451 | *differ_p = false; | |
452 | return true; | |
453 | } | |
454 | } | |
455 | ||
1f400bbb IR |
456 | /* 3. else if (DRA and DRB are represented differently or 2. fails) |
457 | only try to prove that the bases are surely different. */ | |
458 | ||
86a07404 IR |
459 | /* Apply alias analysis. */ |
460 | if (may_alias_p (addr_a, addr_b, dra, drb, &aliased) && !aliased) | |
461 | { | |
462 | *differ_p = true; | |
463 | return true; | |
464 | } | |
465 | ||
466 | /* An instruction writing through a restricted pointer is "independent" of any | |
467 | instruction reading or writing through a different pointer, in the same | |
468 | block/scope. */ | |
469 | else if ((TYPE_RESTRICT (type_a) && !DR_IS_READ (dra)) | |
470 | || (TYPE_RESTRICT (type_b) && !DR_IS_READ (drb))) | |
471 | { | |
472 | *differ_p = true; | |
473 | return true; | |
474 | } | |
475 | return false; | |
476 | } | |
477 | ||
478 | ||
56cf8686 SP |
479 | /* Returns true iff A divides B. */ |
480 | ||
481 | static inline bool | |
482 | tree_fold_divides_p (tree type, | |
483 | tree a, | |
484 | tree b) | |
485 | { | |
56cf8686 SP |
486 | /* Determines whether (A == gcd (A, B)). */ |
487 | return integer_zerop | |
987b67bc | 488 | (fold_build2 (MINUS_EXPR, type, a, tree_fold_gcd (a, b))); |
56cf8686 SP |
489 | } |
490 | ||
86df10e3 SP |
491 | /* Compute the greatest common denominator of two numbers using |
492 | Euclid's algorithm. */ | |
56cf8686 | 493 | |
86df10e3 SP |
494 | static int |
495 | gcd (int a, int b) | |
56cf8686 | 496 | { |
56cf8686 | 497 | |
86df10e3 | 498 | int x, y, z; |
56cf8686 | 499 | |
86df10e3 SP |
500 | x = abs (a); |
501 | y = abs (b); | |
502 | ||
503 | while (x>0) | |
56cf8686 | 504 | { |
86df10e3 SP |
505 | z = y % x; |
506 | y = x; | |
507 | x = z; | |
56cf8686 | 508 | } |
86df10e3 SP |
509 | |
510 | return (y); | |
511 | } | |
512 | ||
513 | /* Returns true iff A divides B. */ | |
514 | ||
515 | static inline bool | |
516 | int_divides_p (int a, int b) | |
517 | { | |
518 | return ((b % a) == 0); | |
56cf8686 SP |
519 | } |
520 | ||
521 | \f | |
522 | ||
523 | /* Dump into FILE all the data references from DATAREFS. */ | |
524 | ||
525 | void | |
526 | dump_data_references (FILE *file, | |
527 | varray_type datarefs) | |
528 | { | |
529 | unsigned int i; | |
530 | ||
531 | for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++) | |
532 | dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i)); | |
533 | } | |
534 | ||
535 | /* Dump into FILE all the dependence relations from DDR. */ | |
536 | ||
537 | void | |
538 | dump_data_dependence_relations (FILE *file, | |
539 | varray_type ddr) | |
540 | { | |
541 | unsigned int i; | |
542 | ||
543 | for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++) | |
544 | dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i)); | |
545 | } | |
546 | ||
547 | /* Dump function for a DATA_REFERENCE structure. */ | |
548 | ||
549 | void | |
550 | dump_data_reference (FILE *outf, | |
551 | struct data_reference *dr) | |
552 | { | |
553 | unsigned int i; | |
554 | ||
36d59cf7 | 555 | fprintf (outf, "(Data Ref: \n stmt: "); |
56cf8686 SP |
556 | print_generic_stmt (outf, DR_STMT (dr), 0); |
557 | fprintf (outf, " ref: "); | |
558 | print_generic_stmt (outf, DR_REF (dr), 0); | |
559 | fprintf (outf, " base_name: "); | |
86a07404 | 560 | print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0); |
56cf8686 SP |
561 | |
562 | for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++) | |
563 | { | |
564 | fprintf (outf, " Access function %d: ", i); | |
565 | print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0); | |
566 | } | |
567 | fprintf (outf, ")\n"); | |
568 | } | |
569 | ||
86df10e3 SP |
570 | /* Dump function for a SUBSCRIPT structure. */ |
571 | ||
572 | void | |
573 | dump_subscript (FILE *outf, struct subscript *subscript) | |
574 | { | |
575 | tree chrec = SUB_CONFLICTS_IN_A (subscript); | |
576 | ||
577 | fprintf (outf, "\n (subscript \n"); | |
578 | fprintf (outf, " iterations_that_access_an_element_twice_in_A: "); | |
579 | print_generic_stmt (outf, chrec, 0); | |
580 | if (chrec == chrec_known) | |
581 | fprintf (outf, " (no dependence)\n"); | |
582 | else if (chrec_contains_undetermined (chrec)) | |
583 | fprintf (outf, " (don't know)\n"); | |
584 | else | |
585 | { | |
586 | tree last_iteration = SUB_LAST_CONFLICT (subscript); | |
587 | fprintf (outf, " last_conflict: "); | |
588 | print_generic_stmt (outf, last_iteration, 0); | |
589 | } | |
590 | ||
591 | chrec = SUB_CONFLICTS_IN_B (subscript); | |
592 | fprintf (outf, " iterations_that_access_an_element_twice_in_B: "); | |
593 | print_generic_stmt (outf, chrec, 0); | |
594 | if (chrec == chrec_known) | |
595 | fprintf (outf, " (no dependence)\n"); | |
596 | else if (chrec_contains_undetermined (chrec)) | |
597 | fprintf (outf, " (don't know)\n"); | |
598 | else | |
599 | { | |
600 | tree last_iteration = SUB_LAST_CONFLICT (subscript); | |
601 | fprintf (outf, " last_conflict: "); | |
602 | print_generic_stmt (outf, last_iteration, 0); | |
603 | } | |
604 | ||
605 | fprintf (outf, " (Subscript distance: "); | |
606 | print_generic_stmt (outf, SUB_DISTANCE (subscript), 0); | |
607 | fprintf (outf, " )\n"); | |
608 | fprintf (outf, " )\n"); | |
609 | } | |
610 | ||
56cf8686 SP |
611 | /* Dump function for a DATA_DEPENDENCE_RELATION structure. */ |
612 | ||
613 | void | |
614 | dump_data_dependence_relation (FILE *outf, | |
615 | struct data_dependence_relation *ddr) | |
616 | { | |
56cf8686 | 617 | struct data_reference *dra, *drb; |
86df10e3 | 618 | |
56cf8686 SP |
619 | dra = DDR_A (ddr); |
620 | drb = DDR_B (ddr); | |
86df10e3 SP |
621 | fprintf (outf, "(Data Dep: \n"); |
622 | if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) | |
56cf8686 SP |
623 | fprintf (outf, " (don't know)\n"); |
624 | ||
625 | else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) | |
626 | fprintf (outf, " (no dependence)\n"); | |
627 | ||
86df10e3 | 628 | else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) |
56cf8686 | 629 | { |
86df10e3 | 630 | unsigned int i; |
56cf8686 SP |
631 | for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) |
632 | { | |
56cf8686 SP |
633 | fprintf (outf, " access_fn_A: "); |
634 | print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0); | |
635 | fprintf (outf, " access_fn_B: "); | |
636 | print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0); | |
86df10e3 | 637 | dump_subscript (outf, DDR_SUBSCRIPT (ddr, i)); |
56cf8686 | 638 | } |
86df10e3 | 639 | if (DDR_DIST_VECT (ddr)) |
56cf8686 | 640 | { |
86df10e3 SP |
641 | fprintf (outf, " distance_vect: "); |
642 | print_lambda_vector (outf, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr)); | |
643 | } | |
644 | if (DDR_DIR_VECT (ddr)) | |
645 | { | |
646 | fprintf (outf, " direction_vect: "); | |
647 | print_lambda_vector (outf, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr)); | |
56cf8686 | 648 | } |
56cf8686 SP |
649 | } |
650 | ||
651 | fprintf (outf, ")\n"); | |
652 | } | |
653 | ||
654 | ||
655 | ||
656 | /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */ | |
657 | ||
658 | void | |
659 | dump_data_dependence_direction (FILE *file, | |
660 | enum data_dependence_direction dir) | |
661 | { | |
662 | switch (dir) | |
663 | { | |
664 | case dir_positive: | |
665 | fprintf (file, "+"); | |
666 | break; | |
667 | ||
668 | case dir_negative: | |
669 | fprintf (file, "-"); | |
670 | break; | |
671 | ||
672 | case dir_equal: | |
673 | fprintf (file, "="); | |
674 | break; | |
675 | ||
676 | case dir_positive_or_negative: | |
677 | fprintf (file, "+-"); | |
678 | break; | |
679 | ||
680 | case dir_positive_or_equal: | |
681 | fprintf (file, "+="); | |
682 | break; | |
683 | ||
684 | case dir_negative_or_equal: | |
685 | fprintf (file, "-="); | |
686 | break; | |
687 | ||
688 | case dir_star: | |
689 | fprintf (file, "*"); | |
690 | break; | |
691 | ||
692 | default: | |
693 | break; | |
694 | } | |
695 | } | |
696 | ||
86df10e3 SP |
697 | /* Dumps the distance and direction vectors in FILE. DDRS contains |
698 | the dependence relations, and VECT_SIZE is the size of the | |
699 | dependence vectors, or in other words the number of loops in the | |
700 | considered nest. */ | |
701 | ||
702 | void | |
703 | dump_dist_dir_vectors (FILE *file, varray_type ddrs) | |
704 | { | |
705 | unsigned int i; | |
706 | ||
707 | for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++) | |
708 | { | |
709 | struct data_dependence_relation *ddr = | |
710 | (struct data_dependence_relation *) | |
711 | VARRAY_GENERIC_PTR (ddrs, i); | |
712 | if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE | |
713 | && DDR_AFFINE_P (ddr)) | |
714 | { | |
715 | fprintf (file, "DISTANCE_V ("); | |
716 | print_lambda_vector (file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr)); | |
717 | fprintf (file, ")\n"); | |
718 | fprintf (file, "DIRECTION_V ("); | |
719 | print_lambda_vector (file, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr)); | |
720 | fprintf (file, ")\n"); | |
721 | } | |
722 | } | |
723 | fprintf (file, "\n\n"); | |
724 | } | |
725 | ||
726 | /* Dumps the data dependence relations DDRS in FILE. */ | |
727 | ||
728 | void | |
729 | dump_ddrs (FILE *file, varray_type ddrs) | |
730 | { | |
731 | unsigned int i; | |
732 | ||
733 | for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++) | |
734 | { | |
735 | struct data_dependence_relation *ddr = | |
736 | (struct data_dependence_relation *) | |
737 | VARRAY_GENERIC_PTR (ddrs, i); | |
738 | dump_data_dependence_relation (file, ddr); | |
739 | } | |
740 | fprintf (file, "\n\n"); | |
741 | } | |
742 | ||
56cf8686 SP |
743 | \f |
744 | ||
86df10e3 SP |
745 | /* Estimate the number of iterations from the size of the data and the |
746 | access functions. */ | |
747 | ||
748 | static void | |
749 | estimate_niter_from_size_of_data (struct loop *loop, | |
750 | tree opnd0, | |
751 | tree access_fn, | |
752 | tree stmt) | |
753 | { | |
852c19aa | 754 | tree estimation = NULL_TREE; |
86df10e3 SP |
755 | tree array_size, data_size, element_size; |
756 | tree init, step; | |
757 | ||
758 | init = initial_condition (access_fn); | |
759 | step = evolution_part_in_loop_num (access_fn, loop->num); | |
760 | ||
761 | array_size = TYPE_SIZE (TREE_TYPE (opnd0)); | |
762 | element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0))); | |
763 | if (array_size == NULL_TREE | |
9ba64a4a SP |
764 | || TREE_CODE (array_size) != INTEGER_CST |
765 | || TREE_CODE (element_size) != INTEGER_CST) | |
86df10e3 SP |
766 | return; |
767 | ||
987b67bc KH |
768 | data_size = fold_build2 (EXACT_DIV_EXPR, integer_type_node, |
769 | array_size, element_size); | |
86df10e3 SP |
770 | |
771 | if (init != NULL_TREE | |
772 | && step != NULL_TREE | |
773 | && TREE_CODE (init) == INTEGER_CST | |
774 | && TREE_CODE (step) == INTEGER_CST) | |
775 | { | |
852c19aa SP |
776 | tree i_plus_s = fold_build2 (PLUS_EXPR, integer_type_node, init, step); |
777 | tree sign = fold_build2 (GT_EXPR, boolean_type_node, i_plus_s, init); | |
778 | ||
779 | if (sign == boolean_true_node) | |
780 | estimation = fold_build2 (CEIL_DIV_EXPR, integer_type_node, | |
781 | fold_build2 (MINUS_EXPR, integer_type_node, | |
782 | data_size, init), step); | |
783 | ||
784 | /* When the step is negative, as in PR23386: (init = 3, step = | |
785 | 0ffffffff, data_size = 100), we have to compute the | |
786 | estimation as ceil_div (init, 0 - step) + 1. */ | |
787 | else if (sign == boolean_false_node) | |
788 | estimation = | |
789 | fold_build2 (PLUS_EXPR, integer_type_node, | |
790 | fold_build2 (CEIL_DIV_EXPR, integer_type_node, | |
791 | init, | |
792 | fold_build2 (MINUS_EXPR, unsigned_type_node, | |
793 | integer_zero_node, step)), | |
794 | integer_one_node); | |
795 | ||
796 | if (estimation) | |
797 | record_estimate (loop, estimation, boolean_true_node, stmt); | |
86df10e3 SP |
798 | } |
799 | } | |
800 | ||
56cf8686 SP |
801 | /* Given an ARRAY_REF node REF, records its access functions. |
802 | Example: given A[i][3], record in ACCESS_FNS the opnd1 function, | |
89dbed81 KH |
803 | i.e. the constant "3", then recursively call the function on opnd0, |
804 | i.e. the ARRAY_REF "A[i]". The function returns the base name: | |
56cf8686 SP |
805 | "A". */ |
806 | ||
807 | static tree | |
808 | analyze_array_indexes (struct loop *loop, | |
9cbb7989 | 809 | VEC(tree,heap) **access_fns, |
86df10e3 | 810 | tree ref, tree stmt) |
56cf8686 SP |
811 | { |
812 | tree opnd0, opnd1; | |
813 | tree access_fn; | |
814 | ||
815 | opnd0 = TREE_OPERAND (ref, 0); | |
816 | opnd1 = TREE_OPERAND (ref, 1); | |
817 | ||
818 | /* The detection of the evolution function for this data access is | |
819 | postponed until the dependence test. This lazy strategy avoids | |
820 | the computation of access functions that are of no interest for | |
821 | the optimizers. */ | |
822 | access_fn = instantiate_parameters | |
823 | (loop, analyze_scalar_evolution (loop, opnd1)); | |
86df10e3 | 824 | |
79ebd55c | 825 | if (chrec_contains_undetermined (loop->estimated_nb_iterations)) |
86df10e3 | 826 | estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt); |
56cf8686 | 827 | |
9cbb7989 | 828 | VEC_safe_push (tree, heap, *access_fns, access_fn); |
56cf8686 SP |
829 | |
830 | /* Recursively record other array access functions. */ | |
831 | if (TREE_CODE (opnd0) == ARRAY_REF) | |
86df10e3 | 832 | return analyze_array_indexes (loop, access_fns, opnd0, stmt); |
56cf8686 SP |
833 | |
834 | /* Return the base name of the data access. */ | |
835 | else | |
836 | return opnd0; | |
837 | } | |
838 | ||
6cb38cd4 | 839 | /* For a data reference REF contained in the statement STMT, initialize |
56cf8686 SP |
840 | a DATA_REFERENCE structure, and return it. IS_READ flag has to be |
841 | set to true when REF is in the right hand side of an | |
842 | assignment. */ | |
843 | ||
d7770457 | 844 | struct data_reference * |
56cf8686 SP |
845 | analyze_array (tree stmt, tree ref, bool is_read) |
846 | { | |
847 | struct data_reference *res; | |
86a07404 | 848 | VEC(tree,heap) *acc_fns; |
56cf8686 SP |
849 | |
850 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
851 | { | |
852 | fprintf (dump_file, "(analyze_array \n"); | |
853 | fprintf (dump_file, " (ref = "); | |
854 | print_generic_stmt (dump_file, ref, 0); | |
855 | fprintf (dump_file, ")\n"); | |
856 | } | |
857 | ||
36d59cf7 | 858 | res = xmalloc (sizeof (struct data_reference)); |
56cf8686 | 859 | |
56cf8686 SP |
860 | DR_STMT (res) = stmt; |
861 | DR_REF (res) = ref; | |
86a07404 IR |
862 | acc_fns = VEC_alloc (tree, heap, 3); |
863 | DR_BASE_OBJECT (res) = analyze_array_indexes | |
864 | (loop_containing_stmt (stmt), &acc_fns, ref, stmt); | |
865 | DR_TYPE (res) = ARRAY_REF_TYPE; | |
866 | DR_SET_ACCESS_FNS (res, acc_fns); | |
56cf8686 | 867 | DR_IS_READ (res) = is_read; |
86a07404 IR |
868 | DR_BASE_ADDRESS (res) = NULL_TREE; |
869 | DR_OFFSET (res) = NULL_TREE; | |
870 | DR_INIT (res) = NULL_TREE; | |
871 | DR_STEP (res) = NULL_TREE; | |
872 | DR_OFFSET_MISALIGNMENT (res) = NULL_TREE; | |
873 | DR_MEMTAG (res) = NULL_TREE; | |
874 | DR_PTR_INFO (res) = NULL; | |
56cf8686 SP |
875 | |
876 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
877 | fprintf (dump_file, ")\n"); | |
878 | ||
879 | return res; | |
880 | } | |
881 | ||
86a07404 IR |
882 | |
883 | /* Analyze an indirect memory reference, REF, that comes from STMT. | |
884 | IS_READ is true if this is an indirect load, and false if it is | |
885 | an indirect store. | |
886 | Return a new data reference structure representing the indirect_ref, or | |
887 | NULL if we cannot describe the access function. */ | |
888 | ||
889 | static struct data_reference * | |
890 | analyze_indirect_ref (tree stmt, tree ref, bool is_read) | |
891 | { | |
892 | struct loop *loop = loop_containing_stmt (stmt); | |
893 | tree ptr_ref = TREE_OPERAND (ref, 0); | |
894 | tree access_fn = analyze_scalar_evolution (loop, ptr_ref); | |
895 | tree init = initial_condition_in_loop_num (access_fn, loop->num); | |
896 | tree base_address = NULL_TREE, evolution, step = NULL_TREE; | |
897 | struct ptr_info_def *ptr_info = NULL; | |
898 | ||
899 | if (TREE_CODE (ptr_ref) == SSA_NAME) | |
900 | ptr_info = SSA_NAME_PTR_INFO (ptr_ref); | |
901 | ||
902 | STRIP_NOPS (init); | |
903 | if (access_fn == chrec_dont_know || !init || init == chrec_dont_know) | |
904 | { | |
905 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
906 | { | |
907 | fprintf (dump_file, "\nBad access function of ptr: "); | |
908 | print_generic_expr (dump_file, ref, TDF_SLIM); | |
909 | fprintf (dump_file, "\n"); | |
910 | } | |
911 | return NULL; | |
912 | } | |
913 | ||
914 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
915 | { | |
916 | fprintf (dump_file, "\nAccess function of ptr: "); | |
917 | print_generic_expr (dump_file, access_fn, TDF_SLIM); | |
918 | fprintf (dump_file, "\n"); | |
919 | } | |
920 | ||
921 | if (!expr_invariant_in_loop_p (loop, init)) | |
922 | { | |
923 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
924 | fprintf (dump_file, "\ninitial condition is not loop invariant.\n"); | |
925 | } | |
926 | else | |
927 | { | |
928 | base_address = init; | |
929 | evolution = evolution_part_in_loop_num (access_fn, loop->num); | |
930 | if (evolution != chrec_dont_know) | |
931 | { | |
932 | if (!evolution) | |
933 | step = ssize_int (0); | |
934 | else | |
935 | { | |
936 | if (TREE_CODE (evolution) == INTEGER_CST) | |
937 | step = fold_convert (ssizetype, evolution); | |
938 | else | |
939 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
940 | fprintf (dump_file, "\nnon constant step for ptr access.\n"); | |
941 | } | |
942 | } | |
943 | else | |
944 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
945 | fprintf (dump_file, "\nunknown evolution of ptr.\n"); | |
946 | } | |
947 | return init_data_ref (stmt, ref, NULL_TREE, access_fn, is_read, base_address, | |
948 | NULL_TREE, step, NULL_TREE, NULL_TREE, | |
949 | ptr_info, POINTER_REF_TYPE); | |
950 | } | |
951 | ||
6cb38cd4 | 952 | /* For a data reference REF contained in the statement STMT, initialize |
56cf8686 SP |
953 | a DATA_REFERENCE structure, and return it. */ |
954 | ||
955 | struct data_reference * | |
956 | init_data_ref (tree stmt, | |
957 | tree ref, | |
958 | tree base, | |
79fe1b3b | 959 | tree access_fn, |
86a07404 IR |
960 | bool is_read, |
961 | tree base_address, | |
962 | tree init_offset, | |
963 | tree step, | |
964 | tree misalign, | |
965 | tree memtag, | |
966 | struct ptr_info_def *ptr_info, | |
967 | enum data_ref_type type) | |
56cf8686 SP |
968 | { |
969 | struct data_reference *res; | |
86a07404 | 970 | VEC(tree,heap) *acc_fns; |
56cf8686 SP |
971 | |
972 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
973 | { | |
974 | fprintf (dump_file, "(init_data_ref \n"); | |
975 | fprintf (dump_file, " (ref = "); | |
976 | print_generic_stmt (dump_file, ref, 0); | |
977 | fprintf (dump_file, ")\n"); | |
978 | } | |
979 | ||
36d59cf7 | 980 | res = xmalloc (sizeof (struct data_reference)); |
56cf8686 | 981 | |
56cf8686 SP |
982 | DR_STMT (res) = stmt; |
983 | DR_REF (res) = ref; | |
86a07404 IR |
984 | DR_BASE_OBJECT (res) = base; |
985 | DR_TYPE (res) = type; | |
986 | acc_fns = VEC_alloc (tree, heap, 3); | |
987 | DR_SET_ACCESS_FNS (res, acc_fns); | |
9cbb7989 | 988 | VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn); |
79fe1b3b | 989 | DR_IS_READ (res) = is_read; |
86a07404 IR |
990 | DR_BASE_ADDRESS (res) = base_address; |
991 | DR_OFFSET (res) = init_offset; | |
992 | DR_INIT (res) = NULL_TREE; | |
993 | DR_STEP (res) = step; | |
994 | DR_OFFSET_MISALIGNMENT (res) = misalign; | |
995 | DR_MEMTAG (res) = memtag; | |
996 | DR_PTR_INFO (res) = ptr_info; | |
56cf8686 SP |
997 | |
998 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
999 | fprintf (dump_file, ")\n"); | |
1000 | ||
1001 | return res; | |
1002 | } | |
1003 | ||
1004 | \f | |
1005 | ||
86a07404 IR |
1006 | /* Function strip_conversions |
1007 | ||
1008 | Strip conversions that don't narrow the mode. */ | |
1009 | ||
1010 | static tree | |
1011 | strip_conversion (tree expr) | |
1012 | { | |
1013 | tree to, ti, oprnd0; | |
1014 | ||
1015 | while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR) | |
1016 | { | |
1017 | to = TREE_TYPE (expr); | |
1018 | oprnd0 = TREE_OPERAND (expr, 0); | |
1019 | ti = TREE_TYPE (oprnd0); | |
1020 | ||
1021 | if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti)) | |
1022 | return NULL_TREE; | |
1023 | if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti))) | |
1024 | return NULL_TREE; | |
1025 | ||
1026 | expr = oprnd0; | |
1027 | } | |
1028 | return expr; | |
1029 | } | |
1030 | \f | |
1031 | ||
1032 | /* Function analyze_offset_expr | |
1033 | ||
1034 | Given an offset expression EXPR received from get_inner_reference, analyze | |
1035 | it and create an expression for INITIAL_OFFSET by substituting the variables | |
1036 | of EXPR with initial_condition of the corresponding access_fn in the loop. | |
1037 | E.g., | |
1038 | for i | |
1039 | for (j = 3; j < N; j++) | |
1040 | a[j].b[i][j] = 0; | |
1041 | ||
1042 | For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be | |
1043 | substituted, since its access_fn in the inner loop is i. 'j' will be | |
1044 | substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where | |
1045 | C` = 3 * C_j + C. | |
1046 | ||
1047 | Compute MISALIGN (the misalignment of the data reference initial access from | |
1048 | its base). Misalignment can be calculated only if all the variables can be | |
1049 | substituted with constants, otherwise, we record maximum possible alignment | |
1050 | in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN | |
1051 | will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be | |
1052 | recorded in ALIGNED_TO. | |
1053 | ||
1054 | STEP is an evolution of the data reference in this loop in bytes. | |
1055 | In the above example, STEP is C_j. | |
1056 | ||
1057 | Return FALSE, if the analysis fails, e.g., there is no access_fn for a | |
1058 | variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO | |
1059 | and STEP) are NULL_TREEs. Otherwise, return TRUE. | |
1060 | ||
1061 | */ | |
1062 | ||
1063 | static bool | |
1064 | analyze_offset_expr (tree expr, | |
1065 | struct loop *loop, | |
1066 | tree *initial_offset, | |
1067 | tree *misalign, | |
1068 | tree *aligned_to, | |
1069 | tree *step) | |
1070 | { | |
1071 | tree oprnd0; | |
1072 | tree oprnd1; | |
1073 | tree left_offset = ssize_int (0); | |
1074 | tree right_offset = ssize_int (0); | |
1075 | tree left_misalign = ssize_int (0); | |
1076 | tree right_misalign = ssize_int (0); | |
1077 | tree left_step = ssize_int (0); | |
1078 | tree right_step = ssize_int (0); | |
1079 | enum tree_code code; | |
1080 | tree init, evolution; | |
1081 | tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE; | |
1082 | ||
1083 | *step = NULL_TREE; | |
1084 | *misalign = NULL_TREE; | |
1085 | *aligned_to = NULL_TREE; | |
1086 | *initial_offset = NULL_TREE; | |
1087 | ||
1088 | /* Strip conversions that don't narrow the mode. */ | |
1089 | expr = strip_conversion (expr); | |
1090 | if (!expr) | |
1091 | return false; | |
1092 | ||
1093 | /* Stop conditions: | |
1094 | 1. Constant. */ | |
1095 | if (TREE_CODE (expr) == INTEGER_CST) | |
1096 | { | |
1097 | *initial_offset = fold_convert (ssizetype, expr); | |
1098 | *misalign = fold_convert (ssizetype, expr); | |
1099 | *step = ssize_int (0); | |
1100 | return true; | |
1101 | } | |
1102 | ||
1103 | /* 2. Variable. Try to substitute with initial_condition of the corresponding | |
1104 | access_fn in the current loop. */ | |
1105 | if (SSA_VAR_P (expr)) | |
1106 | { | |
1107 | tree access_fn = analyze_scalar_evolution (loop, expr); | |
1108 | ||
1109 | if (access_fn == chrec_dont_know) | |
1110 | /* No access_fn. */ | |
1111 | return false; | |
1112 | ||
1113 | init = initial_condition_in_loop_num (access_fn, loop->num); | |
1114 | if (init == expr && !expr_invariant_in_loop_p (loop, init)) | |
1115 | /* Not enough information: may be not loop invariant. | |
1116 | E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its | |
1117 | initial_condition is D, but it depends on i - loop's induction | |
1118 | variable. */ | |
1119 | return false; | |
1120 | ||
1121 | evolution = evolution_part_in_loop_num (access_fn, loop->num); | |
1122 | if (evolution && TREE_CODE (evolution) != INTEGER_CST) | |
1123 | /* Evolution is not constant. */ | |
1124 | return false; | |
1125 | ||
1126 | if (TREE_CODE (init) == INTEGER_CST) | |
1127 | *misalign = fold_convert (ssizetype, init); | |
1128 | else | |
1129 | /* Not constant, misalignment cannot be calculated. */ | |
1130 | *misalign = NULL_TREE; | |
1131 | ||
1132 | *initial_offset = fold_convert (ssizetype, init); | |
1133 | ||
1134 | *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0); | |
1135 | return true; | |
1136 | } | |
1137 | ||
1138 | /* Recursive computation. */ | |
1139 | if (!BINARY_CLASS_P (expr)) | |
1140 | { | |
1141 | /* We expect to get binary expressions (PLUS/MINUS and MULT). */ | |
1142 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1143 | { | |
1144 | fprintf (dump_file, "\nNot binary expression "); | |
1145 | print_generic_expr (dump_file, expr, TDF_SLIM); | |
1146 | fprintf (dump_file, "\n"); | |
1147 | } | |
1148 | return false; | |
1149 | } | |
1150 | oprnd0 = TREE_OPERAND (expr, 0); | |
1151 | oprnd1 = TREE_OPERAND (expr, 1); | |
1152 | ||
1153 | if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign, | |
1154 | &left_aligned_to, &left_step) | |
1155 | || !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign, | |
1156 | &right_aligned_to, &right_step)) | |
1157 | return false; | |
1158 | ||
1159 | /* The type of the operation: plus, minus or mult. */ | |
1160 | code = TREE_CODE (expr); | |
1161 | switch (code) | |
1162 | { | |
1163 | case MULT_EXPR: | |
1164 | if (TREE_CODE (right_offset) != INTEGER_CST) | |
1165 | /* RIGHT_OFFSET can be not constant. For example, for arrays of variable | |
1166 | sized types. | |
1167 | FORNOW: We don't support such cases. */ | |
1168 | return false; | |
1169 | ||
1170 | /* Strip conversions that don't narrow the mode. */ | |
1171 | left_offset = strip_conversion (left_offset); | |
1172 | if (!left_offset) | |
1173 | return false; | |
1174 | /* Misalignment computation. */ | |
1175 | if (SSA_VAR_P (left_offset)) | |
1176 | { | |
1177 | /* If the left side contains variables that can't be substituted with | |
1178 | constants, the misalignment is unknown. However, if the right side | |
1179 | is a multiple of some alignment, we know that the expression is | |
1180 | aligned to it. Therefore, we record such maximum possible value. | |
1181 | */ | |
1182 | *misalign = NULL_TREE; | |
1183 | *aligned_to = ssize_int (highest_pow2_factor (right_offset)); | |
1184 | } | |
1185 | else | |
1186 | { | |
1187 | /* The left operand was successfully substituted with constant. */ | |
1188 | if (left_misalign) | |
1189 | { | |
1190 | /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is | |
1191 | NULL_TREE. */ | |
1192 | *misalign = size_binop (code, left_misalign, right_misalign); | |
1193 | if (left_aligned_to && right_aligned_to) | |
1194 | *aligned_to = size_binop (MIN_EXPR, left_aligned_to, | |
1195 | right_aligned_to); | |
1196 | else | |
1197 | *aligned_to = left_aligned_to ? | |
1198 | left_aligned_to : right_aligned_to; | |
1199 | } | |
1200 | else | |
1201 | *misalign = NULL_TREE; | |
1202 | } | |
1203 | ||
1204 | /* Step calculation. */ | |
1205 | /* Multiply the step by the right operand. */ | |
1206 | *step = size_binop (MULT_EXPR, left_step, right_offset); | |
1207 | break; | |
1208 | ||
1209 | case PLUS_EXPR: | |
1210 | case MINUS_EXPR: | |
1211 | /* Combine the recursive calculations for step and misalignment. */ | |
1212 | *step = size_binop (code, left_step, right_step); | |
1213 | ||
1214 | /* Unknown alignment. */ | |
1215 | if ((!left_misalign && !left_aligned_to) | |
1216 | || (!right_misalign && !right_aligned_to)) | |
1217 | { | |
1218 | *misalign = NULL_TREE; | |
1219 | *aligned_to = NULL_TREE; | |
1220 | break; | |
1221 | } | |
1222 | ||
1223 | if (left_misalign && right_misalign) | |
1224 | *misalign = size_binop (code, left_misalign, right_misalign); | |
1225 | else | |
1226 | *misalign = left_misalign ? left_misalign : right_misalign; | |
1227 | ||
1228 | if (left_aligned_to && right_aligned_to) | |
1229 | *aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to); | |
1230 | else | |
1231 | *aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to; | |
1232 | ||
1233 | break; | |
1234 | ||
1235 | default: | |
1236 | gcc_unreachable (); | |
1237 | } | |
1238 | ||
1239 | /* Compute offset. */ | |
1240 | *initial_offset = fold_convert (ssizetype, | |
1241 | fold_build2 (code, TREE_TYPE (left_offset), | |
1242 | left_offset, | |
1243 | right_offset)); | |
1244 | return true; | |
1245 | } | |
1246 | ||
1247 | /* Function address_analysis | |
1248 | ||
1249 | Return the BASE of the address expression EXPR. | |
1250 | Also compute the OFFSET from BASE, MISALIGN and STEP. | |
1251 | ||
1252 | Input: | |
1253 | EXPR - the address expression that is being analyzed | |
1254 | STMT - the statement that contains EXPR or its original memory reference | |
1255 | IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR | |
1256 | DR - data_reference struct for the original memory reference | |
1257 | ||
1258 | Output: | |
1259 | BASE (returned value) - the base of the data reference EXPR. | |
1260 | INITIAL_OFFSET - initial offset of EXPR from BASE (an expression) | |
1261 | MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the | |
1262 | computation is impossible | |
1263 | ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be | |
1264 | calculated (doesn't depend on variables) | |
1265 | STEP - evolution of EXPR in the loop | |
1266 | ||
1267 | If something unexpected is encountered (an unsupported form of data-ref), | |
1268 | then NULL_TREE is returned. | |
1269 | */ | |
1270 | ||
1271 | static tree | |
1272 | address_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr, | |
1273 | tree *offset, tree *misalign, tree *aligned_to, tree *step) | |
1274 | { | |
1275 | tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1; | |
1276 | tree address_offset = ssize_int (0), address_misalign = ssize_int (0); | |
1277 | tree dummy, address_aligned_to = NULL_TREE; | |
1278 | struct ptr_info_def *dummy1; | |
1279 | subvar_t dummy2; | |
1280 | ||
1281 | switch (TREE_CODE (expr)) | |
1282 | { | |
1283 | case PLUS_EXPR: | |
1284 | case MINUS_EXPR: | |
1285 | /* EXPR is of form {base +/- offset} (or {offset +/- base}). */ | |
1286 | oprnd0 = TREE_OPERAND (expr, 0); | |
1287 | oprnd1 = TREE_OPERAND (expr, 1); | |
1288 | ||
1289 | STRIP_NOPS (oprnd0); | |
1290 | STRIP_NOPS (oprnd1); | |
1291 | ||
1292 | /* Recursively try to find the base of the address contained in EXPR. | |
1293 | For offset, the returned base will be NULL. */ | |
1294 | base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset, | |
1295 | &address_misalign, &address_aligned_to, | |
1296 | step); | |
1297 | ||
1298 | base_addr1 = address_analysis (oprnd1, stmt, is_read, dr, &address_offset, | |
1299 | &address_misalign, &address_aligned_to, | |
1300 | step); | |
1301 | ||
1302 | /* We support cases where only one of the operands contains an | |
1303 | address. */ | |
1304 | if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1)) | |
1305 | { | |
1306 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1307 | { | |
1308 | fprintf (dump_file, | |
1309 | "\neither more than one address or no addresses in expr "); | |
1310 | print_generic_expr (dump_file, expr, TDF_SLIM); | |
1311 | fprintf (dump_file, "\n"); | |
1312 | } | |
1313 | return NULL_TREE; | |
1314 | } | |
1315 | ||
1316 | /* To revert STRIP_NOPS. */ | |
1317 | oprnd0 = TREE_OPERAND (expr, 0); | |
1318 | oprnd1 = TREE_OPERAND (expr, 1); | |
1319 | ||
1320 | offset_expr = base_addr0 ? | |
1321 | fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0); | |
1322 | ||
1323 | /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is | |
1324 | a number, we can add it to the misalignment value calculated for base, | |
1325 | otherwise, misalignment is NULL. */ | |
1326 | if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign) | |
1327 | { | |
1328 | *misalign = size_binop (TREE_CODE (expr), address_misalign, | |
1329 | offset_expr); | |
1330 | *aligned_to = address_aligned_to; | |
1331 | } | |
1332 | else | |
1333 | { | |
1334 | *misalign = NULL_TREE; | |
1335 | *aligned_to = NULL_TREE; | |
1336 | } | |
1337 | ||
1338 | /* Combine offset (from EXPR {base + offset}) with the offset calculated | |
1339 | for base. */ | |
1340 | *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr); | |
1341 | return base_addr0 ? base_addr0 : base_addr1; | |
1342 | ||
1343 | case ADDR_EXPR: | |
1344 | base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read, | |
1345 | &dr, offset, misalign, aligned_to, step, | |
1346 | &dummy, &dummy1, &dummy2); | |
1347 | return base_address; | |
1348 | ||
1349 | case SSA_NAME: | |
1350 | if (!POINTER_TYPE_P (TREE_TYPE (expr))) | |
1351 | { | |
1352 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1353 | { | |
1354 | fprintf (dump_file, "\nnot pointer SSA_NAME "); | |
1355 | print_generic_expr (dump_file, expr, TDF_SLIM); | |
1356 | fprintf (dump_file, "\n"); | |
1357 | } | |
1358 | return NULL_TREE; | |
1359 | } | |
1360 | *aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr)))); | |
1361 | *misalign = ssize_int (0); | |
1362 | *offset = ssize_int (0); | |
1363 | *step = ssize_int (0); | |
1364 | return expr; | |
1365 | ||
1366 | default: | |
1367 | return NULL_TREE; | |
1368 | } | |
1369 | } | |
1370 | ||
1371 | ||
1372 | /* Function object_analysis | |
1373 | ||
1374 | Create a data-reference structure DR for MEMREF. | |
1375 | Return the BASE of the data reference MEMREF if the analysis is possible. | |
1376 | Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP. | |
1377 | E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset | |
1378 | 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET | |
1379 | instantiated with initial_conditions of access_functions of variables, | |
1380 | and STEP is the evolution of the DR_REF in this loop. | |
1381 | ||
1382 | Function get_inner_reference is used for the above in case of ARRAY_REF and | |
1383 | COMPONENT_REF. | |
1384 | ||
1385 | The structure of the function is as follows: | |
1386 | Part 1: | |
1387 | Case 1. For handled_component_p refs | |
1388 | 1.1 build data-reference structure for MEMREF | |
1389 | 1.2 call get_inner_reference | |
1390 | 1.2.1 analyze offset expr received from get_inner_reference | |
1391 | (fall through with BASE) | |
1392 | Case 2. For declarations | |
1393 | 2.1 set MEMTAG | |
1394 | Case 3. For INDIRECT_REFs | |
1395 | 3.1 build data-reference structure for MEMREF | |
1396 | 3.2 analyze evolution and initial condition of MEMREF | |
1397 | 3.3 set data-reference structure for MEMREF | |
1398 | 3.4 call address_analysis to analyze INIT of the access function | |
1399 | 3.5 extract memory tag | |
1400 | ||
1401 | Part 2: | |
1402 | Combine the results of object and address analysis to calculate | |
1403 | INITIAL_OFFSET, STEP and misalignment info. | |
1404 | ||
1405 | Input: | |
1406 | MEMREF - the memory reference that is being analyzed | |
1407 | STMT - the statement that contains MEMREF | |
1408 | IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF | |
1409 | ||
1410 | Output: | |
1411 | BASE_ADDRESS (returned value) - the base address of the data reference MEMREF | |
1412 | E.g, if MEMREF is a.b[k].c[i][j] the returned | |
1413 | base is &a. | |
1414 | DR - data_reference struct for MEMREF | |
1415 | INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression) | |
1416 | MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of | |
1417 | ALIGNMENT or NULL_TREE if the computation is impossible | |
1418 | ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be | |
1419 | calculated (doesn't depend on variables) | |
1420 | STEP - evolution of the DR_REF in the loop | |
1421 | MEMTAG - memory tag for aliasing purposes | |
1422 | PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME | |
1423 | SUBVARS - Sub-variables of the variable | |
1424 | ||
1425 | If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned, | |
1426 | but DR can be created anyway. | |
1427 | ||
1428 | */ | |
1429 | ||
1430 | static tree | |
1431 | object_analysis (tree memref, tree stmt, bool is_read, | |
1432 | struct data_reference **dr, tree *offset, tree *misalign, | |
1433 | tree *aligned_to, tree *step, tree *memtag, | |
1434 | struct ptr_info_def **ptr_info, subvar_t *subvars) | |
1435 | { | |
1436 | tree base = NULL_TREE, base_address = NULL_TREE; | |
1437 | tree object_offset = ssize_int (0), object_misalign = ssize_int (0); | |
1438 | tree object_step = ssize_int (0), address_step = ssize_int (0); | |
1439 | tree address_offset = ssize_int (0), address_misalign = ssize_int (0); | |
1440 | HOST_WIDE_INT pbitsize, pbitpos; | |
1441 | tree poffset, bit_pos_in_bytes; | |
1442 | enum machine_mode pmode; | |
1443 | int punsignedp, pvolatilep; | |
1444 | tree ptr_step = ssize_int (0), ptr_init = NULL_TREE; | |
1445 | struct loop *loop = loop_containing_stmt (stmt); | |
1446 | struct data_reference *ptr_dr = NULL; | |
1447 | tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE; | |
1448 | ||
1449 | *ptr_info = NULL; | |
1450 | ||
1451 | /* Part 1: */ | |
1452 | /* Case 1. handled_component_p refs. */ | |
1453 | if (handled_component_p (memref)) | |
1454 | { | |
1455 | /* 1.1 build data-reference structure for MEMREF. */ | |
1456 | /* TODO: handle COMPONENT_REFs. */ | |
1457 | if (!(*dr)) | |
1458 | { | |
1459 | if (TREE_CODE (memref) == ARRAY_REF) | |
1460 | *dr = analyze_array (stmt, memref, is_read); | |
1461 | else | |
1462 | { | |
1463 | /* FORNOW. */ | |
1464 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1465 | { | |
1466 | fprintf (dump_file, "\ndata-ref of unsupported type "); | |
1467 | print_generic_expr (dump_file, memref, TDF_SLIM); | |
1468 | fprintf (dump_file, "\n"); | |
1469 | } | |
1470 | return NULL_TREE; | |
1471 | } | |
1472 | } | |
1473 | ||
1474 | /* 1.2 call get_inner_reference. */ | |
1475 | /* Find the base and the offset from it. */ | |
1476 | base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset, | |
1477 | &pmode, &punsignedp, &pvolatilep, false); | |
1478 | if (!base) | |
1479 | { | |
1480 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1481 | { | |
1482 | fprintf (dump_file, "\nfailed to get inner ref for "); | |
1483 | print_generic_expr (dump_file, memref, TDF_SLIM); | |
1484 | fprintf (dump_file, "\n"); | |
1485 | } | |
1486 | return NULL_TREE; | |
1487 | } | |
1488 | ||
1489 | /* 1.2.1 analyze offset expr received from get_inner_reference. */ | |
1490 | if (poffset | |
1491 | && !analyze_offset_expr (poffset, loop, &object_offset, | |
1492 | &object_misalign, &object_aligned_to, | |
1493 | &object_step)) | |
1494 | { | |
1495 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1496 | { | |
1497 | fprintf (dump_file, "\nfailed to compute offset or step for "); | |
1498 | print_generic_expr (dump_file, memref, TDF_SLIM); | |
1499 | fprintf (dump_file, "\n"); | |
1500 | } | |
1501 | return NULL_TREE; | |
1502 | } | |
1503 | ||
1504 | /* Add bit position to OFFSET and MISALIGN. */ | |
1505 | ||
1506 | bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT); | |
1507 | /* Check that there is no remainder in bits. */ | |
1508 | if (pbitpos%BITS_PER_UNIT) | |
1509 | { | |
1510 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1511 | fprintf (dump_file, "\nbit offset alignment.\n"); | |
1512 | return NULL_TREE; | |
1513 | } | |
1514 | object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset); | |
1515 | if (object_misalign) | |
1516 | object_misalign = size_binop (PLUS_EXPR, object_misalign, | |
1517 | bit_pos_in_bytes); | |
1518 | ||
1519 | memref = base; /* To continue analysis of BASE. */ | |
1520 | /* fall through */ | |
1521 | } | |
1522 | ||
1523 | /* Part 1: Case 2. Declarations. */ | |
1524 | if (DECL_P (memref)) | |
1525 | { | |
1526 | /* We expect to get a decl only if we already have a DR. */ | |
1527 | if (!(*dr)) | |
1528 | { | |
1529 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1530 | { | |
1531 | fprintf (dump_file, "\nunhandled decl "); | |
1532 | print_generic_expr (dump_file, memref, TDF_SLIM); | |
1533 | fprintf (dump_file, "\n"); | |
1534 | } | |
1535 | return NULL_TREE; | |
1536 | } | |
1537 | ||
1538 | /* TODO: if during the analysis of INDIRECT_REF we get to an object, put | |
1539 | the object in BASE_OBJECT field if we can prove that this is O.K., | |
1540 | i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT. | |
1541 | (e.g., if the object is an array base 'a', where 'a[N]', we must prove | |
1542 | that every access with 'p' (the original INDIRECT_REF based on '&a') | |
1543 | in the loop is within the array boundaries - from a[0] to a[N-1]). | |
1544 | Otherwise, our alias analysis can be incorrect. | |
1545 | Even if an access function based on BASE_OBJECT can't be build, update | |
1546 | BASE_OBJECT field to enable us to prove that two data-refs are | |
1547 | different (without access function, distance analysis is impossible). | |
1548 | */ | |
1549 | if (SSA_VAR_P (memref) && var_can_have_subvars (memref)) | |
1550 | *subvars = get_subvars_for_var (memref); | |
1551 | base_address = build_fold_addr_expr (memref); | |
1552 | /* 2.1 set MEMTAG. */ | |
1553 | *memtag = memref; | |
1554 | } | |
1555 | ||
1556 | /* Part 1: Case 3. INDIRECT_REFs. */ | |
1557 | else if (TREE_CODE (memref) == INDIRECT_REF) | |
1558 | { | |
1559 | tree ptr_ref = TREE_OPERAND (memref, 0); | |
1560 | if (TREE_CODE (ptr_ref) == SSA_NAME) | |
1561 | *ptr_info = SSA_NAME_PTR_INFO (ptr_ref); | |
1562 | ||
1563 | /* 3.1 build data-reference structure for MEMREF. */ | |
1564 | ptr_dr = analyze_indirect_ref (stmt, memref, is_read); | |
1565 | if (!ptr_dr) | |
1566 | { | |
1567 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1568 | { | |
1569 | fprintf (dump_file, "\nfailed to create dr for "); | |
1570 | print_generic_expr (dump_file, memref, TDF_SLIM); | |
1571 | fprintf (dump_file, "\n"); | |
1572 | } | |
1573 | return NULL_TREE; | |
1574 | } | |
1575 | ||
1576 | /* 3.2 analyze evolution and initial condition of MEMREF. */ | |
1577 | ptr_step = DR_STEP (ptr_dr); | |
1578 | ptr_init = DR_BASE_ADDRESS (ptr_dr); | |
1579 | if (!ptr_init || !ptr_step || !POINTER_TYPE_P (TREE_TYPE (ptr_init))) | |
1580 | { | |
1581 | *dr = (*dr) ? *dr : ptr_dr; | |
1582 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1583 | { | |
1584 | fprintf (dump_file, "\nbad pointer access "); | |
1585 | print_generic_expr (dump_file, memref, TDF_SLIM); | |
1586 | fprintf (dump_file, "\n"); | |
1587 | } | |
1588 | return NULL_TREE; | |
1589 | } | |
1590 | ||
1591 | if (integer_zerop (ptr_step) && !(*dr)) | |
1592 | { | |
1593 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1594 | fprintf (dump_file, "\nptr is loop invariant.\n"); | |
1595 | *dr = ptr_dr; | |
1596 | return NULL_TREE; | |
1597 | ||
1598 | /* If there exists DR for MEMREF, we are analyzing the base of | |
1599 | handled component (PTR_INIT), which not necessary has evolution in | |
1600 | the loop. */ | |
1601 | } | |
1602 | object_step = size_binop (PLUS_EXPR, object_step, ptr_step); | |
1603 | ||
1604 | /* 3.3 set data-reference structure for MEMREF. */ | |
1605 | if (!*dr) | |
1606 | *dr = ptr_dr; | |
1607 | ||
1608 | /* 3.4 call address_analysis to analyze INIT of the access | |
1609 | function. */ | |
1610 | base_address = address_analysis (ptr_init, stmt, is_read, *dr, | |
1611 | &address_offset, &address_misalign, | |
1612 | &address_aligned_to, &address_step); | |
1613 | if (!base_address) | |
1614 | { | |
1615 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1616 | { | |
1617 | fprintf (dump_file, "\nfailed to analyze address "); | |
1618 | print_generic_expr (dump_file, ptr_init, TDF_SLIM); | |
1619 | fprintf (dump_file, "\n"); | |
1620 | } | |
1621 | return NULL_TREE; | |
1622 | } | |
1623 | ||
1624 | /* 3.5 extract memory tag. */ | |
1625 | switch (TREE_CODE (base_address)) | |
1626 | { | |
1627 | case SSA_NAME: | |
1628 | *memtag = get_var_ann (SSA_NAME_VAR (base_address))->type_mem_tag; | |
1629 | if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME) | |
1630 | *memtag = get_var_ann ( | |
1631 | SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->type_mem_tag; | |
1632 | break; | |
1633 | case ADDR_EXPR: | |
1634 | *memtag = TREE_OPERAND (base_address, 0); | |
1635 | break; | |
1636 | default: | |
1637 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1638 | { | |
1639 | fprintf (dump_file, "\nno memtag for "); | |
1640 | print_generic_expr (dump_file, memref, TDF_SLIM); | |
1641 | fprintf (dump_file, "\n"); | |
1642 | } | |
1643 | *memtag = NULL_TREE; | |
1644 | break; | |
1645 | } | |
1646 | } | |
1647 | ||
1648 | if (!base_address) | |
1649 | { | |
1650 | /* MEMREF cannot be analyzed. */ | |
1651 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1652 | { | |
1653 | fprintf (dump_file, "\ndata-ref of unsupported type "); | |
1654 | print_generic_expr (dump_file, memref, TDF_SLIM); | |
1655 | fprintf (dump_file, "\n"); | |
1656 | } | |
1657 | return NULL_TREE; | |
1658 | } | |
1659 | ||
1660 | if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag)) | |
1661 | *subvars = get_subvars_for_var (*memtag); | |
1662 | ||
1663 | /* Part 2: Combine the results of object and address analysis to calculate | |
1664 | INITIAL_OFFSET, STEP and misalignment info. */ | |
1665 | *offset = size_binop (PLUS_EXPR, object_offset, address_offset); | |
1666 | ||
1667 | if ((!object_misalign && !object_aligned_to) | |
1668 | || (!address_misalign && !address_aligned_to)) | |
1669 | { | |
1670 | *misalign = NULL_TREE; | |
1671 | *aligned_to = NULL_TREE; | |
1672 | } | |
1673 | else | |
1674 | { | |
1675 | if (object_misalign && address_misalign) | |
1676 | *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign); | |
1677 | else | |
1678 | *misalign = object_misalign ? object_misalign : address_misalign; | |
1679 | if (object_aligned_to && address_aligned_to) | |
1680 | *aligned_to = size_binop (MIN_EXPR, object_aligned_to, | |
1681 | address_aligned_to); | |
1682 | else | |
1683 | *aligned_to = object_aligned_to ? | |
1684 | object_aligned_to : address_aligned_to; | |
1685 | } | |
1686 | *step = size_binop (PLUS_EXPR, object_step, address_step); | |
1687 | ||
1688 | return base_address; | |
1689 | } | |
1690 | ||
1691 | /* Function analyze_offset. | |
1692 | ||
1693 | Extract INVARIANT and CONSTANT parts from OFFSET. | |
1694 | ||
1695 | */ | |
1696 | static void | |
1697 | analyze_offset (tree offset, tree *invariant, tree *constant) | |
1698 | { | |
1699 | tree op0, op1, constant_0, constant_1, invariant_0, invariant_1; | |
1700 | enum tree_code code = TREE_CODE (offset); | |
1701 | ||
1702 | *invariant = NULL_TREE; | |
1703 | *constant = NULL_TREE; | |
1704 | ||
1705 | /* Not PLUS/MINUS expression - recursion stop condition. */ | |
1706 | if (code != PLUS_EXPR && code != MINUS_EXPR) | |
1707 | { | |
1708 | if (TREE_CODE (offset) == INTEGER_CST) | |
1709 | *constant = offset; | |
1710 | else | |
1711 | *invariant = offset; | |
1712 | return; | |
1713 | } | |
1714 | ||
1715 | op0 = TREE_OPERAND (offset, 0); | |
1716 | op1 = TREE_OPERAND (offset, 1); | |
1717 | ||
1718 | /* Recursive call with the operands. */ | |
1719 | analyze_offset (op0, &invariant_0, &constant_0); | |
1720 | analyze_offset (op1, &invariant_1, &constant_1); | |
1721 | ||
1722 | /* Combine the results. */ | |
1723 | *constant = constant_0 ? constant_0 : constant_1; | |
1724 | if (invariant_0 && invariant_1) | |
1725 | *invariant = | |
1726 | fold (build (code, TREE_TYPE (invariant_0), invariant_0, invariant_1)); | |
1727 | else | |
1728 | *invariant = invariant_0 ? invariant_0 : invariant_1; | |
1729 | } | |
1730 | ||
1731 | ||
1732 | /* Function create_data_ref. | |
1733 | ||
1734 | Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS, | |
1735 | DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO, | |
1736 | DR_MEMTAG, and DR_POINTSTO_INFO fields. | |
1737 | ||
1738 | Input: | |
1739 | MEMREF - the memory reference that is being analyzed | |
1740 | STMT - the statement that contains MEMREF | |
1741 | IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF | |
1742 | ||
1743 | Output: | |
1744 | DR (returned value) - data_reference struct for MEMREF | |
1745 | */ | |
1746 | ||
1747 | static struct data_reference * | |
1748 | create_data_ref (tree memref, tree stmt, bool is_read) | |
1749 | { | |
1750 | struct data_reference *dr = NULL; | |
1751 | tree base_address, offset, step, misalign, memtag; | |
1752 | struct loop *loop = loop_containing_stmt (stmt); | |
1753 | tree invariant = NULL_TREE, constant = NULL_TREE; | |
1754 | tree type_size, init_cond; | |
1755 | struct ptr_info_def *ptr_info; | |
1756 | subvar_t subvars = NULL; | |
1757 | tree aligned_to; | |
1758 | ||
1759 | if (!memref) | |
1760 | return NULL; | |
1761 | ||
1762 | base_address = object_analysis (memref, stmt, is_read, &dr, &offset, | |
1763 | &misalign, &aligned_to, &step, &memtag, | |
1764 | &ptr_info, &subvars); | |
1765 | if (!dr || !base_address) | |
1766 | { | |
1767 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1768 | { | |
1769 | fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for "); | |
1770 | print_generic_expr (dump_file, memref, TDF_SLIM); | |
1771 | fprintf (dump_file, "\n"); | |
1772 | } | |
1773 | return NULL; | |
1774 | } | |
1775 | ||
1776 | DR_BASE_ADDRESS (dr) = base_address; | |
1777 | DR_OFFSET (dr) = offset; | |
1778 | DR_INIT (dr) = ssize_int (0); | |
1779 | DR_STEP (dr) = step; | |
1780 | DR_OFFSET_MISALIGNMENT (dr) = misalign; | |
1781 | DR_ALIGNED_TO (dr) = aligned_to; | |
1782 | DR_MEMTAG (dr) = memtag; | |
1783 | DR_PTR_INFO (dr) = ptr_info; | |
1784 | DR_SUBVARS (dr) = subvars; | |
1785 | ||
1786 | type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)))); | |
1787 | ||
1788 | /* Change the access function for INIDIRECT_REFs, according to | |
1789 | DR_BASE_ADDRESS. Analyze OFFSET calculated in object_analysis. OFFSET is | |
1790 | an expression that can contain loop invariant expressions and constants. | |
1791 | We put the constant part in the initial condition of the access function | |
1792 | (for data dependence tests), and in DR_INIT of the data-ref. The loop | |
1793 | invariant part is put in DR_OFFSET. | |
1794 | The evolution part of the access function is STEP calculated in | |
1795 | object_analysis divided by the size of data type. | |
1796 | */ | |
1797 | if (!DR_BASE_OBJECT (dr)) | |
1798 | { | |
1799 | tree access_fn; | |
1800 | tree new_step; | |
1801 | ||
1802 | /* Extract CONSTANT and INVARIANT from OFFSET, and put them in DR_INIT and | |
1803 | DR_OFFSET fields of DR. */ | |
1804 | analyze_offset (offset, &invariant, &constant); | |
1805 | if (constant) | |
1806 | { | |
1807 | DR_INIT (dr) = fold_convert (ssizetype, constant); | |
1808 | init_cond = fold (build (TRUNC_DIV_EXPR, TREE_TYPE (constant), | |
1809 | constant, type_size)); | |
1810 | } | |
1811 | else | |
1812 | DR_INIT (dr) = init_cond = ssize_int (0);; | |
1813 | ||
1814 | if (invariant) | |
1815 | DR_OFFSET (dr) = invariant; | |
1816 | else | |
1817 | DR_OFFSET (dr) = ssize_int (0); | |
1818 | ||
1819 | /* Update access function. */ | |
1820 | access_fn = DR_ACCESS_FN (dr, 0); | |
1821 | new_step = size_binop (TRUNC_DIV_EXPR, | |
1822 | fold_convert (ssizetype, step), type_size); | |
1823 | ||
1824 | access_fn = chrec_replace_initial_condition (access_fn, init_cond); | |
1825 | access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step); | |
1826 | ||
1827 | VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn); | |
1828 | } | |
1829 | ||
1830 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1831 | { | |
1832 | struct ptr_info_def *pi = DR_PTR_INFO (dr); | |
1833 | ||
1834 | fprintf (dump_file, "\nCreated dr for "); | |
1835 | print_generic_expr (dump_file, memref, TDF_SLIM); | |
1836 | fprintf (dump_file, "\n\tbase_address: "); | |
1837 | print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM); | |
1838 | fprintf (dump_file, "\n\toffset from base address: "); | |
1839 | print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM); | |
1840 | fprintf (dump_file, "\n\tconstant offset from base address: "); | |
1841 | print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM); | |
1842 | fprintf (dump_file, "\n\tbase_object: "); | |
1843 | print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM); | |
1844 | fprintf (dump_file, "\n\tstep: "); | |
1845 | print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM); | |
1846 | fprintf (dump_file, "B\n\tmisalignment from base: "); | |
1847 | print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM); | |
1848 | if (DR_OFFSET_MISALIGNMENT (dr)) | |
1849 | fprintf (dump_file, "B"); | |
1850 | if (DR_ALIGNED_TO (dr)) | |
1851 | { | |
1852 | fprintf (dump_file, "\n\taligned to: "); | |
1853 | print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM); | |
1854 | } | |
1855 | fprintf (dump_file, "\n\tmemtag: "); | |
1856 | print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM); | |
1857 | fprintf (dump_file, "\n"); | |
1858 | if (pi && pi->name_mem_tag) | |
1859 | { | |
1860 | fprintf (dump_file, "\n\tnametag: "); | |
1861 | print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM); | |
1862 | fprintf (dump_file, "\n"); | |
1863 | } | |
1864 | } | |
1865 | return dr; | |
1866 | } | |
1867 | ||
1868 | ||
86df10e3 SP |
1869 | /* Returns true when all the functions of a tree_vec CHREC are the |
1870 | same. */ | |
1871 | ||
1872 | static bool | |
1873 | all_chrecs_equal_p (tree chrec) | |
1874 | { | |
1875 | int j; | |
1876 | ||
1877 | for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++) | |
1878 | { | |
1879 | tree chrec_j = TREE_VEC_ELT (chrec, j); | |
1880 | tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1); | |
1881 | if (!integer_zerop | |
1882 | (chrec_fold_minus | |
1883 | (integer_type_node, chrec_j, chrec_j_1))) | |
1884 | return false; | |
1885 | } | |
1886 | return true; | |
1887 | } | |
1888 | ||
1889 | /* Determine for each subscript in the data dependence relation DDR | |
1890 | the distance. */ | |
56cf8686 | 1891 | |
b52485c6 | 1892 | void |
86df10e3 | 1893 | compute_subscript_distance (struct data_dependence_relation *ddr) |
56cf8686 SP |
1894 | { |
1895 | if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) | |
1896 | { | |
1897 | unsigned int i; | |
1898 | ||
1899 | for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) | |
1900 | { | |
1901 | tree conflicts_a, conflicts_b, difference; | |
1902 | struct subscript *subscript; | |
1903 | ||
1904 | subscript = DDR_SUBSCRIPT (ddr, i); | |
1905 | conflicts_a = SUB_CONFLICTS_IN_A (subscript); | |
1906 | conflicts_b = SUB_CONFLICTS_IN_B (subscript); | |
86df10e3 SP |
1907 | |
1908 | if (TREE_CODE (conflicts_a) == TREE_VEC) | |
1909 | { | |
1910 | if (!all_chrecs_equal_p (conflicts_a)) | |
1911 | { | |
1912 | SUB_DISTANCE (subscript) = chrec_dont_know; | |
1913 | return; | |
1914 | } | |
1915 | else | |
1916 | conflicts_a = TREE_VEC_ELT (conflicts_a, 0); | |
1917 | } | |
1918 | ||
1919 | if (TREE_CODE (conflicts_b) == TREE_VEC) | |
1920 | { | |
1921 | if (!all_chrecs_equal_p (conflicts_b)) | |
1922 | { | |
1923 | SUB_DISTANCE (subscript) = chrec_dont_know; | |
1924 | return; | |
1925 | } | |
1926 | else | |
1927 | conflicts_b = TREE_VEC_ELT (conflicts_b, 0); | |
1928 | } | |
1929 | ||
1930 | difference = chrec_fold_minus | |
56cf8686 SP |
1931 | (integer_type_node, conflicts_b, conflicts_a); |
1932 | ||
1933 | if (evolution_function_is_constant_p (difference)) | |
1934 | SUB_DISTANCE (subscript) = difference; | |
1935 | ||
1936 | else | |
1937 | SUB_DISTANCE (subscript) = chrec_dont_know; | |
1938 | } | |
1939 | } | |
1940 | } | |
1941 | ||
1942 | /* Initialize a ddr. */ | |
1943 | ||
1944 | struct data_dependence_relation * | |
1945 | initialize_data_dependence_relation (struct data_reference *a, | |
1946 | struct data_reference *b) | |
1947 | { | |
1948 | struct data_dependence_relation *res; | |
79fe1b3b | 1949 | bool differ_p; |
86a07404 | 1950 | unsigned int i; |
56cf8686 | 1951 | |
36d59cf7 | 1952 | res = xmalloc (sizeof (struct data_dependence_relation)); |
56cf8686 SP |
1953 | DDR_A (res) = a; |
1954 | DDR_B (res) = b; | |
1955 | ||
86a07404 IR |
1956 | if (a == NULL || b == NULL) |
1957 | { | |
1958 | DDR_ARE_DEPENDENT (res) = chrec_dont_know; | |
1959 | return res; | |
1960 | } | |
1961 | ||
1962 | /* When A and B are arrays and their dimensions differ, we directly | |
1963 | initialize the relation to "there is no dependence": chrec_known. */ | |
1964 | if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b) | |
1965 | && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)) | |
1966 | { | |
1967 | DDR_ARE_DEPENDENT (res) = chrec_known; | |
1968 | return res; | |
1969 | } | |
56cf8686 | 1970 | |
86a07404 IR |
1971 | /* Compare the bases of the data-refs. */ |
1972 | if (!base_addr_differ_p (a, b, &differ_p)) | |
56cf8686 | 1973 | { |
86a07404 IR |
1974 | /* Can't determine whether the data-refs access the same memory |
1975 | region. */ | |
1976 | DDR_ARE_DEPENDENT (res) = chrec_dont_know; | |
1977 | return res; | |
1978 | } | |
1979 | if (differ_p) | |
1980 | { | |
1981 | DDR_ARE_DEPENDENT (res) = chrec_known; | |
1982 | return res; | |
1983 | } | |
1984 | ||
1985 | DDR_AFFINE_P (res) = true; | |
1986 | DDR_ARE_DEPENDENT (res) = NULL_TREE; | |
1987 | DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a)); | |
1988 | DDR_SIZE_VECT (res) = 0; | |
1989 | DDR_DIST_VECT (res) = NULL; | |
1990 | DDR_DIR_VECT (res) = NULL; | |
56cf8686 | 1991 | |
86a07404 IR |
1992 | for (i = 0; i < DR_NUM_DIMENSIONS (a); i++) |
1993 | { | |
1994 | struct subscript *subscript; | |
56cf8686 | 1995 | |
86a07404 IR |
1996 | subscript = xmalloc (sizeof (struct subscript)); |
1997 | SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know; | |
1998 | SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know; | |
1999 | SUB_LAST_CONFLICT (subscript) = chrec_dont_know; | |
2000 | SUB_DISTANCE (subscript) = chrec_dont_know; | |
2001 | VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript); | |
56cf8686 SP |
2002 | } |
2003 | ||
2004 | return res; | |
2005 | } | |
2006 | ||
2007 | /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap | |
2008 | description. */ | |
2009 | ||
2010 | static inline void | |
2011 | finalize_ddr_dependent (struct data_dependence_relation *ddr, | |
2012 | tree chrec) | |
2013 | { | |
36d59cf7 DB |
2014 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2015 | { | |
2016 | fprintf (dump_file, "(dependence classified: "); | |
2017 | print_generic_expr (dump_file, chrec, 0); | |
2018 | fprintf (dump_file, ")\n"); | |
2019 | } | |
2020 | ||
56cf8686 SP |
2021 | DDR_ARE_DEPENDENT (ddr) = chrec; |
2022 | varray_clear (DDR_SUBSCRIPTS (ddr)); | |
2023 | } | |
2024 | ||
86df10e3 SP |
2025 | /* The dependence relation DDR cannot be represented by a distance |
2026 | vector. */ | |
2027 | ||
2028 | static inline void | |
2029 | non_affine_dependence_relation (struct data_dependence_relation *ddr) | |
2030 | { | |
2031 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2032 | fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n"); | |
2033 | ||
2034 | DDR_AFFINE_P (ddr) = false; | |
2035 | } | |
2036 | ||
56cf8686 SP |
2037 | \f |
2038 | ||
2039 | /* This section contains the classic Banerjee tests. */ | |
2040 | ||
2041 | /* Returns true iff CHREC_A and CHREC_B are not dependent on any index | |
2042 | variables, i.e., if the ZIV (Zero Index Variable) test is true. */ | |
2043 | ||
2044 | static inline bool | |
2045 | ziv_subscript_p (tree chrec_a, | |
2046 | tree chrec_b) | |
2047 | { | |
2048 | return (evolution_function_is_constant_p (chrec_a) | |
2049 | && evolution_function_is_constant_p (chrec_b)); | |
2050 | } | |
2051 | ||
2052 | /* Returns true iff CHREC_A and CHREC_B are dependent on an index | |
2053 | variable, i.e., if the SIV (Single Index Variable) test is true. */ | |
2054 | ||
2055 | static bool | |
2056 | siv_subscript_p (tree chrec_a, | |
2057 | tree chrec_b) | |
2058 | { | |
2059 | if ((evolution_function_is_constant_p (chrec_a) | |
2060 | && evolution_function_is_univariate_p (chrec_b)) | |
2061 | || (evolution_function_is_constant_p (chrec_b) | |
2062 | && evolution_function_is_univariate_p (chrec_a))) | |
2063 | return true; | |
2064 | ||
2065 | if (evolution_function_is_univariate_p (chrec_a) | |
2066 | && evolution_function_is_univariate_p (chrec_b)) | |
2067 | { | |
2068 | switch (TREE_CODE (chrec_a)) | |
2069 | { | |
2070 | case POLYNOMIAL_CHREC: | |
2071 | switch (TREE_CODE (chrec_b)) | |
2072 | { | |
2073 | case POLYNOMIAL_CHREC: | |
2074 | if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b)) | |
2075 | return false; | |
2076 | ||
2077 | default: | |
2078 | return true; | |
2079 | } | |
2080 | ||
2081 | default: | |
2082 | return true; | |
2083 | } | |
2084 | } | |
2085 | ||
2086 | return false; | |
2087 | } | |
2088 | ||
2089 | /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and | |
2090 | *OVERLAPS_B are initialized to the functions that describe the | |
2091 | relation between the elements accessed twice by CHREC_A and | |
2092 | CHREC_B. For k >= 0, the following property is verified: | |
2093 | ||
2094 | CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ | |
2095 | ||
2096 | static void | |
2097 | analyze_ziv_subscript (tree chrec_a, | |
2098 | tree chrec_b, | |
2099 | tree *overlaps_a, | |
86df10e3 SP |
2100 | tree *overlaps_b, |
2101 | tree *last_conflicts) | |
56cf8686 SP |
2102 | { |
2103 | tree difference; | |
2104 | ||
2105 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2106 | fprintf (dump_file, "(analyze_ziv_subscript \n"); | |
2107 | ||
2108 | difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b); | |
2109 | ||
2110 | switch (TREE_CODE (difference)) | |
2111 | { | |
2112 | case INTEGER_CST: | |
2113 | if (integer_zerop (difference)) | |
2114 | { | |
2115 | /* The difference is equal to zero: the accessed index | |
2116 | overlaps for each iteration in the loop. */ | |
2117 | *overlaps_a = integer_zero_node; | |
2118 | *overlaps_b = integer_zero_node; | |
86df10e3 | 2119 | *last_conflicts = chrec_dont_know; |
56cf8686 SP |
2120 | } |
2121 | else | |
2122 | { | |
2123 | /* The accesses do not overlap. */ | |
2124 | *overlaps_a = chrec_known; | |
86df10e3 SP |
2125 | *overlaps_b = chrec_known; |
2126 | *last_conflicts = integer_zero_node; | |
56cf8686 SP |
2127 | } |
2128 | break; | |
2129 | ||
2130 | default: | |
2131 | /* We're not sure whether the indexes overlap. For the moment, | |
2132 | conservatively answer "don't know". */ | |
2133 | *overlaps_a = chrec_dont_know; | |
86df10e3 SP |
2134 | *overlaps_b = chrec_dont_know; |
2135 | *last_conflicts = chrec_dont_know; | |
56cf8686 SP |
2136 | break; |
2137 | } | |
2138 | ||
2139 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2140 | fprintf (dump_file, ")\n"); | |
2141 | } | |
2142 | ||
2143 | /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a | |
2144 | constant, and CHREC_B is an affine function. *OVERLAPS_A and | |
2145 | *OVERLAPS_B are initialized to the functions that describe the | |
2146 | relation between the elements accessed twice by CHREC_A and | |
2147 | CHREC_B. For k >= 0, the following property is verified: | |
2148 | ||
2149 | CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ | |
2150 | ||
2151 | static void | |
2152 | analyze_siv_subscript_cst_affine (tree chrec_a, | |
2153 | tree chrec_b, | |
2154 | tree *overlaps_a, | |
86df10e3 SP |
2155 | tree *overlaps_b, |
2156 | tree *last_conflicts) | |
56cf8686 SP |
2157 | { |
2158 | bool value0, value1, value2; | |
2159 | tree difference = chrec_fold_minus | |
2160 | (integer_type_node, CHREC_LEFT (chrec_b), chrec_a); | |
2161 | ||
2162 | if (!chrec_is_positive (initial_condition (difference), &value0)) | |
2163 | { | |
2164 | *overlaps_a = chrec_dont_know; | |
2165 | *overlaps_b = chrec_dont_know; | |
86df10e3 | 2166 | *last_conflicts = chrec_dont_know; |
56cf8686 SP |
2167 | return; |
2168 | } | |
2169 | else | |
2170 | { | |
2171 | if (value0 == false) | |
2172 | { | |
2173 | if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1)) | |
2174 | { | |
2175 | *overlaps_a = chrec_dont_know; | |
2176 | *overlaps_b = chrec_dont_know; | |
86df10e3 | 2177 | *last_conflicts = chrec_dont_know; |
56cf8686 SP |
2178 | return; |
2179 | } | |
2180 | else | |
2181 | { | |
2182 | if (value1 == true) | |
2183 | { | |
2184 | /* Example: | |
2185 | chrec_a = 12 | |
2186 | chrec_b = {10, +, 1} | |
2187 | */ | |
2188 | ||
2189 | if (tree_fold_divides_p | |
2190 | (integer_type_node, CHREC_RIGHT (chrec_b), difference)) | |
2191 | { | |
2192 | *overlaps_a = integer_zero_node; | |
987b67bc KH |
2193 | *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node, |
2194 | fold_build1 (ABS_EXPR, | |
2195 | integer_type_node, | |
2196 | difference), | |
2197 | CHREC_RIGHT (chrec_b)); | |
86df10e3 | 2198 | *last_conflicts = integer_one_node; |
56cf8686 SP |
2199 | return; |
2200 | } | |
2201 | ||
2202 | /* When the step does not divides the difference, there are | |
2203 | no overlaps. */ | |
2204 | else | |
2205 | { | |
2206 | *overlaps_a = chrec_known; | |
2207 | *overlaps_b = chrec_known; | |
86df10e3 | 2208 | *last_conflicts = integer_zero_node; |
56cf8686 SP |
2209 | return; |
2210 | } | |
2211 | } | |
2212 | ||
2213 | else | |
2214 | { | |
2215 | /* Example: | |
2216 | chrec_a = 12 | |
2217 | chrec_b = {10, +, -1} | |
2218 | ||
2219 | In this case, chrec_a will not overlap with chrec_b. */ | |
2220 | *overlaps_a = chrec_known; | |
2221 | *overlaps_b = chrec_known; | |
86df10e3 | 2222 | *last_conflicts = integer_zero_node; |
56cf8686 SP |
2223 | return; |
2224 | } | |
2225 | } | |
2226 | } | |
2227 | else | |
2228 | { | |
2229 | if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2)) | |
2230 | { | |
2231 | *overlaps_a = chrec_dont_know; | |
2232 | *overlaps_b = chrec_dont_know; | |
86df10e3 | 2233 | *last_conflicts = chrec_dont_know; |
56cf8686 SP |
2234 | return; |
2235 | } | |
2236 | else | |
2237 | { | |
2238 | if (value2 == false) | |
2239 | { | |
2240 | /* Example: | |
2241 | chrec_a = 3 | |
2242 | chrec_b = {10, +, -1} | |
2243 | */ | |
2244 | if (tree_fold_divides_p | |
2245 | (integer_type_node, CHREC_RIGHT (chrec_b), difference)) | |
2246 | { | |
2247 | *overlaps_a = integer_zero_node; | |
2248 | *overlaps_b = fold | |
2249 | (build (EXACT_DIV_EXPR, integer_type_node, difference, | |
2250 | CHREC_RIGHT (chrec_b))); | |
86df10e3 | 2251 | *last_conflicts = integer_one_node; |
56cf8686 SP |
2252 | return; |
2253 | } | |
2254 | ||
2255 | /* When the step does not divides the difference, there | |
2256 | are no overlaps. */ | |
2257 | else | |
2258 | { | |
2259 | *overlaps_a = chrec_known; | |
2260 | *overlaps_b = chrec_known; | |
86df10e3 | 2261 | *last_conflicts = integer_zero_node; |
56cf8686 SP |
2262 | return; |
2263 | } | |
2264 | } | |
2265 | else | |
2266 | { | |
2267 | /* Example: | |
2268 | chrec_a = 3 | |
2269 | chrec_b = {4, +, 1} | |
2270 | ||
2271 | In this case, chrec_a will not overlap with chrec_b. */ | |
2272 | *overlaps_a = chrec_known; | |
2273 | *overlaps_b = chrec_known; | |
86df10e3 | 2274 | *last_conflicts = integer_zero_node; |
56cf8686 SP |
2275 | return; |
2276 | } | |
2277 | } | |
2278 | } | |
2279 | } | |
2280 | } | |
2281 | ||
50300b4c | 2282 | /* Helper recursive function for initializing the matrix A. Returns |
86df10e3 | 2283 | the initial value of CHREC. */ |
56cf8686 | 2284 | |
86df10e3 SP |
2285 | static int |
2286 | initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult) | |
2287 | { | |
2288 | gcc_assert (chrec); | |
2289 | ||
2290 | if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) | |
2291 | return int_cst_value (chrec); | |
2292 | ||
2293 | A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec)); | |
2294 | return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult); | |
2295 | } | |
2296 | ||
2297 | #define FLOOR_DIV(x,y) ((x) / (y)) | |
2298 | ||
2299 | /* Solves the special case of the Diophantine equation: | |
2300 | | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B) | |
2301 | ||
2302 | Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the | |
2303 | number of iterations that loops X and Y run. The overlaps will be | |
2304 | constructed as evolutions in dimension DIM. */ | |
56cf8686 SP |
2305 | |
2306 | static void | |
86df10e3 SP |
2307 | compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, |
2308 | tree *overlaps_a, tree *overlaps_b, | |
2309 | tree *last_conflicts, int dim) | |
2310 | { | |
2311 | if (((step_a > 0 && step_b > 0) | |
2312 | || (step_a < 0 && step_b < 0))) | |
2313 | { | |
2314 | int step_overlaps_a, step_overlaps_b; | |
2315 | int gcd_steps_a_b, last_conflict, tau2; | |
2316 | ||
2317 | gcd_steps_a_b = gcd (step_a, step_b); | |
2318 | step_overlaps_a = step_b / gcd_steps_a_b; | |
2319 | step_overlaps_b = step_a / gcd_steps_a_b; | |
2320 | ||
2321 | tau2 = FLOOR_DIV (niter, step_overlaps_a); | |
2322 | tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b)); | |
2323 | last_conflict = tau2; | |
2324 | ||
2325 | *overlaps_a = build_polynomial_chrec | |
2326 | (dim, integer_zero_node, | |
2327 | build_int_cst (NULL_TREE, step_overlaps_a)); | |
2328 | *overlaps_b = build_polynomial_chrec | |
2329 | (dim, integer_zero_node, | |
2330 | build_int_cst (NULL_TREE, step_overlaps_b)); | |
2331 | *last_conflicts = build_int_cst (NULL_TREE, last_conflict); | |
2332 | } | |
2333 | ||
2334 | else | |
2335 | { | |
2336 | *overlaps_a = integer_zero_node; | |
2337 | *overlaps_b = integer_zero_node; | |
2338 | *last_conflicts = integer_zero_node; | |
2339 | } | |
2340 | } | |
2341 | ||
2342 | ||
2343 | /* Solves the special case of a Diophantine equation where CHREC_A is | |
2344 | an affine bivariate function, and CHREC_B is an affine univariate | |
2345 | function. For example, | |
2346 | ||
2347 | | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z | |
2348 | ||
2349 | has the following overlapping functions: | |
2350 | ||
2351 | | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v | |
2352 | | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v | |
2353 | | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v | |
2354 | ||
35fd3193 | 2355 | FORNOW: This is a specialized implementation for a case occurring in |
86df10e3 SP |
2356 | a common benchmark. Implement the general algorithm. */ |
2357 | ||
2358 | static void | |
2359 | compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, | |
2360 | tree *overlaps_a, tree *overlaps_b, | |
2361 | tree *last_conflicts) | |
56cf8686 | 2362 | { |
86df10e3 SP |
2363 | bool xz_p, yz_p, xyz_p; |
2364 | int step_x, step_y, step_z; | |
2365 | int niter_x, niter_y, niter_z, niter; | |
2366 | tree numiter_x, numiter_y, numiter_z; | |
2367 | tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz; | |
2368 | tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz; | |
2369 | tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz; | |
2370 | ||
2371 | step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a))); | |
2372 | step_y = int_cst_value (CHREC_RIGHT (chrec_a)); | |
2373 | step_z = int_cst_value (CHREC_RIGHT (chrec_b)); | |
2374 | ||
2375 | numiter_x = number_of_iterations_in_loop | |
2376 | (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]); | |
2377 | numiter_y = number_of_iterations_in_loop | |
2378 | (current_loops->parray[CHREC_VARIABLE (chrec_a)]); | |
2379 | numiter_z = number_of_iterations_in_loop | |
2380 | (current_loops->parray[CHREC_VARIABLE (chrec_b)]); | |
2381 | ||
2382 | if (TREE_CODE (numiter_x) != INTEGER_CST) | |
2383 | numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))] | |
2384 | ->estimated_nb_iterations; | |
2385 | if (TREE_CODE (numiter_y) != INTEGER_CST) | |
2386 | numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)] | |
2387 | ->estimated_nb_iterations; | |
2388 | if (TREE_CODE (numiter_z) != INTEGER_CST) | |
2389 | numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)] | |
2390 | ->estimated_nb_iterations; | |
2391 | ||
79ebd55c SP |
2392 | if (chrec_contains_undetermined (numiter_x) |
2393 | || chrec_contains_undetermined (numiter_y) | |
2394 | || chrec_contains_undetermined (numiter_z) | |
2395 | || TREE_CODE (numiter_x) != INTEGER_CST | |
2396 | || TREE_CODE (numiter_y) != INTEGER_CST | |
2397 | || TREE_CODE (numiter_z) != INTEGER_CST) | |
86df10e3 SP |
2398 | { |
2399 | *overlaps_a = chrec_dont_know; | |
2400 | *overlaps_b = chrec_dont_know; | |
2401 | *last_conflicts = chrec_dont_know; | |
2402 | return; | |
2403 | } | |
2404 | ||
2405 | niter_x = int_cst_value (numiter_x); | |
2406 | niter_y = int_cst_value (numiter_y); | |
2407 | niter_z = int_cst_value (numiter_z); | |
2408 | ||
2409 | niter = MIN (niter_x, niter_z); | |
2410 | compute_overlap_steps_for_affine_univar (niter, step_x, step_z, | |
2411 | &overlaps_a_xz, | |
2412 | &overlaps_b_xz, | |
2413 | &last_conflicts_xz, 1); | |
2414 | niter = MIN (niter_y, niter_z); | |
2415 | compute_overlap_steps_for_affine_univar (niter, step_y, step_z, | |
2416 | &overlaps_a_yz, | |
2417 | &overlaps_b_yz, | |
2418 | &last_conflicts_yz, 2); | |
2419 | niter = MIN (niter_x, niter_z); | |
2420 | niter = MIN (niter_y, niter); | |
2421 | compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z, | |
2422 | &overlaps_a_xyz, | |
2423 | &overlaps_b_xyz, | |
2424 | &last_conflicts_xyz, 3); | |
2425 | ||
2426 | xz_p = !integer_zerop (last_conflicts_xz); | |
2427 | yz_p = !integer_zerop (last_conflicts_yz); | |
2428 | xyz_p = !integer_zerop (last_conflicts_xyz); | |
2429 | ||
2430 | if (xz_p || yz_p || xyz_p) | |
2431 | { | |
2432 | *overlaps_a = make_tree_vec (2); | |
2433 | TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node; | |
2434 | TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node; | |
2435 | *overlaps_b = integer_zero_node; | |
2436 | if (xz_p) | |
2437 | { | |
2438 | TREE_VEC_ELT (*overlaps_a, 0) = | |
2439 | chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0), | |
2440 | overlaps_a_xz); | |
2441 | *overlaps_b = | |
2442 | chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz); | |
2443 | *last_conflicts = last_conflicts_xz; | |
2444 | } | |
2445 | if (yz_p) | |
2446 | { | |
2447 | TREE_VEC_ELT (*overlaps_a, 1) = | |
2448 | chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1), | |
2449 | overlaps_a_yz); | |
2450 | *overlaps_b = | |
2451 | chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz); | |
2452 | *last_conflicts = last_conflicts_yz; | |
2453 | } | |
2454 | if (xyz_p) | |
2455 | { | |
2456 | TREE_VEC_ELT (*overlaps_a, 0) = | |
2457 | chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0), | |
2458 | overlaps_a_xyz); | |
2459 | TREE_VEC_ELT (*overlaps_a, 1) = | |
2460 | chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1), | |
2461 | overlaps_a_xyz); | |
2462 | *overlaps_b = | |
2463 | chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz); | |
2464 | *last_conflicts = last_conflicts_xyz; | |
2465 | } | |
2466 | } | |
2467 | else | |
2468 | { | |
2469 | *overlaps_a = integer_zero_node; | |
2470 | *overlaps_b = integer_zero_node; | |
2471 | *last_conflicts = integer_zero_node; | |
2472 | } | |
56cf8686 SP |
2473 | } |
2474 | ||
2475 | /* Determines the overlapping elements due to accesses CHREC_A and | |
2476 | CHREC_B, that are affine functions. This is a part of the | |
2477 | subscript analyzer. */ | |
2478 | ||
2479 | static void | |
2480 | analyze_subscript_affine_affine (tree chrec_a, | |
2481 | tree chrec_b, | |
2482 | tree *overlaps_a, | |
86df10e3 SP |
2483 | tree *overlaps_b, |
2484 | tree *last_conflicts) | |
56cf8686 | 2485 | { |
86df10e3 SP |
2486 | unsigned nb_vars_a, nb_vars_b, dim; |
2487 | int init_a, init_b, gamma, gcd_alpha_beta; | |
2488 | int tau1, tau2; | |
2489 | lambda_matrix A, U, S; | |
2490 | ||
56cf8686 SP |
2491 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2492 | fprintf (dump_file, "(analyze_subscript_affine_affine \n"); | |
2493 | ||
2494 | /* For determining the initial intersection, we have to solve a | |
2495 | Diophantine equation. This is the most time consuming part. | |
2496 | ||
2497 | For answering to the question: "Is there a dependence?" we have | |
2498 | to prove that there exists a solution to the Diophantine | |
2499 | equation, and that the solution is in the iteration domain, | |
89dbed81 | 2500 | i.e. the solution is positive or zero, and that the solution |
56cf8686 SP |
2501 | happens before the upper bound loop.nb_iterations. Otherwise |
2502 | there is no dependence. This function outputs a description of | |
2503 | the iterations that hold the intersections. */ | |
2504 | ||
56cf8686 | 2505 | |
86df10e3 SP |
2506 | nb_vars_a = nb_vars_in_chrec (chrec_a); |
2507 | nb_vars_b = nb_vars_in_chrec (chrec_b); | |
2508 | ||
2509 | dim = nb_vars_a + nb_vars_b; | |
2510 | U = lambda_matrix_new (dim, dim); | |
2511 | A = lambda_matrix_new (dim, 1); | |
2512 | S = lambda_matrix_new (dim, 1); | |
2513 | ||
2514 | init_a = initialize_matrix_A (A, chrec_a, 0, 1); | |
2515 | init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1); | |
2516 | gamma = init_b - init_a; | |
2517 | ||
2518 | /* Don't do all the hard work of solving the Diophantine equation | |
2519 | when we already know the solution: for example, | |
2520 | | {3, +, 1}_1 | |
2521 | | {3, +, 4}_2 | |
2522 | | gamma = 3 - 3 = 0. | |
2523 | Then the first overlap occurs during the first iterations: | |
2524 | | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x) | |
2525 | */ | |
2526 | if (gamma == 0) | |
56cf8686 | 2527 | { |
86df10e3 | 2528 | if (nb_vars_a == 1 && nb_vars_b == 1) |
56cf8686 | 2529 | { |
86df10e3 SP |
2530 | int step_a, step_b; |
2531 | int niter, niter_a, niter_b; | |
2532 | tree numiter_a, numiter_b; | |
2533 | ||
2534 | numiter_a = number_of_iterations_in_loop | |
2535 | (current_loops->parray[CHREC_VARIABLE (chrec_a)]); | |
2536 | numiter_b = number_of_iterations_in_loop | |
2537 | (current_loops->parray[CHREC_VARIABLE (chrec_b)]); | |
2538 | ||
2539 | if (TREE_CODE (numiter_a) != INTEGER_CST) | |
2540 | numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)] | |
2541 | ->estimated_nb_iterations; | |
2542 | if (TREE_CODE (numiter_b) != INTEGER_CST) | |
2543 | numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)] | |
2544 | ->estimated_nb_iterations; | |
79ebd55c SP |
2545 | if (chrec_contains_undetermined (numiter_a) |
2546 | || chrec_contains_undetermined (numiter_b) | |
2547 | || TREE_CODE (numiter_a) != INTEGER_CST | |
2548 | || TREE_CODE (numiter_b) != INTEGER_CST) | |
86df10e3 SP |
2549 | { |
2550 | *overlaps_a = chrec_dont_know; | |
2551 | *overlaps_b = chrec_dont_know; | |
2552 | *last_conflicts = chrec_dont_know; | |
2553 | return; | |
2554 | } | |
2555 | ||
2556 | niter_a = int_cst_value (numiter_a); | |
2557 | niter_b = int_cst_value (numiter_b); | |
2558 | niter = MIN (niter_a, niter_b); | |
2559 | ||
2560 | step_a = int_cst_value (CHREC_RIGHT (chrec_a)); | |
2561 | step_b = int_cst_value (CHREC_RIGHT (chrec_b)); | |
2562 | ||
2563 | compute_overlap_steps_for_affine_univar (niter, step_a, step_b, | |
2564 | overlaps_a, overlaps_b, | |
2565 | last_conflicts, 1); | |
56cf8686 | 2566 | } |
86df10e3 SP |
2567 | |
2568 | else if (nb_vars_a == 2 && nb_vars_b == 1) | |
2569 | compute_overlap_steps_for_affine_1_2 | |
2570 | (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts); | |
2571 | ||
2572 | else if (nb_vars_a == 1 && nb_vars_b == 2) | |
2573 | compute_overlap_steps_for_affine_1_2 | |
2574 | (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts); | |
2575 | ||
2576 | else | |
56cf8686 | 2577 | { |
86df10e3 SP |
2578 | *overlaps_a = chrec_dont_know; |
2579 | *overlaps_b = chrec_dont_know; | |
2580 | *last_conflicts = chrec_dont_know; | |
56cf8686 | 2581 | } |
86df10e3 SP |
2582 | return; |
2583 | } | |
2584 | ||
2585 | /* U.A = S */ | |
2586 | lambda_matrix_right_hermite (A, dim, 1, S, U); | |
2587 | ||
2588 | if (S[0][0] < 0) | |
2589 | { | |
2590 | S[0][0] *= -1; | |
2591 | lambda_matrix_row_negate (U, dim, 0); | |
2592 | } | |
2593 | gcd_alpha_beta = S[0][0]; | |
2594 | ||
2595 | /* The classic "gcd-test". */ | |
2596 | if (!int_divides_p (gcd_alpha_beta, gamma)) | |
2597 | { | |
2598 | /* The "gcd-test" has determined that there is no integer | |
2599 | solution, i.e. there is no dependence. */ | |
2600 | *overlaps_a = chrec_known; | |
2601 | *overlaps_b = chrec_known; | |
2602 | *last_conflicts = integer_zero_node; | |
2603 | } | |
2604 | ||
2605 | /* Both access functions are univariate. This includes SIV and MIV cases. */ | |
2606 | else if (nb_vars_a == 1 && nb_vars_b == 1) | |
2607 | { | |
2608 | /* Both functions should have the same evolution sign. */ | |
2609 | if (((A[0][0] > 0 && -A[1][0] > 0) | |
2610 | || (A[0][0] < 0 && -A[1][0] < 0))) | |
56cf8686 SP |
2611 | { |
2612 | /* The solutions are given by: | |
2613 | | | |
86df10e3 SP |
2614 | | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0] |
2615 | | [u21 u22] [y0] | |
2616 | ||
56cf8686 | 2617 | For a given integer t. Using the following variables, |
86df10e3 | 2618 | |
56cf8686 SP |
2619 | | i0 = u11 * gamma / gcd_alpha_beta |
2620 | | j0 = u12 * gamma / gcd_alpha_beta | |
2621 | | i1 = u21 | |
2622 | | j1 = u22 | |
86df10e3 | 2623 | |
56cf8686 | 2624 | the solutions are: |
86df10e3 SP |
2625 | |
2626 | | x0 = i0 + i1 * t, | |
2627 | | y0 = j0 + j1 * t. */ | |
2628 | ||
2629 | int i0, j0, i1, j1; | |
2630 | ||
56cf8686 SP |
2631 | /* X0 and Y0 are the first iterations for which there is a |
2632 | dependence. X0, Y0 are two solutions of the Diophantine | |
2633 | equation: chrec_a (X0) = chrec_b (Y0). */ | |
86df10e3 SP |
2634 | int x0, y0; |
2635 | int niter, niter_a, niter_b; | |
2636 | tree numiter_a, numiter_b; | |
2637 | ||
2638 | numiter_a = number_of_iterations_in_loop | |
2639 | (current_loops->parray[CHREC_VARIABLE (chrec_a)]); | |
2640 | numiter_b = number_of_iterations_in_loop | |
2641 | (current_loops->parray[CHREC_VARIABLE (chrec_b)]); | |
2642 | ||
2643 | if (TREE_CODE (numiter_a) != INTEGER_CST) | |
2644 | numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)] | |
2645 | ->estimated_nb_iterations; | |
2646 | if (TREE_CODE (numiter_b) != INTEGER_CST) | |
2647 | numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)] | |
2648 | ->estimated_nb_iterations; | |
79ebd55c SP |
2649 | if (chrec_contains_undetermined (numiter_a) |
2650 | || chrec_contains_undetermined (numiter_b) | |
2651 | || TREE_CODE (numiter_a) != INTEGER_CST | |
2652 | || TREE_CODE (numiter_b) != INTEGER_CST) | |
86df10e3 SP |
2653 | { |
2654 | *overlaps_a = chrec_dont_know; | |
2655 | *overlaps_b = chrec_dont_know; | |
2656 | *last_conflicts = chrec_dont_know; | |
2657 | return; | |
2658 | } | |
2659 | ||
2660 | niter_a = int_cst_value (numiter_a); | |
2661 | niter_b = int_cst_value (numiter_b); | |
2662 | niter = MIN (niter_a, niter_b); | |
2663 | ||
2664 | i0 = U[0][0] * gamma / gcd_alpha_beta; | |
2665 | j0 = U[0][1] * gamma / gcd_alpha_beta; | |
2666 | i1 = U[1][0]; | |
2667 | j1 = U[1][1]; | |
2668 | ||
2669 | if ((i1 == 0 && i0 < 0) | |
2670 | || (j1 == 0 && j0 < 0)) | |
56cf8686 SP |
2671 | { |
2672 | /* There is no solution. | |
2673 | FIXME: The case "i0 > nb_iterations, j0 > nb_iterations" | |
2674 | falls in here, but for the moment we don't look at the | |
2675 | upper bound of the iteration domain. */ | |
2676 | *overlaps_a = chrec_known; | |
2677 | *overlaps_b = chrec_known; | |
86df10e3 SP |
2678 | *last_conflicts = integer_zero_node; |
2679 | } | |
2680 | ||
56cf8686 SP |
2681 | else |
2682 | { | |
86df10e3 | 2683 | if (i1 > 0) |
56cf8686 | 2684 | { |
86df10e3 SP |
2685 | tau1 = CEIL (-i0, i1); |
2686 | tau2 = FLOOR_DIV (niter - i0, i1); | |
2687 | ||
2688 | if (j1 > 0) | |
56cf8686 | 2689 | { |
9ba64a4a | 2690 | int last_conflict, min_multiple; |
86df10e3 SP |
2691 | tau1 = MAX (tau1, CEIL (-j0, j1)); |
2692 | tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1)); | |
2693 | ||
9ba64a4a SP |
2694 | x0 = i1 * tau1 + i0; |
2695 | y0 = j1 * tau1 + j0; | |
2696 | ||
2697 | /* At this point (x0, y0) is one of the | |
2698 | solutions to the Diophantine equation. The | |
2699 | next step has to compute the smallest | |
2700 | positive solution: the first conflicts. */ | |
2701 | min_multiple = MIN (x0 / i1, y0 / j1); | |
2702 | x0 -= i1 * min_multiple; | |
2703 | y0 -= j1 * min_multiple; | |
2704 | ||
86df10e3 SP |
2705 | tau1 = (x0 - i0)/i1; |
2706 | last_conflict = tau2 - tau1; | |
2707 | ||
2708 | *overlaps_a = build_polynomial_chrec | |
2709 | (1, | |
2710 | build_int_cst (NULL_TREE, x0), | |
2711 | build_int_cst (NULL_TREE, i1)); | |
2712 | *overlaps_b = build_polynomial_chrec | |
2713 | (1, | |
2714 | build_int_cst (NULL_TREE, y0), | |
2715 | build_int_cst (NULL_TREE, j1)); | |
2716 | *last_conflicts = build_int_cst (NULL_TREE, last_conflict); | |
56cf8686 SP |
2717 | } |
2718 | else | |
2719 | { | |
2720 | /* FIXME: For the moment, the upper bound of the | |
471854f8 | 2721 | iteration domain for j is not checked. */ |
56cf8686 SP |
2722 | *overlaps_a = chrec_dont_know; |
2723 | *overlaps_b = chrec_dont_know; | |
86df10e3 | 2724 | *last_conflicts = chrec_dont_know; |
56cf8686 SP |
2725 | } |
2726 | } | |
86df10e3 | 2727 | |
56cf8686 SP |
2728 | else |
2729 | { | |
2730 | /* FIXME: For the moment, the upper bound of the | |
471854f8 | 2731 | iteration domain for i is not checked. */ |
56cf8686 SP |
2732 | *overlaps_a = chrec_dont_know; |
2733 | *overlaps_b = chrec_dont_know; | |
86df10e3 | 2734 | *last_conflicts = chrec_dont_know; |
56cf8686 SP |
2735 | } |
2736 | } | |
2737 | } | |
86df10e3 SP |
2738 | else |
2739 | { | |
2740 | *overlaps_a = chrec_dont_know; | |
2741 | *overlaps_b = chrec_dont_know; | |
2742 | *last_conflicts = chrec_dont_know; | |
2743 | } | |
56cf8686 | 2744 | } |
86df10e3 | 2745 | |
56cf8686 SP |
2746 | else |
2747 | { | |
56cf8686 SP |
2748 | *overlaps_a = chrec_dont_know; |
2749 | *overlaps_b = chrec_dont_know; | |
86df10e3 | 2750 | *last_conflicts = chrec_dont_know; |
56cf8686 | 2751 | } |
86df10e3 SP |
2752 | |
2753 | ||
56cf8686 SP |
2754 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2755 | { | |
2756 | fprintf (dump_file, " (overlaps_a = "); | |
2757 | print_generic_expr (dump_file, *overlaps_a, 0); | |
2758 | fprintf (dump_file, ")\n (overlaps_b = "); | |
2759 | print_generic_expr (dump_file, *overlaps_b, 0); | |
2760 | fprintf (dump_file, ")\n"); | |
2761 | } | |
2762 | ||
2763 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2764 | fprintf (dump_file, ")\n"); | |
2765 | } | |
2766 | ||
2767 | /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and | |
2768 | *OVERLAPS_B are initialized to the functions that describe the | |
2769 | relation between the elements accessed twice by CHREC_A and | |
2770 | CHREC_B. For k >= 0, the following property is verified: | |
2771 | ||
2772 | CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ | |
2773 | ||
2774 | static void | |
2775 | analyze_siv_subscript (tree chrec_a, | |
2776 | tree chrec_b, | |
2777 | tree *overlaps_a, | |
86df10e3 SP |
2778 | tree *overlaps_b, |
2779 | tree *last_conflicts) | |
56cf8686 SP |
2780 | { |
2781 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2782 | fprintf (dump_file, "(analyze_siv_subscript \n"); | |
2783 | ||
2784 | if (evolution_function_is_constant_p (chrec_a) | |
2785 | && evolution_function_is_affine_p (chrec_b)) | |
2786 | analyze_siv_subscript_cst_affine (chrec_a, chrec_b, | |
86df10e3 | 2787 | overlaps_a, overlaps_b, last_conflicts); |
56cf8686 SP |
2788 | |
2789 | else if (evolution_function_is_affine_p (chrec_a) | |
2790 | && evolution_function_is_constant_p (chrec_b)) | |
86df10e3 SP |
2791 | analyze_siv_subscript_cst_affine (chrec_b, chrec_a, |
2792 | overlaps_b, overlaps_a, last_conflicts); | |
56cf8686 SP |
2793 | |
2794 | else if (evolution_function_is_affine_p (chrec_a) | |
86df10e3 | 2795 | && evolution_function_is_affine_p (chrec_b)) |
56cf8686 | 2796 | analyze_subscript_affine_affine (chrec_a, chrec_b, |
86df10e3 | 2797 | overlaps_a, overlaps_b, last_conflicts); |
56cf8686 SP |
2798 | else |
2799 | { | |
2800 | *overlaps_a = chrec_dont_know; | |
2801 | *overlaps_b = chrec_dont_know; | |
86df10e3 | 2802 | *last_conflicts = chrec_dont_know; |
56cf8686 SP |
2803 | } |
2804 | ||
2805 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2806 | fprintf (dump_file, ")\n"); | |
2807 | } | |
2808 | ||
2809 | /* Return true when the evolution steps of an affine CHREC divide the | |
2810 | constant CST. */ | |
2811 | ||
2812 | static bool | |
2813 | chrec_steps_divide_constant_p (tree chrec, | |
2814 | tree cst) | |
2815 | { | |
2816 | switch (TREE_CODE (chrec)) | |
2817 | { | |
2818 | case POLYNOMIAL_CHREC: | |
2819 | return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst) | |
2820 | && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst)); | |
2821 | ||
2822 | default: | |
2823 | /* On the initial condition, return true. */ | |
2824 | return true; | |
2825 | } | |
2826 | } | |
2827 | ||
2828 | /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and | |
2829 | *OVERLAPS_B are initialized to the functions that describe the | |
2830 | relation between the elements accessed twice by CHREC_A and | |
2831 | CHREC_B. For k >= 0, the following property is verified: | |
2832 | ||
2833 | CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ | |
2834 | ||
2835 | static void | |
2836 | analyze_miv_subscript (tree chrec_a, | |
2837 | tree chrec_b, | |
2838 | tree *overlaps_a, | |
86df10e3 SP |
2839 | tree *overlaps_b, |
2840 | tree *last_conflicts) | |
56cf8686 SP |
2841 | { |
2842 | /* FIXME: This is a MIV subscript, not yet handled. | |
2843 | Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from | |
2844 | (A[i] vs. A[j]). | |
2845 | ||
2846 | In the SIV test we had to solve a Diophantine equation with two | |
2847 | variables. In the MIV case we have to solve a Diophantine | |
2848 | equation with 2*n variables (if the subscript uses n IVs). | |
2849 | */ | |
2850 | tree difference; | |
2851 | ||
2852 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2853 | fprintf (dump_file, "(analyze_miv_subscript \n"); | |
2854 | ||
2855 | difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b); | |
2856 | ||
2857 | if (chrec_zerop (difference)) | |
2858 | { | |
2859 | /* Access functions are the same: all the elements are accessed | |
2860 | in the same order. */ | |
2861 | *overlaps_a = integer_zero_node; | |
2862 | *overlaps_b = integer_zero_node; | |
86df10e3 SP |
2863 | *last_conflicts = number_of_iterations_in_loop |
2864 | (current_loops->parray[CHREC_VARIABLE (chrec_a)]); | |
56cf8686 SP |
2865 | } |
2866 | ||
2867 | else if (evolution_function_is_constant_p (difference) | |
2868 | /* For the moment, the following is verified: | |
2869 | evolution_function_is_affine_multivariate_p (chrec_a) */ | |
2870 | && !chrec_steps_divide_constant_p (chrec_a, difference)) | |
2871 | { | |
2872 | /* testsuite/.../ssa-chrec-33.c | |
2873 | {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2 | |
2874 | ||
2875 | The difference is 1, and the evolution steps are equal to 2, | |
2876 | consequently there are no overlapping elements. */ | |
2877 | *overlaps_a = chrec_known; | |
2878 | *overlaps_b = chrec_known; | |
86df10e3 | 2879 | *last_conflicts = integer_zero_node; |
56cf8686 SP |
2880 | } |
2881 | ||
86df10e3 SP |
2882 | else if (evolution_function_is_affine_multivariate_p (chrec_a) |
2883 | && evolution_function_is_affine_multivariate_p (chrec_b)) | |
56cf8686 SP |
2884 | { |
2885 | /* testsuite/.../ssa-chrec-35.c | |
2886 | {0, +, 1}_2 vs. {0, +, 1}_3 | |
2887 | the overlapping elements are respectively located at iterations: | |
86df10e3 SP |
2888 | {0, +, 1}_x and {0, +, 1}_x, |
2889 | in other words, we have the equality: | |
2890 | {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x) | |
2891 | ||
2892 | Other examples: | |
2893 | {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) = | |
2894 | {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y) | |
2895 | ||
2896 | {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) = | |
2897 | {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) | |
56cf8686 | 2898 | */ |
86df10e3 SP |
2899 | analyze_subscript_affine_affine (chrec_a, chrec_b, |
2900 | overlaps_a, overlaps_b, last_conflicts); | |
56cf8686 SP |
2901 | } |
2902 | ||
2903 | else | |
2904 | { | |
2905 | /* When the analysis is too difficult, answer "don't know". */ | |
2906 | *overlaps_a = chrec_dont_know; | |
2907 | *overlaps_b = chrec_dont_know; | |
86df10e3 | 2908 | *last_conflicts = chrec_dont_know; |
56cf8686 SP |
2909 | } |
2910 | ||
2911 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2912 | fprintf (dump_file, ")\n"); | |
2913 | } | |
2914 | ||
2915 | /* Determines the iterations for which CHREC_A is equal to CHREC_B. | |
2916 | OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with | |
2917 | two functions that describe the iterations that contain conflicting | |
2918 | elements. | |
2919 | ||
2920 | Remark: For an integer k >= 0, the following equality is true: | |
2921 | ||
2922 | CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)). | |
2923 | */ | |
2924 | ||
2925 | static void | |
2926 | analyze_overlapping_iterations (tree chrec_a, | |
2927 | tree chrec_b, | |
2928 | tree *overlap_iterations_a, | |
86df10e3 SP |
2929 | tree *overlap_iterations_b, |
2930 | tree *last_conflicts) | |
56cf8686 SP |
2931 | { |
2932 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2933 | { | |
2934 | fprintf (dump_file, "(analyze_overlapping_iterations \n"); | |
2935 | fprintf (dump_file, " (chrec_a = "); | |
2936 | print_generic_expr (dump_file, chrec_a, 0); | |
2937 | fprintf (dump_file, ")\n chrec_b = "); | |
2938 | print_generic_expr (dump_file, chrec_b, 0); | |
2939 | fprintf (dump_file, ")\n"); | |
2940 | } | |
2941 | ||
2942 | if (chrec_a == NULL_TREE | |
2943 | || chrec_b == NULL_TREE | |
2944 | || chrec_contains_undetermined (chrec_a) | |
2945 | || chrec_contains_undetermined (chrec_b) | |
2946 | || chrec_contains_symbols (chrec_a) | |
2947 | || chrec_contains_symbols (chrec_b)) | |
2948 | { | |
2949 | *overlap_iterations_a = chrec_dont_know; | |
2950 | *overlap_iterations_b = chrec_dont_know; | |
2951 | } | |
2952 | ||
2953 | else if (ziv_subscript_p (chrec_a, chrec_b)) | |
2954 | analyze_ziv_subscript (chrec_a, chrec_b, | |
86df10e3 SP |
2955 | overlap_iterations_a, overlap_iterations_b, |
2956 | last_conflicts); | |
56cf8686 SP |
2957 | |
2958 | else if (siv_subscript_p (chrec_a, chrec_b)) | |
2959 | analyze_siv_subscript (chrec_a, chrec_b, | |
86df10e3 SP |
2960 | overlap_iterations_a, overlap_iterations_b, |
2961 | last_conflicts); | |
56cf8686 SP |
2962 | |
2963 | else | |
2964 | analyze_miv_subscript (chrec_a, chrec_b, | |
86df10e3 SP |
2965 | overlap_iterations_a, overlap_iterations_b, |
2966 | last_conflicts); | |
56cf8686 SP |
2967 | |
2968 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2969 | { | |
2970 | fprintf (dump_file, " (overlap_iterations_a = "); | |
2971 | print_generic_expr (dump_file, *overlap_iterations_a, 0); | |
2972 | fprintf (dump_file, ")\n (overlap_iterations_b = "); | |
2973 | print_generic_expr (dump_file, *overlap_iterations_b, 0); | |
2974 | fprintf (dump_file, ")\n"); | |
2975 | } | |
2976 | } | |
2977 | ||
2978 | \f | |
2979 | ||
2980 | /* This section contains the affine functions dependences detector. */ | |
2981 | ||
2982 | /* Computes the conflicting iterations, and initialize DDR. */ | |
2983 | ||
2984 | static void | |
2985 | subscript_dependence_tester (struct data_dependence_relation *ddr) | |
2986 | { | |
2987 | unsigned int i; | |
2988 | struct data_reference *dra = DDR_A (ddr); | |
2989 | struct data_reference *drb = DDR_B (ddr); | |
86df10e3 | 2990 | tree last_conflicts; |
56cf8686 SP |
2991 | |
2992 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2993 | fprintf (dump_file, "(subscript_dependence_tester \n"); | |
2994 | ||
2995 | for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) | |
2996 | { | |
2997 | tree overlaps_a, overlaps_b; | |
2998 | struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); | |
2999 | ||
3000 | analyze_overlapping_iterations (DR_ACCESS_FN (dra, i), | |
3001 | DR_ACCESS_FN (drb, i), | |
86df10e3 SP |
3002 | &overlaps_a, &overlaps_b, |
3003 | &last_conflicts); | |
56cf8686 SP |
3004 | |
3005 | if (chrec_contains_undetermined (overlaps_a) | |
3006 | || chrec_contains_undetermined (overlaps_b)) | |
3007 | { | |
3008 | finalize_ddr_dependent (ddr, chrec_dont_know); | |
3009 | break; | |
3010 | } | |
3011 | ||
3012 | else if (overlaps_a == chrec_known | |
3013 | || overlaps_b == chrec_known) | |
3014 | { | |
3015 | finalize_ddr_dependent (ddr, chrec_known); | |
3016 | break; | |
3017 | } | |
3018 | ||
3019 | else | |
3020 | { | |
3021 | SUB_CONFLICTS_IN_A (subscript) = overlaps_a; | |
3022 | SUB_CONFLICTS_IN_B (subscript) = overlaps_b; | |
86df10e3 | 3023 | SUB_LAST_CONFLICT (subscript) = last_conflicts; |
56cf8686 SP |
3024 | } |
3025 | } | |
3026 | ||
3027 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
3028 | fprintf (dump_file, ")\n"); | |
3029 | } | |
3030 | ||
3031 | /* Compute the classic per loop distance vector. | |
3032 | ||
36d59cf7 | 3033 | DDR is the data dependence relation to build a vector from. |
56cf8686 | 3034 | NB_LOOPS is the total number of loops we are considering. |
1f24dd47 | 3035 | FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed |
464f49d8 DB |
3036 | loop nest. |
3037 | Return FALSE if the dependence relation is outside of the loop nest | |
1f24dd47 | 3038 | starting at FIRST_LOOP_DEPTH. |
464f49d8 | 3039 | Return TRUE otherwise. */ |
56cf8686 | 3040 | |
86a07404 | 3041 | static bool |
36d59cf7 | 3042 | build_classic_dist_vector (struct data_dependence_relation *ddr, |
1f24dd47 | 3043 | int nb_loops, int first_loop_depth) |
56cf8686 SP |
3044 | { |
3045 | unsigned i; | |
3046 | lambda_vector dist_v, init_v; | |
3047 | ||
3048 | dist_v = lambda_vector_new (nb_loops); | |
3049 | init_v = lambda_vector_new (nb_loops); | |
3050 | lambda_vector_clear (dist_v, nb_loops); | |
3051 | lambda_vector_clear (init_v, nb_loops); | |
3052 | ||
36d59cf7 | 3053 | if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE) |
464f49d8 | 3054 | return true; |
56cf8686 | 3055 | |
36d59cf7 | 3056 | for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) |
56cf8686 | 3057 | { |
86df10e3 | 3058 | tree access_fn_a, access_fn_b; |
36d59cf7 | 3059 | struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); |
56cf8686 SP |
3060 | |
3061 | if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) | |
86df10e3 SP |
3062 | { |
3063 | non_affine_dependence_relation (ddr); | |
464f49d8 | 3064 | return true; |
86df10e3 SP |
3065 | } |
3066 | ||
3067 | access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i); | |
3068 | access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i); | |
56cf8686 | 3069 | |
86df10e3 SP |
3070 | if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC |
3071 | && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC) | |
56cf8686 | 3072 | { |
1f24dd47 | 3073 | int dist, loop_nb, loop_depth; |
86df10e3 SP |
3074 | int loop_nb_a = CHREC_VARIABLE (access_fn_a); |
3075 | int loop_nb_b = CHREC_VARIABLE (access_fn_b); | |
3076 | struct loop *loop_a = current_loops->parray[loop_nb_a]; | |
3077 | struct loop *loop_b = current_loops->parray[loop_nb_b]; | |
464f49d8 | 3078 | |
8b41b1b2 DB |
3079 | /* If the loop for either variable is at a lower depth than |
3080 | the first_loop's depth, then we can't possibly have a | |
464f49d8 DB |
3081 | dependency at this level of the loop. */ |
3082 | ||
1f24dd47 DB |
3083 | if (loop_a->depth < first_loop_depth |
3084 | || loop_b->depth < first_loop_depth) | |
464f49d8 | 3085 | return false; |
86df10e3 SP |
3086 | |
3087 | if (loop_nb_a != loop_nb_b | |
3088 | && !flow_loop_nested_p (loop_a, loop_b) | |
3089 | && !flow_loop_nested_p (loop_b, loop_a)) | |
3090 | { | |
3091 | /* Example: when there are two consecutive loops, | |
3092 | ||
3093 | | loop_1 | |
3094 | | A[{0, +, 1}_1] | |
3095 | | endloop_1 | |
3096 | | loop_2 | |
3097 | | A[{0, +, 1}_2] | |
3098 | | endloop_2 | |
3099 | ||
3100 | the dependence relation cannot be captured by the | |
3101 | distance abstraction. */ | |
3102 | non_affine_dependence_relation (ddr); | |
464f49d8 | 3103 | return true; |
86df10e3 SP |
3104 | } |
3105 | ||
3106 | /* The dependence is carried by the outermost loop. Example: | |
3107 | | loop_1 | |
3108 | | A[{4, +, 1}_1] | |
3109 | | loop_2 | |
3110 | | A[{5, +, 1}_2] | |
3111 | | endloop_2 | |
3112 | | endloop_1 | |
3113 | In this case, the dependence is carried by loop_1. */ | |
3114 | loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b; | |
1f24dd47 | 3115 | loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth; |
86df10e3 | 3116 | |
56cf8686 SP |
3117 | /* If the loop number is still greater than the number of |
3118 | loops we've been asked to analyze, or negative, | |
3119 | something is borked. */ | |
1f24dd47 DB |
3120 | gcc_assert (loop_depth >= 0); |
3121 | gcc_assert (loop_depth < nb_loops); | |
86df10e3 SP |
3122 | if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) |
3123 | { | |
3124 | non_affine_dependence_relation (ddr); | |
464f49d8 | 3125 | return true; |
86df10e3 SP |
3126 | } |
3127 | ||
56cf8686 SP |
3128 | dist = int_cst_value (SUB_DISTANCE (subscript)); |
3129 | ||
3130 | /* This is the subscript coupling test. | |
3131 | | loop i = 0, N, 1 | |
3132 | | T[i+1][i] = ... | |
3133 | | ... = T[i][i] | |
3134 | | endloop | |
3135 | There is no dependence. */ | |
1f24dd47 DB |
3136 | if (init_v[loop_depth] != 0 |
3137 | && dist_v[loop_depth] != dist) | |
56cf8686 | 3138 | { |
36d59cf7 | 3139 | finalize_ddr_dependent (ddr, chrec_known); |
464f49d8 | 3140 | return true; |
56cf8686 SP |
3141 | } |
3142 | ||
1f24dd47 DB |
3143 | dist_v[loop_depth] = dist; |
3144 | init_v[loop_depth] = 1; | |
56cf8686 SP |
3145 | } |
3146 | } | |
3147 | ||
3148 | /* There is a distance of 1 on all the outer loops: | |
3149 | ||
3150 | Example: there is a dependence of distance 1 on loop_1 for the array A. | |
3151 | | loop_1 | |
3152 | | A[5] = ... | |
3153 | | endloop | |
3154 | */ | |
3155 | { | |
3156 | struct loop *lca, *loop_a, *loop_b; | |
36d59cf7 DB |
3157 | struct data_reference *a = DDR_A (ddr); |
3158 | struct data_reference *b = DDR_B (ddr); | |
1f24dd47 | 3159 | int lca_depth; |
56cf8686 SP |
3160 | loop_a = loop_containing_stmt (DR_STMT (a)); |
3161 | loop_b = loop_containing_stmt (DR_STMT (b)); | |
3162 | ||
3163 | /* Get the common ancestor loop. */ | |
3164 | lca = find_common_loop (loop_a, loop_b); | |
3165 | ||
1f24dd47 DB |
3166 | lca_depth = lca->depth; |
3167 | lca_depth -= first_loop_depth; | |
3168 | gcc_assert (lca_depth >= 0); | |
3169 | gcc_assert (lca_depth < nb_loops); | |
86df10e3 | 3170 | |
56cf8686 SP |
3171 | /* For each outer loop where init_v is not set, the accesses are |
3172 | in dependence of distance 1 in the loop. */ | |
3173 | if (lca != loop_a | |
3174 | && lca != loop_b | |
1f24dd47 DB |
3175 | && init_v[lca_depth] == 0) |
3176 | dist_v[lca_depth] = 1; | |
56cf8686 SP |
3177 | |
3178 | lca = lca->outer; | |
3179 | ||
3180 | if (lca) | |
3181 | { | |
1f24dd47 | 3182 | lca_depth = lca->depth - first_loop_depth; |
56cf8686 SP |
3183 | while (lca->depth != 0) |
3184 | { | |
86df10e3 SP |
3185 | /* If we're considering just a sub-nest, then don't record |
3186 | any information on the outer loops. */ | |
1f24dd47 | 3187 | if (lca_depth < 0) |
86df10e3 SP |
3188 | break; |
3189 | ||
1f24dd47 | 3190 | gcc_assert (lca_depth < nb_loops); |
86df10e3 | 3191 | |
1f24dd47 DB |
3192 | if (init_v[lca_depth] == 0) |
3193 | dist_v[lca_depth] = 1; | |
56cf8686 | 3194 | lca = lca->outer; |
1f24dd47 | 3195 | lca_depth = lca->depth - first_loop_depth; |
56cf8686 SP |
3196 | |
3197 | } | |
3198 | } | |
3199 | } | |
3200 | ||
36d59cf7 | 3201 | DDR_DIST_VECT (ddr) = dist_v; |
86df10e3 | 3202 | DDR_SIZE_VECT (ddr) = nb_loops; |
464f49d8 | 3203 | return true; |
56cf8686 SP |
3204 | } |
3205 | ||
3206 | /* Compute the classic per loop direction vector. | |
3207 | ||
36d59cf7 | 3208 | DDR is the data dependence relation to build a vector from. |
56cf8686 | 3209 | NB_LOOPS is the total number of loops we are considering. |
1f24dd47 | 3210 | FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed |
464f49d8 DB |
3211 | loop nest. |
3212 | Return FALSE if the dependence relation is outside of the loop nest | |
1f24dd47 | 3213 | at FIRST_LOOP_DEPTH. |
464f49d8 | 3214 | Return TRUE otherwise. */ |
56cf8686 | 3215 | |
464f49d8 | 3216 | static bool |
36d59cf7 | 3217 | build_classic_dir_vector (struct data_dependence_relation *ddr, |
1f24dd47 | 3218 | int nb_loops, int first_loop_depth) |
56cf8686 SP |
3219 | { |
3220 | unsigned i; | |
3221 | lambda_vector dir_v, init_v; | |
3222 | ||
3223 | dir_v = lambda_vector_new (nb_loops); | |
3224 | init_v = lambda_vector_new (nb_loops); | |
3225 | lambda_vector_clear (dir_v, nb_loops); | |
3226 | lambda_vector_clear (init_v, nb_loops); | |
3227 | ||
36d59cf7 | 3228 | if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE) |
464f49d8 | 3229 | return true; |
56cf8686 | 3230 | |
36d59cf7 | 3231 | for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) |
56cf8686 | 3232 | { |
86df10e3 | 3233 | tree access_fn_a, access_fn_b; |
36d59cf7 | 3234 | struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); |
56cf8686 | 3235 | |
86df10e3 | 3236 | if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) |
56cf8686 | 3237 | { |
86df10e3 | 3238 | non_affine_dependence_relation (ddr); |
464f49d8 | 3239 | return true; |
86df10e3 SP |
3240 | } |
3241 | ||
3242 | access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i); | |
3243 | access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i); | |
3244 | if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC | |
3245 | && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC) | |
3246 | { | |
1f24dd47 | 3247 | int dist, loop_nb, loop_depth; |
56cf8686 | 3248 | enum data_dependence_direction dir = dir_star; |
86df10e3 SP |
3249 | int loop_nb_a = CHREC_VARIABLE (access_fn_a); |
3250 | int loop_nb_b = CHREC_VARIABLE (access_fn_b); | |
3251 | struct loop *loop_a = current_loops->parray[loop_nb_a]; | |
3252 | struct loop *loop_b = current_loops->parray[loop_nb_b]; | |
464f49d8 | 3253 | |
8b41b1b2 DB |
3254 | /* If the loop for either variable is at a lower depth than |
3255 | the first_loop's depth, then we can't possibly have a | |
3256 | dependency at this level of the loop. */ | |
464f49d8 | 3257 | |
1f24dd47 DB |
3258 | if (loop_a->depth < first_loop_depth |
3259 | || loop_b->depth < first_loop_depth) | |
464f49d8 | 3260 | return false; |
86df10e3 SP |
3261 | |
3262 | if (loop_nb_a != loop_nb_b | |
3263 | && !flow_loop_nested_p (loop_a, loop_b) | |
3264 | && !flow_loop_nested_p (loop_b, loop_a)) | |
3265 | { | |
3266 | /* Example: when there are two consecutive loops, | |
3267 | ||
3268 | | loop_1 | |
3269 | | A[{0, +, 1}_1] | |
3270 | | endloop_1 | |
3271 | | loop_2 | |
3272 | | A[{0, +, 1}_2] | |
3273 | | endloop_2 | |
3274 | ||
3275 | the dependence relation cannot be captured by the | |
3276 | distance abstraction. */ | |
3277 | non_affine_dependence_relation (ddr); | |
464f49d8 | 3278 | return true; |
86df10e3 SP |
3279 | } |
3280 | ||
3281 | /* The dependence is carried by the outermost loop. Example: | |
3282 | | loop_1 | |
3283 | | A[{4, +, 1}_1] | |
3284 | | loop_2 | |
3285 | | A[{5, +, 1}_2] | |
3286 | | endloop_2 | |
3287 | | endloop_1 | |
3288 | In this case, the dependence is carried by loop_1. */ | |
3289 | loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b; | |
1f24dd47 | 3290 | loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth; |
56cf8686 SP |
3291 | |
3292 | /* If the loop number is still greater than the number of | |
3293 | loops we've been asked to analyze, or negative, | |
3294 | something is borked. */ | |
1f24dd47 DB |
3295 | gcc_assert (loop_depth >= 0); |
3296 | gcc_assert (loop_depth < nb_loops); | |
86df10e3 SP |
3297 | |
3298 | if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) | |
56cf8686 | 3299 | { |
86df10e3 | 3300 | non_affine_dependence_relation (ddr); |
464f49d8 | 3301 | return true; |
56cf8686 | 3302 | } |
86df10e3 SP |
3303 | |
3304 | dist = int_cst_value (SUB_DISTANCE (subscript)); | |
3305 | ||
3306 | if (dist == 0) | |
3307 | dir = dir_equal; | |
3308 | else if (dist > 0) | |
3309 | dir = dir_positive; | |
3310 | else if (dist < 0) | |
3311 | dir = dir_negative; | |
56cf8686 SP |
3312 | |
3313 | /* This is the subscript coupling test. | |
3314 | | loop i = 0, N, 1 | |
3315 | | T[i+1][i] = ... | |
3316 | | ... = T[i][i] | |
3317 | | endloop | |
3318 | There is no dependence. */ | |
1f24dd47 | 3319 | if (init_v[loop_depth] != 0 |
56cf8686 | 3320 | && dir != dir_star |
1f24dd47 DB |
3321 | && (enum data_dependence_direction) dir_v[loop_depth] != dir |
3322 | && (enum data_dependence_direction) dir_v[loop_depth] != dir_star) | |
56cf8686 | 3323 | { |
36d59cf7 | 3324 | finalize_ddr_dependent (ddr, chrec_known); |
464f49d8 | 3325 | return true; |
56cf8686 SP |
3326 | } |
3327 | ||
1f24dd47 DB |
3328 | dir_v[loop_depth] = dir; |
3329 | init_v[loop_depth] = 1; | |
56cf8686 SP |
3330 | } |
3331 | } | |
3332 | ||
3333 | /* There is a distance of 1 on all the outer loops: | |
3334 | ||
3335 | Example: there is a dependence of distance 1 on loop_1 for the array A. | |
3336 | | loop_1 | |
3337 | | A[5] = ... | |
3338 | | endloop | |
3339 | */ | |
3340 | { | |
3341 | struct loop *lca, *loop_a, *loop_b; | |
36d59cf7 DB |
3342 | struct data_reference *a = DDR_A (ddr); |
3343 | struct data_reference *b = DDR_B (ddr); | |
1f24dd47 | 3344 | int lca_depth; |
56cf8686 SP |
3345 | loop_a = loop_containing_stmt (DR_STMT (a)); |
3346 | loop_b = loop_containing_stmt (DR_STMT (b)); | |
3347 | ||
3348 | /* Get the common ancestor loop. */ | |
3349 | lca = find_common_loop (loop_a, loop_b); | |
1f24dd47 | 3350 | lca_depth = lca->depth - first_loop_depth; |
56cf8686 | 3351 | |
1f24dd47 DB |
3352 | gcc_assert (lca_depth >= 0); |
3353 | gcc_assert (lca_depth < nb_loops); | |
86df10e3 | 3354 | |
56cf8686 SP |
3355 | /* For each outer loop where init_v is not set, the accesses are |
3356 | in dependence of distance 1 in the loop. */ | |
3357 | if (lca != loop_a | |
3358 | && lca != loop_b | |
1f24dd47 DB |
3359 | && init_v[lca_depth] == 0) |
3360 | dir_v[lca_depth] = dir_positive; | |
56cf8686 SP |
3361 | |
3362 | lca = lca->outer; | |
3363 | if (lca) | |
3364 | { | |
1f24dd47 | 3365 | lca_depth = lca->depth - first_loop_depth; |
56cf8686 SP |
3366 | while (lca->depth != 0) |
3367 | { | |
86df10e3 SP |
3368 | /* If we're considering just a sub-nest, then don't record |
3369 | any information on the outer loops. */ | |
1f24dd47 | 3370 | if (lca_depth < 0) |
86df10e3 SP |
3371 | break; |
3372 | ||
1f24dd47 | 3373 | gcc_assert (lca_depth < nb_loops); |
86df10e3 | 3374 | |
1f24dd47 DB |
3375 | if (init_v[lca_depth] == 0) |
3376 | dir_v[lca_depth] = dir_positive; | |
56cf8686 | 3377 | lca = lca->outer; |
1f24dd47 | 3378 | lca_depth = lca->depth - first_loop_depth; |
56cf8686 SP |
3379 | |
3380 | } | |
3381 | } | |
3382 | } | |
3383 | ||
36d59cf7 | 3384 | DDR_DIR_VECT (ddr) = dir_v; |
86df10e3 | 3385 | DDR_SIZE_VECT (ddr) = nb_loops; |
464f49d8 | 3386 | return true; |
56cf8686 SP |
3387 | } |
3388 | ||
3389 | /* Returns true when all the access functions of A are affine or | |
3390 | constant. */ | |
3391 | ||
3392 | static bool | |
3393 | access_functions_are_affine_or_constant_p (struct data_reference *a) | |
3394 | { | |
3395 | unsigned int i; | |
86a07404 | 3396 | VEC(tree,heap) **fns = DR_ACCESS_FNS_ADDR (a); |
9cbb7989 | 3397 | tree t; |
56cf8686 | 3398 | |
9cbb7989 KH |
3399 | for (i = 0; VEC_iterate (tree, *fns, i, t); i++) |
3400 | if (!evolution_function_is_constant_p (t) | |
3401 | && !evolution_function_is_affine_multivariate_p (t)) | |
56cf8686 SP |
3402 | return false; |
3403 | ||
3404 | return true; | |
3405 | } | |
3406 | ||
3407 | /* This computes the affine dependence relation between A and B. | |
3408 | CHREC_KNOWN is used for representing the independence between two | |
3409 | accesses, while CHREC_DONT_KNOW is used for representing the unknown | |
3410 | relation. | |
3411 | ||
3412 | Note that it is possible to stop the computation of the dependence | |
3413 | relation the first time we detect a CHREC_KNOWN element for a given | |
3414 | subscript. */ | |
3415 | ||
3416 | void | |
3417 | compute_affine_dependence (struct data_dependence_relation *ddr) | |
3418 | { | |
3419 | struct data_reference *dra = DDR_A (ddr); | |
3420 | struct data_reference *drb = DDR_B (ddr); | |
3421 | ||
3422 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
3423 | { | |
36d59cf7 | 3424 | fprintf (dump_file, "(compute_affine_dependence\n"); |
56cf8686 SP |
3425 | fprintf (dump_file, " (stmt_a = \n"); |
3426 | print_generic_expr (dump_file, DR_STMT (dra), 0); | |
3427 | fprintf (dump_file, ")\n (stmt_b = \n"); | |
3428 | print_generic_expr (dump_file, DR_STMT (drb), 0); | |
3429 | fprintf (dump_file, ")\n"); | |
3430 | } | |
3431 | ||
3432 | /* Analyze only when the dependence relation is not yet known. */ | |
3433 | if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) | |
3434 | { | |
3435 | if (access_functions_are_affine_or_constant_p (dra) | |
3436 | && access_functions_are_affine_or_constant_p (drb)) | |
3437 | subscript_dependence_tester (ddr); | |
3438 | ||
3439 | /* As a last case, if the dependence cannot be determined, or if | |
3440 | the dependence is considered too difficult to determine, answer | |
3441 | "don't know". */ | |
3442 | else | |
3443 | finalize_ddr_dependent (ddr, chrec_dont_know); | |
3444 | } | |
3445 | ||
3446 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
3447 | fprintf (dump_file, ")\n"); | |
3448 | } | |
3449 | ||
789246d7 SP |
3450 | /* This computes the dependence relation for the same data |
3451 | reference into DDR. */ | |
3452 | ||
3453 | static void | |
3454 | compute_self_dependence (struct data_dependence_relation *ddr) | |
3455 | { | |
3456 | unsigned int i; | |
3457 | ||
3458 | for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) | |
3459 | { | |
3460 | struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); | |
3461 | ||
3462 | /* The accessed index overlaps for each iteration. */ | |
3463 | SUB_CONFLICTS_IN_A (subscript) = integer_zero_node; | |
3464 | SUB_CONFLICTS_IN_B (subscript) = integer_zero_node; | |
3465 | SUB_LAST_CONFLICT (subscript) = chrec_dont_know; | |
3466 | } | |
3467 | } | |
3468 | ||
7b8a92e1 KH |
3469 | |
3470 | typedef struct data_dependence_relation *ddr_p; | |
3471 | DEF_VEC_P(ddr_p); | |
3472 | DEF_VEC_ALLOC_P(ddr_p,heap); | |
3473 | ||
56cf8686 | 3474 | /* Compute a subset of the data dependence relation graph. Don't |
86a07404 IR |
3475 | compute read-read and self relations if |
3476 | COMPUTE_SELF_AND_READ_READ_DEPENDENCES is FALSE, and avoid the computation | |
3477 | of the opposite relation, i.e. when AB has been computed, don't compute BA. | |
56cf8686 SP |
3478 | DATAREFS contains a list of data references, and the result is set |
3479 | in DEPENDENCE_RELATIONS. */ | |
3480 | ||
3481 | static void | |
36d59cf7 | 3482 | compute_all_dependences (varray_type datarefs, |
86a07404 | 3483 | bool compute_self_and_read_read_dependences, |
7b8a92e1 | 3484 | VEC(ddr_p,heap) **dependence_relations) |
56cf8686 SP |
3485 | { |
3486 | unsigned int i, j, N; | |
3487 | ||
3488 | N = VARRAY_ACTIVE_SIZE (datarefs); | |
3489 | ||
789246d7 SP |
3490 | /* Note that we specifically skip i == j because it's a self dependence, and |
3491 | use compute_self_dependence below. */ | |
3492 | ||
56cf8686 | 3493 | for (i = 0; i < N; i++) |
789246d7 | 3494 | for (j = i + 1; j < N; j++) |
56cf8686 SP |
3495 | { |
3496 | struct data_reference *a, *b; | |
3497 | struct data_dependence_relation *ddr; | |
3498 | ||
3499 | a = VARRAY_GENERIC_PTR (datarefs, i); | |
3500 | b = VARRAY_GENERIC_PTR (datarefs, j); | |
86a07404 IR |
3501 | if (DR_IS_READ (a) && DR_IS_READ (b) |
3502 | && !compute_self_and_read_read_dependences) | |
3503 | continue; | |
56cf8686 SP |
3504 | ddr = initialize_data_dependence_relation (a, b); |
3505 | ||
7b8a92e1 | 3506 | VEC_safe_push (ddr_p, heap, *dependence_relations, ddr); |
56cf8686 | 3507 | compute_affine_dependence (ddr); |
86df10e3 | 3508 | compute_subscript_distance (ddr); |
56cf8686 | 3509 | } |
86a07404 IR |
3510 | if (!compute_self_and_read_read_dependences) |
3511 | return; | |
789246d7 SP |
3512 | |
3513 | /* Compute self dependence relation of each dataref to itself. */ | |
3514 | ||
3515 | for (i = 0; i < N; i++) | |
3516 | { | |
3517 | struct data_reference *a, *b; | |
3518 | struct data_dependence_relation *ddr; | |
3519 | ||
3520 | a = VARRAY_GENERIC_PTR (datarefs, i); | |
3521 | b = VARRAY_GENERIC_PTR (datarefs, i); | |
3522 | ddr = initialize_data_dependence_relation (a, b); | |
3523 | ||
3524 | VEC_safe_push (ddr_p, heap, *dependence_relations, ddr); | |
3525 | compute_self_dependence (ddr); | |
3526 | compute_subscript_distance (ddr); | |
3527 | } | |
56cf8686 SP |
3528 | } |
3529 | ||
3530 | /* Search the data references in LOOP, and record the information into | |
3531 | DATAREFS. Returns chrec_dont_know when failing to analyze a | |
3532 | difficult case, returns NULL_TREE otherwise. | |
3533 | ||
464f49d8 DB |
3534 | TODO: This function should be made smarter so that it can handle address |
3535 | arithmetic as if they were array accesses, etc. */ | |
56cf8686 | 3536 | |
86df10e3 | 3537 | tree |
56cf8686 SP |
3538 | find_data_references_in_loop (struct loop *loop, varray_type *datarefs) |
3539 | { | |
ccbdbf0a JL |
3540 | basic_block bb, *bbs; |
3541 | unsigned int i; | |
56cf8686 | 3542 | block_stmt_iterator bsi; |
86a07404 | 3543 | struct data_reference *dr; |
86df10e3 | 3544 | |
ccbdbf0a JL |
3545 | bbs = get_loop_body (loop); |
3546 | ||
3547 | for (i = 0; i < loop->num_nodes; i++) | |
56cf8686 | 3548 | { |
ccbdbf0a JL |
3549 | bb = bbs[i]; |
3550 | ||
56cf8686 SP |
3551 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) |
3552 | { | |
3553 | tree stmt = bsi_stmt (bsi); | |
56cf8686 | 3554 | |
4aad410d SP |
3555 | /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects. |
3556 | Calls have side-effects, except those to const or pure | |
3557 | functions. */ | |
3558 | if ((TREE_CODE (stmt) == CALL_EXPR | |
3559 | && !(call_expr_flags (stmt) & (ECF_CONST | ECF_PURE))) | |
3560 | || (TREE_CODE (stmt) == ASM_EXPR | |
3561 | && ASM_VOLATILE_P (stmt))) | |
3562 | goto insert_dont_know_node; | |
56cf8686 | 3563 | |
f47c96aa | 3564 | if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) |
56cf8686 | 3565 | continue; |
4aad410d SP |
3566 | |
3567 | switch (TREE_CODE (stmt)) | |
86df10e3 | 3568 | { |
4aad410d | 3569 | case MODIFY_EXPR: |
86a07404 IR |
3570 | { |
3571 | bool one_inserted = false; | |
3572 | tree opnd0 = TREE_OPERAND (stmt, 0); | |
3573 | tree opnd1 = TREE_OPERAND (stmt, 1); | |
3574 | ||
3575 | if (TREE_CODE (opnd0) == ARRAY_REF | |
3576 | || TREE_CODE (opnd0) == INDIRECT_REF) | |
3577 | { | |
3578 | dr = create_data_ref (opnd0, stmt, false); | |
3579 | if (dr) | |
3580 | { | |
3581 | VARRAY_PUSH_GENERIC_PTR (*datarefs, dr); | |
3582 | one_inserted = true; | |
3583 | } | |
3584 | } | |
3585 | ||
3586 | if (TREE_CODE (opnd1) == ARRAY_REF | |
3587 | || TREE_CODE (opnd1) == INDIRECT_REF) | |
3588 | { | |
3589 | dr = create_data_ref (opnd1, stmt, true); | |
3590 | if (dr) | |
3591 | { | |
3592 | VARRAY_PUSH_GENERIC_PTR (*datarefs, dr); | |
3593 | one_inserted = true; | |
3594 | } | |
3595 | } | |
4aad410d | 3596 | |
86a07404 IR |
3597 | if (!one_inserted) |
3598 | goto insert_dont_know_node; | |
4aad410d | 3599 | |
86a07404 IR |
3600 | break; |
3601 | } | |
4aad410d SP |
3602 | |
3603 | case CALL_EXPR: | |
3604 | { | |
3605 | tree args; | |
3606 | bool one_inserted = false; | |
3607 | ||
86a07404 IR |
3608 | for (args = TREE_OPERAND (stmt, 1); args; |
3609 | args = TREE_CHAIN (args)) | |
3610 | if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF | |
3611 | || TREE_CODE (TREE_VALUE (args)) == INDIRECT_REF) | |
4aad410d | 3612 | { |
86a07404 IR |
3613 | dr = create_data_ref (TREE_VALUE (args), stmt, true); |
3614 | if (dr) | |
3615 | { | |
3616 | VARRAY_PUSH_GENERIC_PTR (*datarefs, dr); | |
3617 | one_inserted = true; | |
3618 | } | |
4aad410d SP |
3619 | } |
3620 | ||
3621 | if (!one_inserted) | |
3622 | goto insert_dont_know_node; | |
3623 | ||
3624 | break; | |
3625 | } | |
3626 | ||
3627 | default: | |
86df10e3 SP |
3628 | { |
3629 | struct data_reference *res; | |
4aad410d SP |
3630 | |
3631 | insert_dont_know_node:; | |
86df10e3 SP |
3632 | res = xmalloc (sizeof (struct data_reference)); |
3633 | DR_STMT (res) = NULL_TREE; | |
3634 | DR_REF (res) = NULL_TREE; | |
86a07404 IR |
3635 | DR_BASE_OBJECT (res) = NULL; |
3636 | DR_TYPE (res) = ARRAY_REF_TYPE; | |
3637 | DR_SET_ACCESS_FNS (res, NULL); | |
3638 | DR_BASE_OBJECT (res) = NULL; | |
86df10e3 | 3639 | DR_IS_READ (res) = false; |
86a07404 IR |
3640 | DR_BASE_ADDRESS (res) = NULL_TREE; |
3641 | DR_OFFSET (res) = NULL_TREE; | |
3642 | DR_INIT (res) = NULL_TREE; | |
3643 | DR_STEP (res) = NULL_TREE; | |
3644 | DR_OFFSET_MISALIGNMENT (res) = NULL_TREE; | |
3645 | DR_MEMTAG (res) = NULL_TREE; | |
3646 | DR_PTR_INFO (res) = NULL; | |
86df10e3 | 3647 | VARRAY_PUSH_GENERIC_PTR (*datarefs, res); |
4aad410d SP |
3648 | |
3649 | free (bbs); | |
3650 | return chrec_dont_know; | |
86df10e3 SP |
3651 | } |
3652 | } | |
3653 | ||
3654 | /* When there are no defs in the loop, the loop is parallel. */ | |
f47c96aa | 3655 | if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)) |
79ebd55c | 3656 | loop->parallel_p = false; |
56cf8686 SP |
3657 | } |
3658 | } | |
3659 | ||
ccbdbf0a JL |
3660 | free (bbs); |
3661 | ||
4aad410d | 3662 | return NULL_TREE; |
56cf8686 SP |
3663 | } |
3664 | ||
3665 | \f | |
3666 | ||
3667 | /* This section contains all the entry points. */ | |
3668 | ||
3669 | /* Given a loop nest LOOP, the following vectors are returned: | |
3670 | *DATAREFS is initialized to all the array elements contained in this loop, | |
86a07404 IR |
3671 | *DEPENDENCE_RELATIONS contains the relations between the data references. |
3672 | Compute read-read and self relations if | |
3673 | COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */ | |
56cf8686 SP |
3674 | |
3675 | void | |
86a07404 IR |
3676 | compute_data_dependences_for_loop (struct loop *loop, |
3677 | bool compute_self_and_read_read_dependences, | |
56cf8686 | 3678 | varray_type *datarefs, |
36d59cf7 | 3679 | varray_type *dependence_relations) |
56cf8686 | 3680 | { |
86a07404 | 3681 | unsigned int i, nb_loops; |
7b8a92e1 KH |
3682 | VEC(ddr_p,heap) *allrelations; |
3683 | struct data_dependence_relation *ddr; | |
86a07404 IR |
3684 | struct loop *loop_nest = loop; |
3685 | ||
3686 | while (loop_nest && loop_nest->outer && loop_nest->outer->outer) | |
3687 | loop_nest = loop_nest->outer; | |
3688 | ||
3689 | nb_loops = loop_nest->level; | |
56cf8686 SP |
3690 | |
3691 | /* If one of the data references is not computable, give up without | |
3692 | spending time to compute other dependences. */ | |
3693 | if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know) | |
3694 | { | |
3695 | struct data_dependence_relation *ddr; | |
3696 | ||
3697 | /* Insert a single relation into dependence_relations: | |
3698 | chrec_dont_know. */ | |
3699 | ddr = initialize_data_dependence_relation (NULL, NULL); | |
3700 | VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr); | |
1f24dd47 DB |
3701 | build_classic_dist_vector (ddr, nb_loops, loop->depth); |
3702 | build_classic_dir_vector (ddr, nb_loops, loop->depth); | |
56cf8686 SP |
3703 | return; |
3704 | } | |
3705 | ||
7b8a92e1 | 3706 | allrelations = NULL; |
86a07404 IR |
3707 | compute_all_dependences (*datarefs, compute_self_and_read_read_dependences, |
3708 | &allrelations); | |
56cf8686 | 3709 | |
7b8a92e1 | 3710 | for (i = 0; VEC_iterate (ddr_p, allrelations, i, ddr); i++) |
56cf8686 | 3711 | { |
86a07404 | 3712 | if (build_classic_dist_vector (ddr, nb_loops, loop_nest->depth)) |
464f49d8 DB |
3713 | { |
3714 | VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr); | |
86a07404 | 3715 | build_classic_dir_vector (ddr, nb_loops, loop_nest->depth); |
464f49d8 | 3716 | } |
56cf8686 SP |
3717 | } |
3718 | } | |
3719 | ||
3720 | /* Entry point (for testing only). Analyze all the data references | |
3721 | and the dependence relations. | |
3722 | ||
3723 | The data references are computed first. | |
3724 | ||
3725 | A relation on these nodes is represented by a complete graph. Some | |
3726 | of the relations could be of no interest, thus the relations can be | |
3727 | computed on demand. | |
3728 | ||
3729 | In the following function we compute all the relations. This is | |
3730 | just a first implementation that is here for: | |
3731 | - for showing how to ask for the dependence relations, | |
3732 | - for the debugging the whole dependence graph, | |
3733 | - for the dejagnu testcases and maintenance. | |
3734 | ||
3735 | It is possible to ask only for a part of the graph, avoiding to | |
3736 | compute the whole dependence graph. The computed dependences are | |
3737 | stored in a knowledge base (KB) such that later queries don't | |
3738 | recompute the same information. The implementation of this KB is | |
3739 | transparent to the optimizer, and thus the KB can be changed with a | |
3740 | more efficient implementation, or the KB could be disabled. */ | |
3741 | ||
3742 | void | |
3743 | analyze_all_data_dependences (struct loops *loops) | |
3744 | { | |
3745 | unsigned int i; | |
3746 | varray_type datarefs; | |
3747 | varray_type dependence_relations; | |
56cf8686 SP |
3748 | int nb_data_refs = 10; |
3749 | ||
56cf8686 SP |
3750 | VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs"); |
3751 | VARRAY_GENERIC_PTR_INIT (dependence_relations, | |
3752 | nb_data_refs * nb_data_refs, | |
3753 | "dependence_relations"); | |
3754 | ||
3755 | /* Compute DDs on the whole function. */ | |
86a07404 | 3756 | compute_data_dependences_for_loop (loops->parray[0], false, |
36d59cf7 | 3757 | &datarefs, &dependence_relations); |
56cf8686 SP |
3758 | |
3759 | if (dump_file) | |
3760 | { | |
3761 | dump_data_dependence_relations (dump_file, dependence_relations); | |
3762 | fprintf (dump_file, "\n\n"); | |
56cf8686 | 3763 | |
86df10e3 SP |
3764 | if (dump_flags & TDF_DETAILS) |
3765 | dump_dist_dir_vectors (dump_file, dependence_relations); | |
56cf8686 | 3766 | |
86df10e3 | 3767 | if (dump_flags & TDF_STATS) |
56cf8686 | 3768 | { |
86df10e3 SP |
3769 | unsigned nb_top_relations = 0; |
3770 | unsigned nb_bot_relations = 0; | |
3771 | unsigned nb_basename_differ = 0; | |
3772 | unsigned nb_chrec_relations = 0; | |
3773 | ||
3774 | for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++) | |
3775 | { | |
3776 | struct data_dependence_relation *ddr; | |
3777 | ddr = VARRAY_GENERIC_PTR (dependence_relations, i); | |
56cf8686 | 3778 | |
86df10e3 SP |
3779 | if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr))) |
3780 | nb_top_relations++; | |
56cf8686 | 3781 | |
86df10e3 SP |
3782 | else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) |
3783 | { | |
3784 | struct data_reference *a = DDR_A (ddr); | |
3785 | struct data_reference *b = DDR_B (ddr); | |
3786 | bool differ_p; | |
56cf8686 | 3787 | |
86a07404 IR |
3788 | if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b) |
3789 | && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)) | |
3790 | || (base_object_differ_p (a, b, &differ_p) | |
3791 | && differ_p)) | |
86df10e3 SP |
3792 | nb_basename_differ++; |
3793 | else | |
3794 | nb_bot_relations++; | |
3795 | } | |
56cf8686 | 3796 | |
86df10e3 SP |
3797 | else |
3798 | nb_chrec_relations++; | |
3799 | } | |
56cf8686 | 3800 | |
86df10e3 SP |
3801 | gather_stats_on_scev_database (); |
3802 | } | |
56cf8686 | 3803 | } |
36d59cf7 DB |
3804 | |
3805 | free_dependence_relations (dependence_relations); | |
3806 | free_data_refs (datarefs); | |
3807 | } | |
3808 | ||
3809 | /* Free the memory used by a data dependence relation DDR. */ | |
3810 | ||
3811 | void | |
3812 | free_dependence_relation (struct data_dependence_relation *ddr) | |
3813 | { | |
3814 | if (ddr == NULL) | |
3815 | return; | |
3816 | ||
3817 | if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr)) | |
3818 | varray_clear (DDR_SUBSCRIPTS (ddr)); | |
3819 | free (ddr); | |
3820 | } | |
3821 | ||
3822 | /* Free the memory used by the data dependence relations from | |
3823 | DEPENDENCE_RELATIONS. */ | |
3824 | ||
3825 | void | |
3826 | free_dependence_relations (varray_type dependence_relations) | |
3827 | { | |
3828 | unsigned int i; | |
3829 | if (dependence_relations == NULL) | |
3830 | return; | |
3831 | ||
3832 | for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++) | |
3833 | free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i)); | |
56cf8686 | 3834 | varray_clear (dependence_relations); |
56cf8686 SP |
3835 | } |
3836 | ||
36d59cf7 DB |
3837 | /* Free the memory used by the data references from DATAREFS. */ |
3838 | ||
3839 | void | |
3840 | free_data_refs (varray_type datarefs) | |
3841 | { | |
3842 | unsigned int i; | |
3843 | ||
3844 | if (datarefs == NULL) | |
3845 | return; | |
56cf8686 | 3846 | |
36d59cf7 DB |
3847 | for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++) |
3848 | { | |
3849 | struct data_reference *dr = (struct data_reference *) | |
3850 | VARRAY_GENERIC_PTR (datarefs, i); | |
01c49ce8 KH |
3851 | if (dr) |
3852 | { | |
86a07404 | 3853 | DR_FREE_ACCESS_FNS (dr); |
01c49ce8 KH |
3854 | free (dr); |
3855 | } | |
36d59cf7 DB |
3856 | } |
3857 | varray_clear (datarefs); | |
3858 | } | |
86df10e3 | 3859 |