1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This pass walks a given loop structure searching for array
23 references. The information about the array accesses is recorded
24 in DATA_REFERENCE structures.
26 The basic test for determining the dependences is:
27 given two access functions chrec1 and chrec2 to a same array, and
28 x and y two vectors from the iteration domain, the same element of
29 the array is accessed twice at iterations x and y if and only if:
30 | chrec1 (x) == chrec2 (y).
32 The goals of this analysis are:
34 - to determine the independence: the relation between two
35 independent accesses is qualified with the chrec_known (this
36 information allows a loop parallelization),
38 - when two data references access the same data, to qualify the
39 dependence relation with classic dependence representations:
43 - loop carried level dependence
44 - polyhedron dependence
45 or with the chains of recurrences based representation,
47 - to define a knowledge base for storing the data dependence
50 - to define an interface to access this data.
55 - subscript: given two array accesses a subscript is the tuple
56 composed of the access functions for a given dimension. Example:
57 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
58 (f1, g1), (f2, g2), (f3, g3).
60 - Diophantine equation: an equation whose coefficients and
61 solutions are integer constants, for example the equation
63 has an integer solution x = 1 and y = -1.
67 - "Advanced Compilation for High Performance Computing" by Randy
68 Allen and Ken Kennedy.
69 http://citeseer.ist.psu.edu/goff91practical.html
71 - "Loop Transformations for Restructuring Compilers - The Foundations"
79 #include "coretypes.h"
80 #include "gimple-pretty-print.h"
81 #include "tree-flow.h"
83 #include "tree-data-ref.h"
84 #include "tree-scalar-evolution.h"
85 #include "tree-pass.h"
86 #include "langhooks.h"
87 #include "tree-affine.h"
90 static struct datadep_stats
92 int num_dependence_tests;
93 int num_dependence_dependent;
94 int num_dependence_independent;
95 int num_dependence_undetermined;
97 int num_subscript_tests;
98 int num_subscript_undetermined;
99 int num_same_subscript_function;
102 int num_ziv_independent;
103 int num_ziv_dependent;
104 int num_ziv_unimplemented;
107 int num_siv_independent;
108 int num_siv_dependent;
109 int num_siv_unimplemented;
112 int num_miv_independent;
113 int num_miv_dependent;
114 int num_miv_unimplemented;
117 static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
118 struct data_reference *,
119 struct data_reference *,
121 /* Returns true iff A divides B. */
124 tree_fold_divides_p (const_tree a, const_tree b)
126 gcc_assert (TREE_CODE (a) == INTEGER_CST);
127 gcc_assert (TREE_CODE (b) == INTEGER_CST);
128 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a));
131 /* Returns true iff A divides B. */
134 int_divides_p (int a, int b)
136 return ((b % a) == 0);
141 /* Dump into FILE all the data references from DATAREFS. */
144 dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
147 struct data_reference *dr;
149 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
150 dump_data_reference (file, dr);
153 /* Dump into STDERR all the data references from DATAREFS. */
156 debug_data_references (VEC (data_reference_p, heap) *datarefs)
158 dump_data_references (stderr, datarefs);
161 /* Dump to STDERR all the dependence relations from DDRS. */
164 debug_data_dependence_relations (VEC (ddr_p, heap) *ddrs)
166 dump_data_dependence_relations (stderr, ddrs);
169 /* Dump into FILE all the dependence relations from DDRS. */
172 dump_data_dependence_relations (FILE *file,
173 VEC (ddr_p, heap) *ddrs)
176 struct data_dependence_relation *ddr;
178 FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
179 dump_data_dependence_relation (file, ddr);
182 /* Print to STDERR the data_reference DR. */
185 debug_data_reference (struct data_reference *dr)
187 dump_data_reference (stderr, dr);
190 /* Dump function for a DATA_REFERENCE structure. */
193 dump_data_reference (FILE *outf,
194 struct data_reference *dr)
198 fprintf (outf, "#(Data Ref: \n");
199 fprintf (outf, "# bb: %d \n", gimple_bb (DR_STMT (dr))->index);
200 fprintf (outf, "# stmt: ");
201 print_gimple_stmt (outf, DR_STMT (dr), 0, 0);
202 fprintf (outf, "# ref: ");
203 print_generic_stmt (outf, DR_REF (dr), 0);
204 fprintf (outf, "# base_object: ");
205 print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
207 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
209 fprintf (outf, "# Access function %d: ", i);
210 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
212 fprintf (outf, "#)\n");
215 /* Dumps the affine function described by FN to the file OUTF. */
218 dump_affine_function (FILE *outf, affine_fn fn)
223 print_generic_expr (outf, VEC_index (tree, fn, 0), TDF_SLIM);
224 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
226 fprintf (outf, " + ");
227 print_generic_expr (outf, coef, TDF_SLIM);
228 fprintf (outf, " * x_%u", i);
232 /* Dumps the conflict function CF to the file OUTF. */
235 dump_conflict_function (FILE *outf, conflict_function *cf)
239 if (cf->n == NO_DEPENDENCE)
240 fprintf (outf, "no dependence\n");
241 else if (cf->n == NOT_KNOWN)
242 fprintf (outf, "not known\n");
245 for (i = 0; i < cf->n; i++)
248 dump_affine_function (outf, cf->fns[i]);
249 fprintf (outf, "]\n");
254 /* Dump function for a SUBSCRIPT structure. */
257 dump_subscript (FILE *outf, struct subscript *subscript)
259 conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
261 fprintf (outf, "\n (subscript \n");
262 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
263 dump_conflict_function (outf, cf);
264 if (CF_NONTRIVIAL_P (cf))
266 tree last_iteration = SUB_LAST_CONFLICT (subscript);
267 fprintf (outf, " last_conflict: ");
268 print_generic_stmt (outf, last_iteration, 0);
271 cf = SUB_CONFLICTS_IN_B (subscript);
272 fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
273 dump_conflict_function (outf, cf);
274 if (CF_NONTRIVIAL_P (cf))
276 tree last_iteration = SUB_LAST_CONFLICT (subscript);
277 fprintf (outf, " last_conflict: ");
278 print_generic_stmt (outf, last_iteration, 0);
281 fprintf (outf, " (Subscript distance: ");
282 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
283 fprintf (outf, " )\n");
284 fprintf (outf, " )\n");
287 /* Print the classic direction vector DIRV to OUTF. */
290 print_direction_vector (FILE *outf,
296 for (eq = 0; eq < length; eq++)
298 enum data_dependence_direction dir = ((enum data_dependence_direction)
304 fprintf (outf, " +");
307 fprintf (outf, " -");
310 fprintf (outf, " =");
312 case dir_positive_or_equal:
313 fprintf (outf, " +=");
315 case dir_positive_or_negative:
316 fprintf (outf, " +-");
318 case dir_negative_or_equal:
319 fprintf (outf, " -=");
322 fprintf (outf, " *");
325 fprintf (outf, "indep");
329 fprintf (outf, "\n");
332 /* Print a vector of direction vectors. */
335 print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
341 FOR_EACH_VEC_ELT (lambda_vector, dir_vects, j, v)
342 print_direction_vector (outf, v, length);
345 /* Print out a vector VEC of length N to OUTFILE. */
348 print_lambda_vector (FILE * outfile, lambda_vector vector, int n)
352 for (i = 0; i < n; i++)
353 fprintf (outfile, "%3d ", vector[i]);
354 fprintf (outfile, "\n");
357 /* Print a vector of distance vectors. */
360 print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
366 FOR_EACH_VEC_ELT (lambda_vector, dist_vects, j, v)
367 print_lambda_vector (outf, v, length);
373 debug_data_dependence_relation (struct data_dependence_relation *ddr)
375 dump_data_dependence_relation (stderr, ddr);
378 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
381 dump_data_dependence_relation (FILE *outf,
382 struct data_dependence_relation *ddr)
384 struct data_reference *dra, *drb;
386 fprintf (outf, "(Data Dep: \n");
388 if (!ddr || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
395 dump_data_reference (outf, dra);
397 fprintf (outf, " (nil)\n");
399 dump_data_reference (outf, drb);
401 fprintf (outf, " (nil)\n");
403 fprintf (outf, " (don't know)\n)\n");
409 dump_data_reference (outf, dra);
410 dump_data_reference (outf, drb);
412 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
413 fprintf (outf, " (no dependence)\n");
415 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
420 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
422 fprintf (outf, " access_fn_A: ");
423 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
424 fprintf (outf, " access_fn_B: ");
425 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
426 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
429 fprintf (outf, " inner loop index: %d\n", DDR_INNER_LOOP (ddr));
430 fprintf (outf, " loop nest: (");
431 FOR_EACH_VEC_ELT (loop_p, DDR_LOOP_NEST (ddr), i, loopi)
432 fprintf (outf, "%d ", loopi->num);
433 fprintf (outf, ")\n");
435 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
437 fprintf (outf, " distance_vector: ");
438 print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
442 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
444 fprintf (outf, " direction_vector: ");
445 print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
450 fprintf (outf, ")\n");
453 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
456 dump_data_dependence_direction (FILE *file,
457 enum data_dependence_direction dir)
473 case dir_positive_or_negative:
474 fprintf (file, "+-");
477 case dir_positive_or_equal:
478 fprintf (file, "+=");
481 case dir_negative_or_equal:
482 fprintf (file, "-=");
494 /* Dumps the distance and direction vectors in FILE. DDRS contains
495 the dependence relations, and VECT_SIZE is the size of the
496 dependence vectors, or in other words the number of loops in the
500 dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
503 struct data_dependence_relation *ddr;
506 FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
507 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
509 FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), j, v)
511 fprintf (file, "DISTANCE_V (");
512 print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
513 fprintf (file, ")\n");
516 FOR_EACH_VEC_ELT (lambda_vector, DDR_DIR_VECTS (ddr), j, v)
518 fprintf (file, "DIRECTION_V (");
519 print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
520 fprintf (file, ")\n");
524 fprintf (file, "\n\n");
527 /* Dumps the data dependence relations DDRS in FILE. */
530 dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
533 struct data_dependence_relation *ddr;
535 FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
536 dump_data_dependence_relation (file, ddr);
538 fprintf (file, "\n\n");
541 /* Helper function for split_constant_offset. Expresses OP0 CODE OP1
542 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
543 constant of type ssizetype, and returns true. If we cannot do this
544 with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
548 split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
549 tree *var, tree *off)
553 enum tree_code ocode = code;
561 *var = build_int_cst (type, 0);
562 *off = fold_convert (ssizetype, op0);
565 case POINTER_PLUS_EXPR:
570 split_constant_offset (op0, &var0, &off0);
571 split_constant_offset (op1, &var1, &off1);
572 *var = fold_build2 (code, type, var0, var1);
573 *off = size_binop (ocode, off0, off1);
577 if (TREE_CODE (op1) != INTEGER_CST)
580 split_constant_offset (op0, &var0, &off0);
581 *var = fold_build2 (MULT_EXPR, type, var0, op1);
582 *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, op1));
588 HOST_WIDE_INT pbitsize, pbitpos;
589 enum machine_mode pmode;
590 int punsignedp, pvolatilep;
592 op0 = TREE_OPERAND (op0, 0);
593 base = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset,
594 &pmode, &punsignedp, &pvolatilep, false);
596 if (pbitpos % BITS_PER_UNIT != 0)
598 base = build_fold_addr_expr (base);
599 off0 = ssize_int (pbitpos / BITS_PER_UNIT);
603 split_constant_offset (poffset, &poffset, &off1);
604 off0 = size_binop (PLUS_EXPR, off0, off1);
605 if (POINTER_TYPE_P (TREE_TYPE (base)))
606 base = fold_build_pointer_plus (base, poffset);
608 base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base,
609 fold_convert (TREE_TYPE (base), poffset));
612 var0 = fold_convert (type, base);
614 /* If variable length types are involved, punt, otherwise casts
615 might be converted into ARRAY_REFs in gimplify_conversion.
616 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
617 possibly no longer appears in current GIMPLE, might resurface.
618 This perhaps could run
619 if (CONVERT_EXPR_P (var0))
621 gimplify_conversion (&var0);
622 // Attempt to fill in any within var0 found ARRAY_REF's
623 // element size from corresponding op embedded ARRAY_REF,
624 // if unsuccessful, just punt.
626 while (POINTER_TYPE_P (type))
627 type = TREE_TYPE (type);
628 if (int_size_in_bytes (type) < 0)
638 gimple def_stmt = SSA_NAME_DEF_STMT (op0);
639 enum tree_code subcode;
641 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
644 var0 = gimple_assign_rhs1 (def_stmt);
645 subcode = gimple_assign_rhs_code (def_stmt);
646 var1 = gimple_assign_rhs2 (def_stmt);
648 return split_constant_offset_1 (type, var0, subcode, var1, var, off);
652 /* We must not introduce undefined overflow, and we must not change the value.
653 Hence we're okay if the inner type doesn't overflow to start with
654 (pointer or signed), the outer type also is an integer or pointer
655 and the outer precision is at least as large as the inner. */
656 tree itype = TREE_TYPE (op0);
657 if ((POINTER_TYPE_P (itype)
658 || (INTEGRAL_TYPE_P (itype) && TYPE_OVERFLOW_UNDEFINED (itype)))
659 && TYPE_PRECISION (type) >= TYPE_PRECISION (itype)
660 && (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type)))
662 split_constant_offset (op0, &var0, off);
663 *var = fold_convert (type, var0);
674 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
675 will be ssizetype. */
678 split_constant_offset (tree exp, tree *var, tree *off)
680 tree type = TREE_TYPE (exp), otype, op0, op1, e, o;
684 *off = ssize_int (0);
687 if (tree_is_chrec (exp)
688 || get_gimple_rhs_class (TREE_CODE (exp)) == GIMPLE_TERNARY_RHS)
691 otype = TREE_TYPE (exp);
692 code = TREE_CODE (exp);
693 extract_ops_from_tree (exp, &code, &op0, &op1);
694 if (split_constant_offset_1 (otype, op0, code, op1, &e, &o))
696 *var = fold_convert (type, e);
701 /* Returns the address ADDR of an object in a canonical shape (without nop
702 casts, and with type of pointer to the object). */
705 canonicalize_base_object_address (tree addr)
711 /* The base address may be obtained by casting from integer, in that case
713 if (!POINTER_TYPE_P (TREE_TYPE (addr)))
716 if (TREE_CODE (addr) != ADDR_EXPR)
719 return build_fold_addr_expr (TREE_OPERAND (addr, 0));
722 /* Analyzes the behavior of the memory reference DR in the innermost loop or
723 basic block that contains it. Returns true if analysis succeed or false
727 dr_analyze_innermost (struct data_reference *dr, struct loop *nest)
729 gimple stmt = DR_STMT (dr);
730 struct loop *loop = loop_containing_stmt (stmt);
731 tree ref = DR_REF (dr);
732 HOST_WIDE_INT pbitsize, pbitpos;
734 enum machine_mode pmode;
735 int punsignedp, pvolatilep;
736 affine_iv base_iv, offset_iv;
737 tree init, dinit, step;
738 bool in_loop = (loop && loop->num);
740 if (dump_file && (dump_flags & TDF_DETAILS))
741 fprintf (dump_file, "analyze_innermost: ");
743 base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset,
744 &pmode, &punsignedp, &pvolatilep, false);
745 gcc_assert (base != NULL_TREE);
747 if (pbitpos % BITS_PER_UNIT != 0)
749 if (dump_file && (dump_flags & TDF_DETAILS))
750 fprintf (dump_file, "failed: bit offset alignment.\n");
754 if (TREE_CODE (base) == MEM_REF)
756 if (!integer_zerop (TREE_OPERAND (base, 1)))
760 double_int moff = mem_ref_offset (base);
761 poffset = double_int_to_tree (sizetype, moff);
764 poffset = size_binop (PLUS_EXPR, poffset, TREE_OPERAND (base, 1));
766 base = TREE_OPERAND (base, 0);
769 base = build_fold_addr_expr (base);
773 if (!simple_iv (loop, loop_containing_stmt (stmt), base, &base_iv,
778 if (dump_file && (dump_flags & TDF_DETAILS))
779 fprintf (dump_file, "failed: evolution of base is not"
786 base_iv.step = ssize_int (0);
787 base_iv.no_overflow = true;
794 base_iv.step = ssize_int (0);
795 base_iv.no_overflow = true;
800 offset_iv.base = ssize_int (0);
801 offset_iv.step = ssize_int (0);
807 offset_iv.base = poffset;
808 offset_iv.step = ssize_int (0);
810 else if (!simple_iv (loop, loop_containing_stmt (stmt),
811 poffset, &offset_iv, false))
815 if (dump_file && (dump_flags & TDF_DETAILS))
816 fprintf (dump_file, "failed: evolution of offset is not"
822 offset_iv.base = poffset;
823 offset_iv.step = ssize_int (0);
828 init = ssize_int (pbitpos / BITS_PER_UNIT);
829 split_constant_offset (base_iv.base, &base_iv.base, &dinit);
830 init = size_binop (PLUS_EXPR, init, dinit);
831 split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
832 init = size_binop (PLUS_EXPR, init, dinit);
834 step = size_binop (PLUS_EXPR,
835 fold_convert (ssizetype, base_iv.step),
836 fold_convert (ssizetype, offset_iv.step));
838 DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base);
840 DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base);
844 DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base));
846 if (dump_file && (dump_flags & TDF_DETAILS))
847 fprintf (dump_file, "success.\n");
852 /* Determines the base object and the list of indices of memory reference
853 DR, analyzed in LOOP and instantiated in loop nest NEST. */
856 dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
858 VEC (tree, heap) *access_fns = NULL;
860 tree base, off, access_fn;
861 basic_block before_loop;
863 /* If analyzing a basic-block there are no indices to analyze
864 and thus no access functions. */
867 DR_BASE_OBJECT (dr) = DR_REF (dr);
868 DR_ACCESS_FNS (dr) = NULL;
873 before_loop = block_before_loop (nest);
875 /* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses
876 into a two element array with a constant index. The base is
877 then just the immediate underlying object. */
878 if (TREE_CODE (ref) == REALPART_EXPR)
880 ref = TREE_OPERAND (ref, 0);
881 VEC_safe_push (tree, heap, access_fns, integer_zero_node);
883 else if (TREE_CODE (ref) == IMAGPART_EXPR)
885 ref = TREE_OPERAND (ref, 0);
886 VEC_safe_push (tree, heap, access_fns, integer_one_node);
889 /* Analyze access functions of dimensions we know to be independent. */
890 while (handled_component_p (ref))
892 if (TREE_CODE (ref) == ARRAY_REF)
894 op = TREE_OPERAND (ref, 1);
895 access_fn = analyze_scalar_evolution (loop, op);
896 access_fn = instantiate_scev (before_loop, loop, access_fn);
897 VEC_safe_push (tree, heap, access_fns, access_fn);
899 else if (TREE_CODE (ref) == COMPONENT_REF
900 && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 0))) == RECORD_TYPE)
902 /* For COMPONENT_REFs of records (but not unions!) use the
903 FIELD_DECL offset as constant access function so we can
904 disambiguate a[i].f1 and a[i].f2. */
905 tree off = component_ref_field_offset (ref);
906 off = size_binop (PLUS_EXPR,
907 size_binop (MULT_EXPR,
908 fold_convert (bitsizetype, off),
909 bitsize_int (BITS_PER_UNIT)),
910 DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1)));
911 VEC_safe_push (tree, heap, access_fns, off);
914 /* If we have an unhandled component we could not translate
915 to an access function stop analyzing. We have determined
916 our base object in this case. */
919 ref = TREE_OPERAND (ref, 0);
922 /* If the address operand of a MEM_REF base has an evolution in the
923 analyzed nest, add it as an additional independent access-function. */
924 if (TREE_CODE (ref) == MEM_REF)
926 op = TREE_OPERAND (ref, 0);
927 access_fn = analyze_scalar_evolution (loop, op);
928 access_fn = instantiate_scev (before_loop, loop, access_fn);
929 if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
932 tree memoff = TREE_OPERAND (ref, 1);
933 base = initial_condition (access_fn);
934 orig_type = TREE_TYPE (base);
935 STRIP_USELESS_TYPE_CONVERSION (base);
936 split_constant_offset (base, &base, &off);
937 /* Fold the MEM_REF offset into the evolutions initial
938 value to make more bases comparable. */
939 if (!integer_zerop (memoff))
941 off = size_binop (PLUS_EXPR, off,
942 fold_convert (ssizetype, memoff));
943 memoff = build_int_cst (TREE_TYPE (memoff), 0);
945 access_fn = chrec_replace_initial_condition
946 (access_fn, fold_convert (orig_type, off));
947 /* ??? This is still not a suitable base object for
948 dr_may_alias_p - the base object needs to be an
949 access that covers the object as whole. With
950 an evolution in the pointer this cannot be
952 As a band-aid, mark the access so we can special-case
953 it in dr_may_alias_p. */
954 ref = fold_build2_loc (EXPR_LOCATION (ref),
955 MEM_REF, TREE_TYPE (ref),
957 DR_UNCONSTRAINED_BASE (dr) = true;
958 VEC_safe_push (tree, heap, access_fns, access_fn);
961 else if (DECL_P (ref))
963 /* Canonicalize DR_BASE_OBJECT to MEM_REF form. */
964 ref = build2 (MEM_REF, TREE_TYPE (ref),
965 build_fold_addr_expr (ref),
966 build_int_cst (reference_alias_ptr_type (ref), 0));
969 DR_BASE_OBJECT (dr) = ref;
970 DR_ACCESS_FNS (dr) = access_fns;
973 /* Extracts the alias analysis information from the memory reference DR. */
976 dr_analyze_alias (struct data_reference *dr)
978 tree ref = DR_REF (dr);
979 tree base = get_base_address (ref), addr;
981 if (INDIRECT_REF_P (base)
982 || TREE_CODE (base) == MEM_REF)
984 addr = TREE_OPERAND (base, 0);
985 if (TREE_CODE (addr) == SSA_NAME)
986 DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
990 /* Frees data reference DR. */
993 free_data_ref (data_reference_p dr)
995 VEC_free (tree, heap, DR_ACCESS_FNS (dr));
999 /* Analyzes memory reference MEMREF accessed in STMT. The reference
1000 is read if IS_READ is true, write otherwise. Returns the
1001 data_reference description of MEMREF. NEST is the outermost loop
1002 in which the reference should be instantiated, LOOP is the loop in
1003 which the data reference should be analyzed. */
1005 struct data_reference *
1006 create_data_ref (loop_p nest, loop_p loop, tree memref, gimple stmt,
1009 struct data_reference *dr;
1011 if (dump_file && (dump_flags & TDF_DETAILS))
1013 fprintf (dump_file, "Creating dr for ");
1014 print_generic_expr (dump_file, memref, TDF_SLIM);
1015 fprintf (dump_file, "\n");
1018 dr = XCNEW (struct data_reference);
1019 DR_STMT (dr) = stmt;
1020 DR_REF (dr) = memref;
1021 DR_IS_READ (dr) = is_read;
1023 dr_analyze_innermost (dr, nest);
1024 dr_analyze_indices (dr, nest, loop);
1025 dr_analyze_alias (dr);
1027 if (dump_file && (dump_flags & TDF_DETAILS))
1030 fprintf (dump_file, "\tbase_address: ");
1031 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
1032 fprintf (dump_file, "\n\toffset from base address: ");
1033 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
1034 fprintf (dump_file, "\n\tconstant offset from base address: ");
1035 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
1036 fprintf (dump_file, "\n\tstep: ");
1037 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
1038 fprintf (dump_file, "\n\taligned to: ");
1039 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
1040 fprintf (dump_file, "\n\tbase_object: ");
1041 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
1042 fprintf (dump_file, "\n");
1043 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
1045 fprintf (dump_file, "\tAccess function %d: ", i);
1046 print_generic_stmt (dump_file, DR_ACCESS_FN (dr, i), TDF_SLIM);
1053 /* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
1056 dr_equal_offsets_p1 (tree offset1, tree offset2)
1060 STRIP_NOPS (offset1);
1061 STRIP_NOPS (offset2);
1063 if (offset1 == offset2)
1066 if (TREE_CODE (offset1) != TREE_CODE (offset2)
1067 || (!BINARY_CLASS_P (offset1) && !UNARY_CLASS_P (offset1)))
1070 res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 0),
1071 TREE_OPERAND (offset2, 0));
1073 if (!res || !BINARY_CLASS_P (offset1))
1076 res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 1),
1077 TREE_OPERAND (offset2, 1));
1082 /* Check if DRA and DRB have equal offsets. */
1084 dr_equal_offsets_p (struct data_reference *dra,
1085 struct data_reference *drb)
1087 tree offset1, offset2;
1089 offset1 = DR_OFFSET (dra);
1090 offset2 = DR_OFFSET (drb);
1092 return dr_equal_offsets_p1 (offset1, offset2);
1095 /* Returns true if FNA == FNB. */
1098 affine_function_equal_p (affine_fn fna, affine_fn fnb)
1100 unsigned i, n = VEC_length (tree, fna);
1102 if (n != VEC_length (tree, fnb))
1105 for (i = 0; i < n; i++)
1106 if (!operand_equal_p (VEC_index (tree, fna, i),
1107 VEC_index (tree, fnb, i), 0))
1113 /* If all the functions in CF are the same, returns one of them,
1114 otherwise returns NULL. */
1117 common_affine_function (conflict_function *cf)
1122 if (!CF_NONTRIVIAL_P (cf))
1127 for (i = 1; i < cf->n; i++)
1128 if (!affine_function_equal_p (comm, cf->fns[i]))
1134 /* Returns the base of the affine function FN. */
1137 affine_function_base (affine_fn fn)
1139 return VEC_index (tree, fn, 0);
1142 /* Returns true if FN is a constant. */
1145 affine_function_constant_p (affine_fn fn)
1150 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
1151 if (!integer_zerop (coef))
1157 /* Returns true if FN is the zero constant function. */
1160 affine_function_zero_p (affine_fn fn)
1162 return (integer_zerop (affine_function_base (fn))
1163 && affine_function_constant_p (fn));
1166 /* Returns a signed integer type with the largest precision from TA
1170 signed_type_for_types (tree ta, tree tb)
1172 if (TYPE_PRECISION (ta) > TYPE_PRECISION (tb))
1173 return signed_type_for (ta);
1175 return signed_type_for (tb);
1178 /* Applies operation OP on affine functions FNA and FNB, and returns the
1182 affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
1188 if (VEC_length (tree, fnb) > VEC_length (tree, fna))
1190 n = VEC_length (tree, fna);
1191 m = VEC_length (tree, fnb);
1195 n = VEC_length (tree, fnb);
1196 m = VEC_length (tree, fna);
1199 ret = VEC_alloc (tree, heap, m);
1200 for (i = 0; i < n; i++)
1202 tree type = signed_type_for_types (TREE_TYPE (VEC_index (tree, fna, i)),
1203 TREE_TYPE (VEC_index (tree, fnb, i)));
1205 VEC_quick_push (tree, ret,
1206 fold_build2 (op, type,
1207 VEC_index (tree, fna, i),
1208 VEC_index (tree, fnb, i)));
1211 for (; VEC_iterate (tree, fna, i, coef); i++)
1212 VEC_quick_push (tree, ret,
1213 fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
1214 coef, integer_zero_node));
1215 for (; VEC_iterate (tree, fnb, i, coef); i++)
1216 VEC_quick_push (tree, ret,
1217 fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
1218 integer_zero_node, coef));
1223 /* Returns the sum of affine functions FNA and FNB. */
1226 affine_fn_plus (affine_fn fna, affine_fn fnb)
1228 return affine_fn_op (PLUS_EXPR, fna, fnb);
1231 /* Returns the difference of affine functions FNA and FNB. */
1234 affine_fn_minus (affine_fn fna, affine_fn fnb)
1236 return affine_fn_op (MINUS_EXPR, fna, fnb);
1239 /* Frees affine function FN. */
1242 affine_fn_free (affine_fn fn)
1244 VEC_free (tree, heap, fn);
1247 /* Determine for each subscript in the data dependence relation DDR
1251 compute_subscript_distance (struct data_dependence_relation *ddr)
1253 conflict_function *cf_a, *cf_b;
1254 affine_fn fn_a, fn_b, diff;
1256 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1260 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1262 struct subscript *subscript;
1264 subscript = DDR_SUBSCRIPT (ddr, i);
1265 cf_a = SUB_CONFLICTS_IN_A (subscript);
1266 cf_b = SUB_CONFLICTS_IN_B (subscript);
1268 fn_a = common_affine_function (cf_a);
1269 fn_b = common_affine_function (cf_b);
1272 SUB_DISTANCE (subscript) = chrec_dont_know;
1275 diff = affine_fn_minus (fn_a, fn_b);
1277 if (affine_function_constant_p (diff))
1278 SUB_DISTANCE (subscript) = affine_function_base (diff);
1280 SUB_DISTANCE (subscript) = chrec_dont_know;
1282 affine_fn_free (diff);
1287 /* Returns the conflict function for "unknown". */
1289 static conflict_function *
1290 conflict_fn_not_known (void)
1292 conflict_function *fn = XCNEW (conflict_function);
1298 /* Returns the conflict function for "independent". */
1300 static conflict_function *
1301 conflict_fn_no_dependence (void)
1303 conflict_function *fn = XCNEW (conflict_function);
1304 fn->n = NO_DEPENDENCE;
1309 /* Returns true if the address of OBJ is invariant in LOOP. */
1312 object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj)
1314 while (handled_component_p (obj))
1316 if (TREE_CODE (obj) == ARRAY_REF)
1318 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1319 need to check the stride and the lower bound of the reference. */
1320 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1322 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 3),
1326 else if (TREE_CODE (obj) == COMPONENT_REF)
1328 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1332 obj = TREE_OPERAND (obj, 0);
1335 if (!INDIRECT_REF_P (obj)
1336 && TREE_CODE (obj) != MEM_REF)
1339 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0),
1343 /* Returns false if we can prove that data references A and B do not alias,
1344 true otherwise. If LOOP_NEST is false no cross-iteration aliases are
1348 dr_may_alias_p (const struct data_reference *a, const struct data_reference *b,
1351 tree addr_a = DR_BASE_OBJECT (a);
1352 tree addr_b = DR_BASE_OBJECT (b);
1354 /* If we are not processing a loop nest but scalar code we
1355 do not need to care about possible cross-iteration dependences
1356 and thus can process the full original reference. Do so,
1357 similar to how loop invariant motion applies extra offset-based
1361 aff_tree off1, off2;
1362 double_int size1, size2;
1363 get_inner_reference_aff (DR_REF (a), &off1, &size1);
1364 get_inner_reference_aff (DR_REF (b), &off2, &size2);
1365 aff_combination_scale (&off1, double_int_minus_one);
1366 aff_combination_add (&off2, &off1);
1367 if (aff_comb_cannot_overlap_p (&off2, size1, size2))
1371 /* If we had an evolution in a MEM_REF BASE_OBJECT we do not know
1372 the size of the base-object. So we cannot do any offset/overlap
1373 based analysis but have to rely on points-to information only. */
1374 if (TREE_CODE (addr_a) == MEM_REF
1375 && DR_UNCONSTRAINED_BASE (a))
1377 if (TREE_CODE (addr_b) == MEM_REF
1378 && DR_UNCONSTRAINED_BASE (b))
1379 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a, 0),
1380 TREE_OPERAND (addr_b, 0));
1382 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a, 0),
1383 build_fold_addr_expr (addr_b));
1385 else if (TREE_CODE (addr_b) == MEM_REF
1386 && DR_UNCONSTRAINED_BASE (b))
1387 return ptr_derefs_may_alias_p (build_fold_addr_expr (addr_a),
1388 TREE_OPERAND (addr_b, 0));
1390 /* Otherwise DR_BASE_OBJECT is an access that covers the whole object
1391 that is being subsetted in the loop nest. */
1392 if (DR_IS_WRITE (a) && DR_IS_WRITE (b))
1393 return refs_output_dependent_p (addr_a, addr_b);
1394 else if (DR_IS_READ (a) && DR_IS_WRITE (b))
1395 return refs_anti_dependent_p (addr_a, addr_b);
1396 return refs_may_alias_p (addr_a, addr_b);
1399 /* Initialize a data dependence relation between data accesses A and
1400 B. NB_LOOPS is the number of loops surrounding the references: the
1401 size of the classic distance/direction vectors. */
1403 struct data_dependence_relation *
1404 initialize_data_dependence_relation (struct data_reference *a,
1405 struct data_reference *b,
1406 VEC (loop_p, heap) *loop_nest)
1408 struct data_dependence_relation *res;
1411 res = XNEW (struct data_dependence_relation);
1414 DDR_LOOP_NEST (res) = NULL;
1415 DDR_REVERSED_P (res) = false;
1416 DDR_SUBSCRIPTS (res) = NULL;
1417 DDR_DIR_VECTS (res) = NULL;
1418 DDR_DIST_VECTS (res) = NULL;
1420 if (a == NULL || b == NULL)
1422 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1426 /* If the data references do not alias, then they are independent. */
1427 if (!dr_may_alias_p (a, b, loop_nest != NULL))
1429 DDR_ARE_DEPENDENT (res) = chrec_known;
1433 /* The case where the references are exactly the same. */
1434 if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
1437 && !object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
1438 DR_BASE_OBJECT (a)))
1440 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1443 DDR_AFFINE_P (res) = true;
1444 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1445 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
1446 DDR_LOOP_NEST (res) = loop_nest;
1447 DDR_INNER_LOOP (res) = 0;
1448 DDR_SELF_REFERENCE (res) = true;
1449 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1451 struct subscript *subscript;
1453 subscript = XNEW (struct subscript);
1454 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
1455 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
1456 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1457 SUB_DISTANCE (subscript) = chrec_dont_know;
1458 VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
1463 /* If the references do not access the same object, we do not know
1464 whether they alias or not. */
1465 if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0))
1467 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1471 /* If the base of the object is not invariant in the loop nest, we cannot
1472 analyze it. TODO -- in fact, it would suffice to record that there may
1473 be arbitrary dependences in the loops where the base object varies. */
1475 && !object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
1476 DR_BASE_OBJECT (a)))
1478 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1482 /* If the number of dimensions of the access to not agree we can have
1483 a pointer access to a component of the array element type and an
1484 array access while the base-objects are still the same. Punt. */
1485 if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
1487 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1491 DDR_AFFINE_P (res) = true;
1492 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1493 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
1494 DDR_LOOP_NEST (res) = loop_nest;
1495 DDR_INNER_LOOP (res) = 0;
1496 DDR_SELF_REFERENCE (res) = false;
1498 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1500 struct subscript *subscript;
1502 subscript = XNEW (struct subscript);
1503 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
1504 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
1505 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1506 SUB_DISTANCE (subscript) = chrec_dont_know;
1507 VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
1513 /* Frees memory used by the conflict function F. */
1516 free_conflict_function (conflict_function *f)
1520 if (CF_NONTRIVIAL_P (f))
1522 for (i = 0; i < f->n; i++)
1523 affine_fn_free (f->fns[i]);
1528 /* Frees memory used by SUBSCRIPTS. */
1531 free_subscripts (VEC (subscript_p, heap) *subscripts)
1536 FOR_EACH_VEC_ELT (subscript_p, subscripts, i, s)
1538 free_conflict_function (s->conflicting_iterations_in_a);
1539 free_conflict_function (s->conflicting_iterations_in_b);
1542 VEC_free (subscript_p, heap, subscripts);
1545 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1549 finalize_ddr_dependent (struct data_dependence_relation *ddr,
1552 if (dump_file && (dump_flags & TDF_DETAILS))
1554 fprintf (dump_file, "(dependence classified: ");
1555 print_generic_expr (dump_file, chrec, 0);
1556 fprintf (dump_file, ")\n");
1559 DDR_ARE_DEPENDENT (ddr) = chrec;
1560 free_subscripts (DDR_SUBSCRIPTS (ddr));
1561 DDR_SUBSCRIPTS (ddr) = NULL;
1564 /* The dependence relation DDR cannot be represented by a distance
1568 non_affine_dependence_relation (struct data_dependence_relation *ddr)
1570 if (dump_file && (dump_flags & TDF_DETAILS))
1571 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
1573 DDR_AFFINE_P (ddr) = false;
1578 /* This section contains the classic Banerjee tests. */
1580 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1581 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1584 ziv_subscript_p (const_tree chrec_a, const_tree chrec_b)
1586 return (evolution_function_is_constant_p (chrec_a)
1587 && evolution_function_is_constant_p (chrec_b));
1590 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1591 variable, i.e., if the SIV (Single Index Variable) test is true. */
1594 siv_subscript_p (const_tree chrec_a, const_tree chrec_b)
1596 if ((evolution_function_is_constant_p (chrec_a)
1597 && evolution_function_is_univariate_p (chrec_b))
1598 || (evolution_function_is_constant_p (chrec_b)
1599 && evolution_function_is_univariate_p (chrec_a)))
1602 if (evolution_function_is_univariate_p (chrec_a)
1603 && evolution_function_is_univariate_p (chrec_b))
1605 switch (TREE_CODE (chrec_a))
1607 case POLYNOMIAL_CHREC:
1608 switch (TREE_CODE (chrec_b))
1610 case POLYNOMIAL_CHREC:
1611 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
1626 /* Creates a conflict function with N dimensions. The affine functions
1627 in each dimension follow. */
1629 static conflict_function *
1630 conflict_fn (unsigned n, ...)
1633 conflict_function *ret = XCNEW (conflict_function);
1636 gcc_assert (0 < n && n <= MAX_DIM);
1640 for (i = 0; i < n; i++)
1641 ret->fns[i] = va_arg (ap, affine_fn);
1647 /* Returns constant affine function with value CST. */
1650 affine_fn_cst (tree cst)
1652 affine_fn fn = VEC_alloc (tree, heap, 1);
1653 VEC_quick_push (tree, fn, cst);
1657 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1660 affine_fn_univar (tree cst, unsigned dim, tree coef)
1662 affine_fn fn = VEC_alloc (tree, heap, dim + 1);
1665 gcc_assert (dim > 0);
1666 VEC_quick_push (tree, fn, cst);
1667 for (i = 1; i < dim; i++)
1668 VEC_quick_push (tree, fn, integer_zero_node);
1669 VEC_quick_push (tree, fn, coef);
1673 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1674 *OVERLAPS_B are initialized to the functions that describe the
1675 relation between the elements accessed twice by CHREC_A and
1676 CHREC_B. For k >= 0, the following property is verified:
1678 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1681 analyze_ziv_subscript (tree chrec_a,
1683 conflict_function **overlaps_a,
1684 conflict_function **overlaps_b,
1685 tree *last_conflicts)
1687 tree type, difference;
1688 dependence_stats.num_ziv++;
1690 if (dump_file && (dump_flags & TDF_DETAILS))
1691 fprintf (dump_file, "(analyze_ziv_subscript \n");
1693 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
1694 chrec_a = chrec_convert (type, chrec_a, NULL);
1695 chrec_b = chrec_convert (type, chrec_b, NULL);
1696 difference = chrec_fold_minus (type, chrec_a, chrec_b);
1698 switch (TREE_CODE (difference))
1701 if (integer_zerop (difference))
1703 /* The difference is equal to zero: the accessed index
1704 overlaps for each iteration in the loop. */
1705 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1706 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1707 *last_conflicts = chrec_dont_know;
1708 dependence_stats.num_ziv_dependent++;
1712 /* The accesses do not overlap. */
1713 *overlaps_a = conflict_fn_no_dependence ();
1714 *overlaps_b = conflict_fn_no_dependence ();
1715 *last_conflicts = integer_zero_node;
1716 dependence_stats.num_ziv_independent++;
1721 /* We're not sure whether the indexes overlap. For the moment,
1722 conservatively answer "don't know". */
1723 if (dump_file && (dump_flags & TDF_DETAILS))
1724 fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
1726 *overlaps_a = conflict_fn_not_known ();
1727 *overlaps_b = conflict_fn_not_known ();
1728 *last_conflicts = chrec_dont_know;
1729 dependence_stats.num_ziv_unimplemented++;
1733 if (dump_file && (dump_flags & TDF_DETAILS))
1734 fprintf (dump_file, ")\n");
1737 /* Similar to max_stmt_executions_int, but returns the bound as a tree,
1738 and only if it fits to the int type. If this is not the case, or the
1739 bound on the number of iterations of LOOP could not be derived, returns
1743 max_stmt_executions_tree (struct loop *loop)
1747 if (!max_stmt_executions (loop, true, &nit))
1748 return chrec_dont_know;
1750 if (!double_int_fits_to_tree_p (unsigned_type_node, nit))
1751 return chrec_dont_know;
1753 return double_int_to_tree (unsigned_type_node, nit);
1756 /* Determine whether the CHREC is always positive/negative. If the expression
1757 cannot be statically analyzed, return false, otherwise set the answer into
1761 chrec_is_positive (tree chrec, bool *value)
1763 bool value0, value1, value2;
1764 tree end_value, nb_iter;
1766 switch (TREE_CODE (chrec))
1768 case POLYNOMIAL_CHREC:
1769 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
1770 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
1773 /* FIXME -- overflows. */
1774 if (value0 == value1)
1780 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
1781 and the proof consists in showing that the sign never
1782 changes during the execution of the loop, from 0 to
1783 loop->nb_iterations. */
1784 if (!evolution_function_is_affine_p (chrec))
1787 nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
1788 if (chrec_contains_undetermined (nb_iter))
1792 /* TODO -- If the test is after the exit, we may decrease the number of
1793 iterations by one. */
1795 nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
1798 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
1800 if (!chrec_is_positive (end_value, &value2))
1804 return value0 == value1;
1807 switch (tree_int_cst_sgn (chrec))
1826 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1827 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1828 *OVERLAPS_B are initialized to the functions that describe the
1829 relation between the elements accessed twice by CHREC_A and
1830 CHREC_B. For k >= 0, the following property is verified:
1832 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1835 analyze_siv_subscript_cst_affine (tree chrec_a,
1837 conflict_function **overlaps_a,
1838 conflict_function **overlaps_b,
1839 tree *last_conflicts)
1841 bool value0, value1, value2;
1842 tree type, difference, tmp;
1844 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
1845 chrec_a = chrec_convert (type, chrec_a, NULL);
1846 chrec_b = chrec_convert (type, chrec_b, NULL);
1847 difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a);
1849 /* Special case overlap in the first iteration. */
1850 if (integer_zerop (difference))
1852 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1853 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1854 *last_conflicts = integer_one_node;
1858 if (!chrec_is_positive (initial_condition (difference), &value0))
1860 if (dump_file && (dump_flags & TDF_DETAILS))
1861 fprintf (dump_file, "siv test failed: chrec is not positive.\n");
1863 dependence_stats.num_siv_unimplemented++;
1864 *overlaps_a = conflict_fn_not_known ();
1865 *overlaps_b = conflict_fn_not_known ();
1866 *last_conflicts = chrec_dont_know;
1871 if (value0 == false)
1873 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
1875 if (dump_file && (dump_flags & TDF_DETAILS))
1876 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1878 *overlaps_a = conflict_fn_not_known ();
1879 *overlaps_b = conflict_fn_not_known ();
1880 *last_conflicts = chrec_dont_know;
1881 dependence_stats.num_siv_unimplemented++;
1890 chrec_b = {10, +, 1}
1893 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1895 HOST_WIDE_INT numiter;
1896 struct loop *loop = get_chrec_loop (chrec_b);
1898 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1899 tmp = fold_build2 (EXACT_DIV_EXPR, type,
1900 fold_build1 (ABS_EXPR, type, difference),
1901 CHREC_RIGHT (chrec_b));
1902 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1903 *last_conflicts = integer_one_node;
1906 /* Perform weak-zero siv test to see if overlap is
1907 outside the loop bounds. */
1908 numiter = max_stmt_executions_int (loop, true);
1911 && compare_tree_int (tmp, numiter) > 0)
1913 free_conflict_function (*overlaps_a);
1914 free_conflict_function (*overlaps_b);
1915 *overlaps_a = conflict_fn_no_dependence ();
1916 *overlaps_b = conflict_fn_no_dependence ();
1917 *last_conflicts = integer_zero_node;
1918 dependence_stats.num_siv_independent++;
1921 dependence_stats.num_siv_dependent++;
1925 /* When the step does not divide the difference, there are
1929 *overlaps_a = conflict_fn_no_dependence ();
1930 *overlaps_b = conflict_fn_no_dependence ();
1931 *last_conflicts = integer_zero_node;
1932 dependence_stats.num_siv_independent++;
1941 chrec_b = {10, +, -1}
1943 In this case, chrec_a will not overlap with chrec_b. */
1944 *overlaps_a = conflict_fn_no_dependence ();
1945 *overlaps_b = conflict_fn_no_dependence ();
1946 *last_conflicts = integer_zero_node;
1947 dependence_stats.num_siv_independent++;
1954 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
1956 if (dump_file && (dump_flags & TDF_DETAILS))
1957 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1959 *overlaps_a = conflict_fn_not_known ();
1960 *overlaps_b = conflict_fn_not_known ();
1961 *last_conflicts = chrec_dont_know;
1962 dependence_stats.num_siv_unimplemented++;
1967 if (value2 == false)
1971 chrec_b = {10, +, -1}
1973 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1975 HOST_WIDE_INT numiter;
1976 struct loop *loop = get_chrec_loop (chrec_b);
1978 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1979 tmp = fold_build2 (EXACT_DIV_EXPR, type, difference,
1980 CHREC_RIGHT (chrec_b));
1981 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1982 *last_conflicts = integer_one_node;
1984 /* Perform weak-zero siv test to see if overlap is
1985 outside the loop bounds. */
1986 numiter = max_stmt_executions_int (loop, true);
1989 && compare_tree_int (tmp, numiter) > 0)
1991 free_conflict_function (*overlaps_a);
1992 free_conflict_function (*overlaps_b);
1993 *overlaps_a = conflict_fn_no_dependence ();
1994 *overlaps_b = conflict_fn_no_dependence ();
1995 *last_conflicts = integer_zero_node;
1996 dependence_stats.num_siv_independent++;
1999 dependence_stats.num_siv_dependent++;
2003 /* When the step does not divide the difference, there
2007 *overlaps_a = conflict_fn_no_dependence ();
2008 *overlaps_b = conflict_fn_no_dependence ();
2009 *last_conflicts = integer_zero_node;
2010 dependence_stats.num_siv_independent++;
2020 In this case, chrec_a will not overlap with chrec_b. */
2021 *overlaps_a = conflict_fn_no_dependence ();
2022 *overlaps_b = conflict_fn_no_dependence ();
2023 *last_conflicts = integer_zero_node;
2024 dependence_stats.num_siv_independent++;
2032 /* Helper recursive function for initializing the matrix A. Returns
2033 the initial value of CHREC. */
2036 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2040 switch (TREE_CODE (chrec))
2042 case POLYNOMIAL_CHREC:
2043 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST);
2045 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2046 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2052 tree op0 = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
2053 tree op1 = initialize_matrix_A (A, TREE_OPERAND (chrec, 1), index, mult);
2055 return chrec_fold_op (TREE_CODE (chrec), chrec_type (chrec), op0, op1);
2060 tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
2061 return chrec_convert (chrec_type (chrec), op, NULL);
2066 /* Handle ~X as -1 - X. */
2067 tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
2068 return chrec_fold_op (MINUS_EXPR, chrec_type (chrec),
2069 build_int_cst (TREE_TYPE (chrec), -1), op);
2081 #define FLOOR_DIV(x,y) ((x) / (y))
2083 /* Solves the special case of the Diophantine equation:
2084 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2086 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2087 number of iterations that loops X and Y run. The overlaps will be
2088 constructed as evolutions in dimension DIM. */
2091 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
2092 affine_fn *overlaps_a,
2093 affine_fn *overlaps_b,
2094 tree *last_conflicts, int dim)
2096 if (((step_a > 0 && step_b > 0)
2097 || (step_a < 0 && step_b < 0)))
2099 int step_overlaps_a, step_overlaps_b;
2100 int gcd_steps_a_b, last_conflict, tau2;
2102 gcd_steps_a_b = gcd (step_a, step_b);
2103 step_overlaps_a = step_b / gcd_steps_a_b;
2104 step_overlaps_b = step_a / gcd_steps_a_b;
2108 tau2 = FLOOR_DIV (niter, step_overlaps_a);
2109 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2110 last_conflict = tau2;
2111 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2114 *last_conflicts = chrec_dont_know;
2116 *overlaps_a = affine_fn_univar (integer_zero_node, dim,
2117 build_int_cst (NULL_TREE,
2119 *overlaps_b = affine_fn_univar (integer_zero_node, dim,
2120 build_int_cst (NULL_TREE,
2126 *overlaps_a = affine_fn_cst (integer_zero_node);
2127 *overlaps_b = affine_fn_cst (integer_zero_node);
2128 *last_conflicts = integer_zero_node;
2132 /* Solves the special case of a Diophantine equation where CHREC_A is
2133 an affine bivariate function, and CHREC_B is an affine univariate
2134 function. For example,
2136 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2138 has the following overlapping functions:
2140 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2141 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2142 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2144 FORNOW: This is a specialized implementation for a case occurring in
2145 a common benchmark. Implement the general algorithm. */
2148 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2149 conflict_function **overlaps_a,
2150 conflict_function **overlaps_b,
2151 tree *last_conflicts)
2153 bool xz_p, yz_p, xyz_p;
2154 int step_x, step_y, step_z;
2155 HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
2156 affine_fn overlaps_a_xz, overlaps_b_xz;
2157 affine_fn overlaps_a_yz, overlaps_b_yz;
2158 affine_fn overlaps_a_xyz, overlaps_b_xyz;
2159 affine_fn ova1, ova2, ovb;
2160 tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
2162 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2163 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2164 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2167 max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a)), true);
2168 niter_y = max_stmt_executions_int (get_chrec_loop (chrec_a), true);
2169 niter_z = max_stmt_executions_int (get_chrec_loop (chrec_b), true);
2171 if (niter_x < 0 || niter_y < 0 || niter_z < 0)
2173 if (dump_file && (dump_flags & TDF_DETAILS))
2174 fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
2176 *overlaps_a = conflict_fn_not_known ();
2177 *overlaps_b = conflict_fn_not_known ();
2178 *last_conflicts = chrec_dont_know;
2182 niter = MIN (niter_x, niter_z);
2183 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2186 &last_conflicts_xz, 1);
2187 niter = MIN (niter_y, niter_z);
2188 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2191 &last_conflicts_yz, 2);
2192 niter = MIN (niter_x, niter_z);
2193 niter = MIN (niter_y, niter);
2194 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2197 &last_conflicts_xyz, 3);
2199 xz_p = !integer_zerop (last_conflicts_xz);
2200 yz_p = !integer_zerop (last_conflicts_yz);
2201 xyz_p = !integer_zerop (last_conflicts_xyz);
2203 if (xz_p || yz_p || xyz_p)
2205 ova1 = affine_fn_cst (integer_zero_node);
2206 ova2 = affine_fn_cst (integer_zero_node);
2207 ovb = affine_fn_cst (integer_zero_node);
2210 affine_fn t0 = ova1;
2213 ova1 = affine_fn_plus (ova1, overlaps_a_xz);
2214 ovb = affine_fn_plus (ovb, overlaps_b_xz);
2215 affine_fn_free (t0);
2216 affine_fn_free (t2);
2217 *last_conflicts = last_conflicts_xz;
2221 affine_fn t0 = ova2;
2224 ova2 = affine_fn_plus (ova2, overlaps_a_yz);
2225 ovb = affine_fn_plus (ovb, overlaps_b_yz);
2226 affine_fn_free (t0);
2227 affine_fn_free (t2);
2228 *last_conflicts = last_conflicts_yz;
2232 affine_fn t0 = ova1;
2233 affine_fn t2 = ova2;
2236 ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
2237 ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
2238 ovb = affine_fn_plus (ovb, overlaps_b_xyz);
2239 affine_fn_free (t0);
2240 affine_fn_free (t2);
2241 affine_fn_free (t4);
2242 *last_conflicts = last_conflicts_xyz;
2244 *overlaps_a = conflict_fn (2, ova1, ova2);
2245 *overlaps_b = conflict_fn (1, ovb);
2249 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2250 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2251 *last_conflicts = integer_zero_node;
2254 affine_fn_free (overlaps_a_xz);
2255 affine_fn_free (overlaps_b_xz);
2256 affine_fn_free (overlaps_a_yz);
2257 affine_fn_free (overlaps_b_yz);
2258 affine_fn_free (overlaps_a_xyz);
2259 affine_fn_free (overlaps_b_xyz);
2262 /* Copy the elements of vector VEC1 with length SIZE to VEC2. */
2265 lambda_vector_copy (lambda_vector vec1, lambda_vector vec2,
2268 memcpy (vec2, vec1, size * sizeof (*vec1));
2271 /* Copy the elements of M x N matrix MAT1 to MAT2. */
2274 lambda_matrix_copy (lambda_matrix mat1, lambda_matrix mat2,
2279 for (i = 0; i < m; i++)
2280 lambda_vector_copy (mat1[i], mat2[i], n);
2283 /* Store the N x N identity matrix in MAT. */
2286 lambda_matrix_id (lambda_matrix mat, int size)
2290 for (i = 0; i < size; i++)
2291 for (j = 0; j < size; j++)
2292 mat[i][j] = (i == j) ? 1 : 0;
2295 /* Return the first nonzero element of vector VEC1 between START and N.
2296 We must have START <= N. Returns N if VEC1 is the zero vector. */
2299 lambda_vector_first_nz (lambda_vector vec1, int n, int start)
2302 while (j < n && vec1[j] == 0)
2307 /* Add a multiple of row R1 of matrix MAT with N columns to row R2:
2308 R2 = R2 + CONST1 * R1. */
2311 lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2, int const1)
2318 for (i = 0; i < n; i++)
2319 mat[r2][i] += const1 * mat[r1][i];
2322 /* Swap rows R1 and R2 in matrix MAT. */
2325 lambda_matrix_row_exchange (lambda_matrix mat, int r1, int r2)
2334 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
2335 and store the result in VEC2. */
2338 lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2,
2339 int size, int const1)
2344 lambda_vector_clear (vec2, size);
2346 for (i = 0; i < size; i++)
2347 vec2[i] = const1 * vec1[i];
2350 /* Negate vector VEC1 with length SIZE and store it in VEC2. */
2353 lambda_vector_negate (lambda_vector vec1, lambda_vector vec2,
2356 lambda_vector_mult_const (vec1, vec2, size, -1);
2359 /* Negate row R1 of matrix MAT which has N columns. */
2362 lambda_matrix_row_negate (lambda_matrix mat, int n, int r1)
2364 lambda_vector_negate (mat[r1], mat[r1], n);
2367 /* Return true if two vectors are equal. */
2370 lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
2373 for (i = 0; i < size; i++)
2374 if (vec1[i] != vec2[i])
2379 /* Given an M x N integer matrix A, this function determines an M x
2380 M unimodular matrix U, and an M x N echelon matrix S such that
2381 "U.A = S". This decomposition is also known as "right Hermite".
2383 Ref: Algorithm 2.1 page 33 in "Loop Transformations for
2384 Restructuring Compilers" Utpal Banerjee. */
2387 lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
2388 lambda_matrix S, lambda_matrix U)
2392 lambda_matrix_copy (A, S, m, n);
2393 lambda_matrix_id (U, m);
2395 for (j = 0; j < n; j++)
2397 if (lambda_vector_first_nz (S[j], m, i0) < m)
2400 for (i = m - 1; i >= i0; i--)
2402 while (S[i][j] != 0)
2404 int sigma, factor, a, b;
2408 sigma = (a * b < 0) ? -1: 1;
2411 factor = sigma * (a / b);
2413 lambda_matrix_row_add (S, n, i, i-1, -factor);
2414 lambda_matrix_row_exchange (S, i, i-1);
2416 lambda_matrix_row_add (U, m, i, i-1, -factor);
2417 lambda_matrix_row_exchange (U, i, i-1);
2424 /* Determines the overlapping elements due to accesses CHREC_A and
2425 CHREC_B, that are affine functions. This function cannot handle
2426 symbolic evolution functions, ie. when initial conditions are
2427 parameters, because it uses lambda matrices of integers. */
2430 analyze_subscript_affine_affine (tree chrec_a,
2432 conflict_function **overlaps_a,
2433 conflict_function **overlaps_b,
2434 tree *last_conflicts)
2436 unsigned nb_vars_a, nb_vars_b, dim;
2437 HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta;
2438 lambda_matrix A, U, S;
2439 struct obstack scratch_obstack;
2441 if (eq_evolutions_p (chrec_a, chrec_b))
2443 /* The accessed index overlaps for each iteration in the
2445 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2446 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2447 *last_conflicts = chrec_dont_know;
2450 if (dump_file && (dump_flags & TDF_DETAILS))
2451 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2453 /* For determining the initial intersection, we have to solve a
2454 Diophantine equation. This is the most time consuming part.
2456 For answering to the question: "Is there a dependence?" we have
2457 to prove that there exists a solution to the Diophantine
2458 equation, and that the solution is in the iteration domain,
2459 i.e. the solution is positive or zero, and that the solution
2460 happens before the upper bound loop.nb_iterations. Otherwise
2461 there is no dependence. This function outputs a description of
2462 the iterations that hold the intersections. */
2464 nb_vars_a = nb_vars_in_chrec (chrec_a);
2465 nb_vars_b = nb_vars_in_chrec (chrec_b);
2467 gcc_obstack_init (&scratch_obstack);
2469 dim = nb_vars_a + nb_vars_b;
2470 U = lambda_matrix_new (dim, dim, &scratch_obstack);
2471 A = lambda_matrix_new (dim, 1, &scratch_obstack);
2472 S = lambda_matrix_new (dim, 1, &scratch_obstack);
2474 init_a = int_cst_value (initialize_matrix_A (A, chrec_a, 0, 1));
2475 init_b = int_cst_value (initialize_matrix_A (A, chrec_b, nb_vars_a, -1));
2476 gamma = init_b - init_a;
2478 /* Don't do all the hard work of solving the Diophantine equation
2479 when we already know the solution: for example,
2482 | gamma = 3 - 3 = 0.
2483 Then the first overlap occurs during the first iterations:
2484 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2488 if (nb_vars_a == 1 && nb_vars_b == 1)
2490 HOST_WIDE_INT step_a, step_b;
2491 HOST_WIDE_INT niter, niter_a, niter_b;
2494 niter_a = max_stmt_executions_int (get_chrec_loop (chrec_a), true);
2495 niter_b = max_stmt_executions_int (get_chrec_loop (chrec_b), true);
2496 niter = MIN (niter_a, niter_b);
2497 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2498 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2500 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2503 *overlaps_a = conflict_fn (1, ova);
2504 *overlaps_b = conflict_fn (1, ovb);
2507 else if (nb_vars_a == 2 && nb_vars_b == 1)
2508 compute_overlap_steps_for_affine_1_2
2509 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2511 else if (nb_vars_a == 1 && nb_vars_b == 2)
2512 compute_overlap_steps_for_affine_1_2
2513 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2517 if (dump_file && (dump_flags & TDF_DETAILS))
2518 fprintf (dump_file, "affine-affine test failed: too many variables.\n");
2519 *overlaps_a = conflict_fn_not_known ();
2520 *overlaps_b = conflict_fn_not_known ();
2521 *last_conflicts = chrec_dont_know;
2523 goto end_analyze_subs_aa;
2527 lambda_matrix_right_hermite (A, dim, 1, S, U);
2532 lambda_matrix_row_negate (U, dim, 0);
2534 gcd_alpha_beta = S[0][0];
2536 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2537 but that is a quite strange case. Instead of ICEing, answer
2539 if (gcd_alpha_beta == 0)
2541 *overlaps_a = conflict_fn_not_known ();
2542 *overlaps_b = conflict_fn_not_known ();
2543 *last_conflicts = chrec_dont_know;
2544 goto end_analyze_subs_aa;
2547 /* The classic "gcd-test". */
2548 if (!int_divides_p (gcd_alpha_beta, gamma))
2550 /* The "gcd-test" has determined that there is no integer
2551 solution, i.e. there is no dependence. */
2552 *overlaps_a = conflict_fn_no_dependence ();
2553 *overlaps_b = conflict_fn_no_dependence ();
2554 *last_conflicts = integer_zero_node;
2557 /* Both access functions are univariate. This includes SIV and MIV cases. */
2558 else if (nb_vars_a == 1 && nb_vars_b == 1)
2560 /* Both functions should have the same evolution sign. */
2561 if (((A[0][0] > 0 && -A[1][0] > 0)
2562 || (A[0][0] < 0 && -A[1][0] < 0)))
2564 /* The solutions are given by:
2566 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2569 For a given integer t. Using the following variables,
2571 | i0 = u11 * gamma / gcd_alpha_beta
2572 | j0 = u12 * gamma / gcd_alpha_beta
2579 | y0 = j0 + j1 * t. */
2580 HOST_WIDE_INT i0, j0, i1, j1;
2582 i0 = U[0][0] * gamma / gcd_alpha_beta;
2583 j0 = U[0][1] * gamma / gcd_alpha_beta;
2587 if ((i1 == 0 && i0 < 0)
2588 || (j1 == 0 && j0 < 0))
2590 /* There is no solution.
2591 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2592 falls in here, but for the moment we don't look at the
2593 upper bound of the iteration domain. */
2594 *overlaps_a = conflict_fn_no_dependence ();
2595 *overlaps_b = conflict_fn_no_dependence ();
2596 *last_conflicts = integer_zero_node;
2597 goto end_analyze_subs_aa;
2600 if (i1 > 0 && j1 > 0)
2602 HOST_WIDE_INT niter_a = max_stmt_executions_int
2603 (get_chrec_loop (chrec_a), true);
2604 HOST_WIDE_INT niter_b = max_stmt_executions_int
2605 (get_chrec_loop (chrec_b), true);
2606 HOST_WIDE_INT niter = MIN (niter_a, niter_b);
2608 /* (X0, Y0) is a solution of the Diophantine equation:
2609 "chrec_a (X0) = chrec_b (Y0)". */
2610 HOST_WIDE_INT tau1 = MAX (CEIL (-i0, i1),
2612 HOST_WIDE_INT x0 = i1 * tau1 + i0;
2613 HOST_WIDE_INT y0 = j1 * tau1 + j0;
2615 /* (X1, Y1) is the smallest positive solution of the eq
2616 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2617 first conflict occurs. */
2618 HOST_WIDE_INT min_multiple = MIN (x0 / i1, y0 / j1);
2619 HOST_WIDE_INT x1 = x0 - i1 * min_multiple;
2620 HOST_WIDE_INT y1 = y0 - j1 * min_multiple;
2624 HOST_WIDE_INT tau2 = MIN (FLOOR_DIV (niter - i0, i1),
2625 FLOOR_DIV (niter - j0, j1));
2626 HOST_WIDE_INT last_conflict = tau2 - (x1 - i0)/i1;
2628 /* If the overlap occurs outside of the bounds of the
2629 loop, there is no dependence. */
2630 if (x1 >= niter || y1 >= niter)
2632 *overlaps_a = conflict_fn_no_dependence ();
2633 *overlaps_b = conflict_fn_no_dependence ();
2634 *last_conflicts = integer_zero_node;
2635 goto end_analyze_subs_aa;
2638 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2641 *last_conflicts = chrec_dont_know;
2645 affine_fn_univar (build_int_cst (NULL_TREE, x1),
2647 build_int_cst (NULL_TREE, i1)));
2650 affine_fn_univar (build_int_cst (NULL_TREE, y1),
2652 build_int_cst (NULL_TREE, j1)));
2656 /* FIXME: For the moment, the upper bound of the
2657 iteration domain for i and j is not checked. */
2658 if (dump_file && (dump_flags & TDF_DETAILS))
2659 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2660 *overlaps_a = conflict_fn_not_known ();
2661 *overlaps_b = conflict_fn_not_known ();
2662 *last_conflicts = chrec_dont_know;
2667 if (dump_file && (dump_flags & TDF_DETAILS))
2668 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2669 *overlaps_a = conflict_fn_not_known ();
2670 *overlaps_b = conflict_fn_not_known ();
2671 *last_conflicts = chrec_dont_know;
2676 if (dump_file && (dump_flags & TDF_DETAILS))
2677 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2678 *overlaps_a = conflict_fn_not_known ();
2679 *overlaps_b = conflict_fn_not_known ();
2680 *last_conflicts = chrec_dont_know;
2683 end_analyze_subs_aa:
2684 obstack_free (&scratch_obstack, NULL);
2685 if (dump_file && (dump_flags & TDF_DETAILS))
2687 fprintf (dump_file, " (overlaps_a = ");
2688 dump_conflict_function (dump_file, *overlaps_a);
2689 fprintf (dump_file, ")\n (overlaps_b = ");
2690 dump_conflict_function (dump_file, *overlaps_b);
2691 fprintf (dump_file, ")\n");
2692 fprintf (dump_file, ")\n");
2696 /* Returns true when analyze_subscript_affine_affine can be used for
2697 determining the dependence relation between chrec_a and chrec_b,
2698 that contain symbols. This function modifies chrec_a and chrec_b
2699 such that the analysis result is the same, and such that they don't
2700 contain symbols, and then can safely be passed to the analyzer.
2702 Example: The analysis of the following tuples of evolutions produce
2703 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2706 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2707 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2711 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
2713 tree diff, type, left_a, left_b, right_b;
2715 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
2716 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
2717 /* FIXME: For the moment not handled. Might be refined later. */
2720 type = chrec_type (*chrec_a);
2721 left_a = CHREC_LEFT (*chrec_a);
2722 left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL);
2723 diff = chrec_fold_minus (type, left_a, left_b);
2725 if (!evolution_function_is_constant_p (diff))
2728 if (dump_file && (dump_flags & TDF_DETAILS))
2729 fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
2731 *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
2732 diff, CHREC_RIGHT (*chrec_a));
2733 right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL);
2734 *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
2735 build_int_cst (type, 0),
2740 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2741 *OVERLAPS_B are initialized to the functions that describe the
2742 relation between the elements accessed twice by CHREC_A and
2743 CHREC_B. For k >= 0, the following property is verified:
2745 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2748 analyze_siv_subscript (tree chrec_a,
2750 conflict_function **overlaps_a,
2751 conflict_function **overlaps_b,
2752 tree *last_conflicts,
2755 dependence_stats.num_siv++;
2757 if (dump_file && (dump_flags & TDF_DETAILS))
2758 fprintf (dump_file, "(analyze_siv_subscript \n");
2760 if (evolution_function_is_constant_p (chrec_a)
2761 && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
2762 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
2763 overlaps_a, overlaps_b, last_conflicts);
2765 else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
2766 && evolution_function_is_constant_p (chrec_b))
2767 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2768 overlaps_b, overlaps_a, last_conflicts);
2770 else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
2771 && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
2773 if (!chrec_contains_symbols (chrec_a)
2774 && !chrec_contains_symbols (chrec_b))
2776 analyze_subscript_affine_affine (chrec_a, chrec_b,
2777 overlaps_a, overlaps_b,
2780 if (CF_NOT_KNOWN_P (*overlaps_a)
2781 || CF_NOT_KNOWN_P (*overlaps_b))
2782 dependence_stats.num_siv_unimplemented++;
2783 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2784 || CF_NO_DEPENDENCE_P (*overlaps_b))
2785 dependence_stats.num_siv_independent++;
2787 dependence_stats.num_siv_dependent++;
2789 else if (can_use_analyze_subscript_affine_affine (&chrec_a,
2792 analyze_subscript_affine_affine (chrec_a, chrec_b,
2793 overlaps_a, overlaps_b,
2796 if (CF_NOT_KNOWN_P (*overlaps_a)
2797 || CF_NOT_KNOWN_P (*overlaps_b))
2798 dependence_stats.num_siv_unimplemented++;
2799 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2800 || CF_NO_DEPENDENCE_P (*overlaps_b))
2801 dependence_stats.num_siv_independent++;
2803 dependence_stats.num_siv_dependent++;
2806 goto siv_subscript_dontknow;
2811 siv_subscript_dontknow:;
2812 if (dump_file && (dump_flags & TDF_DETAILS))
2813 fprintf (dump_file, "siv test failed: unimplemented.\n");
2814 *overlaps_a = conflict_fn_not_known ();
2815 *overlaps_b = conflict_fn_not_known ();
2816 *last_conflicts = chrec_dont_know;
2817 dependence_stats.num_siv_unimplemented++;
2820 if (dump_file && (dump_flags & TDF_DETAILS))
2821 fprintf (dump_file, ")\n");
2824 /* Returns false if we can prove that the greatest common divisor of the steps
2825 of CHREC does not divide CST, false otherwise. */
2828 gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst)
2830 HOST_WIDE_INT cd = 0, val;
2833 if (!host_integerp (cst, 0))
2835 val = tree_low_cst (cst, 0);
2837 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
2839 step = CHREC_RIGHT (chrec);
2840 if (!host_integerp (step, 0))
2842 cd = gcd (cd, tree_low_cst (step, 0));
2843 chrec = CHREC_LEFT (chrec);
2846 return val % cd == 0;
2849 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2850 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2851 functions that describe the relation between the elements accessed
2852 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2855 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2858 analyze_miv_subscript (tree chrec_a,
2860 conflict_function **overlaps_a,
2861 conflict_function **overlaps_b,
2862 tree *last_conflicts,
2863 struct loop *loop_nest)
2865 tree type, difference;
2867 dependence_stats.num_miv++;
2868 if (dump_file && (dump_flags & TDF_DETAILS))
2869 fprintf (dump_file, "(analyze_miv_subscript \n");
2871 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
2872 chrec_a = chrec_convert (type, chrec_a, NULL);
2873 chrec_b = chrec_convert (type, chrec_b, NULL);
2874 difference = chrec_fold_minus (type, chrec_a, chrec_b);
2876 if (eq_evolutions_p (chrec_a, chrec_b))
2878 /* Access functions are the same: all the elements are accessed
2879 in the same order. */
2880 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2881 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2882 *last_conflicts = max_stmt_executions_tree (get_chrec_loop (chrec_a));
2883 dependence_stats.num_miv_dependent++;
2886 else if (evolution_function_is_constant_p (difference)
2887 /* For the moment, the following is verified:
2888 evolution_function_is_affine_multivariate_p (chrec_a,
2890 && !gcd_of_steps_may_divide_p (chrec_a, difference))
2892 /* testsuite/.../ssa-chrec-33.c
2893 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2895 The difference is 1, and all the evolution steps are multiples
2896 of 2, consequently there are no overlapping elements. */
2897 *overlaps_a = conflict_fn_no_dependence ();
2898 *overlaps_b = conflict_fn_no_dependence ();
2899 *last_conflicts = integer_zero_node;
2900 dependence_stats.num_miv_independent++;
2903 else if (evolution_function_is_affine_multivariate_p (chrec_a, loop_nest->num)
2904 && !chrec_contains_symbols (chrec_a)
2905 && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num)
2906 && !chrec_contains_symbols (chrec_b))
2908 /* testsuite/.../ssa-chrec-35.c
2909 {0, +, 1}_2 vs. {0, +, 1}_3
2910 the overlapping elements are respectively located at iterations:
2911 {0, +, 1}_x and {0, +, 1}_x,
2912 in other words, we have the equality:
2913 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2916 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2917 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2919 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2920 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2922 analyze_subscript_affine_affine (chrec_a, chrec_b,
2923 overlaps_a, overlaps_b, last_conflicts);
2925 if (CF_NOT_KNOWN_P (*overlaps_a)
2926 || CF_NOT_KNOWN_P (*overlaps_b))
2927 dependence_stats.num_miv_unimplemented++;
2928 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2929 || CF_NO_DEPENDENCE_P (*overlaps_b))
2930 dependence_stats.num_miv_independent++;
2932 dependence_stats.num_miv_dependent++;
2937 /* When the analysis is too difficult, answer "don't know". */
2938 if (dump_file && (dump_flags & TDF_DETAILS))
2939 fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
2941 *overlaps_a = conflict_fn_not_known ();
2942 *overlaps_b = conflict_fn_not_known ();
2943 *last_conflicts = chrec_dont_know;
2944 dependence_stats.num_miv_unimplemented++;
2947 if (dump_file && (dump_flags & TDF_DETAILS))
2948 fprintf (dump_file, ")\n");
2951 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2952 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
2953 OVERLAP_ITERATIONS_B are initialized with two functions that
2954 describe the iterations that contain conflicting elements.
2956 Remark: For an integer k >= 0, the following equality is true:
2958 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2962 analyze_overlapping_iterations (tree chrec_a,
2964 conflict_function **overlap_iterations_a,
2965 conflict_function **overlap_iterations_b,
2966 tree *last_conflicts, struct loop *loop_nest)
2968 unsigned int lnn = loop_nest->num;
2970 dependence_stats.num_subscript_tests++;
2972 if (dump_file && (dump_flags & TDF_DETAILS))
2974 fprintf (dump_file, "(analyze_overlapping_iterations \n");
2975 fprintf (dump_file, " (chrec_a = ");
2976 print_generic_expr (dump_file, chrec_a, 0);
2977 fprintf (dump_file, ")\n (chrec_b = ");
2978 print_generic_expr (dump_file, chrec_b, 0);
2979 fprintf (dump_file, ")\n");
2982 if (chrec_a == NULL_TREE
2983 || chrec_b == NULL_TREE
2984 || chrec_contains_undetermined (chrec_a)
2985 || chrec_contains_undetermined (chrec_b))
2987 dependence_stats.num_subscript_undetermined++;
2989 *overlap_iterations_a = conflict_fn_not_known ();
2990 *overlap_iterations_b = conflict_fn_not_known ();
2993 /* If they are the same chrec, and are affine, they overlap
2994 on every iteration. */
2995 else if (eq_evolutions_p (chrec_a, chrec_b)
2996 && (evolution_function_is_affine_multivariate_p (chrec_a, lnn)
2997 || operand_equal_p (chrec_a, chrec_b, 0)))
2999 dependence_stats.num_same_subscript_function++;
3000 *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
3001 *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
3002 *last_conflicts = chrec_dont_know;
3005 /* If they aren't the same, and aren't affine, we can't do anything
3007 else if ((chrec_contains_symbols (chrec_a)
3008 || chrec_contains_symbols (chrec_b))
3009 && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
3010 || !evolution_function_is_affine_multivariate_p (chrec_b, lnn)))
3012 dependence_stats.num_subscript_undetermined++;
3013 *overlap_iterations_a = conflict_fn_not_known ();
3014 *overlap_iterations_b = conflict_fn_not_known ();
3017 else if (ziv_subscript_p (chrec_a, chrec_b))
3018 analyze_ziv_subscript (chrec_a, chrec_b,
3019 overlap_iterations_a, overlap_iterations_b,
3022 else if (siv_subscript_p (chrec_a, chrec_b))
3023 analyze_siv_subscript (chrec_a, chrec_b,
3024 overlap_iterations_a, overlap_iterations_b,
3025 last_conflicts, lnn);
3028 analyze_miv_subscript (chrec_a, chrec_b,
3029 overlap_iterations_a, overlap_iterations_b,
3030 last_conflicts, loop_nest);
3032 if (dump_file && (dump_flags & TDF_DETAILS))
3034 fprintf (dump_file, " (overlap_iterations_a = ");
3035 dump_conflict_function (dump_file, *overlap_iterations_a);
3036 fprintf (dump_file, ")\n (overlap_iterations_b = ");
3037 dump_conflict_function (dump_file, *overlap_iterations_b);
3038 fprintf (dump_file, ")\n");
3039 fprintf (dump_file, ")\n");
3043 /* Helper function for uniquely inserting distance vectors. */
3046 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
3051 FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), i, v)
3052 if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
3055 VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
3058 /* Helper function for uniquely inserting direction vectors. */
3061 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
3066 FOR_EACH_VEC_ELT (lambda_vector, DDR_DIR_VECTS (ddr), i, v)
3067 if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
3070 VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
3073 /* Add a distance of 1 on all the loops outer than INDEX. If we
3074 haven't yet determined a distance for this outer loop, push a new
3075 distance vector composed of the previous distance, and a distance
3076 of 1 for this outer loop. Example:
3084 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
3085 save (0, 1), then we have to save (1, 0). */
3088 add_outer_distances (struct data_dependence_relation *ddr,
3089 lambda_vector dist_v, int index)
3091 /* For each outer loop where init_v is not set, the accesses are
3092 in dependence of distance 1 in the loop. */
3093 while (--index >= 0)
3095 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3096 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3098 save_dist_v (ddr, save_v);
3102 /* Return false when fail to represent the data dependence as a
3103 distance vector. INIT_B is set to true when a component has been
3104 added to the distance vector DIST_V. INDEX_CARRY is then set to
3105 the index in DIST_V that carries the dependence. */
3108 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
3109 struct data_reference *ddr_a,
3110 struct data_reference *ddr_b,
3111 lambda_vector dist_v, bool *init_b,
3115 lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3117 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3119 tree access_fn_a, access_fn_b;
3120 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3122 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3124 non_affine_dependence_relation (ddr);
3128 access_fn_a = DR_ACCESS_FN (ddr_a, i);
3129 access_fn_b = DR_ACCESS_FN (ddr_b, i);
3131 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3132 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3135 int var_a = CHREC_VARIABLE (access_fn_a);
3136 int var_b = CHREC_VARIABLE (access_fn_b);
3139 || chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3141 non_affine_dependence_relation (ddr);
3145 dist = int_cst_value (SUB_DISTANCE (subscript));
3146 index = index_in_loop_nest (var_a, DDR_LOOP_NEST (ddr));
3147 *index_carry = MIN (index, *index_carry);
3149 /* This is the subscript coupling test. If we have already
3150 recorded a distance for this loop (a distance coming from
3151 another subscript), it should be the same. For example,
3152 in the following code, there is no dependence:
3159 if (init_v[index] != 0 && dist_v[index] != dist)
3161 finalize_ddr_dependent (ddr, chrec_known);
3165 dist_v[index] = dist;
3169 else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
3171 /* This can be for example an affine vs. constant dependence
3172 (T[i] vs. T[3]) that is not an affine dependence and is
3173 not representable as a distance vector. */
3174 non_affine_dependence_relation (ddr);
3182 /* Return true when the DDR contains only constant access functions. */
3185 constant_access_functions (const struct data_dependence_relation *ddr)
3189 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3190 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
3191 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
3197 /* Helper function for the case where DDR_A and DDR_B are the same
3198 multivariate access function with a constant step. For an example
3202 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
3205 tree c_1 = CHREC_LEFT (c_2);
3206 tree c_0 = CHREC_LEFT (c_1);
3207 lambda_vector dist_v;
3210 /* Polynomials with more than 2 variables are not handled yet. When
3211 the evolution steps are parameters, it is not possible to
3212 represent the dependence using classical distance vectors. */
3213 if (TREE_CODE (c_0) != INTEGER_CST
3214 || TREE_CODE (CHREC_RIGHT (c_1)) != INTEGER_CST
3215 || TREE_CODE (CHREC_RIGHT (c_2)) != INTEGER_CST)
3217 DDR_AFFINE_P (ddr) = false;
3221 x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
3222 x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
3224 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3225 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3226 v1 = int_cst_value (CHREC_RIGHT (c_1));
3227 v2 = int_cst_value (CHREC_RIGHT (c_2));
3240 save_dist_v (ddr, dist_v);
3242 add_outer_distances (ddr, dist_v, x_1);
3245 /* Helper function for the case where DDR_A and DDR_B are the same
3246 access functions. */
3249 add_other_self_distances (struct data_dependence_relation *ddr)
3251 lambda_vector dist_v;
3253 int index_carry = DDR_NB_LOOPS (ddr);
3255 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3257 tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
3259 if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
3261 if (!evolution_function_is_univariate_p (access_fun))
3263 if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
3265 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
3269 access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);
3271 if (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC)
3272 add_multivariate_self_dist (ddr, access_fun);
3274 /* The evolution step is not constant: it varies in
3275 the outer loop, so this cannot be represented by a
3276 distance vector. For example in pr34635.c the
3277 evolution is {0, +, {0, +, 4}_1}_2. */
3278 DDR_AFFINE_P (ddr) = false;
3283 index_carry = MIN (index_carry,
3284 index_in_loop_nest (CHREC_VARIABLE (access_fun),
3285 DDR_LOOP_NEST (ddr)));
3289 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3290 add_outer_distances (ddr, dist_v, index_carry);
3294 insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
3296 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3298 dist_v[DDR_INNER_LOOP (ddr)] = 1;
3299 save_dist_v (ddr, dist_v);
3302 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
3303 is the case for example when access functions are the same and
3304 equal to a constant, as in:
3311 in which case the distance vectors are (0) and (1). */
3314 add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
3318 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3320 subscript_p sub = DDR_SUBSCRIPT (ddr, i);
3321 conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
3322 conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
3324 for (j = 0; j < ca->n; j++)
3325 if (affine_function_zero_p (ca->fns[j]))
3327 insert_innermost_unit_dist_vector (ddr);
3331 for (j = 0; j < cb->n; j++)
3332 if (affine_function_zero_p (cb->fns[j]))
3334 insert_innermost_unit_dist_vector (ddr);
3340 /* Compute the classic per loop distance vector. DDR is the data
3341 dependence relation to build a vector from. Return false when fail
3342 to represent the data dependence as a distance vector. */
3345 build_classic_dist_vector (struct data_dependence_relation *ddr,
3346 struct loop *loop_nest)
3348 bool init_b = false;
3349 int index_carry = DDR_NB_LOOPS (ddr);
3350 lambda_vector dist_v;
3352 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3355 if (same_access_functions (ddr))
3357 /* Save the 0 vector. */
3358 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3359 save_dist_v (ddr, dist_v);
3361 if (constant_access_functions (ddr))
3362 add_distance_for_zero_overlaps (ddr);
3364 if (DDR_NB_LOOPS (ddr) > 1)
3365 add_other_self_distances (ddr);
3370 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3371 if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
3372 dist_v, &init_b, &index_carry))
3375 /* Save the distance vector if we initialized one. */
3378 /* Verify a basic constraint: classic distance vectors should
3379 always be lexicographically positive.
3381 Data references are collected in the order of execution of
3382 the program, thus for the following loop
3384 | for (i = 1; i < 100; i++)
3385 | for (j = 1; j < 100; j++)
3387 | t = T[j+1][i-1]; // A
3388 | T[j][i] = t + 2; // B
3391 references are collected following the direction of the wind:
3392 A then B. The data dependence tests are performed also
3393 following this order, such that we're looking at the distance
3394 separating the elements accessed by A from the elements later
3395 accessed by B. But in this example, the distance returned by
3396 test_dep (A, B) is lexicographically negative (-1, 1), that
3397 means that the access A occurs later than B with respect to
3398 the outer loop, ie. we're actually looking upwind. In this
3399 case we solve test_dep (B, A) looking downwind to the
3400 lexicographically positive solution, that returns the
3401 distance vector (1, -1). */
3402 if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
3404 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3405 if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3408 compute_subscript_distance (ddr);
3409 if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3410 save_v, &init_b, &index_carry))
3412 save_dist_v (ddr, save_v);
3413 DDR_REVERSED_P (ddr) = true;
3415 /* In this case there is a dependence forward for all the
3418 | for (k = 1; k < 100; k++)
3419 | for (i = 1; i < 100; i++)
3420 | for (j = 1; j < 100; j++)
3422 | t = T[j+1][i-1]; // A
3423 | T[j][i] = t + 2; // B
3431 if (DDR_NB_LOOPS (ddr) > 1)
3433 add_outer_distances (ddr, save_v, index_carry);
3434 add_outer_distances (ddr, dist_v, index_carry);
3439 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3440 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3442 if (DDR_NB_LOOPS (ddr) > 1)
3444 lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3446 if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr),
3447 DDR_A (ddr), loop_nest))
3449 compute_subscript_distance (ddr);
3450 if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3451 opposite_v, &init_b,
3455 save_dist_v (ddr, save_v);
3456 add_outer_distances (ddr, dist_v, index_carry);
3457 add_outer_distances (ddr, opposite_v, index_carry);
3460 save_dist_v (ddr, save_v);
3465 /* There is a distance of 1 on all the outer loops: Example:
3466 there is a dependence of distance 1 on loop_1 for the array A.
3472 add_outer_distances (ddr, dist_v,
3473 lambda_vector_first_nz (dist_v,
3474 DDR_NB_LOOPS (ddr), 0));
3477 if (dump_file && (dump_flags & TDF_DETAILS))
3481 fprintf (dump_file, "(build_classic_dist_vector\n");
3482 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3484 fprintf (dump_file, " dist_vector = (");
3485 print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
3486 DDR_NB_LOOPS (ddr));
3487 fprintf (dump_file, " )\n");
3489 fprintf (dump_file, ")\n");
3495 /* Return the direction for a given distance.
3496 FIXME: Computing dir this way is suboptimal, since dir can catch
3497 cases that dist is unable to represent. */
3499 static inline enum data_dependence_direction
3500 dir_from_dist (int dist)
3503 return dir_positive;
3505 return dir_negative;
3510 /* Compute the classic per loop direction vector. DDR is the data
3511 dependence relation to build a vector from. */
3514 build_classic_dir_vector (struct data_dependence_relation *ddr)
3517 lambda_vector dist_v;
3519 FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v)
3521 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3523 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3524 dir_v[j] = dir_from_dist (dist_v[j]);
3526 save_dir_v (ddr, dir_v);
3530 /* Helper function. Returns true when there is a dependence between
3531 data references DRA and DRB. */
3534 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
3535 struct data_reference *dra,
3536 struct data_reference *drb,
3537 struct loop *loop_nest)
3540 tree last_conflicts;
3541 struct subscript *subscript;
3542 tree res = NULL_TREE;
3544 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3547 conflict_function *overlaps_a, *overlaps_b;
3549 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
3550 DR_ACCESS_FN (drb, i),
3551 &overlaps_a, &overlaps_b,
3552 &last_conflicts, loop_nest);
3554 if (SUB_CONFLICTS_IN_A (subscript))
3555 free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
3556 if (SUB_CONFLICTS_IN_B (subscript))
3557 free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
3559 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3560 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3561 SUB_LAST_CONFLICT (subscript) = last_conflicts;
3563 /* If there is any undetermined conflict function we have to
3564 give a conservative answer in case we cannot prove that
3565 no dependence exists when analyzing another subscript. */
3566 if (CF_NOT_KNOWN_P (overlaps_a)
3567 || CF_NOT_KNOWN_P (overlaps_b))
3569 res = chrec_dont_know;
3573 /* When there is a subscript with no dependence we can stop. */
3574 else if (CF_NO_DEPENDENCE_P (overlaps_a)
3575 || CF_NO_DEPENDENCE_P (overlaps_b))
3582 if (res == NULL_TREE)
3585 if (res == chrec_known)
3586 dependence_stats.num_dependence_independent++;
3588 dependence_stats.num_dependence_undetermined++;
3589 finalize_ddr_dependent (ddr, res);
3593 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3596 subscript_dependence_tester (struct data_dependence_relation *ddr,
3597 struct loop *loop_nest)
3600 if (dump_file && (dump_flags & TDF_DETAILS))
3601 fprintf (dump_file, "(subscript_dependence_tester \n");
3603 if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest))
3604 dependence_stats.num_dependence_dependent++;
3606 compute_subscript_distance (ddr);
3607 if (build_classic_dist_vector (ddr, loop_nest))
3608 build_classic_dir_vector (ddr);
3610 if (dump_file && (dump_flags & TDF_DETAILS))
3611 fprintf (dump_file, ")\n");
3614 /* Returns true when all the access functions of A are affine or
3615 constant with respect to LOOP_NEST. */
3618 access_functions_are_affine_or_constant_p (const struct data_reference *a,
3619 const struct loop *loop_nest)
3622 VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
3625 FOR_EACH_VEC_ELT (tree, fns, i, t)
3626 if (!evolution_function_is_invariant_p (t, loop_nest->num)
3627 && !evolution_function_is_affine_multivariate_p (t, loop_nest->num))
3633 /* Initializes an equation for an OMEGA problem using the information
3634 contained in the ACCESS_FUN. Returns true when the operation
3637 PB is the omega constraint system.
3638 EQ is the number of the equation to be initialized.
3639 OFFSET is used for shifting the variables names in the constraints:
3640 a constrain is composed of 2 * the number of variables surrounding
3641 dependence accesses. OFFSET is set either to 0 for the first n variables,
3642 then it is set to n.
3643 ACCESS_FUN is expected to be an affine chrec. */
3646 init_omega_eq_with_af (omega_pb pb, unsigned eq,
3647 unsigned int offset, tree access_fun,
3648 struct data_dependence_relation *ddr)
3650 switch (TREE_CODE (access_fun))
3652 case POLYNOMIAL_CHREC:
3654 tree left = CHREC_LEFT (access_fun);
3655 tree right = CHREC_RIGHT (access_fun);
3656 int var = CHREC_VARIABLE (access_fun);
3659 if (TREE_CODE (right) != INTEGER_CST)
3662 var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
3663 pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
3665 /* Compute the innermost loop index. */
3666 DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
3669 pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
3670 += int_cst_value (right);
3672 switch (TREE_CODE (left))
3674 case POLYNOMIAL_CHREC:
3675 return init_omega_eq_with_af (pb, eq, offset, left, ddr);
3678 pb->eqs[eq].coef[0] += int_cst_value (left);
3687 pb->eqs[eq].coef[0] += int_cst_value (access_fun);
3695 /* As explained in the comments preceding init_omega_for_ddr, we have
3696 to set up a system for each loop level, setting outer loops
3697 variation to zero, and current loop variation to positive or zero.
3698 Save each lexico positive distance vector. */
3701 omega_extract_distance_vectors (omega_pb pb,
3702 struct data_dependence_relation *ddr)
3706 struct loop *loopi, *loopj;
3707 enum omega_result res;
3709 /* Set a new problem for each loop in the nest. The basis is the
3710 problem that we have initialized until now. On top of this we
3711 add new constraints. */
3712 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3713 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3716 omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
3717 DDR_NB_LOOPS (ddr));
3719 omega_copy_problem (copy, pb);
3721 /* For all the outer loops "loop_j", add "dj = 0". */
3723 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3725 eq = omega_add_zero_eq (copy, omega_black);
3726 copy->eqs[eq].coef[j + 1] = 1;
3729 /* For "loop_i", add "0 <= di". */
3730 geq = omega_add_zero_geq (copy, omega_black);
3731 copy->geqs[geq].coef[i + 1] = 1;
3733 /* Reduce the constraint system, and test that the current
3734 problem is feasible. */
3735 res = omega_simplify_problem (copy);
3736 if (res == omega_false
3737 || res == omega_unknown
3738 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3741 for (eq = 0; eq < copy->num_subs; eq++)
3742 if (copy->subs[eq].key == (int) i + 1)
3744 dist = copy->subs[eq].coef[0];
3750 /* Reinitialize problem... */
3751 omega_copy_problem (copy, pb);
3753 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3755 eq = omega_add_zero_eq (copy, omega_black);
3756 copy->eqs[eq].coef[j + 1] = 1;
3759 /* ..., but this time "di = 1". */
3760 eq = omega_add_zero_eq (copy, omega_black);
3761 copy->eqs[eq].coef[i + 1] = 1;
3762 copy->eqs[eq].coef[0] = -1;
3764 res = omega_simplify_problem (copy);
3765 if (res == omega_false
3766 || res == omega_unknown
3767 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3770 for (eq = 0; eq < copy->num_subs; eq++)
3771 if (copy->subs[eq].key == (int) i + 1)
3773 dist = copy->subs[eq].coef[0];
3779 /* Save the lexicographically positive distance vector. */
3782 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3783 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3787 for (eq = 0; eq < copy->num_subs; eq++)
3788 if (copy->subs[eq].key > 0)
3790 dist = copy->subs[eq].coef[0];
3791 dist_v[copy->subs[eq].key - 1] = dist;
3794 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3795 dir_v[j] = dir_from_dist (dist_v[j]);
3797 save_dist_v (ddr, dist_v);
3798 save_dir_v (ddr, dir_v);
3802 omega_free_problem (copy);
3806 /* This is called for each subscript of a tuple of data references:
3807 insert an equality for representing the conflicts. */
3810 omega_setup_subscript (tree access_fun_a, tree access_fun_b,
3811 struct data_dependence_relation *ddr,
3812 omega_pb pb, bool *maybe_dependent)
3815 tree type = signed_type_for_types (TREE_TYPE (access_fun_a),
3816 TREE_TYPE (access_fun_b));
3817 tree fun_a = chrec_convert (type, access_fun_a, NULL);
3818 tree fun_b = chrec_convert (type, access_fun_b, NULL);
3819 tree difference = chrec_fold_minus (type, fun_a, fun_b);
3822 /* When the fun_a - fun_b is not constant, the dependence is not
3823 captured by the classic distance vector representation. */
3824 if (TREE_CODE (difference) != INTEGER_CST)
3828 if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
3830 /* There is no dependence. */
3831 *maybe_dependent = false;
3835 minus_one = build_int_cst (type, -1);
3836 fun_b = chrec_fold_multiply (type, fun_b, minus_one);
3838 eq = omega_add_zero_eq (pb, omega_black);
3839 if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
3840 || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
3841 /* There is probably a dependence, but the system of
3842 constraints cannot be built: answer "don't know". */
3846 if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
3847 && !int_divides_p (lambda_vector_gcd
3848 ((lambda_vector) &(pb->eqs[eq].coef[1]),
3849 2 * DDR_NB_LOOPS (ddr)),
3850 pb->eqs[eq].coef[0]))
3852 /* There is no dependence. */
3853 *maybe_dependent = false;
3860 /* Helper function, same as init_omega_for_ddr but specialized for
3861 data references A and B. */
3864 init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
3865 struct data_dependence_relation *ddr,
3866 omega_pb pb, bool *maybe_dependent)
3871 unsigned nb_loops = DDR_NB_LOOPS (ddr);
3873 /* Insert an equality per subscript. */
3874 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3876 if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
3877 ddr, pb, maybe_dependent))
3879 else if (*maybe_dependent == false)
3881 /* There is no dependence. */
3882 DDR_ARE_DEPENDENT (ddr) = chrec_known;
3887 /* Insert inequalities: constraints corresponding to the iteration
3888 domain, i.e. the loops surrounding the references "loop_x" and
3889 the distance variables "dx". The layout of the OMEGA
3890 representation is as follows:
3891 - coef[0] is the constant
3892 - coef[1..nb_loops] are the protected variables that will not be
3893 removed by the solver: the "dx"
3894 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3896 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3897 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3899 HOST_WIDE_INT nbi = max_stmt_executions_int (loopi, true);
3902 ineq = omega_add_zero_geq (pb, omega_black);
3903 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3905 /* 0 <= loop_x + dx */
3906 ineq = omega_add_zero_geq (pb, omega_black);
3907 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3908 pb->geqs[ineq].coef[i + 1] = 1;
3912 /* loop_x <= nb_iters */
3913 ineq = omega_add_zero_geq (pb, omega_black);
3914 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3915 pb->geqs[ineq].coef[0] = nbi;
3917 /* loop_x + dx <= nb_iters */
3918 ineq = omega_add_zero_geq (pb, omega_black);
3919 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3920 pb->geqs[ineq].coef[i + 1] = -1;
3921 pb->geqs[ineq].coef[0] = nbi;
3923 /* A step "dx" bigger than nb_iters is not feasible, so
3924 add "0 <= nb_iters + dx", */
3925 ineq = omega_add_zero_geq (pb, omega_black);
3926 pb->geqs[ineq].coef[i + 1] = 1;
3927 pb->geqs[ineq].coef[0] = nbi;
3928 /* and "dx <= nb_iters". */
3929 ineq = omega_add_zero_geq (pb, omega_black);
3930 pb->geqs[ineq].coef[i + 1] = -1;
3931 pb->geqs[ineq].coef[0] = nbi;
3935 omega_extract_distance_vectors (pb, ddr);
3940 /* Sets up the Omega dependence problem for the data dependence
3941 relation DDR. Returns false when the constraint system cannot be
3942 built, ie. when the test answers "don't know". Returns true
3943 otherwise, and when independence has been proved (using one of the
3944 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3945 set MAYBE_DEPENDENT to true.
3947 Example: for setting up the dependence system corresponding to the
3948 conflicting accesses
3953 | ... A[2*j, 2*(i + j)]
3957 the following constraints come from the iteration domain:
3964 where di, dj are the distance variables. The constraints
3965 representing the conflicting elements are:
3968 i + 1 = 2 * (i + di + j + dj)
3970 For asking that the resulting distance vector (di, dj) be
3971 lexicographically positive, we insert the constraint "di >= 0". If
3972 "di = 0" in the solution, we fix that component to zero, and we
3973 look at the inner loops: we set a new problem where all the outer
3974 loop distances are zero, and fix this inner component to be
3975 positive. When one of the components is positive, we save that
3976 distance, and set a new problem where the distance on this loop is
3977 zero, searching for other distances in the inner loops. Here is
3978 the classic example that illustrates that we have to set for each
3979 inner loop a new problem:
3987 we have to save two distances (1, 0) and (0, 1).
3989 Given two array references, refA and refB, we have to set the
3990 dependence problem twice, refA vs. refB and refB vs. refA, and we
3991 cannot do a single test, as refB might occur before refA in the
3992 inner loops, and the contrary when considering outer loops: ex.
3997 | T[{1,+,1}_2][{1,+,1}_1] // refA
3998 | T[{2,+,1}_2][{0,+,1}_1] // refB
4003 refB touches the elements in T before refA, and thus for the same
4004 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
4005 but for successive loop_0 iterations, we have (1, -1, 1)
4007 The Omega solver expects the distance variables ("di" in the
4008 previous example) to come first in the constraint system (as
4009 variables to be protected, or "safe" variables), the constraint
4010 system is built using the following layout:
4012 "cst | distance vars | index vars".
4016 init_omega_for_ddr (struct data_dependence_relation *ddr,
4017 bool *maybe_dependent)
4022 *maybe_dependent = true;
4024 if (same_access_functions (ddr))
4027 lambda_vector dir_v;
4029 /* Save the 0 vector. */
4030 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
4031 dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4032 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
4033 dir_v[j] = dir_equal;
4034 save_dir_v (ddr, dir_v);
4036 /* Save the dependences carried by outer loops. */
4037 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4038 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
4040 omega_free_problem (pb);
4044 /* Omega expects the protected variables (those that have to be kept
4045 after elimination) to appear first in the constraint system.
4046 These variables are the distance variables. In the following
4047 initialization we declare NB_LOOPS safe variables, and the total
4048 number of variables for the constraint system is 2*NB_LOOPS. */
4049 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4050 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
4052 omega_free_problem (pb);
4054 /* Stop computation if not decidable, or no dependence. */
4055 if (res == false || *maybe_dependent == false)
4058 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4059 res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
4061 omega_free_problem (pb);
4066 /* Return true when DDR contains the same information as that stored
4067 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
4070 ddr_consistent_p (FILE *file,
4071 struct data_dependence_relation *ddr,
4072 VEC (lambda_vector, heap) *dist_vects,
4073 VEC (lambda_vector, heap) *dir_vects)
4077 /* If dump_file is set, output there. */
4078 if (dump_file && (dump_flags & TDF_DETAILS))
4081 if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
4083 lambda_vector b_dist_v;
4084 fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
4085 VEC_length (lambda_vector, dist_vects),
4086 DDR_NUM_DIST_VECTS (ddr));
4088 fprintf (file, "Banerjee dist vectors:\n");
4089 FOR_EACH_VEC_ELT (lambda_vector, dist_vects, i, b_dist_v)
4090 print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
4092 fprintf (file, "Omega dist vectors:\n");
4093 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
4094 print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
4096 fprintf (file, "data dependence relation:\n");
4097 dump_data_dependence_relation (file, ddr);
4099 fprintf (file, ")\n");
4103 if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
4105 fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
4106 VEC_length (lambda_vector, dir_vects),
4107 DDR_NUM_DIR_VECTS (ddr));
4111 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
4113 lambda_vector a_dist_v;
4114 lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
4116 /* Distance vectors are not ordered in the same way in the DDR
4117 and in the DIST_VECTS: search for a matching vector. */
4118 FOR_EACH_VEC_ELT (lambda_vector, dist_vects, j, a_dist_v)
4119 if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
4122 if (j == VEC_length (lambda_vector, dist_vects))
4124 fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
4125 print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
4126 fprintf (file, "not found in Omega dist vectors:\n");
4127 print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
4128 fprintf (file, "data dependence relation:\n");
4129 dump_data_dependence_relation (file, ddr);
4130 fprintf (file, ")\n");
4134 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
4136 lambda_vector a_dir_v;
4137 lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
4139 /* Direction vectors are not ordered in the same way in the DDR
4140 and in the DIR_VECTS: search for a matching vector. */
4141 FOR_EACH_VEC_ELT (lambda_vector, dir_vects, j, a_dir_v)
4142 if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
4145 if (j == VEC_length (lambda_vector, dist_vects))
4147 fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
4148 print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
4149 fprintf (file, "not found in Omega dir vectors:\n");
4150 print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
4151 fprintf (file, "data dependence relation:\n");
4152 dump_data_dependence_relation (file, ddr);
4153 fprintf (file, ")\n");
4160 /* This computes the affine dependence relation between A and B with
4161 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
4162 independence between two accesses, while CHREC_DONT_KNOW is used
4163 for representing the unknown relation.
4165 Note that it is possible to stop the computation of the dependence
4166 relation the first time we detect a CHREC_KNOWN element for a given
4170 compute_affine_dependence (struct data_dependence_relation *ddr,
4171 struct loop *loop_nest)
4173 struct data_reference *dra = DDR_A (ddr);
4174 struct data_reference *drb = DDR_B (ddr);
4176 if (dump_file && (dump_flags & TDF_DETAILS))
4178 fprintf (dump_file, "(compute_affine_dependence\n");
4179 fprintf (dump_file, " stmt_a: ");
4180 print_gimple_stmt (dump_file, DR_STMT (dra), 0, TDF_SLIM);
4181 fprintf (dump_file, " stmt_b: ");
4182 print_gimple_stmt (dump_file, DR_STMT (drb), 0, TDF_SLIM);
4185 /* Analyze only when the dependence relation is not yet known. */
4186 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4188 dependence_stats.num_dependence_tests++;
4190 if (access_functions_are_affine_or_constant_p (dra, loop_nest)
4191 && access_functions_are_affine_or_constant_p (drb, loop_nest))
4193 if (flag_check_data_deps)
4195 /* Compute the dependences using the first algorithm. */
4196 subscript_dependence_tester (ddr, loop_nest);
4198 if (dump_file && (dump_flags & TDF_DETAILS))
4200 fprintf (dump_file, "\n\nBanerjee Analyzer\n");
4201 dump_data_dependence_relation (dump_file, ddr);
4204 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4206 bool maybe_dependent;
4207 VEC (lambda_vector, heap) *dir_vects, *dist_vects;
4209 /* Save the result of the first DD analyzer. */
4210 dist_vects = DDR_DIST_VECTS (ddr);
4211 dir_vects = DDR_DIR_VECTS (ddr);
4213 /* Reset the information. */
4214 DDR_DIST_VECTS (ddr) = NULL;
4215 DDR_DIR_VECTS (ddr) = NULL;
4217 /* Compute the same information using Omega. */
4218 if (!init_omega_for_ddr (ddr, &maybe_dependent))
4219 goto csys_dont_know;
4221 if (dump_file && (dump_flags & TDF_DETAILS))
4223 fprintf (dump_file, "Omega Analyzer\n");
4224 dump_data_dependence_relation (dump_file, ddr);
4227 /* Check that we get the same information. */
4228 if (maybe_dependent)
4229 gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
4234 subscript_dependence_tester (ddr, loop_nest);
4237 /* As a last case, if the dependence cannot be determined, or if
4238 the dependence is considered too difficult to determine, answer
4243 dependence_stats.num_dependence_undetermined++;
4245 if (dump_file && (dump_flags & TDF_DETAILS))
4247 fprintf (dump_file, "Data ref a:\n");
4248 dump_data_reference (dump_file, dra);
4249 fprintf (dump_file, "Data ref b:\n");
4250 dump_data_reference (dump_file, drb);
4251 fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
4253 finalize_ddr_dependent (ddr, chrec_dont_know);
4257 if (dump_file && (dump_flags & TDF_DETAILS))
4259 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4260 fprintf (dump_file, ") -> no dependence\n");
4261 else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
4262 fprintf (dump_file, ") -> dependence analysis failed\n");
4264 fprintf (dump_file, ")\n");
4268 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4269 the data references in DATAREFS, in the LOOP_NEST. When
4270 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4271 relations. Return true when successful, i.e. data references number
4272 is small enough to be handled. */
4275 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
4276 VEC (ddr_p, heap) **dependence_relations,
4277 VEC (loop_p, heap) *loop_nest,
4278 bool compute_self_and_rr)
4280 struct data_dependence_relation *ddr;
4281 struct data_reference *a, *b;
4284 if ((int) VEC_length (data_reference_p, datarefs)
4285 > PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS))
4287 struct data_dependence_relation *ddr;
4289 /* Insert a single relation into dependence_relations:
4291 ddr = initialize_data_dependence_relation (NULL, NULL, loop_nest);
4292 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4296 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, a)
4297 for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
4298 if (DR_IS_WRITE (a) || DR_IS_WRITE (b) || compute_self_and_rr)
4300 ddr = initialize_data_dependence_relation (a, b, loop_nest);
4301 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4303 compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
4306 if (compute_self_and_rr)
4307 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, a)
4309 ddr = initialize_data_dependence_relation (a, a, loop_nest);
4310 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4312 compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
4318 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4319 true if STMT clobbers memory, false otherwise. */
4322 get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references)
4324 bool clobbers_memory = false;
4327 enum gimple_code stmt_code = gimple_code (stmt);
4331 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4332 Calls have side-effects, except those to const or pure
4334 if ((stmt_code == GIMPLE_CALL
4335 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
4336 || (stmt_code == GIMPLE_ASM
4337 && (gimple_asm_volatile_p (stmt) || gimple_vuse (stmt))))
4338 clobbers_memory = true;
4340 if (!gimple_vuse (stmt))
4341 return clobbers_memory;
4343 if (stmt_code == GIMPLE_ASSIGN)
4346 op0 = gimple_assign_lhs_ptr (stmt);
4347 op1 = gimple_assign_rhs1_ptr (stmt);
4350 || (REFERENCE_CLASS_P (*op1)
4351 && (base = get_base_address (*op1))
4352 && TREE_CODE (base) != SSA_NAME))
4354 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4356 ref->is_read = true;
4359 else if (stmt_code == GIMPLE_CALL)
4363 op0 = gimple_call_lhs_ptr (stmt);
4364 n = gimple_call_num_args (stmt);
4365 for (i = 0; i < n; i++)
4367 op1 = gimple_call_arg_ptr (stmt, i);
4370 || (REFERENCE_CLASS_P (*op1) && get_base_address (*op1)))
4372 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4374 ref->is_read = true;
4379 return clobbers_memory;
4383 || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0))))
4385 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4387 ref->is_read = false;
4389 return clobbers_memory;
4392 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4393 reference, returns false, otherwise returns true. NEST is the outermost
4394 loop of the loop nest in which the references should be analyzed. */
4397 find_data_references_in_stmt (struct loop *nest, gimple stmt,
4398 VEC (data_reference_p, heap) **datarefs)
4401 VEC (data_ref_loc, heap) *references;
4404 data_reference_p dr;
4406 if (get_references_in_stmt (stmt, &references))
4408 VEC_free (data_ref_loc, heap, references);
4412 FOR_EACH_VEC_ELT (data_ref_loc, references, i, ref)
4414 dr = create_data_ref (nest, loop_containing_stmt (stmt),
4415 *ref->pos, stmt, ref->is_read);
4416 gcc_assert (dr != NULL);
4417 VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4419 VEC_free (data_ref_loc, heap, references);
4423 /* Stores the data references in STMT to DATAREFS. If there is an
4424 unanalyzable reference, returns false, otherwise returns true.
4425 NEST is the outermost loop of the loop nest in which the references
4426 should be instantiated, LOOP is the loop in which the references
4427 should be analyzed. */
4430 graphite_find_data_references_in_stmt (loop_p nest, loop_p loop, gimple stmt,
4431 VEC (data_reference_p, heap) **datarefs)
4434 VEC (data_ref_loc, heap) *references;
4437 data_reference_p dr;
4439 if (get_references_in_stmt (stmt, &references))
4441 VEC_free (data_ref_loc, heap, references);
4445 FOR_EACH_VEC_ELT (data_ref_loc, references, i, ref)
4447 dr = create_data_ref (nest, loop, *ref->pos, stmt, ref->is_read);
4448 gcc_assert (dr != NULL);
4449 VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4452 VEC_free (data_ref_loc, heap, references);
4456 /* Search the data references in LOOP, and record the information into
4457 DATAREFS. Returns chrec_dont_know when failing to analyze a
4458 difficult case, returns NULL_TREE otherwise. */
4461 find_data_references_in_bb (struct loop *loop, basic_block bb,
4462 VEC (data_reference_p, heap) **datarefs)
4464 gimple_stmt_iterator bsi;
4466 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4468 gimple stmt = gsi_stmt (bsi);
4470 if (!find_data_references_in_stmt (loop, stmt, datarefs))
4472 struct data_reference *res;
4473 res = XCNEW (struct data_reference);
4474 VEC_safe_push (data_reference_p, heap, *datarefs, res);
4476 return chrec_dont_know;
4483 /* Search the data references in LOOP, and record the information into
4484 DATAREFS. Returns chrec_dont_know when failing to analyze a
4485 difficult case, returns NULL_TREE otherwise.
4487 TODO: This function should be made smarter so that it can handle address
4488 arithmetic as if they were array accesses, etc. */
4491 find_data_references_in_loop (struct loop *loop,
4492 VEC (data_reference_p, heap) **datarefs)
4494 basic_block bb, *bbs;
4497 bbs = get_loop_body_in_dom_order (loop);
4499 for (i = 0; i < loop->num_nodes; i++)
4503 if (find_data_references_in_bb (loop, bb, datarefs) == chrec_dont_know)
4506 return chrec_dont_know;
4514 /* Recursive helper function. */
4517 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4519 /* Inner loops of the nest should not contain siblings. Example:
4520 when there are two consecutive loops,
4531 the dependence relation cannot be captured by the distance
4536 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4538 return find_loop_nest_1 (loop->inner, loop_nest);
4542 /* Return false when the LOOP is not well nested. Otherwise return
4543 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4544 contain the loops from the outermost to the innermost, as they will
4545 appear in the classic distance vector. */
4548 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4550 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4552 return find_loop_nest_1 (loop->inner, loop_nest);
4556 /* Returns true when the data dependences have been computed, false otherwise.
4557 Given a loop nest LOOP, the following vectors are returned:
4558 DATAREFS is initialized to all the array elements contained in this loop,
4559 DEPENDENCE_RELATIONS contains the relations between the data references.
4560 Compute read-read and self relations if
4561 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4564 compute_data_dependences_for_loop (struct loop *loop,
4565 bool compute_self_and_read_read_dependences,
4566 VEC (loop_p, heap) **loop_nest,
4567 VEC (data_reference_p, heap) **datarefs,
4568 VEC (ddr_p, heap) **dependence_relations)
4572 memset (&dependence_stats, 0, sizeof (dependence_stats));
4574 /* If the loop nest is not well formed, or one of the data references
4575 is not computable, give up without spending time to compute other
4578 || !find_loop_nest (loop, loop_nest)
4579 || find_data_references_in_loop (loop, datarefs) == chrec_dont_know
4580 || !compute_all_dependences (*datarefs, dependence_relations, *loop_nest,
4581 compute_self_and_read_read_dependences))
4584 if (dump_file && (dump_flags & TDF_STATS))
4586 fprintf (dump_file, "Dependence tester statistics:\n");
4588 fprintf (dump_file, "Number of dependence tests: %d\n",
4589 dependence_stats.num_dependence_tests);
4590 fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4591 dependence_stats.num_dependence_dependent);
4592 fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4593 dependence_stats.num_dependence_independent);
4594 fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4595 dependence_stats.num_dependence_undetermined);
4597 fprintf (dump_file, "Number of subscript tests: %d\n",
4598 dependence_stats.num_subscript_tests);
4599 fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4600 dependence_stats.num_subscript_undetermined);
4601 fprintf (dump_file, "Number of same subscript function: %d\n",
4602 dependence_stats.num_same_subscript_function);
4604 fprintf (dump_file, "Number of ziv tests: %d\n",
4605 dependence_stats.num_ziv);
4606 fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4607 dependence_stats.num_ziv_dependent);
4608 fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4609 dependence_stats.num_ziv_independent);
4610 fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4611 dependence_stats.num_ziv_unimplemented);
4613 fprintf (dump_file, "Number of siv tests: %d\n",
4614 dependence_stats.num_siv);
4615 fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4616 dependence_stats.num_siv_dependent);
4617 fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4618 dependence_stats.num_siv_independent);
4619 fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4620 dependence_stats.num_siv_unimplemented);
4622 fprintf (dump_file, "Number of miv tests: %d\n",
4623 dependence_stats.num_miv);
4624 fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4625 dependence_stats.num_miv_dependent);
4626 fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4627 dependence_stats.num_miv_independent);
4628 fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4629 dependence_stats.num_miv_unimplemented);
4635 /* Returns true when the data dependences for the basic block BB have been
4636 computed, false otherwise.
4637 DATAREFS is initialized to all the array elements contained in this basic
4638 block, DEPENDENCE_RELATIONS contains the relations between the data
4639 references. Compute read-read and self relations if
4640 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4642 compute_data_dependences_for_bb (basic_block bb,
4643 bool compute_self_and_read_read_dependences,
4644 VEC (data_reference_p, heap) **datarefs,
4645 VEC (ddr_p, heap) **dependence_relations)
4647 if (find_data_references_in_bb (NULL, bb, datarefs) == chrec_dont_know)
4650 return compute_all_dependences (*datarefs, dependence_relations, NULL,
4651 compute_self_and_read_read_dependences);
4654 /* Entry point (for testing only). Analyze all the data references
4655 and the dependence relations in LOOP.
4657 The data references are computed first.
4659 A relation on these nodes is represented by a complete graph. Some
4660 of the relations could be of no interest, thus the relations can be
4663 In the following function we compute all the relations. This is
4664 just a first implementation that is here for:
4665 - for showing how to ask for the dependence relations,
4666 - for the debugging the whole dependence graph,
4667 - for the dejagnu testcases and maintenance.
4669 It is possible to ask only for a part of the graph, avoiding to
4670 compute the whole dependence graph. The computed dependences are
4671 stored in a knowledge base (KB) such that later queries don't
4672 recompute the same information. The implementation of this KB is
4673 transparent to the optimizer, and thus the KB can be changed with a
4674 more efficient implementation, or the KB could be disabled. */
4676 analyze_all_data_dependences (struct loop *loop)
4679 int nb_data_refs = 10;
4680 VEC (data_reference_p, heap) *datarefs =
4681 VEC_alloc (data_reference_p, heap, nb_data_refs);
4682 VEC (ddr_p, heap) *dependence_relations =
4683 VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
4684 VEC (loop_p, heap) *loop_nest = VEC_alloc (loop_p, heap, 3);
4686 /* Compute DDs on the whole function. */
4687 compute_data_dependences_for_loop (loop, false, &loop_nest, &datarefs,
4688 &dependence_relations);
4692 dump_data_dependence_relations (dump_file, dependence_relations);
4693 fprintf (dump_file, "\n\n");
4695 if (dump_flags & TDF_DETAILS)
4696 dump_dist_dir_vectors (dump_file, dependence_relations);
4698 if (dump_flags & TDF_STATS)
4700 unsigned nb_top_relations = 0;
4701 unsigned nb_bot_relations = 0;
4702 unsigned nb_chrec_relations = 0;
4703 struct data_dependence_relation *ddr;
4705 FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
4707 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4710 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4714 nb_chrec_relations++;
4717 gather_stats_on_scev_database ();
4721 VEC_free (loop_p, heap, loop_nest);
4722 free_dependence_relations (dependence_relations);
4723 free_data_refs (datarefs);
4726 /* Computes all the data dependences and check that the results of
4727 several analyzers are the same. */
4730 tree_check_data_deps (void)
4733 struct loop *loop_nest;
4735 FOR_EACH_LOOP (li, loop_nest, 0)
4736 analyze_all_data_dependences (loop_nest);
4739 /* Free the memory used by a data dependence relation DDR. */
4742 free_dependence_relation (struct data_dependence_relation *ddr)
4747 if (DDR_SUBSCRIPTS (ddr))
4748 free_subscripts (DDR_SUBSCRIPTS (ddr));
4749 if (DDR_DIST_VECTS (ddr))
4750 VEC_free (lambda_vector, heap, DDR_DIST_VECTS (ddr));
4751 if (DDR_DIR_VECTS (ddr))
4752 VEC_free (lambda_vector, heap, DDR_DIR_VECTS (ddr));
4757 /* Free the memory used by the data dependence relations from
4758 DEPENDENCE_RELATIONS. */
4761 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
4764 struct data_dependence_relation *ddr;
4766 FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
4768 free_dependence_relation (ddr);
4770 VEC_free (ddr_p, heap, dependence_relations);
4773 /* Free the memory used by the data references from DATAREFS. */
4776 free_data_refs (VEC (data_reference_p, heap) *datarefs)
4779 struct data_reference *dr;
4781 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
4783 VEC_free (data_reference_p, heap, datarefs);
4788 /* Dump vertex I in RDG to FILE. */
4791 dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
4793 struct vertex *v = &(rdg->vertices[i]);
4794 struct graph_edge *e;
4796 fprintf (file, "(vertex %d: (%s%s) (in:", i,
4797 RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
4798 RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
4801 for (e = v->pred; e; e = e->pred_next)
4802 fprintf (file, " %d", e->src);
4804 fprintf (file, ") (out:");
4807 for (e = v->succ; e; e = e->succ_next)
4808 fprintf (file, " %d", e->dest);
4810 fprintf (file, ")\n");
4811 print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
4812 fprintf (file, ")\n");
4815 /* Call dump_rdg_vertex on stderr. */
4818 debug_rdg_vertex (struct graph *rdg, int i)
4820 dump_rdg_vertex (stderr, rdg, i);
4823 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4824 dumped vertices to that bitmap. */
4826 void dump_rdg_component (FILE *file, struct graph *rdg, int c, bitmap dumped)
4830 fprintf (file, "(%d\n", c);
4832 for (i = 0; i < rdg->n_vertices; i++)
4833 if (rdg->vertices[i].component == c)
4836 bitmap_set_bit (dumped, i);
4838 dump_rdg_vertex (file, rdg, i);
4841 fprintf (file, ")\n");
4844 /* Call dump_rdg_vertex on stderr. */
4847 debug_rdg_component (struct graph *rdg, int c)
4849 dump_rdg_component (stderr, rdg, c, NULL);
4852 /* Dump the reduced dependence graph RDG to FILE. */
4855 dump_rdg (FILE *file, struct graph *rdg)
4858 bitmap dumped = BITMAP_ALLOC (NULL);
4860 fprintf (file, "(rdg\n");
4862 for (i = 0; i < rdg->n_vertices; i++)
4863 if (!bitmap_bit_p (dumped, i))
4864 dump_rdg_component (file, rdg, rdg->vertices[i].component, dumped);
4866 fprintf (file, ")\n");
4867 BITMAP_FREE (dumped);
4870 /* Call dump_rdg on stderr. */
4873 debug_rdg (struct graph *rdg)
4875 dump_rdg (stderr, rdg);
4879 dot_rdg_1 (FILE *file, struct graph *rdg)
4883 fprintf (file, "digraph RDG {\n");
4885 for (i = 0; i < rdg->n_vertices; i++)
4887 struct vertex *v = &(rdg->vertices[i]);
4888 struct graph_edge *e;
4890 /* Highlight reads from memory. */
4891 if (RDG_MEM_READS_STMT (rdg, i))
4892 fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
4894 /* Highlight stores to memory. */
4895 if (RDG_MEM_WRITE_STMT (rdg, i))
4896 fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
4899 for (e = v->succ; e; e = e->succ_next)
4900 switch (RDGE_TYPE (e))
4903 fprintf (file, "%d -> %d [label=input] \n", i, e->dest);
4907 fprintf (file, "%d -> %d [label=output] \n", i, e->dest);
4911 /* These are the most common dependences: don't print these. */
4912 fprintf (file, "%d -> %d \n", i, e->dest);
4916 fprintf (file, "%d -> %d [label=anti] \n", i, e->dest);
4924 fprintf (file, "}\n\n");
4927 /* Display the Reduced Dependence Graph using dotty. */
4928 extern void dot_rdg (struct graph *);
4931 dot_rdg (struct graph *rdg)
4933 /* When debugging, enable the following code. This cannot be used
4934 in production compilers because it calls "system". */
4936 FILE *file = fopen ("/tmp/rdg.dot", "w");
4937 gcc_assert (file != NULL);
4939 dot_rdg_1 (file, rdg);
4942 system ("dotty /tmp/rdg.dot &");
4944 dot_rdg_1 (stderr, rdg);
4948 /* This structure is used for recording the mapping statement index in
4951 struct GTY(()) rdg_vertex_info
4957 /* Returns the index of STMT in RDG. */
4960 rdg_vertex_for_stmt (struct graph *rdg, gimple stmt)
4962 struct rdg_vertex_info rvi, *slot;
4965 slot = (struct rdg_vertex_info *) htab_find (rdg->indices, &rvi);
4973 /* Creates an edge in RDG for each distance vector from DDR. The
4974 order that we keep track of in the RDG is the order in which
4975 statements have to be executed. */
4978 create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
4980 struct graph_edge *e;
4982 data_reference_p dra = DDR_A (ddr);
4983 data_reference_p drb = DDR_B (ddr);
4984 unsigned level = ddr_dependence_level (ddr);
4986 /* For non scalar dependences, when the dependence is REVERSED,
4987 statement B has to be executed before statement A. */
4989 && !DDR_REVERSED_P (ddr))
4991 data_reference_p tmp = dra;
4996 va = rdg_vertex_for_stmt (rdg, DR_STMT (dra));
4997 vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb));
4999 if (va < 0 || vb < 0)
5002 e = add_edge (rdg, va, vb);
5003 e->data = XNEW (struct rdg_edge);
5005 RDGE_LEVEL (e) = level;
5006 RDGE_RELATION (e) = ddr;
5008 /* Determines the type of the data dependence. */
5009 if (DR_IS_READ (dra) && DR_IS_READ (drb))
5010 RDGE_TYPE (e) = input_dd;
5011 else if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
5012 RDGE_TYPE (e) = output_dd;
5013 else if (DR_IS_WRITE (dra) && DR_IS_READ (drb))
5014 RDGE_TYPE (e) = flow_dd;
5015 else if (DR_IS_READ (dra) && DR_IS_WRITE (drb))
5016 RDGE_TYPE (e) = anti_dd;
5019 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
5020 the index of DEF in RDG. */
5023 create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
5025 use_operand_p imm_use_p;
5026 imm_use_iterator iterator;
5028 FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
5030 struct graph_edge *e;
5031 int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
5036 e = add_edge (rdg, idef, use);
5037 e->data = XNEW (struct rdg_edge);
5038 RDGE_TYPE (e) = flow_dd;
5039 RDGE_RELATION (e) = NULL;
5043 /* Creates the edges of the reduced dependence graph RDG. */
5046 create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs)
5049 struct data_dependence_relation *ddr;
5050 def_operand_p def_p;
5053 FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
5054 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
5055 create_rdg_edge_for_ddr (rdg, ddr);
5057 for (i = 0; i < rdg->n_vertices; i++)
5058 FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
5060 create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
5063 /* Build the vertices of the reduced dependence graph RDG. */
5066 create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts)
5071 FOR_EACH_VEC_ELT (gimple, stmts, i, stmt)
5073 VEC (data_ref_loc, heap) *references;
5075 struct vertex *v = &(rdg->vertices[i]);
5076 struct rdg_vertex_info *rvi = XNEW (struct rdg_vertex_info);
5077 struct rdg_vertex_info **slot;
5081 slot = (struct rdg_vertex_info **) htab_find_slot (rdg->indices, rvi, INSERT);
5088 v->data = XNEW (struct rdg_vertex);
5089 RDG_STMT (rdg, i) = stmt;
5091 RDG_MEM_WRITE_STMT (rdg, i) = false;
5092 RDG_MEM_READS_STMT (rdg, i) = false;
5093 if (gimple_code (stmt) == GIMPLE_PHI)
5096 get_references_in_stmt (stmt, &references);
5097 FOR_EACH_VEC_ELT (data_ref_loc, references, j, ref)
5099 RDG_MEM_WRITE_STMT (rdg, i) = true;
5101 RDG_MEM_READS_STMT (rdg, i) = true;
5103 VEC_free (data_ref_loc, heap, references);
5107 /* Initialize STMTS with all the statements of LOOP. When
5108 INCLUDE_PHIS is true, include also the PHI nodes. The order in
5109 which we discover statements is important as
5110 generate_loops_for_partition is using the same traversal for
5111 identifying statements. */
5114 stmts_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
5117 basic_block *bbs = get_loop_body_in_dom_order (loop);
5119 for (i = 0; i < loop->num_nodes; i++)
5121 basic_block bb = bbs[i];
5122 gimple_stmt_iterator bsi;
5125 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
5126 VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
5128 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
5130 stmt = gsi_stmt (bsi);
5131 if (gimple_code (stmt) != GIMPLE_LABEL && !is_gimple_debug (stmt))
5132 VEC_safe_push (gimple, heap, *stmts, stmt);
5139 /* Returns true when all the dependences are computable. */
5142 known_dependences_p (VEC (ddr_p, heap) *dependence_relations)
5147 FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
5148 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
5154 /* Computes a hash function for element ELT. */
5157 hash_stmt_vertex_info (const void *elt)
5159 const struct rdg_vertex_info *const rvi =
5160 (const struct rdg_vertex_info *) elt;
5161 gimple stmt = rvi->stmt;
5163 return htab_hash_pointer (stmt);
5166 /* Compares database elements E1 and E2. */
5169 eq_stmt_vertex_info (const void *e1, const void *e2)
5171 const struct rdg_vertex_info *elt1 = (const struct rdg_vertex_info *) e1;
5172 const struct rdg_vertex_info *elt2 = (const struct rdg_vertex_info *) e2;
5174 return elt1->stmt == elt2->stmt;
5177 /* Free the element E. */
5180 hash_stmt_vertex_del (void *e)
5185 /* Build the Reduced Dependence Graph (RDG) with one vertex per
5186 statement of the loop nest, and one edge per data dependence or
5187 scalar dependence. */
5190 build_empty_rdg (int n_stmts)
5192 int nb_data_refs = 10;
5193 struct graph *rdg = new_graph (n_stmts);
5195 rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
5196 eq_stmt_vertex_info, hash_stmt_vertex_del);
5200 /* Build the Reduced Dependence Graph (RDG) with one vertex per
5201 statement of the loop nest, and one edge per data dependence or
5202 scalar dependence. */
5205 build_rdg (struct loop *loop,
5206 VEC (loop_p, heap) **loop_nest,
5207 VEC (ddr_p, heap) **dependence_relations,
5208 VEC (data_reference_p, heap) **datarefs)
5210 struct graph *rdg = NULL;
5212 if (compute_data_dependences_for_loop (loop, false, loop_nest, datarefs,
5213 dependence_relations)
5214 && known_dependences_p (*dependence_relations))
5216 VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, 10);
5217 stmts_from_loop (loop, &stmts);
5218 rdg = build_empty_rdg (VEC_length (gimple, stmts));
5219 create_rdg_vertices (rdg, stmts);
5220 create_rdg_edges (rdg, *dependence_relations);
5221 VEC_free (gimple, heap, stmts);
5227 /* Free the reduced dependence graph RDG. */
5230 free_rdg (struct graph *rdg)
5234 for (i = 0; i < rdg->n_vertices; i++)
5236 struct vertex *v = &(rdg->vertices[i]);
5237 struct graph_edge *e;
5239 for (e = v->succ; e; e = e->succ_next)
5245 htab_delete (rdg->indices);
5249 /* Initialize STMTS with all the statements of LOOP that contain a
5253 stores_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
5256 basic_block *bbs = get_loop_body_in_dom_order (loop);
5258 for (i = 0; i < loop->num_nodes; i++)
5260 basic_block bb = bbs[i];
5261 gimple_stmt_iterator bsi;
5263 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
5264 if (gimple_vdef (gsi_stmt (bsi)))
5265 VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
5271 /* Returns true when the statement at STMT is of the form "A[i] = 0"
5272 that contains a data reference on its LHS with a stride of the same
5273 size as its unit type. */
5276 stmt_with_adjacent_zero_store_dr_p (gimple stmt)
5280 struct data_reference *dr;
5283 || !gimple_vdef (stmt)
5284 || !gimple_assign_single_p (stmt))
5287 lhs = gimple_assign_lhs (stmt);
5288 rhs = gimple_assign_rhs1 (stmt);
5290 /* If this is a bitfield store bail out. */
5291 if (TREE_CODE (lhs) == COMPONENT_REF
5292 && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
5295 if (!(integer_zerop (rhs) || real_zerop (rhs)))
5298 dr = XCNEW (struct data_reference);
5300 DR_STMT (dr) = stmt;
5303 res = dr_analyze_innermost (dr, loop_containing_stmt (stmt))
5304 && stride_of_unit_type_p (DR_STEP (dr), TREE_TYPE (lhs));
5310 /* Initialize STMTS with all the statements of LOOP that contain a
5311 store to memory of the form "A[i] = 0". */
5314 stores_zero_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
5318 gimple_stmt_iterator si;
5320 basic_block *bbs = get_loop_body_in_dom_order (loop);
5322 for (i = 0; i < loop->num_nodes; i++)
5323 for (bb = bbs[i], si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
5324 if ((stmt = gsi_stmt (si))
5325 && stmt_with_adjacent_zero_store_dr_p (stmt))
5326 VEC_safe_push (gimple, heap, *stmts, gsi_stmt (si));
5331 /* For a data reference REF, return the declaration of its base
5332 address or NULL_TREE if the base is not determined. */
5335 ref_base_address (gimple stmt, data_ref_loc *ref)
5337 tree base = NULL_TREE;
5339 struct data_reference *dr = XCNEW (struct data_reference);
5341 DR_STMT (dr) = stmt;
5342 DR_REF (dr) = *ref->pos;
5343 dr_analyze_innermost (dr, loop_containing_stmt (stmt));
5344 base_address = DR_BASE_ADDRESS (dr);
5349 switch (TREE_CODE (base_address))
5352 base = TREE_OPERAND (base_address, 0);
5356 base = base_address;
5365 /* Determines whether the statement from vertex V of the RDG has a
5366 definition used outside the loop that contains this statement. */
5369 rdg_defs_used_in_other_loops_p (struct graph *rdg, int v)
5371 gimple stmt = RDG_STMT (rdg, v);
5372 struct loop *loop = loop_containing_stmt (stmt);
5373 use_operand_p imm_use_p;
5374 imm_use_iterator iterator;
5376 def_operand_p def_p;
5381 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF)
5383 FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p))
5385 if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop)
5393 /* Determines whether statements S1 and S2 access to similar memory
5394 locations. Two memory accesses are considered similar when they
5395 have the same base address declaration, i.e. when their
5396 ref_base_address is the same. */
5399 have_similar_memory_accesses (gimple s1, gimple s2)
5403 VEC (data_ref_loc, heap) *refs1, *refs2;
5404 data_ref_loc *ref1, *ref2;
5406 get_references_in_stmt (s1, &refs1);
5407 get_references_in_stmt (s2, &refs2);
5409 FOR_EACH_VEC_ELT (data_ref_loc, refs1, i, ref1)
5411 tree base1 = ref_base_address (s1, ref1);
5414 FOR_EACH_VEC_ELT (data_ref_loc, refs2, j, ref2)
5415 if (base1 == ref_base_address (s2, ref2))
5423 VEC_free (data_ref_loc, heap, refs1);
5424 VEC_free (data_ref_loc, heap, refs2);
5428 /* Helper function for the hashtab. */
5431 have_similar_memory_accesses_1 (const void *s1, const void *s2)
5433 return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple) s1),
5434 CONST_CAST_GIMPLE ((const_gimple) s2));
5437 /* Helper function for the hashtab. */
5440 ref_base_address_1 (const void *s)
5442 gimple stmt = CONST_CAST_GIMPLE ((const_gimple) s);
5444 VEC (data_ref_loc, heap) *refs;
5448 get_references_in_stmt (stmt, &refs);
5450 FOR_EACH_VEC_ELT (data_ref_loc, refs, i, ref)
5453 res = htab_hash_pointer (ref_base_address (stmt, ref));
5457 VEC_free (data_ref_loc, heap, refs);
5461 /* Try to remove duplicated write data references from STMTS. */
5464 remove_similar_memory_refs (VEC (gimple, heap) **stmts)
5468 htab_t seen = htab_create (VEC_length (gimple, *stmts), ref_base_address_1,
5469 have_similar_memory_accesses_1, NULL);
5471 for (i = 0; VEC_iterate (gimple, *stmts, i, stmt); )
5475 slot = htab_find_slot (seen, stmt, INSERT);
5478 VEC_ordered_remove (gimple, *stmts, i);
5481 *slot = (void *) stmt;
5489 /* Returns the index of PARAMETER in the parameters vector of the
5490 ACCESS_MATRIX. If PARAMETER does not exist return -1. */
5493 access_matrix_get_index_for_parameter (tree parameter,
5494 struct access_matrix *access_matrix)
5497 VEC (tree,heap) *lambda_parameters = AM_PARAMETERS (access_matrix);
5498 tree lambda_parameter;
5500 FOR_EACH_VEC_ELT (tree, lambda_parameters, i, lambda_parameter)
5501 if (lambda_parameter == parameter)
5502 return i + AM_NB_INDUCTION_VARS (access_matrix);