1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 /* This pass walks a given loop structure searching for array
23 references. The information about the array accesses is recorded
24 in DATA_REFERENCE structures.
26 The basic test for determining the dependences is:
27 given two access functions chrec1 and chrec2 to a same array, and
28 x and y two vectors from the iteration domain, the same element of
29 the array is accessed twice at iterations x and y if and only if:
30 | chrec1 (x) == chrec2 (y).
32 The goals of this analysis are:
34 - to determine the independence: the relation between two
35 independent accesses is qualified with the chrec_known (this
36 information allows a loop parallelization),
38 - when two data references access the same data, to qualify the
39 dependence relation with classic dependence representations:
43 - loop carried level dependence
44 - polyhedron dependence
45 or with the chains of recurrences based representation,
47 - to define a knowledge base for storing the data dependence
50 - to define an interface to access this data.
55 - subscript: given two array accesses a subscript is the tuple
56 composed of the access functions for a given dimension. Example:
57 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
58 (f1, g1), (f2, g2), (f3, g3).
60 - Diophantine equation: an equation whose coefficients and
61 solutions are integer constants, for example the equation
63 has an integer solution x = 1 and y = -1.
67 - "Advanced Compilation for High Performance Computing" by Randy
68 Allen and Ken Kennedy.
69 http://citeseer.ist.psu.edu/goff91practical.html
71 - "Loop Transformations for Restructuring Compilers - The Foundations"
79 #include "coretypes.h"
84 /* These RTL headers are needed for basic-block.h. */
86 #include "basic-block.h"
87 #include "diagnostic.h"
88 #include "tree-flow.h"
89 #include "tree-dump.h"
92 #include "tree-chrec.h"
93 #include "tree-data-ref.h"
94 #include "tree-scalar-evolution.h"
95 #include "tree-pass.h"
97 /* This is the simplest data dependence test: determines whether the
98 data references A and B access the same array/region. Returns
99 false when the property is not computable at compile time.
100 Otherwise return true, and DIFFER_P will record the result. This
101 utility will not be necessary when alias_sets_conflict_p will be
102 less conservative. */
105 array_base_name_differ_p (struct data_reference
*a
,
106 struct data_reference
*b
,
109 tree base_a
= DR_BASE_NAME (a
);
110 tree base_b
= DR_BASE_NAME (b
);
112 if (!base_a
|| !base_b
)
115 /* Determine if same base. Example: for the array accesses
116 a[i], b[i] or pointer accesses *a, *b, bases are a, b. */
117 if (base_a
== base_b
)
123 /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
125 if (TREE_CODE (base_a
) == INDIRECT_REF
&& TREE_CODE (base_b
) == INDIRECT_REF
126 && TREE_OPERAND (base_a
, 0) == TREE_OPERAND (base_b
, 0))
132 /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */
133 if (TREE_CODE (base_a
) == COMPONENT_REF
&& TREE_CODE (base_b
) == COMPONENT_REF
134 && TREE_OPERAND (base_a
, 0) == TREE_OPERAND (base_b
, 0)
135 && TREE_OPERAND (base_a
, 1) == TREE_OPERAND (base_b
, 1))
142 /* Determine if different bases. */
144 /* At this point we know that base_a != base_b. However, pointer
145 accesses of the form x=(*p) and y=(*q), whose bases are p and q,
146 may still be pointing to the same base. In SSAed GIMPLE p and q will
147 be SSA_NAMES in this case. Therefore, here we check if they are
148 really two different declarations. */
149 if (TREE_CODE (base_a
) == VAR_DECL
&& TREE_CODE (base_b
) == VAR_DECL
)
155 /* Compare two record/union bases s.a and t.b: s != t or (a != b and
156 s and t are not unions). */
157 if (TREE_CODE (base_a
) == COMPONENT_REF
&& TREE_CODE (base_b
) == COMPONENT_REF
158 && ((TREE_CODE (TREE_OPERAND (base_a
, 0)) == VAR_DECL
159 && TREE_CODE (TREE_OPERAND (base_b
, 0)) == VAR_DECL
160 && TREE_OPERAND (base_a
, 0) != TREE_OPERAND (base_b
, 0))
161 || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a
, 0))) == RECORD_TYPE
162 && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b
, 0))) == RECORD_TYPE
163 && TREE_OPERAND (base_a
, 1) != TREE_OPERAND (base_b
, 1))))
169 /* Compare a record/union access and an array access. */
170 if ((TREE_CODE (base_a
) == VAR_DECL
171 && (TREE_CODE (base_b
) == COMPONENT_REF
172 && TREE_CODE (TREE_OPERAND (base_b
, 0)) == VAR_DECL
))
173 || (TREE_CODE (base_b
) == VAR_DECL
174 && (TREE_CODE (base_a
) == COMPONENT_REF
175 && TREE_CODE (TREE_OPERAND (base_a
, 0)) == VAR_DECL
)))
184 /* Returns true iff A divides B. */
187 tree_fold_divides_p (tree type
,
191 /* Determines whether (A == gcd (A, B)). */
193 (fold_build2 (MINUS_EXPR
, type
, a
, tree_fold_gcd (a
, b
)));
196 /* Compute the greatest common denominator of two numbers using
197 Euclid's algorithm. */
218 /* Returns true iff A divides B. */
221 int_divides_p (int a
, int b
)
223 return ((b
% a
) == 0);
228 /* Dump into FILE all the data references from DATAREFS. */
231 dump_data_references (FILE *file
,
232 varray_type datarefs
)
236 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (datarefs
); i
++)
237 dump_data_reference (file
, VARRAY_GENERIC_PTR (datarefs
, i
));
240 /* Dump into FILE all the dependence relations from DDR. */
243 dump_data_dependence_relations (FILE *file
,
248 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ddr
); i
++)
249 dump_data_dependence_relation (file
, VARRAY_GENERIC_PTR (ddr
, i
));
252 /* Dump function for a DATA_REFERENCE structure. */
255 dump_data_reference (FILE *outf
,
256 struct data_reference
*dr
)
260 fprintf (outf
, "(Data Ref: \n stmt: ");
261 print_generic_stmt (outf
, DR_STMT (dr
), 0);
262 fprintf (outf
, " ref: ");
263 print_generic_stmt (outf
, DR_REF (dr
), 0);
264 fprintf (outf
, " base_name: ");
265 print_generic_stmt (outf
, DR_BASE_NAME (dr
), 0);
267 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
269 fprintf (outf
, " Access function %d: ", i
);
270 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
272 fprintf (outf
, ")\n");
275 /* Dump function for a SUBSCRIPT structure. */
278 dump_subscript (FILE *outf
, struct subscript
*subscript
)
280 tree chrec
= SUB_CONFLICTS_IN_A (subscript
);
282 fprintf (outf
, "\n (subscript \n");
283 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
284 print_generic_stmt (outf
, chrec
, 0);
285 if (chrec
== chrec_known
)
286 fprintf (outf
, " (no dependence)\n");
287 else if (chrec_contains_undetermined (chrec
))
288 fprintf (outf
, " (don't know)\n");
291 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
292 fprintf (outf
, " last_conflict: ");
293 print_generic_stmt (outf
, last_iteration
, 0);
296 chrec
= SUB_CONFLICTS_IN_B (subscript
);
297 fprintf (outf
, " iterations_that_access_an_element_twice_in_B: ");
298 print_generic_stmt (outf
, chrec
, 0);
299 if (chrec
== chrec_known
)
300 fprintf (outf
, " (no dependence)\n");
301 else if (chrec_contains_undetermined (chrec
))
302 fprintf (outf
, " (don't know)\n");
305 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
306 fprintf (outf
, " last_conflict: ");
307 print_generic_stmt (outf
, last_iteration
, 0);
310 fprintf (outf
, " (Subscript distance: ");
311 print_generic_stmt (outf
, SUB_DISTANCE (subscript
), 0);
312 fprintf (outf
, " )\n");
313 fprintf (outf
, " )\n");
316 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
319 dump_data_dependence_relation (FILE *outf
,
320 struct data_dependence_relation
*ddr
)
322 struct data_reference
*dra
, *drb
;
326 fprintf (outf
, "(Data Dep: \n");
327 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
328 fprintf (outf
, " (don't know)\n");
330 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
331 fprintf (outf
, " (no dependence)\n");
333 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
336 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
338 fprintf (outf
, " access_fn_A: ");
339 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
340 fprintf (outf
, " access_fn_B: ");
341 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
342 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
344 if (DDR_DIST_VECT (ddr
))
346 fprintf (outf
, " distance_vect: ");
347 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
), DDR_SIZE_VECT (ddr
));
349 if (DDR_DIR_VECT (ddr
))
351 fprintf (outf
, " direction_vect: ");
352 print_lambda_vector (outf
, DDR_DIR_VECT (ddr
), DDR_SIZE_VECT (ddr
));
356 fprintf (outf
, ")\n");
361 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
364 dump_data_dependence_direction (FILE *file
,
365 enum data_dependence_direction dir
)
381 case dir_positive_or_negative
:
382 fprintf (file
, "+-");
385 case dir_positive_or_equal
:
386 fprintf (file
, "+=");
389 case dir_negative_or_equal
:
390 fprintf (file
, "-=");
402 /* Dumps the distance and direction vectors in FILE. DDRS contains
403 the dependence relations, and VECT_SIZE is the size of the
404 dependence vectors, or in other words the number of loops in the
408 dump_dist_dir_vectors (FILE *file
, varray_type ddrs
)
412 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ddrs
); i
++)
414 struct data_dependence_relation
*ddr
=
415 (struct data_dependence_relation
*)
416 VARRAY_GENERIC_PTR (ddrs
, i
);
417 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
418 && DDR_AFFINE_P (ddr
))
420 fprintf (file
, "DISTANCE_V (");
421 print_lambda_vector (file
, DDR_DIST_VECT (ddr
), DDR_SIZE_VECT (ddr
));
422 fprintf (file
, ")\n");
423 fprintf (file
, "DIRECTION_V (");
424 print_lambda_vector (file
, DDR_DIR_VECT (ddr
), DDR_SIZE_VECT (ddr
));
425 fprintf (file
, ")\n");
428 fprintf (file
, "\n\n");
431 /* Dumps the data dependence relations DDRS in FILE. */
434 dump_ddrs (FILE *file
, varray_type ddrs
)
438 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ddrs
); i
++)
440 struct data_dependence_relation
*ddr
=
441 (struct data_dependence_relation
*)
442 VARRAY_GENERIC_PTR (ddrs
, i
);
443 dump_data_dependence_relation (file
, ddr
);
445 fprintf (file
, "\n\n");
450 /* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
451 approximation of the number of iterations for LOOP. */
454 compute_estimated_nb_iterations (struct loop
*loop
)
456 struct nb_iter_bound
*bound
;
458 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
459 if (TREE_CODE (bound
->bound
) == INTEGER_CST
460 /* Update only when there is no previous estimation. */
461 && (chrec_contains_undetermined (loop
->estimated_nb_iterations
)
462 /* Or when the current estimation is smaller. */
463 || tree_int_cst_lt (bound
->bound
, loop
->estimated_nb_iterations
)))
464 loop
->estimated_nb_iterations
= bound
->bound
;
467 /* Estimate the number of iterations from the size of the data and the
471 estimate_niter_from_size_of_data (struct loop
*loop
,
477 tree array_size
, data_size
, element_size
;
480 init
= initial_condition (access_fn
);
481 step
= evolution_part_in_loop_num (access_fn
, loop
->num
);
483 array_size
= TYPE_SIZE (TREE_TYPE (opnd0
));
484 element_size
= TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0
)));
485 if (array_size
== NULL_TREE
486 || TREE_CODE (array_size
) != INTEGER_CST
487 || TREE_CODE (element_size
) != INTEGER_CST
)
490 data_size
= fold_build2 (EXACT_DIV_EXPR
, integer_type_node
,
491 array_size
, element_size
);
493 if (init
!= NULL_TREE
495 && TREE_CODE (init
) == INTEGER_CST
496 && TREE_CODE (step
) == INTEGER_CST
)
498 estimation
= fold_build2 (CEIL_DIV_EXPR
, integer_type_node
,
499 fold_build2 (MINUS_EXPR
, integer_type_node
,
500 data_size
, init
), step
);
502 record_estimate (loop
, estimation
, boolean_true_node
, stmt
);
506 /* Given an ARRAY_REF node REF, records its access functions.
507 Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
508 i.e. the constant "3", then recursively call the function on opnd0,
509 i.e. the ARRAY_REF "A[i]". The function returns the base name:
513 analyze_array_indexes (struct loop
*loop
,
514 VEC(tree
,heap
) **access_fns
,
520 opnd0
= TREE_OPERAND (ref
, 0);
521 opnd1
= TREE_OPERAND (ref
, 1);
523 /* The detection of the evolution function for this data access is
524 postponed until the dependence test. This lazy strategy avoids
525 the computation of access functions that are of no interest for
527 access_fn
= instantiate_parameters
528 (loop
, analyze_scalar_evolution (loop
, opnd1
));
530 if (chrec_contains_undetermined (loop
->estimated_nb_iterations
))
531 estimate_niter_from_size_of_data (loop
, opnd0
, access_fn
, stmt
);
533 VEC_safe_push (tree
, heap
, *access_fns
, access_fn
);
535 /* Recursively record other array access functions. */
536 if (TREE_CODE (opnd0
) == ARRAY_REF
)
537 return analyze_array_indexes (loop
, access_fns
, opnd0
, stmt
);
539 /* Return the base name of the data access. */
544 /* For a data reference REF contained in the statement STMT, initialize
545 a DATA_REFERENCE structure, and return it. IS_READ flag has to be
546 set to true when REF is in the right hand side of an
549 struct data_reference
*
550 analyze_array (tree stmt
, tree ref
, bool is_read
)
552 struct data_reference
*res
;
554 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
556 fprintf (dump_file
, "(analyze_array \n");
557 fprintf (dump_file
, " (ref = ");
558 print_generic_stmt (dump_file
, ref
, 0);
559 fprintf (dump_file
, ")\n");
562 res
= xmalloc (sizeof (struct data_reference
));
564 DR_STMT (res
) = stmt
;
566 DR_ACCESS_FNS (res
) = VEC_alloc (tree
, heap
, 3);
567 DR_BASE_NAME (res
) = analyze_array_indexes
568 (loop_containing_stmt (stmt
), &(DR_ACCESS_FNS (res
)), ref
, stmt
);
569 DR_IS_READ (res
) = is_read
;
571 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
572 fprintf (dump_file
, ")\n");
577 /* For a data reference REF contained in the statement STMT, initialize
578 a DATA_REFERENCE structure, and return it. */
580 struct data_reference
*
581 init_data_ref (tree stmt
,
587 struct data_reference
*res
;
589 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
591 fprintf (dump_file
, "(init_data_ref \n");
592 fprintf (dump_file
, " (ref = ");
593 print_generic_stmt (dump_file
, ref
, 0);
594 fprintf (dump_file
, ")\n");
597 res
= xmalloc (sizeof (struct data_reference
));
599 DR_STMT (res
) = stmt
;
601 DR_ACCESS_FNS (res
) = VEC_alloc (tree
, heap
, 5);
602 DR_BASE_NAME (res
) = base
;
603 VEC_quick_push (tree
, DR_ACCESS_FNS (res
), access_fn
);
604 DR_IS_READ (res
) = is_read
;
606 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
607 fprintf (dump_file
, ")\n");
614 /* Returns true when all the functions of a tree_vec CHREC are the
618 all_chrecs_equal_p (tree chrec
)
622 for (j
= 0; j
< TREE_VEC_LENGTH (chrec
) - 1; j
++)
624 tree chrec_j
= TREE_VEC_ELT (chrec
, j
);
625 tree chrec_j_1
= TREE_VEC_ELT (chrec
, j
+ 1);
628 (integer_type_node
, chrec_j
, chrec_j_1
)))
634 /* Determine for each subscript in the data dependence relation DDR
638 compute_subscript_distance (struct data_dependence_relation
*ddr
)
640 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
644 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
646 tree conflicts_a
, conflicts_b
, difference
;
647 struct subscript
*subscript
;
649 subscript
= DDR_SUBSCRIPT (ddr
, i
);
650 conflicts_a
= SUB_CONFLICTS_IN_A (subscript
);
651 conflicts_b
= SUB_CONFLICTS_IN_B (subscript
);
653 if (TREE_CODE (conflicts_a
) == TREE_VEC
)
655 if (!all_chrecs_equal_p (conflicts_a
))
657 SUB_DISTANCE (subscript
) = chrec_dont_know
;
661 conflicts_a
= TREE_VEC_ELT (conflicts_a
, 0);
664 if (TREE_CODE (conflicts_b
) == TREE_VEC
)
666 if (!all_chrecs_equal_p (conflicts_b
))
668 SUB_DISTANCE (subscript
) = chrec_dont_know
;
672 conflicts_b
= TREE_VEC_ELT (conflicts_b
, 0);
675 difference
= chrec_fold_minus
676 (integer_type_node
, conflicts_b
, conflicts_a
);
678 if (evolution_function_is_constant_p (difference
))
679 SUB_DISTANCE (subscript
) = difference
;
682 SUB_DISTANCE (subscript
) = chrec_dont_know
;
687 /* Initialize a ddr. */
689 struct data_dependence_relation
*
690 initialize_data_dependence_relation (struct data_reference
*a
,
691 struct data_reference
*b
)
693 struct data_dependence_relation
*res
;
696 res
= xmalloc (sizeof (struct data_dependence_relation
));
700 if (a
== NULL
|| b
== NULL
701 || DR_BASE_NAME (a
) == NULL_TREE
702 || DR_BASE_NAME (b
) == NULL_TREE
)
703 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
705 /* When the dimensions of A and B differ, we directly initialize
706 the relation to "there is no dependence": chrec_known. */
707 else if (DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
)
708 || (array_base_name_differ_p (a
, b
, &differ_p
) && differ_p
))
709 DDR_ARE_DEPENDENT (res
) = chrec_known
;
714 DDR_AFFINE_P (res
) = true;
715 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
716 DDR_SUBSCRIPTS_VECTOR_INIT (res
, DR_NUM_DIMENSIONS (a
));
717 DDR_SIZE_VECT (res
) = 0;
718 DDR_DIST_VECT (res
) = NULL
;
719 DDR_DIR_VECT (res
) = NULL
;
721 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
723 struct subscript
*subscript
;
725 subscript
= xmalloc (sizeof (struct subscript
));
726 SUB_CONFLICTS_IN_A (subscript
) = chrec_dont_know
;
727 SUB_CONFLICTS_IN_B (subscript
) = chrec_dont_know
;
728 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
729 SUB_DISTANCE (subscript
) = chrec_dont_know
;
730 VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res
), subscript
);
737 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
741 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
744 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
746 fprintf (dump_file
, "(dependence classified: ");
747 print_generic_expr (dump_file
, chrec
, 0);
748 fprintf (dump_file
, ")\n");
751 DDR_ARE_DEPENDENT (ddr
) = chrec
;
752 varray_clear (DDR_SUBSCRIPTS (ddr
));
755 /* The dependence relation DDR cannot be represented by a distance
759 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
761 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
762 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
764 DDR_AFFINE_P (ddr
) = false;
769 /* This section contains the classic Banerjee tests. */
771 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
772 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
775 ziv_subscript_p (tree chrec_a
,
778 return (evolution_function_is_constant_p (chrec_a
)
779 && evolution_function_is_constant_p (chrec_b
));
782 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
783 variable, i.e., if the SIV (Single Index Variable) test is true. */
786 siv_subscript_p (tree chrec_a
,
789 if ((evolution_function_is_constant_p (chrec_a
)
790 && evolution_function_is_univariate_p (chrec_b
))
791 || (evolution_function_is_constant_p (chrec_b
)
792 && evolution_function_is_univariate_p (chrec_a
)))
795 if (evolution_function_is_univariate_p (chrec_a
)
796 && evolution_function_is_univariate_p (chrec_b
))
798 switch (TREE_CODE (chrec_a
))
800 case POLYNOMIAL_CHREC
:
801 switch (TREE_CODE (chrec_b
))
803 case POLYNOMIAL_CHREC
:
804 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
819 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
820 *OVERLAPS_B are initialized to the functions that describe the
821 relation between the elements accessed twice by CHREC_A and
822 CHREC_B. For k >= 0, the following property is verified:
824 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
827 analyze_ziv_subscript (tree chrec_a
,
831 tree
*last_conflicts
)
835 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
836 fprintf (dump_file
, "(analyze_ziv_subscript \n");
838 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
840 switch (TREE_CODE (difference
))
843 if (integer_zerop (difference
))
845 /* The difference is equal to zero: the accessed index
846 overlaps for each iteration in the loop. */
847 *overlaps_a
= integer_zero_node
;
848 *overlaps_b
= integer_zero_node
;
849 *last_conflicts
= chrec_dont_know
;
853 /* The accesses do not overlap. */
854 *overlaps_a
= chrec_known
;
855 *overlaps_b
= chrec_known
;
856 *last_conflicts
= integer_zero_node
;
861 /* We're not sure whether the indexes overlap. For the moment,
862 conservatively answer "don't know". */
863 *overlaps_a
= chrec_dont_know
;
864 *overlaps_b
= chrec_dont_know
;
865 *last_conflicts
= chrec_dont_know
;
869 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
870 fprintf (dump_file
, ")\n");
873 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
874 constant, and CHREC_B is an affine function. *OVERLAPS_A and
875 *OVERLAPS_B are initialized to the functions that describe the
876 relation between the elements accessed twice by CHREC_A and
877 CHREC_B. For k >= 0, the following property is verified:
879 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
882 analyze_siv_subscript_cst_affine (tree chrec_a
,
886 tree
*last_conflicts
)
888 bool value0
, value1
, value2
;
889 tree difference
= chrec_fold_minus
890 (integer_type_node
, CHREC_LEFT (chrec_b
), chrec_a
);
892 if (!chrec_is_positive (initial_condition (difference
), &value0
))
894 *overlaps_a
= chrec_dont_know
;
895 *overlaps_b
= chrec_dont_know
;
896 *last_conflicts
= chrec_dont_know
;
903 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
905 *overlaps_a
= chrec_dont_know
;
906 *overlaps_b
= chrec_dont_know
;
907 *last_conflicts
= chrec_dont_know
;
919 if (tree_fold_divides_p
920 (integer_type_node
, CHREC_RIGHT (chrec_b
), difference
))
922 *overlaps_a
= integer_zero_node
;
923 *overlaps_b
= fold_build2 (EXACT_DIV_EXPR
, integer_type_node
,
924 fold_build1 (ABS_EXPR
,
927 CHREC_RIGHT (chrec_b
));
928 *last_conflicts
= integer_one_node
;
932 /* When the step does not divides the difference, there are
936 *overlaps_a
= chrec_known
;
937 *overlaps_b
= chrec_known
;
938 *last_conflicts
= integer_zero_node
;
947 chrec_b = {10, +, -1}
949 In this case, chrec_a will not overlap with chrec_b. */
950 *overlaps_a
= chrec_known
;
951 *overlaps_b
= chrec_known
;
952 *last_conflicts
= integer_zero_node
;
959 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
961 *overlaps_a
= chrec_dont_know
;
962 *overlaps_b
= chrec_dont_know
;
963 *last_conflicts
= chrec_dont_know
;
972 chrec_b = {10, +, -1}
974 if (tree_fold_divides_p
975 (integer_type_node
, CHREC_RIGHT (chrec_b
), difference
))
977 *overlaps_a
= integer_zero_node
;
979 (build (EXACT_DIV_EXPR
, integer_type_node
, difference
,
980 CHREC_RIGHT (chrec_b
)));
981 *last_conflicts
= integer_one_node
;
985 /* When the step does not divides the difference, there
989 *overlaps_a
= chrec_known
;
990 *overlaps_b
= chrec_known
;
991 *last_conflicts
= integer_zero_node
;
1001 In this case, chrec_a will not overlap with chrec_b. */
1002 *overlaps_a
= chrec_known
;
1003 *overlaps_b
= chrec_known
;
1004 *last_conflicts
= integer_zero_node
;
1012 /* Helper recursive function for initializing the matrix A. Returns
1013 the initial value of CHREC. */
1016 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
1020 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1021 return int_cst_value (chrec
);
1023 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
1024 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
1027 #define FLOOR_DIV(x,y) ((x) / (y))
1029 /* Solves the special case of the Diophantine equation:
1030 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1032 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1033 number of iterations that loops X and Y run. The overlaps will be
1034 constructed as evolutions in dimension DIM. */
1037 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
1038 tree
*overlaps_a
, tree
*overlaps_b
,
1039 tree
*last_conflicts
, int dim
)
1041 if (((step_a
> 0 && step_b
> 0)
1042 || (step_a
< 0 && step_b
< 0)))
1044 int step_overlaps_a
, step_overlaps_b
;
1045 int gcd_steps_a_b
, last_conflict
, tau2
;
1047 gcd_steps_a_b
= gcd (step_a
, step_b
);
1048 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
1049 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
1051 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
1052 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
1053 last_conflict
= tau2
;
1055 *overlaps_a
= build_polynomial_chrec
1056 (dim
, integer_zero_node
,
1057 build_int_cst (NULL_TREE
, step_overlaps_a
));
1058 *overlaps_b
= build_polynomial_chrec
1059 (dim
, integer_zero_node
,
1060 build_int_cst (NULL_TREE
, step_overlaps_b
));
1061 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
1066 *overlaps_a
= integer_zero_node
;
1067 *overlaps_b
= integer_zero_node
;
1068 *last_conflicts
= integer_zero_node
;
1073 /* Solves the special case of a Diophantine equation where CHREC_A is
1074 an affine bivariate function, and CHREC_B is an affine univariate
1075 function. For example,
1077 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1079 has the following overlapping functions:
1081 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1082 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1083 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1085 FORNOW: This is a specialized implementation for a case occurring in
1086 a common benchmark. Implement the general algorithm. */
1089 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
1090 tree
*overlaps_a
, tree
*overlaps_b
,
1091 tree
*last_conflicts
)
1093 bool xz_p
, yz_p
, xyz_p
;
1094 int step_x
, step_y
, step_z
;
1095 int niter_x
, niter_y
, niter_z
, niter
;
1096 tree numiter_x
, numiter_y
, numiter_z
;
1097 tree overlaps_a_xz
, overlaps_b_xz
, last_conflicts_xz
;
1098 tree overlaps_a_yz
, overlaps_b_yz
, last_conflicts_yz
;
1099 tree overlaps_a_xyz
, overlaps_b_xyz
, last_conflicts_xyz
;
1101 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
1102 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
1103 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
1105 numiter_x
= number_of_iterations_in_loop
1106 (current_loops
->parray
[CHREC_VARIABLE (CHREC_LEFT (chrec_a
))]);
1107 numiter_y
= number_of_iterations_in_loop
1108 (current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]);
1109 numiter_z
= number_of_iterations_in_loop
1110 (current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]);
1112 if (TREE_CODE (numiter_x
) != INTEGER_CST
)
1113 numiter_x
= current_loops
->parray
[CHREC_VARIABLE (CHREC_LEFT (chrec_a
))]
1114 ->estimated_nb_iterations
;
1115 if (TREE_CODE (numiter_y
) != INTEGER_CST
)
1116 numiter_y
= current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]
1117 ->estimated_nb_iterations
;
1118 if (TREE_CODE (numiter_z
) != INTEGER_CST
)
1119 numiter_z
= current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]
1120 ->estimated_nb_iterations
;
1122 if (chrec_contains_undetermined (numiter_x
)
1123 || chrec_contains_undetermined (numiter_y
)
1124 || chrec_contains_undetermined (numiter_z
)
1125 || TREE_CODE (numiter_x
) != INTEGER_CST
1126 || TREE_CODE (numiter_y
) != INTEGER_CST
1127 || TREE_CODE (numiter_z
) != INTEGER_CST
)
1129 *overlaps_a
= chrec_dont_know
;
1130 *overlaps_b
= chrec_dont_know
;
1131 *last_conflicts
= chrec_dont_know
;
1135 niter_x
= int_cst_value (numiter_x
);
1136 niter_y
= int_cst_value (numiter_y
);
1137 niter_z
= int_cst_value (numiter_z
);
1139 niter
= MIN (niter_x
, niter_z
);
1140 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
1143 &last_conflicts_xz
, 1);
1144 niter
= MIN (niter_y
, niter_z
);
1145 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
1148 &last_conflicts_yz
, 2);
1149 niter
= MIN (niter_x
, niter_z
);
1150 niter
= MIN (niter_y
, niter
);
1151 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
1154 &last_conflicts_xyz
, 3);
1156 xz_p
= !integer_zerop (last_conflicts_xz
);
1157 yz_p
= !integer_zerop (last_conflicts_yz
);
1158 xyz_p
= !integer_zerop (last_conflicts_xyz
);
1160 if (xz_p
|| yz_p
|| xyz_p
)
1162 *overlaps_a
= make_tree_vec (2);
1163 TREE_VEC_ELT (*overlaps_a
, 0) = integer_zero_node
;
1164 TREE_VEC_ELT (*overlaps_a
, 1) = integer_zero_node
;
1165 *overlaps_b
= integer_zero_node
;
1168 TREE_VEC_ELT (*overlaps_a
, 0) =
1169 chrec_fold_plus (integer_type_node
, TREE_VEC_ELT (*overlaps_a
, 0),
1172 chrec_fold_plus (integer_type_node
, *overlaps_b
, overlaps_b_xz
);
1173 *last_conflicts
= last_conflicts_xz
;
1177 TREE_VEC_ELT (*overlaps_a
, 1) =
1178 chrec_fold_plus (integer_type_node
, TREE_VEC_ELT (*overlaps_a
, 1),
1181 chrec_fold_plus (integer_type_node
, *overlaps_b
, overlaps_b_yz
);
1182 *last_conflicts
= last_conflicts_yz
;
1186 TREE_VEC_ELT (*overlaps_a
, 0) =
1187 chrec_fold_plus (integer_type_node
, TREE_VEC_ELT (*overlaps_a
, 0),
1189 TREE_VEC_ELT (*overlaps_a
, 1) =
1190 chrec_fold_plus (integer_type_node
, TREE_VEC_ELT (*overlaps_a
, 1),
1193 chrec_fold_plus (integer_type_node
, *overlaps_b
, overlaps_b_xyz
);
1194 *last_conflicts
= last_conflicts_xyz
;
1199 *overlaps_a
= integer_zero_node
;
1200 *overlaps_b
= integer_zero_node
;
1201 *last_conflicts
= integer_zero_node
;
1205 /* Determines the overlapping elements due to accesses CHREC_A and
1206 CHREC_B, that are affine functions. This is a part of the
1207 subscript analyzer. */
1210 analyze_subscript_affine_affine (tree chrec_a
,
1214 tree
*last_conflicts
)
1216 unsigned nb_vars_a
, nb_vars_b
, dim
;
1217 int init_a
, init_b
, gamma
, gcd_alpha_beta
;
1219 lambda_matrix A
, U
, S
;
1221 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1222 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
1224 /* For determining the initial intersection, we have to solve a
1225 Diophantine equation. This is the most time consuming part.
1227 For answering to the question: "Is there a dependence?" we have
1228 to prove that there exists a solution to the Diophantine
1229 equation, and that the solution is in the iteration domain,
1230 i.e. the solution is positive or zero, and that the solution
1231 happens before the upper bound loop.nb_iterations. Otherwise
1232 there is no dependence. This function outputs a description of
1233 the iterations that hold the intersections. */
1236 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
1237 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
1239 dim
= nb_vars_a
+ nb_vars_b
;
1240 U
= lambda_matrix_new (dim
, dim
);
1241 A
= lambda_matrix_new (dim
, 1);
1242 S
= lambda_matrix_new (dim
, 1);
1244 init_a
= initialize_matrix_A (A
, chrec_a
, 0, 1);
1245 init_b
= initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1);
1246 gamma
= init_b
- init_a
;
1248 /* Don't do all the hard work of solving the Diophantine equation
1249 when we already know the solution: for example,
1252 | gamma = 3 - 3 = 0.
1253 Then the first overlap occurs during the first iterations:
1254 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
1258 if (nb_vars_a
== 1 && nb_vars_b
== 1)
1261 int niter
, niter_a
, niter_b
;
1262 tree numiter_a
, numiter_b
;
1264 numiter_a
= number_of_iterations_in_loop
1265 (current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]);
1266 numiter_b
= number_of_iterations_in_loop
1267 (current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]);
1269 if (TREE_CODE (numiter_a
) != INTEGER_CST
)
1270 numiter_a
= current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]
1271 ->estimated_nb_iterations
;
1272 if (TREE_CODE (numiter_b
) != INTEGER_CST
)
1273 numiter_b
= current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]
1274 ->estimated_nb_iterations
;
1275 if (chrec_contains_undetermined (numiter_a
)
1276 || chrec_contains_undetermined (numiter_b
)
1277 || TREE_CODE (numiter_a
) != INTEGER_CST
1278 || TREE_CODE (numiter_b
) != INTEGER_CST
)
1280 *overlaps_a
= chrec_dont_know
;
1281 *overlaps_b
= chrec_dont_know
;
1282 *last_conflicts
= chrec_dont_know
;
1286 niter_a
= int_cst_value (numiter_a
);
1287 niter_b
= int_cst_value (numiter_b
);
1288 niter
= MIN (niter_a
, niter_b
);
1290 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
1291 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
1293 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
1294 overlaps_a
, overlaps_b
,
1298 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
1299 compute_overlap_steps_for_affine_1_2
1300 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
1302 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
1303 compute_overlap_steps_for_affine_1_2
1304 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
1308 *overlaps_a
= chrec_dont_know
;
1309 *overlaps_b
= chrec_dont_know
;
1310 *last_conflicts
= chrec_dont_know
;
1316 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
1321 lambda_matrix_row_negate (U
, dim
, 0);
1323 gcd_alpha_beta
= S
[0][0];
1325 /* The classic "gcd-test". */
1326 if (!int_divides_p (gcd_alpha_beta
, gamma
))
1328 /* The "gcd-test" has determined that there is no integer
1329 solution, i.e. there is no dependence. */
1330 *overlaps_a
= chrec_known
;
1331 *overlaps_b
= chrec_known
;
1332 *last_conflicts
= integer_zero_node
;
1335 /* Both access functions are univariate. This includes SIV and MIV cases. */
1336 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
1338 /* Both functions should have the same evolution sign. */
1339 if (((A
[0][0] > 0 && -A
[1][0] > 0)
1340 || (A
[0][0] < 0 && -A
[1][0] < 0)))
1342 /* The solutions are given by:
1344 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
1347 For a given integer t. Using the following variables,
1349 | i0 = u11 * gamma / gcd_alpha_beta
1350 | j0 = u12 * gamma / gcd_alpha_beta
1357 | y0 = j0 + j1 * t. */
1361 /* X0 and Y0 are the first iterations for which there is a
1362 dependence. X0, Y0 are two solutions of the Diophantine
1363 equation: chrec_a (X0) = chrec_b (Y0). */
1365 int niter
, niter_a
, niter_b
;
1366 tree numiter_a
, numiter_b
;
1368 numiter_a
= number_of_iterations_in_loop
1369 (current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]);
1370 numiter_b
= number_of_iterations_in_loop
1371 (current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]);
1373 if (TREE_CODE (numiter_a
) != INTEGER_CST
)
1374 numiter_a
= current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]
1375 ->estimated_nb_iterations
;
1376 if (TREE_CODE (numiter_b
) != INTEGER_CST
)
1377 numiter_b
= current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]
1378 ->estimated_nb_iterations
;
1379 if (chrec_contains_undetermined (numiter_a
)
1380 || chrec_contains_undetermined (numiter_b
)
1381 || TREE_CODE (numiter_a
) != INTEGER_CST
1382 || TREE_CODE (numiter_b
) != INTEGER_CST
)
1384 *overlaps_a
= chrec_dont_know
;
1385 *overlaps_b
= chrec_dont_know
;
1386 *last_conflicts
= chrec_dont_know
;
1390 niter_a
= int_cst_value (numiter_a
);
1391 niter_b
= int_cst_value (numiter_b
);
1392 niter
= MIN (niter_a
, niter_b
);
1394 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
1395 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
1399 if ((i1
== 0 && i0
< 0)
1400 || (j1
== 0 && j0
< 0))
1402 /* There is no solution.
1403 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
1404 falls in here, but for the moment we don't look at the
1405 upper bound of the iteration domain. */
1406 *overlaps_a
= chrec_known
;
1407 *overlaps_b
= chrec_known
;
1408 *last_conflicts
= integer_zero_node
;
1415 tau1
= CEIL (-i0
, i1
);
1416 tau2
= FLOOR_DIV (niter
- i0
, i1
);
1420 int last_conflict
, min_multiple
;
1421 tau1
= MAX (tau1
, CEIL (-j0
, j1
));
1422 tau2
= MIN (tau2
, FLOOR_DIV (niter
- j0
, j1
));
1424 x0
= i1
* tau1
+ i0
;
1425 y0
= j1
* tau1
+ j0
;
1427 /* At this point (x0, y0) is one of the
1428 solutions to the Diophantine equation. The
1429 next step has to compute the smallest
1430 positive solution: the first conflicts. */
1431 min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
1432 x0
-= i1
* min_multiple
;
1433 y0
-= j1
* min_multiple
;
1435 tau1
= (x0
- i0
)/i1
;
1436 last_conflict
= tau2
- tau1
;
1438 *overlaps_a
= build_polynomial_chrec
1440 build_int_cst (NULL_TREE
, x0
),
1441 build_int_cst (NULL_TREE
, i1
));
1442 *overlaps_b
= build_polynomial_chrec
1444 build_int_cst (NULL_TREE
, y0
),
1445 build_int_cst (NULL_TREE
, j1
));
1446 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
1450 /* FIXME: For the moment, the upper bound of the
1451 iteration domain for j is not checked. */
1452 *overlaps_a
= chrec_dont_know
;
1453 *overlaps_b
= chrec_dont_know
;
1454 *last_conflicts
= chrec_dont_know
;
1460 /* FIXME: For the moment, the upper bound of the
1461 iteration domain for i is not checked. */
1462 *overlaps_a
= chrec_dont_know
;
1463 *overlaps_b
= chrec_dont_know
;
1464 *last_conflicts
= chrec_dont_know
;
1470 *overlaps_a
= chrec_dont_know
;
1471 *overlaps_b
= chrec_dont_know
;
1472 *last_conflicts
= chrec_dont_know
;
1478 *overlaps_a
= chrec_dont_know
;
1479 *overlaps_b
= chrec_dont_know
;
1480 *last_conflicts
= chrec_dont_know
;
1484 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1486 fprintf (dump_file
, " (overlaps_a = ");
1487 print_generic_expr (dump_file
, *overlaps_a
, 0);
1488 fprintf (dump_file
, ")\n (overlaps_b = ");
1489 print_generic_expr (dump_file
, *overlaps_b
, 0);
1490 fprintf (dump_file
, ")\n");
1493 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1494 fprintf (dump_file
, ")\n");
1497 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
1498 *OVERLAPS_B are initialized to the functions that describe the
1499 relation between the elements accessed twice by CHREC_A and
1500 CHREC_B. For k >= 0, the following property is verified:
1502 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1505 analyze_siv_subscript (tree chrec_a
,
1509 tree
*last_conflicts
)
1511 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1512 fprintf (dump_file
, "(analyze_siv_subscript \n");
1514 if (evolution_function_is_constant_p (chrec_a
)
1515 && evolution_function_is_affine_p (chrec_b
))
1516 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
1517 overlaps_a
, overlaps_b
, last_conflicts
);
1519 else if (evolution_function_is_affine_p (chrec_a
)
1520 && evolution_function_is_constant_p (chrec_b
))
1521 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
1522 overlaps_b
, overlaps_a
, last_conflicts
);
1524 else if (evolution_function_is_affine_p (chrec_a
)
1525 && evolution_function_is_affine_p (chrec_b
))
1526 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
1527 overlaps_a
, overlaps_b
, last_conflicts
);
1530 *overlaps_a
= chrec_dont_know
;
1531 *overlaps_b
= chrec_dont_know
;
1532 *last_conflicts
= chrec_dont_know
;
1535 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1536 fprintf (dump_file
, ")\n");
1539 /* Return true when the evolution steps of an affine CHREC divide the
1543 chrec_steps_divide_constant_p (tree chrec
,
1546 switch (TREE_CODE (chrec
))
1548 case POLYNOMIAL_CHREC
:
1549 return (tree_fold_divides_p (integer_type_node
, CHREC_RIGHT (chrec
), cst
)
1550 && chrec_steps_divide_constant_p (CHREC_LEFT (chrec
), cst
));
1553 /* On the initial condition, return true. */
1558 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
1559 *OVERLAPS_B are initialized to the functions that describe the
1560 relation between the elements accessed twice by CHREC_A and
1561 CHREC_B. For k >= 0, the following property is verified:
1563 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1566 analyze_miv_subscript (tree chrec_a
,
1570 tree
*last_conflicts
)
1572 /* FIXME: This is a MIV subscript, not yet handled.
1573 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
1576 In the SIV test we had to solve a Diophantine equation with two
1577 variables. In the MIV case we have to solve a Diophantine
1578 equation with 2*n variables (if the subscript uses n IVs).
1582 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1583 fprintf (dump_file
, "(analyze_miv_subscript \n");
1585 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
1587 if (chrec_zerop (difference
))
1589 /* Access functions are the same: all the elements are accessed
1590 in the same order. */
1591 *overlaps_a
= integer_zero_node
;
1592 *overlaps_b
= integer_zero_node
;
1593 *last_conflicts
= number_of_iterations_in_loop
1594 (current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]);
1597 else if (evolution_function_is_constant_p (difference
)
1598 /* For the moment, the following is verified:
1599 evolution_function_is_affine_multivariate_p (chrec_a) */
1600 && !chrec_steps_divide_constant_p (chrec_a
, difference
))
1602 /* testsuite/.../ssa-chrec-33.c
1603 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
1605 The difference is 1, and the evolution steps are equal to 2,
1606 consequently there are no overlapping elements. */
1607 *overlaps_a
= chrec_known
;
1608 *overlaps_b
= chrec_known
;
1609 *last_conflicts
= integer_zero_node
;
1612 else if (evolution_function_is_affine_multivariate_p (chrec_a
)
1613 && evolution_function_is_affine_multivariate_p (chrec_b
))
1615 /* testsuite/.../ssa-chrec-35.c
1616 {0, +, 1}_2 vs. {0, +, 1}_3
1617 the overlapping elements are respectively located at iterations:
1618 {0, +, 1}_x and {0, +, 1}_x,
1619 in other words, we have the equality:
1620 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
1623 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
1624 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
1626 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
1627 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
1629 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
1630 overlaps_a
, overlaps_b
, last_conflicts
);
1635 /* When the analysis is too difficult, answer "don't know". */
1636 *overlaps_a
= chrec_dont_know
;
1637 *overlaps_b
= chrec_dont_know
;
1638 *last_conflicts
= chrec_dont_know
;
1641 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1642 fprintf (dump_file
, ")\n");
1645 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
1646 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
1647 two functions that describe the iterations that contain conflicting
1650 Remark: For an integer k >= 0, the following equality is true:
1652 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
1656 analyze_overlapping_iterations (tree chrec_a
,
1658 tree
*overlap_iterations_a
,
1659 tree
*overlap_iterations_b
,
1660 tree
*last_conflicts
)
1662 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1664 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
1665 fprintf (dump_file
, " (chrec_a = ");
1666 print_generic_expr (dump_file
, chrec_a
, 0);
1667 fprintf (dump_file
, ")\n chrec_b = ");
1668 print_generic_expr (dump_file
, chrec_b
, 0);
1669 fprintf (dump_file
, ")\n");
1672 if (chrec_a
== NULL_TREE
1673 || chrec_b
== NULL_TREE
1674 || chrec_contains_undetermined (chrec_a
)
1675 || chrec_contains_undetermined (chrec_b
)
1676 || chrec_contains_symbols (chrec_a
)
1677 || chrec_contains_symbols (chrec_b
))
1679 *overlap_iterations_a
= chrec_dont_know
;
1680 *overlap_iterations_b
= chrec_dont_know
;
1683 else if (ziv_subscript_p (chrec_a
, chrec_b
))
1684 analyze_ziv_subscript (chrec_a
, chrec_b
,
1685 overlap_iterations_a
, overlap_iterations_b
,
1688 else if (siv_subscript_p (chrec_a
, chrec_b
))
1689 analyze_siv_subscript (chrec_a
, chrec_b
,
1690 overlap_iterations_a
, overlap_iterations_b
,
1694 analyze_miv_subscript (chrec_a
, chrec_b
,
1695 overlap_iterations_a
, overlap_iterations_b
,
1698 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1700 fprintf (dump_file
, " (overlap_iterations_a = ");
1701 print_generic_expr (dump_file
, *overlap_iterations_a
, 0);
1702 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
1703 print_generic_expr (dump_file
, *overlap_iterations_b
, 0);
1704 fprintf (dump_file
, ")\n");
1710 /* This section contains the affine functions dependences detector. */
1712 /* Computes the conflicting iterations, and initialize DDR. */
1715 subscript_dependence_tester (struct data_dependence_relation
*ddr
)
1718 struct data_reference
*dra
= DDR_A (ddr
);
1719 struct data_reference
*drb
= DDR_B (ddr
);
1720 tree last_conflicts
;
1722 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1723 fprintf (dump_file
, "(subscript_dependence_tester \n");
1725 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1727 tree overlaps_a
, overlaps_b
;
1728 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
1730 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
1731 DR_ACCESS_FN (drb
, i
),
1732 &overlaps_a
, &overlaps_b
,
1735 if (chrec_contains_undetermined (overlaps_a
)
1736 || chrec_contains_undetermined (overlaps_b
))
1738 finalize_ddr_dependent (ddr
, chrec_dont_know
);
1742 else if (overlaps_a
== chrec_known
1743 || overlaps_b
== chrec_known
)
1745 finalize_ddr_dependent (ddr
, chrec_known
);
1751 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
1752 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
1753 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
1757 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1758 fprintf (dump_file
, ")\n");
1761 /* Compute the classic per loop distance vector.
1763 DDR is the data dependence relation to build a vector from.
1764 NB_LOOPS is the total number of loops we are considering.
1765 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
1767 Return FALSE if the dependence relation is outside of the loop nest
1768 starting at FIRST_LOOP_DEPTH.
1769 Return TRUE otherwise. */
1772 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
1773 int nb_loops
, int first_loop_depth
)
1776 lambda_vector dist_v
, init_v
;
1778 dist_v
= lambda_vector_new (nb_loops
);
1779 init_v
= lambda_vector_new (nb_loops
);
1780 lambda_vector_clear (dist_v
, nb_loops
);
1781 lambda_vector_clear (init_v
, nb_loops
);
1783 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
1786 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1788 tree access_fn_a
, access_fn_b
;
1789 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
1791 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
1793 non_affine_dependence_relation (ddr
);
1797 access_fn_a
= DR_ACCESS_FN (DDR_A (ddr
), i
);
1798 access_fn_b
= DR_ACCESS_FN (DDR_B (ddr
), i
);
1800 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
1801 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
1803 int dist
, loop_nb
, loop_depth
;
1804 int loop_nb_a
= CHREC_VARIABLE (access_fn_a
);
1805 int loop_nb_b
= CHREC_VARIABLE (access_fn_b
);
1806 struct loop
*loop_a
= current_loops
->parray
[loop_nb_a
];
1807 struct loop
*loop_b
= current_loops
->parray
[loop_nb_b
];
1809 /* If the loop for either variable is at a lower depth than
1810 the first_loop's depth, then we can't possibly have a
1811 dependency at this level of the loop. */
1813 if (loop_a
->depth
< first_loop_depth
1814 || loop_b
->depth
< first_loop_depth
)
1817 if (loop_nb_a
!= loop_nb_b
1818 && !flow_loop_nested_p (loop_a
, loop_b
)
1819 && !flow_loop_nested_p (loop_b
, loop_a
))
1821 /* Example: when there are two consecutive loops,
1830 the dependence relation cannot be captured by the
1831 distance abstraction. */
1832 non_affine_dependence_relation (ddr
);
1836 /* The dependence is carried by the outermost loop. Example:
1843 In this case, the dependence is carried by loop_1. */
1844 loop_nb
= loop_nb_a
< loop_nb_b
? loop_nb_a
: loop_nb_b
;
1845 loop_depth
= current_loops
->parray
[loop_nb
]->depth
- first_loop_depth
;
1847 /* If the loop number is still greater than the number of
1848 loops we've been asked to analyze, or negative,
1849 something is borked. */
1850 gcc_assert (loop_depth
>= 0);
1851 gcc_assert (loop_depth
< nb_loops
);
1852 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
1854 non_affine_dependence_relation (ddr
);
1858 dist
= int_cst_value (SUB_DISTANCE (subscript
));
1860 /* This is the subscript coupling test.
1865 There is no dependence. */
1866 if (init_v
[loop_depth
] != 0
1867 && dist_v
[loop_depth
] != dist
)
1869 finalize_ddr_dependent (ddr
, chrec_known
);
1873 dist_v
[loop_depth
] = dist
;
1874 init_v
[loop_depth
] = 1;
1878 /* There is a distance of 1 on all the outer loops:
1880 Example: there is a dependence of distance 1 on loop_1 for the array A.
1886 struct loop
*lca
, *loop_a
, *loop_b
;
1887 struct data_reference
*a
= DDR_A (ddr
);
1888 struct data_reference
*b
= DDR_B (ddr
);
1890 loop_a
= loop_containing_stmt (DR_STMT (a
));
1891 loop_b
= loop_containing_stmt (DR_STMT (b
));
1893 /* Get the common ancestor loop. */
1894 lca
= find_common_loop (loop_a
, loop_b
);
1896 lca_depth
= lca
->depth
;
1897 lca_depth
-= first_loop_depth
;
1898 gcc_assert (lca_depth
>= 0);
1899 gcc_assert (lca_depth
< nb_loops
);
1901 /* For each outer loop where init_v is not set, the accesses are
1902 in dependence of distance 1 in the loop. */
1905 && init_v
[lca_depth
] == 0)
1906 dist_v
[lca_depth
] = 1;
1912 lca_depth
= lca
->depth
- first_loop_depth
;
1913 while (lca
->depth
!= 0)
1915 /* If we're considering just a sub-nest, then don't record
1916 any information on the outer loops. */
1920 gcc_assert (lca_depth
< nb_loops
);
1922 if (init_v
[lca_depth
] == 0)
1923 dist_v
[lca_depth
] = 1;
1925 lca_depth
= lca
->depth
- first_loop_depth
;
1931 DDR_DIST_VECT (ddr
) = dist_v
;
1932 DDR_SIZE_VECT (ddr
) = nb_loops
;
1936 /* Compute the classic per loop direction vector.
1938 DDR is the data dependence relation to build a vector from.
1939 NB_LOOPS is the total number of loops we are considering.
1940 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
1942 Return FALSE if the dependence relation is outside of the loop nest
1943 at FIRST_LOOP_DEPTH.
1944 Return TRUE otherwise. */
1947 build_classic_dir_vector (struct data_dependence_relation
*ddr
,
1948 int nb_loops
, int first_loop_depth
)
1951 lambda_vector dir_v
, init_v
;
1953 dir_v
= lambda_vector_new (nb_loops
);
1954 init_v
= lambda_vector_new (nb_loops
);
1955 lambda_vector_clear (dir_v
, nb_loops
);
1956 lambda_vector_clear (init_v
, nb_loops
);
1958 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
1961 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1963 tree access_fn_a
, access_fn_b
;
1964 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
1966 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
1968 non_affine_dependence_relation (ddr
);
1972 access_fn_a
= DR_ACCESS_FN (DDR_A (ddr
), i
);
1973 access_fn_b
= DR_ACCESS_FN (DDR_B (ddr
), i
);
1974 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
1975 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
1977 int dist
, loop_nb
, loop_depth
;
1978 enum data_dependence_direction dir
= dir_star
;
1979 int loop_nb_a
= CHREC_VARIABLE (access_fn_a
);
1980 int loop_nb_b
= CHREC_VARIABLE (access_fn_b
);
1981 struct loop
*loop_a
= current_loops
->parray
[loop_nb_a
];
1982 struct loop
*loop_b
= current_loops
->parray
[loop_nb_b
];
1984 /* If the loop for either variable is at a lower depth than
1985 the first_loop's depth, then we can't possibly have a
1986 dependency at this level of the loop. */
1988 if (loop_a
->depth
< first_loop_depth
1989 || loop_b
->depth
< first_loop_depth
)
1992 if (loop_nb_a
!= loop_nb_b
1993 && !flow_loop_nested_p (loop_a
, loop_b
)
1994 && !flow_loop_nested_p (loop_b
, loop_a
))
1996 /* Example: when there are two consecutive loops,
2005 the dependence relation cannot be captured by the
2006 distance abstraction. */
2007 non_affine_dependence_relation (ddr
);
2011 /* The dependence is carried by the outermost loop. Example:
2018 In this case, the dependence is carried by loop_1. */
2019 loop_nb
= loop_nb_a
< loop_nb_b
? loop_nb_a
: loop_nb_b
;
2020 loop_depth
= current_loops
->parray
[loop_nb
]->depth
- first_loop_depth
;
2022 /* If the loop number is still greater than the number of
2023 loops we've been asked to analyze, or negative,
2024 something is borked. */
2025 gcc_assert (loop_depth
>= 0);
2026 gcc_assert (loop_depth
< nb_loops
);
2028 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2030 non_affine_dependence_relation (ddr
);
2034 dist
= int_cst_value (SUB_DISTANCE (subscript
));
2043 /* This is the subscript coupling test.
2048 There is no dependence. */
2049 if (init_v
[loop_depth
] != 0
2051 && (enum data_dependence_direction
) dir_v
[loop_depth
] != dir
2052 && (enum data_dependence_direction
) dir_v
[loop_depth
] != dir_star
)
2054 finalize_ddr_dependent (ddr
, chrec_known
);
2058 dir_v
[loop_depth
] = dir
;
2059 init_v
[loop_depth
] = 1;
2063 /* There is a distance of 1 on all the outer loops:
2065 Example: there is a dependence of distance 1 on loop_1 for the array A.
2071 struct loop
*lca
, *loop_a
, *loop_b
;
2072 struct data_reference
*a
= DDR_A (ddr
);
2073 struct data_reference
*b
= DDR_B (ddr
);
2075 loop_a
= loop_containing_stmt (DR_STMT (a
));
2076 loop_b
= loop_containing_stmt (DR_STMT (b
));
2078 /* Get the common ancestor loop. */
2079 lca
= find_common_loop (loop_a
, loop_b
);
2080 lca_depth
= lca
->depth
- first_loop_depth
;
2082 gcc_assert (lca_depth
>= 0);
2083 gcc_assert (lca_depth
< nb_loops
);
2085 /* For each outer loop where init_v is not set, the accesses are
2086 in dependence of distance 1 in the loop. */
2089 && init_v
[lca_depth
] == 0)
2090 dir_v
[lca_depth
] = dir_positive
;
2095 lca_depth
= lca
->depth
- first_loop_depth
;
2096 while (lca
->depth
!= 0)
2098 /* If we're considering just a sub-nest, then don't record
2099 any information on the outer loops. */
2103 gcc_assert (lca_depth
< nb_loops
);
2105 if (init_v
[lca_depth
] == 0)
2106 dir_v
[lca_depth
] = dir_positive
;
2108 lca_depth
= lca
->depth
- first_loop_depth
;
2114 DDR_DIR_VECT (ddr
) = dir_v
;
2115 DDR_SIZE_VECT (ddr
) = nb_loops
;
2119 /* Returns true when all the access functions of A are affine or
2123 access_functions_are_affine_or_constant_p (struct data_reference
*a
)
2126 VEC(tree
,heap
) **fns
= &DR_ACCESS_FNS (a
);
2129 for (i
= 0; VEC_iterate (tree
, *fns
, i
, t
); i
++)
2130 if (!evolution_function_is_constant_p (t
)
2131 && !evolution_function_is_affine_multivariate_p (t
))
2137 /* This computes the affine dependence relation between A and B.
2138 CHREC_KNOWN is used for representing the independence between two
2139 accesses, while CHREC_DONT_KNOW is used for representing the unknown
2142 Note that it is possible to stop the computation of the dependence
2143 relation the first time we detect a CHREC_KNOWN element for a given
2147 compute_affine_dependence (struct data_dependence_relation
*ddr
)
2149 struct data_reference
*dra
= DDR_A (ddr
);
2150 struct data_reference
*drb
= DDR_B (ddr
);
2152 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2154 fprintf (dump_file
, "(compute_affine_dependence\n");
2155 fprintf (dump_file
, " (stmt_a = \n");
2156 print_generic_expr (dump_file
, DR_STMT (dra
), 0);
2157 fprintf (dump_file
, ")\n (stmt_b = \n");
2158 print_generic_expr (dump_file
, DR_STMT (drb
), 0);
2159 fprintf (dump_file
, ")\n");
2162 /* Analyze only when the dependence relation is not yet known. */
2163 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
2165 if (access_functions_are_affine_or_constant_p (dra
)
2166 && access_functions_are_affine_or_constant_p (drb
))
2167 subscript_dependence_tester (ddr
);
2169 /* As a last case, if the dependence cannot be determined, or if
2170 the dependence is considered too difficult to determine, answer
2173 finalize_ddr_dependent (ddr
, chrec_dont_know
);
2176 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2177 fprintf (dump_file
, ")\n");
2180 /* This computes the dependence relation for the same data
2181 reference into DDR. */
2184 compute_self_dependence (struct data_dependence_relation
*ddr
)
2188 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2190 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
2192 /* The accessed index overlaps for each iteration. */
2193 SUB_CONFLICTS_IN_A (subscript
) = integer_zero_node
;
2194 SUB_CONFLICTS_IN_B (subscript
) = integer_zero_node
;
2195 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
2200 typedef struct data_dependence_relation
*ddr_p
;
2202 DEF_VEC_ALLOC_P(ddr_p
,heap
);
2204 /* Compute a subset of the data dependence relation graph. Don't
2205 compute read-read relations, and avoid the computation of the
2206 opposite relation, i.e. when AB has been computed, don't compute BA.
2207 DATAREFS contains a list of data references, and the result is set
2208 in DEPENDENCE_RELATIONS. */
2211 compute_all_dependences (varray_type datarefs
,
2212 VEC(ddr_p
,heap
) **dependence_relations
)
2214 unsigned int i
, j
, N
;
2216 N
= VARRAY_ACTIVE_SIZE (datarefs
);
2218 /* Note that we specifically skip i == j because it's a self dependence, and
2219 use compute_self_dependence below. */
2221 for (i
= 0; i
< N
; i
++)
2222 for (j
= i
+ 1; j
< N
; j
++)
2224 struct data_reference
*a
, *b
;
2225 struct data_dependence_relation
*ddr
;
2227 a
= VARRAY_GENERIC_PTR (datarefs
, i
);
2228 b
= VARRAY_GENERIC_PTR (datarefs
, j
);
2229 ddr
= initialize_data_dependence_relation (a
, b
);
2231 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
2232 compute_affine_dependence (ddr
);
2233 compute_subscript_distance (ddr
);
2236 /* Compute self dependence relation of each dataref to itself. */
2238 for (i
= 0; i
< N
; i
++)
2240 struct data_reference
*a
, *b
;
2241 struct data_dependence_relation
*ddr
;
2243 a
= VARRAY_GENERIC_PTR (datarefs
, i
);
2244 b
= VARRAY_GENERIC_PTR (datarefs
, i
);
2245 ddr
= initialize_data_dependence_relation (a
, b
);
2247 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
2248 compute_self_dependence (ddr
);
2249 compute_subscript_distance (ddr
);
2253 /* Search the data references in LOOP, and record the information into
2254 DATAREFS. Returns chrec_dont_know when failing to analyze a
2255 difficult case, returns NULL_TREE otherwise.
2257 TODO: This function should be made smarter so that it can handle address
2258 arithmetic as if they were array accesses, etc. */
2261 find_data_references_in_loop (struct loop
*loop
, varray_type
*datarefs
)
2263 basic_block bb
, *bbs
;
2265 block_stmt_iterator bsi
;
2267 bbs
= get_loop_body (loop
);
2269 for (i
= 0; i
< loop
->num_nodes
; i
++)
2273 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
2275 tree stmt
= bsi_stmt (bsi
);
2277 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
2278 Calls have side-effects, except those to const or pure
2280 if ((TREE_CODE (stmt
) == CALL_EXPR
2281 && !(call_expr_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
2282 || (TREE_CODE (stmt
) == ASM_EXPR
2283 && ASM_VOLATILE_P (stmt
)))
2284 goto insert_dont_know_node
;
2286 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
2289 switch (TREE_CODE (stmt
))
2292 if (TREE_CODE (TREE_OPERAND (stmt
, 0)) == ARRAY_REF
)
2293 VARRAY_PUSH_GENERIC_PTR
2294 (*datarefs
, analyze_array (stmt
, TREE_OPERAND (stmt
, 0),
2297 if (TREE_CODE (TREE_OPERAND (stmt
, 1)) == ARRAY_REF
)
2298 VARRAY_PUSH_GENERIC_PTR
2299 (*datarefs
, analyze_array (stmt
, TREE_OPERAND (stmt
, 1),
2302 if (TREE_CODE (TREE_OPERAND (stmt
, 0)) != ARRAY_REF
2303 && TREE_CODE (TREE_OPERAND (stmt
, 1)) != ARRAY_REF
)
2304 goto insert_dont_know_node
;
2311 bool one_inserted
= false;
2313 for (args
= TREE_OPERAND (stmt
, 1); args
; args
= TREE_CHAIN (args
))
2314 if (TREE_CODE (TREE_VALUE (args
)) == ARRAY_REF
)
2316 VARRAY_PUSH_GENERIC_PTR
2317 (*datarefs
, analyze_array (stmt
, TREE_VALUE (args
), true));
2318 one_inserted
= true;
2322 goto insert_dont_know_node
;
2329 struct data_reference
*res
;
2331 insert_dont_know_node
:;
2332 res
= xmalloc (sizeof (struct data_reference
));
2333 DR_STMT (res
) = NULL_TREE
;
2334 DR_REF (res
) = NULL_TREE
;
2335 DR_ACCESS_FNS (res
) = NULL
;
2336 DR_BASE_NAME (res
) = NULL
;
2337 DR_IS_READ (res
) = false;
2338 VARRAY_PUSH_GENERIC_PTR (*datarefs
, res
);
2341 return chrec_dont_know
;
2345 /* When there are no defs in the loop, the loop is parallel. */
2346 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_VIRTUAL_DEFS
))
2347 loop
->parallel_p
= false;
2350 if (chrec_contains_undetermined (loop
->estimated_nb_iterations
))
2351 compute_estimated_nb_iterations (loop
);
2361 /* This section contains all the entry points. */
2363 /* Given a loop nest LOOP, the following vectors are returned:
2364 *DATAREFS is initialized to all the array elements contained in this loop,
2365 *DEPENDENCE_RELATIONS contains the relations between the data references. */
2368 compute_data_dependences_for_loop (unsigned nb_loops
,
2370 varray_type
*datarefs
,
2371 varray_type
*dependence_relations
)
2374 VEC(ddr_p
,heap
) *allrelations
;
2375 struct data_dependence_relation
*ddr
;
2377 /* If one of the data references is not computable, give up without
2378 spending time to compute other dependences. */
2379 if (find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
2381 struct data_dependence_relation
*ddr
;
2383 /* Insert a single relation into dependence_relations:
2385 ddr
= initialize_data_dependence_relation (NULL
, NULL
);
2386 VARRAY_PUSH_GENERIC_PTR (*dependence_relations
, ddr
);
2387 build_classic_dist_vector (ddr
, nb_loops
, loop
->depth
);
2388 build_classic_dir_vector (ddr
, nb_loops
, loop
->depth
);
2392 allrelations
= NULL
;
2393 compute_all_dependences (*datarefs
, &allrelations
);
2395 for (i
= 0; VEC_iterate (ddr_p
, allrelations
, i
, ddr
); i
++)
2397 if (build_classic_dist_vector (ddr
, nb_loops
, loop
->depth
))
2399 VARRAY_PUSH_GENERIC_PTR (*dependence_relations
, ddr
);
2400 build_classic_dir_vector (ddr
, nb_loops
, loop
->depth
);
2405 /* Entry point (for testing only). Analyze all the data references
2406 and the dependence relations.
2408 The data references are computed first.
2410 A relation on these nodes is represented by a complete graph. Some
2411 of the relations could be of no interest, thus the relations can be
2414 In the following function we compute all the relations. This is
2415 just a first implementation that is here for:
2416 - for showing how to ask for the dependence relations,
2417 - for the debugging the whole dependence graph,
2418 - for the dejagnu testcases and maintenance.
2420 It is possible to ask only for a part of the graph, avoiding to
2421 compute the whole dependence graph. The computed dependences are
2422 stored in a knowledge base (KB) such that later queries don't
2423 recompute the same information. The implementation of this KB is
2424 transparent to the optimizer, and thus the KB can be changed with a
2425 more efficient implementation, or the KB could be disabled. */
2428 analyze_all_data_dependences (struct loops
*loops
)
2431 varray_type datarefs
;
2432 varray_type dependence_relations
;
2433 int nb_data_refs
= 10;
2435 VARRAY_GENERIC_PTR_INIT (datarefs
, nb_data_refs
, "datarefs");
2436 VARRAY_GENERIC_PTR_INIT (dependence_relations
,
2437 nb_data_refs
* nb_data_refs
,
2438 "dependence_relations");
2440 /* Compute DDs on the whole function. */
2441 compute_data_dependences_for_loop (loops
->num
, loops
->parray
[0],
2442 &datarefs
, &dependence_relations
);
2446 dump_data_dependence_relations (dump_file
, dependence_relations
);
2447 fprintf (dump_file
, "\n\n");
2449 if (dump_flags
& TDF_DETAILS
)
2450 dump_dist_dir_vectors (dump_file
, dependence_relations
);
2452 if (dump_flags
& TDF_STATS
)
2454 unsigned nb_top_relations
= 0;
2455 unsigned nb_bot_relations
= 0;
2456 unsigned nb_basename_differ
= 0;
2457 unsigned nb_chrec_relations
= 0;
2459 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (dependence_relations
); i
++)
2461 struct data_dependence_relation
*ddr
;
2462 ddr
= VARRAY_GENERIC_PTR (dependence_relations
, i
);
2464 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
2467 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
2469 struct data_reference
*a
= DDR_A (ddr
);
2470 struct data_reference
*b
= DDR_B (ddr
);
2473 if (DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
)
2474 || (array_base_name_differ_p (a
, b
, &differ_p
) && differ_p
))
2475 nb_basename_differ
++;
2481 nb_chrec_relations
++;
2484 gather_stats_on_scev_database ();
2488 free_dependence_relations (dependence_relations
);
2489 free_data_refs (datarefs
);
2492 /* Free the memory used by a data dependence relation DDR. */
2495 free_dependence_relation (struct data_dependence_relation
*ddr
)
2500 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_SUBSCRIPTS (ddr
))
2501 varray_clear (DDR_SUBSCRIPTS (ddr
));
2505 /* Free the memory used by the data dependence relations from
2506 DEPENDENCE_RELATIONS. */
2509 free_dependence_relations (varray_type dependence_relations
)
2512 if (dependence_relations
== NULL
)
2515 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (dependence_relations
); i
++)
2516 free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations
, i
));
2517 varray_clear (dependence_relations
);
2520 /* Free the memory used by the data references from DATAREFS. */
2523 free_data_refs (varray_type datarefs
)
2527 if (datarefs
== NULL
)
2530 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (datarefs
); i
++)
2532 struct data_reference
*dr
= (struct data_reference
*)
2533 VARRAY_GENERIC_PTR (datarefs
, i
);
2536 VEC_free (tree
, heap
, DR_ACCESS_FNS (dr
));
2540 varray_clear (datarefs
);