1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* This pass walks a given loop structure searching for array
23 references. The information about the array accesses is recorded
24 in DATA_REFERENCE structures.
26 The basic test for determining the dependences is:
27 given two access functions chrec1 and chrec2 to a same array, and
28 x and y two vectors from the iteration domain, the same element of
29 the array is accessed twice at iterations x and y if and only if:
30 | chrec1 (x) == chrec2 (y).
32 The goals of this analysis are:
34 - to determine the independence: the relation between two
35 independent accesses is qualified with the chrec_known (this
36 information allows a loop parallelization),
38 - when two data references access the same data, to qualify the
39 dependence relation with classic dependence representations:
43 - loop carried level dependence
44 - polyhedron dependence
45 or with the chains of recurrences based representation,
47 - to define a knowledge base for storing the data dependence
50 - to define an interface to access this data.
55 - subscript: given two array accesses a subscript is the tuple
56 composed of the access functions for a given dimension. Example:
57 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
58 (f1, g1), (f2, g2), (f3, g3).
60 - Diophantine equation: an equation whose coefficients and
61 solutions are integer constants, for example the equation
63 has an integer solution x = 1 and y = -1.
67 - "Advanced Compilation for High Performance Computing" by Randy
68 Allen and Ken Kennedy.
69 http://citeseer.ist.psu.edu/goff91practical.html
71 - "Loop Transformations for Restructuring Compilers - The Foundations"
79 #include "coretypes.h"
85 /* These RTL headers are needed for basic-block.h. */
87 #include "basic-block.h"
88 #include "diagnostic.h"
89 #include "tree-flow.h"
90 #include "tree-dump.h"
93 #include "tree-chrec.h"
94 #include "tree-data-ref.h"
95 #include "tree-scalar-evolution.h"
96 #include "tree-pass.h"
98 /* This is the simplest data dependence test: determines whether the
99 data references A and B access the same array/region. Returns
100 false when the property is not computable at compile time.
101 Otherwise return true, and DIFFER_P will record the result. This
102 utility will not be necessary when alias_sets_conflict_p will be
103 less conservative. */
106 array_base_name_differ_p (struct data_reference
*a
,
107 struct data_reference
*b
,
110 tree base_a
= DR_BASE_NAME (a
);
111 tree base_b
= DR_BASE_NAME (b
);
113 if (!base_a
|| !base_b
)
116 /* Determine if same base. Example: for the array accesses
117 a[i], b[i] or pointer accesses *a, *b, bases are a, b. */
118 if (base_a
== base_b
)
124 /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
126 if (TREE_CODE (base_a
) == INDIRECT_REF
&& TREE_CODE (base_b
) == INDIRECT_REF
127 && TREE_OPERAND (base_a
, 0) == TREE_OPERAND (base_b
, 0))
133 /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */
134 if (TREE_CODE (base_a
) == COMPONENT_REF
&& TREE_CODE (base_b
) == COMPONENT_REF
135 && TREE_OPERAND (base_a
, 0) == TREE_OPERAND (base_b
, 0)
136 && TREE_OPERAND (base_a
, 1) == TREE_OPERAND (base_b
, 1))
143 /* Determine if different bases. */
145 /* At this point we know that base_a != base_b. However, pointer
146 accesses of the form x=(*p) and y=(*q), whose bases are p and q,
147 may still be pointing to the same base. In SSAed GIMPLE p and q will
148 be SSA_NAMES in this case. Therefore, here we check if they are
149 really two different declarations. */
150 if (TREE_CODE (base_a
) == VAR_DECL
&& TREE_CODE (base_b
) == VAR_DECL
)
156 /* Compare two record/union bases s.a and t.b: s != t or (a != b and
157 s and t are not unions). */
158 if (TREE_CODE (base_a
) == COMPONENT_REF
&& TREE_CODE (base_b
) == COMPONENT_REF
159 && ((TREE_CODE (TREE_OPERAND (base_a
, 0)) == VAR_DECL
160 && TREE_CODE (TREE_OPERAND (base_b
, 0)) == VAR_DECL
161 && TREE_OPERAND (base_a
, 0) != TREE_OPERAND (base_b
, 0))
162 || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a
, 0))) == RECORD_TYPE
163 && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b
, 0))) == RECORD_TYPE
164 && TREE_OPERAND (base_a
, 1) != TREE_OPERAND (base_b
, 1))))
170 /* Compare a record/union access and an array access. */
171 if ((TREE_CODE (base_a
) == VAR_DECL
172 && (TREE_CODE (base_b
) == COMPONENT_REF
173 && TREE_CODE (TREE_OPERAND (base_b
, 0)) == VAR_DECL
))
174 || (TREE_CODE (base_b
) == VAR_DECL
175 && (TREE_CODE (base_a
) == COMPONENT_REF
176 && TREE_CODE (TREE_OPERAND (base_a
, 0)) == VAR_DECL
)))
185 /* Returns true iff A divides B. */
188 tree_fold_divides_p (tree type
,
192 /* Determines whether (A == gcd (A, B)). */
194 (fold (build (MINUS_EXPR
, type
, a
, tree_fold_gcd (a
, b
))));
197 /* Compute the greatest common denominator of two numbers using
198 Euclid's algorithm. */
219 /* Returns true iff A divides B. */
222 int_divides_p (int a
, int b
)
224 return ((b
% a
) == 0);
229 /* Dump into FILE all the data references from DATAREFS. */
232 dump_data_references (FILE *file
,
233 varray_type datarefs
)
237 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (datarefs
); i
++)
238 dump_data_reference (file
, VARRAY_GENERIC_PTR (datarefs
, i
));
241 /* Dump into FILE all the dependence relations from DDR. */
244 dump_data_dependence_relations (FILE *file
,
249 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ddr
); i
++)
250 dump_data_dependence_relation (file
, VARRAY_GENERIC_PTR (ddr
, i
));
253 /* Dump function for a DATA_REFERENCE structure. */
256 dump_data_reference (FILE *outf
,
257 struct data_reference
*dr
)
261 fprintf (outf
, "(Data Ref: \n stmt: ");
262 print_generic_stmt (outf
, DR_STMT (dr
), 0);
263 fprintf (outf
, " ref: ");
264 print_generic_stmt (outf
, DR_REF (dr
), 0);
265 fprintf (outf
, " base_name: ");
266 print_generic_stmt (outf
, DR_BASE_NAME (dr
), 0);
268 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
270 fprintf (outf
, " Access function %d: ", i
);
271 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
273 fprintf (outf
, ")\n");
276 /* Dump function for a SUBSCRIPT structure. */
279 dump_subscript (FILE *outf
, struct subscript
*subscript
)
281 tree chrec
= SUB_CONFLICTS_IN_A (subscript
);
283 fprintf (outf
, "\n (subscript \n");
284 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
285 print_generic_stmt (outf
, chrec
, 0);
286 if (chrec
== chrec_known
)
287 fprintf (outf
, " (no dependence)\n");
288 else if (chrec_contains_undetermined (chrec
))
289 fprintf (outf
, " (don't know)\n");
292 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
293 fprintf (outf
, " last_conflict: ");
294 print_generic_stmt (outf
, last_iteration
, 0);
297 chrec
= SUB_CONFLICTS_IN_B (subscript
);
298 fprintf (outf
, " iterations_that_access_an_element_twice_in_B: ");
299 print_generic_stmt (outf
, chrec
, 0);
300 if (chrec
== chrec_known
)
301 fprintf (outf
, " (no dependence)\n");
302 else if (chrec_contains_undetermined (chrec
))
303 fprintf (outf
, " (don't know)\n");
306 tree last_iteration
= SUB_LAST_CONFLICT (subscript
);
307 fprintf (outf
, " last_conflict: ");
308 print_generic_stmt (outf
, last_iteration
, 0);
311 fprintf (outf
, " (Subscript distance: ");
312 print_generic_stmt (outf
, SUB_DISTANCE (subscript
), 0);
313 fprintf (outf
, " )\n");
314 fprintf (outf
, " )\n");
317 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
320 dump_data_dependence_relation (FILE *outf
,
321 struct data_dependence_relation
*ddr
)
323 struct data_reference
*dra
, *drb
;
327 fprintf (outf
, "(Data Dep: \n");
328 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
329 fprintf (outf
, " (don't know)\n");
331 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
332 fprintf (outf
, " (no dependence)\n");
334 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
337 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
339 fprintf (outf
, " access_fn_A: ");
340 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
341 fprintf (outf
, " access_fn_B: ");
342 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
343 dump_subscript (outf
, DDR_SUBSCRIPT (ddr
, i
));
345 if (DDR_DIST_VECT (ddr
))
347 fprintf (outf
, " distance_vect: ");
348 print_lambda_vector (outf
, DDR_DIST_VECT (ddr
), DDR_SIZE_VECT (ddr
));
350 if (DDR_DIR_VECT (ddr
))
352 fprintf (outf
, " direction_vect: ");
353 print_lambda_vector (outf
, DDR_DIR_VECT (ddr
), DDR_SIZE_VECT (ddr
));
357 fprintf (outf
, ")\n");
362 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
365 dump_data_dependence_direction (FILE *file
,
366 enum data_dependence_direction dir
)
382 case dir_positive_or_negative
:
383 fprintf (file
, "+-");
386 case dir_positive_or_equal
:
387 fprintf (file
, "+=");
390 case dir_negative_or_equal
:
391 fprintf (file
, "-=");
403 /* Dumps the distance and direction vectors in FILE. DDRS contains
404 the dependence relations, and VECT_SIZE is the size of the
405 dependence vectors, or in other words the number of loops in the
409 dump_dist_dir_vectors (FILE *file
, varray_type ddrs
)
413 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ddrs
); i
++)
415 struct data_dependence_relation
*ddr
=
416 (struct data_dependence_relation
*)
417 VARRAY_GENERIC_PTR (ddrs
, i
);
418 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
419 && DDR_AFFINE_P (ddr
))
421 fprintf (file
, "DISTANCE_V (");
422 print_lambda_vector (file
, DDR_DIST_VECT (ddr
), DDR_SIZE_VECT (ddr
));
423 fprintf (file
, ")\n");
424 fprintf (file
, "DIRECTION_V (");
425 print_lambda_vector (file
, DDR_DIR_VECT (ddr
), DDR_SIZE_VECT (ddr
));
426 fprintf (file
, ")\n");
429 fprintf (file
, "\n\n");
432 /* Dumps the data dependence relations DDRS in FILE. */
435 dump_ddrs (FILE *file
, varray_type ddrs
)
439 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ddrs
); i
++)
441 struct data_dependence_relation
*ddr
=
442 (struct data_dependence_relation
*)
443 VARRAY_GENERIC_PTR (ddrs
, i
);
444 dump_data_dependence_relation (file
, ddr
);
446 fprintf (file
, "\n\n");
451 /* Compute the lowest iteration bound for LOOP. It is an
455 compute_estimated_nb_iterations (struct loop
*loop
)
458 struct nb_iter_bound
*bound
, *next
;
460 for (bound
= loop
->bounds
; bound
; bound
= next
)
463 estimation
= bound
->bound
;
465 if (TREE_CODE (estimation
) != INTEGER_CST
)
468 if (loop
->estimated_nb_iterations
)
470 /* Update only if estimation is smaller. */
471 if (tree_int_cst_lt (estimation
, loop
->estimated_nb_iterations
))
472 loop
->estimated_nb_iterations
= estimation
;
475 loop
->estimated_nb_iterations
= estimation
;
479 /* Estimate the number of iterations from the size of the data and the
483 estimate_niter_from_size_of_data (struct loop
*loop
,
489 tree array_size
, data_size
, element_size
;
492 init
= initial_condition (access_fn
);
493 step
= evolution_part_in_loop_num (access_fn
, loop
->num
);
495 array_size
= TYPE_SIZE (TREE_TYPE (opnd0
));
496 element_size
= TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0
)));
497 if (array_size
== NULL_TREE
498 || TREE_CODE (array_size
) != INTEGER_CST
499 || TREE_CODE (element_size
) != INTEGER_CST
)
502 data_size
= fold (build2 (EXACT_DIV_EXPR
, integer_type_node
,
503 array_size
, element_size
));
505 if (init
!= NULL_TREE
507 && TREE_CODE (init
) == INTEGER_CST
508 && TREE_CODE (step
) == INTEGER_CST
)
510 estimation
= fold (build2 (CEIL_DIV_EXPR
, integer_type_node
,
511 fold (build2 (MINUS_EXPR
, integer_type_node
,
512 data_size
, init
)), step
));
514 record_estimate (loop
, estimation
, boolean_true_node
, stmt
);
518 /* Given an ARRAY_REF node REF, records its access functions.
519 Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
520 i.e. the constant "3", then recursively call the function on opnd0,
521 i.e. the ARRAY_REF "A[i]". The function returns the base name:
525 analyze_array_indexes (struct loop
*loop
,
526 varray_type
*access_fns
,
532 opnd0
= TREE_OPERAND (ref
, 0);
533 opnd1
= TREE_OPERAND (ref
, 1);
535 /* The detection of the evolution function for this data access is
536 postponed until the dependence test. This lazy strategy avoids
537 the computation of access functions that are of no interest for
539 access_fn
= instantiate_parameters
540 (loop
, analyze_scalar_evolution (loop
, opnd1
));
542 if (loop
->estimated_nb_iterations
== NULL_TREE
)
543 estimate_niter_from_size_of_data (loop
, opnd0
, access_fn
, stmt
);
545 VARRAY_PUSH_TREE (*access_fns
, access_fn
);
547 /* Recursively record other array access functions. */
548 if (TREE_CODE (opnd0
) == ARRAY_REF
)
549 return analyze_array_indexes (loop
, access_fns
, opnd0
, stmt
);
551 /* Return the base name of the data access. */
556 /* For a data reference REF contained in the statement STMT, initialize
557 a DATA_REFERENCE structure, and return it. IS_READ flag has to be
558 set to true when REF is in the right hand side of an
561 struct data_reference
*
562 analyze_array (tree stmt
, tree ref
, bool is_read
)
564 struct data_reference
*res
;
566 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
568 fprintf (dump_file
, "(analyze_array \n");
569 fprintf (dump_file
, " (ref = ");
570 print_generic_stmt (dump_file
, ref
, 0);
571 fprintf (dump_file
, ")\n");
574 res
= xmalloc (sizeof (struct data_reference
));
576 DR_STMT (res
) = stmt
;
578 VARRAY_TREE_INIT (DR_ACCESS_FNS (res
), 3, "access_fns");
579 DR_BASE_NAME (res
) = analyze_array_indexes
580 (loop_containing_stmt (stmt
), &(DR_ACCESS_FNS (res
)), ref
, stmt
);
581 DR_IS_READ (res
) = is_read
;
583 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
584 fprintf (dump_file
, ")\n");
589 /* For a data reference REF contained in the statement STMT, initialize
590 a DATA_REFERENCE structure, and return it. */
592 struct data_reference
*
593 init_data_ref (tree stmt
,
599 struct data_reference
*res
;
601 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
603 fprintf (dump_file
, "(init_data_ref \n");
604 fprintf (dump_file
, " (ref = ");
605 print_generic_stmt (dump_file
, ref
, 0);
606 fprintf (dump_file
, ")\n");
609 res
= xmalloc (sizeof (struct data_reference
));
611 DR_STMT (res
) = stmt
;
613 VARRAY_TREE_INIT (DR_ACCESS_FNS (res
), 5, "access_fns");
614 DR_BASE_NAME (res
) = base
;
615 VARRAY_PUSH_TREE (DR_ACCESS_FNS (res
), access_fn
);
616 DR_IS_READ (res
) = is_read
;
618 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
619 fprintf (dump_file
, ")\n");
626 /* Returns true when all the functions of a tree_vec CHREC are the
630 all_chrecs_equal_p (tree chrec
)
634 for (j
= 0; j
< TREE_VEC_LENGTH (chrec
) - 1; j
++)
636 tree chrec_j
= TREE_VEC_ELT (chrec
, j
);
637 tree chrec_j_1
= TREE_VEC_ELT (chrec
, j
+ 1);
640 (integer_type_node
, chrec_j
, chrec_j_1
)))
646 /* Determine for each subscript in the data dependence relation DDR
650 compute_subscript_distance (struct data_dependence_relation
*ddr
)
652 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
656 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
658 tree conflicts_a
, conflicts_b
, difference
;
659 struct subscript
*subscript
;
661 subscript
= DDR_SUBSCRIPT (ddr
, i
);
662 conflicts_a
= SUB_CONFLICTS_IN_A (subscript
);
663 conflicts_b
= SUB_CONFLICTS_IN_B (subscript
);
665 if (TREE_CODE (conflicts_a
) == TREE_VEC
)
667 if (!all_chrecs_equal_p (conflicts_a
))
669 SUB_DISTANCE (subscript
) = chrec_dont_know
;
673 conflicts_a
= TREE_VEC_ELT (conflicts_a
, 0);
676 if (TREE_CODE (conflicts_b
) == TREE_VEC
)
678 if (!all_chrecs_equal_p (conflicts_b
))
680 SUB_DISTANCE (subscript
) = chrec_dont_know
;
684 conflicts_b
= TREE_VEC_ELT (conflicts_b
, 0);
687 difference
= chrec_fold_minus
688 (integer_type_node
, conflicts_b
, conflicts_a
);
690 if (evolution_function_is_constant_p (difference
))
691 SUB_DISTANCE (subscript
) = difference
;
694 SUB_DISTANCE (subscript
) = chrec_dont_know
;
699 /* Initialize a ddr. */
701 struct data_dependence_relation
*
702 initialize_data_dependence_relation (struct data_reference
*a
,
703 struct data_reference
*b
)
705 struct data_dependence_relation
*res
;
708 res
= xmalloc (sizeof (struct data_dependence_relation
));
712 if (a
== NULL
|| b
== NULL
713 || DR_BASE_NAME (a
) == NULL_TREE
714 || DR_BASE_NAME (b
) == NULL_TREE
)
715 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
717 /* When the dimensions of A and B differ, we directly initialize
718 the relation to "there is no dependence": chrec_known. */
719 else if (DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
)
720 || (array_base_name_differ_p (a
, b
, &differ_p
) && differ_p
))
721 DDR_ARE_DEPENDENT (res
) = chrec_known
;
726 DDR_AFFINE_P (res
) = true;
727 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
728 DDR_SUBSCRIPTS_VECTOR_INIT (res
, DR_NUM_DIMENSIONS (a
));
729 DDR_SIZE_VECT (res
) = 0;
730 DDR_DIST_VECT (res
) = NULL
;
731 DDR_DIR_VECT (res
) = NULL
;
733 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
735 struct subscript
*subscript
;
737 subscript
= xmalloc (sizeof (struct subscript
));
738 SUB_CONFLICTS_IN_A (subscript
) = chrec_dont_know
;
739 SUB_CONFLICTS_IN_B (subscript
) = chrec_dont_know
;
740 SUB_LAST_CONFLICT (subscript
) = chrec_dont_know
;
741 SUB_DISTANCE (subscript
) = chrec_dont_know
;
742 VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res
), subscript
);
749 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
753 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
756 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
758 fprintf (dump_file
, "(dependence classified: ");
759 print_generic_expr (dump_file
, chrec
, 0);
760 fprintf (dump_file
, ")\n");
763 DDR_ARE_DEPENDENT (ddr
) = chrec
;
764 varray_clear (DDR_SUBSCRIPTS (ddr
));
767 /* The dependence relation DDR cannot be represented by a distance
771 non_affine_dependence_relation (struct data_dependence_relation
*ddr
)
773 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
774 fprintf (dump_file
, "(Dependence relation cannot be represented by distance vector.) \n");
776 DDR_AFFINE_P (ddr
) = false;
781 /* This section contains the classic Banerjee tests. */
783 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
784 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
787 ziv_subscript_p (tree chrec_a
,
790 return (evolution_function_is_constant_p (chrec_a
)
791 && evolution_function_is_constant_p (chrec_b
));
794 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
795 variable, i.e., if the SIV (Single Index Variable) test is true. */
798 siv_subscript_p (tree chrec_a
,
801 if ((evolution_function_is_constant_p (chrec_a
)
802 && evolution_function_is_univariate_p (chrec_b
))
803 || (evolution_function_is_constant_p (chrec_b
)
804 && evolution_function_is_univariate_p (chrec_a
)))
807 if (evolution_function_is_univariate_p (chrec_a
)
808 && evolution_function_is_univariate_p (chrec_b
))
810 switch (TREE_CODE (chrec_a
))
812 case POLYNOMIAL_CHREC
:
813 switch (TREE_CODE (chrec_b
))
815 case POLYNOMIAL_CHREC
:
816 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
831 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
832 *OVERLAPS_B are initialized to the functions that describe the
833 relation between the elements accessed twice by CHREC_A and
834 CHREC_B. For k >= 0, the following property is verified:
836 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
839 analyze_ziv_subscript (tree chrec_a
,
843 tree
*last_conflicts
)
847 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
848 fprintf (dump_file
, "(analyze_ziv_subscript \n");
850 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
852 switch (TREE_CODE (difference
))
855 if (integer_zerop (difference
))
857 /* The difference is equal to zero: the accessed index
858 overlaps for each iteration in the loop. */
859 *overlaps_a
= integer_zero_node
;
860 *overlaps_b
= integer_zero_node
;
861 *last_conflicts
= chrec_dont_know
;
865 /* The accesses do not overlap. */
866 *overlaps_a
= chrec_known
;
867 *overlaps_b
= chrec_known
;
868 *last_conflicts
= integer_zero_node
;
873 /* We're not sure whether the indexes overlap. For the moment,
874 conservatively answer "don't know". */
875 *overlaps_a
= chrec_dont_know
;
876 *overlaps_b
= chrec_dont_know
;
877 *last_conflicts
= chrec_dont_know
;
881 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
882 fprintf (dump_file
, ")\n");
885 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
886 constant, and CHREC_B is an affine function. *OVERLAPS_A and
887 *OVERLAPS_B are initialized to the functions that describe the
888 relation between the elements accessed twice by CHREC_A and
889 CHREC_B. For k >= 0, the following property is verified:
891 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
894 analyze_siv_subscript_cst_affine (tree chrec_a
,
898 tree
*last_conflicts
)
900 bool value0
, value1
, value2
;
901 tree difference
= chrec_fold_minus
902 (integer_type_node
, CHREC_LEFT (chrec_b
), chrec_a
);
904 if (!chrec_is_positive (initial_condition (difference
), &value0
))
906 *overlaps_a
= chrec_dont_know
;
907 *overlaps_b
= chrec_dont_know
;
908 *last_conflicts
= chrec_dont_know
;
915 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
917 *overlaps_a
= chrec_dont_know
;
918 *overlaps_b
= chrec_dont_know
;
919 *last_conflicts
= chrec_dont_know
;
931 if (tree_fold_divides_p
932 (integer_type_node
, CHREC_RIGHT (chrec_b
), difference
))
934 *overlaps_a
= integer_zero_node
;
936 (build (EXACT_DIV_EXPR
, integer_type_node
,
937 fold (build1 (ABS_EXPR
, integer_type_node
, difference
)),
938 CHREC_RIGHT (chrec_b
)));
939 *last_conflicts
= integer_one_node
;
943 /* When the step does not divides the difference, there are
947 *overlaps_a
= chrec_known
;
948 *overlaps_b
= chrec_known
;
949 *last_conflicts
= integer_zero_node
;
958 chrec_b = {10, +, -1}
960 In this case, chrec_a will not overlap with chrec_b. */
961 *overlaps_a
= chrec_known
;
962 *overlaps_b
= chrec_known
;
963 *last_conflicts
= integer_zero_node
;
970 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
972 *overlaps_a
= chrec_dont_know
;
973 *overlaps_b
= chrec_dont_know
;
974 *last_conflicts
= chrec_dont_know
;
983 chrec_b = {10, +, -1}
985 if (tree_fold_divides_p
986 (integer_type_node
, CHREC_RIGHT (chrec_b
), difference
))
988 *overlaps_a
= integer_zero_node
;
990 (build (EXACT_DIV_EXPR
, integer_type_node
, difference
,
991 CHREC_RIGHT (chrec_b
)));
992 *last_conflicts
= integer_one_node
;
996 /* When the step does not divides the difference, there
1000 *overlaps_a
= chrec_known
;
1001 *overlaps_b
= chrec_known
;
1002 *last_conflicts
= integer_zero_node
;
1012 In this case, chrec_a will not overlap with chrec_b. */
1013 *overlaps_a
= chrec_known
;
1014 *overlaps_b
= chrec_known
;
1015 *last_conflicts
= integer_zero_node
;
1023 /* Helper recursive function for initializing the matrix A. Returns
1024 the initial value of CHREC. */
1027 initialize_matrix_A (lambda_matrix A
, tree chrec
, unsigned index
, int mult
)
1031 if (TREE_CODE (chrec
) != POLYNOMIAL_CHREC
)
1032 return int_cst_value (chrec
);
1034 A
[index
][0] = mult
* int_cst_value (CHREC_RIGHT (chrec
));
1035 return initialize_matrix_A (A
, CHREC_LEFT (chrec
), index
+ 1, mult
);
1038 #define FLOOR_DIV(x,y) ((x) / (y))
1040 /* Solves the special case of the Diophantine equation:
1041 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1043 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1044 number of iterations that loops X and Y run. The overlaps will be
1045 constructed as evolutions in dimension DIM. */
1048 compute_overlap_steps_for_affine_univar (int niter
, int step_a
, int step_b
,
1049 tree
*overlaps_a
, tree
*overlaps_b
,
1050 tree
*last_conflicts
, int dim
)
1052 if (((step_a
> 0 && step_b
> 0)
1053 || (step_a
< 0 && step_b
< 0)))
1055 int step_overlaps_a
, step_overlaps_b
;
1056 int gcd_steps_a_b
, last_conflict
, tau2
;
1058 gcd_steps_a_b
= gcd (step_a
, step_b
);
1059 step_overlaps_a
= step_b
/ gcd_steps_a_b
;
1060 step_overlaps_b
= step_a
/ gcd_steps_a_b
;
1062 tau2
= FLOOR_DIV (niter
, step_overlaps_a
);
1063 tau2
= MIN (tau2
, FLOOR_DIV (niter
, step_overlaps_b
));
1064 last_conflict
= tau2
;
1066 *overlaps_a
= build_polynomial_chrec
1067 (dim
, integer_zero_node
,
1068 build_int_cst (NULL_TREE
, step_overlaps_a
));
1069 *overlaps_b
= build_polynomial_chrec
1070 (dim
, integer_zero_node
,
1071 build_int_cst (NULL_TREE
, step_overlaps_b
));
1072 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
1077 *overlaps_a
= integer_zero_node
;
1078 *overlaps_b
= integer_zero_node
;
1079 *last_conflicts
= integer_zero_node
;
1084 /* Solves the special case of a Diophantine equation where CHREC_A is
1085 an affine bivariate function, and CHREC_B is an affine univariate
1086 function. For example,
1088 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1090 has the following overlapping functions:
1092 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1093 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1094 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1096 FORNOW: This is a specialized implementation for a case occurring in
1097 a common benchmark. Implement the general algorithm. */
1100 compute_overlap_steps_for_affine_1_2 (tree chrec_a
, tree chrec_b
,
1101 tree
*overlaps_a
, tree
*overlaps_b
,
1102 tree
*last_conflicts
)
1104 bool xz_p
, yz_p
, xyz_p
;
1105 int step_x
, step_y
, step_z
;
1106 int niter_x
, niter_y
, niter_z
, niter
;
1107 tree numiter_x
, numiter_y
, numiter_z
;
1108 tree overlaps_a_xz
, overlaps_b_xz
, last_conflicts_xz
;
1109 tree overlaps_a_yz
, overlaps_b_yz
, last_conflicts_yz
;
1110 tree overlaps_a_xyz
, overlaps_b_xyz
, last_conflicts_xyz
;
1112 step_x
= int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a
)));
1113 step_y
= int_cst_value (CHREC_RIGHT (chrec_a
));
1114 step_z
= int_cst_value (CHREC_RIGHT (chrec_b
));
1116 numiter_x
= number_of_iterations_in_loop
1117 (current_loops
->parray
[CHREC_VARIABLE (CHREC_LEFT (chrec_a
))]);
1118 numiter_y
= number_of_iterations_in_loop
1119 (current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]);
1120 numiter_z
= number_of_iterations_in_loop
1121 (current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]);
1123 if (TREE_CODE (numiter_x
) != INTEGER_CST
)
1124 numiter_x
= current_loops
->parray
[CHREC_VARIABLE (CHREC_LEFT (chrec_a
))]
1125 ->estimated_nb_iterations
;
1126 if (TREE_CODE (numiter_y
) != INTEGER_CST
)
1127 numiter_y
= current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]
1128 ->estimated_nb_iterations
;
1129 if (TREE_CODE (numiter_z
) != INTEGER_CST
)
1130 numiter_z
= current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]
1131 ->estimated_nb_iterations
;
1133 if (numiter_x
== NULL_TREE
|| numiter_y
== NULL_TREE
1134 || numiter_z
== NULL_TREE
)
1136 *overlaps_a
= chrec_dont_know
;
1137 *overlaps_b
= chrec_dont_know
;
1138 *last_conflicts
= chrec_dont_know
;
1142 niter_x
= int_cst_value (numiter_x
);
1143 niter_y
= int_cst_value (numiter_y
);
1144 niter_z
= int_cst_value (numiter_z
);
1146 niter
= MIN (niter_x
, niter_z
);
1147 compute_overlap_steps_for_affine_univar (niter
, step_x
, step_z
,
1150 &last_conflicts_xz
, 1);
1151 niter
= MIN (niter_y
, niter_z
);
1152 compute_overlap_steps_for_affine_univar (niter
, step_y
, step_z
,
1155 &last_conflicts_yz
, 2);
1156 niter
= MIN (niter_x
, niter_z
);
1157 niter
= MIN (niter_y
, niter
);
1158 compute_overlap_steps_for_affine_univar (niter
, step_x
+ step_y
, step_z
,
1161 &last_conflicts_xyz
, 3);
1163 xz_p
= !integer_zerop (last_conflicts_xz
);
1164 yz_p
= !integer_zerop (last_conflicts_yz
);
1165 xyz_p
= !integer_zerop (last_conflicts_xyz
);
1167 if (xz_p
|| yz_p
|| xyz_p
)
1169 *overlaps_a
= make_tree_vec (2);
1170 TREE_VEC_ELT (*overlaps_a
, 0) = integer_zero_node
;
1171 TREE_VEC_ELT (*overlaps_a
, 1) = integer_zero_node
;
1172 *overlaps_b
= integer_zero_node
;
1175 TREE_VEC_ELT (*overlaps_a
, 0) =
1176 chrec_fold_plus (integer_type_node
, TREE_VEC_ELT (*overlaps_a
, 0),
1179 chrec_fold_plus (integer_type_node
, *overlaps_b
, overlaps_b_xz
);
1180 *last_conflicts
= last_conflicts_xz
;
1184 TREE_VEC_ELT (*overlaps_a
, 1) =
1185 chrec_fold_plus (integer_type_node
, TREE_VEC_ELT (*overlaps_a
, 1),
1188 chrec_fold_plus (integer_type_node
, *overlaps_b
, overlaps_b_yz
);
1189 *last_conflicts
= last_conflicts_yz
;
1193 TREE_VEC_ELT (*overlaps_a
, 0) =
1194 chrec_fold_plus (integer_type_node
, TREE_VEC_ELT (*overlaps_a
, 0),
1196 TREE_VEC_ELT (*overlaps_a
, 1) =
1197 chrec_fold_plus (integer_type_node
, TREE_VEC_ELT (*overlaps_a
, 1),
1200 chrec_fold_plus (integer_type_node
, *overlaps_b
, overlaps_b_xyz
);
1201 *last_conflicts
= last_conflicts_xyz
;
1206 *overlaps_a
= integer_zero_node
;
1207 *overlaps_b
= integer_zero_node
;
1208 *last_conflicts
= integer_zero_node
;
1212 /* Determines the overlapping elements due to accesses CHREC_A and
1213 CHREC_B, that are affine functions. This is a part of the
1214 subscript analyzer. */
1217 analyze_subscript_affine_affine (tree chrec_a
,
1221 tree
*last_conflicts
)
1223 unsigned nb_vars_a
, nb_vars_b
, dim
;
1224 int init_a
, init_b
, gamma
, gcd_alpha_beta
;
1226 lambda_matrix A
, U
, S
;
1228 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1229 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
1231 /* For determining the initial intersection, we have to solve a
1232 Diophantine equation. This is the most time consuming part.
1234 For answering to the question: "Is there a dependence?" we have
1235 to prove that there exists a solution to the Diophantine
1236 equation, and that the solution is in the iteration domain,
1237 i.e. the solution is positive or zero, and that the solution
1238 happens before the upper bound loop.nb_iterations. Otherwise
1239 there is no dependence. This function outputs a description of
1240 the iterations that hold the intersections. */
1243 nb_vars_a
= nb_vars_in_chrec (chrec_a
);
1244 nb_vars_b
= nb_vars_in_chrec (chrec_b
);
1246 dim
= nb_vars_a
+ nb_vars_b
;
1247 U
= lambda_matrix_new (dim
, dim
);
1248 A
= lambda_matrix_new (dim
, 1);
1249 S
= lambda_matrix_new (dim
, 1);
1251 init_a
= initialize_matrix_A (A
, chrec_a
, 0, 1);
1252 init_b
= initialize_matrix_A (A
, chrec_b
, nb_vars_a
, -1);
1253 gamma
= init_b
- init_a
;
1255 /* Don't do all the hard work of solving the Diophantine equation
1256 when we already know the solution: for example,
1259 | gamma = 3 - 3 = 0.
1260 Then the first overlap occurs during the first iterations:
1261 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
1265 if (nb_vars_a
== 1 && nb_vars_b
== 1)
1268 int niter
, niter_a
, niter_b
;
1269 tree numiter_a
, numiter_b
;
1271 numiter_a
= number_of_iterations_in_loop
1272 (current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]);
1273 numiter_b
= number_of_iterations_in_loop
1274 (current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]);
1276 if (TREE_CODE (numiter_a
) != INTEGER_CST
)
1277 numiter_a
= current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]
1278 ->estimated_nb_iterations
;
1279 if (TREE_CODE (numiter_b
) != INTEGER_CST
)
1280 numiter_b
= current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]
1281 ->estimated_nb_iterations
;
1282 if (numiter_a
== NULL_TREE
|| numiter_b
== NULL_TREE
)
1284 *overlaps_a
= chrec_dont_know
;
1285 *overlaps_b
= chrec_dont_know
;
1286 *last_conflicts
= chrec_dont_know
;
1290 niter_a
= int_cst_value (numiter_a
);
1291 niter_b
= int_cst_value (numiter_b
);
1292 niter
= MIN (niter_a
, niter_b
);
1294 step_a
= int_cst_value (CHREC_RIGHT (chrec_a
));
1295 step_b
= int_cst_value (CHREC_RIGHT (chrec_b
));
1297 compute_overlap_steps_for_affine_univar (niter
, step_a
, step_b
,
1298 overlaps_a
, overlaps_b
,
1302 else if (nb_vars_a
== 2 && nb_vars_b
== 1)
1303 compute_overlap_steps_for_affine_1_2
1304 (chrec_a
, chrec_b
, overlaps_a
, overlaps_b
, last_conflicts
);
1306 else if (nb_vars_a
== 1 && nb_vars_b
== 2)
1307 compute_overlap_steps_for_affine_1_2
1308 (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
, last_conflicts
);
1312 *overlaps_a
= chrec_dont_know
;
1313 *overlaps_b
= chrec_dont_know
;
1314 *last_conflicts
= chrec_dont_know
;
1320 lambda_matrix_right_hermite (A
, dim
, 1, S
, U
);
1325 lambda_matrix_row_negate (U
, dim
, 0);
1327 gcd_alpha_beta
= S
[0][0];
1329 /* The classic "gcd-test". */
1330 if (!int_divides_p (gcd_alpha_beta
, gamma
))
1332 /* The "gcd-test" has determined that there is no integer
1333 solution, i.e. there is no dependence. */
1334 *overlaps_a
= chrec_known
;
1335 *overlaps_b
= chrec_known
;
1336 *last_conflicts
= integer_zero_node
;
1339 /* Both access functions are univariate. This includes SIV and MIV cases. */
1340 else if (nb_vars_a
== 1 && nb_vars_b
== 1)
1342 /* Both functions should have the same evolution sign. */
1343 if (((A
[0][0] > 0 && -A
[1][0] > 0)
1344 || (A
[0][0] < 0 && -A
[1][0] < 0)))
1346 /* The solutions are given by:
1348 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
1351 For a given integer t. Using the following variables,
1353 | i0 = u11 * gamma / gcd_alpha_beta
1354 | j0 = u12 * gamma / gcd_alpha_beta
1361 | y0 = j0 + j1 * t. */
1365 /* X0 and Y0 are the first iterations for which there is a
1366 dependence. X0, Y0 are two solutions of the Diophantine
1367 equation: chrec_a (X0) = chrec_b (Y0). */
1369 int niter
, niter_a
, niter_b
;
1370 tree numiter_a
, numiter_b
;
1372 numiter_a
= number_of_iterations_in_loop
1373 (current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]);
1374 numiter_b
= number_of_iterations_in_loop
1375 (current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]);
1377 if (TREE_CODE (numiter_a
) != INTEGER_CST
)
1378 numiter_a
= current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]
1379 ->estimated_nb_iterations
;
1380 if (TREE_CODE (numiter_b
) != INTEGER_CST
)
1381 numiter_b
= current_loops
->parray
[CHREC_VARIABLE (chrec_b
)]
1382 ->estimated_nb_iterations
;
1383 if (numiter_a
== NULL_TREE
|| numiter_b
== NULL_TREE
)
1385 *overlaps_a
= chrec_dont_know
;
1386 *overlaps_b
= chrec_dont_know
;
1387 *last_conflicts
= chrec_dont_know
;
1391 niter_a
= int_cst_value (numiter_a
);
1392 niter_b
= int_cst_value (numiter_b
);
1393 niter
= MIN (niter_a
, niter_b
);
1395 i0
= U
[0][0] * gamma
/ gcd_alpha_beta
;
1396 j0
= U
[0][1] * gamma
/ gcd_alpha_beta
;
1400 if ((i1
== 0 && i0
< 0)
1401 || (j1
== 0 && j0
< 0))
1403 /* There is no solution.
1404 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
1405 falls in here, but for the moment we don't look at the
1406 upper bound of the iteration domain. */
1407 *overlaps_a
= chrec_known
;
1408 *overlaps_b
= chrec_known
;
1409 *last_conflicts
= integer_zero_node
;
1416 tau1
= CEIL (-i0
, i1
);
1417 tau2
= FLOOR_DIV (niter
- i0
, i1
);
1421 int last_conflict
, min_multiple
;
1422 tau1
= MAX (tau1
, CEIL (-j0
, j1
));
1423 tau2
= MIN (tau2
, FLOOR_DIV (niter
- j0
, j1
));
1425 x0
= i1
* tau1
+ i0
;
1426 y0
= j1
* tau1
+ j0
;
1428 /* At this point (x0, y0) is one of the
1429 solutions to the Diophantine equation. The
1430 next step has to compute the smallest
1431 positive solution: the first conflicts. */
1432 min_multiple
= MIN (x0
/ i1
, y0
/ j1
);
1433 x0
-= i1
* min_multiple
;
1434 y0
-= j1
* min_multiple
;
1436 tau1
= (x0
- i0
)/i1
;
1437 last_conflict
= tau2
- tau1
;
1439 *overlaps_a
= build_polynomial_chrec
1441 build_int_cst (NULL_TREE
, x0
),
1442 build_int_cst (NULL_TREE
, i1
));
1443 *overlaps_b
= build_polynomial_chrec
1445 build_int_cst (NULL_TREE
, y0
),
1446 build_int_cst (NULL_TREE
, j1
));
1447 *last_conflicts
= build_int_cst (NULL_TREE
, last_conflict
);
1451 /* FIXME: For the moment, the upper bound of the
1452 iteration domain for j is not checked. */
1453 *overlaps_a
= chrec_dont_know
;
1454 *overlaps_b
= chrec_dont_know
;
1455 *last_conflicts
= chrec_dont_know
;
1461 /* FIXME: For the moment, the upper bound of the
1462 iteration domain for i is not checked. */
1463 *overlaps_a
= chrec_dont_know
;
1464 *overlaps_b
= chrec_dont_know
;
1465 *last_conflicts
= chrec_dont_know
;
1471 *overlaps_a
= chrec_dont_know
;
1472 *overlaps_b
= chrec_dont_know
;
1473 *last_conflicts
= chrec_dont_know
;
1479 *overlaps_a
= chrec_dont_know
;
1480 *overlaps_b
= chrec_dont_know
;
1481 *last_conflicts
= chrec_dont_know
;
1485 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1487 fprintf (dump_file
, " (overlaps_a = ");
1488 print_generic_expr (dump_file
, *overlaps_a
, 0);
1489 fprintf (dump_file
, ")\n (overlaps_b = ");
1490 print_generic_expr (dump_file
, *overlaps_b
, 0);
1491 fprintf (dump_file
, ")\n");
1494 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1495 fprintf (dump_file
, ")\n");
1498 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
1499 *OVERLAPS_B are initialized to the functions that describe the
1500 relation between the elements accessed twice by CHREC_A and
1501 CHREC_B. For k >= 0, the following property is verified:
1503 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1506 analyze_siv_subscript (tree chrec_a
,
1510 tree
*last_conflicts
)
1512 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1513 fprintf (dump_file
, "(analyze_siv_subscript \n");
1515 if (evolution_function_is_constant_p (chrec_a
)
1516 && evolution_function_is_affine_p (chrec_b
))
1517 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
1518 overlaps_a
, overlaps_b
, last_conflicts
);
1520 else if (evolution_function_is_affine_p (chrec_a
)
1521 && evolution_function_is_constant_p (chrec_b
))
1522 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
,
1523 overlaps_b
, overlaps_a
, last_conflicts
);
1525 else if (evolution_function_is_affine_p (chrec_a
)
1526 && evolution_function_is_affine_p (chrec_b
))
1527 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
1528 overlaps_a
, overlaps_b
, last_conflicts
);
1531 *overlaps_a
= chrec_dont_know
;
1532 *overlaps_b
= chrec_dont_know
;
1533 *last_conflicts
= chrec_dont_know
;
1536 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1537 fprintf (dump_file
, ")\n");
1540 /* Return true when the evolution steps of an affine CHREC divide the
1544 chrec_steps_divide_constant_p (tree chrec
,
1547 switch (TREE_CODE (chrec
))
1549 case POLYNOMIAL_CHREC
:
1550 return (tree_fold_divides_p (integer_type_node
, CHREC_RIGHT (chrec
), cst
)
1551 && chrec_steps_divide_constant_p (CHREC_LEFT (chrec
), cst
));
1554 /* On the initial condition, return true. */
1559 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
1560 *OVERLAPS_B are initialized to the functions that describe the
1561 relation between the elements accessed twice by CHREC_A and
1562 CHREC_B. For k >= 0, the following property is verified:
1564 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1567 analyze_miv_subscript (tree chrec_a
,
1571 tree
*last_conflicts
)
1573 /* FIXME: This is a MIV subscript, not yet handled.
1574 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
1577 In the SIV test we had to solve a Diophantine equation with two
1578 variables. In the MIV case we have to solve a Diophantine
1579 equation with 2*n variables (if the subscript uses n IVs).
1583 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1584 fprintf (dump_file
, "(analyze_miv_subscript \n");
1586 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
1588 if (chrec_zerop (difference
))
1590 /* Access functions are the same: all the elements are accessed
1591 in the same order. */
1592 *overlaps_a
= integer_zero_node
;
1593 *overlaps_b
= integer_zero_node
;
1594 *last_conflicts
= number_of_iterations_in_loop
1595 (current_loops
->parray
[CHREC_VARIABLE (chrec_a
)]);
1598 else if (evolution_function_is_constant_p (difference
)
1599 /* For the moment, the following is verified:
1600 evolution_function_is_affine_multivariate_p (chrec_a) */
1601 && !chrec_steps_divide_constant_p (chrec_a
, difference
))
1603 /* testsuite/.../ssa-chrec-33.c
1604 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
1606 The difference is 1, and the evolution steps are equal to 2,
1607 consequently there are no overlapping elements. */
1608 *overlaps_a
= chrec_known
;
1609 *overlaps_b
= chrec_known
;
1610 *last_conflicts
= integer_zero_node
;
1613 else if (evolution_function_is_affine_multivariate_p (chrec_a
)
1614 && evolution_function_is_affine_multivariate_p (chrec_b
))
1616 /* testsuite/.../ssa-chrec-35.c
1617 {0, +, 1}_2 vs. {0, +, 1}_3
1618 the overlapping elements are respectively located at iterations:
1619 {0, +, 1}_x and {0, +, 1}_x,
1620 in other words, we have the equality:
1621 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
1624 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
1625 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
1627 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
1628 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
1630 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
1631 overlaps_a
, overlaps_b
, last_conflicts
);
1636 /* When the analysis is too difficult, answer "don't know". */
1637 *overlaps_a
= chrec_dont_know
;
1638 *overlaps_b
= chrec_dont_know
;
1639 *last_conflicts
= chrec_dont_know
;
1642 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1643 fprintf (dump_file
, ")\n");
1646 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
1647 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
1648 two functions that describe the iterations that contain conflicting
1651 Remark: For an integer k >= 0, the following equality is true:
1653 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
1657 analyze_overlapping_iterations (tree chrec_a
,
1659 tree
*overlap_iterations_a
,
1660 tree
*overlap_iterations_b
,
1661 tree
*last_conflicts
)
1663 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1665 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
1666 fprintf (dump_file
, " (chrec_a = ");
1667 print_generic_expr (dump_file
, chrec_a
, 0);
1668 fprintf (dump_file
, ")\n chrec_b = ");
1669 print_generic_expr (dump_file
, chrec_b
, 0);
1670 fprintf (dump_file
, ")\n");
1673 if (chrec_a
== NULL_TREE
1674 || chrec_b
== NULL_TREE
1675 || chrec_contains_undetermined (chrec_a
)
1676 || chrec_contains_undetermined (chrec_b
)
1677 || chrec_contains_symbols (chrec_a
)
1678 || chrec_contains_symbols (chrec_b
))
1680 *overlap_iterations_a
= chrec_dont_know
;
1681 *overlap_iterations_b
= chrec_dont_know
;
1684 else if (ziv_subscript_p (chrec_a
, chrec_b
))
1685 analyze_ziv_subscript (chrec_a
, chrec_b
,
1686 overlap_iterations_a
, overlap_iterations_b
,
1689 else if (siv_subscript_p (chrec_a
, chrec_b
))
1690 analyze_siv_subscript (chrec_a
, chrec_b
,
1691 overlap_iterations_a
, overlap_iterations_b
,
1695 analyze_miv_subscript (chrec_a
, chrec_b
,
1696 overlap_iterations_a
, overlap_iterations_b
,
1699 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1701 fprintf (dump_file
, " (overlap_iterations_a = ");
1702 print_generic_expr (dump_file
, *overlap_iterations_a
, 0);
1703 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
1704 print_generic_expr (dump_file
, *overlap_iterations_b
, 0);
1705 fprintf (dump_file
, ")\n");
1711 /* This section contains the affine functions dependences detector. */
1713 /* Computes the conflicting iterations, and initialize DDR. */
1716 subscript_dependence_tester (struct data_dependence_relation
*ddr
)
1719 struct data_reference
*dra
= DDR_A (ddr
);
1720 struct data_reference
*drb
= DDR_B (ddr
);
1721 tree last_conflicts
;
1723 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1724 fprintf (dump_file
, "(subscript_dependence_tester \n");
1726 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1728 tree overlaps_a
, overlaps_b
;
1729 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
1731 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
1732 DR_ACCESS_FN (drb
, i
),
1733 &overlaps_a
, &overlaps_b
,
1736 if (chrec_contains_undetermined (overlaps_a
)
1737 || chrec_contains_undetermined (overlaps_b
))
1739 finalize_ddr_dependent (ddr
, chrec_dont_know
);
1743 else if (overlaps_a
== chrec_known
1744 || overlaps_b
== chrec_known
)
1746 finalize_ddr_dependent (ddr
, chrec_known
);
1752 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
1753 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
1754 SUB_LAST_CONFLICT (subscript
) = last_conflicts
;
1758 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1759 fprintf (dump_file
, ")\n");
1762 /* Compute the classic per loop distance vector.
1764 DDR is the data dependence relation to build a vector from.
1765 NB_LOOPS is the total number of loops we are considering.
1766 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
1768 Return FALSE if the dependence relation is outside of the loop nest
1769 starting at FIRST_LOOP_DEPTH.
1770 Return TRUE otherwise. */
1773 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
1774 int nb_loops
, int first_loop_depth
)
1777 lambda_vector dist_v
, init_v
;
1779 dist_v
= lambda_vector_new (nb_loops
);
1780 init_v
= lambda_vector_new (nb_loops
);
1781 lambda_vector_clear (dist_v
, nb_loops
);
1782 lambda_vector_clear (init_v
, nb_loops
);
1784 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
1787 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1789 tree access_fn_a
, access_fn_b
;
1790 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
1792 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
1794 non_affine_dependence_relation (ddr
);
1798 access_fn_a
= DR_ACCESS_FN (DDR_A (ddr
), i
);
1799 access_fn_b
= DR_ACCESS_FN (DDR_B (ddr
), i
);
1801 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
1802 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
1804 int dist
, loop_nb
, loop_depth
;
1805 int loop_nb_a
= CHREC_VARIABLE (access_fn_a
);
1806 int loop_nb_b
= CHREC_VARIABLE (access_fn_b
);
1807 struct loop
*loop_a
= current_loops
->parray
[loop_nb_a
];
1808 struct loop
*loop_b
= current_loops
->parray
[loop_nb_b
];
1810 /* If the loop for either variable is at a lower depth than
1811 the first_loop's depth, then we can't possibly have a
1812 dependency at this level of the loop. */
1814 if (loop_a
->depth
< first_loop_depth
1815 || loop_b
->depth
< first_loop_depth
)
1818 if (loop_nb_a
!= loop_nb_b
1819 && !flow_loop_nested_p (loop_a
, loop_b
)
1820 && !flow_loop_nested_p (loop_b
, loop_a
))
1822 /* Example: when there are two consecutive loops,
1831 the dependence relation cannot be captured by the
1832 distance abstraction. */
1833 non_affine_dependence_relation (ddr
);
1837 /* The dependence is carried by the outermost loop. Example:
1844 In this case, the dependence is carried by loop_1. */
1845 loop_nb
= loop_nb_a
< loop_nb_b
? loop_nb_a
: loop_nb_b
;
1846 loop_depth
= current_loops
->parray
[loop_nb
]->depth
- first_loop_depth
;
1848 /* If the loop number is still greater than the number of
1849 loops we've been asked to analyze, or negative,
1850 something is borked. */
1851 gcc_assert (loop_depth
>= 0);
1852 gcc_assert (loop_depth
< nb_loops
);
1853 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
1855 non_affine_dependence_relation (ddr
);
1859 dist
= int_cst_value (SUB_DISTANCE (subscript
));
1861 /* This is the subscript coupling test.
1866 There is no dependence. */
1867 if (init_v
[loop_depth
] != 0
1868 && dist_v
[loop_depth
] != dist
)
1870 finalize_ddr_dependent (ddr
, chrec_known
);
1874 dist_v
[loop_depth
] = dist
;
1875 init_v
[loop_depth
] = 1;
1879 /* There is a distance of 1 on all the outer loops:
1881 Example: there is a dependence of distance 1 on loop_1 for the array A.
1887 struct loop
*lca
, *loop_a
, *loop_b
;
1888 struct data_reference
*a
= DDR_A (ddr
);
1889 struct data_reference
*b
= DDR_B (ddr
);
1891 loop_a
= loop_containing_stmt (DR_STMT (a
));
1892 loop_b
= loop_containing_stmt (DR_STMT (b
));
1894 /* Get the common ancestor loop. */
1895 lca
= find_common_loop (loop_a
, loop_b
);
1897 lca_depth
= lca
->depth
;
1898 lca_depth
-= first_loop_depth
;
1899 gcc_assert (lca_depth
>= 0);
1900 gcc_assert (lca_depth
< nb_loops
);
1902 /* For each outer loop where init_v is not set, the accesses are
1903 in dependence of distance 1 in the loop. */
1906 && init_v
[lca_depth
] == 0)
1907 dist_v
[lca_depth
] = 1;
1913 lca_depth
= lca
->depth
- first_loop_depth
;
1914 while (lca
->depth
!= 0)
1916 /* If we're considering just a sub-nest, then don't record
1917 any information on the outer loops. */
1921 gcc_assert (lca_depth
< nb_loops
);
1923 if (init_v
[lca_depth
] == 0)
1924 dist_v
[lca_depth
] = 1;
1926 lca_depth
= lca
->depth
- first_loop_depth
;
1932 DDR_DIST_VECT (ddr
) = dist_v
;
1933 DDR_SIZE_VECT (ddr
) = nb_loops
;
1937 /* Compute the classic per loop direction vector.
1939 DDR is the data dependence relation to build a vector from.
1940 NB_LOOPS is the total number of loops we are considering.
1941 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
1943 Return FALSE if the dependence relation is outside of the loop nest
1944 at FIRST_LOOP_DEPTH.
1945 Return TRUE otherwise. */
1948 build_classic_dir_vector (struct data_dependence_relation
*ddr
,
1949 int nb_loops
, int first_loop_depth
)
1952 lambda_vector dir_v
, init_v
;
1954 dir_v
= lambda_vector_new (nb_loops
);
1955 init_v
= lambda_vector_new (nb_loops
);
1956 lambda_vector_clear (dir_v
, nb_loops
);
1957 lambda_vector_clear (init_v
, nb_loops
);
1959 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
1962 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1964 tree access_fn_a
, access_fn_b
;
1965 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
1967 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
1969 non_affine_dependence_relation (ddr
);
1973 access_fn_a
= DR_ACCESS_FN (DDR_A (ddr
), i
);
1974 access_fn_b
= DR_ACCESS_FN (DDR_B (ddr
), i
);
1975 if (TREE_CODE (access_fn_a
) == POLYNOMIAL_CHREC
1976 && TREE_CODE (access_fn_b
) == POLYNOMIAL_CHREC
)
1978 int dist
, loop_nb
, loop_depth
;
1979 enum data_dependence_direction dir
= dir_star
;
1980 int loop_nb_a
= CHREC_VARIABLE (access_fn_a
);
1981 int loop_nb_b
= CHREC_VARIABLE (access_fn_b
);
1982 struct loop
*loop_a
= current_loops
->parray
[loop_nb_a
];
1983 struct loop
*loop_b
= current_loops
->parray
[loop_nb_b
];
1985 /* If the loop for either variable is at a lower depth than
1986 the first_loop's depth, then we can't possibly have a
1987 dependency at this level of the loop. */
1989 if (loop_a
->depth
< first_loop_depth
1990 || loop_b
->depth
< first_loop_depth
)
1993 if (loop_nb_a
!= loop_nb_b
1994 && !flow_loop_nested_p (loop_a
, loop_b
)
1995 && !flow_loop_nested_p (loop_b
, loop_a
))
1997 /* Example: when there are two consecutive loops,
2006 the dependence relation cannot be captured by the
2007 distance abstraction. */
2008 non_affine_dependence_relation (ddr
);
2012 /* The dependence is carried by the outermost loop. Example:
2019 In this case, the dependence is carried by loop_1. */
2020 loop_nb
= loop_nb_a
< loop_nb_b
? loop_nb_a
: loop_nb_b
;
2021 loop_depth
= current_loops
->parray
[loop_nb
]->depth
- first_loop_depth
;
2023 /* If the loop number is still greater than the number of
2024 loops we've been asked to analyze, or negative,
2025 something is borked. */
2026 gcc_assert (loop_depth
>= 0);
2027 gcc_assert (loop_depth
< nb_loops
);
2029 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
2031 non_affine_dependence_relation (ddr
);
2035 dist
= int_cst_value (SUB_DISTANCE (subscript
));
2044 /* This is the subscript coupling test.
2049 There is no dependence. */
2050 if (init_v
[loop_depth
] != 0
2052 && (enum data_dependence_direction
) dir_v
[loop_depth
] != dir
2053 && (enum data_dependence_direction
) dir_v
[loop_depth
] != dir_star
)
2055 finalize_ddr_dependent (ddr
, chrec_known
);
2059 dir_v
[loop_depth
] = dir
;
2060 init_v
[loop_depth
] = 1;
2064 /* There is a distance of 1 on all the outer loops:
2066 Example: there is a dependence of distance 1 on loop_1 for the array A.
2072 struct loop
*lca
, *loop_a
, *loop_b
;
2073 struct data_reference
*a
= DDR_A (ddr
);
2074 struct data_reference
*b
= DDR_B (ddr
);
2076 loop_a
= loop_containing_stmt (DR_STMT (a
));
2077 loop_b
= loop_containing_stmt (DR_STMT (b
));
2079 /* Get the common ancestor loop. */
2080 lca
= find_common_loop (loop_a
, loop_b
);
2081 lca_depth
= lca
->depth
- first_loop_depth
;
2083 gcc_assert (lca_depth
>= 0);
2084 gcc_assert (lca_depth
< nb_loops
);
2086 /* For each outer loop where init_v is not set, the accesses are
2087 in dependence of distance 1 in the loop. */
2090 && init_v
[lca_depth
] == 0)
2091 dir_v
[lca_depth
] = dir_positive
;
2096 lca_depth
= lca
->depth
- first_loop_depth
;
2097 while (lca
->depth
!= 0)
2099 /* If we're considering just a sub-nest, then don't record
2100 any information on the outer loops. */
2104 gcc_assert (lca_depth
< nb_loops
);
2106 if (init_v
[lca_depth
] == 0)
2107 dir_v
[lca_depth
] = dir_positive
;
2109 lca_depth
= lca
->depth
- first_loop_depth
;
2115 DDR_DIR_VECT (ddr
) = dir_v
;
2116 DDR_SIZE_VECT (ddr
) = nb_loops
;
2120 /* Returns true when all the access functions of A are affine or
2124 access_functions_are_affine_or_constant_p (struct data_reference
*a
)
2127 varray_type fns
= DR_ACCESS_FNS (a
);
2129 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (fns
); i
++)
2130 if (!evolution_function_is_constant_p (VARRAY_TREE (fns
, i
))
2131 && !evolution_function_is_affine_multivariate_p (VARRAY_TREE (fns
, i
)))
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 /* Compute a subset of the data dependence relation graph. Don't
2181 compute read-read relations, and avoid the computation of the
2182 opposite relation, i.e. when AB has been computed, don't compute BA.
2183 DATAREFS contains a list of data references, and the result is set
2184 in DEPENDENCE_RELATIONS. */
2187 compute_all_dependences (varray_type datarefs
,
2188 varray_type
*dependence_relations
)
2190 unsigned int i
, j
, N
;
2192 N
= VARRAY_ACTIVE_SIZE (datarefs
);
2194 for (i
= 0; i
< N
; i
++)
2195 for (j
= i
; j
< N
; j
++)
2197 struct data_reference
*a
, *b
;
2198 struct data_dependence_relation
*ddr
;
2200 a
= VARRAY_GENERIC_PTR (datarefs
, i
);
2201 b
= VARRAY_GENERIC_PTR (datarefs
, j
);
2202 ddr
= initialize_data_dependence_relation (a
, b
);
2204 VARRAY_PUSH_GENERIC_PTR (*dependence_relations
, ddr
);
2205 compute_affine_dependence (ddr
);
2206 compute_subscript_distance (ddr
);
2210 /* Search the data references in LOOP, and record the information into
2211 DATAREFS. Returns chrec_dont_know when failing to analyze a
2212 difficult case, returns NULL_TREE otherwise.
2214 TODO: This function should be made smarter so that it can handle address
2215 arithmetic as if they were array accesses, etc. */
2218 find_data_references_in_loop (struct loop
*loop
, varray_type
*datarefs
)
2220 bool dont_know_node_not_inserted
= true;
2221 basic_block bb
, *bbs
;
2223 block_stmt_iterator bsi
;
2225 bbs
= get_loop_body (loop
);
2227 for (i
= 0; i
< loop
->num_nodes
; i
++)
2231 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
2233 tree stmt
= bsi_stmt (bsi
);
2234 stmt_ann_t ann
= stmt_ann (stmt
);
2236 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
2240 && !V_MUST_DEF_OPS (ann
)
2241 && !V_MAY_DEF_OPS (ann
))
2244 /* In the GIMPLE representation, a modify expression
2245 contains a single load or store to memory. */
2246 if (TREE_CODE (TREE_OPERAND (stmt
, 0)) == ARRAY_REF
)
2247 VARRAY_PUSH_GENERIC_PTR
2248 (*datarefs
, analyze_array (stmt
, TREE_OPERAND (stmt
, 0),
2251 else if (TREE_CODE (TREE_OPERAND (stmt
, 1)) == ARRAY_REF
)
2252 VARRAY_PUSH_GENERIC_PTR
2253 (*datarefs
, analyze_array (stmt
, TREE_OPERAND (stmt
, 1),
2257 if (dont_know_node_not_inserted
)
2259 struct data_reference
*res
;
2260 res
= xmalloc (sizeof (struct data_reference
));
2261 DR_STMT (res
) = NULL_TREE
;
2262 DR_REF (res
) = NULL_TREE
;
2263 DR_ACCESS_FNS (res
) = NULL
;
2264 DR_BASE_NAME (res
) = NULL
;
2265 DR_IS_READ (res
) = false;
2266 VARRAY_PUSH_GENERIC_PTR (*datarefs
, res
);
2267 dont_know_node_not_inserted
= false;
2271 /* When there are no defs in the loop, the loop is parallel. */
2272 if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt
)) > 0
2273 || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt
)) > 0)
2274 bb
->loop_father
->parallel_p
= false;
2277 if (bb
->loop_father
->estimated_nb_iterations
== NULL_TREE
)
2278 compute_estimated_nb_iterations (bb
->loop_father
);
2283 return dont_know_node_not_inserted
? NULL_TREE
: chrec_dont_know
;
2288 /* This section contains all the entry points. */
2290 /* Given a loop nest LOOP, the following vectors are returned:
2291 *DATAREFS is initialized to all the array elements contained in this loop,
2292 *DEPENDENCE_RELATIONS contains the relations between the data references. */
2295 compute_data_dependences_for_loop (unsigned nb_loops
,
2297 varray_type
*datarefs
,
2298 varray_type
*dependence_relations
)
2301 varray_type allrelations
;
2303 /* If one of the data references is not computable, give up without
2304 spending time to compute other dependences. */
2305 if (find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
2307 struct data_dependence_relation
*ddr
;
2309 /* Insert a single relation into dependence_relations:
2311 ddr
= initialize_data_dependence_relation (NULL
, NULL
);
2312 VARRAY_PUSH_GENERIC_PTR (*dependence_relations
, ddr
);
2313 build_classic_dist_vector (ddr
, nb_loops
, loop
->depth
);
2314 build_classic_dir_vector (ddr
, nb_loops
, loop
->depth
);
2318 VARRAY_GENERIC_PTR_INIT (allrelations
, 1, "Data dependence relations");
2319 compute_all_dependences (*datarefs
, &allrelations
);
2321 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (allrelations
); i
++)
2323 struct data_dependence_relation
*ddr
;
2324 ddr
= VARRAY_GENERIC_PTR (allrelations
, i
);
2325 if (build_classic_dist_vector (ddr
, nb_loops
, loop
->depth
))
2327 VARRAY_PUSH_GENERIC_PTR (*dependence_relations
, ddr
);
2328 build_classic_dir_vector (ddr
, nb_loops
, loop
->depth
);
2333 /* Entry point (for testing only). Analyze all the data references
2334 and the dependence relations.
2336 The data references are computed first.
2338 A relation on these nodes is represented by a complete graph. Some
2339 of the relations could be of no interest, thus the relations can be
2342 In the following function we compute all the relations. This is
2343 just a first implementation that is here for:
2344 - for showing how to ask for the dependence relations,
2345 - for the debugging the whole dependence graph,
2346 - for the dejagnu testcases and maintenance.
2348 It is possible to ask only for a part of the graph, avoiding to
2349 compute the whole dependence graph. The computed dependences are
2350 stored in a knowledge base (KB) such that later queries don't
2351 recompute the same information. The implementation of this KB is
2352 transparent to the optimizer, and thus the KB can be changed with a
2353 more efficient implementation, or the KB could be disabled. */
2356 analyze_all_data_dependences (struct loops
*loops
)
2359 varray_type datarefs
;
2360 varray_type dependence_relations
;
2361 int nb_data_refs
= 10;
2363 VARRAY_GENERIC_PTR_INIT (datarefs
, nb_data_refs
, "datarefs");
2364 VARRAY_GENERIC_PTR_INIT (dependence_relations
,
2365 nb_data_refs
* nb_data_refs
,
2366 "dependence_relations");
2368 /* Compute DDs on the whole function. */
2369 compute_data_dependences_for_loop (loops
->num
, loops
->parray
[0],
2370 &datarefs
, &dependence_relations
);
2374 dump_data_dependence_relations (dump_file
, dependence_relations
);
2375 fprintf (dump_file
, "\n\n");
2377 if (dump_flags
& TDF_DETAILS
)
2378 dump_dist_dir_vectors (dump_file
, dependence_relations
);
2380 if (dump_flags
& TDF_STATS
)
2382 unsigned nb_top_relations
= 0;
2383 unsigned nb_bot_relations
= 0;
2384 unsigned nb_basename_differ
= 0;
2385 unsigned nb_chrec_relations
= 0;
2387 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (dependence_relations
); i
++)
2389 struct data_dependence_relation
*ddr
;
2390 ddr
= VARRAY_GENERIC_PTR (dependence_relations
, i
);
2392 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
2395 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
2397 struct data_reference
*a
= DDR_A (ddr
);
2398 struct data_reference
*b
= DDR_B (ddr
);
2401 if (DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
)
2402 || (array_base_name_differ_p (a
, b
, &differ_p
) && differ_p
))
2403 nb_basename_differ
++;
2409 nb_chrec_relations
++;
2412 gather_stats_on_scev_database ();
2416 free_dependence_relations (dependence_relations
);
2417 free_data_refs (datarefs
);
2420 /* Free the memory used by a data dependence relation DDR. */
2423 free_dependence_relation (struct data_dependence_relation
*ddr
)
2428 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_SUBSCRIPTS (ddr
))
2429 varray_clear (DDR_SUBSCRIPTS (ddr
));
2433 /* Free the memory used by the data dependence relations from
2434 DEPENDENCE_RELATIONS. */
2437 free_dependence_relations (varray_type dependence_relations
)
2440 if (dependence_relations
== NULL
)
2443 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (dependence_relations
); i
++)
2444 free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations
, i
));
2445 varray_clear (dependence_relations
);
2448 /* Free the memory used by the data references from DATAREFS. */
2451 free_data_refs (varray_type datarefs
)
2455 if (datarefs
== NULL
)
2458 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (datarefs
); i
++)
2460 struct data_reference
*dr
= (struct data_reference
*)
2461 VARRAY_GENERIC_PTR (datarefs
, i
);
2464 if (DR_ACCESS_FNS (dr
))
2465 varray_clear (DR_ACCESS_FNS (dr
));
2469 varray_clear (datarefs
);