]> git.ipfire.org Git - thirdparty/gcc.git/blame - gcc/tree-data-ref.c
projects / thirdparty / gcc.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Fotgotten changelog entry:
[thirdparty/gcc.git] / gcc / tree-data-ref.c
CommitLineData
56cf8686 1/* Data references and dependences detectors.
3d8864c0 2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
0ff4040e 3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
56cf8686
SP		 4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 2, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING. If not, write to the Free
366ccddb
KC		 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
2002110-1301, USA. */
56cf8686
SP		 21
22/* This pass walks a given loop structure searching for array
23 references. The information about the array accesses is recorded
24 in DATA_REFERENCE structures.
25
26 The basic test for determining the dependences is:
27 given two access functions chrec1 and chrec2 to a same array, and
28 x and y two vectors from the iteration domain, the same element of
29 the array is accessed twice at iterations x and y if and only if:
30 | chrec1 (x) == chrec2 (y).
31
32 The goals of this analysis are:
33
34 - to determine the independence: the relation between two
35 independent accesses is qualified with the chrec_known (this
36 information allows a loop parallelization),
37
38 - when two data references access the same data, to qualify the
39 dependence relation with classic dependence representations:
40
41 - distance vectors
42 - direction vectors
43 - loop carried level dependence
44 - polyhedron dependence
45 or with the chains of recurrences based representation,
46
50300b4c 47 - to define a knowledge base for storing the data dependence
56cf8686
SP		 48 information,
49
50 - to define an interface to access this data.
51
52
53 Definitions:
54
55 - subscript: given two array accesses a subscript is the tuple
56 composed of the access functions for a given dimension. Example:
57 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
58 (f1, g1), (f2, g2), (f3, g3).
59
60 - Diophantine equation: an equation whose coefficients and
61 solutions are integer constants, for example the equation
62 | 3*x + 2*y = 1
63 has an integer solution x = 1 and y = -1.
64
65 References:
66
67 - "Advanced Compilation for High Performance Computing" by Randy
68 Allen and Ken Kennedy.
69 http://citeseer.ist.psu.edu/goff91practical.html
70
71 - "Loop Transformations for Restructuring Compilers - The Foundations"
72 by Utpal Banerjee.
73
74
75*/
76
77#include "config.h"
78#include "system.h"
79#include "coretypes.h"
80#include "tm.h"
56cf8686
SP		 81#include "ggc.h"
82#include "tree.h"
83
84/* These RTL headers are needed for basic-block.h. */
85#include "rtl.h"
86#include "basic-block.h"
87#include "diagnostic.h"
88#include "tree-flow.h"
89#include "tree-dump.h"
90#include "timevar.h"
91#include "cfgloop.h"
92#include "tree-chrec.h"
93#include "tree-data-ref.h"
94#include "tree-scalar-evolution.h"
95#include "tree-pass.h"
946e1bc7 96#include "langhooks.h"
56cf8686 97
0ff4040e
SP		 98static struct datadep_stats
99{
100 int num_dependence_tests;
101 int num_dependence_dependent;
102 int num_dependence_independent;
103 int num_dependence_undetermined;
104
105 int num_subscript_tests;
106 int num_subscript_undetermined;
107 int num_same_subscript_function;
108
109 int num_ziv;
110 int num_ziv_independent;
111 int num_ziv_dependent;
112 int num_ziv_unimplemented;
113
114 int num_siv;
115 int num_siv_independent;
116 int num_siv_dependent;
117 int num_siv_unimplemented;
118
119 int num_miv;
120 int num_miv_independent;
121 int num_miv_dependent;
122 int num_miv_unimplemented;
123} dependence_stats;
124
ba42e045
SP		 125static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
126 struct data_reference *,
127 struct data_reference *);
56cf8686
SP		 128/* Returns true iff A divides B. */
129
130static inline bool
b73a6056 131tree_fold_divides_p (tree a, tree b)
56cf8686 132{
b73a6056
RS		 133 gcc_assert (TREE_CODE (a) == INTEGER_CST);
134 gcc_assert (TREE_CODE (b) == INTEGER_CST);
135 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a, 0));
56cf8686
SP		 136}
137
86df10e3
SP		 138/* Returns true iff A divides B. */
139
140static inline bool
141int_divides_p (int a, int b)
142{
143 return ((b % a) == 0);
56cf8686
SP		 144}
145
146\f
147
148/* Dump into FILE all the data references from DATAREFS. */
149
150void
ebf78a47 151dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
56cf8686
SP		 152{
153 unsigned int i;
ebf78a47
SP		 154 struct data_reference *dr;
155
156 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
157 dump_data_reference (file, dr);
56cf8686
SP		 158}
159
ebf78a47 160/* Dump into FILE all the dependence relations from DDRS. */
56cf8686
SP		 161
162void
163dump_data_dependence_relations (FILE *file,
ebf78a47 164 VEC (ddr_p, heap) *ddrs)
56cf8686
SP		 165{
166 unsigned int i;
ebf78a47
SP		 167 struct data_dependence_relation *ddr;
168
169 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
170 dump_data_dependence_relation (file, ddr);
56cf8686
SP		 171}
172
173/* Dump function for a DATA_REFERENCE structure. */
174
175void
176dump_data_reference (FILE *outf,
177 struct data_reference *dr)
178{
179 unsigned int i;
180
36d59cf7 181 fprintf (outf, "(Data Ref: \n stmt: ");
56cf8686
SP		 182 print_generic_stmt (outf, DR_STMT (dr), 0);
183 fprintf (outf, " ref: ");
184 print_generic_stmt (outf, DR_REF (dr), 0);
0ff4040e 185 fprintf (outf, " base_object: ");
86a07404 186 print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
56cf8686
SP		 187
188 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
189 {
190 fprintf (outf, " Access function %d: ", i);
191 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
192 }
193 fprintf (outf, ")\n");
194}
195
d93817c4
ZD		 196/* Dumps the affine function described by FN to the file OUTF. */
197
198static void
199dump_affine_function (FILE *outf, affine_fn fn)
200{
201 unsigned i;
202 tree coef;
203
204 print_generic_expr (outf, VEC_index (tree, fn, 0), TDF_SLIM);
205 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
206 {
207 fprintf (outf, " + ");
208 print_generic_expr (outf, coef, TDF_SLIM);
209 fprintf (outf, " * x_%u", i);
210 }
211}
212
213/* Dumps the conflict function CF to the file OUTF. */
214
215static void
216dump_conflict_function (FILE *outf, conflict_function *cf)
217{
218 unsigned i;
219
220 if (cf->n == NO_DEPENDENCE)
221 fprintf (outf, "no dependence\n");
222 else if (cf->n == NOT_KNOWN)
223 fprintf (outf, "not known\n");
224 else
225 {
226 for (i = 0; i < cf->n; i++)
227 {
228 fprintf (outf, "[");
229 dump_affine_function (outf, cf->fns[i]);
230 fprintf (outf, "]\n");
231 }
232 }
233}
234
86df10e3
SP		 235/* Dump function for a SUBSCRIPT structure. */
236
237void
238dump_subscript (FILE *outf, struct subscript *subscript)
239{
d93817c4 240 conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
86df10e3
SP		 241
242 fprintf (outf, "\n (subscript \n");
243 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
d93817c4
ZD		 244 dump_conflict_function (outf, cf);
245 if (CF_NONTRIVIAL_P (cf))
86df10e3
SP		 246 {
247 tree last_iteration = SUB_LAST_CONFLICT (subscript);
248 fprintf (outf, " last_conflict: ");
249 print_generic_stmt (outf, last_iteration, 0);
250 }
251
d93817c4 252 cf = SUB_CONFLICTS_IN_B (subscript);
86df10e3 253 fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
d93817c4
ZD		 254 dump_conflict_function (outf, cf);
255 if (CF_NONTRIVIAL_P (cf))
86df10e3
SP		 256 {
257 tree last_iteration = SUB_LAST_CONFLICT (subscript);
258 fprintf (outf, " last_conflict: ");
259 print_generic_stmt (outf, last_iteration, 0);
260 }
261
262 fprintf (outf, " (Subscript distance: ");
263 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
264 fprintf (outf, " )\n");
265 fprintf (outf, " )\n");
266}
267
0ff4040e
SP		 268/* Print the classic direction vector DIRV to OUTF. */
269
270void
271print_direction_vector (FILE *outf,
272 lambda_vector dirv,
273 int length)
274{
275 int eq;
276
277 for (eq = 0; eq < length; eq++)
278 {
279 enum data_dependence_direction dir = dirv[eq];
280
281 switch (dir)
282 {
283 case dir_positive:
284 fprintf (outf, " +");
285 break;
286 case dir_negative:
287 fprintf (outf, " -");
288 break;
289 case dir_equal:
290 fprintf (outf, " =");
291 break;
292 case dir_positive_or_equal:
293 fprintf (outf, " +=");
294 break;
295 case dir_positive_or_negative:
296 fprintf (outf, " +-");
297 break;
298 case dir_negative_or_equal:
299 fprintf (outf, " -=");
300 break;
301 case dir_star:
302 fprintf (outf, " *");
303 break;
304 default:
305 fprintf (outf, "indep");
306 break;
307 }
308 }
309 fprintf (outf, "\n");
310}
311
ba42e045
SP		 312/* Print a vector of direction vectors. */
313
314void
315print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
316 int length)
317{
318 unsigned j;
319 lambda_vector v;
320
321 for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++)
322 print_direction_vector (outf, v, length);
323}
324
325/* Print a vector of distance vectors. */
326
327void
328print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
329 int length)
330{
331 unsigned j;
332 lambda_vector v;
333
334 for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++)
335 print_lambda_vector (outf, v, length);
336}
337
338/* Debug version. */
339
340void
341debug_data_dependence_relation (struct data_dependence_relation *ddr)
342{
343 dump_data_dependence_relation (stderr, ddr);
344}
345
56cf8686
SP		 346/* Dump function for a DATA_DEPENDENCE_RELATION structure. */
347
348void
349dump_data_dependence_relation (FILE *outf,
350 struct data_dependence_relation *ddr)
351{
56cf8686 352 struct data_reference *dra, *drb;
86df10e3 353
56cf8686
SP		 354 dra = DDR_A (ddr);
355 drb = DDR_B (ddr);
86df10e3
SP		 356 fprintf (outf, "(Data Dep: \n");
357 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
56cf8686
SP		 358 fprintf (outf, " (don't know)\n");
359
360 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
361 fprintf (outf, " (no dependence)\n");
362
86df10e3 363 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
56cf8686 364 {
86df10e3 365 unsigned int i;
ba42e045 366 struct loop *loopi;
304afda6 367
56cf8686
SP		 368 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
369 {
56cf8686
SP		 370 fprintf (outf, " access_fn_A: ");
371 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
372 fprintf (outf, " access_fn_B: ");
373 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
86df10e3 374 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
56cf8686 375 }
304afda6 376
3d8864c0 377 fprintf (outf, " inner loop index: %d\n", DDR_INNER_LOOP (ddr));
ba42e045
SP		 378 fprintf (outf, " loop nest: (");
379 for (i = 0; VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
380 fprintf (outf, "%d ", loopi->num);
381 fprintf (outf, ")\n");
382
304afda6 383 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
56cf8686 384 {
304afda6
SP		 385 fprintf (outf, " distance_vector: ");
386 print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
ba42e045 387 DDR_NB_LOOPS (ddr));
86df10e3 388 }
304afda6
SP		 389
390 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
86df10e3 391 {
304afda6 392 fprintf (outf, " direction_vector: ");
0ff4040e 393 print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
ba42e045 394 DDR_NB_LOOPS (ddr));
56cf8686 395 }
56cf8686
SP		 396 }
397
398 fprintf (outf, ")\n");
399}
400
56cf8686
SP		 401/* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
402
403void
404dump_data_dependence_direction (FILE *file,
405 enum data_dependence_direction dir)
406{
407 switch (dir)
408 {
409 case dir_positive:
410 fprintf (file, "+");
411 break;
412
413 case dir_negative:
414 fprintf (file, "-");
415 break;
416
417 case dir_equal:
418 fprintf (file, "=");
419 break;
420
421 case dir_positive_or_negative:
422 fprintf (file, "+-");
423 break;
424
425 case dir_positive_or_equal:
426 fprintf (file, "+=");
427 break;
428
429 case dir_negative_or_equal:
430 fprintf (file, "-=");
431 break;
432
433 case dir_star:
434 fprintf (file, "*");
435 break;
436
437 default:
438 break;
439 }
440}
441
86df10e3
SP		 442/* Dumps the distance and direction vectors in FILE. DDRS contains
443 the dependence relations, and VECT_SIZE is the size of the
444 dependence vectors, or in other words the number of loops in the
445 considered nest. */
446
447void
ebf78a47 448dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
86df10e3 449{
304afda6 450 unsigned int i, j;
ebf78a47
SP		 451 struct data_dependence_relation *ddr;
452 lambda_vector v;
86df10e3 453
ebf78a47
SP		 454 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
455 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
456 {
457 for (j = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), j, v); j++)
458 {
459 fprintf (file, "DISTANCE_V (");
460 print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
461 fprintf (file, ")\n");
462 }
463
464 for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++)
465 {
466 fprintf (file, "DIRECTION_V (");
467 print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
468 fprintf (file, ")\n");
469 }
470 }
304afda6 471
86df10e3
SP		 472 fprintf (file, "\n\n");
473}
474
475/* Dumps the data dependence relations DDRS in FILE. */
476
477void
ebf78a47 478dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
86df10e3
SP		 479{
480 unsigned int i;
ebf78a47
SP		 481 struct data_dependence_relation *ddr;
482
483 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
484 dump_data_dependence_relation (file, ddr);
86df10e3 485
86df10e3
SP		 486 fprintf (file, "\n\n");
487}
488
3cb960c7
ZD		 489/* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
490 will be ssizetype. */
86a07404 491
3cb960c7
ZD		 492static void
493split_constant_offset (tree exp, tree *var, tree *off)
86a07404 494{
3cb960c7
ZD		 495 tree type = TREE_TYPE (exp), otype;
496 tree var0, var1;
497 tree off0, off1;
86a07404 498
3cb960c7
ZD		 499 *var = exp;
500 STRIP_NOPS (exp);
501 otype = TREE_TYPE (exp);
86a07404 502
3cb960c7 503 switch (TREE_CODE (exp))
86a07404 504 {
3cb960c7
ZD		 505 case INTEGER_CST:
506 *var = build_int_cst (type, 0);
507 *off = fold_convert (ssizetype, exp);
508 return;
86a07404 509
3cb960c7
ZD		 510 case PLUS_EXPR:
511 case MINUS_EXPR:
512 split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0);
513 split_constant_offset (TREE_OPERAND (exp, 1), &var1, &off1);
514 *var = fold_convert (type, fold_build2 (TREE_CODE (exp), otype,
515 var0, var1));
516 *off = size_binop (TREE_CODE (exp), off0, off1);
517 return;
86a07404 518
86a07404 519 case MULT_EXPR:
3cb960c7
ZD		 520 off1 = TREE_OPERAND (exp, 1);
521 if (TREE_CODE (off1) != INTEGER_CST)
522 break;
523
524 split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0);
525 *var = fold_convert (type, fold_build2 (MULT_EXPR, otype,
526 var0, off1));
527 *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, off1));
528 return;
86a07404 529
3cb960c7
ZD		 530 case ADDR_EXPR:
531 {
532 tree op, base, poffset;
533 HOST_WIDE_INT pbitsize, pbitpos;
534 enum machine_mode pmode;
535 int punsignedp, pvolatilep;
86a07404 536
3cb960c7
ZD		 537 op = TREE_OPERAND (exp, 0);
538 if (!handled_component_p (op))
86a07404 539 break;
86a07404 540
3cb960c7
ZD		 541 base = get_inner_reference (op, &pbitsize, &pbitpos, &poffset,
542 &pmode, &punsignedp, &pvolatilep, false);
86a07404 543
3cb960c7
ZD		 544 if (pbitpos % BITS_PER_UNIT != 0)
545 break;
546 base = build_fold_addr_expr (base);
547 off0 = ssize_int (pbitpos / BITS_PER_UNIT);
86a07404 548
3cb960c7
ZD		 549 if (poffset)
550 {
551 split_constant_offset (poffset, &poffset, &off1);
552 off0 = size_binop (PLUS_EXPR, off0, off1);
553 base = fold_build2 (PLUS_EXPR, TREE_TYPE (base),
554 base,
555 fold_convert (TREE_TYPE (base), poffset));
556 }
557
558 *var = fold_convert (type, base);
559 *off = off0;
560 return;
561 }
86a07404
IR		 562
563 default:
3cb960c7 564 break;
86a07404
IR		 565 }
566
3cb960c7 567 *off = ssize_int (0);
86a07404
IR		 568}
569
3cb960c7
ZD		 570/* Returns the address ADDR of an object in a canonical shape (without nop
571 casts, and with type of pointer to the object). */
86a07404
IR		 572
573static tree
3cb960c7 574canonicalize_base_object_address (tree addr)
86a07404 575{
3cb960c7 576 STRIP_NOPS (addr);
86a07404 577
3cb960c7
ZD		 578 if (TREE_CODE (addr) != ADDR_EXPR)
579 return addr;
86a07404 580
3cb960c7 581 return build_fold_addr_expr (TREE_OPERAND (addr, 0));
86a07404
IR		 582}
583
3cb960c7
ZD		 584/* Analyzes the behavior of the memory reference DR in the innermost loop that
585 contains it. */
86a07404 586
3cb960c7
ZD		 587static void
588dr_analyze_innermost (struct data_reference *dr)
86a07404 589{
3cb960c7
ZD		 590 tree stmt = DR_STMT (dr);
591 struct loop *loop = loop_containing_stmt (stmt);
592 tree ref = DR_REF (dr);
86a07404 593 HOST_WIDE_INT pbitsize, pbitpos;
3cb960c7 594 tree base, poffset;
86a07404
IR		 595 enum machine_mode pmode;
596 int punsignedp, pvolatilep;
3cb960c7
ZD		 597 affine_iv base_iv, offset_iv;
598 tree init, dinit, step;
599
600 if (dump_file && (dump_flags & TDF_DETAILS))
601 fprintf (dump_file, "analyze_innermost: ");
86a07404 602
3cb960c7
ZD		 603 base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset,
604 &pmode, &punsignedp, &pvolatilep, false);
605 gcc_assert (base != NULL_TREE);
86a07404 606
3cb960c7 607 if (pbitpos % BITS_PER_UNIT != 0)
86a07404 608 {
3cb960c7
ZD		 609 if (dump_file && (dump_flags & TDF_DETAILS))
610 fprintf (dump_file, "failed: bit offset alignment.\n");
611 return;
612 }
86a07404 613
3cb960c7
ZD		 614 base = build_fold_addr_expr (base);
615 if (!simple_iv (loop, stmt, base, &base_iv, false))
616 {
617 if (dump_file && (dump_flags & TDF_DETAILS))
618 fprintf (dump_file, "failed: evolution of base is not affine.\n");
619 return;
620 }
621 if (!poffset)
622 {
623 offset_iv.base = ssize_int (0);
624 offset_iv.step = ssize_int (0);
625 }
626 else if (!simple_iv (loop, stmt, poffset, &offset_iv, false))
627 {
628 if (dump_file && (dump_flags & TDF_DETAILS))
629 fprintf (dump_file, "failed: evolution of offset is not affine.\n");
630 return;
631 }
86a07404 632
3cb960c7
ZD		 633 init = ssize_int (pbitpos / BITS_PER_UNIT);
634 split_constant_offset (base_iv.base, &base_iv.base, &dinit);
635 init = size_binop (PLUS_EXPR, init, dinit);
636 split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
637 init = size_binop (PLUS_EXPR, init, dinit);
86a07404 638
3cb960c7
ZD		 639 step = size_binop (PLUS_EXPR,
640 fold_convert (ssizetype, base_iv.step),
641 fold_convert (ssizetype, offset_iv.step));
86a07404 642
3cb960c7 643 DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base);
86a07404 644
3cb960c7
ZD		 645 DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base);
646 DR_INIT (dr) = init;
647 DR_STEP (dr) = step;
86a07404 648
3cb960c7 649 DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base));
86a07404 650
3cb960c7
ZD		 651 if (dump_file && (dump_flags & TDF_DETAILS))
652 fprintf (dump_file, "success.\n");
653}
86a07404 654
3cb960c7
ZD		 655/* Determines the base object and the list of indices of memory reference
656 DR, analysed in loop nest NEST. */
86a07404 657
3cb960c7
ZD		 658static void
659dr_analyze_indices (struct data_reference *dr, struct loop *nest)
660{
661 tree stmt = DR_STMT (dr);
662 struct loop *loop = loop_containing_stmt (stmt);
663 VEC (tree, heap) *access_fns = NULL;
664 tree ref = unshare_expr (DR_REF (dr)), aref = ref, op;
665 tree base, off, access_fn;
86a07404 666
3cb960c7 667 while (handled_component_p (aref))
86a07404 668 {
3cb960c7 669 if (TREE_CODE (aref) == ARRAY_REF)
86a07404 670 {
3cb960c7
ZD		 671 op = TREE_OPERAND (aref, 1);
672 access_fn = analyze_scalar_evolution (loop, op);
673 access_fn = resolve_mixers (nest, access_fn);
674 VEC_safe_push (tree, heap, access_fns, access_fn);
675
676 TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0);
86a07404 677 }
3cb960c7
ZD		 678
679 aref = TREE_OPERAND (aref, 0);
86a07404
IR		 680 }
681
3cb960c7 682 if (INDIRECT_REF_P (aref))
86a07404 683 {
3cb960c7
ZD		 684 op = TREE_OPERAND (aref, 0);
685 access_fn = analyze_scalar_evolution (loop, op);
686 access_fn = resolve_mixers (nest, access_fn);
687 base = initial_condition (access_fn);
688 split_constant_offset (base, &base, &off);
689 access_fn = chrec_replace_initial_condition (access_fn,
690 fold_convert (TREE_TYPE (base), off));
691
692 TREE_OPERAND (aref, 0) = base;
693 VEC_safe_push (tree, heap, access_fns, access_fn);
86a07404 694 }
86a07404 695
3cb960c7
ZD		 696 DR_BASE_OBJECT (dr) = ref;
697 DR_ACCESS_FNS (dr) = access_fns;
86a07404
IR		 698}
699
3cb960c7 700/* Extracts the alias analysis information from the memory reference DR. */
86a07404 701
3cb960c7
ZD		 702static void
703dr_analyze_alias (struct data_reference *dr)
86a07404 704{
3cb960c7
ZD		 705 tree stmt = DR_STMT (dr);
706 tree ref = DR_REF (dr);
707 tree base = get_base_address (ref), addr, smt = NULL_TREE;
708 ssa_op_iter it;
709 tree op;
710 bitmap vops;
711
712 if (DECL_P (base))
713 smt = base;
714 else if (INDIRECT_REF_P (base))
715 {
716 addr = TREE_OPERAND (base, 0);
717 if (TREE_CODE (addr) == SSA_NAME)
718 {
719 smt = symbol_mem_tag (SSA_NAME_VAR (addr));
720 DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
721 }
722 }
86a07404 723
3cb960c7
ZD		 724 DR_SYMBOL_TAG (dr) = smt;
725 if (var_can_have_subvars (smt))
726 DR_SUBVARS (dr) = get_subvars_for_var (smt);
86a07404 727
3cb960c7
ZD		 728 vops = BITMAP_ALLOC (NULL);
729 FOR_EACH_SSA_TREE_OPERAND (op, stmt, it, SSA_OP_VIRTUAL_USES)
86a07404 730 {
3cb960c7 731 bitmap_set_bit (vops, DECL_UID (SSA_NAME_VAR (op)));
86a07404
IR		 732 }
733
3cb960c7
ZD		 734 DR_VOPS (dr) = vops;
735}
86a07404 736
3cb960c7 737/* Returns true if the address of DR is invariant. */
86a07404 738
3cb960c7
ZD		 739static bool
740dr_address_invariant_p (struct data_reference *dr)
741{
742 unsigned i;
743 tree idx;
744
745 for (i = 0; VEC_iterate (tree, DR_ACCESS_FNS (dr), i, idx); i++)
746 if (tree_contains_chrecs (idx, NULL))
747 return false;
e838422b 748
e838422b 749 return true;
86a07404
IR		 750}
751
3cb960c7 752/* Frees data reference DR. */
8fdbc9c6
ZD		 753
754static void
755free_data_ref (data_reference_p dr)
756{
3cb960c7
ZD		 757 BITMAP_FREE (DR_VOPS (dr));
758 VEC_free (tree, heap, DR_ACCESS_FNS (dr));
8fdbc9c6
ZD		 759 free (dr);
760}
86a07404 761
3cb960c7
ZD		 762/* Analyzes memory reference MEMREF accessed in STMT. The reference
763 is read if IS_READ is true, write otherwise. Returns the
764 data_reference description of MEMREF. NEST is the outermost loop of the
765 loop nest in that the reference should be analysed. */
86a07404
IR		 766
767static struct data_reference *
3cb960c7 768create_data_ref (struct loop *nest, tree memref, tree stmt, bool is_read)
86a07404 769{
3cb960c7 770 struct data_reference *dr;
0ff4040e 771
3cb960c7 772 if (dump_file && (dump_flags & TDF_DETAILS))
0ff4040e 773 {
3cb960c7
ZD		 774 fprintf (dump_file, "Creating dr for ");
775 print_generic_expr (dump_file, memref, TDF_SLIM);
776 fprintf (dump_file, "\n");
0ff4040e 777 }
e2157b49 778
3cb960c7
ZD		 779 dr = XCNEW (struct data_reference);
780 DR_STMT (dr) = stmt;
781 DR_REF (dr) = memref;
782 DR_IS_READ (dr) = is_read;
86a07404 783
3cb960c7
ZD		 784 dr_analyze_innermost (dr);
785 dr_analyze_indices (dr, nest);
786 dr_analyze_alias (dr);
86a07404
IR		 787
788 if (dump_file && (dump_flags & TDF_DETAILS))
789 {
3cb960c7 790 fprintf (dump_file, "\tbase_address: ");
86a07404
IR		 791 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
792 fprintf (dump_file, "\n\toffset from base address: ");
793 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
794 fprintf (dump_file, "\n\tconstant offset from base address: ");
795 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
86a07404
IR		 796 fprintf (dump_file, "\n\tstep: ");
797 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
3cb960c7
ZD		 798 fprintf (dump_file, "\n\taligned to: ");
799 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
800 fprintf (dump_file, "\n\tbase_object: ");
801 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
802 fprintf (dump_file, "\n\tsymbol tag: ");
803 print_generic_expr (dump_file, DR_SYMBOL_TAG (dr), TDF_SLIM);
86a07404 804 fprintf (dump_file, "\n");
3cb960c7
ZD		 805 }
806
807 /* FIXME -- data dependence analysis does not work correctly for objects with
808 invariant addresses. Let us fail here until the problem is fixed. */
809 if (dr_address_invariant_p (dr))
810 {
811 free_data_ref (dr);
812 dr = NULL;
813 if (dump_file && (dump_flags & TDF_DETAILS))
814 fprintf (dump_file, "\tFAILED as dr address is invariant\n");
815 }
816
86a07404
IR		 817 return dr;
818}
819
d93817c4
ZD		 820/* Returns true if FNA == FNB. */
821
822static bool
823affine_function_equal_p (affine_fn fna, affine_fn fnb)
824{
825 unsigned i, n = VEC_length (tree, fna);
86a07404 826
f86289d5
ZD		 827 if (n != VEC_length (tree, fnb))
828 return false;
86df10e3 829
d93817c4
ZD		 830 for (i = 0; i < n; i++)
831 if (!operand_equal_p (VEC_index (tree, fna, i),
832 VEC_index (tree, fnb, i), 0))
833 return false;
834
835 return true;
836}
837
838/* If all the functions in CF are the same, returns one of them,
839 otherwise returns NULL. */
840
841static affine_fn
842common_affine_function (conflict_function *cf)
86df10e3 843{
d93817c4
ZD		 844 unsigned i;
845 affine_fn comm;
846
847 if (!CF_NONTRIVIAL_P (cf))
848 return NULL;
849
850 comm = cf->fns[0];
851
852 for (i = 1; i < cf->n; i++)
853 if (!affine_function_equal_p (comm, cf->fns[i]))
854 return NULL;
855
856 return comm;
857}
86df10e3 858
d93817c4
ZD		 859/* Returns the base of the affine function FN. */
860
861static tree
862affine_function_base (affine_fn fn)
863{
864 return VEC_index (tree, fn, 0);
865}
866
867/* Returns true if FN is a constant. */
868
869static bool
870affine_function_constant_p (affine_fn fn)
871{
872 unsigned i;
873 tree coef;
874
875 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
876 if (!integer_zerop (coef))
e2157b49
SP		 877 return false;
878
86df10e3
SP		 879 return true;
880}
881
1baf2906
SP		 882/* Returns true if FN is the zero constant function. */
883
884static bool
885affine_function_zero_p (affine_fn fn)
886{
887 return (integer_zerop (affine_function_base (fn))
888 && affine_function_constant_p (fn));
889}
890
d93817c4
ZD		 891/* Applies operation OP on affine functions FNA and FNB, and returns the
892 result. */
893
894static affine_fn
895affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
896{
897 unsigned i, n, m;
898 affine_fn ret;
899 tree coef;
900
901 if (VEC_length (tree, fnb) > VEC_length (tree, fna))
902 {
903 n = VEC_length (tree, fna);
904 m = VEC_length (tree, fnb);
905 }
906 else
907 {
908 n = VEC_length (tree, fnb);
909 m = VEC_length (tree, fna);
910 }
911
912 ret = VEC_alloc (tree, heap, m);
913 for (i = 0; i < n; i++)
914 VEC_quick_push (tree, ret,
915 fold_build2 (op, integer_type_node,
916 VEC_index (tree, fna, i),
917 VEC_index (tree, fnb, i)));
918
919 for (; VEC_iterate (tree, fna, i, coef); i++)
920 VEC_quick_push (tree, ret,
921 fold_build2 (op, integer_type_node,
922 coef, integer_zero_node));
923 for (; VEC_iterate (tree, fnb, i, coef); i++)
924 VEC_quick_push (tree, ret,
925 fold_build2 (op, integer_type_node,
926 integer_zero_node, coef));
927
928 return ret;
929}
930
931/* Returns the sum of affine functions FNA and FNB. */
932
933static affine_fn
934affine_fn_plus (affine_fn fna, affine_fn fnb)
935{
936 return affine_fn_op (PLUS_EXPR, fna, fnb);
937}
938
939/* Returns the difference of affine functions FNA and FNB. */
940
941static affine_fn
942affine_fn_minus (affine_fn fna, affine_fn fnb)
943{
944 return affine_fn_op (MINUS_EXPR, fna, fnb);
945}
946
947/* Frees affine function FN. */
948
949static void
950affine_fn_free (affine_fn fn)
951{
952 VEC_free (tree, heap, fn);
953}
954
86df10e3
SP		 955/* Determine for each subscript in the data dependence relation DDR
956 the distance. */
56cf8686 957
0ff4040e 958static void
86df10e3 959compute_subscript_distance (struct data_dependence_relation *ddr)
56cf8686 960{
d93817c4
ZD		 961 conflict_function *cf_a, *cf_b;
962 affine_fn fn_a, fn_b, diff;
963
56cf8686
SP		 964 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
965 {
966 unsigned int i;
967
968 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
969 {
56cf8686
SP		 970 struct subscript *subscript;
971
972 subscript = DDR_SUBSCRIPT (ddr, i);
d93817c4
ZD		 973 cf_a = SUB_CONFLICTS_IN_A (subscript);
974 cf_b = SUB_CONFLICTS_IN_B (subscript);
86df10e3 975
d93817c4
ZD		 976 fn_a = common_affine_function (cf_a);
977 fn_b = common_affine_function (cf_b);
978 if (!fn_a || !fn_b)
86df10e3 979 {
d93817c4
ZD		 980 SUB_DISTANCE (subscript) = chrec_dont_know;
981 return;
86df10e3 982 }
d93817c4 983 diff = affine_fn_minus (fn_a, fn_b);
56cf8686 984
d93817c4
ZD		 985 if (affine_function_constant_p (diff))
986 SUB_DISTANCE (subscript) = affine_function_base (diff);
56cf8686
SP		 987 else
988 SUB_DISTANCE (subscript) = chrec_dont_know;
d93817c4
ZD		 989
990 affine_fn_free (diff);
56cf8686
SP		 991 }
992 }
993}
994
d93817c4
ZD		 995/* Returns the conflict function for "unknown". */
996
997static conflict_function *
998conflict_fn_not_known (void)
999{
1000 conflict_function *fn = XCNEW (conflict_function);
1001 fn->n = NOT_KNOWN;
1002
1003 return fn;
1004}
1005
1006/* Returns the conflict function for "independent". */
1007
1008static conflict_function *
1009conflict_fn_no_dependence (void)
1010{
1011 conflict_function *fn = XCNEW (conflict_function);
1012 fn->n = NO_DEPENDENCE;
1013
1014 return fn;
1015}
1016
3cb960c7
ZD		 1017/* Returns true if the address of OBJ is invariant in LOOP. */
1018
1019static bool
1020object_address_invariant_in_loop_p (struct loop *loop, tree obj)
1021{
1022 while (handled_component_p (obj))
1023 {
1024 if (TREE_CODE (obj) == ARRAY_REF)
1025 {
1026 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1027 need to check the stride and the lower bound of the reference. */
1028 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1029 loop->num)
1030 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 3),
1031 loop->num))
1032 return false;
1033 }
1034 else if (TREE_CODE (obj) == COMPONENT_REF)
1035 {
1036 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1037 loop->num))
1038 return false;
1039 }
1040 obj = TREE_OPERAND (obj, 0);
1041 }
1042
1043 if (!INDIRECT_REF_P (obj))
1044 return true;
1045
1046 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0),
1047 loop->num);
1048}
1049
1050/* Returns true if A and B are accesses to different objects, or to different
1051 fields of the same object. */
1052
1053static bool
1054disjoint_objects_p (tree a, tree b)
1055{
1056 tree base_a, base_b;
1057 VEC (tree, heap) *comp_a = NULL, *comp_b = NULL;
1058 bool ret;
1059
1060 base_a = get_base_address (a);
1061 base_b = get_base_address (b);
1062
1063 if (DECL_P (base_a)
1064 && DECL_P (base_b)
1065 && base_a != base_b)
1066 return true;
1067
1068 if (!operand_equal_p (base_a, base_b, 0))
1069 return false;
1070
1071 /* Compare the component references of A and B. We must start from the inner
1072 ones, so record them to the vector first. */
1073 while (handled_component_p (a))
1074 {
1075 VEC_safe_push (tree, heap, comp_a, a);
1076 a = TREE_OPERAND (a, 0);
1077 }
1078 while (handled_component_p (b))
1079 {
1080 VEC_safe_push (tree, heap, comp_b, b);
1081 b = TREE_OPERAND (b, 0);
1082 }
1083
1084 ret = false;
1085 while (1)
1086 {
1087 if (VEC_length (tree, comp_a) == 0
1088 || VEC_length (tree, comp_b) == 0)
1089 break;
1090
1091 a = VEC_pop (tree, comp_a);
1092 b = VEC_pop (tree, comp_b);
1093
1094 /* Real and imaginary part of a variable do not alias. */
1095 if ((TREE_CODE (a) == REALPART_EXPR
1096 && TREE_CODE (b) == IMAGPART_EXPR)
1097 || (TREE_CODE (a) == IMAGPART_EXPR
1098 && TREE_CODE (b) == REALPART_EXPR))
1099 {
1100 ret = true;
1101 break;
1102 }
1103
1104 if (TREE_CODE (a) != TREE_CODE (b))
1105 break;
1106
1107 /* Nothing to do for ARRAY_REFs, as the indices of array_refs in
1108 DR_BASE_OBJECT are always zero. */
1109 if (TREE_CODE (a) == ARRAY_REF)
1110 continue;
1111 else if (TREE_CODE (a) == COMPONENT_REF)
1112 {
1113 if (operand_equal_p (TREE_OPERAND (a, 1), TREE_OPERAND (b, 1), 0))
1114 continue;
1115
1116 /* Different fields of unions may overlap. */
1117 base_a = TREE_OPERAND (a, 0);
1118 if (TREE_CODE (TREE_TYPE (base_a)) == UNION_TYPE)
1119 break;
1120
1121 /* Different fields of structures cannot. */
1122 ret = true;
1123 break;
1124 }
1125 else
1126 break;
1127 }
1128
1129 VEC_free (tree, heap, comp_a);
1130 VEC_free (tree, heap, comp_b);
1131
1132 return ret;
1133}
1134
1135/* Returns false if we can prove that data references A and B do not alias,
1136 true otherwise. */
1137
1138static bool
1139dr_may_alias_p (struct data_reference *a, struct data_reference *b)
1140{
1141 tree addr_a = DR_BASE_ADDRESS (a);
1142 tree addr_b = DR_BASE_ADDRESS (b);
1143 tree type_a, type_b;
1144 tree decl_a = NULL_TREE, decl_b = NULL_TREE;
1145
1146 /* If the sets of virtual operands are disjoint, the memory references do not
1147 alias. */
1148 if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
1149 return false;
1150
1151 /* If the accessed objects are disjoint, the memory references do not
1152 alias. */
1153 if (disjoint_objects_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b)))
1154 return false;
1155
1156 if (!addr_a || !addr_b)
1157 return true;
1158
1159 /* If the references are based on different static objects, they cannot alias
1160 (PTA should be able to disambiguate such accesses, but often it fails to,
1161 since currently we cannot distinguish between pointer and offset in pointer
1162 arithmetics). */
1163 if (TREE_CODE (addr_a) == ADDR_EXPR
1164 && TREE_CODE (addr_b) == ADDR_EXPR)
1165 return TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0);
1166
1167 /* An instruction writing through a restricted pointer is "independent" of any
1168 instruction reading or writing through a different restricted pointer,
1169 in the same block/scope. */
1170
1171 type_a = TREE_TYPE (addr_a);
1172 type_b = TREE_TYPE (addr_b);
1173 gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
1174
1175 if (TREE_CODE (addr_a) == SSA_NAME)
1176 decl_a = SSA_NAME_VAR (addr_a);
1177 if (TREE_CODE (addr_b) == SSA_NAME)
1178 decl_b = SSA_NAME_VAR (addr_b);
1179
1180 if (TYPE_RESTRICT (type_a) && TYPE_RESTRICT (type_b)
1181 && (!DR_IS_READ (a) || !DR_IS_READ (b))
1182 && decl_a && TREE_CODE (decl_a) == PARM_DECL
1183 && decl_b && TREE_CODE (decl_b) == PARM_DECL
1184 && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL
1185 && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b))
1186 return false;
1187
1188 return true;
1189}
1190
0ff4040e
SP		 1191/* Initialize a data dependence relation between data accesses A and
1192 B. NB_LOOPS is the number of loops surrounding the references: the
1193 size of the classic distance/direction vectors. */
56cf8686 1194
0ff4040e 1195static struct data_dependence_relation *
56cf8686 1196initialize_data_dependence_relation (struct data_reference *a,
0ff4040e 1197 struct data_reference *b,
ba42e045 1198 VEC (loop_p, heap) *loop_nest)
56cf8686
SP		 1199{
1200 struct data_dependence_relation *res;
0ff4040e 1201 unsigned int i;
56cf8686 1202
5ed6ace5 1203 res = XNEW (struct data_dependence_relation);
56cf8686
SP		 1204 DDR_A (res) = a;
1205 DDR_B (res) = b;
3ac57120 1206 DDR_LOOP_NEST (res) = NULL;
56cf8686 1207
86a07404
IR		 1208 if (a == NULL || b == NULL)
1209 {
1210 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1211 return res;
1212 }
1213
3cb960c7
ZD		 1214 /* If the data references do not alias, then they are independent. */
1215 if (!dr_may_alias_p (a, b))
86a07404 1216 {
3cb960c7 1217 DDR_ARE_DEPENDENT (res) = chrec_known;
86a07404
IR		 1218 return res;
1219 }
56cf8686 1220
3cb960c7
ZD		 1221 /* If the references do not access the same object, we do not know
1222 whether they alias or not. */
1223 if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0))
56cf8686 1224 {
86a07404
IR		 1225 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1226 return res;
1227 }
0ff4040e 1228
3cb960c7
ZD		 1229 /* If the base of the object is not invariant in the loop nest, we cannot
1230 analyse it. TODO -- in fact, it would suffice to record that there may
1231 be arbitrary depencences in the loops where the base object varies. */
1232 if (!object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
1233 DR_BASE_OBJECT (a)))
86a07404 1234 {
3cb960c7 1235 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
86a07404
IR		 1236 return res;
1237 }
3cb960c7
ZD		 1238
1239 gcc_assert (DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b));
1240
86a07404
IR		 1241 DDR_AFFINE_P (res) = true;
1242 DDR_ARE_DEPENDENT (res) = NULL_TREE;
ebf78a47 1243 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
ba42e045 1244 DDR_LOOP_NEST (res) = loop_nest;
3d8864c0 1245 DDR_INNER_LOOP (res) = 0;
304afda6
SP		 1246 DDR_DIR_VECTS (res) = NULL;
1247 DDR_DIST_VECTS (res) = NULL;
1248
86a07404
IR		 1249 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1250 {
1251 struct subscript *subscript;
56cf8686 1252
5ed6ace5 1253 subscript = XNEW (struct subscript);
d93817c4
ZD		 1254 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
1255 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
86a07404
IR		 1256 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1257 SUB_DISTANCE (subscript) = chrec_dont_know;
ebf78a47 1258 VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
56cf8686 1259 }
ebf78a47 1260
56cf8686
SP		 1261 return res;
1262}
1263
d93817c4
ZD		 1264/* Frees memory used by the conflict function F. */
1265
1266static void
1267free_conflict_function (conflict_function *f)
1268{
1269 unsigned i;
1270
1271 if (CF_NONTRIVIAL_P (f))
1272 {
1273 for (i = 0; i < f->n; i++)
1274 affine_fn_free (f->fns[i]);
1275 }
1276 free (f);
1277}
1278
1279/* Frees memory used by SUBSCRIPTS. */
1280
1281static void
1282free_subscripts (VEC (subscript_p, heap) *subscripts)
1283{
1284 unsigned i;
1285 subscript_p s;
1286
1287 for (i = 0; VEC_iterate (subscript_p, subscripts, i, s); i++)
1288 {
1289 free_conflict_function (s->conflicting_iterations_in_a);
1290 free_conflict_function (s->conflicting_iterations_in_b);
1291 }
1292 VEC_free (subscript_p, heap, subscripts);
1293}
1294
56cf8686
SP		 1295/* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1296 description. */
1297
1298static inline void
1299finalize_ddr_dependent (struct data_dependence_relation *ddr,
1300 tree chrec)
1301{
36d59cf7
DB		 1302 if (dump_file && (dump_flags & TDF_DETAILS))
1303 {
1304 fprintf (dump_file, "(dependence classified: ");
1305 print_generic_expr (dump_file, chrec, 0);
1306 fprintf (dump_file, ")\n");
1307 }
1308
56cf8686 1309 DDR_ARE_DEPENDENT (ddr) = chrec;
d93817c4 1310 free_subscripts (DDR_SUBSCRIPTS (ddr));
56cf8686
SP		 1311}
1312
86df10e3
SP		 1313/* The dependence relation DDR cannot be represented by a distance
1314 vector. */
1315
1316static inline void
1317non_affine_dependence_relation (struct data_dependence_relation *ddr)
1318{
1319 if (dump_file && (dump_flags & TDF_DETAILS))
1320 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
1321
1322 DDR_AFFINE_P (ddr) = false;
1323}
1324
56cf8686
SP		 1325\f
1326
1327/* This section contains the classic Banerjee tests. */
1328
1329/* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1330 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1331
1332static inline bool
1333ziv_subscript_p (tree chrec_a,
1334 tree chrec_b)
1335{
1336 return (evolution_function_is_constant_p (chrec_a)
1337 && evolution_function_is_constant_p (chrec_b));
1338}
1339
1340/* Returns true iff CHREC_A and CHREC_B are dependent on an index
1341 variable, i.e., if the SIV (Single Index Variable) test is true. */
1342
1343static bool
1344siv_subscript_p (tree chrec_a,
1345 tree chrec_b)
1346{
1347 if ((evolution_function_is_constant_p (chrec_a)
1348 && evolution_function_is_univariate_p (chrec_b))
1349 || (evolution_function_is_constant_p (chrec_b)
1350 && evolution_function_is_univariate_p (chrec_a)))
1351 return true;
1352
1353 if (evolution_function_is_univariate_p (chrec_a)
1354 && evolution_function_is_univariate_p (chrec_b))
1355 {
1356 switch (TREE_CODE (chrec_a))
1357 {
1358 case POLYNOMIAL_CHREC:
1359 switch (TREE_CODE (chrec_b))
1360 {
1361 case POLYNOMIAL_CHREC:
1362 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
1363 return false;
1364
1365 default:
1366 return true;
1367 }
1368
1369 default:
1370 return true;
1371 }
1372 }
1373
1374 return false;
1375}
1376
d93817c4
ZD		 1377/* Creates a conflict function with N dimensions. The affine functions
1378 in each dimension follow. */
1379
1380static conflict_function *
1381conflict_fn (unsigned n, ...)
1382{
1383 unsigned i;
1384 conflict_function *ret = XCNEW (conflict_function);
1385 va_list ap;
1386
b39c6706 1387 gcc_assert (0 < n && n <= MAX_DIM);
d93817c4
ZD		 1388 va_start(ap, n);
1389
1390 ret->n = n;
1391 for (i = 0; i < n; i++)
1392 ret->fns[i] = va_arg (ap, affine_fn);
1393 va_end(ap);
1394
1395 return ret;
1396}
1397
1398/* Returns constant affine function with value CST. */
1399
1400static affine_fn
1401affine_fn_cst (tree cst)
1402{
1403 affine_fn fn = VEC_alloc (tree, heap, 1);
1404 VEC_quick_push (tree, fn, cst);
1405 return fn;
1406}
1407
1408/* Returns affine function with single variable, CST + COEF * x_DIM. */
1409
1410static affine_fn
1411affine_fn_univar (tree cst, unsigned dim, tree coef)
1412{
1413 affine_fn fn = VEC_alloc (tree, heap, dim + 1);
1414 unsigned i;
1415
1416 gcc_assert (dim > 0);
1417 VEC_quick_push (tree, fn, cst);
1418 for (i = 1; i < dim; i++)
1419 VEC_quick_push (tree, fn, integer_zero_node);
1420 VEC_quick_push (tree, fn, coef);
1421 return fn;
1422}
1423
56cf8686
SP		 1424/* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1425 *OVERLAPS_B are initialized to the functions that describe the
1426 relation between the elements accessed twice by CHREC_A and
1427 CHREC_B. For k >= 0, the following property is verified:
1428
1429 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1430
1431static void
1432analyze_ziv_subscript (tree chrec_a,
1433 tree chrec_b,
d93817c4
ZD		 1434 conflict_function **overlaps_a,
1435 conflict_function **overlaps_b,
86df10e3 1436 tree *last_conflicts)
56cf8686
SP		 1437{
1438 tree difference;
0ff4040e 1439 dependence_stats.num_ziv++;
56cf8686
SP		 1440
1441 if (dump_file && (dump_flags & TDF_DETAILS))
1442 fprintf (dump_file, "(analyze_ziv_subscript \n");
1443
e2157b49
SP		 1444 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
1445 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
56cf8686
SP		 1446 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
1447
1448 switch (TREE_CODE (difference))
1449 {
1450 case INTEGER_CST:
1451 if (integer_zerop (difference))
1452 {
1453 /* The difference is equal to zero: the accessed index
1454 overlaps for each iteration in the loop. */
d93817c4
ZD		 1455 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1456 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
86df10e3 1457 *last_conflicts = chrec_dont_know;
0ff4040e 1458 dependence_stats.num_ziv_dependent++;
56cf8686
SP		 1459 }
1460 else
1461 {
1462 /* The accesses do not overlap. */
d93817c4
ZD		 1463 *overlaps_a = conflict_fn_no_dependence ();
1464 *overlaps_b = conflict_fn_no_dependence ();
86df10e3 1465 *last_conflicts = integer_zero_node;
0ff4040e 1466 dependence_stats.num_ziv_independent++;
56cf8686
SP		 1467 }
1468 break;
1469
1470 default:
1471 /* We're not sure whether the indexes overlap. For the moment,
1472 conservatively answer "don't know". */
0ff4040e
SP		 1473 if (dump_file && (dump_flags & TDF_DETAILS))
1474 fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
1475
d93817c4
ZD		 1476 *overlaps_a = conflict_fn_not_known ();
1477 *overlaps_b = conflict_fn_not_known ();
86df10e3 1478 *last_conflicts = chrec_dont_know;
0ff4040e 1479 dependence_stats.num_ziv_unimplemented++;
56cf8686
SP		 1480 break;
1481 }
1482
1483 if (dump_file && (dump_flags & TDF_DETAILS))
1484 fprintf (dump_file, ")\n");
1485}
1486
4839cb59
ZD		 1487/* Sets NIT to the estimated number of executions of the statements in
1488 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
1489 large as the number of iterations. If we have no reliable estimate,
1490 the function returns false, otherwise returns true. */
416f403e 1491
ac84e05e 1492bool
4839cb59
ZD		 1493estimated_loop_iterations (struct loop *loop, bool conservative,
1494 double_int *nit)
416f403e 1495{
9bdb685e
ZD		 1496 estimate_numbers_of_iterations_loop (loop);
1497 if (conservative)
4839cb59 1498 {
9bdb685e
ZD		 1499 if (!loop->any_upper_bound)
1500 return false;
4839cb59 1501
9bdb685e 1502 *nit = loop->nb_iterations_upper_bound;
4839cb59 1503 }
9bdb685e 1504 else
946e1bc7 1505 {
9bdb685e
ZD		 1506 if (!loop->any_estimate)
1507 return false;
1508
1509 *nit = loop->nb_iterations_estimate;
946e1bc7
ZD		 1510 }
1511
9bdb685e 1512 return true;
4839cb59
ZD		 1513}
1514
1515/* Similar to estimated_loop_iterations, but returns the estimate only
1516 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1517 on the number of iterations of LOOP could not be derived, returns -1. */
1518
1519HOST_WIDE_INT
1520estimated_loop_iterations_int (struct loop *loop, bool conservative)
1521{
1522 double_int nit;
1523 HOST_WIDE_INT hwi_nit;
1524
1525 if (!estimated_loop_iterations (loop, conservative, &nit))
1526 return -1;
1527
1528 if (!double_int_fits_in_shwi_p (nit))
1529 return -1;
1530 hwi_nit = double_int_to_shwi (nit);
1531
1532 return hwi_nit < 0 ? -1 : hwi_nit;
416f403e
DB		 1533}
1534
4839cb59
ZD		 1535/* Similar to estimated_loop_iterations, but returns the estimate as a tree,
1536 and only if it fits to the int type. If this is not the case, or the
1537 estimate on the number of iterations of LOOP could not be derived, returns
1538 chrec_dont_know. */
1539
1540static tree
1541estimated_loop_iterations_tree (struct loop *loop, bool conservative)
1542{
1543 double_int nit;
1544 tree type;
1545
1546 if (!estimated_loop_iterations (loop, conservative, &nit))
1547 return chrec_dont_know;
1548
1549 type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
1550 if (!double_int_fits_to_tree_p (type, nit))
1551 return chrec_dont_know;
1552
1553 return double_int_to_tree (type, nit);
1554}
1555
56cf8686
SP		 1556/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1557 constant, and CHREC_B is an affine function. *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
1564static void
1565analyze_siv_subscript_cst_affine (tree chrec_a,
1566 tree chrec_b,
d93817c4
ZD		 1567 conflict_function **overlaps_a,
1568 conflict_function **overlaps_b,
86df10e3 1569 tree *last_conflicts)
56cf8686
SP		 1570{
1571 bool value0, value1, value2;
d93817c4 1572 tree difference, tmp;
e2157b49
SP		 1573
1574 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
1575 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
1576 difference = chrec_fold_minus
d91d2db7 1577 (integer_type_node, initial_condition (chrec_b), chrec_a);
56cf8686
SP		 1578
1579 if (!chrec_is_positive (initial_condition (difference), &value0))
1580 {
0ff4040e
SP		 1581 if (dump_file && (dump_flags & TDF_DETAILS))
1582 fprintf (dump_file, "siv test failed: chrec is not positive.\n");
1583
1584 dependence_stats.num_siv_unimplemented++;
d93817c4
ZD		 1585 *overlaps_a = conflict_fn_not_known ();
1586 *overlaps_b = conflict_fn_not_known ();
86df10e3 1587 *last_conflicts = chrec_dont_know;
56cf8686
SP		 1588 return;
1589 }
1590 else
1591 {
1592 if (value0 == false)
1593 {
1594 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
1595 {
0ff4040e
SP		 1596 if (dump_file && (dump_flags & TDF_DETAILS))
1597 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1598
d93817c4
ZD		 1599 *overlaps_a = conflict_fn_not_known ();
1600 *overlaps_b = conflict_fn_not_known ();
86df10e3 1601 *last_conflicts = chrec_dont_know;
0ff4040e 1602 dependence_stats.num_siv_unimplemented++;
56cf8686
SP		 1603 return;
1604 }
1605 else
1606 {
1607 if (value1 == true)
1608 {
1609 /* Example:
1610 chrec_a = 12
1611 chrec_b = {10, +, 1}
1612 */
1613
f457cf40 1614 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
56cf8686 1615 {
4839cb59
ZD		 1616 HOST_WIDE_INT numiter;
1617 struct loop *loop = get_chrec_loop (chrec_b);
416f403e 1618
d93817c4
ZD		 1619 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1620 tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
1621 fold_build1 (ABS_EXPR,
1622 integer_type_node,
1623 difference),
1624 CHREC_RIGHT (chrec_b));
1625 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
86df10e3 1626 *last_conflicts = integer_one_node;
416f403e
DB		 1627
1628
1629 /* Perform weak-zero siv test to see if overlap is
1630 outside the loop bounds. */
4839cb59 1631 numiter = estimated_loop_iterations_int (loop, true);
416f403e 1632
4839cb59
ZD		 1633 if (numiter >= 0
1634 && compare_tree_int (tmp, numiter) > 0)
416f403e 1635 {
d93817c4
ZD		 1636 free_conflict_function (*overlaps_a);
1637 free_conflict_function (*overlaps_b);
1638 *overlaps_a = conflict_fn_no_dependence ();
1639 *overlaps_b = conflict_fn_no_dependence ();
416f403e 1640 *last_conflicts = integer_zero_node;
0ff4040e 1641 dependence_stats.num_siv_independent++;
416f403e
DB		 1642 return;
1643 }
0ff4040e 1644 dependence_stats.num_siv_dependent++;
56cf8686
SP		 1645 return;
1646 }
1647
f457cf40 1648 /* When the step does not divide the difference, there are
56cf8686
SP		 1649 no overlaps. */
1650 else
1651 {
d93817c4
ZD		 1652 *overlaps_a = conflict_fn_no_dependence ();
1653 *overlaps_b = conflict_fn_no_dependence ();
86df10e3 1654 *last_conflicts = integer_zero_node;
0ff4040e 1655 dependence_stats.num_siv_independent++;
56cf8686
SP		 1656 return;
1657 }
1658 }
1659
1660 else
1661 {
1662 /* Example:
1663 chrec_a = 12
1664 chrec_b = {10, +, -1}
1665
1666 In this case, chrec_a will not overlap with chrec_b. */
d93817c4
ZD		 1667 *overlaps_a = conflict_fn_no_dependence ();
1668 *overlaps_b = conflict_fn_no_dependence ();
86df10e3 1669 *last_conflicts = integer_zero_node;
0ff4040e 1670 dependence_stats.num_siv_independent++;
56cf8686
SP		 1671 return;
1672 }
1673 }
1674 }
1675 else
1676 {
1677 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
1678 {
0ff4040e
SP		 1679 if (dump_file && (dump_flags & TDF_DETAILS))
1680 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1681
d93817c4
ZD		 1682 *overlaps_a = conflict_fn_not_known ();
1683 *overlaps_b = conflict_fn_not_known ();
86df10e3 1684 *last_conflicts = chrec_dont_know;
0ff4040e 1685 dependence_stats.num_siv_unimplemented++;
56cf8686
SP		 1686 return;
1687 }
1688 else
1689 {
1690 if (value2 == false)
1691 {
1692 /* Example:
1693 chrec_a = 3
1694 chrec_b = {10, +, -1}
1695 */
f457cf40 1696 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
56cf8686 1697 {
4839cb59
ZD		 1698 HOST_WIDE_INT numiter;
1699 struct loop *loop = get_chrec_loop (chrec_b);
416f403e 1700
d93817c4
ZD		 1701 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1702 tmp = fold_build2 (EXACT_DIV_EXPR,
1703 integer_type_node, difference,
1704 CHREC_RIGHT (chrec_b));
1705 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
86df10e3 1706 *last_conflicts = integer_one_node;
416f403e
DB		 1707
1708 /* Perform weak-zero siv test to see if overlap is
1709 outside the loop bounds. */
4839cb59 1710 numiter = estimated_loop_iterations_int (loop, true);
416f403e 1711
4839cb59
ZD		 1712 if (numiter >= 0
1713 && compare_tree_int (tmp, numiter) > 0)
416f403e 1714 {
d93817c4
ZD		 1715 free_conflict_function (*overlaps_a);
1716 free_conflict_function (*overlaps_b);
1717 *overlaps_a = conflict_fn_no_dependence ();
1718 *overlaps_b = conflict_fn_no_dependence ();
416f403e 1719 *last_conflicts = integer_zero_node;
0ff4040e 1720 dependence_stats.num_siv_independent++;
416f403e
DB		 1721 return;
1722 }
0ff4040e 1723 dependence_stats.num_siv_dependent++;
56cf8686
SP		 1724 return;
1725 }
1726
4286d8ce 1727 /* When the step does not divide the difference, there
56cf8686
SP		 1728 are no overlaps. */
1729 else
1730 {
d93817c4
ZD		 1731 *overlaps_a = conflict_fn_no_dependence ();
1732 *overlaps_b = conflict_fn_no_dependence ();
86df10e3 1733 *last_conflicts = integer_zero_node;
0ff4040e 1734 dependence_stats.num_siv_independent++;
56cf8686
SP		 1735 return;
1736 }
1737 }
1738 else
1739 {
1740 /* Example:
1741 chrec_a = 3
1742 chrec_b = {4, +, 1}
1743
1744 In this case, chrec_a will not overlap with chrec_b. */
d93817c4
ZD		 1745 *overlaps_a = conflict_fn_no_dependence ();
1746 *overlaps_b = conflict_fn_no_dependence ();
86df10e3 1747 *last_conflicts = integer_zero_node;
0ff4040e 1748 dependence_stats.num_siv_independent++;
56cf8686
SP		 1749 return;
1750 }
1751 }
1752 }
1753 }
1754}
1755
50300b4c 1756/* Helper recursive function for initializing the matrix A. Returns
86df10e3 1757 the initial value of CHREC. */
56cf8686 1758
86df10e3
SP		 1759static int
1760initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
1761{
1762 gcc_assert (chrec);
1763
1764 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1765 return int_cst_value (chrec);
1766
1767 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
1768 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
1769}
1770
1771#define FLOOR_DIV(x,y) ((x) / (y))
1772
1773/* Solves the special case of the Diophantine equation:
1774 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1775
1776 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1777 number of iterations that loops X and Y run. The overlaps will be
1778 constructed as evolutions in dimension DIM. */
56cf8686
SP		 1779
1780static void
86df10e3 1781compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
d93817c4
ZD		 1782 affine_fn *overlaps_a,
1783 affine_fn *overlaps_b,
86df10e3
SP		 1784 tree *last_conflicts, int dim)
1785{
1786 if (((step_a > 0 && step_b > 0)
1787 || (step_a < 0 && step_b < 0)))
1788 {
1789 int step_overlaps_a, step_overlaps_b;
1790 int gcd_steps_a_b, last_conflict, tau2;
1791
1792 gcd_steps_a_b = gcd (step_a, step_b);
1793 step_overlaps_a = step_b / gcd_steps_a_b;
1794 step_overlaps_b = step_a / gcd_steps_a_b;
1795
1796 tau2 = FLOOR_DIV (niter, step_overlaps_a);
1797 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
1798 last_conflict = tau2;
1799
d93817c4
ZD		 1800 *overlaps_a = affine_fn_univar (integer_zero_node, dim,
1801 build_int_cst (NULL_TREE,
1802 step_overlaps_a));
1803 *overlaps_b = affine_fn_univar (integer_zero_node, dim,
1804 build_int_cst (NULL_TREE,
1805 step_overlaps_b));
86df10e3
SP		 1806 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
1807 }
1808
1809 else
1810 {
d93817c4
ZD		 1811 *overlaps_a = affine_fn_cst (integer_zero_node);
1812 *overlaps_b = affine_fn_cst (integer_zero_node);
86df10e3
SP		 1813 *last_conflicts = integer_zero_node;
1814 }
1815}
1816
86df10e3
SP		 1817/* Solves the special case of a Diophantine equation where CHREC_A is
1818 an affine bivariate function, and CHREC_B is an affine univariate
1819 function. For example,
1820
1821 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1822
1823 has the following overlapping functions:
1824
1825 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1826 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1827 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1828
35fd3193 1829 FORNOW: This is a specialized implementation for a case occurring in
86df10e3
SP		 1830 a common benchmark. Implement the general algorithm. */
1831
1832static void
1833compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
d93817c4
ZD		 1834 conflict_function **overlaps_a,
1835 conflict_function **overlaps_b,
86df10e3 1836 tree *last_conflicts)
56cf8686 1837{
86df10e3
SP		 1838 bool xz_p, yz_p, xyz_p;
1839 int step_x, step_y, step_z;
4839cb59 1840 HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
d93817c4
ZD		 1841 affine_fn overlaps_a_xz, overlaps_b_xz;
1842 affine_fn overlaps_a_yz, overlaps_b_yz;
1843 affine_fn overlaps_a_xyz, overlaps_b_xyz;
1844 affine_fn ova1, ova2, ovb;
1845 tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
86df10e3
SP		 1846
1847 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
1848 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
1849 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
1850
4839cb59
ZD		 1851 niter_x = estimated_loop_iterations_int
1852 (get_chrec_loop (CHREC_LEFT (chrec_a)), true);
1853 niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), true);
1854 niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), true);
416f403e 1855
4839cb59 1856 if (niter_x < 0 || niter_y < 0 || niter_z < 0)
86df10e3 1857 {
0ff4040e
SP		 1858 if (dump_file && (dump_flags & TDF_DETAILS))
1859 fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
1860
d93817c4
ZD		 1861 *overlaps_a = conflict_fn_not_known ();
1862 *overlaps_b = conflict_fn_not_known ();
86df10e3
SP		 1863 *last_conflicts = chrec_dont_know;
1864 return;
1865 }
1866
86df10e3
SP		 1867 niter = MIN (niter_x, niter_z);
1868 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
1869 &overlaps_a_xz,
1870 &overlaps_b_xz,
1871 &last_conflicts_xz, 1);
1872 niter = MIN (niter_y, niter_z);
1873 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
1874 &overlaps_a_yz,
1875 &overlaps_b_yz,
1876 &last_conflicts_yz, 2);
1877 niter = MIN (niter_x, niter_z);
1878 niter = MIN (niter_y, niter);
1879 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
1880 &overlaps_a_xyz,
1881 &overlaps_b_xyz,
1882 &last_conflicts_xyz, 3);
1883
1884 xz_p = !integer_zerop (last_conflicts_xz);
1885 yz_p = !integer_zerop (last_conflicts_yz);
1886 xyz_p = !integer_zerop (last_conflicts_xyz);
1887
1888 if (xz_p || yz_p || xyz_p)
1889 {
d93817c4
ZD		 1890 ova1 = affine_fn_cst (integer_zero_node);
1891 ova2 = affine_fn_cst (integer_zero_node);
1892 ovb = affine_fn_cst (integer_zero_node);
86df10e3
SP		 1893 if (xz_p)
1894 {
d93817c4
ZD		 1895 affine_fn t0 = ova1;
1896 affine_fn t2 = ovb;
1897
1898 ova1 = affine_fn_plus (ova1, overlaps_a_xz);
1899 ovb = affine_fn_plus (ovb, overlaps_b_xz);
1900 affine_fn_free (t0);
1901 affine_fn_free (t2);
86df10e3
SP		 1902 *last_conflicts = last_conflicts_xz;
1903 }
1904 if (yz_p)
1905 {
d93817c4
ZD		 1906 affine_fn t0 = ova2;
1907 affine_fn t2 = ovb;
1908
1909 ova2 = affine_fn_plus (ova2, overlaps_a_yz);
1910 ovb = affine_fn_plus (ovb, overlaps_b_yz);
1911 affine_fn_free (t0);
1912 affine_fn_free (t2);
86df10e3
SP		 1913 *last_conflicts = last_conflicts_yz;
1914 }
1915 if (xyz_p)
1916 {
d93817c4
ZD		 1917 affine_fn t0 = ova1;
1918 affine_fn t2 = ova2;
1919 affine_fn t4 = ovb;
1920
1921 ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
1922 ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
1923 ovb = affine_fn_plus (ovb, overlaps_b_xyz);
1924 affine_fn_free (t0);
1925 affine_fn_free (t2);
1926 affine_fn_free (t4);
86df10e3
SP		 1927 *last_conflicts = last_conflicts_xyz;
1928 }
d93817c4
ZD		 1929 *overlaps_a = conflict_fn (2, ova1, ova2);
1930 *overlaps_b = conflict_fn (1, ovb);
86df10e3
SP		 1931 }
1932 else
1933 {
d93817c4
ZD		 1934 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1935 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
86df10e3
SP		 1936 *last_conflicts = integer_zero_node;
1937 }
d93817c4
ZD		 1938
1939 affine_fn_free (overlaps_a_xz);
1940 affine_fn_free (overlaps_b_xz);
1941 affine_fn_free (overlaps_a_yz);
1942 affine_fn_free (overlaps_b_yz);
1943 affine_fn_free (overlaps_a_xyz);
1944 affine_fn_free (overlaps_b_xyz);
56cf8686
SP		 1945}
1946
1947/* Determines the overlapping elements due to accesses CHREC_A and
0ff4040e
SP		 1948 CHREC_B, that are affine functions. This function cannot handle
1949 symbolic evolution functions, ie. when initial conditions are
1950 parameters, because it uses lambda matrices of integers. */
56cf8686
SP		 1951
1952static void
1953analyze_subscript_affine_affine (tree chrec_a,
1954 tree chrec_b,
d93817c4
ZD		 1955 conflict_function **overlaps_a,
1956 conflict_function **overlaps_b,
86df10e3 1957 tree *last_conflicts)
56cf8686 1958{
86df10e3
SP		 1959 unsigned nb_vars_a, nb_vars_b, dim;
1960 int init_a, init_b, gamma, gcd_alpha_beta;
1961 int tau1, tau2;
1962 lambda_matrix A, U, S;
1963
e2157b49 1964 if (eq_evolutions_p (chrec_a, chrec_b))
416f403e 1965 {
e2157b49
SP		 1966 /* The accessed index overlaps for each iteration in the
1967 loop. */
d93817c4
ZD		 1968 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1969 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
416f403e
DB		 1970 *last_conflicts = chrec_dont_know;
1971 return;
1972 }
56cf8686
SP		 1973 if (dump_file && (dump_flags & TDF_DETAILS))
1974 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
1975
1976 /* For determining the initial intersection, we have to solve a
1977 Diophantine equation. This is the most time consuming part.
1978
1979 For answering to the question: "Is there a dependence?" we have
1980 to prove that there exists a solution to the Diophantine
1981 equation, and that the solution is in the iteration domain,
89dbed81 1982 i.e. the solution is positive or zero, and that the solution
56cf8686
SP		 1983 happens before the upper bound loop.nb_iterations. Otherwise
1984 there is no dependence. This function outputs a description of
1985 the iterations that hold the intersections. */
1986
86df10e3
SP		 1987 nb_vars_a = nb_vars_in_chrec (chrec_a);
1988 nb_vars_b = nb_vars_in_chrec (chrec_b);
1989
1990 dim = nb_vars_a + nb_vars_b;
1991 U = lambda_matrix_new (dim, dim);
1992 A = lambda_matrix_new (dim, 1);
1993 S = lambda_matrix_new (dim, 1);
1994
1995 init_a = initialize_matrix_A (A, chrec_a, 0, 1);
1996 init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
1997 gamma = init_b - init_a;
1998
1999 /* Don't do all the hard work of solving the Diophantine equation
2000 when we already know the solution: for example,
2001 | {3, +, 1}_1
2002 | {3, +, 4}_2
2003 | gamma = 3 - 3 = 0.
2004 Then the first overlap occurs during the first iterations:
2005 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2006 */
2007 if (gamma == 0)
56cf8686 2008 {
86df10e3 2009 if (nb_vars_a == 1 && nb_vars_b == 1)
56cf8686 2010 {
86df10e3 2011 int step_a, step_b;
4839cb59 2012 HOST_WIDE_INT niter, niter_a, niter_b;
d93817c4 2013 affine_fn ova, ovb;
86df10e3 2014
4839cb59
ZD		 2015 niter_a = estimated_loop_iterations_int
2016 (get_chrec_loop (chrec_a), true);
2017 niter_b = estimated_loop_iterations_int
2018 (get_chrec_loop (chrec_b), true);
2019 if (niter_a < 0 || niter_b < 0)
86df10e3 2020 {
0ff4040e
SP		 2021 if (dump_file && (dump_flags & TDF_DETAILS))
2022 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
d93817c4
ZD		 2023 *overlaps_a = conflict_fn_not_known ();
2024 *overlaps_b = conflict_fn_not_known ();
86df10e3 2025 *last_conflicts = chrec_dont_know;
0ff4040e 2026 goto end_analyze_subs_aa;
86df10e3
SP		 2027 }
2028
86df10e3
SP		 2029 niter = MIN (niter_a, niter_b);
2030
2031 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2032 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2033
2034 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
d93817c4 2035 &ova, &ovb,
86df10e3 2036 last_conflicts, 1);
d93817c4
ZD		 2037 *overlaps_a = conflict_fn (1, ova);
2038 *overlaps_b = conflict_fn (1, ovb);
56cf8686 2039 }
86df10e3
SP		 2040
2041 else if (nb_vars_a == 2 && nb_vars_b == 1)
2042 compute_overlap_steps_for_affine_1_2
2043 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2044
2045 else if (nb_vars_a == 1 && nb_vars_b == 2)
2046 compute_overlap_steps_for_affine_1_2
2047 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2048
2049 else
56cf8686 2050 {
0ff4040e
SP		 2051 if (dump_file && (dump_flags & TDF_DETAILS))
2052 fprintf (dump_file, "affine-affine test failed: too many variables.\n");
d93817c4
ZD		 2053 *overlaps_a = conflict_fn_not_known ();
2054 *overlaps_b = conflict_fn_not_known ();
86df10e3 2055 *last_conflicts = chrec_dont_know;
56cf8686 2056 }
0ff4040e 2057 goto end_analyze_subs_aa;
86df10e3
SP		 2058 }
2059
2060 /* U.A = S */
2061 lambda_matrix_right_hermite (A, dim, 1, S, U);
2062
2063 if (S[0][0] < 0)
2064 {
2065 S[0][0] *= -1;
2066 lambda_matrix_row_negate (U, dim, 0);
2067 }
2068 gcd_alpha_beta = S[0][0];
2069
ba42e045
SP		 2070 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2071 but that is a quite strange case. Instead of ICEing, answer
2072 don't know. */
2073 if (gcd_alpha_beta == 0)
2074 {
d93817c4
ZD		 2075 *overlaps_a = conflict_fn_not_known ();
2076 *overlaps_b = conflict_fn_not_known ();
ba42e045
SP		 2077 *last_conflicts = chrec_dont_know;
2078 goto end_analyze_subs_aa;
2079 }
2080
86df10e3
SP		 2081 /* The classic "gcd-test". */
2082 if (!int_divides_p (gcd_alpha_beta, gamma))
2083 {
2084 /* The "gcd-test" has determined that there is no integer
2085 solution, i.e. there is no dependence. */
d93817c4
ZD		 2086 *overlaps_a = conflict_fn_no_dependence ();
2087 *overlaps_b = conflict_fn_no_dependence ();
86df10e3
SP		 2088 *last_conflicts = integer_zero_node;
2089 }
2090
2091 /* Both access functions are univariate. This includes SIV and MIV cases. */
2092 else if (nb_vars_a == 1 && nb_vars_b == 1)
2093 {
2094 /* Both functions should have the same evolution sign. */
2095 if (((A[0][0] > 0 && -A[1][0] > 0)
2096 || (A[0][0] < 0 && -A[1][0] < 0)))
56cf8686
SP		 2097 {
2098 /* The solutions are given by:
2099 |
86df10e3
SP		 2100 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2101 | [u21 u22] [y0]
2102
56cf8686 2103 For a given integer t. Using the following variables,
86df10e3 2104
56cf8686
SP		 2105 | i0 = u11 * gamma / gcd_alpha_beta
2106 | j0 = u12 * gamma / gcd_alpha_beta
2107 | i1 = u21
2108 | j1 = u22
86df10e3 2109
56cf8686 2110 the solutions are:
86df10e3
SP		 2111
2112 | x0 = i0 + i1 * t,
2113 | y0 = j0 + j1 * t. */
2114
2115 int i0, j0, i1, j1;
2116
56cf8686
SP		 2117 /* X0 and Y0 are the first iterations for which there is a
2118 dependence. X0, Y0 are two solutions of the Diophantine
2119 equation: chrec_a (X0) = chrec_b (Y0). */
86df10e3
SP		 2120 int x0, y0;
2121 int niter, niter_a, niter_b;
86df10e3 2122
4839cb59
ZD		 2123 niter_a = estimated_loop_iterations_int
2124 (get_chrec_loop (chrec_a), true);
2125 niter_b = estimated_loop_iterations_int
2126 (get_chrec_loop (chrec_b), true);
416f403e 2127
4839cb59 2128 if (niter_a < 0 || niter_b < 0)
86df10e3 2129 {
0ff4040e
SP		 2130 if (dump_file && (dump_flags & TDF_DETAILS))
2131 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
d93817c4
ZD		 2132 *overlaps_a = conflict_fn_not_known ();
2133 *overlaps_b = conflict_fn_not_known ();
86df10e3 2134 *last_conflicts = chrec_dont_know;
0ff4040e 2135 goto end_analyze_subs_aa;
86df10e3
SP		 2136 }
2137
86df10e3
SP		 2138 niter = MIN (niter_a, niter_b);
2139
2140 i0 = U[0][0] * gamma / gcd_alpha_beta;
2141 j0 = U[0][1] * gamma / gcd_alpha_beta;
2142 i1 = U[1][0];
2143 j1 = U[1][1];
2144
2145 if ((i1 == 0 && i0 < 0)
2146 || (j1 == 0 && j0 < 0))
56cf8686
SP		 2147 {
2148 /* There is no solution.
2149 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2150 falls in here, but for the moment we don't look at the
2151 upper bound of the iteration domain. */
d93817c4
ZD		 2152 *overlaps_a = conflict_fn_no_dependence ();
2153 *overlaps_b = conflict_fn_no_dependence ();
86df10e3
SP		 2154 *last_conflicts = integer_zero_node;
2155 }
2156
56cf8686
SP		 2157 else
2158 {
86df10e3 2159 if (i1 > 0)
56cf8686 2160 {
86df10e3
SP		 2161 tau1 = CEIL (-i0, i1);
2162 tau2 = FLOOR_DIV (niter - i0, i1);
2163
2164 if (j1 > 0)
56cf8686 2165 {
9ba64a4a 2166 int last_conflict, min_multiple;
86df10e3
SP		 2167 tau1 = MAX (tau1, CEIL (-j0, j1));
2168 tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
2169
9ba64a4a
SP		 2170 x0 = i1 * tau1 + i0;
2171 y0 = j1 * tau1 + j0;
2172
2173 /* At this point (x0, y0) is one of the
2174 solutions to the Diophantine equation. The
2175 next step has to compute the smallest
2176 positive solution: the first conflicts. */
2177 min_multiple = MIN (x0 / i1, y0 / j1);
2178 x0 -= i1 * min_multiple;
2179 y0 -= j1 * min_multiple;
2180
86df10e3
SP		 2181 tau1 = (x0 - i0)/i1;
2182 last_conflict = tau2 - tau1;
2183
416f403e
DB		 2184 /* If the overlap occurs outside of the bounds of the
2185 loop, there is no dependence. */
2186 if (x0 > niter || y0 > niter)
416f403e 2187 {
d93817c4
ZD		 2188 *overlaps_a = conflict_fn_no_dependence ();
2189 *overlaps_b = conflict_fn_no_dependence ();
416f403e
DB		 2190 *last_conflicts = integer_zero_node;
2191 }
2192 else
2193 {
d93817c4
ZD		 2194 *overlaps_a
2195 = conflict_fn (1,
2196 affine_fn_univar (build_int_cst (NULL_TREE, x0),
2197 1,
2198 build_int_cst (NULL_TREE, i1)));
2199 *overlaps_b
2200 = conflict_fn (1,
2201 affine_fn_univar (build_int_cst (NULL_TREE, y0),
2202 1,
2203 build_int_cst (NULL_TREE, j1)));
416f403e
DB		 2204 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2205 }
56cf8686
SP		 2206 }
2207 else
2208 {
2209 /* FIXME: For the moment, the upper bound of the
471854f8 2210 iteration domain for j is not checked. */
0ff4040e
SP		 2211 if (dump_file && (dump_flags & TDF_DETAILS))
2212 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
d93817c4
ZD		 2213 *overlaps_a = conflict_fn_not_known ();
2214 *overlaps_b = conflict_fn_not_known ();
86df10e3 2215 *last_conflicts = chrec_dont_know;
56cf8686
SP		 2216 }
2217 }
86df10e3 2218
56cf8686
SP		 2219 else
2220 {
2221 /* FIXME: For the moment, the upper bound of the
471854f8 2222 iteration domain for i is not checked. */
0ff4040e
SP		 2223 if (dump_file && (dump_flags & TDF_DETAILS))
2224 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
d93817c4
ZD		 2225 *overlaps_a = conflict_fn_not_known ();
2226 *overlaps_b = conflict_fn_not_known ();
86df10e3 2227 *last_conflicts = chrec_dont_know;
56cf8686
SP		 2228 }
2229 }
2230 }
86df10e3
SP		 2231 else
2232 {
0ff4040e
SP		 2233 if (dump_file && (dump_flags & TDF_DETAILS))
2234 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
d93817c4
ZD		 2235 *overlaps_a = conflict_fn_not_known ();
2236 *overlaps_b = conflict_fn_not_known ();
86df10e3
SP		 2237 *last_conflicts = chrec_dont_know;
2238 }
56cf8686 2239 }
86df10e3 2240
56cf8686
SP		 2241 else
2242 {
0ff4040e
SP		 2243 if (dump_file && (dump_flags & TDF_DETAILS))
2244 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
d93817c4
ZD		 2245 *overlaps_a = conflict_fn_not_known ();
2246 *overlaps_b = conflict_fn_not_known ();
86df10e3 2247 *last_conflicts = chrec_dont_know;
56cf8686 2248 }
86df10e3 2249
0ff4040e 2250end_analyze_subs_aa:
56cf8686
SP		 2251 if (dump_file && (dump_flags & TDF_DETAILS))
2252 {
2253 fprintf (dump_file, " (overlaps_a = ");
d93817c4 2254 dump_conflict_function (dump_file, *overlaps_a);
56cf8686 2255 fprintf (dump_file, ")\n (overlaps_b = ");
d93817c4 2256 dump_conflict_function (dump_file, *overlaps_b);
56cf8686 2257 fprintf (dump_file, ")\n");
0ff4040e 2258 fprintf (dump_file, ")\n");
56cf8686 2259 }
0ff4040e
SP		 2260}
2261
2262/* Returns true when analyze_subscript_affine_affine can be used for
2263 determining the dependence relation between chrec_a and chrec_b,
2264 that contain symbols. This function modifies chrec_a and chrec_b
2265 such that the analysis result is the same, and such that they don't
2266 contain symbols, and then can safely be passed to the analyzer.
2267
2268 Example: The analysis of the following tuples of evolutions produce
2269 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2270 vs. {0, +, 1}_1
2271
2272 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2273 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2274*/
2275
2276static bool
2277can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
2278{
16a2acea 2279 tree diff, type, left_a, left_b, right_b;
0ff4040e
SP		 2280
2281 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
2282 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
2283 /* FIXME: For the moment not handled. Might be refined later. */
2284 return false;
2285
16a2acea
SP		 2286 type = chrec_type (*chrec_a);
2287 left_a = CHREC_LEFT (*chrec_a);
2288 left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE);
2289 diff = chrec_fold_minus (type, left_a, left_b);
2290
0ff4040e
SP		 2291 if (!evolution_function_is_constant_p (diff))
2292 return false;
2293
56cf8686 2294 if (dump_file && (dump_flags & TDF_DETAILS))
0ff4040e
SP		 2295 fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
2296
2297 *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
2298 diff, CHREC_RIGHT (*chrec_a));
16a2acea 2299 right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE);
0ff4040e 2300 *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
dc61cc6b 2301 build_int_cst (type, 0),
16a2acea 2302 right_b);
0ff4040e 2303 return true;
56cf8686
SP		 2304}
2305
2306/* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2307 *OVERLAPS_B are initialized to the functions that describe the
2308 relation between the elements accessed twice by CHREC_A and
2309 CHREC_B. For k >= 0, the following property is verified:
2310
2311 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2312
2313static void
2314analyze_siv_subscript (tree chrec_a,
2315 tree chrec_b,
d93817c4
ZD		 2316 conflict_function **overlaps_a,
2317 conflict_function **overlaps_b,
86df10e3 2318 tree *last_conflicts)
56cf8686 2319{
0ff4040e
SP		 2320 dependence_stats.num_siv++;
2321
56cf8686
SP		 2322 if (dump_file && (dump_flags & TDF_DETAILS))
2323 fprintf (dump_file, "(analyze_siv_subscript \n");
2324
2325 if (evolution_function_is_constant_p (chrec_a)
2326 && evolution_function_is_affine_p (chrec_b))
2327 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
86df10e3 2328 overlaps_a, overlaps_b, last_conflicts);
56cf8686
SP		 2329
2330 else if (evolution_function_is_affine_p (chrec_a)
2331 && evolution_function_is_constant_p (chrec_b))
86df10e3
SP		 2332 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2333 overlaps_b, overlaps_a, last_conflicts);
56cf8686
SP		 2334
2335 else if (evolution_function_is_affine_p (chrec_a)
86df10e3 2336 && evolution_function_is_affine_p (chrec_b))
0ff4040e
SP		 2337 {
2338 if (!chrec_contains_symbols (chrec_a)
2339 && !chrec_contains_symbols (chrec_b))
2340 {
2341 analyze_subscript_affine_affine (chrec_a, chrec_b,
2342 overlaps_a, overlaps_b,
2343 last_conflicts);
2344
d93817c4
ZD		 2345 if (CF_NOT_KNOWN_P (*overlaps_a)
2346 || CF_NOT_KNOWN_P (*overlaps_b))
0ff4040e 2347 dependence_stats.num_siv_unimplemented++;
d93817c4
ZD		 2348 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2349 || CF_NO_DEPENDENCE_P (*overlaps_b))
0ff4040e
SP		 2350 dependence_stats.num_siv_independent++;
2351 else
2352 dependence_stats.num_siv_dependent++;
2353 }
2354 else if (can_use_analyze_subscript_affine_affine (&chrec_a,
2355 &chrec_b))
2356 {
2357 analyze_subscript_affine_affine (chrec_a, chrec_b,
2358 overlaps_a, overlaps_b,
2359 last_conflicts);
2360 /* FIXME: The number of iterations is a symbolic expression.
2361 Compute it properly. */
2362 *last_conflicts = chrec_dont_know;
2363
d93817c4
ZD		 2364 if (CF_NOT_KNOWN_P (*overlaps_a)
2365 || CF_NOT_KNOWN_P (*overlaps_b))
0ff4040e 2366 dependence_stats.num_siv_unimplemented++;
d93817c4
ZD		 2367 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2368 || CF_NO_DEPENDENCE_P (*overlaps_b))
0ff4040e
SP		 2369 dependence_stats.num_siv_independent++;
2370 else
2371 dependence_stats.num_siv_dependent++;
2372 }
2373 else
2374 goto siv_subscript_dontknow;
2375 }
2376
56cf8686
SP		 2377 else
2378 {
0ff4040e
SP		 2379 siv_subscript_dontknow:;
2380 if (dump_file && (dump_flags & TDF_DETAILS))
2381 fprintf (dump_file, "siv test failed: unimplemented.\n");
d93817c4
ZD		 2382 *overlaps_a = conflict_fn_not_known ();
2383 *overlaps_b = conflict_fn_not_known ();
86df10e3 2384 *last_conflicts = chrec_dont_know;
0ff4040e 2385 dependence_stats.num_siv_unimplemented++;
56cf8686
SP		 2386 }
2387
2388 if (dump_file && (dump_flags & TDF_DETAILS))
2389 fprintf (dump_file, ")\n");
2390}
2391
55a700ac
ZD		 2392/* Returns false if we can prove that the greatest common divisor of the steps
2393 of CHREC does not divide CST, false otherwise. */
56cf8686
SP		 2394
2395static bool
55a700ac 2396gcd_of_steps_may_divide_p (tree chrec, tree cst)
56cf8686 2397{
55a700ac
ZD		 2398 HOST_WIDE_INT cd = 0, val;
2399 tree step;
0ff4040e 2400
55a700ac
ZD		 2401 if (!host_integerp (cst, 0))
2402 return true;
2403 val = tree_low_cst (cst, 0);
2404
2405 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
2406 {
2407 step = CHREC_RIGHT (chrec);
2408 if (!host_integerp (step, 0))
2409 return true;
2410 cd = gcd (cd, tree_low_cst (step, 0));
2411 chrec = CHREC_LEFT (chrec);
56cf8686 2412 }
55a700ac
ZD		 2413
2414 return val % cd == 0;
56cf8686
SP		 2415}
2416
2417/* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
2418 *OVERLAPS_B are initialized to the functions that describe the
2419 relation between the elements accessed twice by CHREC_A and
2420 CHREC_B. For k >= 0, the following property is verified:
2421
2422 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2423
2424static void
2425analyze_miv_subscript (tree chrec_a,
2426 tree chrec_b,
d93817c4
ZD		 2427 conflict_function **overlaps_a,
2428 conflict_function **overlaps_b,
86df10e3 2429 tree *last_conflicts)
56cf8686
SP		 2430{
2431 /* FIXME: This is a MIV subscript, not yet handled.
2432 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2433 (A[i] vs. A[j]).
2434
2435 In the SIV test we had to solve a Diophantine equation with two
2436 variables. In the MIV case we have to solve a Diophantine
2437 equation with 2*n variables (if the subscript uses n IVs).
2438 */
2439 tree difference;
0ff4040e 2440 dependence_stats.num_miv++;
56cf8686
SP		 2441 if (dump_file && (dump_flags & TDF_DETAILS))
2442 fprintf (dump_file, "(analyze_miv_subscript \n");
e2157b49
SP		 2443
2444 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
2445 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
56cf8686
SP		 2446 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2447
e2157b49 2448 if (eq_evolutions_p (chrec_a, chrec_b))
56cf8686
SP		 2449 {
2450 /* Access functions are the same: all the elements are accessed
2451 in the same order. */
d93817c4
ZD		 2452 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2453 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
4839cb59
ZD		 2454 *last_conflicts = estimated_loop_iterations_tree
2455 (get_chrec_loop (chrec_a), true);
0ff4040e 2456 dependence_stats.num_miv_dependent++;
56cf8686
SP		 2457 }
2458
2459 else if (evolution_function_is_constant_p (difference)
2460 /* For the moment, the following is verified:
a50411de 2461 evolution_function_is_affine_multivariate_p (chrec_a, 0) */
55a700ac 2462 && !gcd_of_steps_may_divide_p (chrec_a, difference))
56cf8686
SP		 2463 {
2464 /* testsuite/.../ssa-chrec-33.c
2465 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
0ff4040e 2466
55a700ac
ZD		 2467 The difference is 1, and all the evolution steps are multiples
2468 of 2, consequently there are no overlapping elements. */
d93817c4
ZD		 2469 *overlaps_a = conflict_fn_no_dependence ();
2470 *overlaps_b = conflict_fn_no_dependence ();
86df10e3 2471 *last_conflicts = integer_zero_node;
0ff4040e 2472 dependence_stats.num_miv_independent++;
56cf8686
SP		 2473 }
2474
a50411de 2475 else if (evolution_function_is_affine_multivariate_p (chrec_a, 0)
0ff4040e 2476 && !chrec_contains_symbols (chrec_a)
a50411de 2477 && evolution_function_is_affine_multivariate_p (chrec_b, 0)
0ff4040e 2478 && !chrec_contains_symbols (chrec_b))
56cf8686
SP		 2479 {
2480 /* testsuite/.../ssa-chrec-35.c
2481 {0, +, 1}_2 vs. {0, +, 1}_3
2482 the overlapping elements are respectively located at iterations:
86df10e3
SP		 2483 {0, +, 1}_x and {0, +, 1}_x,
2484 in other words, we have the equality:
2485 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2486
2487 Other examples:
2488 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2489 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2490
2491 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2492 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
56cf8686 2493 */
86df10e3
SP		 2494 analyze_subscript_affine_affine (chrec_a, chrec_b,
2495 overlaps_a, overlaps_b, last_conflicts);
0ff4040e 2496
d93817c4
ZD		 2497 if (CF_NOT_KNOWN_P (*overlaps_a)
2498 || CF_NOT_KNOWN_P (*overlaps_b))
0ff4040e 2499 dependence_stats.num_miv_unimplemented++;
d93817c4
ZD		 2500 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2501 || CF_NO_DEPENDENCE_P (*overlaps_b))
0ff4040e
SP		 2502 dependence_stats.num_miv_independent++;
2503 else
2504 dependence_stats.num_miv_dependent++;
56cf8686
SP		 2505 }
2506
2507 else
2508 {
2509 /* When the analysis is too difficult, answer "don't know". */
0ff4040e
SP		 2510 if (dump_file && (dump_flags & TDF_DETAILS))
2511 fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
2512
d93817c4
ZD		 2513 *overlaps_a = conflict_fn_not_known ();
2514 *overlaps_b = conflict_fn_not_known ();
86df10e3 2515 *last_conflicts = chrec_dont_know;
0ff4040e 2516 dependence_stats.num_miv_unimplemented++;
56cf8686
SP		 2517 }
2518
2519 if (dump_file && (dump_flags & TDF_DETAILS))
2520 fprintf (dump_file, ")\n");
2521}
2522
2523/* Determines the iterations for which CHREC_A is equal to CHREC_B.
2524 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
2525 two functions that describe the iterations that contain conflicting
2526 elements.
2527
2528 Remark: For an integer k >= 0, the following equality is true:
2529
2530 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2531*/
2532
2533static void
2534analyze_overlapping_iterations (tree chrec_a,
2535 tree chrec_b,
d93817c4
ZD		 2536 conflict_function **overlap_iterations_a,
2537 conflict_function **overlap_iterations_b,
86df10e3 2538 tree *last_conflicts)
56cf8686 2539{
0ff4040e
SP		 2540 dependence_stats.num_subscript_tests++;
2541
56cf8686
SP		 2542 if (dump_file && (dump_flags & TDF_DETAILS))
2543 {
2544 fprintf (dump_file, "(analyze_overlapping_iterations \n");
2545 fprintf (dump_file, " (chrec_a = ");
2546 print_generic_expr (dump_file, chrec_a, 0);
0ff4040e 2547 fprintf (dump_file, ")\n (chrec_b = ");
56cf8686
SP		 2548 print_generic_expr (dump_file, chrec_b, 0);
2549 fprintf (dump_file, ")\n");
2550 }
0ff4040e 2551
56cf8686
SP		 2552 if (chrec_a == NULL_TREE
2553 || chrec_b == NULL_TREE
2554 || chrec_contains_undetermined (chrec_a)
0ff4040e 2555 || chrec_contains_undetermined (chrec_b))
56cf8686 2556 {
0ff4040e
SP		 2557 dependence_stats.num_subscript_undetermined++;
2558
d93817c4
ZD		 2559 *overlap_iterations_a = conflict_fn_not_known ();
2560 *overlap_iterations_b = conflict_fn_not_known ();
56cf8686 2561 }
0ff4040e
SP		 2562
2563 /* If they are the same chrec, and are affine, they overlap
2564 on every iteration. */
2565 else if (eq_evolutions_p (chrec_a, chrec_b)
a50411de 2566 && evolution_function_is_affine_multivariate_p (chrec_a, 0))
0ff4040e
SP		 2567 {
2568 dependence_stats.num_same_subscript_function++;
d93817c4
ZD		 2569 *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2570 *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
0ff4040e
SP		 2571 *last_conflicts = chrec_dont_know;
2572 }
2573
2574 /* If they aren't the same, and aren't affine, we can't do anything
2575 yet. */
2576 else if ((chrec_contains_symbols (chrec_a)
2577 || chrec_contains_symbols (chrec_b))
a50411de
AP		 2578 && (!evolution_function_is_affine_multivariate_p (chrec_a, 0)
2579 || !evolution_function_is_affine_multivariate_p (chrec_b, 0)))
0ff4040e
SP		 2580 {
2581 dependence_stats.num_subscript_undetermined++;
d93817c4
ZD		 2582 *overlap_iterations_a = conflict_fn_not_known ();
2583 *overlap_iterations_b = conflict_fn_not_known ();
0ff4040e
SP		 2584 }
2585
56cf8686
SP		 2586 else if (ziv_subscript_p (chrec_a, chrec_b))
2587 analyze_ziv_subscript (chrec_a, chrec_b,
86df10e3
SP		 2588 overlap_iterations_a, overlap_iterations_b,
2589 last_conflicts);
56cf8686
SP		 2590
2591 else if (siv_subscript_p (chrec_a, chrec_b))
2592 analyze_siv_subscript (chrec_a, chrec_b,
86df10e3
SP		 2593 overlap_iterations_a, overlap_iterations_b,
2594 last_conflicts);
56cf8686
SP		 2595
2596 else
2597 analyze_miv_subscript (chrec_a, chrec_b,
86df10e3
SP		 2598 overlap_iterations_a, overlap_iterations_b,
2599 last_conflicts);
56cf8686
SP		 2600
2601 if (dump_file && (dump_flags & TDF_DETAILS))
2602 {
2603 fprintf (dump_file, " (overlap_iterations_a = ");
d93817c4 2604 dump_conflict_function (dump_file, *overlap_iterations_a);
56cf8686 2605 fprintf (dump_file, ")\n (overlap_iterations_b = ");
d93817c4 2606 dump_conflict_function (dump_file, *overlap_iterations_b);
56cf8686 2607 fprintf (dump_file, ")\n");
0ff4040e 2608 fprintf (dump_file, ")\n");
56cf8686
SP		 2609 }
2610}
2611
ba42e045 2612/* Helper function for uniquely inserting distance vectors. */
56cf8686 2613
ba42e045
SP		 2614static void
2615save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
2616{
2617 unsigned i;
2618 lambda_vector v;
56cf8686 2619
ba42e045
SP		 2620 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
2621 if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
2622 return;
56cf8686 2623
ba42e045
SP		 2624 VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
2625}
56cf8686 2626
ba42e045
SP		 2627/* Helper function for uniquely inserting direction vectors. */
2628
2629static void
2630save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
56cf8686
SP		 2631{
2632 unsigned i;
ba42e045 2633 lambda_vector v;
0ff4040e 2634
ba42e045
SP		 2635 for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
2636 if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
2637 return;
2638
2639 VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
2640}
2641
2642/* Add a distance of 1 on all the loops outer than INDEX. If we
2643 haven't yet determined a distance for this outer loop, push a new
2644 distance vector composed of the previous distance, and a distance
2645 of 1 for this outer loop. Example:
2646
2647 | loop_1
2648 | loop_2
2649 | A[10]
2650 | endloop_2
2651 | endloop_1
2652
2653 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
2654 save (0, 1), then we have to save (1, 0). */
2655
2656static void
2657add_outer_distances (struct data_dependence_relation *ddr,
2658 lambda_vector dist_v, int index)
2659{
2660 /* For each outer loop where init_v is not set, the accesses are
2661 in dependence of distance 1 in the loop. */
2662 while (--index >= 0)
2663 {
2664 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2665 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
2666 save_v[index] = 1;
2667 save_dist_v (ddr, save_v);
2668 }
2669}
2670
2671/* Return false when fail to represent the data dependence as a
2672 distance vector. INIT_B is set to true when a component has been
2673 added to the distance vector DIST_V. INDEX_CARRY is then set to
2674 the index in DIST_V that carries the dependence. */
2675
2676static bool
2677build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
2678 struct data_reference *ddr_a,
2679 struct data_reference *ddr_b,
2680 lambda_vector dist_v, bool *init_b,
2681 int *index_carry)
2682{
2683 unsigned i;
2684 lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
0ff4040e 2685
36d59cf7 2686 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
56cf8686 2687 {
86df10e3 2688 tree access_fn_a, access_fn_b;
36d59cf7 2689 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
56cf8686
SP		 2690
2691 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
86df10e3
SP		 2692 {
2693 non_affine_dependence_relation (ddr);
ba42e045 2694 return false;
86df10e3
SP		 2695 }
2696
ba42e045
SP		 2697 access_fn_a = DR_ACCESS_FN (ddr_a, i);
2698 access_fn_b = DR_ACCESS_FN (ddr_b, i);
56cf8686 2699
86df10e3
SP		 2700 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
2701 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
56cf8686 2702 {
ba42e045
SP		 2703 int dist, index;
2704 int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
2705 DDR_LOOP_NEST (ddr));
2706 int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
2707 DDR_LOOP_NEST (ddr));
86df10e3
SP		 2708
2709 /* The dependence is carried by the outermost loop. Example:
2710 | loop_1
2711 | A[{4, +, 1}_1]
2712 | loop_2
2713 | A[{5, +, 1}_2]
2714 | endloop_2
2715 | endloop_1
2716 In this case, the dependence is carried by loop_1. */
ba42e045
SP		 2717 index = index_a < index_b ? index_a : index_b;
2718 *index_carry = MIN (index, *index_carry);
2719
86df10e3
SP		 2720 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2721 {
2722 non_affine_dependence_relation (ddr);
ba42e045 2723 return false;
86df10e3
SP		 2724 }
2725
56cf8686
SP		 2726 dist = int_cst_value (SUB_DISTANCE (subscript));
2727
ba42e045
SP		 2728 /* This is the subscript coupling test. If we have already
2729 recorded a distance for this loop (a distance coming from
2730 another subscript), it should be the same. For example,
2731 in the following code, there is no dependence:
2732
56cf8686
SP		 2733 | loop i = 0, N, 1
2734 | T[i+1][i] = ...
2735 | ... = T[i][i]
2736 | endloop
ba42e045
SP		 2737 */
2738 if (init_v[index] != 0 && dist_v[index] != dist)
56cf8686 2739 {
36d59cf7 2740 finalize_ddr_dependent (ddr, chrec_known);
ba42e045 2741 return false;
56cf8686
SP		 2742 }
2743
ba42e045
SP		 2744 dist_v[index] = dist;
2745 init_v[index] = 1;
2746 *init_b = true;
2747 }
a50411de 2748 else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
ba42e045
SP		 2749 {
2750 /* This can be for example an affine vs. constant dependence
2751 (T[i] vs. T[3]) that is not an affine dependence and is
2752 not representable as a distance vector. */
2753 non_affine_dependence_relation (ddr);
2754 return false;
56cf8686
SP		 2755 }
2756 }
304afda6 2757
ba42e045
SP		 2758 return true;
2759}
304afda6 2760
ba42e045
SP		 2761/* Return true when the DDR contains two data references that have the
2762 same access functions. */
304afda6 2763
ba42e045
SP		 2764static bool
2765same_access_functions (struct data_dependence_relation *ddr)
2766{
2767 unsigned i;
304afda6 2768
ba42e045 2769 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
e2157b49
SP		 2770 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
2771 DR_ACCESS_FN (DDR_B (ddr), i)))
2772 return false;
304afda6 2773
ba42e045
SP		 2774 return true;
2775}
304afda6 2776
1baf2906
SP		 2777/* Return true when the DDR contains only constant access functions. */
2778
2779static bool
2780constant_access_functions (struct data_dependence_relation *ddr)
2781{
2782 unsigned i;
2783
2784 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2785 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
2786 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
2787 return false;
2788
2789 return true;
2790}
2791
2792
ba42e045
SP		 2793/* Helper function for the case where DDR_A and DDR_B are the same
2794 multivariate access function. */
86df10e3 2795
ba42e045
SP		 2796static void
2797add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
2798{
2799 int x_1, x_2;
2800 tree c_1 = CHREC_LEFT (c_2);
2801 tree c_0 = CHREC_LEFT (c_1);
2802 lambda_vector dist_v;
0ca2faee 2803 int v1, v2, cd;
86df10e3 2804
ba42e045
SP		 2805 /* Polynomials with more than 2 variables are not handled yet. */
2806 if (TREE_CODE (c_0) != INTEGER_CST)
2807 {
2808 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
2809 return;
2810 }
304afda6 2811
ba42e045
SP		 2812 x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
2813 x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
304afda6 2814
ba42e045
SP		 2815 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
2816 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
0ca2faee
ZD		 2817 v1 = int_cst_value (CHREC_RIGHT (c_1));
2818 v2 = int_cst_value (CHREC_RIGHT (c_2));
2819 cd = gcd (v1, v2);
2820 v1 /= cd;
2821 v2 /= cd;
2822
2823 if (v2 < 0)
2824 {
2825 v2 = -v2;
2826 v1 = -v1;
2827 }
2828
2829 dist_v[x_1] = v2;
2830 dist_v[x_2] = -v1;
ba42e045 2831 save_dist_v (ddr, dist_v);
304afda6 2832
ba42e045
SP		 2833 add_outer_distances (ddr, dist_v, x_1);
2834}
304afda6 2835
ba42e045
SP		 2836/* Helper function for the case where DDR_A and DDR_B are the same
2837 access functions. */
37b8a73b 2838
ba42e045
SP		 2839static void
2840add_other_self_distances (struct data_dependence_relation *ddr)
2841{
2842 lambda_vector dist_v;
2843 unsigned i;
2844 int index_carry = DDR_NB_LOOPS (ddr);
304afda6 2845
ba42e045 2846 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
37b8a73b 2847 {
ba42e045 2848 tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
304afda6 2849
ba42e045 2850 if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
304afda6 2851 {
ba42e045
SP		 2852 if (!evolution_function_is_univariate_p (access_fun))
2853 {
2854 if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
2855 {
2856 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
2857 return;
2858 }
2859
2860 add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0));
2861 return;
2862 }
2863
2864 index_carry = MIN (index_carry,
2865 index_in_loop_nest (CHREC_VARIABLE (access_fun),
2866 DDR_LOOP_NEST (ddr)));
304afda6 2867 }
37b8a73b
SP		 2868 }
2869
ba42e045
SP		 2870 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2871 add_outer_distances (ddr, dist_v, index_carry);
56cf8686
SP		 2872}
2873
1baf2906
SP		 2874static void
2875insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
2876{
2877 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2878
2879 dist_v[DDR_INNER_LOOP (ddr)] = 1;
2880 save_dist_v (ddr, dist_v);
2881}
2882
2883/* Adds a unit distance vector to DDR when there is a 0 overlap. This
2884 is the case for example when access functions are the same and
2885 equal to a constant, as in:
2886
2887 | loop_1
2888 | A[3] = ...
2889 | ... = A[3]
2890 | endloop_1
2891
2892 in which case the distance vectors are (0) and (1). */
2893
2894static void
2895add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
2896{
2897 unsigned i, j;
2898
2899 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2900 {
2901 subscript_p sub = DDR_SUBSCRIPT (ddr, i);
2902 conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
2903 conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
2904
2905 for (j = 0; j < ca->n; j++)
2906 if (affine_function_zero_p (ca->fns[j]))
2907 {
2908 insert_innermost_unit_dist_vector (ddr);
2909 return;
2910 }
2911
2912 for (j = 0; j < cb->n; j++)
2913 if (affine_function_zero_p (cb->fns[j]))
2914 {
2915 insert_innermost_unit_dist_vector (ddr);
2916 return;
2917 }
2918 }
2919}
2920
ba42e045
SP		 2921/* Compute the classic per loop distance vector. DDR is the data
2922 dependence relation to build a vector from. Return false when fail
2923 to represent the data dependence as a distance vector. */
56cf8686 2924
464f49d8 2925static bool
ba42e045 2926build_classic_dist_vector (struct data_dependence_relation *ddr)
56cf8686 2927{
304afda6 2928 bool init_b = false;
ba42e045
SP		 2929 int index_carry = DDR_NB_LOOPS (ddr);
2930 lambda_vector dist_v;
304afda6 2931
36d59cf7 2932 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
464f49d8 2933 return true;
ba42e045
SP		 2934
2935 if (same_access_functions (ddr))
56cf8686 2936 {
ba42e045
SP		 2937 /* Save the 0 vector. */
2938 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2939 save_dist_v (ddr, dist_v);
56cf8686 2940
1baf2906
SP		 2941 if (constant_access_functions (ddr))
2942 add_distance_for_zero_overlaps (ddr);
2943
ba42e045
SP		 2944 if (DDR_NB_LOOPS (ddr) > 1)
2945 add_other_self_distances (ddr);
86df10e3 2946
ba42e045
SP		 2947 return true;
2948 }
86df10e3 2949
ba42e045
SP		 2950 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2951 if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
2952 dist_v, &init_b, &index_carry))
2953 return false;
86df10e3 2954
ba42e045
SP		 2955 /* Save the distance vector if we initialized one. */
2956 if (init_b)
2957 {
2958 /* Verify a basic constraint: classic distance vectors should
2959 always be lexicographically positive.
2960
2961 Data references are collected in the order of execution of
2962 the program, thus for the following loop
2963
2964 | for (i = 1; i < 100; i++)
2965 | for (j = 1; j < 100; j++)
2966 | {
2967 | t = T[j+1][i-1]; // A
2968 | T[j][i] = t + 2; // B
2969 | }
2970
2971 references are collected following the direction of the wind:
2972 A then B. The data dependence tests are performed also
2973 following this order, such that we're looking at the distance
2974 separating the elements accessed by A from the elements later
2975 accessed by B. But in this example, the distance returned by
2976 test_dep (A, B) is lexicographically negative (-1, 1), that
2977 means that the access A occurs later than B with respect to
2978 the outer loop, ie. we're actually looking upwind. In this
2979 case we solve test_dep (B, A) looking downwind to the
2980 lexicographically positive solution, that returns the
2981 distance vector (1, -1). */
2982 if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
2983 {
2984 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2985 subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
2986 compute_subscript_distance (ddr);
2987 build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
2988 save_v, &init_b, &index_carry);
2989 save_dist_v (ddr, save_v);
2990
2991 /* In this case there is a dependence forward for all the
2992 outer loops:
2993
2994 | for (k = 1; k < 100; k++)
2995 | for (i = 1; i < 100; i++)
2996 | for (j = 1; j < 100; j++)
2997 | {
2998 | t = T[j+1][i-1]; // A
2999 | T[j][i] = t + 2; // B
3000 | }
3001
3002 the vectors are:
3003 (0, 1, -1)
3004 (1, 1, -1)
3005 (1, -1, 1)
3006 */
3007 if (DDR_NB_LOOPS (ddr) > 1)
3008 {
3009 add_outer_distances (ddr, save_v, index_carry);
3010 add_outer_distances (ddr, dist_v, index_carry);
86df10e3 3011 }
ba42e045
SP		 3012 }
3013 else
3014 {
3015 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3016 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3017 save_dist_v (ddr, save_v);
86df10e3 3018
ba42e045 3019 if (DDR_NB_LOOPS (ddr) > 1)
56cf8686 3020 {
ba42e045 3021 lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
86df10e3 3022
ba42e045
SP		 3023 subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
3024 compute_subscript_distance (ddr);
3025 build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3026 opposite_v, &init_b, &index_carry);
86df10e3 3027
ba42e045
SP		 3028 add_outer_distances (ddr, dist_v, index_carry);
3029 add_outer_distances (ddr, opposite_v, index_carry);
56cf8686 3030 }
56cf8686
SP		 3031 }
3032 }
ba42e045
SP		 3033 else
3034 {
3035 /* There is a distance of 1 on all the outer loops: Example:
3036 there is a dependence of distance 1 on loop_1 for the array A.
304afda6 3037
ba42e045
SP		 3038 | loop_1
3039 | A[5] = ...
3040 | endloop
3041 */
3042 add_outer_distances (ddr, dist_v,
3043 lambda_vector_first_nz (dist_v,
3044 DDR_NB_LOOPS (ddr), 0));
3045 }
3046
3047 if (dump_file && (dump_flags & TDF_DETAILS))
304afda6 3048 {
ba42e045 3049 unsigned i;
304afda6 3050
ba42e045
SP		 3051 fprintf (dump_file, "(build_classic_dist_vector\n");
3052 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3053 {
3054 fprintf (dump_file, " dist_vector = (");
3055 print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
3056 DDR_NB_LOOPS (ddr));
3057 fprintf (dump_file, " )\n");
3058 }
3059 fprintf (dump_file, ")\n");
304afda6
SP		 3060 }
3061
ba42e045
SP		 3062 return true;
3063}
56cf8686 3064
ba42e045
SP		 3065/* Return the direction for a given distance.
3066 FIXME: Computing dir this way is suboptimal, since dir can catch
3067 cases that dist is unable to represent. */
86df10e3 3068
ba42e045
SP		 3069static inline enum data_dependence_direction
3070dir_from_dist (int dist)
3071{
3072 if (dist > 0)
3073 return dir_positive;
3074 else if (dist < 0)
3075 return dir_negative;
3076 else
3077 return dir_equal;
3078}
304afda6 3079
ba42e045
SP		 3080/* Compute the classic per loop direction vector. DDR is the data
3081 dependence relation to build a vector from. */
304afda6 3082
ba42e045
SP		 3083static void
3084build_classic_dir_vector (struct data_dependence_relation *ddr)
3085{
3086 unsigned i, j;
3087 lambda_vector dist_v;
86df10e3 3088
ba42e045
SP		 3089 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
3090 {
3091 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
86df10e3 3092
ba42e045
SP		 3093 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3094 dir_v[j] = dir_from_dist (dist_v[j]);
304afda6 3095
ba42e045
SP		 3096 save_dir_v (ddr, dir_v);
3097 }
56cf8686
SP		 3098}
3099
ba42e045
SP		 3100/* Helper function. Returns true when there is a dependence between
3101 data references DRA and DRB. */
0ff4040e 3102
ba42e045
SP		 3103static bool
3104subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
3105 struct data_reference *dra,
3106 struct data_reference *drb)
0ff4040e
SP		 3107{
3108 unsigned int i;
0ff4040e 3109 tree last_conflicts;
ebf78a47 3110 struct subscript *subscript;
ba42e045 3111
ebf78a47
SP		 3112 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3113 i++)
0ff4040e 3114 {
d93817c4 3115 conflict_function *overlaps_a, *overlaps_b;
ebf78a47 3116
0ff4040e
SP		 3117 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
3118 DR_ACCESS_FN (drb, i),
3119 &overlaps_a, &overlaps_b,
3120 &last_conflicts);
ebf78a47 3121
d93817c4
ZD		 3122 if (CF_NOT_KNOWN_P (overlaps_a)
3123 || CF_NOT_KNOWN_P (overlaps_b))
0ff4040e
SP		 3124 {
3125 finalize_ddr_dependent (ddr, chrec_dont_know);
3126 dependence_stats.num_dependence_undetermined++;
d93817c4
ZD		 3127 free_conflict_function (overlaps_a);
3128 free_conflict_function (overlaps_b);
ba42e045 3129 return false;
0ff4040e 3130 }
ebf78a47 3131
d93817c4
ZD		 3132 else if (CF_NO_DEPENDENCE_P (overlaps_a)
3133 || CF_NO_DEPENDENCE_P (overlaps_b))
0ff4040e
SP		 3134 {
3135 finalize_ddr_dependent (ddr, chrec_known);
3136 dependence_stats.num_dependence_independent++;
d93817c4
ZD		 3137 free_conflict_function (overlaps_a);
3138 free_conflict_function (overlaps_b);
ba42e045 3139 return false;
0ff4040e 3140 }
ebf78a47 3141
0ff4040e
SP		 3142 else
3143 {
3144 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3145 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3146 SUB_LAST_CONFLICT (subscript) = last_conflicts;
3147 }
3148 }
3149
ba42e045
SP		 3150 return true;
3151}
3152
3153/* Computes the conflicting iterations, and initialize DDR. */
3154
3155static void
3156subscript_dependence_tester (struct data_dependence_relation *ddr)
3157{
3158
3159 if (dump_file && (dump_flags & TDF_DETAILS))
3160 fprintf (dump_file, "(subscript_dependence_tester \n");
3161
3162 if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr)))
3163 dependence_stats.num_dependence_dependent++;
0ff4040e 3164
0ff4040e 3165 compute_subscript_distance (ddr);
ba42e045
SP		 3166 if (build_classic_dist_vector (ddr))
3167 build_classic_dir_vector (ddr);
0ff4040e
SP		 3168
3169 if (dump_file && (dump_flags & TDF_DETAILS))
3170 fprintf (dump_file, ")\n");
3171}
3172
56cf8686
SP		 3173/* Returns true when all the access functions of A are affine or
3174 constant. */
3175
3176static bool
3177access_functions_are_affine_or_constant_p (struct data_reference *a)
3178{
3179 unsigned int i;
3d8864c0 3180 VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
9cbb7989 3181 tree t;
3d8864c0
SP		 3182
3183 for (i = 0; VEC_iterate (tree, fns, i, t); i++)
9cbb7989 3184 if (!evolution_function_is_constant_p (t)
a50411de 3185 && !evolution_function_is_affine_multivariate_p (t, 0))
56cf8686
SP		 3186 return false;
3187
3188 return true;
3189}
3190
3d8864c0
SP		 3191/* Initializes an equation for an OMEGA problem using the information
3192 contained in the ACCESS_FUN. Returns true when the operation
3193 succeeded.
3194
3195 PB is the omega constraint system.
3196 EQ is the number of the equation to be initialized.
3197 OFFSET is used for shifting the variables names in the constraints:
3198 a constrain is composed of 2 * the number of variables surrounding
3199 dependence accesses. OFFSET is set either to 0 for the first n variables,
3200 then it is set to n.
3201 ACCESS_FUN is expected to be an affine chrec. */
3202
3203static bool
3204init_omega_eq_with_af (omega_pb pb, unsigned eq,
3205 unsigned int offset, tree access_fun,
3206 struct data_dependence_relation *ddr)
3207{
3208 switch (TREE_CODE (access_fun))
3209 {
3210 case POLYNOMIAL_CHREC:
3211 {
3212 tree left = CHREC_LEFT (access_fun);
3213 tree right = CHREC_RIGHT (access_fun);
3214 int var = CHREC_VARIABLE (access_fun);
3215 unsigned var_idx;
3216
3217 if (TREE_CODE (right) != INTEGER_CST)
3218 return false;
3219
3220 var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
3221 pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
3222
3223 /* Compute the innermost loop index. */
3224 DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
3225
3226 if (offset == 0)
3227 pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
3228 += int_cst_value (right);
3229
3230 switch (TREE_CODE (left))
3231 {
3232 case POLYNOMIAL_CHREC:
3233 return init_omega_eq_with_af (pb, eq, offset, left, ddr);
3234
3235 case INTEGER_CST:
3236 pb->eqs[eq].coef[0] += int_cst_value (left);
3237 return true;
3238
3239 default:
3240 return false;
3241 }
3242 }
3243
3244 case INTEGER_CST:
3245 pb->eqs[eq].coef[0] += int_cst_value (access_fun);
3246 return true;
3247
3248 default:
3249 return false;
3250 }
3251}
3252
3253/* As explained in the comments preceding init_omega_for_ddr, we have
3254 to set up a system for each loop level, setting outer loops
3255 variation to zero, and current loop variation to positive or zero.
3256 Save each lexico positive distance vector. */
3257
3258static void
3259omega_extract_distance_vectors (omega_pb pb,
3260 struct data_dependence_relation *ddr)
3261{
3262 int eq, geq;
3263 unsigned i, j;
3264 struct loop *loopi, *loopj;
3265 enum omega_result res;
3266
3267 /* Set a new problem for each loop in the nest. The basis is the
3268 problem that we have initialized until now. On top of this we
3269 add new constraints. */
3270 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3271 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3272 {
3273 int dist = 0;
3274 omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
3275 DDR_NB_LOOPS (ddr));
3276
3277 omega_copy_problem (copy, pb);
3278
3279 /* For all the outer loops "loop_j", add "dj = 0". */
3280 for (j = 0;
3281 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3282 {
3283 eq = omega_add_zero_eq (copy, omega_black);
3284 copy->eqs[eq].coef[j + 1] = 1;
3285 }
3286
3287 /* For "loop_i", add "0 <= di". */
3288 geq = omega_add_zero_geq (copy, omega_black);
3289 copy->geqs[geq].coef[i + 1] = 1;
3290
3291 /* Reduce the constraint system, and test that the current
3292 problem is feasible. */
3293 res = omega_simplify_problem (copy);
3294 if (res == omega_false
3295 || res == omega_unknown
3296 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3297 goto next_problem;
3298
3299 for (eq = 0; eq < copy->num_subs; eq++)
3300 if (copy->subs[eq].key == (int) i + 1)
3301 {
3302 dist = copy->subs[eq].coef[0];
3303 goto found_dist;
3304 }
3305
3306 if (dist == 0)
3307 {
3308 /* Reinitialize problem... */
3309 omega_copy_problem (copy, pb);
3310 for (j = 0;
3311 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3312 {
3313 eq = omega_add_zero_eq (copy, omega_black);
3314 copy->eqs[eq].coef[j + 1] = 1;
3315 }
3316
3317 /* ..., but this time "di = 1". */
3318 eq = omega_add_zero_eq (copy, omega_black);
3319 copy->eqs[eq].coef[i + 1] = 1;
3320 copy->eqs[eq].coef[0] = -1;
3321
3322 res = omega_simplify_problem (copy);
3323 if (res == omega_false
3324 || res == omega_unknown
3325 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3326 goto next_problem;
3327
3328 for (eq = 0; eq < copy->num_subs; eq++)
3329 if (copy->subs[eq].key == (int) i + 1)
3330 {
3331 dist = copy->subs[eq].coef[0];
3332 goto found_dist;
3333 }
3334 }
3335
3336 found_dist:;
3337 /* Save the lexicographically positive distance vector. */
3338 if (dist >= 0)
3339 {
3340 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3341 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3342
3343 dist_v[i] = dist;
3344
3345 for (eq = 0; eq < copy->num_subs; eq++)
3346 if (copy->subs[eq].key > 0)
3347 {
3348 dist = copy->subs[eq].coef[0];
3349 dist_v[copy->subs[eq].key - 1] = dist;
3350 }
3351
3352 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3353 dir_v[j] = dir_from_dist (dist_v[j]);
3354
3355 save_dist_v (ddr, dist_v);
3356 save_dir_v (ddr, dir_v);
3357 }
3358
3359 next_problem:;
3360 omega_free_problem (copy);
3361 }
3362}
3363
3364/* This is called for each subscript of a tuple of data references:
3365 insert an equality for representing the conflicts. */
3366
3367static bool
3368omega_setup_subscript (tree access_fun_a, tree access_fun_b,
3369 struct data_dependence_relation *ddr,
3370 omega_pb pb, bool *maybe_dependent)
3371{
3372 int eq;
3373 tree fun_a = chrec_convert (integer_type_node, access_fun_a, NULL_TREE);
3374 tree fun_b = chrec_convert (integer_type_node, access_fun_b, NULL_TREE);
3375 tree difference = chrec_fold_minus (integer_type_node, fun_a, fun_b);
3376
3377 /* When the fun_a - fun_b is not constant, the dependence is not
3378 captured by the classic distance vector representation. */
3379 if (TREE_CODE (difference) != INTEGER_CST)
3380 return false;
3381
3382 /* ZIV test. */
3383 if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
3384 {
3385 /* There is no dependence. */
3386 *maybe_dependent = false;
3387 return true;
3388 }
3389
3390 fun_b = chrec_fold_multiply (integer_type_node, fun_b,
3391 integer_minus_one_node);
3392
3393 eq = omega_add_zero_eq (pb, omega_black);
3394 if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
3395 || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
3396 /* There is probably a dependence, but the system of
3397 constraints cannot be built: answer "don't know". */
3398 return false;
3399
3400 /* GCD test. */
3401 if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
3402 && !int_divides_p (lambda_vector_gcd
3403 ((lambda_vector) &(pb->eqs[eq].coef[1]),
3404 2 * DDR_NB_LOOPS (ddr)),
3405 pb->eqs[eq].coef[0]))
3406 {
3407 /* There is no dependence. */
3408 *maybe_dependent = false;
3409 return true;
3410 }
3411
3412 return true;
3413}
3414
3415/* Helper function, same as init_omega_for_ddr but specialized for
3416 data references A and B. */
3417
3418static bool
3419init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
3420 struct data_dependence_relation *ddr,
3421 omega_pb pb, bool *maybe_dependent)
3422{
3423 unsigned i;
3424 int ineq;
3425 struct loop *loopi;
3426 unsigned nb_loops = DDR_NB_LOOPS (ddr);
3427
3428 /* Insert an equality per subscript. */
3429 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3430 {
3431 if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
3432 ddr, pb, maybe_dependent))
3433 return false;
3434 else if (*maybe_dependent == false)
3435 {
3436 /* There is no dependence. */
3437 DDR_ARE_DEPENDENT (ddr) = chrec_known;
3438 return true;
3439 }
3440 }
3441
3442 /* Insert inequalities: constraints corresponding to the iteration
3443 domain, i.e. the loops surrounding the references "loop_x" and
3444 the distance variables "dx". The layout of the OMEGA
3445 representation is as follows:
3446 - coef[0] is the constant
3447 - coef[1..nb_loops] are the protected variables that will not be
3448 removed by the solver: the "dx"
3449 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3450 */
3451 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3452 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3453 {
3454 HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, true);
3455
3456 /* 0 <= loop_x */
3457 ineq = omega_add_zero_geq (pb, omega_black);
3458 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3459
3460 /* 0 <= loop_x + dx */
3461 ineq = omega_add_zero_geq (pb, omega_black);
3462 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3463 pb->geqs[ineq].coef[i + 1] = 1;
3464
3465 if (nbi != -1)
3466 {
3467 /* loop_x <= nb_iters */
3468 ineq = omega_add_zero_geq (pb, omega_black);
3469 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3470 pb->geqs[ineq].coef[0] = nbi;
3471
3472 /* loop_x + dx <= nb_iters */
3473 ineq = omega_add_zero_geq (pb, omega_black);
3474 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3475 pb->geqs[ineq].coef[i + 1] = -1;
3476 pb->geqs[ineq].coef[0] = nbi;
3477
3478 /* A step "dx" bigger than nb_iters is not feasible, so
3479 add "0 <= nb_iters + dx", */
3480 ineq = omega_add_zero_geq (pb, omega_black);
3481 pb->geqs[ineq].coef[i + 1] = 1;
3482 pb->geqs[ineq].coef[0] = nbi;
3483 /* and "dx <= nb_iters". */
3484 ineq = omega_add_zero_geq (pb, omega_black);
3485 pb->geqs[ineq].coef[i + 1] = -1;
3486 pb->geqs[ineq].coef[0] = nbi;
3487 }
3488 }
3489
3490 omega_extract_distance_vectors (pb, ddr);
3491
3492 return true;
3493}
3494
3495/* Sets up the Omega dependence problem for the data dependence
3496 relation DDR. Returns false when the constraint system cannot be
3497 built, ie. when the test answers "don't know". Returns true
3498 otherwise, and when independence has been proved (using one of the
3499 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3500 set MAYBE_DEPENDENT to true.
3501
3502 Example: for setting up the dependence system corresponding to the
3503 conflicting accesses
3504
3505 | loop_i
3506 | loop_j
3507 | A[i, i+1] = ...
3508 | ... A[2*j, 2*(i + j)]
3509 | endloop_j
3510 | endloop_i
3511
3512 the following constraints come from the iteration domain:
3513
3514 0 <= i <= Ni
3515 0 <= i + di <= Ni
3516 0 <= j <= Nj
3517 0 <= j + dj <= Nj
3518
3519 where di, dj are the distance variables. The constraints
3520 representing the conflicting elements are:
3521
3522 i = 2 * (j + dj)
3523 i + 1 = 2 * (i + di + j + dj)
3524
3525 For asking that the resulting distance vector (di, dj) be
3526 lexicographically positive, we insert the constraint "di >= 0". If
3527 "di = 0" in the solution, we fix that component to zero, and we
3528 look at the inner loops: we set a new problem where all the outer
3529 loop distances are zero, and fix this inner component to be
3530 positive. When one of the components is positive, we save that
3531 distance, and set a new problem where the distance on this loop is
3532 zero, searching for other distances in the inner loops. Here is
3533 the classic example that illustrates that we have to set for each
3534 inner loop a new problem:
3535
3536 | loop_1
3537 | loop_2
3538 | A[10]
3539 | endloop_2
3540 | endloop_1
3541
3542 we have to save two distances (1, 0) and (0, 1).
3543
3544 Given two array references, refA and refB, we have to set the
3545 dependence problem twice, refA vs. refB and refB vs. refA, and we
3546 cannot do a single test, as refB might occur before refA in the
3547 inner loops, and the contrary when considering outer loops: ex.
3548
3549 | loop_0
3550 | loop_1
3551 | loop_2
3552 | T[{1,+,1}_2][{1,+,1}_1] // refA
3553 | T[{2,+,1}_2][{0,+,1}_1] // refB
3554 | endloop_2
3555 | endloop_1
3556 | endloop_0
3557
3558 refB touches the elements in T before refA, and thus for the same
3559 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3560 but for successive loop_0 iterations, we have (1, -1, 1)
3561
3562 The Omega solver expects the distance variables ("di" in the
3563 previous example) to come first in the constraint system (as
3564 variables to be protected, or "safe" variables), the constraint
3565 system is built using the following layout:
3566
3567 "cst | distance vars | index vars".
3568*/
3569
3570static bool
3571init_omega_for_ddr (struct data_dependence_relation *ddr,
3572 bool *maybe_dependent)
3573{
3574 omega_pb pb;
3575 bool res = false;
3576
3577 *maybe_dependent = true;
3578
3579 if (same_access_functions (ddr))
3580 {
3581 unsigned j;
3582 lambda_vector dir_v;
3583
3584 /* Save the 0 vector. */
3585 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3586 dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3587 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3588 dir_v[j] = dir_equal;
3589 save_dir_v (ddr, dir_v);
3590
3591 /* Save the dependences carried by outer loops. */
3592 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3593 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3594 maybe_dependent);
3595 omega_free_problem (pb);
3596 return res;
3597 }
3598
3599 /* Omega expects the protected variables (those that have to be kept
3600 after elimination) to appear first in the constraint system.
3601 These variables are the distance variables. In the following
3602 initialization we declare NB_LOOPS safe variables, and the total
3603 number of variables for the constraint system is 2*NB_LOOPS. */
3604 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3605 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3606 maybe_dependent);
3607 omega_free_problem (pb);
3608
3609 /* Stop computation if not decidable, or no dependence. */
3610 if (res == false || *maybe_dependent == false)
3611 return res;
3612
3613 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3614 res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
3615 maybe_dependent);
3616 omega_free_problem (pb);
3617
3618 return res;
3619}
3620
3621/* Return true when DDR contains the same information as that stored
3622 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3623
3624static bool
3625ddr_consistent_p (FILE *file,
3626 struct data_dependence_relation *ddr,
3627 VEC (lambda_vector, heap) *dist_vects,
3628 VEC (lambda_vector, heap) *dir_vects)
3629{
3630 unsigned int i, j;
3631
3632 /* If dump_file is set, output there. */
3633 if (dump_file && (dump_flags & TDF_DETAILS))
3634 file = dump_file;
3635
3636 if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
3637 {
3638 lambda_vector b_dist_v;
3639 fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3640 VEC_length (lambda_vector, dist_vects),
3641 DDR_NUM_DIST_VECTS (ddr));
3642
3643 fprintf (file, "Banerjee dist vectors:\n");
3644 for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++)
3645 print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
3646
3647 fprintf (file, "Omega dist vectors:\n");
3648 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3649 print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
3650
3651 fprintf (file, "data dependence relation:\n");
3652 dump_data_dependence_relation (file, ddr);
3653
3654 fprintf (file, ")\n");
3655 return false;
3656 }
3657
3658 if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
3659 {
3660 fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3661 VEC_length (lambda_vector, dir_vects),
3662 DDR_NUM_DIR_VECTS (ddr));
3663 return false;
3664 }
3665
3666 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3667 {
3668 lambda_vector a_dist_v;
3669 lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
3670
3671 /* Distance vectors are not ordered in the same way in the DDR
3672 and in the DIST_VECTS: search for a matching vector. */
3673 for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, a_dist_v); j++)
3674 if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
3675 break;
3676
3677 if (j == VEC_length (lambda_vector, dist_vects))
3678 {
3679 fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
3680 print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
3681 fprintf (file, "not found in Omega dist vectors:\n");
3682 print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
3683 fprintf (file, "data dependence relation:\n");
3684 dump_data_dependence_relation (file, ddr);
3685 fprintf (file, ")\n");
3686 }
3687 }
3688
3689 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
3690 {
3691 lambda_vector a_dir_v;
3692 lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
3693
3694 /* Direction vectors are not ordered in the same way in the DDR
3695 and in the DIR_VECTS: search for a matching vector. */
3696 for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, a_dir_v); j++)
3697 if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
3698 break;
3699
3700 if (j == VEC_length (lambda_vector, dist_vects))
3701 {
3702 fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
3703 print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
3704 fprintf (file, "not found in Omega dir vectors:\n");
3705 print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
3706 fprintf (file, "data dependence relation:\n");
3707 dump_data_dependence_relation (file, ddr);
3708 fprintf (file, ")\n");
3709 }
3710 }
3711
3712 return true;
3713}
3714
56cf8686
SP		 3715/* This computes the affine dependence relation between A and B.
3716 CHREC_KNOWN is used for representing the independence between two
3717 accesses, while CHREC_DONT_KNOW is used for representing the unknown
3718 relation.
3719
3720 Note that it is possible to stop the computation of the dependence
3721 relation the first time we detect a CHREC_KNOWN element for a given
3722 subscript. */
3723
0ff4040e 3724static void
ba42e045 3725compute_affine_dependence (struct data_dependence_relation *ddr)
56cf8686
SP		 3726{
3727 struct data_reference *dra = DDR_A (ddr);
3728 struct data_reference *drb = DDR_B (ddr);
3729
3730 if (dump_file && (dump_flags & TDF_DETAILS))
3731 {
36d59cf7 3732 fprintf (dump_file, "(compute_affine_dependence\n");
56cf8686
SP		 3733 fprintf (dump_file, " (stmt_a = \n");
3734 print_generic_expr (dump_file, DR_STMT (dra), 0);
3735 fprintf (dump_file, ")\n (stmt_b = \n");
3736 print_generic_expr (dump_file, DR_STMT (drb), 0);
3737 fprintf (dump_file, ")\n");
3738 }
0ff4040e 3739
56cf8686
SP		 3740 /* Analyze only when the dependence relation is not yet known. */
3741 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3742 {
0ff4040e
SP		 3743 dependence_stats.num_dependence_tests++;
3744
56cf8686
SP		 3745 if (access_functions_are_affine_or_constant_p (dra)
3746 && access_functions_are_affine_or_constant_p (drb))
3d8864c0
SP		 3747 {
3748 if (flag_check_data_deps)
3749 {
3750 /* Compute the dependences using the first algorithm. */
3751 subscript_dependence_tester (ddr);
3752
3753 if (dump_file && (dump_flags & TDF_DETAILS))
3754 {
3755 fprintf (dump_file, "\n\nBanerjee Analyzer\n");
3756 dump_data_dependence_relation (dump_file, ddr);
3757 }
3758
3759 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3760 {
3761 bool maybe_dependent;
3762 VEC (lambda_vector, heap) *dir_vects, *dist_vects;
3763
3764 /* Save the result of the first DD analyzer. */
3765 dist_vects = DDR_DIST_VECTS (ddr);
3766 dir_vects = DDR_DIR_VECTS (ddr);
3767
3768 /* Reset the information. */
3769 DDR_DIST_VECTS (ddr) = NULL;
3770 DDR_DIR_VECTS (ddr) = NULL;
3771
3772 /* Compute the same information using Omega. */
3773 if (!init_omega_for_ddr (ddr, &maybe_dependent))
3774 goto csys_dont_know;
3775
3776 if (dump_file && (dump_flags & TDF_DETAILS))
3777 {
3778 fprintf (dump_file, "Omega Analyzer\n");
3779 dump_data_dependence_relation (dump_file, ddr);
3780 }
3781
3782 /* Check that we get the same information. */
3783 if (maybe_dependent)
3784 gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
3785 dir_vects));
3786 }
3787 }
3788 else
3789 subscript_dependence_tester (ddr);
3790 }
3791
56cf8686
SP		 3792 /* As a last case, if the dependence cannot be determined, or if
3793 the dependence is considered too difficult to determine, answer
3794 "don't know". */
3795 else
0ff4040e 3796 {
3d8864c0 3797 csys_dont_know:;
0ff4040e
SP		 3798 dependence_stats.num_dependence_undetermined++;
3799
3800 if (dump_file && (dump_flags & TDF_DETAILS))
3801 {
3802 fprintf (dump_file, "Data ref a:\n");
3803 dump_data_reference (dump_file, dra);
3804 fprintf (dump_file, "Data ref b:\n");
3805 dump_data_reference (dump_file, drb);
3806 fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
3807 }
3808 finalize_ddr_dependent (ddr, chrec_dont_know);
3809 }
56cf8686
SP		 3810 }
3811
3812 if (dump_file && (dump_flags & TDF_DETAILS))
3813 fprintf (dump_file, ")\n");
3814}
3815
789246d7
SP		 3816/* This computes the dependence relation for the same data
3817 reference into DDR. */
3818
3819static void
3820compute_self_dependence (struct data_dependence_relation *ddr)
3821{
3822 unsigned int i;
ebf78a47 3823 struct subscript *subscript;
789246d7 3824
3cb960c7
ZD		 3825 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3826 return;
3827
ebf78a47
SP		 3828 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3829 i++)
789246d7 3830 {
789246d7 3831 /* The accessed index overlaps for each iteration. */
d93817c4
ZD		 3832 SUB_CONFLICTS_IN_A (subscript)
3833 = conflict_fn (1, affine_fn_cst (integer_zero_node));
3834 SUB_CONFLICTS_IN_B (subscript)
3835 = conflict_fn (1, affine_fn_cst (integer_zero_node));
789246d7
SP		 3836 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3837 }
789246d7 3838
0ff4040e 3839 /* The distance vector is the zero vector. */
ba42e045
SP		 3840 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3841 save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
0ff4040e 3842}
7b8a92e1 3843
ba42e045
SP		 3844/* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3845 the data references in DATAREFS, in the LOOP_NEST. When
ebf78a47
SP		 3846 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3847 relations. */
56cf8686
SP		 3848
3849static void
ebf78a47 3850compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
a84481aa 3851 VEC (ddr_p, heap) **dependence_relations,
ba42e045 3852 VEC (loop_p, heap) *loop_nest,
ebf78a47 3853 bool compute_self_and_rr)
56cf8686 3854{
ebf78a47
SP		 3855 struct data_dependence_relation *ddr;
3856 struct data_reference *a, *b;
3857 unsigned int i, j;
56cf8686 3858
ebf78a47
SP		 3859 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
3860 for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
3861 if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
3862 {
3863 ddr = initialize_data_dependence_relation (a, b, loop_nest);
a84481aa 3864 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
ebf78a47
SP		 3865 compute_affine_dependence (ddr);
3866 }
789246d7 3867
ebf78a47
SP		 3868 if (compute_self_and_rr)
3869 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
56cf8686 3870 {
ebf78a47 3871 ddr = initialize_data_dependence_relation (a, a, loop_nest);
a84481aa 3872 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
ebf78a47 3873 compute_self_dependence (ddr);
56cf8686
SP		 3874 }
3875}
3876
946e1bc7
ZD		 3877/* Stores the locations of memory references in STMT to REFERENCES. Returns
3878 true if STMT clobbers memory, false otherwise. */
3879
3880bool
3881get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references)
3882{
3883 bool clobbers_memory = false;
3884 data_ref_loc *ref;
ac84e05e 3885 tree *op0, *op1, call;
946e1bc7
ZD		 3886
3887 *references = NULL;
3888
3889 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
3890 Calls have side-effects, except those to const or pure
3891 functions. */
3892 call = get_call_expr_in (stmt);
3893 if ((call
3894 && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE)))
3895 || (TREE_CODE (stmt) == ASM_EXPR
3896 && ASM_VOLATILE_P (stmt)))
3897 clobbers_memory = true;
3898
3899 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3900 return clobbers_memory;
3901
07beea0d 3902 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
946e1bc7 3903 {
07beea0d
AH		 3904 op0 = &GIMPLE_STMT_OPERAND (stmt, 0);
3905 op1 = &GIMPLE_STMT_OPERAND (stmt, 1);
946e1bc7
ZD		 3906
3907 if (DECL_P (*op1)
3908 || REFERENCE_CLASS_P (*op1))
3909 {
3910 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
3911 ref->pos = op1;
3912 ref->is_read = true;
3913 }
3914
3915 if (DECL_P (*op0)
3916 || REFERENCE_CLASS_P (*op0))
3917 {
3918 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
3919 ref->pos = op0;
3920 ref->is_read = false;
3921 }
3922 }
3923
3924 if (call)
3925 {
ac84e05e
ZD		 3926 unsigned i, n = call_expr_nargs (call);
3927
3928 for (i = 0; i < n; i++)
946e1bc7 3929 {
ac84e05e
ZD		 3930 op0 = &CALL_EXPR_ARG (call, i);
3931
946e1bc7
ZD		 3932 if (DECL_P (*op0)
3933 || REFERENCE_CLASS_P (*op0))
3934 {
3935 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
3936 ref->pos = op0;
3937 ref->is_read = true;
3938 }
3939 }
3940 }
3941
3942 return clobbers_memory;
3943}
3944
3945/* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
3cb960c7
ZD		 3946 reference, returns false, otherwise returns true. NEST is the outermost
3947 loop of the loop nest in that the references should be analysed. */
946e1bc7
ZD		 3948
3949static bool
3cb960c7 3950find_data_references_in_stmt (struct loop *nest, tree stmt,
946e1bc7
ZD		 3951 VEC (data_reference_p, heap) **datarefs)
3952{
3953 unsigned i;
3954 VEC (data_ref_loc, heap) *references;
3955 data_ref_loc *ref;
3956 bool ret = true;
3957 data_reference_p dr;
3958
3959 if (get_references_in_stmt (stmt, &references))
3960 {
3961 VEC_free (data_ref_loc, heap, references);
3962 return false;
3963 }
3964
3965 for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
3966 {
3cb960c7 3967 dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
946e1bc7
ZD		 3968 if (dr)
3969 VEC_safe_push (data_reference_p, heap, *datarefs, dr);
3970 else
3971 {
3972 ret = false;
3973 break;
3974 }
3975 }
3976 VEC_free (data_ref_loc, heap, references);
3977 return ret;
3978}
3979
56cf8686
SP		 3980/* Search the data references in LOOP, and record the information into
3981 DATAREFS. Returns chrec_dont_know when failing to analyze a
3982 difficult case, returns NULL_TREE otherwise.
3cb960c7 3983
464f49d8
DB		 3984 TODO: This function should be made smarter so that it can handle address
3985 arithmetic as if they were array accesses, etc. */
56cf8686 3986
3cb960c7 3987static tree
ebf78a47 3988find_data_references_in_loop (struct loop *loop,
e14b10df 3989 VEC (data_reference_p, heap) **datarefs)
56cf8686 3990{
ccbdbf0a
JL		 3991 basic_block bb, *bbs;
3992 unsigned int i;
56cf8686 3993 block_stmt_iterator bsi;
86df10e3 3994
ccbdbf0a
JL		 3995 bbs = get_loop_body (loop);
3996
3997 for (i = 0; i < loop->num_nodes; i++)
56cf8686 3998 {
ccbdbf0a
JL		 3999 bb = bbs[i];
4000
56cf8686 4001 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
946e1bc7 4002 {
56cf8686 4003 tree stmt = bsi_stmt (bsi);
56cf8686 4004
3cb960c7 4005 if (!find_data_references_in_stmt (loop, stmt, datarefs))
86df10e3 4006 {
946e1bc7 4007 struct data_reference *res;
3cb960c7 4008 res = XCNEW (struct data_reference);
946e1bc7
ZD		 4009 VEC_safe_push (data_reference_p, heap, *datarefs, res);
4010
4011 free (bbs);
4012 return chrec_dont_know;
86df10e3 4013 }
56cf8686
SP		 4014 }
4015 }
ccbdbf0a
JL		 4016 free (bbs);
4017
4aad410d 4018 return NULL_TREE;
56cf8686
SP		 4019}
4020
ba42e045
SP		 4021/* Recursive helper function. */
4022
4023static bool
3ac57120 4024find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
ba42e045
SP		 4025{
4026 /* Inner loops of the nest should not contain siblings. Example:
4027 when there are two consecutive loops,
4028
4029 | loop_0
4030 | loop_1
4031 | A[{0, +, 1}_1]
4032 | endloop_1
4033 | loop_2
4034 | A[{0, +, 1}_2]
4035 | endloop_2
4036 | endloop_0
4037
4038 the dependence relation cannot be captured by the distance
4039 abstraction. */
4040 if (loop->next)
4041 return false;
56cf8686 4042
3ac57120 4043 VEC_safe_push (loop_p, heap, *loop_nest, loop);
ba42e045
SP		 4044 if (loop->inner)
4045 return find_loop_nest_1 (loop->inner, loop_nest);
4046 return true;
4047}
4048
4049/* Return false when the LOOP is not well nested. Otherwise return
4050 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4051 contain the loops from the outermost to the innermost, as they will
4052 appear in the classic distance vector. */
4053
4054static bool
3ac57120 4055find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
ba42e045 4056{
3ac57120 4057 VEC_safe_push (loop_p, heap, *loop_nest, loop);
ba42e045
SP		 4058 if (loop->inner)
4059 return find_loop_nest_1 (loop->inner, loop_nest);
4060 return true;
4061}
56cf8686
SP		 4062
4063/* Given a loop nest LOOP, the following vectors are returned:
ebf78a47
SP		 4064 DATAREFS is initialized to all the array elements contained in this loop,
4065 DEPENDENCE_RELATIONS contains the relations between the data references.
86a07404
IR		 4066 Compute read-read and self relations if
4067 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
56cf8686
SP		 4068
4069void
86a07404
IR		 4070compute_data_dependences_for_loop (struct loop *loop,
4071 bool compute_self_and_read_read_dependences,
e14b10df
SP		 4072 VEC (data_reference_p, heap) **datarefs,
4073 VEC (ddr_p, heap) **dependence_relations)
56cf8686 4074{
ba42e045 4075 VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
86a07404 4076
0ff4040e 4077 memset (&dependence_stats, 0, sizeof (dependence_stats));
56cf8686 4078
ba42e045
SP		 4079 /* If the loop nest is not well formed, or one of the data references
4080 is not computable, give up without spending time to compute other
4081 dependences. */
3cb960c7
ZD		 4082 if (!loop
4083 || !find_loop_nest (loop, &vloops)
ba42e045 4084 || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
56cf8686
SP		 4085 {
4086 struct data_dependence_relation *ddr;
4087
4088 /* Insert a single relation into dependence_relations:
4089 chrec_dont_know. */
ba42e045 4090 ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
e14b10df 4091 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
56cf8686 4092 }
ba42e045 4093 else
a84481aa 4094 compute_all_dependences (*datarefs, dependence_relations, vloops,
ebf78a47 4095 compute_self_and_read_read_dependences);
0ff4040e
SP		 4096
4097 if (dump_file && (dump_flags & TDF_STATS))
56cf8686 4098 {
0ff4040e
SP		 4099 fprintf (dump_file, "Dependence tester statistics:\n");
4100
4101 fprintf (dump_file, "Number of dependence tests: %d\n",
4102 dependence_stats.num_dependence_tests);
4103 fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4104 dependence_stats.num_dependence_dependent);
4105 fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4106 dependence_stats.num_dependence_independent);
4107 fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4108 dependence_stats.num_dependence_undetermined);
4109
4110 fprintf (dump_file, "Number of subscript tests: %d\n",
4111 dependence_stats.num_subscript_tests);
4112 fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4113 dependence_stats.num_subscript_undetermined);
4114 fprintf (dump_file, "Number of same subscript function: %d\n",
4115 dependence_stats.num_same_subscript_function);
4116
4117 fprintf (dump_file, "Number of ziv tests: %d\n",
4118 dependence_stats.num_ziv);
4119 fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4120 dependence_stats.num_ziv_dependent);
4121 fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4122 dependence_stats.num_ziv_independent);
4123 fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4124 dependence_stats.num_ziv_unimplemented);
4125
4126 fprintf (dump_file, "Number of siv tests: %d\n",
4127 dependence_stats.num_siv);
4128 fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4129 dependence_stats.num_siv_dependent);
4130 fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4131 dependence_stats.num_siv_independent);
4132 fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4133 dependence_stats.num_siv_unimplemented);
4134
4135 fprintf (dump_file, "Number of miv tests: %d\n",
4136 dependence_stats.num_miv);
4137 fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4138 dependence_stats.num_miv_dependent);
4139 fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4140 dependence_stats.num_miv_independent);
4141 fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4142 dependence_stats.num_miv_unimplemented);
4143 }
56cf8686
SP		 4144}
4145
4146/* Entry point (for testing only). Analyze all the data references
3d8864c0 4147 and the dependence relations in LOOP.
56cf8686
SP		 4148
4149 The data references are computed first.
4150
4151 A relation on these nodes is represented by a complete graph. Some
4152 of the relations could be of no interest, thus the relations can be
4153 computed on demand.
4154
4155 In the following function we compute all the relations. This is
4156 just a first implementation that is here for:
4157 - for showing how to ask for the dependence relations,
4158 - for the debugging the whole dependence graph,
4159 - for the dejagnu testcases and maintenance.
4160
4161 It is possible to ask only for a part of the graph, avoiding to
4162 compute the whole dependence graph. The computed dependences are
4163 stored in a knowledge base (KB) such that later queries don't
4164 recompute the same information. The implementation of this KB is
4165 transparent to the optimizer, and thus the KB can be changed with a
4166 more efficient implementation, or the KB could be disabled. */
0ff4040e 4167static void
3d8864c0 4168analyze_all_data_dependences (struct loop *loop)
56cf8686
SP		 4169{
4170 unsigned int i;
56cf8686 4171 int nb_data_refs = 10;
ebf78a47
SP		 4172 VEC (data_reference_p, heap) *datarefs =
4173 VEC_alloc (data_reference_p, heap, nb_data_refs);
4174 VEC (ddr_p, heap) *dependence_relations =
4175 VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
56cf8686
SP		 4176
4177 /* Compute DDs on the whole function. */
3d8864c0
SP		 4178 compute_data_dependences_for_loop (loop, false, &datarefs,
4179 &dependence_relations);
56cf8686
SP		 4180
4181 if (dump_file)
4182 {
4183 dump_data_dependence_relations (dump_file, dependence_relations);
4184 fprintf (dump_file, "\n\n");
56cf8686 4185
86df10e3
SP		 4186 if (dump_flags & TDF_DETAILS)
4187 dump_dist_dir_vectors (dump_file, dependence_relations);
56cf8686 4188
86df10e3 4189 if (dump_flags & TDF_STATS)
56cf8686 4190 {
86df10e3
SP		 4191 unsigned nb_top_relations = 0;
4192 unsigned nb_bot_relations = 0;
4193 unsigned nb_basename_differ = 0;
4194 unsigned nb_chrec_relations = 0;
ebf78a47 4195 struct data_dependence_relation *ddr;
86df10e3 4196
ebf78a47 4197 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
86df10e3 4198 {
86df10e3
SP		 4199 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4200 nb_top_relations++;
56cf8686 4201
86df10e3
SP		 4202 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4203 {
4204 struct data_reference *a = DDR_A (ddr);
4205 struct data_reference *b = DDR_B (ddr);
3cb960c7
ZD		 4206
4207 if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
86df10e3
SP		 4208 nb_basename_differ++;
4209 else
4210 nb_bot_relations++;
4211 }
56cf8686 4212
86df10e3
SP		 4213 else
4214 nb_chrec_relations++;
4215 }
56cf8686 4216
86df10e3
SP		 4217 gather_stats_on_scev_database ();
4218 }
56cf8686 4219 }
36d59cf7
DB		 4220
4221 free_dependence_relations (dependence_relations);
4222 free_data_refs (datarefs);
4223}
3d8864c0
SP		 4224
4225/* Computes all the data dependences and check that the results of
4226 several analyzers are the same. */
4227
4228void
4229tree_check_data_deps (void)
4230{
4231 loop_iterator li;
4232 struct loop *loop_nest;
4233
4234 FOR_EACH_LOOP (li, loop_nest, 0)
4235 analyze_all_data_dependences (loop_nest);
4236}
36d59cf7
DB		 4237
4238/* Free the memory used by a data dependence relation DDR. */
4239
4240void
4241free_dependence_relation (struct data_dependence_relation *ddr)
4242{
4243 if (ddr == NULL)
4244 return;
4245
4246 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
d93817c4 4247 free_subscripts (DDR_SUBSCRIPTS (ddr));
ebf78a47 4248
36d59cf7
DB		 4249 free (ddr);
4250}
4251
4252/* Free the memory used by the data dependence relations from
4253 DEPENDENCE_RELATIONS. */
4254
4255void
ebf78a47 4256free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
36d59cf7
DB		 4257{
4258 unsigned int i;
ebf78a47 4259 struct data_dependence_relation *ddr;
3ac57120 4260 VEC (loop_p, heap) *loop_nest = NULL;
36d59cf7 4261
ebf78a47 4262 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
3ac57120
JJ		 4263 {
4264 if (ddr == NULL)
4265 continue;
4266 if (loop_nest == NULL)
4267 loop_nest = DDR_LOOP_NEST (ddr);
4268 else
4269 gcc_assert (DDR_LOOP_NEST (ddr) == NULL
4270 || DDR_LOOP_NEST (ddr) == loop_nest);
4271 free_dependence_relation (ddr);
4272 }
ebf78a47 4273
3ac57120
JJ		 4274 if (loop_nest)
4275 VEC_free (loop_p, heap, loop_nest);
ebf78a47 4276 VEC_free (ddr_p, heap, dependence_relations);
56cf8686
SP		 4277}
4278
36d59cf7
DB		 4279/* Free the memory used by the data references from DATAREFS. */
4280
4281void
ebf78a47 4282free_data_refs (VEC (data_reference_p, heap) *datarefs)
36d59cf7
DB		 4283{
4284 unsigned int i;
ebf78a47 4285 struct data_reference *dr;
56cf8686 4286
ebf78a47 4287 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
8fdbc9c6 4288 free_data_ref (dr);
ebf78a47 4289 VEC_free (data_reference_p, heap, datarefs);
36d59cf7 4290}
86df10e3 4291
Mirror of https://gcc.gnu.org/git/gcc.git