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 analyze_offset (op0, &invariant_0, &constant_0);
1862 analyze_offset (op1, &invariant_1, &constant_1);
1864 /* Combine the results. */
1865 *constant = constant_0 ? constant_0 : constant_1;
1866 if (invariant_0 && invariant_1)
1868 fold_build2 (code, TREE_TYPE (invariant_0), invariant_0, invariant_1);
1870 *invariant = invariant_0 ? invariant_0 : invariant_1;
1873 /* Free the memory used by the data reference DR. */
1876 free_data_ref (data_reference_p dr)
1878 DR_FREE_ACCESS_FNS (dr);
1882 /* Function create_data_ref.
1884 Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS,
1885 DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO,
1886 DR_MEMTAG, and DR_POINTSTO_INFO fields.
1889 MEMREF - the memory reference that is being analyzed
1890 STMT - the statement that contains MEMREF
1891 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1894 DR (returned value) - data_reference struct for MEMREF
1897 static struct data_reference *
1898 create_data_ref (tree memref, tree stmt, bool is_read)
1900 struct data_reference *dr = NULL;
1901 tree base_address, offset, step, misalign, memtag;
1902 struct loop *loop = loop_containing_stmt (stmt);
1903 tree invariant = NULL_TREE, constant = NULL_TREE;
1904 tree type_size, init_cond;
1905 struct ptr_info_def *ptr_info;
1906 subvar_t subvars = NULL;
1907 tree aligned_to, type = NULL_TREE, orig_offset;
1912 base_address = object_analysis (memref, stmt, is_read, &dr, &offset,
1913 &misalign, &aligned_to, &step, &memtag,
1914 &ptr_info, &subvars);
1915 if (!dr || !base_address)
1917 if (dump_file && (dump_flags & TDF_DETAILS))
1919 fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for ");
1920 print_generic_expr (dump_file, memref, TDF_SLIM);
1921 fprintf (dump_file, "\n");
1926 DR_BASE_ADDRESS (dr) = base_address;
1927 DR_OFFSET (dr) = offset;
1928 DR_INIT (dr) = ssize_int (0);
1929 DR_STEP (dr) = step;
1930 DR_OFFSET_MISALIGNMENT (dr) = misalign;
1931 DR_ALIGNED_TO (dr) = aligned_to;
1932 DR_MEMTAG (dr) = memtag;
1933 DR_PTR_INFO (dr) = ptr_info;
1934 DR_SUBVARS (dr) = subvars;
1936 type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
1938 /* Extract CONSTANT and INVARIANT from OFFSET. */
1939 /* Remove cast from OFFSET and restore it for INVARIANT part. */
1940 orig_offset = offset;
1941 STRIP_NOPS (offset);
1942 if (offset != orig_offset)
1943 type = TREE_TYPE (orig_offset);
1944 analyze_offset (offset, &invariant, &constant);
1945 if (type && invariant)
1946 invariant = fold_convert (type, invariant);
1948 /* Put CONSTANT part of OFFSET in DR_INIT and INVARIANT in DR_OFFSET field
1952 DR_INIT (dr) = fold_convert (ssizetype, constant);
1953 init_cond = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (constant),
1954 constant, type_size);
1957 DR_INIT (dr) = init_cond = ssize_int (0);
1960 DR_OFFSET (dr) = invariant;
1962 DR_OFFSET (dr) = ssize_int (0);
1964 /* Change the access function for INIDIRECT_REFs, according to
1965 DR_BASE_ADDRESS. Analyze OFFSET calculated in object_analysis. OFFSET is
1966 an expression that can contain loop invariant expressions and constants.
1967 We put the constant part in the initial condition of the access function
1968 (for data dependence tests), and in DR_INIT of the data-ref. The loop
1969 invariant part is put in DR_OFFSET.
1970 The evolution part of the access function is STEP calculated in
1971 object_analysis divided by the size of data type.
1973 if (!DR_BASE_OBJECT (dr)
1974 || (TREE_CODE (memref) == COMPONENT_REF && DR_NUM_DIMENSIONS (dr) == 1))
1979 /* Update access function. */
1980 access_fn = DR_ACCESS_FN (dr, 0);
1981 if (automatically_generated_chrec_p (access_fn))
1987 new_step = size_binop (TRUNC_DIV_EXPR,
1988 fold_convert (ssizetype, step), type_size);
1990 init_cond = chrec_convert (chrec_type (access_fn), init_cond, stmt);
1991 new_step = chrec_convert (chrec_type (access_fn), new_step, stmt);
1992 if (automatically_generated_chrec_p (init_cond)
1993 || automatically_generated_chrec_p (new_step))
1998 access_fn = chrec_replace_initial_condition (access_fn, init_cond);
1999 access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step);
2001 VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn);
2004 if (dump_file && (dump_flags & TDF_DETAILS))
2006 struct ptr_info_def *pi = DR_PTR_INFO (dr);
2008 fprintf (dump_file, "\nCreated dr for ");
2009 print_generic_expr (dump_file, memref, TDF_SLIM);
2010 fprintf (dump_file, "\n\tbase_address: ");
2011 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
2012 fprintf (dump_file, "\n\toffset from base address: ");
2013 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
2014 fprintf (dump_file, "\n\tconstant offset from base address: ");
2015 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
2016 fprintf (dump_file, "\n\tbase_object: ");
2017 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
2018 fprintf (dump_file, "\n\tstep: ");
2019 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
2020 fprintf (dump_file, "B\n\tmisalignment from base: ");
2021 print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM);
2022 if (DR_OFFSET_MISALIGNMENT (dr))
2023 fprintf (dump_file, "B");
2024 if (DR_ALIGNED_TO (dr))
2026 fprintf (dump_file, "\n\taligned to: ");
2027 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
2029 fprintf (dump_file, "\n\tmemtag: ");
2030 print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM);
2031 fprintf (dump_file, "\n");
2032 if (pi && pi->name_mem_tag)
2034 fprintf (dump_file, "\n\tnametag: ");
2035 print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM);
2036 fprintf (dump_file, "\n");
2042 /* Returns true if FNA == FNB. */
2045 affine_function_equal_p (affine_fn fna, affine_fn fnb)
2047 unsigned i, n = VEC_length (tree, fna);
2049 gcc_assert (n == VEC_length (tree, fnb));
2051 for (i = 0; i < n; i++)
2052 if (!operand_equal_p (VEC_index (tree, fna, i),
2053 VEC_index (tree, fnb, i), 0))
2059 /* If all the functions in CF are the same, returns one of them,
2060 otherwise returns NULL. */
2063 common_affine_function (conflict_function *cf)
2068 if (!CF_NONTRIVIAL_P (cf))
2073 for (i = 1; i < cf->n; i++)
2074 if (!affine_function_equal_p (comm, cf->fns[i]))
2080 /* Returns the base of the affine function FN. */
2083 affine_function_base (affine_fn fn)
2085 return VEC_index (tree, fn, 0);
2088 /* Returns true if FN is a constant. */
2091 affine_function_constant_p (affine_fn fn)
2096 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
2097 if (!integer_zerop (coef))
2103 /* Applies operation OP on affine functions FNA and FNB, and returns the
2107 affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
2113 if (VEC_length (tree, fnb) > VEC_length (tree, fna))
2115 n = VEC_length (tree, fna);
2116 m = VEC_length (tree, fnb);
2120 n = VEC_length (tree, fnb);
2121 m = VEC_length (tree, fna);
2124 ret = VEC_alloc (tree, heap, m);
2125 for (i = 0; i < n; i++)
2126 VEC_quick_push (tree, ret,
2127 fold_build2 (op, integer_type_node,
2128 VEC_index (tree, fna, i),
2129 VEC_index (tree, fnb, i)));
2131 for (; VEC_iterate (tree, fna, i, coef); i++)
2132 VEC_quick_push (tree, ret,
2133 fold_build2 (op, integer_type_node,
2134 coef, integer_zero_node));
2135 for (; VEC_iterate (tree, fnb, i, coef); i++)
2136 VEC_quick_push (tree, ret,
2137 fold_build2 (op, integer_type_node,
2138 integer_zero_node, coef));
2143 /* Returns the sum of affine functions FNA and FNB. */
2146 affine_fn_plus (affine_fn fna, affine_fn fnb)
2148 return affine_fn_op (PLUS_EXPR, fna, fnb);
2151 /* Returns the difference of affine functions FNA and FNB. */
2154 affine_fn_minus (affine_fn fna, affine_fn fnb)
2156 return affine_fn_op (MINUS_EXPR, fna, fnb);
2159 /* Frees affine function FN. */
2162 affine_fn_free (affine_fn fn)
2164 VEC_free (tree, heap, fn);
2167 /* Determine for each subscript in the data dependence relation DDR
2171 compute_subscript_distance (struct data_dependence_relation *ddr)
2173 conflict_function *cf_a, *cf_b;
2174 affine_fn fn_a, fn_b, diff;
2176 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
2180 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2182 struct subscript *subscript;
2184 subscript = DDR_SUBSCRIPT (ddr, i);
2185 cf_a = SUB_CONFLICTS_IN_A (subscript);
2186 cf_b = SUB_CONFLICTS_IN_B (subscript);
2188 fn_a = common_affine_function (cf_a);
2189 fn_b = common_affine_function (cf_b);
2192 SUB_DISTANCE (subscript) = chrec_dont_know;
2195 diff = affine_fn_minus (fn_a, fn_b);
2197 if (affine_function_constant_p (diff))
2198 SUB_DISTANCE (subscript) = affine_function_base (diff);
2200 SUB_DISTANCE (subscript) = chrec_dont_know;
2202 affine_fn_free (diff);
2207 /* Returns the conflict function for "unknown". */
2209 static conflict_function *
2210 conflict_fn_not_known (void)
2212 conflict_function *fn = XCNEW (conflict_function);
2218 /* Returns the conflict function for "independent". */
2220 static conflict_function *
2221 conflict_fn_no_dependence (void)
2223 conflict_function *fn = XCNEW (conflict_function);
2224 fn->n = NO_DEPENDENCE;
2229 /* Initialize a data dependence relation between data accesses A and
2230 B. NB_LOOPS is the number of loops surrounding the references: the
2231 size of the classic distance/direction vectors. */
2233 static struct data_dependence_relation *
2234 initialize_data_dependence_relation (struct data_reference *a,
2235 struct data_reference *b,
2236 VEC (loop_p, heap) *loop_nest)
2238 struct data_dependence_relation *res;
2239 bool differ_p, known_dependence;
2242 res = XNEW (struct data_dependence_relation);
2245 DDR_LOOP_NEST (res) = NULL;
2247 if (a == NULL || b == NULL)
2249 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
2253 /* When A and B are arrays and their dimensions differ, we directly
2254 initialize the relation to "there is no dependence": chrec_known. */
2255 if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
2256 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
2258 DDR_ARE_DEPENDENT (res) = chrec_known;
2262 if (DR_BASE_ADDRESS (a) && DR_BASE_ADDRESS (b))
2263 known_dependence = base_addr_differ_p (a, b, &differ_p);
2265 known_dependence = base_object_differ_p (a, b, &differ_p);
2267 if (!known_dependence)
2269 /* Can't determine whether the data-refs access the same memory
2271 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
2277 DDR_ARE_DEPENDENT (res) = chrec_known;
2281 DDR_AFFINE_P (res) = true;
2282 DDR_ARE_DEPENDENT (res) = NULL_TREE;
2283 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
2284 DDR_LOOP_NEST (res) = loop_nest;
2285 DDR_INNER_LOOP (res) = 0;
2286 DDR_DIR_VECTS (res) = NULL;
2287 DDR_DIST_VECTS (res) = NULL;
2289 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
2291 struct subscript *subscript;
2293 subscript = XNEW (struct subscript);
2294 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
2295 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
2296 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
2297 SUB_DISTANCE (subscript) = chrec_dont_know;
2298 VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
2304 /* Frees memory used by the conflict function F. */
2307 free_conflict_function (conflict_function *f)
2311 if (CF_NONTRIVIAL_P (f))
2313 for (i = 0; i < f->n; i++)
2314 affine_fn_free (f->fns[i]);
2319 /* Frees memory used by SUBSCRIPTS. */
2322 free_subscripts (VEC (subscript_p, heap) *subscripts)
2327 for (i = 0; VEC_iterate (subscript_p, subscripts, i, s); i++)
2329 free_conflict_function (s->conflicting_iterations_in_a);
2330 free_conflict_function (s->conflicting_iterations_in_b);
2332 VEC_free (subscript_p, heap, subscripts);
2335 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
2339 finalize_ddr_dependent (struct data_dependence_relation *ddr,
2342 if (dump_file && (dump_flags & TDF_DETAILS))
2344 fprintf (dump_file, "(dependence classified: ");
2345 print_generic_expr (dump_file, chrec, 0);
2346 fprintf (dump_file, ")\n");
2349 DDR_ARE_DEPENDENT (ddr) = chrec;
2350 free_subscripts (DDR_SUBSCRIPTS (ddr));
2353 /* The dependence relation DDR cannot be represented by a distance
2357 non_affine_dependence_relation (struct data_dependence_relation *ddr)
2359 if (dump_file && (dump_flags & TDF_DETAILS))
2360 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
2362 DDR_AFFINE_P (ddr) = false;
2367 /* This section contains the classic Banerjee tests. */
2369 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
2370 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
2373 ziv_subscript_p (tree chrec_a,
2376 return (evolution_function_is_constant_p (chrec_a)
2377 && evolution_function_is_constant_p (chrec_b));
2380 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
2381 variable, i.e., if the SIV (Single Index Variable) test is true. */
2384 siv_subscript_p (tree chrec_a,
2387 if ((evolution_function_is_constant_p (chrec_a)
2388 && evolution_function_is_univariate_p (chrec_b))
2389 || (evolution_function_is_constant_p (chrec_b)
2390 && evolution_function_is_univariate_p (chrec_a)))
2393 if (evolution_function_is_univariate_p (chrec_a)
2394 && evolution_function_is_univariate_p (chrec_b))
2396 switch (TREE_CODE (chrec_a))
2398 case POLYNOMIAL_CHREC:
2399 switch (TREE_CODE (chrec_b))
2401 case POLYNOMIAL_CHREC:
2402 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
2417 /* Creates a conflict function with N dimensions. The affine functions
2418 in each dimension follow. */
2420 static conflict_function *
2421 conflict_fn (unsigned n, ...)
2424 conflict_function *ret = XCNEW (conflict_function);
2427 gcc_assert (0 < n && n <= MAX_DIM);
2431 for (i = 0; i < n; i++)
2432 ret->fns[i] = va_arg (ap, affine_fn);
2438 /* Returns constant affine function with value CST. */
2441 affine_fn_cst (tree cst)
2443 affine_fn fn = VEC_alloc (tree, heap, 1);
2444 VEC_quick_push (tree, fn, cst);
2448 /* Returns affine function with single variable, CST + COEF * x_DIM. */
2451 affine_fn_univar (tree cst, unsigned dim, tree coef)
2453 affine_fn fn = VEC_alloc (tree, heap, dim + 1);
2456 gcc_assert (dim > 0);
2457 VEC_quick_push (tree, fn, cst);
2458 for (i = 1; i < dim; i++)
2459 VEC_quick_push (tree, fn, integer_zero_node);
2460 VEC_quick_push (tree, fn, coef);
2464 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
2465 *OVERLAPS_B are initialized to the functions that describe the
2466 relation between the elements accessed twice by CHREC_A and
2467 CHREC_B. For k >= 0, the following property is verified:
2469 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2472 analyze_ziv_subscript (tree chrec_a,
2474 conflict_function **overlaps_a,
2475 conflict_function **overlaps_b,
2476 tree *last_conflicts)
2479 dependence_stats.num_ziv++;
2481 if (dump_file && (dump_flags & TDF_DETAILS))
2482 fprintf (dump_file, "(analyze_ziv_subscript \n");
2484 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
2485 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
2486 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2488 switch (TREE_CODE (difference))
2491 if (integer_zerop (difference))
2493 /* The difference is equal to zero: the accessed index
2494 overlaps for each iteration in the loop. */
2495 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2496 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2497 *last_conflicts = chrec_dont_know;
2498 dependence_stats.num_ziv_dependent++;
2502 /* The accesses do not overlap. */
2503 *overlaps_a = conflict_fn_no_dependence ();
2504 *overlaps_b = conflict_fn_no_dependence ();
2505 *last_conflicts = integer_zero_node;
2506 dependence_stats.num_ziv_independent++;
2511 /* We're not sure whether the indexes overlap. For the moment,
2512 conservatively answer "don't know". */
2513 if (dump_file && (dump_flags & TDF_DETAILS))
2514 fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
2516 *overlaps_a = conflict_fn_not_known ();
2517 *overlaps_b = conflict_fn_not_known ();
2518 *last_conflicts = chrec_dont_know;
2519 dependence_stats.num_ziv_unimplemented++;
2523 if (dump_file && (dump_flags & TDF_DETAILS))
2524 fprintf (dump_file, ")\n");
2527 /* Sets NIT to the estimated number of executions of the statements in
2528 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
2529 large as the number of iterations. If we have no reliable estimate,
2530 the function returns false, otherwise returns true. */
2533 estimated_loop_iterations (struct loop *loop, bool conservative,
2536 tree numiter = number_of_exit_cond_executions (loop);
2538 /* If we have an exact value, use it. */
2539 if (TREE_CODE (numiter) == INTEGER_CST)
2541 *nit = tree_to_double_int (numiter);
2545 /* If we have a measured profile and we do not ask for a conservative bound,
2547 if (!conservative && loop->header->count != 0)
2549 *nit = uhwi_to_double_int (expected_loop_iterations (loop) + 1);
2553 /* Finally, try using a reliable estimate on number of iterations according
2554 to the size of the accessed data, if available. */
2555 estimate_numbers_of_iterations_loop (loop);
2556 if (loop->estimate_state == EST_AVAILABLE)
2558 *nit = loop->estimated_nb_iterations;
2565 /* Similar to estimated_loop_iterations, but returns the estimate only
2566 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
2567 on the number of iterations of LOOP could not be derived, returns -1. */
2570 estimated_loop_iterations_int (struct loop *loop, bool conservative)
2573 HOST_WIDE_INT hwi_nit;
2575 if (!estimated_loop_iterations (loop, conservative, &nit))
2578 if (!double_int_fits_in_shwi_p (nit))
2580 hwi_nit = double_int_to_shwi (nit);
2582 return hwi_nit < 0 ? -1 : hwi_nit;
2585 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
2586 and only if it fits to the int type. If this is not the case, or the
2587 estimate on the number of iterations of LOOP could not be derived, returns
2591 estimated_loop_iterations_tree (struct loop *loop, bool conservative)
2596 if (!estimated_loop_iterations (loop, conservative, &nit))
2597 return chrec_dont_know;
2599 type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
2600 if (!double_int_fits_to_tree_p (type, nit))
2601 return chrec_dont_know;
2603 return double_int_to_tree (type, nit);
2606 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2607 constant, and CHREC_B is an affine function. *OVERLAPS_A and
2608 *OVERLAPS_B are initialized to the functions that describe the
2609 relation between the elements accessed twice by CHREC_A and
2610 CHREC_B. For k >= 0, the following property is verified:
2612 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2615 analyze_siv_subscript_cst_affine (tree chrec_a,
2617 conflict_function **overlaps_a,
2618 conflict_function **overlaps_b,
2619 tree *last_conflicts)
2621 bool value0, value1, value2;
2622 tree difference, tmp;
2624 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
2625 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
2626 difference = chrec_fold_minus
2627 (integer_type_node, initial_condition (chrec_b), chrec_a);
2629 if (!chrec_is_positive (initial_condition (difference), &value0))
2631 if (dump_file && (dump_flags & TDF_DETAILS))
2632 fprintf (dump_file, "siv test failed: chrec is not positive.\n");
2634 dependence_stats.num_siv_unimplemented++;
2635 *overlaps_a = conflict_fn_not_known ();
2636 *overlaps_b = conflict_fn_not_known ();
2637 *last_conflicts = chrec_dont_know;
2642 if (value0 == false)
2644 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
2646 if (dump_file && (dump_flags & TDF_DETAILS))
2647 fprintf (dump_file, "siv test failed: chrec not positive.\n");
2649 *overlaps_a = conflict_fn_not_known ();
2650 *overlaps_b = conflict_fn_not_known ();
2651 *last_conflicts = chrec_dont_know;
2652 dependence_stats.num_siv_unimplemented++;
2661 chrec_b = {10, +, 1}
2664 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2666 HOST_WIDE_INT numiter;
2667 struct loop *loop = get_chrec_loop (chrec_b);
2669 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2670 tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
2671 fold_build1 (ABS_EXPR,
2674 CHREC_RIGHT (chrec_b));
2675 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
2676 *last_conflicts = integer_one_node;
2679 /* Perform weak-zero siv test to see if overlap is
2680 outside the loop bounds. */
2681 numiter = estimated_loop_iterations_int (loop, true);
2684 && compare_tree_int (tmp, numiter) > 0)
2686 free_conflict_function (*overlaps_a);
2687 free_conflict_function (*overlaps_b);
2688 *overlaps_a = conflict_fn_no_dependence ();
2689 *overlaps_b = conflict_fn_no_dependence ();
2690 *last_conflicts = integer_zero_node;
2691 dependence_stats.num_siv_independent++;
2694 dependence_stats.num_siv_dependent++;
2698 /* When the step does not divide the difference, there are
2702 *overlaps_a = conflict_fn_no_dependence ();
2703 *overlaps_b = conflict_fn_no_dependence ();
2704 *last_conflicts = integer_zero_node;
2705 dependence_stats.num_siv_independent++;
2714 chrec_b = {10, +, -1}
2716 In this case, chrec_a will not overlap with chrec_b. */
2717 *overlaps_a = conflict_fn_no_dependence ();
2718 *overlaps_b = conflict_fn_no_dependence ();
2719 *last_conflicts = integer_zero_node;
2720 dependence_stats.num_siv_independent++;
2727 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
2729 if (dump_file && (dump_flags & TDF_DETAILS))
2730 fprintf (dump_file, "siv test failed: chrec not positive.\n");
2732 *overlaps_a = conflict_fn_not_known ();
2733 *overlaps_b = conflict_fn_not_known ();
2734 *last_conflicts = chrec_dont_know;
2735 dependence_stats.num_siv_unimplemented++;
2740 if (value2 == false)
2744 chrec_b = {10, +, -1}
2746 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2748 HOST_WIDE_INT numiter;
2749 struct loop *loop = get_chrec_loop (chrec_b);
2751 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2752 tmp = fold_build2 (EXACT_DIV_EXPR,
2753 integer_type_node, difference,
2754 CHREC_RIGHT (chrec_b));
2755 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
2756 *last_conflicts = integer_one_node;
2758 /* Perform weak-zero siv test to see if overlap is
2759 outside the loop bounds. */
2760 numiter = estimated_loop_iterations_int (loop, true);
2763 && compare_tree_int (tmp, numiter) > 0)
2765 free_conflict_function (*overlaps_a);
2766 free_conflict_function (*overlaps_b);
2767 *overlaps_a = conflict_fn_no_dependence ();
2768 *overlaps_b = conflict_fn_no_dependence ();
2769 *last_conflicts = integer_zero_node;
2770 dependence_stats.num_siv_independent++;
2773 dependence_stats.num_siv_dependent++;
2777 /* When the step does not divide the difference, there
2781 *overlaps_a = conflict_fn_no_dependence ();
2782 *overlaps_b = conflict_fn_no_dependence ();
2783 *last_conflicts = integer_zero_node;
2784 dependence_stats.num_siv_independent++;
2794 In this case, chrec_a will not overlap with chrec_b. */
2795 *overlaps_a = conflict_fn_no_dependence ();
2796 *overlaps_b = conflict_fn_no_dependence ();
2797 *last_conflicts = integer_zero_node;
2798 dependence_stats.num_siv_independent++;
2806 /* Helper recursive function for initializing the matrix A. Returns
2807 the initial value of CHREC. */
2810 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2814 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2815 return int_cst_value (chrec);
2817 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2818 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2821 #define FLOOR_DIV(x,y) ((x) / (y))
2823 /* Solves the special case of the Diophantine equation:
2824 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2826 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2827 number of iterations that loops X and Y run. The overlaps will be
2828 constructed as evolutions in dimension DIM. */
2831 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
2832 affine_fn *overlaps_a,
2833 affine_fn *overlaps_b,
2834 tree *last_conflicts, int dim)
2836 if (((step_a > 0 && step_b > 0)
2837 || (step_a < 0 && step_b < 0)))
2839 int step_overlaps_a, step_overlaps_b;
2840 int gcd_steps_a_b, last_conflict, tau2;
2842 gcd_steps_a_b = gcd (step_a, step_b);
2843 step_overlaps_a = step_b / gcd_steps_a_b;
2844 step_overlaps_b = step_a / gcd_steps_a_b;
2846 tau2 = FLOOR_DIV (niter, step_overlaps_a);
2847 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2848 last_conflict = tau2;
2850 *overlaps_a = affine_fn_univar (integer_zero_node, dim,
2851 build_int_cst (NULL_TREE,
2853 *overlaps_b = affine_fn_univar (integer_zero_node, dim,
2854 build_int_cst (NULL_TREE,
2856 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2861 *overlaps_a = affine_fn_cst (integer_zero_node);
2862 *overlaps_b = affine_fn_cst (integer_zero_node);
2863 *last_conflicts = integer_zero_node;
2867 /* Solves the special case of a Diophantine equation where CHREC_A is
2868 an affine bivariate function, and CHREC_B is an affine univariate
2869 function. For example,
2871 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2873 has the following overlapping functions:
2875 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2876 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2877 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2879 FORNOW: This is a specialized implementation for a case occurring in
2880 a common benchmark. Implement the general algorithm. */
2883 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2884 conflict_function **overlaps_a,
2885 conflict_function **overlaps_b,
2886 tree *last_conflicts)
2888 bool xz_p, yz_p, xyz_p;
2889 int step_x, step_y, step_z;
2890 HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
2891 affine_fn overlaps_a_xz, overlaps_b_xz;
2892 affine_fn overlaps_a_yz, overlaps_b_yz;
2893 affine_fn overlaps_a_xyz, overlaps_b_xyz;
2894 affine_fn ova1, ova2, ovb;
2895 tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
2897 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2898 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2899 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2901 niter_x = estimated_loop_iterations_int
2902 (get_chrec_loop (CHREC_LEFT (chrec_a)), true);
2903 niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), true);
2904 niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), true);
2906 if (niter_x < 0 || niter_y < 0 || niter_z < 0)
2908 if (dump_file && (dump_flags & TDF_DETAILS))
2909 fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
2911 *overlaps_a = conflict_fn_not_known ();
2912 *overlaps_b = conflict_fn_not_known ();
2913 *last_conflicts = chrec_dont_know;
2917 niter = MIN (niter_x, niter_z);
2918 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2921 &last_conflicts_xz, 1);
2922 niter = MIN (niter_y, niter_z);
2923 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2926 &last_conflicts_yz, 2);
2927 niter = MIN (niter_x, niter_z);
2928 niter = MIN (niter_y, niter);
2929 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2932 &last_conflicts_xyz, 3);
2934 xz_p = !integer_zerop (last_conflicts_xz);
2935 yz_p = !integer_zerop (last_conflicts_yz);
2936 xyz_p = !integer_zerop (last_conflicts_xyz);
2938 if (xz_p || yz_p || xyz_p)
2940 ova1 = affine_fn_cst (integer_zero_node);
2941 ova2 = affine_fn_cst (integer_zero_node);
2942 ovb = affine_fn_cst (integer_zero_node);
2945 affine_fn t0 = ova1;
2948 ova1 = affine_fn_plus (ova1, overlaps_a_xz);
2949 ovb = affine_fn_plus (ovb, overlaps_b_xz);
2950 affine_fn_free (t0);
2951 affine_fn_free (t2);
2952 *last_conflicts = last_conflicts_xz;
2956 affine_fn t0 = ova2;
2959 ova2 = affine_fn_plus (ova2, overlaps_a_yz);
2960 ovb = affine_fn_plus (ovb, overlaps_b_yz);
2961 affine_fn_free (t0);
2962 affine_fn_free (t2);
2963 *last_conflicts = last_conflicts_yz;
2967 affine_fn t0 = ova1;
2968 affine_fn t2 = ova2;
2971 ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
2972 ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
2973 ovb = affine_fn_plus (ovb, overlaps_b_xyz);
2974 affine_fn_free (t0);
2975 affine_fn_free (t2);
2976 affine_fn_free (t4);
2977 *last_conflicts = last_conflicts_xyz;
2979 *overlaps_a = conflict_fn (2, ova1, ova2);
2980 *overlaps_b = conflict_fn (1, ovb);
2984 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2985 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2986 *last_conflicts = integer_zero_node;
2989 affine_fn_free (overlaps_a_xz);
2990 affine_fn_free (overlaps_b_xz);
2991 affine_fn_free (overlaps_a_yz);
2992 affine_fn_free (overlaps_b_yz);
2993 affine_fn_free (overlaps_a_xyz);
2994 affine_fn_free (overlaps_b_xyz);
2997 /* Determines the overlapping elements due to accesses CHREC_A and
2998 CHREC_B, that are affine functions. This function cannot handle
2999 symbolic evolution functions, ie. when initial conditions are
3000 parameters, because it uses lambda matrices of integers. */
3003 analyze_subscript_affine_affine (tree chrec_a,
3005 conflict_function **overlaps_a,
3006 conflict_function **overlaps_b,
3007 tree *last_conflicts)
3009 unsigned nb_vars_a, nb_vars_b, dim;
3010 int init_a, init_b, gamma, gcd_alpha_beta;
3012 lambda_matrix A, U, S;
3014 if (eq_evolutions_p (chrec_a, chrec_b))
3016 /* The accessed index overlaps for each iteration in the
3018 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
3019 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
3020 *last_conflicts = chrec_dont_know;
3023 if (dump_file && (dump_flags & TDF_DETAILS))
3024 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
3026 /* For determining the initial intersection, we have to solve a
3027 Diophantine equation. This is the most time consuming part.
3029 For answering to the question: "Is there a dependence?" we have
3030 to prove that there exists a solution to the Diophantine
3031 equation, and that the solution is in the iteration domain,
3032 i.e. the solution is positive or zero, and that the solution
3033 happens before the upper bound loop.nb_iterations. Otherwise
3034 there is no dependence. This function outputs a description of
3035 the iterations that hold the intersections. */
3037 nb_vars_a = nb_vars_in_chrec (chrec_a);
3038 nb_vars_b = nb_vars_in_chrec (chrec_b);
3040 dim = nb_vars_a + nb_vars_b;
3041 U = lambda_matrix_new (dim, dim);
3042 A = lambda_matrix_new (dim, 1);
3043 S = lambda_matrix_new (dim, 1);
3045 init_a = initialize_matrix_A (A, chrec_a, 0, 1);
3046 init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
3047 gamma = init_b - init_a;
3049 /* Don't do all the hard work of solving the Diophantine equation
3050 when we already know the solution: for example,
3053 | gamma = 3 - 3 = 0.
3054 Then the first overlap occurs during the first iterations:
3055 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
3059 if (nb_vars_a == 1 && nb_vars_b == 1)
3062 HOST_WIDE_INT niter, niter_a, niter_b;
3065 niter_a = estimated_loop_iterations_int
3066 (get_chrec_loop (chrec_a), true);
3067 niter_b = estimated_loop_iterations_int
3068 (get_chrec_loop (chrec_b), true);
3069 if (niter_a < 0 || niter_b < 0)
3071 if (dump_file && (dump_flags & TDF_DETAILS))
3072 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
3073 *overlaps_a = conflict_fn_not_known ();
3074 *overlaps_b = conflict_fn_not_known ();
3075 *last_conflicts = chrec_dont_know;
3076 goto end_analyze_subs_aa;
3079 niter = MIN (niter_a, niter_b);
3081 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
3082 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
3084 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
3087 *overlaps_a = conflict_fn (1, ova);
3088 *overlaps_b = conflict_fn (1, ovb);
3091 else if (nb_vars_a == 2 && nb_vars_b == 1)
3092 compute_overlap_steps_for_affine_1_2
3093 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
3095 else if (nb_vars_a == 1 && nb_vars_b == 2)
3096 compute_overlap_steps_for_affine_1_2
3097 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
3101 if (dump_file && (dump_flags & TDF_DETAILS))
3102 fprintf (dump_file, "affine-affine test failed: too many variables.\n");
3103 *overlaps_a = conflict_fn_not_known ();
3104 *overlaps_b = conflict_fn_not_known ();
3105 *last_conflicts = chrec_dont_know;
3107 goto end_analyze_subs_aa;
3111 lambda_matrix_right_hermite (A, dim, 1, S, U);
3116 lambda_matrix_row_negate (U, dim, 0);
3118 gcd_alpha_beta = S[0][0];
3120 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
3121 but that is a quite strange case. Instead of ICEing, answer
3123 if (gcd_alpha_beta == 0)
3125 *overlaps_a = conflict_fn_not_known ();
3126 *overlaps_b = conflict_fn_not_known ();
3127 *last_conflicts = chrec_dont_know;
3128 goto end_analyze_subs_aa;
3131 /* The classic "gcd-test". */
3132 if (!int_divides_p (gcd_alpha_beta, gamma))
3134 /* The "gcd-test" has determined that there is no integer
3135 solution, i.e. there is no dependence. */
3136 *overlaps_a = conflict_fn_no_dependence ();
3137 *overlaps_b = conflict_fn_no_dependence ();
3138 *last_conflicts = integer_zero_node;
3141 /* Both access functions are univariate. This includes SIV and MIV cases. */
3142 else if (nb_vars_a == 1 && nb_vars_b == 1)
3144 /* Both functions should have the same evolution sign. */
3145 if (((A[0][0] > 0 && -A[1][0] > 0)
3146 || (A[0][0] < 0 && -A[1][0] < 0)))
3148 /* The solutions are given by:
3150 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
3153 For a given integer t. Using the following variables,
3155 | i0 = u11 * gamma / gcd_alpha_beta
3156 | j0 = u12 * gamma / gcd_alpha_beta
3163 | y0 = j0 + j1 * t. */
3167 /* X0 and Y0 are the first iterations for which there is a
3168 dependence. X0, Y0 are two solutions of the Diophantine
3169 equation: chrec_a (X0) = chrec_b (Y0). */
3171 int niter, niter_a, niter_b;
3173 niter_a = estimated_loop_iterations_int
3174 (get_chrec_loop (chrec_a), true);
3175 niter_b = estimated_loop_iterations_int
3176 (get_chrec_loop (chrec_b), true);
3178 if (niter_a < 0 || niter_b < 0)
3180 if (dump_file && (dump_flags & TDF_DETAILS))
3181 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
3182 *overlaps_a = conflict_fn_not_known ();
3183 *overlaps_b = conflict_fn_not_known ();
3184 *last_conflicts = chrec_dont_know;
3185 goto end_analyze_subs_aa;
3188 niter = MIN (niter_a, niter_b);
3190 i0 = U[0][0] * gamma / gcd_alpha_beta;
3191 j0 = U[0][1] * gamma / gcd_alpha_beta;
3195 if ((i1 == 0 && i0 < 0)
3196 || (j1 == 0 && j0 < 0))
3198 /* There is no solution.
3199 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
3200 falls in here, but for the moment we don't look at the
3201 upper bound of the iteration domain. */
3202 *overlaps_a = conflict_fn_no_dependence ();
3203 *overlaps_b = conflict_fn_no_dependence ();
3204 *last_conflicts = integer_zero_node;
3211 tau1 = CEIL (-i0, i1);
3212 tau2 = FLOOR_DIV (niter - i0, i1);
3216 int last_conflict, min_multiple;
3217 tau1 = MAX (tau1, CEIL (-j0, j1));
3218 tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
3220 x0 = i1 * tau1 + i0;
3221 y0 = j1 * tau1 + j0;
3223 /* At this point (x0, y0) is one of the
3224 solutions to the Diophantine equation. The
3225 next step has to compute the smallest
3226 positive solution: the first conflicts. */
3227 min_multiple = MIN (x0 / i1, y0 / j1);
3228 x0 -= i1 * min_multiple;
3229 y0 -= j1 * min_multiple;
3231 tau1 = (x0 - i0)/i1;
3232 last_conflict = tau2 - tau1;
3234 /* If the overlap occurs outside of the bounds of the
3235 loop, there is no dependence. */
3236 if (x0 > niter || y0 > niter)
3238 *overlaps_a = conflict_fn_no_dependence ();
3239 *overlaps_b = conflict_fn_no_dependence ();
3240 *last_conflicts = integer_zero_node;
3246 affine_fn_univar (build_int_cst (NULL_TREE, x0),
3248 build_int_cst (NULL_TREE, i1)));
3251 affine_fn_univar (build_int_cst (NULL_TREE, y0),
3253 build_int_cst (NULL_TREE, j1)));
3254 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
3259 /* FIXME: For the moment, the upper bound of the
3260 iteration domain for j is not checked. */
3261 if (dump_file && (dump_flags & TDF_DETAILS))
3262 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3263 *overlaps_a = conflict_fn_not_known ();
3264 *overlaps_b = conflict_fn_not_known ();
3265 *last_conflicts = chrec_dont_know;
3271 /* FIXME: For the moment, the upper bound of the
3272 iteration domain for i is not checked. */
3273 if (dump_file && (dump_flags & TDF_DETAILS))
3274 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3275 *overlaps_a = conflict_fn_not_known ();
3276 *overlaps_b = conflict_fn_not_known ();
3277 *last_conflicts = chrec_dont_know;
3283 if (dump_file && (dump_flags & TDF_DETAILS))
3284 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3285 *overlaps_a = conflict_fn_not_known ();
3286 *overlaps_b = conflict_fn_not_known ();
3287 *last_conflicts = chrec_dont_know;
3293 if (dump_file && (dump_flags & TDF_DETAILS))
3294 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3295 *overlaps_a = conflict_fn_not_known ();
3296 *overlaps_b = conflict_fn_not_known ();
3297 *last_conflicts = chrec_dont_know;
3300 end_analyze_subs_aa:
3301 if (dump_file && (dump_flags & TDF_DETAILS))
3303 fprintf (dump_file, " (overlaps_a = ");
3304 dump_conflict_function (dump_file, *overlaps_a);
3305 fprintf (dump_file, ")\n (overlaps_b = ");
3306 dump_conflict_function (dump_file, *overlaps_b);
3307 fprintf (dump_file, ")\n");
3308 fprintf (dump_file, ")\n");
3312 /* Returns true when analyze_subscript_affine_affine can be used for
3313 determining the dependence relation between chrec_a and chrec_b,
3314 that contain symbols. This function modifies chrec_a and chrec_b
3315 such that the analysis result is the same, and such that they don't
3316 contain symbols, and then can safely be passed to the analyzer.
3318 Example: The analysis of the following tuples of evolutions produce
3319 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
3322 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
3323 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
3327 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
3329 tree diff, type, left_a, left_b, right_b;
3331 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
3332 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
3333 /* FIXME: For the moment not handled. Might be refined later. */
3336 type = chrec_type (*chrec_a);
3337 left_a = CHREC_LEFT (*chrec_a);
3338 left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE);
3339 diff = chrec_fold_minus (type, left_a, left_b);
3341 if (!evolution_function_is_constant_p (diff))
3344 if (dump_file && (dump_flags & TDF_DETAILS))
3345 fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
3347 *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
3348 diff, CHREC_RIGHT (*chrec_a));
3349 right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE);
3350 *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
3351 build_int_cst (type, 0),
3356 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
3357 *OVERLAPS_B are initialized to the functions that describe the
3358 relation between the elements accessed twice by CHREC_A and
3359 CHREC_B. For k >= 0, the following property is verified:
3361 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
3364 analyze_siv_subscript (tree chrec_a,
3366 conflict_function **overlaps_a,
3367 conflict_function **overlaps_b,
3368 tree *last_conflicts)
3370 dependence_stats.num_siv++;
3372 if (dump_file && (dump_flags & TDF_DETAILS))
3373 fprintf (dump_file, "(analyze_siv_subscript \n");
3375 if (evolution_function_is_constant_p (chrec_a)
3376 && evolution_function_is_affine_p (chrec_b))
3377 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
3378 overlaps_a, overlaps_b, last_conflicts);
3380 else if (evolution_function_is_affine_p (chrec_a)
3381 && evolution_function_is_constant_p (chrec_b))
3382 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
3383 overlaps_b, overlaps_a, last_conflicts);
3385 else if (evolution_function_is_affine_p (chrec_a)
3386 && evolution_function_is_affine_p (chrec_b))
3388 if (!chrec_contains_symbols (chrec_a)
3389 && !chrec_contains_symbols (chrec_b))
3391 analyze_subscript_affine_affine (chrec_a, chrec_b,
3392 overlaps_a, overlaps_b,
3395 if (CF_NOT_KNOWN_P (*overlaps_a)
3396 || CF_NOT_KNOWN_P (*overlaps_b))
3397 dependence_stats.num_siv_unimplemented++;
3398 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
3399 || CF_NO_DEPENDENCE_P (*overlaps_b))
3400 dependence_stats.num_siv_independent++;
3402 dependence_stats.num_siv_dependent++;
3404 else if (can_use_analyze_subscript_affine_affine (&chrec_a,
3407 analyze_subscript_affine_affine (chrec_a, chrec_b,
3408 overlaps_a, overlaps_b,
3410 /* FIXME: The number of iterations is a symbolic expression.
3411 Compute it properly. */
3412 *last_conflicts = chrec_dont_know;
3414 if (CF_NOT_KNOWN_P (*overlaps_a)
3415 || CF_NOT_KNOWN_P (*overlaps_b))
3416 dependence_stats.num_siv_unimplemented++;
3417 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
3418 || CF_NO_DEPENDENCE_P (*overlaps_b))
3419 dependence_stats.num_siv_independent++;
3421 dependence_stats.num_siv_dependent++;
3424 goto siv_subscript_dontknow;
3429 siv_subscript_dontknow:;
3430 if (dump_file && (dump_flags & TDF_DETAILS))
3431 fprintf (dump_file, "siv test failed: unimplemented.\n");
3432 *overlaps_a = conflict_fn_not_known ();
3433 *overlaps_b = conflict_fn_not_known ();
3434 *last_conflicts = chrec_dont_know;
3435 dependence_stats.num_siv_unimplemented++;
3438 if (dump_file && (dump_flags & TDF_DETAILS))
3439 fprintf (dump_file, ")\n");
3442 /* Return true when the property can be computed. RES should contain
3443 true when calling the first time this function, then it is set to
3444 false when one of the evolution steps of an affine CHREC does not
3445 divide the constant CST. */
3448 chrec_steps_divide_constant_p (tree chrec,
3452 switch (TREE_CODE (chrec))
3454 case POLYNOMIAL_CHREC:
3455 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
3457 if (tree_fold_divides_p (CHREC_RIGHT (chrec), cst))
3458 /* Keep RES to true, and iterate on other dimensions. */
3459 return chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst, res);
3465 /* When the step is a parameter the result is undetermined. */
3469 /* On the initial condition, return true. */
3474 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
3475 *OVERLAPS_B are initialized to the functions that describe the
3476 relation between the elements accessed twice by CHREC_A and
3477 CHREC_B. For k >= 0, the following property is verified:
3479 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
3482 analyze_miv_subscript (tree chrec_a,
3484 conflict_function **overlaps_a,
3485 conflict_function **overlaps_b,
3486 tree *last_conflicts)
3488 /* FIXME: This is a MIV subscript, not yet handled.
3489 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
3492 In the SIV test we had to solve a Diophantine equation with two
3493 variables. In the MIV case we have to solve a Diophantine
3494 equation with 2*n variables (if the subscript uses n IVs).
3496 bool divide_p = true;
3498 dependence_stats.num_miv++;
3499 if (dump_file && (dump_flags & TDF_DETAILS))
3500 fprintf (dump_file, "(analyze_miv_subscript \n");
3502 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
3503 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
3504 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
3506 if (eq_evolutions_p (chrec_a, chrec_b))
3508 /* Access functions are the same: all the elements are accessed
3509 in the same order. */
3510 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
3511 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
3512 *last_conflicts = estimated_loop_iterations_tree
3513 (get_chrec_loop (chrec_a), true);
3514 dependence_stats.num_miv_dependent++;
3517 else if (evolution_function_is_constant_p (difference)
3518 /* For the moment, the following is verified:
3519 evolution_function_is_affine_multivariate_p (chrec_a) */
3520 && chrec_steps_divide_constant_p (chrec_a, difference, ÷_p)
3523 /* testsuite/.../ssa-chrec-33.c
3524 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
3526 The difference is 1, and the evolution steps are equal to 2,
3527 consequently there are no overlapping elements. */
3528 *overlaps_a = conflict_fn_no_dependence ();
3529 *overlaps_b = conflict_fn_no_dependence ();
3530 *last_conflicts = integer_zero_node;
3531 dependence_stats.num_miv_independent++;
3534 else if (evolution_function_is_affine_multivariate_p (chrec_a)
3535 && !chrec_contains_symbols (chrec_a)
3536 && evolution_function_is_affine_multivariate_p (chrec_b)
3537 && !chrec_contains_symbols (chrec_b))
3539 /* testsuite/.../ssa-chrec-35.c
3540 {0, +, 1}_2 vs. {0, +, 1}_3
3541 the overlapping elements are respectively located at iterations:
3542 {0, +, 1}_x and {0, +, 1}_x,
3543 in other words, we have the equality:
3544 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
3547 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
3548 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
3550 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
3551 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
3553 analyze_subscript_affine_affine (chrec_a, chrec_b,
3554 overlaps_a, overlaps_b, last_conflicts);
3556 if (CF_NOT_KNOWN_P (*overlaps_a)
3557 || CF_NOT_KNOWN_P (*overlaps_b))
3558 dependence_stats.num_miv_unimplemented++;
3559 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
3560 || CF_NO_DEPENDENCE_P (*overlaps_b))
3561 dependence_stats.num_miv_independent++;
3563 dependence_stats.num_miv_dependent++;
3568 /* When the analysis is too difficult, answer "don't know". */
3569 if (dump_file && (dump_flags & TDF_DETAILS))
3570 fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
3572 *overlaps_a = conflict_fn_not_known ();
3573 *overlaps_b = conflict_fn_not_known ();
3574 *last_conflicts = chrec_dont_know;
3575 dependence_stats.num_miv_unimplemented++;
3578 if (dump_file && (dump_flags & TDF_DETAILS))
3579 fprintf (dump_file, ")\n");
3582 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
3583 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
3584 two functions that describe the iterations that contain conflicting
3587 Remark: For an integer k >= 0, the following equality is true:
3589 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
3593 analyze_overlapping_iterations (tree chrec_a,
3595 conflict_function **overlap_iterations_a,
3596 conflict_function **overlap_iterations_b,
3597 tree *last_conflicts)
3599 dependence_stats.num_subscript_tests++;
3601 if (dump_file && (dump_flags & TDF_DETAILS))
3603 fprintf (dump_file, "(analyze_overlapping_iterations \n");
3604 fprintf (dump_file, " (chrec_a = ");
3605 print_generic_expr (dump_file, chrec_a, 0);
3606 fprintf (dump_file, ")\n (chrec_b = ");
3607 print_generic_expr (dump_file, chrec_b, 0);
3608 fprintf (dump_file, ")\n");
3611 if (chrec_a == NULL_TREE
3612 || chrec_b == NULL_TREE
3613 || chrec_contains_undetermined (chrec_a)
3614 || chrec_contains_undetermined (chrec_b))
3616 dependence_stats.num_subscript_undetermined++;
3618 *overlap_iterations_a = conflict_fn_not_known ();
3619 *overlap_iterations_b = conflict_fn_not_known ();
3622 /* If they are the same chrec, and are affine, they overlap
3623 on every iteration. */
3624 else if (eq_evolutions_p (chrec_a, chrec_b)
3625 && evolution_function_is_affine_multivariate_p (chrec_a))
3627 dependence_stats.num_same_subscript_function++;
3628 *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
3629 *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
3630 *last_conflicts = chrec_dont_know;
3633 /* If they aren't the same, and aren't affine, we can't do anything
3635 else if ((chrec_contains_symbols (chrec_a)
3636 || chrec_contains_symbols (chrec_b))
3637 && (!evolution_function_is_affine_multivariate_p (chrec_a)
3638 || !evolution_function_is_affine_multivariate_p (chrec_b)))
3640 dependence_stats.num_subscript_undetermined++;
3641 *overlap_iterations_a = conflict_fn_not_known ();
3642 *overlap_iterations_b = conflict_fn_not_known ();
3645 else if (ziv_subscript_p (chrec_a, chrec_b))
3646 analyze_ziv_subscript (chrec_a, chrec_b,
3647 overlap_iterations_a, overlap_iterations_b,
3650 else if (siv_subscript_p (chrec_a, chrec_b))
3651 analyze_siv_subscript (chrec_a, chrec_b,
3652 overlap_iterations_a, overlap_iterations_b,
3656 analyze_miv_subscript (chrec_a, chrec_b,
3657 overlap_iterations_a, overlap_iterations_b,
3660 if (dump_file && (dump_flags & TDF_DETAILS))
3662 fprintf (dump_file, " (overlap_iterations_a = ");
3663 dump_conflict_function (dump_file, *overlap_iterations_a);
3664 fprintf (dump_file, ")\n (overlap_iterations_b = ");
3665 dump_conflict_function (dump_file, *overlap_iterations_b);
3666 fprintf (dump_file, ")\n");
3667 fprintf (dump_file, ")\n");
3671 /* Helper function for uniquely inserting distance vectors. */
3674 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
3679 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
3680 if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
3683 VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
3686 /* Helper function for uniquely inserting direction vectors. */
3689 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
3694 for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
3695 if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
3698 VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
3701 /* Add a distance of 1 on all the loops outer than INDEX. If we
3702 haven't yet determined a distance for this outer loop, push a new
3703 distance vector composed of the previous distance, and a distance
3704 of 1 for this outer loop. Example:
3712 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
3713 save (0, 1), then we have to save (1, 0). */
3716 add_outer_distances (struct data_dependence_relation *ddr,
3717 lambda_vector dist_v, int index)
3719 /* For each outer loop where init_v is not set, the accesses are
3720 in dependence of distance 1 in the loop. */
3721 while (--index >= 0)
3723 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3724 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3726 save_dist_v (ddr, save_v);
3730 /* Return false when fail to represent the data dependence as a
3731 distance vector. INIT_B is set to true when a component has been
3732 added to the distance vector DIST_V. INDEX_CARRY is then set to
3733 the index in DIST_V that carries the dependence. */
3736 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
3737 struct data_reference *ddr_a,
3738 struct data_reference *ddr_b,
3739 lambda_vector dist_v, bool *init_b,
3743 lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3745 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3747 tree access_fn_a, access_fn_b;
3748 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3750 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3752 non_affine_dependence_relation (ddr);
3756 access_fn_a = DR_ACCESS_FN (ddr_a, i);
3757 access_fn_b = DR_ACCESS_FN (ddr_b, i);
3759 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3760 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3763 int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
3764 DDR_LOOP_NEST (ddr));
3765 int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
3766 DDR_LOOP_NEST (ddr));
3768 /* The dependence is carried by the outermost loop. Example:
3775 In this case, the dependence is carried by loop_1. */
3776 index = index_a < index_b ? index_a : index_b;
3777 *index_carry = MIN (index, *index_carry);
3779 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3781 non_affine_dependence_relation (ddr);
3785 dist = int_cst_value (SUB_DISTANCE (subscript));
3787 /* This is the subscript coupling test. If we have already
3788 recorded a distance for this loop (a distance coming from
3789 another subscript), it should be the same. For example,
3790 in the following code, there is no dependence:
3797 if (init_v[index] != 0 && dist_v[index] != dist)
3799 finalize_ddr_dependent (ddr, chrec_known);
3803 dist_v[index] = dist;
3809 /* This can be for example an affine vs. constant dependence
3810 (T[i] vs. T[3]) that is not an affine dependence and is
3811 not representable as a distance vector. */
3812 non_affine_dependence_relation (ddr);
3820 /* Return true when the DDR contains two data references that have the
3821 same access functions. */
3824 same_access_functions (struct data_dependence_relation *ddr)
3828 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3829 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
3830 DR_ACCESS_FN (DDR_B (ddr), i)))
3836 /* Helper function for the case where DDR_A and DDR_B are the same
3837 multivariate access function. */
3840 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
3843 tree c_1 = CHREC_LEFT (c_2);
3844 tree c_0 = CHREC_LEFT (c_1);
3845 lambda_vector dist_v;
3847 /* Polynomials with more than 2 variables are not handled yet. */
3848 if (TREE_CODE (c_0) != INTEGER_CST)
3850 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
3854 x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
3855 x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
3857 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3858 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3859 dist_v[x_1] = int_cst_value (CHREC_RIGHT (c_2));
3860 dist_v[x_2] = -int_cst_value (CHREC_RIGHT (c_1));
3861 save_dist_v (ddr, dist_v);
3863 add_outer_distances (ddr, dist_v, x_1);
3866 /* Helper function for the case where DDR_A and DDR_B are the same
3867 access functions. */
3870 add_other_self_distances (struct data_dependence_relation *ddr)
3872 lambda_vector dist_v;
3874 int index_carry = DDR_NB_LOOPS (ddr);
3876 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3878 tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
3880 if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
3882 if (!evolution_function_is_univariate_p (access_fun))
3884 if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
3886 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
3890 add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0));
3894 index_carry = MIN (index_carry,
3895 index_in_loop_nest (CHREC_VARIABLE (access_fun),
3896 DDR_LOOP_NEST (ddr)));
3900 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3901 add_outer_distances (ddr, dist_v, index_carry);
3904 /* Compute the classic per loop distance vector. DDR is the data
3905 dependence relation to build a vector from. Return false when fail
3906 to represent the data dependence as a distance vector. */
3909 build_classic_dist_vector (struct data_dependence_relation *ddr)
3911 bool init_b = false;
3912 int index_carry = DDR_NB_LOOPS (ddr);
3913 lambda_vector dist_v;
3915 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3918 if (same_access_functions (ddr))
3920 /* Save the 0 vector. */
3921 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3922 save_dist_v (ddr, dist_v);
3924 if (DDR_NB_LOOPS (ddr) > 1)
3925 add_other_self_distances (ddr);
3930 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3931 if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
3932 dist_v, &init_b, &index_carry))
3935 /* Save the distance vector if we initialized one. */
3938 /* Verify a basic constraint: classic distance vectors should
3939 always be lexicographically positive.
3941 Data references are collected in the order of execution of
3942 the program, thus for the following loop
3944 | for (i = 1; i < 100; i++)
3945 | for (j = 1; j < 100; j++)
3947 | t = T[j+1][i-1]; // A
3948 | T[j][i] = t + 2; // B
3951 references are collected following the direction of the wind:
3952 A then B. The data dependence tests are performed also
3953 following this order, such that we're looking at the distance
3954 separating the elements accessed by A from the elements later
3955 accessed by B. But in this example, the distance returned by
3956 test_dep (A, B) is lexicographically negative (-1, 1), that
3957 means that the access A occurs later than B with respect to
3958 the outer loop, ie. we're actually looking upwind. In this
3959 case we solve test_dep (B, A) looking downwind to the
3960 lexicographically positive solution, that returns the
3961 distance vector (1, -1). */
3962 if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
3964 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3965 subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
3966 compute_subscript_distance (ddr);
3967 build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3968 save_v, &init_b, &index_carry);
3969 save_dist_v (ddr, save_v);
3971 /* In this case there is a dependence forward for all the
3974 | for (k = 1; k < 100; k++)
3975 | for (i = 1; i < 100; i++)
3976 | for (j = 1; j < 100; j++)
3978 | t = T[j+1][i-1]; // A
3979 | T[j][i] = t + 2; // B
3987 if (DDR_NB_LOOPS (ddr) > 1)
3989 add_outer_distances (ddr, save_v, index_carry);
3990 add_outer_distances (ddr, dist_v, index_carry);
3995 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3996 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3997 save_dist_v (ddr, save_v);
3999 if (DDR_NB_LOOPS (ddr) > 1)
4001 lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4003 subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
4004 compute_subscript_distance (ddr);
4005 build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
4006 opposite_v, &init_b, &index_carry);
4008 add_outer_distances (ddr, dist_v, index_carry);
4009 add_outer_distances (ddr, opposite_v, index_carry);
4015 /* There is a distance of 1 on all the outer loops: Example:
4016 there is a dependence of distance 1 on loop_1 for the array A.
4022 add_outer_distances (ddr, dist_v,
4023 lambda_vector_first_nz (dist_v,
4024 DDR_NB_LOOPS (ddr), 0));
4027 if (dump_file && (dump_flags & TDF_DETAILS))
4031 fprintf (dump_file, "(build_classic_dist_vector\n");
4032 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
4034 fprintf (dump_file, " dist_vector = (");
4035 print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
4036 DDR_NB_LOOPS (ddr));
4037 fprintf (dump_file, " )\n");
4039 fprintf (dump_file, ")\n");
4045 /* Return the direction for a given distance.
4046 FIXME: Computing dir this way is suboptimal, since dir can catch
4047 cases that dist is unable to represent. */
4049 static inline enum data_dependence_direction
4050 dir_from_dist (int dist)
4053 return dir_positive;
4055 return dir_negative;
4060 /* Compute the classic per loop direction vector. DDR is the data
4061 dependence relation to build a vector from. */
4064 build_classic_dir_vector (struct data_dependence_relation *ddr)
4067 lambda_vector dist_v;
4069 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
4071 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4073 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
4074 dir_v[j] = dir_from_dist (dist_v[j]);
4076 save_dir_v (ddr, dir_v);
4080 /* Helper function. Returns true when there is a dependence between
4081 data references DRA and DRB. */
4084 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
4085 struct data_reference *dra,
4086 struct data_reference *drb)
4089 tree last_conflicts;
4090 struct subscript *subscript;
4092 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
4095 conflict_function *overlaps_a, *overlaps_b;
4097 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
4098 DR_ACCESS_FN (drb, i),
4099 &overlaps_a, &overlaps_b,
4102 if (CF_NOT_KNOWN_P (overlaps_a)
4103 || CF_NOT_KNOWN_P (overlaps_b))
4105 finalize_ddr_dependent (ddr, chrec_dont_know);
4106 dependence_stats.num_dependence_undetermined++;
4107 free_conflict_function (overlaps_a);
4108 free_conflict_function (overlaps_b);
4112 else if (CF_NO_DEPENDENCE_P (overlaps_a)
4113 || CF_NO_DEPENDENCE_P (overlaps_b))
4115 finalize_ddr_dependent (ddr, chrec_known);
4116 dependence_stats.num_dependence_independent++;
4117 free_conflict_function (overlaps_a);
4118 free_conflict_function (overlaps_b);
4124 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
4125 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
4126 SUB_LAST_CONFLICT (subscript) = last_conflicts;
4133 /* Computes the conflicting iterations, and initialize DDR. */
4136 subscript_dependence_tester (struct data_dependence_relation *ddr)
4139 if (dump_file && (dump_flags & TDF_DETAILS))
4140 fprintf (dump_file, "(subscript_dependence_tester \n");
4142 if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr)))
4143 dependence_stats.num_dependence_dependent++;
4145 compute_subscript_distance (ddr);
4146 if (build_classic_dist_vector (ddr))
4147 build_classic_dir_vector (ddr);
4149 if (dump_file && (dump_flags & TDF_DETAILS))
4150 fprintf (dump_file, ")\n");
4153 /* Returns true when all the access functions of A are affine or
4157 access_functions_are_affine_or_constant_p (struct data_reference *a)
4160 VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
4163 for (i = 0; VEC_iterate (tree, fns, i, t); i++)
4164 if (!evolution_function_is_constant_p (t)
4165 && !evolution_function_is_affine_multivariate_p (t))
4171 /* Initializes an equation for an OMEGA problem using the information
4172 contained in the ACCESS_FUN. Returns true when the operation
4175 PB is the omega constraint system.
4176 EQ is the number of the equation to be initialized.
4177 OFFSET is used for shifting the variables names in the constraints:
4178 a constrain is composed of 2 * the number of variables surrounding
4179 dependence accesses. OFFSET is set either to 0 for the first n variables,
4180 then it is set to n.
4181 ACCESS_FUN is expected to be an affine chrec. */
4184 init_omega_eq_with_af (omega_pb pb, unsigned eq,
4185 unsigned int offset, tree access_fun,
4186 struct data_dependence_relation *ddr)
4188 switch (TREE_CODE (access_fun))
4190 case POLYNOMIAL_CHREC:
4192 tree left = CHREC_LEFT (access_fun);
4193 tree right = CHREC_RIGHT (access_fun);
4194 int var = CHREC_VARIABLE (access_fun);
4197 if (TREE_CODE (right) != INTEGER_CST)
4200 var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
4201 pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
4203 /* Compute the innermost loop index. */
4204 DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
4207 pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
4208 += int_cst_value (right);
4210 switch (TREE_CODE (left))
4212 case POLYNOMIAL_CHREC:
4213 return init_omega_eq_with_af (pb, eq, offset, left, ddr);
4216 pb->eqs[eq].coef[0] += int_cst_value (left);
4225 pb->eqs[eq].coef[0] += int_cst_value (access_fun);
4233 /* As explained in the comments preceding init_omega_for_ddr, we have
4234 to set up a system for each loop level, setting outer loops
4235 variation to zero, and current loop variation to positive or zero.
4236 Save each lexico positive distance vector. */
4239 omega_extract_distance_vectors (omega_pb pb,
4240 struct data_dependence_relation *ddr)
4244 struct loop *loopi, *loopj;
4245 enum omega_result res;
4247 /* Set a new problem for each loop in the nest. The basis is the
4248 problem that we have initialized until now. On top of this we
4249 add new constraints. */
4250 for (i = 0; i <= DDR_INNER_LOOP (ddr)
4251 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
4254 omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
4255 DDR_NB_LOOPS (ddr));
4257 omega_copy_problem (copy, pb);
4259 /* For all the outer loops "loop_j", add "dj = 0". */
4261 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
4263 eq = omega_add_zero_eq (copy, omega_black);
4264 copy->eqs[eq].coef[j + 1] = 1;
4267 /* For "loop_i", add "0 <= di". */
4268 geq = omega_add_zero_geq (copy, omega_black);
4269 copy->geqs[geq].coef[i + 1] = 1;
4271 /* Reduce the constraint system, and test that the current
4272 problem is feasible. */
4273 res = omega_simplify_problem (copy);
4274 if (res == omega_false
4275 || res == omega_unknown
4276 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
4279 for (eq = 0; eq < copy->num_subs; eq++)
4280 if (copy->subs[eq].key == (int) i + 1)
4282 dist = copy->subs[eq].coef[0];
4288 /* Reinitialize problem... */
4289 omega_copy_problem (copy, pb);
4291 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
4293 eq = omega_add_zero_eq (copy, omega_black);
4294 copy->eqs[eq].coef[j + 1] = 1;
4297 /* ..., but this time "di = 1". */
4298 eq = omega_add_zero_eq (copy, omega_black);
4299 copy->eqs[eq].coef[i + 1] = 1;
4300 copy->eqs[eq].coef[0] = -1;
4302 res = omega_simplify_problem (copy);
4303 if (res == omega_false
4304 || res == omega_unknown
4305 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
4308 for (eq = 0; eq < copy->num_subs; eq++)
4309 if (copy->subs[eq].key == (int) i + 1)
4311 dist = copy->subs[eq].coef[0];
4317 /* Save the lexicographically positive distance vector. */
4320 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4321 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4325 for (eq = 0; eq < copy->num_subs; eq++)
4326 if (copy->subs[eq].key > 0)
4328 dist = copy->subs[eq].coef[0];
4329 dist_v[copy->subs[eq].key - 1] = dist;
4332 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
4333 dir_v[j] = dir_from_dist (dist_v[j]);
4335 save_dist_v (ddr, dist_v);
4336 save_dir_v (ddr, dir_v);
4340 omega_free_problem (copy);
4344 /* This is called for each subscript of a tuple of data references:
4345 insert an equality for representing the conflicts. */
4348 omega_setup_subscript (tree access_fun_a, tree access_fun_b,
4349 struct data_dependence_relation *ddr,
4350 omega_pb pb, bool *maybe_dependent)
4353 tree fun_a = chrec_convert (integer_type_node, access_fun_a, NULL_TREE);
4354 tree fun_b = chrec_convert (integer_type_node, access_fun_b, NULL_TREE);
4355 tree difference = chrec_fold_minus (integer_type_node, fun_a, fun_b);
4357 /* When the fun_a - fun_b is not constant, the dependence is not
4358 captured by the classic distance vector representation. */
4359 if (TREE_CODE (difference) != INTEGER_CST)
4363 if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
4365 /* There is no dependence. */
4366 *maybe_dependent = false;
4370 fun_b = chrec_fold_multiply (integer_type_node, fun_b,
4371 integer_minus_one_node);
4373 eq = omega_add_zero_eq (pb, omega_black);
4374 if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
4375 || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
4376 /* There is probably a dependence, but the system of
4377 constraints cannot be built: answer "don't know". */
4381 if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
4382 && !int_divides_p (lambda_vector_gcd
4383 ((lambda_vector) &(pb->eqs[eq].coef[1]),
4384 2 * DDR_NB_LOOPS (ddr)),
4385 pb->eqs[eq].coef[0]))
4387 /* There is no dependence. */
4388 *maybe_dependent = false;
4395 /* Helper function, same as init_omega_for_ddr but specialized for
4396 data references A and B. */
4399 init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
4400 struct data_dependence_relation *ddr,
4401 omega_pb pb, bool *maybe_dependent)
4406 unsigned nb_loops = DDR_NB_LOOPS (ddr);
4408 /* Insert an equality per subscript. */
4409 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
4411 if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
4412 ddr, pb, maybe_dependent))
4414 else if (*maybe_dependent == false)
4416 /* There is no dependence. */
4417 DDR_ARE_DEPENDENT (ddr) = chrec_known;
4422 /* Insert inequalities: constraints corresponding to the iteration
4423 domain, i.e. the loops surrounding the references "loop_x" and
4424 the distance variables "dx". The layout of the OMEGA
4425 representation is as follows:
4426 - coef[0] is the constant
4427 - coef[1..nb_loops] are the protected variables that will not be
4428 removed by the solver: the "dx"
4429 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
4431 for (i = 0; i <= DDR_INNER_LOOP (ddr)
4432 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
4434 HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, true);
4437 ineq = omega_add_zero_geq (pb, omega_black);
4438 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
4440 /* 0 <= loop_x + dx */
4441 ineq = omega_add_zero_geq (pb, omega_black);
4442 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
4443 pb->geqs[ineq].coef[i + 1] = 1;
4447 /* loop_x <= nb_iters */
4448 ineq = omega_add_zero_geq (pb, omega_black);
4449 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
4450 pb->geqs[ineq].coef[0] = nbi;
4452 /* loop_x + dx <= nb_iters */
4453 ineq = omega_add_zero_geq (pb, omega_black);
4454 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
4455 pb->geqs[ineq].coef[i + 1] = -1;
4456 pb->geqs[ineq].coef[0] = nbi;
4458 /* A step "dx" bigger than nb_iters is not feasible, so
4459 add "0 <= nb_iters + dx", */
4460 ineq = omega_add_zero_geq (pb, omega_black);
4461 pb->geqs[ineq].coef[i + 1] = 1;
4462 pb->geqs[ineq].coef[0] = nbi;
4463 /* and "dx <= nb_iters". */
4464 ineq = omega_add_zero_geq (pb, omega_black);
4465 pb->geqs[ineq].coef[i + 1] = -1;
4466 pb->geqs[ineq].coef[0] = nbi;
4470 omega_extract_distance_vectors (pb, ddr);
4475 /* Sets up the Omega dependence problem for the data dependence
4476 relation DDR. Returns false when the constraint system cannot be
4477 built, ie. when the test answers "don't know". Returns true
4478 otherwise, and when independence has been proved (using one of the
4479 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
4480 set MAYBE_DEPENDENT to true.
4482 Example: for setting up the dependence system corresponding to the
4483 conflicting accesses
4488 | ... A[2*j, 2*(i + j)]
4492 the following constraints come from the iteration domain:
4499 where di, dj are the distance variables. The constraints
4500 representing the conflicting elements are:
4503 i + 1 = 2 * (i + di + j + dj)
4505 For asking that the resulting distance vector (di, dj) be
4506 lexicographically positive, we insert the constraint "di >= 0". If
4507 "di = 0" in the solution, we fix that component to zero, and we
4508 look at the inner loops: we set a new problem where all the outer
4509 loop distances are zero, and fix this inner component to be
4510 positive. When one of the components is positive, we save that
4511 distance, and set a new problem where the distance on this loop is
4512 zero, searching for other distances in the inner loops. Here is
4513 the classic example that illustrates that we have to set for each
4514 inner loop a new problem:
4522 we have to save two distances (1, 0) and (0, 1).
4524 Given two array references, refA and refB, we have to set the
4525 dependence problem twice, refA vs. refB and refB vs. refA, and we
4526 cannot do a single test, as refB might occur before refA in the
4527 inner loops, and the contrary when considering outer loops: ex.
4532 | T[{1,+,1}_2][{1,+,1}_1] // refA
4533 | T[{2,+,1}_2][{0,+,1}_1] // refB
4538 refB touches the elements in T before refA, and thus for the same
4539 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
4540 but for successive loop_0 iterations, we have (1, -1, 1)
4542 The Omega solver expects the distance variables ("di" in the
4543 previous example) to come first in the constraint system (as
4544 variables to be protected, or "safe" variables), the constraint
4545 system is built using the following layout:
4547 "cst | distance vars | index vars".
4551 init_omega_for_ddr (struct data_dependence_relation *ddr,
4552 bool *maybe_dependent)
4557 *maybe_dependent = true;
4559 if (same_access_functions (ddr))
4562 lambda_vector dir_v;
4564 /* Save the 0 vector. */
4565 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
4566 dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4567 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
4568 dir_v[j] = dir_equal;
4569 save_dir_v (ddr, dir_v);
4571 /* Save the dependences carried by outer loops. */
4572 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4573 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
4575 omega_free_problem (pb);
4579 /* Omega expects the protected variables (those that have to be kept
4580 after elimination) to appear first in the constraint system.
4581 These variables are the distance variables. In the following
4582 initialization we declare NB_LOOPS safe variables, and the total
4583 number of variables for the constraint system is 2*NB_LOOPS. */
4584 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4585 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
4587 omega_free_problem (pb);
4589 /* Stop computation if not decidable, or no dependence. */
4590 if (res == false || *maybe_dependent == false)
4593 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4594 res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
4596 omega_free_problem (pb);
4601 /* Return true when DDR contains the same information as that stored
4602 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
4605 ddr_consistent_p (FILE *file,
4606 struct data_dependence_relation *ddr,
4607 VEC (lambda_vector, heap) *dist_vects,
4608 VEC (lambda_vector, heap) *dir_vects)
4612 /* If dump_file is set, output there. */
4613 if (dump_file && (dump_flags & TDF_DETAILS))
4616 if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
4618 lambda_vector b_dist_v;
4619 fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
4620 VEC_length (lambda_vector, dist_vects),
4621 DDR_NUM_DIST_VECTS (ddr));
4623 fprintf (file, "Banerjee dist vectors:\n");
4624 for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++)
4625 print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
4627 fprintf (file, "Omega dist vectors:\n");
4628 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
4629 print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
4631 fprintf (file, "data dependence relation:\n");
4632 dump_data_dependence_relation (file, ddr);
4634 fprintf (file, ")\n");
4638 if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
4640 fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
4641 VEC_length (lambda_vector, dir_vects),
4642 DDR_NUM_DIR_VECTS (ddr));
4646 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
4648 lambda_vector a_dist_v;
4649 lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
4651 /* Distance vectors are not ordered in the same way in the DDR
4652 and in the DIST_VECTS: search for a matching vector. */
4653 for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, a_dist_v); j++)
4654 if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
4657 if (j == VEC_length (lambda_vector, dist_vects))
4659 fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
4660 print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
4661 fprintf (file, "not found in Omega dist vectors:\n");
4662 print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
4663 fprintf (file, "data dependence relation:\n");
4664 dump_data_dependence_relation (file, ddr);
4665 fprintf (file, ")\n");
4669 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
4671 lambda_vector a_dir_v;
4672 lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
4674 /* Direction vectors are not ordered in the same way in the DDR
4675 and in the DIR_VECTS: search for a matching vector. */
4676 for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, a_dir_v); j++)
4677 if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
4680 if (j == VEC_length (lambda_vector, dist_vects))
4682 fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
4683 print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
4684 fprintf (file, "not found in Omega dir vectors:\n");
4685 print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
4686 fprintf (file, "data dependence relation:\n");
4687 dump_data_dependence_relation (file, ddr);
4688 fprintf (file, ")\n");
4695 /* This computes the affine dependence relation between A and B.
4696 CHREC_KNOWN is used for representing the independence between two
4697 accesses, while CHREC_DONT_KNOW is used for representing the unknown
4700 Note that it is possible to stop the computation of the dependence
4701 relation the first time we detect a CHREC_KNOWN element for a given
4705 compute_affine_dependence (struct data_dependence_relation *ddr)
4707 struct data_reference *dra = DDR_A (ddr);
4708 struct data_reference *drb = DDR_B (ddr);
4710 if (dump_file && (dump_flags & TDF_DETAILS))
4712 fprintf (dump_file, "(compute_affine_dependence\n");
4713 fprintf (dump_file, " (stmt_a = \n");
4714 print_generic_expr (dump_file, DR_STMT (dra), 0);
4715 fprintf (dump_file, ")\n (stmt_b = \n");
4716 print_generic_expr (dump_file, DR_STMT (drb), 0);
4717 fprintf (dump_file, ")\n");
4720 /* Analyze only when the dependence relation is not yet known. */
4721 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4723 dependence_stats.num_dependence_tests++;
4725 if (access_functions_are_affine_or_constant_p (dra)
4726 && access_functions_are_affine_or_constant_p (drb))
4728 if (flag_check_data_deps)
4730 /* Compute the dependences using the first algorithm. */
4731 subscript_dependence_tester (ddr);
4733 if (dump_file && (dump_flags & TDF_DETAILS))
4735 fprintf (dump_file, "\n\nBanerjee Analyzer\n");
4736 dump_data_dependence_relation (dump_file, ddr);
4739 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4741 bool maybe_dependent;
4742 VEC (lambda_vector, heap) *dir_vects, *dist_vects;
4744 /* Save the result of the first DD analyzer. */
4745 dist_vects = DDR_DIST_VECTS (ddr);
4746 dir_vects = DDR_DIR_VECTS (ddr);
4748 /* Reset the information. */
4749 DDR_DIST_VECTS (ddr) = NULL;
4750 DDR_DIR_VECTS (ddr) = NULL;
4752 /* Compute the same information using Omega. */
4753 if (!init_omega_for_ddr (ddr, &maybe_dependent))
4754 goto csys_dont_know;
4756 if (dump_file && (dump_flags & TDF_DETAILS))
4758 fprintf (dump_file, "Omega Analyzer\n");
4759 dump_data_dependence_relation (dump_file, ddr);
4762 /* Check that we get the same information. */
4763 if (maybe_dependent)
4764 gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
4769 subscript_dependence_tester (ddr);
4772 /* As a last case, if the dependence cannot be determined, or if
4773 the dependence is considered too difficult to determine, answer
4778 dependence_stats.num_dependence_undetermined++;
4780 if (dump_file && (dump_flags & TDF_DETAILS))
4782 fprintf (dump_file, "Data ref a:\n");
4783 dump_data_reference (dump_file, dra);
4784 fprintf (dump_file, "Data ref b:\n");
4785 dump_data_reference (dump_file, drb);
4786 fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
4788 finalize_ddr_dependent (ddr, chrec_dont_know);
4792 if (dump_file && (dump_flags & TDF_DETAILS))
4793 fprintf (dump_file, ")\n");
4796 /* This computes the dependence relation for the same data
4797 reference into DDR. */
4800 compute_self_dependence (struct data_dependence_relation *ddr)
4803 struct subscript *subscript;
4805 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
4808 /* The accessed index overlaps for each iteration. */
4809 SUB_CONFLICTS_IN_A (subscript)
4810 = conflict_fn (1, affine_fn_cst (integer_zero_node));
4811 SUB_CONFLICTS_IN_B (subscript)
4812 = conflict_fn (1, affine_fn_cst (integer_zero_node));
4813 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
4816 /* The distance vector is the zero vector. */
4817 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
4818 save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
4821 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4822 the data references in DATAREFS, in the LOOP_NEST. When
4823 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4827 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
4828 VEC (ddr_p, heap) **dependence_relations,
4829 VEC (loop_p, heap) *loop_nest,
4830 bool compute_self_and_rr)
4832 struct data_dependence_relation *ddr;
4833 struct data_reference *a, *b;
4836 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
4837 for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
4838 if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
4840 ddr = initialize_data_dependence_relation (a, b, loop_nest);
4841 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4842 compute_affine_dependence (ddr);
4845 if (compute_self_and_rr)
4846 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
4848 ddr = initialize_data_dependence_relation (a, a, loop_nest);
4849 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4850 compute_self_dependence (ddr);
4854 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4855 true if STMT clobbers memory, false otherwise. */
4858 get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references)
4860 bool clobbers_memory = false;
4862 tree *op0, *op1, arg, call;
4863 call_expr_arg_iterator iter;
4867 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4868 Calls have side-effects, except those to const or pure
4870 call = get_call_expr_in (stmt);
4872 && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE)))
4873 || (TREE_CODE (stmt) == ASM_EXPR
4874 && ASM_VOLATILE_P (stmt)))
4875 clobbers_memory = true;
4877 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
4878 return clobbers_memory;
4880 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
4882 op0 = &GIMPLE_STMT_OPERAND (stmt, 0);
4883 op1 = &GIMPLE_STMT_OPERAND (stmt, 1);
4886 || REFERENCE_CLASS_P (*op1))
4888 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4890 ref->is_read = true;
4894 || REFERENCE_CLASS_P (*op0))
4896 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4898 ref->is_read = false;
4904 FOR_EACH_CALL_EXPR_ARG (arg, iter, call)
4908 || REFERENCE_CLASS_P (*op0))
4910 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4912 ref->is_read = true;
4917 return clobbers_memory;
4920 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4921 reference, returns false, otherwise returns true. */
4924 find_data_references_in_stmt (tree stmt,
4925 VEC (data_reference_p, heap) **datarefs)
4928 VEC (data_ref_loc, heap) *references;
4931 data_reference_p dr;
4933 if (get_references_in_stmt (stmt, &references))
4935 VEC_free (data_ref_loc, heap, references);
4939 for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
4941 dr = create_data_ref (*ref->pos, stmt, ref->is_read);
4943 VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4950 VEC_free (data_ref_loc, heap, references);
4954 /* Search the data references in LOOP, and record the information into
4955 DATAREFS. Returns chrec_dont_know when failing to analyze a
4956 difficult case, returns NULL_TREE otherwise.
4958 TODO: This function should be made smarter so that it can handle address
4959 arithmetic as if they were array accesses, etc. */
4962 find_data_references_in_loop (struct loop *loop,
4963 VEC (data_reference_p, heap) **datarefs)
4965 basic_block bb, *bbs;
4967 block_stmt_iterator bsi;
4969 bbs = get_loop_body (loop);
4971 for (i = 0; i < loop->num_nodes; i++)
4975 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4977 tree stmt = bsi_stmt (bsi);
4979 if (!find_data_references_in_stmt (stmt, datarefs))
4981 struct data_reference *res;
4982 res = XNEW (struct data_reference);
4983 DR_STMT (res) = NULL_TREE;
4984 DR_REF (res) = NULL_TREE;
4985 DR_BASE_OBJECT (res) = NULL;
4986 DR_TYPE (res) = ARRAY_REF_TYPE;
4987 DR_SET_ACCESS_FNS (res, NULL);
4988 DR_BASE_OBJECT (res) = NULL;
4989 DR_IS_READ (res) = false;
4990 DR_BASE_ADDRESS (res) = NULL_TREE;
4991 DR_OFFSET (res) = NULL_TREE;
4992 DR_INIT (res) = NULL_TREE;
4993 DR_STEP (res) = NULL_TREE;
4994 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
4995 DR_MEMTAG (res) = NULL_TREE;
4996 DR_PTR_INFO (res) = NULL;
4997 VEC_safe_push (data_reference_p, heap, *datarefs, res);
5000 return chrec_dont_know;
5009 /* Recursive helper function. */
5012 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
5014 /* Inner loops of the nest should not contain siblings. Example:
5015 when there are two consecutive loops,
5026 the dependence relation cannot be captured by the distance
5031 VEC_safe_push (loop_p, heap, *loop_nest, loop);
5033 return find_loop_nest_1 (loop->inner, loop_nest);
5037 /* Return false when the LOOP is not well nested. Otherwise return
5038 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
5039 contain the loops from the outermost to the innermost, as they will
5040 appear in the classic distance vector. */
5043 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
5045 VEC_safe_push (loop_p, heap, *loop_nest, loop);
5047 return find_loop_nest_1 (loop->inner, loop_nest);
5051 /* Given a loop nest LOOP, the following vectors are returned:
5052 DATAREFS is initialized to all the array elements contained in this loop,
5053 DEPENDENCE_RELATIONS contains the relations between the data references.
5054 Compute read-read and self relations if
5055 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
5058 compute_data_dependences_for_loop (struct loop *loop,
5059 bool compute_self_and_read_read_dependences,
5060 VEC (data_reference_p, heap) **datarefs,
5061 VEC (ddr_p, heap) **dependence_relations)
5063 struct loop *loop_nest = loop;
5064 VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
5066 memset (&dependence_stats, 0, sizeof (dependence_stats));
5068 /* If the loop nest is not well formed, or one of the data references
5069 is not computable, give up without spending time to compute other
5072 || !find_loop_nest (loop_nest, &vloops)
5073 || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
5075 struct data_dependence_relation *ddr;
5077 /* Insert a single relation into dependence_relations:
5079 ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
5080 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
5083 compute_all_dependences (*datarefs, dependence_relations, vloops,
5084 compute_self_and_read_read_dependences);
5086 if (dump_file && (dump_flags & TDF_STATS))
5088 fprintf (dump_file, "Dependence tester statistics:\n");
5090 fprintf (dump_file, "Number of dependence tests: %d\n",
5091 dependence_stats.num_dependence_tests);
5092 fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
5093 dependence_stats.num_dependence_dependent);
5094 fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
5095 dependence_stats.num_dependence_independent);
5096 fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
5097 dependence_stats.num_dependence_undetermined);
5099 fprintf (dump_file, "Number of subscript tests: %d\n",
5100 dependence_stats.num_subscript_tests);
5101 fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
5102 dependence_stats.num_subscript_undetermined);
5103 fprintf (dump_file, "Number of same subscript function: %d\n",
5104 dependence_stats.num_same_subscript_function);
5106 fprintf (dump_file, "Number of ziv tests: %d\n",
5107 dependence_stats.num_ziv);
5108 fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
5109 dependence_stats.num_ziv_dependent);
5110 fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
5111 dependence_stats.num_ziv_independent);
5112 fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
5113 dependence_stats.num_ziv_unimplemented);
5115 fprintf (dump_file, "Number of siv tests: %d\n",
5116 dependence_stats.num_siv);
5117 fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
5118 dependence_stats.num_siv_dependent);
5119 fprintf (dump_file, "Number of siv tests returning independent: %d\n",
5120 dependence_stats.num_siv_independent);
5121 fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
5122 dependence_stats.num_siv_unimplemented);
5124 fprintf (dump_file, "Number of miv tests: %d\n",
5125 dependence_stats.num_miv);
5126 fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
5127 dependence_stats.num_miv_dependent);
5128 fprintf (dump_file, "Number of miv tests returning independent: %d\n",
5129 dependence_stats.num_miv_independent);
5130 fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
5131 dependence_stats.num_miv_unimplemented);
5135 /* Entry point (for testing only). Analyze all the data references
5136 and the dependence relations in LOOP.
5138 The data references are computed first.
5140 A relation on these nodes is represented by a complete graph. Some
5141 of the relations could be of no interest, thus the relations can be
5144 In the following function we compute all the relations. This is
5145 just a first implementation that is here for:
5146 - for showing how to ask for the dependence relations,
5147 - for the debugging the whole dependence graph,
5148 - for the dejagnu testcases and maintenance.
5150 It is possible to ask only for a part of the graph, avoiding to
5151 compute the whole dependence graph. The computed dependences are
5152 stored in a knowledge base (KB) such that later queries don't
5153 recompute the same information. The implementation of this KB is
5154 transparent to the optimizer, and thus the KB can be changed with a
5155 more efficient implementation, or the KB could be disabled. */
5157 analyze_all_data_dependences (struct loop *loop)
5160 int nb_data_refs = 10;
5161 VEC (data_reference_p, heap) *datarefs =
5162 VEC_alloc (data_reference_p, heap, nb_data_refs);
5163 VEC (ddr_p, heap) *dependence_relations =
5164 VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
5166 /* Compute DDs on the whole function. */
5167 compute_data_dependences_for_loop (loop, false, &datarefs,
5168 &dependence_relations);
5172 dump_data_dependence_relations (dump_file, dependence_relations);
5173 fprintf (dump_file, "\n\n");
5175 if (dump_flags & TDF_DETAILS)
5176 dump_dist_dir_vectors (dump_file, dependence_relations);
5178 if (dump_flags & TDF_STATS)
5180 unsigned nb_top_relations = 0;
5181 unsigned nb_bot_relations = 0;
5182 unsigned nb_basename_differ = 0;
5183 unsigned nb_chrec_relations = 0;
5184 struct data_dependence_relation *ddr;
5186 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
5188 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
5191 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
5193 struct data_reference *a = DDR_A (ddr);
5194 struct data_reference *b = DDR_B (ddr);
5197 if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
5198 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
5199 || (base_object_differ_p (a, b, &differ_p)
5201 nb_basename_differ++;
5207 nb_chrec_relations++;
5210 gather_stats_on_scev_database ();
5214 free_dependence_relations (dependence_relations);
5215 free_data_refs (datarefs);
5218 /* Computes all the data dependences and check that the results of
5219 several analyzers are the same. */
5222 tree_check_data_deps (void)
5225 struct loop *loop_nest;
5227 FOR_EACH_LOOP (li, loop_nest, 0)
5228 analyze_all_data_dependences (loop_nest);
5231 /* Free the memory used by a data dependence relation DDR. */
5234 free_dependence_relation (struct data_dependence_relation *ddr)
5239 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
5240 free_subscripts (DDR_SUBSCRIPTS (ddr));
5245 /* Free the memory used by the data dependence relations from
5246 DEPENDENCE_RELATIONS. */
5249 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
5252 struct data_dependence_relation *ddr;
5253 VEC (loop_p, heap) *loop_nest = NULL;
5255 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
5259 if (loop_nest == NULL)
5260 loop_nest = DDR_LOOP_NEST (ddr);
5262 gcc_assert (DDR_LOOP_NEST (ddr) == NULL
5263 || DDR_LOOP_NEST (ddr) == loop_nest);
5264 free_dependence_relation (ddr);
5268 VEC_free (loop_p, heap, loop_nest);
5269 VEC_free (ddr_p, heap, dependence_relations);
5272 /* Free the memory used by the data references from DATAREFS. */
5275 free_data_refs (VEC (data_reference_p, heap) *datarefs)
5278 struct data_reference *dr;
5280 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
5282 VEC_free (data_reference_p, heap, datarefs);