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 2, or (at your option) any later
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
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 /* This pass walks a given loop structure searching for array
23 references. The information about the array accesses is recorded
24 in DATA_REFERENCE structures.
26 The basic test for determining the dependences is:
27 given two access functions chrec1 and chrec2 to a same array, and
28 x and y two vectors from the iteration domain, the same element of
29 the array is accessed twice at iterations x and y if and only if:
30 | chrec1 (x) == chrec2 (y).
32 The goals of this analysis are:
34 - to determine the independence: the relation between two
35 independent accesses is qualified with the chrec_known (this
36 information allows a loop parallelization),
38 - when two data references access the same data, to qualify the
39 dependence relation with classic dependence representations:
43 - loop carried level dependence
44 - polyhedron dependence
45 or with the chains of recurrences based representation,
47 - to define a knowledge base for storing the data dependence
50 - to define an interface to access this data.
55 - subscript: given two array accesses a subscript is the tuple
56 composed of the access functions for a given dimension. Example:
57 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
58 (f1, g1), (f2, g2), (f3, g3).
60 - Diophantine equation: an equation whose coefficients and
61 solutions are integer constants, for example the equation
63 has an integer solution x = 1 and y = -1.
67 - "Advanced Compilation for High Performance Computing" by Randy
68 Allen and Ken Kennedy.
69 http://citeseer.ist.psu.edu/goff91practical.html
71 - "Loop Transformations for Restructuring Compilers - The Foundations"
79 #include "coretypes.h"
84 /* These RTL headers are needed for basic-block.h. */
86 #include "basic-block.h"
87 #include "diagnostic.h"
88 #include "tree-flow.h"
89 #include "tree-dump.h"
92 #include "tree-chrec.h"
93 #include "tree-data-ref.h"
94 #include "tree-scalar-evolution.h"
95 #include "tree-pass.h"
96 #include "langhooks.h"
98 static struct datadep_stats
100 int num_dependence_tests;
101 int num_dependence_dependent;
102 int num_dependence_independent;
103 int num_dependence_undetermined;
105 int num_subscript_tests;
106 int num_subscript_undetermined;
107 int num_same_subscript_function;
110 int num_ziv_independent;
111 int num_ziv_dependent;
112 int num_ziv_unimplemented;
115 int num_siv_independent;
116 int num_siv_dependent;
117 int num_siv_unimplemented;
120 int num_miv_independent;
121 int num_miv_dependent;
122 int num_miv_unimplemented;
125 static tree object_analysis (tree, tree, bool, struct data_reference **,
126 tree *, tree *, tree *, tree *, tree *,
127 struct ptr_info_def **, subvar_t *);
128 static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
129 struct data_reference *,
130 struct data_reference *);
132 /* Determine if PTR and DECL may alias, the result is put in ALIASED.
133 Return FALSE if there is no symbol memory tag for PTR. */
136 ptr_decl_may_alias_p (tree ptr, tree decl,
137 struct data_reference *ptr_dr,
140 tree tag = NULL_TREE;
141 struct ptr_info_def *pi = DR_PTR_INFO (ptr_dr);
143 gcc_assert (TREE_CODE (ptr) == SSA_NAME && DECL_P (decl));
146 tag = pi->name_mem_tag;
148 tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
150 tag = DR_MEMTAG (ptr_dr);
154 *aliased = is_aliased_with (tag, decl);
159 /* Determine if two pointers may alias, the result is put in ALIASED.
160 Return FALSE if there is no symbol memory tag for one of the pointers. */
163 ptr_ptr_may_alias_p (tree ptr_a, tree ptr_b,
164 struct data_reference *dra,
165 struct data_reference *drb,
168 tree tag_a = NULL_TREE, tag_b = NULL_TREE;
169 struct ptr_info_def *pi_a = DR_PTR_INFO (dra);
170 struct ptr_info_def *pi_b = DR_PTR_INFO (drb);
173 if (pi_a && pi_a->name_mem_tag && pi_b && pi_b->name_mem_tag)
175 tag_a = pi_a->name_mem_tag;
176 tag_b = pi_b->name_mem_tag;
180 tag_a = symbol_mem_tag (SSA_NAME_VAR (ptr_a));
182 tag_a = DR_MEMTAG (dra);
186 tag_b = symbol_mem_tag (SSA_NAME_VAR (ptr_b));
188 tag_b = DR_MEMTAG (drb);
192 bal1 = BITMAP_ALLOC (NULL);
193 bitmap_set_bit (bal1, DECL_UID (tag_a));
194 if (MTAG_P (tag_a) && MTAG_ALIASES (tag_a))
195 bitmap_ior_into (bal1, MTAG_ALIASES (tag_a));
197 bal2 = BITMAP_ALLOC (NULL);
198 bitmap_set_bit (bal2, DECL_UID (tag_b));
199 if (MTAG_P (tag_b) && MTAG_ALIASES (tag_b))
200 bitmap_ior_into (bal2, MTAG_ALIASES (tag_b));
201 *aliased = bitmap_intersect_p (bal1, bal2);
209 /* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED.
210 Return FALSE if there is no symbol memory tag for one of the symbols. */
213 may_alias_p (tree base_a, tree base_b,
214 struct data_reference *dra,
215 struct data_reference *drb,
218 if (TREE_CODE (base_a) == ADDR_EXPR || TREE_CODE (base_b) == ADDR_EXPR)
220 if (TREE_CODE (base_a) == ADDR_EXPR && TREE_CODE (base_b) == ADDR_EXPR)
222 *aliased = (TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0));
225 if (TREE_CODE (base_a) == ADDR_EXPR)
226 return ptr_decl_may_alias_p (base_b, TREE_OPERAND (base_a, 0), drb,
229 return ptr_decl_may_alias_p (base_a, TREE_OPERAND (base_b, 0), dra,
233 return ptr_ptr_may_alias_p (base_a, base_b, dra, drb, aliased);
237 /* Determine if a pointer (BASE_A) and a record/union access (BASE_B)
238 are not aliased. Return TRUE if they differ. */
240 record_ptr_differ_p (struct data_reference *dra,
241 struct data_reference *drb)
244 tree base_a = DR_BASE_OBJECT (dra);
245 tree base_b = DR_BASE_OBJECT (drb);
247 if (TREE_CODE (base_b) != COMPONENT_REF)
250 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
251 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
252 Probably will be unnecessary with struct alias analysis. */
253 while (TREE_CODE (base_b) == COMPONENT_REF)
254 base_b = TREE_OPERAND (base_b, 0);
255 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
257 if (TREE_CODE (base_a) == INDIRECT_REF
258 && ((TREE_CODE (base_b) == VAR_DECL
259 && (ptr_decl_may_alias_p (TREE_OPERAND (base_a, 0), base_b, dra,
262 || (TREE_CODE (base_b) == INDIRECT_REF
263 && (ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0),
264 TREE_OPERAND (base_b, 0), dra, drb,
272 /* Determine if two record/union accesses are aliased. Return TRUE if they
275 record_record_differ_p (struct data_reference *dra,
276 struct data_reference *drb)
279 tree base_a = DR_BASE_OBJECT (dra);
280 tree base_b = DR_BASE_OBJECT (drb);
282 if (TREE_CODE (base_b) != COMPONENT_REF
283 || TREE_CODE (base_a) != COMPONENT_REF)
286 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
287 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
288 Probably will be unnecessary with struct alias analysis. */
289 while (TREE_CODE (base_b) == COMPONENT_REF)
290 base_b = TREE_OPERAND (base_b, 0);
291 while (TREE_CODE (base_a) == COMPONENT_REF)
292 base_a = TREE_OPERAND (base_a, 0);
294 if (TREE_CODE (base_a) == INDIRECT_REF
295 && TREE_CODE (base_b) == INDIRECT_REF
296 && ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0),
297 TREE_OPERAND (base_b, 0),
305 /* Determine if an array access (BASE_A) and a record/union access (BASE_B)
306 are not aliased. Return TRUE if they differ. */
308 record_array_differ_p (struct data_reference *dra,
309 struct data_reference *drb)
312 tree base_a = DR_BASE_OBJECT (dra);
313 tree base_b = DR_BASE_OBJECT (drb);
315 if (TREE_CODE (base_b) != COMPONENT_REF)
318 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
319 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
320 Probably will be unnecessary with struct alias analysis. */
321 while (TREE_CODE (base_b) == COMPONENT_REF)
322 base_b = TREE_OPERAND (base_b, 0);
324 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
325 (a[i]). In case of p->c[i] use alias analysis to verify that p is not
327 if (TREE_CODE (base_a) == VAR_DECL
328 && (TREE_CODE (base_b) == VAR_DECL
329 || (TREE_CODE (base_b) == INDIRECT_REF
330 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb,
339 /* Determine if an array access (BASE_A) and a pointer (BASE_B)
340 are not aliased. Return TRUE if they differ. */
342 array_ptr_differ_p (tree base_a, tree base_b,
343 struct data_reference *drb)
347 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
348 help of alias analysis that p is not pointing to a. */
349 if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == INDIRECT_REF
350 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, &aliased)
358 /* This is the simplest data dependence test: determines whether the
359 data references A and B access the same array/region. Returns
360 false when the property is not computable at compile time.
361 Otherwise return true, and DIFFER_P will record the result. This
362 utility will not be necessary when alias_sets_conflict_p will be
363 less conservative. */
366 base_object_differ_p (struct data_reference *a,
367 struct data_reference *b,
370 tree base_a = DR_BASE_OBJECT (a);
371 tree base_b = DR_BASE_OBJECT (b);
374 if (!base_a || !base_b)
377 /* Determine if same base. Example: for the array accesses
378 a[i], b[i] or pointer accesses *a, *b, bases are a, b. */
379 if (base_a == base_b)
385 /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
387 if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
388 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0))
394 /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */
395 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
396 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)
397 && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1))
404 /* Determine if different bases. */
406 /* At this point we know that base_a != base_b. However, pointer
407 accesses of the form x=(*p) and y=(*q), whose bases are p and q,
408 may still be pointing to the same base. In SSAed GIMPLE p and q will
409 be SSA_NAMES in this case. Therefore, here we check if they are
410 really two different declarations. */
411 if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
417 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
418 help of alias analysis that p is not pointing to a. */
419 if (array_ptr_differ_p (base_a, base_b, b)
420 || array_ptr_differ_p (base_b, base_a, a))
426 /* If the bases are pointers ((*q)[i] and (*p)[i]), we check with the
427 help of alias analysis they don't point to the same bases. */
428 if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
429 && (may_alias_p (TREE_OPERAND (base_a, 0), TREE_OPERAND (base_b, 0), a, b,
437 /* Compare two record/union bases s.a and t.b: s != t or (a != b and
438 s and t are not unions). */
439 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
440 && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
441 && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
442 && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
443 || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE
444 && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
445 && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
451 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
453 if (record_ptr_differ_p (a, b) || record_ptr_differ_p (b, a))
459 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
460 (a[i]). In case of p->c[i] use alias analysis to verify that p is not
462 if (record_array_differ_p (a, b) || record_array_differ_p (b, a))
468 /* Compare two record/union accesses (b.c[i] or p->c[i]). */
469 if (record_record_differ_p (a, b))
478 /* Function base_addr_differ_p.
480 This is the simplest data dependence test: determines whether the
481 data references DRA and DRB access the same array/region. Returns
482 false when the property is not computable at compile time.
483 Otherwise return true, and DIFFER_P will record the result.
486 1. if (both DRA and DRB are represented as arrays)
487 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT
488 2. else if (both DRA and DRB are represented as pointers)
489 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION
490 3. else if (DRA and DRB are represented differently or 2. fails)
491 only try to prove that the bases are surely different
495 base_addr_differ_p (struct data_reference *dra,
496 struct data_reference *drb,
499 tree addr_a = DR_BASE_ADDRESS (dra);
500 tree addr_b = DR_BASE_ADDRESS (drb);
505 if (!addr_a || !addr_b)
508 type_a = TREE_TYPE (addr_a);
509 type_b = TREE_TYPE (addr_b);
511 gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
513 /* 1. if (both DRA and DRB are represented as arrays)
514 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT. */
515 if (DR_TYPE (dra) == ARRAY_REF_TYPE && DR_TYPE (drb) == ARRAY_REF_TYPE)
516 return base_object_differ_p (dra, drb, differ_p);
518 /* 2. else if (both DRA and DRB are represented as pointers)
519 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION. */
520 /* If base addresses are the same, we check the offsets, since the access of
521 the data-ref is described by {base addr + offset} and its access function,
522 i.e., in order to decide whether the bases of data-refs are the same we
523 compare both base addresses and offsets. */
524 if (DR_TYPE (dra) == POINTER_REF_TYPE && DR_TYPE (drb) == POINTER_REF_TYPE
526 || (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR
527 && TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0))))
529 /* Compare offsets. */
530 tree offset_a = DR_OFFSET (dra);
531 tree offset_b = DR_OFFSET (drb);
533 STRIP_NOPS (offset_a);
534 STRIP_NOPS (offset_b);
536 /* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle
538 if (offset_a == offset_b
539 || (TREE_CODE (offset_a) == MULT_EXPR
540 && TREE_CODE (offset_b) == MULT_EXPR
541 && TREE_OPERAND (offset_a, 0) == TREE_OPERAND (offset_b, 0)
542 && TREE_OPERAND (offset_a, 1) == TREE_OPERAND (offset_b, 1)))
549 /* 3. else if (DRA and DRB are represented differently or 2. fails)
550 only try to prove that the bases are surely different. */
552 /* Apply alias analysis. */
553 if (may_alias_p (addr_a, addr_b, dra, drb, &aliased) && !aliased)
559 /* An instruction writing through a restricted pointer is "independent" of any
560 instruction reading or writing through a different restricted pointer,
561 in the same block/scope. */
562 else if (TYPE_RESTRICT (type_a)
563 && TYPE_RESTRICT (type_b)
564 && (!DR_IS_READ (drb) || !DR_IS_READ (dra))
565 && TREE_CODE (DR_BASE_ADDRESS (dra)) == SSA_NAME
566 && (decl_a = SSA_NAME_VAR (DR_BASE_ADDRESS (dra)))
567 && TREE_CODE (decl_a) == PARM_DECL
568 && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL
569 && TREE_CODE (DR_BASE_ADDRESS (drb)) == SSA_NAME
570 && (decl_b = SSA_NAME_VAR (DR_BASE_ADDRESS (drb)))
571 && TREE_CODE (decl_b) == PARM_DECL
572 && TREE_CODE (DECL_CONTEXT (decl_b)) == FUNCTION_DECL
573 && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b))
582 /* Returns true iff A divides B. */
585 tree_fold_divides_p (tree a, tree b)
587 gcc_assert (TREE_CODE (a) == INTEGER_CST);
588 gcc_assert (TREE_CODE (b) == INTEGER_CST);
589 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a, 0));
592 /* Returns true iff A divides B. */
595 int_divides_p (int a, int b)
597 return ((b % a) == 0);
602 /* Dump into FILE all the data references from DATAREFS. */
605 dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
608 struct data_reference *dr;
610 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
611 dump_data_reference (file, dr);
614 /* Dump into FILE all the dependence relations from DDRS. */
617 dump_data_dependence_relations (FILE *file,
618 VEC (ddr_p, heap) *ddrs)
621 struct data_dependence_relation *ddr;
623 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
624 dump_data_dependence_relation (file, ddr);
627 /* Dump function for a DATA_REFERENCE structure. */
630 dump_data_reference (FILE *outf,
631 struct data_reference *dr)
635 fprintf (outf, "(Data Ref: \n stmt: ");
636 print_generic_stmt (outf, DR_STMT (dr), 0);
637 fprintf (outf, " ref: ");
638 print_generic_stmt (outf, DR_REF (dr), 0);
639 fprintf (outf, " base_object: ");
640 print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
642 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
644 fprintf (outf, " Access function %d: ", i);
645 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
647 fprintf (outf, ")\n");
650 /* Dumps the affine function described by FN to the file OUTF. */
653 dump_affine_function (FILE *outf, affine_fn fn)
658 print_generic_expr (outf, VEC_index (tree, fn, 0), TDF_SLIM);
659 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
661 fprintf (outf, " + ");
662 print_generic_expr (outf, coef, TDF_SLIM);
663 fprintf (outf, " * x_%u", i);
667 /* Dumps the conflict function CF to the file OUTF. */
670 dump_conflict_function (FILE *outf, conflict_function *cf)
674 if (cf->n == NO_DEPENDENCE)
675 fprintf (outf, "no dependence\n");
676 else if (cf->n == NOT_KNOWN)
677 fprintf (outf, "not known\n");
680 for (i = 0; i < cf->n; i++)
683 dump_affine_function (outf, cf->fns[i]);
684 fprintf (outf, "]\n");
689 /* Dump function for a SUBSCRIPT structure. */
692 dump_subscript (FILE *outf, struct subscript *subscript)
694 conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
696 fprintf (outf, "\n (subscript \n");
697 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
698 dump_conflict_function (outf, cf);
699 if (CF_NONTRIVIAL_P (cf))
701 tree last_iteration = SUB_LAST_CONFLICT (subscript);
702 fprintf (outf, " last_conflict: ");
703 print_generic_stmt (outf, last_iteration, 0);
706 cf = SUB_CONFLICTS_IN_B (subscript);
707 fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
708 dump_conflict_function (outf, cf);
709 if (CF_NONTRIVIAL_P (cf))
711 tree last_iteration = SUB_LAST_CONFLICT (subscript);
712 fprintf (outf, " last_conflict: ");
713 print_generic_stmt (outf, last_iteration, 0);
716 fprintf (outf, " (Subscript distance: ");
717 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
718 fprintf (outf, " )\n");
719 fprintf (outf, " )\n");
722 /* Print the classic direction vector DIRV to OUTF. */
725 print_direction_vector (FILE *outf,
731 for (eq = 0; eq < length; eq++)
733 enum data_dependence_direction dir = dirv[eq];
738 fprintf (outf, " +");
741 fprintf (outf, " -");
744 fprintf (outf, " =");
746 case dir_positive_or_equal:
747 fprintf (outf, " +=");
749 case dir_positive_or_negative:
750 fprintf (outf, " +-");
752 case dir_negative_or_equal:
753 fprintf (outf, " -=");
756 fprintf (outf, " *");
759 fprintf (outf, "indep");
763 fprintf (outf, "\n");
766 /* Print a vector of direction vectors. */
769 print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
775 for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++)
776 print_direction_vector (outf, v, length);
779 /* Print a vector of distance vectors. */
782 print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
788 for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++)
789 print_lambda_vector (outf, v, length);
795 debug_data_dependence_relation (struct data_dependence_relation *ddr)
797 dump_data_dependence_relation (stderr, ddr);
800 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
803 dump_data_dependence_relation (FILE *outf,
804 struct data_dependence_relation *ddr)
806 struct data_reference *dra, *drb;
810 fprintf (outf, "(Data Dep: \n");
811 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
812 fprintf (outf, " (don't know)\n");
814 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
815 fprintf (outf, " (no dependence)\n");
817 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
822 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
824 fprintf (outf, " access_fn_A: ");
825 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
826 fprintf (outf, " access_fn_B: ");
827 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
828 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
831 fprintf (outf, " inner loop index: %d\n", DDR_INNER_LOOP (ddr));
832 fprintf (outf, " loop nest: (");
833 for (i = 0; VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
834 fprintf (outf, "%d ", loopi->num);
835 fprintf (outf, ")\n");
837 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
839 fprintf (outf, " distance_vector: ");
840 print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
844 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
846 fprintf (outf, " direction_vector: ");
847 print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
852 fprintf (outf, ")\n");
855 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
858 dump_data_dependence_direction (FILE *file,
859 enum data_dependence_direction dir)
875 case dir_positive_or_negative:
876 fprintf (file, "+-");
879 case dir_positive_or_equal:
880 fprintf (file, "+=");
883 case dir_negative_or_equal:
884 fprintf (file, "-=");
896 /* Dumps the distance and direction vectors in FILE. DDRS contains
897 the dependence relations, and VECT_SIZE is the size of the
898 dependence vectors, or in other words the number of loops in the
902 dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
905 struct data_dependence_relation *ddr;
908 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
909 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
911 for (j = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), j, v); j++)
913 fprintf (file, "DISTANCE_V (");
914 print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
915 fprintf (file, ")\n");
918 for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++)
920 fprintf (file, "DIRECTION_V (");
921 print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
922 fprintf (file, ")\n");
926 fprintf (file, "\n\n");
929 /* Dumps the data dependence relations DDRS in FILE. */
932 dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
935 struct data_dependence_relation *ddr;
937 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
938 dump_data_dependence_relation (file, ddr);
940 fprintf (file, "\n\n");
945 /* Given an ARRAY_REF node REF, records its access functions.
946 Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
947 i.e. the constant "3", then recursively call the function on opnd0,
948 i.e. the ARRAY_REF "A[i]".
949 The function returns the base name: "A". */
952 analyze_array_indexes (struct loop *loop,
953 VEC(tree,heap) **access_fns,
959 opnd0 = TREE_OPERAND (ref, 0);
960 opnd1 = TREE_OPERAND (ref, 1);
962 /* The detection of the evolution function for this data access is
963 postponed until the dependence test. This lazy strategy avoids
964 the computation of access functions that are of no interest for
966 access_fn = instantiate_parameters
967 (loop, analyze_scalar_evolution (loop, opnd1));
969 VEC_safe_push (tree, heap, *access_fns, access_fn);
971 /* Recursively record other array access functions. */
972 if (TREE_CODE (opnd0) == ARRAY_REF)
973 return analyze_array_indexes (loop, access_fns, opnd0, stmt);
975 /* Return the base name of the data access. */
980 /* For a data reference REF contained in the statement STMT, initialize
981 a DATA_REFERENCE structure, and return it. IS_READ flag has to be
982 set to true when REF is in the right hand side of an
985 static struct data_reference *
986 init_array_ref (tree stmt, tree ref, bool is_read)
988 struct loop *loop = loop_containing_stmt (stmt);
989 VEC(tree,heap) *acc_fns = VEC_alloc (tree, heap, 3);
990 struct data_reference *res = XNEW (struct data_reference);;
992 if (dump_file && (dump_flags & TDF_DETAILS))
994 fprintf (dump_file, "(init_array_ref \n");
995 fprintf (dump_file, " (ref = ");
996 print_generic_stmt (dump_file, ref, 0);
997 fprintf (dump_file, ")\n");
1000 DR_STMT (res) = stmt;
1002 DR_BASE_OBJECT (res) = analyze_array_indexes (loop, &acc_fns, ref, stmt);
1003 DR_TYPE (res) = ARRAY_REF_TYPE;
1004 DR_SET_ACCESS_FNS (res, acc_fns);
1005 DR_IS_READ (res) = is_read;
1006 DR_BASE_ADDRESS (res) = NULL_TREE;
1007 DR_OFFSET (res) = NULL_TREE;
1008 DR_INIT (res) = NULL_TREE;
1009 DR_STEP (res) = NULL_TREE;
1010 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
1011 DR_MEMTAG (res) = NULL_TREE;
1012 DR_PTR_INFO (res) = NULL;
1014 if (dump_file && (dump_flags & TDF_DETAILS))
1015 fprintf (dump_file, ")\n");
1020 /* For a data reference REF contained in the statement STMT, initialize
1021 a DATA_REFERENCE structure, and return it. */
1023 static struct data_reference *
1024 init_pointer_ref (tree stmt, tree ref, tree access_fn, bool is_read,
1025 tree base_address, tree step, struct ptr_info_def *ptr_info)
1027 struct data_reference *res = XNEW (struct data_reference);
1028 VEC(tree,heap) *acc_fns = VEC_alloc (tree, heap, 3);
1030 if (dump_file && (dump_flags & TDF_DETAILS))
1032 fprintf (dump_file, "(init_pointer_ref \n");
1033 fprintf (dump_file, " (ref = ");
1034 print_generic_stmt (dump_file, ref, 0);
1035 fprintf (dump_file, ")\n");
1038 DR_STMT (res) = stmt;
1040 DR_BASE_OBJECT (res) = NULL_TREE;
1041 DR_TYPE (res) = POINTER_REF_TYPE;
1042 DR_SET_ACCESS_FNS (res, acc_fns);
1043 VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
1044 DR_IS_READ (res) = is_read;
1045 DR_BASE_ADDRESS (res) = base_address;
1046 DR_OFFSET (res) = NULL_TREE;
1047 DR_INIT (res) = NULL_TREE;
1048 DR_STEP (res) = step;
1049 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
1050 DR_MEMTAG (res) = NULL_TREE;
1051 DR_PTR_INFO (res) = ptr_info;
1053 if (dump_file && (dump_flags & TDF_DETAILS))
1054 fprintf (dump_file, ")\n");
1059 /* Analyze an indirect memory reference, REF, that comes from STMT.
1060 IS_READ is true if this is an indirect load, and false if it is
1062 Return a new data reference structure representing the indirect_ref, or
1063 NULL if we cannot describe the access function. */
1065 static struct data_reference *
1066 analyze_indirect_ref (tree stmt, tree ref, bool is_read)
1068 struct loop *loop = loop_containing_stmt (stmt);
1069 tree ptr_ref = TREE_OPERAND (ref, 0);
1070 tree access_fn = analyze_scalar_evolution (loop, ptr_ref);
1071 tree init = initial_condition_in_loop_num (access_fn, loop->num);
1072 tree base_address = NULL_TREE, evolution, step = NULL_TREE;
1073 struct ptr_info_def *ptr_info = NULL;
1075 if (TREE_CODE (ptr_ref) == SSA_NAME)
1076 ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
1079 if (access_fn == chrec_dont_know || !init || init == chrec_dont_know)
1081 if (dump_file && (dump_flags & TDF_DETAILS))
1083 fprintf (dump_file, "\nBad access function of ptr: ");
1084 print_generic_expr (dump_file, ref, TDF_SLIM);
1085 fprintf (dump_file, "\n");
1090 if (dump_file && (dump_flags & TDF_DETAILS))
1092 fprintf (dump_file, "\nAccess function of ptr: ");
1093 print_generic_expr (dump_file, access_fn, TDF_SLIM);
1094 fprintf (dump_file, "\n");
1097 if (!expr_invariant_in_loop_p (loop, init))
1099 if (dump_file && (dump_flags & TDF_DETAILS))
1100 fprintf (dump_file, "\ninitial condition is not loop invariant.\n");
1104 base_address = init;
1105 evolution = evolution_part_in_loop_num (access_fn, loop->num);
1106 if (evolution != chrec_dont_know)
1109 step = ssize_int (0);
1112 if (TREE_CODE (evolution) == INTEGER_CST)
1113 step = fold_convert (ssizetype, evolution);
1115 if (dump_file && (dump_flags & TDF_DETAILS))
1116 fprintf (dump_file, "\nnon constant step for ptr access.\n");
1120 if (dump_file && (dump_flags & TDF_DETAILS))
1121 fprintf (dump_file, "\nunknown evolution of ptr.\n");
1123 return init_pointer_ref (stmt, ref, access_fn, is_read, base_address,
1127 /* Function strip_conversions
1129 Strip conversions that don't narrow the mode. */
1132 strip_conversion (tree expr)
1134 tree to, ti, oprnd0;
1136 while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
1138 to = TREE_TYPE (expr);
1139 oprnd0 = TREE_OPERAND (expr, 0);
1140 ti = TREE_TYPE (oprnd0);
1142 if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti))
1144 if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti)))
1153 /* Function analyze_offset_expr
1155 Given an offset expression EXPR received from get_inner_reference, analyze
1156 it and create an expression for INITIAL_OFFSET by substituting the variables
1157 of EXPR with initial_condition of the corresponding access_fn in the loop.
1160 for (j = 3; j < N; j++)
1163 For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be
1164 substituted, since its access_fn in the inner loop is i. 'j' will be
1165 substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
1168 Compute MISALIGN (the misalignment of the data reference initial access from
1169 its base). Misalignment can be calculated only if all the variables can be
1170 substituted with constants, otherwise, we record maximum possible alignment
1171 in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN
1172 will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be
1173 recorded in ALIGNED_TO.
1175 STEP is an evolution of the data reference in this loop in bytes.
1176 In the above example, STEP is C_j.
1178 Return FALSE, if the analysis fails, e.g., there is no access_fn for a
1179 variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO
1180 and STEP) are NULL_TREEs. Otherwise, return TRUE.
1185 analyze_offset_expr (tree expr,
1187 tree *initial_offset,
1194 tree left_offset = ssize_int (0);
1195 tree right_offset = ssize_int (0);
1196 tree left_misalign = ssize_int (0);
1197 tree right_misalign = ssize_int (0);
1198 tree left_step = ssize_int (0);
1199 tree right_step = ssize_int (0);
1200 enum tree_code code;
1201 tree init, evolution;
1202 tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE;
1205 *misalign = NULL_TREE;
1206 *aligned_to = NULL_TREE;
1207 *initial_offset = NULL_TREE;
1209 /* Strip conversions that don't narrow the mode. */
1210 expr = strip_conversion (expr);
1216 if (TREE_CODE (expr) == INTEGER_CST)
1218 *initial_offset = fold_convert (ssizetype, expr);
1219 *misalign = fold_convert (ssizetype, expr);
1220 *step = ssize_int (0);
1224 /* 2. Variable. Try to substitute with initial_condition of the corresponding
1225 access_fn in the current loop. */
1226 if (SSA_VAR_P (expr))
1228 tree access_fn = analyze_scalar_evolution (loop, expr);
1230 if (access_fn == chrec_dont_know)
1234 init = initial_condition_in_loop_num (access_fn, loop->num);
1235 if (!expr_invariant_in_loop_p (loop, init))
1236 /* Not enough information: may be not loop invariant.
1237 E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
1238 initial_condition is D, but it depends on i - loop's induction
1242 evolution = evolution_part_in_loop_num (access_fn, loop->num);
1243 if (evolution && TREE_CODE (evolution) != INTEGER_CST)
1244 /* Evolution is not constant. */
1247 if (TREE_CODE (init) == INTEGER_CST)
1248 *misalign = fold_convert (ssizetype, init);
1250 /* Not constant, misalignment cannot be calculated. */
1251 *misalign = NULL_TREE;
1253 *initial_offset = fold_convert (ssizetype, init);
1255 *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
1259 /* Recursive computation. */
1260 if (!BINARY_CLASS_P (expr))
1262 /* We expect to get binary expressions (PLUS/MINUS and MULT). */
1263 if (dump_file && (dump_flags & TDF_DETAILS))
1265 fprintf (dump_file, "\nNot binary expression ");
1266 print_generic_expr (dump_file, expr, TDF_SLIM);
1267 fprintf (dump_file, "\n");
1271 oprnd0 = TREE_OPERAND (expr, 0);
1272 oprnd1 = TREE_OPERAND (expr, 1);
1274 if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign,
1275 &left_aligned_to, &left_step)
1276 || !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign,
1277 &right_aligned_to, &right_step))
1280 /* The type of the operation: plus, minus or mult. */
1281 code = TREE_CODE (expr);
1285 if (TREE_CODE (right_offset) != INTEGER_CST)
1286 /* RIGHT_OFFSET can be not constant. For example, for arrays of variable
1288 FORNOW: We don't support such cases. */
1291 /* Strip conversions that don't narrow the mode. */
1292 left_offset = strip_conversion (left_offset);
1295 /* Misalignment computation. */
1296 if (SSA_VAR_P (left_offset))
1298 /* If the left side contains variables that can't be substituted with
1299 constants, the misalignment is unknown. However, if the right side
1300 is a multiple of some alignment, we know that the expression is
1301 aligned to it. Therefore, we record such maximum possible value.
1303 *misalign = NULL_TREE;
1304 *aligned_to = ssize_int (highest_pow2_factor (right_offset));
1308 /* The left operand was successfully substituted with constant. */
1311 /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is
1313 *misalign = size_binop (code, left_misalign, right_misalign);
1314 if (left_aligned_to && right_aligned_to)
1315 *aligned_to = size_binop (MIN_EXPR, left_aligned_to,
1318 *aligned_to = left_aligned_to ?
1319 left_aligned_to : right_aligned_to;
1322 *misalign = NULL_TREE;
1325 /* Step calculation. */
1326 /* Multiply the step by the right operand. */
1327 *step = size_binop (MULT_EXPR, left_step, right_offset);
1332 /* Combine the recursive calculations for step and misalignment. */
1333 *step = size_binop (code, left_step, right_step);
1335 /* Unknown alignment. */
1336 if ((!left_misalign && !left_aligned_to)
1337 || (!right_misalign && !right_aligned_to))
1339 *misalign = NULL_TREE;
1340 *aligned_to = NULL_TREE;
1344 if (left_misalign && right_misalign)
1345 *misalign = size_binop (code, left_misalign, right_misalign);
1347 *misalign = left_misalign ? left_misalign : right_misalign;
1349 if (left_aligned_to && right_aligned_to)
1350 *aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to);
1352 *aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to;
1360 /* Compute offset. */
1361 *initial_offset = fold_convert (ssizetype,
1362 fold_build2 (code, TREE_TYPE (left_offset),
1368 /* Function address_analysis
1370 Return the BASE of the address expression EXPR.
1371 Also compute the OFFSET from BASE, MISALIGN and STEP.
1374 EXPR - the address expression that is being analyzed
1375 STMT - the statement that contains EXPR or its original memory reference
1376 IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
1377 DR - data_reference struct for the original memory reference
1380 BASE (returned value) - the base of the data reference EXPR.
1381 INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
1382 MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
1383 computation is impossible
1384 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1385 calculated (doesn't depend on variables)
1386 STEP - evolution of EXPR in the loop
1388 If something unexpected is encountered (an unsupported form of data-ref),
1389 then NULL_TREE is returned.
1393 address_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr,
1394 tree *offset, tree *misalign, tree *aligned_to, tree *step)
1396 tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
1397 tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1398 tree dummy, address_aligned_to = NULL_TREE;
1399 struct ptr_info_def *dummy1;
1402 switch (TREE_CODE (expr))
1406 /* EXPR is of form {base +/- offset} (or {offset +/- base}). */
1407 oprnd0 = TREE_OPERAND (expr, 0);
1408 oprnd1 = TREE_OPERAND (expr, 1);
1410 STRIP_NOPS (oprnd0);
1411 STRIP_NOPS (oprnd1);
1413 /* Recursively try to find the base of the address contained in EXPR.
1414 For offset, the returned base will be NULL. */
1415 base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset,
1416 &address_misalign, &address_aligned_to,
1419 base_addr1 = address_analysis (oprnd1, stmt, is_read, dr, &address_offset,
1420 &address_misalign, &address_aligned_to,
1423 /* We support cases where only one of the operands contains an
1425 if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
1427 if (dump_file && (dump_flags & TDF_DETAILS))
1430 "\neither more than one address or no addresses in expr ");
1431 print_generic_expr (dump_file, expr, TDF_SLIM);
1432 fprintf (dump_file, "\n");
1437 /* To revert STRIP_NOPS. */
1438 oprnd0 = TREE_OPERAND (expr, 0);
1439 oprnd1 = TREE_OPERAND (expr, 1);
1441 offset_expr = base_addr0 ?
1442 fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
1444 /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is
1445 a number, we can add it to the misalignment value calculated for base,
1446 otherwise, misalignment is NULL. */
1447 if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
1449 *misalign = size_binop (TREE_CODE (expr), address_misalign,
1451 *aligned_to = address_aligned_to;
1455 *misalign = NULL_TREE;
1456 *aligned_to = NULL_TREE;
1459 /* Combine offset (from EXPR {base + offset}) with the offset calculated
1461 *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
1462 return base_addr0 ? base_addr0 : base_addr1;
1465 base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read,
1466 &dr, offset, misalign, aligned_to, step,
1467 &dummy, &dummy1, &dummy2);
1468 return base_address;
1471 if (!POINTER_TYPE_P (TREE_TYPE (expr)))
1473 if (dump_file && (dump_flags & TDF_DETAILS))
1475 fprintf (dump_file, "\nnot pointer SSA_NAME ");
1476 print_generic_expr (dump_file, expr, TDF_SLIM);
1477 fprintf (dump_file, "\n");
1481 *aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr))));
1482 *misalign = ssize_int (0);
1483 *offset = ssize_int (0);
1484 *step = ssize_int (0);
1493 /* Function object_analysis
1495 Create a data-reference structure DR for MEMREF.
1496 Return the BASE of the data reference MEMREF if the analysis is possible.
1497 Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1498 E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset
1499 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET
1500 instantiated with initial_conditions of access_functions of variables,
1501 and STEP is the evolution of the DR_REF in this loop.
1503 Function get_inner_reference is used for the above in case of ARRAY_REF and
1506 The structure of the function is as follows:
1508 Case 1. For handled_component_p refs
1509 1.1 build data-reference structure for MEMREF
1510 1.2 call get_inner_reference
1511 1.2.1 analyze offset expr received from get_inner_reference
1512 (fall through with BASE)
1513 Case 2. For declarations
1515 Case 3. For INDIRECT_REFs
1516 3.1 build data-reference structure for MEMREF
1517 3.2 analyze evolution and initial condition of MEMREF
1518 3.3 set data-reference structure for MEMREF
1519 3.4 call address_analysis to analyze INIT of the access function
1520 3.5 extract memory tag
1523 Combine the results of object and address analysis to calculate
1524 INITIAL_OFFSET, STEP and misalignment info.
1527 MEMREF - the memory reference that is being analyzed
1528 STMT - the statement that contains MEMREF
1529 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1532 BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
1533 E.g, if MEMREF is a.b[k].c[i][j] the returned
1535 DR - data_reference struct for MEMREF
1536 INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
1537 MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of
1538 ALIGNMENT or NULL_TREE if the computation is impossible
1539 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1540 calculated (doesn't depend on variables)
1541 STEP - evolution of the DR_REF in the loop
1542 MEMTAG - memory tag for aliasing purposes
1543 PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
1544 SUBVARS - Sub-variables of the variable
1546 If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned,
1547 but DR can be created anyway.
1552 object_analysis (tree memref, tree stmt, bool is_read,
1553 struct data_reference **dr, tree *offset, tree *misalign,
1554 tree *aligned_to, tree *step, tree *memtag,
1555 struct ptr_info_def **ptr_info, subvar_t *subvars)
1557 tree base = NULL_TREE, base_address = NULL_TREE;
1558 tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
1559 tree object_step = ssize_int (0), address_step = ssize_int (0);
1560 tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1561 HOST_WIDE_INT pbitsize, pbitpos;
1562 tree poffset, bit_pos_in_bytes;
1563 enum machine_mode pmode;
1564 int punsignedp, pvolatilep;
1565 tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
1566 struct loop *loop = loop_containing_stmt (stmt);
1567 struct data_reference *ptr_dr = NULL;
1568 tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE;
1569 tree comp_ref = NULL_TREE;
1574 /* Case 1. handled_component_p refs. */
1575 if (handled_component_p (memref))
1577 /* 1.1 build data-reference structure for MEMREF. */
1580 if (TREE_CODE (memref) == ARRAY_REF)
1581 *dr = init_array_ref (stmt, memref, is_read);
1582 else if (TREE_CODE (memref) == COMPONENT_REF)
1586 if (dump_file && (dump_flags & TDF_DETAILS))
1588 fprintf (dump_file, "\ndata-ref of unsupported type ");
1589 print_generic_expr (dump_file, memref, TDF_SLIM);
1590 fprintf (dump_file, "\n");
1596 /* 1.2 call get_inner_reference. */
1597 /* Find the base and the offset from it. */
1598 base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
1599 &pmode, &punsignedp, &pvolatilep, false);
1602 if (dump_file && (dump_flags & TDF_DETAILS))
1604 fprintf (dump_file, "\nfailed to get inner ref for ");
1605 print_generic_expr (dump_file, memref, TDF_SLIM);
1606 fprintf (dump_file, "\n");
1611 /* 1.2.1 analyze offset expr received from get_inner_reference. */
1613 && !analyze_offset_expr (poffset, loop, &object_offset,
1614 &object_misalign, &object_aligned_to,
1617 if (dump_file && (dump_flags & TDF_DETAILS))
1619 fprintf (dump_file, "\nfailed to compute offset or step for ");
1620 print_generic_expr (dump_file, memref, TDF_SLIM);
1621 fprintf (dump_file, "\n");
1626 /* Add bit position to OFFSET and MISALIGN. */
1628 bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
1629 /* Check that there is no remainder in bits. */
1630 if (pbitpos%BITS_PER_UNIT)
1632 if (dump_file && (dump_flags & TDF_DETAILS))
1633 fprintf (dump_file, "\nbit offset alignment.\n");
1636 object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);
1637 if (object_misalign)
1638 object_misalign = size_binop (PLUS_EXPR, object_misalign,
1641 memref = base; /* To continue analysis of BASE. */
1645 /* Part 1: Case 2. Declarations. */
1646 if (DECL_P (memref))
1648 /* We expect to get a decl only if we already have a DR, or with
1649 COMPONENT_REFs of type 'a[i].b'. */
1652 if (comp_ref && TREE_CODE (TREE_OPERAND (comp_ref, 0)) == ARRAY_REF)
1654 *dr = init_array_ref (stmt, TREE_OPERAND (comp_ref, 0), is_read);
1655 if (DR_NUM_DIMENSIONS (*dr) != 1)
1657 if (dump_file && (dump_flags & TDF_DETAILS))
1659 fprintf (dump_file, "\n multidimensional component ref ");
1660 print_generic_expr (dump_file, comp_ref, TDF_SLIM);
1661 fprintf (dump_file, "\n");
1668 if (dump_file && (dump_flags & TDF_DETAILS))
1670 fprintf (dump_file, "\nunhandled decl ");
1671 print_generic_expr (dump_file, memref, TDF_SLIM);
1672 fprintf (dump_file, "\n");
1678 /* TODO: if during the analysis of INDIRECT_REF we get to an object, put
1679 the object in BASE_OBJECT field if we can prove that this is O.K.,
1680 i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT.
1681 (e.g., if the object is an array base 'a', where 'a[N]', we must prove
1682 that every access with 'p' (the original INDIRECT_REF based on '&a')
1683 in the loop is within the array boundaries - from a[0] to a[N-1]).
1684 Otherwise, our alias analysis can be incorrect.
1685 Even if an access function based on BASE_OBJECT can't be build, update
1686 BASE_OBJECT field to enable us to prove that two data-refs are
1687 different (without access function, distance analysis is impossible).
1689 if (SSA_VAR_P (memref) && var_can_have_subvars (memref))
1690 *subvars = get_subvars_for_var (memref);
1691 base_address = build_fold_addr_expr (memref);
1692 /* 2.1 set MEMTAG. */
1696 /* Part 1: Case 3. INDIRECT_REFs. */
1697 else if (TREE_CODE (memref) == INDIRECT_REF)
1699 tree ptr_ref = TREE_OPERAND (memref, 0);
1700 if (TREE_CODE (ptr_ref) == SSA_NAME)
1701 *ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
1703 /* 3.1 build data-reference structure for MEMREF. */
1704 ptr_dr = analyze_indirect_ref (stmt, memref, is_read);
1707 if (dump_file && (dump_flags & TDF_DETAILS))
1709 fprintf (dump_file, "\nfailed to create dr for ");
1710 print_generic_expr (dump_file, memref, TDF_SLIM);
1711 fprintf (dump_file, "\n");
1716 /* 3.2 analyze evolution and initial condition of MEMREF. */
1717 ptr_step = DR_STEP (ptr_dr);
1718 ptr_init = DR_BASE_ADDRESS (ptr_dr);
1719 if (!ptr_init || !ptr_step || !POINTER_TYPE_P (TREE_TYPE (ptr_init)))
1721 *dr = (*dr) ? *dr : ptr_dr;
1722 if (dump_file && (dump_flags & TDF_DETAILS))
1724 fprintf (dump_file, "\nbad pointer access ");
1725 print_generic_expr (dump_file, memref, TDF_SLIM);
1726 fprintf (dump_file, "\n");
1731 if (integer_zerop (ptr_step) && !(*dr))
1733 if (dump_file && (dump_flags & TDF_DETAILS))
1734 fprintf (dump_file, "\nptr is loop invariant.\n");
1738 /* If there exists DR for MEMREF, we are analyzing the base of
1739 handled component (PTR_INIT), which not necessary has evolution in
1742 object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
1744 /* 3.3 set data-reference structure for MEMREF. */
1748 /* 3.4 call address_analysis to analyze INIT of the access
1750 base_address = address_analysis (ptr_init, stmt, is_read, *dr,
1751 &address_offset, &address_misalign,
1752 &address_aligned_to, &address_step);
1755 if (dump_file && (dump_flags & TDF_DETAILS))
1757 fprintf (dump_file, "\nfailed to analyze address ");
1758 print_generic_expr (dump_file, ptr_init, TDF_SLIM);
1759 fprintf (dump_file, "\n");
1764 /* 3.5 extract memory tag. */
1765 switch (TREE_CODE (base_address))
1768 *memtag = symbol_mem_tag (SSA_NAME_VAR (base_address));
1769 if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
1770 *memtag = symbol_mem_tag (SSA_NAME_VAR (TREE_OPERAND (memref, 0)));
1773 *memtag = TREE_OPERAND (base_address, 0);
1776 if (dump_file && (dump_flags & TDF_DETAILS))
1778 fprintf (dump_file, "\nno memtag for ");
1779 print_generic_expr (dump_file, memref, TDF_SLIM);
1780 fprintf (dump_file, "\n");
1782 *memtag = NULL_TREE;
1789 /* MEMREF cannot be analyzed. */
1790 if (dump_file && (dump_flags & TDF_DETAILS))
1792 fprintf (dump_file, "\ndata-ref of unsupported type ");
1793 print_generic_expr (dump_file, memref, TDF_SLIM);
1794 fprintf (dump_file, "\n");
1800 DR_REF (*dr) = comp_ref;
1802 if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag))
1803 *subvars = get_subvars_for_var (*memtag);
1805 /* Part 2: Combine the results of object and address analysis to calculate
1806 INITIAL_OFFSET, STEP and misalignment info. */
1807 *offset = size_binop (PLUS_EXPR, object_offset, address_offset);
1809 if ((!object_misalign && !object_aligned_to)
1810 || (!address_misalign && !address_aligned_to))
1812 *misalign = NULL_TREE;
1813 *aligned_to = NULL_TREE;
1817 if (object_misalign && address_misalign)
1818 *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
1820 *misalign = object_misalign ? object_misalign : address_misalign;
1821 if (object_aligned_to && address_aligned_to)
1822 *aligned_to = size_binop (MIN_EXPR, object_aligned_to,
1823 address_aligned_to);
1825 *aligned_to = object_aligned_to ?
1826 object_aligned_to : address_aligned_to;
1828 *step = size_binop (PLUS_EXPR, object_step, address_step);
1830 return base_address;
1833 /* Function analyze_offset.
1835 Extract INVARIANT and CONSTANT parts from OFFSET.
1839 analyze_offset (tree offset, tree *invariant, tree *constant)
1841 tree op0, op1, constant_0, constant_1, invariant_0, invariant_1;
1842 enum tree_code code = TREE_CODE (offset);
1844 *invariant = NULL_TREE;
1845 *constant = NULL_TREE;
1847 /* Not PLUS/MINUS expression - recursion stop condition. */
1848 if (code != PLUS_EXPR && code != MINUS_EXPR)
1850 if (TREE_CODE (offset) == INTEGER_CST)
1853 *invariant = offset;
1857 op0 = TREE_OPERAND (offset, 0);
1858 op1 = TREE_OPERAND (offset, 1);
1860 /* Recursive call with the operands. */
1861 if (!analyze_offset (op0, &invariant_0, &constant_0)
1862 || !analyze_offset (op1, &invariant_1, &constant_1))
1865 /* Combine the results. Add negation to the subtrahend in case of
1867 if (constant_0 && constant_1)
1869 *constant = constant_0 ? constant_0 : constant_1;
1870 if (code == MINUS_EXPR && constant_1)
1871 *constant = fold_build1 (NEGATE_EXPR, TREE_TYPE (*constant), *constant);
1873 if (invariant_0 && invariant_1)
1875 fold_build2 (code, TREE_TYPE (invariant_0), invariant_0, invariant_1);
1878 *invariant = invariant_0 ? invariant_0 : invariant_1;
1879 if (code == MINUS_EXPR && invariant_1)
1881 fold_build1 (NEGATE_EXPR, TREE_TYPE (*invariant), *invariant);
1886 /* Free the memory used by the data reference DR. */
1889 free_data_ref (data_reference_p dr)
1891 DR_FREE_ACCESS_FNS (dr);
1895 /* Function create_data_ref.
1897 Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS,
1898 DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO,
1899 DR_MEMTAG, and DR_POINTSTO_INFO fields.
1902 MEMREF - the memory reference that is being analyzed
1903 STMT - the statement that contains MEMREF
1904 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1907 DR (returned value) - data_reference struct for MEMREF
1910 static struct data_reference *
1911 create_data_ref (tree memref, tree stmt, bool is_read)
1913 struct data_reference *dr = NULL;
1914 tree base_address, offset, step, misalign, memtag;
1915 struct loop *loop = loop_containing_stmt (stmt);
1916 tree invariant = NULL_TREE, constant = NULL_TREE;
1917 tree type_size, init_cond;
1918 struct ptr_info_def *ptr_info;
1919 subvar_t subvars = NULL;
1920 tree aligned_to, type = NULL_TREE, orig_offset;
1925 base_address = object_analysis (memref, stmt, is_read, &dr, &offset,
1926 &misalign, &aligned_to, &step, &memtag,
1927 &ptr_info, &subvars);
1928 if (!dr || !base_address)
1930 if (dump_file && (dump_flags & TDF_DETAILS))
1932 fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for ");
1933 print_generic_expr (dump_file, memref, TDF_SLIM);
1934 fprintf (dump_file, "\n");
1939 DR_BASE_ADDRESS (dr) = base_address;
1940 DR_OFFSET (dr) = offset;
1941 DR_INIT (dr) = ssize_int (0);
1942 DR_STEP (dr) = step;
1943 DR_OFFSET_MISALIGNMENT (dr) = misalign;
1944 DR_ALIGNED_TO (dr) = aligned_to;
1945 DR_MEMTAG (dr) = memtag;
1946 DR_PTR_INFO (dr) = ptr_info;
1947 DR_SUBVARS (dr) = subvars;
1949 type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
1951 /* Extract CONSTANT and INVARIANT from OFFSET. */
1952 /* Remove cast from OFFSET and restore it for INVARIANT part. */
1953 orig_offset = offset;
1954 STRIP_NOPS (offset);
1955 if (offset != orig_offset)
1956 type = TREE_TYPE (orig_offset);
1957 if (!analyze_offset (offset, &invariant, &constant))
1959 if (dump_file && (dump_flags & TDF_DETAILS))
1961 fprintf (dump_file, "\ncreate_data_ref: failed to analyze dr's");
1962 fprintf (dump_file, " offset for ");
1963 print_generic_expr (dump_file, memref, TDF_SLIM);
1964 fprintf (dump_file, "\n");
1968 if (type && invariant)
1969 invariant = fold_convert (type, invariant);
1971 /* Put CONSTANT part of OFFSET in DR_INIT and INVARIANT in DR_OFFSET field
1975 DR_INIT (dr) = fold_convert (ssizetype, constant);
1976 init_cond = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (constant),
1977 constant, type_size);
1980 DR_INIT (dr) = init_cond = ssize_int (0);
1983 DR_OFFSET (dr) = invariant;
1985 DR_OFFSET (dr) = ssize_int (0);
1987 /* Change the access function for INIDIRECT_REFs, according to
1988 DR_BASE_ADDRESS. Analyze OFFSET calculated in object_analysis. OFFSET is
1989 an expression that can contain loop invariant expressions and constants.
1990 We put the constant part in the initial condition of the access function
1991 (for data dependence tests), and in DR_INIT of the data-ref. The loop
1992 invariant part is put in DR_OFFSET.
1993 The evolution part of the access function is STEP calculated in
1994 object_analysis divided by the size of data type.
1996 if (!DR_BASE_OBJECT (dr)
1997 || (TREE_CODE (memref) == COMPONENT_REF && DR_NUM_DIMENSIONS (dr) == 1))
2002 /* Update access function. */
2003 access_fn = DR_ACCESS_FN (dr, 0);
2004 if (automatically_generated_chrec_p (access_fn))
2010 new_step = size_binop (TRUNC_DIV_EXPR,
2011 fold_convert (ssizetype, step), type_size);
2013 init_cond = chrec_convert (chrec_type (access_fn), init_cond, stmt);
2014 new_step = chrec_convert (chrec_type (access_fn), new_step, stmt);
2015 if (automatically_generated_chrec_p (init_cond)
2016 || automatically_generated_chrec_p (new_step))
2021 access_fn = chrec_replace_initial_condition (access_fn, init_cond);
2022 access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step);
2024 VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn);
2027 if (dump_file && (dump_flags & TDF_DETAILS))
2029 struct ptr_info_def *pi = DR_PTR_INFO (dr);
2031 fprintf (dump_file, "\nCreated dr for ");
2032 print_generic_expr (dump_file, memref, TDF_SLIM);
2033 fprintf (dump_file, "\n\tbase_address: ");
2034 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
2035 fprintf (dump_file, "\n\toffset from base address: ");
2036 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
2037 fprintf (dump_file, "\n\tconstant offset from base address: ");
2038 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
2039 fprintf (dump_file, "\n\tbase_object: ");
2040 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
2041 fprintf (dump_file, "\n\tstep: ");
2042 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
2043 fprintf (dump_file, "B\n\tmisalignment from base: ");
2044 print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM);
2045 if (DR_OFFSET_MISALIGNMENT (dr))
2046 fprintf (dump_file, "B");
2047 if (DR_ALIGNED_TO (dr))
2049 fprintf (dump_file, "\n\taligned to: ");
2050 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
2052 fprintf (dump_file, "\n\tmemtag: ");
2053 print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM);
2054 fprintf (dump_file, "\n");
2055 if (pi && pi->name_mem_tag)
2057 fprintf (dump_file, "\n\tnametag: ");
2058 print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM);
2059 fprintf (dump_file, "\n");
2065 /* Returns true if FNA == FNB. */
2068 affine_function_equal_p (affine_fn fna, affine_fn fnb)
2070 unsigned i, n = VEC_length (tree, fna);
2072 gcc_assert (n == VEC_length (tree, fnb));
2074 for (i = 0; i < n; i++)
2075 if (!operand_equal_p (VEC_index (tree, fna, i),
2076 VEC_index (tree, fnb, i), 0))
2082 /* If all the functions in CF are the same, returns one of them,
2083 otherwise returns NULL. */
2086 common_affine_function (conflict_function *cf)
2091 if (!CF_NONTRIVIAL_P (cf))
2096 for (i = 1; i < cf->n; i++)
2097 if (!affine_function_equal_p (comm, cf->fns[i]))
2103 /* Returns the base of the affine function FN. */
2106 affine_function_base (affine_fn fn)
2108 return VEC_index (tree, fn, 0);
2111 /* Returns true if FN is a constant. */
2114 affine_function_constant_p (affine_fn fn)
2119 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
2120 if (!integer_zerop (coef))
2126 /* Applies operation OP on affine functions FNA and FNB, and returns the
2130 affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
2136 if (VEC_length (tree, fnb) > VEC_length (tree, fna))
2138 n = VEC_length (tree, fna);
2139 m = VEC_length (tree, fnb);
2143 n = VEC_length (tree, fnb);
2144 m = VEC_length (tree, fna);
2147 ret = VEC_alloc (tree, heap, m);
2148 for (i = 0; i < n; i++)
2149 VEC_quick_push (tree, ret,
2150 fold_build2 (op, integer_type_node,
2151 VEC_index (tree, fna, i),
2152 VEC_index (tree, fnb, i)));
2154 for (; VEC_iterate (tree, fna, i, coef); i++)
2155 VEC_quick_push (tree, ret,
2156 fold_build2 (op, integer_type_node,
2157 coef, integer_zero_node));
2158 for (; VEC_iterate (tree, fnb, i, coef); i++)
2159 VEC_quick_push (tree, ret,
2160 fold_build2 (op, integer_type_node,
2161 integer_zero_node, coef));
2166 /* Returns the sum of affine functions FNA and FNB. */
2169 affine_fn_plus (affine_fn fna, affine_fn fnb)
2171 return affine_fn_op (PLUS_EXPR, fna, fnb);
2174 /* Returns the difference of affine functions FNA and FNB. */
2177 affine_fn_minus (affine_fn fna, affine_fn fnb)
2179 return affine_fn_op (MINUS_EXPR, fna, fnb);
2182 /* Frees affine function FN. */
2185 affine_fn_free (affine_fn fn)
2187 VEC_free (tree, heap, fn);
2190 /* Determine for each subscript in the data dependence relation DDR
2194 compute_subscript_distance (struct data_dependence_relation *ddr)
2196 conflict_function *cf_a, *cf_b;
2197 affine_fn fn_a, fn_b, diff;
2199 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
2203 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2205 struct subscript *subscript;
2207 subscript = DDR_SUBSCRIPT (ddr, i);
2208 cf_a = SUB_CONFLICTS_IN_A (subscript);
2209 cf_b = SUB_CONFLICTS_IN_B (subscript);
2211 fn_a = common_affine_function (cf_a);
2212 fn_b = common_affine_function (cf_b);
2215 SUB_DISTANCE (subscript) = chrec_dont_know;
2218 diff = affine_fn_minus (fn_a, fn_b);
2220 if (affine_function_constant_p (diff))
2221 SUB_DISTANCE (subscript) = affine_function_base (diff);
2223 SUB_DISTANCE (subscript) = chrec_dont_know;
2225 affine_fn_free (diff);
2230 /* Returns the conflict function for "unknown". */
2232 static conflict_function *
2233 conflict_fn_not_known (void)
2235 conflict_function *fn = XCNEW (conflict_function);
2241 /* Returns the conflict function for "independent". */
2243 static conflict_function *
2244 conflict_fn_no_dependence (void)
2246 conflict_function *fn = XCNEW (conflict_function);
2247 fn->n = NO_DEPENDENCE;
2252 /* Initialize a data dependence relation between data accesses A and
2253 B. NB_LOOPS is the number of loops surrounding the references: the
2254 size of the classic distance/direction vectors. */
2256 static struct data_dependence_relation *
2257 initialize_data_dependence_relation (struct data_reference *a,
2258 struct data_reference *b,
2259 VEC (loop_p, heap) *loop_nest)
2261 struct data_dependence_relation *res;
2262 bool differ_p, known_dependence;
2265 res = XNEW (struct data_dependence_relation);
2268 DDR_LOOP_NEST (res) = NULL;
2270 if (a == NULL || b == NULL)
2272 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
2276 /* When A and B are arrays and their dimensions differ, we directly
2277 initialize the relation to "there is no dependence": chrec_known. */
2278 if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
2279 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
2281 DDR_ARE_DEPENDENT (res) = chrec_known;
2285 if (DR_BASE_ADDRESS (a) && DR_BASE_ADDRESS (b))
2286 known_dependence = base_addr_differ_p (a, b, &differ_p);
2288 known_dependence = base_object_differ_p (a, b, &differ_p);
2290 if (!known_dependence)
2292 /* Can't determine whether the data-refs access the same memory
2294 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
2300 DDR_ARE_DEPENDENT (res) = chrec_known;
2304 DDR_AFFINE_P (res) = true;
2305 DDR_ARE_DEPENDENT (res) = NULL_TREE;
2306 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
2307 DDR_LOOP_NEST (res) = loop_nest;
2308 DDR_INNER_LOOP (res) = 0;
2309 DDR_DIR_VECTS (res) = NULL;
2310 DDR_DIST_VECTS (res) = NULL;
2312 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
2314 struct subscript *subscript;
2316 subscript = XNEW (struct subscript);
2317 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
2318 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
2319 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
2320 SUB_DISTANCE (subscript) = chrec_dont_know;
2321 VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
2327 /* Frees memory used by the conflict function F. */
2330 free_conflict_function (conflict_function *f)
2334 if (CF_NONTRIVIAL_P (f))
2336 for (i = 0; i < f->n; i++)
2337 affine_fn_free (f->fns[i]);
2342 /* Frees memory used by SUBSCRIPTS. */
2345 free_subscripts (VEC (subscript_p, heap) *subscripts)
2350 for (i = 0; VEC_iterate (subscript_p, subscripts, i, s); i++)
2352 free_conflict_function (s->conflicting_iterations_in_a);
2353 free_conflict_function (s->conflicting_iterations_in_b);
2355 VEC_free (subscript_p, heap, subscripts);
2358 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
2362 finalize_ddr_dependent (struct data_dependence_relation *ddr,
2365 if (dump_file && (dump_flags & TDF_DETAILS))
2367 fprintf (dump_file, "(dependence classified: ");
2368 print_generic_expr (dump_file, chrec, 0);
2369 fprintf (dump_file, ")\n");
2372 DDR_ARE_DEPENDENT (ddr) = chrec;
2373 free_subscripts (DDR_SUBSCRIPTS (ddr));
2376 /* The dependence relation DDR cannot be represented by a distance
2380 non_affine_dependence_relation (struct data_dependence_relation *ddr)
2382 if (dump_file && (dump_flags & TDF_DETAILS))
2383 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
2385 DDR_AFFINE_P (ddr) = false;
2390 /* This section contains the classic Banerjee tests. */
2392 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
2393 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
2396 ziv_subscript_p (tree chrec_a,
2399 return (evolution_function_is_constant_p (chrec_a)
2400 && evolution_function_is_constant_p (chrec_b));
2403 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
2404 variable, i.e., if the SIV (Single Index Variable) test is true. */
2407 siv_subscript_p (tree chrec_a,
2410 if ((evolution_function_is_constant_p (chrec_a)
2411 && evolution_function_is_univariate_p (chrec_b))
2412 || (evolution_function_is_constant_p (chrec_b)
2413 && evolution_function_is_univariate_p (chrec_a)))
2416 if (evolution_function_is_univariate_p (chrec_a)
2417 && evolution_function_is_univariate_p (chrec_b))
2419 switch (TREE_CODE (chrec_a))
2421 case POLYNOMIAL_CHREC:
2422 switch (TREE_CODE (chrec_b))
2424 case POLYNOMIAL_CHREC:
2425 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
2440 /* Creates a conflict function with N dimensions. The affine functions
2441 in each dimension follow. */
2443 static conflict_function *
2444 conflict_fn (unsigned n, ...)
2447 conflict_function *ret = XCNEW (conflict_function);
2450 gcc_assert (0 < n && n <= MAX_DIM);
2454 for (i = 0; i < n; i++)
2455 ret->fns[i] = va_arg (ap, affine_fn);
2461 /* Returns constant affine function with value CST. */
2464 affine_fn_cst (tree cst)
2466 affine_fn fn = VEC_alloc (tree, heap, 1);
2467 VEC_quick_push (tree, fn, cst);
2471 /* Returns affine function with single variable, CST + COEF * x_DIM. */
2474 affine_fn_univar (tree cst, unsigned dim, tree coef)
2476 affine_fn fn = VEC_alloc (tree, heap, dim + 1);
2479 gcc_assert (dim > 0);
2480 VEC_quick_push (tree, fn, cst);
2481 for (i = 1; i < dim; i++)
2482 VEC_quick_push (tree, fn, integer_zero_node);
2483 VEC_quick_push (tree, fn, coef);
2487 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
2488 *OVERLAPS_B are initialized to the functions that describe the
2489 relation between the elements accessed twice by CHREC_A and
2490 CHREC_B. For k >= 0, the following property is verified:
2492 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2495 analyze_ziv_subscript (tree chrec_a,
2497 conflict_function **overlaps_a,
2498 conflict_function **overlaps_b,
2499 tree *last_conflicts)
2502 dependence_stats.num_ziv++;
2504 if (dump_file && (dump_flags & TDF_DETAILS))
2505 fprintf (dump_file, "(analyze_ziv_subscript \n");
2507 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
2508 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
2509 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2511 switch (TREE_CODE (difference))
2514 if (integer_zerop (difference))
2516 /* The difference is equal to zero: the accessed index
2517 overlaps for each iteration in the loop. */
2518 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2519 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2520 *last_conflicts = chrec_dont_know;
2521 dependence_stats.num_ziv_dependent++;
2525 /* The accesses do not overlap. */
2526 *overlaps_a = conflict_fn_no_dependence ();
2527 *overlaps_b = conflict_fn_no_dependence ();
2528 *last_conflicts = integer_zero_node;
2529 dependence_stats.num_ziv_independent++;
2534 /* We're not sure whether the indexes overlap. For the moment,
2535 conservatively answer "don't know". */
2536 if (dump_file && (dump_flags & TDF_DETAILS))
2537 fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
2539 *overlaps_a = conflict_fn_not_known ();
2540 *overlaps_b = conflict_fn_not_known ();
2541 *last_conflicts = chrec_dont_know;
2542 dependence_stats.num_ziv_unimplemented++;
2546 if (dump_file && (dump_flags & TDF_DETAILS))
2547 fprintf (dump_file, ")\n");
2550 /* Sets NIT to the estimated number of executions of the statements in
2551 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
2552 large as the number of iterations. If we have no reliable estimate,
2553 the function returns false, otherwise returns true. */
2556 estimated_loop_iterations (struct loop *loop, bool conservative,
2559 estimate_numbers_of_iterations_loop (loop);
2562 if (!loop->any_upper_bound)
2565 *nit = loop->nb_iterations_upper_bound;
2569 if (!loop->any_estimate)
2572 *nit = loop->nb_iterations_estimate;
2578 /* Similar to estimated_loop_iterations, but returns the estimate only
2579 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
2580 on the number of iterations of LOOP could not be derived, returns -1. */
2583 estimated_loop_iterations_int (struct loop *loop, bool conservative)
2586 HOST_WIDE_INT hwi_nit;
2588 if (!estimated_loop_iterations (loop, conservative, &nit))
2591 if (!double_int_fits_in_shwi_p (nit))
2593 hwi_nit = double_int_to_shwi (nit);
2595 return hwi_nit < 0 ? -1 : hwi_nit;
2598 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
2599 and only if it fits to the int type. If this is not the case, or the
2600 estimate on the number of iterations of LOOP could not be derived, returns
2604 estimated_loop_iterations_tree (struct loop *loop, bool conservative)
2609 if (!estimated_loop_iterations (loop, conservative, &nit))
2610 return chrec_dont_know;
2612 type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
2613 if (!double_int_fits_to_tree_p (type, nit))
2614 return chrec_dont_know;
2616 return double_int_to_tree (type, nit);
2619 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2620 constant, and CHREC_B is an affine function. *OVERLAPS_A and
2621 *OVERLAPS_B are initialized to the functions that describe the
2622 relation between the elements accessed twice by CHREC_A and
2623 CHREC_B. For k >= 0, the following property is verified:
2625 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2628 analyze_siv_subscript_cst_affine (tree chrec_a,
2630 conflict_function **overlaps_a,
2631 conflict_function **overlaps_b,
2632 tree *last_conflicts)
2634 bool value0, value1, value2;
2635 tree difference, tmp;
2637 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
2638 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
2639 difference = chrec_fold_minus
2640 (integer_type_node, initial_condition (chrec_b), chrec_a);
2642 if (!chrec_is_positive (initial_condition (difference), &value0))
2644 if (dump_file && (dump_flags & TDF_DETAILS))
2645 fprintf (dump_file, "siv test failed: chrec is not positive.\n");
2647 dependence_stats.num_siv_unimplemented++;
2648 *overlaps_a = conflict_fn_not_known ();
2649 *overlaps_b = conflict_fn_not_known ();
2650 *last_conflicts = chrec_dont_know;
2655 if (value0 == false)
2657 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
2659 if (dump_file && (dump_flags & TDF_DETAILS))
2660 fprintf (dump_file, "siv test failed: chrec not positive.\n");
2662 *overlaps_a = conflict_fn_not_known ();
2663 *overlaps_b = conflict_fn_not_known ();
2664 *last_conflicts = chrec_dont_know;
2665 dependence_stats.num_siv_unimplemented++;
2674 chrec_b = {10, +, 1}
2677 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2679 HOST_WIDE_INT numiter;
2680 struct loop *loop = get_chrec_loop (chrec_b);
2682 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2683 tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
2684 fold_build1 (ABS_EXPR,
2687 CHREC_RIGHT (chrec_b));
2688 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
2689 *last_conflicts = integer_one_node;
2692 /* Perform weak-zero siv test to see if overlap is
2693 outside the loop bounds. */
2694 numiter = estimated_loop_iterations_int (loop, true);
2697 && compare_tree_int (tmp, numiter) > 0)
2699 free_conflict_function (*overlaps_a);
2700 free_conflict_function (*overlaps_b);
2701 *overlaps_a = conflict_fn_no_dependence ();
2702 *overlaps_b = conflict_fn_no_dependence ();
2703 *last_conflicts = integer_zero_node;
2704 dependence_stats.num_siv_independent++;
2707 dependence_stats.num_siv_dependent++;
2711 /* When the step does not divide the difference, there are
2715 *overlaps_a = conflict_fn_no_dependence ();
2716 *overlaps_b = conflict_fn_no_dependence ();
2717 *last_conflicts = integer_zero_node;
2718 dependence_stats.num_siv_independent++;
2727 chrec_b = {10, +, -1}
2729 In this case, chrec_a will not overlap with chrec_b. */
2730 *overlaps_a = conflict_fn_no_dependence ();
2731 *overlaps_b = conflict_fn_no_dependence ();
2732 *last_conflicts = integer_zero_node;
2733 dependence_stats.num_siv_independent++;
2740 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
2742 if (dump_file && (dump_flags & TDF_DETAILS))
2743 fprintf (dump_file, "siv test failed: chrec not positive.\n");
2745 *overlaps_a = conflict_fn_not_known ();
2746 *overlaps_b = conflict_fn_not_known ();
2747 *last_conflicts = chrec_dont_know;
2748 dependence_stats.num_siv_unimplemented++;
2753 if (value2 == false)
2757 chrec_b = {10, +, -1}
2759 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2761 HOST_WIDE_INT numiter;
2762 struct loop *loop = get_chrec_loop (chrec_b);
2764 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2765 tmp = fold_build2 (EXACT_DIV_EXPR,
2766 integer_type_node, difference,
2767 CHREC_RIGHT (chrec_b));
2768 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
2769 *last_conflicts = integer_one_node;
2771 /* Perform weak-zero siv test to see if overlap is
2772 outside the loop bounds. */
2773 numiter = estimated_loop_iterations_int (loop, true);
2776 && compare_tree_int (tmp, numiter) > 0)
2778 free_conflict_function (*overlaps_a);
2779 free_conflict_function (*overlaps_b);
2780 *overlaps_a = conflict_fn_no_dependence ();
2781 *overlaps_b = conflict_fn_no_dependence ();
2782 *last_conflicts = integer_zero_node;
2783 dependence_stats.num_siv_independent++;
2786 dependence_stats.num_siv_dependent++;
2790 /* When the step does not divide the difference, there
2794 *overlaps_a = conflict_fn_no_dependence ();
2795 *overlaps_b = conflict_fn_no_dependence ();
2796 *last_conflicts = integer_zero_node;
2797 dependence_stats.num_siv_independent++;
2807 In this case, chrec_a will not overlap with chrec_b. */
2808 *overlaps_a = conflict_fn_no_dependence ();
2809 *overlaps_b = conflict_fn_no_dependence ();
2810 *last_conflicts = integer_zero_node;
2811 dependence_stats.num_siv_independent++;
2819 /* Helper recursive function for initializing the matrix A. Returns
2820 the initial value of CHREC. */
2823 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2827 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2828 return int_cst_value (chrec);
2830 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2831 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2834 #define FLOOR_DIV(x,y) ((x) / (y))
2836 /* Solves the special case of the Diophantine equation:
2837 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2839 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2840 number of iterations that loops X and Y run. The overlaps will be
2841 constructed as evolutions in dimension DIM. */
2844 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
2845 affine_fn *overlaps_a,
2846 affine_fn *overlaps_b,
2847 tree *last_conflicts, int dim)
2849 if (((step_a > 0 && step_b > 0)
2850 || (step_a < 0 && step_b < 0)))
2852 int step_overlaps_a, step_overlaps_b;
2853 int gcd_steps_a_b, last_conflict, tau2;
2855 gcd_steps_a_b = gcd (step_a, step_b);
2856 step_overlaps_a = step_b / gcd_steps_a_b;
2857 step_overlaps_b = step_a / gcd_steps_a_b;
2859 tau2 = FLOOR_DIV (niter, step_overlaps_a);
2860 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2861 last_conflict = tau2;
2863 *overlaps_a = affine_fn_univar (integer_zero_node, dim,
2864 build_int_cst (NULL_TREE,
2866 *overlaps_b = affine_fn_univar (integer_zero_node, dim,
2867 build_int_cst (NULL_TREE,
2869 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2874 *overlaps_a = affine_fn_cst (integer_zero_node);
2875 *overlaps_b = affine_fn_cst (integer_zero_node);
2876 *last_conflicts = integer_zero_node;
2880 /* Solves the special case of a Diophantine equation where CHREC_A is
2881 an affine bivariate function, and CHREC_B is an affine univariate
2882 function. For example,
2884 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2886 has the following overlapping functions:
2888 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2889 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2890 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2892 FORNOW: This is a specialized implementation for a case occurring in
2893 a common benchmark. Implement the general algorithm. */
2896 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2897 conflict_function **overlaps_a,
2898 conflict_function **overlaps_b,
2899 tree *last_conflicts)
2901 bool xz_p, yz_p, xyz_p;
2902 int step_x, step_y, step_z;
2903 HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
2904 affine_fn overlaps_a_xz, overlaps_b_xz;
2905 affine_fn overlaps_a_yz, overlaps_b_yz;
2906 affine_fn overlaps_a_xyz, overlaps_b_xyz;
2907 affine_fn ova1, ova2, ovb;
2908 tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
2910 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2911 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2912 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2914 niter_x = estimated_loop_iterations_int
2915 (get_chrec_loop (CHREC_LEFT (chrec_a)), true);
2916 niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), true);
2917 niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), true);
2919 if (niter_x < 0 || niter_y < 0 || niter_z < 0)
2921 if (dump_file && (dump_flags & TDF_DETAILS))
2922 fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
2924 *overlaps_a = conflict_fn_not_known ();
2925 *overlaps_b = conflict_fn_not_known ();
2926 *last_conflicts = chrec_dont_know;
2930 niter = MIN (niter_x, niter_z);
2931 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2934 &last_conflicts_xz, 1);
2935 niter = MIN (niter_y, niter_z);
2936 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2939 &last_conflicts_yz, 2);
2940 niter = MIN (niter_x, niter_z);
2941 niter = MIN (niter_y, niter);
2942 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2945 &last_conflicts_xyz, 3);
2947 xz_p = !integer_zerop (last_conflicts_xz);
2948 yz_p = !integer_zerop (last_conflicts_yz);
2949 xyz_p = !integer_zerop (last_conflicts_xyz);
2951 if (xz_p || yz_p || xyz_p)
2953 ova1 = affine_fn_cst (integer_zero_node);
2954 ova2 = affine_fn_cst (integer_zero_node);
2955 ovb = affine_fn_cst (integer_zero_node);
2958 affine_fn t0 = ova1;
2961 ova1 = affine_fn_plus (ova1, overlaps_a_xz);
2962 ovb = affine_fn_plus (ovb, overlaps_b_xz);
2963 affine_fn_free (t0);
2964 affine_fn_free (t2);
2965 *last_conflicts = last_conflicts_xz;
2969 affine_fn t0 = ova2;
2972 ova2 = affine_fn_plus (ova2, overlaps_a_yz);
2973 ovb = affine_fn_plus (ovb, overlaps_b_yz);
2974 affine_fn_free (t0);
2975 affine_fn_free (t2);
2976 *last_conflicts = last_conflicts_yz;
2980 affine_fn t0 = ova1;
2981 affine_fn t2 = ova2;
2984 ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
2985 ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
2986 ovb = affine_fn_plus (ovb, overlaps_b_xyz);
2987 affine_fn_free (t0);
2988 affine_fn_free (t2);
2989 affine_fn_free (t4);
2990 *last_conflicts = last_conflicts_xyz;
2992 *overlaps_a = conflict_fn (2, ova1, ova2);
2993 *overlaps_b = conflict_fn (1, ovb);
2997 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2998 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2999 *last_conflicts = integer_zero_node;
3002 affine_fn_free (overlaps_a_xz);
3003 affine_fn_free (overlaps_b_xz);
3004 affine_fn_free (overlaps_a_yz);
3005 affine_fn_free (overlaps_b_yz);
3006 affine_fn_free (overlaps_a_xyz);
3007 affine_fn_free (overlaps_b_xyz);
3010 /* Determines the overlapping elements due to accesses CHREC_A and
3011 CHREC_B, that are affine functions. This function cannot handle
3012 symbolic evolution functions, ie. when initial conditions are
3013 parameters, because it uses lambda matrices of integers. */
3016 analyze_subscript_affine_affine (tree chrec_a,
3018 conflict_function **overlaps_a,
3019 conflict_function **overlaps_b,
3020 tree *last_conflicts)
3022 unsigned nb_vars_a, nb_vars_b, dim;
3023 int init_a, init_b, gamma, gcd_alpha_beta;
3025 lambda_matrix A, U, S;
3027 if (eq_evolutions_p (chrec_a, chrec_b))
3029 /* The accessed index overlaps for each iteration in the
3031 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
3032 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
3033 *last_conflicts = chrec_dont_know;
3036 if (dump_file && (dump_flags & TDF_DETAILS))
3037 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
3039 /* For determining the initial intersection, we have to solve a
3040 Diophantine equation. This is the most time consuming part.
3042 For answering to the question: "Is there a dependence?" we have
3043 to prove that there exists a solution to the Diophantine
3044 equation, and that the solution is in the iteration domain,
3045 i.e. the solution is positive or zero, and that the solution
3046 happens before the upper bound loop.nb_iterations. Otherwise
3047 there is no dependence. This function outputs a description of
3048 the iterations that hold the intersections. */
3050 nb_vars_a = nb_vars_in_chrec (chrec_a);
3051 nb_vars_b = nb_vars_in_chrec (chrec_b);
3053 dim = nb_vars_a + nb_vars_b;
3054 U = lambda_matrix_new (dim, dim);
3055 A = lambda_matrix_new (dim, 1);
3056 S = lambda_matrix_new (dim, 1);
3058 init_a = initialize_matrix_A (A, chrec_a, 0, 1);
3059 init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
3060 gamma = init_b - init_a;
3062 /* Don't do all the hard work of solving the Diophantine equation
3063 when we already know the solution: for example,
3066 | gamma = 3 - 3 = 0.
3067 Then the first overlap occurs during the first iterations:
3068 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
3072 if (nb_vars_a == 1 && nb_vars_b == 1)
3075 HOST_WIDE_INT niter, niter_a, niter_b;
3078 niter_a = estimated_loop_iterations_int
3079 (get_chrec_loop (chrec_a), true);
3080 niter_b = estimated_loop_iterations_int
3081 (get_chrec_loop (chrec_b), true);
3082 if (niter_a < 0 || niter_b < 0)
3084 if (dump_file && (dump_flags & TDF_DETAILS))
3085 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
3086 *overlaps_a = conflict_fn_not_known ();
3087 *overlaps_b = conflict_fn_not_known ();
3088 *last_conflicts = chrec_dont_know;
3089 goto end_analyze_subs_aa;
3092 niter = MIN (niter_a, niter_b);
3094 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
3095 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
3097 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
3100 *overlaps_a = conflict_fn (1, ova);
3101 *overlaps_b = conflict_fn (1, ovb);
3104 else if (nb_vars_a == 2 && nb_vars_b == 1)
3105 compute_overlap_steps_for_affine_1_2
3106 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
3108 else if (nb_vars_a == 1 && nb_vars_b == 2)
3109 compute_overlap_steps_for_affine_1_2
3110 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
3114 if (dump_file && (dump_flags & TDF_DETAILS))
3115 fprintf (dump_file, "affine-affine test failed: too many variables.\n");
3116 *overlaps_a = conflict_fn_not_known ();
3117 *overlaps_b = conflict_fn_not_known ();
3118 *last_conflicts = chrec_dont_know;
3120 goto end_analyze_subs_aa;
3124 lambda_matrix_right_hermite (A, dim, 1, S, U);
3129 lambda_matrix_row_negate (U, dim, 0);
3131 gcd_alpha_beta = S[0][0];
3133 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
3134 but that is a quite strange case. Instead of ICEing, answer
3136 if (gcd_alpha_beta == 0)
3138 *overlaps_a = conflict_fn_not_known ();
3139 *overlaps_b = conflict_fn_not_known ();
3140 *last_conflicts = chrec_dont_know;
3141 goto end_analyze_subs_aa;
3144 /* The classic "gcd-test". */
3145 if (!int_divides_p (gcd_alpha_beta, gamma))
3147 /* The "gcd-test" has determined that there is no integer
3148 solution, i.e. there is no dependence. */
3149 *overlaps_a = conflict_fn_no_dependence ();
3150 *overlaps_b = conflict_fn_no_dependence ();
3151 *last_conflicts = integer_zero_node;
3154 /* Both access functions are univariate. This includes SIV and MIV cases. */
3155 else if (nb_vars_a == 1 && nb_vars_b == 1)
3157 /* Both functions should have the same evolution sign. */
3158 if (((A[0][0] > 0 && -A[1][0] > 0)
3159 || (A[0][0] < 0 && -A[1][0] < 0)))
3161 /* The solutions are given by:
3163 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
3166 For a given integer t. Using the following variables,
3168 | i0 = u11 * gamma / gcd_alpha_beta
3169 | j0 = u12 * gamma / gcd_alpha_beta
3176 | y0 = j0 + j1 * t. */
3180 /* X0 and Y0 are the first iterations for which there is a
3181 dependence. X0, Y0 are two solutions of the Diophantine
3182 equation: chrec_a (X0) = chrec_b (Y0). */
3184 int niter, niter_a, niter_b;
3186 niter_a = estimated_loop_iterations_int
3187 (get_chrec_loop (chrec_a), true);
3188 niter_b = estimated_loop_iterations_int
3189 (get_chrec_loop (chrec_b), true);
3191 if (niter_a < 0 || niter_b < 0)
3193 if (dump_file && (dump_flags & TDF_DETAILS))
3194 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
3195 *overlaps_a = conflict_fn_not_known ();
3196 *overlaps_b = conflict_fn_not_known ();
3197 *last_conflicts = chrec_dont_know;
3198 goto end_analyze_subs_aa;
3201 niter = MIN (niter_a, niter_b);
3203 i0 = U[0][0] * gamma / gcd_alpha_beta;
3204 j0 = U[0][1] * gamma / gcd_alpha_beta;
3208 if ((i1 == 0 && i0 < 0)
3209 || (j1 == 0 && j0 < 0))
3211 /* There is no solution.
3212 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
3213 falls in here, but for the moment we don't look at the
3214 upper bound of the iteration domain. */
3215 *overlaps_a = conflict_fn_no_dependence ();
3216 *overlaps_b = conflict_fn_no_dependence ();
3217 *last_conflicts = integer_zero_node;
3224 tau1 = CEIL (-i0, i1);
3225 tau2 = FLOOR_DIV (niter - i0, i1);
3229 int last_conflict, min_multiple;
3230 tau1 = MAX (tau1, CEIL (-j0, j1));
3231 tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
3233 x0 = i1 * tau1 + i0;
3234 y0 = j1 * tau1 + j0;
3236 /* At this point (x0, y0) is one of the
3237 solutions to the Diophantine equation. The
3238 next step has to compute the smallest
3239 positive solution: the first conflicts. */
3240 min_multiple = MIN (x0 / i1, y0 / j1);
3241 x0 -= i1 * min_multiple;
3242 y0 -= j1 * min_multiple;
3244 tau1 = (x0 - i0)/i1;
3245 last_conflict = tau2 - tau1;
3247 /* If the overlap occurs outside of the bounds of the
3248 loop, there is no dependence. */
3249 if (x0 > niter || y0 > niter)
3251 *overlaps_a = conflict_fn_no_dependence ();
3252 *overlaps_b = conflict_fn_no_dependence ();
3253 *last_conflicts = integer_zero_node;
3259 affine_fn_univar (build_int_cst (NULL_TREE, x0),
3261 build_int_cst (NULL_TREE, i1)));
3264 affine_fn_univar (build_int_cst (NULL_TREE, y0),
3266 build_int_cst (NULL_TREE, j1)));
3267 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
3272 /* FIXME: For the moment, the upper bound of the
3273 iteration domain for j is not checked. */
3274 if (dump_file && (dump_flags & TDF_DETAILS))
3275 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3276 *overlaps_a = conflict_fn_not_known ();
3277 *overlaps_b = conflict_fn_not_known ();
3278 *last_conflicts = chrec_dont_know;
3284 /* FIXME: For the moment, the upper bound of the
3285 iteration domain for i is not checked. */
3286 if (dump_file && (dump_flags & TDF_DETAILS))
3287 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3288 *overlaps_a = conflict_fn_not_known ();
3289 *overlaps_b = conflict_fn_not_known ();
3290 *last_conflicts = chrec_dont_know;
3296 if (dump_file && (dump_flags & TDF_DETAILS))
3297 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3298 *overlaps_a = conflict_fn_not_known ();
3299 *overlaps_b = conflict_fn_not_known ();
3300 *last_conflicts = chrec_dont_know;
3306 if (dump_file && (dump_flags & TDF_DETAILS))
3307 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3308 *overlaps_a = conflict_fn_not_known ();
3309 *overlaps_b = conflict_fn_not_known ();
3310 *last_conflicts = chrec_dont_know;
3313 end_analyze_subs_aa:
3314 if (dump_file && (dump_flags & TDF_DETAILS))
3316 fprintf (dump_file, " (overlaps_a = ");
3317 dump_conflict_function (dump_file, *overlaps_a);
3318 fprintf (dump_file, ")\n (overlaps_b = ");
3319 dump_conflict_function (dump_file, *overlaps_b);
3320 fprintf (dump_file, ")\n");
3321 fprintf (dump_file, ")\n");
3325 /* Returns true when analyze_subscript_affine_affine can be used for
3326 determining the dependence relation between chrec_a and chrec_b,
3327 that contain symbols. This function modifies chrec_a and chrec_b
3328 such that the analysis result is the same, and such that they don't
3329 contain symbols, and then can safely be passed to the analyzer.
3331 Example: The analysis of the following tuples of evolutions produce
3332 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
3335 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
3336 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
3340 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
3342 tree diff, type, left_a, left_b, right_b;
3344 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
3345 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
3346 /* FIXME: For the moment not handled. Might be refined later. */
3349 type = chrec_type (*chrec_a);
3350 left_a = CHREC_LEFT (*chrec_a);
3351 left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE);
3352 diff = chrec_fold_minus (type, left_a, left_b);
3354 if (!evolution_function_is_constant_p (diff))
3357 if (dump_file && (dump_flags & TDF_DETAILS))
3358 fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
3360 *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
3361 diff, CHREC_RIGHT (*chrec_a));
3362 right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE);
3363 *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
3364 build_int_cst (type, 0),
3369 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
3370 *OVERLAPS_B are initialized to the functions that describe the
3371 relation between the elements accessed twice by CHREC_A and
3372 CHREC_B. For k >= 0, the following property is verified:
3374 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
3377 analyze_siv_subscript (tree chrec_a,
3379 conflict_function **overlaps_a,
3380 conflict_function **overlaps_b,
3381 tree *last_conflicts)
3383 dependence_stats.num_siv++;
3385 if (dump_file && (dump_flags & TDF_DETAILS))
3386 fprintf (dump_file, "(analyze_siv_subscript \n");
3388 if (evolution_function_is_constant_p (chrec_a)
3389 && evolution_function_is_affine_p (chrec_b))
3390 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
3391 overlaps_a, overlaps_b, last_conflicts);
3393 else if (evolution_function_is_affine_p (chrec_a)
3394 && evolution_function_is_constant_p (chrec_b))
3395 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
3396 overlaps_b, overlaps_a, last_conflicts);
3398 else if (evolution_function_is_affine_p (chrec_a)
3399 && evolution_function_is_affine_p (chrec_b))
3401 if (!chrec_contains_symbols (chrec_a)
3402 && !chrec_contains_symbols (chrec_b))
3404 analyze_subscript_affine_affine (chrec_a, chrec_b,
3405 overlaps_a, overlaps_b,
3408 if (CF_NOT_KNOWN_P (*overlaps_a)
3409 || CF_NOT_KNOWN_P (*overlaps_b))
3410 dependence_stats.num_siv_unimplemented++;
3411 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
3412 || CF_NO_DEPENDENCE_P (*overlaps_b))
3413 dependence_stats.num_siv_independent++;
3415 dependence_stats.num_siv_dependent++;
3417 else if (can_use_analyze_subscript_affine_affine (&chrec_a,
3420 analyze_subscript_affine_affine (chrec_a, chrec_b,
3421 overlaps_a, overlaps_b,
3423 /* FIXME: The number of iterations is a symbolic expression.
3424 Compute it properly. */
3425 *last_conflicts = chrec_dont_know;
3427 if (CF_NOT_KNOWN_P (*overlaps_a)
3428 || CF_NOT_KNOWN_P (*overlaps_b))
3429 dependence_stats.num_siv_unimplemented++;
3430 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
3431 || CF_NO_DEPENDENCE_P (*overlaps_b))
3432 dependence_stats.num_siv_independent++;
3434 dependence_stats.num_siv_dependent++;
3437 goto siv_subscript_dontknow;
3442 siv_subscript_dontknow:;
3443 if (dump_file && (dump_flags & TDF_DETAILS))
3444 fprintf (dump_file, "siv test failed: unimplemented.\n");
3445 *overlaps_a = conflict_fn_not_known ();
3446 *overlaps_b = conflict_fn_not_known ();
3447 *last_conflicts = chrec_dont_know;
3448 dependence_stats.num_siv_unimplemented++;
3451 if (dump_file && (dump_flags & TDF_DETAILS))
3452 fprintf (dump_file, ")\n");
3455 /* Return true when the property can be computed. RES should contain
3456 true when calling the first time this function, then it is set to
3457 false when one of the evolution steps of an affine CHREC does not
3458 divide the constant CST. */
3461 chrec_steps_divide_constant_p (tree chrec,
3465 switch (TREE_CODE (chrec))
3467 case POLYNOMIAL_CHREC:
3468 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
3470 if (tree_fold_divides_p (CHREC_RIGHT (chrec), cst))
3471 /* Keep RES to true, and iterate on other dimensions. */
3472 return chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst, res);
3478 /* When the step is a parameter the result is undetermined. */
3482 /* On the initial condition, return true. */
3487 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
3488 *OVERLAPS_B are initialized to the functions that describe the
3489 relation between the elements accessed twice by CHREC_A and
3490 CHREC_B. For k >= 0, the following property is verified:
3492 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
3495 analyze_miv_subscript (tree chrec_a,
3497 conflict_function **overlaps_a,
3498 conflict_function **overlaps_b,
3499 tree *last_conflicts)
3501 /* FIXME: This is a MIV subscript, not yet handled.
3502 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
3505 In the SIV test we had to solve a Diophantine equation with two
3506 variables. In the MIV case we have to solve a Diophantine
3507 equation with 2*n variables (if the subscript uses n IVs).
3509 bool divide_p = true;
3511 dependence_stats.num_miv++;
3512 if (dump_file && (dump_flags & TDF_DETAILS))
3513 fprintf (dump_file, "(analyze_miv_subscript \n");
3515 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
3516 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
3517 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
3519 if (eq_evolutions_p (chrec_a, chrec_b))
3521 /* Access functions are the same: all the elements are accessed
3522 in the same order. */
3523 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
3524 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
3525 *last_conflicts = estimated_loop_iterations_tree
3526 (get_chrec_loop (chrec_a), true);
3527 dependence_stats.num_miv_dependent++;
3530 else if (evolution_function_is_constant_p (difference)
3531 /* For the moment, the following is verified:
3532 evolution_function_is_affine_multivariate_p (chrec_a) */
3533 && chrec_steps_divide_constant_p (chrec_a, difference, ÷_p)
3536 /* testsuite/.../ssa-chrec-33.c
3537 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
3539 The difference is 1, and the evolution steps are equal to 2,
3540 consequently there are no overlapping elements. */
3541 *overlaps_a = conflict_fn_no_dependence ();
3542 *overlaps_b = conflict_fn_no_dependence ();
3543 *last_conflicts = integer_zero_node;
3544 dependence_stats.num_miv_independent++;
3547 else if (evolution_function_is_affine_multivariate_p (chrec_a)
3548 && !chrec_contains_symbols (chrec_a)
3549 && evolution_function_is_affine_multivariate_p (chrec_b)
3550 && !chrec_contains_symbols (chrec_b))
3552 /* testsuite/.../ssa-chrec-35.c
3553 {0, +, 1}_2 vs. {0, +, 1}_3
3554 the overlapping elements are respectively located at iterations:
3555 {0, +, 1}_x and {0, +, 1}_x,
3556 in other words, we have the equality:
3557 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
3560 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
3561 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
3563 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
3564 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
3566 analyze_subscript_affine_affine (chrec_a, chrec_b,
3567 overlaps_a, overlaps_b, last_conflicts);
3569 if (CF_NOT_KNOWN_P (*overlaps_a)
3570 || CF_NOT_KNOWN_P (*overlaps_b))
3571 dependence_stats.num_miv_unimplemented++;
3572 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
3573 || CF_NO_DEPENDENCE_P (*overlaps_b))
3574 dependence_stats.num_miv_independent++;
3576 dependence_stats.num_miv_dependent++;
3581 /* When the analysis is too difficult, answer "don't know". */
3582 if (dump_file && (dump_flags & TDF_DETAILS))
3583 fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
3585 *overlaps_a = conflict_fn_not_known ();
3586 *overlaps_b = conflict_fn_not_known ();
3587 *last_conflicts = chrec_dont_know;
3588 dependence_stats.num_miv_unimplemented++;
3591 if (dump_file && (dump_flags & TDF_DETAILS))
3592 fprintf (dump_file, ")\n");
3595 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
3596 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
3597 two functions that describe the iterations that contain conflicting
3600 Remark: For an integer k >= 0, the following equality is true:
3602 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
3606 analyze_overlapping_iterations (tree chrec_a,
3608 conflict_function **overlap_iterations_a,
3609 conflict_function **overlap_iterations_b,
3610 tree *last_conflicts)
3612 dependence_stats.num_subscript_tests++;
3614 if (dump_file && (dump_flags & TDF_DETAILS))
3616 fprintf (dump_file, "(analyze_overlapping_iterations \n");
3617 fprintf (dump_file, " (chrec_a = ");
3618 print_generic_expr (dump_file, chrec_a, 0);
3619 fprintf (dump_file, ")\n (chrec_b = ");
3620 print_generic_expr (dump_file, chrec_b, 0);
3621 fprintf (dump_file, ")\n");
3624 if (chrec_a == NULL_TREE
3625 || chrec_b == NULL_TREE
3626 || chrec_contains_undetermined (chrec_a)
3627 || chrec_contains_undetermined (chrec_b))
3629 dependence_stats.num_subscript_undetermined++;
3631 *overlap_iterations_a = conflict_fn_not_known ();
3632 *overlap_iterations_b = conflict_fn_not_known ();
3635 /* If they are the same chrec, and are affine, they overlap
3636 on every iteration. */
3637 else if (eq_evolutions_p (chrec_a, chrec_b)
3638 && evolution_function_is_affine_multivariate_p (chrec_a))
3640 dependence_stats.num_same_subscript_function++;
3641 *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
3642 *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
3643 *last_conflicts = chrec_dont_know;
3646 /* If they aren't the same, and aren't affine, we can't do anything
3648 else if ((chrec_contains_symbols (chrec_a)
3649 || chrec_contains_symbols (chrec_b))
3650 && (!evolution_function_is_affine_multivariate_p (chrec_a)
3651 || !evolution_function_is_affine_multivariate_p (chrec_b)))
3653 dependence_stats.num_subscript_undetermined++;
3654 *overlap_iterations_a = conflict_fn_not_known ();
3655 *overlap_iterations_b = conflict_fn_not_known ();
3658 else if (ziv_subscript_p (chrec_a, chrec_b))
3659 analyze_ziv_subscript (chrec_a, chrec_b,
3660 overlap_iterations_a, overlap_iterations_b,
3663 else if (siv_subscript_p (chrec_a, chrec_b))
3664 analyze_siv_subscript (chrec_a, chrec_b,
3665 overlap_iterations_a, overlap_iterations_b,
3669 analyze_miv_subscript (chrec_a, chrec_b,
3670 overlap_iterations_a, overlap_iterations_b,
3673 if (dump_file && (dump_flags & TDF_DETAILS))
3675 fprintf (dump_file, " (overlap_iterations_a = ");
3676 dump_conflict_function (dump_file, *overlap_iterations_a);
3677 fprintf (dump_file, ")\n (overlap_iterations_b = ");
3678 dump_conflict_function (dump_file, *overlap_iterations_b);
3679 fprintf (dump_file, ")\n");
3680 fprintf (dump_file, ")\n");
3684 /* Helper function for uniquely inserting distance vectors. */
3687 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
3692 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
3693 if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
3696 VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
3699 /* Helper function for uniquely inserting direction vectors. */
3702 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
3707 for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
3708 if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
3711 VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
3714 /* Add a distance of 1 on all the loops outer than INDEX. If we
3715 haven't yet determined a distance for this outer loop, push a new
3716 distance vector composed of the previous distance, and a distance
3717 of 1 for this outer loop. Example:
3725 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
3726 save (0, 1), then we have to save (1, 0). */
3729 add_outer_distances (struct data_dependence_relation *ddr,
3730 lambda_vector dist_v, int index)
3732 /* For each outer loop where init_v is not set, the accesses are
3733 in dependence of distance 1 in the loop. */
3734 while (--index >= 0)
3736 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3737 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3739 save_dist_v (ddr, save_v);
3743 /* Return false when fail to represent the data dependence as a
3744 distance vector. INIT_B is set to true when a component has been
3745 added to the distance vector DIST_V. INDEX_CARRY is then set to
3746 the index in DIST_V that carries the dependence. */
3749 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
3750 struct data_reference *ddr_a,
3751 struct data_reference *ddr_b,
3752 lambda_vector dist_v, bool *init_b,
3756 lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3758 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3760 tree access_fn_a, access_fn_b;
3761 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3763 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3765 non_affine_dependence_relation (ddr);
3769 access_fn_a = DR_ACCESS_FN (ddr_a, i);
3770 access_fn_b = DR_ACCESS_FN (ddr_b, i);
3772 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3773 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3776 int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
3777 DDR_LOOP_NEST (ddr));
3778 int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
3779 DDR_LOOP_NEST (ddr));
3781 /* The dependence is carried by the outermost loop. Example:
3788 In this case, the dependence is carried by loop_1. */
3789 index = index_a < index_b ? index_a : index_b;
3790 *index_carry = MIN (index, *index_carry);
3792 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3794 non_affine_dependence_relation (ddr);
3798 dist = int_cst_value (SUB_DISTANCE (subscript));
3800 /* This is the subscript coupling test. If we have already
3801 recorded a distance for this loop (a distance coming from
3802 another subscript), it should be the same. For example,
3803 in the following code, there is no dependence:
3810 if (init_v[index] != 0 && dist_v[index] != dist)
3812 finalize_ddr_dependent (ddr, chrec_known);
3816 dist_v[index] = dist;
3822 /* This can be for example an affine vs. constant dependence
3823 (T[i] vs. T[3]) that is not an affine dependence and is
3824 not representable as a distance vector. */
3825 non_affine_dependence_relation (ddr);
3833 /* Return true when the DDR contains two data references that have the
3834 same access functions. */
3837 same_access_functions (struct data_dependence_relation *ddr)
3841 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3842 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
3843 DR_ACCESS_FN (DDR_B (ddr), i)))
3849 /* Helper function for the case where DDR_A and DDR_B are the same
3850 multivariate access function. */
3853 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
3856 tree c_1 = CHREC_LEFT (c_2);
3857 tree c_0 = CHREC_LEFT (c_1);
3858 lambda_vector dist_v;
3860 /* Polynomials with more than 2 variables are not handled yet. */
3861 if (TREE_CODE (c_0) != INTEGER_CST)
3863 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
3867 x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
3868 x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
3870 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3871 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3872 dist_v[x_1] = int_cst_value (CHREC_RIGHT (c_2));
3873 dist_v[x_2] = -int_cst_value (CHREC_RIGHT (c_1));
3874 save_dist_v (ddr, dist_v);
3876 add_outer_distances (ddr, dist_v, x_1);
3879 /* Helper function for the case where DDR_A and DDR_B are the same
3880 access functions. */
3883 add_other_self_distances (struct data_dependence_relation *ddr)
3885 lambda_vector dist_v;
3887 int index_carry = DDR_NB_LOOPS (ddr);
3889 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3891 tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
3893 if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
3895 if (!evolution_function_is_univariate_p (access_fun))
3897 if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
3899 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
3903 add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0));
3907 index_carry = MIN (index_carry,
3908 index_in_loop_nest (CHREC_VARIABLE (access_fun),
3909 DDR_LOOP_NEST (ddr)));
3913 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3914 add_outer_distances (ddr, dist_v, index_carry);
3917 /* Compute the classic per loop distance vector. DDR is the data
3918 dependence relation to build a vector from. Return false when fail
3919 to represent the data dependence as a distance vector. */
3922 build_classic_dist_vector (struct data_dependence_relation *ddr)
3924 bool init_b = false;
3925 int index_carry = DDR_NB_LOOPS (ddr);
3926 lambda_vector dist_v;
3928 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3931 if (same_access_functions (ddr))
3933 /* Save the 0 vector. */
3934 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3935 save_dist_v (ddr, dist_v);
3937 if (DDR_NB_LOOPS (ddr) > 1)
3938 add_other_self_distances (ddr);
3943 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3944 if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
3945 dist_v, &init_b, &index_carry))
3948 /* Save the distance vector if we initialized one. */
3951 /* Verify a basic constraint: classic distance vectors should
3952 always be lexicographically positive.
3954 Data references are collected in the order of execution of
3955 the program, thus for the following loop
3957 | for (i = 1; i < 100; i++)
3958 | for (j = 1; j < 100; j++)
3960 | t = T[j+1][i-1]; // A
3961 | T[j][i] = t + 2; // B
3964 references are collected following the direction of the wind:
3965 A then B. The data dependence tests are performed also
3966 following this order, such that we're looking at the distance
3967 separating the elements accessed by A from the elements later
3968 accessed by B. But in this example, the distance returned by
3969 test_dep (A, B) is lexicographically negative (-1, 1), that
3970 means that the access A occurs later than B with respect to
3971 the outer loop, ie. we're actually looking upwind. In this
3972 case we solve test_dep (B, A) looking downwind to the
3973 lexicographically positive solution, that returns the
3974 distance vector (1, -1). */
3975 if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
3977 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3978 subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
3979 compute_subscript_distance (ddr);
3980 build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3981 save_v, &init_b, &index_carry);
3982 save_dist_v (ddr, save_v);
3984 /* In this case there is a dependence forward for all the
3987 | for (k = 1; k < 100; k++)
3988 | for (i = 1; i < 100; i++)
3989 | for (j = 1; j < 100; j++)
3991 | t = T[j+1][i-1]; // A
3992 | T[j][i] = t + 2; // B
4000 if (DDR_NB_LOOPS (ddr) > 1)
4002 add_outer_distances (ddr, save_v, index_carry);
4003 add_outer_distances (ddr, dist_v, index_carry);
4008 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4009 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
4010 save_dist_v (ddr, save_v);
4012 if (DDR_NB_LOOPS (ddr) > 1)
4014 lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4016 subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
4017 compute_subscript_distance (ddr);
4018 build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
4019 opposite_v, &init_b, &index_carry);
4021 add_outer_distances (ddr, dist_v, index_carry);
4022 add_outer_distances (ddr, opposite_v, index_carry);
4028 /* There is a distance of 1 on all the outer loops: Example:
4029 there is a dependence of distance 1 on loop_1 for the array A.
4035 add_outer_distances (ddr, dist_v,
4036 lambda_vector_first_nz (dist_v,
4037 DDR_NB_LOOPS (ddr), 0));
4040 if (dump_file && (dump_flags & TDF_DETAILS))
4044 fprintf (dump_file, "(build_classic_dist_vector\n");
4045 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
4047 fprintf (dump_file, " dist_vector = (");
4048 print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
4049 DDR_NB_LOOPS (ddr));
4050 fprintf (dump_file, " )\n");
4052 fprintf (dump_file, ")\n");
4058 /* Return the direction for a given distance.
4059 FIXME: Computing dir this way is suboptimal, since dir can catch
4060 cases that dist is unable to represent. */
4062 static inline enum data_dependence_direction
4063 dir_from_dist (int dist)
4066 return dir_positive;
4068 return dir_negative;
4073 /* Compute the classic per loop direction vector. DDR is the data
4074 dependence relation to build a vector from. */
4077 build_classic_dir_vector (struct data_dependence_relation *ddr)
4080 lambda_vector dist_v;
4082 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
4084 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4086 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
4087 dir_v[j] = dir_from_dist (dist_v[j]);
4089 save_dir_v (ddr, dir_v);
4093 /* Helper function. Returns true when there is a dependence between
4094 data references DRA and DRB. */
4097 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
4098 struct data_reference *dra,
4099 struct data_reference *drb)
4102 tree last_conflicts;
4103 struct subscript *subscript;
4105 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
4108 conflict_function *overlaps_a, *overlaps_b;
4110 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
4111 DR_ACCESS_FN (drb, i),
4112 &overlaps_a, &overlaps_b,
4115 if (CF_NOT_KNOWN_P (overlaps_a)
4116 || CF_NOT_KNOWN_P (overlaps_b))
4118 finalize_ddr_dependent (ddr, chrec_dont_know);
4119 dependence_stats.num_dependence_undetermined++;
4120 free_conflict_function (overlaps_a);
4121 free_conflict_function (overlaps_b);
4125 else if (CF_NO_DEPENDENCE_P (overlaps_a)
4126 || CF_NO_DEPENDENCE_P (overlaps_b))
4128 finalize_ddr_dependent (ddr, chrec_known);
4129 dependence_stats.num_dependence_independent++;
4130 free_conflict_function (overlaps_a);
4131 free_conflict_function (overlaps_b);
4137 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
4138 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
4139 SUB_LAST_CONFLICT (subscript) = last_conflicts;
4146 /* Computes the conflicting iterations, and initialize DDR. */
4149 subscript_dependence_tester (struct data_dependence_relation *ddr)
4152 if (dump_file && (dump_flags & TDF_DETAILS))
4153 fprintf (dump_file, "(subscript_dependence_tester \n");
4155 if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr)))
4156 dependence_stats.num_dependence_dependent++;
4158 compute_subscript_distance (ddr);
4159 if (build_classic_dist_vector (ddr))
4160 build_classic_dir_vector (ddr);
4162 if (dump_file && (dump_flags & TDF_DETAILS))
4163 fprintf (dump_file, ")\n");
4166 /* Returns true when all the access functions of A are affine or
4170 access_functions_are_affine_or_constant_p (struct data_reference *a)
4173 VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
4176 for (i = 0; VEC_iterate (tree, fns, i, t); i++)
4177 if (!evolution_function_is_constant_p (t)
4178 && !evolution_function_is_affine_multivariate_p (t))
4184 /* Initializes an equation for an OMEGA problem using the information
4185 contained in the ACCESS_FUN. Returns true when the operation
4188 PB is the omega constraint system.
4189 EQ is the number of the equation to be initialized.
4190 OFFSET is used for shifting the variables names in the constraints:
4191 a constrain is composed of 2 * the number of variables surrounding
4192 dependence accesses. OFFSET is set either to 0 for the first n variables,
4193 then it is set to n.
4194 ACCESS_FUN is expected to be an affine chrec. */
4197 init_omega_eq_with_af (omega_pb pb, unsigned eq,
4198 unsigned int offset, tree access_fun,
4199 struct data_dependence_relation *ddr)
4201 switch (TREE_CODE (access_fun))
4203 case POLYNOMIAL_CHREC:
4205 tree left = CHREC_LEFT (access_fun);
4206 tree right = CHREC_RIGHT (access_fun);
4207 int var = CHREC_VARIABLE (access_fun);
4210 if (TREE_CODE (right) != INTEGER_CST)
4213 var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
4214 pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
4216 /* Compute the innermost loop index. */
4217 DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
4220 pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
4221 += int_cst_value (right);
4223 switch (TREE_CODE (left))
4225 case POLYNOMIAL_CHREC:
4226 return init_omega_eq_with_af (pb, eq, offset, left, ddr);
4229 pb->eqs[eq].coef[0] += int_cst_value (left);
4238 pb->eqs[eq].coef[0] += int_cst_value (access_fun);
4246 /* As explained in the comments preceding init_omega_for_ddr, we have
4247 to set up a system for each loop level, setting outer loops
4248 variation to zero, and current loop variation to positive or zero.
4249 Save each lexico positive distance vector. */
4252 omega_extract_distance_vectors (omega_pb pb,
4253 struct data_dependence_relation *ddr)
4257 struct loop *loopi, *loopj;
4258 enum omega_result res;
4260 /* Set a new problem for each loop in the nest. The basis is the
4261 problem that we have initialized until now. On top of this we
4262 add new constraints. */
4263 for (i = 0; i <= DDR_INNER_LOOP (ddr)
4264 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
4267 omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
4268 DDR_NB_LOOPS (ddr));
4270 omega_copy_problem (copy, pb);
4272 /* For all the outer loops "loop_j", add "dj = 0". */
4274 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
4276 eq = omega_add_zero_eq (copy, omega_black);
4277 copy->eqs[eq].coef[j + 1] = 1;
4280 /* For "loop_i", add "0 <= di". */
4281 geq = omega_add_zero_geq (copy, omega_black);
4282 copy->geqs[geq].coef[i + 1] = 1;
4284 /* Reduce the constraint system, and test that the current
4285 problem is feasible. */
4286 res = omega_simplify_problem (copy);
4287 if (res == omega_false
4288 || res == omega_unknown
4289 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
4292 for (eq = 0; eq < copy->num_subs; eq++)
4293 if (copy->subs[eq].key == (int) i + 1)
4295 dist = copy->subs[eq].coef[0];
4301 /* Reinitialize problem... */
4302 omega_copy_problem (copy, pb);
4304 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
4306 eq = omega_add_zero_eq (copy, omega_black);
4307 copy->eqs[eq].coef[j + 1] = 1;
4310 /* ..., but this time "di = 1". */
4311 eq = omega_add_zero_eq (copy, omega_black);
4312 copy->eqs[eq].coef[i + 1] = 1;
4313 copy->eqs[eq].coef[0] = -1;
4315 res = omega_simplify_problem (copy);
4316 if (res == omega_false
4317 || res == omega_unknown
4318 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
4321 for (eq = 0; eq < copy->num_subs; eq++)
4322 if (copy->subs[eq].key == (int) i + 1)
4324 dist = copy->subs[eq].coef[0];
4330 /* Save the lexicographically positive distance vector. */
4333 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4334 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4338 for (eq = 0; eq < copy->num_subs; eq++)
4339 if (copy->subs[eq].key > 0)
4341 dist = copy->subs[eq].coef[0];
4342 dist_v[copy->subs[eq].key - 1] = dist;
4345 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
4346 dir_v[j] = dir_from_dist (dist_v[j]);
4348 save_dist_v (ddr, dist_v);
4349 save_dir_v (ddr, dir_v);
4353 omega_free_problem (copy);
4357 /* This is called for each subscript of a tuple of data references:
4358 insert an equality for representing the conflicts. */
4361 omega_setup_subscript (tree access_fun_a, tree access_fun_b,
4362 struct data_dependence_relation *ddr,
4363 omega_pb pb, bool *maybe_dependent)
4366 tree fun_a = chrec_convert (integer_type_node, access_fun_a, NULL_TREE);
4367 tree fun_b = chrec_convert (integer_type_node, access_fun_b, NULL_TREE);
4368 tree difference = chrec_fold_minus (integer_type_node, fun_a, fun_b);
4370 /* When the fun_a - fun_b is not constant, the dependence is not
4371 captured by the classic distance vector representation. */
4372 if (TREE_CODE (difference) != INTEGER_CST)
4376 if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
4378 /* There is no dependence. */
4379 *maybe_dependent = false;
4383 fun_b = chrec_fold_multiply (integer_type_node, fun_b,
4384 integer_minus_one_node);
4386 eq = omega_add_zero_eq (pb, omega_black);
4387 if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
4388 || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
4389 /* There is probably a dependence, but the system of
4390 constraints cannot be built: answer "don't know". */
4394 if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
4395 && !int_divides_p (lambda_vector_gcd
4396 ((lambda_vector) &(pb->eqs[eq].coef[1]),
4397 2 * DDR_NB_LOOPS (ddr)),
4398 pb->eqs[eq].coef[0]))
4400 /* There is no dependence. */
4401 *maybe_dependent = false;
4408 /* Helper function, same as init_omega_for_ddr but specialized for
4409 data references A and B. */
4412 init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
4413 struct data_dependence_relation *ddr,
4414 omega_pb pb, bool *maybe_dependent)
4419 unsigned nb_loops = DDR_NB_LOOPS (ddr);
4421 /* Insert an equality per subscript. */
4422 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
4424 if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
4425 ddr, pb, maybe_dependent))
4427 else if (*maybe_dependent == false)
4429 /* There is no dependence. */
4430 DDR_ARE_DEPENDENT (ddr) = chrec_known;
4435 /* Insert inequalities: constraints corresponding to the iteration
4436 domain, i.e. the loops surrounding the references "loop_x" and
4437 the distance variables "dx". The layout of the OMEGA
4438 representation is as follows:
4439 - coef[0] is the constant
4440 - coef[1..nb_loops] are the protected variables that will not be
4441 removed by the solver: the "dx"
4442 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
4444 for (i = 0; i <= DDR_INNER_LOOP (ddr)
4445 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
4447 HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, true);
4450 ineq = omega_add_zero_geq (pb, omega_black);
4451 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
4453 /* 0 <= loop_x + dx */
4454 ineq = omega_add_zero_geq (pb, omega_black);
4455 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
4456 pb->geqs[ineq].coef[i + 1] = 1;
4460 /* loop_x <= nb_iters */
4461 ineq = omega_add_zero_geq (pb, omega_black);
4462 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
4463 pb->geqs[ineq].coef[0] = nbi;
4465 /* loop_x + dx <= nb_iters */
4466 ineq = omega_add_zero_geq (pb, omega_black);
4467 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
4468 pb->geqs[ineq].coef[i + 1] = -1;
4469 pb->geqs[ineq].coef[0] = nbi;
4471 /* A step "dx" bigger than nb_iters is not feasible, so
4472 add "0 <= nb_iters + dx", */
4473 ineq = omega_add_zero_geq (pb, omega_black);
4474 pb->geqs[ineq].coef[i + 1] = 1;
4475 pb->geqs[ineq].coef[0] = nbi;
4476 /* and "dx <= nb_iters". */
4477 ineq = omega_add_zero_geq (pb, omega_black);
4478 pb->geqs[ineq].coef[i + 1] = -1;
4479 pb->geqs[ineq].coef[0] = nbi;
4483 omega_extract_distance_vectors (pb, ddr);
4488 /* Sets up the Omega dependence problem for the data dependence
4489 relation DDR. Returns false when the constraint system cannot be
4490 built, ie. when the test answers "don't know". Returns true
4491 otherwise, and when independence has been proved (using one of the
4492 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
4493 set MAYBE_DEPENDENT to true.
4495 Example: for setting up the dependence system corresponding to the
4496 conflicting accesses
4501 | ... A[2*j, 2*(i + j)]
4505 the following constraints come from the iteration domain:
4512 where di, dj are the distance variables. The constraints
4513 representing the conflicting elements are:
4516 i + 1 = 2 * (i + di + j + dj)
4518 For asking that the resulting distance vector (di, dj) be
4519 lexicographically positive, we insert the constraint "di >= 0". If
4520 "di = 0" in the solution, we fix that component to zero, and we
4521 look at the inner loops: we set a new problem where all the outer
4522 loop distances are zero, and fix this inner component to be
4523 positive. When one of the components is positive, we save that
4524 distance, and set a new problem where the distance on this loop is
4525 zero, searching for other distances in the inner loops. Here is
4526 the classic example that illustrates that we have to set for each
4527 inner loop a new problem:
4535 we have to save two distances (1, 0) and (0, 1).
4537 Given two array references, refA and refB, we have to set the
4538 dependence problem twice, refA vs. refB and refB vs. refA, and we
4539 cannot do a single test, as refB might occur before refA in the
4540 inner loops, and the contrary when considering outer loops: ex.
4545 | T[{1,+,1}_2][{1,+,1}_1] // refA
4546 | T[{2,+,1}_2][{0,+,1}_1] // refB
4551 refB touches the elements in T before refA, and thus for the same
4552 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
4553 but for successive loop_0 iterations, we have (1, -1, 1)
4555 The Omega solver expects the distance variables ("di" in the
4556 previous example) to come first in the constraint system (as
4557 variables to be protected, or "safe" variables), the constraint
4558 system is built using the following layout:
4560 "cst | distance vars | index vars".
4564 init_omega_for_ddr (struct data_dependence_relation *ddr,
4565 bool *maybe_dependent)
4570 *maybe_dependent = true;
4572 if (same_access_functions (ddr))
4575 lambda_vector dir_v;
4577 /* Save the 0 vector. */
4578 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
4579 dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4580 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
4581 dir_v[j] = dir_equal;
4582 save_dir_v (ddr, dir_v);
4584 /* Save the dependences carried by outer loops. */
4585 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4586 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
4588 omega_free_problem (pb);
4592 /* Omega expects the protected variables (those that have to be kept
4593 after elimination) to appear first in the constraint system.
4594 These variables are the distance variables. In the following
4595 initialization we declare NB_LOOPS safe variables, and the total
4596 number of variables for the constraint system is 2*NB_LOOPS. */
4597 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4598 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
4600 omega_free_problem (pb);
4602 /* Stop computation if not decidable, or no dependence. */
4603 if (res == false || *maybe_dependent == false)
4606 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4607 res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
4609 omega_free_problem (pb);
4614 /* Return true when DDR contains the same information as that stored
4615 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
4618 ddr_consistent_p (FILE *file,
4619 struct data_dependence_relation *ddr,
4620 VEC (lambda_vector, heap) *dist_vects,
4621 VEC (lambda_vector, heap) *dir_vects)
4625 /* If dump_file is set, output there. */
4626 if (dump_file && (dump_flags & TDF_DETAILS))
4629 if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
4631 lambda_vector b_dist_v;
4632 fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
4633 VEC_length (lambda_vector, dist_vects),
4634 DDR_NUM_DIST_VECTS (ddr));
4636 fprintf (file, "Banerjee dist vectors:\n");
4637 for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++)
4638 print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
4640 fprintf (file, "Omega dist vectors:\n");
4641 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
4642 print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
4644 fprintf (file, "data dependence relation:\n");
4645 dump_data_dependence_relation (file, ddr);
4647 fprintf (file, ")\n");
4651 if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
4653 fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
4654 VEC_length (lambda_vector, dir_vects),
4655 DDR_NUM_DIR_VECTS (ddr));
4659 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
4661 lambda_vector a_dist_v;
4662 lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
4664 /* Distance vectors are not ordered in the same way in the DDR
4665 and in the DIST_VECTS: search for a matching vector. */
4666 for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, a_dist_v); j++)
4667 if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
4670 if (j == VEC_length (lambda_vector, dist_vects))
4672 fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
4673 print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
4674 fprintf (file, "not found in Omega dist vectors:\n");
4675 print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
4676 fprintf (file, "data dependence relation:\n");
4677 dump_data_dependence_relation (file, ddr);
4678 fprintf (file, ")\n");
4682 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
4684 lambda_vector a_dir_v;
4685 lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
4687 /* Direction vectors are not ordered in the same way in the DDR
4688 and in the DIR_VECTS: search for a matching vector. */
4689 for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, a_dir_v); j++)
4690 if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
4693 if (j == VEC_length (lambda_vector, dist_vects))
4695 fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
4696 print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
4697 fprintf (file, "not found in Omega dir vectors:\n");
4698 print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
4699 fprintf (file, "data dependence relation:\n");
4700 dump_data_dependence_relation (file, ddr);
4701 fprintf (file, ")\n");
4708 /* This computes the affine dependence relation between A and B.
4709 CHREC_KNOWN is used for representing the independence between two
4710 accesses, while CHREC_DONT_KNOW is used for representing the unknown
4713 Note that it is possible to stop the computation of the dependence
4714 relation the first time we detect a CHREC_KNOWN element for a given
4718 compute_affine_dependence (struct data_dependence_relation *ddr)
4720 struct data_reference *dra = DDR_A (ddr);
4721 struct data_reference *drb = DDR_B (ddr);
4723 if (dump_file && (dump_flags & TDF_DETAILS))
4725 fprintf (dump_file, "(compute_affine_dependence\n");
4726 fprintf (dump_file, " (stmt_a = \n");
4727 print_generic_expr (dump_file, DR_STMT (dra), 0);
4728 fprintf (dump_file, ")\n (stmt_b = \n");
4729 print_generic_expr (dump_file, DR_STMT (drb), 0);
4730 fprintf (dump_file, ")\n");
4733 /* Analyze only when the dependence relation is not yet known. */
4734 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4736 dependence_stats.num_dependence_tests++;
4738 if (access_functions_are_affine_or_constant_p (dra)
4739 && access_functions_are_affine_or_constant_p (drb))
4741 if (flag_check_data_deps)
4743 /* Compute the dependences using the first algorithm. */
4744 subscript_dependence_tester (ddr);
4746 if (dump_file && (dump_flags & TDF_DETAILS))
4748 fprintf (dump_file, "\n\nBanerjee Analyzer\n");
4749 dump_data_dependence_relation (dump_file, ddr);
4752 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4754 bool maybe_dependent;
4755 VEC (lambda_vector, heap) *dir_vects, *dist_vects;
4757 /* Save the result of the first DD analyzer. */
4758 dist_vects = DDR_DIST_VECTS (ddr);
4759 dir_vects = DDR_DIR_VECTS (ddr);
4761 /* Reset the information. */
4762 DDR_DIST_VECTS (ddr) = NULL;
4763 DDR_DIR_VECTS (ddr) = NULL;
4765 /* Compute the same information using Omega. */
4766 if (!init_omega_for_ddr (ddr, &maybe_dependent))
4767 goto csys_dont_know;
4769 if (dump_file && (dump_flags & TDF_DETAILS))
4771 fprintf (dump_file, "Omega Analyzer\n");
4772 dump_data_dependence_relation (dump_file, ddr);
4775 /* Check that we get the same information. */
4776 if (maybe_dependent)
4777 gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
4782 subscript_dependence_tester (ddr);
4785 /* As a last case, if the dependence cannot be determined, or if
4786 the dependence is considered too difficult to determine, answer
4791 dependence_stats.num_dependence_undetermined++;
4793 if (dump_file && (dump_flags & TDF_DETAILS))
4795 fprintf (dump_file, "Data ref a:\n");
4796 dump_data_reference (dump_file, dra);
4797 fprintf (dump_file, "Data ref b:\n");
4798 dump_data_reference (dump_file, drb);
4799 fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
4801 finalize_ddr_dependent (ddr, chrec_dont_know);
4805 if (dump_file && (dump_flags & TDF_DETAILS))
4806 fprintf (dump_file, ")\n");
4809 /* This computes the dependence relation for the same data
4810 reference into DDR. */
4813 compute_self_dependence (struct data_dependence_relation *ddr)
4816 struct subscript *subscript;
4818 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
4821 /* The accessed index overlaps for each iteration. */
4822 SUB_CONFLICTS_IN_A (subscript)
4823 = conflict_fn (1, affine_fn_cst (integer_zero_node));
4824 SUB_CONFLICTS_IN_B (subscript)
4825 = conflict_fn (1, affine_fn_cst (integer_zero_node));
4826 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
4829 /* The distance vector is the zero vector. */
4830 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
4831 save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
4834 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4835 the data references in DATAREFS, in the LOOP_NEST. When
4836 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4840 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
4841 VEC (ddr_p, heap) **dependence_relations,
4842 VEC (loop_p, heap) *loop_nest,
4843 bool compute_self_and_rr)
4845 struct data_dependence_relation *ddr;
4846 struct data_reference *a, *b;
4849 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
4850 for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
4851 if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
4853 ddr = initialize_data_dependence_relation (a, b, loop_nest);
4854 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4855 compute_affine_dependence (ddr);
4858 if (compute_self_and_rr)
4859 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
4861 ddr = initialize_data_dependence_relation (a, a, loop_nest);
4862 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4863 compute_self_dependence (ddr);
4867 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4868 true if STMT clobbers memory, false otherwise. */
4871 get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references)
4873 bool clobbers_memory = false;
4875 tree *op0, *op1, arg, call;
4876 call_expr_arg_iterator iter;
4880 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4881 Calls have side-effects, except those to const or pure
4883 call = get_call_expr_in (stmt);
4885 && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE)))
4886 || (TREE_CODE (stmt) == ASM_EXPR
4887 && ASM_VOLATILE_P (stmt)))
4888 clobbers_memory = true;
4890 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
4891 return clobbers_memory;
4893 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
4895 op0 = &GIMPLE_STMT_OPERAND (stmt, 0);
4896 op1 = &GIMPLE_STMT_OPERAND (stmt, 1);
4899 || REFERENCE_CLASS_P (*op1))
4901 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4903 ref->is_read = true;
4907 || REFERENCE_CLASS_P (*op0))
4909 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4911 ref->is_read = false;
4917 FOR_EACH_CALL_EXPR_ARG (arg, iter, call)
4921 || REFERENCE_CLASS_P (*op0))
4923 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4925 ref->is_read = true;
4930 return clobbers_memory;
4933 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4934 reference, returns false, otherwise returns true. */
4937 find_data_references_in_stmt (tree stmt,
4938 VEC (data_reference_p, heap) **datarefs)
4941 VEC (data_ref_loc, heap) *references;
4944 data_reference_p dr;
4946 if (get_references_in_stmt (stmt, &references))
4948 VEC_free (data_ref_loc, heap, references);
4952 for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
4954 dr = create_data_ref (*ref->pos, stmt, ref->is_read);
4956 VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4963 VEC_free (data_ref_loc, heap, references);
4967 /* Search the data references in LOOP, and record the information into
4968 DATAREFS. Returns chrec_dont_know when failing to analyze a
4969 difficult case, returns NULL_TREE otherwise.
4971 TODO: This function should be made smarter so that it can handle address
4972 arithmetic as if they were array accesses, etc. */
4975 find_data_references_in_loop (struct loop *loop,
4976 VEC (data_reference_p, heap) **datarefs)
4978 basic_block bb, *bbs;
4980 block_stmt_iterator bsi;
4982 bbs = get_loop_body (loop);
4984 for (i = 0; i < loop->num_nodes; i++)
4988 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4990 tree stmt = bsi_stmt (bsi);
4992 if (!find_data_references_in_stmt (stmt, datarefs))
4994 struct data_reference *res;
4995 res = XNEW (struct data_reference);
4996 DR_STMT (res) = NULL_TREE;
4997 DR_REF (res) = NULL_TREE;
4998 DR_BASE_OBJECT (res) = NULL;
4999 DR_TYPE (res) = ARRAY_REF_TYPE;
5000 DR_SET_ACCESS_FNS (res, NULL);
5001 DR_BASE_OBJECT (res) = NULL;
5002 DR_IS_READ (res) = false;
5003 DR_BASE_ADDRESS (res) = NULL_TREE;
5004 DR_OFFSET (res) = NULL_TREE;
5005 DR_INIT (res) = NULL_TREE;
5006 DR_STEP (res) = NULL_TREE;
5007 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
5008 DR_MEMTAG (res) = NULL_TREE;
5009 DR_PTR_INFO (res) = NULL;
5010 VEC_safe_push (data_reference_p, heap, *datarefs, res);
5013 return chrec_dont_know;
5022 /* Recursive helper function. */
5025 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
5027 /* Inner loops of the nest should not contain siblings. Example:
5028 when there are two consecutive loops,
5039 the dependence relation cannot be captured by the distance
5044 VEC_safe_push (loop_p, heap, *loop_nest, loop);
5046 return find_loop_nest_1 (loop->inner, loop_nest);
5050 /* Return false when the LOOP is not well nested. Otherwise return
5051 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
5052 contain the loops from the outermost to the innermost, as they will
5053 appear in the classic distance vector. */
5056 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
5058 VEC_safe_push (loop_p, heap, *loop_nest, loop);
5060 return find_loop_nest_1 (loop->inner, loop_nest);
5064 /* Given a loop nest LOOP, the following vectors are returned:
5065 DATAREFS is initialized to all the array elements contained in this loop,
5066 DEPENDENCE_RELATIONS contains the relations between the data references.
5067 Compute read-read and self relations if
5068 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
5071 compute_data_dependences_for_loop (struct loop *loop,
5072 bool compute_self_and_read_read_dependences,
5073 VEC (data_reference_p, heap) **datarefs,
5074 VEC (ddr_p, heap) **dependence_relations)
5076 struct loop *loop_nest = loop;
5077 VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
5079 memset (&dependence_stats, 0, sizeof (dependence_stats));
5081 /* If the loop nest is not well formed, or one of the data references
5082 is not computable, give up without spending time to compute other
5085 || !find_loop_nest (loop_nest, &vloops)
5086 || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
5088 struct data_dependence_relation *ddr;
5090 /* Insert a single relation into dependence_relations:
5092 ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
5093 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
5096 compute_all_dependences (*datarefs, dependence_relations, vloops,
5097 compute_self_and_read_read_dependences);
5099 if (dump_file && (dump_flags & TDF_STATS))
5101 fprintf (dump_file, "Dependence tester statistics:\n");
5103 fprintf (dump_file, "Number of dependence tests: %d\n",
5104 dependence_stats.num_dependence_tests);
5105 fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
5106 dependence_stats.num_dependence_dependent);
5107 fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
5108 dependence_stats.num_dependence_independent);
5109 fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
5110 dependence_stats.num_dependence_undetermined);
5112 fprintf (dump_file, "Number of subscript tests: %d\n",
5113 dependence_stats.num_subscript_tests);
5114 fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
5115 dependence_stats.num_subscript_undetermined);
5116 fprintf (dump_file, "Number of same subscript function: %d\n",
5117 dependence_stats.num_same_subscript_function);
5119 fprintf (dump_file, "Number of ziv tests: %d\n",
5120 dependence_stats.num_ziv);
5121 fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
5122 dependence_stats.num_ziv_dependent);
5123 fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
5124 dependence_stats.num_ziv_independent);
5125 fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
5126 dependence_stats.num_ziv_unimplemented);
5128 fprintf (dump_file, "Number of siv tests: %d\n",
5129 dependence_stats.num_siv);
5130 fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
5131 dependence_stats.num_siv_dependent);
5132 fprintf (dump_file, "Number of siv tests returning independent: %d\n",
5133 dependence_stats.num_siv_independent);
5134 fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
5135 dependence_stats.num_siv_unimplemented);
5137 fprintf (dump_file, "Number of miv tests: %d\n",
5138 dependence_stats.num_miv);
5139 fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
5140 dependence_stats.num_miv_dependent);
5141 fprintf (dump_file, "Number of miv tests returning independent: %d\n",
5142 dependence_stats.num_miv_independent);
5143 fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
5144 dependence_stats.num_miv_unimplemented);
5148 /* Entry point (for testing only). Analyze all the data references
5149 and the dependence relations in LOOP.
5151 The data references are computed first.
5153 A relation on these nodes is represented by a complete graph. Some
5154 of the relations could be of no interest, thus the relations can be
5157 In the following function we compute all the relations. This is
5158 just a first implementation that is here for:
5159 - for showing how to ask for the dependence relations,
5160 - for the debugging the whole dependence graph,
5161 - for the dejagnu testcases and maintenance.
5163 It is possible to ask only for a part of the graph, avoiding to
5164 compute the whole dependence graph. The computed dependences are
5165 stored in a knowledge base (KB) such that later queries don't
5166 recompute the same information. The implementation of this KB is
5167 transparent to the optimizer, and thus the KB can be changed with a
5168 more efficient implementation, or the KB could be disabled. */
5170 analyze_all_data_dependences (struct loop *loop)
5173 int nb_data_refs = 10;
5174 VEC (data_reference_p, heap) *datarefs =
5175 VEC_alloc (data_reference_p, heap, nb_data_refs);
5176 VEC (ddr_p, heap) *dependence_relations =
5177 VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
5179 /* Compute DDs on the whole function. */
5180 compute_data_dependences_for_loop (loop, false, &datarefs,
5181 &dependence_relations);
5185 dump_data_dependence_relations (dump_file, dependence_relations);
5186 fprintf (dump_file, "\n\n");
5188 if (dump_flags & TDF_DETAILS)
5189 dump_dist_dir_vectors (dump_file, dependence_relations);
5191 if (dump_flags & TDF_STATS)
5193 unsigned nb_top_relations = 0;
5194 unsigned nb_bot_relations = 0;
5195 unsigned nb_basename_differ = 0;
5196 unsigned nb_chrec_relations = 0;
5197 struct data_dependence_relation *ddr;
5199 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
5201 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
5204 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
5206 struct data_reference *a = DDR_A (ddr);
5207 struct data_reference *b = DDR_B (ddr);
5210 if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
5211 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
5212 || (base_object_differ_p (a, b, &differ_p)
5214 nb_basename_differ++;
5220 nb_chrec_relations++;
5223 gather_stats_on_scev_database ();
5227 free_dependence_relations (dependence_relations);
5228 free_data_refs (datarefs);
5231 /* Computes all the data dependences and check that the results of
5232 several analyzers are the same. */
5235 tree_check_data_deps (void)
5238 struct loop *loop_nest;
5240 FOR_EACH_LOOP (li, loop_nest, 0)
5241 analyze_all_data_dependences (loop_nest);
5244 /* Free the memory used by a data dependence relation DDR. */
5247 free_dependence_relation (struct data_dependence_relation *ddr)
5252 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
5253 free_subscripts (DDR_SUBSCRIPTS (ddr));
5258 /* Free the memory used by the data dependence relations from
5259 DEPENDENCE_RELATIONS. */
5262 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
5265 struct data_dependence_relation *ddr;
5266 VEC (loop_p, heap) *loop_nest = NULL;
5268 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
5272 if (loop_nest == NULL)
5273 loop_nest = DDR_LOOP_NEST (ddr);
5275 gcc_assert (DDR_LOOP_NEST (ddr) == NULL
5276 || DDR_LOOP_NEST (ddr) == loop_nest);
5277 free_dependence_relation (ddr);
5281 VEC_free (loop_p, heap, loop_nest);
5282 VEC_free (ddr_p, heap, dependence_relations);
5285 /* Free the memory used by the data references from DATAREFS. */
5288 free_data_refs (VEC (data_reference_p, heap) *datarefs)
5291 struct data_reference *dr;
5293 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
5295 VEC_free (data_reference_p, heap, datarefs);