1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* This pass walks a given loop structure searching for array
23 references. The information about the array accesses is recorded
24 in DATA_REFERENCE structures.
26 The basic test for determining the dependences is:
27 given two access functions chrec1 and chrec2 to a same array, and
28 x and y two vectors from the iteration domain, the same element of
29 the array is accessed twice at iterations x and y if and only if:
30 | chrec1 (x) == chrec2 (y).
32 The goals of this analysis are:
34 - to determine the independence: the relation between two
35 independent accesses is qualified with the chrec_known (this
36 information allows a loop parallelization),
38 - when two data references access the same data, to qualify the
39 dependence relation with classic dependence representations:
43 - loop carried level dependence
44 - polyhedron dependence
45 or with the chains of recurrences based representation,
47 - to define a knowledge base for storing the data dependeces
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"
100 /* This is the simplest data dependence test: determines whether the
101 data references A and B access the same array/region. If can't determine -
102 return false; Otherwise, return true, and DIFFER_P will record
103 the result. This utility will not be necessary when alias_sets_conflict_p
104 will be less conservative. */
107 array_base_name_differ_p (struct data_reference
*a
,
108 struct data_reference
*b
,
111 tree base_a
= DR_BASE_NAME (a
);
112 tree base_b
= DR_BASE_NAME (b
);
113 tree ta
= TREE_TYPE (base_a
);
114 tree tb
= TREE_TYPE (base_b
);
117 /** Determine if same base **/
119 /* array accesses: a[i],b[i] or pointer accesses: *a,*b. bases are a,b. */
120 if (base_a
== base_b
)
126 /* pointer based accesses - (*p)[i],(*q)[j]. bases are (*p),(*q) */
127 if (TREE_CODE (base_a
) == INDIRECT_REF
&& TREE_CODE (base_b
) == INDIRECT_REF
128 && TREE_OPERAND (base_a
, 0) == TREE_OPERAND (base_b
, 0))
134 /* record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */
135 if (TREE_CODE (base_a
) == COMPONENT_REF
&& TREE_CODE (base_b
) == COMPONENT_REF
136 && TREE_OPERAND (base_a
, 0) == TREE_OPERAND (base_b
, 0)
137 && TREE_OPERAND (base_a
, 1) == TREE_OPERAND (base_b
, 1))
144 /** Determine if different bases **/
146 /* at this point we know that base_a != base_b. However, pointer accesses
147 of the form x=(*p) and y=(*q), which bases are p and q, may still by pointing
148 to the same base. In SSAed GIMPLE p and q will be SSA_NAMES in this case.
149 Therefore, here we check if it's really two diferent 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:
157 s != t or (a != b and s and t are not unions) */
158 if (TREE_CODE (base_a
) == COMPONENT_REF
&& TREE_CODE (base_b
) == COMPONENT_REF
159 && ((TREE_CODE (TREE_OPERAND (base_a
, 0)) == VAR_DECL
160 && TREE_CODE (TREE_OPERAND (base_b
, 0)) == VAR_DECL
161 && TREE_OPERAND (base_a
, 0) != TREE_OPERAND (base_b
, 0))
162 || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a
, 0))) == RECORD_TYPE
163 && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b
, 0))) == RECORD_TYPE
164 && TREE_OPERAND (base_a
, 1) != TREE_OPERAND (base_b
, 1))))
170 /* compare a record/union access and an array access. */
171 if ((TREE_CODE (base_a
) == VAR_DECL
172 && (TREE_CODE (base_b
) == COMPONENT_REF
173 && TREE_CODE (TREE_OPERAND (base_b
, 0)) == VAR_DECL
))
174 || (TREE_CODE (base_b
) == VAR_DECL
175 && (TREE_CODE (base_a
) == COMPONENT_REF
176 && TREE_CODE (TREE_OPERAND (base_a
, 0)) == VAR_DECL
)))
182 if (!alias_sets_conflict_p (get_alias_set (base_a
), get_alias_set (base_b
)))
188 /* An insn writing through a restricted pointer is "independent" of any
189 insn reading or writing through a different pointer, in the same
192 if ((TREE_CODE (ta
) == POINTER_TYPE
&& TYPE_RESTRICT (ta
)
194 || (TREE_CODE (tb
) == POINTER_TYPE
&& TYPE_RESTRICT (tb
)
201 *differ_p
= false; /* Don't know, but be conservative. */
205 /* Returns true iff A divides B. */
208 tree_fold_divides_p (tree type
,
212 if (integer_onep (a
))
215 /* Determines whether (A == gcd (A, B)). */
217 (fold (build (MINUS_EXPR
, type
, a
, tree_fold_gcd (a
, b
))));
220 /* Bezout: Let A1 and A2 be two integers; there exist two integers U11
223 | U11 * A1 + U12 * A2 = gcd (A1, A2).
225 This function computes the greatest common divisor using the
226 Blankinship algorithm. The gcd is returned, and the coefficients
227 of the unimodular matrix U are (U11, U12, U21, U22) such that,
231 | (U11 U12) (A1) = (gcd)
234 FIXME: Use lambda_..._hermite for implementing this function.
238 tree_fold_bezout (tree a1
,
240 tree
*u11
, tree
*u12
,
241 tree
*u21
, tree
*u22
)
245 /* Initialize S with the coefficients of A. */
249 /* Initialize the U matrix */
250 *u11
= integer_one_node
;
251 *u12
= integer_zero_node
;
252 *u21
= integer_zero_node
;
253 *u22
= integer_one_node
;
255 if (integer_zerop (a1
)
256 || integer_zerop (a2
))
257 return integer_zero_node
;
259 while (!integer_zerop (s2
))
262 tree z
, zu21
, zu22
, zs2
;
264 sign
= tree_int_cst_sgn (s1
) * tree_int_cst_sgn (s2
);
265 z
= fold (build (FLOOR_DIV_EXPR
, integer_type_node
,
266 fold (build1 (ABS_EXPR
, integer_type_node
, s1
)),
267 fold (build1 (ABS_EXPR
, integer_type_node
, s2
))));
268 zu21
= fold (build (MULT_EXPR
, integer_type_node
, z
, *u21
));
269 zu22
= fold (build (MULT_EXPR
, integer_type_node
, z
, *u22
));
270 zs2
= fold (build (MULT_EXPR
, integer_type_node
, z
, s2
));
272 /* row1 -= z * row2. */
275 *u11
= fold (build (PLUS_EXPR
, integer_type_node
, *u11
, zu21
));
276 *u12
= fold (build (PLUS_EXPR
, integer_type_node
, *u12
, zu22
));
277 s1
= fold (build (PLUS_EXPR
, integer_type_node
, s1
, zs2
));
281 *u11
= fold (build (MINUS_EXPR
, integer_type_node
, *u11
, zu21
));
282 *u12
= fold (build (MINUS_EXPR
, integer_type_node
, *u12
, zu22
));
283 s1
= fold (build (MINUS_EXPR
, integer_type_node
, s1
, zs2
));
286 /* Should not happen. */
289 /* Interchange row1 and row2. */
307 if (tree_int_cst_sgn (s1
) < 0)
309 *u11
= fold (build (MULT_EXPR
, integer_type_node
, *u11
,
310 integer_minus_one_node
));
311 *u12
= fold (build (MULT_EXPR
, integer_type_node
, *u12
,
312 integer_minus_one_node
));
313 s1
= fold (build (MULT_EXPR
, integer_type_node
, s1
, integer_minus_one_node
));
321 /* Dump into FILE all the data references from DATAREFS. */
324 dump_data_references (FILE *file
,
325 varray_type datarefs
)
329 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (datarefs
); i
++)
330 dump_data_reference (file
, VARRAY_GENERIC_PTR (datarefs
, i
));
333 /* Dump into FILE all the dependence relations from DDR. */
336 dump_data_dependence_relations (FILE *file
,
341 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ddr
); i
++)
342 dump_data_dependence_relation (file
, VARRAY_GENERIC_PTR (ddr
, i
));
345 /* Dump function for a DATA_REFERENCE structure. */
348 dump_data_reference (FILE *outf
,
349 struct data_reference
*dr
)
353 fprintf (outf
, "(Data Ref: \n stmt: ");
354 print_generic_stmt (outf
, DR_STMT (dr
), 0);
355 fprintf (outf
, " ref: ");
356 print_generic_stmt (outf
, DR_REF (dr
), 0);
357 fprintf (outf
, " base_name: ");
358 print_generic_stmt (outf
, DR_BASE_NAME (dr
), 0);
360 for (i
= 0; i
< DR_NUM_DIMENSIONS (dr
); i
++)
362 fprintf (outf
, " Access function %d: ", i
);
363 print_generic_stmt (outf
, DR_ACCESS_FN (dr
, i
), 0);
365 fprintf (outf
, ")\n");
368 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
371 dump_data_dependence_relation (FILE *outf
,
372 struct data_dependence_relation
*ddr
)
375 struct data_reference
*dra
, *drb
;
381 fprintf (outf
, "(Data Dep:");
383 fprintf (outf
, "(Data Dep:");
385 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
386 fprintf (outf
, " (don't know)\n");
388 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
389 fprintf (outf
, " (no dependence)\n");
393 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
396 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
398 fprintf (outf
, "\n (subscript %d:\n", i
);
399 fprintf (outf
, " access_fn_A: ");
400 print_generic_stmt (outf
, DR_ACCESS_FN (dra
, i
), 0);
401 fprintf (outf
, " access_fn_B: ");
402 print_generic_stmt (outf
, DR_ACCESS_FN (drb
, i
), 0);
404 chrec
= SUB_CONFLICTS_IN_A (subscript
);
405 fprintf (outf
, " iterations_that_access_an_element_twice_in_A: ");
406 print_generic_stmt (outf
, chrec
, 0);
407 if (chrec
== chrec_known
)
408 fprintf (outf
, " (no dependence)\n");
409 else if (chrec_contains_undetermined (chrec
))
410 fprintf (outf
, " (don't know)\n");
413 tree last_iteration
= SUB_LAST_CONFLICT_IN_A (subscript
);
414 fprintf (outf
, " last_iteration_that_access_an_element_twice_in_A: ");
415 print_generic_stmt (outf
, last_iteration
, 0);
418 chrec
= SUB_CONFLICTS_IN_B (subscript
);
419 fprintf (outf
, " iterations_that_access_an_element_twice_in_B: ");
420 print_generic_stmt (outf
, chrec
, 0);
421 if (chrec
== chrec_known
)
422 fprintf (outf
, " (no dependence)\n");
423 else if (chrec_contains_undetermined (chrec
))
424 fprintf (outf
, " (don't know)\n");
427 tree last_iteration
= SUB_LAST_CONFLICT_IN_B (subscript
);
428 fprintf (outf
, " last_iteration_that_access_an_element_twice_in_B: ");
429 print_generic_stmt (outf
, last_iteration
, 0);
432 fprintf (outf
, " )\n");
435 fprintf (outf
, " (Distance Vector: \n");
436 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
438 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
441 print_generic_stmt (outf
, SUB_DISTANCE (subscript
), 0);
442 fprintf (outf
, ")\n");
444 fprintf (outf
, " )\n");
447 fprintf (outf
, ")\n");
452 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
455 dump_data_dependence_direction (FILE *file
,
456 enum data_dependence_direction dir
)
472 case dir_positive_or_negative
:
473 fprintf (file
, "+-");
476 case dir_positive_or_equal
:
477 fprintf (file
, "+=");
480 case dir_negative_or_equal
:
481 fprintf (file
, "-=");
495 /* Given an ARRAY_REF node REF, records its access functions.
496 Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
497 ie. the constant "3", then recursively call the function on opnd0,
498 ie. the ARRAY_REF "A[i]". The function returns the base name:
502 analyze_array_indexes (struct loop
*loop
,
503 varray_type access_fns
,
509 opnd0
= TREE_OPERAND (ref
, 0);
510 opnd1
= TREE_OPERAND (ref
, 1);
512 /* The detection of the evolution function for this data access is
513 postponed until the dependence test. This lazy strategy avoids
514 the computation of access functions that are of no interest for
516 access_fn
= instantiate_parameters
517 (loop
, analyze_scalar_evolution (loop
, opnd1
));
519 VARRAY_PUSH_TREE (access_fns
, access_fn
);
521 /* Recursively record other array access functions. */
522 if (TREE_CODE (opnd0
) == ARRAY_REF
)
523 return analyze_array_indexes (loop
, access_fns
, opnd0
);
525 /* Return the base name of the data access. */
530 /* For a data reference REF contained in the statemet STMT, initialize
531 a DATA_REFERENCE structure, and return it. IS_READ flag has to be
532 set to true when REF is in the right hand side of an
535 struct data_reference
*
536 analyze_array (tree stmt
, tree ref
, bool is_read
)
538 struct data_reference
*res
;
540 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
542 fprintf (dump_file
, "(analyze_array \n");
543 fprintf (dump_file
, " (ref = ");
544 print_generic_stmt (dump_file
, ref
, 0);
545 fprintf (dump_file
, ")\n");
548 res
= xmalloc (sizeof (struct data_reference
));
550 DR_STMT (res
) = stmt
;
552 VARRAY_TREE_INIT (DR_ACCESS_FNS (res
), 3, "access_fns");
553 DR_BASE_NAME (res
) = analyze_array_indexes
554 (loop_containing_stmt (stmt
), DR_ACCESS_FNS (res
), ref
);
555 DR_IS_READ (res
) = is_read
;
557 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
558 fprintf (dump_file
, ")\n");
563 /* For a data reference REF contained in the statemet STMT, initialize
564 a DATA_REFERENCE structure, and return it. */
566 struct data_reference
*
567 init_data_ref (tree stmt
,
573 struct data_reference
*res
;
575 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
577 fprintf (dump_file
, "(init_data_ref \n");
578 fprintf (dump_file
, " (ref = ");
579 print_generic_stmt (dump_file
, ref
, 0);
580 fprintf (dump_file
, ")\n");
583 res
= xmalloc (sizeof (struct data_reference
));
585 DR_STMT (res
) = stmt
;
587 VARRAY_TREE_INIT (DR_ACCESS_FNS (res
), 5, "access_fns");
588 DR_BASE_NAME (res
) = base
;
589 VARRAY_PUSH_TREE (DR_ACCESS_FNS (res
), access_fn
);
590 DR_IS_READ (res
) = is_read
;
592 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
593 fprintf (dump_file
, ")\n");
600 /* When there exists a dependence relation, determine its distance
604 compute_distance_vector (struct data_dependence_relation
*ddr
)
606 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
610 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
612 tree conflicts_a
, conflicts_b
, difference
;
613 struct subscript
*subscript
;
615 subscript
= DDR_SUBSCRIPT (ddr
, i
);
616 conflicts_a
= SUB_CONFLICTS_IN_A (subscript
);
617 conflicts_b
= SUB_CONFLICTS_IN_B (subscript
);
618 difference
= chrec_fold_minus
619 (integer_type_node
, conflicts_b
, conflicts_a
);
621 if (evolution_function_is_constant_p (difference
))
622 SUB_DISTANCE (subscript
) = difference
;
625 SUB_DISTANCE (subscript
) = chrec_dont_know
;
630 /* Initialize a ddr. */
632 struct data_dependence_relation
*
633 initialize_data_dependence_relation (struct data_reference
*a
,
634 struct data_reference
*b
)
636 struct data_dependence_relation
*res
;
639 res
= xmalloc (sizeof (struct data_dependence_relation
));
643 if (a
== NULL
|| b
== NULL
644 || DR_BASE_NAME (a
) == NULL_TREE
645 || DR_BASE_NAME (b
) == NULL_TREE
)
646 DDR_ARE_DEPENDENT (res
) = chrec_dont_know
;
648 /* When the dimensions of A and B differ, we directly initialize
649 the relation to "there is no dependence": chrec_known. */
650 else if (DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
)
651 || (array_base_name_differ_p (a
, b
, &differ_p
) && differ_p
))
652 DDR_ARE_DEPENDENT (res
) = chrec_known
;
657 DDR_ARE_DEPENDENT (res
) = NULL_TREE
;
658 DDR_SUBSCRIPTS_VECTOR_INIT (res
, DR_NUM_DIMENSIONS (a
));
660 for (i
= 0; i
< DR_NUM_DIMENSIONS (a
); i
++)
662 struct subscript
*subscript
;
664 subscript
= xmalloc (sizeof (struct subscript
));
665 SUB_CONFLICTS_IN_A (subscript
) = chrec_dont_know
;
666 SUB_CONFLICTS_IN_B (subscript
) = chrec_dont_know
;
667 SUB_LAST_CONFLICT_IN_A (subscript
) = chrec_dont_know
;
668 SUB_LAST_CONFLICT_IN_B (subscript
) = chrec_dont_know
;
669 SUB_DISTANCE (subscript
) = chrec_dont_know
;
670 VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res
), subscript
);
677 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
681 finalize_ddr_dependent (struct data_dependence_relation
*ddr
,
684 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
686 fprintf (dump_file
, "(dependence classified: ");
687 print_generic_expr (dump_file
, chrec
, 0);
688 fprintf (dump_file
, ")\n");
691 DDR_ARE_DEPENDENT (ddr
) = chrec
;
692 varray_clear (DDR_SUBSCRIPTS (ddr
));
697 /* This section contains the classic Banerjee tests. */
699 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
700 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
703 ziv_subscript_p (tree chrec_a
,
706 return (evolution_function_is_constant_p (chrec_a
)
707 && evolution_function_is_constant_p (chrec_b
));
710 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
711 variable, i.e., if the SIV (Single Index Variable) test is true. */
714 siv_subscript_p (tree chrec_a
,
717 if ((evolution_function_is_constant_p (chrec_a
)
718 && evolution_function_is_univariate_p (chrec_b
))
719 || (evolution_function_is_constant_p (chrec_b
)
720 && evolution_function_is_univariate_p (chrec_a
)))
723 if (evolution_function_is_univariate_p (chrec_a
)
724 && evolution_function_is_univariate_p (chrec_b
))
726 switch (TREE_CODE (chrec_a
))
728 case POLYNOMIAL_CHREC
:
729 switch (TREE_CODE (chrec_b
))
731 case POLYNOMIAL_CHREC
:
732 if (CHREC_VARIABLE (chrec_a
) != CHREC_VARIABLE (chrec_b
))
747 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
748 *OVERLAPS_B are initialized to the functions that describe the
749 relation between the elements accessed twice by CHREC_A and
750 CHREC_B. For k >= 0, the following property is verified:
752 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
755 analyze_ziv_subscript (tree chrec_a
,
762 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
763 fprintf (dump_file
, "(analyze_ziv_subscript \n");
765 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
767 switch (TREE_CODE (difference
))
770 if (integer_zerop (difference
))
772 /* The difference is equal to zero: the accessed index
773 overlaps for each iteration in the loop. */
774 *overlaps_a
= integer_zero_node
;
775 *overlaps_b
= integer_zero_node
;
779 /* The accesses do not overlap. */
780 *overlaps_a
= chrec_known
;
781 *overlaps_b
= chrec_known
;
786 /* We're not sure whether the indexes overlap. For the moment,
787 conservatively answer "don't know". */
788 *overlaps_a
= chrec_dont_know
;
789 *overlaps_b
= chrec_dont_know
;
793 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
794 fprintf (dump_file
, ")\n");
797 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
798 constant, and CHREC_B is an affine function. *OVERLAPS_A and
799 *OVERLAPS_B are initialized to the functions that describe the
800 relation between the elements accessed twice by CHREC_A and
801 CHREC_B. For k >= 0, the following property is verified:
803 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
806 analyze_siv_subscript_cst_affine (tree chrec_a
,
811 bool value0
, value1
, value2
;
812 tree difference
= chrec_fold_minus
813 (integer_type_node
, CHREC_LEFT (chrec_b
), chrec_a
);
815 if (!chrec_is_positive (initial_condition (difference
), &value0
))
817 *overlaps_a
= chrec_dont_know
;
818 *overlaps_b
= chrec_dont_know
;
825 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value1
))
827 *overlaps_a
= chrec_dont_know
;
828 *overlaps_b
= chrec_dont_know
;
840 if (tree_fold_divides_p
841 (integer_type_node
, CHREC_RIGHT (chrec_b
), difference
))
843 *overlaps_a
= integer_zero_node
;
845 (build (EXACT_DIV_EXPR
, integer_type_node
,
846 fold (build1 (ABS_EXPR
, integer_type_node
, difference
)),
847 CHREC_RIGHT (chrec_b
)));
851 /* When the step does not divides the difference, there are
855 *overlaps_a
= chrec_known
;
856 *overlaps_b
= chrec_known
;
865 chrec_b = {10, +, -1}
867 In this case, chrec_a will not overlap with chrec_b. */
868 *overlaps_a
= chrec_known
;
869 *overlaps_b
= chrec_known
;
876 if (!chrec_is_positive (CHREC_RIGHT (chrec_b
), &value2
))
878 *overlaps_a
= chrec_dont_know
;
879 *overlaps_b
= chrec_dont_know
;
888 chrec_b = {10, +, -1}
890 if (tree_fold_divides_p
891 (integer_type_node
, CHREC_RIGHT (chrec_b
), difference
))
893 *overlaps_a
= integer_zero_node
;
895 (build (EXACT_DIV_EXPR
, integer_type_node
, difference
,
896 CHREC_RIGHT (chrec_b
)));
900 /* When the step does not divides the difference, there
904 *overlaps_a
= chrec_known
;
905 *overlaps_b
= chrec_known
;
915 In this case, chrec_a will not overlap with chrec_b. */
916 *overlaps_a
= chrec_known
;
917 *overlaps_b
= chrec_known
;
925 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is an
926 affine function, and CHREC_B is a constant. *OVERLAPS_A and
927 *OVERLAPS_B are initialized to the functions that describe the
928 relation between the elements accessed twice by CHREC_A and
929 CHREC_B. For k >= 0, the following property is verified:
931 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
934 analyze_siv_subscript_affine_cst (tree chrec_a
,
939 analyze_siv_subscript_cst_affine (chrec_b
, chrec_a
, overlaps_b
, overlaps_a
);
942 /* Determines the overlapping elements due to accesses CHREC_A and
943 CHREC_B, that are affine functions. This is a part of the
944 subscript analyzer. */
947 analyze_subscript_affine_affine (tree chrec_a
,
952 tree left_a
, left_b
, right_a
, right_b
;
954 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
955 fprintf (dump_file
, "(analyze_subscript_affine_affine \n");
957 /* For determining the initial intersection, we have to solve a
958 Diophantine equation. This is the most time consuming part.
960 For answering to the question: "Is there a dependence?" we have
961 to prove that there exists a solution to the Diophantine
962 equation, and that the solution is in the iteration domain,
963 ie. the solution is positive or zero, and that the solution
964 happens before the upper bound loop.nb_iterations. Otherwise
965 there is no dependence. This function outputs a description of
966 the iterations that hold the intersections. */
968 left_a
= CHREC_LEFT (chrec_a
);
969 left_b
= CHREC_LEFT (chrec_b
);
970 right_a
= CHREC_RIGHT (chrec_a
);
971 right_b
= CHREC_RIGHT (chrec_b
);
973 if (chrec_zerop (chrec_fold_minus (integer_type_node
, left_a
, left_b
)))
975 /* The first element accessed twice is on the first
977 *overlaps_a
= build_polynomial_chrec
978 (CHREC_VARIABLE (chrec_b
), integer_zero_node
, integer_one_node
);
979 *overlaps_b
= build_polynomial_chrec
980 (CHREC_VARIABLE (chrec_a
), integer_zero_node
, integer_one_node
);
983 else if (TREE_CODE (left_a
) == INTEGER_CST
984 && TREE_CODE (left_b
) == INTEGER_CST
985 && TREE_CODE (right_a
) == INTEGER_CST
986 && TREE_CODE (right_b
) == INTEGER_CST
988 /* Both functions should have the same evolution sign. */
989 && ((tree_int_cst_sgn (right_a
) > 0
990 && tree_int_cst_sgn (right_b
) > 0)
991 || (tree_int_cst_sgn (right_a
) < 0
992 && tree_int_cst_sgn (right_b
) < 0)))
994 /* Here we have to solve the Diophantine equation. Reference
995 book: "Loop Transformations for Restructuring Compilers - The
996 Foundations" by Utpal Banerjee, pages 59-80.
998 ALPHA * X0 = BETA * Y0 + GAMMA.
1003 GAMMA = LEFT_B - LEFT_A
1004 CHREC_A = {LEFT_A, +, RIGHT_A}
1005 CHREC_B = {LEFT_B, +, RIGHT_B}
1007 The Diophantine equation has a solution if and only if gcd
1008 (ALPHA, BETA) divides GAMMA. This is commonly known under
1009 the name of the "gcd-test".
1011 tree alpha
, beta
, gamma
;
1013 tree gcd_alpha_beta
;
1014 tree u11
, u12
, u21
, u22
;
1016 /* Both alpha and beta have to be integer_type_node. The gcd
1017 function does not work correctly otherwise. */
1018 alpha
= copy_node (right_a
);
1019 beta
= copy_node (right_b
);
1020 la
= copy_node (left_a
);
1021 lb
= copy_node (left_b
);
1022 TREE_TYPE (alpha
) = integer_type_node
;
1023 TREE_TYPE (beta
) = integer_type_node
;
1024 TREE_TYPE (la
) = integer_type_node
;
1025 TREE_TYPE (lb
) = integer_type_node
;
1027 gamma
= fold (build (MINUS_EXPR
, integer_type_node
, lb
, la
));
1029 /* FIXME: Use lambda_*_Hermite for implementing Bezout. */
1030 gcd_alpha_beta
= tree_fold_bezout
1032 fold (build (MULT_EXPR
, integer_type_node
, beta
,
1033 integer_minus_one_node
)),
1037 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1039 fprintf (dump_file
, " (alpha = ");
1040 print_generic_expr (dump_file
, alpha
, 0);
1041 fprintf (dump_file
, ")\n (beta = ");
1042 print_generic_expr (dump_file
, beta
, 0);
1043 fprintf (dump_file
, ")\n (gamma = ");
1044 print_generic_expr (dump_file
, gamma
, 0);
1045 fprintf (dump_file
, ")\n (gcd_alpha_beta = ");
1046 print_generic_expr (dump_file
, gcd_alpha_beta
, 0);
1047 fprintf (dump_file
, ")\n");
1050 /* The classic "gcd-test". */
1051 if (!tree_fold_divides_p (integer_type_node
, gcd_alpha_beta
, gamma
))
1053 /* The "gcd-test" has determined that there is no integer
1054 solution, ie. there is no dependence. */
1055 *overlaps_a
= chrec_known
;
1056 *overlaps_b
= chrec_known
;
1061 /* The solutions are given by:
1063 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [X]
1066 For a given integer t. Using the following variables,
1068 | i0 = u11 * gamma / gcd_alpha_beta
1069 | j0 = u12 * gamma / gcd_alpha_beta
1076 | y = j0 + j1 * t. */
1078 tree i0
, j0
, i1
, j1
, t
;
1081 /* X0 and Y0 are the first iterations for which there is a
1082 dependence. X0, Y0 are two solutions of the Diophantine
1083 equation: chrec_a (X0) = chrec_b (Y0). */
1086 /* Exact div because in this case gcd_alpha_beta divides
1088 gamma_gcd
= fold (build (EXACT_DIV_EXPR
, integer_type_node
, gamma
,
1090 i0
= fold (build (MULT_EXPR
, integer_type_node
, u11
, gamma_gcd
));
1091 j0
= fold (build (MULT_EXPR
, integer_type_node
, u12
, gamma_gcd
));
1095 if ((tree_int_cst_sgn (i1
) == 0
1096 && tree_int_cst_sgn (i0
) < 0)
1097 || (tree_int_cst_sgn (j1
) == 0
1098 && tree_int_cst_sgn (j0
) < 0))
1100 /* There is no solution.
1101 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
1102 falls in here, but for the moment we don't look at the
1103 upper bound of the iteration domain. */
1104 *overlaps_a
= chrec_known
;
1105 *overlaps_b
= chrec_known
;
1110 if (tree_int_cst_sgn (i1
) > 0)
1113 (build (CEIL_DIV_EXPR
, integer_type_node
,
1114 fold (build (MULT_EXPR
, integer_type_node
, i0
,
1115 integer_minus_one_node
)),
1118 if (tree_int_cst_sgn (j1
) > 0)
1121 (build (MAX_EXPR
, integer_type_node
, t
,
1122 fold (build (CEIL_DIV_EXPR
, integer_type_node
,
1125 integer_type_node
, j0
,
1126 integer_minus_one_node
)),
1130 (build (PLUS_EXPR
, integer_type_node
, i0
,
1132 (MULT_EXPR
, integer_type_node
, i1
, t
))));
1134 (build (PLUS_EXPR
, integer_type_node
, j0
,
1136 (MULT_EXPR
, integer_type_node
, j1
, t
))));
1138 *overlaps_a
= build_polynomial_chrec
1139 (CHREC_VARIABLE (chrec_b
), x0
, u21
);
1140 *overlaps_b
= build_polynomial_chrec
1141 (CHREC_VARIABLE (chrec_a
), y0
, u22
);
1145 /* FIXME: For the moment, the upper bound of the
1146 iteration domain for j is not checked. */
1147 *overlaps_a
= chrec_dont_know
;
1148 *overlaps_b
= chrec_dont_know
;
1154 /* FIXME: For the moment, the upper bound of the
1155 iteration domain for i is not checked. */
1156 *overlaps_a
= chrec_dont_know
;
1157 *overlaps_b
= chrec_dont_know
;
1165 /* For the moment, "don't know". */
1166 *overlaps_a
= chrec_dont_know
;
1167 *overlaps_b
= chrec_dont_know
;
1170 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1172 fprintf (dump_file
, " (overlaps_a = ");
1173 print_generic_expr (dump_file
, *overlaps_a
, 0);
1174 fprintf (dump_file
, ")\n (overlaps_b = ");
1175 print_generic_expr (dump_file
, *overlaps_b
, 0);
1176 fprintf (dump_file
, ")\n");
1179 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1180 fprintf (dump_file
, ")\n");
1183 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
1184 *OVERLAPS_B are initialized to the functions that describe the
1185 relation between the elements accessed twice by CHREC_A and
1186 CHREC_B. For k >= 0, the following property is verified:
1188 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1191 analyze_siv_subscript (tree chrec_a
,
1196 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1197 fprintf (dump_file
, "(analyze_siv_subscript \n");
1199 if (evolution_function_is_constant_p (chrec_a
)
1200 && evolution_function_is_affine_p (chrec_b
))
1201 analyze_siv_subscript_cst_affine (chrec_a
, chrec_b
,
1202 overlaps_a
, overlaps_b
);
1204 else if (evolution_function_is_affine_p (chrec_a
)
1205 && evolution_function_is_constant_p (chrec_b
))
1206 analyze_siv_subscript_affine_cst (chrec_a
, chrec_b
,
1207 overlaps_a
, overlaps_b
);
1209 else if (evolution_function_is_affine_p (chrec_a
)
1210 && evolution_function_is_affine_p (chrec_b
)
1211 && (CHREC_VARIABLE (chrec_a
) == CHREC_VARIABLE (chrec_b
)))
1212 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
1213 overlaps_a
, overlaps_b
);
1216 *overlaps_a
= chrec_dont_know
;
1217 *overlaps_b
= chrec_dont_know
;
1220 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1221 fprintf (dump_file
, ")\n");
1224 /* Return true when the evolution steps of an affine CHREC divide the
1228 chrec_steps_divide_constant_p (tree chrec
,
1231 switch (TREE_CODE (chrec
))
1233 case POLYNOMIAL_CHREC
:
1234 return (tree_fold_divides_p (integer_type_node
, CHREC_RIGHT (chrec
), cst
)
1235 && chrec_steps_divide_constant_p (CHREC_LEFT (chrec
), cst
));
1238 /* On the initial condition, return true. */
1243 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
1244 *OVERLAPS_B are initialized to the functions that describe the
1245 relation between the elements accessed twice by CHREC_A and
1246 CHREC_B. For k >= 0, the following property is verified:
1248 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1251 analyze_miv_subscript (tree chrec_a
,
1256 /* FIXME: This is a MIV subscript, not yet handled.
1257 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
1260 In the SIV test we had to solve a Diophantine equation with two
1261 variables. In the MIV case we have to solve a Diophantine
1262 equation with 2*n variables (if the subscript uses n IVs).
1266 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1267 fprintf (dump_file
, "(analyze_miv_subscript \n");
1269 difference
= chrec_fold_minus (integer_type_node
, chrec_a
, chrec_b
);
1271 if (chrec_zerop (difference
))
1273 /* Access functions are the same: all the elements are accessed
1274 in the same order. */
1275 *overlaps_a
= integer_zero_node
;
1276 *overlaps_b
= integer_zero_node
;
1279 else if (evolution_function_is_constant_p (difference
)
1280 /* For the moment, the following is verified:
1281 evolution_function_is_affine_multivariate_p (chrec_a) */
1282 && !chrec_steps_divide_constant_p (chrec_a
, difference
))
1284 /* testsuite/.../ssa-chrec-33.c
1285 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
1287 The difference is 1, and the evolution steps are equal to 2,
1288 consequently there are no overlapping elements. */
1289 *overlaps_a
= chrec_known
;
1290 *overlaps_b
= chrec_known
;
1293 else if (evolution_function_is_univariate_p (chrec_a
)
1294 && evolution_function_is_univariate_p (chrec_b
))
1296 /* testsuite/.../ssa-chrec-35.c
1297 {0, +, 1}_2 vs. {0, +, 1}_3
1298 the overlapping elements are respectively located at iterations:
1299 {0, +, 1}_3 and {0, +, 1}_2.
1301 if (evolution_function_is_affine_p (chrec_a
)
1302 && evolution_function_is_affine_p (chrec_b
))
1303 analyze_subscript_affine_affine (chrec_a
, chrec_b
,
1304 overlaps_a
, overlaps_b
);
1307 *overlaps_a
= chrec_dont_know
;
1308 *overlaps_b
= chrec_dont_know
;
1314 /* When the analysis is too difficult, answer "don't know". */
1315 *overlaps_a
= chrec_dont_know
;
1316 *overlaps_b
= chrec_dont_know
;
1319 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1320 fprintf (dump_file
, ")\n");
1323 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
1324 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
1325 two functions that describe the iterations that contain conflicting
1328 Remark: For an integer k >= 0, the following equality is true:
1330 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
1334 analyze_overlapping_iterations (tree chrec_a
,
1336 tree
*overlap_iterations_a
,
1337 tree
*overlap_iterations_b
)
1339 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1341 fprintf (dump_file
, "(analyze_overlapping_iterations \n");
1342 fprintf (dump_file
, " (chrec_a = ");
1343 print_generic_expr (dump_file
, chrec_a
, 0);
1344 fprintf (dump_file
, ")\n chrec_b = ");
1345 print_generic_expr (dump_file
, chrec_b
, 0);
1346 fprintf (dump_file
, ")\n");
1349 if (chrec_a
== NULL_TREE
1350 || chrec_b
== NULL_TREE
1351 || chrec_contains_undetermined (chrec_a
)
1352 || chrec_contains_undetermined (chrec_b
)
1353 || chrec_contains_symbols (chrec_a
)
1354 || chrec_contains_symbols (chrec_b
))
1356 *overlap_iterations_a
= chrec_dont_know
;
1357 *overlap_iterations_b
= chrec_dont_know
;
1360 else if (ziv_subscript_p (chrec_a
, chrec_b
))
1361 analyze_ziv_subscript (chrec_a
, chrec_b
,
1362 overlap_iterations_a
, overlap_iterations_b
);
1364 else if (siv_subscript_p (chrec_a
, chrec_b
))
1365 analyze_siv_subscript (chrec_a
, chrec_b
,
1366 overlap_iterations_a
, overlap_iterations_b
);
1369 analyze_miv_subscript (chrec_a
, chrec_b
,
1370 overlap_iterations_a
, overlap_iterations_b
);
1372 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1374 fprintf (dump_file
, " (overlap_iterations_a = ");
1375 print_generic_expr (dump_file
, *overlap_iterations_a
, 0);
1376 fprintf (dump_file
, ")\n (overlap_iterations_b = ");
1377 print_generic_expr (dump_file
, *overlap_iterations_b
, 0);
1378 fprintf (dump_file
, ")\n");
1384 /* This section contains the affine functions dependences detector. */
1386 /* Computes the conflicting iterations, and initialize DDR. */
1389 subscript_dependence_tester (struct data_dependence_relation
*ddr
)
1392 struct data_reference
*dra
= DDR_A (ddr
);
1393 struct data_reference
*drb
= DDR_B (ddr
);
1395 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1396 fprintf (dump_file
, "(subscript_dependence_tester \n");
1398 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1400 tree overlaps_a
, overlaps_b
;
1401 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
1403 analyze_overlapping_iterations (DR_ACCESS_FN (dra
, i
),
1404 DR_ACCESS_FN (drb
, i
),
1405 &overlaps_a
, &overlaps_b
);
1407 if (chrec_contains_undetermined (overlaps_a
)
1408 || chrec_contains_undetermined (overlaps_b
))
1410 finalize_ddr_dependent (ddr
, chrec_dont_know
);
1414 else if (overlaps_a
== chrec_known
1415 || overlaps_b
== chrec_known
)
1417 finalize_ddr_dependent (ddr
, chrec_known
);
1423 SUB_CONFLICTS_IN_A (subscript
) = overlaps_a
;
1424 SUB_CONFLICTS_IN_B (subscript
) = overlaps_b
;
1428 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1429 fprintf (dump_file
, ")\n");
1432 /* Compute the classic per loop distance vector.
1434 DDR is the data dependence relation to build a vector from.
1435 NB_LOOPS is the total number of loops we are considering.
1436 FIRST_LOOP is the loop->num of the first loop. */
1439 build_classic_dist_vector (struct data_dependence_relation
*ddr
,
1440 int nb_loops
, unsigned int first_loop
)
1443 lambda_vector dist_v
, init_v
;
1445 dist_v
= lambda_vector_new (nb_loops
);
1446 init_v
= lambda_vector_new (nb_loops
);
1447 lambda_vector_clear (dist_v
, nb_loops
);
1448 lambda_vector_clear (init_v
, nb_loops
);
1450 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
1453 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1455 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
1457 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
1460 if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript
)) == POLYNOMIAL_CHREC
)
1464 loop_nb
= CHREC_VARIABLE (SUB_CONFLICTS_IN_A (subscript
));
1465 loop_nb
-= first_loop
;
1466 /* If the loop number is still greater than the number of
1467 loops we've been asked to analyze, or negative,
1468 something is borked. */
1469 if (loop_nb
< 0 || loop_nb
>= nb_loops
)
1471 dist
= int_cst_value (SUB_DISTANCE (subscript
));
1473 /* This is the subscript coupling test.
1478 There is no dependence. */
1479 if (init_v
[loop_nb
] != 0
1480 && dist_v
[loop_nb
] != dist
)
1482 finalize_ddr_dependent (ddr
, chrec_known
);
1486 dist_v
[loop_nb
] = dist
;
1487 init_v
[loop_nb
] = 1;
1491 /* There is a distance of 1 on all the outer loops:
1493 Example: there is a dependence of distance 1 on loop_1 for the array A.
1499 struct loop
*lca
, *loop_a
, *loop_b
;
1500 struct data_reference
*a
= DDR_A (ddr
);
1501 struct data_reference
*b
= DDR_B (ddr
);
1503 loop_a
= loop_containing_stmt (DR_STMT (a
));
1504 loop_b
= loop_containing_stmt (DR_STMT (b
));
1506 /* Get the common ancestor loop. */
1507 lca
= find_common_loop (loop_a
, loop_b
);
1510 lca_nb
-= first_loop
;
1511 if (lca_nb
< 0 || lca_nb
>= nb_loops
)
1513 /* For each outer loop where init_v is not set, the accesses are
1514 in dependence of distance 1 in the loop. */
1517 && init_v
[lca_nb
] == 0)
1524 lca_nb
= lca
->num
- first_loop
;
1525 while (lca
->depth
!= 0)
1527 if (lca_nb
< 0 || lca_nb
>= nb_loops
)
1529 if (init_v
[lca_nb
] == 0)
1532 lca_nb
= lca
->num
- first_loop
;
1538 DDR_DIST_VECT (ddr
) = dist_v
;
1541 /* Compute the classic per loop direction vector.
1543 DDR is the data dependence relation to build a vector from.
1544 NB_LOOPS is the total number of loops we are considering.
1545 FIRST_LOOP is the loop->num of the first loop. */
1548 build_classic_dir_vector (struct data_dependence_relation
*ddr
,
1549 int nb_loops
, unsigned int first_loop
)
1552 lambda_vector dir_v
, init_v
;
1554 dir_v
= lambda_vector_new (nb_loops
);
1555 init_v
= lambda_vector_new (nb_loops
);
1556 lambda_vector_clear (dir_v
, nb_loops
);
1557 lambda_vector_clear (init_v
, nb_loops
);
1559 if (DDR_ARE_DEPENDENT (ddr
) != NULL_TREE
)
1562 for (i
= 0; i
< DDR_NUM_SUBSCRIPTS (ddr
); i
++)
1564 struct subscript
*subscript
= DDR_SUBSCRIPT (ddr
, i
);
1566 if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript
)) == POLYNOMIAL_CHREC
1567 && TREE_CODE (SUB_CONFLICTS_IN_B (subscript
)) == POLYNOMIAL_CHREC
)
1571 enum data_dependence_direction dir
= dir_star
;
1572 loop_nb
= CHREC_VARIABLE (SUB_CONFLICTS_IN_A (subscript
));
1573 loop_nb
-= first_loop
;
1575 /* If the loop number is still greater than the number of
1576 loops we've been asked to analyze, or negative,
1577 something is borked. */
1578 if (loop_nb
< 0 || loop_nb
>= nb_loops
)
1580 if (chrec_contains_undetermined (SUB_DISTANCE (subscript
)))
1586 int dist
= int_cst_value (SUB_DISTANCE (subscript
));
1596 /* This is the subscript coupling test.
1601 There is no dependence. */
1602 if (init_v
[loop_nb
] != 0
1604 && (enum data_dependence_direction
) dir_v
[loop_nb
] != dir
1605 && (enum data_dependence_direction
) dir_v
[loop_nb
] != dir_star
)
1607 finalize_ddr_dependent (ddr
, chrec_known
);
1611 dir_v
[loop_nb
] = dir
;
1612 init_v
[loop_nb
] = 1;
1616 /* There is a distance of 1 on all the outer loops:
1618 Example: there is a dependence of distance 1 on loop_1 for the array A.
1624 struct loop
*lca
, *loop_a
, *loop_b
;
1625 struct data_reference
*a
= DDR_A (ddr
);
1626 struct data_reference
*b
= DDR_B (ddr
);
1628 loop_a
= loop_containing_stmt (DR_STMT (a
));
1629 loop_b
= loop_containing_stmt (DR_STMT (b
));
1631 /* Get the common ancestor loop. */
1632 lca
= find_common_loop (loop_a
, loop_b
);
1633 lca_nb
= lca
->num
- first_loop
;
1635 if (lca_nb
< 0 || lca_nb
>= nb_loops
)
1637 /* For each outer loop where init_v is not set, the accesses are
1638 in dependence of distance 1 in the loop. */
1641 && init_v
[lca_nb
] == 0)
1642 dir_v
[lca_nb
] = dir_positive
;
1647 lca_nb
= lca
->num
- first_loop
;
1648 while (lca
->depth
!= 0)
1650 if (lca_nb
< 0 || lca_nb
>= nb_loops
)
1652 if (init_v
[lca_nb
] == 0)
1653 dir_v
[lca_nb
] = dir_positive
;
1655 lca_nb
= lca
->num
- first_loop
;
1661 DDR_DIR_VECT (ddr
) = dir_v
;
1664 /* Returns true when all the access functions of A are affine or
1668 access_functions_are_affine_or_constant_p (struct data_reference
*a
)
1671 varray_type fns
= DR_ACCESS_FNS (a
);
1673 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (fns
); i
++)
1674 if (!evolution_function_is_constant_p (VARRAY_TREE (fns
, i
))
1675 && !evolution_function_is_affine_multivariate_p (VARRAY_TREE (fns
, i
)))
1681 /* This computes the affine dependence relation between A and B.
1682 CHREC_KNOWN is used for representing the independence between two
1683 accesses, while CHREC_DONT_KNOW is used for representing the unknown
1686 Note that it is possible to stop the computation of the dependence
1687 relation the first time we detect a CHREC_KNOWN element for a given
1691 compute_affine_dependence (struct data_dependence_relation
*ddr
)
1693 struct data_reference
*dra
= DDR_A (ddr
);
1694 struct data_reference
*drb
= DDR_B (ddr
);
1696 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1698 fprintf (dump_file
, "(compute_affine_dependence\n");
1699 fprintf (dump_file
, " (stmt_a = \n");
1700 print_generic_expr (dump_file
, DR_STMT (dra
), 0);
1701 fprintf (dump_file
, ")\n (stmt_b = \n");
1702 print_generic_expr (dump_file
, DR_STMT (drb
), 0);
1703 fprintf (dump_file
, ")\n");
1706 /* Analyze only when the dependence relation is not yet known. */
1707 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1709 if (access_functions_are_affine_or_constant_p (dra
)
1710 && access_functions_are_affine_or_constant_p (drb
))
1711 subscript_dependence_tester (ddr
);
1713 /* As a last case, if the dependence cannot be determined, or if
1714 the dependence is considered too difficult to determine, answer
1717 finalize_ddr_dependent (ddr
, chrec_dont_know
);
1720 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1721 fprintf (dump_file
, ")\n");
1724 /* Compute a subset of the data dependence relation graph. Don't
1725 compute read-read relations, and avoid the computation of the
1726 opposite relation, ie. when AB has been computed, don't compute BA.
1727 DATAREFS contains a list of data references, and the result is set
1728 in DEPENDENCE_RELATIONS. */
1731 compute_all_dependences (varray_type datarefs
,
1732 varray_type
*dependence_relations
)
1734 unsigned int i
, j
, N
;
1736 N
= VARRAY_ACTIVE_SIZE (datarefs
);
1738 for (i
= 0; i
< N
; i
++)
1739 for (j
= i
; j
< N
; j
++)
1741 struct data_reference
*a
, *b
;
1742 struct data_dependence_relation
*ddr
;
1744 a
= VARRAY_GENERIC_PTR (datarefs
, i
);
1745 b
= VARRAY_GENERIC_PTR (datarefs
, j
);
1747 ddr
= initialize_data_dependence_relation (a
, b
);
1749 VARRAY_PUSH_GENERIC_PTR (*dependence_relations
, ddr
);
1750 compute_affine_dependence (ddr
);
1751 compute_distance_vector (ddr
);
1755 /* Search the data references in LOOP, and record the information into
1756 DATAREFS. Returns chrec_dont_know when failing to analyze a
1757 difficult case, returns NULL_TREE otherwise.
1759 FIXME: This is a "dumb" walker over all the trees in the loop body.
1760 Find another technique that avoids this costly walk. This is
1761 acceptable for the moment, since this function is used only for
1762 debugging purposes. */
1765 find_data_references_in_loop (struct loop
*loop
, varray_type
*datarefs
)
1768 block_stmt_iterator bsi
;
1772 if (!flow_bb_inside_loop_p (loop
, bb
))
1775 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1777 tree stmt
= bsi_stmt (bsi
);
1778 stmt_ann_t ann
= stmt_ann (stmt
);
1780 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
1784 && !V_MUST_DEF_OPS (ann
)
1785 && !V_MAY_DEF_OPS (ann
))
1788 /* In the GIMPLE representation, a modify expression
1789 contains a single load or store to memory. */
1790 if (TREE_CODE (TREE_OPERAND (stmt
, 0)) == ARRAY_REF
)
1791 VARRAY_PUSH_GENERIC_PTR
1792 (*datarefs
, analyze_array (stmt
, TREE_OPERAND (stmt
, 0),
1795 else if (TREE_CODE (TREE_OPERAND (stmt
, 1)) == ARRAY_REF
)
1796 VARRAY_PUSH_GENERIC_PTR
1797 (*datarefs
, analyze_array (stmt
, TREE_OPERAND (stmt
, 1),
1801 return chrec_dont_know
;
1810 /* This section contains all the entry points. */
1812 /* Given a loop nest LOOP, the following vectors are returned:
1813 *DATAREFS is initialized to all the array elements contained in this loop,
1814 *DEPENDENCE_RELATIONS contains the relations between the data references. */
1817 compute_data_dependences_for_loop (unsigned nb_loops
,
1819 varray_type
*datarefs
,
1820 varray_type
*dependence_relations
)
1824 /* If one of the data references is not computable, give up without
1825 spending time to compute other dependences. */
1826 if (find_data_references_in_loop (loop
, datarefs
) == chrec_dont_know
)
1828 struct data_dependence_relation
*ddr
;
1830 /* Insert a single relation into dependence_relations:
1832 ddr
= initialize_data_dependence_relation (NULL
, NULL
);
1833 VARRAY_PUSH_GENERIC_PTR (*dependence_relations
, ddr
);
1834 build_classic_dist_vector (ddr
, nb_loops
, loop
->num
);
1835 build_classic_dir_vector (ddr
, nb_loops
, loop
->num
);
1839 compute_all_dependences (*datarefs
, dependence_relations
);
1841 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (*dependence_relations
); i
++)
1843 struct data_dependence_relation
*ddr
;
1844 ddr
= VARRAY_GENERIC_PTR (*dependence_relations
, i
);
1845 build_classic_dist_vector (ddr
, nb_loops
, loop
->num
);
1846 build_classic_dir_vector (ddr
, nb_loops
, loop
->num
);
1850 /* Entry point (for testing only). Analyze all the data references
1851 and the dependence relations.
1853 The data references are computed first.
1855 A relation on these nodes is represented by a complete graph. Some
1856 of the relations could be of no interest, thus the relations can be
1859 In the following function we compute all the relations. This is
1860 just a first implementation that is here for:
1861 - for showing how to ask for the dependence relations,
1862 - for the debugging the whole dependence graph,
1863 - for the dejagnu testcases and maintenance.
1865 It is possible to ask only for a part of the graph, avoiding to
1866 compute the whole dependence graph. The computed dependences are
1867 stored in a knowledge base (KB) such that later queries don't
1868 recompute the same information. The implementation of this KB is
1869 transparent to the optimizer, and thus the KB can be changed with a
1870 more efficient implementation, or the KB could be disabled. */
1873 analyze_all_data_dependences (struct loops
*loops
)
1876 varray_type datarefs
;
1877 varray_type dependence_relations
;
1878 int nb_data_refs
= 10;
1880 VARRAY_GENERIC_PTR_INIT (datarefs
, nb_data_refs
, "datarefs");
1881 VARRAY_GENERIC_PTR_INIT (dependence_relations
,
1882 nb_data_refs
* nb_data_refs
,
1883 "dependence_relations");
1885 /* Compute DDs on the whole function. */
1886 compute_data_dependences_for_loop (loops
->num
, loops
->parray
[0],
1887 &datarefs
, &dependence_relations
);
1891 dump_data_dependence_relations (dump_file
, dependence_relations
);
1892 fprintf (dump_file
, "\n\n");
1895 /* Don't dump distances in order to avoid to update the
1897 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1899 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (dependence_relations
); i
++)
1901 struct data_dependence_relation
*ddr
=
1902 (struct data_dependence_relation
*)
1903 VARRAY_GENERIC_PTR (dependence_relations
, i
);
1904 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1906 fprintf (dump_file
, "DISTANCE_V (");
1907 print_lambda_vector (dump_file
, DDR_DIST_VECT (ddr
), loops
->num
);
1908 fprintf (dump_file
, ")\n");
1909 fprintf (dump_file
, "DIRECTION_V (");
1910 print_lambda_vector (dump_file
, DDR_DIR_VECT (ddr
), loops
->num
);
1911 fprintf (dump_file
, ")\n");
1914 fprintf (dump_file
, "\n\n");
1917 if (dump_file
&& (dump_flags
& TDF_STATS
))
1919 unsigned nb_top_relations
= 0;
1920 unsigned nb_bot_relations
= 0;
1921 unsigned nb_basename_differ
= 0;
1922 unsigned nb_chrec_relations
= 0;
1924 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (dependence_relations
); i
++)
1926 struct data_dependence_relation
*ddr
;
1927 ddr
= VARRAY_GENERIC_PTR (dependence_relations
, i
);
1929 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr
)))
1932 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
1934 struct data_reference
*a
= DDR_A (ddr
);
1935 struct data_reference
*b
= DDR_B (ddr
);
1938 if (DR_NUM_DIMENSIONS (a
) != DR_NUM_DIMENSIONS (b
)
1939 || (array_base_name_differ_p (a
, b
, &differ_p
) && differ_p
))
1940 nb_basename_differ
++;
1946 nb_chrec_relations
++;
1949 gather_stats_on_scev_database ();
1952 free_dependence_relations (dependence_relations
);
1953 free_data_refs (datarefs
);
1956 /* Free the memory used by a data dependence relation DDR. */
1959 free_dependence_relation (struct data_dependence_relation
*ddr
)
1964 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
&& DDR_SUBSCRIPTS (ddr
))
1965 varray_clear (DDR_SUBSCRIPTS (ddr
));
1969 /* Free the memory used by the data dependence relations from
1970 DEPENDENCE_RELATIONS. */
1973 free_dependence_relations (varray_type dependence_relations
)
1976 if (dependence_relations
== NULL
)
1979 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (dependence_relations
); i
++)
1980 free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations
, i
));
1981 varray_clear (dependence_relations
);
1984 /* Free the memory used by the data references from DATAREFS. */
1987 free_data_refs (varray_type datarefs
)
1991 if (datarefs
== NULL
)
1994 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (datarefs
); i
++)
1996 struct data_reference
*dr
= (struct data_reference
*)
1997 VARRAY_GENERIC_PTR (datarefs
, i
);
1998 if (dr
&& DR_ACCESS_FNS (dr
))
1999 varray_clear (DR_ACCESS_FNS (dr
));
2001 varray_clear (datarefs
);