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