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]".
803 If ESTIMATE_ONLY is true, we just set the estimated number of loop
804 iterations, we don't store the access function.
805 The function returns the base name: "A". */
808 analyze_array_indexes (struct loop *loop,
809 VEC(tree,heap) **access_fns,
816 opnd0 = TREE_OPERAND (ref, 0);
817 opnd1 = TREE_OPERAND (ref, 1);
819 /* The detection of the evolution function for this data access is
820 postponed until the dependence test. This lazy strategy avoids
821 the computation of access functions that are of no interest for
823 access_fn = instantiate_parameters
824 (loop, analyze_scalar_evolution (loop, opnd1));
826 if (chrec_contains_undetermined (loop->estimated_nb_iterations))
827 estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
830 VEC_safe_push (tree, heap, *access_fns, access_fn);
832 /* Recursively record other array access functions. */
833 if (TREE_CODE (opnd0) == ARRAY_REF)
834 return analyze_array_indexes (loop, access_fns, opnd0, stmt, estimate_only);
836 /* Return the base name of the data access. */
841 /* For an array reference REF contained in STMT, attempt to bound the
842 number of iterations in the loop containing STMT */
845 estimate_iters_using_array (tree stmt, tree ref)
847 analyze_array_indexes (loop_containing_stmt (stmt), NULL, ref, stmt,
851 /* For a data reference REF contained in the statement STMT, initialize
852 a DATA_REFERENCE structure, and return it. IS_READ flag has to be
853 set to true when REF is in the right hand side of an
856 struct data_reference *
857 analyze_array (tree stmt, tree ref, bool is_read)
859 struct data_reference *res;
860 VEC(tree,heap) *acc_fns;
862 if (dump_file && (dump_flags & TDF_DETAILS))
864 fprintf (dump_file, "(analyze_array \n");
865 fprintf (dump_file, " (ref = ");
866 print_generic_stmt (dump_file, ref, 0);
867 fprintf (dump_file, ")\n");
870 res = xmalloc (sizeof (struct data_reference));
872 DR_STMT (res) = stmt;
874 acc_fns = VEC_alloc (tree, heap, 3);
875 DR_BASE_OBJECT (res) = analyze_array_indexes
876 (loop_containing_stmt (stmt), &acc_fns, ref, stmt, false);
877 DR_TYPE (res) = ARRAY_REF_TYPE;
878 DR_SET_ACCESS_FNS (res, acc_fns);
879 DR_IS_READ (res) = is_read;
880 DR_BASE_ADDRESS (res) = NULL_TREE;
881 DR_OFFSET (res) = NULL_TREE;
882 DR_INIT (res) = NULL_TREE;
883 DR_STEP (res) = NULL_TREE;
884 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
885 DR_MEMTAG (res) = NULL_TREE;
886 DR_PTR_INFO (res) = NULL;
888 if (dump_file && (dump_flags & TDF_DETAILS))
889 fprintf (dump_file, ")\n");
895 /* Analyze an indirect memory reference, REF, that comes from STMT.
896 IS_READ is true if this is an indirect load, and false if it is
898 Return a new data reference structure representing the indirect_ref, or
899 NULL if we cannot describe the access function. */
901 static struct data_reference *
902 analyze_indirect_ref (tree stmt, tree ref, bool is_read)
904 struct loop *loop = loop_containing_stmt (stmt);
905 tree ptr_ref = TREE_OPERAND (ref, 0);
906 tree access_fn = analyze_scalar_evolution (loop, ptr_ref);
907 tree init = initial_condition_in_loop_num (access_fn, loop->num);
908 tree base_address = NULL_TREE, evolution, step = NULL_TREE;
909 struct ptr_info_def *ptr_info = NULL;
911 if (TREE_CODE (ptr_ref) == SSA_NAME)
912 ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
915 if (access_fn == chrec_dont_know || !init || init == chrec_dont_know)
917 if (dump_file && (dump_flags & TDF_DETAILS))
919 fprintf (dump_file, "\nBad access function of ptr: ");
920 print_generic_expr (dump_file, ref, TDF_SLIM);
921 fprintf (dump_file, "\n");
926 if (dump_file && (dump_flags & TDF_DETAILS))
928 fprintf (dump_file, "\nAccess function of ptr: ");
929 print_generic_expr (dump_file, access_fn, TDF_SLIM);
930 fprintf (dump_file, "\n");
933 if (!expr_invariant_in_loop_p (loop, init))
935 if (dump_file && (dump_flags & TDF_DETAILS))
936 fprintf (dump_file, "\ninitial condition is not loop invariant.\n");
941 evolution = evolution_part_in_loop_num (access_fn, loop->num);
942 if (evolution != chrec_dont_know)
945 step = ssize_int (0);
948 if (TREE_CODE (evolution) == INTEGER_CST)
949 step = fold_convert (ssizetype, evolution);
951 if (dump_file && (dump_flags & TDF_DETAILS))
952 fprintf (dump_file, "\nnon constant step for ptr access.\n");
956 if (dump_file && (dump_flags & TDF_DETAILS))
957 fprintf (dump_file, "\nunknown evolution of ptr.\n");
959 return init_data_ref (stmt, ref, NULL_TREE, access_fn, is_read, base_address,
960 NULL_TREE, step, NULL_TREE, NULL_TREE,
961 ptr_info, POINTER_REF_TYPE);
964 /* For a data reference REF contained in the statement STMT, initialize
965 a DATA_REFERENCE structure, and return it. */
967 struct data_reference *
968 init_data_ref (tree stmt,
978 struct ptr_info_def *ptr_info,
979 enum data_ref_type type)
981 struct data_reference *res;
982 VEC(tree,heap) *acc_fns;
984 if (dump_file && (dump_flags & TDF_DETAILS))
986 fprintf (dump_file, "(init_data_ref \n");
987 fprintf (dump_file, " (ref = ");
988 print_generic_stmt (dump_file, ref, 0);
989 fprintf (dump_file, ")\n");
992 res = xmalloc (sizeof (struct data_reference));
994 DR_STMT (res) = stmt;
996 DR_BASE_OBJECT (res) = base;
997 DR_TYPE (res) = type;
998 acc_fns = VEC_alloc (tree, heap, 3);
999 DR_SET_ACCESS_FNS (res, acc_fns);
1000 VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
1001 DR_IS_READ (res) = is_read;
1002 DR_BASE_ADDRESS (res) = base_address;
1003 DR_OFFSET (res) = init_offset;
1004 DR_INIT (res) = NULL_TREE;
1005 DR_STEP (res) = step;
1006 DR_OFFSET_MISALIGNMENT (res) = misalign;
1007 DR_MEMTAG (res) = memtag;
1008 DR_PTR_INFO (res) = ptr_info;
1010 if (dump_file && (dump_flags & TDF_DETAILS))
1011 fprintf (dump_file, ")\n");
1018 /* Function strip_conversions
1020 Strip conversions that don't narrow the mode. */
1023 strip_conversion (tree expr)
1025 tree to, ti, oprnd0;
1027 while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
1029 to = TREE_TYPE (expr);
1030 oprnd0 = TREE_OPERAND (expr, 0);
1031 ti = TREE_TYPE (oprnd0);
1033 if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti))
1035 if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti)))
1044 /* Function analyze_offset_expr
1046 Given an offset expression EXPR received from get_inner_reference, analyze
1047 it and create an expression for INITIAL_OFFSET by substituting the variables
1048 of EXPR with initial_condition of the corresponding access_fn in the loop.
1051 for (j = 3; j < N; j++)
1054 For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be
1055 substituted, since its access_fn in the inner loop is i. 'j' will be
1056 substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
1059 Compute MISALIGN (the misalignment of the data reference initial access from
1060 its base). Misalignment can be calculated only if all the variables can be
1061 substituted with constants, otherwise, we record maximum possible alignment
1062 in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN
1063 will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be
1064 recorded in ALIGNED_TO.
1066 STEP is an evolution of the data reference in this loop in bytes.
1067 In the above example, STEP is C_j.
1069 Return FALSE, if the analysis fails, e.g., there is no access_fn for a
1070 variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO
1071 and STEP) are NULL_TREEs. Otherwise, return TRUE.
1076 analyze_offset_expr (tree expr,
1078 tree *initial_offset,
1085 tree left_offset = ssize_int (0);
1086 tree right_offset = ssize_int (0);
1087 tree left_misalign = ssize_int (0);
1088 tree right_misalign = ssize_int (0);
1089 tree left_step = ssize_int (0);
1090 tree right_step = ssize_int (0);
1091 enum tree_code code;
1092 tree init, evolution;
1093 tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE;
1096 *misalign = NULL_TREE;
1097 *aligned_to = NULL_TREE;
1098 *initial_offset = NULL_TREE;
1100 /* Strip conversions that don't narrow the mode. */
1101 expr = strip_conversion (expr);
1107 if (TREE_CODE (expr) == INTEGER_CST)
1109 *initial_offset = fold_convert (ssizetype, expr);
1110 *misalign = fold_convert (ssizetype, expr);
1111 *step = ssize_int (0);
1115 /* 2. Variable. Try to substitute with initial_condition of the corresponding
1116 access_fn in the current loop. */
1117 if (SSA_VAR_P (expr))
1119 tree access_fn = analyze_scalar_evolution (loop, expr);
1121 if (access_fn == chrec_dont_know)
1125 init = initial_condition_in_loop_num (access_fn, loop->num);
1126 if (init == expr && !expr_invariant_in_loop_p (loop, init))
1127 /* Not enough information: may be not loop invariant.
1128 E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
1129 initial_condition is D, but it depends on i - loop's induction
1133 evolution = evolution_part_in_loop_num (access_fn, loop->num);
1134 if (evolution && TREE_CODE (evolution) != INTEGER_CST)
1135 /* Evolution is not constant. */
1138 if (TREE_CODE (init) == INTEGER_CST)
1139 *misalign = fold_convert (ssizetype, init);
1141 /* Not constant, misalignment cannot be calculated. */
1142 *misalign = NULL_TREE;
1144 *initial_offset = fold_convert (ssizetype, init);
1146 *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
1150 /* Recursive computation. */
1151 if (!BINARY_CLASS_P (expr))
1153 /* We expect to get binary expressions (PLUS/MINUS and MULT). */
1154 if (dump_file && (dump_flags & TDF_DETAILS))
1156 fprintf (dump_file, "\nNot binary expression ");
1157 print_generic_expr (dump_file, expr, TDF_SLIM);
1158 fprintf (dump_file, "\n");
1162 oprnd0 = TREE_OPERAND (expr, 0);
1163 oprnd1 = TREE_OPERAND (expr, 1);
1165 if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign,
1166 &left_aligned_to, &left_step)
1167 || !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign,
1168 &right_aligned_to, &right_step))
1171 /* The type of the operation: plus, minus or mult. */
1172 code = TREE_CODE (expr);
1176 if (TREE_CODE (right_offset) != INTEGER_CST)
1177 /* RIGHT_OFFSET can be not constant. For example, for arrays of variable
1179 FORNOW: We don't support such cases. */
1182 /* Strip conversions that don't narrow the mode. */
1183 left_offset = strip_conversion (left_offset);
1186 /* Misalignment computation. */
1187 if (SSA_VAR_P (left_offset))
1189 /* If the left side contains variables that can't be substituted with
1190 constants, the misalignment is unknown. However, if the right side
1191 is a multiple of some alignment, we know that the expression is
1192 aligned to it. Therefore, we record such maximum possible value.
1194 *misalign = NULL_TREE;
1195 *aligned_to = ssize_int (highest_pow2_factor (right_offset));
1199 /* The left operand was successfully substituted with constant. */
1202 /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is
1204 *misalign = size_binop (code, left_misalign, right_misalign);
1205 if (left_aligned_to && right_aligned_to)
1206 *aligned_to = size_binop (MIN_EXPR, left_aligned_to,
1209 *aligned_to = left_aligned_to ?
1210 left_aligned_to : right_aligned_to;
1213 *misalign = NULL_TREE;
1216 /* Step calculation. */
1217 /* Multiply the step by the right operand. */
1218 *step = size_binop (MULT_EXPR, left_step, right_offset);
1223 /* Combine the recursive calculations for step and misalignment. */
1224 *step = size_binop (code, left_step, right_step);
1226 /* Unknown alignment. */
1227 if ((!left_misalign && !left_aligned_to)
1228 || (!right_misalign && !right_aligned_to))
1230 *misalign = NULL_TREE;
1231 *aligned_to = NULL_TREE;
1235 if (left_misalign && right_misalign)
1236 *misalign = size_binop (code, left_misalign, right_misalign);
1238 *misalign = left_misalign ? left_misalign : right_misalign;
1240 if (left_aligned_to && right_aligned_to)
1241 *aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to);
1243 *aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to;
1251 /* Compute offset. */
1252 *initial_offset = fold_convert (ssizetype,
1253 fold_build2 (code, TREE_TYPE (left_offset),
1259 /* Function address_analysis
1261 Return the BASE of the address expression EXPR.
1262 Also compute the OFFSET from BASE, MISALIGN and STEP.
1265 EXPR - the address expression that is being analyzed
1266 STMT - the statement that contains EXPR or its original memory reference
1267 IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
1268 DR - data_reference struct for the original memory reference
1271 BASE (returned value) - the base of the data reference EXPR.
1272 INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
1273 MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
1274 computation is impossible
1275 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1276 calculated (doesn't depend on variables)
1277 STEP - evolution of EXPR in the loop
1279 If something unexpected is encountered (an unsupported form of data-ref),
1280 then NULL_TREE is returned.
1284 address_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr,
1285 tree *offset, tree *misalign, tree *aligned_to, tree *step)
1287 tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
1288 tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1289 tree dummy, address_aligned_to = NULL_TREE;
1290 struct ptr_info_def *dummy1;
1293 switch (TREE_CODE (expr))
1297 /* EXPR is of form {base +/- offset} (or {offset +/- base}). */
1298 oprnd0 = TREE_OPERAND (expr, 0);
1299 oprnd1 = TREE_OPERAND (expr, 1);
1301 STRIP_NOPS (oprnd0);
1302 STRIP_NOPS (oprnd1);
1304 /* Recursively try to find the base of the address contained in EXPR.
1305 For offset, the returned base will be NULL. */
1306 base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset,
1307 &address_misalign, &address_aligned_to,
1310 base_addr1 = address_analysis (oprnd1, stmt, is_read, dr, &address_offset,
1311 &address_misalign, &address_aligned_to,
1314 /* We support cases where only one of the operands contains an
1316 if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
1318 if (dump_file && (dump_flags & TDF_DETAILS))
1321 "\neither more than one address or no addresses in expr ");
1322 print_generic_expr (dump_file, expr, TDF_SLIM);
1323 fprintf (dump_file, "\n");
1328 /* To revert STRIP_NOPS. */
1329 oprnd0 = TREE_OPERAND (expr, 0);
1330 oprnd1 = TREE_OPERAND (expr, 1);
1332 offset_expr = base_addr0 ?
1333 fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
1335 /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is
1336 a number, we can add it to the misalignment value calculated for base,
1337 otherwise, misalignment is NULL. */
1338 if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
1340 *misalign = size_binop (TREE_CODE (expr), address_misalign,
1342 *aligned_to = address_aligned_to;
1346 *misalign = NULL_TREE;
1347 *aligned_to = NULL_TREE;
1350 /* Combine offset (from EXPR {base + offset}) with the offset calculated
1352 *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
1353 return base_addr0 ? base_addr0 : base_addr1;
1356 base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read,
1357 &dr, offset, misalign, aligned_to, step,
1358 &dummy, &dummy1, &dummy2);
1359 return base_address;
1362 if (!POINTER_TYPE_P (TREE_TYPE (expr)))
1364 if (dump_file && (dump_flags & TDF_DETAILS))
1366 fprintf (dump_file, "\nnot pointer SSA_NAME ");
1367 print_generic_expr (dump_file, expr, TDF_SLIM);
1368 fprintf (dump_file, "\n");
1372 *aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr))));
1373 *misalign = ssize_int (0);
1374 *offset = ssize_int (0);
1375 *step = ssize_int (0);
1384 /* Function object_analysis
1386 Create a data-reference structure DR for MEMREF.
1387 Return the BASE of the data reference MEMREF if the analysis is possible.
1388 Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1389 E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset
1390 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET
1391 instantiated with initial_conditions of access_functions of variables,
1392 and STEP is the evolution of the DR_REF in this loop.
1394 Function get_inner_reference is used for the above in case of ARRAY_REF and
1397 The structure of the function is as follows:
1399 Case 1. For handled_component_p refs
1400 1.1 build data-reference structure for MEMREF
1401 1.2 call get_inner_reference
1402 1.2.1 analyze offset expr received from get_inner_reference
1403 (fall through with BASE)
1404 Case 2. For declarations
1406 Case 3. For INDIRECT_REFs
1407 3.1 build data-reference structure for MEMREF
1408 3.2 analyze evolution and initial condition of MEMREF
1409 3.3 set data-reference structure for MEMREF
1410 3.4 call address_analysis to analyze INIT of the access function
1411 3.5 extract memory tag
1414 Combine the results of object and address analysis to calculate
1415 INITIAL_OFFSET, STEP and misalignment info.
1418 MEMREF - the memory reference that is being analyzed
1419 STMT - the statement that contains MEMREF
1420 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1423 BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
1424 E.g, if MEMREF is a.b[k].c[i][j] the returned
1426 DR - data_reference struct for MEMREF
1427 INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
1428 MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of
1429 ALIGNMENT or NULL_TREE if the computation is impossible
1430 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1431 calculated (doesn't depend on variables)
1432 STEP - evolution of the DR_REF in the loop
1433 MEMTAG - memory tag for aliasing purposes
1434 PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
1435 SUBVARS - Sub-variables of the variable
1437 If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned,
1438 but DR can be created anyway.
1443 object_analysis (tree memref, tree stmt, bool is_read,
1444 struct data_reference **dr, tree *offset, tree *misalign,
1445 tree *aligned_to, tree *step, tree *memtag,
1446 struct ptr_info_def **ptr_info, subvar_t *subvars)
1448 tree base = NULL_TREE, base_address = NULL_TREE;
1449 tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
1450 tree object_step = ssize_int (0), address_step = ssize_int (0);
1451 tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1452 HOST_WIDE_INT pbitsize, pbitpos;
1453 tree poffset, bit_pos_in_bytes;
1454 enum machine_mode pmode;
1455 int punsignedp, pvolatilep;
1456 tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
1457 struct loop *loop = loop_containing_stmt (stmt);
1458 struct data_reference *ptr_dr = NULL;
1459 tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE;
1464 /* Case 1. handled_component_p refs. */
1465 if (handled_component_p (memref))
1467 /* 1.1 build data-reference structure for MEMREF. */
1468 /* TODO: handle COMPONENT_REFs. */
1471 if (TREE_CODE (memref) == ARRAY_REF)
1472 *dr = analyze_array (stmt, memref, is_read);
1476 if (dump_file && (dump_flags & TDF_DETAILS))
1478 fprintf (dump_file, "\ndata-ref of unsupported type ");
1479 print_generic_expr (dump_file, memref, TDF_SLIM);
1480 fprintf (dump_file, "\n");
1486 /* 1.2 call get_inner_reference. */
1487 /* Find the base and the offset from it. */
1488 base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
1489 &pmode, &punsignedp, &pvolatilep, false);
1492 if (dump_file && (dump_flags & TDF_DETAILS))
1494 fprintf (dump_file, "\nfailed to get inner ref for ");
1495 print_generic_expr (dump_file, memref, TDF_SLIM);
1496 fprintf (dump_file, "\n");
1501 /* 1.2.1 analyze offset expr received from get_inner_reference. */
1503 && !analyze_offset_expr (poffset, loop, &object_offset,
1504 &object_misalign, &object_aligned_to,
1507 if (dump_file && (dump_flags & TDF_DETAILS))
1509 fprintf (dump_file, "\nfailed to compute offset or step for ");
1510 print_generic_expr (dump_file, memref, TDF_SLIM);
1511 fprintf (dump_file, "\n");
1516 /* Add bit position to OFFSET and MISALIGN. */
1518 bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
1519 /* Check that there is no remainder in bits. */
1520 if (pbitpos%BITS_PER_UNIT)
1522 if (dump_file && (dump_flags & TDF_DETAILS))
1523 fprintf (dump_file, "\nbit offset alignment.\n");
1526 object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);
1527 if (object_misalign)
1528 object_misalign = size_binop (PLUS_EXPR, object_misalign,
1531 memref = base; /* To continue analysis of BASE. */
1535 /* Part 1: Case 2. Declarations. */
1536 if (DECL_P (memref))
1538 /* We expect to get a decl only if we already have a DR. */
1541 if (dump_file && (dump_flags & TDF_DETAILS))
1543 fprintf (dump_file, "\nunhandled decl ");
1544 print_generic_expr (dump_file, memref, TDF_SLIM);
1545 fprintf (dump_file, "\n");
1550 /* TODO: if during the analysis of INDIRECT_REF we get to an object, put
1551 the object in BASE_OBJECT field if we can prove that this is O.K.,
1552 i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT.
1553 (e.g., if the object is an array base 'a', where 'a[N]', we must prove
1554 that every access with 'p' (the original INDIRECT_REF based on '&a')
1555 in the loop is within the array boundaries - from a[0] to a[N-1]).
1556 Otherwise, our alias analysis can be incorrect.
1557 Even if an access function based on BASE_OBJECT can't be build, update
1558 BASE_OBJECT field to enable us to prove that two data-refs are
1559 different (without access function, distance analysis is impossible).
1561 if (SSA_VAR_P (memref) && var_can_have_subvars (memref))
1562 *subvars = get_subvars_for_var (memref);
1563 base_address = build_fold_addr_expr (memref);
1564 /* 2.1 set MEMTAG. */
1568 /* Part 1: Case 3. INDIRECT_REFs. */
1569 else if (TREE_CODE (memref) == INDIRECT_REF)
1571 tree ptr_ref = TREE_OPERAND (memref, 0);
1572 if (TREE_CODE (ptr_ref) == SSA_NAME)
1573 *ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
1575 /* 3.1 build data-reference structure for MEMREF. */
1576 ptr_dr = analyze_indirect_ref (stmt, memref, is_read);
1579 if (dump_file && (dump_flags & TDF_DETAILS))
1581 fprintf (dump_file, "\nfailed to create dr for ");
1582 print_generic_expr (dump_file, memref, TDF_SLIM);
1583 fprintf (dump_file, "\n");
1588 /* 3.2 analyze evolution and initial condition of MEMREF. */
1589 ptr_step = DR_STEP (ptr_dr);
1590 ptr_init = DR_BASE_ADDRESS (ptr_dr);
1591 if (!ptr_init || !ptr_step || !POINTER_TYPE_P (TREE_TYPE (ptr_init)))
1593 *dr = (*dr) ? *dr : ptr_dr;
1594 if (dump_file && (dump_flags & TDF_DETAILS))
1596 fprintf (dump_file, "\nbad pointer access ");
1597 print_generic_expr (dump_file, memref, TDF_SLIM);
1598 fprintf (dump_file, "\n");
1603 if (integer_zerop (ptr_step) && !(*dr))
1605 if (dump_file && (dump_flags & TDF_DETAILS))
1606 fprintf (dump_file, "\nptr is loop invariant.\n");
1610 /* If there exists DR for MEMREF, we are analyzing the base of
1611 handled component (PTR_INIT), which not necessary has evolution in
1614 object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
1616 /* 3.3 set data-reference structure for MEMREF. */
1620 /* 3.4 call address_analysis to analyze INIT of the access
1622 base_address = address_analysis (ptr_init, stmt, is_read, *dr,
1623 &address_offset, &address_misalign,
1624 &address_aligned_to, &address_step);
1627 if (dump_file && (dump_flags & TDF_DETAILS))
1629 fprintf (dump_file, "\nfailed to analyze address ");
1630 print_generic_expr (dump_file, ptr_init, TDF_SLIM);
1631 fprintf (dump_file, "\n");
1636 /* 3.5 extract memory tag. */
1637 switch (TREE_CODE (base_address))
1640 *memtag = get_var_ann (SSA_NAME_VAR (base_address))->type_mem_tag;
1641 if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
1642 *memtag = get_var_ann (
1643 SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->type_mem_tag;
1646 *memtag = TREE_OPERAND (base_address, 0);
1649 if (dump_file && (dump_flags & TDF_DETAILS))
1651 fprintf (dump_file, "\nno memtag for ");
1652 print_generic_expr (dump_file, memref, TDF_SLIM);
1653 fprintf (dump_file, "\n");
1655 *memtag = NULL_TREE;
1662 /* MEMREF cannot be analyzed. */
1663 if (dump_file && (dump_flags & TDF_DETAILS))
1665 fprintf (dump_file, "\ndata-ref of unsupported type ");
1666 print_generic_expr (dump_file, memref, TDF_SLIM);
1667 fprintf (dump_file, "\n");
1672 if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag))
1673 *subvars = get_subvars_for_var (*memtag);
1675 /* Part 2: Combine the results of object and address analysis to calculate
1676 INITIAL_OFFSET, STEP and misalignment info. */
1677 *offset = size_binop (PLUS_EXPR, object_offset, address_offset);
1679 if ((!object_misalign && !object_aligned_to)
1680 || (!address_misalign && !address_aligned_to))
1682 *misalign = NULL_TREE;
1683 *aligned_to = NULL_TREE;
1687 if (object_misalign && address_misalign)
1688 *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
1690 *misalign = object_misalign ? object_misalign : address_misalign;
1691 if (object_aligned_to && address_aligned_to)
1692 *aligned_to = size_binop (MIN_EXPR, object_aligned_to,
1693 address_aligned_to);
1695 *aligned_to = object_aligned_to ?
1696 object_aligned_to : address_aligned_to;
1698 *step = size_binop (PLUS_EXPR, object_step, address_step);
1700 return base_address;
1703 /* Function analyze_offset.
1705 Extract INVARIANT and CONSTANT parts from OFFSET.
1709 analyze_offset (tree offset, tree *invariant, tree *constant)
1711 tree op0, op1, constant_0, constant_1, invariant_0, invariant_1;
1712 enum tree_code code = TREE_CODE (offset);
1714 *invariant = NULL_TREE;
1715 *constant = NULL_TREE;
1717 /* Not PLUS/MINUS expression - recursion stop condition. */
1718 if (code != PLUS_EXPR && code != MINUS_EXPR)
1720 if (TREE_CODE (offset) == INTEGER_CST)
1723 *invariant = offset;
1727 op0 = TREE_OPERAND (offset, 0);
1728 op1 = TREE_OPERAND (offset, 1);
1730 /* Recursive call with the operands. */
1731 analyze_offset (op0, &invariant_0, &constant_0);
1732 analyze_offset (op1, &invariant_1, &constant_1);
1734 /* Combine the results. */
1735 *constant = constant_0 ? constant_0 : constant_1;
1736 if (invariant_0 && invariant_1)
1738 fold_build2 (code, TREE_TYPE (invariant_0), invariant_0, invariant_1);
1740 *invariant = invariant_0 ? invariant_0 : invariant_1;
1744 /* Function create_data_ref.
1746 Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS,
1747 DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO,
1748 DR_MEMTAG, and DR_POINTSTO_INFO fields.
1751 MEMREF - the memory reference that is being analyzed
1752 STMT - the statement that contains MEMREF
1753 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1756 DR (returned value) - data_reference struct for MEMREF
1759 static struct data_reference *
1760 create_data_ref (tree memref, tree stmt, bool is_read)
1762 struct data_reference *dr = NULL;
1763 tree base_address, offset, step, misalign, memtag;
1764 struct loop *loop = loop_containing_stmt (stmt);
1765 tree invariant = NULL_TREE, constant = NULL_TREE;
1766 tree type_size, init_cond;
1767 struct ptr_info_def *ptr_info;
1768 subvar_t subvars = NULL;
1774 base_address = object_analysis (memref, stmt, is_read, &dr, &offset,
1775 &misalign, &aligned_to, &step, &memtag,
1776 &ptr_info, &subvars);
1777 if (!dr || !base_address)
1779 if (dump_file && (dump_flags & TDF_DETAILS))
1781 fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for ");
1782 print_generic_expr (dump_file, memref, TDF_SLIM);
1783 fprintf (dump_file, "\n");
1788 DR_BASE_ADDRESS (dr) = base_address;
1789 DR_OFFSET (dr) = offset;
1790 DR_INIT (dr) = ssize_int (0);
1791 DR_STEP (dr) = step;
1792 DR_OFFSET_MISALIGNMENT (dr) = misalign;
1793 DR_ALIGNED_TO (dr) = aligned_to;
1794 DR_MEMTAG (dr) = memtag;
1795 DR_PTR_INFO (dr) = ptr_info;
1796 DR_SUBVARS (dr) = subvars;
1798 type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
1800 /* Change the access function for INIDIRECT_REFs, according to
1801 DR_BASE_ADDRESS. Analyze OFFSET calculated in object_analysis. OFFSET is
1802 an expression that can contain loop invariant expressions and constants.
1803 We put the constant part in the initial condition of the access function
1804 (for data dependence tests), and in DR_INIT of the data-ref. The loop
1805 invariant part is put in DR_OFFSET.
1806 The evolution part of the access function is STEP calculated in
1807 object_analysis divided by the size of data type.
1809 if (!DR_BASE_OBJECT (dr))
1814 /* Extract CONSTANT and INVARIANT from OFFSET, and put them in DR_INIT and
1815 DR_OFFSET fields of DR. */
1816 analyze_offset (offset, &invariant, &constant);
1819 DR_INIT (dr) = fold_convert (ssizetype, constant);
1820 init_cond = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (constant),
1821 constant, type_size);
1824 DR_INIT (dr) = init_cond = ssize_int (0);;
1827 DR_OFFSET (dr) = invariant;
1829 DR_OFFSET (dr) = ssize_int (0);
1831 /* Update access function. */
1832 access_fn = DR_ACCESS_FN (dr, 0);
1833 new_step = size_binop (TRUNC_DIV_EXPR,
1834 fold_convert (ssizetype, step), type_size);
1836 access_fn = chrec_replace_initial_condition (access_fn, init_cond);
1837 access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step);
1839 VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn);
1842 if (dump_file && (dump_flags & TDF_DETAILS))
1844 struct ptr_info_def *pi = DR_PTR_INFO (dr);
1846 fprintf (dump_file, "\nCreated dr for ");
1847 print_generic_expr (dump_file, memref, TDF_SLIM);
1848 fprintf (dump_file, "\n\tbase_address: ");
1849 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
1850 fprintf (dump_file, "\n\toffset from base address: ");
1851 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
1852 fprintf (dump_file, "\n\tconstant offset from base address: ");
1853 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
1854 fprintf (dump_file, "\n\tbase_object: ");
1855 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
1856 fprintf (dump_file, "\n\tstep: ");
1857 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
1858 fprintf (dump_file, "B\n\tmisalignment from base: ");
1859 print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM);
1860 if (DR_OFFSET_MISALIGNMENT (dr))
1861 fprintf (dump_file, "B");
1862 if (DR_ALIGNED_TO (dr))
1864 fprintf (dump_file, "\n\taligned to: ");
1865 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
1867 fprintf (dump_file, "\n\tmemtag: ");
1868 print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM);
1869 fprintf (dump_file, "\n");
1870 if (pi && pi->name_mem_tag)
1872 fprintf (dump_file, "\n\tnametag: ");
1873 print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM);
1874 fprintf (dump_file, "\n");
1881 /* Returns true when all the functions of a tree_vec CHREC are the
1885 all_chrecs_equal_p (tree chrec)
1889 for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
1891 tree chrec_j = TREE_VEC_ELT (chrec, j);
1892 tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1);
1895 (integer_type_node, chrec_j, chrec_j_1)))
1901 /* Determine for each subscript in the data dependence relation DDR
1905 compute_subscript_distance (struct data_dependence_relation *ddr)
1907 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1911 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1913 tree conflicts_a, conflicts_b, difference;
1914 struct subscript *subscript;
1916 subscript = DDR_SUBSCRIPT (ddr, i);
1917 conflicts_a = SUB_CONFLICTS_IN_A (subscript);
1918 conflicts_b = SUB_CONFLICTS_IN_B (subscript);
1920 if (TREE_CODE (conflicts_a) == TREE_VEC)
1922 if (!all_chrecs_equal_p (conflicts_a))
1924 SUB_DISTANCE (subscript) = chrec_dont_know;
1928 conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
1931 if (TREE_CODE (conflicts_b) == TREE_VEC)
1933 if (!all_chrecs_equal_p (conflicts_b))
1935 SUB_DISTANCE (subscript) = chrec_dont_know;
1939 conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
1942 difference = chrec_fold_minus
1943 (integer_type_node, conflicts_b, conflicts_a);
1945 if (evolution_function_is_constant_p (difference))
1946 SUB_DISTANCE (subscript) = difference;
1949 SUB_DISTANCE (subscript) = chrec_dont_know;
1954 /* Initialize a ddr. */
1956 struct data_dependence_relation *
1957 initialize_data_dependence_relation (struct data_reference *a,
1958 struct data_reference *b)
1960 struct data_dependence_relation *res;
1964 res = xmalloc (sizeof (struct data_dependence_relation));
1968 if (a == NULL || b == NULL)
1970 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1974 /* When A and B are arrays and their dimensions differ, we directly
1975 initialize the relation to "there is no dependence": chrec_known. */
1976 if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
1977 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
1979 DDR_ARE_DEPENDENT (res) = chrec_known;
1983 /* Compare the bases of the data-refs. */
1984 if (!base_addr_differ_p (a, b, &differ_p))
1986 /* Can't determine whether the data-refs access the same memory
1988 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1993 DDR_ARE_DEPENDENT (res) = chrec_known;
1997 DDR_AFFINE_P (res) = true;
1998 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1999 DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
2000 DDR_SIZE_VECT (res) = 0;
2001 DDR_DIST_VECT (res) = NULL;
2002 DDR_DIR_VECT (res) = NULL;
2004 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
2006 struct subscript *subscript;
2008 subscript = xmalloc (sizeof (struct subscript));
2009 SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
2010 SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
2011 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
2012 SUB_DISTANCE (subscript) = chrec_dont_know;
2013 VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
2019 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
2023 finalize_ddr_dependent (struct data_dependence_relation *ddr,
2026 if (dump_file && (dump_flags & TDF_DETAILS))
2028 fprintf (dump_file, "(dependence classified: ");
2029 print_generic_expr (dump_file, chrec, 0);
2030 fprintf (dump_file, ")\n");
2033 DDR_ARE_DEPENDENT (ddr) = chrec;
2034 varray_clear (DDR_SUBSCRIPTS (ddr));
2037 /* The dependence relation DDR cannot be represented by a distance
2041 non_affine_dependence_relation (struct data_dependence_relation *ddr)
2043 if (dump_file && (dump_flags & TDF_DETAILS))
2044 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
2046 DDR_AFFINE_P (ddr) = false;
2051 /* This section contains the classic Banerjee tests. */
2053 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
2054 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
2057 ziv_subscript_p (tree chrec_a,
2060 return (evolution_function_is_constant_p (chrec_a)
2061 && evolution_function_is_constant_p (chrec_b));
2064 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
2065 variable, i.e., if the SIV (Single Index Variable) test is true. */
2068 siv_subscript_p (tree chrec_a,
2071 if ((evolution_function_is_constant_p (chrec_a)
2072 && evolution_function_is_univariate_p (chrec_b))
2073 || (evolution_function_is_constant_p (chrec_b)
2074 && evolution_function_is_univariate_p (chrec_a)))
2077 if (evolution_function_is_univariate_p (chrec_a)
2078 && evolution_function_is_univariate_p (chrec_b))
2080 switch (TREE_CODE (chrec_a))
2082 case POLYNOMIAL_CHREC:
2083 switch (TREE_CODE (chrec_b))
2085 case POLYNOMIAL_CHREC:
2086 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
2101 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
2102 *OVERLAPS_B are initialized to the functions that describe the
2103 relation between the elements accessed twice by CHREC_A and
2104 CHREC_B. For k >= 0, the following property is verified:
2106 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2109 analyze_ziv_subscript (tree chrec_a,
2113 tree *last_conflicts)
2117 if (dump_file && (dump_flags & TDF_DETAILS))
2118 fprintf (dump_file, "(analyze_ziv_subscript \n");
2120 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2122 switch (TREE_CODE (difference))
2125 if (integer_zerop (difference))
2127 /* The difference is equal to zero: the accessed index
2128 overlaps for each iteration in the loop. */
2129 *overlaps_a = integer_zero_node;
2130 *overlaps_b = integer_zero_node;
2131 *last_conflicts = chrec_dont_know;
2135 /* The accesses do not overlap. */
2136 *overlaps_a = chrec_known;
2137 *overlaps_b = chrec_known;
2138 *last_conflicts = integer_zero_node;
2143 /* We're not sure whether the indexes overlap. For the moment,
2144 conservatively answer "don't know". */
2145 *overlaps_a = chrec_dont_know;
2146 *overlaps_b = chrec_dont_know;
2147 *last_conflicts = chrec_dont_know;
2151 if (dump_file && (dump_flags & TDF_DETAILS))
2152 fprintf (dump_file, ")\n");
2155 /* Get the real or estimated number of iterations for LOOPNUM, whichever is
2156 available. Return the number of iterations as a tree, or NULL_TREE if
2160 get_number_of_iters_for_loop (int loopnum)
2162 tree numiter = number_of_iterations_in_loop (current_loops->parray[loopnum]);
2164 if (TREE_CODE (numiter) != INTEGER_CST)
2165 numiter = current_loops->parray[loopnum]->estimated_nb_iterations;
2166 if (chrec_contains_undetermined (numiter))
2171 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2172 constant, and CHREC_B is an affine function. *OVERLAPS_A and
2173 *OVERLAPS_B are initialized to the functions that describe the
2174 relation between the elements accessed twice by CHREC_A and
2175 CHREC_B. For k >= 0, the following property is verified:
2177 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2180 analyze_siv_subscript_cst_affine (tree chrec_a,
2184 tree *last_conflicts)
2186 bool value0, value1, value2;
2187 tree difference = chrec_fold_minus
2188 (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
2190 if (!chrec_is_positive (initial_condition (difference), &value0))
2192 *overlaps_a = chrec_dont_know;
2193 *overlaps_b = chrec_dont_know;
2194 *last_conflicts = chrec_dont_know;
2199 if (value0 == false)
2201 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
2203 *overlaps_a = chrec_dont_know;
2204 *overlaps_b = chrec_dont_know;
2205 *last_conflicts = chrec_dont_know;
2214 chrec_b = {10, +, 1}
2217 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2220 int loopnum = CHREC_VARIABLE (chrec_b);
2222 *overlaps_a = integer_zero_node;
2223 *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
2224 fold_build1 (ABS_EXPR,
2227 CHREC_RIGHT (chrec_b));
2228 *last_conflicts = integer_one_node;
2231 /* Perform weak-zero siv test to see if overlap is
2232 outside the loop bounds. */
2233 numiter = get_number_of_iters_for_loop (loopnum);
2235 if (numiter != NULL_TREE
2236 && TREE_CODE (*overlaps_b) == INTEGER_CST
2237 && tree_int_cst_lt (numiter, *overlaps_b))
2239 *overlaps_a = chrec_known;
2240 *overlaps_b = chrec_known;
2241 *last_conflicts = integer_zero_node;
2247 /* When the step does not divide the difference, there are
2251 *overlaps_a = chrec_known;
2252 *overlaps_b = chrec_known;
2253 *last_conflicts = integer_zero_node;
2262 chrec_b = {10, +, -1}
2264 In this case, chrec_a will not overlap with chrec_b. */
2265 *overlaps_a = chrec_known;
2266 *overlaps_b = chrec_known;
2267 *last_conflicts = integer_zero_node;
2274 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
2276 *overlaps_a = chrec_dont_know;
2277 *overlaps_b = chrec_dont_know;
2278 *last_conflicts = chrec_dont_know;
2283 if (value2 == false)
2287 chrec_b = {10, +, -1}
2289 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2292 int loopnum = CHREC_VARIABLE (chrec_b);
2294 *overlaps_a = integer_zero_node;
2295 *overlaps_b = fold_build2 (EXACT_DIV_EXPR,
2296 integer_type_node, difference,
2297 CHREC_RIGHT (chrec_b));
2298 *last_conflicts = integer_one_node;
2300 /* Perform weak-zero siv test to see if overlap is
2301 outside the loop bounds. */
2302 numiter = get_number_of_iters_for_loop (loopnum);
2304 if (numiter != NULL_TREE
2305 && TREE_CODE (*overlaps_b) == INTEGER_CST
2306 && tree_int_cst_lt (numiter, *overlaps_b))
2308 *overlaps_a = chrec_known;
2309 *overlaps_b = chrec_known;
2310 *last_conflicts = integer_zero_node;
2316 /* When the step does not divide the difference, there
2320 *overlaps_a = chrec_known;
2321 *overlaps_b = chrec_known;
2322 *last_conflicts = integer_zero_node;
2332 In this case, chrec_a will not overlap with chrec_b. */
2333 *overlaps_a = chrec_known;
2334 *overlaps_b = chrec_known;
2335 *last_conflicts = integer_zero_node;
2343 /* Helper recursive function for initializing the matrix A. Returns
2344 the initial value of CHREC. */
2347 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2351 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2352 return int_cst_value (chrec);
2354 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2355 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2358 #define FLOOR_DIV(x,y) ((x) / (y))
2360 /* Solves the special case of the Diophantine equation:
2361 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2363 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2364 number of iterations that loops X and Y run. The overlaps will be
2365 constructed as evolutions in dimension DIM. */
2368 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
2369 tree *overlaps_a, tree *overlaps_b,
2370 tree *last_conflicts, int dim)
2372 if (((step_a > 0 && step_b > 0)
2373 || (step_a < 0 && step_b < 0)))
2375 int step_overlaps_a, step_overlaps_b;
2376 int gcd_steps_a_b, last_conflict, tau2;
2378 gcd_steps_a_b = gcd (step_a, step_b);
2379 step_overlaps_a = step_b / gcd_steps_a_b;
2380 step_overlaps_b = step_a / gcd_steps_a_b;
2382 tau2 = FLOOR_DIV (niter, step_overlaps_a);
2383 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2384 last_conflict = tau2;
2386 *overlaps_a = build_polynomial_chrec
2387 (dim, integer_zero_node,
2388 build_int_cst (NULL_TREE, step_overlaps_a));
2389 *overlaps_b = build_polynomial_chrec
2390 (dim, integer_zero_node,
2391 build_int_cst (NULL_TREE, step_overlaps_b));
2392 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2397 *overlaps_a = integer_zero_node;
2398 *overlaps_b = integer_zero_node;
2399 *last_conflicts = integer_zero_node;
2404 /* Solves the special case of a Diophantine equation where CHREC_A is
2405 an affine bivariate function, and CHREC_B is an affine univariate
2406 function. For example,
2408 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2410 has the following overlapping functions:
2412 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2413 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2414 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2416 FORNOW: This is a specialized implementation for a case occurring in
2417 a common benchmark. Implement the general algorithm. */
2420 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2421 tree *overlaps_a, tree *overlaps_b,
2422 tree *last_conflicts)
2424 bool xz_p, yz_p, xyz_p;
2425 int step_x, step_y, step_z;
2426 int niter_x, niter_y, niter_z, niter;
2427 tree numiter_x, numiter_y, numiter_z;
2428 tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
2429 tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
2430 tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
2432 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2433 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2434 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2436 numiter_x = get_number_of_iters_for_loop (CHREC_VARIABLE (CHREC_LEFT (chrec_a)));
2437 numiter_y = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
2438 numiter_z = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
2440 if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
2441 || numiter_z == NULL_TREE)
2443 *overlaps_a = chrec_dont_know;
2444 *overlaps_b = chrec_dont_know;
2445 *last_conflicts = chrec_dont_know;
2449 niter_x = int_cst_value (numiter_x);
2450 niter_y = int_cst_value (numiter_y);
2451 niter_z = int_cst_value (numiter_z);
2453 niter = MIN (niter_x, niter_z);
2454 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2457 &last_conflicts_xz, 1);
2458 niter = MIN (niter_y, niter_z);
2459 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2462 &last_conflicts_yz, 2);
2463 niter = MIN (niter_x, niter_z);
2464 niter = MIN (niter_y, niter);
2465 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2468 &last_conflicts_xyz, 3);
2470 xz_p = !integer_zerop (last_conflicts_xz);
2471 yz_p = !integer_zerop (last_conflicts_yz);
2472 xyz_p = !integer_zerop (last_conflicts_xyz);
2474 if (xz_p || yz_p || xyz_p)
2476 *overlaps_a = make_tree_vec (2);
2477 TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
2478 TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
2479 *overlaps_b = integer_zero_node;
2482 TREE_VEC_ELT (*overlaps_a, 0) =
2483 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
2486 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
2487 *last_conflicts = last_conflicts_xz;
2491 TREE_VEC_ELT (*overlaps_a, 1) =
2492 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
2495 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
2496 *last_conflicts = last_conflicts_yz;
2500 TREE_VEC_ELT (*overlaps_a, 0) =
2501 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
2503 TREE_VEC_ELT (*overlaps_a, 1) =
2504 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
2507 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
2508 *last_conflicts = last_conflicts_xyz;
2513 *overlaps_a = integer_zero_node;
2514 *overlaps_b = integer_zero_node;
2515 *last_conflicts = integer_zero_node;
2519 /* Determines the overlapping elements due to accesses CHREC_A and
2520 CHREC_B, that are affine functions. This is a part of the
2521 subscript analyzer. */
2524 analyze_subscript_affine_affine (tree chrec_a,
2528 tree *last_conflicts)
2530 unsigned nb_vars_a, nb_vars_b, dim;
2531 int init_a, init_b, gamma, gcd_alpha_beta;
2533 lambda_matrix A, U, S;
2534 tree difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2536 if (integer_zerop (difference))
2538 /* The difference is equal to zero: the accessed index
2539 overlaps for each iteration in the loop. */
2540 *overlaps_a = integer_zero_node;
2541 *overlaps_b = integer_zero_node;
2542 *last_conflicts = chrec_dont_know;
2545 if (dump_file && (dump_flags & TDF_DETAILS))
2546 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2548 /* For determining the initial intersection, we have to solve a
2549 Diophantine equation. This is the most time consuming part.
2551 For answering to the question: "Is there a dependence?" we have
2552 to prove that there exists a solution to the Diophantine
2553 equation, and that the solution is in the iteration domain,
2554 i.e. the solution is positive or zero, and that the solution
2555 happens before the upper bound loop.nb_iterations. Otherwise
2556 there is no dependence. This function outputs a description of
2557 the iterations that hold the intersections. */
2560 nb_vars_a = nb_vars_in_chrec (chrec_a);
2561 nb_vars_b = nb_vars_in_chrec (chrec_b);
2563 dim = nb_vars_a + nb_vars_b;
2564 U = lambda_matrix_new (dim, dim);
2565 A = lambda_matrix_new (dim, 1);
2566 S = lambda_matrix_new (dim, 1);
2568 init_a = initialize_matrix_A (A, chrec_a, 0, 1);
2569 init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
2570 gamma = init_b - init_a;
2572 /* Don't do all the hard work of solving the Diophantine equation
2573 when we already know the solution: for example,
2576 | gamma = 3 - 3 = 0.
2577 Then the first overlap occurs during the first iterations:
2578 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2582 if (nb_vars_a == 1 && nb_vars_b == 1)
2585 int niter, niter_a, niter_b;
2586 tree numiter_a, numiter_b;
2588 numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
2589 numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
2590 if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
2592 *overlaps_a = chrec_dont_know;
2593 *overlaps_b = chrec_dont_know;
2594 *last_conflicts = chrec_dont_know;
2598 niter_a = int_cst_value (numiter_a);
2599 niter_b = int_cst_value (numiter_b);
2600 niter = MIN (niter_a, niter_b);
2602 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2603 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2605 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2606 overlaps_a, overlaps_b,
2610 else if (nb_vars_a == 2 && nb_vars_b == 1)
2611 compute_overlap_steps_for_affine_1_2
2612 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2614 else if (nb_vars_a == 1 && nb_vars_b == 2)
2615 compute_overlap_steps_for_affine_1_2
2616 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2620 *overlaps_a = chrec_dont_know;
2621 *overlaps_b = chrec_dont_know;
2622 *last_conflicts = chrec_dont_know;
2628 lambda_matrix_right_hermite (A, dim, 1, S, U);
2633 lambda_matrix_row_negate (U, dim, 0);
2635 gcd_alpha_beta = S[0][0];
2637 /* The classic "gcd-test". */
2638 if (!int_divides_p (gcd_alpha_beta, gamma))
2640 /* The "gcd-test" has determined that there is no integer
2641 solution, i.e. there is no dependence. */
2642 *overlaps_a = chrec_known;
2643 *overlaps_b = chrec_known;
2644 *last_conflicts = integer_zero_node;
2647 /* Both access functions are univariate. This includes SIV and MIV cases. */
2648 else if (nb_vars_a == 1 && nb_vars_b == 1)
2650 /* Both functions should have the same evolution sign. */
2651 if (((A[0][0] > 0 && -A[1][0] > 0)
2652 || (A[0][0] < 0 && -A[1][0] < 0)))
2654 /* The solutions are given by:
2656 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2659 For a given integer t. Using the following variables,
2661 | i0 = u11 * gamma / gcd_alpha_beta
2662 | j0 = u12 * gamma / gcd_alpha_beta
2669 | y0 = j0 + j1 * t. */
2673 /* X0 and Y0 are the first iterations for which there is a
2674 dependence. X0, Y0 are two solutions of the Diophantine
2675 equation: chrec_a (X0) = chrec_b (Y0). */
2677 int niter, niter_a, niter_b;
2678 tree numiter_a, numiter_b;
2680 numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
2681 numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
2683 if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
2685 *overlaps_a = chrec_dont_know;
2686 *overlaps_b = chrec_dont_know;
2687 *last_conflicts = chrec_dont_know;
2691 niter_a = int_cst_value (numiter_a);
2692 niter_b = int_cst_value (numiter_b);
2693 niter = MIN (niter_a, niter_b);
2695 i0 = U[0][0] * gamma / gcd_alpha_beta;
2696 j0 = U[0][1] * gamma / gcd_alpha_beta;
2700 if ((i1 == 0 && i0 < 0)
2701 || (j1 == 0 && j0 < 0))
2703 /* There is no solution.
2704 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2705 falls in here, but for the moment we don't look at the
2706 upper bound of the iteration domain. */
2707 *overlaps_a = chrec_known;
2708 *overlaps_b = chrec_known;
2709 *last_conflicts = integer_zero_node;
2716 tau1 = CEIL (-i0, i1);
2717 tau2 = FLOOR_DIV (niter - i0, i1);
2721 int last_conflict, min_multiple;
2722 tau1 = MAX (tau1, CEIL (-j0, j1));
2723 tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
2725 x0 = i1 * tau1 + i0;
2726 y0 = j1 * tau1 + j0;
2728 /* At this point (x0, y0) is one of the
2729 solutions to the Diophantine equation. The
2730 next step has to compute the smallest
2731 positive solution: the first conflicts. */
2732 min_multiple = MIN (x0 / i1, y0 / j1);
2733 x0 -= i1 * min_multiple;
2734 y0 -= j1 * min_multiple;
2736 tau1 = (x0 - i0)/i1;
2737 last_conflict = tau2 - tau1;
2739 /* If the overlap occurs outside of the bounds of the
2740 loop, there is no dependence. */
2741 if (x0 > niter || y0 > niter)
2744 *overlaps_a = chrec_known;
2745 *overlaps_b = chrec_known;
2746 *last_conflicts = integer_zero_node;
2750 *overlaps_a = build_polynomial_chrec
2752 build_int_cst (NULL_TREE, x0),
2753 build_int_cst (NULL_TREE, i1));
2754 *overlaps_b = build_polynomial_chrec
2756 build_int_cst (NULL_TREE, y0),
2757 build_int_cst (NULL_TREE, j1));
2758 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2763 /* FIXME: For the moment, the upper bound of the
2764 iteration domain for j is not checked. */
2765 *overlaps_a = chrec_dont_know;
2766 *overlaps_b = chrec_dont_know;
2767 *last_conflicts = chrec_dont_know;
2773 /* FIXME: For the moment, the upper bound of the
2774 iteration domain for i is not checked. */
2775 *overlaps_a = chrec_dont_know;
2776 *overlaps_b = chrec_dont_know;
2777 *last_conflicts = chrec_dont_know;
2783 *overlaps_a = chrec_dont_know;
2784 *overlaps_b = chrec_dont_know;
2785 *last_conflicts = chrec_dont_know;
2791 *overlaps_a = chrec_dont_know;
2792 *overlaps_b = chrec_dont_know;
2793 *last_conflicts = chrec_dont_know;
2797 if (dump_file && (dump_flags & TDF_DETAILS))
2799 fprintf (dump_file, " (overlaps_a = ");
2800 print_generic_expr (dump_file, *overlaps_a, 0);
2801 fprintf (dump_file, ")\n (overlaps_b = ");
2802 print_generic_expr (dump_file, *overlaps_b, 0);
2803 fprintf (dump_file, ")\n");
2806 if (dump_file && (dump_flags & TDF_DETAILS))
2807 fprintf (dump_file, ")\n");
2810 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2811 *OVERLAPS_B are initialized to the functions that describe the
2812 relation between the elements accessed twice by CHREC_A and
2813 CHREC_B. For k >= 0, the following property is verified:
2815 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2818 analyze_siv_subscript (tree chrec_a,
2822 tree *last_conflicts)
2824 if (dump_file && (dump_flags & TDF_DETAILS))
2825 fprintf (dump_file, "(analyze_siv_subscript \n");
2827 if (evolution_function_is_constant_p (chrec_a)
2828 && evolution_function_is_affine_p (chrec_b))
2829 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
2830 overlaps_a, overlaps_b, last_conflicts);
2832 else if (evolution_function_is_affine_p (chrec_a)
2833 && evolution_function_is_constant_p (chrec_b))
2834 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2835 overlaps_b, overlaps_a, last_conflicts);
2837 else if (evolution_function_is_affine_p (chrec_a)
2838 && evolution_function_is_affine_p (chrec_b))
2839 analyze_subscript_affine_affine (chrec_a, chrec_b,
2840 overlaps_a, overlaps_b, last_conflicts);
2843 *overlaps_a = chrec_dont_know;
2844 *overlaps_b = chrec_dont_know;
2845 *last_conflicts = chrec_dont_know;
2848 if (dump_file && (dump_flags & TDF_DETAILS))
2849 fprintf (dump_file, ")\n");
2852 /* Return true when the evolution steps of an affine CHREC divide the
2856 chrec_steps_divide_constant_p (tree chrec,
2859 switch (TREE_CODE (chrec))
2861 case POLYNOMIAL_CHREC:
2862 return (tree_fold_divides_p (CHREC_RIGHT (chrec), cst)
2863 && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
2866 /* On the initial condition, return true. */
2871 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
2872 *OVERLAPS_B are initialized to the functions that describe the
2873 relation between the elements accessed twice by CHREC_A and
2874 CHREC_B. For k >= 0, the following property is verified:
2876 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2879 analyze_miv_subscript (tree chrec_a,
2883 tree *last_conflicts)
2885 /* FIXME: This is a MIV subscript, not yet handled.
2886 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2889 In the SIV test we had to solve a Diophantine equation with two
2890 variables. In the MIV case we have to solve a Diophantine
2891 equation with 2*n variables (if the subscript uses n IVs).
2895 if (dump_file && (dump_flags & TDF_DETAILS))
2896 fprintf (dump_file, "(analyze_miv_subscript \n");
2898 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2900 if (chrec_zerop (difference))
2902 /* Access functions are the same: all the elements are accessed
2903 in the same order. */
2904 *overlaps_a = integer_zero_node;
2905 *overlaps_b = integer_zero_node;
2906 *last_conflicts = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
2910 else if (evolution_function_is_constant_p (difference)
2911 /* For the moment, the following is verified:
2912 evolution_function_is_affine_multivariate_p (chrec_a) */
2913 && !chrec_steps_divide_constant_p (chrec_a, difference))
2915 /* testsuite/.../ssa-chrec-33.c
2916 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2918 The difference is 1, and the evolution steps are equal to 2,
2919 consequently there are no overlapping elements. */
2920 *overlaps_a = chrec_known;
2921 *overlaps_b = chrec_known;
2922 *last_conflicts = integer_zero_node;
2925 else if (evolution_function_is_affine_multivariate_p (chrec_a)
2926 && evolution_function_is_affine_multivariate_p (chrec_b))
2928 /* testsuite/.../ssa-chrec-35.c
2929 {0, +, 1}_2 vs. {0, +, 1}_3
2930 the overlapping elements are respectively located at iterations:
2931 {0, +, 1}_x and {0, +, 1}_x,
2932 in other words, we have the equality:
2933 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2936 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2937 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2939 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2940 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2942 analyze_subscript_affine_affine (chrec_a, chrec_b,
2943 overlaps_a, overlaps_b, last_conflicts);
2948 /* When the analysis is too difficult, answer "don't know". */
2949 *overlaps_a = chrec_dont_know;
2950 *overlaps_b = chrec_dont_know;
2951 *last_conflicts = chrec_dont_know;
2954 if (dump_file && (dump_flags & TDF_DETAILS))
2955 fprintf (dump_file, ")\n");
2958 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
2959 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
2960 two functions that describe the iterations that contain conflicting
2963 Remark: For an integer k >= 0, the following equality is true:
2965 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2969 analyze_overlapping_iterations (tree chrec_a,
2971 tree *overlap_iterations_a,
2972 tree *overlap_iterations_b,
2973 tree *last_conflicts)
2975 if (dump_file && (dump_flags & TDF_DETAILS))
2977 fprintf (dump_file, "(analyze_overlapping_iterations \n");
2978 fprintf (dump_file, " (chrec_a = ");
2979 print_generic_expr (dump_file, chrec_a, 0);
2980 fprintf (dump_file, ")\n chrec_b = ");
2981 print_generic_expr (dump_file, chrec_b, 0);
2982 fprintf (dump_file, ")\n");
2985 if (chrec_a == NULL_TREE
2986 || chrec_b == NULL_TREE
2987 || chrec_contains_undetermined (chrec_a)
2988 || chrec_contains_undetermined (chrec_b)
2989 || chrec_contains_symbols (chrec_a)
2990 || chrec_contains_symbols (chrec_b))
2992 *overlap_iterations_a = chrec_dont_know;
2993 *overlap_iterations_b = chrec_dont_know;
2996 else if (ziv_subscript_p (chrec_a, chrec_b))
2997 analyze_ziv_subscript (chrec_a, chrec_b,
2998 overlap_iterations_a, overlap_iterations_b,
3001 else if (siv_subscript_p (chrec_a, chrec_b))
3002 analyze_siv_subscript (chrec_a, chrec_b,
3003 overlap_iterations_a, overlap_iterations_b,
3007 analyze_miv_subscript (chrec_a, chrec_b,
3008 overlap_iterations_a, overlap_iterations_b,
3011 if (dump_file && (dump_flags & TDF_DETAILS))
3013 fprintf (dump_file, " (overlap_iterations_a = ");
3014 print_generic_expr (dump_file, *overlap_iterations_a, 0);
3015 fprintf (dump_file, ")\n (overlap_iterations_b = ");
3016 print_generic_expr (dump_file, *overlap_iterations_b, 0);
3017 fprintf (dump_file, ")\n");
3023 /* This section contains the affine functions dependences detector. */
3025 /* Computes the conflicting iterations, and initialize DDR. */
3028 subscript_dependence_tester (struct data_dependence_relation *ddr)
3031 struct data_reference *dra = DDR_A (ddr);
3032 struct data_reference *drb = DDR_B (ddr);
3033 tree last_conflicts;
3035 if (dump_file && (dump_flags & TDF_DETAILS))
3036 fprintf (dump_file, "(subscript_dependence_tester \n");
3038 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3040 tree overlaps_a, overlaps_b;
3041 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3043 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
3044 DR_ACCESS_FN (drb, i),
3045 &overlaps_a, &overlaps_b,
3048 if (chrec_contains_undetermined (overlaps_a)
3049 || chrec_contains_undetermined (overlaps_b))
3051 finalize_ddr_dependent (ddr, chrec_dont_know);
3055 else if (overlaps_a == chrec_known
3056 || overlaps_b == chrec_known)
3058 finalize_ddr_dependent (ddr, chrec_known);
3064 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3065 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3066 SUB_LAST_CONFLICT (subscript) = last_conflicts;
3070 if (dump_file && (dump_flags & TDF_DETAILS))
3071 fprintf (dump_file, ")\n");
3074 /* Compute the classic per loop distance vector.
3076 DDR is the data dependence relation to build a vector from.
3077 NB_LOOPS is the total number of loops we are considering.
3078 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
3080 Return FALSE when fail to represent the data dependence as a distance
3082 Return TRUE otherwise. */
3085 build_classic_dist_vector (struct data_dependence_relation *ddr,
3086 int nb_loops, int first_loop_depth)
3089 lambda_vector dist_v, init_v;
3091 dist_v = lambda_vector_new (nb_loops);
3092 init_v = lambda_vector_new (nb_loops);
3093 lambda_vector_clear (dist_v, nb_loops);
3094 lambda_vector_clear (init_v, nb_loops);
3096 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3099 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3101 tree access_fn_a, access_fn_b;
3102 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3104 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3106 non_affine_dependence_relation (ddr);
3110 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
3111 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
3113 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3114 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3116 int dist, loop_nb, loop_depth;
3117 int loop_nb_a = CHREC_VARIABLE (access_fn_a);
3118 int loop_nb_b = CHREC_VARIABLE (access_fn_b);
3119 struct loop *loop_a = current_loops->parray[loop_nb_a];
3120 struct loop *loop_b = current_loops->parray[loop_nb_b];
3122 /* If the loop for either variable is at a lower depth than
3123 the first_loop's depth, then we can't possibly have a
3124 dependency at this level of the loop. */
3126 if (loop_a->depth < first_loop_depth
3127 || loop_b->depth < first_loop_depth)
3130 if (loop_nb_a != loop_nb_b
3131 && !flow_loop_nested_p (loop_a, loop_b)
3132 && !flow_loop_nested_p (loop_b, loop_a))
3134 /* Example: when there are two consecutive loops,
3143 the dependence relation cannot be captured by the
3144 distance abstraction. */
3145 non_affine_dependence_relation (ddr);
3149 /* The dependence is carried by the outermost loop. Example:
3156 In this case, the dependence is carried by loop_1. */
3157 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
3158 loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
3160 /* If the loop number is still greater than the number of
3161 loops we've been asked to analyze, or negative,
3162 something is borked. */
3163 gcc_assert (loop_depth >= 0);
3164 gcc_assert (loop_depth < nb_loops);
3165 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3167 non_affine_dependence_relation (ddr);
3171 dist = int_cst_value (SUB_DISTANCE (subscript));
3173 /* This is the subscript coupling test.
3178 There is no dependence. */
3179 if (init_v[loop_depth] != 0
3180 && dist_v[loop_depth] != dist)
3182 finalize_ddr_dependent (ddr, chrec_known);
3186 dist_v[loop_depth] = dist;
3187 init_v[loop_depth] = 1;
3191 /* There is a distance of 1 on all the outer loops:
3193 Example: there is a dependence of distance 1 on loop_1 for the array A.
3199 struct loop *lca, *loop_a, *loop_b;
3200 struct data_reference *a = DDR_A (ddr);
3201 struct data_reference *b = DDR_B (ddr);
3203 loop_a = loop_containing_stmt (DR_STMT (a));
3204 loop_b = loop_containing_stmt (DR_STMT (b));
3206 /* Get the common ancestor loop. */
3207 lca = find_common_loop (loop_a, loop_b);
3209 lca_depth = lca->depth;
3210 lca_depth -= first_loop_depth;
3211 gcc_assert (lca_depth >= 0);
3212 gcc_assert (lca_depth < nb_loops);
3214 /* For each outer loop where init_v is not set, the accesses are
3215 in dependence of distance 1 in the loop. */
3218 && init_v[lca_depth] == 0)
3219 dist_v[lca_depth] = 1;
3225 lca_depth = lca->depth - first_loop_depth;
3226 while (lca->depth != 0)
3228 /* If we're considering just a sub-nest, then don't record
3229 any information on the outer loops. */
3233 gcc_assert (lca_depth < nb_loops);
3235 if (init_v[lca_depth] == 0)
3236 dist_v[lca_depth] = 1;
3238 lca_depth = lca->depth - first_loop_depth;
3244 DDR_DIST_VECT (ddr) = dist_v;
3245 DDR_SIZE_VECT (ddr) = nb_loops;
3247 /* Verify a basic constraint: classic distance vectors should always
3248 be lexicographically positive. */
3249 if (!lambda_vector_lexico_pos (DDR_DIST_VECT (ddr),
3250 DDR_SIZE_VECT (ddr)))
3252 if (DDR_SIZE_VECT (ddr) == 1)
3253 /* This one is simple to fix, and can be fixed.
3254 Multidimensional arrays cannot be fixed that simply. */
3255 lambda_vector_negate (DDR_DIST_VECT (ddr), DDR_DIST_VECT (ddr),
3256 DDR_SIZE_VECT (ddr));
3258 /* This is not valid: we need the delta test for properly
3266 /* Compute the classic per loop direction vector.
3268 DDR is the data dependence relation to build a vector from.
3269 NB_LOOPS is the total number of loops we are considering.
3270 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
3272 Return FALSE if the dependence relation is outside of the loop nest
3273 at FIRST_LOOP_DEPTH.
3274 Return TRUE otherwise. */
3277 build_classic_dir_vector (struct data_dependence_relation *ddr,
3278 int nb_loops, int first_loop_depth)
3281 lambda_vector dir_v, init_v;
3283 dir_v = lambda_vector_new (nb_loops);
3284 init_v = lambda_vector_new (nb_loops);
3285 lambda_vector_clear (dir_v, nb_loops);
3286 lambda_vector_clear (init_v, nb_loops);
3288 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3291 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3293 tree access_fn_a, access_fn_b;
3294 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3296 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3298 non_affine_dependence_relation (ddr);
3302 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
3303 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
3304 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3305 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3307 int dist, loop_nb, loop_depth;
3308 enum data_dependence_direction dir = dir_star;
3309 int loop_nb_a = CHREC_VARIABLE (access_fn_a);
3310 int loop_nb_b = CHREC_VARIABLE (access_fn_b);
3311 struct loop *loop_a = current_loops->parray[loop_nb_a];
3312 struct loop *loop_b = current_loops->parray[loop_nb_b];
3314 /* If the loop for either variable is at a lower depth than
3315 the first_loop's depth, then we can't possibly have a
3316 dependency at this level of the loop. */
3318 if (loop_a->depth < first_loop_depth
3319 || loop_b->depth < first_loop_depth)
3322 if (loop_nb_a != loop_nb_b
3323 && !flow_loop_nested_p (loop_a, loop_b)
3324 && !flow_loop_nested_p (loop_b, loop_a))
3326 /* Example: when there are two consecutive loops,
3335 the dependence relation cannot be captured by the
3336 distance abstraction. */
3337 non_affine_dependence_relation (ddr);
3341 /* The dependence is carried by the outermost loop. Example:
3348 In this case, the dependence is carried by loop_1. */
3349 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
3350 loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
3352 /* If the loop number is still greater than the number of
3353 loops we've been asked to analyze, or negative,
3354 something is borked. */
3355 gcc_assert (loop_depth >= 0);
3356 gcc_assert (loop_depth < nb_loops);
3358 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3360 non_affine_dependence_relation (ddr);
3364 dist = int_cst_value (SUB_DISTANCE (subscript));
3373 /* This is the subscript coupling test.
3378 There is no dependence. */
3379 if (init_v[loop_depth] != 0
3381 && (enum data_dependence_direction) dir_v[loop_depth] != dir
3382 && (enum data_dependence_direction) dir_v[loop_depth] != dir_star)
3384 finalize_ddr_dependent (ddr, chrec_known);
3388 dir_v[loop_depth] = dir;
3389 init_v[loop_depth] = 1;
3393 /* There is a distance of 1 on all the outer loops:
3395 Example: there is a dependence of distance 1 on loop_1 for the array A.
3401 struct loop *lca, *loop_a, *loop_b;
3402 struct data_reference *a = DDR_A (ddr);
3403 struct data_reference *b = DDR_B (ddr);
3405 loop_a = loop_containing_stmt (DR_STMT (a));
3406 loop_b = loop_containing_stmt (DR_STMT (b));
3408 /* Get the common ancestor loop. */
3409 lca = find_common_loop (loop_a, loop_b);
3410 lca_depth = lca->depth - first_loop_depth;
3412 gcc_assert (lca_depth >= 0);
3413 gcc_assert (lca_depth < nb_loops);
3415 /* For each outer loop where init_v is not set, the accesses are
3416 in dependence of distance 1 in the loop. */
3419 && init_v[lca_depth] == 0)
3420 dir_v[lca_depth] = dir_positive;
3425 lca_depth = lca->depth - first_loop_depth;
3426 while (lca->depth != 0)
3428 /* If we're considering just a sub-nest, then don't record
3429 any information on the outer loops. */
3433 gcc_assert (lca_depth < nb_loops);
3435 if (init_v[lca_depth] == 0)
3436 dir_v[lca_depth] = dir_positive;
3438 lca_depth = lca->depth - first_loop_depth;
3444 DDR_DIR_VECT (ddr) = dir_v;
3445 DDR_SIZE_VECT (ddr) = nb_loops;
3449 /* Returns true when all the access functions of A are affine or
3453 access_functions_are_affine_or_constant_p (struct data_reference *a)
3456 VEC(tree,heap) **fns = DR_ACCESS_FNS_ADDR (a);
3459 for (i = 0; VEC_iterate (tree, *fns, i, t); i++)
3460 if (!evolution_function_is_constant_p (t)
3461 && !evolution_function_is_affine_multivariate_p (t))
3467 /* This computes the affine dependence relation between A and B.
3468 CHREC_KNOWN is used for representing the independence between two
3469 accesses, while CHREC_DONT_KNOW is used for representing the unknown
3472 Note that it is possible to stop the computation of the dependence
3473 relation the first time we detect a CHREC_KNOWN element for a given
3477 compute_affine_dependence (struct data_dependence_relation *ddr)
3479 struct data_reference *dra = DDR_A (ddr);
3480 struct data_reference *drb = DDR_B (ddr);
3482 if (dump_file && (dump_flags & TDF_DETAILS))
3484 fprintf (dump_file, "(compute_affine_dependence\n");
3485 fprintf (dump_file, " (stmt_a = \n");
3486 print_generic_expr (dump_file, DR_STMT (dra), 0);
3487 fprintf (dump_file, ")\n (stmt_b = \n");
3488 print_generic_expr (dump_file, DR_STMT (drb), 0);
3489 fprintf (dump_file, ")\n");
3492 /* Analyze only when the dependence relation is not yet known. */
3493 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3495 if (access_functions_are_affine_or_constant_p (dra)
3496 && access_functions_are_affine_or_constant_p (drb))
3497 subscript_dependence_tester (ddr);
3499 /* As a last case, if the dependence cannot be determined, or if
3500 the dependence is considered too difficult to determine, answer
3503 finalize_ddr_dependent (ddr, chrec_dont_know);
3506 if (dump_file && (dump_flags & TDF_DETAILS))
3507 fprintf (dump_file, ")\n");
3510 /* This computes the dependence relation for the same data
3511 reference into DDR. */
3514 compute_self_dependence (struct data_dependence_relation *ddr)
3518 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3520 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3522 /* The accessed index overlaps for each iteration. */
3523 SUB_CONFLICTS_IN_A (subscript) = integer_zero_node;
3524 SUB_CONFLICTS_IN_B (subscript) = integer_zero_node;
3525 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3530 typedef struct data_dependence_relation *ddr_p;
3532 DEF_VEC_ALLOC_P(ddr_p,heap);
3534 /* Compute a subset of the data dependence relation graph. Don't
3535 compute read-read and self relations if
3536 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is FALSE, and avoid the computation
3537 of the opposite relation, i.e. when AB has been computed, don't compute BA.
3538 DATAREFS contains a list of data references, and the result is set
3539 in DEPENDENCE_RELATIONS. */
3542 compute_all_dependences (varray_type datarefs,
3543 bool compute_self_and_read_read_dependences,
3544 VEC(ddr_p,heap) **dependence_relations)
3546 unsigned int i, j, N;
3548 N = VARRAY_ACTIVE_SIZE (datarefs);
3550 /* Note that we specifically skip i == j because it's a self dependence, and
3551 use compute_self_dependence below. */
3553 for (i = 0; i < N; i++)
3554 for (j = i + 1; j < N; j++)
3556 struct data_reference *a, *b;
3557 struct data_dependence_relation *ddr;
3559 a = VARRAY_GENERIC_PTR (datarefs, i);
3560 b = VARRAY_GENERIC_PTR (datarefs, j);
3561 if (DR_IS_READ (a) && DR_IS_READ (b)
3562 && !compute_self_and_read_read_dependences)
3564 ddr = initialize_data_dependence_relation (a, b);
3566 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3567 compute_affine_dependence (ddr);
3568 compute_subscript_distance (ddr);
3570 if (!compute_self_and_read_read_dependences)
3573 /* Compute self dependence relation of each dataref to itself. */
3575 for (i = 0; i < N; i++)
3577 struct data_reference *a, *b;
3578 struct data_dependence_relation *ddr;
3580 a = VARRAY_GENERIC_PTR (datarefs, i);
3581 b = VARRAY_GENERIC_PTR (datarefs, i);
3582 ddr = initialize_data_dependence_relation (a, b);
3584 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3585 compute_self_dependence (ddr);
3586 compute_subscript_distance (ddr);
3590 /* Search the data references in LOOP, and record the information into
3591 DATAREFS. Returns chrec_dont_know when failing to analyze a
3592 difficult case, returns NULL_TREE otherwise.
3594 TODO: This function should be made smarter so that it can handle address
3595 arithmetic as if they were array accesses, etc. */
3598 find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
3600 basic_block bb, *bbs;
3602 block_stmt_iterator bsi;
3603 struct data_reference *dr;
3605 bbs = get_loop_body (loop);
3607 for (i = 0; i < loop->num_nodes; i++)
3611 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3613 tree stmt = bsi_stmt (bsi);
3615 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
3616 Calls have side-effects, except those to const or pure
3618 if ((TREE_CODE (stmt) == CALL_EXPR
3619 && !(call_expr_flags (stmt) & (ECF_CONST | ECF_PURE)))
3620 || (TREE_CODE (stmt) == ASM_EXPR
3621 && ASM_VOLATILE_P (stmt)))
3622 goto insert_dont_know_node;
3624 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3627 switch (TREE_CODE (stmt))
3631 bool one_inserted = false;
3632 tree opnd0 = TREE_OPERAND (stmt, 0);
3633 tree opnd1 = TREE_OPERAND (stmt, 1);
3635 if (TREE_CODE (opnd0) == ARRAY_REF
3636 || TREE_CODE (opnd0) == INDIRECT_REF)
3638 dr = create_data_ref (opnd0, stmt, false);
3641 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3642 one_inserted = true;
3646 if (TREE_CODE (opnd1) == ARRAY_REF
3647 || TREE_CODE (opnd1) == INDIRECT_REF)
3649 dr = create_data_ref (opnd1, stmt, true);
3652 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3653 one_inserted = true;
3658 goto insert_dont_know_node;
3666 bool one_inserted = false;
3668 for (args = TREE_OPERAND (stmt, 1); args;
3669 args = TREE_CHAIN (args))
3670 if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
3671 || TREE_CODE (TREE_VALUE (args)) == INDIRECT_REF)
3673 dr = create_data_ref (TREE_VALUE (args), stmt, true);
3676 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3677 one_inserted = true;
3682 goto insert_dont_know_node;
3689 struct data_reference *res;
3691 insert_dont_know_node:;
3692 res = xmalloc (sizeof (struct data_reference));
3693 DR_STMT (res) = NULL_TREE;
3694 DR_REF (res) = NULL_TREE;
3695 DR_BASE_OBJECT (res) = NULL;
3696 DR_TYPE (res) = ARRAY_REF_TYPE;
3697 DR_SET_ACCESS_FNS (res, NULL);
3698 DR_BASE_OBJECT (res) = NULL;
3699 DR_IS_READ (res) = false;
3700 DR_BASE_ADDRESS (res) = NULL_TREE;
3701 DR_OFFSET (res) = NULL_TREE;
3702 DR_INIT (res) = NULL_TREE;
3703 DR_STEP (res) = NULL_TREE;
3704 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
3705 DR_MEMTAG (res) = NULL_TREE;
3706 DR_PTR_INFO (res) = NULL;
3707 VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
3710 return chrec_dont_know;
3714 /* When there are no defs in the loop, the loop is parallel. */
3715 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
3716 loop->parallel_p = false;
3727 /* This section contains all the entry points. */
3729 /* Given a loop nest LOOP, the following vectors are returned:
3730 *DATAREFS is initialized to all the array elements contained in this loop,
3731 *DEPENDENCE_RELATIONS contains the relations between the data references.
3732 Compute read-read and self relations if
3733 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
3736 compute_data_dependences_for_loop (struct loop *loop,
3737 bool compute_self_and_read_read_dependences,
3738 varray_type *datarefs,
3739 varray_type *dependence_relations)
3741 unsigned int i, nb_loops;
3742 VEC(ddr_p,heap) *allrelations;
3743 struct data_dependence_relation *ddr;
3744 struct loop *loop_nest = loop;
3746 while (loop_nest && loop_nest->outer && loop_nest->outer->outer)
3747 loop_nest = loop_nest->outer;
3749 nb_loops = loop_nest->level;
3751 /* If one of the data references is not computable, give up without
3752 spending time to compute other dependences. */
3753 if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
3755 struct data_dependence_relation *ddr;
3757 /* Insert a single relation into dependence_relations:
3759 ddr = initialize_data_dependence_relation (NULL, NULL);
3760 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
3761 build_classic_dist_vector (ddr, nb_loops, loop->depth);
3762 build_classic_dir_vector (ddr, nb_loops, loop->depth);
3766 allrelations = NULL;
3767 compute_all_dependences (*datarefs, compute_self_and_read_read_dependences,
3770 for (i = 0; VEC_iterate (ddr_p, allrelations, i, ddr); i++)
3772 if (build_classic_dist_vector (ddr, nb_loops, loop_nest->depth))
3774 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
3775 build_classic_dir_vector (ddr, nb_loops, loop_nest->depth);
3780 /* Entry point (for testing only). Analyze all the data references
3781 and the dependence relations.
3783 The data references are computed first.
3785 A relation on these nodes is represented by a complete graph. Some
3786 of the relations could be of no interest, thus the relations can be
3789 In the following function we compute all the relations. This is
3790 just a first implementation that is here for:
3791 - for showing how to ask for the dependence relations,
3792 - for the debugging the whole dependence graph,
3793 - for the dejagnu testcases and maintenance.
3795 It is possible to ask only for a part of the graph, avoiding to
3796 compute the whole dependence graph. The computed dependences are
3797 stored in a knowledge base (KB) such that later queries don't
3798 recompute the same information. The implementation of this KB is
3799 transparent to the optimizer, and thus the KB can be changed with a
3800 more efficient implementation, or the KB could be disabled. */
3803 analyze_all_data_dependences (struct loops *loops)
3806 varray_type datarefs;
3807 varray_type dependence_relations;
3808 int nb_data_refs = 10;
3810 VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
3811 VARRAY_GENERIC_PTR_INIT (dependence_relations,
3812 nb_data_refs * nb_data_refs,
3813 "dependence_relations");
3815 /* Compute DDs on the whole function. */
3816 compute_data_dependences_for_loop (loops->parray[0], false,
3817 &datarefs, &dependence_relations);
3821 dump_data_dependence_relations (dump_file, dependence_relations);
3822 fprintf (dump_file, "\n\n");
3824 if (dump_flags & TDF_DETAILS)
3825 dump_dist_dir_vectors (dump_file, dependence_relations);
3827 if (dump_flags & TDF_STATS)
3829 unsigned nb_top_relations = 0;
3830 unsigned nb_bot_relations = 0;
3831 unsigned nb_basename_differ = 0;
3832 unsigned nb_chrec_relations = 0;
3834 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
3836 struct data_dependence_relation *ddr;
3837 ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
3839 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
3842 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
3844 struct data_reference *a = DDR_A (ddr);
3845 struct data_reference *b = DDR_B (ddr);
3848 if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
3849 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
3850 || (base_object_differ_p (a, b, &differ_p)
3852 nb_basename_differ++;
3858 nb_chrec_relations++;
3861 gather_stats_on_scev_database ();
3865 free_dependence_relations (dependence_relations);
3866 free_data_refs (datarefs);
3869 /* Free the memory used by a data dependence relation DDR. */
3872 free_dependence_relation (struct data_dependence_relation *ddr)
3877 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
3878 varray_clear (DDR_SUBSCRIPTS (ddr));
3882 /* Free the memory used by the data dependence relations from
3883 DEPENDENCE_RELATIONS. */
3886 free_dependence_relations (varray_type dependence_relations)
3889 if (dependence_relations == NULL)
3892 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
3893 free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
3894 varray_clear (dependence_relations);
3897 /* Free the memory used by the data references from DATAREFS. */
3900 free_data_refs (varray_type datarefs)
3904 if (datarefs == NULL)
3907 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
3909 struct data_reference *dr = (struct data_reference *)
3910 VARRAY_GENERIC_PTR (datarefs, i);
3913 DR_FREE_ACCESS_FNS (dr);
3917 varray_clear (datarefs);