1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 /* This pass walks a given loop structure searching for array
23 references. The information about the array accesses is recorded
24 in DATA_REFERENCE structures.
26 The basic test for determining the dependences is:
27 given two access functions chrec1 and chrec2 to a same array, and
28 x and y two vectors from the iteration domain, the same element of
29 the array is accessed twice at iterations x and y if and only if:
30 | chrec1 (x) == chrec2 (y).
32 The goals of this analysis are:
34 - to determine the independence: the relation between two
35 independent accesses is qualified with the chrec_known (this
36 information allows a loop parallelization),
38 - when two data references access the same data, to qualify the
39 dependence relation with classic dependence representations:
43 - loop carried level dependence
44 - polyhedron dependence
45 or with the chains of recurrences based representation,
47 - to define a knowledge base for storing the data dependence
50 - to define an interface to access this data.
55 - subscript: given two array accesses a subscript is the tuple
56 composed of the access functions for a given dimension. Example:
57 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
58 (f1, g1), (f2, g2), (f3, g3).
60 - Diophantine equation: an equation whose coefficients and
61 solutions are integer constants, for example the equation
63 has an integer solution x = 1 and y = -1.
67 - "Advanced Compilation for High Performance Computing" by Randy
68 Allen and Ken Kennedy.
69 http://citeseer.ist.psu.edu/goff91practical.html
71 - "Loop Transformations for Restructuring Compilers - The Foundations"
79 #include "coretypes.h"
84 /* These RTL headers are needed for basic-block.h. */
86 #include "basic-block.h"
87 #include "diagnostic.h"
88 #include "tree-flow.h"
89 #include "tree-dump.h"
92 #include "tree-chrec.h"
93 #include "tree-data-ref.h"
94 #include "tree-scalar-evolution.h"
95 #include "tree-pass.h"
97 static tree object_analysis (tree, tree, bool, struct data_reference **,
98 tree *, tree *, tree *, tree *, tree *,
99 struct ptr_info_def **, subvar_t *);
100 static struct data_reference * init_data_ref (tree, tree, tree, tree, bool,
101 tree, tree, tree, tree, tree,
102 struct ptr_info_def *,
105 /* Determine if PTR and DECL may alias, the result is put in ALIASED.
106 Return FALSE if there is no type memory tag for PTR.
109 ptr_decl_may_alias_p (tree ptr, tree decl,
110 struct data_reference *ptr_dr,
115 gcc_assert (TREE_CODE (ptr) == SSA_NAME && DECL_P (decl));
117 tag = get_var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
119 tag = DR_MEMTAG (ptr_dr);
123 *aliased = is_aliased_with (tag, decl);
128 /* Determine if two pointers may alias, the result is put in ALIASED.
129 Return FALSE if there is no type memory tag for one of the pointers.
132 ptr_ptr_may_alias_p (tree ptr_a, tree ptr_b,
133 struct data_reference *dra,
134 struct data_reference *drb,
139 tag_a = get_var_ann (SSA_NAME_VAR (ptr_a))->type_mem_tag;
141 tag_a = DR_MEMTAG (dra);
144 tag_b = get_var_ann (SSA_NAME_VAR (ptr_b))->type_mem_tag;
146 tag_b = DR_MEMTAG (drb);
149 *aliased = (tag_a == tag_b);
154 /* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED.
155 Return FALSE if there is no type memory tag for one of the symbols.
158 may_alias_p (tree base_a, tree base_b,
159 struct data_reference *dra,
160 struct data_reference *drb,
163 if (TREE_CODE (base_a) == ADDR_EXPR || TREE_CODE (base_b) == ADDR_EXPR)
165 if (TREE_CODE (base_a) == ADDR_EXPR && TREE_CODE (base_b) == ADDR_EXPR)
167 *aliased = (TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0));
170 if (TREE_CODE (base_a) == ADDR_EXPR)
171 return ptr_decl_may_alias_p (base_b, TREE_OPERAND (base_a, 0), drb,
174 return ptr_decl_may_alias_p (base_a, TREE_OPERAND (base_b, 0), dra,
178 return ptr_ptr_may_alias_p (base_a, base_b, dra, drb, aliased);
182 /* Determine if a pointer (BASE_A) and a record/union access (BASE_B)
183 are not aliased. Return TRUE if they differ. */
185 record_ptr_differ_p (struct data_reference *dra,
186 struct data_reference *drb)
189 tree base_a = DR_BASE_OBJECT (dra);
190 tree base_b = DR_BASE_OBJECT (drb);
192 if (TREE_CODE (base_b) != COMPONENT_REF)
195 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
196 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
197 Probably will be unnecessary with struct alias analysis. */
198 while (TREE_CODE (base_b) == COMPONENT_REF)
199 base_b = TREE_OPERAND (base_b, 0);
200 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
202 if (TREE_CODE (base_a) == INDIRECT_REF
203 && ((TREE_CODE (base_b) == VAR_DECL
204 && (ptr_decl_may_alias_p (TREE_OPERAND (base_a, 0), base_b, dra,
207 || (TREE_CODE (base_b) == INDIRECT_REF
208 && (ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0),
209 TREE_OPERAND (base_b, 0), dra, drb,
218 /* Determine if an array access (BASE_A) and a record/union access (BASE_B)
219 are not aliased. Return TRUE if they differ. */
221 record_array_differ_p (struct data_reference *dra,
222 struct data_reference *drb)
225 tree base_a = DR_BASE_OBJECT (dra);
226 tree base_b = DR_BASE_OBJECT (drb);
228 if (TREE_CODE (base_b) != COMPONENT_REF)
231 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
232 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
233 Probably will be unnecessary with struct alias analysis. */
234 while (TREE_CODE (base_b) == COMPONENT_REF)
235 base_b = TREE_OPERAND (base_b, 0);
237 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
238 (a[i]). In case of p->c[i] use alias analysis to verify that p is not
240 if (TREE_CODE (base_a) == VAR_DECL
241 && (TREE_CODE (base_b) == VAR_DECL
242 || (TREE_CODE (base_b) == INDIRECT_REF
243 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb,
252 /* Determine if an array access (BASE_A) and a pointer (BASE_B)
253 are not aliased. Return TRUE if they differ. */
255 array_ptr_differ_p (tree base_a, tree base_b,
256 struct data_reference *drb)
260 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
261 help of alias analysis that p is not pointing to a. */
262 if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == INDIRECT_REF
263 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, &aliased)
271 /* This is the simplest data dependence test: determines whether the
272 data references A and B access the same array/region. Returns
273 false when the property is not computable at compile time.
274 Otherwise return true, and DIFFER_P will record the result. This
275 utility will not be necessary when alias_sets_conflict_p will be
276 less conservative. */
279 base_object_differ_p (struct data_reference *a,
280 struct data_reference *b,
283 tree base_a = DR_BASE_OBJECT (a);
284 tree base_b = DR_BASE_OBJECT (b);
287 if (!base_a || !base_b)
290 /* Determine if same base. Example: for the array accesses
291 a[i], b[i] or pointer accesses *a, *b, bases are a, b. */
292 if (base_a == base_b)
298 /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
300 if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
301 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0))
307 /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */
308 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
309 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)
310 && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1))
317 /* Determine if different bases. */
319 /* At this point we know that base_a != base_b. However, pointer
320 accesses of the form x=(*p) and y=(*q), whose bases are p and q,
321 may still be pointing to the same base. In SSAed GIMPLE p and q will
322 be SSA_NAMES in this case. Therefore, here we check if they are
323 really two different declarations. */
324 if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
330 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
331 help of alias analysis that p is not pointing to a. */
332 if (array_ptr_differ_p (base_a, base_b, b)
333 || array_ptr_differ_p (base_b, base_a, a))
339 /* If the bases are pointers ((*q)[i] and (*p)[i]), we check with the
340 help of alias analysis they don't point to the same bases. */
341 if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
342 && (may_alias_p (TREE_OPERAND (base_a, 0), TREE_OPERAND (base_b, 0), a, b,
350 /* Compare two record/union bases s.a and t.b: s != t or (a != b and
351 s and t are not unions). */
352 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
353 && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
354 && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
355 && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
356 || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE
357 && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
358 && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
364 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
366 if (record_ptr_differ_p (a, b) || record_ptr_differ_p (b, a))
372 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
373 (a[i]). In case of p->c[i] use alias analysis to verify that p is not
375 if (record_array_differ_p (a, b) || record_array_differ_p (b, a))
384 /* Function base_addr_differ_p.
386 This is the simplest data dependence test: determines whether the
387 data references A and B access the same array/region. Returns
388 false when the property is not computable at compile time.
389 Otherwise return true, and DIFFER_P will record the result. This
390 utility will not be necessary when alias_sets_conflict_p will be
391 less conservative. */
395 base_addr_differ_p (struct data_reference *dra,
396 struct data_reference *drb,
399 tree addr_a = DR_BASE_ADDRESS (dra);
400 tree addr_b = DR_BASE_ADDRESS (drb);
404 if (!addr_a || !addr_b)
407 type_a = TREE_TYPE (addr_a);
408 type_b = TREE_TYPE (addr_b);
410 gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
412 /* Compare base objects first if possible. If DR_BASE_OBJECT is NULL, it means
413 that the data-ref is of INDIRECT_REF, and alias analysis will be applied to
414 reveal the dependence. */
415 if (DR_BASE_OBJECT (dra) && DR_BASE_OBJECT (drb))
416 return base_object_differ_p (dra, drb, differ_p);
418 /* If base addresses are the same, we check the offsets, since the access of
419 the data-ref is described by {base addr + offset} and its access function,
420 i.e., in order to decide whether the bases of data-refs are the same we
421 compare both base addresses and offsets. */
423 || (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR
424 && TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0)))
426 /* Compare offsets. */
427 tree offset_a = DR_OFFSET (dra);
428 tree offset_b = DR_OFFSET (drb);
430 gcc_assert (!DR_BASE_OBJECT (dra) && !DR_BASE_OBJECT (drb));
432 STRIP_NOPS (offset_a);
433 STRIP_NOPS (offset_b);
435 /* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle
437 if ((offset_a == offset_b)
438 || (TREE_CODE (offset_a) == MULT_EXPR
439 && TREE_CODE (offset_b) == MULT_EXPR
440 && TREE_OPERAND (offset_a, 0) == TREE_OPERAND (offset_b, 0)
441 && TREE_OPERAND (offset_a, 1) == TREE_OPERAND (offset_b, 1)))
448 /* Apply alias analysis. */
449 if (may_alias_p (addr_a, addr_b, dra, drb, &aliased) && !aliased)
455 /* An instruction writing through a restricted pointer is "independent" of any
456 instruction reading or writing through a different pointer, in the same
458 else if ((TYPE_RESTRICT (type_a) && !DR_IS_READ (dra))
459 || (TYPE_RESTRICT (type_b) && !DR_IS_READ (drb)))
468 /* Returns true iff A divides B. */
471 tree_fold_divides_p (tree type,
475 /* Determines whether (A == gcd (A, B)). */
477 (fold_build2 (MINUS_EXPR, type, a, tree_fold_gcd (a, b)));
480 /* Compute the greatest common denominator of two numbers using
481 Euclid's algorithm. */
502 /* Returns true iff A divides B. */
505 int_divides_p (int a, int b)
507 return ((b % a) == 0);
512 /* Dump into FILE all the data references from DATAREFS. */
515 dump_data_references (FILE *file,
516 varray_type datarefs)
520 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
521 dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i));
524 /* Dump into FILE all the dependence relations from DDR. */
527 dump_data_dependence_relations (FILE *file,
532 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++)
533 dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i));
536 /* Dump function for a DATA_REFERENCE structure. */
539 dump_data_reference (FILE *outf,
540 struct data_reference *dr)
544 fprintf (outf, "(Data Ref: \n stmt: ");
545 print_generic_stmt (outf, DR_STMT (dr), 0);
546 fprintf (outf, " ref: ");
547 print_generic_stmt (outf, DR_REF (dr), 0);
548 fprintf (outf, " base_name: ");
549 print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
551 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
553 fprintf (outf, " Access function %d: ", i);
554 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
556 fprintf (outf, ")\n");
559 /* Dump function for a SUBSCRIPT structure. */
562 dump_subscript (FILE *outf, struct subscript *subscript)
564 tree chrec = SUB_CONFLICTS_IN_A (subscript);
566 fprintf (outf, "\n (subscript \n");
567 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
568 print_generic_stmt (outf, chrec, 0);
569 if (chrec == chrec_known)
570 fprintf (outf, " (no dependence)\n");
571 else if (chrec_contains_undetermined (chrec))
572 fprintf (outf, " (don't know)\n");
575 tree last_iteration = SUB_LAST_CONFLICT (subscript);
576 fprintf (outf, " last_conflict: ");
577 print_generic_stmt (outf, last_iteration, 0);
580 chrec = SUB_CONFLICTS_IN_B (subscript);
581 fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
582 print_generic_stmt (outf, chrec, 0);
583 if (chrec == chrec_known)
584 fprintf (outf, " (no dependence)\n");
585 else if (chrec_contains_undetermined (chrec))
586 fprintf (outf, " (don't know)\n");
589 tree last_iteration = SUB_LAST_CONFLICT (subscript);
590 fprintf (outf, " last_conflict: ");
591 print_generic_stmt (outf, last_iteration, 0);
594 fprintf (outf, " (Subscript distance: ");
595 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
596 fprintf (outf, " )\n");
597 fprintf (outf, " )\n");
600 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
603 dump_data_dependence_relation (FILE *outf,
604 struct data_dependence_relation *ddr)
606 struct data_reference *dra, *drb;
610 fprintf (outf, "(Data Dep: \n");
611 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
612 fprintf (outf, " (don't know)\n");
614 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
615 fprintf (outf, " (no dependence)\n");
617 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
620 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
622 fprintf (outf, " access_fn_A: ");
623 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
624 fprintf (outf, " access_fn_B: ");
625 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
626 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
628 if (DDR_DIST_VECT (ddr))
630 fprintf (outf, " distance_vect: ");
631 print_lambda_vector (outf, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
633 if (DDR_DIR_VECT (ddr))
635 fprintf (outf, " direction_vect: ");
636 print_lambda_vector (outf, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
640 fprintf (outf, ")\n");
645 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
648 dump_data_dependence_direction (FILE *file,
649 enum data_dependence_direction dir)
665 case dir_positive_or_negative:
666 fprintf (file, "+-");
669 case dir_positive_or_equal:
670 fprintf (file, "+=");
673 case dir_negative_or_equal:
674 fprintf (file, "-=");
686 /* Dumps the distance and direction vectors in FILE. DDRS contains
687 the dependence relations, and VECT_SIZE is the size of the
688 dependence vectors, or in other words the number of loops in the
692 dump_dist_dir_vectors (FILE *file, varray_type ddrs)
696 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
698 struct data_dependence_relation *ddr =
699 (struct data_dependence_relation *)
700 VARRAY_GENERIC_PTR (ddrs, i);
701 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
702 && DDR_AFFINE_P (ddr))
704 fprintf (file, "DISTANCE_V (");
705 print_lambda_vector (file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
706 fprintf (file, ")\n");
707 fprintf (file, "DIRECTION_V (");
708 print_lambda_vector (file, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
709 fprintf (file, ")\n");
712 fprintf (file, "\n\n");
715 /* Dumps the data dependence relations DDRS in FILE. */
718 dump_ddrs (FILE *file, varray_type ddrs)
722 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
724 struct data_dependence_relation *ddr =
725 (struct data_dependence_relation *)
726 VARRAY_GENERIC_PTR (ddrs, i);
727 dump_data_dependence_relation (file, ddr);
729 fprintf (file, "\n\n");
734 /* Estimate the number of iterations from the size of the data and the
738 estimate_niter_from_size_of_data (struct loop *loop,
744 tree array_size, data_size, element_size;
747 init = initial_condition (access_fn);
748 step = evolution_part_in_loop_num (access_fn, loop->num);
750 array_size = TYPE_SIZE (TREE_TYPE (opnd0));
751 element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
752 if (array_size == NULL_TREE
753 || TREE_CODE (array_size) != INTEGER_CST
754 || TREE_CODE (element_size) != INTEGER_CST)
757 data_size = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
758 array_size, element_size);
760 if (init != NULL_TREE
762 && TREE_CODE (init) == INTEGER_CST
763 && TREE_CODE (step) == INTEGER_CST)
765 estimation = fold_build2 (CEIL_DIV_EXPR, integer_type_node,
766 fold_build2 (MINUS_EXPR, integer_type_node,
767 data_size, init), step);
769 record_estimate (loop, estimation, boolean_true_node, stmt);
773 /* Given an ARRAY_REF node REF, records its access functions.
774 Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
775 i.e. the constant "3", then recursively call the function on opnd0,
776 i.e. the ARRAY_REF "A[i]". The function returns the base name:
780 analyze_array_indexes (struct loop *loop,
781 VEC(tree,heap) **access_fns,
787 opnd0 = TREE_OPERAND (ref, 0);
788 opnd1 = TREE_OPERAND (ref, 1);
790 /* The detection of the evolution function for this data access is
791 postponed until the dependence test. This lazy strategy avoids
792 the computation of access functions that are of no interest for
794 access_fn = instantiate_parameters
795 (loop, analyze_scalar_evolution (loop, opnd1));
797 if (chrec_contains_undetermined (loop->estimated_nb_iterations))
798 estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
800 VEC_safe_push (tree, heap, *access_fns, access_fn);
802 /* Recursively record other array access functions. */
803 if (TREE_CODE (opnd0) == ARRAY_REF)
804 return analyze_array_indexes (loop, access_fns, opnd0, stmt);
806 /* Return the base name of the data access. */
811 /* For a data reference REF contained in the statement STMT, initialize
812 a DATA_REFERENCE structure, and return it. IS_READ flag has to be
813 set to true when REF is in the right hand side of an
816 struct data_reference *
817 analyze_array (tree stmt, tree ref, bool is_read)
819 struct data_reference *res;
820 VEC(tree,heap) *acc_fns;
822 if (dump_file && (dump_flags & TDF_DETAILS))
824 fprintf (dump_file, "(analyze_array \n");
825 fprintf (dump_file, " (ref = ");
826 print_generic_stmt (dump_file, ref, 0);
827 fprintf (dump_file, ")\n");
830 res = xmalloc (sizeof (struct data_reference));
832 DR_STMT (res) = stmt;
834 acc_fns = VEC_alloc (tree, heap, 3);
835 DR_BASE_OBJECT (res) = analyze_array_indexes
836 (loop_containing_stmt (stmt), &acc_fns, ref, stmt);
837 DR_TYPE (res) = ARRAY_REF_TYPE;
838 DR_SET_ACCESS_FNS (res, acc_fns);
839 DR_IS_READ (res) = is_read;
840 DR_BASE_ADDRESS (res) = NULL_TREE;
841 DR_OFFSET (res) = NULL_TREE;
842 DR_INIT (res) = NULL_TREE;
843 DR_STEP (res) = NULL_TREE;
844 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
845 DR_MEMTAG (res) = NULL_TREE;
846 DR_PTR_INFO (res) = NULL;
848 if (dump_file && (dump_flags & TDF_DETAILS))
849 fprintf (dump_file, ")\n");
855 /* Analyze an indirect memory reference, REF, that comes from STMT.
856 IS_READ is true if this is an indirect load, and false if it is
858 Return a new data reference structure representing the indirect_ref, or
859 NULL if we cannot describe the access function. */
861 static struct data_reference *
862 analyze_indirect_ref (tree stmt, tree ref, bool is_read)
864 struct loop *loop = loop_containing_stmt (stmt);
865 tree ptr_ref = TREE_OPERAND (ref, 0);
866 tree access_fn = analyze_scalar_evolution (loop, ptr_ref);
867 tree init = initial_condition_in_loop_num (access_fn, loop->num);
868 tree base_address = NULL_TREE, evolution, step = NULL_TREE;
869 struct ptr_info_def *ptr_info = NULL;
871 if (TREE_CODE (ptr_ref) == SSA_NAME)
872 ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
875 if (access_fn == chrec_dont_know || !init || init == chrec_dont_know)
877 if (dump_file && (dump_flags & TDF_DETAILS))
879 fprintf (dump_file, "\nBad access function of ptr: ");
880 print_generic_expr (dump_file, ref, TDF_SLIM);
881 fprintf (dump_file, "\n");
886 if (dump_file && (dump_flags & TDF_DETAILS))
888 fprintf (dump_file, "\nAccess function of ptr: ");
889 print_generic_expr (dump_file, access_fn, TDF_SLIM);
890 fprintf (dump_file, "\n");
893 if (!expr_invariant_in_loop_p (loop, init))
895 if (dump_file && (dump_flags & TDF_DETAILS))
896 fprintf (dump_file, "\ninitial condition is not loop invariant.\n");
901 evolution = evolution_part_in_loop_num (access_fn, loop->num);
902 if (evolution != chrec_dont_know)
905 step = ssize_int (0);
908 if (TREE_CODE (evolution) == INTEGER_CST)
909 step = fold_convert (ssizetype, evolution);
911 if (dump_file && (dump_flags & TDF_DETAILS))
912 fprintf (dump_file, "\nnon constant step for ptr access.\n");
916 if (dump_file && (dump_flags & TDF_DETAILS))
917 fprintf (dump_file, "\nunknown evolution of ptr.\n");
919 return init_data_ref (stmt, ref, NULL_TREE, access_fn, is_read, base_address,
920 NULL_TREE, step, NULL_TREE, NULL_TREE,
921 ptr_info, POINTER_REF_TYPE);
924 /* For a data reference REF contained in the statement STMT, initialize
925 a DATA_REFERENCE structure, and return it. */
927 struct data_reference *
928 init_data_ref (tree stmt,
938 struct ptr_info_def *ptr_info,
939 enum data_ref_type type)
941 struct data_reference *res;
942 VEC(tree,heap) *acc_fns;
944 if (dump_file && (dump_flags & TDF_DETAILS))
946 fprintf (dump_file, "(init_data_ref \n");
947 fprintf (dump_file, " (ref = ");
948 print_generic_stmt (dump_file, ref, 0);
949 fprintf (dump_file, ")\n");
952 res = xmalloc (sizeof (struct data_reference));
954 DR_STMT (res) = stmt;
956 DR_BASE_OBJECT (res) = base;
957 DR_TYPE (res) = type;
958 acc_fns = VEC_alloc (tree, heap, 3);
959 DR_SET_ACCESS_FNS (res, acc_fns);
960 VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
961 DR_IS_READ (res) = is_read;
962 DR_BASE_ADDRESS (res) = base_address;
963 DR_OFFSET (res) = init_offset;
964 DR_INIT (res) = NULL_TREE;
965 DR_STEP (res) = step;
966 DR_OFFSET_MISALIGNMENT (res) = misalign;
967 DR_MEMTAG (res) = memtag;
968 DR_PTR_INFO (res) = ptr_info;
970 if (dump_file && (dump_flags & TDF_DETAILS))
971 fprintf (dump_file, ")\n");
978 /* Function strip_conversions
980 Strip conversions that don't narrow the mode. */
983 strip_conversion (tree expr)
987 while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
989 to = TREE_TYPE (expr);
990 oprnd0 = TREE_OPERAND (expr, 0);
991 ti = TREE_TYPE (oprnd0);
993 if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti))
995 if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti)))
1004 /* Function analyze_offset_expr
1006 Given an offset expression EXPR received from get_inner_reference, analyze
1007 it and create an expression for INITIAL_OFFSET by substituting the variables
1008 of EXPR with initial_condition of the corresponding access_fn in the loop.
1011 for (j = 3; j < N; j++)
1014 For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be
1015 substituted, since its access_fn in the inner loop is i. 'j' will be
1016 substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
1019 Compute MISALIGN (the misalignment of the data reference initial access from
1020 its base). Misalignment can be calculated only if all the variables can be
1021 substituted with constants, otherwise, we record maximum possible alignment
1022 in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN
1023 will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be
1024 recorded in ALIGNED_TO.
1026 STEP is an evolution of the data reference in this loop in bytes.
1027 In the above example, STEP is C_j.
1029 Return FALSE, if the analysis fails, e.g., there is no access_fn for a
1030 variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO
1031 and STEP) are NULL_TREEs. Otherwise, return TRUE.
1036 analyze_offset_expr (tree expr,
1038 tree *initial_offset,
1045 tree left_offset = ssize_int (0);
1046 tree right_offset = ssize_int (0);
1047 tree left_misalign = ssize_int (0);
1048 tree right_misalign = ssize_int (0);
1049 tree left_step = ssize_int (0);
1050 tree right_step = ssize_int (0);
1051 enum tree_code code;
1052 tree init, evolution;
1053 tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE;
1056 *misalign = NULL_TREE;
1057 *aligned_to = NULL_TREE;
1058 *initial_offset = NULL_TREE;
1060 /* Strip conversions that don't narrow the mode. */
1061 expr = strip_conversion (expr);
1067 if (TREE_CODE (expr) == INTEGER_CST)
1069 *initial_offset = fold_convert (ssizetype, expr);
1070 *misalign = fold_convert (ssizetype, expr);
1071 *step = ssize_int (0);
1075 /* 2. Variable. Try to substitute with initial_condition of the corresponding
1076 access_fn in the current loop. */
1077 if (SSA_VAR_P (expr))
1079 tree access_fn = analyze_scalar_evolution (loop, expr);
1081 if (access_fn == chrec_dont_know)
1085 init = initial_condition_in_loop_num (access_fn, loop->num);
1086 if (init == expr && !expr_invariant_in_loop_p (loop, init))
1087 /* Not enough information: may be not loop invariant.
1088 E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
1089 initial_condition is D, but it depends on i - loop's induction
1093 evolution = evolution_part_in_loop_num (access_fn, loop->num);
1094 if (evolution && TREE_CODE (evolution) != INTEGER_CST)
1095 /* Evolution is not constant. */
1098 if (TREE_CODE (init) == INTEGER_CST)
1099 *misalign = fold_convert (ssizetype, init);
1101 /* Not constant, misalignment cannot be calculated. */
1102 *misalign = NULL_TREE;
1104 *initial_offset = fold_convert (ssizetype, init);
1106 *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
1110 /* Recursive computation. */
1111 if (!BINARY_CLASS_P (expr))
1113 /* We expect to get binary expressions (PLUS/MINUS and MULT). */
1114 if (dump_file && (dump_flags & TDF_DETAILS))
1116 fprintf (dump_file, "\nNot binary expression ");
1117 print_generic_expr (dump_file, expr, TDF_SLIM);
1118 fprintf (dump_file, "\n");
1122 oprnd0 = TREE_OPERAND (expr, 0);
1123 oprnd1 = TREE_OPERAND (expr, 1);
1125 if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign,
1126 &left_aligned_to, &left_step)
1127 || !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign,
1128 &right_aligned_to, &right_step))
1131 /* The type of the operation: plus, minus or mult. */
1132 code = TREE_CODE (expr);
1136 if (TREE_CODE (right_offset) != INTEGER_CST)
1137 /* RIGHT_OFFSET can be not constant. For example, for arrays of variable
1139 FORNOW: We don't support such cases. */
1142 /* Strip conversions that don't narrow the mode. */
1143 left_offset = strip_conversion (left_offset);
1146 /* Misalignment computation. */
1147 if (SSA_VAR_P (left_offset))
1149 /* If the left side contains variables that can't be substituted with
1150 constants, the misalignment is unknown. However, if the right side
1151 is a multiple of some alignment, we know that the expression is
1152 aligned to it. Therefore, we record such maximum possible value.
1154 *misalign = NULL_TREE;
1155 *aligned_to = ssize_int (highest_pow2_factor (right_offset));
1159 /* The left operand was successfully substituted with constant. */
1162 /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is
1164 *misalign = size_binop (code, left_misalign, right_misalign);
1165 if (left_aligned_to && right_aligned_to)
1166 *aligned_to = size_binop (MIN_EXPR, left_aligned_to,
1169 *aligned_to = left_aligned_to ?
1170 left_aligned_to : right_aligned_to;
1173 *misalign = NULL_TREE;
1176 /* Step calculation. */
1177 /* Multiply the step by the right operand. */
1178 *step = size_binop (MULT_EXPR, left_step, right_offset);
1183 /* Combine the recursive calculations for step and misalignment. */
1184 *step = size_binop (code, left_step, right_step);
1186 /* Unknown alignment. */
1187 if ((!left_misalign && !left_aligned_to)
1188 || (!right_misalign && !right_aligned_to))
1190 *misalign = NULL_TREE;
1191 *aligned_to = NULL_TREE;
1195 if (left_misalign && right_misalign)
1196 *misalign = size_binop (code, left_misalign, right_misalign);
1198 *misalign = left_misalign ? left_misalign : right_misalign;
1200 if (left_aligned_to && right_aligned_to)
1201 *aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to);
1203 *aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to;
1211 /* Compute offset. */
1212 *initial_offset = fold_convert (ssizetype,
1213 fold_build2 (code, TREE_TYPE (left_offset),
1219 /* Function address_analysis
1221 Return the BASE of the address expression EXPR.
1222 Also compute the OFFSET from BASE, MISALIGN and STEP.
1225 EXPR - the address expression that is being analyzed
1226 STMT - the statement that contains EXPR or its original memory reference
1227 IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
1228 DR - data_reference struct for the original memory reference
1231 BASE (returned value) - the base of the data reference EXPR.
1232 INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
1233 MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
1234 computation is impossible
1235 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1236 calculated (doesn't depend on variables)
1237 STEP - evolution of EXPR in the loop
1239 If something unexpected is encountered (an unsupported form of data-ref),
1240 then NULL_TREE is returned.
1244 address_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr,
1245 tree *offset, tree *misalign, tree *aligned_to, tree *step)
1247 tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
1248 tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1249 tree dummy, address_aligned_to = NULL_TREE;
1250 struct ptr_info_def *dummy1;
1253 switch (TREE_CODE (expr))
1257 /* EXPR is of form {base +/- offset} (or {offset +/- base}). */
1258 oprnd0 = TREE_OPERAND (expr, 0);
1259 oprnd1 = TREE_OPERAND (expr, 1);
1261 STRIP_NOPS (oprnd0);
1262 STRIP_NOPS (oprnd1);
1264 /* Recursively try to find the base of the address contained in EXPR.
1265 For offset, the returned base will be NULL. */
1266 base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset,
1267 &address_misalign, &address_aligned_to,
1270 base_addr1 = address_analysis (oprnd1, stmt, is_read, dr, &address_offset,
1271 &address_misalign, &address_aligned_to,
1274 /* We support cases where only one of the operands contains an
1276 if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
1278 if (dump_file && (dump_flags & TDF_DETAILS))
1281 "\neither more than one address or no addresses in expr ");
1282 print_generic_expr (dump_file, expr, TDF_SLIM);
1283 fprintf (dump_file, "\n");
1288 /* To revert STRIP_NOPS. */
1289 oprnd0 = TREE_OPERAND (expr, 0);
1290 oprnd1 = TREE_OPERAND (expr, 1);
1292 offset_expr = base_addr0 ?
1293 fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
1295 /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is
1296 a number, we can add it to the misalignment value calculated for base,
1297 otherwise, misalignment is NULL. */
1298 if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
1300 *misalign = size_binop (TREE_CODE (expr), address_misalign,
1302 *aligned_to = address_aligned_to;
1306 *misalign = NULL_TREE;
1307 *aligned_to = NULL_TREE;
1310 /* Combine offset (from EXPR {base + offset}) with the offset calculated
1312 *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
1313 return base_addr0 ? base_addr0 : base_addr1;
1316 base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read,
1317 &dr, offset, misalign, aligned_to, step,
1318 &dummy, &dummy1, &dummy2);
1319 return base_address;
1322 if (!POINTER_TYPE_P (TREE_TYPE (expr)))
1324 if (dump_file && (dump_flags & TDF_DETAILS))
1326 fprintf (dump_file, "\nnot pointer SSA_NAME ");
1327 print_generic_expr (dump_file, expr, TDF_SLIM);
1328 fprintf (dump_file, "\n");
1332 *aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr))));
1333 *misalign = ssize_int (0);
1334 *offset = ssize_int (0);
1335 *step = ssize_int (0);
1344 /* Function object_analysis
1346 Create a data-reference structure DR for MEMREF.
1347 Return the BASE of the data reference MEMREF if the analysis is possible.
1348 Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1349 E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset
1350 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET
1351 instantiated with initial_conditions of access_functions of variables,
1352 and STEP is the evolution of the DR_REF in this loop.
1354 Function get_inner_reference is used for the above in case of ARRAY_REF and
1357 The structure of the function is as follows:
1359 Case 1. For handled_component_p refs
1360 1.1 build data-reference structure for MEMREF
1361 1.2 call get_inner_reference
1362 1.2.1 analyze offset expr received from get_inner_reference
1363 (fall through with BASE)
1364 Case 2. For declarations
1366 Case 3. For INDIRECT_REFs
1367 3.1 build data-reference structure for MEMREF
1368 3.2 analyze evolution and initial condition of MEMREF
1369 3.3 set data-reference structure for MEMREF
1370 3.4 call address_analysis to analyze INIT of the access function
1371 3.5 extract memory tag
1374 Combine the results of object and address analysis to calculate
1375 INITIAL_OFFSET, STEP and misalignment info.
1378 MEMREF - the memory reference that is being analyzed
1379 STMT - the statement that contains MEMREF
1380 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1383 BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
1384 E.g, if MEMREF is a.b[k].c[i][j] the returned
1386 DR - data_reference struct for MEMREF
1387 INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
1388 MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of
1389 ALIGNMENT or NULL_TREE if the computation is impossible
1390 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1391 calculated (doesn't depend on variables)
1392 STEP - evolution of the DR_REF in the loop
1393 MEMTAG - memory tag for aliasing purposes
1394 PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
1395 SUBVARS - Sub-variables of the variable
1397 If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned,
1398 but DR can be created anyway.
1403 object_analysis (tree memref, tree stmt, bool is_read,
1404 struct data_reference **dr, tree *offset, tree *misalign,
1405 tree *aligned_to, tree *step, tree *memtag,
1406 struct ptr_info_def **ptr_info, subvar_t *subvars)
1408 tree base = NULL_TREE, base_address = NULL_TREE;
1409 tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
1410 tree object_step = ssize_int (0), address_step = ssize_int (0);
1411 tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1412 HOST_WIDE_INT pbitsize, pbitpos;
1413 tree poffset, bit_pos_in_bytes;
1414 enum machine_mode pmode;
1415 int punsignedp, pvolatilep;
1416 tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
1417 struct loop *loop = loop_containing_stmt (stmt);
1418 struct data_reference *ptr_dr = NULL;
1419 tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE;
1424 /* Case 1. handled_component_p refs. */
1425 if (handled_component_p (memref))
1427 /* 1.1 build data-reference structure for MEMREF. */
1428 /* TODO: handle COMPONENT_REFs. */
1431 if (TREE_CODE (memref) == ARRAY_REF)
1432 *dr = analyze_array (stmt, memref, is_read);
1436 if (dump_file && (dump_flags & TDF_DETAILS))
1438 fprintf (dump_file, "\ndata-ref of unsupported type ");
1439 print_generic_expr (dump_file, memref, TDF_SLIM);
1440 fprintf (dump_file, "\n");
1446 /* 1.2 call get_inner_reference. */
1447 /* Find the base and the offset from it. */
1448 base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
1449 &pmode, &punsignedp, &pvolatilep, false);
1452 if (dump_file && (dump_flags & TDF_DETAILS))
1454 fprintf (dump_file, "\nfailed to get inner ref for ");
1455 print_generic_expr (dump_file, memref, TDF_SLIM);
1456 fprintf (dump_file, "\n");
1461 /* 1.2.1 analyze offset expr received from get_inner_reference. */
1463 && !analyze_offset_expr (poffset, loop, &object_offset,
1464 &object_misalign, &object_aligned_to,
1467 if (dump_file && (dump_flags & TDF_DETAILS))
1469 fprintf (dump_file, "\nfailed to compute offset or step for ");
1470 print_generic_expr (dump_file, memref, TDF_SLIM);
1471 fprintf (dump_file, "\n");
1476 /* Add bit position to OFFSET and MISALIGN. */
1478 bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
1479 /* Check that there is no remainder in bits. */
1480 if (pbitpos%BITS_PER_UNIT)
1482 if (dump_file && (dump_flags & TDF_DETAILS))
1483 fprintf (dump_file, "\nbit offset alignment.\n");
1486 object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);
1487 if (object_misalign)
1488 object_misalign = size_binop (PLUS_EXPR, object_misalign,
1491 memref = base; /* To continue analysis of BASE. */
1495 /* Part 1: Case 2. Declarations. */
1496 if (DECL_P (memref))
1498 /* We expect to get a decl only if we already have a DR. */
1501 if (dump_file && (dump_flags & TDF_DETAILS))
1503 fprintf (dump_file, "\nunhandled decl ");
1504 print_generic_expr (dump_file, memref, TDF_SLIM);
1505 fprintf (dump_file, "\n");
1510 /* TODO: if during the analysis of INDIRECT_REF we get to an object, put
1511 the object in BASE_OBJECT field if we can prove that this is O.K.,
1512 i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT.
1513 (e.g., if the object is an array base 'a', where 'a[N]', we must prove
1514 that every access with 'p' (the original INDIRECT_REF based on '&a')
1515 in the loop is within the array boundaries - from a[0] to a[N-1]).
1516 Otherwise, our alias analysis can be incorrect.
1517 Even if an access function based on BASE_OBJECT can't be build, update
1518 BASE_OBJECT field to enable us to prove that two data-refs are
1519 different (without access function, distance analysis is impossible).
1521 if (SSA_VAR_P (memref) && var_can_have_subvars (memref))
1522 *subvars = get_subvars_for_var (memref);
1523 base_address = build_fold_addr_expr (memref);
1524 /* 2.1 set MEMTAG. */
1528 /* Part 1: Case 3. INDIRECT_REFs. */
1529 else if (TREE_CODE (memref) == INDIRECT_REF)
1531 tree ptr_ref = TREE_OPERAND (memref, 0);
1532 if (TREE_CODE (ptr_ref) == SSA_NAME)
1533 *ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
1535 /* 3.1 build data-reference structure for MEMREF. */
1536 ptr_dr = analyze_indirect_ref (stmt, memref, is_read);
1539 if (dump_file && (dump_flags & TDF_DETAILS))
1541 fprintf (dump_file, "\nfailed to create dr for ");
1542 print_generic_expr (dump_file, memref, TDF_SLIM);
1543 fprintf (dump_file, "\n");
1548 /* 3.2 analyze evolution and initial condition of MEMREF. */
1549 ptr_step = DR_STEP (ptr_dr);
1550 ptr_init = DR_BASE_ADDRESS (ptr_dr);
1551 if (!ptr_init || !ptr_step || !POINTER_TYPE_P (TREE_TYPE (ptr_init)))
1553 *dr = (*dr) ? *dr : ptr_dr;
1554 if (dump_file && (dump_flags & TDF_DETAILS))
1556 fprintf (dump_file, "\nbad pointer access ");
1557 print_generic_expr (dump_file, memref, TDF_SLIM);
1558 fprintf (dump_file, "\n");
1563 if (integer_zerop (ptr_step) && !(*dr))
1565 if (dump_file && (dump_flags & TDF_DETAILS))
1566 fprintf (dump_file, "\nptr is loop invariant.\n");
1570 /* If there exists DR for MEMREF, we are analyzing the base of
1571 handled component (PTR_INIT), which not necessary has evolution in
1574 object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
1576 /* 3.3 set data-reference structure for MEMREF. */
1580 /* 3.4 call address_analysis to analyze INIT of the access
1582 base_address = address_analysis (ptr_init, stmt, is_read, *dr,
1583 &address_offset, &address_misalign,
1584 &address_aligned_to, &address_step);
1587 if (dump_file && (dump_flags & TDF_DETAILS))
1589 fprintf (dump_file, "\nfailed to analyze address ");
1590 print_generic_expr (dump_file, ptr_init, TDF_SLIM);
1591 fprintf (dump_file, "\n");
1596 /* 3.5 extract memory tag. */
1597 switch (TREE_CODE (base_address))
1600 *memtag = get_var_ann (SSA_NAME_VAR (base_address))->type_mem_tag;
1601 if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
1602 *memtag = get_var_ann (
1603 SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->type_mem_tag;
1606 *memtag = TREE_OPERAND (base_address, 0);
1609 if (dump_file && (dump_flags & TDF_DETAILS))
1611 fprintf (dump_file, "\nno memtag for ");
1612 print_generic_expr (dump_file, memref, TDF_SLIM);
1613 fprintf (dump_file, "\n");
1615 *memtag = NULL_TREE;
1622 /* MEMREF cannot be analyzed. */
1623 if (dump_file && (dump_flags & TDF_DETAILS))
1625 fprintf (dump_file, "\ndata-ref of unsupported type ");
1626 print_generic_expr (dump_file, memref, TDF_SLIM);
1627 fprintf (dump_file, "\n");
1632 if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag))
1633 *subvars = get_subvars_for_var (*memtag);
1635 /* Part 2: Combine the results of object and address analysis to calculate
1636 INITIAL_OFFSET, STEP and misalignment info. */
1637 *offset = size_binop (PLUS_EXPR, object_offset, address_offset);
1639 if ((!object_misalign && !object_aligned_to)
1640 || (!address_misalign && !address_aligned_to))
1642 *misalign = NULL_TREE;
1643 *aligned_to = NULL_TREE;
1647 if (object_misalign && address_misalign)
1648 *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
1650 *misalign = object_misalign ? object_misalign : address_misalign;
1651 if (object_aligned_to && address_aligned_to)
1652 *aligned_to = size_binop (MIN_EXPR, object_aligned_to,
1653 address_aligned_to);
1655 *aligned_to = object_aligned_to ?
1656 object_aligned_to : address_aligned_to;
1658 *step = size_binop (PLUS_EXPR, object_step, address_step);
1660 return base_address;
1663 /* Function analyze_offset.
1665 Extract INVARIANT and CONSTANT parts from OFFSET.
1669 analyze_offset (tree offset, tree *invariant, tree *constant)
1671 tree op0, op1, constant_0, constant_1, invariant_0, invariant_1;
1672 enum tree_code code = TREE_CODE (offset);
1674 *invariant = NULL_TREE;
1675 *constant = NULL_TREE;
1677 /* Not PLUS/MINUS expression - recursion stop condition. */
1678 if (code != PLUS_EXPR && code != MINUS_EXPR)
1680 if (TREE_CODE (offset) == INTEGER_CST)
1683 *invariant = offset;
1687 op0 = TREE_OPERAND (offset, 0);
1688 op1 = TREE_OPERAND (offset, 1);
1690 /* Recursive call with the operands. */
1691 analyze_offset (op0, &invariant_0, &constant_0);
1692 analyze_offset (op1, &invariant_1, &constant_1);
1694 /* Combine the results. */
1695 *constant = constant_0 ? constant_0 : constant_1;
1696 if (invariant_0 && invariant_1)
1698 fold (build (code, TREE_TYPE (invariant_0), invariant_0, invariant_1));
1700 *invariant = invariant_0 ? invariant_0 : invariant_1;
1704 /* Function create_data_ref.
1706 Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS,
1707 DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO,
1708 DR_MEMTAG, and DR_POINTSTO_INFO fields.
1711 MEMREF - the memory reference that is being analyzed
1712 STMT - the statement that contains MEMREF
1713 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1716 DR (returned value) - data_reference struct for MEMREF
1719 static struct data_reference *
1720 create_data_ref (tree memref, tree stmt, bool is_read)
1722 struct data_reference *dr = NULL;
1723 tree base_address, offset, step, misalign, memtag;
1724 struct loop *loop = loop_containing_stmt (stmt);
1725 tree invariant = NULL_TREE, constant = NULL_TREE;
1726 tree type_size, init_cond;
1727 struct ptr_info_def *ptr_info;
1728 subvar_t subvars = NULL;
1734 base_address = object_analysis (memref, stmt, is_read, &dr, &offset,
1735 &misalign, &aligned_to, &step, &memtag,
1736 &ptr_info, &subvars);
1737 if (!dr || !base_address)
1739 if (dump_file && (dump_flags & TDF_DETAILS))
1741 fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for ");
1742 print_generic_expr (dump_file, memref, TDF_SLIM);
1743 fprintf (dump_file, "\n");
1748 DR_BASE_ADDRESS (dr) = base_address;
1749 DR_OFFSET (dr) = offset;
1750 DR_INIT (dr) = ssize_int (0);
1751 DR_STEP (dr) = step;
1752 DR_OFFSET_MISALIGNMENT (dr) = misalign;
1753 DR_ALIGNED_TO (dr) = aligned_to;
1754 DR_MEMTAG (dr) = memtag;
1755 DR_PTR_INFO (dr) = ptr_info;
1756 DR_SUBVARS (dr) = subvars;
1758 type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
1760 /* Change the access function for INIDIRECT_REFs, according to
1761 DR_BASE_ADDRESS. Analyze OFFSET calculated in object_analysis. OFFSET is
1762 an expression that can contain loop invariant expressions and constants.
1763 We put the constant part in the initial condition of the access function
1764 (for data dependence tests), and in DR_INIT of the data-ref. The loop
1765 invariant part is put in DR_OFFSET.
1766 The evolution part of the access function is STEP calculated in
1767 object_analysis divided by the size of data type.
1769 if (!DR_BASE_OBJECT (dr))
1774 /* Extract CONSTANT and INVARIANT from OFFSET, and put them in DR_INIT and
1775 DR_OFFSET fields of DR. */
1776 analyze_offset (offset, &invariant, &constant);
1779 DR_INIT (dr) = fold_convert (ssizetype, constant);
1780 init_cond = fold (build (TRUNC_DIV_EXPR, TREE_TYPE (constant),
1781 constant, type_size));
1784 DR_INIT (dr) = init_cond = ssize_int (0);;
1787 DR_OFFSET (dr) = invariant;
1789 DR_OFFSET (dr) = ssize_int (0);
1791 /* Update access function. */
1792 access_fn = DR_ACCESS_FN (dr, 0);
1793 new_step = size_binop (TRUNC_DIV_EXPR,
1794 fold_convert (ssizetype, step), type_size);
1796 access_fn = chrec_replace_initial_condition (access_fn, init_cond);
1797 access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step);
1799 VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn);
1802 if (dump_file && (dump_flags & TDF_DETAILS))
1804 struct ptr_info_def *pi = DR_PTR_INFO (dr);
1806 fprintf (dump_file, "\nCreated dr for ");
1807 print_generic_expr (dump_file, memref, TDF_SLIM);
1808 fprintf (dump_file, "\n\tbase_address: ");
1809 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
1810 fprintf (dump_file, "\n\toffset from base address: ");
1811 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
1812 fprintf (dump_file, "\n\tconstant offset from base address: ");
1813 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
1814 fprintf (dump_file, "\n\tbase_object: ");
1815 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
1816 fprintf (dump_file, "\n\tstep: ");
1817 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
1818 fprintf (dump_file, "B\n\tmisalignment from base: ");
1819 print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM);
1820 if (DR_OFFSET_MISALIGNMENT (dr))
1821 fprintf (dump_file, "B");
1822 if (DR_ALIGNED_TO (dr))
1824 fprintf (dump_file, "\n\taligned to: ");
1825 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
1827 fprintf (dump_file, "\n\tmemtag: ");
1828 print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM);
1829 fprintf (dump_file, "\n");
1830 if (pi && pi->name_mem_tag)
1832 fprintf (dump_file, "\n\tnametag: ");
1833 print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM);
1834 fprintf (dump_file, "\n");
1841 /* Returns true when all the functions of a tree_vec CHREC are the
1845 all_chrecs_equal_p (tree chrec)
1849 for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
1851 tree chrec_j = TREE_VEC_ELT (chrec, j);
1852 tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1);
1855 (integer_type_node, chrec_j, chrec_j_1)))
1861 /* Determine for each subscript in the data dependence relation DDR
1865 compute_subscript_distance (struct data_dependence_relation *ddr)
1867 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1871 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1873 tree conflicts_a, conflicts_b, difference;
1874 struct subscript *subscript;
1876 subscript = DDR_SUBSCRIPT (ddr, i);
1877 conflicts_a = SUB_CONFLICTS_IN_A (subscript);
1878 conflicts_b = SUB_CONFLICTS_IN_B (subscript);
1880 if (TREE_CODE (conflicts_a) == TREE_VEC)
1882 if (!all_chrecs_equal_p (conflicts_a))
1884 SUB_DISTANCE (subscript) = chrec_dont_know;
1888 conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
1891 if (TREE_CODE (conflicts_b) == TREE_VEC)
1893 if (!all_chrecs_equal_p (conflicts_b))
1895 SUB_DISTANCE (subscript) = chrec_dont_know;
1899 conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
1902 difference = chrec_fold_minus
1903 (integer_type_node, conflicts_b, conflicts_a);
1905 if (evolution_function_is_constant_p (difference))
1906 SUB_DISTANCE (subscript) = difference;
1909 SUB_DISTANCE (subscript) = chrec_dont_know;
1914 /* Initialize a ddr. */
1916 struct data_dependence_relation *
1917 initialize_data_dependence_relation (struct data_reference *a,
1918 struct data_reference *b)
1920 struct data_dependence_relation *res;
1924 res = xmalloc (sizeof (struct data_dependence_relation));
1928 if (a == NULL || b == NULL)
1930 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1934 /* When A and B are arrays and their dimensions differ, we directly
1935 initialize the relation to "there is no dependence": chrec_known. */
1936 if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
1937 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
1939 DDR_ARE_DEPENDENT (res) = chrec_known;
1943 /* Compare the bases of the data-refs. */
1944 if (!base_addr_differ_p (a, b, &differ_p))
1946 /* Can't determine whether the data-refs access the same memory
1948 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1953 DDR_ARE_DEPENDENT (res) = chrec_known;
1957 DDR_AFFINE_P (res) = true;
1958 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1959 DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
1960 DDR_SIZE_VECT (res) = 0;
1961 DDR_DIST_VECT (res) = NULL;
1962 DDR_DIR_VECT (res) = NULL;
1964 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1966 struct subscript *subscript;
1968 subscript = xmalloc (sizeof (struct subscript));
1969 SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
1970 SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
1971 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1972 SUB_DISTANCE (subscript) = chrec_dont_know;
1973 VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
1979 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1983 finalize_ddr_dependent (struct data_dependence_relation *ddr,
1986 if (dump_file && (dump_flags & TDF_DETAILS))
1988 fprintf (dump_file, "(dependence classified: ");
1989 print_generic_expr (dump_file, chrec, 0);
1990 fprintf (dump_file, ")\n");
1993 DDR_ARE_DEPENDENT (ddr) = chrec;
1994 varray_clear (DDR_SUBSCRIPTS (ddr));
1997 /* The dependence relation DDR cannot be represented by a distance
2001 non_affine_dependence_relation (struct data_dependence_relation *ddr)
2003 if (dump_file && (dump_flags & TDF_DETAILS))
2004 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
2006 DDR_AFFINE_P (ddr) = false;
2011 /* This section contains the classic Banerjee tests. */
2013 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
2014 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
2017 ziv_subscript_p (tree chrec_a,
2020 return (evolution_function_is_constant_p (chrec_a)
2021 && evolution_function_is_constant_p (chrec_b));
2024 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
2025 variable, i.e., if the SIV (Single Index Variable) test is true. */
2028 siv_subscript_p (tree chrec_a,
2031 if ((evolution_function_is_constant_p (chrec_a)
2032 && evolution_function_is_univariate_p (chrec_b))
2033 || (evolution_function_is_constant_p (chrec_b)
2034 && evolution_function_is_univariate_p (chrec_a)))
2037 if (evolution_function_is_univariate_p (chrec_a)
2038 && evolution_function_is_univariate_p (chrec_b))
2040 switch (TREE_CODE (chrec_a))
2042 case POLYNOMIAL_CHREC:
2043 switch (TREE_CODE (chrec_b))
2045 case POLYNOMIAL_CHREC:
2046 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
2061 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
2062 *OVERLAPS_B are initialized to the functions that describe the
2063 relation between the elements accessed twice by CHREC_A and
2064 CHREC_B. For k >= 0, the following property is verified:
2066 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2069 analyze_ziv_subscript (tree chrec_a,
2073 tree *last_conflicts)
2077 if (dump_file && (dump_flags & TDF_DETAILS))
2078 fprintf (dump_file, "(analyze_ziv_subscript \n");
2080 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2082 switch (TREE_CODE (difference))
2085 if (integer_zerop (difference))
2087 /* The difference is equal to zero: the accessed index
2088 overlaps for each iteration in the loop. */
2089 *overlaps_a = integer_zero_node;
2090 *overlaps_b = integer_zero_node;
2091 *last_conflicts = chrec_dont_know;
2095 /* The accesses do not overlap. */
2096 *overlaps_a = chrec_known;
2097 *overlaps_b = chrec_known;
2098 *last_conflicts = integer_zero_node;
2103 /* We're not sure whether the indexes overlap. For the moment,
2104 conservatively answer "don't know". */
2105 *overlaps_a = chrec_dont_know;
2106 *overlaps_b = chrec_dont_know;
2107 *last_conflicts = chrec_dont_know;
2111 if (dump_file && (dump_flags & TDF_DETAILS))
2112 fprintf (dump_file, ")\n");
2115 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2116 constant, and CHREC_B is an affine function. *OVERLAPS_A and
2117 *OVERLAPS_B are initialized to the functions that describe the
2118 relation between the elements accessed twice by CHREC_A and
2119 CHREC_B. For k >= 0, the following property is verified:
2121 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2124 analyze_siv_subscript_cst_affine (tree chrec_a,
2128 tree *last_conflicts)
2130 bool value0, value1, value2;
2131 tree difference = chrec_fold_minus
2132 (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
2134 if (!chrec_is_positive (initial_condition (difference), &value0))
2136 *overlaps_a = chrec_dont_know;
2137 *overlaps_b = chrec_dont_know;
2138 *last_conflicts = chrec_dont_know;
2143 if (value0 == false)
2145 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
2147 *overlaps_a = chrec_dont_know;
2148 *overlaps_b = chrec_dont_know;
2149 *last_conflicts = chrec_dont_know;
2158 chrec_b = {10, +, 1}
2161 if (tree_fold_divides_p
2162 (integer_type_node, CHREC_RIGHT (chrec_b), difference))
2164 *overlaps_a = integer_zero_node;
2165 *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
2166 fold_build1 (ABS_EXPR,
2169 CHREC_RIGHT (chrec_b));
2170 *last_conflicts = integer_one_node;
2174 /* When the step does not divides the difference, there are
2178 *overlaps_a = chrec_known;
2179 *overlaps_b = chrec_known;
2180 *last_conflicts = integer_zero_node;
2189 chrec_b = {10, +, -1}
2191 In this case, chrec_a will not overlap with chrec_b. */
2192 *overlaps_a = chrec_known;
2193 *overlaps_b = chrec_known;
2194 *last_conflicts = integer_zero_node;
2201 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
2203 *overlaps_a = chrec_dont_know;
2204 *overlaps_b = chrec_dont_know;
2205 *last_conflicts = chrec_dont_know;
2210 if (value2 == false)
2214 chrec_b = {10, +, -1}
2216 if (tree_fold_divides_p
2217 (integer_type_node, CHREC_RIGHT (chrec_b), difference))
2219 *overlaps_a = integer_zero_node;
2221 (build (EXACT_DIV_EXPR, integer_type_node, difference,
2222 CHREC_RIGHT (chrec_b)));
2223 *last_conflicts = integer_one_node;
2227 /* When the step does not divides the difference, there
2231 *overlaps_a = chrec_known;
2232 *overlaps_b = chrec_known;
2233 *last_conflicts = integer_zero_node;
2243 In this case, chrec_a will not overlap with chrec_b. */
2244 *overlaps_a = chrec_known;
2245 *overlaps_b = chrec_known;
2246 *last_conflicts = integer_zero_node;
2254 /* Helper recursive function for initializing the matrix A. Returns
2255 the initial value of CHREC. */
2258 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2262 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2263 return int_cst_value (chrec);
2265 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2266 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2269 #define FLOOR_DIV(x,y) ((x) / (y))
2271 /* Solves the special case of the Diophantine equation:
2272 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2274 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2275 number of iterations that loops X and Y run. The overlaps will be
2276 constructed as evolutions in dimension DIM. */
2279 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
2280 tree *overlaps_a, tree *overlaps_b,
2281 tree *last_conflicts, int dim)
2283 if (((step_a > 0 && step_b > 0)
2284 || (step_a < 0 && step_b < 0)))
2286 int step_overlaps_a, step_overlaps_b;
2287 int gcd_steps_a_b, last_conflict, tau2;
2289 gcd_steps_a_b = gcd (step_a, step_b);
2290 step_overlaps_a = step_b / gcd_steps_a_b;
2291 step_overlaps_b = step_a / gcd_steps_a_b;
2293 tau2 = FLOOR_DIV (niter, step_overlaps_a);
2294 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2295 last_conflict = tau2;
2297 *overlaps_a = build_polynomial_chrec
2298 (dim, integer_zero_node,
2299 build_int_cst (NULL_TREE, step_overlaps_a));
2300 *overlaps_b = build_polynomial_chrec
2301 (dim, integer_zero_node,
2302 build_int_cst (NULL_TREE, step_overlaps_b));
2303 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2308 *overlaps_a = integer_zero_node;
2309 *overlaps_b = integer_zero_node;
2310 *last_conflicts = integer_zero_node;
2315 /* Solves the special case of a Diophantine equation where CHREC_A is
2316 an affine bivariate function, and CHREC_B is an affine univariate
2317 function. For example,
2319 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2321 has the following overlapping functions:
2323 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2324 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2325 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2327 FORNOW: This is a specialized implementation for a case occurring in
2328 a common benchmark. Implement the general algorithm. */
2331 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2332 tree *overlaps_a, tree *overlaps_b,
2333 tree *last_conflicts)
2335 bool xz_p, yz_p, xyz_p;
2336 int step_x, step_y, step_z;
2337 int niter_x, niter_y, niter_z, niter;
2338 tree numiter_x, numiter_y, numiter_z;
2339 tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
2340 tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
2341 tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
2343 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2344 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2345 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2347 numiter_x = number_of_iterations_in_loop
2348 (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]);
2349 numiter_y = number_of_iterations_in_loop
2350 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2351 numiter_z = number_of_iterations_in_loop
2352 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2354 if (TREE_CODE (numiter_x) != INTEGER_CST)
2355 numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]
2356 ->estimated_nb_iterations;
2357 if (TREE_CODE (numiter_y) != INTEGER_CST)
2358 numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2359 ->estimated_nb_iterations;
2360 if (TREE_CODE (numiter_z) != INTEGER_CST)
2361 numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2362 ->estimated_nb_iterations;
2364 if (chrec_contains_undetermined (numiter_x)
2365 || chrec_contains_undetermined (numiter_y)
2366 || chrec_contains_undetermined (numiter_z)
2367 || TREE_CODE (numiter_x) != INTEGER_CST
2368 || TREE_CODE (numiter_y) != INTEGER_CST
2369 || TREE_CODE (numiter_z) != INTEGER_CST)
2371 *overlaps_a = chrec_dont_know;
2372 *overlaps_b = chrec_dont_know;
2373 *last_conflicts = chrec_dont_know;
2377 niter_x = int_cst_value (numiter_x);
2378 niter_y = int_cst_value (numiter_y);
2379 niter_z = int_cst_value (numiter_z);
2381 niter = MIN (niter_x, niter_z);
2382 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2385 &last_conflicts_xz, 1);
2386 niter = MIN (niter_y, niter_z);
2387 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2390 &last_conflicts_yz, 2);
2391 niter = MIN (niter_x, niter_z);
2392 niter = MIN (niter_y, niter);
2393 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2396 &last_conflicts_xyz, 3);
2398 xz_p = !integer_zerop (last_conflicts_xz);
2399 yz_p = !integer_zerop (last_conflicts_yz);
2400 xyz_p = !integer_zerop (last_conflicts_xyz);
2402 if (xz_p || yz_p || xyz_p)
2404 *overlaps_a = make_tree_vec (2);
2405 TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
2406 TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
2407 *overlaps_b = integer_zero_node;
2410 TREE_VEC_ELT (*overlaps_a, 0) =
2411 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
2414 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
2415 *last_conflicts = last_conflicts_xz;
2419 TREE_VEC_ELT (*overlaps_a, 1) =
2420 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
2423 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
2424 *last_conflicts = last_conflicts_yz;
2428 TREE_VEC_ELT (*overlaps_a, 0) =
2429 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
2431 TREE_VEC_ELT (*overlaps_a, 1) =
2432 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
2435 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
2436 *last_conflicts = last_conflicts_xyz;
2441 *overlaps_a = integer_zero_node;
2442 *overlaps_b = integer_zero_node;
2443 *last_conflicts = integer_zero_node;
2447 /* Determines the overlapping elements due to accesses CHREC_A and
2448 CHREC_B, that are affine functions. This is a part of the
2449 subscript analyzer. */
2452 analyze_subscript_affine_affine (tree chrec_a,
2456 tree *last_conflicts)
2458 unsigned nb_vars_a, nb_vars_b, dim;
2459 int init_a, init_b, gamma, gcd_alpha_beta;
2461 lambda_matrix A, U, S;
2463 if (dump_file && (dump_flags & TDF_DETAILS))
2464 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2466 /* For determining the initial intersection, we have to solve a
2467 Diophantine equation. This is the most time consuming part.
2469 For answering to the question: "Is there a dependence?" we have
2470 to prove that there exists a solution to the Diophantine
2471 equation, and that the solution is in the iteration domain,
2472 i.e. the solution is positive or zero, and that the solution
2473 happens before the upper bound loop.nb_iterations. Otherwise
2474 there is no dependence. This function outputs a description of
2475 the iterations that hold the intersections. */
2478 nb_vars_a = nb_vars_in_chrec (chrec_a);
2479 nb_vars_b = nb_vars_in_chrec (chrec_b);
2481 dim = nb_vars_a + nb_vars_b;
2482 U = lambda_matrix_new (dim, dim);
2483 A = lambda_matrix_new (dim, 1);
2484 S = lambda_matrix_new (dim, 1);
2486 init_a = initialize_matrix_A (A, chrec_a, 0, 1);
2487 init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
2488 gamma = init_b - init_a;
2490 /* Don't do all the hard work of solving the Diophantine equation
2491 when we already know the solution: for example,
2494 | gamma = 3 - 3 = 0.
2495 Then the first overlap occurs during the first iterations:
2496 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2500 if (nb_vars_a == 1 && nb_vars_b == 1)
2503 int niter, niter_a, niter_b;
2504 tree numiter_a, numiter_b;
2506 numiter_a = number_of_iterations_in_loop
2507 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2508 numiter_b = number_of_iterations_in_loop
2509 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2511 if (TREE_CODE (numiter_a) != INTEGER_CST)
2512 numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2513 ->estimated_nb_iterations;
2514 if (TREE_CODE (numiter_b) != INTEGER_CST)
2515 numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2516 ->estimated_nb_iterations;
2517 if (chrec_contains_undetermined (numiter_a)
2518 || chrec_contains_undetermined (numiter_b)
2519 || TREE_CODE (numiter_a) != INTEGER_CST
2520 || TREE_CODE (numiter_b) != INTEGER_CST)
2522 *overlaps_a = chrec_dont_know;
2523 *overlaps_b = chrec_dont_know;
2524 *last_conflicts = chrec_dont_know;
2528 niter_a = int_cst_value (numiter_a);
2529 niter_b = int_cst_value (numiter_b);
2530 niter = MIN (niter_a, niter_b);
2532 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2533 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2535 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2536 overlaps_a, overlaps_b,
2540 else if (nb_vars_a == 2 && nb_vars_b == 1)
2541 compute_overlap_steps_for_affine_1_2
2542 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2544 else if (nb_vars_a == 1 && nb_vars_b == 2)
2545 compute_overlap_steps_for_affine_1_2
2546 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2550 *overlaps_a = chrec_dont_know;
2551 *overlaps_b = chrec_dont_know;
2552 *last_conflicts = chrec_dont_know;
2558 lambda_matrix_right_hermite (A, dim, 1, S, U);
2563 lambda_matrix_row_negate (U, dim, 0);
2565 gcd_alpha_beta = S[0][0];
2567 /* The classic "gcd-test". */
2568 if (!int_divides_p (gcd_alpha_beta, gamma))
2570 /* The "gcd-test" has determined that there is no integer
2571 solution, i.e. there is no dependence. */
2572 *overlaps_a = chrec_known;
2573 *overlaps_b = chrec_known;
2574 *last_conflicts = integer_zero_node;
2577 /* Both access functions are univariate. This includes SIV and MIV cases. */
2578 else if (nb_vars_a == 1 && nb_vars_b == 1)
2580 /* Both functions should have the same evolution sign. */
2581 if (((A[0][0] > 0 && -A[1][0] > 0)
2582 || (A[0][0] < 0 && -A[1][0] < 0)))
2584 /* The solutions are given by:
2586 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2589 For a given integer t. Using the following variables,
2591 | i0 = u11 * gamma / gcd_alpha_beta
2592 | j0 = u12 * gamma / gcd_alpha_beta
2599 | y0 = j0 + j1 * t. */
2603 /* X0 and Y0 are the first iterations for which there is a
2604 dependence. X0, Y0 are two solutions of the Diophantine
2605 equation: chrec_a (X0) = chrec_b (Y0). */
2607 int niter, niter_a, niter_b;
2608 tree numiter_a, numiter_b;
2610 numiter_a = number_of_iterations_in_loop
2611 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2612 numiter_b = number_of_iterations_in_loop
2613 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2615 if (TREE_CODE (numiter_a) != INTEGER_CST)
2616 numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2617 ->estimated_nb_iterations;
2618 if (TREE_CODE (numiter_b) != INTEGER_CST)
2619 numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2620 ->estimated_nb_iterations;
2621 if (chrec_contains_undetermined (numiter_a)
2622 || chrec_contains_undetermined (numiter_b)
2623 || TREE_CODE (numiter_a) != INTEGER_CST
2624 || TREE_CODE (numiter_b) != INTEGER_CST)
2626 *overlaps_a = chrec_dont_know;
2627 *overlaps_b = chrec_dont_know;
2628 *last_conflicts = chrec_dont_know;
2632 niter_a = int_cst_value (numiter_a);
2633 niter_b = int_cst_value (numiter_b);
2634 niter = MIN (niter_a, niter_b);
2636 i0 = U[0][0] * gamma / gcd_alpha_beta;
2637 j0 = U[0][1] * gamma / gcd_alpha_beta;
2641 if ((i1 == 0 && i0 < 0)
2642 || (j1 == 0 && j0 < 0))
2644 /* There is no solution.
2645 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2646 falls in here, but for the moment we don't look at the
2647 upper bound of the iteration domain. */
2648 *overlaps_a = chrec_known;
2649 *overlaps_b = chrec_known;
2650 *last_conflicts = integer_zero_node;
2657 tau1 = CEIL (-i0, i1);
2658 tau2 = FLOOR_DIV (niter - i0, i1);
2662 int last_conflict, min_multiple;
2663 tau1 = MAX (tau1, CEIL (-j0, j1));
2664 tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
2666 x0 = i1 * tau1 + i0;
2667 y0 = j1 * tau1 + j0;
2669 /* At this point (x0, y0) is one of the
2670 solutions to the Diophantine equation. The
2671 next step has to compute the smallest
2672 positive solution: the first conflicts. */
2673 min_multiple = MIN (x0 / i1, y0 / j1);
2674 x0 -= i1 * min_multiple;
2675 y0 -= j1 * min_multiple;
2677 tau1 = (x0 - i0)/i1;
2678 last_conflict = tau2 - tau1;
2680 *overlaps_a = build_polynomial_chrec
2682 build_int_cst (NULL_TREE, x0),
2683 build_int_cst (NULL_TREE, i1));
2684 *overlaps_b = build_polynomial_chrec
2686 build_int_cst (NULL_TREE, y0),
2687 build_int_cst (NULL_TREE, j1));
2688 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2692 /* FIXME: For the moment, the upper bound of the
2693 iteration domain for j is not checked. */
2694 *overlaps_a = chrec_dont_know;
2695 *overlaps_b = chrec_dont_know;
2696 *last_conflicts = chrec_dont_know;
2702 /* FIXME: For the moment, the upper bound of the
2703 iteration domain for i is not checked. */
2704 *overlaps_a = chrec_dont_know;
2705 *overlaps_b = chrec_dont_know;
2706 *last_conflicts = chrec_dont_know;
2712 *overlaps_a = chrec_dont_know;
2713 *overlaps_b = chrec_dont_know;
2714 *last_conflicts = chrec_dont_know;
2720 *overlaps_a = chrec_dont_know;
2721 *overlaps_b = chrec_dont_know;
2722 *last_conflicts = chrec_dont_know;
2726 if (dump_file && (dump_flags & TDF_DETAILS))
2728 fprintf (dump_file, " (overlaps_a = ");
2729 print_generic_expr (dump_file, *overlaps_a, 0);
2730 fprintf (dump_file, ")\n (overlaps_b = ");
2731 print_generic_expr (dump_file, *overlaps_b, 0);
2732 fprintf (dump_file, ")\n");
2735 if (dump_file && (dump_flags & TDF_DETAILS))
2736 fprintf (dump_file, ")\n");
2739 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2740 *OVERLAPS_B are initialized to the functions that describe the
2741 relation between the elements accessed twice by CHREC_A and
2742 CHREC_B. For k >= 0, the following property is verified:
2744 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2747 analyze_siv_subscript (tree chrec_a,
2751 tree *last_conflicts)
2753 if (dump_file && (dump_flags & TDF_DETAILS))
2754 fprintf (dump_file, "(analyze_siv_subscript \n");
2756 if (evolution_function_is_constant_p (chrec_a)
2757 && evolution_function_is_affine_p (chrec_b))
2758 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
2759 overlaps_a, overlaps_b, last_conflicts);
2761 else if (evolution_function_is_affine_p (chrec_a)
2762 && evolution_function_is_constant_p (chrec_b))
2763 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2764 overlaps_b, overlaps_a, last_conflicts);
2766 else if (evolution_function_is_affine_p (chrec_a)
2767 && evolution_function_is_affine_p (chrec_b))
2768 analyze_subscript_affine_affine (chrec_a, chrec_b,
2769 overlaps_a, overlaps_b, last_conflicts);
2772 *overlaps_a = chrec_dont_know;
2773 *overlaps_b = chrec_dont_know;
2774 *last_conflicts = chrec_dont_know;
2777 if (dump_file && (dump_flags & TDF_DETAILS))
2778 fprintf (dump_file, ")\n");
2781 /* Return true when the evolution steps of an affine CHREC divide the
2785 chrec_steps_divide_constant_p (tree chrec,
2788 switch (TREE_CODE (chrec))
2790 case POLYNOMIAL_CHREC:
2791 return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst)
2792 && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
2795 /* On the initial condition, return true. */
2800 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
2801 *OVERLAPS_B are initialized to the functions that describe the
2802 relation between the elements accessed twice by CHREC_A and
2803 CHREC_B. For k >= 0, the following property is verified:
2805 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2808 analyze_miv_subscript (tree chrec_a,
2812 tree *last_conflicts)
2814 /* FIXME: This is a MIV subscript, not yet handled.
2815 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2818 In the SIV test we had to solve a Diophantine equation with two
2819 variables. In the MIV case we have to solve a Diophantine
2820 equation with 2*n variables (if the subscript uses n IVs).
2824 if (dump_file && (dump_flags & TDF_DETAILS))
2825 fprintf (dump_file, "(analyze_miv_subscript \n");
2827 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2829 if (chrec_zerop (difference))
2831 /* Access functions are the same: all the elements are accessed
2832 in the same order. */
2833 *overlaps_a = integer_zero_node;
2834 *overlaps_b = integer_zero_node;
2835 *last_conflicts = number_of_iterations_in_loop
2836 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2839 else if (evolution_function_is_constant_p (difference)
2840 /* For the moment, the following is verified:
2841 evolution_function_is_affine_multivariate_p (chrec_a) */
2842 && !chrec_steps_divide_constant_p (chrec_a, difference))
2844 /* testsuite/.../ssa-chrec-33.c
2845 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2847 The difference is 1, and the evolution steps are equal to 2,
2848 consequently there are no overlapping elements. */
2849 *overlaps_a = chrec_known;
2850 *overlaps_b = chrec_known;
2851 *last_conflicts = integer_zero_node;
2854 else if (evolution_function_is_affine_multivariate_p (chrec_a)
2855 && evolution_function_is_affine_multivariate_p (chrec_b))
2857 /* testsuite/.../ssa-chrec-35.c
2858 {0, +, 1}_2 vs. {0, +, 1}_3
2859 the overlapping elements are respectively located at iterations:
2860 {0, +, 1}_x and {0, +, 1}_x,
2861 in other words, we have the equality:
2862 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2865 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2866 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2868 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2869 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2871 analyze_subscript_affine_affine (chrec_a, chrec_b,
2872 overlaps_a, overlaps_b, last_conflicts);
2877 /* When the analysis is too difficult, answer "don't know". */
2878 *overlaps_a = chrec_dont_know;
2879 *overlaps_b = chrec_dont_know;
2880 *last_conflicts = chrec_dont_know;
2883 if (dump_file && (dump_flags & TDF_DETAILS))
2884 fprintf (dump_file, ")\n");
2887 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
2888 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
2889 two functions that describe the iterations that contain conflicting
2892 Remark: For an integer k >= 0, the following equality is true:
2894 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2898 analyze_overlapping_iterations (tree chrec_a,
2900 tree *overlap_iterations_a,
2901 tree *overlap_iterations_b,
2902 tree *last_conflicts)
2904 if (dump_file && (dump_flags & TDF_DETAILS))
2906 fprintf (dump_file, "(analyze_overlapping_iterations \n");
2907 fprintf (dump_file, " (chrec_a = ");
2908 print_generic_expr (dump_file, chrec_a, 0);
2909 fprintf (dump_file, ")\n chrec_b = ");
2910 print_generic_expr (dump_file, chrec_b, 0);
2911 fprintf (dump_file, ")\n");
2914 if (chrec_a == NULL_TREE
2915 || chrec_b == NULL_TREE
2916 || chrec_contains_undetermined (chrec_a)
2917 || chrec_contains_undetermined (chrec_b)
2918 || chrec_contains_symbols (chrec_a)
2919 || chrec_contains_symbols (chrec_b))
2921 *overlap_iterations_a = chrec_dont_know;
2922 *overlap_iterations_b = chrec_dont_know;
2925 else if (ziv_subscript_p (chrec_a, chrec_b))
2926 analyze_ziv_subscript (chrec_a, chrec_b,
2927 overlap_iterations_a, overlap_iterations_b,
2930 else if (siv_subscript_p (chrec_a, chrec_b))
2931 analyze_siv_subscript (chrec_a, chrec_b,
2932 overlap_iterations_a, overlap_iterations_b,
2936 analyze_miv_subscript (chrec_a, chrec_b,
2937 overlap_iterations_a, overlap_iterations_b,
2940 if (dump_file && (dump_flags & TDF_DETAILS))
2942 fprintf (dump_file, " (overlap_iterations_a = ");
2943 print_generic_expr (dump_file, *overlap_iterations_a, 0);
2944 fprintf (dump_file, ")\n (overlap_iterations_b = ");
2945 print_generic_expr (dump_file, *overlap_iterations_b, 0);
2946 fprintf (dump_file, ")\n");
2952 /* This section contains the affine functions dependences detector. */
2954 /* Computes the conflicting iterations, and initialize DDR. */
2957 subscript_dependence_tester (struct data_dependence_relation *ddr)
2960 struct data_reference *dra = DDR_A (ddr);
2961 struct data_reference *drb = DDR_B (ddr);
2962 tree last_conflicts;
2964 if (dump_file && (dump_flags & TDF_DETAILS))
2965 fprintf (dump_file, "(subscript_dependence_tester \n");
2967 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2969 tree overlaps_a, overlaps_b;
2970 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
2972 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
2973 DR_ACCESS_FN (drb, i),
2974 &overlaps_a, &overlaps_b,
2977 if (chrec_contains_undetermined (overlaps_a)
2978 || chrec_contains_undetermined (overlaps_b))
2980 finalize_ddr_dependent (ddr, chrec_dont_know);
2984 else if (overlaps_a == chrec_known
2985 || overlaps_b == chrec_known)
2987 finalize_ddr_dependent (ddr, chrec_known);
2993 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
2994 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
2995 SUB_LAST_CONFLICT (subscript) = last_conflicts;
2999 if (dump_file && (dump_flags & TDF_DETAILS))
3000 fprintf (dump_file, ")\n");
3003 /* Compute the classic per loop distance vector.
3005 DDR is the data dependence relation to build a vector from.
3006 NB_LOOPS is the total number of loops we are considering.
3007 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
3009 Return FALSE if the dependence relation is outside of the loop nest
3010 starting at FIRST_LOOP_DEPTH.
3011 Return TRUE otherwise. */
3014 build_classic_dist_vector (struct data_dependence_relation *ddr,
3015 int nb_loops, int first_loop_depth)
3018 lambda_vector dist_v, init_v;
3020 dist_v = lambda_vector_new (nb_loops);
3021 init_v = lambda_vector_new (nb_loops);
3022 lambda_vector_clear (dist_v, nb_loops);
3023 lambda_vector_clear (init_v, nb_loops);
3025 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3028 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3030 tree access_fn_a, access_fn_b;
3031 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3033 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3035 non_affine_dependence_relation (ddr);
3039 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
3040 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
3042 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3043 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3045 int dist, loop_nb, loop_depth;
3046 int loop_nb_a = CHREC_VARIABLE (access_fn_a);
3047 int loop_nb_b = CHREC_VARIABLE (access_fn_b);
3048 struct loop *loop_a = current_loops->parray[loop_nb_a];
3049 struct loop *loop_b = current_loops->parray[loop_nb_b];
3051 /* If the loop for either variable is at a lower depth than
3052 the first_loop's depth, then we can't possibly have a
3053 dependency at this level of the loop. */
3055 if (loop_a->depth < first_loop_depth
3056 || loop_b->depth < first_loop_depth)
3059 if (loop_nb_a != loop_nb_b
3060 && !flow_loop_nested_p (loop_a, loop_b)
3061 && !flow_loop_nested_p (loop_b, loop_a))
3063 /* Example: when there are two consecutive loops,
3072 the dependence relation cannot be captured by the
3073 distance abstraction. */
3074 non_affine_dependence_relation (ddr);
3078 /* The dependence is carried by the outermost loop. Example:
3085 In this case, the dependence is carried by loop_1. */
3086 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
3087 loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
3089 /* If the loop number is still greater than the number of
3090 loops we've been asked to analyze, or negative,
3091 something is borked. */
3092 gcc_assert (loop_depth >= 0);
3093 gcc_assert (loop_depth < nb_loops);
3094 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3096 non_affine_dependence_relation (ddr);
3100 dist = int_cst_value (SUB_DISTANCE (subscript));
3102 /* This is the subscript coupling test.
3107 There is no dependence. */
3108 if (init_v[loop_depth] != 0
3109 && dist_v[loop_depth] != dist)
3111 finalize_ddr_dependent (ddr, chrec_known);
3115 dist_v[loop_depth] = dist;
3116 init_v[loop_depth] = 1;
3120 /* There is a distance of 1 on all the outer loops:
3122 Example: there is a dependence of distance 1 on loop_1 for the array A.
3128 struct loop *lca, *loop_a, *loop_b;
3129 struct data_reference *a = DDR_A (ddr);
3130 struct data_reference *b = DDR_B (ddr);
3132 loop_a = loop_containing_stmt (DR_STMT (a));
3133 loop_b = loop_containing_stmt (DR_STMT (b));
3135 /* Get the common ancestor loop. */
3136 lca = find_common_loop (loop_a, loop_b);
3138 lca_depth = lca->depth;
3139 lca_depth -= first_loop_depth;
3140 gcc_assert (lca_depth >= 0);
3141 gcc_assert (lca_depth < nb_loops);
3143 /* For each outer loop where init_v is not set, the accesses are
3144 in dependence of distance 1 in the loop. */
3147 && init_v[lca_depth] == 0)
3148 dist_v[lca_depth] = 1;
3154 lca_depth = lca->depth - first_loop_depth;
3155 while (lca->depth != 0)
3157 /* If we're considering just a sub-nest, then don't record
3158 any information on the outer loops. */
3162 gcc_assert (lca_depth < nb_loops);
3164 if (init_v[lca_depth] == 0)
3165 dist_v[lca_depth] = 1;
3167 lca_depth = lca->depth - first_loop_depth;
3173 DDR_DIST_VECT (ddr) = dist_v;
3174 DDR_SIZE_VECT (ddr) = nb_loops;
3178 /* Compute the classic per loop direction vector.
3180 DDR is the data dependence relation to build a vector from.
3181 NB_LOOPS is the total number of loops we are considering.
3182 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
3184 Return FALSE if the dependence relation is outside of the loop nest
3185 at FIRST_LOOP_DEPTH.
3186 Return TRUE otherwise. */
3189 build_classic_dir_vector (struct data_dependence_relation *ddr,
3190 int nb_loops, int first_loop_depth)
3193 lambda_vector dir_v, init_v;
3195 dir_v = lambda_vector_new (nb_loops);
3196 init_v = lambda_vector_new (nb_loops);
3197 lambda_vector_clear (dir_v, nb_loops);
3198 lambda_vector_clear (init_v, nb_loops);
3200 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3203 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3205 tree access_fn_a, access_fn_b;
3206 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3208 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3210 non_affine_dependence_relation (ddr);
3214 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
3215 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
3216 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3217 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3219 int dist, loop_nb, loop_depth;
3220 enum data_dependence_direction dir = dir_star;
3221 int loop_nb_a = CHREC_VARIABLE (access_fn_a);
3222 int loop_nb_b = CHREC_VARIABLE (access_fn_b);
3223 struct loop *loop_a = current_loops->parray[loop_nb_a];
3224 struct loop *loop_b = current_loops->parray[loop_nb_b];
3226 /* If the loop for either variable is at a lower depth than
3227 the first_loop's depth, then we can't possibly have a
3228 dependency at this level of the loop. */
3230 if (loop_a->depth < first_loop_depth
3231 || loop_b->depth < first_loop_depth)
3234 if (loop_nb_a != loop_nb_b
3235 && !flow_loop_nested_p (loop_a, loop_b)
3236 && !flow_loop_nested_p (loop_b, loop_a))
3238 /* Example: when there are two consecutive loops,
3247 the dependence relation cannot be captured by the
3248 distance abstraction. */
3249 non_affine_dependence_relation (ddr);
3253 /* The dependence is carried by the outermost loop. Example:
3260 In this case, the dependence is carried by loop_1. */
3261 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
3262 loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
3264 /* If the loop number is still greater than the number of
3265 loops we've been asked to analyze, or negative,
3266 something is borked. */
3267 gcc_assert (loop_depth >= 0);
3268 gcc_assert (loop_depth < nb_loops);
3270 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3272 non_affine_dependence_relation (ddr);
3276 dist = int_cst_value (SUB_DISTANCE (subscript));
3285 /* This is the subscript coupling test.
3290 There is no dependence. */
3291 if (init_v[loop_depth] != 0
3293 && (enum data_dependence_direction) dir_v[loop_depth] != dir
3294 && (enum data_dependence_direction) dir_v[loop_depth] != dir_star)
3296 finalize_ddr_dependent (ddr, chrec_known);
3300 dir_v[loop_depth] = dir;
3301 init_v[loop_depth] = 1;
3305 /* There is a distance of 1 on all the outer loops:
3307 Example: there is a dependence of distance 1 on loop_1 for the array A.
3313 struct loop *lca, *loop_a, *loop_b;
3314 struct data_reference *a = DDR_A (ddr);
3315 struct data_reference *b = DDR_B (ddr);
3317 loop_a = loop_containing_stmt (DR_STMT (a));
3318 loop_b = loop_containing_stmt (DR_STMT (b));
3320 /* Get the common ancestor loop. */
3321 lca = find_common_loop (loop_a, loop_b);
3322 lca_depth = lca->depth - first_loop_depth;
3324 gcc_assert (lca_depth >= 0);
3325 gcc_assert (lca_depth < nb_loops);
3327 /* For each outer loop where init_v is not set, the accesses are
3328 in dependence of distance 1 in the loop. */
3331 && init_v[lca_depth] == 0)
3332 dir_v[lca_depth] = dir_positive;
3337 lca_depth = lca->depth - first_loop_depth;
3338 while (lca->depth != 0)
3340 /* If we're considering just a sub-nest, then don't record
3341 any information on the outer loops. */
3345 gcc_assert (lca_depth < nb_loops);
3347 if (init_v[lca_depth] == 0)
3348 dir_v[lca_depth] = dir_positive;
3350 lca_depth = lca->depth - first_loop_depth;
3356 DDR_DIR_VECT (ddr) = dir_v;
3357 DDR_SIZE_VECT (ddr) = nb_loops;
3361 /* Returns true when all the access functions of A are affine or
3365 access_functions_are_affine_or_constant_p (struct data_reference *a)
3368 VEC(tree,heap) **fns = DR_ACCESS_FNS_ADDR (a);
3371 for (i = 0; VEC_iterate (tree, *fns, i, t); i++)
3372 if (!evolution_function_is_constant_p (t)
3373 && !evolution_function_is_affine_multivariate_p (t))
3379 /* This computes the affine dependence relation between A and B.
3380 CHREC_KNOWN is used for representing the independence between two
3381 accesses, while CHREC_DONT_KNOW is used for representing the unknown
3384 Note that it is possible to stop the computation of the dependence
3385 relation the first time we detect a CHREC_KNOWN element for a given
3389 compute_affine_dependence (struct data_dependence_relation *ddr)
3391 struct data_reference *dra = DDR_A (ddr);
3392 struct data_reference *drb = DDR_B (ddr);
3394 if (dump_file && (dump_flags & TDF_DETAILS))
3396 fprintf (dump_file, "(compute_affine_dependence\n");
3397 fprintf (dump_file, " (stmt_a = \n");
3398 print_generic_expr (dump_file, DR_STMT (dra), 0);
3399 fprintf (dump_file, ")\n (stmt_b = \n");
3400 print_generic_expr (dump_file, DR_STMT (drb), 0);
3401 fprintf (dump_file, ")\n");
3404 /* Analyze only when the dependence relation is not yet known. */
3405 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3407 if (access_functions_are_affine_or_constant_p (dra)
3408 && access_functions_are_affine_or_constant_p (drb))
3409 subscript_dependence_tester (ddr);
3411 /* As a last case, if the dependence cannot be determined, or if
3412 the dependence is considered too difficult to determine, answer
3415 finalize_ddr_dependent (ddr, chrec_dont_know);
3418 if (dump_file && (dump_flags & TDF_DETAILS))
3419 fprintf (dump_file, ")\n");
3422 /* This computes the dependence relation for the same data
3423 reference into DDR. */
3426 compute_self_dependence (struct data_dependence_relation *ddr)
3430 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3432 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3434 /* The accessed index overlaps for each iteration. */
3435 SUB_CONFLICTS_IN_A (subscript) = integer_zero_node;
3436 SUB_CONFLICTS_IN_B (subscript) = integer_zero_node;
3437 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3442 typedef struct data_dependence_relation *ddr_p;
3444 DEF_VEC_ALLOC_P(ddr_p,heap);
3446 /* Compute a subset of the data dependence relation graph. Don't
3447 compute read-read and self relations if
3448 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is FALSE, and avoid the computation
3449 of the opposite relation, i.e. when AB has been computed, don't compute BA.
3450 DATAREFS contains a list of data references, and the result is set
3451 in DEPENDENCE_RELATIONS. */
3454 compute_all_dependences (varray_type datarefs,
3455 bool compute_self_and_read_read_dependences,
3456 VEC(ddr_p,heap) **dependence_relations)
3458 unsigned int i, j, N;
3460 N = VARRAY_ACTIVE_SIZE (datarefs);
3462 /* Note that we specifically skip i == j because it's a self dependence, and
3463 use compute_self_dependence below. */
3465 for (i = 0; i < N; i++)
3466 for (j = i + 1; j < N; j++)
3468 struct data_reference *a, *b;
3469 struct data_dependence_relation *ddr;
3471 a = VARRAY_GENERIC_PTR (datarefs, i);
3472 b = VARRAY_GENERIC_PTR (datarefs, j);
3473 if (DR_IS_READ (a) && DR_IS_READ (b)
3474 && !compute_self_and_read_read_dependences)
3476 ddr = initialize_data_dependence_relation (a, b);
3478 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3479 compute_affine_dependence (ddr);
3480 compute_subscript_distance (ddr);
3482 if (!compute_self_and_read_read_dependences)
3485 /* Compute self dependence relation of each dataref to itself. */
3487 for (i = 0; i < N; i++)
3489 struct data_reference *a, *b;
3490 struct data_dependence_relation *ddr;
3492 a = VARRAY_GENERIC_PTR (datarefs, i);
3493 b = VARRAY_GENERIC_PTR (datarefs, i);
3494 ddr = initialize_data_dependence_relation (a, b);
3496 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3497 compute_self_dependence (ddr);
3498 compute_subscript_distance (ddr);
3502 /* Search the data references in LOOP, and record the information into
3503 DATAREFS. Returns chrec_dont_know when failing to analyze a
3504 difficult case, returns NULL_TREE otherwise.
3506 TODO: This function should be made smarter so that it can handle address
3507 arithmetic as if they were array accesses, etc. */
3510 find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
3512 basic_block bb, *bbs;
3514 block_stmt_iterator bsi;
3515 struct data_reference *dr;
3517 bbs = get_loop_body (loop);
3519 for (i = 0; i < loop->num_nodes; i++)
3523 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3525 tree stmt = bsi_stmt (bsi);
3527 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
3528 Calls have side-effects, except those to const or pure
3530 if ((TREE_CODE (stmt) == CALL_EXPR
3531 && !(call_expr_flags (stmt) & (ECF_CONST | ECF_PURE)))
3532 || (TREE_CODE (stmt) == ASM_EXPR
3533 && ASM_VOLATILE_P (stmt)))
3534 goto insert_dont_know_node;
3536 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3539 switch (TREE_CODE (stmt))
3543 bool one_inserted = false;
3544 tree opnd0 = TREE_OPERAND (stmt, 0);
3545 tree opnd1 = TREE_OPERAND (stmt, 1);
3547 if (TREE_CODE (opnd0) == ARRAY_REF
3548 || TREE_CODE (opnd0) == INDIRECT_REF)
3550 dr = create_data_ref (opnd0, stmt, false);
3553 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3554 one_inserted = true;
3558 if (TREE_CODE (opnd1) == ARRAY_REF
3559 || TREE_CODE (opnd1) == INDIRECT_REF)
3561 dr = create_data_ref (opnd1, stmt, true);
3564 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3565 one_inserted = true;
3570 goto insert_dont_know_node;
3578 bool one_inserted = false;
3580 for (args = TREE_OPERAND (stmt, 1); args;
3581 args = TREE_CHAIN (args))
3582 if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
3583 || TREE_CODE (TREE_VALUE (args)) == INDIRECT_REF)
3585 dr = create_data_ref (TREE_VALUE (args), stmt, true);
3588 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3589 one_inserted = true;
3594 goto insert_dont_know_node;
3601 struct data_reference *res;
3603 insert_dont_know_node:;
3604 res = xmalloc (sizeof (struct data_reference));
3605 DR_STMT (res) = NULL_TREE;
3606 DR_REF (res) = NULL_TREE;
3607 DR_BASE_OBJECT (res) = NULL;
3608 DR_TYPE (res) = ARRAY_REF_TYPE;
3609 DR_SET_ACCESS_FNS (res, NULL);
3610 DR_BASE_OBJECT (res) = NULL;
3611 DR_IS_READ (res) = false;
3612 DR_BASE_ADDRESS (res) = NULL_TREE;
3613 DR_OFFSET (res) = NULL_TREE;
3614 DR_INIT (res) = NULL_TREE;
3615 DR_STEP (res) = NULL_TREE;
3616 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
3617 DR_MEMTAG (res) = NULL_TREE;
3618 DR_PTR_INFO (res) = NULL;
3619 VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
3622 return chrec_dont_know;
3626 /* When there are no defs in the loop, the loop is parallel. */
3627 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
3628 loop->parallel_p = false;
3639 /* This section contains all the entry points. */
3641 /* Given a loop nest LOOP, the following vectors are returned:
3642 *DATAREFS is initialized to all the array elements contained in this loop,
3643 *DEPENDENCE_RELATIONS contains the relations between the data references.
3644 Compute read-read and self relations if
3645 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
3648 compute_data_dependences_for_loop (struct loop *loop,
3649 bool compute_self_and_read_read_dependences,
3650 varray_type *datarefs,
3651 varray_type *dependence_relations)
3653 unsigned int i, nb_loops;
3654 VEC(ddr_p,heap) *allrelations;
3655 struct data_dependence_relation *ddr;
3656 struct loop *loop_nest = loop;
3658 while (loop_nest && loop_nest->outer && loop_nest->outer->outer)
3659 loop_nest = loop_nest->outer;
3661 nb_loops = loop_nest->level;
3663 /* If one of the data references is not computable, give up without
3664 spending time to compute other dependences. */
3665 if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
3667 struct data_dependence_relation *ddr;
3669 /* Insert a single relation into dependence_relations:
3671 ddr = initialize_data_dependence_relation (NULL, NULL);
3672 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
3673 build_classic_dist_vector (ddr, nb_loops, loop->depth);
3674 build_classic_dir_vector (ddr, nb_loops, loop->depth);
3678 allrelations = NULL;
3679 compute_all_dependences (*datarefs, compute_self_and_read_read_dependences,
3682 for (i = 0; VEC_iterate (ddr_p, allrelations, i, ddr); i++)
3684 if (build_classic_dist_vector (ddr, nb_loops, loop_nest->depth))
3686 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
3687 build_classic_dir_vector (ddr, nb_loops, loop_nest->depth);
3692 /* Entry point (for testing only). Analyze all the data references
3693 and the dependence relations.
3695 The data references are computed first.
3697 A relation on these nodes is represented by a complete graph. Some
3698 of the relations could be of no interest, thus the relations can be
3701 In the following function we compute all the relations. This is
3702 just a first implementation that is here for:
3703 - for showing how to ask for the dependence relations,
3704 - for the debugging the whole dependence graph,
3705 - for the dejagnu testcases and maintenance.
3707 It is possible to ask only for a part of the graph, avoiding to
3708 compute the whole dependence graph. The computed dependences are
3709 stored in a knowledge base (KB) such that later queries don't
3710 recompute the same information. The implementation of this KB is
3711 transparent to the optimizer, and thus the KB can be changed with a
3712 more efficient implementation, or the KB could be disabled. */
3715 analyze_all_data_dependences (struct loops *loops)
3718 varray_type datarefs;
3719 varray_type dependence_relations;
3720 int nb_data_refs = 10;
3722 VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
3723 VARRAY_GENERIC_PTR_INIT (dependence_relations,
3724 nb_data_refs * nb_data_refs,
3725 "dependence_relations");
3727 /* Compute DDs on the whole function. */
3728 compute_data_dependences_for_loop (loops->parray[0], false,
3729 &datarefs, &dependence_relations);
3733 dump_data_dependence_relations (dump_file, dependence_relations);
3734 fprintf (dump_file, "\n\n");
3736 if (dump_flags & TDF_DETAILS)
3737 dump_dist_dir_vectors (dump_file, dependence_relations);
3739 if (dump_flags & TDF_STATS)
3741 unsigned nb_top_relations = 0;
3742 unsigned nb_bot_relations = 0;
3743 unsigned nb_basename_differ = 0;
3744 unsigned nb_chrec_relations = 0;
3746 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
3748 struct data_dependence_relation *ddr;
3749 ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
3751 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
3754 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
3756 struct data_reference *a = DDR_A (ddr);
3757 struct data_reference *b = DDR_B (ddr);
3760 if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
3761 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
3762 || (base_object_differ_p (a, b, &differ_p)
3764 nb_basename_differ++;
3770 nb_chrec_relations++;
3773 gather_stats_on_scev_database ();
3777 free_dependence_relations (dependence_relations);
3778 free_data_refs (datarefs);
3781 /* Free the memory used by a data dependence relation DDR. */
3784 free_dependence_relation (struct data_dependence_relation *ddr)
3789 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
3790 varray_clear (DDR_SUBSCRIPTS (ddr));
3794 /* Free the memory used by the data dependence relations from
3795 DEPENDENCE_RELATIONS. */
3798 free_dependence_relations (varray_type dependence_relations)
3801 if (dependence_relations == NULL)
3804 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
3805 free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
3806 varray_clear (dependence_relations);
3809 /* Free the memory used by the data references from DATAREFS. */
3812 free_data_refs (varray_type datarefs)
3816 if (datarefs == NULL)
3819 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
3821 struct data_reference *dr = (struct data_reference *)
3822 VARRAY_GENERIC_PTR (datarefs, i);
3825 DR_FREE_ACCESS_FNS (dr);
3829 varray_clear (datarefs);