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 = get_var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag;
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);
176 if (pi_a && pi_a->name_mem_tag && pi_b && pi_b->name_mem_tag)
178 tag_a = pi_a->name_mem_tag;
179 tag_b = pi_b->name_mem_tag;
183 tag_a = get_var_ann (SSA_NAME_VAR (ptr_a))->symbol_mem_tag;
185 tag_a = DR_MEMTAG (dra);
189 tag_b = get_var_ann (SSA_NAME_VAR (ptr_b))->symbol_mem_tag;
191 tag_b = DR_MEMTAG (drb);
195 *aliased = (tag_a == tag_b);
200 /* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED.
201 Return FALSE if there is no symbol memory tag for one of the symbols. */
204 may_alias_p (tree base_a, tree base_b,
205 struct data_reference *dra,
206 struct data_reference *drb,
209 if (TREE_CODE (base_a) == ADDR_EXPR || TREE_CODE (base_b) == ADDR_EXPR)
211 if (TREE_CODE (base_a) == ADDR_EXPR && TREE_CODE (base_b) == ADDR_EXPR)
213 *aliased = (TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0));
216 if (TREE_CODE (base_a) == ADDR_EXPR)
217 return ptr_decl_may_alias_p (base_b, TREE_OPERAND (base_a, 0), drb,
220 return ptr_decl_may_alias_p (base_a, TREE_OPERAND (base_b, 0), dra,
224 return ptr_ptr_may_alias_p (base_a, base_b, dra, drb, aliased);
228 /* Determine if a pointer (BASE_A) and a record/union access (BASE_B)
229 are not aliased. Return TRUE if they differ. */
231 record_ptr_differ_p (struct data_reference *dra,
232 struct data_reference *drb)
235 tree base_a = DR_BASE_OBJECT (dra);
236 tree base_b = DR_BASE_OBJECT (drb);
238 if (TREE_CODE (base_b) != COMPONENT_REF)
241 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
242 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
243 Probably will be unnecessary with struct alias analysis. */
244 while (TREE_CODE (base_b) == COMPONENT_REF)
245 base_b = TREE_OPERAND (base_b, 0);
246 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
248 if (TREE_CODE (base_a) == INDIRECT_REF
249 && ((TREE_CODE (base_b) == VAR_DECL
250 && (ptr_decl_may_alias_p (TREE_OPERAND (base_a, 0), base_b, dra,
253 || (TREE_CODE (base_b) == INDIRECT_REF
254 && (ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0),
255 TREE_OPERAND (base_b, 0), dra, drb,
263 /* Determine if two record/union accesses are aliased. Return TRUE if they
266 record_record_differ_p (struct data_reference *dra,
267 struct data_reference *drb)
270 tree base_a = DR_BASE_OBJECT (dra);
271 tree base_b = DR_BASE_OBJECT (drb);
273 if (TREE_CODE (base_b) != COMPONENT_REF
274 || TREE_CODE (base_a) != COMPONENT_REF)
277 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
278 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
279 Probably will be unnecessary with struct alias analysis. */
280 while (TREE_CODE (base_b) == COMPONENT_REF)
281 base_b = TREE_OPERAND (base_b, 0);
282 while (TREE_CODE (base_a) == COMPONENT_REF)
283 base_a = TREE_OPERAND (base_a, 0);
285 if (TREE_CODE (base_a) == INDIRECT_REF
286 && TREE_CODE (base_b) == INDIRECT_REF
287 && ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0),
288 TREE_OPERAND (base_b, 0),
296 /* Determine if an array access (BASE_A) and a record/union access (BASE_B)
297 are not aliased. Return TRUE if they differ. */
299 record_array_differ_p (struct data_reference *dra,
300 struct data_reference *drb)
303 tree base_a = DR_BASE_OBJECT (dra);
304 tree base_b = DR_BASE_OBJECT (drb);
306 if (TREE_CODE (base_b) != COMPONENT_REF)
309 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
310 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
311 Probably will be unnecessary with struct alias analysis. */
312 while (TREE_CODE (base_b) == COMPONENT_REF)
313 base_b = TREE_OPERAND (base_b, 0);
315 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
316 (a[i]). In case of p->c[i] use alias analysis to verify that p is not
318 if (TREE_CODE (base_a) == VAR_DECL
319 && (TREE_CODE (base_b) == VAR_DECL
320 || (TREE_CODE (base_b) == INDIRECT_REF
321 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb,
330 /* Determine if an array access (BASE_A) and a pointer (BASE_B)
331 are not aliased. Return TRUE if they differ. */
333 array_ptr_differ_p (tree base_a, tree base_b,
334 struct data_reference *drb)
338 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
339 help of alias analysis that p is not pointing to a. */
340 if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == INDIRECT_REF
341 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, &aliased)
349 /* This is the simplest data dependence test: determines whether the
350 data references A and B access the same array/region. Returns
351 false when the property is not computable at compile time.
352 Otherwise return true, and DIFFER_P will record the result. This
353 utility will not be necessary when alias_sets_conflict_p will be
354 less conservative. */
357 base_object_differ_p (struct data_reference *a,
358 struct data_reference *b,
361 tree base_a = DR_BASE_OBJECT (a);
362 tree base_b = DR_BASE_OBJECT (b);
365 if (!base_a || !base_b)
368 /* Determine if same base. Example: for the array accesses
369 a[i], b[i] or pointer accesses *a, *b, bases are a, b. */
370 if (base_a == base_b)
376 /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
378 if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
379 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0))
385 /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */
386 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
387 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)
388 && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1))
395 /* Determine if different bases. */
397 /* At this point we know that base_a != base_b. However, pointer
398 accesses of the form x=(*p) and y=(*q), whose bases are p and q,
399 may still be pointing to the same base. In SSAed GIMPLE p and q will
400 be SSA_NAMES in this case. Therefore, here we check if they are
401 really two different declarations. */
402 if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
408 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
409 help of alias analysis that p is not pointing to a. */
410 if (array_ptr_differ_p (base_a, base_b, b)
411 || array_ptr_differ_p (base_b, base_a, a))
417 /* If the bases are pointers ((*q)[i] and (*p)[i]), we check with the
418 help of alias analysis they don't point to the same bases. */
419 if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
420 && (may_alias_p (TREE_OPERAND (base_a, 0), TREE_OPERAND (base_b, 0), a, b,
428 /* Compare two record/union bases s.a and t.b: s != t or (a != b and
429 s and t are not unions). */
430 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
431 && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
432 && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
433 && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
434 || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE
435 && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
436 && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
442 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
444 if (record_ptr_differ_p (a, b) || record_ptr_differ_p (b, a))
450 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
451 (a[i]). In case of p->c[i] use alias analysis to verify that p is not
453 if (record_array_differ_p (a, b) || record_array_differ_p (b, a))
459 /* Compare two record/union accesses (b.c[i] or p->c[i]). */
460 if (record_record_differ_p (a, b))
469 /* Function base_addr_differ_p.
471 This is the simplest data dependence test: determines whether the
472 data references DRA and DRB access the same array/region. Returns
473 false when the property is not computable at compile time.
474 Otherwise return true, and DIFFER_P will record the result.
477 1. if (both DRA and DRB are represented as arrays)
478 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT
479 2. else if (both DRA and DRB are represented as pointers)
480 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION
481 3. else if (DRA and DRB are represented differently or 2. fails)
482 only try to prove that the bases are surely different
486 base_addr_differ_p (struct data_reference *dra,
487 struct data_reference *drb,
490 tree addr_a = DR_BASE_ADDRESS (dra);
491 tree addr_b = DR_BASE_ADDRESS (drb);
495 if (!addr_a || !addr_b)
498 type_a = TREE_TYPE (addr_a);
499 type_b = TREE_TYPE (addr_b);
501 gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
503 /* 1. if (both DRA and DRB are represented as arrays)
504 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT. */
505 if (DR_TYPE (dra) == ARRAY_REF_TYPE && DR_TYPE (drb) == ARRAY_REF_TYPE)
506 return base_object_differ_p (dra, drb, differ_p);
508 /* 2. else if (both DRA and DRB are represented as pointers)
509 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION. */
510 /* If base addresses are the same, we check the offsets, since the access of
511 the data-ref is described by {base addr + offset} and its access function,
512 i.e., in order to decide whether the bases of data-refs are the same we
513 compare both base addresses and offsets. */
514 if (DR_TYPE (dra) == POINTER_REF_TYPE && DR_TYPE (drb) == POINTER_REF_TYPE
516 || (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR
517 && TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0))))
519 /* Compare offsets. */
520 tree offset_a = DR_OFFSET (dra);
521 tree offset_b = DR_OFFSET (drb);
523 STRIP_NOPS (offset_a);
524 STRIP_NOPS (offset_b);
526 /* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle
528 if (offset_a == offset_b
529 || (TREE_CODE (offset_a) == MULT_EXPR
530 && TREE_CODE (offset_b) == MULT_EXPR
531 && TREE_OPERAND (offset_a, 0) == TREE_OPERAND (offset_b, 0)
532 && TREE_OPERAND (offset_a, 1) == TREE_OPERAND (offset_b, 1)))
539 /* 3. else if (DRA and DRB are represented differently or 2. fails)
540 only try to prove that the bases are surely different. */
542 /* Apply alias analysis. */
543 if (may_alias_p (addr_a, addr_b, dra, drb, &aliased) && !aliased)
549 /* An instruction writing through a restricted pointer is "independent" of any
550 instruction reading or writing through a different pointer, in the same
552 else if ((TYPE_RESTRICT (type_a) && !DR_IS_READ (dra))
553 || (TYPE_RESTRICT (type_b) && !DR_IS_READ (drb)))
561 /* Returns true iff A divides B. */
564 tree_fold_divides_p (tree a,
567 /* Determines whether (A == gcd (A, B)). */
568 return tree_int_cst_equal (a, tree_fold_gcd (a, b));
571 /* Returns true iff A divides B. */
574 int_divides_p (int a, int b)
576 return ((b % a) == 0);
581 /* Dump into FILE all the data references from DATAREFS. */
584 dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
587 struct data_reference *dr;
589 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
590 dump_data_reference (file, dr);
593 /* Dump into FILE all the dependence relations from DDRS. */
596 dump_data_dependence_relations (FILE *file,
597 VEC (ddr_p, heap) *ddrs)
600 struct data_dependence_relation *ddr;
602 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
603 dump_data_dependence_relation (file, ddr);
606 /* Dump function for a DATA_REFERENCE structure. */
609 dump_data_reference (FILE *outf,
610 struct data_reference *dr)
614 fprintf (outf, "(Data Ref: \n stmt: ");
615 print_generic_stmt (outf, DR_STMT (dr), 0);
616 fprintf (outf, " ref: ");
617 print_generic_stmt (outf, DR_REF (dr), 0);
618 fprintf (outf, " base_object: ");
619 print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
621 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
623 fprintf (outf, " Access function %d: ", i);
624 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
626 fprintf (outf, ")\n");
629 /* Dump function for a SUBSCRIPT structure. */
632 dump_subscript (FILE *outf, struct subscript *subscript)
634 tree chrec = SUB_CONFLICTS_IN_A (subscript);
636 fprintf (outf, "\n (subscript \n");
637 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
638 print_generic_stmt (outf, chrec, 0);
639 if (chrec == chrec_known)
640 fprintf (outf, " (no dependence)\n");
641 else if (chrec_contains_undetermined (chrec))
642 fprintf (outf, " (don't know)\n");
645 tree last_iteration = SUB_LAST_CONFLICT (subscript);
646 fprintf (outf, " last_conflict: ");
647 print_generic_stmt (outf, last_iteration, 0);
650 chrec = SUB_CONFLICTS_IN_B (subscript);
651 fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
652 print_generic_stmt (outf, chrec, 0);
653 if (chrec == chrec_known)
654 fprintf (outf, " (no dependence)\n");
655 else if (chrec_contains_undetermined (chrec))
656 fprintf (outf, " (don't know)\n");
659 tree last_iteration = SUB_LAST_CONFLICT (subscript);
660 fprintf (outf, " last_conflict: ");
661 print_generic_stmt (outf, last_iteration, 0);
664 fprintf (outf, " (Subscript distance: ");
665 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
666 fprintf (outf, " )\n");
667 fprintf (outf, " )\n");
670 /* Print the classic direction vector DIRV to OUTF. */
673 print_direction_vector (FILE *outf,
679 for (eq = 0; eq < length; eq++)
681 enum data_dependence_direction dir = dirv[eq];
686 fprintf (outf, " +");
689 fprintf (outf, " -");
692 fprintf (outf, " =");
694 case dir_positive_or_equal:
695 fprintf (outf, " +=");
697 case dir_positive_or_negative:
698 fprintf (outf, " +-");
700 case dir_negative_or_equal:
701 fprintf (outf, " -=");
704 fprintf (outf, " *");
707 fprintf (outf, "indep");
711 fprintf (outf, "\n");
714 /* Print a vector of direction vectors. */
717 print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
723 for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++)
724 print_direction_vector (outf, v, length);
727 /* Print a vector of distance vectors. */
730 print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
736 for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++)
737 print_lambda_vector (outf, v, length);
743 debug_data_dependence_relation (struct data_dependence_relation *ddr)
745 dump_data_dependence_relation (stderr, ddr);
748 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
751 dump_data_dependence_relation (FILE *outf,
752 struct data_dependence_relation *ddr)
754 struct data_reference *dra, *drb;
758 fprintf (outf, "(Data Dep: \n");
759 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
760 fprintf (outf, " (don't know)\n");
762 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
763 fprintf (outf, " (no dependence)\n");
765 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
770 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
772 fprintf (outf, " access_fn_A: ");
773 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
774 fprintf (outf, " access_fn_B: ");
775 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
776 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
779 fprintf (outf, " loop nest: (");
780 for (i = 0; VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
781 fprintf (outf, "%d ", loopi->num);
782 fprintf (outf, ")\n");
784 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
786 fprintf (outf, " distance_vector: ");
787 print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
791 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
793 fprintf (outf, " direction_vector: ");
794 print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
799 fprintf (outf, ")\n");
802 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
805 dump_data_dependence_direction (FILE *file,
806 enum data_dependence_direction dir)
822 case dir_positive_or_negative:
823 fprintf (file, "+-");
826 case dir_positive_or_equal:
827 fprintf (file, "+=");
830 case dir_negative_or_equal:
831 fprintf (file, "-=");
843 /* Dumps the distance and direction vectors in FILE. DDRS contains
844 the dependence relations, and VECT_SIZE is the size of the
845 dependence vectors, or in other words the number of loops in the
849 dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
852 struct data_dependence_relation *ddr;
855 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
856 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
858 for (j = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), j, v); j++)
860 fprintf (file, "DISTANCE_V (");
861 print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
862 fprintf (file, ")\n");
865 for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++)
867 fprintf (file, "DIRECTION_V (");
868 print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
869 fprintf (file, ")\n");
873 fprintf (file, "\n\n");
876 /* Dumps the data dependence relations DDRS in FILE. */
879 dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
882 struct data_dependence_relation *ddr;
884 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
885 dump_data_dependence_relation (file, ddr);
887 fprintf (file, "\n\n");
892 /* Given an ARRAY_REF node REF, records its access functions.
893 Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
894 i.e. the constant "3", then recursively call the function on opnd0,
895 i.e. the ARRAY_REF "A[i]".
896 The function returns the base name: "A". */
899 analyze_array_indexes (struct loop *loop,
900 VEC(tree,heap) **access_fns,
906 opnd0 = TREE_OPERAND (ref, 0);
907 opnd1 = TREE_OPERAND (ref, 1);
909 /* The detection of the evolution function for this data access is
910 postponed until the dependence test. This lazy strategy avoids
911 the computation of access functions that are of no interest for
913 access_fn = instantiate_parameters
914 (loop, analyze_scalar_evolution (loop, opnd1));
916 VEC_safe_push (tree, heap, *access_fns, access_fn);
918 /* Recursively record other array access functions. */
919 if (TREE_CODE (opnd0) == ARRAY_REF)
920 return analyze_array_indexes (loop, access_fns, opnd0, stmt);
922 /* Return the base name of the data access. */
927 /* For a data reference REF contained in the statement STMT, initialize
928 a DATA_REFERENCE structure, and return it. IS_READ flag has to be
929 set to true when REF is in the right hand side of an
932 struct data_reference *
933 analyze_array (tree stmt, tree ref, bool is_read)
935 struct data_reference *res;
936 VEC(tree,heap) *acc_fns;
938 if (dump_file && (dump_flags & TDF_DETAILS))
940 fprintf (dump_file, "(analyze_array \n");
941 fprintf (dump_file, " (ref = ");
942 print_generic_stmt (dump_file, ref, 0);
943 fprintf (dump_file, ")\n");
946 res = XNEW (struct data_reference);
948 DR_STMT (res) = stmt;
950 acc_fns = VEC_alloc (tree, heap, 3);
951 DR_BASE_OBJECT (res) = analyze_array_indexes
952 (loop_containing_stmt (stmt), &acc_fns, ref, stmt);
953 DR_TYPE (res) = ARRAY_REF_TYPE;
954 DR_SET_ACCESS_FNS (res, acc_fns);
955 DR_IS_READ (res) = is_read;
956 DR_BASE_ADDRESS (res) = NULL_TREE;
957 DR_OFFSET (res) = NULL_TREE;
958 DR_INIT (res) = NULL_TREE;
959 DR_STEP (res) = NULL_TREE;
960 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
961 DR_MEMTAG (res) = NULL_TREE;
962 DR_PTR_INFO (res) = NULL;
964 if (dump_file && (dump_flags & TDF_DETAILS))
965 fprintf (dump_file, ")\n");
970 /* Analyze an indirect memory reference, REF, that comes from STMT.
971 IS_READ is true if this is an indirect load, and false if it is
973 Return a new data reference structure representing the indirect_ref, or
974 NULL if we cannot describe the access function. */
976 static struct data_reference *
977 analyze_indirect_ref (tree stmt, tree ref, bool is_read)
979 struct loop *loop = loop_containing_stmt (stmt);
980 tree ptr_ref = TREE_OPERAND (ref, 0);
981 tree access_fn = analyze_scalar_evolution (loop, ptr_ref);
982 tree init = initial_condition_in_loop_num (access_fn, loop->num);
983 tree base_address = NULL_TREE, evolution, step = NULL_TREE;
984 struct ptr_info_def *ptr_info = NULL;
986 if (TREE_CODE (ptr_ref) == SSA_NAME)
987 ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
990 if (access_fn == chrec_dont_know || !init || init == chrec_dont_know)
992 if (dump_file && (dump_flags & TDF_DETAILS))
994 fprintf (dump_file, "\nBad access function of ptr: ");
995 print_generic_expr (dump_file, ref, TDF_SLIM);
996 fprintf (dump_file, "\n");
1001 if (dump_file && (dump_flags & TDF_DETAILS))
1003 fprintf (dump_file, "\nAccess function of ptr: ");
1004 print_generic_expr (dump_file, access_fn, TDF_SLIM);
1005 fprintf (dump_file, "\n");
1008 if (!expr_invariant_in_loop_p (loop, init))
1010 if (dump_file && (dump_flags & TDF_DETAILS))
1011 fprintf (dump_file, "\ninitial condition is not loop invariant.\n");
1015 base_address = init;
1016 evolution = evolution_part_in_loop_num (access_fn, loop->num);
1017 if (evolution != chrec_dont_know)
1020 step = ssize_int (0);
1023 if (TREE_CODE (evolution) == INTEGER_CST)
1024 step = fold_convert (ssizetype, evolution);
1026 if (dump_file && (dump_flags & TDF_DETAILS))
1027 fprintf (dump_file, "\nnon constant step for ptr access.\n");
1031 if (dump_file && (dump_flags & TDF_DETAILS))
1032 fprintf (dump_file, "\nunknown evolution of ptr.\n");
1034 return init_data_ref (stmt, ref, NULL_TREE, access_fn, is_read, base_address,
1035 NULL_TREE, step, NULL_TREE, NULL_TREE,
1036 ptr_info, POINTER_REF_TYPE);
1039 /* For a data reference REF contained in the statement STMT, initialize
1040 a DATA_REFERENCE structure, and return it. */
1042 struct data_reference *
1043 init_data_ref (tree stmt,
1053 struct ptr_info_def *ptr_info,
1054 enum data_ref_type type)
1056 struct data_reference *res;
1057 VEC(tree,heap) *acc_fns;
1059 if (dump_file && (dump_flags & TDF_DETAILS))
1061 fprintf (dump_file, "(init_data_ref \n");
1062 fprintf (dump_file, " (ref = ");
1063 print_generic_stmt (dump_file, ref, 0);
1064 fprintf (dump_file, ")\n");
1067 res = XNEW (struct data_reference);
1069 DR_STMT (res) = stmt;
1071 DR_BASE_OBJECT (res) = base;
1072 DR_TYPE (res) = type;
1073 acc_fns = VEC_alloc (tree, heap, 3);
1074 DR_SET_ACCESS_FNS (res, acc_fns);
1075 VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
1076 DR_IS_READ (res) = is_read;
1077 DR_BASE_ADDRESS (res) = base_address;
1078 DR_OFFSET (res) = init_offset;
1079 DR_INIT (res) = NULL_TREE;
1080 DR_STEP (res) = step;
1081 DR_OFFSET_MISALIGNMENT (res) = misalign;
1082 DR_MEMTAG (res) = memtag;
1083 DR_PTR_INFO (res) = ptr_info;
1085 if (dump_file && (dump_flags & TDF_DETAILS))
1086 fprintf (dump_file, ")\n");
1091 /* Function strip_conversions
1093 Strip conversions that don't narrow the mode. */
1096 strip_conversion (tree expr)
1098 tree to, ti, oprnd0;
1100 while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
1102 to = TREE_TYPE (expr);
1103 oprnd0 = TREE_OPERAND (expr, 0);
1104 ti = TREE_TYPE (oprnd0);
1106 if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti))
1108 if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti)))
1117 /* Function analyze_offset_expr
1119 Given an offset expression EXPR received from get_inner_reference, analyze
1120 it and create an expression for INITIAL_OFFSET by substituting the variables
1121 of EXPR with initial_condition of the corresponding access_fn in the loop.
1124 for (j = 3; j < N; j++)
1127 For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be
1128 substituted, since its access_fn in the inner loop is i. 'j' will be
1129 substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
1132 Compute MISALIGN (the misalignment of the data reference initial access from
1133 its base). Misalignment can be calculated only if all the variables can be
1134 substituted with constants, otherwise, we record maximum possible alignment
1135 in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN
1136 will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be
1137 recorded in ALIGNED_TO.
1139 STEP is an evolution of the data reference in this loop in bytes.
1140 In the above example, STEP is C_j.
1142 Return FALSE, if the analysis fails, e.g., there is no access_fn for a
1143 variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO
1144 and STEP) are NULL_TREEs. Otherwise, return TRUE.
1149 analyze_offset_expr (tree expr,
1151 tree *initial_offset,
1158 tree left_offset = ssize_int (0);
1159 tree right_offset = ssize_int (0);
1160 tree left_misalign = ssize_int (0);
1161 tree right_misalign = ssize_int (0);
1162 tree left_step = ssize_int (0);
1163 tree right_step = ssize_int (0);
1164 enum tree_code code;
1165 tree init, evolution;
1166 tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE;
1169 *misalign = NULL_TREE;
1170 *aligned_to = NULL_TREE;
1171 *initial_offset = NULL_TREE;
1173 /* Strip conversions that don't narrow the mode. */
1174 expr = strip_conversion (expr);
1180 if (TREE_CODE (expr) == INTEGER_CST)
1182 *initial_offset = fold_convert (ssizetype, expr);
1183 *misalign = fold_convert (ssizetype, expr);
1184 *step = ssize_int (0);
1188 /* 2. Variable. Try to substitute with initial_condition of the corresponding
1189 access_fn in the current loop. */
1190 if (SSA_VAR_P (expr))
1192 tree access_fn = analyze_scalar_evolution (loop, expr);
1194 if (access_fn == chrec_dont_know)
1198 init = initial_condition_in_loop_num (access_fn, loop->num);
1199 if (!expr_invariant_in_loop_p (loop, init))
1200 /* Not enough information: may be not loop invariant.
1201 E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
1202 initial_condition is D, but it depends on i - loop's induction
1206 evolution = evolution_part_in_loop_num (access_fn, loop->num);
1207 if (evolution && TREE_CODE (evolution) != INTEGER_CST)
1208 /* Evolution is not constant. */
1211 if (TREE_CODE (init) == INTEGER_CST)
1212 *misalign = fold_convert (ssizetype, init);
1214 /* Not constant, misalignment cannot be calculated. */
1215 *misalign = NULL_TREE;
1217 *initial_offset = fold_convert (ssizetype, init);
1219 *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
1223 /* Recursive computation. */
1224 if (!BINARY_CLASS_P (expr))
1226 /* We expect to get binary expressions (PLUS/MINUS and MULT). */
1227 if (dump_file && (dump_flags & TDF_DETAILS))
1229 fprintf (dump_file, "\nNot binary expression ");
1230 print_generic_expr (dump_file, expr, TDF_SLIM);
1231 fprintf (dump_file, "\n");
1235 oprnd0 = TREE_OPERAND (expr, 0);
1236 oprnd1 = TREE_OPERAND (expr, 1);
1238 if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign,
1239 &left_aligned_to, &left_step)
1240 || !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign,
1241 &right_aligned_to, &right_step))
1244 /* The type of the operation: plus, minus or mult. */
1245 code = TREE_CODE (expr);
1249 if (TREE_CODE (right_offset) != INTEGER_CST)
1250 /* RIGHT_OFFSET can be not constant. For example, for arrays of variable
1252 FORNOW: We don't support such cases. */
1255 /* Strip conversions that don't narrow the mode. */
1256 left_offset = strip_conversion (left_offset);
1259 /* Misalignment computation. */
1260 if (SSA_VAR_P (left_offset))
1262 /* If the left side contains variables that can't be substituted with
1263 constants, the misalignment is unknown. However, if the right side
1264 is a multiple of some alignment, we know that the expression is
1265 aligned to it. Therefore, we record such maximum possible value.
1267 *misalign = NULL_TREE;
1268 *aligned_to = ssize_int (highest_pow2_factor (right_offset));
1272 /* The left operand was successfully substituted with constant. */
1275 /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is
1277 *misalign = size_binop (code, left_misalign, right_misalign);
1278 if (left_aligned_to && right_aligned_to)
1279 *aligned_to = size_binop (MIN_EXPR, left_aligned_to,
1282 *aligned_to = left_aligned_to ?
1283 left_aligned_to : right_aligned_to;
1286 *misalign = NULL_TREE;
1289 /* Step calculation. */
1290 /* Multiply the step by the right operand. */
1291 *step = size_binop (MULT_EXPR, left_step, right_offset);
1296 /* Combine the recursive calculations for step and misalignment. */
1297 *step = size_binop (code, left_step, right_step);
1299 /* Unknown alignment. */
1300 if ((!left_misalign && !left_aligned_to)
1301 || (!right_misalign && !right_aligned_to))
1303 *misalign = NULL_TREE;
1304 *aligned_to = NULL_TREE;
1308 if (left_misalign && right_misalign)
1309 *misalign = size_binop (code, left_misalign, right_misalign);
1311 *misalign = left_misalign ? left_misalign : right_misalign;
1313 if (left_aligned_to && right_aligned_to)
1314 *aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to);
1316 *aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to;
1324 /* Compute offset. */
1325 *initial_offset = fold_convert (ssizetype,
1326 fold_build2 (code, TREE_TYPE (left_offset),
1332 /* Function address_analysis
1334 Return the BASE of the address expression EXPR.
1335 Also compute the OFFSET from BASE, MISALIGN and STEP.
1338 EXPR - the address expression that is being analyzed
1339 STMT - the statement that contains EXPR or its original memory reference
1340 IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
1341 DR - data_reference struct for the original memory reference
1344 BASE (returned value) - the base of the data reference EXPR.
1345 INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
1346 MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
1347 computation is impossible
1348 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1349 calculated (doesn't depend on variables)
1350 STEP - evolution of EXPR in the loop
1352 If something unexpected is encountered (an unsupported form of data-ref),
1353 then NULL_TREE is returned.
1357 address_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr,
1358 tree *offset, tree *misalign, tree *aligned_to, tree *step)
1360 tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
1361 tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1362 tree dummy, address_aligned_to = NULL_TREE;
1363 struct ptr_info_def *dummy1;
1366 switch (TREE_CODE (expr))
1370 /* EXPR is of form {base +/- offset} (or {offset +/- base}). */
1371 oprnd0 = TREE_OPERAND (expr, 0);
1372 oprnd1 = TREE_OPERAND (expr, 1);
1374 STRIP_NOPS (oprnd0);
1375 STRIP_NOPS (oprnd1);
1377 /* Recursively try to find the base of the address contained in EXPR.
1378 For offset, the returned base will be NULL. */
1379 base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset,
1380 &address_misalign, &address_aligned_to,
1383 base_addr1 = address_analysis (oprnd1, stmt, is_read, dr, &address_offset,
1384 &address_misalign, &address_aligned_to,
1387 /* We support cases where only one of the operands contains an
1389 if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
1391 if (dump_file && (dump_flags & TDF_DETAILS))
1394 "\neither more than one address or no addresses in expr ");
1395 print_generic_expr (dump_file, expr, TDF_SLIM);
1396 fprintf (dump_file, "\n");
1401 /* To revert STRIP_NOPS. */
1402 oprnd0 = TREE_OPERAND (expr, 0);
1403 oprnd1 = TREE_OPERAND (expr, 1);
1405 offset_expr = base_addr0 ?
1406 fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
1408 /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is
1409 a number, we can add it to the misalignment value calculated for base,
1410 otherwise, misalignment is NULL. */
1411 if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
1413 *misalign = size_binop (TREE_CODE (expr), address_misalign,
1415 *aligned_to = address_aligned_to;
1419 *misalign = NULL_TREE;
1420 *aligned_to = NULL_TREE;
1423 /* Combine offset (from EXPR {base + offset}) with the offset calculated
1425 *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
1426 return base_addr0 ? base_addr0 : base_addr1;
1429 base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read,
1430 &dr, offset, misalign, aligned_to, step,
1431 &dummy, &dummy1, &dummy2);
1432 return base_address;
1435 if (!POINTER_TYPE_P (TREE_TYPE (expr)))
1437 if (dump_file && (dump_flags & TDF_DETAILS))
1439 fprintf (dump_file, "\nnot pointer SSA_NAME ");
1440 print_generic_expr (dump_file, expr, TDF_SLIM);
1441 fprintf (dump_file, "\n");
1445 *aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr))));
1446 *misalign = ssize_int (0);
1447 *offset = ssize_int (0);
1448 *step = ssize_int (0);
1457 /* Function object_analysis
1459 Create a data-reference structure DR for MEMREF.
1460 Return the BASE of the data reference MEMREF if the analysis is possible.
1461 Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1462 E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset
1463 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET
1464 instantiated with initial_conditions of access_functions of variables,
1465 and STEP is the evolution of the DR_REF in this loop.
1467 Function get_inner_reference is used for the above in case of ARRAY_REF and
1470 The structure of the function is as follows:
1472 Case 1. For handled_component_p refs
1473 1.1 build data-reference structure for MEMREF
1474 1.2 call get_inner_reference
1475 1.2.1 analyze offset expr received from get_inner_reference
1476 (fall through with BASE)
1477 Case 2. For declarations
1479 Case 3. For INDIRECT_REFs
1480 3.1 build data-reference structure for MEMREF
1481 3.2 analyze evolution and initial condition of MEMREF
1482 3.3 set data-reference structure for MEMREF
1483 3.4 call address_analysis to analyze INIT of the access function
1484 3.5 extract memory tag
1487 Combine the results of object and address analysis to calculate
1488 INITIAL_OFFSET, STEP and misalignment info.
1491 MEMREF - the memory reference that is being analyzed
1492 STMT - the statement that contains MEMREF
1493 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1496 BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
1497 E.g, if MEMREF is a.b[k].c[i][j] the returned
1499 DR - data_reference struct for MEMREF
1500 INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
1501 MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of
1502 ALIGNMENT or NULL_TREE if the computation is impossible
1503 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1504 calculated (doesn't depend on variables)
1505 STEP - evolution of the DR_REF in the loop
1506 MEMTAG - memory tag for aliasing purposes
1507 PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
1508 SUBVARS - Sub-variables of the variable
1510 If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned,
1511 but DR can be created anyway.
1516 object_analysis (tree memref, tree stmt, bool is_read,
1517 struct data_reference **dr, tree *offset, tree *misalign,
1518 tree *aligned_to, tree *step, tree *memtag,
1519 struct ptr_info_def **ptr_info, subvar_t *subvars)
1521 tree base = NULL_TREE, base_address = NULL_TREE;
1522 tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
1523 tree object_step = ssize_int (0), address_step = ssize_int (0);
1524 tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1525 HOST_WIDE_INT pbitsize, pbitpos;
1526 tree poffset, bit_pos_in_bytes;
1527 enum machine_mode pmode;
1528 int punsignedp, pvolatilep;
1529 tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
1530 struct loop *loop = loop_containing_stmt (stmt);
1531 struct data_reference *ptr_dr = NULL;
1532 tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE;
1533 tree comp_ref = NULL_TREE;
1538 /* Case 1. handled_component_p refs. */
1539 if (handled_component_p (memref))
1541 /* 1.1 build data-reference structure for MEMREF. */
1544 if (TREE_CODE (memref) == ARRAY_REF)
1545 *dr = analyze_array (stmt, memref, is_read);
1546 else if (TREE_CODE (memref) == COMPONENT_REF)
1550 if (dump_file && (dump_flags & TDF_DETAILS))
1552 fprintf (dump_file, "\ndata-ref of unsupported type ");
1553 print_generic_expr (dump_file, memref, TDF_SLIM);
1554 fprintf (dump_file, "\n");
1560 /* 1.2 call get_inner_reference. */
1561 /* Find the base and the offset from it. */
1562 base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
1563 &pmode, &punsignedp, &pvolatilep, false);
1566 if (dump_file && (dump_flags & TDF_DETAILS))
1568 fprintf (dump_file, "\nfailed to get inner ref for ");
1569 print_generic_expr (dump_file, memref, TDF_SLIM);
1570 fprintf (dump_file, "\n");
1575 /* 1.2.1 analyze offset expr received from get_inner_reference. */
1577 && !analyze_offset_expr (poffset, loop, &object_offset,
1578 &object_misalign, &object_aligned_to,
1581 if (dump_file && (dump_flags & TDF_DETAILS))
1583 fprintf (dump_file, "\nfailed to compute offset or step for ");
1584 print_generic_expr (dump_file, memref, TDF_SLIM);
1585 fprintf (dump_file, "\n");
1590 /* Add bit position to OFFSET and MISALIGN. */
1592 bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
1593 /* Check that there is no remainder in bits. */
1594 if (pbitpos%BITS_PER_UNIT)
1596 if (dump_file && (dump_flags & TDF_DETAILS))
1597 fprintf (dump_file, "\nbit offset alignment.\n");
1600 object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);
1601 if (object_misalign)
1602 object_misalign = size_binop (PLUS_EXPR, object_misalign,
1605 memref = base; /* To continue analysis of BASE. */
1609 /* Part 1: Case 2. Declarations. */
1610 if (DECL_P (memref))
1612 /* We expect to get a decl only if we already have a DR, or with
1613 COMPONENT_REFs of type 'a[i].b'. */
1616 if (comp_ref && TREE_CODE (TREE_OPERAND (comp_ref, 0)) == ARRAY_REF)
1618 *dr = analyze_array (stmt, TREE_OPERAND (comp_ref, 0), is_read);
1619 if (DR_NUM_DIMENSIONS (*dr) != 1)
1621 if (dump_file && (dump_flags & TDF_DETAILS))
1623 fprintf (dump_file, "\n multidimensional component ref ");
1624 print_generic_expr (dump_file, comp_ref, TDF_SLIM);
1625 fprintf (dump_file, "\n");
1632 if (dump_file && (dump_flags & TDF_DETAILS))
1634 fprintf (dump_file, "\nunhandled decl ");
1635 print_generic_expr (dump_file, memref, TDF_SLIM);
1636 fprintf (dump_file, "\n");
1642 /* TODO: if during the analysis of INDIRECT_REF we get to an object, put
1643 the object in BASE_OBJECT field if we can prove that this is O.K.,
1644 i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT.
1645 (e.g., if the object is an array base 'a', where 'a[N]', we must prove
1646 that every access with 'p' (the original INDIRECT_REF based on '&a')
1647 in the loop is within the array boundaries - from a[0] to a[N-1]).
1648 Otherwise, our alias analysis can be incorrect.
1649 Even if an access function based on BASE_OBJECT can't be build, update
1650 BASE_OBJECT field to enable us to prove that two data-refs are
1651 different (without access function, distance analysis is impossible).
1653 if (SSA_VAR_P (memref) && var_can_have_subvars (memref))
1654 *subvars = get_subvars_for_var (memref);
1655 base_address = build_fold_addr_expr (memref);
1656 /* 2.1 set MEMTAG. */
1660 /* Part 1: Case 3. INDIRECT_REFs. */
1661 else if (TREE_CODE (memref) == INDIRECT_REF)
1663 tree ptr_ref = TREE_OPERAND (memref, 0);
1664 if (TREE_CODE (ptr_ref) == SSA_NAME)
1665 *ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
1667 /* 3.1 build data-reference structure for MEMREF. */
1668 ptr_dr = analyze_indirect_ref (stmt, memref, is_read);
1671 if (dump_file && (dump_flags & TDF_DETAILS))
1673 fprintf (dump_file, "\nfailed to create dr for ");
1674 print_generic_expr (dump_file, memref, TDF_SLIM);
1675 fprintf (dump_file, "\n");
1680 /* 3.2 analyze evolution and initial condition of MEMREF. */
1681 ptr_step = DR_STEP (ptr_dr);
1682 ptr_init = DR_BASE_ADDRESS (ptr_dr);
1683 if (!ptr_init || !ptr_step || !POINTER_TYPE_P (TREE_TYPE (ptr_init)))
1685 *dr = (*dr) ? *dr : ptr_dr;
1686 if (dump_file && (dump_flags & TDF_DETAILS))
1688 fprintf (dump_file, "\nbad pointer access ");
1689 print_generic_expr (dump_file, memref, TDF_SLIM);
1690 fprintf (dump_file, "\n");
1695 if (integer_zerop (ptr_step) && !(*dr))
1697 if (dump_file && (dump_flags & TDF_DETAILS))
1698 fprintf (dump_file, "\nptr is loop invariant.\n");
1702 /* If there exists DR for MEMREF, we are analyzing the base of
1703 handled component (PTR_INIT), which not necessary has evolution in
1706 object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
1708 /* 3.3 set data-reference structure for MEMREF. */
1712 /* 3.4 call address_analysis to analyze INIT of the access
1714 base_address = address_analysis (ptr_init, stmt, is_read, *dr,
1715 &address_offset, &address_misalign,
1716 &address_aligned_to, &address_step);
1719 if (dump_file && (dump_flags & TDF_DETAILS))
1721 fprintf (dump_file, "\nfailed to analyze address ");
1722 print_generic_expr (dump_file, ptr_init, TDF_SLIM);
1723 fprintf (dump_file, "\n");
1728 /* 3.5 extract memory tag. */
1729 switch (TREE_CODE (base_address))
1732 *memtag = get_var_ann (SSA_NAME_VAR (base_address))->symbol_mem_tag;
1733 if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
1734 *memtag = get_var_ann (
1735 SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->symbol_mem_tag;
1738 *memtag = TREE_OPERAND (base_address, 0);
1741 if (dump_file && (dump_flags & TDF_DETAILS))
1743 fprintf (dump_file, "\nno memtag for ");
1744 print_generic_expr (dump_file, memref, TDF_SLIM);
1745 fprintf (dump_file, "\n");
1747 *memtag = NULL_TREE;
1754 /* MEMREF cannot be analyzed. */
1755 if (dump_file && (dump_flags & TDF_DETAILS))
1757 fprintf (dump_file, "\ndata-ref of unsupported type ");
1758 print_generic_expr (dump_file, memref, TDF_SLIM);
1759 fprintf (dump_file, "\n");
1765 DR_REF (*dr) = comp_ref;
1767 if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag))
1768 *subvars = get_subvars_for_var (*memtag);
1770 /* Part 2: Combine the results of object and address analysis to calculate
1771 INITIAL_OFFSET, STEP and misalignment info. */
1772 *offset = size_binop (PLUS_EXPR, object_offset, address_offset);
1774 if ((!object_misalign && !object_aligned_to)
1775 || (!address_misalign && !address_aligned_to))
1777 *misalign = NULL_TREE;
1778 *aligned_to = NULL_TREE;
1782 if (object_misalign && address_misalign)
1783 *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
1785 *misalign = object_misalign ? object_misalign : address_misalign;
1786 if (object_aligned_to && address_aligned_to)
1787 *aligned_to = size_binop (MIN_EXPR, object_aligned_to,
1788 address_aligned_to);
1790 *aligned_to = object_aligned_to ?
1791 object_aligned_to : address_aligned_to;
1793 *step = size_binop (PLUS_EXPR, object_step, address_step);
1795 return base_address;
1798 /* Function analyze_offset.
1800 Extract INVARIANT and CONSTANT parts from OFFSET.
1804 analyze_offset (tree offset, tree *invariant, tree *constant)
1806 tree op0, op1, constant_0, constant_1, invariant_0, invariant_1;
1807 enum tree_code code = TREE_CODE (offset);
1809 *invariant = NULL_TREE;
1810 *constant = NULL_TREE;
1812 /* Not PLUS/MINUS expression - recursion stop condition. */
1813 if (code != PLUS_EXPR && code != MINUS_EXPR)
1815 if (TREE_CODE (offset) == INTEGER_CST)
1818 *invariant = offset;
1822 op0 = TREE_OPERAND (offset, 0);
1823 op1 = TREE_OPERAND (offset, 1);
1825 /* Recursive call with the operands. */
1826 analyze_offset (op0, &invariant_0, &constant_0);
1827 analyze_offset (op1, &invariant_1, &constant_1);
1829 /* Combine the results. */
1830 *constant = constant_0 ? constant_0 : constant_1;
1831 if (invariant_0 && invariant_1)
1833 fold_build2 (code, TREE_TYPE (invariant_0), invariant_0, invariant_1);
1835 *invariant = invariant_0 ? invariant_0 : invariant_1;
1838 /* Free the memory used by the data reference DR. */
1841 free_data_ref (data_reference_p dr)
1843 DR_FREE_ACCESS_FNS (dr);
1847 /* Function create_data_ref.
1849 Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS,
1850 DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO,
1851 DR_MEMTAG, and DR_POINTSTO_INFO fields.
1854 MEMREF - the memory reference that is being analyzed
1855 STMT - the statement that contains MEMREF
1856 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1859 DR (returned value) - data_reference struct for MEMREF
1862 static struct data_reference *
1863 create_data_ref (tree memref, tree stmt, bool is_read)
1865 struct data_reference *dr = NULL;
1866 tree base_address, offset, step, misalign, memtag;
1867 struct loop *loop = loop_containing_stmt (stmt);
1868 tree invariant = NULL_TREE, constant = NULL_TREE;
1869 tree type_size, init_cond;
1870 struct ptr_info_def *ptr_info;
1871 subvar_t subvars = NULL;
1872 tree aligned_to, type = NULL_TREE, orig_offset;
1877 base_address = object_analysis (memref, stmt, is_read, &dr, &offset,
1878 &misalign, &aligned_to, &step, &memtag,
1879 &ptr_info, &subvars);
1880 if (!dr || !base_address)
1882 if (dump_file && (dump_flags & TDF_DETAILS))
1884 fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for ");
1885 print_generic_expr (dump_file, memref, TDF_SLIM);
1886 fprintf (dump_file, "\n");
1891 DR_BASE_ADDRESS (dr) = base_address;
1892 DR_OFFSET (dr) = offset;
1893 DR_INIT (dr) = ssize_int (0);
1894 DR_STEP (dr) = step;
1895 DR_OFFSET_MISALIGNMENT (dr) = misalign;
1896 DR_ALIGNED_TO (dr) = aligned_to;
1897 DR_MEMTAG (dr) = memtag;
1898 DR_PTR_INFO (dr) = ptr_info;
1899 DR_SUBVARS (dr) = subvars;
1901 type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
1903 /* Extract CONSTANT and INVARIANT from OFFSET. */
1904 /* Remove cast from OFFSET and restore it for INVARIANT part. */
1905 orig_offset = offset;
1906 STRIP_NOPS (offset);
1907 if (offset != orig_offset)
1908 type = TREE_TYPE (orig_offset);
1909 analyze_offset (offset, &invariant, &constant);
1910 if (type && invariant)
1911 invariant = fold_convert (type, invariant);
1913 /* Put CONSTANT part of OFFSET in DR_INIT and INVARIANT in DR_OFFSET field
1917 DR_INIT (dr) = fold_convert (ssizetype, constant);
1918 init_cond = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (constant),
1919 constant, type_size);
1922 DR_INIT (dr) = init_cond = ssize_int (0);
1925 DR_OFFSET (dr) = invariant;
1927 DR_OFFSET (dr) = ssize_int (0);
1929 /* Change the access function for INIDIRECT_REFs, according to
1930 DR_BASE_ADDRESS. Analyze OFFSET calculated in object_analysis. OFFSET is
1931 an expression that can contain loop invariant expressions and constants.
1932 We put the constant part in the initial condition of the access function
1933 (for data dependence tests), and in DR_INIT of the data-ref. The loop
1934 invariant part is put in DR_OFFSET.
1935 The evolution part of the access function is STEP calculated in
1936 object_analysis divided by the size of data type.
1938 if (!DR_BASE_OBJECT (dr)
1939 || (TREE_CODE (memref) == COMPONENT_REF && DR_NUM_DIMENSIONS (dr) == 1))
1944 /* Update access function. */
1945 access_fn = DR_ACCESS_FN (dr, 0);
1946 if (automatically_generated_chrec_p (access_fn))
1952 new_step = size_binop (TRUNC_DIV_EXPR,
1953 fold_convert (ssizetype, step), type_size);
1955 init_cond = chrec_convert (chrec_type (access_fn), init_cond, stmt);
1956 new_step = chrec_convert (chrec_type (access_fn), new_step, stmt);
1957 if (automatically_generated_chrec_p (init_cond)
1958 || automatically_generated_chrec_p (new_step))
1963 access_fn = chrec_replace_initial_condition (access_fn, init_cond);
1964 access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step);
1966 VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn);
1969 if (dump_file && (dump_flags & TDF_DETAILS))
1971 struct ptr_info_def *pi = DR_PTR_INFO (dr);
1973 fprintf (dump_file, "\nCreated dr for ");
1974 print_generic_expr (dump_file, memref, TDF_SLIM);
1975 fprintf (dump_file, "\n\tbase_address: ");
1976 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
1977 fprintf (dump_file, "\n\toffset from base address: ");
1978 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
1979 fprintf (dump_file, "\n\tconstant offset from base address: ");
1980 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
1981 fprintf (dump_file, "\n\tbase_object: ");
1982 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
1983 fprintf (dump_file, "\n\tstep: ");
1984 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
1985 fprintf (dump_file, "B\n\tmisalignment from base: ");
1986 print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM);
1987 if (DR_OFFSET_MISALIGNMENT (dr))
1988 fprintf (dump_file, "B");
1989 if (DR_ALIGNED_TO (dr))
1991 fprintf (dump_file, "\n\taligned to: ");
1992 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
1994 fprintf (dump_file, "\n\tmemtag: ");
1995 print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM);
1996 fprintf (dump_file, "\n");
1997 if (pi && pi->name_mem_tag)
1999 fprintf (dump_file, "\n\tnametag: ");
2000 print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM);
2001 fprintf (dump_file, "\n");
2008 /* Returns true when all the functions of a tree_vec CHREC are the
2012 all_chrecs_equal_p (tree chrec)
2016 for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
2017 if (!eq_evolutions_p (TREE_VEC_ELT (chrec, j),
2018 TREE_VEC_ELT (chrec, j + 1)))
2024 /* Determine for each subscript in the data dependence relation DDR
2028 compute_subscript_distance (struct data_dependence_relation *ddr)
2030 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
2034 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2036 tree conflicts_a, conflicts_b, difference;
2037 struct subscript *subscript;
2039 subscript = DDR_SUBSCRIPT (ddr, i);
2040 conflicts_a = SUB_CONFLICTS_IN_A (subscript);
2041 conflicts_b = SUB_CONFLICTS_IN_B (subscript);
2043 if (TREE_CODE (conflicts_a) == TREE_VEC)
2045 if (!all_chrecs_equal_p (conflicts_a))
2047 SUB_DISTANCE (subscript) = chrec_dont_know;
2051 conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
2054 if (TREE_CODE (conflicts_b) == TREE_VEC)
2056 if (!all_chrecs_equal_p (conflicts_b))
2058 SUB_DISTANCE (subscript) = chrec_dont_know;
2062 conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
2065 conflicts_b = chrec_convert (integer_type_node, conflicts_b,
2067 conflicts_a = chrec_convert (integer_type_node, conflicts_a,
2069 difference = chrec_fold_minus
2070 (integer_type_node, conflicts_b, conflicts_a);
2072 if (evolution_function_is_constant_p (difference))
2073 SUB_DISTANCE (subscript) = difference;
2076 SUB_DISTANCE (subscript) = chrec_dont_know;
2081 /* Initialize a data dependence relation between data accesses A and
2082 B. NB_LOOPS is the number of loops surrounding the references: the
2083 size of the classic distance/direction vectors. */
2085 static struct data_dependence_relation *
2086 initialize_data_dependence_relation (struct data_reference *a,
2087 struct data_reference *b,
2088 VEC (loop_p, heap) *loop_nest)
2090 struct data_dependence_relation *res;
2091 bool differ_p, known_dependence;
2094 res = XNEW (struct data_dependence_relation);
2097 DDR_LOOP_NEST (res) = NULL;
2099 if (a == NULL || b == NULL)
2101 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
2105 /* When A and B are arrays and their dimensions differ, we directly
2106 initialize the relation to "there is no dependence": chrec_known. */
2107 if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
2108 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
2110 DDR_ARE_DEPENDENT (res) = chrec_known;
2114 if (DR_BASE_ADDRESS (a) && DR_BASE_ADDRESS (b))
2115 known_dependence = base_addr_differ_p (a, b, &differ_p);
2117 known_dependence = base_object_differ_p (a, b, &differ_p);
2119 if (!known_dependence)
2121 /* Can't determine whether the data-refs access the same memory
2123 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
2129 DDR_ARE_DEPENDENT (res) = chrec_known;
2133 DDR_AFFINE_P (res) = true;
2134 DDR_ARE_DEPENDENT (res) = NULL_TREE;
2135 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
2136 DDR_LOOP_NEST (res) = loop_nest;
2137 DDR_DIR_VECTS (res) = NULL;
2138 DDR_DIST_VECTS (res) = NULL;
2140 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
2142 struct subscript *subscript;
2144 subscript = XNEW (struct subscript);
2145 SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
2146 SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
2147 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
2148 SUB_DISTANCE (subscript) = chrec_dont_know;
2149 VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
2155 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
2159 finalize_ddr_dependent (struct data_dependence_relation *ddr,
2162 if (dump_file && (dump_flags & TDF_DETAILS))
2164 fprintf (dump_file, "(dependence classified: ");
2165 print_generic_expr (dump_file, chrec, 0);
2166 fprintf (dump_file, ")\n");
2169 DDR_ARE_DEPENDENT (ddr) = chrec;
2170 VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr));
2173 /* The dependence relation DDR cannot be represented by a distance
2177 non_affine_dependence_relation (struct data_dependence_relation *ddr)
2179 if (dump_file && (dump_flags & TDF_DETAILS))
2180 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
2182 DDR_AFFINE_P (ddr) = false;
2187 /* This section contains the classic Banerjee tests. */
2189 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
2190 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
2193 ziv_subscript_p (tree chrec_a,
2196 return (evolution_function_is_constant_p (chrec_a)
2197 && evolution_function_is_constant_p (chrec_b));
2200 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
2201 variable, i.e., if the SIV (Single Index Variable) test is true. */
2204 siv_subscript_p (tree chrec_a,
2207 if ((evolution_function_is_constant_p (chrec_a)
2208 && evolution_function_is_univariate_p (chrec_b))
2209 || (evolution_function_is_constant_p (chrec_b)
2210 && evolution_function_is_univariate_p (chrec_a)))
2213 if (evolution_function_is_univariate_p (chrec_a)
2214 && evolution_function_is_univariate_p (chrec_b))
2216 switch (TREE_CODE (chrec_a))
2218 case POLYNOMIAL_CHREC:
2219 switch (TREE_CODE (chrec_b))
2221 case POLYNOMIAL_CHREC:
2222 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
2237 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
2238 *OVERLAPS_B are initialized to the functions that describe the
2239 relation between the elements accessed twice by CHREC_A and
2240 CHREC_B. For k >= 0, the following property is verified:
2242 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2245 analyze_ziv_subscript (tree chrec_a,
2249 tree *last_conflicts)
2252 dependence_stats.num_ziv++;
2254 if (dump_file && (dump_flags & TDF_DETAILS))
2255 fprintf (dump_file, "(analyze_ziv_subscript \n");
2257 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
2258 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
2259 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2261 switch (TREE_CODE (difference))
2264 if (integer_zerop (difference))
2266 /* The difference is equal to zero: the accessed index
2267 overlaps for each iteration in the loop. */
2268 *overlaps_a = integer_zero_node;
2269 *overlaps_b = integer_zero_node;
2270 *last_conflicts = chrec_dont_know;
2271 dependence_stats.num_ziv_dependent++;
2275 /* The accesses do not overlap. */
2276 *overlaps_a = chrec_known;
2277 *overlaps_b = chrec_known;
2278 *last_conflicts = integer_zero_node;
2279 dependence_stats.num_ziv_independent++;
2284 /* We're not sure whether the indexes overlap. For the moment,
2285 conservatively answer "don't know". */
2286 if (dump_file && (dump_flags & TDF_DETAILS))
2287 fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
2289 *overlaps_a = chrec_dont_know;
2290 *overlaps_b = chrec_dont_know;
2291 *last_conflicts = chrec_dont_know;
2292 dependence_stats.num_ziv_unimplemented++;
2296 if (dump_file && (dump_flags & TDF_DETAILS))
2297 fprintf (dump_file, ")\n");
2300 /* Get the real or estimated number of iterations for LOOPNUM, whichever is
2301 available. Return the number of iterations as a tree, or NULL_TREE if
2305 get_number_of_iters_for_loop (int loopnum)
2307 struct loop *loop = get_loop (loopnum);
2308 tree numiter = number_of_exit_cond_executions (loop);
2310 if (TREE_CODE (numiter) == INTEGER_CST)
2313 if (loop->estimate_state == EST_AVAILABLE)
2315 tree type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
2316 if (double_int_fits_to_tree_p (type, loop->estimated_nb_iterations))
2317 return double_int_to_tree (type, loop->estimated_nb_iterations);
2323 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2324 constant, and CHREC_B is an affine function. *OVERLAPS_A and
2325 *OVERLAPS_B are initialized to the functions that describe the
2326 relation between the elements accessed twice by CHREC_A and
2327 CHREC_B. For k >= 0, the following property is verified:
2329 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2332 analyze_siv_subscript_cst_affine (tree chrec_a,
2336 tree *last_conflicts)
2338 bool value0, value1, value2;
2341 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
2342 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
2343 difference = chrec_fold_minus
2344 (integer_type_node, initial_condition (chrec_b), chrec_a);
2346 if (!chrec_is_positive (initial_condition (difference), &value0))
2348 if (dump_file && (dump_flags & TDF_DETAILS))
2349 fprintf (dump_file, "siv test failed: chrec is not positive.\n");
2351 dependence_stats.num_siv_unimplemented++;
2352 *overlaps_a = chrec_dont_know;
2353 *overlaps_b = chrec_dont_know;
2354 *last_conflicts = chrec_dont_know;
2359 if (value0 == false)
2361 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
2363 if (dump_file && (dump_flags & TDF_DETAILS))
2364 fprintf (dump_file, "siv test failed: chrec not positive.\n");
2366 *overlaps_a = chrec_dont_know;
2367 *overlaps_b = chrec_dont_know;
2368 *last_conflicts = chrec_dont_know;
2369 dependence_stats.num_siv_unimplemented++;
2378 chrec_b = {10, +, 1}
2381 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2384 int loopnum = CHREC_VARIABLE (chrec_b);
2386 *overlaps_a = integer_zero_node;
2387 *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
2388 fold_build1 (ABS_EXPR,
2391 CHREC_RIGHT (chrec_b));
2392 *last_conflicts = integer_one_node;
2395 /* Perform weak-zero siv test to see if overlap is
2396 outside the loop bounds. */
2397 numiter = get_number_of_iters_for_loop (loopnum);
2399 if (numiter != NULL_TREE
2400 && TREE_CODE (*overlaps_b) == INTEGER_CST
2401 && tree_int_cst_lt (numiter, *overlaps_b))
2403 *overlaps_a = chrec_known;
2404 *overlaps_b = chrec_known;
2405 *last_conflicts = integer_zero_node;
2406 dependence_stats.num_siv_independent++;
2409 dependence_stats.num_siv_dependent++;
2413 /* When the step does not divide the difference, there are
2417 *overlaps_a = chrec_known;
2418 *overlaps_b = chrec_known;
2419 *last_conflicts = integer_zero_node;
2420 dependence_stats.num_siv_independent++;
2429 chrec_b = {10, +, -1}
2431 In this case, chrec_a will not overlap with chrec_b. */
2432 *overlaps_a = chrec_known;
2433 *overlaps_b = chrec_known;
2434 *last_conflicts = integer_zero_node;
2435 dependence_stats.num_siv_independent++;
2442 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
2444 if (dump_file && (dump_flags & TDF_DETAILS))
2445 fprintf (dump_file, "siv test failed: chrec not positive.\n");
2447 *overlaps_a = chrec_dont_know;
2448 *overlaps_b = chrec_dont_know;
2449 *last_conflicts = chrec_dont_know;
2450 dependence_stats.num_siv_unimplemented++;
2455 if (value2 == false)
2459 chrec_b = {10, +, -1}
2461 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2464 int loopnum = CHREC_VARIABLE (chrec_b);
2466 *overlaps_a = integer_zero_node;
2467 *overlaps_b = fold_build2 (EXACT_DIV_EXPR,
2468 integer_type_node, difference,
2469 CHREC_RIGHT (chrec_b));
2470 *last_conflicts = integer_one_node;
2472 /* Perform weak-zero siv test to see if overlap is
2473 outside the loop bounds. */
2474 numiter = get_number_of_iters_for_loop (loopnum);
2476 if (numiter != NULL_TREE
2477 && TREE_CODE (*overlaps_b) == INTEGER_CST
2478 && tree_int_cst_lt (numiter, *overlaps_b))
2480 *overlaps_a = chrec_known;
2481 *overlaps_b = chrec_known;
2482 *last_conflicts = integer_zero_node;
2483 dependence_stats.num_siv_independent++;
2486 dependence_stats.num_siv_dependent++;
2490 /* When the step does not divide the difference, there
2494 *overlaps_a = chrec_known;
2495 *overlaps_b = chrec_known;
2496 *last_conflicts = integer_zero_node;
2497 dependence_stats.num_siv_independent++;
2507 In this case, chrec_a will not overlap with chrec_b. */
2508 *overlaps_a = chrec_known;
2509 *overlaps_b = chrec_known;
2510 *last_conflicts = integer_zero_node;
2511 dependence_stats.num_siv_independent++;
2519 /* Helper recursive function for initializing the matrix A. Returns
2520 the initial value of CHREC. */
2523 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2527 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2528 return int_cst_value (chrec);
2530 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2531 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2534 #define FLOOR_DIV(x,y) ((x) / (y))
2536 /* Solves the special case of the Diophantine equation:
2537 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2539 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2540 number of iterations that loops X and Y run. The overlaps will be
2541 constructed as evolutions in dimension DIM. */
2544 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
2545 tree *overlaps_a, tree *overlaps_b,
2546 tree *last_conflicts, int dim)
2548 if (((step_a > 0 && step_b > 0)
2549 || (step_a < 0 && step_b < 0)))
2551 int step_overlaps_a, step_overlaps_b;
2552 int gcd_steps_a_b, last_conflict, tau2;
2554 gcd_steps_a_b = gcd (step_a, step_b);
2555 step_overlaps_a = step_b / gcd_steps_a_b;
2556 step_overlaps_b = step_a / gcd_steps_a_b;
2558 tau2 = FLOOR_DIV (niter, step_overlaps_a);
2559 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2560 last_conflict = tau2;
2562 *overlaps_a = build_polynomial_chrec
2563 (dim, integer_zero_node,
2564 build_int_cst (NULL_TREE, step_overlaps_a));
2565 *overlaps_b = build_polynomial_chrec
2566 (dim, integer_zero_node,
2567 build_int_cst (NULL_TREE, step_overlaps_b));
2568 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2573 *overlaps_a = integer_zero_node;
2574 *overlaps_b = integer_zero_node;
2575 *last_conflicts = integer_zero_node;
2580 /* Solves the special case of a Diophantine equation where CHREC_A is
2581 an affine bivariate function, and CHREC_B is an affine univariate
2582 function. For example,
2584 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2586 has the following overlapping functions:
2588 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2589 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2590 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2592 FORNOW: This is a specialized implementation for a case occurring in
2593 a common benchmark. Implement the general algorithm. */
2596 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2597 tree *overlaps_a, tree *overlaps_b,
2598 tree *last_conflicts)
2600 bool xz_p, yz_p, xyz_p;
2601 int step_x, step_y, step_z;
2602 int niter_x, niter_y, niter_z, niter;
2603 tree numiter_x, numiter_y, numiter_z;
2604 tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
2605 tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
2606 tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
2608 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2609 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2610 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2612 numiter_x = get_number_of_iters_for_loop (CHREC_VARIABLE (CHREC_LEFT (chrec_a)));
2613 numiter_y = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
2614 numiter_z = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
2616 if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
2617 || numiter_z == NULL_TREE)
2619 if (dump_file && (dump_flags & TDF_DETAILS))
2620 fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
2622 *overlaps_a = chrec_dont_know;
2623 *overlaps_b = chrec_dont_know;
2624 *last_conflicts = chrec_dont_know;
2628 niter_x = int_cst_value (numiter_x);
2629 niter_y = int_cst_value (numiter_y);
2630 niter_z = int_cst_value (numiter_z);
2632 niter = MIN (niter_x, niter_z);
2633 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2636 &last_conflicts_xz, 1);
2637 niter = MIN (niter_y, niter_z);
2638 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2641 &last_conflicts_yz, 2);
2642 niter = MIN (niter_x, niter_z);
2643 niter = MIN (niter_y, niter);
2644 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2647 &last_conflicts_xyz, 3);
2649 xz_p = !integer_zerop (last_conflicts_xz);
2650 yz_p = !integer_zerop (last_conflicts_yz);
2651 xyz_p = !integer_zerop (last_conflicts_xyz);
2653 if (xz_p || yz_p || xyz_p)
2655 *overlaps_a = make_tree_vec (2);
2656 TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
2657 TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
2658 *overlaps_b = integer_zero_node;
2661 tree t0 = chrec_convert (integer_type_node,
2662 TREE_VEC_ELT (*overlaps_a, 0), NULL_TREE);
2663 tree t1 = chrec_convert (integer_type_node, overlaps_a_xz,
2665 tree t2 = chrec_convert (integer_type_node, *overlaps_b,
2667 tree t3 = chrec_convert (integer_type_node, overlaps_b_xz,
2670 TREE_VEC_ELT (*overlaps_a, 0) = chrec_fold_plus (integer_type_node,
2672 *overlaps_b = chrec_fold_plus (integer_type_node, t2, t3);
2673 *last_conflicts = last_conflicts_xz;
2677 tree t0 = chrec_convert (integer_type_node,
2678 TREE_VEC_ELT (*overlaps_a, 1), NULL_TREE);
2679 tree t1 = chrec_convert (integer_type_node, overlaps_a_yz, NULL_TREE);
2680 tree t2 = chrec_convert (integer_type_node, *overlaps_b, NULL_TREE);
2681 tree t3 = chrec_convert (integer_type_node, overlaps_b_yz, NULL_TREE);
2683 TREE_VEC_ELT (*overlaps_a, 1) = chrec_fold_plus (integer_type_node,
2685 *overlaps_b = chrec_fold_plus (integer_type_node, t2, t3);
2686 *last_conflicts = last_conflicts_yz;
2690 tree t0 = chrec_convert (integer_type_node,
2691 TREE_VEC_ELT (*overlaps_a, 0), NULL_TREE);
2692 tree t1 = chrec_convert (integer_type_node, overlaps_a_xyz,
2694 tree t2 = chrec_convert (integer_type_node,
2695 TREE_VEC_ELT (*overlaps_a, 1), NULL_TREE);
2696 tree t3 = chrec_convert (integer_type_node, overlaps_a_xyz,
2698 tree t4 = chrec_convert (integer_type_node, *overlaps_b, NULL_TREE);
2699 tree t5 = chrec_convert (integer_type_node, overlaps_b_xyz,
2702 TREE_VEC_ELT (*overlaps_a, 0) = chrec_fold_plus (integer_type_node,
2704 TREE_VEC_ELT (*overlaps_a, 1) = chrec_fold_plus (integer_type_node,
2706 *overlaps_b = chrec_fold_plus (integer_type_node, t4, t5);
2707 *last_conflicts = last_conflicts_xyz;
2712 *overlaps_a = integer_zero_node;
2713 *overlaps_b = integer_zero_node;
2714 *last_conflicts = integer_zero_node;
2718 /* Determines the overlapping elements due to accesses CHREC_A and
2719 CHREC_B, that are affine functions. This function cannot handle
2720 symbolic evolution functions, ie. when initial conditions are
2721 parameters, because it uses lambda matrices of integers. */
2724 analyze_subscript_affine_affine (tree chrec_a,
2728 tree *last_conflicts)
2730 unsigned nb_vars_a, nb_vars_b, dim;
2731 int init_a, init_b, gamma, gcd_alpha_beta;
2733 lambda_matrix A, U, S;
2735 if (eq_evolutions_p (chrec_a, chrec_b))
2737 /* The accessed index overlaps for each iteration in the
2739 *overlaps_a = integer_zero_node;
2740 *overlaps_b = integer_zero_node;
2741 *last_conflicts = chrec_dont_know;
2744 if (dump_file && (dump_flags & TDF_DETAILS))
2745 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2747 /* For determining the initial intersection, we have to solve a
2748 Diophantine equation. This is the most time consuming part.
2750 For answering to the question: "Is there a dependence?" we have
2751 to prove that there exists a solution to the Diophantine
2752 equation, and that the solution is in the iteration domain,
2753 i.e. the solution is positive or zero, and that the solution
2754 happens before the upper bound loop.nb_iterations. Otherwise
2755 there is no dependence. This function outputs a description of
2756 the iterations that hold the intersections. */
2758 nb_vars_a = nb_vars_in_chrec (chrec_a);
2759 nb_vars_b = nb_vars_in_chrec (chrec_b);
2761 dim = nb_vars_a + nb_vars_b;
2762 U = lambda_matrix_new (dim, dim);
2763 A = lambda_matrix_new (dim, 1);
2764 S = lambda_matrix_new (dim, 1);
2766 init_a = initialize_matrix_A (A, chrec_a, 0, 1);
2767 init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
2768 gamma = init_b - init_a;
2770 /* Don't do all the hard work of solving the Diophantine equation
2771 when we already know the solution: for example,
2774 | gamma = 3 - 3 = 0.
2775 Then the first overlap occurs during the first iterations:
2776 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2780 if (nb_vars_a == 1 && nb_vars_b == 1)
2783 int niter, niter_a, niter_b;
2784 tree numiter_a, numiter_b;
2786 numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
2787 numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
2788 if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
2790 if (dump_file && (dump_flags & TDF_DETAILS))
2791 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
2792 *overlaps_a = chrec_dont_know;
2793 *overlaps_b = chrec_dont_know;
2794 *last_conflicts = chrec_dont_know;
2795 goto end_analyze_subs_aa;
2798 niter_a = int_cst_value (numiter_a);
2799 niter_b = int_cst_value (numiter_b);
2800 niter = MIN (niter_a, niter_b);
2802 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2803 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2805 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2806 overlaps_a, overlaps_b,
2810 else if (nb_vars_a == 2 && nb_vars_b == 1)
2811 compute_overlap_steps_for_affine_1_2
2812 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2814 else if (nb_vars_a == 1 && nb_vars_b == 2)
2815 compute_overlap_steps_for_affine_1_2
2816 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2820 if (dump_file && (dump_flags & TDF_DETAILS))
2821 fprintf (dump_file, "affine-affine test failed: too many variables.\n");
2822 *overlaps_a = chrec_dont_know;
2823 *overlaps_b = chrec_dont_know;
2824 *last_conflicts = chrec_dont_know;
2826 goto end_analyze_subs_aa;
2830 lambda_matrix_right_hermite (A, dim, 1, S, U);
2835 lambda_matrix_row_negate (U, dim, 0);
2837 gcd_alpha_beta = S[0][0];
2839 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2840 but that is a quite strange case. Instead of ICEing, answer
2842 if (gcd_alpha_beta == 0)
2844 *overlaps_a = chrec_dont_know;
2845 *overlaps_b = chrec_dont_know;
2846 *last_conflicts = chrec_dont_know;
2847 goto end_analyze_subs_aa;
2850 /* The classic "gcd-test". */
2851 if (!int_divides_p (gcd_alpha_beta, gamma))
2853 /* The "gcd-test" has determined that there is no integer
2854 solution, i.e. there is no dependence. */
2855 *overlaps_a = chrec_known;
2856 *overlaps_b = chrec_known;
2857 *last_conflicts = integer_zero_node;
2860 /* Both access functions are univariate. This includes SIV and MIV cases. */
2861 else if (nb_vars_a == 1 && nb_vars_b == 1)
2863 /* Both functions should have the same evolution sign. */
2864 if (((A[0][0] > 0 && -A[1][0] > 0)
2865 || (A[0][0] < 0 && -A[1][0] < 0)))
2867 /* The solutions are given by:
2869 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2872 For a given integer t. Using the following variables,
2874 | i0 = u11 * gamma / gcd_alpha_beta
2875 | j0 = u12 * gamma / gcd_alpha_beta
2882 | y0 = j0 + j1 * t. */
2886 /* X0 and Y0 are the first iterations for which there is a
2887 dependence. X0, Y0 are two solutions of the Diophantine
2888 equation: chrec_a (X0) = chrec_b (Y0). */
2890 int niter, niter_a, niter_b;
2891 tree numiter_a, numiter_b;
2893 numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
2894 numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
2896 if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
2898 if (dump_file && (dump_flags & TDF_DETAILS))
2899 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
2900 *overlaps_a = chrec_dont_know;
2901 *overlaps_b = chrec_dont_know;
2902 *last_conflicts = chrec_dont_know;
2903 goto end_analyze_subs_aa;
2906 niter_a = int_cst_value (numiter_a);
2907 niter_b = int_cst_value (numiter_b);
2908 niter = MIN (niter_a, niter_b);
2910 i0 = U[0][0] * gamma / gcd_alpha_beta;
2911 j0 = U[0][1] * gamma / gcd_alpha_beta;
2915 if ((i1 == 0 && i0 < 0)
2916 || (j1 == 0 && j0 < 0))
2918 /* There is no solution.
2919 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2920 falls in here, but for the moment we don't look at the
2921 upper bound of the iteration domain. */
2922 *overlaps_a = chrec_known;
2923 *overlaps_b = chrec_known;
2924 *last_conflicts = integer_zero_node;
2931 tau1 = CEIL (-i0, i1);
2932 tau2 = FLOOR_DIV (niter - i0, i1);
2936 int last_conflict, min_multiple;
2937 tau1 = MAX (tau1, CEIL (-j0, j1));
2938 tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
2940 x0 = i1 * tau1 + i0;
2941 y0 = j1 * tau1 + j0;
2943 /* At this point (x0, y0) is one of the
2944 solutions to the Diophantine equation. The
2945 next step has to compute the smallest
2946 positive solution: the first conflicts. */
2947 min_multiple = MIN (x0 / i1, y0 / j1);
2948 x0 -= i1 * min_multiple;
2949 y0 -= j1 * min_multiple;
2951 tau1 = (x0 - i0)/i1;
2952 last_conflict = tau2 - tau1;
2954 /* If the overlap occurs outside of the bounds of the
2955 loop, there is no dependence. */
2956 if (x0 > niter || y0 > niter)
2958 *overlaps_a = chrec_known;
2959 *overlaps_b = chrec_known;
2960 *last_conflicts = integer_zero_node;
2964 *overlaps_a = build_polynomial_chrec
2966 build_int_cst (NULL_TREE, x0),
2967 build_int_cst (NULL_TREE, i1));
2968 *overlaps_b = build_polynomial_chrec
2970 build_int_cst (NULL_TREE, y0),
2971 build_int_cst (NULL_TREE, j1));
2972 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2977 /* FIXME: For the moment, the upper bound of the
2978 iteration domain for j is not checked. */
2979 if (dump_file && (dump_flags & TDF_DETAILS))
2980 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2981 *overlaps_a = chrec_dont_know;
2982 *overlaps_b = chrec_dont_know;
2983 *last_conflicts = chrec_dont_know;
2989 /* FIXME: For the moment, the upper bound of the
2990 iteration domain for i is not checked. */
2991 if (dump_file && (dump_flags & TDF_DETAILS))
2992 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2993 *overlaps_a = chrec_dont_know;
2994 *overlaps_b = chrec_dont_know;
2995 *last_conflicts = chrec_dont_know;
3001 if (dump_file && (dump_flags & TDF_DETAILS))
3002 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3003 *overlaps_a = chrec_dont_know;
3004 *overlaps_b = chrec_dont_know;
3005 *last_conflicts = chrec_dont_know;
3011 if (dump_file && (dump_flags & TDF_DETAILS))
3012 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3013 *overlaps_a = chrec_dont_know;
3014 *overlaps_b = chrec_dont_know;
3015 *last_conflicts = chrec_dont_know;
3018 end_analyze_subs_aa:
3019 if (dump_file && (dump_flags & TDF_DETAILS))
3021 fprintf (dump_file, " (overlaps_a = ");
3022 print_generic_expr (dump_file, *overlaps_a, 0);
3023 fprintf (dump_file, ")\n (overlaps_b = ");
3024 print_generic_expr (dump_file, *overlaps_b, 0);
3025 fprintf (dump_file, ")\n");
3026 fprintf (dump_file, ")\n");
3030 /* Returns true when analyze_subscript_affine_affine can be used for
3031 determining the dependence relation between chrec_a and chrec_b,
3032 that contain symbols. This function modifies chrec_a and chrec_b
3033 such that the analysis result is the same, and such that they don't
3034 contain symbols, and then can safely be passed to the analyzer.
3036 Example: The analysis of the following tuples of evolutions produce
3037 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
3040 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
3041 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
3045 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
3047 tree diff, type, left_a, left_b, right_b;
3049 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
3050 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
3051 /* FIXME: For the moment not handled. Might be refined later. */
3054 type = chrec_type (*chrec_a);
3055 left_a = CHREC_LEFT (*chrec_a);
3056 left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE);
3057 diff = chrec_fold_minus (type, left_a, left_b);
3059 if (!evolution_function_is_constant_p (diff))
3062 if (dump_file && (dump_flags & TDF_DETAILS))
3063 fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
3065 *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
3066 diff, CHREC_RIGHT (*chrec_a));
3067 right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE);
3068 *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
3069 build_int_cst (type, 0),
3074 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
3075 *OVERLAPS_B are initialized to the functions that describe the
3076 relation between the elements accessed twice by CHREC_A and
3077 CHREC_B. For k >= 0, the following property is verified:
3079 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
3082 analyze_siv_subscript (tree chrec_a,
3086 tree *last_conflicts)
3088 dependence_stats.num_siv++;
3090 if (dump_file && (dump_flags & TDF_DETAILS))
3091 fprintf (dump_file, "(analyze_siv_subscript \n");
3093 if (evolution_function_is_constant_p (chrec_a)
3094 && evolution_function_is_affine_p (chrec_b))
3095 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
3096 overlaps_a, overlaps_b, last_conflicts);
3098 else if (evolution_function_is_affine_p (chrec_a)
3099 && evolution_function_is_constant_p (chrec_b))
3100 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
3101 overlaps_b, overlaps_a, last_conflicts);
3103 else if (evolution_function_is_affine_p (chrec_a)
3104 && evolution_function_is_affine_p (chrec_b))
3106 if (!chrec_contains_symbols (chrec_a)
3107 && !chrec_contains_symbols (chrec_b))
3109 analyze_subscript_affine_affine (chrec_a, chrec_b,
3110 overlaps_a, overlaps_b,
3113 if (*overlaps_a == chrec_dont_know
3114 || *overlaps_b == chrec_dont_know)
3115 dependence_stats.num_siv_unimplemented++;
3116 else if (*overlaps_a == chrec_known
3117 || *overlaps_b == chrec_known)
3118 dependence_stats.num_siv_independent++;
3120 dependence_stats.num_siv_dependent++;
3122 else if (can_use_analyze_subscript_affine_affine (&chrec_a,
3125 analyze_subscript_affine_affine (chrec_a, chrec_b,
3126 overlaps_a, overlaps_b,
3128 /* FIXME: The number of iterations is a symbolic expression.
3129 Compute it properly. */
3130 *last_conflicts = chrec_dont_know;
3132 if (*overlaps_a == chrec_dont_know
3133 || *overlaps_b == chrec_dont_know)
3134 dependence_stats.num_siv_unimplemented++;
3135 else if (*overlaps_a == chrec_known
3136 || *overlaps_b == chrec_known)
3137 dependence_stats.num_siv_independent++;
3139 dependence_stats.num_siv_dependent++;
3142 goto siv_subscript_dontknow;
3147 siv_subscript_dontknow:;
3148 if (dump_file && (dump_flags & TDF_DETAILS))
3149 fprintf (dump_file, "siv test failed: unimplemented.\n");
3150 *overlaps_a = chrec_dont_know;
3151 *overlaps_b = chrec_dont_know;
3152 *last_conflicts = chrec_dont_know;
3153 dependence_stats.num_siv_unimplemented++;
3156 if (dump_file && (dump_flags & TDF_DETAILS))
3157 fprintf (dump_file, ")\n");
3160 /* Return true when the property can be computed. RES should contain
3161 true when calling the first time this function, then it is set to
3162 false when one of the evolution steps of an affine CHREC does not
3163 divide the constant CST. */
3166 chrec_steps_divide_constant_p (tree chrec,
3170 switch (TREE_CODE (chrec))
3172 case POLYNOMIAL_CHREC:
3173 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
3175 if (tree_fold_divides_p (CHREC_RIGHT (chrec), cst))
3176 /* Keep RES to true, and iterate on other dimensions. */
3177 return chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst, res);
3183 /* When the step is a parameter the result is undetermined. */
3187 /* On the initial condition, return true. */
3192 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
3193 *OVERLAPS_B are initialized to the functions that describe the
3194 relation between the elements accessed twice by CHREC_A and
3195 CHREC_B. For k >= 0, the following property is verified:
3197 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
3200 analyze_miv_subscript (tree chrec_a,
3204 tree *last_conflicts)
3206 /* FIXME: This is a MIV subscript, not yet handled.
3207 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
3210 In the SIV test we had to solve a Diophantine equation with two
3211 variables. In the MIV case we have to solve a Diophantine
3212 equation with 2*n variables (if the subscript uses n IVs).
3214 bool divide_p = true;
3216 dependence_stats.num_miv++;
3217 if (dump_file && (dump_flags & TDF_DETAILS))
3218 fprintf (dump_file, "(analyze_miv_subscript \n");
3220 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
3221 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
3222 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
3224 if (eq_evolutions_p (chrec_a, chrec_b))
3226 /* Access functions are the same: all the elements are accessed
3227 in the same order. */
3228 *overlaps_a = integer_zero_node;
3229 *overlaps_b = integer_zero_node;
3230 *last_conflicts = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
3231 dependence_stats.num_miv_dependent++;
3234 else if (evolution_function_is_constant_p (difference)
3235 /* For the moment, the following is verified:
3236 evolution_function_is_affine_multivariate_p (chrec_a) */
3237 && chrec_steps_divide_constant_p (chrec_a, difference, ÷_p)
3240 /* testsuite/.../ssa-chrec-33.c
3241 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
3243 The difference is 1, and the evolution steps are equal to 2,
3244 consequently there are no overlapping elements. */
3245 *overlaps_a = chrec_known;
3246 *overlaps_b = chrec_known;
3247 *last_conflicts = integer_zero_node;
3248 dependence_stats.num_miv_independent++;
3251 else if (evolution_function_is_affine_multivariate_p (chrec_a)
3252 && !chrec_contains_symbols (chrec_a)
3253 && evolution_function_is_affine_multivariate_p (chrec_b)
3254 && !chrec_contains_symbols (chrec_b))
3256 /* testsuite/.../ssa-chrec-35.c
3257 {0, +, 1}_2 vs. {0, +, 1}_3
3258 the overlapping elements are respectively located at iterations:
3259 {0, +, 1}_x and {0, +, 1}_x,
3260 in other words, we have the equality:
3261 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
3264 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
3265 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
3267 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
3268 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
3270 analyze_subscript_affine_affine (chrec_a, chrec_b,
3271 overlaps_a, overlaps_b, last_conflicts);
3273 if (*overlaps_a == chrec_dont_know
3274 || *overlaps_b == chrec_dont_know)
3275 dependence_stats.num_miv_unimplemented++;
3276 else if (*overlaps_a == chrec_known
3277 || *overlaps_b == chrec_known)
3278 dependence_stats.num_miv_independent++;
3280 dependence_stats.num_miv_dependent++;
3285 /* When the analysis is too difficult, answer "don't know". */
3286 if (dump_file && (dump_flags & TDF_DETAILS))
3287 fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
3289 *overlaps_a = chrec_dont_know;
3290 *overlaps_b = chrec_dont_know;
3291 *last_conflicts = chrec_dont_know;
3292 dependence_stats.num_miv_unimplemented++;
3295 if (dump_file && (dump_flags & TDF_DETAILS))
3296 fprintf (dump_file, ")\n");
3299 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
3300 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
3301 two functions that describe the iterations that contain conflicting
3304 Remark: For an integer k >= 0, the following equality is true:
3306 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
3310 analyze_overlapping_iterations (tree chrec_a,
3312 tree *overlap_iterations_a,
3313 tree *overlap_iterations_b,
3314 tree *last_conflicts)
3316 dependence_stats.num_subscript_tests++;
3318 if (dump_file && (dump_flags & TDF_DETAILS))
3320 fprintf (dump_file, "(analyze_overlapping_iterations \n");
3321 fprintf (dump_file, " (chrec_a = ");
3322 print_generic_expr (dump_file, chrec_a, 0);
3323 fprintf (dump_file, ")\n (chrec_b = ");
3324 print_generic_expr (dump_file, chrec_b, 0);
3325 fprintf (dump_file, ")\n");
3328 if (chrec_a == NULL_TREE
3329 || chrec_b == NULL_TREE
3330 || chrec_contains_undetermined (chrec_a)
3331 || chrec_contains_undetermined (chrec_b))
3333 dependence_stats.num_subscript_undetermined++;
3335 *overlap_iterations_a = chrec_dont_know;
3336 *overlap_iterations_b = chrec_dont_know;
3339 /* If they are the same chrec, and are affine, they overlap
3340 on every iteration. */
3341 else if (eq_evolutions_p (chrec_a, chrec_b)
3342 && evolution_function_is_affine_multivariate_p (chrec_a))
3344 dependence_stats.num_same_subscript_function++;
3345 *overlap_iterations_a = integer_zero_node;
3346 *overlap_iterations_b = integer_zero_node;
3347 *last_conflicts = chrec_dont_know;
3350 /* If they aren't the same, and aren't affine, we can't do anything
3352 else if ((chrec_contains_symbols (chrec_a)
3353 || chrec_contains_symbols (chrec_b))
3354 && (!evolution_function_is_affine_multivariate_p (chrec_a)
3355 || !evolution_function_is_affine_multivariate_p (chrec_b)))
3357 dependence_stats.num_subscript_undetermined++;
3358 *overlap_iterations_a = chrec_dont_know;
3359 *overlap_iterations_b = chrec_dont_know;
3362 else if (ziv_subscript_p (chrec_a, chrec_b))
3363 analyze_ziv_subscript (chrec_a, chrec_b,
3364 overlap_iterations_a, overlap_iterations_b,
3367 else if (siv_subscript_p (chrec_a, chrec_b))
3368 analyze_siv_subscript (chrec_a, chrec_b,
3369 overlap_iterations_a, overlap_iterations_b,
3373 analyze_miv_subscript (chrec_a, chrec_b,
3374 overlap_iterations_a, overlap_iterations_b,
3377 if (dump_file && (dump_flags & TDF_DETAILS))
3379 fprintf (dump_file, " (overlap_iterations_a = ");
3380 print_generic_expr (dump_file, *overlap_iterations_a, 0);
3381 fprintf (dump_file, ")\n (overlap_iterations_b = ");
3382 print_generic_expr (dump_file, *overlap_iterations_b, 0);
3383 fprintf (dump_file, ")\n");
3384 fprintf (dump_file, ")\n");
3388 /* Helper function for uniquely inserting distance vectors. */
3391 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
3396 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
3397 if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
3400 VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
3403 /* Helper function for uniquely inserting direction vectors. */
3406 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
3411 for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
3412 if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
3415 VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
3418 /* Add a distance of 1 on all the loops outer than INDEX. If we
3419 haven't yet determined a distance for this outer loop, push a new
3420 distance vector composed of the previous distance, and a distance
3421 of 1 for this outer loop. Example:
3429 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
3430 save (0, 1), then we have to save (1, 0). */
3433 add_outer_distances (struct data_dependence_relation *ddr,
3434 lambda_vector dist_v, int index)
3436 /* For each outer loop where init_v is not set, the accesses are
3437 in dependence of distance 1 in the loop. */
3438 while (--index >= 0)
3440 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3441 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3443 save_dist_v (ddr, save_v);
3447 /* Return false when fail to represent the data dependence as a
3448 distance vector. INIT_B is set to true when a component has been
3449 added to the distance vector DIST_V. INDEX_CARRY is then set to
3450 the index in DIST_V that carries the dependence. */
3453 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
3454 struct data_reference *ddr_a,
3455 struct data_reference *ddr_b,
3456 lambda_vector dist_v, bool *init_b,
3460 lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3462 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3464 tree access_fn_a, access_fn_b;
3465 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3467 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3469 non_affine_dependence_relation (ddr);
3473 access_fn_a = DR_ACCESS_FN (ddr_a, i);
3474 access_fn_b = DR_ACCESS_FN (ddr_b, i);
3476 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3477 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3480 int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
3481 DDR_LOOP_NEST (ddr));
3482 int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
3483 DDR_LOOP_NEST (ddr));
3485 /* The dependence is carried by the outermost loop. Example:
3492 In this case, the dependence is carried by loop_1. */
3493 index = index_a < index_b ? index_a : index_b;
3494 *index_carry = MIN (index, *index_carry);
3496 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3498 non_affine_dependence_relation (ddr);
3502 dist = int_cst_value (SUB_DISTANCE (subscript));
3504 /* This is the subscript coupling test. If we have already
3505 recorded a distance for this loop (a distance coming from
3506 another subscript), it should be the same. For example,
3507 in the following code, there is no dependence:
3514 if (init_v[index] != 0 && dist_v[index] != dist)
3516 finalize_ddr_dependent (ddr, chrec_known);
3520 dist_v[index] = dist;
3526 /* This can be for example an affine vs. constant dependence
3527 (T[i] vs. T[3]) that is not an affine dependence and is
3528 not representable as a distance vector. */
3529 non_affine_dependence_relation (ddr);
3537 /* Return true when the DDR contains two data references that have the
3538 same access functions. */
3541 same_access_functions (struct data_dependence_relation *ddr)
3545 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3546 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
3547 DR_ACCESS_FN (DDR_B (ddr), i)))
3553 /* Helper function for the case where DDR_A and DDR_B are the same
3554 multivariate access function. */
3557 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
3560 tree c_1 = CHREC_LEFT (c_2);
3561 tree c_0 = CHREC_LEFT (c_1);
3562 lambda_vector dist_v;
3564 /* Polynomials with more than 2 variables are not handled yet. */
3565 if (TREE_CODE (c_0) != INTEGER_CST)
3567 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
3571 x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
3572 x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
3574 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3575 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3576 dist_v[x_1] = int_cst_value (CHREC_RIGHT (c_2));
3577 dist_v[x_2] = -int_cst_value (CHREC_RIGHT (c_1));
3578 save_dist_v (ddr, dist_v);
3580 add_outer_distances (ddr, dist_v, x_1);
3583 /* Helper function for the case where DDR_A and DDR_B are the same
3584 access functions. */
3587 add_other_self_distances (struct data_dependence_relation *ddr)
3589 lambda_vector dist_v;
3591 int index_carry = DDR_NB_LOOPS (ddr);
3593 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3595 tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
3597 if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
3599 if (!evolution_function_is_univariate_p (access_fun))
3601 if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
3603 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
3607 add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0));
3611 index_carry = MIN (index_carry,
3612 index_in_loop_nest (CHREC_VARIABLE (access_fun),
3613 DDR_LOOP_NEST (ddr)));
3617 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3618 add_outer_distances (ddr, dist_v, index_carry);
3621 /* Compute the classic per loop distance vector. DDR is the data
3622 dependence relation to build a vector from. Return false when fail
3623 to represent the data dependence as a distance vector. */
3626 build_classic_dist_vector (struct data_dependence_relation *ddr)
3628 bool init_b = false;
3629 int index_carry = DDR_NB_LOOPS (ddr);
3630 lambda_vector dist_v;
3632 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3635 if (same_access_functions (ddr))
3637 /* Save the 0 vector. */
3638 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3639 save_dist_v (ddr, dist_v);
3641 if (DDR_NB_LOOPS (ddr) > 1)
3642 add_other_self_distances (ddr);
3647 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3648 if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
3649 dist_v, &init_b, &index_carry))
3652 /* Save the distance vector if we initialized one. */
3655 /* Verify a basic constraint: classic distance vectors should
3656 always be lexicographically positive.
3658 Data references are collected in the order of execution of
3659 the program, thus for the following loop
3661 | for (i = 1; i < 100; i++)
3662 | for (j = 1; j < 100; j++)
3664 | t = T[j+1][i-1]; // A
3665 | T[j][i] = t + 2; // B
3668 references are collected following the direction of the wind:
3669 A then B. The data dependence tests are performed also
3670 following this order, such that we're looking at the distance
3671 separating the elements accessed by A from the elements later
3672 accessed by B. But in this example, the distance returned by
3673 test_dep (A, B) is lexicographically negative (-1, 1), that
3674 means that the access A occurs later than B with respect to
3675 the outer loop, ie. we're actually looking upwind. In this
3676 case we solve test_dep (B, A) looking downwind to the
3677 lexicographically positive solution, that returns the
3678 distance vector (1, -1). */
3679 if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
3681 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3682 subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
3683 compute_subscript_distance (ddr);
3684 build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3685 save_v, &init_b, &index_carry);
3686 save_dist_v (ddr, save_v);
3688 /* In this case there is a dependence forward for all the
3691 | for (k = 1; k < 100; k++)
3692 | for (i = 1; i < 100; i++)
3693 | for (j = 1; j < 100; j++)
3695 | t = T[j+1][i-1]; // A
3696 | T[j][i] = t + 2; // B
3704 if (DDR_NB_LOOPS (ddr) > 1)
3706 add_outer_distances (ddr, save_v, index_carry);
3707 add_outer_distances (ddr, dist_v, index_carry);
3712 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3713 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3714 save_dist_v (ddr, save_v);
3716 if (DDR_NB_LOOPS (ddr) > 1)
3718 lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3720 subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
3721 compute_subscript_distance (ddr);
3722 build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3723 opposite_v, &init_b, &index_carry);
3725 add_outer_distances (ddr, dist_v, index_carry);
3726 add_outer_distances (ddr, opposite_v, index_carry);
3732 /* There is a distance of 1 on all the outer loops: Example:
3733 there is a dependence of distance 1 on loop_1 for the array A.
3739 add_outer_distances (ddr, dist_v,
3740 lambda_vector_first_nz (dist_v,
3741 DDR_NB_LOOPS (ddr), 0));
3744 if (dump_file && (dump_flags & TDF_DETAILS))
3748 fprintf (dump_file, "(build_classic_dist_vector\n");
3749 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3751 fprintf (dump_file, " dist_vector = (");
3752 print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
3753 DDR_NB_LOOPS (ddr));
3754 fprintf (dump_file, " )\n");
3756 fprintf (dump_file, ")\n");
3762 /* Return the direction for a given distance.
3763 FIXME: Computing dir this way is suboptimal, since dir can catch
3764 cases that dist is unable to represent. */
3766 static inline enum data_dependence_direction
3767 dir_from_dist (int dist)
3770 return dir_positive;
3772 return dir_negative;
3777 /* Compute the classic per loop direction vector. DDR is the data
3778 dependence relation to build a vector from. */
3781 build_classic_dir_vector (struct data_dependence_relation *ddr)
3784 lambda_vector dist_v;
3786 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
3788 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3790 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3791 dir_v[j] = dir_from_dist (dist_v[j]);
3793 save_dir_v (ddr, dir_v);
3797 /* Helper function. Returns true when there is a dependence between
3798 data references DRA and DRB. */
3801 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
3802 struct data_reference *dra,
3803 struct data_reference *drb)
3806 tree last_conflicts;
3807 struct subscript *subscript;
3809 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3812 tree overlaps_a, overlaps_b;
3814 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
3815 DR_ACCESS_FN (drb, i),
3816 &overlaps_a, &overlaps_b,
3819 if (chrec_contains_undetermined (overlaps_a)
3820 || chrec_contains_undetermined (overlaps_b))
3822 finalize_ddr_dependent (ddr, chrec_dont_know);
3823 dependence_stats.num_dependence_undetermined++;
3827 else if (overlaps_a == chrec_known
3828 || overlaps_b == chrec_known)
3830 finalize_ddr_dependent (ddr, chrec_known);
3831 dependence_stats.num_dependence_independent++;
3837 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3838 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3839 SUB_LAST_CONFLICT (subscript) = last_conflicts;
3846 /* Computes the conflicting iterations, and initialize DDR. */
3849 subscript_dependence_tester (struct data_dependence_relation *ddr)
3852 if (dump_file && (dump_flags & TDF_DETAILS))
3853 fprintf (dump_file, "(subscript_dependence_tester \n");
3855 if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr)))
3856 dependence_stats.num_dependence_dependent++;
3858 compute_subscript_distance (ddr);
3859 if (build_classic_dist_vector (ddr))
3860 build_classic_dir_vector (ddr);
3862 if (dump_file && (dump_flags & TDF_DETAILS))
3863 fprintf (dump_file, ")\n");
3866 /* Returns true when all the access functions of A are affine or
3870 access_functions_are_affine_or_constant_p (struct data_reference *a)
3873 VEC(tree,heap) **fns = DR_ACCESS_FNS_ADDR (a);
3876 for (i = 0; VEC_iterate (tree, *fns, i, t); i++)
3877 if (!evolution_function_is_constant_p (t)
3878 && !evolution_function_is_affine_multivariate_p (t))
3884 /* This computes the affine dependence relation between A and B.
3885 CHREC_KNOWN is used for representing the independence between two
3886 accesses, while CHREC_DONT_KNOW is used for representing the unknown
3889 Note that it is possible to stop the computation of the dependence
3890 relation the first time we detect a CHREC_KNOWN element for a given
3894 compute_affine_dependence (struct data_dependence_relation *ddr)
3896 struct data_reference *dra = DDR_A (ddr);
3897 struct data_reference *drb = DDR_B (ddr);
3899 if (dump_file && (dump_flags & TDF_DETAILS))
3901 fprintf (dump_file, "(compute_affine_dependence\n");
3902 fprintf (dump_file, " (stmt_a = \n");
3903 print_generic_expr (dump_file, DR_STMT (dra), 0);
3904 fprintf (dump_file, ")\n (stmt_b = \n");
3905 print_generic_expr (dump_file, DR_STMT (drb), 0);
3906 fprintf (dump_file, ")\n");
3909 /* Analyze only when the dependence relation is not yet known. */
3910 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3912 dependence_stats.num_dependence_tests++;
3914 if (access_functions_are_affine_or_constant_p (dra)
3915 && access_functions_are_affine_or_constant_p (drb))
3916 subscript_dependence_tester (ddr);
3918 /* As a last case, if the dependence cannot be determined, or if
3919 the dependence is considered too difficult to determine, answer
3923 dependence_stats.num_dependence_undetermined++;
3925 if (dump_file && (dump_flags & TDF_DETAILS))
3927 fprintf (dump_file, "Data ref a:\n");
3928 dump_data_reference (dump_file, dra);
3929 fprintf (dump_file, "Data ref b:\n");
3930 dump_data_reference (dump_file, drb);
3931 fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
3933 finalize_ddr_dependent (ddr, chrec_dont_know);
3937 if (dump_file && (dump_flags & TDF_DETAILS))
3938 fprintf (dump_file, ")\n");
3941 /* This computes the dependence relation for the same data
3942 reference into DDR. */
3945 compute_self_dependence (struct data_dependence_relation *ddr)
3948 struct subscript *subscript;
3950 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3953 /* The accessed index overlaps for each iteration. */
3954 SUB_CONFLICTS_IN_A (subscript) = integer_zero_node;
3955 SUB_CONFLICTS_IN_B (subscript) = integer_zero_node;
3956 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3959 /* The distance vector is the zero vector. */
3960 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3961 save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3964 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3965 the data references in DATAREFS, in the LOOP_NEST. When
3966 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3970 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
3971 VEC (ddr_p, heap) **dependence_relations,
3972 VEC (loop_p, heap) *loop_nest,
3973 bool compute_self_and_rr)
3975 struct data_dependence_relation *ddr;
3976 struct data_reference *a, *b;
3979 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
3980 for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
3981 if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
3983 ddr = initialize_data_dependence_relation (a, b, loop_nest);
3984 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3985 compute_affine_dependence (ddr);
3988 if (compute_self_and_rr)
3989 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
3991 ddr = initialize_data_dependence_relation (a, a, loop_nest);
3992 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3993 compute_self_dependence (ddr);
3997 /* Stores the locations of memory references in STMT to REFERENCES. Returns
3998 true if STMT clobbers memory, false otherwise. */
4001 get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references)
4003 bool clobbers_memory = false;
4005 tree *op0, *op1, args, call;
4009 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4010 Calls have side-effects, except those to const or pure
4012 call = get_call_expr_in (stmt);
4014 && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE)))
4015 || (TREE_CODE (stmt) == ASM_EXPR
4016 && ASM_VOLATILE_P (stmt)))
4017 clobbers_memory = true;
4019 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
4020 return clobbers_memory;
4022 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
4024 op0 = &GIMPLE_STMT_OPERAND (stmt, 0);
4025 op1 = &GIMPLE_STMT_OPERAND (stmt, 1);
4028 || REFERENCE_CLASS_P (*op1))
4030 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4032 ref->is_read = true;
4036 || REFERENCE_CLASS_P (*op0))
4038 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4040 ref->is_read = false;
4046 for (args = TREE_OPERAND (call, 1); args; args = TREE_CHAIN (args))
4048 op0 = &TREE_VALUE (args);
4050 || REFERENCE_CLASS_P (*op0))
4052 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4054 ref->is_read = true;
4059 return clobbers_memory;
4062 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4063 reference, returns false, otherwise returns true. */
4066 find_data_references_in_stmt (tree stmt,
4067 VEC (data_reference_p, heap) **datarefs)
4070 VEC (data_ref_loc, heap) *references;
4073 data_reference_p dr;
4075 if (get_references_in_stmt (stmt, &references))
4077 VEC_free (data_ref_loc, heap, references);
4081 for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
4083 dr = create_data_ref (*ref->pos, stmt, ref->is_read);
4085 VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4092 VEC_free (data_ref_loc, heap, references);
4096 /* Search the data references in LOOP, and record the information into
4097 DATAREFS. Returns chrec_dont_know when failing to analyze a
4098 difficult case, returns NULL_TREE otherwise.
4100 TODO: This function should be made smarter so that it can handle address
4101 arithmetic as if they were array accesses, etc. */
4104 find_data_references_in_loop (struct loop *loop,
4105 VEC (data_reference_p, heap) **datarefs)
4107 basic_block bb, *bbs;
4109 block_stmt_iterator bsi;
4111 bbs = get_loop_body (loop);
4113 for (i = 0; i < loop->num_nodes; i++)
4117 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4119 tree stmt = bsi_stmt (bsi);
4121 if (!find_data_references_in_stmt (stmt, datarefs))
4123 struct data_reference *res;
4124 res = XNEW (struct data_reference);
4125 DR_STMT (res) = NULL_TREE;
4126 DR_REF (res) = NULL_TREE;
4127 DR_BASE_OBJECT (res) = NULL;
4128 DR_TYPE (res) = ARRAY_REF_TYPE;
4129 DR_SET_ACCESS_FNS (res, NULL);
4130 DR_BASE_OBJECT (res) = NULL;
4131 DR_IS_READ (res) = false;
4132 DR_BASE_ADDRESS (res) = NULL_TREE;
4133 DR_OFFSET (res) = NULL_TREE;
4134 DR_INIT (res) = NULL_TREE;
4135 DR_STEP (res) = NULL_TREE;
4136 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
4137 DR_MEMTAG (res) = NULL_TREE;
4138 DR_PTR_INFO (res) = NULL;
4139 VEC_safe_push (data_reference_p, heap, *datarefs, res);
4142 return chrec_dont_know;
4151 /* Recursive helper function. */
4154 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4156 /* Inner loops of the nest should not contain siblings. Example:
4157 when there are two consecutive loops,
4168 the dependence relation cannot be captured by the distance
4173 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4175 return find_loop_nest_1 (loop->inner, loop_nest);
4179 /* Return false when the LOOP is not well nested. Otherwise return
4180 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4181 contain the loops from the outermost to the innermost, as they will
4182 appear in the classic distance vector. */
4185 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4187 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4189 return find_loop_nest_1 (loop->inner, loop_nest);
4193 /* Given a loop nest LOOP, the following vectors are returned:
4194 DATAREFS is initialized to all the array elements contained in this loop,
4195 DEPENDENCE_RELATIONS contains the relations between the data references.
4196 Compute read-read and self relations if
4197 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4200 compute_data_dependences_for_loop (struct loop *loop,
4201 bool compute_self_and_read_read_dependences,
4202 VEC (data_reference_p, heap) **datarefs,
4203 VEC (ddr_p, heap) **dependence_relations)
4205 struct loop *loop_nest = loop;
4206 VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
4208 memset (&dependence_stats, 0, sizeof (dependence_stats));
4210 /* If the loop nest is not well formed, or one of the data references
4211 is not computable, give up without spending time to compute other
4214 || !find_loop_nest (loop_nest, &vloops)
4215 || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
4217 struct data_dependence_relation *ddr;
4219 /* Insert a single relation into dependence_relations:
4221 ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
4222 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4225 compute_all_dependences (*datarefs, dependence_relations, vloops,
4226 compute_self_and_read_read_dependences);
4228 if (dump_file && (dump_flags & TDF_STATS))
4230 fprintf (dump_file, "Dependence tester statistics:\n");
4232 fprintf (dump_file, "Number of dependence tests: %d\n",
4233 dependence_stats.num_dependence_tests);
4234 fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4235 dependence_stats.num_dependence_dependent);
4236 fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4237 dependence_stats.num_dependence_independent);
4238 fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4239 dependence_stats.num_dependence_undetermined);
4241 fprintf (dump_file, "Number of subscript tests: %d\n",
4242 dependence_stats.num_subscript_tests);
4243 fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4244 dependence_stats.num_subscript_undetermined);
4245 fprintf (dump_file, "Number of same subscript function: %d\n",
4246 dependence_stats.num_same_subscript_function);
4248 fprintf (dump_file, "Number of ziv tests: %d\n",
4249 dependence_stats.num_ziv);
4250 fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4251 dependence_stats.num_ziv_dependent);
4252 fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4253 dependence_stats.num_ziv_independent);
4254 fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4255 dependence_stats.num_ziv_unimplemented);
4257 fprintf (dump_file, "Number of siv tests: %d\n",
4258 dependence_stats.num_siv);
4259 fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4260 dependence_stats.num_siv_dependent);
4261 fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4262 dependence_stats.num_siv_independent);
4263 fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4264 dependence_stats.num_siv_unimplemented);
4266 fprintf (dump_file, "Number of miv tests: %d\n",
4267 dependence_stats.num_miv);
4268 fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4269 dependence_stats.num_miv_dependent);
4270 fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4271 dependence_stats.num_miv_independent);
4272 fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4273 dependence_stats.num_miv_unimplemented);
4277 /* Entry point (for testing only). Analyze all the data references
4278 and the dependence relations.
4280 The data references are computed first.
4282 A relation on these nodes is represented by a complete graph. Some
4283 of the relations could be of no interest, thus the relations can be
4286 In the following function we compute all the relations. This is
4287 just a first implementation that is here for:
4288 - for showing how to ask for the dependence relations,
4289 - for the debugging the whole dependence graph,
4290 - for the dejagnu testcases and maintenance.
4292 It is possible to ask only for a part of the graph, avoiding to
4293 compute the whole dependence graph. The computed dependences are
4294 stored in a knowledge base (KB) such that later queries don't
4295 recompute the same information. The implementation of this KB is
4296 transparent to the optimizer, and thus the KB can be changed with a
4297 more efficient implementation, or the KB could be disabled. */
4300 analyze_all_data_dependences (struct loops *loops)
4303 int nb_data_refs = 10;
4304 VEC (data_reference_p, heap) *datarefs =
4305 VEC_alloc (data_reference_p, heap, nb_data_refs);
4306 VEC (ddr_p, heap) *dependence_relations =
4307 VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
4309 /* Compute DDs on the whole function. */
4310 compute_data_dependences_for_loop (loops->parray[0], false,
4311 &datarefs, &dependence_relations);
4315 dump_data_dependence_relations (dump_file, dependence_relations);
4316 fprintf (dump_file, "\n\n");
4318 if (dump_flags & TDF_DETAILS)
4319 dump_dist_dir_vectors (dump_file, dependence_relations);
4321 if (dump_flags & TDF_STATS)
4323 unsigned nb_top_relations = 0;
4324 unsigned nb_bot_relations = 0;
4325 unsigned nb_basename_differ = 0;
4326 unsigned nb_chrec_relations = 0;
4327 struct data_dependence_relation *ddr;
4329 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4331 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4334 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4336 struct data_reference *a = DDR_A (ddr);
4337 struct data_reference *b = DDR_B (ddr);
4340 if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
4341 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
4342 || (base_object_differ_p (a, b, &differ_p)
4344 nb_basename_differ++;
4350 nb_chrec_relations++;
4353 gather_stats_on_scev_database ();
4357 free_dependence_relations (dependence_relations);
4358 free_data_refs (datarefs);
4362 /* Free the memory used by a data dependence relation DDR. */
4365 free_dependence_relation (struct data_dependence_relation *ddr)
4370 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
4371 VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr));
4376 /* Free the memory used by the data dependence relations from
4377 DEPENDENCE_RELATIONS. */
4380 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
4383 struct data_dependence_relation *ddr;
4384 VEC (loop_p, heap) *loop_nest = NULL;
4386 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4390 if (loop_nest == NULL)
4391 loop_nest = DDR_LOOP_NEST (ddr);
4393 gcc_assert (DDR_LOOP_NEST (ddr) == NULL
4394 || DDR_LOOP_NEST (ddr) == loop_nest);
4395 free_dependence_relation (ddr);
4399 VEC_free (loop_p, heap, loop_nest);
4400 VEC_free (ddr_p, heap, dependence_relations);
4403 /* Free the memory used by the data references from DATAREFS. */
4406 free_data_refs (VEC (data_reference_p, heap) *datarefs)
4409 struct data_reference *dr;
4411 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
4413 VEC_free (data_reference_p, heap, datarefs);