1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
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"
96 #include "langhooks.h"
98 static struct datadep_stats
100 int num_dependence_tests;
101 int num_dependence_dependent;
102 int num_dependence_independent;
103 int num_dependence_undetermined;
105 int num_subscript_tests;
106 int num_subscript_undetermined;
107 int num_same_subscript_function;
110 int num_ziv_independent;
111 int num_ziv_dependent;
112 int num_ziv_unimplemented;
115 int num_siv_independent;
116 int num_siv_dependent;
117 int num_siv_unimplemented;
120 int num_miv_independent;
121 int num_miv_dependent;
122 int num_miv_unimplemented;
125 static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
126 struct data_reference *,
127 struct data_reference *);
128 /* Returns true iff A divides B. */
131 tree_fold_divides_p (tree a, tree b)
133 gcc_assert (TREE_CODE (a) == INTEGER_CST);
134 gcc_assert (TREE_CODE (b) == INTEGER_CST);
135 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a, 0));
138 /* Returns true iff A divides B. */
141 int_divides_p (int a, int b)
143 return ((b % a) == 0);
148 /* Dump into FILE all the data references from DATAREFS. */
151 dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
154 struct data_reference *dr;
156 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
157 dump_data_reference (file, dr);
160 /* Dump into FILE all the dependence relations from DDRS. */
163 dump_data_dependence_relations (FILE *file,
164 VEC (ddr_p, heap) *ddrs)
167 struct data_dependence_relation *ddr;
169 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
170 dump_data_dependence_relation (file, ddr);
173 /* Dump function for a DATA_REFERENCE structure. */
176 dump_data_reference (FILE *outf,
177 struct data_reference *dr)
181 fprintf (outf, "(Data Ref: \n stmt: ");
182 print_generic_stmt (outf, DR_STMT (dr), 0);
183 fprintf (outf, " ref: ");
184 print_generic_stmt (outf, DR_REF (dr), 0);
185 fprintf (outf, " base_object: ");
186 print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
188 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
190 fprintf (outf, " Access function %d: ", i);
191 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
193 fprintf (outf, ")\n");
196 /* Dumps the affine function described by FN to the file OUTF. */
199 dump_affine_function (FILE *outf, affine_fn fn)
204 print_generic_expr (outf, VEC_index (tree, fn, 0), TDF_SLIM);
205 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
207 fprintf (outf, " + ");
208 print_generic_expr (outf, coef, TDF_SLIM);
209 fprintf (outf, " * x_%u", i);
213 /* Dumps the conflict function CF to the file OUTF. */
216 dump_conflict_function (FILE *outf, conflict_function *cf)
220 if (cf->n == NO_DEPENDENCE)
221 fprintf (outf, "no dependence\n");
222 else if (cf->n == NOT_KNOWN)
223 fprintf (outf, "not known\n");
226 for (i = 0; i < cf->n; i++)
229 dump_affine_function (outf, cf->fns[i]);
230 fprintf (outf, "]\n");
235 /* Dump function for a SUBSCRIPT structure. */
238 dump_subscript (FILE *outf, struct subscript *subscript)
240 conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
242 fprintf (outf, "\n (subscript \n");
243 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
244 dump_conflict_function (outf, cf);
245 if (CF_NONTRIVIAL_P (cf))
247 tree last_iteration = SUB_LAST_CONFLICT (subscript);
248 fprintf (outf, " last_conflict: ");
249 print_generic_stmt (outf, last_iteration, 0);
252 cf = SUB_CONFLICTS_IN_B (subscript);
253 fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
254 dump_conflict_function (outf, cf);
255 if (CF_NONTRIVIAL_P (cf))
257 tree last_iteration = SUB_LAST_CONFLICT (subscript);
258 fprintf (outf, " last_conflict: ");
259 print_generic_stmt (outf, last_iteration, 0);
262 fprintf (outf, " (Subscript distance: ");
263 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
264 fprintf (outf, " )\n");
265 fprintf (outf, " )\n");
268 /* Print the classic direction vector DIRV to OUTF. */
271 print_direction_vector (FILE *outf,
277 for (eq = 0; eq < length; eq++)
279 enum data_dependence_direction dir = dirv[eq];
284 fprintf (outf, " +");
287 fprintf (outf, " -");
290 fprintf (outf, " =");
292 case dir_positive_or_equal:
293 fprintf (outf, " +=");
295 case dir_positive_or_negative:
296 fprintf (outf, " +-");
298 case dir_negative_or_equal:
299 fprintf (outf, " -=");
302 fprintf (outf, " *");
305 fprintf (outf, "indep");
309 fprintf (outf, "\n");
312 /* Print a vector of direction vectors. */
315 print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
321 for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++)
322 print_direction_vector (outf, v, length);
325 /* Print a vector of distance vectors. */
328 print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
334 for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++)
335 print_lambda_vector (outf, v, length);
341 debug_data_dependence_relation (struct data_dependence_relation *ddr)
343 dump_data_dependence_relation (stderr, ddr);
346 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
349 dump_data_dependence_relation (FILE *outf,
350 struct data_dependence_relation *ddr)
352 struct data_reference *dra, *drb;
356 fprintf (outf, "(Data Dep: \n");
357 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
358 fprintf (outf, " (don't know)\n");
360 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
361 fprintf (outf, " (no dependence)\n");
363 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
368 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
370 fprintf (outf, " access_fn_A: ");
371 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
372 fprintf (outf, " access_fn_B: ");
373 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
374 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
377 fprintf (outf, " inner loop index: %d\n", DDR_INNER_LOOP (ddr));
378 fprintf (outf, " loop nest: (");
379 for (i = 0; VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
380 fprintf (outf, "%d ", loopi->num);
381 fprintf (outf, ")\n");
383 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
385 fprintf (outf, " distance_vector: ");
386 print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
390 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
392 fprintf (outf, " direction_vector: ");
393 print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
398 fprintf (outf, ")\n");
401 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
404 dump_data_dependence_direction (FILE *file,
405 enum data_dependence_direction dir)
421 case dir_positive_or_negative:
422 fprintf (file, "+-");
425 case dir_positive_or_equal:
426 fprintf (file, "+=");
429 case dir_negative_or_equal:
430 fprintf (file, "-=");
442 /* Dumps the distance and direction vectors in FILE. DDRS contains
443 the dependence relations, and VECT_SIZE is the size of the
444 dependence vectors, or in other words the number of loops in the
448 dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
451 struct data_dependence_relation *ddr;
454 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
455 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
457 for (j = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), j, v); j++)
459 fprintf (file, "DISTANCE_V (");
460 print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
461 fprintf (file, ")\n");
464 for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++)
466 fprintf (file, "DIRECTION_V (");
467 print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
468 fprintf (file, ")\n");
472 fprintf (file, "\n\n");
475 /* Dumps the data dependence relations DDRS in FILE. */
478 dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
481 struct data_dependence_relation *ddr;
483 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
484 dump_data_dependence_relation (file, ddr);
486 fprintf (file, "\n\n");
489 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
490 will be ssizetype. */
493 split_constant_offset (tree exp, tree *var, tree *off)
495 tree type = TREE_TYPE (exp), otype;
501 otype = TREE_TYPE (exp);
503 switch (TREE_CODE (exp))
506 *var = build_int_cst (type, 0);
507 *off = fold_convert (ssizetype, exp);
512 split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0);
513 split_constant_offset (TREE_OPERAND (exp, 1), &var1, &off1);
514 *var = fold_convert (type, fold_build2 (TREE_CODE (exp), otype,
516 *off = size_binop (TREE_CODE (exp), off0, off1);
520 off1 = TREE_OPERAND (exp, 1);
521 if (TREE_CODE (off1) != INTEGER_CST)
524 split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0);
525 *var = fold_convert (type, fold_build2 (MULT_EXPR, otype,
527 *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, off1));
532 tree op, base, poffset;
533 HOST_WIDE_INT pbitsize, pbitpos;
534 enum machine_mode pmode;
535 int punsignedp, pvolatilep;
537 op = TREE_OPERAND (exp, 0);
538 if (!handled_component_p (op))
541 base = get_inner_reference (op, &pbitsize, &pbitpos, &poffset,
542 &pmode, &punsignedp, &pvolatilep, false);
544 if (pbitpos % BITS_PER_UNIT != 0)
546 base = build_fold_addr_expr (base);
547 off0 = ssize_int (pbitpos / BITS_PER_UNIT);
551 split_constant_offset (poffset, &poffset, &off1);
552 off0 = size_binop (PLUS_EXPR, off0, off1);
553 base = fold_build2 (PLUS_EXPR, TREE_TYPE (base),
555 fold_convert (TREE_TYPE (base), poffset));
558 *var = fold_convert (type, base);
567 *off = ssize_int (0);
570 /* Returns the address ADDR of an object in a canonical shape (without nop
571 casts, and with type of pointer to the object). */
574 canonicalize_base_object_address (tree addr)
580 /* The base address may be obtained by casting from integer, in that case
582 if (!POINTER_TYPE_P (TREE_TYPE (addr)))
585 if (TREE_CODE (addr) != ADDR_EXPR)
588 return build_fold_addr_expr (TREE_OPERAND (addr, 0));
591 /* Analyzes the behavior of the memory reference DR in the innermost loop that
595 dr_analyze_innermost (struct data_reference *dr)
597 tree stmt = DR_STMT (dr);
598 struct loop *loop = loop_containing_stmt (stmt);
599 tree ref = DR_REF (dr);
600 HOST_WIDE_INT pbitsize, pbitpos;
602 enum machine_mode pmode;
603 int punsignedp, pvolatilep;
604 affine_iv base_iv, offset_iv;
605 tree init, dinit, step;
607 if (dump_file && (dump_flags & TDF_DETAILS))
608 fprintf (dump_file, "analyze_innermost: ");
610 base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset,
611 &pmode, &punsignedp, &pvolatilep, false);
612 gcc_assert (base != NULL_TREE);
614 if (pbitpos % BITS_PER_UNIT != 0)
616 if (dump_file && (dump_flags & TDF_DETAILS))
617 fprintf (dump_file, "failed: bit offset alignment.\n");
621 base = build_fold_addr_expr (base);
622 if (!simple_iv (loop, stmt, base, &base_iv, false))
624 if (dump_file && (dump_flags & TDF_DETAILS))
625 fprintf (dump_file, "failed: evolution of base is not affine.\n");
630 offset_iv.base = ssize_int (0);
631 offset_iv.step = ssize_int (0);
633 else if (!simple_iv (loop, stmt, poffset, &offset_iv, false))
635 if (dump_file && (dump_flags & TDF_DETAILS))
636 fprintf (dump_file, "failed: evolution of offset is not affine.\n");
640 init = ssize_int (pbitpos / BITS_PER_UNIT);
641 split_constant_offset (base_iv.base, &base_iv.base, &dinit);
642 init = size_binop (PLUS_EXPR, init, dinit);
643 split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
644 init = size_binop (PLUS_EXPR, init, dinit);
646 step = size_binop (PLUS_EXPR,
647 fold_convert (ssizetype, base_iv.step),
648 fold_convert (ssizetype, offset_iv.step));
650 DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base);
652 DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base);
656 DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base));
658 if (dump_file && (dump_flags & TDF_DETAILS))
659 fprintf (dump_file, "success.\n");
662 /* Determines the base object and the list of indices of memory reference
663 DR, analyzed in loop nest NEST. */
666 dr_analyze_indices (struct data_reference *dr, struct loop *nest)
668 tree stmt = DR_STMT (dr);
669 struct loop *loop = loop_containing_stmt (stmt);
670 VEC (tree, heap) *access_fns = NULL;
671 tree ref = unshare_expr (DR_REF (dr)), aref = ref, op;
672 tree base, off, access_fn;
674 while (handled_component_p (aref))
676 if (TREE_CODE (aref) == ARRAY_REF)
678 op = TREE_OPERAND (aref, 1);
679 access_fn = analyze_scalar_evolution (loop, op);
680 access_fn = resolve_mixers (nest, access_fn);
681 VEC_safe_push (tree, heap, access_fns, access_fn);
683 TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0);
686 aref = TREE_OPERAND (aref, 0);
689 if (INDIRECT_REF_P (aref))
691 op = TREE_OPERAND (aref, 0);
692 access_fn = analyze_scalar_evolution (loop, op);
693 access_fn = resolve_mixers (nest, access_fn);
694 base = initial_condition (access_fn);
695 split_constant_offset (base, &base, &off);
696 access_fn = chrec_replace_initial_condition (access_fn,
697 fold_convert (TREE_TYPE (base), off));
699 TREE_OPERAND (aref, 0) = base;
700 VEC_safe_push (tree, heap, access_fns, access_fn);
703 DR_BASE_OBJECT (dr) = ref;
704 DR_ACCESS_FNS (dr) = access_fns;
707 /* Extracts the alias analysis information from the memory reference DR. */
710 dr_analyze_alias (struct data_reference *dr)
712 tree stmt = DR_STMT (dr);
713 tree ref = DR_REF (dr);
714 tree base = get_base_address (ref), addr, smt = NULL_TREE;
721 else if (INDIRECT_REF_P (base))
723 addr = TREE_OPERAND (base, 0);
724 if (TREE_CODE (addr) == SSA_NAME)
726 smt = symbol_mem_tag (SSA_NAME_VAR (addr));
727 DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
731 DR_SYMBOL_TAG (dr) = smt;
732 if (var_can_have_subvars (smt))
733 DR_SUBVARS (dr) = get_subvars_for_var (smt);
735 vops = BITMAP_ALLOC (NULL);
736 FOR_EACH_SSA_TREE_OPERAND (op, stmt, it, SSA_OP_VIRTUAL_USES)
738 bitmap_set_bit (vops, DECL_UID (SSA_NAME_VAR (op)));
744 /* Returns true if the address of DR is invariant. */
747 dr_address_invariant_p (struct data_reference *dr)
752 for (i = 0; VEC_iterate (tree, DR_ACCESS_FNS (dr), i, idx); i++)
753 if (tree_contains_chrecs (idx, NULL))
759 /* Frees data reference DR. */
762 free_data_ref (data_reference_p dr)
764 BITMAP_FREE (DR_VOPS (dr));
765 VEC_free (tree, heap, DR_ACCESS_FNS (dr));
769 /* Analyzes memory reference MEMREF accessed in STMT. The reference
770 is read if IS_READ is true, write otherwise. Returns the
771 data_reference description of MEMREF. NEST is the outermost loop of the
772 loop nest in that the reference should be analysed. */
774 struct data_reference *
775 create_data_ref (struct loop *nest, tree memref, tree stmt, bool is_read)
777 struct data_reference *dr;
779 if (dump_file && (dump_flags & TDF_DETAILS))
781 fprintf (dump_file, "Creating dr for ");
782 print_generic_expr (dump_file, memref, TDF_SLIM);
783 fprintf (dump_file, "\n");
786 dr = XCNEW (struct data_reference);
788 DR_REF (dr) = memref;
789 DR_IS_READ (dr) = is_read;
791 dr_analyze_innermost (dr);
792 dr_analyze_indices (dr, nest);
793 dr_analyze_alias (dr);
795 if (dump_file && (dump_flags & TDF_DETAILS))
797 fprintf (dump_file, "\tbase_address: ");
798 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
799 fprintf (dump_file, "\n\toffset from base address: ");
800 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
801 fprintf (dump_file, "\n\tconstant offset from base address: ");
802 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
803 fprintf (dump_file, "\n\tstep: ");
804 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
805 fprintf (dump_file, "\n\taligned to: ");
806 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
807 fprintf (dump_file, "\n\tbase_object: ");
808 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
809 fprintf (dump_file, "\n\tsymbol tag: ");
810 print_generic_expr (dump_file, DR_SYMBOL_TAG (dr), TDF_SLIM);
811 fprintf (dump_file, "\n");
817 /* Returns true if FNA == FNB. */
820 affine_function_equal_p (affine_fn fna, affine_fn fnb)
822 unsigned i, n = VEC_length (tree, fna);
824 if (n != VEC_length (tree, fnb))
827 for (i = 0; i < n; i++)
828 if (!operand_equal_p (VEC_index (tree, fna, i),
829 VEC_index (tree, fnb, i), 0))
835 /* If all the functions in CF are the same, returns one of them,
836 otherwise returns NULL. */
839 common_affine_function (conflict_function *cf)
844 if (!CF_NONTRIVIAL_P (cf))
849 for (i = 1; i < cf->n; i++)
850 if (!affine_function_equal_p (comm, cf->fns[i]))
856 /* Returns the base of the affine function FN. */
859 affine_function_base (affine_fn fn)
861 return VEC_index (tree, fn, 0);
864 /* Returns true if FN is a constant. */
867 affine_function_constant_p (affine_fn fn)
872 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
873 if (!integer_zerop (coef))
879 /* Returns true if FN is the zero constant function. */
882 affine_function_zero_p (affine_fn fn)
884 return (integer_zerop (affine_function_base (fn))
885 && affine_function_constant_p (fn));
888 /* Applies operation OP on affine functions FNA and FNB, and returns the
892 affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
898 if (VEC_length (tree, fnb) > VEC_length (tree, fna))
900 n = VEC_length (tree, fna);
901 m = VEC_length (tree, fnb);
905 n = VEC_length (tree, fnb);
906 m = VEC_length (tree, fna);
909 ret = VEC_alloc (tree, heap, m);
910 for (i = 0; i < n; i++)
911 VEC_quick_push (tree, ret,
912 fold_build2 (op, integer_type_node,
913 VEC_index (tree, fna, i),
914 VEC_index (tree, fnb, i)));
916 for (; VEC_iterate (tree, fna, i, coef); i++)
917 VEC_quick_push (tree, ret,
918 fold_build2 (op, integer_type_node,
919 coef, integer_zero_node));
920 for (; VEC_iterate (tree, fnb, i, coef); i++)
921 VEC_quick_push (tree, ret,
922 fold_build2 (op, integer_type_node,
923 integer_zero_node, coef));
928 /* Returns the sum of affine functions FNA and FNB. */
931 affine_fn_plus (affine_fn fna, affine_fn fnb)
933 return affine_fn_op (PLUS_EXPR, fna, fnb);
936 /* Returns the difference of affine functions FNA and FNB. */
939 affine_fn_minus (affine_fn fna, affine_fn fnb)
941 return affine_fn_op (MINUS_EXPR, fna, fnb);
944 /* Frees affine function FN. */
947 affine_fn_free (affine_fn fn)
949 VEC_free (tree, heap, fn);
952 /* Determine for each subscript in the data dependence relation DDR
956 compute_subscript_distance (struct data_dependence_relation *ddr)
958 conflict_function *cf_a, *cf_b;
959 affine_fn fn_a, fn_b, diff;
961 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
965 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
967 struct subscript *subscript;
969 subscript = DDR_SUBSCRIPT (ddr, i);
970 cf_a = SUB_CONFLICTS_IN_A (subscript);
971 cf_b = SUB_CONFLICTS_IN_B (subscript);
973 fn_a = common_affine_function (cf_a);
974 fn_b = common_affine_function (cf_b);
977 SUB_DISTANCE (subscript) = chrec_dont_know;
980 diff = affine_fn_minus (fn_a, fn_b);
982 if (affine_function_constant_p (diff))
983 SUB_DISTANCE (subscript) = affine_function_base (diff);
985 SUB_DISTANCE (subscript) = chrec_dont_know;
987 affine_fn_free (diff);
992 /* Returns the conflict function for "unknown". */
994 static conflict_function *
995 conflict_fn_not_known (void)
997 conflict_function *fn = XCNEW (conflict_function);
1003 /* Returns the conflict function for "independent". */
1005 static conflict_function *
1006 conflict_fn_no_dependence (void)
1008 conflict_function *fn = XCNEW (conflict_function);
1009 fn->n = NO_DEPENDENCE;
1014 /* Returns true if the address of OBJ is invariant in LOOP. */
1017 object_address_invariant_in_loop_p (struct loop *loop, tree obj)
1019 while (handled_component_p (obj))
1021 if (TREE_CODE (obj) == ARRAY_REF)
1023 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1024 need to check the stride and the lower bound of the reference. */
1025 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1027 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 3),
1031 else if (TREE_CODE (obj) == COMPONENT_REF)
1033 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1037 obj = TREE_OPERAND (obj, 0);
1040 if (!INDIRECT_REF_P (obj))
1043 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0),
1047 /* Returns true if A and B are accesses to different objects, or to different
1048 fields of the same object. */
1051 disjoint_objects_p (tree a, tree b)
1053 tree base_a, base_b;
1054 VEC (tree, heap) *comp_a = NULL, *comp_b = NULL;
1057 base_a = get_base_address (a);
1058 base_b = get_base_address (b);
1062 && base_a != base_b)
1065 if (!operand_equal_p (base_a, base_b, 0))
1068 /* Compare the component references of A and B. We must start from the inner
1069 ones, so record them to the vector first. */
1070 while (handled_component_p (a))
1072 VEC_safe_push (tree, heap, comp_a, a);
1073 a = TREE_OPERAND (a, 0);
1075 while (handled_component_p (b))
1077 VEC_safe_push (tree, heap, comp_b, b);
1078 b = TREE_OPERAND (b, 0);
1084 if (VEC_length (tree, comp_a) == 0
1085 || VEC_length (tree, comp_b) == 0)
1088 a = VEC_pop (tree, comp_a);
1089 b = VEC_pop (tree, comp_b);
1091 /* Real and imaginary part of a variable do not alias. */
1092 if ((TREE_CODE (a) == REALPART_EXPR
1093 && TREE_CODE (b) == IMAGPART_EXPR)
1094 || (TREE_CODE (a) == IMAGPART_EXPR
1095 && TREE_CODE (b) == REALPART_EXPR))
1101 if (TREE_CODE (a) != TREE_CODE (b))
1104 /* Nothing to do for ARRAY_REFs, as the indices of array_refs in
1105 DR_BASE_OBJECT are always zero. */
1106 if (TREE_CODE (a) == ARRAY_REF)
1108 else if (TREE_CODE (a) == COMPONENT_REF)
1110 if (operand_equal_p (TREE_OPERAND (a, 1), TREE_OPERAND (b, 1), 0))
1113 /* Different fields of unions may overlap. */
1114 base_a = TREE_OPERAND (a, 0);
1115 if (TREE_CODE (TREE_TYPE (base_a)) == UNION_TYPE)
1118 /* Different fields of structures cannot. */
1126 VEC_free (tree, heap, comp_a);
1127 VEC_free (tree, heap, comp_b);
1132 /* Returns false if we can prove that data references A and B do not alias,
1136 dr_may_alias_p (struct data_reference *a, struct data_reference *b)
1138 tree addr_a = DR_BASE_ADDRESS (a);
1139 tree addr_b = DR_BASE_ADDRESS (b);
1140 tree type_a, type_b;
1141 tree decl_a = NULL_TREE, decl_b = NULL_TREE;
1143 /* If the sets of virtual operands are disjoint, the memory references do not
1145 if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
1148 /* If the accessed objects are disjoint, the memory references do not
1150 if (disjoint_objects_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b)))
1153 if (!addr_a || !addr_b)
1156 /* If the references are based on different static objects, they cannot alias
1157 (PTA should be able to disambiguate such accesses, but often it fails to,
1158 since currently we cannot distinguish between pointer and offset in pointer
1160 if (TREE_CODE (addr_a) == ADDR_EXPR
1161 && TREE_CODE (addr_b) == ADDR_EXPR)
1162 return TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0);
1164 /* An instruction writing through a restricted pointer is "independent" of any
1165 instruction reading or writing through a different restricted pointer,
1166 in the same block/scope. */
1168 type_a = TREE_TYPE (addr_a);
1169 type_b = TREE_TYPE (addr_b);
1170 gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
1172 if (TREE_CODE (addr_a) == SSA_NAME)
1173 decl_a = SSA_NAME_VAR (addr_a);
1174 if (TREE_CODE (addr_b) == SSA_NAME)
1175 decl_b = SSA_NAME_VAR (addr_b);
1177 if (TYPE_RESTRICT (type_a) && TYPE_RESTRICT (type_b)
1178 && (!DR_IS_READ (a) || !DR_IS_READ (b))
1179 && decl_a && DECL_P (decl_a)
1180 && decl_b && DECL_P (decl_b)
1182 && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL
1183 && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b))
1189 /* Initialize a data dependence relation between data accesses A and
1190 B. NB_LOOPS is the number of loops surrounding the references: the
1191 size of the classic distance/direction vectors. */
1193 static struct data_dependence_relation *
1194 initialize_data_dependence_relation (struct data_reference *a,
1195 struct data_reference *b,
1196 VEC (loop_p, heap) *loop_nest)
1198 struct data_dependence_relation *res;
1201 res = XNEW (struct data_dependence_relation);
1204 DDR_LOOP_NEST (res) = NULL;
1206 if (a == NULL || b == NULL)
1208 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1212 /* If the data references do not alias, then they are independent. */
1213 if (!dr_may_alias_p (a, b))
1215 DDR_ARE_DEPENDENT (res) = chrec_known;
1219 /* If the references do not access the same object, we do not know
1220 whether they alias or not. */
1221 if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0))
1223 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1227 /* If the base of the object is not invariant in the loop nest, we cannot
1228 analyse it. TODO -- in fact, it would suffice to record that there may
1229 be arbitrary dependences in the loops where the base object varies. */
1230 if (!object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
1231 DR_BASE_OBJECT (a)))
1233 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1237 gcc_assert (DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b));
1239 DDR_AFFINE_P (res) = true;
1240 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1241 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
1242 DDR_LOOP_NEST (res) = loop_nest;
1243 DDR_INNER_LOOP (res) = 0;
1244 DDR_DIR_VECTS (res) = NULL;
1245 DDR_DIST_VECTS (res) = NULL;
1247 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1249 struct subscript *subscript;
1251 subscript = XNEW (struct subscript);
1252 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
1253 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
1254 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1255 SUB_DISTANCE (subscript) = chrec_dont_know;
1256 VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
1262 /* Frees memory used by the conflict function F. */
1265 free_conflict_function (conflict_function *f)
1269 if (CF_NONTRIVIAL_P (f))
1271 for (i = 0; i < f->n; i++)
1272 affine_fn_free (f->fns[i]);
1277 /* Frees memory used by SUBSCRIPTS. */
1280 free_subscripts (VEC (subscript_p, heap) *subscripts)
1285 for (i = 0; VEC_iterate (subscript_p, subscripts, i, s); i++)
1287 free_conflict_function (s->conflicting_iterations_in_a);
1288 free_conflict_function (s->conflicting_iterations_in_b);
1290 VEC_free (subscript_p, heap, subscripts);
1293 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1297 finalize_ddr_dependent (struct data_dependence_relation *ddr,
1300 if (dump_file && (dump_flags & TDF_DETAILS))
1302 fprintf (dump_file, "(dependence classified: ");
1303 print_generic_expr (dump_file, chrec, 0);
1304 fprintf (dump_file, ")\n");
1307 DDR_ARE_DEPENDENT (ddr) = chrec;
1308 free_subscripts (DDR_SUBSCRIPTS (ddr));
1311 /* The dependence relation DDR cannot be represented by a distance
1315 non_affine_dependence_relation (struct data_dependence_relation *ddr)
1317 if (dump_file && (dump_flags & TDF_DETAILS))
1318 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
1320 DDR_AFFINE_P (ddr) = false;
1325 /* This section contains the classic Banerjee tests. */
1327 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1328 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1331 ziv_subscript_p (tree chrec_a,
1334 return (evolution_function_is_constant_p (chrec_a)
1335 && evolution_function_is_constant_p (chrec_b));
1338 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1339 variable, i.e., if the SIV (Single Index Variable) test is true. */
1342 siv_subscript_p (tree chrec_a,
1345 if ((evolution_function_is_constant_p (chrec_a)
1346 && evolution_function_is_univariate_p (chrec_b))
1347 || (evolution_function_is_constant_p (chrec_b)
1348 && evolution_function_is_univariate_p (chrec_a)))
1351 if (evolution_function_is_univariate_p (chrec_a)
1352 && evolution_function_is_univariate_p (chrec_b))
1354 switch (TREE_CODE (chrec_a))
1356 case POLYNOMIAL_CHREC:
1357 switch (TREE_CODE (chrec_b))
1359 case POLYNOMIAL_CHREC:
1360 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
1375 /* Creates a conflict function with N dimensions. The affine functions
1376 in each dimension follow. */
1378 static conflict_function *
1379 conflict_fn (unsigned n, ...)
1382 conflict_function *ret = XCNEW (conflict_function);
1385 gcc_assert (0 < n && n <= MAX_DIM);
1389 for (i = 0; i < n; i++)
1390 ret->fns[i] = va_arg (ap, affine_fn);
1396 /* Returns constant affine function with value CST. */
1399 affine_fn_cst (tree cst)
1401 affine_fn fn = VEC_alloc (tree, heap, 1);
1402 VEC_quick_push (tree, fn, cst);
1406 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1409 affine_fn_univar (tree cst, unsigned dim, tree coef)
1411 affine_fn fn = VEC_alloc (tree, heap, dim + 1);
1414 gcc_assert (dim > 0);
1415 VEC_quick_push (tree, fn, cst);
1416 for (i = 1; i < dim; i++)
1417 VEC_quick_push (tree, fn, integer_zero_node);
1418 VEC_quick_push (tree, fn, coef);
1422 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1423 *OVERLAPS_B are initialized to the functions that describe the
1424 relation between the elements accessed twice by CHREC_A and
1425 CHREC_B. For k >= 0, the following property is verified:
1427 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1430 analyze_ziv_subscript (tree chrec_a,
1432 conflict_function **overlaps_a,
1433 conflict_function **overlaps_b,
1434 tree *last_conflicts)
1437 dependence_stats.num_ziv++;
1439 if (dump_file && (dump_flags & TDF_DETAILS))
1440 fprintf (dump_file, "(analyze_ziv_subscript \n");
1442 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
1443 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
1444 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
1446 switch (TREE_CODE (difference))
1449 if (integer_zerop (difference))
1451 /* The difference is equal to zero: the accessed index
1452 overlaps for each iteration in the loop. */
1453 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1454 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1455 *last_conflicts = chrec_dont_know;
1456 dependence_stats.num_ziv_dependent++;
1460 /* The accesses do not overlap. */
1461 *overlaps_a = conflict_fn_no_dependence ();
1462 *overlaps_b = conflict_fn_no_dependence ();
1463 *last_conflicts = integer_zero_node;
1464 dependence_stats.num_ziv_independent++;
1469 /* We're not sure whether the indexes overlap. For the moment,
1470 conservatively answer "don't know". */
1471 if (dump_file && (dump_flags & TDF_DETAILS))
1472 fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
1474 *overlaps_a = conflict_fn_not_known ();
1475 *overlaps_b = conflict_fn_not_known ();
1476 *last_conflicts = chrec_dont_know;
1477 dependence_stats.num_ziv_unimplemented++;
1481 if (dump_file && (dump_flags & TDF_DETAILS))
1482 fprintf (dump_file, ")\n");
1485 /* Sets NIT to the estimated number of executions of the statements in
1486 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
1487 large as the number of iterations. If we have no reliable estimate,
1488 the function returns false, otherwise returns true. */
1491 estimated_loop_iterations (struct loop *loop, bool conservative,
1494 estimate_numbers_of_iterations_loop (loop);
1497 if (!loop->any_upper_bound)
1500 *nit = loop->nb_iterations_upper_bound;
1504 if (!loop->any_estimate)
1507 *nit = loop->nb_iterations_estimate;
1513 /* Similar to estimated_loop_iterations, but returns the estimate only
1514 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1515 on the number of iterations of LOOP could not be derived, returns -1. */
1518 estimated_loop_iterations_int (struct loop *loop, bool conservative)
1521 HOST_WIDE_INT hwi_nit;
1523 if (!estimated_loop_iterations (loop, conservative, &nit))
1526 if (!double_int_fits_in_shwi_p (nit))
1528 hwi_nit = double_int_to_shwi (nit);
1530 return hwi_nit < 0 ? -1 : hwi_nit;
1533 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
1534 and only if it fits to the int type. If this is not the case, or the
1535 estimate on the number of iterations of LOOP could not be derived, returns
1539 estimated_loop_iterations_tree (struct loop *loop, bool conservative)
1544 if (!estimated_loop_iterations (loop, conservative, &nit))
1545 return chrec_dont_know;
1547 type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
1548 if (!double_int_fits_to_tree_p (type, nit))
1549 return chrec_dont_know;
1551 return double_int_to_tree (type, nit);
1554 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1555 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1556 *OVERLAPS_B are initialized to the functions that describe the
1557 relation between the elements accessed twice by CHREC_A and
1558 CHREC_B. For k >= 0, the following property is verified:
1560 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1563 analyze_siv_subscript_cst_affine (tree chrec_a,
1565 conflict_function **overlaps_a,
1566 conflict_function **overlaps_b,
1567 tree *last_conflicts)
1569 bool value0, value1, value2;
1570 tree difference, tmp;
1572 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
1573 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
1574 difference = chrec_fold_minus
1575 (integer_type_node, initial_condition (chrec_b), chrec_a);
1577 if (!chrec_is_positive (initial_condition (difference), &value0))
1579 if (dump_file && (dump_flags & TDF_DETAILS))
1580 fprintf (dump_file, "siv test failed: chrec is not positive.\n");
1582 dependence_stats.num_siv_unimplemented++;
1583 *overlaps_a = conflict_fn_not_known ();
1584 *overlaps_b = conflict_fn_not_known ();
1585 *last_conflicts = chrec_dont_know;
1590 if (value0 == false)
1592 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
1594 if (dump_file && (dump_flags & TDF_DETAILS))
1595 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1597 *overlaps_a = conflict_fn_not_known ();
1598 *overlaps_b = conflict_fn_not_known ();
1599 *last_conflicts = chrec_dont_know;
1600 dependence_stats.num_siv_unimplemented++;
1609 chrec_b = {10, +, 1}
1612 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1614 HOST_WIDE_INT numiter;
1615 struct loop *loop = get_chrec_loop (chrec_b);
1617 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1618 tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
1619 fold_build1 (ABS_EXPR,
1622 CHREC_RIGHT (chrec_b));
1623 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1624 *last_conflicts = integer_one_node;
1627 /* Perform weak-zero siv test to see if overlap is
1628 outside the loop bounds. */
1629 numiter = estimated_loop_iterations_int (loop, true);
1632 && compare_tree_int (tmp, numiter) > 0)
1634 free_conflict_function (*overlaps_a);
1635 free_conflict_function (*overlaps_b);
1636 *overlaps_a = conflict_fn_no_dependence ();
1637 *overlaps_b = conflict_fn_no_dependence ();
1638 *last_conflicts = integer_zero_node;
1639 dependence_stats.num_siv_independent++;
1642 dependence_stats.num_siv_dependent++;
1646 /* When the step does not divide the difference, there are
1650 *overlaps_a = conflict_fn_no_dependence ();
1651 *overlaps_b = conflict_fn_no_dependence ();
1652 *last_conflicts = integer_zero_node;
1653 dependence_stats.num_siv_independent++;
1662 chrec_b = {10, +, -1}
1664 In this case, chrec_a will not overlap with chrec_b. */
1665 *overlaps_a = conflict_fn_no_dependence ();
1666 *overlaps_b = conflict_fn_no_dependence ();
1667 *last_conflicts = integer_zero_node;
1668 dependence_stats.num_siv_independent++;
1675 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
1677 if (dump_file && (dump_flags & TDF_DETAILS))
1678 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1680 *overlaps_a = conflict_fn_not_known ();
1681 *overlaps_b = conflict_fn_not_known ();
1682 *last_conflicts = chrec_dont_know;
1683 dependence_stats.num_siv_unimplemented++;
1688 if (value2 == false)
1692 chrec_b = {10, +, -1}
1694 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1696 HOST_WIDE_INT numiter;
1697 struct loop *loop = get_chrec_loop (chrec_b);
1699 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1700 tmp = fold_build2 (EXACT_DIV_EXPR,
1701 integer_type_node, difference,
1702 CHREC_RIGHT (chrec_b));
1703 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1704 *last_conflicts = integer_one_node;
1706 /* Perform weak-zero siv test to see if overlap is
1707 outside the loop bounds. */
1708 numiter = estimated_loop_iterations_int (loop, true);
1711 && compare_tree_int (tmp, numiter) > 0)
1713 free_conflict_function (*overlaps_a);
1714 free_conflict_function (*overlaps_b);
1715 *overlaps_a = conflict_fn_no_dependence ();
1716 *overlaps_b = conflict_fn_no_dependence ();
1717 *last_conflicts = integer_zero_node;
1718 dependence_stats.num_siv_independent++;
1721 dependence_stats.num_siv_dependent++;
1725 /* When the step does not divide the difference, there
1729 *overlaps_a = conflict_fn_no_dependence ();
1730 *overlaps_b = conflict_fn_no_dependence ();
1731 *last_conflicts = integer_zero_node;
1732 dependence_stats.num_siv_independent++;
1742 In this case, chrec_a will not overlap with chrec_b. */
1743 *overlaps_a = conflict_fn_no_dependence ();
1744 *overlaps_b = conflict_fn_no_dependence ();
1745 *last_conflicts = integer_zero_node;
1746 dependence_stats.num_siv_independent++;
1754 /* Helper recursive function for initializing the matrix A. Returns
1755 the initial value of CHREC. */
1758 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
1762 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1763 return int_cst_value (chrec);
1765 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
1766 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
1769 #define FLOOR_DIV(x,y) ((x) / (y))
1771 /* Solves the special case of the Diophantine equation:
1772 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1774 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
1775 number of iterations that loops X and Y run. The overlaps will be
1776 constructed as evolutions in dimension DIM. */
1779 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
1780 affine_fn *overlaps_a,
1781 affine_fn *overlaps_b,
1782 tree *last_conflicts, int dim)
1784 if (((step_a > 0 && step_b > 0)
1785 || (step_a < 0 && step_b < 0)))
1787 int step_overlaps_a, step_overlaps_b;
1788 int gcd_steps_a_b, last_conflict, tau2;
1790 gcd_steps_a_b = gcd (step_a, step_b);
1791 step_overlaps_a = step_b / gcd_steps_a_b;
1792 step_overlaps_b = step_a / gcd_steps_a_b;
1794 tau2 = FLOOR_DIV (niter, step_overlaps_a);
1795 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
1796 last_conflict = tau2;
1798 *overlaps_a = affine_fn_univar (integer_zero_node, dim,
1799 build_int_cst (NULL_TREE,
1801 *overlaps_b = affine_fn_univar (integer_zero_node, dim,
1802 build_int_cst (NULL_TREE,
1804 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
1809 *overlaps_a = affine_fn_cst (integer_zero_node);
1810 *overlaps_b = affine_fn_cst (integer_zero_node);
1811 *last_conflicts = integer_zero_node;
1815 /* Solves the special case of a Diophantine equation where CHREC_A is
1816 an affine bivariate function, and CHREC_B is an affine univariate
1817 function. For example,
1819 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1821 has the following overlapping functions:
1823 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1824 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1825 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1827 FORNOW: This is a specialized implementation for a case occurring in
1828 a common benchmark. Implement the general algorithm. */
1831 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
1832 conflict_function **overlaps_a,
1833 conflict_function **overlaps_b,
1834 tree *last_conflicts)
1836 bool xz_p, yz_p, xyz_p;
1837 int step_x, step_y, step_z;
1838 HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
1839 affine_fn overlaps_a_xz, overlaps_b_xz;
1840 affine_fn overlaps_a_yz, overlaps_b_yz;
1841 affine_fn overlaps_a_xyz, overlaps_b_xyz;
1842 affine_fn ova1, ova2, ovb;
1843 tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
1845 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
1846 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
1847 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
1849 niter_x = estimated_loop_iterations_int
1850 (get_chrec_loop (CHREC_LEFT (chrec_a)), true);
1851 niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), true);
1852 niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), true);
1854 if (niter_x < 0 || niter_y < 0 || niter_z < 0)
1856 if (dump_file && (dump_flags & TDF_DETAILS))
1857 fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
1859 *overlaps_a = conflict_fn_not_known ();
1860 *overlaps_b = conflict_fn_not_known ();
1861 *last_conflicts = chrec_dont_know;
1865 niter = MIN (niter_x, niter_z);
1866 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
1869 &last_conflicts_xz, 1);
1870 niter = MIN (niter_y, niter_z);
1871 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
1874 &last_conflicts_yz, 2);
1875 niter = MIN (niter_x, niter_z);
1876 niter = MIN (niter_y, niter);
1877 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
1880 &last_conflicts_xyz, 3);
1882 xz_p = !integer_zerop (last_conflicts_xz);
1883 yz_p = !integer_zerop (last_conflicts_yz);
1884 xyz_p = !integer_zerop (last_conflicts_xyz);
1886 if (xz_p || yz_p || xyz_p)
1888 ova1 = affine_fn_cst (integer_zero_node);
1889 ova2 = affine_fn_cst (integer_zero_node);
1890 ovb = affine_fn_cst (integer_zero_node);
1893 affine_fn t0 = ova1;
1896 ova1 = affine_fn_plus (ova1, overlaps_a_xz);
1897 ovb = affine_fn_plus (ovb, overlaps_b_xz);
1898 affine_fn_free (t0);
1899 affine_fn_free (t2);
1900 *last_conflicts = last_conflicts_xz;
1904 affine_fn t0 = ova2;
1907 ova2 = affine_fn_plus (ova2, overlaps_a_yz);
1908 ovb = affine_fn_plus (ovb, overlaps_b_yz);
1909 affine_fn_free (t0);
1910 affine_fn_free (t2);
1911 *last_conflicts = last_conflicts_yz;
1915 affine_fn t0 = ova1;
1916 affine_fn t2 = ova2;
1919 ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
1920 ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
1921 ovb = affine_fn_plus (ovb, overlaps_b_xyz);
1922 affine_fn_free (t0);
1923 affine_fn_free (t2);
1924 affine_fn_free (t4);
1925 *last_conflicts = last_conflicts_xyz;
1927 *overlaps_a = conflict_fn (2, ova1, ova2);
1928 *overlaps_b = conflict_fn (1, ovb);
1932 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1933 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1934 *last_conflicts = integer_zero_node;
1937 affine_fn_free (overlaps_a_xz);
1938 affine_fn_free (overlaps_b_xz);
1939 affine_fn_free (overlaps_a_yz);
1940 affine_fn_free (overlaps_b_yz);
1941 affine_fn_free (overlaps_a_xyz);
1942 affine_fn_free (overlaps_b_xyz);
1945 /* Determines the overlapping elements due to accesses CHREC_A and
1946 CHREC_B, that are affine functions. This function cannot handle
1947 symbolic evolution functions, ie. when initial conditions are
1948 parameters, because it uses lambda matrices of integers. */
1951 analyze_subscript_affine_affine (tree chrec_a,
1953 conflict_function **overlaps_a,
1954 conflict_function **overlaps_b,
1955 tree *last_conflicts)
1957 unsigned nb_vars_a, nb_vars_b, dim;
1958 int init_a, init_b, gamma, gcd_alpha_beta;
1960 lambda_matrix A, U, S;
1962 if (eq_evolutions_p (chrec_a, chrec_b))
1964 /* The accessed index overlaps for each iteration in the
1966 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1967 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1968 *last_conflicts = chrec_dont_know;
1971 if (dump_file && (dump_flags & TDF_DETAILS))
1972 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
1974 /* For determining the initial intersection, we have to solve a
1975 Diophantine equation. This is the most time consuming part.
1977 For answering to the question: "Is there a dependence?" we have
1978 to prove that there exists a solution to the Diophantine
1979 equation, and that the solution is in the iteration domain,
1980 i.e. the solution is positive or zero, and that the solution
1981 happens before the upper bound loop.nb_iterations. Otherwise
1982 there is no dependence. This function outputs a description of
1983 the iterations that hold the intersections. */
1985 nb_vars_a = nb_vars_in_chrec (chrec_a);
1986 nb_vars_b = nb_vars_in_chrec (chrec_b);
1988 dim = nb_vars_a + nb_vars_b;
1989 U = lambda_matrix_new (dim, dim);
1990 A = lambda_matrix_new (dim, 1);
1991 S = lambda_matrix_new (dim, 1);
1993 init_a = initialize_matrix_A (A, chrec_a, 0, 1);
1994 init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
1995 gamma = init_b - init_a;
1997 /* Don't do all the hard work of solving the Diophantine equation
1998 when we already know the solution: for example,
2001 | gamma = 3 - 3 = 0.
2002 Then the first overlap occurs during the first iterations:
2003 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2007 if (nb_vars_a == 1 && nb_vars_b == 1)
2010 HOST_WIDE_INT niter, niter_a, niter_b;
2013 niter_a = estimated_loop_iterations_int
2014 (get_chrec_loop (chrec_a), true);
2015 niter_b = estimated_loop_iterations_int
2016 (get_chrec_loop (chrec_b), true);
2017 if (niter_a < 0 || niter_b < 0)
2019 if (dump_file && (dump_flags & TDF_DETAILS))
2020 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
2021 *overlaps_a = conflict_fn_not_known ();
2022 *overlaps_b = conflict_fn_not_known ();
2023 *last_conflicts = chrec_dont_know;
2024 goto end_analyze_subs_aa;
2027 niter = MIN (niter_a, niter_b);
2029 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2030 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2032 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2035 *overlaps_a = conflict_fn (1, ova);
2036 *overlaps_b = conflict_fn (1, ovb);
2039 else if (nb_vars_a == 2 && nb_vars_b == 1)
2040 compute_overlap_steps_for_affine_1_2
2041 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2043 else if (nb_vars_a == 1 && nb_vars_b == 2)
2044 compute_overlap_steps_for_affine_1_2
2045 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2049 if (dump_file && (dump_flags & TDF_DETAILS))
2050 fprintf (dump_file, "affine-affine test failed: too many variables.\n");
2051 *overlaps_a = conflict_fn_not_known ();
2052 *overlaps_b = conflict_fn_not_known ();
2053 *last_conflicts = chrec_dont_know;
2055 goto end_analyze_subs_aa;
2059 lambda_matrix_right_hermite (A, dim, 1, S, U);
2064 lambda_matrix_row_negate (U, dim, 0);
2066 gcd_alpha_beta = S[0][0];
2068 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2069 but that is a quite strange case. Instead of ICEing, answer
2071 if (gcd_alpha_beta == 0)
2073 *overlaps_a = conflict_fn_not_known ();
2074 *overlaps_b = conflict_fn_not_known ();
2075 *last_conflicts = chrec_dont_know;
2076 goto end_analyze_subs_aa;
2079 /* The classic "gcd-test". */
2080 if (!int_divides_p (gcd_alpha_beta, gamma))
2082 /* The "gcd-test" has determined that there is no integer
2083 solution, i.e. there is no dependence. */
2084 *overlaps_a = conflict_fn_no_dependence ();
2085 *overlaps_b = conflict_fn_no_dependence ();
2086 *last_conflicts = integer_zero_node;
2089 /* Both access functions are univariate. This includes SIV and MIV cases. */
2090 else if (nb_vars_a == 1 && nb_vars_b == 1)
2092 /* Both functions should have the same evolution sign. */
2093 if (((A[0][0] > 0 && -A[1][0] > 0)
2094 || (A[0][0] < 0 && -A[1][0] < 0)))
2096 /* The solutions are given by:
2098 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2101 For a given integer t. Using the following variables,
2103 | i0 = u11 * gamma / gcd_alpha_beta
2104 | j0 = u12 * gamma / gcd_alpha_beta
2111 | y0 = j0 + j1 * t. */
2115 /* X0 and Y0 are the first iterations for which there is a
2116 dependence. X0, Y0 are two solutions of the Diophantine
2117 equation: chrec_a (X0) = chrec_b (Y0). */
2119 int niter, niter_a, niter_b;
2121 niter_a = estimated_loop_iterations_int
2122 (get_chrec_loop (chrec_a), true);
2123 niter_b = estimated_loop_iterations_int
2124 (get_chrec_loop (chrec_b), true);
2126 if (niter_a < 0 || niter_b < 0)
2128 if (dump_file && (dump_flags & TDF_DETAILS))
2129 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
2130 *overlaps_a = conflict_fn_not_known ();
2131 *overlaps_b = conflict_fn_not_known ();
2132 *last_conflicts = chrec_dont_know;
2133 goto end_analyze_subs_aa;
2136 niter = MIN (niter_a, niter_b);
2138 i0 = U[0][0] * gamma / gcd_alpha_beta;
2139 j0 = U[0][1] * gamma / gcd_alpha_beta;
2143 if ((i1 == 0 && i0 < 0)
2144 || (j1 == 0 && j0 < 0))
2146 /* There is no solution.
2147 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2148 falls in here, but for the moment we don't look at the
2149 upper bound of the iteration domain. */
2150 *overlaps_a = conflict_fn_no_dependence ();
2151 *overlaps_b = conflict_fn_no_dependence ();
2152 *last_conflicts = integer_zero_node;
2159 tau1 = CEIL (-i0, i1);
2160 tau2 = FLOOR_DIV (niter - i0, i1);
2164 int last_conflict, min_multiple;
2165 tau1 = MAX (tau1, CEIL (-j0, j1));
2166 tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
2168 x0 = i1 * tau1 + i0;
2169 y0 = j1 * tau1 + j0;
2171 /* At this point (x0, y0) is one of the
2172 solutions to the Diophantine equation. The
2173 next step has to compute the smallest
2174 positive solution: the first conflicts. */
2175 min_multiple = MIN (x0 / i1, y0 / j1);
2176 x0 -= i1 * min_multiple;
2177 y0 -= j1 * min_multiple;
2179 tau1 = (x0 - i0)/i1;
2180 last_conflict = tau2 - tau1;
2182 /* If the overlap occurs outside of the bounds of the
2183 loop, there is no dependence. */
2184 if (x0 > niter || y0 > niter)
2186 *overlaps_a = conflict_fn_no_dependence ();
2187 *overlaps_b = conflict_fn_no_dependence ();
2188 *last_conflicts = integer_zero_node;
2194 affine_fn_univar (build_int_cst (NULL_TREE, x0),
2196 build_int_cst (NULL_TREE, i1)));
2199 affine_fn_univar (build_int_cst (NULL_TREE, y0),
2201 build_int_cst (NULL_TREE, j1)));
2202 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2207 /* FIXME: For the moment, the upper bound of the
2208 iteration domain for j is not checked. */
2209 if (dump_file && (dump_flags & TDF_DETAILS))
2210 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2211 *overlaps_a = conflict_fn_not_known ();
2212 *overlaps_b = conflict_fn_not_known ();
2213 *last_conflicts = chrec_dont_know;
2219 /* FIXME: For the moment, the upper bound of the
2220 iteration domain for i is not checked. */
2221 if (dump_file && (dump_flags & TDF_DETAILS))
2222 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2223 *overlaps_a = conflict_fn_not_known ();
2224 *overlaps_b = conflict_fn_not_known ();
2225 *last_conflicts = chrec_dont_know;
2231 if (dump_file && (dump_flags & TDF_DETAILS))
2232 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2233 *overlaps_a = conflict_fn_not_known ();
2234 *overlaps_b = conflict_fn_not_known ();
2235 *last_conflicts = chrec_dont_know;
2241 if (dump_file && (dump_flags & TDF_DETAILS))
2242 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2243 *overlaps_a = conflict_fn_not_known ();
2244 *overlaps_b = conflict_fn_not_known ();
2245 *last_conflicts = chrec_dont_know;
2248 end_analyze_subs_aa:
2249 if (dump_file && (dump_flags & TDF_DETAILS))
2251 fprintf (dump_file, " (overlaps_a = ");
2252 dump_conflict_function (dump_file, *overlaps_a);
2253 fprintf (dump_file, ")\n (overlaps_b = ");
2254 dump_conflict_function (dump_file, *overlaps_b);
2255 fprintf (dump_file, ")\n");
2256 fprintf (dump_file, ")\n");
2260 /* Returns true when analyze_subscript_affine_affine can be used for
2261 determining the dependence relation between chrec_a and chrec_b,
2262 that contain symbols. This function modifies chrec_a and chrec_b
2263 such that the analysis result is the same, and such that they don't
2264 contain symbols, and then can safely be passed to the analyzer.
2266 Example: The analysis of the following tuples of evolutions produce
2267 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2270 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2271 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2275 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
2277 tree diff, type, left_a, left_b, right_b;
2279 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
2280 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
2281 /* FIXME: For the moment not handled. Might be refined later. */
2284 type = chrec_type (*chrec_a);
2285 left_a = CHREC_LEFT (*chrec_a);
2286 left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE);
2287 diff = chrec_fold_minus (type, left_a, left_b);
2289 if (!evolution_function_is_constant_p (diff))
2292 if (dump_file && (dump_flags & TDF_DETAILS))
2293 fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
2295 *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
2296 diff, CHREC_RIGHT (*chrec_a));
2297 right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE);
2298 *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
2299 build_int_cst (type, 0),
2304 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2305 *OVERLAPS_B are initialized to the functions that describe the
2306 relation between the elements accessed twice by CHREC_A and
2307 CHREC_B. For k >= 0, the following property is verified:
2309 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2312 analyze_siv_subscript (tree chrec_a,
2314 conflict_function **overlaps_a,
2315 conflict_function **overlaps_b,
2316 tree *last_conflicts)
2318 dependence_stats.num_siv++;
2320 if (dump_file && (dump_flags & TDF_DETAILS))
2321 fprintf (dump_file, "(analyze_siv_subscript \n");
2323 if (evolution_function_is_constant_p (chrec_a)
2324 && evolution_function_is_affine_p (chrec_b))
2325 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
2326 overlaps_a, overlaps_b, last_conflicts);
2328 else if (evolution_function_is_affine_p (chrec_a)
2329 && evolution_function_is_constant_p (chrec_b))
2330 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2331 overlaps_b, overlaps_a, last_conflicts);
2333 else if (evolution_function_is_affine_p (chrec_a)
2334 && evolution_function_is_affine_p (chrec_b))
2336 if (!chrec_contains_symbols (chrec_a)
2337 && !chrec_contains_symbols (chrec_b))
2339 analyze_subscript_affine_affine (chrec_a, chrec_b,
2340 overlaps_a, overlaps_b,
2343 if (CF_NOT_KNOWN_P (*overlaps_a)
2344 || CF_NOT_KNOWN_P (*overlaps_b))
2345 dependence_stats.num_siv_unimplemented++;
2346 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2347 || CF_NO_DEPENDENCE_P (*overlaps_b))
2348 dependence_stats.num_siv_independent++;
2350 dependence_stats.num_siv_dependent++;
2352 else if (can_use_analyze_subscript_affine_affine (&chrec_a,
2355 analyze_subscript_affine_affine (chrec_a, chrec_b,
2356 overlaps_a, overlaps_b,
2358 /* FIXME: The number of iterations is a symbolic expression.
2359 Compute it properly. */
2360 *last_conflicts = chrec_dont_know;
2362 if (CF_NOT_KNOWN_P (*overlaps_a)
2363 || CF_NOT_KNOWN_P (*overlaps_b))
2364 dependence_stats.num_siv_unimplemented++;
2365 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2366 || CF_NO_DEPENDENCE_P (*overlaps_b))
2367 dependence_stats.num_siv_independent++;
2369 dependence_stats.num_siv_dependent++;
2372 goto siv_subscript_dontknow;
2377 siv_subscript_dontknow:;
2378 if (dump_file && (dump_flags & TDF_DETAILS))
2379 fprintf (dump_file, "siv test failed: unimplemented.\n");
2380 *overlaps_a = conflict_fn_not_known ();
2381 *overlaps_b = conflict_fn_not_known ();
2382 *last_conflicts = chrec_dont_know;
2383 dependence_stats.num_siv_unimplemented++;
2386 if (dump_file && (dump_flags & TDF_DETAILS))
2387 fprintf (dump_file, ")\n");
2390 /* Returns false if we can prove that the greatest common divisor of the steps
2391 of CHREC does not divide CST, false otherwise. */
2394 gcd_of_steps_may_divide_p (tree chrec, tree cst)
2396 HOST_WIDE_INT cd = 0, val;
2399 if (!host_integerp (cst, 0))
2401 val = tree_low_cst (cst, 0);
2403 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
2405 step = CHREC_RIGHT (chrec);
2406 if (!host_integerp (step, 0))
2408 cd = gcd (cd, tree_low_cst (step, 0));
2409 chrec = CHREC_LEFT (chrec);
2412 return val % cd == 0;
2415 /* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
2416 *OVERLAPS_B are initialized to the functions that describe the
2417 relation between the elements accessed twice by CHREC_A and
2418 CHREC_B. For k >= 0, the following property is verified:
2420 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2423 analyze_miv_subscript (tree chrec_a,
2425 conflict_function **overlaps_a,
2426 conflict_function **overlaps_b,
2427 tree *last_conflicts)
2429 /* FIXME: This is a MIV subscript, not yet handled.
2430 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2433 In the SIV test we had to solve a Diophantine equation with two
2434 variables. In the MIV case we have to solve a Diophantine
2435 equation with 2*n variables (if the subscript uses n IVs).
2438 dependence_stats.num_miv++;
2439 if (dump_file && (dump_flags & TDF_DETAILS))
2440 fprintf (dump_file, "(analyze_miv_subscript \n");
2442 chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
2443 chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
2444 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2446 if (eq_evolutions_p (chrec_a, chrec_b))
2448 /* Access functions are the same: all the elements are accessed
2449 in the same order. */
2450 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2451 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2452 *last_conflicts = estimated_loop_iterations_tree
2453 (get_chrec_loop (chrec_a), true);
2454 dependence_stats.num_miv_dependent++;
2457 else if (evolution_function_is_constant_p (difference)
2458 /* For the moment, the following is verified:
2459 evolution_function_is_affine_multivariate_p (chrec_a, 0) */
2460 && !gcd_of_steps_may_divide_p (chrec_a, difference))
2462 /* testsuite/.../ssa-chrec-33.c
2463 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2465 The difference is 1, and all the evolution steps are multiples
2466 of 2, consequently there are no overlapping elements. */
2467 *overlaps_a = conflict_fn_no_dependence ();
2468 *overlaps_b = conflict_fn_no_dependence ();
2469 *last_conflicts = integer_zero_node;
2470 dependence_stats.num_miv_independent++;
2473 else if (evolution_function_is_affine_multivariate_p (chrec_a, 0)
2474 && !chrec_contains_symbols (chrec_a)
2475 && evolution_function_is_affine_multivariate_p (chrec_b, 0)
2476 && !chrec_contains_symbols (chrec_b))
2478 /* testsuite/.../ssa-chrec-35.c
2479 {0, +, 1}_2 vs. {0, +, 1}_3
2480 the overlapping elements are respectively located at iterations:
2481 {0, +, 1}_x and {0, +, 1}_x,
2482 in other words, we have the equality:
2483 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2486 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2487 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2489 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2490 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2492 analyze_subscript_affine_affine (chrec_a, chrec_b,
2493 overlaps_a, overlaps_b, last_conflicts);
2495 if (CF_NOT_KNOWN_P (*overlaps_a)
2496 || CF_NOT_KNOWN_P (*overlaps_b))
2497 dependence_stats.num_miv_unimplemented++;
2498 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2499 || CF_NO_DEPENDENCE_P (*overlaps_b))
2500 dependence_stats.num_miv_independent++;
2502 dependence_stats.num_miv_dependent++;
2507 /* When the analysis is too difficult, answer "don't know". */
2508 if (dump_file && (dump_flags & TDF_DETAILS))
2509 fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
2511 *overlaps_a = conflict_fn_not_known ();
2512 *overlaps_b = conflict_fn_not_known ();
2513 *last_conflicts = chrec_dont_know;
2514 dependence_stats.num_miv_unimplemented++;
2517 if (dump_file && (dump_flags & TDF_DETAILS))
2518 fprintf (dump_file, ")\n");
2521 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
2522 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
2523 two functions that describe the iterations that contain conflicting
2526 Remark: For an integer k >= 0, the following equality is true:
2528 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2532 analyze_overlapping_iterations (tree chrec_a,
2534 conflict_function **overlap_iterations_a,
2535 conflict_function **overlap_iterations_b,
2536 tree *last_conflicts)
2538 dependence_stats.num_subscript_tests++;
2540 if (dump_file && (dump_flags & TDF_DETAILS))
2542 fprintf (dump_file, "(analyze_overlapping_iterations \n");
2543 fprintf (dump_file, " (chrec_a = ");
2544 print_generic_expr (dump_file, chrec_a, 0);
2545 fprintf (dump_file, ")\n (chrec_b = ");
2546 print_generic_expr (dump_file, chrec_b, 0);
2547 fprintf (dump_file, ")\n");
2550 if (chrec_a == NULL_TREE
2551 || chrec_b == NULL_TREE
2552 || chrec_contains_undetermined (chrec_a)
2553 || chrec_contains_undetermined (chrec_b))
2555 dependence_stats.num_subscript_undetermined++;
2557 *overlap_iterations_a = conflict_fn_not_known ();
2558 *overlap_iterations_b = conflict_fn_not_known ();
2561 /* If they are the same chrec, and are affine, they overlap
2562 on every iteration. */
2563 else if (eq_evolutions_p (chrec_a, chrec_b)
2564 && evolution_function_is_affine_multivariate_p (chrec_a, 0))
2566 dependence_stats.num_same_subscript_function++;
2567 *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2568 *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2569 *last_conflicts = chrec_dont_know;
2572 /* If they aren't the same, and aren't affine, we can't do anything
2574 else if ((chrec_contains_symbols (chrec_a)
2575 || chrec_contains_symbols (chrec_b))
2576 && (!evolution_function_is_affine_multivariate_p (chrec_a, 0)
2577 || !evolution_function_is_affine_multivariate_p (chrec_b, 0)))
2579 dependence_stats.num_subscript_undetermined++;
2580 *overlap_iterations_a = conflict_fn_not_known ();
2581 *overlap_iterations_b = conflict_fn_not_known ();
2584 else if (ziv_subscript_p (chrec_a, chrec_b))
2585 analyze_ziv_subscript (chrec_a, chrec_b,
2586 overlap_iterations_a, overlap_iterations_b,
2589 else if (siv_subscript_p (chrec_a, chrec_b))
2590 analyze_siv_subscript (chrec_a, chrec_b,
2591 overlap_iterations_a, overlap_iterations_b,
2595 analyze_miv_subscript (chrec_a, chrec_b,
2596 overlap_iterations_a, overlap_iterations_b,
2599 if (dump_file && (dump_flags & TDF_DETAILS))
2601 fprintf (dump_file, " (overlap_iterations_a = ");
2602 dump_conflict_function (dump_file, *overlap_iterations_a);
2603 fprintf (dump_file, ")\n (overlap_iterations_b = ");
2604 dump_conflict_function (dump_file, *overlap_iterations_b);
2605 fprintf (dump_file, ")\n");
2606 fprintf (dump_file, ")\n");
2610 /* Helper function for uniquely inserting distance vectors. */
2613 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
2618 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
2619 if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
2622 VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
2625 /* Helper function for uniquely inserting direction vectors. */
2628 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
2633 for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
2634 if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
2637 VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
2640 /* Add a distance of 1 on all the loops outer than INDEX. If we
2641 haven't yet determined a distance for this outer loop, push a new
2642 distance vector composed of the previous distance, and a distance
2643 of 1 for this outer loop. Example:
2651 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
2652 save (0, 1), then we have to save (1, 0). */
2655 add_outer_distances (struct data_dependence_relation *ddr,
2656 lambda_vector dist_v, int index)
2658 /* For each outer loop where init_v is not set, the accesses are
2659 in dependence of distance 1 in the loop. */
2660 while (--index >= 0)
2662 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2663 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
2665 save_dist_v (ddr, save_v);
2669 /* Return false when fail to represent the data dependence as a
2670 distance vector. INIT_B is set to true when a component has been
2671 added to the distance vector DIST_V. INDEX_CARRY is then set to
2672 the index in DIST_V that carries the dependence. */
2675 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
2676 struct data_reference *ddr_a,
2677 struct data_reference *ddr_b,
2678 lambda_vector dist_v, bool *init_b,
2682 lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2684 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2686 tree access_fn_a, access_fn_b;
2687 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
2689 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2691 non_affine_dependence_relation (ddr);
2695 access_fn_a = DR_ACCESS_FN (ddr_a, i);
2696 access_fn_b = DR_ACCESS_FN (ddr_b, i);
2698 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
2699 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
2702 int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
2703 DDR_LOOP_NEST (ddr));
2704 int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
2705 DDR_LOOP_NEST (ddr));
2707 /* The dependence is carried by the outermost loop. Example:
2714 In this case, the dependence is carried by loop_1. */
2715 index = index_a < index_b ? index_a : index_b;
2716 *index_carry = MIN (index, *index_carry);
2718 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2720 non_affine_dependence_relation (ddr);
2724 dist = int_cst_value (SUB_DISTANCE (subscript));
2726 /* This is the subscript coupling test. If we have already
2727 recorded a distance for this loop (a distance coming from
2728 another subscript), it should be the same. For example,
2729 in the following code, there is no dependence:
2736 if (init_v[index] != 0 && dist_v[index] != dist)
2738 finalize_ddr_dependent (ddr, chrec_known);
2742 dist_v[index] = dist;
2746 else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
2748 /* This can be for example an affine vs. constant dependence
2749 (T[i] vs. T[3]) that is not an affine dependence and is
2750 not representable as a distance vector. */
2751 non_affine_dependence_relation (ddr);
2759 /* Return true when the DDR contains two data references that have the
2760 same access functions. */
2763 same_access_functions (struct data_dependence_relation *ddr)
2767 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2768 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
2769 DR_ACCESS_FN (DDR_B (ddr), i)))
2775 /* Return true when the DDR contains only constant access functions. */
2778 constant_access_functions (struct data_dependence_relation *ddr)
2782 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2783 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
2784 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
2791 /* Helper function for the case where DDR_A and DDR_B are the same
2792 multivariate access function. */
2795 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
2798 tree c_1 = CHREC_LEFT (c_2);
2799 tree c_0 = CHREC_LEFT (c_1);
2800 lambda_vector dist_v;
2803 /* Polynomials with more than 2 variables are not handled yet. */
2804 if (TREE_CODE (c_0) != INTEGER_CST)
2806 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
2810 x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
2811 x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
2813 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
2814 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2815 v1 = int_cst_value (CHREC_RIGHT (c_1));
2816 v2 = int_cst_value (CHREC_RIGHT (c_2));
2829 save_dist_v (ddr, dist_v);
2831 add_outer_distances (ddr, dist_v, x_1);
2834 /* Helper function for the case where DDR_A and DDR_B are the same
2835 access functions. */
2838 add_other_self_distances (struct data_dependence_relation *ddr)
2840 lambda_vector dist_v;
2842 int index_carry = DDR_NB_LOOPS (ddr);
2844 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2846 tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
2848 if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
2850 if (!evolution_function_is_univariate_p (access_fun))
2852 if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
2854 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
2858 add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0));
2862 index_carry = MIN (index_carry,
2863 index_in_loop_nest (CHREC_VARIABLE (access_fun),
2864 DDR_LOOP_NEST (ddr)));
2868 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2869 add_outer_distances (ddr, dist_v, index_carry);
2873 insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
2875 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2877 dist_v[DDR_INNER_LOOP (ddr)] = 1;
2878 save_dist_v (ddr, dist_v);
2881 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
2882 is the case for example when access functions are the same and
2883 equal to a constant, as in:
2890 in which case the distance vectors are (0) and (1). */
2893 add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
2897 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2899 subscript_p sub = DDR_SUBSCRIPT (ddr, i);
2900 conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
2901 conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
2903 for (j = 0; j < ca->n; j++)
2904 if (affine_function_zero_p (ca->fns[j]))
2906 insert_innermost_unit_dist_vector (ddr);
2910 for (j = 0; j < cb->n; j++)
2911 if (affine_function_zero_p (cb->fns[j]))
2913 insert_innermost_unit_dist_vector (ddr);
2919 /* Compute the classic per loop distance vector. DDR is the data
2920 dependence relation to build a vector from. Return false when fail
2921 to represent the data dependence as a distance vector. */
2924 build_classic_dist_vector (struct data_dependence_relation *ddr)
2926 bool init_b = false;
2927 int index_carry = DDR_NB_LOOPS (ddr);
2928 lambda_vector dist_v;
2930 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
2933 if (same_access_functions (ddr))
2935 /* Save the 0 vector. */
2936 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2937 save_dist_v (ddr, dist_v);
2939 if (constant_access_functions (ddr))
2940 add_distance_for_zero_overlaps (ddr);
2942 if (DDR_NB_LOOPS (ddr) > 1)
2943 add_other_self_distances (ddr);
2948 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2949 if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
2950 dist_v, &init_b, &index_carry))
2953 /* Save the distance vector if we initialized one. */
2956 /* Verify a basic constraint: classic distance vectors should
2957 always be lexicographically positive.
2959 Data references are collected in the order of execution of
2960 the program, thus for the following loop
2962 | for (i = 1; i < 100; i++)
2963 | for (j = 1; j < 100; j++)
2965 | t = T[j+1][i-1]; // A
2966 | T[j][i] = t + 2; // B
2969 references are collected following the direction of the wind:
2970 A then B. The data dependence tests are performed also
2971 following this order, such that we're looking at the distance
2972 separating the elements accessed by A from the elements later
2973 accessed by B. But in this example, the distance returned by
2974 test_dep (A, B) is lexicographically negative (-1, 1), that
2975 means that the access A occurs later than B with respect to
2976 the outer loop, ie. we're actually looking upwind. In this
2977 case we solve test_dep (B, A) looking downwind to the
2978 lexicographically positive solution, that returns the
2979 distance vector (1, -1). */
2980 if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
2982 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2983 subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
2984 compute_subscript_distance (ddr);
2985 build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
2986 save_v, &init_b, &index_carry);
2987 save_dist_v (ddr, save_v);
2989 /* In this case there is a dependence forward for all the
2992 | for (k = 1; k < 100; k++)
2993 | for (i = 1; i < 100; i++)
2994 | for (j = 1; j < 100; j++)
2996 | t = T[j+1][i-1]; // A
2997 | T[j][i] = t + 2; // B
3005 if (DDR_NB_LOOPS (ddr) > 1)
3007 add_outer_distances (ddr, save_v, index_carry);
3008 add_outer_distances (ddr, dist_v, index_carry);
3013 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3014 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3015 save_dist_v (ddr, save_v);
3017 if (DDR_NB_LOOPS (ddr) > 1)
3019 lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3021 subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
3022 compute_subscript_distance (ddr);
3023 build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3024 opposite_v, &init_b, &index_carry);
3026 add_outer_distances (ddr, dist_v, index_carry);
3027 add_outer_distances (ddr, opposite_v, index_carry);
3033 /* There is a distance of 1 on all the outer loops: Example:
3034 there is a dependence of distance 1 on loop_1 for the array A.
3040 add_outer_distances (ddr, dist_v,
3041 lambda_vector_first_nz (dist_v,
3042 DDR_NB_LOOPS (ddr), 0));
3045 if (dump_file && (dump_flags & TDF_DETAILS))
3049 fprintf (dump_file, "(build_classic_dist_vector\n");
3050 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3052 fprintf (dump_file, " dist_vector = (");
3053 print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
3054 DDR_NB_LOOPS (ddr));
3055 fprintf (dump_file, " )\n");
3057 fprintf (dump_file, ")\n");
3063 /* Return the direction for a given distance.
3064 FIXME: Computing dir this way is suboptimal, since dir can catch
3065 cases that dist is unable to represent. */
3067 static inline enum data_dependence_direction
3068 dir_from_dist (int dist)
3071 return dir_positive;
3073 return dir_negative;
3078 /* Compute the classic per loop direction vector. DDR is the data
3079 dependence relation to build a vector from. */
3082 build_classic_dir_vector (struct data_dependence_relation *ddr)
3085 lambda_vector dist_v;
3087 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
3089 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3091 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3092 dir_v[j] = dir_from_dist (dist_v[j]);
3094 save_dir_v (ddr, dir_v);
3098 /* Helper function. Returns true when there is a dependence between
3099 data references DRA and DRB. */
3102 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
3103 struct data_reference *dra,
3104 struct data_reference *drb)
3107 tree last_conflicts;
3108 struct subscript *subscript;
3110 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3113 conflict_function *overlaps_a, *overlaps_b;
3115 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
3116 DR_ACCESS_FN (drb, i),
3117 &overlaps_a, &overlaps_b,
3120 if (CF_NOT_KNOWN_P (overlaps_a)
3121 || CF_NOT_KNOWN_P (overlaps_b))
3123 finalize_ddr_dependent (ddr, chrec_dont_know);
3124 dependence_stats.num_dependence_undetermined++;
3125 free_conflict_function (overlaps_a);
3126 free_conflict_function (overlaps_b);
3130 else if (CF_NO_DEPENDENCE_P (overlaps_a)
3131 || CF_NO_DEPENDENCE_P (overlaps_b))
3133 finalize_ddr_dependent (ddr, chrec_known);
3134 dependence_stats.num_dependence_independent++;
3135 free_conflict_function (overlaps_a);
3136 free_conflict_function (overlaps_b);
3142 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3143 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3144 SUB_LAST_CONFLICT (subscript) = last_conflicts;
3151 /* Computes the conflicting iterations, and initialize DDR. */
3154 subscript_dependence_tester (struct data_dependence_relation *ddr)
3157 if (dump_file && (dump_flags & TDF_DETAILS))
3158 fprintf (dump_file, "(subscript_dependence_tester \n");
3160 if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr)))
3161 dependence_stats.num_dependence_dependent++;
3163 compute_subscript_distance (ddr);
3164 if (build_classic_dist_vector (ddr))
3165 build_classic_dir_vector (ddr);
3167 if (dump_file && (dump_flags & TDF_DETAILS))
3168 fprintf (dump_file, ")\n");
3171 /* Returns true when all the access functions of A are affine or
3175 access_functions_are_affine_or_constant_p (struct data_reference *a)
3178 VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
3181 for (i = 0; VEC_iterate (tree, fns, i, t); i++)
3182 if (!evolution_function_is_constant_p (t)
3183 && !evolution_function_is_affine_multivariate_p (t, 0))
3189 /* Initializes an equation for an OMEGA problem using the information
3190 contained in the ACCESS_FUN. Returns true when the operation
3193 PB is the omega constraint system.
3194 EQ is the number of the equation to be initialized.
3195 OFFSET is used for shifting the variables names in the constraints:
3196 a constrain is composed of 2 * the number of variables surrounding
3197 dependence accesses. OFFSET is set either to 0 for the first n variables,
3198 then it is set to n.
3199 ACCESS_FUN is expected to be an affine chrec. */
3202 init_omega_eq_with_af (omega_pb pb, unsigned eq,
3203 unsigned int offset, tree access_fun,
3204 struct data_dependence_relation *ddr)
3206 switch (TREE_CODE (access_fun))
3208 case POLYNOMIAL_CHREC:
3210 tree left = CHREC_LEFT (access_fun);
3211 tree right = CHREC_RIGHT (access_fun);
3212 int var = CHREC_VARIABLE (access_fun);
3215 if (TREE_CODE (right) != INTEGER_CST)
3218 var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
3219 pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
3221 /* Compute the innermost loop index. */
3222 DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
3225 pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
3226 += int_cst_value (right);
3228 switch (TREE_CODE (left))
3230 case POLYNOMIAL_CHREC:
3231 return init_omega_eq_with_af (pb, eq, offset, left, ddr);
3234 pb->eqs[eq].coef[0] += int_cst_value (left);
3243 pb->eqs[eq].coef[0] += int_cst_value (access_fun);
3251 /* As explained in the comments preceding init_omega_for_ddr, we have
3252 to set up a system for each loop level, setting outer loops
3253 variation to zero, and current loop variation to positive or zero.
3254 Save each lexico positive distance vector. */
3257 omega_extract_distance_vectors (omega_pb pb,
3258 struct data_dependence_relation *ddr)
3262 struct loop *loopi, *loopj;
3263 enum omega_result res;
3265 /* Set a new problem for each loop in the nest. The basis is the
3266 problem that we have initialized until now. On top of this we
3267 add new constraints. */
3268 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3269 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3272 omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
3273 DDR_NB_LOOPS (ddr));
3275 omega_copy_problem (copy, pb);
3277 /* For all the outer loops "loop_j", add "dj = 0". */
3279 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3281 eq = omega_add_zero_eq (copy, omega_black);
3282 copy->eqs[eq].coef[j + 1] = 1;
3285 /* For "loop_i", add "0 <= di". */
3286 geq = omega_add_zero_geq (copy, omega_black);
3287 copy->geqs[geq].coef[i + 1] = 1;
3289 /* Reduce the constraint system, and test that the current
3290 problem is feasible. */
3291 res = omega_simplify_problem (copy);
3292 if (res == omega_false
3293 || res == omega_unknown
3294 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3297 for (eq = 0; eq < copy->num_subs; eq++)
3298 if (copy->subs[eq].key == (int) i + 1)
3300 dist = copy->subs[eq].coef[0];
3306 /* Reinitialize problem... */
3307 omega_copy_problem (copy, pb);
3309 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3311 eq = omega_add_zero_eq (copy, omega_black);
3312 copy->eqs[eq].coef[j + 1] = 1;
3315 /* ..., but this time "di = 1". */
3316 eq = omega_add_zero_eq (copy, omega_black);
3317 copy->eqs[eq].coef[i + 1] = 1;
3318 copy->eqs[eq].coef[0] = -1;
3320 res = omega_simplify_problem (copy);
3321 if (res == omega_false
3322 || res == omega_unknown
3323 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3326 for (eq = 0; eq < copy->num_subs; eq++)
3327 if (copy->subs[eq].key == (int) i + 1)
3329 dist = copy->subs[eq].coef[0];
3335 /* Save the lexicographically positive distance vector. */
3338 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3339 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3343 for (eq = 0; eq < copy->num_subs; eq++)
3344 if (copy->subs[eq].key > 0)
3346 dist = copy->subs[eq].coef[0];
3347 dist_v[copy->subs[eq].key - 1] = dist;
3350 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3351 dir_v[j] = dir_from_dist (dist_v[j]);
3353 save_dist_v (ddr, dist_v);
3354 save_dir_v (ddr, dir_v);
3358 omega_free_problem (copy);
3362 /* This is called for each subscript of a tuple of data references:
3363 insert an equality for representing the conflicts. */
3366 omega_setup_subscript (tree access_fun_a, tree access_fun_b,
3367 struct data_dependence_relation *ddr,
3368 omega_pb pb, bool *maybe_dependent)
3371 tree fun_a = chrec_convert (integer_type_node, access_fun_a, NULL_TREE);
3372 tree fun_b = chrec_convert (integer_type_node, access_fun_b, NULL_TREE);
3373 tree difference = chrec_fold_minus (integer_type_node, fun_a, fun_b);
3375 /* When the fun_a - fun_b is not constant, the dependence is not
3376 captured by the classic distance vector representation. */
3377 if (TREE_CODE (difference) != INTEGER_CST)
3381 if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
3383 /* There is no dependence. */
3384 *maybe_dependent = false;
3388 fun_b = chrec_fold_multiply (integer_type_node, fun_b,
3389 integer_minus_one_node);
3391 eq = omega_add_zero_eq (pb, omega_black);
3392 if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
3393 || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
3394 /* There is probably a dependence, but the system of
3395 constraints cannot be built: answer "don't know". */
3399 if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
3400 && !int_divides_p (lambda_vector_gcd
3401 ((lambda_vector) &(pb->eqs[eq].coef[1]),
3402 2 * DDR_NB_LOOPS (ddr)),
3403 pb->eqs[eq].coef[0]))
3405 /* There is no dependence. */
3406 *maybe_dependent = false;
3413 /* Helper function, same as init_omega_for_ddr but specialized for
3414 data references A and B. */
3417 init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
3418 struct data_dependence_relation *ddr,
3419 omega_pb pb, bool *maybe_dependent)
3424 unsigned nb_loops = DDR_NB_LOOPS (ddr);
3426 /* Insert an equality per subscript. */
3427 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3429 if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
3430 ddr, pb, maybe_dependent))
3432 else if (*maybe_dependent == false)
3434 /* There is no dependence. */
3435 DDR_ARE_DEPENDENT (ddr) = chrec_known;
3440 /* Insert inequalities: constraints corresponding to the iteration
3441 domain, i.e. the loops surrounding the references "loop_x" and
3442 the distance variables "dx". The layout of the OMEGA
3443 representation is as follows:
3444 - coef[0] is the constant
3445 - coef[1..nb_loops] are the protected variables that will not be
3446 removed by the solver: the "dx"
3447 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3449 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3450 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3452 HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, true);
3455 ineq = omega_add_zero_geq (pb, omega_black);
3456 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3458 /* 0 <= loop_x + dx */
3459 ineq = omega_add_zero_geq (pb, omega_black);
3460 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3461 pb->geqs[ineq].coef[i + 1] = 1;
3465 /* loop_x <= nb_iters */
3466 ineq = omega_add_zero_geq (pb, omega_black);
3467 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3468 pb->geqs[ineq].coef[0] = nbi;
3470 /* loop_x + dx <= nb_iters */
3471 ineq = omega_add_zero_geq (pb, omega_black);
3472 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3473 pb->geqs[ineq].coef[i + 1] = -1;
3474 pb->geqs[ineq].coef[0] = nbi;
3476 /* A step "dx" bigger than nb_iters is not feasible, so
3477 add "0 <= nb_iters + dx", */
3478 ineq = omega_add_zero_geq (pb, omega_black);
3479 pb->geqs[ineq].coef[i + 1] = 1;
3480 pb->geqs[ineq].coef[0] = nbi;
3481 /* and "dx <= nb_iters". */
3482 ineq = omega_add_zero_geq (pb, omega_black);
3483 pb->geqs[ineq].coef[i + 1] = -1;
3484 pb->geqs[ineq].coef[0] = nbi;
3488 omega_extract_distance_vectors (pb, ddr);
3493 /* Sets up the Omega dependence problem for the data dependence
3494 relation DDR. Returns false when the constraint system cannot be
3495 built, ie. when the test answers "don't know". Returns true
3496 otherwise, and when independence has been proved (using one of the
3497 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3498 set MAYBE_DEPENDENT to true.
3500 Example: for setting up the dependence system corresponding to the
3501 conflicting accesses
3506 | ... A[2*j, 2*(i + j)]
3510 the following constraints come from the iteration domain:
3517 where di, dj are the distance variables. The constraints
3518 representing the conflicting elements are:
3521 i + 1 = 2 * (i + di + j + dj)
3523 For asking that the resulting distance vector (di, dj) be
3524 lexicographically positive, we insert the constraint "di >= 0". If
3525 "di = 0" in the solution, we fix that component to zero, and we
3526 look at the inner loops: we set a new problem where all the outer
3527 loop distances are zero, and fix this inner component to be
3528 positive. When one of the components is positive, we save that
3529 distance, and set a new problem where the distance on this loop is
3530 zero, searching for other distances in the inner loops. Here is
3531 the classic example that illustrates that we have to set for each
3532 inner loop a new problem:
3540 we have to save two distances (1, 0) and (0, 1).
3542 Given two array references, refA and refB, we have to set the
3543 dependence problem twice, refA vs. refB and refB vs. refA, and we
3544 cannot do a single test, as refB might occur before refA in the
3545 inner loops, and the contrary when considering outer loops: ex.
3550 | T[{1,+,1}_2][{1,+,1}_1] // refA
3551 | T[{2,+,1}_2][{0,+,1}_1] // refB
3556 refB touches the elements in T before refA, and thus for the same
3557 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3558 but for successive loop_0 iterations, we have (1, -1, 1)
3560 The Omega solver expects the distance variables ("di" in the
3561 previous example) to come first in the constraint system (as
3562 variables to be protected, or "safe" variables), the constraint
3563 system is built using the following layout:
3565 "cst | distance vars | index vars".
3569 init_omega_for_ddr (struct data_dependence_relation *ddr,
3570 bool *maybe_dependent)
3575 *maybe_dependent = true;
3577 if (same_access_functions (ddr))
3580 lambda_vector dir_v;
3582 /* Save the 0 vector. */
3583 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3584 dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3585 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3586 dir_v[j] = dir_equal;
3587 save_dir_v (ddr, dir_v);
3589 /* Save the dependences carried by outer loops. */
3590 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3591 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3593 omega_free_problem (pb);
3597 /* Omega expects the protected variables (those that have to be kept
3598 after elimination) to appear first in the constraint system.
3599 These variables are the distance variables. In the following
3600 initialization we declare NB_LOOPS safe variables, and the total
3601 number of variables for the constraint system is 2*NB_LOOPS. */
3602 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3603 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3605 omega_free_problem (pb);
3607 /* Stop computation if not decidable, or no dependence. */
3608 if (res == false || *maybe_dependent == false)
3611 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3612 res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
3614 omega_free_problem (pb);
3619 /* Return true when DDR contains the same information as that stored
3620 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
3623 ddr_consistent_p (FILE *file,
3624 struct data_dependence_relation *ddr,
3625 VEC (lambda_vector, heap) *dist_vects,
3626 VEC (lambda_vector, heap) *dir_vects)
3630 /* If dump_file is set, output there. */
3631 if (dump_file && (dump_flags & TDF_DETAILS))
3634 if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
3636 lambda_vector b_dist_v;
3637 fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3638 VEC_length (lambda_vector, dist_vects),
3639 DDR_NUM_DIST_VECTS (ddr));
3641 fprintf (file, "Banerjee dist vectors:\n");
3642 for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++)
3643 print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
3645 fprintf (file, "Omega dist vectors:\n");
3646 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3647 print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
3649 fprintf (file, "data dependence relation:\n");
3650 dump_data_dependence_relation (file, ddr);
3652 fprintf (file, ")\n");
3656 if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
3658 fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3659 VEC_length (lambda_vector, dir_vects),
3660 DDR_NUM_DIR_VECTS (ddr));
3664 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3666 lambda_vector a_dist_v;
3667 lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
3669 /* Distance vectors are not ordered in the same way in the DDR
3670 and in the DIST_VECTS: search for a matching vector. */
3671 for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, a_dist_v); j++)
3672 if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
3675 if (j == VEC_length (lambda_vector, dist_vects))
3677 fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
3678 print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
3679 fprintf (file, "not found in Omega dist vectors:\n");
3680 print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
3681 fprintf (file, "data dependence relation:\n");
3682 dump_data_dependence_relation (file, ddr);
3683 fprintf (file, ")\n");
3687 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
3689 lambda_vector a_dir_v;
3690 lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
3692 /* Direction vectors are not ordered in the same way in the DDR
3693 and in the DIR_VECTS: search for a matching vector. */
3694 for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, a_dir_v); j++)
3695 if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
3698 if (j == VEC_length (lambda_vector, dist_vects))
3700 fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
3701 print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
3702 fprintf (file, "not found in Omega dir vectors:\n");
3703 print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
3704 fprintf (file, "data dependence relation:\n");
3705 dump_data_dependence_relation (file, ddr);
3706 fprintf (file, ")\n");
3713 /* This computes the affine dependence relation between A and B.
3714 CHREC_KNOWN is used for representing the independence between two
3715 accesses, while CHREC_DONT_KNOW is used for representing the unknown
3718 Note that it is possible to stop the computation of the dependence
3719 relation the first time we detect a CHREC_KNOWN element for a given
3723 compute_affine_dependence (struct data_dependence_relation *ddr)
3725 struct data_reference *dra = DDR_A (ddr);
3726 struct data_reference *drb = DDR_B (ddr);
3728 if (dump_file && (dump_flags & TDF_DETAILS))
3730 fprintf (dump_file, "(compute_affine_dependence\n");
3731 fprintf (dump_file, " (stmt_a = \n");
3732 print_generic_expr (dump_file, DR_STMT (dra), 0);
3733 fprintf (dump_file, ")\n (stmt_b = \n");
3734 print_generic_expr (dump_file, DR_STMT (drb), 0);
3735 fprintf (dump_file, ")\n");
3738 /* Analyze only when the dependence relation is not yet known. */
3739 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3741 dependence_stats.num_dependence_tests++;
3743 if (access_functions_are_affine_or_constant_p (dra)
3744 && access_functions_are_affine_or_constant_p (drb))
3746 if (flag_check_data_deps)
3748 /* Compute the dependences using the first algorithm. */
3749 subscript_dependence_tester (ddr);
3751 if (dump_file && (dump_flags & TDF_DETAILS))
3753 fprintf (dump_file, "\n\nBanerjee Analyzer\n");
3754 dump_data_dependence_relation (dump_file, ddr);
3757 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3759 bool maybe_dependent;
3760 VEC (lambda_vector, heap) *dir_vects, *dist_vects;
3762 /* Save the result of the first DD analyzer. */
3763 dist_vects = DDR_DIST_VECTS (ddr);
3764 dir_vects = DDR_DIR_VECTS (ddr);
3766 /* Reset the information. */
3767 DDR_DIST_VECTS (ddr) = NULL;
3768 DDR_DIR_VECTS (ddr) = NULL;
3770 /* Compute the same information using Omega. */
3771 if (!init_omega_for_ddr (ddr, &maybe_dependent))
3772 goto csys_dont_know;
3774 if (dump_file && (dump_flags & TDF_DETAILS))
3776 fprintf (dump_file, "Omega Analyzer\n");
3777 dump_data_dependence_relation (dump_file, ddr);
3780 /* Check that we get the same information. */
3781 if (maybe_dependent)
3782 gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
3787 subscript_dependence_tester (ddr);
3790 /* As a last case, if the dependence cannot be determined, or if
3791 the dependence is considered too difficult to determine, answer
3796 dependence_stats.num_dependence_undetermined++;
3798 if (dump_file && (dump_flags & TDF_DETAILS))
3800 fprintf (dump_file, "Data ref a:\n");
3801 dump_data_reference (dump_file, dra);
3802 fprintf (dump_file, "Data ref b:\n");
3803 dump_data_reference (dump_file, drb);
3804 fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
3806 finalize_ddr_dependent (ddr, chrec_dont_know);
3810 if (dump_file && (dump_flags & TDF_DETAILS))
3811 fprintf (dump_file, ")\n");
3814 /* This computes the dependence relation for the same data
3815 reference into DDR. */
3818 compute_self_dependence (struct data_dependence_relation *ddr)
3821 struct subscript *subscript;
3823 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3826 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3829 /* The accessed index overlaps for each iteration. */
3830 SUB_CONFLICTS_IN_A (subscript)
3831 = conflict_fn (1, affine_fn_cst (integer_zero_node));
3832 SUB_CONFLICTS_IN_B (subscript)
3833 = conflict_fn (1, affine_fn_cst (integer_zero_node));
3834 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3837 /* The distance vector is the zero vector. */
3838 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3839 save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3842 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3843 the data references in DATAREFS, in the LOOP_NEST. When
3844 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3848 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
3849 VEC (ddr_p, heap) **dependence_relations,
3850 VEC (loop_p, heap) *loop_nest,
3851 bool compute_self_and_rr)
3853 struct data_dependence_relation *ddr;
3854 struct data_reference *a, *b;
3857 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
3858 for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
3859 if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
3861 ddr = initialize_data_dependence_relation (a, b, loop_nest);
3862 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3863 compute_affine_dependence (ddr);
3866 if (compute_self_and_rr)
3867 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
3869 ddr = initialize_data_dependence_relation (a, a, loop_nest);
3870 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3871 compute_self_dependence (ddr);
3875 /* Stores the locations of memory references in STMT to REFERENCES. Returns
3876 true if STMT clobbers memory, false otherwise. */
3879 get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references)
3881 bool clobbers_memory = false;
3883 tree *op0, *op1, call;
3887 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
3888 Calls have side-effects, except those to const or pure
3890 call = get_call_expr_in (stmt);
3892 && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE)))
3893 || (TREE_CODE (stmt) == ASM_EXPR
3894 && ASM_VOLATILE_P (stmt)))
3895 clobbers_memory = true;
3897 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3898 return clobbers_memory;
3900 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
3902 op0 = &GIMPLE_STMT_OPERAND (stmt, 0);
3903 op1 = &GIMPLE_STMT_OPERAND (stmt, 1);
3906 || REFERENCE_CLASS_P (*op1))
3908 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
3910 ref->is_read = true;
3914 || REFERENCE_CLASS_P (*op0))
3916 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
3918 ref->is_read = false;
3924 unsigned i, n = call_expr_nargs (call);
3926 for (i = 0; i < n; i++)
3928 op0 = &CALL_EXPR_ARG (call, i);
3931 || REFERENCE_CLASS_P (*op0))
3933 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
3935 ref->is_read = true;
3940 return clobbers_memory;
3943 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
3944 reference, returns false, otherwise returns true. NEST is the outermost
3945 loop of the loop nest in that the references should be analysed. */
3948 find_data_references_in_stmt (struct loop *nest, tree stmt,
3949 VEC (data_reference_p, heap) **datarefs)
3952 VEC (data_ref_loc, heap) *references;
3955 data_reference_p dr;
3957 if (get_references_in_stmt (stmt, &references))
3959 VEC_free (data_ref_loc, heap, references);
3963 for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
3965 dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
3966 gcc_assert (dr != NULL);
3968 /* FIXME -- data dependence analysis does not work correctly for objects with
3969 invariant addresses. Let us fail here until the problem is fixed. */
3970 if (dr_address_invariant_p (dr))
3973 if (dump_file && (dump_flags & TDF_DETAILS))
3974 fprintf (dump_file, "\tFAILED as dr address is invariant\n");
3979 VEC_safe_push (data_reference_p, heap, *datarefs, dr);
3981 VEC_free (data_ref_loc, heap, references);
3985 /* Search the data references in LOOP, and record the information into
3986 DATAREFS. Returns chrec_dont_know when failing to analyze a
3987 difficult case, returns NULL_TREE otherwise.
3989 TODO: This function should be made smarter so that it can handle address
3990 arithmetic as if they were array accesses, etc. */
3993 find_data_references_in_loop (struct loop *loop,
3994 VEC (data_reference_p, heap) **datarefs)
3996 basic_block bb, *bbs;
3998 block_stmt_iterator bsi;
4000 bbs = get_loop_body_in_dom_order (loop);
4002 for (i = 0; i < loop->num_nodes; i++)
4006 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4008 tree stmt = bsi_stmt (bsi);
4010 if (!find_data_references_in_stmt (loop, stmt, datarefs))
4012 struct data_reference *res;
4013 res = XCNEW (struct data_reference);
4014 VEC_safe_push (data_reference_p, heap, *datarefs, res);
4017 return chrec_dont_know;
4026 /* Recursive helper function. */
4029 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4031 /* Inner loops of the nest should not contain siblings. Example:
4032 when there are two consecutive loops,
4043 the dependence relation cannot be captured by the distance
4048 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4050 return find_loop_nest_1 (loop->inner, loop_nest);
4054 /* Return false when the LOOP is not well nested. Otherwise return
4055 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4056 contain the loops from the outermost to the innermost, as they will
4057 appear in the classic distance vector. */
4060 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4062 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4064 return find_loop_nest_1 (loop->inner, loop_nest);
4068 /* Given a loop nest LOOP, the following vectors are returned:
4069 DATAREFS is initialized to all the array elements contained in this loop,
4070 DEPENDENCE_RELATIONS contains the relations between the data references.
4071 Compute read-read and self relations if
4072 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4075 compute_data_dependences_for_loop (struct loop *loop,
4076 bool compute_self_and_read_read_dependences,
4077 VEC (data_reference_p, heap) **datarefs,
4078 VEC (ddr_p, heap) **dependence_relations)
4080 VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
4082 memset (&dependence_stats, 0, sizeof (dependence_stats));
4084 /* If the loop nest is not well formed, or one of the data references
4085 is not computable, give up without spending time to compute other
4088 || !find_loop_nest (loop, &vloops)
4089 || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
4091 struct data_dependence_relation *ddr;
4093 /* Insert a single relation into dependence_relations:
4095 ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
4096 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4099 compute_all_dependences (*datarefs, dependence_relations, vloops,
4100 compute_self_and_read_read_dependences);
4102 if (dump_file && (dump_flags & TDF_STATS))
4104 fprintf (dump_file, "Dependence tester statistics:\n");
4106 fprintf (dump_file, "Number of dependence tests: %d\n",
4107 dependence_stats.num_dependence_tests);
4108 fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4109 dependence_stats.num_dependence_dependent);
4110 fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4111 dependence_stats.num_dependence_independent);
4112 fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4113 dependence_stats.num_dependence_undetermined);
4115 fprintf (dump_file, "Number of subscript tests: %d\n",
4116 dependence_stats.num_subscript_tests);
4117 fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4118 dependence_stats.num_subscript_undetermined);
4119 fprintf (dump_file, "Number of same subscript function: %d\n",
4120 dependence_stats.num_same_subscript_function);
4122 fprintf (dump_file, "Number of ziv tests: %d\n",
4123 dependence_stats.num_ziv);
4124 fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4125 dependence_stats.num_ziv_dependent);
4126 fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4127 dependence_stats.num_ziv_independent);
4128 fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4129 dependence_stats.num_ziv_unimplemented);
4131 fprintf (dump_file, "Number of siv tests: %d\n",
4132 dependence_stats.num_siv);
4133 fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4134 dependence_stats.num_siv_dependent);
4135 fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4136 dependence_stats.num_siv_independent);
4137 fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4138 dependence_stats.num_siv_unimplemented);
4140 fprintf (dump_file, "Number of miv tests: %d\n",
4141 dependence_stats.num_miv);
4142 fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4143 dependence_stats.num_miv_dependent);
4144 fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4145 dependence_stats.num_miv_independent);
4146 fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4147 dependence_stats.num_miv_unimplemented);
4151 /* Entry point (for testing only). Analyze all the data references
4152 and the dependence relations in LOOP.
4154 The data references are computed first.
4156 A relation on these nodes is represented by a complete graph. Some
4157 of the relations could be of no interest, thus the relations can be
4160 In the following function we compute all the relations. This is
4161 just a first implementation that is here for:
4162 - for showing how to ask for the dependence relations,
4163 - for the debugging the whole dependence graph,
4164 - for the dejagnu testcases and maintenance.
4166 It is possible to ask only for a part of the graph, avoiding to
4167 compute the whole dependence graph. The computed dependences are
4168 stored in a knowledge base (KB) such that later queries don't
4169 recompute the same information. The implementation of this KB is
4170 transparent to the optimizer, and thus the KB can be changed with a
4171 more efficient implementation, or the KB could be disabled. */
4173 analyze_all_data_dependences (struct loop *loop)
4176 int nb_data_refs = 10;
4177 VEC (data_reference_p, heap) *datarefs =
4178 VEC_alloc (data_reference_p, heap, nb_data_refs);
4179 VEC (ddr_p, heap) *dependence_relations =
4180 VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
4182 /* Compute DDs on the whole function. */
4183 compute_data_dependences_for_loop (loop, false, &datarefs,
4184 &dependence_relations);
4188 dump_data_dependence_relations (dump_file, dependence_relations);
4189 fprintf (dump_file, "\n\n");
4191 if (dump_flags & TDF_DETAILS)
4192 dump_dist_dir_vectors (dump_file, dependence_relations);
4194 if (dump_flags & TDF_STATS)
4196 unsigned nb_top_relations = 0;
4197 unsigned nb_bot_relations = 0;
4198 unsigned nb_basename_differ = 0;
4199 unsigned nb_chrec_relations = 0;
4200 struct data_dependence_relation *ddr;
4202 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4204 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4207 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4209 struct data_reference *a = DDR_A (ddr);
4210 struct data_reference *b = DDR_B (ddr);
4212 if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
4213 nb_basename_differ++;
4219 nb_chrec_relations++;
4222 gather_stats_on_scev_database ();
4226 free_dependence_relations (dependence_relations);
4227 free_data_refs (datarefs);
4230 /* Computes all the data dependences and check that the results of
4231 several analyzers are the same. */
4234 tree_check_data_deps (void)
4237 struct loop *loop_nest;
4239 FOR_EACH_LOOP (li, loop_nest, 0)
4240 analyze_all_data_dependences (loop_nest);
4243 /* Free the memory used by a data dependence relation DDR. */
4246 free_dependence_relation (struct data_dependence_relation *ddr)
4251 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
4252 free_subscripts (DDR_SUBSCRIPTS (ddr));
4257 /* Free the memory used by the data dependence relations from
4258 DEPENDENCE_RELATIONS. */
4261 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
4264 struct data_dependence_relation *ddr;
4265 VEC (loop_p, heap) *loop_nest = NULL;
4267 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4271 if (loop_nest == NULL)
4272 loop_nest = DDR_LOOP_NEST (ddr);
4274 gcc_assert (DDR_LOOP_NEST (ddr) == NULL
4275 || DDR_LOOP_NEST (ddr) == loop_nest);
4276 free_dependence_relation (ddr);
4280 VEC_free (loop_p, heap, loop_nest);
4281 VEC_free (ddr_p, heap, dependence_relations);
4284 /* Free the memory used by the data references from DATAREFS. */
4287 free_data_refs (VEC (data_reference_p, heap) *datarefs)
4290 struct data_reference *dr;
4292 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
4294 VEC_free (data_reference_p, heap, datarefs);