1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004 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, 59 Temple Place - Suite 330, 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"
85 /* These RTL headers are needed for basic-block.h. */
87 #include "basic-block.h"
88 #include "diagnostic.h"
89 #include "tree-flow.h"
90 #include "tree-dump.h"
93 #include "tree-chrec.h"
94 #include "tree-data-ref.h"
95 #include "tree-scalar-evolution.h"
96 #include "tree-pass.h"
98 /* This is the simplest data dependence test: determines whether the
99 data references A and B access the same array/region. Returns
100 false when the property is not computable at compile time.
101 Otherwise return true, and DIFFER_P will record the result. This
102 utility will not be necessary when alias_sets_conflict_p will be
103 less conservative. */
106 array_base_name_differ_p (struct data_reference *a,
107 struct data_reference *b,
110 tree base_a = DR_BASE_NAME (a);
111 tree base_b = DR_BASE_NAME (b);
112 tree ta = TREE_TYPE (base_a);
113 tree tb = TREE_TYPE (base_b);
116 /* Determine if same base. Example: for the array accesses
117 a[i], b[i] or pointer accesses *a, *b, bases are a, b. */
118 if (base_a == base_b)
124 /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
126 if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
127 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0))
133 /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */
134 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
135 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)
136 && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1))
143 /* Determine if different bases. */
145 /* At this point we know that base_a != base_b. However, pointer
146 accesses of the form x=(*p) and y=(*q), whose bases are p and q,
147 may still be pointing to the same base. In SSAed GIMPLE p and q will
148 be SSA_NAMES in this case. Therefore, here we check if they are
149 really two different declarations. */
150 if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
156 /* Compare two record/union bases s.a and t.b: s != t or (a != b and
157 s and t are not unions). */
158 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
159 && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
160 && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
161 && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
162 || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE
163 && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
164 && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
170 /* Compare a record/union access and an array access. */
171 if ((TREE_CODE (base_a) == VAR_DECL
172 && (TREE_CODE (base_b) == COMPONENT_REF
173 && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL))
174 || (TREE_CODE (base_b) == VAR_DECL
175 && (TREE_CODE (base_a) == COMPONENT_REF
176 && TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL)))
182 if (!alias_sets_conflict_p (get_alias_set (base_a), get_alias_set (base_b)))
188 /* An instruction writing through a restricted pointer is
189 "independent" of any instruction reading or writing through a
190 different pointer, in the same block/scope. */
191 if ((TREE_CODE (ta) == POINTER_TYPE && TYPE_RESTRICT (ta)
193 || (TREE_CODE (tb) == POINTER_TYPE && TYPE_RESTRICT (tb)
203 /* Returns true iff A divides B. */
206 tree_fold_divides_p (tree type,
210 /* Determines whether (A == gcd (A, B)). */
212 (fold (build (MINUS_EXPR, type, a, tree_fold_gcd (a, b))));
215 /* Compute the greatest common denominator of two numbers using
216 Euclid's algorithm. */
237 /* Returns true iff A divides B. */
240 int_divides_p (int a, int b)
242 return ((b % a) == 0);
247 /* Dump into FILE all the data references from DATAREFS. */
250 dump_data_references (FILE *file,
251 varray_type datarefs)
255 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
256 dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i));
259 /* Dump into FILE all the dependence relations from DDR. */
262 dump_data_dependence_relations (FILE *file,
267 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++)
268 dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i));
271 /* Dump function for a DATA_REFERENCE structure. */
274 dump_data_reference (FILE *outf,
275 struct data_reference *dr)
279 fprintf (outf, "(Data Ref: \n stmt: ");
280 print_generic_stmt (outf, DR_STMT (dr), 0);
281 fprintf (outf, " ref: ");
282 print_generic_stmt (outf, DR_REF (dr), 0);
283 fprintf (outf, " base_name: ");
284 print_generic_stmt (outf, DR_BASE_NAME (dr), 0);
286 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
288 fprintf (outf, " Access function %d: ", i);
289 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
291 fprintf (outf, ")\n");
294 /* Dump function for a SUBSCRIPT structure. */
297 dump_subscript (FILE *outf, struct subscript *subscript)
299 tree chrec = SUB_CONFLICTS_IN_A (subscript);
301 fprintf (outf, "\n (subscript \n");
302 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
303 print_generic_stmt (outf, chrec, 0);
304 if (chrec == chrec_known)
305 fprintf (outf, " (no dependence)\n");
306 else if (chrec_contains_undetermined (chrec))
307 fprintf (outf, " (don't know)\n");
310 tree last_iteration = SUB_LAST_CONFLICT (subscript);
311 fprintf (outf, " last_conflict: ");
312 print_generic_stmt (outf, last_iteration, 0);
315 chrec = SUB_CONFLICTS_IN_B (subscript);
316 fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
317 print_generic_stmt (outf, chrec, 0);
318 if (chrec == chrec_known)
319 fprintf (outf, " (no dependence)\n");
320 else if (chrec_contains_undetermined (chrec))
321 fprintf (outf, " (don't know)\n");
324 tree last_iteration = SUB_LAST_CONFLICT (subscript);
325 fprintf (outf, " last_conflict: ");
326 print_generic_stmt (outf, last_iteration, 0);
329 fprintf (outf, " (Subscript distance: ");
330 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
331 fprintf (outf, " )\n");
332 fprintf (outf, " )\n");
335 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
338 dump_data_dependence_relation (FILE *outf,
339 struct data_dependence_relation *ddr)
341 struct data_reference *dra, *drb;
345 fprintf (outf, "(Data Dep: \n");
346 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
347 fprintf (outf, " (don't know)\n");
349 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
350 fprintf (outf, " (no dependence)\n");
352 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
355 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
357 fprintf (outf, " access_fn_A: ");
358 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
359 fprintf (outf, " access_fn_B: ");
360 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
361 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
363 if (DDR_DIST_VECT (ddr))
365 fprintf (outf, " distance_vect: ");
366 print_lambda_vector (outf, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
368 if (DDR_DIR_VECT (ddr))
370 fprintf (outf, " direction_vect: ");
371 print_lambda_vector (outf, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
375 fprintf (outf, ")\n");
380 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
383 dump_data_dependence_direction (FILE *file,
384 enum data_dependence_direction dir)
400 case dir_positive_or_negative:
401 fprintf (file, "+-");
404 case dir_positive_or_equal:
405 fprintf (file, "+=");
408 case dir_negative_or_equal:
409 fprintf (file, "-=");
421 /* Dumps the distance and direction vectors in FILE. DDRS contains
422 the dependence relations, and VECT_SIZE is the size of the
423 dependence vectors, or in other words the number of loops in the
427 dump_dist_dir_vectors (FILE *file, varray_type ddrs)
431 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
433 struct data_dependence_relation *ddr =
434 (struct data_dependence_relation *)
435 VARRAY_GENERIC_PTR (ddrs, i);
436 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
437 && DDR_AFFINE_P (ddr))
439 fprintf (file, "DISTANCE_V (");
440 print_lambda_vector (file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
441 fprintf (file, ")\n");
442 fprintf (file, "DIRECTION_V (");
443 print_lambda_vector (file, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
444 fprintf (file, ")\n");
447 fprintf (file, "\n\n");
450 /* Dumps the data dependence relations DDRS in FILE. */
453 dump_ddrs (FILE *file, varray_type ddrs)
457 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
459 struct data_dependence_relation *ddr =
460 (struct data_dependence_relation *)
461 VARRAY_GENERIC_PTR (ddrs, i);
462 dump_data_dependence_relation (file, ddr);
464 fprintf (file, "\n\n");
469 /* Compute the lowest iteration bound for LOOP. It is an
473 compute_estimated_nb_iterations (struct loop *loop)
476 struct nb_iter_bound *bound, *next;
478 for (bound = loop->bounds; bound; bound = next)
481 estimation = bound->bound;
483 if (TREE_CODE (estimation) != INTEGER_CST)
486 if (loop->estimated_nb_iterations)
488 /* Update only if estimation is smaller. */
489 if (tree_int_cst_lt (estimation, loop->estimated_nb_iterations))
490 loop->estimated_nb_iterations = estimation;
493 loop->estimated_nb_iterations = estimation;
497 /* Estimate the number of iterations from the size of the data and the
501 estimate_niter_from_size_of_data (struct loop *loop,
507 tree array_size, data_size, element_size;
510 init = initial_condition (access_fn);
511 step = evolution_part_in_loop_num (access_fn, loop->num);
513 array_size = TYPE_SIZE (TREE_TYPE (opnd0));
514 element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
515 if (array_size == NULL_TREE
516 || element_size == NULL_TREE)
519 data_size = fold (build2 (EXACT_DIV_EXPR, integer_type_node,
520 array_size, element_size));
522 if (init != NULL_TREE
524 && TREE_CODE (init) == INTEGER_CST
525 && TREE_CODE (step) == INTEGER_CST)
527 estimation = fold (build2 (CEIL_DIV_EXPR, integer_type_node,
528 fold (build2 (MINUS_EXPR, integer_type_node,
529 data_size, init)), step));
531 record_estimate (loop, estimation, boolean_true_node, stmt);
535 /* Given an ARRAY_REF node REF, records its access functions.
536 Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
537 i.e. the constant "3", then recursively call the function on opnd0,
538 i.e. the ARRAY_REF "A[i]". The function returns the base name:
542 analyze_array_indexes (struct loop *loop,
543 varray_type *access_fns,
549 opnd0 = TREE_OPERAND (ref, 0);
550 opnd1 = TREE_OPERAND (ref, 1);
552 /* The detection of the evolution function for this data access is
553 postponed until the dependence test. This lazy strategy avoids
554 the computation of access functions that are of no interest for
556 access_fn = instantiate_parameters
557 (loop, analyze_scalar_evolution (loop, opnd1));
559 if (loop->estimated_nb_iterations == NULL_TREE)
560 estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
562 VARRAY_PUSH_TREE (*access_fns, access_fn);
564 /* Recursively record other array access functions. */
565 if (TREE_CODE (opnd0) == ARRAY_REF)
566 return analyze_array_indexes (loop, access_fns, opnd0, stmt);
568 /* Return the base name of the data access. */
573 /* For a data reference REF contained in the statement STMT, initialize
574 a DATA_REFERENCE structure, and return it. IS_READ flag has to be
575 set to true when REF is in the right hand side of an
578 struct data_reference *
579 analyze_array (tree stmt, tree ref, bool is_read)
581 struct data_reference *res;
583 if (dump_file && (dump_flags & TDF_DETAILS))
585 fprintf (dump_file, "(analyze_array \n");
586 fprintf (dump_file, " (ref = ");
587 print_generic_stmt (dump_file, ref, 0);
588 fprintf (dump_file, ")\n");
591 res = xmalloc (sizeof (struct data_reference));
593 DR_STMT (res) = stmt;
595 VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 3, "access_fns");
596 DR_BASE_NAME (res) = analyze_array_indexes
597 (loop_containing_stmt (stmt), &(DR_ACCESS_FNS (res)), ref, stmt);
598 DR_IS_READ (res) = is_read;
600 if (dump_file && (dump_flags & TDF_DETAILS))
601 fprintf (dump_file, ")\n");
606 /* For a data reference REF contained in the statement STMT, initialize
607 a DATA_REFERENCE structure, and return it. */
609 struct data_reference *
610 init_data_ref (tree stmt,
616 struct data_reference *res;
618 if (dump_file && (dump_flags & TDF_DETAILS))
620 fprintf (dump_file, "(init_data_ref \n");
621 fprintf (dump_file, " (ref = ");
622 print_generic_stmt (dump_file, ref, 0);
623 fprintf (dump_file, ")\n");
626 res = xmalloc (sizeof (struct data_reference));
628 DR_STMT (res) = stmt;
630 VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 5, "access_fns");
631 DR_BASE_NAME (res) = base;
632 VARRAY_PUSH_TREE (DR_ACCESS_FNS (res), access_fn);
633 DR_IS_READ (res) = is_read;
635 if (dump_file && (dump_flags & TDF_DETAILS))
636 fprintf (dump_file, ")\n");
643 /* Returns true when all the functions of a tree_vec CHREC are the
647 all_chrecs_equal_p (tree chrec)
651 for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
653 tree chrec_j = TREE_VEC_ELT (chrec, j);
654 tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1);
657 (integer_type_node, chrec_j, chrec_j_1)))
663 /* Determine for each subscript in the data dependence relation DDR
667 compute_subscript_distance (struct data_dependence_relation *ddr)
669 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
673 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
675 tree conflicts_a, conflicts_b, difference;
676 struct subscript *subscript;
678 subscript = DDR_SUBSCRIPT (ddr, i);
679 conflicts_a = SUB_CONFLICTS_IN_A (subscript);
680 conflicts_b = SUB_CONFLICTS_IN_B (subscript);
682 if (TREE_CODE (conflicts_a) == TREE_VEC)
684 if (!all_chrecs_equal_p (conflicts_a))
686 SUB_DISTANCE (subscript) = chrec_dont_know;
690 conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
693 if (TREE_CODE (conflicts_b) == TREE_VEC)
695 if (!all_chrecs_equal_p (conflicts_b))
697 SUB_DISTANCE (subscript) = chrec_dont_know;
701 conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
704 difference = chrec_fold_minus
705 (integer_type_node, conflicts_b, conflicts_a);
707 if (evolution_function_is_constant_p (difference))
708 SUB_DISTANCE (subscript) = difference;
711 SUB_DISTANCE (subscript) = chrec_dont_know;
716 /* Initialize a ddr. */
718 struct data_dependence_relation *
719 initialize_data_dependence_relation (struct data_reference *a,
720 struct data_reference *b)
722 struct data_dependence_relation *res;
725 res = xmalloc (sizeof (struct data_dependence_relation));
729 if (a == NULL || b == NULL
730 || DR_BASE_NAME (a) == NULL_TREE
731 || DR_BASE_NAME (b) == NULL_TREE)
732 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
734 /* When the dimensions of A and B differ, we directly initialize
735 the relation to "there is no dependence": chrec_known. */
736 else if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
737 || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
738 DDR_ARE_DEPENDENT (res) = chrec_known;
743 DDR_AFFINE_P (res) = true;
744 DDR_ARE_DEPENDENT (res) = NULL_TREE;
745 DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
746 DDR_SIZE_VECT (res) = 0;
747 DDR_DIST_VECT (res) = NULL;
748 DDR_DIR_VECT (res) = NULL;
750 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
752 struct subscript *subscript;
754 subscript = xmalloc (sizeof (struct subscript));
755 SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
756 SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
757 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
758 SUB_DISTANCE (subscript) = chrec_dont_know;
759 VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
766 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
770 finalize_ddr_dependent (struct data_dependence_relation *ddr,
773 if (dump_file && (dump_flags & TDF_DETAILS))
775 fprintf (dump_file, "(dependence classified: ");
776 print_generic_expr (dump_file, chrec, 0);
777 fprintf (dump_file, ")\n");
780 DDR_ARE_DEPENDENT (ddr) = chrec;
781 varray_clear (DDR_SUBSCRIPTS (ddr));
784 /* The dependence relation DDR cannot be represented by a distance
788 non_affine_dependence_relation (struct data_dependence_relation *ddr)
790 if (dump_file && (dump_flags & TDF_DETAILS))
791 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
793 DDR_AFFINE_P (ddr) = false;
798 /* This section contains the classic Banerjee tests. */
800 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
801 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
804 ziv_subscript_p (tree chrec_a,
807 return (evolution_function_is_constant_p (chrec_a)
808 && evolution_function_is_constant_p (chrec_b));
811 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
812 variable, i.e., if the SIV (Single Index Variable) test is true. */
815 siv_subscript_p (tree chrec_a,
818 if ((evolution_function_is_constant_p (chrec_a)
819 && evolution_function_is_univariate_p (chrec_b))
820 || (evolution_function_is_constant_p (chrec_b)
821 && evolution_function_is_univariate_p (chrec_a)))
824 if (evolution_function_is_univariate_p (chrec_a)
825 && evolution_function_is_univariate_p (chrec_b))
827 switch (TREE_CODE (chrec_a))
829 case POLYNOMIAL_CHREC:
830 switch (TREE_CODE (chrec_b))
832 case POLYNOMIAL_CHREC:
833 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
848 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
849 *OVERLAPS_B are initialized to the functions that describe the
850 relation between the elements accessed twice by CHREC_A and
851 CHREC_B. For k >= 0, the following property is verified:
853 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
856 analyze_ziv_subscript (tree chrec_a,
860 tree *last_conflicts)
864 if (dump_file && (dump_flags & TDF_DETAILS))
865 fprintf (dump_file, "(analyze_ziv_subscript \n");
867 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
869 switch (TREE_CODE (difference))
872 if (integer_zerop (difference))
874 /* The difference is equal to zero: the accessed index
875 overlaps for each iteration in the loop. */
876 *overlaps_a = integer_zero_node;
877 *overlaps_b = integer_zero_node;
878 *last_conflicts = chrec_dont_know;
882 /* The accesses do not overlap. */
883 *overlaps_a = chrec_known;
884 *overlaps_b = chrec_known;
885 *last_conflicts = integer_zero_node;
890 /* We're not sure whether the indexes overlap. For the moment,
891 conservatively answer "don't know". */
892 *overlaps_a = chrec_dont_know;
893 *overlaps_b = chrec_dont_know;
894 *last_conflicts = chrec_dont_know;
898 if (dump_file && (dump_flags & TDF_DETAILS))
899 fprintf (dump_file, ")\n");
902 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
903 constant, and CHREC_B is an affine function. *OVERLAPS_A and
904 *OVERLAPS_B are initialized to the functions that describe the
905 relation between the elements accessed twice by CHREC_A and
906 CHREC_B. For k >= 0, the following property is verified:
908 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
911 analyze_siv_subscript_cst_affine (tree chrec_a,
915 tree *last_conflicts)
917 bool value0, value1, value2;
918 tree difference = chrec_fold_minus
919 (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
921 if (!chrec_is_positive (initial_condition (difference), &value0))
923 *overlaps_a = chrec_dont_know;
924 *overlaps_b = chrec_dont_know;
925 *last_conflicts = chrec_dont_know;
932 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
934 *overlaps_a = chrec_dont_know;
935 *overlaps_b = chrec_dont_know;
936 *last_conflicts = chrec_dont_know;
948 if (tree_fold_divides_p
949 (integer_type_node, CHREC_RIGHT (chrec_b), difference))
951 *overlaps_a = integer_zero_node;
953 (build (EXACT_DIV_EXPR, integer_type_node,
954 fold (build1 (ABS_EXPR, integer_type_node, difference)),
955 CHREC_RIGHT (chrec_b)));
956 *last_conflicts = integer_one_node;
960 /* When the step does not divides the difference, there are
964 *overlaps_a = chrec_known;
965 *overlaps_b = chrec_known;
966 *last_conflicts = integer_zero_node;
975 chrec_b = {10, +, -1}
977 In this case, chrec_a will not overlap with chrec_b. */
978 *overlaps_a = chrec_known;
979 *overlaps_b = chrec_known;
980 *last_conflicts = integer_zero_node;
987 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
989 *overlaps_a = chrec_dont_know;
990 *overlaps_b = chrec_dont_know;
991 *last_conflicts = chrec_dont_know;
1000 chrec_b = {10, +, -1}
1002 if (tree_fold_divides_p
1003 (integer_type_node, CHREC_RIGHT (chrec_b), difference))
1005 *overlaps_a = integer_zero_node;
1007 (build (EXACT_DIV_EXPR, integer_type_node, difference,
1008 CHREC_RIGHT (chrec_b)));
1009 *last_conflicts = integer_one_node;
1013 /* When the step does not divides the difference, there
1017 *overlaps_a = chrec_known;
1018 *overlaps_b = chrec_known;
1019 *last_conflicts = integer_zero_node;
1029 In this case, chrec_a will not overlap with chrec_b. */
1030 *overlaps_a = chrec_known;
1031 *overlaps_b = chrec_known;
1032 *last_conflicts = integer_zero_node;
1040 /* Helper recursive function for initializing the matrix A. Returns
1041 the initial value of CHREC. */
1044 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
1048 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1049 return int_cst_value (chrec);
1051 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
1052 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
1055 #define FLOOR_DIV(x,y) ((x) / (y))
1057 /* Solves the special case of the Diophantine equation:
1058 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1060 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1061 number of iterations that loops X and Y run. The overlaps will be
1062 constructed as evolutions in dimension DIM. */
1065 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
1066 tree *overlaps_a, tree *overlaps_b,
1067 tree *last_conflicts, int dim)
1069 if (((step_a > 0 && step_b > 0)
1070 || (step_a < 0 && step_b < 0)))
1072 int step_overlaps_a, step_overlaps_b;
1073 int gcd_steps_a_b, last_conflict, tau2;
1075 gcd_steps_a_b = gcd (step_a, step_b);
1076 step_overlaps_a = step_b / gcd_steps_a_b;
1077 step_overlaps_b = step_a / gcd_steps_a_b;
1079 tau2 = FLOOR_DIV (niter, step_overlaps_a);
1080 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
1081 last_conflict = tau2;
1083 *overlaps_a = build_polynomial_chrec
1084 (dim, integer_zero_node,
1085 build_int_cst (NULL_TREE, step_overlaps_a));
1086 *overlaps_b = build_polynomial_chrec
1087 (dim, integer_zero_node,
1088 build_int_cst (NULL_TREE, step_overlaps_b));
1089 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
1094 *overlaps_a = integer_zero_node;
1095 *overlaps_b = integer_zero_node;
1096 *last_conflicts = integer_zero_node;
1101 /* Solves the special case of a Diophantine equation where CHREC_A is
1102 an affine bivariate function, and CHREC_B is an affine univariate
1103 function. For example,
1105 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1107 has the following overlapping functions:
1109 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1110 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1111 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1113 FORNOW: This is a specialized implementation for a case occuring in
1114 a common benchmark. Implement the general algorithm. */
1117 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
1118 tree *overlaps_a, tree *overlaps_b,
1119 tree *last_conflicts)
1121 bool xz_p, yz_p, xyz_p;
1122 int step_x, step_y, step_z;
1123 int niter_x, niter_y, niter_z, niter;
1124 tree numiter_x, numiter_y, numiter_z;
1125 tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
1126 tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
1127 tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
1129 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
1130 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
1131 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
1133 numiter_x = number_of_iterations_in_loop
1134 (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]);
1135 numiter_y = number_of_iterations_in_loop
1136 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
1137 numiter_z = number_of_iterations_in_loop
1138 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
1140 if (TREE_CODE (numiter_x) != INTEGER_CST)
1141 numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]
1142 ->estimated_nb_iterations;
1143 if (TREE_CODE (numiter_y) != INTEGER_CST)
1144 numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]
1145 ->estimated_nb_iterations;
1146 if (TREE_CODE (numiter_z) != INTEGER_CST)
1147 numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
1148 ->estimated_nb_iterations;
1150 if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
1151 || numiter_z == NULL_TREE)
1153 *overlaps_a = chrec_dont_know;
1154 *overlaps_b = chrec_dont_know;
1155 *last_conflicts = chrec_dont_know;
1159 niter_x = int_cst_value (numiter_x);
1160 niter_y = int_cst_value (numiter_y);
1161 niter_z = int_cst_value (numiter_z);
1163 niter = MIN (niter_x, niter_z);
1164 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
1167 &last_conflicts_xz, 1);
1168 niter = MIN (niter_y, niter_z);
1169 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
1172 &last_conflicts_yz, 2);
1173 niter = MIN (niter_x, niter_z);
1174 niter = MIN (niter_y, niter);
1175 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
1178 &last_conflicts_xyz, 3);
1180 xz_p = !integer_zerop (last_conflicts_xz);
1181 yz_p = !integer_zerop (last_conflicts_yz);
1182 xyz_p = !integer_zerop (last_conflicts_xyz);
1184 if (xz_p || yz_p || xyz_p)
1186 *overlaps_a = make_tree_vec (2);
1187 TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
1188 TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
1189 *overlaps_b = integer_zero_node;
1192 TREE_VEC_ELT (*overlaps_a, 0) =
1193 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
1196 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
1197 *last_conflicts = last_conflicts_xz;
1201 TREE_VEC_ELT (*overlaps_a, 1) =
1202 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
1205 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
1206 *last_conflicts = last_conflicts_yz;
1210 TREE_VEC_ELT (*overlaps_a, 0) =
1211 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
1213 TREE_VEC_ELT (*overlaps_a, 1) =
1214 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
1217 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
1218 *last_conflicts = last_conflicts_xyz;
1223 *overlaps_a = integer_zero_node;
1224 *overlaps_b = integer_zero_node;
1225 *last_conflicts = integer_zero_node;
1229 /* Determines the overlapping elements due to accesses CHREC_A and
1230 CHREC_B, that are affine functions. This is a part of the
1231 subscript analyzer. */
1234 analyze_subscript_affine_affine (tree chrec_a,
1238 tree *last_conflicts)
1240 unsigned nb_vars_a, nb_vars_b, dim;
1241 int init_a, init_b, gamma, gcd_alpha_beta;
1243 lambda_matrix A, U, S;
1245 if (dump_file && (dump_flags & TDF_DETAILS))
1246 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
1248 /* For determining the initial intersection, we have to solve a
1249 Diophantine equation. This is the most time consuming part.
1251 For answering to the question: "Is there a dependence?" we have
1252 to prove that there exists a solution to the Diophantine
1253 equation, and that the solution is in the iteration domain,
1254 i.e. the solution is positive or zero, and that the solution
1255 happens before the upper bound loop.nb_iterations. Otherwise
1256 there is no dependence. This function outputs a description of
1257 the iterations that hold the intersections. */
1260 nb_vars_a = nb_vars_in_chrec (chrec_a);
1261 nb_vars_b = nb_vars_in_chrec (chrec_b);
1263 dim = nb_vars_a + nb_vars_b;
1264 U = lambda_matrix_new (dim, dim);
1265 A = lambda_matrix_new (dim, 1);
1266 S = lambda_matrix_new (dim, 1);
1268 init_a = initialize_matrix_A (A, chrec_a, 0, 1);
1269 init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
1270 gamma = init_b - init_a;
1272 /* Don't do all the hard work of solving the Diophantine equation
1273 when we already know the solution: for example,
1276 | gamma = 3 - 3 = 0.
1277 Then the first overlap occurs during the first iterations:
1278 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
1282 if (nb_vars_a == 1 && nb_vars_b == 1)
1285 int niter, niter_a, niter_b;
1286 tree numiter_a, numiter_b;
1288 numiter_a = number_of_iterations_in_loop
1289 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
1290 numiter_b = number_of_iterations_in_loop
1291 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
1293 if (TREE_CODE (numiter_a) != INTEGER_CST)
1294 numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
1295 ->estimated_nb_iterations;
1296 if (TREE_CODE (numiter_b) != INTEGER_CST)
1297 numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
1298 ->estimated_nb_iterations;
1299 if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
1301 *overlaps_a = chrec_dont_know;
1302 *overlaps_b = chrec_dont_know;
1303 *last_conflicts = chrec_dont_know;
1307 niter_a = int_cst_value (numiter_a);
1308 niter_b = int_cst_value (numiter_b);
1309 niter = MIN (niter_a, niter_b);
1311 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
1312 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
1314 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
1315 overlaps_a, overlaps_b,
1319 else if (nb_vars_a == 2 && nb_vars_b == 1)
1320 compute_overlap_steps_for_affine_1_2
1321 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
1323 else if (nb_vars_a == 1 && nb_vars_b == 2)
1324 compute_overlap_steps_for_affine_1_2
1325 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
1329 *overlaps_a = chrec_dont_know;
1330 *overlaps_b = chrec_dont_know;
1331 *last_conflicts = chrec_dont_know;
1337 lambda_matrix_right_hermite (A, dim, 1, S, U);
1342 lambda_matrix_row_negate (U, dim, 0);
1344 gcd_alpha_beta = S[0][0];
1346 /* The classic "gcd-test". */
1347 if (!int_divides_p (gcd_alpha_beta, gamma))
1349 /* The "gcd-test" has determined that there is no integer
1350 solution, i.e. there is no dependence. */
1351 *overlaps_a = chrec_known;
1352 *overlaps_b = chrec_known;
1353 *last_conflicts = integer_zero_node;
1356 /* Both access functions are univariate. This includes SIV and MIV cases. */
1357 else if (nb_vars_a == 1 && nb_vars_b == 1)
1359 /* Both functions should have the same evolution sign. */
1360 if (((A[0][0] > 0 && -A[1][0] > 0)
1361 || (A[0][0] < 0 && -A[1][0] < 0)))
1363 /* The solutions are given by:
1365 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
1368 For a given integer t. Using the following variables,
1370 | i0 = u11 * gamma / gcd_alpha_beta
1371 | j0 = u12 * gamma / gcd_alpha_beta
1378 | y0 = j0 + j1 * t. */
1382 /* X0 and Y0 are the first iterations for which there is a
1383 dependence. X0, Y0 are two solutions of the Diophantine
1384 equation: chrec_a (X0) = chrec_b (Y0). */
1386 int niter, niter_a, niter_b;
1387 tree numiter_a, numiter_b;
1389 numiter_a = number_of_iterations_in_loop
1390 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
1391 numiter_b = number_of_iterations_in_loop
1392 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
1394 if (TREE_CODE (numiter_a) != INTEGER_CST)
1395 numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
1396 ->estimated_nb_iterations;
1397 if (TREE_CODE (numiter_b) != INTEGER_CST)
1398 numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
1399 ->estimated_nb_iterations;
1400 if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
1402 *overlaps_a = chrec_dont_know;
1403 *overlaps_b = chrec_dont_know;
1404 *last_conflicts = chrec_dont_know;
1408 niter_a = int_cst_value (numiter_a);
1409 niter_b = int_cst_value (numiter_b);
1410 niter = MIN (niter_a, niter_b);
1412 i0 = U[0][0] * gamma / gcd_alpha_beta;
1413 j0 = U[0][1] * gamma / gcd_alpha_beta;
1417 if ((i1 == 0 && i0 < 0)
1418 || (j1 == 0 && j0 < 0))
1420 /* There is no solution.
1421 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
1422 falls in here, but for the moment we don't look at the
1423 upper bound of the iteration domain. */
1424 *overlaps_a = chrec_known;
1425 *overlaps_b = chrec_known;
1426 *last_conflicts = integer_zero_node;
1433 tau1 = CEIL (-i0, i1);
1434 tau2 = FLOOR_DIV (niter - i0, i1);
1439 tau1 = MAX (tau1, CEIL (-j0, j1));
1440 tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
1442 x0 = (i1 * tau1 + i0) % i1;
1443 y0 = (j1 * tau1 + j0) % j1;
1444 tau1 = (x0 - i0)/i1;
1445 last_conflict = tau2 - tau1;
1447 *overlaps_a = build_polynomial_chrec
1449 build_int_cst (NULL_TREE, x0),
1450 build_int_cst (NULL_TREE, i1));
1451 *overlaps_b = build_polynomial_chrec
1453 build_int_cst (NULL_TREE, y0),
1454 build_int_cst (NULL_TREE, j1));
1455 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
1459 /* FIXME: For the moment, the upper bound of the
1460 iteration domain for j is not checked. */
1461 *overlaps_a = chrec_dont_know;
1462 *overlaps_b = chrec_dont_know;
1463 *last_conflicts = chrec_dont_know;
1469 /* FIXME: For the moment, the upper bound of the
1470 iteration domain for i is not checked. */
1471 *overlaps_a = chrec_dont_know;
1472 *overlaps_b = chrec_dont_know;
1473 *last_conflicts = chrec_dont_know;
1479 *overlaps_a = chrec_dont_know;
1480 *overlaps_b = chrec_dont_know;
1481 *last_conflicts = chrec_dont_know;
1487 *overlaps_a = chrec_dont_know;
1488 *overlaps_b = chrec_dont_know;
1489 *last_conflicts = chrec_dont_know;
1493 if (dump_file && (dump_flags & TDF_DETAILS))
1495 fprintf (dump_file, " (overlaps_a = ");
1496 print_generic_expr (dump_file, *overlaps_a, 0);
1497 fprintf (dump_file, ")\n (overlaps_b = ");
1498 print_generic_expr (dump_file, *overlaps_b, 0);
1499 fprintf (dump_file, ")\n");
1502 if (dump_file && (dump_flags & TDF_DETAILS))
1503 fprintf (dump_file, ")\n");
1506 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
1507 *OVERLAPS_B are initialized to the functions that describe the
1508 relation between the elements accessed twice by CHREC_A and
1509 CHREC_B. For k >= 0, the following property is verified:
1511 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1514 analyze_siv_subscript (tree chrec_a,
1518 tree *last_conflicts)
1520 if (dump_file && (dump_flags & TDF_DETAILS))
1521 fprintf (dump_file, "(analyze_siv_subscript \n");
1523 if (evolution_function_is_constant_p (chrec_a)
1524 && evolution_function_is_affine_p (chrec_b))
1525 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
1526 overlaps_a, overlaps_b, last_conflicts);
1528 else if (evolution_function_is_affine_p (chrec_a)
1529 && evolution_function_is_constant_p (chrec_b))
1530 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
1531 overlaps_b, overlaps_a, last_conflicts);
1533 else if (evolution_function_is_affine_p (chrec_a)
1534 && evolution_function_is_affine_p (chrec_b))
1535 analyze_subscript_affine_affine (chrec_a, chrec_b,
1536 overlaps_a, overlaps_b, last_conflicts);
1539 *overlaps_a = chrec_dont_know;
1540 *overlaps_b = chrec_dont_know;
1541 *last_conflicts = chrec_dont_know;
1544 if (dump_file && (dump_flags & TDF_DETAILS))
1545 fprintf (dump_file, ")\n");
1548 /* Return true when the evolution steps of an affine CHREC divide the
1552 chrec_steps_divide_constant_p (tree chrec,
1555 switch (TREE_CODE (chrec))
1557 case POLYNOMIAL_CHREC:
1558 return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst)
1559 && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
1562 /* On the initial condition, return true. */
1567 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
1568 *OVERLAPS_B are initialized to the functions that describe the
1569 relation between the elements accessed twice by CHREC_A and
1570 CHREC_B. For k >= 0, the following property is verified:
1572 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1575 analyze_miv_subscript (tree chrec_a,
1579 tree *last_conflicts)
1581 /* FIXME: This is a MIV subscript, not yet handled.
1582 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
1585 In the SIV test we had to solve a Diophantine equation with two
1586 variables. In the MIV case we have to solve a Diophantine
1587 equation with 2*n variables (if the subscript uses n IVs).
1591 if (dump_file && (dump_flags & TDF_DETAILS))
1592 fprintf (dump_file, "(analyze_miv_subscript \n");
1594 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
1596 if (chrec_zerop (difference))
1598 /* Access functions are the same: all the elements are accessed
1599 in the same order. */
1600 *overlaps_a = integer_zero_node;
1601 *overlaps_b = integer_zero_node;
1602 *last_conflicts = number_of_iterations_in_loop
1603 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
1606 else if (evolution_function_is_constant_p (difference)
1607 /* For the moment, the following is verified:
1608 evolution_function_is_affine_multivariate_p (chrec_a) */
1609 && !chrec_steps_divide_constant_p (chrec_a, difference))
1611 /* testsuite/.../ssa-chrec-33.c
1612 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
1614 The difference is 1, and the evolution steps are equal to 2,
1615 consequently there are no overlapping elements. */
1616 *overlaps_a = chrec_known;
1617 *overlaps_b = chrec_known;
1618 *last_conflicts = integer_zero_node;
1621 else if (evolution_function_is_affine_multivariate_p (chrec_a)
1622 && evolution_function_is_affine_multivariate_p (chrec_b))
1624 /* testsuite/.../ssa-chrec-35.c
1625 {0, +, 1}_2 vs. {0, +, 1}_3
1626 the overlapping elements are respectively located at iterations:
1627 {0, +, 1}_x and {0, +, 1}_x,
1628 in other words, we have the equality:
1629 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
1632 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
1633 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
1635 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
1636 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
1638 analyze_subscript_affine_affine (chrec_a, chrec_b,
1639 overlaps_a, overlaps_b, last_conflicts);
1644 /* When the analysis is too difficult, answer "don't know". */
1645 *overlaps_a = chrec_dont_know;
1646 *overlaps_b = chrec_dont_know;
1647 *last_conflicts = chrec_dont_know;
1650 if (dump_file && (dump_flags & TDF_DETAILS))
1651 fprintf (dump_file, ")\n");
1654 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
1655 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
1656 two functions that describe the iterations that contain conflicting
1659 Remark: For an integer k >= 0, the following equality is true:
1661 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
1665 analyze_overlapping_iterations (tree chrec_a,
1667 tree *overlap_iterations_a,
1668 tree *overlap_iterations_b,
1669 tree *last_conflicts)
1671 if (dump_file && (dump_flags & TDF_DETAILS))
1673 fprintf (dump_file, "(analyze_overlapping_iterations \n");
1674 fprintf (dump_file, " (chrec_a = ");
1675 print_generic_expr (dump_file, chrec_a, 0);
1676 fprintf (dump_file, ")\n chrec_b = ");
1677 print_generic_expr (dump_file, chrec_b, 0);
1678 fprintf (dump_file, ")\n");
1681 if (chrec_a == NULL_TREE
1682 || chrec_b == NULL_TREE
1683 || chrec_contains_undetermined (chrec_a)
1684 || chrec_contains_undetermined (chrec_b)
1685 || chrec_contains_symbols (chrec_a)
1686 || chrec_contains_symbols (chrec_b))
1688 *overlap_iterations_a = chrec_dont_know;
1689 *overlap_iterations_b = chrec_dont_know;
1692 else if (ziv_subscript_p (chrec_a, chrec_b))
1693 analyze_ziv_subscript (chrec_a, chrec_b,
1694 overlap_iterations_a, overlap_iterations_b,
1697 else if (siv_subscript_p (chrec_a, chrec_b))
1698 analyze_siv_subscript (chrec_a, chrec_b,
1699 overlap_iterations_a, overlap_iterations_b,
1703 analyze_miv_subscript (chrec_a, chrec_b,
1704 overlap_iterations_a, overlap_iterations_b,
1707 if (dump_file && (dump_flags & TDF_DETAILS))
1709 fprintf (dump_file, " (overlap_iterations_a = ");
1710 print_generic_expr (dump_file, *overlap_iterations_a, 0);
1711 fprintf (dump_file, ")\n (overlap_iterations_b = ");
1712 print_generic_expr (dump_file, *overlap_iterations_b, 0);
1713 fprintf (dump_file, ")\n");
1719 /* This section contains the affine functions dependences detector. */
1721 /* Computes the conflicting iterations, and initialize DDR. */
1724 subscript_dependence_tester (struct data_dependence_relation *ddr)
1727 struct data_reference *dra = DDR_A (ddr);
1728 struct data_reference *drb = DDR_B (ddr);
1729 tree last_conflicts;
1731 if (dump_file && (dump_flags & TDF_DETAILS))
1732 fprintf (dump_file, "(subscript_dependence_tester \n");
1734 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1736 tree overlaps_a, overlaps_b;
1737 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1739 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
1740 DR_ACCESS_FN (drb, i),
1741 &overlaps_a, &overlaps_b,
1744 if (chrec_contains_undetermined (overlaps_a)
1745 || chrec_contains_undetermined (overlaps_b))
1747 finalize_ddr_dependent (ddr, chrec_dont_know);
1751 else if (overlaps_a == chrec_known
1752 || overlaps_b == chrec_known)
1754 finalize_ddr_dependent (ddr, chrec_known);
1760 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
1761 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
1762 SUB_LAST_CONFLICT (subscript) = last_conflicts;
1766 if (dump_file && (dump_flags & TDF_DETAILS))
1767 fprintf (dump_file, ")\n");
1770 /* Compute the classic per loop distance vector.
1772 DDR is the data dependence relation to build a vector from.
1773 NB_LOOPS is the total number of loops we are considering.
1774 FIRST_LOOP is the loop->num of the first loop in the analyzed
1776 Return FALSE if the dependence relation is outside of the loop nest
1777 starting with FIRST_LOOP.
1778 Return TRUE otherwise. */
1781 build_classic_dist_vector (struct data_dependence_relation *ddr,
1782 int nb_loops, unsigned int first_loop)
1785 lambda_vector dist_v, init_v;
1787 dist_v = lambda_vector_new (nb_loops);
1788 init_v = lambda_vector_new (nb_loops);
1789 lambda_vector_clear (dist_v, nb_loops);
1790 lambda_vector_clear (init_v, nb_loops);
1792 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
1795 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1797 tree access_fn_a, access_fn_b;
1798 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1800 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
1802 non_affine_dependence_relation (ddr);
1806 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
1807 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
1809 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
1810 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
1813 int loop_nb_a = CHREC_VARIABLE (access_fn_a);
1814 int loop_nb_b = CHREC_VARIABLE (access_fn_b);
1815 struct loop *loop_a = current_loops->parray[loop_nb_a];
1816 struct loop *loop_b = current_loops->parray[loop_nb_b];
1817 struct loop *loop_first = current_loops->parray[first_loop];
1819 /* If the loop for either variable is at a lower depth than
1820 the first_loop's depth, then we can't possibly have a
1821 dependency at this level of the loop. */
1823 if (loop_a->depth < loop_first->depth
1824 || loop_b->depth < loop_first->depth)
1827 if (loop_nb_a != loop_nb_b
1828 && !flow_loop_nested_p (loop_a, loop_b)
1829 && !flow_loop_nested_p (loop_b, loop_a))
1831 /* Example: when there are two consecutive loops,
1840 the dependence relation cannot be captured by the
1841 distance abstraction. */
1842 non_affine_dependence_relation (ddr);
1846 /* The dependence is carried by the outermost loop. Example:
1853 In this case, the dependence is carried by loop_1. */
1854 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
1855 loop_nb -= first_loop;
1857 /* If the loop number is still greater than the number of
1858 loops we've been asked to analyze, or negative,
1859 something is borked. */
1860 gcc_assert (loop_nb >= 0);
1861 gcc_assert (loop_nb < nb_loops);
1862 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
1864 non_affine_dependence_relation (ddr);
1868 dist = int_cst_value (SUB_DISTANCE (subscript));
1870 /* This is the subscript coupling test.
1875 There is no dependence. */
1876 if (init_v[loop_nb] != 0
1877 && dist_v[loop_nb] != dist)
1879 finalize_ddr_dependent (ddr, chrec_known);
1883 dist_v[loop_nb] = dist;
1884 init_v[loop_nb] = 1;
1888 /* There is a distance of 1 on all the outer loops:
1890 Example: there is a dependence of distance 1 on loop_1 for the array A.
1896 struct loop *lca, *loop_a, *loop_b;
1897 struct data_reference *a = DDR_A (ddr);
1898 struct data_reference *b = DDR_B (ddr);
1900 loop_a = loop_containing_stmt (DR_STMT (a));
1901 loop_b = loop_containing_stmt (DR_STMT (b));
1903 /* Get the common ancestor loop. */
1904 lca = find_common_loop (loop_a, loop_b);
1907 lca_nb -= first_loop;
1908 gcc_assert (lca_nb >= 0);
1909 gcc_assert (lca_nb < nb_loops);
1911 /* For each outer loop where init_v is not set, the accesses are
1912 in dependence of distance 1 in the loop. */
1915 && init_v[lca_nb] == 0)
1922 lca_nb = lca->num - first_loop;
1923 while (lca->depth != 0)
1925 /* If we're considering just a sub-nest, then don't record
1926 any information on the outer loops. */
1930 gcc_assert (lca_nb < nb_loops);
1932 if (init_v[lca_nb] == 0)
1935 lca_nb = lca->num - first_loop;
1941 DDR_DIST_VECT (ddr) = dist_v;
1942 DDR_SIZE_VECT (ddr) = nb_loops;
1946 /* Compute the classic per loop direction vector.
1948 DDR is the data dependence relation to build a vector from.
1949 NB_LOOPS is the total number of loops we are considering.
1950 FIRST_LOOP is the loop->num of the first loop in the analyzed
1952 Return FALSE if the dependence relation is outside of the loop nest
1953 starting with FIRST_LOOP.
1954 Return TRUE otherwise. */
1957 build_classic_dir_vector (struct data_dependence_relation *ddr,
1958 int nb_loops, unsigned int first_loop)
1961 lambda_vector dir_v, init_v;
1963 dir_v = lambda_vector_new (nb_loops);
1964 init_v = lambda_vector_new (nb_loops);
1965 lambda_vector_clear (dir_v, nb_loops);
1966 lambda_vector_clear (init_v, nb_loops);
1968 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
1971 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1973 tree access_fn_a, access_fn_b;
1974 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1976 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
1978 non_affine_dependence_relation (ddr);
1982 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
1983 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
1984 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
1985 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
1988 enum data_dependence_direction dir = dir_star;
1989 int loop_nb_a = CHREC_VARIABLE (access_fn_a);
1990 int loop_nb_b = CHREC_VARIABLE (access_fn_b);
1991 struct loop *loop_a = current_loops->parray[loop_nb_a];
1992 struct loop *loop_b = current_loops->parray[loop_nb_b];
1993 struct loop *loop_first = current_loops->parray[first_loop];
1995 /* If the loop for either variable is at a lower depth than
1996 the first_loop's depth, then we can't possibly have a
1997 dependency at this level of the loop. */
1999 if (loop_a->depth < loop_first->depth
2000 || loop_b->depth < loop_first->depth)
2003 if (loop_nb_a != loop_nb_b
2004 && !flow_loop_nested_p (loop_a, loop_b)
2005 && !flow_loop_nested_p (loop_b, loop_a))
2007 /* Example: when there are two consecutive loops,
2016 the dependence relation cannot be captured by the
2017 distance abstraction. */
2018 non_affine_dependence_relation (ddr);
2022 /* The dependence is carried by the outermost loop. Example:
2029 In this case, the dependence is carried by loop_1. */
2030 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
2031 loop_nb -= first_loop;
2033 /* If the loop number is still greater than the number of
2034 loops we've been asked to analyze, or negative,
2035 something is borked. */
2036 gcc_assert (loop_nb >= 0);
2037 gcc_assert (loop_nb < nb_loops);
2039 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2041 non_affine_dependence_relation (ddr);
2045 dist = int_cst_value (SUB_DISTANCE (subscript));
2054 /* This is the subscript coupling test.
2059 There is no dependence. */
2060 if (init_v[loop_nb] != 0
2062 && (enum data_dependence_direction) dir_v[loop_nb] != dir
2063 && (enum data_dependence_direction) dir_v[loop_nb] != dir_star)
2065 finalize_ddr_dependent (ddr, chrec_known);
2069 dir_v[loop_nb] = dir;
2070 init_v[loop_nb] = 1;
2074 /* There is a distance of 1 on all the outer loops:
2076 Example: there is a dependence of distance 1 on loop_1 for the array A.
2082 struct loop *lca, *loop_a, *loop_b;
2083 struct data_reference *a = DDR_A (ddr);
2084 struct data_reference *b = DDR_B (ddr);
2086 loop_a = loop_containing_stmt (DR_STMT (a));
2087 loop_b = loop_containing_stmt (DR_STMT (b));
2089 /* Get the common ancestor loop. */
2090 lca = find_common_loop (loop_a, loop_b);
2091 lca_nb = lca->num - first_loop;
2093 gcc_assert (lca_nb >= 0);
2094 gcc_assert (lca_nb < nb_loops);
2096 /* For each outer loop where init_v is not set, the accesses are
2097 in dependence of distance 1 in the loop. */
2100 && init_v[lca_nb] == 0)
2101 dir_v[lca_nb] = dir_positive;
2106 lca_nb = lca->num - first_loop;
2107 while (lca->depth != 0)
2109 /* If we're considering just a sub-nest, then don't record
2110 any information on the outer loops. */
2114 gcc_assert (lca_nb < nb_loops);
2116 if (init_v[lca_nb] == 0)
2117 dir_v[lca_nb] = dir_positive;
2119 lca_nb = lca->num - first_loop;
2125 DDR_DIR_VECT (ddr) = dir_v;
2126 DDR_SIZE_VECT (ddr) = nb_loops;
2130 /* Returns true when all the access functions of A are affine or
2134 access_functions_are_affine_or_constant_p (struct data_reference *a)
2137 varray_type fns = DR_ACCESS_FNS (a);
2139 for (i = 0; i < VARRAY_ACTIVE_SIZE (fns); i++)
2140 if (!evolution_function_is_constant_p (VARRAY_TREE (fns, i))
2141 && !evolution_function_is_affine_multivariate_p (VARRAY_TREE (fns, i)))
2147 /* This computes the affine dependence relation between A and B.
2148 CHREC_KNOWN is used for representing the independence between two
2149 accesses, while CHREC_DONT_KNOW is used for representing the unknown
2152 Note that it is possible to stop the computation of the dependence
2153 relation the first time we detect a CHREC_KNOWN element for a given
2157 compute_affine_dependence (struct data_dependence_relation *ddr)
2159 struct data_reference *dra = DDR_A (ddr);
2160 struct data_reference *drb = DDR_B (ddr);
2162 if (dump_file && (dump_flags & TDF_DETAILS))
2164 fprintf (dump_file, "(compute_affine_dependence\n");
2165 fprintf (dump_file, " (stmt_a = \n");
2166 print_generic_expr (dump_file, DR_STMT (dra), 0);
2167 fprintf (dump_file, ")\n (stmt_b = \n");
2168 print_generic_expr (dump_file, DR_STMT (drb), 0);
2169 fprintf (dump_file, ")\n");
2172 /* Analyze only when the dependence relation is not yet known. */
2173 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
2175 if (access_functions_are_affine_or_constant_p (dra)
2176 && access_functions_are_affine_or_constant_p (drb))
2177 subscript_dependence_tester (ddr);
2179 /* As a last case, if the dependence cannot be determined, or if
2180 the dependence is considered too difficult to determine, answer
2183 finalize_ddr_dependent (ddr, chrec_dont_know);
2186 if (dump_file && (dump_flags & TDF_DETAILS))
2187 fprintf (dump_file, ")\n");
2190 /* Compute a subset of the data dependence relation graph. Don't
2191 compute read-read relations, and avoid the computation of the
2192 opposite relation, i.e. when AB has been computed, don't compute BA.
2193 DATAREFS contains a list of data references, and the result is set
2194 in DEPENDENCE_RELATIONS. */
2197 compute_all_dependences (varray_type datarefs,
2198 varray_type *dependence_relations)
2200 unsigned int i, j, N;
2202 N = VARRAY_ACTIVE_SIZE (datarefs);
2204 for (i = 0; i < N; i++)
2205 for (j = i; j < N; j++)
2207 struct data_reference *a, *b;
2208 struct data_dependence_relation *ddr;
2210 a = VARRAY_GENERIC_PTR (datarefs, i);
2211 b = VARRAY_GENERIC_PTR (datarefs, j);
2212 ddr = initialize_data_dependence_relation (a, b);
2214 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
2215 compute_affine_dependence (ddr);
2216 compute_subscript_distance (ddr);
2220 /* Search the data references in LOOP, and record the information into
2221 DATAREFS. Returns chrec_dont_know when failing to analyze a
2222 difficult case, returns NULL_TREE otherwise.
2224 TODO: This function should be made smarter so that it can handle address
2225 arithmetic as if they were array accesses, etc. */
2228 find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
2230 bool dont_know_node_not_inserted = true;
2231 basic_block bb, *bbs;
2233 block_stmt_iterator bsi;
2235 bbs = get_loop_body (loop);
2237 for (i = 0; i < loop->num_nodes; i++)
2241 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2243 tree stmt = bsi_stmt (bsi);
2244 stmt_ann_t ann = stmt_ann (stmt);
2246 if (TREE_CODE (stmt) != MODIFY_EXPR)
2250 && !V_MUST_DEF_OPS (ann)
2251 && !V_MAY_DEF_OPS (ann))
2254 /* In the GIMPLE representation, a modify expression
2255 contains a single load or store to memory. */
2256 if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF)
2257 VARRAY_PUSH_GENERIC_PTR
2258 (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 0),
2261 else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF)
2262 VARRAY_PUSH_GENERIC_PTR
2263 (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1),
2267 if (dont_know_node_not_inserted)
2269 struct data_reference *res;
2270 res = xmalloc (sizeof (struct data_reference));
2271 DR_STMT (res) = NULL_TREE;
2272 DR_REF (res) = NULL_TREE;
2273 DR_ACCESS_FNS (res) = NULL;
2274 DR_BASE_NAME (res) = NULL;
2275 DR_IS_READ (res) = false;
2276 VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
2277 dont_know_node_not_inserted = false;
2281 /* When there are no defs in the loop, the loop is parallel. */
2282 if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0
2283 || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0)
2284 bb->loop_father->parallel_p = false;
2287 if (bb->loop_father->estimated_nb_iterations == NULL_TREE)
2288 compute_estimated_nb_iterations (bb->loop_father);
2293 return dont_know_node_not_inserted ? NULL_TREE : chrec_dont_know;
2298 /* This section contains all the entry points. */
2300 /* Given a loop nest LOOP, the following vectors are returned:
2301 *DATAREFS is initialized to all the array elements contained in this loop,
2302 *DEPENDENCE_RELATIONS contains the relations between the data references. */
2305 compute_data_dependences_for_loop (unsigned nb_loops,
2307 varray_type *datarefs,
2308 varray_type *dependence_relations)
2311 varray_type allrelations;
2313 /* If one of the data references is not computable, give up without
2314 spending time to compute other dependences. */
2315 if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
2317 struct data_dependence_relation *ddr;
2319 /* Insert a single relation into dependence_relations:
2321 ddr = initialize_data_dependence_relation (NULL, NULL);
2322 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
2323 build_classic_dist_vector (ddr, nb_loops, loop->num);
2324 build_classic_dir_vector (ddr, nb_loops, loop->num);
2328 VARRAY_GENERIC_PTR_INIT (allrelations, 1, "Data dependence relations");
2329 compute_all_dependences (*datarefs, &allrelations);
2331 for (i = 0; i < VARRAY_ACTIVE_SIZE (allrelations); i++)
2333 struct data_dependence_relation *ddr;
2334 ddr = VARRAY_GENERIC_PTR (allrelations, i);
2335 if (build_classic_dist_vector (ddr, nb_loops, loop->num))
2337 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
2338 build_classic_dir_vector (ddr, nb_loops, loop->num);
2343 /* Entry point (for testing only). Analyze all the data references
2344 and the dependence relations.
2346 The data references are computed first.
2348 A relation on these nodes is represented by a complete graph. Some
2349 of the relations could be of no interest, thus the relations can be
2352 In the following function we compute all the relations. This is
2353 just a first implementation that is here for:
2354 - for showing how to ask for the dependence relations,
2355 - for the debugging the whole dependence graph,
2356 - for the dejagnu testcases and maintenance.
2358 It is possible to ask only for a part of the graph, avoiding to
2359 compute the whole dependence graph. The computed dependences are
2360 stored in a knowledge base (KB) such that later queries don't
2361 recompute the same information. The implementation of this KB is
2362 transparent to the optimizer, and thus the KB can be changed with a
2363 more efficient implementation, or the KB could be disabled. */
2366 analyze_all_data_dependences (struct loops *loops)
2369 varray_type datarefs;
2370 varray_type dependence_relations;
2371 int nb_data_refs = 10;
2373 VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
2374 VARRAY_GENERIC_PTR_INIT (dependence_relations,
2375 nb_data_refs * nb_data_refs,
2376 "dependence_relations");
2378 /* Compute DDs on the whole function. */
2379 compute_data_dependences_for_loop (loops->num, loops->parray[0],
2380 &datarefs, &dependence_relations);
2384 dump_data_dependence_relations (dump_file, dependence_relations);
2385 fprintf (dump_file, "\n\n");
2387 if (dump_flags & TDF_DETAILS)
2388 dump_dist_dir_vectors (dump_file, dependence_relations);
2390 if (dump_flags & TDF_STATS)
2392 unsigned nb_top_relations = 0;
2393 unsigned nb_bot_relations = 0;
2394 unsigned nb_basename_differ = 0;
2395 unsigned nb_chrec_relations = 0;
2397 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
2399 struct data_dependence_relation *ddr;
2400 ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
2402 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
2405 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
2407 struct data_reference *a = DDR_A (ddr);
2408 struct data_reference *b = DDR_B (ddr);
2411 if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
2412 || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
2413 nb_basename_differ++;
2419 nb_chrec_relations++;
2422 gather_stats_on_scev_database ();
2426 free_dependence_relations (dependence_relations);
2427 free_data_refs (datarefs);
2430 /* Free the memory used by a data dependence relation DDR. */
2433 free_dependence_relation (struct data_dependence_relation *ddr)
2438 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
2439 varray_clear (DDR_SUBSCRIPTS (ddr));
2443 /* Free the memory used by the data dependence relations from
2444 DEPENDENCE_RELATIONS. */
2447 free_dependence_relations (varray_type dependence_relations)
2450 if (dependence_relations == NULL)
2453 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
2454 free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
2455 varray_clear (dependence_relations);
2458 /* Free the memory used by the data references from DATAREFS. */
2461 free_data_refs (varray_type datarefs)
2465 if (datarefs == NULL)
2468 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
2470 struct data_reference *dr = (struct data_reference *)
2471 VARRAY_GENERIC_PTR (datarefs, i);
2472 if (dr && DR_ACCESS_FNS (dr))
2473 varray_clear (DR_ACCESS_FNS (dr));
2475 varray_clear (datarefs);