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 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2156 constant, and CHREC_B is an affine function. *OVERLAPS_A and
2157 *OVERLAPS_B are initialized to the functions that describe the
2158 relation between the elements accessed twice by CHREC_A and
2159 CHREC_B. For k >= 0, the following property is verified:
2161 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2164 analyze_siv_subscript_cst_affine (tree chrec_a,
2168 tree *last_conflicts)
2170 bool value0, value1, value2;
2171 tree difference = chrec_fold_minus
2172 (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
2174 if (!chrec_is_positive (initial_condition (difference), &value0))
2176 *overlaps_a = chrec_dont_know;
2177 *overlaps_b = chrec_dont_know;
2178 *last_conflicts = chrec_dont_know;
2183 if (value0 == false)
2185 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
2187 *overlaps_a = chrec_dont_know;
2188 *overlaps_b = chrec_dont_know;
2189 *last_conflicts = chrec_dont_know;
2198 chrec_b = {10, +, 1}
2201 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2203 *overlaps_a = integer_zero_node;
2204 *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
2205 fold_build1 (ABS_EXPR,
2208 CHREC_RIGHT (chrec_b));
2209 *last_conflicts = integer_one_node;
2213 /* When the step does not divide the difference, there are
2217 *overlaps_a = chrec_known;
2218 *overlaps_b = chrec_known;
2219 *last_conflicts = integer_zero_node;
2228 chrec_b = {10, +, -1}
2230 In this case, chrec_a will not overlap with chrec_b. */
2231 *overlaps_a = chrec_known;
2232 *overlaps_b = chrec_known;
2233 *last_conflicts = integer_zero_node;
2240 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
2242 *overlaps_a = chrec_dont_know;
2243 *overlaps_b = chrec_dont_know;
2244 *last_conflicts = chrec_dont_know;
2249 if (value2 == false)
2253 chrec_b = {10, +, -1}
2255 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2257 *overlaps_a = integer_zero_node;
2258 *overlaps_b = fold_build2 (EXACT_DIV_EXPR,
2259 integer_type_node, difference,
2260 CHREC_RIGHT (chrec_b));
2261 *last_conflicts = integer_one_node;
2265 /* When the step does not divide the difference, there
2269 *overlaps_a = chrec_known;
2270 *overlaps_b = chrec_known;
2271 *last_conflicts = integer_zero_node;
2281 In this case, chrec_a will not overlap with chrec_b. */
2282 *overlaps_a = chrec_known;
2283 *overlaps_b = chrec_known;
2284 *last_conflicts = integer_zero_node;
2292 /* Helper recursive function for initializing the matrix A. Returns
2293 the initial value of CHREC. */
2296 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2300 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2301 return int_cst_value (chrec);
2303 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2304 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2307 #define FLOOR_DIV(x,y) ((x) / (y))
2309 /* Solves the special case of the Diophantine equation:
2310 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2312 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2313 number of iterations that loops X and Y run. The overlaps will be
2314 constructed as evolutions in dimension DIM. */
2317 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
2318 tree *overlaps_a, tree *overlaps_b,
2319 tree *last_conflicts, int dim)
2321 if (((step_a > 0 && step_b > 0)
2322 || (step_a < 0 && step_b < 0)))
2324 int step_overlaps_a, step_overlaps_b;
2325 int gcd_steps_a_b, last_conflict, tau2;
2327 gcd_steps_a_b = gcd (step_a, step_b);
2328 step_overlaps_a = step_b / gcd_steps_a_b;
2329 step_overlaps_b = step_a / gcd_steps_a_b;
2331 tau2 = FLOOR_DIV (niter, step_overlaps_a);
2332 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2333 last_conflict = tau2;
2335 *overlaps_a = build_polynomial_chrec
2336 (dim, integer_zero_node,
2337 build_int_cst (NULL_TREE, step_overlaps_a));
2338 *overlaps_b = build_polynomial_chrec
2339 (dim, integer_zero_node,
2340 build_int_cst (NULL_TREE, step_overlaps_b));
2341 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2346 *overlaps_a = integer_zero_node;
2347 *overlaps_b = integer_zero_node;
2348 *last_conflicts = integer_zero_node;
2353 /* Solves the special case of a Diophantine equation where CHREC_A is
2354 an affine bivariate function, and CHREC_B is an affine univariate
2355 function. For example,
2357 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2359 has the following overlapping functions:
2361 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2362 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2363 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2365 FORNOW: This is a specialized implementation for a case occurring in
2366 a common benchmark. Implement the general algorithm. */
2369 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2370 tree *overlaps_a, tree *overlaps_b,
2371 tree *last_conflicts)
2373 bool xz_p, yz_p, xyz_p;
2374 int step_x, step_y, step_z;
2375 int niter_x, niter_y, niter_z, niter;
2376 tree numiter_x, numiter_y, numiter_z;
2377 tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
2378 tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
2379 tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
2381 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2382 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2383 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2385 numiter_x = number_of_iterations_in_loop
2386 (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]);
2387 numiter_y = number_of_iterations_in_loop
2388 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2389 numiter_z = number_of_iterations_in_loop
2390 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2392 if (TREE_CODE (numiter_x) != INTEGER_CST)
2393 numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]
2394 ->estimated_nb_iterations;
2395 if (TREE_CODE (numiter_y) != INTEGER_CST)
2396 numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2397 ->estimated_nb_iterations;
2398 if (TREE_CODE (numiter_z) != INTEGER_CST)
2399 numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2400 ->estimated_nb_iterations;
2402 if (chrec_contains_undetermined (numiter_x)
2403 || chrec_contains_undetermined (numiter_y)
2404 || chrec_contains_undetermined (numiter_z)
2405 || TREE_CODE (numiter_x) != INTEGER_CST
2406 || TREE_CODE (numiter_y) != INTEGER_CST
2407 || TREE_CODE (numiter_z) != INTEGER_CST)
2409 *overlaps_a = chrec_dont_know;
2410 *overlaps_b = chrec_dont_know;
2411 *last_conflicts = chrec_dont_know;
2415 niter_x = int_cst_value (numiter_x);
2416 niter_y = int_cst_value (numiter_y);
2417 niter_z = int_cst_value (numiter_z);
2419 niter = MIN (niter_x, niter_z);
2420 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2423 &last_conflicts_xz, 1);
2424 niter = MIN (niter_y, niter_z);
2425 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2428 &last_conflicts_yz, 2);
2429 niter = MIN (niter_x, niter_z);
2430 niter = MIN (niter_y, niter);
2431 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2434 &last_conflicts_xyz, 3);
2436 xz_p = !integer_zerop (last_conflicts_xz);
2437 yz_p = !integer_zerop (last_conflicts_yz);
2438 xyz_p = !integer_zerop (last_conflicts_xyz);
2440 if (xz_p || yz_p || xyz_p)
2442 *overlaps_a = make_tree_vec (2);
2443 TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
2444 TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
2445 *overlaps_b = integer_zero_node;
2448 TREE_VEC_ELT (*overlaps_a, 0) =
2449 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
2452 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
2453 *last_conflicts = last_conflicts_xz;
2457 TREE_VEC_ELT (*overlaps_a, 1) =
2458 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
2461 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
2462 *last_conflicts = last_conflicts_yz;
2466 TREE_VEC_ELT (*overlaps_a, 0) =
2467 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
2469 TREE_VEC_ELT (*overlaps_a, 1) =
2470 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
2473 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
2474 *last_conflicts = last_conflicts_xyz;
2479 *overlaps_a = integer_zero_node;
2480 *overlaps_b = integer_zero_node;
2481 *last_conflicts = integer_zero_node;
2485 /* Determines the overlapping elements due to accesses CHREC_A and
2486 CHREC_B, that are affine functions. This is a part of the
2487 subscript analyzer. */
2490 analyze_subscript_affine_affine (tree chrec_a,
2494 tree *last_conflicts)
2496 unsigned nb_vars_a, nb_vars_b, dim;
2497 int init_a, init_b, gamma, gcd_alpha_beta;
2499 lambda_matrix A, U, S;
2501 if (dump_file && (dump_flags & TDF_DETAILS))
2502 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2504 /* For determining the initial intersection, we have to solve a
2505 Diophantine equation. This is the most time consuming part.
2507 For answering to the question: "Is there a dependence?" we have
2508 to prove that there exists a solution to the Diophantine
2509 equation, and that the solution is in the iteration domain,
2510 i.e. the solution is positive or zero, and that the solution
2511 happens before the upper bound loop.nb_iterations. Otherwise
2512 there is no dependence. This function outputs a description of
2513 the iterations that hold the intersections. */
2516 nb_vars_a = nb_vars_in_chrec (chrec_a);
2517 nb_vars_b = nb_vars_in_chrec (chrec_b);
2519 dim = nb_vars_a + nb_vars_b;
2520 U = lambda_matrix_new (dim, dim);
2521 A = lambda_matrix_new (dim, 1);
2522 S = lambda_matrix_new (dim, 1);
2524 init_a = initialize_matrix_A (A, chrec_a, 0, 1);
2525 init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
2526 gamma = init_b - init_a;
2528 /* Don't do all the hard work of solving the Diophantine equation
2529 when we already know the solution: for example,
2532 | gamma = 3 - 3 = 0.
2533 Then the first overlap occurs during the first iterations:
2534 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2538 if (nb_vars_a == 1 && nb_vars_b == 1)
2541 int niter, niter_a, niter_b;
2542 tree numiter_a, numiter_b;
2544 numiter_a = number_of_iterations_in_loop
2545 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2546 numiter_b = number_of_iterations_in_loop
2547 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2549 if (TREE_CODE (numiter_a) != INTEGER_CST)
2550 numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2551 ->estimated_nb_iterations;
2552 if (TREE_CODE (numiter_b) != INTEGER_CST)
2553 numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2554 ->estimated_nb_iterations;
2555 if (chrec_contains_undetermined (numiter_a)
2556 || chrec_contains_undetermined (numiter_b)
2557 || TREE_CODE (numiter_a) != INTEGER_CST
2558 || TREE_CODE (numiter_b) != INTEGER_CST)
2560 *overlaps_a = chrec_dont_know;
2561 *overlaps_b = chrec_dont_know;
2562 *last_conflicts = chrec_dont_know;
2566 niter_a = int_cst_value (numiter_a);
2567 niter_b = int_cst_value (numiter_b);
2568 niter = MIN (niter_a, niter_b);
2570 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2571 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2573 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2574 overlaps_a, overlaps_b,
2578 else if (nb_vars_a == 2 && nb_vars_b == 1)
2579 compute_overlap_steps_for_affine_1_2
2580 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2582 else if (nb_vars_a == 1 && nb_vars_b == 2)
2583 compute_overlap_steps_for_affine_1_2
2584 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2588 *overlaps_a = chrec_dont_know;
2589 *overlaps_b = chrec_dont_know;
2590 *last_conflicts = chrec_dont_know;
2596 lambda_matrix_right_hermite (A, dim, 1, S, U);
2601 lambda_matrix_row_negate (U, dim, 0);
2603 gcd_alpha_beta = S[0][0];
2605 /* The classic "gcd-test". */
2606 if (!int_divides_p (gcd_alpha_beta, gamma))
2608 /* The "gcd-test" has determined that there is no integer
2609 solution, i.e. there is no dependence. */
2610 *overlaps_a = chrec_known;
2611 *overlaps_b = chrec_known;
2612 *last_conflicts = integer_zero_node;
2615 /* Both access functions are univariate. This includes SIV and MIV cases. */
2616 else if (nb_vars_a == 1 && nb_vars_b == 1)
2618 /* Both functions should have the same evolution sign. */
2619 if (((A[0][0] > 0 && -A[1][0] > 0)
2620 || (A[0][0] < 0 && -A[1][0] < 0)))
2622 /* The solutions are given by:
2624 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2627 For a given integer t. Using the following variables,
2629 | i0 = u11 * gamma / gcd_alpha_beta
2630 | j0 = u12 * gamma / gcd_alpha_beta
2637 | y0 = j0 + j1 * t. */
2641 /* X0 and Y0 are the first iterations for which there is a
2642 dependence. X0, Y0 are two solutions of the Diophantine
2643 equation: chrec_a (X0) = chrec_b (Y0). */
2645 int niter, niter_a, niter_b;
2646 tree numiter_a, numiter_b;
2648 numiter_a = number_of_iterations_in_loop
2649 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2650 numiter_b = number_of_iterations_in_loop
2651 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2653 if (TREE_CODE (numiter_a) != INTEGER_CST)
2654 numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2655 ->estimated_nb_iterations;
2656 if (TREE_CODE (numiter_b) != INTEGER_CST)
2657 numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2658 ->estimated_nb_iterations;
2659 if (chrec_contains_undetermined (numiter_a)
2660 || chrec_contains_undetermined (numiter_b)
2661 || TREE_CODE (numiter_a) != INTEGER_CST
2662 || TREE_CODE (numiter_b) != INTEGER_CST)
2664 *overlaps_a = chrec_dont_know;
2665 *overlaps_b = chrec_dont_know;
2666 *last_conflicts = chrec_dont_know;
2670 niter_a = int_cst_value (numiter_a);
2671 niter_b = int_cst_value (numiter_b);
2672 niter = MIN (niter_a, niter_b);
2674 i0 = U[0][0] * gamma / gcd_alpha_beta;
2675 j0 = U[0][1] * gamma / gcd_alpha_beta;
2679 if ((i1 == 0 && i0 < 0)
2680 || (j1 == 0 && j0 < 0))
2682 /* There is no solution.
2683 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2684 falls in here, but for the moment we don't look at the
2685 upper bound of the iteration domain. */
2686 *overlaps_a = chrec_known;
2687 *overlaps_b = chrec_known;
2688 *last_conflicts = integer_zero_node;
2695 tau1 = CEIL (-i0, i1);
2696 tau2 = FLOOR_DIV (niter - i0, i1);
2700 int last_conflict, min_multiple;
2701 tau1 = MAX (tau1, CEIL (-j0, j1));
2702 tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
2704 x0 = i1 * tau1 + i0;
2705 y0 = j1 * tau1 + j0;
2707 /* At this point (x0, y0) is one of the
2708 solutions to the Diophantine equation. The
2709 next step has to compute the smallest
2710 positive solution: the first conflicts. */
2711 min_multiple = MIN (x0 / i1, y0 / j1);
2712 x0 -= i1 * min_multiple;
2713 y0 -= j1 * min_multiple;
2715 tau1 = (x0 - i0)/i1;
2716 last_conflict = tau2 - tau1;
2718 *overlaps_a = build_polynomial_chrec
2720 build_int_cst (NULL_TREE, x0),
2721 build_int_cst (NULL_TREE, i1));
2722 *overlaps_b = build_polynomial_chrec
2724 build_int_cst (NULL_TREE, y0),
2725 build_int_cst (NULL_TREE, j1));
2726 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2730 /* FIXME: For the moment, the upper bound of the
2731 iteration domain for j is not checked. */
2732 *overlaps_a = chrec_dont_know;
2733 *overlaps_b = chrec_dont_know;
2734 *last_conflicts = chrec_dont_know;
2740 /* FIXME: For the moment, the upper bound of the
2741 iteration domain for i is not checked. */
2742 *overlaps_a = chrec_dont_know;
2743 *overlaps_b = chrec_dont_know;
2744 *last_conflicts = chrec_dont_know;
2750 *overlaps_a = chrec_dont_know;
2751 *overlaps_b = chrec_dont_know;
2752 *last_conflicts = chrec_dont_know;
2758 *overlaps_a = chrec_dont_know;
2759 *overlaps_b = chrec_dont_know;
2760 *last_conflicts = chrec_dont_know;
2764 if (dump_file && (dump_flags & TDF_DETAILS))
2766 fprintf (dump_file, " (overlaps_a = ");
2767 print_generic_expr (dump_file, *overlaps_a, 0);
2768 fprintf (dump_file, ")\n (overlaps_b = ");
2769 print_generic_expr (dump_file, *overlaps_b, 0);
2770 fprintf (dump_file, ")\n");
2773 if (dump_file && (dump_flags & TDF_DETAILS))
2774 fprintf (dump_file, ")\n");
2777 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2778 *OVERLAPS_B are initialized to the functions that describe the
2779 relation between the elements accessed twice by CHREC_A and
2780 CHREC_B. For k >= 0, the following property is verified:
2782 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2785 analyze_siv_subscript (tree chrec_a,
2789 tree *last_conflicts)
2791 if (dump_file && (dump_flags & TDF_DETAILS))
2792 fprintf (dump_file, "(analyze_siv_subscript \n");
2794 if (evolution_function_is_constant_p (chrec_a)
2795 && evolution_function_is_affine_p (chrec_b))
2796 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
2797 overlaps_a, overlaps_b, last_conflicts);
2799 else if (evolution_function_is_affine_p (chrec_a)
2800 && evolution_function_is_constant_p (chrec_b))
2801 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2802 overlaps_b, overlaps_a, last_conflicts);
2804 else if (evolution_function_is_affine_p (chrec_a)
2805 && evolution_function_is_affine_p (chrec_b))
2806 analyze_subscript_affine_affine (chrec_a, chrec_b,
2807 overlaps_a, overlaps_b, last_conflicts);
2810 *overlaps_a = chrec_dont_know;
2811 *overlaps_b = chrec_dont_know;
2812 *last_conflicts = chrec_dont_know;
2815 if (dump_file && (dump_flags & TDF_DETAILS))
2816 fprintf (dump_file, ")\n");
2819 /* Return true when the evolution steps of an affine CHREC divide the
2823 chrec_steps_divide_constant_p (tree chrec,
2826 switch (TREE_CODE (chrec))
2828 case POLYNOMIAL_CHREC:
2829 return (tree_fold_divides_p (CHREC_RIGHT (chrec), cst)
2830 && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
2833 /* On the initial condition, return true. */
2838 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
2839 *OVERLAPS_B are initialized to the functions that describe the
2840 relation between the elements accessed twice by CHREC_A and
2841 CHREC_B. For k >= 0, the following property is verified:
2843 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2846 analyze_miv_subscript (tree chrec_a,
2850 tree *last_conflicts)
2852 /* FIXME: This is a MIV subscript, not yet handled.
2853 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2856 In the SIV test we had to solve a Diophantine equation with two
2857 variables. In the MIV case we have to solve a Diophantine
2858 equation with 2*n variables (if the subscript uses n IVs).
2862 if (dump_file && (dump_flags & TDF_DETAILS))
2863 fprintf (dump_file, "(analyze_miv_subscript \n");
2865 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2867 if (chrec_zerop (difference))
2869 /* Access functions are the same: all the elements are accessed
2870 in the same order. */
2871 *overlaps_a = integer_zero_node;
2872 *overlaps_b = integer_zero_node;
2873 *last_conflicts = number_of_iterations_in_loop
2874 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2877 else if (evolution_function_is_constant_p (difference)
2878 /* For the moment, the following is verified:
2879 evolution_function_is_affine_multivariate_p (chrec_a) */
2880 && !chrec_steps_divide_constant_p (chrec_a, difference))
2882 /* testsuite/.../ssa-chrec-33.c
2883 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2885 The difference is 1, and the evolution steps are equal to 2,
2886 consequently there are no overlapping elements. */
2887 *overlaps_a = chrec_known;
2888 *overlaps_b = chrec_known;
2889 *last_conflicts = integer_zero_node;
2892 else if (evolution_function_is_affine_multivariate_p (chrec_a)
2893 && evolution_function_is_affine_multivariate_p (chrec_b))
2895 /* testsuite/.../ssa-chrec-35.c
2896 {0, +, 1}_2 vs. {0, +, 1}_3
2897 the overlapping elements are respectively located at iterations:
2898 {0, +, 1}_x and {0, +, 1}_x,
2899 in other words, we have the equality:
2900 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2903 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2904 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2906 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2907 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2909 analyze_subscript_affine_affine (chrec_a, chrec_b,
2910 overlaps_a, overlaps_b, last_conflicts);
2915 /* When the analysis is too difficult, answer "don't know". */
2916 *overlaps_a = chrec_dont_know;
2917 *overlaps_b = chrec_dont_know;
2918 *last_conflicts = chrec_dont_know;
2921 if (dump_file && (dump_flags & TDF_DETAILS))
2922 fprintf (dump_file, ")\n");
2925 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
2926 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
2927 two functions that describe the iterations that contain conflicting
2930 Remark: For an integer k >= 0, the following equality is true:
2932 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2936 analyze_overlapping_iterations (tree chrec_a,
2938 tree *overlap_iterations_a,
2939 tree *overlap_iterations_b,
2940 tree *last_conflicts)
2942 if (dump_file && (dump_flags & TDF_DETAILS))
2944 fprintf (dump_file, "(analyze_overlapping_iterations \n");
2945 fprintf (dump_file, " (chrec_a = ");
2946 print_generic_expr (dump_file, chrec_a, 0);
2947 fprintf (dump_file, ")\n chrec_b = ");
2948 print_generic_expr (dump_file, chrec_b, 0);
2949 fprintf (dump_file, ")\n");
2952 if (chrec_a == NULL_TREE
2953 || chrec_b == NULL_TREE
2954 || chrec_contains_undetermined (chrec_a)
2955 || chrec_contains_undetermined (chrec_b)
2956 || chrec_contains_symbols (chrec_a)
2957 || chrec_contains_symbols (chrec_b))
2959 *overlap_iterations_a = chrec_dont_know;
2960 *overlap_iterations_b = chrec_dont_know;
2963 else if (ziv_subscript_p (chrec_a, chrec_b))
2964 analyze_ziv_subscript (chrec_a, chrec_b,
2965 overlap_iterations_a, overlap_iterations_b,
2968 else if (siv_subscript_p (chrec_a, chrec_b))
2969 analyze_siv_subscript (chrec_a, chrec_b,
2970 overlap_iterations_a, overlap_iterations_b,
2974 analyze_miv_subscript (chrec_a, chrec_b,
2975 overlap_iterations_a, overlap_iterations_b,
2978 if (dump_file && (dump_flags & TDF_DETAILS))
2980 fprintf (dump_file, " (overlap_iterations_a = ");
2981 print_generic_expr (dump_file, *overlap_iterations_a, 0);
2982 fprintf (dump_file, ")\n (overlap_iterations_b = ");
2983 print_generic_expr (dump_file, *overlap_iterations_b, 0);
2984 fprintf (dump_file, ")\n");
2990 /* This section contains the affine functions dependences detector. */
2992 /* Computes the conflicting iterations, and initialize DDR. */
2995 subscript_dependence_tester (struct data_dependence_relation *ddr)
2998 struct data_reference *dra = DDR_A (ddr);
2999 struct data_reference *drb = DDR_B (ddr);
3000 tree last_conflicts;
3002 if (dump_file && (dump_flags & TDF_DETAILS))
3003 fprintf (dump_file, "(subscript_dependence_tester \n");
3005 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3007 tree overlaps_a, overlaps_b;
3008 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3010 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
3011 DR_ACCESS_FN (drb, i),
3012 &overlaps_a, &overlaps_b,
3015 if (chrec_contains_undetermined (overlaps_a)
3016 || chrec_contains_undetermined (overlaps_b))
3018 finalize_ddr_dependent (ddr, chrec_dont_know);
3022 else if (overlaps_a == chrec_known
3023 || overlaps_b == chrec_known)
3025 finalize_ddr_dependent (ddr, chrec_known);
3031 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3032 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3033 SUB_LAST_CONFLICT (subscript) = last_conflicts;
3037 if (dump_file && (dump_flags & TDF_DETAILS))
3038 fprintf (dump_file, ")\n");
3041 /* Compute the classic per loop distance vector.
3043 DDR is the data dependence relation to build a vector from.
3044 NB_LOOPS is the total number of loops we are considering.
3045 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
3047 Return FALSE when fail to represent the data dependence as a distance
3049 Return TRUE otherwise. */
3052 build_classic_dist_vector (struct data_dependence_relation *ddr,
3053 int nb_loops, int first_loop_depth)
3056 lambda_vector dist_v, init_v;
3058 dist_v = lambda_vector_new (nb_loops);
3059 init_v = lambda_vector_new (nb_loops);
3060 lambda_vector_clear (dist_v, nb_loops);
3061 lambda_vector_clear (init_v, nb_loops);
3063 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3066 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3068 tree access_fn_a, access_fn_b;
3069 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3071 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3073 non_affine_dependence_relation (ddr);
3077 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
3078 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
3080 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3081 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3083 int dist, loop_nb, loop_depth;
3084 int loop_nb_a = CHREC_VARIABLE (access_fn_a);
3085 int loop_nb_b = CHREC_VARIABLE (access_fn_b);
3086 struct loop *loop_a = current_loops->parray[loop_nb_a];
3087 struct loop *loop_b = current_loops->parray[loop_nb_b];
3089 /* If the loop for either variable is at a lower depth than
3090 the first_loop's depth, then we can't possibly have a
3091 dependency at this level of the loop. */
3093 if (loop_a->depth < first_loop_depth
3094 || loop_b->depth < first_loop_depth)
3097 if (loop_nb_a != loop_nb_b
3098 && !flow_loop_nested_p (loop_a, loop_b)
3099 && !flow_loop_nested_p (loop_b, loop_a))
3101 /* Example: when there are two consecutive loops,
3110 the dependence relation cannot be captured by the
3111 distance abstraction. */
3112 non_affine_dependence_relation (ddr);
3116 /* The dependence is carried by the outermost loop. Example:
3123 In this case, the dependence is carried by loop_1. */
3124 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
3125 loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
3127 /* If the loop number is still greater than the number of
3128 loops we've been asked to analyze, or negative,
3129 something is borked. */
3130 gcc_assert (loop_depth >= 0);
3131 gcc_assert (loop_depth < nb_loops);
3132 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3134 non_affine_dependence_relation (ddr);
3138 dist = int_cst_value (SUB_DISTANCE (subscript));
3140 /* This is the subscript coupling test.
3145 There is no dependence. */
3146 if (init_v[loop_depth] != 0
3147 && dist_v[loop_depth] != dist)
3149 finalize_ddr_dependent (ddr, chrec_known);
3153 dist_v[loop_depth] = dist;
3154 init_v[loop_depth] = 1;
3158 /* There is a distance of 1 on all the outer loops:
3160 Example: there is a dependence of distance 1 on loop_1 for the array A.
3166 struct loop *lca, *loop_a, *loop_b;
3167 struct data_reference *a = DDR_A (ddr);
3168 struct data_reference *b = DDR_B (ddr);
3170 loop_a = loop_containing_stmt (DR_STMT (a));
3171 loop_b = loop_containing_stmt (DR_STMT (b));
3173 /* Get the common ancestor loop. */
3174 lca = find_common_loop (loop_a, loop_b);
3176 lca_depth = lca->depth;
3177 lca_depth -= first_loop_depth;
3178 gcc_assert (lca_depth >= 0);
3179 gcc_assert (lca_depth < nb_loops);
3181 /* For each outer loop where init_v is not set, the accesses are
3182 in dependence of distance 1 in the loop. */
3185 && init_v[lca_depth] == 0)
3186 dist_v[lca_depth] = 1;
3192 lca_depth = lca->depth - first_loop_depth;
3193 while (lca->depth != 0)
3195 /* If we're considering just a sub-nest, then don't record
3196 any information on the outer loops. */
3200 gcc_assert (lca_depth < nb_loops);
3202 if (init_v[lca_depth] == 0)
3203 dist_v[lca_depth] = 1;
3205 lca_depth = lca->depth - first_loop_depth;
3211 DDR_DIST_VECT (ddr) = dist_v;
3212 DDR_SIZE_VECT (ddr) = nb_loops;
3214 /* Verify a basic constraint: classic distance vectors should always
3215 be lexicographically positive. */
3216 if (!lambda_vector_lexico_pos (DDR_DIST_VECT (ddr),
3217 DDR_SIZE_VECT (ddr)))
3219 if (DDR_SIZE_VECT (ddr) == 1)
3220 /* This one is simple to fix, and can be fixed.
3221 Multidimensional arrays cannot be fixed that simply. */
3222 lambda_vector_negate (DDR_DIST_VECT (ddr), DDR_DIST_VECT (ddr),
3223 DDR_SIZE_VECT (ddr));
3225 /* This is not valid: we need the delta test for properly
3233 /* Compute the classic per loop direction vector.
3235 DDR is the data dependence relation to build a vector from.
3236 NB_LOOPS is the total number of loops we are considering.
3237 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
3239 Return FALSE if the dependence relation is outside of the loop nest
3240 at FIRST_LOOP_DEPTH.
3241 Return TRUE otherwise. */
3244 build_classic_dir_vector (struct data_dependence_relation *ddr,
3245 int nb_loops, int first_loop_depth)
3248 lambda_vector dir_v, init_v;
3250 dir_v = lambda_vector_new (nb_loops);
3251 init_v = lambda_vector_new (nb_loops);
3252 lambda_vector_clear (dir_v, nb_loops);
3253 lambda_vector_clear (init_v, nb_loops);
3255 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3258 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3260 tree access_fn_a, access_fn_b;
3261 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3263 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3265 non_affine_dependence_relation (ddr);
3269 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
3270 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
3271 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3272 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3274 int dist, loop_nb, loop_depth;
3275 enum data_dependence_direction dir = dir_star;
3276 int loop_nb_a = CHREC_VARIABLE (access_fn_a);
3277 int loop_nb_b = CHREC_VARIABLE (access_fn_b);
3278 struct loop *loop_a = current_loops->parray[loop_nb_a];
3279 struct loop *loop_b = current_loops->parray[loop_nb_b];
3281 /* If the loop for either variable is at a lower depth than
3282 the first_loop's depth, then we can't possibly have a
3283 dependency at this level of the loop. */
3285 if (loop_a->depth < first_loop_depth
3286 || loop_b->depth < first_loop_depth)
3289 if (loop_nb_a != loop_nb_b
3290 && !flow_loop_nested_p (loop_a, loop_b)
3291 && !flow_loop_nested_p (loop_b, loop_a))
3293 /* Example: when there are two consecutive loops,
3302 the dependence relation cannot be captured by the
3303 distance abstraction. */
3304 non_affine_dependence_relation (ddr);
3308 /* The dependence is carried by the outermost loop. Example:
3315 In this case, the dependence is carried by loop_1. */
3316 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
3317 loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
3319 /* If the loop number is still greater than the number of
3320 loops we've been asked to analyze, or negative,
3321 something is borked. */
3322 gcc_assert (loop_depth >= 0);
3323 gcc_assert (loop_depth < nb_loops);
3325 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3327 non_affine_dependence_relation (ddr);
3331 dist = int_cst_value (SUB_DISTANCE (subscript));
3340 /* This is the subscript coupling test.
3345 There is no dependence. */
3346 if (init_v[loop_depth] != 0
3348 && (enum data_dependence_direction) dir_v[loop_depth] != dir
3349 && (enum data_dependence_direction) dir_v[loop_depth] != dir_star)
3351 finalize_ddr_dependent (ddr, chrec_known);
3355 dir_v[loop_depth] = dir;
3356 init_v[loop_depth] = 1;
3360 /* There is a distance of 1 on all the outer loops:
3362 Example: there is a dependence of distance 1 on loop_1 for the array A.
3368 struct loop *lca, *loop_a, *loop_b;
3369 struct data_reference *a = DDR_A (ddr);
3370 struct data_reference *b = DDR_B (ddr);
3372 loop_a = loop_containing_stmt (DR_STMT (a));
3373 loop_b = loop_containing_stmt (DR_STMT (b));
3375 /* Get the common ancestor loop. */
3376 lca = find_common_loop (loop_a, loop_b);
3377 lca_depth = lca->depth - first_loop_depth;
3379 gcc_assert (lca_depth >= 0);
3380 gcc_assert (lca_depth < nb_loops);
3382 /* For each outer loop where init_v is not set, the accesses are
3383 in dependence of distance 1 in the loop. */
3386 && init_v[lca_depth] == 0)
3387 dir_v[lca_depth] = dir_positive;
3392 lca_depth = lca->depth - first_loop_depth;
3393 while (lca->depth != 0)
3395 /* If we're considering just a sub-nest, then don't record
3396 any information on the outer loops. */
3400 gcc_assert (lca_depth < nb_loops);
3402 if (init_v[lca_depth] == 0)
3403 dir_v[lca_depth] = dir_positive;
3405 lca_depth = lca->depth - first_loop_depth;
3411 DDR_DIR_VECT (ddr) = dir_v;
3412 DDR_SIZE_VECT (ddr) = nb_loops;
3416 /* Returns true when all the access functions of A are affine or
3420 access_functions_are_affine_or_constant_p (struct data_reference *a)
3423 VEC(tree,heap) **fns = DR_ACCESS_FNS_ADDR (a);
3426 for (i = 0; VEC_iterate (tree, *fns, i, t); i++)
3427 if (!evolution_function_is_constant_p (t)
3428 && !evolution_function_is_affine_multivariate_p (t))
3434 /* This computes the affine dependence relation between A and B.
3435 CHREC_KNOWN is used for representing the independence between two
3436 accesses, while CHREC_DONT_KNOW is used for representing the unknown
3439 Note that it is possible to stop the computation of the dependence
3440 relation the first time we detect a CHREC_KNOWN element for a given
3444 compute_affine_dependence (struct data_dependence_relation *ddr)
3446 struct data_reference *dra = DDR_A (ddr);
3447 struct data_reference *drb = DDR_B (ddr);
3449 if (dump_file && (dump_flags & TDF_DETAILS))
3451 fprintf (dump_file, "(compute_affine_dependence\n");
3452 fprintf (dump_file, " (stmt_a = \n");
3453 print_generic_expr (dump_file, DR_STMT (dra), 0);
3454 fprintf (dump_file, ")\n (stmt_b = \n");
3455 print_generic_expr (dump_file, DR_STMT (drb), 0);
3456 fprintf (dump_file, ")\n");
3459 /* Analyze only when the dependence relation is not yet known. */
3460 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3462 if (access_functions_are_affine_or_constant_p (dra)
3463 && access_functions_are_affine_or_constant_p (drb))
3464 subscript_dependence_tester (ddr);
3466 /* As a last case, if the dependence cannot be determined, or if
3467 the dependence is considered too difficult to determine, answer
3470 finalize_ddr_dependent (ddr, chrec_dont_know);
3473 if (dump_file && (dump_flags & TDF_DETAILS))
3474 fprintf (dump_file, ")\n");
3477 /* This computes the dependence relation for the same data
3478 reference into DDR. */
3481 compute_self_dependence (struct data_dependence_relation *ddr)
3485 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3487 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3489 /* The accessed index overlaps for each iteration. */
3490 SUB_CONFLICTS_IN_A (subscript) = integer_zero_node;
3491 SUB_CONFLICTS_IN_B (subscript) = integer_zero_node;
3492 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3497 typedef struct data_dependence_relation *ddr_p;
3499 DEF_VEC_ALLOC_P(ddr_p,heap);
3501 /* Compute a subset of the data dependence relation graph. Don't
3502 compute read-read and self relations if
3503 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is FALSE, and avoid the computation
3504 of the opposite relation, i.e. when AB has been computed, don't compute BA.
3505 DATAREFS contains a list of data references, and the result is set
3506 in DEPENDENCE_RELATIONS. */
3509 compute_all_dependences (varray_type datarefs,
3510 bool compute_self_and_read_read_dependences,
3511 VEC(ddr_p,heap) **dependence_relations)
3513 unsigned int i, j, N;
3515 N = VARRAY_ACTIVE_SIZE (datarefs);
3517 /* Note that we specifically skip i == j because it's a self dependence, and
3518 use compute_self_dependence below. */
3520 for (i = 0; i < N; i++)
3521 for (j = i + 1; j < N; j++)
3523 struct data_reference *a, *b;
3524 struct data_dependence_relation *ddr;
3526 a = VARRAY_GENERIC_PTR (datarefs, i);
3527 b = VARRAY_GENERIC_PTR (datarefs, j);
3528 if (DR_IS_READ (a) && DR_IS_READ (b)
3529 && !compute_self_and_read_read_dependences)
3531 ddr = initialize_data_dependence_relation (a, b);
3533 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3534 compute_affine_dependence (ddr);
3535 compute_subscript_distance (ddr);
3537 if (!compute_self_and_read_read_dependences)
3540 /* Compute self dependence relation of each dataref to itself. */
3542 for (i = 0; i < N; i++)
3544 struct data_reference *a, *b;
3545 struct data_dependence_relation *ddr;
3547 a = VARRAY_GENERIC_PTR (datarefs, i);
3548 b = VARRAY_GENERIC_PTR (datarefs, i);
3549 ddr = initialize_data_dependence_relation (a, b);
3551 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3552 compute_self_dependence (ddr);
3553 compute_subscript_distance (ddr);
3557 /* Search the data references in LOOP, and record the information into
3558 DATAREFS. Returns chrec_dont_know when failing to analyze a
3559 difficult case, returns NULL_TREE otherwise.
3561 TODO: This function should be made smarter so that it can handle address
3562 arithmetic as if they were array accesses, etc. */
3565 find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
3567 basic_block bb, *bbs;
3569 block_stmt_iterator bsi;
3570 struct data_reference *dr;
3572 bbs = get_loop_body (loop);
3574 for (i = 0; i < loop->num_nodes; i++)
3578 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3580 tree stmt = bsi_stmt (bsi);
3582 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
3583 Calls have side-effects, except those to const or pure
3585 if ((TREE_CODE (stmt) == CALL_EXPR
3586 && !(call_expr_flags (stmt) & (ECF_CONST | ECF_PURE)))
3587 || (TREE_CODE (stmt) == ASM_EXPR
3588 && ASM_VOLATILE_P (stmt)))
3589 goto insert_dont_know_node;
3591 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3594 switch (TREE_CODE (stmt))
3598 bool one_inserted = false;
3599 tree opnd0 = TREE_OPERAND (stmt, 0);
3600 tree opnd1 = TREE_OPERAND (stmt, 1);
3602 if (TREE_CODE (opnd0) == ARRAY_REF
3603 || TREE_CODE (opnd0) == INDIRECT_REF)
3605 dr = create_data_ref (opnd0, stmt, false);
3608 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3609 one_inserted = true;
3613 if (TREE_CODE (opnd1) == ARRAY_REF
3614 || TREE_CODE (opnd1) == INDIRECT_REF)
3616 dr = create_data_ref (opnd1, stmt, true);
3619 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3620 one_inserted = true;
3625 goto insert_dont_know_node;
3633 bool one_inserted = false;
3635 for (args = TREE_OPERAND (stmt, 1); args;
3636 args = TREE_CHAIN (args))
3637 if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
3638 || TREE_CODE (TREE_VALUE (args)) == INDIRECT_REF)
3640 dr = create_data_ref (TREE_VALUE (args), stmt, true);
3643 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3644 one_inserted = true;
3649 goto insert_dont_know_node;
3656 struct data_reference *res;
3658 insert_dont_know_node:;
3659 res = xmalloc (sizeof (struct data_reference));
3660 DR_STMT (res) = NULL_TREE;
3661 DR_REF (res) = NULL_TREE;
3662 DR_BASE_OBJECT (res) = NULL;
3663 DR_TYPE (res) = ARRAY_REF_TYPE;
3664 DR_SET_ACCESS_FNS (res, NULL);
3665 DR_BASE_OBJECT (res) = NULL;
3666 DR_IS_READ (res) = false;
3667 DR_BASE_ADDRESS (res) = NULL_TREE;
3668 DR_OFFSET (res) = NULL_TREE;
3669 DR_INIT (res) = NULL_TREE;
3670 DR_STEP (res) = NULL_TREE;
3671 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
3672 DR_MEMTAG (res) = NULL_TREE;
3673 DR_PTR_INFO (res) = NULL;
3674 VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
3677 return chrec_dont_know;
3681 /* When there are no defs in the loop, the loop is parallel. */
3682 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
3683 loop->parallel_p = false;
3694 /* This section contains all the entry points. */
3696 /* Given a loop nest LOOP, the following vectors are returned:
3697 *DATAREFS is initialized to all the array elements contained in this loop,
3698 *DEPENDENCE_RELATIONS contains the relations between the data references.
3699 Compute read-read and self relations if
3700 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
3703 compute_data_dependences_for_loop (struct loop *loop,
3704 bool compute_self_and_read_read_dependences,
3705 varray_type *datarefs,
3706 varray_type *dependence_relations)
3708 unsigned int i, nb_loops;
3709 VEC(ddr_p,heap) *allrelations;
3710 struct data_dependence_relation *ddr;
3711 struct loop *loop_nest = loop;
3713 while (loop_nest && loop_nest->outer && loop_nest->outer->outer)
3714 loop_nest = loop_nest->outer;
3716 nb_loops = loop_nest->level;
3718 /* If one of the data references is not computable, give up without
3719 spending time to compute other dependences. */
3720 if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
3722 struct data_dependence_relation *ddr;
3724 /* Insert a single relation into dependence_relations:
3726 ddr = initialize_data_dependence_relation (NULL, NULL);
3727 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
3728 build_classic_dist_vector (ddr, nb_loops, loop->depth);
3729 build_classic_dir_vector (ddr, nb_loops, loop->depth);
3733 allrelations = NULL;
3734 compute_all_dependences (*datarefs, compute_self_and_read_read_dependences,
3737 for (i = 0; VEC_iterate (ddr_p, allrelations, i, ddr); i++)
3739 if (build_classic_dist_vector (ddr, nb_loops, loop_nest->depth))
3741 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
3742 build_classic_dir_vector (ddr, nb_loops, loop_nest->depth);
3747 /* Entry point (for testing only). Analyze all the data references
3748 and the dependence relations.
3750 The data references are computed first.
3752 A relation on these nodes is represented by a complete graph. Some
3753 of the relations could be of no interest, thus the relations can be
3756 In the following function we compute all the relations. This is
3757 just a first implementation that is here for:
3758 - for showing how to ask for the dependence relations,
3759 - for the debugging the whole dependence graph,
3760 - for the dejagnu testcases and maintenance.
3762 It is possible to ask only for a part of the graph, avoiding to
3763 compute the whole dependence graph. The computed dependences are
3764 stored in a knowledge base (KB) such that later queries don't
3765 recompute the same information. The implementation of this KB is
3766 transparent to the optimizer, and thus the KB can be changed with a
3767 more efficient implementation, or the KB could be disabled. */
3770 analyze_all_data_dependences (struct loops *loops)
3773 varray_type datarefs;
3774 varray_type dependence_relations;
3775 int nb_data_refs = 10;
3777 VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
3778 VARRAY_GENERIC_PTR_INIT (dependence_relations,
3779 nb_data_refs * nb_data_refs,
3780 "dependence_relations");
3782 /* Compute DDs on the whole function. */
3783 compute_data_dependences_for_loop (loops->parray[0], false,
3784 &datarefs, &dependence_relations);
3788 dump_data_dependence_relations (dump_file, dependence_relations);
3789 fprintf (dump_file, "\n\n");
3791 if (dump_flags & TDF_DETAILS)
3792 dump_dist_dir_vectors (dump_file, dependence_relations);
3794 if (dump_flags & TDF_STATS)
3796 unsigned nb_top_relations = 0;
3797 unsigned nb_bot_relations = 0;
3798 unsigned nb_basename_differ = 0;
3799 unsigned nb_chrec_relations = 0;
3801 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
3803 struct data_dependence_relation *ddr;
3804 ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
3806 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
3809 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
3811 struct data_reference *a = DDR_A (ddr);
3812 struct data_reference *b = DDR_B (ddr);
3815 if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
3816 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
3817 || (base_object_differ_p (a, b, &differ_p)
3819 nb_basename_differ++;
3825 nb_chrec_relations++;
3828 gather_stats_on_scev_database ();
3832 free_dependence_relations (dependence_relations);
3833 free_data_refs (datarefs);
3836 /* Free the memory used by a data dependence relation DDR. */
3839 free_dependence_relation (struct data_dependence_relation *ddr)
3844 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
3845 varray_clear (DDR_SUBSCRIPTS (ddr));
3849 /* Free the memory used by the data dependence relations from
3850 DEPENDENCE_RELATIONS. */
3853 free_dependence_relations (varray_type dependence_relations)
3856 if (dependence_relations == NULL)
3859 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
3860 free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
3861 varray_clear (dependence_relations);
3864 /* Free the memory used by the data references from DATAREFS. */
3867 free_data_refs (varray_type datarefs)
3871 if (datarefs == NULL)
3874 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
3876 struct data_reference *dr = (struct data_reference *)
3877 VARRAY_GENERIC_PTR (datarefs, i);
3880 DR_FREE_ACCESS_FNS (dr);
3884 varray_clear (datarefs);