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
1778 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
1779 int nb_loops
, unsigned int first_loop
)
1782 lambda_vector dist_v
, init_v
;
1784 dist_v
= lambda_vector_new (nb_loops
);
1785 init_v
= lambda_vector_new (nb_loops
);
1786 lambda_vector_clear (dist_v
, nb_loops
);
1787 lambda_vector_clear (init_v
, nb_loops
);
1789 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
1792 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1794 tree access_fn_a
, access_fn_b
;
1795 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
1797 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
1799 non_affine_dependence_relation (ddr
);
1803 access_fn_a
= DR_ACCESS_FN (DDR_A (ddr
), i
);
1804 access_fn_b
= DR_ACCESS_FN (DDR_B (ddr
), i
);
1806 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
1807 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
1810 int loop_nb_a
= CHREC_VARIABLE (access_fn_a
);
1811 int loop_nb_b
= CHREC_VARIABLE (access_fn_b
);
1812 struct loop
*loop_a
= current_loops
->parray
[loop_nb_a
];
1813 struct loop
*loop_b
= current_loops
->parray
[loop_nb_b
];
1815 if (loop_nb_a
!= loop_nb_b
1816 && !flow_loop_nested_p (loop_a
, loop_b
)
1817 && !flow_loop_nested_p (loop_b
, loop_a
))
1819 /* Example: when there are two consecutive loops,
1828 the dependence relation cannot be captured by the
1829 distance abstraction. */
1830 non_affine_dependence_relation (ddr
);
1834 /* The dependence is carried by the outermost loop. Example:
1841 In this case, the dependence is carried by loop_1. */
1842 loop_nb
= loop_nb_a
< loop_nb_b
? loop_nb_a
: loop_nb_b
;
1843 loop_nb
-= first_loop
;
1845 /* If the loop number is still greater than the number of
1846 loops we've been asked to analyze, or negative,
1847 something is borked. */
1848 gcc_assert (loop_nb
>= 0);
1849 gcc_assert (loop_nb
< nb_loops
);
1850 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
1852 non_affine_dependence_relation (ddr
);
1856 dist
= int_cst_value (SUB_DISTANCE (subscript
));
1858 /* This is the subscript coupling test.
1863 There is no dependence. */
1864 if (init_v
[loop_nb
] != 0
1865 && dist_v
[loop_nb
] != dist
)
1867 finalize_ddr_dependent (ddr
, chrec_known
);
1871 dist_v
[loop_nb
] = dist
;
1872 init_v
[loop_nb
] = 1;
1876 /* There is a distance of 1 on all the outer loops:
1878 Example: there is a dependence of distance 1 on loop_1 for the array A.
1884 struct loop
*lca
, *loop_a
, *loop_b
;
1885 struct data_reference
*a
= DDR_A (ddr
);
1886 struct data_reference
*b
= DDR_B (ddr
);
1888 loop_a
= loop_containing_stmt (DR_STMT (a
));
1889 loop_b
= loop_containing_stmt (DR_STMT (b
));
1891 /* Get the common ancestor loop. */
1892 lca
= find_common_loop (loop_a
, loop_b
);
1895 lca_nb
-= first_loop
;
1896 gcc_assert (lca_nb
>= 0);
1897 gcc_assert (lca_nb
< nb_loops
);
1899 /* For each outer loop where init_v is not set, the accesses are
1900 in dependence of distance 1 in the loop. */
1903 && init_v
[lca_nb
] == 0)
1910 lca_nb
= lca
->num
- first_loop
;
1911 while (lca
->depth
!= 0)
1913 /* If we're considering just a sub-nest, then don't record
1914 any information on the outer loops. */
1918 gcc_assert (lca_nb
< nb_loops
);
1920 if (init_v
[lca_nb
] == 0)
1923 lca_nb
= lca
->num
- first_loop
;
1929 DDR_DIST_VECT (ddr
) = dist_v
;
1930 DDR_SIZE_VECT (ddr
) = nb_loops
;
1933 /* Compute the classic per loop direction vector.
1935 DDR is the data dependence relation to build a vector from.
1936 NB_LOOPS is the total number of loops we are considering.
1937 FIRST_LOOP is the loop->num of the first loop in the analyzed
1941 build_classic_dir_vector (struct data_dependence_relation
*ddr
,
1942 int nb_loops
, unsigned int first_loop
)
1945 lambda_vector dir_v
, init_v
;
1947 dir_v
= lambda_vector_new (nb_loops
);
1948 init_v
= lambda_vector_new (nb_loops
);
1949 lambda_vector_clear (dir_v
, nb_loops
);
1950 lambda_vector_clear (init_v
, nb_loops
);
1952 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
1955 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1957 tree access_fn_a
, access_fn_b
;
1958 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
1960 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
1962 non_affine_dependence_relation (ddr
);
1966 access_fn_a
= DR_ACCESS_FN (DDR_A (ddr
), i
);
1967 access_fn_b
= DR_ACCESS_FN (DDR_B (ddr
), i
);
1968 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
1969 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
1972 enum data_dependence_direction dir
= dir_star
;
1973 int loop_nb_a
= CHREC_VARIABLE (access_fn_a
);
1974 int loop_nb_b
= CHREC_VARIABLE (access_fn_b
);
1975 struct loop
*loop_a
= current_loops
->parray
[loop_nb_a
];
1976 struct loop
*loop_b
= current_loops
->parray
[loop_nb_b
];
1978 if (loop_nb_a
!= loop_nb_b
1979 && !flow_loop_nested_p (loop_a
, loop_b
)
1980 && !flow_loop_nested_p (loop_b
, loop_a
))
1982 /* Example: when there are two consecutive loops,
1991 the dependence relation cannot be captured by the
1992 distance abstraction. */
1993 non_affine_dependence_relation (ddr
);
1997 /* The dependence is carried by the outermost loop. Example:
2004 In this case, the dependence is carried by loop_1. */
2005 loop_nb
= loop_nb_a
< loop_nb_b
? loop_nb_a
: loop_nb_b
;
2006 loop_nb
-= first_loop
;
2008 /* If the loop number is still greater than the number of
2009 loops we've been asked to analyze, or negative,
2010 something is borked. */
2011 gcc_assert (loop_nb
>= 0);
2012 gcc_assert (loop_nb
< nb_loops
);
2014 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2016 non_affine_dependence_relation (ddr
);
2020 dist
= int_cst_value (SUB_DISTANCE (subscript
));
2029 /* This is the subscript coupling test.
2034 There is no dependence. */
2035 if (init_v
[loop_nb
] != 0
2037 && (enum data_dependence_direction
) dir_v
[loop_nb
] != dir
2038 && (enum data_dependence_direction
) dir_v
[loop_nb
] != dir_star
)
2040 finalize_ddr_dependent (ddr
, chrec_known
);
2044 dir_v
[loop_nb
] = dir
;
2045 init_v
[loop_nb
] = 1;
2049 /* There is a distance of 1 on all the outer loops:
2051 Example: there is a dependence of distance 1 on loop_1 for the array A.
2057 struct loop
*lca
, *loop_a
, *loop_b
;
2058 struct data_reference
*a
= DDR_A (ddr
);
2059 struct data_reference
*b
= DDR_B (ddr
);
2061 loop_a
= loop_containing_stmt (DR_STMT (a
));
2062 loop_b
= loop_containing_stmt (DR_STMT (b
));
2064 /* Get the common ancestor loop. */
2065 lca
= find_common_loop (loop_a
, loop_b
);
2066 lca_nb
= lca
->num
- first_loop
;
2068 gcc_assert (lca_nb
>= 0);
2069 gcc_assert (lca_nb
< nb_loops
);
2071 /* For each outer loop where init_v is not set, the accesses are
2072 in dependence of distance 1 in the loop. */
2075 && init_v
[lca_nb
] == 0)
2076 dir_v
[lca_nb
] = dir_positive
;
2081 lca_nb
= lca
->num
- first_loop
;
2082 while (lca
->depth
!= 0)
2084 /* If we're considering just a sub-nest, then don't record
2085 any information on the outer loops. */
2089 gcc_assert (lca_nb
< nb_loops
);
2091 if (init_v
[lca_nb
] == 0)
2092 dir_v
[lca_nb
] = dir_positive
;
2094 lca_nb
= lca
->num
- first_loop
;
2100 DDR_DIR_VECT (ddr
) = dir_v
;
2101 DDR_SIZE_VECT (ddr
) = nb_loops
;
2104 /* Returns true when all the access functions of A are affine or
2108 access_functions_are_affine_or_constant_p (struct data_reference
*a
)
2111 varray_type fns
= DR_ACCESS_FNS (a
);
2113 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (fns
); i
++)
2114 if (!evolution_function_is_constant_p (VARRAY_TREE (fns
, i
))
2115 && !evolution_function_is_affine_multivariate_p (VARRAY_TREE (fns
, i
)))
2121 /* This computes the affine dependence relation between A and B.
2122 CHREC_KNOWN is used for representing the independence between two
2123 accesses, while CHREC_DONT_KNOW is used for representing the unknown
2126 Note that it is possible to stop the computation of the dependence
2127 relation the first time we detect a CHREC_KNOWN element for a given
2131 compute_affine_dependence (struct data_dependence_relation
*ddr
)
2133 struct data_reference
*dra
= DDR_A (ddr
);
2134 struct data_reference
*drb
= DDR_B (ddr
);
2136 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2138 fprintf (dump_file
, "(compute_affine_dependence\n");
2139 fprintf (dump_file
, " (stmt_a = \n");
2140 print_generic_expr (dump_file
, DR_STMT (dra
), 0);
2141 fprintf (dump_file
, ")\n (stmt_b = \n");
2142 print_generic_expr (dump_file
, DR_STMT (drb
), 0);
2143 fprintf (dump_file
, ")\n");
2146 /* Analyze only when the dependence relation is not yet known. */
2147 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
2149 if (access_functions_are_affine_or_constant_p (dra
)
2150 && access_functions_are_affine_or_constant_p (drb
))
2151 subscript_dependence_tester (ddr
);
2153 /* As a last case, if the dependence cannot be determined, or if
2154 the dependence is considered too difficult to determine, answer
2157 finalize_ddr_dependent (ddr
, chrec_dont_know
);
2160 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2161 fprintf (dump_file
, ")\n");
2164 /* Compute a subset of the data dependence relation graph. Don't
2165 compute read-read relations, and avoid the computation of the
2166 opposite relation, i.e. when AB has been computed, don't compute BA.
2167 DATAREFS contains a list of data references, and the result is set
2168 in DEPENDENCE_RELATIONS. */
2171 compute_all_dependences (varray_type datarefs
,
2172 varray_type
*dependence_relations
)
2174 unsigned int i
, j
, N
;
2176 N
= VARRAY_ACTIVE_SIZE (datarefs
);
2178 for (i
= 0; i
< N
; i
++)
2179 for (j
= i
; j
< N
; j
++)
2181 struct data_reference
*a
, *b
;
2182 struct data_dependence_relation
*ddr
;
2184 a
= VARRAY_GENERIC_PTR (datarefs
, i
);
2185 b
= VARRAY_GENERIC_PTR (datarefs
, j
);
2186 ddr
= initialize_data_dependence_relation (a
, b
);
2188 VARRAY_PUSH_GENERIC_PTR (*dependence_relations
, ddr
);
2189 compute_affine_dependence (ddr
);
2190 compute_subscript_distance (ddr
);
2194 /* Search the data references in LOOP, and record the information into
2195 DATAREFS. Returns chrec_dont_know when failing to analyze a
2196 difficult case, returns NULL_TREE otherwise.
2198 FIXME: This is a "dumb" walker over all the trees in the loop body.
2199 Find another technique that avoids this costly walk. This is
2200 acceptable for the moment, since this function is used only for
2201 debugging purposes. */
2204 find_data_references_in_loop (struct loop
*loop
, varray_type
*datarefs
)
2206 bool dont_know_node_not_inserted
= true;
2208 block_stmt_iterator bsi
;
2212 if (!flow_bb_inside_loop_p (loop
, bb
))
2215 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
2217 tree stmt
= bsi_stmt (bsi
);
2218 stmt_ann_t ann
= stmt_ann (stmt
);
2220 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
2224 && !V_MUST_DEF_OPS (ann
)
2225 && !V_MAY_DEF_OPS (ann
))
2228 /* In the GIMPLE representation, a modify expression
2229 contains a single load or store to memory. */
2230 if (TREE_CODE (TREE_OPERAND (stmt
, 0)) == ARRAY_REF
)
2231 VARRAY_PUSH_GENERIC_PTR
2232 (*datarefs
, analyze_array (stmt
, TREE_OPERAND (stmt
, 0),
2235 else if (TREE_CODE (TREE_OPERAND (stmt
, 1)) == ARRAY_REF
)
2236 VARRAY_PUSH_GENERIC_PTR
2237 (*datarefs
, analyze_array (stmt
, TREE_OPERAND (stmt
, 1),
2242 if (dont_know_node_not_inserted
)
2244 struct data_reference
*res
;
2245 res
= xmalloc (sizeof (struct data_reference
));
2246 DR_STMT (res
) = NULL_TREE
;
2247 DR_REF (res
) = NULL_TREE
;
2248 DR_ACCESS_FNS (res
) = NULL
;
2249 DR_BASE_NAME (res
) = NULL
;
2250 DR_IS_READ (res
) = false;
2251 VARRAY_PUSH_GENERIC_PTR (*datarefs
, res
);
2253 dont_know_node_not_inserted
= false;
2257 /* When there are no defs in the loop, the loop is parallel. */
2258 if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt
)) > 0
2259 || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt
)) > 0)
2260 bb
->loop_father
->parallel_p
= false;
2263 if (bb
->loop_father
->estimated_nb_iterations
== NULL_TREE
)
2264 compute_estimated_nb_iterations (bb
->loop_father
);
2267 return dont_know_node_not_inserted
? NULL_TREE
: chrec_dont_know
;
2272 /* This section contains all the entry points. */
2274 /* Given a loop nest LOOP, the following vectors are returned:
2275 *DATAREFS is initialized to all the array elements contained in this loop,
2276 *DEPENDENCE_RELATIONS contains the relations between the data references. */
2279 compute_data_dependences_for_loop (unsigned nb_loops
,
2281 varray_type
*datarefs
,
2282 varray_type
*dependence_relations
)
2286 /* If one of the data references is not computable, give up without
2287 spending time to compute other dependences. */
2288 if (find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
2290 struct data_dependence_relation
*ddr
;
2292 /* Insert a single relation into dependence_relations:
2294 ddr
= initialize_data_dependence_relation (NULL
, NULL
);
2295 VARRAY_PUSH_GENERIC_PTR (*dependence_relations
, ddr
);
2296 build_classic_dist_vector (ddr
, nb_loops
, loop
->num
);
2297 build_classic_dir_vector (ddr
, nb_loops
, loop
->num
);
2301 compute_all_dependences (*datarefs
, dependence_relations
);
2303 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (*dependence_relations
); i
++)
2305 struct data_dependence_relation
*ddr
;
2306 ddr
= VARRAY_GENERIC_PTR (*dependence_relations
, i
);
2307 build_classic_dist_vector (ddr
, nb_loops
, loop
->num
);
2308 build_classic_dir_vector (ddr
, nb_loops
, loop
->num
);
2312 /* Entry point (for testing only). Analyze all the data references
2313 and the dependence relations.
2315 The data references are computed first.
2317 A relation on these nodes is represented by a complete graph. Some
2318 of the relations could be of no interest, thus the relations can be
2321 In the following function we compute all the relations. This is
2322 just a first implementation that is here for:
2323 - for showing how to ask for the dependence relations,
2324 - for the debugging the whole dependence graph,
2325 - for the dejagnu testcases and maintenance.
2327 It is possible to ask only for a part of the graph, avoiding to
2328 compute the whole dependence graph. The computed dependences are
2329 stored in a knowledge base (KB) such that later queries don't
2330 recompute the same information. The implementation of this KB is
2331 transparent to the optimizer, and thus the KB can be changed with a
2332 more efficient implementation, or the KB could be disabled. */
2335 analyze_all_data_dependences (struct loops
*loops
)
2338 varray_type datarefs
;
2339 varray_type dependence_relations
;
2340 int nb_data_refs
= 10;
2342 VARRAY_GENERIC_PTR_INIT (datarefs
, nb_data_refs
, "datarefs");
2343 VARRAY_GENERIC_PTR_INIT (dependence_relations
,
2344 nb_data_refs
* nb_data_refs
,
2345 "dependence_relations");
2347 /* Compute DDs on the whole function. */
2348 compute_data_dependences_for_loop (loops
->num
, loops
->parray
[0],
2349 &datarefs
, &dependence_relations
);
2353 dump_data_dependence_relations (dump_file
, dependence_relations
);
2354 fprintf (dump_file
, "\n\n");
2356 if (dump_flags
& TDF_DETAILS
)
2357 dump_dist_dir_vectors (dump_file
, dependence_relations
);
2359 if (dump_flags
& TDF_STATS
)
2361 unsigned nb_top_relations
= 0;
2362 unsigned nb_bot_relations
= 0;
2363 unsigned nb_basename_differ
= 0;
2364 unsigned nb_chrec_relations
= 0;
2366 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (dependence_relations
); i
++)
2368 struct data_dependence_relation
*ddr
;
2369 ddr
= VARRAY_GENERIC_PTR (dependence_relations
, i
);
2371 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
2374 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
2376 struct data_reference
*a
= DDR_A (ddr
);
2377 struct data_reference
*b
= DDR_B (ddr
);
2380 if (DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
)
2381 || (array_base_name_differ_p (a
, b
, &differ_p
) && differ_p
))
2382 nb_basename_differ
++;
2388 nb_chrec_relations
++;
2391 gather_stats_on_scev_database ();
2395 free_dependence_relations (dependence_relations
);
2396 free_data_refs (datarefs
);
2399 /* Free the memory used by a data dependence relation DDR. */
2402 free_dependence_relation (struct data_dependence_relation
*ddr
)
2407 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_SUBSCRIPTS (ddr
))
2408 varray_clear (DDR_SUBSCRIPTS (ddr
));
2412 /* Free the memory used by the data dependence relations from
2413 DEPENDENCE_RELATIONS. */
2416 free_dependence_relations (varray_type dependence_relations
)
2419 if (dependence_relations
== NULL
)
2422 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (dependence_relations
); i
++)
2423 free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations
, i
));
2424 varray_clear (dependence_relations
);
2427 /* Free the memory used by the data references from DATAREFS. */
2430 free_data_refs (varray_type datarefs
)
2434 if (datarefs
== NULL
)
2437 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (datarefs
); i
++)
2439 struct data_reference
*dr
= (struct data_reference
*)
2440 VARRAY_GENERIC_PTR (datarefs
, i
);
2441 if (dr
&& DR_ACCESS_FNS (dr
))
2442 varray_clear (DR_ACCESS_FNS (dr
));
2444 varray_clear (datarefs
);