]>
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 | |
19 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
20 | 02111-1307, USA. */ | |
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 | |
79fe1b3b | 97 | /* This is the simplest data dependence test: determines whether the |
68b26d5c SP |
98 | data references A and B access the same array/region. Returns |
99 | false when the property is not computable at compile time. | |
100 | Otherwise return true, and DIFFER_P will record the result. This | |
101 | utility will not be necessary when alias_sets_conflict_p will be | |
102 | less conservative. */ | |
79fe1b3b DN |
103 | |
104 | bool | |
105 | array_base_name_differ_p (struct data_reference *a, | |
106 | struct data_reference *b, | |
107 | bool *differ_p) | |
108 | { | |
109 | tree base_a = DR_BASE_NAME (a); | |
110 | tree base_b = DR_BASE_NAME (b); | |
79fe1b3b | 111 | |
e3a8a4ed IR |
112 | if (!base_a || !base_b) |
113 | return false; | |
114 | ||
68b26d5c SP |
115 | /* Determine if same base. Example: for the array accesses |
116 | a[i], b[i] or pointer accesses *a, *b, bases are a, b. */ | |
79fe1b3b DN |
117 | if (base_a == base_b) |
118 | { | |
119 | *differ_p = false; | |
120 | return true; | |
121 | } | |
122 | ||
68b26d5c SP |
123 | /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p) |
124 | and (*q) */ | |
79fe1b3b DN |
125 | if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF |
126 | && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)) | |
127 | { | |
128 | *differ_p = false; | |
129 | return true; | |
130 | } | |
131 | ||
86df10e3 | 132 | /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */ |
79fe1b3b DN |
133 | if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF |
134 | && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0) | |
135 | && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1)) | |
136 | { | |
137 | *differ_p = false; | |
138 | return true; | |
139 | } | |
140 | ||
86df10e3 | 141 | |
68b26d5c | 142 | /* Determine if different bases. */ |
79fe1b3b | 143 | |
68b26d5c | 144 | /* At this point we know that base_a != base_b. However, pointer |
59c4456e KH |
145 | accesses of the form x=(*p) and y=(*q), whose bases are p and q, |
146 | may still be pointing to the same base. In SSAed GIMPLE p and q will | |
147 | be SSA_NAMES in this case. Therefore, here we check if they are | |
148 | really two different declarations. */ | |
79fe1b3b DN |
149 | if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL) |
150 | { | |
151 | *differ_p = true; | |
152 | return true; | |
153 | } | |
154 | ||
68b26d5c SP |
155 | /* Compare two record/union bases s.a and t.b: s != t or (a != b and |
156 | s and t are not unions). */ | |
79fe1b3b DN |
157 | if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF |
158 | && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL | |
159 | && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL | |
160 | && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0)) | |
161 | || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE | |
162 | && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE | |
163 | && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1)))) | |
164 | { | |
165 | *differ_p = true; | |
166 | return true; | |
167 | } | |
168 | ||
68b26d5c | 169 | /* Compare a record/union access and an array access. */ |
79fe1b3b DN |
170 | if ((TREE_CODE (base_a) == VAR_DECL |
171 | && (TREE_CODE (base_b) == COMPONENT_REF | |
172 | && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL)) | |
173 | || (TREE_CODE (base_b) == VAR_DECL | |
174 | && (TREE_CODE (base_a) == COMPONENT_REF | |
175 | && TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL))) | |
176 | { | |
177 | *differ_p = true; | |
178 | return true; | |
179 | } | |
180 | ||
79fe1b3b DN |
181 | return false; |
182 | } | |
56cf8686 SP |
183 | |
184 | /* Returns true iff A divides B. */ | |
185 | ||
186 | static inline bool | |
187 | tree_fold_divides_p (tree type, | |
188 | tree a, | |
189 | tree b) | |
190 | { | |
56cf8686 SP |
191 | /* Determines whether (A == gcd (A, B)). */ |
192 | return integer_zerop | |
193 | (fold (build (MINUS_EXPR, type, a, tree_fold_gcd (a, b)))); | |
194 | } | |
195 | ||
86df10e3 SP |
196 | /* Compute the greatest common denominator of two numbers using |
197 | Euclid's algorithm. */ | |
56cf8686 | 198 | |
86df10e3 SP |
199 | static int |
200 | gcd (int a, int b) | |
56cf8686 | 201 | { |
56cf8686 | 202 | |
86df10e3 | 203 | int x, y, z; |
56cf8686 | 204 | |
86df10e3 SP |
205 | x = abs (a); |
206 | y = abs (b); | |
207 | ||
208 | while (x>0) | |
56cf8686 | 209 | { |
86df10e3 SP |
210 | z = y % x; |
211 | y = x; | |
212 | x = z; | |
56cf8686 | 213 | } |
86df10e3 SP |
214 | |
215 | return (y); | |
216 | } | |
217 | ||
218 | /* Returns true iff A divides B. */ | |
219 | ||
220 | static inline bool | |
221 | int_divides_p (int a, int b) | |
222 | { | |
223 | return ((b % a) == 0); | |
56cf8686 SP |
224 | } |
225 | ||
226 | \f | |
227 | ||
228 | /* Dump into FILE all the data references from DATAREFS. */ | |
229 | ||
230 | void | |
231 | dump_data_references (FILE *file, | |
232 | varray_type datarefs) | |
233 | { | |
234 | unsigned int i; | |
235 | ||
236 | for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++) | |
237 | dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i)); | |
238 | } | |
239 | ||
240 | /* Dump into FILE all the dependence relations from DDR. */ | |
241 | ||
242 | void | |
243 | dump_data_dependence_relations (FILE *file, | |
244 | varray_type ddr) | |
245 | { | |
246 | unsigned int i; | |
247 | ||
248 | for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++) | |
249 | dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i)); | |
250 | } | |
251 | ||
252 | /* Dump function for a DATA_REFERENCE structure. */ | |
253 | ||
254 | void | |
255 | dump_data_reference (FILE *outf, | |
256 | struct data_reference *dr) | |
257 | { | |
258 | unsigned int i; | |
259 | ||
36d59cf7 | 260 | fprintf (outf, "(Data Ref: \n stmt: "); |
56cf8686 SP |
261 | print_generic_stmt (outf, DR_STMT (dr), 0); |
262 | fprintf (outf, " ref: "); | |
263 | print_generic_stmt (outf, DR_REF (dr), 0); | |
264 | fprintf (outf, " base_name: "); | |
265 | print_generic_stmt (outf, DR_BASE_NAME (dr), 0); | |
266 | ||
267 | for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++) | |
268 | { | |
269 | fprintf (outf, " Access function %d: ", i); | |
270 | print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0); | |
271 | } | |
272 | fprintf (outf, ")\n"); | |
273 | } | |
274 | ||
86df10e3 SP |
275 | /* Dump function for a SUBSCRIPT structure. */ |
276 | ||
277 | void | |
278 | dump_subscript (FILE *outf, struct subscript *subscript) | |
279 | { | |
280 | tree chrec = SUB_CONFLICTS_IN_A (subscript); | |
281 | ||
282 | fprintf (outf, "\n (subscript \n"); | |
283 | fprintf (outf, " iterations_that_access_an_element_twice_in_A: "); | |
284 | print_generic_stmt (outf, chrec, 0); | |
285 | if (chrec == chrec_known) | |
286 | fprintf (outf, " (no dependence)\n"); | |
287 | else if (chrec_contains_undetermined (chrec)) | |
288 | fprintf (outf, " (don't know)\n"); | |
289 | else | |
290 | { | |
291 | tree last_iteration = SUB_LAST_CONFLICT (subscript); | |
292 | fprintf (outf, " last_conflict: "); | |
293 | print_generic_stmt (outf, last_iteration, 0); | |
294 | } | |
295 | ||
296 | chrec = SUB_CONFLICTS_IN_B (subscript); | |
297 | fprintf (outf, " iterations_that_access_an_element_twice_in_B: "); | |
298 | print_generic_stmt (outf, chrec, 0); | |
299 | if (chrec == chrec_known) | |
300 | fprintf (outf, " (no dependence)\n"); | |
301 | else if (chrec_contains_undetermined (chrec)) | |
302 | fprintf (outf, " (don't know)\n"); | |
303 | else | |
304 | { | |
305 | tree last_iteration = SUB_LAST_CONFLICT (subscript); | |
306 | fprintf (outf, " last_conflict: "); | |
307 | print_generic_stmt (outf, last_iteration, 0); | |
308 | } | |
309 | ||
310 | fprintf (outf, " (Subscript distance: "); | |
311 | print_generic_stmt (outf, SUB_DISTANCE (subscript), 0); | |
312 | fprintf (outf, " )\n"); | |
313 | fprintf (outf, " )\n"); | |
314 | } | |
315 | ||
56cf8686 SP |
316 | /* Dump function for a DATA_DEPENDENCE_RELATION structure. */ |
317 | ||
318 | void | |
319 | dump_data_dependence_relation (FILE *outf, | |
320 | struct data_dependence_relation *ddr) | |
321 | { | |
56cf8686 | 322 | struct data_reference *dra, *drb; |
86df10e3 | 323 | |
56cf8686 SP |
324 | dra = DDR_A (ddr); |
325 | drb = DDR_B (ddr); | |
86df10e3 SP |
326 | fprintf (outf, "(Data Dep: \n"); |
327 | if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) | |
56cf8686 SP |
328 | fprintf (outf, " (don't know)\n"); |
329 | ||
330 | else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) | |
331 | fprintf (outf, " (no dependence)\n"); | |
332 | ||
86df10e3 | 333 | else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) |
56cf8686 | 334 | { |
86df10e3 | 335 | unsigned int i; |
56cf8686 SP |
336 | for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) |
337 | { | |
56cf8686 SP |
338 | fprintf (outf, " access_fn_A: "); |
339 | print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0); | |
340 | fprintf (outf, " access_fn_B: "); | |
341 | print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0); | |
86df10e3 | 342 | dump_subscript (outf, DDR_SUBSCRIPT (ddr, i)); |
56cf8686 | 343 | } |
86df10e3 | 344 | if (DDR_DIST_VECT (ddr)) |
56cf8686 | 345 | { |
86df10e3 SP |
346 | fprintf (outf, " distance_vect: "); |
347 | print_lambda_vector (outf, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr)); | |
348 | } | |
349 | if (DDR_DIR_VECT (ddr)) | |
350 | { | |
351 | fprintf (outf, " direction_vect: "); | |
352 | print_lambda_vector (outf, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr)); | |
56cf8686 | 353 | } |
56cf8686 SP |
354 | } |
355 | ||
356 | fprintf (outf, ")\n"); | |
357 | } | |
358 | ||
359 | ||
360 | ||
361 | /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */ | |
362 | ||
363 | void | |
364 | dump_data_dependence_direction (FILE *file, | |
365 | enum data_dependence_direction dir) | |
366 | { | |
367 | switch (dir) | |
368 | { | |
369 | case dir_positive: | |
370 | fprintf (file, "+"); | |
371 | break; | |
372 | ||
373 | case dir_negative: | |
374 | fprintf (file, "-"); | |
375 | break; | |
376 | ||
377 | case dir_equal: | |
378 | fprintf (file, "="); | |
379 | break; | |
380 | ||
381 | case dir_positive_or_negative: | |
382 | fprintf (file, "+-"); | |
383 | break; | |
384 | ||
385 | case dir_positive_or_equal: | |
386 | fprintf (file, "+="); | |
387 | break; | |
388 | ||
389 | case dir_negative_or_equal: | |
390 | fprintf (file, "-="); | |
391 | break; | |
392 | ||
393 | case dir_star: | |
394 | fprintf (file, "*"); | |
395 | break; | |
396 | ||
397 | default: | |
398 | break; | |
399 | } | |
400 | } | |
401 | ||
86df10e3 SP |
402 | /* Dumps the distance and direction vectors in FILE. DDRS contains |
403 | the dependence relations, and VECT_SIZE is the size of the | |
404 | dependence vectors, or in other words the number of loops in the | |
405 | considered nest. */ | |
406 | ||
407 | void | |
408 | dump_dist_dir_vectors (FILE *file, varray_type ddrs) | |
409 | { | |
410 | unsigned int i; | |
411 | ||
412 | for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++) | |
413 | { | |
414 | struct data_dependence_relation *ddr = | |
415 | (struct data_dependence_relation *) | |
416 | VARRAY_GENERIC_PTR (ddrs, i); | |
417 | if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE | |
418 | && DDR_AFFINE_P (ddr)) | |
419 | { | |
420 | fprintf (file, "DISTANCE_V ("); | |
421 | print_lambda_vector (file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr)); | |
422 | fprintf (file, ")\n"); | |
423 | fprintf (file, "DIRECTION_V ("); | |
424 | print_lambda_vector (file, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr)); | |
425 | fprintf (file, ")\n"); | |
426 | } | |
427 | } | |
428 | fprintf (file, "\n\n"); | |
429 | } | |
430 | ||
431 | /* Dumps the data dependence relations DDRS in FILE. */ | |
432 | ||
433 | void | |
434 | dump_ddrs (FILE *file, varray_type ddrs) | |
435 | { | |
436 | unsigned int i; | |
437 | ||
438 | for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++) | |
439 | { | |
440 | struct data_dependence_relation *ddr = | |
441 | (struct data_dependence_relation *) | |
442 | VARRAY_GENERIC_PTR (ddrs, i); | |
443 | dump_data_dependence_relation (file, ddr); | |
444 | } | |
445 | fprintf (file, "\n\n"); | |
446 | } | |
447 | ||
56cf8686 SP |
448 | \f |
449 | ||
79ebd55c SP |
450 | /* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe |
451 | approximation of the number of iterations for LOOP. */ | |
86df10e3 SP |
452 | |
453 | static void | |
454 | compute_estimated_nb_iterations (struct loop *loop) | |
455 | { | |
79ebd55c SP |
456 | struct nb_iter_bound *bound; |
457 | ||
458 | for (bound = loop->bounds; bound; bound = bound->next) | |
459 | if (TREE_CODE (bound->bound) == INTEGER_CST | |
460 | /* Update only when there is no previous estimation. */ | |
461 | && (chrec_contains_undetermined (loop->estimated_nb_iterations) | |
462 | /* Or when the current estimation is smaller. */ | |
463 | || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations))) | |
464 | loop->estimated_nb_iterations = bound->bound; | |
86df10e3 SP |
465 | } |
466 | ||
467 | /* Estimate the number of iterations from the size of the data and the | |
468 | access functions. */ | |
469 | ||
470 | static void | |
471 | estimate_niter_from_size_of_data (struct loop *loop, | |
472 | tree opnd0, | |
473 | tree access_fn, | |
474 | tree stmt) | |
475 | { | |
476 | tree estimation; | |
477 | tree array_size, data_size, element_size; | |
478 | tree init, step; | |
479 | ||
480 | init = initial_condition (access_fn); | |
481 | step = evolution_part_in_loop_num (access_fn, loop->num); | |
482 | ||
483 | array_size = TYPE_SIZE (TREE_TYPE (opnd0)); | |
484 | element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0))); | |
485 | if (array_size == NULL_TREE | |
9ba64a4a SP |
486 | || TREE_CODE (array_size) != INTEGER_CST |
487 | || TREE_CODE (element_size) != INTEGER_CST) | |
86df10e3 SP |
488 | return; |
489 | ||
490 | data_size = fold (build2 (EXACT_DIV_EXPR, integer_type_node, | |
9ba64a4a | 491 | array_size, element_size)); |
86df10e3 SP |
492 | |
493 | if (init != NULL_TREE | |
494 | && step != NULL_TREE | |
495 | && TREE_CODE (init) == INTEGER_CST | |
496 | && TREE_CODE (step) == INTEGER_CST) | |
497 | { | |
498 | estimation = fold (build2 (CEIL_DIV_EXPR, integer_type_node, | |
499 | fold (build2 (MINUS_EXPR, integer_type_node, | |
500 | data_size, init)), step)); | |
501 | ||
502 | record_estimate (loop, estimation, boolean_true_node, stmt); | |
503 | } | |
504 | } | |
505 | ||
56cf8686 SP |
506 | /* Given an ARRAY_REF node REF, records its access functions. |
507 | Example: given A[i][3], record in ACCESS_FNS the opnd1 function, | |
89dbed81 KH |
508 | i.e. the constant "3", then recursively call the function on opnd0, |
509 | i.e. the ARRAY_REF "A[i]". The function returns the base name: | |
56cf8686 SP |
510 | "A". */ |
511 | ||
512 | static tree | |
513 | analyze_array_indexes (struct loop *loop, | |
9cbb7989 | 514 | VEC(tree,heap) **access_fns, |
86df10e3 | 515 | tree ref, tree stmt) |
56cf8686 SP |
516 | { |
517 | tree opnd0, opnd1; | |
518 | tree access_fn; | |
519 | ||
520 | opnd0 = TREE_OPERAND (ref, 0); | |
521 | opnd1 = TREE_OPERAND (ref, 1); | |
522 | ||
523 | /* The detection of the evolution function for this data access is | |
524 | postponed until the dependence test. This lazy strategy avoids | |
525 | the computation of access functions that are of no interest for | |
526 | the optimizers. */ | |
527 | access_fn = instantiate_parameters | |
528 | (loop, analyze_scalar_evolution (loop, opnd1)); | |
86df10e3 | 529 | |
79ebd55c | 530 | if (chrec_contains_undetermined (loop->estimated_nb_iterations)) |
86df10e3 | 531 | estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt); |
56cf8686 | 532 | |
9cbb7989 | 533 | VEC_safe_push (tree, heap, *access_fns, access_fn); |
56cf8686 SP |
534 | |
535 | /* Recursively record other array access functions. */ | |
536 | if (TREE_CODE (opnd0) == ARRAY_REF) | |
86df10e3 | 537 | return analyze_array_indexes (loop, access_fns, opnd0, stmt); |
56cf8686 SP |
538 | |
539 | /* Return the base name of the data access. */ | |
540 | else | |
541 | return opnd0; | |
542 | } | |
543 | ||
6cb38cd4 | 544 | /* For a data reference REF contained in the statement STMT, initialize |
56cf8686 SP |
545 | a DATA_REFERENCE structure, and return it. IS_READ flag has to be |
546 | set to true when REF is in the right hand side of an | |
547 | assignment. */ | |
548 | ||
549 | struct data_reference * | |
550 | analyze_array (tree stmt, tree ref, bool is_read) | |
551 | { | |
552 | struct data_reference *res; | |
553 | ||
554 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
555 | { | |
556 | fprintf (dump_file, "(analyze_array \n"); | |
557 | fprintf (dump_file, " (ref = "); | |
558 | print_generic_stmt (dump_file, ref, 0); | |
559 | fprintf (dump_file, ")\n"); | |
560 | } | |
561 | ||
36d59cf7 | 562 | res = xmalloc (sizeof (struct data_reference)); |
56cf8686 | 563 | |
56cf8686 SP |
564 | DR_STMT (res) = stmt; |
565 | DR_REF (res) = ref; | |
9cbb7989 | 566 | DR_ACCESS_FNS (res) = VEC_alloc (tree, heap, 3); |
56cf8686 | 567 | DR_BASE_NAME (res) = analyze_array_indexes |
86df10e3 | 568 | (loop_containing_stmt (stmt), &(DR_ACCESS_FNS (res)), ref, stmt); |
56cf8686 SP |
569 | DR_IS_READ (res) = is_read; |
570 | ||
571 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
572 | fprintf (dump_file, ")\n"); | |
573 | ||
574 | return res; | |
575 | } | |
576 | ||
6cb38cd4 | 577 | /* For a data reference REF contained in the statement STMT, initialize |
56cf8686 SP |
578 | a DATA_REFERENCE structure, and return it. */ |
579 | ||
580 | struct data_reference * | |
581 | init_data_ref (tree stmt, | |
582 | tree ref, | |
583 | tree base, | |
79fe1b3b DN |
584 | tree access_fn, |
585 | bool is_read) | |
56cf8686 SP |
586 | { |
587 | struct data_reference *res; | |
588 | ||
589 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
590 | { | |
591 | fprintf (dump_file, "(init_data_ref \n"); | |
592 | fprintf (dump_file, " (ref = "); | |
593 | print_generic_stmt (dump_file, ref, 0); | |
594 | fprintf (dump_file, ")\n"); | |
595 | } | |
596 | ||
36d59cf7 | 597 | res = xmalloc (sizeof (struct data_reference)); |
56cf8686 | 598 | |
56cf8686 SP |
599 | DR_STMT (res) = stmt; |
600 | DR_REF (res) = ref; | |
9cbb7989 | 601 | DR_ACCESS_FNS (res) = VEC_alloc (tree, heap, 5); |
56cf8686 | 602 | DR_BASE_NAME (res) = base; |
9cbb7989 | 603 | VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn); |
79fe1b3b | 604 | DR_IS_READ (res) = is_read; |
56cf8686 SP |
605 | |
606 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
607 | fprintf (dump_file, ")\n"); | |
608 | ||
609 | return res; | |
610 | } | |
611 | ||
612 | \f | |
613 | ||
86df10e3 SP |
614 | /* Returns true when all the functions of a tree_vec CHREC are the |
615 | same. */ | |
616 | ||
617 | static bool | |
618 | all_chrecs_equal_p (tree chrec) | |
619 | { | |
620 | int j; | |
621 | ||
622 | for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++) | |
623 | { | |
624 | tree chrec_j = TREE_VEC_ELT (chrec, j); | |
625 | tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1); | |
626 | if (!integer_zerop | |
627 | (chrec_fold_minus | |
628 | (integer_type_node, chrec_j, chrec_j_1))) | |
629 | return false; | |
630 | } | |
631 | return true; | |
632 | } | |
633 | ||
634 | /* Determine for each subscript in the data dependence relation DDR | |
635 | the distance. */ | |
56cf8686 | 636 | |
b52485c6 | 637 | void |
86df10e3 | 638 | compute_subscript_distance (struct data_dependence_relation *ddr) |
56cf8686 SP |
639 | { |
640 | if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) | |
641 | { | |
642 | unsigned int i; | |
643 | ||
644 | for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) | |
645 | { | |
646 | tree conflicts_a, conflicts_b, difference; | |
647 | struct subscript *subscript; | |
648 | ||
649 | subscript = DDR_SUBSCRIPT (ddr, i); | |
650 | conflicts_a = SUB_CONFLICTS_IN_A (subscript); | |
651 | conflicts_b = SUB_CONFLICTS_IN_B (subscript); | |
86df10e3 SP |
652 | |
653 | if (TREE_CODE (conflicts_a) == TREE_VEC) | |
654 | { | |
655 | if (!all_chrecs_equal_p (conflicts_a)) | |
656 | { | |
657 | SUB_DISTANCE (subscript) = chrec_dont_know; | |
658 | return; | |
659 | } | |
660 | else | |
661 | conflicts_a = TREE_VEC_ELT (conflicts_a, 0); | |
662 | } | |
663 | ||
664 | if (TREE_CODE (conflicts_b) == TREE_VEC) | |
665 | { | |
666 | if (!all_chrecs_equal_p (conflicts_b)) | |
667 | { | |
668 | SUB_DISTANCE (subscript) = chrec_dont_know; | |
669 | return; | |
670 | } | |
671 | else | |
672 | conflicts_b = TREE_VEC_ELT (conflicts_b, 0); | |
673 | } | |
674 | ||
675 | difference = chrec_fold_minus | |
56cf8686 SP |
676 | (integer_type_node, conflicts_b, conflicts_a); |
677 | ||
678 | if (evolution_function_is_constant_p (difference)) | |
679 | SUB_DISTANCE (subscript) = difference; | |
680 | ||
681 | else | |
682 | SUB_DISTANCE (subscript) = chrec_dont_know; | |
683 | } | |
684 | } | |
685 | } | |
686 | ||
687 | /* Initialize a ddr. */ | |
688 | ||
689 | struct data_dependence_relation * | |
690 | initialize_data_dependence_relation (struct data_reference *a, | |
691 | struct data_reference *b) | |
692 | { | |
693 | struct data_dependence_relation *res; | |
79fe1b3b | 694 | bool differ_p; |
56cf8686 | 695 | |
36d59cf7 | 696 | res = xmalloc (sizeof (struct data_dependence_relation)); |
56cf8686 SP |
697 | DDR_A (res) = a; |
698 | DDR_B (res) = b; | |
699 | ||
700 | if (a == NULL || b == NULL | |
701 | || DR_BASE_NAME (a) == NULL_TREE | |
702 | || DR_BASE_NAME (b) == NULL_TREE) | |
703 | DDR_ARE_DEPENDENT (res) = chrec_dont_know; | |
704 | ||
705 | /* When the dimensions of A and B differ, we directly initialize | |
706 | the relation to "there is no dependence": chrec_known. */ | |
707 | else if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b) | |
79fe1b3b | 708 | || (array_base_name_differ_p (a, b, &differ_p) && differ_p)) |
56cf8686 SP |
709 | DDR_ARE_DEPENDENT (res) = chrec_known; |
710 | ||
711 | else | |
712 | { | |
713 | unsigned int i; | |
86df10e3 | 714 | DDR_AFFINE_P (res) = true; |
56cf8686 SP |
715 | DDR_ARE_DEPENDENT (res) = NULL_TREE; |
716 | DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a)); | |
86df10e3 SP |
717 | DDR_SIZE_VECT (res) = 0; |
718 | DDR_DIST_VECT (res) = NULL; | |
719 | DDR_DIR_VECT (res) = NULL; | |
56cf8686 SP |
720 | |
721 | for (i = 0; i < DR_NUM_DIMENSIONS (a); i++) | |
722 | { | |
723 | struct subscript *subscript; | |
724 | ||
36d59cf7 | 725 | subscript = xmalloc (sizeof (struct subscript)); |
56cf8686 SP |
726 | SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know; |
727 | SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know; | |
86df10e3 | 728 | SUB_LAST_CONFLICT (subscript) = chrec_dont_know; |
56cf8686 | 729 | SUB_DISTANCE (subscript) = chrec_dont_know; |
56cf8686 SP |
730 | VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript); |
731 | } | |
732 | } | |
733 | ||
734 | return res; | |
735 | } | |
736 | ||
737 | /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap | |
738 | description. */ | |
739 | ||
740 | static inline void | |
741 | finalize_ddr_dependent (struct data_dependence_relation *ddr, | |
742 | tree chrec) | |
743 | { | |
36d59cf7 DB |
744 | if (dump_file && (dump_flags & TDF_DETAILS)) |
745 | { | |
746 | fprintf (dump_file, "(dependence classified: "); | |
747 | print_generic_expr (dump_file, chrec, 0); | |
748 | fprintf (dump_file, ")\n"); | |
749 | } | |
750 | ||
56cf8686 SP |
751 | DDR_ARE_DEPENDENT (ddr) = chrec; |
752 | varray_clear (DDR_SUBSCRIPTS (ddr)); | |
753 | } | |
754 | ||
86df10e3 SP |
755 | /* The dependence relation DDR cannot be represented by a distance |
756 | vector. */ | |
757 | ||
758 | static inline void | |
759 | non_affine_dependence_relation (struct data_dependence_relation *ddr) | |
760 | { | |
761 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
762 | fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n"); | |
763 | ||
764 | DDR_AFFINE_P (ddr) = false; | |
765 | } | |
766 | ||
56cf8686 SP |
767 | \f |
768 | ||
769 | /* This section contains the classic Banerjee tests. */ | |
770 | ||
771 | /* Returns true iff CHREC_A and CHREC_B are not dependent on any index | |
772 | variables, i.e., if the ZIV (Zero Index Variable) test is true. */ | |
773 | ||
774 | static inline bool | |
775 | ziv_subscript_p (tree chrec_a, | |
776 | tree chrec_b) | |
777 | { | |
778 | return (evolution_function_is_constant_p (chrec_a) | |
779 | && evolution_function_is_constant_p (chrec_b)); | |
780 | } | |
781 | ||
782 | /* Returns true iff CHREC_A and CHREC_B are dependent on an index | |
783 | variable, i.e., if the SIV (Single Index Variable) test is true. */ | |
784 | ||
785 | static bool | |
786 | siv_subscript_p (tree chrec_a, | |
787 | tree chrec_b) | |
788 | { | |
789 | if ((evolution_function_is_constant_p (chrec_a) | |
790 | && evolution_function_is_univariate_p (chrec_b)) | |
791 | || (evolution_function_is_constant_p (chrec_b) | |
792 | && evolution_function_is_univariate_p (chrec_a))) | |
793 | return true; | |
794 | ||
795 | if (evolution_function_is_univariate_p (chrec_a) | |
796 | && evolution_function_is_univariate_p (chrec_b)) | |
797 | { | |
798 | switch (TREE_CODE (chrec_a)) | |
799 | { | |
800 | case POLYNOMIAL_CHREC: | |
801 | switch (TREE_CODE (chrec_b)) | |
802 | { | |
803 | case POLYNOMIAL_CHREC: | |
804 | if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b)) | |
805 | return false; | |
806 | ||
807 | default: | |
808 | return true; | |
809 | } | |
810 | ||
811 | default: | |
812 | return true; | |
813 | } | |
814 | } | |
815 | ||
816 | return false; | |
817 | } | |
818 | ||
819 | /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and | |
820 | *OVERLAPS_B are initialized to the functions that describe the | |
821 | relation between the elements accessed twice by CHREC_A and | |
822 | CHREC_B. For k >= 0, the following property is verified: | |
823 | ||
824 | CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ | |
825 | ||
826 | static void | |
827 | analyze_ziv_subscript (tree chrec_a, | |
828 | tree chrec_b, | |
829 | tree *overlaps_a, | |
86df10e3 SP |
830 | tree *overlaps_b, |
831 | tree *last_conflicts) | |
56cf8686 SP |
832 | { |
833 | tree difference; | |
834 | ||
835 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
836 | fprintf (dump_file, "(analyze_ziv_subscript \n"); | |
837 | ||
838 | difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b); | |
839 | ||
840 | switch (TREE_CODE (difference)) | |
841 | { | |
842 | case INTEGER_CST: | |
843 | if (integer_zerop (difference)) | |
844 | { | |
845 | /* The difference is equal to zero: the accessed index | |
846 | overlaps for each iteration in the loop. */ | |
847 | *overlaps_a = integer_zero_node; | |
848 | *overlaps_b = integer_zero_node; | |
86df10e3 | 849 | *last_conflicts = chrec_dont_know; |
56cf8686 SP |
850 | } |
851 | else | |
852 | { | |
853 | /* The accesses do not overlap. */ | |
854 | *overlaps_a = chrec_known; | |
86df10e3 SP |
855 | *overlaps_b = chrec_known; |
856 | *last_conflicts = integer_zero_node; | |
56cf8686 SP |
857 | } |
858 | break; | |
859 | ||
860 | default: | |
861 | /* We're not sure whether the indexes overlap. For the moment, | |
862 | conservatively answer "don't know". */ | |
863 | *overlaps_a = chrec_dont_know; | |
86df10e3 SP |
864 | *overlaps_b = chrec_dont_know; |
865 | *last_conflicts = chrec_dont_know; | |
56cf8686 SP |
866 | break; |
867 | } | |
868 | ||
869 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
870 | fprintf (dump_file, ")\n"); | |
871 | } | |
872 | ||
873 | /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a | |
874 | constant, and CHREC_B is an affine function. *OVERLAPS_A and | |
875 | *OVERLAPS_B are initialized to the functions that describe the | |
876 | relation between the elements accessed twice by CHREC_A and | |
877 | CHREC_B. For k >= 0, the following property is verified: | |
878 | ||
879 | CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ | |
880 | ||
881 | static void | |
882 | analyze_siv_subscript_cst_affine (tree chrec_a, | |
883 | tree chrec_b, | |
884 | tree *overlaps_a, | |
86df10e3 SP |
885 | tree *overlaps_b, |
886 | tree *last_conflicts) | |
56cf8686 SP |
887 | { |
888 | bool value0, value1, value2; | |
889 | tree difference = chrec_fold_minus | |
890 | (integer_type_node, CHREC_LEFT (chrec_b), chrec_a); | |
891 | ||
892 | if (!chrec_is_positive (initial_condition (difference), &value0)) | |
893 | { | |
894 | *overlaps_a = chrec_dont_know; | |
895 | *overlaps_b = chrec_dont_know; | |
86df10e3 | 896 | *last_conflicts = chrec_dont_know; |
56cf8686 SP |
897 | return; |
898 | } | |
899 | else | |
900 | { | |
901 | if (value0 == false) | |
902 | { | |
903 | if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1)) | |
904 | { | |
905 | *overlaps_a = chrec_dont_know; | |
906 | *overlaps_b = chrec_dont_know; | |
86df10e3 | 907 | *last_conflicts = chrec_dont_know; |
56cf8686 SP |
908 | return; |
909 | } | |
910 | else | |
911 | { | |
912 | if (value1 == true) | |
913 | { | |
914 | /* Example: | |
915 | chrec_a = 12 | |
916 | chrec_b = {10, +, 1} | |
917 | */ | |
918 | ||
919 | if (tree_fold_divides_p | |
920 | (integer_type_node, CHREC_RIGHT (chrec_b), difference)) | |
921 | { | |
922 | *overlaps_a = integer_zero_node; | |
923 | *overlaps_b = fold | |
924 | (build (EXACT_DIV_EXPR, integer_type_node, | |
925 | fold (build1 (ABS_EXPR, integer_type_node, difference)), | |
926 | CHREC_RIGHT (chrec_b))); | |
86df10e3 | 927 | *last_conflicts = integer_one_node; |
56cf8686 SP |
928 | return; |
929 | } | |
930 | ||
931 | /* When the step does not divides the difference, there are | |
932 | no overlaps. */ | |
933 | else | |
934 | { | |
935 | *overlaps_a = chrec_known; | |
936 | *overlaps_b = chrec_known; | |
86df10e3 | 937 | *last_conflicts = integer_zero_node; |
56cf8686 SP |
938 | return; |
939 | } | |
940 | } | |
941 | ||
942 | else | |
943 | { | |
944 | /* Example: | |
945 | chrec_a = 12 | |
946 | chrec_b = {10, +, -1} | |
947 | ||
948 | In this case, chrec_a will not overlap with chrec_b. */ | |
949 | *overlaps_a = chrec_known; | |
950 | *overlaps_b = chrec_known; | |
86df10e3 | 951 | *last_conflicts = integer_zero_node; |
56cf8686 SP |
952 | return; |
953 | } | |
954 | } | |
955 | } | |
956 | else | |
957 | { | |
958 | if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2)) | |
959 | { | |
960 | *overlaps_a = chrec_dont_know; | |
961 | *overlaps_b = chrec_dont_know; | |
86df10e3 | 962 | *last_conflicts = chrec_dont_know; |
56cf8686 SP |
963 | return; |
964 | } | |
965 | else | |
966 | { | |
967 | if (value2 == false) | |
968 | { | |
969 | /* Example: | |
970 | chrec_a = 3 | |
971 | chrec_b = {10, +, -1} | |
972 | */ | |
973 | if (tree_fold_divides_p | |
974 | (integer_type_node, CHREC_RIGHT (chrec_b), difference)) | |
975 | { | |
976 | *overlaps_a = integer_zero_node; | |
977 | *overlaps_b = fold | |
978 | (build (EXACT_DIV_EXPR, integer_type_node, difference, | |
979 | CHREC_RIGHT (chrec_b))); | |
86df10e3 | 980 | *last_conflicts = integer_one_node; |
56cf8686 SP |
981 | return; |
982 | } | |
983 | ||
984 | /* When the step does not divides the difference, there | |
985 | are no overlaps. */ | |
986 | else | |
987 | { | |
988 | *overlaps_a = chrec_known; | |
989 | *overlaps_b = chrec_known; | |
86df10e3 | 990 | *last_conflicts = integer_zero_node; |
56cf8686 SP |
991 | return; |
992 | } | |
993 | } | |
994 | else | |
995 | { | |
996 | /* Example: | |
997 | chrec_a = 3 | |
998 | chrec_b = {4, +, 1} | |
999 | ||
1000 | In this case, chrec_a will not overlap with chrec_b. */ | |
1001 | *overlaps_a = chrec_known; | |
1002 | *overlaps_b = chrec_known; | |
86df10e3 | 1003 | *last_conflicts = integer_zero_node; |
56cf8686 SP |
1004 | return; |
1005 | } | |
1006 | } | |
1007 | } | |
1008 | } | |
1009 | } | |
1010 | ||
50300b4c | 1011 | /* Helper recursive function for initializing the matrix A. Returns |
86df10e3 | 1012 | the initial value of CHREC. */ |
56cf8686 | 1013 | |
86df10e3 SP |
1014 | static int |
1015 | initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult) | |
1016 | { | |
1017 | gcc_assert (chrec); | |
1018 | ||
1019 | if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) | |
1020 | return int_cst_value (chrec); | |
1021 | ||
1022 | A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec)); | |
1023 | return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult); | |
1024 | } | |
1025 | ||
1026 | #define FLOOR_DIV(x,y) ((x) / (y)) | |
1027 | ||
1028 | /* Solves the special case of the Diophantine equation: | |
1029 | | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B) | |
1030 | ||
1031 | Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the | |
1032 | number of iterations that loops X and Y run. The overlaps will be | |
1033 | constructed as evolutions in dimension DIM. */ | |
56cf8686 SP |
1034 | |
1035 | static void | |
86df10e3 SP |
1036 | compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, |
1037 | tree *overlaps_a, tree *overlaps_b, | |
1038 | tree *last_conflicts, int dim) | |
1039 | { | |
1040 | if (((step_a > 0 && step_b > 0) | |
1041 | || (step_a < 0 && step_b < 0))) | |
1042 | { | |
1043 | int step_overlaps_a, step_overlaps_b; | |
1044 | int gcd_steps_a_b, last_conflict, tau2; | |
1045 | ||
1046 | gcd_steps_a_b = gcd (step_a, step_b); | |
1047 | step_overlaps_a = step_b / gcd_steps_a_b; | |
1048 | step_overlaps_b = step_a / gcd_steps_a_b; | |
1049 | ||
1050 | tau2 = FLOOR_DIV (niter, step_overlaps_a); | |
1051 | tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b)); | |
1052 | last_conflict = tau2; | |
1053 | ||
1054 | *overlaps_a = build_polynomial_chrec | |
1055 | (dim, integer_zero_node, | |
1056 | build_int_cst (NULL_TREE, step_overlaps_a)); | |
1057 | *overlaps_b = build_polynomial_chrec | |
1058 | (dim, integer_zero_node, | |
1059 | build_int_cst (NULL_TREE, step_overlaps_b)); | |
1060 | *last_conflicts = build_int_cst (NULL_TREE, last_conflict); | |
1061 | } | |
1062 | ||
1063 | else | |
1064 | { | |
1065 | *overlaps_a = integer_zero_node; | |
1066 | *overlaps_b = integer_zero_node; | |
1067 | *last_conflicts = integer_zero_node; | |
1068 | } | |
1069 | } | |
1070 | ||
1071 | ||
1072 | /* Solves the special case of a Diophantine equation where CHREC_A is | |
1073 | an affine bivariate function, and CHREC_B is an affine univariate | |
1074 | function. For example, | |
1075 | ||
1076 | | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z | |
1077 | ||
1078 | has the following overlapping functions: | |
1079 | ||
1080 | | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v | |
1081 | | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v | |
1082 | | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v | |
1083 | ||
35fd3193 | 1084 | FORNOW: This is a specialized implementation for a case occurring in |
86df10e3 SP |
1085 | a common benchmark. Implement the general algorithm. */ |
1086 | ||
1087 | static void | |
1088 | compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, | |
1089 | tree *overlaps_a, tree *overlaps_b, | |
1090 | tree *last_conflicts) | |
56cf8686 | 1091 | { |
86df10e3 SP |
1092 | bool xz_p, yz_p, xyz_p; |
1093 | int step_x, step_y, step_z; | |
1094 | int niter_x, niter_y, niter_z, niter; | |
1095 | tree numiter_x, numiter_y, numiter_z; | |
1096 | tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz; | |
1097 | tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz; | |
1098 | tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz; | |
1099 | ||
1100 | step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a))); | |
1101 | step_y = int_cst_value (CHREC_RIGHT (chrec_a)); | |
1102 | step_z = int_cst_value (CHREC_RIGHT (chrec_b)); | |
1103 | ||
1104 | numiter_x = number_of_iterations_in_loop | |
1105 | (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]); | |
1106 | numiter_y = number_of_iterations_in_loop | |
1107 | (current_loops->parray[CHREC_VARIABLE (chrec_a)]); | |
1108 | numiter_z = number_of_iterations_in_loop | |
1109 | (current_loops->parray[CHREC_VARIABLE (chrec_b)]); | |
1110 | ||
1111 | if (TREE_CODE (numiter_x) != INTEGER_CST) | |
1112 | numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))] | |
1113 | ->estimated_nb_iterations; | |
1114 | if (TREE_CODE (numiter_y) != INTEGER_CST) | |
1115 | numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)] | |
1116 | ->estimated_nb_iterations; | |
1117 | if (TREE_CODE (numiter_z) != INTEGER_CST) | |
1118 | numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)] | |
1119 | ->estimated_nb_iterations; | |
1120 | ||
79ebd55c SP |
1121 | if (chrec_contains_undetermined (numiter_x) |
1122 | || chrec_contains_undetermined (numiter_y) | |
1123 | || chrec_contains_undetermined (numiter_z) | |
1124 | || TREE_CODE (numiter_x) != INTEGER_CST | |
1125 | || TREE_CODE (numiter_y) != INTEGER_CST | |
1126 | || TREE_CODE (numiter_z) != INTEGER_CST) | |
86df10e3 SP |
1127 | { |
1128 | *overlaps_a = chrec_dont_know; | |
1129 | *overlaps_b = chrec_dont_know; | |
1130 | *last_conflicts = chrec_dont_know; | |
1131 | return; | |
1132 | } | |
1133 | ||
1134 | niter_x = int_cst_value (numiter_x); | |
1135 | niter_y = int_cst_value (numiter_y); | |
1136 | niter_z = int_cst_value (numiter_z); | |
1137 | ||
1138 | niter = MIN (niter_x, niter_z); | |
1139 | compute_overlap_steps_for_affine_univar (niter, step_x, step_z, | |
1140 | &overlaps_a_xz, | |
1141 | &overlaps_b_xz, | |
1142 | &last_conflicts_xz, 1); | |
1143 | niter = MIN (niter_y, niter_z); | |
1144 | compute_overlap_steps_for_affine_univar (niter, step_y, step_z, | |
1145 | &overlaps_a_yz, | |
1146 | &overlaps_b_yz, | |
1147 | &last_conflicts_yz, 2); | |
1148 | niter = MIN (niter_x, niter_z); | |
1149 | niter = MIN (niter_y, niter); | |
1150 | compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z, | |
1151 | &overlaps_a_xyz, | |
1152 | &overlaps_b_xyz, | |
1153 | &last_conflicts_xyz, 3); | |
1154 | ||
1155 | xz_p = !integer_zerop (last_conflicts_xz); | |
1156 | yz_p = !integer_zerop (last_conflicts_yz); | |
1157 | xyz_p = !integer_zerop (last_conflicts_xyz); | |
1158 | ||
1159 | if (xz_p || yz_p || xyz_p) | |
1160 | { | |
1161 | *overlaps_a = make_tree_vec (2); | |
1162 | TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node; | |
1163 | TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node; | |
1164 | *overlaps_b = integer_zero_node; | |
1165 | if (xz_p) | |
1166 | { | |
1167 | TREE_VEC_ELT (*overlaps_a, 0) = | |
1168 | chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0), | |
1169 | overlaps_a_xz); | |
1170 | *overlaps_b = | |
1171 | chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz); | |
1172 | *last_conflicts = last_conflicts_xz; | |
1173 | } | |
1174 | if (yz_p) | |
1175 | { | |
1176 | TREE_VEC_ELT (*overlaps_a, 1) = | |
1177 | chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1), | |
1178 | overlaps_a_yz); | |
1179 | *overlaps_b = | |
1180 | chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz); | |
1181 | *last_conflicts = last_conflicts_yz; | |
1182 | } | |
1183 | if (xyz_p) | |
1184 | { | |
1185 | TREE_VEC_ELT (*overlaps_a, 0) = | |
1186 | chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0), | |
1187 | overlaps_a_xyz); | |
1188 | TREE_VEC_ELT (*overlaps_a, 1) = | |
1189 | chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1), | |
1190 | overlaps_a_xyz); | |
1191 | *overlaps_b = | |
1192 | chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz); | |
1193 | *last_conflicts = last_conflicts_xyz; | |
1194 | } | |
1195 | } | |
1196 | else | |
1197 | { | |
1198 | *overlaps_a = integer_zero_node; | |
1199 | *overlaps_b = integer_zero_node; | |
1200 | *last_conflicts = integer_zero_node; | |
1201 | } | |
56cf8686 SP |
1202 | } |
1203 | ||
1204 | /* Determines the overlapping elements due to accesses CHREC_A and | |
1205 | CHREC_B, that are affine functions. This is a part of the | |
1206 | subscript analyzer. */ | |
1207 | ||
1208 | static void | |
1209 | analyze_subscript_affine_affine (tree chrec_a, | |
1210 | tree chrec_b, | |
1211 | tree *overlaps_a, | |
86df10e3 SP |
1212 | tree *overlaps_b, |
1213 | tree *last_conflicts) | |
56cf8686 | 1214 | { |
86df10e3 SP |
1215 | unsigned nb_vars_a, nb_vars_b, dim; |
1216 | int init_a, init_b, gamma, gcd_alpha_beta; | |
1217 | int tau1, tau2; | |
1218 | lambda_matrix A, U, S; | |
1219 | ||
56cf8686 SP |
1220 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1221 | fprintf (dump_file, "(analyze_subscript_affine_affine \n"); | |
1222 | ||
1223 | /* For determining the initial intersection, we have to solve a | |
1224 | Diophantine equation. This is the most time consuming part. | |
1225 | ||
1226 | For answering to the question: "Is there a dependence?" we have | |
1227 | to prove that there exists a solution to the Diophantine | |
1228 | equation, and that the solution is in the iteration domain, | |
89dbed81 | 1229 | i.e. the solution is positive or zero, and that the solution |
56cf8686 SP |
1230 | happens before the upper bound loop.nb_iterations. Otherwise |
1231 | there is no dependence. This function outputs a description of | |
1232 | the iterations that hold the intersections. */ | |
1233 | ||
56cf8686 | 1234 | |
86df10e3 SP |
1235 | nb_vars_a = nb_vars_in_chrec (chrec_a); |
1236 | nb_vars_b = nb_vars_in_chrec (chrec_b); | |
1237 | ||
1238 | dim = nb_vars_a + nb_vars_b; | |
1239 | U = lambda_matrix_new (dim, dim); | |
1240 | A = lambda_matrix_new (dim, 1); | |
1241 | S = lambda_matrix_new (dim, 1); | |
1242 | ||
1243 | init_a = initialize_matrix_A (A, chrec_a, 0, 1); | |
1244 | init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1); | |
1245 | gamma = init_b - init_a; | |
1246 | ||
1247 | /* Don't do all the hard work of solving the Diophantine equation | |
1248 | when we already know the solution: for example, | |
1249 | | {3, +, 1}_1 | |
1250 | | {3, +, 4}_2 | |
1251 | | gamma = 3 - 3 = 0. | |
1252 | Then the first overlap occurs during the first iterations: | |
1253 | | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x) | |
1254 | */ | |
1255 | if (gamma == 0) | |
56cf8686 | 1256 | { |
86df10e3 | 1257 | if (nb_vars_a == 1 && nb_vars_b == 1) |
56cf8686 | 1258 | { |
86df10e3 SP |
1259 | int step_a, step_b; |
1260 | int niter, niter_a, niter_b; | |
1261 | tree numiter_a, numiter_b; | |
1262 | ||
1263 | numiter_a = number_of_iterations_in_loop | |
1264 | (current_loops->parray[CHREC_VARIABLE (chrec_a)]); | |
1265 | numiter_b = number_of_iterations_in_loop | |
1266 | (current_loops->parray[CHREC_VARIABLE (chrec_b)]); | |
1267 | ||
1268 | if (TREE_CODE (numiter_a) != INTEGER_CST) | |
1269 | numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)] | |
1270 | ->estimated_nb_iterations; | |
1271 | if (TREE_CODE (numiter_b) != INTEGER_CST) | |
1272 | numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)] | |
1273 | ->estimated_nb_iterations; | |
79ebd55c SP |
1274 | if (chrec_contains_undetermined (numiter_a) |
1275 | || chrec_contains_undetermined (numiter_b) | |
1276 | || TREE_CODE (numiter_a) != INTEGER_CST | |
1277 | || TREE_CODE (numiter_b) != INTEGER_CST) | |
86df10e3 SP |
1278 | { |
1279 | *overlaps_a = chrec_dont_know; | |
1280 | *overlaps_b = chrec_dont_know; | |
1281 | *last_conflicts = chrec_dont_know; | |
1282 | return; | |
1283 | } | |
1284 | ||
1285 | niter_a = int_cst_value (numiter_a); | |
1286 | niter_b = int_cst_value (numiter_b); | |
1287 | niter = MIN (niter_a, niter_b); | |
1288 | ||
1289 | step_a = int_cst_value (CHREC_RIGHT (chrec_a)); | |
1290 | step_b = int_cst_value (CHREC_RIGHT (chrec_b)); | |
1291 | ||
1292 | compute_overlap_steps_for_affine_univar (niter, step_a, step_b, | |
1293 | overlaps_a, overlaps_b, | |
1294 | last_conflicts, 1); | |
56cf8686 | 1295 | } |
86df10e3 SP |
1296 | |
1297 | else if (nb_vars_a == 2 && nb_vars_b == 1) | |
1298 | compute_overlap_steps_for_affine_1_2 | |
1299 | (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts); | |
1300 | ||
1301 | else if (nb_vars_a == 1 && nb_vars_b == 2) | |
1302 | compute_overlap_steps_for_affine_1_2 | |
1303 | (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts); | |
1304 | ||
1305 | else | |
56cf8686 | 1306 | { |
86df10e3 SP |
1307 | *overlaps_a = chrec_dont_know; |
1308 | *overlaps_b = chrec_dont_know; | |
1309 | *last_conflicts = chrec_dont_know; | |
56cf8686 | 1310 | } |
86df10e3 SP |
1311 | return; |
1312 | } | |
1313 | ||
1314 | /* U.A = S */ | |
1315 | lambda_matrix_right_hermite (A, dim, 1, S, U); | |
1316 | ||
1317 | if (S[0][0] < 0) | |
1318 | { | |
1319 | S[0][0] *= -1; | |
1320 | lambda_matrix_row_negate (U, dim, 0); | |
1321 | } | |
1322 | gcd_alpha_beta = S[0][0]; | |
1323 | ||
1324 | /* The classic "gcd-test". */ | |
1325 | if (!int_divides_p (gcd_alpha_beta, gamma)) | |
1326 | { | |
1327 | /* The "gcd-test" has determined that there is no integer | |
1328 | solution, i.e. there is no dependence. */ | |
1329 | *overlaps_a = chrec_known; | |
1330 | *overlaps_b = chrec_known; | |
1331 | *last_conflicts = integer_zero_node; | |
1332 | } | |
1333 | ||
1334 | /* Both access functions are univariate. This includes SIV and MIV cases. */ | |
1335 | else if (nb_vars_a == 1 && nb_vars_b == 1) | |
1336 | { | |
1337 | /* Both functions should have the same evolution sign. */ | |
1338 | if (((A[0][0] > 0 && -A[1][0] > 0) | |
1339 | || (A[0][0] < 0 && -A[1][0] < 0))) | |
56cf8686 SP |
1340 | { |
1341 | /* The solutions are given by: | |
1342 | | | |
86df10e3 SP |
1343 | | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0] |
1344 | | [u21 u22] [y0] | |
1345 | ||
56cf8686 | 1346 | For a given integer t. Using the following variables, |
86df10e3 | 1347 | |
56cf8686 SP |
1348 | | i0 = u11 * gamma / gcd_alpha_beta |
1349 | | j0 = u12 * gamma / gcd_alpha_beta | |
1350 | | i1 = u21 | |
1351 | | j1 = u22 | |
86df10e3 | 1352 | |
56cf8686 | 1353 | the solutions are: |
86df10e3 SP |
1354 | |
1355 | | x0 = i0 + i1 * t, | |
1356 | | y0 = j0 + j1 * t. */ | |
1357 | ||
1358 | int i0, j0, i1, j1; | |
1359 | ||
56cf8686 SP |
1360 | /* X0 and Y0 are the first iterations for which there is a |
1361 | dependence. X0, Y0 are two solutions of the Diophantine | |
1362 | equation: chrec_a (X0) = chrec_b (Y0). */ | |
86df10e3 SP |
1363 | int x0, y0; |
1364 | int niter, niter_a, niter_b; | |
1365 | tree numiter_a, numiter_b; | |
1366 | ||
1367 | numiter_a = number_of_iterations_in_loop | |
1368 | (current_loops->parray[CHREC_VARIABLE (chrec_a)]); | |
1369 | numiter_b = number_of_iterations_in_loop | |
1370 | (current_loops->parray[CHREC_VARIABLE (chrec_b)]); | |
1371 | ||
1372 | if (TREE_CODE (numiter_a) != INTEGER_CST) | |
1373 | numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)] | |
1374 | ->estimated_nb_iterations; | |
1375 | if (TREE_CODE (numiter_b) != INTEGER_CST) | |
1376 | numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)] | |
1377 | ->estimated_nb_iterations; | |
79ebd55c SP |
1378 | if (chrec_contains_undetermined (numiter_a) |
1379 | || chrec_contains_undetermined (numiter_b) | |
1380 | || TREE_CODE (numiter_a) != INTEGER_CST | |
1381 | || TREE_CODE (numiter_b) != INTEGER_CST) | |
86df10e3 SP |
1382 | { |
1383 | *overlaps_a = chrec_dont_know; | |
1384 | *overlaps_b = chrec_dont_know; | |
1385 | *last_conflicts = chrec_dont_know; | |
1386 | return; | |
1387 | } | |
1388 | ||
1389 | niter_a = int_cst_value (numiter_a); | |
1390 | niter_b = int_cst_value (numiter_b); | |
1391 | niter = MIN (niter_a, niter_b); | |
1392 | ||
1393 | i0 = U[0][0] * gamma / gcd_alpha_beta; | |
1394 | j0 = U[0][1] * gamma / gcd_alpha_beta; | |
1395 | i1 = U[1][0]; | |
1396 | j1 = U[1][1]; | |
1397 | ||
1398 | if ((i1 == 0 && i0 < 0) | |
1399 | || (j1 == 0 && j0 < 0)) | |
56cf8686 SP |
1400 | { |
1401 | /* There is no solution. | |
1402 | FIXME: The case "i0 > nb_iterations, j0 > nb_iterations" | |
1403 | falls in here, but for the moment we don't look at the | |
1404 | upper bound of the iteration domain. */ | |
1405 | *overlaps_a = chrec_known; | |
1406 | *overlaps_b = chrec_known; | |
86df10e3 SP |
1407 | *last_conflicts = integer_zero_node; |
1408 | } | |
1409 | ||
56cf8686 SP |
1410 | else |
1411 | { | |
86df10e3 | 1412 | if (i1 > 0) |
56cf8686 | 1413 | { |
86df10e3 SP |
1414 | tau1 = CEIL (-i0, i1); |
1415 | tau2 = FLOOR_DIV (niter - i0, i1); | |
1416 | ||
1417 | if (j1 > 0) | |
56cf8686 | 1418 | { |
9ba64a4a | 1419 | int last_conflict, min_multiple; |
86df10e3 SP |
1420 | tau1 = MAX (tau1, CEIL (-j0, j1)); |
1421 | tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1)); | |
1422 | ||
9ba64a4a SP |
1423 | x0 = i1 * tau1 + i0; |
1424 | y0 = j1 * tau1 + j0; | |
1425 | ||
1426 | /* At this point (x0, y0) is one of the | |
1427 | solutions to the Diophantine equation. The | |
1428 | next step has to compute the smallest | |
1429 | positive solution: the first conflicts. */ | |
1430 | min_multiple = MIN (x0 / i1, y0 / j1); | |
1431 | x0 -= i1 * min_multiple; | |
1432 | y0 -= j1 * min_multiple; | |
1433 | ||
86df10e3 SP |
1434 | tau1 = (x0 - i0)/i1; |
1435 | last_conflict = tau2 - tau1; | |
1436 | ||
1437 | *overlaps_a = build_polynomial_chrec | |
1438 | (1, | |
1439 | build_int_cst (NULL_TREE, x0), | |
1440 | build_int_cst (NULL_TREE, i1)); | |
1441 | *overlaps_b = build_polynomial_chrec | |
1442 | (1, | |
1443 | build_int_cst (NULL_TREE, y0), | |
1444 | build_int_cst (NULL_TREE, j1)); | |
1445 | *last_conflicts = build_int_cst (NULL_TREE, last_conflict); | |
56cf8686 SP |
1446 | } |
1447 | else | |
1448 | { | |
1449 | /* FIXME: For the moment, the upper bound of the | |
471854f8 | 1450 | iteration domain for j is not checked. */ |
56cf8686 SP |
1451 | *overlaps_a = chrec_dont_know; |
1452 | *overlaps_b = chrec_dont_know; | |
86df10e3 | 1453 | *last_conflicts = chrec_dont_know; |
56cf8686 SP |
1454 | } |
1455 | } | |
86df10e3 | 1456 | |
56cf8686 SP |
1457 | else |
1458 | { | |
1459 | /* FIXME: For the moment, the upper bound of the | |
471854f8 | 1460 | iteration domain for i is not checked. */ |
56cf8686 SP |
1461 | *overlaps_a = chrec_dont_know; |
1462 | *overlaps_b = chrec_dont_know; | |
86df10e3 | 1463 | *last_conflicts = chrec_dont_know; |
56cf8686 SP |
1464 | } |
1465 | } | |
1466 | } | |
86df10e3 SP |
1467 | else |
1468 | { | |
1469 | *overlaps_a = chrec_dont_know; | |
1470 | *overlaps_b = chrec_dont_know; | |
1471 | *last_conflicts = chrec_dont_know; | |
1472 | } | |
56cf8686 | 1473 | } |
86df10e3 | 1474 | |
56cf8686 SP |
1475 | else |
1476 | { | |
56cf8686 SP |
1477 | *overlaps_a = chrec_dont_know; |
1478 | *overlaps_b = chrec_dont_know; | |
86df10e3 | 1479 | *last_conflicts = chrec_dont_know; |
56cf8686 | 1480 | } |
86df10e3 SP |
1481 | |
1482 | ||
56cf8686 SP |
1483 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1484 | { | |
1485 | fprintf (dump_file, " (overlaps_a = "); | |
1486 | print_generic_expr (dump_file, *overlaps_a, 0); | |
1487 | fprintf (dump_file, ")\n (overlaps_b = "); | |
1488 | print_generic_expr (dump_file, *overlaps_b, 0); | |
1489 | fprintf (dump_file, ")\n"); | |
1490 | } | |
1491 | ||
1492 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1493 | fprintf (dump_file, ")\n"); | |
1494 | } | |
1495 | ||
1496 | /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and | |
1497 | *OVERLAPS_B are initialized to the functions that describe the | |
1498 | relation between the elements accessed twice by CHREC_A and | |
1499 | CHREC_B. For k >= 0, the following property is verified: | |
1500 | ||
1501 | CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ | |
1502 | ||
1503 | static void | |
1504 | analyze_siv_subscript (tree chrec_a, | |
1505 | tree chrec_b, | |
1506 | tree *overlaps_a, | |
86df10e3 SP |
1507 | tree *overlaps_b, |
1508 | tree *last_conflicts) | |
56cf8686 SP |
1509 | { |
1510 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1511 | fprintf (dump_file, "(analyze_siv_subscript \n"); | |
1512 | ||
1513 | if (evolution_function_is_constant_p (chrec_a) | |
1514 | && evolution_function_is_affine_p (chrec_b)) | |
1515 | analyze_siv_subscript_cst_affine (chrec_a, chrec_b, | |
86df10e3 | 1516 | overlaps_a, overlaps_b, last_conflicts); |
56cf8686 SP |
1517 | |
1518 | else if (evolution_function_is_affine_p (chrec_a) | |
1519 | && evolution_function_is_constant_p (chrec_b)) | |
86df10e3 SP |
1520 | analyze_siv_subscript_cst_affine (chrec_b, chrec_a, |
1521 | overlaps_b, overlaps_a, last_conflicts); | |
56cf8686 SP |
1522 | |
1523 | else if (evolution_function_is_affine_p (chrec_a) | |
86df10e3 | 1524 | && evolution_function_is_affine_p (chrec_b)) |
56cf8686 | 1525 | analyze_subscript_affine_affine (chrec_a, chrec_b, |
86df10e3 | 1526 | overlaps_a, overlaps_b, last_conflicts); |
56cf8686 SP |
1527 | else |
1528 | { | |
1529 | *overlaps_a = chrec_dont_know; | |
1530 | *overlaps_b = chrec_dont_know; | |
86df10e3 | 1531 | *last_conflicts = chrec_dont_know; |
56cf8686 SP |
1532 | } |
1533 | ||
1534 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1535 | fprintf (dump_file, ")\n"); | |
1536 | } | |
1537 | ||
1538 | /* Return true when the evolution steps of an affine CHREC divide the | |
1539 | constant CST. */ | |
1540 | ||
1541 | static bool | |
1542 | chrec_steps_divide_constant_p (tree chrec, | |
1543 | tree cst) | |
1544 | { | |
1545 | switch (TREE_CODE (chrec)) | |
1546 | { | |
1547 | case POLYNOMIAL_CHREC: | |
1548 | return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst) | |
1549 | && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst)); | |
1550 | ||
1551 | default: | |
1552 | /* On the initial condition, return true. */ | |
1553 | return true; | |
1554 | } | |
1555 | } | |
1556 | ||
1557 | /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and | |
1558 | *OVERLAPS_B are initialized to the functions that describe the | |
1559 | relation between the elements accessed twice by CHREC_A and | |
1560 | CHREC_B. For k >= 0, the following property is verified: | |
1561 | ||
1562 | CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ | |
1563 | ||
1564 | static void | |
1565 | analyze_miv_subscript (tree chrec_a, | |
1566 | tree chrec_b, | |
1567 | tree *overlaps_a, | |
86df10e3 SP |
1568 | tree *overlaps_b, |
1569 | tree *last_conflicts) | |
56cf8686 SP |
1570 | { |
1571 | /* FIXME: This is a MIV subscript, not yet handled. | |
1572 | Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from | |
1573 | (A[i] vs. A[j]). | |
1574 | ||
1575 | In the SIV test we had to solve a Diophantine equation with two | |
1576 | variables. In the MIV case we have to solve a Diophantine | |
1577 | equation with 2*n variables (if the subscript uses n IVs). | |
1578 | */ | |
1579 | tree difference; | |
1580 | ||
1581 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1582 | fprintf (dump_file, "(analyze_miv_subscript \n"); | |
1583 | ||
1584 | difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b); | |
1585 | ||
1586 | if (chrec_zerop (difference)) | |
1587 | { | |
1588 | /* Access functions are the same: all the elements are accessed | |
1589 | in the same order. */ | |
1590 | *overlaps_a = integer_zero_node; | |
1591 | *overlaps_b = integer_zero_node; | |
86df10e3 SP |
1592 | *last_conflicts = number_of_iterations_in_loop |
1593 | (current_loops->parray[CHREC_VARIABLE (chrec_a)]); | |
56cf8686 SP |
1594 | } |
1595 | ||
1596 | else if (evolution_function_is_constant_p (difference) | |
1597 | /* For the moment, the following is verified: | |
1598 | evolution_function_is_affine_multivariate_p (chrec_a) */ | |
1599 | && !chrec_steps_divide_constant_p (chrec_a, difference)) | |
1600 | { | |
1601 | /* testsuite/.../ssa-chrec-33.c | |
1602 | {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2 | |
1603 | ||
1604 | The difference is 1, and the evolution steps are equal to 2, | |
1605 | consequently there are no overlapping elements. */ | |
1606 | *overlaps_a = chrec_known; | |
1607 | *overlaps_b = chrec_known; | |
86df10e3 | 1608 | *last_conflicts = integer_zero_node; |
56cf8686 SP |
1609 | } |
1610 | ||
86df10e3 SP |
1611 | else if (evolution_function_is_affine_multivariate_p (chrec_a) |
1612 | && evolution_function_is_affine_multivariate_p (chrec_b)) | |
56cf8686 SP |
1613 | { |
1614 | /* testsuite/.../ssa-chrec-35.c | |
1615 | {0, +, 1}_2 vs. {0, +, 1}_3 | |
1616 | the overlapping elements are respectively located at iterations: | |
86df10e3 SP |
1617 | {0, +, 1}_x and {0, +, 1}_x, |
1618 | in other words, we have the equality: | |
1619 | {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x) | |
1620 | ||
1621 | Other examples: | |
1622 | {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) = | |
1623 | {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y) | |
1624 | ||
1625 | {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) = | |
1626 | {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) | |
56cf8686 | 1627 | */ |
86df10e3 SP |
1628 | analyze_subscript_affine_affine (chrec_a, chrec_b, |
1629 | overlaps_a, overlaps_b, last_conflicts); | |
56cf8686 SP |
1630 | } |
1631 | ||
1632 | else | |
1633 | { | |
1634 | /* When the analysis is too difficult, answer "don't know". */ | |
1635 | *overlaps_a = chrec_dont_know; | |
1636 | *overlaps_b = chrec_dont_know; | |
86df10e3 | 1637 | *last_conflicts = chrec_dont_know; |
56cf8686 SP |
1638 | } |
1639 | ||
1640 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1641 | fprintf (dump_file, ")\n"); | |
1642 | } | |
1643 | ||
1644 | /* Determines the iterations for which CHREC_A is equal to CHREC_B. | |
1645 | OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with | |
1646 | two functions that describe the iterations that contain conflicting | |
1647 | elements. | |
1648 | ||
1649 | Remark: For an integer k >= 0, the following equality is true: | |
1650 | ||
1651 | CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)). | |
1652 | */ | |
1653 | ||
1654 | static void | |
1655 | analyze_overlapping_iterations (tree chrec_a, | |
1656 | tree chrec_b, | |
1657 | tree *overlap_iterations_a, | |
86df10e3 SP |
1658 | tree *overlap_iterations_b, |
1659 | tree *last_conflicts) | |
56cf8686 SP |
1660 | { |
1661 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1662 | { | |
1663 | fprintf (dump_file, "(analyze_overlapping_iterations \n"); | |
1664 | fprintf (dump_file, " (chrec_a = "); | |
1665 | print_generic_expr (dump_file, chrec_a, 0); | |
1666 | fprintf (dump_file, ")\n chrec_b = "); | |
1667 | print_generic_expr (dump_file, chrec_b, 0); | |
1668 | fprintf (dump_file, ")\n"); | |
1669 | } | |
1670 | ||
1671 | if (chrec_a == NULL_TREE | |
1672 | || chrec_b == NULL_TREE | |
1673 | || chrec_contains_undetermined (chrec_a) | |
1674 | || chrec_contains_undetermined (chrec_b) | |
1675 | || chrec_contains_symbols (chrec_a) | |
1676 | || chrec_contains_symbols (chrec_b)) | |
1677 | { | |
1678 | *overlap_iterations_a = chrec_dont_know; | |
1679 | *overlap_iterations_b = chrec_dont_know; | |
1680 | } | |
1681 | ||
1682 | else if (ziv_subscript_p (chrec_a, chrec_b)) | |
1683 | analyze_ziv_subscript (chrec_a, chrec_b, | |
86df10e3 SP |
1684 | overlap_iterations_a, overlap_iterations_b, |
1685 | last_conflicts); | |
56cf8686 SP |
1686 | |
1687 | else if (siv_subscript_p (chrec_a, chrec_b)) | |
1688 | analyze_siv_subscript (chrec_a, chrec_b, | |
86df10e3 SP |
1689 | overlap_iterations_a, overlap_iterations_b, |
1690 | last_conflicts); | |
56cf8686 SP |
1691 | |
1692 | else | |
1693 | analyze_miv_subscript (chrec_a, chrec_b, | |
86df10e3 SP |
1694 | overlap_iterations_a, overlap_iterations_b, |
1695 | last_conflicts); | |
56cf8686 SP |
1696 | |
1697 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1698 | { | |
1699 | fprintf (dump_file, " (overlap_iterations_a = "); | |
1700 | print_generic_expr (dump_file, *overlap_iterations_a, 0); | |
1701 | fprintf (dump_file, ")\n (overlap_iterations_b = "); | |
1702 | print_generic_expr (dump_file, *overlap_iterations_b, 0); | |
1703 | fprintf (dump_file, ")\n"); | |
1704 | } | |
1705 | } | |
1706 | ||
1707 | \f | |
1708 | ||
1709 | /* This section contains the affine functions dependences detector. */ | |
1710 | ||
1711 | /* Computes the conflicting iterations, and initialize DDR. */ | |
1712 | ||
1713 | static void | |
1714 | subscript_dependence_tester (struct data_dependence_relation *ddr) | |
1715 | { | |
1716 | unsigned int i; | |
1717 | struct data_reference *dra = DDR_A (ddr); | |
1718 | struct data_reference *drb = DDR_B (ddr); | |
86df10e3 | 1719 | tree last_conflicts; |
56cf8686 SP |
1720 | |
1721 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1722 | fprintf (dump_file, "(subscript_dependence_tester \n"); | |
1723 | ||
1724 | for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) | |
1725 | { | |
1726 | tree overlaps_a, overlaps_b; | |
1727 | struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); | |
1728 | ||
1729 | analyze_overlapping_iterations (DR_ACCESS_FN (dra, i), | |
1730 | DR_ACCESS_FN (drb, i), | |
86df10e3 SP |
1731 | &overlaps_a, &overlaps_b, |
1732 | &last_conflicts); | |
56cf8686 SP |
1733 | |
1734 | if (chrec_contains_undetermined (overlaps_a) | |
1735 | || chrec_contains_undetermined (overlaps_b)) | |
1736 | { | |
1737 | finalize_ddr_dependent (ddr, chrec_dont_know); | |
1738 | break; | |
1739 | } | |
1740 | ||
1741 | else if (overlaps_a == chrec_known | |
1742 | || overlaps_b == chrec_known) | |
1743 | { | |
1744 | finalize_ddr_dependent (ddr, chrec_known); | |
1745 | break; | |
1746 | } | |
1747 | ||
1748 | else | |
1749 | { | |
1750 | SUB_CONFLICTS_IN_A (subscript) = overlaps_a; | |
1751 | SUB_CONFLICTS_IN_B (subscript) = overlaps_b; | |
86df10e3 | 1752 | SUB_LAST_CONFLICT (subscript) = last_conflicts; |
56cf8686 SP |
1753 | } |
1754 | } | |
1755 | ||
1756 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1757 | fprintf (dump_file, ")\n"); | |
1758 | } | |
1759 | ||
1760 | /* Compute the classic per loop distance vector. | |
1761 | ||
36d59cf7 | 1762 | DDR is the data dependence relation to build a vector from. |
56cf8686 | 1763 | NB_LOOPS is the total number of loops we are considering. |
1f24dd47 | 1764 | FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed |
464f49d8 DB |
1765 | loop nest. |
1766 | Return FALSE if the dependence relation is outside of the loop nest | |
1f24dd47 | 1767 | starting at FIRST_LOOP_DEPTH. |
464f49d8 | 1768 | Return TRUE otherwise. */ |
56cf8686 | 1769 | |
b52485c6 | 1770 | bool |
36d59cf7 | 1771 | build_classic_dist_vector (struct data_dependence_relation *ddr, |
1f24dd47 | 1772 | int nb_loops, int first_loop_depth) |
56cf8686 SP |
1773 | { |
1774 | unsigned i; | |
1775 | lambda_vector dist_v, init_v; | |
1776 | ||
1777 | dist_v = lambda_vector_new (nb_loops); | |
1778 | init_v = lambda_vector_new (nb_loops); | |
1779 | lambda_vector_clear (dist_v, nb_loops); | |
1780 | lambda_vector_clear (init_v, nb_loops); | |
1781 | ||
36d59cf7 | 1782 | if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE) |
464f49d8 | 1783 | return true; |
56cf8686 | 1784 | |
36d59cf7 | 1785 | for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) |
56cf8686 | 1786 | { |
86df10e3 | 1787 | tree access_fn_a, access_fn_b; |
36d59cf7 | 1788 | struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); |
56cf8686 SP |
1789 | |
1790 | if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) | |
86df10e3 SP |
1791 | { |
1792 | non_affine_dependence_relation (ddr); | |
464f49d8 | 1793 | return true; |
86df10e3 SP |
1794 | } |
1795 | ||
1796 | access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i); | |
1797 | access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i); | |
56cf8686 | 1798 | |
86df10e3 SP |
1799 | if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC |
1800 | && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC) | |
56cf8686 | 1801 | { |
1f24dd47 | 1802 | int dist, loop_nb, loop_depth; |
86df10e3 SP |
1803 | int loop_nb_a = CHREC_VARIABLE (access_fn_a); |
1804 | int loop_nb_b = CHREC_VARIABLE (access_fn_b); | |
1805 | struct loop *loop_a = current_loops->parray[loop_nb_a]; | |
1806 | struct loop *loop_b = current_loops->parray[loop_nb_b]; | |
464f49d8 | 1807 | |
8b41b1b2 DB |
1808 | /* If the loop for either variable is at a lower depth than |
1809 | the first_loop's depth, then we can't possibly have a | |
464f49d8 DB |
1810 | dependency at this level of the loop. */ |
1811 | ||
1f24dd47 DB |
1812 | if (loop_a->depth < first_loop_depth |
1813 | || loop_b->depth < first_loop_depth) | |
464f49d8 | 1814 | return false; |
86df10e3 SP |
1815 | |
1816 | if (loop_nb_a != loop_nb_b | |
1817 | && !flow_loop_nested_p (loop_a, loop_b) | |
1818 | && !flow_loop_nested_p (loop_b, loop_a)) | |
1819 | { | |
1820 | /* Example: when there are two consecutive loops, | |
1821 | ||
1822 | | loop_1 | |
1823 | | A[{0, +, 1}_1] | |
1824 | | endloop_1 | |
1825 | | loop_2 | |
1826 | | A[{0, +, 1}_2] | |
1827 | | endloop_2 | |
1828 | ||
1829 | the dependence relation cannot be captured by the | |
1830 | distance abstraction. */ | |
1831 | non_affine_dependence_relation (ddr); | |
464f49d8 | 1832 | return true; |
86df10e3 SP |
1833 | } |
1834 | ||
1835 | /* The dependence is carried by the outermost loop. Example: | |
1836 | | loop_1 | |
1837 | | A[{4, +, 1}_1] | |
1838 | | loop_2 | |
1839 | | A[{5, +, 1}_2] | |
1840 | | endloop_2 | |
1841 | | endloop_1 | |
1842 | In this case, the dependence is carried by loop_1. */ | |
1843 | loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b; | |
1f24dd47 | 1844 | loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth; |
86df10e3 | 1845 | |
56cf8686 SP |
1846 | /* If the loop number is still greater than the number of |
1847 | loops we've been asked to analyze, or negative, | |
1848 | something is borked. */ | |
1f24dd47 DB |
1849 | gcc_assert (loop_depth >= 0); |
1850 | gcc_assert (loop_depth < nb_loops); | |
86df10e3 SP |
1851 | if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) |
1852 | { | |
1853 | non_affine_dependence_relation (ddr); | |
464f49d8 | 1854 | return true; |
86df10e3 SP |
1855 | } |
1856 | ||
56cf8686 SP |
1857 | dist = int_cst_value (SUB_DISTANCE (subscript)); |
1858 | ||
1859 | /* This is the subscript coupling test. | |
1860 | | loop i = 0, N, 1 | |
1861 | | T[i+1][i] = ... | |
1862 | | ... = T[i][i] | |
1863 | | endloop | |
1864 | There is no dependence. */ | |
1f24dd47 DB |
1865 | if (init_v[loop_depth] != 0 |
1866 | && dist_v[loop_depth] != dist) | |
56cf8686 | 1867 | { |
36d59cf7 | 1868 | finalize_ddr_dependent (ddr, chrec_known); |
464f49d8 | 1869 | return true; |
56cf8686 SP |
1870 | } |
1871 | ||
1f24dd47 DB |
1872 | dist_v[loop_depth] = dist; |
1873 | init_v[loop_depth] = 1; | |
56cf8686 SP |
1874 | } |
1875 | } | |
1876 | ||
1877 | /* There is a distance of 1 on all the outer loops: | |
1878 | ||
1879 | Example: there is a dependence of distance 1 on loop_1 for the array A. | |
1880 | | loop_1 | |
1881 | | A[5] = ... | |
1882 | | endloop | |
1883 | */ | |
1884 | { | |
1885 | struct loop *lca, *loop_a, *loop_b; | |
36d59cf7 DB |
1886 | struct data_reference *a = DDR_A (ddr); |
1887 | struct data_reference *b = DDR_B (ddr); | |
1f24dd47 | 1888 | int lca_depth; |
56cf8686 SP |
1889 | loop_a = loop_containing_stmt (DR_STMT (a)); |
1890 | loop_b = loop_containing_stmt (DR_STMT (b)); | |
1891 | ||
1892 | /* Get the common ancestor loop. */ | |
1893 | lca = find_common_loop (loop_a, loop_b); | |
1894 | ||
1f24dd47 DB |
1895 | lca_depth = lca->depth; |
1896 | lca_depth -= first_loop_depth; | |
1897 | gcc_assert (lca_depth >= 0); | |
1898 | gcc_assert (lca_depth < nb_loops); | |
86df10e3 | 1899 | |
56cf8686 SP |
1900 | /* For each outer loop where init_v is not set, the accesses are |
1901 | in dependence of distance 1 in the loop. */ | |
1902 | if (lca != loop_a | |
1903 | && lca != loop_b | |
1f24dd47 DB |
1904 | && init_v[lca_depth] == 0) |
1905 | dist_v[lca_depth] = 1; | |
56cf8686 SP |
1906 | |
1907 | lca = lca->outer; | |
1908 | ||
1909 | if (lca) | |
1910 | { | |
1f24dd47 | 1911 | lca_depth = lca->depth - first_loop_depth; |
56cf8686 SP |
1912 | while (lca->depth != 0) |
1913 | { | |
86df10e3 SP |
1914 | /* If we're considering just a sub-nest, then don't record |
1915 | any information on the outer loops. */ | |
1f24dd47 | 1916 | if (lca_depth < 0) |
86df10e3 SP |
1917 | break; |
1918 | ||
1f24dd47 | 1919 | gcc_assert (lca_depth < nb_loops); |
86df10e3 | 1920 | |
1f24dd47 DB |
1921 | if (init_v[lca_depth] == 0) |
1922 | dist_v[lca_depth] = 1; | |
56cf8686 | 1923 | lca = lca->outer; |
1f24dd47 | 1924 | lca_depth = lca->depth - first_loop_depth; |
56cf8686 SP |
1925 | |
1926 | } | |
1927 | } | |
1928 | } | |
1929 | ||
36d59cf7 | 1930 | DDR_DIST_VECT (ddr) = dist_v; |
86df10e3 | 1931 | DDR_SIZE_VECT (ddr) = nb_loops; |
464f49d8 | 1932 | return true; |
56cf8686 SP |
1933 | } |
1934 | ||
1935 | /* Compute the classic per loop direction vector. | |
1936 | ||
36d59cf7 | 1937 | DDR is the data dependence relation to build a vector from. |
56cf8686 | 1938 | NB_LOOPS is the total number of loops we are considering. |
1f24dd47 | 1939 | FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed |
464f49d8 DB |
1940 | loop nest. |
1941 | Return FALSE if the dependence relation is outside of the loop nest | |
1f24dd47 | 1942 | at FIRST_LOOP_DEPTH. |
464f49d8 | 1943 | Return TRUE otherwise. */ |
56cf8686 | 1944 | |
464f49d8 | 1945 | static bool |
36d59cf7 | 1946 | build_classic_dir_vector (struct data_dependence_relation *ddr, |
1f24dd47 | 1947 | int nb_loops, int first_loop_depth) |
56cf8686 SP |
1948 | { |
1949 | unsigned i; | |
1950 | lambda_vector dir_v, init_v; | |
1951 | ||
1952 | dir_v = lambda_vector_new (nb_loops); | |
1953 | init_v = lambda_vector_new (nb_loops); | |
1954 | lambda_vector_clear (dir_v, nb_loops); | |
1955 | lambda_vector_clear (init_v, nb_loops); | |
1956 | ||
36d59cf7 | 1957 | if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE) |
464f49d8 | 1958 | return true; |
56cf8686 | 1959 | |
36d59cf7 | 1960 | for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) |
56cf8686 | 1961 | { |
86df10e3 | 1962 | tree access_fn_a, access_fn_b; |
36d59cf7 | 1963 | struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); |
56cf8686 | 1964 | |
86df10e3 | 1965 | if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) |
56cf8686 | 1966 | { |
86df10e3 | 1967 | non_affine_dependence_relation (ddr); |
464f49d8 | 1968 | return true; |
86df10e3 SP |
1969 | } |
1970 | ||
1971 | access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i); | |
1972 | access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i); | |
1973 | if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC | |
1974 | && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC) | |
1975 | { | |
1f24dd47 | 1976 | int dist, loop_nb, loop_depth; |
56cf8686 | 1977 | enum data_dependence_direction dir = dir_star; |
86df10e3 SP |
1978 | int loop_nb_a = CHREC_VARIABLE (access_fn_a); |
1979 | int loop_nb_b = CHREC_VARIABLE (access_fn_b); | |
1980 | struct loop *loop_a = current_loops->parray[loop_nb_a]; | |
1981 | struct loop *loop_b = current_loops->parray[loop_nb_b]; | |
464f49d8 | 1982 | |
8b41b1b2 DB |
1983 | /* If the loop for either variable is at a lower depth than |
1984 | the first_loop's depth, then we can't possibly have a | |
1985 | dependency at this level of the loop. */ | |
464f49d8 | 1986 | |
1f24dd47 DB |
1987 | if (loop_a->depth < first_loop_depth |
1988 | || loop_b->depth < first_loop_depth) | |
464f49d8 | 1989 | return false; |
86df10e3 SP |
1990 | |
1991 | if (loop_nb_a != loop_nb_b | |
1992 | && !flow_loop_nested_p (loop_a, loop_b) | |
1993 | && !flow_loop_nested_p (loop_b, loop_a)) | |
1994 | { | |
1995 | /* Example: when there are two consecutive loops, | |
1996 | ||
1997 | | loop_1 | |
1998 | | A[{0, +, 1}_1] | |
1999 | | endloop_1 | |
2000 | | loop_2 | |
2001 | | A[{0, +, 1}_2] | |
2002 | | endloop_2 | |
2003 | ||
2004 | the dependence relation cannot be captured by the | |
2005 | distance abstraction. */ | |
2006 | non_affine_dependence_relation (ddr); | |
464f49d8 | 2007 | return true; |
86df10e3 SP |
2008 | } |
2009 | ||
2010 | /* The dependence is carried by the outermost loop. Example: | |
2011 | | loop_1 | |
2012 | | A[{4, +, 1}_1] | |
2013 | | loop_2 | |
2014 | | A[{5, +, 1}_2] | |
2015 | | endloop_2 | |
2016 | | endloop_1 | |
2017 | In this case, the dependence is carried by loop_1. */ | |
2018 | loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b; | |
1f24dd47 | 2019 | loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth; |
56cf8686 SP |
2020 | |
2021 | /* If the loop number is still greater than the number of | |
2022 | loops we've been asked to analyze, or negative, | |
2023 | something is borked. */ | |
1f24dd47 DB |
2024 | gcc_assert (loop_depth >= 0); |
2025 | gcc_assert (loop_depth < nb_loops); | |
86df10e3 SP |
2026 | |
2027 | if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) | |
56cf8686 | 2028 | { |
86df10e3 | 2029 | non_affine_dependence_relation (ddr); |
464f49d8 | 2030 | return true; |
56cf8686 | 2031 | } |
86df10e3 SP |
2032 | |
2033 | dist = int_cst_value (SUB_DISTANCE (subscript)); | |
2034 | ||
2035 | if (dist == 0) | |
2036 | dir = dir_equal; | |
2037 | else if (dist > 0) | |
2038 | dir = dir_positive; | |
2039 | else if (dist < 0) | |
2040 | dir = dir_negative; | |
56cf8686 SP |
2041 | |
2042 | /* This is the subscript coupling test. | |
2043 | | loop i = 0, N, 1 | |
2044 | | T[i+1][i] = ... | |
2045 | | ... = T[i][i] | |
2046 | | endloop | |
2047 | There is no dependence. */ | |
1f24dd47 | 2048 | if (init_v[loop_depth] != 0 |
56cf8686 | 2049 | && dir != dir_star |
1f24dd47 DB |
2050 | && (enum data_dependence_direction) dir_v[loop_depth] != dir |
2051 | && (enum data_dependence_direction) dir_v[loop_depth] != dir_star) | |
56cf8686 | 2052 | { |
36d59cf7 | 2053 | finalize_ddr_dependent (ddr, chrec_known); |
464f49d8 | 2054 | return true; |
56cf8686 SP |
2055 | } |
2056 | ||
1f24dd47 DB |
2057 | dir_v[loop_depth] = dir; |
2058 | init_v[loop_depth] = 1; | |
56cf8686 SP |
2059 | } |
2060 | } | |
2061 | ||
2062 | /* There is a distance of 1 on all the outer loops: | |
2063 | ||
2064 | Example: there is a dependence of distance 1 on loop_1 for the array A. | |
2065 | | loop_1 | |
2066 | | A[5] = ... | |
2067 | | endloop | |
2068 | */ | |
2069 | { | |
2070 | struct loop *lca, *loop_a, *loop_b; | |
36d59cf7 DB |
2071 | struct data_reference *a = DDR_A (ddr); |
2072 | struct data_reference *b = DDR_B (ddr); | |
1f24dd47 | 2073 | int lca_depth; |
56cf8686 SP |
2074 | loop_a = loop_containing_stmt (DR_STMT (a)); |
2075 | loop_b = loop_containing_stmt (DR_STMT (b)); | |
2076 | ||
2077 | /* Get the common ancestor loop. */ | |
2078 | lca = find_common_loop (loop_a, loop_b); | |
1f24dd47 | 2079 | lca_depth = lca->depth - first_loop_depth; |
56cf8686 | 2080 | |
1f24dd47 DB |
2081 | gcc_assert (lca_depth >= 0); |
2082 | gcc_assert (lca_depth < nb_loops); | |
86df10e3 | 2083 | |
56cf8686 SP |
2084 | /* For each outer loop where init_v is not set, the accesses are |
2085 | in dependence of distance 1 in the loop. */ | |
2086 | if (lca != loop_a | |
2087 | && lca != loop_b | |
1f24dd47 DB |
2088 | && init_v[lca_depth] == 0) |
2089 | dir_v[lca_depth] = dir_positive; | |
56cf8686 SP |
2090 | |
2091 | lca = lca->outer; | |
2092 | if (lca) | |
2093 | { | |
1f24dd47 | 2094 | lca_depth = lca->depth - first_loop_depth; |
56cf8686 SP |
2095 | while (lca->depth != 0) |
2096 | { | |
86df10e3 SP |
2097 | /* If we're considering just a sub-nest, then don't record |
2098 | any information on the outer loops. */ | |
1f24dd47 | 2099 | if (lca_depth < 0) |
86df10e3 SP |
2100 | break; |
2101 | ||
1f24dd47 | 2102 | gcc_assert (lca_depth < nb_loops); |
86df10e3 | 2103 | |
1f24dd47 DB |
2104 | if (init_v[lca_depth] == 0) |
2105 | dir_v[lca_depth] = dir_positive; | |
56cf8686 | 2106 | lca = lca->outer; |
1f24dd47 | 2107 | lca_depth = lca->depth - first_loop_depth; |
56cf8686 SP |
2108 | |
2109 | } | |
2110 | } | |
2111 | } | |
2112 | ||
36d59cf7 | 2113 | DDR_DIR_VECT (ddr) = dir_v; |
86df10e3 | 2114 | DDR_SIZE_VECT (ddr) = nb_loops; |
464f49d8 | 2115 | return true; |
56cf8686 SP |
2116 | } |
2117 | ||
2118 | /* Returns true when all the access functions of A are affine or | |
2119 | constant. */ | |
2120 | ||
2121 | static bool | |
2122 | access_functions_are_affine_or_constant_p (struct data_reference *a) | |
2123 | { | |
2124 | unsigned int i; | |
9cbb7989 KH |
2125 | VEC(tree,heap) **fns = &DR_ACCESS_FNS (a); |
2126 | tree t; | |
56cf8686 | 2127 | |
9cbb7989 KH |
2128 | for (i = 0; VEC_iterate (tree, *fns, i, t); i++) |
2129 | if (!evolution_function_is_constant_p (t) | |
2130 | && !evolution_function_is_affine_multivariate_p (t)) | |
56cf8686 SP |
2131 | return false; |
2132 | ||
2133 | return true; | |
2134 | } | |
2135 | ||
2136 | /* This computes the affine dependence relation between A and B. | |
2137 | CHREC_KNOWN is used for representing the independence between two | |
2138 | accesses, while CHREC_DONT_KNOW is used for representing the unknown | |
2139 | relation. | |
2140 | ||
2141 | Note that it is possible to stop the computation of the dependence | |
2142 | relation the first time we detect a CHREC_KNOWN element for a given | |
2143 | subscript. */ | |
2144 | ||
2145 | void | |
2146 | compute_affine_dependence (struct data_dependence_relation *ddr) | |
2147 | { | |
2148 | struct data_reference *dra = DDR_A (ddr); | |
2149 | struct data_reference *drb = DDR_B (ddr); | |
2150 | ||
2151 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2152 | { | |
36d59cf7 | 2153 | fprintf (dump_file, "(compute_affine_dependence\n"); |
56cf8686 SP |
2154 | fprintf (dump_file, " (stmt_a = \n"); |
2155 | print_generic_expr (dump_file, DR_STMT (dra), 0); | |
2156 | fprintf (dump_file, ")\n (stmt_b = \n"); | |
2157 | print_generic_expr (dump_file, DR_STMT (drb), 0); | |
2158 | fprintf (dump_file, ")\n"); | |
2159 | } | |
2160 | ||
2161 | /* Analyze only when the dependence relation is not yet known. */ | |
2162 | if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) | |
2163 | { | |
2164 | if (access_functions_are_affine_or_constant_p (dra) | |
2165 | && access_functions_are_affine_or_constant_p (drb)) | |
2166 | subscript_dependence_tester (ddr); | |
2167 | ||
2168 | /* As a last case, if the dependence cannot be determined, or if | |
2169 | the dependence is considered too difficult to determine, answer | |
2170 | "don't know". */ | |
2171 | else | |
2172 | finalize_ddr_dependent (ddr, chrec_dont_know); | |
2173 | } | |
2174 | ||
2175 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2176 | fprintf (dump_file, ")\n"); | |
2177 | } | |
2178 | ||
789246d7 SP |
2179 | /* This computes the dependence relation for the same data |
2180 | reference into DDR. */ | |
2181 | ||
2182 | static void | |
2183 | compute_self_dependence (struct data_dependence_relation *ddr) | |
2184 | { | |
2185 | unsigned int i; | |
2186 | ||
2187 | for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) | |
2188 | { | |
2189 | struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); | |
2190 | ||
2191 | /* The accessed index overlaps for each iteration. */ | |
2192 | SUB_CONFLICTS_IN_A (subscript) = integer_zero_node; | |
2193 | SUB_CONFLICTS_IN_B (subscript) = integer_zero_node; | |
2194 | SUB_LAST_CONFLICT (subscript) = chrec_dont_know; | |
2195 | } | |
2196 | } | |
2197 | ||
7b8a92e1 KH |
2198 | |
2199 | typedef struct data_dependence_relation *ddr_p; | |
2200 | DEF_VEC_P(ddr_p); | |
2201 | DEF_VEC_ALLOC_P(ddr_p,heap); | |
2202 | ||
56cf8686 SP |
2203 | /* Compute a subset of the data dependence relation graph. Don't |
2204 | compute read-read relations, and avoid the computation of the | |
89dbed81 | 2205 | opposite relation, i.e. when AB has been computed, don't compute BA. |
56cf8686 SP |
2206 | DATAREFS contains a list of data references, and the result is set |
2207 | in DEPENDENCE_RELATIONS. */ | |
2208 | ||
2209 | static void | |
36d59cf7 | 2210 | compute_all_dependences (varray_type datarefs, |
7b8a92e1 | 2211 | VEC(ddr_p,heap) **dependence_relations) |
56cf8686 SP |
2212 | { |
2213 | unsigned int i, j, N; | |
2214 | ||
2215 | N = VARRAY_ACTIVE_SIZE (datarefs); | |
2216 | ||
789246d7 SP |
2217 | /* Note that we specifically skip i == j because it's a self dependence, and |
2218 | use compute_self_dependence below. */ | |
2219 | ||
56cf8686 | 2220 | for (i = 0; i < N; i++) |
789246d7 | 2221 | for (j = i + 1; j < N; j++) |
56cf8686 SP |
2222 | { |
2223 | struct data_reference *a, *b; | |
2224 | struct data_dependence_relation *ddr; | |
2225 | ||
2226 | a = VARRAY_GENERIC_PTR (datarefs, i); | |
2227 | b = VARRAY_GENERIC_PTR (datarefs, j); | |
56cf8686 SP |
2228 | ddr = initialize_data_dependence_relation (a, b); |
2229 | ||
7b8a92e1 | 2230 | VEC_safe_push (ddr_p, heap, *dependence_relations, ddr); |
56cf8686 | 2231 | compute_affine_dependence (ddr); |
86df10e3 | 2232 | compute_subscript_distance (ddr); |
56cf8686 | 2233 | } |
789246d7 SP |
2234 | |
2235 | /* Compute self dependence relation of each dataref to itself. */ | |
2236 | ||
2237 | for (i = 0; i < N; i++) | |
2238 | { | |
2239 | struct data_reference *a, *b; | |
2240 | struct data_dependence_relation *ddr; | |
2241 | ||
2242 | a = VARRAY_GENERIC_PTR (datarefs, i); | |
2243 | b = VARRAY_GENERIC_PTR (datarefs, i); | |
2244 | ddr = initialize_data_dependence_relation (a, b); | |
2245 | ||
2246 | VEC_safe_push (ddr_p, heap, *dependence_relations, ddr); | |
2247 | compute_self_dependence (ddr); | |
2248 | compute_subscript_distance (ddr); | |
2249 | } | |
56cf8686 SP |
2250 | } |
2251 | ||
2252 | /* Search the data references in LOOP, and record the information into | |
2253 | DATAREFS. Returns chrec_dont_know when failing to analyze a | |
2254 | difficult case, returns NULL_TREE otherwise. | |
2255 | ||
464f49d8 DB |
2256 | TODO: This function should be made smarter so that it can handle address |
2257 | arithmetic as if they were array accesses, etc. */ | |
56cf8686 | 2258 | |
86df10e3 | 2259 | tree |
56cf8686 SP |
2260 | find_data_references_in_loop (struct loop *loop, varray_type *datarefs) |
2261 | { | |
ccbdbf0a JL |
2262 | basic_block bb, *bbs; |
2263 | unsigned int i; | |
56cf8686 | 2264 | block_stmt_iterator bsi; |
86df10e3 | 2265 | |
ccbdbf0a JL |
2266 | bbs = get_loop_body (loop); |
2267 | ||
2268 | for (i = 0; i < loop->num_nodes; i++) | |
56cf8686 | 2269 | { |
ccbdbf0a JL |
2270 | bb = bbs[i]; |
2271 | ||
56cf8686 SP |
2272 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) |
2273 | { | |
2274 | tree stmt = bsi_stmt (bsi); | |
56cf8686 | 2275 | |
4aad410d SP |
2276 | /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects. |
2277 | Calls have side-effects, except those to const or pure | |
2278 | functions. */ | |
2279 | if ((TREE_CODE (stmt) == CALL_EXPR | |
2280 | && !(call_expr_flags (stmt) & (ECF_CONST | ECF_PURE))) | |
2281 | || (TREE_CODE (stmt) == ASM_EXPR | |
2282 | && ASM_VOLATILE_P (stmt))) | |
2283 | goto insert_dont_know_node; | |
56cf8686 | 2284 | |
f47c96aa | 2285 | if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) |
56cf8686 | 2286 | continue; |
4aad410d SP |
2287 | |
2288 | switch (TREE_CODE (stmt)) | |
86df10e3 | 2289 | { |
4aad410d SP |
2290 | case MODIFY_EXPR: |
2291 | if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF) | |
2292 | VARRAY_PUSH_GENERIC_PTR | |
2293 | (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 0), | |
2294 | false)); | |
2295 | ||
2296 | if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF) | |
2297 | VARRAY_PUSH_GENERIC_PTR | |
2298 | (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1), | |
2299 | true)); | |
2300 | ||
2301 | if (TREE_CODE (TREE_OPERAND (stmt, 0)) != ARRAY_REF | |
2302 | && TREE_CODE (TREE_OPERAND (stmt, 1)) != ARRAY_REF) | |
2303 | goto insert_dont_know_node; | |
2304 | ||
2305 | break; | |
2306 | ||
2307 | case CALL_EXPR: | |
2308 | { | |
2309 | tree args; | |
2310 | bool one_inserted = false; | |
2311 | ||
2312 | for (args = TREE_OPERAND (stmt, 1); args; args = TREE_CHAIN (args)) | |
2313 | if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF) | |
2314 | { | |
2315 | VARRAY_PUSH_GENERIC_PTR | |
2316 | (*datarefs, analyze_array (stmt, TREE_VALUE (args), true)); | |
2317 | one_inserted = true; | |
2318 | } | |
2319 | ||
2320 | if (!one_inserted) | |
2321 | goto insert_dont_know_node; | |
2322 | ||
2323 | break; | |
2324 | } | |
2325 | ||
2326 | default: | |
86df10e3 SP |
2327 | { |
2328 | struct data_reference *res; | |
4aad410d SP |
2329 | |
2330 | insert_dont_know_node:; | |
86df10e3 SP |
2331 | res = xmalloc (sizeof (struct data_reference)); |
2332 | DR_STMT (res) = NULL_TREE; | |
2333 | DR_REF (res) = NULL_TREE; | |
2334 | DR_ACCESS_FNS (res) = NULL; | |
2335 | DR_BASE_NAME (res) = NULL; | |
2336 | DR_IS_READ (res) = false; | |
2337 | VARRAY_PUSH_GENERIC_PTR (*datarefs, res); | |
4aad410d SP |
2338 | |
2339 | free (bbs); | |
2340 | return chrec_dont_know; | |
86df10e3 SP |
2341 | } |
2342 | } | |
2343 | ||
2344 | /* When there are no defs in the loop, the loop is parallel. */ | |
f47c96aa | 2345 | if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)) |
79ebd55c | 2346 | loop->parallel_p = false; |
56cf8686 | 2347 | } |
86df10e3 | 2348 | |
79ebd55c SP |
2349 | if (chrec_contains_undetermined (loop->estimated_nb_iterations)) |
2350 | compute_estimated_nb_iterations (loop); | |
56cf8686 SP |
2351 | } |
2352 | ||
ccbdbf0a JL |
2353 | free (bbs); |
2354 | ||
4aad410d | 2355 | return NULL_TREE; |
56cf8686 SP |
2356 | } |
2357 | ||
2358 | \f | |
2359 | ||
2360 | /* This section contains all the entry points. */ | |
2361 | ||
2362 | /* Given a loop nest LOOP, the following vectors are returned: | |
2363 | *DATAREFS is initialized to all the array elements contained in this loop, | |
36d59cf7 | 2364 | *DEPENDENCE_RELATIONS contains the relations between the data references. */ |
56cf8686 SP |
2365 | |
2366 | void | |
2367 | compute_data_dependences_for_loop (unsigned nb_loops, | |
2368 | struct loop *loop, | |
2369 | varray_type *datarefs, | |
36d59cf7 | 2370 | varray_type *dependence_relations) |
56cf8686 SP |
2371 | { |
2372 | unsigned int i; | |
7b8a92e1 KH |
2373 | VEC(ddr_p,heap) *allrelations; |
2374 | struct data_dependence_relation *ddr; | |
56cf8686 SP |
2375 | |
2376 | /* If one of the data references is not computable, give up without | |
2377 | spending time to compute other dependences. */ | |
2378 | if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know) | |
2379 | { | |
2380 | struct data_dependence_relation *ddr; | |
2381 | ||
2382 | /* Insert a single relation into dependence_relations: | |
2383 | chrec_dont_know. */ | |
2384 | ddr = initialize_data_dependence_relation (NULL, NULL); | |
2385 | VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr); | |
1f24dd47 DB |
2386 | build_classic_dist_vector (ddr, nb_loops, loop->depth); |
2387 | build_classic_dir_vector (ddr, nb_loops, loop->depth); | |
56cf8686 SP |
2388 | return; |
2389 | } | |
2390 | ||
7b8a92e1 | 2391 | allrelations = NULL; |
464f49d8 | 2392 | compute_all_dependences (*datarefs, &allrelations); |
56cf8686 | 2393 | |
7b8a92e1 | 2394 | for (i = 0; VEC_iterate (ddr_p, allrelations, i, ddr); i++) |
56cf8686 | 2395 | { |
1f24dd47 | 2396 | if (build_classic_dist_vector (ddr, nb_loops, loop->depth)) |
464f49d8 DB |
2397 | { |
2398 | VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr); | |
1f24dd47 | 2399 | build_classic_dir_vector (ddr, nb_loops, loop->depth); |
464f49d8 | 2400 | } |
56cf8686 SP |
2401 | } |
2402 | } | |
2403 | ||
2404 | /* Entry point (for testing only). Analyze all the data references | |
2405 | and the dependence relations. | |
2406 | ||
2407 | The data references are computed first. | |
2408 | ||
2409 | A relation on these nodes is represented by a complete graph. Some | |
2410 | of the relations could be of no interest, thus the relations can be | |
2411 | computed on demand. | |
2412 | ||
2413 | In the following function we compute all the relations. This is | |
2414 | just a first implementation that is here for: | |
2415 | - for showing how to ask for the dependence relations, | |
2416 | - for the debugging the whole dependence graph, | |
2417 | - for the dejagnu testcases and maintenance. | |
2418 | ||
2419 | It is possible to ask only for a part of the graph, avoiding to | |
2420 | compute the whole dependence graph. The computed dependences are | |
2421 | stored in a knowledge base (KB) such that later queries don't | |
2422 | recompute the same information. The implementation of this KB is | |
2423 | transparent to the optimizer, and thus the KB can be changed with a | |
2424 | more efficient implementation, or the KB could be disabled. */ | |
2425 | ||
2426 | void | |
2427 | analyze_all_data_dependences (struct loops *loops) | |
2428 | { | |
2429 | unsigned int i; | |
2430 | varray_type datarefs; | |
2431 | varray_type dependence_relations; | |
56cf8686 SP |
2432 | int nb_data_refs = 10; |
2433 | ||
56cf8686 SP |
2434 | VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs"); |
2435 | VARRAY_GENERIC_PTR_INIT (dependence_relations, | |
2436 | nb_data_refs * nb_data_refs, | |
2437 | "dependence_relations"); | |
2438 | ||
2439 | /* Compute DDs on the whole function. */ | |
2440 | compute_data_dependences_for_loop (loops->num, loops->parray[0], | |
36d59cf7 | 2441 | &datarefs, &dependence_relations); |
56cf8686 SP |
2442 | |
2443 | if (dump_file) | |
2444 | { | |
2445 | dump_data_dependence_relations (dump_file, dependence_relations); | |
2446 | fprintf (dump_file, "\n\n"); | |
56cf8686 | 2447 | |
86df10e3 SP |
2448 | if (dump_flags & TDF_DETAILS) |
2449 | dump_dist_dir_vectors (dump_file, dependence_relations); | |
56cf8686 | 2450 | |
86df10e3 | 2451 | if (dump_flags & TDF_STATS) |
56cf8686 | 2452 | { |
86df10e3 SP |
2453 | unsigned nb_top_relations = 0; |
2454 | unsigned nb_bot_relations = 0; | |
2455 | unsigned nb_basename_differ = 0; | |
2456 | unsigned nb_chrec_relations = 0; | |
2457 | ||
2458 | for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++) | |
2459 | { | |
2460 | struct data_dependence_relation *ddr; | |
2461 | ddr = VARRAY_GENERIC_PTR (dependence_relations, i); | |
56cf8686 | 2462 | |
86df10e3 SP |
2463 | if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr))) |
2464 | nb_top_relations++; | |
56cf8686 | 2465 | |
86df10e3 SP |
2466 | else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) |
2467 | { | |
2468 | struct data_reference *a = DDR_A (ddr); | |
2469 | struct data_reference *b = DDR_B (ddr); | |
2470 | bool differ_p; | |
56cf8686 | 2471 | |
86df10e3 SP |
2472 | if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b) |
2473 | || (array_base_name_differ_p (a, b, &differ_p) && differ_p)) | |
2474 | nb_basename_differ++; | |
2475 | else | |
2476 | nb_bot_relations++; | |
2477 | } | |
56cf8686 | 2478 | |
86df10e3 SP |
2479 | else |
2480 | nb_chrec_relations++; | |
2481 | } | |
56cf8686 | 2482 | |
86df10e3 SP |
2483 | gather_stats_on_scev_database (); |
2484 | } | |
56cf8686 | 2485 | } |
36d59cf7 DB |
2486 | |
2487 | free_dependence_relations (dependence_relations); | |
2488 | free_data_refs (datarefs); | |
2489 | } | |
2490 | ||
2491 | /* Free the memory used by a data dependence relation DDR. */ | |
2492 | ||
2493 | void | |
2494 | free_dependence_relation (struct data_dependence_relation *ddr) | |
2495 | { | |
2496 | if (ddr == NULL) | |
2497 | return; | |
2498 | ||
2499 | if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr)) | |
2500 | varray_clear (DDR_SUBSCRIPTS (ddr)); | |
2501 | free (ddr); | |
2502 | } | |
2503 | ||
2504 | /* Free the memory used by the data dependence relations from | |
2505 | DEPENDENCE_RELATIONS. */ | |
2506 | ||
2507 | void | |
2508 | free_dependence_relations (varray_type dependence_relations) | |
2509 | { | |
2510 | unsigned int i; | |
2511 | if (dependence_relations == NULL) | |
2512 | return; | |
2513 | ||
2514 | for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++) | |
2515 | free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i)); | |
56cf8686 | 2516 | varray_clear (dependence_relations); |
56cf8686 SP |
2517 | } |
2518 | ||
36d59cf7 DB |
2519 | /* Free the memory used by the data references from DATAREFS. */ |
2520 | ||
2521 | void | |
2522 | free_data_refs (varray_type datarefs) | |
2523 | { | |
2524 | unsigned int i; | |
2525 | ||
2526 | if (datarefs == NULL) | |
2527 | return; | |
56cf8686 | 2528 | |
36d59cf7 DB |
2529 | for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++) |
2530 | { | |
2531 | struct data_reference *dr = (struct data_reference *) | |
2532 | VARRAY_GENERIC_PTR (datarefs, i); | |
01c49ce8 KH |
2533 | if (dr) |
2534 | { | |
9cbb7989 | 2535 | VEC_free (tree, heap, DR_ACCESS_FNS (dr)); |
01c49ce8 KH |
2536 | free (dr); |
2537 | } | |
36d59cf7 DB |
2538 | } |
2539 | varray_clear (datarefs); | |
2540 | } | |
86df10e3 | 2541 |