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, 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);
114 if (!base_a || !base_b)
117 ta = TREE_TYPE (base_a);
118 tb = TREE_TYPE (base_b);
120 gcc_assert (!POINTER_TYPE_P (ta) && !POINTER_TYPE_P (tb));
122 /* Determine if same base. Example: for the array accesses
123 a[i], b[i] or pointer accesses *a, *b, bases are a, b. */
124 if (base_a == base_b)
130 /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
132 if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
133 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0))
139 /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */
140 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
141 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)
142 && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1))
149 /* Determine if different bases. */
151 /* At this point we know that base_a != base_b. However, pointer
152 accesses of the form x=(*p) and y=(*q), whose bases are p and q,
153 may still be pointing to the same base. In SSAed GIMPLE p and q will
154 be SSA_NAMES in this case. Therefore, here we check if they are
155 really two different declarations. */
156 if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
162 /* Compare two record/union bases s.a and t.b: s != t or (a != b and
163 s and t are not unions). */
164 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
165 && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
166 && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
167 && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
168 || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE
169 && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
170 && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
176 /* Compare a record/union access and an array access. */
177 if ((TREE_CODE (base_a) == VAR_DECL
178 && (TREE_CODE (base_b) == COMPONENT_REF
179 && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL))
180 || (TREE_CODE (base_b) == VAR_DECL
181 && (TREE_CODE (base_a) == COMPONENT_REF
182 && TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL)))
191 /* Returns true iff A divides B. */
194 tree_fold_divides_p (tree type,
198 /* Determines whether (A == gcd (A, B)). */
200 (fold (build (MINUS_EXPR, type, a, tree_fold_gcd (a, b))));
203 /* Compute the greatest common denominator of two numbers using
204 Euclid's algorithm. */
225 /* Returns true iff A divides B. */
228 int_divides_p (int a, int b)
230 return ((b % a) == 0);
235 /* Dump into FILE all the data references from DATAREFS. */
238 dump_data_references (FILE *file,
239 varray_type datarefs)
243 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
244 dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i));
247 /* Dump into FILE all the dependence relations from DDR. */
250 dump_data_dependence_relations (FILE *file,
255 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++)
256 dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i));
259 /* Dump function for a DATA_REFERENCE structure. */
262 dump_data_reference (FILE *outf,
263 struct data_reference *dr)
267 fprintf (outf, "(Data Ref: \n stmt: ");
268 print_generic_stmt (outf, DR_STMT (dr), 0);
269 fprintf (outf, " ref: ");
270 print_generic_stmt (outf, DR_REF (dr), 0);
271 fprintf (outf, " base_name: ");
272 print_generic_stmt (outf, DR_BASE_NAME (dr), 0);
274 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
276 fprintf (outf, " Access function %d: ", i);
277 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
279 fprintf (outf, ")\n");
282 /* Dump function for a SUBSCRIPT structure. */
285 dump_subscript (FILE *outf, struct subscript *subscript)
287 tree chrec = SUB_CONFLICTS_IN_A (subscript);
289 fprintf (outf, "\n (subscript \n");
290 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
291 print_generic_stmt (outf, chrec, 0);
292 if (chrec == chrec_known)
293 fprintf (outf, " (no dependence)\n");
294 else if (chrec_contains_undetermined (chrec))
295 fprintf (outf, " (don't know)\n");
298 tree last_iteration = SUB_LAST_CONFLICT (subscript);
299 fprintf (outf, " last_conflict: ");
300 print_generic_stmt (outf, last_iteration, 0);
303 chrec = SUB_CONFLICTS_IN_B (subscript);
304 fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
305 print_generic_stmt (outf, chrec, 0);
306 if (chrec == chrec_known)
307 fprintf (outf, " (no dependence)\n");
308 else if (chrec_contains_undetermined (chrec))
309 fprintf (outf, " (don't know)\n");
312 tree last_iteration = SUB_LAST_CONFLICT (subscript);
313 fprintf (outf, " last_conflict: ");
314 print_generic_stmt (outf, last_iteration, 0);
317 fprintf (outf, " (Subscript distance: ");
318 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
319 fprintf (outf, " )\n");
320 fprintf (outf, " )\n");
323 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
326 dump_data_dependence_relation (FILE *outf,
327 struct data_dependence_relation *ddr)
329 struct data_reference *dra, *drb;
333 fprintf (outf, "(Data Dep: \n");
334 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
335 fprintf (outf, " (don't know)\n");
337 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
338 fprintf (outf, " (no dependence)\n");
340 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
343 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
345 fprintf (outf, " access_fn_A: ");
346 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
347 fprintf (outf, " access_fn_B: ");
348 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
349 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
351 if (DDR_DIST_VECT (ddr))
353 fprintf (outf, " distance_vect: ");
354 print_lambda_vector (outf, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
356 if (DDR_DIR_VECT (ddr))
358 fprintf (outf, " direction_vect: ");
359 print_lambda_vector (outf, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
363 fprintf (outf, ")\n");
368 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
371 dump_data_dependence_direction (FILE *file,
372 enum data_dependence_direction dir)
388 case dir_positive_or_negative:
389 fprintf (file, "+-");
392 case dir_positive_or_equal:
393 fprintf (file, "+=");
396 case dir_negative_or_equal:
397 fprintf (file, "-=");
409 /* Dumps the distance and direction vectors in FILE. DDRS contains
410 the dependence relations, and VECT_SIZE is the size of the
411 dependence vectors, or in other words the number of loops in the
415 dump_dist_dir_vectors (FILE *file, varray_type ddrs)
419 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
421 struct data_dependence_relation *ddr =
422 (struct data_dependence_relation *)
423 VARRAY_GENERIC_PTR (ddrs, i);
424 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
425 && DDR_AFFINE_P (ddr))
427 fprintf (file, "DISTANCE_V (");
428 print_lambda_vector (file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
429 fprintf (file, ")\n");
430 fprintf (file, "DIRECTION_V (");
431 print_lambda_vector (file, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
432 fprintf (file, ")\n");
435 fprintf (file, "\n\n");
438 /* Dumps the data dependence relations DDRS in FILE. */
441 dump_ddrs (FILE *file, varray_type ddrs)
445 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
447 struct data_dependence_relation *ddr =
448 (struct data_dependence_relation *)
449 VARRAY_GENERIC_PTR (ddrs, i);
450 dump_data_dependence_relation (file, ddr);
452 fprintf (file, "\n\n");
457 /* Compute the lowest iteration bound for LOOP. It is an
461 compute_estimated_nb_iterations (struct loop *loop)
464 struct nb_iter_bound *bound, *next;
466 for (bound = loop->bounds; bound; bound = next)
469 estimation = bound->bound;
471 if (TREE_CODE (estimation) != INTEGER_CST)
474 if (loop->estimated_nb_iterations)
476 /* Update only if estimation is smaller. */
477 if (tree_int_cst_lt (estimation, loop->estimated_nb_iterations))
478 loop->estimated_nb_iterations = estimation;
481 loop->estimated_nb_iterations = estimation;
485 /* Estimate the number of iterations from the size of the data and the
489 estimate_niter_from_size_of_data (struct loop *loop,
495 tree array_size, data_size, element_size;
498 init = initial_condition (access_fn);
499 step = evolution_part_in_loop_num (access_fn, loop->num);
501 array_size = TYPE_SIZE (TREE_TYPE (opnd0));
502 element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
503 if (array_size == NULL_TREE
504 || TREE_CODE (array_size) != INTEGER_CST
505 || TREE_CODE (element_size) != INTEGER_CST)
508 data_size = fold (build2 (EXACT_DIV_EXPR, integer_type_node,
509 array_size, element_size));
511 if (init != NULL_TREE
513 && TREE_CODE (init) == INTEGER_CST
514 && TREE_CODE (step) == INTEGER_CST)
516 estimation = fold (build2 (CEIL_DIV_EXPR, integer_type_node,
517 fold (build2 (MINUS_EXPR, integer_type_node,
518 data_size, init)), step));
520 record_estimate (loop, estimation, boolean_true_node, stmt);
524 /* Given an ARRAY_REF node REF, records its access functions.
525 Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
526 i.e. the constant "3", then recursively call the function on opnd0,
527 i.e. the ARRAY_REF "A[i]". The function returns the base name:
531 analyze_array_indexes (struct loop *loop,
532 varray_type *access_fns,
538 opnd0 = TREE_OPERAND (ref, 0);
539 opnd1 = TREE_OPERAND (ref, 1);
541 /* The detection of the evolution function for this data access is
542 postponed until the dependence test. This lazy strategy avoids
543 the computation of access functions that are of no interest for
545 access_fn = instantiate_parameters
546 (loop, analyze_scalar_evolution (loop, opnd1));
548 if (loop->estimated_nb_iterations == NULL_TREE)
549 estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
551 VARRAY_PUSH_TREE (*access_fns, access_fn);
553 /* Recursively record other array access functions. */
554 if (TREE_CODE (opnd0) == ARRAY_REF)
555 return analyze_array_indexes (loop, access_fns, opnd0, stmt);
557 /* Return the base name of the data access. */
562 /* For a data reference REF contained in the statement STMT, initialize
563 a DATA_REFERENCE structure, and return it. IS_READ flag has to be
564 set to true when REF is in the right hand side of an
567 struct data_reference *
568 analyze_array (tree stmt, tree ref, bool is_read)
570 struct data_reference *res;
572 if (dump_file && (dump_flags & TDF_DETAILS))
574 fprintf (dump_file, "(analyze_array \n");
575 fprintf (dump_file, " (ref = ");
576 print_generic_stmt (dump_file, ref, 0);
577 fprintf (dump_file, ")\n");
580 res = xmalloc (sizeof (struct data_reference));
582 DR_STMT (res) = stmt;
584 VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 3, "access_fns");
585 DR_BASE_NAME (res) = analyze_array_indexes
586 (loop_containing_stmt (stmt), &(DR_ACCESS_FNS (res)), ref, stmt);
587 DR_IS_READ (res) = is_read;
589 if (dump_file && (dump_flags & TDF_DETAILS))
590 fprintf (dump_file, ")\n");
595 /* For a data reference REF contained in the statement STMT, initialize
596 a DATA_REFERENCE structure, and return it. */
598 struct data_reference *
599 init_data_ref (tree stmt,
605 struct data_reference *res;
607 if (dump_file && (dump_flags & TDF_DETAILS))
609 fprintf (dump_file, "(init_data_ref \n");
610 fprintf (dump_file, " (ref = ");
611 print_generic_stmt (dump_file, ref, 0);
612 fprintf (dump_file, ")\n");
615 res = xmalloc (sizeof (struct data_reference));
617 DR_STMT (res) = stmt;
619 VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 5, "access_fns");
620 DR_BASE_NAME (res) = base;
621 VARRAY_PUSH_TREE (DR_ACCESS_FNS (res), access_fn);
622 DR_IS_READ (res) = is_read;
624 if (dump_file && (dump_flags & TDF_DETAILS))
625 fprintf (dump_file, ")\n");
632 /* Returns true when all the functions of a tree_vec CHREC are the
636 all_chrecs_equal_p (tree chrec)
640 for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
642 tree chrec_j = TREE_VEC_ELT (chrec, j);
643 tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1);
646 (integer_type_node, chrec_j, chrec_j_1)))
652 /* Determine for each subscript in the data dependence relation DDR
656 compute_subscript_distance (struct data_dependence_relation *ddr)
658 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
662 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
664 tree conflicts_a, conflicts_b, difference;
665 struct subscript *subscript;
667 subscript = DDR_SUBSCRIPT (ddr, i);
668 conflicts_a = SUB_CONFLICTS_IN_A (subscript);
669 conflicts_b = SUB_CONFLICTS_IN_B (subscript);
671 if (TREE_CODE (conflicts_a) == TREE_VEC)
673 if (!all_chrecs_equal_p (conflicts_a))
675 SUB_DISTANCE (subscript) = chrec_dont_know;
679 conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
682 if (TREE_CODE (conflicts_b) == TREE_VEC)
684 if (!all_chrecs_equal_p (conflicts_b))
686 SUB_DISTANCE (subscript) = chrec_dont_know;
690 conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
693 difference = chrec_fold_minus
694 (integer_type_node, conflicts_b, conflicts_a);
696 if (evolution_function_is_constant_p (difference))
697 SUB_DISTANCE (subscript) = difference;
700 SUB_DISTANCE (subscript) = chrec_dont_know;
705 /* Initialize a ddr. */
707 struct data_dependence_relation *
708 initialize_data_dependence_relation (struct data_reference *a,
709 struct data_reference *b)
711 struct data_dependence_relation *res;
714 res = xmalloc (sizeof (struct data_dependence_relation));
718 if (a == NULL || b == NULL
719 || DR_BASE_NAME (a) == NULL_TREE
720 || DR_BASE_NAME (b) == NULL_TREE)
721 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
723 /* When the dimensions of A and B differ, we directly initialize
724 the relation to "there is no dependence": chrec_known. */
725 else if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
726 || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
727 DDR_ARE_DEPENDENT (res) = chrec_known;
732 DDR_AFFINE_P (res) = true;
733 DDR_ARE_DEPENDENT (res) = NULL_TREE;
734 DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
735 DDR_SIZE_VECT (res) = 0;
736 DDR_DIST_VECT (res) = NULL;
737 DDR_DIR_VECT (res) = NULL;
739 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
741 struct subscript *subscript;
743 subscript = xmalloc (sizeof (struct subscript));
744 SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
745 SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
746 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
747 SUB_DISTANCE (subscript) = chrec_dont_know;
748 VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
755 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
759 finalize_ddr_dependent (struct data_dependence_relation *ddr,
762 if (dump_file && (dump_flags & TDF_DETAILS))
764 fprintf (dump_file, "(dependence classified: ");
765 print_generic_expr (dump_file, chrec, 0);
766 fprintf (dump_file, ")\n");
769 DDR_ARE_DEPENDENT (ddr) = chrec;
770 varray_clear (DDR_SUBSCRIPTS (ddr));
773 /* The dependence relation DDR cannot be represented by a distance
777 non_affine_dependence_relation (struct data_dependence_relation *ddr)
779 if (dump_file && (dump_flags & TDF_DETAILS))
780 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
782 DDR_AFFINE_P (ddr) = false;
787 /* This section contains the classic Banerjee tests. */
789 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
790 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
793 ziv_subscript_p (tree chrec_a,
796 return (evolution_function_is_constant_p (chrec_a)
797 && evolution_function_is_constant_p (chrec_b));
800 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
801 variable, i.e., if the SIV (Single Index Variable) test is true. */
804 siv_subscript_p (tree chrec_a,
807 if ((evolution_function_is_constant_p (chrec_a)
808 && evolution_function_is_univariate_p (chrec_b))
809 || (evolution_function_is_constant_p (chrec_b)
810 && evolution_function_is_univariate_p (chrec_a)))
813 if (evolution_function_is_univariate_p (chrec_a)
814 && evolution_function_is_univariate_p (chrec_b))
816 switch (TREE_CODE (chrec_a))
818 case POLYNOMIAL_CHREC:
819 switch (TREE_CODE (chrec_b))
821 case POLYNOMIAL_CHREC:
822 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
837 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
838 *OVERLAPS_B are initialized to the functions that describe the
839 relation between the elements accessed twice by CHREC_A and
840 CHREC_B. For k >= 0, the following property is verified:
842 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
845 analyze_ziv_subscript (tree chrec_a,
849 tree *last_conflicts)
853 if (dump_file && (dump_flags & TDF_DETAILS))
854 fprintf (dump_file, "(analyze_ziv_subscript \n");
856 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
858 switch (TREE_CODE (difference))
861 if (integer_zerop (difference))
863 /* The difference is equal to zero: the accessed index
864 overlaps for each iteration in the loop. */
865 *overlaps_a = integer_zero_node;
866 *overlaps_b = integer_zero_node;
867 *last_conflicts = chrec_dont_know;
871 /* The accesses do not overlap. */
872 *overlaps_a = chrec_known;
873 *overlaps_b = chrec_known;
874 *last_conflicts = integer_zero_node;
879 /* We're not sure whether the indexes overlap. For the moment,
880 conservatively answer "don't know". */
881 *overlaps_a = chrec_dont_know;
882 *overlaps_b = chrec_dont_know;
883 *last_conflicts = chrec_dont_know;
887 if (dump_file && (dump_flags & TDF_DETAILS))
888 fprintf (dump_file, ")\n");
891 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
892 constant, and CHREC_B is an affine function. *OVERLAPS_A and
893 *OVERLAPS_B are initialized to the functions that describe the
894 relation between the elements accessed twice by CHREC_A and
895 CHREC_B. For k >= 0, the following property is verified:
897 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
900 analyze_siv_subscript_cst_affine (tree chrec_a,
904 tree *last_conflicts)
906 bool value0, value1, value2;
907 tree difference = chrec_fold_minus
908 (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
910 if (!chrec_is_positive (initial_condition (difference), &value0))
912 *overlaps_a = chrec_dont_know;
913 *overlaps_b = chrec_dont_know;
914 *last_conflicts = chrec_dont_know;
921 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
923 *overlaps_a = chrec_dont_know;
924 *overlaps_b = chrec_dont_know;
925 *last_conflicts = chrec_dont_know;
937 if (tree_fold_divides_p
938 (integer_type_node, CHREC_RIGHT (chrec_b), difference))
940 *overlaps_a = integer_zero_node;
942 (build (EXACT_DIV_EXPR, integer_type_node,
943 fold (build1 (ABS_EXPR, integer_type_node, difference)),
944 CHREC_RIGHT (chrec_b)));
945 *last_conflicts = integer_one_node;
949 /* When the step does not divides the difference, there are
953 *overlaps_a = chrec_known;
954 *overlaps_b = chrec_known;
955 *last_conflicts = integer_zero_node;
964 chrec_b = {10, +, -1}
966 In this case, chrec_a will not overlap with chrec_b. */
967 *overlaps_a = chrec_known;
968 *overlaps_b = chrec_known;
969 *last_conflicts = integer_zero_node;
976 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
978 *overlaps_a = chrec_dont_know;
979 *overlaps_b = chrec_dont_know;
980 *last_conflicts = chrec_dont_know;
989 chrec_b = {10, +, -1}
991 if (tree_fold_divides_p
992 (integer_type_node, CHREC_RIGHT (chrec_b), difference))
994 *overlaps_a = integer_zero_node;
996 (build (EXACT_DIV_EXPR, integer_type_node, difference,
997 CHREC_RIGHT (chrec_b)));
998 *last_conflicts = integer_one_node;
1002 /* When the step does not divides the difference, there
1006 *overlaps_a = chrec_known;
1007 *overlaps_b = chrec_known;
1008 *last_conflicts = integer_zero_node;
1018 In this case, chrec_a will not overlap with chrec_b. */
1019 *overlaps_a = chrec_known;
1020 *overlaps_b = chrec_known;
1021 *last_conflicts = integer_zero_node;
1029 /* Helper recursive function for initializing the matrix A. Returns
1030 the initial value of CHREC. */
1033 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
1037 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1038 return int_cst_value (chrec);
1040 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
1041 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
1044 #define FLOOR_DIV(x,y) ((x) / (y))
1046 /* Solves the special case of the Diophantine equation:
1047 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1049 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1050 number of iterations that loops X and Y run. The overlaps will be
1051 constructed as evolutions in dimension DIM. */
1054 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
1055 tree *overlaps_a, tree *overlaps_b,
1056 tree *last_conflicts, int dim)
1058 if (((step_a > 0 && step_b > 0)
1059 || (step_a < 0 && step_b < 0)))
1061 int step_overlaps_a, step_overlaps_b;
1062 int gcd_steps_a_b, last_conflict, tau2;
1064 gcd_steps_a_b = gcd (step_a, step_b);
1065 step_overlaps_a = step_b / gcd_steps_a_b;
1066 step_overlaps_b = step_a / gcd_steps_a_b;
1068 tau2 = FLOOR_DIV (niter, step_overlaps_a);
1069 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
1070 last_conflict = tau2;
1072 *overlaps_a = build_polynomial_chrec
1073 (dim, integer_zero_node,
1074 build_int_cst (NULL_TREE, step_overlaps_a));
1075 *overlaps_b = build_polynomial_chrec
1076 (dim, integer_zero_node,
1077 build_int_cst (NULL_TREE, step_overlaps_b));
1078 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
1083 *overlaps_a = integer_zero_node;
1084 *overlaps_b = integer_zero_node;
1085 *last_conflicts = integer_zero_node;
1090 /* Solves the special case of a Diophantine equation where CHREC_A is
1091 an affine bivariate function, and CHREC_B is an affine univariate
1092 function. For example,
1094 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1096 has the following overlapping functions:
1098 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1099 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1100 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1102 FORNOW: This is a specialized implementation for a case occurring in
1103 a common benchmark. Implement the general algorithm. */
1106 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
1107 tree *overlaps_a, tree *overlaps_b,
1108 tree *last_conflicts)
1110 bool xz_p, yz_p, xyz_p;
1111 int step_x, step_y, step_z;
1112 int niter_x, niter_y, niter_z, niter;
1113 tree numiter_x, numiter_y, numiter_z;
1114 tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
1115 tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
1116 tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
1118 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
1119 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
1120 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
1122 numiter_x = number_of_iterations_in_loop
1123 (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]);
1124 numiter_y = number_of_iterations_in_loop
1125 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
1126 numiter_z = number_of_iterations_in_loop
1127 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
1129 if (TREE_CODE (numiter_x) != INTEGER_CST)
1130 numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]
1131 ->estimated_nb_iterations;
1132 if (TREE_CODE (numiter_y) != INTEGER_CST)
1133 numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]
1134 ->estimated_nb_iterations;
1135 if (TREE_CODE (numiter_z) != INTEGER_CST)
1136 numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
1137 ->estimated_nb_iterations;
1139 if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
1140 || numiter_z == NULL_TREE)
1142 *overlaps_a = chrec_dont_know;
1143 *overlaps_b = chrec_dont_know;
1144 *last_conflicts = chrec_dont_know;
1148 niter_x = int_cst_value (numiter_x);
1149 niter_y = int_cst_value (numiter_y);
1150 niter_z = int_cst_value (numiter_z);
1152 niter = MIN (niter_x, niter_z);
1153 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
1156 &last_conflicts_xz, 1);
1157 niter = MIN (niter_y, niter_z);
1158 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
1161 &last_conflicts_yz, 2);
1162 niter = MIN (niter_x, niter_z);
1163 niter = MIN (niter_y, niter);
1164 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
1167 &last_conflicts_xyz, 3);
1169 xz_p = !integer_zerop (last_conflicts_xz);
1170 yz_p = !integer_zerop (last_conflicts_yz);
1171 xyz_p = !integer_zerop (last_conflicts_xyz);
1173 if (xz_p || yz_p || xyz_p)
1175 *overlaps_a = make_tree_vec (2);
1176 TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
1177 TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
1178 *overlaps_b = integer_zero_node;
1181 TREE_VEC_ELT (*overlaps_a, 0) =
1182 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
1185 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
1186 *last_conflicts = last_conflicts_xz;
1190 TREE_VEC_ELT (*overlaps_a, 1) =
1191 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
1194 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
1195 *last_conflicts = last_conflicts_yz;
1199 TREE_VEC_ELT (*overlaps_a, 0) =
1200 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
1202 TREE_VEC_ELT (*overlaps_a, 1) =
1203 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
1206 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
1207 *last_conflicts = last_conflicts_xyz;
1212 *overlaps_a = integer_zero_node;
1213 *overlaps_b = integer_zero_node;
1214 *last_conflicts = integer_zero_node;
1218 /* Determines the overlapping elements due to accesses CHREC_A and
1219 CHREC_B, that are affine functions. This is a part of the
1220 subscript analyzer. */
1223 analyze_subscript_affine_affine (tree chrec_a,
1227 tree *last_conflicts)
1229 unsigned nb_vars_a, nb_vars_b, dim;
1230 int init_a, init_b, gamma, gcd_alpha_beta;
1232 lambda_matrix A, U, S;
1234 if (dump_file && (dump_flags & TDF_DETAILS))
1235 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
1237 /* For determining the initial intersection, we have to solve a
1238 Diophantine equation. This is the most time consuming part.
1240 For answering to the question: "Is there a dependence?" we have
1241 to prove that there exists a solution to the Diophantine
1242 equation, and that the solution is in the iteration domain,
1243 i.e. the solution is positive or zero, and that the solution
1244 happens before the upper bound loop.nb_iterations. Otherwise
1245 there is no dependence. This function outputs a description of
1246 the iterations that hold the intersections. */
1249 nb_vars_a = nb_vars_in_chrec (chrec_a);
1250 nb_vars_b = nb_vars_in_chrec (chrec_b);
1252 dim = nb_vars_a + nb_vars_b;
1253 U = lambda_matrix_new (dim, dim);
1254 A = lambda_matrix_new (dim, 1);
1255 S = lambda_matrix_new (dim, 1);
1257 init_a = initialize_matrix_A (A, chrec_a, 0, 1);
1258 init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
1259 gamma = init_b - init_a;
1261 /* Don't do all the hard work of solving the Diophantine equation
1262 when we already know the solution: for example,
1265 | gamma = 3 - 3 = 0.
1266 Then the first overlap occurs during the first iterations:
1267 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
1271 if (nb_vars_a == 1 && nb_vars_b == 1)
1274 int niter, niter_a, niter_b;
1275 tree numiter_a, numiter_b;
1277 numiter_a = number_of_iterations_in_loop
1278 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
1279 numiter_b = number_of_iterations_in_loop
1280 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
1282 if (TREE_CODE (numiter_a) != INTEGER_CST)
1283 numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
1284 ->estimated_nb_iterations;
1285 if (TREE_CODE (numiter_b) != INTEGER_CST)
1286 numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
1287 ->estimated_nb_iterations;
1288 if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
1290 *overlaps_a = chrec_dont_know;
1291 *overlaps_b = chrec_dont_know;
1292 *last_conflicts = chrec_dont_know;
1296 niter_a = int_cst_value (numiter_a);
1297 niter_b = int_cst_value (numiter_b);
1298 niter = MIN (niter_a, niter_b);
1300 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
1301 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
1303 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
1304 overlaps_a, overlaps_b,
1308 else if (nb_vars_a == 2 && nb_vars_b == 1)
1309 compute_overlap_steps_for_affine_1_2
1310 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
1312 else if (nb_vars_a == 1 && nb_vars_b == 2)
1313 compute_overlap_steps_for_affine_1_2
1314 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
1318 *overlaps_a = chrec_dont_know;
1319 *overlaps_b = chrec_dont_know;
1320 *last_conflicts = chrec_dont_know;
1326 lambda_matrix_right_hermite (A, dim, 1, S, U);
1331 lambda_matrix_row_negate (U, dim, 0);
1333 gcd_alpha_beta = S[0][0];
1335 /* The classic "gcd-test". */
1336 if (!int_divides_p (gcd_alpha_beta, gamma))
1338 /* The "gcd-test" has determined that there is no integer
1339 solution, i.e. there is no dependence. */
1340 *overlaps_a = chrec_known;
1341 *overlaps_b = chrec_known;
1342 *last_conflicts = integer_zero_node;
1345 /* Both access functions are univariate. This includes SIV and MIV cases. */
1346 else if (nb_vars_a == 1 && nb_vars_b == 1)
1348 /* Both functions should have the same evolution sign. */
1349 if (((A[0][0] > 0 && -A[1][0] > 0)
1350 || (A[0][0] < 0 && -A[1][0] < 0)))
1352 /* The solutions are given by:
1354 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
1357 For a given integer t. Using the following variables,
1359 | i0 = u11 * gamma / gcd_alpha_beta
1360 | j0 = u12 * gamma / gcd_alpha_beta
1367 | y0 = j0 + j1 * t. */
1371 /* X0 and Y0 are the first iterations for which there is a
1372 dependence. X0, Y0 are two solutions of the Diophantine
1373 equation: chrec_a (X0) = chrec_b (Y0). */
1375 int niter, niter_a, niter_b;
1376 tree numiter_a, numiter_b;
1378 numiter_a = number_of_iterations_in_loop
1379 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
1380 numiter_b = number_of_iterations_in_loop
1381 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
1383 if (TREE_CODE (numiter_a) != INTEGER_CST)
1384 numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
1385 ->estimated_nb_iterations;
1386 if (TREE_CODE (numiter_b) != INTEGER_CST)
1387 numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
1388 ->estimated_nb_iterations;
1389 if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
1391 *overlaps_a = chrec_dont_know;
1392 *overlaps_b = chrec_dont_know;
1393 *last_conflicts = chrec_dont_know;
1397 niter_a = int_cst_value (numiter_a);
1398 niter_b = int_cst_value (numiter_b);
1399 niter = MIN (niter_a, niter_b);
1401 i0 = U[0][0] * gamma / gcd_alpha_beta;
1402 j0 = U[0][1] * gamma / gcd_alpha_beta;
1406 if ((i1 == 0 && i0 < 0)
1407 || (j1 == 0 && j0 < 0))
1409 /* There is no solution.
1410 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
1411 falls in here, but for the moment we don't look at the
1412 upper bound of the iteration domain. */
1413 *overlaps_a = chrec_known;
1414 *overlaps_b = chrec_known;
1415 *last_conflicts = integer_zero_node;
1422 tau1 = CEIL (-i0, i1);
1423 tau2 = FLOOR_DIV (niter - i0, i1);
1427 int last_conflict, min_multiple;
1428 tau1 = MAX (tau1, CEIL (-j0, j1));
1429 tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
1431 x0 = i1 * tau1 + i0;
1432 y0 = j1 * tau1 + j0;
1434 /* At this point (x0, y0) is one of the
1435 solutions to the Diophantine equation. The
1436 next step has to compute the smallest
1437 positive solution: the first conflicts. */
1438 min_multiple = MIN (x0 / i1, y0 / j1);
1439 x0 -= i1 * min_multiple;
1440 y0 -= j1 * min_multiple;
1442 tau1 = (x0 - i0)/i1;
1443 last_conflict = tau2 - tau1;
1445 *overlaps_a = build_polynomial_chrec
1447 build_int_cst (NULL_TREE, x0),
1448 build_int_cst (NULL_TREE, i1));
1449 *overlaps_b = build_polynomial_chrec
1451 build_int_cst (NULL_TREE, y0),
1452 build_int_cst (NULL_TREE, j1));
1453 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
1457 /* FIXME: For the moment, the upper bound of the
1458 iteration domain for j is not checked. */
1459 *overlaps_a = chrec_dont_know;
1460 *overlaps_b = chrec_dont_know;
1461 *last_conflicts = chrec_dont_know;
1467 /* FIXME: For the moment, the upper bound of the
1468 iteration domain for i is not checked. */
1469 *overlaps_a = chrec_dont_know;
1470 *overlaps_b = chrec_dont_know;
1471 *last_conflicts = chrec_dont_know;
1477 *overlaps_a = chrec_dont_know;
1478 *overlaps_b = chrec_dont_know;
1479 *last_conflicts = chrec_dont_know;
1485 *overlaps_a = chrec_dont_know;
1486 *overlaps_b = chrec_dont_know;
1487 *last_conflicts = chrec_dont_know;
1491 if (dump_file && (dump_flags & TDF_DETAILS))
1493 fprintf (dump_file, " (overlaps_a = ");
1494 print_generic_expr (dump_file, *overlaps_a, 0);
1495 fprintf (dump_file, ")\n (overlaps_b = ");
1496 print_generic_expr (dump_file, *overlaps_b, 0);
1497 fprintf (dump_file, ")\n");
1500 if (dump_file && (dump_flags & TDF_DETAILS))
1501 fprintf (dump_file, ")\n");
1504 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
1505 *OVERLAPS_B are initialized to the functions that describe the
1506 relation between the elements accessed twice by CHREC_A and
1507 CHREC_B. For k >= 0, the following property is verified:
1509 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1512 analyze_siv_subscript (tree chrec_a,
1516 tree *last_conflicts)
1518 if (dump_file && (dump_flags & TDF_DETAILS))
1519 fprintf (dump_file, "(analyze_siv_subscript \n");
1521 if (evolution_function_is_constant_p (chrec_a)
1522 && evolution_function_is_affine_p (chrec_b))
1523 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
1524 overlaps_a, overlaps_b, last_conflicts);
1526 else if (evolution_function_is_affine_p (chrec_a)
1527 && evolution_function_is_constant_p (chrec_b))
1528 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
1529 overlaps_b, overlaps_a, last_conflicts);
1531 else if (evolution_function_is_affine_p (chrec_a)
1532 && evolution_function_is_affine_p (chrec_b))
1533 analyze_subscript_affine_affine (chrec_a, chrec_b,
1534 overlaps_a, overlaps_b, last_conflicts);
1537 *overlaps_a = chrec_dont_know;
1538 *overlaps_b = chrec_dont_know;
1539 *last_conflicts = chrec_dont_know;
1542 if (dump_file && (dump_flags & TDF_DETAILS))
1543 fprintf (dump_file, ")\n");
1546 /* Return true when the evolution steps of an affine CHREC divide the
1550 chrec_steps_divide_constant_p (tree chrec,
1553 switch (TREE_CODE (chrec))
1555 case POLYNOMIAL_CHREC:
1556 return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst)
1557 && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
1560 /* On the initial condition, return true. */
1565 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
1566 *OVERLAPS_B are initialized to the functions that describe the
1567 relation between the elements accessed twice by CHREC_A and
1568 CHREC_B. For k >= 0, the following property is verified:
1570 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1573 analyze_miv_subscript (tree chrec_a,
1577 tree *last_conflicts)
1579 /* FIXME: This is a MIV subscript, not yet handled.
1580 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
1583 In the SIV test we had to solve a Diophantine equation with two
1584 variables. In the MIV case we have to solve a Diophantine
1585 equation with 2*n variables (if the subscript uses n IVs).
1589 if (dump_file && (dump_flags & TDF_DETAILS))
1590 fprintf (dump_file, "(analyze_miv_subscript \n");
1592 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
1594 if (chrec_zerop (difference))
1596 /* Access functions are the same: all the elements are accessed
1597 in the same order. */
1598 *overlaps_a = integer_zero_node;
1599 *overlaps_b = integer_zero_node;
1600 *last_conflicts = number_of_iterations_in_loop
1601 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
1604 else if (evolution_function_is_constant_p (difference)
1605 /* For the moment, the following is verified:
1606 evolution_function_is_affine_multivariate_p (chrec_a) */
1607 && !chrec_steps_divide_constant_p (chrec_a, difference))
1609 /* testsuite/.../ssa-chrec-33.c
1610 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
1612 The difference is 1, and the evolution steps are equal to 2,
1613 consequently there are no overlapping elements. */
1614 *overlaps_a = chrec_known;
1615 *overlaps_b = chrec_known;
1616 *last_conflicts = integer_zero_node;
1619 else if (evolution_function_is_affine_multivariate_p (chrec_a)
1620 && evolution_function_is_affine_multivariate_p (chrec_b))
1622 /* testsuite/.../ssa-chrec-35.c
1623 {0, +, 1}_2 vs. {0, +, 1}_3
1624 the overlapping elements are respectively located at iterations:
1625 {0, +, 1}_x and {0, +, 1}_x,
1626 in other words, we have the equality:
1627 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
1630 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
1631 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
1633 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
1634 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
1636 analyze_subscript_affine_affine (chrec_a, chrec_b,
1637 overlaps_a, overlaps_b, last_conflicts);
1642 /* When the analysis is too difficult, answer "don't know". */
1643 *overlaps_a = chrec_dont_know;
1644 *overlaps_b = chrec_dont_know;
1645 *last_conflicts = chrec_dont_know;
1648 if (dump_file && (dump_flags & TDF_DETAILS))
1649 fprintf (dump_file, ")\n");
1652 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
1653 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
1654 two functions that describe the iterations that contain conflicting
1657 Remark: For an integer k >= 0, the following equality is true:
1659 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
1663 analyze_overlapping_iterations (tree chrec_a,
1665 tree *overlap_iterations_a,
1666 tree *overlap_iterations_b,
1667 tree *last_conflicts)
1669 if (dump_file && (dump_flags & TDF_DETAILS))
1671 fprintf (dump_file, "(analyze_overlapping_iterations \n");
1672 fprintf (dump_file, " (chrec_a = ");
1673 print_generic_expr (dump_file, chrec_a, 0);
1674 fprintf (dump_file, ")\n chrec_b = ");
1675 print_generic_expr (dump_file, chrec_b, 0);
1676 fprintf (dump_file, ")\n");
1679 if (chrec_a == NULL_TREE
1680 || chrec_b == NULL_TREE
1681 || chrec_contains_undetermined (chrec_a)
1682 || chrec_contains_undetermined (chrec_b)
1683 || chrec_contains_symbols (chrec_a)
1684 || chrec_contains_symbols (chrec_b))
1686 *overlap_iterations_a = chrec_dont_know;
1687 *overlap_iterations_b = chrec_dont_know;
1690 else if (ziv_subscript_p (chrec_a, chrec_b))
1691 analyze_ziv_subscript (chrec_a, chrec_b,
1692 overlap_iterations_a, overlap_iterations_b,
1695 else if (siv_subscript_p (chrec_a, chrec_b))
1696 analyze_siv_subscript (chrec_a, chrec_b,
1697 overlap_iterations_a, overlap_iterations_b,
1701 analyze_miv_subscript (chrec_a, chrec_b,
1702 overlap_iterations_a, overlap_iterations_b,
1705 if (dump_file && (dump_flags & TDF_DETAILS))
1707 fprintf (dump_file, " (overlap_iterations_a = ");
1708 print_generic_expr (dump_file, *overlap_iterations_a, 0);
1709 fprintf (dump_file, ")\n (overlap_iterations_b = ");
1710 print_generic_expr (dump_file, *overlap_iterations_b, 0);
1711 fprintf (dump_file, ")\n");
1717 /* This section contains the affine functions dependences detector. */
1719 /* Computes the conflicting iterations, and initialize DDR. */
1722 subscript_dependence_tester (struct data_dependence_relation *ddr)
1725 struct data_reference *dra = DDR_A (ddr);
1726 struct data_reference *drb = DDR_B (ddr);
1727 tree last_conflicts;
1729 if (dump_file && (dump_flags & TDF_DETAILS))
1730 fprintf (dump_file, "(subscript_dependence_tester \n");
1732 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1734 tree overlaps_a, overlaps_b;
1735 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1737 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
1738 DR_ACCESS_FN (drb, i),
1739 &overlaps_a, &overlaps_b,
1742 if (chrec_contains_undetermined (overlaps_a)
1743 || chrec_contains_undetermined (overlaps_b))
1745 finalize_ddr_dependent (ddr, chrec_dont_know);
1749 else if (overlaps_a == chrec_known
1750 || overlaps_b == chrec_known)
1752 finalize_ddr_dependent (ddr, chrec_known);
1758 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
1759 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
1760 SUB_LAST_CONFLICT (subscript) = last_conflicts;
1764 if (dump_file && (dump_flags & TDF_DETAILS))
1765 fprintf (dump_file, ")\n");
1768 /* Compute the classic per loop distance vector.
1770 DDR is the data dependence relation to build a vector from.
1771 NB_LOOPS is the total number of loops we are considering.
1772 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
1774 Return FALSE if the dependence relation is outside of the loop nest
1775 starting at FIRST_LOOP_DEPTH.
1776 Return TRUE otherwise. */
1779 build_classic_dist_vector (struct data_dependence_relation *ddr,
1780 int nb_loops, int first_loop_depth)
1783 lambda_vector dist_v, init_v;
1785 dist_v = lambda_vector_new (nb_loops);
1786 init_v = lambda_vector_new (nb_loops);
1787 lambda_vector_clear (dist_v, nb_loops);
1788 lambda_vector_clear (init_v, nb_loops);
1790 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
1793 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1795 tree access_fn_a, access_fn_b;
1796 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1798 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
1800 non_affine_dependence_relation (ddr);
1804 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
1805 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
1807 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
1808 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
1810 int dist, loop_nb, loop_depth;
1811 int loop_nb_a = CHREC_VARIABLE (access_fn_a);
1812 int loop_nb_b = CHREC_VARIABLE (access_fn_b);
1813 struct loop *loop_a = current_loops->parray[loop_nb_a];
1814 struct loop *loop_b = current_loops->parray[loop_nb_b];
1816 /* If the loop for either variable is at a lower depth than
1817 the first_loop's depth, then we can't possibly have a
1818 dependency at this level of the loop. */
1820 if (loop_a->depth < first_loop_depth
1821 || loop_b->depth < first_loop_depth)
1824 if (loop_nb_a != loop_nb_b
1825 && !flow_loop_nested_p (loop_a, loop_b)
1826 && !flow_loop_nested_p (loop_b, loop_a))
1828 /* Example: when there are two consecutive loops,
1837 the dependence relation cannot be captured by the
1838 distance abstraction. */
1839 non_affine_dependence_relation (ddr);
1843 /* The dependence is carried by the outermost loop. Example:
1850 In this case, the dependence is carried by loop_1. */
1851 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
1852 loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
1854 /* If the loop number is still greater than the number of
1855 loops we've been asked to analyze, or negative,
1856 something is borked. */
1857 gcc_assert (loop_depth >= 0);
1858 gcc_assert (loop_depth < nb_loops);
1859 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
1861 non_affine_dependence_relation (ddr);
1865 dist = int_cst_value (SUB_DISTANCE (subscript));
1867 /* This is the subscript coupling test.
1872 There is no dependence. */
1873 if (init_v[loop_depth] != 0
1874 && dist_v[loop_depth] != dist)
1876 finalize_ddr_dependent (ddr, chrec_known);
1880 dist_v[loop_depth] = dist;
1881 init_v[loop_depth] = 1;
1885 /* There is a distance of 1 on all the outer loops:
1887 Example: there is a dependence of distance 1 on loop_1 for the array A.
1893 struct loop *lca, *loop_a, *loop_b;
1894 struct data_reference *a = DDR_A (ddr);
1895 struct data_reference *b = DDR_B (ddr);
1897 loop_a = loop_containing_stmt (DR_STMT (a));
1898 loop_b = loop_containing_stmt (DR_STMT (b));
1900 /* Get the common ancestor loop. */
1901 lca = find_common_loop (loop_a, loop_b);
1903 lca_depth = lca->depth;
1904 lca_depth -= first_loop_depth;
1905 gcc_assert (lca_depth >= 0);
1906 gcc_assert (lca_depth < nb_loops);
1908 /* For each outer loop where init_v is not set, the accesses are
1909 in dependence of distance 1 in the loop. */
1912 && init_v[lca_depth] == 0)
1913 dist_v[lca_depth] = 1;
1919 lca_depth = lca->depth - first_loop_depth;
1920 while (lca->depth != 0)
1922 /* If we're considering just a sub-nest, then don't record
1923 any information on the outer loops. */
1927 gcc_assert (lca_depth < nb_loops);
1929 if (init_v[lca_depth] == 0)
1930 dist_v[lca_depth] = 1;
1932 lca_depth = lca->depth - first_loop_depth;
1938 DDR_DIST_VECT (ddr) = dist_v;
1939 DDR_SIZE_VECT (ddr) = nb_loops;
1943 /* Compute the classic per loop direction vector.
1945 DDR is the data dependence relation to build a vector from.
1946 NB_LOOPS is the total number of loops we are considering.
1947 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
1949 Return FALSE if the dependence relation is outside of the loop nest
1950 at FIRST_LOOP_DEPTH.
1951 Return TRUE otherwise. */
1954 build_classic_dir_vector (struct data_dependence_relation *ddr,
1955 int nb_loops, int first_loop_depth)
1958 lambda_vector dir_v, init_v;
1960 dir_v = lambda_vector_new (nb_loops);
1961 init_v = lambda_vector_new (nb_loops);
1962 lambda_vector_clear (dir_v, nb_loops);
1963 lambda_vector_clear (init_v, nb_loops);
1965 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
1968 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1970 tree access_fn_a, access_fn_b;
1971 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1973 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
1975 non_affine_dependence_relation (ddr);
1979 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
1980 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
1981 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
1982 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
1984 int dist, loop_nb, loop_depth;
1985 enum data_dependence_direction dir = dir_star;
1986 int loop_nb_a = CHREC_VARIABLE (access_fn_a);
1987 int loop_nb_b = CHREC_VARIABLE (access_fn_b);
1988 struct loop *loop_a = current_loops->parray[loop_nb_a];
1989 struct loop *loop_b = current_loops->parray[loop_nb_b];
1991 /* If the loop for either variable is at a lower depth than
1992 the first_loop's depth, then we can't possibly have a
1993 dependency at this level of the loop. */
1995 if (loop_a->depth < first_loop_depth
1996 || loop_b->depth < first_loop_depth)
1999 if (loop_nb_a != loop_nb_b
2000 && !flow_loop_nested_p (loop_a, loop_b)
2001 && !flow_loop_nested_p (loop_b, loop_a))
2003 /* Example: when there are two consecutive loops,
2012 the dependence relation cannot be captured by the
2013 distance abstraction. */
2014 non_affine_dependence_relation (ddr);
2018 /* The dependence is carried by the outermost loop. Example:
2025 In this case, the dependence is carried by loop_1. */
2026 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
2027 loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
2029 /* If the loop number is still greater than the number of
2030 loops we've been asked to analyze, or negative,
2031 something is borked. */
2032 gcc_assert (loop_depth >= 0);
2033 gcc_assert (loop_depth < nb_loops);
2035 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2037 non_affine_dependence_relation (ddr);
2041 dist = int_cst_value (SUB_DISTANCE (subscript));
2050 /* This is the subscript coupling test.
2055 There is no dependence. */
2056 if (init_v[loop_depth] != 0
2058 && (enum data_dependence_direction) dir_v[loop_depth] != dir
2059 && (enum data_dependence_direction) dir_v[loop_depth] != dir_star)
2061 finalize_ddr_dependent (ddr, chrec_known);
2065 dir_v[loop_depth] = dir;
2066 init_v[loop_depth] = 1;
2070 /* There is a distance of 1 on all the outer loops:
2072 Example: there is a dependence of distance 1 on loop_1 for the array A.
2078 struct loop *lca, *loop_a, *loop_b;
2079 struct data_reference *a = DDR_A (ddr);
2080 struct data_reference *b = DDR_B (ddr);
2082 loop_a = loop_containing_stmt (DR_STMT (a));
2083 loop_b = loop_containing_stmt (DR_STMT (b));
2085 /* Get the common ancestor loop. */
2086 lca = find_common_loop (loop_a, loop_b);
2087 lca_depth = lca->depth - first_loop_depth;
2089 gcc_assert (lca_depth >= 0);
2090 gcc_assert (lca_depth < nb_loops);
2092 /* For each outer loop where init_v is not set, the accesses are
2093 in dependence of distance 1 in the loop. */
2096 && init_v[lca_depth] == 0)
2097 dir_v[lca_depth] = dir_positive;
2102 lca_depth = lca->depth - first_loop_depth;
2103 while (lca->depth != 0)
2105 /* If we're considering just a sub-nest, then don't record
2106 any information on the outer loops. */
2110 gcc_assert (lca_depth < nb_loops);
2112 if (init_v[lca_depth] == 0)
2113 dir_v[lca_depth] = dir_positive;
2115 lca_depth = lca->depth - first_loop_depth;
2121 DDR_DIR_VECT (ddr) = dir_v;
2122 DDR_SIZE_VECT (ddr) = nb_loops;
2126 /* Returns true when all the access functions of A are affine or
2130 access_functions_are_affine_or_constant_p (struct data_reference *a)
2133 varray_type fns = DR_ACCESS_FNS (a);
2135 for (i = 0; i < VARRAY_ACTIVE_SIZE (fns); i++)
2136 if (!evolution_function_is_constant_p (VARRAY_TREE (fns, i))
2137 && !evolution_function_is_affine_multivariate_p (VARRAY_TREE (fns, i)))
2143 /* This computes the affine dependence relation between A and B.
2144 CHREC_KNOWN is used for representing the independence between two
2145 accesses, while CHREC_DONT_KNOW is used for representing the unknown
2148 Note that it is possible to stop the computation of the dependence
2149 relation the first time we detect a CHREC_KNOWN element for a given
2153 compute_affine_dependence (struct data_dependence_relation *ddr)
2155 struct data_reference *dra = DDR_A (ddr);
2156 struct data_reference *drb = DDR_B (ddr);
2158 if (dump_file && (dump_flags & TDF_DETAILS))
2160 fprintf (dump_file, "(compute_affine_dependence\n");
2161 fprintf (dump_file, " (stmt_a = \n");
2162 print_generic_expr (dump_file, DR_STMT (dra), 0);
2163 fprintf (dump_file, ")\n (stmt_b = \n");
2164 print_generic_expr (dump_file, DR_STMT (drb), 0);
2165 fprintf (dump_file, ")\n");
2168 /* Analyze only when the dependence relation is not yet known. */
2169 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
2171 if (access_functions_are_affine_or_constant_p (dra)
2172 && access_functions_are_affine_or_constant_p (drb))
2173 subscript_dependence_tester (ddr);
2175 /* As a last case, if the dependence cannot be determined, or if
2176 the dependence is considered too difficult to determine, answer
2179 finalize_ddr_dependent (ddr, chrec_dont_know);
2182 if (dump_file && (dump_flags & TDF_DETAILS))
2183 fprintf (dump_file, ")\n");
2186 /* Compute a subset of the data dependence relation graph. Don't
2187 compute read-read relations, and avoid the computation of the
2188 opposite relation, i.e. when AB has been computed, don't compute BA.
2189 DATAREFS contains a list of data references, and the result is set
2190 in DEPENDENCE_RELATIONS. */
2193 compute_all_dependences (varray_type datarefs,
2194 varray_type *dependence_relations)
2196 unsigned int i, j, N;
2198 N = VARRAY_ACTIVE_SIZE (datarefs);
2200 for (i = 0; i < N; i++)
2201 for (j = i; j < N; j++)
2203 struct data_reference *a, *b;
2204 struct data_dependence_relation *ddr;
2206 a = VARRAY_GENERIC_PTR (datarefs, i);
2207 b = VARRAY_GENERIC_PTR (datarefs, j);
2208 ddr = initialize_data_dependence_relation (a, b);
2210 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
2211 compute_affine_dependence (ddr);
2212 compute_subscript_distance (ddr);
2216 /* Search the data references in LOOP, and record the information into
2217 DATAREFS. Returns chrec_dont_know when failing to analyze a
2218 difficult case, returns NULL_TREE otherwise.
2220 TODO: This function should be made smarter so that it can handle address
2221 arithmetic as if they were array accesses, etc. */
2224 find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
2226 bool dont_know_node_not_inserted = true;
2227 basic_block bb, *bbs;
2229 block_stmt_iterator bsi;
2231 bbs = get_loop_body (loop);
2233 for (i = 0; i < loop->num_nodes; i++)
2237 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2239 tree stmt = bsi_stmt (bsi);
2240 stmt_ann_t ann = stmt_ann (stmt);
2242 if (TREE_CODE (stmt) != MODIFY_EXPR)
2246 && !V_MUST_DEF_OPS (ann)
2247 && !V_MAY_DEF_OPS (ann))
2250 /* In the GIMPLE representation, a modify expression
2251 contains a single load or store to memory. */
2252 if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF)
2253 VARRAY_PUSH_GENERIC_PTR
2254 (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 0),
2257 else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF)
2258 VARRAY_PUSH_GENERIC_PTR
2259 (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1),
2263 if (dont_know_node_not_inserted)
2265 struct data_reference *res;
2266 res = xmalloc (sizeof (struct data_reference));
2267 DR_STMT (res) = NULL_TREE;
2268 DR_REF (res) = NULL_TREE;
2269 DR_ACCESS_FNS (res) = NULL;
2270 DR_BASE_NAME (res) = NULL;
2271 DR_IS_READ (res) = false;
2272 VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
2273 dont_know_node_not_inserted = false;
2277 /* When there are no defs in the loop, the loop is parallel. */
2278 if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0
2279 || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0)
2280 bb->loop_father->parallel_p = false;
2283 if (bb->loop_father->estimated_nb_iterations == NULL_TREE)
2284 compute_estimated_nb_iterations (bb->loop_father);
2289 return dont_know_node_not_inserted ? NULL_TREE : chrec_dont_know;
2294 /* This section contains all the entry points. */
2296 /* Given a loop nest LOOP, the following vectors are returned:
2297 *DATAREFS is initialized to all the array elements contained in this loop,
2298 *DEPENDENCE_RELATIONS contains the relations between the data references. */
2301 compute_data_dependences_for_loop (unsigned nb_loops,
2303 varray_type *datarefs,
2304 varray_type *dependence_relations)
2307 varray_type allrelations;
2309 /* If one of the data references is not computable, give up without
2310 spending time to compute other dependences. */
2311 if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
2313 struct data_dependence_relation *ddr;
2315 /* Insert a single relation into dependence_relations:
2317 ddr = initialize_data_dependence_relation (NULL, NULL);
2318 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
2319 build_classic_dist_vector (ddr, nb_loops, loop->depth);
2320 build_classic_dir_vector (ddr, nb_loops, loop->depth);
2324 VARRAY_GENERIC_PTR_INIT (allrelations, 1, "Data dependence relations");
2325 compute_all_dependences (*datarefs, &allrelations);
2327 for (i = 0; i < VARRAY_ACTIVE_SIZE (allrelations); i++)
2329 struct data_dependence_relation *ddr;
2330 ddr = VARRAY_GENERIC_PTR (allrelations, i);
2331 if (build_classic_dist_vector (ddr, nb_loops, loop->depth))
2333 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
2334 build_classic_dir_vector (ddr, nb_loops, loop->depth);
2339 /* Entry point (for testing only). Analyze all the data references
2340 and the dependence relations.
2342 The data references are computed first.
2344 A relation on these nodes is represented by a complete graph. Some
2345 of the relations could be of no interest, thus the relations can be
2348 In the following function we compute all the relations. This is
2349 just a first implementation that is here for:
2350 - for showing how to ask for the dependence relations,
2351 - for the debugging the whole dependence graph,
2352 - for the dejagnu testcases and maintenance.
2354 It is possible to ask only for a part of the graph, avoiding to
2355 compute the whole dependence graph. The computed dependences are
2356 stored in a knowledge base (KB) such that later queries don't
2357 recompute the same information. The implementation of this KB is
2358 transparent to the optimizer, and thus the KB can be changed with a
2359 more efficient implementation, or the KB could be disabled. */
2362 analyze_all_data_dependences (struct loops *loops)
2365 varray_type datarefs;
2366 varray_type dependence_relations;
2367 int nb_data_refs = 10;
2369 VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
2370 VARRAY_GENERIC_PTR_INIT (dependence_relations,
2371 nb_data_refs * nb_data_refs,
2372 "dependence_relations");
2374 /* Compute DDs on the whole function. */
2375 compute_data_dependences_for_loop (loops->num, loops->parray[0],
2376 &datarefs, &dependence_relations);
2380 dump_data_dependence_relations (dump_file, dependence_relations);
2381 fprintf (dump_file, "\n\n");
2383 if (dump_flags & TDF_DETAILS)
2384 dump_dist_dir_vectors (dump_file, dependence_relations);
2386 if (dump_flags & TDF_STATS)
2388 unsigned nb_top_relations = 0;
2389 unsigned nb_bot_relations = 0;
2390 unsigned nb_basename_differ = 0;
2391 unsigned nb_chrec_relations = 0;
2393 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
2395 struct data_dependence_relation *ddr;
2396 ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
2398 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
2401 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
2403 struct data_reference *a = DDR_A (ddr);
2404 struct data_reference *b = DDR_B (ddr);
2407 if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
2408 || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
2409 nb_basename_differ++;
2415 nb_chrec_relations++;
2418 gather_stats_on_scev_database ();
2422 free_dependence_relations (dependence_relations);
2423 free_data_refs (datarefs);
2426 /* Free the memory used by a data dependence relation DDR. */
2429 free_dependence_relation (struct data_dependence_relation *ddr)
2434 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
2435 varray_clear (DDR_SUBSCRIPTS (ddr));
2439 /* Free the memory used by the data dependence relations from
2440 DEPENDENCE_RELATIONS. */
2443 free_dependence_relations (varray_type dependence_relations)
2446 if (dependence_relations == NULL)
2449 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
2450 free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
2451 varray_clear (dependence_relations);
2454 /* Free the memory used by the data references from DATAREFS. */
2457 free_data_refs (varray_type datarefs)
2461 if (datarefs == NULL)
2464 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
2466 struct data_reference *dr = (struct data_reference *)
2467 VARRAY_GENERIC_PTR (datarefs, i);
2470 if (DR_ACCESS_FNS (dr))
2471 varray_clear (DR_ACCESS_FNS (dr));
2475 varray_clear (datarefs);