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 DRA and DRB 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.
392 1. if (both DRA and DRB are represented as arrays)
393 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT
394 2. else if (both DRA and DRB are represented as pointers)
395 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION
396 3. else if (DRA and DRB are represented differently or 2. fails)
397 only try to prove that the bases are surely different
402 base_addr_differ_p (struct data_reference *dra,
403 struct data_reference *drb,
406 tree addr_a = DR_BASE_ADDRESS (dra);
407 tree addr_b = DR_BASE_ADDRESS (drb);
411 if (!addr_a || !addr_b)
414 type_a = TREE_TYPE (addr_a);
415 type_b = TREE_TYPE (addr_b);
417 gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
419 /* 1. if (both DRA and DRB are represented as arrays)
420 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT. */
421 if (DR_TYPE (dra) == ARRAY_REF_TYPE && DR_TYPE (drb) == ARRAY_REF_TYPE)
422 return base_object_differ_p (dra, drb, differ_p);
425 /* 2. else if (both DRA and DRB are represented as pointers)
426 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION. */
427 /* If base addresses are the same, we check the offsets, since the access of
428 the data-ref is described by {base addr + offset} and its access function,
429 i.e., in order to decide whether the bases of data-refs are the same we
430 compare both base addresses and offsets. */
431 if (DR_TYPE (dra) == POINTER_REF_TYPE && DR_TYPE (drb) == POINTER_REF_TYPE
433 || (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR
434 && TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0))))
436 /* Compare offsets. */
437 tree offset_a = DR_OFFSET (dra);
438 tree offset_b = DR_OFFSET (drb);
440 STRIP_NOPS (offset_a);
441 STRIP_NOPS (offset_b);
443 /* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle
445 if ((offset_a == offset_b)
446 || (TREE_CODE (offset_a) == MULT_EXPR
447 && TREE_CODE (offset_b) == MULT_EXPR
448 && TREE_OPERAND (offset_a, 0) == TREE_OPERAND (offset_b, 0)
449 && TREE_OPERAND (offset_a, 1) == TREE_OPERAND (offset_b, 1)))
456 /* 3. else if (DRA and DRB are represented differently or 2. fails)
457 only try to prove that the bases are surely different. */
459 /* Apply alias analysis. */
460 if (may_alias_p (addr_a, addr_b, dra, drb, &aliased) && !aliased)
466 /* An instruction writing through a restricted pointer is "independent" of any
467 instruction reading or writing through a different pointer, in the same
469 else if ((TYPE_RESTRICT (type_a) && !DR_IS_READ (dra))
470 || (TYPE_RESTRICT (type_b) && !DR_IS_READ (drb)))
479 /* Returns true iff A divides B. */
482 tree_fold_divides_p (tree type,
486 /* Determines whether (A == gcd (A, B)). */
488 (fold_build2 (MINUS_EXPR, type, a, tree_fold_gcd (a, b)));
491 /* Compute the greatest common denominator of two numbers using
492 Euclid's algorithm. */
513 /* Returns true iff A divides B. */
516 int_divides_p (int a, int b)
518 return ((b % a) == 0);
523 /* Dump into FILE all the data references from DATAREFS. */
526 dump_data_references (FILE *file,
527 varray_type datarefs)
531 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
532 dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i));
535 /* Dump into FILE all the dependence relations from DDR. */
538 dump_data_dependence_relations (FILE *file,
543 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++)
544 dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i));
547 /* Dump function for a DATA_REFERENCE structure. */
550 dump_data_reference (FILE *outf,
551 struct data_reference *dr)
555 fprintf (outf, "(Data Ref: \n stmt: ");
556 print_generic_stmt (outf, DR_STMT (dr), 0);
557 fprintf (outf, " ref: ");
558 print_generic_stmt (outf, DR_REF (dr), 0);
559 fprintf (outf, " base_name: ");
560 print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
562 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
564 fprintf (outf, " Access function %d: ", i);
565 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
567 fprintf (outf, ")\n");
570 /* Dump function for a SUBSCRIPT structure. */
573 dump_subscript (FILE *outf, struct subscript *subscript)
575 tree chrec = SUB_CONFLICTS_IN_A (subscript);
577 fprintf (outf, "\n (subscript \n");
578 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
579 print_generic_stmt (outf, chrec, 0);
580 if (chrec == chrec_known)
581 fprintf (outf, " (no dependence)\n");
582 else if (chrec_contains_undetermined (chrec))
583 fprintf (outf, " (don't know)\n");
586 tree last_iteration = SUB_LAST_CONFLICT (subscript);
587 fprintf (outf, " last_conflict: ");
588 print_generic_stmt (outf, last_iteration, 0);
591 chrec = SUB_CONFLICTS_IN_B (subscript);
592 fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
593 print_generic_stmt (outf, chrec, 0);
594 if (chrec == chrec_known)
595 fprintf (outf, " (no dependence)\n");
596 else if (chrec_contains_undetermined (chrec))
597 fprintf (outf, " (don't know)\n");
600 tree last_iteration = SUB_LAST_CONFLICT (subscript);
601 fprintf (outf, " last_conflict: ");
602 print_generic_stmt (outf, last_iteration, 0);
605 fprintf (outf, " (Subscript distance: ");
606 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
607 fprintf (outf, " )\n");
608 fprintf (outf, " )\n");
611 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
614 dump_data_dependence_relation (FILE *outf,
615 struct data_dependence_relation *ddr)
617 struct data_reference *dra, *drb;
621 fprintf (outf, "(Data Dep: \n");
622 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
623 fprintf (outf, " (don't know)\n");
625 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
626 fprintf (outf, " (no dependence)\n");
628 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
631 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
633 fprintf (outf, " access_fn_A: ");
634 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
635 fprintf (outf, " access_fn_B: ");
636 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
637 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
639 if (DDR_DIST_VECT (ddr))
641 fprintf (outf, " distance_vect: ");
642 print_lambda_vector (outf, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
644 if (DDR_DIR_VECT (ddr))
646 fprintf (outf, " direction_vect: ");
647 print_lambda_vector (outf, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
651 fprintf (outf, ")\n");
656 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
659 dump_data_dependence_direction (FILE *file,
660 enum data_dependence_direction dir)
676 case dir_positive_or_negative:
677 fprintf (file, "+-");
680 case dir_positive_or_equal:
681 fprintf (file, "+=");
684 case dir_negative_or_equal:
685 fprintf (file, "-=");
697 /* Dumps the distance and direction vectors in FILE. DDRS contains
698 the dependence relations, and VECT_SIZE is the size of the
699 dependence vectors, or in other words the number of loops in the
703 dump_dist_dir_vectors (FILE *file, varray_type ddrs)
707 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
709 struct data_dependence_relation *ddr =
710 (struct data_dependence_relation *)
711 VARRAY_GENERIC_PTR (ddrs, i);
712 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
713 && DDR_AFFINE_P (ddr))
715 fprintf (file, "DISTANCE_V (");
716 print_lambda_vector (file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
717 fprintf (file, ")\n");
718 fprintf (file, "DIRECTION_V (");
719 print_lambda_vector (file, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
720 fprintf (file, ")\n");
723 fprintf (file, "\n\n");
726 /* Dumps the data dependence relations DDRS in FILE. */
729 dump_ddrs (FILE *file, varray_type ddrs)
733 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
735 struct data_dependence_relation *ddr =
736 (struct data_dependence_relation *)
737 VARRAY_GENERIC_PTR (ddrs, i);
738 dump_data_dependence_relation (file, ddr);
740 fprintf (file, "\n\n");
745 /* Estimate the number of iterations from the size of the data and the
749 estimate_niter_from_size_of_data (struct loop *loop,
755 tree array_size, data_size, element_size;
758 init = initial_condition (access_fn);
759 step = evolution_part_in_loop_num (access_fn, loop->num);
761 array_size = TYPE_SIZE (TREE_TYPE (opnd0));
762 element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
763 if (array_size == NULL_TREE
764 || TREE_CODE (array_size) != INTEGER_CST
765 || TREE_CODE (element_size) != INTEGER_CST)
768 data_size = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
769 array_size, element_size);
771 if (init != NULL_TREE
773 && TREE_CODE (init) == INTEGER_CST
774 && TREE_CODE (step) == INTEGER_CST)
776 estimation = fold_build2 (CEIL_DIV_EXPR, integer_type_node,
777 fold_build2 (MINUS_EXPR, integer_type_node,
778 data_size, init), step);
780 record_estimate (loop, estimation, boolean_true_node, stmt);
784 /* Given an ARRAY_REF node REF, records its access functions.
785 Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
786 i.e. the constant "3", then recursively call the function on opnd0,
787 i.e. the ARRAY_REF "A[i]". The function returns the base name:
791 analyze_array_indexes (struct loop *loop,
792 VEC(tree,heap) **access_fns,
798 opnd0 = TREE_OPERAND (ref, 0);
799 opnd1 = TREE_OPERAND (ref, 1);
801 /* The detection of the evolution function for this data access is
802 postponed until the dependence test. This lazy strategy avoids
803 the computation of access functions that are of no interest for
805 access_fn = instantiate_parameters
806 (loop, analyze_scalar_evolution (loop, opnd1));
808 if (chrec_contains_undetermined (loop->estimated_nb_iterations))
809 estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
811 VEC_safe_push (tree, heap, *access_fns, access_fn);
813 /* Recursively record other array access functions. */
814 if (TREE_CODE (opnd0) == ARRAY_REF)
815 return analyze_array_indexes (loop, access_fns, opnd0, stmt);
817 /* Return the base name of the data access. */
822 /* For a data reference REF contained in the statement STMT, initialize
823 a DATA_REFERENCE structure, and return it. IS_READ flag has to be
824 set to true when REF is in the right hand side of an
827 struct data_reference *
828 analyze_array (tree stmt, tree ref, bool is_read)
830 struct data_reference *res;
831 VEC(tree,heap) *acc_fns;
833 if (dump_file && (dump_flags & TDF_DETAILS))
835 fprintf (dump_file, "(analyze_array \n");
836 fprintf (dump_file, " (ref = ");
837 print_generic_stmt (dump_file, ref, 0);
838 fprintf (dump_file, ")\n");
841 res = xmalloc (sizeof (struct data_reference));
843 DR_STMT (res) = stmt;
845 acc_fns = VEC_alloc (tree, heap, 3);
846 DR_BASE_OBJECT (res) = analyze_array_indexes
847 (loop_containing_stmt (stmt), &acc_fns, ref, stmt);
848 DR_TYPE (res) = ARRAY_REF_TYPE;
849 DR_SET_ACCESS_FNS (res, acc_fns);
850 DR_IS_READ (res) = is_read;
851 DR_BASE_ADDRESS (res) = NULL_TREE;
852 DR_OFFSET (res) = NULL_TREE;
853 DR_INIT (res) = NULL_TREE;
854 DR_STEP (res) = NULL_TREE;
855 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
856 DR_MEMTAG (res) = NULL_TREE;
857 DR_PTR_INFO (res) = NULL;
859 if (dump_file && (dump_flags & TDF_DETAILS))
860 fprintf (dump_file, ")\n");
866 /* Analyze an indirect memory reference, REF, that comes from STMT.
867 IS_READ is true if this is an indirect load, and false if it is
869 Return a new data reference structure representing the indirect_ref, or
870 NULL if we cannot describe the access function. */
872 static struct data_reference *
873 analyze_indirect_ref (tree stmt, tree ref, bool is_read)
875 struct loop *loop = loop_containing_stmt (stmt);
876 tree ptr_ref = TREE_OPERAND (ref, 0);
877 tree access_fn = analyze_scalar_evolution (loop, ptr_ref);
878 tree init = initial_condition_in_loop_num (access_fn, loop->num);
879 tree base_address = NULL_TREE, evolution, step = NULL_TREE;
880 struct ptr_info_def *ptr_info = NULL;
882 if (TREE_CODE (ptr_ref) == SSA_NAME)
883 ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
886 if (access_fn == chrec_dont_know || !init || init == chrec_dont_know)
888 if (dump_file && (dump_flags & TDF_DETAILS))
890 fprintf (dump_file, "\nBad access function of ptr: ");
891 print_generic_expr (dump_file, ref, TDF_SLIM);
892 fprintf (dump_file, "\n");
897 if (dump_file && (dump_flags & TDF_DETAILS))
899 fprintf (dump_file, "\nAccess function of ptr: ");
900 print_generic_expr (dump_file, access_fn, TDF_SLIM);
901 fprintf (dump_file, "\n");
904 if (!expr_invariant_in_loop_p (loop, init))
906 if (dump_file && (dump_flags & TDF_DETAILS))
907 fprintf (dump_file, "\ninitial condition is not loop invariant.\n");
912 evolution = evolution_part_in_loop_num (access_fn, loop->num);
913 if (evolution != chrec_dont_know)
916 step = ssize_int (0);
919 if (TREE_CODE (evolution) == INTEGER_CST)
920 step = fold_convert (ssizetype, evolution);
922 if (dump_file && (dump_flags & TDF_DETAILS))
923 fprintf (dump_file, "\nnon constant step for ptr access.\n");
927 if (dump_file && (dump_flags & TDF_DETAILS))
928 fprintf (dump_file, "\nunknown evolution of ptr.\n");
930 return init_data_ref (stmt, ref, NULL_TREE, access_fn, is_read, base_address,
931 NULL_TREE, step, NULL_TREE, NULL_TREE,
932 ptr_info, POINTER_REF_TYPE);
935 /* For a data reference REF contained in the statement STMT, initialize
936 a DATA_REFERENCE structure, and return it. */
938 struct data_reference *
939 init_data_ref (tree stmt,
949 struct ptr_info_def *ptr_info,
950 enum data_ref_type type)
952 struct data_reference *res;
953 VEC(tree,heap) *acc_fns;
955 if (dump_file && (dump_flags & TDF_DETAILS))
957 fprintf (dump_file, "(init_data_ref \n");
958 fprintf (dump_file, " (ref = ");
959 print_generic_stmt (dump_file, ref, 0);
960 fprintf (dump_file, ")\n");
963 res = xmalloc (sizeof (struct data_reference));
965 DR_STMT (res) = stmt;
967 DR_BASE_OBJECT (res) = base;
968 DR_TYPE (res) = type;
969 acc_fns = VEC_alloc (tree, heap, 3);
970 DR_SET_ACCESS_FNS (res, acc_fns);
971 VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
972 DR_IS_READ (res) = is_read;
973 DR_BASE_ADDRESS (res) = base_address;
974 DR_OFFSET (res) = init_offset;
975 DR_INIT (res) = NULL_TREE;
976 DR_STEP (res) = step;
977 DR_OFFSET_MISALIGNMENT (res) = misalign;
978 DR_MEMTAG (res) = memtag;
979 DR_PTR_INFO (res) = ptr_info;
981 if (dump_file && (dump_flags & TDF_DETAILS))
982 fprintf (dump_file, ")\n");
989 /* Function strip_conversions
991 Strip conversions that don't narrow the mode. */
994 strip_conversion (tree expr)
998 while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
1000 to = TREE_TYPE (expr);
1001 oprnd0 = TREE_OPERAND (expr, 0);
1002 ti = TREE_TYPE (oprnd0);
1004 if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti))
1006 if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti)))
1015 /* Function analyze_offset_expr
1017 Given an offset expression EXPR received from get_inner_reference, analyze
1018 it and create an expression for INITIAL_OFFSET by substituting the variables
1019 of EXPR with initial_condition of the corresponding access_fn in the loop.
1022 for (j = 3; j < N; j++)
1025 For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be
1026 substituted, since its access_fn in the inner loop is i. 'j' will be
1027 substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
1030 Compute MISALIGN (the misalignment of the data reference initial access from
1031 its base). Misalignment can be calculated only if all the variables can be
1032 substituted with constants, otherwise, we record maximum possible alignment
1033 in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN
1034 will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be
1035 recorded in ALIGNED_TO.
1037 STEP is an evolution of the data reference in this loop in bytes.
1038 In the above example, STEP is C_j.
1040 Return FALSE, if the analysis fails, e.g., there is no access_fn for a
1041 variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO
1042 and STEP) are NULL_TREEs. Otherwise, return TRUE.
1047 analyze_offset_expr (tree expr,
1049 tree *initial_offset,
1056 tree left_offset = ssize_int (0);
1057 tree right_offset = ssize_int (0);
1058 tree left_misalign = ssize_int (0);
1059 tree right_misalign = ssize_int (0);
1060 tree left_step = ssize_int (0);
1061 tree right_step = ssize_int (0);
1062 enum tree_code code;
1063 tree init, evolution;
1064 tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE;
1067 *misalign = NULL_TREE;
1068 *aligned_to = NULL_TREE;
1069 *initial_offset = NULL_TREE;
1071 /* Strip conversions that don't narrow the mode. */
1072 expr = strip_conversion (expr);
1078 if (TREE_CODE (expr) == INTEGER_CST)
1080 *initial_offset = fold_convert (ssizetype, expr);
1081 *misalign = fold_convert (ssizetype, expr);
1082 *step = ssize_int (0);
1086 /* 2. Variable. Try to substitute with initial_condition of the corresponding
1087 access_fn in the current loop. */
1088 if (SSA_VAR_P (expr))
1090 tree access_fn = analyze_scalar_evolution (loop, expr);
1092 if (access_fn == chrec_dont_know)
1096 init = initial_condition_in_loop_num (access_fn, loop->num);
1097 if (init == expr && !expr_invariant_in_loop_p (loop, init))
1098 /* Not enough information: may be not loop invariant.
1099 E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
1100 initial_condition is D, but it depends on i - loop's induction
1104 evolution = evolution_part_in_loop_num (access_fn, loop->num);
1105 if (evolution && TREE_CODE (evolution) != INTEGER_CST)
1106 /* Evolution is not constant. */
1109 if (TREE_CODE (init) == INTEGER_CST)
1110 *misalign = fold_convert (ssizetype, init);
1112 /* Not constant, misalignment cannot be calculated. */
1113 *misalign = NULL_TREE;
1115 *initial_offset = fold_convert (ssizetype, init);
1117 *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
1121 /* Recursive computation. */
1122 if (!BINARY_CLASS_P (expr))
1124 /* We expect to get binary expressions (PLUS/MINUS and MULT). */
1125 if (dump_file && (dump_flags & TDF_DETAILS))
1127 fprintf (dump_file, "\nNot binary expression ");
1128 print_generic_expr (dump_file, expr, TDF_SLIM);
1129 fprintf (dump_file, "\n");
1133 oprnd0 = TREE_OPERAND (expr, 0);
1134 oprnd1 = TREE_OPERAND (expr, 1);
1136 if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign,
1137 &left_aligned_to, &left_step)
1138 || !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign,
1139 &right_aligned_to, &right_step))
1142 /* The type of the operation: plus, minus or mult. */
1143 code = TREE_CODE (expr);
1147 if (TREE_CODE (right_offset) != INTEGER_CST)
1148 /* RIGHT_OFFSET can be not constant. For example, for arrays of variable
1150 FORNOW: We don't support such cases. */
1153 /* Strip conversions that don't narrow the mode. */
1154 left_offset = strip_conversion (left_offset);
1157 /* Misalignment computation. */
1158 if (SSA_VAR_P (left_offset))
1160 /* If the left side contains variables that can't be substituted with
1161 constants, the misalignment is unknown. However, if the right side
1162 is a multiple of some alignment, we know that the expression is
1163 aligned to it. Therefore, we record such maximum possible value.
1165 *misalign = NULL_TREE;
1166 *aligned_to = ssize_int (highest_pow2_factor (right_offset));
1170 /* The left operand was successfully substituted with constant. */
1173 /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is
1175 *misalign = size_binop (code, left_misalign, right_misalign);
1176 if (left_aligned_to && right_aligned_to)
1177 *aligned_to = size_binop (MIN_EXPR, left_aligned_to,
1180 *aligned_to = left_aligned_to ?
1181 left_aligned_to : right_aligned_to;
1184 *misalign = NULL_TREE;
1187 /* Step calculation. */
1188 /* Multiply the step by the right operand. */
1189 *step = size_binop (MULT_EXPR, left_step, right_offset);
1194 /* Combine the recursive calculations for step and misalignment. */
1195 *step = size_binop (code, left_step, right_step);
1197 /* Unknown alignment. */
1198 if ((!left_misalign && !left_aligned_to)
1199 || (!right_misalign && !right_aligned_to))
1201 *misalign = NULL_TREE;
1202 *aligned_to = NULL_TREE;
1206 if (left_misalign && right_misalign)
1207 *misalign = size_binop (code, left_misalign, right_misalign);
1209 *misalign = left_misalign ? left_misalign : right_misalign;
1211 if (left_aligned_to && right_aligned_to)
1212 *aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to);
1214 *aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to;
1222 /* Compute offset. */
1223 *initial_offset = fold_convert (ssizetype,
1224 fold_build2 (code, TREE_TYPE (left_offset),
1230 /* Function address_analysis
1232 Return the BASE of the address expression EXPR.
1233 Also compute the OFFSET from BASE, MISALIGN and STEP.
1236 EXPR - the address expression that is being analyzed
1237 STMT - the statement that contains EXPR or its original memory reference
1238 IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
1239 DR - data_reference struct for the original memory reference
1242 BASE (returned value) - the base of the data reference EXPR.
1243 INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
1244 MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
1245 computation is impossible
1246 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1247 calculated (doesn't depend on variables)
1248 STEP - evolution of EXPR in the loop
1250 If something unexpected is encountered (an unsupported form of data-ref),
1251 then NULL_TREE is returned.
1255 address_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr,
1256 tree *offset, tree *misalign, tree *aligned_to, tree *step)
1258 tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
1259 tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1260 tree dummy, address_aligned_to = NULL_TREE;
1261 struct ptr_info_def *dummy1;
1264 switch (TREE_CODE (expr))
1268 /* EXPR is of form {base +/- offset} (or {offset +/- base}). */
1269 oprnd0 = TREE_OPERAND (expr, 0);
1270 oprnd1 = TREE_OPERAND (expr, 1);
1272 STRIP_NOPS (oprnd0);
1273 STRIP_NOPS (oprnd1);
1275 /* Recursively try to find the base of the address contained in EXPR.
1276 For offset, the returned base will be NULL. */
1277 base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset,
1278 &address_misalign, &address_aligned_to,
1281 base_addr1 = address_analysis (oprnd1, stmt, is_read, dr, &address_offset,
1282 &address_misalign, &address_aligned_to,
1285 /* We support cases where only one of the operands contains an
1287 if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
1289 if (dump_file && (dump_flags & TDF_DETAILS))
1292 "\neither more than one address or no addresses in expr ");
1293 print_generic_expr (dump_file, expr, TDF_SLIM);
1294 fprintf (dump_file, "\n");
1299 /* To revert STRIP_NOPS. */
1300 oprnd0 = TREE_OPERAND (expr, 0);
1301 oprnd1 = TREE_OPERAND (expr, 1);
1303 offset_expr = base_addr0 ?
1304 fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
1306 /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is
1307 a number, we can add it to the misalignment value calculated for base,
1308 otherwise, misalignment is NULL. */
1309 if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
1311 *misalign = size_binop (TREE_CODE (expr), address_misalign,
1313 *aligned_to = address_aligned_to;
1317 *misalign = NULL_TREE;
1318 *aligned_to = NULL_TREE;
1321 /* Combine offset (from EXPR {base + offset}) with the offset calculated
1323 *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
1324 return base_addr0 ? base_addr0 : base_addr1;
1327 base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read,
1328 &dr, offset, misalign, aligned_to, step,
1329 &dummy, &dummy1, &dummy2);
1330 return base_address;
1333 if (!POINTER_TYPE_P (TREE_TYPE (expr)))
1335 if (dump_file && (dump_flags & TDF_DETAILS))
1337 fprintf (dump_file, "\nnot pointer SSA_NAME ");
1338 print_generic_expr (dump_file, expr, TDF_SLIM);
1339 fprintf (dump_file, "\n");
1343 *aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr))));
1344 *misalign = ssize_int (0);
1345 *offset = ssize_int (0);
1346 *step = ssize_int (0);
1355 /* Function object_analysis
1357 Create a data-reference structure DR for MEMREF.
1358 Return the BASE of the data reference MEMREF if the analysis is possible.
1359 Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1360 E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset
1361 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET
1362 instantiated with initial_conditions of access_functions of variables,
1363 and STEP is the evolution of the DR_REF in this loop.
1365 Function get_inner_reference is used for the above in case of ARRAY_REF and
1368 The structure of the function is as follows:
1370 Case 1. For handled_component_p refs
1371 1.1 build data-reference structure for MEMREF
1372 1.2 call get_inner_reference
1373 1.2.1 analyze offset expr received from get_inner_reference
1374 (fall through with BASE)
1375 Case 2. For declarations
1377 Case 3. For INDIRECT_REFs
1378 3.1 build data-reference structure for MEMREF
1379 3.2 analyze evolution and initial condition of MEMREF
1380 3.3 set data-reference structure for MEMREF
1381 3.4 call address_analysis to analyze INIT of the access function
1382 3.5 extract memory tag
1385 Combine the results of object and address analysis to calculate
1386 INITIAL_OFFSET, STEP and misalignment info.
1389 MEMREF - the memory reference that is being analyzed
1390 STMT - the statement that contains MEMREF
1391 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1394 BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
1395 E.g, if MEMREF is a.b[k].c[i][j] the returned
1397 DR - data_reference struct for MEMREF
1398 INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
1399 MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of
1400 ALIGNMENT or NULL_TREE if the computation is impossible
1401 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1402 calculated (doesn't depend on variables)
1403 STEP - evolution of the DR_REF in the loop
1404 MEMTAG - memory tag for aliasing purposes
1405 PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
1406 SUBVARS - Sub-variables of the variable
1408 If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned,
1409 but DR can be created anyway.
1414 object_analysis (tree memref, tree stmt, bool is_read,
1415 struct data_reference **dr, tree *offset, tree *misalign,
1416 tree *aligned_to, tree *step, tree *memtag,
1417 struct ptr_info_def **ptr_info, subvar_t *subvars)
1419 tree base = NULL_TREE, base_address = NULL_TREE;
1420 tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
1421 tree object_step = ssize_int (0), address_step = ssize_int (0);
1422 tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1423 HOST_WIDE_INT pbitsize, pbitpos;
1424 tree poffset, bit_pos_in_bytes;
1425 enum machine_mode pmode;
1426 int punsignedp, pvolatilep;
1427 tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
1428 struct loop *loop = loop_containing_stmt (stmt);
1429 struct data_reference *ptr_dr = NULL;
1430 tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE;
1435 /* Case 1. handled_component_p refs. */
1436 if (handled_component_p (memref))
1438 /* 1.1 build data-reference structure for MEMREF. */
1439 /* TODO: handle COMPONENT_REFs. */
1442 if (TREE_CODE (memref) == ARRAY_REF)
1443 *dr = analyze_array (stmt, memref, is_read);
1447 if (dump_file && (dump_flags & TDF_DETAILS))
1449 fprintf (dump_file, "\ndata-ref of unsupported type ");
1450 print_generic_expr (dump_file, memref, TDF_SLIM);
1451 fprintf (dump_file, "\n");
1457 /* 1.2 call get_inner_reference. */
1458 /* Find the base and the offset from it. */
1459 base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
1460 &pmode, &punsignedp, &pvolatilep, false);
1463 if (dump_file && (dump_flags & TDF_DETAILS))
1465 fprintf (dump_file, "\nfailed to get inner ref for ");
1466 print_generic_expr (dump_file, memref, TDF_SLIM);
1467 fprintf (dump_file, "\n");
1472 /* 1.2.1 analyze offset expr received from get_inner_reference. */
1474 && !analyze_offset_expr (poffset, loop, &object_offset,
1475 &object_misalign, &object_aligned_to,
1478 if (dump_file && (dump_flags & TDF_DETAILS))
1480 fprintf (dump_file, "\nfailed to compute offset or step for ");
1481 print_generic_expr (dump_file, memref, TDF_SLIM);
1482 fprintf (dump_file, "\n");
1487 /* Add bit position to OFFSET and MISALIGN. */
1489 bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
1490 /* Check that there is no remainder in bits. */
1491 if (pbitpos%BITS_PER_UNIT)
1493 if (dump_file && (dump_flags & TDF_DETAILS))
1494 fprintf (dump_file, "\nbit offset alignment.\n");
1497 object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);
1498 if (object_misalign)
1499 object_misalign = size_binop (PLUS_EXPR, object_misalign,
1502 memref = base; /* To continue analysis of BASE. */
1506 /* Part 1: Case 2. Declarations. */
1507 if (DECL_P (memref))
1509 /* We expect to get a decl only if we already have a DR. */
1512 if (dump_file && (dump_flags & TDF_DETAILS))
1514 fprintf (dump_file, "\nunhandled decl ");
1515 print_generic_expr (dump_file, memref, TDF_SLIM);
1516 fprintf (dump_file, "\n");
1521 /* TODO: if during the analysis of INDIRECT_REF we get to an object, put
1522 the object in BASE_OBJECT field if we can prove that this is O.K.,
1523 i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT.
1524 (e.g., if the object is an array base 'a', where 'a[N]', we must prove
1525 that every access with 'p' (the original INDIRECT_REF based on '&a')
1526 in the loop is within the array boundaries - from a[0] to a[N-1]).
1527 Otherwise, our alias analysis can be incorrect.
1528 Even if an access function based on BASE_OBJECT can't be build, update
1529 BASE_OBJECT field to enable us to prove that two data-refs are
1530 different (without access function, distance analysis is impossible).
1532 if (SSA_VAR_P (memref) && var_can_have_subvars (memref))
1533 *subvars = get_subvars_for_var (memref);
1534 base_address = build_fold_addr_expr (memref);
1535 /* 2.1 set MEMTAG. */
1539 /* Part 1: Case 3. INDIRECT_REFs. */
1540 else if (TREE_CODE (memref) == INDIRECT_REF)
1542 tree ptr_ref = TREE_OPERAND (memref, 0);
1543 if (TREE_CODE (ptr_ref) == SSA_NAME)
1544 *ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
1546 /* 3.1 build data-reference structure for MEMREF. */
1547 ptr_dr = analyze_indirect_ref (stmt, memref, is_read);
1550 if (dump_file && (dump_flags & TDF_DETAILS))
1552 fprintf (dump_file, "\nfailed to create dr for ");
1553 print_generic_expr (dump_file, memref, TDF_SLIM);
1554 fprintf (dump_file, "\n");
1559 /* 3.2 analyze evolution and initial condition of MEMREF. */
1560 ptr_step = DR_STEP (ptr_dr);
1561 ptr_init = DR_BASE_ADDRESS (ptr_dr);
1562 if (!ptr_init || !ptr_step || !POINTER_TYPE_P (TREE_TYPE (ptr_init)))
1564 *dr = (*dr) ? *dr : ptr_dr;
1565 if (dump_file && (dump_flags & TDF_DETAILS))
1567 fprintf (dump_file, "\nbad pointer access ");
1568 print_generic_expr (dump_file, memref, TDF_SLIM);
1569 fprintf (dump_file, "\n");
1574 if (integer_zerop (ptr_step) && !(*dr))
1576 if (dump_file && (dump_flags & TDF_DETAILS))
1577 fprintf (dump_file, "\nptr is loop invariant.\n");
1581 /* If there exists DR for MEMREF, we are analyzing the base of
1582 handled component (PTR_INIT), which not necessary has evolution in
1585 object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
1587 /* 3.3 set data-reference structure for MEMREF. */
1591 /* 3.4 call address_analysis to analyze INIT of the access
1593 base_address = address_analysis (ptr_init, stmt, is_read, *dr,
1594 &address_offset, &address_misalign,
1595 &address_aligned_to, &address_step);
1598 if (dump_file && (dump_flags & TDF_DETAILS))
1600 fprintf (dump_file, "\nfailed to analyze address ");
1601 print_generic_expr (dump_file, ptr_init, TDF_SLIM);
1602 fprintf (dump_file, "\n");
1607 /* 3.5 extract memory tag. */
1608 switch (TREE_CODE (base_address))
1611 *memtag = get_var_ann (SSA_NAME_VAR (base_address))->type_mem_tag;
1612 if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
1613 *memtag = get_var_ann (
1614 SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->type_mem_tag;
1617 *memtag = TREE_OPERAND (base_address, 0);
1620 if (dump_file && (dump_flags & TDF_DETAILS))
1622 fprintf (dump_file, "\nno memtag for ");
1623 print_generic_expr (dump_file, memref, TDF_SLIM);
1624 fprintf (dump_file, "\n");
1626 *memtag = NULL_TREE;
1633 /* MEMREF cannot be analyzed. */
1634 if (dump_file && (dump_flags & TDF_DETAILS))
1636 fprintf (dump_file, "\ndata-ref of unsupported type ");
1637 print_generic_expr (dump_file, memref, TDF_SLIM);
1638 fprintf (dump_file, "\n");
1643 if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag))
1644 *subvars = get_subvars_for_var (*memtag);
1646 /* Part 2: Combine the results of object and address analysis to calculate
1647 INITIAL_OFFSET, STEP and misalignment info. */
1648 *offset = size_binop (PLUS_EXPR, object_offset, address_offset);
1650 if ((!object_misalign && !object_aligned_to)
1651 || (!address_misalign && !address_aligned_to))
1653 *misalign = NULL_TREE;
1654 *aligned_to = NULL_TREE;
1658 if (object_misalign && address_misalign)
1659 *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
1661 *misalign = object_misalign ? object_misalign : address_misalign;
1662 if (object_aligned_to && address_aligned_to)
1663 *aligned_to = size_binop (MIN_EXPR, object_aligned_to,
1664 address_aligned_to);
1666 *aligned_to = object_aligned_to ?
1667 object_aligned_to : address_aligned_to;
1669 *step = size_binop (PLUS_EXPR, object_step, address_step);
1671 return base_address;
1674 /* Function analyze_offset.
1676 Extract INVARIANT and CONSTANT parts from OFFSET.
1680 analyze_offset (tree offset, tree *invariant, tree *constant)
1682 tree op0, op1, constant_0, constant_1, invariant_0, invariant_1;
1683 enum tree_code code = TREE_CODE (offset);
1685 *invariant = NULL_TREE;
1686 *constant = NULL_TREE;
1688 /* Not PLUS/MINUS expression - recursion stop condition. */
1689 if (code != PLUS_EXPR && code != MINUS_EXPR)
1691 if (TREE_CODE (offset) == INTEGER_CST)
1694 *invariant = offset;
1698 op0 = TREE_OPERAND (offset, 0);
1699 op1 = TREE_OPERAND (offset, 1);
1701 /* Recursive call with the operands. */
1702 analyze_offset (op0, &invariant_0, &constant_0);
1703 analyze_offset (op1, &invariant_1, &constant_1);
1705 /* Combine the results. */
1706 *constant = constant_0 ? constant_0 : constant_1;
1707 if (invariant_0 && invariant_1)
1709 fold (build (code, TREE_TYPE (invariant_0), invariant_0, invariant_1));
1711 *invariant = invariant_0 ? invariant_0 : invariant_1;
1715 /* Function create_data_ref.
1717 Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS,
1718 DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO,
1719 DR_MEMTAG, and DR_POINTSTO_INFO fields.
1722 MEMREF - the memory reference that is being analyzed
1723 STMT - the statement that contains MEMREF
1724 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1727 DR (returned value) - data_reference struct for MEMREF
1730 static struct data_reference *
1731 create_data_ref (tree memref, tree stmt, bool is_read)
1733 struct data_reference *dr = NULL;
1734 tree base_address, offset, step, misalign, memtag;
1735 struct loop *loop = loop_containing_stmt (stmt);
1736 tree invariant = NULL_TREE, constant = NULL_TREE;
1737 tree type_size, init_cond;
1738 struct ptr_info_def *ptr_info;
1739 subvar_t subvars = NULL;
1745 base_address = object_analysis (memref, stmt, is_read, &dr, &offset,
1746 &misalign, &aligned_to, &step, &memtag,
1747 &ptr_info, &subvars);
1748 if (!dr || !base_address)
1750 if (dump_file && (dump_flags & TDF_DETAILS))
1752 fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for ");
1753 print_generic_expr (dump_file, memref, TDF_SLIM);
1754 fprintf (dump_file, "\n");
1759 DR_BASE_ADDRESS (dr) = base_address;
1760 DR_OFFSET (dr) = offset;
1761 DR_INIT (dr) = ssize_int (0);
1762 DR_STEP (dr) = step;
1763 DR_OFFSET_MISALIGNMENT (dr) = misalign;
1764 DR_ALIGNED_TO (dr) = aligned_to;
1765 DR_MEMTAG (dr) = memtag;
1766 DR_PTR_INFO (dr) = ptr_info;
1767 DR_SUBVARS (dr) = subvars;
1769 type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
1771 /* Change the access function for INIDIRECT_REFs, according to
1772 DR_BASE_ADDRESS. Analyze OFFSET calculated in object_analysis. OFFSET is
1773 an expression that can contain loop invariant expressions and constants.
1774 We put the constant part in the initial condition of the access function
1775 (for data dependence tests), and in DR_INIT of the data-ref. The loop
1776 invariant part is put in DR_OFFSET.
1777 The evolution part of the access function is STEP calculated in
1778 object_analysis divided by the size of data type.
1780 if (!DR_BASE_OBJECT (dr))
1785 /* Extract CONSTANT and INVARIANT from OFFSET, and put them in DR_INIT and
1786 DR_OFFSET fields of DR. */
1787 analyze_offset (offset, &invariant, &constant);
1790 DR_INIT (dr) = fold_convert (ssizetype, constant);
1791 init_cond = fold (build (TRUNC_DIV_EXPR, TREE_TYPE (constant),
1792 constant, type_size));
1795 DR_INIT (dr) = init_cond = ssize_int (0);;
1798 DR_OFFSET (dr) = invariant;
1800 DR_OFFSET (dr) = ssize_int (0);
1802 /* Update access function. */
1803 access_fn = DR_ACCESS_FN (dr, 0);
1804 new_step = size_binop (TRUNC_DIV_EXPR,
1805 fold_convert (ssizetype, step), type_size);
1807 access_fn = chrec_replace_initial_condition (access_fn, init_cond);
1808 access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step);
1810 VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn);
1813 if (dump_file && (dump_flags & TDF_DETAILS))
1815 struct ptr_info_def *pi = DR_PTR_INFO (dr);
1817 fprintf (dump_file, "\nCreated dr for ");
1818 print_generic_expr (dump_file, memref, TDF_SLIM);
1819 fprintf (dump_file, "\n\tbase_address: ");
1820 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
1821 fprintf (dump_file, "\n\toffset from base address: ");
1822 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
1823 fprintf (dump_file, "\n\tconstant offset from base address: ");
1824 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
1825 fprintf (dump_file, "\n\tbase_object: ");
1826 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
1827 fprintf (dump_file, "\n\tstep: ");
1828 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
1829 fprintf (dump_file, "B\n\tmisalignment from base: ");
1830 print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM);
1831 if (DR_OFFSET_MISALIGNMENT (dr))
1832 fprintf (dump_file, "B");
1833 if (DR_ALIGNED_TO (dr))
1835 fprintf (dump_file, "\n\taligned to: ");
1836 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
1838 fprintf (dump_file, "\n\tmemtag: ");
1839 print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM);
1840 fprintf (dump_file, "\n");
1841 if (pi && pi->name_mem_tag)
1843 fprintf (dump_file, "\n\tnametag: ");
1844 print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM);
1845 fprintf (dump_file, "\n");
1852 /* Returns true when all the functions of a tree_vec CHREC are the
1856 all_chrecs_equal_p (tree chrec)
1860 for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
1862 tree chrec_j = TREE_VEC_ELT (chrec, j);
1863 tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1);
1866 (integer_type_node, chrec_j, chrec_j_1)))
1872 /* Determine for each subscript in the data dependence relation DDR
1876 compute_subscript_distance (struct data_dependence_relation *ddr)
1878 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1882 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1884 tree conflicts_a, conflicts_b, difference;
1885 struct subscript *subscript;
1887 subscript = DDR_SUBSCRIPT (ddr, i);
1888 conflicts_a = SUB_CONFLICTS_IN_A (subscript);
1889 conflicts_b = SUB_CONFLICTS_IN_B (subscript);
1891 if (TREE_CODE (conflicts_a) == TREE_VEC)
1893 if (!all_chrecs_equal_p (conflicts_a))
1895 SUB_DISTANCE (subscript) = chrec_dont_know;
1899 conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
1902 if (TREE_CODE (conflicts_b) == TREE_VEC)
1904 if (!all_chrecs_equal_p (conflicts_b))
1906 SUB_DISTANCE (subscript) = chrec_dont_know;
1910 conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
1913 difference = chrec_fold_minus
1914 (integer_type_node, conflicts_b, conflicts_a);
1916 if (evolution_function_is_constant_p (difference))
1917 SUB_DISTANCE (subscript) = difference;
1920 SUB_DISTANCE (subscript) = chrec_dont_know;
1925 /* Initialize a ddr. */
1927 struct data_dependence_relation *
1928 initialize_data_dependence_relation (struct data_reference *a,
1929 struct data_reference *b)
1931 struct data_dependence_relation *res;
1935 res = xmalloc (sizeof (struct data_dependence_relation));
1939 if (a == NULL || b == NULL)
1941 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1945 /* When A and B are arrays and their dimensions differ, we directly
1946 initialize the relation to "there is no dependence": chrec_known. */
1947 if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
1948 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
1950 DDR_ARE_DEPENDENT (res) = chrec_known;
1954 /* Compare the bases of the data-refs. */
1955 if (!base_addr_differ_p (a, b, &differ_p))
1957 /* Can't determine whether the data-refs access the same memory
1959 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1964 DDR_ARE_DEPENDENT (res) = chrec_known;
1968 DDR_AFFINE_P (res) = true;
1969 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1970 DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
1971 DDR_SIZE_VECT (res) = 0;
1972 DDR_DIST_VECT (res) = NULL;
1973 DDR_DIR_VECT (res) = NULL;
1975 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1977 struct subscript *subscript;
1979 subscript = xmalloc (sizeof (struct subscript));
1980 SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
1981 SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
1982 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1983 SUB_DISTANCE (subscript) = chrec_dont_know;
1984 VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
1990 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1994 finalize_ddr_dependent (struct data_dependence_relation *ddr,
1997 if (dump_file && (dump_flags & TDF_DETAILS))
1999 fprintf (dump_file, "(dependence classified: ");
2000 print_generic_expr (dump_file, chrec, 0);
2001 fprintf (dump_file, ")\n");
2004 DDR_ARE_DEPENDENT (ddr) = chrec;
2005 varray_clear (DDR_SUBSCRIPTS (ddr));
2008 /* The dependence relation DDR cannot be represented by a distance
2012 non_affine_dependence_relation (struct data_dependence_relation *ddr)
2014 if (dump_file && (dump_flags & TDF_DETAILS))
2015 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
2017 DDR_AFFINE_P (ddr) = false;
2022 /* This section contains the classic Banerjee tests. */
2024 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
2025 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
2028 ziv_subscript_p (tree chrec_a,
2031 return (evolution_function_is_constant_p (chrec_a)
2032 && evolution_function_is_constant_p (chrec_b));
2035 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
2036 variable, i.e., if the SIV (Single Index Variable) test is true. */
2039 siv_subscript_p (tree chrec_a,
2042 if ((evolution_function_is_constant_p (chrec_a)
2043 && evolution_function_is_univariate_p (chrec_b))
2044 || (evolution_function_is_constant_p (chrec_b)
2045 && evolution_function_is_univariate_p (chrec_a)))
2048 if (evolution_function_is_univariate_p (chrec_a)
2049 && evolution_function_is_univariate_p (chrec_b))
2051 switch (TREE_CODE (chrec_a))
2053 case POLYNOMIAL_CHREC:
2054 switch (TREE_CODE (chrec_b))
2056 case POLYNOMIAL_CHREC:
2057 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
2072 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
2073 *OVERLAPS_B are initialized to the functions that describe the
2074 relation between the elements accessed twice by CHREC_A and
2075 CHREC_B. For k >= 0, the following property is verified:
2077 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2080 analyze_ziv_subscript (tree chrec_a,
2084 tree *last_conflicts)
2088 if (dump_file && (dump_flags & TDF_DETAILS))
2089 fprintf (dump_file, "(analyze_ziv_subscript \n");
2091 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2093 switch (TREE_CODE (difference))
2096 if (integer_zerop (difference))
2098 /* The difference is equal to zero: the accessed index
2099 overlaps for each iteration in the loop. */
2100 *overlaps_a = integer_zero_node;
2101 *overlaps_b = integer_zero_node;
2102 *last_conflicts = chrec_dont_know;
2106 /* The accesses do not overlap. */
2107 *overlaps_a = chrec_known;
2108 *overlaps_b = chrec_known;
2109 *last_conflicts = integer_zero_node;
2114 /* We're not sure whether the indexes overlap. For the moment,
2115 conservatively answer "don't know". */
2116 *overlaps_a = chrec_dont_know;
2117 *overlaps_b = chrec_dont_know;
2118 *last_conflicts = chrec_dont_know;
2122 if (dump_file && (dump_flags & TDF_DETAILS))
2123 fprintf (dump_file, ")\n");
2126 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2127 constant, and CHREC_B is an affine function. *OVERLAPS_A and
2128 *OVERLAPS_B are initialized to the functions that describe the
2129 relation between the elements accessed twice by CHREC_A and
2130 CHREC_B. For k >= 0, the following property is verified:
2132 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2135 analyze_siv_subscript_cst_affine (tree chrec_a,
2139 tree *last_conflicts)
2141 bool value0, value1, value2;
2142 tree difference = chrec_fold_minus
2143 (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
2145 if (!chrec_is_positive (initial_condition (difference), &value0))
2147 *overlaps_a = chrec_dont_know;
2148 *overlaps_b = chrec_dont_know;
2149 *last_conflicts = chrec_dont_know;
2154 if (value0 == false)
2156 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
2158 *overlaps_a = chrec_dont_know;
2159 *overlaps_b = chrec_dont_know;
2160 *last_conflicts = chrec_dont_know;
2169 chrec_b = {10, +, 1}
2172 if (tree_fold_divides_p
2173 (integer_type_node, CHREC_RIGHT (chrec_b), difference))
2175 *overlaps_a = integer_zero_node;
2176 *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
2177 fold_build1 (ABS_EXPR,
2180 CHREC_RIGHT (chrec_b));
2181 *last_conflicts = integer_one_node;
2185 /* When the step does not divides the difference, there are
2189 *overlaps_a = chrec_known;
2190 *overlaps_b = chrec_known;
2191 *last_conflicts = integer_zero_node;
2200 chrec_b = {10, +, -1}
2202 In this case, chrec_a will not overlap with chrec_b. */
2203 *overlaps_a = chrec_known;
2204 *overlaps_b = chrec_known;
2205 *last_conflicts = integer_zero_node;
2212 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
2214 *overlaps_a = chrec_dont_know;
2215 *overlaps_b = chrec_dont_know;
2216 *last_conflicts = chrec_dont_know;
2221 if (value2 == false)
2225 chrec_b = {10, +, -1}
2227 if (tree_fold_divides_p
2228 (integer_type_node, CHREC_RIGHT (chrec_b), difference))
2230 *overlaps_a = integer_zero_node;
2232 (build (EXACT_DIV_EXPR, integer_type_node, difference,
2233 CHREC_RIGHT (chrec_b)));
2234 *last_conflicts = integer_one_node;
2238 /* When the step does not divides the difference, there
2242 *overlaps_a = chrec_known;
2243 *overlaps_b = chrec_known;
2244 *last_conflicts = integer_zero_node;
2254 In this case, chrec_a will not overlap with chrec_b. */
2255 *overlaps_a = chrec_known;
2256 *overlaps_b = chrec_known;
2257 *last_conflicts = integer_zero_node;
2265 /* Helper recursive function for initializing the matrix A. Returns
2266 the initial value of CHREC. */
2269 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2273 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2274 return int_cst_value (chrec);
2276 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2277 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2280 #define FLOOR_DIV(x,y) ((x) / (y))
2282 /* Solves the special case of the Diophantine equation:
2283 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2285 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2286 number of iterations that loops X and Y run. The overlaps will be
2287 constructed as evolutions in dimension DIM. */
2290 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
2291 tree *overlaps_a, tree *overlaps_b,
2292 tree *last_conflicts, int dim)
2294 if (((step_a > 0 && step_b > 0)
2295 || (step_a < 0 && step_b < 0)))
2297 int step_overlaps_a, step_overlaps_b;
2298 int gcd_steps_a_b, last_conflict, tau2;
2300 gcd_steps_a_b = gcd (step_a, step_b);
2301 step_overlaps_a = step_b / gcd_steps_a_b;
2302 step_overlaps_b = step_a / gcd_steps_a_b;
2304 tau2 = FLOOR_DIV (niter, step_overlaps_a);
2305 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2306 last_conflict = tau2;
2308 *overlaps_a = build_polynomial_chrec
2309 (dim, integer_zero_node,
2310 build_int_cst (NULL_TREE, step_overlaps_a));
2311 *overlaps_b = build_polynomial_chrec
2312 (dim, integer_zero_node,
2313 build_int_cst (NULL_TREE, step_overlaps_b));
2314 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2319 *overlaps_a = integer_zero_node;
2320 *overlaps_b = integer_zero_node;
2321 *last_conflicts = integer_zero_node;
2326 /* Solves the special case of a Diophantine equation where CHREC_A is
2327 an affine bivariate function, and CHREC_B is an affine univariate
2328 function. For example,
2330 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2332 has the following overlapping functions:
2334 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2335 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2336 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2338 FORNOW: This is a specialized implementation for a case occurring in
2339 a common benchmark. Implement the general algorithm. */
2342 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2343 tree *overlaps_a, tree *overlaps_b,
2344 tree *last_conflicts)
2346 bool xz_p, yz_p, xyz_p;
2347 int step_x, step_y, step_z;
2348 int niter_x, niter_y, niter_z, niter;
2349 tree numiter_x, numiter_y, numiter_z;
2350 tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
2351 tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
2352 tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
2354 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2355 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2356 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2358 numiter_x = number_of_iterations_in_loop
2359 (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]);
2360 numiter_y = number_of_iterations_in_loop
2361 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2362 numiter_z = number_of_iterations_in_loop
2363 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2365 if (TREE_CODE (numiter_x) != INTEGER_CST)
2366 numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]
2367 ->estimated_nb_iterations;
2368 if (TREE_CODE (numiter_y) != INTEGER_CST)
2369 numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2370 ->estimated_nb_iterations;
2371 if (TREE_CODE (numiter_z) != INTEGER_CST)
2372 numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2373 ->estimated_nb_iterations;
2375 if (chrec_contains_undetermined (numiter_x)
2376 || chrec_contains_undetermined (numiter_y)
2377 || chrec_contains_undetermined (numiter_z)
2378 || TREE_CODE (numiter_x) != INTEGER_CST
2379 || TREE_CODE (numiter_y) != INTEGER_CST
2380 || TREE_CODE (numiter_z) != INTEGER_CST)
2382 *overlaps_a = chrec_dont_know;
2383 *overlaps_b = chrec_dont_know;
2384 *last_conflicts = chrec_dont_know;
2388 niter_x = int_cst_value (numiter_x);
2389 niter_y = int_cst_value (numiter_y);
2390 niter_z = int_cst_value (numiter_z);
2392 niter = MIN (niter_x, niter_z);
2393 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2396 &last_conflicts_xz, 1);
2397 niter = MIN (niter_y, niter_z);
2398 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2401 &last_conflicts_yz, 2);
2402 niter = MIN (niter_x, niter_z);
2403 niter = MIN (niter_y, niter);
2404 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2407 &last_conflicts_xyz, 3);
2409 xz_p = !integer_zerop (last_conflicts_xz);
2410 yz_p = !integer_zerop (last_conflicts_yz);
2411 xyz_p = !integer_zerop (last_conflicts_xyz);
2413 if (xz_p || yz_p || xyz_p)
2415 *overlaps_a = make_tree_vec (2);
2416 TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
2417 TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
2418 *overlaps_b = integer_zero_node;
2421 TREE_VEC_ELT (*overlaps_a, 0) =
2422 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
2425 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
2426 *last_conflicts = last_conflicts_xz;
2430 TREE_VEC_ELT (*overlaps_a, 1) =
2431 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
2434 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
2435 *last_conflicts = last_conflicts_yz;
2439 TREE_VEC_ELT (*overlaps_a, 0) =
2440 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
2442 TREE_VEC_ELT (*overlaps_a, 1) =
2443 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
2446 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
2447 *last_conflicts = last_conflicts_xyz;
2452 *overlaps_a = integer_zero_node;
2453 *overlaps_b = integer_zero_node;
2454 *last_conflicts = integer_zero_node;
2458 /* Determines the overlapping elements due to accesses CHREC_A and
2459 CHREC_B, that are affine functions. This is a part of the
2460 subscript analyzer. */
2463 analyze_subscript_affine_affine (tree chrec_a,
2467 tree *last_conflicts)
2469 unsigned nb_vars_a, nb_vars_b, dim;
2470 int init_a, init_b, gamma, gcd_alpha_beta;
2472 lambda_matrix A, U, S;
2474 if (dump_file && (dump_flags & TDF_DETAILS))
2475 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2477 /* For determining the initial intersection, we have to solve a
2478 Diophantine equation. This is the most time consuming part.
2480 For answering to the question: "Is there a dependence?" we have
2481 to prove that there exists a solution to the Diophantine
2482 equation, and that the solution is in the iteration domain,
2483 i.e. the solution is positive or zero, and that the solution
2484 happens before the upper bound loop.nb_iterations. Otherwise
2485 there is no dependence. This function outputs a description of
2486 the iterations that hold the intersections. */
2489 nb_vars_a = nb_vars_in_chrec (chrec_a);
2490 nb_vars_b = nb_vars_in_chrec (chrec_b);
2492 dim = nb_vars_a + nb_vars_b;
2493 U = lambda_matrix_new (dim, dim);
2494 A = lambda_matrix_new (dim, 1);
2495 S = lambda_matrix_new (dim, 1);
2497 init_a = initialize_matrix_A (A, chrec_a, 0, 1);
2498 init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
2499 gamma = init_b - init_a;
2501 /* Don't do all the hard work of solving the Diophantine equation
2502 when we already know the solution: for example,
2505 | gamma = 3 - 3 = 0.
2506 Then the first overlap occurs during the first iterations:
2507 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2511 if (nb_vars_a == 1 && nb_vars_b == 1)
2514 int niter, niter_a, niter_b;
2515 tree numiter_a, numiter_b;
2517 numiter_a = number_of_iterations_in_loop
2518 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2519 numiter_b = number_of_iterations_in_loop
2520 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2522 if (TREE_CODE (numiter_a) != INTEGER_CST)
2523 numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2524 ->estimated_nb_iterations;
2525 if (TREE_CODE (numiter_b) != INTEGER_CST)
2526 numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2527 ->estimated_nb_iterations;
2528 if (chrec_contains_undetermined (numiter_a)
2529 || chrec_contains_undetermined (numiter_b)
2530 || TREE_CODE (numiter_a) != INTEGER_CST
2531 || TREE_CODE (numiter_b) != INTEGER_CST)
2533 *overlaps_a = chrec_dont_know;
2534 *overlaps_b = chrec_dont_know;
2535 *last_conflicts = chrec_dont_know;
2539 niter_a = int_cst_value (numiter_a);
2540 niter_b = int_cst_value (numiter_b);
2541 niter = MIN (niter_a, niter_b);
2543 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2544 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2546 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2547 overlaps_a, overlaps_b,
2551 else if (nb_vars_a == 2 && nb_vars_b == 1)
2552 compute_overlap_steps_for_affine_1_2
2553 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2555 else if (nb_vars_a == 1 && nb_vars_b == 2)
2556 compute_overlap_steps_for_affine_1_2
2557 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2561 *overlaps_a = chrec_dont_know;
2562 *overlaps_b = chrec_dont_know;
2563 *last_conflicts = chrec_dont_know;
2569 lambda_matrix_right_hermite (A, dim, 1, S, U);
2574 lambda_matrix_row_negate (U, dim, 0);
2576 gcd_alpha_beta = S[0][0];
2578 /* The classic "gcd-test". */
2579 if (!int_divides_p (gcd_alpha_beta, gamma))
2581 /* The "gcd-test" has determined that there is no integer
2582 solution, i.e. there is no dependence. */
2583 *overlaps_a = chrec_known;
2584 *overlaps_b = chrec_known;
2585 *last_conflicts = integer_zero_node;
2588 /* Both access functions are univariate. This includes SIV and MIV cases. */
2589 else if (nb_vars_a == 1 && nb_vars_b == 1)
2591 /* Both functions should have the same evolution sign. */
2592 if (((A[0][0] > 0 && -A[1][0] > 0)
2593 || (A[0][0] < 0 && -A[1][0] < 0)))
2595 /* The solutions are given by:
2597 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2600 For a given integer t. Using the following variables,
2602 | i0 = u11 * gamma / gcd_alpha_beta
2603 | j0 = u12 * gamma / gcd_alpha_beta
2610 | y0 = j0 + j1 * t. */
2614 /* X0 and Y0 are the first iterations for which there is a
2615 dependence. X0, Y0 are two solutions of the Diophantine
2616 equation: chrec_a (X0) = chrec_b (Y0). */
2618 int niter, niter_a, niter_b;
2619 tree numiter_a, numiter_b;
2621 numiter_a = number_of_iterations_in_loop
2622 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2623 numiter_b = number_of_iterations_in_loop
2624 (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2626 if (TREE_CODE (numiter_a) != INTEGER_CST)
2627 numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2628 ->estimated_nb_iterations;
2629 if (TREE_CODE (numiter_b) != INTEGER_CST)
2630 numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2631 ->estimated_nb_iterations;
2632 if (chrec_contains_undetermined (numiter_a)
2633 || chrec_contains_undetermined (numiter_b)
2634 || TREE_CODE (numiter_a) != INTEGER_CST
2635 || TREE_CODE (numiter_b) != INTEGER_CST)
2637 *overlaps_a = chrec_dont_know;
2638 *overlaps_b = chrec_dont_know;
2639 *last_conflicts = chrec_dont_know;
2643 niter_a = int_cst_value (numiter_a);
2644 niter_b = int_cst_value (numiter_b);
2645 niter = MIN (niter_a, niter_b);
2647 i0 = U[0][0] * gamma / gcd_alpha_beta;
2648 j0 = U[0][1] * gamma / gcd_alpha_beta;
2652 if ((i1 == 0 && i0 < 0)
2653 || (j1 == 0 && j0 < 0))
2655 /* There is no solution.
2656 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2657 falls in here, but for the moment we don't look at the
2658 upper bound of the iteration domain. */
2659 *overlaps_a = chrec_known;
2660 *overlaps_b = chrec_known;
2661 *last_conflicts = integer_zero_node;
2668 tau1 = CEIL (-i0, i1);
2669 tau2 = FLOOR_DIV (niter - i0, i1);
2673 int last_conflict, min_multiple;
2674 tau1 = MAX (tau1, CEIL (-j0, j1));
2675 tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
2677 x0 = i1 * tau1 + i0;
2678 y0 = j1 * tau1 + j0;
2680 /* At this point (x0, y0) is one of the
2681 solutions to the Diophantine equation. The
2682 next step has to compute the smallest
2683 positive solution: the first conflicts. */
2684 min_multiple = MIN (x0 / i1, y0 / j1);
2685 x0 -= i1 * min_multiple;
2686 y0 -= j1 * min_multiple;
2688 tau1 = (x0 - i0)/i1;
2689 last_conflict = tau2 - tau1;
2691 *overlaps_a = build_polynomial_chrec
2693 build_int_cst (NULL_TREE, x0),
2694 build_int_cst (NULL_TREE, i1));
2695 *overlaps_b = build_polynomial_chrec
2697 build_int_cst (NULL_TREE, y0),
2698 build_int_cst (NULL_TREE, j1));
2699 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2703 /* FIXME: For the moment, the upper bound of the
2704 iteration domain for j is not checked. */
2705 *overlaps_a = chrec_dont_know;
2706 *overlaps_b = chrec_dont_know;
2707 *last_conflicts = chrec_dont_know;
2713 /* FIXME: For the moment, the upper bound of the
2714 iteration domain for i is not checked. */
2715 *overlaps_a = chrec_dont_know;
2716 *overlaps_b = chrec_dont_know;
2717 *last_conflicts = chrec_dont_know;
2723 *overlaps_a = chrec_dont_know;
2724 *overlaps_b = chrec_dont_know;
2725 *last_conflicts = chrec_dont_know;
2731 *overlaps_a = chrec_dont_know;
2732 *overlaps_b = chrec_dont_know;
2733 *last_conflicts = chrec_dont_know;
2737 if (dump_file && (dump_flags & TDF_DETAILS))
2739 fprintf (dump_file, " (overlaps_a = ");
2740 print_generic_expr (dump_file, *overlaps_a, 0);
2741 fprintf (dump_file, ")\n (overlaps_b = ");
2742 print_generic_expr (dump_file, *overlaps_b, 0);
2743 fprintf (dump_file, ")\n");
2746 if (dump_file && (dump_flags & TDF_DETAILS))
2747 fprintf (dump_file, ")\n");
2750 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2751 *OVERLAPS_B are initialized to the functions that describe the
2752 relation between the elements accessed twice by CHREC_A and
2753 CHREC_B. For k >= 0, the following property is verified:
2755 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2758 analyze_siv_subscript (tree chrec_a,
2762 tree *last_conflicts)
2764 if (dump_file && (dump_flags & TDF_DETAILS))
2765 fprintf (dump_file, "(analyze_siv_subscript \n");
2767 if (evolution_function_is_constant_p (chrec_a)
2768 && evolution_function_is_affine_p (chrec_b))
2769 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
2770 overlaps_a, overlaps_b, last_conflicts);
2772 else if (evolution_function_is_affine_p (chrec_a)
2773 && evolution_function_is_constant_p (chrec_b))
2774 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2775 overlaps_b, overlaps_a, last_conflicts);
2777 else if (evolution_function_is_affine_p (chrec_a)
2778 && evolution_function_is_affine_p (chrec_b))
2779 analyze_subscript_affine_affine (chrec_a, chrec_b,
2780 overlaps_a, overlaps_b, last_conflicts);
2783 *overlaps_a = chrec_dont_know;
2784 *overlaps_b = chrec_dont_know;
2785 *last_conflicts = chrec_dont_know;
2788 if (dump_file && (dump_flags & TDF_DETAILS))
2789 fprintf (dump_file, ")\n");
2792 /* Return true when the evolution steps of an affine CHREC divide the
2796 chrec_steps_divide_constant_p (tree chrec,
2799 switch (TREE_CODE (chrec))
2801 case POLYNOMIAL_CHREC:
2802 return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst)
2803 && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
2806 /* On the initial condition, return true. */
2811 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
2812 *OVERLAPS_B are initialized to the functions that describe the
2813 relation between the elements accessed twice by CHREC_A and
2814 CHREC_B. For k >= 0, the following property is verified:
2816 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2819 analyze_miv_subscript (tree chrec_a,
2823 tree *last_conflicts)
2825 /* FIXME: This is a MIV subscript, not yet handled.
2826 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2829 In the SIV test we had to solve a Diophantine equation with two
2830 variables. In the MIV case we have to solve a Diophantine
2831 equation with 2*n variables (if the subscript uses n IVs).
2835 if (dump_file && (dump_flags & TDF_DETAILS))
2836 fprintf (dump_file, "(analyze_miv_subscript \n");
2838 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2840 if (chrec_zerop (difference))
2842 /* Access functions are the same: all the elements are accessed
2843 in the same order. */
2844 *overlaps_a = integer_zero_node;
2845 *overlaps_b = integer_zero_node;
2846 *last_conflicts = number_of_iterations_in_loop
2847 (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2850 else if (evolution_function_is_constant_p (difference)
2851 /* For the moment, the following is verified:
2852 evolution_function_is_affine_multivariate_p (chrec_a) */
2853 && !chrec_steps_divide_constant_p (chrec_a, difference))
2855 /* testsuite/.../ssa-chrec-33.c
2856 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2858 The difference is 1, and the evolution steps are equal to 2,
2859 consequently there are no overlapping elements. */
2860 *overlaps_a = chrec_known;
2861 *overlaps_b = chrec_known;
2862 *last_conflicts = integer_zero_node;
2865 else if (evolution_function_is_affine_multivariate_p (chrec_a)
2866 && evolution_function_is_affine_multivariate_p (chrec_b))
2868 /* testsuite/.../ssa-chrec-35.c
2869 {0, +, 1}_2 vs. {0, +, 1}_3
2870 the overlapping elements are respectively located at iterations:
2871 {0, +, 1}_x and {0, +, 1}_x,
2872 in other words, we have the equality:
2873 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2876 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2877 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2879 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2880 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2882 analyze_subscript_affine_affine (chrec_a, chrec_b,
2883 overlaps_a, overlaps_b, last_conflicts);
2888 /* When the analysis is too difficult, answer "don't know". */
2889 *overlaps_a = chrec_dont_know;
2890 *overlaps_b = chrec_dont_know;
2891 *last_conflicts = chrec_dont_know;
2894 if (dump_file && (dump_flags & TDF_DETAILS))
2895 fprintf (dump_file, ")\n");
2898 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
2899 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
2900 two functions that describe the iterations that contain conflicting
2903 Remark: For an integer k >= 0, the following equality is true:
2905 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2909 analyze_overlapping_iterations (tree chrec_a,
2911 tree *overlap_iterations_a,
2912 tree *overlap_iterations_b,
2913 tree *last_conflicts)
2915 if (dump_file && (dump_flags & TDF_DETAILS))
2917 fprintf (dump_file, "(analyze_overlapping_iterations \n");
2918 fprintf (dump_file, " (chrec_a = ");
2919 print_generic_expr (dump_file, chrec_a, 0);
2920 fprintf (dump_file, ")\n chrec_b = ");
2921 print_generic_expr (dump_file, chrec_b, 0);
2922 fprintf (dump_file, ")\n");
2925 if (chrec_a == NULL_TREE
2926 || chrec_b == NULL_TREE
2927 || chrec_contains_undetermined (chrec_a)
2928 || chrec_contains_undetermined (chrec_b)
2929 || chrec_contains_symbols (chrec_a)
2930 || chrec_contains_symbols (chrec_b))
2932 *overlap_iterations_a = chrec_dont_know;
2933 *overlap_iterations_b = chrec_dont_know;
2936 else if (ziv_subscript_p (chrec_a, chrec_b))
2937 analyze_ziv_subscript (chrec_a, chrec_b,
2938 overlap_iterations_a, overlap_iterations_b,
2941 else if (siv_subscript_p (chrec_a, chrec_b))
2942 analyze_siv_subscript (chrec_a, chrec_b,
2943 overlap_iterations_a, overlap_iterations_b,
2947 analyze_miv_subscript (chrec_a, chrec_b,
2948 overlap_iterations_a, overlap_iterations_b,
2951 if (dump_file && (dump_flags & TDF_DETAILS))
2953 fprintf (dump_file, " (overlap_iterations_a = ");
2954 print_generic_expr (dump_file, *overlap_iterations_a, 0);
2955 fprintf (dump_file, ")\n (overlap_iterations_b = ");
2956 print_generic_expr (dump_file, *overlap_iterations_b, 0);
2957 fprintf (dump_file, ")\n");
2963 /* This section contains the affine functions dependences detector. */
2965 /* Computes the conflicting iterations, and initialize DDR. */
2968 subscript_dependence_tester (struct data_dependence_relation *ddr)
2971 struct data_reference *dra = DDR_A (ddr);
2972 struct data_reference *drb = DDR_B (ddr);
2973 tree last_conflicts;
2975 if (dump_file && (dump_flags & TDF_DETAILS))
2976 fprintf (dump_file, "(subscript_dependence_tester \n");
2978 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2980 tree overlaps_a, overlaps_b;
2981 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
2983 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
2984 DR_ACCESS_FN (drb, i),
2985 &overlaps_a, &overlaps_b,
2988 if (chrec_contains_undetermined (overlaps_a)
2989 || chrec_contains_undetermined (overlaps_b))
2991 finalize_ddr_dependent (ddr, chrec_dont_know);
2995 else if (overlaps_a == chrec_known
2996 || overlaps_b == chrec_known)
2998 finalize_ddr_dependent (ddr, chrec_known);
3004 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3005 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3006 SUB_LAST_CONFLICT (subscript) = last_conflicts;
3010 if (dump_file && (dump_flags & TDF_DETAILS))
3011 fprintf (dump_file, ")\n");
3014 /* Compute the classic per loop distance vector.
3016 DDR is the data dependence relation to build a vector from.
3017 NB_LOOPS is the total number of loops we are considering.
3018 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
3020 Return FALSE if the dependence relation is outside of the loop nest
3021 starting at FIRST_LOOP_DEPTH.
3022 Return TRUE otherwise. */
3025 build_classic_dist_vector (struct data_dependence_relation *ddr,
3026 int nb_loops, int first_loop_depth)
3029 lambda_vector dist_v, init_v;
3031 dist_v = lambda_vector_new (nb_loops);
3032 init_v = lambda_vector_new (nb_loops);
3033 lambda_vector_clear (dist_v, nb_loops);
3034 lambda_vector_clear (init_v, nb_loops);
3036 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3039 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3041 tree access_fn_a, access_fn_b;
3042 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3044 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3046 non_affine_dependence_relation (ddr);
3050 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
3051 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
3053 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3054 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3056 int dist, loop_nb, loop_depth;
3057 int loop_nb_a = CHREC_VARIABLE (access_fn_a);
3058 int loop_nb_b = CHREC_VARIABLE (access_fn_b);
3059 struct loop *loop_a = current_loops->parray[loop_nb_a];
3060 struct loop *loop_b = current_loops->parray[loop_nb_b];
3062 /* If the loop for either variable is at a lower depth than
3063 the first_loop's depth, then we can't possibly have a
3064 dependency at this level of the loop. */
3066 if (loop_a->depth < first_loop_depth
3067 || loop_b->depth < first_loop_depth)
3070 if (loop_nb_a != loop_nb_b
3071 && !flow_loop_nested_p (loop_a, loop_b)
3072 && !flow_loop_nested_p (loop_b, loop_a))
3074 /* Example: when there are two consecutive loops,
3083 the dependence relation cannot be captured by the
3084 distance abstraction. */
3085 non_affine_dependence_relation (ddr);
3089 /* The dependence is carried by the outermost loop. Example:
3096 In this case, the dependence is carried by loop_1. */
3097 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
3098 loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
3100 /* If the loop number is still greater than the number of
3101 loops we've been asked to analyze, or negative,
3102 something is borked. */
3103 gcc_assert (loop_depth >= 0);
3104 gcc_assert (loop_depth < nb_loops);
3105 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3107 non_affine_dependence_relation (ddr);
3111 dist = int_cst_value (SUB_DISTANCE (subscript));
3113 /* This is the subscript coupling test.
3118 There is no dependence. */
3119 if (init_v[loop_depth] != 0
3120 && dist_v[loop_depth] != dist)
3122 finalize_ddr_dependent (ddr, chrec_known);
3126 dist_v[loop_depth] = dist;
3127 init_v[loop_depth] = 1;
3131 /* There is a distance of 1 on all the outer loops:
3133 Example: there is a dependence of distance 1 on loop_1 for the array A.
3139 struct loop *lca, *loop_a, *loop_b;
3140 struct data_reference *a = DDR_A (ddr);
3141 struct data_reference *b = DDR_B (ddr);
3143 loop_a = loop_containing_stmt (DR_STMT (a));
3144 loop_b = loop_containing_stmt (DR_STMT (b));
3146 /* Get the common ancestor loop. */
3147 lca = find_common_loop (loop_a, loop_b);
3149 lca_depth = lca->depth;
3150 lca_depth -= first_loop_depth;
3151 gcc_assert (lca_depth >= 0);
3152 gcc_assert (lca_depth < nb_loops);
3154 /* For each outer loop where init_v is not set, the accesses are
3155 in dependence of distance 1 in the loop. */
3158 && init_v[lca_depth] == 0)
3159 dist_v[lca_depth] = 1;
3165 lca_depth = lca->depth - first_loop_depth;
3166 while (lca->depth != 0)
3168 /* If we're considering just a sub-nest, then don't record
3169 any information on the outer loops. */
3173 gcc_assert (lca_depth < nb_loops);
3175 if (init_v[lca_depth] == 0)
3176 dist_v[lca_depth] = 1;
3178 lca_depth = lca->depth - first_loop_depth;
3184 DDR_DIST_VECT (ddr) = dist_v;
3185 DDR_SIZE_VECT (ddr) = nb_loops;
3189 /* Compute the classic per loop direction vector.
3191 DDR is the data dependence relation to build a vector from.
3192 NB_LOOPS is the total number of loops we are considering.
3193 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
3195 Return FALSE if the dependence relation is outside of the loop nest
3196 at FIRST_LOOP_DEPTH.
3197 Return TRUE otherwise. */
3200 build_classic_dir_vector (struct data_dependence_relation *ddr,
3201 int nb_loops, int first_loop_depth)
3204 lambda_vector dir_v, init_v;
3206 dir_v = lambda_vector_new (nb_loops);
3207 init_v = lambda_vector_new (nb_loops);
3208 lambda_vector_clear (dir_v, nb_loops);
3209 lambda_vector_clear (init_v, nb_loops);
3211 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3214 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3216 tree access_fn_a, access_fn_b;
3217 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3219 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3221 non_affine_dependence_relation (ddr);
3225 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
3226 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
3227 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3228 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3230 int dist, loop_nb, loop_depth;
3231 enum data_dependence_direction dir = dir_star;
3232 int loop_nb_a = CHREC_VARIABLE (access_fn_a);
3233 int loop_nb_b = CHREC_VARIABLE (access_fn_b);
3234 struct loop *loop_a = current_loops->parray[loop_nb_a];
3235 struct loop *loop_b = current_loops->parray[loop_nb_b];
3237 /* If the loop for either variable is at a lower depth than
3238 the first_loop's depth, then we can't possibly have a
3239 dependency at this level of the loop. */
3241 if (loop_a->depth < first_loop_depth
3242 || loop_b->depth < first_loop_depth)
3245 if (loop_nb_a != loop_nb_b
3246 && !flow_loop_nested_p (loop_a, loop_b)
3247 && !flow_loop_nested_p (loop_b, loop_a))
3249 /* Example: when there are two consecutive loops,
3258 the dependence relation cannot be captured by the
3259 distance abstraction. */
3260 non_affine_dependence_relation (ddr);
3264 /* The dependence is carried by the outermost loop. Example:
3271 In this case, the dependence is carried by loop_1. */
3272 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
3273 loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
3275 /* If the loop number is still greater than the number of
3276 loops we've been asked to analyze, or negative,
3277 something is borked. */
3278 gcc_assert (loop_depth >= 0);
3279 gcc_assert (loop_depth < nb_loops);
3281 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3283 non_affine_dependence_relation (ddr);
3287 dist = int_cst_value (SUB_DISTANCE (subscript));
3296 /* This is the subscript coupling test.
3301 There is no dependence. */
3302 if (init_v[loop_depth] != 0
3304 && (enum data_dependence_direction) dir_v[loop_depth] != dir
3305 && (enum data_dependence_direction) dir_v[loop_depth] != dir_star)
3307 finalize_ddr_dependent (ddr, chrec_known);
3311 dir_v[loop_depth] = dir;
3312 init_v[loop_depth] = 1;
3316 /* There is a distance of 1 on all the outer loops:
3318 Example: there is a dependence of distance 1 on loop_1 for the array A.
3324 struct loop *lca, *loop_a, *loop_b;
3325 struct data_reference *a = DDR_A (ddr);
3326 struct data_reference *b = DDR_B (ddr);
3328 loop_a = loop_containing_stmt (DR_STMT (a));
3329 loop_b = loop_containing_stmt (DR_STMT (b));
3331 /* Get the common ancestor loop. */
3332 lca = find_common_loop (loop_a, loop_b);
3333 lca_depth = lca->depth - first_loop_depth;
3335 gcc_assert (lca_depth >= 0);
3336 gcc_assert (lca_depth < nb_loops);
3338 /* For each outer loop where init_v is not set, the accesses are
3339 in dependence of distance 1 in the loop. */
3342 && init_v[lca_depth] == 0)
3343 dir_v[lca_depth] = dir_positive;
3348 lca_depth = lca->depth - first_loop_depth;
3349 while (lca->depth != 0)
3351 /* If we're considering just a sub-nest, then don't record
3352 any information on the outer loops. */
3356 gcc_assert (lca_depth < nb_loops);
3358 if (init_v[lca_depth] == 0)
3359 dir_v[lca_depth] = dir_positive;
3361 lca_depth = lca->depth - first_loop_depth;
3367 DDR_DIR_VECT (ddr) = dir_v;
3368 DDR_SIZE_VECT (ddr) = nb_loops;
3372 /* Returns true when all the access functions of A are affine or
3376 access_functions_are_affine_or_constant_p (struct data_reference *a)
3379 VEC(tree,heap) **fns = DR_ACCESS_FNS_ADDR (a);
3382 for (i = 0; VEC_iterate (tree, *fns, i, t); i++)
3383 if (!evolution_function_is_constant_p (t)
3384 && !evolution_function_is_affine_multivariate_p (t))
3390 /* This computes the affine dependence relation between A and B.
3391 CHREC_KNOWN is used for representing the independence between two
3392 accesses, while CHREC_DONT_KNOW is used for representing the unknown
3395 Note that it is possible to stop the computation of the dependence
3396 relation the first time we detect a CHREC_KNOWN element for a given
3400 compute_affine_dependence (struct data_dependence_relation *ddr)
3402 struct data_reference *dra = DDR_A (ddr);
3403 struct data_reference *drb = DDR_B (ddr);
3405 if (dump_file && (dump_flags & TDF_DETAILS))
3407 fprintf (dump_file, "(compute_affine_dependence\n");
3408 fprintf (dump_file, " (stmt_a = \n");
3409 print_generic_expr (dump_file, DR_STMT (dra), 0);
3410 fprintf (dump_file, ")\n (stmt_b = \n");
3411 print_generic_expr (dump_file, DR_STMT (drb), 0);
3412 fprintf (dump_file, ")\n");
3415 /* Analyze only when the dependence relation is not yet known. */
3416 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3418 if (access_functions_are_affine_or_constant_p (dra)
3419 && access_functions_are_affine_or_constant_p (drb))
3420 subscript_dependence_tester (ddr);
3422 /* As a last case, if the dependence cannot be determined, or if
3423 the dependence is considered too difficult to determine, answer
3426 finalize_ddr_dependent (ddr, chrec_dont_know);
3429 if (dump_file && (dump_flags & TDF_DETAILS))
3430 fprintf (dump_file, ")\n");
3433 /* This computes the dependence relation for the same data
3434 reference into DDR. */
3437 compute_self_dependence (struct data_dependence_relation *ddr)
3441 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3443 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3445 /* The accessed index overlaps for each iteration. */
3446 SUB_CONFLICTS_IN_A (subscript) = integer_zero_node;
3447 SUB_CONFLICTS_IN_B (subscript) = integer_zero_node;
3448 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3453 typedef struct data_dependence_relation *ddr_p;
3455 DEF_VEC_ALLOC_P(ddr_p,heap);
3457 /* Compute a subset of the data dependence relation graph. Don't
3458 compute read-read and self relations if
3459 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is FALSE, and avoid the computation
3460 of the opposite relation, i.e. when AB has been computed, don't compute BA.
3461 DATAREFS contains a list of data references, and the result is set
3462 in DEPENDENCE_RELATIONS. */
3465 compute_all_dependences (varray_type datarefs,
3466 bool compute_self_and_read_read_dependences,
3467 VEC(ddr_p,heap) **dependence_relations)
3469 unsigned int i, j, N;
3471 N = VARRAY_ACTIVE_SIZE (datarefs);
3473 /* Note that we specifically skip i == j because it's a self dependence, and
3474 use compute_self_dependence below. */
3476 for (i = 0; i < N; i++)
3477 for (j = i + 1; j < N; j++)
3479 struct data_reference *a, *b;
3480 struct data_dependence_relation *ddr;
3482 a = VARRAY_GENERIC_PTR (datarefs, i);
3483 b = VARRAY_GENERIC_PTR (datarefs, j);
3484 if (DR_IS_READ (a) && DR_IS_READ (b)
3485 && !compute_self_and_read_read_dependences)
3487 ddr = initialize_data_dependence_relation (a, b);
3489 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3490 compute_affine_dependence (ddr);
3491 compute_subscript_distance (ddr);
3493 if (!compute_self_and_read_read_dependences)
3496 /* Compute self dependence relation of each dataref to itself. */
3498 for (i = 0; i < N; i++)
3500 struct data_reference *a, *b;
3501 struct data_dependence_relation *ddr;
3503 a = VARRAY_GENERIC_PTR (datarefs, i);
3504 b = VARRAY_GENERIC_PTR (datarefs, i);
3505 ddr = initialize_data_dependence_relation (a, b);
3507 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3508 compute_self_dependence (ddr);
3509 compute_subscript_distance (ddr);
3513 /* Search the data references in LOOP, and record the information into
3514 DATAREFS. Returns chrec_dont_know when failing to analyze a
3515 difficult case, returns NULL_TREE otherwise.
3517 TODO: This function should be made smarter so that it can handle address
3518 arithmetic as if they were array accesses, etc. */
3521 find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
3523 basic_block bb, *bbs;
3525 block_stmt_iterator bsi;
3526 struct data_reference *dr;
3528 bbs = get_loop_body (loop);
3530 for (i = 0; i < loop->num_nodes; i++)
3534 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3536 tree stmt = bsi_stmt (bsi);
3538 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
3539 Calls have side-effects, except those to const or pure
3541 if ((TREE_CODE (stmt) == CALL_EXPR
3542 && !(call_expr_flags (stmt) & (ECF_CONST | ECF_PURE)))
3543 || (TREE_CODE (stmt) == ASM_EXPR
3544 && ASM_VOLATILE_P (stmt)))
3545 goto insert_dont_know_node;
3547 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3550 switch (TREE_CODE (stmt))
3554 bool one_inserted = false;
3555 tree opnd0 = TREE_OPERAND (stmt, 0);
3556 tree opnd1 = TREE_OPERAND (stmt, 1);
3558 if (TREE_CODE (opnd0) == ARRAY_REF
3559 || TREE_CODE (opnd0) == INDIRECT_REF)
3561 dr = create_data_ref (opnd0, stmt, false);
3564 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3565 one_inserted = true;
3569 if (TREE_CODE (opnd1) == ARRAY_REF
3570 || TREE_CODE (opnd1) == INDIRECT_REF)
3572 dr = create_data_ref (opnd1, stmt, true);
3575 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3576 one_inserted = true;
3581 goto insert_dont_know_node;
3589 bool one_inserted = false;
3591 for (args = TREE_OPERAND (stmt, 1); args;
3592 args = TREE_CHAIN (args))
3593 if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
3594 || TREE_CODE (TREE_VALUE (args)) == INDIRECT_REF)
3596 dr = create_data_ref (TREE_VALUE (args), stmt, true);
3599 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3600 one_inserted = true;
3605 goto insert_dont_know_node;
3612 struct data_reference *res;
3614 insert_dont_know_node:;
3615 res = xmalloc (sizeof (struct data_reference));
3616 DR_STMT (res) = NULL_TREE;
3617 DR_REF (res) = NULL_TREE;
3618 DR_BASE_OBJECT (res) = NULL;
3619 DR_TYPE (res) = ARRAY_REF_TYPE;
3620 DR_SET_ACCESS_FNS (res, NULL);
3621 DR_BASE_OBJECT (res) = NULL;
3622 DR_IS_READ (res) = false;
3623 DR_BASE_ADDRESS (res) = NULL_TREE;
3624 DR_OFFSET (res) = NULL_TREE;
3625 DR_INIT (res) = NULL_TREE;
3626 DR_STEP (res) = NULL_TREE;
3627 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
3628 DR_MEMTAG (res) = NULL_TREE;
3629 DR_PTR_INFO (res) = NULL;
3630 VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
3633 return chrec_dont_know;
3637 /* When there are no defs in the loop, the loop is parallel. */
3638 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
3639 loop->parallel_p = false;
3650 /* This section contains all the entry points. */
3652 /* Given a loop nest LOOP, the following vectors are returned:
3653 *DATAREFS is initialized to all the array elements contained in this loop,
3654 *DEPENDENCE_RELATIONS contains the relations between the data references.
3655 Compute read-read and self relations if
3656 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
3659 compute_data_dependences_for_loop (struct loop *loop,
3660 bool compute_self_and_read_read_dependences,
3661 varray_type *datarefs,
3662 varray_type *dependence_relations)
3664 unsigned int i, nb_loops;
3665 VEC(ddr_p,heap) *allrelations;
3666 struct data_dependence_relation *ddr;
3667 struct loop *loop_nest = loop;
3669 while (loop_nest && loop_nest->outer && loop_nest->outer->outer)
3670 loop_nest = loop_nest->outer;
3672 nb_loops = loop_nest->level;
3674 /* If one of the data references is not computable, give up without
3675 spending time to compute other dependences. */
3676 if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
3678 struct data_dependence_relation *ddr;
3680 /* Insert a single relation into dependence_relations:
3682 ddr = initialize_data_dependence_relation (NULL, NULL);
3683 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
3684 build_classic_dist_vector (ddr, nb_loops, loop->depth);
3685 build_classic_dir_vector (ddr, nb_loops, loop->depth);
3689 allrelations = NULL;
3690 compute_all_dependences (*datarefs, compute_self_and_read_read_dependences,
3693 for (i = 0; VEC_iterate (ddr_p, allrelations, i, ddr); i++)
3695 if (build_classic_dist_vector (ddr, nb_loops, loop_nest->depth))
3697 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
3698 build_classic_dir_vector (ddr, nb_loops, loop_nest->depth);
3703 /* Entry point (for testing only). Analyze all the data references
3704 and the dependence relations.
3706 The data references are computed first.
3708 A relation on these nodes is represented by a complete graph. Some
3709 of the relations could be of no interest, thus the relations can be
3712 In the following function we compute all the relations. This is
3713 just a first implementation that is here for:
3714 - for showing how to ask for the dependence relations,
3715 - for the debugging the whole dependence graph,
3716 - for the dejagnu testcases and maintenance.
3718 It is possible to ask only for a part of the graph, avoiding to
3719 compute the whole dependence graph. The computed dependences are
3720 stored in a knowledge base (KB) such that later queries don't
3721 recompute the same information. The implementation of this KB is
3722 transparent to the optimizer, and thus the KB can be changed with a
3723 more efficient implementation, or the KB could be disabled. */
3726 analyze_all_data_dependences (struct loops *loops)
3729 varray_type datarefs;
3730 varray_type dependence_relations;
3731 int nb_data_refs = 10;
3733 VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
3734 VARRAY_GENERIC_PTR_INIT (dependence_relations,
3735 nb_data_refs * nb_data_refs,
3736 "dependence_relations");
3738 /* Compute DDs on the whole function. */
3739 compute_data_dependences_for_loop (loops->parray[0], false,
3740 &datarefs, &dependence_relations);
3744 dump_data_dependence_relations (dump_file, dependence_relations);
3745 fprintf (dump_file, "\n\n");
3747 if (dump_flags & TDF_DETAILS)
3748 dump_dist_dir_vectors (dump_file, dependence_relations);
3750 if (dump_flags & TDF_STATS)
3752 unsigned nb_top_relations = 0;
3753 unsigned nb_bot_relations = 0;
3754 unsigned nb_basename_differ = 0;
3755 unsigned nb_chrec_relations = 0;
3757 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
3759 struct data_dependence_relation *ddr;
3760 ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
3762 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
3765 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
3767 struct data_reference *a = DDR_A (ddr);
3768 struct data_reference *b = DDR_B (ddr);
3771 if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
3772 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
3773 || (base_object_differ_p (a, b, &differ_p)
3775 nb_basename_differ++;
3781 nb_chrec_relations++;
3784 gather_stats_on_scev_database ();
3788 free_dependence_relations (dependence_relations);
3789 free_data_refs (datarefs);
3792 /* Free the memory used by a data dependence relation DDR. */
3795 free_dependence_relation (struct data_dependence_relation *ddr)
3800 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
3801 varray_clear (DDR_SUBSCRIPTS (ddr));
3805 /* Free the memory used by the data dependence relations from
3806 DEPENDENCE_RELATIONS. */
3809 free_dependence_relations (varray_type dependence_relations)
3812 if (dependence_relations == NULL)
3815 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
3816 free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
3817 varray_clear (dependence_relations);
3820 /* Free the memory used by the data references from DATAREFS. */
3823 free_data_refs (varray_type datarefs)
3827 if (datarefs == NULL)
3830 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
3832 struct data_reference *dr = (struct data_reference *)
3833 VARRAY_GENERIC_PTR (datarefs, i);
3836 DR_FREE_ACCESS_FNS (dr);
3840 varray_clear (datarefs);