* sv.po, zh_CN.po: Update.
[official-gcc.git] / gcc / tree-data-ref.c
blobd48f020a495e58cad543c0e19643603bc89d1148
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
10 version.
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
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA. */
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:
41 - distance vectors
42 - direction vectors
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
48 information,
50 - to define an interface to access this data.
53 Definitions:
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
62 | 3*x + 2*y = 1
63 has an integer solution x = 1 and y = -1.
65 References:
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"
72 by Utpal Banerjee.
77 #include "config.h"
78 #include "system.h"
79 #include "coretypes.h"
80 #include "tm.h"
81 #include "ggc.h"
82 #include "tree.h"
84 /* These RTL headers are needed for basic-block.h. */
85 #include "rtl.h"
86 #include "basic-block.h"
87 #include "diagnostic.h"
88 #include "tree-flow.h"
89 #include "tree-dump.h"
90 #include "timevar.h"
91 #include "cfgloop.h"
92 #include "tree-chrec.h"
93 #include "tree-data-ref.h"
94 #include "tree-scalar-evolution.h"
95 #include "tree-pass.h"
97 /* This is the simplest data dependence test: determines whether the
98 data references A and B access the same array/region. Returns
99 false when the property is not computable at compile time.
100 Otherwise return true, and DIFFER_P will record the result. This
101 utility will not be necessary when alias_sets_conflict_p will be
102 less conservative. */
104 bool
105 array_base_name_differ_p (struct data_reference *a,
106 struct data_reference *b,
107 bool *differ_p)
109 tree base_a = DR_BASE_NAME (a);
110 tree base_b = DR_BASE_NAME (b);
112 if (!base_a || !base_b)
113 return false;
115 /* Determine if same base. Example: for the array accesses
116 a[i], b[i] or pointer accesses *a, *b, bases are a, b. */
117 if (base_a == base_b)
119 *differ_p = false;
120 return true;
123 /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
124 and (*q) */
125 if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
126 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0))
128 *differ_p = false;
129 return true;
132 /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */
133 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
134 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)
135 && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1))
137 *differ_p = false;
138 return true;
142 /* Determine if different bases. */
144 /* At this point we know that base_a != base_b. However, pointer
145 accesses of the form x=(*p) and y=(*q), whose bases are p and q,
146 may still be pointing to the same base. In SSAed GIMPLE p and q will
147 be SSA_NAMES in this case. Therefore, here we check if they are
148 really two different declarations. */
149 if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
151 *differ_p = true;
152 return true;
155 /* Compare two record/union bases s.a and t.b: s != t or (a != b and
156 s and t are not unions). */
157 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
158 && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
159 && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
160 && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
161 || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE
162 && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
163 && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
165 *differ_p = true;
166 return true;
169 /* Compare a record/union access and an array access. */
170 if ((TREE_CODE (base_a) == VAR_DECL
171 && (TREE_CODE (base_b) == COMPONENT_REF
172 && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL))
173 || (TREE_CODE (base_b) == VAR_DECL
174 && (TREE_CODE (base_a) == COMPONENT_REF
175 && TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL)))
177 *differ_p = true;
178 return true;
181 return false;
184 /* Returns true iff A divides B. */
186 static inline bool
187 tree_fold_divides_p (tree type,
188 tree a,
189 tree b)
191 /* Determines whether (A == gcd (A, B)). */
192 return integer_zerop
193 (fold_build2 (MINUS_EXPR, type, a, tree_fold_gcd (a, b)));
196 /* Compute the greatest common denominator of two numbers using
197 Euclid's algorithm. */
199 static int
200 gcd (int a, int b)
203 int x, y, z;
205 x = abs (a);
206 y = abs (b);
208 while (x>0)
210 z = y % x;
211 y = x;
212 x = z;
215 return (y);
218 /* Returns true iff A divides B. */
220 static inline bool
221 int_divides_p (int a, int b)
223 return ((b % a) == 0);
228 /* Dump into FILE all the data references from DATAREFS. */
230 void
231 dump_data_references (FILE *file,
232 varray_type datarefs)
234 unsigned int i;
236 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
237 dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i));
240 /* Dump into FILE all the dependence relations from DDR. */
242 void
243 dump_data_dependence_relations (FILE *file,
244 varray_type ddr)
246 unsigned int i;
248 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++)
249 dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i));
252 /* Dump function for a DATA_REFERENCE structure. */
254 void
255 dump_data_reference (FILE *outf,
256 struct data_reference *dr)
258 unsigned int i;
260 fprintf (outf, "(Data Ref: \n stmt: ");
261 print_generic_stmt (outf, DR_STMT (dr), 0);
262 fprintf (outf, " ref: ");
263 print_generic_stmt (outf, DR_REF (dr), 0);
264 fprintf (outf, " base_name: ");
265 print_generic_stmt (outf, DR_BASE_NAME (dr), 0);
267 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
269 fprintf (outf, " Access function %d: ", i);
270 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
272 fprintf (outf, ")\n");
275 /* Dump function for a SUBSCRIPT structure. */
277 void
278 dump_subscript (FILE *outf, struct subscript *subscript)
280 tree chrec = SUB_CONFLICTS_IN_A (subscript);
282 fprintf (outf, "\n (subscript \n");
283 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
284 print_generic_stmt (outf, chrec, 0);
285 if (chrec == chrec_known)
286 fprintf (outf, " (no dependence)\n");
287 else if (chrec_contains_undetermined (chrec))
288 fprintf (outf, " (don't know)\n");
289 else
291 tree last_iteration = SUB_LAST_CONFLICT (subscript);
292 fprintf (outf, " last_conflict: ");
293 print_generic_stmt (outf, last_iteration, 0);
296 chrec = SUB_CONFLICTS_IN_B (subscript);
297 fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
298 print_generic_stmt (outf, chrec, 0);
299 if (chrec == chrec_known)
300 fprintf (outf, " (no dependence)\n");
301 else if (chrec_contains_undetermined (chrec))
302 fprintf (outf, " (don't know)\n");
303 else
305 tree last_iteration = SUB_LAST_CONFLICT (subscript);
306 fprintf (outf, " last_conflict: ");
307 print_generic_stmt (outf, last_iteration, 0);
310 fprintf (outf, " (Subscript distance: ");
311 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
312 fprintf (outf, " )\n");
313 fprintf (outf, " )\n");
316 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
318 void
319 dump_data_dependence_relation (FILE *outf,
320 struct data_dependence_relation *ddr)
322 struct data_reference *dra, *drb;
324 dra = DDR_A (ddr);
325 drb = DDR_B (ddr);
326 fprintf (outf, "(Data Dep: \n");
327 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
328 fprintf (outf, " (don't know)\n");
330 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
331 fprintf (outf, " (no dependence)\n");
333 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
335 unsigned int i;
336 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
338 fprintf (outf, " access_fn_A: ");
339 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
340 fprintf (outf, " access_fn_B: ");
341 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
342 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
344 if (DDR_DIST_VECT (ddr))
346 fprintf (outf, " distance_vect: ");
347 print_lambda_vector (outf, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
349 if (DDR_DIR_VECT (ddr))
351 fprintf (outf, " direction_vect: ");
352 print_lambda_vector (outf, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
356 fprintf (outf, ")\n");
361 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
363 void
364 dump_data_dependence_direction (FILE *file,
365 enum data_dependence_direction dir)
367 switch (dir)
369 case dir_positive:
370 fprintf (file, "+");
371 break;
373 case dir_negative:
374 fprintf (file, "-");
375 break;
377 case dir_equal:
378 fprintf (file, "=");
379 break;
381 case dir_positive_or_negative:
382 fprintf (file, "+-");
383 break;
385 case dir_positive_or_equal:
386 fprintf (file, "+=");
387 break;
389 case dir_negative_or_equal:
390 fprintf (file, "-=");
391 break;
393 case dir_star:
394 fprintf (file, "*");
395 break;
397 default:
398 break;
402 /* Dumps the distance and direction vectors in FILE. DDRS contains
403 the dependence relations, and VECT_SIZE is the size of the
404 dependence vectors, or in other words the number of loops in the
405 considered nest. */
407 void
408 dump_dist_dir_vectors (FILE *file, varray_type ddrs)
410 unsigned int i;
412 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
414 struct data_dependence_relation *ddr =
415 (struct data_dependence_relation *)
416 VARRAY_GENERIC_PTR (ddrs, i);
417 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
418 && DDR_AFFINE_P (ddr))
420 fprintf (file, "DISTANCE_V (");
421 print_lambda_vector (file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
422 fprintf (file, ")\n");
423 fprintf (file, "DIRECTION_V (");
424 print_lambda_vector (file, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
425 fprintf (file, ")\n");
428 fprintf (file, "\n\n");
431 /* Dumps the data dependence relations DDRS in FILE. */
433 void
434 dump_ddrs (FILE *file, varray_type ddrs)
436 unsigned int i;
438 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
440 struct data_dependence_relation *ddr =
441 (struct data_dependence_relation *)
442 VARRAY_GENERIC_PTR (ddrs, i);
443 dump_data_dependence_relation (file, ddr);
445 fprintf (file, "\n\n");
450 /* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
451 approximation of the number of iterations for LOOP. */
453 static void
454 compute_estimated_nb_iterations (struct loop *loop)
456 struct nb_iter_bound *bound;
458 for (bound = loop->bounds; bound; bound = bound->next)
459 if (TREE_CODE (bound->bound) == INTEGER_CST
460 /* Update only when there is no previous estimation. */
461 && (chrec_contains_undetermined (loop->estimated_nb_iterations)
462 /* Or when the current estimation is smaller. */
463 || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations)))
464 loop->estimated_nb_iterations = bound->bound;
467 /* Estimate the number of iterations from the size of the data and the
468 access functions. */
470 static void
471 estimate_niter_from_size_of_data (struct loop *loop,
472 tree opnd0,
473 tree access_fn,
474 tree stmt)
476 tree estimation;
477 tree array_size, data_size, element_size;
478 tree init, step;
480 init = initial_condition (access_fn);
481 step = evolution_part_in_loop_num (access_fn, loop->num);
483 array_size = TYPE_SIZE (TREE_TYPE (opnd0));
484 element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
485 if (array_size == NULL_TREE
486 || TREE_CODE (array_size) != INTEGER_CST
487 || TREE_CODE (element_size) != INTEGER_CST)
488 return;
490 data_size = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
491 array_size, element_size);
493 if (init != NULL_TREE
494 && step != NULL_TREE
495 && TREE_CODE (init) == INTEGER_CST
496 && TREE_CODE (step) == INTEGER_CST)
498 estimation = fold_build2 (CEIL_DIV_EXPR, integer_type_node,
499 fold_build2 (MINUS_EXPR, integer_type_node,
500 data_size, init), step);
502 record_estimate (loop, estimation, boolean_true_node, stmt);
506 /* Given an ARRAY_REF node REF, records its access functions.
507 Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
508 i.e. the constant "3", then recursively call the function on opnd0,
509 i.e. the ARRAY_REF "A[i]". The function returns the base name:
510 "A". */
512 static tree
513 analyze_array_indexes (struct loop *loop,
514 VEC(tree,heap) **access_fns,
515 tree ref, tree stmt)
517 tree opnd0, opnd1;
518 tree access_fn;
520 opnd0 = TREE_OPERAND (ref, 0);
521 opnd1 = TREE_OPERAND (ref, 1);
523 /* The detection of the evolution function for this data access is
524 postponed until the dependence test. This lazy strategy avoids
525 the computation of access functions that are of no interest for
526 the optimizers. */
527 access_fn = instantiate_parameters
528 (loop, analyze_scalar_evolution (loop, opnd1));
530 if (chrec_contains_undetermined (loop->estimated_nb_iterations))
531 estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
533 VEC_safe_push (tree, heap, *access_fns, access_fn);
535 /* Recursively record other array access functions. */
536 if (TREE_CODE (opnd0) == ARRAY_REF)
537 return analyze_array_indexes (loop, access_fns, opnd0, stmt);
539 /* Return the base name of the data access. */
540 else
541 return opnd0;
544 /* For a data reference REF contained in the statement STMT, initialize
545 a DATA_REFERENCE structure, and return it. IS_READ flag has to be
546 set to true when REF is in the right hand side of an
547 assignment. */
549 struct data_reference *
550 analyze_array (tree stmt, tree ref, bool is_read)
552 struct data_reference *res;
554 if (dump_file && (dump_flags & TDF_DETAILS))
556 fprintf (dump_file, "(analyze_array \n");
557 fprintf (dump_file, " (ref = ");
558 print_generic_stmt (dump_file, ref, 0);
559 fprintf (dump_file, ")\n");
562 res = xmalloc (sizeof (struct data_reference));
564 DR_STMT (res) = stmt;
565 DR_REF (res) = ref;
566 DR_ACCESS_FNS (res) = VEC_alloc (tree, heap, 3);
567 DR_BASE_NAME (res) = analyze_array_indexes
568 (loop_containing_stmt (stmt), &(DR_ACCESS_FNS (res)), ref, stmt);
569 DR_IS_READ (res) = is_read;
571 if (dump_file && (dump_flags & TDF_DETAILS))
572 fprintf (dump_file, ")\n");
574 return res;
577 /* For a data reference REF contained in the statement STMT, initialize
578 a DATA_REFERENCE structure, and return it. */
580 struct data_reference *
581 init_data_ref (tree stmt,
582 tree ref,
583 tree base,
584 tree access_fn,
585 bool is_read)
587 struct data_reference *res;
589 if (dump_file && (dump_flags & TDF_DETAILS))
591 fprintf (dump_file, "(init_data_ref \n");
592 fprintf (dump_file, " (ref = ");
593 print_generic_stmt (dump_file, ref, 0);
594 fprintf (dump_file, ")\n");
597 res = xmalloc (sizeof (struct data_reference));
599 DR_STMT (res) = stmt;
600 DR_REF (res) = ref;
601 DR_ACCESS_FNS (res) = VEC_alloc (tree, heap, 5);
602 DR_BASE_NAME (res) = base;
603 VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
604 DR_IS_READ (res) = is_read;
606 if (dump_file && (dump_flags & TDF_DETAILS))
607 fprintf (dump_file, ")\n");
609 return res;
614 /* Returns true when all the functions of a tree_vec CHREC are the
615 same. */
617 static bool
618 all_chrecs_equal_p (tree chrec)
620 int j;
622 for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
624 tree chrec_j = TREE_VEC_ELT (chrec, j);
625 tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1);
626 if (!integer_zerop
627 (chrec_fold_minus
628 (integer_type_node, chrec_j, chrec_j_1)))
629 return false;
631 return true;
634 /* Determine for each subscript in the data dependence relation DDR
635 the distance. */
637 void
638 compute_subscript_distance (struct data_dependence_relation *ddr)
640 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
642 unsigned int i;
644 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
646 tree conflicts_a, conflicts_b, difference;
647 struct subscript *subscript;
649 subscript = DDR_SUBSCRIPT (ddr, i);
650 conflicts_a = SUB_CONFLICTS_IN_A (subscript);
651 conflicts_b = SUB_CONFLICTS_IN_B (subscript);
653 if (TREE_CODE (conflicts_a) == TREE_VEC)
655 if (!all_chrecs_equal_p (conflicts_a))
657 SUB_DISTANCE (subscript) = chrec_dont_know;
658 return;
660 else
661 conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
664 if (TREE_CODE (conflicts_b) == TREE_VEC)
666 if (!all_chrecs_equal_p (conflicts_b))
668 SUB_DISTANCE (subscript) = chrec_dont_know;
669 return;
671 else
672 conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
675 difference = chrec_fold_minus
676 (integer_type_node, conflicts_b, conflicts_a);
678 if (evolution_function_is_constant_p (difference))
679 SUB_DISTANCE (subscript) = difference;
681 else
682 SUB_DISTANCE (subscript) = chrec_dont_know;
687 /* Initialize a ddr. */
689 struct data_dependence_relation *
690 initialize_data_dependence_relation (struct data_reference *a,
691 struct data_reference *b)
693 struct data_dependence_relation *res;
694 bool differ_p;
696 res = xmalloc (sizeof (struct data_dependence_relation));
697 DDR_A (res) = a;
698 DDR_B (res) = b;
700 if (a == NULL || b == NULL
701 || DR_BASE_NAME (a) == NULL_TREE
702 || DR_BASE_NAME (b) == NULL_TREE)
703 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
705 /* When the dimensions of A and B differ, we directly initialize
706 the relation to "there is no dependence": chrec_known. */
707 else if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
708 || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
709 DDR_ARE_DEPENDENT (res) = chrec_known;
711 else
713 unsigned int i;
714 DDR_AFFINE_P (res) = true;
715 DDR_ARE_DEPENDENT (res) = NULL_TREE;
716 DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
717 DDR_SIZE_VECT (res) = 0;
718 DDR_DIST_VECT (res) = NULL;
719 DDR_DIR_VECT (res) = NULL;
721 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
723 struct subscript *subscript;
725 subscript = xmalloc (sizeof (struct subscript));
726 SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
727 SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
728 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
729 SUB_DISTANCE (subscript) = chrec_dont_know;
730 VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
734 return res;
737 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
738 description. */
740 static inline void
741 finalize_ddr_dependent (struct data_dependence_relation *ddr,
742 tree chrec)
744 if (dump_file && (dump_flags & TDF_DETAILS))
746 fprintf (dump_file, "(dependence classified: ");
747 print_generic_expr (dump_file, chrec, 0);
748 fprintf (dump_file, ")\n");
751 DDR_ARE_DEPENDENT (ddr) = chrec;
752 varray_clear (DDR_SUBSCRIPTS (ddr));
755 /* The dependence relation DDR cannot be represented by a distance
756 vector. */
758 static inline void
759 non_affine_dependence_relation (struct data_dependence_relation *ddr)
761 if (dump_file && (dump_flags & TDF_DETAILS))
762 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
764 DDR_AFFINE_P (ddr) = false;
769 /* This section contains the classic Banerjee tests. */
771 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
772 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
774 static inline bool
775 ziv_subscript_p (tree chrec_a,
776 tree chrec_b)
778 return (evolution_function_is_constant_p (chrec_a)
779 && evolution_function_is_constant_p (chrec_b));
782 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
783 variable, i.e., if the SIV (Single Index Variable) test is true. */
785 static bool
786 siv_subscript_p (tree chrec_a,
787 tree chrec_b)
789 if ((evolution_function_is_constant_p (chrec_a)
790 && evolution_function_is_univariate_p (chrec_b))
791 || (evolution_function_is_constant_p (chrec_b)
792 && evolution_function_is_univariate_p (chrec_a)))
793 return true;
795 if (evolution_function_is_univariate_p (chrec_a)
796 && evolution_function_is_univariate_p (chrec_b))
798 switch (TREE_CODE (chrec_a))
800 case POLYNOMIAL_CHREC:
801 switch (TREE_CODE (chrec_b))
803 case POLYNOMIAL_CHREC:
804 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
805 return false;
807 default:
808 return true;
811 default:
812 return true;
816 return false;
819 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
820 *OVERLAPS_B are initialized to the functions that describe the
821 relation between the elements accessed twice by CHREC_A and
822 CHREC_B. For k >= 0, the following property is verified:
824 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
826 static void
827 analyze_ziv_subscript (tree chrec_a,
828 tree chrec_b,
829 tree *overlaps_a,
830 tree *overlaps_b,
831 tree *last_conflicts)
833 tree difference;
835 if (dump_file && (dump_flags & TDF_DETAILS))
836 fprintf (dump_file, "(analyze_ziv_subscript \n");
838 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
840 switch (TREE_CODE (difference))
842 case INTEGER_CST:
843 if (integer_zerop (difference))
845 /* The difference is equal to zero: the accessed index
846 overlaps for each iteration in the loop. */
847 *overlaps_a = integer_zero_node;
848 *overlaps_b = integer_zero_node;
849 *last_conflicts = chrec_dont_know;
851 else
853 /* The accesses do not overlap. */
854 *overlaps_a = chrec_known;
855 *overlaps_b = chrec_known;
856 *last_conflicts = integer_zero_node;
858 break;
860 default:
861 /* We're not sure whether the indexes overlap. For the moment,
862 conservatively answer "don't know". */
863 *overlaps_a = chrec_dont_know;
864 *overlaps_b = chrec_dont_know;
865 *last_conflicts = chrec_dont_know;
866 break;
869 if (dump_file && (dump_flags & TDF_DETAILS))
870 fprintf (dump_file, ")\n");
873 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
874 constant, and CHREC_B is an affine function. *OVERLAPS_A and
875 *OVERLAPS_B are initialized to the functions that describe the
876 relation between the elements accessed twice by CHREC_A and
877 CHREC_B. For k >= 0, the following property is verified:
879 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
881 static void
882 analyze_siv_subscript_cst_affine (tree chrec_a,
883 tree chrec_b,
884 tree *overlaps_a,
885 tree *overlaps_b,
886 tree *last_conflicts)
888 bool value0, value1, value2;
889 tree difference = chrec_fold_minus
890 (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
892 if (!chrec_is_positive (initial_condition (difference), &value0))
894 *overlaps_a = chrec_dont_know;
895 *overlaps_b = chrec_dont_know;
896 *last_conflicts = chrec_dont_know;
897 return;
899 else
901 if (value0 == false)
903 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
905 *overlaps_a = chrec_dont_know;
906 *overlaps_b = chrec_dont_know;
907 *last_conflicts = chrec_dont_know;
908 return;
910 else
912 if (value1 == true)
914 /* Example:
915 chrec_a = 12
916 chrec_b = {10, +, 1}
919 if (tree_fold_divides_p
920 (integer_type_node, CHREC_RIGHT (chrec_b), difference))
922 *overlaps_a = integer_zero_node;
923 *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
924 fold_build1 (ABS_EXPR,
925 integer_type_node,
926 difference),
927 CHREC_RIGHT (chrec_b));
928 *last_conflicts = integer_one_node;
929 return;
932 /* When the step does not divides the difference, there are
933 no overlaps. */
934 else
936 *overlaps_a = chrec_known;
937 *overlaps_b = chrec_known;
938 *last_conflicts = integer_zero_node;
939 return;
943 else
945 /* Example:
946 chrec_a = 12
947 chrec_b = {10, +, -1}
949 In this case, chrec_a will not overlap with chrec_b. */
950 *overlaps_a = chrec_known;
951 *overlaps_b = chrec_known;
952 *last_conflicts = integer_zero_node;
953 return;
957 else
959 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
961 *overlaps_a = chrec_dont_know;
962 *overlaps_b = chrec_dont_know;
963 *last_conflicts = chrec_dont_know;
964 return;
966 else
968 if (value2 == false)
970 /* Example:
971 chrec_a = 3
972 chrec_b = {10, +, -1}
974 if (tree_fold_divides_p
975 (integer_type_node, CHREC_RIGHT (chrec_b), difference))
977 *overlaps_a = integer_zero_node;
978 *overlaps_b = fold
979 (build (EXACT_DIV_EXPR, integer_type_node, difference,
980 CHREC_RIGHT (chrec_b)));
981 *last_conflicts = integer_one_node;
982 return;
985 /* When the step does not divides the difference, there
986 are no overlaps. */
987 else
989 *overlaps_a = chrec_known;
990 *overlaps_b = chrec_known;
991 *last_conflicts = integer_zero_node;
992 return;
995 else
997 /* Example:
998 chrec_a = 3
999 chrec_b = {4, +, 1}
1001 In this case, chrec_a will not overlap with chrec_b. */
1002 *overlaps_a = chrec_known;
1003 *overlaps_b = chrec_known;
1004 *last_conflicts = integer_zero_node;
1005 return;
1012 /* Helper recursive function for initializing the matrix A. Returns
1013 the initial value of CHREC. */
1015 static int
1016 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
1018 gcc_assert (chrec);
1020 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1021 return int_cst_value (chrec);
1023 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
1024 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
1027 #define FLOOR_DIV(x,y) ((x) / (y))
1029 /* Solves the special case of the Diophantine equation:
1030 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1032 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1033 number of iterations that loops X and Y run. The overlaps will be
1034 constructed as evolutions in dimension DIM. */
1036 static void
1037 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
1038 tree *overlaps_a, tree *overlaps_b,
1039 tree *last_conflicts, int dim)
1041 if (((step_a > 0 && step_b > 0)
1042 || (step_a < 0 && step_b < 0)))
1044 int step_overlaps_a, step_overlaps_b;
1045 int gcd_steps_a_b, last_conflict, tau2;
1047 gcd_steps_a_b = gcd (step_a, step_b);
1048 step_overlaps_a = step_b / gcd_steps_a_b;
1049 step_overlaps_b = step_a / gcd_steps_a_b;
1051 tau2 = FLOOR_DIV (niter, step_overlaps_a);
1052 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
1053 last_conflict = tau2;
1055 *overlaps_a = build_polynomial_chrec
1056 (dim, integer_zero_node,
1057 build_int_cst (NULL_TREE, step_overlaps_a));
1058 *overlaps_b = build_polynomial_chrec
1059 (dim, integer_zero_node,
1060 build_int_cst (NULL_TREE, step_overlaps_b));
1061 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
1064 else
1066 *overlaps_a = integer_zero_node;
1067 *overlaps_b = integer_zero_node;
1068 *last_conflicts = integer_zero_node;
1073 /* Solves the special case of a Diophantine equation where CHREC_A is
1074 an affine bivariate function, and CHREC_B is an affine univariate
1075 function. For example,
1077 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1079 has the following overlapping functions:
1081 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1082 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1083 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1085 FORNOW: This is a specialized implementation for a case occurring in
1086 a common benchmark. Implement the general algorithm. */
1088 static void
1089 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
1090 tree *overlaps_a, tree *overlaps_b,
1091 tree *last_conflicts)
1093 bool xz_p, yz_p, xyz_p;
1094 int step_x, step_y, step_z;
1095 int niter_x, niter_y, niter_z, niter;
1096 tree numiter_x, numiter_y, numiter_z;
1097 tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
1098 tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
1099 tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
1101 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
1102 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
1103 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
1105 numiter_x = number_of_iterations_in_loop
1106 (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]);
1107 numiter_y = number_of_iterations_in_loop
1108 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
1109 numiter_z = number_of_iterations_in_loop
1110 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
1112 if (TREE_CODE (numiter_x) != INTEGER_CST)
1113 numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]
1114 ->estimated_nb_iterations;
1115 if (TREE_CODE (numiter_y) != INTEGER_CST)
1116 numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]
1117 ->estimated_nb_iterations;
1118 if (TREE_CODE (numiter_z) != INTEGER_CST)
1119 numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
1120 ->estimated_nb_iterations;
1122 if (chrec_contains_undetermined (numiter_x)
1123 || chrec_contains_undetermined (numiter_y)
1124 || chrec_contains_undetermined (numiter_z)
1125 || TREE_CODE (numiter_x) != INTEGER_CST
1126 || TREE_CODE (numiter_y) != INTEGER_CST
1127 || TREE_CODE (numiter_z) != INTEGER_CST)
1129 *overlaps_a = chrec_dont_know;
1130 *overlaps_b = chrec_dont_know;
1131 *last_conflicts = chrec_dont_know;
1132 return;
1135 niter_x = int_cst_value (numiter_x);
1136 niter_y = int_cst_value (numiter_y);
1137 niter_z = int_cst_value (numiter_z);
1139 niter = MIN (niter_x, niter_z);
1140 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
1141 &overlaps_a_xz,
1142 &overlaps_b_xz,
1143 &last_conflicts_xz, 1);
1144 niter = MIN (niter_y, niter_z);
1145 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
1146 &overlaps_a_yz,
1147 &overlaps_b_yz,
1148 &last_conflicts_yz, 2);
1149 niter = MIN (niter_x, niter_z);
1150 niter = MIN (niter_y, niter);
1151 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
1152 &overlaps_a_xyz,
1153 &overlaps_b_xyz,
1154 &last_conflicts_xyz, 3);
1156 xz_p = !integer_zerop (last_conflicts_xz);
1157 yz_p = !integer_zerop (last_conflicts_yz);
1158 xyz_p = !integer_zerop (last_conflicts_xyz);
1160 if (xz_p || yz_p || xyz_p)
1162 *overlaps_a = make_tree_vec (2);
1163 TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
1164 TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
1165 *overlaps_b = integer_zero_node;
1166 if (xz_p)
1168 TREE_VEC_ELT (*overlaps_a, 0) =
1169 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
1170 overlaps_a_xz);
1171 *overlaps_b =
1172 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
1173 *last_conflicts = last_conflicts_xz;
1175 if (yz_p)
1177 TREE_VEC_ELT (*overlaps_a, 1) =
1178 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
1179 overlaps_a_yz);
1180 *overlaps_b =
1181 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
1182 *last_conflicts = last_conflicts_yz;
1184 if (xyz_p)
1186 TREE_VEC_ELT (*overlaps_a, 0) =
1187 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
1188 overlaps_a_xyz);
1189 TREE_VEC_ELT (*overlaps_a, 1) =
1190 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
1191 overlaps_a_xyz);
1192 *overlaps_b =
1193 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
1194 *last_conflicts = last_conflicts_xyz;
1197 else
1199 *overlaps_a = integer_zero_node;
1200 *overlaps_b = integer_zero_node;
1201 *last_conflicts = integer_zero_node;
1205 /* Determines the overlapping elements due to accesses CHREC_A and
1206 CHREC_B, that are affine functions. This is a part of the
1207 subscript analyzer. */
1209 static void
1210 analyze_subscript_affine_affine (tree chrec_a,
1211 tree chrec_b,
1212 tree *overlaps_a,
1213 tree *overlaps_b,
1214 tree *last_conflicts)
1216 unsigned nb_vars_a, nb_vars_b, dim;
1217 int init_a, init_b, gamma, gcd_alpha_beta;
1218 int tau1, tau2;
1219 lambda_matrix A, U, S;
1221 if (dump_file && (dump_flags & TDF_DETAILS))
1222 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
1224 /* For determining the initial intersection, we have to solve a
1225 Diophantine equation. This is the most time consuming part.
1227 For answering to the question: "Is there a dependence?" we have
1228 to prove that there exists a solution to the Diophantine
1229 equation, and that the solution is in the iteration domain,
1230 i.e. the solution is positive or zero, and that the solution
1231 happens before the upper bound loop.nb_iterations. Otherwise
1232 there is no dependence. This function outputs a description of
1233 the iterations that hold the intersections. */
1236 nb_vars_a = nb_vars_in_chrec (chrec_a);
1237 nb_vars_b = nb_vars_in_chrec (chrec_b);
1239 dim = nb_vars_a + nb_vars_b;
1240 U = lambda_matrix_new (dim, dim);
1241 A = lambda_matrix_new (dim, 1);
1242 S = lambda_matrix_new (dim, 1);
1244 init_a = initialize_matrix_A (A, chrec_a, 0, 1);
1245 init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
1246 gamma = init_b - init_a;
1248 /* Don't do all the hard work of solving the Diophantine equation
1249 when we already know the solution: for example,
1250 | {3, +, 1}_1
1251 | {3, +, 4}_2
1252 | gamma = 3 - 3 = 0.
1253 Then the first overlap occurs during the first iterations:
1254 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
1256 if (gamma == 0)
1258 if (nb_vars_a == 1 && nb_vars_b == 1)
1260 int step_a, step_b;
1261 int niter, niter_a, niter_b;
1262 tree numiter_a, numiter_b;
1264 numiter_a = number_of_iterations_in_loop
1265 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
1266 numiter_b = number_of_iterations_in_loop
1267 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
1269 if (TREE_CODE (numiter_a) != INTEGER_CST)
1270 numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
1271 ->estimated_nb_iterations;
1272 if (TREE_CODE (numiter_b) != INTEGER_CST)
1273 numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
1274 ->estimated_nb_iterations;
1275 if (chrec_contains_undetermined (numiter_a)
1276 || chrec_contains_undetermined (numiter_b)
1277 || TREE_CODE (numiter_a) != INTEGER_CST
1278 || TREE_CODE (numiter_b) != INTEGER_CST)
1280 *overlaps_a = chrec_dont_know;
1281 *overlaps_b = chrec_dont_know;
1282 *last_conflicts = chrec_dont_know;
1283 return;
1286 niter_a = int_cst_value (numiter_a);
1287 niter_b = int_cst_value (numiter_b);
1288 niter = MIN (niter_a, niter_b);
1290 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
1291 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
1293 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
1294 overlaps_a, overlaps_b,
1295 last_conflicts, 1);
1298 else if (nb_vars_a == 2 && nb_vars_b == 1)
1299 compute_overlap_steps_for_affine_1_2
1300 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
1302 else if (nb_vars_a == 1 && nb_vars_b == 2)
1303 compute_overlap_steps_for_affine_1_2
1304 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
1306 else
1308 *overlaps_a = chrec_dont_know;
1309 *overlaps_b = chrec_dont_know;
1310 *last_conflicts = chrec_dont_know;
1312 return;
1315 /* U.A = S */
1316 lambda_matrix_right_hermite (A, dim, 1, S, U);
1318 if (S[0][0] < 0)
1320 S[0][0] *= -1;
1321 lambda_matrix_row_negate (U, dim, 0);
1323 gcd_alpha_beta = S[0][0];
1325 /* The classic "gcd-test". */
1326 if (!int_divides_p (gcd_alpha_beta, gamma))
1328 /* The "gcd-test" has determined that there is no integer
1329 solution, i.e. there is no dependence. */
1330 *overlaps_a = chrec_known;
1331 *overlaps_b = chrec_known;
1332 *last_conflicts = integer_zero_node;
1335 /* Both access functions are univariate. This includes SIV and MIV cases. */
1336 else if (nb_vars_a == 1 && nb_vars_b == 1)
1338 /* Both functions should have the same evolution sign. */
1339 if (((A[0][0] > 0 && -A[1][0] > 0)
1340 || (A[0][0] < 0 && -A[1][0] < 0)))
1342 /* The solutions are given by:
1344 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
1345 | [u21 u22] [y0]
1347 For a given integer t. Using the following variables,
1349 | i0 = u11 * gamma / gcd_alpha_beta
1350 | j0 = u12 * gamma / gcd_alpha_beta
1351 | i1 = u21
1352 | j1 = u22
1354 the solutions are:
1356 | x0 = i0 + i1 * t,
1357 | y0 = j0 + j1 * t. */
1359 int i0, j0, i1, j1;
1361 /* X0 and Y0 are the first iterations for which there is a
1362 dependence. X0, Y0 are two solutions of the Diophantine
1363 equation: chrec_a (X0) = chrec_b (Y0). */
1364 int x0, y0;
1365 int niter, niter_a, niter_b;
1366 tree numiter_a, numiter_b;
1368 numiter_a = number_of_iterations_in_loop
1369 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
1370 numiter_b = number_of_iterations_in_loop
1371 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
1373 if (TREE_CODE (numiter_a) != INTEGER_CST)
1374 numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
1375 ->estimated_nb_iterations;
1376 if (TREE_CODE (numiter_b) != INTEGER_CST)
1377 numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
1378 ->estimated_nb_iterations;
1379 if (chrec_contains_undetermined (numiter_a)
1380 || chrec_contains_undetermined (numiter_b)
1381 || TREE_CODE (numiter_a) != INTEGER_CST
1382 || TREE_CODE (numiter_b) != INTEGER_CST)
1384 *overlaps_a = chrec_dont_know;
1385 *overlaps_b = chrec_dont_know;
1386 *last_conflicts = chrec_dont_know;
1387 return;
1390 niter_a = int_cst_value (numiter_a);
1391 niter_b = int_cst_value (numiter_b);
1392 niter = MIN (niter_a, niter_b);
1394 i0 = U[0][0] * gamma / gcd_alpha_beta;
1395 j0 = U[0][1] * gamma / gcd_alpha_beta;
1396 i1 = U[1][0];
1397 j1 = U[1][1];
1399 if ((i1 == 0 && i0 < 0)
1400 || (j1 == 0 && j0 < 0))
1402 /* There is no solution.
1403 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
1404 falls in here, but for the moment we don't look at the
1405 upper bound of the iteration domain. */
1406 *overlaps_a = chrec_known;
1407 *overlaps_b = chrec_known;
1408 *last_conflicts = integer_zero_node;
1411 else
1413 if (i1 > 0)
1415 tau1 = CEIL (-i0, i1);
1416 tau2 = FLOOR_DIV (niter - i0, i1);
1418 if (j1 > 0)
1420 int last_conflict, min_multiple;
1421 tau1 = MAX (tau1, CEIL (-j0, j1));
1422 tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
1424 x0 = i1 * tau1 + i0;
1425 y0 = j1 * tau1 + j0;
1427 /* At this point (x0, y0) is one of the
1428 solutions to the Diophantine equation. The
1429 next step has to compute the smallest
1430 positive solution: the first conflicts. */
1431 min_multiple = MIN (x0 / i1, y0 / j1);
1432 x0 -= i1 * min_multiple;
1433 y0 -= j1 * min_multiple;
1435 tau1 = (x0 - i0)/i1;
1436 last_conflict = tau2 - tau1;
1438 *overlaps_a = build_polynomial_chrec
1440 build_int_cst (NULL_TREE, x0),
1441 build_int_cst (NULL_TREE, i1));
1442 *overlaps_b = build_polynomial_chrec
1444 build_int_cst (NULL_TREE, y0),
1445 build_int_cst (NULL_TREE, j1));
1446 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
1448 else
1450 /* FIXME: For the moment, the upper bound of the
1451 iteration domain for j is not checked. */
1452 *overlaps_a = chrec_dont_know;
1453 *overlaps_b = chrec_dont_know;
1454 *last_conflicts = chrec_dont_know;
1458 else
1460 /* FIXME: For the moment, the upper bound of the
1461 iteration domain for i is not checked. */
1462 *overlaps_a = chrec_dont_know;
1463 *overlaps_b = chrec_dont_know;
1464 *last_conflicts = chrec_dont_know;
1468 else
1470 *overlaps_a = chrec_dont_know;
1471 *overlaps_b = chrec_dont_know;
1472 *last_conflicts = chrec_dont_know;
1476 else
1478 *overlaps_a = chrec_dont_know;
1479 *overlaps_b = chrec_dont_know;
1480 *last_conflicts = chrec_dont_know;
1484 if (dump_file && (dump_flags & TDF_DETAILS))
1486 fprintf (dump_file, " (overlaps_a = ");
1487 print_generic_expr (dump_file, *overlaps_a, 0);
1488 fprintf (dump_file, ")\n (overlaps_b = ");
1489 print_generic_expr (dump_file, *overlaps_b, 0);
1490 fprintf (dump_file, ")\n");
1493 if (dump_file && (dump_flags & TDF_DETAILS))
1494 fprintf (dump_file, ")\n");
1497 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
1498 *OVERLAPS_B are initialized to the functions that describe the
1499 relation between the elements accessed twice by CHREC_A and
1500 CHREC_B. For k >= 0, the following property is verified:
1502 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1504 static void
1505 analyze_siv_subscript (tree chrec_a,
1506 tree chrec_b,
1507 tree *overlaps_a,
1508 tree *overlaps_b,
1509 tree *last_conflicts)
1511 if (dump_file && (dump_flags & TDF_DETAILS))
1512 fprintf (dump_file, "(analyze_siv_subscript \n");
1514 if (evolution_function_is_constant_p (chrec_a)
1515 && evolution_function_is_affine_p (chrec_b))
1516 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
1517 overlaps_a, overlaps_b, last_conflicts);
1519 else if (evolution_function_is_affine_p (chrec_a)
1520 && evolution_function_is_constant_p (chrec_b))
1521 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
1522 overlaps_b, overlaps_a, last_conflicts);
1524 else if (evolution_function_is_affine_p (chrec_a)
1525 && evolution_function_is_affine_p (chrec_b))
1526 analyze_subscript_affine_affine (chrec_a, chrec_b,
1527 overlaps_a, overlaps_b, last_conflicts);
1528 else
1530 *overlaps_a = chrec_dont_know;
1531 *overlaps_b = chrec_dont_know;
1532 *last_conflicts = chrec_dont_know;
1535 if (dump_file && (dump_flags & TDF_DETAILS))
1536 fprintf (dump_file, ")\n");
1539 /* Return true when the evolution steps of an affine CHREC divide the
1540 constant CST. */
1542 static bool
1543 chrec_steps_divide_constant_p (tree chrec,
1544 tree cst)
1546 switch (TREE_CODE (chrec))
1548 case POLYNOMIAL_CHREC:
1549 return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst)
1550 && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
1552 default:
1553 /* On the initial condition, return true. */
1554 return true;
1558 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
1559 *OVERLAPS_B are initialized to the functions that describe the
1560 relation between the elements accessed twice by CHREC_A and
1561 CHREC_B. For k >= 0, the following property is verified:
1563 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1565 static void
1566 analyze_miv_subscript (tree chrec_a,
1567 tree chrec_b,
1568 tree *overlaps_a,
1569 tree *overlaps_b,
1570 tree *last_conflicts)
1572 /* FIXME: This is a MIV subscript, not yet handled.
1573 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
1574 (A[i] vs. A[j]).
1576 In the SIV test we had to solve a Diophantine equation with two
1577 variables. In the MIV case we have to solve a Diophantine
1578 equation with 2*n variables (if the subscript uses n IVs).
1580 tree difference;
1582 if (dump_file && (dump_flags & TDF_DETAILS))
1583 fprintf (dump_file, "(analyze_miv_subscript \n");
1585 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
1587 if (chrec_zerop (difference))
1589 /* Access functions are the same: all the elements are accessed
1590 in the same order. */
1591 *overlaps_a = integer_zero_node;
1592 *overlaps_b = integer_zero_node;
1593 *last_conflicts = number_of_iterations_in_loop
1594 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
1597 else if (evolution_function_is_constant_p (difference)
1598 /* For the moment, the following is verified:
1599 evolution_function_is_affine_multivariate_p (chrec_a) */
1600 && !chrec_steps_divide_constant_p (chrec_a, difference))
1602 /* testsuite/.../ssa-chrec-33.c
1603 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
1605 The difference is 1, and the evolution steps are equal to 2,
1606 consequently there are no overlapping elements. */
1607 *overlaps_a = chrec_known;
1608 *overlaps_b = chrec_known;
1609 *last_conflicts = integer_zero_node;
1612 else if (evolution_function_is_affine_multivariate_p (chrec_a)
1613 && evolution_function_is_affine_multivariate_p (chrec_b))
1615 /* testsuite/.../ssa-chrec-35.c
1616 {0, +, 1}_2 vs. {0, +, 1}_3
1617 the overlapping elements are respectively located at iterations:
1618 {0, +, 1}_x and {0, +, 1}_x,
1619 in other words, we have the equality:
1620 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
1622 Other examples:
1623 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
1624 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
1626 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
1627 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
1629 analyze_subscript_affine_affine (chrec_a, chrec_b,
1630 overlaps_a, overlaps_b, last_conflicts);
1633 else
1635 /* When the analysis is too difficult, answer "don't know". */
1636 *overlaps_a = chrec_dont_know;
1637 *overlaps_b = chrec_dont_know;
1638 *last_conflicts = chrec_dont_know;
1641 if (dump_file && (dump_flags & TDF_DETAILS))
1642 fprintf (dump_file, ")\n");
1645 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
1646 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
1647 two functions that describe the iterations that contain conflicting
1648 elements.
1650 Remark: For an integer k >= 0, the following equality is true:
1652 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
1655 static void
1656 analyze_overlapping_iterations (tree chrec_a,
1657 tree chrec_b,
1658 tree *overlap_iterations_a,
1659 tree *overlap_iterations_b,
1660 tree *last_conflicts)
1662 if (dump_file && (dump_flags & TDF_DETAILS))
1664 fprintf (dump_file, "(analyze_overlapping_iterations \n");
1665 fprintf (dump_file, " (chrec_a = ");
1666 print_generic_expr (dump_file, chrec_a, 0);
1667 fprintf (dump_file, ")\n chrec_b = ");
1668 print_generic_expr (dump_file, chrec_b, 0);
1669 fprintf (dump_file, ")\n");
1672 if (chrec_a == NULL_TREE
1673 || chrec_b == NULL_TREE
1674 || chrec_contains_undetermined (chrec_a)
1675 || chrec_contains_undetermined (chrec_b)
1676 || chrec_contains_symbols (chrec_a)
1677 || chrec_contains_symbols (chrec_b))
1679 *overlap_iterations_a = chrec_dont_know;
1680 *overlap_iterations_b = chrec_dont_know;
1683 else if (ziv_subscript_p (chrec_a, chrec_b))
1684 analyze_ziv_subscript (chrec_a, chrec_b,
1685 overlap_iterations_a, overlap_iterations_b,
1686 last_conflicts);
1688 else if (siv_subscript_p (chrec_a, chrec_b))
1689 analyze_siv_subscript (chrec_a, chrec_b,
1690 overlap_iterations_a, overlap_iterations_b,
1691 last_conflicts);
1693 else
1694 analyze_miv_subscript (chrec_a, chrec_b,
1695 overlap_iterations_a, overlap_iterations_b,
1696 last_conflicts);
1698 if (dump_file && (dump_flags & TDF_DETAILS))
1700 fprintf (dump_file, " (overlap_iterations_a = ");
1701 print_generic_expr (dump_file, *overlap_iterations_a, 0);
1702 fprintf (dump_file, ")\n (overlap_iterations_b = ");
1703 print_generic_expr (dump_file, *overlap_iterations_b, 0);
1704 fprintf (dump_file, ")\n");
1710 /* This section contains the affine functions dependences detector. */
1712 /* Computes the conflicting iterations, and initialize DDR. */
1714 static void
1715 subscript_dependence_tester (struct data_dependence_relation *ddr)
1717 unsigned int i;
1718 struct data_reference *dra = DDR_A (ddr);
1719 struct data_reference *drb = DDR_B (ddr);
1720 tree last_conflicts;
1722 if (dump_file && (dump_flags & TDF_DETAILS))
1723 fprintf (dump_file, "(subscript_dependence_tester \n");
1725 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1727 tree overlaps_a, overlaps_b;
1728 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1730 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
1731 DR_ACCESS_FN (drb, i),
1732 &overlaps_a, &overlaps_b,
1733 &last_conflicts);
1735 if (chrec_contains_undetermined (overlaps_a)
1736 || chrec_contains_undetermined (overlaps_b))
1738 finalize_ddr_dependent (ddr, chrec_dont_know);
1739 break;
1742 else if (overlaps_a == chrec_known
1743 || overlaps_b == chrec_known)
1745 finalize_ddr_dependent (ddr, chrec_known);
1746 break;
1749 else
1751 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
1752 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
1753 SUB_LAST_CONFLICT (subscript) = last_conflicts;
1757 if (dump_file && (dump_flags & TDF_DETAILS))
1758 fprintf (dump_file, ")\n");
1761 /* Compute the classic per loop distance vector.
1763 DDR is the data dependence relation to build a vector from.
1764 NB_LOOPS is the total number of loops we are considering.
1765 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
1766 loop nest.
1767 Return FALSE if the dependence relation is outside of the loop nest
1768 starting at FIRST_LOOP_DEPTH.
1769 Return TRUE otherwise. */
1771 bool
1772 build_classic_dist_vector (struct data_dependence_relation *ddr,
1773 int nb_loops, int first_loop_depth)
1775 unsigned i;
1776 lambda_vector dist_v, init_v;
1778 dist_v = lambda_vector_new (nb_loops);
1779 init_v = lambda_vector_new (nb_loops);
1780 lambda_vector_clear (dist_v, nb_loops);
1781 lambda_vector_clear (init_v, nb_loops);
1783 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
1784 return true;
1786 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1788 tree access_fn_a, access_fn_b;
1789 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1791 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
1793 non_affine_dependence_relation (ddr);
1794 return true;
1797 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
1798 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
1800 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
1801 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
1803 int dist, loop_nb, loop_depth;
1804 int loop_nb_a = CHREC_VARIABLE (access_fn_a);
1805 int loop_nb_b = CHREC_VARIABLE (access_fn_b);
1806 struct loop *loop_a = current_loops->parray[loop_nb_a];
1807 struct loop *loop_b = current_loops->parray[loop_nb_b];
1809 /* If the loop for either variable is at a lower depth than
1810 the first_loop's depth, then we can't possibly have a
1811 dependency at this level of the loop. */
1813 if (loop_a->depth < first_loop_depth
1814 || loop_b->depth < first_loop_depth)
1815 return false;
1817 if (loop_nb_a != loop_nb_b
1818 && !flow_loop_nested_p (loop_a, loop_b)
1819 && !flow_loop_nested_p (loop_b, loop_a))
1821 /* Example: when there are two consecutive loops,
1823 | loop_1
1824 | A[{0, +, 1}_1]
1825 | endloop_1
1826 | loop_2
1827 | A[{0, +, 1}_2]
1828 | endloop_2
1830 the dependence relation cannot be captured by the
1831 distance abstraction. */
1832 non_affine_dependence_relation (ddr);
1833 return true;
1836 /* The dependence is carried by the outermost loop. Example:
1837 | loop_1
1838 | A[{4, +, 1}_1]
1839 | loop_2
1840 | A[{5, +, 1}_2]
1841 | endloop_2
1842 | endloop_1
1843 In this case, the dependence is carried by loop_1. */
1844 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
1845 loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
1847 /* If the loop number is still greater than the number of
1848 loops we've been asked to analyze, or negative,
1849 something is borked. */
1850 gcc_assert (loop_depth >= 0);
1851 gcc_assert (loop_depth < nb_loops);
1852 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
1854 non_affine_dependence_relation (ddr);
1855 return true;
1858 dist = int_cst_value (SUB_DISTANCE (subscript));
1860 /* This is the subscript coupling test.
1861 | loop i = 0, N, 1
1862 | T[i+1][i] = ...
1863 | ... = T[i][i]
1864 | endloop
1865 There is no dependence. */
1866 if (init_v[loop_depth] != 0
1867 && dist_v[loop_depth] != dist)
1869 finalize_ddr_dependent (ddr, chrec_known);
1870 return true;
1873 dist_v[loop_depth] = dist;
1874 init_v[loop_depth] = 1;
1878 /* There is a distance of 1 on all the outer loops:
1880 Example: there is a dependence of distance 1 on loop_1 for the array A.
1881 | loop_1
1882 | A[5] = ...
1883 | endloop
1886 struct loop *lca, *loop_a, *loop_b;
1887 struct data_reference *a = DDR_A (ddr);
1888 struct data_reference *b = DDR_B (ddr);
1889 int lca_depth;
1890 loop_a = loop_containing_stmt (DR_STMT (a));
1891 loop_b = loop_containing_stmt (DR_STMT (b));
1893 /* Get the common ancestor loop. */
1894 lca = find_common_loop (loop_a, loop_b);
1896 lca_depth = lca->depth;
1897 lca_depth -= first_loop_depth;
1898 gcc_assert (lca_depth >= 0);
1899 gcc_assert (lca_depth < nb_loops);
1901 /* For each outer loop where init_v is not set, the accesses are
1902 in dependence of distance 1 in the loop. */
1903 if (lca != loop_a
1904 && lca != loop_b
1905 && init_v[lca_depth] == 0)
1906 dist_v[lca_depth] = 1;
1908 lca = lca->outer;
1910 if (lca)
1912 lca_depth = lca->depth - first_loop_depth;
1913 while (lca->depth != 0)
1915 /* If we're considering just a sub-nest, then don't record
1916 any information on the outer loops. */
1917 if (lca_depth < 0)
1918 break;
1920 gcc_assert (lca_depth < nb_loops);
1922 if (init_v[lca_depth] == 0)
1923 dist_v[lca_depth] = 1;
1924 lca = lca->outer;
1925 lca_depth = lca->depth - first_loop_depth;
1931 DDR_DIST_VECT (ddr) = dist_v;
1932 DDR_SIZE_VECT (ddr) = nb_loops;
1933 return true;
1936 /* Compute the classic per loop direction vector.
1938 DDR is the data dependence relation to build a vector from.
1939 NB_LOOPS is the total number of loops we are considering.
1940 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
1941 loop nest.
1942 Return FALSE if the dependence relation is outside of the loop nest
1943 at FIRST_LOOP_DEPTH.
1944 Return TRUE otherwise. */
1946 static bool
1947 build_classic_dir_vector (struct data_dependence_relation *ddr,
1948 int nb_loops, int first_loop_depth)
1950 unsigned i;
1951 lambda_vector dir_v, init_v;
1953 dir_v = lambda_vector_new (nb_loops);
1954 init_v = lambda_vector_new (nb_loops);
1955 lambda_vector_clear (dir_v, nb_loops);
1956 lambda_vector_clear (init_v, nb_loops);
1958 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
1959 return true;
1961 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1963 tree access_fn_a, access_fn_b;
1964 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1966 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
1968 non_affine_dependence_relation (ddr);
1969 return true;
1972 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
1973 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
1974 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
1975 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
1977 int dist, loop_nb, loop_depth;
1978 enum data_dependence_direction dir = dir_star;
1979 int loop_nb_a = CHREC_VARIABLE (access_fn_a);
1980 int loop_nb_b = CHREC_VARIABLE (access_fn_b);
1981 struct loop *loop_a = current_loops->parray[loop_nb_a];
1982 struct loop *loop_b = current_loops->parray[loop_nb_b];
1984 /* If the loop for either variable is at a lower depth than
1985 the first_loop's depth, then we can't possibly have a
1986 dependency at this level of the loop. */
1988 if (loop_a->depth < first_loop_depth
1989 || loop_b->depth < first_loop_depth)
1990 return false;
1992 if (loop_nb_a != loop_nb_b
1993 && !flow_loop_nested_p (loop_a, loop_b)
1994 && !flow_loop_nested_p (loop_b, loop_a))
1996 /* Example: when there are two consecutive loops,
1998 | loop_1
1999 | A[{0, +, 1}_1]
2000 | endloop_1
2001 | loop_2
2002 | A[{0, +, 1}_2]
2003 | endloop_2
2005 the dependence relation cannot be captured by the
2006 distance abstraction. */
2007 non_affine_dependence_relation (ddr);
2008 return true;
2011 /* The dependence is carried by the outermost loop. Example:
2012 | loop_1
2013 | A[{4, +, 1}_1]
2014 | loop_2
2015 | A[{5, +, 1}_2]
2016 | endloop_2
2017 | endloop_1
2018 In this case, the dependence is carried by loop_1. */
2019 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
2020 loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
2022 /* If the loop number is still greater than the number of
2023 loops we've been asked to analyze, or negative,
2024 something is borked. */
2025 gcc_assert (loop_depth >= 0);
2026 gcc_assert (loop_depth < nb_loops);
2028 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2030 non_affine_dependence_relation (ddr);
2031 return true;
2034 dist = int_cst_value (SUB_DISTANCE (subscript));
2036 if (dist == 0)
2037 dir = dir_equal;
2038 else if (dist > 0)
2039 dir = dir_positive;
2040 else if (dist < 0)
2041 dir = dir_negative;
2043 /* This is the subscript coupling test.
2044 | loop i = 0, N, 1
2045 | T[i+1][i] = ...
2046 | ... = T[i][i]
2047 | endloop
2048 There is no dependence. */
2049 if (init_v[loop_depth] != 0
2050 && dir != dir_star
2051 && (enum data_dependence_direction) dir_v[loop_depth] != dir
2052 && (enum data_dependence_direction) dir_v[loop_depth] != dir_star)
2054 finalize_ddr_dependent (ddr, chrec_known);
2055 return true;
2058 dir_v[loop_depth] = dir;
2059 init_v[loop_depth] = 1;
2063 /* There is a distance of 1 on all the outer loops:
2065 Example: there is a dependence of distance 1 on loop_1 for the array A.
2066 | loop_1
2067 | A[5] = ...
2068 | endloop
2071 struct loop *lca, *loop_a, *loop_b;
2072 struct data_reference *a = DDR_A (ddr);
2073 struct data_reference *b = DDR_B (ddr);
2074 int lca_depth;
2075 loop_a = loop_containing_stmt (DR_STMT (a));
2076 loop_b = loop_containing_stmt (DR_STMT (b));
2078 /* Get the common ancestor loop. */
2079 lca = find_common_loop (loop_a, loop_b);
2080 lca_depth = lca->depth - first_loop_depth;
2082 gcc_assert (lca_depth >= 0);
2083 gcc_assert (lca_depth < nb_loops);
2085 /* For each outer loop where init_v is not set, the accesses are
2086 in dependence of distance 1 in the loop. */
2087 if (lca != loop_a
2088 && lca != loop_b
2089 && init_v[lca_depth] == 0)
2090 dir_v[lca_depth] = dir_positive;
2092 lca = lca->outer;
2093 if (lca)
2095 lca_depth = lca->depth - first_loop_depth;
2096 while (lca->depth != 0)
2098 /* If we're considering just a sub-nest, then don't record
2099 any information on the outer loops. */
2100 if (lca_depth < 0)
2101 break;
2103 gcc_assert (lca_depth < nb_loops);
2105 if (init_v[lca_depth] == 0)
2106 dir_v[lca_depth] = dir_positive;
2107 lca = lca->outer;
2108 lca_depth = lca->depth - first_loop_depth;
2114 DDR_DIR_VECT (ddr) = dir_v;
2115 DDR_SIZE_VECT (ddr) = nb_loops;
2116 return true;
2119 /* Returns true when all the access functions of A are affine or
2120 constant. */
2122 static bool
2123 access_functions_are_affine_or_constant_p (struct data_reference *a)
2125 unsigned int i;
2126 VEC(tree,heap) **fns = &DR_ACCESS_FNS (a);
2127 tree t;
2129 for (i = 0; VEC_iterate (tree, *fns, i, t); i++)
2130 if (!evolution_function_is_constant_p (t)
2131 && !evolution_function_is_affine_multivariate_p (t))
2132 return false;
2134 return true;
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
2140 relation.
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
2144 subscript. */
2146 void
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
2171 "don't know". */
2172 else
2173 finalize_ddr_dependent (ddr, chrec_dont_know);
2176 if (dump_file && (dump_flags & TDF_DETAILS))
2177 fprintf (dump_file, ")\n");
2180 /* This computes the dependence relation for the same data
2181 reference into DDR. */
2183 static void
2184 compute_self_dependence (struct data_dependence_relation *ddr)
2186 unsigned int i;
2188 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2190 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
2192 /* The accessed index overlaps for each iteration. */
2193 SUB_CONFLICTS_IN_A (subscript) = integer_zero_node;
2194 SUB_CONFLICTS_IN_B (subscript) = integer_zero_node;
2195 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
2200 typedef struct data_dependence_relation *ddr_p;
2201 DEF_VEC_P(ddr_p);
2202 DEF_VEC_ALLOC_P(ddr_p,heap);
2204 /* Compute a subset of the data dependence relation graph. Don't
2205 compute read-read relations, and avoid the computation of the
2206 opposite relation, i.e. when AB has been computed, don't compute BA.
2207 DATAREFS contains a list of data references, and the result is set
2208 in DEPENDENCE_RELATIONS. */
2210 static void
2211 compute_all_dependences (varray_type datarefs,
2212 VEC(ddr_p,heap) **dependence_relations)
2214 unsigned int i, j, N;
2216 N = VARRAY_ACTIVE_SIZE (datarefs);
2218 /* Note that we specifically skip i == j because it's a self dependence, and
2219 use compute_self_dependence below. */
2221 for (i = 0; i < N; i++)
2222 for (j = i + 1; j < N; j++)
2224 struct data_reference *a, *b;
2225 struct data_dependence_relation *ddr;
2227 a = VARRAY_GENERIC_PTR (datarefs, i);
2228 b = VARRAY_GENERIC_PTR (datarefs, j);
2229 ddr = initialize_data_dependence_relation (a, b);
2231 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
2232 compute_affine_dependence (ddr);
2233 compute_subscript_distance (ddr);
2236 /* Compute self dependence relation of each dataref to itself. */
2238 for (i = 0; i < N; i++)
2240 struct data_reference *a, *b;
2241 struct data_dependence_relation *ddr;
2243 a = VARRAY_GENERIC_PTR (datarefs, i);
2244 b = VARRAY_GENERIC_PTR (datarefs, i);
2245 ddr = initialize_data_dependence_relation (a, b);
2247 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
2248 compute_self_dependence (ddr);
2249 compute_subscript_distance (ddr);
2253 /* Search the data references in LOOP, and record the information into
2254 DATAREFS. Returns chrec_dont_know when failing to analyze a
2255 difficult case, returns NULL_TREE otherwise.
2257 TODO: This function should be made smarter so that it can handle address
2258 arithmetic as if they were array accesses, etc. */
2260 tree
2261 find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
2263 basic_block bb, *bbs;
2264 unsigned int i;
2265 block_stmt_iterator bsi;
2267 bbs = get_loop_body (loop);
2269 for (i = 0; i < loop->num_nodes; i++)
2271 bb = bbs[i];
2273 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2275 tree stmt = bsi_stmt (bsi);
2277 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
2278 Calls have side-effects, except those to const or pure
2279 functions. */
2280 if ((TREE_CODE (stmt) == CALL_EXPR
2281 && !(call_expr_flags (stmt) & (ECF_CONST | ECF_PURE)))
2282 || (TREE_CODE (stmt) == ASM_EXPR
2283 && ASM_VOLATILE_P (stmt)))
2284 goto insert_dont_know_node;
2286 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
2287 continue;
2289 switch (TREE_CODE (stmt))
2291 case MODIFY_EXPR:
2292 if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF)
2293 VARRAY_PUSH_GENERIC_PTR
2294 (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 0),
2295 false));
2297 if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF)
2298 VARRAY_PUSH_GENERIC_PTR
2299 (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1),
2300 true));
2302 if (TREE_CODE (TREE_OPERAND (stmt, 0)) != ARRAY_REF
2303 && TREE_CODE (TREE_OPERAND (stmt, 1)) != ARRAY_REF)
2304 goto insert_dont_know_node;
2306 break;
2308 case CALL_EXPR:
2310 tree args;
2311 bool one_inserted = false;
2313 for (args = TREE_OPERAND (stmt, 1); args; args = TREE_CHAIN (args))
2314 if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF)
2316 VARRAY_PUSH_GENERIC_PTR
2317 (*datarefs, analyze_array (stmt, TREE_VALUE (args), true));
2318 one_inserted = true;
2321 if (!one_inserted)
2322 goto insert_dont_know_node;
2324 break;
2327 default:
2329 struct data_reference *res;
2331 insert_dont_know_node:;
2332 res = xmalloc (sizeof (struct data_reference));
2333 DR_STMT (res) = NULL_TREE;
2334 DR_REF (res) = NULL_TREE;
2335 DR_ACCESS_FNS (res) = NULL;
2336 DR_BASE_NAME (res) = NULL;
2337 DR_IS_READ (res) = false;
2338 VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
2340 free (bbs);
2341 return chrec_dont_know;
2345 /* When there are no defs in the loop, the loop is parallel. */
2346 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
2347 loop->parallel_p = false;
2350 if (chrec_contains_undetermined (loop->estimated_nb_iterations))
2351 compute_estimated_nb_iterations (loop);
2354 free (bbs);
2356 return NULL_TREE;
2361 /* This section contains all the entry points. */
2363 /* Given a loop nest LOOP, the following vectors are returned:
2364 *DATAREFS is initialized to all the array elements contained in this loop,
2365 *DEPENDENCE_RELATIONS contains the relations between the data references. */
2367 void
2368 compute_data_dependences_for_loop (unsigned nb_loops,
2369 struct loop *loop,
2370 varray_type *datarefs,
2371 varray_type *dependence_relations)
2373 unsigned int i;
2374 VEC(ddr_p,heap) *allrelations;
2375 struct data_dependence_relation *ddr;
2377 /* If one of the data references is not computable, give up without
2378 spending time to compute other dependences. */
2379 if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
2381 struct data_dependence_relation *ddr;
2383 /* Insert a single relation into dependence_relations:
2384 chrec_dont_know. */
2385 ddr = initialize_data_dependence_relation (NULL, NULL);
2386 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
2387 build_classic_dist_vector (ddr, nb_loops, loop->depth);
2388 build_classic_dir_vector (ddr, nb_loops, loop->depth);
2389 return;
2392 allrelations = NULL;
2393 compute_all_dependences (*datarefs, &allrelations);
2395 for (i = 0; VEC_iterate (ddr_p, allrelations, i, ddr); i++)
2397 if (build_classic_dist_vector (ddr, nb_loops, loop->depth))
2399 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
2400 build_classic_dir_vector (ddr, nb_loops, loop->depth);
2405 /* Entry point (for testing only). Analyze all the data references
2406 and the dependence relations.
2408 The data references are computed first.
2410 A relation on these nodes is represented by a complete graph. Some
2411 of the relations could be of no interest, thus the relations can be
2412 computed on demand.
2414 In the following function we compute all the relations. This is
2415 just a first implementation that is here for:
2416 - for showing how to ask for the dependence relations,
2417 - for the debugging the whole dependence graph,
2418 - for the dejagnu testcases and maintenance.
2420 It is possible to ask only for a part of the graph, avoiding to
2421 compute the whole dependence graph. The computed dependences are
2422 stored in a knowledge base (KB) such that later queries don't
2423 recompute the same information. The implementation of this KB is
2424 transparent to the optimizer, and thus the KB can be changed with a
2425 more efficient implementation, or the KB could be disabled. */
2427 void
2428 analyze_all_data_dependences (struct loops *loops)
2430 unsigned int i;
2431 varray_type datarefs;
2432 varray_type dependence_relations;
2433 int nb_data_refs = 10;
2435 VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
2436 VARRAY_GENERIC_PTR_INIT (dependence_relations,
2437 nb_data_refs * nb_data_refs,
2438 "dependence_relations");
2440 /* Compute DDs on the whole function. */
2441 compute_data_dependences_for_loop (loops->num, loops->parray[0],
2442 &datarefs, &dependence_relations);
2444 if (dump_file)
2446 dump_data_dependence_relations (dump_file, dependence_relations);
2447 fprintf (dump_file, "\n\n");
2449 if (dump_flags & TDF_DETAILS)
2450 dump_dist_dir_vectors (dump_file, dependence_relations);
2452 if (dump_flags & TDF_STATS)
2454 unsigned nb_top_relations = 0;
2455 unsigned nb_bot_relations = 0;
2456 unsigned nb_basename_differ = 0;
2457 unsigned nb_chrec_relations = 0;
2459 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
2461 struct data_dependence_relation *ddr;
2462 ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
2464 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
2465 nb_top_relations++;
2467 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
2469 struct data_reference *a = DDR_A (ddr);
2470 struct data_reference *b = DDR_B (ddr);
2471 bool differ_p;
2473 if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
2474 || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
2475 nb_basename_differ++;
2476 else
2477 nb_bot_relations++;
2480 else
2481 nb_chrec_relations++;
2484 gather_stats_on_scev_database ();
2488 free_dependence_relations (dependence_relations);
2489 free_data_refs (datarefs);
2492 /* Free the memory used by a data dependence relation DDR. */
2494 void
2495 free_dependence_relation (struct data_dependence_relation *ddr)
2497 if (ddr == NULL)
2498 return;
2500 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
2501 varray_clear (DDR_SUBSCRIPTS (ddr));
2502 free (ddr);
2505 /* Free the memory used by the data dependence relations from
2506 DEPENDENCE_RELATIONS. */
2508 void
2509 free_dependence_relations (varray_type dependence_relations)
2511 unsigned int i;
2512 if (dependence_relations == NULL)
2513 return;
2515 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
2516 free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
2517 varray_clear (dependence_relations);
2520 /* Free the memory used by the data references from DATAREFS. */
2522 void
2523 free_data_refs (varray_type datarefs)
2525 unsigned int i;
2527 if (datarefs == NULL)
2528 return;
2530 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
2532 struct data_reference *dr = (struct data_reference *)
2533 VARRAY_GENERIC_PTR (datarefs, i);
2534 if (dr)
2536 VEC_free (tree, heap, DR_ACCESS_FNS (dr));
2537 free (dr);
2540 varray_clear (datarefs);