libfuncs.h (LTI_synchronize): New libfunc_index.
[official-gcc.git] / gcc / tree-data-ref.c
blobc024b74e09cd175e6451aad943cc39cc8f54bf09
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>
5 This file is part of GCC.
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.
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.
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/>. */
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.
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).
31 The goals of this analysis are:
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),
37 - when two data references access the same data, to qualify the
38 dependence relation with classic dependence representations:
40 - distance vectors
41 - direction vectors
42 - loop carried level dependence
43 - polyhedron dependence
44 or with the chains of recurrences based representation,
46 - to define a knowledge base for storing the data dependence
47 information,
49 - to define an interface to access this data.
52 Definitions:
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).
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.
64 References:
66 - "Advanced Compilation for High Performance Computing" by Randy
67 Allen and Ken Kennedy.
68 http://citeseer.ist.psu.edu/goff91practical.html
70 - "Loop Transformations for Restructuring Compilers - The Foundations"
71 by Utpal Banerjee.
76 #include "config.h"
77 #include "system.h"
78 #include "coretypes.h"
79 #include "tm.h"
80 #include "ggc.h"
81 #include "tree.h"
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"
96 static struct datadep_stats
98 int num_dependence_tests;
99 int num_dependence_dependent;
100 int num_dependence_independent;
101 int num_dependence_undetermined;
103 int num_subscript_tests;
104 int num_subscript_undetermined;
105 int num_same_subscript_function;
107 int num_ziv;
108 int num_ziv_independent;
109 int num_ziv_dependent;
110 int num_ziv_unimplemented;
112 int num_siv;
113 int num_siv_independent;
114 int num_siv_dependent;
115 int num_siv_unimplemented;
117 int num_miv;
118 int num_miv_independent;
119 int num_miv_dependent;
120 int num_miv_unimplemented;
121 } dependence_stats;
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. */
129 static inline bool
130 tree_fold_divides_p (const_tree a, const_tree b)
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));
137 /* Returns true iff A divides B. */
139 static inline bool
140 int_divides_p (int a, int b)
142 return ((b % a) == 0);
147 /* Dump into FILE all the data references from DATAREFS. */
149 void
150 dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
152 unsigned int i;
153 struct data_reference *dr;
155 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
156 dump_data_reference (file, dr);
159 /* Dump to STDERR all the dependence relations from DDRS. */
161 void
162 debug_data_dependence_relations (VEC (ddr_p, heap) *ddrs)
164 dump_data_dependence_relations (stderr, ddrs);
167 /* Dump into FILE all the dependence relations from DDRS. */
169 void
170 dump_data_dependence_relations (FILE *file,
171 VEC (ddr_p, heap) *ddrs)
173 unsigned int i;
174 struct data_dependence_relation *ddr;
176 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
177 dump_data_dependence_relation (file, ddr);
180 /* Dump function for a DATA_REFERENCE structure. */
182 void
183 dump_data_reference (FILE *outf,
184 struct data_reference *dr)
186 unsigned int i;
188 fprintf (outf, "(Data Ref: \n stmt: ");
189 print_generic_stmt (outf, DR_STMT (dr), 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);
195 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
197 fprintf (outf, " Access function %d: ", i);
198 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
200 fprintf (outf, ")\n");
203 /* Dumps the affine function described by FN to the file OUTF. */
205 static void
206 dump_affine_function (FILE *outf, affine_fn fn)
208 unsigned i;
209 tree coef;
211 print_generic_expr (outf, VEC_index (tree, fn, 0), TDF_SLIM);
212 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
214 fprintf (outf, " + ");
215 print_generic_expr (outf, coef, TDF_SLIM);
216 fprintf (outf, " * x_%u", i);
220 /* Dumps the conflict function CF to the file OUTF. */
222 static void
223 dump_conflict_function (FILE *outf, conflict_function *cf)
225 unsigned i;
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
233 for (i = 0; i < cf->n; i++)
235 fprintf (outf, "[");
236 dump_affine_function (outf, cf->fns[i]);
237 fprintf (outf, "]\n");
242 /* Dump function for a SUBSCRIPT structure. */
244 void
245 dump_subscript (FILE *outf, struct subscript *subscript)
247 conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
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))
254 tree last_iteration = SUB_LAST_CONFLICT (subscript);
255 fprintf (outf, " last_conflict: ");
256 print_generic_stmt (outf, last_iteration, 0);
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))
264 tree last_iteration = SUB_LAST_CONFLICT (subscript);
265 fprintf (outf, " last_conflict: ");
266 print_generic_stmt (outf, last_iteration, 0);
269 fprintf (outf, " (Subscript distance: ");
270 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
271 fprintf (outf, " )\n");
272 fprintf (outf, " )\n");
275 /* Print the classic direction vector DIRV to OUTF. */
277 void
278 print_direction_vector (FILE *outf,
279 lambda_vector dirv,
280 int length)
282 int eq;
284 for (eq = 0; eq < length; eq++)
286 enum data_dependence_direction dir = dirv[eq];
288 switch (dir)
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;
316 fprintf (outf, "\n");
319 /* Print a vector of direction vectors. */
321 void
322 print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
323 int length)
325 unsigned j;
326 lambda_vector v;
328 for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++)
329 print_direction_vector (outf, v, length);
332 /* Print a vector of distance vectors. */
334 void
335 print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
336 int length)
338 unsigned j;
339 lambda_vector v;
341 for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++)
342 print_lambda_vector (outf, v, length);
345 /* Debug version. */
347 void
348 debug_data_dependence_relation (struct data_dependence_relation *ddr)
350 dump_data_dependence_relation (stderr, ddr);
353 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
355 void
356 dump_data_dependence_relation (FILE *outf,
357 struct data_dependence_relation *ddr)
359 struct data_reference *dra, *drb;
361 fprintf (outf, "(Data Dep: \n");
363 if (!ddr || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
365 fprintf (outf, " (don't know)\n)\n");
366 return;
369 dra = DDR_A (ddr);
370 drb = DDR_B (ddr);
371 dump_data_reference (outf, dra);
372 dump_data_reference (outf, drb);
374 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
375 fprintf (outf, " (no dependence)\n");
377 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
379 unsigned int i;
380 struct loop *loopi;
382 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
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));
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");
397 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
399 fprintf (outf, " distance_vector: ");
400 print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
401 DDR_NB_LOOPS (ddr));
404 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
406 fprintf (outf, " direction_vector: ");
407 print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
408 DDR_NB_LOOPS (ddr));
412 fprintf (outf, ")\n");
415 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
417 void
418 dump_data_dependence_direction (FILE *file,
419 enum data_dependence_direction dir)
421 switch (dir)
423 case dir_positive:
424 fprintf (file, "+");
425 break;
427 case dir_negative:
428 fprintf (file, "-");
429 break;
431 case dir_equal:
432 fprintf (file, "=");
433 break;
435 case dir_positive_or_negative:
436 fprintf (file, "+-");
437 break;
439 case dir_positive_or_equal:
440 fprintf (file, "+=");
441 break;
443 case dir_negative_or_equal:
444 fprintf (file, "-=");
445 break;
447 case dir_star:
448 fprintf (file, "*");
449 break;
451 default:
452 break;
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. */
461 void
462 dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
464 unsigned int i, j;
465 struct data_dependence_relation *ddr;
466 lambda_vector v;
468 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
469 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
471 for (j = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), j, v); j++)
473 fprintf (file, "DISTANCE_V (");
474 print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
475 fprintf (file, ")\n");
478 for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++)
480 fprintf (file, "DIRECTION_V (");
481 print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
482 fprintf (file, ")\n");
486 fprintf (file, "\n\n");
489 /* Dumps the data dependence relations DDRS in FILE. */
491 void
492 dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
494 unsigned int i;
495 struct data_dependence_relation *ddr;
497 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
498 dump_data_dependence_relation (file, ddr);
500 fprintf (file, "\n\n");
503 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
504 will be ssizetype. */
506 void
507 split_constant_offset (tree exp, tree *var, tree *off)
509 tree type = TREE_TYPE (exp), otype;
510 tree var0, var1;
511 tree off0, off1;
512 enum tree_code code;
514 *var = exp;
515 STRIP_NOPS (exp);
516 otype = TREE_TYPE (exp);
517 code = TREE_CODE (exp);
519 switch (code)
521 case INTEGER_CST:
522 *var = build_int_cst (type, 0);
523 *off = fold_convert (ssizetype, exp);
524 return;
526 case POINTER_PLUS_EXPR:
527 code = PLUS_EXPR;
528 /* FALLTHROUGH */
529 case PLUS_EXPR:
530 case MINUS_EXPR:
531 split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0);
532 split_constant_offset (TREE_OPERAND (exp, 1), &var1, &off1);
533 *var = fold_convert (type, fold_build2 (TREE_CODE (exp), otype,
534 var0, var1));
535 *off = size_binop (code, off0, off1);
536 return;
538 case MULT_EXPR:
539 off1 = TREE_OPERAND (exp, 1);
540 if (TREE_CODE (off1) != INTEGER_CST)
541 break;
543 split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0);
544 *var = fold_convert (type, fold_build2 (MULT_EXPR, otype,
545 var0, off1));
546 *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, off1));
547 return;
549 case ADDR_EXPR:
551 tree op, base, poffset;
552 HOST_WIDE_INT pbitsize, pbitpos;
553 enum machine_mode pmode;
554 int punsignedp, pvolatilep;
556 op = TREE_OPERAND (exp, 0);
557 if (!handled_component_p (op))
558 break;
560 base = get_inner_reference (op, &pbitsize, &pbitpos, &poffset,
561 &pmode, &punsignedp, &pvolatilep, false);
563 if (pbitpos % BITS_PER_UNIT != 0)
564 break;
565 base = build_fold_addr_expr (base);
566 off0 = ssize_int (pbitpos / BITS_PER_UNIT);
568 if (poffset)
570 split_constant_offset (poffset, &poffset, &off1);
571 off0 = size_binop (PLUS_EXPR, off0, off1);
572 if (POINTER_TYPE_P (TREE_TYPE (base)))
573 base = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (base),
574 base, fold_convert (sizetype, poffset));
575 else
576 base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base,
577 fold_convert (TREE_TYPE (base), poffset));
580 var0 = fold_convert (type, base);
582 /* If variable length types are involved, punt, otherwise casts
583 might be converted into ARRAY_REFs in gimplify_conversion.
584 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
585 possibly no longer appears in current GIMPLE, might resurface.
586 This perhaps could run
587 if (TREE_CODE (var0) == NOP_EXPR
588 || TREE_CODE (var0) == CONVERT_EXPR)
590 gimplify_conversion (&var0);
591 // Attempt to fill in any within var0 found ARRAY_REF's
592 // element size from corresponding op embedded ARRAY_REF,
593 // if unsuccessful, just punt.
594 } */
595 while (POINTER_TYPE_P (type))
596 type = TREE_TYPE (type);
597 if (int_size_in_bytes (type) < 0)
598 break;
600 *var = var0;
601 *off = off0;
602 return;
605 case SSA_NAME:
607 tree def_stmt = SSA_NAME_DEF_STMT (exp);
608 if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT)
610 tree def_stmt_rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
612 if (!TREE_SIDE_EFFECTS (def_stmt_rhs)
613 && EXPR_P (def_stmt_rhs)
614 && !REFERENCE_CLASS_P (def_stmt_rhs)
615 && !get_call_expr_in (def_stmt_rhs))
617 split_constant_offset (def_stmt_rhs, &var0, &off0);
618 var0 = fold_convert (type, var0);
619 *var = var0;
620 *off = off0;
621 return;
624 break;
627 default:
628 break;
631 *off = ssize_int (0);
634 /* Returns the address ADDR of an object in a canonical shape (without nop
635 casts, and with type of pointer to the object). */
637 static tree
638 canonicalize_base_object_address (tree addr)
640 tree orig = addr;
642 STRIP_NOPS (addr);
644 /* The base address may be obtained by casting from integer, in that case
645 keep the cast. */
646 if (!POINTER_TYPE_P (TREE_TYPE (addr)))
647 return orig;
649 if (TREE_CODE (addr) != ADDR_EXPR)
650 return addr;
652 return build_fold_addr_expr (TREE_OPERAND (addr, 0));
655 /* Analyzes the behavior of the memory reference DR in the innermost loop that
656 contains it. */
658 void
659 dr_analyze_innermost (struct data_reference *dr)
661 tree stmt = DR_STMT (dr);
662 struct loop *loop = loop_containing_stmt (stmt);
663 tree ref = DR_REF (dr);
664 HOST_WIDE_INT pbitsize, pbitpos;
665 tree base, poffset;
666 enum machine_mode pmode;
667 int punsignedp, pvolatilep;
668 affine_iv base_iv, offset_iv;
669 tree init, dinit, step;
671 if (dump_file && (dump_flags & TDF_DETAILS))
672 fprintf (dump_file, "analyze_innermost: ");
674 base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset,
675 &pmode, &punsignedp, &pvolatilep, false);
676 gcc_assert (base != NULL_TREE);
678 if (pbitpos % BITS_PER_UNIT != 0)
680 if (dump_file && (dump_flags & TDF_DETAILS))
681 fprintf (dump_file, "failed: bit offset alignment.\n");
682 return;
685 base = build_fold_addr_expr (base);
686 if (!simple_iv (loop, stmt, base, &base_iv, false))
688 if (dump_file && (dump_flags & TDF_DETAILS))
689 fprintf (dump_file, "failed: evolution of base is not affine.\n");
690 return;
692 if (!poffset)
694 offset_iv.base = ssize_int (0);
695 offset_iv.step = ssize_int (0);
697 else if (!simple_iv (loop, stmt, poffset, &offset_iv, false))
699 if (dump_file && (dump_flags & TDF_DETAILS))
700 fprintf (dump_file, "failed: evolution of offset is not affine.\n");
701 return;
704 init = ssize_int (pbitpos / BITS_PER_UNIT);
705 split_constant_offset (base_iv.base, &base_iv.base, &dinit);
706 init = size_binop (PLUS_EXPR, init, dinit);
707 split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
708 init = size_binop (PLUS_EXPR, init, dinit);
710 step = size_binop (PLUS_EXPR,
711 fold_convert (ssizetype, base_iv.step),
712 fold_convert (ssizetype, offset_iv.step));
714 DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base);
716 DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base);
717 DR_INIT (dr) = init;
718 DR_STEP (dr) = step;
720 DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base));
722 if (dump_file && (dump_flags & TDF_DETAILS))
723 fprintf (dump_file, "success.\n");
726 /* Determines the base object and the list of indices of memory reference
727 DR, analyzed in loop nest NEST. */
729 static void
730 dr_analyze_indices (struct data_reference *dr, struct loop *nest)
732 tree stmt = DR_STMT (dr);
733 struct loop *loop = loop_containing_stmt (stmt);
734 VEC (tree, heap) *access_fns = NULL;
735 tree ref = unshare_expr (DR_REF (dr)), aref = ref, op;
736 tree base, off, access_fn;
738 while (handled_component_p (aref))
740 if (TREE_CODE (aref) == ARRAY_REF)
742 op = TREE_OPERAND (aref, 1);
743 access_fn = analyze_scalar_evolution (loop, op);
744 access_fn = instantiate_scev (nest, loop, access_fn);
745 VEC_safe_push (tree, heap, access_fns, access_fn);
747 TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0);
750 aref = TREE_OPERAND (aref, 0);
753 if (INDIRECT_REF_P (aref))
755 op = TREE_OPERAND (aref, 0);
756 access_fn = analyze_scalar_evolution (loop, op);
757 access_fn = instantiate_scev (nest, loop, access_fn);
758 base = initial_condition (access_fn);
759 split_constant_offset (base, &base, &off);
760 access_fn = chrec_replace_initial_condition (access_fn,
761 fold_convert (TREE_TYPE (base), off));
763 TREE_OPERAND (aref, 0) = base;
764 VEC_safe_push (tree, heap, access_fns, access_fn);
767 DR_BASE_OBJECT (dr) = ref;
768 DR_ACCESS_FNS (dr) = access_fns;
771 /* Extracts the alias analysis information from the memory reference DR. */
773 static void
774 dr_analyze_alias (struct data_reference *dr)
776 tree stmt = DR_STMT (dr);
777 tree ref = DR_REF (dr);
778 tree base = get_base_address (ref), addr, smt = NULL_TREE;
779 ssa_op_iter it;
780 tree op;
781 bitmap vops;
783 if (DECL_P (base))
784 smt = base;
785 else if (INDIRECT_REF_P (base))
787 addr = TREE_OPERAND (base, 0);
788 if (TREE_CODE (addr) == SSA_NAME)
790 smt = symbol_mem_tag (SSA_NAME_VAR (addr));
791 DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
795 DR_SYMBOL_TAG (dr) = smt;
797 vops = BITMAP_ALLOC (NULL);
798 FOR_EACH_SSA_TREE_OPERAND (op, stmt, it, SSA_OP_VIRTUAL_USES)
800 bitmap_set_bit (vops, DECL_UID (SSA_NAME_VAR (op)));
803 DR_VOPS (dr) = vops;
806 /* Returns true if the address of DR is invariant. */
808 static bool
809 dr_address_invariant_p (struct data_reference *dr)
811 unsigned i;
812 tree idx;
814 for (i = 0; VEC_iterate (tree, DR_ACCESS_FNS (dr), i, idx); i++)
815 if (tree_contains_chrecs (idx, NULL))
816 return false;
818 return true;
821 /* Frees data reference DR. */
823 void
824 free_data_ref (data_reference_p dr)
826 BITMAP_FREE (DR_VOPS (dr));
827 VEC_free (tree, heap, DR_ACCESS_FNS (dr));
828 free (dr);
831 /* Analyzes memory reference MEMREF accessed in STMT. The reference
832 is read if IS_READ is true, write otherwise. Returns the
833 data_reference description of MEMREF. NEST is the outermost loop of the
834 loop nest in that the reference should be analyzed. */
836 struct data_reference *
837 create_data_ref (struct loop *nest, tree memref, tree stmt, bool is_read)
839 struct data_reference *dr;
841 if (dump_file && (dump_flags & TDF_DETAILS))
843 fprintf (dump_file, "Creating dr for ");
844 print_generic_expr (dump_file, memref, TDF_SLIM);
845 fprintf (dump_file, "\n");
848 dr = XCNEW (struct data_reference);
849 DR_STMT (dr) = stmt;
850 DR_REF (dr) = memref;
851 DR_IS_READ (dr) = is_read;
853 dr_analyze_innermost (dr);
854 dr_analyze_indices (dr, nest);
855 dr_analyze_alias (dr);
857 if (dump_file && (dump_flags & TDF_DETAILS))
859 fprintf (dump_file, "\tbase_address: ");
860 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
861 fprintf (dump_file, "\n\toffset from base address: ");
862 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
863 fprintf (dump_file, "\n\tconstant offset from base address: ");
864 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
865 fprintf (dump_file, "\n\tstep: ");
866 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
867 fprintf (dump_file, "\n\taligned to: ");
868 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
869 fprintf (dump_file, "\n\tbase_object: ");
870 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
871 fprintf (dump_file, "\n\tsymbol tag: ");
872 print_generic_expr (dump_file, DR_SYMBOL_TAG (dr), TDF_SLIM);
873 fprintf (dump_file, "\n");
876 return dr;
879 /* Returns true if FNA == FNB. */
881 static bool
882 affine_function_equal_p (affine_fn fna, affine_fn fnb)
884 unsigned i, n = VEC_length (tree, fna);
886 if (n != VEC_length (tree, fnb))
887 return false;
889 for (i = 0; i < n; i++)
890 if (!operand_equal_p (VEC_index (tree, fna, i),
891 VEC_index (tree, fnb, i), 0))
892 return false;
894 return true;
897 /* If all the functions in CF are the same, returns one of them,
898 otherwise returns NULL. */
900 static affine_fn
901 common_affine_function (conflict_function *cf)
903 unsigned i;
904 affine_fn comm;
906 if (!CF_NONTRIVIAL_P (cf))
907 return NULL;
909 comm = cf->fns[0];
911 for (i = 1; i < cf->n; i++)
912 if (!affine_function_equal_p (comm, cf->fns[i]))
913 return NULL;
915 return comm;
918 /* Returns the base of the affine function FN. */
920 static tree
921 affine_function_base (affine_fn fn)
923 return VEC_index (tree, fn, 0);
926 /* Returns true if FN is a constant. */
928 static bool
929 affine_function_constant_p (affine_fn fn)
931 unsigned i;
932 tree coef;
934 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
935 if (!integer_zerop (coef))
936 return false;
938 return true;
941 /* Returns true if FN is the zero constant function. */
943 static bool
944 affine_function_zero_p (affine_fn fn)
946 return (integer_zerop (affine_function_base (fn))
947 && affine_function_constant_p (fn));
950 /* Returns a signed integer type with the largest precision from TA
951 and TB. */
953 static tree
954 signed_type_for_types (tree ta, tree tb)
956 if (TYPE_PRECISION (ta) > TYPE_PRECISION (tb))
957 return signed_type_for (ta);
958 else
959 return signed_type_for (tb);
962 /* Applies operation OP on affine functions FNA and FNB, and returns the
963 result. */
965 static affine_fn
966 affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
968 unsigned i, n, m;
969 affine_fn ret;
970 tree coef;
972 if (VEC_length (tree, fnb) > VEC_length (tree, fna))
974 n = VEC_length (tree, fna);
975 m = VEC_length (tree, fnb);
977 else
979 n = VEC_length (tree, fnb);
980 m = VEC_length (tree, fna);
983 ret = VEC_alloc (tree, heap, m);
984 for (i = 0; i < n; i++)
986 tree type = signed_type_for_types (TREE_TYPE (VEC_index (tree, fna, i)),
987 TREE_TYPE (VEC_index (tree, fnb, i)));
989 VEC_quick_push (tree, ret,
990 fold_build2 (op, type,
991 VEC_index (tree, fna, i),
992 VEC_index (tree, fnb, i)));
995 for (; VEC_iterate (tree, fna, i, coef); i++)
996 VEC_quick_push (tree, ret,
997 fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
998 coef, integer_zero_node));
999 for (; VEC_iterate (tree, fnb, i, coef); i++)
1000 VEC_quick_push (tree, ret,
1001 fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
1002 integer_zero_node, coef));
1004 return ret;
1007 /* Returns the sum of affine functions FNA and FNB. */
1009 static affine_fn
1010 affine_fn_plus (affine_fn fna, affine_fn fnb)
1012 return affine_fn_op (PLUS_EXPR, fna, fnb);
1015 /* Returns the difference of affine functions FNA and FNB. */
1017 static affine_fn
1018 affine_fn_minus (affine_fn fna, affine_fn fnb)
1020 return affine_fn_op (MINUS_EXPR, fna, fnb);
1023 /* Frees affine function FN. */
1025 static void
1026 affine_fn_free (affine_fn fn)
1028 VEC_free (tree, heap, fn);
1031 /* Determine for each subscript in the data dependence relation DDR
1032 the distance. */
1034 static void
1035 compute_subscript_distance (struct data_dependence_relation *ddr)
1037 conflict_function *cf_a, *cf_b;
1038 affine_fn fn_a, fn_b, diff;
1040 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1042 unsigned int i;
1044 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1046 struct subscript *subscript;
1048 subscript = DDR_SUBSCRIPT (ddr, i);
1049 cf_a = SUB_CONFLICTS_IN_A (subscript);
1050 cf_b = SUB_CONFLICTS_IN_B (subscript);
1052 fn_a = common_affine_function (cf_a);
1053 fn_b = common_affine_function (cf_b);
1054 if (!fn_a || !fn_b)
1056 SUB_DISTANCE (subscript) = chrec_dont_know;
1057 return;
1059 diff = affine_fn_minus (fn_a, fn_b);
1061 if (affine_function_constant_p (diff))
1062 SUB_DISTANCE (subscript) = affine_function_base (diff);
1063 else
1064 SUB_DISTANCE (subscript) = chrec_dont_know;
1066 affine_fn_free (diff);
1071 /* Returns the conflict function for "unknown". */
1073 static conflict_function *
1074 conflict_fn_not_known (void)
1076 conflict_function *fn = XCNEW (conflict_function);
1077 fn->n = NOT_KNOWN;
1079 return fn;
1082 /* Returns the conflict function for "independent". */
1084 static conflict_function *
1085 conflict_fn_no_dependence (void)
1087 conflict_function *fn = XCNEW (conflict_function);
1088 fn->n = NO_DEPENDENCE;
1090 return fn;
1093 /* Returns true if the address of OBJ is invariant in LOOP. */
1095 static bool
1096 object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj)
1098 while (handled_component_p (obj))
1100 if (TREE_CODE (obj) == ARRAY_REF)
1102 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1103 need to check the stride and the lower bound of the reference. */
1104 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1105 loop->num)
1106 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 3),
1107 loop->num))
1108 return false;
1110 else if (TREE_CODE (obj) == COMPONENT_REF)
1112 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1113 loop->num))
1114 return false;
1116 obj = TREE_OPERAND (obj, 0);
1119 if (!INDIRECT_REF_P (obj))
1120 return true;
1122 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0),
1123 loop->num);
1126 /* Returns true if A and B are accesses to different objects, or to different
1127 fields of the same object. */
1129 static bool
1130 disjoint_objects_p (tree a, tree b)
1132 tree base_a, base_b;
1133 VEC (tree, heap) *comp_a = NULL, *comp_b = NULL;
1134 bool ret;
1136 base_a = get_base_address (a);
1137 base_b = get_base_address (b);
1139 if (DECL_P (base_a)
1140 && DECL_P (base_b)
1141 && base_a != base_b)
1142 return true;
1144 if (!operand_equal_p (base_a, base_b, 0))
1145 return false;
1147 /* Compare the component references of A and B. We must start from the inner
1148 ones, so record them to the vector first. */
1149 while (handled_component_p (a))
1151 VEC_safe_push (tree, heap, comp_a, a);
1152 a = TREE_OPERAND (a, 0);
1154 while (handled_component_p (b))
1156 VEC_safe_push (tree, heap, comp_b, b);
1157 b = TREE_OPERAND (b, 0);
1160 ret = false;
1161 while (1)
1163 if (VEC_length (tree, comp_a) == 0
1164 || VEC_length (tree, comp_b) == 0)
1165 break;
1167 a = VEC_pop (tree, comp_a);
1168 b = VEC_pop (tree, comp_b);
1170 /* Real and imaginary part of a variable do not alias. */
1171 if ((TREE_CODE (a) == REALPART_EXPR
1172 && TREE_CODE (b) == IMAGPART_EXPR)
1173 || (TREE_CODE (a) == IMAGPART_EXPR
1174 && TREE_CODE (b) == REALPART_EXPR))
1176 ret = true;
1177 break;
1180 if (TREE_CODE (a) != TREE_CODE (b))
1181 break;
1183 /* Nothing to do for ARRAY_REFs, as the indices of array_refs in
1184 DR_BASE_OBJECT are always zero. */
1185 if (TREE_CODE (a) == ARRAY_REF)
1186 continue;
1187 else if (TREE_CODE (a) == COMPONENT_REF)
1189 if (operand_equal_p (TREE_OPERAND (a, 1), TREE_OPERAND (b, 1), 0))
1190 continue;
1192 /* Different fields of unions may overlap. */
1193 base_a = TREE_OPERAND (a, 0);
1194 if (TREE_CODE (TREE_TYPE (base_a)) == UNION_TYPE)
1195 break;
1197 /* Different fields of structures cannot. */
1198 ret = true;
1199 break;
1201 else
1202 break;
1205 VEC_free (tree, heap, comp_a);
1206 VEC_free (tree, heap, comp_b);
1208 return ret;
1211 /* Returns false if we can prove that data references A and B do not alias,
1212 true otherwise. */
1214 static bool
1215 dr_may_alias_p (const struct data_reference *a, const struct data_reference *b)
1217 const_tree addr_a = DR_BASE_ADDRESS (a);
1218 const_tree addr_b = DR_BASE_ADDRESS (b);
1219 const_tree type_a, type_b;
1220 const_tree decl_a = NULL_TREE, decl_b = NULL_TREE;
1222 /* If the sets of virtual operands are disjoint, the memory references do not
1223 alias. */
1224 if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
1225 return false;
1227 /* If the accessed objects are disjoint, the memory references do not
1228 alias. */
1229 if (disjoint_objects_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b)))
1230 return false;
1232 if (!addr_a || !addr_b)
1233 return true;
1235 /* If the references are based on different static objects, they cannot alias
1236 (PTA should be able to disambiguate such accesses, but often it fails to,
1237 since currently we cannot distinguish between pointer and offset in pointer
1238 arithmetics). */
1239 if (TREE_CODE (addr_a) == ADDR_EXPR
1240 && TREE_CODE (addr_b) == ADDR_EXPR)
1241 return TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0);
1243 /* An instruction writing through a restricted pointer is "independent" of any
1244 instruction reading or writing through a different restricted pointer,
1245 in the same block/scope. */
1247 type_a = TREE_TYPE (addr_a);
1248 type_b = TREE_TYPE (addr_b);
1249 gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
1251 if (TREE_CODE (addr_a) == SSA_NAME)
1252 decl_a = SSA_NAME_VAR (addr_a);
1253 if (TREE_CODE (addr_b) == SSA_NAME)
1254 decl_b = SSA_NAME_VAR (addr_b);
1256 if (TYPE_RESTRICT (type_a) && TYPE_RESTRICT (type_b)
1257 && (!DR_IS_READ (a) || !DR_IS_READ (b))
1258 && decl_a && DECL_P (decl_a)
1259 && decl_b && DECL_P (decl_b)
1260 && decl_a != decl_b
1261 && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL
1262 && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b))
1263 return false;
1265 return true;
1268 static void compute_self_dependence (struct data_dependence_relation *);
1270 /* Initialize a data dependence relation between data accesses A and
1271 B. NB_LOOPS is the number of loops surrounding the references: the
1272 size of the classic distance/direction vectors. */
1274 static struct data_dependence_relation *
1275 initialize_data_dependence_relation (struct data_reference *a,
1276 struct data_reference *b,
1277 VEC (loop_p, heap) *loop_nest)
1279 struct data_dependence_relation *res;
1280 unsigned int i;
1282 res = XNEW (struct data_dependence_relation);
1283 DDR_A (res) = a;
1284 DDR_B (res) = b;
1285 DDR_LOOP_NEST (res) = NULL;
1286 DDR_REVERSED_P (res) = false;
1287 DDR_SUBSCRIPTS (res) = NULL;
1288 DDR_DIR_VECTS (res) = NULL;
1289 DDR_DIST_VECTS (res) = NULL;
1291 if (a == NULL || b == NULL)
1293 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1294 return res;
1297 /* If the data references do not alias, then they are independent. */
1298 if (!dr_may_alias_p (a, b))
1300 DDR_ARE_DEPENDENT (res) = chrec_known;
1301 return res;
1304 /* When the references are exactly the same, don't spend time doing
1305 the data dependence tests, just initialize the ddr and return. */
1306 if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
1308 DDR_AFFINE_P (res) = true;
1309 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1310 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
1311 DDR_LOOP_NEST (res) = loop_nest;
1312 DDR_INNER_LOOP (res) = 0;
1313 DDR_SELF_REFERENCE (res) = true;
1314 compute_self_dependence (res);
1315 return res;
1318 /* If the references do not access the same object, we do not know
1319 whether they alias or not. */
1320 if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0))
1322 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1323 return res;
1326 /* If the base of the object is not invariant in the loop nest, we cannot
1327 analyze it. TODO -- in fact, it would suffice to record that there may
1328 be arbitrary dependences in the loops where the base object varies. */
1329 if (!object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
1330 DR_BASE_OBJECT (a)))
1332 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1333 return res;
1336 gcc_assert (DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b));
1338 DDR_AFFINE_P (res) = true;
1339 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1340 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
1341 DDR_LOOP_NEST (res) = loop_nest;
1342 DDR_INNER_LOOP (res) = 0;
1343 DDR_SELF_REFERENCE (res) = false;
1345 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1347 struct subscript *subscript;
1349 subscript = XNEW (struct subscript);
1350 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
1351 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
1352 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1353 SUB_DISTANCE (subscript) = chrec_dont_know;
1354 VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
1357 return res;
1360 /* Frees memory used by the conflict function F. */
1362 static void
1363 free_conflict_function (conflict_function *f)
1365 unsigned i;
1367 if (CF_NONTRIVIAL_P (f))
1369 for (i = 0; i < f->n; i++)
1370 affine_fn_free (f->fns[i]);
1372 free (f);
1375 /* Frees memory used by SUBSCRIPTS. */
1377 static void
1378 free_subscripts (VEC (subscript_p, heap) *subscripts)
1380 unsigned i;
1381 subscript_p s;
1383 for (i = 0; VEC_iterate (subscript_p, subscripts, i, s); i++)
1385 free_conflict_function (s->conflicting_iterations_in_a);
1386 free_conflict_function (s->conflicting_iterations_in_b);
1388 VEC_free (subscript_p, heap, subscripts);
1391 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1392 description. */
1394 static inline void
1395 finalize_ddr_dependent (struct data_dependence_relation *ddr,
1396 tree chrec)
1398 if (dump_file && (dump_flags & TDF_DETAILS))
1400 fprintf (dump_file, "(dependence classified: ");
1401 print_generic_expr (dump_file, chrec, 0);
1402 fprintf (dump_file, ")\n");
1405 DDR_ARE_DEPENDENT (ddr) = chrec;
1406 free_subscripts (DDR_SUBSCRIPTS (ddr));
1407 DDR_SUBSCRIPTS (ddr) = NULL;
1410 /* The dependence relation DDR cannot be represented by a distance
1411 vector. */
1413 static inline void
1414 non_affine_dependence_relation (struct data_dependence_relation *ddr)
1416 if (dump_file && (dump_flags & TDF_DETAILS))
1417 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
1419 DDR_AFFINE_P (ddr) = false;
1424 /* This section contains the classic Banerjee tests. */
1426 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1427 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1429 static inline bool
1430 ziv_subscript_p (const_tree chrec_a, const_tree chrec_b)
1432 return (evolution_function_is_constant_p (chrec_a)
1433 && evolution_function_is_constant_p (chrec_b));
1436 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1437 variable, i.e., if the SIV (Single Index Variable) test is true. */
1439 static bool
1440 siv_subscript_p (const_tree chrec_a, const_tree chrec_b)
1442 if ((evolution_function_is_constant_p (chrec_a)
1443 && evolution_function_is_univariate_p (chrec_b))
1444 || (evolution_function_is_constant_p (chrec_b)
1445 && evolution_function_is_univariate_p (chrec_a)))
1446 return true;
1448 if (evolution_function_is_univariate_p (chrec_a)
1449 && evolution_function_is_univariate_p (chrec_b))
1451 switch (TREE_CODE (chrec_a))
1453 case POLYNOMIAL_CHREC:
1454 switch (TREE_CODE (chrec_b))
1456 case POLYNOMIAL_CHREC:
1457 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
1458 return false;
1460 default:
1461 return true;
1464 default:
1465 return true;
1469 return false;
1472 /* Creates a conflict function with N dimensions. The affine functions
1473 in each dimension follow. */
1475 static conflict_function *
1476 conflict_fn (unsigned n, ...)
1478 unsigned i;
1479 conflict_function *ret = XCNEW (conflict_function);
1480 va_list ap;
1482 gcc_assert (0 < n && n <= MAX_DIM);
1483 va_start(ap, n);
1485 ret->n = n;
1486 for (i = 0; i < n; i++)
1487 ret->fns[i] = va_arg (ap, affine_fn);
1488 va_end(ap);
1490 return ret;
1493 /* Returns constant affine function with value CST. */
1495 static affine_fn
1496 affine_fn_cst (tree cst)
1498 affine_fn fn = VEC_alloc (tree, heap, 1);
1499 VEC_quick_push (tree, fn, cst);
1500 return fn;
1503 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1505 static affine_fn
1506 affine_fn_univar (tree cst, unsigned dim, tree coef)
1508 affine_fn fn = VEC_alloc (tree, heap, dim + 1);
1509 unsigned i;
1511 gcc_assert (dim > 0);
1512 VEC_quick_push (tree, fn, cst);
1513 for (i = 1; i < dim; i++)
1514 VEC_quick_push (tree, fn, integer_zero_node);
1515 VEC_quick_push (tree, fn, coef);
1516 return fn;
1519 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1520 *OVERLAPS_B are initialized to the functions that describe the
1521 relation between the elements accessed twice by CHREC_A and
1522 CHREC_B. For k >= 0, the following property is verified:
1524 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1526 static void
1527 analyze_ziv_subscript (tree chrec_a,
1528 tree chrec_b,
1529 conflict_function **overlaps_a,
1530 conflict_function **overlaps_b,
1531 tree *last_conflicts)
1533 tree type, difference;
1534 dependence_stats.num_ziv++;
1536 if (dump_file && (dump_flags & TDF_DETAILS))
1537 fprintf (dump_file, "(analyze_ziv_subscript \n");
1539 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
1540 chrec_a = chrec_convert (type, chrec_a, NULL_TREE);
1541 chrec_b = chrec_convert (type, chrec_b, NULL_TREE);
1542 difference = chrec_fold_minus (type, chrec_a, chrec_b);
1544 switch (TREE_CODE (difference))
1546 case INTEGER_CST:
1547 if (integer_zerop (difference))
1549 /* The difference is equal to zero: the accessed index
1550 overlaps for each iteration in the loop. */
1551 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1552 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1553 *last_conflicts = chrec_dont_know;
1554 dependence_stats.num_ziv_dependent++;
1556 else
1558 /* The accesses do not overlap. */
1559 *overlaps_a = conflict_fn_no_dependence ();
1560 *overlaps_b = conflict_fn_no_dependence ();
1561 *last_conflicts = integer_zero_node;
1562 dependence_stats.num_ziv_independent++;
1564 break;
1566 default:
1567 /* We're not sure whether the indexes overlap. For the moment,
1568 conservatively answer "don't know". */
1569 if (dump_file && (dump_flags & TDF_DETAILS))
1570 fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
1572 *overlaps_a = conflict_fn_not_known ();
1573 *overlaps_b = conflict_fn_not_known ();
1574 *last_conflicts = chrec_dont_know;
1575 dependence_stats.num_ziv_unimplemented++;
1576 break;
1579 if (dump_file && (dump_flags & TDF_DETAILS))
1580 fprintf (dump_file, ")\n");
1583 /* Sets NIT to the estimated number of executions of the statements in
1584 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
1585 large as the number of iterations. If we have no reliable estimate,
1586 the function returns false, otherwise returns true. */
1588 bool
1589 estimated_loop_iterations (struct loop *loop, bool conservative,
1590 double_int *nit)
1592 estimate_numbers_of_iterations_loop (loop);
1593 if (conservative)
1595 if (!loop->any_upper_bound)
1596 return false;
1598 *nit = loop->nb_iterations_upper_bound;
1600 else
1602 if (!loop->any_estimate)
1603 return false;
1605 *nit = loop->nb_iterations_estimate;
1608 return true;
1611 /* Similar to estimated_loop_iterations, but returns the estimate only
1612 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1613 on the number of iterations of LOOP could not be derived, returns -1. */
1615 HOST_WIDE_INT
1616 estimated_loop_iterations_int (struct loop *loop, bool conservative)
1618 double_int nit;
1619 HOST_WIDE_INT hwi_nit;
1621 if (!estimated_loop_iterations (loop, conservative, &nit))
1622 return -1;
1624 if (!double_int_fits_in_shwi_p (nit))
1625 return -1;
1626 hwi_nit = double_int_to_shwi (nit);
1628 return hwi_nit < 0 ? -1 : hwi_nit;
1631 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
1632 and only if it fits to the int type. If this is not the case, or the
1633 estimate on the number of iterations of LOOP could not be derived, returns
1634 chrec_dont_know. */
1636 static tree
1637 estimated_loop_iterations_tree (struct loop *loop, bool conservative)
1639 double_int nit;
1640 tree type;
1642 if (!estimated_loop_iterations (loop, conservative, &nit))
1643 return chrec_dont_know;
1645 type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
1646 if (!double_int_fits_to_tree_p (type, nit))
1647 return chrec_dont_know;
1649 return double_int_to_tree (type, nit);
1652 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1653 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1654 *OVERLAPS_B are initialized to the functions that describe the
1655 relation between the elements accessed twice by CHREC_A and
1656 CHREC_B. For k >= 0, the following property is verified:
1658 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1660 static void
1661 analyze_siv_subscript_cst_affine (tree chrec_a,
1662 tree chrec_b,
1663 conflict_function **overlaps_a,
1664 conflict_function **overlaps_b,
1665 tree *last_conflicts)
1667 bool value0, value1, value2;
1668 tree type, difference, tmp;
1670 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
1671 chrec_a = chrec_convert (type, chrec_a, NULL_TREE);
1672 chrec_b = chrec_convert (type, chrec_b, NULL_TREE);
1673 difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a);
1675 if (!chrec_is_positive (initial_condition (difference), &value0))
1677 if (dump_file && (dump_flags & TDF_DETAILS))
1678 fprintf (dump_file, "siv test failed: chrec is not positive.\n");
1680 dependence_stats.num_siv_unimplemented++;
1681 *overlaps_a = conflict_fn_not_known ();
1682 *overlaps_b = conflict_fn_not_known ();
1683 *last_conflicts = chrec_dont_know;
1684 return;
1686 else
1688 if (value0 == false)
1690 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
1692 if (dump_file && (dump_flags & TDF_DETAILS))
1693 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1695 *overlaps_a = conflict_fn_not_known ();
1696 *overlaps_b = conflict_fn_not_known ();
1697 *last_conflicts = chrec_dont_know;
1698 dependence_stats.num_siv_unimplemented++;
1699 return;
1701 else
1703 if (value1 == true)
1705 /* Example:
1706 chrec_a = 12
1707 chrec_b = {10, +, 1}
1710 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1712 HOST_WIDE_INT numiter;
1713 struct loop *loop = get_chrec_loop (chrec_b);
1715 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1716 tmp = fold_build2 (EXACT_DIV_EXPR, type,
1717 fold_build1 (ABS_EXPR, type, difference),
1718 CHREC_RIGHT (chrec_b));
1719 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1720 *last_conflicts = integer_one_node;
1723 /* Perform weak-zero siv test to see if overlap is
1724 outside the loop bounds. */
1725 numiter = estimated_loop_iterations_int (loop, false);
1727 if (numiter >= 0
1728 && compare_tree_int (tmp, numiter) > 0)
1730 free_conflict_function (*overlaps_a);
1731 free_conflict_function (*overlaps_b);
1732 *overlaps_a = conflict_fn_no_dependence ();
1733 *overlaps_b = conflict_fn_no_dependence ();
1734 *last_conflicts = integer_zero_node;
1735 dependence_stats.num_siv_independent++;
1736 return;
1738 dependence_stats.num_siv_dependent++;
1739 return;
1742 /* When the step does not divide the difference, there are
1743 no overlaps. */
1744 else
1746 *overlaps_a = conflict_fn_no_dependence ();
1747 *overlaps_b = conflict_fn_no_dependence ();
1748 *last_conflicts = integer_zero_node;
1749 dependence_stats.num_siv_independent++;
1750 return;
1754 else
1756 /* Example:
1757 chrec_a = 12
1758 chrec_b = {10, +, -1}
1760 In this case, chrec_a will not overlap with chrec_b. */
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;
1769 else
1771 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
1773 if (dump_file && (dump_flags & TDF_DETAILS))
1774 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1776 *overlaps_a = conflict_fn_not_known ();
1777 *overlaps_b = conflict_fn_not_known ();
1778 *last_conflicts = chrec_dont_know;
1779 dependence_stats.num_siv_unimplemented++;
1780 return;
1782 else
1784 if (value2 == false)
1786 /* Example:
1787 chrec_a = 3
1788 chrec_b = {10, +, -1}
1790 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1792 HOST_WIDE_INT numiter;
1793 struct loop *loop = get_chrec_loop (chrec_b);
1795 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1796 tmp = fold_build2 (EXACT_DIV_EXPR, type, difference,
1797 CHREC_RIGHT (chrec_b));
1798 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1799 *last_conflicts = integer_one_node;
1801 /* Perform weak-zero siv test to see if overlap is
1802 outside the loop bounds. */
1803 numiter = estimated_loop_iterations_int (loop, false);
1805 if (numiter >= 0
1806 && compare_tree_int (tmp, numiter) > 0)
1808 free_conflict_function (*overlaps_a);
1809 free_conflict_function (*overlaps_b);
1810 *overlaps_a = conflict_fn_no_dependence ();
1811 *overlaps_b = conflict_fn_no_dependence ();
1812 *last_conflicts = integer_zero_node;
1813 dependence_stats.num_siv_independent++;
1814 return;
1816 dependence_stats.num_siv_dependent++;
1817 return;
1820 /* When the step does not divide the difference, there
1821 are no overlaps. */
1822 else
1824 *overlaps_a = conflict_fn_no_dependence ();
1825 *overlaps_b = conflict_fn_no_dependence ();
1826 *last_conflicts = integer_zero_node;
1827 dependence_stats.num_siv_independent++;
1828 return;
1831 else
1833 /* Example:
1834 chrec_a = 3
1835 chrec_b = {4, +, 1}
1837 In this case, chrec_a will not overlap with chrec_b. */
1838 *overlaps_a = conflict_fn_no_dependence ();
1839 *overlaps_b = conflict_fn_no_dependence ();
1840 *last_conflicts = integer_zero_node;
1841 dependence_stats.num_siv_independent++;
1842 return;
1849 /* Helper recursive function for initializing the matrix A. Returns
1850 the initial value of CHREC. */
1852 static tree
1853 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
1855 gcc_assert (chrec);
1857 switch (TREE_CODE (chrec))
1859 case POLYNOMIAL_CHREC:
1860 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST);
1862 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
1863 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
1865 case PLUS_EXPR:
1866 case MULT_EXPR:
1867 case MINUS_EXPR:
1869 tree op0 = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
1870 tree op1 = initialize_matrix_A (A, TREE_OPERAND (chrec, 1), index, mult);
1872 return chrec_fold_op (TREE_CODE (chrec), chrec_type (chrec), op0, op1);
1875 case NOP_EXPR:
1877 tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
1878 return chrec_convert (chrec_type (chrec), op, NULL_TREE);
1881 case INTEGER_CST:
1882 return chrec;
1884 default:
1885 gcc_unreachable ();
1886 return NULL_TREE;
1890 #define FLOOR_DIV(x,y) ((x) / (y))
1892 /* Solves the special case of the Diophantine equation:
1893 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1895 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1896 number of iterations that loops X and Y run. The overlaps will be
1897 constructed as evolutions in dimension DIM. */
1899 static void
1900 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
1901 affine_fn *overlaps_a,
1902 affine_fn *overlaps_b,
1903 tree *last_conflicts, int dim)
1905 if (((step_a > 0 && step_b > 0)
1906 || (step_a < 0 && step_b < 0)))
1908 int step_overlaps_a, step_overlaps_b;
1909 int gcd_steps_a_b, last_conflict, tau2;
1911 gcd_steps_a_b = gcd (step_a, step_b);
1912 step_overlaps_a = step_b / gcd_steps_a_b;
1913 step_overlaps_b = step_a / gcd_steps_a_b;
1915 if (niter > 0)
1917 tau2 = FLOOR_DIV (niter, step_overlaps_a);
1918 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
1919 last_conflict = tau2;
1920 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
1922 else
1923 *last_conflicts = chrec_dont_know;
1925 *overlaps_a = affine_fn_univar (integer_zero_node, dim,
1926 build_int_cst (NULL_TREE,
1927 step_overlaps_a));
1928 *overlaps_b = affine_fn_univar (integer_zero_node, dim,
1929 build_int_cst (NULL_TREE,
1930 step_overlaps_b));
1933 else
1935 *overlaps_a = affine_fn_cst (integer_zero_node);
1936 *overlaps_b = affine_fn_cst (integer_zero_node);
1937 *last_conflicts = integer_zero_node;
1941 /* Solves the special case of a Diophantine equation where CHREC_A is
1942 an affine bivariate function, and CHREC_B is an affine univariate
1943 function. For example,
1945 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1947 has the following overlapping functions:
1949 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1950 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1951 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1953 FORNOW: This is a specialized implementation for a case occurring in
1954 a common benchmark. Implement the general algorithm. */
1956 static void
1957 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
1958 conflict_function **overlaps_a,
1959 conflict_function **overlaps_b,
1960 tree *last_conflicts)
1962 bool xz_p, yz_p, xyz_p;
1963 int step_x, step_y, step_z;
1964 HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
1965 affine_fn overlaps_a_xz, overlaps_b_xz;
1966 affine_fn overlaps_a_yz, overlaps_b_yz;
1967 affine_fn overlaps_a_xyz, overlaps_b_xyz;
1968 affine_fn ova1, ova2, ovb;
1969 tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
1971 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
1972 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
1973 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
1975 niter_x =
1976 estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a)),
1977 false);
1978 niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), false);
1979 niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), false);
1981 if (niter_x < 0 || niter_y < 0 || niter_z < 0)
1983 if (dump_file && (dump_flags & TDF_DETAILS))
1984 fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
1986 *overlaps_a = conflict_fn_not_known ();
1987 *overlaps_b = conflict_fn_not_known ();
1988 *last_conflicts = chrec_dont_know;
1989 return;
1992 niter = MIN (niter_x, niter_z);
1993 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
1994 &overlaps_a_xz,
1995 &overlaps_b_xz,
1996 &last_conflicts_xz, 1);
1997 niter = MIN (niter_y, niter_z);
1998 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
1999 &overlaps_a_yz,
2000 &overlaps_b_yz,
2001 &last_conflicts_yz, 2);
2002 niter = MIN (niter_x, niter_z);
2003 niter = MIN (niter_y, niter);
2004 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2005 &overlaps_a_xyz,
2006 &overlaps_b_xyz,
2007 &last_conflicts_xyz, 3);
2009 xz_p = !integer_zerop (last_conflicts_xz);
2010 yz_p = !integer_zerop (last_conflicts_yz);
2011 xyz_p = !integer_zerop (last_conflicts_xyz);
2013 if (xz_p || yz_p || xyz_p)
2015 ova1 = affine_fn_cst (integer_zero_node);
2016 ova2 = affine_fn_cst (integer_zero_node);
2017 ovb = affine_fn_cst (integer_zero_node);
2018 if (xz_p)
2020 affine_fn t0 = ova1;
2021 affine_fn t2 = ovb;
2023 ova1 = affine_fn_plus (ova1, overlaps_a_xz);
2024 ovb = affine_fn_plus (ovb, overlaps_b_xz);
2025 affine_fn_free (t0);
2026 affine_fn_free (t2);
2027 *last_conflicts = last_conflicts_xz;
2029 if (yz_p)
2031 affine_fn t0 = ova2;
2032 affine_fn t2 = ovb;
2034 ova2 = affine_fn_plus (ova2, overlaps_a_yz);
2035 ovb = affine_fn_plus (ovb, overlaps_b_yz);
2036 affine_fn_free (t0);
2037 affine_fn_free (t2);
2038 *last_conflicts = last_conflicts_yz;
2040 if (xyz_p)
2042 affine_fn t0 = ova1;
2043 affine_fn t2 = ova2;
2044 affine_fn t4 = ovb;
2046 ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
2047 ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
2048 ovb = affine_fn_plus (ovb, overlaps_b_xyz);
2049 affine_fn_free (t0);
2050 affine_fn_free (t2);
2051 affine_fn_free (t4);
2052 *last_conflicts = last_conflicts_xyz;
2054 *overlaps_a = conflict_fn (2, ova1, ova2);
2055 *overlaps_b = conflict_fn (1, ovb);
2057 else
2059 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2060 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2061 *last_conflicts = integer_zero_node;
2064 affine_fn_free (overlaps_a_xz);
2065 affine_fn_free (overlaps_b_xz);
2066 affine_fn_free (overlaps_a_yz);
2067 affine_fn_free (overlaps_b_yz);
2068 affine_fn_free (overlaps_a_xyz);
2069 affine_fn_free (overlaps_b_xyz);
2072 /* Determines the overlapping elements due to accesses CHREC_A and
2073 CHREC_B, that are affine functions. This function cannot handle
2074 symbolic evolution functions, ie. when initial conditions are
2075 parameters, because it uses lambda matrices of integers. */
2077 static void
2078 analyze_subscript_affine_affine (tree chrec_a,
2079 tree chrec_b,
2080 conflict_function **overlaps_a,
2081 conflict_function **overlaps_b,
2082 tree *last_conflicts)
2084 unsigned nb_vars_a, nb_vars_b, dim;
2085 HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta;
2086 lambda_matrix A, U, S;
2088 if (eq_evolutions_p (chrec_a, chrec_b))
2090 /* The accessed index overlaps for each iteration in the
2091 loop. */
2092 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2093 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2094 *last_conflicts = chrec_dont_know;
2095 return;
2097 if (dump_file && (dump_flags & TDF_DETAILS))
2098 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2100 /* For determining the initial intersection, we have to solve a
2101 Diophantine equation. This is the most time consuming part.
2103 For answering to the question: "Is there a dependence?" we have
2104 to prove that there exists a solution to the Diophantine
2105 equation, and that the solution is in the iteration domain,
2106 i.e. the solution is positive or zero, and that the solution
2107 happens before the upper bound loop.nb_iterations. Otherwise
2108 there is no dependence. This function outputs a description of
2109 the iterations that hold the intersections. */
2111 nb_vars_a = nb_vars_in_chrec (chrec_a);
2112 nb_vars_b = nb_vars_in_chrec (chrec_b);
2114 dim = nb_vars_a + nb_vars_b;
2115 U = lambda_matrix_new (dim, dim);
2116 A = lambda_matrix_new (dim, 1);
2117 S = lambda_matrix_new (dim, 1);
2119 init_a = int_cst_value (initialize_matrix_A (A, chrec_a, 0, 1));
2120 init_b = int_cst_value (initialize_matrix_A (A, chrec_b, nb_vars_a, -1));
2121 gamma = init_b - init_a;
2123 /* Don't do all the hard work of solving the Diophantine equation
2124 when we already know the solution: for example,
2125 | {3, +, 1}_1
2126 | {3, +, 4}_2
2127 | gamma = 3 - 3 = 0.
2128 Then the first overlap occurs during the first iterations:
2129 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2131 if (gamma == 0)
2133 if (nb_vars_a == 1 && nb_vars_b == 1)
2135 HOST_WIDE_INT step_a, step_b;
2136 HOST_WIDE_INT niter, niter_a, niter_b;
2137 affine_fn ova, ovb;
2139 niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a),
2140 false);
2141 niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b),
2142 false);
2143 niter = MIN (niter_a, niter_b);
2144 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2145 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2147 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2148 &ova, &ovb,
2149 last_conflicts, 1);
2150 *overlaps_a = conflict_fn (1, ova);
2151 *overlaps_b = conflict_fn (1, ovb);
2154 else if (nb_vars_a == 2 && nb_vars_b == 1)
2155 compute_overlap_steps_for_affine_1_2
2156 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2158 else if (nb_vars_a == 1 && nb_vars_b == 2)
2159 compute_overlap_steps_for_affine_1_2
2160 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2162 else
2164 if (dump_file && (dump_flags & TDF_DETAILS))
2165 fprintf (dump_file, "affine-affine test failed: too many variables.\n");
2166 *overlaps_a = conflict_fn_not_known ();
2167 *overlaps_b = conflict_fn_not_known ();
2168 *last_conflicts = chrec_dont_know;
2170 goto end_analyze_subs_aa;
2173 /* U.A = S */
2174 lambda_matrix_right_hermite (A, dim, 1, S, U);
2176 if (S[0][0] < 0)
2178 S[0][0] *= -1;
2179 lambda_matrix_row_negate (U, dim, 0);
2181 gcd_alpha_beta = S[0][0];
2183 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2184 but that is a quite strange case. Instead of ICEing, answer
2185 don't know. */
2186 if (gcd_alpha_beta == 0)
2188 *overlaps_a = conflict_fn_not_known ();
2189 *overlaps_b = conflict_fn_not_known ();
2190 *last_conflicts = chrec_dont_know;
2191 goto end_analyze_subs_aa;
2194 /* The classic "gcd-test". */
2195 if (!int_divides_p (gcd_alpha_beta, gamma))
2197 /* The "gcd-test" has determined that there is no integer
2198 solution, i.e. there is no dependence. */
2199 *overlaps_a = conflict_fn_no_dependence ();
2200 *overlaps_b = conflict_fn_no_dependence ();
2201 *last_conflicts = integer_zero_node;
2204 /* Both access functions are univariate. This includes SIV and MIV cases. */
2205 else if (nb_vars_a == 1 && nb_vars_b == 1)
2207 /* Both functions should have the same evolution sign. */
2208 if (((A[0][0] > 0 && -A[1][0] > 0)
2209 || (A[0][0] < 0 && -A[1][0] < 0)))
2211 /* The solutions are given by:
2213 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2214 | [u21 u22] [y0]
2216 For a given integer t. Using the following variables,
2218 | i0 = u11 * gamma / gcd_alpha_beta
2219 | j0 = u12 * gamma / gcd_alpha_beta
2220 | i1 = u21
2221 | j1 = u22
2223 the solutions are:
2225 | x0 = i0 + i1 * t,
2226 | y0 = j0 + j1 * t. */
2227 HOST_WIDE_INT i0, j0, i1, j1;
2229 i0 = U[0][0] * gamma / gcd_alpha_beta;
2230 j0 = U[0][1] * gamma / gcd_alpha_beta;
2231 i1 = U[1][0];
2232 j1 = U[1][1];
2234 if ((i1 == 0 && i0 < 0)
2235 || (j1 == 0 && j0 < 0))
2237 /* There is no solution.
2238 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2239 falls in here, but for the moment we don't look at the
2240 upper bound of the iteration domain. */
2241 *overlaps_a = conflict_fn_no_dependence ();
2242 *overlaps_b = conflict_fn_no_dependence ();
2243 *last_conflicts = integer_zero_node;
2244 goto end_analyze_subs_aa;
2247 if (i1 > 0 && j1 > 0)
2249 HOST_WIDE_INT niter_a = estimated_loop_iterations_int
2250 (get_chrec_loop (chrec_a), false);
2251 HOST_WIDE_INT niter_b = estimated_loop_iterations_int
2252 (get_chrec_loop (chrec_b), false);
2253 HOST_WIDE_INT niter = MIN (niter_a, niter_b);
2255 /* (X0, Y0) is a solution of the Diophantine equation:
2256 "chrec_a (X0) = chrec_b (Y0)". */
2257 HOST_WIDE_INT tau1 = MAX (CEIL (-i0, i1),
2258 CEIL (-j0, j1));
2259 HOST_WIDE_INT x0 = i1 * tau1 + i0;
2260 HOST_WIDE_INT y0 = j1 * tau1 + j0;
2262 /* (X1, Y1) is the smallest positive solution of the eq
2263 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2264 first conflict occurs. */
2265 HOST_WIDE_INT min_multiple = MIN (x0 / i1, y0 / j1);
2266 HOST_WIDE_INT x1 = x0 - i1 * min_multiple;
2267 HOST_WIDE_INT y1 = y0 - j1 * min_multiple;
2269 if (niter > 0)
2271 HOST_WIDE_INT tau2 = MIN (FLOOR_DIV (niter - i0, i1),
2272 FLOOR_DIV (niter - j0, j1));
2273 HOST_WIDE_INT last_conflict = tau2 - (x1 - i0)/i1;
2275 /* If the overlap occurs outside of the bounds of the
2276 loop, there is no dependence. */
2277 if (x1 > niter || y1 > niter)
2279 *overlaps_a = conflict_fn_no_dependence ();
2280 *overlaps_b = conflict_fn_no_dependence ();
2281 *last_conflicts = integer_zero_node;
2282 goto end_analyze_subs_aa;
2284 else
2285 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2287 else
2288 *last_conflicts = chrec_dont_know;
2290 *overlaps_a
2291 = conflict_fn (1,
2292 affine_fn_univar (build_int_cst (NULL_TREE, x1),
2294 build_int_cst (NULL_TREE, i1)));
2295 *overlaps_b
2296 = conflict_fn (1,
2297 affine_fn_univar (build_int_cst (NULL_TREE, y1),
2299 build_int_cst (NULL_TREE, j1)));
2301 else
2303 /* FIXME: For the moment, the upper bound of the
2304 iteration domain for i and j is not checked. */
2305 if (dump_file && (dump_flags & TDF_DETAILS))
2306 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2307 *overlaps_a = conflict_fn_not_known ();
2308 *overlaps_b = conflict_fn_not_known ();
2309 *last_conflicts = chrec_dont_know;
2312 else
2314 if (dump_file && (dump_flags & TDF_DETAILS))
2315 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2316 *overlaps_a = conflict_fn_not_known ();
2317 *overlaps_b = conflict_fn_not_known ();
2318 *last_conflicts = chrec_dont_know;
2321 else
2323 if (dump_file && (dump_flags & TDF_DETAILS))
2324 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2325 *overlaps_a = conflict_fn_not_known ();
2326 *overlaps_b = conflict_fn_not_known ();
2327 *last_conflicts = chrec_dont_know;
2330 end_analyze_subs_aa:
2331 if (dump_file && (dump_flags & TDF_DETAILS))
2333 fprintf (dump_file, " (overlaps_a = ");
2334 dump_conflict_function (dump_file, *overlaps_a);
2335 fprintf (dump_file, ")\n (overlaps_b = ");
2336 dump_conflict_function (dump_file, *overlaps_b);
2337 fprintf (dump_file, ")\n");
2338 fprintf (dump_file, ")\n");
2342 /* Returns true when analyze_subscript_affine_affine can be used for
2343 determining the dependence relation between chrec_a and chrec_b,
2344 that contain symbols. This function modifies chrec_a and chrec_b
2345 such that the analysis result is the same, and such that they don't
2346 contain symbols, and then can safely be passed to the analyzer.
2348 Example: The analysis of the following tuples of evolutions produce
2349 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2350 vs. {0, +, 1}_1
2352 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2353 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2356 static bool
2357 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
2359 tree diff, type, left_a, left_b, right_b;
2361 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
2362 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
2363 /* FIXME: For the moment not handled. Might be refined later. */
2364 return false;
2366 type = chrec_type (*chrec_a);
2367 left_a = CHREC_LEFT (*chrec_a);
2368 left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE);
2369 diff = chrec_fold_minus (type, left_a, left_b);
2371 if (!evolution_function_is_constant_p (diff))
2372 return false;
2374 if (dump_file && (dump_flags & TDF_DETAILS))
2375 fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
2377 *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
2378 diff, CHREC_RIGHT (*chrec_a));
2379 right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE);
2380 *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
2381 build_int_cst (type, 0),
2382 right_b);
2383 return true;
2386 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2387 *OVERLAPS_B are initialized to the functions that describe the
2388 relation between the elements accessed twice by CHREC_A and
2389 CHREC_B. For k >= 0, the following property is verified:
2391 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2393 static void
2394 analyze_siv_subscript (tree chrec_a,
2395 tree chrec_b,
2396 conflict_function **overlaps_a,
2397 conflict_function **overlaps_b,
2398 tree *last_conflicts,
2399 int loop_nest_num)
2401 dependence_stats.num_siv++;
2403 if (dump_file && (dump_flags & TDF_DETAILS))
2404 fprintf (dump_file, "(analyze_siv_subscript \n");
2406 if (evolution_function_is_constant_p (chrec_a)
2407 && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
2408 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
2409 overlaps_a, overlaps_b, last_conflicts);
2411 else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
2412 && evolution_function_is_constant_p (chrec_b))
2413 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2414 overlaps_b, overlaps_a, last_conflicts);
2416 else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
2417 && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
2419 if (!chrec_contains_symbols (chrec_a)
2420 && !chrec_contains_symbols (chrec_b))
2422 analyze_subscript_affine_affine (chrec_a, chrec_b,
2423 overlaps_a, overlaps_b,
2424 last_conflicts);
2426 if (CF_NOT_KNOWN_P (*overlaps_a)
2427 || CF_NOT_KNOWN_P (*overlaps_b))
2428 dependence_stats.num_siv_unimplemented++;
2429 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2430 || CF_NO_DEPENDENCE_P (*overlaps_b))
2431 dependence_stats.num_siv_independent++;
2432 else
2433 dependence_stats.num_siv_dependent++;
2435 else if (can_use_analyze_subscript_affine_affine (&chrec_a,
2436 &chrec_b))
2438 analyze_subscript_affine_affine (chrec_a, chrec_b,
2439 overlaps_a, overlaps_b,
2440 last_conflicts);
2442 if (CF_NOT_KNOWN_P (*overlaps_a)
2443 || CF_NOT_KNOWN_P (*overlaps_b))
2444 dependence_stats.num_siv_unimplemented++;
2445 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2446 || CF_NO_DEPENDENCE_P (*overlaps_b))
2447 dependence_stats.num_siv_independent++;
2448 else
2449 dependence_stats.num_siv_dependent++;
2451 else
2452 goto siv_subscript_dontknow;
2455 else
2457 siv_subscript_dontknow:;
2458 if (dump_file && (dump_flags & TDF_DETAILS))
2459 fprintf (dump_file, "siv test failed: unimplemented.\n");
2460 *overlaps_a = conflict_fn_not_known ();
2461 *overlaps_b = conflict_fn_not_known ();
2462 *last_conflicts = chrec_dont_know;
2463 dependence_stats.num_siv_unimplemented++;
2466 if (dump_file && (dump_flags & TDF_DETAILS))
2467 fprintf (dump_file, ")\n");
2470 /* Returns false if we can prove that the greatest common divisor of the steps
2471 of CHREC does not divide CST, false otherwise. */
2473 static bool
2474 gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst)
2476 HOST_WIDE_INT cd = 0, val;
2477 tree step;
2479 if (!host_integerp (cst, 0))
2480 return true;
2481 val = tree_low_cst (cst, 0);
2483 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
2485 step = CHREC_RIGHT (chrec);
2486 if (!host_integerp (step, 0))
2487 return true;
2488 cd = gcd (cd, tree_low_cst (step, 0));
2489 chrec = CHREC_LEFT (chrec);
2492 return val % cd == 0;
2495 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2496 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2497 functions that describe the relation between the elements accessed
2498 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2499 is verified:
2501 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2503 static void
2504 analyze_miv_subscript (tree chrec_a,
2505 tree chrec_b,
2506 conflict_function **overlaps_a,
2507 conflict_function **overlaps_b,
2508 tree *last_conflicts,
2509 struct loop *loop_nest)
2511 /* FIXME: This is a MIV subscript, not yet handled.
2512 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2513 (A[i] vs. A[j]).
2515 In the SIV test we had to solve a Diophantine equation with two
2516 variables. In the MIV case we have to solve a Diophantine
2517 equation with 2*n variables (if the subscript uses n IVs).
2519 tree type, difference;
2521 dependence_stats.num_miv++;
2522 if (dump_file && (dump_flags & TDF_DETAILS))
2523 fprintf (dump_file, "(analyze_miv_subscript \n");
2525 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
2526 chrec_a = chrec_convert (type, chrec_a, NULL_TREE);
2527 chrec_b = chrec_convert (type, chrec_b, NULL_TREE);
2528 difference = chrec_fold_minus (type, chrec_a, chrec_b);
2530 if (eq_evolutions_p (chrec_a, chrec_b))
2532 /* Access functions are the same: all the elements are accessed
2533 in the same order. */
2534 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2535 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2536 *last_conflicts = estimated_loop_iterations_tree
2537 (get_chrec_loop (chrec_a), true);
2538 dependence_stats.num_miv_dependent++;
2541 else if (evolution_function_is_constant_p (difference)
2542 /* For the moment, the following is verified:
2543 evolution_function_is_affine_multivariate_p (chrec_a,
2544 loop_nest->num) */
2545 && !gcd_of_steps_may_divide_p (chrec_a, difference))
2547 /* testsuite/.../ssa-chrec-33.c
2548 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2550 The difference is 1, and all the evolution steps are multiples
2551 of 2, consequently there are no overlapping elements. */
2552 *overlaps_a = conflict_fn_no_dependence ();
2553 *overlaps_b = conflict_fn_no_dependence ();
2554 *last_conflicts = integer_zero_node;
2555 dependence_stats.num_miv_independent++;
2558 else if (evolution_function_is_affine_multivariate_p (chrec_a, loop_nest->num)
2559 && !chrec_contains_symbols (chrec_a)
2560 && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num)
2561 && !chrec_contains_symbols (chrec_b))
2563 /* testsuite/.../ssa-chrec-35.c
2564 {0, +, 1}_2 vs. {0, +, 1}_3
2565 the overlapping elements are respectively located at iterations:
2566 {0, +, 1}_x and {0, +, 1}_x,
2567 in other words, we have the equality:
2568 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2570 Other examples:
2571 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2572 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2574 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2575 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2577 analyze_subscript_affine_affine (chrec_a, chrec_b,
2578 overlaps_a, overlaps_b, last_conflicts);
2580 if (CF_NOT_KNOWN_P (*overlaps_a)
2581 || CF_NOT_KNOWN_P (*overlaps_b))
2582 dependence_stats.num_miv_unimplemented++;
2583 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2584 || CF_NO_DEPENDENCE_P (*overlaps_b))
2585 dependence_stats.num_miv_independent++;
2586 else
2587 dependence_stats.num_miv_dependent++;
2590 else
2592 /* When the analysis is too difficult, answer "don't know". */
2593 if (dump_file && (dump_flags & TDF_DETAILS))
2594 fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
2596 *overlaps_a = conflict_fn_not_known ();
2597 *overlaps_b = conflict_fn_not_known ();
2598 *last_conflicts = chrec_dont_know;
2599 dependence_stats.num_miv_unimplemented++;
2602 if (dump_file && (dump_flags & TDF_DETAILS))
2603 fprintf (dump_file, ")\n");
2606 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2607 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
2608 OVERLAP_ITERATIONS_B are initialized with two functions that
2609 describe the iterations that contain conflicting elements.
2611 Remark: For an integer k >= 0, the following equality is true:
2613 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2616 static void
2617 analyze_overlapping_iterations (tree chrec_a,
2618 tree chrec_b,
2619 conflict_function **overlap_iterations_a,
2620 conflict_function **overlap_iterations_b,
2621 tree *last_conflicts, struct loop *loop_nest)
2623 unsigned int lnn = loop_nest->num;
2625 dependence_stats.num_subscript_tests++;
2627 if (dump_file && (dump_flags & TDF_DETAILS))
2629 fprintf (dump_file, "(analyze_overlapping_iterations \n");
2630 fprintf (dump_file, " (chrec_a = ");
2631 print_generic_expr (dump_file, chrec_a, 0);
2632 fprintf (dump_file, ")\n (chrec_b = ");
2633 print_generic_expr (dump_file, chrec_b, 0);
2634 fprintf (dump_file, ")\n");
2637 if (chrec_a == NULL_TREE
2638 || chrec_b == NULL_TREE
2639 || chrec_contains_undetermined (chrec_a)
2640 || chrec_contains_undetermined (chrec_b))
2642 dependence_stats.num_subscript_undetermined++;
2644 *overlap_iterations_a = conflict_fn_not_known ();
2645 *overlap_iterations_b = conflict_fn_not_known ();
2648 /* If they are the same chrec, and are affine, they overlap
2649 on every iteration. */
2650 else if (eq_evolutions_p (chrec_a, chrec_b)
2651 && evolution_function_is_affine_multivariate_p (chrec_a, lnn))
2653 dependence_stats.num_same_subscript_function++;
2654 *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2655 *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2656 *last_conflicts = chrec_dont_know;
2659 /* If they aren't the same, and aren't affine, we can't do anything
2660 yet. */
2661 else if ((chrec_contains_symbols (chrec_a)
2662 || chrec_contains_symbols (chrec_b))
2663 && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
2664 || !evolution_function_is_affine_multivariate_p (chrec_b, lnn)))
2666 dependence_stats.num_subscript_undetermined++;
2667 *overlap_iterations_a = conflict_fn_not_known ();
2668 *overlap_iterations_b = conflict_fn_not_known ();
2671 else if (ziv_subscript_p (chrec_a, chrec_b))
2672 analyze_ziv_subscript (chrec_a, chrec_b,
2673 overlap_iterations_a, overlap_iterations_b,
2674 last_conflicts);
2676 else if (siv_subscript_p (chrec_a, chrec_b))
2677 analyze_siv_subscript (chrec_a, chrec_b,
2678 overlap_iterations_a, overlap_iterations_b,
2679 last_conflicts, lnn);
2681 else
2682 analyze_miv_subscript (chrec_a, chrec_b,
2683 overlap_iterations_a, overlap_iterations_b,
2684 last_conflicts, loop_nest);
2686 if (dump_file && (dump_flags & TDF_DETAILS))
2688 fprintf (dump_file, " (overlap_iterations_a = ");
2689 dump_conflict_function (dump_file, *overlap_iterations_a);
2690 fprintf (dump_file, ")\n (overlap_iterations_b = ");
2691 dump_conflict_function (dump_file, *overlap_iterations_b);
2692 fprintf (dump_file, ")\n");
2693 fprintf (dump_file, ")\n");
2697 /* Helper function for uniquely inserting distance vectors. */
2699 static void
2700 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
2702 unsigned i;
2703 lambda_vector v;
2705 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
2706 if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
2707 return;
2709 VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
2712 /* Helper function for uniquely inserting direction vectors. */
2714 static void
2715 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
2717 unsigned i;
2718 lambda_vector v;
2720 for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
2721 if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
2722 return;
2724 VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
2727 /* Add a distance of 1 on all the loops outer than INDEX. If we
2728 haven't yet determined a distance for this outer loop, push a new
2729 distance vector composed of the previous distance, and a distance
2730 of 1 for this outer loop. Example:
2732 | loop_1
2733 | loop_2
2734 | A[10]
2735 | endloop_2
2736 | endloop_1
2738 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
2739 save (0, 1), then we have to save (1, 0). */
2741 static void
2742 add_outer_distances (struct data_dependence_relation *ddr,
2743 lambda_vector dist_v, int index)
2745 /* For each outer loop where init_v is not set, the accesses are
2746 in dependence of distance 1 in the loop. */
2747 while (--index >= 0)
2749 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2750 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
2751 save_v[index] = 1;
2752 save_dist_v (ddr, save_v);
2756 /* Return false when fail to represent the data dependence as a
2757 distance vector. INIT_B is set to true when a component has been
2758 added to the distance vector DIST_V. INDEX_CARRY is then set to
2759 the index in DIST_V that carries the dependence. */
2761 static bool
2762 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
2763 struct data_reference *ddr_a,
2764 struct data_reference *ddr_b,
2765 lambda_vector dist_v, bool *init_b,
2766 int *index_carry)
2768 unsigned i;
2769 lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2771 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2773 tree access_fn_a, access_fn_b;
2774 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
2776 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2778 non_affine_dependence_relation (ddr);
2779 return false;
2782 access_fn_a = DR_ACCESS_FN (ddr_a, i);
2783 access_fn_b = DR_ACCESS_FN (ddr_b, i);
2785 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
2786 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
2788 int dist, index;
2789 int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
2790 DDR_LOOP_NEST (ddr));
2791 int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
2792 DDR_LOOP_NEST (ddr));
2794 /* The dependence is carried by the outermost loop. Example:
2795 | loop_1
2796 | A[{4, +, 1}_1]
2797 | loop_2
2798 | A[{5, +, 1}_2]
2799 | endloop_2
2800 | endloop_1
2801 In this case, the dependence is carried by loop_1. */
2802 index = index_a < index_b ? index_a : index_b;
2803 *index_carry = MIN (index, *index_carry);
2805 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2807 non_affine_dependence_relation (ddr);
2808 return false;
2811 dist = int_cst_value (SUB_DISTANCE (subscript));
2813 /* This is the subscript coupling test. If we have already
2814 recorded a distance for this loop (a distance coming from
2815 another subscript), it should be the same. For example,
2816 in the following code, there is no dependence:
2818 | loop i = 0, N, 1
2819 | T[i+1][i] = ...
2820 | ... = T[i][i]
2821 | endloop
2823 if (init_v[index] != 0 && dist_v[index] != dist)
2825 finalize_ddr_dependent (ddr, chrec_known);
2826 return false;
2829 dist_v[index] = dist;
2830 init_v[index] = 1;
2831 *init_b = true;
2833 else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
2835 /* This can be for example an affine vs. constant dependence
2836 (T[i] vs. T[3]) that is not an affine dependence and is
2837 not representable as a distance vector. */
2838 non_affine_dependence_relation (ddr);
2839 return false;
2843 return true;
2846 /* Return true when the DDR contains only constant access functions. */
2848 static bool
2849 constant_access_functions (const struct data_dependence_relation *ddr)
2851 unsigned i;
2853 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2854 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
2855 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
2856 return false;
2858 return true;
2861 /* Helper function for the case where DDR_A and DDR_B are the same
2862 multivariate access function with a constant step. For an example
2863 see pr34635-1.c. */
2865 static void
2866 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
2868 int x_1, x_2;
2869 tree c_1 = CHREC_LEFT (c_2);
2870 tree c_0 = CHREC_LEFT (c_1);
2871 lambda_vector dist_v;
2872 int v1, v2, cd;
2874 /* Polynomials with more than 2 variables are not handled yet. When
2875 the evolution steps are parameters, it is not possible to
2876 represent the dependence using classical distance vectors. */
2877 if (TREE_CODE (c_0) != INTEGER_CST
2878 || TREE_CODE (CHREC_RIGHT (c_1)) != INTEGER_CST
2879 || TREE_CODE (CHREC_RIGHT (c_2)) != INTEGER_CST)
2881 DDR_AFFINE_P (ddr) = false;
2882 return;
2885 x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
2886 x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
2888 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
2889 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2890 v1 = int_cst_value (CHREC_RIGHT (c_1));
2891 v2 = int_cst_value (CHREC_RIGHT (c_2));
2892 cd = gcd (v1, v2);
2893 v1 /= cd;
2894 v2 /= cd;
2896 if (v2 < 0)
2898 v2 = -v2;
2899 v1 = -v1;
2902 dist_v[x_1] = v2;
2903 dist_v[x_2] = -v1;
2904 save_dist_v (ddr, dist_v);
2906 add_outer_distances (ddr, dist_v, x_1);
2909 /* Helper function for the case where DDR_A and DDR_B are the same
2910 access functions. */
2912 static void
2913 add_other_self_distances (struct data_dependence_relation *ddr)
2915 lambda_vector dist_v;
2916 unsigned i;
2917 int index_carry = DDR_NB_LOOPS (ddr);
2919 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2921 tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
2923 if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
2925 if (!evolution_function_is_univariate_p (access_fun))
2927 if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
2929 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
2930 return;
2933 access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);
2935 if (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC)
2936 add_multivariate_self_dist (ddr, access_fun);
2937 else
2938 /* The evolution step is not constant: it varies in
2939 the outer loop, so this cannot be represented by a
2940 distance vector. For example in pr34635.c the
2941 evolution is {0, +, {0, +, 4}_1}_2. */
2942 DDR_AFFINE_P (ddr) = false;
2944 return;
2947 index_carry = MIN (index_carry,
2948 index_in_loop_nest (CHREC_VARIABLE (access_fun),
2949 DDR_LOOP_NEST (ddr)));
2953 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2954 add_outer_distances (ddr, dist_v, index_carry);
2957 static void
2958 insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
2960 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2962 dist_v[DDR_INNER_LOOP (ddr)] = 1;
2963 save_dist_v (ddr, dist_v);
2966 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
2967 is the case for example when access functions are the same and
2968 equal to a constant, as in:
2970 | loop_1
2971 | A[3] = ...
2972 | ... = A[3]
2973 | endloop_1
2975 in which case the distance vectors are (0) and (1). */
2977 static void
2978 add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
2980 unsigned i, j;
2982 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2984 subscript_p sub = DDR_SUBSCRIPT (ddr, i);
2985 conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
2986 conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
2988 for (j = 0; j < ca->n; j++)
2989 if (affine_function_zero_p (ca->fns[j]))
2991 insert_innermost_unit_dist_vector (ddr);
2992 return;
2995 for (j = 0; j < cb->n; j++)
2996 if (affine_function_zero_p (cb->fns[j]))
2998 insert_innermost_unit_dist_vector (ddr);
2999 return;
3004 /* Compute the classic per loop distance vector. DDR is the data
3005 dependence relation to build a vector from. Return false when fail
3006 to represent the data dependence as a distance vector. */
3008 static bool
3009 build_classic_dist_vector (struct data_dependence_relation *ddr,
3010 struct loop *loop_nest)
3012 bool init_b = false;
3013 int index_carry = DDR_NB_LOOPS (ddr);
3014 lambda_vector dist_v;
3016 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3017 return false;
3019 if (same_access_functions (ddr))
3021 /* Save the 0 vector. */
3022 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3023 save_dist_v (ddr, dist_v);
3025 if (constant_access_functions (ddr))
3026 add_distance_for_zero_overlaps (ddr);
3028 if (DDR_NB_LOOPS (ddr) > 1)
3029 add_other_self_distances (ddr);
3031 return true;
3034 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3035 if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
3036 dist_v, &init_b, &index_carry))
3037 return false;
3039 /* Save the distance vector if we initialized one. */
3040 if (init_b)
3042 /* Verify a basic constraint: classic distance vectors should
3043 always be lexicographically positive.
3045 Data references are collected in the order of execution of
3046 the program, thus for the following loop
3048 | for (i = 1; i < 100; i++)
3049 | for (j = 1; j < 100; j++)
3051 | t = T[j+1][i-1]; // A
3052 | T[j][i] = t + 2; // B
3055 references are collected following the direction of the wind:
3056 A then B. The data dependence tests are performed also
3057 following this order, such that we're looking at the distance
3058 separating the elements accessed by A from the elements later
3059 accessed by B. But in this example, the distance returned by
3060 test_dep (A, B) is lexicographically negative (-1, 1), that
3061 means that the access A occurs later than B with respect to
3062 the outer loop, ie. we're actually looking upwind. In this
3063 case we solve test_dep (B, A) looking downwind to the
3064 lexicographically positive solution, that returns the
3065 distance vector (1, -1). */
3066 if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
3068 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3069 if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3070 loop_nest))
3071 return false;
3072 compute_subscript_distance (ddr);
3073 if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3074 save_v, &init_b, &index_carry))
3075 return false;
3076 save_dist_v (ddr, save_v);
3077 DDR_REVERSED_P (ddr) = true;
3079 /* In this case there is a dependence forward for all the
3080 outer loops:
3082 | for (k = 1; k < 100; k++)
3083 | for (i = 1; i < 100; i++)
3084 | for (j = 1; j < 100; j++)
3086 | t = T[j+1][i-1]; // A
3087 | T[j][i] = t + 2; // B
3090 the vectors are:
3091 (0, 1, -1)
3092 (1, 1, -1)
3093 (1, -1, 1)
3095 if (DDR_NB_LOOPS (ddr) > 1)
3097 add_outer_distances (ddr, save_v, index_carry);
3098 add_outer_distances (ddr, dist_v, index_carry);
3101 else
3103 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3104 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3106 if (DDR_NB_LOOPS (ddr) > 1)
3108 lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3110 if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr),
3111 DDR_A (ddr), loop_nest))
3112 return false;
3113 compute_subscript_distance (ddr);
3114 if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3115 opposite_v, &init_b,
3116 &index_carry))
3117 return false;
3119 save_dist_v (ddr, save_v);
3120 add_outer_distances (ddr, dist_v, index_carry);
3121 add_outer_distances (ddr, opposite_v, index_carry);
3123 else
3124 save_dist_v (ddr, save_v);
3127 else
3129 /* There is a distance of 1 on all the outer loops: Example:
3130 there is a dependence of distance 1 on loop_1 for the array A.
3132 | loop_1
3133 | A[5] = ...
3134 | endloop
3136 add_outer_distances (ddr, dist_v,
3137 lambda_vector_first_nz (dist_v,
3138 DDR_NB_LOOPS (ddr), 0));
3141 if (dump_file && (dump_flags & TDF_DETAILS))
3143 unsigned i;
3145 fprintf (dump_file, "(build_classic_dist_vector\n");
3146 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3148 fprintf (dump_file, " dist_vector = (");
3149 print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
3150 DDR_NB_LOOPS (ddr));
3151 fprintf (dump_file, " )\n");
3153 fprintf (dump_file, ")\n");
3156 return true;
3159 /* Return the direction for a given distance.
3160 FIXME: Computing dir this way is suboptimal, since dir can catch
3161 cases that dist is unable to represent. */
3163 static inline enum data_dependence_direction
3164 dir_from_dist (int dist)
3166 if (dist > 0)
3167 return dir_positive;
3168 else if (dist < 0)
3169 return dir_negative;
3170 else
3171 return dir_equal;
3174 /* Compute the classic per loop direction vector. DDR is the data
3175 dependence relation to build a vector from. */
3177 static void
3178 build_classic_dir_vector (struct data_dependence_relation *ddr)
3180 unsigned i, j;
3181 lambda_vector dist_v;
3183 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
3185 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3187 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3188 dir_v[j] = dir_from_dist (dist_v[j]);
3190 save_dir_v (ddr, dir_v);
3194 /* Helper function. Returns true when there is a dependence between
3195 data references DRA and DRB. */
3197 static bool
3198 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
3199 struct data_reference *dra,
3200 struct data_reference *drb,
3201 struct loop *loop_nest)
3203 unsigned int i;
3204 tree last_conflicts;
3205 struct subscript *subscript;
3207 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3208 i++)
3210 conflict_function *overlaps_a, *overlaps_b;
3212 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
3213 DR_ACCESS_FN (drb, i),
3214 &overlaps_a, &overlaps_b,
3215 &last_conflicts, loop_nest);
3217 if (CF_NOT_KNOWN_P (overlaps_a)
3218 || CF_NOT_KNOWN_P (overlaps_b))
3220 finalize_ddr_dependent (ddr, chrec_dont_know);
3221 dependence_stats.num_dependence_undetermined++;
3222 free_conflict_function (overlaps_a);
3223 free_conflict_function (overlaps_b);
3224 return false;
3227 else if (CF_NO_DEPENDENCE_P (overlaps_a)
3228 || CF_NO_DEPENDENCE_P (overlaps_b))
3230 finalize_ddr_dependent (ddr, chrec_known);
3231 dependence_stats.num_dependence_independent++;
3232 free_conflict_function (overlaps_a);
3233 free_conflict_function (overlaps_b);
3234 return false;
3237 else
3239 if (SUB_CONFLICTS_IN_A (subscript))
3240 free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
3241 if (SUB_CONFLICTS_IN_B (subscript))
3242 free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
3244 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3245 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3246 SUB_LAST_CONFLICT (subscript) = last_conflicts;
3250 return true;
3253 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3255 static void
3256 subscript_dependence_tester (struct data_dependence_relation *ddr,
3257 struct loop *loop_nest)
3260 if (dump_file && (dump_flags & TDF_DETAILS))
3261 fprintf (dump_file, "(subscript_dependence_tester \n");
3263 if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest))
3264 dependence_stats.num_dependence_dependent++;
3266 compute_subscript_distance (ddr);
3267 if (build_classic_dist_vector (ddr, loop_nest))
3268 build_classic_dir_vector (ddr);
3270 if (dump_file && (dump_flags & TDF_DETAILS))
3271 fprintf (dump_file, ")\n");
3274 /* Returns true when all the access functions of A are affine or
3275 constant with respect to LOOP_NEST. */
3277 static bool
3278 access_functions_are_affine_or_constant_p (const struct data_reference *a,
3279 const struct loop *loop_nest)
3281 unsigned int i;
3282 VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
3283 tree t;
3285 for (i = 0; VEC_iterate (tree, fns, i, t); i++)
3286 if (!evolution_function_is_invariant_p (t, loop_nest->num)
3287 && !evolution_function_is_affine_multivariate_p (t, loop_nest->num))
3288 return false;
3290 return true;
3293 /* Initializes an equation for an OMEGA problem using the information
3294 contained in the ACCESS_FUN. Returns true when the operation
3295 succeeded.
3297 PB is the omega constraint system.
3298 EQ is the number of the equation to be initialized.
3299 OFFSET is used for shifting the variables names in the constraints:
3300 a constrain is composed of 2 * the number of variables surrounding
3301 dependence accesses. OFFSET is set either to 0 for the first n variables,
3302 then it is set to n.
3303 ACCESS_FUN is expected to be an affine chrec. */
3305 static bool
3306 init_omega_eq_with_af (omega_pb pb, unsigned eq,
3307 unsigned int offset, tree access_fun,
3308 struct data_dependence_relation *ddr)
3310 switch (TREE_CODE (access_fun))
3312 case POLYNOMIAL_CHREC:
3314 tree left = CHREC_LEFT (access_fun);
3315 tree right = CHREC_RIGHT (access_fun);
3316 int var = CHREC_VARIABLE (access_fun);
3317 unsigned var_idx;
3319 if (TREE_CODE (right) != INTEGER_CST)
3320 return false;
3322 var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
3323 pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
3325 /* Compute the innermost loop index. */
3326 DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
3328 if (offset == 0)
3329 pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
3330 += int_cst_value (right);
3332 switch (TREE_CODE (left))
3334 case POLYNOMIAL_CHREC:
3335 return init_omega_eq_with_af (pb, eq, offset, left, ddr);
3337 case INTEGER_CST:
3338 pb->eqs[eq].coef[0] += int_cst_value (left);
3339 return true;
3341 default:
3342 return false;
3346 case INTEGER_CST:
3347 pb->eqs[eq].coef[0] += int_cst_value (access_fun);
3348 return true;
3350 default:
3351 return false;
3355 /* As explained in the comments preceding init_omega_for_ddr, we have
3356 to set up a system for each loop level, setting outer loops
3357 variation to zero, and current loop variation to positive or zero.
3358 Save each lexico positive distance vector. */
3360 static void
3361 omega_extract_distance_vectors (omega_pb pb,
3362 struct data_dependence_relation *ddr)
3364 int eq, geq;
3365 unsigned i, j;
3366 struct loop *loopi, *loopj;
3367 enum omega_result res;
3369 /* Set a new problem for each loop in the nest. The basis is the
3370 problem that we have initialized until now. On top of this we
3371 add new constraints. */
3372 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3373 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3375 int dist = 0;
3376 omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
3377 DDR_NB_LOOPS (ddr));
3379 omega_copy_problem (copy, pb);
3381 /* For all the outer loops "loop_j", add "dj = 0". */
3382 for (j = 0;
3383 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3385 eq = omega_add_zero_eq (copy, omega_black);
3386 copy->eqs[eq].coef[j + 1] = 1;
3389 /* For "loop_i", add "0 <= di". */
3390 geq = omega_add_zero_geq (copy, omega_black);
3391 copy->geqs[geq].coef[i + 1] = 1;
3393 /* Reduce the constraint system, and test that the current
3394 problem is feasible. */
3395 res = omega_simplify_problem (copy);
3396 if (res == omega_false
3397 || res == omega_unknown
3398 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3399 goto next_problem;
3401 for (eq = 0; eq < copy->num_subs; eq++)
3402 if (copy->subs[eq].key == (int) i + 1)
3404 dist = copy->subs[eq].coef[0];
3405 goto found_dist;
3408 if (dist == 0)
3410 /* Reinitialize problem... */
3411 omega_copy_problem (copy, pb);
3412 for (j = 0;
3413 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3415 eq = omega_add_zero_eq (copy, omega_black);
3416 copy->eqs[eq].coef[j + 1] = 1;
3419 /* ..., but this time "di = 1". */
3420 eq = omega_add_zero_eq (copy, omega_black);
3421 copy->eqs[eq].coef[i + 1] = 1;
3422 copy->eqs[eq].coef[0] = -1;
3424 res = omega_simplify_problem (copy);
3425 if (res == omega_false
3426 || res == omega_unknown
3427 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3428 goto next_problem;
3430 for (eq = 0; eq < copy->num_subs; eq++)
3431 if (copy->subs[eq].key == (int) i + 1)
3433 dist = copy->subs[eq].coef[0];
3434 goto found_dist;
3438 found_dist:;
3439 /* Save the lexicographically positive distance vector. */
3440 if (dist >= 0)
3442 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3443 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3445 dist_v[i] = dist;
3447 for (eq = 0; eq < copy->num_subs; eq++)
3448 if (copy->subs[eq].key > 0)
3450 dist = copy->subs[eq].coef[0];
3451 dist_v[copy->subs[eq].key - 1] = dist;
3454 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3455 dir_v[j] = dir_from_dist (dist_v[j]);
3457 save_dist_v (ddr, dist_v);
3458 save_dir_v (ddr, dir_v);
3461 next_problem:;
3462 omega_free_problem (copy);
3466 /* This is called for each subscript of a tuple of data references:
3467 insert an equality for representing the conflicts. */
3469 static bool
3470 omega_setup_subscript (tree access_fun_a, tree access_fun_b,
3471 struct data_dependence_relation *ddr,
3472 omega_pb pb, bool *maybe_dependent)
3474 int eq;
3475 tree type = signed_type_for_types (TREE_TYPE (access_fun_a),
3476 TREE_TYPE (access_fun_b));
3477 tree fun_a = chrec_convert (type, access_fun_a, NULL_TREE);
3478 tree fun_b = chrec_convert (type, access_fun_b, NULL_TREE);
3479 tree difference = chrec_fold_minus (type, fun_a, fun_b);
3481 /* When the fun_a - fun_b is not constant, the dependence is not
3482 captured by the classic distance vector representation. */
3483 if (TREE_CODE (difference) != INTEGER_CST)
3484 return false;
3486 /* ZIV test. */
3487 if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
3489 /* There is no dependence. */
3490 *maybe_dependent = false;
3491 return true;
3494 fun_b = chrec_fold_multiply (type, fun_b, integer_minus_one_node);
3496 eq = omega_add_zero_eq (pb, omega_black);
3497 if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
3498 || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
3499 /* There is probably a dependence, but the system of
3500 constraints cannot be built: answer "don't know". */
3501 return false;
3503 /* GCD test. */
3504 if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
3505 && !int_divides_p (lambda_vector_gcd
3506 ((lambda_vector) &(pb->eqs[eq].coef[1]),
3507 2 * DDR_NB_LOOPS (ddr)),
3508 pb->eqs[eq].coef[0]))
3510 /* There is no dependence. */
3511 *maybe_dependent = false;
3512 return true;
3515 return true;
3518 /* Helper function, same as init_omega_for_ddr but specialized for
3519 data references A and B. */
3521 static bool
3522 init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
3523 struct data_dependence_relation *ddr,
3524 omega_pb pb, bool *maybe_dependent)
3526 unsigned i;
3527 int ineq;
3528 struct loop *loopi;
3529 unsigned nb_loops = DDR_NB_LOOPS (ddr);
3531 /* Insert an equality per subscript. */
3532 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3534 if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
3535 ddr, pb, maybe_dependent))
3536 return false;
3537 else if (*maybe_dependent == false)
3539 /* There is no dependence. */
3540 DDR_ARE_DEPENDENT (ddr) = chrec_known;
3541 return true;
3545 /* Insert inequalities: constraints corresponding to the iteration
3546 domain, i.e. the loops surrounding the references "loop_x" and
3547 the distance variables "dx". The layout of the OMEGA
3548 representation is as follows:
3549 - coef[0] is the constant
3550 - coef[1..nb_loops] are the protected variables that will not be
3551 removed by the solver: the "dx"
3552 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3554 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3555 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3557 HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, false);
3559 /* 0 <= loop_x */
3560 ineq = omega_add_zero_geq (pb, omega_black);
3561 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3563 /* 0 <= loop_x + dx */
3564 ineq = omega_add_zero_geq (pb, omega_black);
3565 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3566 pb->geqs[ineq].coef[i + 1] = 1;
3568 if (nbi != -1)
3570 /* loop_x <= nb_iters */
3571 ineq = omega_add_zero_geq (pb, omega_black);
3572 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3573 pb->geqs[ineq].coef[0] = nbi;
3575 /* loop_x + dx <= nb_iters */
3576 ineq = omega_add_zero_geq (pb, omega_black);
3577 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3578 pb->geqs[ineq].coef[i + 1] = -1;
3579 pb->geqs[ineq].coef[0] = nbi;
3581 /* A step "dx" bigger than nb_iters is not feasible, so
3582 add "0 <= nb_iters + dx", */
3583 ineq = omega_add_zero_geq (pb, omega_black);
3584 pb->geqs[ineq].coef[i + 1] = 1;
3585 pb->geqs[ineq].coef[0] = nbi;
3586 /* and "dx <= nb_iters". */
3587 ineq = omega_add_zero_geq (pb, omega_black);
3588 pb->geqs[ineq].coef[i + 1] = -1;
3589 pb->geqs[ineq].coef[0] = nbi;
3593 omega_extract_distance_vectors (pb, ddr);
3595 return true;
3598 /* Sets up the Omega dependence problem for the data dependence
3599 relation DDR. Returns false when the constraint system cannot be
3600 built, ie. when the test answers "don't know". Returns true
3601 otherwise, and when independence has been proved (using one of the
3602 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3603 set MAYBE_DEPENDENT to true.
3605 Example: for setting up the dependence system corresponding to the
3606 conflicting accesses
3608 | loop_i
3609 | loop_j
3610 | A[i, i+1] = ...
3611 | ... A[2*j, 2*(i + j)]
3612 | endloop_j
3613 | endloop_i
3615 the following constraints come from the iteration domain:
3617 0 <= i <= Ni
3618 0 <= i + di <= Ni
3619 0 <= j <= Nj
3620 0 <= j + dj <= Nj
3622 where di, dj are the distance variables. The constraints
3623 representing the conflicting elements are:
3625 i = 2 * (j + dj)
3626 i + 1 = 2 * (i + di + j + dj)
3628 For asking that the resulting distance vector (di, dj) be
3629 lexicographically positive, we insert the constraint "di >= 0". If
3630 "di = 0" in the solution, we fix that component to zero, and we
3631 look at the inner loops: we set a new problem where all the outer
3632 loop distances are zero, and fix this inner component to be
3633 positive. When one of the components is positive, we save that
3634 distance, and set a new problem where the distance on this loop is
3635 zero, searching for other distances in the inner loops. Here is
3636 the classic example that illustrates that we have to set for each
3637 inner loop a new problem:
3639 | loop_1
3640 | loop_2
3641 | A[10]
3642 | endloop_2
3643 | endloop_1
3645 we have to save two distances (1, 0) and (0, 1).
3647 Given two array references, refA and refB, we have to set the
3648 dependence problem twice, refA vs. refB and refB vs. refA, and we
3649 cannot do a single test, as refB might occur before refA in the
3650 inner loops, and the contrary when considering outer loops: ex.
3652 | loop_0
3653 | loop_1
3654 | loop_2
3655 | T[{1,+,1}_2][{1,+,1}_1] // refA
3656 | T[{2,+,1}_2][{0,+,1}_1] // refB
3657 | endloop_2
3658 | endloop_1
3659 | endloop_0
3661 refB touches the elements in T before refA, and thus for the same
3662 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3663 but for successive loop_0 iterations, we have (1, -1, 1)
3665 The Omega solver expects the distance variables ("di" in the
3666 previous example) to come first in the constraint system (as
3667 variables to be protected, or "safe" variables), the constraint
3668 system is built using the following layout:
3670 "cst | distance vars | index vars".
3673 static bool
3674 init_omega_for_ddr (struct data_dependence_relation *ddr,
3675 bool *maybe_dependent)
3677 omega_pb pb;
3678 bool res = false;
3680 *maybe_dependent = true;
3682 if (same_access_functions (ddr))
3684 unsigned j;
3685 lambda_vector dir_v;
3687 /* Save the 0 vector. */
3688 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3689 dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3690 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3691 dir_v[j] = dir_equal;
3692 save_dir_v (ddr, dir_v);
3694 /* Save the dependences carried by outer loops. */
3695 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3696 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3697 maybe_dependent);
3698 omega_free_problem (pb);
3699 return res;
3702 /* Omega expects the protected variables (those that have to be kept
3703 after elimination) to appear first in the constraint system.
3704 These variables are the distance variables. In the following
3705 initialization we declare NB_LOOPS safe variables, and the total
3706 number of variables for the constraint system is 2*NB_LOOPS. */
3707 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3708 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3709 maybe_dependent);
3710 omega_free_problem (pb);
3712 /* Stop computation if not decidable, or no dependence. */
3713 if (res == false || *maybe_dependent == false)
3714 return res;
3716 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3717 res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
3718 maybe_dependent);
3719 omega_free_problem (pb);
3721 return res;
3724 /* Return true when DDR contains the same information as that stored
3725 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3727 static bool
3728 ddr_consistent_p (FILE *file,
3729 struct data_dependence_relation *ddr,
3730 VEC (lambda_vector, heap) *dist_vects,
3731 VEC (lambda_vector, heap) *dir_vects)
3733 unsigned int i, j;
3735 /* If dump_file is set, output there. */
3736 if (dump_file && (dump_flags & TDF_DETAILS))
3737 file = dump_file;
3739 if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
3741 lambda_vector b_dist_v;
3742 fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3743 VEC_length (lambda_vector, dist_vects),
3744 DDR_NUM_DIST_VECTS (ddr));
3746 fprintf (file, "Banerjee dist vectors:\n");
3747 for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++)
3748 print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
3750 fprintf (file, "Omega dist vectors:\n");
3751 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3752 print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
3754 fprintf (file, "data dependence relation:\n");
3755 dump_data_dependence_relation (file, ddr);
3757 fprintf (file, ")\n");
3758 return false;
3761 if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
3763 fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3764 VEC_length (lambda_vector, dir_vects),
3765 DDR_NUM_DIR_VECTS (ddr));
3766 return false;
3769 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3771 lambda_vector a_dist_v;
3772 lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
3774 /* Distance vectors are not ordered in the same way in the DDR
3775 and in the DIST_VECTS: search for a matching vector. */
3776 for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, a_dist_v); j++)
3777 if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
3778 break;
3780 if (j == VEC_length (lambda_vector, dist_vects))
3782 fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
3783 print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
3784 fprintf (file, "not found in Omega dist vectors:\n");
3785 print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
3786 fprintf (file, "data dependence relation:\n");
3787 dump_data_dependence_relation (file, ddr);
3788 fprintf (file, ")\n");
3792 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
3794 lambda_vector a_dir_v;
3795 lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
3797 /* Direction vectors are not ordered in the same way in the DDR
3798 and in the DIR_VECTS: search for a matching vector. */
3799 for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, a_dir_v); j++)
3800 if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
3801 break;
3803 if (j == VEC_length (lambda_vector, dist_vects))
3805 fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
3806 print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
3807 fprintf (file, "not found in Omega dir vectors:\n");
3808 print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
3809 fprintf (file, "data dependence relation:\n");
3810 dump_data_dependence_relation (file, ddr);
3811 fprintf (file, ")\n");
3815 return true;
3818 /* This computes the affine dependence relation between A and B with
3819 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
3820 independence between two accesses, while CHREC_DONT_KNOW is used
3821 for representing the unknown relation.
3823 Note that it is possible to stop the computation of the dependence
3824 relation the first time we detect a CHREC_KNOWN element for a given
3825 subscript. */
3827 static void
3828 compute_affine_dependence (struct data_dependence_relation *ddr,
3829 struct loop *loop_nest)
3831 struct data_reference *dra = DDR_A (ddr);
3832 struct data_reference *drb = DDR_B (ddr);
3834 if (dump_file && (dump_flags & TDF_DETAILS))
3836 fprintf (dump_file, "(compute_affine_dependence\n");
3837 fprintf (dump_file, " (stmt_a = \n");
3838 print_generic_expr (dump_file, DR_STMT (dra), 0);
3839 fprintf (dump_file, ")\n (stmt_b = \n");
3840 print_generic_expr (dump_file, DR_STMT (drb), 0);
3841 fprintf (dump_file, ")\n");
3844 /* Analyze only when the dependence relation is not yet known. */
3845 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
3846 && !DDR_SELF_REFERENCE (ddr))
3848 dependence_stats.num_dependence_tests++;
3850 if (access_functions_are_affine_or_constant_p (dra, loop_nest)
3851 && access_functions_are_affine_or_constant_p (drb, loop_nest))
3853 if (flag_check_data_deps)
3855 /* Compute the dependences using the first algorithm. */
3856 subscript_dependence_tester (ddr, loop_nest);
3858 if (dump_file && (dump_flags & TDF_DETAILS))
3860 fprintf (dump_file, "\n\nBanerjee Analyzer\n");
3861 dump_data_dependence_relation (dump_file, ddr);
3864 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3866 bool maybe_dependent;
3867 VEC (lambda_vector, heap) *dir_vects, *dist_vects;
3869 /* Save the result of the first DD analyzer. */
3870 dist_vects = DDR_DIST_VECTS (ddr);
3871 dir_vects = DDR_DIR_VECTS (ddr);
3873 /* Reset the information. */
3874 DDR_DIST_VECTS (ddr) = NULL;
3875 DDR_DIR_VECTS (ddr) = NULL;
3877 /* Compute the same information using Omega. */
3878 if (!init_omega_for_ddr (ddr, &maybe_dependent))
3879 goto csys_dont_know;
3881 if (dump_file && (dump_flags & TDF_DETAILS))
3883 fprintf (dump_file, "Omega Analyzer\n");
3884 dump_data_dependence_relation (dump_file, ddr);
3887 /* Check that we get the same information. */
3888 if (maybe_dependent)
3889 gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
3890 dir_vects));
3893 else
3894 subscript_dependence_tester (ddr, loop_nest);
3897 /* As a last case, if the dependence cannot be determined, or if
3898 the dependence is considered too difficult to determine, answer
3899 "don't know". */
3900 else
3902 csys_dont_know:;
3903 dependence_stats.num_dependence_undetermined++;
3905 if (dump_file && (dump_flags & TDF_DETAILS))
3907 fprintf (dump_file, "Data ref a:\n");
3908 dump_data_reference (dump_file, dra);
3909 fprintf (dump_file, "Data ref b:\n");
3910 dump_data_reference (dump_file, drb);
3911 fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
3913 finalize_ddr_dependent (ddr, chrec_dont_know);
3917 if (dump_file && (dump_flags & TDF_DETAILS))
3918 fprintf (dump_file, ")\n");
3921 /* This computes the dependence relation for the same data
3922 reference into DDR. */
3924 static void
3925 compute_self_dependence (struct data_dependence_relation *ddr)
3927 unsigned int i;
3928 struct subscript *subscript;
3930 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3931 return;
3933 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3934 i++)
3936 if (SUB_CONFLICTS_IN_A (subscript))
3937 free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
3938 if (SUB_CONFLICTS_IN_B (subscript))
3939 free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
3941 /* The accessed index overlaps for each iteration. */
3942 SUB_CONFLICTS_IN_A (subscript)
3943 = conflict_fn (1, affine_fn_cst (integer_zero_node));
3944 SUB_CONFLICTS_IN_B (subscript)
3945 = conflict_fn (1, affine_fn_cst (integer_zero_node));
3946 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3949 /* The distance vector is the zero vector. */
3950 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3951 save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3954 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3955 the data references in DATAREFS, in the LOOP_NEST. When
3956 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3957 relations. */
3959 void
3960 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
3961 VEC (ddr_p, heap) **dependence_relations,
3962 VEC (loop_p, heap) *loop_nest,
3963 bool compute_self_and_rr)
3965 struct data_dependence_relation *ddr;
3966 struct data_reference *a, *b;
3967 unsigned int i, j;
3969 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
3970 for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
3971 if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
3973 ddr = initialize_data_dependence_relation (a, b, loop_nest);
3974 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3975 compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
3978 if (compute_self_and_rr)
3979 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
3981 ddr = initialize_data_dependence_relation (a, a, loop_nest);
3982 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3983 compute_self_dependence (ddr);
3987 /* Stores the locations of memory references in STMT to REFERENCES. Returns
3988 true if STMT clobbers memory, false otherwise. */
3990 bool
3991 get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references)
3993 bool clobbers_memory = false;
3994 data_ref_loc *ref;
3995 tree *op0, *op1, call;
3997 *references = NULL;
3999 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4000 Calls have side-effects, except those to const or pure
4001 functions. */
4002 call = get_call_expr_in (stmt);
4003 if ((call
4004 && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE)))
4005 || (TREE_CODE (stmt) == ASM_EXPR
4006 && ASM_VOLATILE_P (stmt)))
4007 clobbers_memory = true;
4009 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
4010 return clobbers_memory;
4012 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
4014 tree base;
4015 op0 = &GIMPLE_STMT_OPERAND (stmt, 0);
4016 op1 = &GIMPLE_STMT_OPERAND (stmt, 1);
4018 if (DECL_P (*op1)
4019 || (REFERENCE_CLASS_P (*op1)
4020 && (base = get_base_address (*op1))
4021 && TREE_CODE (base) != SSA_NAME))
4023 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4024 ref->pos = op1;
4025 ref->is_read = true;
4028 if (DECL_P (*op0)
4029 || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
4031 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4032 ref->pos = op0;
4033 ref->is_read = false;
4037 if (call)
4039 unsigned i, n = call_expr_nargs (call);
4041 for (i = 0; i < n; i++)
4043 op0 = &CALL_EXPR_ARG (call, i);
4045 if (DECL_P (*op0)
4046 || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
4048 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4049 ref->pos = op0;
4050 ref->is_read = true;
4055 return clobbers_memory;
4058 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4059 reference, returns false, otherwise returns true. NEST is the outermost
4060 loop of the loop nest in that the references should be analyzed. */
4062 static bool
4063 find_data_references_in_stmt (struct loop *nest, tree stmt,
4064 VEC (data_reference_p, heap) **datarefs)
4066 unsigned i;
4067 VEC (data_ref_loc, heap) *references;
4068 data_ref_loc *ref;
4069 bool ret = true;
4070 data_reference_p dr;
4072 if (get_references_in_stmt (stmt, &references))
4074 VEC_free (data_ref_loc, heap, references);
4075 return false;
4078 for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
4080 dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
4081 gcc_assert (dr != NULL);
4083 /* FIXME -- data dependence analysis does not work correctly for objects with
4084 invariant addresses. Let us fail here until the problem is fixed. */
4085 if (dr_address_invariant_p (dr))
4087 free_data_ref (dr);
4088 if (dump_file && (dump_flags & TDF_DETAILS))
4089 fprintf (dump_file, "\tFAILED as dr address is invariant\n");
4090 ret = false;
4091 break;
4094 VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4096 VEC_free (data_ref_loc, heap, references);
4097 return ret;
4100 /* Search the data references in LOOP, and record the information into
4101 DATAREFS. Returns chrec_dont_know when failing to analyze a
4102 difficult case, returns NULL_TREE otherwise.
4104 TODO: This function should be made smarter so that it can handle address
4105 arithmetic as if they were array accesses, etc. */
4107 static tree
4108 find_data_references_in_loop (struct loop *loop,
4109 VEC (data_reference_p, heap) **datarefs)
4111 basic_block bb, *bbs;
4112 unsigned int i;
4113 block_stmt_iterator bsi;
4115 bbs = get_loop_body_in_dom_order (loop);
4117 for (i = 0; i < loop->num_nodes; i++)
4119 bb = bbs[i];
4121 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4123 tree stmt = bsi_stmt (bsi);
4125 if (!find_data_references_in_stmt (loop, stmt, datarefs))
4127 struct data_reference *res;
4128 res = XCNEW (struct data_reference);
4129 VEC_safe_push (data_reference_p, heap, *datarefs, res);
4131 free (bbs);
4132 return chrec_dont_know;
4136 free (bbs);
4138 return NULL_TREE;
4141 /* Recursive helper function. */
4143 static bool
4144 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4146 /* Inner loops of the nest should not contain siblings. Example:
4147 when there are two consecutive loops,
4149 | loop_0
4150 | loop_1
4151 | A[{0, +, 1}_1]
4152 | endloop_1
4153 | loop_2
4154 | A[{0, +, 1}_2]
4155 | endloop_2
4156 | endloop_0
4158 the dependence relation cannot be captured by the distance
4159 abstraction. */
4160 if (loop->next)
4161 return false;
4163 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4164 if (loop->inner)
4165 return find_loop_nest_1 (loop->inner, loop_nest);
4166 return true;
4169 /* Return false when the LOOP is not well nested. Otherwise return
4170 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4171 contain the loops from the outermost to the innermost, as they will
4172 appear in the classic distance vector. */
4174 bool
4175 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4177 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4178 if (loop->inner)
4179 return find_loop_nest_1 (loop->inner, loop_nest);
4180 return true;
4183 /* Returns true when the data dependences have been computed, false otherwise.
4184 Given a loop nest LOOP, the following vectors are returned:
4185 DATAREFS is initialized to all the array elements contained in this loop,
4186 DEPENDENCE_RELATIONS contains the relations between the data references.
4187 Compute read-read and self relations if
4188 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4190 bool
4191 compute_data_dependences_for_loop (struct loop *loop,
4192 bool compute_self_and_read_read_dependences,
4193 VEC (data_reference_p, heap) **datarefs,
4194 VEC (ddr_p, heap) **dependence_relations)
4196 bool res = true;
4197 VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
4199 memset (&dependence_stats, 0, sizeof (dependence_stats));
4201 /* If the loop nest is not well formed, or one of the data references
4202 is not computable, give up without spending time to compute other
4203 dependences. */
4204 if (!loop
4205 || !find_loop_nest (loop, &vloops)
4206 || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
4208 struct data_dependence_relation *ddr;
4210 /* Insert a single relation into dependence_relations:
4211 chrec_dont_know. */
4212 ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
4213 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4214 res = false;
4216 else
4217 compute_all_dependences (*datarefs, dependence_relations, vloops,
4218 compute_self_and_read_read_dependences);
4220 if (dump_file && (dump_flags & TDF_STATS))
4222 fprintf (dump_file, "Dependence tester statistics:\n");
4224 fprintf (dump_file, "Number of dependence tests: %d\n",
4225 dependence_stats.num_dependence_tests);
4226 fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4227 dependence_stats.num_dependence_dependent);
4228 fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4229 dependence_stats.num_dependence_independent);
4230 fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4231 dependence_stats.num_dependence_undetermined);
4233 fprintf (dump_file, "Number of subscript tests: %d\n",
4234 dependence_stats.num_subscript_tests);
4235 fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4236 dependence_stats.num_subscript_undetermined);
4237 fprintf (dump_file, "Number of same subscript function: %d\n",
4238 dependence_stats.num_same_subscript_function);
4240 fprintf (dump_file, "Number of ziv tests: %d\n",
4241 dependence_stats.num_ziv);
4242 fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4243 dependence_stats.num_ziv_dependent);
4244 fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4245 dependence_stats.num_ziv_independent);
4246 fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4247 dependence_stats.num_ziv_unimplemented);
4249 fprintf (dump_file, "Number of siv tests: %d\n",
4250 dependence_stats.num_siv);
4251 fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4252 dependence_stats.num_siv_dependent);
4253 fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4254 dependence_stats.num_siv_independent);
4255 fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4256 dependence_stats.num_siv_unimplemented);
4258 fprintf (dump_file, "Number of miv tests: %d\n",
4259 dependence_stats.num_miv);
4260 fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4261 dependence_stats.num_miv_dependent);
4262 fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4263 dependence_stats.num_miv_independent);
4264 fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4265 dependence_stats.num_miv_unimplemented);
4268 return res;
4271 /* Entry point (for testing only). Analyze all the data references
4272 and the dependence relations in LOOP.
4274 The data references are computed first.
4276 A relation on these nodes is represented by a complete graph. Some
4277 of the relations could be of no interest, thus the relations can be
4278 computed on demand.
4280 In the following function we compute all the relations. This is
4281 just a first implementation that is here for:
4282 - for showing how to ask for the dependence relations,
4283 - for the debugging the whole dependence graph,
4284 - for the dejagnu testcases and maintenance.
4286 It is possible to ask only for a part of the graph, avoiding to
4287 compute the whole dependence graph. The computed dependences are
4288 stored in a knowledge base (KB) such that later queries don't
4289 recompute the same information. The implementation of this KB is
4290 transparent to the optimizer, and thus the KB can be changed with a
4291 more efficient implementation, or the KB could be disabled. */
4292 static void
4293 analyze_all_data_dependences (struct loop *loop)
4295 unsigned int i;
4296 int nb_data_refs = 10;
4297 VEC (data_reference_p, heap) *datarefs =
4298 VEC_alloc (data_reference_p, heap, nb_data_refs);
4299 VEC (ddr_p, heap) *dependence_relations =
4300 VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
4302 /* Compute DDs on the whole function. */
4303 compute_data_dependences_for_loop (loop, false, &datarefs,
4304 &dependence_relations);
4306 if (dump_file)
4308 dump_data_dependence_relations (dump_file, dependence_relations);
4309 fprintf (dump_file, "\n\n");
4311 if (dump_flags & TDF_DETAILS)
4312 dump_dist_dir_vectors (dump_file, dependence_relations);
4314 if (dump_flags & TDF_STATS)
4316 unsigned nb_top_relations = 0;
4317 unsigned nb_bot_relations = 0;
4318 unsigned nb_basename_differ = 0;
4319 unsigned nb_chrec_relations = 0;
4320 struct data_dependence_relation *ddr;
4322 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4324 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4325 nb_top_relations++;
4327 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4329 struct data_reference *a = DDR_A (ddr);
4330 struct data_reference *b = DDR_B (ddr);
4332 if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
4333 nb_basename_differ++;
4334 else
4335 nb_bot_relations++;
4338 else
4339 nb_chrec_relations++;
4342 gather_stats_on_scev_database ();
4346 free_dependence_relations (dependence_relations);
4347 free_data_refs (datarefs);
4350 /* Computes all the data dependences and check that the results of
4351 several analyzers are the same. */
4353 void
4354 tree_check_data_deps (void)
4356 loop_iterator li;
4357 struct loop *loop_nest;
4359 FOR_EACH_LOOP (li, loop_nest, 0)
4360 analyze_all_data_dependences (loop_nest);
4363 /* Free the memory used by a data dependence relation DDR. */
4365 void
4366 free_dependence_relation (struct data_dependence_relation *ddr)
4368 if (ddr == NULL)
4369 return;
4371 if (DDR_SUBSCRIPTS (ddr))
4372 free_subscripts (DDR_SUBSCRIPTS (ddr));
4373 if (DDR_DIST_VECTS (ddr))
4374 VEC_free (lambda_vector, heap, DDR_DIST_VECTS (ddr));
4375 if (DDR_DIR_VECTS (ddr))
4376 VEC_free (lambda_vector, heap, DDR_DIR_VECTS (ddr));
4378 free (ddr);
4381 /* Free the memory used by the data dependence relations from
4382 DEPENDENCE_RELATIONS. */
4384 void
4385 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
4387 unsigned int i;
4388 struct data_dependence_relation *ddr;
4389 VEC (loop_p, heap) *loop_nest = NULL;
4391 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4393 if (ddr == NULL)
4394 continue;
4395 if (loop_nest == NULL)
4396 loop_nest = DDR_LOOP_NEST (ddr);
4397 else
4398 gcc_assert (DDR_LOOP_NEST (ddr) == NULL
4399 || DDR_LOOP_NEST (ddr) == loop_nest);
4400 free_dependence_relation (ddr);
4403 if (loop_nest)
4404 VEC_free (loop_p, heap, loop_nest);
4405 VEC_free (ddr_p, heap, dependence_relations);
4408 /* Free the memory used by the data references from DATAREFS. */
4410 void
4411 free_data_refs (VEC (data_reference_p, heap) *datarefs)
4413 unsigned int i;
4414 struct data_reference *dr;
4416 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
4417 free_data_ref (dr);
4418 VEC_free (data_reference_p, heap, datarefs);
4423 /* Dump vertex I in RDG to FILE. */
4425 void
4426 dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
4428 struct vertex *v = &(rdg->vertices[i]);
4429 struct graph_edge *e;
4431 fprintf (file, "(vertex %d: (%s%s) (in:", i,
4432 RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
4433 RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
4435 if (v->pred)
4436 for (e = v->pred; e; e = e->pred_next)
4437 fprintf (file, " %d", e->src);
4439 fprintf (file, ") (out:");
4441 if (v->succ)
4442 for (e = v->succ; e; e = e->succ_next)
4443 fprintf (file, " %d", e->dest);
4445 fprintf (file, ") \n");
4446 print_generic_stmt (file, RDGV_STMT (v), TDF_VOPS|TDF_MEMSYMS);
4447 fprintf (file, ")\n");
4450 /* Call dump_rdg_vertex on stderr. */
4452 void
4453 debug_rdg_vertex (struct graph *rdg, int i)
4455 dump_rdg_vertex (stderr, rdg, i);
4458 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4459 dumped vertices to that bitmap. */
4461 void dump_rdg_component (FILE *file, struct graph *rdg, int c, bitmap dumped)
4463 int i;
4465 fprintf (file, "(%d\n", c);
4467 for (i = 0; i < rdg->n_vertices; i++)
4468 if (rdg->vertices[i].component == c)
4470 if (dumped)
4471 bitmap_set_bit (dumped, i);
4473 dump_rdg_vertex (file, rdg, i);
4476 fprintf (file, ")\n");
4479 /* Call dump_rdg_vertex on stderr. */
4481 void
4482 debug_rdg_component (struct graph *rdg, int c)
4484 dump_rdg_component (stderr, rdg, c, NULL);
4487 /* Dump the reduced dependence graph RDG to FILE. */
4489 void
4490 dump_rdg (FILE *file, struct graph *rdg)
4492 int i;
4493 bitmap dumped = BITMAP_ALLOC (NULL);
4495 fprintf (file, "(rdg\n");
4497 for (i = 0; i < rdg->n_vertices; i++)
4498 if (!bitmap_bit_p (dumped, i))
4499 dump_rdg_component (file, rdg, rdg->vertices[i].component, dumped);
4501 fprintf (file, ")\n");
4502 BITMAP_FREE (dumped);
4505 /* Call dump_rdg on stderr. */
4507 void
4508 debug_rdg (struct graph *rdg)
4510 dump_rdg (stderr, rdg);
4513 static void
4514 dot_rdg_1 (FILE *file, struct graph *rdg)
4516 int i;
4518 fprintf (file, "digraph RDG {\n");
4520 for (i = 0; i < rdg->n_vertices; i++)
4522 struct vertex *v = &(rdg->vertices[i]);
4523 struct graph_edge *e;
4525 /* Highlight reads from memory. */
4526 if (RDG_MEM_READS_STMT (rdg, i))
4527 fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
4529 /* Highlight stores to memory. */
4530 if (RDG_MEM_WRITE_STMT (rdg, i))
4531 fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
4533 if (v->succ)
4534 for (e = v->succ; e; e = e->succ_next)
4535 switch (RDGE_TYPE (e))
4537 case input_dd:
4538 fprintf (file, "%d -> %d [label=input] \n", i, e->dest);
4539 break;
4541 case output_dd:
4542 fprintf (file, "%d -> %d [label=output] \n", i, e->dest);
4543 break;
4545 case flow_dd:
4546 /* These are the most common dependences: don't print these. */
4547 fprintf (file, "%d -> %d \n", i, e->dest);
4548 break;
4550 case anti_dd:
4551 fprintf (file, "%d -> %d [label=anti] \n", i, e->dest);
4552 break;
4554 default:
4555 gcc_unreachable ();
4559 fprintf (file, "}\n\n");
4562 /* Display SCOP using dotty. */
4564 void
4565 dot_rdg (struct graph *rdg)
4567 FILE *file = fopen ("/tmp/rdg.dot", "w");
4568 gcc_assert (file != NULL);
4570 dot_rdg_1 (file, rdg);
4571 fclose (file);
4573 system ("dotty /tmp/rdg.dot");
4577 /* This structure is used for recording the mapping statement index in
4578 the RDG. */
4580 struct rdg_vertex_info GTY(())
4582 tree stmt;
4583 int index;
4586 /* Returns the index of STMT in RDG. */
4589 rdg_vertex_for_stmt (struct graph *rdg, tree stmt)
4591 struct rdg_vertex_info rvi, *slot;
4593 rvi.stmt = stmt;
4594 slot = (struct rdg_vertex_info *) htab_find (rdg->indices, &rvi);
4596 if (!slot)
4597 return -1;
4599 return slot->index;
4602 /* Creates an edge in RDG for each distance vector from DDR. The
4603 order that we keep track of in the RDG is the order in which
4604 statements have to be executed. */
4606 static void
4607 create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
4609 struct graph_edge *e;
4610 int va, vb;
4611 data_reference_p dra = DDR_A (ddr);
4612 data_reference_p drb = DDR_B (ddr);
4613 unsigned level = ddr_dependence_level (ddr);
4615 /* For non scalar dependences, when the dependence is REVERSED,
4616 statement B has to be executed before statement A. */
4617 if (level > 0
4618 && !DDR_REVERSED_P (ddr))
4620 data_reference_p tmp = dra;
4621 dra = drb;
4622 drb = tmp;
4625 va = rdg_vertex_for_stmt (rdg, DR_STMT (dra));
4626 vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb));
4628 if (va < 0 || vb < 0)
4629 return;
4631 e = add_edge (rdg, va, vb);
4632 e->data = XNEW (struct rdg_edge);
4634 RDGE_LEVEL (e) = level;
4636 /* Determines the type of the data dependence. */
4637 if (DR_IS_READ (dra) && DR_IS_READ (drb))
4638 RDGE_TYPE (e) = input_dd;
4639 else if (!DR_IS_READ (dra) && !DR_IS_READ (drb))
4640 RDGE_TYPE (e) = output_dd;
4641 else if (!DR_IS_READ (dra) && DR_IS_READ (drb))
4642 RDGE_TYPE (e) = flow_dd;
4643 else if (DR_IS_READ (dra) && !DR_IS_READ (drb))
4644 RDGE_TYPE (e) = anti_dd;
4647 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
4648 the index of DEF in RDG. */
4650 static void
4651 create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
4653 use_operand_p imm_use_p;
4654 imm_use_iterator iterator;
4656 FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
4658 struct graph_edge *e;
4659 int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
4661 if (use < 0)
4662 continue;
4664 e = add_edge (rdg, idef, use);
4665 e->data = XNEW (struct rdg_edge);
4666 RDGE_TYPE (e) = flow_dd;
4670 /* Creates the edges of the reduced dependence graph RDG. */
4672 static void
4673 create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs)
4675 int i;
4676 struct data_dependence_relation *ddr;
4677 def_operand_p def_p;
4678 ssa_op_iter iter;
4680 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
4681 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4682 create_rdg_edge_for_ddr (rdg, ddr);
4684 for (i = 0; i < rdg->n_vertices; i++)
4685 FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
4686 iter, SSA_OP_DEF)
4687 create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
4690 /* Build the vertices of the reduced dependence graph RDG. */
4692 static void
4693 create_rdg_vertices (struct graph *rdg, VEC (tree, heap) *stmts)
4695 int i, j;
4696 tree stmt;
4698 for (i = 0; VEC_iterate (tree, stmts, i, stmt); i++)
4700 VEC (data_ref_loc, heap) *references;
4701 data_ref_loc *ref;
4702 struct vertex *v = &(rdg->vertices[i]);
4703 struct rdg_vertex_info *rvi = XNEW (struct rdg_vertex_info);
4704 struct rdg_vertex_info **slot;
4706 rvi->stmt = stmt;
4707 rvi->index = i;
4708 slot = (struct rdg_vertex_info **) htab_find_slot (rdg->indices, rvi, INSERT);
4710 if (!*slot)
4711 *slot = rvi;
4712 else
4713 free (rvi);
4715 v->data = XNEW (struct rdg_vertex);
4716 RDG_STMT (rdg, i) = stmt;
4718 RDG_MEM_WRITE_STMT (rdg, i) = false;
4719 RDG_MEM_READS_STMT (rdg, i) = false;
4720 if (TREE_CODE (stmt) == PHI_NODE)
4721 continue;
4723 get_references_in_stmt (stmt, &references);
4724 for (j = 0; VEC_iterate (data_ref_loc, references, j, ref); j++)
4725 if (!ref->is_read)
4726 RDG_MEM_WRITE_STMT (rdg, i) = true;
4727 else
4728 RDG_MEM_READS_STMT (rdg, i) = true;
4730 VEC_free (data_ref_loc, heap, references);
4734 /* Initialize STMTS with all the statements of LOOP. When
4735 INCLUDE_PHIS is true, include also the PHI nodes. The order in
4736 which we discover statements is important as
4737 generate_loops_for_partition is using the same traversal for
4738 identifying statements. */
4740 static void
4741 stmts_from_loop (struct loop *loop, VEC (tree, heap) **stmts)
4743 unsigned int i;
4744 basic_block *bbs = get_loop_body_in_dom_order (loop);
4746 for (i = 0; i < loop->num_nodes; i++)
4748 tree phi, stmt;
4749 basic_block bb = bbs[i];
4750 block_stmt_iterator bsi;
4752 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4753 VEC_safe_push (tree, heap, *stmts, phi);
4755 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4756 if (TREE_CODE (stmt = bsi_stmt (bsi)) != LABEL_EXPR)
4757 VEC_safe_push (tree, heap, *stmts, stmt);
4760 free (bbs);
4763 /* Returns true when all the dependences are computable. */
4765 static bool
4766 known_dependences_p (VEC (ddr_p, heap) *dependence_relations)
4768 ddr_p ddr;
4769 unsigned int i;
4771 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4772 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
4773 return false;
4775 return true;
4778 /* Computes a hash function for element ELT. */
4780 static hashval_t
4781 hash_stmt_vertex_info (const void *elt)
4783 const struct rdg_vertex_info *const rvi =
4784 (const struct rdg_vertex_info *) elt;
4785 const_tree stmt = rvi->stmt;
4787 return htab_hash_pointer (stmt);
4790 /* Compares database elements E1 and E2. */
4792 static int
4793 eq_stmt_vertex_info (const void *e1, const void *e2)
4795 const struct rdg_vertex_info *elt1 = (const struct rdg_vertex_info *) e1;
4796 const struct rdg_vertex_info *elt2 = (const struct rdg_vertex_info *) e2;
4798 return elt1->stmt == elt2->stmt;
4801 /* Free the element E. */
4803 static void
4804 hash_stmt_vertex_del (void *e)
4806 free (e);
4809 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4810 statement of the loop nest, and one edge per data dependence or
4811 scalar dependence. */
4813 struct graph *
4814 build_rdg (struct loop *loop)
4816 int nb_data_refs = 10;
4817 struct graph *rdg = NULL;
4818 VEC (ddr_p, heap) *dependence_relations;
4819 VEC (data_reference_p, heap) *datarefs;
4820 VEC (tree, heap) *stmts = VEC_alloc (tree, heap, nb_data_refs);
4822 dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs) ;
4823 datarefs = VEC_alloc (data_reference_p, heap, nb_data_refs);
4824 compute_data_dependences_for_loop (loop,
4825 false,
4826 &datarefs,
4827 &dependence_relations);
4829 if (!known_dependences_p (dependence_relations))
4830 goto end_rdg;
4832 stmts_from_loop (loop, &stmts);
4833 rdg = new_graph (VEC_length (tree, stmts));
4835 rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
4836 eq_stmt_vertex_info, hash_stmt_vertex_del);
4837 create_rdg_vertices (rdg, stmts);
4838 create_rdg_edges (rdg, dependence_relations);
4840 end_rdg:
4841 free_dependence_relations (dependence_relations);
4842 free_data_refs (datarefs);
4843 VEC_free (tree, heap, stmts);
4845 return rdg;
4848 /* Free the reduced dependence graph RDG. */
4850 void
4851 free_rdg (struct graph *rdg)
4853 int i;
4855 for (i = 0; i < rdg->n_vertices; i++)
4856 free (rdg->vertices[i].data);
4858 htab_delete (rdg->indices);
4859 free_graph (rdg);
4862 /* Initialize STMTS with all the statements of LOOP that contain a
4863 store to memory. */
4865 void
4866 stores_from_loop (struct loop *loop, VEC (tree, heap) **stmts)
4868 unsigned int i;
4869 basic_block *bbs = get_loop_body_in_dom_order (loop);
4871 for (i = 0; i < loop->num_nodes; i++)
4873 basic_block bb = bbs[i];
4874 block_stmt_iterator bsi;
4876 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4877 if (!ZERO_SSA_OPERANDS (bsi_stmt (bsi), SSA_OP_VDEF))
4878 VEC_safe_push (tree, heap, *stmts, bsi_stmt (bsi));
4881 free (bbs);
4884 /* For a data reference REF, return the declaration of its base
4885 address or NULL_TREE if the base is not determined. */
4887 static inline tree
4888 ref_base_address (tree stmt, data_ref_loc *ref)
4890 tree base = NULL_TREE;
4891 tree base_address;
4892 struct data_reference *dr = XCNEW (struct data_reference);
4894 DR_STMT (dr) = stmt;
4895 DR_REF (dr) = *ref->pos;
4896 dr_analyze_innermost (dr);
4897 base_address = DR_BASE_ADDRESS (dr);
4899 if (!base_address)
4900 goto end;
4902 switch (TREE_CODE (base_address))
4904 case ADDR_EXPR:
4905 base = TREE_OPERAND (base_address, 0);
4906 break;
4908 default:
4909 base = base_address;
4910 break;
4913 end:
4914 free_data_ref (dr);
4915 return base;
4918 /* Determines whether the statement from vertex V of the RDG has a
4919 definition used outside the loop that contains this statement. */
4921 bool
4922 rdg_defs_used_in_other_loops_p (struct graph *rdg, int v)
4924 tree stmt = RDG_STMT (rdg, v);
4925 struct loop *loop = loop_containing_stmt (stmt);
4926 use_operand_p imm_use_p;
4927 imm_use_iterator iterator;
4928 ssa_op_iter it;
4929 def_operand_p def_p;
4931 if (!loop)
4932 return true;
4934 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF)
4936 FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p))
4938 if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop)
4939 return true;
4943 return false;
4946 /* Determines whether statements S1 and S2 access to similar memory
4947 locations. Two memory accesses are considered similar when they
4948 have the same base address declaration, i.e. when their
4949 ref_base_address is the same. */
4951 bool
4952 have_similar_memory_accesses (tree s1, tree s2)
4954 bool res = false;
4955 unsigned i, j;
4956 VEC (data_ref_loc, heap) *refs1, *refs2;
4957 data_ref_loc *ref1, *ref2;
4959 get_references_in_stmt (s1, &refs1);
4960 get_references_in_stmt (s2, &refs2);
4962 for (i = 0; VEC_iterate (data_ref_loc, refs1, i, ref1); i++)
4964 tree base1 = ref_base_address (s1, ref1);
4966 if (base1)
4967 for (j = 0; VEC_iterate (data_ref_loc, refs2, j, ref2); j++)
4968 if (base1 == ref_base_address (s2, ref2))
4970 res = true;
4971 goto end;
4975 end:
4976 VEC_free (data_ref_loc, heap, refs1);
4977 VEC_free (data_ref_loc, heap, refs2);
4978 return res;
4981 /* Helper function for the hashtab. */
4983 static int
4984 have_similar_memory_accesses_1 (const void *s1, const void *s2)
4986 return have_similar_memory_accesses (CONST_CAST_TREE ((const_tree)s1),
4987 CONST_CAST_TREE ((const_tree)s2));
4990 /* Helper function for the hashtab. */
4992 static hashval_t
4993 ref_base_address_1 (const void *s)
4995 tree stmt = CONST_CAST_TREE((const_tree)s);
4996 unsigned i;
4997 VEC (data_ref_loc, heap) *refs;
4998 data_ref_loc *ref;
4999 hashval_t res = 0;
5001 get_references_in_stmt (stmt, &refs);
5003 for (i = 0; VEC_iterate (data_ref_loc, refs, i, ref); i++)
5004 if (!ref->is_read)
5006 res = htab_hash_pointer (ref_base_address (stmt, ref));
5007 break;
5010 VEC_free (data_ref_loc, heap, refs);
5011 return res;
5014 /* Try to remove duplicated write data references from STMTS. */
5016 void
5017 remove_similar_memory_refs (VEC (tree, heap) **stmts)
5019 unsigned i;
5020 tree stmt;
5021 htab_t seen = htab_create (VEC_length (tree, *stmts), ref_base_address_1,
5022 have_similar_memory_accesses_1, NULL);
5024 for (i = 0; VEC_iterate (tree, *stmts, i, stmt); )
5026 void **slot;
5028 slot = htab_find_slot (seen, stmt, INSERT);
5030 if (*slot)
5031 VEC_ordered_remove (tree, *stmts, i);
5032 else
5034 *slot = (void *) stmt;
5035 i++;
5039 htab_delete (seen);
5042 /* Returns the index of PARAMETER in the parameters vector of the
5043 ACCESS_MATRIX. If PARAMETER does not exist return -1. */
5045 int
5046 access_matrix_get_index_for_parameter (tree parameter,
5047 struct access_matrix *access_matrix)
5049 int i;
5050 VEC (tree,heap) *lambda_parameters = AM_PARAMETERS (access_matrix);
5051 tree lambda_parameter;
5053 for (i = 0; VEC_iterate (tree, lambda_parameters, i, lambda_parameter); i++)
5054 if (lambda_parameter == parameter)
5055 return i + AM_NB_INDUCTION_VARS (access_matrix);
5057 return -1;