1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006 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 struct data_reference * init_data_ref (tree, tree, tree, tree, bool,
129 tree, tree, tree, tree, tree,
130 struct ptr_info_def *,
132 static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
133 struct data_reference *,
134 struct data_reference *);
136 /* Determine if PTR and DECL may alias, the result is put in ALIASED.
137 Return FALSE if there is no symbol memory tag for PTR. */
140 ptr_decl_may_alias_p (tree ptr, tree decl,
141 struct data_reference *ptr_dr,
144 tree tag = NULL_TREE;
145 struct ptr_info_def *pi = DR_PTR_INFO (ptr_dr);
147 gcc_assert (TREE_CODE (ptr) == SSA_NAME && DECL_P (decl));
150 tag = pi->name_mem_tag;
152 tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
154 tag = DR_MEMTAG (ptr_dr);
158 *aliased = is_aliased_with (tag, decl);
163 /* Determine if two pointers may alias, the result is put in ALIASED.
164 Return FALSE if there is no symbol memory tag for one of the pointers. */
167 ptr_ptr_may_alias_p (tree ptr_a, tree ptr_b,
168 struct data_reference *dra,
169 struct data_reference *drb,
172 tree tag_a = NULL_TREE, tag_b = NULL_TREE;
173 struct ptr_info_def *pi_a = DR_PTR_INFO (dra);
174 struct ptr_info_def *pi_b = DR_PTR_INFO (drb);
177 if (pi_a && pi_a->name_mem_tag && pi_b && pi_b->name_mem_tag)
179 tag_a = pi_a->name_mem_tag;
180 tag_b = pi_b->name_mem_tag;
184 tag_a = symbol_mem_tag (SSA_NAME_VAR (ptr_a));
186 tag_a = DR_MEMTAG (dra);
190 tag_b = symbol_mem_tag (SSA_NAME_VAR (ptr_b));
192 tag_b = DR_MEMTAG (drb);
196 bal1 = BITMAP_ALLOC (NULL);
197 bitmap_set_bit (bal1, DECL_UID (tag_a));
198 if (MTAG_P (tag_a) && MTAG_ALIASES (tag_a))
199 bitmap_ior_into (bal1, MTAG_ALIASES (tag_a));
201 bal2 = BITMAP_ALLOC (NULL);
202 bitmap_set_bit (bal2, DECL_UID (tag_b));
203 if (MTAG_P (tag_b) && MTAG_ALIASES (tag_b))
204 bitmap_ior_into (bal2, MTAG_ALIASES (tag_b));
205 *aliased = bitmap_intersect_p (bal1, bal2);
213 /* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED.
214 Return FALSE if there is no symbol memory tag for one of the symbols. */
217 may_alias_p (tree base_a, tree base_b,
218 struct data_reference *dra,
219 struct data_reference *drb,
222 if (TREE_CODE (base_a) == ADDR_EXPR || TREE_CODE (base_b) == ADDR_EXPR)
224 if (TREE_CODE (base_a) == ADDR_EXPR && TREE_CODE (base_b) == ADDR_EXPR)
226 *aliased = (TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0));
229 if (TREE_CODE (base_a) == ADDR_EXPR)
230 return ptr_decl_may_alias_p (base_b, TREE_OPERAND (base_a, 0), drb,
233 return ptr_decl_may_alias_p (base_a, TREE_OPERAND (base_b, 0), dra,
237 return ptr_ptr_may_alias_p (base_a, base_b, dra, drb, aliased);
241 /* Determine if a pointer (BASE_A) and a record/union access (BASE_B)
242 are not aliased. Return TRUE if they differ. */
244 record_ptr_differ_p (struct data_reference *dra,
245 struct data_reference *drb)
248 tree base_a = DR_BASE_OBJECT (dra);
249 tree base_b = DR_BASE_OBJECT (drb);
251 if (TREE_CODE (base_b) != COMPONENT_REF)
254 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
255 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
256 Probably will be unnecessary with struct alias analysis. */
257 while (TREE_CODE (base_b) == COMPONENT_REF)
258 base_b = TREE_OPERAND (base_b, 0);
259 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
261 if (TREE_CODE (base_a) == INDIRECT_REF
262 && ((TREE_CODE (base_b) == VAR_DECL
263 && (ptr_decl_may_alias_p (TREE_OPERAND (base_a, 0), base_b, dra,
266 || (TREE_CODE (base_b) == INDIRECT_REF
267 && (ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0),
268 TREE_OPERAND (base_b, 0), dra, drb,
276 /* Determine if two record/union accesses are aliased. Return TRUE if they
279 record_record_differ_p (struct data_reference *dra,
280 struct data_reference *drb)
283 tree base_a = DR_BASE_OBJECT (dra);
284 tree base_b = DR_BASE_OBJECT (drb);
286 if (TREE_CODE (base_b) != COMPONENT_REF
287 || TREE_CODE (base_a) != COMPONENT_REF)
290 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
291 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
292 Probably will be unnecessary with struct alias analysis. */
293 while (TREE_CODE (base_b) == COMPONENT_REF)
294 base_b = TREE_OPERAND (base_b, 0);
295 while (TREE_CODE (base_a) == COMPONENT_REF)
296 base_a = TREE_OPERAND (base_a, 0);
298 if (TREE_CODE (base_a) == INDIRECT_REF
299 && TREE_CODE (base_b) == INDIRECT_REF
300 && ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0),
301 TREE_OPERAND (base_b, 0),
309 /* Determine if an array access (BASE_A) and a record/union access (BASE_B)
310 are not aliased. Return TRUE if they differ. */
312 record_array_differ_p (struct data_reference *dra,
313 struct data_reference *drb)
316 tree base_a = DR_BASE_OBJECT (dra);
317 tree base_b = DR_BASE_OBJECT (drb);
319 if (TREE_CODE (base_b) != COMPONENT_REF)
322 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
323 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
324 Probably will be unnecessary with struct alias analysis. */
325 while (TREE_CODE (base_b) == COMPONENT_REF)
326 base_b = TREE_OPERAND (base_b, 0);
328 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
329 (a[i]). In case of p->c[i] use alias analysis to verify that p is not
331 if (TREE_CODE (base_a) == VAR_DECL
332 && (TREE_CODE (base_b) == VAR_DECL
333 || (TREE_CODE (base_b) == INDIRECT_REF
334 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb,
343 /* Determine if an array access (BASE_A) and a pointer (BASE_B)
344 are not aliased. Return TRUE if they differ. */
346 array_ptr_differ_p (tree base_a, tree base_b,
347 struct data_reference *drb)
351 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
352 help of alias analysis that p is not pointing to a. */
353 if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == INDIRECT_REF
354 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, &aliased)
362 /* This is the simplest data dependence test: determines whether the
363 data references A and B access the same array/region. Returns
364 false when the property is not computable at compile time.
365 Otherwise return true, and DIFFER_P will record the result. This
366 utility will not be necessary when alias_sets_conflict_p will be
367 less conservative. */
370 base_object_differ_p (struct data_reference *a,
371 struct data_reference *b,
374 tree base_a = DR_BASE_OBJECT (a);
375 tree base_b = DR_BASE_OBJECT (b);
378 if (!base_a || !base_b)
381 /* Determine if same base. Example: for the array accesses
382 a[i], b[i] or pointer accesses *a, *b, bases are a, b. */
383 if (base_a == base_b)
389 /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
391 if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
392 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0))
398 /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */
399 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
400 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)
401 && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1))
408 /* Determine if different bases. */
410 /* At this point we know that base_a != base_b. However, pointer
411 accesses of the form x=(*p) and y=(*q), whose bases are p and q,
412 may still be pointing to the same base. In SSAed GIMPLE p and q will
413 be SSA_NAMES in this case. Therefore, here we check if they are
414 really two different declarations. */
415 if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
421 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
422 help of alias analysis that p is not pointing to a. */
423 if (array_ptr_differ_p (base_a, base_b, b)
424 || array_ptr_differ_p (base_b, base_a, a))
430 /* If the bases are pointers ((*q)[i] and (*p)[i]), we check with the
431 help of alias analysis they don't point to the same bases. */
432 if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
433 && (may_alias_p (TREE_OPERAND (base_a, 0), TREE_OPERAND (base_b, 0), a, b,
441 /* Compare two record/union bases s.a and t.b: s != t or (a != b and
442 s and t are not unions). */
443 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
444 && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
445 && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
446 && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
447 || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE
448 && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
449 && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
455 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
457 if (record_ptr_differ_p (a, b) || record_ptr_differ_p (b, a))
463 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
464 (a[i]). In case of p->c[i] use alias analysis to verify that p is not
466 if (record_array_differ_p (a, b) || record_array_differ_p (b, a))
472 /* Compare two record/union accesses (b.c[i] or p->c[i]). */
473 if (record_record_differ_p (a, b))
482 /* Function base_addr_differ_p.
484 This is the simplest data dependence test: determines whether the
485 data references DRA and DRB access the same array/region. Returns
486 false when the property is not computable at compile time.
487 Otherwise return true, and DIFFER_P will record the result.
490 1. if (both DRA and DRB are represented as arrays)
491 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT
492 2. else if (both DRA and DRB are represented as pointers)
493 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION
494 3. else if (DRA and DRB are represented differently or 2. fails)
495 only try to prove that the bases are surely different
499 base_addr_differ_p (struct data_reference *dra,
500 struct data_reference *drb,
503 tree addr_a = DR_BASE_ADDRESS (dra);
504 tree addr_b = DR_BASE_ADDRESS (drb);
509 if (!addr_a || !addr_b)
512 type_a = TREE_TYPE (addr_a);
513 type_b = TREE_TYPE (addr_b);
515 gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
517 /* 1. if (both DRA and DRB are represented as arrays)
518 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT. */
519 if (DR_TYPE (dra) == ARRAY_REF_TYPE && DR_TYPE (drb) == ARRAY_REF_TYPE)
520 return base_object_differ_p (dra, drb, differ_p);
522 /* 2. else if (both DRA and DRB are represented as pointers)
523 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION. */
524 /* If base addresses are the same, we check the offsets, since the access of
525 the data-ref is described by {base addr + offset} and its access function,
526 i.e., in order to decide whether the bases of data-refs are the same we
527 compare both base addresses and offsets. */
528 if (DR_TYPE (dra) == POINTER_REF_TYPE && DR_TYPE (drb) == POINTER_REF_TYPE
530 || (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR
531 && TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0))))
533 /* Compare offsets. */
534 tree offset_a = DR_OFFSET (dra);
535 tree offset_b = DR_OFFSET (drb);
537 STRIP_NOPS (offset_a);
538 STRIP_NOPS (offset_b);
540 /* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle
542 if (offset_a == offset_b
543 || (TREE_CODE (offset_a) == MULT_EXPR
544 && TREE_CODE (offset_b) == MULT_EXPR
545 && TREE_OPERAND (offset_a, 0) == TREE_OPERAND (offset_b, 0)
546 && TREE_OPERAND (offset_a, 1) == TREE_OPERAND (offset_b, 1)))
553 /* 3. else if (DRA and DRB are represented differently or 2. fails)
554 only try to prove that the bases are surely different. */
556 /* Apply alias analysis. */
557 if (may_alias_p (addr_a, addr_b, dra, drb, &aliased) && !aliased)
563 /* An instruction writing through a restricted pointer is "independent" of any
564 instruction reading or writing through a different restricted pointer,
565 in the same block/scope. */
566 else if (TYPE_RESTRICT (type_a)
567 && TYPE_RESTRICT (type_b)
568 && (!DR_IS_READ (drb) || !DR_IS_READ (dra))
569 && TREE_CODE (DR_BASE_ADDRESS (dra)) == SSA_NAME
570 && (decl_a = SSA_NAME_VAR (DR_BASE_ADDRESS (dra)))
571 && TREE_CODE (decl_a) == PARM_DECL
572 && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL
573 && TREE_CODE (DR_BASE_ADDRESS (drb)) == SSA_NAME
574 && (decl_b = SSA_NAME_VAR (DR_BASE_ADDRESS (drb)))
575 && TREE_CODE (decl_b) == PARM_DECL
576 && TREE_CODE (DECL_CONTEXT (decl_b)) == FUNCTION_DECL
577 && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b))
586 /* Returns true iff A divides B. */
589 tree_fold_divides_p (tree a, tree b)
591 gcc_assert (TREE_CODE (a) == INTEGER_CST);
592 gcc_assert (TREE_CODE (b) == INTEGER_CST);
593 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a, 0));
596 /* Returns true iff A divides B. */
599 int_divides_p (int a, int b)
601 return ((b % a) == 0);
606 /* Dump into FILE all the data references from DATAREFS. */
609 dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
612 struct data_reference *dr;
614 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
615 dump_data_reference (file, dr);
618 /* Dump into FILE all the dependence relations from DDRS. */
621 dump_data_dependence_relations (FILE *file,
622 VEC (ddr_p, heap) *ddrs)
625 struct data_dependence_relation *ddr;
627 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
628 dump_data_dependence_relation (file, ddr);
631 /* Dump function for a DATA_REFERENCE structure. */
634 dump_data_reference (FILE *outf,
635 struct data_reference *dr)
639 fprintf (outf, "(Data Ref: \n stmt: ");
640 print_generic_stmt (outf, DR_STMT (dr), 0);
641 fprintf (outf, " ref: ");
642 print_generic_stmt (outf, DR_REF (dr), 0);
643 fprintf (outf, " base_object: ");
644 print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
646 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
648 fprintf (outf, " Access function %d: ", i);
649 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
651 fprintf (outf, ")\n");
654 /* Dumps the affine function described by FN to the file OUTF. */
657 dump_affine_function (FILE *outf, affine_fn fn)
662 print_generic_expr (outf, VEC_index (tree, fn, 0), TDF_SLIM);
663 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
665 fprintf (outf, " + ");
666 print_generic_expr (outf, coef, TDF_SLIM);
667 fprintf (outf, " * x_%u", i);
671 /* Dumps the conflict function CF to the file OUTF. */
674 dump_conflict_function (FILE *outf, conflict_function *cf)
678 if (cf->n == NO_DEPENDENCE)
679 fprintf (outf, "no dependence\n");
680 else if (cf->n == NOT_KNOWN)
681 fprintf (outf, "not known\n");
684 for (i = 0; i < cf->n; i++)
687 dump_affine_function (outf, cf->fns[i]);
688 fprintf (outf, "]\n");
693 /* Dump function for a SUBSCRIPT structure. */
696 dump_subscript (FILE *outf, struct subscript *subscript)
698 conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
700 fprintf (outf, "\n (subscript \n");
701 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
702 dump_conflict_function (outf, cf);
703 if (CF_NONTRIVIAL_P (cf))
705 tree last_iteration = SUB_LAST_CONFLICT (subscript);
706 fprintf (outf, " last_conflict: ");
707 print_generic_stmt (outf, last_iteration, 0);
710 cf = SUB_CONFLICTS_IN_B (subscript);
711 fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
712 dump_conflict_function (outf, cf);
713 if (CF_NONTRIVIAL_P (cf))
715 tree last_iteration = SUB_LAST_CONFLICT (subscript);
716 fprintf (outf, " last_conflict: ");
717 print_generic_stmt (outf, last_iteration, 0);
720 fprintf (outf, " (Subscript distance: ");
721 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
722 fprintf (outf, " )\n");
723 fprintf (outf, " )\n");
726 /* Print the classic direction vector DIRV to OUTF. */
729 print_direction_vector (FILE *outf,
735 for (eq = 0; eq < length; eq++)
737 enum data_dependence_direction dir = dirv[eq];
742 fprintf (outf, " +");
745 fprintf (outf, " -");
748 fprintf (outf, " =");
750 case dir_positive_or_equal:
751 fprintf (outf, " +=");
753 case dir_positive_or_negative:
754 fprintf (outf, " +-");
756 case dir_negative_or_equal:
757 fprintf (outf, " -=");
760 fprintf (outf, " *");
763 fprintf (outf, "indep");
767 fprintf (outf, "\n");
770 /* Print a vector of direction vectors. */
773 print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
779 for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++)
780 print_direction_vector (outf, v, length);
783 /* Print a vector of distance vectors. */
786 print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
792 for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++)
793 print_lambda_vector (outf, v, length);
799 debug_data_dependence_relation (struct data_dependence_relation *ddr)
801 dump_data_dependence_relation (stderr, ddr);
804 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
807 dump_data_dependence_relation (FILE *outf,
808 struct data_dependence_relation *ddr)
810 struct data_reference *dra, *drb;
814 fprintf (outf, "(Data Dep: \n");
815 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
816 fprintf (outf, " (don't know)\n");
818 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
819 fprintf (outf, " (no dependence)\n");
821 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
826 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
828 fprintf (outf, " access_fn_A: ");
829 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
830 fprintf (outf, " access_fn_B: ");
831 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
832 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
835 fprintf (outf, " loop nest: (");
836 for (i = 0; VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
837 fprintf (outf, "%d ", loopi->num);
838 fprintf (outf, ")\n");
840 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
842 fprintf (outf, " distance_vector: ");
843 print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
847 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
849 fprintf (outf, " direction_vector: ");
850 print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
855 fprintf (outf, ")\n");
858 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
861 dump_data_dependence_direction (FILE *file,
862 enum data_dependence_direction dir)
878 case dir_positive_or_negative:
879 fprintf (file, "+-");
882 case dir_positive_or_equal:
883 fprintf (file, "+=");
886 case dir_negative_or_equal:
887 fprintf (file, "-=");
899 /* Dumps the distance and direction vectors in FILE. DDRS contains
900 the dependence relations, and VECT_SIZE is the size of the
901 dependence vectors, or in other words the number of loops in the
905 dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
908 struct data_dependence_relation *ddr;
911 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
912 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
914 for (j = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), j, v); j++)
916 fprintf (file, "DISTANCE_V (");
917 print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
918 fprintf (file, ")\n");
921 for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++)
923 fprintf (file, "DIRECTION_V (");
924 print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
925 fprintf (file, ")\n");
929 fprintf (file, "\n\n");
932 /* Dumps the data dependence relations DDRS in FILE. */
935 dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
938 struct data_dependence_relation *ddr;
940 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
941 dump_data_dependence_relation (file, ddr);
943 fprintf (file, "\n\n");
948 /* Given an ARRAY_REF node REF, records its access functions.
949 Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
950 i.e. the constant "3", then recursively call the function on opnd0,
951 i.e. the ARRAY_REF "A[i]".
952 The function returns the base name: "A". */
955 analyze_array_indexes (struct loop *loop,
956 VEC(tree,heap) **access_fns,
962 opnd0 = TREE_OPERAND (ref, 0);
963 opnd1 = TREE_OPERAND (ref, 1);
965 /* The detection of the evolution function for this data access is
966 postponed until the dependence test. This lazy strategy avoids
967 the computation of access functions that are of no interest for
969 access_fn = instantiate_parameters
970 (loop, analyze_scalar_evolution (loop, opnd1));
972 VEC_safe_push (tree, heap, *access_fns, access_fn);
974 /* Recursively record other array access functions. */
975 if (TREE_CODE (opnd0) == ARRAY_REF)
976 return analyze_array_indexes (loop, access_fns, opnd0, stmt);
978 /* Return the base name of the data access. */
983 /* For a data reference REF contained in the statement STMT, initialize
984 a DATA_REFERENCE structure, and return it. IS_READ flag has to be
985 set to true when REF is in the right hand side of an
988 struct data_reference *
989 analyze_array (tree stmt, tree ref, bool is_read)
991 struct data_reference *res;
992 VEC(tree,heap) *acc_fns;
994 if (dump_file && (dump_flags & TDF_DETAILS))
996 fprintf (dump_file, "(analyze_array \n");
997 fprintf (dump_file, " (ref = ");
998 print_generic_stmt (dump_file, ref, 0);
999 fprintf (dump_file, ")\n");
1002 res = XNEW (struct data_reference);
1004 DR_STMT (res) = stmt;
1006 acc_fns = VEC_alloc (tree, heap, 3);
1007 DR_BASE_OBJECT (res) = analyze_array_indexes
1008 (loop_containing_stmt (stmt), &acc_fns, ref, stmt);
1009 DR_TYPE (res) = ARRAY_REF_TYPE;
1010 DR_SET_ACCESS_FNS (res, acc_fns);
1011 DR_IS_READ (res) = is_read;
1012 DR_BASE_ADDRESS (res) = NULL_TREE;
1013 DR_OFFSET (res) = NULL_TREE;
1014 DR_INIT (res) = NULL_TREE;
1015 DR_STEP (res) = NULL_TREE;
1016 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
1017 DR_MEMTAG (res) = NULL_TREE;
1018 DR_PTR_INFO (res) = NULL;
1020 if (dump_file && (dump_flags & TDF_DETAILS))
1021 fprintf (dump_file, ")\n");
1026 /* Analyze an indirect memory reference, REF, that comes from STMT.
1027 IS_READ is true if this is an indirect load, and false if it is
1029 Return a new data reference structure representing the indirect_ref, or
1030 NULL if we cannot describe the access function. */
1032 static struct data_reference *
1033 analyze_indirect_ref (tree stmt, tree ref, bool is_read)
1035 struct loop *loop = loop_containing_stmt (stmt);
1036 tree ptr_ref = TREE_OPERAND (ref, 0);
1037 tree access_fn = analyze_scalar_evolution (loop, ptr_ref);
1038 tree init = initial_condition_in_loop_num (access_fn, loop->num);
1039 tree base_address = NULL_TREE, evolution, step = NULL_TREE;
1040 struct ptr_info_def *ptr_info = NULL;
1042 if (TREE_CODE (ptr_ref) == SSA_NAME)
1043 ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
1046 if (access_fn == chrec_dont_know || !init || init == chrec_dont_know)
1048 if (dump_file && (dump_flags & TDF_DETAILS))
1050 fprintf (dump_file, "\nBad access function of ptr: ");
1051 print_generic_expr (dump_file, ref, TDF_SLIM);
1052 fprintf (dump_file, "\n");
1057 if (dump_file && (dump_flags & TDF_DETAILS))
1059 fprintf (dump_file, "\nAccess function of ptr: ");
1060 print_generic_expr (dump_file, access_fn, TDF_SLIM);
1061 fprintf (dump_file, "\n");
1064 if (!expr_invariant_in_loop_p (loop, init))
1066 if (dump_file && (dump_flags & TDF_DETAILS))
1067 fprintf (dump_file, "\ninitial condition is not loop invariant.\n");
1071 base_address = init;
1072 evolution = evolution_part_in_loop_num (access_fn, loop->num);
1073 if (evolution != chrec_dont_know)
1076 step = ssize_int (0);
1079 if (TREE_CODE (evolution) == INTEGER_CST)
1080 step = fold_convert (ssizetype, evolution);
1082 if (dump_file && (dump_flags & TDF_DETAILS))
1083 fprintf (dump_file, "\nnon constant step for ptr access.\n");
1087 if (dump_file && (dump_flags & TDF_DETAILS))
1088 fprintf (dump_file, "\nunknown evolution of ptr.\n");
1090 return init_data_ref (stmt, ref, NULL_TREE, access_fn, is_read, base_address,
1091 NULL_TREE, step, NULL_TREE, NULL_TREE,
1092 ptr_info, POINTER_REF_TYPE);
1095 /* For a data reference REF contained in the statement STMT, initialize
1096 a DATA_REFERENCE structure, and return it. */
1098 struct data_reference *
1099 init_data_ref (tree stmt,
1109 struct ptr_info_def *ptr_info,
1110 enum data_ref_type type)
1112 struct data_reference *res;
1113 VEC(tree,heap) *acc_fns;
1115 if (dump_file && (dump_flags & TDF_DETAILS))
1117 fprintf (dump_file, "(init_data_ref \n");
1118 fprintf (dump_file, " (ref = ");
1119 print_generic_stmt (dump_file, ref, 0);
1120 fprintf (dump_file, ")\n");
1123 res = XNEW (struct data_reference);
1125 DR_STMT (res) = stmt;
1127 DR_BASE_OBJECT (res) = base;
1128 DR_TYPE (res) = type;
1129 acc_fns = VEC_alloc (tree, heap, 3);
1130 DR_SET_ACCESS_FNS (res, acc_fns);
1131 VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
1132 DR_IS_READ (res) = is_read;
1133 DR_BASE_ADDRESS (res) = base_address;
1134 DR_OFFSET (res) = init_offset;
1135 DR_INIT (res) = NULL_TREE;
1136 DR_STEP (res) = step;
1137 DR_OFFSET_MISALIGNMENT (res) = misalign;
1138 DR_MEMTAG (res) = memtag;
1139 DR_PTR_INFO (res) = ptr_info;
1141 if (dump_file && (dump_flags & TDF_DETAILS))
1142 fprintf (dump_file, ")\n");
1147 /* Function strip_conversions
1149 Strip conversions that don't narrow the mode. */
1152 strip_conversion (tree expr)
1154 tree to, ti, oprnd0;
1156 while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
1158 to = TREE_TYPE (expr);
1159 oprnd0 = TREE_OPERAND (expr, 0);
1160 ti = TREE_TYPE (oprnd0);
1162 if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti))
1164 if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti)))
1173 /* Function analyze_offset_expr
1175 Given an offset expression EXPR received from get_inner_reference, analyze
1176 it and create an expression for INITIAL_OFFSET by substituting the variables
1177 of EXPR with initial_condition of the corresponding access_fn in the loop.
1180 for (j = 3; j < N; j++)
1183 For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be
1184 substituted, since its access_fn in the inner loop is i. 'j' will be
1185 substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
1188 Compute MISALIGN (the misalignment of the data reference initial access from
1189 its base). Misalignment can be calculated only if all the variables can be
1190 substituted with constants, otherwise, we record maximum possible alignment
1191 in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN
1192 will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be
1193 recorded in ALIGNED_TO.
1195 STEP is an evolution of the data reference in this loop in bytes.
1196 In the above example, STEP is C_j.
1198 Return FALSE, if the analysis fails, e.g., there is no access_fn for a
1199 variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO
1200 and STEP) are NULL_TREEs. Otherwise, return TRUE.
1205 analyze_offset_expr (tree expr,
1207 tree *initial_offset,
1214 tree left_offset = ssize_int (0);
1215 tree right_offset = ssize_int (0);
1216 tree left_misalign = ssize_int (0);
1217 tree right_misalign = ssize_int (0);
1218 tree left_step = ssize_int (0);
1219 tree right_step = ssize_int (0);
1220 enum tree_code code;
1221 tree init, evolution;
1222 tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE;
1225 *misalign = NULL_TREE;
1226 *aligned_to = NULL_TREE;
1227 *initial_offset = NULL_TREE;
1229 /* Strip conversions that don't narrow the mode. */
1230 expr = strip_conversion (expr);
1236 if (TREE_CODE (expr) == INTEGER_CST)
1238 *initial_offset = fold_convert (ssizetype, expr);
1239 *misalign = fold_convert (ssizetype, expr);
1240 *step = ssize_int (0);
1244 /* 2. Variable. Try to substitute with initial_condition of the corresponding
1245 access_fn in the current loop. */
1246 if (SSA_VAR_P (expr))
1248 tree access_fn = analyze_scalar_evolution (loop, expr);
1250 if (access_fn == chrec_dont_know)
1254 init = initial_condition_in_loop_num (access_fn, loop->num);
1255 if (!expr_invariant_in_loop_p (loop, init))
1256 /* Not enough information: may be not loop invariant.
1257 E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
1258 initial_condition is D, but it depends on i - loop's induction
1262 evolution = evolution_part_in_loop_num (access_fn, loop->num);
1263 if (evolution && TREE_CODE (evolution) != INTEGER_CST)
1264 /* Evolution is not constant. */
1267 if (TREE_CODE (init) == INTEGER_CST)
1268 *misalign = fold_convert (ssizetype, init);
1270 /* Not constant, misalignment cannot be calculated. */
1271 *misalign = NULL_TREE;
1273 *initial_offset = fold_convert (ssizetype, init);
1275 *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
1279 /* Recursive computation. */
1280 if (!BINARY_CLASS_P (expr))
1282 /* We expect to get binary expressions (PLUS/MINUS and MULT). */
1283 if (dump_file && (dump_flags & TDF_DETAILS))
1285 fprintf (dump_file, "\nNot binary expression ");
1286 print_generic_expr (dump_file, expr, TDF_SLIM);
1287 fprintf (dump_file, "\n");
1291 oprnd0 = TREE_OPERAND (expr, 0);
1292 oprnd1 = TREE_OPERAND (expr, 1);
1294 if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign,
1295 &left_aligned_to, &left_step)
1296 || !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign,
1297 &right_aligned_to, &right_step))
1300 /* The type of the operation: plus, minus or mult. */
1301 code = TREE_CODE (expr);
1305 if (TREE_CODE (right_offset) != INTEGER_CST)
1306 /* RIGHT_OFFSET can be not constant. For example, for arrays of variable
1308 FORNOW: We don't support such cases. */
1311 /* Strip conversions that don't narrow the mode. */
1312 left_offset = strip_conversion (left_offset);
1315 /* Misalignment computation. */
1316 if (SSA_VAR_P (left_offset))
1318 /* If the left side contains variables that can't be substituted with
1319 constants, the misalignment is unknown. However, if the right side
1320 is a multiple of some alignment, we know that the expression is
1321 aligned to it. Therefore, we record such maximum possible value.
1323 *misalign = NULL_TREE;
1324 *aligned_to = ssize_int (highest_pow2_factor (right_offset));
1328 /* The left operand was successfully substituted with constant. */
1331 /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is
1333 *misalign = size_binop (code, left_misalign, right_misalign);
1334 if (left_aligned_to && right_aligned_to)
1335 *aligned_to = size_binop (MIN_EXPR, left_aligned_to,
1338 *aligned_to = left_aligned_to ?
1339 left_aligned_to : right_aligned_to;
1342 *misalign = NULL_TREE;
1345 /* Step calculation. */
1346 /* Multiply the step by the right operand. */
1347 *step = size_binop (MULT_EXPR, left_step, right_offset);
1352 /* Combine the recursive calculations for step and misalignment. */
1353 *step = size_binop (code, left_step, right_step);
1355 /* Unknown alignment. */
1356 if ((!left_misalign && !left_aligned_to)
1357 || (!right_misalign && !right_aligned_to))
1359 *misalign = NULL_TREE;
1360 *aligned_to = NULL_TREE;
1364 if (left_misalign && right_misalign)
1365 *misalign = size_binop (code, left_misalign, right_misalign);
1367 *misalign = left_misalign ? left_misalign : right_misalign;
1369 if (left_aligned_to && right_aligned_to)
1370 *aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to);
1372 *aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to;
1380 /* Compute offset. */
1381 *initial_offset = fold_convert (ssizetype,
1382 fold_build2 (code, TREE_TYPE (left_offset),
1388 /* Function address_analysis
1390 Return the BASE of the address expression EXPR.
1391 Also compute the OFFSET from BASE, MISALIGN and STEP.
1394 EXPR - the address expression that is being analyzed
1395 STMT - the statement that contains EXPR or its original memory reference
1396 IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
1397 DR - data_reference struct for the original memory reference
1400 BASE (returned value) - the base of the data reference EXPR.
1401 INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
1402 MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
1403 computation is impossible
1404 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1405 calculated (doesn't depend on variables)
1406 STEP - evolution of EXPR in the loop
1408 If something unexpected is encountered (an unsupported form of data-ref),
1409 then NULL_TREE is returned.
1413 address_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr,
1414 tree *offset, tree *misalign, tree *aligned_to, tree *step)
1416 tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
1417 tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1418 tree dummy, address_aligned_to = NULL_TREE;
1419 struct ptr_info_def *dummy1;
1422 switch (TREE_CODE (expr))
1426 /* EXPR is of form {base +/- offset} (or {offset +/- base}). */
1427 oprnd0 = TREE_OPERAND (expr, 0);
1428 oprnd1 = TREE_OPERAND (expr, 1);
1430 STRIP_NOPS (oprnd0);
1431 STRIP_NOPS (oprnd1);
1433 /* Recursively try to find the base of the address contained in EXPR.
1434 For offset, the returned base will be NULL. */
1435 base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset,
1436 &address_misalign, &address_aligned_to,
1439 base_addr1 = address_analysis (oprnd1, stmt, is_read, dr, &address_offset,
1440 &address_misalign, &address_aligned_to,
1443 /* We support cases where only one of the operands contains an
1445 if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
1447 if (dump_file && (dump_flags & TDF_DETAILS))
1450 "\neither more than one address or no addresses in expr ");
1451 print_generic_expr (dump_file, expr, TDF_SLIM);
1452 fprintf (dump_file, "\n");
1457 /* To revert STRIP_NOPS. */
1458 oprnd0 = TREE_OPERAND (expr, 0);
1459 oprnd1 = TREE_OPERAND (expr, 1);
1461 offset_expr = base_addr0 ?
1462 fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
1464 /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is
1465 a number, we can add it to the misalignment value calculated for base,
1466 otherwise, misalignment is NULL. */
1467 if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
1469 *misalign = size_binop (TREE_CODE (expr), address_misalign,
1471 *aligned_to = address_aligned_to;
1475 *misalign = NULL_TREE;
1476 *aligned_to = NULL_TREE;
1479 /* Combine offset (from EXPR {base + offset}) with the offset calculated
1481 *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
1482 return base_addr0 ? base_addr0 : base_addr1;
1485 base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read,
1486 &dr, offset, misalign, aligned_to, step,
1487 &dummy, &dummy1, &dummy2);
1488 return base_address;
1491 if (!POINTER_TYPE_P (TREE_TYPE (expr)))
1493 if (dump_file && (dump_flags & TDF_DETAILS))
1495 fprintf (dump_file, "\nnot pointer SSA_NAME ");
1496 print_generic_expr (dump_file, expr, TDF_SLIM);
1497 fprintf (dump_file, "\n");
1501 *aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr))));
1502 *misalign = ssize_int (0);
1503 *offset = ssize_int (0);
1504 *step = ssize_int (0);
1513 /* Function object_analysis
1515 Create a data-reference structure DR for MEMREF.
1516 Return the BASE of the data reference MEMREF if the analysis is possible.
1517 Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1518 E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset
1519 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET
1520 instantiated with initial_conditions of access_functions of variables,
1521 and STEP is the evolution of the DR_REF in this loop.
1523 Function get_inner_reference is used for the above in case of ARRAY_REF and
1526 The structure of the function is as follows:
1528 Case 1. For handled_component_p refs
1529 1.1 build data-reference structure for MEMREF
1530 1.2 call get_inner_reference
1531 1.2.1 analyze offset expr received from get_inner_reference
1532 (fall through with BASE)
1533 Case 2. For declarations
1535 Case 3. For INDIRECT_REFs
1536 3.1 build data-reference structure for MEMREF
1537 3.2 analyze evolution and initial condition of MEMREF
1538 3.3 set data-reference structure for MEMREF
1539 3.4 call address_analysis to analyze INIT of the access function
1540 3.5 extract memory tag
1543 Combine the results of object and address analysis to calculate
1544 INITIAL_OFFSET, STEP and misalignment info.
1547 MEMREF - the memory reference that is being analyzed
1548 STMT - the statement that contains MEMREF
1549 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1552 BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
1553 E.g, if MEMREF is a.b[k].c[i][j] the returned
1555 DR - data_reference struct for MEMREF
1556 INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
1557 MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of
1558 ALIGNMENT or NULL_TREE if the computation is impossible
1559 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1560 calculated (doesn't depend on variables)
1561 STEP - evolution of the DR_REF in the loop
1562 MEMTAG - memory tag for aliasing purposes
1563 PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
1564 SUBVARS - Sub-variables of the variable
1566 If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned,
1567 but DR can be created anyway.
1572 object_analysis (tree memref, tree stmt, bool is_read,
1573 struct data_reference **dr, tree *offset, tree *misalign,
1574 tree *aligned_to, tree *step, tree *memtag,
1575 struct ptr_info_def **ptr_info, subvar_t *subvars)
1577 tree base = NULL_TREE, base_address = NULL_TREE;
1578 tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
1579 tree object_step = ssize_int (0), address_step = ssize_int (0);
1580 tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1581 HOST_WIDE_INT pbitsize, pbitpos;
1582 tree poffset, bit_pos_in_bytes;
1583 enum machine_mode pmode;
1584 int punsignedp, pvolatilep;
1585 tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
1586 struct loop *loop = loop_containing_stmt (stmt);
1587 struct data_reference *ptr_dr = NULL;
1588 tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE;
1589 tree comp_ref = NULL_TREE;
1594 /* Case 1. handled_component_p refs. */
1595 if (handled_component_p (memref))
1597 /* 1.1 build data-reference structure for MEMREF. */
1600 if (TREE_CODE (memref) == ARRAY_REF)
1601 *dr = analyze_array (stmt, memref, is_read);
1602 else if (TREE_CODE (memref) == COMPONENT_REF)
1606 if (dump_file && (dump_flags & TDF_DETAILS))
1608 fprintf (dump_file, "\ndata-ref of unsupported type ");
1609 print_generic_expr (dump_file, memref, TDF_SLIM);
1610 fprintf (dump_file, "\n");
1616 /* 1.2 call get_inner_reference. */
1617 /* Find the base and the offset from it. */
1618 base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
1619 &pmode, &punsignedp, &pvolatilep, false);
1622 if (dump_file && (dump_flags & TDF_DETAILS))
1624 fprintf (dump_file, "\nfailed to get inner ref for ");
1625 print_generic_expr (dump_file, memref, TDF_SLIM);
1626 fprintf (dump_file, "\n");
1631 /* 1.2.1 analyze offset expr received from get_inner_reference. */
1633 && !analyze_offset_expr (poffset, loop, &object_offset,
1634 &object_misalign, &object_aligned_to,
1637 if (dump_file && (dump_flags & TDF_DETAILS))
1639 fprintf (dump_file, "\nfailed to compute offset or step for ");
1640 print_generic_expr (dump_file, memref, TDF_SLIM);
1641 fprintf (dump_file, "\n");
1646 /* Add bit position to OFFSET and MISALIGN. */
1648 bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
1649 /* Check that there is no remainder in bits. */
1650 if (pbitpos%BITS_PER_UNIT)
1652 if (dump_file && (dump_flags & TDF_DETAILS))
1653 fprintf (dump_file, "\nbit offset alignment.\n");
1656 object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);
1657 if (object_misalign)
1658 object_misalign = size_binop (PLUS_EXPR, object_misalign,
1661 memref = base; /* To continue analysis of BASE. */
1665 /* Part 1: Case 2. Declarations. */
1666 if (DECL_P (memref))
1668 /* We expect to get a decl only if we already have a DR, or with
1669 COMPONENT_REFs of type 'a[i].b'. */
1672 if (comp_ref && TREE_CODE (TREE_OPERAND (comp_ref, 0)) == ARRAY_REF)
1674 *dr = analyze_array (stmt, TREE_OPERAND (comp_ref, 0), is_read);
1675 if (DR_NUM_DIMENSIONS (*dr) != 1)
1677 if (dump_file && (dump_flags & TDF_DETAILS))
1679 fprintf (dump_file, "\n multidimensional component ref ");
1680 print_generic_expr (dump_file, comp_ref, TDF_SLIM);
1681 fprintf (dump_file, "\n");
1688 if (dump_file && (dump_flags & TDF_DETAILS))
1690 fprintf (dump_file, "\nunhandled decl ");
1691 print_generic_expr (dump_file, memref, TDF_SLIM);
1692 fprintf (dump_file, "\n");
1698 /* TODO: if during the analysis of INDIRECT_REF we get to an object, put
1699 the object in BASE_OBJECT field if we can prove that this is O.K.,
1700 i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT.
1701 (e.g., if the object is an array base 'a', where 'a[N]', we must prove
1702 that every access with 'p' (the original INDIRECT_REF based on '&a')
1703 in the loop is within the array boundaries - from a[0] to a[N-1]).
1704 Otherwise, our alias analysis can be incorrect.
1705 Even if an access function based on BASE_OBJECT can't be build, update
1706 BASE_OBJECT field to enable us to prove that two data-refs are
1707 different (without access function, distance analysis is impossible).
1709 if (SSA_VAR_P (memref) && var_can_have_subvars (memref))
1710 *subvars = get_subvars_for_var (memref);
1711 base_address = build_fold_addr_expr (memref);
1712 /* 2.1 set MEMTAG. */
1716 /* Part 1: Case 3. INDIRECT_REFs. */
1717 else if (TREE_CODE (memref) == INDIRECT_REF)
1719 tree ptr_ref = TREE_OPERAND (memref, 0);
1720 if (TREE_CODE (ptr_ref) == SSA_NAME)
1721 *ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
1723 /* 3.1 build data-reference structure for MEMREF. */
1724 ptr_dr = analyze_indirect_ref (stmt, memref, is_read);
1727 if (dump_file && (dump_flags & TDF_DETAILS))
1729 fprintf (dump_file, "\nfailed to create dr for ");
1730 print_generic_expr (dump_file, memref, TDF_SLIM);
1731 fprintf (dump_file, "\n");
1736 /* 3.2 analyze evolution and initial condition of MEMREF. */
1737 ptr_step = DR_STEP (ptr_dr);
1738 ptr_init = DR_BASE_ADDRESS (ptr_dr);
1739 if (!ptr_init || !ptr_step || !POINTER_TYPE_P (TREE_TYPE (ptr_init)))
1741 *dr = (*dr) ? *dr : ptr_dr;
1742 if (dump_file && (dump_flags & TDF_DETAILS))
1744 fprintf (dump_file, "\nbad pointer access ");
1745 print_generic_expr (dump_file, memref, TDF_SLIM);
1746 fprintf (dump_file, "\n");
1751 if (integer_zerop (ptr_step) && !(*dr))
1753 if (dump_file && (dump_flags & TDF_DETAILS))
1754 fprintf (dump_file, "\nptr is loop invariant.\n");
1758 /* If there exists DR for MEMREF, we are analyzing the base of
1759 handled component (PTR_INIT), which not necessary has evolution in
1762 object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
1764 /* 3.3 set data-reference structure for MEMREF. */
1768 /* 3.4 call address_analysis to analyze INIT of the access
1770 base_address = address_analysis (ptr_init, stmt, is_read, *dr,
1771 &address_offset, &address_misalign,
1772 &address_aligned_to, &address_step);
1775 if (dump_file && (dump_flags & TDF_DETAILS))
1777 fprintf (dump_file, "\nfailed to analyze address ");
1778 print_generic_expr (dump_file, ptr_init, TDF_SLIM);
1779 fprintf (dump_file, "\n");
1784 /* 3.5 extract memory tag. */
1785 switch (TREE_CODE (base_address))
1788 *memtag = symbol_mem_tag (SSA_NAME_VAR (base_address));
1789 if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
1790 *memtag = symbol_mem_tag (SSA_NAME_VAR (TREE_OPERAND (memref, 0)));
1793 *memtag = TREE_OPERAND (base_address, 0);
1796 if (dump_file && (dump_flags & TDF_DETAILS))
1798 fprintf (dump_file, "\nno memtag for ");
1799 print_generic_expr (dump_file, memref, TDF_SLIM);
1800 fprintf (dump_file, "\n");
1802 *memtag = NULL_TREE;
1809 /* MEMREF cannot be analyzed. */
1810 if (dump_file && (dump_flags & TDF_DETAILS))
1812 fprintf (dump_file, "\ndata-ref of unsupported type ");
1813 print_generic_expr (dump_file, memref, TDF_SLIM);
1814 fprintf (dump_file, "\n");
1820 DR_REF (*dr) = comp_ref;
1822 if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag))
1823 *subvars = get_subvars_for_var (*memtag);
1825 /* Part 2: Combine the results of object and address analysis to calculate
1826 INITIAL_OFFSET, STEP and misalignment info. */
1827 *offset = size_binop (PLUS_EXPR, object_offset, address_offset);
1829 if ((!object_misalign && !object_aligned_to)
1830 || (!address_misalign && !address_aligned_to))
1832 *misalign = NULL_TREE;
1833 *aligned_to = NULL_TREE;
1837 if (object_misalign && address_misalign)
1838 *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
1840 *misalign = object_misalign ? object_misalign : address_misalign;
1841 if (object_aligned_to && address_aligned_to)
1842 *aligned_to = size_binop (MIN_EXPR, object_aligned_to,
1843 address_aligned_to);
1845 *aligned_to = object_aligned_to ?
1846 object_aligned_to : address_aligned_to;
1848 *step = size_binop (PLUS_EXPR, object_step, address_step);
1850 return base_address;
1853 /* Function analyze_offset.
1855 Extract INVARIANT and CONSTANT parts from OFFSET.
1859 analyze_offset (tree offset, tree *invariant, tree *constant)
1861 tree op0, op1, constant_0, constant_1, invariant_0, invariant_1;
1862 enum tree_code code = TREE_CODE (offset);
1864 *invariant = NULL_TREE;
1865 *constant = NULL_TREE;
1867 /* Not PLUS/MINUS expression - recursion stop condition. */
1868 if (code != PLUS_EXPR && code != MINUS_EXPR)
1870 if (TREE_CODE (offset) == INTEGER_CST)
1873 *invariant = offset;
1877 op0 = TREE_OPERAND (offset, 0);
1878 op1 = TREE_OPERAND (offset, 1);
1880 /* Recursive call with the operands. */
1881 analyze_offset (op0, &invariant_0, &constant_0);
1882 analyze_offset (op1, &invariant_1, &constant_1);
1884 /* Combine the results. */
1885 *constant = constant_0 ? constant_0 : constant_1;
1886 if (invariant_0 && invariant_1)
1888 fold_build2 (code, TREE_TYPE (invariant_0), invariant_0, invariant_1);
1890 *invariant = invariant_0 ? invariant_0 : invariant_1;
1893 /* Free the memory used by the data reference DR. */
1896 free_data_ref (data_reference_p dr)
1898 DR_FREE_ACCESS_FNS (dr);
1902 /* Function create_data_ref.
1904 Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS,
1905 DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO,
1906 DR_MEMTAG, and DR_POINTSTO_INFO fields.
1909 MEMREF - the memory reference that is being analyzed
1910 STMT - the statement that contains MEMREF
1911 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1914 DR (returned value) - data_reference struct for MEMREF
1917 static struct data_reference *
1918 create_data_ref (tree memref, tree stmt, bool is_read)
1920 struct data_reference *dr = NULL;
1921 tree base_address, offset, step, misalign, memtag;
1922 struct loop *loop = loop_containing_stmt (stmt);
1923 tree invariant = NULL_TREE, constant = NULL_TREE;
1924 tree type_size, init_cond;
1925 struct ptr_info_def *ptr_info;
1926 subvar_t subvars = NULL;
1927 tree aligned_to, type = NULL_TREE, orig_offset;
1932 base_address = object_analysis (memref, stmt, is_read, &dr, &offset,
1933 &misalign, &aligned_to, &step, &memtag,
1934 &ptr_info, &subvars);
1935 if (!dr || !base_address)
1937 if (dump_file && (dump_flags & TDF_DETAILS))
1939 fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for ");
1940 print_generic_expr (dump_file, memref, TDF_SLIM);
1941 fprintf (dump_file, "\n");
1946 DR_BASE_ADDRESS (dr) = base_address;
1947 DR_OFFSET (dr) = offset;
1948 DR_INIT (dr) = ssize_int (0);
1949 DR_STEP (dr) = step;
1950 DR_OFFSET_MISALIGNMENT (dr) = misalign;
1951 DR_ALIGNED_TO (dr) = aligned_to;
1952 DR_MEMTAG (dr) = memtag;
1953 DR_PTR_INFO (dr) = ptr_info;
1954 DR_SUBVARS (dr) = subvars;
1956 type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
1958 /* Extract CONSTANT and INVARIANT from OFFSET. */
1959 /* Remove cast from OFFSET and restore it for INVARIANT part. */
1960 orig_offset = offset;
1961 STRIP_NOPS (offset);
1962 if (offset != orig_offset)
1963 type = TREE_TYPE (orig_offset);
1964 analyze_offset (offset, &invariant, &constant);
1965 if (type && invariant)
1966 invariant = fold_convert (type, invariant);
1968 /* Put CONSTANT part of OFFSET in DR_INIT and INVARIANT in DR_OFFSET field
1972 DR_INIT (dr) = fold_convert (ssizetype, constant);
1973 init_cond = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (constant),
1974 constant, type_size);
1977 DR_INIT (dr) = init_cond = ssize_int (0);
1980 DR_OFFSET (dr) = invariant;
1982 DR_OFFSET (dr) = ssize_int (0);
1984 /* Change the access function for INIDIRECT_REFs, according to
1985 DR_BASE_ADDRESS. Analyze OFFSET calculated in object_analysis. OFFSET is
1986 an expression that can contain loop invariant expressions and constants.
1987 We put the constant part in the initial condition of the access function
1988 (for data dependence tests), and in DR_INIT of the data-ref. The loop
1989 invariant part is put in DR_OFFSET.
1990 The evolution part of the access function is STEP calculated in
1991 object_analysis divided by the size of data type.
1993 if (!DR_BASE_OBJECT (dr)
1994 || (TREE_CODE (memref) == COMPONENT_REF && DR_NUM_DIMENSIONS (dr) == 1))
1999 /* Update access function. */
2000 access_fn = DR_ACCESS_FN (dr, 0);
2001 if (automatically_generated_chrec_p (access_fn))
2007 new_step = size_binop (TRUNC_DIV_EXPR,
2008 fold_convert (ssizetype, step), type_size);
2010 init_cond = chrec_convert (chrec_type (access_fn), init_cond, stmt);
2011 new_step = chrec_convert (chrec_type (access_fn), new_step, stmt);
2012 if (automatically_generated_chrec_p (init_cond)
2013 || automatically_generated_chrec_p (new_step))
2018 access_fn = chrec_replace_initial_condition (access_fn, init_cond);
2019 access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step);
2021 VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn);
2024 if (dump_file && (dump_flags & TDF_DETAILS))
2026 struct ptr_info_def *pi = DR_PTR_INFO (dr);
2028 fprintf (dump_file, "\nCreated dr for ");
2029 print_generic_expr (dump_file, memref, TDF_SLIM);
2030 fprintf (dump_file, "\n\tbase_address: ");
2031 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
2032 fprintf (dump_file, "\n\toffset from base address: ");
2033 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
2034 fprintf (dump_file, "\n\tconstant offset from base address: ");
2035 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
2036 fprintf (dump_file, "\n\tbase_object: ");
2037 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
2038 fprintf (dump_file, "\n\tstep: ");
2039 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
2040 fprintf (dump_file, "B\n\tmisalignment from base: ");
2041 print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM);
2042 if (DR_OFFSET_MISALIGNMENT (dr))
2043 fprintf (dump_file, "B");
2044 if (DR_ALIGNED_TO (dr))
2046 fprintf (dump_file, "\n\taligned to: ");
2047 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
2049 fprintf (dump_file, "\n\tmemtag: ");
2050 print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM);
2051 fprintf (dump_file, "\n");
2052 if (pi && pi->name_mem_tag)
2054 fprintf (dump_file, "\n\tnametag: ");
2055 print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM);
2056 fprintf (dump_file, "\n");
2062 /* Returns true if FNA == FNB. */
2065 affine_function_equal_p (affine_fn fna, affine_fn fnb)
2067 unsigned i, n = VEC_length (tree, fna);
2069 gcc_assert (n == VEC_length (tree, fnb));
2071 for (i = 0; i < n; i++)
2072 if (!operand_equal_p (VEC_index (tree, fna, i),
2073 VEC_index (tree, fnb, i), 0))
2079 /* If all the functions in CF are the same, returns one of them,
2080 otherwise returns NULL. */
2083 common_affine_function (conflict_function *cf)
2088 if (!CF_NONTRIVIAL_P (cf))
2093 for (i = 1; i < cf->n; i++)
2094 if (!affine_function_equal_p (comm, cf->fns[i]))
2100 /* Returns the base of the affine function FN. */
2103 affine_function_base (affine_fn fn)
2105 return VEC_index (tree, fn, 0);
2108 /* Returns true if FN is a constant. */
2111 affine_function_constant_p (affine_fn fn)
2116 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
2117 if (!integer_zerop (coef))
2123 /* Applies operation OP on affine functions FNA and FNB, and returns the
2127 affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
2133 if (VEC_length (tree, fnb) > VEC_length (tree, fna))
2135 n = VEC_length (tree, fna);
2136 m = VEC_length (tree, fnb);
2140 n = VEC_length (tree, fnb);
2141 m = VEC_length (tree, fna);
2144 ret = VEC_alloc (tree, heap, m);
2145 for (i = 0; i < n; i++)
2146 VEC_quick_push (tree, ret,
2147 fold_build2 (op, integer_type_node,
2148 VEC_index (tree, fna, i),
2149 VEC_index (tree, fnb, i)));
2151 for (; VEC_iterate (tree, fna, i, coef); i++)
2152 VEC_quick_push (tree, ret,
2153 fold_build2 (op, integer_type_node,
2154 coef, integer_zero_node));
2155 for (; VEC_iterate (tree, fnb, i, coef); i++)
2156 VEC_quick_push (tree, ret,
2157 fold_build2 (op, integer_type_node,
2158 integer_zero_node, coef));
2163 /* Returns the sum of affine functions FNA and FNB. */
2166 affine_fn_plus (affine_fn fna, affine_fn fnb)
2168 return affine_fn_op (PLUS_EXPR, fna, fnb);
2171 /* Returns the difference of affine functions FNA and FNB. */
2174 affine_fn_minus (affine_fn fna, affine_fn fnb)
2176 return affine_fn_op (MINUS_EXPR, fna, fnb);
2179 /* Frees affine function FN. */
2182 affine_fn_free (affine_fn fn)
2184 VEC_free (tree, heap, fn);
2187 /* Determine for each subscript in the data dependence relation DDR
2191 compute_subscript_distance (struct data_dependence_relation *ddr)
2193 conflict_function *cf_a, *cf_b;
2194 affine_fn fn_a, fn_b, diff;
2196 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
2200 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2202 struct subscript *subscript;
2204 subscript = DDR_SUBSCRIPT (ddr, i);
2205 cf_a = SUB_CONFLICTS_IN_A (subscript);
2206 cf_b = SUB_CONFLICTS_IN_B (subscript);
2208 fn_a = common_affine_function (cf_a);
2209 fn_b = common_affine_function (cf_b);
2212 SUB_DISTANCE (subscript) = chrec_dont_know;
2215 diff = affine_fn_minus (fn_a, fn_b);
2217 if (affine_function_constant_p (diff))
2218 SUB_DISTANCE (subscript) = affine_function_base (diff);
2220 SUB_DISTANCE (subscript) = chrec_dont_know;
2222 affine_fn_free (diff);
2227 /* Returns the conflict function for "unknown". */
2229 static conflict_function *
2230 conflict_fn_not_known (void)
2232 conflict_function *fn = XCNEW (conflict_function);
2238 /* Returns the conflict function for "independent". */
2240 static conflict_function *
2241 conflict_fn_no_dependence (void)
2243 conflict_function *fn = XCNEW (conflict_function);
2244 fn->n = NO_DEPENDENCE;
2249 /* Initialize a data dependence relation between data accesses A and
2250 B. NB_LOOPS is the number of loops surrounding the references: the
2251 size of the classic distance/direction vectors. */
2253 static struct data_dependence_relation *
2254 initialize_data_dependence_relation (struct data_reference *a,
2255 struct data_reference *b,
2256 VEC (loop_p, heap) *loop_nest)
2258 struct data_dependence_relation *res;
2259 bool differ_p, known_dependence;
2262 res = XNEW (struct data_dependence_relation);
2265 DDR_LOOP_NEST (res) = NULL;
2267 if (a == NULL || b == NULL)
2269 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
2273 /* When A and B are arrays and their dimensions differ, we directly
2274 initialize the relation to "there is no dependence": chrec_known. */
2275 if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
2276 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
2278 DDR_ARE_DEPENDENT (res) = chrec_known;
2282 if (DR_BASE_ADDRESS (a) && DR_BASE_ADDRESS (b))
2283 known_dependence = base_addr_differ_p (a, b, &differ_p);
2285 known_dependence = base_object_differ_p (a, b, &differ_p);
2287 if (!known_dependence)
2289 /* Can't determine whether the data-refs access the same memory
2291 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
2297 DDR_ARE_DEPENDENT (res) = chrec_known;
2301 DDR_AFFINE_P (res) = true;
2302 DDR_ARE_DEPENDENT (res) = NULL_TREE;
2303 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
2304 DDR_LOOP_NEST (res) = loop_nest;
2305 DDR_DIR_VECTS (res) = NULL;
2306 DDR_DIST_VECTS (res) = NULL;
2308 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
2310 struct subscript *subscript;
2312 subscript = XNEW (struct subscript);
2313 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
2314 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
2315 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
2316 SUB_DISTANCE (subscript) = chrec_dont_know;
2317 VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
2323 /* Frees memory used by the conflict function F. */
2326 free_conflict_function (conflict_function *f)
2330 if (CF_NONTRIVIAL_P (f))
2332 for (i = 0; i < f->n; i++)
2333 affine_fn_free (f->fns[i]);
2338 /* Frees memory used by SUBSCRIPTS. */
2341 free_subscripts (VEC (subscript_p, heap) *subscripts)
2346 for (i = 0; VEC_iterate (subscript_p, subscripts, i, s); i++)
2348 free_conflict_function (s->conflicting_iterations_in_a);
2349 free_conflict_function (s->conflicting_iterations_in_b);
2351 VEC_free (subscript_p, heap, subscripts);
2354 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
2358 finalize_ddr_dependent (struct data_dependence_relation *ddr,
2361 if (dump_file && (dump_flags & TDF_DETAILS))
2363 fprintf (dump_file, "(dependence classified: ");
2364 print_generic_expr (dump_file, chrec, 0);
2365 fprintf (dump_file, ")\n");
2368 DDR_ARE_DEPENDENT (ddr) = chrec;
2369 free_subscripts (DDR_SUBSCRIPTS (ddr));
2372 /* The dependence relation DDR cannot be represented by a distance
2376 non_affine_dependence_relation (struct data_dependence_relation *ddr)
2378 if (dump_file && (dump_flags & TDF_DETAILS))
2379 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
2381 DDR_AFFINE_P (ddr) = false;
2386 /* This section contains the classic Banerjee tests. */
2388 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
2389 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
2392 ziv_subscript_p (tree chrec_a,
2395 return (evolution_function_is_constant_p (chrec_a)
2396 && evolution_function_is_constant_p (chrec_b));
2399 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
2400 variable, i.e., if the SIV (Single Index Variable) test is true. */
2403 siv_subscript_p (tree chrec_a,
2406 if ((evolution_function_is_constant_p (chrec_a)
2407 && evolution_function_is_univariate_p (chrec_b))
2408 || (evolution_function_is_constant_p (chrec_b)
2409 && evolution_function_is_univariate_p (chrec_a)))
2412 if (evolution_function_is_univariate_p (chrec_a)
2413 && evolution_function_is_univariate_p (chrec_b))
2415 switch (TREE_CODE (chrec_a))
2417 case POLYNOMIAL_CHREC:
2418 switch (TREE_CODE (chrec_b))
2420 case POLYNOMIAL_CHREC:
2421 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
2436 /* Creates a conflict function with N dimensions. The affine functions
2437 in each dimension follow. */
2439 static conflict_function *
2440 conflict_fn (unsigned n, ...)
2443 conflict_function *ret = XCNEW (conflict_function);
2446 gcc_assert (0 < n && n <= MAX_DIM);
2450 for (i = 0; i < n; i++)
2451 ret->fns[i] = va_arg (ap, affine_fn);
2457 /* Returns constant affine function with value CST. */
2460 affine_fn_cst (tree cst)
2462 affine_fn fn = VEC_alloc (tree, heap, 1);
2463 VEC_quick_push (tree, fn, cst);
2467 /* Returns affine function with single variable, CST + COEF * x_DIM. */
2470 affine_fn_univar (tree cst, unsigned dim, tree coef)
2472 affine_fn fn = VEC_alloc (tree, heap, dim + 1);
2475 gcc_assert (dim > 0);
2476 VEC_quick_push (tree, fn, cst);
2477 for (i = 1; i < dim; i++)
2478 VEC_quick_push (tree, fn, integer_zero_node);
2479 VEC_quick_push (tree, fn, coef);
2483 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
2484 *OVERLAPS_B are initialized to the functions that describe the
2485 relation between the elements accessed twice by CHREC_A and
2486 CHREC_B. For k >= 0, the following property is verified:
2488 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2491 analyze_ziv_subscript (tree chrec_a,
2493 conflict_function **overlaps_a,
2494 conflict_function **overlaps_b,
2495 tree *last_conflicts)
2498 dependence_stats.num_ziv++;
2500 if (dump_file && (dump_flags & TDF_DETAILS))
2501 fprintf (dump_file, "(analyze_ziv_subscript \n");
2503 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
2504 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
2505 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2507 switch (TREE_CODE (difference))
2510 if (integer_zerop (difference))
2512 /* The difference is equal to zero: the accessed index
2513 overlaps for each iteration in the loop. */
2514 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2515 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2516 *last_conflicts = chrec_dont_know;
2517 dependence_stats.num_ziv_dependent++;
2521 /* The accesses do not overlap. */
2522 *overlaps_a = conflict_fn_no_dependence ();
2523 *overlaps_b = conflict_fn_no_dependence ();
2524 *last_conflicts = integer_zero_node;
2525 dependence_stats.num_ziv_independent++;
2530 /* We're not sure whether the indexes overlap. For the moment,
2531 conservatively answer "don't know". */
2532 if (dump_file && (dump_flags & TDF_DETAILS))
2533 fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
2535 *overlaps_a = conflict_fn_not_known ();
2536 *overlaps_b = conflict_fn_not_known ();
2537 *last_conflicts = chrec_dont_know;
2538 dependence_stats.num_ziv_unimplemented++;
2542 if (dump_file && (dump_flags & TDF_DETAILS))
2543 fprintf (dump_file, ")\n");
2546 /* Get the real or estimated number of iterations for LOOPNUM, whichever is
2547 available. Return the number of iterations as a tree, or NULL_TREE if
2551 get_number_of_iters_for_loop (int loopnum)
2553 struct loop *loop = get_loop (loopnum);
2554 tree numiter = number_of_exit_cond_executions (loop);
2556 if (TREE_CODE (numiter) == INTEGER_CST)
2559 if (loop->estimate_state == EST_AVAILABLE)
2561 tree type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
2562 if (double_int_fits_to_tree_p (type, loop->estimated_nb_iterations))
2563 return double_int_to_tree (type, loop->estimated_nb_iterations);
2569 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2570 constant, and CHREC_B is an affine function. *OVERLAPS_A and
2571 *OVERLAPS_B are initialized to the functions that describe the
2572 relation between the elements accessed twice by CHREC_A and
2573 CHREC_B. For k >= 0, the following property is verified:
2575 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2578 analyze_siv_subscript_cst_affine (tree chrec_a,
2580 conflict_function **overlaps_a,
2581 conflict_function **overlaps_b,
2582 tree *last_conflicts)
2584 bool value0, value1, value2;
2585 tree difference, tmp;
2587 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
2588 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
2589 difference = chrec_fold_minus
2590 (integer_type_node, initial_condition (chrec_b), chrec_a);
2592 if (!chrec_is_positive (initial_condition (difference), &value0))
2594 if (dump_file && (dump_flags & TDF_DETAILS))
2595 fprintf (dump_file, "siv test failed: chrec is not positive.\n");
2597 dependence_stats.num_siv_unimplemented++;
2598 *overlaps_a = conflict_fn_not_known ();
2599 *overlaps_b = conflict_fn_not_known ();
2600 *last_conflicts = chrec_dont_know;
2605 if (value0 == false)
2607 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
2609 if (dump_file && (dump_flags & TDF_DETAILS))
2610 fprintf (dump_file, "siv test failed: chrec not positive.\n");
2612 *overlaps_a = conflict_fn_not_known ();
2613 *overlaps_b = conflict_fn_not_known ();
2614 *last_conflicts = chrec_dont_know;
2615 dependence_stats.num_siv_unimplemented++;
2624 chrec_b = {10, +, 1}
2627 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2630 int loopnum = CHREC_VARIABLE (chrec_b);
2632 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2633 tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
2634 fold_build1 (ABS_EXPR,
2637 CHREC_RIGHT (chrec_b));
2638 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
2639 *last_conflicts = integer_one_node;
2642 /* Perform weak-zero siv test to see if overlap is
2643 outside the loop bounds. */
2644 numiter = get_number_of_iters_for_loop (loopnum);
2646 if (numiter != NULL_TREE
2647 && TREE_CODE (tmp) == INTEGER_CST
2648 && tree_int_cst_lt (numiter, tmp))
2650 free_conflict_function (*overlaps_a);
2651 free_conflict_function (*overlaps_b);
2652 *overlaps_a = conflict_fn_no_dependence ();
2653 *overlaps_b = conflict_fn_no_dependence ();
2654 *last_conflicts = integer_zero_node;
2655 dependence_stats.num_siv_independent++;
2658 dependence_stats.num_siv_dependent++;
2662 /* When the step does not divide the difference, there are
2666 *overlaps_a = conflict_fn_no_dependence ();
2667 *overlaps_b = conflict_fn_no_dependence ();
2668 *last_conflicts = integer_zero_node;
2669 dependence_stats.num_siv_independent++;
2678 chrec_b = {10, +, -1}
2680 In this case, chrec_a will not overlap with chrec_b. */
2681 *overlaps_a = conflict_fn_no_dependence ();
2682 *overlaps_b = conflict_fn_no_dependence ();
2683 *last_conflicts = integer_zero_node;
2684 dependence_stats.num_siv_independent++;
2691 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
2693 if (dump_file && (dump_flags & TDF_DETAILS))
2694 fprintf (dump_file, "siv test failed: chrec not positive.\n");
2696 *overlaps_a = conflict_fn_not_known ();
2697 *overlaps_b = conflict_fn_not_known ();
2698 *last_conflicts = chrec_dont_know;
2699 dependence_stats.num_siv_unimplemented++;
2704 if (value2 == false)
2708 chrec_b = {10, +, -1}
2710 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2713 int loopnum = CHREC_VARIABLE (chrec_b);
2715 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2716 tmp = fold_build2 (EXACT_DIV_EXPR,
2717 integer_type_node, difference,
2718 CHREC_RIGHT (chrec_b));
2719 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
2720 *last_conflicts = integer_one_node;
2722 /* Perform weak-zero siv test to see if overlap is
2723 outside the loop bounds. */
2724 numiter = get_number_of_iters_for_loop (loopnum);
2726 if (numiter != NULL_TREE
2727 && TREE_CODE (tmp) == INTEGER_CST
2728 && tree_int_cst_lt (numiter, tmp))
2730 free_conflict_function (*overlaps_a);
2731 free_conflict_function (*overlaps_b);
2732 *overlaps_a = conflict_fn_no_dependence ();
2733 *overlaps_b = conflict_fn_no_dependence ();
2734 *last_conflicts = integer_zero_node;
2735 dependence_stats.num_siv_independent++;
2738 dependence_stats.num_siv_dependent++;
2742 /* When the step does not divide the difference, there
2746 *overlaps_a = conflict_fn_no_dependence ();
2747 *overlaps_b = conflict_fn_no_dependence ();
2748 *last_conflicts = integer_zero_node;
2749 dependence_stats.num_siv_independent++;
2759 In this case, chrec_a will not overlap with chrec_b. */
2760 *overlaps_a = conflict_fn_no_dependence ();
2761 *overlaps_b = conflict_fn_no_dependence ();
2762 *last_conflicts = integer_zero_node;
2763 dependence_stats.num_siv_independent++;
2771 /* Helper recursive function for initializing the matrix A. Returns
2772 the initial value of CHREC. */
2775 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2779 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2780 return int_cst_value (chrec);
2782 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2783 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2786 #define FLOOR_DIV(x,y) ((x) / (y))
2788 /* Solves the special case of the Diophantine equation:
2789 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2791 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2792 number of iterations that loops X and Y run. The overlaps will be
2793 constructed as evolutions in dimension DIM. */
2796 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
2797 affine_fn *overlaps_a,
2798 affine_fn *overlaps_b,
2799 tree *last_conflicts, int dim)
2801 if (((step_a > 0 && step_b > 0)
2802 || (step_a < 0 && step_b < 0)))
2804 int step_overlaps_a, step_overlaps_b;
2805 int gcd_steps_a_b, last_conflict, tau2;
2807 gcd_steps_a_b = gcd (step_a, step_b);
2808 step_overlaps_a = step_b / gcd_steps_a_b;
2809 step_overlaps_b = step_a / gcd_steps_a_b;
2811 tau2 = FLOOR_DIV (niter, step_overlaps_a);
2812 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2813 last_conflict = tau2;
2815 *overlaps_a = affine_fn_univar (integer_zero_node, dim,
2816 build_int_cst (NULL_TREE,
2818 *overlaps_b = affine_fn_univar (integer_zero_node, dim,
2819 build_int_cst (NULL_TREE,
2821 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2826 *overlaps_a = affine_fn_cst (integer_zero_node);
2827 *overlaps_b = affine_fn_cst (integer_zero_node);
2828 *last_conflicts = integer_zero_node;
2832 /* Solves the special case of a Diophantine equation where CHREC_A is
2833 an affine bivariate function, and CHREC_B is an affine univariate
2834 function. For example,
2836 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2838 has the following overlapping functions:
2840 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2841 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2842 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2844 FORNOW: This is a specialized implementation for a case occurring in
2845 a common benchmark. Implement the general algorithm. */
2848 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2849 conflict_function **overlaps_a,
2850 conflict_function **overlaps_b,
2851 tree *last_conflicts)
2853 bool xz_p, yz_p, xyz_p;
2854 int step_x, step_y, step_z;
2855 int niter_x, niter_y, niter_z, niter;
2856 tree numiter_x, numiter_y, numiter_z;
2857 affine_fn overlaps_a_xz, overlaps_b_xz;
2858 affine_fn overlaps_a_yz, overlaps_b_yz;
2859 affine_fn overlaps_a_xyz, overlaps_b_xyz;
2860 affine_fn ova1, ova2, ovb;
2861 tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
2863 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2864 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2865 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2867 numiter_x = get_number_of_iters_for_loop (CHREC_VARIABLE (CHREC_LEFT (chrec_a)));
2868 numiter_y = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
2869 numiter_z = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
2871 if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
2872 || numiter_z == NULL_TREE)
2874 if (dump_file && (dump_flags & TDF_DETAILS))
2875 fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
2877 *overlaps_a = conflict_fn_not_known ();
2878 *overlaps_b = conflict_fn_not_known ();
2879 *last_conflicts = chrec_dont_know;
2883 niter_x = int_cst_value (numiter_x);
2884 niter_y = int_cst_value (numiter_y);
2885 niter_z = int_cst_value (numiter_z);
2887 niter = MIN (niter_x, niter_z);
2888 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2891 &last_conflicts_xz, 1);
2892 niter = MIN (niter_y, niter_z);
2893 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2896 &last_conflicts_yz, 2);
2897 niter = MIN (niter_x, niter_z);
2898 niter = MIN (niter_y, niter);
2899 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2902 &last_conflicts_xyz, 3);
2904 xz_p = !integer_zerop (last_conflicts_xz);
2905 yz_p = !integer_zerop (last_conflicts_yz);
2906 xyz_p = !integer_zerop (last_conflicts_xyz);
2908 if (xz_p || yz_p || xyz_p)
2910 ova1 = affine_fn_cst (integer_zero_node);
2911 ova2 = affine_fn_cst (integer_zero_node);
2912 ovb = affine_fn_cst (integer_zero_node);
2915 affine_fn t0 = ova1;
2918 ova1 = affine_fn_plus (ova1, overlaps_a_xz);
2919 ovb = affine_fn_plus (ovb, overlaps_b_xz);
2920 affine_fn_free (t0);
2921 affine_fn_free (t2);
2922 *last_conflicts = last_conflicts_xz;
2926 affine_fn t0 = ova2;
2929 ova2 = affine_fn_plus (ova2, overlaps_a_yz);
2930 ovb = affine_fn_plus (ovb, overlaps_b_yz);
2931 affine_fn_free (t0);
2932 affine_fn_free (t2);
2933 *last_conflicts = last_conflicts_yz;
2937 affine_fn t0 = ova1;
2938 affine_fn t2 = ova2;
2941 ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
2942 ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
2943 ovb = affine_fn_plus (ovb, overlaps_b_xyz);
2944 affine_fn_free (t0);
2945 affine_fn_free (t2);
2946 affine_fn_free (t4);
2947 *last_conflicts = last_conflicts_xyz;
2949 *overlaps_a = conflict_fn (2, ova1, ova2);
2950 *overlaps_b = conflict_fn (1, ovb);
2954 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2955 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2956 *last_conflicts = integer_zero_node;
2959 affine_fn_free (overlaps_a_xz);
2960 affine_fn_free (overlaps_b_xz);
2961 affine_fn_free (overlaps_a_yz);
2962 affine_fn_free (overlaps_b_yz);
2963 affine_fn_free (overlaps_a_xyz);
2964 affine_fn_free (overlaps_b_xyz);
2967 /* Determines the overlapping elements due to accesses CHREC_A and
2968 CHREC_B, that are affine functions. This function cannot handle
2969 symbolic evolution functions, ie. when initial conditions are
2970 parameters, because it uses lambda matrices of integers. */
2973 analyze_subscript_affine_affine (tree chrec_a,
2975 conflict_function **overlaps_a,
2976 conflict_function **overlaps_b,
2977 tree *last_conflicts)
2979 unsigned nb_vars_a, nb_vars_b, dim;
2980 int init_a, init_b, gamma, gcd_alpha_beta;
2982 lambda_matrix A, U, S;
2984 if (eq_evolutions_p (chrec_a, chrec_b))
2986 /* The accessed index overlaps for each iteration in the
2988 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2989 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2990 *last_conflicts = chrec_dont_know;
2993 if (dump_file && (dump_flags & TDF_DETAILS))
2994 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2996 /* For determining the initial intersection, we have to solve a
2997 Diophantine equation. This is the most time consuming part.
2999 For answering to the question: "Is there a dependence?" we have
3000 to prove that there exists a solution to the Diophantine
3001 equation, and that the solution is in the iteration domain,
3002 i.e. the solution is positive or zero, and that the solution
3003 happens before the upper bound loop.nb_iterations. Otherwise
3004 there is no dependence. This function outputs a description of
3005 the iterations that hold the intersections. */
3007 nb_vars_a = nb_vars_in_chrec (chrec_a);
3008 nb_vars_b = nb_vars_in_chrec (chrec_b);
3010 dim = nb_vars_a + nb_vars_b;
3011 U = lambda_matrix_new (dim, dim);
3012 A = lambda_matrix_new (dim, 1);
3013 S = lambda_matrix_new (dim, 1);
3015 init_a = initialize_matrix_A (A, chrec_a, 0, 1);
3016 init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
3017 gamma = init_b - init_a;
3019 /* Don't do all the hard work of solving the Diophantine equation
3020 when we already know the solution: for example,
3023 | gamma = 3 - 3 = 0.
3024 Then the first overlap occurs during the first iterations:
3025 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
3029 if (nb_vars_a == 1 && nb_vars_b == 1)
3032 int niter, niter_a, niter_b;
3033 tree numiter_a, numiter_b;
3036 numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
3037 numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
3038 if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
3040 if (dump_file && (dump_flags & TDF_DETAILS))
3041 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
3042 *overlaps_a = conflict_fn_not_known ();
3043 *overlaps_b = conflict_fn_not_known ();
3044 *last_conflicts = chrec_dont_know;
3045 goto end_analyze_subs_aa;
3048 niter_a = int_cst_value (numiter_a);
3049 niter_b = int_cst_value (numiter_b);
3050 niter = MIN (niter_a, niter_b);
3052 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
3053 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
3055 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
3058 *overlaps_a = conflict_fn (1, ova);
3059 *overlaps_b = conflict_fn (1, ovb);
3062 else if (nb_vars_a == 2 && nb_vars_b == 1)
3063 compute_overlap_steps_for_affine_1_2
3064 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
3066 else if (nb_vars_a == 1 && nb_vars_b == 2)
3067 compute_overlap_steps_for_affine_1_2
3068 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
3072 if (dump_file && (dump_flags & TDF_DETAILS))
3073 fprintf (dump_file, "affine-affine test failed: too many variables.\n");
3074 *overlaps_a = conflict_fn_not_known ();
3075 *overlaps_b = conflict_fn_not_known ();
3076 *last_conflicts = chrec_dont_know;
3078 goto end_analyze_subs_aa;
3082 lambda_matrix_right_hermite (A, dim, 1, S, U);
3087 lambda_matrix_row_negate (U, dim, 0);
3089 gcd_alpha_beta = S[0][0];
3091 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
3092 but that is a quite strange case. Instead of ICEing, answer
3094 if (gcd_alpha_beta == 0)
3096 *overlaps_a = conflict_fn_not_known ();
3097 *overlaps_b = conflict_fn_not_known ();
3098 *last_conflicts = chrec_dont_know;
3099 goto end_analyze_subs_aa;
3102 /* The classic "gcd-test". */
3103 if (!int_divides_p (gcd_alpha_beta, gamma))
3105 /* The "gcd-test" has determined that there is no integer
3106 solution, i.e. there is no dependence. */
3107 *overlaps_a = conflict_fn_no_dependence ();
3108 *overlaps_b = conflict_fn_no_dependence ();
3109 *last_conflicts = integer_zero_node;
3112 /* Both access functions are univariate. This includes SIV and MIV cases. */
3113 else if (nb_vars_a == 1 && nb_vars_b == 1)
3115 /* Both functions should have the same evolution sign. */
3116 if (((A[0][0] > 0 && -A[1][0] > 0)
3117 || (A[0][0] < 0 && -A[1][0] < 0)))
3119 /* The solutions are given by:
3121 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
3124 For a given integer t. Using the following variables,
3126 | i0 = u11 * gamma / gcd_alpha_beta
3127 | j0 = u12 * gamma / gcd_alpha_beta
3134 | y0 = j0 + j1 * t. */
3138 /* X0 and Y0 are the first iterations for which there is a
3139 dependence. X0, Y0 are two solutions of the Diophantine
3140 equation: chrec_a (X0) = chrec_b (Y0). */
3142 int niter, niter_a, niter_b;
3143 tree numiter_a, numiter_b;
3145 numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
3146 numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
3148 if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
3150 if (dump_file && (dump_flags & TDF_DETAILS))
3151 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
3152 *overlaps_a = conflict_fn_not_known ();
3153 *overlaps_b = conflict_fn_not_known ();
3154 *last_conflicts = chrec_dont_know;
3155 goto end_analyze_subs_aa;
3158 niter_a = int_cst_value (numiter_a);
3159 niter_b = int_cst_value (numiter_b);
3160 niter = MIN (niter_a, niter_b);
3162 i0 = U[0][0] * gamma / gcd_alpha_beta;
3163 j0 = U[0][1] * gamma / gcd_alpha_beta;
3167 if ((i1 == 0 && i0 < 0)
3168 || (j1 == 0 && j0 < 0))
3170 /* There is no solution.
3171 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
3172 falls in here, but for the moment we don't look at the
3173 upper bound of the iteration domain. */
3174 *overlaps_a = conflict_fn_no_dependence ();
3175 *overlaps_b = conflict_fn_no_dependence ();
3176 *last_conflicts = integer_zero_node;
3183 tau1 = CEIL (-i0, i1);
3184 tau2 = FLOOR_DIV (niter - i0, i1);
3188 int last_conflict, min_multiple;
3189 tau1 = MAX (tau1, CEIL (-j0, j1));
3190 tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
3192 x0 = i1 * tau1 + i0;
3193 y0 = j1 * tau1 + j0;
3195 /* At this point (x0, y0) is one of the
3196 solutions to the Diophantine equation. The
3197 next step has to compute the smallest
3198 positive solution: the first conflicts. */
3199 min_multiple = MIN (x0 / i1, y0 / j1);
3200 x0 -= i1 * min_multiple;
3201 y0 -= j1 * min_multiple;
3203 tau1 = (x0 - i0)/i1;
3204 last_conflict = tau2 - tau1;
3206 /* If the overlap occurs outside of the bounds of the
3207 loop, there is no dependence. */
3208 if (x0 > niter || y0 > niter)
3210 *overlaps_a = conflict_fn_no_dependence ();
3211 *overlaps_b = conflict_fn_no_dependence ();
3212 *last_conflicts = integer_zero_node;
3218 affine_fn_univar (build_int_cst (NULL_TREE, x0),
3220 build_int_cst (NULL_TREE, i1)));
3223 affine_fn_univar (build_int_cst (NULL_TREE, y0),
3225 build_int_cst (NULL_TREE, j1)));
3226 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
3231 /* FIXME: For the moment, the upper bound of the
3232 iteration domain for j is not checked. */
3233 if (dump_file && (dump_flags & TDF_DETAILS))
3234 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3235 *overlaps_a = conflict_fn_not_known ();
3236 *overlaps_b = conflict_fn_not_known ();
3237 *last_conflicts = chrec_dont_know;
3243 /* FIXME: For the moment, the upper bound of the
3244 iteration domain for i is not checked. */
3245 if (dump_file && (dump_flags & TDF_DETAILS))
3246 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3247 *overlaps_a = conflict_fn_not_known ();
3248 *overlaps_b = conflict_fn_not_known ();
3249 *last_conflicts = chrec_dont_know;
3255 if (dump_file && (dump_flags & TDF_DETAILS))
3256 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3257 *overlaps_a = conflict_fn_not_known ();
3258 *overlaps_b = conflict_fn_not_known ();
3259 *last_conflicts = chrec_dont_know;
3265 if (dump_file && (dump_flags & TDF_DETAILS))
3266 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3267 *overlaps_a = conflict_fn_not_known ();
3268 *overlaps_b = conflict_fn_not_known ();
3269 *last_conflicts = chrec_dont_know;
3272 end_analyze_subs_aa:
3273 if (dump_file && (dump_flags & TDF_DETAILS))
3275 fprintf (dump_file, " (overlaps_a = ");
3276 dump_conflict_function (dump_file, *overlaps_a);
3277 fprintf (dump_file, ")\n (overlaps_b = ");
3278 dump_conflict_function (dump_file, *overlaps_b);
3279 fprintf (dump_file, ")\n");
3280 fprintf (dump_file, ")\n");
3284 /* Returns true when analyze_subscript_affine_affine can be used for
3285 determining the dependence relation between chrec_a and chrec_b,
3286 that contain symbols. This function modifies chrec_a and chrec_b
3287 such that the analysis result is the same, and such that they don't
3288 contain symbols, and then can safely be passed to the analyzer.
3290 Example: The analysis of the following tuples of evolutions produce
3291 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
3294 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
3295 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
3299 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
3301 tree diff, type, left_a, left_b, right_b;
3303 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
3304 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
3305 /* FIXME: For the moment not handled. Might be refined later. */
3308 type = chrec_type (*chrec_a);
3309 left_a = CHREC_LEFT (*chrec_a);
3310 left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE);
3311 diff = chrec_fold_minus (type, left_a, left_b);
3313 if (!evolution_function_is_constant_p (diff))
3316 if (dump_file && (dump_flags & TDF_DETAILS))
3317 fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
3319 *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
3320 diff, CHREC_RIGHT (*chrec_a));
3321 right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE);
3322 *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
3323 build_int_cst (type, 0),
3328 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
3329 *OVERLAPS_B are initialized to the functions that describe the
3330 relation between the elements accessed twice by CHREC_A and
3331 CHREC_B. For k >= 0, the following property is verified:
3333 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
3336 analyze_siv_subscript (tree chrec_a,
3338 conflict_function **overlaps_a,
3339 conflict_function **overlaps_b,
3340 tree *last_conflicts)
3342 dependence_stats.num_siv++;
3344 if (dump_file && (dump_flags & TDF_DETAILS))
3345 fprintf (dump_file, "(analyze_siv_subscript \n");
3347 if (evolution_function_is_constant_p (chrec_a)
3348 && evolution_function_is_affine_p (chrec_b))
3349 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
3350 overlaps_a, overlaps_b, last_conflicts);
3352 else if (evolution_function_is_affine_p (chrec_a)
3353 && evolution_function_is_constant_p (chrec_b))
3354 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
3355 overlaps_b, overlaps_a, last_conflicts);
3357 else if (evolution_function_is_affine_p (chrec_a)
3358 && evolution_function_is_affine_p (chrec_b))
3360 if (!chrec_contains_symbols (chrec_a)
3361 && !chrec_contains_symbols (chrec_b))
3363 analyze_subscript_affine_affine (chrec_a, chrec_b,
3364 overlaps_a, overlaps_b,
3367 if (CF_NOT_KNOWN_P (*overlaps_a)
3368 || CF_NOT_KNOWN_P (*overlaps_b))
3369 dependence_stats.num_siv_unimplemented++;
3370 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
3371 || CF_NO_DEPENDENCE_P (*overlaps_b))
3372 dependence_stats.num_siv_independent++;
3374 dependence_stats.num_siv_dependent++;
3376 else if (can_use_analyze_subscript_affine_affine (&chrec_a,
3379 analyze_subscript_affine_affine (chrec_a, chrec_b,
3380 overlaps_a, overlaps_b,
3382 /* FIXME: The number of iterations is a symbolic expression.
3383 Compute it properly. */
3384 *last_conflicts = chrec_dont_know;
3386 if (CF_NOT_KNOWN_P (*overlaps_a)
3387 || CF_NOT_KNOWN_P (*overlaps_b))
3388 dependence_stats.num_siv_unimplemented++;
3389 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
3390 || CF_NO_DEPENDENCE_P (*overlaps_b))
3391 dependence_stats.num_siv_independent++;
3393 dependence_stats.num_siv_dependent++;
3396 goto siv_subscript_dontknow;
3401 siv_subscript_dontknow:;
3402 if (dump_file && (dump_flags & TDF_DETAILS))
3403 fprintf (dump_file, "siv test failed: unimplemented.\n");
3404 *overlaps_a = conflict_fn_not_known ();
3405 *overlaps_b = conflict_fn_not_known ();
3406 *last_conflicts = chrec_dont_know;
3407 dependence_stats.num_siv_unimplemented++;
3410 if (dump_file && (dump_flags & TDF_DETAILS))
3411 fprintf (dump_file, ")\n");
3414 /* Return true when the property can be computed. RES should contain
3415 true when calling the first time this function, then it is set to
3416 false when one of the evolution steps of an affine CHREC does not
3417 divide the constant CST. */
3420 chrec_steps_divide_constant_p (tree chrec,
3424 switch (TREE_CODE (chrec))
3426 case POLYNOMIAL_CHREC:
3427 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
3429 if (tree_fold_divides_p (CHREC_RIGHT (chrec), cst))
3430 /* Keep RES to true, and iterate on other dimensions. */
3431 return chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst, res);
3437 /* When the step is a parameter the result is undetermined. */
3441 /* On the initial condition, return true. */
3446 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
3447 *OVERLAPS_B are initialized to the functions that describe the
3448 relation between the elements accessed twice by CHREC_A and
3449 CHREC_B. For k >= 0, the following property is verified:
3451 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
3454 analyze_miv_subscript (tree chrec_a,
3456 conflict_function **overlaps_a,
3457 conflict_function **overlaps_b,
3458 tree *last_conflicts)
3460 /* FIXME: This is a MIV subscript, not yet handled.
3461 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
3464 In the SIV test we had to solve a Diophantine equation with two
3465 variables. In the MIV case we have to solve a Diophantine
3466 equation with 2*n variables (if the subscript uses n IVs).
3468 bool divide_p = true;
3470 dependence_stats.num_miv++;
3471 if (dump_file && (dump_flags & TDF_DETAILS))
3472 fprintf (dump_file, "(analyze_miv_subscript \n");
3474 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
3475 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
3476 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
3478 if (eq_evolutions_p (chrec_a, chrec_b))
3480 /* Access functions are the same: all the elements are accessed
3481 in the same order. */
3482 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
3483 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
3484 *last_conflicts = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
3485 dependence_stats.num_miv_dependent++;
3488 else if (evolution_function_is_constant_p (difference)
3489 /* For the moment, the following is verified:
3490 evolution_function_is_affine_multivariate_p (chrec_a) */
3491 && chrec_steps_divide_constant_p (chrec_a, difference, ÷_p)
3494 /* testsuite/.../ssa-chrec-33.c
3495 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
3497 The difference is 1, and the evolution steps are equal to 2,
3498 consequently there are no overlapping elements. */
3499 *overlaps_a = conflict_fn_no_dependence ();
3500 *overlaps_b = conflict_fn_no_dependence ();
3501 *last_conflicts = integer_zero_node;
3502 dependence_stats.num_miv_independent++;
3505 else if (evolution_function_is_affine_multivariate_p (chrec_a)
3506 && !chrec_contains_symbols (chrec_a)
3507 && evolution_function_is_affine_multivariate_p (chrec_b)
3508 && !chrec_contains_symbols (chrec_b))
3510 /* testsuite/.../ssa-chrec-35.c
3511 {0, +, 1}_2 vs. {0, +, 1}_3
3512 the overlapping elements are respectively located at iterations:
3513 {0, +, 1}_x and {0, +, 1}_x,
3514 in other words, we have the equality:
3515 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
3518 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
3519 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
3521 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
3522 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
3524 analyze_subscript_affine_affine (chrec_a, chrec_b,
3525 overlaps_a, overlaps_b, last_conflicts);
3527 if (CF_NOT_KNOWN_P (*overlaps_a)
3528 || CF_NOT_KNOWN_P (*overlaps_b))
3529 dependence_stats.num_miv_unimplemented++;
3530 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
3531 || CF_NO_DEPENDENCE_P (*overlaps_b))
3532 dependence_stats.num_miv_independent++;
3534 dependence_stats.num_miv_dependent++;
3539 /* When the analysis is too difficult, answer "don't know". */
3540 if (dump_file && (dump_flags & TDF_DETAILS))
3541 fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
3543 *overlaps_a = conflict_fn_not_known ();
3544 *overlaps_b = conflict_fn_not_known ();
3545 *last_conflicts = chrec_dont_know;
3546 dependence_stats.num_miv_unimplemented++;
3549 if (dump_file && (dump_flags & TDF_DETAILS))
3550 fprintf (dump_file, ")\n");
3553 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
3554 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
3555 two functions that describe the iterations that contain conflicting
3558 Remark: For an integer k >= 0, the following equality is true:
3560 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
3564 analyze_overlapping_iterations (tree chrec_a,
3566 conflict_function **overlap_iterations_a,
3567 conflict_function **overlap_iterations_b,
3568 tree *last_conflicts)
3570 dependence_stats.num_subscript_tests++;
3572 if (dump_file && (dump_flags & TDF_DETAILS))
3574 fprintf (dump_file, "(analyze_overlapping_iterations \n");
3575 fprintf (dump_file, " (chrec_a = ");
3576 print_generic_expr (dump_file, chrec_a, 0);
3577 fprintf (dump_file, ")\n (chrec_b = ");
3578 print_generic_expr (dump_file, chrec_b, 0);
3579 fprintf (dump_file, ")\n");
3582 if (chrec_a == NULL_TREE
3583 || chrec_b == NULL_TREE
3584 || chrec_contains_undetermined (chrec_a)
3585 || chrec_contains_undetermined (chrec_b))
3587 dependence_stats.num_subscript_undetermined++;
3589 *overlap_iterations_a = conflict_fn_not_known ();
3590 *overlap_iterations_b = conflict_fn_not_known ();
3593 /* If they are the same chrec, and are affine, they overlap
3594 on every iteration. */
3595 else if (eq_evolutions_p (chrec_a, chrec_b)
3596 && evolution_function_is_affine_multivariate_p (chrec_a))
3598 dependence_stats.num_same_subscript_function++;
3599 *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
3600 *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
3601 *last_conflicts = chrec_dont_know;
3604 /* If they aren't the same, and aren't affine, we can't do anything
3606 else if ((chrec_contains_symbols (chrec_a)
3607 || chrec_contains_symbols (chrec_b))
3608 && (!evolution_function_is_affine_multivariate_p (chrec_a)
3609 || !evolution_function_is_affine_multivariate_p (chrec_b)))
3611 dependence_stats.num_subscript_undetermined++;
3612 *overlap_iterations_a = conflict_fn_not_known ();
3613 *overlap_iterations_b = conflict_fn_not_known ();
3616 else if (ziv_subscript_p (chrec_a, chrec_b))
3617 analyze_ziv_subscript (chrec_a, chrec_b,
3618 overlap_iterations_a, overlap_iterations_b,
3621 else if (siv_subscript_p (chrec_a, chrec_b))
3622 analyze_siv_subscript (chrec_a, chrec_b,
3623 overlap_iterations_a, overlap_iterations_b,
3627 analyze_miv_subscript (chrec_a, chrec_b,
3628 overlap_iterations_a, overlap_iterations_b,
3631 if (dump_file && (dump_flags & TDF_DETAILS))
3633 fprintf (dump_file, " (overlap_iterations_a = ");
3634 dump_conflict_function (dump_file, *overlap_iterations_a);
3635 fprintf (dump_file, ")\n (overlap_iterations_b = ");
3636 dump_conflict_function (dump_file, *overlap_iterations_b);
3637 fprintf (dump_file, ")\n");
3638 fprintf (dump_file, ")\n");
3642 /* Helper function for uniquely inserting distance vectors. */
3645 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
3650 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
3651 if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
3654 VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
3657 /* Helper function for uniquely inserting direction vectors. */
3660 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
3665 for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
3666 if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
3669 VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
3672 /* Add a distance of 1 on all the loops outer than INDEX. If we
3673 haven't yet determined a distance for this outer loop, push a new
3674 distance vector composed of the previous distance, and a distance
3675 of 1 for this outer loop. Example:
3683 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
3684 save (0, 1), then we have to save (1, 0). */
3687 add_outer_distances (struct data_dependence_relation *ddr,
3688 lambda_vector dist_v, int index)
3690 /* For each outer loop where init_v is not set, the accesses are
3691 in dependence of distance 1 in the loop. */
3692 while (--index >= 0)
3694 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3695 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3697 save_dist_v (ddr, save_v);
3701 /* Return false when fail to represent the data dependence as a
3702 distance vector. INIT_B is set to true when a component has been
3703 added to the distance vector DIST_V. INDEX_CARRY is then set to
3704 the index in DIST_V that carries the dependence. */
3707 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
3708 struct data_reference *ddr_a,
3709 struct data_reference *ddr_b,
3710 lambda_vector dist_v, bool *init_b,
3714 lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3716 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3718 tree access_fn_a, access_fn_b;
3719 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3721 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3723 non_affine_dependence_relation (ddr);
3727 access_fn_a = DR_ACCESS_FN (ddr_a, i);
3728 access_fn_b = DR_ACCESS_FN (ddr_b, i);
3730 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3731 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3734 int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
3735 DDR_LOOP_NEST (ddr));
3736 int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
3737 DDR_LOOP_NEST (ddr));
3739 /* The dependence is carried by the outermost loop. Example:
3746 In this case, the dependence is carried by loop_1. */
3747 index = index_a < index_b ? index_a : index_b;
3748 *index_carry = MIN (index, *index_carry);
3750 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3752 non_affine_dependence_relation (ddr);
3756 dist = int_cst_value (SUB_DISTANCE (subscript));
3758 /* This is the subscript coupling test. If we have already
3759 recorded a distance for this loop (a distance coming from
3760 another subscript), it should be the same. For example,
3761 in the following code, there is no dependence:
3768 if (init_v[index] != 0 && dist_v[index] != dist)
3770 finalize_ddr_dependent (ddr, chrec_known);
3774 dist_v[index] = dist;
3780 /* This can be for example an affine vs. constant dependence
3781 (T[i] vs. T[3]) that is not an affine dependence and is
3782 not representable as a distance vector. */
3783 non_affine_dependence_relation (ddr);
3791 /* Return true when the DDR contains two data references that have the
3792 same access functions. */
3795 same_access_functions (struct data_dependence_relation *ddr)
3799 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3800 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
3801 DR_ACCESS_FN (DDR_B (ddr), i)))
3807 /* Helper function for the case where DDR_A and DDR_B are the same
3808 multivariate access function. */
3811 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
3814 tree c_1 = CHREC_LEFT (c_2);
3815 tree c_0 = CHREC_LEFT (c_1);
3816 lambda_vector dist_v;
3818 /* Polynomials with more than 2 variables are not handled yet. */
3819 if (TREE_CODE (c_0) != INTEGER_CST)
3821 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
3825 x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
3826 x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
3828 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3829 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3830 dist_v[x_1] = int_cst_value (CHREC_RIGHT (c_2));
3831 dist_v[x_2] = -int_cst_value (CHREC_RIGHT (c_1));
3832 save_dist_v (ddr, dist_v);
3834 add_outer_distances (ddr, dist_v, x_1);
3837 /* Helper function for the case where DDR_A and DDR_B are the same
3838 access functions. */
3841 add_other_self_distances (struct data_dependence_relation *ddr)
3843 lambda_vector dist_v;
3845 int index_carry = DDR_NB_LOOPS (ddr);
3847 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3849 tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
3851 if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
3853 if (!evolution_function_is_univariate_p (access_fun))
3855 if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
3857 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
3861 add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0));
3865 index_carry = MIN (index_carry,
3866 index_in_loop_nest (CHREC_VARIABLE (access_fun),
3867 DDR_LOOP_NEST (ddr)));
3871 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3872 add_outer_distances (ddr, dist_v, index_carry);
3875 /* Compute the classic per loop distance vector. DDR is the data
3876 dependence relation to build a vector from. Return false when fail
3877 to represent the data dependence as a distance vector. */
3880 build_classic_dist_vector (struct data_dependence_relation *ddr)
3882 bool init_b = false;
3883 int index_carry = DDR_NB_LOOPS (ddr);
3884 lambda_vector dist_v;
3886 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3889 if (same_access_functions (ddr))
3891 /* Save the 0 vector. */
3892 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3893 save_dist_v (ddr, dist_v);
3895 if (DDR_NB_LOOPS (ddr) > 1)
3896 add_other_self_distances (ddr);
3901 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3902 if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
3903 dist_v, &init_b, &index_carry))
3906 /* Save the distance vector if we initialized one. */
3909 /* Verify a basic constraint: classic distance vectors should
3910 always be lexicographically positive.
3912 Data references are collected in the order of execution of
3913 the program, thus for the following loop
3915 | for (i = 1; i < 100; i++)
3916 | for (j = 1; j < 100; j++)
3918 | t = T[j+1][i-1]; // A
3919 | T[j][i] = t + 2; // B
3922 references are collected following the direction of the wind:
3923 A then B. The data dependence tests are performed also
3924 following this order, such that we're looking at the distance
3925 separating the elements accessed by A from the elements later
3926 accessed by B. But in this example, the distance returned by
3927 test_dep (A, B) is lexicographically negative (-1, 1), that
3928 means that the access A occurs later than B with respect to
3929 the outer loop, ie. we're actually looking upwind. In this
3930 case we solve test_dep (B, A) looking downwind to the
3931 lexicographically positive solution, that returns the
3932 distance vector (1, -1). */
3933 if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
3935 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3936 subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
3937 compute_subscript_distance (ddr);
3938 build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3939 save_v, &init_b, &index_carry);
3940 save_dist_v (ddr, save_v);
3942 /* In this case there is a dependence forward for all the
3945 | for (k = 1; k < 100; k++)
3946 | for (i = 1; i < 100; i++)
3947 | for (j = 1; j < 100; j++)
3949 | t = T[j+1][i-1]; // A
3950 | T[j][i] = t + 2; // B
3958 if (DDR_NB_LOOPS (ddr) > 1)
3960 add_outer_distances (ddr, save_v, index_carry);
3961 add_outer_distances (ddr, dist_v, index_carry);
3966 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3967 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3968 save_dist_v (ddr, save_v);
3970 if (DDR_NB_LOOPS (ddr) > 1)
3972 lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3974 subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
3975 compute_subscript_distance (ddr);
3976 build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3977 opposite_v, &init_b, &index_carry);
3979 add_outer_distances (ddr, dist_v, index_carry);
3980 add_outer_distances (ddr, opposite_v, index_carry);
3986 /* There is a distance of 1 on all the outer loops: Example:
3987 there is a dependence of distance 1 on loop_1 for the array A.
3993 add_outer_distances (ddr, dist_v,
3994 lambda_vector_first_nz (dist_v,
3995 DDR_NB_LOOPS (ddr), 0));
3998 if (dump_file && (dump_flags & TDF_DETAILS))
4002 fprintf (dump_file, "(build_classic_dist_vector\n");
4003 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
4005 fprintf (dump_file, " dist_vector = (");
4006 print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
4007 DDR_NB_LOOPS (ddr));
4008 fprintf (dump_file, " )\n");
4010 fprintf (dump_file, ")\n");
4016 /* Return the direction for a given distance.
4017 FIXME: Computing dir this way is suboptimal, since dir can catch
4018 cases that dist is unable to represent. */
4020 static inline enum data_dependence_direction
4021 dir_from_dist (int dist)
4024 return dir_positive;
4026 return dir_negative;
4031 /* Compute the classic per loop direction vector. DDR is the data
4032 dependence relation to build a vector from. */
4035 build_classic_dir_vector (struct data_dependence_relation *ddr)
4038 lambda_vector dist_v;
4040 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
4042 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4044 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
4045 dir_v[j] = dir_from_dist (dist_v[j]);
4047 save_dir_v (ddr, dir_v);
4051 /* Helper function. Returns true when there is a dependence between
4052 data references DRA and DRB. */
4055 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
4056 struct data_reference *dra,
4057 struct data_reference *drb)
4060 tree last_conflicts;
4061 struct subscript *subscript;
4063 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
4066 conflict_function *overlaps_a, *overlaps_b;
4068 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
4069 DR_ACCESS_FN (drb, i),
4070 &overlaps_a, &overlaps_b,
4073 if (CF_NOT_KNOWN_P (overlaps_a)
4074 || CF_NOT_KNOWN_P (overlaps_b))
4076 finalize_ddr_dependent (ddr, chrec_dont_know);
4077 dependence_stats.num_dependence_undetermined++;
4078 free_conflict_function (overlaps_a);
4079 free_conflict_function (overlaps_b);
4083 else if (CF_NO_DEPENDENCE_P (overlaps_a)
4084 || CF_NO_DEPENDENCE_P (overlaps_b))
4086 finalize_ddr_dependent (ddr, chrec_known);
4087 dependence_stats.num_dependence_independent++;
4088 free_conflict_function (overlaps_a);
4089 free_conflict_function (overlaps_b);
4095 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
4096 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
4097 SUB_LAST_CONFLICT (subscript) = last_conflicts;
4104 /* Computes the conflicting iterations, and initialize DDR. */
4107 subscript_dependence_tester (struct data_dependence_relation *ddr)
4110 if (dump_file && (dump_flags & TDF_DETAILS))
4111 fprintf (dump_file, "(subscript_dependence_tester \n");
4113 if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr)))
4114 dependence_stats.num_dependence_dependent++;
4116 compute_subscript_distance (ddr);
4117 if (build_classic_dist_vector (ddr))
4118 build_classic_dir_vector (ddr);
4120 if (dump_file && (dump_flags & TDF_DETAILS))
4121 fprintf (dump_file, ")\n");
4124 /* Returns true when all the access functions of A are affine or
4128 access_functions_are_affine_or_constant_p (struct data_reference *a)
4131 VEC(tree,heap) **fns = DR_ACCESS_FNS_ADDR (a);
4134 for (i = 0; VEC_iterate (tree, *fns, i, t); i++)
4135 if (!evolution_function_is_constant_p (t)
4136 && !evolution_function_is_affine_multivariate_p (t))
4142 /* This computes the affine dependence relation between A and B.
4143 CHREC_KNOWN is used for representing the independence between two
4144 accesses, while CHREC_DONT_KNOW is used for representing the unknown
4147 Note that it is possible to stop the computation of the dependence
4148 relation the first time we detect a CHREC_KNOWN element for a given
4152 compute_affine_dependence (struct data_dependence_relation *ddr)
4154 struct data_reference *dra = DDR_A (ddr);
4155 struct data_reference *drb = DDR_B (ddr);
4157 if (dump_file && (dump_flags & TDF_DETAILS))
4159 fprintf (dump_file, "(compute_affine_dependence\n");
4160 fprintf (dump_file, " (stmt_a = \n");
4161 print_generic_expr (dump_file, DR_STMT (dra), 0);
4162 fprintf (dump_file, ")\n (stmt_b = \n");
4163 print_generic_expr (dump_file, DR_STMT (drb), 0);
4164 fprintf (dump_file, ")\n");
4167 /* Analyze only when the dependence relation is not yet known. */
4168 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4170 dependence_stats.num_dependence_tests++;
4172 if (access_functions_are_affine_or_constant_p (dra)
4173 && access_functions_are_affine_or_constant_p (drb))
4174 subscript_dependence_tester (ddr);
4176 /* As a last case, if the dependence cannot be determined, or if
4177 the dependence is considered too difficult to determine, answer
4181 dependence_stats.num_dependence_undetermined++;
4183 if (dump_file && (dump_flags & TDF_DETAILS))
4185 fprintf (dump_file, "Data ref a:\n");
4186 dump_data_reference (dump_file, dra);
4187 fprintf (dump_file, "Data ref b:\n");
4188 dump_data_reference (dump_file, drb);
4189 fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
4191 finalize_ddr_dependent (ddr, chrec_dont_know);
4195 if (dump_file && (dump_flags & TDF_DETAILS))
4196 fprintf (dump_file, ")\n");
4199 /* This computes the dependence relation for the same data
4200 reference into DDR. */
4203 compute_self_dependence (struct data_dependence_relation *ddr)
4206 struct subscript *subscript;
4208 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
4211 /* The accessed index overlaps for each iteration. */
4212 SUB_CONFLICTS_IN_A (subscript)
4213 = conflict_fn (1, affine_fn_cst (integer_zero_node));
4214 SUB_CONFLICTS_IN_B (subscript)
4215 = conflict_fn (1, affine_fn_cst (integer_zero_node));
4216 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
4219 /* The distance vector is the zero vector. */
4220 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
4221 save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
4224 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4225 the data references in DATAREFS, in the LOOP_NEST. When
4226 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4230 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
4231 VEC (ddr_p, heap) **dependence_relations,
4232 VEC (loop_p, heap) *loop_nest,
4233 bool compute_self_and_rr)
4235 struct data_dependence_relation *ddr;
4236 struct data_reference *a, *b;
4239 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
4240 for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
4241 if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
4243 ddr = initialize_data_dependence_relation (a, b, loop_nest);
4244 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4245 compute_affine_dependence (ddr);
4248 if (compute_self_and_rr)
4249 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
4251 ddr = initialize_data_dependence_relation (a, a, loop_nest);
4252 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4253 compute_self_dependence (ddr);
4257 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4258 true if STMT clobbers memory, false otherwise. */
4261 get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references)
4263 bool clobbers_memory = false;
4265 tree *op0, *op1, arg, call;
4266 call_expr_arg_iterator iter;
4270 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4271 Calls have side-effects, except those to const or pure
4273 call = get_call_expr_in (stmt);
4275 && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE)))
4276 || (TREE_CODE (stmt) == ASM_EXPR
4277 && ASM_VOLATILE_P (stmt)))
4278 clobbers_memory = true;
4280 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
4281 return clobbers_memory;
4283 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
4285 op0 = &GIMPLE_STMT_OPERAND (stmt, 0);
4286 op1 = &GIMPLE_STMT_OPERAND (stmt, 1);
4289 || REFERENCE_CLASS_P (*op1))
4291 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4293 ref->is_read = true;
4297 || REFERENCE_CLASS_P (*op0))
4299 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4301 ref->is_read = false;
4307 FOR_EACH_CALL_EXPR_ARG (arg, iter, call)
4311 || REFERENCE_CLASS_P (*op0))
4313 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4315 ref->is_read = true;
4320 return clobbers_memory;
4323 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4324 reference, returns false, otherwise returns true. */
4327 find_data_references_in_stmt (tree stmt,
4328 VEC (data_reference_p, heap) **datarefs)
4331 VEC (data_ref_loc, heap) *references;
4334 data_reference_p dr;
4336 if (get_references_in_stmt (stmt, &references))
4338 VEC_free (data_ref_loc, heap, references);
4342 for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
4344 dr = create_data_ref (*ref->pos, stmt, ref->is_read);
4346 VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4353 VEC_free (data_ref_loc, heap, references);
4357 /* Search the data references in LOOP, and record the information into
4358 DATAREFS. Returns chrec_dont_know when failing to analyze a
4359 difficult case, returns NULL_TREE otherwise.
4361 TODO: This function should be made smarter so that it can handle address
4362 arithmetic as if they were array accesses, etc. */
4365 find_data_references_in_loop (struct loop *loop,
4366 VEC (data_reference_p, heap) **datarefs)
4368 basic_block bb, *bbs;
4370 block_stmt_iterator bsi;
4372 bbs = get_loop_body (loop);
4374 for (i = 0; i < loop->num_nodes; i++)
4378 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4380 tree stmt = bsi_stmt (bsi);
4382 if (!find_data_references_in_stmt (stmt, datarefs))
4384 struct data_reference *res;
4385 res = XNEW (struct data_reference);
4386 DR_STMT (res) = NULL_TREE;
4387 DR_REF (res) = NULL_TREE;
4388 DR_BASE_OBJECT (res) = NULL;
4389 DR_TYPE (res) = ARRAY_REF_TYPE;
4390 DR_SET_ACCESS_FNS (res, NULL);
4391 DR_BASE_OBJECT (res) = NULL;
4392 DR_IS_READ (res) = false;
4393 DR_BASE_ADDRESS (res) = NULL_TREE;
4394 DR_OFFSET (res) = NULL_TREE;
4395 DR_INIT (res) = NULL_TREE;
4396 DR_STEP (res) = NULL_TREE;
4397 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
4398 DR_MEMTAG (res) = NULL_TREE;
4399 DR_PTR_INFO (res) = NULL;
4400 VEC_safe_push (data_reference_p, heap, *datarefs, res);
4403 return chrec_dont_know;
4412 /* Recursive helper function. */
4415 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4417 /* Inner loops of the nest should not contain siblings. Example:
4418 when there are two consecutive loops,
4429 the dependence relation cannot be captured by the distance
4434 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4436 return find_loop_nest_1 (loop->inner, loop_nest);
4440 /* Return false when the LOOP is not well nested. Otherwise return
4441 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4442 contain the loops from the outermost to the innermost, as they will
4443 appear in the classic distance vector. */
4446 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4448 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4450 return find_loop_nest_1 (loop->inner, loop_nest);
4454 /* Given a loop nest LOOP, the following vectors are returned:
4455 DATAREFS is initialized to all the array elements contained in this loop,
4456 DEPENDENCE_RELATIONS contains the relations between the data references.
4457 Compute read-read and self relations if
4458 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4461 compute_data_dependences_for_loop (struct loop *loop,
4462 bool compute_self_and_read_read_dependences,
4463 VEC (data_reference_p, heap) **datarefs,
4464 VEC (ddr_p, heap) **dependence_relations)
4466 struct loop *loop_nest = loop;
4467 VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
4469 memset (&dependence_stats, 0, sizeof (dependence_stats));
4471 /* If the loop nest is not well formed, or one of the data references
4472 is not computable, give up without spending time to compute other
4475 || !find_loop_nest (loop_nest, &vloops)
4476 || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
4478 struct data_dependence_relation *ddr;
4480 /* Insert a single relation into dependence_relations:
4482 ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
4483 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4486 compute_all_dependences (*datarefs, dependence_relations, vloops,
4487 compute_self_and_read_read_dependences);
4489 if (dump_file && (dump_flags & TDF_STATS))
4491 fprintf (dump_file, "Dependence tester statistics:\n");
4493 fprintf (dump_file, "Number of dependence tests: %d\n",
4494 dependence_stats.num_dependence_tests);
4495 fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4496 dependence_stats.num_dependence_dependent);
4497 fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4498 dependence_stats.num_dependence_independent);
4499 fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4500 dependence_stats.num_dependence_undetermined);
4502 fprintf (dump_file, "Number of subscript tests: %d\n",
4503 dependence_stats.num_subscript_tests);
4504 fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4505 dependence_stats.num_subscript_undetermined);
4506 fprintf (dump_file, "Number of same subscript function: %d\n",
4507 dependence_stats.num_same_subscript_function);
4509 fprintf (dump_file, "Number of ziv tests: %d\n",
4510 dependence_stats.num_ziv);
4511 fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4512 dependence_stats.num_ziv_dependent);
4513 fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4514 dependence_stats.num_ziv_independent);
4515 fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4516 dependence_stats.num_ziv_unimplemented);
4518 fprintf (dump_file, "Number of siv tests: %d\n",
4519 dependence_stats.num_siv);
4520 fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4521 dependence_stats.num_siv_dependent);
4522 fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4523 dependence_stats.num_siv_independent);
4524 fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4525 dependence_stats.num_siv_unimplemented);
4527 fprintf (dump_file, "Number of miv tests: %d\n",
4528 dependence_stats.num_miv);
4529 fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4530 dependence_stats.num_miv_dependent);
4531 fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4532 dependence_stats.num_miv_independent);
4533 fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4534 dependence_stats.num_miv_unimplemented);
4538 /* Entry point (for testing only). Analyze all the data references
4539 and the dependence relations.
4541 The data references are computed first.
4543 A relation on these nodes is represented by a complete graph. Some
4544 of the relations could be of no interest, thus the relations can be
4547 In the following function we compute all the relations. This is
4548 just a first implementation that is here for:
4549 - for showing how to ask for the dependence relations,
4550 - for the debugging the whole dependence graph,
4551 - for the dejagnu testcases and maintenance.
4553 It is possible to ask only for a part of the graph, avoiding to
4554 compute the whole dependence graph. The computed dependences are
4555 stored in a knowledge base (KB) such that later queries don't
4556 recompute the same information. The implementation of this KB is
4557 transparent to the optimizer, and thus the KB can be changed with a
4558 more efficient implementation, or the KB could be disabled. */
4561 analyze_all_data_dependences (struct loops *loops)
4564 int nb_data_refs = 10;
4565 VEC (data_reference_p, heap) *datarefs =
4566 VEC_alloc (data_reference_p, heap, nb_data_refs);
4567 VEC (ddr_p, heap) *dependence_relations =
4568 VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
4570 /* Compute DDs on the whole function. */
4571 compute_data_dependences_for_loop (loops->parray[0], false,
4572 &datarefs, &dependence_relations);
4576 dump_data_dependence_relations (dump_file, dependence_relations);
4577 fprintf (dump_file, "\n\n");
4579 if (dump_flags & TDF_DETAILS)
4580 dump_dist_dir_vectors (dump_file, dependence_relations);
4582 if (dump_flags & TDF_STATS)
4584 unsigned nb_top_relations = 0;
4585 unsigned nb_bot_relations = 0;
4586 unsigned nb_basename_differ = 0;
4587 unsigned nb_chrec_relations = 0;
4588 struct data_dependence_relation *ddr;
4590 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4592 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4595 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4597 struct data_reference *a = DDR_A (ddr);
4598 struct data_reference *b = DDR_B (ddr);
4601 if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
4602 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
4603 || (base_object_differ_p (a, b, &differ_p)
4605 nb_basename_differ++;
4611 nb_chrec_relations++;
4614 gather_stats_on_scev_database ();
4618 free_dependence_relations (dependence_relations);
4619 free_data_refs (datarefs);
4623 /* Free the memory used by a data dependence relation DDR. */
4626 free_dependence_relation (struct data_dependence_relation *ddr)
4631 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
4632 free_subscripts (DDR_SUBSCRIPTS (ddr));
4637 /* Free the memory used by the data dependence relations from
4638 DEPENDENCE_RELATIONS. */
4641 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
4644 struct data_dependence_relation *ddr;
4645 VEC (loop_p, heap) *loop_nest = NULL;
4647 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4651 if (loop_nest == NULL)
4652 loop_nest = DDR_LOOP_NEST (ddr);
4654 gcc_assert (DDR_LOOP_NEST (ddr) == NULL
4655 || DDR_LOOP_NEST (ddr) == loop_nest);
4656 free_dependence_relation (ddr);
4660 VEC_free (loop_p, heap, loop_nest);
4661 VEC_free (ddr_p, heap, dependence_relations);
4664 /* Free the memory used by the data references from DATAREFS. */
4667 free_data_refs (VEC (data_reference_p, heap) *datarefs)
4670 struct data_reference *dr;
4672 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
4674 VEC_free (data_reference_p, heap, datarefs);