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"
97 static struct datadep_stats
99 int num_dependence_tests
;
100 int num_dependence_dependent
;
101 int num_dependence_independent
;
102 int num_dependence_undetermined
;
104 int num_subscript_tests
;
105 int num_subscript_undetermined
;
106 int num_same_subscript_function
;
109 int num_ziv_independent
;
110 int num_ziv_dependent
;
111 int num_ziv_unimplemented
;
114 int num_siv_independent
;
115 int num_siv_dependent
;
116 int num_siv_unimplemented
;
119 int num_miv_independent
;
120 int num_miv_dependent
;
121 int num_miv_unimplemented
;
124 static tree
object_analysis (tree
, tree
, bool, struct data_reference
**,
125 tree
*, tree
*, tree
*, tree
*, tree
*,
126 struct ptr_info_def
**, subvar_t
*);
127 static struct data_reference
* init_data_ref (tree
, tree
, tree
, tree
, bool,
128 tree
, tree
, tree
, tree
, tree
,
129 struct ptr_info_def
*,
131 static bool subscript_dependence_tester_1 (struct data_dependence_relation
*,
132 struct data_reference
*,
133 struct data_reference
*);
135 /* Determine if PTR and DECL may alias, the result is put in ALIASED.
136 Return FALSE if there is no symbol memory tag for PTR. */
139 ptr_decl_may_alias_p (tree ptr
, tree decl
,
140 struct data_reference
*ptr_dr
,
145 gcc_assert (TREE_CODE (ptr
) == SSA_NAME
&& DECL_P (decl
));
147 tag
= get_var_ann (SSA_NAME_VAR (ptr
))->symbol_mem_tag
;
149 tag
= DR_MEMTAG (ptr_dr
);
153 *aliased
= is_aliased_with (tag
, decl
);
158 /* Determine if two pointers may alias, the result is put in ALIASED.
159 Return FALSE if there is no symbol memory tag for one of the pointers. */
162 ptr_ptr_may_alias_p (tree ptr_a
, tree ptr_b
,
163 struct data_reference
*dra
,
164 struct data_reference
*drb
,
169 tag_a
= get_var_ann (SSA_NAME_VAR (ptr_a
))->symbol_mem_tag
;
171 tag_a
= DR_MEMTAG (dra
);
174 tag_b
= get_var_ann (SSA_NAME_VAR (ptr_b
))->symbol_mem_tag
;
176 tag_b
= DR_MEMTAG (drb
);
179 *aliased
= (tag_a
== tag_b
);
184 /* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED.
185 Return FALSE if there is no symbol memory tag for one of the symbols. */
188 may_alias_p (tree base_a
, tree base_b
,
189 struct data_reference
*dra
,
190 struct data_reference
*drb
,
193 if (TREE_CODE (base_a
) == ADDR_EXPR
|| TREE_CODE (base_b
) == ADDR_EXPR
)
195 if (TREE_CODE (base_a
) == ADDR_EXPR
&& TREE_CODE (base_b
) == ADDR_EXPR
)
197 *aliased
= (TREE_OPERAND (base_a
, 0) == TREE_OPERAND (base_b
, 0));
200 if (TREE_CODE (base_a
) == ADDR_EXPR
)
201 return ptr_decl_may_alias_p (base_b
, TREE_OPERAND (base_a
, 0), drb
,
204 return ptr_decl_may_alias_p (base_a
, TREE_OPERAND (base_b
, 0), dra
,
208 return ptr_ptr_may_alias_p (base_a
, base_b
, dra
, drb
, aliased
);
212 /* Determine if a pointer (BASE_A) and a record/union access (BASE_B)
213 are not aliased. Return TRUE if they differ. */
215 record_ptr_differ_p (struct data_reference
*dra
,
216 struct data_reference
*drb
)
219 tree base_a
= DR_BASE_OBJECT (dra
);
220 tree base_b
= DR_BASE_OBJECT (drb
);
222 if (TREE_CODE (base_b
) != COMPONENT_REF
)
225 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
226 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
227 Probably will be unnecessary with struct alias analysis. */
228 while (TREE_CODE (base_b
) == COMPONENT_REF
)
229 base_b
= TREE_OPERAND (base_b
, 0);
230 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
232 if (TREE_CODE (base_a
) == INDIRECT_REF
233 && ((TREE_CODE (base_b
) == VAR_DECL
234 && (ptr_decl_may_alias_p (TREE_OPERAND (base_a
, 0), base_b
, dra
,
237 || (TREE_CODE (base_b
) == INDIRECT_REF
238 && (ptr_ptr_may_alias_p (TREE_OPERAND (base_a
, 0),
239 TREE_OPERAND (base_b
, 0), dra
, drb
,
248 /* Determine if an array access (BASE_A) and a record/union access (BASE_B)
249 are not aliased. Return TRUE if they differ. */
251 record_array_differ_p (struct data_reference
*dra
,
252 struct data_reference
*drb
)
255 tree base_a
= DR_BASE_OBJECT (dra
);
256 tree base_b
= DR_BASE_OBJECT (drb
);
258 if (TREE_CODE (base_b
) != COMPONENT_REF
)
261 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
262 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
263 Probably will be unnecessary with struct alias analysis. */
264 while (TREE_CODE (base_b
) == COMPONENT_REF
)
265 base_b
= TREE_OPERAND (base_b
, 0);
267 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
268 (a[i]). In case of p->c[i] use alias analysis to verify that p is not
270 if (TREE_CODE (base_a
) == VAR_DECL
271 && (TREE_CODE (base_b
) == VAR_DECL
272 || (TREE_CODE (base_b
) == INDIRECT_REF
273 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b
, 0), base_a
, drb
,
282 /* Determine if an array access (BASE_A) and a pointer (BASE_B)
283 are not aliased. Return TRUE if they differ. */
285 array_ptr_differ_p (tree base_a
, tree base_b
,
286 struct data_reference
*drb
)
290 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
291 help of alias analysis that p is not pointing to a. */
292 if (TREE_CODE (base_a
) == VAR_DECL
&& TREE_CODE (base_b
) == INDIRECT_REF
293 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b
, 0), base_a
, drb
, &aliased
)
301 /* This is the simplest data dependence test: determines whether the
302 data references A and B access the same array/region. Returns
303 false when the property is not computable at compile time.
304 Otherwise return true, and DIFFER_P will record the result. This
305 utility will not be necessary when alias_sets_conflict_p will be
306 less conservative. */
309 base_object_differ_p (struct data_reference
*a
,
310 struct data_reference
*b
,
313 tree base_a
= DR_BASE_OBJECT (a
);
314 tree base_b
= DR_BASE_OBJECT (b
);
317 if (!base_a
|| !base_b
)
320 /* Determine if same base. Example: for the array accesses
321 a[i], b[i] or pointer accesses *a, *b, bases are a, b. */
322 if (base_a
== base_b
)
328 /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
330 if (TREE_CODE (base_a
) == INDIRECT_REF
&& TREE_CODE (base_b
) == INDIRECT_REF
331 && TREE_OPERAND (base_a
, 0) == TREE_OPERAND (base_b
, 0))
337 /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */
338 if (TREE_CODE (base_a
) == COMPONENT_REF
&& TREE_CODE (base_b
) == COMPONENT_REF
339 && TREE_OPERAND (base_a
, 0) == TREE_OPERAND (base_b
, 0)
340 && TREE_OPERAND (base_a
, 1) == TREE_OPERAND (base_b
, 1))
347 /* Determine if different bases. */
349 /* At this point we know that base_a != base_b. However, pointer
350 accesses of the form x=(*p) and y=(*q), whose bases are p and q,
351 may still be pointing to the same base. In SSAed GIMPLE p and q will
352 be SSA_NAMES in this case. Therefore, here we check if they are
353 really two different declarations. */
354 if (TREE_CODE (base_a
) == VAR_DECL
&& TREE_CODE (base_b
) == VAR_DECL
)
360 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
361 help of alias analysis that p is not pointing to a. */
362 if (array_ptr_differ_p (base_a
, base_b
, b
)
363 || array_ptr_differ_p (base_b
, base_a
, a
))
369 /* If the bases are pointers ((*q)[i] and (*p)[i]), we check with the
370 help of alias analysis they don't point to the same bases. */
371 if (TREE_CODE (base_a
) == INDIRECT_REF
&& TREE_CODE (base_b
) == INDIRECT_REF
372 && (may_alias_p (TREE_OPERAND (base_a
, 0), TREE_OPERAND (base_b
, 0), a
, b
,
380 /* Compare two record/union bases s.a and t.b: s != t or (a != b and
381 s and t are not unions). */
382 if (TREE_CODE (base_a
) == COMPONENT_REF
&& TREE_CODE (base_b
) == COMPONENT_REF
383 && ((TREE_CODE (TREE_OPERAND (base_a
, 0)) == VAR_DECL
384 && TREE_CODE (TREE_OPERAND (base_b
, 0)) == VAR_DECL
385 && TREE_OPERAND (base_a
, 0) != TREE_OPERAND (base_b
, 0))
386 || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a
, 0))) == RECORD_TYPE
387 && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b
, 0))) == RECORD_TYPE
388 && TREE_OPERAND (base_a
, 1) != TREE_OPERAND (base_b
, 1))))
394 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
396 if (record_ptr_differ_p (a
, b
) || record_ptr_differ_p (b
, a
))
402 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
403 (a[i]). In case of p->c[i] use alias analysis to verify that p is not
405 if (record_array_differ_p (a
, b
) || record_array_differ_p (b
, a
))
414 /* Function base_addr_differ_p.
416 This is the simplest data dependence test: determines whether the
417 data references DRA and DRB access the same array/region. Returns
418 false when the property is not computable at compile time.
419 Otherwise return true, and DIFFER_P will record the result.
422 1. if (both DRA and DRB are represented as arrays)
423 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT
424 2. else if (both DRA and DRB are represented as pointers)
425 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION
426 3. else if (DRA and DRB are represented differently or 2. fails)
427 only try to prove that the bases are surely different
431 base_addr_differ_p (struct data_reference
*dra
,
432 struct data_reference
*drb
,
435 tree addr_a
= DR_BASE_ADDRESS (dra
);
436 tree addr_b
= DR_BASE_ADDRESS (drb
);
440 if (!addr_a
|| !addr_b
)
443 type_a
= TREE_TYPE (addr_a
);
444 type_b
= TREE_TYPE (addr_b
);
446 gcc_assert (POINTER_TYPE_P (type_a
) && POINTER_TYPE_P (type_b
));
448 /* 1. if (both DRA and DRB are represented as arrays)
449 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT. */
450 if (DR_TYPE (dra
) == ARRAY_REF_TYPE
&& DR_TYPE (drb
) == ARRAY_REF_TYPE
)
451 return base_object_differ_p (dra
, drb
, differ_p
);
453 /* 2. else if (both DRA and DRB are represented as pointers)
454 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION. */
455 /* If base addresses are the same, we check the offsets, since the access of
456 the data-ref is described by {base addr + offset} and its access function,
457 i.e., in order to decide whether the bases of data-refs are the same we
458 compare both base addresses and offsets. */
459 if (DR_TYPE (dra
) == POINTER_REF_TYPE
&& DR_TYPE (drb
) == POINTER_REF_TYPE
461 || (TREE_CODE (addr_a
) == ADDR_EXPR
&& TREE_CODE (addr_b
) == ADDR_EXPR
462 && TREE_OPERAND (addr_a
, 0) == TREE_OPERAND (addr_b
, 0))))
464 /* Compare offsets. */
465 tree offset_a
= DR_OFFSET (dra
);
466 tree offset_b
= DR_OFFSET (drb
);
468 STRIP_NOPS (offset_a
);
469 STRIP_NOPS (offset_b
);
471 /* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle
473 if (offset_a
== offset_b
474 || (TREE_CODE (offset_a
) == MULT_EXPR
475 && TREE_CODE (offset_b
) == MULT_EXPR
476 && TREE_OPERAND (offset_a
, 0) == TREE_OPERAND (offset_b
, 0)
477 && TREE_OPERAND (offset_a
, 1) == TREE_OPERAND (offset_b
, 1)))
484 /* 3. else if (DRA and DRB are represented differently or 2. fails)
485 only try to prove that the bases are surely different. */
487 /* Apply alias analysis. */
488 if (may_alias_p (addr_a
, addr_b
, dra
, drb
, &aliased
) && !aliased
)
494 /* An instruction writing through a restricted pointer is "independent" of any
495 instruction reading or writing through a different pointer, in the same
497 else if ((TYPE_RESTRICT (type_a
) && !DR_IS_READ (dra
))
498 || (TYPE_RESTRICT (type_b
) && !DR_IS_READ (drb
)))
506 /* Returns true iff A divides B. */
509 tree_fold_divides_p (tree a
,
512 /* Determines whether (A == gcd (A, B)). */
513 return tree_int_cst_equal (a
, tree_fold_gcd (a
, b
));
516 /* Returns true iff A divides B. */
519 int_divides_p (int a
, int b
)
521 return ((b
% a
) == 0);
526 /* Dump into FILE all the data references from DATAREFS. */
529 dump_data_references (FILE *file
, VEC (data_reference_p
, heap
) *datarefs
)
532 struct data_reference
*dr
;
534 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
535 dump_data_reference (file
, dr
);
538 /* Dump into FILE all the dependence relations from DDRS. */
541 dump_data_dependence_relations (FILE *file
,
542 VEC (ddr_p
, heap
) *ddrs
)
545 struct data_dependence_relation
*ddr
;
547 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
548 dump_data_dependence_relation (file
, ddr
);
551 /* Dump function for a DATA_REFERENCE structure. */
554 dump_data_reference (FILE *outf
,
555 struct data_reference
*dr
)
559 fprintf (outf
, "(Data Ref: \n stmt: ");
560 print_generic_stmt (outf
, DR_STMT (dr
), 0);
561 fprintf (outf
, " ref: ");
562 print_generic_stmt (outf
, DR_REF (dr
), 0);
563 fprintf (outf
, " base_object: ");
564 print_generic_stmt (outf
, DR_BASE_OBJECT (dr
), 0);
566 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
568 fprintf (outf
, " Access function %d: ", i
);
569 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
571 fprintf (outf
, ")\n");
574 /* Dump function for a SUBSCRIPT structure. */
577 dump_subscript (FILE *outf
, struct subscript
*subscript
)
579 tree chrec
= SUB_CONFLICTS_IN_A (subscript
);
581 fprintf (outf
, "\n (subscript \n");
582 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
583 print_generic_stmt (outf
, chrec
, 0);
584 if (chrec
== chrec_known
)
585 fprintf (outf
, " (no dependence)\n");
586 else if (chrec_contains_undetermined (chrec
))
587 fprintf (outf
, " (don't know)\n");
590 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
591 fprintf (outf
, " last_conflict: ");
592 print_generic_stmt (outf
, last_iteration
, 0);
595 chrec
= SUB_CONFLICTS_IN_B (subscript
);
596 fprintf (outf
, " iterations_that_access_an_element_twice_in_B: ");
597 print_generic_stmt (outf
, chrec
, 0);
598 if (chrec
== chrec_known
)
599 fprintf (outf
, " (no dependence)\n");
600 else if (chrec_contains_undetermined (chrec
))
601 fprintf (outf
, " (don't know)\n");
604 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
605 fprintf (outf
, " last_conflict: ");
606 print_generic_stmt (outf
, last_iteration
, 0);
609 fprintf (outf
, " (Subscript distance: ");
610 print_generic_stmt (outf
, SUB_DISTANCE (subscript
), 0);
611 fprintf (outf
, " )\n");
612 fprintf (outf
, " )\n");
615 /* Print the classic direction vector DIRV to OUTF. */
618 print_direction_vector (FILE *outf
,
624 for (eq
= 0; eq
< length
; eq
++)
626 enum data_dependence_direction dir
= dirv
[eq
];
631 fprintf (outf
, " +");
634 fprintf (outf
, " -");
637 fprintf (outf
, " =");
639 case dir_positive_or_equal
:
640 fprintf (outf
, " +=");
642 case dir_positive_or_negative
:
643 fprintf (outf
, " +-");
645 case dir_negative_or_equal
:
646 fprintf (outf
, " -=");
649 fprintf (outf
, " *");
652 fprintf (outf
, "indep");
656 fprintf (outf
, "\n");
659 /* Print a vector of direction vectors. */
662 print_dir_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dir_vects
,
668 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, v
); j
++)
669 print_direction_vector (outf
, v
, length
);
672 /* Print a vector of distance vectors. */
675 print_dist_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dist_vects
,
681 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, v
); j
++)
682 print_lambda_vector (outf
, v
, length
);
688 debug_data_dependence_relation (struct data_dependence_relation
*ddr
)
690 dump_data_dependence_relation (stderr
, ddr
);
693 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
696 dump_data_dependence_relation (FILE *outf
,
697 struct data_dependence_relation
*ddr
)
699 struct data_reference
*dra
, *drb
;
703 fprintf (outf
, "(Data Dep: \n");
704 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
705 fprintf (outf
, " (don't know)\n");
707 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
708 fprintf (outf
, " (no dependence)\n");
710 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
715 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
717 fprintf (outf
, " access_fn_A: ");
718 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
719 fprintf (outf
, " access_fn_B: ");
720 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
721 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
724 fprintf (outf
, " loop nest: (");
725 for (i
= 0; VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
726 fprintf (outf
, "%d ", loopi
->num
);
727 fprintf (outf
, ")\n");
729 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
731 fprintf (outf
, " distance_vector: ");
732 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
, i
),
736 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
738 fprintf (outf
, " direction_vector: ");
739 print_direction_vector (outf
, DDR_DIR_VECT (ddr
, i
),
744 fprintf (outf
, ")\n");
747 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
750 dump_data_dependence_direction (FILE *file
,
751 enum data_dependence_direction dir
)
767 case dir_positive_or_negative
:
768 fprintf (file
, "+-");
771 case dir_positive_or_equal
:
772 fprintf (file
, "+=");
775 case dir_negative_or_equal
:
776 fprintf (file
, "-=");
788 /* Dumps the distance and direction vectors in FILE. DDRS contains
789 the dependence relations, and VECT_SIZE is the size of the
790 dependence vectors, or in other words the number of loops in the
794 dump_dist_dir_vectors (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
797 struct data_dependence_relation
*ddr
;
800 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
801 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
803 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), j
, v
); j
++)
805 fprintf (file
, "DISTANCE_V (");
806 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
807 fprintf (file
, ")\n");
810 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), j
, v
); j
++)
812 fprintf (file
, "DIRECTION_V (");
813 print_direction_vector (file
, v
, DDR_NB_LOOPS (ddr
));
814 fprintf (file
, ")\n");
818 fprintf (file
, "\n\n");
821 /* Dumps the data dependence relations DDRS in FILE. */
824 dump_ddrs (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
827 struct data_dependence_relation
*ddr
;
829 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
830 dump_data_dependence_relation (file
, ddr
);
832 fprintf (file
, "\n\n");
837 /* Estimate the number of iterations from the size of the data and the
841 estimate_niter_from_size_of_data (struct loop
*loop
,
846 tree estimation
= NULL_TREE
;
847 tree array_size
, data_size
, element_size
;
850 init
= initial_condition (access_fn
);
851 step
= evolution_part_in_loop_num (access_fn
, loop
->num
);
853 array_size
= TYPE_SIZE (TREE_TYPE (opnd0
));
854 element_size
= TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0
)));
855 if (array_size
== NULL_TREE
856 || TREE_CODE (array_size
) != INTEGER_CST
857 || TREE_CODE (element_size
) != INTEGER_CST
)
860 data_size
= fold_build2 (EXACT_DIV_EXPR
, integer_type_node
,
861 array_size
, element_size
);
863 if (init
!= NULL_TREE
865 && TREE_CODE (init
) == INTEGER_CST
866 && TREE_CODE (step
) == INTEGER_CST
)
868 tree i_plus_s
= fold_build2 (PLUS_EXPR
, integer_type_node
, init
, step
);
869 tree sign
= fold_binary (GT_EXPR
, boolean_type_node
, i_plus_s
, init
);
871 if (sign
== boolean_true_node
)
872 estimation
= fold_build2 (CEIL_DIV_EXPR
, integer_type_node
,
873 fold_build2 (MINUS_EXPR
, integer_type_node
,
874 data_size
, init
), step
);
876 /* When the step is negative, as in PR23386: (init = 3, step =
877 0ffffffff, data_size = 100), we have to compute the
878 estimation as ceil_div (init, 0 - step) + 1. */
879 else if (sign
== boolean_false_node
)
881 fold_build2 (PLUS_EXPR
, integer_type_node
,
882 fold_build2 (CEIL_DIV_EXPR
, integer_type_node
,
884 fold_build2 (MINUS_EXPR
, unsigned_type_node
,
885 integer_zero_node
, step
)),
889 record_estimate (loop
, estimation
, boolean_true_node
, stmt
);
893 /* Given an ARRAY_REF node REF, records its access functions.
894 Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
895 i.e. the constant "3", then recursively call the function on opnd0,
896 i.e. the ARRAY_REF "A[i]".
897 If ESTIMATE_ONLY is true, we just set the estimated number of loop
898 iterations, we don't store the access function.
899 The function returns the base name: "A". */
902 analyze_array_indexes (struct loop
*loop
,
903 VEC(tree
,heap
) **access_fns
,
910 opnd0
= TREE_OPERAND (ref
, 0);
911 opnd1
= TREE_OPERAND (ref
, 1);
913 /* The detection of the evolution function for this data access is
914 postponed until the dependence test. This lazy strategy avoids
915 the computation of access functions that are of no interest for
917 access_fn
= instantiate_parameters
918 (loop
, analyze_scalar_evolution (loop
, opnd1
));
921 && chrec_contains_undetermined (loop
->estimated_nb_iterations
))
922 estimate_niter_from_size_of_data (loop
, opnd0
, access_fn
, stmt
);
925 VEC_safe_push (tree
, heap
, *access_fns
, access_fn
);
927 /* Recursively record other array access functions. */
928 if (TREE_CODE (opnd0
) == ARRAY_REF
)
929 return analyze_array_indexes (loop
, access_fns
, opnd0
, stmt
, estimate_only
);
931 /* Return the base name of the data access. */
936 /* For an array reference REF contained in STMT, attempt to bound the
937 number of iterations in the loop containing STMT */
940 estimate_iters_using_array (tree stmt
, tree ref
)
942 analyze_array_indexes (loop_containing_stmt (stmt
), NULL
, ref
, stmt
,
946 /* For a data reference REF contained in the statement STMT, initialize
947 a DATA_REFERENCE structure, and return it. IS_READ flag has to be
948 set to true when REF is in the right hand side of an
951 struct data_reference
*
952 analyze_array (tree stmt
, tree ref
, bool is_read
)
954 struct data_reference
*res
;
955 VEC(tree
,heap
) *acc_fns
;
957 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
959 fprintf (dump_file
, "(analyze_array \n");
960 fprintf (dump_file
, " (ref = ");
961 print_generic_stmt (dump_file
, ref
, 0);
962 fprintf (dump_file
, ")\n");
965 res
= XNEW (struct data_reference
);
967 DR_STMT (res
) = stmt
;
969 acc_fns
= VEC_alloc (tree
, heap
, 3);
970 DR_BASE_OBJECT (res
) = analyze_array_indexes
971 (loop_containing_stmt (stmt
), &acc_fns
, ref
, stmt
, false);
972 DR_TYPE (res
) = ARRAY_REF_TYPE
;
973 DR_SET_ACCESS_FNS (res
, acc_fns
);
974 DR_IS_READ (res
) = is_read
;
975 DR_BASE_ADDRESS (res
) = NULL_TREE
;
976 DR_OFFSET (res
) = NULL_TREE
;
977 DR_INIT (res
) = NULL_TREE
;
978 DR_STEP (res
) = NULL_TREE
;
979 DR_OFFSET_MISALIGNMENT (res
) = NULL_TREE
;
980 DR_MEMTAG (res
) = NULL_TREE
;
981 DR_PTR_INFO (res
) = NULL
;
983 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
984 fprintf (dump_file
, ")\n");
989 /* Analyze an indirect memory reference, REF, that comes from STMT.
990 IS_READ is true if this is an indirect load, and false if it is
992 Return a new data reference structure representing the indirect_ref, or
993 NULL if we cannot describe the access function. */
995 static struct data_reference
*
996 analyze_indirect_ref (tree stmt
, tree ref
, bool is_read
)
998 struct loop
*loop
= loop_containing_stmt (stmt
);
999 tree ptr_ref
= TREE_OPERAND (ref
, 0);
1000 tree access_fn
= analyze_scalar_evolution (loop
, ptr_ref
);
1001 tree init
= initial_condition_in_loop_num (access_fn
, loop
->num
);
1002 tree base_address
= NULL_TREE
, evolution
, step
= NULL_TREE
;
1003 struct ptr_info_def
*ptr_info
= NULL
;
1005 if (TREE_CODE (ptr_ref
) == SSA_NAME
)
1006 ptr_info
= SSA_NAME_PTR_INFO (ptr_ref
);
1009 if (access_fn
== chrec_dont_know
|| !init
|| init
== chrec_dont_know
)
1011 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1013 fprintf (dump_file
, "\nBad access function of ptr: ");
1014 print_generic_expr (dump_file
, ref
, TDF_SLIM
);
1015 fprintf (dump_file
, "\n");
1020 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1022 fprintf (dump_file
, "\nAccess function of ptr: ");
1023 print_generic_expr (dump_file
, access_fn
, TDF_SLIM
);
1024 fprintf (dump_file
, "\n");
1027 if (!expr_invariant_in_loop_p (loop
, init
))
1029 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1030 fprintf (dump_file
, "\ninitial condition is not loop invariant.\n");
1034 base_address
= init
;
1035 evolution
= evolution_part_in_loop_num (access_fn
, loop
->num
);
1036 if (evolution
!= chrec_dont_know
)
1039 step
= ssize_int (0);
1042 if (TREE_CODE (evolution
) == INTEGER_CST
)
1043 step
= fold_convert (ssizetype
, evolution
);
1045 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1046 fprintf (dump_file
, "\nnon constant step for ptr access.\n");
1050 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1051 fprintf (dump_file
, "\nunknown evolution of ptr.\n");
1053 return init_data_ref (stmt
, ref
, NULL_TREE
, access_fn
, is_read
, base_address
,
1054 NULL_TREE
, step
, NULL_TREE
, NULL_TREE
,
1055 ptr_info
, POINTER_REF_TYPE
);
1058 /* For a data reference REF contained in the statement STMT, initialize
1059 a DATA_REFERENCE structure, and return it. */
1061 struct data_reference
*
1062 init_data_ref (tree stmt
,
1072 struct ptr_info_def
*ptr_info
,
1073 enum data_ref_type type
)
1075 struct data_reference
*res
;
1076 VEC(tree
,heap
) *acc_fns
;
1078 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1080 fprintf (dump_file
, "(init_data_ref \n");
1081 fprintf (dump_file
, " (ref = ");
1082 print_generic_stmt (dump_file
, ref
, 0);
1083 fprintf (dump_file
, ")\n");
1086 res
= XNEW (struct data_reference
);
1088 DR_STMT (res
) = stmt
;
1090 DR_BASE_OBJECT (res
) = base
;
1091 DR_TYPE (res
) = type
;
1092 acc_fns
= VEC_alloc (tree
, heap
, 3);
1093 DR_SET_ACCESS_FNS (res
, acc_fns
);
1094 VEC_quick_push (tree
, DR_ACCESS_FNS (res
), access_fn
);
1095 DR_IS_READ (res
) = is_read
;
1096 DR_BASE_ADDRESS (res
) = base_address
;
1097 DR_OFFSET (res
) = init_offset
;
1098 DR_INIT (res
) = NULL_TREE
;
1099 DR_STEP (res
) = step
;
1100 DR_OFFSET_MISALIGNMENT (res
) = misalign
;
1101 DR_MEMTAG (res
) = memtag
;
1102 DR_PTR_INFO (res
) = ptr_info
;
1104 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1105 fprintf (dump_file
, ")\n");
1110 /* Function strip_conversions
1112 Strip conversions that don't narrow the mode. */
1115 strip_conversion (tree expr
)
1117 tree to
, ti
, oprnd0
;
1119 while (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
)
1121 to
= TREE_TYPE (expr
);
1122 oprnd0
= TREE_OPERAND (expr
, 0);
1123 ti
= TREE_TYPE (oprnd0
);
1125 if (!INTEGRAL_TYPE_P (to
) || !INTEGRAL_TYPE_P (ti
))
1127 if (GET_MODE_SIZE (TYPE_MODE (to
)) < GET_MODE_SIZE (TYPE_MODE (ti
)))
1136 /* Function analyze_offset_expr
1138 Given an offset expression EXPR received from get_inner_reference, analyze
1139 it and create an expression for INITIAL_OFFSET by substituting the variables
1140 of EXPR with initial_condition of the corresponding access_fn in the loop.
1143 for (j = 3; j < N; j++)
1146 For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be
1147 substituted, since its access_fn in the inner loop is i. 'j' will be
1148 substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
1151 Compute MISALIGN (the misalignment of the data reference initial access from
1152 its base). Misalignment can be calculated only if all the variables can be
1153 substituted with constants, otherwise, we record maximum possible alignment
1154 in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN
1155 will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be
1156 recorded in ALIGNED_TO.
1158 STEP is an evolution of the data reference in this loop in bytes.
1159 In the above example, STEP is C_j.
1161 Return FALSE, if the analysis fails, e.g., there is no access_fn for a
1162 variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO
1163 and STEP) are NULL_TREEs. Otherwise, return TRUE.
1168 analyze_offset_expr (tree expr
,
1170 tree
*initial_offset
,
1177 tree left_offset
= ssize_int (0);
1178 tree right_offset
= ssize_int (0);
1179 tree left_misalign
= ssize_int (0);
1180 tree right_misalign
= ssize_int (0);
1181 tree left_step
= ssize_int (0);
1182 tree right_step
= ssize_int (0);
1183 enum tree_code code
;
1184 tree init
, evolution
;
1185 tree left_aligned_to
= NULL_TREE
, right_aligned_to
= NULL_TREE
;
1188 *misalign
= NULL_TREE
;
1189 *aligned_to
= NULL_TREE
;
1190 *initial_offset
= NULL_TREE
;
1192 /* Strip conversions that don't narrow the mode. */
1193 expr
= strip_conversion (expr
);
1199 if (TREE_CODE (expr
) == INTEGER_CST
)
1201 *initial_offset
= fold_convert (ssizetype
, expr
);
1202 *misalign
= fold_convert (ssizetype
, expr
);
1203 *step
= ssize_int (0);
1207 /* 2. Variable. Try to substitute with initial_condition of the corresponding
1208 access_fn in the current loop. */
1209 if (SSA_VAR_P (expr
))
1211 tree access_fn
= analyze_scalar_evolution (loop
, expr
);
1213 if (access_fn
== chrec_dont_know
)
1217 init
= initial_condition_in_loop_num (access_fn
, loop
->num
);
1218 if (!expr_invariant_in_loop_p (loop
, init
))
1219 /* Not enough information: may be not loop invariant.
1220 E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
1221 initial_condition is D, but it depends on i - loop's induction
1225 evolution
= evolution_part_in_loop_num (access_fn
, loop
->num
);
1226 if (evolution
&& TREE_CODE (evolution
) != INTEGER_CST
)
1227 /* Evolution is not constant. */
1230 if (TREE_CODE (init
) == INTEGER_CST
)
1231 *misalign
= fold_convert (ssizetype
, init
);
1233 /* Not constant, misalignment cannot be calculated. */
1234 *misalign
= NULL_TREE
;
1236 *initial_offset
= fold_convert (ssizetype
, init
);
1238 *step
= evolution
? fold_convert (ssizetype
, evolution
) : ssize_int (0);
1242 /* Recursive computation. */
1243 if (!BINARY_CLASS_P (expr
))
1245 /* We expect to get binary expressions (PLUS/MINUS and MULT). */
1246 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1248 fprintf (dump_file
, "\nNot binary expression ");
1249 print_generic_expr (dump_file
, expr
, TDF_SLIM
);
1250 fprintf (dump_file
, "\n");
1254 oprnd0
= TREE_OPERAND (expr
, 0);
1255 oprnd1
= TREE_OPERAND (expr
, 1);
1257 if (!analyze_offset_expr (oprnd0
, loop
, &left_offset
, &left_misalign
,
1258 &left_aligned_to
, &left_step
)
1259 || !analyze_offset_expr (oprnd1
, loop
, &right_offset
, &right_misalign
,
1260 &right_aligned_to
, &right_step
))
1263 /* The type of the operation: plus, minus or mult. */
1264 code
= TREE_CODE (expr
);
1268 if (TREE_CODE (right_offset
) != INTEGER_CST
)
1269 /* RIGHT_OFFSET can be not constant. For example, for arrays of variable
1271 FORNOW: We don't support such cases. */
1274 /* Strip conversions that don't narrow the mode. */
1275 left_offset
= strip_conversion (left_offset
);
1278 /* Misalignment computation. */
1279 if (SSA_VAR_P (left_offset
))
1281 /* If the left side contains variables that can't be substituted with
1282 constants, the misalignment is unknown. However, if the right side
1283 is a multiple of some alignment, we know that the expression is
1284 aligned to it. Therefore, we record such maximum possible value.
1286 *misalign
= NULL_TREE
;
1287 *aligned_to
= ssize_int (highest_pow2_factor (right_offset
));
1291 /* The left operand was successfully substituted with constant. */
1294 /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is
1296 *misalign
= size_binop (code
, left_misalign
, right_misalign
);
1297 if (left_aligned_to
&& right_aligned_to
)
1298 *aligned_to
= size_binop (MIN_EXPR
, left_aligned_to
,
1301 *aligned_to
= left_aligned_to
?
1302 left_aligned_to
: right_aligned_to
;
1305 *misalign
= NULL_TREE
;
1308 /* Step calculation. */
1309 /* Multiply the step by the right operand. */
1310 *step
= size_binop (MULT_EXPR
, left_step
, right_offset
);
1315 /* Combine the recursive calculations for step and misalignment. */
1316 *step
= size_binop (code
, left_step
, right_step
);
1318 /* Unknown alignment. */
1319 if ((!left_misalign
&& !left_aligned_to
)
1320 || (!right_misalign
&& !right_aligned_to
))
1322 *misalign
= NULL_TREE
;
1323 *aligned_to
= NULL_TREE
;
1327 if (left_misalign
&& right_misalign
)
1328 *misalign
= size_binop (code
, left_misalign
, right_misalign
);
1330 *misalign
= left_misalign
? left_misalign
: right_misalign
;
1332 if (left_aligned_to
&& right_aligned_to
)
1333 *aligned_to
= size_binop (MIN_EXPR
, left_aligned_to
, right_aligned_to
);
1335 *aligned_to
= left_aligned_to
? left_aligned_to
: right_aligned_to
;
1343 /* Compute offset. */
1344 *initial_offset
= fold_convert (ssizetype
,
1345 fold_build2 (code
, TREE_TYPE (left_offset
),
1351 /* Function address_analysis
1353 Return the BASE of the address expression EXPR.
1354 Also compute the OFFSET from BASE, MISALIGN and STEP.
1357 EXPR - the address expression that is being analyzed
1358 STMT - the statement that contains EXPR or its original memory reference
1359 IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
1360 DR - data_reference struct for the original memory reference
1363 BASE (returned value) - the base of the data reference EXPR.
1364 INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
1365 MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
1366 computation is impossible
1367 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1368 calculated (doesn't depend on variables)
1369 STEP - evolution of EXPR in the loop
1371 If something unexpected is encountered (an unsupported form of data-ref),
1372 then NULL_TREE is returned.
1376 address_analysis (tree expr
, tree stmt
, bool is_read
, struct data_reference
*dr
,
1377 tree
*offset
, tree
*misalign
, tree
*aligned_to
, tree
*step
)
1379 tree oprnd0
, oprnd1
, base_address
, offset_expr
, base_addr0
, base_addr1
;
1380 tree address_offset
= ssize_int (0), address_misalign
= ssize_int (0);
1381 tree dummy
, address_aligned_to
= NULL_TREE
;
1382 struct ptr_info_def
*dummy1
;
1385 switch (TREE_CODE (expr
))
1389 /* EXPR is of form {base +/- offset} (or {offset +/- base}). */
1390 oprnd0
= TREE_OPERAND (expr
, 0);
1391 oprnd1
= TREE_OPERAND (expr
, 1);
1393 STRIP_NOPS (oprnd0
);
1394 STRIP_NOPS (oprnd1
);
1396 /* Recursively try to find the base of the address contained in EXPR.
1397 For offset, the returned base will be NULL. */
1398 base_addr0
= address_analysis (oprnd0
, stmt
, is_read
, dr
, &address_offset
,
1399 &address_misalign
, &address_aligned_to
,
1402 base_addr1
= address_analysis (oprnd1
, stmt
, is_read
, dr
, &address_offset
,
1403 &address_misalign
, &address_aligned_to
,
1406 /* We support cases where only one of the operands contains an
1408 if ((base_addr0
&& base_addr1
) || (!base_addr0
&& !base_addr1
))
1410 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1413 "\neither more than one address or no addresses in expr ");
1414 print_generic_expr (dump_file
, expr
, TDF_SLIM
);
1415 fprintf (dump_file
, "\n");
1420 /* To revert STRIP_NOPS. */
1421 oprnd0
= TREE_OPERAND (expr
, 0);
1422 oprnd1
= TREE_OPERAND (expr
, 1);
1424 offset_expr
= base_addr0
?
1425 fold_convert (ssizetype
, oprnd1
) : fold_convert (ssizetype
, oprnd0
);
1427 /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is
1428 a number, we can add it to the misalignment value calculated for base,
1429 otherwise, misalignment is NULL. */
1430 if (TREE_CODE (offset_expr
) == INTEGER_CST
&& address_misalign
)
1432 *misalign
= size_binop (TREE_CODE (expr
), address_misalign
,
1434 *aligned_to
= address_aligned_to
;
1438 *misalign
= NULL_TREE
;
1439 *aligned_to
= NULL_TREE
;
1442 /* Combine offset (from EXPR {base + offset}) with the offset calculated
1444 *offset
= size_binop (TREE_CODE (expr
), address_offset
, offset_expr
);
1445 return base_addr0
? base_addr0
: base_addr1
;
1448 base_address
= object_analysis (TREE_OPERAND (expr
, 0), stmt
, is_read
,
1449 &dr
, offset
, misalign
, aligned_to
, step
,
1450 &dummy
, &dummy1
, &dummy2
);
1451 return base_address
;
1454 if (!POINTER_TYPE_P (TREE_TYPE (expr
)))
1456 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1458 fprintf (dump_file
, "\nnot pointer SSA_NAME ");
1459 print_generic_expr (dump_file
, expr
, TDF_SLIM
);
1460 fprintf (dump_file
, "\n");
1464 *aligned_to
= ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr
))));
1465 *misalign
= ssize_int (0);
1466 *offset
= ssize_int (0);
1467 *step
= ssize_int (0);
1476 /* Function object_analysis
1478 Create a data-reference structure DR for MEMREF.
1479 Return the BASE of the data reference MEMREF if the analysis is possible.
1480 Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1481 E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset
1482 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET
1483 instantiated with initial_conditions of access_functions of variables,
1484 and STEP is the evolution of the DR_REF in this loop.
1486 Function get_inner_reference is used for the above in case of ARRAY_REF and
1489 The structure of the function is as follows:
1491 Case 1. For handled_component_p refs
1492 1.1 build data-reference structure for MEMREF
1493 1.2 call get_inner_reference
1494 1.2.1 analyze offset expr received from get_inner_reference
1495 (fall through with BASE)
1496 Case 2. For declarations
1498 Case 3. For INDIRECT_REFs
1499 3.1 build data-reference structure for MEMREF
1500 3.2 analyze evolution and initial condition of MEMREF
1501 3.3 set data-reference structure for MEMREF
1502 3.4 call address_analysis to analyze INIT of the access function
1503 3.5 extract memory tag
1506 Combine the results of object and address analysis to calculate
1507 INITIAL_OFFSET, STEP and misalignment info.
1510 MEMREF - the memory reference that is being analyzed
1511 STMT - the statement that contains MEMREF
1512 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1515 BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
1516 E.g, if MEMREF is a.b[k].c[i][j] the returned
1518 DR - data_reference struct for MEMREF
1519 INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
1520 MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of
1521 ALIGNMENT or NULL_TREE if the computation is impossible
1522 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1523 calculated (doesn't depend on variables)
1524 STEP - evolution of the DR_REF in the loop
1525 MEMTAG - memory tag for aliasing purposes
1526 PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
1527 SUBVARS - Sub-variables of the variable
1529 If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned,
1530 but DR can be created anyway.
1535 object_analysis (tree memref
, tree stmt
, bool is_read
,
1536 struct data_reference
**dr
, tree
*offset
, tree
*misalign
,
1537 tree
*aligned_to
, tree
*step
, tree
*memtag
,
1538 struct ptr_info_def
**ptr_info
, subvar_t
*subvars
)
1540 tree base
= NULL_TREE
, base_address
= NULL_TREE
;
1541 tree object_offset
= ssize_int (0), object_misalign
= ssize_int (0);
1542 tree object_step
= ssize_int (0), address_step
= ssize_int (0);
1543 tree address_offset
= ssize_int (0), address_misalign
= ssize_int (0);
1544 HOST_WIDE_INT pbitsize
, pbitpos
;
1545 tree poffset
, bit_pos_in_bytes
;
1546 enum machine_mode pmode
;
1547 int punsignedp
, pvolatilep
;
1548 tree ptr_step
= ssize_int (0), ptr_init
= NULL_TREE
;
1549 struct loop
*loop
= loop_containing_stmt (stmt
);
1550 struct data_reference
*ptr_dr
= NULL
;
1551 tree object_aligned_to
= NULL_TREE
, address_aligned_to
= NULL_TREE
;
1552 tree comp_ref
= NULL_TREE
;
1557 /* Case 1. handled_component_p refs. */
1558 if (handled_component_p (memref
))
1560 /* 1.1 build data-reference structure for MEMREF. */
1563 if (TREE_CODE (memref
) == ARRAY_REF
)
1564 *dr
= analyze_array (stmt
, memref
, is_read
);
1565 else if (TREE_CODE (memref
) == COMPONENT_REF
)
1569 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1571 fprintf (dump_file
, "\ndata-ref of unsupported type ");
1572 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1573 fprintf (dump_file
, "\n");
1579 /* 1.2 call get_inner_reference. */
1580 /* Find the base and the offset from it. */
1581 base
= get_inner_reference (memref
, &pbitsize
, &pbitpos
, &poffset
,
1582 &pmode
, &punsignedp
, &pvolatilep
, false);
1585 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1587 fprintf (dump_file
, "\nfailed to get inner ref for ");
1588 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1589 fprintf (dump_file
, "\n");
1594 /* 1.2.1 analyze offset expr received from get_inner_reference. */
1596 && !analyze_offset_expr (poffset
, loop
, &object_offset
,
1597 &object_misalign
, &object_aligned_to
,
1600 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1602 fprintf (dump_file
, "\nfailed to compute offset or step for ");
1603 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1604 fprintf (dump_file
, "\n");
1609 /* Add bit position to OFFSET and MISALIGN. */
1611 bit_pos_in_bytes
= ssize_int (pbitpos
/BITS_PER_UNIT
);
1612 /* Check that there is no remainder in bits. */
1613 if (pbitpos
%BITS_PER_UNIT
)
1615 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1616 fprintf (dump_file
, "\nbit offset alignment.\n");
1619 object_offset
= size_binop (PLUS_EXPR
, bit_pos_in_bytes
, object_offset
);
1620 if (object_misalign
)
1621 object_misalign
= size_binop (PLUS_EXPR
, object_misalign
,
1624 memref
= base
; /* To continue analysis of BASE. */
1628 /* Part 1: Case 2. Declarations. */
1629 if (DECL_P (memref
))
1631 /* We expect to get a decl only if we already have a DR, or with
1632 COMPONENT_REFs of type 'a[i].b'. */
1635 if (comp_ref
&& TREE_CODE (TREE_OPERAND (comp_ref
, 0)) == ARRAY_REF
)
1637 *dr
= analyze_array (stmt
, TREE_OPERAND (comp_ref
, 0), is_read
);
1638 if (DR_NUM_DIMENSIONS (*dr
) != 1)
1640 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1642 fprintf (dump_file
, "\n multidimensional component ref ");
1643 print_generic_expr (dump_file
, comp_ref
, TDF_SLIM
);
1644 fprintf (dump_file
, "\n");
1651 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1653 fprintf (dump_file
, "\nunhandled decl ");
1654 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1655 fprintf (dump_file
, "\n");
1661 /* TODO: if during the analysis of INDIRECT_REF we get to an object, put
1662 the object in BASE_OBJECT field if we can prove that this is O.K.,
1663 i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT.
1664 (e.g., if the object is an array base 'a', where 'a[N]', we must prove
1665 that every access with 'p' (the original INDIRECT_REF based on '&a')
1666 in the loop is within the array boundaries - from a[0] to a[N-1]).
1667 Otherwise, our alias analysis can be incorrect.
1668 Even if an access function based on BASE_OBJECT can't be build, update
1669 BASE_OBJECT field to enable us to prove that two data-refs are
1670 different (without access function, distance analysis is impossible).
1672 if (SSA_VAR_P (memref
) && var_can_have_subvars (memref
))
1673 *subvars
= get_subvars_for_var (memref
);
1674 base_address
= build_fold_addr_expr (memref
);
1675 /* 2.1 set MEMTAG. */
1679 /* Part 1: Case 3. INDIRECT_REFs. */
1680 else if (TREE_CODE (memref
) == INDIRECT_REF
)
1682 tree ptr_ref
= TREE_OPERAND (memref
, 0);
1683 if (TREE_CODE (ptr_ref
) == SSA_NAME
)
1684 *ptr_info
= SSA_NAME_PTR_INFO (ptr_ref
);
1686 /* 3.1 build data-reference structure for MEMREF. */
1687 ptr_dr
= analyze_indirect_ref (stmt
, memref
, is_read
);
1690 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1692 fprintf (dump_file
, "\nfailed to create dr for ");
1693 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1694 fprintf (dump_file
, "\n");
1699 /* 3.2 analyze evolution and initial condition of MEMREF. */
1700 ptr_step
= DR_STEP (ptr_dr
);
1701 ptr_init
= DR_BASE_ADDRESS (ptr_dr
);
1702 if (!ptr_init
|| !ptr_step
|| !POINTER_TYPE_P (TREE_TYPE (ptr_init
)))
1704 *dr
= (*dr
) ? *dr
: ptr_dr
;
1705 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1707 fprintf (dump_file
, "\nbad pointer access ");
1708 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1709 fprintf (dump_file
, "\n");
1714 if (integer_zerop (ptr_step
) && !(*dr
))
1716 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1717 fprintf (dump_file
, "\nptr is loop invariant.\n");
1721 /* If there exists DR for MEMREF, we are analyzing the base of
1722 handled component (PTR_INIT), which not necessary has evolution in
1725 object_step
= size_binop (PLUS_EXPR
, object_step
, ptr_step
);
1727 /* 3.3 set data-reference structure for MEMREF. */
1731 /* 3.4 call address_analysis to analyze INIT of the access
1733 base_address
= address_analysis (ptr_init
, stmt
, is_read
, *dr
,
1734 &address_offset
, &address_misalign
,
1735 &address_aligned_to
, &address_step
);
1738 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1740 fprintf (dump_file
, "\nfailed to analyze address ");
1741 print_generic_expr (dump_file
, ptr_init
, TDF_SLIM
);
1742 fprintf (dump_file
, "\n");
1747 /* 3.5 extract memory tag. */
1748 switch (TREE_CODE (base_address
))
1751 *memtag
= get_var_ann (SSA_NAME_VAR (base_address
))->symbol_mem_tag
;
1752 if (!(*memtag
) && TREE_CODE (TREE_OPERAND (memref
, 0)) == SSA_NAME
)
1753 *memtag
= get_var_ann (
1754 SSA_NAME_VAR (TREE_OPERAND (memref
, 0)))->symbol_mem_tag
;
1757 *memtag
= TREE_OPERAND (base_address
, 0);
1760 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1762 fprintf (dump_file
, "\nno memtag for ");
1763 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1764 fprintf (dump_file
, "\n");
1766 *memtag
= NULL_TREE
;
1773 /* MEMREF cannot be analyzed. */
1774 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1776 fprintf (dump_file
, "\ndata-ref of unsupported type ");
1777 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1778 fprintf (dump_file
, "\n");
1784 DR_REF (*dr
) = comp_ref
;
1786 if (SSA_VAR_P (*memtag
) && var_can_have_subvars (*memtag
))
1787 *subvars
= get_subvars_for_var (*memtag
);
1789 /* Part 2: Combine the results of object and address analysis to calculate
1790 INITIAL_OFFSET, STEP and misalignment info. */
1791 *offset
= size_binop (PLUS_EXPR
, object_offset
, address_offset
);
1793 if ((!object_misalign
&& !object_aligned_to
)
1794 || (!address_misalign
&& !address_aligned_to
))
1796 *misalign
= NULL_TREE
;
1797 *aligned_to
= NULL_TREE
;
1801 if (object_misalign
&& address_misalign
)
1802 *misalign
= size_binop (PLUS_EXPR
, object_misalign
, address_misalign
);
1804 *misalign
= object_misalign
? object_misalign
: address_misalign
;
1805 if (object_aligned_to
&& address_aligned_to
)
1806 *aligned_to
= size_binop (MIN_EXPR
, object_aligned_to
,
1807 address_aligned_to
);
1809 *aligned_to
= object_aligned_to
?
1810 object_aligned_to
: address_aligned_to
;
1812 *step
= size_binop (PLUS_EXPR
, object_step
, address_step
);
1814 return base_address
;
1817 /* Function analyze_offset.
1819 Extract INVARIANT and CONSTANT parts from OFFSET.
1823 analyze_offset (tree offset
, tree
*invariant
, tree
*constant
)
1825 tree op0
, op1
, constant_0
, constant_1
, invariant_0
, invariant_1
;
1826 enum tree_code code
= TREE_CODE (offset
);
1828 *invariant
= NULL_TREE
;
1829 *constant
= NULL_TREE
;
1831 /* Not PLUS/MINUS expression - recursion stop condition. */
1832 if (code
!= PLUS_EXPR
&& code
!= MINUS_EXPR
)
1834 if (TREE_CODE (offset
) == INTEGER_CST
)
1837 *invariant
= offset
;
1841 op0
= TREE_OPERAND (offset
, 0);
1842 op1
= TREE_OPERAND (offset
, 1);
1844 /* Recursive call with the operands. */
1845 analyze_offset (op0
, &invariant_0
, &constant_0
);
1846 analyze_offset (op1
, &invariant_1
, &constant_1
);
1848 /* Combine the results. */
1849 *constant
= constant_0
? constant_0
: constant_1
;
1850 if (invariant_0
&& invariant_1
)
1852 fold_build2 (code
, TREE_TYPE (invariant_0
), invariant_0
, invariant_1
);
1854 *invariant
= invariant_0
? invariant_0
: invariant_1
;
1858 /* Function create_data_ref.
1860 Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS,
1861 DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO,
1862 DR_MEMTAG, and DR_POINTSTO_INFO fields.
1865 MEMREF - the memory reference that is being analyzed
1866 STMT - the statement that contains MEMREF
1867 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1870 DR (returned value) - data_reference struct for MEMREF
1873 static struct data_reference
*
1874 create_data_ref (tree memref
, tree stmt
, bool is_read
)
1876 struct data_reference
*dr
= NULL
;
1877 tree base_address
, offset
, step
, misalign
, memtag
;
1878 struct loop
*loop
= loop_containing_stmt (stmt
);
1879 tree invariant
= NULL_TREE
, constant
= NULL_TREE
;
1880 tree type_size
, init_cond
;
1881 struct ptr_info_def
*ptr_info
;
1882 subvar_t subvars
= NULL
;
1883 tree aligned_to
, type
= NULL_TREE
, orig_offset
;
1888 base_address
= object_analysis (memref
, stmt
, is_read
, &dr
, &offset
,
1889 &misalign
, &aligned_to
, &step
, &memtag
,
1890 &ptr_info
, &subvars
);
1891 if (!dr
|| !base_address
)
1893 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1895 fprintf (dump_file
, "\ncreate_data_ref: failed to create a dr for ");
1896 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1897 fprintf (dump_file
, "\n");
1902 DR_BASE_ADDRESS (dr
) = base_address
;
1903 DR_OFFSET (dr
) = offset
;
1904 DR_INIT (dr
) = ssize_int (0);
1905 DR_STEP (dr
) = step
;
1906 DR_OFFSET_MISALIGNMENT (dr
) = misalign
;
1907 DR_ALIGNED_TO (dr
) = aligned_to
;
1908 DR_MEMTAG (dr
) = memtag
;
1909 DR_PTR_INFO (dr
) = ptr_info
;
1910 DR_SUBVARS (dr
) = subvars
;
1912 type_size
= fold_convert (ssizetype
, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr
))));
1914 /* Extract CONSTANT and INVARIANT from OFFSET. */
1915 /* Remove cast from OFFSET and restore it for INVARIANT part. */
1916 orig_offset
= offset
;
1917 STRIP_NOPS (offset
);
1918 if (offset
!= orig_offset
)
1919 type
= TREE_TYPE (orig_offset
);
1920 analyze_offset (offset
, &invariant
, &constant
);
1921 if (type
&& invariant
)
1922 invariant
= fold_convert (type
, invariant
);
1924 /* Put CONSTANT part of OFFSET in DR_INIT and INVARIANT in DR_OFFSET field
1928 DR_INIT (dr
) = fold_convert (ssizetype
, constant
);
1929 init_cond
= fold_build2 (TRUNC_DIV_EXPR
, TREE_TYPE (constant
),
1930 constant
, type_size
);
1933 DR_INIT (dr
) = init_cond
= ssize_int (0);
1936 DR_OFFSET (dr
) = invariant
;
1938 DR_OFFSET (dr
) = ssize_int (0);
1940 /* Change the access function for INIDIRECT_REFs, according to
1941 DR_BASE_ADDRESS. Analyze OFFSET calculated in object_analysis. OFFSET is
1942 an expression that can contain loop invariant expressions and constants.
1943 We put the constant part in the initial condition of the access function
1944 (for data dependence tests), and in DR_INIT of the data-ref. The loop
1945 invariant part is put in DR_OFFSET.
1946 The evolution part of the access function is STEP calculated in
1947 object_analysis divided by the size of data type.
1949 if (!DR_BASE_OBJECT (dr
)
1950 || (TREE_CODE (memref
) == COMPONENT_REF
&& DR_NUM_DIMENSIONS (dr
) == 1))
1955 /* Update access function. */
1956 access_fn
= DR_ACCESS_FN (dr
, 0);
1957 new_step
= size_binop (TRUNC_DIV_EXPR
,
1958 fold_convert (ssizetype
, step
), type_size
);
1960 init_cond
= chrec_convert (chrec_type (access_fn
), init_cond
, stmt
);
1961 new_step
= chrec_convert (chrec_type (access_fn
), new_step
, stmt
);
1962 access_fn
= chrec_replace_initial_condition (access_fn
, init_cond
);
1963 access_fn
= reset_evolution_in_loop (loop
->num
, access_fn
, new_step
);
1965 VEC_replace (tree
, DR_ACCESS_FNS (dr
), 0, access_fn
);
1968 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1970 struct ptr_info_def
*pi
= DR_PTR_INFO (dr
);
1972 fprintf (dump_file
, "\nCreated dr for ");
1973 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1974 fprintf (dump_file
, "\n\tbase_address: ");
1975 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
1976 fprintf (dump_file
, "\n\toffset from base address: ");
1977 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
1978 fprintf (dump_file
, "\n\tconstant offset from base address: ");
1979 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
1980 fprintf (dump_file
, "\n\tbase_object: ");
1981 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
1982 fprintf (dump_file
, "\n\tstep: ");
1983 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
1984 fprintf (dump_file
, "B\n\tmisalignment from base: ");
1985 print_generic_expr (dump_file
, DR_OFFSET_MISALIGNMENT (dr
), TDF_SLIM
);
1986 if (DR_OFFSET_MISALIGNMENT (dr
))
1987 fprintf (dump_file
, "B");
1988 if (DR_ALIGNED_TO (dr
))
1990 fprintf (dump_file
, "\n\taligned to: ");
1991 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
1993 fprintf (dump_file
, "\n\tmemtag: ");
1994 print_generic_expr (dump_file
, DR_MEMTAG (dr
), TDF_SLIM
);
1995 fprintf (dump_file
, "\n");
1996 if (pi
&& pi
->name_mem_tag
)
1998 fprintf (dump_file
, "\n\tnametag: ");
1999 print_generic_expr (dump_file
, pi
->name_mem_tag
, TDF_SLIM
);
2000 fprintf (dump_file
, "\n");
2007 /* Returns true when all the functions of a tree_vec CHREC are the
2011 all_chrecs_equal_p (tree chrec
)
2015 for (j
= 0; j
< TREE_VEC_LENGTH (chrec
) - 1; j
++)
2016 if (!eq_evolutions_p (TREE_VEC_ELT (chrec
, j
),
2017 TREE_VEC_ELT (chrec
, j
+ 1)))
2023 /* Determine for each subscript in the data dependence relation DDR
2027 compute_subscript_distance (struct data_dependence_relation
*ddr
)
2029 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
2033 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2035 tree conflicts_a
, conflicts_b
, difference
;
2036 struct subscript
*subscript
;
2038 subscript
= DDR_SUBSCRIPT (ddr
, i
);
2039 conflicts_a
= SUB_CONFLICTS_IN_A (subscript
);
2040 conflicts_b
= SUB_CONFLICTS_IN_B (subscript
);
2042 if (TREE_CODE (conflicts_a
) == TREE_VEC
)
2044 if (!all_chrecs_equal_p (conflicts_a
))
2046 SUB_DISTANCE (subscript
) = chrec_dont_know
;
2050 conflicts_a
= TREE_VEC_ELT (conflicts_a
, 0);
2053 if (TREE_CODE (conflicts_b
) == TREE_VEC
)
2055 if (!all_chrecs_equal_p (conflicts_b
))
2057 SUB_DISTANCE (subscript
) = chrec_dont_know
;
2061 conflicts_b
= TREE_VEC_ELT (conflicts_b
, 0);
2064 conflicts_b
= chrec_convert (integer_type_node
, conflicts_b
,
2066 conflicts_a
= chrec_convert (integer_type_node
, conflicts_a
,
2068 difference
= chrec_fold_minus
2069 (integer_type_node
, conflicts_b
, conflicts_a
);
2071 if (evolution_function_is_constant_p (difference
))
2072 SUB_DISTANCE (subscript
) = difference
;
2075 SUB_DISTANCE (subscript
) = chrec_dont_know
;
2080 /* Initialize a data dependence relation between data accesses A and
2081 B. NB_LOOPS is the number of loops surrounding the references: the
2082 size of the classic distance/direction vectors. */
2084 static struct data_dependence_relation
*
2085 initialize_data_dependence_relation (struct data_reference
*a
,
2086 struct data_reference
*b
,
2087 VEC (loop_p
, heap
) *loop_nest
)
2089 struct data_dependence_relation
*res
;
2090 bool differ_p
, known_dependence
;
2093 res
= XNEW (struct data_dependence_relation
);
2097 if (a
== NULL
|| b
== NULL
)
2099 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
2103 /* When A and B are arrays and their dimensions differ, we directly
2104 initialize the relation to "there is no dependence": chrec_known. */
2105 if (DR_BASE_OBJECT (a
) && DR_BASE_OBJECT (b
)
2106 && DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
))
2108 DDR_ARE_DEPENDENT (res
) = chrec_known
;
2112 if (DR_BASE_ADDRESS (a
) && DR_BASE_ADDRESS (b
))
2113 known_dependence
= base_addr_differ_p (a
, b
, &differ_p
);
2115 known_dependence
= base_object_differ_p (a
, b
, &differ_p
);
2117 if (!known_dependence
)
2119 /* Can't determine whether the data-refs access the same memory
2121 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
2127 DDR_ARE_DEPENDENT (res
) = chrec_known
;
2131 DDR_AFFINE_P (res
) = true;
2132 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
2133 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
2134 DDR_LOOP_NEST (res
) = loop_nest
;
2135 DDR_DIR_VECTS (res
) = NULL
;
2136 DDR_DIST_VECTS (res
) = NULL
;
2138 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
2140 struct subscript
*subscript
;
2142 subscript
= XNEW (struct subscript
);
2143 SUB_CONFLICTS_IN_A (subscript
) = chrec_dont_know
;
2144 SUB_CONFLICTS_IN_B (subscript
) = chrec_dont_know
;
2145 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
2146 SUB_DISTANCE (subscript
) = chrec_dont_know
;
2147 VEC_safe_push (subscript_p
, heap
, DDR_SUBSCRIPTS (res
), subscript
);
2153 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
2157 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
2160 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2162 fprintf (dump_file
, "(dependence classified: ");
2163 print_generic_expr (dump_file
, chrec
, 0);
2164 fprintf (dump_file
, ")\n");
2167 DDR_ARE_DEPENDENT (ddr
) = chrec
;
2168 VEC_free (subscript_p
, heap
, DDR_SUBSCRIPTS (ddr
));
2171 /* The dependence relation DDR cannot be represented by a distance
2175 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
2177 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2178 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
2180 DDR_AFFINE_P (ddr
) = false;
2185 /* This section contains the classic Banerjee tests. */
2187 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
2188 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
2191 ziv_subscript_p (tree chrec_a
,
2194 return (evolution_function_is_constant_p (chrec_a
)
2195 && evolution_function_is_constant_p (chrec_b
));
2198 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
2199 variable, i.e., if the SIV (Single Index Variable) test is true. */
2202 siv_subscript_p (tree chrec_a
,
2205 if ((evolution_function_is_constant_p (chrec_a
)
2206 && evolution_function_is_univariate_p (chrec_b
))
2207 || (evolution_function_is_constant_p (chrec_b
)
2208 && evolution_function_is_univariate_p (chrec_a
)))
2211 if (evolution_function_is_univariate_p (chrec_a
)
2212 && evolution_function_is_univariate_p (chrec_b
))
2214 switch (TREE_CODE (chrec_a
))
2216 case POLYNOMIAL_CHREC
:
2217 switch (TREE_CODE (chrec_b
))
2219 case POLYNOMIAL_CHREC
:
2220 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
2235 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
2236 *OVERLAPS_B are initialized to the functions that describe the
2237 relation between the elements accessed twice by CHREC_A and
2238 CHREC_B. For k >= 0, the following property is verified:
2240 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2243 analyze_ziv_subscript (tree chrec_a
,
2247 tree
*last_conflicts
)
2250 dependence_stats
.num_ziv
++;
2252 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2253 fprintf (dump_file
, "(analyze_ziv_subscript \n");
2255 chrec_a
= chrec_convert (integer_type_node
, chrec_a
, NULL_TREE
);
2256 chrec_b
= chrec_convert (integer_type_node
, chrec_b
, NULL_TREE
);
2257 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
2259 switch (TREE_CODE (difference
))
2262 if (integer_zerop (difference
))
2264 /* The difference is equal to zero: the accessed index
2265 overlaps for each iteration in the loop. */
2266 *overlaps_a
= integer_zero_node
;
2267 *overlaps_b
= integer_zero_node
;
2268 *last_conflicts
= chrec_dont_know
;
2269 dependence_stats
.num_ziv_dependent
++;
2273 /* The accesses do not overlap. */
2274 *overlaps_a
= chrec_known
;
2275 *overlaps_b
= chrec_known
;
2276 *last_conflicts
= integer_zero_node
;
2277 dependence_stats
.num_ziv_independent
++;
2282 /* We're not sure whether the indexes overlap. For the moment,
2283 conservatively answer "don't know". */
2284 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2285 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
2287 *overlaps_a
= chrec_dont_know
;
2288 *overlaps_b
= chrec_dont_know
;
2289 *last_conflicts
= chrec_dont_know
;
2290 dependence_stats
.num_ziv_unimplemented
++;
2294 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2295 fprintf (dump_file
, ")\n");
2298 /* Get the real or estimated number of iterations for LOOPNUM, whichever is
2299 available. Return the number of iterations as a tree, or NULL_TREE if
2303 get_number_of_iters_for_loop (int loopnum
)
2305 tree numiter
= number_of_iterations_in_loop (current_loops
->parray
[loopnum
]);
2307 if (TREE_CODE (numiter
) != INTEGER_CST
)
2308 numiter
= current_loops
->parray
[loopnum
]->estimated_nb_iterations
;
2309 if (chrec_contains_undetermined (numiter
))
2314 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2315 constant, and CHREC_B is an affine function. *OVERLAPS_A and
2316 *OVERLAPS_B are initialized to the functions that describe the
2317 relation between the elements accessed twice by CHREC_A and
2318 CHREC_B. For k >= 0, the following property is verified:
2320 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2323 analyze_siv_subscript_cst_affine (tree chrec_a
,
2327 tree
*last_conflicts
)
2329 bool value0
, value1
, value2
;
2332 chrec_a
= chrec_convert (integer_type_node
, chrec_a
, NULL_TREE
);
2333 chrec_b
= chrec_convert (integer_type_node
, chrec_b
, NULL_TREE
);
2334 difference
= chrec_fold_minus
2335 (integer_type_node
, CHREC_LEFT (chrec_b
), chrec_a
);
2337 if (!chrec_is_positive (initial_condition (difference
), &value0
))
2339 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2340 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
2342 dependence_stats
.num_siv_unimplemented
++;
2343 *overlaps_a
= chrec_dont_know
;
2344 *overlaps_b
= chrec_dont_know
;
2345 *last_conflicts
= chrec_dont_know
;
2350 if (value0
== false)
2352 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
2354 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2355 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
2357 *overlaps_a
= chrec_dont_know
;
2358 *overlaps_b
= chrec_dont_know
;
2359 *last_conflicts
= chrec_dont_know
;
2360 dependence_stats
.num_siv_unimplemented
++;
2369 chrec_b = {10, +, 1}
2372 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
2375 int loopnum
= CHREC_VARIABLE (chrec_b
);
2377 *overlaps_a
= integer_zero_node
;
2378 *overlaps_b
= fold_build2 (EXACT_DIV_EXPR
, integer_type_node
,
2379 fold_build1 (ABS_EXPR
,
2382 CHREC_RIGHT (chrec_b
));
2383 *last_conflicts
= integer_one_node
;
2386 /* Perform weak-zero siv test to see if overlap is
2387 outside the loop bounds. */
2388 numiter
= get_number_of_iters_for_loop (loopnum
);
2390 if (numiter
!= NULL_TREE
2391 && TREE_CODE (*overlaps_b
) == INTEGER_CST
2392 && tree_int_cst_lt (numiter
, *overlaps_b
))
2394 *overlaps_a
= chrec_known
;
2395 *overlaps_b
= chrec_known
;
2396 *last_conflicts
= integer_zero_node
;
2397 dependence_stats
.num_siv_independent
++;
2400 dependence_stats
.num_siv_dependent
++;
2404 /* When the step does not divide the difference, there are
2408 *overlaps_a
= chrec_known
;
2409 *overlaps_b
= chrec_known
;
2410 *last_conflicts
= integer_zero_node
;
2411 dependence_stats
.num_siv_independent
++;
2420 chrec_b = {10, +, -1}
2422 In this case, chrec_a will not overlap with chrec_b. */
2423 *overlaps_a
= chrec_known
;
2424 *overlaps_b
= chrec_known
;
2425 *last_conflicts
= integer_zero_node
;
2426 dependence_stats
.num_siv_independent
++;
2433 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
2435 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2436 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
2438 *overlaps_a
= chrec_dont_know
;
2439 *overlaps_b
= chrec_dont_know
;
2440 *last_conflicts
= chrec_dont_know
;
2441 dependence_stats
.num_siv_unimplemented
++;
2446 if (value2
== false)
2450 chrec_b = {10, +, -1}
2452 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
2455 int loopnum
= CHREC_VARIABLE (chrec_b
);
2457 *overlaps_a
= integer_zero_node
;
2458 *overlaps_b
= fold_build2 (EXACT_DIV_EXPR
,
2459 integer_type_node
, difference
,
2460 CHREC_RIGHT (chrec_b
));
2461 *last_conflicts
= integer_one_node
;
2463 /* Perform weak-zero siv test to see if overlap is
2464 outside the loop bounds. */
2465 numiter
= get_number_of_iters_for_loop (loopnum
);
2467 if (numiter
!= NULL_TREE
2468 && TREE_CODE (*overlaps_b
) == INTEGER_CST
2469 && tree_int_cst_lt (numiter
, *overlaps_b
))
2471 *overlaps_a
= chrec_known
;
2472 *overlaps_b
= chrec_known
;
2473 *last_conflicts
= integer_zero_node
;
2474 dependence_stats
.num_siv_independent
++;
2477 dependence_stats
.num_siv_dependent
++;
2481 /* When the step does not divide the difference, there
2485 *overlaps_a
= chrec_known
;
2486 *overlaps_b
= chrec_known
;
2487 *last_conflicts
= integer_zero_node
;
2488 dependence_stats
.num_siv_independent
++;
2498 In this case, chrec_a will not overlap with chrec_b. */
2499 *overlaps_a
= chrec_known
;
2500 *overlaps_b
= chrec_known
;
2501 *last_conflicts
= integer_zero_node
;
2502 dependence_stats
.num_siv_independent
++;
2510 /* Helper recursive function for initializing the matrix A. Returns
2511 the initial value of CHREC. */
2514 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
2518 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
2519 return int_cst_value (chrec
);
2521 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
2522 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
2525 #define FLOOR_DIV(x,y) ((x) / (y))
2527 /* Solves the special case of the Diophantine equation:
2528 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2530 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2531 number of iterations that loops X and Y run. The overlaps will be
2532 constructed as evolutions in dimension DIM. */
2535 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
2536 tree
*overlaps_a
, tree
*overlaps_b
,
2537 tree
*last_conflicts
, int dim
)
2539 if (((step_a
> 0 && step_b
> 0)
2540 || (step_a
< 0 && step_b
< 0)))
2542 int step_overlaps_a
, step_overlaps_b
;
2543 int gcd_steps_a_b
, last_conflict
, tau2
;
2545 gcd_steps_a_b
= gcd (step_a
, step_b
);
2546 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
2547 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
2549 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
2550 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
2551 last_conflict
= tau2
;
2553 *overlaps_a
= build_polynomial_chrec
2554 (dim
, integer_zero_node
,
2555 build_int_cst (NULL_TREE
, step_overlaps_a
));
2556 *overlaps_b
= build_polynomial_chrec
2557 (dim
, integer_zero_node
,
2558 build_int_cst (NULL_TREE
, step_overlaps_b
));
2559 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2564 *overlaps_a
= integer_zero_node
;
2565 *overlaps_b
= integer_zero_node
;
2566 *last_conflicts
= integer_zero_node
;
2571 /* Solves the special case of a Diophantine equation where CHREC_A is
2572 an affine bivariate function, and CHREC_B is an affine univariate
2573 function. For example,
2575 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2577 has the following overlapping functions:
2579 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2580 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2581 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2583 FORNOW: This is a specialized implementation for a case occurring in
2584 a common benchmark. Implement the general algorithm. */
2587 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
2588 tree
*overlaps_a
, tree
*overlaps_b
,
2589 tree
*last_conflicts
)
2591 bool xz_p
, yz_p
, xyz_p
;
2592 int step_x
, step_y
, step_z
;
2593 int niter_x
, niter_y
, niter_z
, niter
;
2594 tree numiter_x
, numiter_y
, numiter_z
;
2595 tree overlaps_a_xz
, overlaps_b_xz
, last_conflicts_xz
;
2596 tree overlaps_a_yz
, overlaps_b_yz
, last_conflicts_yz
;
2597 tree overlaps_a_xyz
, overlaps_b_xyz
, last_conflicts_xyz
;
2599 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
2600 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
2601 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
2603 numiter_x
= get_number_of_iters_for_loop (CHREC_VARIABLE (CHREC_LEFT (chrec_a
)));
2604 numiter_y
= get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a
));
2605 numiter_z
= get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b
));
2607 if (numiter_x
== NULL_TREE
|| numiter_y
== NULL_TREE
2608 || numiter_z
== NULL_TREE
)
2610 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2611 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
2613 *overlaps_a
= chrec_dont_know
;
2614 *overlaps_b
= chrec_dont_know
;
2615 *last_conflicts
= chrec_dont_know
;
2619 niter_x
= int_cst_value (numiter_x
);
2620 niter_y
= int_cst_value (numiter_y
);
2621 niter_z
= int_cst_value (numiter_z
);
2623 niter
= MIN (niter_x
, niter_z
);
2624 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
2627 &last_conflicts_xz
, 1);
2628 niter
= MIN (niter_y
, niter_z
);
2629 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
2632 &last_conflicts_yz
, 2);
2633 niter
= MIN (niter_x
, niter_z
);
2634 niter
= MIN (niter_y
, niter
);
2635 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
2638 &last_conflicts_xyz
, 3);
2640 xz_p
= !integer_zerop (last_conflicts_xz
);
2641 yz_p
= !integer_zerop (last_conflicts_yz
);
2642 xyz_p
= !integer_zerop (last_conflicts_xyz
);
2644 if (xz_p
|| yz_p
|| xyz_p
)
2646 *overlaps_a
= make_tree_vec (2);
2647 TREE_VEC_ELT (*overlaps_a
, 0) = integer_zero_node
;
2648 TREE_VEC_ELT (*overlaps_a
, 1) = integer_zero_node
;
2649 *overlaps_b
= integer_zero_node
;
2652 tree t0
= chrec_convert (integer_type_node
,
2653 TREE_VEC_ELT (*overlaps_a
, 0), NULL_TREE
);
2654 tree t1
= chrec_convert (integer_type_node
, overlaps_a_xz
,
2656 tree t2
= chrec_convert (integer_type_node
, *overlaps_b
,
2658 tree t3
= chrec_convert (integer_type_node
, overlaps_b_xz
,
2661 TREE_VEC_ELT (*overlaps_a
, 0) = chrec_fold_plus (integer_type_node
,
2663 *overlaps_b
= chrec_fold_plus (integer_type_node
, t2
, t3
);
2664 *last_conflicts
= last_conflicts_xz
;
2668 tree t0
= chrec_convert (integer_type_node
,
2669 TREE_VEC_ELT (*overlaps_a
, 1), NULL_TREE
);
2670 tree t1
= chrec_convert (integer_type_node
, overlaps_a_yz
, NULL_TREE
);
2671 tree t2
= chrec_convert (integer_type_node
, *overlaps_b
, NULL_TREE
);
2672 tree t3
= chrec_convert (integer_type_node
, overlaps_b_yz
, NULL_TREE
);
2674 TREE_VEC_ELT (*overlaps_a
, 1) = chrec_fold_plus (integer_type_node
,
2676 *overlaps_b
= chrec_fold_plus (integer_type_node
, t2
, t3
);
2677 *last_conflicts
= last_conflicts_yz
;
2681 tree t0
= chrec_convert (integer_type_node
,
2682 TREE_VEC_ELT (*overlaps_a
, 0), NULL_TREE
);
2683 tree t1
= chrec_convert (integer_type_node
, overlaps_a_xyz
,
2685 tree t2
= chrec_convert (integer_type_node
,
2686 TREE_VEC_ELT (*overlaps_a
, 1), NULL_TREE
);
2687 tree t3
= chrec_convert (integer_type_node
, overlaps_a_xyz
,
2689 tree t4
= chrec_convert (integer_type_node
, *overlaps_b
, NULL_TREE
);
2690 tree t5
= chrec_convert (integer_type_node
, overlaps_b_xyz
,
2693 TREE_VEC_ELT (*overlaps_a
, 0) = chrec_fold_plus (integer_type_node
,
2695 TREE_VEC_ELT (*overlaps_a
, 1) = chrec_fold_plus (integer_type_node
,
2697 *overlaps_b
= chrec_fold_plus (integer_type_node
, t4
, t5
);
2698 *last_conflicts
= last_conflicts_xyz
;
2703 *overlaps_a
= integer_zero_node
;
2704 *overlaps_b
= integer_zero_node
;
2705 *last_conflicts
= integer_zero_node
;
2709 /* Determines the overlapping elements due to accesses CHREC_A and
2710 CHREC_B, that are affine functions. This function cannot handle
2711 symbolic evolution functions, ie. when initial conditions are
2712 parameters, because it uses lambda matrices of integers. */
2715 analyze_subscript_affine_affine (tree chrec_a
,
2719 tree
*last_conflicts
)
2721 unsigned nb_vars_a
, nb_vars_b
, dim
;
2722 int init_a
, init_b
, gamma
, gcd_alpha_beta
;
2724 lambda_matrix A
, U
, S
;
2726 if (eq_evolutions_p (chrec_a
, chrec_b
))
2728 /* The accessed index overlaps for each iteration in the
2730 *overlaps_a
= integer_zero_node
;
2731 *overlaps_b
= integer_zero_node
;
2732 *last_conflicts
= chrec_dont_know
;
2735 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2736 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
2738 /* For determining the initial intersection, we have to solve a
2739 Diophantine equation. This is the most time consuming part.
2741 For answering to the question: "Is there a dependence?" we have
2742 to prove that there exists a solution to the Diophantine
2743 equation, and that the solution is in the iteration domain,
2744 i.e. the solution is positive or zero, and that the solution
2745 happens before the upper bound loop.nb_iterations. Otherwise
2746 there is no dependence. This function outputs a description of
2747 the iterations that hold the intersections. */
2749 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
2750 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
2752 dim
= nb_vars_a
+ nb_vars_b
;
2753 U
= lambda_matrix_new (dim
, dim
);
2754 A
= lambda_matrix_new (dim
, 1);
2755 S
= lambda_matrix_new (dim
, 1);
2757 init_a
= initialize_matrix_A (A
, chrec_a
, 0, 1);
2758 init_b
= initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1);
2759 gamma
= init_b
- init_a
;
2761 /* Don't do all the hard work of solving the Diophantine equation
2762 when we already know the solution: for example,
2765 | gamma = 3 - 3 = 0.
2766 Then the first overlap occurs during the first iterations:
2767 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2771 if (nb_vars_a
== 1 && nb_vars_b
== 1)
2774 int niter
, niter_a
, niter_b
;
2775 tree numiter_a
, numiter_b
;
2777 numiter_a
= get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a
));
2778 numiter_b
= get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b
));
2779 if (numiter_a
== NULL_TREE
|| numiter_b
== NULL_TREE
)
2781 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2782 fprintf (dump_file
, "affine-affine test failed: missing iteration counts.\n");
2783 *overlaps_a
= chrec_dont_know
;
2784 *overlaps_b
= chrec_dont_know
;
2785 *last_conflicts
= chrec_dont_know
;
2786 goto end_analyze_subs_aa
;
2789 niter_a
= int_cst_value (numiter_a
);
2790 niter_b
= int_cst_value (numiter_b
);
2791 niter
= MIN (niter_a
, niter_b
);
2793 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
2794 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
2796 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
2797 overlaps_a
, overlaps_b
,
2801 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
2802 compute_overlap_steps_for_affine_1_2
2803 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
2805 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
2806 compute_overlap_steps_for_affine_1_2
2807 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
2811 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2812 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
2813 *overlaps_a
= chrec_dont_know
;
2814 *overlaps_b
= chrec_dont_know
;
2815 *last_conflicts
= chrec_dont_know
;
2817 goto end_analyze_subs_aa
;
2821 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
2826 lambda_matrix_row_negate (U
, dim
, 0);
2828 gcd_alpha_beta
= S
[0][0];
2830 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2831 but that is a quite strange case. Instead of ICEing, answer
2833 if (gcd_alpha_beta
== 0)
2835 *overlaps_a
= chrec_dont_know
;
2836 *overlaps_b
= chrec_dont_know
;
2837 *last_conflicts
= chrec_dont_know
;
2838 goto end_analyze_subs_aa
;
2841 /* The classic "gcd-test". */
2842 if (!int_divides_p (gcd_alpha_beta
, gamma
))
2844 /* The "gcd-test" has determined that there is no integer
2845 solution, i.e. there is no dependence. */
2846 *overlaps_a
= chrec_known
;
2847 *overlaps_b
= chrec_known
;
2848 *last_conflicts
= integer_zero_node
;
2851 /* Both access functions are univariate. This includes SIV and MIV cases. */
2852 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
2854 /* Both functions should have the same evolution sign. */
2855 if (((A
[0][0] > 0 && -A
[1][0] > 0)
2856 || (A
[0][0] < 0 && -A
[1][0] < 0)))
2858 /* The solutions are given by:
2860 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2863 For a given integer t. Using the following variables,
2865 | i0 = u11 * gamma / gcd_alpha_beta
2866 | j0 = u12 * gamma / gcd_alpha_beta
2873 | y0 = j0 + j1 * t. */
2877 /* X0 and Y0 are the first iterations for which there is a
2878 dependence. X0, Y0 are two solutions of the Diophantine
2879 equation: chrec_a (X0) = chrec_b (Y0). */
2881 int niter
, niter_a
, niter_b
;
2882 tree numiter_a
, numiter_b
;
2884 numiter_a
= get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a
));
2885 numiter_b
= get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b
));
2887 if (numiter_a
== NULL_TREE
|| numiter_b
== NULL_TREE
)
2889 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2890 fprintf (dump_file
, "affine-affine test failed: missing iteration counts.\n");
2891 *overlaps_a
= chrec_dont_know
;
2892 *overlaps_b
= chrec_dont_know
;
2893 *last_conflicts
= chrec_dont_know
;
2894 goto end_analyze_subs_aa
;
2897 niter_a
= int_cst_value (numiter_a
);
2898 niter_b
= int_cst_value (numiter_b
);
2899 niter
= MIN (niter_a
, niter_b
);
2901 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
2902 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
2906 if ((i1
== 0 && i0
< 0)
2907 || (j1
== 0 && j0
< 0))
2909 /* There is no solution.
2910 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2911 falls in here, but for the moment we don't look at the
2912 upper bound of the iteration domain. */
2913 *overlaps_a
= chrec_known
;
2914 *overlaps_b
= chrec_known
;
2915 *last_conflicts
= integer_zero_node
;
2922 tau1
= CEIL (-i0
, i1
);
2923 tau2
= FLOOR_DIV (niter
- i0
, i1
);
2927 int last_conflict
, min_multiple
;
2928 tau1
= MAX (tau1
, CEIL (-j0
, j1
));
2929 tau2
= MIN (tau2
, FLOOR_DIV (niter
- j0
, j1
));
2931 x0
= i1
* tau1
+ i0
;
2932 y0
= j1
* tau1
+ j0
;
2934 /* At this point (x0, y0) is one of the
2935 solutions to the Diophantine equation. The
2936 next step has to compute the smallest
2937 positive solution: the first conflicts. */
2938 min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
2939 x0
-= i1
* min_multiple
;
2940 y0
-= j1
* min_multiple
;
2942 tau1
= (x0
- i0
)/i1
;
2943 last_conflict
= tau2
- tau1
;
2945 /* If the overlap occurs outside of the bounds of the
2946 loop, there is no dependence. */
2947 if (x0
> niter
|| y0
> niter
)
2949 *overlaps_a
= chrec_known
;
2950 *overlaps_b
= chrec_known
;
2951 *last_conflicts
= integer_zero_node
;
2955 *overlaps_a
= build_polynomial_chrec
2957 build_int_cst (NULL_TREE
, x0
),
2958 build_int_cst (NULL_TREE
, i1
));
2959 *overlaps_b
= build_polynomial_chrec
2961 build_int_cst (NULL_TREE
, y0
),
2962 build_int_cst (NULL_TREE
, j1
));
2963 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2968 /* FIXME: For the moment, the upper bound of the
2969 iteration domain for j is not checked. */
2970 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2971 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2972 *overlaps_a
= chrec_dont_know
;
2973 *overlaps_b
= chrec_dont_know
;
2974 *last_conflicts
= chrec_dont_know
;
2980 /* FIXME: For the moment, the upper bound of the
2981 iteration domain for i is not checked. */
2982 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2983 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2984 *overlaps_a
= chrec_dont_know
;
2985 *overlaps_b
= chrec_dont_know
;
2986 *last_conflicts
= chrec_dont_know
;
2992 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2993 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
2994 *overlaps_a
= chrec_dont_know
;
2995 *overlaps_b
= chrec_dont_know
;
2996 *last_conflicts
= chrec_dont_know
;
3002 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3003 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
3004 *overlaps_a
= chrec_dont_know
;
3005 *overlaps_b
= chrec_dont_know
;
3006 *last_conflicts
= chrec_dont_know
;
3009 end_analyze_subs_aa
:
3010 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3012 fprintf (dump_file
, " (overlaps_a = ");
3013 print_generic_expr (dump_file
, *overlaps_a
, 0);
3014 fprintf (dump_file
, ")\n (overlaps_b = ");
3015 print_generic_expr (dump_file
, *overlaps_b
, 0);
3016 fprintf (dump_file
, ")\n");
3017 fprintf (dump_file
, ")\n");
3021 /* Returns true when analyze_subscript_affine_affine can be used for
3022 determining the dependence relation between chrec_a and chrec_b,
3023 that contain symbols. This function modifies chrec_a and chrec_b
3024 such that the analysis result is the same, and such that they don't
3025 contain symbols, and then can safely be passed to the analyzer.
3027 Example: The analysis of the following tuples of evolutions produce
3028 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
3031 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
3032 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
3036 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
3038 tree diff
, type
, left_a
, left_b
, right_b
;
3040 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
3041 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
3042 /* FIXME: For the moment not handled. Might be refined later. */
3045 type
= chrec_type (*chrec_a
);
3046 left_a
= CHREC_LEFT (*chrec_a
);
3047 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL_TREE
);
3048 diff
= chrec_fold_minus (type
, left_a
, left_b
);
3050 if (!evolution_function_is_constant_p (diff
))
3053 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3054 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
3056 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
3057 diff
, CHREC_RIGHT (*chrec_a
));
3058 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL_TREE
);
3059 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
3060 build_int_cst (type
, 0),
3065 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
3066 *OVERLAPS_B are initialized to the functions that describe the
3067 relation between the elements accessed twice by CHREC_A and
3068 CHREC_B. For k >= 0, the following property is verified:
3070 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
3073 analyze_siv_subscript (tree chrec_a
,
3077 tree
*last_conflicts
)
3079 dependence_stats
.num_siv
++;
3081 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3082 fprintf (dump_file
, "(analyze_siv_subscript \n");
3084 if (evolution_function_is_constant_p (chrec_a
)
3085 && evolution_function_is_affine_p (chrec_b
))
3086 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
3087 overlaps_a
, overlaps_b
, last_conflicts
);
3089 else if (evolution_function_is_affine_p (chrec_a
)
3090 && evolution_function_is_constant_p (chrec_b
))
3091 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
3092 overlaps_b
, overlaps_a
, last_conflicts
);
3094 else if (evolution_function_is_affine_p (chrec_a
)
3095 && evolution_function_is_affine_p (chrec_b
))
3097 if (!chrec_contains_symbols (chrec_a
)
3098 && !chrec_contains_symbols (chrec_b
))
3100 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
3101 overlaps_a
, overlaps_b
,
3104 if (*overlaps_a
== chrec_dont_know
3105 || *overlaps_b
== chrec_dont_know
)
3106 dependence_stats
.num_siv_unimplemented
++;
3107 else if (*overlaps_a
== chrec_known
3108 || *overlaps_b
== chrec_known
)
3109 dependence_stats
.num_siv_independent
++;
3111 dependence_stats
.num_siv_dependent
++;
3113 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
3116 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
3117 overlaps_a
, overlaps_b
,
3119 /* FIXME: The number of iterations is a symbolic expression.
3120 Compute it properly. */
3121 *last_conflicts
= chrec_dont_know
;
3123 if (*overlaps_a
== chrec_dont_know
3124 || *overlaps_b
== chrec_dont_know
)
3125 dependence_stats
.num_siv_unimplemented
++;
3126 else if (*overlaps_a
== chrec_known
3127 || *overlaps_b
== chrec_known
)
3128 dependence_stats
.num_siv_independent
++;
3130 dependence_stats
.num_siv_dependent
++;
3133 goto siv_subscript_dontknow
;
3138 siv_subscript_dontknow
:;
3139 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3140 fprintf (dump_file
, "siv test failed: unimplemented.\n");
3141 *overlaps_a
= chrec_dont_know
;
3142 *overlaps_b
= chrec_dont_know
;
3143 *last_conflicts
= chrec_dont_know
;
3144 dependence_stats
.num_siv_unimplemented
++;
3147 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3148 fprintf (dump_file
, ")\n");
3151 /* Return true when the property can be computed. RES should contain
3152 true when calling the first time this function, then it is set to
3153 false when one of the evolution steps of an affine CHREC does not
3154 divide the constant CST. */
3157 chrec_steps_divide_constant_p (tree chrec
,
3161 switch (TREE_CODE (chrec
))
3163 case POLYNOMIAL_CHREC
:
3164 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
)))
3166 if (tree_fold_divides_p (CHREC_RIGHT (chrec
), cst
))
3167 /* Keep RES to true, and iterate on other dimensions. */
3168 return chrec_steps_divide_constant_p (CHREC_LEFT (chrec
), cst
, res
);
3174 /* When the step is a parameter the result is undetermined. */
3178 /* On the initial condition, return true. */
3183 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
3184 *OVERLAPS_B are initialized to the functions that describe the
3185 relation between the elements accessed twice by CHREC_A and
3186 CHREC_B. For k >= 0, the following property is verified:
3188 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
3191 analyze_miv_subscript (tree chrec_a
,
3195 tree
*last_conflicts
)
3197 /* FIXME: This is a MIV subscript, not yet handled.
3198 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
3201 In the SIV test we had to solve a Diophantine equation with two
3202 variables. In the MIV case we have to solve a Diophantine
3203 equation with 2*n variables (if the subscript uses n IVs).
3205 bool divide_p
= true;
3207 dependence_stats
.num_miv
++;
3208 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3209 fprintf (dump_file
, "(analyze_miv_subscript \n");
3211 chrec_a
= chrec_convert (integer_type_node
, chrec_a
, NULL_TREE
);
3212 chrec_b
= chrec_convert (integer_type_node
, chrec_b
, NULL_TREE
);
3213 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
3215 if (eq_evolutions_p (chrec_a
, chrec_b
))
3217 /* Access functions are the same: all the elements are accessed
3218 in the same order. */
3219 *overlaps_a
= integer_zero_node
;
3220 *overlaps_b
= integer_zero_node
;
3221 *last_conflicts
= get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a
));
3222 dependence_stats
.num_miv_dependent
++;
3225 else if (evolution_function_is_constant_p (difference
)
3226 /* For the moment, the following is verified:
3227 evolution_function_is_affine_multivariate_p (chrec_a) */
3228 && chrec_steps_divide_constant_p (chrec_a
, difference
, ÷_p
)
3231 /* testsuite/.../ssa-chrec-33.c
3232 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
3234 The difference is 1, and the evolution steps are equal to 2,
3235 consequently there are no overlapping elements. */
3236 *overlaps_a
= chrec_known
;
3237 *overlaps_b
= chrec_known
;
3238 *last_conflicts
= integer_zero_node
;
3239 dependence_stats
.num_miv_independent
++;
3242 else if (evolution_function_is_affine_multivariate_p (chrec_a
)
3243 && !chrec_contains_symbols (chrec_a
)
3244 && evolution_function_is_affine_multivariate_p (chrec_b
)
3245 && !chrec_contains_symbols (chrec_b
))
3247 /* testsuite/.../ssa-chrec-35.c
3248 {0, +, 1}_2 vs. {0, +, 1}_3
3249 the overlapping elements are respectively located at iterations:
3250 {0, +, 1}_x and {0, +, 1}_x,
3251 in other words, we have the equality:
3252 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
3255 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
3256 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
3258 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
3259 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
3261 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
3262 overlaps_a
, overlaps_b
, last_conflicts
);
3264 if (*overlaps_a
== chrec_dont_know
3265 || *overlaps_b
== chrec_dont_know
)
3266 dependence_stats
.num_miv_unimplemented
++;
3267 else if (*overlaps_a
== chrec_known
3268 || *overlaps_b
== chrec_known
)
3269 dependence_stats
.num_miv_independent
++;
3271 dependence_stats
.num_miv_dependent
++;
3276 /* When the analysis is too difficult, answer "don't know". */
3277 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3278 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
3280 *overlaps_a
= chrec_dont_know
;
3281 *overlaps_b
= chrec_dont_know
;
3282 *last_conflicts
= chrec_dont_know
;
3283 dependence_stats
.num_miv_unimplemented
++;
3286 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3287 fprintf (dump_file
, ")\n");
3290 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
3291 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
3292 two functions that describe the iterations that contain conflicting
3295 Remark: For an integer k >= 0, the following equality is true:
3297 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
3301 analyze_overlapping_iterations (tree chrec_a
,
3303 tree
*overlap_iterations_a
,
3304 tree
*overlap_iterations_b
,
3305 tree
*last_conflicts
)
3307 dependence_stats
.num_subscript_tests
++;
3309 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3311 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
3312 fprintf (dump_file
, " (chrec_a = ");
3313 print_generic_expr (dump_file
, chrec_a
, 0);
3314 fprintf (dump_file
, ")\n (chrec_b = ");
3315 print_generic_expr (dump_file
, chrec_b
, 0);
3316 fprintf (dump_file
, ")\n");
3319 if (chrec_a
== NULL_TREE
3320 || chrec_b
== NULL_TREE
3321 || chrec_contains_undetermined (chrec_a
)
3322 || chrec_contains_undetermined (chrec_b
))
3324 dependence_stats
.num_subscript_undetermined
++;
3326 *overlap_iterations_a
= chrec_dont_know
;
3327 *overlap_iterations_b
= chrec_dont_know
;
3330 /* If they are the same chrec, and are affine, they overlap
3331 on every iteration. */
3332 else if (eq_evolutions_p (chrec_a
, chrec_b
)
3333 && evolution_function_is_affine_multivariate_p (chrec_a
))
3335 dependence_stats
.num_same_subscript_function
++;
3336 *overlap_iterations_a
= integer_zero_node
;
3337 *overlap_iterations_b
= integer_zero_node
;
3338 *last_conflicts
= chrec_dont_know
;
3341 /* If they aren't the same, and aren't affine, we can't do anything
3343 else if ((chrec_contains_symbols (chrec_a
)
3344 || chrec_contains_symbols (chrec_b
))
3345 && (!evolution_function_is_affine_multivariate_p (chrec_a
)
3346 || !evolution_function_is_affine_multivariate_p (chrec_b
)))
3348 dependence_stats
.num_subscript_undetermined
++;
3349 *overlap_iterations_a
= chrec_dont_know
;
3350 *overlap_iterations_b
= chrec_dont_know
;
3353 else if (ziv_subscript_p (chrec_a
, chrec_b
))
3354 analyze_ziv_subscript (chrec_a
, chrec_b
,
3355 overlap_iterations_a
, overlap_iterations_b
,
3358 else if (siv_subscript_p (chrec_a
, chrec_b
))
3359 analyze_siv_subscript (chrec_a
, chrec_b
,
3360 overlap_iterations_a
, overlap_iterations_b
,
3364 analyze_miv_subscript (chrec_a
, chrec_b
,
3365 overlap_iterations_a
, overlap_iterations_b
,
3368 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3370 fprintf (dump_file
, " (overlap_iterations_a = ");
3371 print_generic_expr (dump_file
, *overlap_iterations_a
, 0);
3372 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
3373 print_generic_expr (dump_file
, *overlap_iterations_b
, 0);
3374 fprintf (dump_file
, ")\n");
3375 fprintf (dump_file
, ")\n");
3379 /* Helper function for uniquely inserting distance vectors. */
3382 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
3387 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, v
); i
++)
3388 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
3391 VEC_safe_push (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
), dist_v
);
3394 /* Helper function for uniquely inserting direction vectors. */
3397 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
3402 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), i
, v
); i
++)
3403 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
3406 VEC_safe_push (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
), dir_v
);
3409 /* Add a distance of 1 on all the loops outer than INDEX. If we
3410 haven't yet determined a distance for this outer loop, push a new
3411 distance vector composed of the previous distance, and a distance
3412 of 1 for this outer loop. Example:
3420 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
3421 save (0, 1), then we have to save (1, 0). */
3424 add_outer_distances (struct data_dependence_relation
*ddr
,
3425 lambda_vector dist_v
, int index
)
3427 /* For each outer loop where init_v is not set, the accesses are
3428 in dependence of distance 1 in the loop. */
3429 while (--index
>= 0)
3431 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3432 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3434 save_dist_v (ddr
, save_v
);
3438 /* Return false when fail to represent the data dependence as a
3439 distance vector. INIT_B is set to true when a component has been
3440 added to the distance vector DIST_V. INDEX_CARRY is then set to
3441 the index in DIST_V that carries the dependence. */
3444 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
3445 struct data_reference
*ddr_a
,
3446 struct data_reference
*ddr_b
,
3447 lambda_vector dist_v
, bool *init_b
,
3451 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3453 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3455 tree access_fn_a
, access_fn_b
;
3456 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
3458 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
3460 non_affine_dependence_relation (ddr
);
3464 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
3465 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
3467 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
3468 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
3471 int index_a
= index_in_loop_nest (CHREC_VARIABLE (access_fn_a
),
3472 DDR_LOOP_NEST (ddr
));
3473 int index_b
= index_in_loop_nest (CHREC_VARIABLE (access_fn_b
),
3474 DDR_LOOP_NEST (ddr
));
3476 /* The dependence is carried by the outermost loop. Example:
3483 In this case, the dependence is carried by loop_1. */
3484 index
= index_a
< index_b
? index_a
: index_b
;
3485 *index_carry
= MIN (index
, *index_carry
);
3487 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
3489 non_affine_dependence_relation (ddr
);
3493 dist
= int_cst_value (SUB_DISTANCE (subscript
));
3495 /* This is the subscript coupling test. If we have already
3496 recorded a distance for this loop (a distance coming from
3497 another subscript), it should be the same. For example,
3498 in the following code, there is no dependence:
3505 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
3507 finalize_ddr_dependent (ddr
, chrec_known
);
3511 dist_v
[index
] = dist
;
3517 /* This can be for example an affine vs. constant dependence
3518 (T[i] vs. T[3]) that is not an affine dependence and is
3519 not representable as a distance vector. */
3520 non_affine_dependence_relation (ddr
);
3528 /* Return true when the DDR contains two data references that have the
3529 same access functions. */
3532 same_access_functions (struct data_dependence_relation
*ddr
)
3536 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3537 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr
), i
),
3538 DR_ACCESS_FN (DDR_B (ddr
), i
)))
3544 /* Helper function for the case where DDR_A and DDR_B are the same
3545 multivariate access function. */
3548 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
3551 tree c_1
= CHREC_LEFT (c_2
);
3552 tree c_0
= CHREC_LEFT (c_1
);
3553 lambda_vector dist_v
;
3555 /* Polynomials with more than 2 variables are not handled yet. */
3556 if (TREE_CODE (c_0
) != INTEGER_CST
)
3558 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
3562 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
3563 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
3565 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3566 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3567 dist_v
[x_1
] = int_cst_value (CHREC_RIGHT (c_2
));
3568 dist_v
[x_2
] = -int_cst_value (CHREC_RIGHT (c_1
));
3569 save_dist_v (ddr
, dist_v
);
3571 add_outer_distances (ddr
, dist_v
, x_1
);
3574 /* Helper function for the case where DDR_A and DDR_B are the same
3575 access functions. */
3578 add_other_self_distances (struct data_dependence_relation
*ddr
)
3580 lambda_vector dist_v
;
3582 int index_carry
= DDR_NB_LOOPS (ddr
);
3584 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3586 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
3588 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
3590 if (!evolution_function_is_univariate_p (access_fun
))
3592 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
3594 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
3598 add_multivariate_self_dist (ddr
, DR_ACCESS_FN (DDR_A (ddr
), 0));
3602 index_carry
= MIN (index_carry
,
3603 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
3604 DDR_LOOP_NEST (ddr
)));
3608 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3609 add_outer_distances (ddr
, dist_v
, index_carry
);
3612 /* Compute the classic per loop distance vector. DDR is the data
3613 dependence relation to build a vector from. Return false when fail
3614 to represent the data dependence as a distance vector. */
3617 build_classic_dist_vector (struct data_dependence_relation
*ddr
)
3619 bool init_b
= false;
3620 int index_carry
= DDR_NB_LOOPS (ddr
);
3621 lambda_vector dist_v
;
3623 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3626 if (same_access_functions (ddr
))
3628 /* Save the 0 vector. */
3629 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3630 save_dist_v (ddr
, dist_v
);
3632 if (DDR_NB_LOOPS (ddr
) > 1)
3633 add_other_self_distances (ddr
);
3638 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3639 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
3640 dist_v
, &init_b
, &index_carry
))
3643 /* Save the distance vector if we initialized one. */
3646 /* Verify a basic constraint: classic distance vectors should
3647 always be lexicographically positive.
3649 Data references are collected in the order of execution of
3650 the program, thus for the following loop
3652 | for (i = 1; i < 100; i++)
3653 | for (j = 1; j < 100; j++)
3655 | t = T[j+1][i-1]; // A
3656 | T[j][i] = t + 2; // B
3659 references are collected following the direction of the wind:
3660 A then B. The data dependence tests are performed also
3661 following this order, such that we're looking at the distance
3662 separating the elements accessed by A from the elements later
3663 accessed by B. But in this example, the distance returned by
3664 test_dep (A, B) is lexicographically negative (-1, 1), that
3665 means that the access A occurs later than B with respect to
3666 the outer loop, ie. we're actually looking upwind. In this
3667 case we solve test_dep (B, A) looking downwind to the
3668 lexicographically positive solution, that returns the
3669 distance vector (1, -1). */
3670 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
3672 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3673 subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
));
3674 compute_subscript_distance (ddr
);
3675 build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3676 save_v
, &init_b
, &index_carry
);
3677 save_dist_v (ddr
, save_v
);
3679 /* In this case there is a dependence forward for all the
3682 | for (k = 1; k < 100; k++)
3683 | for (i = 1; i < 100; i++)
3684 | for (j = 1; j < 100; j++)
3686 | t = T[j+1][i-1]; // A
3687 | T[j][i] = t + 2; // B
3695 if (DDR_NB_LOOPS (ddr
) > 1)
3697 add_outer_distances (ddr
, save_v
, index_carry
);
3698 add_outer_distances (ddr
, dist_v
, index_carry
);
3703 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3704 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3705 save_dist_v (ddr
, save_v
);
3707 if (DDR_NB_LOOPS (ddr
) > 1)
3709 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3711 subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
));
3712 compute_subscript_distance (ddr
);
3713 build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3714 opposite_v
, &init_b
, &index_carry
);
3716 add_outer_distances (ddr
, dist_v
, index_carry
);
3717 add_outer_distances (ddr
, opposite_v
, index_carry
);
3723 /* There is a distance of 1 on all the outer loops: Example:
3724 there is a dependence of distance 1 on loop_1 for the array A.
3730 add_outer_distances (ddr
, dist_v
,
3731 lambda_vector_first_nz (dist_v
,
3732 DDR_NB_LOOPS (ddr
), 0));
3735 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3739 fprintf (dump_file
, "(build_classic_dist_vector\n");
3740 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3742 fprintf (dump_file
, " dist_vector = (");
3743 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3744 DDR_NB_LOOPS (ddr
));
3745 fprintf (dump_file
, " )\n");
3747 fprintf (dump_file
, ")\n");
3753 /* Return the direction for a given distance.
3754 FIXME: Computing dir this way is suboptimal, since dir can catch
3755 cases that dist is unable to represent. */
3757 static inline enum data_dependence_direction
3758 dir_from_dist (int dist
)
3761 return dir_positive
;
3763 return dir_negative
;
3768 /* Compute the classic per loop direction vector. DDR is the data
3769 dependence relation to build a vector from. */
3772 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3775 lambda_vector dist_v
;
3777 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, dist_v
); i
++)
3779 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3781 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3782 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3784 save_dir_v (ddr
, dir_v
);
3788 /* Helper function. Returns true when there is a dependence between
3789 data references DRA and DRB. */
3792 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3793 struct data_reference
*dra
,
3794 struct data_reference
*drb
)
3797 tree last_conflicts
;
3798 struct subscript
*subscript
;
3800 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3803 tree overlaps_a
, overlaps_b
;
3805 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3806 DR_ACCESS_FN (drb
, i
),
3807 &overlaps_a
, &overlaps_b
,
3810 if (chrec_contains_undetermined (overlaps_a
)
3811 || chrec_contains_undetermined (overlaps_b
))
3813 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3814 dependence_stats
.num_dependence_undetermined
++;
3818 else if (overlaps_a
== chrec_known
3819 || overlaps_b
== chrec_known
)
3821 finalize_ddr_dependent (ddr
, chrec_known
);
3822 dependence_stats
.num_dependence_independent
++;
3828 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3829 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3830 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3837 /* Computes the conflicting iterations, and initialize DDR. */
3840 subscript_dependence_tester (struct data_dependence_relation
*ddr
)
3843 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3844 fprintf (dump_file
, "(subscript_dependence_tester \n");
3846 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
)))
3847 dependence_stats
.num_dependence_dependent
++;
3849 compute_subscript_distance (ddr
);
3850 if (build_classic_dist_vector (ddr
))
3851 build_classic_dir_vector (ddr
);
3853 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3854 fprintf (dump_file
, ")\n");
3857 /* Returns true when all the access functions of A are affine or
3861 access_functions_are_affine_or_constant_p (struct data_reference
*a
)
3864 VEC(tree
,heap
) **fns
= DR_ACCESS_FNS_ADDR (a
);
3867 for (i
= 0; VEC_iterate (tree
, *fns
, i
, t
); i
++)
3868 if (!evolution_function_is_constant_p (t
)
3869 && !evolution_function_is_affine_multivariate_p (t
))
3875 /* This computes the affine dependence relation between A and B.
3876 CHREC_KNOWN is used for representing the independence between two
3877 accesses, while CHREC_DONT_KNOW is used for representing the unknown
3880 Note that it is possible to stop the computation of the dependence
3881 relation the first time we detect a CHREC_KNOWN element for a given
3885 compute_affine_dependence (struct data_dependence_relation
*ddr
)
3887 struct data_reference
*dra
= DDR_A (ddr
);
3888 struct data_reference
*drb
= DDR_B (ddr
);
3890 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3892 fprintf (dump_file
, "(compute_affine_dependence\n");
3893 fprintf (dump_file
, " (stmt_a = \n");
3894 print_generic_expr (dump_file
, DR_STMT (dra
), 0);
3895 fprintf (dump_file
, ")\n (stmt_b = \n");
3896 print_generic_expr (dump_file
, DR_STMT (drb
), 0);
3897 fprintf (dump_file
, ")\n");
3900 /* Analyze only when the dependence relation is not yet known. */
3901 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
3903 dependence_stats
.num_dependence_tests
++;
3905 if (access_functions_are_affine_or_constant_p (dra
)
3906 && access_functions_are_affine_or_constant_p (drb
))
3907 subscript_dependence_tester (ddr
);
3909 /* As a last case, if the dependence cannot be determined, or if
3910 the dependence is considered too difficult to determine, answer
3914 dependence_stats
.num_dependence_undetermined
++;
3916 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3918 fprintf (dump_file
, "Data ref a:\n");
3919 dump_data_reference (dump_file
, dra
);
3920 fprintf (dump_file
, "Data ref b:\n");
3921 dump_data_reference (dump_file
, drb
);
3922 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
3924 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3928 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3929 fprintf (dump_file
, ")\n");
3932 /* This computes the dependence relation for the same data
3933 reference into DDR. */
3936 compute_self_dependence (struct data_dependence_relation
*ddr
)
3939 struct subscript
*subscript
;
3941 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3944 /* The accessed index overlaps for each iteration. */
3945 SUB_CONFLICTS_IN_A (subscript
) = integer_zero_node
;
3946 SUB_CONFLICTS_IN_B (subscript
) = integer_zero_node
;
3947 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
3950 /* The distance vector is the zero vector. */
3951 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3952 save_dir_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
3955 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3956 the data references in DATAREFS, in the LOOP_NEST. When
3957 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3961 compute_all_dependences (VEC (data_reference_p
, heap
) *datarefs
,
3962 VEC (ddr_p
, heap
) **dependence_relations
,
3963 VEC (loop_p
, heap
) *loop_nest
,
3964 bool compute_self_and_rr
)
3966 struct data_dependence_relation
*ddr
;
3967 struct data_reference
*a
, *b
;
3970 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
3971 for (j
= i
+ 1; VEC_iterate (data_reference_p
, datarefs
, j
, b
); j
++)
3972 if (!DR_IS_READ (a
) || !DR_IS_READ (b
) || compute_self_and_rr
)
3974 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
3975 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
3976 compute_affine_dependence (ddr
);
3979 if (compute_self_and_rr
)
3980 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
3982 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
3983 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
3984 compute_self_dependence (ddr
);
3988 /* Search the data references in LOOP, and record the information into
3989 DATAREFS. Returns chrec_dont_know when failing to analyze a
3990 difficult case, returns NULL_TREE otherwise.
3992 TODO: This function should be made smarter so that it can handle address
3993 arithmetic as if they were array accesses, etc. */
3996 find_data_references_in_loop (struct loop
*loop
,
3997 VEC (data_reference_p
, heap
) **datarefs
)
3999 basic_block bb
, *bbs
;
4001 block_stmt_iterator bsi
;
4002 struct data_reference
*dr
;
4004 bbs
= get_loop_body (loop
);
4006 for (i
= 0; i
< loop
->num_nodes
; i
++)
4010 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4012 tree stmt
= bsi_stmt (bsi
);
4014 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4015 Calls have side-effects, except those to const or pure
4017 if ((TREE_CODE (stmt
) == CALL_EXPR
4018 && !(call_expr_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
4019 || (TREE_CODE (stmt
) == ASM_EXPR
4020 && ASM_VOLATILE_P (stmt
)))
4021 goto insert_dont_know_node
;
4023 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
4026 switch (TREE_CODE (stmt
))
4030 bool one_inserted
= false;
4031 tree opnd0
= TREE_OPERAND (stmt
, 0);
4032 tree opnd1
= TREE_OPERAND (stmt
, 1);
4034 if (TREE_CODE (opnd0
) == ARRAY_REF
4035 || TREE_CODE (opnd0
) == INDIRECT_REF
4036 || TREE_CODE (opnd0
) == COMPONENT_REF
)
4038 dr
= create_data_ref (opnd0
, stmt
, false);
4041 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4042 one_inserted
= true;
4046 if (TREE_CODE (opnd1
) == ARRAY_REF
4047 || TREE_CODE (opnd1
) == INDIRECT_REF
4048 || TREE_CODE (opnd1
) == COMPONENT_REF
)
4050 dr
= create_data_ref (opnd1
, stmt
, true);
4053 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4054 one_inserted
= true;
4059 goto insert_dont_know_node
;
4067 bool one_inserted
= false;
4069 for (args
= TREE_OPERAND (stmt
, 1); args
;
4070 args
= TREE_CHAIN (args
))
4071 if (TREE_CODE (TREE_VALUE (args
)) == ARRAY_REF
4072 || TREE_CODE (TREE_VALUE (args
)) == INDIRECT_REF
4073 || TREE_CODE (TREE_VALUE (args
)) == COMPONENT_REF
)
4075 dr
= create_data_ref (TREE_VALUE (args
), stmt
, true);
4078 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4079 one_inserted
= true;
4084 goto insert_dont_know_node
;
4091 struct data_reference
*res
;
4093 insert_dont_know_node
:;
4094 res
= XNEW (struct data_reference
);
4095 DR_STMT (res
) = NULL_TREE
;
4096 DR_REF (res
) = NULL_TREE
;
4097 DR_BASE_OBJECT (res
) = NULL
;
4098 DR_TYPE (res
) = ARRAY_REF_TYPE
;
4099 DR_SET_ACCESS_FNS (res
, NULL
);
4100 DR_BASE_OBJECT (res
) = NULL
;
4101 DR_IS_READ (res
) = false;
4102 DR_BASE_ADDRESS (res
) = NULL_TREE
;
4103 DR_OFFSET (res
) = NULL_TREE
;
4104 DR_INIT (res
) = NULL_TREE
;
4105 DR_STEP (res
) = NULL_TREE
;
4106 DR_OFFSET_MISALIGNMENT (res
) = NULL_TREE
;
4107 DR_MEMTAG (res
) = NULL_TREE
;
4108 DR_PTR_INFO (res
) = NULL
;
4109 VEC_safe_push (data_reference_p
, heap
, *datarefs
, res
);
4112 return chrec_dont_know
;
4116 /* When there are no defs in the loop, the loop is parallel. */
4117 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_VIRTUAL_DEFS
))
4118 loop
->parallel_p
= false;
4127 /* Recursive helper function. */
4130 find_loop_nest_1 (struct loop
*loop
, VEC (loop_p
, heap
) *loop_nest
)
4132 /* Inner loops of the nest should not contain siblings. Example:
4133 when there are two consecutive loops,
4144 the dependence relation cannot be captured by the distance
4149 VEC_safe_push (loop_p
, heap
, loop_nest
, loop
);
4151 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4155 /* Return false when the LOOP is not well nested. Otherwise return
4156 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4157 contain the loops from the outermost to the innermost, as they will
4158 appear in the classic distance vector. */
4161 find_loop_nest (struct loop
*loop
, VEC (loop_p
, heap
) *loop_nest
)
4163 VEC_safe_push (loop_p
, heap
, loop_nest
, loop
);
4165 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4169 /* Given a loop nest LOOP, the following vectors are returned:
4170 DATAREFS is initialized to all the array elements contained in this loop,
4171 DEPENDENCE_RELATIONS contains the relations between the data references.
4172 Compute read-read and self relations if
4173 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4176 compute_data_dependences_for_loop (struct loop
*loop
,
4177 bool compute_self_and_read_read_dependences
,
4178 VEC (data_reference_p
, heap
) **datarefs
,
4179 VEC (ddr_p
, heap
) **dependence_relations
)
4181 struct loop
*loop_nest
= loop
;
4182 VEC (loop_p
, heap
) *vloops
= VEC_alloc (loop_p
, heap
, 3);
4184 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4186 /* If the loop nest is not well formed, or one of the data references
4187 is not computable, give up without spending time to compute other
4190 || !find_loop_nest (loop_nest
, vloops
)
4191 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
4193 struct data_dependence_relation
*ddr
;
4195 /* Insert a single relation into dependence_relations:
4197 ddr
= initialize_data_dependence_relation (NULL
, NULL
, vloops
);
4198 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4201 compute_all_dependences (*datarefs
, dependence_relations
, vloops
,
4202 compute_self_and_read_read_dependences
);
4204 if (dump_file
&& (dump_flags
& TDF_STATS
))
4206 fprintf (dump_file
, "Dependence tester statistics:\n");
4208 fprintf (dump_file
, "Number of dependence tests: %d\n",
4209 dependence_stats
.num_dependence_tests
);
4210 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4211 dependence_stats
.num_dependence_dependent
);
4212 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4213 dependence_stats
.num_dependence_independent
);
4214 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4215 dependence_stats
.num_dependence_undetermined
);
4217 fprintf (dump_file
, "Number of subscript tests: %d\n",
4218 dependence_stats
.num_subscript_tests
);
4219 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4220 dependence_stats
.num_subscript_undetermined
);
4221 fprintf (dump_file
, "Number of same subscript function: %d\n",
4222 dependence_stats
.num_same_subscript_function
);
4224 fprintf (dump_file
, "Number of ziv tests: %d\n",
4225 dependence_stats
.num_ziv
);
4226 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4227 dependence_stats
.num_ziv_dependent
);
4228 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4229 dependence_stats
.num_ziv_independent
);
4230 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4231 dependence_stats
.num_ziv_unimplemented
);
4233 fprintf (dump_file
, "Number of siv tests: %d\n",
4234 dependence_stats
.num_siv
);
4235 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4236 dependence_stats
.num_siv_dependent
);
4237 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4238 dependence_stats
.num_siv_independent
);
4239 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4240 dependence_stats
.num_siv_unimplemented
);
4242 fprintf (dump_file
, "Number of miv tests: %d\n",
4243 dependence_stats
.num_miv
);
4244 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4245 dependence_stats
.num_miv_dependent
);
4246 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4247 dependence_stats
.num_miv_independent
);
4248 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4249 dependence_stats
.num_miv_unimplemented
);
4253 /* Entry point (for testing only). Analyze all the data references
4254 and the dependence relations.
4256 The data references are computed first.
4258 A relation on these nodes is represented by a complete graph. Some
4259 of the relations could be of no interest, thus the relations can be
4262 In the following function we compute all the relations. This is
4263 just a first implementation that is here for:
4264 - for showing how to ask for the dependence relations,
4265 - for the debugging the whole dependence graph,
4266 - for the dejagnu testcases and maintenance.
4268 It is possible to ask only for a part of the graph, avoiding to
4269 compute the whole dependence graph. The computed dependences are
4270 stored in a knowledge base (KB) such that later queries don't
4271 recompute the same information. The implementation of this KB is
4272 transparent to the optimizer, and thus the KB can be changed with a
4273 more efficient implementation, or the KB could be disabled. */
4276 analyze_all_data_dependences (struct loops
*loops
)
4279 int nb_data_refs
= 10;
4280 VEC (data_reference_p
, heap
) *datarefs
=
4281 VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4282 VEC (ddr_p
, heap
) *dependence_relations
=
4283 VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
);
4285 /* Compute DDs on the whole function. */
4286 compute_data_dependences_for_loop (loops
->parray
[0], false,
4287 &datarefs
, &dependence_relations
);
4291 dump_data_dependence_relations (dump_file
, dependence_relations
);
4292 fprintf (dump_file
, "\n\n");
4294 if (dump_flags
& TDF_DETAILS
)
4295 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4297 if (dump_flags
& TDF_STATS
)
4299 unsigned nb_top_relations
= 0;
4300 unsigned nb_bot_relations
= 0;
4301 unsigned nb_basename_differ
= 0;
4302 unsigned nb_chrec_relations
= 0;
4303 struct data_dependence_relation
*ddr
;
4305 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4307 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4310 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4312 struct data_reference
*a
= DDR_A (ddr
);
4313 struct data_reference
*b
= DDR_B (ddr
);
4316 if ((DR_BASE_OBJECT (a
) && DR_BASE_OBJECT (b
)
4317 && DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
))
4318 || (base_object_differ_p (a
, b
, &differ_p
)
4320 nb_basename_differ
++;
4326 nb_chrec_relations
++;
4329 gather_stats_on_scev_database ();
4333 free_dependence_relations (dependence_relations
);
4334 free_data_refs (datarefs
);
4338 /* Free the memory used by a data dependence relation DDR. */
4341 free_dependence_relation (struct data_dependence_relation
*ddr
)
4346 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_SUBSCRIPTS (ddr
))
4347 VEC_free (subscript_p
, heap
, DDR_SUBSCRIPTS (ddr
));
4352 /* Free the memory used by the data dependence relations from
4353 DEPENDENCE_RELATIONS. */
4356 free_dependence_relations (VEC (ddr_p
, heap
) *dependence_relations
)
4359 struct data_dependence_relation
*ddr
;
4361 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4362 free_dependence_relation (ddr
);
4364 VEC_free (ddr_p
, heap
, dependence_relations
);
4367 /* Free the memory used by the data references from DATAREFS. */
4370 free_data_refs (VEC (data_reference_p
, heap
) *datarefs
)
4373 struct data_reference
*dr
;
4375 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
4377 if (DR_TYPE(dr
) == ARRAY_REF_TYPE
)
4378 VEC_free (tree
, heap
, (dr
)->object_info
.access_fns
);
4380 VEC_free (tree
, heap
, (dr
)->first_location
.access_fns
);
4384 VEC_free (data_reference_p
, heap
, datarefs
);