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
,
143 tree tag
= NULL_TREE
;
144 struct ptr_info_def
*pi
= DR_PTR_INFO (ptr_dr
);
146 gcc_assert (TREE_CODE (ptr
) == SSA_NAME
&& DECL_P (decl
));
149 tag
= pi
->name_mem_tag
;
151 tag
= get_var_ann (SSA_NAME_VAR (ptr
))->symbol_mem_tag
;
153 tag
= DR_MEMTAG (ptr_dr
);
157 *aliased
= is_aliased_with (tag
, decl
);
162 /* Determine if two pointers may alias, the result is put in ALIASED.
163 Return FALSE if there is no symbol memory tag for one of the pointers. */
166 ptr_ptr_may_alias_p (tree ptr_a
, tree ptr_b
,
167 struct data_reference
*dra
,
168 struct data_reference
*drb
,
171 tree tag_a
= NULL_TREE
, tag_b
= NULL_TREE
;
172 struct ptr_info_def
*pi_a
= DR_PTR_INFO (dra
);
173 struct ptr_info_def
*pi_b
= DR_PTR_INFO (drb
);
175 if (pi_a
&& pi_a
->name_mem_tag
&& pi_b
&& pi_b
->name_mem_tag
)
177 tag_a
= pi_a
->name_mem_tag
;
178 tag_b
= pi_b
->name_mem_tag
;
182 tag_a
= get_var_ann (SSA_NAME_VAR (ptr_a
))->symbol_mem_tag
;
184 tag_a
= DR_MEMTAG (dra
);
188 tag_b
= get_var_ann (SSA_NAME_VAR (ptr_b
))->symbol_mem_tag
;
190 tag_b
= DR_MEMTAG (drb
);
194 *aliased
= (tag_a
== tag_b
);
199 /* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED.
200 Return FALSE if there is no symbol memory tag for one of the symbols. */
203 may_alias_p (tree base_a
, tree base_b
,
204 struct data_reference
*dra
,
205 struct data_reference
*drb
,
208 if (TREE_CODE (base_a
) == ADDR_EXPR
|| TREE_CODE (base_b
) == ADDR_EXPR
)
210 if (TREE_CODE (base_a
) == ADDR_EXPR
&& TREE_CODE (base_b
) == ADDR_EXPR
)
212 *aliased
= (TREE_OPERAND (base_a
, 0) == TREE_OPERAND (base_b
, 0));
215 if (TREE_CODE (base_a
) == ADDR_EXPR
)
216 return ptr_decl_may_alias_p (base_b
, TREE_OPERAND (base_a
, 0), drb
,
219 return ptr_decl_may_alias_p (base_a
, TREE_OPERAND (base_b
, 0), dra
,
223 return ptr_ptr_may_alias_p (base_a
, base_b
, dra
, drb
, aliased
);
227 /* Determine if a pointer (BASE_A) and a record/union access (BASE_B)
228 are not aliased. Return TRUE if they differ. */
230 record_ptr_differ_p (struct data_reference
*dra
,
231 struct data_reference
*drb
)
234 tree base_a
= DR_BASE_OBJECT (dra
);
235 tree base_b
= DR_BASE_OBJECT (drb
);
237 if (TREE_CODE (base_b
) != COMPONENT_REF
)
240 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
241 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
242 Probably will be unnecessary with struct alias analysis. */
243 while (TREE_CODE (base_b
) == COMPONENT_REF
)
244 base_b
= TREE_OPERAND (base_b
, 0);
245 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
247 if (TREE_CODE (base_a
) == INDIRECT_REF
248 && ((TREE_CODE (base_b
) == VAR_DECL
249 && (ptr_decl_may_alias_p (TREE_OPERAND (base_a
, 0), base_b
, dra
,
252 || (TREE_CODE (base_b
) == INDIRECT_REF
253 && (ptr_ptr_may_alias_p (TREE_OPERAND (base_a
, 0),
254 TREE_OPERAND (base_b
, 0), dra
, drb
,
262 /* Determine if two record/union accesses are aliased. Return TRUE if they
265 record_record_differ_p (struct data_reference
*dra
,
266 struct data_reference
*drb
)
269 tree base_a
= DR_BASE_OBJECT (dra
);
270 tree base_b
= DR_BASE_OBJECT (drb
);
272 if (TREE_CODE (base_b
) != COMPONENT_REF
273 || TREE_CODE (base_a
) != COMPONENT_REF
)
276 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
277 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
278 Probably will be unnecessary with struct alias analysis. */
279 while (TREE_CODE (base_b
) == COMPONENT_REF
)
280 base_b
= TREE_OPERAND (base_b
, 0);
281 while (TREE_CODE (base_a
) == COMPONENT_REF
)
282 base_a
= TREE_OPERAND (base_a
, 0);
284 if (TREE_CODE (base_a
) == INDIRECT_REF
285 && TREE_CODE (base_b
) == INDIRECT_REF
286 && ptr_ptr_may_alias_p (TREE_OPERAND (base_a
, 0),
287 TREE_OPERAND (base_b
, 0),
295 /* Determine if an array access (BASE_A) and a record/union access (BASE_B)
296 are not aliased. Return TRUE if they differ. */
298 record_array_differ_p (struct data_reference
*dra
,
299 struct data_reference
*drb
)
302 tree base_a
= DR_BASE_OBJECT (dra
);
303 tree base_b
= DR_BASE_OBJECT (drb
);
305 if (TREE_CODE (base_b
) != COMPONENT_REF
)
308 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
309 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
310 Probably will be unnecessary with struct alias analysis. */
311 while (TREE_CODE (base_b
) == COMPONENT_REF
)
312 base_b
= TREE_OPERAND (base_b
, 0);
314 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
315 (a[i]). In case of p->c[i] use alias analysis to verify that p is not
317 if (TREE_CODE (base_a
) == VAR_DECL
318 && (TREE_CODE (base_b
) == VAR_DECL
319 || (TREE_CODE (base_b
) == INDIRECT_REF
320 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b
, 0), base_a
, drb
,
329 /* Determine if an array access (BASE_A) and a pointer (BASE_B)
330 are not aliased. Return TRUE if they differ. */
332 array_ptr_differ_p (tree base_a
, tree base_b
,
333 struct data_reference
*drb
)
337 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
338 help of alias analysis that p is not pointing to a. */
339 if (TREE_CODE (base_a
) == VAR_DECL
&& TREE_CODE (base_b
) == INDIRECT_REF
340 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b
, 0), base_a
, drb
, &aliased
)
348 /* This is the simplest data dependence test: determines whether the
349 data references A and B access the same array/region. Returns
350 false when the property is not computable at compile time.
351 Otherwise return true, and DIFFER_P will record the result. This
352 utility will not be necessary when alias_sets_conflict_p will be
353 less conservative. */
356 base_object_differ_p (struct data_reference
*a
,
357 struct data_reference
*b
,
360 tree base_a
= DR_BASE_OBJECT (a
);
361 tree base_b
= DR_BASE_OBJECT (b
);
364 if (!base_a
|| !base_b
)
367 /* Determine if same base. Example: for the array accesses
368 a[i], b[i] or pointer accesses *a, *b, bases are a, b. */
369 if (base_a
== base_b
)
375 /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
377 if (TREE_CODE (base_a
) == INDIRECT_REF
&& TREE_CODE (base_b
) == INDIRECT_REF
378 && TREE_OPERAND (base_a
, 0) == TREE_OPERAND (base_b
, 0))
384 /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */
385 if (TREE_CODE (base_a
) == COMPONENT_REF
&& TREE_CODE (base_b
) == COMPONENT_REF
386 && TREE_OPERAND (base_a
, 0) == TREE_OPERAND (base_b
, 0)
387 && TREE_OPERAND (base_a
, 1) == TREE_OPERAND (base_b
, 1))
394 /* Determine if different bases. */
396 /* At this point we know that base_a != base_b. However, pointer
397 accesses of the form x=(*p) and y=(*q), whose bases are p and q,
398 may still be pointing to the same base. In SSAed GIMPLE p and q will
399 be SSA_NAMES in this case. Therefore, here we check if they are
400 really two different declarations. */
401 if (TREE_CODE (base_a
) == VAR_DECL
&& TREE_CODE (base_b
) == VAR_DECL
)
407 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
408 help of alias analysis that p is not pointing to a. */
409 if (array_ptr_differ_p (base_a
, base_b
, b
)
410 || array_ptr_differ_p (base_b
, base_a
, a
))
416 /* If the bases are pointers ((*q)[i] and (*p)[i]), we check with the
417 help of alias analysis they don't point to the same bases. */
418 if (TREE_CODE (base_a
) == INDIRECT_REF
&& TREE_CODE (base_b
) == INDIRECT_REF
419 && (may_alias_p (TREE_OPERAND (base_a
, 0), TREE_OPERAND (base_b
, 0), a
, b
,
427 /* Compare two record/union bases s.a and t.b: s != t or (a != b and
428 s and t are not unions). */
429 if (TREE_CODE (base_a
) == COMPONENT_REF
&& TREE_CODE (base_b
) == COMPONENT_REF
430 && ((TREE_CODE (TREE_OPERAND (base_a
, 0)) == VAR_DECL
431 && TREE_CODE (TREE_OPERAND (base_b
, 0)) == VAR_DECL
432 && TREE_OPERAND (base_a
, 0) != TREE_OPERAND (base_b
, 0))
433 || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a
, 0))) == RECORD_TYPE
434 && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b
, 0))) == RECORD_TYPE
435 && TREE_OPERAND (base_a
, 1) != TREE_OPERAND (base_b
, 1))))
441 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
443 if (record_ptr_differ_p (a
, b
) || record_ptr_differ_p (b
, a
))
449 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
450 (a[i]). In case of p->c[i] use alias analysis to verify that p is not
452 if (record_array_differ_p (a
, b
) || record_array_differ_p (b
, a
))
458 /* Compare two record/union accesses (b.c[i] or p->c[i]). */
459 if (record_record_differ_p (a
, b
))
468 /* Function base_addr_differ_p.
470 This is the simplest data dependence test: determines whether the
471 data references DRA and DRB access the same array/region. Returns
472 false when the property is not computable at compile time.
473 Otherwise return true, and DIFFER_P will record the result.
476 1. if (both DRA and DRB are represented as arrays)
477 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT
478 2. else if (both DRA and DRB are represented as pointers)
479 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION
480 3. else if (DRA and DRB are represented differently or 2. fails)
481 only try to prove that the bases are surely different
485 base_addr_differ_p (struct data_reference
*dra
,
486 struct data_reference
*drb
,
489 tree addr_a
= DR_BASE_ADDRESS (dra
);
490 tree addr_b
= DR_BASE_ADDRESS (drb
);
494 if (!addr_a
|| !addr_b
)
497 type_a
= TREE_TYPE (addr_a
);
498 type_b
= TREE_TYPE (addr_b
);
500 gcc_assert (POINTER_TYPE_P (type_a
) && POINTER_TYPE_P (type_b
));
502 /* 1. if (both DRA and DRB are represented as arrays)
503 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT. */
504 if (DR_TYPE (dra
) == ARRAY_REF_TYPE
&& DR_TYPE (drb
) == ARRAY_REF_TYPE
)
505 return base_object_differ_p (dra
, drb
, differ_p
);
507 /* 2. else if (both DRA and DRB are represented as pointers)
508 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION. */
509 /* If base addresses are the same, we check the offsets, since the access of
510 the data-ref is described by {base addr + offset} and its access function,
511 i.e., in order to decide whether the bases of data-refs are the same we
512 compare both base addresses and offsets. */
513 if (DR_TYPE (dra
) == POINTER_REF_TYPE
&& DR_TYPE (drb
) == POINTER_REF_TYPE
515 || (TREE_CODE (addr_a
) == ADDR_EXPR
&& TREE_CODE (addr_b
) == ADDR_EXPR
516 && TREE_OPERAND (addr_a
, 0) == TREE_OPERAND (addr_b
, 0))))
518 /* Compare offsets. */
519 tree offset_a
= DR_OFFSET (dra
);
520 tree offset_b
= DR_OFFSET (drb
);
522 STRIP_NOPS (offset_a
);
523 STRIP_NOPS (offset_b
);
525 /* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle
527 if (offset_a
== offset_b
528 || (TREE_CODE (offset_a
) == MULT_EXPR
529 && TREE_CODE (offset_b
) == MULT_EXPR
530 && TREE_OPERAND (offset_a
, 0) == TREE_OPERAND (offset_b
, 0)
531 && TREE_OPERAND (offset_a
, 1) == TREE_OPERAND (offset_b
, 1)))
538 /* 3. else if (DRA and DRB are represented differently or 2. fails)
539 only try to prove that the bases are surely different. */
541 /* Apply alias analysis. */
542 if (may_alias_p (addr_a
, addr_b
, dra
, drb
, &aliased
) && !aliased
)
548 /* An instruction writing through a restricted pointer is "independent" of any
549 instruction reading or writing through a different pointer, in the same
551 else if ((TYPE_RESTRICT (type_a
) && !DR_IS_READ (dra
))
552 || (TYPE_RESTRICT (type_b
) && !DR_IS_READ (drb
)))
560 /* Returns true iff A divides B. */
563 tree_fold_divides_p (tree a
,
566 /* Determines whether (A == gcd (A, B)). */
567 return tree_int_cst_equal (a
, tree_fold_gcd (a
, b
));
570 /* Returns true iff A divides B. */
573 int_divides_p (int a
, int b
)
575 return ((b
% a
) == 0);
580 /* Dump into FILE all the data references from DATAREFS. */
583 dump_data_references (FILE *file
, VEC (data_reference_p
, heap
) *datarefs
)
586 struct data_reference
*dr
;
588 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
589 dump_data_reference (file
, dr
);
592 /* Dump into FILE all the dependence relations from DDRS. */
595 dump_data_dependence_relations (FILE *file
,
596 VEC (ddr_p
, heap
) *ddrs
)
599 struct data_dependence_relation
*ddr
;
601 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
602 dump_data_dependence_relation (file
, ddr
);
605 /* Dump function for a DATA_REFERENCE structure. */
608 dump_data_reference (FILE *outf
,
609 struct data_reference
*dr
)
613 fprintf (outf
, "(Data Ref: \n stmt: ");
614 print_generic_stmt (outf
, DR_STMT (dr
), 0);
615 fprintf (outf
, " ref: ");
616 print_generic_stmt (outf
, DR_REF (dr
), 0);
617 fprintf (outf
, " base_object: ");
618 print_generic_stmt (outf
, DR_BASE_OBJECT (dr
), 0);
620 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
622 fprintf (outf
, " Access function %d: ", i
);
623 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
625 fprintf (outf
, ")\n");
628 /* Dump function for a SUBSCRIPT structure. */
631 dump_subscript (FILE *outf
, struct subscript
*subscript
)
633 tree chrec
= SUB_CONFLICTS_IN_A (subscript
);
635 fprintf (outf
, "\n (subscript \n");
636 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
637 print_generic_stmt (outf
, chrec
, 0);
638 if (chrec
== chrec_known
)
639 fprintf (outf
, " (no dependence)\n");
640 else if (chrec_contains_undetermined (chrec
))
641 fprintf (outf
, " (don't know)\n");
644 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
645 fprintf (outf
, " last_conflict: ");
646 print_generic_stmt (outf
, last_iteration
, 0);
649 chrec
= SUB_CONFLICTS_IN_B (subscript
);
650 fprintf (outf
, " iterations_that_access_an_element_twice_in_B: ");
651 print_generic_stmt (outf
, chrec
, 0);
652 if (chrec
== chrec_known
)
653 fprintf (outf
, " (no dependence)\n");
654 else if (chrec_contains_undetermined (chrec
))
655 fprintf (outf
, " (don't know)\n");
658 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
659 fprintf (outf
, " last_conflict: ");
660 print_generic_stmt (outf
, last_iteration
, 0);
663 fprintf (outf
, " (Subscript distance: ");
664 print_generic_stmt (outf
, SUB_DISTANCE (subscript
), 0);
665 fprintf (outf
, " )\n");
666 fprintf (outf
, " )\n");
669 /* Print the classic direction vector DIRV to OUTF. */
672 print_direction_vector (FILE *outf
,
678 for (eq
= 0; eq
< length
; eq
++)
680 enum data_dependence_direction dir
= dirv
[eq
];
685 fprintf (outf
, " +");
688 fprintf (outf
, " -");
691 fprintf (outf
, " =");
693 case dir_positive_or_equal
:
694 fprintf (outf
, " +=");
696 case dir_positive_or_negative
:
697 fprintf (outf
, " +-");
699 case dir_negative_or_equal
:
700 fprintf (outf
, " -=");
703 fprintf (outf
, " *");
706 fprintf (outf
, "indep");
710 fprintf (outf
, "\n");
713 /* Print a vector of direction vectors. */
716 print_dir_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dir_vects
,
722 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, v
); j
++)
723 print_direction_vector (outf
, v
, length
);
726 /* Print a vector of distance vectors. */
729 print_dist_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dist_vects
,
735 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, v
); j
++)
736 print_lambda_vector (outf
, v
, length
);
742 debug_data_dependence_relation (struct data_dependence_relation
*ddr
)
744 dump_data_dependence_relation (stderr
, ddr
);
747 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
750 dump_data_dependence_relation (FILE *outf
,
751 struct data_dependence_relation
*ddr
)
753 struct data_reference
*dra
, *drb
;
757 fprintf (outf
, "(Data Dep: \n");
758 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
759 fprintf (outf
, " (don't know)\n");
761 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
762 fprintf (outf
, " (no dependence)\n");
764 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
769 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
771 fprintf (outf
, " access_fn_A: ");
772 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
773 fprintf (outf
, " access_fn_B: ");
774 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
775 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
778 fprintf (outf
, " loop nest: (");
779 for (i
= 0; VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
780 fprintf (outf
, "%d ", loopi
->num
);
781 fprintf (outf
, ")\n");
783 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
785 fprintf (outf
, " distance_vector: ");
786 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
, i
),
790 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
792 fprintf (outf
, " direction_vector: ");
793 print_direction_vector (outf
, DDR_DIR_VECT (ddr
, i
),
798 fprintf (outf
, ")\n");
801 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
804 dump_data_dependence_direction (FILE *file
,
805 enum data_dependence_direction dir
)
821 case dir_positive_or_negative
:
822 fprintf (file
, "+-");
825 case dir_positive_or_equal
:
826 fprintf (file
, "+=");
829 case dir_negative_or_equal
:
830 fprintf (file
, "-=");
842 /* Dumps the distance and direction vectors in FILE. DDRS contains
843 the dependence relations, and VECT_SIZE is the size of the
844 dependence vectors, or in other words the number of loops in the
848 dump_dist_dir_vectors (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
851 struct data_dependence_relation
*ddr
;
854 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
855 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
857 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), j
, v
); j
++)
859 fprintf (file
, "DISTANCE_V (");
860 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
861 fprintf (file
, ")\n");
864 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), j
, v
); j
++)
866 fprintf (file
, "DIRECTION_V (");
867 print_direction_vector (file
, v
, DDR_NB_LOOPS (ddr
));
868 fprintf (file
, ")\n");
872 fprintf (file
, "\n\n");
875 /* Dumps the data dependence relations DDRS in FILE. */
878 dump_ddrs (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
881 struct data_dependence_relation
*ddr
;
883 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
884 dump_data_dependence_relation (file
, ddr
);
886 fprintf (file
, "\n\n");
891 /* Estimate the number of iterations from the size of the data and the
895 estimate_niter_from_size_of_data (struct loop
*loop
,
900 tree estimation
= NULL_TREE
;
901 tree array_size
, data_size
, element_size
;
904 init
= initial_condition (access_fn
);
905 step
= evolution_part_in_loop_num (access_fn
, loop
->num
);
907 array_size
= TYPE_SIZE (TREE_TYPE (opnd0
));
908 element_size
= TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0
)));
909 if (array_size
== NULL_TREE
910 || TREE_CODE (array_size
) != INTEGER_CST
911 || TREE_CODE (element_size
) != INTEGER_CST
)
914 data_size
= fold_build2 (EXACT_DIV_EXPR
, integer_type_node
,
915 array_size
, element_size
);
917 if (init
!= NULL_TREE
919 && TREE_CODE (init
) == INTEGER_CST
920 && TREE_CODE (step
) == INTEGER_CST
)
922 tree i_plus_s
= fold_build2 (PLUS_EXPR
, integer_type_node
, init
, step
);
923 tree sign
= fold_binary (GT_EXPR
, boolean_type_node
, i_plus_s
, init
);
925 if (sign
== boolean_true_node
)
926 estimation
= fold_build2 (CEIL_DIV_EXPR
, integer_type_node
,
927 fold_build2 (MINUS_EXPR
, integer_type_node
,
928 data_size
, init
), step
);
930 /* When the step is negative, as in PR23386: (init = 3, step =
931 0ffffffff, data_size = 100), we have to compute the
932 estimation as ceil_div (init, 0 - step) + 1. */
933 else if (sign
== boolean_false_node
)
935 fold_build2 (PLUS_EXPR
, integer_type_node
,
936 fold_build2 (CEIL_DIV_EXPR
, integer_type_node
,
938 fold_build2 (MINUS_EXPR
, unsigned_type_node
,
939 integer_zero_node
, step
)),
943 record_estimate (loop
, estimation
, boolean_true_node
, stmt
);
947 /* Given an ARRAY_REF node REF, records its access functions.
948 Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
949 i.e. the constant "3", then recursively call the function on opnd0,
950 i.e. the ARRAY_REF "A[i]".
951 If ESTIMATE_ONLY is true, we just set the estimated number of loop
952 iterations, we don't store the access function.
953 The function returns the base name: "A". */
956 analyze_array_indexes (struct loop
*loop
,
957 VEC(tree
,heap
) **access_fns
,
964 opnd0
= TREE_OPERAND (ref
, 0);
965 opnd1
= TREE_OPERAND (ref
, 1);
967 /* The detection of the evolution function for this data access is
968 postponed until the dependence test. This lazy strategy avoids
969 the computation of access functions that are of no interest for
971 access_fn
= instantiate_parameters
972 (loop
, analyze_scalar_evolution (loop
, opnd1
));
975 && chrec_contains_undetermined (loop
->estimated_nb_iterations
))
976 estimate_niter_from_size_of_data (loop
, opnd0
, access_fn
, stmt
);
979 VEC_safe_push (tree
, heap
, *access_fns
, access_fn
);
981 /* Recursively record other array access functions. */
982 if (TREE_CODE (opnd0
) == ARRAY_REF
)
983 return analyze_array_indexes (loop
, access_fns
, opnd0
, stmt
, estimate_only
);
985 /* Return the base name of the data access. */
990 /* For an array reference REF contained in STMT, attempt to bound the
991 number of iterations in the loop containing STMT */
994 estimate_iters_using_array (tree stmt
, tree ref
)
996 analyze_array_indexes (loop_containing_stmt (stmt
), NULL
, ref
, stmt
,
1000 /* For a data reference REF contained in the statement STMT, initialize
1001 a DATA_REFERENCE structure, and return it. IS_READ flag has to be
1002 set to true when REF is in the right hand side of an
1005 struct data_reference
*
1006 analyze_array (tree stmt
, tree ref
, bool is_read
)
1008 struct data_reference
*res
;
1009 VEC(tree
,heap
) *acc_fns
;
1011 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1013 fprintf (dump_file
, "(analyze_array \n");
1014 fprintf (dump_file
, " (ref = ");
1015 print_generic_stmt (dump_file
, ref
, 0);
1016 fprintf (dump_file
, ")\n");
1019 res
= XNEW (struct data_reference
);
1021 DR_STMT (res
) = stmt
;
1023 acc_fns
= VEC_alloc (tree
, heap
, 3);
1024 DR_BASE_OBJECT (res
) = analyze_array_indexes
1025 (loop_containing_stmt (stmt
), &acc_fns
, ref
, stmt
, false);
1026 DR_TYPE (res
) = ARRAY_REF_TYPE
;
1027 DR_SET_ACCESS_FNS (res
, acc_fns
);
1028 DR_IS_READ (res
) = is_read
;
1029 DR_BASE_ADDRESS (res
) = NULL_TREE
;
1030 DR_OFFSET (res
) = NULL_TREE
;
1031 DR_INIT (res
) = NULL_TREE
;
1032 DR_STEP (res
) = NULL_TREE
;
1033 DR_OFFSET_MISALIGNMENT (res
) = NULL_TREE
;
1034 DR_MEMTAG (res
) = NULL_TREE
;
1035 DR_PTR_INFO (res
) = NULL
;
1037 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1038 fprintf (dump_file
, ")\n");
1043 /* Analyze an indirect memory reference, REF, that comes from STMT.
1044 IS_READ is true if this is an indirect load, and false if it is
1046 Return a new data reference structure representing the indirect_ref, or
1047 NULL if we cannot describe the access function. */
1049 static struct data_reference
*
1050 analyze_indirect_ref (tree stmt
, tree ref
, bool is_read
)
1052 struct loop
*loop
= loop_containing_stmt (stmt
);
1053 tree ptr_ref
= TREE_OPERAND (ref
, 0);
1054 tree access_fn
= analyze_scalar_evolution (loop
, ptr_ref
);
1055 tree init
= initial_condition_in_loop_num (access_fn
, loop
->num
);
1056 tree base_address
= NULL_TREE
, evolution
, step
= NULL_TREE
;
1057 struct ptr_info_def
*ptr_info
= NULL
;
1059 if (TREE_CODE (ptr_ref
) == SSA_NAME
)
1060 ptr_info
= SSA_NAME_PTR_INFO (ptr_ref
);
1063 if (access_fn
== chrec_dont_know
|| !init
|| init
== chrec_dont_know
)
1065 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1067 fprintf (dump_file
, "\nBad access function of ptr: ");
1068 print_generic_expr (dump_file
, ref
, TDF_SLIM
);
1069 fprintf (dump_file
, "\n");
1074 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1076 fprintf (dump_file
, "\nAccess function of ptr: ");
1077 print_generic_expr (dump_file
, access_fn
, TDF_SLIM
);
1078 fprintf (dump_file
, "\n");
1081 if (!expr_invariant_in_loop_p (loop
, init
))
1083 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1084 fprintf (dump_file
, "\ninitial condition is not loop invariant.\n");
1088 base_address
= init
;
1089 evolution
= evolution_part_in_loop_num (access_fn
, loop
->num
);
1090 if (evolution
!= chrec_dont_know
)
1093 step
= ssize_int (0);
1096 if (TREE_CODE (evolution
) == INTEGER_CST
)
1097 step
= fold_convert (ssizetype
, evolution
);
1099 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1100 fprintf (dump_file
, "\nnon constant step for ptr access.\n");
1104 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1105 fprintf (dump_file
, "\nunknown evolution of ptr.\n");
1107 return init_data_ref (stmt
, ref
, NULL_TREE
, access_fn
, is_read
, base_address
,
1108 NULL_TREE
, step
, NULL_TREE
, NULL_TREE
,
1109 ptr_info
, POINTER_REF_TYPE
);
1112 /* For a data reference REF contained in the statement STMT, initialize
1113 a DATA_REFERENCE structure, and return it. */
1115 struct data_reference
*
1116 init_data_ref (tree stmt
,
1126 struct ptr_info_def
*ptr_info
,
1127 enum data_ref_type type
)
1129 struct data_reference
*res
;
1130 VEC(tree
,heap
) *acc_fns
;
1132 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1134 fprintf (dump_file
, "(init_data_ref \n");
1135 fprintf (dump_file
, " (ref = ");
1136 print_generic_stmt (dump_file
, ref
, 0);
1137 fprintf (dump_file
, ")\n");
1140 res
= XNEW (struct data_reference
);
1142 DR_STMT (res
) = stmt
;
1144 DR_BASE_OBJECT (res
) = base
;
1145 DR_TYPE (res
) = type
;
1146 acc_fns
= VEC_alloc (tree
, heap
, 3);
1147 DR_SET_ACCESS_FNS (res
, acc_fns
);
1148 VEC_quick_push (tree
, DR_ACCESS_FNS (res
), access_fn
);
1149 DR_IS_READ (res
) = is_read
;
1150 DR_BASE_ADDRESS (res
) = base_address
;
1151 DR_OFFSET (res
) = init_offset
;
1152 DR_INIT (res
) = NULL_TREE
;
1153 DR_STEP (res
) = step
;
1154 DR_OFFSET_MISALIGNMENT (res
) = misalign
;
1155 DR_MEMTAG (res
) = memtag
;
1156 DR_PTR_INFO (res
) = ptr_info
;
1158 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1159 fprintf (dump_file
, ")\n");
1164 /* Function strip_conversions
1166 Strip conversions that don't narrow the mode. */
1169 strip_conversion (tree expr
)
1171 tree to
, ti
, oprnd0
;
1173 while (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
)
1175 to
= TREE_TYPE (expr
);
1176 oprnd0
= TREE_OPERAND (expr
, 0);
1177 ti
= TREE_TYPE (oprnd0
);
1179 if (!INTEGRAL_TYPE_P (to
) || !INTEGRAL_TYPE_P (ti
))
1181 if (GET_MODE_SIZE (TYPE_MODE (to
)) < GET_MODE_SIZE (TYPE_MODE (ti
)))
1190 /* Function analyze_offset_expr
1192 Given an offset expression EXPR received from get_inner_reference, analyze
1193 it and create an expression for INITIAL_OFFSET by substituting the variables
1194 of EXPR with initial_condition of the corresponding access_fn in the loop.
1197 for (j = 3; j < N; j++)
1200 For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be
1201 substituted, since its access_fn in the inner loop is i. 'j' will be
1202 substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
1205 Compute MISALIGN (the misalignment of the data reference initial access from
1206 its base). Misalignment can be calculated only if all the variables can be
1207 substituted with constants, otherwise, we record maximum possible alignment
1208 in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN
1209 will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be
1210 recorded in ALIGNED_TO.
1212 STEP is an evolution of the data reference in this loop in bytes.
1213 In the above example, STEP is C_j.
1215 Return FALSE, if the analysis fails, e.g., there is no access_fn for a
1216 variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO
1217 and STEP) are NULL_TREEs. Otherwise, return TRUE.
1222 analyze_offset_expr (tree expr
,
1224 tree
*initial_offset
,
1231 tree left_offset
= ssize_int (0);
1232 tree right_offset
= ssize_int (0);
1233 tree left_misalign
= ssize_int (0);
1234 tree right_misalign
= ssize_int (0);
1235 tree left_step
= ssize_int (0);
1236 tree right_step
= ssize_int (0);
1237 enum tree_code code
;
1238 tree init
, evolution
;
1239 tree left_aligned_to
= NULL_TREE
, right_aligned_to
= NULL_TREE
;
1242 *misalign
= NULL_TREE
;
1243 *aligned_to
= NULL_TREE
;
1244 *initial_offset
= NULL_TREE
;
1246 /* Strip conversions that don't narrow the mode. */
1247 expr
= strip_conversion (expr
);
1253 if (TREE_CODE (expr
) == INTEGER_CST
)
1255 *initial_offset
= fold_convert (ssizetype
, expr
);
1256 *misalign
= fold_convert (ssizetype
, expr
);
1257 *step
= ssize_int (0);
1261 /* 2. Variable. Try to substitute with initial_condition of the corresponding
1262 access_fn in the current loop. */
1263 if (SSA_VAR_P (expr
))
1265 tree access_fn
= analyze_scalar_evolution (loop
, expr
);
1267 if (access_fn
== chrec_dont_know
)
1271 init
= initial_condition_in_loop_num (access_fn
, loop
->num
);
1272 if (!expr_invariant_in_loop_p (loop
, init
))
1273 /* Not enough information: may be not loop invariant.
1274 E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
1275 initial_condition is D, but it depends on i - loop's induction
1279 evolution
= evolution_part_in_loop_num (access_fn
, loop
->num
);
1280 if (evolution
&& TREE_CODE (evolution
) != INTEGER_CST
)
1281 /* Evolution is not constant. */
1284 if (TREE_CODE (init
) == INTEGER_CST
)
1285 *misalign
= fold_convert (ssizetype
, init
);
1287 /* Not constant, misalignment cannot be calculated. */
1288 *misalign
= NULL_TREE
;
1290 *initial_offset
= fold_convert (ssizetype
, init
);
1292 *step
= evolution
? fold_convert (ssizetype
, evolution
) : ssize_int (0);
1296 /* Recursive computation. */
1297 if (!BINARY_CLASS_P (expr
))
1299 /* We expect to get binary expressions (PLUS/MINUS and MULT). */
1300 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1302 fprintf (dump_file
, "\nNot binary expression ");
1303 print_generic_expr (dump_file
, expr
, TDF_SLIM
);
1304 fprintf (dump_file
, "\n");
1308 oprnd0
= TREE_OPERAND (expr
, 0);
1309 oprnd1
= TREE_OPERAND (expr
, 1);
1311 if (!analyze_offset_expr (oprnd0
, loop
, &left_offset
, &left_misalign
,
1312 &left_aligned_to
, &left_step
)
1313 || !analyze_offset_expr (oprnd1
, loop
, &right_offset
, &right_misalign
,
1314 &right_aligned_to
, &right_step
))
1317 /* The type of the operation: plus, minus or mult. */
1318 code
= TREE_CODE (expr
);
1322 if (TREE_CODE (right_offset
) != INTEGER_CST
)
1323 /* RIGHT_OFFSET can be not constant. For example, for arrays of variable
1325 FORNOW: We don't support such cases. */
1328 /* Strip conversions that don't narrow the mode. */
1329 left_offset
= strip_conversion (left_offset
);
1332 /* Misalignment computation. */
1333 if (SSA_VAR_P (left_offset
))
1335 /* If the left side contains variables that can't be substituted with
1336 constants, the misalignment is unknown. However, if the right side
1337 is a multiple of some alignment, we know that the expression is
1338 aligned to it. Therefore, we record such maximum possible value.
1340 *misalign
= NULL_TREE
;
1341 *aligned_to
= ssize_int (highest_pow2_factor (right_offset
));
1345 /* The left operand was successfully substituted with constant. */
1348 /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is
1350 *misalign
= size_binop (code
, left_misalign
, right_misalign
);
1351 if (left_aligned_to
&& right_aligned_to
)
1352 *aligned_to
= size_binop (MIN_EXPR
, left_aligned_to
,
1355 *aligned_to
= left_aligned_to
?
1356 left_aligned_to
: right_aligned_to
;
1359 *misalign
= NULL_TREE
;
1362 /* Step calculation. */
1363 /* Multiply the step by the right operand. */
1364 *step
= size_binop (MULT_EXPR
, left_step
, right_offset
);
1369 /* Combine the recursive calculations for step and misalignment. */
1370 *step
= size_binop (code
, left_step
, right_step
);
1372 /* Unknown alignment. */
1373 if ((!left_misalign
&& !left_aligned_to
)
1374 || (!right_misalign
&& !right_aligned_to
))
1376 *misalign
= NULL_TREE
;
1377 *aligned_to
= NULL_TREE
;
1381 if (left_misalign
&& right_misalign
)
1382 *misalign
= size_binop (code
, left_misalign
, right_misalign
);
1384 *misalign
= left_misalign
? left_misalign
: right_misalign
;
1386 if (left_aligned_to
&& right_aligned_to
)
1387 *aligned_to
= size_binop (MIN_EXPR
, left_aligned_to
, right_aligned_to
);
1389 *aligned_to
= left_aligned_to
? left_aligned_to
: right_aligned_to
;
1397 /* Compute offset. */
1398 *initial_offset
= fold_convert (ssizetype
,
1399 fold_build2 (code
, TREE_TYPE (left_offset
),
1405 /* Function address_analysis
1407 Return the BASE of the address expression EXPR.
1408 Also compute the OFFSET from BASE, MISALIGN and STEP.
1411 EXPR - the address expression that is being analyzed
1412 STMT - the statement that contains EXPR or its original memory reference
1413 IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
1414 DR - data_reference struct for the original memory reference
1417 BASE (returned value) - the base of the data reference EXPR.
1418 INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
1419 MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
1420 computation is impossible
1421 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1422 calculated (doesn't depend on variables)
1423 STEP - evolution of EXPR in the loop
1425 If something unexpected is encountered (an unsupported form of data-ref),
1426 then NULL_TREE is returned.
1430 address_analysis (tree expr
, tree stmt
, bool is_read
, struct data_reference
*dr
,
1431 tree
*offset
, tree
*misalign
, tree
*aligned_to
, tree
*step
)
1433 tree oprnd0
, oprnd1
, base_address
, offset_expr
, base_addr0
, base_addr1
;
1434 tree address_offset
= ssize_int (0), address_misalign
= ssize_int (0);
1435 tree dummy
, address_aligned_to
= NULL_TREE
;
1436 struct ptr_info_def
*dummy1
;
1439 switch (TREE_CODE (expr
))
1443 /* EXPR is of form {base +/- offset} (or {offset +/- base}). */
1444 oprnd0
= TREE_OPERAND (expr
, 0);
1445 oprnd1
= TREE_OPERAND (expr
, 1);
1447 STRIP_NOPS (oprnd0
);
1448 STRIP_NOPS (oprnd1
);
1450 /* Recursively try to find the base of the address contained in EXPR.
1451 For offset, the returned base will be NULL. */
1452 base_addr0
= address_analysis (oprnd0
, stmt
, is_read
, dr
, &address_offset
,
1453 &address_misalign
, &address_aligned_to
,
1456 base_addr1
= address_analysis (oprnd1
, stmt
, is_read
, dr
, &address_offset
,
1457 &address_misalign
, &address_aligned_to
,
1460 /* We support cases where only one of the operands contains an
1462 if ((base_addr0
&& base_addr1
) || (!base_addr0
&& !base_addr1
))
1464 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1467 "\neither more than one address or no addresses in expr ");
1468 print_generic_expr (dump_file
, expr
, TDF_SLIM
);
1469 fprintf (dump_file
, "\n");
1474 /* To revert STRIP_NOPS. */
1475 oprnd0
= TREE_OPERAND (expr
, 0);
1476 oprnd1
= TREE_OPERAND (expr
, 1);
1478 offset_expr
= base_addr0
?
1479 fold_convert (ssizetype
, oprnd1
) : fold_convert (ssizetype
, oprnd0
);
1481 /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is
1482 a number, we can add it to the misalignment value calculated for base,
1483 otherwise, misalignment is NULL. */
1484 if (TREE_CODE (offset_expr
) == INTEGER_CST
&& address_misalign
)
1486 *misalign
= size_binop (TREE_CODE (expr
), address_misalign
,
1488 *aligned_to
= address_aligned_to
;
1492 *misalign
= NULL_TREE
;
1493 *aligned_to
= NULL_TREE
;
1496 /* Combine offset (from EXPR {base + offset}) with the offset calculated
1498 *offset
= size_binop (TREE_CODE (expr
), address_offset
, offset_expr
);
1499 return base_addr0
? base_addr0
: base_addr1
;
1502 base_address
= object_analysis (TREE_OPERAND (expr
, 0), stmt
, is_read
,
1503 &dr
, offset
, misalign
, aligned_to
, step
,
1504 &dummy
, &dummy1
, &dummy2
);
1505 return base_address
;
1508 if (!POINTER_TYPE_P (TREE_TYPE (expr
)))
1510 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1512 fprintf (dump_file
, "\nnot pointer SSA_NAME ");
1513 print_generic_expr (dump_file
, expr
, TDF_SLIM
);
1514 fprintf (dump_file
, "\n");
1518 *aligned_to
= ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr
))));
1519 *misalign
= ssize_int (0);
1520 *offset
= ssize_int (0);
1521 *step
= ssize_int (0);
1530 /* Function object_analysis
1532 Create a data-reference structure DR for MEMREF.
1533 Return the BASE of the data reference MEMREF if the analysis is possible.
1534 Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1535 E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset
1536 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET
1537 instantiated with initial_conditions of access_functions of variables,
1538 and STEP is the evolution of the DR_REF in this loop.
1540 Function get_inner_reference is used for the above in case of ARRAY_REF and
1543 The structure of the function is as follows:
1545 Case 1. For handled_component_p refs
1546 1.1 build data-reference structure for MEMREF
1547 1.2 call get_inner_reference
1548 1.2.1 analyze offset expr received from get_inner_reference
1549 (fall through with BASE)
1550 Case 2. For declarations
1552 Case 3. For INDIRECT_REFs
1553 3.1 build data-reference structure for MEMREF
1554 3.2 analyze evolution and initial condition of MEMREF
1555 3.3 set data-reference structure for MEMREF
1556 3.4 call address_analysis to analyze INIT of the access function
1557 3.5 extract memory tag
1560 Combine the results of object and address analysis to calculate
1561 INITIAL_OFFSET, STEP and misalignment info.
1564 MEMREF - the memory reference that is being analyzed
1565 STMT - the statement that contains MEMREF
1566 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1569 BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
1570 E.g, if MEMREF is a.b[k].c[i][j] the returned
1572 DR - data_reference struct for MEMREF
1573 INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
1574 MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of
1575 ALIGNMENT or NULL_TREE if the computation is impossible
1576 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1577 calculated (doesn't depend on variables)
1578 STEP - evolution of the DR_REF in the loop
1579 MEMTAG - memory tag for aliasing purposes
1580 PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
1581 SUBVARS - Sub-variables of the variable
1583 If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned,
1584 but DR can be created anyway.
1589 object_analysis (tree memref
, tree stmt
, bool is_read
,
1590 struct data_reference
**dr
, tree
*offset
, tree
*misalign
,
1591 tree
*aligned_to
, tree
*step
, tree
*memtag
,
1592 struct ptr_info_def
**ptr_info
, subvar_t
*subvars
)
1594 tree base
= NULL_TREE
, base_address
= NULL_TREE
;
1595 tree object_offset
= ssize_int (0), object_misalign
= ssize_int (0);
1596 tree object_step
= ssize_int (0), address_step
= ssize_int (0);
1597 tree address_offset
= ssize_int (0), address_misalign
= ssize_int (0);
1598 HOST_WIDE_INT pbitsize
, pbitpos
;
1599 tree poffset
, bit_pos_in_bytes
;
1600 enum machine_mode pmode
;
1601 int punsignedp
, pvolatilep
;
1602 tree ptr_step
= ssize_int (0), ptr_init
= NULL_TREE
;
1603 struct loop
*loop
= loop_containing_stmt (stmt
);
1604 struct data_reference
*ptr_dr
= NULL
;
1605 tree object_aligned_to
= NULL_TREE
, address_aligned_to
= NULL_TREE
;
1606 tree comp_ref
= NULL_TREE
;
1611 /* Case 1. handled_component_p refs. */
1612 if (handled_component_p (memref
))
1614 /* 1.1 build data-reference structure for MEMREF. */
1617 if (TREE_CODE (memref
) == ARRAY_REF
)
1618 *dr
= analyze_array (stmt
, memref
, is_read
);
1619 else if (TREE_CODE (memref
) == COMPONENT_REF
)
1623 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1625 fprintf (dump_file
, "\ndata-ref of unsupported type ");
1626 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1627 fprintf (dump_file
, "\n");
1633 /* 1.2 call get_inner_reference. */
1634 /* Find the base and the offset from it. */
1635 base
= get_inner_reference (memref
, &pbitsize
, &pbitpos
, &poffset
,
1636 &pmode
, &punsignedp
, &pvolatilep
, false);
1639 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1641 fprintf (dump_file
, "\nfailed to get inner ref for ");
1642 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1643 fprintf (dump_file
, "\n");
1648 /* 1.2.1 analyze offset expr received from get_inner_reference. */
1650 && !analyze_offset_expr (poffset
, loop
, &object_offset
,
1651 &object_misalign
, &object_aligned_to
,
1654 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1656 fprintf (dump_file
, "\nfailed to compute offset or step for ");
1657 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1658 fprintf (dump_file
, "\n");
1663 /* Add bit position to OFFSET and MISALIGN. */
1665 bit_pos_in_bytes
= ssize_int (pbitpos
/BITS_PER_UNIT
);
1666 /* Check that there is no remainder in bits. */
1667 if (pbitpos
%BITS_PER_UNIT
)
1669 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1670 fprintf (dump_file
, "\nbit offset alignment.\n");
1673 object_offset
= size_binop (PLUS_EXPR
, bit_pos_in_bytes
, object_offset
);
1674 if (object_misalign
)
1675 object_misalign
= size_binop (PLUS_EXPR
, object_misalign
,
1678 memref
= base
; /* To continue analysis of BASE. */
1682 /* Part 1: Case 2. Declarations. */
1683 if (DECL_P (memref
))
1685 /* We expect to get a decl only if we already have a DR, or with
1686 COMPONENT_REFs of type 'a[i].b'. */
1689 if (comp_ref
&& TREE_CODE (TREE_OPERAND (comp_ref
, 0)) == ARRAY_REF
)
1691 *dr
= analyze_array (stmt
, TREE_OPERAND (comp_ref
, 0), is_read
);
1692 if (DR_NUM_DIMENSIONS (*dr
) != 1)
1694 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1696 fprintf (dump_file
, "\n multidimensional component ref ");
1697 print_generic_expr (dump_file
, comp_ref
, TDF_SLIM
);
1698 fprintf (dump_file
, "\n");
1705 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1707 fprintf (dump_file
, "\nunhandled decl ");
1708 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1709 fprintf (dump_file
, "\n");
1715 /* TODO: if during the analysis of INDIRECT_REF we get to an object, put
1716 the object in BASE_OBJECT field if we can prove that this is O.K.,
1717 i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT.
1718 (e.g., if the object is an array base 'a', where 'a[N]', we must prove
1719 that every access with 'p' (the original INDIRECT_REF based on '&a')
1720 in the loop is within the array boundaries - from a[0] to a[N-1]).
1721 Otherwise, our alias analysis can be incorrect.
1722 Even if an access function based on BASE_OBJECT can't be build, update
1723 BASE_OBJECT field to enable us to prove that two data-refs are
1724 different (without access function, distance analysis is impossible).
1726 if (SSA_VAR_P (memref
) && var_can_have_subvars (memref
))
1727 *subvars
= get_subvars_for_var (memref
);
1728 base_address
= build_fold_addr_expr (memref
);
1729 /* 2.1 set MEMTAG. */
1733 /* Part 1: Case 3. INDIRECT_REFs. */
1734 else if (TREE_CODE (memref
) == INDIRECT_REF
)
1736 tree ptr_ref
= TREE_OPERAND (memref
, 0);
1737 if (TREE_CODE (ptr_ref
) == SSA_NAME
)
1738 *ptr_info
= SSA_NAME_PTR_INFO (ptr_ref
);
1740 /* 3.1 build data-reference structure for MEMREF. */
1741 ptr_dr
= analyze_indirect_ref (stmt
, memref
, is_read
);
1744 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1746 fprintf (dump_file
, "\nfailed to create dr for ");
1747 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1748 fprintf (dump_file
, "\n");
1753 /* 3.2 analyze evolution and initial condition of MEMREF. */
1754 ptr_step
= DR_STEP (ptr_dr
);
1755 ptr_init
= DR_BASE_ADDRESS (ptr_dr
);
1756 if (!ptr_init
|| !ptr_step
|| !POINTER_TYPE_P (TREE_TYPE (ptr_init
)))
1758 *dr
= (*dr
) ? *dr
: ptr_dr
;
1759 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1761 fprintf (dump_file
, "\nbad pointer access ");
1762 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1763 fprintf (dump_file
, "\n");
1768 if (integer_zerop (ptr_step
) && !(*dr
))
1770 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1771 fprintf (dump_file
, "\nptr is loop invariant.\n");
1775 /* If there exists DR for MEMREF, we are analyzing the base of
1776 handled component (PTR_INIT), which not necessary has evolution in
1779 object_step
= size_binop (PLUS_EXPR
, object_step
, ptr_step
);
1781 /* 3.3 set data-reference structure for MEMREF. */
1785 /* 3.4 call address_analysis to analyze INIT of the access
1787 base_address
= address_analysis (ptr_init
, stmt
, is_read
, *dr
,
1788 &address_offset
, &address_misalign
,
1789 &address_aligned_to
, &address_step
);
1792 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1794 fprintf (dump_file
, "\nfailed to analyze address ");
1795 print_generic_expr (dump_file
, ptr_init
, TDF_SLIM
);
1796 fprintf (dump_file
, "\n");
1801 /* 3.5 extract memory tag. */
1802 switch (TREE_CODE (base_address
))
1805 *memtag
= get_var_ann (SSA_NAME_VAR (base_address
))->symbol_mem_tag
;
1806 if (!(*memtag
) && TREE_CODE (TREE_OPERAND (memref
, 0)) == SSA_NAME
)
1807 *memtag
= get_var_ann (
1808 SSA_NAME_VAR (TREE_OPERAND (memref
, 0)))->symbol_mem_tag
;
1811 *memtag
= TREE_OPERAND (base_address
, 0);
1814 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1816 fprintf (dump_file
, "\nno memtag for ");
1817 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1818 fprintf (dump_file
, "\n");
1820 *memtag
= NULL_TREE
;
1827 /* MEMREF cannot be analyzed. */
1828 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1830 fprintf (dump_file
, "\ndata-ref of unsupported type ");
1831 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1832 fprintf (dump_file
, "\n");
1838 DR_REF (*dr
) = comp_ref
;
1840 if (SSA_VAR_P (*memtag
) && var_can_have_subvars (*memtag
))
1841 *subvars
= get_subvars_for_var (*memtag
);
1843 /* Part 2: Combine the results of object and address analysis to calculate
1844 INITIAL_OFFSET, STEP and misalignment info. */
1845 *offset
= size_binop (PLUS_EXPR
, object_offset
, address_offset
);
1847 if ((!object_misalign
&& !object_aligned_to
)
1848 || (!address_misalign
&& !address_aligned_to
))
1850 *misalign
= NULL_TREE
;
1851 *aligned_to
= NULL_TREE
;
1855 if (object_misalign
&& address_misalign
)
1856 *misalign
= size_binop (PLUS_EXPR
, object_misalign
, address_misalign
);
1858 *misalign
= object_misalign
? object_misalign
: address_misalign
;
1859 if (object_aligned_to
&& address_aligned_to
)
1860 *aligned_to
= size_binop (MIN_EXPR
, object_aligned_to
,
1861 address_aligned_to
);
1863 *aligned_to
= object_aligned_to
?
1864 object_aligned_to
: address_aligned_to
;
1866 *step
= size_binop (PLUS_EXPR
, object_step
, address_step
);
1868 return base_address
;
1871 /* Function analyze_offset.
1873 Extract INVARIANT and CONSTANT parts from OFFSET.
1877 analyze_offset (tree offset
, tree
*invariant
, tree
*constant
)
1879 tree op0
, op1
, constant_0
, constant_1
, invariant_0
, invariant_1
;
1880 enum tree_code code
= TREE_CODE (offset
);
1882 *invariant
= NULL_TREE
;
1883 *constant
= NULL_TREE
;
1885 /* Not PLUS/MINUS expression - recursion stop condition. */
1886 if (code
!= PLUS_EXPR
&& code
!= MINUS_EXPR
)
1888 if (TREE_CODE (offset
) == INTEGER_CST
)
1891 *invariant
= offset
;
1895 op0
= TREE_OPERAND (offset
, 0);
1896 op1
= TREE_OPERAND (offset
, 1);
1898 /* Recursive call with the operands. */
1899 analyze_offset (op0
, &invariant_0
, &constant_0
);
1900 analyze_offset (op1
, &invariant_1
, &constant_1
);
1902 /* Combine the results. */
1903 *constant
= constant_0
? constant_0
: constant_1
;
1904 if (invariant_0
&& invariant_1
)
1906 fold_build2 (code
, TREE_TYPE (invariant_0
), invariant_0
, invariant_1
);
1908 *invariant
= invariant_0
? invariant_0
: invariant_1
;
1911 /* Free the memory used by the data reference DR. */
1914 free_data_ref (data_reference_p dr
)
1916 DR_FREE_ACCESS_FNS (dr
);
1920 /* Function create_data_ref.
1922 Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS,
1923 DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO,
1924 DR_MEMTAG, and DR_POINTSTO_INFO fields.
1927 MEMREF - the memory reference that is being analyzed
1928 STMT - the statement that contains MEMREF
1929 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1932 DR (returned value) - data_reference struct for MEMREF
1935 static struct data_reference
*
1936 create_data_ref (tree memref
, tree stmt
, bool is_read
)
1938 struct data_reference
*dr
= NULL
;
1939 tree base_address
, offset
, step
, misalign
, memtag
;
1940 struct loop
*loop
= loop_containing_stmt (stmt
);
1941 tree invariant
= NULL_TREE
, constant
= NULL_TREE
;
1942 tree type_size
, init_cond
;
1943 struct ptr_info_def
*ptr_info
;
1944 subvar_t subvars
= NULL
;
1945 tree aligned_to
, type
= NULL_TREE
, orig_offset
;
1950 base_address
= object_analysis (memref
, stmt
, is_read
, &dr
, &offset
,
1951 &misalign
, &aligned_to
, &step
, &memtag
,
1952 &ptr_info
, &subvars
);
1953 if (!dr
|| !base_address
)
1955 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1957 fprintf (dump_file
, "\ncreate_data_ref: failed to create a dr for ");
1958 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1959 fprintf (dump_file
, "\n");
1964 DR_BASE_ADDRESS (dr
) = base_address
;
1965 DR_OFFSET (dr
) = offset
;
1966 DR_INIT (dr
) = ssize_int (0);
1967 DR_STEP (dr
) = step
;
1968 DR_OFFSET_MISALIGNMENT (dr
) = misalign
;
1969 DR_ALIGNED_TO (dr
) = aligned_to
;
1970 DR_MEMTAG (dr
) = memtag
;
1971 DR_PTR_INFO (dr
) = ptr_info
;
1972 DR_SUBVARS (dr
) = subvars
;
1974 type_size
= fold_convert (ssizetype
, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr
))));
1976 /* Extract CONSTANT and INVARIANT from OFFSET. */
1977 /* Remove cast from OFFSET and restore it for INVARIANT part. */
1978 orig_offset
= offset
;
1979 STRIP_NOPS (offset
);
1980 if (offset
!= orig_offset
)
1981 type
= TREE_TYPE (orig_offset
);
1982 analyze_offset (offset
, &invariant
, &constant
);
1983 if (type
&& invariant
)
1984 invariant
= fold_convert (type
, invariant
);
1986 /* Put CONSTANT part of OFFSET in DR_INIT and INVARIANT in DR_OFFSET field
1990 DR_INIT (dr
) = fold_convert (ssizetype
, constant
);
1991 init_cond
= fold_build2 (TRUNC_DIV_EXPR
, TREE_TYPE (constant
),
1992 constant
, type_size
);
1995 DR_INIT (dr
) = init_cond
= ssize_int (0);
1998 DR_OFFSET (dr
) = invariant
;
2000 DR_OFFSET (dr
) = ssize_int (0);
2002 /* Change the access function for INIDIRECT_REFs, according to
2003 DR_BASE_ADDRESS. Analyze OFFSET calculated in object_analysis. OFFSET is
2004 an expression that can contain loop invariant expressions and constants.
2005 We put the constant part in the initial condition of the access function
2006 (for data dependence tests), and in DR_INIT of the data-ref. The loop
2007 invariant part is put in DR_OFFSET.
2008 The evolution part of the access function is STEP calculated in
2009 object_analysis divided by the size of data type.
2011 if (!DR_BASE_OBJECT (dr
)
2012 || (TREE_CODE (memref
) == COMPONENT_REF
&& DR_NUM_DIMENSIONS (dr
) == 1))
2017 /* Update access function. */
2018 access_fn
= DR_ACCESS_FN (dr
, 0);
2019 if (automatically_generated_chrec_p (access_fn
))
2025 new_step
= size_binop (TRUNC_DIV_EXPR
,
2026 fold_convert (ssizetype
, step
), type_size
);
2028 init_cond
= chrec_convert (chrec_type (access_fn
), init_cond
, stmt
);
2029 new_step
= chrec_convert (chrec_type (access_fn
), new_step
, stmt
);
2030 if (automatically_generated_chrec_p (init_cond
)
2031 || automatically_generated_chrec_p (new_step
))
2036 access_fn
= chrec_replace_initial_condition (access_fn
, init_cond
);
2037 access_fn
= reset_evolution_in_loop (loop
->num
, access_fn
, new_step
);
2039 VEC_replace (tree
, DR_ACCESS_FNS (dr
), 0, access_fn
);
2042 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2044 struct ptr_info_def
*pi
= DR_PTR_INFO (dr
);
2046 fprintf (dump_file
, "\nCreated dr for ");
2047 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
2048 fprintf (dump_file
, "\n\tbase_address: ");
2049 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
2050 fprintf (dump_file
, "\n\toffset from base address: ");
2051 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
2052 fprintf (dump_file
, "\n\tconstant offset from base address: ");
2053 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
2054 fprintf (dump_file
, "\n\tbase_object: ");
2055 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
2056 fprintf (dump_file
, "\n\tstep: ");
2057 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
2058 fprintf (dump_file
, "B\n\tmisalignment from base: ");
2059 print_generic_expr (dump_file
, DR_OFFSET_MISALIGNMENT (dr
), TDF_SLIM
);
2060 if (DR_OFFSET_MISALIGNMENT (dr
))
2061 fprintf (dump_file
, "B");
2062 if (DR_ALIGNED_TO (dr
))
2064 fprintf (dump_file
, "\n\taligned to: ");
2065 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
2067 fprintf (dump_file
, "\n\tmemtag: ");
2068 print_generic_expr (dump_file
, DR_MEMTAG (dr
), TDF_SLIM
);
2069 fprintf (dump_file
, "\n");
2070 if (pi
&& pi
->name_mem_tag
)
2072 fprintf (dump_file
, "\n\tnametag: ");
2073 print_generic_expr (dump_file
, pi
->name_mem_tag
, TDF_SLIM
);
2074 fprintf (dump_file
, "\n");
2081 /* Returns true when all the functions of a tree_vec CHREC are the
2085 all_chrecs_equal_p (tree chrec
)
2089 for (j
= 0; j
< TREE_VEC_LENGTH (chrec
) - 1; j
++)
2090 if (!eq_evolutions_p (TREE_VEC_ELT (chrec
, j
),
2091 TREE_VEC_ELT (chrec
, j
+ 1)))
2097 /* Determine for each subscript in the data dependence relation DDR
2101 compute_subscript_distance (struct data_dependence_relation
*ddr
)
2103 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
2107 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2109 tree conflicts_a
, conflicts_b
, difference
;
2110 struct subscript
*subscript
;
2112 subscript
= DDR_SUBSCRIPT (ddr
, i
);
2113 conflicts_a
= SUB_CONFLICTS_IN_A (subscript
);
2114 conflicts_b
= SUB_CONFLICTS_IN_B (subscript
);
2116 if (TREE_CODE (conflicts_a
) == TREE_VEC
)
2118 if (!all_chrecs_equal_p (conflicts_a
))
2120 SUB_DISTANCE (subscript
) = chrec_dont_know
;
2124 conflicts_a
= TREE_VEC_ELT (conflicts_a
, 0);
2127 if (TREE_CODE (conflicts_b
) == TREE_VEC
)
2129 if (!all_chrecs_equal_p (conflicts_b
))
2131 SUB_DISTANCE (subscript
) = chrec_dont_know
;
2135 conflicts_b
= TREE_VEC_ELT (conflicts_b
, 0);
2138 conflicts_b
= chrec_convert (integer_type_node
, conflicts_b
,
2140 conflicts_a
= chrec_convert (integer_type_node
, conflicts_a
,
2142 difference
= chrec_fold_minus
2143 (integer_type_node
, conflicts_b
, conflicts_a
);
2145 if (evolution_function_is_constant_p (difference
))
2146 SUB_DISTANCE (subscript
) = difference
;
2149 SUB_DISTANCE (subscript
) = chrec_dont_know
;
2154 /* Initialize a data dependence relation between data accesses A and
2155 B. NB_LOOPS is the number of loops surrounding the references: the
2156 size of the classic distance/direction vectors. */
2158 static struct data_dependence_relation
*
2159 initialize_data_dependence_relation (struct data_reference
*a
,
2160 struct data_reference
*b
,
2161 VEC (loop_p
, heap
) *loop_nest
)
2163 struct data_dependence_relation
*res
;
2164 bool differ_p
, known_dependence
;
2167 res
= XNEW (struct data_dependence_relation
);
2170 DDR_LOOP_NEST (res
) = NULL
;
2172 if (a
== NULL
|| b
== NULL
)
2174 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
2178 /* When A and B are arrays and their dimensions differ, we directly
2179 initialize the relation to "there is no dependence": chrec_known. */
2180 if (DR_BASE_OBJECT (a
) && DR_BASE_OBJECT (b
)
2181 && DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
))
2183 DDR_ARE_DEPENDENT (res
) = chrec_known
;
2187 if (DR_BASE_ADDRESS (a
) && DR_BASE_ADDRESS (b
))
2188 known_dependence
= base_addr_differ_p (a
, b
, &differ_p
);
2190 known_dependence
= base_object_differ_p (a
, b
, &differ_p
);
2192 if (!known_dependence
)
2194 /* Can't determine whether the data-refs access the same memory
2196 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
2202 DDR_ARE_DEPENDENT (res
) = chrec_known
;
2206 DDR_AFFINE_P (res
) = true;
2207 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
2208 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
2209 DDR_LOOP_NEST (res
) = loop_nest
;
2210 DDR_DIR_VECTS (res
) = NULL
;
2211 DDR_DIST_VECTS (res
) = NULL
;
2213 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
2215 struct subscript
*subscript
;
2217 subscript
= XNEW (struct subscript
);
2218 SUB_CONFLICTS_IN_A (subscript
) = chrec_dont_know
;
2219 SUB_CONFLICTS_IN_B (subscript
) = chrec_dont_know
;
2220 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
2221 SUB_DISTANCE (subscript
) = chrec_dont_know
;
2222 VEC_safe_push (subscript_p
, heap
, DDR_SUBSCRIPTS (res
), subscript
);
2228 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
2232 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
2235 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2237 fprintf (dump_file
, "(dependence classified: ");
2238 print_generic_expr (dump_file
, chrec
, 0);
2239 fprintf (dump_file
, ")\n");
2242 DDR_ARE_DEPENDENT (ddr
) = chrec
;
2243 VEC_free (subscript_p
, heap
, DDR_SUBSCRIPTS (ddr
));
2246 /* The dependence relation DDR cannot be represented by a distance
2250 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
2252 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2253 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
2255 DDR_AFFINE_P (ddr
) = false;
2260 /* This section contains the classic Banerjee tests. */
2262 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
2263 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
2266 ziv_subscript_p (tree chrec_a
,
2269 return (evolution_function_is_constant_p (chrec_a
)
2270 && evolution_function_is_constant_p (chrec_b
));
2273 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
2274 variable, i.e., if the SIV (Single Index Variable) test is true. */
2277 siv_subscript_p (tree chrec_a
,
2280 if ((evolution_function_is_constant_p (chrec_a
)
2281 && evolution_function_is_univariate_p (chrec_b
))
2282 || (evolution_function_is_constant_p (chrec_b
)
2283 && evolution_function_is_univariate_p (chrec_a
)))
2286 if (evolution_function_is_univariate_p (chrec_a
)
2287 && evolution_function_is_univariate_p (chrec_b
))
2289 switch (TREE_CODE (chrec_a
))
2291 case POLYNOMIAL_CHREC
:
2292 switch (TREE_CODE (chrec_b
))
2294 case POLYNOMIAL_CHREC
:
2295 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
2310 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
2311 *OVERLAPS_B are initialized to the functions that describe the
2312 relation between the elements accessed twice by CHREC_A and
2313 CHREC_B. For k >= 0, the following property is verified:
2315 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2318 analyze_ziv_subscript (tree chrec_a
,
2322 tree
*last_conflicts
)
2325 dependence_stats
.num_ziv
++;
2327 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2328 fprintf (dump_file
, "(analyze_ziv_subscript \n");
2330 chrec_a
= chrec_convert (integer_type_node
, chrec_a
, NULL_TREE
);
2331 chrec_b
= chrec_convert (integer_type_node
, chrec_b
, NULL_TREE
);
2332 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
2334 switch (TREE_CODE (difference
))
2337 if (integer_zerop (difference
))
2339 /* The difference is equal to zero: the accessed index
2340 overlaps for each iteration in the loop. */
2341 *overlaps_a
= integer_zero_node
;
2342 *overlaps_b
= integer_zero_node
;
2343 *last_conflicts
= chrec_dont_know
;
2344 dependence_stats
.num_ziv_dependent
++;
2348 /* The accesses do not overlap. */
2349 *overlaps_a
= chrec_known
;
2350 *overlaps_b
= chrec_known
;
2351 *last_conflicts
= integer_zero_node
;
2352 dependence_stats
.num_ziv_independent
++;
2357 /* We're not sure whether the indexes overlap. For the moment,
2358 conservatively answer "don't know". */
2359 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2360 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
2362 *overlaps_a
= chrec_dont_know
;
2363 *overlaps_b
= chrec_dont_know
;
2364 *last_conflicts
= chrec_dont_know
;
2365 dependence_stats
.num_ziv_unimplemented
++;
2369 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2370 fprintf (dump_file
, ")\n");
2373 /* Get the real or estimated number of iterations for LOOPNUM, whichever is
2374 available. Return the number of iterations as a tree, or NULL_TREE if
2378 get_number_of_iters_for_loop (int loopnum
)
2380 tree numiter
= number_of_iterations_in_loop (current_loops
->parray
[loopnum
]);
2382 if (TREE_CODE (numiter
) != INTEGER_CST
)
2383 numiter
= current_loops
->parray
[loopnum
]->estimated_nb_iterations
;
2384 if (chrec_contains_undetermined (numiter
))
2389 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2390 constant, and CHREC_B is an affine function. *OVERLAPS_A and
2391 *OVERLAPS_B are initialized to the functions that describe the
2392 relation between the elements accessed twice by CHREC_A and
2393 CHREC_B. For k >= 0, the following property is verified:
2395 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2398 analyze_siv_subscript_cst_affine (tree chrec_a
,
2402 tree
*last_conflicts
)
2404 bool value0
, value1
, value2
;
2407 chrec_a
= chrec_convert (integer_type_node
, chrec_a
, NULL_TREE
);
2408 chrec_b
= chrec_convert (integer_type_node
, chrec_b
, NULL_TREE
);
2409 difference
= chrec_fold_minus
2410 (integer_type_node
, initial_condition (chrec_b
), chrec_a
);
2412 if (!chrec_is_positive (initial_condition (difference
), &value0
))
2414 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2415 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
2417 dependence_stats
.num_siv_unimplemented
++;
2418 *overlaps_a
= chrec_dont_know
;
2419 *overlaps_b
= chrec_dont_know
;
2420 *last_conflicts
= chrec_dont_know
;
2425 if (value0
== false)
2427 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
2429 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2430 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
2432 *overlaps_a
= chrec_dont_know
;
2433 *overlaps_b
= chrec_dont_know
;
2434 *last_conflicts
= chrec_dont_know
;
2435 dependence_stats
.num_siv_unimplemented
++;
2444 chrec_b = {10, +, 1}
2447 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
2450 int loopnum
= CHREC_VARIABLE (chrec_b
);
2452 *overlaps_a
= integer_zero_node
;
2453 *overlaps_b
= fold_build2 (EXACT_DIV_EXPR
, integer_type_node
,
2454 fold_build1 (ABS_EXPR
,
2457 CHREC_RIGHT (chrec_b
));
2458 *last_conflicts
= integer_one_node
;
2461 /* Perform weak-zero siv test to see if overlap is
2462 outside the loop bounds. */
2463 numiter
= get_number_of_iters_for_loop (loopnum
);
2465 if (numiter
!= NULL_TREE
2466 && TREE_CODE (*overlaps_b
) == INTEGER_CST
2467 && tree_int_cst_lt (numiter
, *overlaps_b
))
2469 *overlaps_a
= chrec_known
;
2470 *overlaps_b
= chrec_known
;
2471 *last_conflicts
= integer_zero_node
;
2472 dependence_stats
.num_siv_independent
++;
2475 dependence_stats
.num_siv_dependent
++;
2479 /* When the step does not divide the difference, there are
2483 *overlaps_a
= chrec_known
;
2484 *overlaps_b
= chrec_known
;
2485 *last_conflicts
= integer_zero_node
;
2486 dependence_stats
.num_siv_independent
++;
2495 chrec_b = {10, +, -1}
2497 In this case, chrec_a will not overlap with chrec_b. */
2498 *overlaps_a
= chrec_known
;
2499 *overlaps_b
= chrec_known
;
2500 *last_conflicts
= integer_zero_node
;
2501 dependence_stats
.num_siv_independent
++;
2508 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
2510 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2511 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
2513 *overlaps_a
= chrec_dont_know
;
2514 *overlaps_b
= chrec_dont_know
;
2515 *last_conflicts
= chrec_dont_know
;
2516 dependence_stats
.num_siv_unimplemented
++;
2521 if (value2
== false)
2525 chrec_b = {10, +, -1}
2527 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
2530 int loopnum
= CHREC_VARIABLE (chrec_b
);
2532 *overlaps_a
= integer_zero_node
;
2533 *overlaps_b
= fold_build2 (EXACT_DIV_EXPR
,
2534 integer_type_node
, difference
,
2535 CHREC_RIGHT (chrec_b
));
2536 *last_conflicts
= integer_one_node
;
2538 /* Perform weak-zero siv test to see if overlap is
2539 outside the loop bounds. */
2540 numiter
= get_number_of_iters_for_loop (loopnum
);
2542 if (numiter
!= NULL_TREE
2543 && TREE_CODE (*overlaps_b
) == INTEGER_CST
2544 && tree_int_cst_lt (numiter
, *overlaps_b
))
2546 *overlaps_a
= chrec_known
;
2547 *overlaps_b
= chrec_known
;
2548 *last_conflicts
= integer_zero_node
;
2549 dependence_stats
.num_siv_independent
++;
2552 dependence_stats
.num_siv_dependent
++;
2556 /* When the step does not divide the difference, there
2560 *overlaps_a
= chrec_known
;
2561 *overlaps_b
= chrec_known
;
2562 *last_conflicts
= integer_zero_node
;
2563 dependence_stats
.num_siv_independent
++;
2573 In this case, chrec_a will not overlap with chrec_b. */
2574 *overlaps_a
= chrec_known
;
2575 *overlaps_b
= chrec_known
;
2576 *last_conflicts
= integer_zero_node
;
2577 dependence_stats
.num_siv_independent
++;
2585 /* Helper recursive function for initializing the matrix A. Returns
2586 the initial value of CHREC. */
2589 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
2593 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
2594 return int_cst_value (chrec
);
2596 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
2597 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
2600 #define FLOOR_DIV(x,y) ((x) / (y))
2602 /* Solves the special case of the Diophantine equation:
2603 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2605 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2606 number of iterations that loops X and Y run. The overlaps will be
2607 constructed as evolutions in dimension DIM. */
2610 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
2611 tree
*overlaps_a
, tree
*overlaps_b
,
2612 tree
*last_conflicts
, int dim
)
2614 if (((step_a
> 0 && step_b
> 0)
2615 || (step_a
< 0 && step_b
< 0)))
2617 int step_overlaps_a
, step_overlaps_b
;
2618 int gcd_steps_a_b
, last_conflict
, tau2
;
2620 gcd_steps_a_b
= gcd (step_a
, step_b
);
2621 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
2622 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
2624 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
2625 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
2626 last_conflict
= tau2
;
2628 *overlaps_a
= build_polynomial_chrec
2629 (dim
, integer_zero_node
,
2630 build_int_cst (NULL_TREE
, step_overlaps_a
));
2631 *overlaps_b
= build_polynomial_chrec
2632 (dim
, integer_zero_node
,
2633 build_int_cst (NULL_TREE
, step_overlaps_b
));
2634 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2639 *overlaps_a
= integer_zero_node
;
2640 *overlaps_b
= integer_zero_node
;
2641 *last_conflicts
= integer_zero_node
;
2646 /* Solves the special case of a Diophantine equation where CHREC_A is
2647 an affine bivariate function, and CHREC_B is an affine univariate
2648 function. For example,
2650 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2652 has the following overlapping functions:
2654 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2655 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2656 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2658 FORNOW: This is a specialized implementation for a case occurring in
2659 a common benchmark. Implement the general algorithm. */
2662 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
2663 tree
*overlaps_a
, tree
*overlaps_b
,
2664 tree
*last_conflicts
)
2666 bool xz_p
, yz_p
, xyz_p
;
2667 int step_x
, step_y
, step_z
;
2668 int niter_x
, niter_y
, niter_z
, niter
;
2669 tree numiter_x
, numiter_y
, numiter_z
;
2670 tree overlaps_a_xz
, overlaps_b_xz
, last_conflicts_xz
;
2671 tree overlaps_a_yz
, overlaps_b_yz
, last_conflicts_yz
;
2672 tree overlaps_a_xyz
, overlaps_b_xyz
, last_conflicts_xyz
;
2674 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
2675 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
2676 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
2678 numiter_x
= get_number_of_iters_for_loop (CHREC_VARIABLE (CHREC_LEFT (chrec_a
)));
2679 numiter_y
= get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a
));
2680 numiter_z
= get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b
));
2682 if (numiter_x
== NULL_TREE
|| numiter_y
== NULL_TREE
2683 || numiter_z
== NULL_TREE
)
2685 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2686 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
2688 *overlaps_a
= chrec_dont_know
;
2689 *overlaps_b
= chrec_dont_know
;
2690 *last_conflicts
= chrec_dont_know
;
2694 niter_x
= int_cst_value (numiter_x
);
2695 niter_y
= int_cst_value (numiter_y
);
2696 niter_z
= int_cst_value (numiter_z
);
2698 niter
= MIN (niter_x
, niter_z
);
2699 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
2702 &last_conflicts_xz
, 1);
2703 niter
= MIN (niter_y
, niter_z
);
2704 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
2707 &last_conflicts_yz
, 2);
2708 niter
= MIN (niter_x
, niter_z
);
2709 niter
= MIN (niter_y
, niter
);
2710 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
2713 &last_conflicts_xyz
, 3);
2715 xz_p
= !integer_zerop (last_conflicts_xz
);
2716 yz_p
= !integer_zerop (last_conflicts_yz
);
2717 xyz_p
= !integer_zerop (last_conflicts_xyz
);
2719 if (xz_p
|| yz_p
|| xyz_p
)
2721 *overlaps_a
= make_tree_vec (2);
2722 TREE_VEC_ELT (*overlaps_a
, 0) = integer_zero_node
;
2723 TREE_VEC_ELT (*overlaps_a
, 1) = integer_zero_node
;
2724 *overlaps_b
= integer_zero_node
;
2727 tree t0
= chrec_convert (integer_type_node
,
2728 TREE_VEC_ELT (*overlaps_a
, 0), NULL_TREE
);
2729 tree t1
= chrec_convert (integer_type_node
, overlaps_a_xz
,
2731 tree t2
= chrec_convert (integer_type_node
, *overlaps_b
,
2733 tree t3
= chrec_convert (integer_type_node
, overlaps_b_xz
,
2736 TREE_VEC_ELT (*overlaps_a
, 0) = chrec_fold_plus (integer_type_node
,
2738 *overlaps_b
= chrec_fold_plus (integer_type_node
, t2
, t3
);
2739 *last_conflicts
= last_conflicts_xz
;
2743 tree t0
= chrec_convert (integer_type_node
,
2744 TREE_VEC_ELT (*overlaps_a
, 1), NULL_TREE
);
2745 tree t1
= chrec_convert (integer_type_node
, overlaps_a_yz
, NULL_TREE
);
2746 tree t2
= chrec_convert (integer_type_node
, *overlaps_b
, NULL_TREE
);
2747 tree t3
= chrec_convert (integer_type_node
, overlaps_b_yz
, NULL_TREE
);
2749 TREE_VEC_ELT (*overlaps_a
, 1) = chrec_fold_plus (integer_type_node
,
2751 *overlaps_b
= chrec_fold_plus (integer_type_node
, t2
, t3
);
2752 *last_conflicts
= last_conflicts_yz
;
2756 tree t0
= chrec_convert (integer_type_node
,
2757 TREE_VEC_ELT (*overlaps_a
, 0), NULL_TREE
);
2758 tree t1
= chrec_convert (integer_type_node
, overlaps_a_xyz
,
2760 tree t2
= chrec_convert (integer_type_node
,
2761 TREE_VEC_ELT (*overlaps_a
, 1), NULL_TREE
);
2762 tree t3
= chrec_convert (integer_type_node
, overlaps_a_xyz
,
2764 tree t4
= chrec_convert (integer_type_node
, *overlaps_b
, NULL_TREE
);
2765 tree t5
= chrec_convert (integer_type_node
, overlaps_b_xyz
,
2768 TREE_VEC_ELT (*overlaps_a
, 0) = chrec_fold_plus (integer_type_node
,
2770 TREE_VEC_ELT (*overlaps_a
, 1) = chrec_fold_plus (integer_type_node
,
2772 *overlaps_b
= chrec_fold_plus (integer_type_node
, t4
, t5
);
2773 *last_conflicts
= last_conflicts_xyz
;
2778 *overlaps_a
= integer_zero_node
;
2779 *overlaps_b
= integer_zero_node
;
2780 *last_conflicts
= integer_zero_node
;
2784 /* Determines the overlapping elements due to accesses CHREC_A and
2785 CHREC_B, that are affine functions. This function cannot handle
2786 symbolic evolution functions, ie. when initial conditions are
2787 parameters, because it uses lambda matrices of integers. */
2790 analyze_subscript_affine_affine (tree chrec_a
,
2794 tree
*last_conflicts
)
2796 unsigned nb_vars_a
, nb_vars_b
, dim
;
2797 int init_a
, init_b
, gamma
, gcd_alpha_beta
;
2799 lambda_matrix A
, U
, S
;
2801 if (eq_evolutions_p (chrec_a
, chrec_b
))
2803 /* The accessed index overlaps for each iteration in the
2805 *overlaps_a
= integer_zero_node
;
2806 *overlaps_b
= integer_zero_node
;
2807 *last_conflicts
= chrec_dont_know
;
2810 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2811 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
2813 /* For determining the initial intersection, we have to solve a
2814 Diophantine equation. This is the most time consuming part.
2816 For answering to the question: "Is there a dependence?" we have
2817 to prove that there exists a solution to the Diophantine
2818 equation, and that the solution is in the iteration domain,
2819 i.e. the solution is positive or zero, and that the solution
2820 happens before the upper bound loop.nb_iterations. Otherwise
2821 there is no dependence. This function outputs a description of
2822 the iterations that hold the intersections. */
2824 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
2825 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
2827 dim
= nb_vars_a
+ nb_vars_b
;
2828 U
= lambda_matrix_new (dim
, dim
);
2829 A
= lambda_matrix_new (dim
, 1);
2830 S
= lambda_matrix_new (dim
, 1);
2832 init_a
= initialize_matrix_A (A
, chrec_a
, 0, 1);
2833 init_b
= initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1);
2834 gamma
= init_b
- init_a
;
2836 /* Don't do all the hard work of solving the Diophantine equation
2837 when we already know the solution: for example,
2840 | gamma = 3 - 3 = 0.
2841 Then the first overlap occurs during the first iterations:
2842 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2846 if (nb_vars_a
== 1 && nb_vars_b
== 1)
2849 int niter
, niter_a
, niter_b
;
2850 tree numiter_a
, numiter_b
;
2852 numiter_a
= get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a
));
2853 numiter_b
= get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b
));
2854 if (numiter_a
== NULL_TREE
|| numiter_b
== NULL_TREE
)
2856 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2857 fprintf (dump_file
, "affine-affine test failed: missing iteration counts.\n");
2858 *overlaps_a
= chrec_dont_know
;
2859 *overlaps_b
= chrec_dont_know
;
2860 *last_conflicts
= chrec_dont_know
;
2861 goto end_analyze_subs_aa
;
2864 niter_a
= int_cst_value (numiter_a
);
2865 niter_b
= int_cst_value (numiter_b
);
2866 niter
= MIN (niter_a
, niter_b
);
2868 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
2869 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
2871 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
2872 overlaps_a
, overlaps_b
,
2876 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
2877 compute_overlap_steps_for_affine_1_2
2878 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
2880 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
2881 compute_overlap_steps_for_affine_1_2
2882 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
2886 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2887 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
2888 *overlaps_a
= chrec_dont_know
;
2889 *overlaps_b
= chrec_dont_know
;
2890 *last_conflicts
= chrec_dont_know
;
2892 goto end_analyze_subs_aa
;
2896 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
2901 lambda_matrix_row_negate (U
, dim
, 0);
2903 gcd_alpha_beta
= S
[0][0];
2905 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2906 but that is a quite strange case. Instead of ICEing, answer
2908 if (gcd_alpha_beta
== 0)
2910 *overlaps_a
= chrec_dont_know
;
2911 *overlaps_b
= chrec_dont_know
;
2912 *last_conflicts
= chrec_dont_know
;
2913 goto end_analyze_subs_aa
;
2916 /* The classic "gcd-test". */
2917 if (!int_divides_p (gcd_alpha_beta
, gamma
))
2919 /* The "gcd-test" has determined that there is no integer
2920 solution, i.e. there is no dependence. */
2921 *overlaps_a
= chrec_known
;
2922 *overlaps_b
= chrec_known
;
2923 *last_conflicts
= integer_zero_node
;
2926 /* Both access functions are univariate. This includes SIV and MIV cases. */
2927 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
2929 /* Both functions should have the same evolution sign. */
2930 if (((A
[0][0] > 0 && -A
[1][0] > 0)
2931 || (A
[0][0] < 0 && -A
[1][0] < 0)))
2933 /* The solutions are given by:
2935 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2938 For a given integer t. Using the following variables,
2940 | i0 = u11 * gamma / gcd_alpha_beta
2941 | j0 = u12 * gamma / gcd_alpha_beta
2948 | y0 = j0 + j1 * t. */
2952 /* X0 and Y0 are the first iterations for which there is a
2953 dependence. X0, Y0 are two solutions of the Diophantine
2954 equation: chrec_a (X0) = chrec_b (Y0). */
2956 int niter
, niter_a
, niter_b
;
2957 tree numiter_a
, numiter_b
;
2959 numiter_a
= get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a
));
2960 numiter_b
= get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b
));
2962 if (numiter_a
== NULL_TREE
|| numiter_b
== NULL_TREE
)
2964 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2965 fprintf (dump_file
, "affine-affine test failed: missing iteration counts.\n");
2966 *overlaps_a
= chrec_dont_know
;
2967 *overlaps_b
= chrec_dont_know
;
2968 *last_conflicts
= chrec_dont_know
;
2969 goto end_analyze_subs_aa
;
2972 niter_a
= int_cst_value (numiter_a
);
2973 niter_b
= int_cst_value (numiter_b
);
2974 niter
= MIN (niter_a
, niter_b
);
2976 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
2977 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
2981 if ((i1
== 0 && i0
< 0)
2982 || (j1
== 0 && j0
< 0))
2984 /* There is no solution.
2985 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2986 falls in here, but for the moment we don't look at the
2987 upper bound of the iteration domain. */
2988 *overlaps_a
= chrec_known
;
2989 *overlaps_b
= chrec_known
;
2990 *last_conflicts
= integer_zero_node
;
2997 tau1
= CEIL (-i0
, i1
);
2998 tau2
= FLOOR_DIV (niter
- i0
, i1
);
3002 int last_conflict
, min_multiple
;
3003 tau1
= MAX (tau1
, CEIL (-j0
, j1
));
3004 tau2
= MIN (tau2
, FLOOR_DIV (niter
- j0
, j1
));
3006 x0
= i1
* tau1
+ i0
;
3007 y0
= j1
* tau1
+ j0
;
3009 /* At this point (x0, y0) is one of the
3010 solutions to the Diophantine equation. The
3011 next step has to compute the smallest
3012 positive solution: the first conflicts. */
3013 min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
3014 x0
-= i1
* min_multiple
;
3015 y0
-= j1
* min_multiple
;
3017 tau1
= (x0
- i0
)/i1
;
3018 last_conflict
= tau2
- tau1
;
3020 /* If the overlap occurs outside of the bounds of the
3021 loop, there is no dependence. */
3022 if (x0
> niter
|| y0
> niter
)
3024 *overlaps_a
= chrec_known
;
3025 *overlaps_b
= chrec_known
;
3026 *last_conflicts
= integer_zero_node
;
3030 *overlaps_a
= build_polynomial_chrec
3032 build_int_cst (NULL_TREE
, x0
),
3033 build_int_cst (NULL_TREE
, i1
));
3034 *overlaps_b
= build_polynomial_chrec
3036 build_int_cst (NULL_TREE
, y0
),
3037 build_int_cst (NULL_TREE
, j1
));
3038 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
3043 /* FIXME: For the moment, the upper bound of the
3044 iteration domain for j is not checked. */
3045 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3046 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
3047 *overlaps_a
= chrec_dont_know
;
3048 *overlaps_b
= chrec_dont_know
;
3049 *last_conflicts
= chrec_dont_know
;
3055 /* FIXME: For the moment, the upper bound of the
3056 iteration domain for i is not checked. */
3057 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3058 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
3059 *overlaps_a
= chrec_dont_know
;
3060 *overlaps_b
= chrec_dont_know
;
3061 *last_conflicts
= chrec_dont_know
;
3067 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3068 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
3069 *overlaps_a
= chrec_dont_know
;
3070 *overlaps_b
= chrec_dont_know
;
3071 *last_conflicts
= chrec_dont_know
;
3077 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3078 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
3079 *overlaps_a
= chrec_dont_know
;
3080 *overlaps_b
= chrec_dont_know
;
3081 *last_conflicts
= chrec_dont_know
;
3084 end_analyze_subs_aa
:
3085 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3087 fprintf (dump_file
, " (overlaps_a = ");
3088 print_generic_expr (dump_file
, *overlaps_a
, 0);
3089 fprintf (dump_file
, ")\n (overlaps_b = ");
3090 print_generic_expr (dump_file
, *overlaps_b
, 0);
3091 fprintf (dump_file
, ")\n");
3092 fprintf (dump_file
, ")\n");
3096 /* Returns true when analyze_subscript_affine_affine can be used for
3097 determining the dependence relation between chrec_a and chrec_b,
3098 that contain symbols. This function modifies chrec_a and chrec_b
3099 such that the analysis result is the same, and such that they don't
3100 contain symbols, and then can safely be passed to the analyzer.
3102 Example: The analysis of the following tuples of evolutions produce
3103 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
3106 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
3107 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
3111 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
3113 tree diff
, type
, left_a
, left_b
, right_b
;
3115 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
3116 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
3117 /* FIXME: For the moment not handled. Might be refined later. */
3120 type
= chrec_type (*chrec_a
);
3121 left_a
= CHREC_LEFT (*chrec_a
);
3122 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL_TREE
);
3123 diff
= chrec_fold_minus (type
, left_a
, left_b
);
3125 if (!evolution_function_is_constant_p (diff
))
3128 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3129 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
3131 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
3132 diff
, CHREC_RIGHT (*chrec_a
));
3133 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL_TREE
);
3134 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
3135 build_int_cst (type
, 0),
3140 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
3141 *OVERLAPS_B are initialized to the functions that describe the
3142 relation between the elements accessed twice by CHREC_A and
3143 CHREC_B. For k >= 0, the following property is verified:
3145 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
3148 analyze_siv_subscript (tree chrec_a
,
3152 tree
*last_conflicts
)
3154 dependence_stats
.num_siv
++;
3156 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3157 fprintf (dump_file
, "(analyze_siv_subscript \n");
3159 if (evolution_function_is_constant_p (chrec_a
)
3160 && evolution_function_is_affine_p (chrec_b
))
3161 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
3162 overlaps_a
, overlaps_b
, last_conflicts
);
3164 else if (evolution_function_is_affine_p (chrec_a
)
3165 && evolution_function_is_constant_p (chrec_b
))
3166 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
3167 overlaps_b
, overlaps_a
, last_conflicts
);
3169 else if (evolution_function_is_affine_p (chrec_a
)
3170 && evolution_function_is_affine_p (chrec_b
))
3172 if (!chrec_contains_symbols (chrec_a
)
3173 && !chrec_contains_symbols (chrec_b
))
3175 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
3176 overlaps_a
, overlaps_b
,
3179 if (*overlaps_a
== chrec_dont_know
3180 || *overlaps_b
== chrec_dont_know
)
3181 dependence_stats
.num_siv_unimplemented
++;
3182 else if (*overlaps_a
== chrec_known
3183 || *overlaps_b
== chrec_known
)
3184 dependence_stats
.num_siv_independent
++;
3186 dependence_stats
.num_siv_dependent
++;
3188 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
3191 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
3192 overlaps_a
, overlaps_b
,
3194 /* FIXME: The number of iterations is a symbolic expression.
3195 Compute it properly. */
3196 *last_conflicts
= chrec_dont_know
;
3198 if (*overlaps_a
== chrec_dont_know
3199 || *overlaps_b
== chrec_dont_know
)
3200 dependence_stats
.num_siv_unimplemented
++;
3201 else if (*overlaps_a
== chrec_known
3202 || *overlaps_b
== chrec_known
)
3203 dependence_stats
.num_siv_independent
++;
3205 dependence_stats
.num_siv_dependent
++;
3208 goto siv_subscript_dontknow
;
3213 siv_subscript_dontknow
:;
3214 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3215 fprintf (dump_file
, "siv test failed: unimplemented.\n");
3216 *overlaps_a
= chrec_dont_know
;
3217 *overlaps_b
= chrec_dont_know
;
3218 *last_conflicts
= chrec_dont_know
;
3219 dependence_stats
.num_siv_unimplemented
++;
3222 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3223 fprintf (dump_file
, ")\n");
3226 /* Return true when the property can be computed. RES should contain
3227 true when calling the first time this function, then it is set to
3228 false when one of the evolution steps of an affine CHREC does not
3229 divide the constant CST. */
3232 chrec_steps_divide_constant_p (tree chrec
,
3236 switch (TREE_CODE (chrec
))
3238 case POLYNOMIAL_CHREC
:
3239 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
)))
3241 if (tree_fold_divides_p (CHREC_RIGHT (chrec
), cst
))
3242 /* Keep RES to true, and iterate on other dimensions. */
3243 return chrec_steps_divide_constant_p (CHREC_LEFT (chrec
), cst
, res
);
3249 /* When the step is a parameter the result is undetermined. */
3253 /* On the initial condition, return true. */
3258 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
3259 *OVERLAPS_B are initialized to the functions that describe the
3260 relation between the elements accessed twice by CHREC_A and
3261 CHREC_B. For k >= 0, the following property is verified:
3263 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
3266 analyze_miv_subscript (tree chrec_a
,
3270 tree
*last_conflicts
)
3272 /* FIXME: This is a MIV subscript, not yet handled.
3273 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
3276 In the SIV test we had to solve a Diophantine equation with two
3277 variables. In the MIV case we have to solve a Diophantine
3278 equation with 2*n variables (if the subscript uses n IVs).
3280 bool divide_p
= true;
3282 dependence_stats
.num_miv
++;
3283 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3284 fprintf (dump_file
, "(analyze_miv_subscript \n");
3286 chrec_a
= chrec_convert (integer_type_node
, chrec_a
, NULL_TREE
);
3287 chrec_b
= chrec_convert (integer_type_node
, chrec_b
, NULL_TREE
);
3288 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
3290 if (eq_evolutions_p (chrec_a
, chrec_b
))
3292 /* Access functions are the same: all the elements are accessed
3293 in the same order. */
3294 *overlaps_a
= integer_zero_node
;
3295 *overlaps_b
= integer_zero_node
;
3296 *last_conflicts
= get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a
));
3297 dependence_stats
.num_miv_dependent
++;
3300 else if (evolution_function_is_constant_p (difference
)
3301 /* For the moment, the following is verified:
3302 evolution_function_is_affine_multivariate_p (chrec_a) */
3303 && chrec_steps_divide_constant_p (chrec_a
, difference
, ÷_p
)
3306 /* testsuite/.../ssa-chrec-33.c
3307 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
3309 The difference is 1, and the evolution steps are equal to 2,
3310 consequently there are no overlapping elements. */
3311 *overlaps_a
= chrec_known
;
3312 *overlaps_b
= chrec_known
;
3313 *last_conflicts
= integer_zero_node
;
3314 dependence_stats
.num_miv_independent
++;
3317 else if (evolution_function_is_affine_multivariate_p (chrec_a
)
3318 && !chrec_contains_symbols (chrec_a
)
3319 && evolution_function_is_affine_multivariate_p (chrec_b
)
3320 && !chrec_contains_symbols (chrec_b
))
3322 /* testsuite/.../ssa-chrec-35.c
3323 {0, +, 1}_2 vs. {0, +, 1}_3
3324 the overlapping elements are respectively located at iterations:
3325 {0, +, 1}_x and {0, +, 1}_x,
3326 in other words, we have the equality:
3327 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
3330 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
3331 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
3333 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
3334 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
3336 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
3337 overlaps_a
, overlaps_b
, last_conflicts
);
3339 if (*overlaps_a
== chrec_dont_know
3340 || *overlaps_b
== chrec_dont_know
)
3341 dependence_stats
.num_miv_unimplemented
++;
3342 else if (*overlaps_a
== chrec_known
3343 || *overlaps_b
== chrec_known
)
3344 dependence_stats
.num_miv_independent
++;
3346 dependence_stats
.num_miv_dependent
++;
3351 /* When the analysis is too difficult, answer "don't know". */
3352 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3353 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
3355 *overlaps_a
= chrec_dont_know
;
3356 *overlaps_b
= chrec_dont_know
;
3357 *last_conflicts
= chrec_dont_know
;
3358 dependence_stats
.num_miv_unimplemented
++;
3361 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3362 fprintf (dump_file
, ")\n");
3365 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
3366 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
3367 two functions that describe the iterations that contain conflicting
3370 Remark: For an integer k >= 0, the following equality is true:
3372 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
3376 analyze_overlapping_iterations (tree chrec_a
,
3378 tree
*overlap_iterations_a
,
3379 tree
*overlap_iterations_b
,
3380 tree
*last_conflicts
)
3382 dependence_stats
.num_subscript_tests
++;
3384 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3386 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
3387 fprintf (dump_file
, " (chrec_a = ");
3388 print_generic_expr (dump_file
, chrec_a
, 0);
3389 fprintf (dump_file
, ")\n (chrec_b = ");
3390 print_generic_expr (dump_file
, chrec_b
, 0);
3391 fprintf (dump_file
, ")\n");
3394 if (chrec_a
== NULL_TREE
3395 || chrec_b
== NULL_TREE
3396 || chrec_contains_undetermined (chrec_a
)
3397 || chrec_contains_undetermined (chrec_b
))
3399 dependence_stats
.num_subscript_undetermined
++;
3401 *overlap_iterations_a
= chrec_dont_know
;
3402 *overlap_iterations_b
= chrec_dont_know
;
3405 /* If they are the same chrec, and are affine, they overlap
3406 on every iteration. */
3407 else if (eq_evolutions_p (chrec_a
, chrec_b
)
3408 && evolution_function_is_affine_multivariate_p (chrec_a
))
3410 dependence_stats
.num_same_subscript_function
++;
3411 *overlap_iterations_a
= integer_zero_node
;
3412 *overlap_iterations_b
= integer_zero_node
;
3413 *last_conflicts
= chrec_dont_know
;
3416 /* If they aren't the same, and aren't affine, we can't do anything
3418 else if ((chrec_contains_symbols (chrec_a
)
3419 || chrec_contains_symbols (chrec_b
))
3420 && (!evolution_function_is_affine_multivariate_p (chrec_a
)
3421 || !evolution_function_is_affine_multivariate_p (chrec_b
)))
3423 dependence_stats
.num_subscript_undetermined
++;
3424 *overlap_iterations_a
= chrec_dont_know
;
3425 *overlap_iterations_b
= chrec_dont_know
;
3428 else if (ziv_subscript_p (chrec_a
, chrec_b
))
3429 analyze_ziv_subscript (chrec_a
, chrec_b
,
3430 overlap_iterations_a
, overlap_iterations_b
,
3433 else if (siv_subscript_p (chrec_a
, chrec_b
))
3434 analyze_siv_subscript (chrec_a
, chrec_b
,
3435 overlap_iterations_a
, overlap_iterations_b
,
3439 analyze_miv_subscript (chrec_a
, chrec_b
,
3440 overlap_iterations_a
, overlap_iterations_b
,
3443 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3445 fprintf (dump_file
, " (overlap_iterations_a = ");
3446 print_generic_expr (dump_file
, *overlap_iterations_a
, 0);
3447 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
3448 print_generic_expr (dump_file
, *overlap_iterations_b
, 0);
3449 fprintf (dump_file
, ")\n");
3450 fprintf (dump_file
, ")\n");
3454 /* Helper function for uniquely inserting distance vectors. */
3457 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
3462 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, v
); i
++)
3463 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
3466 VEC_safe_push (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
), dist_v
);
3469 /* Helper function for uniquely inserting direction vectors. */
3472 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
3477 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), i
, v
); i
++)
3478 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
3481 VEC_safe_push (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
), dir_v
);
3484 /* Add a distance of 1 on all the loops outer than INDEX. If we
3485 haven't yet determined a distance for this outer loop, push a new
3486 distance vector composed of the previous distance, and a distance
3487 of 1 for this outer loop. Example:
3495 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
3496 save (0, 1), then we have to save (1, 0). */
3499 add_outer_distances (struct data_dependence_relation
*ddr
,
3500 lambda_vector dist_v
, int index
)
3502 /* For each outer loop where init_v is not set, the accesses are
3503 in dependence of distance 1 in the loop. */
3504 while (--index
>= 0)
3506 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3507 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3509 save_dist_v (ddr
, save_v
);
3513 /* Return false when fail to represent the data dependence as a
3514 distance vector. INIT_B is set to true when a component has been
3515 added to the distance vector DIST_V. INDEX_CARRY is then set to
3516 the index in DIST_V that carries the dependence. */
3519 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
3520 struct data_reference
*ddr_a
,
3521 struct data_reference
*ddr_b
,
3522 lambda_vector dist_v
, bool *init_b
,
3526 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3528 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3530 tree access_fn_a
, access_fn_b
;
3531 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
3533 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
3535 non_affine_dependence_relation (ddr
);
3539 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
3540 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
3542 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
3543 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
3546 int index_a
= index_in_loop_nest (CHREC_VARIABLE (access_fn_a
),
3547 DDR_LOOP_NEST (ddr
));
3548 int index_b
= index_in_loop_nest (CHREC_VARIABLE (access_fn_b
),
3549 DDR_LOOP_NEST (ddr
));
3551 /* The dependence is carried by the outermost loop. Example:
3558 In this case, the dependence is carried by loop_1. */
3559 index
= index_a
< index_b
? index_a
: index_b
;
3560 *index_carry
= MIN (index
, *index_carry
);
3562 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
3564 non_affine_dependence_relation (ddr
);
3568 dist
= int_cst_value (SUB_DISTANCE (subscript
));
3570 /* This is the subscript coupling test. If we have already
3571 recorded a distance for this loop (a distance coming from
3572 another subscript), it should be the same. For example,
3573 in the following code, there is no dependence:
3580 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
3582 finalize_ddr_dependent (ddr
, chrec_known
);
3586 dist_v
[index
] = dist
;
3592 /* This can be for example an affine vs. constant dependence
3593 (T[i] vs. T[3]) that is not an affine dependence and is
3594 not representable as a distance vector. */
3595 non_affine_dependence_relation (ddr
);
3603 /* Return true when the DDR contains two data references that have the
3604 same access functions. */
3607 same_access_functions (struct data_dependence_relation
*ddr
)
3611 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3612 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr
), i
),
3613 DR_ACCESS_FN (DDR_B (ddr
), i
)))
3619 /* Helper function for the case where DDR_A and DDR_B are the same
3620 multivariate access function. */
3623 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
3626 tree c_1
= CHREC_LEFT (c_2
);
3627 tree c_0
= CHREC_LEFT (c_1
);
3628 lambda_vector dist_v
;
3630 /* Polynomials with more than 2 variables are not handled yet. */
3631 if (TREE_CODE (c_0
) != INTEGER_CST
)
3633 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
3637 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
3638 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
3640 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3641 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3642 dist_v
[x_1
] = int_cst_value (CHREC_RIGHT (c_2
));
3643 dist_v
[x_2
] = -int_cst_value (CHREC_RIGHT (c_1
));
3644 save_dist_v (ddr
, dist_v
);
3646 add_outer_distances (ddr
, dist_v
, x_1
);
3649 /* Helper function for the case where DDR_A and DDR_B are the same
3650 access functions. */
3653 add_other_self_distances (struct data_dependence_relation
*ddr
)
3655 lambda_vector dist_v
;
3657 int index_carry
= DDR_NB_LOOPS (ddr
);
3659 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3661 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
3663 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
3665 if (!evolution_function_is_univariate_p (access_fun
))
3667 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
3669 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
3673 add_multivariate_self_dist (ddr
, DR_ACCESS_FN (DDR_A (ddr
), 0));
3677 index_carry
= MIN (index_carry
,
3678 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
3679 DDR_LOOP_NEST (ddr
)));
3683 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3684 add_outer_distances (ddr
, dist_v
, index_carry
);
3687 /* Compute the classic per loop distance vector. DDR is the data
3688 dependence relation to build a vector from. Return false when fail
3689 to represent the data dependence as a distance vector. */
3692 build_classic_dist_vector (struct data_dependence_relation
*ddr
)
3694 bool init_b
= false;
3695 int index_carry
= DDR_NB_LOOPS (ddr
);
3696 lambda_vector dist_v
;
3698 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3701 if (same_access_functions (ddr
))
3703 /* Save the 0 vector. */
3704 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3705 save_dist_v (ddr
, dist_v
);
3707 if (DDR_NB_LOOPS (ddr
) > 1)
3708 add_other_self_distances (ddr
);
3713 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3714 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
3715 dist_v
, &init_b
, &index_carry
))
3718 /* Save the distance vector if we initialized one. */
3721 /* Verify a basic constraint: classic distance vectors should
3722 always be lexicographically positive.
3724 Data references are collected in the order of execution of
3725 the program, thus for the following loop
3727 | for (i = 1; i < 100; i++)
3728 | for (j = 1; j < 100; j++)
3730 | t = T[j+1][i-1]; // A
3731 | T[j][i] = t + 2; // B
3734 references are collected following the direction of the wind:
3735 A then B. The data dependence tests are performed also
3736 following this order, such that we're looking at the distance
3737 separating the elements accessed by A from the elements later
3738 accessed by B. But in this example, the distance returned by
3739 test_dep (A, B) is lexicographically negative (-1, 1), that
3740 means that the access A occurs later than B with respect to
3741 the outer loop, ie. we're actually looking upwind. In this
3742 case we solve test_dep (B, A) looking downwind to the
3743 lexicographically positive solution, that returns the
3744 distance vector (1, -1). */
3745 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
3747 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3748 subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
));
3749 compute_subscript_distance (ddr
);
3750 build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3751 save_v
, &init_b
, &index_carry
);
3752 save_dist_v (ddr
, save_v
);
3754 /* In this case there is a dependence forward for all the
3757 | for (k = 1; k < 100; k++)
3758 | for (i = 1; i < 100; i++)
3759 | for (j = 1; j < 100; j++)
3761 | t = T[j+1][i-1]; // A
3762 | T[j][i] = t + 2; // B
3770 if (DDR_NB_LOOPS (ddr
) > 1)
3772 add_outer_distances (ddr
, save_v
, index_carry
);
3773 add_outer_distances (ddr
, dist_v
, index_carry
);
3778 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3779 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3780 save_dist_v (ddr
, save_v
);
3782 if (DDR_NB_LOOPS (ddr
) > 1)
3784 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3786 subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
));
3787 compute_subscript_distance (ddr
);
3788 build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3789 opposite_v
, &init_b
, &index_carry
);
3791 add_outer_distances (ddr
, dist_v
, index_carry
);
3792 add_outer_distances (ddr
, opposite_v
, index_carry
);
3798 /* There is a distance of 1 on all the outer loops: Example:
3799 there is a dependence of distance 1 on loop_1 for the array A.
3805 add_outer_distances (ddr
, dist_v
,
3806 lambda_vector_first_nz (dist_v
,
3807 DDR_NB_LOOPS (ddr
), 0));
3810 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3814 fprintf (dump_file
, "(build_classic_dist_vector\n");
3815 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
3817 fprintf (dump_file
, " dist_vector = (");
3818 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
3819 DDR_NB_LOOPS (ddr
));
3820 fprintf (dump_file
, " )\n");
3822 fprintf (dump_file
, ")\n");
3828 /* Return the direction for a given distance.
3829 FIXME: Computing dir this way is suboptimal, since dir can catch
3830 cases that dist is unable to represent. */
3832 static inline enum data_dependence_direction
3833 dir_from_dist (int dist
)
3836 return dir_positive
;
3838 return dir_negative
;
3843 /* Compute the classic per loop direction vector. DDR is the data
3844 dependence relation to build a vector from. */
3847 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
3850 lambda_vector dist_v
;
3852 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, dist_v
); i
++)
3854 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3856 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
3857 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
3859 save_dir_v (ddr
, dir_v
);
3863 /* Helper function. Returns true when there is a dependence between
3864 data references DRA and DRB. */
3867 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
3868 struct data_reference
*dra
,
3869 struct data_reference
*drb
)
3872 tree last_conflicts
;
3873 struct subscript
*subscript
;
3875 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
3878 tree overlaps_a
, overlaps_b
;
3880 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
3881 DR_ACCESS_FN (drb
, i
),
3882 &overlaps_a
, &overlaps_b
,
3885 if (chrec_contains_undetermined (overlaps_a
)
3886 || chrec_contains_undetermined (overlaps_b
))
3888 finalize_ddr_dependent (ddr
, chrec_dont_know
);
3889 dependence_stats
.num_dependence_undetermined
++;
3893 else if (overlaps_a
== chrec_known
3894 || overlaps_b
== chrec_known
)
3896 finalize_ddr_dependent (ddr
, chrec_known
);
3897 dependence_stats
.num_dependence_independent
++;
3903 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
3904 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
3905 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
3912 /* Computes the conflicting iterations, and initialize DDR. */
3915 subscript_dependence_tester (struct data_dependence_relation
*ddr
)
3918 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3919 fprintf (dump_file
, "(subscript_dependence_tester \n");
3921 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
)))
3922 dependence_stats
.num_dependence_dependent
++;
3924 compute_subscript_distance (ddr
);
3925 if (build_classic_dist_vector (ddr
))
3926 build_classic_dir_vector (ddr
);
3928 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3929 fprintf (dump_file
, ")\n");
3932 /* Returns true when all the access functions of A are affine or
3936 access_functions_are_affine_or_constant_p (struct data_reference
*a
)
3939 VEC(tree
,heap
) **fns
= DR_ACCESS_FNS_ADDR (a
);
3942 for (i
= 0; VEC_iterate (tree
, *fns
, i
, t
); i
++)
3943 if (!evolution_function_is_constant_p (t
)
3944 && !evolution_function_is_affine_multivariate_p (t
))
3950 /* This computes the affine dependence relation between A and B.
3951 CHREC_KNOWN is used for representing the independence between two
3952 accesses, while CHREC_DONT_KNOW is used for representing the unknown
3955 Note that it is possible to stop the computation of the dependence
3956 relation the first time we detect a CHREC_KNOWN element for a given
3960 compute_affine_dependence (struct data_dependence_relation
*ddr
)
3962 struct data_reference
*dra
= DDR_A (ddr
);
3963 struct data_reference
*drb
= DDR_B (ddr
);
3965 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3967 fprintf (dump_file
, "(compute_affine_dependence\n");
3968 fprintf (dump_file
, " (stmt_a = \n");
3969 print_generic_expr (dump_file
, DR_STMT (dra
), 0);
3970 fprintf (dump_file
, ")\n (stmt_b = \n");
3971 print_generic_expr (dump_file
, DR_STMT (drb
), 0);
3972 fprintf (dump_file
, ")\n");
3975 /* Analyze only when the dependence relation is not yet known. */
3976 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
3978 dependence_stats
.num_dependence_tests
++;
3980 if (access_functions_are_affine_or_constant_p (dra
)
3981 && access_functions_are_affine_or_constant_p (drb
))
3982 subscript_dependence_tester (ddr
);
3984 /* As a last case, if the dependence cannot be determined, or if
3985 the dependence is considered too difficult to determine, answer
3989 dependence_stats
.num_dependence_undetermined
++;
3991 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3993 fprintf (dump_file
, "Data ref a:\n");
3994 dump_data_reference (dump_file
, dra
);
3995 fprintf (dump_file
, "Data ref b:\n");
3996 dump_data_reference (dump_file
, drb
);
3997 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
3999 finalize_ddr_dependent (ddr
, chrec_dont_know
);
4003 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4004 fprintf (dump_file
, ")\n");
4007 /* This computes the dependence relation for the same data
4008 reference into DDR. */
4011 compute_self_dependence (struct data_dependence_relation
*ddr
)
4014 struct subscript
*subscript
;
4016 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
4019 /* The accessed index overlaps for each iteration. */
4020 SUB_CONFLICTS_IN_A (subscript
) = integer_zero_node
;
4021 SUB_CONFLICTS_IN_B (subscript
) = integer_zero_node
;
4022 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
4025 /* The distance vector is the zero vector. */
4026 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
4027 save_dir_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
4030 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4031 the data references in DATAREFS, in the LOOP_NEST. When
4032 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4036 compute_all_dependences (VEC (data_reference_p
, heap
) *datarefs
,
4037 VEC (ddr_p
, heap
) **dependence_relations
,
4038 VEC (loop_p
, heap
) *loop_nest
,
4039 bool compute_self_and_rr
)
4041 struct data_dependence_relation
*ddr
;
4042 struct data_reference
*a
, *b
;
4045 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
4046 for (j
= i
+ 1; VEC_iterate (data_reference_p
, datarefs
, j
, b
); j
++)
4047 if (!DR_IS_READ (a
) || !DR_IS_READ (b
) || compute_self_and_rr
)
4049 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
4050 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4051 compute_affine_dependence (ddr
);
4054 if (compute_self_and_rr
)
4055 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
4057 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
4058 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4059 compute_self_dependence (ddr
);
4063 /* Search the data references in LOOP, and record the information into
4064 DATAREFS. Returns chrec_dont_know when failing to analyze a
4065 difficult case, returns NULL_TREE otherwise.
4067 TODO: This function should be made smarter so that it can handle address
4068 arithmetic as if they were array accesses, etc. */
4071 find_data_references_in_loop (struct loop
*loop
,
4072 VEC (data_reference_p
, heap
) **datarefs
)
4074 basic_block bb
, *bbs
;
4076 block_stmt_iterator bsi
;
4077 struct data_reference
*dr
;
4079 bbs
= get_loop_body (loop
);
4081 for (i
= 0; i
< loop
->num_nodes
; i
++)
4085 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4087 tree stmt
= bsi_stmt (bsi
);
4089 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4090 Calls have side-effects, except those to const or pure
4092 if ((TREE_CODE (stmt
) == CALL_EXPR
4093 && !(call_expr_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
4094 || (TREE_CODE (stmt
) == ASM_EXPR
4095 && ASM_VOLATILE_P (stmt
)))
4096 goto insert_dont_know_node
;
4098 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
4101 switch (TREE_CODE (stmt
))
4105 bool one_inserted
= false;
4106 tree opnd0
= TREE_OPERAND (stmt
, 0);
4107 tree opnd1
= TREE_OPERAND (stmt
, 1);
4109 if (TREE_CODE (opnd0
) == ARRAY_REF
4110 || TREE_CODE (opnd0
) == INDIRECT_REF
4111 || TREE_CODE (opnd0
) == COMPONENT_REF
)
4113 dr
= create_data_ref (opnd0
, stmt
, false);
4116 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4117 one_inserted
= true;
4121 if (TREE_CODE (opnd1
) == ARRAY_REF
4122 || TREE_CODE (opnd1
) == INDIRECT_REF
4123 || TREE_CODE (opnd1
) == COMPONENT_REF
)
4125 dr
= create_data_ref (opnd1
, stmt
, true);
4128 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4129 one_inserted
= true;
4134 goto insert_dont_know_node
;
4142 bool one_inserted
= false;
4144 for (args
= TREE_OPERAND (stmt
, 1); args
;
4145 args
= TREE_CHAIN (args
))
4146 if (TREE_CODE (TREE_VALUE (args
)) == ARRAY_REF
4147 || TREE_CODE (TREE_VALUE (args
)) == INDIRECT_REF
4148 || TREE_CODE (TREE_VALUE (args
)) == COMPONENT_REF
)
4150 dr
= create_data_ref (TREE_VALUE (args
), stmt
, true);
4153 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4154 one_inserted
= true;
4159 goto insert_dont_know_node
;
4166 struct data_reference
*res
;
4168 insert_dont_know_node
:;
4169 res
= XNEW (struct data_reference
);
4170 DR_STMT (res
) = NULL_TREE
;
4171 DR_REF (res
) = NULL_TREE
;
4172 DR_BASE_OBJECT (res
) = NULL
;
4173 DR_TYPE (res
) = ARRAY_REF_TYPE
;
4174 DR_SET_ACCESS_FNS (res
, NULL
);
4175 DR_BASE_OBJECT (res
) = NULL
;
4176 DR_IS_READ (res
) = false;
4177 DR_BASE_ADDRESS (res
) = NULL_TREE
;
4178 DR_OFFSET (res
) = NULL_TREE
;
4179 DR_INIT (res
) = NULL_TREE
;
4180 DR_STEP (res
) = NULL_TREE
;
4181 DR_OFFSET_MISALIGNMENT (res
) = NULL_TREE
;
4182 DR_MEMTAG (res
) = NULL_TREE
;
4183 DR_PTR_INFO (res
) = NULL
;
4184 VEC_safe_push (data_reference_p
, heap
, *datarefs
, res
);
4187 return chrec_dont_know
;
4191 /* When there are no defs in the loop, the loop is parallel. */
4192 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_VIRTUAL_DEFS
))
4193 loop
->parallel_p
= false;
4202 /* Recursive helper function. */
4205 find_loop_nest_1 (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4207 /* Inner loops of the nest should not contain siblings. Example:
4208 when there are two consecutive loops,
4219 the dependence relation cannot be captured by the distance
4224 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4226 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4230 /* Return false when the LOOP is not well nested. Otherwise return
4231 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4232 contain the loops from the outermost to the innermost, as they will
4233 appear in the classic distance vector. */
4236 find_loop_nest (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
4238 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
4240 return find_loop_nest_1 (loop
->inner
, loop_nest
);
4244 /* Given a loop nest LOOP, the following vectors are returned:
4245 DATAREFS is initialized to all the array elements contained in this loop,
4246 DEPENDENCE_RELATIONS contains the relations between the data references.
4247 Compute read-read and self relations if
4248 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4251 compute_data_dependences_for_loop (struct loop
*loop
,
4252 bool compute_self_and_read_read_dependences
,
4253 VEC (data_reference_p
, heap
) **datarefs
,
4254 VEC (ddr_p
, heap
) **dependence_relations
)
4256 struct loop
*loop_nest
= loop
;
4257 VEC (loop_p
, heap
) *vloops
= VEC_alloc (loop_p
, heap
, 3);
4259 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
4261 /* If the loop nest is not well formed, or one of the data references
4262 is not computable, give up without spending time to compute other
4265 || !find_loop_nest (loop_nest
, &vloops
)
4266 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
4268 struct data_dependence_relation
*ddr
;
4270 /* Insert a single relation into dependence_relations:
4272 ddr
= initialize_data_dependence_relation (NULL
, NULL
, vloops
);
4273 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4276 compute_all_dependences (*datarefs
, dependence_relations
, vloops
,
4277 compute_self_and_read_read_dependences
);
4279 if (dump_file
&& (dump_flags
& TDF_STATS
))
4281 fprintf (dump_file
, "Dependence tester statistics:\n");
4283 fprintf (dump_file
, "Number of dependence tests: %d\n",
4284 dependence_stats
.num_dependence_tests
);
4285 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
4286 dependence_stats
.num_dependence_dependent
);
4287 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
4288 dependence_stats
.num_dependence_independent
);
4289 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
4290 dependence_stats
.num_dependence_undetermined
);
4292 fprintf (dump_file
, "Number of subscript tests: %d\n",
4293 dependence_stats
.num_subscript_tests
);
4294 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
4295 dependence_stats
.num_subscript_undetermined
);
4296 fprintf (dump_file
, "Number of same subscript function: %d\n",
4297 dependence_stats
.num_same_subscript_function
);
4299 fprintf (dump_file
, "Number of ziv tests: %d\n",
4300 dependence_stats
.num_ziv
);
4301 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
4302 dependence_stats
.num_ziv_dependent
);
4303 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
4304 dependence_stats
.num_ziv_independent
);
4305 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
4306 dependence_stats
.num_ziv_unimplemented
);
4308 fprintf (dump_file
, "Number of siv tests: %d\n",
4309 dependence_stats
.num_siv
);
4310 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
4311 dependence_stats
.num_siv_dependent
);
4312 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
4313 dependence_stats
.num_siv_independent
);
4314 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
4315 dependence_stats
.num_siv_unimplemented
);
4317 fprintf (dump_file
, "Number of miv tests: %d\n",
4318 dependence_stats
.num_miv
);
4319 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
4320 dependence_stats
.num_miv_dependent
);
4321 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
4322 dependence_stats
.num_miv_independent
);
4323 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
4324 dependence_stats
.num_miv_unimplemented
);
4328 /* Entry point (for testing only). Analyze all the data references
4329 and the dependence relations.
4331 The data references are computed first.
4333 A relation on these nodes is represented by a complete graph. Some
4334 of the relations could be of no interest, thus the relations can be
4337 In the following function we compute all the relations. This is
4338 just a first implementation that is here for:
4339 - for showing how to ask for the dependence relations,
4340 - for the debugging the whole dependence graph,
4341 - for the dejagnu testcases and maintenance.
4343 It is possible to ask only for a part of the graph, avoiding to
4344 compute the whole dependence graph. The computed dependences are
4345 stored in a knowledge base (KB) such that later queries don't
4346 recompute the same information. The implementation of this KB is
4347 transparent to the optimizer, and thus the KB can be changed with a
4348 more efficient implementation, or the KB could be disabled. */
4351 analyze_all_data_dependences (struct loops
*loops
)
4354 int nb_data_refs
= 10;
4355 VEC (data_reference_p
, heap
) *datarefs
=
4356 VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
4357 VEC (ddr_p
, heap
) *dependence_relations
=
4358 VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
);
4360 /* Compute DDs on the whole function. */
4361 compute_data_dependences_for_loop (loops
->parray
[0], false,
4362 &datarefs
, &dependence_relations
);
4366 dump_data_dependence_relations (dump_file
, dependence_relations
);
4367 fprintf (dump_file
, "\n\n");
4369 if (dump_flags
& TDF_DETAILS
)
4370 dump_dist_dir_vectors (dump_file
, dependence_relations
);
4372 if (dump_flags
& TDF_STATS
)
4374 unsigned nb_top_relations
= 0;
4375 unsigned nb_bot_relations
= 0;
4376 unsigned nb_basename_differ
= 0;
4377 unsigned nb_chrec_relations
= 0;
4378 struct data_dependence_relation
*ddr
;
4380 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4382 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
4385 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
4387 struct data_reference
*a
= DDR_A (ddr
);
4388 struct data_reference
*b
= DDR_B (ddr
);
4391 if ((DR_BASE_OBJECT (a
) && DR_BASE_OBJECT (b
)
4392 && DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
))
4393 || (base_object_differ_p (a
, b
, &differ_p
)
4395 nb_basename_differ
++;
4401 nb_chrec_relations
++;
4404 gather_stats_on_scev_database ();
4408 free_dependence_relations (dependence_relations
);
4409 free_data_refs (datarefs
);
4413 /* Free the memory used by a data dependence relation DDR. */
4416 free_dependence_relation (struct data_dependence_relation
*ddr
)
4421 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_SUBSCRIPTS (ddr
))
4422 VEC_free (subscript_p
, heap
, DDR_SUBSCRIPTS (ddr
));
4427 /* Free the memory used by the data dependence relations from
4428 DEPENDENCE_RELATIONS. */
4431 free_dependence_relations (VEC (ddr_p
, heap
) *dependence_relations
)
4434 struct data_dependence_relation
*ddr
;
4435 VEC (loop_p
, heap
) *loop_nest
= NULL
;
4437 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
4441 if (loop_nest
== NULL
)
4442 loop_nest
= DDR_LOOP_NEST (ddr
);
4444 gcc_assert (DDR_LOOP_NEST (ddr
) == NULL
4445 || DDR_LOOP_NEST (ddr
) == loop_nest
);
4446 free_dependence_relation (ddr
);
4450 VEC_free (loop_p
, heap
, loop_nest
);
4451 VEC_free (ddr_p
, heap
, dependence_relations
);
4454 /* Free the memory used by the data references from DATAREFS. */
4457 free_data_refs (VEC (data_reference_p
, heap
) *datarefs
)
4460 struct data_reference
*dr
;
4462 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
4464 VEC_free (data_reference_p
, heap
, datarefs
);