1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 /* This pass walks a given loop structure searching for array
23 references. The information about the array accesses is recorded
24 in DATA_REFERENCE structures.
26 The basic test for determining the dependences is:
27 given two access functions chrec1 and chrec2 to a same array, and
28 x and y two vectors from the iteration domain, the same element of
29 the array is accessed twice at iterations x and y if and only if:
30 | chrec1 (x) == chrec2 (y).
32 The goals of this analysis are:
34 - to determine the independence: the relation between two
35 independent accesses is qualified with the chrec_known (this
36 information allows a loop parallelization),
38 - when two data references access the same data, to qualify the
39 dependence relation with classic dependence representations:
43 - loop carried level dependence
44 - polyhedron dependence
45 or with the chains of recurrences based representation,
47 - to define a knowledge base for storing the data dependence
50 - to define an interface to access this data.
55 - subscript: given two array accesses a subscript is the tuple
56 composed of the access functions for a given dimension. Example:
57 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
58 (f1, g1), (f2, g2), (f3, g3).
60 - Diophantine equation: an equation whose coefficients and
61 solutions are integer constants, for example the equation
63 has an integer solution x = 1 and y = -1.
67 - "Advanced Compilation for High Performance Computing" by Randy
68 Allen and Ken Kennedy.
69 http://citeseer.ist.psu.edu/goff91practical.html
71 - "Loop Transformations for Restructuring Compilers - The Foundations"
79 #include "coretypes.h"
84 /* These RTL headers are needed for basic-block.h. */
86 #include "basic-block.h"
87 #include "diagnostic.h"
88 #include "tree-flow.h"
89 #include "tree-dump.h"
92 #include "tree-chrec.h"
93 #include "tree-data-ref.h"
94 #include "tree-scalar-evolution.h"
95 #include "tree-pass.h"
97 static tree object_analysis (tree, tree, bool, struct data_reference **,
98 tree *, tree *, tree *, tree *, tree *,
99 struct ptr_info_def **, subvar_t *);
100 static struct data_reference * init_data_ref (tree, tree, tree, tree, bool,
101 tree, tree, tree, tree, tree,
102 struct ptr_info_def *,
105 /* Determine if PTR and DECL may alias, the result is put in ALIASED.
106 Return FALSE if there is no type memory tag for PTR.
109 ptr_decl_may_alias_p (tree ptr, tree decl,
110 struct data_reference *ptr_dr,
115 gcc_assert (TREE_CODE (ptr) == SSA_NAME && DECL_P (decl));
117 tag = get_var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
119 tag = DR_MEMTAG (ptr_dr);
123 *aliased = is_aliased_with (tag, decl);
128 /* Determine if two pointers may alias, the result is put in ALIASED.
129 Return FALSE if there is no type memory tag for one of the pointers.
132 ptr_ptr_may_alias_p (tree ptr_a, tree ptr_b,
133 struct data_reference *dra,
134 struct data_reference *drb,
139 tag_a = get_var_ann (SSA_NAME_VAR (ptr_a))->type_mem_tag;
141 tag_a = DR_MEMTAG (dra);
144 tag_b = get_var_ann (SSA_NAME_VAR (ptr_b))->type_mem_tag;
146 tag_b = DR_MEMTAG (drb);
149 *aliased = (tag_a == tag_b);
154 /* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED.
155 Return FALSE if there is no type memory tag for one of the symbols.
158 may_alias_p (tree base_a, tree base_b,
159 struct data_reference *dra,
160 struct data_reference *drb,
163 if (TREE_CODE (base_a) == ADDR_EXPR || TREE_CODE (base_b) == ADDR_EXPR)
165 if (TREE_CODE (base_a) == ADDR_EXPR && TREE_CODE (base_b) == ADDR_EXPR)
167 *aliased = (TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0));
170 if (TREE_CODE (base_a) == ADDR_EXPR)
171 return ptr_decl_may_alias_p (base_b, TREE_OPERAND (base_a, 0), drb,
174 return ptr_decl_may_alias_p (base_a, TREE_OPERAND (base_b, 0), dra,
178 return ptr_ptr_may_alias_p (base_a, base_b, dra, drb, aliased);
182 /* Determine if a pointer (BASE_A) and a record/union access (BASE_B)
183 are not aliased. Return TRUE if they differ. */
185 record_ptr_differ_p (struct data_reference *dra,
186 struct data_reference *drb)
189 tree base_a = DR_BASE_OBJECT (dra);
190 tree base_b = DR_BASE_OBJECT (drb);
192 if (TREE_CODE (base_b) != COMPONENT_REF)
195 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
196 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
197 Probably will be unnecessary with struct alias analysis. */
198 while (TREE_CODE (base_b) == COMPONENT_REF)
199 base_b = TREE_OPERAND (base_b, 0);
200 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
202 if (TREE_CODE (base_a) == INDIRECT_REF
203 && ((TREE_CODE (base_b) == VAR_DECL
204 && (ptr_decl_may_alias_p (TREE_OPERAND (base_a, 0), base_b, dra,
207 || (TREE_CODE (base_b) == INDIRECT_REF
208 && (ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0),
209 TREE_OPERAND (base_b, 0), dra, drb,
218 /* Determine if an array access (BASE_A) and a record/union access (BASE_B)
219 are not aliased. Return TRUE if they differ. */
221 record_array_differ_p (struct data_reference *dra,
222 struct data_reference *drb)
225 tree base_a = DR_BASE_OBJECT (dra);
226 tree base_b = DR_BASE_OBJECT (drb);
228 if (TREE_CODE (base_b) != COMPONENT_REF)
231 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
232 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
233 Probably will be unnecessary with struct alias analysis. */
234 while (TREE_CODE (base_b) == COMPONENT_REF)
235 base_b = TREE_OPERAND (base_b, 0);
237 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
238 (a[i]). In case of p->c[i] use alias analysis to verify that p is not
240 if (TREE_CODE (base_a) == VAR_DECL
241 && (TREE_CODE (base_b) == VAR_DECL
242 || (TREE_CODE (base_b) == INDIRECT_REF
243 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb,
252 /* Determine if an array access (BASE_A) and a pointer (BASE_B)
253 are not aliased. Return TRUE if they differ. */
255 array_ptr_differ_p (tree base_a, tree base_b,
256 struct data_reference *drb)
260 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
261 help of alias analysis that p is not pointing to a. */
262 if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == INDIRECT_REF
263 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, &aliased)
271 /* This is the simplest data dependence test: determines whether the
272 data references A and B access the same array/region. Returns
273 false when the property is not computable at compile time.
274 Otherwise return true, and DIFFER_P will record the result. This
275 utility will not be necessary when alias_sets_conflict_p will be
276 less conservative. */
279 base_object_differ_p (struct data_reference *a,
280 struct data_reference *b,
283 tree base_a = DR_BASE_OBJECT (a);
284 tree base_b = DR_BASE_OBJECT (b);
287 if (!base_a || !base_b)
290 /* Determine if same base. Example: for the array accesses
291 a[i], b[i] or pointer accesses *a, *b, bases are a, b. */
292 if (base_a == base_b)
298 /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
300 if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
301 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0))
307 /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */
308 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
309 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)
310 && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1))
317 /* Determine if different bases. */
319 /* At this point we know that base_a != base_b. However, pointer
320 accesses of the form x=(*p) and y=(*q), whose bases are p and q,
321 may still be pointing to the same base. In SSAed GIMPLE p and q will
322 be SSA_NAMES in this case. Therefore, here we check if they are
323 really two different declarations. */
324 if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
330 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
331 help of alias analysis that p is not pointing to a. */
332 if (array_ptr_differ_p (base_a, base_b, b)
333 || array_ptr_differ_p (base_b, base_a, a))
339 /* If the bases are pointers ((*q)[i] and (*p)[i]), we check with the
340 help of alias analysis they don't point to the same bases. */
341 if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
342 && (may_alias_p (TREE_OPERAND (base_a, 0), TREE_OPERAND (base_b, 0), a, b,
350 /* Compare two record/union bases s.a and t.b: s != t or (a != b and
351 s and t are not unions). */
352 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
353 && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
354 && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
355 && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
356 || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE
357 && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
358 && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
364 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
366 if (record_ptr_differ_p (a, b) || record_ptr_differ_p (b, a))
372 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
373 (a[i]). In case of p->c[i] use alias analysis to verify that p is not
375 if (record_array_differ_p (a, b) || record_array_differ_p (b, a))
384 /* Function base_addr_differ_p.
386 This is the simplest data dependence test: determines whether the
387 data references DRA and DRB access the same array/region. Returns
388 false when the property is not computable at compile time.
389 Otherwise return true, and DIFFER_P will record the result.
392 1. if (both DRA and DRB are represented as arrays)
393 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT
394 2. else if (both DRA and DRB are represented as pointers)
395 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION
396 3. else if (DRA and DRB are represented differently or 2. fails)
397 only try to prove that the bases are surely different
402 base_addr_differ_p (struct data_reference *dra,
403 struct data_reference *drb,
406 tree addr_a = DR_BASE_ADDRESS (dra);
407 tree addr_b = DR_BASE_ADDRESS (drb);
411 if (!addr_a || !addr_b)
414 type_a = TREE_TYPE (addr_a);
415 type_b = TREE_TYPE (addr_b);
417 gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
419 /* 1. if (both DRA and DRB are represented as arrays)
420 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT. */
421 if (DR_TYPE (dra) == ARRAY_REF_TYPE && DR_TYPE (drb) == ARRAY_REF_TYPE)
422 return base_object_differ_p (dra, drb, differ_p);
425 /* 2. else if (both DRA and DRB are represented as pointers)
426 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION. */
427 /* If base addresses are the same, we check the offsets, since the access of
428 the data-ref is described by {base addr + offset} and its access function,
429 i.e., in order to decide whether the bases of data-refs are the same we
430 compare both base addresses and offsets. */
431 if (DR_TYPE (dra) == POINTER_REF_TYPE && DR_TYPE (drb) == POINTER_REF_TYPE
433 || (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR
434 && TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0))))
436 /* Compare offsets. */
437 tree offset_a = DR_OFFSET (dra);
438 tree offset_b = DR_OFFSET (drb);
440 STRIP_NOPS (offset_a);
441 STRIP_NOPS (offset_b);
443 /* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle
445 if ((offset_a == offset_b)
446 || (TREE_CODE (offset_a) == MULT_EXPR
447 && TREE_CODE (offset_b) == MULT_EXPR
448 && TREE_OPERAND (offset_a, 0) == TREE_OPERAND (offset_b, 0)
449 && TREE_OPERAND (offset_a, 1) == TREE_OPERAND (offset_b, 1)))
456 /* 3. else if (DRA and DRB are represented differently or 2. fails)
457 only try to prove that the bases are surely different. */
459 /* Apply alias analysis. */
460 if (may_alias_p (addr_a, addr_b, dra, drb, &aliased) && !aliased)
466 /* An instruction writing through a restricted pointer is "independent" of any
467 instruction reading or writing through a different pointer, in the same
469 else if ((TYPE_RESTRICT (type_a) && !DR_IS_READ (dra))
470 || (TYPE_RESTRICT (type_b) && !DR_IS_READ (drb)))
479 /* Returns true iff A divides B. */
482 tree_fold_divides_p (tree a,
485 /* Determines whether (A == gcd (A, B)). */
486 return tree_int_cst_equal (a, tree_fold_gcd (a, b));
489 /* Compute the greatest common denominator of two numbers using
490 Euclid's algorithm. */
511 /* Returns true iff A divides B. */
514 int_divides_p (int a, int b)
516 return ((b % a) == 0);
521 /* Dump into FILE all the data references from DATAREFS. */
524 dump_data_references (FILE *file,
525 varray_type datarefs)
529 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
530 dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i));
533 /* Dump into FILE all the dependence relations from DDR. */
536 dump_data_dependence_relations (FILE *file,
541 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++)
542 dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i));
545 /* Dump function for a DATA_REFERENCE structure. */
548 dump_data_reference (FILE *outf,
549 struct data_reference *dr)
553 fprintf (outf, "(Data Ref: \n stmt: ");
554 print_generic_stmt (outf, DR_STMT (dr), 0);
555 fprintf (outf, " ref: ");
556 print_generic_stmt (outf, DR_REF (dr), 0);
557 fprintf (outf, " base_name: ");
558 print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
560 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
562 fprintf (outf, " Access function %d: ", i);
563 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
565 fprintf (outf, ")\n");
568 /* Dump function for a SUBSCRIPT structure. */
571 dump_subscript (FILE *outf, struct subscript *subscript)
573 tree chrec = SUB_CONFLICTS_IN_A (subscript);
575 fprintf (outf, "\n (subscript \n");
576 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
577 print_generic_stmt (outf, chrec, 0);
578 if (chrec == chrec_known)
579 fprintf (outf, " (no dependence)\n");
580 else if (chrec_contains_undetermined (chrec))
581 fprintf (outf, " (don't know)\n");
584 tree last_iteration = SUB_LAST_CONFLICT (subscript);
585 fprintf (outf, " last_conflict: ");
586 print_generic_stmt (outf, last_iteration, 0);
589 chrec = SUB_CONFLICTS_IN_B (subscript);
590 fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
591 print_generic_stmt (outf, chrec, 0);
592 if (chrec == chrec_known)
593 fprintf (outf, " (no dependence)\n");
594 else if (chrec_contains_undetermined (chrec))
595 fprintf (outf, " (don't know)\n");
598 tree last_iteration = SUB_LAST_CONFLICT (subscript);
599 fprintf (outf, " last_conflict: ");
600 print_generic_stmt (outf, last_iteration, 0);
603 fprintf (outf, " (Subscript distance: ");
604 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
605 fprintf (outf, " )\n");
606 fprintf (outf, " )\n");
609 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
612 dump_data_dependence_relation (FILE *outf,
613 struct data_dependence_relation *ddr)
615 struct data_reference *dra, *drb;
619 fprintf (outf, "(Data Dep: \n");
620 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
621 fprintf (outf, " (don't know)\n");
623 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
624 fprintf (outf, " (no dependence)\n");
626 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
629 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
631 fprintf (outf, " access_fn_A: ");
632 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
633 fprintf (outf, " access_fn_B: ");
634 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
635 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
637 if (DDR_DIST_VECT (ddr))
639 fprintf (outf, " distance_vect: ");
640 print_lambda_vector (outf, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
642 if (DDR_DIR_VECT (ddr))
644 fprintf (outf, " direction_vect: ");
645 print_lambda_vector (outf, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
649 fprintf (outf, ")\n");
654 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
657 dump_data_dependence_direction (FILE *file,
658 enum data_dependence_direction dir)
674 case dir_positive_or_negative:
675 fprintf (file, "+-");
678 case dir_positive_or_equal:
679 fprintf (file, "+=");
682 case dir_negative_or_equal:
683 fprintf (file, "-=");
695 /* Dumps the distance and direction vectors in FILE. DDRS contains
696 the dependence relations, and VECT_SIZE is the size of the
697 dependence vectors, or in other words the number of loops in the
701 dump_dist_dir_vectors (FILE *file, varray_type ddrs)
705 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
707 struct data_dependence_relation *ddr =
708 (struct data_dependence_relation *)
709 VARRAY_GENERIC_PTR (ddrs, i);
710 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
711 && DDR_AFFINE_P (ddr))
713 fprintf (file, "DISTANCE_V (");
714 print_lambda_vector (file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
715 fprintf (file, ")\n");
716 fprintf (file, "DIRECTION_V (");
717 print_lambda_vector (file, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
718 fprintf (file, ")\n");
721 fprintf (file, "\n\n");
724 /* Dumps the data dependence relations DDRS in FILE. */
727 dump_ddrs (FILE *file, varray_type ddrs)
731 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
733 struct data_dependence_relation *ddr =
734 (struct data_dependence_relation *)
735 VARRAY_GENERIC_PTR (ddrs, i);
736 dump_data_dependence_relation (file, ddr);
738 fprintf (file, "\n\n");
743 /* Estimate the number of iterations from the size of the data and the
747 estimate_niter_from_size_of_data (struct loop *loop,
752 tree estimation = NULL_TREE;
753 tree array_size, data_size, element_size;
756 init = initial_condition (access_fn);
757 step = evolution_part_in_loop_num (access_fn, loop->num);
759 array_size = TYPE_SIZE (TREE_TYPE (opnd0));
760 element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
761 if (array_size == NULL_TREE
762 || TREE_CODE (array_size) != INTEGER_CST
763 || TREE_CODE (element_size) != INTEGER_CST)
766 data_size = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
767 array_size, element_size);
769 if (init != NULL_TREE
771 && TREE_CODE (init) == INTEGER_CST
772 && TREE_CODE (step) == INTEGER_CST)
774 tree i_plus_s = fold_build2 (PLUS_EXPR, integer_type_node, init, step);
775 tree sign = fold_build2 (GT_EXPR, boolean_type_node, i_plus_s, init);
777 if (sign == boolean_true_node)
778 estimation = fold_build2 (CEIL_DIV_EXPR, integer_type_node,
779 fold_build2 (MINUS_EXPR, integer_type_node,
780 data_size, init), step);
782 /* When the step is negative, as in PR23386: (init = 3, step =
783 0ffffffff, data_size = 100), we have to compute the
784 estimation as ceil_div (init, 0 - step) + 1. */
785 else if (sign == boolean_false_node)
787 fold_build2 (PLUS_EXPR, integer_type_node,
788 fold_build2 (CEIL_DIV_EXPR, integer_type_node,
790 fold_build2 (MINUS_EXPR, unsigned_type_node,
791 integer_zero_node, step)),
795 record_estimate (loop, estimation, boolean_true_node, stmt);
799 /* Given an ARRAY_REF node REF, records its access functions.
800 Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
801 i.e. the constant "3", then recursively call the function on opnd0,
802 i.e. the ARRAY_REF "A[i]". The function returns the base name:
806 analyze_array_indexes (struct loop *loop,
807 VEC(tree,heap) **access_fns,
813 opnd0 = TREE_OPERAND (ref, 0);
814 opnd1 = TREE_OPERAND (ref, 1);
816 /* The detection of the evolution function for this data access is
817 postponed until the dependence test. This lazy strategy avoids
818 the computation of access functions that are of no interest for
820 access_fn = instantiate_parameters
821 (loop, analyze_scalar_evolution (loop, opnd1));
823 if (chrec_contains_undetermined (loop->estimated_nb_iterations))
824 estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
826 VEC_safe_push (tree, heap, *access_fns, access_fn);
828 /* Recursively record other array access functions. */
829 if (TREE_CODE (opnd0) == ARRAY_REF)
830 return analyze_array_indexes (loop, access_fns, opnd0, stmt);
832 /* Return the base name of the data access. */
837 /* For a data reference REF contained in the statement STMT, initialize
838 a DATA_REFERENCE structure, and return it. IS_READ flag has to be
839 set to true when REF is in the right hand side of an
842 struct data_reference *
843 analyze_array (tree stmt, tree ref, bool is_read)
845 struct data_reference *res;
846 VEC(tree,heap) *acc_fns;
848 if (dump_file && (dump_flags & TDF_DETAILS))
850 fprintf (dump_file, "(analyze_array \n");
851 fprintf (dump_file, " (ref = ");
852 print_generic_stmt (dump_file, ref, 0);
853 fprintf (dump_file, ")\n");
856 res = xmalloc (sizeof (struct data_reference));
858 DR_STMT (res) = stmt;
860 acc_fns = VEC_alloc (tree, heap, 3);
861 DR_BASE_OBJECT (res) = analyze_array_indexes
862 (loop_containing_stmt (stmt), &acc_fns, ref, stmt);
863 DR_TYPE (res) = ARRAY_REF_TYPE;
864 DR_SET_ACCESS_FNS (res, acc_fns);
865 DR_IS_READ (res) = is_read;
866 DR_BASE_ADDRESS (res) = NULL_TREE;
867 DR_OFFSET (res) = NULL_TREE;
868 DR_INIT (res) = NULL_TREE;
869 DR_STEP (res) = NULL_TREE;
870 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
871 DR_MEMTAG (res) = NULL_TREE;
872 DR_PTR_INFO (res) = NULL;
874 if (dump_file && (dump_flags & TDF_DETAILS))
875 fprintf (dump_file, ")\n");
881 /* Analyze an indirect memory reference, REF, that comes from STMT.
882 IS_READ is true if this is an indirect load, and false if it is
884 Return a new data reference structure representing the indirect_ref, or
885 NULL if we cannot describe the access function. */
887 static struct data_reference *
888 analyze_indirect_ref (tree stmt, tree ref, bool is_read)
890 struct loop *loop = loop_containing_stmt (stmt);
891 tree ptr_ref = TREE_OPERAND (ref, 0);
892 tree access_fn = analyze_scalar_evolution (loop, ptr_ref);
893 tree init = initial_condition_in_loop_num (access_fn, loop->num);
894 tree base_address = NULL_TREE, evolution, step = NULL_TREE;
895 struct ptr_info_def *ptr_info = NULL;
897 if (TREE_CODE (ptr_ref) == SSA_NAME)
898 ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
901 if (access_fn == chrec_dont_know || !init || init == chrec_dont_know)
903 if (dump_file && (dump_flags & TDF_DETAILS))
905 fprintf (dump_file, "\nBad access function of ptr: ");
906 print_generic_expr (dump_file, ref, TDF_SLIM);
907 fprintf (dump_file, "\n");
912 if (dump_file && (dump_flags & TDF_DETAILS))
914 fprintf (dump_file, "\nAccess function of ptr: ");
915 print_generic_expr (dump_file, access_fn, TDF_SLIM);
916 fprintf (dump_file, "\n");
919 if (!expr_invariant_in_loop_p (loop, init))
921 if (dump_file && (dump_flags & TDF_DETAILS))
922 fprintf (dump_file, "\ninitial condition is not loop invariant.\n");
927 evolution = evolution_part_in_loop_num (access_fn, loop->num);
928 if (evolution != chrec_dont_know)
931 step = ssize_int (0);
934 if (TREE_CODE (evolution) == INTEGER_CST)
935 step = fold_convert (ssizetype, evolution);
937 if (dump_file && (dump_flags & TDF_DETAILS))
938 fprintf (dump_file, "\nnon constant step for ptr access.\n");
942 if (dump_file && (dump_flags & TDF_DETAILS))
943 fprintf (dump_file, "\nunknown evolution of ptr.\n");
945 return init_data_ref (stmt, ref, NULL_TREE, access_fn, is_read, base_address,
946 NULL_TREE, step, NULL_TREE, NULL_TREE,
947 ptr_info, POINTER_REF_TYPE);
950 /* For a data reference REF contained in the statement STMT, initialize
951 a DATA_REFERENCE structure, and return it. */
953 struct data_reference *
954 init_data_ref (tree stmt,
964 struct ptr_info_def *ptr_info,
965 enum data_ref_type type)
967 struct data_reference *res;
968 VEC(tree,heap) *acc_fns;
970 if (dump_file && (dump_flags & TDF_DETAILS))
972 fprintf (dump_file, "(init_data_ref \n");
973 fprintf (dump_file, " (ref = ");
974 print_generic_stmt (dump_file, ref, 0);
975 fprintf (dump_file, ")\n");
978 res = xmalloc (sizeof (struct data_reference));
980 DR_STMT (res) = stmt;
982 DR_BASE_OBJECT (res) = base;
983 DR_TYPE (res) = type;
984 acc_fns = VEC_alloc (tree, heap, 3);
985 DR_SET_ACCESS_FNS (res, acc_fns);
986 VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
987 DR_IS_READ (res) = is_read;
988 DR_BASE_ADDRESS (res) = base_address;
989 DR_OFFSET (res) = init_offset;
990 DR_INIT (res) = NULL_TREE;
991 DR_STEP (res) = step;
992 DR_OFFSET_MISALIGNMENT (res) = misalign;
993 DR_MEMTAG (res) = memtag;
994 DR_PTR_INFO (res) = ptr_info;
996 if (dump_file && (dump_flags & TDF_DETAILS))
997 fprintf (dump_file, ")\n");
1004 /* Function strip_conversions
1006 Strip conversions that don't narrow the mode. */
1009 strip_conversion (tree expr)
1011 tree to, ti, oprnd0;
1013 while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
1015 to = TREE_TYPE (expr);
1016 oprnd0 = TREE_OPERAND (expr, 0);
1017 ti = TREE_TYPE (oprnd0);
1019 if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti))
1021 if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti)))
1030 /* Function analyze_offset_expr
1032 Given an offset expression EXPR received from get_inner_reference, analyze
1033 it and create an expression for INITIAL_OFFSET by substituting the variables
1034 of EXPR with initial_condition of the corresponding access_fn in the loop.
1037 for (j = 3; j < N; j++)
1040 For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be
1041 substituted, since its access_fn in the inner loop is i. 'j' will be
1042 substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
1045 Compute MISALIGN (the misalignment of the data reference initial access from
1046 its base). Misalignment can be calculated only if all the variables can be
1047 substituted with constants, otherwise, we record maximum possible alignment
1048 in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN
1049 will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be
1050 recorded in ALIGNED_TO.
1052 STEP is an evolution of the data reference in this loop in bytes.
1053 In the above example, STEP is C_j.
1055 Return FALSE, if the analysis fails, e.g., there is no access_fn for a
1056 variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO
1057 and STEP) are NULL_TREEs. Otherwise, return TRUE.
1062 analyze_offset_expr (tree expr,
1064 tree *initial_offset,
1071 tree left_offset = ssize_int (0);
1072 tree right_offset = ssize_int (0);
1073 tree left_misalign = ssize_int (0);
1074 tree right_misalign = ssize_int (0);
1075 tree left_step = ssize_int (0);
1076 tree right_step = ssize_int (0);
1077 enum tree_code code;
1078 tree init, evolution;
1079 tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE;
1082 *misalign = NULL_TREE;
1083 *aligned_to = NULL_TREE;
1084 *initial_offset = NULL_TREE;
1086 /* Strip conversions that don't narrow the mode. */
1087 expr = strip_conversion (expr);
1093 if (TREE_CODE (expr) == INTEGER_CST)
1095 *initial_offset = fold_convert (ssizetype, expr);
1096 *misalign = fold_convert (ssizetype, expr);
1097 *step = ssize_int (0);
1101 /* 2. Variable. Try to substitute with initial_condition of the corresponding
1102 access_fn in the current loop. */
1103 if (SSA_VAR_P (expr))
1105 tree access_fn = analyze_scalar_evolution (loop, expr);
1107 if (access_fn == chrec_dont_know)
1111 init = initial_condition_in_loop_num (access_fn, loop->num);
1112 if (init == expr && !expr_invariant_in_loop_p (loop, init))
1113 /* Not enough information: may be not loop invariant.
1114 E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
1115 initial_condition is D, but it depends on i - loop's induction
1119 evolution = evolution_part_in_loop_num (access_fn, loop->num);
1120 if (evolution && TREE_CODE (evolution) != INTEGER_CST)
1121 /* Evolution is not constant. */
1124 if (TREE_CODE (init) == INTEGER_CST)
1125 *misalign = fold_convert (ssizetype, init);
1127 /* Not constant, misalignment cannot be calculated. */
1128 *misalign = NULL_TREE;
1130 *initial_offset = fold_convert (ssizetype, init);
1132 *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
1136 /* Recursive computation. */
1137 if (!BINARY_CLASS_P (expr))
1139 /* We expect to get binary expressions (PLUS/MINUS and MULT). */
1140 if (dump_file && (dump_flags & TDF_DETAILS))
1142 fprintf (dump_file, "\nNot binary expression ");
1143 print_generic_expr (dump_file, expr, TDF_SLIM);
1144 fprintf (dump_file, "\n");
1148 oprnd0 = TREE_OPERAND (expr, 0);
1149 oprnd1 = TREE_OPERAND (expr, 1);
1151 if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign,
1152 &left_aligned_to, &left_step)
1153 || !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign,
1154 &right_aligned_to, &right_step))
1157 /* The type of the operation: plus, minus or mult. */
1158 code = TREE_CODE (expr);
1162 if (TREE_CODE (right_offset) != INTEGER_CST)
1163 /* RIGHT_OFFSET can be not constant. For example, for arrays of variable
1165 FORNOW: We don't support such cases. */
1168 /* Strip conversions that don't narrow the mode. */
1169 left_offset = strip_conversion (left_offset);
1172 /* Misalignment computation. */
1173 if (SSA_VAR_P (left_offset))
1175 /* If the left side contains variables that can't be substituted with
1176 constants, the misalignment is unknown. However, if the right side
1177 is a multiple of some alignment, we know that the expression is
1178 aligned to it. Therefore, we record such maximum possible value.
1180 *misalign = NULL_TREE;
1181 *aligned_to = ssize_int (highest_pow2_factor (right_offset));
1185 /* The left operand was successfully substituted with constant. */
1188 /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is
1190 *misalign = size_binop (code, left_misalign, right_misalign);
1191 if (left_aligned_to && right_aligned_to)
1192 *aligned_to = size_binop (MIN_EXPR, left_aligned_to,
1195 *aligned_to = left_aligned_to ?
1196 left_aligned_to : right_aligned_to;
1199 *misalign = NULL_TREE;
1202 /* Step calculation. */
1203 /* Multiply the step by the right operand. */
1204 *step = size_binop (MULT_EXPR, left_step, right_offset);
1209 /* Combine the recursive calculations for step and misalignment. */
1210 *step = size_binop (code, left_step, right_step);
1212 /* Unknown alignment. */
1213 if ((!left_misalign && !left_aligned_to)
1214 || (!right_misalign && !right_aligned_to))
1216 *misalign = NULL_TREE;
1217 *aligned_to = NULL_TREE;
1221 if (left_misalign && right_misalign)
1222 *misalign = size_binop (code, left_misalign, right_misalign);
1224 *misalign = left_misalign ? left_misalign : right_misalign;
1226 if (left_aligned_to && right_aligned_to)
1227 *aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to);
1229 *aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to;
1237 /* Compute offset. */
1238 *initial_offset = fold_convert (ssizetype,
1239 fold_build2 (code, TREE_TYPE (left_offset),
1245 /* Function address_analysis
1247 Return the BASE of the address expression EXPR.
1248 Also compute the OFFSET from BASE, MISALIGN and STEP.
1251 EXPR - the address expression that is being analyzed
1252 STMT - the statement that contains EXPR or its original memory reference
1253 IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
1254 DR - data_reference struct for the original memory reference
1257 BASE (returned value) - the base of the data reference EXPR.
1258 INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
1259 MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
1260 computation is impossible
1261 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1262 calculated (doesn't depend on variables)
1263 STEP - evolution of EXPR in the loop
1265 If something unexpected is encountered (an unsupported form of data-ref),
1266 then NULL_TREE is returned.
1270 address_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr,
1271 tree *offset, tree *misalign, tree *aligned_to, tree *step)
1273 tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
1274 tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1275 tree dummy, address_aligned_to = NULL_TREE;
1276 struct ptr_info_def *dummy1;
1279 switch (TREE_CODE (expr))
1283 /* EXPR is of form {base +/- offset} (or {offset +/- base}). */
1284 oprnd0 = TREE_OPERAND (expr, 0);
1285 oprnd1 = TREE_OPERAND (expr, 1);
1287 STRIP_NOPS (oprnd0);
1288 STRIP_NOPS (oprnd1);
1290 /* Recursively try to find the base of the address contained in EXPR.
1291 For offset, the returned base will be NULL. */
1292 base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset,
1293 &address_misalign, &address_aligned_to,
1296 base_addr1 = address_analysis (oprnd1, stmt, is_read, dr, &address_offset,
1297 &address_misalign, &address_aligned_to,
1300 /* We support cases where only one of the operands contains an
1302 if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
1304 if (dump_file && (dump_flags & TDF_DETAILS))
1307 "\neither more than one address or no addresses in expr ");
1308 print_generic_expr (dump_file, expr, TDF_SLIM);
1309 fprintf (dump_file, "\n");
1314 /* To revert STRIP_NOPS. */
1315 oprnd0 = TREE_OPERAND (expr, 0);
1316 oprnd1 = TREE_OPERAND (expr, 1);
1318 offset_expr = base_addr0 ?
1319 fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
1321 /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is
1322 a number, we can add it to the misalignment value calculated for base,
1323 otherwise, misalignment is NULL. */
1324 if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
1326 *misalign = size_binop (TREE_CODE (expr), address_misalign,
1328 *aligned_to = address_aligned_to;
1332 *misalign = NULL_TREE;
1333 *aligned_to = NULL_TREE;
1336 /* Combine offset (from EXPR {base + offset}) with the offset calculated
1338 *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
1339 return base_addr0 ? base_addr0 : base_addr1;
1342 base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read,
1343 &dr, offset, misalign, aligned_to, step,
1344 &dummy, &dummy1, &dummy2);
1345 return base_address;
1348 if (!POINTER_TYPE_P (TREE_TYPE (expr)))
1350 if (dump_file && (dump_flags & TDF_DETAILS))
1352 fprintf (dump_file, "\nnot pointer SSA_NAME ");
1353 print_generic_expr (dump_file, expr, TDF_SLIM);
1354 fprintf (dump_file, "\n");
1358 *aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr))));
1359 *misalign = ssize_int (0);
1360 *offset = ssize_int (0);
1361 *step = ssize_int (0);
1370 /* Function object_analysis
1372 Create a data-reference structure DR for MEMREF.
1373 Return the BASE of the data reference MEMREF if the analysis is possible.
1374 Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1375 E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset
1376 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET
1377 instantiated with initial_conditions of access_functions of variables,
1378 and STEP is the evolution of the DR_REF in this loop.
1380 Function get_inner_reference is used for the above in case of ARRAY_REF and
1383 The structure of the function is as follows:
1385 Case 1. For handled_component_p refs
1386 1.1 build data-reference structure for MEMREF
1387 1.2 call get_inner_reference
1388 1.2.1 analyze offset expr received from get_inner_reference
1389 (fall through with BASE)
1390 Case 2. For declarations
1392 Case 3. For INDIRECT_REFs
1393 3.1 build data-reference structure for MEMREF
1394 3.2 analyze evolution and initial condition of MEMREF
1395 3.3 set data-reference structure for MEMREF
1396 3.4 call address_analysis to analyze INIT of the access function
1397 3.5 extract memory tag
1400 Combine the results of object and address analysis to calculate
1401 INITIAL_OFFSET, STEP and misalignment info.
1404 MEMREF - the memory reference that is being analyzed
1405 STMT - the statement that contains MEMREF
1406 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1409 BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
1410 E.g, if MEMREF is a.b[k].c[i][j] the returned
1412 DR - data_reference struct for MEMREF
1413 INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
1414 MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of
1415 ALIGNMENT or NULL_TREE if the computation is impossible
1416 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1417 calculated (doesn't depend on variables)
1418 STEP - evolution of the DR_REF in the loop
1419 MEMTAG - memory tag for aliasing purposes
1420 PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
1421 SUBVARS - Sub-variables of the variable
1423 If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned,
1424 but DR can be created anyway.
1429 object_analysis (tree memref, tree stmt, bool is_read,
1430 struct data_reference **dr, tree *offset, tree *misalign,
1431 tree *aligned_to, tree *step, tree *memtag,
1432 struct ptr_info_def **ptr_info, subvar_t *subvars)
1434 tree base = NULL_TREE, base_address = NULL_TREE;
1435 tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
1436 tree object_step = ssize_int (0), address_step = ssize_int (0);
1437 tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1438 HOST_WIDE_INT pbitsize, pbitpos;
1439 tree poffset, bit_pos_in_bytes;
1440 enum machine_mode pmode;
1441 int punsignedp, pvolatilep;
1442 tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
1443 struct loop *loop = loop_containing_stmt (stmt);
1444 struct data_reference *ptr_dr = NULL;
1445 tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE;
1450 /* Case 1. handled_component_p refs. */
1451 if (handled_component_p (memref))
1453 /* 1.1 build data-reference structure for MEMREF. */
1454 /* TODO: handle COMPONENT_REFs. */
1457 if (TREE_CODE (memref) == ARRAY_REF)
1458 *dr = analyze_array (stmt, memref, is_read);
1462 if (dump_file && (dump_flags & TDF_DETAILS))
1464 fprintf (dump_file, "\ndata-ref of unsupported type ");
1465 print_generic_expr (dump_file, memref, TDF_SLIM);
1466 fprintf (dump_file, "\n");
1472 /* 1.2 call get_inner_reference. */
1473 /* Find the base and the offset from it. */
1474 base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
1475 &pmode, &punsignedp, &pvolatilep, false);
1478 if (dump_file && (dump_flags & TDF_DETAILS))
1480 fprintf (dump_file, "\nfailed to get inner ref for ");
1481 print_generic_expr (dump_file, memref, TDF_SLIM);
1482 fprintf (dump_file, "\n");
1487 /* 1.2.1 analyze offset expr received from get_inner_reference. */
1489 && !analyze_offset_expr (poffset, loop, &object_offset,
1490 &object_misalign, &object_aligned_to,
1493 if (dump_file && (dump_flags & TDF_DETAILS))
1495 fprintf (dump_file, "\nfailed to compute offset or step for ");
1496 print_generic_expr (dump_file, memref, TDF_SLIM);
1497 fprintf (dump_file, "\n");
1502 /* Add bit position to OFFSET and MISALIGN. */
1504 bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
1505 /* Check that there is no remainder in bits. */
1506 if (pbitpos%BITS_PER_UNIT)
1508 if (dump_file && (dump_flags & TDF_DETAILS))
1509 fprintf (dump_file, "\nbit offset alignment.\n");
1512 object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);
1513 if (object_misalign)
1514 object_misalign = size_binop (PLUS_EXPR, object_misalign,
1517 memref = base; /* To continue analysis of BASE. */
1521 /* Part 1: Case 2. Declarations. */
1522 if (DECL_P (memref))
1524 /* We expect to get a decl only if we already have a DR. */
1527 if (dump_file && (dump_flags & TDF_DETAILS))
1529 fprintf (dump_file, "\nunhandled decl ");
1530 print_generic_expr (dump_file, memref, TDF_SLIM);
1531 fprintf (dump_file, "\n");
1536 /* TODO: if during the analysis of INDIRECT_REF we get to an object, put
1537 the object in BASE_OBJECT field if we can prove that this is O.K.,
1538 i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT.
1539 (e.g., if the object is an array base 'a', where 'a[N]', we must prove
1540 that every access with 'p' (the original INDIRECT_REF based on '&a')
1541 in the loop is within the array boundaries - from a[0] to a[N-1]).
1542 Otherwise, our alias analysis can be incorrect.
1543 Even if an access function based on BASE_OBJECT can't be build, update
1544 BASE_OBJECT field to enable us to prove that two data-refs are
1545 different (without access function, distance analysis is impossible).
1547 if (SSA_VAR_P (memref) && var_can_have_subvars (memref))
1548 *subvars = get_subvars_for_var (memref);
1549 base_address = build_fold_addr_expr (memref);
1550 /* 2.1 set MEMTAG. */
1554 /* Part 1: Case 3. INDIRECT_REFs. */
1555 else if (TREE_CODE (memref) == INDIRECT_REF)
1557 tree ptr_ref = TREE_OPERAND (memref, 0);
1558 if (TREE_CODE (ptr_ref) == SSA_NAME)
1559 *ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
1561 /* 3.1 build data-reference structure for MEMREF. */
1562 ptr_dr = analyze_indirect_ref (stmt, memref, is_read);
1565 if (dump_file && (dump_flags & TDF_DETAILS))
1567 fprintf (dump_file, "\nfailed to create dr for ");
1568 print_generic_expr (dump_file, memref, TDF_SLIM);
1569 fprintf (dump_file, "\n");
1574 /* 3.2 analyze evolution and initial condition of MEMREF. */
1575 ptr_step = DR_STEP (ptr_dr);
1576 ptr_init = DR_BASE_ADDRESS (ptr_dr);
1577 if (!ptr_init || !ptr_step || !POINTER_TYPE_P (TREE_TYPE (ptr_init)))
1579 *dr = (*dr) ? *dr : ptr_dr;
1580 if (dump_file && (dump_flags & TDF_DETAILS))
1582 fprintf (dump_file, "\nbad pointer access ");
1583 print_generic_expr (dump_file, memref, TDF_SLIM);
1584 fprintf (dump_file, "\n");
1589 if (integer_zerop (ptr_step) && !(*dr))
1591 if (dump_file && (dump_flags & TDF_DETAILS))
1592 fprintf (dump_file, "\nptr is loop invariant.\n");
1596 /* If there exists DR for MEMREF, we are analyzing the base of
1597 handled component (PTR_INIT), which not necessary has evolution in
1600 object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
1602 /* 3.3 set data-reference structure for MEMREF. */
1606 /* 3.4 call address_analysis to analyze INIT of the access
1608 base_address = address_analysis (ptr_init, stmt, is_read, *dr,
1609 &address_offset, &address_misalign,
1610 &address_aligned_to, &address_step);
1613 if (dump_file && (dump_flags & TDF_DETAILS))
1615 fprintf (dump_file, "\nfailed to analyze address ");
1616 print_generic_expr (dump_file, ptr_init, TDF_SLIM);
1617 fprintf (dump_file, "\n");
1622 /* 3.5 extract memory tag. */
1623 switch (TREE_CODE (base_address))
1626 *memtag = get_var_ann (SSA_NAME_VAR (base_address))->type_mem_tag;
1627 if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
1628 *memtag = get_var_ann (
1629 SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->type_mem_tag;
1632 *memtag = TREE_OPERAND (base_address, 0);
1635 if (dump_file && (dump_flags & TDF_DETAILS))
1637 fprintf (dump_file, "\nno memtag for ");
1638 print_generic_expr (dump_file, memref, TDF_SLIM);
1639 fprintf (dump_file, "\n");
1641 *memtag = NULL_TREE;
1648 /* MEMREF cannot be analyzed. */
1649 if (dump_file && (dump_flags & TDF_DETAILS))
1651 fprintf (dump_file, "\ndata-ref of unsupported type ");
1652 print_generic_expr (dump_file, memref, TDF_SLIM);
1653 fprintf (dump_file, "\n");
1658 if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag))
1659 *subvars = get_subvars_for_var (*memtag);
1661 /* Part 2: Combine the results of object and address analysis to calculate
1662 INITIAL_OFFSET, STEP and misalignment info. */
1663 *offset = size_binop (PLUS_EXPR, object_offset, address_offset);
1665 if ((!object_misalign && !object_aligned_to)
1666 || (!address_misalign && !address_aligned_to))
1668 *misalign = NULL_TREE;
1669 *aligned_to = NULL_TREE;
1673 if (object_misalign && address_misalign)
1674 *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
1676 *misalign = object_misalign ? object_misalign : address_misalign;
1677 if (object_aligned_to && address_aligned_to)
1678 *aligned_to = size_binop (MIN_EXPR, object_aligned_to,
1679 address_aligned_to);
1681 *aligned_to = object_aligned_to ?
1682 object_aligned_to : address_aligned_to;
1684 *step = size_binop (PLUS_EXPR, object_step, address_step);
1686 return base_address;
1689 /* Function analyze_offset.
1691 Extract INVARIANT and CONSTANT parts from OFFSET.
1695 analyze_offset (tree offset, tree *invariant, tree *constant)
1697 tree op0, op1, constant_0, constant_1, invariant_0, invariant_1;
1698 enum tree_code code = TREE_CODE (offset);
1700 *invariant = NULL_TREE;
1701 *constant = NULL_TREE;
1703 /* Not PLUS/MINUS expression - recursion stop condition. */
1704 if (code != PLUS_EXPR && code != MINUS_EXPR)
1706 if (TREE_CODE (offset) == INTEGER_CST)
1709 *invariant = offset;
1713 op0 = TREE_OPERAND (offset, 0);
1714 op1 = TREE_OPERAND (offset, 1);
1716 /* Recursive call with the operands. */
1717 analyze_offset (op0, &invariant_0, &constant_0);
1718 analyze_offset (op1, &invariant_1, &constant_1);
1720 /* Combine the results. */
1721 *constant = constant_0 ? constant_0 : constant_1;
1722 if (invariant_0 && invariant_1)
1724 fold_build2 (code, TREE_TYPE (invariant_0), invariant_0, invariant_1);
1726 *invariant = invariant_0 ? invariant_0 : invariant_1;
1730 /* Function create_data_ref.
1732 Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS,
1733 DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO,
1734 DR_MEMTAG, and DR_POINTSTO_INFO fields.
1737 MEMREF - the memory reference that is being analyzed
1738 STMT - the statement that contains MEMREF
1739 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1742 DR (returned value) - data_reference struct for MEMREF
1745 static struct data_reference *
1746 create_data_ref (tree memref, tree stmt, bool is_read)
1748 struct data_reference *dr = NULL;
1749 tree base_address, offset, step, misalign, memtag;
1750 struct loop *loop = loop_containing_stmt (stmt);
1751 tree invariant = NULL_TREE, constant = NULL_TREE;
1752 tree type_size, init_cond;
1753 struct ptr_info_def *ptr_info;
1754 subvar_t subvars = NULL;
1760 base_address = object_analysis (memref, stmt, is_read, &dr, &offset,
1761 &misalign, &aligned_to, &step, &memtag,
1762 &ptr_info, &subvars);
1763 if (!dr || !base_address)
1765 if (dump_file && (dump_flags & TDF_DETAILS))
1767 fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for ");
1768 print_generic_expr (dump_file, memref, TDF_SLIM);
1769 fprintf (dump_file, "\n");
1774 DR_BASE_ADDRESS (dr) = base_address;
1775 DR_OFFSET (dr) = offset;
1776 DR_INIT (dr) = ssize_int (0);
1777 DR_STEP (dr) = step;
1778 DR_OFFSET_MISALIGNMENT (dr) = misalign;
1779 DR_ALIGNED_TO (dr) = aligned_to;
1780 DR_MEMTAG (dr) = memtag;
1781 DR_PTR_INFO (dr) = ptr_info;
1782 DR_SUBVARS (dr) = subvars;
1784 type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
1786 /* Change the access function for INIDIRECT_REFs, according to
1787 DR_BASE_ADDRESS. Analyze OFFSET calculated in object_analysis. OFFSET is
1788 an expression that can contain loop invariant expressions and constants.
1789 We put the constant part in the initial condition of the access function
1790 (for data dependence tests), and in DR_INIT of the data-ref. The loop
1791 invariant part is put in DR_OFFSET.
1792 The evolution part of the access function is STEP calculated in
1793 object_analysis divided by the size of data type.
1795 if (!DR_BASE_OBJECT (dr))
1800 /* Extract CONSTANT and INVARIANT from OFFSET, and put them in DR_INIT and
1801 DR_OFFSET fields of DR. */
1802 analyze_offset (offset, &invariant, &constant);
1805 DR_INIT (dr) = fold_convert (ssizetype, constant);
1806 init_cond = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (constant),
1807 constant, type_size);
1810 DR_INIT (dr) = init_cond = ssize_int (0);;
1813 DR_OFFSET (dr) = invariant;
1815 DR_OFFSET (dr) = ssize_int (0);
1817 /* Update access function. */
1818 access_fn = DR_ACCESS_FN (dr, 0);
1819 new_step = size_binop (TRUNC_DIV_EXPR,
1820 fold_convert (ssizetype, step), type_size);
1822 access_fn = chrec_replace_initial_condition (access_fn, init_cond);
1823 access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step);
1825 VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn);
1828 if (dump_file && (dump_flags & TDF_DETAILS))
1830 struct ptr_info_def *pi = DR_PTR_INFO (dr);
1832 fprintf (dump_file, "\nCreated dr for ");
1833 print_generic_expr (dump_file, memref, TDF_SLIM);
1834 fprintf (dump_file, "\n\tbase_address: ");
1835 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
1836 fprintf (dump_file, "\n\toffset from base address: ");
1837 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
1838 fprintf (dump_file, "\n\tconstant offset from base address: ");
1839 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
1840 fprintf (dump_file, "\n\tbase_object: ");
1841 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
1842 fprintf (dump_file, "\n\tstep: ");
1843 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
1844 fprintf (dump_file, "B\n\tmisalignment from base: ");
1845 print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM);
1846 if (DR_OFFSET_MISALIGNMENT (dr))
1847 fprintf (dump_file, "B");
1848 if (DR_ALIGNED_TO (dr))
1850 fprintf (dump_file, "\n\taligned to: ");
1851 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
1853 fprintf (dump_file, "\n\tmemtag: ");
1854 print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM);
1855 fprintf (dump_file, "\n");
1856 if (pi && pi->name_mem_tag)
1858 fprintf (dump_file, "\n\tnametag: ");
1859 print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM);
1860 fprintf (dump_file, "\n");
1867 /* Returns true when all the functions of a tree_vec CHREC are the
1871 all_chrecs_equal_p (tree chrec)
1875 for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
1877 tree chrec_j = TREE_VEC_ELT (chrec, j);
1878 tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1);
1881 (integer_type_node, chrec_j, chrec_j_1)))
1887 /* Determine for each subscript in the data dependence relation DDR
1891 compute_subscript_distance (struct data_dependence_relation *ddr)
1893 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1897 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1899 tree conflicts_a, conflicts_b, difference;
1900 struct subscript *subscript;
1902 subscript = DDR_SUBSCRIPT (ddr, i);
1903 conflicts_a = SUB_CONFLICTS_IN_A (subscript);
1904 conflicts_b = SUB_CONFLICTS_IN_B (subscript);
1906 if (TREE_CODE (conflicts_a) == TREE_VEC)
1908 if (!all_chrecs_equal_p (conflicts_a))
1910 SUB_DISTANCE (subscript) = chrec_dont_know;
1914 conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
1917 if (TREE_CODE (conflicts_b) == TREE_VEC)
1919 if (!all_chrecs_equal_p (conflicts_b))
1921 SUB_DISTANCE (subscript) = chrec_dont_know;
1925 conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
1928 difference = chrec_fold_minus
1929 (integer_type_node, conflicts_b, conflicts_a);
1931 if (evolution_function_is_constant_p (difference))
1932 SUB_DISTANCE (subscript) = difference;
1935 SUB_DISTANCE (subscript) = chrec_dont_know;
1940 /* Initialize a ddr. */
1942 struct data_dependence_relation *
1943 initialize_data_dependence_relation (struct data_reference *a,
1944 struct data_reference *b)
1946 struct data_dependence_relation *res;
1950 res = xmalloc (sizeof (struct data_dependence_relation));
1954 if (a == NULL || b == NULL)
1956 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1960 /* When A and B are arrays and their dimensions differ, we directly
1961 initialize the relation to "there is no dependence": chrec_known. */
1962 if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
1963 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
1965 DDR_ARE_DEPENDENT (res) = chrec_known;
1969 /* Compare the bases of the data-refs. */
1970 if (!base_addr_differ_p (a, b, &differ_p))
1972 /* Can't determine whether the data-refs access the same memory
1974 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1979 DDR_ARE_DEPENDENT (res) = chrec_known;
1983 DDR_AFFINE_P (res) = true;
1984 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1985 DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
1986 DDR_SIZE_VECT (res) = 0;
1987 DDR_DIST_VECT (res) = NULL;
1988 DDR_DIR_VECT (res) = NULL;
1990 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1992 struct subscript *subscript;
1994 subscript = xmalloc (sizeof (struct subscript));
1995 SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
1996 SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
1997 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1998 SUB_DISTANCE (subscript) = chrec_dont_know;
1999 VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
2005 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
2009 finalize_ddr_dependent (struct data_dependence_relation *ddr,
2012 if (dump_file && (dump_flags & TDF_DETAILS))
2014 fprintf (dump_file, "(dependence classified: ");
2015 print_generic_expr (dump_file, chrec, 0);
2016 fprintf (dump_file, ")\n");
2019 DDR_ARE_DEPENDENT (ddr) = chrec;
2020 varray_clear (DDR_SUBSCRIPTS (ddr));
2023 /* The dependence relation DDR cannot be represented by a distance
2027 non_affine_dependence_relation (struct data_dependence_relation *ddr)
2029 if (dump_file && (dump_flags & TDF_DETAILS))
2030 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
2032 DDR_AFFINE_P (ddr) = false;
2037 /* This section contains the classic Banerjee tests. */
2039 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
2040 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
2043 ziv_subscript_p (tree chrec_a,
2046 return (evolution_function_is_constant_p (chrec_a)
2047 && evolution_function_is_constant_p (chrec_b));
2050 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
2051 variable, i.e., if the SIV (Single Index Variable) test is true. */
2054 siv_subscript_p (tree chrec_a,
2057 if ((evolution_function_is_constant_p (chrec_a)
2058 && evolution_function_is_univariate_p (chrec_b))
2059 || (evolution_function_is_constant_p (chrec_b)
2060 && evolution_function_is_univariate_p (chrec_a)))
2063 if (evolution_function_is_univariate_p (chrec_a)
2064 && evolution_function_is_univariate_p (chrec_b))
2066 switch (TREE_CODE (chrec_a))
2068 case POLYNOMIAL_CHREC:
2069 switch (TREE_CODE (chrec_b))
2071 case POLYNOMIAL_CHREC:
2072 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
2087 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
2088 *OVERLAPS_B are initialized to the functions that describe the
2089 relation between the elements accessed twice by CHREC_A and
2090 CHREC_B. For k >= 0, the following property is verified:
2092 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2095 analyze_ziv_subscript (tree chrec_a,
2099 tree *last_conflicts)
2103 if (dump_file && (dump_flags & TDF_DETAILS))
2104 fprintf (dump_file, "(analyze_ziv_subscript \n");
2106 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2108 switch (TREE_CODE (difference))
2111 if (integer_zerop (difference))
2113 /* The difference is equal to zero: the accessed index
2114 overlaps for each iteration in the loop. */
2115 *overlaps_a = integer_zero_node;
2116 *overlaps_b = integer_zero_node;
2117 *last_conflicts = chrec_dont_know;
2121 /* The accesses do not overlap. */
2122 *overlaps_a = chrec_known;
2123 *overlaps_b = chrec_known;
2124 *last_conflicts = integer_zero_node;
2129 /* We're not sure whether the indexes overlap. For the moment,
2130 conservatively answer "don't know". */
2131 *overlaps_a = chrec_dont_know;
2132 *overlaps_b = chrec_dont_know;
2133 *last_conflicts = chrec_dont_know;
2137 if (dump_file && (dump_flags & TDF_DETAILS))
2138 fprintf (dump_file, ")\n");
2141 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2142 constant, and CHREC_B is an affine function. *OVERLAPS_A and
2143 *OVERLAPS_B are initialized to the functions that describe the
2144 relation between the elements accessed twice by CHREC_A and
2145 CHREC_B. For k >= 0, the following property is verified:
2147 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2150 analyze_siv_subscript_cst_affine (tree chrec_a,
2154 tree *last_conflicts)
2156 bool value0, value1, value2;
2157 tree difference = chrec_fold_minus
2158 (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
2160 if (!chrec_is_positive (initial_condition (difference), &value0))
2162 *overlaps_a = chrec_dont_know;
2163 *overlaps_b = chrec_dont_know;
2164 *last_conflicts = chrec_dont_know;
2169 if (value0 == false)
2171 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
2173 *overlaps_a = chrec_dont_know;
2174 *overlaps_b = chrec_dont_know;
2175 *last_conflicts = chrec_dont_know;
2184 chrec_b = {10, +, 1}
2187 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2189 *overlaps_a = integer_zero_node;
2190 *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
2191 fold_build1 (ABS_EXPR,
2194 CHREC_RIGHT (chrec_b));
2195 *last_conflicts = integer_one_node;
2199 /* When the step does not divide the difference, there are
2203 *overlaps_a = chrec_known;
2204 *overlaps_b = chrec_known;
2205 *last_conflicts = integer_zero_node;
2214 chrec_b = {10, +, -1}
2216 In this case, chrec_a will not overlap with chrec_b. */
2217 *overlaps_a = chrec_known;
2218 *overlaps_b = chrec_known;
2219 *last_conflicts = integer_zero_node;
2226 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
2228 *overlaps_a = chrec_dont_know;
2229 *overlaps_b = chrec_dont_know;
2230 *last_conflicts = chrec_dont_know;
2235 if (value2 == false)
2239 chrec_b = {10, +, -1}
2241 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2243 *overlaps_a = integer_zero_node;
2244 *overlaps_b = fold_build2 (EXACT_DIV_EXPR,
2245 integer_type_node, difference,
2246 CHREC_RIGHT (chrec_b));
2247 *last_conflicts = integer_one_node;
2251 /* When the step does not divides the difference, there
2255 *overlaps_a = chrec_known;
2256 *overlaps_b = chrec_known;
2257 *last_conflicts = integer_zero_node;
2267 In this case, chrec_a will not overlap with chrec_b. */
2268 *overlaps_a = chrec_known;
2269 *overlaps_b = chrec_known;
2270 *last_conflicts = integer_zero_node;
2278 /* Helper recursive function for initializing the matrix A. Returns
2279 the initial value of CHREC. */
2282 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2286 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2287 return int_cst_value (chrec);
2289 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2290 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2293 #define FLOOR_DIV(x,y) ((x) / (y))
2295 /* Solves the special case of the Diophantine equation:
2296 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2298 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2299 number of iterations that loops X and Y run. The overlaps will be
2300 constructed as evolutions in dimension DIM. */
2303 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
2304 tree *overlaps_a, tree *overlaps_b,
2305 tree *last_conflicts, int dim)
2307 if (((step_a > 0 && step_b > 0)
2308 || (step_a < 0 && step_b < 0)))
2310 int step_overlaps_a, step_overlaps_b;
2311 int gcd_steps_a_b, last_conflict, tau2;
2313 gcd_steps_a_b = gcd (step_a, step_b);
2314 step_overlaps_a = step_b / gcd_steps_a_b;
2315 step_overlaps_b = step_a / gcd_steps_a_b;
2317 tau2 = FLOOR_DIV (niter, step_overlaps_a);
2318 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2319 last_conflict = tau2;
2321 *overlaps_a = build_polynomial_chrec
2322 (dim, integer_zero_node,
2323 build_int_cst (NULL_TREE, step_overlaps_a));
2324 *overlaps_b = build_polynomial_chrec
2325 (dim, integer_zero_node,
2326 build_int_cst (NULL_TREE, step_overlaps_b));
2327 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2332 *overlaps_a = integer_zero_node;
2333 *overlaps_b = integer_zero_node;
2334 *last_conflicts = integer_zero_node;
2339 /* Solves the special case of a Diophantine equation where CHREC_A is
2340 an affine bivariate function, and CHREC_B is an affine univariate
2341 function. For example,
2343 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2345 has the following overlapping functions:
2347 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2348 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2349 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2351 FORNOW: This is a specialized implementation for a case occurring in
2352 a common benchmark. Implement the general algorithm. */
2355 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2356 tree *overlaps_a, tree *overlaps_b,
2357 tree *last_conflicts)
2359 bool xz_p, yz_p, xyz_p;
2360 int step_x, step_y, step_z;
2361 int niter_x, niter_y, niter_z, niter;
2362 tree numiter_x, numiter_y, numiter_z;
2363 tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
2364 tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
2365 tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
2367 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2368 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2369 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2371 numiter_x = number_of_iterations_in_loop
2372 (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]);
2373 numiter_y = number_of_iterations_in_loop
2374 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2375 numiter_z = number_of_iterations_in_loop
2376 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2378 if (TREE_CODE (numiter_x) != INTEGER_CST)
2379 numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]
2380 ->estimated_nb_iterations;
2381 if (TREE_CODE (numiter_y) != INTEGER_CST)
2382 numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2383 ->estimated_nb_iterations;
2384 if (TREE_CODE (numiter_z) != INTEGER_CST)
2385 numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2386 ->estimated_nb_iterations;
2388 if (chrec_contains_undetermined (numiter_x)
2389 || chrec_contains_undetermined (numiter_y)
2390 || chrec_contains_undetermined (numiter_z)
2391 || TREE_CODE (numiter_x) != INTEGER_CST
2392 || TREE_CODE (numiter_y) != INTEGER_CST
2393 || TREE_CODE (numiter_z) != INTEGER_CST)
2395 *overlaps_a = chrec_dont_know;
2396 *overlaps_b = chrec_dont_know;
2397 *last_conflicts = chrec_dont_know;
2401 niter_x = int_cst_value (numiter_x);
2402 niter_y = int_cst_value (numiter_y);
2403 niter_z = int_cst_value (numiter_z);
2405 niter = MIN (niter_x, niter_z);
2406 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2409 &last_conflicts_xz, 1);
2410 niter = MIN (niter_y, niter_z);
2411 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2414 &last_conflicts_yz, 2);
2415 niter = MIN (niter_x, niter_z);
2416 niter = MIN (niter_y, niter);
2417 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2420 &last_conflicts_xyz, 3);
2422 xz_p = !integer_zerop (last_conflicts_xz);
2423 yz_p = !integer_zerop (last_conflicts_yz);
2424 xyz_p = !integer_zerop (last_conflicts_xyz);
2426 if (xz_p || yz_p || xyz_p)
2428 *overlaps_a = make_tree_vec (2);
2429 TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
2430 TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
2431 *overlaps_b = integer_zero_node;
2434 TREE_VEC_ELT (*overlaps_a, 0) =
2435 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
2438 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
2439 *last_conflicts = last_conflicts_xz;
2443 TREE_VEC_ELT (*overlaps_a, 1) =
2444 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
2447 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
2448 *last_conflicts = last_conflicts_yz;
2452 TREE_VEC_ELT (*overlaps_a, 0) =
2453 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
2455 TREE_VEC_ELT (*overlaps_a, 1) =
2456 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
2459 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
2460 *last_conflicts = last_conflicts_xyz;
2465 *overlaps_a = integer_zero_node;
2466 *overlaps_b = integer_zero_node;
2467 *last_conflicts = integer_zero_node;
2471 /* Determines the overlapping elements due to accesses CHREC_A and
2472 CHREC_B, that are affine functions. This is a part of the
2473 subscript analyzer. */
2476 analyze_subscript_affine_affine (tree chrec_a,
2480 tree *last_conflicts)
2482 unsigned nb_vars_a, nb_vars_b, dim;
2483 int init_a, init_b, gamma, gcd_alpha_beta;
2485 lambda_matrix A, U, S;
2487 if (dump_file && (dump_flags & TDF_DETAILS))
2488 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2490 /* For determining the initial intersection, we have to solve a
2491 Diophantine equation. This is the most time consuming part.
2493 For answering to the question: "Is there a dependence?" we have
2494 to prove that there exists a solution to the Diophantine
2495 equation, and that the solution is in the iteration domain,
2496 i.e. the solution is positive or zero, and that the solution
2497 happens before the upper bound loop.nb_iterations. Otherwise
2498 there is no dependence. This function outputs a description of
2499 the iterations that hold the intersections. */
2502 nb_vars_a = nb_vars_in_chrec (chrec_a);
2503 nb_vars_b = nb_vars_in_chrec (chrec_b);
2505 dim = nb_vars_a + nb_vars_b;
2506 U = lambda_matrix_new (dim, dim);
2507 A = lambda_matrix_new (dim, 1);
2508 S = lambda_matrix_new (dim, 1);
2510 init_a = initialize_matrix_A (A, chrec_a, 0, 1);
2511 init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
2512 gamma = init_b - init_a;
2514 /* Don't do all the hard work of solving the Diophantine equation
2515 when we already know the solution: for example,
2518 | gamma = 3 - 3 = 0.
2519 Then the first overlap occurs during the first iterations:
2520 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2524 if (nb_vars_a == 1 && nb_vars_b == 1)
2527 int niter, niter_a, niter_b;
2528 tree numiter_a, numiter_b;
2530 numiter_a = number_of_iterations_in_loop
2531 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2532 numiter_b = number_of_iterations_in_loop
2533 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2535 if (TREE_CODE (numiter_a) != INTEGER_CST)
2536 numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2537 ->estimated_nb_iterations;
2538 if (TREE_CODE (numiter_b) != INTEGER_CST)
2539 numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2540 ->estimated_nb_iterations;
2541 if (chrec_contains_undetermined (numiter_a)
2542 || chrec_contains_undetermined (numiter_b)
2543 || TREE_CODE (numiter_a) != INTEGER_CST
2544 || TREE_CODE (numiter_b) != INTEGER_CST)
2546 *overlaps_a = chrec_dont_know;
2547 *overlaps_b = chrec_dont_know;
2548 *last_conflicts = chrec_dont_know;
2552 niter_a = int_cst_value (numiter_a);
2553 niter_b = int_cst_value (numiter_b);
2554 niter = MIN (niter_a, niter_b);
2556 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2557 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2559 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2560 overlaps_a, overlaps_b,
2564 else if (nb_vars_a == 2 && nb_vars_b == 1)
2565 compute_overlap_steps_for_affine_1_2
2566 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2568 else if (nb_vars_a == 1 && nb_vars_b == 2)
2569 compute_overlap_steps_for_affine_1_2
2570 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2574 *overlaps_a = chrec_dont_know;
2575 *overlaps_b = chrec_dont_know;
2576 *last_conflicts = chrec_dont_know;
2582 lambda_matrix_right_hermite (A, dim, 1, S, U);
2587 lambda_matrix_row_negate (U, dim, 0);
2589 gcd_alpha_beta = S[0][0];
2591 /* The classic "gcd-test". */
2592 if (!int_divides_p (gcd_alpha_beta, gamma))
2594 /* The "gcd-test" has determined that there is no integer
2595 solution, i.e. there is no dependence. */
2596 *overlaps_a = chrec_known;
2597 *overlaps_b = chrec_known;
2598 *last_conflicts = integer_zero_node;
2601 /* Both access functions are univariate. This includes SIV and MIV cases. */
2602 else if (nb_vars_a == 1 && nb_vars_b == 1)
2604 /* Both functions should have the same evolution sign. */
2605 if (((A[0][0] > 0 && -A[1][0] > 0)
2606 || (A[0][0] < 0 && -A[1][0] < 0)))
2608 /* The solutions are given by:
2610 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2613 For a given integer t. Using the following variables,
2615 | i0 = u11 * gamma / gcd_alpha_beta
2616 | j0 = u12 * gamma / gcd_alpha_beta
2623 | y0 = j0 + j1 * t. */
2627 /* X0 and Y0 are the first iterations for which there is a
2628 dependence. X0, Y0 are two solutions of the Diophantine
2629 equation: chrec_a (X0) = chrec_b (Y0). */
2631 int niter, niter_a, niter_b;
2632 tree numiter_a, numiter_b;
2634 numiter_a = number_of_iterations_in_loop
2635 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2636 numiter_b = number_of_iterations_in_loop
2637 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2639 if (TREE_CODE (numiter_a) != INTEGER_CST)
2640 numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2641 ->estimated_nb_iterations;
2642 if (TREE_CODE (numiter_b) != INTEGER_CST)
2643 numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2644 ->estimated_nb_iterations;
2645 if (chrec_contains_undetermined (numiter_a)
2646 || chrec_contains_undetermined (numiter_b)
2647 || TREE_CODE (numiter_a) != INTEGER_CST
2648 || TREE_CODE (numiter_b) != INTEGER_CST)
2650 *overlaps_a = chrec_dont_know;
2651 *overlaps_b = chrec_dont_know;
2652 *last_conflicts = chrec_dont_know;
2656 niter_a = int_cst_value (numiter_a);
2657 niter_b = int_cst_value (numiter_b);
2658 niter = MIN (niter_a, niter_b);
2660 i0 = U[0][0] * gamma / gcd_alpha_beta;
2661 j0 = U[0][1] * gamma / gcd_alpha_beta;
2665 if ((i1 == 0 && i0 < 0)
2666 || (j1 == 0 && j0 < 0))
2668 /* There is no solution.
2669 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2670 falls in here, but for the moment we don't look at the
2671 upper bound of the iteration domain. */
2672 *overlaps_a = chrec_known;
2673 *overlaps_b = chrec_known;
2674 *last_conflicts = integer_zero_node;
2681 tau1 = CEIL (-i0, i1);
2682 tau2 = FLOOR_DIV (niter - i0, i1);
2686 int last_conflict, min_multiple;
2687 tau1 = MAX (tau1, CEIL (-j0, j1));
2688 tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
2690 x0 = i1 * tau1 + i0;
2691 y0 = j1 * tau1 + j0;
2693 /* At this point (x0, y0) is one of the
2694 solutions to the Diophantine equation. The
2695 next step has to compute the smallest
2696 positive solution: the first conflicts. */
2697 min_multiple = MIN (x0 / i1, y0 / j1);
2698 x0 -= i1 * min_multiple;
2699 y0 -= j1 * min_multiple;
2701 tau1 = (x0 - i0)/i1;
2702 last_conflict = tau2 - tau1;
2704 *overlaps_a = build_polynomial_chrec
2706 build_int_cst (NULL_TREE, x0),
2707 build_int_cst (NULL_TREE, i1));
2708 *overlaps_b = build_polynomial_chrec
2710 build_int_cst (NULL_TREE, y0),
2711 build_int_cst (NULL_TREE, j1));
2712 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2716 /* FIXME: For the moment, the upper bound of the
2717 iteration domain for j is not checked. */
2718 *overlaps_a = chrec_dont_know;
2719 *overlaps_b = chrec_dont_know;
2720 *last_conflicts = chrec_dont_know;
2726 /* FIXME: For the moment, the upper bound of the
2727 iteration domain for i is not checked. */
2728 *overlaps_a = chrec_dont_know;
2729 *overlaps_b = chrec_dont_know;
2730 *last_conflicts = chrec_dont_know;
2736 *overlaps_a = chrec_dont_know;
2737 *overlaps_b = chrec_dont_know;
2738 *last_conflicts = chrec_dont_know;
2744 *overlaps_a = chrec_dont_know;
2745 *overlaps_b = chrec_dont_know;
2746 *last_conflicts = chrec_dont_know;
2750 if (dump_file && (dump_flags & TDF_DETAILS))
2752 fprintf (dump_file, " (overlaps_a = ");
2753 print_generic_expr (dump_file, *overlaps_a, 0);
2754 fprintf (dump_file, ")\n (overlaps_b = ");
2755 print_generic_expr (dump_file, *overlaps_b, 0);
2756 fprintf (dump_file, ")\n");
2759 if (dump_file && (dump_flags & TDF_DETAILS))
2760 fprintf (dump_file, ")\n");
2763 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2764 *OVERLAPS_B are initialized to the functions that describe the
2765 relation between the elements accessed twice by CHREC_A and
2766 CHREC_B. For k >= 0, the following property is verified:
2768 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2771 analyze_siv_subscript (tree chrec_a,
2775 tree *last_conflicts)
2777 if (dump_file && (dump_flags & TDF_DETAILS))
2778 fprintf (dump_file, "(analyze_siv_subscript \n");
2780 if (evolution_function_is_constant_p (chrec_a)
2781 && evolution_function_is_affine_p (chrec_b))
2782 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
2783 overlaps_a, overlaps_b, last_conflicts);
2785 else if (evolution_function_is_affine_p (chrec_a)
2786 && evolution_function_is_constant_p (chrec_b))
2787 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2788 overlaps_b, overlaps_a, last_conflicts);
2790 else if (evolution_function_is_affine_p (chrec_a)
2791 && evolution_function_is_affine_p (chrec_b))
2792 analyze_subscript_affine_affine (chrec_a, chrec_b,
2793 overlaps_a, overlaps_b, last_conflicts);
2796 *overlaps_a = chrec_dont_know;
2797 *overlaps_b = chrec_dont_know;
2798 *last_conflicts = chrec_dont_know;
2801 if (dump_file && (dump_flags & TDF_DETAILS))
2802 fprintf (dump_file, ")\n");
2805 /* Return true when the evolution steps of an affine CHREC divide the
2809 chrec_steps_divide_constant_p (tree chrec,
2812 switch (TREE_CODE (chrec))
2814 case POLYNOMIAL_CHREC:
2815 return (tree_fold_divides_p (CHREC_RIGHT (chrec), cst)
2816 && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
2819 /* On the initial condition, return true. */
2824 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
2825 *OVERLAPS_B are initialized to the functions that describe the
2826 relation between the elements accessed twice by CHREC_A and
2827 CHREC_B. For k >= 0, the following property is verified:
2829 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2832 analyze_miv_subscript (tree chrec_a,
2836 tree *last_conflicts)
2838 /* FIXME: This is a MIV subscript, not yet handled.
2839 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2842 In the SIV test we had to solve a Diophantine equation with two
2843 variables. In the MIV case we have to solve a Diophantine
2844 equation with 2*n variables (if the subscript uses n IVs).
2848 if (dump_file && (dump_flags & TDF_DETAILS))
2849 fprintf (dump_file, "(analyze_miv_subscript \n");
2851 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2853 if (chrec_zerop (difference))
2855 /* Access functions are the same: all the elements are accessed
2856 in the same order. */
2857 *overlaps_a = integer_zero_node;
2858 *overlaps_b = integer_zero_node;
2859 *last_conflicts = number_of_iterations_in_loop
2860 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2863 else if (evolution_function_is_constant_p (difference)
2864 /* For the moment, the following is verified:
2865 evolution_function_is_affine_multivariate_p (chrec_a) */
2866 && !chrec_steps_divide_constant_p (chrec_a, difference))
2868 /* testsuite/.../ssa-chrec-33.c
2869 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2871 The difference is 1, and the evolution steps are equal to 2,
2872 consequently there are no overlapping elements. */
2873 *overlaps_a = chrec_known;
2874 *overlaps_b = chrec_known;
2875 *last_conflicts = integer_zero_node;
2878 else if (evolution_function_is_affine_multivariate_p (chrec_a)
2879 && evolution_function_is_affine_multivariate_p (chrec_b))
2881 /* testsuite/.../ssa-chrec-35.c
2882 {0, +, 1}_2 vs. {0, +, 1}_3
2883 the overlapping elements are respectively located at iterations:
2884 {0, +, 1}_x and {0, +, 1}_x,
2885 in other words, we have the equality:
2886 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2889 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2890 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2892 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2893 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2895 analyze_subscript_affine_affine (chrec_a, chrec_b,
2896 overlaps_a, overlaps_b, last_conflicts);
2901 /* When the analysis is too difficult, answer "don't know". */
2902 *overlaps_a = chrec_dont_know;
2903 *overlaps_b = chrec_dont_know;
2904 *last_conflicts = chrec_dont_know;
2907 if (dump_file && (dump_flags & TDF_DETAILS))
2908 fprintf (dump_file, ")\n");
2911 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
2912 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
2913 two functions that describe the iterations that contain conflicting
2916 Remark: For an integer k >= 0, the following equality is true:
2918 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2922 analyze_overlapping_iterations (tree chrec_a,
2924 tree *overlap_iterations_a,
2925 tree *overlap_iterations_b,
2926 tree *last_conflicts)
2928 if (dump_file && (dump_flags & TDF_DETAILS))
2930 fprintf (dump_file, "(analyze_overlapping_iterations \n");
2931 fprintf (dump_file, " (chrec_a = ");
2932 print_generic_expr (dump_file, chrec_a, 0);
2933 fprintf (dump_file, ")\n chrec_b = ");
2934 print_generic_expr (dump_file, chrec_b, 0);
2935 fprintf (dump_file, ")\n");
2938 if (chrec_a == NULL_TREE
2939 || chrec_b == NULL_TREE
2940 || chrec_contains_undetermined (chrec_a)
2941 || chrec_contains_undetermined (chrec_b)
2942 || chrec_contains_symbols (chrec_a)
2943 || chrec_contains_symbols (chrec_b))
2945 *overlap_iterations_a = chrec_dont_know;
2946 *overlap_iterations_b = chrec_dont_know;
2949 else if (ziv_subscript_p (chrec_a, chrec_b))
2950 analyze_ziv_subscript (chrec_a, chrec_b,
2951 overlap_iterations_a, overlap_iterations_b,
2954 else if (siv_subscript_p (chrec_a, chrec_b))
2955 analyze_siv_subscript (chrec_a, chrec_b,
2956 overlap_iterations_a, overlap_iterations_b,
2960 analyze_miv_subscript (chrec_a, chrec_b,
2961 overlap_iterations_a, overlap_iterations_b,
2964 if (dump_file && (dump_flags & TDF_DETAILS))
2966 fprintf (dump_file, " (overlap_iterations_a = ");
2967 print_generic_expr (dump_file, *overlap_iterations_a, 0);
2968 fprintf (dump_file, ")\n (overlap_iterations_b = ");
2969 print_generic_expr (dump_file, *overlap_iterations_b, 0);
2970 fprintf (dump_file, ")\n");
2976 /* This section contains the affine functions dependences detector. */
2978 /* Computes the conflicting iterations, and initialize DDR. */
2981 subscript_dependence_tester (struct data_dependence_relation *ddr)
2984 struct data_reference *dra = DDR_A (ddr);
2985 struct data_reference *drb = DDR_B (ddr);
2986 tree last_conflicts;
2988 if (dump_file && (dump_flags & TDF_DETAILS))
2989 fprintf (dump_file, "(subscript_dependence_tester \n");
2991 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2993 tree overlaps_a, overlaps_b;
2994 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
2996 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
2997 DR_ACCESS_FN (drb, i),
2998 &overlaps_a, &overlaps_b,
3001 if (chrec_contains_undetermined (overlaps_a)
3002 || chrec_contains_undetermined (overlaps_b))
3004 finalize_ddr_dependent (ddr, chrec_dont_know);
3008 else if (overlaps_a == chrec_known
3009 || overlaps_b == chrec_known)
3011 finalize_ddr_dependent (ddr, chrec_known);
3017 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3018 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3019 SUB_LAST_CONFLICT (subscript) = last_conflicts;
3023 if (dump_file && (dump_flags & TDF_DETAILS))
3024 fprintf (dump_file, ")\n");
3027 /* Compute the classic per loop distance vector.
3029 DDR is the data dependence relation to build a vector from.
3030 NB_LOOPS is the total number of loops we are considering.
3031 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
3033 Return FALSE if the dependence relation is outside of the loop nest
3034 starting at FIRST_LOOP_DEPTH.
3035 Return TRUE otherwise. */
3038 build_classic_dist_vector (struct data_dependence_relation *ddr,
3039 int nb_loops, int first_loop_depth)
3042 lambda_vector dist_v, init_v;
3044 dist_v = lambda_vector_new (nb_loops);
3045 init_v = lambda_vector_new (nb_loops);
3046 lambda_vector_clear (dist_v, nb_loops);
3047 lambda_vector_clear (init_v, nb_loops);
3049 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3052 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3054 tree access_fn_a, access_fn_b;
3055 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3057 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3059 non_affine_dependence_relation (ddr);
3063 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
3064 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
3066 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3067 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3069 int dist, loop_nb, loop_depth;
3070 int loop_nb_a = CHREC_VARIABLE (access_fn_a);
3071 int loop_nb_b = CHREC_VARIABLE (access_fn_b);
3072 struct loop *loop_a = current_loops->parray[loop_nb_a];
3073 struct loop *loop_b = current_loops->parray[loop_nb_b];
3075 /* If the loop for either variable is at a lower depth than
3076 the first_loop's depth, then we can't possibly have a
3077 dependency at this level of the loop. */
3079 if (loop_a->depth < first_loop_depth
3080 || loop_b->depth < first_loop_depth)
3083 if (loop_nb_a != loop_nb_b
3084 && !flow_loop_nested_p (loop_a, loop_b)
3085 && !flow_loop_nested_p (loop_b, loop_a))
3087 /* Example: when there are two consecutive loops,
3096 the dependence relation cannot be captured by the
3097 distance abstraction. */
3098 non_affine_dependence_relation (ddr);
3102 /* The dependence is carried by the outermost loop. Example:
3109 In this case, the dependence is carried by loop_1. */
3110 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
3111 loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
3113 /* If the loop number is still greater than the number of
3114 loops we've been asked to analyze, or negative,
3115 something is borked. */
3116 gcc_assert (loop_depth >= 0);
3117 gcc_assert (loop_depth < nb_loops);
3118 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3120 non_affine_dependence_relation (ddr);
3124 dist = int_cst_value (SUB_DISTANCE (subscript));
3126 /* This is the subscript coupling test.
3131 There is no dependence. */
3132 if (init_v[loop_depth] != 0
3133 && dist_v[loop_depth] != dist)
3135 finalize_ddr_dependent (ddr, chrec_known);
3139 dist_v[loop_depth] = dist;
3140 init_v[loop_depth] = 1;
3144 /* There is a distance of 1 on all the outer loops:
3146 Example: there is a dependence of distance 1 on loop_1 for the array A.
3152 struct loop *lca, *loop_a, *loop_b;
3153 struct data_reference *a = DDR_A (ddr);
3154 struct data_reference *b = DDR_B (ddr);
3156 loop_a = loop_containing_stmt (DR_STMT (a));
3157 loop_b = loop_containing_stmt (DR_STMT (b));
3159 /* Get the common ancestor loop. */
3160 lca = find_common_loop (loop_a, loop_b);
3162 lca_depth = lca->depth;
3163 lca_depth -= first_loop_depth;
3164 gcc_assert (lca_depth >= 0);
3165 gcc_assert (lca_depth < nb_loops);
3167 /* For each outer loop where init_v is not set, the accesses are
3168 in dependence of distance 1 in the loop. */
3171 && init_v[lca_depth] == 0)
3172 dist_v[lca_depth] = 1;
3178 lca_depth = lca->depth - first_loop_depth;
3179 while (lca->depth != 0)
3181 /* If we're considering just a sub-nest, then don't record
3182 any information on the outer loops. */
3186 gcc_assert (lca_depth < nb_loops);
3188 if (init_v[lca_depth] == 0)
3189 dist_v[lca_depth] = 1;
3191 lca_depth = lca->depth - first_loop_depth;
3197 DDR_DIST_VECT (ddr) = dist_v;
3198 DDR_SIZE_VECT (ddr) = nb_loops;
3202 /* Compute the classic per loop direction vector.
3204 DDR is the data dependence relation to build a vector from.
3205 NB_LOOPS is the total number of loops we are considering.
3206 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
3208 Return FALSE if the dependence relation is outside of the loop nest
3209 at FIRST_LOOP_DEPTH.
3210 Return TRUE otherwise. */
3213 build_classic_dir_vector (struct data_dependence_relation *ddr,
3214 int nb_loops, int first_loop_depth)
3217 lambda_vector dir_v, init_v;
3219 dir_v = lambda_vector_new (nb_loops);
3220 init_v = lambda_vector_new (nb_loops);
3221 lambda_vector_clear (dir_v, nb_loops);
3222 lambda_vector_clear (init_v, nb_loops);
3224 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3227 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3229 tree access_fn_a, access_fn_b;
3230 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3232 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3234 non_affine_dependence_relation (ddr);
3238 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
3239 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
3240 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3241 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3243 int dist, loop_nb, loop_depth;
3244 enum data_dependence_direction dir = dir_star;
3245 int loop_nb_a = CHREC_VARIABLE (access_fn_a);
3246 int loop_nb_b = CHREC_VARIABLE (access_fn_b);
3247 struct loop *loop_a = current_loops->parray[loop_nb_a];
3248 struct loop *loop_b = current_loops->parray[loop_nb_b];
3250 /* If the loop for either variable is at a lower depth than
3251 the first_loop's depth, then we can't possibly have a
3252 dependency at this level of the loop. */
3254 if (loop_a->depth < first_loop_depth
3255 || loop_b->depth < first_loop_depth)
3258 if (loop_nb_a != loop_nb_b
3259 && !flow_loop_nested_p (loop_a, loop_b)
3260 && !flow_loop_nested_p (loop_b, loop_a))
3262 /* Example: when there are two consecutive loops,
3271 the dependence relation cannot be captured by the
3272 distance abstraction. */
3273 non_affine_dependence_relation (ddr);
3277 /* The dependence is carried by the outermost loop. Example:
3284 In this case, the dependence is carried by loop_1. */
3285 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
3286 loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
3288 /* If the loop number is still greater than the number of
3289 loops we've been asked to analyze, or negative,
3290 something is borked. */
3291 gcc_assert (loop_depth >= 0);
3292 gcc_assert (loop_depth < nb_loops);
3294 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3296 non_affine_dependence_relation (ddr);
3300 dist = int_cst_value (SUB_DISTANCE (subscript));
3309 /* This is the subscript coupling test.
3314 There is no dependence. */
3315 if (init_v[loop_depth] != 0
3317 && (enum data_dependence_direction) dir_v[loop_depth] != dir
3318 && (enum data_dependence_direction) dir_v[loop_depth] != dir_star)
3320 finalize_ddr_dependent (ddr, chrec_known);
3324 dir_v[loop_depth] = dir;
3325 init_v[loop_depth] = 1;
3329 /* There is a distance of 1 on all the outer loops:
3331 Example: there is a dependence of distance 1 on loop_1 for the array A.
3337 struct loop *lca, *loop_a, *loop_b;
3338 struct data_reference *a = DDR_A (ddr);
3339 struct data_reference *b = DDR_B (ddr);
3341 loop_a = loop_containing_stmt (DR_STMT (a));
3342 loop_b = loop_containing_stmt (DR_STMT (b));
3344 /* Get the common ancestor loop. */
3345 lca = find_common_loop (loop_a, loop_b);
3346 lca_depth = lca->depth - first_loop_depth;
3348 gcc_assert (lca_depth >= 0);
3349 gcc_assert (lca_depth < nb_loops);
3351 /* For each outer loop where init_v is not set, the accesses are
3352 in dependence of distance 1 in the loop. */
3355 && init_v[lca_depth] == 0)
3356 dir_v[lca_depth] = dir_positive;
3361 lca_depth = lca->depth - first_loop_depth;
3362 while (lca->depth != 0)
3364 /* If we're considering just a sub-nest, then don't record
3365 any information on the outer loops. */
3369 gcc_assert (lca_depth < nb_loops);
3371 if (init_v[lca_depth] == 0)
3372 dir_v[lca_depth] = dir_positive;
3374 lca_depth = lca->depth - first_loop_depth;
3380 DDR_DIR_VECT (ddr) = dir_v;
3381 DDR_SIZE_VECT (ddr) = nb_loops;
3385 /* Returns true when all the access functions of A are affine or
3389 access_functions_are_affine_or_constant_p (struct data_reference *a)
3392 VEC(tree,heap) **fns = DR_ACCESS_FNS_ADDR (a);
3395 for (i = 0; VEC_iterate (tree, *fns, i, t); i++)
3396 if (!evolution_function_is_constant_p (t)
3397 && !evolution_function_is_affine_multivariate_p (t))
3403 /* This computes the affine dependence relation between A and B.
3404 CHREC_KNOWN is used for representing the independence between two
3405 accesses, while CHREC_DONT_KNOW is used for representing the unknown
3408 Note that it is possible to stop the computation of the dependence
3409 relation the first time we detect a CHREC_KNOWN element for a given
3413 compute_affine_dependence (struct data_dependence_relation *ddr)
3415 struct data_reference *dra = DDR_A (ddr);
3416 struct data_reference *drb = DDR_B (ddr);
3418 if (dump_file && (dump_flags & TDF_DETAILS))
3420 fprintf (dump_file, "(compute_affine_dependence\n");
3421 fprintf (dump_file, " (stmt_a = \n");
3422 print_generic_expr (dump_file, DR_STMT (dra), 0);
3423 fprintf (dump_file, ")\n (stmt_b = \n");
3424 print_generic_expr (dump_file, DR_STMT (drb), 0);
3425 fprintf (dump_file, ")\n");
3428 /* Analyze only when the dependence relation is not yet known. */
3429 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3431 if (access_functions_are_affine_or_constant_p (dra)
3432 && access_functions_are_affine_or_constant_p (drb))
3433 subscript_dependence_tester (ddr);
3435 /* As a last case, if the dependence cannot be determined, or if
3436 the dependence is considered too difficult to determine, answer
3439 finalize_ddr_dependent (ddr, chrec_dont_know);
3442 if (dump_file && (dump_flags & TDF_DETAILS))
3443 fprintf (dump_file, ")\n");
3446 /* This computes the dependence relation for the same data
3447 reference into DDR. */
3450 compute_self_dependence (struct data_dependence_relation *ddr)
3454 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3456 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3458 /* The accessed index overlaps for each iteration. */
3459 SUB_CONFLICTS_IN_A (subscript) = integer_zero_node;
3460 SUB_CONFLICTS_IN_B (subscript) = integer_zero_node;
3461 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3466 typedef struct data_dependence_relation *ddr_p;
3468 DEF_VEC_ALLOC_P(ddr_p,heap);
3470 /* Compute a subset of the data dependence relation graph. Don't
3471 compute read-read and self relations if
3472 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is FALSE, and avoid the computation
3473 of the opposite relation, i.e. when AB has been computed, don't compute BA.
3474 DATAREFS contains a list of data references, and the result is set
3475 in DEPENDENCE_RELATIONS. */
3478 compute_all_dependences (varray_type datarefs,
3479 bool compute_self_and_read_read_dependences,
3480 VEC(ddr_p,heap) **dependence_relations)
3482 unsigned int i, j, N;
3484 N = VARRAY_ACTIVE_SIZE (datarefs);
3486 /* Note that we specifically skip i == j because it's a self dependence, and
3487 use compute_self_dependence below. */
3489 for (i = 0; i < N; i++)
3490 for (j = i + 1; j < N; j++)
3492 struct data_reference *a, *b;
3493 struct data_dependence_relation *ddr;
3495 a = VARRAY_GENERIC_PTR (datarefs, i);
3496 b = VARRAY_GENERIC_PTR (datarefs, j);
3497 if (DR_IS_READ (a) && DR_IS_READ (b)
3498 && !compute_self_and_read_read_dependences)
3500 ddr = initialize_data_dependence_relation (a, b);
3502 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3503 compute_affine_dependence (ddr);
3504 compute_subscript_distance (ddr);
3506 if (!compute_self_and_read_read_dependences)
3509 /* Compute self dependence relation of each dataref to itself. */
3511 for (i = 0; i < N; i++)
3513 struct data_reference *a, *b;
3514 struct data_dependence_relation *ddr;
3516 a = VARRAY_GENERIC_PTR (datarefs, i);
3517 b = VARRAY_GENERIC_PTR (datarefs, i);
3518 ddr = initialize_data_dependence_relation (a, b);
3520 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3521 compute_self_dependence (ddr);
3522 compute_subscript_distance (ddr);
3526 /* Search the data references in LOOP, and record the information into
3527 DATAREFS. Returns chrec_dont_know when failing to analyze a
3528 difficult case, returns NULL_TREE otherwise.
3530 TODO: This function should be made smarter so that it can handle address
3531 arithmetic as if they were array accesses, etc. */
3534 find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
3536 basic_block bb, *bbs;
3538 block_stmt_iterator bsi;
3539 struct data_reference *dr;
3541 bbs = get_loop_body (loop);
3543 for (i = 0; i < loop->num_nodes; i++)
3547 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3549 tree stmt = bsi_stmt (bsi);
3551 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
3552 Calls have side-effects, except those to const or pure
3554 if ((TREE_CODE (stmt) == CALL_EXPR
3555 && !(call_expr_flags (stmt) & (ECF_CONST | ECF_PURE)))
3556 || (TREE_CODE (stmt) == ASM_EXPR
3557 && ASM_VOLATILE_P (stmt)))
3558 goto insert_dont_know_node;
3560 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3563 switch (TREE_CODE (stmt))
3567 bool one_inserted = false;
3568 tree opnd0 = TREE_OPERAND (stmt, 0);
3569 tree opnd1 = TREE_OPERAND (stmt, 1);
3571 if (TREE_CODE (opnd0) == ARRAY_REF
3572 || TREE_CODE (opnd0) == INDIRECT_REF)
3574 dr = create_data_ref (opnd0, stmt, false);
3577 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3578 one_inserted = true;
3582 if (TREE_CODE (opnd1) == ARRAY_REF
3583 || TREE_CODE (opnd1) == INDIRECT_REF)
3585 dr = create_data_ref (opnd1, stmt, true);
3588 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3589 one_inserted = true;
3594 goto insert_dont_know_node;
3602 bool one_inserted = false;
3604 for (args = TREE_OPERAND (stmt, 1); args;
3605 args = TREE_CHAIN (args))
3606 if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
3607 || TREE_CODE (TREE_VALUE (args)) == INDIRECT_REF)
3609 dr = create_data_ref (TREE_VALUE (args), stmt, true);
3612 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3613 one_inserted = true;
3618 goto insert_dont_know_node;
3625 struct data_reference *res;
3627 insert_dont_know_node:;
3628 res = xmalloc (sizeof (struct data_reference));
3629 DR_STMT (res) = NULL_TREE;
3630 DR_REF (res) = NULL_TREE;
3631 DR_BASE_OBJECT (res) = NULL;
3632 DR_TYPE (res) = ARRAY_REF_TYPE;
3633 DR_SET_ACCESS_FNS (res, NULL);
3634 DR_BASE_OBJECT (res) = NULL;
3635 DR_IS_READ (res) = false;
3636 DR_BASE_ADDRESS (res) = NULL_TREE;
3637 DR_OFFSET (res) = NULL_TREE;
3638 DR_INIT (res) = NULL_TREE;
3639 DR_STEP (res) = NULL_TREE;
3640 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
3641 DR_MEMTAG (res) = NULL_TREE;
3642 DR_PTR_INFO (res) = NULL;
3643 VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
3646 return chrec_dont_know;
3650 /* When there are no defs in the loop, the loop is parallel. */
3651 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
3652 loop->parallel_p = false;
3663 /* This section contains all the entry points. */
3665 /* Given a loop nest LOOP, the following vectors are returned:
3666 *DATAREFS is initialized to all the array elements contained in this loop,
3667 *DEPENDENCE_RELATIONS contains the relations between the data references.
3668 Compute read-read and self relations if
3669 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
3672 compute_data_dependences_for_loop (struct loop *loop,
3673 bool compute_self_and_read_read_dependences,
3674 varray_type *datarefs,
3675 varray_type *dependence_relations)
3677 unsigned int i, nb_loops;
3678 VEC(ddr_p,heap) *allrelations;
3679 struct data_dependence_relation *ddr;
3680 struct loop *loop_nest = loop;
3682 while (loop_nest && loop_nest->outer && loop_nest->outer->outer)
3683 loop_nest = loop_nest->outer;
3685 nb_loops = loop_nest->level;
3687 /* If one of the data references is not computable, give up without
3688 spending time to compute other dependences. */
3689 if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
3691 struct data_dependence_relation *ddr;
3693 /* Insert a single relation into dependence_relations:
3695 ddr = initialize_data_dependence_relation (NULL, NULL);
3696 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
3697 build_classic_dist_vector (ddr, nb_loops, loop->depth);
3698 build_classic_dir_vector (ddr, nb_loops, loop->depth);
3702 allrelations = NULL;
3703 compute_all_dependences (*datarefs, compute_self_and_read_read_dependences,
3706 for (i = 0; VEC_iterate (ddr_p, allrelations, i, ddr); i++)
3708 if (build_classic_dist_vector (ddr, nb_loops, loop_nest->depth))
3710 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
3711 build_classic_dir_vector (ddr, nb_loops, loop_nest->depth);
3716 /* Entry point (for testing only). Analyze all the data references
3717 and the dependence relations.
3719 The data references are computed first.
3721 A relation on these nodes is represented by a complete graph. Some
3722 of the relations could be of no interest, thus the relations can be
3725 In the following function we compute all the relations. This is
3726 just a first implementation that is here for:
3727 - for showing how to ask for the dependence relations,
3728 - for the debugging the whole dependence graph,
3729 - for the dejagnu testcases and maintenance.
3731 It is possible to ask only for a part of the graph, avoiding to
3732 compute the whole dependence graph. The computed dependences are
3733 stored in a knowledge base (KB) such that later queries don't
3734 recompute the same information. The implementation of this KB is
3735 transparent to the optimizer, and thus the KB can be changed with a
3736 more efficient implementation, or the KB could be disabled. */
3739 analyze_all_data_dependences (struct loops *loops)
3742 varray_type datarefs;
3743 varray_type dependence_relations;
3744 int nb_data_refs = 10;
3746 VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
3747 VARRAY_GENERIC_PTR_INIT (dependence_relations,
3748 nb_data_refs * nb_data_refs,
3749 "dependence_relations");
3751 /* Compute DDs on the whole function. */
3752 compute_data_dependences_for_loop (loops->parray[0], false,
3753 &datarefs, &dependence_relations);
3757 dump_data_dependence_relations (dump_file, dependence_relations);
3758 fprintf (dump_file, "\n\n");
3760 if (dump_flags & TDF_DETAILS)
3761 dump_dist_dir_vectors (dump_file, dependence_relations);
3763 if (dump_flags & TDF_STATS)
3765 unsigned nb_top_relations = 0;
3766 unsigned nb_bot_relations = 0;
3767 unsigned nb_basename_differ = 0;
3768 unsigned nb_chrec_relations = 0;
3770 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
3772 struct data_dependence_relation *ddr;
3773 ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
3775 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
3778 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
3780 struct data_reference *a = DDR_A (ddr);
3781 struct data_reference *b = DDR_B (ddr);
3784 if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
3785 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
3786 || (base_object_differ_p (a, b, &differ_p)
3788 nb_basename_differ++;
3794 nb_chrec_relations++;
3797 gather_stats_on_scev_database ();
3801 free_dependence_relations (dependence_relations);
3802 free_data_refs (datarefs);
3805 /* Free the memory used by a data dependence relation DDR. */
3808 free_dependence_relation (struct data_dependence_relation *ddr)
3813 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
3814 varray_clear (DDR_SUBSCRIPTS (ddr));
3818 /* Free the memory used by the data dependence relations from
3819 DEPENDENCE_RELATIONS. */
3822 free_dependence_relations (varray_type dependence_relations)
3825 if (dependence_relations == NULL)
3828 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
3829 free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
3830 varray_clear (dependence_relations);
3833 /* Free the memory used by the data references from DATAREFS. */
3836 free_data_refs (varray_type datarefs)
3840 if (datarefs == NULL)
3843 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
3845 struct data_reference *dr = (struct data_reference *)
3846 VARRAY_GENERIC_PTR (datarefs, i);
3849 DR_FREE_ACCESS_FNS (dr);
3853 varray_clear (datarefs);