1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 /* This pass walks a given loop structure searching for array
23 references. The information about the array accesses is recorded
24 in DATA_REFERENCE structures.
26 The basic test for determining the dependences is:
27 given two access functions chrec1 and chrec2 to a same array, and
28 x and y two vectors from the iteration domain, the same element of
29 the array is accessed twice at iterations x and y if and only if:
30 | chrec1 (x) == chrec2 (y).
32 The goals of this analysis are:
34 - to determine the independence: the relation between two
35 independent accesses is qualified with the chrec_known (this
36 information allows a loop parallelization),
38 - when two data references access the same data, to qualify the
39 dependence relation with classic dependence representations:
43 - loop carried level dependence
44 - polyhedron dependence
45 or with the chains of recurrences based representation,
47 - to define a knowledge base for storing the data dependence
50 - to define an interface to access this data.
55 - subscript: given two array accesses a subscript is the tuple
56 composed of the access functions for a given dimension. Example:
57 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
58 (f1, g1), (f2, g2), (f3, g3).
60 - Diophantine equation: an equation whose coefficients and
61 solutions are integer constants, for example the equation
63 has an integer solution x = 1 and y = -1.
67 - "Advanced Compilation for High Performance Computing" by Randy
68 Allen and Ken Kennedy.
69 http://citeseer.ist.psu.edu/goff91practical.html
71 - "Loop Transformations for Restructuring Compilers - The Foundations"
79 #include "coretypes.h"
84 /* These RTL headers are needed for basic-block.h. */
86 #include "basic-block.h"
87 #include "diagnostic.h"
88 #include "tree-flow.h"
89 #include "tree-dump.h"
92 #include "tree-chrec.h"
93 #include "tree-data-ref.h"
94 #include "tree-scalar-evolution.h"
95 #include "tree-pass.h"
96 #include "langhooks.h"
98 static struct datadep_stats
100 int num_dependence_tests
;
101 int num_dependence_dependent
;
102 int num_dependence_independent
;
103 int num_dependence_undetermined
;
105 int num_subscript_tests
;
106 int num_subscript_undetermined
;
107 int num_same_subscript_function
;
110 int num_ziv_independent
;
111 int num_ziv_dependent
;
112 int num_ziv_unimplemented
;
115 int num_siv_independent
;
116 int num_siv_dependent
;
117 int num_siv_unimplemented
;
120 int num_miv_independent
;
121 int num_miv_dependent
;
122 int num_miv_unimplemented
;
125 static tree
object_analysis (tree
, tree
, bool, struct data_reference
**,
126 tree
*, tree
*, tree
*, tree
*, tree
*,
127 struct ptr_info_def
**, subvar_t
*);
128 static bool subscript_dependence_tester_1 (struct data_dependence_relation
*,
129 struct data_reference
*,
130 struct data_reference
*);
132 /* Determine if PTR and DECL may alias, the result is put in ALIASED.
133 Return FALSE if there is no symbol memory tag for PTR. */
136 ptr_decl_may_alias_p (tree ptr
, tree decl
,
137 struct data_reference
*ptr_dr
,
140 tree tag
= NULL_TREE
;
141 struct ptr_info_def
*pi
= DR_PTR_INFO (ptr_dr
);
143 gcc_assert (TREE_CODE (ptr
) == SSA_NAME
&& DECL_P (decl
));
146 tag
= pi
->name_mem_tag
;
148 tag
= symbol_mem_tag (SSA_NAME_VAR (ptr
));
150 tag
= DR_MEMTAG (ptr_dr
);
154 *aliased
= is_aliased_with (tag
, decl
);
159 /* Determine if two pointers may alias, the result is put in ALIASED.
160 Return FALSE if there is no symbol memory tag for one of the pointers. */
163 ptr_ptr_may_alias_p (tree ptr_a
, tree ptr_b
,
164 struct data_reference
*dra
,
165 struct data_reference
*drb
,
168 tree tag_a
= NULL_TREE
, tag_b
= NULL_TREE
;
169 struct ptr_info_def
*pi_a
= DR_PTR_INFO (dra
);
170 struct ptr_info_def
*pi_b
= DR_PTR_INFO (drb
);
173 if (pi_a
&& pi_a
->name_mem_tag
&& pi_b
&& pi_b
->name_mem_tag
)
175 tag_a
= pi_a
->name_mem_tag
;
176 tag_b
= pi_b
->name_mem_tag
;
180 tag_a
= symbol_mem_tag (SSA_NAME_VAR (ptr_a
));
182 tag_a
= DR_MEMTAG (dra
);
186 tag_b
= symbol_mem_tag (SSA_NAME_VAR (ptr_b
));
188 tag_b
= DR_MEMTAG (drb
);
192 bal1
= BITMAP_ALLOC (NULL
);
193 bitmap_set_bit (bal1
, DECL_UID (tag_a
));
194 if (MTAG_P (tag_a
) && MTAG_ALIASES (tag_a
))
195 bitmap_ior_into (bal1
, MTAG_ALIASES (tag_a
));
197 bal2
= BITMAP_ALLOC (NULL
);
198 bitmap_set_bit (bal2
, DECL_UID (tag_b
));
199 if (MTAG_P (tag_b
) && MTAG_ALIASES (tag_b
))
200 bitmap_ior_into (bal2
, MTAG_ALIASES (tag_b
));
201 *aliased
= bitmap_intersect_p (bal1
, bal2
);
209 /* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED.
210 Return FALSE if there is no symbol memory tag for one of the symbols. */
213 may_alias_p (tree base_a
, tree base_b
,
214 struct data_reference
*dra
,
215 struct data_reference
*drb
,
218 if (TREE_CODE (base_a
) == ADDR_EXPR
|| TREE_CODE (base_b
) == ADDR_EXPR
)
220 if (TREE_CODE (base_a
) == ADDR_EXPR
&& TREE_CODE (base_b
) == ADDR_EXPR
)
222 *aliased
= (TREE_OPERAND (base_a
, 0) == TREE_OPERAND (base_b
, 0));
225 if (TREE_CODE (base_a
) == ADDR_EXPR
)
226 return ptr_decl_may_alias_p (base_b
, TREE_OPERAND (base_a
, 0), drb
,
229 return ptr_decl_may_alias_p (base_a
, TREE_OPERAND (base_b
, 0), dra
,
233 return ptr_ptr_may_alias_p (base_a
, base_b
, dra
, drb
, aliased
);
237 /* Determine if a pointer (BASE_A) and a record/union access (BASE_B)
238 are not aliased. Return TRUE if they differ. */
240 record_ptr_differ_p (struct data_reference
*dra
,
241 struct data_reference
*drb
)
244 tree base_a
= DR_BASE_OBJECT (dra
);
245 tree base_b
= DR_BASE_OBJECT (drb
);
247 if (TREE_CODE (base_b
) != COMPONENT_REF
)
250 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
251 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
252 Probably will be unnecessary with struct alias analysis. */
253 while (TREE_CODE (base_b
) == COMPONENT_REF
)
254 base_b
= TREE_OPERAND (base_b
, 0);
255 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
257 if (TREE_CODE (base_a
) == INDIRECT_REF
258 && ((TREE_CODE (base_b
) == VAR_DECL
259 && (ptr_decl_may_alias_p (TREE_OPERAND (base_a
, 0), base_b
, dra
,
262 || (TREE_CODE (base_b
) == INDIRECT_REF
263 && (ptr_ptr_may_alias_p (TREE_OPERAND (base_a
, 0),
264 TREE_OPERAND (base_b
, 0), dra
, drb
,
272 /* Determine if two record/union accesses are aliased. Return TRUE if they
275 record_record_differ_p (struct data_reference
*dra
,
276 struct data_reference
*drb
)
279 tree base_a
= DR_BASE_OBJECT (dra
);
280 tree base_b
= DR_BASE_OBJECT (drb
);
282 if (TREE_CODE (base_b
) != COMPONENT_REF
283 || TREE_CODE (base_a
) != COMPONENT_REF
)
286 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
287 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
288 Probably will be unnecessary with struct alias analysis. */
289 while (TREE_CODE (base_b
) == COMPONENT_REF
)
290 base_b
= TREE_OPERAND (base_b
, 0);
291 while (TREE_CODE (base_a
) == COMPONENT_REF
)
292 base_a
= TREE_OPERAND (base_a
, 0);
294 if (TREE_CODE (base_a
) == INDIRECT_REF
295 && TREE_CODE (base_b
) == INDIRECT_REF
296 && ptr_ptr_may_alias_p (TREE_OPERAND (base_a
, 0),
297 TREE_OPERAND (base_b
, 0),
305 /* Determine if an array access (BASE_A) and a record/union access (BASE_B)
306 are not aliased. Return TRUE if they differ. */
308 record_array_differ_p (struct data_reference
*dra
,
309 struct data_reference
*drb
)
312 tree base_a
= DR_BASE_OBJECT (dra
);
313 tree base_b
= DR_BASE_OBJECT (drb
);
315 if (TREE_CODE (base_b
) != COMPONENT_REF
)
318 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
319 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
320 Probably will be unnecessary with struct alias analysis. */
321 while (TREE_CODE (base_b
) == COMPONENT_REF
)
322 base_b
= TREE_OPERAND (base_b
, 0);
324 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
325 (a[i]). In case of p->c[i] use alias analysis to verify that p is not
327 if (TREE_CODE (base_a
) == VAR_DECL
328 && (TREE_CODE (base_b
) == VAR_DECL
329 || (TREE_CODE (base_b
) == INDIRECT_REF
330 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b
, 0), base_a
, drb
,
339 /* Determine if an array access (BASE_A) and a pointer (BASE_B)
340 are not aliased. Return TRUE if they differ. */
342 array_ptr_differ_p (tree base_a
, tree base_b
,
343 struct data_reference
*drb
)
347 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
348 help of alias analysis that p is not pointing to a. */
349 if (TREE_CODE (base_a
) == VAR_DECL
&& TREE_CODE (base_b
) == INDIRECT_REF
350 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b
, 0), base_a
, drb
, &aliased
)
358 /* This is the simplest data dependence test: determines whether the
359 data references A and B access the same array/region. Returns
360 false when the property is not computable at compile time.
361 Otherwise return true, and DIFFER_P will record the result. This
362 utility will not be necessary when alias_sets_conflict_p will be
363 less conservative. */
366 base_object_differ_p (struct data_reference
*a
,
367 struct data_reference
*b
,
370 tree base_a
= DR_BASE_OBJECT (a
);
371 tree base_b
= DR_BASE_OBJECT (b
);
374 if (!base_a
|| !base_b
)
377 /* Determine if same base. Example: for the array accesses
378 a[i], b[i] or pointer accesses *a, *b, bases are a, b. */
379 if (base_a
== base_b
)
385 /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
387 if (TREE_CODE (base_a
) == INDIRECT_REF
&& TREE_CODE (base_b
) == INDIRECT_REF
388 && TREE_OPERAND (base_a
, 0) == TREE_OPERAND (base_b
, 0))
394 /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */
395 if (TREE_CODE (base_a
) == COMPONENT_REF
&& TREE_CODE (base_b
) == COMPONENT_REF
396 && TREE_OPERAND (base_a
, 0) == TREE_OPERAND (base_b
, 0)
397 && TREE_OPERAND (base_a
, 1) == TREE_OPERAND (base_b
, 1))
404 /* Determine if different bases. */
406 /* At this point we know that base_a != base_b. However, pointer
407 accesses of the form x=(*p) and y=(*q), whose bases are p and q,
408 may still be pointing to the same base. In SSAed GIMPLE p and q will
409 be SSA_NAMES in this case. Therefore, here we check if they are
410 really two different declarations. */
411 if (TREE_CODE (base_a
) == VAR_DECL
&& TREE_CODE (base_b
) == VAR_DECL
)
417 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
418 help of alias analysis that p is not pointing to a. */
419 if (array_ptr_differ_p (base_a
, base_b
, b
)
420 || array_ptr_differ_p (base_b
, base_a
, a
))
426 /* If the bases are pointers ((*q)[i] and (*p)[i]), we check with the
427 help of alias analysis they don't point to the same bases. */
428 if (TREE_CODE (base_a
) == INDIRECT_REF
&& TREE_CODE (base_b
) == INDIRECT_REF
429 && (may_alias_p (TREE_OPERAND (base_a
, 0), TREE_OPERAND (base_b
, 0), a
, b
,
437 /* Compare two record/union bases s.a and t.b: s != t or (a != b and
438 s and t are not unions). */
439 if (TREE_CODE (base_a
) == COMPONENT_REF
&& TREE_CODE (base_b
) == COMPONENT_REF
440 && ((TREE_CODE (TREE_OPERAND (base_a
, 0)) == VAR_DECL
441 && TREE_CODE (TREE_OPERAND (base_b
, 0)) == VAR_DECL
442 && TREE_OPERAND (base_a
, 0) != TREE_OPERAND (base_b
, 0))
443 || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a
, 0))) == RECORD_TYPE
444 && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b
, 0))) == RECORD_TYPE
445 && TREE_OPERAND (base_a
, 1) != TREE_OPERAND (base_b
, 1))))
451 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
453 if (record_ptr_differ_p (a
, b
) || record_ptr_differ_p (b
, a
))
459 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
460 (a[i]). In case of p->c[i] use alias analysis to verify that p is not
462 if (record_array_differ_p (a
, b
) || record_array_differ_p (b
, a
))
468 /* Compare two record/union accesses (b.c[i] or p->c[i]). */
469 if (record_record_differ_p (a
, b
))
478 /* Function base_addr_differ_p.
480 This is the simplest data dependence test: determines whether the
481 data references DRA and DRB access the same array/region. Returns
482 false when the property is not computable at compile time.
483 Otherwise return true, and DIFFER_P will record the result.
486 1. if (both DRA and DRB are represented as arrays)
487 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT
488 2. else if (both DRA and DRB are represented as pointers)
489 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION
490 3. else if (DRA and DRB are represented differently or 2. fails)
491 only try to prove that the bases are surely different
495 base_addr_differ_p (struct data_reference
*dra
,
496 struct data_reference
*drb
,
499 tree addr_a
= DR_BASE_ADDRESS (dra
);
500 tree addr_b
= DR_BASE_ADDRESS (drb
);
505 if (!addr_a
|| !addr_b
)
508 type_a
= TREE_TYPE (addr_a
);
509 type_b
= TREE_TYPE (addr_b
);
511 gcc_assert (POINTER_TYPE_P (type_a
) && POINTER_TYPE_P (type_b
));
513 /* 1. if (both DRA and DRB are represented as arrays)
514 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT. */
515 if (DR_TYPE (dra
) == ARRAY_REF_TYPE
&& DR_TYPE (drb
) == ARRAY_REF_TYPE
)
516 return base_object_differ_p (dra
, drb
, differ_p
);
518 /* 2. else if (both DRA and DRB are represented as pointers)
519 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION. */
520 /* If base addresses are the same, we check the offsets, since the access of
521 the data-ref is described by {base addr + offset} and its access function,
522 i.e., in order to decide whether the bases of data-refs are the same we
523 compare both base addresses and offsets. */
524 if (DR_TYPE (dra
) == POINTER_REF_TYPE
&& DR_TYPE (drb
) == POINTER_REF_TYPE
526 || (TREE_CODE (addr_a
) == ADDR_EXPR
&& TREE_CODE (addr_b
) == ADDR_EXPR
527 && TREE_OPERAND (addr_a
, 0) == TREE_OPERAND (addr_b
, 0))))
529 /* Compare offsets. */
530 tree offset_a
= DR_OFFSET (dra
);
531 tree offset_b
= DR_OFFSET (drb
);
533 STRIP_NOPS (offset_a
);
534 STRIP_NOPS (offset_b
);
536 /* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle
538 if (offset_a
== offset_b
539 || (TREE_CODE (offset_a
) == MULT_EXPR
540 && TREE_CODE (offset_b
) == MULT_EXPR
541 && TREE_OPERAND (offset_a
, 0) == TREE_OPERAND (offset_b
, 0)
542 && TREE_OPERAND (offset_a
, 1) == TREE_OPERAND (offset_b
, 1)))
549 /* 3. else if (DRA and DRB are represented differently or 2. fails)
550 only try to prove that the bases are surely different. */
552 /* Apply alias analysis. */
553 if (may_alias_p (addr_a
, addr_b
, dra
, drb
, &aliased
) && !aliased
)
559 /* An instruction writing through a restricted pointer is "independent" of any
560 instruction reading or writing through a different restricted pointer,
561 in the same block/scope. */
562 else if (TYPE_RESTRICT (type_a
)
563 && TYPE_RESTRICT (type_b
)
564 && (!DR_IS_READ (drb
) || !DR_IS_READ (dra
))
565 && TREE_CODE (DR_BASE_ADDRESS (dra
)) == SSA_NAME
566 && (decl_a
= SSA_NAME_VAR (DR_BASE_ADDRESS (dra
)))
567 && TREE_CODE (decl_a
) == PARM_DECL
568 && TREE_CODE (DECL_CONTEXT (decl_a
)) == FUNCTION_DECL
569 && TREE_CODE (DR_BASE_ADDRESS (drb
)) == SSA_NAME
570 && (decl_b
= SSA_NAME_VAR (DR_BASE_ADDRESS (drb
)))
571 && TREE_CODE (decl_b
) == PARM_DECL
572 && TREE_CODE (DECL_CONTEXT (decl_b
)) == FUNCTION_DECL
573 && DECL_CONTEXT (decl_a
) == DECL_CONTEXT (decl_b
))
582 /* Returns true iff A divides B. */
585 tree_fold_divides_p (tree a
, tree b
)
587 gcc_assert (TREE_CODE (a
) == INTEGER_CST
);
588 gcc_assert (TREE_CODE (b
) == INTEGER_CST
);
589 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR
, b
, a
, 0));
592 /* Returns true iff A divides B. */
595 int_divides_p (int a
, int b
)
597 return ((b
% a
) == 0);
602 /* Dump into FILE all the data references from DATAREFS. */
605 dump_data_references (FILE *file
, VEC (data_reference_p
, heap
) *datarefs
)
608 struct data_reference
*dr
;
610 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
611 dump_data_reference (file
, dr
);
614 /* Dump into FILE all the dependence relations from DDRS. */
617 dump_data_dependence_relations (FILE *file
,
618 VEC (ddr_p
, heap
) *ddrs
)
621 struct data_dependence_relation
*ddr
;
623 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
624 dump_data_dependence_relation (file
, ddr
);
627 /* Dump function for a DATA_REFERENCE structure. */
630 dump_data_reference (FILE *outf
,
631 struct data_reference
*dr
)
635 fprintf (outf
, "(Data Ref: \n stmt: ");
636 print_generic_stmt (outf
, DR_STMT (dr
), 0);
637 fprintf (outf
, " ref: ");
638 print_generic_stmt (outf
, DR_REF (dr
), 0);
639 fprintf (outf
, " base_object: ");
640 print_generic_stmt (outf
, DR_BASE_OBJECT (dr
), 0);
642 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
644 fprintf (outf
, " Access function %d: ", i
);
645 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
647 fprintf (outf
, ")\n");
650 /* Dumps the affine function described by FN to the file OUTF. */
653 dump_affine_function (FILE *outf
, affine_fn fn
)
658 print_generic_expr (outf
, VEC_index (tree
, fn
, 0), TDF_SLIM
);
659 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
661 fprintf (outf
, " + ");
662 print_generic_expr (outf
, coef
, TDF_SLIM
);
663 fprintf (outf
, " * x_%u", i
);
667 /* Dumps the conflict function CF to the file OUTF. */
670 dump_conflict_function (FILE *outf
, conflict_function
*cf
)
674 if (cf
->n
== NO_DEPENDENCE
)
675 fprintf (outf
, "no dependence\n");
676 else if (cf
->n
== NOT_KNOWN
)
677 fprintf (outf
, "not known\n");
680 for (i
= 0; i
< cf
->n
; i
++)
683 dump_affine_function (outf
, cf
->fns
[i
]);
684 fprintf (outf
, "]\n");
689 /* Dump function for a SUBSCRIPT structure. */
692 dump_subscript (FILE *outf
, struct subscript
*subscript
)
694 conflict_function
*cf
= SUB_CONFLICTS_IN_A (subscript
);
696 fprintf (outf
, "\n (subscript \n");
697 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
698 dump_conflict_function (outf
, cf
);
699 if (CF_NONTRIVIAL_P (cf
))
701 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
702 fprintf (outf
, " last_conflict: ");
703 print_generic_stmt (outf
, last_iteration
, 0);
706 cf
= SUB_CONFLICTS_IN_B (subscript
);
707 fprintf (outf
, " iterations_that_access_an_element_twice_in_B: ");
708 dump_conflict_function (outf
, cf
);
709 if (CF_NONTRIVIAL_P (cf
))
711 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
712 fprintf (outf
, " last_conflict: ");
713 print_generic_stmt (outf
, last_iteration
, 0);
716 fprintf (outf
, " (Subscript distance: ");
717 print_generic_stmt (outf
, SUB_DISTANCE (subscript
), 0);
718 fprintf (outf
, " )\n");
719 fprintf (outf
, " )\n");
722 /* Print the classic direction vector DIRV to OUTF. */
725 print_direction_vector (FILE *outf
,
731 for (eq
= 0; eq
< length
; eq
++)
733 enum data_dependence_direction dir
= dirv
[eq
];
738 fprintf (outf
, " +");
741 fprintf (outf
, " -");
744 fprintf (outf
, " =");
746 case dir_positive_or_equal
:
747 fprintf (outf
, " +=");
749 case dir_positive_or_negative
:
750 fprintf (outf
, " +-");
752 case dir_negative_or_equal
:
753 fprintf (outf
, " -=");
756 fprintf (outf
, " *");
759 fprintf (outf
, "indep");
763 fprintf (outf
, "\n");
766 /* Print a vector of direction vectors. */
769 print_dir_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dir_vects
,
775 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, v
); j
++)
776 print_direction_vector (outf
, v
, length
);
779 /* Print a vector of distance vectors. */
782 print_dist_vectors (FILE *outf
, VEC (lambda_vector
, heap
) *dist_vects
,
788 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, v
); j
++)
789 print_lambda_vector (outf
, v
, length
);
795 debug_data_dependence_relation (struct data_dependence_relation
*ddr
)
797 dump_data_dependence_relation (stderr
, ddr
);
800 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
803 dump_data_dependence_relation (FILE *outf
,
804 struct data_dependence_relation
*ddr
)
806 struct data_reference
*dra
, *drb
;
810 fprintf (outf
, "(Data Dep: \n");
811 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
812 fprintf (outf
, " (don't know)\n");
814 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
815 fprintf (outf
, " (no dependence)\n");
817 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
822 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
824 fprintf (outf
, " access_fn_A: ");
825 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
826 fprintf (outf
, " access_fn_B: ");
827 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
828 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
831 fprintf (outf
, " inner loop index: %d\n", DDR_INNER_LOOP (ddr
));
832 fprintf (outf
, " loop nest: (");
833 for (i
= 0; VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
834 fprintf (outf
, "%d ", loopi
->num
);
835 fprintf (outf
, ")\n");
837 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
839 fprintf (outf
, " distance_vector: ");
840 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
, i
),
844 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
846 fprintf (outf
, " direction_vector: ");
847 print_direction_vector (outf
, DDR_DIR_VECT (ddr
, i
),
852 fprintf (outf
, ")\n");
855 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
858 dump_data_dependence_direction (FILE *file
,
859 enum data_dependence_direction dir
)
875 case dir_positive_or_negative
:
876 fprintf (file
, "+-");
879 case dir_positive_or_equal
:
880 fprintf (file
, "+=");
883 case dir_negative_or_equal
:
884 fprintf (file
, "-=");
896 /* Dumps the distance and direction vectors in FILE. DDRS contains
897 the dependence relations, and VECT_SIZE is the size of the
898 dependence vectors, or in other words the number of loops in the
902 dump_dist_dir_vectors (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
905 struct data_dependence_relation
*ddr
;
908 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
909 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_AFFINE_P (ddr
))
911 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), j
, v
); j
++)
913 fprintf (file
, "DISTANCE_V (");
914 print_lambda_vector (file
, v
, DDR_NB_LOOPS (ddr
));
915 fprintf (file
, ")\n");
918 for (j
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), j
, v
); j
++)
920 fprintf (file
, "DIRECTION_V (");
921 print_direction_vector (file
, v
, DDR_NB_LOOPS (ddr
));
922 fprintf (file
, ")\n");
926 fprintf (file
, "\n\n");
929 /* Dumps the data dependence relations DDRS in FILE. */
932 dump_ddrs (FILE *file
, VEC (ddr_p
, heap
) *ddrs
)
935 struct data_dependence_relation
*ddr
;
937 for (i
= 0; VEC_iterate (ddr_p
, ddrs
, i
, ddr
); i
++)
938 dump_data_dependence_relation (file
, ddr
);
940 fprintf (file
, "\n\n");
945 /* Given an ARRAY_REF node REF, records its access functions.
946 Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
947 i.e. the constant "3", then recursively call the function on opnd0,
948 i.e. the ARRAY_REF "A[i]".
949 The function returns the base name: "A". */
952 analyze_array_indexes (struct loop
*loop
,
953 VEC(tree
,heap
) **access_fns
,
959 opnd0
= TREE_OPERAND (ref
, 0);
960 opnd1
= TREE_OPERAND (ref
, 1);
962 /* The detection of the evolution function for this data access is
963 postponed until the dependence test. This lazy strategy avoids
964 the computation of access functions that are of no interest for
966 access_fn
= instantiate_parameters
967 (loop
, analyze_scalar_evolution (loop
, opnd1
));
969 VEC_safe_push (tree
, heap
, *access_fns
, access_fn
);
971 /* Recursively record other array access functions. */
972 if (TREE_CODE (opnd0
) == ARRAY_REF
)
973 return analyze_array_indexes (loop
, access_fns
, opnd0
, stmt
);
975 /* Return the base name of the data access. */
980 /* For a data reference REF contained in the statement STMT, initialize
981 a DATA_REFERENCE structure, and return it. IS_READ flag has to be
982 set to true when REF is in the right hand side of an
985 static struct data_reference
*
986 init_array_ref (tree stmt
, tree ref
, bool is_read
)
988 struct loop
*loop
= loop_containing_stmt (stmt
);
989 VEC(tree
,heap
) *acc_fns
= VEC_alloc (tree
, heap
, 3);
990 struct data_reference
*res
= XNEW (struct data_reference
);;
992 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
994 fprintf (dump_file
, "(init_array_ref \n");
995 fprintf (dump_file
, " (ref = ");
996 print_generic_stmt (dump_file
, ref
, 0);
997 fprintf (dump_file
, ")\n");
1000 DR_STMT (res
) = stmt
;
1002 DR_BASE_OBJECT (res
) = analyze_array_indexes (loop
, &acc_fns
, ref
, stmt
);
1003 DR_TYPE (res
) = ARRAY_REF_TYPE
;
1004 DR_SET_ACCESS_FNS (res
, acc_fns
);
1005 DR_IS_READ (res
) = is_read
;
1006 DR_BASE_ADDRESS (res
) = NULL_TREE
;
1007 DR_OFFSET (res
) = NULL_TREE
;
1008 DR_INIT (res
) = NULL_TREE
;
1009 DR_STEP (res
) = NULL_TREE
;
1010 DR_OFFSET_MISALIGNMENT (res
) = NULL_TREE
;
1011 DR_MEMTAG (res
) = NULL_TREE
;
1012 DR_PTR_INFO (res
) = NULL
;
1014 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1015 fprintf (dump_file
, ")\n");
1020 /* For a data reference REF contained in the statement STMT, initialize
1021 a DATA_REFERENCE structure, and return it. */
1023 static struct data_reference
*
1024 init_pointer_ref (tree stmt
, tree ref
, tree access_fn
, bool is_read
,
1025 tree base_address
, tree step
, struct ptr_info_def
*ptr_info
)
1027 struct data_reference
*res
= XNEW (struct data_reference
);
1028 VEC(tree
,heap
) *acc_fns
= VEC_alloc (tree
, heap
, 3);
1030 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1032 fprintf (dump_file
, "(init_pointer_ref \n");
1033 fprintf (dump_file
, " (ref = ");
1034 print_generic_stmt (dump_file
, ref
, 0);
1035 fprintf (dump_file
, ")\n");
1038 DR_STMT (res
) = stmt
;
1040 DR_BASE_OBJECT (res
) = NULL_TREE
;
1041 DR_TYPE (res
) = POINTER_REF_TYPE
;
1042 DR_SET_ACCESS_FNS (res
, acc_fns
);
1043 VEC_quick_push (tree
, DR_ACCESS_FNS (res
), access_fn
);
1044 DR_IS_READ (res
) = is_read
;
1045 DR_BASE_ADDRESS (res
) = base_address
;
1046 DR_OFFSET (res
) = NULL_TREE
;
1047 DR_INIT (res
) = NULL_TREE
;
1048 DR_STEP (res
) = step
;
1049 DR_OFFSET_MISALIGNMENT (res
) = NULL_TREE
;
1050 DR_MEMTAG (res
) = NULL_TREE
;
1051 DR_PTR_INFO (res
) = ptr_info
;
1053 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1054 fprintf (dump_file
, ")\n");
1059 /* Analyze an indirect memory reference, REF, that comes from STMT.
1060 IS_READ is true if this is an indirect load, and false if it is
1062 Return a new data reference structure representing the indirect_ref, or
1063 NULL if we cannot describe the access function. */
1065 static struct data_reference
*
1066 analyze_indirect_ref (tree stmt
, tree ref
, bool is_read
)
1068 struct loop
*loop
= loop_containing_stmt (stmt
);
1069 tree ptr_ref
= TREE_OPERAND (ref
, 0);
1070 tree access_fn
= analyze_scalar_evolution (loop
, ptr_ref
);
1071 tree init
= initial_condition_in_loop_num (access_fn
, loop
->num
);
1072 tree base_address
= NULL_TREE
, evolution
, step
= NULL_TREE
;
1073 struct ptr_info_def
*ptr_info
= NULL
;
1075 if (TREE_CODE (ptr_ref
) == SSA_NAME
)
1076 ptr_info
= SSA_NAME_PTR_INFO (ptr_ref
);
1079 if (access_fn
== chrec_dont_know
|| !init
|| init
== chrec_dont_know
)
1081 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1083 fprintf (dump_file
, "\nBad access function of ptr: ");
1084 print_generic_expr (dump_file
, ref
, TDF_SLIM
);
1085 fprintf (dump_file
, "\n");
1090 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1092 fprintf (dump_file
, "\nAccess function of ptr: ");
1093 print_generic_expr (dump_file
, access_fn
, TDF_SLIM
);
1094 fprintf (dump_file
, "\n");
1097 if (!expr_invariant_in_loop_p (loop
, init
))
1099 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1100 fprintf (dump_file
, "\ninitial condition is not loop invariant.\n");
1104 base_address
= init
;
1105 evolution
= evolution_part_in_loop_num (access_fn
, loop
->num
);
1106 if (evolution
!= chrec_dont_know
)
1109 step
= ssize_int (0);
1112 if (TREE_CODE (evolution
) == INTEGER_CST
)
1113 step
= fold_convert (ssizetype
, evolution
);
1115 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1116 fprintf (dump_file
, "\nnon constant step for ptr access.\n");
1120 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1121 fprintf (dump_file
, "\nunknown evolution of ptr.\n");
1123 return init_pointer_ref (stmt
, ref
, access_fn
, is_read
, base_address
,
1127 /* Function strip_conversions
1129 Strip conversions that don't narrow the mode. */
1132 strip_conversion (tree expr
)
1134 tree to
, ti
, oprnd0
;
1136 while (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
)
1138 to
= TREE_TYPE (expr
);
1139 oprnd0
= TREE_OPERAND (expr
, 0);
1140 ti
= TREE_TYPE (oprnd0
);
1142 if (!INTEGRAL_TYPE_P (to
) || !INTEGRAL_TYPE_P (ti
))
1144 if (GET_MODE_SIZE (TYPE_MODE (to
)) < GET_MODE_SIZE (TYPE_MODE (ti
)))
1153 /* Function analyze_offset_expr
1155 Given an offset expression EXPR received from get_inner_reference, analyze
1156 it and create an expression for INITIAL_OFFSET by substituting the variables
1157 of EXPR with initial_condition of the corresponding access_fn in the loop.
1160 for (j = 3; j < N; j++)
1163 For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be
1164 substituted, since its access_fn in the inner loop is i. 'j' will be
1165 substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
1168 Compute MISALIGN (the misalignment of the data reference initial access from
1169 its base). Misalignment can be calculated only if all the variables can be
1170 substituted with constants, otherwise, we record maximum possible alignment
1171 in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN
1172 will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be
1173 recorded in ALIGNED_TO.
1175 STEP is an evolution of the data reference in this loop in bytes.
1176 In the above example, STEP is C_j.
1178 Return FALSE, if the analysis fails, e.g., there is no access_fn for a
1179 variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO
1180 and STEP) are NULL_TREEs. Otherwise, return TRUE.
1185 analyze_offset_expr (tree expr
,
1187 tree
*initial_offset
,
1194 tree left_offset
= ssize_int (0);
1195 tree right_offset
= ssize_int (0);
1196 tree left_misalign
= ssize_int (0);
1197 tree right_misalign
= ssize_int (0);
1198 tree left_step
= ssize_int (0);
1199 tree right_step
= ssize_int (0);
1200 enum tree_code code
;
1201 tree init
, evolution
;
1202 tree left_aligned_to
= NULL_TREE
, right_aligned_to
= NULL_TREE
;
1205 *misalign
= NULL_TREE
;
1206 *aligned_to
= NULL_TREE
;
1207 *initial_offset
= NULL_TREE
;
1209 /* Strip conversions that don't narrow the mode. */
1210 expr
= strip_conversion (expr
);
1216 if (TREE_CODE (expr
) == INTEGER_CST
)
1218 *initial_offset
= fold_convert (ssizetype
, expr
);
1219 *misalign
= fold_convert (ssizetype
, expr
);
1220 *step
= ssize_int (0);
1224 /* 2. Variable. Try to substitute with initial_condition of the corresponding
1225 access_fn in the current loop. */
1226 if (SSA_VAR_P (expr
))
1228 tree access_fn
= analyze_scalar_evolution (loop
, expr
);
1230 if (access_fn
== chrec_dont_know
)
1234 init
= initial_condition_in_loop_num (access_fn
, loop
->num
);
1235 if (!expr_invariant_in_loop_p (loop
, init
))
1236 /* Not enough information: may be not loop invariant.
1237 E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
1238 initial_condition is D, but it depends on i - loop's induction
1242 evolution
= evolution_part_in_loop_num (access_fn
, loop
->num
);
1243 if (evolution
&& TREE_CODE (evolution
) != INTEGER_CST
)
1244 /* Evolution is not constant. */
1247 if (TREE_CODE (init
) == INTEGER_CST
)
1248 *misalign
= fold_convert (ssizetype
, init
);
1250 /* Not constant, misalignment cannot be calculated. */
1251 *misalign
= NULL_TREE
;
1253 *initial_offset
= fold_convert (ssizetype
, init
);
1255 *step
= evolution
? fold_convert (ssizetype
, evolution
) : ssize_int (0);
1259 /* Recursive computation. */
1260 if (!BINARY_CLASS_P (expr
))
1262 /* We expect to get binary expressions (PLUS/MINUS and MULT). */
1263 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1265 fprintf (dump_file
, "\nNot binary expression ");
1266 print_generic_expr (dump_file
, expr
, TDF_SLIM
);
1267 fprintf (dump_file
, "\n");
1271 oprnd0
= TREE_OPERAND (expr
, 0);
1272 oprnd1
= TREE_OPERAND (expr
, 1);
1274 if (!analyze_offset_expr (oprnd0
, loop
, &left_offset
, &left_misalign
,
1275 &left_aligned_to
, &left_step
)
1276 || !analyze_offset_expr (oprnd1
, loop
, &right_offset
, &right_misalign
,
1277 &right_aligned_to
, &right_step
))
1280 /* The type of the operation: plus, minus or mult. */
1281 code
= TREE_CODE (expr
);
1285 if (TREE_CODE (right_offset
) != INTEGER_CST
)
1286 /* RIGHT_OFFSET can be not constant. For example, for arrays of variable
1288 FORNOW: We don't support such cases. */
1291 /* Strip conversions that don't narrow the mode. */
1292 left_offset
= strip_conversion (left_offset
);
1295 /* Misalignment computation. */
1296 if (SSA_VAR_P (left_offset
))
1298 /* If the left side contains variables that can't be substituted with
1299 constants, the misalignment is unknown. However, if the right side
1300 is a multiple of some alignment, we know that the expression is
1301 aligned to it. Therefore, we record such maximum possible value.
1303 *misalign
= NULL_TREE
;
1304 *aligned_to
= ssize_int (highest_pow2_factor (right_offset
));
1308 /* The left operand was successfully substituted with constant. */
1311 /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is
1313 *misalign
= size_binop (code
, left_misalign
, right_misalign
);
1314 if (left_aligned_to
&& right_aligned_to
)
1315 *aligned_to
= size_binop (MIN_EXPR
, left_aligned_to
,
1318 *aligned_to
= left_aligned_to
?
1319 left_aligned_to
: right_aligned_to
;
1322 *misalign
= NULL_TREE
;
1325 /* Step calculation. */
1326 /* Multiply the step by the right operand. */
1327 *step
= size_binop (MULT_EXPR
, left_step
, right_offset
);
1332 /* Combine the recursive calculations for step and misalignment. */
1333 *step
= size_binop (code
, left_step
, right_step
);
1335 /* Unknown alignment. */
1336 if ((!left_misalign
&& !left_aligned_to
)
1337 || (!right_misalign
&& !right_aligned_to
))
1339 *misalign
= NULL_TREE
;
1340 *aligned_to
= NULL_TREE
;
1344 if (left_misalign
&& right_misalign
)
1345 *misalign
= size_binop (code
, left_misalign
, right_misalign
);
1347 *misalign
= left_misalign
? left_misalign
: right_misalign
;
1349 if (left_aligned_to
&& right_aligned_to
)
1350 *aligned_to
= size_binop (MIN_EXPR
, left_aligned_to
, right_aligned_to
);
1352 *aligned_to
= left_aligned_to
? left_aligned_to
: right_aligned_to
;
1360 /* Compute offset. */
1361 *initial_offset
= fold_convert (ssizetype
,
1362 fold_build2 (code
, TREE_TYPE (left_offset
),
1368 /* Function address_analysis
1370 Return the BASE of the address expression EXPR.
1371 Also compute the OFFSET from BASE, MISALIGN and STEP.
1374 EXPR - the address expression that is being analyzed
1375 STMT - the statement that contains EXPR or its original memory reference
1376 IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
1377 DR - data_reference struct for the original memory reference
1380 BASE (returned value) - the base of the data reference EXPR.
1381 INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
1382 MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
1383 computation is impossible
1384 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1385 calculated (doesn't depend on variables)
1386 STEP - evolution of EXPR in the loop
1388 If something unexpected is encountered (an unsupported form of data-ref),
1389 then NULL_TREE is returned.
1393 address_analysis (tree expr
, tree stmt
, bool is_read
, struct data_reference
*dr
,
1394 tree
*offset
, tree
*misalign
, tree
*aligned_to
, tree
*step
)
1396 tree oprnd0
, oprnd1
, base_address
, offset_expr
, base_addr0
, base_addr1
;
1397 tree address_offset
= ssize_int (0), address_misalign
= ssize_int (0);
1398 tree dummy
, address_aligned_to
= NULL_TREE
;
1399 struct ptr_info_def
*dummy1
;
1402 switch (TREE_CODE (expr
))
1406 /* EXPR is of form {base +/- offset} (or {offset +/- base}). */
1407 oprnd0
= TREE_OPERAND (expr
, 0);
1408 oprnd1
= TREE_OPERAND (expr
, 1);
1410 STRIP_NOPS (oprnd0
);
1411 STRIP_NOPS (oprnd1
);
1413 /* Recursively try to find the base of the address contained in EXPR.
1414 For offset, the returned base will be NULL. */
1415 base_addr0
= address_analysis (oprnd0
, stmt
, is_read
, dr
, &address_offset
,
1416 &address_misalign
, &address_aligned_to
,
1419 base_addr1
= address_analysis (oprnd1
, stmt
, is_read
, dr
, &address_offset
,
1420 &address_misalign
, &address_aligned_to
,
1423 /* We support cases where only one of the operands contains an
1425 if ((base_addr0
&& base_addr1
) || (!base_addr0
&& !base_addr1
))
1427 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1430 "\neither more than one address or no addresses in expr ");
1431 print_generic_expr (dump_file
, expr
, TDF_SLIM
);
1432 fprintf (dump_file
, "\n");
1437 /* To revert STRIP_NOPS. */
1438 oprnd0
= TREE_OPERAND (expr
, 0);
1439 oprnd1
= TREE_OPERAND (expr
, 1);
1441 offset_expr
= base_addr0
?
1442 fold_convert (ssizetype
, oprnd1
) : fold_convert (ssizetype
, oprnd0
);
1444 /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is
1445 a number, we can add it to the misalignment value calculated for base,
1446 otherwise, misalignment is NULL. */
1447 if (TREE_CODE (offset_expr
) == INTEGER_CST
&& address_misalign
)
1449 *misalign
= size_binop (TREE_CODE (expr
), address_misalign
,
1451 *aligned_to
= address_aligned_to
;
1455 *misalign
= NULL_TREE
;
1456 *aligned_to
= NULL_TREE
;
1459 /* Combine offset (from EXPR {base + offset}) with the offset calculated
1461 *offset
= size_binop (TREE_CODE (expr
), address_offset
, offset_expr
);
1462 return base_addr0
? base_addr0
: base_addr1
;
1465 base_address
= object_analysis (TREE_OPERAND (expr
, 0), stmt
, is_read
,
1466 &dr
, offset
, misalign
, aligned_to
, step
,
1467 &dummy
, &dummy1
, &dummy2
);
1468 return base_address
;
1471 if (!POINTER_TYPE_P (TREE_TYPE (expr
)))
1473 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1475 fprintf (dump_file
, "\nnot pointer SSA_NAME ");
1476 print_generic_expr (dump_file
, expr
, TDF_SLIM
);
1477 fprintf (dump_file
, "\n");
1481 *aligned_to
= ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr
))));
1482 *misalign
= ssize_int (0);
1483 *offset
= ssize_int (0);
1484 *step
= ssize_int (0);
1493 /* Function object_analysis
1495 Create a data-reference structure DR for MEMREF.
1496 Return the BASE of the data reference MEMREF if the analysis is possible.
1497 Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1498 E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset
1499 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET
1500 instantiated with initial_conditions of access_functions of variables,
1501 and STEP is the evolution of the DR_REF in this loop.
1503 Function get_inner_reference is used for the above in case of ARRAY_REF and
1506 The structure of the function is as follows:
1508 Case 1. For handled_component_p refs
1509 1.1 build data-reference structure for MEMREF
1510 1.2 call get_inner_reference
1511 1.2.1 analyze offset expr received from get_inner_reference
1512 (fall through with BASE)
1513 Case 2. For declarations
1515 Case 3. For INDIRECT_REFs
1516 3.1 build data-reference structure for MEMREF
1517 3.2 analyze evolution and initial condition of MEMREF
1518 3.3 set data-reference structure for MEMREF
1519 3.4 call address_analysis to analyze INIT of the access function
1520 3.5 extract memory tag
1523 Combine the results of object and address analysis to calculate
1524 INITIAL_OFFSET, STEP and misalignment info.
1527 MEMREF - the memory reference that is being analyzed
1528 STMT - the statement that contains MEMREF
1529 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1532 BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
1533 E.g, if MEMREF is a.b[k].c[i][j] the returned
1535 DR - data_reference struct for MEMREF
1536 INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
1537 MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of
1538 ALIGNMENT or NULL_TREE if the computation is impossible
1539 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1540 calculated (doesn't depend on variables)
1541 STEP - evolution of the DR_REF in the loop
1542 MEMTAG - memory tag for aliasing purposes
1543 PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
1544 SUBVARS - Sub-variables of the variable
1546 If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned,
1547 but DR can be created anyway.
1552 object_analysis (tree memref
, tree stmt
, bool is_read
,
1553 struct data_reference
**dr
, tree
*offset
, tree
*misalign
,
1554 tree
*aligned_to
, tree
*step
, tree
*memtag
,
1555 struct ptr_info_def
**ptr_info
, subvar_t
*subvars
)
1557 tree base
= NULL_TREE
, base_address
= NULL_TREE
;
1558 tree object_offset
= ssize_int (0), object_misalign
= ssize_int (0);
1559 tree object_step
= ssize_int (0), address_step
= ssize_int (0);
1560 tree address_offset
= ssize_int (0), address_misalign
= ssize_int (0);
1561 HOST_WIDE_INT pbitsize
, pbitpos
;
1562 tree poffset
, bit_pos_in_bytes
;
1563 enum machine_mode pmode
;
1564 int punsignedp
, pvolatilep
;
1565 tree ptr_step
= ssize_int (0), ptr_init
= NULL_TREE
;
1566 struct loop
*loop
= loop_containing_stmt (stmt
);
1567 struct data_reference
*ptr_dr
= NULL
;
1568 tree object_aligned_to
= NULL_TREE
, address_aligned_to
= NULL_TREE
;
1569 tree comp_ref
= NULL_TREE
;
1574 /* Case 1. handled_component_p refs. */
1575 if (handled_component_p (memref
))
1577 /* 1.1 build data-reference structure for MEMREF. */
1580 if (TREE_CODE (memref
) == ARRAY_REF
)
1581 *dr
= init_array_ref (stmt
, memref
, is_read
);
1582 else if (TREE_CODE (memref
) == COMPONENT_REF
)
1586 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1588 fprintf (dump_file
, "\ndata-ref of unsupported type ");
1589 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1590 fprintf (dump_file
, "\n");
1596 /* 1.2 call get_inner_reference. */
1597 /* Find the base and the offset from it. */
1598 base
= get_inner_reference (memref
, &pbitsize
, &pbitpos
, &poffset
,
1599 &pmode
, &punsignedp
, &pvolatilep
, false);
1602 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1604 fprintf (dump_file
, "\nfailed to get inner ref for ");
1605 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1606 fprintf (dump_file
, "\n");
1611 /* 1.2.1 analyze offset expr received from get_inner_reference. */
1613 && !analyze_offset_expr (poffset
, loop
, &object_offset
,
1614 &object_misalign
, &object_aligned_to
,
1617 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1619 fprintf (dump_file
, "\nfailed to compute offset or step for ");
1620 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1621 fprintf (dump_file
, "\n");
1626 /* Add bit position to OFFSET and MISALIGN. */
1628 bit_pos_in_bytes
= ssize_int (pbitpos
/BITS_PER_UNIT
);
1629 /* Check that there is no remainder in bits. */
1630 if (pbitpos
%BITS_PER_UNIT
)
1632 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1633 fprintf (dump_file
, "\nbit offset alignment.\n");
1636 object_offset
= size_binop (PLUS_EXPR
, bit_pos_in_bytes
, object_offset
);
1637 if (object_misalign
)
1638 object_misalign
= size_binop (PLUS_EXPR
, object_misalign
,
1641 memref
= base
; /* To continue analysis of BASE. */
1645 /* Part 1: Case 2. Declarations. */
1646 if (DECL_P (memref
))
1648 /* We expect to get a decl only if we already have a DR, or with
1649 COMPONENT_REFs of type 'a[i].b'. */
1652 if (comp_ref
&& TREE_CODE (TREE_OPERAND (comp_ref
, 0)) == ARRAY_REF
)
1654 *dr
= init_array_ref (stmt
, TREE_OPERAND (comp_ref
, 0), is_read
);
1655 if (DR_NUM_DIMENSIONS (*dr
) != 1)
1657 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1659 fprintf (dump_file
, "\n multidimensional component ref ");
1660 print_generic_expr (dump_file
, comp_ref
, TDF_SLIM
);
1661 fprintf (dump_file
, "\n");
1668 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1670 fprintf (dump_file
, "\nunhandled decl ");
1671 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1672 fprintf (dump_file
, "\n");
1678 /* TODO: if during the analysis of INDIRECT_REF we get to an object, put
1679 the object in BASE_OBJECT field if we can prove that this is O.K.,
1680 i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT.
1681 (e.g., if the object is an array base 'a', where 'a[N]', we must prove
1682 that every access with 'p' (the original INDIRECT_REF based on '&a')
1683 in the loop is within the array boundaries - from a[0] to a[N-1]).
1684 Otherwise, our alias analysis can be incorrect.
1685 Even if an access function based on BASE_OBJECT can't be build, update
1686 BASE_OBJECT field to enable us to prove that two data-refs are
1687 different (without access function, distance analysis is impossible).
1689 if (SSA_VAR_P (memref
) && var_can_have_subvars (memref
))
1690 *subvars
= get_subvars_for_var (memref
);
1691 base_address
= build_fold_addr_expr (memref
);
1692 /* 2.1 set MEMTAG. */
1696 /* Part 1: Case 3. INDIRECT_REFs. */
1697 else if (TREE_CODE (memref
) == INDIRECT_REF
)
1699 tree ptr_ref
= TREE_OPERAND (memref
, 0);
1700 if (TREE_CODE (ptr_ref
) == SSA_NAME
)
1701 *ptr_info
= SSA_NAME_PTR_INFO (ptr_ref
);
1703 /* 3.1 build data-reference structure for MEMREF. */
1704 ptr_dr
= analyze_indirect_ref (stmt
, memref
, is_read
);
1707 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1709 fprintf (dump_file
, "\nfailed to create dr for ");
1710 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1711 fprintf (dump_file
, "\n");
1716 /* 3.2 analyze evolution and initial condition of MEMREF. */
1717 ptr_step
= DR_STEP (ptr_dr
);
1718 ptr_init
= DR_BASE_ADDRESS (ptr_dr
);
1719 if (!ptr_init
|| !ptr_step
|| !POINTER_TYPE_P (TREE_TYPE (ptr_init
)))
1721 *dr
= (*dr
) ? *dr
: ptr_dr
;
1722 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1724 fprintf (dump_file
, "\nbad pointer access ");
1725 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1726 fprintf (dump_file
, "\n");
1731 if (integer_zerop (ptr_step
) && !(*dr
))
1733 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1734 fprintf (dump_file
, "\nptr is loop invariant.\n");
1738 /* If there exists DR for MEMREF, we are analyzing the base of
1739 handled component (PTR_INIT), which not necessary has evolution in
1742 object_step
= size_binop (PLUS_EXPR
, object_step
, ptr_step
);
1744 /* 3.3 set data-reference structure for MEMREF. */
1748 /* 3.4 call address_analysis to analyze INIT of the access
1750 base_address
= address_analysis (ptr_init
, stmt
, is_read
, *dr
,
1751 &address_offset
, &address_misalign
,
1752 &address_aligned_to
, &address_step
);
1755 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1757 fprintf (dump_file
, "\nfailed to analyze address ");
1758 print_generic_expr (dump_file
, ptr_init
, TDF_SLIM
);
1759 fprintf (dump_file
, "\n");
1764 /* 3.5 extract memory tag. */
1765 switch (TREE_CODE (base_address
))
1768 *memtag
= symbol_mem_tag (SSA_NAME_VAR (base_address
));
1769 if (!(*memtag
) && TREE_CODE (TREE_OPERAND (memref
, 0)) == SSA_NAME
)
1770 *memtag
= symbol_mem_tag (SSA_NAME_VAR (TREE_OPERAND (memref
, 0)));
1773 *memtag
= TREE_OPERAND (base_address
, 0);
1776 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1778 fprintf (dump_file
, "\nno memtag for ");
1779 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1780 fprintf (dump_file
, "\n");
1782 *memtag
= NULL_TREE
;
1789 /* MEMREF cannot be analyzed. */
1790 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1792 fprintf (dump_file
, "\ndata-ref of unsupported type ");
1793 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1794 fprintf (dump_file
, "\n");
1800 DR_REF (*dr
) = comp_ref
;
1802 if (SSA_VAR_P (*memtag
) && var_can_have_subvars (*memtag
))
1803 *subvars
= get_subvars_for_var (*memtag
);
1805 /* Part 2: Combine the results of object and address analysis to calculate
1806 INITIAL_OFFSET, STEP and misalignment info. */
1807 *offset
= size_binop (PLUS_EXPR
, object_offset
, address_offset
);
1809 if ((!object_misalign
&& !object_aligned_to
)
1810 || (!address_misalign
&& !address_aligned_to
))
1812 *misalign
= NULL_TREE
;
1813 *aligned_to
= NULL_TREE
;
1817 if (object_misalign
&& address_misalign
)
1818 *misalign
= size_binop (PLUS_EXPR
, object_misalign
, address_misalign
);
1820 *misalign
= object_misalign
? object_misalign
: address_misalign
;
1821 if (object_aligned_to
&& address_aligned_to
)
1822 *aligned_to
= size_binop (MIN_EXPR
, object_aligned_to
,
1823 address_aligned_to
);
1825 *aligned_to
= object_aligned_to
?
1826 object_aligned_to
: address_aligned_to
;
1828 *step
= size_binop (PLUS_EXPR
, object_step
, address_step
);
1830 return base_address
;
1833 /* Function analyze_offset.
1835 Extract INVARIANT and CONSTANT parts from OFFSET.
1839 analyze_offset (tree offset
, tree
*invariant
, tree
*constant
)
1841 tree op0
, op1
, constant_0
, constant_1
, invariant_0
, invariant_1
;
1842 enum tree_code code
= TREE_CODE (offset
);
1844 *invariant
= NULL_TREE
;
1845 *constant
= NULL_TREE
;
1847 /* Not PLUS/MINUS expression - recursion stop condition. */
1848 if (code
!= PLUS_EXPR
&& code
!= MINUS_EXPR
)
1850 if (TREE_CODE (offset
) == INTEGER_CST
)
1853 *invariant
= offset
;
1857 op0
= TREE_OPERAND (offset
, 0);
1858 op1
= TREE_OPERAND (offset
, 1);
1860 /* Recursive call with the operands. */
1861 if (!analyze_offset (op0
, &invariant_0
, &constant_0
)
1862 || !analyze_offset (op1
, &invariant_1
, &constant_1
))
1865 /* Combine the results. Add negation to the subtrahend in case of
1867 if (constant_0
&& constant_1
)
1869 *constant
= constant_0
? constant_0
: constant_1
;
1870 if (code
== MINUS_EXPR
&& constant_1
)
1871 *constant
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (*constant
), *constant
);
1873 if (invariant_0
&& invariant_1
)
1875 fold_build2 (code
, TREE_TYPE (invariant_0
), invariant_0
, invariant_1
);
1878 *invariant
= invariant_0
? invariant_0
: invariant_1
;
1879 if (code
== MINUS_EXPR
&& invariant_1
)
1881 fold_build1 (NEGATE_EXPR
, TREE_TYPE (*invariant
), *invariant
);
1886 /* Free the memory used by the data reference DR. */
1889 free_data_ref (data_reference_p dr
)
1891 DR_FREE_ACCESS_FNS (dr
);
1895 /* Function create_data_ref.
1897 Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS,
1898 DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO,
1899 DR_MEMTAG, and DR_POINTSTO_INFO fields.
1902 MEMREF - the memory reference that is being analyzed
1903 STMT - the statement that contains MEMREF
1904 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1907 DR (returned value) - data_reference struct for MEMREF
1910 static struct data_reference
*
1911 create_data_ref (tree memref
, tree stmt
, bool is_read
)
1913 struct data_reference
*dr
= NULL
;
1914 tree base_address
, offset
, step
, misalign
, memtag
;
1915 struct loop
*loop
= loop_containing_stmt (stmt
);
1916 tree invariant
= NULL_TREE
, constant
= NULL_TREE
;
1917 tree type_size
, init_cond
;
1918 struct ptr_info_def
*ptr_info
;
1919 subvar_t subvars
= NULL
;
1920 tree aligned_to
, type
= NULL_TREE
, orig_offset
;
1925 base_address
= object_analysis (memref
, stmt
, is_read
, &dr
, &offset
,
1926 &misalign
, &aligned_to
, &step
, &memtag
,
1927 &ptr_info
, &subvars
);
1928 if (!dr
|| !base_address
)
1930 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1932 fprintf (dump_file
, "\ncreate_data_ref: failed to create a dr for ");
1933 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1934 fprintf (dump_file
, "\n");
1939 DR_BASE_ADDRESS (dr
) = base_address
;
1940 DR_OFFSET (dr
) = offset
;
1941 DR_INIT (dr
) = ssize_int (0);
1942 DR_STEP (dr
) = step
;
1943 DR_OFFSET_MISALIGNMENT (dr
) = misalign
;
1944 DR_ALIGNED_TO (dr
) = aligned_to
;
1945 DR_MEMTAG (dr
) = memtag
;
1946 DR_PTR_INFO (dr
) = ptr_info
;
1947 DR_SUBVARS (dr
) = subvars
;
1949 type_size
= fold_convert (ssizetype
, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr
))));
1951 /* Extract CONSTANT and INVARIANT from OFFSET. */
1952 /* Remove cast from OFFSET and restore it for INVARIANT part. */
1953 orig_offset
= offset
;
1954 STRIP_NOPS (offset
);
1955 if (offset
!= orig_offset
)
1956 type
= TREE_TYPE (orig_offset
);
1957 if (!analyze_offset (offset
, &invariant
, &constant
))
1959 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1961 fprintf (dump_file
, "\ncreate_data_ref: failed to analyze dr's");
1962 fprintf (dump_file
, " offset for ");
1963 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
1964 fprintf (dump_file
, "\n");
1968 if (type
&& invariant
)
1969 invariant
= fold_convert (type
, invariant
);
1971 /* Put CONSTANT part of OFFSET in DR_INIT and INVARIANT in DR_OFFSET field
1975 DR_INIT (dr
) = fold_convert (ssizetype
, constant
);
1976 init_cond
= fold_build2 (TRUNC_DIV_EXPR
, TREE_TYPE (constant
),
1977 constant
, type_size
);
1980 DR_INIT (dr
) = init_cond
= ssize_int (0);
1983 DR_OFFSET (dr
) = invariant
;
1985 DR_OFFSET (dr
) = ssize_int (0);
1987 /* Change the access function for INIDIRECT_REFs, according to
1988 DR_BASE_ADDRESS. Analyze OFFSET calculated in object_analysis. OFFSET is
1989 an expression that can contain loop invariant expressions and constants.
1990 We put the constant part in the initial condition of the access function
1991 (for data dependence tests), and in DR_INIT of the data-ref. The loop
1992 invariant part is put in DR_OFFSET.
1993 The evolution part of the access function is STEP calculated in
1994 object_analysis divided by the size of data type.
1996 if (!DR_BASE_OBJECT (dr
)
1997 || (TREE_CODE (memref
) == COMPONENT_REF
&& DR_NUM_DIMENSIONS (dr
) == 1))
2002 /* Update access function. */
2003 access_fn
= DR_ACCESS_FN (dr
, 0);
2004 if (automatically_generated_chrec_p (access_fn
))
2010 new_step
= size_binop (TRUNC_DIV_EXPR
,
2011 fold_convert (ssizetype
, step
), type_size
);
2013 init_cond
= chrec_convert (chrec_type (access_fn
), init_cond
, stmt
);
2014 new_step
= chrec_convert (chrec_type (access_fn
), new_step
, stmt
);
2015 if (automatically_generated_chrec_p (init_cond
)
2016 || automatically_generated_chrec_p (new_step
))
2021 access_fn
= chrec_replace_initial_condition (access_fn
, init_cond
);
2022 access_fn
= reset_evolution_in_loop (loop
->num
, access_fn
, new_step
);
2024 VEC_replace (tree
, DR_ACCESS_FNS (dr
), 0, access_fn
);
2027 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2029 struct ptr_info_def
*pi
= DR_PTR_INFO (dr
);
2031 fprintf (dump_file
, "\nCreated dr for ");
2032 print_generic_expr (dump_file
, memref
, TDF_SLIM
);
2033 fprintf (dump_file
, "\n\tbase_address: ");
2034 print_generic_expr (dump_file
, DR_BASE_ADDRESS (dr
), TDF_SLIM
);
2035 fprintf (dump_file
, "\n\toffset from base address: ");
2036 print_generic_expr (dump_file
, DR_OFFSET (dr
), TDF_SLIM
);
2037 fprintf (dump_file
, "\n\tconstant offset from base address: ");
2038 print_generic_expr (dump_file
, DR_INIT (dr
), TDF_SLIM
);
2039 fprintf (dump_file
, "\n\tbase_object: ");
2040 print_generic_expr (dump_file
, DR_BASE_OBJECT (dr
), TDF_SLIM
);
2041 fprintf (dump_file
, "\n\tstep: ");
2042 print_generic_expr (dump_file
, DR_STEP (dr
), TDF_SLIM
);
2043 fprintf (dump_file
, "B\n\tmisalignment from base: ");
2044 print_generic_expr (dump_file
, DR_OFFSET_MISALIGNMENT (dr
), TDF_SLIM
);
2045 if (DR_OFFSET_MISALIGNMENT (dr
))
2046 fprintf (dump_file
, "B");
2047 if (DR_ALIGNED_TO (dr
))
2049 fprintf (dump_file
, "\n\taligned to: ");
2050 print_generic_expr (dump_file
, DR_ALIGNED_TO (dr
), TDF_SLIM
);
2052 fprintf (dump_file
, "\n\tmemtag: ");
2053 print_generic_expr (dump_file
, DR_MEMTAG (dr
), TDF_SLIM
);
2054 fprintf (dump_file
, "\n");
2055 if (pi
&& pi
->name_mem_tag
)
2057 fprintf (dump_file
, "\n\tnametag: ");
2058 print_generic_expr (dump_file
, pi
->name_mem_tag
, TDF_SLIM
);
2059 fprintf (dump_file
, "\n");
2065 /* Returns true if FNA == FNB. */
2068 affine_function_equal_p (affine_fn fna
, affine_fn fnb
)
2070 unsigned i
, n
= VEC_length (tree
, fna
);
2072 if (n
!= VEC_length (tree
, fnb
))
2075 for (i
= 0; i
< n
; i
++)
2076 if (!operand_equal_p (VEC_index (tree
, fna
, i
),
2077 VEC_index (tree
, fnb
, i
), 0))
2083 /* If all the functions in CF are the same, returns one of them,
2084 otherwise returns NULL. */
2087 common_affine_function (conflict_function
*cf
)
2092 if (!CF_NONTRIVIAL_P (cf
))
2097 for (i
= 1; i
< cf
->n
; i
++)
2098 if (!affine_function_equal_p (comm
, cf
->fns
[i
]))
2104 /* Returns the base of the affine function FN. */
2107 affine_function_base (affine_fn fn
)
2109 return VEC_index (tree
, fn
, 0);
2112 /* Returns true if FN is a constant. */
2115 affine_function_constant_p (affine_fn fn
)
2120 for (i
= 1; VEC_iterate (tree
, fn
, i
, coef
); i
++)
2121 if (!integer_zerop (coef
))
2127 /* Applies operation OP on affine functions FNA and FNB, and returns the
2131 affine_fn_op (enum tree_code op
, affine_fn fna
, affine_fn fnb
)
2137 if (VEC_length (tree
, fnb
) > VEC_length (tree
, fna
))
2139 n
= VEC_length (tree
, fna
);
2140 m
= VEC_length (tree
, fnb
);
2144 n
= VEC_length (tree
, fnb
);
2145 m
= VEC_length (tree
, fna
);
2148 ret
= VEC_alloc (tree
, heap
, m
);
2149 for (i
= 0; i
< n
; i
++)
2150 VEC_quick_push (tree
, ret
,
2151 fold_build2 (op
, integer_type_node
,
2152 VEC_index (tree
, fna
, i
),
2153 VEC_index (tree
, fnb
, i
)));
2155 for (; VEC_iterate (tree
, fna
, i
, coef
); i
++)
2156 VEC_quick_push (tree
, ret
,
2157 fold_build2 (op
, integer_type_node
,
2158 coef
, integer_zero_node
));
2159 for (; VEC_iterate (tree
, fnb
, i
, coef
); i
++)
2160 VEC_quick_push (tree
, ret
,
2161 fold_build2 (op
, integer_type_node
,
2162 integer_zero_node
, coef
));
2167 /* Returns the sum of affine functions FNA and FNB. */
2170 affine_fn_plus (affine_fn fna
, affine_fn fnb
)
2172 return affine_fn_op (PLUS_EXPR
, fna
, fnb
);
2175 /* Returns the difference of affine functions FNA and FNB. */
2178 affine_fn_minus (affine_fn fna
, affine_fn fnb
)
2180 return affine_fn_op (MINUS_EXPR
, fna
, fnb
);
2183 /* Frees affine function FN. */
2186 affine_fn_free (affine_fn fn
)
2188 VEC_free (tree
, heap
, fn
);
2191 /* Determine for each subscript in the data dependence relation DDR
2195 compute_subscript_distance (struct data_dependence_relation
*ddr
)
2197 conflict_function
*cf_a
, *cf_b
;
2198 affine_fn fn_a
, fn_b
, diff
;
2200 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
2204 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2206 struct subscript
*subscript
;
2208 subscript
= DDR_SUBSCRIPT (ddr
, i
);
2209 cf_a
= SUB_CONFLICTS_IN_A (subscript
);
2210 cf_b
= SUB_CONFLICTS_IN_B (subscript
);
2212 fn_a
= common_affine_function (cf_a
);
2213 fn_b
= common_affine_function (cf_b
);
2216 SUB_DISTANCE (subscript
) = chrec_dont_know
;
2219 diff
= affine_fn_minus (fn_a
, fn_b
);
2221 if (affine_function_constant_p (diff
))
2222 SUB_DISTANCE (subscript
) = affine_function_base (diff
);
2224 SUB_DISTANCE (subscript
) = chrec_dont_know
;
2226 affine_fn_free (diff
);
2231 /* Returns the conflict function for "unknown". */
2233 static conflict_function
*
2234 conflict_fn_not_known (void)
2236 conflict_function
*fn
= XCNEW (conflict_function
);
2242 /* Returns the conflict function for "independent". */
2244 static conflict_function
*
2245 conflict_fn_no_dependence (void)
2247 conflict_function
*fn
= XCNEW (conflict_function
);
2248 fn
->n
= NO_DEPENDENCE
;
2253 /* Initialize a data dependence relation between data accesses A and
2254 B. NB_LOOPS is the number of loops surrounding the references: the
2255 size of the classic distance/direction vectors. */
2257 static struct data_dependence_relation
*
2258 initialize_data_dependence_relation (struct data_reference
*a
,
2259 struct data_reference
*b
,
2260 VEC (loop_p
, heap
) *loop_nest
)
2262 struct data_dependence_relation
*res
;
2263 bool differ_p
, known_dependence
;
2266 res
= XNEW (struct data_dependence_relation
);
2269 DDR_LOOP_NEST (res
) = NULL
;
2271 if (a
== NULL
|| b
== NULL
)
2273 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
2277 /* When A and B are arrays and their dimensions differ, we directly
2278 initialize the relation to "there is no dependence": chrec_known. */
2279 if (DR_BASE_OBJECT (a
) && DR_BASE_OBJECT (b
)
2280 && DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
))
2282 DDR_ARE_DEPENDENT (res
) = chrec_known
;
2286 if (DR_BASE_ADDRESS (a
) && DR_BASE_ADDRESS (b
))
2287 known_dependence
= base_addr_differ_p (a
, b
, &differ_p
);
2289 known_dependence
= base_object_differ_p (a
, b
, &differ_p
);
2291 if (!known_dependence
)
2293 /* Can't determine whether the data-refs access the same memory
2295 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
2301 DDR_ARE_DEPENDENT (res
) = chrec_known
;
2305 DDR_AFFINE_P (res
) = true;
2306 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
2307 DDR_SUBSCRIPTS (res
) = VEC_alloc (subscript_p
, heap
, DR_NUM_DIMENSIONS (a
));
2308 DDR_LOOP_NEST (res
) = loop_nest
;
2309 DDR_INNER_LOOP (res
) = 0;
2310 DDR_DIR_VECTS (res
) = NULL
;
2311 DDR_DIST_VECTS (res
) = NULL
;
2313 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
2315 struct subscript
*subscript
;
2317 subscript
= XNEW (struct subscript
);
2318 SUB_CONFLICTS_IN_A (subscript
) = conflict_fn_not_known ();
2319 SUB_CONFLICTS_IN_B (subscript
) = conflict_fn_not_known ();
2320 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
2321 SUB_DISTANCE (subscript
) = chrec_dont_know
;
2322 VEC_safe_push (subscript_p
, heap
, DDR_SUBSCRIPTS (res
), subscript
);
2328 /* Frees memory used by the conflict function F. */
2331 free_conflict_function (conflict_function
*f
)
2335 if (CF_NONTRIVIAL_P (f
))
2337 for (i
= 0; i
< f
->n
; i
++)
2338 affine_fn_free (f
->fns
[i
]);
2343 /* Frees memory used by SUBSCRIPTS. */
2346 free_subscripts (VEC (subscript_p
, heap
) *subscripts
)
2351 for (i
= 0; VEC_iterate (subscript_p
, subscripts
, i
, s
); i
++)
2353 free_conflict_function (s
->conflicting_iterations_in_a
);
2354 free_conflict_function (s
->conflicting_iterations_in_b
);
2356 VEC_free (subscript_p
, heap
, subscripts
);
2359 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
2363 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
2366 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2368 fprintf (dump_file
, "(dependence classified: ");
2369 print_generic_expr (dump_file
, chrec
, 0);
2370 fprintf (dump_file
, ")\n");
2373 DDR_ARE_DEPENDENT (ddr
) = chrec
;
2374 free_subscripts (DDR_SUBSCRIPTS (ddr
));
2377 /* The dependence relation DDR cannot be represented by a distance
2381 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
2383 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2384 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
2386 DDR_AFFINE_P (ddr
) = false;
2391 /* This section contains the classic Banerjee tests. */
2393 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
2394 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
2397 ziv_subscript_p (tree chrec_a
,
2400 return (evolution_function_is_constant_p (chrec_a
)
2401 && evolution_function_is_constant_p (chrec_b
));
2404 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
2405 variable, i.e., if the SIV (Single Index Variable) test is true. */
2408 siv_subscript_p (tree chrec_a
,
2411 if ((evolution_function_is_constant_p (chrec_a
)
2412 && evolution_function_is_univariate_p (chrec_b
))
2413 || (evolution_function_is_constant_p (chrec_b
)
2414 && evolution_function_is_univariate_p (chrec_a
)))
2417 if (evolution_function_is_univariate_p (chrec_a
)
2418 && evolution_function_is_univariate_p (chrec_b
))
2420 switch (TREE_CODE (chrec_a
))
2422 case POLYNOMIAL_CHREC
:
2423 switch (TREE_CODE (chrec_b
))
2425 case POLYNOMIAL_CHREC
:
2426 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
2441 /* Creates a conflict function with N dimensions. The affine functions
2442 in each dimension follow. */
2444 static conflict_function
*
2445 conflict_fn (unsigned n
, ...)
2448 conflict_function
*ret
= XCNEW (conflict_function
);
2451 gcc_assert (0 < n
&& n
<= MAX_DIM
);
2455 for (i
= 0; i
< n
; i
++)
2456 ret
->fns
[i
] = va_arg (ap
, affine_fn
);
2462 /* Returns constant affine function with value CST. */
2465 affine_fn_cst (tree cst
)
2467 affine_fn fn
= VEC_alloc (tree
, heap
, 1);
2468 VEC_quick_push (tree
, fn
, cst
);
2472 /* Returns affine function with single variable, CST + COEF * x_DIM. */
2475 affine_fn_univar (tree cst
, unsigned dim
, tree coef
)
2477 affine_fn fn
= VEC_alloc (tree
, heap
, dim
+ 1);
2480 gcc_assert (dim
> 0);
2481 VEC_quick_push (tree
, fn
, cst
);
2482 for (i
= 1; i
< dim
; i
++)
2483 VEC_quick_push (tree
, fn
, integer_zero_node
);
2484 VEC_quick_push (tree
, fn
, coef
);
2488 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
2489 *OVERLAPS_B are initialized to the functions that describe the
2490 relation between the elements accessed twice by CHREC_A and
2491 CHREC_B. For k >= 0, the following property is verified:
2493 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2496 analyze_ziv_subscript (tree chrec_a
,
2498 conflict_function
**overlaps_a
,
2499 conflict_function
**overlaps_b
,
2500 tree
*last_conflicts
)
2503 dependence_stats
.num_ziv
++;
2505 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2506 fprintf (dump_file
, "(analyze_ziv_subscript \n");
2508 chrec_a
= chrec_convert (integer_type_node
, chrec_a
, NULL_TREE
);
2509 chrec_b
= chrec_convert (integer_type_node
, chrec_b
, NULL_TREE
);
2510 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
2512 switch (TREE_CODE (difference
))
2515 if (integer_zerop (difference
))
2517 /* The difference is equal to zero: the accessed index
2518 overlaps for each iteration in the loop. */
2519 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2520 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2521 *last_conflicts
= chrec_dont_know
;
2522 dependence_stats
.num_ziv_dependent
++;
2526 /* The accesses do not overlap. */
2527 *overlaps_a
= conflict_fn_no_dependence ();
2528 *overlaps_b
= conflict_fn_no_dependence ();
2529 *last_conflicts
= integer_zero_node
;
2530 dependence_stats
.num_ziv_independent
++;
2535 /* We're not sure whether the indexes overlap. For the moment,
2536 conservatively answer "don't know". */
2537 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2538 fprintf (dump_file
, "ziv test failed: difference is non-integer.\n");
2540 *overlaps_a
= conflict_fn_not_known ();
2541 *overlaps_b
= conflict_fn_not_known ();
2542 *last_conflicts
= chrec_dont_know
;
2543 dependence_stats
.num_ziv_unimplemented
++;
2547 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2548 fprintf (dump_file
, ")\n");
2551 /* Sets NIT to the estimated number of executions of the statements in
2552 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
2553 large as the number of iterations. If we have no reliable estimate,
2554 the function returns false, otherwise returns true. */
2557 estimated_loop_iterations (struct loop
*loop
, bool conservative
,
2560 estimate_numbers_of_iterations_loop (loop
);
2563 if (!loop
->any_upper_bound
)
2566 *nit
= loop
->nb_iterations_upper_bound
;
2570 if (!loop
->any_estimate
)
2573 *nit
= loop
->nb_iterations_estimate
;
2579 /* Similar to estimated_loop_iterations, but returns the estimate only
2580 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
2581 on the number of iterations of LOOP could not be derived, returns -1. */
2584 estimated_loop_iterations_int (struct loop
*loop
, bool conservative
)
2587 HOST_WIDE_INT hwi_nit
;
2589 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
2592 if (!double_int_fits_in_shwi_p (nit
))
2594 hwi_nit
= double_int_to_shwi (nit
);
2596 return hwi_nit
< 0 ? -1 : hwi_nit
;
2599 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
2600 and only if it fits to the int type. If this is not the case, or the
2601 estimate on the number of iterations of LOOP could not be derived, returns
2605 estimated_loop_iterations_tree (struct loop
*loop
, bool conservative
)
2610 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
2611 return chrec_dont_know
;
2613 type
= lang_hooks
.types
.type_for_size (INT_TYPE_SIZE
, true);
2614 if (!double_int_fits_to_tree_p (type
, nit
))
2615 return chrec_dont_know
;
2617 return double_int_to_tree (type
, nit
);
2620 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2621 constant, and CHREC_B is an affine function. *OVERLAPS_A and
2622 *OVERLAPS_B are initialized to the functions that describe the
2623 relation between the elements accessed twice by CHREC_A and
2624 CHREC_B. For k >= 0, the following property is verified:
2626 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2629 analyze_siv_subscript_cst_affine (tree chrec_a
,
2631 conflict_function
**overlaps_a
,
2632 conflict_function
**overlaps_b
,
2633 tree
*last_conflicts
)
2635 bool value0
, value1
, value2
;
2636 tree difference
, tmp
;
2638 chrec_a
= chrec_convert (integer_type_node
, chrec_a
, NULL_TREE
);
2639 chrec_b
= chrec_convert (integer_type_node
, chrec_b
, NULL_TREE
);
2640 difference
= chrec_fold_minus
2641 (integer_type_node
, initial_condition (chrec_b
), chrec_a
);
2643 if (!chrec_is_positive (initial_condition (difference
), &value0
))
2645 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2646 fprintf (dump_file
, "siv test failed: chrec is not positive.\n");
2648 dependence_stats
.num_siv_unimplemented
++;
2649 *overlaps_a
= conflict_fn_not_known ();
2650 *overlaps_b
= conflict_fn_not_known ();
2651 *last_conflicts
= chrec_dont_know
;
2656 if (value0
== false)
2658 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
2660 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2661 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
2663 *overlaps_a
= conflict_fn_not_known ();
2664 *overlaps_b
= conflict_fn_not_known ();
2665 *last_conflicts
= chrec_dont_know
;
2666 dependence_stats
.num_siv_unimplemented
++;
2675 chrec_b = {10, +, 1}
2678 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
2680 HOST_WIDE_INT numiter
;
2681 struct loop
*loop
= get_chrec_loop (chrec_b
);
2683 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2684 tmp
= fold_build2 (EXACT_DIV_EXPR
, integer_type_node
,
2685 fold_build1 (ABS_EXPR
,
2688 CHREC_RIGHT (chrec_b
));
2689 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
2690 *last_conflicts
= integer_one_node
;
2693 /* Perform weak-zero siv test to see if overlap is
2694 outside the loop bounds. */
2695 numiter
= estimated_loop_iterations_int (loop
, true);
2698 && compare_tree_int (tmp
, numiter
) > 0)
2700 free_conflict_function (*overlaps_a
);
2701 free_conflict_function (*overlaps_b
);
2702 *overlaps_a
= conflict_fn_no_dependence ();
2703 *overlaps_b
= conflict_fn_no_dependence ();
2704 *last_conflicts
= integer_zero_node
;
2705 dependence_stats
.num_siv_independent
++;
2708 dependence_stats
.num_siv_dependent
++;
2712 /* When the step does not divide the difference, there are
2716 *overlaps_a
= conflict_fn_no_dependence ();
2717 *overlaps_b
= conflict_fn_no_dependence ();
2718 *last_conflicts
= integer_zero_node
;
2719 dependence_stats
.num_siv_independent
++;
2728 chrec_b = {10, +, -1}
2730 In this case, chrec_a will not overlap with chrec_b. */
2731 *overlaps_a
= conflict_fn_no_dependence ();
2732 *overlaps_b
= conflict_fn_no_dependence ();
2733 *last_conflicts
= integer_zero_node
;
2734 dependence_stats
.num_siv_independent
++;
2741 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
2743 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2744 fprintf (dump_file
, "siv test failed: chrec not positive.\n");
2746 *overlaps_a
= conflict_fn_not_known ();
2747 *overlaps_b
= conflict_fn_not_known ();
2748 *last_conflicts
= chrec_dont_know
;
2749 dependence_stats
.num_siv_unimplemented
++;
2754 if (value2
== false)
2758 chrec_b = {10, +, -1}
2760 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b
), difference
))
2762 HOST_WIDE_INT numiter
;
2763 struct loop
*loop
= get_chrec_loop (chrec_b
);
2765 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2766 tmp
= fold_build2 (EXACT_DIV_EXPR
,
2767 integer_type_node
, difference
,
2768 CHREC_RIGHT (chrec_b
));
2769 *overlaps_b
= conflict_fn (1, affine_fn_cst (tmp
));
2770 *last_conflicts
= integer_one_node
;
2772 /* Perform weak-zero siv test to see if overlap is
2773 outside the loop bounds. */
2774 numiter
= estimated_loop_iterations_int (loop
, true);
2777 && compare_tree_int (tmp
, numiter
) > 0)
2779 free_conflict_function (*overlaps_a
);
2780 free_conflict_function (*overlaps_b
);
2781 *overlaps_a
= conflict_fn_no_dependence ();
2782 *overlaps_b
= conflict_fn_no_dependence ();
2783 *last_conflicts
= integer_zero_node
;
2784 dependence_stats
.num_siv_independent
++;
2787 dependence_stats
.num_siv_dependent
++;
2791 /* When the step does not divide the difference, there
2795 *overlaps_a
= conflict_fn_no_dependence ();
2796 *overlaps_b
= conflict_fn_no_dependence ();
2797 *last_conflicts
= integer_zero_node
;
2798 dependence_stats
.num_siv_independent
++;
2808 In this case, chrec_a will not overlap with chrec_b. */
2809 *overlaps_a
= conflict_fn_no_dependence ();
2810 *overlaps_b
= conflict_fn_no_dependence ();
2811 *last_conflicts
= integer_zero_node
;
2812 dependence_stats
.num_siv_independent
++;
2820 /* Helper recursive function for initializing the matrix A. Returns
2821 the initial value of CHREC. */
2824 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
2828 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
2829 return int_cst_value (chrec
);
2831 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
2832 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
2835 #define FLOOR_DIV(x,y) ((x) / (y))
2837 /* Solves the special case of the Diophantine equation:
2838 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2840 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2841 number of iterations that loops X and Y run. The overlaps will be
2842 constructed as evolutions in dimension DIM. */
2845 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
2846 affine_fn
*overlaps_a
,
2847 affine_fn
*overlaps_b
,
2848 tree
*last_conflicts
, int dim
)
2850 if (((step_a
> 0 && step_b
> 0)
2851 || (step_a
< 0 && step_b
< 0)))
2853 int step_overlaps_a
, step_overlaps_b
;
2854 int gcd_steps_a_b
, last_conflict
, tau2
;
2856 gcd_steps_a_b
= gcd (step_a
, step_b
);
2857 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
2858 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
2860 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
2861 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
2862 last_conflict
= tau2
;
2864 *overlaps_a
= affine_fn_univar (integer_zero_node
, dim
,
2865 build_int_cst (NULL_TREE
,
2867 *overlaps_b
= affine_fn_univar (integer_zero_node
, dim
,
2868 build_int_cst (NULL_TREE
,
2870 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
2875 *overlaps_a
= affine_fn_cst (integer_zero_node
);
2876 *overlaps_b
= affine_fn_cst (integer_zero_node
);
2877 *last_conflicts
= integer_zero_node
;
2881 /* Solves the special case of a Diophantine equation where CHREC_A is
2882 an affine bivariate function, and CHREC_B is an affine univariate
2883 function. For example,
2885 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2887 has the following overlapping functions:
2889 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2890 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2891 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2893 FORNOW: This is a specialized implementation for a case occurring in
2894 a common benchmark. Implement the general algorithm. */
2897 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
2898 conflict_function
**overlaps_a
,
2899 conflict_function
**overlaps_b
,
2900 tree
*last_conflicts
)
2902 bool xz_p
, yz_p
, xyz_p
;
2903 int step_x
, step_y
, step_z
;
2904 HOST_WIDE_INT niter_x
, niter_y
, niter_z
, niter
;
2905 affine_fn overlaps_a_xz
, overlaps_b_xz
;
2906 affine_fn overlaps_a_yz
, overlaps_b_yz
;
2907 affine_fn overlaps_a_xyz
, overlaps_b_xyz
;
2908 affine_fn ova1
, ova2
, ovb
;
2909 tree last_conflicts_xz
, last_conflicts_yz
, last_conflicts_xyz
;
2911 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
2912 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
2913 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
2915 niter_x
= estimated_loop_iterations_int
2916 (get_chrec_loop (CHREC_LEFT (chrec_a
)), true);
2917 niter_y
= estimated_loop_iterations_int (get_chrec_loop (chrec_a
), true);
2918 niter_z
= estimated_loop_iterations_int (get_chrec_loop (chrec_b
), true);
2920 if (niter_x
< 0 || niter_y
< 0 || niter_z
< 0)
2922 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2923 fprintf (dump_file
, "overlap steps test failed: no iteration counts.\n");
2925 *overlaps_a
= conflict_fn_not_known ();
2926 *overlaps_b
= conflict_fn_not_known ();
2927 *last_conflicts
= chrec_dont_know
;
2931 niter
= MIN (niter_x
, niter_z
);
2932 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
2935 &last_conflicts_xz
, 1);
2936 niter
= MIN (niter_y
, niter_z
);
2937 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
2940 &last_conflicts_yz
, 2);
2941 niter
= MIN (niter_x
, niter_z
);
2942 niter
= MIN (niter_y
, niter
);
2943 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
2946 &last_conflicts_xyz
, 3);
2948 xz_p
= !integer_zerop (last_conflicts_xz
);
2949 yz_p
= !integer_zerop (last_conflicts_yz
);
2950 xyz_p
= !integer_zerop (last_conflicts_xyz
);
2952 if (xz_p
|| yz_p
|| xyz_p
)
2954 ova1
= affine_fn_cst (integer_zero_node
);
2955 ova2
= affine_fn_cst (integer_zero_node
);
2956 ovb
= affine_fn_cst (integer_zero_node
);
2959 affine_fn t0
= ova1
;
2962 ova1
= affine_fn_plus (ova1
, overlaps_a_xz
);
2963 ovb
= affine_fn_plus (ovb
, overlaps_b_xz
);
2964 affine_fn_free (t0
);
2965 affine_fn_free (t2
);
2966 *last_conflicts
= last_conflicts_xz
;
2970 affine_fn t0
= ova2
;
2973 ova2
= affine_fn_plus (ova2
, overlaps_a_yz
);
2974 ovb
= affine_fn_plus (ovb
, overlaps_b_yz
);
2975 affine_fn_free (t0
);
2976 affine_fn_free (t2
);
2977 *last_conflicts
= last_conflicts_yz
;
2981 affine_fn t0
= ova1
;
2982 affine_fn t2
= ova2
;
2985 ova1
= affine_fn_plus (ova1
, overlaps_a_xyz
);
2986 ova2
= affine_fn_plus (ova2
, overlaps_a_xyz
);
2987 ovb
= affine_fn_plus (ovb
, overlaps_b_xyz
);
2988 affine_fn_free (t0
);
2989 affine_fn_free (t2
);
2990 affine_fn_free (t4
);
2991 *last_conflicts
= last_conflicts_xyz
;
2993 *overlaps_a
= conflict_fn (2, ova1
, ova2
);
2994 *overlaps_b
= conflict_fn (1, ovb
);
2998 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
2999 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3000 *last_conflicts
= integer_zero_node
;
3003 affine_fn_free (overlaps_a_xz
);
3004 affine_fn_free (overlaps_b_xz
);
3005 affine_fn_free (overlaps_a_yz
);
3006 affine_fn_free (overlaps_b_yz
);
3007 affine_fn_free (overlaps_a_xyz
);
3008 affine_fn_free (overlaps_b_xyz
);
3011 /* Determines the overlapping elements due to accesses CHREC_A and
3012 CHREC_B, that are affine functions. This function cannot handle
3013 symbolic evolution functions, ie. when initial conditions are
3014 parameters, because it uses lambda matrices of integers. */
3017 analyze_subscript_affine_affine (tree chrec_a
,
3019 conflict_function
**overlaps_a
,
3020 conflict_function
**overlaps_b
,
3021 tree
*last_conflicts
)
3023 unsigned nb_vars_a
, nb_vars_b
, dim
;
3024 int init_a
, init_b
, gamma
, gcd_alpha_beta
;
3026 lambda_matrix A
, U
, S
;
3028 if (eq_evolutions_p (chrec_a
, chrec_b
))
3030 /* The accessed index overlaps for each iteration in the
3032 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3033 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3034 *last_conflicts
= chrec_dont_know
;
3037 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3038 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
3040 /* For determining the initial intersection, we have to solve a
3041 Diophantine equation. This is the most time consuming part.
3043 For answering to the question: "Is there a dependence?" we have
3044 to prove that there exists a solution to the Diophantine
3045 equation, and that the solution is in the iteration domain,
3046 i.e. the solution is positive or zero, and that the solution
3047 happens before the upper bound loop.nb_iterations. Otherwise
3048 there is no dependence. This function outputs a description of
3049 the iterations that hold the intersections. */
3051 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
3052 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
3054 dim
= nb_vars_a
+ nb_vars_b
;
3055 U
= lambda_matrix_new (dim
, dim
);
3056 A
= lambda_matrix_new (dim
, 1);
3057 S
= lambda_matrix_new (dim
, 1);
3059 init_a
= initialize_matrix_A (A
, chrec_a
, 0, 1);
3060 init_b
= initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1);
3061 gamma
= init_b
- init_a
;
3063 /* Don't do all the hard work of solving the Diophantine equation
3064 when we already know the solution: for example,
3067 | gamma = 3 - 3 = 0.
3068 Then the first overlap occurs during the first iterations:
3069 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
3073 if (nb_vars_a
== 1 && nb_vars_b
== 1)
3076 HOST_WIDE_INT niter
, niter_a
, niter_b
;
3079 niter_a
= estimated_loop_iterations_int
3080 (get_chrec_loop (chrec_a
), true);
3081 niter_b
= estimated_loop_iterations_int
3082 (get_chrec_loop (chrec_b
), true);
3083 if (niter_a
< 0 || niter_b
< 0)
3085 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3086 fprintf (dump_file
, "affine-affine test failed: missing iteration counts.\n");
3087 *overlaps_a
= conflict_fn_not_known ();
3088 *overlaps_b
= conflict_fn_not_known ();
3089 *last_conflicts
= chrec_dont_know
;
3090 goto end_analyze_subs_aa
;
3093 niter
= MIN (niter_a
, niter_b
);
3095 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
3096 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
3098 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
3101 *overlaps_a
= conflict_fn (1, ova
);
3102 *overlaps_b
= conflict_fn (1, ovb
);
3105 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
3106 compute_overlap_steps_for_affine_1_2
3107 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
3109 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
3110 compute_overlap_steps_for_affine_1_2
3111 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
3115 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3116 fprintf (dump_file
, "affine-affine test failed: too many variables.\n");
3117 *overlaps_a
= conflict_fn_not_known ();
3118 *overlaps_b
= conflict_fn_not_known ();
3119 *last_conflicts
= chrec_dont_know
;
3121 goto end_analyze_subs_aa
;
3125 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
3130 lambda_matrix_row_negate (U
, dim
, 0);
3132 gcd_alpha_beta
= S
[0][0];
3134 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
3135 but that is a quite strange case. Instead of ICEing, answer
3137 if (gcd_alpha_beta
== 0)
3139 *overlaps_a
= conflict_fn_not_known ();
3140 *overlaps_b
= conflict_fn_not_known ();
3141 *last_conflicts
= chrec_dont_know
;
3142 goto end_analyze_subs_aa
;
3145 /* The classic "gcd-test". */
3146 if (!int_divides_p (gcd_alpha_beta
, gamma
))
3148 /* The "gcd-test" has determined that there is no integer
3149 solution, i.e. there is no dependence. */
3150 *overlaps_a
= conflict_fn_no_dependence ();
3151 *overlaps_b
= conflict_fn_no_dependence ();
3152 *last_conflicts
= integer_zero_node
;
3155 /* Both access functions are univariate. This includes SIV and MIV cases. */
3156 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
3158 /* Both functions should have the same evolution sign. */
3159 if (((A
[0][0] > 0 && -A
[1][0] > 0)
3160 || (A
[0][0] < 0 && -A
[1][0] < 0)))
3162 /* The solutions are given by:
3164 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
3167 For a given integer t. Using the following variables,
3169 | i0 = u11 * gamma / gcd_alpha_beta
3170 | j0 = u12 * gamma / gcd_alpha_beta
3177 | y0 = j0 + j1 * t. */
3181 /* X0 and Y0 are the first iterations for which there is a
3182 dependence. X0, Y0 are two solutions of the Diophantine
3183 equation: chrec_a (X0) = chrec_b (Y0). */
3185 int niter
, niter_a
, niter_b
;
3187 niter_a
= estimated_loop_iterations_int
3188 (get_chrec_loop (chrec_a
), true);
3189 niter_b
= estimated_loop_iterations_int
3190 (get_chrec_loop (chrec_b
), true);
3192 if (niter_a
< 0 || niter_b
< 0)
3194 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3195 fprintf (dump_file
, "affine-affine test failed: missing iteration counts.\n");
3196 *overlaps_a
= conflict_fn_not_known ();
3197 *overlaps_b
= conflict_fn_not_known ();
3198 *last_conflicts
= chrec_dont_know
;
3199 goto end_analyze_subs_aa
;
3202 niter
= MIN (niter_a
, niter_b
);
3204 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
3205 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
3209 if ((i1
== 0 && i0
< 0)
3210 || (j1
== 0 && j0
< 0))
3212 /* There is no solution.
3213 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
3214 falls in here, but for the moment we don't look at the
3215 upper bound of the iteration domain. */
3216 *overlaps_a
= conflict_fn_no_dependence ();
3217 *overlaps_b
= conflict_fn_no_dependence ();
3218 *last_conflicts
= integer_zero_node
;
3225 tau1
= CEIL (-i0
, i1
);
3226 tau2
= FLOOR_DIV (niter
- i0
, i1
);
3230 int last_conflict
, min_multiple
;
3231 tau1
= MAX (tau1
, CEIL (-j0
, j1
));
3232 tau2
= MIN (tau2
, FLOOR_DIV (niter
- j0
, j1
));
3234 x0
= i1
* tau1
+ i0
;
3235 y0
= j1
* tau1
+ j0
;
3237 /* At this point (x0, y0) is one of the
3238 solutions to the Diophantine equation. The
3239 next step has to compute the smallest
3240 positive solution: the first conflicts. */
3241 min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
3242 x0
-= i1
* min_multiple
;
3243 y0
-= j1
* min_multiple
;
3245 tau1
= (x0
- i0
)/i1
;
3246 last_conflict
= tau2
- tau1
;
3248 /* If the overlap occurs outside of the bounds of the
3249 loop, there is no dependence. */
3250 if (x0
> niter
|| y0
> niter
)
3252 *overlaps_a
= conflict_fn_no_dependence ();
3253 *overlaps_b
= conflict_fn_no_dependence ();
3254 *last_conflicts
= integer_zero_node
;
3260 affine_fn_univar (build_int_cst (NULL_TREE
, x0
),
3262 build_int_cst (NULL_TREE
, i1
)));
3265 affine_fn_univar (build_int_cst (NULL_TREE
, y0
),
3267 build_int_cst (NULL_TREE
, j1
)));
3268 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
3273 /* FIXME: For the moment, the upper bound of the
3274 iteration domain for j is not checked. */
3275 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3276 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
3277 *overlaps_a
= conflict_fn_not_known ();
3278 *overlaps_b
= conflict_fn_not_known ();
3279 *last_conflicts
= chrec_dont_know
;
3285 /* FIXME: For the moment, the upper bound of the
3286 iteration domain for i is not checked. */
3287 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3288 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
3289 *overlaps_a
= conflict_fn_not_known ();
3290 *overlaps_b
= conflict_fn_not_known ();
3291 *last_conflicts
= chrec_dont_know
;
3297 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3298 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
3299 *overlaps_a
= conflict_fn_not_known ();
3300 *overlaps_b
= conflict_fn_not_known ();
3301 *last_conflicts
= chrec_dont_know
;
3307 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3308 fprintf (dump_file
, "affine-affine test failed: unimplemented.\n");
3309 *overlaps_a
= conflict_fn_not_known ();
3310 *overlaps_b
= conflict_fn_not_known ();
3311 *last_conflicts
= chrec_dont_know
;
3314 end_analyze_subs_aa
:
3315 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3317 fprintf (dump_file
, " (overlaps_a = ");
3318 dump_conflict_function (dump_file
, *overlaps_a
);
3319 fprintf (dump_file
, ")\n (overlaps_b = ");
3320 dump_conflict_function (dump_file
, *overlaps_b
);
3321 fprintf (dump_file
, ")\n");
3322 fprintf (dump_file
, ")\n");
3326 /* Returns true when analyze_subscript_affine_affine can be used for
3327 determining the dependence relation between chrec_a and chrec_b,
3328 that contain symbols. This function modifies chrec_a and chrec_b
3329 such that the analysis result is the same, and such that they don't
3330 contain symbols, and then can safely be passed to the analyzer.
3332 Example: The analysis of the following tuples of evolutions produce
3333 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
3336 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
3337 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
3341 can_use_analyze_subscript_affine_affine (tree
*chrec_a
, tree
*chrec_b
)
3343 tree diff
, type
, left_a
, left_b
, right_b
;
3345 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a
))
3346 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b
)))
3347 /* FIXME: For the moment not handled. Might be refined later. */
3350 type
= chrec_type (*chrec_a
);
3351 left_a
= CHREC_LEFT (*chrec_a
);
3352 left_b
= chrec_convert (type
, CHREC_LEFT (*chrec_b
), NULL_TREE
);
3353 diff
= chrec_fold_minus (type
, left_a
, left_b
);
3355 if (!evolution_function_is_constant_p (diff
))
3358 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3359 fprintf (dump_file
, "can_use_subscript_aff_aff_for_symbolic \n");
3361 *chrec_a
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_a
),
3362 diff
, CHREC_RIGHT (*chrec_a
));
3363 right_b
= chrec_convert (type
, CHREC_RIGHT (*chrec_b
), NULL_TREE
);
3364 *chrec_b
= build_polynomial_chrec (CHREC_VARIABLE (*chrec_b
),
3365 build_int_cst (type
, 0),
3370 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
3371 *OVERLAPS_B are initialized to the functions that describe the
3372 relation between the elements accessed twice by CHREC_A and
3373 CHREC_B. For k >= 0, the following property is verified:
3375 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
3378 analyze_siv_subscript (tree chrec_a
,
3380 conflict_function
**overlaps_a
,
3381 conflict_function
**overlaps_b
,
3382 tree
*last_conflicts
)
3384 dependence_stats
.num_siv
++;
3386 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3387 fprintf (dump_file
, "(analyze_siv_subscript \n");
3389 if (evolution_function_is_constant_p (chrec_a
)
3390 && evolution_function_is_affine_p (chrec_b
))
3391 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
3392 overlaps_a
, overlaps_b
, last_conflicts
);
3394 else if (evolution_function_is_affine_p (chrec_a
)
3395 && evolution_function_is_constant_p (chrec_b
))
3396 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
3397 overlaps_b
, overlaps_a
, last_conflicts
);
3399 else if (evolution_function_is_affine_p (chrec_a
)
3400 && evolution_function_is_affine_p (chrec_b
))
3402 if (!chrec_contains_symbols (chrec_a
)
3403 && !chrec_contains_symbols (chrec_b
))
3405 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
3406 overlaps_a
, overlaps_b
,
3409 if (CF_NOT_KNOWN_P (*overlaps_a
)
3410 || CF_NOT_KNOWN_P (*overlaps_b
))
3411 dependence_stats
.num_siv_unimplemented
++;
3412 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
3413 || CF_NO_DEPENDENCE_P (*overlaps_b
))
3414 dependence_stats
.num_siv_independent
++;
3416 dependence_stats
.num_siv_dependent
++;
3418 else if (can_use_analyze_subscript_affine_affine (&chrec_a
,
3421 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
3422 overlaps_a
, overlaps_b
,
3424 /* FIXME: The number of iterations is a symbolic expression.
3425 Compute it properly. */
3426 *last_conflicts
= chrec_dont_know
;
3428 if (CF_NOT_KNOWN_P (*overlaps_a
)
3429 || CF_NOT_KNOWN_P (*overlaps_b
))
3430 dependence_stats
.num_siv_unimplemented
++;
3431 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
3432 || CF_NO_DEPENDENCE_P (*overlaps_b
))
3433 dependence_stats
.num_siv_independent
++;
3435 dependence_stats
.num_siv_dependent
++;
3438 goto siv_subscript_dontknow
;
3443 siv_subscript_dontknow
:;
3444 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3445 fprintf (dump_file
, "siv test failed: unimplemented.\n");
3446 *overlaps_a
= conflict_fn_not_known ();
3447 *overlaps_b
= conflict_fn_not_known ();
3448 *last_conflicts
= chrec_dont_know
;
3449 dependence_stats
.num_siv_unimplemented
++;
3452 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3453 fprintf (dump_file
, ")\n");
3456 /* Return true when the property can be computed. RES should contain
3457 true when calling the first time this function, then it is set to
3458 false when one of the evolution steps of an affine CHREC does not
3459 divide the constant CST. */
3462 chrec_steps_divide_constant_p (tree chrec
,
3466 switch (TREE_CODE (chrec
))
3468 case POLYNOMIAL_CHREC
:
3469 if (evolution_function_is_constant_p (CHREC_RIGHT (chrec
)))
3471 if (tree_fold_divides_p (CHREC_RIGHT (chrec
), cst
))
3472 /* Keep RES to true, and iterate on other dimensions. */
3473 return chrec_steps_divide_constant_p (CHREC_LEFT (chrec
), cst
, res
);
3479 /* When the step is a parameter the result is undetermined. */
3483 /* On the initial condition, return true. */
3488 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
3489 *OVERLAPS_B are initialized to the functions that describe the
3490 relation between the elements accessed twice by CHREC_A and
3491 CHREC_B. For k >= 0, the following property is verified:
3493 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
3496 analyze_miv_subscript (tree chrec_a
,
3498 conflict_function
**overlaps_a
,
3499 conflict_function
**overlaps_b
,
3500 tree
*last_conflicts
)
3502 /* FIXME: This is a MIV subscript, not yet handled.
3503 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
3506 In the SIV test we had to solve a Diophantine equation with two
3507 variables. In the MIV case we have to solve a Diophantine
3508 equation with 2*n variables (if the subscript uses n IVs).
3510 bool divide_p
= true;
3512 dependence_stats
.num_miv
++;
3513 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3514 fprintf (dump_file
, "(analyze_miv_subscript \n");
3516 chrec_a
= chrec_convert (integer_type_node
, chrec_a
, NULL_TREE
);
3517 chrec_b
= chrec_convert (integer_type_node
, chrec_b
, NULL_TREE
);
3518 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
3520 if (eq_evolutions_p (chrec_a
, chrec_b
))
3522 /* Access functions are the same: all the elements are accessed
3523 in the same order. */
3524 *overlaps_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3525 *overlaps_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3526 *last_conflicts
= estimated_loop_iterations_tree
3527 (get_chrec_loop (chrec_a
), true);
3528 dependence_stats
.num_miv_dependent
++;
3531 else if (evolution_function_is_constant_p (difference
)
3532 /* For the moment, the following is verified:
3533 evolution_function_is_affine_multivariate_p (chrec_a) */
3534 && chrec_steps_divide_constant_p (chrec_a
, difference
, ÷_p
)
3537 /* testsuite/.../ssa-chrec-33.c
3538 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
3540 The difference is 1, and the evolution steps are equal to 2,
3541 consequently there are no overlapping elements. */
3542 *overlaps_a
= conflict_fn_no_dependence ();
3543 *overlaps_b
= conflict_fn_no_dependence ();
3544 *last_conflicts
= integer_zero_node
;
3545 dependence_stats
.num_miv_independent
++;
3548 else if (evolution_function_is_affine_multivariate_p (chrec_a
)
3549 && !chrec_contains_symbols (chrec_a
)
3550 && evolution_function_is_affine_multivariate_p (chrec_b
)
3551 && !chrec_contains_symbols (chrec_b
))
3553 /* testsuite/.../ssa-chrec-35.c
3554 {0, +, 1}_2 vs. {0, +, 1}_3
3555 the overlapping elements are respectively located at iterations:
3556 {0, +, 1}_x and {0, +, 1}_x,
3557 in other words, we have the equality:
3558 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
3561 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
3562 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
3564 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
3565 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
3567 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
3568 overlaps_a
, overlaps_b
, last_conflicts
);
3570 if (CF_NOT_KNOWN_P (*overlaps_a
)
3571 || CF_NOT_KNOWN_P (*overlaps_b
))
3572 dependence_stats
.num_miv_unimplemented
++;
3573 else if (CF_NO_DEPENDENCE_P (*overlaps_a
)
3574 || CF_NO_DEPENDENCE_P (*overlaps_b
))
3575 dependence_stats
.num_miv_independent
++;
3577 dependence_stats
.num_miv_dependent
++;
3582 /* When the analysis is too difficult, answer "don't know". */
3583 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3584 fprintf (dump_file
, "analyze_miv_subscript test failed: unimplemented.\n");
3586 *overlaps_a
= conflict_fn_not_known ();
3587 *overlaps_b
= conflict_fn_not_known ();
3588 *last_conflicts
= chrec_dont_know
;
3589 dependence_stats
.num_miv_unimplemented
++;
3592 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3593 fprintf (dump_file
, ")\n");
3596 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
3597 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
3598 two functions that describe the iterations that contain conflicting
3601 Remark: For an integer k >= 0, the following equality is true:
3603 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
3607 analyze_overlapping_iterations (tree chrec_a
,
3609 conflict_function
**overlap_iterations_a
,
3610 conflict_function
**overlap_iterations_b
,
3611 tree
*last_conflicts
)
3613 dependence_stats
.num_subscript_tests
++;
3615 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3617 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
3618 fprintf (dump_file
, " (chrec_a = ");
3619 print_generic_expr (dump_file
, chrec_a
, 0);
3620 fprintf (dump_file
, ")\n (chrec_b = ");
3621 print_generic_expr (dump_file
, chrec_b
, 0);
3622 fprintf (dump_file
, ")\n");
3625 if (chrec_a
== NULL_TREE
3626 || chrec_b
== NULL_TREE
3627 || chrec_contains_undetermined (chrec_a
)
3628 || chrec_contains_undetermined (chrec_b
))
3630 dependence_stats
.num_subscript_undetermined
++;
3632 *overlap_iterations_a
= conflict_fn_not_known ();
3633 *overlap_iterations_b
= conflict_fn_not_known ();
3636 /* If they are the same chrec, and are affine, they overlap
3637 on every iteration. */
3638 else if (eq_evolutions_p (chrec_a
, chrec_b
)
3639 && evolution_function_is_affine_multivariate_p (chrec_a
))
3641 dependence_stats
.num_same_subscript_function
++;
3642 *overlap_iterations_a
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3643 *overlap_iterations_b
= conflict_fn (1, affine_fn_cst (integer_zero_node
));
3644 *last_conflicts
= chrec_dont_know
;
3647 /* If they aren't the same, and aren't affine, we can't do anything
3649 else if ((chrec_contains_symbols (chrec_a
)
3650 || chrec_contains_symbols (chrec_b
))
3651 && (!evolution_function_is_affine_multivariate_p (chrec_a
)
3652 || !evolution_function_is_affine_multivariate_p (chrec_b
)))
3654 dependence_stats
.num_subscript_undetermined
++;
3655 *overlap_iterations_a
= conflict_fn_not_known ();
3656 *overlap_iterations_b
= conflict_fn_not_known ();
3659 else if (ziv_subscript_p (chrec_a
, chrec_b
))
3660 analyze_ziv_subscript (chrec_a
, chrec_b
,
3661 overlap_iterations_a
, overlap_iterations_b
,
3664 else if (siv_subscript_p (chrec_a
, chrec_b
))
3665 analyze_siv_subscript (chrec_a
, chrec_b
,
3666 overlap_iterations_a
, overlap_iterations_b
,
3670 analyze_miv_subscript (chrec_a
, chrec_b
,
3671 overlap_iterations_a
, overlap_iterations_b
,
3674 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3676 fprintf (dump_file
, " (overlap_iterations_a = ");
3677 dump_conflict_function (dump_file
, *overlap_iterations_a
);
3678 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
3679 dump_conflict_function (dump_file
, *overlap_iterations_b
);
3680 fprintf (dump_file
, ")\n");
3681 fprintf (dump_file
, ")\n");
3685 /* Helper function for uniquely inserting distance vectors. */
3688 save_dist_v (struct data_dependence_relation
*ddr
, lambda_vector dist_v
)
3693 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, v
); i
++)
3694 if (lambda_vector_equal (v
, dist_v
, DDR_NB_LOOPS (ddr
)))
3697 VEC_safe_push (lambda_vector
, heap
, DDR_DIST_VECTS (ddr
), dist_v
);
3700 /* Helper function for uniquely inserting direction vectors. */
3703 save_dir_v (struct data_dependence_relation
*ddr
, lambda_vector dir_v
)
3708 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIR_VECTS (ddr
), i
, v
); i
++)
3709 if (lambda_vector_equal (v
, dir_v
, DDR_NB_LOOPS (ddr
)))
3712 VEC_safe_push (lambda_vector
, heap
, DDR_DIR_VECTS (ddr
), dir_v
);
3715 /* Add a distance of 1 on all the loops outer than INDEX. If we
3716 haven't yet determined a distance for this outer loop, push a new
3717 distance vector composed of the previous distance, and a distance
3718 of 1 for this outer loop. Example:
3726 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
3727 save (0, 1), then we have to save (1, 0). */
3730 add_outer_distances (struct data_dependence_relation
*ddr
,
3731 lambda_vector dist_v
, int index
)
3733 /* For each outer loop where init_v is not set, the accesses are
3734 in dependence of distance 1 in the loop. */
3735 while (--index
>= 0)
3737 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3738 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
3740 save_dist_v (ddr
, save_v
);
3744 /* Return false when fail to represent the data dependence as a
3745 distance vector. INIT_B is set to true when a component has been
3746 added to the distance vector DIST_V. INDEX_CARRY is then set to
3747 the index in DIST_V that carries the dependence. */
3750 build_classic_dist_vector_1 (struct data_dependence_relation
*ddr
,
3751 struct data_reference
*ddr_a
,
3752 struct data_reference
*ddr_b
,
3753 lambda_vector dist_v
, bool *init_b
,
3757 lambda_vector init_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3759 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3761 tree access_fn_a
, access_fn_b
;
3762 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
3764 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
3766 non_affine_dependence_relation (ddr
);
3770 access_fn_a
= DR_ACCESS_FN (ddr_a
, i
);
3771 access_fn_b
= DR_ACCESS_FN (ddr_b
, i
);
3773 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
3774 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
3777 int index_a
= index_in_loop_nest (CHREC_VARIABLE (access_fn_a
),
3778 DDR_LOOP_NEST (ddr
));
3779 int index_b
= index_in_loop_nest (CHREC_VARIABLE (access_fn_b
),
3780 DDR_LOOP_NEST (ddr
));
3782 /* The dependence is carried by the outermost loop. Example:
3789 In this case, the dependence is carried by loop_1. */
3790 index
= index_a
< index_b
? index_a
: index_b
;
3791 *index_carry
= MIN (index
, *index_carry
);
3793 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
3795 non_affine_dependence_relation (ddr
);
3799 dist
= int_cst_value (SUB_DISTANCE (subscript
));
3801 /* This is the subscript coupling test. If we have already
3802 recorded a distance for this loop (a distance coming from
3803 another subscript), it should be the same. For example,
3804 in the following code, there is no dependence:
3811 if (init_v
[index
] != 0 && dist_v
[index
] != dist
)
3813 finalize_ddr_dependent (ddr
, chrec_known
);
3817 dist_v
[index
] = dist
;
3823 /* This can be for example an affine vs. constant dependence
3824 (T[i] vs. T[3]) that is not an affine dependence and is
3825 not representable as a distance vector. */
3826 non_affine_dependence_relation (ddr
);
3834 /* Return true when the DDR contains two data references that have the
3835 same access functions. */
3838 same_access_functions (struct data_dependence_relation
*ddr
)
3842 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3843 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr
), i
),
3844 DR_ACCESS_FN (DDR_B (ddr
), i
)))
3850 /* Helper function for the case where DDR_A and DDR_B are the same
3851 multivariate access function. */
3854 add_multivariate_self_dist (struct data_dependence_relation
*ddr
, tree c_2
)
3857 tree c_1
= CHREC_LEFT (c_2
);
3858 tree c_0
= CHREC_LEFT (c_1
);
3859 lambda_vector dist_v
;
3861 /* Polynomials with more than 2 variables are not handled yet. */
3862 if (TREE_CODE (c_0
) != INTEGER_CST
)
3864 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
3868 x_2
= index_in_loop_nest (CHREC_VARIABLE (c_2
), DDR_LOOP_NEST (ddr
));
3869 x_1
= index_in_loop_nest (CHREC_VARIABLE (c_1
), DDR_LOOP_NEST (ddr
));
3871 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3872 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3873 dist_v
[x_1
] = int_cst_value (CHREC_RIGHT (c_2
));
3874 dist_v
[x_2
] = -int_cst_value (CHREC_RIGHT (c_1
));
3875 save_dist_v (ddr
, dist_v
);
3877 add_outer_distances (ddr
, dist_v
, x_1
);
3880 /* Helper function for the case where DDR_A and DDR_B are the same
3881 access functions. */
3884 add_other_self_distances (struct data_dependence_relation
*ddr
)
3886 lambda_vector dist_v
;
3888 int index_carry
= DDR_NB_LOOPS (ddr
);
3890 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
3892 tree access_fun
= DR_ACCESS_FN (DDR_A (ddr
), i
);
3894 if (TREE_CODE (access_fun
) == POLYNOMIAL_CHREC
)
3896 if (!evolution_function_is_univariate_p (access_fun
))
3898 if (DDR_NUM_SUBSCRIPTS (ddr
) != 1)
3900 DDR_ARE_DEPENDENT (ddr
) = chrec_dont_know
;
3904 add_multivariate_self_dist (ddr
, DR_ACCESS_FN (DDR_A (ddr
), 0));
3908 index_carry
= MIN (index_carry
,
3909 index_in_loop_nest (CHREC_VARIABLE (access_fun
),
3910 DDR_LOOP_NEST (ddr
)));
3914 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3915 add_outer_distances (ddr
, dist_v
, index_carry
);
3918 /* Compute the classic per loop distance vector. DDR is the data
3919 dependence relation to build a vector from. Return false when fail
3920 to represent the data dependence as a distance vector. */
3923 build_classic_dist_vector (struct data_dependence_relation
*ddr
)
3925 bool init_b
= false;
3926 int index_carry
= DDR_NB_LOOPS (ddr
);
3927 lambda_vector dist_v
;
3929 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
3932 if (same_access_functions (ddr
))
3934 /* Save the 0 vector. */
3935 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3936 save_dist_v (ddr
, dist_v
);
3938 if (DDR_NB_LOOPS (ddr
) > 1)
3939 add_other_self_distances (ddr
);
3944 dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3945 if (!build_classic_dist_vector_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
),
3946 dist_v
, &init_b
, &index_carry
))
3949 /* Save the distance vector if we initialized one. */
3952 /* Verify a basic constraint: classic distance vectors should
3953 always be lexicographically positive.
3955 Data references are collected in the order of execution of
3956 the program, thus for the following loop
3958 | for (i = 1; i < 100; i++)
3959 | for (j = 1; j < 100; j++)
3961 | t = T[j+1][i-1]; // A
3962 | T[j][i] = t + 2; // B
3965 references are collected following the direction of the wind:
3966 A then B. The data dependence tests are performed also
3967 following this order, such that we're looking at the distance
3968 separating the elements accessed by A from the elements later
3969 accessed by B. But in this example, the distance returned by
3970 test_dep (A, B) is lexicographically negative (-1, 1), that
3971 means that the access A occurs later than B with respect to
3972 the outer loop, ie. we're actually looking upwind. In this
3973 case we solve test_dep (B, A) looking downwind to the
3974 lexicographically positive solution, that returns the
3975 distance vector (1, -1). */
3976 if (!lambda_vector_lexico_pos (dist_v
, DDR_NB_LOOPS (ddr
)))
3978 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
3979 subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
));
3980 compute_subscript_distance (ddr
);
3981 build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
3982 save_v
, &init_b
, &index_carry
);
3983 save_dist_v (ddr
, save_v
);
3985 /* In this case there is a dependence forward for all the
3988 | for (k = 1; k < 100; k++)
3989 | for (i = 1; i < 100; i++)
3990 | for (j = 1; j < 100; j++)
3992 | t = T[j+1][i-1]; // A
3993 | T[j][i] = t + 2; // B
4001 if (DDR_NB_LOOPS (ddr
) > 1)
4003 add_outer_distances (ddr
, save_v
, index_carry
);
4004 add_outer_distances (ddr
, dist_v
, index_carry
);
4009 lambda_vector save_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4010 lambda_vector_copy (dist_v
, save_v
, DDR_NB_LOOPS (ddr
));
4011 save_dist_v (ddr
, save_v
);
4013 if (DDR_NB_LOOPS (ddr
) > 1)
4015 lambda_vector opposite_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4017 subscript_dependence_tester_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
));
4018 compute_subscript_distance (ddr
);
4019 build_classic_dist_vector_1 (ddr
, DDR_B (ddr
), DDR_A (ddr
),
4020 opposite_v
, &init_b
, &index_carry
);
4022 add_outer_distances (ddr
, dist_v
, index_carry
);
4023 add_outer_distances (ddr
, opposite_v
, index_carry
);
4029 /* There is a distance of 1 on all the outer loops: Example:
4030 there is a dependence of distance 1 on loop_1 for the array A.
4036 add_outer_distances (ddr
, dist_v
,
4037 lambda_vector_first_nz (dist_v
,
4038 DDR_NB_LOOPS (ddr
), 0));
4041 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4045 fprintf (dump_file
, "(build_classic_dist_vector\n");
4046 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
4048 fprintf (dump_file
, " dist_vector = (");
4049 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
, i
),
4050 DDR_NB_LOOPS (ddr
));
4051 fprintf (dump_file
, " )\n");
4053 fprintf (dump_file
, ")\n");
4059 /* Return the direction for a given distance.
4060 FIXME: Computing dir this way is suboptimal, since dir can catch
4061 cases that dist is unable to represent. */
4063 static inline enum data_dependence_direction
4064 dir_from_dist (int dist
)
4067 return dir_positive
;
4069 return dir_negative
;
4074 /* Compute the classic per loop direction vector. DDR is the data
4075 dependence relation to build a vector from. */
4078 build_classic_dir_vector (struct data_dependence_relation
*ddr
)
4081 lambda_vector dist_v
;
4083 for (i
= 0; VEC_iterate (lambda_vector
, DDR_DIST_VECTS (ddr
), i
, dist_v
); i
++)
4085 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4087 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
4088 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
4090 save_dir_v (ddr
, dir_v
);
4094 /* Helper function. Returns true when there is a dependence between
4095 data references DRA and DRB. */
4098 subscript_dependence_tester_1 (struct data_dependence_relation
*ddr
,
4099 struct data_reference
*dra
,
4100 struct data_reference
*drb
)
4103 tree last_conflicts
;
4104 struct subscript
*subscript
;
4106 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
4109 conflict_function
*overlaps_a
, *overlaps_b
;
4111 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
4112 DR_ACCESS_FN (drb
, i
),
4113 &overlaps_a
, &overlaps_b
,
4116 if (CF_NOT_KNOWN_P (overlaps_a
)
4117 || CF_NOT_KNOWN_P (overlaps_b
))
4119 finalize_ddr_dependent (ddr
, chrec_dont_know
);
4120 dependence_stats
.num_dependence_undetermined
++;
4121 free_conflict_function (overlaps_a
);
4122 free_conflict_function (overlaps_b
);
4126 else if (CF_NO_DEPENDENCE_P (overlaps_a
)
4127 || CF_NO_DEPENDENCE_P (overlaps_b
))
4129 finalize_ddr_dependent (ddr
, chrec_known
);
4130 dependence_stats
.num_dependence_independent
++;
4131 free_conflict_function (overlaps_a
);
4132 free_conflict_function (overlaps_b
);
4138 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
4139 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
4140 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
4147 /* Computes the conflicting iterations, and initialize DDR. */
4150 subscript_dependence_tester (struct data_dependence_relation
*ddr
)
4153 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4154 fprintf (dump_file
, "(subscript_dependence_tester \n");
4156 if (subscript_dependence_tester_1 (ddr
, DDR_A (ddr
), DDR_B (ddr
)))
4157 dependence_stats
.num_dependence_dependent
++;
4159 compute_subscript_distance (ddr
);
4160 if (build_classic_dist_vector (ddr
))
4161 build_classic_dir_vector (ddr
);
4163 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4164 fprintf (dump_file
, ")\n");
4167 /* Returns true when all the access functions of A are affine or
4171 access_functions_are_affine_or_constant_p (struct data_reference
*a
)
4174 VEC(tree
,heap
) *fns
= DR_ACCESS_FNS (a
);
4177 for (i
= 0; VEC_iterate (tree
, fns
, i
, t
); i
++)
4178 if (!evolution_function_is_constant_p (t
)
4179 && !evolution_function_is_affine_multivariate_p (t
))
4185 /* Initializes an equation for an OMEGA problem using the information
4186 contained in the ACCESS_FUN. Returns true when the operation
4189 PB is the omega constraint system.
4190 EQ is the number of the equation to be initialized.
4191 OFFSET is used for shifting the variables names in the constraints:
4192 a constrain is composed of 2 * the number of variables surrounding
4193 dependence accesses. OFFSET is set either to 0 for the first n variables,
4194 then it is set to n.
4195 ACCESS_FUN is expected to be an affine chrec. */
4198 init_omega_eq_with_af (omega_pb pb
, unsigned eq
,
4199 unsigned int offset
, tree access_fun
,
4200 struct data_dependence_relation
*ddr
)
4202 switch (TREE_CODE (access_fun
))
4204 case POLYNOMIAL_CHREC
:
4206 tree left
= CHREC_LEFT (access_fun
);
4207 tree right
= CHREC_RIGHT (access_fun
);
4208 int var
= CHREC_VARIABLE (access_fun
);
4211 if (TREE_CODE (right
) != INTEGER_CST
)
4214 var_idx
= index_in_loop_nest (var
, DDR_LOOP_NEST (ddr
));
4215 pb
->eqs
[eq
].coef
[offset
+ var_idx
+ 1] = int_cst_value (right
);
4217 /* Compute the innermost loop index. */
4218 DDR_INNER_LOOP (ddr
) = MAX (DDR_INNER_LOOP (ddr
), var_idx
);
4221 pb
->eqs
[eq
].coef
[var_idx
+ DDR_NB_LOOPS (ddr
) + 1]
4222 += int_cst_value (right
);
4224 switch (TREE_CODE (left
))
4226 case POLYNOMIAL_CHREC
:
4227 return init_omega_eq_with_af (pb
, eq
, offset
, left
, ddr
);
4230 pb
->eqs
[eq
].coef
[0] += int_cst_value (left
);
4239 pb
->eqs
[eq
].coef
[0] += int_cst_value (access_fun
);
4247 /* As explained in the comments preceding init_omega_for_ddr, we have
4248 to set up a system for each loop level, setting outer loops
4249 variation to zero, and current loop variation to positive or zero.
4250 Save each lexico positive distance vector. */
4253 omega_extract_distance_vectors (omega_pb pb
,
4254 struct data_dependence_relation
*ddr
)
4258 struct loop
*loopi
, *loopj
;
4259 enum omega_result res
;
4261 /* Set a new problem for each loop in the nest. The basis is the
4262 problem that we have initialized until now. On top of this we
4263 add new constraints. */
4264 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
4265 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
4268 omega_pb copy
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
),
4269 DDR_NB_LOOPS (ddr
));
4271 omega_copy_problem (copy
, pb
);
4273 /* For all the outer loops "loop_j", add "dj = 0". */
4275 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
4277 eq
= omega_add_zero_eq (copy
, omega_black
);
4278 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
4281 /* For "loop_i", add "0 <= di". */
4282 geq
= omega_add_zero_geq (copy
, omega_black
);
4283 copy
->geqs
[geq
].coef
[i
+ 1] = 1;
4285 /* Reduce the constraint system, and test that the current
4286 problem is feasible. */
4287 res
= omega_simplify_problem (copy
);
4288 if (res
== omega_false
4289 || res
== omega_unknown
4290 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
4293 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
4294 if (copy
->subs
[eq
].key
== (int) i
+ 1)
4296 dist
= copy
->subs
[eq
].coef
[0];
4302 /* Reinitialize problem... */
4303 omega_copy_problem (copy
, pb
);
4305 j
< i
&& VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), j
, loopj
); j
++)
4307 eq
= omega_add_zero_eq (copy
, omega_black
);
4308 copy
->eqs
[eq
].coef
[j
+ 1] = 1;
4311 /* ..., but this time "di = 1". */
4312 eq
= omega_add_zero_eq (copy
, omega_black
);
4313 copy
->eqs
[eq
].coef
[i
+ 1] = 1;
4314 copy
->eqs
[eq
].coef
[0] = -1;
4316 res
= omega_simplify_problem (copy
);
4317 if (res
== omega_false
4318 || res
== omega_unknown
4319 || copy
->num_geqs
> (int) DDR_NB_LOOPS (ddr
))
4322 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
4323 if (copy
->subs
[eq
].key
== (int) i
+ 1)
4325 dist
= copy
->subs
[eq
].coef
[0];
4331 /* Save the lexicographically positive distance vector. */
4334 lambda_vector dist_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4335 lambda_vector dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4339 for (eq
= 0; eq
< copy
->num_subs
; eq
++)
4340 if (copy
->subs
[eq
].key
> 0)
4342 dist
= copy
->subs
[eq
].coef
[0];
4343 dist_v
[copy
->subs
[eq
].key
- 1] = dist
;
4346 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
4347 dir_v
[j
] = dir_from_dist (dist_v
[j
]);
4349 save_dist_v (ddr
, dist_v
);
4350 save_dir_v (ddr
, dir_v
);
4354 omega_free_problem (copy
);
4358 /* This is called for each subscript of a tuple of data references:
4359 insert an equality for representing the conflicts. */
4362 omega_setup_subscript (tree access_fun_a
, tree access_fun_b
,
4363 struct data_dependence_relation
*ddr
,
4364 omega_pb pb
, bool *maybe_dependent
)
4367 tree fun_a
= chrec_convert (integer_type_node
, access_fun_a
, NULL_TREE
);
4368 tree fun_b
= chrec_convert (integer_type_node
, access_fun_b
, NULL_TREE
);
4369 tree difference
= chrec_fold_minus (integer_type_node
, fun_a
, fun_b
);
4371 /* When the fun_a - fun_b is not constant, the dependence is not
4372 captured by the classic distance vector representation. */
4373 if (TREE_CODE (difference
) != INTEGER_CST
)
4377 if (ziv_subscript_p (fun_a
, fun_b
) && !integer_zerop (difference
))
4379 /* There is no dependence. */
4380 *maybe_dependent
= false;
4384 fun_b
= chrec_fold_multiply (integer_type_node
, fun_b
,
4385 integer_minus_one_node
);
4387 eq
= omega_add_zero_eq (pb
, omega_black
);
4388 if (!init_omega_eq_with_af (pb
, eq
, DDR_NB_LOOPS (ddr
), fun_a
, ddr
)
4389 || !init_omega_eq_with_af (pb
, eq
, 0, fun_b
, ddr
))
4390 /* There is probably a dependence, but the system of
4391 constraints cannot be built: answer "don't know". */
4395 if (DDR_NB_LOOPS (ddr
) != 0 && pb
->eqs
[eq
].coef
[0]
4396 && !int_divides_p (lambda_vector_gcd
4397 ((lambda_vector
) &(pb
->eqs
[eq
].coef
[1]),
4398 2 * DDR_NB_LOOPS (ddr
)),
4399 pb
->eqs
[eq
].coef
[0]))
4401 /* There is no dependence. */
4402 *maybe_dependent
= false;
4409 /* Helper function, same as init_omega_for_ddr but specialized for
4410 data references A and B. */
4413 init_omega_for_ddr_1 (struct data_reference
*dra
, struct data_reference
*drb
,
4414 struct data_dependence_relation
*ddr
,
4415 omega_pb pb
, bool *maybe_dependent
)
4420 unsigned nb_loops
= DDR_NB_LOOPS (ddr
);
4422 /* Insert an equality per subscript. */
4423 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
4425 if (!omega_setup_subscript (DR_ACCESS_FN (dra
, i
), DR_ACCESS_FN (drb
, i
),
4426 ddr
, pb
, maybe_dependent
))
4428 else if (*maybe_dependent
== false)
4430 /* There is no dependence. */
4431 DDR_ARE_DEPENDENT (ddr
) = chrec_known
;
4436 /* Insert inequalities: constraints corresponding to the iteration
4437 domain, i.e. the loops surrounding the references "loop_x" and
4438 the distance variables "dx". The layout of the OMEGA
4439 representation is as follows:
4440 - coef[0] is the constant
4441 - coef[1..nb_loops] are the protected variables that will not be
4442 removed by the solver: the "dx"
4443 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
4445 for (i
= 0; i
<= DDR_INNER_LOOP (ddr
)
4446 && VEC_iterate (loop_p
, DDR_LOOP_NEST (ddr
), i
, loopi
); i
++)
4448 HOST_WIDE_INT nbi
= estimated_loop_iterations_int (loopi
, true);
4451 ineq
= omega_add_zero_geq (pb
, omega_black
);
4452 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
4454 /* 0 <= loop_x + dx */
4455 ineq
= omega_add_zero_geq (pb
, omega_black
);
4456 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = 1;
4457 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
4461 /* loop_x <= nb_iters */
4462 ineq
= omega_add_zero_geq (pb
, omega_black
);
4463 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
4464 pb
->geqs
[ineq
].coef
[0] = nbi
;
4466 /* loop_x + dx <= nb_iters */
4467 ineq
= omega_add_zero_geq (pb
, omega_black
);
4468 pb
->geqs
[ineq
].coef
[i
+ nb_loops
+ 1] = -1;
4469 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
4470 pb
->geqs
[ineq
].coef
[0] = nbi
;
4472 /* A step "dx" bigger than nb_iters is not feasible, so
4473 add "0 <= nb_iters + dx", */
4474 ineq
= omega_add_zero_geq (pb
, omega_black
);
4475 pb
->geqs
[ineq
].coef
[i
+ 1] = 1;
4476 pb
->geqs
[ineq
].coef
[0] = nbi
;
4477 /* and "dx <= nb_iters". */
4478 ineq
= omega_add_zero_geq (pb
, omega_black
);
4479 pb
->geqs
[ineq
].coef
[i
+ 1] = -1;
4480 pb
->geqs
[ineq
].coef
[0] = nbi
;
4484 omega_extract_distance_vectors (pb
, ddr
);
4489 /* Sets up the Omega dependence problem for the data dependence
4490 relation DDR. Returns false when the constraint system cannot be
4491 built, ie. when the test answers "don't know". Returns true
4492 otherwise, and when independence has been proved (using one of the
4493 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
4494 set MAYBE_DEPENDENT to true.
4496 Example: for setting up the dependence system corresponding to the
4497 conflicting accesses
4502 | ... A[2*j, 2*(i + j)]
4506 the following constraints come from the iteration domain:
4513 where di, dj are the distance variables. The constraints
4514 representing the conflicting elements are:
4517 i + 1 = 2 * (i + di + j + dj)
4519 For asking that the resulting distance vector (di, dj) be
4520 lexicographically positive, we insert the constraint "di >= 0". If
4521 "di = 0" in the solution, we fix that component to zero, and we
4522 look at the inner loops: we set a new problem where all the outer
4523 loop distances are zero, and fix this inner component to be
4524 positive. When one of the components is positive, we save that
4525 distance, and set a new problem where the distance on this loop is
4526 zero, searching for other distances in the inner loops. Here is
4527 the classic example that illustrates that we have to set for each
4528 inner loop a new problem:
4536 we have to save two distances (1, 0) and (0, 1).
4538 Given two array references, refA and refB, we have to set the
4539 dependence problem twice, refA vs. refB and refB vs. refA, and we
4540 cannot do a single test, as refB might occur before refA in the
4541 inner loops, and the contrary when considering outer loops: ex.
4546 | T[{1,+,1}_2][{1,+,1}_1] // refA
4547 | T[{2,+,1}_2][{0,+,1}_1] // refB
4552 refB touches the elements in T before refA, and thus for the same
4553 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
4554 but for successive loop_0 iterations, we have (1, -1, 1)
4556 The Omega solver expects the distance variables ("di" in the
4557 previous example) to come first in the constraint system (as
4558 variables to be protected, or "safe" variables), the constraint
4559 system is built using the following layout:
4561 "cst | distance vars | index vars".
4565 init_omega_for_ddr (struct data_dependence_relation
*ddr
,
4566 bool *maybe_dependent
)
4571 *maybe_dependent
= true;
4573 if (same_access_functions (ddr
))
4576 lambda_vector dir_v
;
4578 /* Save the 0 vector. */
4579 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
4580 dir_v
= lambda_vector_new (DDR_NB_LOOPS (ddr
));
4581 for (j
= 0; j
< DDR_NB_LOOPS (ddr
); j
++)
4582 dir_v
[j
] = dir_equal
;
4583 save_dir_v (ddr
, dir_v
);
4585 /* Save the dependences carried by outer loops. */
4586 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
4587 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
4589 omega_free_problem (pb
);
4593 /* Omega expects the protected variables (those that have to be kept
4594 after elimination) to appear first in the constraint system.
4595 These variables are the distance variables. In the following
4596 initialization we declare NB_LOOPS safe variables, and the total
4597 number of variables for the constraint system is 2*NB_LOOPS. */
4598 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
4599 res
= init_omega_for_ddr_1 (DDR_A (ddr
), DDR_B (ddr
), ddr
, pb
,
4601 omega_free_problem (pb
);
4603 /* Stop computation if not decidable, or no dependence. */
4604 if (res
== false || *maybe_dependent
== false)
4607 pb
= omega_alloc_problem (2 * DDR_NB_LOOPS (ddr
), DDR_NB_LOOPS (ddr
));
4608 res
= init_omega_for_ddr_1 (DDR_B (ddr
), DDR_A (ddr
), ddr
, pb
,
4610 omega_free_problem (pb
);
4615 /* Return true when DDR contains the same information as that stored
4616 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
4619 ddr_consistent_p (FILE *file
,
4620 struct data_dependence_relation
*ddr
,
4621 VEC (lambda_vector
, heap
) *dist_vects
,
4622 VEC (lambda_vector
, heap
) *dir_vects
)
4626 /* If dump_file is set, output there. */
4627 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4630 if (VEC_length (lambda_vector
, dist_vects
) != DDR_NUM_DIST_VECTS (ddr
))
4632 lambda_vector b_dist_v
;
4633 fprintf (file
, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
4634 VEC_length (lambda_vector
, dist_vects
),
4635 DDR_NUM_DIST_VECTS (ddr
));
4637 fprintf (file
, "Banerjee dist vectors:\n");
4638 for (i
= 0; VEC_iterate (lambda_vector
, dist_vects
, i
, b_dist_v
); i
++)
4639 print_lambda_vector (file
, b_dist_v
, DDR_NB_LOOPS (ddr
));
4641 fprintf (file
, "Omega dist vectors:\n");
4642 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
4643 print_lambda_vector (file
, DDR_DIST_VECT (ddr
, i
), DDR_NB_LOOPS (ddr
));
4645 fprintf (file
, "data dependence relation:\n");
4646 dump_data_dependence_relation (file
, ddr
);
4648 fprintf (file
, ")\n");
4652 if (VEC_length (lambda_vector
, dir_vects
) != DDR_NUM_DIR_VECTS (ddr
))
4654 fprintf (file
, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
4655 VEC_length (lambda_vector
, dir_vects
),
4656 DDR_NUM_DIR_VECTS (ddr
));
4660 for (i
= 0; i
< DDR_NUM_DIST_VECTS (ddr
); i
++)
4662 lambda_vector a_dist_v
;
4663 lambda_vector b_dist_v
= DDR_DIST_VECT (ddr
, i
);
4665 /* Distance vectors are not ordered in the same way in the DDR
4666 and in the DIST_VECTS: search for a matching vector. */
4667 for (j
= 0; VEC_iterate (lambda_vector
, dist_vects
, j
, a_dist_v
); j
++)
4668 if (lambda_vector_equal (a_dist_v
, b_dist_v
, DDR_NB_LOOPS (ddr
)))
4671 if (j
== VEC_length (lambda_vector
, dist_vects
))
4673 fprintf (file
, "\n(Dist vectors from the first dependence analyzer:\n");
4674 print_dist_vectors (file
, dist_vects
, DDR_NB_LOOPS (ddr
));
4675 fprintf (file
, "not found in Omega dist vectors:\n");
4676 print_dist_vectors (file
, DDR_DIST_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
4677 fprintf (file
, "data dependence relation:\n");
4678 dump_data_dependence_relation (file
, ddr
);
4679 fprintf (file
, ")\n");
4683 for (i
= 0; i
< DDR_NUM_DIR_VECTS (ddr
); i
++)
4685 lambda_vector a_dir_v
;
4686 lambda_vector b_dir_v
= DDR_DIR_VECT (ddr
, i
);
4688 /* Direction vectors are not ordered in the same way in the DDR
4689 and in the DIR_VECTS: search for a matching vector. */
4690 for (j
= 0; VEC_iterate (lambda_vector
, dir_vects
, j
, a_dir_v
); j
++)
4691 if (lambda_vector_equal (a_dir_v
, b_dir_v
, DDR_NB_LOOPS (ddr
)))
4694 if (j
== VEC_length (lambda_vector
, dist_vects
))
4696 fprintf (file
, "\n(Dir vectors from the first dependence analyzer:\n");
4697 print_dir_vectors (file
, dir_vects
, DDR_NB_LOOPS (ddr
));
4698 fprintf (file
, "not found in Omega dir vectors:\n");
4699 print_dir_vectors (file
, DDR_DIR_VECTS (ddr
), DDR_NB_LOOPS (ddr
));
4700 fprintf (file
, "data dependence relation:\n");
4701 dump_data_dependence_relation (file
, ddr
);
4702 fprintf (file
, ")\n");
4709 /* This computes the affine dependence relation between A and B.
4710 CHREC_KNOWN is used for representing the independence between two
4711 accesses, while CHREC_DONT_KNOW is used for representing the unknown
4714 Note that it is possible to stop the computation of the dependence
4715 relation the first time we detect a CHREC_KNOWN element for a given
4719 compute_affine_dependence (struct data_dependence_relation
*ddr
)
4721 struct data_reference
*dra
= DDR_A (ddr
);
4722 struct data_reference
*drb
= DDR_B (ddr
);
4724 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4726 fprintf (dump_file
, "(compute_affine_dependence\n");
4727 fprintf (dump_file
, " (stmt_a = \n");
4728 print_generic_expr (dump_file
, DR_STMT (dra
), 0);
4729 fprintf (dump_file
, ")\n (stmt_b = \n");
4730 print_generic_expr (dump_file
, DR_STMT (drb
), 0);
4731 fprintf (dump_file
, ")\n");
4734 /* Analyze only when the dependence relation is not yet known. */
4735 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4737 dependence_stats
.num_dependence_tests
++;
4739 if (access_functions_are_affine_or_constant_p (dra
)
4740 && access_functions_are_affine_or_constant_p (drb
))
4742 if (flag_check_data_deps
)
4744 /* Compute the dependences using the first algorithm. */
4745 subscript_dependence_tester (ddr
);
4747 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4749 fprintf (dump_file
, "\n\nBanerjee Analyzer\n");
4750 dump_data_dependence_relation (dump_file
, ddr
);
4753 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
4755 bool maybe_dependent
;
4756 VEC (lambda_vector
, heap
) *dir_vects
, *dist_vects
;
4758 /* Save the result of the first DD analyzer. */
4759 dist_vects
= DDR_DIST_VECTS (ddr
);
4760 dir_vects
= DDR_DIR_VECTS (ddr
);
4762 /* Reset the information. */
4763 DDR_DIST_VECTS (ddr
) = NULL
;
4764 DDR_DIR_VECTS (ddr
) = NULL
;
4766 /* Compute the same information using Omega. */
4767 if (!init_omega_for_ddr (ddr
, &maybe_dependent
))
4768 goto csys_dont_know
;
4770 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4772 fprintf (dump_file
, "Omega Analyzer\n");
4773 dump_data_dependence_relation (dump_file
, ddr
);
4776 /* Check that we get the same information. */
4777 if (maybe_dependent
)
4778 gcc_assert (ddr_consistent_p (stderr
, ddr
, dist_vects
,
4783 subscript_dependence_tester (ddr
);
4786 /* As a last case, if the dependence cannot be determined, or if
4787 the dependence is considered too difficult to determine, answer
4792 dependence_stats
.num_dependence_undetermined
++;
4794 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4796 fprintf (dump_file
, "Data ref a:\n");
4797 dump_data_reference (dump_file
, dra
);
4798 fprintf (dump_file
, "Data ref b:\n");
4799 dump_data_reference (dump_file
, drb
);
4800 fprintf (dump_file
, "affine dependence test not usable: access function not affine or constant.\n");
4802 finalize_ddr_dependent (ddr
, chrec_dont_know
);
4806 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4807 fprintf (dump_file
, ")\n");
4810 /* This computes the dependence relation for the same data
4811 reference into DDR. */
4814 compute_self_dependence (struct data_dependence_relation
*ddr
)
4817 struct subscript
*subscript
;
4819 for (i
= 0; VEC_iterate (subscript_p
, DDR_SUBSCRIPTS (ddr
), i
, subscript
);
4822 /* The accessed index overlaps for each iteration. */
4823 SUB_CONFLICTS_IN_A (subscript
)
4824 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
4825 SUB_CONFLICTS_IN_B (subscript
)
4826 = conflict_fn (1, affine_fn_cst (integer_zero_node
));
4827 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
4830 /* The distance vector is the zero vector. */
4831 save_dist_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
4832 save_dir_v (ddr
, lambda_vector_new (DDR_NB_LOOPS (ddr
)));
4835 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4836 the data references in DATAREFS, in the LOOP_NEST. When
4837 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4841 compute_all_dependences (VEC (data_reference_p
, heap
) *datarefs
,
4842 VEC (ddr_p
, heap
) **dependence_relations
,
4843 VEC (loop_p
, heap
) *loop_nest
,
4844 bool compute_self_and_rr
)
4846 struct data_dependence_relation
*ddr
;
4847 struct data_reference
*a
, *b
;
4850 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
4851 for (j
= i
+ 1; VEC_iterate (data_reference_p
, datarefs
, j
, b
); j
++)
4852 if (!DR_IS_READ (a
) || !DR_IS_READ (b
) || compute_self_and_rr
)
4854 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
4855 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4856 compute_affine_dependence (ddr
);
4859 if (compute_self_and_rr
)
4860 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, a
); i
++)
4862 ddr
= initialize_data_dependence_relation (a
, a
, loop_nest
);
4863 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
4864 compute_self_dependence (ddr
);
4868 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4869 true if STMT clobbers memory, false otherwise. */
4872 get_references_in_stmt (tree stmt
, VEC (data_ref_loc
, heap
) **references
)
4874 bool clobbers_memory
= false;
4876 tree
*op0
, *op1
, arg
, call
;
4877 call_expr_arg_iterator iter
;
4881 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4882 Calls have side-effects, except those to const or pure
4884 call
= get_call_expr_in (stmt
);
4886 && !(call_expr_flags (call
) & (ECF_CONST
| ECF_PURE
)))
4887 || (TREE_CODE (stmt
) == ASM_EXPR
4888 && ASM_VOLATILE_P (stmt
)))
4889 clobbers_memory
= true;
4891 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
4892 return clobbers_memory
;
4894 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
4896 op0
= &GIMPLE_STMT_OPERAND (stmt
, 0);
4897 op1
= &GIMPLE_STMT_OPERAND (stmt
, 1);
4900 || REFERENCE_CLASS_P (*op1
))
4902 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4904 ref
->is_read
= true;
4908 || REFERENCE_CLASS_P (*op0
))
4910 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4912 ref
->is_read
= false;
4918 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, call
)
4922 || REFERENCE_CLASS_P (*op0
))
4924 ref
= VEC_safe_push (data_ref_loc
, heap
, *references
, NULL
);
4926 ref
->is_read
= true;
4931 return clobbers_memory
;
4934 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4935 reference, returns false, otherwise returns true. */
4938 find_data_references_in_stmt (tree stmt
,
4939 VEC (data_reference_p
, heap
) **datarefs
)
4942 VEC (data_ref_loc
, heap
) *references
;
4945 data_reference_p dr
;
4947 if (get_references_in_stmt (stmt
, &references
))
4949 VEC_free (data_ref_loc
, heap
, references
);
4953 for (i
= 0; VEC_iterate (data_ref_loc
, references
, i
, ref
); i
++)
4955 dr
= create_data_ref (*ref
->pos
, stmt
, ref
->is_read
);
4957 VEC_safe_push (data_reference_p
, heap
, *datarefs
, dr
);
4964 VEC_free (data_ref_loc
, heap
, references
);
4968 /* Search the data references in LOOP, and record the information into
4969 DATAREFS. Returns chrec_dont_know when failing to analyze a
4970 difficult case, returns NULL_TREE otherwise.
4972 TODO: This function should be made smarter so that it can handle address
4973 arithmetic as if they were array accesses, etc. */
4976 find_data_references_in_loop (struct loop
*loop
,
4977 VEC (data_reference_p
, heap
) **datarefs
)
4979 basic_block bb
, *bbs
;
4981 block_stmt_iterator bsi
;
4983 bbs
= get_loop_body (loop
);
4985 for (i
= 0; i
< loop
->num_nodes
; i
++)
4989 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4991 tree stmt
= bsi_stmt (bsi
);
4993 if (!find_data_references_in_stmt (stmt
, datarefs
))
4995 struct data_reference
*res
;
4996 res
= XNEW (struct data_reference
);
4997 DR_STMT (res
) = NULL_TREE
;
4998 DR_REF (res
) = NULL_TREE
;
4999 DR_BASE_OBJECT (res
) = NULL
;
5000 DR_TYPE (res
) = ARRAY_REF_TYPE
;
5001 DR_SET_ACCESS_FNS (res
, NULL
);
5002 DR_BASE_OBJECT (res
) = NULL
;
5003 DR_IS_READ (res
) = false;
5004 DR_BASE_ADDRESS (res
) = NULL_TREE
;
5005 DR_OFFSET (res
) = NULL_TREE
;
5006 DR_INIT (res
) = NULL_TREE
;
5007 DR_STEP (res
) = NULL_TREE
;
5008 DR_OFFSET_MISALIGNMENT (res
) = NULL_TREE
;
5009 DR_MEMTAG (res
) = NULL_TREE
;
5010 DR_PTR_INFO (res
) = NULL
;
5011 VEC_safe_push (data_reference_p
, heap
, *datarefs
, res
);
5014 return chrec_dont_know
;
5023 /* Recursive helper function. */
5026 find_loop_nest_1 (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
5028 /* Inner loops of the nest should not contain siblings. Example:
5029 when there are two consecutive loops,
5040 the dependence relation cannot be captured by the distance
5045 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
5047 return find_loop_nest_1 (loop
->inner
, loop_nest
);
5051 /* Return false when the LOOP is not well nested. Otherwise return
5052 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
5053 contain the loops from the outermost to the innermost, as they will
5054 appear in the classic distance vector. */
5057 find_loop_nest (struct loop
*loop
, VEC (loop_p
, heap
) **loop_nest
)
5059 VEC_safe_push (loop_p
, heap
, *loop_nest
, loop
);
5061 return find_loop_nest_1 (loop
->inner
, loop_nest
);
5065 /* Given a loop nest LOOP, the following vectors are returned:
5066 DATAREFS is initialized to all the array elements contained in this loop,
5067 DEPENDENCE_RELATIONS contains the relations between the data references.
5068 Compute read-read and self relations if
5069 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
5072 compute_data_dependences_for_loop (struct loop
*loop
,
5073 bool compute_self_and_read_read_dependences
,
5074 VEC (data_reference_p
, heap
) **datarefs
,
5075 VEC (ddr_p
, heap
) **dependence_relations
)
5077 struct loop
*loop_nest
= loop
;
5078 VEC (loop_p
, heap
) *vloops
= VEC_alloc (loop_p
, heap
, 3);
5080 memset (&dependence_stats
, 0, sizeof (dependence_stats
));
5082 /* If the loop nest is not well formed, or one of the data references
5083 is not computable, give up without spending time to compute other
5086 || !find_loop_nest (loop_nest
, &vloops
)
5087 || find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
5089 struct data_dependence_relation
*ddr
;
5091 /* Insert a single relation into dependence_relations:
5093 ddr
= initialize_data_dependence_relation (NULL
, NULL
, vloops
);
5094 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
5097 compute_all_dependences (*datarefs
, dependence_relations
, vloops
,
5098 compute_self_and_read_read_dependences
);
5100 if (dump_file
&& (dump_flags
& TDF_STATS
))
5102 fprintf (dump_file
, "Dependence tester statistics:\n");
5104 fprintf (dump_file
, "Number of dependence tests: %d\n",
5105 dependence_stats
.num_dependence_tests
);
5106 fprintf (dump_file
, "Number of dependence tests classified dependent: %d\n",
5107 dependence_stats
.num_dependence_dependent
);
5108 fprintf (dump_file
, "Number of dependence tests classified independent: %d\n",
5109 dependence_stats
.num_dependence_independent
);
5110 fprintf (dump_file
, "Number of undetermined dependence tests: %d\n",
5111 dependence_stats
.num_dependence_undetermined
);
5113 fprintf (dump_file
, "Number of subscript tests: %d\n",
5114 dependence_stats
.num_subscript_tests
);
5115 fprintf (dump_file
, "Number of undetermined subscript tests: %d\n",
5116 dependence_stats
.num_subscript_undetermined
);
5117 fprintf (dump_file
, "Number of same subscript function: %d\n",
5118 dependence_stats
.num_same_subscript_function
);
5120 fprintf (dump_file
, "Number of ziv tests: %d\n",
5121 dependence_stats
.num_ziv
);
5122 fprintf (dump_file
, "Number of ziv tests returning dependent: %d\n",
5123 dependence_stats
.num_ziv_dependent
);
5124 fprintf (dump_file
, "Number of ziv tests returning independent: %d\n",
5125 dependence_stats
.num_ziv_independent
);
5126 fprintf (dump_file
, "Number of ziv tests unimplemented: %d\n",
5127 dependence_stats
.num_ziv_unimplemented
);
5129 fprintf (dump_file
, "Number of siv tests: %d\n",
5130 dependence_stats
.num_siv
);
5131 fprintf (dump_file
, "Number of siv tests returning dependent: %d\n",
5132 dependence_stats
.num_siv_dependent
);
5133 fprintf (dump_file
, "Number of siv tests returning independent: %d\n",
5134 dependence_stats
.num_siv_independent
);
5135 fprintf (dump_file
, "Number of siv tests unimplemented: %d\n",
5136 dependence_stats
.num_siv_unimplemented
);
5138 fprintf (dump_file
, "Number of miv tests: %d\n",
5139 dependence_stats
.num_miv
);
5140 fprintf (dump_file
, "Number of miv tests returning dependent: %d\n",
5141 dependence_stats
.num_miv_dependent
);
5142 fprintf (dump_file
, "Number of miv tests returning independent: %d\n",
5143 dependence_stats
.num_miv_independent
);
5144 fprintf (dump_file
, "Number of miv tests unimplemented: %d\n",
5145 dependence_stats
.num_miv_unimplemented
);
5149 /* Entry point (for testing only). Analyze all the data references
5150 and the dependence relations in LOOP.
5152 The data references are computed first.
5154 A relation on these nodes is represented by a complete graph. Some
5155 of the relations could be of no interest, thus the relations can be
5158 In the following function we compute all the relations. This is
5159 just a first implementation that is here for:
5160 - for showing how to ask for the dependence relations,
5161 - for the debugging the whole dependence graph,
5162 - for the dejagnu testcases and maintenance.
5164 It is possible to ask only for a part of the graph, avoiding to
5165 compute the whole dependence graph. The computed dependences are
5166 stored in a knowledge base (KB) such that later queries don't
5167 recompute the same information. The implementation of this KB is
5168 transparent to the optimizer, and thus the KB can be changed with a
5169 more efficient implementation, or the KB could be disabled. */
5171 analyze_all_data_dependences (struct loop
*loop
)
5174 int nb_data_refs
= 10;
5175 VEC (data_reference_p
, heap
) *datarefs
=
5176 VEC_alloc (data_reference_p
, heap
, nb_data_refs
);
5177 VEC (ddr_p
, heap
) *dependence_relations
=
5178 VEC_alloc (ddr_p
, heap
, nb_data_refs
* nb_data_refs
);
5180 /* Compute DDs on the whole function. */
5181 compute_data_dependences_for_loop (loop
, false, &datarefs
,
5182 &dependence_relations
);
5186 dump_data_dependence_relations (dump_file
, dependence_relations
);
5187 fprintf (dump_file
, "\n\n");
5189 if (dump_flags
& TDF_DETAILS
)
5190 dump_dist_dir_vectors (dump_file
, dependence_relations
);
5192 if (dump_flags
& TDF_STATS
)
5194 unsigned nb_top_relations
= 0;
5195 unsigned nb_bot_relations
= 0;
5196 unsigned nb_basename_differ
= 0;
5197 unsigned nb_chrec_relations
= 0;
5198 struct data_dependence_relation
*ddr
;
5200 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
5202 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
5205 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
5207 struct data_reference
*a
= DDR_A (ddr
);
5208 struct data_reference
*b
= DDR_B (ddr
);
5211 if ((DR_BASE_OBJECT (a
) && DR_BASE_OBJECT (b
)
5212 && DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
))
5213 || (base_object_differ_p (a
, b
, &differ_p
)
5215 nb_basename_differ
++;
5221 nb_chrec_relations
++;
5224 gather_stats_on_scev_database ();
5228 free_dependence_relations (dependence_relations
);
5229 free_data_refs (datarefs
);
5232 /* Computes all the data dependences and check that the results of
5233 several analyzers are the same. */
5236 tree_check_data_deps (void)
5239 struct loop
*loop_nest
;
5241 FOR_EACH_LOOP (li
, loop_nest
, 0)
5242 analyze_all_data_dependences (loop_nest
);
5245 /* Free the memory used by a data dependence relation DDR. */
5248 free_dependence_relation (struct data_dependence_relation
*ddr
)
5253 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_SUBSCRIPTS (ddr
))
5254 free_subscripts (DDR_SUBSCRIPTS (ddr
));
5259 /* Free the memory used by the data dependence relations from
5260 DEPENDENCE_RELATIONS. */
5263 free_dependence_relations (VEC (ddr_p
, heap
) *dependence_relations
)
5266 struct data_dependence_relation
*ddr
;
5267 VEC (loop_p
, heap
) *loop_nest
= NULL
;
5269 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
5273 if (loop_nest
== NULL
)
5274 loop_nest
= DDR_LOOP_NEST (ddr
);
5276 gcc_assert (DDR_LOOP_NEST (ddr
) == NULL
5277 || DDR_LOOP_NEST (ddr
) == loop_nest
);
5278 free_dependence_relation (ddr
);
5282 VEC_free (loop_p
, heap
, loop_nest
);
5283 VEC_free (ddr_p
, heap
, dependence_relations
);
5286 /* Free the memory used by the data references from DATAREFS. */
5289 free_data_refs (VEC (data_reference_p
, heap
) *datarefs
)
5292 struct data_reference
*dr
;
5294 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
5296 VEC_free (data_reference_p
, heap
, datarefs
);