1 /* Data references and dependences detectors.
2 Copyright (C) 2003-2015 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 3, 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 COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass walks a given loop structure searching for array
22 references. The information about the array accesses is recorded
23 in DATA_REFERENCE structures.
25 The basic test for determining the dependences is:
26 given two access functions chrec1 and chrec2 to a same array, and
27 x and y two vectors from the iteration domain, the same element of
28 the array is accessed twice at iterations x and y if and only if:
29 | chrec1 (x) == chrec2 (y).
31 The goals of this analysis are:
33 - to determine the independence: the relation between two
34 independent accesses is qualified with the chrec_known (this
35 information allows a loop parallelization),
37 - when two data references access the same data, to qualify the
38 dependence relation with classic dependence representations:
42 - loop carried level dependence
43 - polyhedron dependence
44 or with the chains of recurrences based representation,
46 - to define a knowledge base for storing the data dependence
49 - to define an interface to access this data.
54 - subscript: given two array accesses a subscript is the tuple
55 composed of the access functions for a given dimension. Example:
56 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
57 (f1, g1), (f2, g2), (f3, g3).
59 - Diophantine equation: an equation whose coefficients and
60 solutions are integer constants, for example the equation
62 has an integer solution x = 1 and y = -1.
66 - "Advanced Compilation for High Performance Computing" by Randy
67 Allen and Ken Kennedy.
68 http://citeseer.ist.psu.edu/goff91practical.html
70 - "Loop Transformations for Restructuring Compilers - The Foundations"
78 #include "coretypes.h"
82 #include "double-int.h"
90 #include "fold-const.h"
93 #include "hard-reg-set.h"
97 #include "statistics.h"
99 #include "fixed-value.h"
100 #include "insn-config.h"
105 #include "emit-rtl.h"
109 #include "gimple-pretty-print.h"
111 #include "dominance.h"
113 #include "basic-block.h"
114 #include "tree-ssa-alias.h"
115 #include "internal-fn.h"
116 #include "gimple-expr.h"
119 #include "gimple-iterator.h"
120 #include "tree-ssa-loop-niter.h"
121 #include "tree-ssa-loop.h"
122 #include "tree-ssa.h"
124 #include "tree-data-ref.h"
125 #include "tree-scalar-evolution.h"
126 #include "dumpfile.h"
127 #include "langhooks.h"
128 #include "tree-affine.h"
131 static struct datadep_stats
133 int num_dependence_tests;
134 int num_dependence_dependent;
135 int num_dependence_independent;
136 int num_dependence_undetermined;
138 int num_subscript_tests;
139 int num_subscript_undetermined;
140 int num_same_subscript_function;
143 int num_ziv_independent;
144 int num_ziv_dependent;
145 int num_ziv_unimplemented;
148 int num_siv_independent;
149 int num_siv_dependent;
150 int num_siv_unimplemented;
153 int num_miv_independent;
154 int num_miv_dependent;
155 int num_miv_unimplemented;
158 static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
159 struct data_reference *,
160 struct data_reference *,
162 /* Returns true iff A divides B. */
165 tree_fold_divides_p (const_tree a, const_tree b)
167 gcc_assert (TREE_CODE (a) == INTEGER_CST);
168 gcc_assert (TREE_CODE (b) == INTEGER_CST);
169 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a));
172 /* Returns true iff A divides B. */
175 int_divides_p (int a, int b)
177 return ((b % a) == 0);
182 /* Dump into FILE all the data references from DATAREFS. */
185 dump_data_references (FILE *file, vec<data_reference_p> datarefs)
188 struct data_reference *dr;
190 FOR_EACH_VEC_ELT (datarefs, i, dr)
191 dump_data_reference (file, dr);
194 /* Unified dump into FILE all the data references from DATAREFS. */
197 debug (vec<data_reference_p> &ref)
199 dump_data_references (stderr, ref);
203 debug (vec<data_reference_p> *ptr)
208 fprintf (stderr, "<nil>\n");
212 /* Dump into STDERR all the data references from DATAREFS. */
215 debug_data_references (vec<data_reference_p> datarefs)
217 dump_data_references (stderr, datarefs);
220 /* Print to STDERR the data_reference DR. */
223 debug_data_reference (struct data_reference *dr)
225 dump_data_reference (stderr, dr);
228 /* Dump function for a DATA_REFERENCE structure. */
231 dump_data_reference (FILE *outf,
232 struct data_reference *dr)
236 fprintf (outf, "#(Data Ref: \n");
237 fprintf (outf, "# bb: %d \n", gimple_bb (DR_STMT (dr))->index);
238 fprintf (outf, "# stmt: ");
239 print_gimple_stmt (outf, DR_STMT (dr), 0, 0);
240 fprintf (outf, "# ref: ");
241 print_generic_stmt (outf, DR_REF (dr), 0);
242 fprintf (outf, "# base_object: ");
243 print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
245 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
247 fprintf (outf, "# Access function %d: ", i);
248 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
250 fprintf (outf, "#)\n");
253 /* Unified dump function for a DATA_REFERENCE structure. */
256 debug (data_reference &ref)
258 dump_data_reference (stderr, &ref);
262 debug (data_reference *ptr)
267 fprintf (stderr, "<nil>\n");
271 /* Dumps the affine function described by FN to the file OUTF. */
274 dump_affine_function (FILE *outf, affine_fn fn)
279 print_generic_expr (outf, fn[0], TDF_SLIM);
280 for (i = 1; fn.iterate (i, &coef); i++)
282 fprintf (outf, " + ");
283 print_generic_expr (outf, coef, TDF_SLIM);
284 fprintf (outf, " * x_%u", i);
288 /* Dumps the conflict function CF to the file OUTF. */
291 dump_conflict_function (FILE *outf, conflict_function *cf)
295 if (cf->n == NO_DEPENDENCE)
296 fprintf (outf, "no dependence");
297 else if (cf->n == NOT_KNOWN)
298 fprintf (outf, "not known");
301 for (i = 0; i < cf->n; i++)
306 dump_affine_function (outf, cf->fns[i]);
312 /* Dump function for a SUBSCRIPT structure. */
315 dump_subscript (FILE *outf, struct subscript *subscript)
317 conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
319 fprintf (outf, "\n (subscript \n");
320 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
321 dump_conflict_function (outf, cf);
322 if (CF_NONTRIVIAL_P (cf))
324 tree last_iteration = SUB_LAST_CONFLICT (subscript);
325 fprintf (outf, "\n last_conflict: ");
326 print_generic_expr (outf, last_iteration, 0);
329 cf = SUB_CONFLICTS_IN_B (subscript);
330 fprintf (outf, "\n iterations_that_access_an_element_twice_in_B: ");
331 dump_conflict_function (outf, cf);
332 if (CF_NONTRIVIAL_P (cf))
334 tree last_iteration = SUB_LAST_CONFLICT (subscript);
335 fprintf (outf, "\n last_conflict: ");
336 print_generic_expr (outf, last_iteration, 0);
339 fprintf (outf, "\n (Subscript distance: ");
340 print_generic_expr (outf, SUB_DISTANCE (subscript), 0);
341 fprintf (outf, " ))\n");
344 /* Print the classic direction vector DIRV to OUTF. */
347 print_direction_vector (FILE *outf,
353 for (eq = 0; eq < length; eq++)
355 enum data_dependence_direction dir = ((enum data_dependence_direction)
361 fprintf (outf, " +");
364 fprintf (outf, " -");
367 fprintf (outf, " =");
369 case dir_positive_or_equal:
370 fprintf (outf, " +=");
372 case dir_positive_or_negative:
373 fprintf (outf, " +-");
375 case dir_negative_or_equal:
376 fprintf (outf, " -=");
379 fprintf (outf, " *");
382 fprintf (outf, "indep");
386 fprintf (outf, "\n");
389 /* Print a vector of direction vectors. */
392 print_dir_vectors (FILE *outf, vec<lambda_vector> dir_vects,
398 FOR_EACH_VEC_ELT (dir_vects, j, v)
399 print_direction_vector (outf, v, length);
402 /* Print out a vector VEC of length N to OUTFILE. */
405 print_lambda_vector (FILE * outfile, lambda_vector vector, int n)
409 for (i = 0; i < n; i++)
410 fprintf (outfile, "%3d ", vector[i]);
411 fprintf (outfile, "\n");
414 /* Print a vector of distance vectors. */
417 print_dist_vectors (FILE *outf, vec<lambda_vector> dist_vects,
423 FOR_EACH_VEC_ELT (dist_vects, j, v)
424 print_lambda_vector (outf, v, length);
427 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
430 dump_data_dependence_relation (FILE *outf,
431 struct data_dependence_relation *ddr)
433 struct data_reference *dra, *drb;
435 fprintf (outf, "(Data Dep: \n");
437 if (!ddr || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
444 dump_data_reference (outf, dra);
446 fprintf (outf, " (nil)\n");
448 dump_data_reference (outf, drb);
450 fprintf (outf, " (nil)\n");
452 fprintf (outf, " (don't know)\n)\n");
458 dump_data_reference (outf, dra);
459 dump_data_reference (outf, drb);
461 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
462 fprintf (outf, " (no dependence)\n");
464 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
469 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
471 fprintf (outf, " access_fn_A: ");
472 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
473 fprintf (outf, " access_fn_B: ");
474 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
475 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
478 fprintf (outf, " inner loop index: %d\n", DDR_INNER_LOOP (ddr));
479 fprintf (outf, " loop nest: (");
480 FOR_EACH_VEC_ELT (DDR_LOOP_NEST (ddr), i, loopi)
481 fprintf (outf, "%d ", loopi->num);
482 fprintf (outf, ")\n");
484 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
486 fprintf (outf, " distance_vector: ");
487 print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
491 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
493 fprintf (outf, " direction_vector: ");
494 print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
499 fprintf (outf, ")\n");
505 debug_data_dependence_relation (struct data_dependence_relation *ddr)
507 dump_data_dependence_relation (stderr, ddr);
510 /* Dump into FILE all the dependence relations from DDRS. */
513 dump_data_dependence_relations (FILE *file,
517 struct data_dependence_relation *ddr;
519 FOR_EACH_VEC_ELT (ddrs, i, ddr)
520 dump_data_dependence_relation (file, ddr);
524 debug (vec<ddr_p> &ref)
526 dump_data_dependence_relations (stderr, ref);
530 debug (vec<ddr_p> *ptr)
535 fprintf (stderr, "<nil>\n");
539 /* Dump to STDERR all the dependence relations from DDRS. */
542 debug_data_dependence_relations (vec<ddr_p> ddrs)
544 dump_data_dependence_relations (stderr, ddrs);
547 /* Dumps the distance and direction vectors in FILE. DDRS contains
548 the dependence relations, and VECT_SIZE is the size of the
549 dependence vectors, or in other words the number of loops in the
553 dump_dist_dir_vectors (FILE *file, vec<ddr_p> ddrs)
556 struct data_dependence_relation *ddr;
559 FOR_EACH_VEC_ELT (ddrs, i, ddr)
560 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
562 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), j, v)
564 fprintf (file, "DISTANCE_V (");
565 print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
566 fprintf (file, ")\n");
569 FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr), j, v)
571 fprintf (file, "DIRECTION_V (");
572 print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
573 fprintf (file, ")\n");
577 fprintf (file, "\n\n");
580 /* Dumps the data dependence relations DDRS in FILE. */
583 dump_ddrs (FILE *file, vec<ddr_p> ddrs)
586 struct data_dependence_relation *ddr;
588 FOR_EACH_VEC_ELT (ddrs, i, ddr)
589 dump_data_dependence_relation (file, ddr);
591 fprintf (file, "\n\n");
595 debug_ddrs (vec<ddr_p> ddrs)
597 dump_ddrs (stderr, ddrs);
600 /* Helper function for split_constant_offset. Expresses OP0 CODE OP1
601 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
602 constant of type ssizetype, and returns true. If we cannot do this
603 with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
607 split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
608 tree *var, tree *off)
612 enum tree_code ocode = code;
620 *var = build_int_cst (type, 0);
621 *off = fold_convert (ssizetype, op0);
624 case POINTER_PLUS_EXPR:
629 split_constant_offset (op0, &var0, &off0);
630 split_constant_offset (op1, &var1, &off1);
631 *var = fold_build2 (code, type, var0, var1);
632 *off = size_binop (ocode, off0, off1);
636 if (TREE_CODE (op1) != INTEGER_CST)
639 split_constant_offset (op0, &var0, &off0);
640 *var = fold_build2 (MULT_EXPR, type, var0, op1);
641 *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, op1));
647 HOST_WIDE_INT pbitsize, pbitpos;
649 int punsignedp, pvolatilep;
651 op0 = TREE_OPERAND (op0, 0);
652 base = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset,
653 &pmode, &punsignedp, &pvolatilep, false);
655 if (pbitpos % BITS_PER_UNIT != 0)
657 base = build_fold_addr_expr (base);
658 off0 = ssize_int (pbitpos / BITS_PER_UNIT);
662 split_constant_offset (poffset, &poffset, &off1);
663 off0 = size_binop (PLUS_EXPR, off0, off1);
664 if (POINTER_TYPE_P (TREE_TYPE (base)))
665 base = fold_build_pointer_plus (base, poffset);
667 base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base,
668 fold_convert (TREE_TYPE (base), poffset));
671 var0 = fold_convert (type, base);
673 /* If variable length types are involved, punt, otherwise casts
674 might be converted into ARRAY_REFs in gimplify_conversion.
675 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
676 possibly no longer appears in current GIMPLE, might resurface.
677 This perhaps could run
678 if (CONVERT_EXPR_P (var0))
680 gimplify_conversion (&var0);
681 // Attempt to fill in any within var0 found ARRAY_REF's
682 // element size from corresponding op embedded ARRAY_REF,
683 // if unsuccessful, just punt.
685 while (POINTER_TYPE_P (type))
686 type = TREE_TYPE (type);
687 if (int_size_in_bytes (type) < 0)
697 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
700 gimple def_stmt = SSA_NAME_DEF_STMT (op0);
701 enum tree_code subcode;
703 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
706 var0 = gimple_assign_rhs1 (def_stmt);
707 subcode = gimple_assign_rhs_code (def_stmt);
708 var1 = gimple_assign_rhs2 (def_stmt);
710 return split_constant_offset_1 (type, var0, subcode, var1, var, off);
714 /* We must not introduce undefined overflow, and we must not change the value.
715 Hence we're okay if the inner type doesn't overflow to start with
716 (pointer or signed), the outer type also is an integer or pointer
717 and the outer precision is at least as large as the inner. */
718 tree itype = TREE_TYPE (op0);
719 if ((POINTER_TYPE_P (itype)
720 || (INTEGRAL_TYPE_P (itype) && TYPE_OVERFLOW_UNDEFINED (itype)))
721 && TYPE_PRECISION (type) >= TYPE_PRECISION (itype)
722 && (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type)))
724 split_constant_offset (op0, &var0, off);
725 *var = fold_convert (type, var0);
736 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
737 will be ssizetype. */
740 split_constant_offset (tree exp, tree *var, tree *off)
742 tree type = TREE_TYPE (exp), otype, op0, op1, e, o;
746 *off = ssize_int (0);
749 if (tree_is_chrec (exp)
750 || get_gimple_rhs_class (TREE_CODE (exp)) == GIMPLE_TERNARY_RHS)
753 otype = TREE_TYPE (exp);
754 code = TREE_CODE (exp);
755 extract_ops_from_tree (exp, &code, &op0, &op1);
756 if (split_constant_offset_1 (otype, op0, code, op1, &e, &o))
758 *var = fold_convert (type, e);
763 /* Returns the address ADDR of an object in a canonical shape (without nop
764 casts, and with type of pointer to the object). */
767 canonicalize_base_object_address (tree addr)
773 /* The base address may be obtained by casting from integer, in that case
775 if (!POINTER_TYPE_P (TREE_TYPE (addr)))
778 if (TREE_CODE (addr) != ADDR_EXPR)
781 return build_fold_addr_expr (TREE_OPERAND (addr, 0));
784 /* Analyzes the behavior of the memory reference DR in the innermost loop or
785 basic block that contains it. Returns true if analysis succeed or false
789 dr_analyze_innermost (struct data_reference *dr, struct loop *nest)
791 gimple stmt = DR_STMT (dr);
792 struct loop *loop = loop_containing_stmt (stmt);
793 tree ref = DR_REF (dr);
794 HOST_WIDE_INT pbitsize, pbitpos;
797 int punsignedp, pvolatilep;
798 affine_iv base_iv, offset_iv;
799 tree init, dinit, step;
800 bool in_loop = (loop && loop->num);
802 if (dump_file && (dump_flags & TDF_DETAILS))
803 fprintf (dump_file, "analyze_innermost: ");
805 base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset,
806 &pmode, &punsignedp, &pvolatilep, false);
807 gcc_assert (base != NULL_TREE);
809 if (pbitpos % BITS_PER_UNIT != 0)
811 if (dump_file && (dump_flags & TDF_DETAILS))
812 fprintf (dump_file, "failed: bit offset alignment.\n");
816 if (TREE_CODE (base) == MEM_REF)
818 if (!integer_zerop (TREE_OPERAND (base, 1)))
820 offset_int moff = mem_ref_offset (base);
821 tree mofft = wide_int_to_tree (sizetype, moff);
825 poffset = size_binop (PLUS_EXPR, poffset, mofft);
827 base = TREE_OPERAND (base, 0);
830 base = build_fold_addr_expr (base);
834 if (!simple_iv (loop, loop_containing_stmt (stmt), base, &base_iv,
835 nest ? true : false))
839 if (dump_file && (dump_flags & TDF_DETAILS))
840 fprintf (dump_file, "failed: evolution of base is not"
847 base_iv.step = ssize_int (0);
848 base_iv.no_overflow = true;
855 base_iv.step = ssize_int (0);
856 base_iv.no_overflow = true;
861 offset_iv.base = ssize_int (0);
862 offset_iv.step = ssize_int (0);
868 offset_iv.base = poffset;
869 offset_iv.step = ssize_int (0);
871 else if (!simple_iv (loop, loop_containing_stmt (stmt),
873 nest ? true : false))
877 if (dump_file && (dump_flags & TDF_DETAILS))
878 fprintf (dump_file, "failed: evolution of offset is not"
884 offset_iv.base = poffset;
885 offset_iv.step = ssize_int (0);
890 init = ssize_int (pbitpos / BITS_PER_UNIT);
891 split_constant_offset (base_iv.base, &base_iv.base, &dinit);
892 init = size_binop (PLUS_EXPR, init, dinit);
893 split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
894 init = size_binop (PLUS_EXPR, init, dinit);
896 step = size_binop (PLUS_EXPR,
897 fold_convert (ssizetype, base_iv.step),
898 fold_convert (ssizetype, offset_iv.step));
900 DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base);
902 DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base);
906 DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base));
908 if (dump_file && (dump_flags & TDF_DETAILS))
909 fprintf (dump_file, "success.\n");
914 /* Determines the base object and the list of indices of memory reference
915 DR, analyzed in LOOP and instantiated in loop nest NEST. */
918 dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
920 vec<tree> access_fns = vNULL;
922 tree base, off, access_fn;
923 basic_block before_loop;
925 /* If analyzing a basic-block there are no indices to analyze
926 and thus no access functions. */
929 DR_BASE_OBJECT (dr) = DR_REF (dr);
930 DR_ACCESS_FNS (dr).create (0);
935 before_loop = block_before_loop (nest);
937 /* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses
938 into a two element array with a constant index. The base is
939 then just the immediate underlying object. */
940 if (TREE_CODE (ref) == REALPART_EXPR)
942 ref = TREE_OPERAND (ref, 0);
943 access_fns.safe_push (integer_zero_node);
945 else if (TREE_CODE (ref) == IMAGPART_EXPR)
947 ref = TREE_OPERAND (ref, 0);
948 access_fns.safe_push (integer_one_node);
951 /* Analyze access functions of dimensions we know to be independent. */
952 while (handled_component_p (ref))
954 if (TREE_CODE (ref) == ARRAY_REF)
956 op = TREE_OPERAND (ref, 1);
957 access_fn = analyze_scalar_evolution (loop, op);
958 access_fn = instantiate_scev (before_loop, loop, access_fn);
959 access_fns.safe_push (access_fn);
961 else if (TREE_CODE (ref) == COMPONENT_REF
962 && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 0))) == RECORD_TYPE)
964 /* For COMPONENT_REFs of records (but not unions!) use the
965 FIELD_DECL offset as constant access function so we can
966 disambiguate a[i].f1 and a[i].f2. */
967 tree off = component_ref_field_offset (ref);
968 off = size_binop (PLUS_EXPR,
969 size_binop (MULT_EXPR,
970 fold_convert (bitsizetype, off),
971 bitsize_int (BITS_PER_UNIT)),
972 DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1)));
973 access_fns.safe_push (off);
976 /* If we have an unhandled component we could not translate
977 to an access function stop analyzing. We have determined
978 our base object in this case. */
981 ref = TREE_OPERAND (ref, 0);
984 /* If the address operand of a MEM_REF base has an evolution in the
985 analyzed nest, add it as an additional independent access-function. */
986 if (TREE_CODE (ref) == MEM_REF)
988 op = TREE_OPERAND (ref, 0);
989 access_fn = analyze_scalar_evolution (loop, op);
990 access_fn = instantiate_scev (before_loop, loop, access_fn);
991 if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
994 tree memoff = TREE_OPERAND (ref, 1);
995 base = initial_condition (access_fn);
996 orig_type = TREE_TYPE (base);
997 STRIP_USELESS_TYPE_CONVERSION (base);
998 split_constant_offset (base, &base, &off);
999 STRIP_USELESS_TYPE_CONVERSION (base);
1000 /* Fold the MEM_REF offset into the evolutions initial
1001 value to make more bases comparable. */
1002 if (!integer_zerop (memoff))
1004 off = size_binop (PLUS_EXPR, off,
1005 fold_convert (ssizetype, memoff));
1006 memoff = build_int_cst (TREE_TYPE (memoff), 0);
1008 /* Adjust the offset so it is a multiple of the access type
1009 size and thus we separate bases that can possibly be used
1010 to produce partial overlaps (which the access_fn machinery
1013 if (TYPE_SIZE_UNIT (TREE_TYPE (ref))
1014 && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref))) == INTEGER_CST
1015 && !integer_zerop (TYPE_SIZE_UNIT (TREE_TYPE (ref))))
1016 rem = wi::mod_trunc (off, TYPE_SIZE_UNIT (TREE_TYPE (ref)), SIGNED);
1018 /* If we can't compute the remainder simply force the initial
1019 condition to zero. */
1021 off = wide_int_to_tree (ssizetype, wi::sub (off, rem));
1022 memoff = wide_int_to_tree (TREE_TYPE (memoff), rem);
1023 /* And finally replace the initial condition. */
1024 access_fn = chrec_replace_initial_condition
1025 (access_fn, fold_convert (orig_type, off));
1026 /* ??? This is still not a suitable base object for
1027 dr_may_alias_p - the base object needs to be an
1028 access that covers the object as whole. With
1029 an evolution in the pointer this cannot be
1031 As a band-aid, mark the access so we can special-case
1032 it in dr_may_alias_p. */
1034 ref = fold_build2_loc (EXPR_LOCATION (ref),
1035 MEM_REF, TREE_TYPE (ref),
1037 MR_DEPENDENCE_CLIQUE (ref) = MR_DEPENDENCE_CLIQUE (old);
1038 MR_DEPENDENCE_BASE (ref) = MR_DEPENDENCE_BASE (old);
1039 DR_UNCONSTRAINED_BASE (dr) = true;
1040 access_fns.safe_push (access_fn);
1043 else if (DECL_P (ref))
1045 /* Canonicalize DR_BASE_OBJECT to MEM_REF form. */
1046 ref = build2 (MEM_REF, TREE_TYPE (ref),
1047 build_fold_addr_expr (ref),
1048 build_int_cst (reference_alias_ptr_type (ref), 0));
1051 DR_BASE_OBJECT (dr) = ref;
1052 DR_ACCESS_FNS (dr) = access_fns;
1055 /* Extracts the alias analysis information from the memory reference DR. */
1058 dr_analyze_alias (struct data_reference *dr)
1060 tree ref = DR_REF (dr);
1061 tree base = get_base_address (ref), addr;
1063 if (INDIRECT_REF_P (base)
1064 || TREE_CODE (base) == MEM_REF)
1066 addr = TREE_OPERAND (base, 0);
1067 if (TREE_CODE (addr) == SSA_NAME)
1068 DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
1072 /* Frees data reference DR. */
1075 free_data_ref (data_reference_p dr)
1077 DR_ACCESS_FNS (dr).release ();
1081 /* Analyzes memory reference MEMREF accessed in STMT. The reference
1082 is read if IS_READ is true, write otherwise. Returns the
1083 data_reference description of MEMREF. NEST is the outermost loop
1084 in which the reference should be instantiated, LOOP is the loop in
1085 which the data reference should be analyzed. */
1087 struct data_reference *
1088 create_data_ref (loop_p nest, loop_p loop, tree memref, gimple stmt,
1091 struct data_reference *dr;
1093 if (dump_file && (dump_flags & TDF_DETAILS))
1095 fprintf (dump_file, "Creating dr for ");
1096 print_generic_expr (dump_file, memref, TDF_SLIM);
1097 fprintf (dump_file, "\n");
1100 dr = XCNEW (struct data_reference);
1101 DR_STMT (dr) = stmt;
1102 DR_REF (dr) = memref;
1103 DR_IS_READ (dr) = is_read;
1105 dr_analyze_innermost (dr, nest);
1106 dr_analyze_indices (dr, nest, loop);
1107 dr_analyze_alias (dr);
1109 if (dump_file && (dump_flags & TDF_DETAILS))
1112 fprintf (dump_file, "\tbase_address: ");
1113 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
1114 fprintf (dump_file, "\n\toffset from base address: ");
1115 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
1116 fprintf (dump_file, "\n\tconstant offset from base address: ");
1117 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
1118 fprintf (dump_file, "\n\tstep: ");
1119 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
1120 fprintf (dump_file, "\n\taligned to: ");
1121 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
1122 fprintf (dump_file, "\n\tbase_object: ");
1123 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
1124 fprintf (dump_file, "\n");
1125 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
1127 fprintf (dump_file, "\tAccess function %d: ", i);
1128 print_generic_stmt (dump_file, DR_ACCESS_FN (dr, i), TDF_SLIM);
1135 /* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
1138 dr_equal_offsets_p1 (tree offset1, tree offset2)
1142 STRIP_NOPS (offset1);
1143 STRIP_NOPS (offset2);
1145 if (offset1 == offset2)
1148 if (TREE_CODE (offset1) != TREE_CODE (offset2)
1149 || (!BINARY_CLASS_P (offset1) && !UNARY_CLASS_P (offset1)))
1152 res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 0),
1153 TREE_OPERAND (offset2, 0));
1155 if (!res || !BINARY_CLASS_P (offset1))
1158 res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 1),
1159 TREE_OPERAND (offset2, 1));
1164 /* Check if DRA and DRB have equal offsets. */
1166 dr_equal_offsets_p (struct data_reference *dra,
1167 struct data_reference *drb)
1169 tree offset1, offset2;
1171 offset1 = DR_OFFSET (dra);
1172 offset2 = DR_OFFSET (drb);
1174 return dr_equal_offsets_p1 (offset1, offset2);
1177 /* Returns true if FNA == FNB. */
1180 affine_function_equal_p (affine_fn fna, affine_fn fnb)
1182 unsigned i, n = fna.length ();
1184 if (n != fnb.length ())
1187 for (i = 0; i < n; i++)
1188 if (!operand_equal_p (fna[i], fnb[i], 0))
1194 /* If all the functions in CF are the same, returns one of them,
1195 otherwise returns NULL. */
1198 common_affine_function (conflict_function *cf)
1203 if (!CF_NONTRIVIAL_P (cf))
1204 return affine_fn ();
1208 for (i = 1; i < cf->n; i++)
1209 if (!affine_function_equal_p (comm, cf->fns[i]))
1210 return affine_fn ();
1215 /* Returns the base of the affine function FN. */
1218 affine_function_base (affine_fn fn)
1223 /* Returns true if FN is a constant. */
1226 affine_function_constant_p (affine_fn fn)
1231 for (i = 1; fn.iterate (i, &coef); i++)
1232 if (!integer_zerop (coef))
1238 /* Returns true if FN is the zero constant function. */
1241 affine_function_zero_p (affine_fn fn)
1243 return (integer_zerop (affine_function_base (fn))
1244 && affine_function_constant_p (fn));
1247 /* Returns a signed integer type with the largest precision from TA
1251 signed_type_for_types (tree ta, tree tb)
1253 if (TYPE_PRECISION (ta) > TYPE_PRECISION (tb))
1254 return signed_type_for (ta);
1256 return signed_type_for (tb);
1259 /* Applies operation OP on affine functions FNA and FNB, and returns the
1263 affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
1269 if (fnb.length () > fna.length ())
1281 for (i = 0; i < n; i++)
1283 tree type = signed_type_for_types (TREE_TYPE (fna[i]),
1284 TREE_TYPE (fnb[i]));
1285 ret.quick_push (fold_build2 (op, type, fna[i], fnb[i]));
1288 for (; fna.iterate (i, &coef); i++)
1289 ret.quick_push (fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
1290 coef, integer_zero_node));
1291 for (; fnb.iterate (i, &coef); i++)
1292 ret.quick_push (fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
1293 integer_zero_node, coef));
1298 /* Returns the sum of affine functions FNA and FNB. */
1301 affine_fn_plus (affine_fn fna, affine_fn fnb)
1303 return affine_fn_op (PLUS_EXPR, fna, fnb);
1306 /* Returns the difference of affine functions FNA and FNB. */
1309 affine_fn_minus (affine_fn fna, affine_fn fnb)
1311 return affine_fn_op (MINUS_EXPR, fna, fnb);
1314 /* Frees affine function FN. */
1317 affine_fn_free (affine_fn fn)
1322 /* Determine for each subscript in the data dependence relation DDR
1326 compute_subscript_distance (struct data_dependence_relation *ddr)
1328 conflict_function *cf_a, *cf_b;
1329 affine_fn fn_a, fn_b, diff;
1331 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1335 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1337 struct subscript *subscript;
1339 subscript = DDR_SUBSCRIPT (ddr, i);
1340 cf_a = SUB_CONFLICTS_IN_A (subscript);
1341 cf_b = SUB_CONFLICTS_IN_B (subscript);
1343 fn_a = common_affine_function (cf_a);
1344 fn_b = common_affine_function (cf_b);
1345 if (!fn_a.exists () || !fn_b.exists ())
1347 SUB_DISTANCE (subscript) = chrec_dont_know;
1350 diff = affine_fn_minus (fn_a, fn_b);
1352 if (affine_function_constant_p (diff))
1353 SUB_DISTANCE (subscript) = affine_function_base (diff);
1355 SUB_DISTANCE (subscript) = chrec_dont_know;
1357 affine_fn_free (diff);
1362 /* Returns the conflict function for "unknown". */
1364 static conflict_function *
1365 conflict_fn_not_known (void)
1367 conflict_function *fn = XCNEW (conflict_function);
1373 /* Returns the conflict function for "independent". */
1375 static conflict_function *
1376 conflict_fn_no_dependence (void)
1378 conflict_function *fn = XCNEW (conflict_function);
1379 fn->n = NO_DEPENDENCE;
1384 /* Returns true if the address of OBJ is invariant in LOOP. */
1387 object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj)
1389 while (handled_component_p (obj))
1391 if (TREE_CODE (obj) == ARRAY_REF)
1393 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1394 need to check the stride and the lower bound of the reference. */
1395 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1397 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 3),
1401 else if (TREE_CODE (obj) == COMPONENT_REF)
1403 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1407 obj = TREE_OPERAND (obj, 0);
1410 if (!INDIRECT_REF_P (obj)
1411 && TREE_CODE (obj) != MEM_REF)
1414 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0),
1418 /* Returns false if we can prove that data references A and B do not alias,
1419 true otherwise. If LOOP_NEST is false no cross-iteration aliases are
1423 dr_may_alias_p (const struct data_reference *a, const struct data_reference *b,
1426 tree addr_a = DR_BASE_OBJECT (a);
1427 tree addr_b = DR_BASE_OBJECT (b);
1429 /* If we are not processing a loop nest but scalar code we
1430 do not need to care about possible cross-iteration dependences
1431 and thus can process the full original reference. Do so,
1432 similar to how loop invariant motion applies extra offset-based
1436 aff_tree off1, off2;
1437 widest_int size1, size2;
1438 get_inner_reference_aff (DR_REF (a), &off1, &size1);
1439 get_inner_reference_aff (DR_REF (b), &off2, &size2);
1440 aff_combination_scale (&off1, -1);
1441 aff_combination_add (&off2, &off1);
1442 if (aff_comb_cannot_overlap_p (&off2, size1, size2))
1446 if ((TREE_CODE (addr_a) == MEM_REF || TREE_CODE (addr_a) == TARGET_MEM_REF)
1447 && (TREE_CODE (addr_b) == MEM_REF || TREE_CODE (addr_b) == TARGET_MEM_REF)
1448 && MR_DEPENDENCE_CLIQUE (addr_a) == MR_DEPENDENCE_CLIQUE (addr_b)
1449 && MR_DEPENDENCE_BASE (addr_a) != MR_DEPENDENCE_BASE (addr_b))
1452 /* If we had an evolution in a pointer-based MEM_REF BASE_OBJECT we
1453 do not know the size of the base-object. So we cannot do any
1454 offset/overlap based analysis but have to rely on points-to
1455 information only. */
1456 if (TREE_CODE (addr_a) == MEM_REF
1457 && (DR_UNCONSTRAINED_BASE (a)
1458 || TREE_CODE (TREE_OPERAND (addr_a, 0)) == SSA_NAME))
1460 /* For true dependences we can apply TBAA. */
1461 if (flag_strict_aliasing
1462 && DR_IS_WRITE (a) && DR_IS_READ (b)
1463 && !alias_sets_conflict_p (get_alias_set (DR_REF (a)),
1464 get_alias_set (DR_REF (b))))
1466 if (TREE_CODE (addr_b) == MEM_REF)
1467 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a, 0),
1468 TREE_OPERAND (addr_b, 0));
1470 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a, 0),
1471 build_fold_addr_expr (addr_b));
1473 else if (TREE_CODE (addr_b) == MEM_REF
1474 && (DR_UNCONSTRAINED_BASE (b)
1475 || TREE_CODE (TREE_OPERAND (addr_b, 0)) == SSA_NAME))
1477 /* For true dependences we can apply TBAA. */
1478 if (flag_strict_aliasing
1479 && DR_IS_WRITE (a) && DR_IS_READ (b)
1480 && !alias_sets_conflict_p (get_alias_set (DR_REF (a)),
1481 get_alias_set (DR_REF (b))))
1483 if (TREE_CODE (addr_a) == MEM_REF)
1484 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a, 0),
1485 TREE_OPERAND (addr_b, 0));
1487 return ptr_derefs_may_alias_p (build_fold_addr_expr (addr_a),
1488 TREE_OPERAND (addr_b, 0));
1491 /* Otherwise DR_BASE_OBJECT is an access that covers the whole object
1492 that is being subsetted in the loop nest. */
1493 if (DR_IS_WRITE (a) && DR_IS_WRITE (b))
1494 return refs_output_dependent_p (addr_a, addr_b);
1495 else if (DR_IS_READ (a) && DR_IS_WRITE (b))
1496 return refs_anti_dependent_p (addr_a, addr_b);
1497 return refs_may_alias_p (addr_a, addr_b);
1500 /* Initialize a data dependence relation between data accesses A and
1501 B. NB_LOOPS is the number of loops surrounding the references: the
1502 size of the classic distance/direction vectors. */
1504 struct data_dependence_relation *
1505 initialize_data_dependence_relation (struct data_reference *a,
1506 struct data_reference *b,
1507 vec<loop_p> loop_nest)
1509 struct data_dependence_relation *res;
1512 res = XNEW (struct data_dependence_relation);
1515 DDR_LOOP_NEST (res).create (0);
1516 DDR_REVERSED_P (res) = false;
1517 DDR_SUBSCRIPTS (res).create (0);
1518 DDR_DIR_VECTS (res).create (0);
1519 DDR_DIST_VECTS (res).create (0);
1521 if (a == NULL || b == NULL)
1523 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1527 /* If the data references do not alias, then they are independent. */
1528 if (!dr_may_alias_p (a, b, loop_nest.exists ()))
1530 DDR_ARE_DEPENDENT (res) = chrec_known;
1534 /* The case where the references are exactly the same. */
1535 if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
1537 if (loop_nest.exists ()
1538 && !object_address_invariant_in_loop_p (loop_nest[0],
1539 DR_BASE_OBJECT (a)))
1541 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1544 DDR_AFFINE_P (res) = true;
1545 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1546 DDR_SUBSCRIPTS (res).create (DR_NUM_DIMENSIONS (a));
1547 DDR_LOOP_NEST (res) = loop_nest;
1548 DDR_INNER_LOOP (res) = 0;
1549 DDR_SELF_REFERENCE (res) = true;
1550 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1552 struct subscript *subscript;
1554 subscript = XNEW (struct subscript);
1555 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
1556 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
1557 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1558 SUB_DISTANCE (subscript) = chrec_dont_know;
1559 DDR_SUBSCRIPTS (res).safe_push (subscript);
1564 /* If the references do not access the same object, we do not know
1565 whether they alias or not. */
1566 if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0))
1568 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1572 /* If the base of the object is not invariant in the loop nest, we cannot
1573 analyze it. TODO -- in fact, it would suffice to record that there may
1574 be arbitrary dependences in the loops where the base object varies. */
1575 if (loop_nest.exists ()
1576 && !object_address_invariant_in_loop_p (loop_nest[0],
1577 DR_BASE_OBJECT (a)))
1579 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1583 /* If the number of dimensions of the access to not agree we can have
1584 a pointer access to a component of the array element type and an
1585 array access while the base-objects are still the same. Punt. */
1586 if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
1588 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1592 DDR_AFFINE_P (res) = true;
1593 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1594 DDR_SUBSCRIPTS (res).create (DR_NUM_DIMENSIONS (a));
1595 DDR_LOOP_NEST (res) = loop_nest;
1596 DDR_INNER_LOOP (res) = 0;
1597 DDR_SELF_REFERENCE (res) = false;
1599 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1601 struct subscript *subscript;
1603 subscript = XNEW (struct subscript);
1604 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
1605 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
1606 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1607 SUB_DISTANCE (subscript) = chrec_dont_know;
1608 DDR_SUBSCRIPTS (res).safe_push (subscript);
1614 /* Frees memory used by the conflict function F. */
1617 free_conflict_function (conflict_function *f)
1621 if (CF_NONTRIVIAL_P (f))
1623 for (i = 0; i < f->n; i++)
1624 affine_fn_free (f->fns[i]);
1629 /* Frees memory used by SUBSCRIPTS. */
1632 free_subscripts (vec<subscript_p> subscripts)
1637 FOR_EACH_VEC_ELT (subscripts, i, s)
1639 free_conflict_function (s->conflicting_iterations_in_a);
1640 free_conflict_function (s->conflicting_iterations_in_b);
1643 subscripts.release ();
1646 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1650 finalize_ddr_dependent (struct data_dependence_relation *ddr,
1653 DDR_ARE_DEPENDENT (ddr) = chrec;
1654 free_subscripts (DDR_SUBSCRIPTS (ddr));
1655 DDR_SUBSCRIPTS (ddr).create (0);
1658 /* The dependence relation DDR cannot be represented by a distance
1662 non_affine_dependence_relation (struct data_dependence_relation *ddr)
1664 if (dump_file && (dump_flags & TDF_DETAILS))
1665 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
1667 DDR_AFFINE_P (ddr) = false;
1672 /* This section contains the classic Banerjee tests. */
1674 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1675 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1678 ziv_subscript_p (const_tree chrec_a, const_tree chrec_b)
1680 return (evolution_function_is_constant_p (chrec_a)
1681 && evolution_function_is_constant_p (chrec_b));
1684 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1685 variable, i.e., if the SIV (Single Index Variable) test is true. */
1688 siv_subscript_p (const_tree chrec_a, const_tree chrec_b)
1690 if ((evolution_function_is_constant_p (chrec_a)
1691 && evolution_function_is_univariate_p (chrec_b))
1692 || (evolution_function_is_constant_p (chrec_b)
1693 && evolution_function_is_univariate_p (chrec_a)))
1696 if (evolution_function_is_univariate_p (chrec_a)
1697 && evolution_function_is_univariate_p (chrec_b))
1699 switch (TREE_CODE (chrec_a))
1701 case POLYNOMIAL_CHREC:
1702 switch (TREE_CODE (chrec_b))
1704 case POLYNOMIAL_CHREC:
1705 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
1720 /* Creates a conflict function with N dimensions. The affine functions
1721 in each dimension follow. */
1723 static conflict_function *
1724 conflict_fn (unsigned n, ...)
1727 conflict_function *ret = XCNEW (conflict_function);
1730 gcc_assert (0 < n && n <= MAX_DIM);
1734 for (i = 0; i < n; i++)
1735 ret->fns[i] = va_arg (ap, affine_fn);
1741 /* Returns constant affine function with value CST. */
1744 affine_fn_cst (tree cst)
1748 fn.quick_push (cst);
1752 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1755 affine_fn_univar (tree cst, unsigned dim, tree coef)
1758 fn.create (dim + 1);
1761 gcc_assert (dim > 0);
1762 fn.quick_push (cst);
1763 for (i = 1; i < dim; i++)
1764 fn.quick_push (integer_zero_node);
1765 fn.quick_push (coef);
1769 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1770 *OVERLAPS_B are initialized to the functions that describe the
1771 relation between the elements accessed twice by CHREC_A and
1772 CHREC_B. For k >= 0, the following property is verified:
1774 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1777 analyze_ziv_subscript (tree chrec_a,
1779 conflict_function **overlaps_a,
1780 conflict_function **overlaps_b,
1781 tree *last_conflicts)
1783 tree type, difference;
1784 dependence_stats.num_ziv++;
1786 if (dump_file && (dump_flags & TDF_DETAILS))
1787 fprintf (dump_file, "(analyze_ziv_subscript \n");
1789 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
1790 chrec_a = chrec_convert (type, chrec_a, NULL);
1791 chrec_b = chrec_convert (type, chrec_b, NULL);
1792 difference = chrec_fold_minus (type, chrec_a, chrec_b);
1794 switch (TREE_CODE (difference))
1797 if (integer_zerop (difference))
1799 /* The difference is equal to zero: the accessed index
1800 overlaps for each iteration in the loop. */
1801 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1802 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1803 *last_conflicts = chrec_dont_know;
1804 dependence_stats.num_ziv_dependent++;
1808 /* The accesses do not overlap. */
1809 *overlaps_a = conflict_fn_no_dependence ();
1810 *overlaps_b = conflict_fn_no_dependence ();
1811 *last_conflicts = integer_zero_node;
1812 dependence_stats.num_ziv_independent++;
1817 /* We're not sure whether the indexes overlap. For the moment,
1818 conservatively answer "don't know". */
1819 if (dump_file && (dump_flags & TDF_DETAILS))
1820 fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
1822 *overlaps_a = conflict_fn_not_known ();
1823 *overlaps_b = conflict_fn_not_known ();
1824 *last_conflicts = chrec_dont_know;
1825 dependence_stats.num_ziv_unimplemented++;
1829 if (dump_file && (dump_flags & TDF_DETAILS))
1830 fprintf (dump_file, ")\n");
1833 /* Similar to max_stmt_executions_int, but returns the bound as a tree,
1834 and only if it fits to the int type. If this is not the case, or the
1835 bound on the number of iterations of LOOP could not be derived, returns
1839 max_stmt_executions_tree (struct loop *loop)
1843 if (!max_stmt_executions (loop, &nit))
1844 return chrec_dont_know;
1846 if (!wi::fits_to_tree_p (nit, unsigned_type_node))
1847 return chrec_dont_know;
1849 return wide_int_to_tree (unsigned_type_node, nit);
1852 /* Determine whether the CHREC is always positive/negative. If the expression
1853 cannot be statically analyzed, return false, otherwise set the answer into
1857 chrec_is_positive (tree chrec, bool *value)
1859 bool value0, value1, value2;
1860 tree end_value, nb_iter;
1862 switch (TREE_CODE (chrec))
1864 case POLYNOMIAL_CHREC:
1865 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
1866 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
1869 /* FIXME -- overflows. */
1870 if (value0 == value1)
1876 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
1877 and the proof consists in showing that the sign never
1878 changes during the execution of the loop, from 0 to
1879 loop->nb_iterations. */
1880 if (!evolution_function_is_affine_p (chrec))
1883 nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
1884 if (chrec_contains_undetermined (nb_iter))
1888 /* TODO -- If the test is after the exit, we may decrease the number of
1889 iterations by one. */
1891 nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
1894 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
1896 if (!chrec_is_positive (end_value, &value2))
1900 return value0 == value1;
1903 switch (tree_int_cst_sgn (chrec))
1922 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1923 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1924 *OVERLAPS_B are initialized to the functions that describe the
1925 relation between the elements accessed twice by CHREC_A and
1926 CHREC_B. For k >= 0, the following property is verified:
1928 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1931 analyze_siv_subscript_cst_affine (tree chrec_a,
1933 conflict_function **overlaps_a,
1934 conflict_function **overlaps_b,
1935 tree *last_conflicts)
1937 bool value0, value1, value2;
1938 tree type, difference, tmp;
1940 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
1941 chrec_a = chrec_convert (type, chrec_a, NULL);
1942 chrec_b = chrec_convert (type, chrec_b, NULL);
1943 difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a);
1945 /* Special case overlap in the first iteration. */
1946 if (integer_zerop (difference))
1948 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1949 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1950 *last_conflicts = integer_one_node;
1954 if (!chrec_is_positive (initial_condition (difference), &value0))
1956 if (dump_file && (dump_flags & TDF_DETAILS))
1957 fprintf (dump_file, "siv test failed: chrec is not positive.\n");
1959 dependence_stats.num_siv_unimplemented++;
1960 *overlaps_a = conflict_fn_not_known ();
1961 *overlaps_b = conflict_fn_not_known ();
1962 *last_conflicts = chrec_dont_know;
1967 if (value0 == false)
1969 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
1971 if (dump_file && (dump_flags & TDF_DETAILS))
1972 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1974 *overlaps_a = conflict_fn_not_known ();
1975 *overlaps_b = conflict_fn_not_known ();
1976 *last_conflicts = chrec_dont_know;
1977 dependence_stats.num_siv_unimplemented++;
1986 chrec_b = {10, +, 1}
1989 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1991 HOST_WIDE_INT numiter;
1992 struct loop *loop = get_chrec_loop (chrec_b);
1994 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1995 tmp = fold_build2 (EXACT_DIV_EXPR, type,
1996 fold_build1 (ABS_EXPR, type, difference),
1997 CHREC_RIGHT (chrec_b));
1998 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1999 *last_conflicts = integer_one_node;
2002 /* Perform weak-zero siv test to see if overlap is
2003 outside the loop bounds. */
2004 numiter = max_stmt_executions_int (loop);
2007 && compare_tree_int (tmp, numiter) > 0)
2009 free_conflict_function (*overlaps_a);
2010 free_conflict_function (*overlaps_b);
2011 *overlaps_a = conflict_fn_no_dependence ();
2012 *overlaps_b = conflict_fn_no_dependence ();
2013 *last_conflicts = integer_zero_node;
2014 dependence_stats.num_siv_independent++;
2017 dependence_stats.num_siv_dependent++;
2021 /* When the step does not divide the difference, there are
2025 *overlaps_a = conflict_fn_no_dependence ();
2026 *overlaps_b = conflict_fn_no_dependence ();
2027 *last_conflicts = integer_zero_node;
2028 dependence_stats.num_siv_independent++;
2037 chrec_b = {10, +, -1}
2039 In this case, chrec_a will not overlap with chrec_b. */
2040 *overlaps_a = conflict_fn_no_dependence ();
2041 *overlaps_b = conflict_fn_no_dependence ();
2042 *last_conflicts = integer_zero_node;
2043 dependence_stats.num_siv_independent++;
2050 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
2052 if (dump_file && (dump_flags & TDF_DETAILS))
2053 fprintf (dump_file, "siv test failed: chrec not positive.\n");
2055 *overlaps_a = conflict_fn_not_known ();
2056 *overlaps_b = conflict_fn_not_known ();
2057 *last_conflicts = chrec_dont_know;
2058 dependence_stats.num_siv_unimplemented++;
2063 if (value2 == false)
2067 chrec_b = {10, +, -1}
2069 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2071 HOST_WIDE_INT numiter;
2072 struct loop *loop = get_chrec_loop (chrec_b);
2074 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2075 tmp = fold_build2 (EXACT_DIV_EXPR, type, difference,
2076 CHREC_RIGHT (chrec_b));
2077 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
2078 *last_conflicts = integer_one_node;
2080 /* Perform weak-zero siv test to see if overlap is
2081 outside the loop bounds. */
2082 numiter = max_stmt_executions_int (loop);
2085 && compare_tree_int (tmp, numiter) > 0)
2087 free_conflict_function (*overlaps_a);
2088 free_conflict_function (*overlaps_b);
2089 *overlaps_a = conflict_fn_no_dependence ();
2090 *overlaps_b = conflict_fn_no_dependence ();
2091 *last_conflicts = integer_zero_node;
2092 dependence_stats.num_siv_independent++;
2095 dependence_stats.num_siv_dependent++;
2099 /* When the step does not divide the difference, there
2103 *overlaps_a = conflict_fn_no_dependence ();
2104 *overlaps_b = conflict_fn_no_dependence ();
2105 *last_conflicts = integer_zero_node;
2106 dependence_stats.num_siv_independent++;
2116 In this case, chrec_a will not overlap with chrec_b. */
2117 *overlaps_a = conflict_fn_no_dependence ();
2118 *overlaps_b = conflict_fn_no_dependence ();
2119 *last_conflicts = integer_zero_node;
2120 dependence_stats.num_siv_independent++;
2128 /* Helper recursive function for initializing the matrix A. Returns
2129 the initial value of CHREC. */
2132 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2136 switch (TREE_CODE (chrec))
2138 case POLYNOMIAL_CHREC:
2139 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST);
2141 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2142 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2148 tree op0 = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
2149 tree op1 = initialize_matrix_A (A, TREE_OPERAND (chrec, 1), index, mult);
2151 return chrec_fold_op (TREE_CODE (chrec), chrec_type (chrec), op0, op1);
2156 tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
2157 return chrec_convert (chrec_type (chrec), op, NULL);
2162 /* Handle ~X as -1 - X. */
2163 tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
2164 return chrec_fold_op (MINUS_EXPR, chrec_type (chrec),
2165 build_int_cst (TREE_TYPE (chrec), -1), op);
2177 #define FLOOR_DIV(x,y) ((x) / (y))
2179 /* Solves the special case of the Diophantine equation:
2180 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2182 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2183 number of iterations that loops X and Y run. The overlaps will be
2184 constructed as evolutions in dimension DIM. */
2187 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
2188 affine_fn *overlaps_a,
2189 affine_fn *overlaps_b,
2190 tree *last_conflicts, int dim)
2192 if (((step_a > 0 && step_b > 0)
2193 || (step_a < 0 && step_b < 0)))
2195 int step_overlaps_a, step_overlaps_b;
2196 int gcd_steps_a_b, last_conflict, tau2;
2198 gcd_steps_a_b = gcd (step_a, step_b);
2199 step_overlaps_a = step_b / gcd_steps_a_b;
2200 step_overlaps_b = step_a / gcd_steps_a_b;
2204 tau2 = FLOOR_DIV (niter, step_overlaps_a);
2205 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2206 last_conflict = tau2;
2207 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2210 *last_conflicts = chrec_dont_know;
2212 *overlaps_a = affine_fn_univar (integer_zero_node, dim,
2213 build_int_cst (NULL_TREE,
2215 *overlaps_b = affine_fn_univar (integer_zero_node, dim,
2216 build_int_cst (NULL_TREE,
2222 *overlaps_a = affine_fn_cst (integer_zero_node);
2223 *overlaps_b = affine_fn_cst (integer_zero_node);
2224 *last_conflicts = integer_zero_node;
2228 /* Solves the special case of a Diophantine equation where CHREC_A is
2229 an affine bivariate function, and CHREC_B is an affine univariate
2230 function. For example,
2232 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2234 has the following overlapping functions:
2236 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2237 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2238 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2240 FORNOW: This is a specialized implementation for a case occurring in
2241 a common benchmark. Implement the general algorithm. */
2244 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2245 conflict_function **overlaps_a,
2246 conflict_function **overlaps_b,
2247 tree *last_conflicts)
2249 bool xz_p, yz_p, xyz_p;
2250 int step_x, step_y, step_z;
2251 HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
2252 affine_fn overlaps_a_xz, overlaps_b_xz;
2253 affine_fn overlaps_a_yz, overlaps_b_yz;
2254 affine_fn overlaps_a_xyz, overlaps_b_xyz;
2255 affine_fn ova1, ova2, ovb;
2256 tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
2258 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2259 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2260 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2262 niter_x = max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a)));
2263 niter_y = max_stmt_executions_int (get_chrec_loop (chrec_a));
2264 niter_z = max_stmt_executions_int (get_chrec_loop (chrec_b));
2266 if (niter_x < 0 || niter_y < 0 || niter_z < 0)
2268 if (dump_file && (dump_flags & TDF_DETAILS))
2269 fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
2271 *overlaps_a = conflict_fn_not_known ();
2272 *overlaps_b = conflict_fn_not_known ();
2273 *last_conflicts = chrec_dont_know;
2277 niter = MIN (niter_x, niter_z);
2278 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2281 &last_conflicts_xz, 1);
2282 niter = MIN (niter_y, niter_z);
2283 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2286 &last_conflicts_yz, 2);
2287 niter = MIN (niter_x, niter_z);
2288 niter = MIN (niter_y, niter);
2289 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2292 &last_conflicts_xyz, 3);
2294 xz_p = !integer_zerop (last_conflicts_xz);
2295 yz_p = !integer_zerop (last_conflicts_yz);
2296 xyz_p = !integer_zerop (last_conflicts_xyz);
2298 if (xz_p || yz_p || xyz_p)
2300 ova1 = affine_fn_cst (integer_zero_node);
2301 ova2 = affine_fn_cst (integer_zero_node);
2302 ovb = affine_fn_cst (integer_zero_node);
2305 affine_fn t0 = ova1;
2308 ova1 = affine_fn_plus (ova1, overlaps_a_xz);
2309 ovb = affine_fn_plus (ovb, overlaps_b_xz);
2310 affine_fn_free (t0);
2311 affine_fn_free (t2);
2312 *last_conflicts = last_conflicts_xz;
2316 affine_fn t0 = ova2;
2319 ova2 = affine_fn_plus (ova2, overlaps_a_yz);
2320 ovb = affine_fn_plus (ovb, overlaps_b_yz);
2321 affine_fn_free (t0);
2322 affine_fn_free (t2);
2323 *last_conflicts = last_conflicts_yz;
2327 affine_fn t0 = ova1;
2328 affine_fn t2 = ova2;
2331 ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
2332 ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
2333 ovb = affine_fn_plus (ovb, overlaps_b_xyz);
2334 affine_fn_free (t0);
2335 affine_fn_free (t2);
2336 affine_fn_free (t4);
2337 *last_conflicts = last_conflicts_xyz;
2339 *overlaps_a = conflict_fn (2, ova1, ova2);
2340 *overlaps_b = conflict_fn (1, ovb);
2344 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2345 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2346 *last_conflicts = integer_zero_node;
2349 affine_fn_free (overlaps_a_xz);
2350 affine_fn_free (overlaps_b_xz);
2351 affine_fn_free (overlaps_a_yz);
2352 affine_fn_free (overlaps_b_yz);
2353 affine_fn_free (overlaps_a_xyz);
2354 affine_fn_free (overlaps_b_xyz);
2357 /* Copy the elements of vector VEC1 with length SIZE to VEC2. */
2360 lambda_vector_copy (lambda_vector vec1, lambda_vector vec2,
2363 memcpy (vec2, vec1, size * sizeof (*vec1));
2366 /* Copy the elements of M x N matrix MAT1 to MAT2. */
2369 lambda_matrix_copy (lambda_matrix mat1, lambda_matrix mat2,
2374 for (i = 0; i < m; i++)
2375 lambda_vector_copy (mat1[i], mat2[i], n);
2378 /* Store the N x N identity matrix in MAT. */
2381 lambda_matrix_id (lambda_matrix mat, int size)
2385 for (i = 0; i < size; i++)
2386 for (j = 0; j < size; j++)
2387 mat[i][j] = (i == j) ? 1 : 0;
2390 /* Return the first nonzero element of vector VEC1 between START and N.
2391 We must have START <= N. Returns N if VEC1 is the zero vector. */
2394 lambda_vector_first_nz (lambda_vector vec1, int n, int start)
2397 while (j < n && vec1[j] == 0)
2402 /* Add a multiple of row R1 of matrix MAT with N columns to row R2:
2403 R2 = R2 + CONST1 * R1. */
2406 lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2, int const1)
2413 for (i = 0; i < n; i++)
2414 mat[r2][i] += const1 * mat[r1][i];
2417 /* Swap rows R1 and R2 in matrix MAT. */
2420 lambda_matrix_row_exchange (lambda_matrix mat, int r1, int r2)
2429 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
2430 and store the result in VEC2. */
2433 lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2,
2434 int size, int const1)
2439 lambda_vector_clear (vec2, size);
2441 for (i = 0; i < size; i++)
2442 vec2[i] = const1 * vec1[i];
2445 /* Negate vector VEC1 with length SIZE and store it in VEC2. */
2448 lambda_vector_negate (lambda_vector vec1, lambda_vector vec2,
2451 lambda_vector_mult_const (vec1, vec2, size, -1);
2454 /* Negate row R1 of matrix MAT which has N columns. */
2457 lambda_matrix_row_negate (lambda_matrix mat, int n, int r1)
2459 lambda_vector_negate (mat[r1], mat[r1], n);
2462 /* Return true if two vectors are equal. */
2465 lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
2468 for (i = 0; i < size; i++)
2469 if (vec1[i] != vec2[i])
2474 /* Given an M x N integer matrix A, this function determines an M x
2475 M unimodular matrix U, and an M x N echelon matrix S such that
2476 "U.A = S". This decomposition is also known as "right Hermite".
2478 Ref: Algorithm 2.1 page 33 in "Loop Transformations for
2479 Restructuring Compilers" Utpal Banerjee. */
2482 lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
2483 lambda_matrix S, lambda_matrix U)
2487 lambda_matrix_copy (A, S, m, n);
2488 lambda_matrix_id (U, m);
2490 for (j = 0; j < n; j++)
2492 if (lambda_vector_first_nz (S[j], m, i0) < m)
2495 for (i = m - 1; i >= i0; i--)
2497 while (S[i][j] != 0)
2499 int sigma, factor, a, b;
2503 sigma = (a * b < 0) ? -1: 1;
2506 factor = sigma * (a / b);
2508 lambda_matrix_row_add (S, n, i, i-1, -factor);
2509 lambda_matrix_row_exchange (S, i, i-1);
2511 lambda_matrix_row_add (U, m, i, i-1, -factor);
2512 lambda_matrix_row_exchange (U, i, i-1);
2519 /* Determines the overlapping elements due to accesses CHREC_A and
2520 CHREC_B, that are affine functions. This function cannot handle
2521 symbolic evolution functions, ie. when initial conditions are
2522 parameters, because it uses lambda matrices of integers. */
2525 analyze_subscript_affine_affine (tree chrec_a,
2527 conflict_function **overlaps_a,
2528 conflict_function **overlaps_b,
2529 tree *last_conflicts)
2531 unsigned nb_vars_a, nb_vars_b, dim;
2532 HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta;
2533 lambda_matrix A, U, S;
2534 struct obstack scratch_obstack;
2536 if (eq_evolutions_p (chrec_a, chrec_b))
2538 /* The accessed index overlaps for each iteration in the
2540 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2541 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2542 *last_conflicts = chrec_dont_know;
2545 if (dump_file && (dump_flags & TDF_DETAILS))
2546 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2548 /* For determining the initial intersection, we have to solve a
2549 Diophantine equation. This is the most time consuming part.
2551 For answering to the question: "Is there a dependence?" we have
2552 to prove that there exists a solution to the Diophantine
2553 equation, and that the solution is in the iteration domain,
2554 i.e. the solution is positive or zero, and that the solution
2555 happens before the upper bound loop.nb_iterations. Otherwise
2556 there is no dependence. This function outputs a description of
2557 the iterations that hold the intersections. */
2559 nb_vars_a = nb_vars_in_chrec (chrec_a);
2560 nb_vars_b = nb_vars_in_chrec (chrec_b);
2562 gcc_obstack_init (&scratch_obstack);
2564 dim = nb_vars_a + nb_vars_b;
2565 U = lambda_matrix_new (dim, dim, &scratch_obstack);
2566 A = lambda_matrix_new (dim, 1, &scratch_obstack);
2567 S = lambda_matrix_new (dim, 1, &scratch_obstack);
2569 init_a = int_cst_value (initialize_matrix_A (A, chrec_a, 0, 1));
2570 init_b = int_cst_value (initialize_matrix_A (A, chrec_b, nb_vars_a, -1));
2571 gamma = init_b - init_a;
2573 /* Don't do all the hard work of solving the Diophantine equation
2574 when we already know the solution: for example,
2577 | gamma = 3 - 3 = 0.
2578 Then the first overlap occurs during the first iterations:
2579 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2583 if (nb_vars_a == 1 && nb_vars_b == 1)
2585 HOST_WIDE_INT step_a, step_b;
2586 HOST_WIDE_INT niter, niter_a, niter_b;
2589 niter_a = max_stmt_executions_int (get_chrec_loop (chrec_a));
2590 niter_b = max_stmt_executions_int (get_chrec_loop (chrec_b));
2591 niter = MIN (niter_a, niter_b);
2592 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2593 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2595 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2598 *overlaps_a = conflict_fn (1, ova);
2599 *overlaps_b = conflict_fn (1, ovb);
2602 else if (nb_vars_a == 2 && nb_vars_b == 1)
2603 compute_overlap_steps_for_affine_1_2
2604 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2606 else if (nb_vars_a == 1 && nb_vars_b == 2)
2607 compute_overlap_steps_for_affine_1_2
2608 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2612 if (dump_file && (dump_flags & TDF_DETAILS))
2613 fprintf (dump_file, "affine-affine test failed: too many variables.\n");
2614 *overlaps_a = conflict_fn_not_known ();
2615 *overlaps_b = conflict_fn_not_known ();
2616 *last_conflicts = chrec_dont_know;
2618 goto end_analyze_subs_aa;
2622 lambda_matrix_right_hermite (A, dim, 1, S, U);
2627 lambda_matrix_row_negate (U, dim, 0);
2629 gcd_alpha_beta = S[0][0];
2631 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2632 but that is a quite strange case. Instead of ICEing, answer
2634 if (gcd_alpha_beta == 0)
2636 *overlaps_a = conflict_fn_not_known ();
2637 *overlaps_b = conflict_fn_not_known ();
2638 *last_conflicts = chrec_dont_know;
2639 goto end_analyze_subs_aa;
2642 /* The classic "gcd-test". */
2643 if (!int_divides_p (gcd_alpha_beta, gamma))
2645 /* The "gcd-test" has determined that there is no integer
2646 solution, i.e. there is no dependence. */
2647 *overlaps_a = conflict_fn_no_dependence ();
2648 *overlaps_b = conflict_fn_no_dependence ();
2649 *last_conflicts = integer_zero_node;
2652 /* Both access functions are univariate. This includes SIV and MIV cases. */
2653 else if (nb_vars_a == 1 && nb_vars_b == 1)
2655 /* Both functions should have the same evolution sign. */
2656 if (((A[0][0] > 0 && -A[1][0] > 0)
2657 || (A[0][0] < 0 && -A[1][0] < 0)))
2659 /* The solutions are given by:
2661 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2664 For a given integer t. Using the following variables,
2666 | i0 = u11 * gamma / gcd_alpha_beta
2667 | j0 = u12 * gamma / gcd_alpha_beta
2674 | y0 = j0 + j1 * t. */
2675 HOST_WIDE_INT i0, j0, i1, j1;
2677 i0 = U[0][0] * gamma / gcd_alpha_beta;
2678 j0 = U[0][1] * gamma / gcd_alpha_beta;
2682 if ((i1 == 0 && i0 < 0)
2683 || (j1 == 0 && j0 < 0))
2685 /* There is no solution.
2686 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2687 falls in here, but for the moment we don't look at the
2688 upper bound of the iteration domain. */
2689 *overlaps_a = conflict_fn_no_dependence ();
2690 *overlaps_b = conflict_fn_no_dependence ();
2691 *last_conflicts = integer_zero_node;
2692 goto end_analyze_subs_aa;
2695 if (i1 > 0 && j1 > 0)
2697 HOST_WIDE_INT niter_a
2698 = max_stmt_executions_int (get_chrec_loop (chrec_a));
2699 HOST_WIDE_INT niter_b
2700 = max_stmt_executions_int (get_chrec_loop (chrec_b));
2701 HOST_WIDE_INT niter = MIN (niter_a, niter_b);
2703 /* (X0, Y0) is a solution of the Diophantine equation:
2704 "chrec_a (X0) = chrec_b (Y0)". */
2705 HOST_WIDE_INT tau1 = MAX (CEIL (-i0, i1),
2707 HOST_WIDE_INT x0 = i1 * tau1 + i0;
2708 HOST_WIDE_INT y0 = j1 * tau1 + j0;
2710 /* (X1, Y1) is the smallest positive solution of the eq
2711 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2712 first conflict occurs. */
2713 HOST_WIDE_INT min_multiple = MIN (x0 / i1, y0 / j1);
2714 HOST_WIDE_INT x1 = x0 - i1 * min_multiple;
2715 HOST_WIDE_INT y1 = y0 - j1 * min_multiple;
2719 HOST_WIDE_INT tau2 = MIN (FLOOR_DIV (niter - i0, i1),
2720 FLOOR_DIV (niter - j0, j1));
2721 HOST_WIDE_INT last_conflict = tau2 - (x1 - i0)/i1;
2723 /* If the overlap occurs outside of the bounds of the
2724 loop, there is no dependence. */
2725 if (x1 >= niter || y1 >= niter)
2727 *overlaps_a = conflict_fn_no_dependence ();
2728 *overlaps_b = conflict_fn_no_dependence ();
2729 *last_conflicts = integer_zero_node;
2730 goto end_analyze_subs_aa;
2733 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2736 *last_conflicts = chrec_dont_know;
2740 affine_fn_univar (build_int_cst (NULL_TREE, x1),
2742 build_int_cst (NULL_TREE, i1)));
2745 affine_fn_univar (build_int_cst (NULL_TREE, y1),
2747 build_int_cst (NULL_TREE, j1)));
2751 /* FIXME: For the moment, the upper bound of the
2752 iteration domain for i and j is not checked. */
2753 if (dump_file && (dump_flags & TDF_DETAILS))
2754 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2755 *overlaps_a = conflict_fn_not_known ();
2756 *overlaps_b = conflict_fn_not_known ();
2757 *last_conflicts = chrec_dont_know;
2762 if (dump_file && (dump_flags & TDF_DETAILS))
2763 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2764 *overlaps_a = conflict_fn_not_known ();
2765 *overlaps_b = conflict_fn_not_known ();
2766 *last_conflicts = chrec_dont_know;
2771 if (dump_file && (dump_flags & TDF_DETAILS))
2772 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2773 *overlaps_a = conflict_fn_not_known ();
2774 *overlaps_b = conflict_fn_not_known ();
2775 *last_conflicts = chrec_dont_know;
2778 end_analyze_subs_aa:
2779 obstack_free (&scratch_obstack, NULL);
2780 if (dump_file && (dump_flags & TDF_DETAILS))
2782 fprintf (dump_file, " (overlaps_a = ");
2783 dump_conflict_function (dump_file, *overlaps_a);
2784 fprintf (dump_file, ")\n (overlaps_b = ");
2785 dump_conflict_function (dump_file, *overlaps_b);
2786 fprintf (dump_file, "))\n");
2790 /* Returns true when analyze_subscript_affine_affine can be used for
2791 determining the dependence relation between chrec_a and chrec_b,
2792 that contain symbols. This function modifies chrec_a and chrec_b
2793 such that the analysis result is the same, and such that they don't
2794 contain symbols, and then can safely be passed to the analyzer.
2796 Example: The analysis of the following tuples of evolutions produce
2797 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2800 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2801 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2805 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
2807 tree diff, type, left_a, left_b, right_b;
2809 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
2810 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
2811 /* FIXME: For the moment not handled. Might be refined later. */
2814 type = chrec_type (*chrec_a);
2815 left_a = CHREC_LEFT (*chrec_a);
2816 left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL);
2817 diff = chrec_fold_minus (type, left_a, left_b);
2819 if (!evolution_function_is_constant_p (diff))
2822 if (dump_file && (dump_flags & TDF_DETAILS))
2823 fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
2825 *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
2826 diff, CHREC_RIGHT (*chrec_a));
2827 right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL);
2828 *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
2829 build_int_cst (type, 0),
2834 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2835 *OVERLAPS_B are initialized to the functions that describe the
2836 relation between the elements accessed twice by CHREC_A and
2837 CHREC_B. For k >= 0, the following property is verified:
2839 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2842 analyze_siv_subscript (tree chrec_a,
2844 conflict_function **overlaps_a,
2845 conflict_function **overlaps_b,
2846 tree *last_conflicts,
2849 dependence_stats.num_siv++;
2851 if (dump_file && (dump_flags & TDF_DETAILS))
2852 fprintf (dump_file, "(analyze_siv_subscript \n");
2854 if (evolution_function_is_constant_p (chrec_a)
2855 && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
2856 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
2857 overlaps_a, overlaps_b, last_conflicts);
2859 else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
2860 && evolution_function_is_constant_p (chrec_b))
2861 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2862 overlaps_b, overlaps_a, last_conflicts);
2864 else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
2865 && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
2867 if (!chrec_contains_symbols (chrec_a)
2868 && !chrec_contains_symbols (chrec_b))
2870 analyze_subscript_affine_affine (chrec_a, chrec_b,
2871 overlaps_a, overlaps_b,
2874 if (CF_NOT_KNOWN_P (*overlaps_a)
2875 || CF_NOT_KNOWN_P (*overlaps_b))
2876 dependence_stats.num_siv_unimplemented++;
2877 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2878 || CF_NO_DEPENDENCE_P (*overlaps_b))
2879 dependence_stats.num_siv_independent++;
2881 dependence_stats.num_siv_dependent++;
2883 else if (can_use_analyze_subscript_affine_affine (&chrec_a,
2886 analyze_subscript_affine_affine (chrec_a, chrec_b,
2887 overlaps_a, overlaps_b,
2890 if (CF_NOT_KNOWN_P (*overlaps_a)
2891 || CF_NOT_KNOWN_P (*overlaps_b))
2892 dependence_stats.num_siv_unimplemented++;
2893 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2894 || CF_NO_DEPENDENCE_P (*overlaps_b))
2895 dependence_stats.num_siv_independent++;
2897 dependence_stats.num_siv_dependent++;
2900 goto siv_subscript_dontknow;
2905 siv_subscript_dontknow:;
2906 if (dump_file && (dump_flags & TDF_DETAILS))
2907 fprintf (dump_file, " siv test failed: unimplemented");
2908 *overlaps_a = conflict_fn_not_known ();
2909 *overlaps_b = conflict_fn_not_known ();
2910 *last_conflicts = chrec_dont_know;
2911 dependence_stats.num_siv_unimplemented++;
2914 if (dump_file && (dump_flags & TDF_DETAILS))
2915 fprintf (dump_file, ")\n");
2918 /* Returns false if we can prove that the greatest common divisor of the steps
2919 of CHREC does not divide CST, false otherwise. */
2922 gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst)
2924 HOST_WIDE_INT cd = 0, val;
2927 if (!tree_fits_shwi_p (cst))
2929 val = tree_to_shwi (cst);
2931 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
2933 step = CHREC_RIGHT (chrec);
2934 if (!tree_fits_shwi_p (step))
2936 cd = gcd (cd, tree_to_shwi (step));
2937 chrec = CHREC_LEFT (chrec);
2940 return val % cd == 0;
2943 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2944 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2945 functions that describe the relation between the elements accessed
2946 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2949 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2952 analyze_miv_subscript (tree chrec_a,
2954 conflict_function **overlaps_a,
2955 conflict_function **overlaps_b,
2956 tree *last_conflicts,
2957 struct loop *loop_nest)
2959 tree type, difference;
2961 dependence_stats.num_miv++;
2962 if (dump_file && (dump_flags & TDF_DETAILS))
2963 fprintf (dump_file, "(analyze_miv_subscript \n");
2965 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
2966 chrec_a = chrec_convert (type, chrec_a, NULL);
2967 chrec_b = chrec_convert (type, chrec_b, NULL);
2968 difference = chrec_fold_minus (type, chrec_a, chrec_b);
2970 if (eq_evolutions_p (chrec_a, chrec_b))
2972 /* Access functions are the same: all the elements are accessed
2973 in the same order. */
2974 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2975 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2976 *last_conflicts = max_stmt_executions_tree (get_chrec_loop (chrec_a));
2977 dependence_stats.num_miv_dependent++;
2980 else if (evolution_function_is_constant_p (difference)
2981 /* For the moment, the following is verified:
2982 evolution_function_is_affine_multivariate_p (chrec_a,
2984 && !gcd_of_steps_may_divide_p (chrec_a, difference))
2986 /* testsuite/.../ssa-chrec-33.c
2987 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2989 The difference is 1, and all the evolution steps are multiples
2990 of 2, consequently there are no overlapping elements. */
2991 *overlaps_a = conflict_fn_no_dependence ();
2992 *overlaps_b = conflict_fn_no_dependence ();
2993 *last_conflicts = integer_zero_node;
2994 dependence_stats.num_miv_independent++;
2997 else if (evolution_function_is_affine_multivariate_p (chrec_a, loop_nest->num)
2998 && !chrec_contains_symbols (chrec_a)
2999 && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num)
3000 && !chrec_contains_symbols (chrec_b))
3002 /* testsuite/.../ssa-chrec-35.c
3003 {0, +, 1}_2 vs. {0, +, 1}_3
3004 the overlapping elements are respectively located at iterations:
3005 {0, +, 1}_x and {0, +, 1}_x,
3006 in other words, we have the equality:
3007 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
3010 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
3011 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
3013 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
3014 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
3016 analyze_subscript_affine_affine (chrec_a, chrec_b,
3017 overlaps_a, overlaps_b, last_conflicts);
3019 if (CF_NOT_KNOWN_P (*overlaps_a)
3020 || CF_NOT_KNOWN_P (*overlaps_b))
3021 dependence_stats.num_miv_unimplemented++;
3022 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
3023 || CF_NO_DEPENDENCE_P (*overlaps_b))
3024 dependence_stats.num_miv_independent++;
3026 dependence_stats.num_miv_dependent++;
3031 /* When the analysis is too difficult, answer "don't know". */
3032 if (dump_file && (dump_flags & TDF_DETAILS))
3033 fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
3035 *overlaps_a = conflict_fn_not_known ();
3036 *overlaps_b = conflict_fn_not_known ();
3037 *last_conflicts = chrec_dont_know;
3038 dependence_stats.num_miv_unimplemented++;
3041 if (dump_file && (dump_flags & TDF_DETAILS))
3042 fprintf (dump_file, ")\n");
3045 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
3046 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
3047 OVERLAP_ITERATIONS_B are initialized with two functions that
3048 describe the iterations that contain conflicting elements.
3050 Remark: For an integer k >= 0, the following equality is true:
3052 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
3056 analyze_overlapping_iterations (tree chrec_a,
3058 conflict_function **overlap_iterations_a,
3059 conflict_function **overlap_iterations_b,
3060 tree *last_conflicts, struct loop *loop_nest)
3062 unsigned int lnn = loop_nest->num;
3064 dependence_stats.num_subscript_tests++;
3066 if (dump_file && (dump_flags & TDF_DETAILS))
3068 fprintf (dump_file, "(analyze_overlapping_iterations \n");
3069 fprintf (dump_file, " (chrec_a = ");
3070 print_generic_expr (dump_file, chrec_a, 0);
3071 fprintf (dump_file, ")\n (chrec_b = ");
3072 print_generic_expr (dump_file, chrec_b, 0);
3073 fprintf (dump_file, ")\n");
3076 if (chrec_a == NULL_TREE
3077 || chrec_b == NULL_TREE
3078 || chrec_contains_undetermined (chrec_a)
3079 || chrec_contains_undetermined (chrec_b))
3081 dependence_stats.num_subscript_undetermined++;
3083 *overlap_iterations_a = conflict_fn_not_known ();
3084 *overlap_iterations_b = conflict_fn_not_known ();
3087 /* If they are the same chrec, and are affine, they overlap
3088 on every iteration. */
3089 else if (eq_evolutions_p (chrec_a, chrec_b)
3090 && (evolution_function_is_affine_multivariate_p (chrec_a, lnn)
3091 || operand_equal_p (chrec_a, chrec_b, 0)))
3093 dependence_stats.num_same_subscript_function++;
3094 *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
3095 *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
3096 *last_conflicts = chrec_dont_know;
3099 /* If they aren't the same, and aren't affine, we can't do anything
3101 else if ((chrec_contains_symbols (chrec_a)
3102 || chrec_contains_symbols (chrec_b))
3103 && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
3104 || !evolution_function_is_affine_multivariate_p (chrec_b, lnn)))
3106 dependence_stats.num_subscript_undetermined++;
3107 *overlap_iterations_a = conflict_fn_not_known ();
3108 *overlap_iterations_b = conflict_fn_not_known ();
3111 else if (ziv_subscript_p (chrec_a, chrec_b))
3112 analyze_ziv_subscript (chrec_a, chrec_b,
3113 overlap_iterations_a, overlap_iterations_b,
3116 else if (siv_subscript_p (chrec_a, chrec_b))
3117 analyze_siv_subscript (chrec_a, chrec_b,
3118 overlap_iterations_a, overlap_iterations_b,
3119 last_conflicts, lnn);
3122 analyze_miv_subscript (chrec_a, chrec_b,
3123 overlap_iterations_a, overlap_iterations_b,
3124 last_conflicts, loop_nest);
3126 if (dump_file && (dump_flags & TDF_DETAILS))
3128 fprintf (dump_file, " (overlap_iterations_a = ");
3129 dump_conflict_function (dump_file, *overlap_iterations_a);
3130 fprintf (dump_file, ")\n (overlap_iterations_b = ");
3131 dump_conflict_function (dump_file, *overlap_iterations_b);
3132 fprintf (dump_file, "))\n");
3136 /* Helper function for uniquely inserting distance vectors. */
3139 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
3144 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, v)
3145 if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
3148 DDR_DIST_VECTS (ddr).safe_push (dist_v);
3151 /* Helper function for uniquely inserting direction vectors. */
3154 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
3159 FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr), i, v)
3160 if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
3163 DDR_DIR_VECTS (ddr).safe_push (dir_v);
3166 /* Add a distance of 1 on all the loops outer than INDEX. If we
3167 haven't yet determined a distance for this outer loop, push a new
3168 distance vector composed of the previous distance, and a distance
3169 of 1 for this outer loop. Example:
3177 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
3178 save (0, 1), then we have to save (1, 0). */
3181 add_outer_distances (struct data_dependence_relation *ddr,
3182 lambda_vector dist_v, int index)
3184 /* For each outer loop where init_v is not set, the accesses are
3185 in dependence of distance 1 in the loop. */
3186 while (--index >= 0)
3188 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3189 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3191 save_dist_v (ddr, save_v);
3195 /* Return false when fail to represent the data dependence as a
3196 distance vector. INIT_B is set to true when a component has been
3197 added to the distance vector DIST_V. INDEX_CARRY is then set to
3198 the index in DIST_V that carries the dependence. */
3201 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
3202 struct data_reference *ddr_a,
3203 struct data_reference *ddr_b,
3204 lambda_vector dist_v, bool *init_b,
3208 lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3210 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3212 tree access_fn_a, access_fn_b;
3213 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3215 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3217 non_affine_dependence_relation (ddr);
3221 access_fn_a = DR_ACCESS_FN (ddr_a, i);
3222 access_fn_b = DR_ACCESS_FN (ddr_b, i);
3224 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3225 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3228 int var_a = CHREC_VARIABLE (access_fn_a);
3229 int var_b = CHREC_VARIABLE (access_fn_b);
3232 || chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3234 non_affine_dependence_relation (ddr);
3238 dist = int_cst_value (SUB_DISTANCE (subscript));
3239 index = index_in_loop_nest (var_a, DDR_LOOP_NEST (ddr));
3240 *index_carry = MIN (index, *index_carry);
3242 /* This is the subscript coupling test. If we have already
3243 recorded a distance for this loop (a distance coming from
3244 another subscript), it should be the same. For example,
3245 in the following code, there is no dependence:
3252 if (init_v[index] != 0 && dist_v[index] != dist)
3254 finalize_ddr_dependent (ddr, chrec_known);
3258 dist_v[index] = dist;
3262 else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
3264 /* This can be for example an affine vs. constant dependence
3265 (T[i] vs. T[3]) that is not an affine dependence and is
3266 not representable as a distance vector. */
3267 non_affine_dependence_relation (ddr);
3275 /* Return true when the DDR contains only constant access functions. */
3278 constant_access_functions (const struct data_dependence_relation *ddr)
3282 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3283 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
3284 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
3290 /* Helper function for the case where DDR_A and DDR_B are the same
3291 multivariate access function with a constant step. For an example
3295 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
3298 tree c_1 = CHREC_LEFT (c_2);
3299 tree c_0 = CHREC_LEFT (c_1);
3300 lambda_vector dist_v;
3303 /* Polynomials with more than 2 variables are not handled yet. When
3304 the evolution steps are parameters, it is not possible to
3305 represent the dependence using classical distance vectors. */
3306 if (TREE_CODE (c_0) != INTEGER_CST
3307 || TREE_CODE (CHREC_RIGHT (c_1)) != INTEGER_CST
3308 || TREE_CODE (CHREC_RIGHT (c_2)) != INTEGER_CST)
3310 DDR_AFFINE_P (ddr) = false;
3314 x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
3315 x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
3317 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3318 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3319 v1 = int_cst_value (CHREC_RIGHT (c_1));
3320 v2 = int_cst_value (CHREC_RIGHT (c_2));
3333 save_dist_v (ddr, dist_v);
3335 add_outer_distances (ddr, dist_v, x_1);
3338 /* Helper function for the case where DDR_A and DDR_B are the same
3339 access functions. */
3342 add_other_self_distances (struct data_dependence_relation *ddr)
3344 lambda_vector dist_v;
3346 int index_carry = DDR_NB_LOOPS (ddr);
3348 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3350 tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
3352 if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
3354 if (!evolution_function_is_univariate_p (access_fun))
3356 if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
3358 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
3362 access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);
3364 if (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC)
3365 add_multivariate_self_dist (ddr, access_fun);
3367 /* The evolution step is not constant: it varies in
3368 the outer loop, so this cannot be represented by a
3369 distance vector. For example in pr34635.c the
3370 evolution is {0, +, {0, +, 4}_1}_2. */
3371 DDR_AFFINE_P (ddr) = false;
3376 index_carry = MIN (index_carry,
3377 index_in_loop_nest (CHREC_VARIABLE (access_fun),
3378 DDR_LOOP_NEST (ddr)));
3382 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3383 add_outer_distances (ddr, dist_v, index_carry);
3387 insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
3389 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3391 dist_v[DDR_INNER_LOOP (ddr)] = 1;
3392 save_dist_v (ddr, dist_v);
3395 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
3396 is the case for example when access functions are the same and
3397 equal to a constant, as in:
3404 in which case the distance vectors are (0) and (1). */
3407 add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
3411 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3413 subscript_p sub = DDR_SUBSCRIPT (ddr, i);
3414 conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
3415 conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
3417 for (j = 0; j < ca->n; j++)
3418 if (affine_function_zero_p (ca->fns[j]))
3420 insert_innermost_unit_dist_vector (ddr);
3424 for (j = 0; j < cb->n; j++)
3425 if (affine_function_zero_p (cb->fns[j]))
3427 insert_innermost_unit_dist_vector (ddr);
3433 /* Compute the classic per loop distance vector. DDR is the data
3434 dependence relation to build a vector from. Return false when fail
3435 to represent the data dependence as a distance vector. */
3438 build_classic_dist_vector (struct data_dependence_relation *ddr,
3439 struct loop *loop_nest)
3441 bool init_b = false;
3442 int index_carry = DDR_NB_LOOPS (ddr);
3443 lambda_vector dist_v;
3445 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3448 if (same_access_functions (ddr))
3450 /* Save the 0 vector. */
3451 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3452 save_dist_v (ddr, dist_v);
3454 if (constant_access_functions (ddr))
3455 add_distance_for_zero_overlaps (ddr);
3457 if (DDR_NB_LOOPS (ddr) > 1)
3458 add_other_self_distances (ddr);
3463 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3464 if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
3465 dist_v, &init_b, &index_carry))
3468 /* Save the distance vector if we initialized one. */
3471 /* Verify a basic constraint: classic distance vectors should
3472 always be lexicographically positive.
3474 Data references are collected in the order of execution of
3475 the program, thus for the following loop
3477 | for (i = 1; i < 100; i++)
3478 | for (j = 1; j < 100; j++)
3480 | t = T[j+1][i-1]; // A
3481 | T[j][i] = t + 2; // B
3484 references are collected following the direction of the wind:
3485 A then B. The data dependence tests are performed also
3486 following this order, such that we're looking at the distance
3487 separating the elements accessed by A from the elements later
3488 accessed by B. But in this example, the distance returned by
3489 test_dep (A, B) is lexicographically negative (-1, 1), that
3490 means that the access A occurs later than B with respect to
3491 the outer loop, ie. we're actually looking upwind. In this
3492 case we solve test_dep (B, A) looking downwind to the
3493 lexicographically positive solution, that returns the
3494 distance vector (1, -1). */
3495 if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
3497 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3498 if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3501 compute_subscript_distance (ddr);
3502 if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3503 save_v, &init_b, &index_carry))
3505 save_dist_v (ddr, save_v);
3506 DDR_REVERSED_P (ddr) = true;
3508 /* In this case there is a dependence forward for all the
3511 | for (k = 1; k < 100; k++)
3512 | for (i = 1; i < 100; i++)
3513 | for (j = 1; j < 100; j++)
3515 | t = T[j+1][i-1]; // A
3516 | T[j][i] = t + 2; // B
3524 if (DDR_NB_LOOPS (ddr) > 1)
3526 add_outer_distances (ddr, save_v, index_carry);
3527 add_outer_distances (ddr, dist_v, index_carry);
3532 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3533 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3535 if (DDR_NB_LOOPS (ddr) > 1)
3537 lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3539 if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr),
3540 DDR_A (ddr), loop_nest))
3542 compute_subscript_distance (ddr);
3543 if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3544 opposite_v, &init_b,
3548 save_dist_v (ddr, save_v);
3549 add_outer_distances (ddr, dist_v, index_carry);
3550 add_outer_distances (ddr, opposite_v, index_carry);
3553 save_dist_v (ddr, save_v);
3558 /* There is a distance of 1 on all the outer loops: Example:
3559 there is a dependence of distance 1 on loop_1 for the array A.
3565 add_outer_distances (ddr, dist_v,
3566 lambda_vector_first_nz (dist_v,
3567 DDR_NB_LOOPS (ddr), 0));
3570 if (dump_file && (dump_flags & TDF_DETAILS))
3574 fprintf (dump_file, "(build_classic_dist_vector\n");
3575 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3577 fprintf (dump_file, " dist_vector = (");
3578 print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
3579 DDR_NB_LOOPS (ddr));
3580 fprintf (dump_file, " )\n");
3582 fprintf (dump_file, ")\n");
3588 /* Return the direction for a given distance.
3589 FIXME: Computing dir this way is suboptimal, since dir can catch
3590 cases that dist is unable to represent. */
3592 static inline enum data_dependence_direction
3593 dir_from_dist (int dist)
3596 return dir_positive;
3598 return dir_negative;
3603 /* Compute the classic per loop direction vector. DDR is the data
3604 dependence relation to build a vector from. */
3607 build_classic_dir_vector (struct data_dependence_relation *ddr)
3610 lambda_vector dist_v;
3612 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
3614 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3616 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3617 dir_v[j] = dir_from_dist (dist_v[j]);
3619 save_dir_v (ddr, dir_v);
3623 /* Helper function. Returns true when there is a dependence between
3624 data references DRA and DRB. */
3627 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
3628 struct data_reference *dra,
3629 struct data_reference *drb,
3630 struct loop *loop_nest)
3633 tree last_conflicts;
3634 struct subscript *subscript;
3635 tree res = NULL_TREE;
3637 for (i = 0; DDR_SUBSCRIPTS (ddr).iterate (i, &subscript); i++)
3639 conflict_function *overlaps_a, *overlaps_b;
3641 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
3642 DR_ACCESS_FN (drb, i),
3643 &overlaps_a, &overlaps_b,
3644 &last_conflicts, loop_nest);
3646 if (SUB_CONFLICTS_IN_A (subscript))
3647 free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
3648 if (SUB_CONFLICTS_IN_B (subscript))
3649 free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
3651 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3652 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3653 SUB_LAST_CONFLICT (subscript) = last_conflicts;
3655 /* If there is any undetermined conflict function we have to
3656 give a conservative answer in case we cannot prove that
3657 no dependence exists when analyzing another subscript. */
3658 if (CF_NOT_KNOWN_P (overlaps_a)
3659 || CF_NOT_KNOWN_P (overlaps_b))
3661 res = chrec_dont_know;
3665 /* When there is a subscript with no dependence we can stop. */
3666 else if (CF_NO_DEPENDENCE_P (overlaps_a)
3667 || CF_NO_DEPENDENCE_P (overlaps_b))
3674 if (res == NULL_TREE)
3677 if (res == chrec_known)
3678 dependence_stats.num_dependence_independent++;
3680 dependence_stats.num_dependence_undetermined++;
3681 finalize_ddr_dependent (ddr, res);
3685 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3688 subscript_dependence_tester (struct data_dependence_relation *ddr,
3689 struct loop *loop_nest)
3691 if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest))
3692 dependence_stats.num_dependence_dependent++;
3694 compute_subscript_distance (ddr);
3695 if (build_classic_dist_vector (ddr, loop_nest))
3696 build_classic_dir_vector (ddr);
3699 /* Returns true when all the access functions of A are affine or
3700 constant with respect to LOOP_NEST. */
3703 access_functions_are_affine_or_constant_p (const struct data_reference *a,
3704 const struct loop *loop_nest)
3707 vec<tree> fns = DR_ACCESS_FNS (a);
3710 FOR_EACH_VEC_ELT (fns, i, t)
3711 if (!evolution_function_is_invariant_p (t, loop_nest->num)
3712 && !evolution_function_is_affine_multivariate_p (t, loop_nest->num))
3718 /* Initializes an equation for an OMEGA problem using the information
3719 contained in the ACCESS_FUN. Returns true when the operation
3722 PB is the omega constraint system.
3723 EQ is the number of the equation to be initialized.
3724 OFFSET is used for shifting the variables names in the constraints:
3725 a constrain is composed of 2 * the number of variables surrounding
3726 dependence accesses. OFFSET is set either to 0 for the first n variables,
3727 then it is set to n.
3728 ACCESS_FUN is expected to be an affine chrec. */
3731 init_omega_eq_with_af (omega_pb pb, unsigned eq,
3732 unsigned int offset, tree access_fun,
3733 struct data_dependence_relation *ddr)
3735 switch (TREE_CODE (access_fun))
3737 case POLYNOMIAL_CHREC:
3739 tree left = CHREC_LEFT (access_fun);
3740 tree right = CHREC_RIGHT (access_fun);
3741 int var = CHREC_VARIABLE (access_fun);
3744 if (TREE_CODE (right) != INTEGER_CST)
3747 var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
3748 pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
3750 /* Compute the innermost loop index. */
3751 DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
3754 pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
3755 += int_cst_value (right);
3757 switch (TREE_CODE (left))
3759 case POLYNOMIAL_CHREC:
3760 return init_omega_eq_with_af (pb, eq, offset, left, ddr);
3763 pb->eqs[eq].coef[0] += int_cst_value (left);
3772 pb->eqs[eq].coef[0] += int_cst_value (access_fun);
3780 /* As explained in the comments preceding init_omega_for_ddr, we have
3781 to set up a system for each loop level, setting outer loops
3782 variation to zero, and current loop variation to positive or zero.
3783 Save each lexico positive distance vector. */
3786 omega_extract_distance_vectors (omega_pb pb,
3787 struct data_dependence_relation *ddr)
3791 struct loop *loopi, *loopj;
3792 enum omega_result res;
3794 /* Set a new problem for each loop in the nest. The basis is the
3795 problem that we have initialized until now. On top of this we
3796 add new constraints. */
3797 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3798 && DDR_LOOP_NEST (ddr).iterate (i, &loopi); i++)
3801 omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
3802 DDR_NB_LOOPS (ddr));
3804 omega_copy_problem (copy, pb);
3806 /* For all the outer loops "loop_j", add "dj = 0". */
3807 for (j = 0; j < i && DDR_LOOP_NEST (ddr).iterate (j, &loopj); j++)
3809 eq = omega_add_zero_eq (copy, omega_black);
3810 copy->eqs[eq].coef[j + 1] = 1;
3813 /* For "loop_i", add "0 <= di". */
3814 geq = omega_add_zero_geq (copy, omega_black);
3815 copy->geqs[geq].coef[i + 1] = 1;
3817 /* Reduce the constraint system, and test that the current
3818 problem is feasible. */
3819 res = omega_simplify_problem (copy);
3820 if (res == omega_false
3821 || res == omega_unknown
3822 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3825 for (eq = 0; eq < copy->num_subs; eq++)
3826 if (copy->subs[eq].key == (int) i + 1)
3828 dist = copy->subs[eq].coef[0];
3834 /* Reinitialize problem... */
3835 omega_copy_problem (copy, pb);
3836 for (j = 0; j < i && DDR_LOOP_NEST (ddr).iterate (j, &loopj); j++)
3838 eq = omega_add_zero_eq (copy, omega_black);
3839 copy->eqs[eq].coef[j + 1] = 1;
3842 /* ..., but this time "di = 1". */
3843 eq = omega_add_zero_eq (copy, omega_black);
3844 copy->eqs[eq].coef[i + 1] = 1;
3845 copy->eqs[eq].coef[0] = -1;
3847 res = omega_simplify_problem (copy);
3848 if (res == omega_false
3849 || res == omega_unknown
3850 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3853 for (eq = 0; eq < copy->num_subs; eq++)
3854 if (copy->subs[eq].key == (int) i + 1)
3856 dist = copy->subs[eq].coef[0];
3862 /* Save the lexicographically positive distance vector. */
3865 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3866 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3870 for (eq = 0; eq < copy->num_subs; eq++)
3871 if (copy->subs[eq].key > 0)
3873 dist = copy->subs[eq].coef[0];
3874 dist_v[copy->subs[eq].key - 1] = dist;
3877 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3878 dir_v[j] = dir_from_dist (dist_v[j]);
3880 save_dist_v (ddr, dist_v);
3881 save_dir_v (ddr, dir_v);
3885 omega_free_problem (copy);
3889 /* This is called for each subscript of a tuple of data references:
3890 insert an equality for representing the conflicts. */
3893 omega_setup_subscript (tree access_fun_a, tree access_fun_b,
3894 struct data_dependence_relation *ddr,
3895 omega_pb pb, bool *maybe_dependent)
3898 tree type = signed_type_for_types (TREE_TYPE (access_fun_a),
3899 TREE_TYPE (access_fun_b));
3900 tree fun_a = chrec_convert (type, access_fun_a, NULL);
3901 tree fun_b = chrec_convert (type, access_fun_b, NULL);
3902 tree difference = chrec_fold_minus (type, fun_a, fun_b);
3905 /* When the fun_a - fun_b is not constant, the dependence is not
3906 captured by the classic distance vector representation. */
3907 if (TREE_CODE (difference) != INTEGER_CST)
3911 if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
3913 /* There is no dependence. */
3914 *maybe_dependent = false;
3918 minus_one = build_int_cst (type, -1);
3919 fun_b = chrec_fold_multiply (type, fun_b, minus_one);
3921 eq = omega_add_zero_eq (pb, omega_black);
3922 if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
3923 || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
3924 /* There is probably a dependence, but the system of
3925 constraints cannot be built: answer "don't know". */
3929 if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
3930 && !int_divides_p (lambda_vector_gcd
3931 ((lambda_vector) &(pb->eqs[eq].coef[1]),
3932 2 * DDR_NB_LOOPS (ddr)),
3933 pb->eqs[eq].coef[0]))
3935 /* There is no dependence. */
3936 *maybe_dependent = false;
3943 /* Helper function, same as init_omega_for_ddr but specialized for
3944 data references A and B. */
3947 init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
3948 struct data_dependence_relation *ddr,
3949 omega_pb pb, bool *maybe_dependent)
3954 unsigned nb_loops = DDR_NB_LOOPS (ddr);
3956 /* Insert an equality per subscript. */
3957 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3959 if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
3960 ddr, pb, maybe_dependent))
3962 else if (*maybe_dependent == false)
3964 /* There is no dependence. */
3965 DDR_ARE_DEPENDENT (ddr) = chrec_known;
3970 /* Insert inequalities: constraints corresponding to the iteration
3971 domain, i.e. the loops surrounding the references "loop_x" and
3972 the distance variables "dx". The layout of the OMEGA
3973 representation is as follows:
3974 - coef[0] is the constant
3975 - coef[1..nb_loops] are the protected variables that will not be
3976 removed by the solver: the "dx"
3977 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3979 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3980 && DDR_LOOP_NEST (ddr).iterate (i, &loopi); i++)
3982 HOST_WIDE_INT nbi = max_stmt_executions_int (loopi);
3985 ineq = omega_add_zero_geq (pb, omega_black);
3986 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3988 /* 0 <= loop_x + dx */
3989 ineq = omega_add_zero_geq (pb, omega_black);
3990 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3991 pb->geqs[ineq].coef[i + 1] = 1;
3995 /* loop_x <= nb_iters */
3996 ineq = omega_add_zero_geq (pb, omega_black);
3997 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3998 pb->geqs[ineq].coef[0] = nbi;
4000 /* loop_x + dx <= nb_iters */
4001 ineq = omega_add_zero_geq (pb, omega_black);
4002 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
4003 pb->geqs[ineq].coef[i + 1] = -1;
4004 pb->geqs[ineq].coef[0] = nbi;
4006 /* A step "dx" bigger than nb_iters is not feasible, so
4007 add "0 <= nb_iters + dx", */
4008 ineq = omega_add_zero_geq (pb, omega_black);
4009 pb->geqs[ineq].coef[i + 1] = 1;
4010 pb->geqs[ineq].coef[0] = nbi;
4011 /* and "dx <= nb_iters". */
4012 ineq = omega_add_zero_geq (pb, omega_black);
4013 pb->geqs[ineq].coef[i + 1] = -1;
4014 pb->geqs[ineq].coef[0] = nbi;
4018 omega_extract_distance_vectors (pb, ddr);
4023 /* Sets up the Omega dependence problem for the data dependence
4024 relation DDR. Returns false when the constraint system cannot be
4025 built, ie. when the test answers "don't know". Returns true
4026 otherwise, and when independence has been proved (using one of the
4027 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
4028 set MAYBE_DEPENDENT to true.
4030 Example: for setting up the dependence system corresponding to the
4031 conflicting accesses
4036 | ... A[2*j, 2*(i + j)]
4040 the following constraints come from the iteration domain:
4047 where di, dj are the distance variables. The constraints
4048 representing the conflicting elements are:
4051 i + 1 = 2 * (i + di + j + dj)
4053 For asking that the resulting distance vector (di, dj) be
4054 lexicographically positive, we insert the constraint "di >= 0". If
4055 "di = 0" in the solution, we fix that component to zero, and we
4056 look at the inner loops: we set a new problem where all the outer
4057 loop distances are zero, and fix this inner component to be
4058 positive. When one of the components is positive, we save that
4059 distance, and set a new problem where the distance on this loop is
4060 zero, searching for other distances in the inner loops. Here is
4061 the classic example that illustrates that we have to set for each
4062 inner loop a new problem:
4070 we have to save two distances (1, 0) and (0, 1).
4072 Given two array references, refA and refB, we have to set the
4073 dependence problem twice, refA vs. refB and refB vs. refA, and we
4074 cannot do a single test, as refB might occur before refA in the
4075 inner loops, and the contrary when considering outer loops: ex.
4080 | T[{1,+,1}_2][{1,+,1}_1] // refA
4081 | T[{2,+,1}_2][{0,+,1}_1] // refB
4086 refB touches the elements in T before refA, and thus for the same
4087 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
4088 but for successive loop_0 iterations, we have (1, -1, 1)
4090 The Omega solver expects the distance variables ("di" in the
4091 previous example) to come first in the constraint system (as
4092 variables to be protected, or "safe" variables), the constraint
4093 system is built using the following layout:
4095 "cst | distance vars | index vars".
4099 init_omega_for_ddr (struct data_dependence_relation *ddr,
4100 bool *maybe_dependent)
4105 *maybe_dependent = true;
4107 if (same_access_functions (ddr))
4110 lambda_vector dir_v;
4112 /* Save the 0 vector. */
4113 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
4114 dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4115 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
4116 dir_v[j] = dir_equal;
4117 save_dir_v (ddr, dir_v);
4119 /* Save the dependences carried by outer loops. */
4120 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4121 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
4123 omega_free_problem (pb);
4127 /* Omega expects the protected variables (those that have to be kept
4128 after elimination) to appear first in the constraint system.
4129 These variables are the distance variables. In the following
4130 initialization we declare NB_LOOPS safe variables, and the total
4131 number of variables for the constraint system is 2*NB_LOOPS. */
4132 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4133 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
4135 omega_free_problem (pb);
4137 /* Stop computation if not decidable, or no dependence. */
4138 if (res == false || *maybe_dependent == false)
4141 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4142 res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
4144 omega_free_problem (pb);
4149 /* Return true when DDR contains the same information as that stored
4150 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
4153 ddr_consistent_p (FILE *file,
4154 struct data_dependence_relation *ddr,
4155 vec<lambda_vector> dist_vects,
4156 vec<lambda_vector> dir_vects)
4160 /* If dump_file is set, output there. */
4161 if (dump_file && (dump_flags & TDF_DETAILS))
4164 if (dist_vects.length () != DDR_NUM_DIST_VECTS (ddr))
4166 lambda_vector b_dist_v;
4167 fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
4168 dist_vects.length (),
4169 DDR_NUM_DIST_VECTS (ddr));
4171 fprintf (file, "Banerjee dist vectors:\n");
4172 FOR_EACH_VEC_ELT (dist_vects, i, b_dist_v)
4173 print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
4175 fprintf (file, "Omega dist vectors:\n");
4176 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
4177 print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
4179 fprintf (file, "data dependence relation:\n");
4180 dump_data_dependence_relation (file, ddr);
4182 fprintf (file, ")\n");
4186 if (dir_vects.length () != DDR_NUM_DIR_VECTS (ddr))
4188 fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
4189 dir_vects.length (),
4190 DDR_NUM_DIR_VECTS (ddr));
4194 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
4196 lambda_vector a_dist_v;
4197 lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
4199 /* Distance vectors are not ordered in the same way in the DDR
4200 and in the DIST_VECTS: search for a matching vector. */
4201 FOR_EACH_VEC_ELT (dist_vects, j, a_dist_v)
4202 if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
4205 if (j == dist_vects.length ())
4207 fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
4208 print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
4209 fprintf (file, "not found in Omega dist vectors:\n");
4210 print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
4211 fprintf (file, "data dependence relation:\n");
4212 dump_data_dependence_relation (file, ddr);
4213 fprintf (file, ")\n");
4217 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
4219 lambda_vector a_dir_v;
4220 lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
4222 /* Direction vectors are not ordered in the same way in the DDR
4223 and in the DIR_VECTS: search for a matching vector. */
4224 FOR_EACH_VEC_ELT (dir_vects, j, a_dir_v)
4225 if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
4228 if (j == dist_vects.length ())
4230 fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
4231 print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
4232 fprintf (file, "not found in Omega dir vectors:\n");
4233 print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
4234 fprintf (file, "data dependence relation:\n");
4235 dump_data_dependence_relation (file, ddr);
4236 fprintf (file, ")\n");
4243 /* This computes the affine dependence relation between A and B with
4244 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
4245 independence between two accesses, while CHREC_DONT_KNOW is used
4246 for representing the unknown relation.
4248 Note that it is possible to stop the computation of the dependence
4249 relation the first time we detect a CHREC_KNOWN element for a given
4253 compute_affine_dependence (struct data_dependence_relation *ddr,
4254 struct loop *loop_nest)
4256 struct data_reference *dra = DDR_A (ddr);
4257 struct data_reference *drb = DDR_B (ddr);
4259 if (dump_file && (dump_flags & TDF_DETAILS))
4261 fprintf (dump_file, "(compute_affine_dependence\n");
4262 fprintf (dump_file, " stmt_a: ");
4263 print_gimple_stmt (dump_file, DR_STMT (dra), 0, TDF_SLIM);
4264 fprintf (dump_file, " stmt_b: ");
4265 print_gimple_stmt (dump_file, DR_STMT (drb), 0, TDF_SLIM);
4268 /* Analyze only when the dependence relation is not yet known. */
4269 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4271 dependence_stats.num_dependence_tests++;
4273 if (access_functions_are_affine_or_constant_p (dra, loop_nest)
4274 && access_functions_are_affine_or_constant_p (drb, loop_nest))
4276 subscript_dependence_tester (ddr, loop_nest);
4278 if (flag_check_data_deps)
4280 /* Dump the dependences from the first algorithm. */
4281 if (dump_file && (dump_flags & TDF_DETAILS))
4283 fprintf (dump_file, "\n\nBanerjee Analyzer\n");
4284 dump_data_dependence_relation (dump_file, ddr);
4287 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4289 bool maybe_dependent;
4290 vec<lambda_vector> dir_vects, dist_vects;
4292 /* Save the result of the first DD analyzer. */
4293 dist_vects = DDR_DIST_VECTS (ddr);
4294 dir_vects = DDR_DIR_VECTS (ddr);
4296 /* Reset the information. */
4297 DDR_DIST_VECTS (ddr).create (0);
4298 DDR_DIR_VECTS (ddr).create (0);
4300 /* Compute the same information using Omega. */
4301 if (!init_omega_for_ddr (ddr, &maybe_dependent))
4302 goto csys_dont_know;
4304 if (dump_file && (dump_flags & TDF_DETAILS))
4306 fprintf (dump_file, "Omega Analyzer\n");
4307 dump_data_dependence_relation (dump_file, ddr);
4310 /* Check that we get the same information. */
4311 if (maybe_dependent)
4312 gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
4318 /* As a last case, if the dependence cannot be determined, or if
4319 the dependence is considered too difficult to determine, answer
4324 dependence_stats.num_dependence_undetermined++;
4326 if (dump_file && (dump_flags & TDF_DETAILS))
4328 fprintf (dump_file, "Data ref a:\n");
4329 dump_data_reference (dump_file, dra);
4330 fprintf (dump_file, "Data ref b:\n");
4331 dump_data_reference (dump_file, drb);
4332 fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
4334 finalize_ddr_dependent (ddr, chrec_dont_know);
4338 if (dump_file && (dump_flags & TDF_DETAILS))
4340 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4341 fprintf (dump_file, ") -> no dependence\n");
4342 else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
4343 fprintf (dump_file, ") -> dependence analysis failed\n");
4345 fprintf (dump_file, ")\n");
4349 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4350 the data references in DATAREFS, in the LOOP_NEST. When
4351 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4352 relations. Return true when successful, i.e. data references number
4353 is small enough to be handled. */
4356 compute_all_dependences (vec<data_reference_p> datarefs,
4357 vec<ddr_p> *dependence_relations,
4358 vec<loop_p> loop_nest,
4359 bool compute_self_and_rr)
4361 struct data_dependence_relation *ddr;
4362 struct data_reference *a, *b;
4365 if ((int) datarefs.length ()
4366 > PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS))
4368 struct data_dependence_relation *ddr;
4370 /* Insert a single relation into dependence_relations:
4372 ddr = initialize_data_dependence_relation (NULL, NULL, loop_nest);
4373 dependence_relations->safe_push (ddr);
4377 FOR_EACH_VEC_ELT (datarefs, i, a)
4378 for (j = i + 1; datarefs.iterate (j, &b); j++)
4379 if (DR_IS_WRITE (a) || DR_IS_WRITE (b) || compute_self_and_rr)
4381 ddr = initialize_data_dependence_relation (a, b, loop_nest);
4382 dependence_relations->safe_push (ddr);
4383 if (loop_nest.exists ())
4384 compute_affine_dependence (ddr, loop_nest[0]);
4387 if (compute_self_and_rr)
4388 FOR_EACH_VEC_ELT (datarefs, i, a)
4390 ddr = initialize_data_dependence_relation (a, a, loop_nest);
4391 dependence_relations->safe_push (ddr);
4392 if (loop_nest.exists ())
4393 compute_affine_dependence (ddr, loop_nest[0]);
4399 /* Describes a location of a memory reference. */
4401 typedef struct data_ref_loc_d
4403 /* The memory reference. */
4406 /* True if the memory reference is read. */
4411 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4412 true if STMT clobbers memory, false otherwise. */
4415 get_references_in_stmt (gimple stmt, vec<data_ref_loc, va_heap> *references)
4417 bool clobbers_memory = false;
4420 enum gimple_code stmt_code = gimple_code (stmt);
4422 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4423 As we cannot model data-references to not spelled out
4424 accesses give up if they may occur. */
4425 if (stmt_code == GIMPLE_CALL
4426 && !(gimple_call_flags (stmt) & ECF_CONST))
4428 /* Allow IFN_GOMP_SIMD_LANE in their own loops. */
4429 if (gimple_call_internal_p (stmt))
4430 switch (gimple_call_internal_fn (stmt))
4432 case IFN_GOMP_SIMD_LANE:
4434 struct loop *loop = gimple_bb (stmt)->loop_father;
4435 tree uid = gimple_call_arg (stmt, 0);
4436 gcc_assert (TREE_CODE (uid) == SSA_NAME);
4438 || loop->simduid != SSA_NAME_VAR (uid))
4439 clobbers_memory = true;
4443 case IFN_MASK_STORE:
4446 clobbers_memory = true;
4450 clobbers_memory = true;
4452 else if (stmt_code == GIMPLE_ASM
4453 && (gimple_asm_volatile_p (as_a <gasm *> (stmt))
4454 || gimple_vuse (stmt)))
4455 clobbers_memory = true;
4457 if (!gimple_vuse (stmt))
4458 return clobbers_memory;
4460 if (stmt_code == GIMPLE_ASSIGN)
4463 op0 = gimple_assign_lhs (stmt);
4464 op1 = gimple_assign_rhs1 (stmt);
4467 || (REFERENCE_CLASS_P (op1)
4468 && (base = get_base_address (op1))
4469 && TREE_CODE (base) != SSA_NAME))
4473 references->safe_push (ref);
4476 else if (stmt_code == GIMPLE_CALL)
4480 ref.is_read = false;
4481 if (gimple_call_internal_p (stmt))
4482 switch (gimple_call_internal_fn (stmt))
4485 if (gimple_call_lhs (stmt) == NULL_TREE)
4488 case IFN_MASK_STORE:
4489 ref.ref = fold_build2 (MEM_REF,
4491 ? TREE_TYPE (gimple_call_lhs (stmt))
4492 : TREE_TYPE (gimple_call_arg (stmt, 3)),
4493 gimple_call_arg (stmt, 0),
4494 gimple_call_arg (stmt, 1));
4495 references->safe_push (ref);
4501 op0 = gimple_call_lhs (stmt);
4502 n = gimple_call_num_args (stmt);
4503 for (i = 0; i < n; i++)
4505 op1 = gimple_call_arg (stmt, i);
4508 || (REFERENCE_CLASS_P (op1) && get_base_address (op1)))
4512 references->safe_push (ref);
4517 return clobbers_memory;
4521 || (REFERENCE_CLASS_P (op0) && get_base_address (op0))))
4524 ref.is_read = false;
4525 references->safe_push (ref);
4527 return clobbers_memory;
4530 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4531 reference, returns false, otherwise returns true. NEST is the outermost
4532 loop of the loop nest in which the references should be analyzed. */
4535 find_data_references_in_stmt (struct loop *nest, gimple stmt,
4536 vec<data_reference_p> *datarefs)
4539 auto_vec<data_ref_loc, 2> references;
4542 data_reference_p dr;
4544 if (get_references_in_stmt (stmt, &references))
4547 FOR_EACH_VEC_ELT (references, i, ref)
4549 dr = create_data_ref (nest, loop_containing_stmt (stmt),
4550 ref->ref, stmt, ref->is_read);
4551 gcc_assert (dr != NULL);
4552 datarefs->safe_push (dr);
4554 references.release ();
4558 /* Stores the data references in STMT to DATAREFS. If there is an
4559 unanalyzable reference, returns false, otherwise returns true.
4560 NEST is the outermost loop of the loop nest in which the references
4561 should be instantiated, LOOP is the loop in which the references
4562 should be analyzed. */
4565 graphite_find_data_references_in_stmt (loop_p nest, loop_p loop, gimple stmt,
4566 vec<data_reference_p> *datarefs)
4569 auto_vec<data_ref_loc, 2> references;
4572 data_reference_p dr;
4574 if (get_references_in_stmt (stmt, &references))
4577 FOR_EACH_VEC_ELT (references, i, ref)
4579 dr = create_data_ref (nest, loop, ref->ref, stmt, ref->is_read);
4580 gcc_assert (dr != NULL);
4581 datarefs->safe_push (dr);
4584 references.release ();
4588 /* Search the data references in LOOP, and record the information into
4589 DATAREFS. Returns chrec_dont_know when failing to analyze a
4590 difficult case, returns NULL_TREE otherwise. */
4593 find_data_references_in_bb (struct loop *loop, basic_block bb,
4594 vec<data_reference_p> *datarefs)
4596 gimple_stmt_iterator bsi;
4598 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4600 gimple stmt = gsi_stmt (bsi);
4602 if (!find_data_references_in_stmt (loop, stmt, datarefs))
4604 struct data_reference *res;
4605 res = XCNEW (struct data_reference);
4606 datarefs->safe_push (res);
4608 return chrec_dont_know;
4615 /* Search the data references in LOOP, and record the information into
4616 DATAREFS. Returns chrec_dont_know when failing to analyze a
4617 difficult case, returns NULL_TREE otherwise.
4619 TODO: This function should be made smarter so that it can handle address
4620 arithmetic as if they were array accesses, etc. */
4623 find_data_references_in_loop (struct loop *loop,
4624 vec<data_reference_p> *datarefs)
4626 basic_block bb, *bbs;
4629 bbs = get_loop_body_in_dom_order (loop);
4631 for (i = 0; i < loop->num_nodes; i++)
4635 if (find_data_references_in_bb (loop, bb, datarefs) == chrec_dont_know)
4638 return chrec_dont_know;
4646 /* Recursive helper function. */
4649 find_loop_nest_1 (struct loop *loop, vec<loop_p> *loop_nest)
4651 /* Inner loops of the nest should not contain siblings. Example:
4652 when there are two consecutive loops,
4663 the dependence relation cannot be captured by the distance
4668 loop_nest->safe_push (loop);
4670 return find_loop_nest_1 (loop->inner, loop_nest);
4674 /* Return false when the LOOP is not well nested. Otherwise return
4675 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4676 contain the loops from the outermost to the innermost, as they will
4677 appear in the classic distance vector. */
4680 find_loop_nest (struct loop *loop, vec<loop_p> *loop_nest)
4682 loop_nest->safe_push (loop);
4684 return find_loop_nest_1 (loop->inner, loop_nest);
4688 /* Returns true when the data dependences have been computed, false otherwise.
4689 Given a loop nest LOOP, the following vectors are returned:
4690 DATAREFS is initialized to all the array elements contained in this loop,
4691 DEPENDENCE_RELATIONS contains the relations between the data references.
4692 Compute read-read and self relations if
4693 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4696 compute_data_dependences_for_loop (struct loop *loop,
4697 bool compute_self_and_read_read_dependences,
4698 vec<loop_p> *loop_nest,
4699 vec<data_reference_p> *datarefs,
4700 vec<ddr_p> *dependence_relations)
4704 memset (&dependence_stats, 0, sizeof (dependence_stats));
4706 /* If the loop nest is not well formed, or one of the data references
4707 is not computable, give up without spending time to compute other
4710 || !find_loop_nest (loop, loop_nest)
4711 || find_data_references_in_loop (loop, datarefs) == chrec_dont_know
4712 || !compute_all_dependences (*datarefs, dependence_relations, *loop_nest,
4713 compute_self_and_read_read_dependences))
4716 if (dump_file && (dump_flags & TDF_STATS))
4718 fprintf (dump_file, "Dependence tester statistics:\n");
4720 fprintf (dump_file, "Number of dependence tests: %d\n",
4721 dependence_stats.num_dependence_tests);
4722 fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4723 dependence_stats.num_dependence_dependent);
4724 fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4725 dependence_stats.num_dependence_independent);
4726 fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4727 dependence_stats.num_dependence_undetermined);
4729 fprintf (dump_file, "Number of subscript tests: %d\n",
4730 dependence_stats.num_subscript_tests);
4731 fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4732 dependence_stats.num_subscript_undetermined);
4733 fprintf (dump_file, "Number of same subscript function: %d\n",
4734 dependence_stats.num_same_subscript_function);
4736 fprintf (dump_file, "Number of ziv tests: %d\n",
4737 dependence_stats.num_ziv);
4738 fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4739 dependence_stats.num_ziv_dependent);
4740 fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4741 dependence_stats.num_ziv_independent);
4742 fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4743 dependence_stats.num_ziv_unimplemented);
4745 fprintf (dump_file, "Number of siv tests: %d\n",
4746 dependence_stats.num_siv);
4747 fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4748 dependence_stats.num_siv_dependent);
4749 fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4750 dependence_stats.num_siv_independent);
4751 fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4752 dependence_stats.num_siv_unimplemented);
4754 fprintf (dump_file, "Number of miv tests: %d\n",
4755 dependence_stats.num_miv);
4756 fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4757 dependence_stats.num_miv_dependent);
4758 fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4759 dependence_stats.num_miv_independent);
4760 fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4761 dependence_stats.num_miv_unimplemented);
4767 /* Returns true when the data dependences for the basic block BB have been
4768 computed, false otherwise.
4769 DATAREFS is initialized to all the array elements contained in this basic
4770 block, DEPENDENCE_RELATIONS contains the relations between the data
4771 references. Compute read-read and self relations if
4772 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4774 compute_data_dependences_for_bb (basic_block bb,
4775 bool compute_self_and_read_read_dependences,
4776 vec<data_reference_p> *datarefs,
4777 vec<ddr_p> *dependence_relations)
4779 if (find_data_references_in_bb (NULL, bb, datarefs) == chrec_dont_know)
4782 return compute_all_dependences (*datarefs, dependence_relations, vNULL,
4783 compute_self_and_read_read_dependences);
4786 /* Entry point (for testing only). Analyze all the data references
4787 and the dependence relations in LOOP.
4789 The data references are computed first.
4791 A relation on these nodes is represented by a complete graph. Some
4792 of the relations could be of no interest, thus the relations can be
4795 In the following function we compute all the relations. This is
4796 just a first implementation that is here for:
4797 - for showing how to ask for the dependence relations,
4798 - for the debugging the whole dependence graph,
4799 - for the dejagnu testcases and maintenance.
4801 It is possible to ask only for a part of the graph, avoiding to
4802 compute the whole dependence graph. The computed dependences are
4803 stored in a knowledge base (KB) such that later queries don't
4804 recompute the same information. The implementation of this KB is
4805 transparent to the optimizer, and thus the KB can be changed with a
4806 more efficient implementation, or the KB could be disabled. */
4808 analyze_all_data_dependences (struct loop *loop)
4811 int nb_data_refs = 10;
4812 vec<data_reference_p> datarefs;
4813 datarefs.create (nb_data_refs);
4814 vec<ddr_p> dependence_relations;
4815 dependence_relations.create (nb_data_refs * nb_data_refs);
4816 vec<loop_p> loop_nest;
4817 loop_nest.create (3);
4819 /* Compute DDs on the whole function. */
4820 compute_data_dependences_for_loop (loop, false, &loop_nest, &datarefs,
4821 &dependence_relations);
4825 dump_data_dependence_relations (dump_file, dependence_relations);
4826 fprintf (dump_file, "\n\n");
4828 if (dump_flags & TDF_DETAILS)
4829 dump_dist_dir_vectors (dump_file, dependence_relations);
4831 if (dump_flags & TDF_STATS)
4833 unsigned nb_top_relations = 0;
4834 unsigned nb_bot_relations = 0;
4835 unsigned nb_chrec_relations = 0;
4836 struct data_dependence_relation *ddr;
4838 FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
4840 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4843 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4847 nb_chrec_relations++;
4850 gather_stats_on_scev_database ();
4854 loop_nest.release ();
4855 free_dependence_relations (dependence_relations);
4856 free_data_refs (datarefs);
4859 /* Computes all the data dependences and check that the results of
4860 several analyzers are the same. */
4863 tree_check_data_deps (void)
4865 struct loop *loop_nest;
4867 FOR_EACH_LOOP (loop_nest, 0)
4868 analyze_all_data_dependences (loop_nest);
4871 /* Free the memory used by a data dependence relation DDR. */
4874 free_dependence_relation (struct data_dependence_relation *ddr)
4879 if (DDR_SUBSCRIPTS (ddr).exists ())
4880 free_subscripts (DDR_SUBSCRIPTS (ddr));
4881 DDR_DIST_VECTS (ddr).release ();
4882 DDR_DIR_VECTS (ddr).release ();
4887 /* Free the memory used by the data dependence relations from
4888 DEPENDENCE_RELATIONS. */
4891 free_dependence_relations (vec<ddr_p> dependence_relations)
4894 struct data_dependence_relation *ddr;
4896 FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
4898 free_dependence_relation (ddr);
4900 dependence_relations.release ();
4903 /* Free the memory used by the data references from DATAREFS. */
4906 free_data_refs (vec<data_reference_p> datarefs)
4909 struct data_reference *dr;
4911 FOR_EACH_VEC_ELT (datarefs, i, dr)
4913 datarefs.release ();