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 (build (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
;
924 (build (EXACT_DIV_EXPR
, integer_type_node
,
925 fold (build1 (ABS_EXPR
, integer_type_node
, difference
)),
926 CHREC_RIGHT (chrec_b
)));
927 *last_conflicts
= integer_one_node
;
931 /* When the step does not divides the difference, there are
935 *overlaps_a
= chrec_known
;
936 *overlaps_b
= chrec_known
;
937 *last_conflicts
= integer_zero_node
;
946 chrec_b = {10, +, -1}
948 In this case, chrec_a will not overlap with chrec_b. */
949 *overlaps_a
= chrec_known
;
950 *overlaps_b
= chrec_known
;
951 *last_conflicts
= integer_zero_node
;
958 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
960 *overlaps_a
= chrec_dont_know
;
961 *overlaps_b
= chrec_dont_know
;
962 *last_conflicts
= chrec_dont_know
;
971 chrec_b = {10, +, -1}
973 if (tree_fold_divides_p
974 (integer_type_node
, CHREC_RIGHT (chrec_b
), difference
))
976 *overlaps_a
= integer_zero_node
;
978 (build (EXACT_DIV_EXPR
, integer_type_node
, difference
,
979 CHREC_RIGHT (chrec_b
)));
980 *last_conflicts
= integer_one_node
;
984 /* When the step does not divides the difference, there
988 *overlaps_a
= chrec_known
;
989 *overlaps_b
= chrec_known
;
990 *last_conflicts
= integer_zero_node
;
1000 In this case, chrec_a will not overlap with chrec_b. */
1001 *overlaps_a
= chrec_known
;
1002 *overlaps_b
= chrec_known
;
1003 *last_conflicts
= integer_zero_node
;
1011 /* Helper recursive function for initializing the matrix A. Returns
1012 the initial value of CHREC. */
1015 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
1019 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1020 return int_cst_value (chrec
);
1022 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
1023 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
1026 #define FLOOR_DIV(x,y) ((x) / (y))
1028 /* Solves the special case of the Diophantine equation:
1029 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1031 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1032 number of iterations that loops X and Y run. The overlaps will be
1033 constructed as evolutions in dimension DIM. */
1036 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
1037 tree
*overlaps_a
, tree
*overlaps_b
,
1038 tree
*last_conflicts
, int dim
)
1040 if (((step_a
> 0 && step_b
> 0)
1041 || (step_a
< 0 && step_b
< 0)))
1043 int step_overlaps_a
, step_overlaps_b
;
1044 int gcd_steps_a_b
, last_conflict
, tau2
;
1046 gcd_steps_a_b
= gcd (step_a
, step_b
);
1047 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
1048 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
1050 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
1051 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
1052 last_conflict
= tau2
;
1054 *overlaps_a
= build_polynomial_chrec
1055 (dim
, integer_zero_node
,
1056 build_int_cst (NULL_TREE
, step_overlaps_a
));
1057 *overlaps_b
= build_polynomial_chrec
1058 (dim
, integer_zero_node
,
1059 build_int_cst (NULL_TREE
, step_overlaps_b
));
1060 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
1065 *overlaps_a
= integer_zero_node
;
1066 *overlaps_b
= integer_zero_node
;
1067 *last_conflicts
= integer_zero_node
;
1072 /* Solves the special case of a Diophantine equation where CHREC_A is
1073 an affine bivariate function, and CHREC_B is an affine univariate
1074 function. For example,
1076 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1078 has the following overlapping functions:
1080 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1081 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1082 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1084 FORNOW: This is a specialized implementation for a case occurring in
1085 a common benchmark. Implement the general algorithm. */
1088 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
1089 tree
*overlaps_a
, tree
*overlaps_b
,
1090 tree
*last_conflicts
)
1092 bool xz_p
, yz_p
, xyz_p
;
1093 int step_x
, step_y
, step_z
;
1094 int niter_x
, niter_y
, niter_z
, niter
;
1095 tree numiter_x
, numiter_y
, numiter_z
;
1096 tree overlaps_a_xz
, overlaps_b_xz
, last_conflicts_xz
;
1097 tree overlaps_a_yz
, overlaps_b_yz
, last_conflicts_yz
;
1098 tree overlaps_a_xyz
, overlaps_b_xyz
, last_conflicts_xyz
;
1100 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
1101 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
1102 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
1104 numiter_x
= number_of_iterations_in_loop
1105 (current_loops
->parray
[CHREC_VARIABLE (CHREC_LEFT (chrec_a
))]);
1106 numiter_y
= number_of_iterations_in_loop
1107 (current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]);
1108 numiter_z
= number_of_iterations_in_loop
1109 (current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]);
1111 if (TREE_CODE (numiter_x
) != INTEGER_CST
)
1112 numiter_x
= current_loops
->parray
[CHREC_VARIABLE (CHREC_LEFT (chrec_a
))]
1113 ->estimated_nb_iterations
;
1114 if (TREE_CODE (numiter_y
) != INTEGER_CST
)
1115 numiter_y
= current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]
1116 ->estimated_nb_iterations
;
1117 if (TREE_CODE (numiter_z
) != INTEGER_CST
)
1118 numiter_z
= current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]
1119 ->estimated_nb_iterations
;
1121 if (chrec_contains_undetermined (numiter_x
)
1122 || chrec_contains_undetermined (numiter_y
)
1123 || chrec_contains_undetermined (numiter_z
)
1124 || TREE_CODE (numiter_x
) != INTEGER_CST
1125 || TREE_CODE (numiter_y
) != INTEGER_CST
1126 || TREE_CODE (numiter_z
) != INTEGER_CST
)
1128 *overlaps_a
= chrec_dont_know
;
1129 *overlaps_b
= chrec_dont_know
;
1130 *last_conflicts
= chrec_dont_know
;
1134 niter_x
= int_cst_value (numiter_x
);
1135 niter_y
= int_cst_value (numiter_y
);
1136 niter_z
= int_cst_value (numiter_z
);
1138 niter
= MIN (niter_x
, niter_z
);
1139 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
1142 &last_conflicts_xz
, 1);
1143 niter
= MIN (niter_y
, niter_z
);
1144 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
1147 &last_conflicts_yz
, 2);
1148 niter
= MIN (niter_x
, niter_z
);
1149 niter
= MIN (niter_y
, niter
);
1150 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
1153 &last_conflicts_xyz
, 3);
1155 xz_p
= !integer_zerop (last_conflicts_xz
);
1156 yz_p
= !integer_zerop (last_conflicts_yz
);
1157 xyz_p
= !integer_zerop (last_conflicts_xyz
);
1159 if (xz_p
|| yz_p
|| xyz_p
)
1161 *overlaps_a
= make_tree_vec (2);
1162 TREE_VEC_ELT (*overlaps_a
, 0) = integer_zero_node
;
1163 TREE_VEC_ELT (*overlaps_a
, 1) = integer_zero_node
;
1164 *overlaps_b
= integer_zero_node
;
1167 TREE_VEC_ELT (*overlaps_a
, 0) =
1168 chrec_fold_plus (integer_type_node
, TREE_VEC_ELT (*overlaps_a
, 0),
1171 chrec_fold_plus (integer_type_node
, *overlaps_b
, overlaps_b_xz
);
1172 *last_conflicts
= last_conflicts_xz
;
1176 TREE_VEC_ELT (*overlaps_a
, 1) =
1177 chrec_fold_plus (integer_type_node
, TREE_VEC_ELT (*overlaps_a
, 1),
1180 chrec_fold_plus (integer_type_node
, *overlaps_b
, overlaps_b_yz
);
1181 *last_conflicts
= last_conflicts_yz
;
1185 TREE_VEC_ELT (*overlaps_a
, 0) =
1186 chrec_fold_plus (integer_type_node
, TREE_VEC_ELT (*overlaps_a
, 0),
1188 TREE_VEC_ELT (*overlaps_a
, 1) =
1189 chrec_fold_plus (integer_type_node
, TREE_VEC_ELT (*overlaps_a
, 1),
1192 chrec_fold_plus (integer_type_node
, *overlaps_b
, overlaps_b_xyz
);
1193 *last_conflicts
= last_conflicts_xyz
;
1198 *overlaps_a
= integer_zero_node
;
1199 *overlaps_b
= integer_zero_node
;
1200 *last_conflicts
= integer_zero_node
;
1204 /* Determines the overlapping elements due to accesses CHREC_A and
1205 CHREC_B, that are affine functions. This is a part of the
1206 subscript analyzer. */
1209 analyze_subscript_affine_affine (tree chrec_a
,
1213 tree
*last_conflicts
)
1215 unsigned nb_vars_a
, nb_vars_b
, dim
;
1216 int init_a
, init_b
, gamma
, gcd_alpha_beta
;
1218 lambda_matrix A
, U
, S
;
1220 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1221 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
1223 /* For determining the initial intersection, we have to solve a
1224 Diophantine equation. This is the most time consuming part.
1226 For answering to the question: "Is there a dependence?" we have
1227 to prove that there exists a solution to the Diophantine
1228 equation, and that the solution is in the iteration domain,
1229 i.e. the solution is positive or zero, and that the solution
1230 happens before the upper bound loop.nb_iterations. Otherwise
1231 there is no dependence. This function outputs a description of
1232 the iterations that hold the intersections. */
1235 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
1236 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
1238 dim
= nb_vars_a
+ nb_vars_b
;
1239 U
= lambda_matrix_new (dim
, dim
);
1240 A
= lambda_matrix_new (dim
, 1);
1241 S
= lambda_matrix_new (dim
, 1);
1243 init_a
= initialize_matrix_A (A
, chrec_a
, 0, 1);
1244 init_b
= initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1);
1245 gamma
= init_b
- init_a
;
1247 /* Don't do all the hard work of solving the Diophantine equation
1248 when we already know the solution: for example,
1251 | gamma = 3 - 3 = 0.
1252 Then the first overlap occurs during the first iterations:
1253 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
1257 if (nb_vars_a
== 1 && nb_vars_b
== 1)
1260 int niter
, niter_a
, niter_b
;
1261 tree numiter_a
, numiter_b
;
1263 numiter_a
= number_of_iterations_in_loop
1264 (current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]);
1265 numiter_b
= number_of_iterations_in_loop
1266 (current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]);
1268 if (TREE_CODE (numiter_a
) != INTEGER_CST
)
1269 numiter_a
= current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]
1270 ->estimated_nb_iterations
;
1271 if (TREE_CODE (numiter_b
) != INTEGER_CST
)
1272 numiter_b
= current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]
1273 ->estimated_nb_iterations
;
1274 if (chrec_contains_undetermined (numiter_a
)
1275 || chrec_contains_undetermined (numiter_b
)
1276 || TREE_CODE (numiter_a
) != INTEGER_CST
1277 || TREE_CODE (numiter_b
) != INTEGER_CST
)
1279 *overlaps_a
= chrec_dont_know
;
1280 *overlaps_b
= chrec_dont_know
;
1281 *last_conflicts
= chrec_dont_know
;
1285 niter_a
= int_cst_value (numiter_a
);
1286 niter_b
= int_cst_value (numiter_b
);
1287 niter
= MIN (niter_a
, niter_b
);
1289 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
1290 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
1292 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
1293 overlaps_a
, overlaps_b
,
1297 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
1298 compute_overlap_steps_for_affine_1_2
1299 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
1301 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
1302 compute_overlap_steps_for_affine_1_2
1303 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
1307 *overlaps_a
= chrec_dont_know
;
1308 *overlaps_b
= chrec_dont_know
;
1309 *last_conflicts
= chrec_dont_know
;
1315 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
1320 lambda_matrix_row_negate (U
, dim
, 0);
1322 gcd_alpha_beta
= S
[0][0];
1324 /* The classic "gcd-test". */
1325 if (!int_divides_p (gcd_alpha_beta
, gamma
))
1327 /* The "gcd-test" has determined that there is no integer
1328 solution, i.e. there is no dependence. */
1329 *overlaps_a
= chrec_known
;
1330 *overlaps_b
= chrec_known
;
1331 *last_conflicts
= integer_zero_node
;
1334 /* Both access functions are univariate. This includes SIV and MIV cases. */
1335 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
1337 /* Both functions should have the same evolution sign. */
1338 if (((A
[0][0] > 0 && -A
[1][0] > 0)
1339 || (A
[0][0] < 0 && -A
[1][0] < 0)))
1341 /* The solutions are given by:
1343 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
1346 For a given integer t. Using the following variables,
1348 | i0 = u11 * gamma / gcd_alpha_beta
1349 | j0 = u12 * gamma / gcd_alpha_beta
1356 | y0 = j0 + j1 * t. */
1360 /* X0 and Y0 are the first iterations for which there is a
1361 dependence. X0, Y0 are two solutions of the Diophantine
1362 equation: chrec_a (X0) = chrec_b (Y0). */
1364 int niter
, niter_a
, niter_b
;
1365 tree numiter_a
, numiter_b
;
1367 numiter_a
= number_of_iterations_in_loop
1368 (current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]);
1369 numiter_b
= number_of_iterations_in_loop
1370 (current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]);
1372 if (TREE_CODE (numiter_a
) != INTEGER_CST
)
1373 numiter_a
= current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]
1374 ->estimated_nb_iterations
;
1375 if (TREE_CODE (numiter_b
) != INTEGER_CST
)
1376 numiter_b
= current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]
1377 ->estimated_nb_iterations
;
1378 if (chrec_contains_undetermined (numiter_a
)
1379 || chrec_contains_undetermined (numiter_b
)
1380 || TREE_CODE (numiter_a
) != INTEGER_CST
1381 || TREE_CODE (numiter_b
) != INTEGER_CST
)
1383 *overlaps_a
= chrec_dont_know
;
1384 *overlaps_b
= chrec_dont_know
;
1385 *last_conflicts
= chrec_dont_know
;
1389 niter_a
= int_cst_value (numiter_a
);
1390 niter_b
= int_cst_value (numiter_b
);
1391 niter
= MIN (niter_a
, niter_b
);
1393 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
1394 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
1398 if ((i1
== 0 && i0
< 0)
1399 || (j1
== 0 && j0
< 0))
1401 /* There is no solution.
1402 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
1403 falls in here, but for the moment we don't look at the
1404 upper bound of the iteration domain. */
1405 *overlaps_a
= chrec_known
;
1406 *overlaps_b
= chrec_known
;
1407 *last_conflicts
= integer_zero_node
;
1414 tau1
= CEIL (-i0
, i1
);
1415 tau2
= FLOOR_DIV (niter
- i0
, i1
);
1419 int last_conflict
, min_multiple
;
1420 tau1
= MAX (tau1
, CEIL (-j0
, j1
));
1421 tau2
= MIN (tau2
, FLOOR_DIV (niter
- j0
, j1
));
1423 x0
= i1
* tau1
+ i0
;
1424 y0
= j1
* tau1
+ j0
;
1426 /* At this point (x0, y0) is one of the
1427 solutions to the Diophantine equation. The
1428 next step has to compute the smallest
1429 positive solution: the first conflicts. */
1430 min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
1431 x0
-= i1
* min_multiple
;
1432 y0
-= j1
* min_multiple
;
1434 tau1
= (x0
- i0
)/i1
;
1435 last_conflict
= tau2
- tau1
;
1437 *overlaps_a
= build_polynomial_chrec
1439 build_int_cst (NULL_TREE
, x0
),
1440 build_int_cst (NULL_TREE
, i1
));
1441 *overlaps_b
= build_polynomial_chrec
1443 build_int_cst (NULL_TREE
, y0
),
1444 build_int_cst (NULL_TREE
, j1
));
1445 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
1449 /* FIXME: For the moment, the upper bound of the
1450 iteration domain for j is not checked. */
1451 *overlaps_a
= chrec_dont_know
;
1452 *overlaps_b
= chrec_dont_know
;
1453 *last_conflicts
= chrec_dont_know
;
1459 /* FIXME: For the moment, the upper bound of the
1460 iteration domain for i is not checked. */
1461 *overlaps_a
= chrec_dont_know
;
1462 *overlaps_b
= chrec_dont_know
;
1463 *last_conflicts
= chrec_dont_know
;
1469 *overlaps_a
= chrec_dont_know
;
1470 *overlaps_b
= chrec_dont_know
;
1471 *last_conflicts
= chrec_dont_know
;
1477 *overlaps_a
= chrec_dont_know
;
1478 *overlaps_b
= chrec_dont_know
;
1479 *last_conflicts
= chrec_dont_know
;
1483 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1485 fprintf (dump_file
, " (overlaps_a = ");
1486 print_generic_expr (dump_file
, *overlaps_a
, 0);
1487 fprintf (dump_file
, ")\n (overlaps_b = ");
1488 print_generic_expr (dump_file
, *overlaps_b
, 0);
1489 fprintf (dump_file
, ")\n");
1492 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1493 fprintf (dump_file
, ")\n");
1496 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
1497 *OVERLAPS_B are initialized to the functions that describe the
1498 relation between the elements accessed twice by CHREC_A and
1499 CHREC_B. For k >= 0, the following property is verified:
1501 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1504 analyze_siv_subscript (tree chrec_a
,
1508 tree
*last_conflicts
)
1510 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1511 fprintf (dump_file
, "(analyze_siv_subscript \n");
1513 if (evolution_function_is_constant_p (chrec_a
)
1514 && evolution_function_is_affine_p (chrec_b
))
1515 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
1516 overlaps_a
, overlaps_b
, last_conflicts
);
1518 else if (evolution_function_is_affine_p (chrec_a
)
1519 && evolution_function_is_constant_p (chrec_b
))
1520 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
1521 overlaps_b
, overlaps_a
, last_conflicts
);
1523 else if (evolution_function_is_affine_p (chrec_a
)
1524 && evolution_function_is_affine_p (chrec_b
))
1525 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
1526 overlaps_a
, overlaps_b
, last_conflicts
);
1529 *overlaps_a
= chrec_dont_know
;
1530 *overlaps_b
= chrec_dont_know
;
1531 *last_conflicts
= chrec_dont_know
;
1534 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1535 fprintf (dump_file
, ")\n");
1538 /* Return true when the evolution steps of an affine CHREC divide the
1542 chrec_steps_divide_constant_p (tree chrec
,
1545 switch (TREE_CODE (chrec
))
1547 case POLYNOMIAL_CHREC
:
1548 return (tree_fold_divides_p (integer_type_node
, CHREC_RIGHT (chrec
), cst
)
1549 && chrec_steps_divide_constant_p (CHREC_LEFT (chrec
), cst
));
1552 /* On the initial condition, return true. */
1557 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
1558 *OVERLAPS_B are initialized to the functions that describe the
1559 relation between the elements accessed twice by CHREC_A and
1560 CHREC_B. For k >= 0, the following property is verified:
1562 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1565 analyze_miv_subscript (tree chrec_a
,
1569 tree
*last_conflicts
)
1571 /* FIXME: This is a MIV subscript, not yet handled.
1572 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
1575 In the SIV test we had to solve a Diophantine equation with two
1576 variables. In the MIV case we have to solve a Diophantine
1577 equation with 2*n variables (if the subscript uses n IVs).
1581 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1582 fprintf (dump_file
, "(analyze_miv_subscript \n");
1584 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
1586 if (chrec_zerop (difference
))
1588 /* Access functions are the same: all the elements are accessed
1589 in the same order. */
1590 *overlaps_a
= integer_zero_node
;
1591 *overlaps_b
= integer_zero_node
;
1592 *last_conflicts
= number_of_iterations_in_loop
1593 (current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]);
1596 else if (evolution_function_is_constant_p (difference
)
1597 /* For the moment, the following is verified:
1598 evolution_function_is_affine_multivariate_p (chrec_a) */
1599 && !chrec_steps_divide_constant_p (chrec_a
, difference
))
1601 /* testsuite/.../ssa-chrec-33.c
1602 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
1604 The difference is 1, and the evolution steps are equal to 2,
1605 consequently there are no overlapping elements. */
1606 *overlaps_a
= chrec_known
;
1607 *overlaps_b
= chrec_known
;
1608 *last_conflicts
= integer_zero_node
;
1611 else if (evolution_function_is_affine_multivariate_p (chrec_a
)
1612 && evolution_function_is_affine_multivariate_p (chrec_b
))
1614 /* testsuite/.../ssa-chrec-35.c
1615 {0, +, 1}_2 vs. {0, +, 1}_3
1616 the overlapping elements are respectively located at iterations:
1617 {0, +, 1}_x and {0, +, 1}_x,
1618 in other words, we have the equality:
1619 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
1622 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
1623 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
1625 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
1626 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
1628 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
1629 overlaps_a
, overlaps_b
, last_conflicts
);
1634 /* When the analysis is too difficult, answer "don't know". */
1635 *overlaps_a
= chrec_dont_know
;
1636 *overlaps_b
= chrec_dont_know
;
1637 *last_conflicts
= chrec_dont_know
;
1640 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1641 fprintf (dump_file
, ")\n");
1644 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
1645 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
1646 two functions that describe the iterations that contain conflicting
1649 Remark: For an integer k >= 0, the following equality is true:
1651 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
1655 analyze_overlapping_iterations (tree chrec_a
,
1657 tree
*overlap_iterations_a
,
1658 tree
*overlap_iterations_b
,
1659 tree
*last_conflicts
)
1661 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1663 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
1664 fprintf (dump_file
, " (chrec_a = ");
1665 print_generic_expr (dump_file
, chrec_a
, 0);
1666 fprintf (dump_file
, ")\n chrec_b = ");
1667 print_generic_expr (dump_file
, chrec_b
, 0);
1668 fprintf (dump_file
, ")\n");
1671 if (chrec_a
== NULL_TREE
1672 || chrec_b
== NULL_TREE
1673 || chrec_contains_undetermined (chrec_a
)
1674 || chrec_contains_undetermined (chrec_b
)
1675 || chrec_contains_symbols (chrec_a
)
1676 || chrec_contains_symbols (chrec_b
))
1678 *overlap_iterations_a
= chrec_dont_know
;
1679 *overlap_iterations_b
= chrec_dont_know
;
1682 else if (ziv_subscript_p (chrec_a
, chrec_b
))
1683 analyze_ziv_subscript (chrec_a
, chrec_b
,
1684 overlap_iterations_a
, overlap_iterations_b
,
1687 else if (siv_subscript_p (chrec_a
, chrec_b
))
1688 analyze_siv_subscript (chrec_a
, chrec_b
,
1689 overlap_iterations_a
, overlap_iterations_b
,
1693 analyze_miv_subscript (chrec_a
, chrec_b
,
1694 overlap_iterations_a
, overlap_iterations_b
,
1697 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1699 fprintf (dump_file
, " (overlap_iterations_a = ");
1700 print_generic_expr (dump_file
, *overlap_iterations_a
, 0);
1701 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
1702 print_generic_expr (dump_file
, *overlap_iterations_b
, 0);
1703 fprintf (dump_file
, ")\n");
1709 /* This section contains the affine functions dependences detector. */
1711 /* Computes the conflicting iterations, and initialize DDR. */
1714 subscript_dependence_tester (struct data_dependence_relation
*ddr
)
1717 struct data_reference
*dra
= DDR_A (ddr
);
1718 struct data_reference
*drb
= DDR_B (ddr
);
1719 tree last_conflicts
;
1721 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1722 fprintf (dump_file
, "(subscript_dependence_tester \n");
1724 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1726 tree overlaps_a
, overlaps_b
;
1727 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
1729 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
1730 DR_ACCESS_FN (drb
, i
),
1731 &overlaps_a
, &overlaps_b
,
1734 if (chrec_contains_undetermined (overlaps_a
)
1735 || chrec_contains_undetermined (overlaps_b
))
1737 finalize_ddr_dependent (ddr
, chrec_dont_know
);
1741 else if (overlaps_a
== chrec_known
1742 || overlaps_b
== chrec_known
)
1744 finalize_ddr_dependent (ddr
, chrec_known
);
1750 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
1751 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
1752 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
1756 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1757 fprintf (dump_file
, ")\n");
1760 /* Compute the classic per loop distance vector.
1762 DDR is the data dependence relation to build a vector from.
1763 NB_LOOPS is the total number of loops we are considering.
1764 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
1766 Return FALSE if the dependence relation is outside of the loop nest
1767 starting at FIRST_LOOP_DEPTH.
1768 Return TRUE otherwise. */
1771 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
1772 int nb_loops
, int first_loop_depth
)
1775 lambda_vector dist_v
, init_v
;
1777 dist_v
= lambda_vector_new (nb_loops
);
1778 init_v
= lambda_vector_new (nb_loops
);
1779 lambda_vector_clear (dist_v
, nb_loops
);
1780 lambda_vector_clear (init_v
, nb_loops
);
1782 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
1785 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1787 tree access_fn_a
, access_fn_b
;
1788 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
1790 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
1792 non_affine_dependence_relation (ddr
);
1796 access_fn_a
= DR_ACCESS_FN (DDR_A (ddr
), i
);
1797 access_fn_b
= DR_ACCESS_FN (DDR_B (ddr
), i
);
1799 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
1800 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
1802 int dist
, loop_nb
, loop_depth
;
1803 int loop_nb_a
= CHREC_VARIABLE (access_fn_a
);
1804 int loop_nb_b
= CHREC_VARIABLE (access_fn_b
);
1805 struct loop
*loop_a
= current_loops
->parray
[loop_nb_a
];
1806 struct loop
*loop_b
= current_loops
->parray
[loop_nb_b
];
1808 /* If the loop for either variable is at a lower depth than
1809 the first_loop's depth, then we can't possibly have a
1810 dependency at this level of the loop. */
1812 if (loop_a
->depth
< first_loop_depth
1813 || loop_b
->depth
< first_loop_depth
)
1816 if (loop_nb_a
!= loop_nb_b
1817 && !flow_loop_nested_p (loop_a
, loop_b
)
1818 && !flow_loop_nested_p (loop_b
, loop_a
))
1820 /* Example: when there are two consecutive loops,
1829 the dependence relation cannot be captured by the
1830 distance abstraction. */
1831 non_affine_dependence_relation (ddr
);
1835 /* The dependence is carried by the outermost loop. Example:
1842 In this case, the dependence is carried by loop_1. */
1843 loop_nb
= loop_nb_a
< loop_nb_b
? loop_nb_a
: loop_nb_b
;
1844 loop_depth
= current_loops
->parray
[loop_nb
]->depth
- first_loop_depth
;
1846 /* If the loop number is still greater than the number of
1847 loops we've been asked to analyze, or negative,
1848 something is borked. */
1849 gcc_assert (loop_depth
>= 0);
1850 gcc_assert (loop_depth
< nb_loops
);
1851 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
1853 non_affine_dependence_relation (ddr
);
1857 dist
= int_cst_value (SUB_DISTANCE (subscript
));
1859 /* This is the subscript coupling test.
1864 There is no dependence. */
1865 if (init_v
[loop_depth
] != 0
1866 && dist_v
[loop_depth
] != dist
)
1868 finalize_ddr_dependent (ddr
, chrec_known
);
1872 dist_v
[loop_depth
] = dist
;
1873 init_v
[loop_depth
] = 1;
1877 /* There is a distance of 1 on all the outer loops:
1879 Example: there is a dependence of distance 1 on loop_1 for the array A.
1885 struct loop
*lca
, *loop_a
, *loop_b
;
1886 struct data_reference
*a
= DDR_A (ddr
);
1887 struct data_reference
*b
= DDR_B (ddr
);
1889 loop_a
= loop_containing_stmt (DR_STMT (a
));
1890 loop_b
= loop_containing_stmt (DR_STMT (b
));
1892 /* Get the common ancestor loop. */
1893 lca
= find_common_loop (loop_a
, loop_b
);
1895 lca_depth
= lca
->depth
;
1896 lca_depth
-= first_loop_depth
;
1897 gcc_assert (lca_depth
>= 0);
1898 gcc_assert (lca_depth
< nb_loops
);
1900 /* For each outer loop where init_v is not set, the accesses are
1901 in dependence of distance 1 in the loop. */
1904 && init_v
[lca_depth
] == 0)
1905 dist_v
[lca_depth
] = 1;
1911 lca_depth
= lca
->depth
- first_loop_depth
;
1912 while (lca
->depth
!= 0)
1914 /* If we're considering just a sub-nest, then don't record
1915 any information on the outer loops. */
1919 gcc_assert (lca_depth
< nb_loops
);
1921 if (init_v
[lca_depth
] == 0)
1922 dist_v
[lca_depth
] = 1;
1924 lca_depth
= lca
->depth
- first_loop_depth
;
1930 DDR_DIST_VECT (ddr
) = dist_v
;
1931 DDR_SIZE_VECT (ddr
) = nb_loops
;
1935 /* Compute the classic per loop direction vector.
1937 DDR is the data dependence relation to build a vector from.
1938 NB_LOOPS is the total number of loops we are considering.
1939 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
1941 Return FALSE if the dependence relation is outside of the loop nest
1942 at FIRST_LOOP_DEPTH.
1943 Return TRUE otherwise. */
1946 build_classic_dir_vector (struct data_dependence_relation
*ddr
,
1947 int nb_loops
, int first_loop_depth
)
1950 lambda_vector dir_v
, init_v
;
1952 dir_v
= lambda_vector_new (nb_loops
);
1953 init_v
= lambda_vector_new (nb_loops
);
1954 lambda_vector_clear (dir_v
, nb_loops
);
1955 lambda_vector_clear (init_v
, nb_loops
);
1957 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
1960 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1962 tree access_fn_a
, access_fn_b
;
1963 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
1965 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
1967 non_affine_dependence_relation (ddr
);
1971 access_fn_a
= DR_ACCESS_FN (DDR_A (ddr
), i
);
1972 access_fn_b
= DR_ACCESS_FN (DDR_B (ddr
), i
);
1973 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
1974 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
1976 int dist
, loop_nb
, loop_depth
;
1977 enum data_dependence_direction dir
= dir_star
;
1978 int loop_nb_a
= CHREC_VARIABLE (access_fn_a
);
1979 int loop_nb_b
= CHREC_VARIABLE (access_fn_b
);
1980 struct loop
*loop_a
= current_loops
->parray
[loop_nb_a
];
1981 struct loop
*loop_b
= current_loops
->parray
[loop_nb_b
];
1983 /* If the loop for either variable is at a lower depth than
1984 the first_loop's depth, then we can't possibly have a
1985 dependency at this level of the loop. */
1987 if (loop_a
->depth
< first_loop_depth
1988 || loop_b
->depth
< first_loop_depth
)
1991 if (loop_nb_a
!= loop_nb_b
1992 && !flow_loop_nested_p (loop_a
, loop_b
)
1993 && !flow_loop_nested_p (loop_b
, loop_a
))
1995 /* Example: when there are two consecutive loops,
2004 the dependence relation cannot be captured by the
2005 distance abstraction. */
2006 non_affine_dependence_relation (ddr
);
2010 /* The dependence is carried by the outermost loop. Example:
2017 In this case, the dependence is carried by loop_1. */
2018 loop_nb
= loop_nb_a
< loop_nb_b
? loop_nb_a
: loop_nb_b
;
2019 loop_depth
= current_loops
->parray
[loop_nb
]->depth
- first_loop_depth
;
2021 /* If the loop number is still greater than the number of
2022 loops we've been asked to analyze, or negative,
2023 something is borked. */
2024 gcc_assert (loop_depth
>= 0);
2025 gcc_assert (loop_depth
< nb_loops
);
2027 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2029 non_affine_dependence_relation (ddr
);
2033 dist
= int_cst_value (SUB_DISTANCE (subscript
));
2042 /* This is the subscript coupling test.
2047 There is no dependence. */
2048 if (init_v
[loop_depth
] != 0
2050 && (enum data_dependence_direction
) dir_v
[loop_depth
] != dir
2051 && (enum data_dependence_direction
) dir_v
[loop_depth
] != dir_star
)
2053 finalize_ddr_dependent (ddr
, chrec_known
);
2057 dir_v
[loop_depth
] = dir
;
2058 init_v
[loop_depth
] = 1;
2062 /* There is a distance of 1 on all the outer loops:
2064 Example: there is a dependence of distance 1 on loop_1 for the array A.
2070 struct loop
*lca
, *loop_a
, *loop_b
;
2071 struct data_reference
*a
= DDR_A (ddr
);
2072 struct data_reference
*b
= DDR_B (ddr
);
2074 loop_a
= loop_containing_stmt (DR_STMT (a
));
2075 loop_b
= loop_containing_stmt (DR_STMT (b
));
2077 /* Get the common ancestor loop. */
2078 lca
= find_common_loop (loop_a
, loop_b
);
2079 lca_depth
= lca
->depth
- first_loop_depth
;
2081 gcc_assert (lca_depth
>= 0);
2082 gcc_assert (lca_depth
< nb_loops
);
2084 /* For each outer loop where init_v is not set, the accesses are
2085 in dependence of distance 1 in the loop. */
2088 && init_v
[lca_depth
] == 0)
2089 dir_v
[lca_depth
] = dir_positive
;
2094 lca_depth
= lca
->depth
- first_loop_depth
;
2095 while (lca
->depth
!= 0)
2097 /* If we're considering just a sub-nest, then don't record
2098 any information on the outer loops. */
2102 gcc_assert (lca_depth
< nb_loops
);
2104 if (init_v
[lca_depth
] == 0)
2105 dir_v
[lca_depth
] = dir_positive
;
2107 lca_depth
= lca
->depth
- first_loop_depth
;
2113 DDR_DIR_VECT (ddr
) = dir_v
;
2114 DDR_SIZE_VECT (ddr
) = nb_loops
;
2118 /* Returns true when all the access functions of A are affine or
2122 access_functions_are_affine_or_constant_p (struct data_reference
*a
)
2125 VEC(tree
,heap
) **fns
= &DR_ACCESS_FNS (a
);
2128 for (i
= 0; VEC_iterate (tree
, *fns
, i
, t
); i
++)
2129 if (!evolution_function_is_constant_p (t
)
2130 && !evolution_function_is_affine_multivariate_p (t
))
2136 /* This computes the affine dependence relation between A and B.
2137 CHREC_KNOWN is used for representing the independence between two
2138 accesses, while CHREC_DONT_KNOW is used for representing the unknown
2141 Note that it is possible to stop the computation of the dependence
2142 relation the first time we detect a CHREC_KNOWN element for a given
2146 compute_affine_dependence (struct data_dependence_relation
*ddr
)
2148 struct data_reference
*dra
= DDR_A (ddr
);
2149 struct data_reference
*drb
= DDR_B (ddr
);
2151 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2153 fprintf (dump_file
, "(compute_affine_dependence\n");
2154 fprintf (dump_file
, " (stmt_a = \n");
2155 print_generic_expr (dump_file
, DR_STMT (dra
), 0);
2156 fprintf (dump_file
, ")\n (stmt_b = \n");
2157 print_generic_expr (dump_file
, DR_STMT (drb
), 0);
2158 fprintf (dump_file
, ")\n");
2161 /* Analyze only when the dependence relation is not yet known. */
2162 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
2164 if (access_functions_are_affine_or_constant_p (dra
)
2165 && access_functions_are_affine_or_constant_p (drb
))
2166 subscript_dependence_tester (ddr
);
2168 /* As a last case, if the dependence cannot be determined, or if
2169 the dependence is considered too difficult to determine, answer
2172 finalize_ddr_dependent (ddr
, chrec_dont_know
);
2175 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2176 fprintf (dump_file
, ")\n");
2179 /* This computes the dependence relation for the same data
2180 reference into DDR. */
2183 compute_self_dependence (struct data_dependence_relation
*ddr
)
2187 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
2189 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
2191 /* The accessed index overlaps for each iteration. */
2192 SUB_CONFLICTS_IN_A (subscript
) = integer_zero_node
;
2193 SUB_CONFLICTS_IN_B (subscript
) = integer_zero_node
;
2194 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
2199 typedef struct data_dependence_relation
*ddr_p
;
2201 DEF_VEC_ALLOC_P(ddr_p
,heap
);
2203 /* Compute a subset of the data dependence relation graph. Don't
2204 compute read-read relations, and avoid the computation of the
2205 opposite relation, i.e. when AB has been computed, don't compute BA.
2206 DATAREFS contains a list of data references, and the result is set
2207 in DEPENDENCE_RELATIONS. */
2210 compute_all_dependences (varray_type datarefs
,
2211 VEC(ddr_p
,heap
) **dependence_relations
)
2213 unsigned int i
, j
, N
;
2215 N
= VARRAY_ACTIVE_SIZE (datarefs
);
2217 /* Note that we specifically skip i == j because it's a self dependence, and
2218 use compute_self_dependence below. */
2220 for (i
= 0; i
< N
; i
++)
2221 for (j
= i
+ 1; j
< N
; j
++)
2223 struct data_reference
*a
, *b
;
2224 struct data_dependence_relation
*ddr
;
2226 a
= VARRAY_GENERIC_PTR (datarefs
, i
);
2227 b
= VARRAY_GENERIC_PTR (datarefs
, j
);
2228 ddr
= initialize_data_dependence_relation (a
, b
);
2230 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
2231 compute_affine_dependence (ddr
);
2232 compute_subscript_distance (ddr
);
2235 /* Compute self dependence relation of each dataref to itself. */
2237 for (i
= 0; i
< N
; i
++)
2239 struct data_reference
*a
, *b
;
2240 struct data_dependence_relation
*ddr
;
2242 a
= VARRAY_GENERIC_PTR (datarefs
, i
);
2243 b
= VARRAY_GENERIC_PTR (datarefs
, i
);
2244 ddr
= initialize_data_dependence_relation (a
, b
);
2246 VEC_safe_push (ddr_p
, heap
, *dependence_relations
, ddr
);
2247 compute_self_dependence (ddr
);
2248 compute_subscript_distance (ddr
);
2252 /* Search the data references in LOOP, and record the information into
2253 DATAREFS. Returns chrec_dont_know when failing to analyze a
2254 difficult case, returns NULL_TREE otherwise.
2256 TODO: This function should be made smarter so that it can handle address
2257 arithmetic as if they were array accesses, etc. */
2260 find_data_references_in_loop (struct loop
*loop
, varray_type
*datarefs
)
2262 basic_block bb
, *bbs
;
2264 block_stmt_iterator bsi
;
2266 bbs
= get_loop_body (loop
);
2268 for (i
= 0; i
< loop
->num_nodes
; i
++)
2272 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
2274 tree stmt
= bsi_stmt (bsi
);
2276 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
2277 Calls have side-effects, except those to const or pure
2279 if ((TREE_CODE (stmt
) == CALL_EXPR
2280 && !(call_expr_flags (stmt
) & (ECF_CONST
| ECF_PURE
)))
2281 || (TREE_CODE (stmt
) == ASM_EXPR
2282 && ASM_VOLATILE_P (stmt
)))
2283 goto insert_dont_know_node
;
2285 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
2288 switch (TREE_CODE (stmt
))
2291 if (TREE_CODE (TREE_OPERAND (stmt
, 0)) == ARRAY_REF
)
2292 VARRAY_PUSH_GENERIC_PTR
2293 (*datarefs
, analyze_array (stmt
, TREE_OPERAND (stmt
, 0),
2296 if (TREE_CODE (TREE_OPERAND (stmt
, 1)) == ARRAY_REF
)
2297 VARRAY_PUSH_GENERIC_PTR
2298 (*datarefs
, analyze_array (stmt
, TREE_OPERAND (stmt
, 1),
2301 if (TREE_CODE (TREE_OPERAND (stmt
, 0)) != ARRAY_REF
2302 && TREE_CODE (TREE_OPERAND (stmt
, 1)) != ARRAY_REF
)
2303 goto insert_dont_know_node
;
2310 bool one_inserted
= false;
2312 for (args
= TREE_OPERAND (stmt
, 1); args
; args
= TREE_CHAIN (args
))
2313 if (TREE_CODE (TREE_VALUE (args
)) == ARRAY_REF
)
2315 VARRAY_PUSH_GENERIC_PTR
2316 (*datarefs
, analyze_array (stmt
, TREE_VALUE (args
), true));
2317 one_inserted
= true;
2321 goto insert_dont_know_node
;
2328 struct data_reference
*res
;
2330 insert_dont_know_node
:;
2331 res
= xmalloc (sizeof (struct data_reference
));
2332 DR_STMT (res
) = NULL_TREE
;
2333 DR_REF (res
) = NULL_TREE
;
2334 DR_ACCESS_FNS (res
) = NULL
;
2335 DR_BASE_NAME (res
) = NULL
;
2336 DR_IS_READ (res
) = false;
2337 VARRAY_PUSH_GENERIC_PTR (*datarefs
, res
);
2340 return chrec_dont_know
;
2344 /* When there are no defs in the loop, the loop is parallel. */
2345 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_VIRTUAL_DEFS
))
2346 loop
->parallel_p
= false;
2349 if (chrec_contains_undetermined (loop
->estimated_nb_iterations
))
2350 compute_estimated_nb_iterations (loop
);
2360 /* This section contains all the entry points. */
2362 /* Given a loop nest LOOP, the following vectors are returned:
2363 *DATAREFS is initialized to all the array elements contained in this loop,
2364 *DEPENDENCE_RELATIONS contains the relations between the data references. */
2367 compute_data_dependences_for_loop (unsigned nb_loops
,
2369 varray_type
*datarefs
,
2370 varray_type
*dependence_relations
)
2373 VEC(ddr_p
,heap
) *allrelations
;
2374 struct data_dependence_relation
*ddr
;
2376 /* If one of the data references is not computable, give up without
2377 spending time to compute other dependences. */
2378 if (find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
2380 struct data_dependence_relation
*ddr
;
2382 /* Insert a single relation into dependence_relations:
2384 ddr
= initialize_data_dependence_relation (NULL
, NULL
);
2385 VARRAY_PUSH_GENERIC_PTR (*dependence_relations
, ddr
);
2386 build_classic_dist_vector (ddr
, nb_loops
, loop
->depth
);
2387 build_classic_dir_vector (ddr
, nb_loops
, loop
->depth
);
2391 allrelations
= NULL
;
2392 compute_all_dependences (*datarefs
, &allrelations
);
2394 for (i
= 0; VEC_iterate (ddr_p
, allrelations
, i
, ddr
); i
++)
2396 if (build_classic_dist_vector (ddr
, nb_loops
, loop
->depth
))
2398 VARRAY_PUSH_GENERIC_PTR (*dependence_relations
, ddr
);
2399 build_classic_dir_vector (ddr
, nb_loops
, loop
->depth
);
2404 /* Entry point (for testing only). Analyze all the data references
2405 and the dependence relations.
2407 The data references are computed first.
2409 A relation on these nodes is represented by a complete graph. Some
2410 of the relations could be of no interest, thus the relations can be
2413 In the following function we compute all the relations. This is
2414 just a first implementation that is here for:
2415 - for showing how to ask for the dependence relations,
2416 - for the debugging the whole dependence graph,
2417 - for the dejagnu testcases and maintenance.
2419 It is possible to ask only for a part of the graph, avoiding to
2420 compute the whole dependence graph. The computed dependences are
2421 stored in a knowledge base (KB) such that later queries don't
2422 recompute the same information. The implementation of this KB is
2423 transparent to the optimizer, and thus the KB can be changed with a
2424 more efficient implementation, or the KB could be disabled. */
2427 analyze_all_data_dependences (struct loops
*loops
)
2430 varray_type datarefs
;
2431 varray_type dependence_relations
;
2432 int nb_data_refs
= 10;
2434 VARRAY_GENERIC_PTR_INIT (datarefs
, nb_data_refs
, "datarefs");
2435 VARRAY_GENERIC_PTR_INIT (dependence_relations
,
2436 nb_data_refs
* nb_data_refs
,
2437 "dependence_relations");
2439 /* Compute DDs on the whole function. */
2440 compute_data_dependences_for_loop (loops
->num
, loops
->parray
[0],
2441 &datarefs
, &dependence_relations
);
2445 dump_data_dependence_relations (dump_file
, dependence_relations
);
2446 fprintf (dump_file
, "\n\n");
2448 if (dump_flags
& TDF_DETAILS
)
2449 dump_dist_dir_vectors (dump_file
, dependence_relations
);
2451 if (dump_flags
& TDF_STATS
)
2453 unsigned nb_top_relations
= 0;
2454 unsigned nb_bot_relations
= 0;
2455 unsigned nb_basename_differ
= 0;
2456 unsigned nb_chrec_relations
= 0;
2458 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (dependence_relations
); i
++)
2460 struct data_dependence_relation
*ddr
;
2461 ddr
= VARRAY_GENERIC_PTR (dependence_relations
, i
);
2463 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
2466 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
2468 struct data_reference
*a
= DDR_A (ddr
);
2469 struct data_reference
*b
= DDR_B (ddr
);
2472 if (DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
)
2473 || (array_base_name_differ_p (a
, b
, &differ_p
) && differ_p
))
2474 nb_basename_differ
++;
2480 nb_chrec_relations
++;
2483 gather_stats_on_scev_database ();
2487 free_dependence_relations (dependence_relations
);
2488 free_data_refs (datarefs
);
2491 /* Free the memory used by a data dependence relation DDR. */
2494 free_dependence_relation (struct data_dependence_relation
*ddr
)
2499 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_SUBSCRIPTS (ddr
))
2500 varray_clear (DDR_SUBSCRIPTS (ddr
));
2504 /* Free the memory used by the data dependence relations from
2505 DEPENDENCE_RELATIONS. */
2508 free_dependence_relations (varray_type dependence_relations
)
2511 if (dependence_relations
== NULL
)
2514 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (dependence_relations
); i
++)
2515 free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations
, i
));
2516 varray_clear (dependence_relations
);
2519 /* Free the memory used by the data references from DATAREFS. */
2522 free_data_refs (varray_type datarefs
)
2526 if (datarefs
== NULL
)
2529 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (datarefs
); i
++)
2531 struct data_reference
*dr
= (struct data_reference
*)
2532 VARRAY_GENERIC_PTR (datarefs
, i
);
2535 VEC_free (tree
, heap
, DR_ACCESS_FNS (dr
));
2539 varray_clear (datarefs
);